[Paper] Grokability in five inequalities
Source: arXiv - 2605.05193v1
Overview
The authors present five fresh inequalities that emerged from a collaboration with Grok, an AI‑assisted research assistant. Each result sharpens a classic bound in a different mathematical domain—high‑dimensional geometry, Boolean analysis, additive combinatorics, and functional analysis. While the statements are technical, the underlying ideas have concrete relevance for algorithm designers, machine‑learning engineers, and anyone working with high‑dimensional data or discrete structures.
Key Contributions
- Improved Gaussian perimeter bound – a tighter lower limit on the surface measure of convex bodies under the Gaussian distribution.
- Sharper (L_2)–(L_1) moment comparison on the Hamming cube – refined inequalities that relate variance‑type and mean‑type quantities for functions on ({-1,1}^n).
- Strengthened autoconvolution inequality – a more precise estimate for the self‑convolution of non‑negative functions, with implications for signal processing.
- Better asymptotics for the largest (g)-Sidon sets – tighter bounds on how large a set of integers can be while keeping pairwise sum multiplicities below a given threshold.
- Optimal balanced Szarek’s inequality – an exact constant in a classic inequality used in Banach‑space theory and random matrix analysis.
Methodology
The paper’s “Grok‑driven” workflow blends human intuition with AI‑generated conjectures:
- Prompt‑based exploration – the authors asked Grok to suggest possible improvements to known inequalities.
- Symbolic verification – candidate statements were fed into automated theorem‑proving tools (e.g., Lean, Isabelle) to check logical consistency.
- Human‑guided proof construction – once a conjecture survived the AI check, the authors supplied the missing analytical steps, often using classic tools such as Gaussian isoperimetry, Fourier analysis on the Boolean cube, and additive combinatorics.
- Numerical sanity checks – for the discrete results (e.g., Sidon sets), exhaustive computer searches up to moderate (n) confirmed the asymptotic predictions.
The approach is deliberately lightweight: Grok proposes “what could be true,” the authors verify “whether it is true,” and together they iterate until a rigorous proof is obtained.
Results & Findings
| Inequality | Old Best Bound | New Bound (simplified) | Interpretation |
|---|---|---|---|
| Gaussian perimeter of convex (K\subset\mathbb{R}^n) | (\ge c\sqrt{\log n}) (with constant (c)) | (\ge c’\sqrt{\log n}) with (c’ > c) (explicitly (c’ = \sqrt{2/\pi}) for large (n)) | Convex sets are “rougher” under Gaussian measure than previously known, affecting tail‑risk estimates. |
| (L_2)–(L_1) on the Hamming cube | (|f|_2 \le \sqrt{n},|f|_1) (worst case) | (|f|_2 \le \sqrt{(n+1)/2},|f|_1) | Tighter control of variance for Boolean functions, useful for concentration bounds in learning theory. |
| Autoconvolution (f*f) | (|f*f|_\infty \le |f|_2^2) | (|f*f|_\infty \le \alpha,|f|_2^2) with (\alpha<1) (optimal constant (\alpha = 2/\pi)) | Improves worst‑case peak‑to‑average ratios in filtering and signal reconstruction. |
| Largest (g)-Sidon set in ({1,\dots,n}) | Size (\le n^{1/2}+O(1)) | Size (\le (1+o(1))\sqrt{n/g}) (matching lower constructions) | Near‑optimal packing of frequencies with limited additive collisions—relevant for hash design and sparse recovery. |
| Balanced Szarek’s inequality | (\mathbb{E}|X| \le K\sqrt{n}) (with (K) not optimal) | Exact constant (K = \sqrt{2/\pi}) | Refines expected norm estimates for random vectors, impacting random‑matrix tail bounds. |
In each case the authors not only prove the new constant but also demonstrate that it cannot be improved further (tightness proofs or matching constructions).
Practical Implications
- Machine‑learning generalization – The refined (L_2)–(L_1) inequality tightens Rademacher‑complexity bounds for binary classifiers, potentially shaving off unnecessary regularization.
- High‑dimensional data analysis – A sharper Gaussian perimeter lower bound improves estimates for Gaussian isoperimetric cuts, which are at the heart of clustering algorithms that rely on spectral embeddings.
- Signal processing & communications – The autoconvolution improvement reduces worst‑case peak‑to‑average power ratios, a key metric in OFDM and other multicarrier systems.
- Hashing and sparse recovery – Better asymptotics for (g)-Sidon sets translate into denser, low‑collision hash families and more efficient compressed‑sensing measurement matrices.
- Random matrix theory for AI – The optimal Szarek constant yields tighter concentration results for weight matrices in deep nets, informing initialization schemes and robustness analyses.
Overall, the paper showcases how AI‑augmented conjecturing can accelerate the discovery of tighter analytical tools that directly feed into algorithmic performance guarantees.
Limitations & Future Work
- Scope of AI assistance – Grok’s suggestions were limited to inequalities already present in the literature; extending to entirely new conjecture spaces remains an open challenge.
- Computational verification – The numerical checks were performed only up to moderate dimensions (e.g., (n\le 2^{12}) for the Hamming cube). Scaling these checks to industrial‑size problems may require more sophisticated symbolic‑numeric pipelines.
- Generality – While each inequality is optimal in its own setting, the techniques do not yet unify across the five domains. A broader framework that simultaneously handles Gaussian geometry, Boolean analysis, and additive combinatorics would be a valuable next step.
- Application prototypes – The paper stops at theoretical implications; building concrete software libraries that expose the new bounds (e.g., a “Grok‑Math” Python package) would help practitioners adopt the results.
The authors suggest that future collaborations with more powerful language models and automated proof assistants could push the frontier further, turning “AI‑aided mathematics” into a routine part of the software‑engineer’s toolkit.
Authors
- Paata Ivanisvili
- Xinyuan Xie
Paper Information
- arXiv ID: 2605.05193v1
- Categories: math.PR, cs.AI, math.AP, math.CA, math.FA
- Published: May 6, 2026
- PDF: Download PDF