Primal/Dual Method for the Grothendieck Constant
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Primal/Dual Method for the Grothendieck Constant".
Paper summary: Tom: So, wrapping up the "Primal/Dual Method for the Grothendieck Constant," the authors have successfully proven that one point seven seven three is less than KG, and one point seven seven nine nine is greater than KG >
Jane: And they found a numerical estimate around one point seven seven nine from their primal/dual search, which fits right in that range >
Lu: The authors used Gaussian duality theory based on Hermite projection games for the upper bound and operators on Gaussian space for the lower bound to precisely define these bounds >
Meng: It shows that we can use these complex optimization problems, even with AI assistance in the search, to get concrete numerical values for constants that are usually theoretical concepts >
Lalam: The paper is really about showing how a primal/dual framework can be used algorithmically to pin down the real Grothendieck constant >
Tom: So what this means for the world is that we have a more systematic way to explore the landscape of these kinds of mathematical constants, even if it requires massive computational overhead for rigorous proof >
Conclusion: Tom: So, we've been looking at this paper about the Grothendieck constant using some primal and dual methods to find bounds.
Jane: And basically, they found a way to search for upper and lower limits on that constant by making two objects with really close numbers.
Lu: The core idea is this alternating update rule where they try to minimize something over one set of choices and maximize something over another set.
Meng: From an engineering standpoint, it sounds like they're using AI heuristics to guess the best starting points for these searches because the full proof is too complex for a direct calculation.
Lalam: And what they’re aiming for is to get a pair of candidates where their primal and dual estimates match up pretty closely, suggesting the constant sits around one point seven seven nine.
Tom: That's what caught my attention, because we're dealing with this real constant that shows up in so many places.
Jane: It’s a big deal because it gives us a systematic way to find these bounds using duality theory, which is a very solid mathematical framework.
Lu: They established strong duality here using Sion's minimax theorem, meaning the search strategy they used—minimizing over Q and maximizing over C—is mathematically sound for finding that gap between the upper and lower bounds.
Meng: I wonder how robust those heuristic guesses are when you try to deploy this on a massive scale, because the paper relies on these AI-driven optimizations to narrow down what's possible.
Tom: Well, they do have some rigorous certificates proving where those numbers actually land, showing the constant is between one point seven seven three and one point seven seven nine nine.
Jane: So for someone just listening, it means we have a structured algorithm that can tackle these high-level mathematical limits without having to prove every single inequality by hand.
Lu: It’s really about the process of finding those bounds through optimization—it shows how representation learning and duality can be used together to constrain a real number.
Meng: But the paper does acknowledge that getting those rigorous certificates involves these massive analytical reductions, which means the actual computational verification is pretty heavy.
Tom: That's fair; it’s not just a simple calculation, it’s a whole system of checks to confirm those bounds hold up under pressure.
Jane: So we have this powerful method that uses AI to guide the search for these important limits on the Grothendieck constant, setting us between one point seven seven three and one point seven seven nine nine.
Lu: Exactly, it's a demonstration of how primal dual methods can be used algorithmically to pin down constants through clever search strategies.
Steven Heilman, Chris Jones, Giulio Malavolta
University of Southern California · University of California, Davis · Bocconi University
cs.CC, math.FA
Submitted: 2026-10-07
Updated: 2026-11-14
Code: https://github.com/christophsjones/RealGrothendieck
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 68/100
The gist: The paper presents a primal/dual method for algorithmically searching for upper and lower bounds on the real Grothendieck constant by proving that 1.773 ≤ KG ≤ 1.7799.
Key concepts
- Primal/Dual Method
- This is a search strategy where two related problems (primal and dual) are solved simultaneously. In this context, it involves minimizing one quantity (q over Q) while maximizing another (c over C). The goal is to find a pair of objects whose values are close, which heuristically points to the value of KG.
- Duality Theory for KG
- This theory formalizes the relationship between the upper and lower bounds. It states that 1/KG equals the supremum of 'c' in set C and the infimum of 'q' in set Q. This strong duality, guaranteed by Sion’s minimax theorem, provides a mathematical framework to precisely bound KG from both sides.
- Numerical Primal/Dual Search
- This is the practical step where the search is executed. It uses AI heuristics to find initial optimizers for one set (Q) and then refines the search by minimizing the worst-case value among rounding functions in a pool. This process yields candidate estimates that match on their first four digits, suggesting KG ≈ 1.779.
- Certificate Certification
- These are rigorous mathematical proofs that validate the numerical bounds found by the algorithm. The upper bound is certified by showing a specific inequality holds for a mixture of rounding functions, while the lower bound uses a reduction to an SDP game to prove KG is greater than 1.773.
Terminology
Summary
The paper presents a primal/dual method for algorithmically searching for upper and lower bounds on the real Grothendieck constant by proving that 1. p. 0 773 ≤ KG ≤ 1. p. 0 Primal/Dual Method for the Grothendieck Constant
Steven Heilman∗ Chris Jones† Giulio Malavolta‡
Abstract
We determine the hundredths digit of the real Grothendieck constant by proving 1. 773 ≤ KG ≤
1.Where the paper says it
Where the paper says it
Primal/Dual Method for Bounding KG
The main conceptual innovation is a primal/dual method for algorithmically searching for upper and lower bounds on KG by producing a pair of objects with nearly-matching value which heuristically suggest KG ≈ 1.779. This search involves an alternating update rule where q is minimized over Q and c is maximized over C. p. 3 2,
1
KG
= sup
c∈C
inf
q∈Q
⟨c, q⟩ = inf
q∈Q
sup
c∈C
⟨c, q⟩ (2. 3)
This suggests that we should search for extremizers c, q using a primal/dual algorithm, using the
alternating update rules (assuming the extrema are attained),
q = arg min
q∈Q
⟨c, q⟩, c = arg max
c∈C
⟨c, q⟩. 6)
This can be formulated as a linear program in µ again parameterized by (cm(f, g))1≤m≤D. Running the algorithm leads to a pair of candidates with heuristic primal and dual estimates of
KG matching on the first four digits KG ≈ 1.Where the paper says it
Where the paper says it
Duality Theory for KG
The paper establishes that two types of Gaussian objects are sufficient to precisely bound KG from both sides, specifically Krivine rounding schemes for the upper bound and operators on Gaussian space for the lower bound. The duality theory is formalized by Theorem 2. p. 0 Furthermore, numerical heuristics suggest the estimate KG ≈ 1. We start by simplifying the Gaussian duality theory of KG, based on Hermite projection games and Krivine rounding
schemes. 2 Numerical primal/dual search
By Theorem 2. 2,
1
KG
= sup
c∈C
inf
q∈Q
⟨c, q⟩ = inf
q∈Q
sup
c∈C
⟨c, q⟩ (2. This implies the weak duality supc∈C infq∈Q ⟨c, q⟩ ≤ infq∈Q supc∈C ⟨c, q⟩. Strong duality holds by Sion’s minimax theorem: C is convex, Q is convex and compact in the weak-∗
topology on ℓ∞ = (ℓ1)
∗
, and ⟨c, q⟩ is affine and continuous in each variable separately.Where the paper says it
Where the paper says it
Where the paper says it
Numerical Primal/Dual Search
The numerical primal/dual search uses a slight variant of Eq. (2.4) involving two steps: first, heuristically compute infinity-to-one optimizers for Q using AI heuristics. p. 4 In the first step, fix Q and heuristically compute its infinity-to-1 optimizers (fi
, gi)i∈I . Add
(fi
, gi)i∈I to a pool of rounding functions, denoted R. Heuristically calculating the ∞-to-1
optimizers is very slow and is guided by AI-heuristics. In the second step, fix the pool R and re-compute Q to minimize the worst value among the
rounding functions in the pool. q = arg min
q∈Q≤D
max
(f,g)∈R
X
D
m=1
m odd
qmcm(f, g) Q =
X
D
m=1
qmΠm . 5)
This computation can be formulated as a linear program parameterized by the coefficients
(cm(f, g))1≤m≤D for (f, g) ∈ R. 6)
This can be formulated as a linear program in µ again parameterized by (cm(f, g))1≤m≤D. Running the algorithm leads to a pair of candidates with heuristic primal and dual estimates of
KG matching on the first four digits KG ≈ 1.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the Gains Come From
The rigorous certificates are very large (analytical reductions to thousands of numerical inequalities) because brute-force proofs for OPT(Q) involve extensive numerical inequalities proven using AI tools. The upper bound is certified by Theorem 4. p. 1 779
because we were not able to certify the instances found by the primal/dual search, instead using
simpler instances for Theorem 1. To explain the difficulties more, one of the two certification tasks
is to prove an upper bound on OPT(Q) for a candidate hard instance Q. 773 ≤ KG ≤
1. Furthermore, numerical heuristics suggest the estimate KG ≈ 1. The main body of the paper contains the general primal/dual theory, then outlines the instances
and certificates used for Theorem 1. The upper and lower bounds are proven in Theorem 4. 779
because we were not able to certify the instances found by the primal/dual search, instead using
simpler instances for Theorem 1. To explain the difficulties more, one of the two certification tasks
is to prove an upper bound on OPT(Q) for a candidate hard instance Q.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Upper Bound Certificate
The upper bound is estimated by calculating c1(µ) − Podd m≥3cm for a mixture of rounding functions µ. The resulting estimated upper bound is c1(µ) − X63i=3cm ≈ 0. p. 1 779
because we were not able to certify the instances found by the primal/dual search, instead using
simpler instances for Theorem 1. To explain the difficulties more, one of the two certification tasks
is to prove an upper bound on OPT(Q) for a candidate hard instance Q.Where the paper says it
Lower Bound Certificate
The lower bound is proven by showing that for a Hermite projection game Q = Podd m≥1 qmΠm with SDP(Q) ≥ 1−on(1) and OPT(Q) = vn(q) ≤ v∞(q), then SDP(Q)/ OPT(Q) ≥ 1−on(1) v∞(q)=KG − on(1). The final bound is KG ≥ 1. p. 0 KG is a basic mathematical constant arising in several fields including functional analysis [Pis12],
quantum information [AGT06], and approximation algorithms [AN06, KN12]. The bound KG < ∞
was first proven by Grothendieck and is now known as “Grothendieck’s inequality” [Gro56].Where the paper says it
Source Bits Checks and uses
The verification process involves running python verify.py --lower --workers 4 to check the lower certificate, and upper/verify. p. 0 773 ≤ KG ≤ 1. 7799
Our main conceptual innovation is a primal/dual method for algorithmically searching for upper
and lower bounds on KG. 779
because we were not able to certify the instances found by the primal/dual search, instead using
simpler instances for Theorem 1. To explain the difficulties more, one of the two certification tasks
is to prove an upper bound on OPT(Q) for a candidate hard instance Q. It remains to pass from B to K. The set K is exactly the set of barycenters of probability measures
on B.Where the paper says it
Where the paper says it
Where the paper says it
C Upper Bound Certificate
The C upper bound certificate is derived from the calculation of Cˆ[a, b] and the final sum in Eq. (C.54), which yields KG ≤ 5.996940779766870 · 10−8.
The source bits checks confirm the final bound is KG ≤ 5.996940779766870 · 10−8.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Primal/dual method for bounding Grothendieck constant KG: The AI system can perform an algorithmic search for upper and lower bounds on KG using alternating update rules (Eq. 2.4) based on heuristics from Hermite projection games and Krivine rounding schemes, resulting in a pair of objects with
nearly-matching value which heuristically suggest KG ≈ 1.779.
-
Rigorous certification of bounds: The system can rigorously certify the values of the primal/dual search objects by utilizing AI tools to provide
brute-force proofs
involvingextensive numerical inequalities proven using AI tools, which would have been impossible to obtain by hand.
-
Verification and error bounding: The system can verify the numerical results against exact rational arithmetic, as demonstrated in the source code checks, ensuring that the final bounds derived from the primal/dual method satisfy Theorem 4.1 (KG ≥ 1.773) and its upper bound (KG < 1.779893).
-
Asymptotic analysis: The system can lift Hermite projection games to an explicit asymptotic space in the limit n → ∞, allowing it to determine that
asymptotic Boolean functions are closely related to the 'limiting Krivine schemes' used by Saha et al. [SLX+26].
-
Polynomial threshold function optimization: The system can identify
asymptotic ∞-to-1 optimizers of Q
which are shown to exist and can be of the formf = sign(p) and g = sign(r) for p, r in H≤D.
Abstract
We determine the hundredths digit of the real Grothendieck constant by proving 1.773 at most K G at most 1.7799. Furthermore, numerical heuristics suggest the estimate K G about 1.779. We start by simplifying the Gaussian duality theory of K G, based on Hermite projection games and Krivine rounding schemes. The bounds are obtained by a heuristic primal/dual search for these objects, followed by rigorous certification of their values. The search and certification are performed using AI tools, and in particular the rigorous certificates are very large (analytical reductions to thousands of numerical inequalities).
Sources
- A Lower Bound for Grothendieck's Constant
- An Upper Bound on Grothendieck's Constant
- Limit distributions for polynomials with independent and identically distributed entries
- The Grothendieck Constant is Strictly Larger than Davie-Reeds' Bound
- New Lower and Upper Bounds for the Grothendieck Constant
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?