Certified upper bounds for two sum-difference exponents
Version 1 / Nov 15, 2026 / CC BY 4.0
Abstract
For finite sets of real numbers and , Katz and Tao proved in 1999 that has at most elements whenever , and have at most elements; by an argument of Bourgain, bounds of this kind give lower bounds for the dimension of Kakeya sets. We lower the exponent to , and to in every abelian group. We also prove for all finite sets of integers, improving the exponent of Kleinwaks; through his transfer theorem, this lowers the upper bound for the sum-difference constant of Gyarmati, Hennecart and Ruzsa from to . Both proofs add up entropy inequalities among integer combinations of coordinates of several copies of a random pair, with rational weights found by linear programming; all four bounds are also proved in Lean 4.
References
- T. F. Bloom, Erdős problem #1097 , https://www.erdosproblems.com/1097, accessed October 20, 2026; the problem was posed at the 1989 Great Western Number Theory problem session.link
- J. Bourgain, On the dimension of Kakeya sets and related maximal inequalities , Geom. Funct. Anal. 9 (1999), 256--282.
- E. P. Csirmaz and L. Csirmaz, Information inequalities for five random variables , Computation 14 (2026), no. 2, article 42; arXiv:2512.23316.arXiv
- R. Dougherty, C. Freiling and K. Zeger, Non-Shannon information inequalities in four random variables , arXiv:1104.3602, 2011.arXiv
- A. Farnamfar, Sharp optimality of for literal ladder constructions , Zenodo, doi:10.5281/zenodo.23337952 (https://doi.org/10.5281/zenodo.23337952), 2026.DOI
- A. Farnamfar, Sharp colour bounds and structural obstructions for three-direction sums--differences constructions , Zenodo, doi:10.5281/zenodo.23385419 (https://doi.org/10.5281/zenodo.23385419), 2026.DOI
- G. A. Freiman and V. P. Pigarev, The relation between the invariants and (Russian), Kalinin. Gos. Univ., Moscow, 1973, 172--174.
- B. Georgiev, J. Gómez-Serrano, T. Tao and A. Z. Wagner, Mathematical exploration and discovery at scale , arXiv:2511.02864, 2025; published as Mathematical discovery and exploration can be done at scale , Proc. Natl. Acad. Sci. USA 123 (2026), no. 40, e2536158123. Problem numbers refer to the arXiv version.arXiv
- B. Green and I. Z. Ruzsa, On the arithmetic Kakeya conjecture of Katz and Tao , Period. Math. Hungar. 78 (2019), 135--151.
- K. Gyarmati, F. Hennecart and I. Z. Ruzsa, Sums and differences of finite sets , Funct. Approx. Comment. Math. 37 (2007), 175--186.
Show all 30 referencesShow fewer references
- F. Hennecart, G. Robert and A. Yudin, On the number of sums and differences , Astérisque 258 (1999), 173--178.
- Q. Huangfu and J. A. J. Hall, Parallelizing the dual revised simplex method , Math. Program. Comput. 10 (2018), 119--142.
- N. H. Katz and T. Tao, Bounds on arithmetic projections, and applications to the Kakeya conjecture , Math. Res. Lett. 6 (1999), 625--630.
- N. H. Katz and T. Tao, New bounds for Kakeya problems , J. Anal. Math. 87 (2002), 231--263.
- L. J. Kleinwaks, Improved sum-difference inequalities in abelian groups , proof paper, version 1.1 (October 6, 2026), and Lean formalization, https://github.com/kleinwaks/sum-difference, archived as doi:10.5281/zenodo.23200803 (https://doi.org/10.5281/zenodo.23200803).DOI
- M. Lemm, New counterexamples for sums-differences , Proc. Amer. Math. Soc. 143 (2015), 3863--3868.
- M. Madiman, On the entropy of sums , in: Proc. IEEE Information Theory Workshop, Porto, 2008, 303--307.
- The mathlib Community, The Lean mathematical library , in: Proc. 9th ACM SIGPLAN Int. Conf. Certified Programs and Proofs (CPP 2020), 2020, 367--381.
- F. Matúš, Infinitely many information inequalities , in: Proc. IEEE Int. Symp. Information Theory, Nice, 2007, 41--44.
- Mosaic Intelligence, A mechanized certificate ladder and a certified Shannon wall for the Katz--Tao sum--difference problem , Zenodo, doi:10.5281/zenodo.20646386 (https://doi.org/10.5281/zenodo.20646386), 2026.DOI
- Mosaic Intelligence, Certified sum-difference lower-bound certificates for , , and , certificate archive, doi:10.5281/zenodo.20794135 (https://doi.org/10.5281/zenodo.20794135), 2026.DOI
- 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.
- G. Petridis, New proofs of Plünnecke-type estimates for product sets in groups , Combinatorica 32 (2012), 721--733.
- I. Z. Ruzsa, An analog of Freiman's theorem in groups , Astérisque 258 (1999), 323--326.
- I. Z. Ruzsa, Sumsets and entropy , Random Structures Algorithms 34 (2009), 1--10.
- T. Tao, Sumset and inverse sumset theory for Shannon entropy , Combin. Probab. Comput. 19 (2010), 603--639.
- T. Tao, Sum-difference exponents for boundedly many slopes, and rational complexity , arXiv:2511.15135, 2025.arXiv
- T. Tao et al., Optimization constants in mathematics , https://teorth.github.io/optimizationproblems/, pages 3a and 3b, accessed October 19, 2026.link
- T. S. Tomar, Certificates, programs and Lean proofs for ``Certified upper bounds for two sum-difference exponents'' , Zenodo, doi: (https://doi.org/\ZenodoDOI), 2026.link
- Z. Zhang and R. W. Yeung, On characterization of entropy function via information inequalities , IEEE Trans. Inform. Theory 44 (1998), 1440--1452.
Version history
- v1 · 16 pagesSubmitted by Tejasvi Singh TomarPublished on Zenodo: https://doi.org/10.5281/zenodo.23716680CurrentNov 15, 2026