CS Paper Radar

Sharper Bounds for the Complex Grothendieck Constant

Steven Heilman, Chris Jones, Giulio Malavolta

cs.DS math.FAquant-ph ·submitted 2026-09-21 22:38 UTC · v1
theory

Abstract

We show that $1.4<K_G^{\mathbb{C}}<1.404898554746$, where $K_G^{\mathbb{C}}$ is the complex Grothendieck constant. The upper bound improves on Haagerup's bound of $1.40490913\ldots$ from 1987, and the lower bound improves on Davie's bound of $1.33807$ from 1984. The upper bound combines ideas from the real and noncommutative complex cases of Grothendieck's inequality.

Comment
21 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Primal/Dual Method for the Grothendieck Constant

cs.CC math.FA ·2026-10-07 ·Steven Heilman, Chris Jones, Giulio Malavolta
similarity 0.61
Abstract

We determine the hundredths digit of the real Grothendieck constant by proving $1.773 \leq K_G \leq 1.7799$. Furthermore, numerical heuristics suggest the estimate $K_G \approx 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 {\em 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).

0.33

New Lower and Upper Bounds for the Grothendieck Constant

cs.CC cs.DS ·2026-08-11 ·Rahul Saha, Alan Li, Anton Xue, Swarat Chaudhuri, Adam Klivans +2 more
theoryhighly cited similarity 0.58
Abstract

We establish new bounds on the Grothendieck constant $K_G$: \[ \frac{6π}{11} \le K_G \le \fracπ{2\log(1+\sqrt2)} - 10^{-4}. \] Methodologically, our lower bound approach differs from previous works by establishing limitations on the asymptotically optimal Krivine schemes, rather than giving explicit constructions of gap instances. Our upper bound is obtained by proposing and analyzing the first asymptotic construction of rounding schemes, whereas previous works only consider low-dimensional schemes. Together, these bounds determine the previously unknown tenths digit of $K_G$ to be $7$. The bounds were discovered by a long-running collaborative effort of humans and a long-horizon AI research system that we engineered.

0.43

A Counterexample to the Gyarmati-Matolcsi-Ruzsa Conjecture

cs.IT math.CO ·2026-10-30 ·Chandra Nair, Aref Namayandeh, Zhaobang Zhu
similarity 0.51
Abstract · 12 pages

We provide a counterexample to the non-abelian Gyarmati-Matolcsi-Ruzsa conjecture. The construction comes from an equivalent maximal-coupling entropy inequality, for which a counterexample can be found in a lower-dimensional group. We give an explicit cardinality counterexample in $D_4^{14}$, the fourteenth direct power of the dihedral group of order $8$.

0.48

Polynomial Swap Coboundary Expansion with Applications to LTCs and PCPs

cs.CC math.COcs.DMmath.GR ·2026-11-12 ·Yotam Dikstein, Izhar Oppenheim, Inga Valentiner-Branth
theory similarity 0.49
Abstract · 63 pages

Swap coboundary expansion, introduced independently by Bafna--Minzer and Dikstein--Dinur, is a local-to-global property that underlies agreement tests in the low-acceptance regime and recent constructions of succinct PCPs. Previous works obtained bounds of $\exp(-O(\sqrt{r}))$ for the $r$-swap coboundary expansion of Chapman--Lubotzky complexes. We establish the first inverse-polynomial bounds for bounded-degree complexes: suitable skeleta of Kac--Moody--Steinberg (KMS) complexes have $r$-swap coboundary expansion at least $r^{-O(1)}$. Our theorem supplies a key ingredient in forthcoming work of Ben Yaacov--Dikstein--Liu, which obtains local tests for sparse algebraic codes with guarantees even at arbitrarily small acceptance probability. These tests use $\exp(\operatorname{poly}(1/\varepsilon))$ queries and guarantee that any word accepted with probability at least $\varepsilon$ agrees with a codeword on an $\varepsilon^{O(1)}$ fraction of coordinates. Separately, substituting our bound into the existing analysis of Bafna--Minzer--Vyas--Yun improves the soundness dependence of their two-query PCP construction, giving perfect completeness, soundness $\varepsilon$, and proof length $n(\log n)^{\exp(\operatorname{poly}(1/\varepsilon))}$. Our proof exploits the product structure of the groups arising in KMS complexes. The main new ingredient is a decomposition lemma for Dehn functions, which separates the analysis of group relations into independent problems on much smaller factors, with only polynomial overhead.

0.35

From an entropic inequality for sums in abelian groups to the theorems of Ruzsa and Plünnecke

cs.IT math.CO ·2026-10-08 ·Chandra Nair, Aref Namayandeh, Zhaobang Zhu
similarity 0.48
Abstract · 12 pages

We give a direct information-theoretic proof of the Plünnecke--Ruzsa inequalities for finite subsets of abelian groups. The argument rests on an elementary coupling inequality proved by maximizing joint entropy, without tensor powers or asymptotic constructions. It also yields Ruzsa's sumset triangle inequality and an extension to non-abelian groups.

0.13

Bounds on the real tensor rank of octonion multiplication

cs.CC ·2026-08-17 ·Hardik Jain
theorycode/data similarity 0.47
Abstract · Code at https://github.com/hxrdxkxvxd/octonion-rank

The tensor rank of a bilinear map is the least number of multiplications any bilinear algorithm needs to compute it; for the multiplication of an algebra it measures how cheaply the algebra can be multiplied at all. For the even-dimensional real normed division algebras it is $3$ for the complex numbers and $8$ for the quaternions, both classical, while for the octonions $\mathbb{O}$ only a range was known: at least $15$ (Fiduccia and Zalcstein, 1977) and at most $30$ (Cariow and Cariowa). We prove $$18 \le \operatorname{R}_{\mathbb{R}}(T_{\mathbb{O}}) \le 25.$$ The lower bound peels the eight slices of $T_{\mathbb{O}}$ down to two and bounds the rank of the surviving pencil through the octonion norm. Nothing in it is special to dimension $8$: the same steps give $\operatorname{R}_{\mathbb{R}}(T_A) \ge \frac{5}{2}n - 2$ for every real normed division algebra $A$ of even dimension $n$, sharp for $\mathbb{C}$ and $\mathbb{H}$ and the best bound we know for $\mathbb{O}$. The upper bound is a separate construction, an explicit rank-$25$ decomposition certified by a Krawczyk argument, in exact rational arithmetic, to sit within $10^{-6}$ of an exact one. The same two arguments pin down the rank of a smaller three-slice quaternion tensor $τ$, giving $\operatorname{R}_{\mathbb{R}}(τ) = 7$. The Lean 4 kernel checks the lower bounds and the Krawczyk existence principle; the accompanying scripts check the certificate's finitely many exact-rational inequalities.

0.57

Long-Horizon AI Research for Grothendieck Constant: A Case Study in Human-AI Mathematical Collaboration

cs.AI cs.CCcs.HCmath.FA ·2026-08-11 ·Alan Li, Rahul Saha, Anton Xue, Swarat Chaudhuri, Adam Klivans +2 more
similarity 0.46
Abstract

AI agents are increasingly used in mathematics research, but it is often unclear how to use them effectively. Towards this, we present an extensive case study of how AI was used to improve bounds on the Grothendieck constant $K_G$, which captures the hardness between combinatorial problems and their continuous relaxations. Specifically, while the precise value of $K_G$ is not known, we recently tightened the best known bounds to \[ \frac{6π}{11} \;\le\; K_G \;\le\; \fracπ{2\log(1+\sqrt2)} - 10^{-4}. \] Crucially, these improvements were achieved using an AI research system that could arrive at insights deemed novel by domain experts. We give a detailed discussion of our experience using AI for mathematics research, particularly touching upon its strengths and weaknesses, as well as our experience with creating ideal conditions for AI to arrive at breakthrough insights.

0.34

Tensor value and the 9/4 bound for matrix multiplication

cs.CC math.RT ·2026-11-06 ·Mahmut Levent Doğan, Vladimir Lysikov, Keiya Sakabe, Michael Walter
theory similarity 0.45
Abstract

We give an exposition of OpenAI's recent result that the exponent of matrix multiplication is at most 9/4 valid over every field. Our main tool is a fractional symmetrized variant of the tensor value introduced by Coppersmith and Winograd, used in place of spectral points (tensor characters) in the original proof. We prove a superadditivity inequality for a power of this value on partially direct sums, whose summands share one tensor factor and occupy independent subspaces in the other two. Together with the degenerations of polynomial multiplication tensors from the OpenAI proof, this inequality yields the bound.

0.08