In mathematics, the Grothendieck inequality states that there is a universal constant  with the following property. 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 . In fact, there are two Grothendieck constants,  and , depending on whether one works with real or complex numbers, respectively.

The Grothendieck inequality and Grothendieck constants are named after Alexander Grothendieck, who proved the existence of the constants in a paper published in 1953.

Motivation and the operator formulation 
Let  be an  matrix. Then  defines a linear operator between the normed spaces  and  for . The -norm of  is the quantity

If , we denote the norm by .

One can consider the following question: For what value of  and  is  maximized? Since  is linear, then it suffices to consider  such that  contains as many points as possible, and also  such that  is as large as possible. By comparing  for , one sees that  for all .

One way to compute  is by solving the following quadratic integer program:

To see this, note that , and taking the maximum over  gives . Then taking the maximum over  gives  by the convexity of  and by the triangle inequality. This quadratic integer program can be relaxed to the following semidefinite program:

It is known that exactly computing  for  is NP-hard, while exacting computing  is NP-hard for .

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  such that, for any , for any  matrix , and for any Hilbert space ,

Bounds on the constants
The sequences  and  are easily seen to be increasing, and Grothendieck's result states that they are bounded, so they have limits.

Grothendieck proved that  where  is defined to be .

 improved the result by proving that , conjecturing that the upper bound is tight. However, this conjecture was disproved by .

Grothendieck constant of order d

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 .

Lower bounds

Some historical data on best known lower bounds of  is summarized in the following table.

Upper bounds

Some historical data on best known upper bounds of :

Applications

Cut norm estimation 
Given an  real matrix , the cut norm of  is defined by

 

The notion of cut norm is essential in designing efficient approximation algorithms for dense graphs and matrices. More generally, the definition of cut norm can be generalized for symmetric measurable functions  so that the cut norm of  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 ; specifically, given an  real matrix, one can find a number  such that

where  is an absolute constant. This approximation algorithm uses semidefinite programming.

We give a sketch of this approximation algorithm. Let  be  matrix defined by

One can verify that  by observing, if  form a maximizer for the cut norm of , then

form a maximizer for the cut norm of . Next, one can verify that , where

Although not important in this proof,  can be interpreted to be the norm of  when viewed as a linear operator from  to .

Now it suffices to design an efficient algorithm for approximating . We consider the following semidefinite program:

Then . The Grothedieck inequality implies that . Many algorithms (such as interior-point methods, first-order methods, the bundle method, the augmented Lagrangian method) are known to output the value of a semidefinite program up to an additive error  in time that is polynomial in the program description size and . Therefore, one can output  which satisfies

Szemerédi's regularity lemma 
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.

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  is close to being -regular, meaning that for all  with , we have

where  for all  and  are the vertex and edge sets of the graph, respectively. To that end, we construct an  matrix , where , defined by

Then for all ,

Hence, if  is not -regular, then . It follows that using the cut norm approximation algorithm together with the rounding technique, one can find in polynomial time  such that

Then the algorithm for producing a Szemerédi's regular partition follows from the constructive argument of Alon et al.

Variants of the Grothendieck inequality

Grothendieck inequality of a graph 
The Grothendieck inequality of a graph states that for each  and for each graph  without self loops, there exists a universal constant  such that every  matrix  satisfies that

The Grothendieck constant of a graph , denoted , is defined to be the smallest constant  that satisfies the above property.

The Grothendieck inequality of a graph is an extension of the Grothendieck inequality because the former inequality is the special case of the latter inequality when  is a bipartite graph with two copies of  as its bipartition classes. Thus,

For , the -vertex complete graph, the Grothendieck inequality of  becomes

It turns out that . On one hand, we have . Indeed, the following inequality is true for any  matrix , which implies that  by the Cauchy-Schwarz inequality:

On the other hand, the matching lower bound  is due to Alon, Makarychev, Makarychev and Naor in 2006.

The Grothendieck inequality  of a graph  depends upon the structure of . It is known that

and

where  is the clique number of , i.e., the largest  such that there exists  with  such that  for all distinct , and

The parameter  is known as the Lovász theta function of the complement of .

L^p Grothendieck inequality 
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  approximate , 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.

For instance, the following inequality is due to Naor and Schechtman and independently due to Guruswami et al: For every  matrix  and every ,

where

The constant  is sharp in the inequality. Stirling's formula implies that  as .

See also
Pisier–Ringrose inequality

References

External links
 (NB: the historical part is not exact there.)

Theorems in functional analysis
Inequalities