# Equidistant Points in the Plane problem by Paul Erdos

This problem was actually posed by Erdos in Geombinatorics (Oct. 1994) and goes as follows:

Let $f(n)$ be the largest integer for which there are $n$ distinct points $x_1,x_2,\dots,x_n$ in the plane so that for every $i, 1\le i \le n$ there are at least $f(n)$ points $x_j, 1\le j \le n$ equidistant from $x_i.$

Erdos mentions that $f(n) > n^{\frac{c}{\log\log n}}$ is demonstrated by lattice points, although he did not mention the proof there.

He also stated that the inequality $f(n) < c\sqrt{n}$ is trivial. But I am not sure how to prove this though.

Any help on these two problems would be greatly appreciated.

(Also, Erdos conjectures that $f(n) < n^\epsilon$ for every $\epsilon > 0$ for which he gives \$500 and \$100 for a counterexample.)

-
Related and possibly dupe: math.stackexchange.com/questions/52745/… –  Aryabhata Apr 7 '12 at 16:48
@Aryabhata I don't think these problems are related (unless I am missing something). This problem is about the maximum number of points that can be equidistant from each point. Whereas that link is about another problem, dealing with the maximum number of times a distance can occur among $n$ points. –  Souparna P Apr 7 '12 at 17:02
For definiteness, $U(3) = 3$ (from the post in the link) where $f(3)=2,$ etc. –  Souparna P Apr 7 '12 at 17:08
If I remember correctly this and the other problem were dealt with in the same paper by Erdos and were related. If you notice, I didn't try to cast a close vote :-). Just added that here to link these two questions (see the Linked section on the right). –  Aryabhata Apr 7 '12 at 18:43
@Aryabhata I think you may be thinking of some other problem (or maybe I am missing something in which case if you could please correct me). But I got this from a paper written by Erdos and published in 1994, where he asked this, so I don't think the 1946 paper has the answer to this. But in any case, surely, $f(n)$ is bounded above by $U(n)$ (as used in the previous post) but that only gives us that $f(n) < c_1n^{4/3}$ which is weaker than the claimed $f(n) < cn^{1/2}.$ –  Souparna P Apr 7 '12 at 20:31

I think an argument for $n^{c/\log\log n}$ could proceed along the following lines – I won't make any effort to fill in details to make it rigorous, but I think that should be possible.

The number of ways of representing $a_m:=\prod_{k=1}^mq_k^2$, where $q_k$ is the $k$-th prime with residue $1\bmod4$, as an ordered sum of squares is $3^m$ (see MathWorld). Since the residues of the primes are equidistributed, about half of them have residue $1\bmod 4$. Since the product of the first $m$ primes, the $m$-th primorial, goes as $\mathrm e^{m\log m}$, the product of the first $m$ primes with residue $1\bmod 4$ should go as $\mathrm e^{(m\log m)/2}$. Now if we form a square integer grid with side length $2\mathrm e^{(m\log m)/2}$, it has $n=4\mathrm e^{m\log m}$ points, each of which is equidistant from at least $3^m$ other points. Solving for $m$ yields

$$m=\frac{\log n-\log 4}{\log m}=\frac{\log n-\log 4}{\log(\log n-\log 4)-\log\log m}\sim\frac{\log n}{\log\log n}\;,$$

and thus $f(n)\ge3^m\sim n^{3/\log\log n}$.

To prove the upper bound $c\sqrt n$, consider $f(n)$ points equidistant from a point. Each such point $p_i$ must in turn be equidistant from a set $S_i$ of at least $f(n)$ points. The $S_i$ may have points in common, but any pair of $S_i$ can have at most $2$ points in common, since all points in a given $S_i$ lie on a circle. Now consider the set $S=\bigcup S_i$, and imagine a table with a row for each set $S_i$ and a column for each point in $S$. Make a check in a table entry if the corresponding set contains the corresponding point. The table must contain at least $r:=f(n)^2$ checks. Each pair of rows may have at most two checks in common. Thus the number $p$ of pairs of checks in the same column can be at most twice the number of pairs of rows, that is, $p\le f(n)(f(n)-1)\le f(n)^2$. A column with $k$ checks contributes $k$ checks to $r$ and $k(k-1)/2$ pairs to $p$. Thus

$$\sum_jk_j\ge f(n)^2\quad\text{and}\quad\sum_j\frac{k_j(k_j-1)}2\le f(n)^2\;,$$

where $k_j$ is the number of checks in column $j$. Let there be $n_\lt$ columns with at most $3$ checks. Then

$$f(n)^2\le\sum_jk_j\le3n_\lt+\sigma\quad\text{with}\quad\sigma:=\sum_{k_j\ge4}k_j$$

and

$$f(n)^2\ge\sum_j\frac{k_j(k_j-1)}2\ge\sum_{k_j\ge4}\frac{k_j(k_j-1)}2\ge\frac32\sum_{k_j\ge4}k_j=\frac32\sigma\;.$$

Together,

$$\frac32\sigma\le3n_\lt+\sigma\;,\\ \sigma\le6n_\lt$$

and thus

$$f(n)^2\le9n_\lt\le9n\;,\\ f(n)\le3\sqrt n\;.$$

-
Thank you for your answer. I haven't read the first part yet, but I will do so later. For the second part, I don't understand how you get $\sum_j \dfrac{(k_j)(k_j-1)}{2} \le f(n)^2.$ (+) Maybe I am misunderstanding your definition of $p.$ But based on your current definition (in which $p$ is the number of pairs of checks in one column) I don't see how in the sum (+), the summands cumulatively are less than or equal to $p \le f(n)^2.$ Thank you for your help. –  Souparna P Apr 8 '12 at 0:37
@limac: I'm sorry, I somehow overlooked this comment at the time. I'm not sure whether you changed "the same" to "one" by accident in "the number of pairs of checks in the same column", or whether this indicates a misunderstanding. Perhaps you could point out what part of the text directly above that inequality ("Each pair of rows ... and $k(k-1)/2$ pairs to $p$.") you find unclear. To my mind, that text is the justification for the inequality you're asking about. –  joriki Apr 27 '12 at 8:59
Sorry for the delay in reply, I had a fever. But this is what I don't understand. You let $p$ be the number of pairs of checks in the same column, so we are talking about one particular column here, say column C. Is that right so far? Next, you say that a column with $k$ checks contributes $k(k-1)/2$ pairs to p. And then you take a sum over all the columns, which all sum to be less than or equal to $p.$ But isn't $p$ the number of pairs of checks in the same column. Then how is the sum over all the columns still sum to less than or equal to $p.$ I hope I explained my confusion clearly. Thanks! –  Souparna P May 3 '12 at 22:37