2

Let $x_1,\ldots,x_n$ be $n$ complex numbers, and define $x_I:=\sum_{i\in I}x_i$ for any set $I\subseteq[n]$. Finally, declare the family $(x_1,\ldots,x_n)$ to be "sumset-distinct" if the $2^n$ numbers $(x_I)_{I\subseteq [n]}$ are pairwise distinct. My questions are:

  1. Has this notion been studied and if yes under what name?
  2. Is there a simple characterization of sumset-distinct families?
  3. Are there simple methods to determine whether a given family is sumset-distinct. For example, are the $n^{th}$ roots of unity $\left(e^{\frac{2ik\pi}{n}}\right)_{1\le k \le n}$ sumset-distinct?
DRJ
  • 170
  • If $n$ is composite then there will be more than one nonempty subset of the $n$th roots of unity with sum zero. – Gerry Myerson Mar 10 '23 at 01:52
  • As the OP talks about $2^n$ possible sums, the question includes the case that $I$ is empty. Hence the answer to 3. is no whenever $n>1$, because the sum of the $n$-th roots of unity vanishes. – Peter Mueller Mar 10 '23 at 10:53

2 Answers2

7

The set $\{x_i\}$ is called in the literature a sum-distinct set.

There is a big open problem in the area, due to Erdős and Moser: determining $f(n)=\min\{ \max(S): |S|=n, S\subseteq \mathbb{N}, S \text{ sum-distinct}\}$. The current lower bounds on $f$ are of the form $f(n)\ge C 2^n/\sqrt{n}$. A trivial upper bound is $f(n)\le 2^{n-1}$ by taking $x_i=2^{i-1}$.

There are some useful characterizations which were used in the literature to attack this problem. One characterization used by Dubroff--Fox--Xu is that if $\varepsilon_i$ are i.i.d random variables taking the values $\pm 1$ with equal probabilities then $\sum \varepsilon_i x_i$ takes each of its $2^n$ possible values with probability $2^{-n}$ iff $S$ is a sum-distinct set. A related (earlier) observation of Elkies is that if $x_i$ are integers valued then the Laurent polynomial $A(z)=\prod_i(1+(z^{x_i}+z^{-x_i})/2)$ has a very particular coefficient structure if $S$ is sum-distinct (and in particular the constant coefficient is $1$).

Ofir Gorodetsky
  • 13,395
  • 1
  • 60
  • 75
  • Any related results more general than my answer for roots of unity, i.e., arbitrary reals or complex numbers? – kodlu Mar 09 '23 at 23:09
  • 1
    Not that I am aware of, although Elkies' article does discuss sets of reals (in the context of the conjecture I mention). – Ofir Gorodetsky Mar 10 '23 at 09:48
4

If $n$ is prime the sums of $n^{th}$ roots of unity are distinct but more can be said (see here) using the following result:

Theorem 1 of Mann's paper "On linear relations between roots of unity" (Mathematika 12 (1965), 107-117) says the following. Let $\zeta_1,\dots,\zeta_r$ be roots of unity and let $a_1,\dots,a_r$ be nonzero integers. Suppose that $\sum_{i=1}^r a_i \zeta_i = 0$ but that there is no nonempty proper subset $S$ of $\{1,2,\dots,r\}$ for which $\sum_{i\in S} a_i \zeta_i = 0$. Then for each $i$ and $j$ we have $(\zeta_i/\zeta_j)^m=1$ where $m$ is the product of the primes which are $\le r$.

which itself depends on Lam and Yeung's "On vanishing sums of roots of unity" available at arXiv,

kodlu
  • 10,131
  • 2
  • 34
  • 53