One question on linear combinations of roots of unity

Question

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....

Answer 1

$\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). 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$).

Answer 2

Some ideas for this question:

Idea 1: using the formula $\sum_{i=0}^{n-1} \omega^{i}=0$ and its variations, we can obtain the solutions for $\lvert z\rvert^2=0$ or $\lvert z\rvert^2=4$.

Idea 2: if $n$ is a prime number and $n$ mod $4 ≡ 3$, using YCor's method, we can obtain the solutions for $\lvert z\rvert^2=n+1$.

Idea 3: if $n$ is a prime number of the form $k^2 + 1$, using its biquadratic residues, we can obtain the solutions for $\lvert z\rvert^2=(3n+1)/4$.

Idea 4: for $n$ is a prime number, maybe some solutions can be obtained by higher orders of residues.

I will look for other types of ideas and update this answer later.