# 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.

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.

• You want to know when a (potentially open) polygon with unit edges, with directions given by the quadratic residues $\pmod n$ is closed? – Eric Towers Feb 2 '16 at 17:30
• i don't think i understand your question – Renart Feb 2 '16 at 17:31
• great question @Renart (+1) – user153330 Feb 2 '16 at 17:37
• What's wrong with this one? en.wikipedia.org/wiki/Stolz%E2%80%93Ces%C3%A0ro_theorem – user198044 Feb 2 '16 at 17:48
• i would guess that Euler Mac-Laurin could be working here – tired Feb 2 '16 at 17:54

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 $$\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).$$ Thus $$|S|^2 \leq 2\sum_{h=0}^{n-1} \min\left(\frac2{|1-e^{i2h}|},n\right).$$ 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 $$|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).$$ 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.

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.
• I wrote down question 4 thinking that the answer was going to be obviously the whole unit disk or obviously just $\{0,1\}$, or something like that, but actually I think the question is rather subtle! Let $L$ be the set. Then I can prove that $L$ is a closed, convex subset of the unit disk whose boundary touches the unit circle only at $1$ and is tangent to it there. – Sean Eberhard Feb 11 '16 at 15:36
• Actually not quite tangent. – Sean Eberhard Feb 12 '16 at 15:35
• For more than you ever wanted to know about question 4, follow the links at mathoverflow.net/questions/231606/…. However, I think this question is reasonable: 4'. Show that $\{z: g_n(\alpha)\to z~\text{for some}~\alpha\} = \{z: |z|\leq 1\}$. – Sean Eberhard Feb 20 '16 at 22:31
• Thanks for the answer ! i've read a little bit of the book "uniform distribution of sequences" by L. Kuipers and H. niederreiterbut but I still don't know how to answer your question 6... Could you give me a hint/short answer ? – Renart Mar 8 '16 at 13:14
• Sure. It's a nice question once you see it. Actually look for a power of 2 starting 7777777..., and to get this consider the sequence $\log_{10}(2^n)$ modulo $1$. – Sean Eberhard Mar 8 '16 at 17:33