Erdős Problem #652

Erdős Problem 652: the $k$-th smallest pinned distance count

Statement and claim.

For $n$ distinct planar points, let $R(x)$ count the distinct positive distances from $x$ to the other points, and order the points so that $R(x_1)\leq\cdots\leq R(x_n)$. The problem asks whether the best constants $\alpha_k$ permitting $R(x_k)<\alpha_k\sqrt n$ for arbitrarily large configurations (or for every sufficiently large $n$) must tend to infinity. In fact, for $k\geq2$, \[ \alpha_k=\Theta(\sqrt k). \] We reconstruct the pinned crossing-number argument and circle-grid construction in Surya Mathialagan, On Bipartite Distinct Distances in the Plane, https://arxiv.org/abs/1912.01883, Sections 2--3. In the arXiv version the pinned assertion is Theorem 3.6; its Theorem 1.4 only states the weaker unpinned consequence. See https://www.erdosproblems.com/652.

External geometric inputs.

We use two standard theorems, in the forms stated in the cited paper. A topological multigraph with $v$ vertices, $e>5\mu v$ edges, and maximum edge multiplicity $\mu$ has crossing number at least $c e^3/(\mu v^2)$. Also, among $m$ planar points the number of lines containing at least $r\geq2$ of them is at most \[ C\left(\frac{m^2}{r^3}+\frac mr\right). \] The latter is the rich-line consequence of the Szemerédi--Trotter theorem. Absolute constants below may depend on these two absolute theorem constants, not on $m,N$.

The pinned estimate.

Let $P,Q$ be disjoint planar point sets of sizes $m,N$, with $2\leq m\leq N^{1/3}$, and put \[ t=\max_{p\in P}\#\{|p-q|:q\in Q\}. \] We prove $t\geq c\sqrt{mN}$. For bounded $m$, this follows already from two centres: each ordered pair of distances from two distinct centres specifies the intersection of two circles, containing at most two points. Hence $N\leq2t^2$. We may therefore assume $m$ is larger than a sufficiently large absolute constant.

Suppose for contradiction that $t<\varepsilon\sqrt{mN}$, where the positive absolute $\varepsilon$ will be small. Draw all circles about each $p\in P$ passing through $Q$; there are at most $mt$ circles. On every circle containing at least three points of $Q$, join consecutive points by the intervening circular arcs. This gives a multigraph on $Q$ with \[ e\geq mN-2mt \] edges, since circles with one or two points discard at most $2mt$ point--circle incidences. Distinct circles meet at most twice, and arcs from the same circle have disjoint interiors. After small local perturbations if needed, this drawing has $O(m^2t^2)$ crossings.

We bound the number of edges of high multiplicity. The centres of circles supplying arcs between a fixed pair $u,v$ all lie on the perpendicular bisector $\ell$ of that pair. Because circles with at most two points were discarded, any one circle supplies at most one arc with these endpoints. Thus multiplicity at least $r$ forces $\ell$ to contain at least $r$ points of $P$.

A line containing $s$ centres accounts for at most $2st$ such arcs: each of the at most $st$ circles has at most two consecutive arcs whose endpoints are exchanged by reflection in the line. Each such arc crosses one of the two intersection points of the circle with that line, which proves this count. Divide the possible $s$'s into dyadic ranges and apply the rich-line bound. The number of arcs whose bisector contains at least $r$ centres is therefore \[ O\left(\frac{tm^2}{r^2}+tm\log(2m)\right). \tag{1} \] Indeed a dyadic range $s\leq|\ell\cap P|<2s$ contributes $O(t(m^2/s^2+m))$; summing proves $1$.

Fix a sufficiently large absolute integer $K$, and remove every edge belonging to a pair of multiplicity at least $K$. By $1$, the number removed is at most \[ C'\left(\frac{tm^2}{K^2}+tm\log(2m)\right) \leq C'\varepsilon mN \left(\frac1{K^2}+\frac{\log(2m)}m\right), \] where $m^3\leq N$ was used. Choosing $\varepsilon$ sufficiently small leaves $e'\geq mN/2$ edges, of multiplicity at most $K$. For $m>10K$, the crossing lemma applies and gives \[ m^2t^2\gg \operatorname{cr}(G') \gg\frac{(mN)^3}{K N^2} \gg m^3N. \] Thus $t\gg\sqrt{mN}$, contradicting the choice of $\varepsilon$ smaller than this absolute constant. The bounded range $m\leq10K$ was covered by the two-circle argument. This proves the uniform pinned estimate.

The lower bound for $\alpha_k$.

Take $P=\{x_1,\ldots,x_k\}$, the $k$ points with smallest distance counts, and let $Q$ consist of the other $n-k$ points. For fixed $k$ and $n\geq k^3+k$, the estimate applies and gives some $p\in P$ with at least $c\sqrt{k(n-k)}$ distances to $Q$. Every point of $P$ has $R(p)\leq R(x_k)$, so \[ R(x_k)\geq c\sqrt{k(n-k)}. \] As $n\to\infty$, any admissible constant $\alpha_k$ is therefore at least $c\sqrt k$. This proves the requested divergence.

A matching order of magnitude.

For integers $s\geq k$, use centres \[ P=\{(a,0):1\leq a\leq k\} \] and the $ks^2$ points \[ Q=\{(i,\sqrt j):1\leq i\leq s,\ s^2+1-i^2\leq j\leq s^2+ks-i^2,\ j\in\mathbb Z\}. \] All radicands are positive, and these points are distinct. The squared distance from $(a,0)$ to $(i,\sqrt j)$ is $a^2-2ai+i^2+j$. For all $1\leq a\leq k\leq s$, these integers lie between \[ k^2-2ks+s^2+1 \quad\hbox{and}\quad k^2-2k+s^2+ks. \] There are at most $3ks$ possible values. Adding the other centres contributes at most $k-1$ further distances to each centre.

For an arbitrary sufficiently large $n$, choose $s=\lceil\sqrt{(n-k)/k}\rceil$, and delete points of $Q$ until exactly $n-k$ remain. The $k$ centres still have at most $3ks+k=O(\sqrt{kn})$ distances each. Thus $R(x_k)=O(\sqrt{kn})$, with an absolute implied constant, for every sufficiently large $n$. Together with the lower bound this proves $\alpha_k=\Theta(\sqrt k)$.

Scope.

This is a reconstruction of the known resolution using the two explicit geometric theorems, including the required uniform constant and the order-statistic quantifiers.

Completion estimate.

COMPLETION: 100%

Problem #652

1) FORMAL RESTATEMENT

Let $n\ge 2$ and let $X=\{x_1,\dots,x_n\}\subset \mathbb{R}^2$ be a set of $n$ distinct points. For a point $x\in X$ define \[ R_X(x)\;:=\;\left\lvert \{\,\mathrm{dist}(x,y): y\in X\setminus\{x\}\,\} \right\rvert\in\{1,2,\dots,n-1\}, \] the number of distinct distances from $x$ to the other points. Order the points of $X$ so that \[ R_X(x_{(1)})\le R_X(x_{(2)})\le \cdots \le R_X(x_{(n)}), \] where $x_{(k)}$ denotes a point attaining the $k$th smallest value (break ties arbitrarily). Fix $k\in\mathbb{N}$.

Define \[ \alpha_k\;:=\;\inf\left\{\,\alpha>0:\exists N_0\ \forall n\ge N_0\ \exists X\subset\mathbb{R}^2,\ \left\lvert X \right\rvert=n,\ \text{with }R_X(x_{(k)})\le \alpha\sqrt n\right\}. \] (Using $\le$ instead of $<$ is immaterial asymptotically and avoids the issue that a "minimum" need not be attained.)

Question. Is it true that $\alpha_k\to\infty$ as $k\to\infty$?

2) QUICK LITERATURE/CONTEXT CHECK

• A construction of Elekes ("circle grid") shows that for every fixed $k$ one can realize $R_X(x_{(k)})=O_k(\sqrt n)$, i.e. $\alpha_k<\infty$ for every fixed $k$.
• The bipartite distinct-distances paper of Mathialagan (EJC 2021) contains a theorem (their Theorem 14) implying a lower bound of order $\sqrt{k}\,\sqrt n$ for $R_X(x_{(k)})$ once $n$ is sufficiently large compared to $k$. This yields $\alpha_k=\Omega(\sqrt{k})$, and in particular $\alpha_k\to\infty$.

3) ATTACK PLAN

1. Let $X$ be an arbitrary $n$-point set and let $P$ be the subset of the $k$ points with smallest $R_X(\cdot)$, i.e. $P=\{x_{(1)},\dots,x_{(k)}\}$. Let $Q=X\setminus P$.
2. Apply the following bipartite theorem: for $\left\lvert P \right\rvert=m$ and $\left\lvert Q \right\rvert=N$ with $m\le N^{1/3}$, there exists $p\in P$ that determines $\Omega(\sqrt{mN})$ distinct distances to $Q$.
3. Since $p\in P$, we have $R_X(p)\le R_X(x_{(k)})$; but also $R_X(p)\ge R_Q(p)$ (distinct distances from $p$ to $Q$). This will force $R_X(x_{(k)})\ge \Omega(\sqrt{k(n-k)})$.
4. Divide by $\sqrt n$ and choose $n$ large compared to $k^3$ to conclude $\alpha_k\ge c\sqrt{k}$ for an absolute constant $c>0$.

4) WORK

Step 1: A bipartite lower bound (quoted).

We quote the following theorem from Mathialagan [Mathialagan2021, Theorem 14].

Theorem (Mathialagan). Let $P,Q\subset\mathbb{R}^2$ be finite point sets with $\left\lvert P \right\rvert=m$ and $\left\lvert Q \right\rvert=n$ satisfying $2\le m\le n^{1/3}$. Then there exists a point $p\in P$ such that the number of distinct distances from $p$ to points of $Q$ is $\Omega(\sqrt{mn})$.

Here the implied constant in $\Omega(\cdot)$ is absolute. (For completeness: Mathialagan proves this via a crossing-number argument on a multigraph built from concentric circles centered at points of $P$ passing through points of $Q$; see [Mathialagan2021, pp. 6--7].)

Step 2: Apply the bipartite theorem to the $k$ smallest $R$-values.

Let $X\subset\mathbb{R}^2$ be any $n$-point set and write $x_{(1)},\dots,x_{(n)}$ for the ordering by $R_X(\cdot)$. Fix $k\ge 2$ and set \[ P:=\{x_{(1)},\dots,x_{(k)}\},\qquad Q:=X\setminus P. \] Then $\left\lvert P \right\rvert=k$ and $\left\lvert Q \right\rvert=n-k$. Assume that \begin{equation}\label{wsref-0-65-71-3a-6d-6b-5f-63-6f-6e-64-69-74-69-6f-6e} 2\le k\le (n-k)^{1/3}. \end{equation} Under (eq:mk_condition), Mathialagan's theorem yields a point $p\in P$ such that \begin{equation}\label{wsref-0-65-71-3a-6c-6f-77-65-72-5f-62-69-70} \left\lvert \{\mathrm{dist}(p,q): q\in Q\} \right\rvert\;\ge\; c\sqrt{k(n-k)} \end{equation} for some absolute constant $c>0$.

But \[ R_X(p)\;\ge\;\left\lvert \{\mathrm{dist}(p,q): q\in Q\} \right\rvert, \] because the set of distances from $p$ to $Q$ is a subset of the set of distances from $p$ to $X\setminus\{p\}$. Therefore, from (eq:lower_bip) we get \begin{equation}\label{wsref-0-65-71-3a-6c-6f-77-65-72-5f-52-70} R_X(p)\ge c\sqrt{k(n-k)}. \end{equation} Since $p\in P$ and $P$ consists of the $k$ points with the smallest $R_X$-values, \[ R_X(p)\le R_X(x_{(k)}). \] Combining this with (eq:lower_Rp) gives the universal bound \begin{equation}\label{wsref-0-65-71-3a-6c-6f-77-65-72-5f-52-6b} R_X(x_{(k)})\ge c\sqrt{k(n-k)}\qquad\text{whenever }2\le k\le (n-k)^{1/3}. \end{equation}

Step 3: Convert to a lower bound on $\alpha_k$.

Fix $k\ge 2$ and choose $n$ sufficiently large so that $n-k\ge k^3$; equivalently $n\ge k^3+k$. Then $k\le (n-k)^{1/3}$, so (eq:lower_Rk) applies and yields \[ R_X(x_{(k)})\ge c\sqrt{k(n-k)}\ge c\sqrt{k}\,\sqrt{n-k}. \] For example, if $n\ge 2k^3$ then $n-k\ge n/2$ and we get \begin{equation}\label{wsref-0-65-71-3a-6c-6f-77-65-72-5f-72-61-74-69-6f} \frac{R_X(x_{(k)})}{\sqrt n}\ge \frac{c}{\sqrt 2}\,\sqrt{k}\,. \end{equation} Since (eq:lower_ratio) holds for every $n$-point set $X$ once $n\ge 2k^3$, any constant $\alpha$ for which one can have $R_X(x_{(k)})\le \alpha\sqrt n$ for large $n$ must satisfy $\alpha\ge (c/\sqrt2)\sqrt{k}$. Therefore \[ \alpha_k\ge c'\sqrt{k}\qquad\text{for some absolute }c'>0. \] In particular $\alpha_k\to\infty$ as $k\to\infty$.

5) VERIFICATION / FAST REALITY CHECK

• Sanity check for small $k$. For $k=2$ and large $n$, (eq:lower_Rk) gives $R_X(x_{(2)})\ge c\sqrt{2(n-2)}=\Omega(\sqrt n)$, consistent with the known phenomenon that one can force at least constant$\times\sqrt n$ distinct distances for the second-smallest $R$.
• Scaling. If $n\asymp k^3$, then (eq:lower_Rk) gives $R_X(x_{(k)})=\Omega(k^2)$ while $\sqrt n\asymp k^{3/2}$, so $R_X(x_{(k)})/\sqrt n=\Omega(\sqrt k)$, matching the claimed growth.
• Compatibility with Elekes. Elekes' construction yields $R_X(x_{(k)})\le C_k\sqrt n$ with $C_k$ depending on $k$; our lower bound shows $C_k$ must grow at least on the order of $\sqrt k$.

6) FINAL

FULL SOLUTION
PROVED

Using Mathialagan's bipartite theorem (Theorem 14 in [Mathialagan2021]), one obtains the universal bound $R_X(x_{(k)})\ge c\sqrt{k(n-k)}$ for all $n$-point sets $X$ whenever $k\le (n-k)^{1/3}$. Taking $n\ge 2k^3$ gives $R_X(x_{(k)})/\sqrt n\ge c'\sqrt{k}$. Consequently $\alpha_k\ge c'\sqrt{k}$ for an absolute $c'>0$, and hence $\alpha_k\to\infty$ as $k\to\infty$.

7) COMPLETION ESTIMATE

100%.