In mathematics, the Grothendieck inequality states that there is a universal constant K G {\displaystyle K_{G}} with the following property. If Mij 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 si, tj 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 Si, Tj 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. 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 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 n , ‖ ⋅ ‖ p ) {\displaystyle (\mathbb {R} ^{n},\|\cdot \|_{p})} and ( R m , ‖ ⋅ ‖ q ) {\displaystyle (\mathbb {R} ^{m},\|\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, 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)} . Krivine (1979) improved the upper bound by proving that K G R ≤ π 2 ln ( 1 + 2 ) ≈ 1.78221398 {\displaystyle K_{G}^{\mathbb {R} }\leq {\frac {\pi }{2\ln(1+{\sqrt {2}})}}\approx 1.78221398} , conjecturing that it is tight. However, this conjecture was disproved by Braverman et al. (2011). They did not provide an explicit upper bound, but it seems their argument showed that K G R < π 2 log ( 1 + 2 ) − 10 − 500 {\displaystyle K_{G}^{\mathbb {R} }<{\frac {\pi }{2\log(1+{\sqrt {2}})}}-10^{-500}} . The best numerical lower bound for K G R {\displaystyle K_{G}^{\mathbb {R} }} was ≈ 1.67696 {\displaystyle \approx 1.67696} by Davie (1984). This was shown not to be optimal by Heilman (2026a) and Jones & Malavolta (2026). The best numerical upper bound for K G R {\displaystyle K_{G}^{\mathbb {R} }} is π 2 log ( 1 + 2 ) − 6.039 ⋅ 10 − 5 ≈ 1.7821536 {\displaystyle {\frac {\pi }{2\log(1+{\sqrt {2}})}}-6.039\cdot 10^{-5}\approx 1.7821536} by Li et al. (2026), with concurrent improvement of π 2 log ( 1 + 2 ) − 10 − 5 {\displaystyle {\frac {\pi }{2\log(1+{\sqrt {2}})}}-10^{-5}} in Heilman (2026b).
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})} .
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.
Upper bounds Some historical data on best known upper bounds of K G R ( d ) {\displaystyle K_{G}^{\mathbb {R} }(d)} :
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. 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\}.}
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