Erdős Problem #653

Problem #653

1. ROUND-3 OBJECTIVE

Path (C): obstruction / correction at the level of strategy.

I build strictly on the Round-2 progress, whose main new theorem was the exact collinear formula \[ g_{\mathrm{line}}(n)=\left\lceil\frac{n}{2}\right\rceil. \] The most promising next step is to show that this is not merely a one-line phenomenon: the same $\lceil n/2\rceil$ barrier persists for points on a single circle, and more generally for any configuration with all but $t$ points on one line or one circle. This would rule out an entire family of "one-dimensional" or "almost one-dimensional" constructions.

Throughout, for a finite set $X\subset \mathbf{R}^2$, I write \[ R_X(x):=\left|\{ |x-y|:y\in X\setminus\{x\}\}\right|, \qquad V(X):=\left|\{R_X(x):x\in X\}\right|. \] Thus $g(n)=\max_{|X|=n}V(X)$.

2. Round-2 FOUNDATION USED

I use the following Round-2 results as fixed input.

• The exact collinear theorem: if $X$ is any $n$-point set contained in a line, then \[ V(X)\le \left\lceil\frac{n}{2}\right\rceil, \] and equality is attained by an arithmetic progression.
• The explicit line construction $X=\{0,1,\dots,n-1\}$, for which the attained values are exactly \[ \left\lceil\frac{n-1}{2}\right\rceil,\left\lceil\frac{n-1}{2}\right\rceil+1,\dots,n-1. \]
• The global status and bounds recorded on the Erdős Problems page: the problem remains open, with known bounds $g(n)>\tfrac38 n$, $g(n)>\tfrac{7}{10}n$, and $g(n)<n-cn^{2/3}$ for some absolute $c>0$ [EP653].

3. NEW INSIGHT / TOOL (ROUND 3)

There are two genuinely new ingredients in this round.

(i) Exact circular analogue. If all $n$ points lie on a common circle, then again \[ V(X)\le \left\lceil\frac{n}{2}\right\rceil, \] and this is sharp.

(ii) Stability with outliers. If $X$ has $m$ points on one line or one circle and $t=n-m$ arbitrary outliers, then \[ V(X)\le 2t+\left\lceil\frac{m}{2}\right\rceil. \] Equivalently, if at least $n-t$ points lie on a common line or circle, then \[ V(X)\le 2t+\left\lceil\frac{n-t}{2}\right\rceil. \] In particular, if $t=o(n)$, then \[ V(X)\le \frac{n}{2}+o(n), \] so any eventual construction with $V(X)=(1-o(1))n$ must be genuinely non-concentrated: it cannot place $n-o(n)$ points on a single line or circle.

A sharper corollary is that if $V(X)=(1-o(1))n$, then no line or circle can contain more than $(\tfrac23+o(1))n$ points.

4. ATTACK PLAN (ROUND 3)

The exact gap left after Round 2 was this: the collinear theorem ruled out only a single line. It did not say anything about other natural one-dimensional supports (especially circles), nor about "almost collinear" or "almost cyclic" constructions with a small number of outliers.

The plan is therefore:

1. prove that for points on a common circle, every fixed point sees each distance with multiplicity at most $2$, giving the same $\lceil n/2\rceil$ upper bound as in the line case;
2. show that a short-arc circular arithmetic progression attains $\lceil n/2\rceil$, making the circular bound sharp;
3. add $t$ arbitrary outliers and observe that each outlier can create at most one new distance from any prescribed point on the line/circle support, yielding the stability inequality \[ V(X)\le 2t+\left\lceil\frac{m}{2}\right\rceil. \]

This overcomes the Round-2 obstacle by ruling out an entire class of strategies, not just a single exact model.

5. WORK (ROUND 3)

Lemma 1 (distance multiplicity on a circle).

Proof. Let the circle have centre $O$ and radius $r$. Apply a rigid motion so that $O=(0,0)$ and $x=(r,0)$. Any point $y\in C$ has the form \[ y=(r\cos\theta,r\sin\theta) \] for some $\theta\in [0,2\pi)$. Then \[ |x-y|^2=(r-r\cos\theta)^2+(r\sin\theta)^2=2r^2(1-\cos\theta). \] Thus the distance $|x-y|$ depends only on $\cos\theta$. If two points $y,z\in C$ satisfy $|x-y|=|x-z|$, then their angles $\theta,\phi$ satisfy $\cos\theta=\cos\phi$, hence $\phi\equiv \pm \theta\pmod{2\pi}$. Therefore either $y=z$ or $z$ is the reflection of $y$ across the diameter $Ox$.

So for each fixed distance from $x$, there are at most two points of $C$ at that distance from $x$. Since there are $m-1$ points in $Y\setminus\{x\}$, the number of distinct distances from $x$ to $Y\setminus\{x\}$ is at least $\lceil (m-1)/2\rceil$, and trivially at most $m-1$. $\square$

Theorem 2 (exact line/circle bound).

Proof. The line case was proved in Round 2, so only the circle case is new.

Let $Y$ be any $n$-point set on a common circle. By Lemma 1, for every $y\in Y$, \[ \left\lceil\frac{n-1}{2}\right\rceil \le R_Y(y)\le n-1. \] Hence every value $R_Y(y)$ lies in the integer interval \[ \left\lceil\frac{n-1}{2}\right\rceil,\left\lceil\frac{n-1}{2}\right\rceil+1,\dots,n-1, \] which contains exactly \[ (n-1)-\left\lceil\frac{n-1}{2}\right\rceil+1=\left\lceil\frac{n}{2}\right\rceil \] integers. Therefore \[ V(Y)\le \left\lceil\frac{n}{2}\right\rceil. \]

To see that this is sharp, choose a circle of radius $1$ and pick points \[ y_i=(\cos(i\delta),\sin(i\delta)),\qquad i=0,1,\dots,n-1, \] where $\delta>0$ is so small that \[ (n-1)\delta<\pi. \] Then for each fixed $i$, the distance between $y_i$ and $y_j$ is \[ |y_i-y_j|=2\sin\!\left(\frac{|i-j|\delta}{2}\right). \] Because $0\le |i-j|\delta<\pi$, the function $u\mapsto 2\sin(u/2)$ is strictly increasing on the relevant interval, so equal distances from $y_i$ correspond exactly to equal values of $|i-j|$. Hence \[ R_Y(y_i)=\max\{i,n-1-i\}. \] As $i$ runs from $0$ to $n-1$, these values are precisely \[ \left\lceil\frac{n-1}{2}\right\rceil,\left\lceil\frac{n-1}{2}\right\rceil+1,\dots,n-1, \] so \[ V(Y)=\left\lceil\frac{n}{2}\right\rceil. \] This proves the circle case, and therefore the combined line/circle statement. $\square$

Theorem 3 (stability with outliers).

Proof. Fix $y\in Y$. Let \[ S_Y(y):=\{ |y-y'|:y'\in Y\setminus\{y\}\} \] and \[ S_Z(y):=\{ |y-z|:z\in Z\}. \] Then \[ R_X(y)=|S_Y(y)\cup S_Z(y)|. \] By Theorem 2, the line/circle support gives \[ \left\lceil\frac{m-1}{2}\right\rceil \le |S_Y(y)|\le m-1. \] Since $|S_Z(y)|\le t$, adding the outliers can create at most $t$ new distances. Therefore \[ \left\lceil\frac{m-1}{2}\right\rceil \le R_X(y)\le m-1+t=n-1. \] So every value $R_X(y)$ with $y\in Y$ lies in the integer interval \[ \left\lceil\frac{m-1}{2}\right\rceil,\left\lceil\frac{m-1}{2}\right\rceil+1,\dots,n-1, \] which contains exactly \[ (n-1)-\left\lceil\frac{m-1}{2}\right\rceil+1 = n-\left\lceil\frac{m-1}{2}\right\rceil = t+\left\lceil\frac{m}{2}\right\rceil \] integers. Hence the points of $Y$ contribute at most \[ t+\left\lceil\frac{m}{2}\right\rceil \] distinct values to $V(X)$.

The remaining points are the $t$ points of $Z$, which contribute at most $t$ additional values. Therefore \[ V(X)\le \left(t+\left\lceil\frac{m}{2}\right\rceil\right)+t =2t+\left\lceil\frac{m}{2}\right\rceil. \] This proves the claim. $\square$

Corollary 4 (obstruction to asymptotic extremality).

Proof. Apply Theorem 3 with $t=n-m$: \[ V(X)\le 2(n-m)+\left\lceil\frac{m}{2}\right\rceil \le 2n-2m+\frac{m}{2}+\frac12 =2n-\frac{3m}{2}+\frac12. \] Now if also $V(X)\ge (1-\eta)n$, then \[ (1-\eta)n\le 2n-\frac{3m}{2}+\frac12, \] so \[ \frac{3m}{2}\le (1+\eta)n+\frac12, \qquad\text{hence}\qquad m\le \frac{2+2\eta}{3}n+\frac13. \] The asymptotic statement follows immediately. $\square$

6. ADVERSARIAL VERIFICATION

I now try to break the new arguments.

• Circle multiplicity lemma. Could one distance from a fixed point on a circle be realised by three or more points? No: the squared distance is $2r^2(1-\cos\theta)$, and a fixed value of $\cos\theta$ gives only the two possibilities $\theta$ and $-\theta$ modulo $2\pi$, except for the antipodal case where there is only one point.

• Sharpness construction on a circle. The choice $(n-1)\delta<\pi$ is essential. It ensures that the chord-length function is strictly increasing in $|i-j|\delta$, so no accidental equalities occur beyond the obvious symmetry $|i-j|=|i-k|$.

• Stability theorem. I only used the interval containment \[ \left\lceil\frac{m-1}{2}\right\rceil\le R_X(y)\le n-1 \quad (y\in Y), \] not any exact formula. So accidental coincidences between distances to $Y$ and distances to outliers in $Z$ can only decrease $R_X(y)$, never increase it beyond the interval bound.

• Quantifiers. The obstruction is uniform in $n,m,t$: it does not assume that $t$ is fixed or small. The asymptotic corollary is obtained only afterwards by substituting $t=n-m$.

• Interaction with Round 2. Theorem 2 does not reprove the line case from scratch; it imports the Round-2 collinear theorem and adds only the genuinely new circle case.

No inconsistency with the Round-2 writeup was found.

7. FINAL

UNRESOLVED (BUT STRICTLY ADVANCED)

The full planar problem remains open. However, Round 3 makes a substantive advance beyond Round 2:

• it proves the exact same extremal value $\lceil n/2\rceil$ for point sets on a single circle as for point sets on a single line;
• it proves the stability bound \[ V(X)\le 2t+\left\lceil\frac{n-t}{2}\right\rceil \] whenever all but $t$ points lie on one line or one circle;
• consequently, any putative family with $V(X)=(1-o(1))n$ must avoid placing more than $(\tfrac23+o(1))n$ points on any single line or circle.

This rules out the entire "near-line / near-circle" strategy class.

8. COMPLETION ESTIMATE

COMPLETION: 55%

9. REFERENCES

References

• [EP653] T. F. Bloom, Erdős Problem #653, Erdős Problems website, accessed 2026-03-07.
• [EF97] P. Erdős and P. Fishburn, Distinct distances in finite planar sets, Discrete Mathematics 175 $1997$, 97--132.
• [CsI97] Gy. Csizmadia and D. Ismailescu, Maximum number of different distance counts, in Intuitive Geometry (Budapest, 1995), Bolyai Society Mathematical Studies 6 $1997$, 301--309.

Problem 653: outliers also obey the distance multiplicity restriction

1) OBJECTIVE AND SOURCE REVIEW

2) WORK

If $Y$ lies on a nondegenerate circle $C$ with centre $O$, precisely the same argument holds for every $x\ne O$: a circle centred at $x$ is distinct from $C$, and two distinct circles meet in at most two points. The centre $O$, if it belongs to $X$, is the sole exception. Therefore \[ V(X)\le n-\left\lceil\frac{m-1}{2}\right\rceil+\mathbf1_{O\in X}. \] For completeness, the intersection assertion follows by subtracting the two circle equations: common points lie on a line, which meets either nondegenerate circle at most twice.

Consequently a configuration satisfying $V(X)\ge(1-\eta)n$ has at most $2\eta n+1$ points on any line and at most $2\eta n+3$ on any circle. In particular, if $V(X_n)=(1-o(1))|X_n|$, then every line and every circle contains $o(|X_n|)$ points. This is stronger than the supplied bound allowing roughly two thirds of the points on such a support.

3) ADVERSARIAL VERIFICATION

4) FINAL

5) SOURCES CHECKED

6) COMPLETION ESTIMATE

Problem #653

1. ROUND-2 OBJECTIVE

Path (C): obstruction / correction at the level of strategy.

Round 1 gave only the baseline lower bound $g(n)\ge \lceil n/2\rceil$ from equally spaced collinear points. I now prove that this baseline is best possible inside the entire collinear class. So any eventual construction proving $g(n)\ge (1-o(1))n$ must be genuinely two-dimensional.

2. Round-1 FOUNDATION USED

I use the following Round-1 ingredients.

• The definition \[ g(n):=\max\left|\{R_X(x):x\in X\}\right|, \] where $R_X(x)$ is the number of distinct distances from $x$ to the other points of $X$.
• The explicit Round-1 construction $X=\{0,1,\dots,n-1\}$ on a line, for which the attained values are exactly \[ \left\lceil\frac{n-1}{2}\right\rceil,\left\lceil\frac{n-1}{2}\right\rceil+1,\dots,n-1, \] so $g(n)\ge \lceil n/2\rceil$.
• The known global literature bounds quoted in Round 1 (namely $g(n)>\tfrac{7}{10}n$ and $g(n)<n-cn^{2/3}$); I do not reprove them here [EP653].

3. NEW INSIGHT / TOOL (ROUND 2)

The new theorem is an exact classification for collinear point sets.

Theorem. Let $g_{\mathrm{line}}(n)$ be the maximum possible number of distinct values of $R_X(x)$ over all $n$-point sets $X\subset \mathbf{R}^2$ contained in a single line. Then \[ g_{\mathrm{line}}(n)=\left\lceil\frac{n}{2}\right\rceil. \]

This strictly advances Round 1: the previously known baseline construction is now shown to be optimal for all collinear sets, so the one-dimensional strategy is exhausted.

4. ATTACK PLAN (ROUND 2)

The Round-1 gap was that the collinear construction was only exhibited, not understood structurally.

For a collinear set $X=\{a_1<\cdots<a_n\}$, I write the distances from $a_i$ to the left and to the right separately. Distances on the same side are automatically distinct. The only possible collisions are between one left distance and one right distance, and each such collision corresponds exactly to a symmetric pair around $a_i$.

This reduces the problem to bounding the number of symmetric pairs around a point, which is at most $\lfloor (n-1)/2\rfloor$. That forces all the values $R_X(a_i)$ into an interval of length $\lceil n/2\rceil$, giving the desired exact upper bound.

5. WORK (ROUND 2)

Let \[ X=\{a_1<a_2<\cdots<a_n\}\subset \mathbf{R} \] be a collinear $n$-point set. For each $i$, let \[ L_i:=\{a_i-a_j:1\le j<i\},\qquad U_i:=\{a_j-a_i:i<j\le n\}. \] Then $L_i$ and $U_i$ are sets of positive real numbers, and \[ |L_i|=i-1,\qquad |U_i|=n-i, \] because all distances on a fixed side are automatically distinct.

The set of all distinct distances from $a_i$ to the other points is exactly $L_i\cup U_i$, so \[ R_X(a_i)=|L_i\cup U_i|=|L_i|+|U_i|-|L_i\cap U_i|. \] Hence \[ R_X(a_i)=n-1-|L_i\cap U_i|. \]

Now $d\in L_i\cap U_i$ if and only if there exist indices $j<i<k$ such that \[ a_i-a_j=d=a_k-a_i, \] that is, \[ a_j+a_k=2a_i. \] So $|L_i\cap U_i|$ is exactly the number of symmetric pairs of points of $X$ around $a_i$. Denote this number by $p_i$. Then \[ R_X(a_i)=n-1-p_i. \]

Clearly \[ p_i\le \min(i-1,n-i)\le \left\lfloor\frac{n-1}{2}\right\rfloor. \] Therefore \[ R_X(a_i)\ge n-1-\left\lfloor\frac{n-1}{2}\right\rfloor =\left\lceil\frac{n-1}{2}\right\rceil. \] Trivially also $R_X(a_i)\le n-1$. Thus every value $R_X(a_i)$ belongs to the integer interval \[ \left\lceil\frac{n-1}{2}\right\rceil,\left\lceil\frac{n-1}{2}\right\rceil+1,\dots,n-1. \] The number of integers in this interval is \[ (n-1)-\left\lceil\frac{n-1}{2}\right\rceil+1=\left\lceil\frac{n}{2}\right\rceil. \] So any collinear $n$-point set satisfies \[ \left|\{R_X(x):x\in X\}\right|\le \left\lceil\frac{n}{2}\right\rceil. \] Hence \[ g_{\mathrm{line}}(n)\le \left\lceil\frac{n}{2}\right\rceil. \]

On the other hand, for the arithmetic progression \[ X=\{0,1,\dots,n-1\} \] we have \[ R_X(i)=\max(i,n-1-i) \] for $0\le i\le n-1$, so the attained values are exactly \[ \left\lceil\frac{n-1}{2}\right\rceil,\left\lceil\frac{n-1}{2}\right\rceil+1,\dots,n-1. \] Thus \[ g_{\mathrm{line}}(n)\ge \left\lceil\frac{n}{2}\right\rceil. \] Combining the two inequalities gives \[ g_{\mathrm{line}}(n)=\left\lceil\frac{n}{2}\right\rceil. \]

6. ADVERSARIAL VERIFICATION

• The key identity $R_X(a_i)=n-1-p_i$ uses the fact that collisions cannot occur among distances on the same side of $a_i$; this is valid because the points are strictly ordered on a line.
• A distance can be counted twice only via one point on the left and one point on the right; that is exactly the symmetric-pair condition.
• Edge cases match the formula: for $n=1,2,3$ the theorem gives $1,1,2$, which are correct.
• The arithmetic progression really attains every value in the interval, so the upper bound is sharp.

7. FINAL

UNRESOLVED (BUT STRICTLY ADVANCED)

The full planar problem remains open, but Round 2 proves the exact collinear extremal value \[ g_{\mathrm{line}}(n)=\left\lceil\frac{n}{2}\right\rceil. \] This rules out the entire collinear strategy class as a route to $g(n)\ge (1-o(1))n$.

8. COMPLETION ESTIMATE

COMPLETION: 40%