Erdős problem 706 and uniform multiscale refinements

Primarily AI-generated textHuman understanding: no partsmath.CO — Combinatorics

Contributed by Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer ↗

Version 1 / Nov 21, 2026 / CC BY 4.0

Abstract

We give a detailed exposition of the OpenAI–Galán argument that resolves Erdős problem 706, including character rigidity, its compact-tower and radial arguments, and the transfer from arbitrary colorings to weak measurable colorings for algebraic distances. Galán’s application of Bukh’s theorem gives finite planar graphs with rr forbidden distances and chromatic number greater than 4.0485r4.0485^r. We also prove a uniform product estimate for normalized compact distance clusters and give quantitative fixed-ratio bounds from weighted unit-distance graphs. The linked Lean verification covers the original negative answer and the elementary bounds 2r≤L(r)≤7r2^r\le L(r)\le7^r.

Author comments: Revised manuscript accompanying Justin Sun Prize submission JSP-000576. Original source package, attribution and verification scope: https://github.com/Ghuffy1/erdos-706-lean/tree/2a22f736eea81c04ec696c1b1d7f770b4417f5f7

Provenance statement

The manuscript credits OpenAI and Sergi Galán for the original argument and OpenAI Codex assistance with exposition, mathematical exploration, checks and drafting. It links the upstream licenses and exact source revisions. The four affiliations inferred by the original package were omitted.

References

  1. G. Ambrus, A. Csiszárik, M. Matolcsi, D. Varga and P. Zsámboki, The density of planar sets avoiding unit distances , Math. Program. 207 (2024), 303--327, https://arxiv.org/abs/2207.14179v3.link
  2. B. Bekka, P. de la Harpe and A. Valette, Kazhdan's Property (T) , New Mathematical Monographs 11, Cambridge University Press, 2008, DOI 10.1017/CBO9780511542749. Theorem locators refer to the author manuscript of February 23, 2007.DOI
  3. T. Bellitto, A. Pêcher and A. Sédillot, On the density of sets of the Euclidean plane avoiding distance 11 , Discrete Math. Theor. Comput. Sci. 23 (2021), no. 1, DOI 10.46298/dmtcs.5153.DOI
  4. B. Bukh, Measurable sets with excluded distances , Geom. Funct. Anal. 18 (2008), 668--697.
  5. D. Castro-Silva, Geometrical sets with forbidden configurations , Forum Math. Sigma 11 (2023), e44, DOI 10.1017/fms.2023.43.DOI
  6. R. Chen, Decompositions and measures on countable Borel equivalence relations , arXiv:1801.02767v2, Section 3, Theorem 3.1 (Farrell--Varadarajan), https://arxiv.org/abs/1801.02767v2.arXiv
  7. J. Davies, Measurable obstructions for unmeasurable colourings , preprint, arXiv:2610.12301v1 (2026).arXiv
  8. N. G. de Bruijn and P. Erdős, A colour problem for infinite graphs and a problem in the theory of relations , Indag. Math. 13 (1951), 369--373.
  9. F. W. J. Olver and L. C. Maximon, Bessel functions , Chapter 10 of the NIST Digital Library of Mathematical Functions , https://dlmf.nist.gov/10 , accessed November 4, 2026.link
  10. E. DeCorte, F. M. de Oliveira Filho and F. Vallentin, Complete positivity and distance-avoiding sets , Math. Program. 191 (2022), 487--558, DOI 10.1007/s10107-020-01562-6.DOI
Show all 22 referencesShow fewer references
  1. P. Erdős, On the combinatorial problems which I would most like to see solved , Combinatorica 1 (1981), 25--42.
  2. T. F. Bloom, Erdős Problem #706 , https://www.erdosproblems.com/706.link
  3. H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions , J. Analyse Math. 31 (1977), 204--256, DOI 10.1007/BF02813304.DOI
  4. S. Galán, Measurable density bounds hold for all colourings of the plane with algebraic forbidden distances , manuscript, version 8, October 11, 2026. Frozen source, commit cb660f322dce47a773f347d39818ffc46e6ca72c (https://github.com/decalion89/chromatic-number-of-the-plane/blob/cb660f322dce47a773f347d39818ffc46e6ca72c/papers/forbidden-distances/forbidden-distances.tex).link
  5. L. E. Gibbons, D. W. Hearn, P. M. Pardalos and M. V. Ramana, Continuous characterizations of the maximum clique problem , Math. Oper. Res. 22 (1997), no. 3, 754--768.
  6. A. Jamneshan, An uncountable Furstenberg--Zimmer structure theory---Corrigendum , Ergodic Theory Dynam. Systems 46 (2026), no. 1, 211--217, DOI 10.1017/etds.2025.10214.DOI
  7. M. Laurent and L. F. Vargas, Finite convergence of sum-of-squares hierarchies for the stability number of a graph , SIAM J. Optim. 32 (2022), no. 2, 491--518, DOI 10.1137/21M140345X.DOI
  8. F. M. de Oliveira Filho and F. Vallentin, Fourier analysis, linear programming, and densities of distance-avoiding sets in Rn\R^n , J. Eur. Math. Soc. 12 (2010), 1417--1428, DOI 10.4171/JEMS/236.DOI
  9. OpenAI, The Euclidean plane is not five-colorable , OpenAI Math Release manuscript, September 23, 2026. Frozen source, commit 4eaee87548250b2682affda7d05d947c05554bae (https://github.com/openai/math/tree/4eaee87548250b2682affda7d05d947c05554bae/preprints/The-Euclidean-plane-is-not-five-colorable-September-23-2026).link
  10. L. A. Székely, Measurable chromatic number of geometric graphs and sets without some distances in Euclidean space , Combinatorica 4 (1984), 213--218, DOI 10.1007/BF02579223.DOI
  11. L. A. Székely and N. C. Wormald, Bounds on the measurable chromatic number of Rn\R^n , Discrete Math. 75 (1989), 343--372, DOI 10.1016/0012-365X(89)90099-X.DOI
  12. T. Tao, 254A, Lecture 9. Ergodicity , February 4, 2008, Theorem 4 and Remark 5, https://terrytao.wordpress.com/2008/02/04/254a-lecture-9-ergodicity/.link

Version history

  1. v1 · 50 pagesSubmitted by Liam KruerRevised manuscript accompanying Justin Sun Prize submission JSP-000576. Original source package, attribution and verification scope: https://github.com/Ghuffy1/erdos-706-lean/tree/2a22f736eea81c04ec696c1b1d7f770b4417f5f7CurrentNov 21, 2026