An Upper Bound on Grothendieck’s Constant

Steven Heilman · 2026

Read An Upper Bound on Grothendieck’s Constant by Steven Heilman (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-00247.txt.

Introduction

Heilman tightens the known cap on a famed constant from math and computing. The constant, tied to Grothendieck, bounds how well some hard tasks can be smoothed. A 2011 team had set a cap just shy of a clean bound. Their proof needed an extra dice step in its scheme.

Heilman drops that extra step with a fresh scheme. He casts points onto a chance plane through the core. A fifth-grade curve then sets the cut line. This proves a cap a hair below the clean bound. A third-grade form gives a like cap by the same path. A proof checked by strict span math seals a looser but firm cap. The work ends a long open guess from 2011.

Catalog record

CREATORSteven Heilman
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.00247

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Upper Bound on Grothendieck’s Constant Thanks: Email: [email protected] Supported by NSF Grant CCF AF 2448108. MSC Classification: 15A60, 90C27, 42C10, 68Q17 Keywords: rounding scheme, Grothendieck constant, semidefinite programming Department of Mathematics, University of Southern California, Los Angeles, CA 90089 Steven Heilman Abstract . We show that Grothendieck’s real constant K G K_{G} can be upper bounded by projecting vectors onto a random plane through the origin and thresholding a degree five Hermite polynomial. This resolves a conjecture of Braverman-Makarychev-Makarychev-Naor from 2011, who required an extra randomization step in their rounding scheme and proved K G < π 2 ​ log ⁡ ( 1 + 2 ) − 10 − 500 K_{G}<\frac{\pi}{2\log(1+\sqrt{2})}-10^{-500} . As a corollary of our result, we prove the bound K G < π 2 ​ log ⁡ ( 1 + 2 ) − 10 − 217 K_{G}<\frac{\pi}{2\log(1+\sqrt{2})}-10^{-217} by thresholding degree three Hermite polynomials in the plane. We finally give a rigorous computer-assisted proof that K G < π 2 ​ log ⁡ ( 1 + 2 ) − 10 − 5 K_{G}<\frac{\pi}{2\log(1+\sqrt{2})}-10^{-5} using interval arithmetic and degree three Hermite polynomial thresholding. 1. Introduction Grothendieck’s real constant K_{G} is the infimum over all K\in(0,\infty) such that, for all positive integers m,n and for every real m\times n matrix (a_{ij}) , we have \max_{\begin{subarray}{c}x_{1},\ldots,x_{m}\\ y_{1},\ldots,y_{n}\end{subarray}\in S^{m+n-1}}\sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij}\langle x_{i},y_{j}\rangle\leq K\cdot\max_{\begin{subarray}{c}\epsilon_{1},\ldots,\epsilon_{m}\\ \delta_{1},\ldots,\delta_{n}\end{subarray}\in\{-1,1\}}\sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij}\epsilon_{i}\delta_{j}, (1) where \langle x,y\rangle=\sum_{i=1}^{d}x_{i}y_{i} for all x,y\in\mathbb{R}^{d} and S^{d-1}=\{x\in\mathbb{R}^{d}\colon\langle x,x\rangle=1\} for any d\geq 1 . Inequality ( 1 ) was originally stated as an inequality of two different tensor norms [ G53 ] (see also [ P12 , Section 3] ), though the discretized formulation ( 1 ) was proven in [ LP68 ] . Determining the exact value of K_{G} remains a significant open problem since it was first posited in [ G53 ] . We can rephrase the problem of finding the constant K_{G} as: what is the “best” way to “round” the vectors x_{1},\ldots,x_{m},y_{1},\ldots,y_{n} to \pm 1 ? There are many good references on ( 1 ) and its connections to combinatorics, functional analysis, Banach space theory, operator algebras, the Connes embedding problem, theoretical computer science, and quantum mechanics; see, for example, [ P12 , KN12 ] . Note also that Grothendieck’s constant is the maximal quantum violation in Bell’s inequality from quantum mechanics [ T87 ] . Also, assuming the Unique Games Conjecture [ K02 ] , it is NP-hard to approximate the right side of ( 1 ) within any constant smaller than Grothendieck’s constant K_{G} [ RS09 ] . Grothendieck [ G53 ] originally proved that K_{G}\leq\sinh(\pi/2)\approx 2.3013 . In [ K77 ] , Krivine improved this bound to K_{G}\leq\frac{\pi}{2\log(1+\sqrt{2})}\approx 1.78221397819 (see Example 1.4 below), and it was generally believed that this inequality should be an equality [ K01 ] . However, it was then shown in [ BMMN13 ] that there is a c^{\prime}>0 such that K_{G}<\frac{\pi}{2\log(1+\sqrt{2})}-c^{\prime}. (2) An effective c^{\prime} was proven but not specified in [ BMMN13 ] ; an inspection of the argument seems to give c^{\prime}=10^{-500} . Krivine’s argument [ K77 ] shows that, after “preprocessing” the vectors x_{1},\ldots,x_{m},y_{1},\ldots,y_{n} by nonlinearly mapping them to a different Hilbert space (Fock space), we can then map those vectors to \pm 1 by projecting them onto a Gaussian random vector, and taking the sign of this projected value. (The nonlinear preprocessing removes the nonlinearity that appears after projecting onto the Gaussian.) The argument of [ BMMN13 ] instead projects the preprocessed vectors onto a random plane through the origin, and then (with probability 0<p<1 ) applies a perturbation of the sign function on this two-dimensional plane to “round” the vectors to \pm 1 (and with probability 1-p applies the sign function). This perturbation uses a degree 5 Hermite polynomial. Also, rounding schemes of this form (projecting onto a random hyperplane through the origin and then thresholding, possibly with additional randomness) can obtain arbitrarily good approximations of K_{G} [ RN14 ] . In other words, finding the exact value of K_{G} reduces to finding the best “rounding scheme” for vectors x_{1},\ldots,x_{m},y_{1},\ldots,y_{n} in ( 1 ) (where the rounding scheme itself might need additional randomness). The best known lower bounds for K_{G} were recently shown in [ H26 , JM26 ] to be around 1.6769 . In particular, [ JM26 ] showed a 10^{-12} improvement over the bound from [ D84 , R91 ] . 1.1. Krivine Rounding Schemes We now describe the rounding scheme we will use to prove the best known constant in Grothendieck’s inequality. Definition 1.1 ( Krivine rounding scheme , [ BMMN13 ] ) . Fix k\in\mathbb{N} and let f,g\colon\mathbb{R}^{k}\to\{-1,1\} be odd measurable functions. Let G_{1},G_{2}\in\mathbb{R}^{k} be independent standard Gaussian random vectors, so that G_{1} has density x\mapsto(2\pi)^{-k/2}e^{-\|x\|_{2}^{2}/2} . For any t\in(-1,1) , define the (complex correlation parameter) noise stability \displaystyle H_{f,g}(t) \displaystyle\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\mathbb{E}\left[f\left(\frac{1}{\sqrt{2}}G_{1}\right)g\left(\frac{t}{\sqrt{2}}G_{1}+\frac{\sqrt{1-t^{2}}}{\sqrt{2}}G_{2}\right)\right] (3) \displaystyle=\frac{1}{\pi^{k}(1-t^{2})^{k/2}}\int_{\mathbb{R}^{k}}\int_{\mathbb{R}^{k}}f(x)g(y)\exp\left(\frac{-\|x\|_{2}^{2}-\|y\|_{2}^{2}+2t\langle x,y\rangle}{1-t^{2}}\right)\,dx\,dy. Then H_{f,g} extends to an analytic function on the strip \left\{z\in\mathbb{C}\colon\Re(z)\in(-1,1)\right\}. We shall call \{f,g\} a Krivine rounding scheme if H_{f,g} is invertible on a neighborhood of the origin, and if we consider the Taylor expansion H_{f,g}^{-1}(z)=\sum_{j=0}^{\infty}\widehat{a}_{2j+1}z^{2j+1}, (4) then there exists c=c(f,g)\in(0,\infty) satisfying \sum_{j=0}^{\infty}|\widehat{a}_{2j+1}|c^{2j+1}=1. (5) Only odd Taylor coefficients appear in ( 4 ) since H_{f,g} , and therefore also H_{f,g}^{-1} , is odd. A Krivine rounding scheme yields an algorithmic proof of Grothendieck’s inequality in the following way. Algorithm 1.2 ( Krivine rounding algorithm , [ BMMN13 ] ) . Input : Vectors \{x_{r}\}_{r=1}^{m},\{y_{s}\}_{s=1}^{n}\subseteq S^{m+n-1} , and f,g\colon\mathbb{R}^{k}\to\{-1,1\} , which define coefficients \{\widehat{a}_{2j+1}\}_{j=0}^{\infty} by ( 4 ) and a constant c\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}c(f,g) by ( 5 ). Output : Random signs \{\sigma_{r}\}_{r=1}^{m},\{\tau_{s}\}_{s=1}^{n}\subseteq\{-1,1\} . Step 0 (Notation). Consider the Hilbert space \mathcal{H}=\bigoplus_{j=0}^{\infty}\left(\mathbb{R}^{m+n}\right)^{\otimes(2j+1)}. For any x\in S^{m+n-1} we can then define two vectors I(x),J(x)\in\mathcal{H} by \displaystyle I(x) \displaystyle\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\sum_{j=0}^{\infty}|\widehat{a}_{2j+1}|^{1/2}c^{(2j+1)/2}x^{\otimes(2j+1)} (6) \displaystyle J(x) \displaystyle\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\sum_{j=0}^{\infty}\operatorname{sign}(\widehat{a}_{2j+1})|\widehat{a}_{2j+1}|^{1/2}c^{(2j+1)/2}x^{\otimes(2j+1)}, The choice of c was made in order to ensure that I(x) and J(x) are unit vectors in \mathcal{H} . Moreover, the definitions ( 6 ) were made so that the following identity holds: \forall x,y\in S^{m+n-1},\qquad\langle I(x),J(y)\rangle_{\mathcal{H}}\stackrel{{\scriptstyle\eqref{one9}}}{{=}}H_{f,g}^{-1}\bigl(c\langle x,y\rangle\bigr). (7) Step 1 (Preprocessing the vectors). Transform the initial unit vectors \{x_{r}\}_{r=1}^{m},\{y_{s}\}_{s=1}^{n}\subseteq S^{m+n-1} to vectors \{u_{r}\}_{r=1}^{m},\{v_{s}\}_{s=1}^{n}\subseteq S^{m+n-1} satisfying the identities \forall\,(r,s)\in\{1,\ldots,m\}\times\{1,\ldots,n\},\qquad\langle u_{r},v_{s}\rangle=\langle I(x_{r}),J(y_{s})\rangle_{\mathcal{H}}\stackrel{{\scriptstyle\eqref{one14}}}{{=}}H_{f,g}^{-1}\bigl(c\langle x_{r},y_{s}\rangle\bigr). (8) As explained in [ AN04 ] , these new vectors can be computed efficiently provided H_{f,g}^{-1} can be computed efficiently; this simply amounts to computing a Cholesky decomposition. Step 2 (Random projection). Let G\colon\mathbb{R}^{m+n}\to\mathbb{R}^{k} be a random k\times(m+n) matrix whose entries are i.i.d. standard Gaussian random variables. Let \sigma_{1},\ldots,\sigma_{m},\tau_{1},\ldots,\tau_{n}\in\{-1,1\} be random signs defined by \forall\,(r,s)\in\{1,\ldots,m\}\times\{1,\ldots,n\},\qquad\sigma_{r}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}f\left(\frac{1}{\sqrt{2}}Gu_{r}\right)\quad\text{and}\quad\tau_{s}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}g\left(\frac{1}{\sqrt{2}}Gv_{s}\right). (9) A Krivine rounding scheme automatically upper bounds K_{G} via the constant c from ( 5 ). Corollary 1.3 ( [ BMMN13 ] ) . Let f,g\colon\mathbb{R}^{k}\to\{-1,1\} be a Krivine rounding scheme. Then K_{G}\leq\frac{1}{c(f,g)}. Proof, [ BMMN13 ] . Having obtained the random signs \sigma_{1},\ldots,\sigma_{m},\tau_{1},\ldots,\tau_{n}\in\{-1,1\} as in ( 9 ), for every m\times n matrix (a_{rs}) we have \displaystyle\max_{\varepsilon_{1},\ldots,\varepsilon_{m},\delta_{1},\ldots,\delta_{n}\in\{-1,1\}}\sum_{r=1}^{m}\sum_{s=1}^{n}a_{rs}\varepsilon_{r}\delta_{s}\geq\mathbb{E}\left[\sum_{r=1}^{m}\sum_{s=1}^{n}a_{rs}\sigma_{r}\tau_{s}\right] \displaystyle\stackrel{{\scriptstyle(*)}}{{=}}\mathbb{E}\left[\sum_{r=1}^{m}\sum_{s=1}^{n}a_{rs}H_{f,g}\bigl(\langle u_{r},v_{s}\rangle\bigr)\right]\stackrel{{\scriptstyle\eqref{one15}}}{{=}}c(f,g)\sum_{r=1}^{m}\sum_{s=1}^{n}a_{rs}\langle x_{r},y_{s}\rangle, where (*) follows by rotational invariance from ( 9 ) and ( 3 ).∎ Example 1.4 . Let k=1 and let f(x)=g(x)=\mathrm{sign}(x) for all x\in\mathbb{R} . Then H_{f,g}(z)=\frac{2}{\pi}\arcsin(z) , H_{f,g}^{-1}(z)=\sin(\pi z/2) , \widehat{a}_{2j+1}=(-1)^{j}(\pi/2)^{2j+1}/(2j+1)! , so c=c(f,g) satisfies 1=\sum_{j=0}^{\infty}|\widehat{a}_{2j+1}|c^{2j+1}=\sum_{j=0}^{\infty}\frac{(\pi/2)^{2j+1}}{(2j+1)!}c^{2j+1}=\sinh(\pi c/2). So, c=\frac{2}{\pi}\sinh^{-1}(1)=\frac{2}{\pi}\log(1+\sqrt{2}) , and Corollary 1.3 gives Krivine’s bound K_{G}\leq\frac{\pi}{2\log(1+\sqrt{2})} . 1.2. The Proof of [ BMMN13 ] The main result of [ BMMN13 ] is ( 2 ). The proof of ( 2

Read the complete text