The proof of van der Corput inequality

Question

$\newcommand{\lrp}[1]{\left(#1\right)}$ $\newcommand{\lrmod}[1]{\left|#1\right|}$

I am trying to understand the proof of the van der Corput inequality given in Lemma 1 of this blog entry due to Tao. We will use the Big-O notation, whose definition can be found here.

Lemma. (Van der Corput Inequality). Let $a_1 a_2, a_3 , \ldots$ be a sequence of complex numbers bounded by magnitude $1$. Then for any $1\leq H\leq N$ we have $$ \lrmod{ \frac{1}{N} \sum_{n=1}^N a_n } \leq \lrp{ \frac{1}{H}\sum_{h=0}^{H-1} \lrmod{ \frac{1}{N} \sum_{n=1}^N a_{n+h}\bar a_n} }^{1/2} + O\lrp{ \frac{H}{N}} $$

The proof Tao has provided proceeds as follows. It is easy to see that $$ \lrmod{ \frac{1}{N} \sum_{n=1}^N a_n - \frac{1}{N} \sum_{n=1}^N a_{n+h} } = O\lrp{\frac{H}{N}} $$ Therefore $$ \frac{1}{H}\sum_{h=0}^{H-1}\lrmod{ \frac{1}{N} \sum_{n=1}^N a_n - \frac{1}{N} \sum_{n=1}^N a_{n+h} } = O\lrp{\frac{H}{N}} $$ and hence by triangle inequality we have that $$ \lrmod{\frac{1}{N} \sum_{n=1}^N a_n - \frac{1}{N}\sum_{n=1}^N \frac{1}{H}\sum_{h=0}^{H-1} a_{n+h}} = O\lrp{\frac{H}{N}} $$ Write $$ x= \frac{1}{N} \sum_{n=1}^N a_n \text{ and } y_n= \frac{1}{H} \sum_{h=0}^{H-1} a_{n+h} $$ So the last equation becomes $$ \lrmod{x- \frac{1}{N}\sum_{n=1}^N y_n} = O\lrp{ \frac{H}{N}} $$ Again by triangle inequality we have that $$ |x| \leq \lrmod{ \frac{1}{N} \sum_{n=1}^N y_n} + O\lrp{ \frac{H}{N}} \leq \frac{1}{N} \sum_{n=1}^N |y_n| + O\lrp{ \frac{H}{N}} $$ By Jensen's inequality we have $$ \lrp{\frac{1}{N} \sum_{n=1}^N |y_n|}^2 \leq \frac{1}{N}\sum_{n=1}^N |y_n|^2 $$ Thus we get $$ |x| \leq \lrp{ \frac{1}{N}\sum_{n=1}^N |y_n|^2}^{1/2} + O\lrp{ \frac{H}{N}} $$ which is nothing but $$ \lrmod{ \frac{1}{N}\sum_{n=1}^N a_n} \leq \lrp{ \frac{1}{N} \sum_{n=1}^N \lrmod{\frac{1}{H} \sum_{h=0}^{H-1} a_{n+h}}^2}^{1/2} + O\lrp{ \frac{H}{N}} $$ At this point Tao writes that ``Expanding out the square and rearranging a bit, we soon obtain the desired upper bound." I am unable to follow this step. Can somebody please give some details here. Also, if you can comment on what this inequality is trying to capture then please feel free to share.

Answer 1

You are mistaking the inequality. Tao is saying that there is a constant $C > 0$ with $|\frac{1}{N}\sum_{n \le N} a_n| \le C(\frac{1}{H}\sum_{h \le H} |\frac{1}{N}\sum_{n \le N} a_{n+h}\overline{a_n}|)^{1/2} + C\frac{H}{N}$.

Actually, I think there should be a $C\frac{1}{H^{1/2}}$ on the right hand side as well (see the link I gave).

Based on where you got to, and using $\sqrt{x+y} \le \sqrt{x}+\sqrt{y}$, it suffices to show $$\frac{1}{N}\sum_{n \le N} |\frac{1}{H}\sum_{h \le H} a_{n+h}|^2 \le \frac{2}{H}\sum_{h \le H} |\frac{1}{N}\sum_{n \le N} a_{n+h}\overline{a_n}|+O(\frac{1}{H})+O(\frac{H}{N}).$$

Merely by expanding the square, the left hand side is $$\frac{1}{H^2}\sum_{h_1,h_2 \le H} \frac{1}{N}\sum_{n \le N} a_{n+h_1}\overline{a_{n+h_2}}.$$ The term $h_1 = h_2$ has contribution $$\frac{1}{H^2}\sum_{h \le H} \frac{1}{N}\sum_{n \le N} |a_{n+h}|^2 = O(\frac{1}{H}),$$ so we can ignore it. We are left with

\begin{align*} \frac{2}{H^2}\sum_{1 \le h_1 < h_2 \le H} \frac{1}{N}\sum_{n \le N} a_{n+h_1}\overline{a_{n+h_2}} &= \frac{2}{H^2}\sum_{1 \le h_1 < h_2 \le H} \frac{1}{N}\sum_{n=h_1+1}^{N+h_1} a_n\overline{a_{n+h_2-h_1}} \\ &= \frac{2}{H^2}\sum_{1 \le h_1 < h_2 \le H} \left[\frac{1}{N}\sum_{n=1}^N a_n\overline{a_{n+h_2-h_1}} + O(\frac{H}{N})\right]. \end{align*}

The $O(\frac{H}{N})$ term merely comes out of the triple sum (since everything is averaged), so we can ignore it. We are left with $$\frac{2}{H^2} \sum_{1 \le h_1 < h_2 \le H} \frac{1}{N}\sum_{n=1}^N a_n\overline{a_{n+h_2-h_1}} = \frac{2}{H^2}\sum_{h \le H}\sum_{\substack{1 \le h_1 < h_2 \le H \\ h_2-h_2 = h}} \frac{1}{N}\sum_{n=1}^N a_n\overline{a_{n+h}}.$$

Now, we can pull out the sum in $n$ and note that the number of $1 \le h_1 < h_2 \le H$ with $h_2-h_1 = h$ is $H-h$ to get $$\frac{2}{H^2}\sum_{h \le H} (H-h)\frac{1}{N}\sum_{n=1}^N a_n\overline{a_{n+h}},$$ which is upper bounded by $$\frac{2}{H^2}\sum_{h \le H} (H-h)\left|\frac{1}{N}\sum_{n=1}^N a_n\overline{a_{n+h}}\right|,$$ which is of course upper bounded by $$\frac{2}{H}\sum_{h \le H} \left|\frac{1}{N}\sum_{n=1}^N a_n\overline{a_{n+h}}\right|,$$ as desired.

---

In regards to what this inequality is trying to capture. First, note that it holds in any Hilbert space, i.e. $||\frac{1}{N}\sum_{n \le N} v_n|| \le C(\frac{1}{H}\sum_{h \le H} ||\frac{1}{N}\sum_{n \le N} \langle v_{n+h},v_n \rangle||)^{1/2}+C\frac{1}{H^{1/2}}+C\frac{H}{N}$ (just go through the proof). Now suppose the $v_n$'s are mutually orthogonal. Then the left hand side is $\frac{1}{\sqrt{N}}$, while the right hand side is $O(\frac{1}{H^{1/2}})+O(\frac{H}{N})$ (which actually shows the need for the $O(\frac{1}{H^{1/2}})$ term), where the $O(\frac{1}{H^{1/2}})$ term came from $\frac{1}{N}\sum_{n \le N} \langle v_n,v_n \rangle$, the "diagonal term" in the proof above. The point is that the Van der Corput inequality allows one to get good bounds on $||\frac{1}{N}\sum_{n \le N} v_n||$ when the $v_n$'s are "almost orthogonal" (the preceding sentence shows it specializes to actual orthogonality).

Answer 2

Here is a slightly different proof. Let $a_1,\ldots, a_N$ be complex numbers (not necessarily of modulus $1$). Define $a_n=0$ for $n\leq0$ or $n>N$. For any $1\leq H\leq N$ we have that

$$H\sum^N_{n=1}a_n=\sum^{N+H-1}_{p=1}\sum^{H-1}_{h=0}a_{p-h}$$

By Cauchy-Schwartz \begin{align} H\Big|\sum^N_{n=1}a_n\Big| &\leq (N+H-1)^{1/2}\left(\sum^{N+H-1}_{p=1}\left|\sum^{H-1}_{h=0}a_{p-h}\right|^2\right)^{1/2}=(N+h-1)^{1/2}\left(\sum^{N+H-1}_{p=1}\left(\sum^{H-1}_{h=0}a_{p-h}\right)\left(\sum^{H-1}_{h=0}\overline{a_{p-h}}\right)\right)^{1/2}\\ &=(N+H-1)^{1/2}\left(\sum^{N+H-1}_{p=1}\left(\sum^{H-1}_{h=0}|a_{p-h}|^2+2\sum_{1\leq s<r\leq H-1}{\frak R}\big(a_{p-r}\overline{a_{p-s}}\big)\right)\right)^{1/2}\\ &=(N+H-1)^{1/2}\left(\sum^{N+H-1}_{p=1}\left(\sum^{H-1}_{h=0}|a_{p-h}|^2\right) + 2\sum^{N+H-1}_{p=1}\sum_{1\leq s<r\leq H-1}{\frak R}\big(a_{p-r}\overline{a_{p-s}}\big)\right)^{1/2} \end{align} The nonzero terms in the sum $$S:=\sum^{N+H-1}_{p=1}\sum_{1\leq s<r\leq H-1}{\frak R}\big(a_{p-r}\overline{a_{p-s}}\big)$$ are of the form $a_n\overline{a_{n+h}}$ where $1\leq n\leq N-1$ and $1\leq h\leq H-1$. For fixed $n=p-r$ and $h=r-s$ in $\{1,\ldots N-1\}$ and $\{1,\ldots, H-1\}$ respectively, the pairs $(s, r)$ with $0\leq s<r\leq H-1$ that yield $a_n\overline{a_{n+h}}$ are $(0,h),(1,h+1),\ldots (H-1-h,h+H-1-h)$ and for each such pair, there is a unique $1\leq p\leq N+H-1$ such that $n=p-r$. Hence, the term $a_n\overline{a_{n+h}}$ appears $H-h$ times in $S$. Consequently Hence \begin{align} \Big|\sum^N_{n=1}a_n\Big|\leq (N+H-1)^{1/2}\left(H\sum^N_{n=1}|a_n|^2+ 2\sum^{H-1}_{h=1}(H-h)\sum^{N-h}_{n=1}{\frak R}\big(a_n\overline{a_{n+h}}\big)\right)^{1/2}\tag{1}\label{one} \end{align}. Inequality \eqref{one} is van der Corput's inequality. It can also be rewritten as \begin{align} \Big|\frac1N\sum^N_{n=1}a_n\Big|^2\leq \frac{N+H-1}{NH}\left(\frac1N\sum^N_{n=1}|a_n|^2\,+\,2\sum^{H-1}_{h=1}\frac{H-h}{H}\frac{N-h}{N}\frac1{N-h}\sum^{N-h}_{n=1}{\frak R}(a_n\overline{a_{n+h}})\right) \end{align}