Skip to main content
4 of 4
deleted 11 characters in body
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

To expand on the Prouhet-Tarry-Escott problem, this is to find (multi)-sets of integers $A$ and $B$ with $\sum_Aa^k=\sum_Bb^k$ for $0 \le k \le m-1$. Then $|A|=|B|$ and perhaps one can always get $|A|=m$ although no-one really knows. This translates into ways to choose $n=2|A|$ Nth roots of unity (at least for even N): take the set $S$ consisting of the $n$ roots $\alpha^a$ and $-\alpha^b$ where $\alpha=e^\frac{2\pi i}{N}$. Note that -1 is a power of $\alpha$. I'm not sure what to do when $n$ and/or $N$ is odd but other people probably do. Fast forwarding over some details, one ends up with a polynomial of the form $(\alpha-1)^kg(\alpha)$ and that first factor gives the whole thing a size $O(\cos(\frac{2\pi}{N})^k)=O(N^{-k})$ The constant is easily computable although kind of large and requiring a fairly large $N$ to be accurate (for n=10 I got multi-digit accuracy by N=1000 although maybe N=100 was ok too). A reference I like is P. Borwein, C. Ingalls, The Prouhet-Tarry-Escott Problem revisited.

The referenced article by G. Myerson says (if my quick read is correct) that an approximately equal spacing around the unit circle can be $O(N^{-1})$ but not better but that no one knows a general construction which is better. It is intriguing that the solution sketched above has no special use of the number theoretic properties of $N$ except parity. Perhaps (some of) the best solutions (for an even number of roots) involve roots from 2 thin wedges which are nearly antipodal. For 4 roots the optimum is to take 1 twice and two other roots one on each side of -1.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104