KRIVINE SCHEMES ARE OPTIMAL

ASSAF NAOR AND ODED REGEV

Abstract. It is shown that for every k ∈ ℕ there exists a Borel probability measure μ on {−1, 1}^{ℝ^{k}} × {−1, 1}^{ℝ^{k}} such that for every m, n ∈ ℕ and x_{1}, …, x_{m}, y_{1}, …, y_{n} ∈ 𝕊^{m+n−1} there exist x′_{1}, …, x′_{m}, y′_{1}, …, y′_{n} ∈ 𝕊^{m+n−1} such that if G : ℝ^{m+n} → ℝ^{k} is a random k × (m + n) matrix whose entries are i.i.d. standard Gaussian random variables then for all (i, j) ∈ {1, …, m} × {1, …, n} we have

𝔼_{G} [∫_{\{−1,1\}^{ℝ^{k}} ×\{−1,1\}^{ℝ^{k}}} f(Gx′_{i})g(Gy′_{j})dμ(f, g)] = \frac{⟨x_{i}, y_{j}⟩}{(1 + C/k)K_{G}} ,

where K_{G} is the real Grothendieck constant and C ∈ (0, ∞) is a universal constant. This establishes that Krivine’s rounding method yields an arbitrarily good approximation of K_{G}.

1. introduction

Grothendieck’s inequality [4, 7] asserts that there exists a constant K ∈ (0, ∞) such that for every n, m ∈ ℕ, every m × n matrix A = (a_{ij}) with real entries, and every choice of unit vectors x_{1}, …, x_{m}, y_{1}, …, y_{n} ∈ 𝕊^{m+n−1}, there are signs ε_{1}, …, ε_{m}, δ_{1}, …, δ_{n} ∈ {−1, 1} satisfying

∑_{i=1}^{m} ∑_{j=1}^{n} a_{ij}⟨x_{i}, y_{j}⟩ ⩽ K ∑_{i=1}^{m} ∑_{j=1}^{n} a_{ij}ε_{i}δ_{j}.  (1)

The infimum over those K ∈ (0, ∞) for which (1) holds true is called the (real) Grothendieck constant and is denoted K_{G}. The exact value of K_{G} remains a long-standing mystery ever since Grothendieck’s original 1953 work [4]. The best known bounds on K_{G} are due to [9, 2].

We call a Borel probability measure μ on {−1, 1}^{ℝ^{k}} × {−1, 1}^{ℝ^{k}} a k-dimensional Krivine scheme of quality K ∈ (0, ∞) if for every m, n ∈ ℕ and every choice of unit vectors x_{1}, …, x_{m}, y_{1}, …, y_{n} ∈ 𝕊^{m+n−1} there exist new unit vectors x′_{1}, …, x′_{m}, y′_{1}, …, y′_{n} ∈ 𝕊^{m+n−1} such that if G : ℝ^{m+n} → ℝ^{k} is a random k × (m + n) matrix whose entries are i.i.d. standard Gaussian random variables then for all (i, j) ∈ {1, …, m} × {1, …, n} we have

𝔼_{G} [∫_{\{−1,1\}^{ℝ^{k}} ×\{−1,1\}^{ℝ^{k}}} f(Gx′_{i})g(Gy′_{j})dμ(f, g)] = \frac{1}{K} ⟨x_{i}, y_{j}⟩.  (2)

For (2) to make sense we need to require that the function of G appearing under the expectation in (2) is Lebesgue measurable. The required measurability will be immediate for the Krivine schemes that we discuss below, but in general this assumption should be taken to be part of the definition of a Krivine scheme.

A.N. was supported by NSF grant CCF-0832795, BSF grant 2010021, the Packard Foundation and the Simons Foundation. O. R. was supported by a European Research Council (ERC) Starting Grant.

The existence of a k-dimensional Krivine scheme of quality K implies that K_{G} ⩽ K. Indeed, since f(Gx′_{i}), g(Gy′_{j}) ∈ {−1, 1} point-wise,

∑_{i=1}^{m} ∑_{j=1}^{n} a_{ij}⟨x_{i}, y_{j}⟩ = K𝔼_{G} [∫_{{−1,1}^{ℝ^{k}} ×{−1,1}^{ℝ^{k}}} (∑_{i=1}^{m} ∑_{j=1}^{n} a_{ij}f(Gx′_{i})g(Gy′_{j})) dμ(f, g)]

⩽ K max_{ε_{1},...,ε_{m},δ_{1},...,δ_{n}∈{−1,1}} ∑_{i=1}^{m} ∑_{j=1}^{n} a_{ij}ε_{i}δ_{j}.  (3)

A different way to describe the above reasoning is via the following procedure that, given unit vectors x_{1}, …, x_{m}, y_{1}, …, y_{n} ∈ 𝕊^{m+n−1}, produces signs ε_{1}, …, ε_{m}, δ_{1}, …, δ_{n} ∈ {−1, 1} so as to satisfy the desired inequality (1). Identify f ∈ {−1, 1}^{ℝ^{k}} with the bipartition of ℝ^{k} given by f^{−1}(−1), f^{−1}(1) ⊆ ℝ^{k}. Thus μ could be thought of as a carefully chosen notion of a random pair ({A, ℝ^{k} ∖ A}, {B, ℝ^{k} ∖ B}) of bipartitions of ℝ^{k}. The new unit vectors x′_{1}, …, x′_{m}, y′_{1}, …, y′_{n} ∈ 𝕊^{m+n−1} should be thought of as the result of preprocessing the initial vectors x_{1}, …, x_{m}, y_{1}, …, y_{n} ∈ 𝕊^{m+n−1}, in anticipation of the “random projection” step to come. In this step one chooses a random k ×(m+n) Gaussian matrix G, and, independently of G, a pair of bipartitions ({A, ℝ^{k} ∖ A}, {B, ℝ^{k} ∖ B}) whose law is μ. One then defines random signs ε_{1}, …, ε_{m}, δ_{1}, …, δ_{n} ∈ {−1, 1} by

ε_{i} =^{def} \{ \begin{matrix}1 & if Gx′_{i} ∈ A, \\ −1 & if Gx′_{i} ∈ ℝ^{k} ∖ A, \end{matrix} and δ_{j} =^{def} \{ \begin{matrix}1 & if Gy′_{j} ∈ B, \\ −1 & if Gy′_{j} ∈ ℝ^{k} ∖ B. \end{matrix}

Inequality (3) means that for this choice of random signs the desired Grothendieck inequality (1) holds in expectation, with respect to the randomness of the matrix G and the pair of bipartitions ({A, ℝ^{k} ∖ A}, {B, ℝ^{k} ∖ B}).

The preprocessing step of a Krivine scheme has been somewhat suppressed in the above discussion because it is essentially determined by the measure μ itself. Indeed, by rotation invariance the left hand side of (2) depends only on ⟨x′_{i}, y′_{j}⟩; say, it equals Ψ(⟨x′_{i}, y′_{j}⟩) for some function Ψ : [−1, 1] → [−1, 1]. If Ψ were invertible on [−1/K, 1/K] then (2) would become ⟨x′_{i}, y′_{j}⟩ = Ψ^{−1}(⟨x_{i}, y_{j}⟩/K). This means that the mutual angles between the new unit vectors (if they indeed exist) are determined by (2) and the initial configuration of vectors. Only these angles matter for the purpose of applying a Krivine scheme to bound K_{G}.

We note that in the known examples of Krivine schemes (including those described below) the preprocessing step that associates new unit vectors x′_{1}, …, x′_{m}, y′_{1}, …, y′_{n} ∈ 𝕊^{m+n−1} to the initial unit vectors x_{1}, …, x_{m}, y_{1}, …, y_{n} ∈ 𝕊^{m+n−1} is oblivious to the initial configuration in the following sense. There exist (nonlinear) mappings S, T : 𝕊^{∞} → 𝕊^{∞}, where 𝕊^{∞} is the unit sphere of ℓ_{2}, such that if we identify the span of T (x_{1}), …, T (x_{m}), S(y_{1}), …, S(y_{n}) with a subspace of ℝ^{m+n} then (2) holds true with x′_{i} = T (x_{i}) and y′_{j} = S(y_{j}). We call such Krivine schemes oblivious Krivine schemes. It is possible to show that any Krivine scheme satisfying an additional continuity assumption is oblivious. For all purposes that we can imagine, one can take the definition of a Krivine scheme to include the assumption that it is oblivious.

Theorem 1.1 (Optimality of Krivine schemes). For every k ∈ ℕ there exists a k-dimensional oblivious Krivine scheme of quality (1 + O(1/k))K_{G}.

One might initially believe that restricting attention to Krivine schemes in order to prove Grothendieck’s inequality is too restrictive: the role of random Gaussian matrices is not mandated by the problem at hand, and moreover it might be beneficial to choose the signs ε_{1}, …, ε_{m}, δ_{1}, …, δ_{n} ∈ {−1, 1} via a procedure that depends on the given matrix (a_{ij}). Nevertheless, Theorem 1.1 shows that oblivious Krivine rounding schemes capture K_{G} exactly.

To date, the best known upper estimates on K_{G} were obtained via oblivious Krivine schemes. Krivine introduced [6] this approach to Grothendieck’s inequality in 1977 in order to obtain a new upper bound on K_{G}. His argument used a one-dimensional Krivine scheme that is based on a deterministic partition of ℝ: in Krivine’s original work the measure μ is supported on the pair (sign(·), sign(·)) ∈ {−1, 1}^{ℝ} × {−1, 1}^{ℝ}. Krivine conjectured [6] that the bound thus obtained is actually the exact value of the Grothendieck constant. Clearly, if true, Krivine’s conjecture would have implied that oblivious Krivine schemes yield an exact evaluation of K_{G}, and would have thus made Theorem 1.1 redundant.

However, in 2011 Krivine’s conjecture was refuted [2], yielding the best known upper bound on K_{G} via a two-dimensional Krivine rounding scheme. It was this development that motivated us to investigate the possible validity of Theorem 1.1. While at present there is no compelling conjecture as to the exact value of K_{G} (though in [2] a candidate for this value is proposed based on a certain geometric conjecture that at this point seems quite speculative), Theorem 1.1 justifies the focus on oblivious Krivine schemes. In essence, Theorem 1.1 says that in order to understand the Grothendieck constant it suffices to focus on ways to partition Euclidean space so as to ensure the validity of (2) with K as small as possible.

2. Proof of Theorem 1.1

Fix k ∈ ℕ. By a well-known duality argument (see [8, Thm. 3.4] and [1, Prop. 1.1]) there exists a Borel probability measure ν_{k} on {−1, 1}^{𝕊^{k−1}} × {−1, 1}^{𝕊^{k−1}} such that

∀ x, y ∈ 𝕊^{k−1}, ∫_{\{−1,1\}^{𝕊^{k−1}}×\{−1,1\}^{𝕊^{k−1}}} f(x)g(y)dν_{k}(f, g) = \frac{1}{K_{G}} ⟨x, y⟩ .  (4)

By identifying f ∈ {−1, 1}^{𝕊^{k−1}} with its radial extension x ↦ f(x/∥x∥_{2}) (with the convention that the radial extension equals 1 at x = 0), the measure ν_{k} induces a probability measure μ_{k} on {−1, 1}^{ℝ^{k}} × {−1, 1}^{ℝ^{k}} that satisfies

∀ x, y ∈ ℝ^{k} ∖ \{0\}, ∫_{\{−1,1\}^{ℝ^{k}} ×\{−1,1\}^{ℝ^{k}}} f(x)g(y)dμ_{k}(f, g) = \frac{1}{K_{G}} ⟨\frac{x}{∥x∥_{2}} , \frac{y}{∥y∥_{2}} ⟩ . (5)

Our goal will be to show that μ_{k} is the desired Krivine scheme (note that, due to (5), the measurability of the function of G appearing under the expectation in (2) is immediate). To this end it would be beneficial to rewrite the key requirement (2) using (5). Let G_{1}, G_{2} ∈ ℝ^{k} be i.i.d. standard Gaussian random vectors in ℝ^{k}. For t ∈ [−1, 1] define

f_{k}(t) =^{def} 𝔼_{G_{1},G_{2}} [⟨\frac{G_{1}}{∥G_{1}∥_{2}} , \frac{tG_{1} + \sqrt{1 − t^{2}}G_{2}}{∥tG_{1} + \sqrt{1 − t^{2}}G_{2}∥_{2}} ⟩] .  (6)

Using this notation, combined with (5) and rotation invariance, the desired identity (2) becomes

∀(i, j) ∈ \{1, …, m\} × \{1, …, n\}, \frac{1}{K_{G}} f_{k} (⟨x′_{i}, y′_{j}⟩) = \frac{1}{K} ⟨x_{i}, y_{j}⟩.  (7)

By direct computation (see [5, page 203] for k = 2 and [3, Lemma 2.1] for general k ⩾ 2) for every t ∈ [−1, 1] we have f_{k}(t) = ∑_{n=0}^{∞} a_{n}(k)t^{2n+1}, where

a_{n}(k) =^{def} \frac{1}{4^{n}\sqrt{π}} \binom{2n}{n}\frac{Γ ((k + 1)/2)^{2} Γ (n + 1/2)}{Γ (k/2) Γ (n + 1 + k/2)} = \frac{2}{k} (\frac{Γ (\frac{k+1}{2})}{Γ (\frac{k}{2})})^{2} ∏_{j=1}^{n} \frac{(2j − 1)^{2}}{2j(k + 2j)}. (8)

By Stirling’s formula, for every integer n ⩾ 2 we have

a_{n}(k) ≍ \frac{k^{(k+1)/2}}{2^{k/2}\sqrt{n}(n + k/2)^{(k+1)/2}(1 + k/(2n))^{n}} ≲ \frac{k^{(k+1)/2}}{k^{2}2^{k/2}(n + k/2)^{(k+1)/2}} .  (9)

Hence,

∑_{n=2}^{∞} a_{n}(k) ≲ \frac{k^{(k+1)/2}}{k^{2}2^{k/2}} ∫_{1}^{∞} \frac{dx}{(x + k/2)^{(k+1)/2}} ≲ \frac{k^{(k+1)/2}}{k^{3}2^{k/2}(k/2)^{(k−1)/2}} ≲ \frac{1}{k^{2}} .  (10)

Also,

a_{0}(k) = 1 − \frac{1}{2k} + O (\frac{1}{k^{2}} ) and a_{1}(k) = \frac{a_{0}(k)}{2(k + 2)} ≍ \frac{1}{k}.  (11)

Write 𝔻 = \{z ∈ ℂ : |z| < 1\}. By (10) for every z ∈ \overline{𝔻} we have f_{k}(z) = ∑_{n=0}^{∞} a_{n}(k)z^{2n+1}, and f_{k} is continuous on \overline{𝔻} and analytic on 𝔻. Moreover, by (10) and (11) we know that there exists a universal constant C ∈ (1, ∞) such that |f_{k}(z) − a_{0}(k)z| < C/k for every z ∈ ∂𝔻. We assume from now on that k is large enough so that a_{0}(k) − 2C/k > 0. Then |a_{0}(k)z − f_{k}(z)| < |a_{0}(k)z − ζ| for every ζ ∈ (a_{0}(k) − C/k)𝔻 and z ∈ ∂𝔻. By Rouché’s theorem it follows that a_{0}(k)z − ζ and f_{k}(z) − ζ have the same number of zeros in 𝔻. Hence f_{k}^{−1} : (a_{0}(k) − C/k)𝔻 → 𝔻 is well defined and analytic on (a_{0}(k) − C/k)𝔻.

For w ∈ (a_{0}(k) − C/k)𝔻 write f_{k}^{−1}(w) = ∑_{n=0}^{∞} b_{n}(k)w^{2n+1} for some {b_{n}(k)}_{n=0}^{∞} ⊆ ℝ. Thus b_{0}(k) = 1/a_{0}(k) and b_{1}(k) = −a_{1}(k)/a_{0}(k)^{4} = −1/(2(k + 2)a_{0}(k)^{3}). Observe that for k large enough we have 1 − 4C/k ⩽ (a_{0}(k) − 2C/k)/a_{0}(k) ⩽ ∑_{n=0}^{∞} |b_{n}(k)|(a_{0}(k) − 2C/k)^{2n+1} < ∞, so that by continuity there exists c_{k} ∈ (0, 1−2C/k] satisfying ∑_{n=0}^{∞} |b_{n}(k)|c_{k}^{2n+1} = 1−4C/k.

Lemma 2.1. We have c_{k} ⩾ 1 − O(1/k).

Assuming the validity of Lemma 2.1 for the moment, we conclude the proof of Theorem 1.1.

Proof of Theorem 1.1. This is a slight variant of Krivine’s original argument [6]. Define two

mappings S, T : 𝕊^{∞} → (⨁_{n=0}^{∞}(ℓ_{2})^{⊗(2n+1)}) ⊕ ℝ^{2} =^{def} H ≅ ℓ_{2} by

S(x) =^{def} ((|b_{n}(k)|^{1/2}c_{k}^{(2n+1)/2}x^{⊗(2n+1)})_{n=0}^{∞} , (\sqrt{\frac{4C}{k}} , 0)) ,

and

T (x) =^{def} ((sign(b_{n}(k))|b_{n}(k)|^{1/2}c_{k}^{(2n+1)/2}x^{⊗(2n+1)})_{n=0}^{∞} , (0, \sqrt{\frac{4C}{k}} )) .

For every x ∈ 𝕊^{∞} we have ∥S(x)∥_{H}^{2} = ∥T (x)∥_{H}^{2} = ∑_{n=0}^{∞} |b_{n}(k)|c_{k}^{2n+1}+4C/k = 1. Moreover, f_{k} (⟨S(x), T (y)⟩_{H}) = f_{k} (∑_{n=0}^{∞} b_{n}(k)c_{k}^{2n+1}⟨x, y⟩^{2n+1}) = f_{k}(f_{k}^{−1}(c_{k}⟨x, y⟩)) = c_{k}⟨x, y⟩. Thus, recalling the formulation of the desired identity appearing in (7), μ_{k} is an oblivious kdimensional Krivine scheme of quality K_{G}/c_{k} = (1 + O(1/k))K_{G}, as desired. □

It remains to prove Lemma 2.1.

Proof of Lemma 2.1. For every w ∈ (a_{0}(k)−C/k)𝔻 write z = f_{k}^{−1}(w) ∈ 𝔻. Then using (11),

f_{k}^{−1}(w) − b_{0}(k)w − b_{1}(k)w^{3} = f_{k}^{−1}(w) − \frac{w}{a_{0}(k)} + \frac{w^{3}}{2(k + 2)a_{0}(k)^{3}}

= −\frac{f_{k}(z) − a_{0}(k)z − a_{1}(k)z^{3}}{a_{0}(k)} − \frac{(a_{0}(k)z − f_{k}(z))(a_{0}(k)^{2}z^{2} + a_{0}(k)zf_{k}(z) + f_{k}(z)^{2})}{2(k + 2)a_{0}(k)^{3}}. (12)

By (10) and (11) we have |f_{k}(z) − a_{0}(k)z − a_{1}(k)z^{3}| ≲ 1/k^{2} and |f_{k}(z) − a_{0}(k)z| ≲ 1/k. Moreover, due to (11) we have a_{0}(k) ≍ 1 and therefore |a_{0}(k)^{2}z^{2} + a_{0}(k)zf_{k}(z) + f_{k}(z)^{2}| ≲ 1. Consequently, it follows from (12) that

|f_{k}^{−1}(w) − b_{0}(k)w − b_{1}(k)w^{3}| ≲ \frac{1}{k^{2}} .

Hence, by Cauchy’s integral formula for every integer n ⩾ 2 and every r ∈ (0, a_{0}(k) − C/k),

|b_{n}(k)| = |\frac{1}{2πi} ∮_{r∂𝔻} \frac{f_{k}^{−1}(w) − b_{0}(k)w − b_{1}(k)w^{3}}{w^{2n+2}} dw| ≲ \frac{1}{k^{2}r^{2n+1}} .

Thus there is a universal constant A ∈ (0, ∞) such that |b_{n}(k)| ⩽ Ak^{−2}(a_{0}(k) − C/k)^{−(2n+1)} for n ⩾ 2. If c_{k} ⩾ a_{0}(k) − C/k then we are done. Assume therefore that c_{k} < a_{0}(k) − C/k, in which case, recalling that b_{0}(k) = 1/a_{0}(k) and b_{1}(k) = −1/(2(k + 2)a_{0}(k)^{3}), we have

1 = ∑_{n=0}^{∞} |b_{n}(k)|c_{k}^{2n+1} ⩽ \frac{c_{k}}{a_{0}(k)} + \frac{c_{k}^{3}}{2(k + 2)a_{0}(k)^{2}} + \frac{A}{k^{2}} ∑_{n=2}^{∞} (\frac{c_{k}}{a_{0}(k) − C/k} )^{2n+1}

= \frac{c_{k}}{a_{0}(k)} + \frac{c_{k}^{3}}{2(k + 2)a_{0}(k)^{2}} + \frac{A}{k^{2}} · \frac{(c_{k}/(a_{0}(k) − C/k))^{5}}{1 − (c_{k}/(a_{0}(k) − C/k))^{2}} .  (13)

By (11), a straightforward computation shows that (13) implies that c_{k} ⩾ 1 − O(1/k). □

Acknowledgements. We are grateful to Thomas Vidick for helpful suggestions.

References

[1] R. Blei. The Grothendieck inequality revisited. Preprint available at http://arxiv.org/abs/1111.7304, 2012.

[2] M. Braverman, K. Makarychev, Y. Makarychev, and A. Naor. The Grothendieck constant is strictly smaller than Krivine’s bound. In IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 453–462, 2011.

[3] J. Briët, F. M. de Oliveira Filho, and F. Vallentin. Grothendieck inequalities for semidefinite programs with rank constraint. Preprint available at http://arxiv.org/pdf/1011.1754v2.pdf, 2010.

[4] A. Grothendieck. Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. Mat. São Paulo, 8:1–79, 1953.

[5] U. Haagerup. A new upper bound for the complex Grothendieck constant. Israel J. Math., 60(2):199–224, 1987.

[6] J.-L. Krivine. Sur la constante de Grothendieck. C. R. Acad. Sci. Paris Sér. A-B, 284(8):A445–A446, 1977.

[7] J. Lindenstrauss and A. Pełczyński. Absolutely summing operators in L_{p}-spaces and their applications. Studia Math., 29:275–326, 1968.

[8] G. Pisier. Grothendieck’s theorem, past and present. Bull. Am. Math. Soc., New Ser., 49(2):237–323, 2012.

[9] J. A. Reeds. A new lower bound on the real Grothendieck constant. Unpublished manuscript, available

at http://www.dtc.umn.edu/reedsj/bound2.dvi, 1991.