# Proving an estimate of Weyl

I'm working through some problems of Fourier Analysis by Stein, Shakarchi and I got stuck trying to solve the following problem:

Let $S_N = \sum_{n=1}^N e^{2\pi i f(n)}$. Show that for $H\le N$, one has

$$|S_N|^2 \le c \frac NH \sum_{h=0}^H\, \left|\,\sum_{n=1}^{N-h} e^{2\pi i(f(n+h)- f(n))} \right|$$ for some constant $c>0$ independent of $N$, $H$, and $f$.

There is even a hint: Let $a_n = e^{2\pi if(n)}$ if $1\le n\le N$ and $0$ otherwise. Then write $H\;\sum_n a_n = \sum_{h=1}^H \sum_n a_{n+h}$ and apply the Cauchy-Schwarz inequality.

Well, I'm realy horrible at this stuff, but I'll write down at least a beginning

\begin{align} |S_N|^2 &= \frac 1{H^2} \left| \sum_{h=1}^H \sum_n a_n \right|^2 \\ &\leq \frac1H \sum_{h=1}^H \left|\sum_n a_{n+h} \right|^2 \\ &= \frac1H \sum_{h=1}^H \sum_{n,m} a_{n+h}\overline{a_{m+h}} \end{align}

and after this I already get lost. =( (Of course, I have scribbed down much more than just this, but it all lead nowhere, so I won't expose you to that...)

I would really appreciate some help. Cheers!

-
I just have to say that your LaTeX looks like perl. Short, concise, impossible to decipher. (You were missing a | somewhere there. Also the *-environments don't exist here. – Asaf Karagila Oct 12 '11 at 23:20
@AsafKaragila: I apologize if my edit overrode yours. – JavaMan Oct 12 '11 at 23:21
@Asaf: Sorry, normally others don't need (want?) to read my code, so I might have developed some bad habits there ^^. Thanks for correcting! – Sam Oct 12 '11 at 23:21

As for the computation, you have $$HS_N=H\sum_na_n=\sum_{k=1}^H\sum_na_{n+k}=\sum_n\sum_{k=1}^Ha_{n+k}.$$ The inner sum vanishes except for $n$ in the range $1-H\leq n\leq N-1$. It follows by the Cauchy-Schwarz inequality that \begin{align*} H^2|S_N|^2 &= \left|\sum_n\sum_{k=1}^Ha_{n+k}\right|^2\leq (N+H-1)\sum_n\left|\sum_{k=1}^Ha_{n+k}\right|^2\\ &= (N+H-1)\sum_n\sum_{k=1}^H\sum_{j=1}^Ha_{n+k}\overline{a}_{n+j}\\ &= (N+H-1)\sum_{k=1}^H\sum_{j=1}^H\sum_na_{n+k}\overline{a}_{n+j}. \end{align*} To evaluate the sum, group the terms $a_{n+k}\overline{a}_{n+j}$ by the value of the difference $k-j$ (I've included a detailed computation below in case it's not clear what I mean). In the end, you'll find that \begin{align*} \sum_{k=1}^H\sum_{j=1}^H\sum_na_{n+k}\overline{a}_{n+j} &= H\sum_n|a_n|^2+ 2\text{Re}\,\left(\sum_{h=1}^{H-1}(H-h)\sum_na_{n+h}\overline{a}_{n}\right)\\ &\leq 2\sum_{h=0}^{H-1}(H-h)\left|\sum_na_{n+h}\overline{a}_{n}\right|. \end{align*} Combining everything from here (I've adjusted this to reflect @process91's comment), you get \begin{align*} |S_N|^2& \leq 2\left(\frac{N+H-1}{H}\right)\sum_{h=0}^{H-1}\left(1-\frac{h}{H}\right)\left|\sum_na_{n+h}\overline{a}_{n}\right|\\ &\leq 4\frac{N}{H}\sum_{h=0}^{H}\left|\sum_na_{n+h}\overline{a}_{n}\right|. \end{align*} Now just delimit the above sum and insert $e^{2\pi i(f(n+h)-f(n))}$ for $a_{n+h}\overline{a}_n$ to get the inequality the book wants.
Here's a detailed computation of the sum I referenced above. Write \begin{align*} \sum_{k=1}^H\sum_{j=1}^H\sum_na_{n+k}\overline{a}_{n+j} &= \sum_{1\leq j\leq k\leq H}\sum_na_{n+k}\overline{a}_{n+j}\\ &\qquad + \sum_{1\leq k<j\leq H}\sum_na_{n+k}\overline{a}_{n+j}, \end{align*} and observe that \begin{align*} \sum_{1\leq j\leq k\leq H}\sum_na_{n+k}\overline{a}_{n+j} &= \sum_{1\leq j\leq k\leq H}\sum_na_{n+k-j}\overline{a}_{n}\\ &= \sum_{0\leq k-j\leq H-j\leq H-1}\sum_na_{n+k-j}\overline{a}_n\\ &= \sum_{0\leq h\leq H-j\leq H-1}\sum_na_{n+h}\overline{a}_n\\ &= \sum_{h=0}^{H-1}\sum_{j=1}^{H-h}\sum_na_{n+h}\overline{a}_n\\ &= \sum_{h=0}^{H-1}(H-h)\sum_na_{n+h}\overline{a}_n. \end{align*} Similarly, \begin{align*} \sum_{1\leq k<j\leq H}\sum_na_{n+k}\overline{a}_{n+j} &= \sum_{h=1}^{H-1}(H-h)\sum_na_n\overline{a}_{n+h}. \end{align*} So it follows that \begin{align*} \sum_{k=1}^H\sum_{j=1}^H\sum_na_{n+k}\overline{a}_{n+j} &= H\sum_n|a_n|^2+ 2\text{Re}\,\left(\sum_{h=1}^{H-1}(H-h)\sum_na_{n+h}\overline{a}_{n}\right). \end{align*}
Great answer, two comments - I think there is a small mistake on the second line after "Combining everything from here", the 2 should become a 4 otherwise I believe it is false. The other point is that getting the answer for $H-1$ is not quite enough to conclude it for $H$, instead we can use the following: \begin{align*} |S_N|^2& \leq 2\left(\frac{N+H-1}{H}\right) \sum_{h=0}^{H-1}\left(1-\frac{h}{H}\right)\left|\sum_n a_{n+h}\overline{a}_{n}\right|\\ &\leq 4\frac{N}{H}\sum_{h=0}^{H}\left|\sum_na_{n+h}\overline{a}_{n}\right|. \end{align*} – process91 Jun 25 '14 at 19:10