Subexponential bounds for distinct-distance subsets
Version 1 / Nov 21, 2026 / CC BY 4.0
Abstract
Let be the least such that every set of points in contains points whose pairwise distances are all distinct. For every fixed we prove , which answers the subexponential-growth question in Erdős problem 1088. A rank–rectangle theorem gives a large rectangle on which a single row or column function describes the entries of a matrix covered by finitely many such functions. The proof uses hyperplane rounding and rank bounds. A geometric induction and successive halving of the affine dimension give the estimate. The pinned Lean source verifies the original subexponential target. The written manuscript supplies the sharper dependence on the number of types and retains its draft status.
Provenance statement
References
- K. Ball, An elementary introduction to modern convex geometry, in: Flavors of Geometry , MSRI Publications 31, Cambridge University Press, 1997, pp. 1--58.
- A. Blokhuis, Few-distance sets , CWI Tract 7, Centrum voor Wiskunde en Informatica, Amsterdam, 1984.
- Y. Caro, New results on the independence number, Technical Report, Tel Aviv University, 1979.
- T. F. Bloom, Erdős Problem #1088, https://www.erdosproblems.com/1088. The problem page records the Erdős--Straus bound and its source.link
- D. Gavinsky and S. Lovett, En route to the log-rank conjecture: new reductions and equivalent formulations, in: Automata, Languages, and Programming (ICALP 2014) , Lecture Notes in Computer Science 8572, Springer, 2014, pp. 514--524.
- M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42 (1995), 1115--1145.
- Z. Hunter, A. Milojević, B. Sudakov and I. Tomon, Disjoint pairs in set systems and combinatorics of low rank matrices, arXiv:2411.13510.arXiv
- F. John, Extremum problems with inequalities as subsidiary conditions, in: Studies and Essays Presented to R. Courant on his 60th Birthday , Interscience, New York, 1948, pp. 187--204.
- D. Kőnig, Gráfok és mátrixok, Matematikai és Fizikai Lapok 38 (1931), 116--119.
- S. Lovett, Communication is bounded by root of rank, J. ACM 63 (2016), Article 1; arXiv:1306.1877.arXiv
Show all 16 referencesShow fewer references
- Prior in-project work: research notes on Erdős Problem #1088 by a peer AI session of the same project (notes file e1088.md , 2026), unpublished.
- T. Rothvoß, A direct proof for Lovett's bound on the communication complexity of low rank matrices, arXiv:1409.6366, 2014.arXiv
- W. F. Sheppard, On the application of the theory of error to cases of normal distribution and normal correlation, Philos. Trans. Roy. Soc. London Ser. A 192 (1899), 101--167.
- N. Singer and M. Sudan, Point-hyperplane incidence geometry and the log-rank conjecture, arXiv:2101.09592 (version 5, 2022).arXiv
- B. Sudakov and I. Tomon, Matrix discrepancy and the log-rank conjecture, arXiv:2311.18524.arXiv
- V. K. Wei, A lower bound on the stability number of a simple graph, Bell Laboratories Technical Memorandum 81-11217-9, 1981.
Version history
- v1 · 33 pagesSubmitted by Liam KruerManuscript accompanying Justin Sun Prize submission JSP-000905. Pinned TeX, formal source, and build records are listed at https://github.com/TheJustinSunPrize/awards/pull/5557CurrentNov 21, 2026