5
$\begingroup$

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!

Improve this question
$\endgroup$
6
  • $\begingroup$ See: mathoverflow.net/questions/46068/… for a related discussion. $\endgroup$
    – Mark Lewko
    Commented Nov 22, 2018 at 0:16
  • $\begingroup$ 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). $\endgroup$
    – shurtados
    Commented Nov 22, 2018 at 0:28
  • $\begingroup$ 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? $\endgroup$
    – Seva
    Commented Nov 22, 2018 at 10:10
  • 3
    $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Commented Nov 22, 2018 at 11:57
  • $\begingroup$ @Seva: Yes, that's what I want. I modified the statement to make it hopefully more clear. $\endgroup$
    – shurtados
    Commented Nov 22, 2018 at 15:01

0

Reset to default

You must log in to answer this question.