Show that $ \lim\limits_{n\to\infty}\frac{1}{n}\sum\limits_{k=0}^{n-1}e^{ik^2}=0$

TL;DR : The question is how do I show that $\displaystyle \lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}e^{ik^2}=0$ ?

More generaly the question would be : given an increasing sequence of integers $(u_k)$ and an irrational number $\alpha$, how do I tell if $\displaystyle \lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}e^{2i\pi \alpha u_k}=0$ ? I'm not asking for a criterium for completely general sequences, an answer for sequences like $u_k=k^2$, $v_k=k!$ or $w_k=p(k)$ with $p\in \mathbf Z [X]$ would already be awesome.

A little explanation about this question :

In Real and Complex Analysis by Rudin there is the folowing exercise :

Let $f$ be a continuous, complex valued, $1$-periodic function and $\alpha$ an irrational number. Show that $\displaystyle \lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}f(\alpha k)=\int_0^1f(x)\mathrm d x$. (We say that $(\alpha k)_k$ is uniformly distributed in $\mathbf R / \mathbf Z$)

With the hint given by Rudin the proof is pretty straightforward : First one show that this is true for every $f_j=\exp(2i\pi j\cdot)$ with $j\in \mathbf{Z} $. Then using density of trigonometric polynomials in $(C^0_1(\mathbf{R}),\|\cdot\|_\infty)$ and the fact that the $0$-th Fourier coefficient of $f$ is it's integral over a period, one can conclude using a $3\varepsilon$ argument. This proof is possible because one can compute explicitly the sums $$\displaystyle \frac{1}{n}\sum_{k=0}^{n-1}e^{2i\pi j \alpha k}=\frac{1}{n}\cdot\frac{1-e^{2i\pi j\alpha n}}{1-e^{2i\pi j\alpha}}\longrightarrow 0 \text{ when }n\to\infty \text{ and }j\in \mathbf{Z}^*.$$

Now using a different approach (with dynamical systems and ergodic theorems) Tao show in his blog that $(\alpha k^2)_k $ is uniformly distributed in $\mathbf R / \mathbf Z$ (corollary 2 in this blog). I'd like to prove this result using the methods of the exercice of Rudin, but this reduce to show that $$\displaystyle \frac{1}{n}\sum_{k=0}^{n-1}e^{2i\pi j \alpha k^2}\longrightarrow 0 \text{ when }n\to\infty \text{ and }j\in \mathbf{Z}^*.$$ Hence my question.

P.S. When i ask wolfram alpha to compute $\sum_{k\geq0}e^{ik^2}$ it answer me with some particular value of the Jacobi-theta function. Of course the serie is not convergent but maybe it's some kind of resummation technique or analytic continuation. I'm not familiar with these things but it might be interesting to look in that direction.

Solution 1:

Gauss sums

Your sum is strongly related to the Gauss sum. The usual trick is to compute the modulus. This works particularly smoothly over $\mathbf{Z}/p\mathbf{Z}$ as with usual Gauss sums, but essentially it works here too: If $S = \sum_{k=0}^{n-1} e^{ik^2},$ then \begin{align} |S|^2 &= \sum_{k=0}^{n-1} \sum_{k'=0}^{n-1} e^{i(k'^2 - k^2)}\\ &= \sum_{h=-n+1}^{n-1} \sum_{\substack{0\leq k<n\\ 0\leq k+h<n}} e^{i(2kh+h^2)}, \end{align} where we have written $h=k'-k$. Now the inner sum is a geometric series with at most $n$ terms and with common ratio $e^{i2h}$, so we have \begin{equation} \left|\sum_{\substack{0\leq k<n\\ 0\leq k+h<n}} e^{i(2kh+h^2)}\right| \leq \min\left(\frac{2}{|1-e^{i2h}|},n\right). \end{equation} Thus \begin{equation} |S|^2 \leq 2\sum_{h=0}^{n-1} \min\left(\frac2{|1-e^{i2h}|},n\right). \end{equation} Now fix $\epsilon>0$. Since $(h/\pi)_{h=1}^\infty$ is equidistributed mod $1$ the number of $h=0,\dots,n-1$ for which $|1-e^{i2h}| \leq \epsilon$ is $O(\epsilon n)$, so \begin{equation} |S|^2 \leq 2\sum_{\substack{0\leq h < n\\ |1-e^{i2h}| \leq \epsilon}}n + 2\sum_{\substack{0\leq h < n\\ |1-e^{i2h}| > \epsilon}} \frac2{|1-e^{i2h}|} \leq O(\epsilon n^2) + O(\epsilon^{-1} n). \end{equation} Since $\epsilon$ was arbitrary this implies $|S|^2=o(n^2)$, and hence $|S|=o(n)$.

The van der Corput trick

The only thing we really used about $k^2$ here is that for fixed $h$ we understand the behaviour of the sequence $(k+h)^2 - k^2$, and indeed if you repeat the above calculation but with a judicious application of the Cauchy--Schwarz inequality then you prove a general fact called van der Corput's difference theorem (aka Weyl's differencing trick): if $(u_k)$ is a sequence such that for each $h\geq 1$ the sequence $(u_{k+h}-u_k)$ is equidistributed modulo $1$, then $(u_k)$ is equidistributed modulo $1$. See for example Corollary 2 on Tao's blog here. This implies for example that $\sum_{k=0}^{n-1} e^{i2\pi p(k)} = o(n)$ for every nonconstant polynomial $p$ with irrational leading coefficient.

Other sequences

In general there is no hard and fast rule about $\lim \frac1n \sum_{k=0}^{n-1} e^{i2\pi \alpha u_k}$, i.e., about equidistribution of $(u_k)$, and in fact the other sequence you mention, $k!$, is indeed very different. To take a slightly simpler example which is qualitatively similar, consider $u_k = 2^k$. Let $f_n(\alpha)$ be the exponential sum $\frac1n \sum_{k=1}^n e^{i2\pi \alpha 2^k}$. Then it is a well known consequence of the ergodic theorem that $f_n(\alpha)$ converges to $0$ for almost every $\alpha$. On the other hand clearly $f_n(\alpha)\to 1$ for every dyadic rational $\alpha$, as $\alpha 2^k$ is eventually constantly $0$ mod $1$. But then by Baire category theorem we must have for a comeagre set of $\alpha$ that $f_n(\alpha)$ does not converge to $0$. Thus it's difficult to say anything too general about $f_n(\alpha)$, especially for particular $\alpha$. For instance, proving $\lim_{n\to\infty} f_n(\sqrt{2})=0$ is a famous open problem.

Test your understanding

Here are some related problems to think about, not all of which I know off-hand how to answer!

1. Is $(\sqrt{n})$ equidistributed mod $1$?
2. What about $(\log n)$?
3. Show that there are some $\alpha$ for which $f_n(\alpha)$ does not converge.
4. Determine $\{z: f_n(\alpha)\to z~\text{for some}~\alpha\}$.
5. Let $g_n(\alpha) = \frac1n \sum_{k=1}^n e^{i2\pi \alpha k!}$. Prove statements for $g_n$ analogous to those we proved for $f_n$.
6. Is there a power of $2$ with at least $7$ decimal digits equal to $7$?
7. Think of other silly (but not open) problems like these ones.