The grothendieck constant is strictly smaller than krivine's bound

The (real) Grothendieck constant K_G is the infimum over those K ∈ (0, ∞) such that for every m, n ∈ N and every m × n real matrix (a_ij) we have max -x_i}^m _i=1, -y_j}ⁿ _j=1 ⊆ S^n+m-1 Σ^m _i=1 Σ^m _j=1 a_ij(x_i, y_j) ≤ K -ϵ_i}^m _i=1, -δ_j}^{max n} _j=1 ⊆-1, 1} Σ^m _i=1 Σ^m _j=1a_ijϵ_iδ_j. The classical Grothendieck inequality asserts the nonobvious fact that the above inequality does hold true for some K ∈ (0, ∞) that is independent of m; n and (a_ij). 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 K_G remains a mystery. The last progress on this problem was in 1977, when Krivine proved that K_G ≤ π/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 (a_ij) which exhibit (asymptotically, as m; n → ∞) a lower bound on KG that matches Krivine's bound. Here, we obtain an improved Grothendieck inequality that holds for all matrices (a_ij) and yields a bound K_G < π/2 log(1 + √2) - ϵ₀ for some effective constant ϵ₀ > 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 R² 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.