Primal/Dual Method for the Grothendieck Constant

1 Introduction

• KG is a mathematical constant arising in functional analysis, quantum information, and approximation algorithms, and its finiteness is Grothendieck’s inequality.The paper situates its result against a history of improving bounds.Source: §1 · p. 1
• The paper establishes the first three digits of the real Grothendieck constant as 1.77.The introduction identifies this as the main result.Source: §1 · p. 1
• A primal/dual method searches algorithmically for upper and lower bounds, producing nearly matching objects that heuristically suggest KG ≈1.779.Their values must still be certified to obtain rigorous bounds.Source: §1 · pp. 1–2
• The authors could not certify the search instances, so Theorem 1.1 uses simpler instances and its bounds differ from the heuristic estimate.Certification involves extensive numerical inequalities proved using AI tools.Source: §1 · p. 2

1.1 Is there a short formula for KG?

• Unlike the simpler related constants kG and αGW, the nearly tight integrality-gap instances constructed for KG appear significantly more complicated.The paper says the constructions for KG are known not to achieve tight bounds.Source: §1.1 · p. 2
• The paper asks whether KG has a short formula, suggesting that a numerically tractable optimization value may be the best attainable description if optimal constructions have little structure.The Parisi formula is presented as a comparison: its optimizer is not known to have a simpler description than the optimization problem’s solution.Source: §1.1 · pp. 2–3

2.1 Duality theory for KG

• Convex duality shows that Hermite projection games and Krivine rounding schemes suffice to bound K_G from below and above, respectively.The dual infimum is attained.Source: §2.1 · pp. 3–4

2.2 Numerical primal/dual search

• The search likely has no efficient implementation because calculating the required infinity-to-1 optimizers is NP-hard in general.The authors therefore use heuristics to search for good optimizers.Source: §2.2 · p. 4
• Each search iteration heuristically adds infinity-to-1 optimizers of Q to a rounding pool, then updates Q by minimizing its worst value over that pool.The update is formulated as a linear program over coefficients through degree D.Source: §2.2 · p. 5
• K_G ≈ 1.779: the primal and dual candidates produced by the search have estimates matching on the first four digits.These are heuristic estimates for a candidate pair.Source: §2.2 · p. 5

2.3 Proofs for the duality theory

• Sion’s minimax theorem gives strong duality and an attained dual minimum; discretization turns Hermite-game operators into matrix witnesses for lower bounds on K_G.The operator witness yields a matrix ratio SDP(Q)/OPT(Q).Source: §2.1 · p. 3, §2.3 · p. 6

3 Asymptotic Boolean functions

• Asymptotic Boolean functions are limits of Boolean functions on R^n, arise as ∞-to-1 optimizers, and are used in the numerical primal/dual search.They are closely related to the limiting Krivine schemes of Saha et al. [SLX+26].Source: §3 · p. 6

3.1 Graded Gaussian space

• Graded Gaussian space replaces an asymptotically Gaussian sum with a new Gaussian variable whose grade records the degree of the original polynomial.Variables carry positive integer grades, and the resulting polynomials have both standard degree and graded degree.Source: §3.1 · p. 7
• The graded spaces are closed under bounded-moment limits and their elements can be approximated by finitary functions.The theorem also gives weak closure of the laws in each graded space.Source: §3.1 · p. 8

3.2 Asymptotic Boolean functions on Gaussian space

• The coefficient-sequence set K equals C, and compactness arguments let the section attain finite-support game optima within the asymptotic Boolean class.The proof establishes compactness for the class of bounded odd pairs before identifying K with C.Source: §3.2 · pp. 8–10
• For finitely supported games, an asymptotic Boolean optimizer exists, and one can choose optimizers that are threshold functions of graded degree at most D.The section identifies these as essentially polynomial threshold functions.Source: §3.2 · p. 10
• In the n→∞ setting, the construction attains SDP(Q)/OPT(Q) = K_G; an odd-function distribution with f(X), g(X) ∈ {−1, 1} has Hμ(t) = t/K_G on [−1, 1].Source: §3.2 · pp. 10–11

4.1 Certifying the lower bound

• The certified lower bound is KG ≥ 1.773, obtained by bounding OPT(Q) for a Hermite projection game.The proof reduces the optimization to 44 dimensions and then to finitely many numerical inequalities.Source: §4.1 · p. 11

4.2 Certifying the upper bound

• The upper-bound scheme mixes weighted polynomial-based rounding procedures and uses shared Gaussian vectors to produce signs for input vectors.The conditional row–column sign correlation is H_i(⟨x_a, y_b⟩).Source: §4.2 · pp. 11–13
• The rounding scheme certifies the upper bound KG < 1.779893.Theorem 4.2 supplies this bound for the scheme described in the section.Source: §4.2 · p. 13
• The upper-bound certification combines bounds on the kernel coefficients, with the even coefficients vanishing.The proof invokes bounds from four appendix equations.Source: §4.2 · pp. 13–14

A Numerical summary of the primal/dual run

• The 190-minute run used degree parameter D = 15, 92 Q updates, and a final response pool of 274 rounding-function pairs.The run began with Q = Π1 and maintained a larger pool of 13,069 asymptotic Boolean functions for heuristic norm estimates.Source: A Numerical summary of the primal/dual… · p. 17
• The run ended with a nonzero duality gap, and the remaining gap also reflects truncated coefficient calculations and numerical integration error.The calculations of |c_i(µ)| for i ≥ 3 were computed only up to degree at least 63.Source: A Numerical summary of the primal/dual… · pp. 17–18
• 1.779171 is the estimated upper bound from the final pool’s maximum response value of 0.5620595.The final game’s maximum within the pool was 0.5619674, and a subsequent search found slightly larger responses.Source: A Numerical summary of the primal/dual… · p. 18
• The final rounding mixture uses 8 pairs, each with value approximately 0.5619674 in the final game.The pairs are signs of graded multivariate polynomials with graded-degree at most 15.Source: A Numerical summary of the primal/dual… · p. 18, Table 3 · p. 18

B.1 The game and its one-variable reduction

• The proof first relates KG to v∞(q), leaving an upper bound on v∞(q) as the remaining task.A standard discretization argument gives KG ≥ 1/v∞(q).Source: §B.1 · p. 19
• Proposition B.1 reduces proving the lower bound to showing v_n(q) ≤ v* for every n.The finite family of closed intervals must cover [0, 1] and satisfy the stated dimension-independent conditions.Source: §B.1 · p. 19
• Replacing f and g successively by sign responses cannot decrease OPT(Q), allowing the proof to work with odd functions and h = (f + g)/2, k = (f − g)/2.These substitutions give h^2 + k^2 = 1.Source: §B.1 · p. 20
• The proof bounds the objective using feasible moments and interval-specific matrix inequalities, then uses convexity to control the maximum at interval endpoints.The resulting endpoint bound establishes the claim in Proposition B.1.Source: §B.1 · p. 20

B.2 Finite certification

• The proof reduces feasible-moment bounds to an integer quadratic over signs, then certifies its maximum using graph bounds and sign fixing.The finite reduction partitions [−9, 9] into intervals and panels.Source: §B.2 · pp. 21–22
• Rectangle certificates recursively split a rational cover and bound each leaf using augmented polynomials, graph bounds, and rounding-error charges.The covering and checked leaves establish Eq. (B.19).Source: §B.2 · pp. 22–23
• All 35 certificate rows pass, with the largest payoff bound 0.564015352833 < v*, completing the proof of Theorem 4.1.The checks combine Proposition B.1 with Theorem 2.2.Source: §B.2 · p. 23
• The verifier checks coverage, matrix inequalities, regenerated error allowances, and finite certificates, using outward-rounded 384-bit intervals for analytic calculations.The tail check for Eq. (B.22) uses exact rational arithmetic.Source: §B.2 · p. 23

• The Hermite integrals use W and X1, X2, X3 as independent standard Gaussians, with X = (X1, X2, X3).Source: C Upper bound certificate · p. 23
• For 17 ≤ i ≤ 31, the sign-disagreement probability is arccos(Pi(t))/π by rotational symmetry of two independent standard Gaussians.Source: C Upper bound certificate · p. 23
• The coefficient C[a, b] equals E F² = 1, and C[a, b] = 0 when a + b is even.Source: C Upper bound certificate · p. 23

C.1 Numerical bounds for the coefficients up to degree 681

• 0.56187737994533522919 is the resulting stated lower-bound value for the finite coefficient inequality.Source: §C.1 · p. 25
• The certificate constructs nonnegative rational approximations ˆC[a, b] for a + b ≤ 681 and uses the same array in the finite inequality.Source: §C.1 · pp. 25–26
• The coefficient approximation uses 24-point Gauss–Legendre quadrature on 768 unit-interval nodes, with 512-bit enclosures and rounded binary64 stored values.Source: §C.1 · p. 26
• 0.561894649254995327808 lower-bounds the first term, while 1.540129331402561534750 · 10^-5 upper-bounds the subtracted sum.Source: §C.1 · p. 28

C.2 Bounds above degree 681 for H14, H17, . . . , H31

• The coefficient quantities uij are expectations of F*(X1, X2) times Hermite polynomials, and vanish when i + j is even.Source: §C.2 · p. 34
• 0.9648417014661795 is a lower bound for the coefficient sum, and λ14 times its complement is below 1.254728050780 · 10^-6.Source: §C.2 · p. 34
• In the cited listing, the value associated with i = 17 is 6.982 · 10^-54, while the value associated with i = 18 is 1.223 · 10^-13.Source: §C.2 · p. 35

C.3 Bounds above degree 681 for H1, . . . , H13

• The finite sum uses the exact rational coefficients ˆC[a, b] and is evaluated at 256-bit precision to bound λi.Source: §C.3 · p. 36
• The 256-bit finite-sum evaluation gives upper bounds of 2.364541 · 10^-7 for λ1 and 6.366458 · 10^-6 for λ8.Source: §C.3 · p. 36
• The interval bounds are summed with weights λi to obtain Eq. (C.38).Source: §C.3 · p. 36

C.4 Bounds above degree 681 for P

• Each eHi Taylor series converges absolutely and uniformly on |t| ≤ 1, and its restriction to the unit circle is C4 with fourth angular derivative D4 eHi.Source: §C.4 · pp. 37, 39
• r(27/4) > 7, r(j)(27/4) > 0 for 1 ≤ j ≤ 15, and |r(x)| < 33/20 for |x| ≤ 7/2.The inequalities are verified using interval rounding at 256 bits.Source: §C.4 · pp. 37–38
• For s ≥ 0, min{r(27/4 + s), er(27/4 + s)} ≥ r(27/4) > 7.Source: §C.4 · p. 37
• The interval computation covers 6284 closed intervals and uses the smallest available finite upper endpoint for each interval when combining bounds into Eq. (C.53).The calculations use 192-bit interval rounding on each entire closed interval.Source: §C.4 · pp. 40, 45

C.5 Verification of the numerical bounds

• The verifier compares SHA-256 hashes and checks exact equality with supplied rounding data and data defining F∗.The source descriptions also specify hash comparisons against recorded file contents.Source: §C.5 · pp. 45–46
• The program runs all 12 numerical calculations in a fresh directory before writing VERIFIED.json, and writes ACCEPTED.json only after checking inputs, a scalar condition, and five numerical inequalities.Source: §C.5 · p. 47
• Interval endpoints are rounded down for lower bounds and up for upper bounds, and verification assumes correct execution of the arithmetic operations and elementary functions.Source: §C.5 · p. 47
• The --all --workers 4 option also runs the lower certificate and requires a C++17 compiler and GMP/MPFR, while --data-only checks input identities and rational comparisons without running either numerical proof.Source: §C.5 · p. 47