Van der Corput inequality explained

is strongly correlated with many unit vectors

u₁,...,u_n\inV

, then many of the pairs

u_i,u_j

must be strongly correlated with each other. Here, the notion of correlation is made precise by the inner product of the space

: when the absolute value of

\langleu,v\rangle

is close to

, then

and

are considered to be strongly correlated. (More generally, if the vectors involved are not unit vectors, then strong correlation means that

|\langleu,v\rangle| ≈ \|u\|\|v\|

Statement of the inequality

Let

be a real or complex inner product space with inner product

\langle ⋅ , ⋅ \rangle

and induced norm

\| ⋅ \|

. Suppose that

v,u_1,...,u_n\inV

and that

\|v\|=1

. Then

\displaystyle\left(

	n
\sum
	i=1

|\langlev,u_i\rangle|\right)²\leq

	n
\sum
	i,j=1

|\langleu_i,u_j\rangle|.

In terms of the correlation heuristic mentioned above, if

is strongly correlated with many unit vectors

u_1,...,u_n\inV

, then the left-hand side of the inequality will be large, which then forces a significant proportion of the vectors

u_i

to be strongly correlated with one another.

Proof of the inequality

We start by noticing that for any

i\in1,...,n

there exists

\epsilon_i

(real or complex) such that

|\epsilon_i|=1

and

|\langlev,u_i\rangle|=\epsilon_i\langlev,u_i\rangle

. Then,

	n
\left(\sum
	i=1

\left|\langlev,u_i\rangle\right|\right)²

=\left(

	n
\sum
	i=1

\epsilon_i\langlev,u_i\rangle\right)²

=\left(\left\langlev,

	n
\sum
	i=1

\epsilon_iu_i\right\rangle\right)²

since the inner product is bilinear

\leq\|v\|²\left\|

	n
\sum
	i=1

\epsilon_iu_i\right\|²

by the Cauchy–Schwarz inequality

=\|v\|²\left\langle

	n
\sum
	i=1

\epsilon_iu_i,

	n
\sum
	j=1

\epsilon_iu_j\right\rangle

by the definition of the induced norm

	n
\sum
	i,j=1

\epsilon_i\epsilon_j\langleu_i,u_j\rangle

since

is a unit vector and the inner product is bilinear

\leq

	n
\sum
	i,j=1

|\langleu_i,u_j\rangle|

since

|\epsilon_i|=1

for all

External links

A blog post by Terence Tao on correlation transitivity, including the van der Corput inequality https://terrytao.wordpress.com/2014/06/05/when-is-correlation-transitive/