In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, the Grothendieck inequality states that there is a universal constant
with the following property. If ''M''
''ij'' is an ''n'' × ''n'' (
real
Real may refer to:
Currencies
* Argentine real
* Brazilian real (R$)
* Central American Republic real
* Mexican real
* Portuguese real
* Spanish real
* Spanish colonial real
Nature and science
* Reality, the state of things as they exist, rathe ...
or
complex
Complex commonly refers to:
* Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe
** Complex system, a system composed of many components which may interact with each ...
)
matrix
Matrix (: matrices or matrixes) or MATRIX may refer to:
Science and mathematics
* Matrix (mathematics), a rectangular array of numbers, symbols or expressions
* Matrix (logic), part of a formula in prenex normal form
* Matrix (biology), the m ...
with
:
for all (real or complex) numbers ''s''
''i'', ''t''
''j'' of absolute value at most 1, then
:
for all
vectors ''S''
''i'', ''T''
''j'' in the
unit ball
Unit may refer to:
General measurement
* Unit of measurement, a definite magnitude of a physical quantity, defined and adopted by convention or by law
**International System of Units (SI), modern form of the metric system
**English units, histo ...
''B''(''H'') of a (real or complex)
Hilbert space
In mathematics, a Hilbert space is a real number, real or complex number, complex inner product space that is also a complete metric space with respect to the metric induced by the inner product. It generalizes the notion of Euclidean space. The ...
''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
Alexander Grothendieck, later Alexandre Grothendieck in French (; ; ; 28 March 1928 – 13 November 2014), was a German-born French mathematician who became the leading figure in the creation of modern algebraic geometry. His research ext ...
, 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
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
, while exacting computing
is
NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
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
Limit or Limits may refer to:
Arts and media
* ''Limit'' (manga), a manga by Keiko Suenobu
* ''Limit'' (film), a South Korean film
* Limit (music), a way to characterize harmony
* "Limit" (song), a 2016 single by Luna Sea
* "Limits", a 2009 ...
.
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
In theoretical physics, quantum nonlocality refers to the phenomenon by which the measurement statistics of a multipartite quantum system do not allow an interpretation with local realism. Quantum nonlocality has been experimentally verified unde ...
: the
Tsirelson bound of any full correlation bipartite
Bell inequality
Bell's theorem is a term encompassing a number of closely related results in physics, all of which determine that quantum mechanics is incompatible with local hidden-variable theories, given some basic assumptions about the nature of measuremen ...
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
In mathematics, the concept of a measure is a generalization and formalization of geometrical measures (length, area, volume) and other common notions, such as magnitude, mass, and probability of events. These seemingly distinct concepts hav ...
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
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...
of a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discret ...
.
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
Semidefinite programming (SDP) is a subfield of mathematical programming concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize)
over the intersection of the cone of po ...
.
We give a sketch of this approximation algorithm. Let
be
matrix defined by
One can verify that
by observing, if