HEXAGONbeta

Certified lower bounds for the first and the signed third autocorrelation constants

A mix of human-written and AI-generated textHuman understanding: all partsmath.CA — Classical Analysis and ODEsmath.NT — Number Theorymath.CO — Combinatoricsmath.OC — Optimization and Control

Contributed by Tejasvi Singh Tomar ↗

Version 1 / Nov 12, 2026 / CC BY 4.0

Abstract

Let C1C_1 be the largest constant such that sup⁡∣t∣≤1/2∫f(t−x)f(x) dx≥C1(∫−1/41/4f)2\sup_{|t|\le 1/2}\int f(t-x)f(x)\,dx\ge C_1\bigl(\int_{-1/4}^{1/4}f\bigr)^2 for every nonnegative function ff on the real line. We prove C1≥1.337C_1\ge 1.337, improving the bound 1.29371.2937 of Kim and Pilanci, by a spatial branch-and-bound over the masses of ff on equal bins. Consequently, for every large gg, every gg-Sidon set in {1,…,N}\{1,\dots,N\} has fewer than 1.2231gN1.2231\sqrt{gN} elements once NN is large enough in terms of gg. For real-valued ff supported in [−1/4,1/4][-1/4,1/4], let C3C_3 and C3′C_3' be the analogous constants for the essential suprema of ∣f∗f∣|f*f| and of f∗ff*f; no lower bound better than the trivial bound 11 was recorded for them. We prove C3≥C3′≥4/3C_3\ge C_3'\ge 4/3 with the argument principle. Both proofs are computer-assisted, and both theorems are also proved in Lean 4.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23715655

References

  1. A. Novikov et al., AlphaEvolve: A coding agent for scientific and algorithmic discovery , arXiv:2506.13131, 2025.arXiv
  2. F. Bianchi, Y. Kwon, A. Pappu and J. Zou, Harnessing the collective intelligence of AI agents in the wild for new discoveries , arXiv:2606.10402, 2026.arXiv
  3. J. Cilleruelo, I. Z. Ruzsa and C. Vinuesa, Generalized Sidon sets , Adv. Math. 225 (2010), 2786--2807.
  4. A. Cloninger and S. Steinerberger, On suprema of autoconvolutions with an application to Sidon sets , Proc. Amer. Math. Soc. 145 (2017), 3191--3200.
  5. Together AI, EinsteinArena state-of-the-art results , https://github.com/togethercomputer/EinsteinArena-new-SOTA, 2026.link
  6. P. J. Goulart and Y. Chen, Clarabel: An interior-point solver for conic programs with quadratic objectives , arXiv:2405.12762, 2024.arXiv
  7. M. German, C1dC_{1d} upper-bound certificate (600 cells) , GitHub repository, https://github.com/steps-re/c1d-certificate, commit 9a09149 , accessed October 2026.link
  8. B. Georgiev, J. Gómez-Serrano, T. Tao and A. Z. Wagner, Mathematical exploration and discovery at scale , arXiv:2511.02864, 2025.arXiv
  9. Q. Huangfu and J. A. J. Hall, Parallelizing the dual revised simplex method , Math. Program. Comput. 10 (2018), 119--142.
  10. P. Ivanisvili and X. Xie, Grokability in five inequalities , arXiv:2605.05193, 2026.arXiv
Show all 26 referencesShow fewer references
  1. P. Jana et al., MILO: Automated harness discovery via orchestrated multi-agent evolution , arXiv:2609.38349, 2026.arXiv
  2. F. Johansson, Arb: efficient arbitrary-precision midpoint-radius interval arithmetic , IEEE Trans. Comput. 66 (2017), 1281--1292.
  3. A. Kharlamova, J. Kang, B. He and S. Liu, Certificate for C1d≤1.457854884921989C_{1d}\le1.457854884921989 (signed third autocorrelation constant) , Zenodo, doi:10.5281/zenodo.23541324, 2026.DOI
  4. S. Kim and M. Pilanci, AI-assisted discovery of convex relaxations via dual agents , Proc. 43rd Int. Conf. Machine Learning, PMLR 306 , 2026; arXiv:2606.31182.arXiv
  5. L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language , in: Automated Deduction -- CADE 28, Lecture Notes in Comput. Sci. 12699 , Springer, 2021, 625--635.
  6. The mathlib Community, The Lean mathematical library , in: Proc. 9th ACM SIGPLAN Int. Conf. Certified Programs and Proofs (CPP 2020), 2020, 367--381.
  7. G. P. McCormick, Computability of global solutions to factorable nonconvex programs. I. Convex underestimating problems , Math. Program. 10 (1976), 147--175.
  8. M. Matolcsi and C. Vinuesa, Improved bounds on the supremum of autoconvolutions , J. Math. Anal. Appl. 372 (2010), 439--447.
  9. A. Neumaier and O. Shcherbina, Safe bounds in linear and mixed-integer linear programming , Math. Program. 99 (2004), 283--296.
  10. D. Davis, P. Ivanisvili, T. Tao and contributors, Optimization constants in mathematics , GitHub repository, https://github.com/teorth/optimizationproblems, 2026. Constant 1d: https://teorth.github.io/optimizationproblems/constants/1d.html, accessed October 2026.link
  11. A. Piterbarg, J. Bajaj and D. Vincent, A new lower bound for the supremum of autoconvolutions , GitHub repository, https://github.com/AndreiPiterbarg/sidon-autocorrelation, commit 1ed5889 , accessed October 2026.link
  12. The python-flint developers, python-flint: Python bindings for FLINT , version 0.9.0, https://github.com/flintlib/python-flint.link
  13. H. D. Sherali and W. P. Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems , SIAM J. Discrete Math. 3 (1990), 411--430.
  14. H. D. Sherali and B. M. P. Fraticelli, Enhancing RLT relaxations via a new class of semidefinite cuts , J. Global Optim. 22 (2002), 233--261.
  15. N. Z. Shor, Quadratic optimization problems , Soviet J. Comput. Systems Sci. 25 (1987), 1--11.
  16. A. Schinzel and W. M. Schmidt, Comparison of L1L^1- and L∞L^\infty-norms of squares of polynomials , Acta Arith. 104 (2002), 283--296.

Version history

  1. v1 · 19 pagesSubmitted by Tejasvi Singh TomarPublished on Zenodo: https://doi.org/10.5281/zenodo.23715655CurrentNov 12, 2026