3
$\begingroup$

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.)

  • 0
    You might be right...2012-04-07

1 Answers 1

1

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

  • 0
    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!2012-05-03