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?

  • 1
    $\begingroup$ You should be able to do better using some version of the Azuma-Hoeffding inequality? Or Bernstein's inequality? $\endgroup$ – pseudocydonia Oct 10 '19 at 17:16
  • 2
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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$? $\endgroup$ – Kurisuto Asutora Oct 11 '19 at 7:52
  • 2
    $\begingroup$ 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. $\endgroup$ – Terry Tao Oct 11 '19 at 16:29
  • $\begingroup$ 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). $\endgroup$ – mathworker21 Oct 14 '19 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.