# One question on linear combinations of roots of unity

For $$n \geq 1$$, I want to find all solutions $$x_i$$ of the 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}$$$$

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

• Do the solutions for small n suggest any pattern? Commented Dec 22, 2022 at 16:19
• Although this also has strong "harmonic analysis" aspects, I suspect that it would be easier to give structural answers when $n$ is prime $p$, perhaps especially when $p=2q+1$ with prime $q$... for Galois-theory reasons. This would be a quite slim slice of the whole space of examples... but/and would it be of interest to you? Commented Dec 22, 2022 at 21:25
• For prime $p=4n-1$, up to translation, complex conjugation and complementation, the function giving rise to integral norm seems to to be the one mapping a nonzero square mod $p$ to $1$ and nonsquares and zero mod $p$ to $-1$.
– YCor
Commented Dec 23, 2022 at 20:18
• Your tables took a very long time to render for me because each number was rendered as its own formula. Removing them from math mode seems to preserve all semantic information and make the page load much more quickly, so I did so. I hope that is all right. Commented Dec 23, 2022 at 22:41
• It is much faster now :) Thank you. @LSpice Commented Dec 23, 2022 at 22:49

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

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

• For $p=31=2^5-1$ and $p=73$, I have found something related in this paper -- "A theorem in finite projective geometry and some applications to number theory" by Singer. ams.org/journals/tran/1938-043-03/S0002-9947-1938-1501951-4/… Commented Dec 27, 2022 at 7:35
• @user369335 thanks! it indeed says there is a solution with $c=1$ (and cardinal $m+1$) modulo $p=m^2+m+1$ for every prime power $m$. This indeed realizes the following values of $(p,q)$: $(7,3)$, $(13,4)$, $(31,6)$, $(73,9)$, $(307,18)$, etc. I'll need to look closer into it to understand the construction of the desired subset.
– YCor
Commented Dec 27, 2022 at 8:08
• I got it. For a prime power $m$, Singer finds an element $T$ 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)$. Define $I$ as the set of $i\in\mathbf{Z}/p\mathbf{Z}$ such that $x_0,Tx_0,T^ix_0$ are aligned. Then $I$ is the desired subset. 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\}$.
– YCor
Commented Dec 27, 2022 at 10:47
• Note that this explains the case $(p,|I|)=(31,6)$ but not the case $(p,|I|)=(31,10)$.
– YCor
Commented Dec 27, 2022 at 13:49
• @user369335 ah, thanks! indeed I misread your table, from which indeed $(31,10)$ is excluded.
– YCor
Commented Dec 27, 2022 at 15:55

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.

• The list you displayed seems to suggest that there is nothing else when $n$ is prime.
– YCor
Commented Dec 23, 2022 at 22:22
• @YCor $n=31$ is a counter example. $\lvert z \rvert^2=20$ have $620$ solutions. Commented Dec 24, 2022 at 3:32
• @user369335 OK, thanks (when I wrote my previous comment the table was up to 30). What is $\{i: x_i=1\}$ for some example realizing $|z|^2=20$?
– YCor
Commented Dec 24, 2022 at 7:03
• well, the set of solutions is invariant under the affine group (here, of order 620=31.30) so it's enough to write one solution per orbit (and here's it's a single orbit).
– YCor
Commented Dec 24, 2022 at 15:24
• Well according to the table above there are 496 solutions, which does not divide 620. So there must be more than one orbit actually. Commented Dec 24, 2022 at 16:22