REVIEW 2 major objections 5 minor 30 references
Erd\H{o}s's unit distance problem and rigidity
T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read A rigidity conjecture, if true, breaks the 40-year-old unit-distance upper bound.
desk verdict Theorem 6 is a genuine structural contribution; Theorem 8 is a promising conditional reduction that needs constant-tracking and a 2-core argument, but the flaws are repairable. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine is the pair of polynomial partitions behind Theorem 6: two applications of a polynomial partitioning theorem first cut the point set and its unit circles into cells containing about $h^6$ points and circles, then select cells carrying at least $h^7$ incidences. The converting step is a double pigeonhole: among the $k\gtrsim n^{2/3}/h^5$ rigid subgraphs, at most $2^{h^{12}}$ isomorphism types and $9^{2h^6}$ congruence classes per type are possible, and fixing the images of two vertices leaves at most two embeddings; the resulting contradiction for $h\approx\log^{1/12} n$ is what proves Theorem 8.
What would settle it
Find a plane-realizable graph with $\gtrsim n^{7/6}$ edges in which no vertex has all its neighbours on one line but every sub-framework on four or more vertices is non-rigid; such a graph would refute the rigidity conjecture and remove the basis for Theorem 8, independently of the rest of the argument.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that dense unit-distance configurations are locally rich: Theorem 6 shows that when $u(P) \ge n^{4/3}/h(n)$ with $h(n)\to\infty$, the point set contains roughly $n^{2/3}/h^5$ vertex-disjoint small bipartite graphs, each with parts of size at most about $h^6$ and at least about $h^7$ unit edges, all unit-embedded into $P$. The paper then proves Theorem 8: if Conjecture 7 is true, the same structural information forces $u(n)=O(n^{4/3}/\log^{1/12} n)$. The role of rigidity is to bound the number of congruence classes among the many disjoint copies, so that a repeated distance $a$ appears too often inside a set of size about $n^{1/3}h^4$.
Load-bearing premise
The argument stands or falls on Conjecture 7, the open rigidity statement that any graph with roughly $n^{7/6}$ edges, realized so that no vertex's neighbours lie on a common line, contains a rigid sub-framework on at least four vertices; only a much denser special case has been proved.
Editorial extensions
If this is right
- If Conjecture 7 is true, $u(n) = O(n^{4/3}/\log^{1/12} n)$, the first improvement over the classical 1984 bound.
- Theorem 6 gives a universal local-structure statement for any point set with $u(P)\ge n^{4/3}/h(n)$: many disjoint small bipartite unit-embedded subgraphs with $|U_i|,|V_i|\lesssim h^6$ and $|E_i|\gtrsim h^7$.
- The known weaker rigidity theorem, which requires edge density $\Omega(n^{1+\alpha})$ for some $\alpha>1/2$, already guarantees rigid sub-frameworks in much denser graphs, so the conjecture is a strengthening to density $\gtrsim n^{7/6}$.
- The argument relies on bipartiteness to make each rigid subgraph have at least two vertices on each side, a property needed for the final repeated-distance counting.
Reading between the lines
- The step that applies the rigidity conjecture to the incidence graphs is not fully written down: those graphs may contain degree-2 vertices, whose neighbours are collinear, so the claim that the hypothesis applies automatically appears to require a 2-core reduction that is not stated.
- The final contradiction needs the constant hidden in $h\approx\log^{1/12} n$ to satisfy $c^{12}<2/9$; checking this numerical condition is essential before the conditional proof is complete.
- If the rigidity conjecture is resolved, the partition-and-count scheme may transfer to other problems where the same distance or congruent curves appear many times, as long as a bounded-number-of-embeddings statement holds.
- A plausible route to testing the conjecture is to look for realizations just above the known $\Omega(n\log n)$ lower bound, where the impossibility of rigid sub-frameworks may meet the new threshold.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies Erdős's unit distance problem: the best known upper bound u(n)=O(n^{4/3}) is due to Spencer, Szemerédi, and Trotter (1984). The authors prove an unconditional structural theorem (Theorem 6): if a set P of n points has u(P) ≥ n^{4/3}/h(n) with h(n)→∞, then P contains many pairwise vertex-disjoint small bipartite unit-embedded graphs Gi, each with parts of size ≲h^6 and ≳h^7 unit edges. They then state a rigidity conjecture (Conjecture 7) about dense graphs whose vertex realizations avoid the property that a vertex's neighbours are collinear, and they prove (Theorem 8) that, assuming Conjecture 7, u(n)=O(n^{4/3}/log^{1/12} n), giving the first improvement over the 1984 bound. The proof of Theorem 8 uses the structural theorem, a pigeonhole over graph types and congruence classes, and a counting argument on pairs in a subset P'. The proof of Theorem 6 uses two polynomial partitioning steps and incidence counting.
Significance. If the main conditional result were established as stated, it would be a significant conceptual advance: it would give the first unconditional-from-a-conjecture route past the classical n^{4/3} barrier. The unconditional Theorem 6 is a substantial structural contribution and its proof, modulo the corrections below, appears sound. The paper is transparent about the fact that Conjecture 7 is unproved and explicitly flags the conditional nature of Theorem 8; no fitted constants or data are smuggled in as predictions. The reliance on the authors' earlier work [20] is appropriate as evidence for the weaker rigidity threshold. However, as written, the conditional derivation has a load-bearing gap concerning constants in the application of Conjecture 7, and several local statements need correction.
major comments (2)
- [Section 2, first paragraph] The assertion that the non-collinearity hypothesis in Conjecture 7 'applies automatically' to the incidence graphs Gi is false for vertices of degree 0, 1, or 2, whose neighbours are trivially collinear. The natural repair is to pass to the 3-core (delete vertices of degree ≤2); since Gi has ≳h^7 edges and O(h^6) vertices, this deletes only O(h^6) edges, which is negligible for large h. However, after this repair the remaining graph Gi' satisfies |E(Gi')| ≥ (c/2)h^7 and |V(Gi')| ≤ 2C h^6, so the density ratio is |E(Gi')|/|V(Gi')|^{7/6} ≥ δ = (c/2)/(2C)^{7/6}. In Theorem 6, c is chosen 'sufficiently small' in the low-cell counting step, and Conjecture 7's threshold constant C_7 is never specified; the proof never verifies δ ≥ C_7. This is not a cosmetic issue: a random bipartite graph with parts of size h^6 and edge probability c h^{-5} has c h^7 edges, matching Theorem 6, but with high probability it has no subgraph with |E| ≥ C_7 |V|^{7/6} for any C_7 exceeding c up to constants. Thus Theorem 8 is not established from Conjecture 7 as stated. The argument would go through if Conjecture 7 were stated in a constant-uniform form: for every ε > 0, every graph with |E| ≥ ε n^{7/6} and with no vertex whose neighbours are collinear contains a rigid subframework on at least 4 vertices.
- [Section 2, final paragraph] There is a typo: 'h = h(n) that tends to zero' should read 'tends to infinity'. More substantively, the final contradiction is not automatic for the stated choice h ≈ log^{1/12} n. Taking logarithms of the displayed inequality gives (2/9) log_2 n ≲ h^{12} + 2h^6 log_2 9 + O(log h). If h = c log_2^{1/12} n, this forces c^{12} < 2/9 up to the constant in the O-term; at the natural choice c=1 no contradiction occurs. The proof should either fix an explicit sufficiently small constant or state the choice of h more precisely.
minor comments (5)
- [Theorem 6, item 1] The statement |P'| ≈ n^{1/3}h^4 is not justified by the proof, which yields only the upper bound |P'| ≤ C n^{1/3}h^4 and a much weaker lower bound from the incidence count. Since Section 2 uses only the upper bound, the statement should be corrected to '≲' or a matching lower bound should be supplied.
- [Section 3, first and second partitioning] The proof of Theorem 6 assumes r = n^{1/3}/h^2 ≥ 1 and that n is large relative to h; as stated, 'h tending to infinity' is too broad. The theorem should quantify the allowed range of h (for example h(n)=o(n^{1/6})), which is satisfied by the eventual choice h ≈ log^{1/12} n.
- [Section 3, construction of Gπ] The map from the V-vertices of Gπ to the centers of the circles in Dπ may fail to be injective if the center set of Dπ intersects Qπ, so the constructed p(i) may not be a 'unit embedding' in the sense defined in Section 1.3, which requires injectivity. Either argue that this overlap cannot occur, or replace 'unit embedding' by 'unit realization'; the later argument only needs the non-collinearity property, which does hold for vertices of degree at least 3.
- [Section 2, congruence-counting step] The claim that fixing the images of v1 and v2 leaves at most two possible realizations of H is not a standard consequence of the cited Milnor bound and may be false in general for rigid frameworks with a fixed pair of non-adjacent vertices. Even if the correct bound is 9^{O(h^6)} instead of 2, the final contradiction survives because h^6 = o(log n), so this step should be either justified or relaxed.
- [Conjecture 7] The notation |E| ≳ n^{7/6} leaves the threshold constant implicit. Given the application in Theorem 8, the conjecture should state explicitly whether it is asserted for every fixed ε > 0 at |E| ≥ ε n^{7/6}, or with a specific constant that is matched against the constants in Theorem 6.
Circularity Check
No circularity: Theorem 8 is an explicitly conditional reduction; the structure theorem is unconditional; the only self-citation is non-load-bearing.
full rationale
The derivation chain is not circular. No claim reduces by construction to its own input. Theorem 6 is an unconditional structural statement proved by two rounds of Guth's polynomial partitioning (Theorem 9); its parameters (r = n^{1/3}/h^2, cell sizes h^6, edge counts h^7, k ≳ n^{2/3}/h^5) are produced by incidence counting and pigeonhole arguments, not by encoding the target bound u(n) = O(n^{4/3}/log^{1/12} n). The function h(n) is a free slack function chosen only at the end of Section 2 to force a contradiction; it is not fitted to data, so pattern 2 (fitted input called prediction) does not apply. Theorem 8 is explicitly conditional on Conjecture 7, an openly stated new conjecture whose hypotheses (|E| ≳ n^{7/6}, no vertex's neighbours on a common line) do not mention u(n); the log-improvement emerges from a genuine counting step (2^{h^{12}} bipartite graph types times 9^{2h^6} congruence classes via Milnor's bound) rather than from restating the conjecture. The only self-citation, Raz-Solymosi [20], is a published, peer-reviewed theorem used solely as motivation ('A weaker version of this conjecture has been established by the last two authors') and is not load-bearing for Theorem 8, which invokes Conjecture 7, not Theorem 5. Pattern 4 and 5 do not apply: no uniqueness theorem or ansatz is imported from the authors' prior work. The reviewer-flagged gap in Section 2, that degree-≤2 vertices in the cell incidence graphs do not satisfy the non-collinearity hypothesis and the claim that the assumption 'applies automatically' is false, is a correctness or constant-matching issue in the conditional implication, not a circularity: a 3-core repair would not make the conclusion identical to the hypothesis, and the constant condition c^{12} < 2/9 is a standard technical requirement. Hence the honest finding is no significant circularity; the score of 2 reflects only the minor, non-load-bearing self-citation.
Assumptions & free parameters
free parameters (1)
- h(n) =
h → ∞, constrained to h^{12} < (2/9) log₂ n
assumptions (5)
- standard math Guth's polynomial partitioning theorem (Theorem 9, [11])
- standard math Spencer-Szemerédi-Trotter unit-distance bound u(n) = O(n^{4/3})
- standard math Milnor's bound: a rigid framework on m vertices has at most 9^m non-congruent embeddings ([16])
- standard math Raz-Solymosi Theorem 5 ([20]): |E| = Ω(n^{1+α}), α > 1/2, forces a rigid sub-framework
- domain assumption Tacit heuristic: near-extremal point sets exist and are worth studying
Cite this review
Pith. "Pith review of Erd\H{o}s's unit distance problem and rigidity." pith.science (2026). https://pith.science/paper/BY4ZFBJN
@misc{pith2026250715679,
author = {Pith},
title = {Pith review of: Erd\Hos's unit distance problem and rigidity},
year = {2026},
howpublished = {\url{https://pith.science/paper/BY4ZFBJN}},
note = {Machine review of arXiv:2507.15679}
}
abstract
According to a classical result of Spencer, Szemer\'edi, and Trotter (1984), the maximum number of times the unit distance can occur among $n$ points in the plane is $O(n^{4/3})$. This is far from Erd\H{o}s's lower bound, $n^{1+O(1/\log\log n)}$, which is conjectured to be optimal. We prove a structural result for point sets with nearly $n^{4/3}$ unit distances and use it to reduce the problem to a conjecture on rigid frameworks. This conjecture, if true, would yield the first improvement on the bound of Spencer et al. A weaker version of this conjecture has been established by the last two authors.
Reference graph
Works this paper leans on
-
[20]
Orit E. Raz and J´ ozsef Solymosi. Dense Graphs Have Rigid Parts.Discrete & Compu- tational Geometry 69 (2023), 1079–1094
work page 2023
-
[1]
Leonard Asimow and Ben Roth. The rigidity of graphs. Trans. Amer. Math. Soc. 245 (1978), 279–289
work page 1978
-
[2]
Leonard Asimow and Ben Roth. The rigidity of graphs II. J. Math. Anal. Appl. , 68 (1979), 171–190
work page 1979
-
[3]
C. Borcea and I. Streinu, The number of embeddings of minimally rigid graphs, Discrete Comput. Geom. 31 (2004), 287–303, DOI: 10.1007/s00454-003-2902-0
-
[4]
Peter Brass, William O.J. Moser, and J´ anos Pach. Research Problems in Discrete Ge- ometry. New York, Springer, 2005
work page 2005
-
[5]
Robert Connelly. Generic global rigidity. Discrete & Computational Geometry 33 (2005), 549–563
work page 2005
-
[6]
Fan Chung, Endre Szemer´ edi, and William T. Trotter. The number of different dis- tances determined by a set of points in the Euclidean plane. Discrete & Computational Geometry 7, no. 1 (1992), 1–11
work page 1992
-
[7]
Clarkson, Herbert Edelsbrunner, Leonidas J
Kenneth L. Clarkson, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, and Emo Welzl. Combinatorial complexity bounds for arrangements of curves and spheres. Discrete & Computational Geometry 5, no. 2 (1990), 99–160
work page 1990
Show all 30 references
-
[8]
On sets of distances of n points
Paul Erd˝ os. On sets of distances of n points. American Mathematical Monthly 53, no. 5 (1946), 248–250
1946
-
[9]
On sets of distances of n points in Euclidean space
Paul Erd˝ os. On sets of distances of n points in Euclidean space. Magyar Tudom´ anyos Akad´ emia Matematikai Kutat´ o Int´ ezet´ enek K¨ ozlem´ enyei5, no. 1–2 (1959), 165–169
1959
-
[10]
The Erdos Distance Problem
Julia Garibaldi, Alex Iosevich, and Steven Senger. The Erdos Distance Problem. Amer- ican Mathematical Soc., 2011
2011
-
[11]
Polynomial partitioning for a set of varieties
Larry Guth. Polynomial partitioning for a set of varieties. Mathematical Proceedings Cambridge Philosophical Society 159 (2015), 459–469
2015
-
[12]
Polynomial Methods in Combinatorics
Larry Guth. Polynomial Methods in Combinatorics. American Mathematical Society, 2016. 9
2016
-
[13]
On the Erd˝ os distinct distances problem in the plane
Larry Guth and Nets Hawk Katz. On the Erd˝ os distinct distances problem in the plane. Annals of Mathematics (2015), 155–190
2015
-
[14]
A new entropy inequality for the Erd˝ os distance problem
Nets Hawk Katz and G´ abor Tardos. A new entropy inequality for the Erd˝ os distance problem. Contemporary Mathematics, Vol. 342 (2004), 119–126
2004
-
[15]
Springer Science & Business Media, 2013
Jiˇ ri Matouˇ sek.Lectures on Discrete Geometry. Springer Science & Business Media, 2013
2013
-
[16]
Milnor, On the Betti numbers of real varieties, Proc
J. Milnor, On the Betti numbers of real varieties, Proc. AMS 15 (1964), 275–280
1964
-
[17]
On the different distances determined by n points
Leo Moser. On the different distances determined by n points. American Mathematical Monthly 59, no. 2 (1952), 85–91
1952
-
[18]
J´ anos Pach and Pankaj K. Agarwal. Combinatorial Geometry. John Wiley & Sons, 2011
2011
-
[19]
Forbidden paths and cycles in ordered graphs and matrices
J´ anos Pach and G´ abor Tardos. Forbidden paths and cycles in ordered graphs and matrices. Israel Journal of Mathematics 155, no. 1 (2006), 359–380
2006
-
[21]
Rational distances with rational angles
Ryan Schwartz, J´ ozsef Solymosi, and Frank de Zeeuw. Rational distances with rational angles. Mathematika, 58, 2, (2012), 409–418
2012
-
[22]
Using the subspace theorem to bound unit distances, Mosc
Ryan Schwartz. Using the subspace theorem to bound unit distances, Mosc. J. Comb. Number Theory, 3, 1, (2013), 108–117
2013
-
[23]
Classification of maps sending lines into translates of a curve, Linear Algebra and its Applications , Volume 668, 2023, 161-172,
J´ ozsef Solymosi and Endre Szab´ o. Classification of maps sending lines into translates of a curve, Linear Algebra and its Applications , Volume 668, 2023, 161-172,
2023
-
[24]
J´ ozsef Solymosi and Csaba D. T´ oth. Distinct distances in the plane.Discrete & Com- putational Geometry 25 (2001), 629–634
2001
-
[25]
Joel Spencer, Endre Szemer´ edi, and William T. Trotter. Unit distances in the Euclidean plane. In: Graph Theory and Combinatorics , Academic Press, 1984, 294–304
1984
-
[26]
Crossing numbers and hard Erd˝ os problems in discrete geometry.Com- binatorics, Probability and Computing 6, no
L´ aszl´ o Sz´ ekely. Crossing numbers and hard Erd˝ os problems in discrete geometry.Com- binatorics, Probability and Computing 6, no. 3 (1997), 353–358
1997
-
[27]
Endre Szemer´ edi and William T. Trotter. Extremal problems in discrete geomtery, Combinatorica, 3 (1983), 381–392
1983
-
[28]
Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory
Terence Tao. Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory. In: EMS Surveys in Math- ematical Sciences 1, no. 1 (2014), 1–46
2014
-
[29]
Terence Tao and Van H. Vu. Additive Combinatorics. Cambridge University Press, 2006
2006
-
[30]
P. Valtr. Strictly convex norms allowing many unit distances and related touching questions, manuscript 2005. 10
2005
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.