Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer

up vote 3 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 a little 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+h}\right)\\ &\leq 2\sum_{h=0}^{H-1}(H-h)\left|\sum_na_{n+h}\overline{a}_{n+h}\right|. \end{align*} $$ Combining everything from here, 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 2\frac{N}{H-1}\sum_{h=0}^{H-1}\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. (The way the hint is set up, you get the inequality for $H-1$, but this is obviously inconsequential.)

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+h}\right). \end{align*}$$

share|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
add comment

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.