Prove that $\sum_{k=0}^n{e^{ik^2}} = o(n^\alpha)$, $ \forall \alpha >0$ I want to prove that : 
$\sum_{k=0}^n{e^{ik^2}} = o(n^\alpha)$, $ \forall \alpha >0$ when $n$ tends to $+\infty$
Perhaps $\sum_{k=0}^n{e^{ik^2}}$ is bounded, I don't know.
Do you have ideas ?
 A: 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);
  }
}

