In
mathematics , the Grothendieck inequality states that there is a universal constant
K
G
{\displaystyle K_{G}}
with the following property. If M ij is an n × n (
real or
complex )
matrix with
|
∑
i
,
j
M
i
j
s
i
t
j
|
≤
1
{\displaystyle {\Big |}\sum _{i,j}M_{ij}s_{i}t_{j}{\Big |}\leq 1}
for all (real or complex) numbers s i , t j of absolute value at most 1, then
|
∑
i
,
j
M
i
j
⟨
S
i
,
T
j
⟩
|
≤
K
G
{\displaystyle {\Big |}\sum _{i,j}M_{ij}\langle S_{i},T_{j}\rangle {\Big |}\leq K_{G}}
for all
vectors S i , T j in the
unit ball B (H ) of a (real or complex)
Hilbert space H , the constant
K
G
{\displaystyle K_{G}}
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
K
G
(
d
)
{\displaystyle K_{G}(d)}
. In fact, there are two Grothendieck constants,
K
G
R
(
d
)
{\displaystyle K_{G}^{\mathbb {R} }(d)}
and
K
G
C
(
d
)
{\displaystyle K_{G}^{\mathbb {C} }(d)}
, depending on whether one works with real or complex numbers, respectively.
[1]
The Grothendieck inequality and Grothendieck constants are named after
Alexander Grothendieck , who proved the existence of the constants in a paper published in 1953.
[2]
Motivation and the operator formulation
Let
A
=
(
a
i
j
)
{\displaystyle A=(a_{ij})}
be an
m
×
n
{\displaystyle m\times n}
matrix. Then
A
{\displaystyle A}
defines a linear operator between the normed spaces
(
R
m
,
‖
⋅
‖
p
)
{\displaystyle (\mathbb {R} ^{m},\|\cdot \|_{p})}
and
(
R
n
,
‖
⋅
‖
q
)
{\displaystyle (\mathbb {R} ^{n},\|\cdot \|_{q})}
for
1
≤
p
,
q
≤
∞
{\displaystyle 1\leq p,q\leq \infty }
. The
(
p
→
q
)
{\displaystyle (p\to q)}
-norm of
A
{\displaystyle A}
is the quantity
‖
A
‖
p
→
q
=
max
x
∈
R
n
:
‖
x
‖
p
=
1
‖
A
x
‖
q
.
{\displaystyle \|A\|_{p\to q}=\max _{x\in \mathbb {R} ^{n}:\|x\|_{p}=1}\|Ax\|_{q}.}
If
p
=
q
{\displaystyle p=q}
, we denote the norm by
‖
A
‖
p
{\displaystyle \|A\|_{p}}
.
One can consider the following question: For what value of
p
{\displaystyle p}
and
q
{\displaystyle q}
is
‖
A
‖
p
→
q
{\displaystyle \|A\|_{p\to q}}
maximized? Since
A
{\displaystyle A}
is linear, then it suffices to consider
p
{\displaystyle p}
such that
{
x
∈
R
n
:
‖
x
‖
p
≤
1
}
{\displaystyle \{x\in \mathbb {R} ^{n}:\|x\|_{p}\leq 1\}}
contains as many points as possible, and also
q
{\displaystyle q}
such that
‖
A
x
‖
q
{\displaystyle \|Ax\|_{q}}
is as large as possible. By comparing
‖
x
‖
p
{\displaystyle \|x\|_{p}}
for
p
=
1
,
2
,
…
,
∞
{\displaystyle p=1,2,\ldots ,\infty }
, one sees that
‖
A
‖
∞
→
1
≥
‖
A
‖
p
→
q
{\displaystyle \|A\|_{\infty \to 1}\geq \|A\|_{p\to q}}
for all
1
≤
p
,
q
≤
∞
{\displaystyle 1\leq p,q\leq \infty }
.
One way to compute
‖
A
‖
∞
→
1
{\displaystyle \|A\|_{\infty \to 1}}
is by solving the following quadratic
integer program :
max
∑
i
,
j
A
i
j
x
i
y
j
s.t.
(
x
,
y
)
∈
{
−
1
,
1
}
m
+
n
{\displaystyle {\begin{aligned}\max &\qquad \sum _{i,j}A_{ij}x_{i}y_{j}\\{\text{s.t.}}&\qquad (x,y)\in \{-1,1\}^{m+n}\end{aligned}}}
To see this, note that
∑
i
,
j
A
i
j
x
i
y
j
=
∑
i
(
A
y
)
i
x
i
{\displaystyle \sum _{i,j}A_{ij}x_{i}y_{j}=\sum _{i}(Ay)_{i}x_{i}}
, and taking the maximum over
x
∈
{
−
1
,
1
}
m
{\displaystyle x\in \{-1,1\}^{m}}
gives
‖
A
y
‖
1
{\displaystyle \|Ay\|_{1}}
. Then taking the maximum over
y
∈
{
−
1
,
1
}
n
{\displaystyle y\in \{-1,1\}^{n}}
gives
‖
A
‖
∞
→
1
{\displaystyle \|A\|_{\infty \to 1}}
by the convexity of
{
x
∈
R
m
:
‖
x
‖
∞
=
1
}
{\displaystyle \{x\in \mathbb {R} ^{m}:\|x\|_{\infty }=1\}}
and by the triangle inequality. This quadratic integer program can be relaxed to the following
semidefinite program :
max
∑
i
,
j
A
i
j
⟨
x
(
i
)
,
y
(
j
)
⟩
s.t.
x
(
1
)
,
…
,
x
(
m
)
,
y
(
1
)
,
…
,
y
(
n
)
are unit vectors in
(
R
d
,
‖
⋅
‖
2
)
{\displaystyle {\begin{aligned}\max &\qquad \sum _{i,j}A_{ij}\langle x^{(i)},y^{(j)}\rangle \\{\text{s.t.}}&\qquad x^{(1)},\ldots ,x^{(m)},y^{(1)},\ldots ,y^{(n)}{\text{ are unit vectors in }}(\mathbb {R} ^{d},\|\cdot \|_{2})\end{aligned}}}
It is known that exactly computing
‖
A
‖
p
→
q
{\displaystyle \|A\|_{p\to q}}
for
1
≤
q
<
p
≤
∞
{\displaystyle 1\leq q<p\leq \infty }
is
NP-hard , while exacting computing
‖
A
‖
p
{\displaystyle \|A\|_{p}}
is
NP-hard for
p
∉
{
1
,
2
,
∞
}
{\displaystyle p\not \in \{1,2,\infty \}}
.
One can then ask the following natural question: How well does an optimal solution to the
semidefinite program approximate
‖
A
‖
∞
→
1
{\displaystyle \|A\|_{\infty \to 1}}
? The Grothendieck inequality provides an answer to this question: There exists a fixed constant
C
>
0
{\displaystyle C>0}
such that, for any
m
,
n
≥
1
{\displaystyle m,n\geq 1}
, for any
m
×
n
{\displaystyle m\times n}
matrix
A
{\displaystyle A}
, and for any Hilbert space
H
{\displaystyle H}
,
max
x
(
i
)
,
y
(
i
)
∈
H
unit vectors
∑
i
,
j
A
i
j
⟨
x
(
i
)
,
y
(
j
)
⟩
H
≤
C
‖
A
‖
∞
→
1
.
{\displaystyle \max _{x^{(i)},y^{(i)}\in H{\text{ unit vectors}}}\sum _{i,j}A_{ij}\left\langle x^{(i)},y^{(j)}\right\rangle _{H}\leq C\|A\|_{\infty \to 1}.}
Bounds on the constants
The sequences
K
G
R
(
d
)
{\displaystyle K_{G}^{\mathbb {R} }(d)}
and
K
G
C
(
d
)
{\displaystyle K_{G}^{\mathbb {C} }(d)}
are easily seen to be increasing, and Grothendieck's result states that they are
bounded ,
[2]
[3] so they have
limits .
Grothendieck proved that
1.57
≈
π
2
≤
K
G
R
≤
sinh
π
2
≈
2.3
,
{\displaystyle 1.57\approx {\frac {\pi }{2}}\leq K_{G}^{\mathbb {R} }\leq \operatorname {sinh} {\frac {\pi }{2}}\approx 2.3,}
where
K
G
R
{\displaystyle K_{G}^{\mathbb {R} }}
is defined to be
sup
d
K
G
R
(
d
)
{\displaystyle \sup _{d}K_{G}^{\mathbb {R} }(d)}
.
[4]
Krivine (1979)
[5] improved the result by proving that
K
G
R
≤
π
2
ln
(
1
+
2
)
≈
1.7822
{\displaystyle K_{G}^{\mathbb {R} }\leq {\frac {\pi }{2\ln(1+{\sqrt {2}})}}\approx 1.7822}
, conjecturing that the upper bound is tight. However, this conjecture was disproved by
Braverman et al. (2011) .
[6]
Grothendieck constant of order d
Boris Tsirelson showed that the Grothendieck constants
K
G
R
(
d
)
{\displaystyle K_{G}^{\mathbb {R} }(d)}
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
K
G
R
(
2
d
2
)
{\displaystyle K_{G}^{\mathbb {R} }(2d^{2})}
.
[7]
[8]
Lower bounds
Some historical data on best known lower bounds of
K
G
R
(
d
)
{\displaystyle K_{G}^{\mathbb {R} }(d)}
is summarized in the following table.
d
Grothendieck, 1953
[2]
Krivine, 1979
[5]
Davie, 1984
[9]
Fishburn et al., 1994
[10]
Vértesi, 2008
[11]
Briët et al., 2011
[12]
Hua et al., 2015
[13]
Diviánszky et al., 2017
[14]
Designolle et al., 2023
[15]
2
2
{\displaystyle {\sqrt {2}}}
≈ 1.41421
3
1.41724
1.41758
1.4359
1.4367
4
1.44521
1.44566
1.4841
5
10
7
{\displaystyle {\frac {10}{7}}}
≈ 1.42857
1.46007
1.46112
6
1.47017
7
1.46286
1.47583
8
1.47586
1.47972
9
1.48608
∞
π
2
{\displaystyle {\frac {\pi }{2}}}
≈ 1.57079
1.67696
Upper bounds
Some historical data on best known upper bounds of
K
G
R
(
d
)
{\displaystyle K_{G}^{\mathbb {R} }(d)}
:
d
Grothendieck, 1953
[2]
Rietz, 1974
[16]
Krivine, 1979
[5]
Braverman et al., 2011
[6]
Hirsch et al., 2016
[17]
Designolle et al., 2023
[15]
2
2
{\displaystyle {\sqrt {2}}}
≈ 1.41421
3
1.5163
1.4644
1.4546
4
π
2
{\displaystyle {\frac {\pi }{2}}}
≈ 1.5708
8
1.6641
∞
sinh
π
2
{\displaystyle \operatorname {sinh} {\frac {\pi }{2}}}
≈ 2.30130
2.261
π
2
ln
(
1
+
2
)
{\displaystyle {\frac {\pi }{2\ln(1+{\sqrt {2}})}}}
≈ 1.78221
π
2
ln
(
1
+
2
)
−
ε
{\displaystyle {\frac {\pi }{2\ln(1+{\sqrt {2}})}}-\varepsilon }
Applications
Cut norm estimation
Given an
m
×
n
{\displaystyle m\times n}
real matrix
A
=
(
a
i
j
)
{\displaystyle A=(a_{ij})}
, the cut norm of
A
{\displaystyle A}
is defined by
‖
A
‖
◻
=
max
S
⊂
m
,
T
⊂
n
|
∑
i
∈
S
,
j
∈
T
a
i
j
|
.
{\displaystyle \|A\|_{\square }=\max _{S\subset [m],T\subset [n]}\left|\sum _{i\in S,j\in T}a_{ij}\right|.}
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
W
:
0
,
1
2
→
R
{\displaystyle W:[0,1]^{2}\to \mathbb {R} }
so that the cut norm of
W
{\displaystyle W}
is defined by
‖
W
‖
◻
=
sup
S
,
T
⊂
0
,
1
|
∫
S
×
T
W
|
.
{\displaystyle \|W\|_{\square }=\sup _{S,T\subset [0,1]}\left|\int _{S\times T}W\right|.}
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
A
{\displaystyle A}
; specifically, given an
m
×
n
{\displaystyle m\times n}
real matrix, one can find a number
α
{\displaystyle \alpha }
such that
‖
A
‖
◻
≤
α
≤
C
‖
A
‖
◻
,
{\displaystyle \|A\|_{\square }\leq \alpha \leq C\|A\|_{\square },}
where
C
{\displaystyle C}
is an absolute constant.
[18] This approximation algorithm uses
semidefinite programming .
We give a sketch of this approximation algorithm. Let
B
=
(
b
i
j
)
{\displaystyle B=(b_{ij})}
be
(
m
+
1
)
×
(
n
+
1
)
{\displaystyle (m+1)\times (n+1)}
matrix defined by
(
a
11
a
12
…
a
1
n
−
∑
k
=
1
n
a
1
k
a
21
a
22
…
a
2
n
−
∑
k
=
1
n
a
2
k
⋮
⋮
⋱
⋮
⋮
a
m
1
a
m
2
…
a
m
n
−
∑
k
=
1
n
a
m
k
−
∑
ℓ
=
1
m
a
ℓ
1
−
∑
ℓ
=
1
m
a
ℓ
2
…
−
∑
ℓ
=
1
m
a
ℓ
n
∑
k
=
1
n
∑
ℓ
=
1
m
a
ℓ
k
)
.
{\displaystyle {\begin{pmatrix}a_{11}&a_{12}&\ldots &a_{1n}&-\sum _{k=1}^{n}a_{1k}\\a_{21}&a_{22}&\ldots &a_{2n}&-\sum _{k=1}^{n}a_{2k}\\\vdots &\vdots &\ddots &\vdots &\vdots \\a_{m1}&a_{m2}&\ldots &a_{mn}&-\sum _{k=1}^{n}a_{mk}\\-\sum _{\ell =1}^{m}a_{\ell 1}&-\sum _{\ell =1}^{m}a_{\ell 2}&\ldots &-\sum _{\ell =1}^{m}a_{\ell n}&\sum _{k=1}^{n}\sum _{\ell =1}^{m}a_{\ell k}\end{pmatrix}}.}
One can verify that
‖
A
‖
◻
=
‖
B
‖
◻
{\displaystyle \|A\|_{\square }=\|B\|_{\square }}
by observing, if
S
∈
m
+
1
,
T
∈
n
+
1
{\displaystyle S\in [m+1],T\in [n+1]}
form a maximizer for the cut norm of
B
{\displaystyle B}
, then
S
∗
=
{
S
,
if
m
+
1
∉
S
,
m
∖
S
,
otherwise
,
T
∗
=
{
T
,
if
n
+
1
∉
T
,
n
∖
S
,
otherwise
,
{\displaystyle S^{*}={\begin{cases}S,&{\text{if }}m+1\not \in S,\\{[m]}\setminus S,&{\text{otherwise}},\end{cases}}\qquad T^{*}={\begin{cases}T,&{\text{if }}n+1\not \in T,\\{[n]}\setminus S,&{\text{otherwise}},\end{cases}}\qquad }
form a maximizer for the cut norm of
A
{\displaystyle A}
. Next, one can verify that
‖
B
‖
◻
=
‖
B
‖
∞
→
1
/
4
{\displaystyle \|B\|_{\square }=\|B\|_{\infty \to 1}/4}
, where
‖
B
‖
∞
→
1
=
max
{
∑
i
=
1
m
+
1
∑
j
=
1
n
+
1
b
i
j
ε
i
δ
j
:
ε
1
,
…
,
ε
m
+
1
∈
{
−
1
,
1
}
,
δ
1
,
…
,
δ
n
+
1
∈
{
−
1
,
1
}
}
.
{\displaystyle \|B\|_{\infty \to 1}=\max \left\{\sum _{i=1}^{m+1}\sum _{j=1}^{n+1}b_{ij}\varepsilon _{i}\delta _{j}:\varepsilon _{1},\ldots ,\varepsilon _{m+1}\in \{-1,1\},\delta _{1},\ldots ,\delta _{n+1}\in \{-1,1\}\right\}.}
[19]
Although not important in this proof,
‖
B
‖
∞
→
1
{\displaystyle \|B\|_{\infty \to 1}}
can be interpreted to be the norm of
B
{\displaystyle B}
when viewed as a linear operator from
ℓ
∞
m
{\displaystyle \ell _{\infty }^{m}}
to
ℓ
1
m
{\displaystyle \ell _{1}^{m}}
.
Now it suffices to design an efficient algorithm for approximating
‖
A
‖
∞
→
1
{\displaystyle \|A\|_{\infty \to 1}}
. We consider the following
semidefinite program :
SDP
(
A
)
=
max
{
∑
i
=
1
m
∑
j
=
1
n
a
i
j
⟨
x
i
,
y
j
⟩
:
x
1
,
…
,
x
m
,
y
1
,
…
,
y
n
∈
S
n
+
m
−
1
}
.
{\displaystyle {\text{SDP}}(A)=\max \left\{\sum _{i=1}^{m}\sum _{j=1}^{n}a_{ij}\left\langle x_{i},y_{j}\right\rangle :x_{1},\ldots ,x_{m},y_{1},\ldots ,y_{n}\in S^{n+m-1}\right\}.}
Then
SDP
(
A
)
≥
‖
A
‖
∞
→
1
{\displaystyle {\text{SDP}}(A)\geq \|A\|_{\infty \to 1}}
. The Grothedieck inequality implies that
SDP
(
A
)
≤
K
G
R
‖
A
‖
∞
→
1
{\displaystyle {\text{SDP}}(A)\leq K_{G}^{\mathbb {R} }\|A\|_{\infty \to 1}}
. 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
ε
{\displaystyle \varepsilon }
in time that is polynomial in the program description size and
log
(
1
/
ε
)
{\displaystyle \log(1/\varepsilon )}
.
[20] Therefore, one can output
α
=
SDP
(
B
)
{\displaystyle \alpha ={\text{SDP}}(B)}
which satisfies
‖
A
‖
◻
≤
α
≤
C
‖
A
‖
◻
with
C
=
K
G
R
.
{\displaystyle \|A\|_{\square }\leq \alpha \leq C\|A\|_{\square }\qquad {\text{with}}\qquad C=K_{G}^{\mathbb {R} }.}
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.
[19]
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
(
X
,
Y
)
{\displaystyle (X,Y)}
is close to being
ε
{\displaystyle \varepsilon }
-regular , meaning that for all
S
⊂
X
,
T
⊂
Y
{\displaystyle S\subset X,T\subset Y}
with
|
S
|
≥
ε
|
X
|
,
|
T
|
≥
ε
|
Y
|
{\displaystyle |S|\geq \varepsilon |X|,|T|\geq \varepsilon |Y|}
, we have
|
e
(
S
,
T
)
|
S
|
|
T
|
−
e
(
X
,
Y
)
|
X
|
|
Y
|
|
≤
ε
,
{\displaystyle \left|{\frac {e(S,T)}{|S||T|}}-{\frac {e(X,Y)}{|X||Y|}}\right|\leq \varepsilon ,}
where
e
(
X
′
,
Y
′
)
=
|
{
(
u
,
v
)
∈
X
′
×
Y
′
:
u
v
∈
E
}
|
{\displaystyle e(X',Y')=|\{(u,v)\in X'\times Y':uv\in E\}|}
for all
X
′
,
Y
′
⊂
V
{\displaystyle X',Y'\subset V}
and
V
,
E
{\displaystyle V,E}
are the vertex and edge sets of the graph, respectively. To that end, we construct an
n
×
n
{\displaystyle n\times n}
matrix
A
=
(
a
x
y
)
(
x
,
y
)
∈
X
×
Y
{\displaystyle A=(a_{xy})_{(x,y)\in X\times Y}}
, where
n
=
|
V
|
{\displaystyle n=|V|}
, defined by
a
x
y
=
{
1
−
e
(
X
,
Y
)
|
X
|
|
Y
|
,
if
x
y
∈
E
,
−
e
(
X
,
Y
)
|
X
|
|
Y
|
,
otherwise
.
{\displaystyle a_{xy}={\begin{cases}1-{\frac {e(X,Y)}{|X||Y|}},&{\text{if }}xy\in E,\\-{\frac {e(X,Y)}{|X||Y|}},&{\text{otherwise}}.\end{cases}}}
Then for all
S
⊂
X
,
T
⊂
Y
{\displaystyle S\subset X,T\subset Y}
,
|
∑
x
∈
S
,
y
∈
T
a
x
y
|
=
|
S
|
|
T
|
|
e
(
S
,
T
)
|
S
|
|
T
|
−
e
(
X
,
Y
)
|
X
|
|
Y
|
|
.
{\displaystyle \left|\sum _{x\in S,y\in T}a_{xy}\right|=|S||T|\left|{\frac {e(S,T)}{|S||T|}}-{\frac {e(X,Y)}{|X||Y|}}\right|.}
Hence, if
(
X
,
Y
)
{\displaystyle (X,Y)}
is not
ε
{\displaystyle \varepsilon }
-regular, then
‖
A
‖
◻
≥
ε
3
n
2
{\displaystyle \|A\|_{\square }\geq \varepsilon ^{3}n^{2}}
. It follows that using the cut norm approximation algorithm together with the rounding technique, one can find in polynomial time
S
⊂
X
,
T
⊂
Y
{\displaystyle S\subset X,T\subset Y}
such that
min
{
n
|
S
|
,
n
|
T
|
,
n
2
|
e
(
S
,
T
)
|
S
|
|
T
|
−
e
(
X
,
Y
)
|
X
|
|
Y
|
|
}
≥
|
∑
x
∈
S
,
y
∈
T
a
x
y
|
≥
1
K
G
R
ε
3
n
2
≥
1
2
ε
3
n
2
.
{\displaystyle \min \left\{n|S|,n|T|,n^{2}\left|{\frac {e(S,T)}{|S||T|}}-{\frac {e(X,Y)}{|X||Y|}}\right|\right\}\geq \left|\sum _{x\in S,y\in T}a_{xy}\right|\geq {\frac {1}{K_{G}^{\mathbb {R} }}}\varepsilon ^{3}n^{2}\geq {\frac {1}{2}}\varepsilon ^{3}n^{2}.}
Then the algorithm for producing a Szemerédi's regular partition follows from the constructive argument of Alon et al.
[21]
Variants of the Grothendieck inequality
Grothendieck inequality of a graph
The Grothendieck inequality of a graph states that for each
n
∈
N
{\displaystyle n\in \mathbb {N} }
and for each graph
G
=
(
{
1
,
…
,
n
}
,
E
)
{\displaystyle G=(\{1,\ldots ,n\},E)}
without self loops, there exists a universal constant
K
>
0
{\displaystyle K>0}
such that every
n
×
n
{\displaystyle n\times n}
matrix
A
=
(
a
i
j
)
{\displaystyle A=(a_{ij})}
satisfies that
max
x
1
,
…
,
x
n
∈
S
n
−
1
∑
i
j
∈
E
a
i
j
⟨
x
i
,
x
j
⟩
≤
K
max
ε
1
,
…
,
ε
n
∈
{
−
1
,
1
}
∑
i
j
∈
E
a
i
j
ε
1
ε
n
.
{\displaystyle \max _{x_{1},\ldots ,x_{n}\in S^{n-1}}\sum _{ij\in E}a_{ij}\left\langle x_{i},x_{j}\right\rangle \leq K\max _{\varepsilon _{1},\ldots ,\varepsilon _{n}\in \{-1,1\}}\sum _{ij\in E}a_{ij}\varepsilon _{1}\varepsilon _{n}.}
[22]
The Grothendieck constant of a graph
G
{\displaystyle G}
, denoted
K
(
G
)
{\displaystyle K(G)}
, is defined to be the smallest constant
K
{\displaystyle K}
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
G
{\displaystyle G}
is a
bipartite graph with two copies of
{
1
,
…
,
n
}
{\displaystyle \{1,\ldots ,n\}}
as its bipartition classes. Thus,
K
G
=
sup
n
∈
N
{
K
(
G
)
:
G
is an
n
-vertex bipartite graph
}
.
{\displaystyle K_{G}=\sup _{n\in \mathbb {N} }\{K(G):G{\text{ is an }}n{\text{-vertex bipartite graph}}\}.}
For
G
=
K
n
{\displaystyle G=K_{n}}
, the
n
{\displaystyle n}
-vertex complete graph, the Grothendieck inequality of
G
{\displaystyle G}
becomes
max
x
1
,
…
,
x
n
∈
S
n
−
1
∑
i
,
j
∈
{
1
,
…
,
n
}
,
i
≠
j
a
i
j
⟨
x
i
,
x
j
⟩
≤
K
(
K
n
)
max
ε
1
,
…
,
ε
n
∈
{
−
1
,
1
}
∑
i
,
j
∈
{
1
,
…
,
n
}
,
i
≠
j
a
i
j
ε
i
ε
j
.
{\displaystyle \max _{x_{1},\ldots ,x_{n}\in S^{n-1}}\sum _{i,j\in \{1,\ldots ,n\},i\neq j}a_{ij}\left\langle x_{i},x_{j}\right\rangle \leq K(K_{n})\max _{\varepsilon _{1},\ldots ,\varepsilon _{n}\in \{-1,1\}}\sum _{i,j\in \{1,\ldots ,n\},i\neq j}a_{ij}\varepsilon _{i}\varepsilon _{j}.}
It turns out that
K
(
K
n
)
≍
log
n
{\displaystyle K(K_{n})\asymp \log n}
. On one hand, we have
K
(
K
n
)
≲
log
n
{\displaystyle K(K_{n})\lesssim \log n}
.
[23]
[24]
[25] Indeed, the following inequality is true for any
n
×
n
{\displaystyle n\times n}
matrix
A
=
(
a
i
j
)
{\displaystyle A=(a_{ij})}
, which implies that
K
(
K
n
)
≲
log
n
{\displaystyle K(K_{n})\lesssim \log n}
by the
Cauchy-Schwarz inequality :
[22]
max
x
1
,
…
,
x
n
∈
S
n
−
1
∑
i
,
j
∈
{
1
,
…
,
n
}
,
i
≠
j
a
i
j
⟨
x
i
,
x
j
⟩
≤
log
(
∑
i
∈
{
1
,
…
,
n
}
∑
j
∈
{
1
,
…
,
n
}
∖
{
i
}
|
a
i
j
|
∑
i
∈
{
1
,
…
,
n
}
∑
j
∈
{
1
,
…
,
n
}
∖
{
i
}
a
i
j
2
)
max
ε
1
,
…
,
ε
n
∈
{
−
1
,
1
}
∑
i
,
j
∈
{
1
,
…
,
n
}
,
i
≠
j
a
i
j
ε
1
ε
n
.
{\displaystyle \max _{x_{1},\ldots ,x_{n}\in S^{n-1}}\sum _{i,j\in \{1,\ldots ,n\},i\neq j}a_{ij}\left\langle x_{i},x_{j}\right\rangle \leq \log \left({\frac {\sum _{i\in \{1,\ldots ,n\}}\sum _{j\in \{1,\ldots ,n\}\setminus \{i\}}|a_{ij}|}{\sqrt {\sum _{i\in \{1,\ldots ,n\}}\sum _{j\in \{1,\ldots ,n\}\setminus \{i\}}a_{ij}^{2}}}}\right)\max _{\varepsilon _{1},\ldots ,\varepsilon _{n}\in \{-1,1\}}\sum _{i,j\in \{1,\ldots ,n\},i\neq j}a_{ij}\varepsilon _{1}\varepsilon _{n}.}
On the other hand, the matching lower bound
K
(
K
n
)
≳
log
n
{\displaystyle K(K_{n})\gtrsim \log n}
is due to
Alon , Makarychev, Makarychev and
Naor in 2006.
[22]
The Grothendieck inequality
K
(
G
)
{\displaystyle K(G)}
of a graph
G
{\displaystyle G}
depends upon the structure of
G
{\displaystyle G}
. It is known that
log
ω
≲
K
(
G
)
≲
log
ϑ
,
{\displaystyle \log \omega \lesssim K(G)\lesssim \log \vartheta ,}
[22]
and
K
(
G
)
≤
π
2
log
(
1
+
(
ϑ
−
1
)
2
+
1
ϑ
−
1
)
,
{\displaystyle K(G)\leq {\frac {\pi }{2\log \left({\frac {1+{\sqrt {(\vartheta -1)^{2}+1}}}{\vartheta -1}}\right)}},}
[26]
where
ω
{\displaystyle \omega }
is the
clique number of
G
{\displaystyle G}
, i.e., the largest
k
∈
{
2
,
…
,
n
}
{\displaystyle k\in \{2,\ldots ,n\}}
such that there exists
S
⊂
{
1
,
…
,
n
}
{\displaystyle S\subset \{1,\ldots ,n\}}
with
|
S
|
=
k
{\displaystyle |S|=k}
such that
i
j
∈
E
{\displaystyle ij\in E}
for all distinct
i
,
j
∈
S
{\displaystyle i,j\in S}
, and
ϑ
=
min
{
max
i
∈
{
1
,
…
,
n
}
1
⟨
x
i
,
y
⟩
:
x
1
,
…
,
x
n
,
y
∈
S
n
,
⟨
x
i
,
x
j
⟩
=
0
∀
i
j
∈
E
}
.
{\displaystyle \vartheta =\min \left\{\max _{i\in \{1,\ldots ,n\}}{\frac {1}{\langle x_{i},y\rangle }}:x_{1},\ldots ,x_{n},y\in S^{n},\left\langle x_{i},x_{j}\right\rangle =0\;\forall ij\in E\right\}.}
The parameter
ϑ
{\displaystyle \vartheta }
is known as the
Lovász theta function of the complement of
G
{\displaystyle G}
.
[27]
[28]
[22]
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
SDP
(
A
)
{\displaystyle {\text{SDP}}(A)}
approximate
‖
A
‖
∞
→
1
{\displaystyle \|A\|_{\infty \to 1}}
, 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
[29] and independently due to Guruswami et al:
[30] For every
n
×
n
{\displaystyle n\times n}
matrix
A
=
(
a
i
j
)
{\displaystyle A=(a_{ij})}
and every
p
≥
2
{\displaystyle p\geq 2}
,
max
x
1
,
…
,
x
n
∈
R
n
,
∑
k
=
1
n
‖
x
k
‖
2
p
≤
1
∑
i
=
1
n
∑
j
=
1
n
a
i
j
⟨
x
i
,
x
j
⟩
≤
γ
p
2
max
t
1
,
…
,
t
n
∈
R
,
∑
k
=
1
n
|
t
k
|
p
≤
1
∑
i
=
1
n
∑
j
=
1
n
a
i
j
t
i
t
j
,
{\displaystyle \max _{x_{1},\ldots ,x_{n}\in \mathbb {R} ^{n},\sum _{k=1}^{n}\|x_{k}\|_{2}^{p}\leq 1}\sum _{i=1}^{n}\sum _{j=1}^{n}a_{ij}\left\langle x_{i},x_{j}\right\rangle \leq \gamma _{p}^{2}\max _{t_{1},\ldots ,t_{n}\in \mathbb {R} ,\sum _{k=1}^{n}|t_{k}|^{p}\leq 1}\sum _{i=1}^{n}\sum _{j=1}^{n}a_{ij}t_{i}t_{j},}
where
γ
p
=
2
(
Γ
(
(
p
+
1
)
/
2
)
π
)
1
/
p
.
{\displaystyle \gamma _{p}={\sqrt {2}}\left({\frac {\Gamma ((p+1)/2)}{\sqrt {\pi }}}\right)^{1/p}.}
The constant
γ
p
2
{\displaystyle \gamma _{p}^{2}}
is sharp in the inequality.
Stirling's formula implies that
γ
p
2
=
p
/
e
+
O
(
1
)
{\displaystyle \gamma _{p}^{2}=p/e+O(1)}
as
p
→
∞
{\displaystyle p\to \infty }
.
See also
References
^
Pisier, Gilles (April 2012), "Grothendieck's Theorem, Past and Present",
Bulletin of the American Mathematical Society , 49 (2): 237–323,
arXiv :
1101.4195 ,
doi :
10.1090/S0273-0979-2011-01348-9 ,
S2CID
119162963 .
^
a
b
c
d
Grothendieck, Alexander (1953), "Résumé de la théorie métrique des produits tensoriels topologiques", Bol. Soc. Mat. Sao Paulo , 8 : 1–79,
MR
0094682 .
^ Blei, Ron C. (1987), "An elementary proof of the Grothendieck inequality",
Proceedings of the American Mathematical Society , 100 (1), American Mathematical Society: 58–60,
doi :
10.2307/2046119 ,
ISSN
0002-9939 ,
JSTOR
2046119 ,
MR
0883401 .
^ Finch, Steven R. (2003),
Mathematical constants ,
Cambridge University Press ,
ISBN
978-0-521-81805-6 .
^
a
b
c Krivine, J.-L. (1979), "Constantes de Grothendieck et fonctions de type positif sur les sphères",
Advances in Mathematics , 31 (1): 16–30,
doi :
10.1016/0001-8708(79)90017-3 ,
ISSN
0001-8708 ,
MR
0521464 .
^
a
b Braverman, Mark; Makarychev, Konstantin; Makarychev, Yury; Naor, Assaf (2011), "The Grothendieck Constant is Strictly Smaller than Krivine's Bound",
52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pp. 453–462,
arXiv :
1103.6161 ,
doi :
10.1109/FOCS.2011.77 ,
S2CID
7803437 .
^ Boris Tsirelson (1987).
"Quantum analogues of the Bell inequalities. The case of two spatially separated domains" (PDF) . Journal of Soviet Mathematics . 36 (4): 557–570.
doi :
10.1007/BF01663472 .
S2CID
119363229 .
^ Acín, Antonio; Gisin, Nicolas; Toner, Benjamin (2006), "Grothendieck's constant and local models for noisy entangled quantum states",
Physical Review A , 73 (6): 062105,
arXiv :
quant-ph/0606138 ,
Bibcode :
2006PhRvA..73f2105A ,
doi :
10.1103/PhysRevA.73.062105 ,
S2CID
2588399 .
^ Davie, A. M. (1984), Unpublished .
^ Fishburn, P. C.; Reeds, J. A. (1994), "Bell Inequalities, Grothendieck's Constant, and Root Two",
SIAM Journal on Discrete Mathematics , 7 (1): 48–56,
doi :
10.1137/S0895480191219350 .
^ Vértesi, Tamás (2008), "More efficient Bell inequalities for Werner states",
Physical Review A , 78 (3): 032112,
arXiv :
0806.0096 ,
Bibcode :
2008PhRvA..78c2112V ,
doi :
10.1103/PhysRevA.78.032112 ,
S2CID
119119134 .
^ Briët, Jop; Buhrman, Harry; Toner, Ben (2011), "A Generalized Grothendieck Inequality and Nonlocal Correlations that Require High Entanglement",
Communications in Mathematical Physics , 305 (3): 827,
Bibcode :
2011CMaPh.305..827B ,
doi :
10.1007/s00220-011-1280-3 .
^ Hua, Bobo; Li, Ming; Zhang, Tinggui; Zhou, Chunqin; Li-Jost, Xianqing; Fei, Shao-Ming (2015), "Towards Grothendieck Constants and LHV Models in Quantum Mechanics", Journal of Physics A: Mathematical and Theoretical , 48 (6),
Journal of Physics A : 065302,
arXiv :
1501.05507 ,
Bibcode :
2015JPhA...48f5302H ,
doi :
10.1088/1751-8113/48/6/065302 ,
S2CID
1082714 .
^ Diviánszky, Péter; Bene, Erika; Vértesi, Tamás (2017), "Qutrit witness from the Grothendieck constant of order four",
Physical Review A , 96 (1): 012113,
arXiv :
1707.04719 ,
Bibcode :
2017PhRvA..96a2113D ,
doi :
10.1103/PhysRevA.96.012113 ,
S2CID
119079607 .
^
a
b Sébastien Designolle; Gabriele Iommazzo; Mathieu Besançon; Sebastian Knebel; Patrick Gelß; Sebastian Pokutta (2023), "Improved local models and new Bell inequalities via Frank-Wolfe algorithms",
Physical Review Research , 5 (4): 043059,
arXiv :
2302.04721 ,
doi :
10.1103/PhysRevResearch.5.043059
^ Rietz, Ronald E. (1974), "A proof of the Grothendieck inequality",
Israel Journal of Mathematics , 19 (3): 271–276,
doi :
10.1007/BF02757725 .
^ Hirsch, Flavien; Quintino, Marco Túlio; Vértesi, Tamás; Navascués, Miguel; Brunner, Nicolas (2017), "Better local hidden variable models for two-qubit Werner states and an upper bound on the Grothendieck constant", Quantum , 1 : 3,
arXiv :
1609.06114 ,
Bibcode :
2017Quant...1....3H ,
doi :
10.22331/q-2017-04-25-3 ,
S2CID
14199122 .
^ Alon, Noga; Naor, Assaf (January 2006).
"Approximating the Cut-Norm via Grothendieck's Inequality" . SIAM Journal on Computing . 35 (4): 787–803.
doi :
10.1137/S0097539704441629 .
ISSN
0097-5397 .
^
a
b Khot, Subhash; Naor, Assaf (2012-04-25).
"Grothendieck-Type Inequalities in Combinatorial Optimization" . Communications on Pure and Applied Mathematics . 65 (7): 992–1035.
arXiv :
1108.2464 .
doi :
10.1002/cpa.21398 .
ISSN
0010-3640 .
S2CID
3175317 .
^ P., Boyd, Stephen (2011).
Convex optimization . Cambridge Univ. Pr.
ISBN
978-0-521-83378-3 .
OCLC
767754283 . {{
cite book }}
: CS1 maint: multiple names: authors list (
link )
^ Alon, N. (1992).
"The algorithmic aspects of the regularity lemma" . Proceedings., 33rd Annual Symposium on Foundations of Computer Science . IEEE. pp. 473–481.
doi :
10.1109/sfcs.1992.267804 .
ISBN
0-8186-2900-2 .
S2CID
2222009 .
^
a
b
c
d
e Alon, Noga; Makarychev, Konstantin; Makarychev, Yury; Naor, Assaf (2006-03-01).
"Quadratic forms on graphs" . Inventiones Mathematicae . 163 (3): 499–522.
doi :
10.1007/s00222-005-0465-9 .
ISSN
1432-1297 .
^ Nemirovski, A.; Roos, C.; Terlaky, T. (1999-12-01).
"On maximization of quadratic form over intersection of ellipsoids with common center" . Mathematical Programming . 86 (3): 463–473.
doi :
10.1007/s101070050100 .
ISSN
1436-4646 .
S2CID
2988923 .
^ Megretski, Alexandre (2001).
"Relaxations of Quadratic Programs in Operator Theory and System Analysis" . In Borichev, Alexander A.; Nikolski, Nikolai K. (eds.). Systems, Approximation, Singular Integral Operators, and Related Topics . Operator Theory: Advances and Applications. Basel: Birkhäuser. pp. 365–392.
doi :
10.1007/978-3-0348-8362-7_15 .
ISBN
978-3-0348-8362-7 .
^ Charikar, M.; Wirth, A. (2004).
"Maximizing Quadratic Programs: Extending Grothendieck's Inequality" . 45th Annual IEEE Symposium on Foundations of Computer Science . IEEE. pp. 54–60.
doi :
10.1109/focs.2004.39 .
ISBN
0-7695-2228-9 .
S2CID
7036076 .
^ Briet, Jop; de Oliveira Filho, Fernando Mario; Vallentin, Frank (2014).
"Grothendieck Inequalities for Semidefinite Programs with Rank Constraint" . Theory of Computing . 10 (1): 77–105.
arXiv :
1011.1754 .
doi :
10.4086/toc.2014.v010a004 .
ISSN
1557-2862 .
S2CID
1004947 .
^ Lovasz, L. (January 1979).
"On the Shannon capacity of a graph" . IEEE Transactions on Information Theory . 25 (1): 1–7.
doi :
10.1109/TIT.1979.1055985 .
ISSN
0018-9448 .
^ Karger, David; Motwani, Rajeev; Sudan, Madhu (1998-03-01).
"Approximate graph coloring by semidefinite programming" . Journal of the ACM . 45 (2): 246–265.
doi :
10.1145/274787.274791 .
ISSN
0004-5411 .
^ Naor, A., & Schechtman, G. (2009). An approximation scheme for quadratic form maximization on convex bodies. Manuscript , 1 (4), 8.
^ Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi (2012-01-17).
"Bypassing UGC from some Optimal Geometric Inapproximability Results" . Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms . Philadelphia, PA: Society for Industrial and Applied Mathematics: 699–717.
doi :
10.1137/1.9781611973099.58 .
ISBN
978-1-61197-210-8 .
External links
Spaces
Theorems Operators Algebras Open problems Applications Advanced topics