Certified upper bounds for two sum-difference exponents

A mix of human-written and AI-generated textHuman understanding: all partsmath.CO — Combinatoricsmath.NT — Number Theorycs.IT — Information Theory

Contributed by Tejasvi Singh Tomar ↗

Version 1 / Nov 15, 2026 / CC BY 4.0

Abstract

For finite sets A,BA,B of real numbers and G⊆A×BG\subseteq A\times B, Katz and Tao proved in 1999 that {a−b:(a,b)∈G}\{a-b:(a,b)\in G\} has at most N11/6N^{11/6} elements whenever AA, BB and {a+b:(a,b)∈G}\{a+b:(a,b)\in G\} have at most NN elements; by an argument of Bourgain, bounds of this kind give lower bounds for the dimension of Kakeya sets. We lower the exponent 11/611/6 to 1.82731.8273, and to 1.82951.8295 in every abelian group. We also prove ∣X−Y∣≤∣X+Y∣1.4209|X-Y|\le|X+Y|^{1.4209} for all finite sets X,YX,Y of integers, improving the exponent 1.45431.4543 of Kleinwaks; through his transfer theorem, this lowers the upper bound for the sum-difference constant of Gyarmati, Hennecart and Ruzsa from 1.31241.3124 to 1.29621.2962. 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.

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

References

  1. 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
  2. J. Bourgain, On the dimension of Kakeya sets and related maximal inequalities , Geom. Funct. Anal. 9 (1999), 256--282.
  3. E. P. Csirmaz and L. Csirmaz, Information inequalities for five random variables , Computation 14 (2026), no. 2, article 42; arXiv:2512.23316.arXiv
  4. R. Dougherty, C. Freiling and K. Zeger, Non-Shannon information inequalities in four random variables , arXiv:1104.3602, 2011.arXiv
  5. A. Farnamfar, Sharp optimality of 11/611/6 for literal ladder constructions , Zenodo, doi:10.5281/zenodo.23337952 (https://doi.org/10.5281/zenodo.23337952), 2026.DOI
  6. 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
  7. G. A. Freiman and V. P. Pigarev, The relation between the invariants RR and TT (Russian), Kalinin. Gos. Univ., Moscow, 1973, 172--174.
  8. 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
  9. B. Green and I. Z. Ruzsa, On the arithmetic Kakeya conjecture of Katz and Tao , Period. Math. Hungar. 78 (2019), 135--151.
  10. 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
  1. F. Hennecart, G. Robert and A. Yudin, On the number of sums and differences , Astérisque 258 (1999), 173--178.
  2. Q. Huangfu and J. A. J. Hall, Parallelizing the dual revised simplex method , Math. Program. Comput. 10 (2018), 119--142.
  3. N. H. Katz and T. Tao, Bounds on arithmetic projections, and applications to the Kakeya conjecture , Math. Res. Lett. 6 (1999), 625--630.
  4. N. H. Katz and T. Tao, New bounds for Kakeya problems , J. Anal. Math. 87 (2002), 231--263.
  5. 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
  6. M. Lemm, New counterexamples for sums-differences , Proc. Amer. Math. Soc. 143 (2015), 3863--3868.
  7. M. Madiman, On the entropy of sums , in: Proc. IEEE Information Theory Workshop, Porto, 2008, 303--307.
  8. The mathlib Community, The Lean mathematical library , in: Proc. 9th ACM SIGPLAN Int. Conf. Certified Programs and Proofs (CPP 2020), 2020, 367--381.
  9. F. Matúš, Infinitely many information inequalities , in: Proc. IEEE Int. Symp. Information Theory, Nice, 2007, 41--44.
  10. 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
  11. Mosaic Intelligence, Certified sum-difference lower-bound certificates for C3aC_{3a}, C3bC_{3b}, and C3cC_{3c} , certificate archive, doi:10.5281/zenodo.20794135 (https://doi.org/10.5281/zenodo.20794135), 2026.DOI
  12. 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.
  13. G. Petridis, New proofs of Plünnecke-type estimates for product sets in groups , Combinatorica 32 (2012), 721--733.
  14. I. Z. Ruzsa, An analog of Freiman's theorem in groups , Astérisque 258 (1999), 323--326.
  15. I. Z. Ruzsa, Sumsets and entropy , Random Structures Algorithms 34 (2009), 1--10.
  16. T. Tao, Sumset and inverse sumset theory for Shannon entropy , Combin. Probab. Comput. 19 (2010), 603--639.
  17. T. Tao, Sum-difference exponents for boundedly many slopes, and rational complexity , arXiv:2511.15135, 2025.arXiv
  18. T. Tao et al., Optimization constants in mathematics , https://teorth.github.io/optimizationproblems/, pages 3a and 3b, accessed October 19, 2026.link
  19. 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
  20. Z. Zhang and R. W. Yeung, On characterization of entropy function via information inequalities , IEEE Trans. Inform. Theory 44 (1998), 1440--1452.

Version history

  1. v1 · 16 pagesSubmitted by Tejasvi Singh TomarPublished on Zenodo: https://doi.org/10.5281/zenodo.23716680CurrentNov 15, 2026