Bounds on sums of roots of unity with few exceptions and prime orders
Small sums of roots of unity: polylogarithmic exceptional sets and conditional separation
Computational Complexity
Summary
Sometimes, when you add up special points called roots of unity — numbers arranged in a circle — the sum can become very small, which has puzzled mathematicians. The paper finds that only very few points on a large grid can produce sums that are extremely close to zero, and this is done without relying on unproven assumptions. Additionally, assuming a famous conjecture, the authors show that sums of certain prime-based roots of unity do not get too small as the primes grow. These findings help better understand the behavior and limits of these special sums.
What this means in practice
- •For cryptographers: Use bounds on sums of prime-order roots of unity to assess security assumptions in cryptographic schemes based on algebraic number theory.
- •For signal processing engineers: Improve error analysis for algorithms that use sums of complex roots of unity in signal reconstruction and Fourier transforms.
A theory result. No direct application yet.
Authors
Qi Cheng
Abstract
We prove a polylogarithmic exceptional-set estimate for symmetric five-term sums of roots of unity of arbitrary order. More precisely, at most $O((\log(2N))^{11})$ points of the $N$-grid satisfy $|1+2\cos(2πx)+2\cos(2πy)|<\exp(-C(\log(2N))^{13})$. This implies the corresponding bound for small conjugates at the reduced conductor: outside polylogarithmically many real embeddings, every such sum is at least quasipolynomially large. The proof is unconditional and combines a polynomial-vector-field multiplicity estimate, arithmetic jet determinants, analytic propagation, and interpolation determinants for nearby grid points. As a companion result, assuming a uniform number-field $abc$ conjecture, we prove that every sum of a fixed number of distinct prime-order roots of unity has modulus at least $\exp(-\varepsilon p)$ for every $\varepsilon>0$ and all sufficiently large primes $p$, uniformly in the exponents. That proof uses simultaneous compression of the exponents, discriminant estimates, and cyclic resultants.