# Lower bound for some sums of roots of unity

Let $$n$$ be a positive integer (assume $$n$$ is prime for simplicity), and let $$x_k = \pm1$$, for $$k = 0,1,2,..., n-1$$. Let $$\rho$$ be an $$n-$$th primitive root of unity, I am interested in a lower bound for the absolute value of all possible sums of the form:

$$S_n = \sum_{k=0}^{n-1} x_k \rho^k$$ assuming that such sum is not equal to zero (when $$n$$ is prime this can only happen when all the $$x_k$$'s have the same sign).

One can obtain an easy lower bound of $$\frac{1}{n^{n-1}}$$ by multiplying the algebraic integer $$S_n$$ by all its Galois conjugates, but given that there are $$2^n$$ possible $$S_n$$ contained in a ball of radius $$n$$, I am expecting a better lower bound (hopefully $$e^{-Cn}$$ for some constant $$C$$).

I am also interested in the probability $$Pr(|S_n| < e^{-100n})$$, where $$100$$ is arbitrary. I am expecting this quantity to be exponentially small, I think from an argument in Tao-Vu's paper (https://arxiv.org/abs/1307.4357) related to Nguyen-Vu's optimal Offord-Littlewood inverse Theorem one might be able to show that such probability is smaller than $$n^{-C}$$ (for any fixed $$C$$ and $$n \to \infty$$), but I'm still far from understanding their method.

I would be grateful for any information related to sums of this form, similar sums or some understanding in how difficult this question can be.

Thanks!

• See: mathoverflow.net/questions/46068/… for a related discussion. – Mark Lewko Nov 22 '18 at 0:16
• Thank you, I saw that while writing the question, so it seems the question is very difficult, my hope is that because I'm taking all the roots of unity something different can be said, for example when $x_i$ are characters, the absolute value of the sum is $\sqrt(p)$ (If I'm correct). – shurtados Nov 22 '18 at 0:28
• What do you mean writing "given that there are $2^n$ sums, I am expecting a better lower bound"? Don't you need a uniform lower bound for all these sums? That is, do you want to show that none of the $2^n$ sums are small in absolute value? – Seva Nov 22 '18 at 10:10
• Write $S_n=A-B$, where $A$ collects all the $+1$ terms, $B$, all the $-1$ terms. Then $S+2B=A+B=0$, so $B=-(1/2)S$, so $S$ is tiny if and only if $B$ is tiny. So I don't think "taking all the roots of unity" makes the problem any easier than taking any old sum of $n$th roots of unity. – Gerry Myerson Nov 22 '18 at 11:57
• @Seva: Yes, that's what I want. I modified the statement to make it hopefully more clear. – shurtados Nov 22 '18 at 15:01