The Gaussian Correlation Conjecture

Unsolved problems

Update: This conjecture has now been solved! See A simple proof of the Gaussian correlation conjecture extended to multivariate gamma distributions by T. Royen, and Royen’s proof of the Gaussian correlation inequality by Rafał Latała, and Dariusz Matlak.

The Gaussian correlation conjecture is a simple looking inequality which, nevertheless, remains unproven. The standard n-dimensional Gaussian measure is

\displaystyle \mu_n(A) = (2\pi)^{-n/2}\int_A\exp(-\frac{1}{2}x^2)\,dx

for measurable subsets {A} of n-dimensional space {\mathbb{R}^n}. The conjecture states that

\displaystyle \mu_n(A\cap B)\ge \mu_n(A)\mu_n(B) (1)

for all convex and symmetric sets {A,B}. This inequality can be shown to be equivalent to the following statement. If {\{X_i\}_{i=1}^n} are jointly Gaussian random variables with mean zero, and {1\le k\le n}, then

\displaystyle {\mathbb P}\left(\max_{i\le n}|X_i|\le 1\right)\ge {\mathbb P}\left(\max_{i\le k}|X_i|\le 1\right){\mathbb P}\left(\max_{k<i\le n}|X_i|\le 1\right). (2)

A less general version of this inequality was initially stated in 1955 in a paper by Dunnet and Sobel, and the full version as stated above was conjectured in 1972 by Das Gupta et al.

Various special cases of the conjecture are known to be true. In 1967, Khatri and Šidák independently proved (2) for {k=1} or, equivalently, (1) in the case where {A} is a symmetric slab (the region between two parallel hyperplanes). The two dimensional case was proven in 1977 by Pitt, and the case where {A} is an arbitrary centered ellipsoid was proven in 1999 by Hargé.

In this entry we shall discuss the following interesting partial results due to Schechtman, Schlumprecht and Zinn in 1998.

  1. There is a positive constant {c} such that the conjecture is true whenever the two sets are contained in the Euclidean ball of radius {c\sqrt{n}}.
  2. If, for every {n}, the conjecture is true whenever the sets are contained in the ball of radius {\sqrt{n}}, then it is true in general.

At first sight it would seem that this comes close to proving the conjecture. Unfortunately, the constant in the first statement is {c=1/(2\sqrt{e})}, which is strictly less than one, so the second statement cannot be applied. Furthermore, it does not appear that the proof can be improved to increase {c} to one. Alternatively, we could try improving the second statement to only require the sets to be contained in the ball of radius {c\sqrt{n}} for some {c<1} but, again, it does not seem that the proof can be extended in this way.

For full details, see the paper by Schechtman, Schlumprecht and Zinn, which is freely available online. As the methods used are interesting in themselves, we briefly run through them now, and look at alternative approaches in a later post. The proof of 1 relies on applying a rotation, or change of variables, in the calculation of the measure of {A\times B}, and a result on log-concave functions is used to turn it into an inequality. The key idea employed in the proof of 2 is a tensor power trick along the same lines as those described by Terence Tao in his blog. This will give the following result.

Lemma 1 Let {a,c_n} be positive constants with {c_n^{1/n}\rightarrow 1} as {n} goes to infinity. Suppose that, for each {n}, the inequality

\displaystyle \mu_n(A\cap B)\ge c_n\mu_n(A)\mu_n(B) (3)

holds for all symmetric convex sets {A,B} in the Euclidean ball of radius {a\sqrt{n}}. Then, {\mu_n(A\cap B)\ge\mu_n(A)\mu_n(B)} for all such {A,B}.

To prove this, apply inequality (3) to the powers {A^m,B^m}, which will be in the Euclidean ball of radius {a\sqrt{mn}} in {{\mathbb R}^{mn}}.

\displaystyle \setlength\arraycolsep{2pt} \begin{array}{rcl} \displaystyle\mu_n(A\cap B)^m&\displaystyle=&\displaystyle\mu_{mn}(A^m\cap B^m)\ge c_{mn}\mu_{mn}(A^m)\mu_{mn}(B^m)\\ &\displaystyle =&\displaystyle c_{mn}\mu_{n}(A)^m\mu_{n}(B)^m. \end{array}

Raising to the power of {1/m} and taking the limit {c_{mn}^{1/m}\rightarrow 1} as {m\rightarrow\infty} proves the lemma.

Let us start with statement 2 above. The proof begins by showing that the correlation inequality (1) holds when {B} is a Euclidean ball. In fact, by the invariance of the Gaussian measure under rotations, this can be reduced to the trivial case where both {A} and {B} are spherically symmetric, so that one is a subset of the other. Then, writing {B^n_2} for the unit n-dimensional Euclidean ball,

\displaystyle \setlength\arraycolsep{2pt} \begin{array}{rcl} \displaystyle\mu_n(A\cap B)&\displaystyle\ge&\displaystyle \mu_n\left((A\cap \sqrt{n}B^n_2)\cap(B\cap \sqrt{n}B^n_2)\right)\\ &\displaystyle\ge&\displaystyle \mu_n\left(A\cap \sqrt{n}B^n_2\right)\mu_n\left(B\cap \sqrt{n}B^n_2\right)\\ &\displaystyle\ge&\displaystyle \mu_n(\sqrt{n}B^n_2)^2\mu_n(A)\mu_n(B). \end{array}

The second of these inequalities uses the hypothesis of statement 2, and the third uses the Gaussian correlation inequality in the case where one of the two sets is a Euclidean ball. The result will follow from Lemma 1 as long as we can prove that {\mu_n(\sqrt{n}B^n_2)^{1/n}} tends to 1 as {n} goes to infinity. In fact, it can be shown that {\mu_n(\sqrt{n}B^n_2)} converges to 1/2 (this is an easy application of the Central Limit Theorem), which completes the proof.

Moving on to statement 1, the trick is to consider rotating the product {A\times B} by 45 degrees, {u = (x-y)/\sqrt{2}}, {v=(x+y)/\sqrt{2}}. Then {x,y} are in {A,B} respectively if and only if {u} is in {(A+B)/\sqrt{2}} and {v} is in {(\sqrt{2}A-u)\cap(\sqrt{2}B+u)}. As the measure {\mu_{2n}=\mu_n\otimes\mu_n} is invariant under rotations, this gives

\displaystyle \setlength\arraycolsep{2pt} \begin{array}{rl} \displaystyle\mu_n(A)\mu_n(B) &\displaystyle = \mu_{2n}(A\times B)\\ &\displaystyle = \int_{(A+B)/\sqrt{2}}\mu_n\left((\sqrt{2}A-u)\cap(\sqrt{2}B+u)\right)\,\mu_n(du). \end{array} (4)

In order to bound the integrand on the right hand side, we want to show that its maximum is attained when {u=0}. For this, the following result of Prékopa (available here) and Leindler on log-concave functions is used.

Theorem 2 If {f\colon{\mathbb R}^m\times{\mathbb R}^n\rightarrow{\mathbb R}_+} is log-concave then so is {x\mapsto\int f(x,y)dy}.

Applied to the log-concave function {I_{\sqrt{2}A}(v+u)I_{\sqrt{2}B}(v-u)p_n(v)}, with {p_n} being the standard {n}-dimensional Gaussian density and {I_\cdot} the indicator function, this shows that

\displaystyle \mu_n\left((\sqrt{2}A-u)\cap(\sqrt{2}B+u)\right)=\int I_{\sqrt{2}A}(v+u)I_{\sqrt{2}B}(v-u)p_n(v)\,dv

is log-concave in {u}. Together with symmetry in {u}, this implies that its maximum occurs at {u=0}. So, (4) gives the inequality

\displaystyle \mu_n(A)\mu_n(B)\le\mu_n\left((A+B)/\sqrt{2}\right)\mu_n\left((\sqrt{2}A)\cap(\sqrt{2}B)\right).

This almost completes the proof. It is not difficult to show that {\mu_n(\sqrt{2}(A\cap B))} is bounded by {2^{n/2}\mu_n(A\cap B)} and, if {A} and {B} are contained in a ball of radius {c\sqrt{n}}, then {\mu_n((A+B)/\sqrt{2})} is bounded by {(2\pi)^{-n/2}} multiplied by the volume {V_n} of a ball of radius {c\sqrt{2n}},

\displaystyle \begin{array}{l} \displaystyle\mu_n(A)\mu_n(B)\le c_n\mu_n\left(A\cap B\right),\\ \displaystyle c_n=(2\pi)^{-n/2}V_n2^{n/2}. \end{array}

The formula for the volume of a ball of radius {c\sqrt{2n}} together with Stirling’s approximation can be used to show that {c_n^{1/n}\rightarrow 2c\sqrt{e}} as {n} goes to infinity. So, using the value {c=1/(2\sqrt{e})}, the result follows from Lemma 1.

This completes the sketch of the proofs of 1 and 2. I don’t know if it is possible to go much further with the methods described here. However, in a later post, we shall look at an alternative method which is strong enough to prove the conjecture in the special cases where {n=2} or where one of the sets is a centered ellipsoid.

Published by George Lowther

Published

5 thoughts on “The Gaussian Correlation Conjecture”

  1. Pingback: The Gaussian Correlation Conjecture 2 « Almost Sure

    1. Thanks for that link. Sorry, I have been away from this blog for a while. I still have to check some of the details, but the proof looks good, and surprisingly straightforward!

      Reply
  3. Pingback: A Great Solution | Gödel's Lost Letter and P=NP

Leave a comment