The Grothendieck Constant is Strictly Smaller than Krivine's Bound

Abstract

The (real) Grothendieck constant 𝐾𝐺 is the infimum over those 𝐾∈(0,∞) such that for every 𝑚,𝑛∈ℕ and every 𝑚×𝑛 real matrix (𝑎𝑖𝑗) we have

max{𝑥𝑖}𝑚𝑖=1,{𝑦𝑗}𝑛𝑗=1⊆𝑆𝑛+𝑚−1∑𝑖=1𝑚∑𝑗=1𝑛𝑎𝑖𝑗⟨𝑥𝑖,𝑦𝑗⟩⩽𝐾max{𝜀𝑖}𝑚𝑖=1,{𝛿𝑗}𝑛𝑗=1⊆{−1,1}∑𝑖=1𝑚∑𝑗=1𝑛𝑎𝑖𝑗𝜀𝑖𝛿𝑗. The classical Grothendieck inequality asserts the nonobvious fact that the above inequality does hold true for some 𝐾∈(0,∞) that is independent of 𝑚,𝑛 and (𝑎𝑖𝑗) . Since Grothendieck’s 1953 discovery of this powerful theorem, it has found numerous applications in a variety of areas, but, despite attracting a lot of attention, the exact value of the Grothendieck constant 𝐾𝐺 remains a mystery. The last progress on this problem was in 1977, when Krivine proved that 𝐾𝐺⩽𝜋/2log(1+2‾√) and conjectured that his bound is optimal. Krivine’s conjecture has been restated repeatedly since 1977, resulting in focusing the subsequent research on the search for examples of matrices (𝑎𝑖𝑗) which exhibit (asymptotically, as 𝑚,𝑛→∞ ) a lower bound on 𝐾𝐺 that matches Krivine’s bound. Here, we obtain an improved Grothendieck inequality that holds for all matrices (𝑎𝑖𝑗) and yields a bound 𝐾𝐺<𝜋/2log(1+2‾√)−𝜀0 for some effective constant 𝜀0>0 . Other than disproving Krivine’s conjecture, and along the way also disproving an intermediate conjecture of König that was made in 2000 as a step towards Krivine’s conjecture, our main contribution is conceptual: despite dealing with a binary rounding problem, random two-dimensional projections, when combined with a careful partition of ℝ2 in order to round the projected vectors to values in {−1,1} , perform better than the ubiquitous random hyperplane technique. By establishing the usefulness of higher-dimensional rounding schemes, this fact has consequences in approximation algorithms. Specifically, it yields the best known polynomial-time approximation algorithm for the Frieze–Kannan Cut Norm problem, a generic and well-studied optimization problem with many applications.