ERDŐS/DAILY ▸

← back to the ledger

ERDőS #668 · PARTIAL

Erdős problem 668 — wave w008

Date: 2026-07-28 (UTC)

Claim labels

Every substantive conclusion below is marked as requested:

transcription/source audit rather than a mathematical inference;

theorem in Alexeev--Mixon--Parshall;

diagnosis rather than a theorem;

computation.

0. Mandatory live-page audit

(a, direct source audit) I accessed the live page through the Bright Data browser path on 2026-07-28. Direct datacenter curl was separately confirmed to receive Cloudflare's “Just a moment...” challenge. The live browser rendered the following statement (verbatim, with only Markdown/LaTeX typesetting substituted for the site's MathJax rendering):

Is it true that the number of incongruent sets of \(n\) points in \(\mathbb{R}^2\) which maximise the number of unit distances tends to infinity as \(n\to\infty\)? Is it always \(>1\) for \(n>3\)?

(a, direct source audit) The page is marked OPEN, was last edited 27 December 2025, lists 0 claimed proofs, and has:

Thus neither mandatory stop condition applies.

(a, direct source audit) The page's listed results are:

  1. For \(n=4\), the count is \(1\); the unique maximizer is “two equilateral

triangles joined by an edge.”

  1. Engel--Hammond-Lee--Su--Varga--Zsámboki [EHSVZ25] and

Alexeev--Mixon--Parshall [AMP25] give computational evidence that the count is \(1\) for various other \(5\leq n\leq21\), but their calculations count only graph-isomorphism classes, not congruence classes.

  1. The maximum number \(u(n)\) of unit distances is Erdős problem 90.
  2. The related OEIS entry is A385657.

(a, direct source audit) I also opened the linked discussion thread and read all three comments:

small-\(n\) graph counts are known. The site says this comment was incorporated.

nonisomorphic constructions for the then-known exact cases through \(15\), often only one; this does not count congruence classes, and exact \(u(n)\) was then the obstruction.

known through \(21\) in AMP25; their count is only up to graph isomorphism; the method could in principle count Euclidean congruence classes. He mentioned that \(n=20\) has one graph but did not recall whether its point realization is unique. The site says this comment was incorporated.

No comment claims a partial or complete solution.

1. Definitions and result obtained

Let

\[ u(n)=\max\bigl\{\#\{\{p,q\}\subset P:\|p-q\|=1\}:P\subset\mathbb R^2,\ |P|=n\bigr\} \]

and let \(C(n)\) be the cardinality of the set of \(n\)-point maximizers, modulo all Euclidean isometries. Write \(\mathfrak c=|\mathbb R|=2^{\aleph_0}\).

The output of this run is the following exact finite result.

Theorem.

1. (a) \(C(6)=\mathfrak c\). 2. (b) Using Theorem 1 of Alexeev--Mixon--Parshall for the exact values of \(u(n)\), one has \[ > C(8)=C(9)=C(12)=C(21)=\mathfrak c. > \]

The first assertion is fully elementary and does not depend on the computer enumerations in the literature. The other four constructions and all their distance counts are elementary; only the assertion that their displayed edge counts are globally maximal uses AMP25.

This does not settle the limit as \(n\to\infty\): five exceptional finite arguments, even with uncountably many maximizers at each one, provide no eventual lower bound on \(C(n)\).

2. Primary-source/literature audit

(a, direct source audit) Erdős's original source is:

Probability* (1997), pp. 1--10, DOI 10.1017/CBO9780511662034.004.

I inspected page 5 of a scan. Immediately after defining \(f(n)\) as the maximum number of unit-distance pairs, Erdős asks whether the number of incongruent \(n\)-point sets with \(f(n)\) unit distances exceeds one for \(n>3\) and tends to infinity. Thus the live statement accurately reflects the original question.

(a, direct source audit) The two sources cited by the live page both exist and say the relevant things:

Diverse beam search to find densest-known planar unit distance graphs, arXiv:2406.15317v3, published online in Experimental Mathematics in 2025, DOI 10.1080/10586458.2025.2507956. Section 5.2 defines disjoint Minkowski sums and explicitly says that the optimal 9-vertex graph is the sum of two unit triangles. Its table counts graph-isomorphism classes found by a beam search; it does not classify congruence classes.

The Erdős unit distance problem for small point sets, arXiv:2412.11914v2. Theorem 1 establishes exact \(u(n)\) through \(21\) and enumerates all extremal abstract unit-distance graphs. Its relevant rows are \[ \begin{array}{c|ccccc} n&6&8&9&12&21\\ \hline u(n)&9&14&18&27&57\\ \#\text{ abstract graph classes}&4&3&1&1&5. \end{array} \] Appendix A explicitly observes that the first \(n=6\) graph is a triangle-plus-edge Minkowski sum with a relative-angle degree of freedom, and similarly that the first \(n=21\) graph is the sum of a triangle and the 7-vertex wheel. It calculates \(3\cdot12+3\cdot7=57\).

(a, direct source audit) The relevant downloaded source hashes were:

Er97 scan:
8c9e66f1cca8f38f98432079ba1010f8f46662f572b089da93e25350c0e19423
arXiv:2406.15317v3 PDF:
ef390fed54a6715c61bae12ce3909526bd4ba48ab92a265280e78f3cac8177ca
arXiv:2412.11914v2 PDF:
16885d4dffd5377796efff1ed7bb09be00c2b3948739a4e41413ce0da9c965d7
AMP25 ancillary graph6.txt:
4f7da8729d4818712e8718daabce29fb7f423cd7abec07eb195f0a04d6601a49

(a, direct source audit) OEIS A385657 is explicitly the “Number of nonisomorphic maximally dense unit-distance graphs on \(n\) vertices.” It is therefore not the sequence \(C(n)\). In particular, it gives one graph at \(n=9\), while the theorem above gives \(\mathfrak c\) congruence classes. OEIS A186705, for \(u(n)\), already contains an informal 2018 comment describing a one-degree-of-freedom 9-point, 18-unit-distance construction. I therefore make no novelty claim for the existence of flexibility at \(n=9\); the contribution here is a uniform exact proof and checker that turns the graph/congruence caveat into cardinality statements at five exact sizes.

(a, direct source audit) I also checked the post-page-update 2026 developments on the ordinary unit-distance problem:

arXiv:2605.20579, constructs arbitrarily large point sets with more than \(n^{1.014}\) unit pairs.

arXiv:2605.20695, gives a human-verified account of the new polynomial-exponent lower bound.

Those papers give lower-bound constructions; they do not identify \(u(n)\) at their orders and do not show that those constructions are maximizers. Consequently they do not currently certify any new value of \(C(n)\).

(c) Exact-phrase searches for Erdős's incongruence question, searches for congruence/rigidity of maximally dense unit-distance graphs, and forward searches around EHSVZ25/AMP25 found no primary source resolving the asymptotic question or giving a congruence-class enumeration. This is a documented search miss, not a proof that no such source exists. The live page also remains OPEN with no claim or worker.

3. The Minkowski-flex lemma

For finite \(A,B\subset\mathbb R^2\), let \(a=|A|\), \(b=|B|\), and let \(e(A),e(B)\) count their unit-distance pairs. Let \(R_\theta\) be rotation through angle \(\theta\), and put

\[ P_\theta=A+R_\theta B =\{x+R_\theta y:x\in A,\ y\in B\}. \]

Lemma (a). If the sum map \(A\times B\to P_\theta\) is injective, then \(|P_\theta|=ab\) and \[ > e(P_\theta)\ \geq\ b\,e(A)+a\,e(B). \tag{1} > \]

Proof. For every unit pair \(\{x,x'\}\) of \(A\) and every \(y\in B\), \(\{x+R_\theta y,x'+R_\theta y\}\) is a unit pair. This gives \(b e(A)\) pairs. Likewise, translating every rotated unit pair of \(B\) by every \(x\in A\) gives \(a e(B)\) pairs. Injectivity makes all these vertices distinct and makes the two collections of pairs disjoint. ∎

(a) A collision in the sum map would give

\[ x-x'=R_\theta(y'-y) \tag{2} \]

for nonzero difference vectors. For fixed finite \(A,B\), only finitely many angles can satisfy (2). Thus a generic relative rotation is disjoint.

(a) If the right side of (1) equals the known upper bound \(u(ab)\), then every disjoint \(P_\theta\) is automatically an extremal \(ab\)-point set. If a congruence invariant such as its diameter varies injectively with \(\theta\) on an interval, these extremal sets give \(\mathfrak c\) distinct congruence classes. There cannot be more than \(\mathfrak c\), since all ordered \(n\)-tuples form a subset of \(\mathbb R^{2n}\).

4. Five explicit continuous families

Put

\[ \begin{aligned} E_x&=\{(0,0),(1,0)\},& E_y&=\{(0,0),(0,1)\},\\ T&=\{(0,0),(1,0),(1/2,\sqrt3/2)\},\\ T_y&=\{(0,0),(0,1),(-\sqrt3/2,1/2)\},\\ D&=\{(0,0),(1,0),(1/2,\sqrt3/2),(1/2,-\sqrt3/2)\},\\ W&=\{(0,0)\}\cup \{(\cos(k\pi/3),\sin(k\pi/3)):0\leq k<6\}. \end{aligned} \]

Here \(T,T_y\) are unit triangles, \(D\) is the diamond, and \(W\) is a regular unit hexagon with its centre. Direct counting gives

\[ \begin{array}{c|rrrrrr} X&E_x&E_y&T&T_y&D&W\\ \hline |X|&2&2&3&3&4&7\\ e(X)&1&1&3&3&5&12. \end{array} \]

For every \(0<\theta<\pi/6\), take the following sets:

\[ \begin{array}{c|c|c|c|c} n&P_\theta&b\,e(A)+a\,e(B)&u(n)&\operatorname{diam}(P_\theta)^2\\ \hline 6&T+R_\theta E_x&2\cdot3+3\cdot1=9&9& 2+2\cos\theta\\ 8&D+R_\theta E_y&2\cdot5+4\cdot1=14&14& 4+2\sqrt3\cos\theta\\ 9&T+R_\theta T&3\cdot3+3\cdot3=18&18& 2+2\cos\theta\\ 12&D+R_\theta T_y&3\cdot5+4\cdot3=27&27& 4+2\sqrt3\cos\theta\\ 21&W+R_\theta T&3\cdot12+7\cdot3=57&57& 5+4\cos\theta \end{array} \]

The \(n=6\) row, including \(u(6)=9\), is (a). The other four equalities with \(u(n)\) are (b) via AMP25 Theorem 1.

4.1 Disjointness on the whole interval

(a) The nonzero differences of \(T\) all have length \(1\) and directions \(k\pi/3\). Those of \(T_y\) have length \(1\) and directions \(\pi/2+k\pi/3\). The differences of \(D\) have either:

The only length-1 differences of \(W\) have directions \(k\pi/3\). In every row, equation (2) would require equality of lengths and equality of one of these directions after adding \(\theta\). For \(0<\theta<\pi/6\), none coincide:

\(\theta\equiv0\pmod{\pi/3}\);

\(\theta=\pi/6\) at the first endpoint encountered.

Thus every displayed sum has exactly \(n\) distinct points throughout the open interval.

4.2 Unit distances

(a) The arithmetic in the third column follows directly from Lemma (1). For \(n=6\), the elementary upper bound proved in Section 5 shows that these are all the unit pairs. For \(n=8,9,12,21\), AMP25's upper bounds show the same. In particular, each \(P_\theta\) is an extremal point set.

4.3 Pairwise incongruence

(a) The diameter formulae are exact. For \(n=6,9\), each summand has diameter \(1\), and the closest pair of diameter directions differs by \(\theta\), giving squared diameter \(1+1+2\cos\theta\).

For \(n=8,12\), the unique long direction in \(D\) has length \(\sqrt3\); it is paired with the aligned unit direction of the other summand. This gives

\[ 3+1+2\sqrt3\cos\theta. \]

Every competing difference uses a unit difference of \(D\), hence has length at most \(2\), or uses the long difference at a larger angle.

For \(n=21\), a wheel diameter of length \(2\) pairs with a triangle edge of length \(1\), giving

\[ 4+1+4\cos\theta. \]

All shorter wheel differences have length at most \(\sqrt3\); even when perfectly aligned with a unit triangle difference, they cannot beat the displayed value for \(0<\theta<\pi/6\).

Each displayed squared diameter is strictly decreasing on \((0,\pi/6)\). Different parameters therefore give different diameters and hence noncongruent point sets. The interval has cardinality \(\mathfrak c\), and the universal upper bound is also \(\mathfrak c\). This proves the theorem once \(u(6)=9\) is established.

5. Elementary proof that \(u(6)=9\)

Unit-circle lemma (a). Among \(k\leq5\) distinct points on a circle of radius \(1\), at most \(k-1\) pairs are unit distance apart.

Proof. A unit chord subtends a central angle \(\pi/3\). Within each orbit under rotation by \(\pi/3\), the unit-chord graph is the 6-cycle \(C_6\). With at most five selected vertices, no whole \(C_6\) occurs, so every component is a path and has at most one fewer edge than vertices. Summing over orbits gives at most \(k-1\). ∎

Proposition (a). Every six-point planar set has at most nine unit distances.

Proof. Let \(G\) be its unit-distance graph and let \(\Delta=\Delta(G)\).

\(e(G)\leq6\Delta/2\leq9\).

the unit circle around \(v\), so the unit-circle lemma gives at most four edges among them. Hence \(e(G)\leq5+4=9\).

\(w\) be the sixth vertex. The unit-circle lemma gives \(e(G[S])\leq3\). Also \(w\) is not adjacent to \(v\), and it has at most two neighbours in \(S\), because two distinct unit circles have at most two intersection points. Thus \[ e(G)\leq4+3+2=9. \]

These cases exhaust all possibilities. The \(T+R_\theta E_x\) construction has nine unit distances, so \(u(6)=9\). ∎

Combining this proposition with Section 4 proves (a) \(C(6)=\mathfrak c\) from scratch.

6. Reproducible verification

The standalone verifier is runs/erdos668_wavew008_reverify.py. It uses only the Python standard library. Its arithmetic is exact in \(\mathbb Q(\sqrt3)\); no floating-point equality is used.

It independently performs the following:

  1. (d) Recounts the unit pairs of \(E_x,E_y,T,T_y,D,W\).
  2. (d) Uses the rational rotation parameter

\[ \cos\theta=\frac{1-t^2}{1+t^2},\qquad \sin\theta=\frac{2t}{1+t^2} \] at \(t=1/10,1/7,1/5\). For all five families at all three parameters, it verifies exact point count, exact unit-pair count, and the exact diameter formula.

  1. (d) Enumerates all \(2^{15}=32768\) labelled six-vertex graphs. It

imposes the two necessary geometric properties used in the elementary proof (at most two common neighbours; the unit-circle neighbourhood bound) and independently confirms that none has more than nine edges.

  1. (d) Scans every nontrivial factorization \(n=ab\leq21\) in the

published \(u(n)\) table and finds exactly \[ (a,b,n,u(n))=(2,3,6,9),(2,4,8,14),(3,3,9,18), (3,4,12,27),(3,7,21,57). \]

  1. (d) Implements graph6 decoding and graph isomorphism from scratch,

decodes the relevant AMP25 ancillary certificates, verifies their vertex and edge counts, and verifies that each family above is isomorphic to the first graph listed at its order.

Run:

python runs/erdos668_wavew008_reverify.py

Observed output:

base sets: exact unit-edge counts 1,1,3,3,5,12 [PASS]
five exact constructions at t=1/10: point/edge/diameter checks [PASS]
five exact constructions at t=1/7: point/edge/diameter checks [PASS]
five exact constructions at t=1/5: point/edge/diameter checks [PASS]
proper subsets of the unit-chord C6: maxima 0,0,1,2,3,4 [PASS]
all 2^15 six-vertex graphs: geometric necessities force <=9 edges
    (21034 accepted; 1260 have 9) [PASS]
product-equality scan of the published u(n) table:
    [(2, 3, 6, 9), (2, 4, 8, 14), (3, 3, 9, 18),
     (3, 4, 12, 27), (3, 7, 21, 57)] [PASS]
AMP25 graph6 rows decode with stated sizes/edges; each exact family
    matches its first listed graph [PASS]
15,000 CPU-hours at $0.04-$0.10/core-hour = $600-$1,500 [PASS]
PASS: C(6)=continuum is supported by a from-scratch upper/lower check;
    n=8,9,12,21 constructions are exact modulo the published optimality
    theorem.

Runtime was \(0.41\) seconds with peak RSS \(14704\) KB on the final run on this VM. The verifier's SHA-256 after the final run is recorded in the final validation section below.

7. What this says about graph counts

(a/b) At the five relevant orders:

\[ \begin{array}{c|ccccc} n&6&8&9&12&21\\ \hline \text{AMP25 graph classes}&4&3&1&1&5\\ C(n)&\mathfrak c&\mathfrak c&\mathfrak c&\mathfrak c&\mathfrak c \end{array} \]

The \(C(6)\) row is elementary (a); the other four entries are (b). This makes the page's caveat decisive: even a unique extremal abstract graph (as at \(n=9\) and \(n=12\)) can have a positive-dimensional realization space and continuum many congruence classes.

8. Exact remaining obstruction

The Minkowski lemma isolates one possible propagation mechanism. If \(|A|=a\), \(|B|=b\), both summands are extremal, and

\[ u(ab)=b\,u(a)+a\,u(b), \tag{3} \]

then generic relative rotations of a disjoint sum are extremal. When a distance invariant varies, this gives \(C(ab)=\mathfrak c\).

(d) In the exact table through \(21\), the only nontrivial products satisfying (3) are precisely the five products used above. This finite scan does not suggest an eventual identity and is not evidence against one.

(c) A theorem propagating (3), or another theorem that transfers a flex while preserving global extremality, is the exact missing lemma for this route. Rigidity theory alone detects a flex of a chosen unit-distance graph; it does not prove that the graph has \(u(n)\) edges. Conversely, the 2026 number-theoretic constructions give many unit distances but no matching upper bound, so they cannot certify a maximizer.

(c) Exhaustive small-graph computation is not an asymptotic route. AMP25 reports about 1000 total CPU-hours for its \(n=21\) calculation and estimates 15000 total CPU-hours merely to enumerate the relevant 61-edge \(n=22\) forbidden-subgraph candidates. At an illustrative 2026 commodity rate of USD 0.04--0.10 per core-hour, the latter is roughly USD 600--1500 before implementation, storage, exact embeddability, or congruence-class analysis. More importantly, any fixed extension remains finite and cannot prove \(C(n)\to\infty\).

(c) To close the original problem one would need, uniformly in all sufficiently large \(n\), either:

  1. many provably extremal nonisomorphic faithful graphs; or
  2. a provably extremal graph with a controlled realization space containing

increasingly many (ideally continuously many) congruence classes; or

  1. an extremality-preserving construction covering all sufficiently large

orders.

No source found supplies the required uniformity. The result of this run is therefore a sharp finite advance and a clean reduction, not a solution of the limit question.

9. Final validation record

The report and checker were inspected after creation. The final checker run completed all assertions in under one second. Its final SHA-256 is:

052458fd9017c33e5387cdfecdb37f1a7d12623effc42006c76064c5012186ec  runs/erdos668_wavew008_reverify.py

PARTIAL: Elementary proof gives continuum many incongruent maximizers at n=6; modulo AMP25's exact u(n) theorem the same holds at n=8,9,12,21, while no uniform extremality-propagation lemma is known.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger