Proving an estimate of Weyl

Question

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!

Answer 1

Here's a route to the solution. I tried to be detailed with the sums, so the computations get a little messy. By the way, this inequality is a form of van der Corput's Inequality. You can see more at Terry Tao's blog, but the version he talks about is a little less obviously related.

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*}$$