Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 5 down vote accepted

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

share|cite|improve this answer
Nice =). Thank you so much for taking the time to write up this clear and detailed answer! Also, thanks for the references. – Sam Oct 13 '11 at 12:35
@Sam My pleasure :) – Nick Strehlke Oct 13 '11 at 16:12
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
@process91 Thank you for noticing that after all this time—I've now fixed the answer! – Nick Strehlke Jun 26 '14 at 6:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.