gpt pro 5.2 attempt on Math-888

Problem #653

1) FORMAL RESTATEMENT

Let $X=\{x_1,\dots,x_n\}\subset\mathbb{R}^2$ be a set of $n\ge 2$ distinct points. For each $x\in X$, let \[ R_X(x)=\left\lvert \{\mathrm{dist}(x,y):y\in X\setminus\{x\}\} \right\rvert. \] Let \[ V(X):=\left\lvert \{R_X(x):x\in X\} \right\rvert\in\{1,2,\dots,n\} \] be the number of distinct distance-count values realized by points of $X$. Define \[ g(n):=\max\{V(X):X\subset\mathbb{R}^2,\ \left\lvert X \right\rvert=n\}. \]

Question. Is it true that $g(n)\ge (1-o(1))n$ as $n\to\infty$? Equivalently: can one realize $n-o(n)$ distinct values among the integers $R_X(x)\in\{1,\dots,n-1\}$?

2) QUICK LITERATURE/CONTEXT CHECK

The standard references (as quoted in the problem statement) give:

• Erdős--Fishburn proved $g(n)>\tfrac{3}{8}n$.
• Csizmadia--Ismailescu improved this to $g(n)>\tfrac{7}{10}n$.
• An upper bound of the form $g(n)<n-cn^{2/3}$ (for some $c>0$) is known.

The above does not resolve whether $g(n)=n-o(n)$; note that the upper bound $n-cn^{2/3}$ is itself $n-o(n)$.

3) ATTACK PLAN

Since a complete proof/counterexample for $g(n)\ge (1-o(1))n$ is not currently known to me, the plan is:

1. Record a simple explicit construction giving $g(n)\ge \lceil n/2\rceil$ (baseline sanity check).
2. Explain why "generic" point sets typically have $V(X)=1$ (all $R_X(x)=n-1$), so maximizing $V(X)$ requires carefully engineered repeated distances.
3. Outline a plausible "design" paradigm: prescribe, for many points $x$, controlled multiplicities of distances by placing many points on few circles centered at $x$, while avoiding unintended additional equalities.
4. Identify the first serious obstruction: global geometric dependencies between these circle constraints.

4) WORK

A baseline construction: $n$ collinear points.

Let $X=\{(0,0),(1,0),\dots,(n-1,0)\}\subset\mathbb{R}^2$. For the point $x_i=(i,0)$, the set of distances to other points is \[ \{\left\lvert i-j \right\rvert:0\le j\le n-1,\ j\ne i\}=\{1,2,\dots,\max\{i,n-1-i\}\}. \] Hence \[ R_X(x_i)=\max\{i,n-1-i\}. \] As $i$ runs from $0$ to $n-1$, the values $\max\{i,n-1-i\}$ attain exactly the integers \[ \left\lceil\frac{n-1}{2}\right\rceil,\ \left\lceil\frac{n-1}{2}\right\rceil+1,\ \dots,\ n-1, \] so \[ V(X)=n-\left\lceil\frac{n-1}{2}\right\rceil=\left\lceil\frac{n}{2}\right\rceil. \] Therefore \begin{equation}\label{wsref-0-65-71-3a-67-6e-5f-68-61-6c-66} g(n)\ge \left\lceil\frac{n}{2}\right\rceil. \end{equation} This is far from the best known constant ($7/10$), but it is a clean sanity check.

Why generic configurations do not help.

If $X$ is in a sufficiently generic position (e.g., random real coordinates), then for each fixed $x\in X$ the distances $\mathrm{dist}(x,y)$ to distinct $y$ are almost surely all distinct. Hence $R_X(x)=n-1$ for every $x$, so $V(X)=1$. Thus, to make $V(X)$ large, one must enforce repeated distances at many points while keeping the repeated-distance patterns different across points.

A "local degrees of repetition" heuristic.

Write $r(x):=(n-1)-R_X(x)$, the number of "collisions" among the $n-1$ distances from $x$. To make many $R_X(x)$ distinct, we would like many different values of $r(x)$. Large $r(x)$ can be produced efficiently if many points lie on a few circles centered at $x$: if a circle centered at $x$ contains $t$ points, then those $t$ edges from $x$ contribute only one distance value (reducing $R_X(x)$ by $t-1$ compared to the all-distinct case).

First obstruction: choosing such circles independently for many centers is globally constrained, because the same auxiliary points participate in distance relations with all centers, potentially creating unintended collisions that equalize $R_X(\cdot)$ values. This global dependency is exactly what makes pushing $g(n)$ from a constant fraction (like $0.7n$) up to $n-o(n)$ difficult.

5) VERIFICATION / FAST REALITY CHECK

• For $n$ collinear equally spaced points, an explicit computation gives $V(X)=\lceil n/2\rceil$ and the distinct values form an interval. (For instance, $n=10$ gives distinct $R$-values $\{5,6,7,8,9\}$.)
• Random point sets (integer-grid samples) usually give $R_X(x)=n-1$ for every $x$ (so $V(X)=1$), confirming that one must build in symmetry/repetition on purpose.

6) FINAL

UNRESOLVED

• (i) Farthest reached: Verified a simple explicit lower bound $g(n)\ge\lceil n/2\rceil$ via $n$ collinear equally spaced points, and explained why generic configurations give $g(n)=1$.
• (ii) Exact first gap: No construction is provided that achieves $g(n)\ge (1-o(1))n$, nor is there a proof that this is impossible. The key obstacle is controlling repeated-distance patterns for many centers without forcing many points to share the same $R_X(\cdot)$ value.
• (iii) Most promising next moves:
  1. Re-examine the Csizmadia--Ismailescu construction (which achieves $0.7n$) and attempt to "densify" it by adding a small number of carefully placed auxiliary points that break residual symmetries and split remaining multiplicities, aiming for $n-O(n^{2/3})$ distinct values.
  2. Seek an explicit "coding" scheme: represent each point $x$ by a small set of prescribed radii with controlled multiplicities, and realize these simultaneously via a common pool of points arranged on carefully chosen curves/surfaces so that collisions occur only where intended.
  3. Improve upper bounds beyond $n-cn^{2/3}$ in regimes relevant to $n-o(n)$ (or find structural reasons showing $n-o(n)$ is feasible).
• (iv) What would finish it:
  • Either an explicit family $X_n$ with $V(X_n)=n-o(n)$ (ideally $n-O(n^{2/3})$ or better),
  • or a new obstruction proving $V(X)\le (1-\varepsilon)n$ for some fixed $\varepsilon>0$.

7) COMPLETION ESTIMATE

Not complete (open problem in the literature as far as I can verify quickly); this writeup contains a correct baseline bound and a roadmap.