Erdős problem 706 and uniform multiscale refinements
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 forbidden distances and chromatic number greater than . 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 .
Provenance statement
References
- 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
- 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
- T. Bellitto, A. Pêcher and A. Sédillot, On the density of sets of the Euclidean plane avoiding distance , Discrete Math. Theor. Comput. Sci. 23 (2021), no. 1, DOI 10.46298/dmtcs.5153.DOI
- B. Bukh, Measurable sets with excluded distances , Geom. Funct. Anal. 18 (2008), 668--697.
- D. Castro-Silva, Geometrical sets with forbidden configurations , Forum Math. Sigma 11 (2023), e44, DOI 10.1017/fms.2023.43.DOI
- 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
- J. Davies, Measurable obstructions for unmeasurable colourings , preprint, arXiv:2610.12301v1 (2026).arXiv
- 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.
- 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
- 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
- P. Erdős, On the combinatorial problems which I would most like to see solved , Combinatorica 1 (1981), 25--42.
- T. F. Bloom, Erdős Problem #706 , https://www.erdosproblems.com/706.link
- 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
- 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
- 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.
- 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
- 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
- F. M. de Oliveira Filho and F. Vallentin, Fourier analysis, linear programming, and densities of distance-avoiding sets in , J. Eur. Math. Soc. 12 (2010), 1417--1428, DOI 10.4171/JEMS/236.DOI
- 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
- 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
- L. A. Székely and N. C. Wormald, Bounds on the measurable chromatic number of , Discrete Math. 75 (1989), 343--372, DOI 10.1016/0012-365X(89)90099-X.DOI
- 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
- 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