Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-27T14:29:22.589Z Has data issue: false hasContentIssue false
  • English
  • Français

THE GROTHENDIECK CONSTANT IS STRICTLY SMALLER THAN KRIVINE’S BOUND

Part of: Basic linear algebra

Published online by Cambridge University Press:  19 November 2013

MARK BRAVERMAN ,
KONSTANTIN MAKARYCHEV ,
YURY MAKARYCHEV  and
ASSAF NAOR
MARK BRAVERMAN
Affiliation:
Princeton University, Department of Computer Science, 35 Olden Street, Princeton, NJ 08540, [email protected]
KONSTANTIN MAKARYCHEV
Affiliation:
Microsoft Research, One Microsoft Way, Redmond, WA 98052, [email protected]
YURY MAKARYCHEV
Affiliation:
Toyota Technological Institute at Chicago, 6045 S. Kenwood Ave., Chicago, IL 60637, [email protected]
ASSAF NAOR
Affiliation:
New York University, Courant Institute, 251 Mercer Street, New York, NY 10012, [email protected]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The (real) Grothendieck constant ${K}_{G} $ is the infimum over those $K\in (0, \infty )$ such that for every $m, n\in \mathbb{N} $ and every $m\times n$ real matrix $({a}_{ij} )$ we have

$$\begin{eqnarray*}\displaystyle \max _{\{ x_{i}\} _{i= 1}^{m} , \{ {y}_{j} \} _{j= 1}^{n} \subseteq {S}^{n+ m- 1} }\sum _{i= 1}^{m} \sum _{j= 1}^{n} {a}_{ij} \langle {x}_{i} , {y}_{j} \rangle \leqslant K\max _{\{ \varepsilon _{i}\} _{i= 1}^{m} , \{ {\delta }_{j} \} _{j= 1}^{n} \subseteq \{ - 1, 1\} }\sum _{i= 1}^{m} \sum _{j= 1}^{n} {a}_{ij} {\varepsilon }_{i} {\delta }_{j} . &&\displaystyle\end{eqnarray*}$$
The classical Grothendieck inequality asserts the nonobvious fact that the above inequality does hold true for some $K\in (0, \infty )$ 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} \leqslant \pi / 2\log (1+ \sqrt{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\rightarrow \infty $) a lower bound on ${K}_{G} $ 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} \lt \pi / 2\log (1+ \sqrt{2} )- {\varepsilon }_{0} $ for some effective constant ${\varepsilon }_{0} \gt 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 ${ \mathbb{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.

MSC classification

Secondary: 15A60: Norms of matrices, numerical range, applications of functional analysis to matrix theory 15A45: Miscellaneous inequalities involving matrices 90C27: Combinatorial optimization 90C22: Semidefinite programming
Type
Research Article
Information
Forum of Mathematics, Pi , Volume 1 , 2013 , e4
Creative Commons
Creative Common License - CCCreative Common License - BY
The online version of this article is published within an Open Access environment subject to the conditions of the Creative Commons Attribution licence .
Copyright
© The Author(s) 2013.

References

Albiac, F. and Kalton, N. J., Topics in Banach Space Theory, Graduate Texts in Mathematics, 233 (Springer, New York, 2006).Google Scholar
Alon, N. and Naor, A., ‘Approximating the cut-norm via Grothendieck’s inequality’, SIAM J. Comput. 35(4) (2006), 787–803 (electronic).Google Scholar
Andrews, G. E., Askey, R. and Roy, R., Special Functions, Encyclopedia of Mathematics and its Applications, 71 (Cambridge University Press, Cambridge, 1999).Google Scholar
Azor, R., Gillis, J. and Victor, J. D., ‘Combinatorial applications of Hermite polynomials’, SIAM J. Math. Anal. 13(5) (1982), 879–890.Google Scholar
Blei, R., Analysis in Integer and Fractional Dimensions, Cambridge Studies in Advanced Mathematics, 71 (Cambridge University Press, Cambridge, 2001).Google Scholar
Blei, R. C., ‘An elementary proof of the Grothendieck inequality’, Proc. Amer. Math. Soc. 100(1) (1987), 58–60.Google Scholar
Cleve, R., Høyer, P., Toner, B. and Watrous, J., ‘Consequences and limits of nonlocal strategies’, 19th Annual IEEE Conference on Computational Complexity (2004), 236–249.Google Scholar
Davie, A. M., ‘Matrix norms related to Grothendieck’s inequality’, in Banach Spaces (Columbia, Mo., 1984), Lecture Notes in Mathematics, 1166 (Springer, Berlin, 1985), 22–26.CrossRefGoogle Scholar
Diestel, J., Fourie, J. H. and Swart, J., The Metric Theory of Tensor Products (American Mathematical Society, Providence, RI, 2008), Grothendieck’s résumé revisited.Google Scholar
Diestel, J., Jarchow, H. and Tonge, A., Absolutely Summing Operators, Cambridge Studies in Advanced Mathematics, 43 (Cambridge University Press, Cambridge, 1995).CrossRefGoogle Scholar
Fishburn, P. C. and Reeds, J. A., ‘Bell inequalities, Grothendieck’s constant, and root two’, SIAM J. Discrete Math. 7(1) (1994), 48–56.Google Scholar
Frieze, A. and Kannan, R., ‘Quick approximation to matrices and applications’, Combinatorica 19(2) (1999), 175–220.CrossRefGoogle Scholar
Garling, D. J. H., Inequalities: A Journey into Linear Analysis (Cambridge University Press, Cambridge, 2007).Google Scholar
Grothendieck, A., ‘Résumé de la théorie métrique des produits tensoriels topologiques’, Bol. Soc. Mat. São Paulo 8 (1953), 1–79.Google Scholar
Grötschel, M., Lovász, L. and Schrijver, A., ‘The ellipsoid method and its consequences in combinatorial optimization’, Combinatorica 1(2) (1981), 169–197.CrossRefGoogle Scholar
Haagerup, U., ‘A new upper bound for the complex Grothendieck constant’, Israel J. Math. 60(2) (1987), 199–224.CrossRefGoogle Scholar
Jameson, G. J. O., Summing and Nuclear Norms in Banach Space Theory, London Mathematical Society Student Texts, 8 (Cambridge University Press, Cambridge, 1987).Google Scholar
Johnson, W. B. and Lindenstrauss, J., ‘Basic concepts in the geometry of Banach spaces’, in Handbook of the Geometry of Banach Spaces, Vol. I (North-Holland, Amsterdam, 2001), 1–84.Google Scholar
Khot, S., ‘On the power of unique 2-prover 1-round games’, in Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (ACM, New York, 2002), 767–775 (electronic).Google Scholar
Khot, S., Kindler, G., Mossel, E. and O’Donnell, R., ‘Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?’, SIAM J. Comput. 37(1) (2007), 319–357 (electronic).Google Scholar
Khot, S. and Naor, A., ‘Grothendieck-type inequalities in combinatorial optimization’, Comm. Pure Appl. Math. 65(7) (2012), 992–1035.Google Scholar
König, H., ‘On an extremal problem originating in questions of unconditional convergence’, in Recent Progress in Multivariate Approximation (Witten-Bommerholz, 2000), Internat. Ser. Numer. Math., 137 (Birkhäuser, Basel, 2001), 185–192.Google Scholar
Krivine, J.-L., ‘Sur la constante de Grothendieck’, C. R. Acad. Sci. Paris Sér. A–B 284(8) (1977), A445–A446.Google Scholar
Krivine, J.-L., ‘Constantes de Grothendieck et fonctions de type positif sur les sphères’, Adv. Math. 31(1) (1979), 16–30.Google Scholar
Lieb, E. H., ‘Gaussian kernels have only Gaussian maximizers’, Invent. Math. 102(1) (1990), 179–208.Google Scholar
Lindenstrauss, J. and Pełczyński, A., ‘Absolutely summing operators in ${L}_{p} $-spaces and their applications’, Studia Math. 29 (1968), 275–326.Google Scholar
Lindenstrauss, J. and Tzafriri, L., Classical Banach Spaces. I. Sequence Spaces, Ergebnisse der Mathematik und ihrer Grenzgebiete, 92 (Springer, Berlin, 1977).Google Scholar
Maurey, B., ‘Une nouvelle démonstration d’un théorème de Grothendieck’, in Séminaire Maurey-Schwartz Année 1972–1973: Espaces ${L}^{p} $ et applications radonifiantes, Exp. No. 22 (Centre de Math., École Polytech, Paris, 1973), 7.Google Scholar
Maurey, B. and Pisier, G., ‘Un théorème d’extrapolation et ses conséquences’, C. R. Acad. Sci. Paris Sér. A–B 277 (1973), A39–A42.Google Scholar
Naor, A. and Regev, O., ‘Krivine schemes are optimal’, Proc. Amer. Math. Soc., 2012, to appear, preprint available at http://arxiv.org/abs/1205.6415.Google Scholar
Pisier, G., ‘Grothendieck’s theorem for noncommutative ${C}^{\ast } $-algebras, with an appendix on Grothendieck’s constants’, J. Funct. Anal. 29(3) (1978), 397–415.Google Scholar
Pisier, G., Factorization of Linear Operators and Geometry of Banach Spaces, CBMS Regional Conference Series in Mathematics, 60 (Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1986).CrossRefGoogle Scholar
Pisier, G., ‘Grothendieck’s theorem, past and present’, Bull. Amer. Math. Soc. (N.S.) 49(2) (2012), 237–323.Google Scholar
Raghavendra, P. and Steurer, D., ‘Towards computing the Grothendieck constant’, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, 525–534.Google Scholar
Reeds, J. A., ‘A new lower bound on the real Grothendieck constant’, unpublished manuscript, available at http://www.dtc.umn.edu/reedsj/bound2.dvi 1991.Google Scholar
Rietz, R. E., ‘A proof of the Grothendieck inequality’, Israel J. Math. 19 (1974), 271–276.CrossRefGoogle Scholar
Schwartz, L., Geometry and Probability in Banach Spaces, Lecture Notes in Mathematics, 852 (Springer, Berlin, 1981), based on notes taken by Paul R. Chernoff.Google Scholar
Tsirelson, B. S., ‘Quantum analogues of Bell’s inequalities. The case of two spatially divided domains’, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 142 (1985), 174–194, 200. Problems of the theory of probability distributions, IX.Google Scholar