In mathematics, the Grothendieck inequality 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 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, 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

. The -norm is the quantity

.

.

is by solving the following quadratic integer program:

and by the triangle inequality. This quadratic integer program can be relaxed to the following semidefinite program:

is NP-hard is NP-hard.

One can then ask the following natural question: How well does an optimal solution to the semidefinite program,

Bounds on the constants

are easily seen to be increasing, and Grothendieck's result states that they are bounded, so they have limits.

.

, conjecturing that it is tight. However, this conjecture was disproved by ..

by . This was shown not to be optimal by and .

by in .

Grothendieck constant of order d

Boris Tsirelson 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.

Lower bounds

is summarized in the following table.

Upper bounds

:

Applications

Cut norm estimation

, the cut norm 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 so that the cut norm 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.

such that

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

matrix defined by

, then

, where

.

. We consider the following semidefinite program:

. Many algorithms (such as interior-point methods, first-order methods, the bundle method, the augmented Lagrangian method. 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.

is close to being -regular, we have

, defined by

,

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 satisfies that

The Grothendieck constant of a graph that satisfies the above property.

is a bipartite graph as its bipartition classes. Thus,

-vertex complete graph becomes

. by the Cauchy-Schwarz inequality:

is due to Alon, Makarychev, Makarychev and Naor in 2006.

. It is known that

and

is the clique number, and

is known as the Lovász theta function.

L^p Grothendieck inequality

, 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:,

where

is sharp in the inequality. Stirling's formula.

See also

• Pisier–Ringrose inequality

References

External links

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