For $n \geq 1$, I want to find all solutions $x\_i$ of the equation


\begin{equation}
 \begin{array}l
 x\_i \in \mathbb{Z}, i=0,1,2\dotsc,n-1 \\
 x\_i^2 = 1, i=0,1,2\dotsc,n-1 \\
 \omega = \cos(2\pi/n)+i\sin(2\pi/n) \\ 
 z = \sum\_{i=0}^{n-1} x\_i \omega^{i} \\
 \lvert z\rvert^2 \in \mathbb{Z}.
 \end{array}
\end{equation}


As an example, $x\_i = 1$, $i=0,1,2\dotsc,n-1$ is one solution to this equation.
And $x\_i = -1$, $i=0,1,2\dotsc,n-1$ is another solution.
For small $n$, all solutions can be found by mathematical software.
Is there any good idea for bigger $n$?


Here is the computational result for small $n$:





| $n$ | Number of solutions | $2^n$ | Percentage |
| --- | --- | --- | --- |
| 1 | 2 | 2 | 100% |
| 2 | 4 | 4 | 100% |
| 3 | 8 | 8 | 100% |
| 4 | 16 | 16 | 100% |
| 5 | 12 | 32 | 37.5% |
| 6 | 64 | 64 | 100% |
| 7 | 44 | 128 | 34.375% |
| 8 | 144 | 256 | 56.25% |
| 9 | 80 | 512 | 15.625% |
| 10 | 244 | 1024 | 23.8281% |
| 11 | 68 | 2048 | 3.32031% |
| 12 | 1816 | 4096 | 44.3359% |
| 13 | 132 | 8192 | 1.61132% |
| 14 | 2020 | 16384 | 12.3291% |
| 15 | 1628 | 32768 | 4.96826% |
| 16 | 4480 | 65536 | 6.83593% |
| 17 | 36 | 131072 | 0.02746% |
| 18 | 17200 | 262144 | 6.56127% |
| 19 | 116 | 524288 | 0.02212% |
| 20 | 33416 | 1048576 | 3.18679% |
| 21 | 6644 | 2097152 | 0.31681% |
| 22 | 30364 | 4194304 | 0.72393% |
| 23 | 140 | 8388608 | 0.00166% |
| 24 | 530512 | 16777216 | 3.16209% |
| 25 | 832 | 33554432 | 0.00247% |
| 26 | 173164 | 67108864 | 0.25803% |
| 27 | 14336 | 134217728 | 0.01068% |
| 28 | 673024 | 268435456 | 0.25072% |
| 29 | 60 | 536870912 | 0.00001% |
| 30 | 12263284 | 1073741824 | 1.14210% |
| 31 | 1180 | 2147483648 | 0.00005% |
| 32 | 2228224 | 4294967296 | 0.05187% |
| 33 | 87788 | 8589934592 | 0.00102% |
| 34 | 2359468 | 17179869184 | 0.01373% |
| 35 | 17098 | 34359738368 | 0.00004% |
| 36 | 52492960 | 68719476736 | 0.07638% |



Here is the further detail, the prime number related patterns are quite obvious.





| $n$ | $\lvert z\rvert^2$ | Number of solutions |
| --- | --- | --- |
| 1 | 1 | 2 |
| 2 | 0 | 2 |
| 2 | 4 | 2 |
| 3 | 0 | 2 |
| 3 | 4 | 6 |
| 4 | 0 | 4 |
| 4 | 4 | 8 |
| 4 | 8 | 4 |
| 5 | 0 | 2 |
| 5 | 4 | 10 |
| 6 | 0 | 10 |
| 6 | 4 | 36 |
| 6 | 12 | 12 |
| 6 | 16 | 6 |
| 7 | 0 | 2 |
| 7 | 4 | 14 |
| 7 | 8 | 28 |
| 8 | 0 | 16 |
| 8 | 4 | 64 |
| 8 | 8 | 32 |
| 8 | 12 | 32 |
| 9 | 0 | 8 |
| 9 | 4 | 72 |
| 10 | 0 | 34 |
| 10 | 4 | 180 |
| 10 | 16 | 10 |
| 10 | 20 | 20 |
| 11 | 0 | 2 |
| 11 | 4 | 22 |
| 11 | 12 | 44 |
| 12 | 0 | 100 |
| 12 | 4 | 720 |
| 12 | 8 | 432 |
| 12 | 12 | 240 |
| 12 | 16 | 120 |
| 12 | 20 | 144 |
| 12 | 24 | 48 |
| 12 | 32 | 12 |
| 13 | 0 | 2 |
| 13 | 4 | 26 |
| 13 | 12 | 104 |
| 14 | 0 | 130 |
| 14 | 4 | 924 |
| 14 | 8 | 672 |
| 14 | 16 | 238 |
| 14 | 28 | 28 |
| 14 | 32 | 28 |
| 15 | 0 | 38 |
| 15 | 4 | 600 |
| 15 | 8 | 600 |
| 15 | 12 | 60 |
| 15 | 16 | 210 |
| 15 | 20 | 60 |
| 15 | 24 | 60 |
| 16 | 0 | 256 |
| 16 | 4 | 2048 |
| 16 | 8 | 1024 |
| 16 | 12 | 1024 |
| 16 | 28 | 128 |
| 17 | 0 | 2 |
| 17 | 4 | 34 |
| 18 | 0 | 1000 |
| 18 | 4 | 10800 |
| 18 | 12 | 3600 |
| 18 | 16 | 1800 |
| 19 | 0 | 2 |
| 19 | 4 | 38 |
| 19 | 20 | 76 |
| 20 | 0 | 1156 |
| 20 | 4 | 12240 |
| 20 | 8 | 6480 |
| 20 | 12 | 5760 |
| 20 | 16 | 680 |
| 20 | 20 | 4640 |
| 20 | 24 | 1440 |
| 20 | 28 | 640 |
| 20 | 32 | 20 |
| 20 | 36 | 80 |
| 20 | 40 | 240 |
| 20 | 48 | 40 |
| 21 | 0 | 134 |
| 21 | 4 | 2856 |
| 21 | 8 | 2184 |
| 21 | 12 | 84 |
| 21 | 16 | 714 |
| 21 | 24 | 168 |
| 21 | 28 | 420 |
| 21 | 32 | 84 |
| 22 | 0 | 2050 |
| 22 | 4 | 22572 |
| 22 | 12 | 4224 |
| 22 | 16 | 22 |
| 22 | 20 | 1408 |
| 22 | 44 | 44 |
| 22 | 48 | 44 |
| 23 | 0 | 2 |
| 23 | 4 | 46 |
| 23 | 24 | 92 |
| 24 | 0 | 10000 |
| 24 | 4 | 144000 |
| 24 | 8 | 86400 |
| 24 | 12 | 151680 |
| 24 | 16 | 24000 |
| 24 | 20 | 63360 |
| 24 | 24 | 26880 |
| 24 | 28 | 11520 |
| 24 | 32 | 2400 |
| 24 | 36 | 6720 |
| 24 | 40 | 1920 |
| 24 | 44 | 960 |
| 24 | 48 | 480 |
| 24 | 60 | 192 |
| 25 | 0 | 32 |
| 25 | 4 | 800 |
| 26 | 0 | 8194 |
| 26 | 4 | 106548 |
| 26 | 12 | 54912 |
| 26 | 16 | 26 |
| 26 | 36 | 3328 |
| 26 | 48 | 104 |
| 26 | 52 | 52 |
| 27 | 0 | 512 |
| 27 | 4 | 13824 |
| 28 | 0 | 16900 |
| 28 | 4 | 240240 |
| 28 | 8 | 296688 |
| 28 | 16 | 94136 |
| 28 | 20 | 3696 |
| 28 | 28 | 7280 |
| 28 | 32 | 10892 |
| 28 | 40 | 2688 |
| 28 | 52 | 336 |
| 28 | 56 | 112 |
| 28 | 64 | 56 |
| 29 | 0 | 2 |
| 29 | 4 | 58 |
| 30 | 0 | 146854 |
| 30 | 4 | 2856780 |
| 30 | 8 | 3657600 |
| 30 | 12 | 1151400 |
| 30 | 16 | 2268360 |
| 30 | 20 | 528600 |
| 30 | 24 | 675840 |
| 30 | 28 | 240480 |
| 30 | 32 | 447480 |
| 30 | 36 | 40980 |
| 30 | 40 | 92160 |
| 30 | 44 | 72000 |
| 30 | 48 | 38460 |
| 30 | 52 | 1080 |
| 30 | 56 | 28800 |
| 30 | 60 | 5160 |
| 30 | 64 | 7410 |
| 30 | 68 | 120 |
| 30 | 72 | 1920 |
| 30 | 76 | 1320 |
| 30 | 80 | 300 |
| 30 | 92 | 120 |
| 30 | 96 | 60 |
| 31 | 0 | 2 |
| 31 | 4 | 62 |
| 31 | 20 | 620 |
| 31 | 32 | 496 |
| 32 | 0 | 65536 |
| 32 | 4 | 1048576 |
| 32 | 8 | 524288 |
| 32 | 12 | 524288 |
| 32 | 28 | 65536 |
| 33 | 0 | 2054 |
| 33 | 4 | 67848 |
| 33 | 12 | 13068 |
| 33 | 16 | 66 |
| 33 | 20 | 4224 |
| 33 | 36 | 264 |
| 33 | 44 | 132 |
| 33 | 48 | 132 |
| 34 | 0 | 131074 |
| 34 | 4 | 2228292 |
| 34 | 16 | 34 |
| 34 | 68 | 68 |
| 35 | 0 | 228 |
| 35 | 4 | 5600 |
| 35 | 8 | 5320 |
| 35 | 12 | 3080 |
| 35 | 16 | 1190 |
| 35 | 20 | 140 |
| 35 | 24 | 280 |
| 35 | 28 | 140 |
| 35 | 32 | 140 |
| 35 | 36 | 420 |
| 35 | 40 | 280 |
| 35 | 44 | 140 |
| 35 | 72 | 140 |
| 36 | 0 | 1000000 |
| 36 | 4 | 21600000 |
| 36 | 8 | 12960000 |
| 36 | 12 | 7200000 |
| 36 | 16 | 3600000 |
| 36 | 20 | 4320000 |
| 36 | 24 | 1440000 |
| 36 | 32 | 360000 |
| 36 | 68 | 12960 |



Actually, this problem has some variations, for example:


Consider $x\_i = 1, 0$ or $x\_i = \pm 1,0$ instead of $x\_i = \pm 1$.


Consider remove the constraint $x\_i^2=1$.


Consider $x\_i \in \mathbb{Q}$ or $x\_i \in \mathbb{R}$ instead of $x\_i \in \mathbb{Z}$.


Any comment/answer to this problem and its variations will be appreciated.


Here are my motivations:


First, in algebraic number theory, a Gauss sum or Gaussian sum is a particular kind of finite sum of roots of unity. From this equation, maybe we can find out more interesting formulas.


Second, in linear algebra, the order of Hadamard matrices is usually $4k$, where $k=1,2,3,...$, and here $\lvert z \rvert^2$ is usually $4k$ too. Although Hadamard conjecture is still an open problem, maybe one day this conjecture will be proven and we will find out that it is not a coincidence....



One question on linear combinations of roots of unity
$\newcommand{\Z}{\mathbf{Z}}\newcommand{\Q}{\mathbf{Q}}\DeclareMathOperator\W{\mathcal{W}}$This is just an extended comment. Write $\zeta\_n=\exp(2i\pi/n)$.


For a subset $I$ of $\Z/n\Z$, write $$z\_I=z\_{n,I}=\sum\_{j\in I}\zeta\_n^j,$$ and $Z\_I=Z\_{n,I}=|z\_{n,I}|^2$ (we omit $n$ in the notation when there is no ambiguity).


The question is equivalent to classifying those $I$ such that $Z\_{n,I}\in\frac14\Z$, and describe the numbers $Z\_{n,I}$ thus obtained. Indeed, the alternate sum $Z'\_I=\sum\_{j\in\Z/n\Z}a\_j\zeta\_n^j$, where $a\_j=1$ for $j\in I$ and $a\_j=-1$ for $j\notin I$, is equal to $4Z\_I$.


Now, observe that $Z\_I=z\_I\overline{z\_I}$ is an algebraic integer. Thus, $Z\_I\in\Q$ is equivalent to $Z\_I\in\Z$. This explains why the norm $Z'\_I=4Z\_I$ in your table (second column) is always a multiple of 4.


Let $\W(n)$ be the set of subsets $I$ of $\Z/n\Z$ such that $Z\_I\in\Z$ (or equivalently $Z\_I\in\Q$)




---


Note that $\W(n)$ is stable under complementation, and the function $I\mapsto Z\_I$ is also invariant under complementation. This reduces to describing subsets $I\in\W(n)$ with $|I|\le n/2$. Also note that $\W(n)$ is invariant under translation in $\Z/n\Z$. It is also invariant under the action of $(\Z/n\Z)^\times$, because the Galois group of the complex numbers over $\Q$ acts transitively on primitive $n$-roots of unity. Thus, $\W(n)$ is $(\Z/n\Z)\rtimes (\Z/n\Z)^\times$-invariant.


Trivial examples of elements of $\W(n)$ are the empty set (with $Z\_\emptyset=0$) and singletons (with $Z\_{\{j\}}=1$), and thus their complements as well.


Describing more generally those functions $f:\Z/n\Z\to\Q$ such that $\sum\_{j\in\Z/n\Z}f(j)\zeta\_n^j\in\Q$ can sound as just "more general" but it is also more natural and might allow to use more tools, e.g., of representation-theoretic flavor.




---


Now here are some comments on the case when $n=p$ is prime.


I start with extracting from OP's table these cases:


In this case (and only in this case), the "only" relation between the $\zeta\_p^j$ is the fact that the sum is zero. That is, the family $(\zeta\_p^j)\_{0\le j\le p-2}$ is linearly $\Q$-free.


Rewrite the condition $Z\_I\in\Z$ as $\sum\_{j,k\in I}\zeta\_n^{j-k}\in\Z$. Write $q=|I|$. In turn, this can be written as
$(Z\_I=)q+\sum\_{\ell\in\Z/p\Z-\{0\}}W\_{I,\ell}\zeta\_n^\ell\in\Z$, with $W\_{I,\ell}=|\{(j,k)\in I^2:j-k=\ell\}|$. Because of the freeness condition, this precisely means that the cardinal $W\_{I,\ell}$ is independent of $\ell\in\Z/p\Z-\{0\}$. If this cardinal is $c$, we obtain that $Z\_I=q+c\sum\_{\ell\in\Z/p\Z-\{0\}}\zeta\_n^\ell=q-c$. For emphasis, let us write:



> 
> For $p$ prime, a subset $I$ of $\Z/p\Z$ is in $\W(p)$ if and only if the cardinal of $\{(j,k)\in I^2:j-k=\ell\}$ is independent of $p$.
> 
> 
> 


We also have $\sum\_{\ell\in\Z/p\Z-\{0\}}W\_{I,\ell}=q(q-1)$. Hence, if $|W\_{I,\ell}|=c$ for all nonzero $\ell$, we deduce $(p-1)c=q(q-1)$. This shows that the only cardinals $q$ to consider are those such that $p-1$ divides $q(q-1)$ (or, equivalently, such that $p-1$ divides $q(p-q)$). This is quite restrictive. This equality can be rewritten as $Z\_I=q(p-q)/(p-1)$.


One can list those pairs $(p,q)$ with $p$ prime, $0\le q\le p/2$, such that $p-1$ divides $q(q-1)$. Among them, the following families, which can be realized:


(0) For every $p$, the trivial solutions $q\in\{0,1\}$ (empty set and singletons);


Here is already what we can extract from OP's table in the prime case (adding the $q$ and $c$ columns, and dividing the number of cases by 2 since OP's table also includes the cardinal $p-q$ case).





| $p$ | $q$ | $Z\_{p,q}$ | $c\_{p,q}$ | number of cases |
| --- | --- | --- | --- | --- |
| $p$ | 0 | 0 | 0 | 1 |
| $p$ | 1 | 1 | 0 | $p$ |
| 7 | 3 | 2 | 1 | $2p$ |
| 11 | 5 | 3 | 2 | $2p$ |
| 13 | 4 | 3 | 1 | $4p$ |
| 19 | 9 | 5 | 4 | $2p$ |
| 23 | 11 | 6 | 5 | $2p$ |
| 31 | 6 | 5 | 1 | $10p$ |
| 31 | 15 | 8 | 7 | $8p$ |



(1) The next easy case is $q=(p-1)/2$ (i.e., the largest possible $q$ subject to $q\le p/2$). in which the divisibility condition is equivalent to $p\equiv 3(\bmod 4)$. In this case, this is indeed achieved by a subset $I$, namely, $I$ being the set of nonzero squares modulo $p$. In this case $Z\_{p,q}=(p+1)/4$ and $c=c\_{p,q}$ equals $(p-3)/4$.


Here are the first few values (the case $p=3$ is degenerate since this is part of Case (0))





| $p$ | $q$ | $Z\_{p,q}$ | $c\_{p,q}$ |
| --- | --- | --- | --- |
| 3 | 1 | 1 | 0 |
| 7 | 3 | 2 | 1 |
| 11 | 5 | 3 | 2 |
| 19 | 9 | 5 | 4 |
| 23 | 11 | 6 | 5 |
| 31 | 15 | 8 | 7 |
| 43 | 21 | 2 | 10 |
| 47 | 23 | 4 | 11 |



(2) Another family (empirically obtained): for each prime $p$ of the form $4k^2+1$ for $k$ odd (hence $p\equiv 5(\bmod 16)$), with $q=(p-1)/4(=k^2)$, achieved by the set $I$ of nonzero fourth powers modulo $p$. In this case $Z\_{p,q}=3(p-5)/16+1$.


The set of possible $p$ is infinite, by standard conjectures. Here are the first few values (the case $p=5$ being degenerate, being part of (0)).





| $p$ | $q$ | $Z\_{p,q}$ | $c\_{p,q}$ |
| --- | --- | --- | --- |
| 5 | 1 | 1 | 0 |
| 37 | 9 | 7 | 2 |
| 101 | 25 | 19 | 6 |
| 197 | 49 | 37 | 12 |
| 677 | 169 | 127 | 42 |
| 2917 | 729 | 547 | 182 |
| 4357 | 1089 | 817 | 272 |
| 5477 | 1369 | 1027 | 342 |



(3) Another family (empirically obtained): for each prime $p$ of the form $4k^2+9$ for $k$ odd (hence $p\equiv 13(\bmod 16)$), with $q=(p+3)/4(=k^2+3)$, achieved by the set $I$ of fourth powers modulo $p$ (including zero). In this case $Z\_{p,q}=3(p+3)/16$.


The set of possible $p$ is infinite, by standard conjectures. Here are the first few values :





| $p$ | $q$ | $Z\_{p,q}$ | $c\_{p,q}$ |
| --- | --- | --- | --- |
| 13 | 4 | 3 | 1 |
| 109 | 28 | 21 | 7 |
| 1453 | 364 | 273 | 91 |
| 3373 | 844 | 633 | 211 |
| 3853 | 964 | 723 | 241 |
| 4909 | 1228 | 921 | 307 |
| 6733 | 1684 | 1263 | 421 |



(4) For $p=73$, $q=9$, this is achieved by the set of nonzero 8th powers (here $Z\_{73,9}=8$, $c\_{73,9}=1$). I don't know if this fits in a natural family.


(5) [Added after OP's comment to a first version of this answer] J. Singer's examples. (J. Singer, *"A theorem in finite projective geometry and some applications to number theory"*, Trans. AMS 43 377-385, 1938 [link](https://www.ams.org/journals/tran/1938-043-03/S0002-9947-1938-1501951-4/S0002-9947-1938-1501951-4.pdf)). For a prime-power $m$, Singer fixes an element of order $p=m^2+m+1$ in $\mathrm{PGL}\_3(\mathbf{F}\_m)$. So $\langle T\rangle$ acts simply transitively on $\mathrm{P}^2(\mathbf{F}\_m)$. Fix $x\_0\in \mathrm{P}^2(\mathbf{F}\_m)$. Let $I$ be the set of $i\in\Z/p\Z$ such that $x\_0,Tx\_0,T^ix\_0$ are aligned. Then $I\in\W(p)$, with $|I|=m+1$, $c\_I=1$, $|Z\_I|=m$. Example: $m=5$, $p=31$, $T=\begin{pmatrix}0&0&1\\1&0&0\\0&1&1\end{pmatrix}$, $x\_0=[1:0:0]$, $I=\{0,1,3,8,12,18\}$. First few values (with $p$ prime — Singer's construction doesn't assume $p$ prime: only $m$ has to be a prime power) are listed here; note that the cases $p=7,13$ already appeared in (1),(3) respectively; the case $p=73$ appeared in (4) and indeed we can obtain in this way an affine image of the set of nonzero 8th-powers.





| $p$ | $q$ | $Z\_{p,q}$ | $c\_{p,q}$ |
| --- | --- | --- | --- |
| 7 | 3 | 2 | 1 |
| 13 | 4 | 3 | 1 |
| 31 | 6 | 5 | 1 |
| 73 | 9 | 8 | 1 |
| 307 | 18 | 17 | 1 |
| 757 | 28 | 27 | 1 |
| 1723 | 42 | 41 | 1 |



While testing $I$ to be the set of given powers, including or not zero, this is all I could find. For $k$-th powers with $k\le 8$, I tested for $p\le 6000$. For $k$-powers in general I maybe tested for $p\le 200$.


This is not the whole picture, since OP's list indicates that there are other cases when $(p,q)=(31,15)$ (only $2p$ among them being corresponding to the set of nonzero squares and its affine images). There are probably also other values of $(p,q)$ but one should test for $p>31$ to find them.




---


For various $p$, I checked the possible $q$ with the condition that $p-1$ divides $q(q-1)$. The solutions with $k\le 1$ or $q=(p-1)/2$ have been described and are achieved by some $i$. Let me list the first other solutions (i.e., $1<q<(p-1)/2$), excluding also the ones already listed above in (0)-(5).





| $p$ | $q$ | $Z\_{p,q}$ | $c\_{p,q}$ |
| --- | --- | --- | --- |
| 29 | 8 | 6 | 2 |
| 31 | 10 | 7 | 3 |
| 41 | 16 | 10 | 6 |
| 43 | 7 | 6 | 1 |
| 43 | 15 | 10 | 5 |
| 53 | 13 | 10 | 3 |
| 61 | 16 | 12 | 4 |
| 61 | 21 | 14 | 7 |
| 61 | 25 | 15 | 10 |
| 67 | 12 | 10 | 2 |
| 67 | 22 | 15 | 7 |



among them, the ones for $(p,q)=(29,8)$, $=(31,10)$ $=(43,7)$ are **not** achieved.


I don't know about the other ones. About the specific case $c=1$, one checks easily that it corresponds to the case when $p$ has the form $m^2+m+1$ (with $|I|=m+1$). By (5) this is indeed achieved when $m$ is a prime power, and the case $m=6$, $p=43$ shows that it need not be achieved otherwise. The next cases are when $m$ is $12,14,15$ (corresponding to $p$ being $157$, $211$, $241$).


