/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
Let $f(n)$ be such that, given any $x_1,\ldots,x_n\in \mathbb{R}^2$ with no four points on a
circle, there exists some $x_i$ with at least $f(n)$ many distinct distances to the other $x_j$.
Is it true that $f(n) > (1-o(1))n$?
Erdős asks this in [Er97e]. The answer is no: Aletheia [Fe26] constructed, for every $m \geq 10$,
a set of $n = 4m$ points with no four on a circle such that every point has fewer than
$\frac{3}{4}n$ distinct distances to the other points. This gives infinitely many $n$, which is
enough to refute the statement with $\varepsilon = 1/8$. See Erdos654.erdos_654.variants.feng.
In fact every point $x$ has at least $\frac{n-1}{3}$ distinct distances to the other points: a
circle centred at $x$ contains at most three other points, since four would lie on a common
circle.
Aletheia [Fe26] showed that for every $m \geq 10$ there is a set of $n = 4m$ points in
$\mathbb{R}^2$, no four on a circle, such that every point has fewer than $\frac{3}{4}n = 3m$
distinct distances to the other points.
The construction places $2m$ points on each of two perpendicular lines, so it is not in general
position. Each point has at most $3m - 1$ distinct distances to the other points.
Erdős [Er87b] and Erdős and Pach [ErPa90] ask the question of erdos_654.parts.ii under the
additional assumption that no three points are on a line. Let $x_1,\ldots,x_n\in \mathbb{R}^2$ with
no three points on a line and no four points on a circle. Is there some $x_i$ with at least
$(\frac{1}{3}+c)n$ distinct distances to the other $x_j$, for some constant $c>0$ and all large
$n$?
Let $x_1,\ldots,x_n\in \mathbb{R}^2$ with no three points on a line and no four points on a
circle. Is there some $x_i$ with at least $(1-o(1))n$ distinct distances to the other $x_j$?
This is the general-position analogue of Erdos654.erdos_654.parts.i. The remark on
erdosproblems.com notes that the construction of [Fe26], which has all points on two lines, does
not settle the version in general position.
Erdős and Pach [ErPa90] suggest that the bound $(1-o(1))n$ holds under the assumption that every
circle centred at a point $x_i$ contains at most $2$ other points $x_j$. We state this for points
in general position (no three on a line and no four on a circle [Er87b, p. 167]), the setting in
which [Er87b] and [ErPa90] ask the weaker question. Without the assumption of no three points on a
line the statement is false: the sets of [Fe26] satisfy the circle condition.