Absolute values of sums of subsets of nth roots of 1, equalities without obvious symmetry.

Question

I attempt to count the number of different absolute values of sums of subsets of $n$-th roots of 1.
Since the $n$-th complex roots of 1 lie on the unit circle and form an $n$-gon, it is immediately obvious that subsets (of roots) show rotation and reflection symmetry. This multiplicity can be eliminated from the count by specifying the subsets using Polya's bracelet (reversible necklace) counting. See OEIS A052307. Moreover, since the sum of all $n$ roots is zero, we need only consider bracelets with $0$ to $\lfloor n/2 \rfloor$ white beads and the rest black. So, in terms of subset selections, we need only count subsets of upto $\lfloor n/2 \rfloor$ roots.
The count of all possible ($0,1$-exchangable) bracelets upto $n=19$ is:
$1, 2, 2, 4, 4, 8, 9, 19, 23, 47, 63, 137, 190, 410, 612, 1345, 2056, 4536, 7155$
The count of all different absolute values of sums of subsets of the complex $n$-th roots of 1 for $n$ upto $19$ is:
$(2), 2, 2, 3, 4, 4, 9, 10, 17, 18, 63, 24, 187, 96, 281, 241, 1964, 226, 6831$
Surprisingly, for $n$ prime in $(2,3,5,7,11)$ both counts are equal, but for $n$ in $(13,17,19,23, \ldots)$ there are subsets of roots with identical absolute value sums but with no obvious symmetry.
Example: for $n=13$,
$\{0,0,0,0,0,0,1,0,1,0,0,1,1\}$ and $\{0,0,0,0,0,1,0,0,0,1,1,0,1\}$ sum to $\sqrt3$
$\{0,0,0,0,1,0,0,1,1,0,1,1,1\}$ and $\{0,0,0,1,0,0,1,1,1,1,0,0,1\}$ to $(7+\sqrt{13})/2$
$\{0,0,0,0,1,1,0,1,0,1,0,1,1\}$ and $\{0,0,0,1,0,1,0,0,1,0,1,1,1\}$ to $(7-\sqrt{13})/2$
These $3$ 'doublets' decrease the count for $n=13$ from $190$ to $187$. For $n=17$ I find $92$ doublets, and $n=19$ has $324$ doublets. Even better: $n=23$ has $3861$ doublets and $44$ triplets.
How can this be? What kind of non-symmetric equivalence is operating here?

Answer 1

In particular for $n=13$ we have a case when $n = k^2-k+1$. Why does that matter?

Let us say we have $k$ numbers $a_1$, ..., $a_k$ in $\mathbb Z_n$.

Let us compute $|z|^2 = z\overline{z}$, where $z = \sum_{i=1}^k r^{a_i}$, $r = e^{2\pi i/n}$. Notice that $r^a$ is properly defined for $a\in \mathbb Z_n$. Multiplying $z = \sum_{i=1}^k r^{a_i}$ and $\overline{z} = \sum_{i=1}^k r^{-a_i}$, we obtain $|z|^2 = \sum_{i,j} r^{a_i-a_j}$.

Thus in order for this value to be the same for two different sets $\{a_i\}$ and $\{b_i\}$ of $k$ numbers in $\mathbb Z_n$ it would be sufficient that multisets of all possible pairwise differences $a_i-a_j$ and $b_i-b_j$ coincide. Each of these multisets has $k$ zeros and we could "replace" them with just one zero.

Then you will have $k(k-1)+1 = k^2-k+1$ of these differences. In your first example we have exactly the case where both multisets of all pairwise differences concide with $\mathbb Z_n$.

And it brings up a well known combinatorial question -- if $n = k^2-k+1$ then do there exist $k$ numbers in $\mathbb Z_n$ such that all their pairwise differences are distinct modulo $n$? This leads to the so-called Golomb rulers and Golomb modular rulers (look'em up), and this is a very interesting and complicated topic. $n=13$ is the first prime number for which there exists more than one perfect modular Golomb ruler, namely, two: $R_1=\{0, 6, 10, 11\}$ and $R_2=\{0, 7, 9, 12\}$. As you can easily check, in this case $R_2$ is simply $R_1$ multiplied by 2.

However, your other examples are of a different nature. For instance, the second example gives the following multiset of pairwise differences for both sequences: $$ \{0^6, 1^3, 2^2, 3^3, 4^3, 5^2, 6^2, 7^2, 8^2, 9^3, 10^3, 11^2, 12^3\} $$ (this is a so-called multiplicative multiset notation where $x^p$ means $p$ entries of $x$).

This seems like quite an interesting question altogether, and I will gladly spend more time on it. Hopefully, some more ideas will follow.

Answer 2

A couple of more or less obvious points (just to make sure it has been said):

a) for any composite number $n$ there will be different subsets of roots with the same sums, and therefore with the same absolute value, so we can immediately restrict our investigation to prime $n$.

b) if $n$ is prime then if sum $\sum_{i=0}^{n-1} c_i r^i$ with integer coefficients equals zero then all coefficients $c_i$ must be the same. That follows from the fact that the minimal integer polynomial for $r$ is $\sum_{i=0}^{n-1} r^i$. Now, let us say you have two subsets $A$ and $B$ of powers of $r$ with their sums having the same absolute value, with $k=|A|$, and $l=|B|$. The multisets of their pairwise differences have $k^2$ and $l^2$ elements, respectively. Since the "multiset difference" of these multisets must consist of several copies of $\mathbb Z_n$, $n$ must divide $k^2-l^2$. From $1\le k,l \le n$ follows that either $l=k$ or $l=n-k$. For the second case we can replace $B$ with $\tilde B = \mathbb Z\setminus B$, which has the same absolute value of the sum of its elements. Thus we can reduce our question to the following:

For which prime numbers $n$ there exist subsets $A$ and $B$ of $\mathbb Z_n$ (which we can also identify with the set of vertices of regular $n$-gon) satisfying the following three conditions:

1. $A$ and $B$ have the same number of elements;
2. $A$ and $B$ are not equivalent under actions of dihedral group $D_n$ (that is, rotations and symmetries of the regular $n$-gon; or we can regard them as functions $f:\mathbb Z_n\rightarrow \mathbb Z_n$ defined by formulas $f(x) = a \pm x$);
3. The multisets of their pairwise differences coincide?

Answer 3

With Wouter M.'s new example for $n = 29$ $$ A = \{0, 3, 5, 9, 10 , 11\}, \quad B = \{0, 2, 4, 5, 10, 11\} $$ comes the proof that at least one doublet (in his terminology) always exists for any number $n > 11$. Indeed, the multisets of pairwise differences for $A$ and $B$ (taken as sets of integers, not residues modulo $n$) are the same -- that is easy to check.

It is left to prove that $A$ and $B$ are neither equivalent under actions of $D_n$, nor complementary to each other. The latter is proved by the fact that $A$ does not contain four consecutive elements while $B$ has neighbor elements 5 and 10. The former can be proved as follows. There are two neighbors in $B$ with difference 5 -- such neighbors in $A$ can exist only if $n=11+5=16$. At the same time, $A$ has one neighbor-difference of 4, and $B$ can have one such only if $n=11+4=15$.

Thus the pair $(A,B)$ provides us with a "universal" doublet for all $n>11$. This, of course, does not resolve a problem of counting the overall number of different abs.values for subset sums (man, we need a shorter name for that sequence!) but it answers one of the questions posed by the topic starter.

We can get back now to the more interesting question: why do these equal-length subsets happen? what kind of "symmetry" can be used to construct them? do there exist quadruplets, pentuplets, or $k$-tuplets with arbitrarily large $k$?

Answer 4

Proof that universal $x$-tuplets (terminology is defined in one of the above posts) exist for any natural number $x$:

For any natural $k$ we define sets $A_{k,0} = \{0, (3^k-1)/2, 3^k\}$ and $A_{k,1} = \{0, (3^k+1)/2, 3^k\}$. Incidentally, $A_{k,0}$ and $A_{k,1}$ are obtained one from the other by reflection about midpoint of $[0; 3^k]$.

Further, for any sets $S_1$, ..., $S_p$ their "sum" $\bigoplus_{i=1}^p S_i$ is defined as a multiset that consists of all possible sums $\sum_{i=1}^p s_i$, where for every index $i$ number $s_i$ is an element of $S_i$.

Now, let us fix some natural number $m$. For any sequence $D = \{d_i\}$ of $m$ zeros and ones we define multiset $\mathcal A_D= \bigoplus_{i=1}^p A_{i,d_i}$. Then the following properties of these multisets hold true:

• all multisets $\mathcal A_D$ are, in fact, regular sets of non-negative integers;
• any two such sets $\mathcal A_D$ and $\mathcal A_E$ are homometric (that is, they have the same multiset of pairwise differences);
• if different sequences $D$ and $E$ end with the same digit ($0$ or $1$), then the sets $\mathcal A_D$ and $\mathcal A_E$ are not congruent.

Using these properties we can build $2^{m-1}$ sets of integers (one for every binary sequence of length $m$ that ends with $0$), every two of which are homometric but not congruent. Granted, those sets are not the "minimal" ones in terms of size or "stretch" but finding the minimal examples seems to be a much, much harder task --- however that surely can be done for a few small values of $k$ (e.g., finding the smallest possible doublet or triplet).