## Abstract

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}}^{n} _{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=1}a_{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) - ϵ_{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 R^{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.

Original language | English (US) |
---|---|

Article number | e4 |

Journal | Forum of Mathematics, Pi |

Volume | 1 |

DOIs | |

State | Published - 2013 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Analysis
- Algebra and Number Theory
- Statistics and Probability
- Mathematical Physics
- Geometry and Topology
- Discrete Mathematics and Combinatorics