Erdős problem 657 — wave w006

Date: 2026-07-28 (UTC)

Claim labels used throughout:

• [a] elementary-rigorous: proved here from elementary facts and exact arithmetic.
• [b] rigorous-modulo-named-theorem: the cited conclusion follows from the named published theorem(s).
• [c] plausible/structural-unverified: a search result, interpretation, or structural lead that is not claimed as a theorem.
• [d] computational-only: observed by computation but not promoted to a theorem.

0. Mandatory live-page gate

I fetched both the live problem page and its discussion thread through the Bright Data browser on 2026-07-28. This was a real browser rendering, not the stale tracker YAML or a direct curl.

Live statement (verbatim; only line wrapping and TeX rendering normalized)

Is it true that if \(A\subset \mathbb{R}^2\) is a set of \(n\) points such that every subset of \(3\) points determines \(3\) distinct distances (i.e. \(A\) has no isosceles triangles) then \(A\) must determine at least \(f(n)n\) distinct distances, for some \(f(n)\to \infty\)?

Source: live problem 657.

Gate status

• [a] The rendered badge says OPEN.
• [a] The page says 0 claimed proofs for this problem.
• [a] “Currently working on this problem”: None.
• [a] “Interested in collaborating”: None.
• [a] The other work/difficulty/formalisation markers are also None; the

only listed like is Alfaiz.

• [a] The page says it was last edited 15 October 2025 and displays six

comments. Therefore the requested stop condition was absent and I proceeded.

All known-result text shown on the page

• [b] The page attributes the \( \mathbb R^k\) problem to Erdős and

R. O. Davies in [Er73]. The primary scan really does state this, asks whether the minimum number divided by \(n\) tends to infinity, says this is unproved even for \(k=1\), and records Straus's \(2^k\ge n\) construction with \(n-1\) distances. See Erdős 1973, pp. 136–137 of the scan.

• [a, source report] The live page says [Er97e] instead names Erdős,

Füredi, Ruzsa, and Pach as investigators, without Davies.

• [b] On the line, “no isosceles triangle” is exactly “no nontrivial

three-term arithmetic progression,” and positive distances are half of the nonzero difference set. Dumitrescu proved superlinear growth and in particular a lower bound \(n(\log n)^c\), while Behrend-type constructions give \(n2^{O(\sqrt{\log n})}\). The actual primary paper is A. Dumitrescu, On distinct distances and \(\lambda\)-free point sets, Discrete Mathematics 308 (2008), 6533–6538, doi:10.1016/j.disc.2007.11.046.

• [b] The page's newer one-dimensional bound is

\[ \frac{|A-A|}{|A|} \ge 2^{c(\log |A|)^{1/9}}. \] It combines Ruzsa's sumset bound with modern bounds on \(r_3(N)\). The advertised exponent is verified in Bloom–Sisask, arXiv:2309.02353, whose abstract states \(r_3(N)\le N\exp(-c(\log N)^{1/9})\). The predecessor is Kelley–Meka, arXiv:2302.05537.

• [b] Straus's observation on the page is high-dimensional:

if \(2^k\ge n\), there are \(n\) points in \(\mathbb R^k\), with no isosceles triangle, determining at most \(n-1\) distances. It does not give a planar construction for unbounded \(n\).

• [a, source report] The page cross-references problem 135.

All six comments shown in the live discussion

The site explicitly warns that comments are not verified. I therefore record their content but do not silently upgrade it to theorem status.

1. [a] Quanyu Tang (2025-10-02 05:42) gives the matching-color lower bound

\[ \phi(n,3,3)\ge \begin{cases} n,&n\text{ odd},\\ n-1,&n\text{ even}, \end{cases} \] and notes tightness for \(n=3\) and \(n=4\).

1. [c] Alfaiz (2025-10-01 12:41) expands the Ruzsa/Kelley–Meka argument,

but initially asserts an invalid planar-to-line projection.

1. [b] Quanyu Tang (2025-10-01 15:52) observes that Ruzsa's original

equation (9.4) directly yields \(|A+A|\ge c n(n/r_3(n))^{1/4}\), and combines this with \(|A+A||A|\le |A-A|^2\). This is a one-dimensional/torsion-free-group statement.

1. [a] Quanyu Tang (2025-10-01 19:34) identifies the decisive gap:

projection of a planar set to a line does not preserve the no-isosceles property. Thus the quasipolynomial improvement does not answer the planar question.

1. [a] Alfaiz (2025-10-02 01:56) accepts the correction and says the

planar question remains open.

1. [b] Zach Hunter (2025-08-19 06:16) gives the original concise

Ruzsa + Plünnecke–Ruzsa + Kelley–Meka route for the one-dimensional quasipolynomial improvement; the page says it was updated to incorporate this.

Discussion source: problem 657 thread.

1. Literature audit beyond the page

• [b] Fox–Pach–Suk, More distinct distances under local conditions,

Combinatorica 38 (2018), explicitly says \(D(n,3,3)\ge n-1\), records the \(n2^{O(\sqrt{\log n})}\) upper bound, and says \(\lim D(n,3,3)/n=\infty\) remains open: author PDF, doi:10.1007/s00493-016-3637-X.

• [b] Pohoata–Sheffer,

Local Properties in Colored Graphs, Distinct Distances, and Difference Sets, arXiv:1807.00201, defines the same \(\phi(n,k,\ell)\) and records only \(\phi(n,3,3)=\Omega(n)\) for this parameter. Its stronger local-color theorems concern other parameter ranges.

• [b] Fish–Lund–Sheffer,

A Construction for Difference Sets with Local Properties, arXiv:1812.07651, is genuinely about difference sets on the line. It does not repair the failed planar projection.

• [b] A very recent related primary source is Croot–Mao–Pohoata–Sheffer–Yip,

A combinatorial large sieve for Sidon sets, distances, and norm forms, arXiv:2606.17487v2. It proves a strong upper bound on the size of an isosceles-free subset of the arithmetic box \([N]^2\). This is a restriction on subsets of a fixed lattice box, not a lower bound on the number of distances of an arbitrary real planar set, so it does not settle problem 657.

• [c] Targeted searches by the exact notation \(\phi(n,3,3)\), by the

statement “no isosceles triangles,” and through the cited-paper chain found no primary source giving an asymptotic planar improvement or the exact \(n=5,6\) values below. This is a literature-search miss, not a claim that the small table is unpublished.

2. Notation and the universal matching bound

Let \(\phi(n)=\phi(n,3,3)\). Color each edge of \(K_n\) by its Euclidean length.

[a] Lemma 1 (matching bound). Every color class is a matching. Hence

Indeed, two same-colored edges meeting at a vertex are exactly an isosceles triangle (including the collinear, degenerate case). This reproduces the thread's parity sharpening from scratch.

3. Exact five-point construction: \(\phi(5)=5\)

The matching bound gives \(\phi(5)\ge5\). The following algebraic configuration attains it.

Let \(a\) be the unique root in

of

Existence follows from the opposite signs of \(q\) at the two rational endpoints. Exact interval evaluation gives

throughout this interval, proving uniqueness.

Define

and

Numerically, only for orientation,

[a] Exact distance certificate. Reducing the expanded squared distances modulo \(q(a)=0\) gives the following five classes:

| edges | common squared distance | decimal guide | |---|---:|---:| | \(14,23\) | \(\frac{2(552a^3+304a^2-243a-202)}{363}\) | \(0.844856890741\ldots\) | | \(01,24\) | \(1\) | \(1\) | | \(02,34\) | \(\frac{4(6a^3+98a^2+96a-89)}{363}\) | \(0.745992381189\ldots\) | | \(03,12\) | \(d^2\) | \(0.041576596173\ldots\) | | \(04,13\) | \(1+d^2\) | \(1.041576596173\ldots\) |

Exact rational interval arithmetic on the isolating interval for \(a\) proves all five displayed values positive and pairwise distinct. Each row consists of two disjoint edges, so at every vertex its four incident distances are different. Thus these are five distinct points with no isosceles triangle and exactly five distances. Together with Lemma 1:

No decimal approximation is used in this proof.

4. A geometric obstruction at six points

Lemma 1 only gives \(\phi(6)\ge5\). Geometry excludes equality.

[a] Lemma 2. Six planar points with no isosceles triangle cannot determine only five distances.

Proof. Suppose they did. The 15 edges are partitioned into five matchings, each of size at most three. Equality forces all five color classes to be perfect matchings. Consequently every point has one incident edge of each of the five squared lengths, so the sum \(S\) of squared distances from a point to all the other points is independent of the point.

Let \(g\) be the centroid. For every \(i\),

The left side is the same \(S\), so all six points lie on one circle centered at \(g\).

Order them cyclically as \(P_0,\ldots,P_5\). A globally shortest chord must join consecutive cyclic points: otherwise a point in its shorter arc gives a still shorter subchord. Its color is a perfect matching of the six-cycle, so, after relabeling, the three shortest chords are

Their positive cyclic angular gaps are all the same, say \(x\). (Equal chords have gaps \(x\) or \(2\pi-x\); one complementary gap together with the other two already has sum \(>2\pi\).)

Write the gap from \(P_1\) to \(P_2\) as \(y>0\). The disjoint chords \(P_0P_2\) and \(P_1P_3\) both subtend the arc \(x+y\), so they have equal length. This length is not the shortest one: equality with the chord of gap \(x\) would force \(x+y=2\pi-x\), which is incompatible with the three positive \(x\)-gaps and the remaining positive gaps summing to \(2\pi\). Because equal-length edges cannot meet, a third edge of this new length would have to be \(P_4P_5\), but that edge has the strictly shorter length. Thus this color class has size exactly two, contradicting the fact that all five classes have size three. \(\square\)

Therefore \(\phi(6)\ge6\).

5. Exact six-point construction: \(\phi(6)=6\)

Put \(r=\sqrt7\), and take

[a] Exact distance certificate. Direct arithmetic in \(\mathbb Q(\sqrt7)\) gives:

| edges | common squared distance | decimal guide | |---|---:|---:| | \(03,12\) | \(37152-3008r\) | \(29193.580056\ldots\) | | \(05,14\) | \(27648-1688r\) | \(23181.971787\ldots\) | | \(04,15,23\) | \(36800-3800r\) | \(26746.145018\ldots\) | | \(25,34\) | \(20256+2800r\) | \(27664.103671\ldots\) | | \(01,24,35\) | \(30976\) | \(30976\) | | \(02,13,45\) | \(3712-1248r\) | \(410.102364\ldots\) |

The exact sign test for \(A+B\sqrt7\) compares \(A^2\) with \(7B^2\); it proves these six values positive and pairwise distinct. Within every row the listed edges are disjoint. Hence every vertex sees five different lengths, so the set has no isosceles triangle and determines exactly six distances. With Lemma 2:

6. Verified small table

Combining the thread's elementary \(n=3,4\) examples with the two exact certificates above gives:

| \(n\) | \(\phi(n,3,3)\) | lower bound | attaining example | |---:|---:|---|---| | 3 | 3 | matching bound | any scalene triangle | | 4 | 3 | matching bound | a non-square rectangle | | 5 | 5 | matching bound | algebraic construction in §3 | | 6 | 6 | Lemma 2 | \(\mathbb Q(\sqrt7)\) construction in §5 |

[a] Thus the exact table through six points is

7. Independent code and executed result

The standalone checker is erdos657_wavew006_reverify.py. It uses only the Python standard library.

It independently:

1. implements exact polynomial arithmetic in

\(\mathbb Q[a]/(q(a))\);

1. isolates the selected root using rational endpoint signs and an exact

positive derivative interval;

1. expands all ten five-point squared distances, reduces them modulo \(q\),

and proves positivity/distinction with rational interval arithmetic;

1. implements exact \(\mathbb Q(\sqrt7)\) arithmetic and checks all fifteen

six-point distances and their matching classes;

1. recomputes the matching lower bound and the two alternating perfect

matchings of the six-cycle used in Lemma 2.

Run:

python runs/erdos657_wavew006_reverify.py

Executed result on this VM:

PASS: all exact checks succeeded
certified exact table: phi(n,3,3) for n=3,4,5,6 is 3,3,5,6

The complete executable source is in the standalone file; all proof decisions use fractions.Fraction or exact pairs \(A+B\sqrt7\).

[d] Numerical least-squares and small-grid searches were used only as discovery tools for candidate equality patterns. They are not used by, and are not evidence needed for, any boxed result.

8. What remains and the precise asymptotic wall

• [a] A distance coloring with no isosceles triangles is a proper edge

coloring of \(K_n\), and that fact alone gives only the linear matching bound. Lemma 2 gains something because hypothetical equality at \(n=6\) makes every color a perfect matching; this forces constant squared-distance row sums and hence concyclicity.

• [a] The six-point cyclic contradiction does not automatically extend:

for larger even \(n\), the two equal second-neighbor chords can be completed to a matching using the remaining \(n-4\) vertices. More importantly, under a general \(O(n)\)-distance hypothesis the color classes need not be perfect, the row sums need not agree, and the concyclicity step disappears.

• [c] A useful missing lemma would have to convert “\(\binom n2\) edges

split among \(O(n)\) Euclidean matchings” into a large subconfiguration whose squared-distance row sums (or cyclic order) are sufficiently rigid. No theorem found in the cited local-distance literature supplies that extraction.

• [a] The one-dimensional machinery cannot fill this gap: an arbitrary

projection can create equal distances/three-term progressions. The 2026 large-sieve theorem likewise relies on the ambient arithmetic box and norm congruences, which arbitrary real planar coordinates do not possess.

Accordingly, this report makes exact, reproducible small-case progress but does not claim any uniform superlinear lower bound.

PARTIAL: Exact elementary/algebraic certificates prove \(\phi(n,3,3)=3,3,5,6\) for \(n=3,4,5,6\); the planar asymptotic question remains open.