Prove that $\sum_{k=0}^n{e^{ik^2}} = o(n^\alpha)$, $ \forall \alpha >0$

Solution 1:

I don't have a proof, but I have a heuristic argument and numerical results that go against your conjecture, which might be interesting to you.

Consider the following heuristic. For sufficiently large $n$, suppose the terms in the sum will distribute 'randomly' around the unit circle in the complex plane. In this approximation your summation is equivalent to a random walk in the complex plane with $n$ steps of length 1. Let \begin{equation} f(n) = \sum_{k=0}^n e^{ik^2}. \end{equation} Then, the above argument implies not only: \begin{equation} \operatorname{Re}(f(n)),\operatorname{Im}(f(n)) \in O(\sqrt{n}) \end{equation} but even the stronger condition \begin{equation} |f(n)|^2 \sim n + g(n) \end{equation} with \begin{align} \operatorname{Re}(g(n)),\operatorname{Im}(g(n)) \in o(\sqrt{n}). \end{align} The correction $g(n)$ comes from the fact that the 'random walk' starts in the positive $\Re$ direction and then heads counter-clockwise in the complex plane, which biases $f(n)$ on the order of the persistence length of the random walk.

So... I checked my idea numerically, and the results are very weird. Take a look:

The orders of magnitude are about right, which supports my heuristic argument. However, the function is not at all well behaved. The expected relative fluctuations in $|f(n)|^2$ if it's an $n$-step random walk are $1/\sqrt{n}$; the fluctuations we're seeing here are way larger than this. Also, there is obviously some periodicity to $|f(n)|^2$, with periods at least as long as $10^9$. I even suspect there's some self-similarity in $|f(n)|^2$: the entire curve in the second plot isn't so different from the individual little 'teeth', and the function has significant structure both on the scale of $n\sim 10^3$ and $n\sim 10^{10}$.

Personally I highly doubt this function is $o(n^\epsilon)$ $\forall \epsilon>0$, but otherwise I don't know what it is.

Here's the simple code I wrote to generate the above data, if anyone is interested in experimenting:

// To compile: gcc -std=c99 -O3 random_walk.c -o random_walk

#include <stdio.h>
#include <math.h>
#include <stdint.h>

#define NMAX 1e3
#define PRINT_INTERVAL 1

int main(){
  double sum_real=0.;
  double sum_imaginary=0.;
  for(uint_fast64_t k=0; k<=NMAX; k++){
    double kSquared = (double)k*k;
    sum_real += cos(kSquared);
    sum_imaginary += sin(kSquared);
    if(k%PRINT_INTERVAL==0)
      printf("%e\t%e\n", (double)k, sum_real*sum_real + sum_imaginary*sum_imaginary);
  }
}