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.)
 A: 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\;.
$$
