Erdoes #654 - working report - Erdős Problem a Day

Erdős problem 654 — wave w005

Date of live-page check: 2026-07-28 (UTC).

Claim labels used throughout:

(a) elementary-rigorous: proved here from elementary facts.
(b) rigorous-modulo-named-theorem/source: depends on the explicitly named

theorem or on an exact source transcription.

(c) plausible/structural-unverified: a search result, diagnosis, or

structural idea that is not a theorem.

(d) computational-only: established by the supplied exact computation,

without being promoted to a mathematical proof unless an accompanying argument is also given.

0. Mandatory live-page gate

(b) I fetched the live page through the Bright Data browser path, with JavaScript-rendered document.body.innerText. The page header says OPEN and was last edited 1 February 2026. It lists zero comments, zero claimed proofs, nobody under “Interested in collaborating,” and nobody under “Currently working on this problem.” The “difficult,” “tractable,” and formalisation markers are also empty. The only likes shown are Jeewon Kim and Junseok Lee. Thus the stop condition is not triggered. The page does say that the strongest subquestion has now been disproved, but the page continues to classify the remaining problem as open.

Verbatim live statement

Let \(f(n)\) be such that, given any \(x_1,\ldots,x_n\in \mathbb{R}^2\) with no four points on a circle, there exists some \(x_i\) with at least \(f(n)\) many distinct distances to other \(x_j\). Estimate \(f(n)\) - in particular, is it true that \[ > f(n)>(1-o(1))n? > \] Or at least \[ > f(n) > (1/3+c)n > \] for some \(c>0\), for all large \(n\)?

(b) The live page lists the following known information.

The trivial bound is \(f(n)\geq (n-1)/3\).
Erdős [Er97e] asked the \((1-o(1))n\) question, said it might be too

optimistic, but was sure the trivial bound could be significantly improved.

Erdős [Er87b] and Erdős–Pach [ErPa90] asked the weaker

\((1/3+c)n\) question under the extra condition that no three points are collinear.

Erdős suggested that the \((1-o(1))n\) assertion might hold if no circle

centred at one of the points contains more than two other points.

The strongest assertion is now false: Aletheia/Feng et al. [Fe26] construct

no-four-concyclic configurations in which every point determines at most \(3n/4\) distinct distances. Their points lie on two lines, so this does not settle the no-three-collinear variant.

1. Definition and result obtained

Use the standard geometric convention that the \(x_i\) are distinct. For a finite planar set \(X\), put

R_X(p)=\left|\{|p-q|:q\in X\setminus\{p\}\}\right|, \qquad f(n)=\min_{\substack{|X|=n\\\text{no four concyclic}}}\max_{p\in X}R_X(p).

The finite cases and bounds proved here are:

| \(n\) | verified conclusion | basis | |---:|:---|:---| | 2 | \(f(2)=1\) | (a) | | 3 | \(f(3)=1\) | (a) | | 4 | \(f(4)=2\) | (a) | | 5 | \(f(5)=3\) | (b) Nozaki–Shinohara Proposition 4.16, plus an (a) construction | | 6 | \(f(6)=3\) | (b) Nozaki–Shinohara Proposition 4.16, plus an (a) construction | | 7 | \(3\leq f(7)\leq4\) | (b) lower bound and (a) upper construction | | 8 | \(4\leq f(8)\leq5\) | (b) Nozaki–Shinohara Proposition 4.18 and (a) upper construction |

These are small-case results only; they do not imply an asymptotic improvement.

2. Lower bounds

\(n\leq4\)

(a) For \(n=2,3\), distinctness gives the lower bound \(1\), and two points or an equilateral triangle attain it.

(a) If four planar points had \(R_X(p)\leq1\) at every point, all three edges incident to each vertex would have the same length. Moving through the complete graph shows that all six pairwise distances would be equal. Four equidistant points cannot lie in \(\mathbb R^2\): after translating one point to the origin, the other three vectors have Gram matrix with diagonal \(s^2\) and off-diagonal \(s^2/2\), whose three eigenvalues are \(2s^2,s^2/2,s^2/2>0\), hence rank \(3\), whereas three planar vectors have Gram rank at most \(2\). Thus \(f(4)\geq2\).

\(5\leq n\leq7\)

(b) A set is locally two-distance when \(R_X(p)\leq2\) for every point. Proposition 4.16 of H. Nozaki and M. Shinohara, “On a generalization of distance sets,” arXiv:0906.0199v2, proves

\operatorname{LDS}_2(2)=\operatorname{DS}_2(2)=5

and its \(d=2\) proof identifies every five-point optimal locally two-distance set as \(R_5\), the regular pentagon. Consequently:

no planar locally two-distance set has more than five points;
a five-point locally two-distance set is a regular pentagon and hence has

five concyclic points.

It follows that an admissible five-point set has a point with at least three distances, and the same is automatically true for six- and seven-point sets. Therefore \(f(5),f(6),f(7)\geq3\).

\(n=8\)

(b) Proposition 4.18 of the same paper states:

every eight-point planar set \(X\) satisfies

\(\sum_{p\in X}R_X(p)\geq24\);

equality occurs only for a configuration similar to its Figure 1;
every eight-point locally three-distance planar set is similar to Figure 1.

Suppose an admissible eight-point set had \(R_X(p)\leq3\) everywhere. Then the displayed sum is at most \(24\), so equality holds and the set is Figure 1 up to similarity. Figure 1 contains its four central square vertices, which are concyclic. This contradicts admissibility, proving \(f(8)\geq4\). For an independent check of the relevant geometry, Figure 1 can be realised as

(\pm1,\pm1),\quad (0,\pm(1+\sqrt3)),\quad (\pm(1+\sqrt3),0).

The exact checker confirms that all eight local counts equal \(3\), their sum is \(24\), and the central four points are concyclic. This last calculation is (d); the uniform lower bound is (b) because it uses Proposition 4.18 and its uniqueness clause.

3. Explicit upper constructions

All distance calculations below use squared distances, which preserve equality of nonnegative distances.

\(n=4\)

(a) Take an equilateral triangle

(0,0),\quad(2,0),\quad(1,\sqrt3)

and its centroid \((1,\sqrt3/3)\). The three vertices each see two distances and the centroid sees one. The centroid is not on the triangle's circumcircle, so the four points are not concyclic. Hence \(f(4)\leq2\).

One six-point configuration supplies \(n=5,6,7\)

Let

B=\{(-3,0),(-1,0),(1,0),(3,0),(0,\sqrt7),(0,-\sqrt7)\}.

(a) The pinned squared-distance sets in \(B\) are:

at \((\pm3,0)\): \(\{4,16,36\}\);
at \((\pm1,0)\): \(\{4,8,16\}\);
at \((0,\pm\sqrt7)\): \(\{8,16,28\}\).

Thus every point of \(B\) sees exactly three distances. A circle meets each coordinate axis in at most two points. Four points of \(B\) on one circle would therefore have to be two from each axis. By intersecting chords (power of the origin), their signed coordinate products would obey \(x_1x_2=y_1y_2\). The only product on the vertical axis is \(-7\), while products of two distinct horizontal coordinates belong to \(\{-9,-3,-1,3\}\). Hence this cannot happen. Four collinear horizontal points are not points on a Euclidean circle.

(a) Delete \((0,-\sqrt7)\) to obtain an admissible five-point set with local counts \((3,3,3,3,2)\). Keeping all of \(B\) proves \(f(6)\leq3\). Adding the origin produces an admissible seven-point set with counts

\[ (4,4,4,4,4,4,3). \]

No old four-subset becomes cyclic. A circle through the newly added origin can contain at most one additional point from each coordinate axis, hence at most three points of this union in total. Therefore \(f(7)\leq4\).

\(n=8\)

Put \(a=2^{10}\), \(b=3^{10}\), and take

C=\{(\pm a,0),(\pm2a,0),(0,\pm b),(0,\pm3b)\}.

(a) Each point has at most three same-axis distances. Cross-axis distances depend only on the two absolute coordinate magnitudes on the other axis, so there are at most two of those. Thus \(R_C(p)\leq5\). Direct exact enumeration gives local counts

\[ (5,5,5,5,4,4,5,5) \]

in the ordering used by the checker.

(a) As above, any cyclic four-subset would need two points from each axis. Intersecting chords at the origin would equate a nonzero signed power of \(2\) with a nonzero signed power of \(3\), impossible by unique factorisation. Hence \(C\) is admissible and \(f(8)\leq5\). This is the \(m=2\) instance of the two-axis idea in Feng et al., but the proof here is complete on its own.

4. A clean exact reduction of the asymptotic question

Fix an admissible \(X\) and \(p\in X\). No circle centred at \(p\) contains four points of \(X\), so every positive distance from \(p\) occurs one, two, or three times. Let \(a_j(p)\) be the number of distance values occurring exactly \(j\) times. Then

\[ n-1=a_1(p)+2a_2(p)+3a_3(p) \]

and therefore

\boxed{\; R_X(p)=\frac{n-1}{3} +\frac{2a_1(p)+a_2(p)}{3}. \;} \tag{1}

(a) Formula (1) both proves the trivial bound and isolates the entire missing step. The requested inequality

\[ R_X(p)>(1/3+c)n \]

is exactly equivalent to finding some centre \(p\) for which

2a_1(p)+a_2(p)>3cn+1. \tag{2}

Thus a fixed improvement over \(1/3\) is precisely a theorem forcing a linear “occupancy deficit from three” among the distance circles of at least one centre.

(a) The naive incidence count cannot supply that theorem. Counting the ordered pairs \((p,q)\), \(p\ne q\), as incidences of \(q\) with a distance-circle centred at \(p\), there are \(n(n-1)\) incidences and every such circle contains at most three points. This yields only \(\sum_pR_X(p)\geq n(n-1)/3\), exactly the sum of the first term in (1). Any proof of (2) must exploit compatibility between triples on circles with different centres, not merely the per-circle capacity.

(c) The precise current wall is therefore the following missing lemma: there are constants \(c>0,n_0\) such that every admissible \(n\)-point set, \(n\geq n_0\), has a point \(p\) satisfying (2). Equivalently, one must rule out configurations in which almost every distance shell at every centre is filled in triples. Neither the checked sources nor the computations here provide that cross-centre rigidity. This is a diagnosis, not a claim that no such lemma exists.

5. Reproducible exact verification

The standalone verifier is erdos654_wavew005_reverify.py (SHA-256 8d3adaac08f38772b110af0ac37a83e74797ee55472f7b2738bb306335da4195). It uses only the Python standard library for the mathematical checks and exact arithmetic in \(\mathbb Q(\sqrt d)\). It computes pinned distance sets in two independent ways, enumerates every four-subset, and distinguishes the zero circle determinant caused by four collinear points from a genuine circle. The optional source audit additionally needs pdftotext and network access.

Run:

python runs/erdos654_wavew005_reverify.py
python runs/erdos654_wavew005_reverify.py --check-sources

The full audited run produced:

n=2: local counts=(1, 1); max=1
n=3: local counts=(1, 1, 1); max=1
n=4: local counts=(2, 2, 2, 1); max=2
n=5: local counts=(3, 3, 3, 3, 2); max=3; collinear four-subsets=((0, 1, 2, 3),)
n=6: local counts=(3, 3, 3, 3, 3, 3); max=3; collinear four-subsets=((0, 1, 2, 3),)
n=7: local counts=(4, 4, 4, 4, 4, 4, 3); max=4; collinear four-subsets=((0, 1, 2, 3), (0, 1, 2, 6), (0, 1, 3, 6), (0, 2, 3, 6), (1, 2, 3, 6))
n=8 upper: local counts=(5, 5, 5, 5, 4, 4, 5, 5); max=5; collinear four-subsets=((0, 1, 2, 3), (4, 5, 6, 7))
eight-point equality figure: all local counts=3, sum=24, cyclic four-subsets=((0, 1, 2, 3), (0, 1, 5, 7), (0, 2, 4, 5), (0, 2, 6, 7), (0, 3, 4, 6), (1, 2, 4, 6), (1, 3, 4, 7), (1, 3, 5, 6), (2, 3, 5, 7), (4, 5, 6, 7))
raw independent local-partition counts: n=7 -> 122^7=402271083010688; n=8 -> 715^8=68304345527688750390625
Er87b: source hash and 3 cited passages verified
Nozaki-Shinohara v2: source hash and 4 cited passages verified
Feng et al. v3: source hash and 4 cited passages verified
ErPa90 Crossref: DOI, title, authors, pages, and year verified
Er97e journal contents: 4 journal-contents phrases verified
transcript sha256: d0ab07a841aeb6b18889f710a164d3b7c28b0d2ab26abef69c07d542b30b15d1
ALL EXACT CHECKS PASSED

(d) These outputs verify the stated coordinates, pinned counts, cyclic tests, equality-configuration geometry, source hashes, and cited PDF passages. They are not being used to infer an unproved uniform theorem.

(d) A completely raw search for a seven-point locally three-distance counterexample to \(f(7)=4\) is already too large for this run. A partition of the six neighbours at one vertex into at most three distance classes has

\[ S(6,1)+S(6,2)+S(6,3)=1+31+90=122 \]

possibilities, giving \(122^7=402{,}271{,}083{,}010{,}688\) independent local patterns before edge consistency, symmetry, or Euclidean realisability. Even an impossible sustained rate of \(10^6\) complete patterns/second would take about \(12.75\) CPU-years. A serious search would need canonical edge-colouring generation followed by exact Euclidean-distance-matrix/real-algebraic feasibility; this raw enumeration was therefore not run.

6. Primary-source audit and search limits

(b) The following primary PDFs were downloaded, SHA-256 pinned, converted to text, and checked for the passages used above by --check-sources:

P. Erdős, “Some combinatorial and metric problems in geometry” (1987),

SHA-256 7637fce3170209f9d767d969d8c7c19b58144717f1a86798a4148aad2952a1f9. Page 168 gives the no-three-collinear/no-four-concyclic formulation, the \((n-1)/3\) bound, and the requested fixed improvement.

H. Nozaki and M. Shinohara,

“On a generalization of distance sets,” arXiv:0906.0199v2, SHA-256 ae3a6e820ff866ae3e214c86a625542d7fab2ebccbd4a8c8e59e288f23547b5b. Propositions 4.16 and 4.18 say exactly what is invoked in Sections 2 and 3.

T. Feng et al.,

“Semi-Autonomous Mathematics Discovery with Gemini: A Case Study on the Erdős Problems,” arXiv:2601.22401v3, SHA-256 fa2afcd192e6209183f44840f11632b266f2b973b722bb0b346ee39e3edee76e. Section 3.1 proves the two-axis \(3n/4\) counterexample. Version 3 also explicitly says that an attempted answer for the general-position variant was incorrect and was omitted.

(b) I verified the existence and bibliographic metadata of Erdős–Pach, “Variations on the theme of repeated distances,” Combinatorica 10 (1990), 261–269, but the publisher did not expose the full text in this environment. I therefore rely on the live problem page—not an invented reconstruction—for what its page 267 asks. Likewise, I verified the bibliographic record for Erdős’s 1997 “Some of my favourite unsolved problems,” but did not obtain a primary full-text scan; no exact-text assertion from it is used in the proof above.

(c) Exact-title, exact-phrase, arXiv, DOI, and citation searches did not locate a later primary source resolving the remaining \((1/3+c)n\) question. This is an honest search miss, not a proof of novelty, priority, or continued openness; the live page is the authority for the current status.

PARTIAL: Proved \(f(2)=1,\ f(3)=1,\ f(4)=2,\ f(5)=f(6)=3\), established \(3\leq f(7)\leq4\) and \(4\leq f(8)\leq5\), and supplied exact no-four-concyclic constructions and checks; the asymptotic \((1/3+c)n\) question remains open.

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