Krivine schemes are optimal
Résumé
Grothendieck's inequality asserts that there exists a constant K>0 such that for every m,n and every m×n matrix A=(aij) with real entries and every choice of unit vectors x1,…,xm,y1,…,yn∈Sm+n−1, there are signs ε1,…,εm,δ1,…,δn∈{−1,1} satisfying
∑mi=1∑nj=1aij⟨xi,yj⟩≤K∑mi=1∑nj=1aijεiδj.
The infimum over those K for which this inequality holds is called the (real) Grothendieck constant and is denoted KG.
In order to investigate the exact value of KG, the authors introduce the following definition. A Borel probability measure μ on {−1,1}Rk×{−1,1}Rk is a k-dimensional Krivine scheme of quality K>0 if for every m,n and every choice of unit vectors x1,…,xm,y1,…,yn∈Sm+n−1, there exist new unit vectors x′1,…,x′m,y′1,…,y′n∈Sm+n−1 such that if G:Rm+n→Rk 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
EG[∫{−1,1}Rk×{−1,1}Rkf(Gx′i)g(Gy′j)dμ(f,g)]=1K⟨xi,yj⟩.
The authors note that the existence of a k-dimensional Krivine scheme of quality K>0 implies that KG≤K. A special one-dimensional Krivine scheme was introduced by J.-L. Krivine [C. R. Acad. Sci. Paris Sér. A-B 284 (1977), no. 8, A445–A446; MR0428414 (55 #1435)] in order to obtain a new upper bound on KG. Krivine conjectured that his bound is exact. This conjecture was refuted [M. Braverman et al., in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science—FOCS 2011, 453–462, IEEE Computer Soc., Los Alamitos, CA, 2011; MR2932721] yielding a better upper bound on KG via a two-dimensional Krivine scheme.
In the paper under review the authors prove the optimality of the Krivine scheme: For every k∈N there exists a k-dimensional Krivine scheme of quality (1+O(1/k))KG.