Primal/Dual Method for the Grothendieck Constant

arXiv:2610.10477 · cs.CC, math.FA · Submitted 2026-10-07 · Read on arXiv

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

Where the paper says it

773 ≤ KG ≤ 1. p. 0

Where the paper says it

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.

7799 Our main conceptual innovation is a primal/dual method for algorithmically searching for upper and lower bounds on KG.

773 ≤ KG ≤ 1.7799.

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

Where the paper says it

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⟩.

The algorithm produces a pair of candidates with heuristic primal and dual estimates of KG matching on the first four digits KG ≈ 1. p. 4
Where the paper says it

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.

779.

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

Where the paper says it

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, which states that 1/KG = sup c in C inf q in Q, suggesting a primal/dual search strategy. p. 3
Where the paper says it

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 establishes strong duality via Sion’s minimax theorem. p. 5
Where the paper says it

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.

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

Where the paper says it

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.

Second, fix the pool R and re-compute Q to minimize the worst value among rounding functions in the pool. p. 4
Where the paper says it

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.

This computation can be formulated as a linear program parameterized by coefficients (cm(f, g))1≤m≤D for (f, g) ∈ R. p. 4
Where the paper says it

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.

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. p. 4
Where the paper says it

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.

779.

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

Where the paper says it

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.

2, where the estimate c1 − Xm≥3cm > 0. p. 0
Where the paper says it

773 ≤ KG ≤ 1. Furthermore, numerical heuristics suggest the estimate KG ≈ 1.

561831528950464991 > 1000000/1779893. The lower bound is certified by Theorem 4. p. 1
Where the paper says it

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.

1, where the game and its one-variable reduction show SDP(Q)/ OPT(Q) ≥ 1−on(1) v∞(q) = KG − on(1). p. 1
Where the paper says it

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.

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

Where the paper says it

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.

5618556, 1/0.5618556 = 1.7798167.

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

Where the paper says it

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].

773.

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

Where the paper says it

773 ≤ KG ≤ 1. 7799 Our main conceptual innovation is a primal/dual method for algorithmically searching for upper and lower bounds on KG.

py to check the upper bound. p. 1
Where the paper says it

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.

The verification confirms that all checks pass and the final bound is KG ≤ 5. p. 9
Where the paper says it

It remains to pass from B to K. The set K is exactly the set of barycenters of probability measures on B.

996940779766870 · 10−8.

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

  1. 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.

  2. 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 involving extensive numerical inequalities proven using AI tools, which would have been impossible to obtain by hand.

  3. 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).

  4. 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].

  5. Polynomial threshold function optimization: The system can identify asymptotic ∞-to-1 optimizers of Q which are shown to exist and can be of the form f = 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

Related papers