Large deviations for trigonometric polynomials

Question

Let $n_1 < \dots < n_N$ be positive integers. Assume we don't know anything about their actual values. What is the best general upper bound we can give for $$ \mu \left( x \in [0,1] : ~\left|\sum_{k=1}^N e^{2 \pi i n_k x} \right| > \kappa \sqrt{N} \right)? $$ Here $\mu$ is Lebesgue measure on $[0,1]$, and $\kappa$ is a parameter (imagine $\kappa$ to be somewhere around $\sqrt{\log N}$).

Of course we can use $\|\sum_{k=1}^N e^{2 \pi i n_k x}\|_2 = \sqrt{N}$ plus Chebyshev's inequality, to get $\mu \leq \kappa^{-2}$. But is there anything smarter we can do? Taking other norms than $L^2$-norm does not work, since in general these norms can get very large and the result will be worse than using $L^2$ norm. For example when $n_1 , \dots, n_N = 1, \dots, N$, we have an $L^4$ norm as large as $N^{3/4}$ - however, the actual size of the exceptional set is very small, so arguing with $L^4$ norms would be stupid in that situation. So is there any general estimate which beats the $L^2$ estimate?

Answer 1

Your example $n_i=i$ shows that the $L^2$ bound is sharp when $\kappa \sim \sqrt{N}$ (though of course for $\kappa > \sqrt{N}$ the LHS vanishes). For smaller values of $\kappa$ one can simply combine this construction with a generic trigonometric series. In particular, if we have $N = M L$ for some integers $M,L$ with $M$ comparable to a large multiple of $\kappa^2$, we can consider the trigonometric polynomial $$ (\sum_{m=1}^M e^{2\pi i m x}) (\sum_{l=1}^L e^{2\pi i a_l x})$$ where the $a_l$ are some very widely separated frequencies in general position (e.g. $a_l = A^l$ for some large $A$). This is a polynomial of the required form $\sum_{k=1}^N e^{2\pi i n_k x}$ if the $a_l$ are sufficiently widely separated. Informally, the first factor $\sum_{m=1}^M e^{2\pi i m x}$ is of size $\sim M$ when $x = O(1/M)$, and the second factor is typically of size $\sqrt{L}$, so one expects the product to be of size $\sim M \sqrt{L} \geq \kappa \sqrt{N}$ on a set of size $\sim 1/M \sim \kappa^{-2}$, thus demonstrating the sharpness of the $L^2$ bound. One can make these calculations more rigorous by computing the moments $$ \int_0^1 |\sum_{m=1}^M e^{2\pi i m x}|^{2+2j} |\sum_{l=1}^L e^{2\pi i a_l x}|^{2j}\ dx$$ for $j=1,2$, and using the Paley-Zygmund inequality (with respect to the probability measure coming from normalising $|\sum_{m=1}^M e^{2\pi i m x}|^2\ dx$); I'll leave this as an exercise to the interested reader.