← All problems

10 Lectures and 42 Open Problems — The Grothendieck Constant

For positive integers m,nm,n and a real matrix A=(aij)∈Rm×nA=(a_{ij})\in\mathbb{R}^{m\times n}, define the sign optimum and vector optimum by

M±(A)=max⁡εi,δj∈{−1,1}∣∑i=1m∑j=1naijεiδj∣,Mvec(A)=sup⁡ui,vj∈Sm+n−1∣∑i=1m∑j=1naij⟨ui,vj⟩∣,M_{\pm}(A)=\max_{\varepsilon_i,\delta_j\in\{-1,1\}}\left|\sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij}\varepsilon_i\delta_j\right|, \qquad M_{\mathrm{vec}}(A)=\sup_{u_i,v_j\in S^{m+n-1}}\left|\sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij}\langle u_i,v_j\rangle\right|,

where Sm+n−1S^{m+n-1} is the unit sphere in Rm+n\mathbb{R}^{m+n}. The real Grothendieck constant is

KG=inf⁡{K>0:Mvec(A)≤KM±(A) for every m,n∈N and every A∈Rm×n}.K_G=\inf\left\{K>0: M_{\mathrm{vec}}(A)\le K M_{\pm}(A)\text{ for every }m,n\in\mathbb{N}\text{ and every }A\in\mathbb{R}^{m\times n}\right\}.

The question is to determine the exact value of KGK_G. Braverman, Makarychev, Makarychev, and Naor (2013) New Lower and Upper Bounds for the Grothendieck Constant

Background

Grothendieck’s inequality asserts that the ratio between the vector optimum and the sign optimum is bounded by a universal constant, uniformly over all matrix dimensions and coefficients. In optimization, this constant is the worst-case integrality gap of the canonical semidefinite relaxation of a bilinear sign problem; the inequality also has important roles in the geometry of Banach spaces, operator spaces, harmonic analysis, and quantum information. New Lower and Upper Bounds for the Grothendieck Constant

Since Grothendieck’s 1953 discovery, the central challenge has been to narrow the gap between constructions giving lower bounds and rounding schemes giving upper bounds. Krivine’s 1977 scheme first lifts the vectors to an infinite-dimensional space and then rounds them by a random hyperplane, yielding KG≤π/(2log⁡(1+2))K_G\le \pi/(2\log(1+\sqrt{2})). Krivine conjectured that this was exact. Braverman, Makarychev, Makarychev, and Naor disproved the conjecture by mixing hyperplane rounding with a non-hyperplane method; their argument uses random two-dimensional projections and a suitable partition of the plane. The Grothendieck Constant is Less Than {π/2 log(1+√2)}-10^{-5} Braverman, Makarychev, Makarychev, and Naor (2013)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.