Erdős problem 653 — live audit and exact values for \(n=7,8,9\)

Accessed 2026-07-28 UTC. Claim labels used throughout:

• (a) elementary-rigorous: proved in this report from elementary facts.
• (b) rigorous-modulo-named-source/theorem: the cited source was located and checked to the extent stated.
• (c) plausible/structural-unverified: useful evidence, but not a theorem.
• (d) computational-only: a reproducible finite computation, not promoted to a general theorem.

0. Mandatory live-page gate

(b) I loaded the live problem page through the Bright Data browser path, then separately loaded its LaTeX view and expanded its dynamic bibliography box. Direct datacenter HTTP was not used for this gate.

The verbatim statement from the live LaTeX view is:

Let \(x_1,\ldots,x_n\in \mathbb{R}^2\) and let \(R(x_i)=\#\{ \lvert x_j-x_i\rvert : j\neq i\}\), where the points are ordered such that \[R(x_1)\leq \cdots \leq R(x_n).\] Let \(g(n)\) be the maximum number of distinct values the \(R(x_i)\) can take. Is it true that \(g(n) \geq (1-o(1))n\)?

(b) The live gate was clear:

• status: OPEN;
• comments: 0 comments on this problem;
• claimed proofs: 0 claimed proofs for this problem;
• Interested in collaborating: None;
• Currently working on this problem: None;
• This problem looks difficult: None;
• This problem looks tractable: None;
• The results on this problem could be formalisable: None;
• I am working on formalising the results on this problem: None.

The page also lists Aron under “Likes this problem”; this is not a worker or collaboration marker. Thus the mandatory stop condition did not fire.

The page's known-results paragraph, transcribed exactly in mathematical notation, is:

Erdős and Fishburn proved \(g(n)>\frac38n\) and Csizmadia proved \(g(n)>\frac7{10}n\). Both groups proved \(g(n)<n-cn^{2/3}\) for some constant \(c>0\).

(b) Expanding [Er97e] on the live page gives Paul Erdős, Some of my favourite unsolved problems, Math. Japon. (1997), 527–537, MR 1487304. The live page is the ground truth for the quoted \(3/8\), \(7/10\), and \(n-cn^{2/3}\) statements.

1. Literature audit

(b) The original paper P. Erdős and P. C. Fishburn, “Distinct distances in finite planar sets,” Discrete Mathematics 175 (1997), 97–13200145-8) exists with DOI 10.1016/S0012-365X(96)00145-8. Its publisher abstract defines the same vector of pinned distance counts \(f_i\), under the name \(F_n\), and says that it determines all sum-minimising configurations through \(n\leq7\) and the minimum sum for \(n=8\). The accessible publisher abstract does not expose the proof or coefficient of the live page's \(3/8\) lower bound, so I do not pretend to have independently audited that coefficient from the full paper.

(b) The primary scanned proceedings volume contains G. Csizmadia and D. Ismailescu, Maximum number of different distance counts, Bolyai Society Mathematical Studies 6, Intuitive Geometry (1997), 301–309. Google Books' scan of the volume shows on page 302 the \(10N+5\)-point construction with \(7N-4\) different counts (asymptotic ratio \(0.7\)); page 306 states \(D_2(6)=4\) and \(D_2(n)=n-1\) for \(n\leq5\); and page 307 gives the sublinear-defect upper bound. Their \(D_2(n)\) is the present \(g(n)\). OCR mangles some superscripts, so for the exact exponent in the upper bound I retain the authoritative live-page transcription \(2/3\).

(c) Exact-title searches, DOI/citation searches, OpenAlex cited-by searches for the Erdős–Fishburn paper, and searches for the strings D_2(7), D_2(8), and D_2(9) found no later primary paper improving \(0.7\) or recording the exact planar values below. The indexed citations I inspected concern other aspects of finite distance sets (especially isosceles subsets). This is a search report, not a proof of absence, and I make no priority claim for the small values proved here.

(b) I use the standard distinct-point interpretation. This is explicit in the Erdős–Fishburn formulation (“a set of \(n\) points”) and in the live page's linked formalisation, which uses a Finset. Allowing repeated locations would define a different multiset problem.

2. A uniform elementary upper bound at the top of the spectrum

Lemma

(a) For every \(n\geq7\),

Proof

(a) Every \(R(x_i)\) is an integer in \(\{1,\ldots,n-1\}\). If a configuration had \(n-1\) distinct \(R\)-values, its spectrum would therefore be exactly

Choose \(p,q\) with \(R(p)=1\) and \(R(q)=2\).

(a) Since the points are distinct and \(R(p)=1\), all other \(n-1\) points lie on one circle \(C\) centred at \(p\). Since \(R(q)=2\), all points other than \(q\) lie on the union of two circles \(D_1,D_2\) centred at \(q\).

(a) The centres \(p\) and \(q\) are different, so neither \(D_i\) coincides with \(C\). Two distinct Euclidean circles meet in at most two points. Consequently

has at most \(2+2=4\) points. Hence \(n\leq6\), contrary to \(n\geq7\). Thus \(n-1\) distinct counts are impossible, proving \(g(n)\leq n-2\). \(\square\)

The “two circles meet in at most two points” fact used above follows immediately by subtracting their two quadratic equations: the common points lie on one line, and substituting that line into either circle gives a quadratic equation. Thus no incidence theorem or asymptotic machinery is hidden in the lemma.

3. One nested exact construction

Let \(s=\sqrt3\), and define the following points:

| name | coordinate | |---|---| | \(O\) | \((0,0)\) | | \(A_0\) | \((2,0)\) | | \(A_1\) | \((s,1)\) | | \(A_2\) | \((1,s)\) | | \(A_3\) | \((0,2)\) | | \(A_5\) | \((-s,1)\) | | \(A_6\) | \((-2,0)\) | | \(Y\) | \((s-1,3+s)\) | | \(Z\) | \((-1,s)\) |

Set

(a) The six \(A\)-points in \(S_7\) are the radius-\(2\) dodecagon vertices at angles \(0,\pi/6,\pi/3,\pi/2,5\pi/6,\pi\); \(O\) is their centre. The point \(Z\) is the previously omitted vertex at angle \(2\pi/3\), while \(Y\) is off that circle. The nine listed points are pairwise distinct.

(a) All squared distances lie in \(\mathbb Q(s)\). Equality can therefore be checked exactly by comparing the two rational coefficients in \(a+bs\), since \(s\notin\mathbb Q\). Counting distinct squared distances is equivalent to counting distinct distances because \(t\mapsto\sqrt t\) is injective on nonnegative reals.

The exact recomputation gives:

| set | \(R\)-values in the displayed coordinate order | spectrum | number of values | |---|---|---|---:| | \(S_7\) | \((1,5,4,4,3,5,6)\) | \(\{1,3,4,5,6\}\) | \(5\) | | \(S_8\) | \((2,6,4,5,3,6,7,7)\) | \(\{2,3,4,5,6,7\}\) | \(6\) | | \(S_9\) | \((2,7,5,5,3,6,7,8,4)\) | \(\{2,3,4,5,6,7,8\}\) | \(7\) |

For a compact hand audit, the exact squared-distance sets in \(S_9\) are:

Their cardinalities are precisely the \(S_9\) row in the table. Removing \(Z\), and then \(Y\), gives the other two rows; those deletions must be recomputed because a removed distance can collapse a pinned count.

Exact small-case theorem

(a) The construction gives \(g(7)\geq5\), \(g(8)\geq6\), and \(g(9)\geq7\). The lemma gives the reverse inequalities. Therefore

This is a finite exact result and does not settle the asymptotic question.

4. Independent re-verification

The standalone checker is erdos653_wavew005_reverify.py. Run it from the repository root with:

python runs/erdos653_wavew005_reverify.py

(d) It uses only the Python standard library and reads no certificate or generated data. It implements \(\mathbb Q(\sqrt3)\) as exact pairs of Fractions, checks that all coordinates are distinct, builds each full squared-distance matrix, and computes every \(R\)-value twice:

1. by taking distinct off-diagonal values in each matrix row;
2. by grouping all edges globally by exact squared length and counting incident length-colours.

It asserts the three vectors and spectra above. The successful run ended with

matrix transcript sha256: 41064f08b2caa871d889e8beef168ef8a3d73cc5d4dac90dbf6144b67b2eb5ba
ALL EXACT CHECKS PASSED

(d) Exploratory searches over regular-polygon subsets and intersections of already occurring distance circles were used only to discover the coordinates. A restricted attempt to extend this nested family to \(n=10\) did not reach eight different counts. That miss is not an upper bound for \(g(10)\), because the searched families are only a tiny semialgebraic subfamily of all ten-point configurations.

5. What remains

(a) The exact theorem supplies three sharp concrete cases and the general top-spectrum obstruction \(g(n)\leq n-2\) for \(n\geq7\). It does not supply a family for unbounded \(n\), so it makes no claim that \(g(n)/n\to1\).

(b) Against the live page's cited results, the asymptotic interval remains

in the stated sense. Closing the problem requires a uniform construction with \(n-o(n)\) different pinned-distance counts; finite optimisation cannot provide that uniformity.

(c) The exact missing ingredient exposed by this run is a scalable way to prescribe many different local equality patterns among Euclidean distances while keeping one symmetric global distance matrix. Abstractly assigning different numbers of incident “distance colours” is easy; realizing those colour equalities by a rank-two Euclidean squared-distance matrix is the unresolved geometric constraint.

PARTIAL: Proved \(g(n)\le n-2\) for every \(n\ge7\) and, by exact nested \(\mathbb Q(\sqrt3)\) constructions, \(g(7)=5\), \(g(8)=6\), and \(g(9)=7\); the asymptotic question remains open.