In mathematics, the Grothendieck inequality states that there is a universal constant
If Mij is an n × n (real or complex) matrix with for all (real or complex) numbers si, tj of absolute value at most 1, then for all vectors Si, Tj in the unit ball B(H) of a (real or complex) Hilbert space H, the constant
being independent of n. For a fixed Hilbert space of dimension d, the smallest constant that satisfies this property for all n × n matrices is called a Grothendieck constant and denoted
, depending on whether one works with real or complex numbers, respectively.
defines a linear operator between the normed spaces
is by solving the following quadratic integer program:
One can then ask the following natural question: How well does an optimal solution to the semidefinite program approximate
The Grothendieck inequality provides an answer to this question: There exists a fixed constant
are easily seen to be increasing, and Grothendieck's result states that they are bounded,[2][3] so they have limits.
, conjecturing that the upper bound is tight.
However, this conjecture was disproved by Braverman et al.
[6] Boris Tsirelson showed that the Grothendieck constants
play an essential role in the problem of quantum nonlocality: the Tsirelson bound of any full correlation bipartite Bell inequality for a quantum system of dimension d is upperbounded by
is defined by The notion of cut norm is essential in designing efficient approximation algorithms for dense graphs and matrices.
is defined by This generalized definition of cut norm is crucial in the study of the space of graphons, and the two definitions of cut norm can be linked via the adjacency matrix of a graph.
An application of the Grothendieck inequality is to give an efficient algorithm for approximating the cut norm of a given real matrix
real matrix, one can find a number
[19] This approximation algorithm uses semidefinite programming.
form a maximizer for the cut norm of
form a maximizer for the cut norm of
Now it suffices to design an efficient algorithm for approximating
in time that is polynomial in the program description size and
Szemerédi's regularity lemma is a useful tool in graph theory, asserting (informally) that any graph can be partitioned into a controlled number of pieces that interact with each other in a pseudorandom way.
Another application of the Grothendieck inequality is to produce a partition of the vertex set that satisfies the conclusion of Szemerédi's regularity lemma, via the cut norm estimation algorithm, in time that is polynomial in the upper bound of Szemerédi's regular partition size but independent of the number of vertices in the graph.
[20] It turns out that the main "bottleneck" of constructing a Szemeredi's regular partition in polynomial time is to determine in polynomial time whether or not a given pair
It follows that using the cut norm approximation algorithm together with the rounding technique, one can find in polynomial time
Then the algorithm for producing a Szemerédi's regular partition follows from the constructive argument of Alon et al.[22] The Grothendieck inequality of a graph states that for each
[28][29][23] In the application of the Grothendieck inequality for approximating the cut norm, we have seen that the Grothendieck inequality answers the following question: How well does an optimal solution to the semidefinite program
, which can be viewed as an optimization problem over the unit cube?
More generally, we can ask similar questions over convex bodies other than the unit cube.