Erdős Problem #654

Problem 654: a precise defect parameter for the remaining lower bound

1) OBJECTIVE AND SOURCE REVIEW

Attempt dated 2026-09-23. I read all of 654.tex. Its two-axis construction correctly addresses the already disproved near-$n$ assertion under no four concyclic points, but does not settle the requested improvement above $(n-1)/3$, including the no-three-collinear version. The primary Aletheia paper likewise presents this as a partial result. I investigate the remaining general-position lower bound, rather than promoting the known counterexample to a full solution.

2) WORK

Let $X$ have $n$ distinct points, no three collinear and no four concyclic. For each centre $x\in X$, let $s_i(x)$ count its distance classes of size $i$, for $i=1,2,3$. Larger classes are excluded by the no-four-concyclic hypothesis. Thus \[ n-1=s_1(x)+2s_2(x)+3s_3(x),\qquad R_X(x)=s_1(x)+s_2(x)+s_3(x). \] For an unordered pair $\{y,z\}$, let $c(y,z)$ be the number of points $x\in X$ equidistant from $y,z$. Such points lie on the perpendicular bisector, so $0\le c(y,z)\le2$. Define its total deficit \[ D(X)=\sum_{\{y,z\}\subset X}(2-c(y,z))\ge0. \] Double-counting choices of an apex and an equal-distance pair yields \[ \sum_{\{y,z\}}c(y,z)=\sum_x(s_2(x)+3s_3(x)). \] Subtract from $n(n-1)=\sum_x(s_1+2s_2+3s_3)$ to obtain the exact identity \[ D(X)=\sum_x(s_1(x)+s_2(x)). \] Since $3R_X(x)-(n-1)=2s_1(x)+s_2(x)$, averaging now gives \[ \max_xR_X(x)\ge\frac{n-1}{3}+\frac{D(X)}{3n}. \] In particular, it would suffice to prove a uniform $D(X)\ge\delta n^2$ for some $\delta>0$. More concretely, if at least $\delta n^2$ unordered pairs have at most one equidistant apex in $X$, that same improved lower bound follows.

There is also a direct obstruction to transferring the supplied construction into general position while preserving all its distance coincidences. If three distinct observer points remain equidistant from the same pair of opposite-axis points, those three observers must remain on their common perpendicular bisector. They are therefore collinear. A perturbation satisfying no three collinear must destroy some of precisely the equalities used by the original construction; generic small displacement does not preserve its distance count bound.

3) ADVERSARIAL VERIFICATION

The formula for $D$ is an exact double count, not evidence that $D$ is quadratic. The elementary restrictions only guarantee nonnegativity, and proving the required quantitative deficit is the unresolved geometric step. The two-axis example contains arbitrarily large collinear subsets and cannot be used in this argument's general-position class.

4) FINAL

UNRESOLVED. A uniform quadratic deficit of saturated perpendicular bisectors would imply the desired positive linear improvement. No such deficit theorem or matching general-position construction is proved here.

5) SOURCES CHECKED

The complete supplied version; T. Feng et al., Semi-Autonomous Mathematics Discovery with Gemini: A Case Study on the Erdős Problems, https://arxiv.org/html/2601.22401v3, checked 2026-09-23 for the attribution and partial scope. The defect identity and perturbation obstruction are proved above.

6) COMPLETION ESTIMATE

Subjective progress toward the remaining linear-improvement question. COMPLETION: 15%

Problem #654

1. ROUND-2 OBJECTIVE

Path (B): explicit counterexample / disproof.

Round 1 left the main gap completely open: no counterexample family was known there. In Round 2 I give an explicit infinite family showing that the strongest form of the conjecture is false.

2. Round-1 FOUNDATION USED

I use only the Round-1 definition of \[ f(n):=\min_{|X|=n}\max_{x\in X} R_X(x) \] under the constraint that $X\subset \mathbf{R}^2$ has no four points on a circle, together with the trivial lower bound $f(n)\ge (n-1)/3$.

No nontrivial Round-1 lemma is needed for the disproof.

3. NEW INSIGHT / TOOL (ROUND 2)

The new construction has two ingredients.

• Put symmetric pairs of points on each coordinate axis. Then from any point on one axis, the distances to the opposite axis come in equal pairs, so the cross-axis contribution is halved.
• Choose the $x$-coordinates to be powers of $2$ and the $y$-coordinates to be powers of $3$. Then any product of two signed $x$-coordinates is a signed power of $2$, while any product of two signed $y$-coordinates is a signed power of $3$. This forbids the only possible $4$-point concyclicity pattern.

4. ATTACK PLAN (ROUND 2)

For each $t\ge 1$, define \[ X_t:=\{(\pm 2^i,0):1\le i\le t\}\cup\{(0,\pm 3^j):1\le j\le t\}. \] Then $|X_t|=4t$.

I prove two claims.

1. No four points of $X_t$ lie on a common circle.
2. Every point of $X_t$ determines at most $3t-1$ distinct distances to the other points.

These two claims imply \[ f(4t)\le 3t-1=\frac{3}{4}(4t)-1, \] which disproves the asymptotic statement $f(n)>(1-o(1))n$.

5. WORK (ROUND 2)

Fix $t\ge 1$, and define \[ A_t:=\{\pm 2^i:1\le i\le t\},\qquad B_t:=\{\pm 3^j:1\le j\le t\}, \] \[ X_t:=\{(a,0):a\in A_t\}\cup \{(0,b):b\in B_t\}. \] Then $|X_t|=4t$.

Claim 1: no four points of $X_t$ are concyclic.

A circle meets any fixed line in at most two points. Since all points of $X_t$ lie on the two coordinate axes, any set of four concyclic points from $X_t$ would have to consist of exactly two points on the $x$-axis and exactly two points on the $y$-axis. So it would have the form \[ (a,0),(a',0),(0,b),(0,b') \] with $a\ne a'$ and $b\ne b'$.

Suppose such four points lie on a circle. Write the equation of the circle as \[ x^2+y^2+ux+vy+w=0. \] Plugging in $(a,0)$ and $(a',0)$ shows that $a$ and $a'$ are roots of \[ x^2+ux+w=0, \] so by Viète's formula, \[ aa'=w. \] Similarly, plugging in $(0,b)$ and $(0,b')$ shows that $b$ and $b'$ are roots of \[ y^2+vy+w=0, \] so \[ bb'=w. \] Hence \[ aa'=bb'. \] But $aa'$ is a signed power of $2$, while $bb'$ is a signed power of $3$. These can never be equal. Contradiction.

Therefore no four points of $X_t$ lie on a common circle.

Claim 2: every point of $X_t$ sees at most $3t-1$ distinct distances.

Take first a point $p=(a,0)$ on the $x$-axis.

• There are $2t-1$ other points of $X_t$ on the $x$-axis, so their contribution to $R_{X_t}(p)$ is at most $2t-1$.
• For each $j\in\{1,\dots,t\}$, the two points $(0,3^j)$ and $(0,-3^j)$ are both at distance \[ \sqrt{a^2+3^{2j}} \] from $p$. So all $2t$ points on the $y$-axis contribute at most $t$ distinct distances.

Hence \[ R_{X_t}(p)\le (2t-1)+t=3t-1. \]

The same argument applies to a point on the $y$-axis by symmetry. Thus every point of $X_t$ determines at most $3t-1$ distinct distances.

So for $n=4t$ we have constructed an $n$-point set with no four points on a circle and with \[ \max_{x\in X_t}R_{X_t}(x)\le 3t-1=\frac{3n}{4}-1. \] Therefore \[ f(4t)\le \frac{3}{4}(4t)-1. \] In particular, \[ \limsup_{t\to\infty}\frac{f(4t)}{4t}\le \frac{3}{4}<1. \] So the statement $f(n)>(1-o(1))n$ is false.

6. ADVERSARIAL VERIFICATION

• The concyclicity proof covers all sign patterns: any product of two signed $x$-coordinates is $\pm 2^m$, and any product of two signed $y$-coordinates is $\pm 3^n$.
• A circle cannot contain three points from one axis and one from the other, because each axis meets a circle in at most two points.
• In the distance count I used only upper bounds, so possible accidental overlaps between same-axis and cross-axis distances can only help.
• The family is given for $n=4t$. That is enough to disprove an asymptotic assertion of the form $(1-o(1))n$, since such a statement must hold along every infinite subsequence.

7. FINAL

Partial known SOLUTION -- COUNTEREXAMPLE / DISPROOF

The strongest form of Problem #654 is false. The explicit family \[ X_t=\{(\pm 2^i,0):1\le i\le t\}\cup\{(0,\pm 3^j):1\le j\le t\} \] has no four points on a circle and satisfies \[ \max_{x\in X_t}R_{X_t}(x)\le \frac{3}{4}|X_t|-1. \] Thus $f(n)$ is not $(1-o(1))n$ in general. This agrees with the current status note on the Erdős Problems site [EP654].

8. COMPLETION ESTIMATE

COMPLETION: 30%

The conjecture that $f(n)>(1-o(1))n$ is false. Aletheia $2026$ constructed (n)-point sets in the plane with no four points on a circle such that every point determines at most $(3/4)n+O(1)$ distinct distances. However, this construction places all points on two lines and therefore does not resolve the stronger version of the problem for point sets in general position. Determining whether $f(n)>(1/3+c)n$ for some $c>0$ in general position remains open.

Problem #654

1) FORMAL RESTATEMENT

Let $X=\{x_1,\dots,x_n\}\subset\mathbb{R}^2$ be a set of $n$ distinct points such that no four points of $X$ lie on a common circle. For each $x\in X$, define \[ R_X(x)=\left\lvert \{\mathrm{dist}(x,y):y\in X\setminus\{x\}\} \right\rvert. \]

Question. Must there exist a point $x\in X$ with \[ R_X(x)\ge (1-o(1))n\qquad\text{as }n\to\infty? \] Equivalently: does every such $X$ contain a point from which all but $o(n)$ of the $n-1$ distances to other points are distinct?

2) QUICK LITERATURE/CONTEXT CHECK

• The problem is attributed to Erdős--Pach $1990$.
• A trivial lower bound holds for every point: since no circle can contain four points of $X$, for fixed $x\in X$ and fixed radius $r$, the circle of radius $r$ centered at $x$ contains at most $3$ points of $X$. Hence each distance value from $x$ occurs at most $3$ times, so $R_X(x)\ge (n-1)/3$.
• No general improvement beyond $(n-1)/3$ is known to me that approaches $(1-o(1))n$. There is related literature on "distinct distances under local conditions" (Fox--Pach--Suk) and on distinct distances in general position, but it does not directly settle this single-point, near-$n$ requirement.

3) ATTACK PLAN

1. Translate the condition $R_X(x)\le (1-\varepsilon)n$ into a statement about many repeated distances from $x$. Because multiplicity per distance is at most $3$, having $R_X(x)\le (1-\varepsilon)n$ forces $\Omega(\varepsilon n)$ many radii where the circle centered at $x$ contains 2 or 3 points.
2. Attempt a global contradiction if every point has many such repeated radii. Potential tools: incidence bounds for point--circle systems, and bounds on the number of isosceles triangles (each repeated distance at $x$ yields at least one isosceles triangle with apex $x$).
3. Try to show that forcing too many repeated radii at all points necessarily creates a forbidden 4-cocircular configuration.

4) WORK

The trivial $(n-1)/3$ bound (spelled out).

Fix $x\in X$. For each $r>0$, let \[ M_x(r):=\left\lvert \{y\in X\setminus\{x\}:\mathrm{dist}(x,y)=r\} \right\rvert. \] Then $\sum_r M_x(r)=n-1$ and $R_X(x)=\left\lvert \{r:M_x(r)\ge 1\} \right\rvert$. If $M_x(r)\ge 4$ for some $r$, then the circle of radius $r$ centered at $x$ contains at least four points of $X$ (namely those $y$ with $\mathrm{dist}(x,y)=r$), contradicting the hypothesis. Therefore $M_x(r)\le 3$ for all $r$. Hence \[ n-1=\sum_r M_x(r)\le 3\,\left\lvert \{r:M_x(r)\ge 1\} \right\rvert=3R_X(x), \] so \begin{equation}\label{wsref-0-65-71-3a-74-72-69-76-69-61-6c-36-35-34} R_X(x)\ge \frac{n-1}{3}\qquad\text{for every }x\in X. \end{equation}

Reformulation via isosceles triangles.

For fixed $x\in X$, the number of isosceles triangles with apex $x$ equals \[ T(x):=\sum_r \binom{M_x(r)}{2}. \] Because $M_x(r)\le 3$, each term is at most $\binom{3}{2}=3$, hence \[ T(x)\le 3R_X(x)\le 3(n-1). \] Conversely, if $R_X(x)=n-1-s$ (meaning $s$ "missing" distinct distances compared to the generic maximum), then the multiset $(M_x(r))_r$ has $\sum_r (M_x(r)-1)=s$. Under the cap $M_x(r)\le 3$, this forces at most linear many isosceles triangles at $x$: indeed $\binom{2}{2}=1$ and $\binom{3}{2}=3$, so $T(x)\le 3s$. Thus the conjectured conclusion $R_X(x)=(1-o(1))n$ is equivalent to the existence of some $x$ with $T(x)=o(n)$.

First gap: I do not see a known global upper bound forcing $\min_x T(x)=o(n)$ from the no-4-cocircular condition alone. The condition allows $T(x)$ to be linear for every $x$ (consistent with (eq:trivial654)), and showing that some $T(x)$ must actually be $o(n)$ appears to require new structure.

5) VERIFICATION / FAST REALITY CHECK

• Generic point sets satisfy the hypothesis (no four cocircular with probability $1$) and typically have $R_X(x)=n-1$ for every $x$, so the desired conclusion holds easily there. Thus the difficulty is purely worst-case.
• Collinear $n$-point sets also satisfy the hypothesis (any circle meets a line in at most two points). In that case, endpoints have $R_X(x)=n-1$, again consistent with the conjectured conclusion.
• Any potential counterexample must therefore enforce many repeated distances from every point while still avoiding any circle containing four of the points.

6) FINAL

UNRESOLVED

• (i) Farthest reached: Established the trivial universal bound $R_X(x)\ge (n-1)/3$ for every $x$ and reformulated the goal as finding $x$ with only $o(n)$ isosceles triangles as apex.
• (ii) Exact first gap: No argument is given that improves $(n-1)/3$ to $(1-\varepsilon)n$ for any fixed $\varepsilon>0$, nor a construction showing the opposite. The missing ingredient is a global constraint that forces at least one point to have very few repeated distances.
• (iii) Most promising next moves:
  1. Develop a quantitative "circle-richness" incidence bound adapted to circles centered at points of $X$ with bounded co-circularity, to show that not all points can have $\Theta(n)$ radii with multiplicity $\ge 2$.
  2. Translate repeated distances at many centers into many coincident perpendicular bisectors, then use rich-bisector bounds (of the type used in crossing-number distinct-distance arguments) to force a forbidden cocircularity.
  3. Explore whether adding the mild extra assumption "no three collinear" (full general position) changes the answer; some known distinct-distance results under local conditions may become more effective in that regime.
• (iv) What would finish it:
  • Either prove that in every $n$-point set with no four cocircular there exists $x$ with $R_X(x)\ge n-n^{\gamma}$ for some $\gamma<1$ (already implies $(1-o(1))n$),
  • or give an explicit construction (for infinitely many $n$) with no four cocircular but with $\max_{x\in X} R_X(x)\le (1-\varepsilon)n$ for some fixed $\varepsilon>0$.

7) COMPLETION ESTIMATE

Not complete (open problem as far as I can verify quickly); this writeup isolates equivalent formulations and the current bottleneck.

References

• [Mathialagan2021] S. Mathialagan, On bipartite distinct distances in the plane, The Electronic Journal of Combinatorics 28$4$ $2021$, #P4.33.
• [Elekes1995] G. Elekes, Circle grids and bipartite graphs of distances, Combinatorica 15 $1995$, 167--174.
• [CsizmadiaIsmailescu1997] Gy. Csizmadia and D. Ismailescu, Maximum number of different distance counts, in: Intuitive Geometry (Budapest, 1995), Bolyai Society Mathematical Studies 6 $1997$, 301--309.
• [ErdosPach1990] P. Erdős and J. Pach, Variations on the theme of repeated distances, Combinatorica 10 $1990$, 261--269.