gpt pro 5.2 attempt on Math-5796

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.