# Large deviations for trigonometric polynomials

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?

• You should be able to do better using some version of the Azuma-Hoeffding inequality? Or Bernstein's inequality? – pseudocydonia Oct 10 '19 at 17:16
• No, this is not applicable here, since the trigonometric polynomial is not a sum of independent random variables. There is an analogue of Bernstein's inequality, but only if the sequence $(n_k)_k$ grows very quickly, e.g. exponentially. See for example Kac, M.: On the distribution of values of sums of the type $\sum f(2^k t).$ Ann. of Math. (2) 47 (1946), 33–49. – Kurisuto Asutora Oct 11 '19 at 7:53

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.
• Thank you, this is very helpful. If I understand correctly, then in probabilistic terms the polynomial here is constructed as a sum of (essentially) independent objects, with the independence coming from the separation of frequencies. Do you have any intuition if a similar example could also be constructed without resorting to this sort of independence? More specifically, is the $L^2$ bound still sharp if we additionally could assume that the $n_1, \dots, n_N$ are of comparable size, such as $n_1, \dots, n_N \in [R,2R]$ for some $R$? – Kurisuto Asutora Oct 11 '19 at 7:52
• If one shifts all the $n_i$ in my example by a large factor $R$ then they will all lie in $[R,2R]$ but the distribution of the magnitude of the trignometric sum is unchanged. So if $R$ is allowed to be really large (E.g. exponentially large in $N$) this doesn't help at all. However one might be able to do something in the opposite regime when $R$ is comparable to $N$ and there is not enough "room" to have independent behaviour. – Terry Tao Oct 11 '19 at 16:29
• It should be noted that one also wants the $a_l$'s large so that the second factor is indeed typically of size $\sqrt{L}$ (obviously for $x$ close to $0$, the second factor is of size $L$ -- the point is the "close to" depends on the size of the $a_l$'s). – mathworker21 Oct 14 '19 at 15:16