Grothendieck inequality

In mathematics, the Grothendieck inequality states that there is a universal constant $K_{G}$ with the following property. If M_ij is an n × n (real or complex) matrix with

${\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

${\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}$ 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)$. In fact, there are two Grothendieck constants, $K_{G}^{\mathbb {R} }(d)$ and $K_{G}^{\mathbb {C} }(d)$, 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.

Bounds on the constants

The sequences $K_{G}^{\mathbb {R} }(d)$ and $K_{G}^{\mathbb {C} }(d)$ are easily seen to be increasing, and Grothendieck's result states that they are bounded, so they have limits.

Grothendieck proved that $1.57\approx {\frac {\pi }{2}}\leq K_{G}^{\mathbb {R} }\leq \operatorname {sinh} {\frac {\pi }{2}}\approx 2.3,$ where $K_{G}^{\mathbb {R} }$ is defined to be $\sup _{d}K_{G}^{\mathbb {R} }(d)$.

Krivine (1979) improved the result by proving that $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).

Grothendieck constant of order d

Boris Tsirelson showed that the Grothendieck constants $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}^{\mathbb {R} }(2d^{2})$.

Lower bounds

Some historical data on best known lower bounds of $K_{G}^{\mathbb {R} }(d)$ is summarized in the following table.

d	Grothendieck, 1953	Krivine, 1979	Davie, 1984	Fishburn et al., 1994	Vértesi, 2008	Briët et al., 2011	Hua et al., 2015	Diviánszky et al., 2017
2		${\sqrt {2}}$ ≈ 1.41421
3					1.41724		1.41758	1.4359
4					1.44521		1.44566	1.4841
5				${\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
...
∞	${\frac {\pi }{2}}$ ≈ 1.57079		1.67696

Upper bounds

Some historical data on best known upper bounds of $K_{G}^{\mathbb {R} }(d)$:

d	Grothendieck, 1953	Rietz, 1974	Krivine, 1979	Braverman et al., 2011	Hirsch et al., 2016
2			${\sqrt {2}}$ ≈ 1.41421
3			1.5163		1.4644
4			${\frac {\pi }{2}}$ ≈ 1.5708
...
8			1.6641
...
∞	$\operatorname {sinh} {\frac {\pi }{2}}$ ≈ 2.30130	2.261	${\frac {\pi }{2\ln(1+{\sqrt {2}})}}$ ≈ 1.78221	${\frac {\pi }{2\ln(1+{\sqrt {2}})}}-\varepsilon$

Applications

Cut norm estimation

Given an $m\times n$ real matrix $A=(a_{ij})$, the cut norm of $A$ is defined by

$\|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. An application of the Grothendieck inequality is to give an efficient algorithm for approximating the cut norm of a given real matrix $A$; specifically, given an $m\times n$ real matrix, one can find a number $\alpha$ such that

$\|A\|_{\square }\leq \alpha \leq C\|A\|_{\square },$

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

We give a sketch of this approximation algorithm. Let $B=(b_{ij})$ be $(m+1)\times (n+1)$ matrix defined by

${\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 easily verify that $\|A\|_{\square }=\|B\|_{\square }$ by observing, if $S\in [m+1],T\in [n+1]$ form a maximizer for the cut norm of $B$, then

$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$. Next, one can easily verify that $\|B\|_{\square }=\|B\|_{\infty \to 1}/4$, where

$\|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\}.$

Although not important in this proof, $\|B\|_{\infty \to 1}$ can be interpreted to be the norm of $B$ when viewed as a linear operator from $\ell _{\infty }^{m}$ to $\ell _{1}^{m}$.

Now it suffices to design an efficient algorithm for approximating $\|A\|_{\infty \to 1}$. We consider the following semidefinite program:

${\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 ${\text{SDP}}(A)\geq \|A\|_{\infty \to 1}$. The Grothedieck inequality implies that ${\text{SDP}}(A)\leq K_{G}^{\mathbb {R} }\|A\|_{\infty \to 1}$. Many algorithms (such as interior methods) are known to output the value of a semidefinite program up to an additive error $\varepsilon$ in time that is polynomial in the program description size and $\log(1/\varepsilon )$. Therefore, one can output $\alpha ={\text{SDP}}(B)$ which satisfies $\|A\|_{\square }\leq \alpha \leq C\|A\|_{\square }$ with $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.

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)$ is close to being $\varepsilon$-regular, meaning that for all $S\subset X,T\subset Y$ with $|S|\geq \varepsilon |X|,|T|\geq \varepsilon |Y|$, we have

$\left|{\frac {e(S,T)}{|S||T|}}-{\frac {e(X,Y)}{|X||Y|}}\right|\leq \varepsilon ,$

where $e(A,B)=|\{(u,v)\in A\times B:uv\in E\}|$ for all $A,B\subset V$ and $V,E$ are the vertex and edges of the graph, respectively. To that end, we construct an $n\times n$ matrix $A=(a_{xy})_{(x,y)\in X\times Y}$, where $n=|V|$, defined by

$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\subset X,T\subset Y$,

$\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)$ is not $\varepsilon$-regular, then $\|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\subset X,T\subset Y$ such that

$\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.

Grothendieck inequality of a graph

The Grothendieck inequality of a graph states that for each $n\in \mathbb {N}$ and for each graph $G=(\{1,\ldots ,n\},E)$ without self loops, there exists a universal constant $K>0$ such that every $n\times n$ matrix $A=(a_{ij})$ satisfies that

$\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}.$

The Grothendieck constant of a graph $G$, denoted $K(G)$, is defined to be the smallest constant $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$ is a bipartite graph. Thus,

$K_{G}=\sup _{n\in \mathbb {N} }\{K(G):G{\text{ is an }}n{\text{-vertex bipartite graph}}\}.$

For $G=K_{n}$, the $n$-vertex complete graph, the Grothendieck inequality of $G$ becomes

$\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 _{1}\varepsilon _{n}.$

It turns out that $K(K_{n})\asymp \log n$. On one hand, we have $K(K_{n})\lesssim \log n$. Indeed, the following inequality is true for any $n\times n$ matrix $A=(a_{ij})$, which implies that $K(K_{n})\lesssim \log n$ by the Cauchy-Schwarz inequality:

$\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, we have the matching lower bound $K(K_{n})\gtrsim \log n$.

The Grothendieck inequality $K(G)$ of a graph $G$ depends upon the structure of $G$. It is known that

$\log \omega \lesssim K(G)\lesssim \log \vartheta ,$

and

$K(G)\leq {\frac {\pi }{2\log \left({\frac {1+{\sqrt {(\vartheta -1)^{2}+1}}}{\vartheta -1}}\right)}},$

where $\omega$ is the clique number of $G$, i.e., the largest $k\in \{2,\ldots ,n\}$ such that there exists $S\subset \{1,\ldots ,n\}$ with $|S|=k$ such that $ij\in E$ for all distinct $i,j\in S$, and

$\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 $\vartheta$ is known as the Lovász theta function of the complement of $G$.

, See also

• Pisier–Ringrose inequality

External links

• Weisstein, Eric W. "Grothendieck's Constant". MathWorld. (NB: the historical part is not exact there.)