Skip to main content
12 of 12
edited tags
user369335
  • 696
  • 1
  • 5
  • 22

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

user369335
  • 696
  • 1
  • 5
  • 22