Grothendieck's Inequality

Abstract: The year was 1953. Rajendra Prasad was still the president of India after winning the presidential election one year prior. On the other side of the globe, a journal in São Paulo published a paper by Alexander Grothendieck. "Résumé de la théorie métrique des produits tensoriels topologiques," or, comment dites-vous... "Summary of the metric theory of topological tensor products." The central theorem of this paper is now known as Grothendieck's inequality. For nearly 15 years, nobody seemed to care about it. In 1968, Lindenstrauss and Pełczyński published a paper highlighting, reformulating and building on the various gems in Grothendieck's paper. One of their reformulations of Grothendieck's inequality is extremely relevant to complexity theory.

Suppose you are interested in calculating, for a given real matrix A, the maximum of sum A_ij d_i e_j, with the constraint that each d_i and e_j should be a real number between 1 and -1. (People interested in finding the largest cut in a weighted bipartite graph need not suppose.) Grothendieck's inequality says that you might as well maximise over d_i and e_j being real vectors of arbitrary dimension, but with the norm of each vector being at most 1. You might get a larger maximum in the latter case, but it is larger by at most a multiplicative constant.

This constant, maximised over all matrices A, is known as Grothendieck's constant. He showed it is at least ~1.5 and at most ~2.3. Subsequent works have improved these bounds, to being at least ~1.676 and at most ~1.782.

We will see a proof of the ~1.782 upper bound, by Krivine in 1977. It is remarkably neat and elementary.