Logo
FAQ Tags Prizes Definitions Links
All Problems Random Solved Random Open
2 solved out of 18 shown
$500
Does every set of $n$ distinct points in $\mathbb{R}^2$ determine $\gg n/\sqrt{\log n}$ many distinct distances?
A $\sqrt{n}\times\sqrt{n}$ integer grid shows that this would be the best possibe. Nearly solved by Guth and Katz [GuKa15] who proved that there are always $\gg n/\log n$ many distinct distances. It may be true that there is a single point which determines $\gg n/\sqrt{\log n}$ distinct distances, or even that there are $\gg n$ many such points, or even that this is true averaged over all points.
$500
Does every set of $n$ distinct points in $\mathbb{R}^2$ contain at most $n^{1+O(1/\log\log n)}$ many pairs which are distance 1 apart?
This would be the best possible, as is shown by a set of lattice points. It is easy to show that there are $O(n^{3/2})$ many such pairs. The best known upper bound is $O(n^{4/3})$, due to Spencer, Szemerédi, and Trotter [SpSzTr84]. In [Er83c] Erdős offers \$250 for an upper bound of the form $n^{1+o(1)}$.
Suppose $A\subset \mathbb{R}^2$ has $\lvert A\rvert=n$ and minimises the number of distinct distances between points in $A$. Prove that for large $n$ there are at least two (and probably many) such $A$ which are non-similar.
For $n=5$ the regular pentagon is the unique such set (Erdős mysteriously remarks this was proved by 'a colleague').
$500
Let $\epsilon>0$. Given any set of $n$ distinct points in $\mathbb{R}^2$ prove that each point is equidistant from $O_\epsilon(n^\epsilon)$ many other points.
Erdős only offers \$100 for a counterexample.
$500
Let $x_1,\ldots,x_n\in\mathbb{R}^2$ determine the set of distances $\{u_1,\ldots,u_t\}$. Suppose $u_i$ appears as the distance between $f(u_i)$ many pairs of points. Then for all $\epsilon>0$ \[\sum_i f(u_i)^2 \ll_\epsilon n^{3+\epsilon}.\]
The case when the points determine a convex polygon was been solved by Fishburn [Al63]. Note it is trivial that $\sum f(u_i)=\binom{n}{2}$. Solved by Guth and Katz [GuKa15] who proved the upper bound \[ \sum_i f(u_i)^2 \ll n^3\log n.\]
If $n$ points in $\mathbb{R}^2$ form a convex polygon then there are $O(n)$ many pairs which are distance $1$ apart.
Conjectured by Erdős and Moser. Füredi has proved an upper bound of $O(n\log n)$. Edelsbrunner and Hajnal have constructed $n$ such points with $2n-7$ pairs distance $1$ apart.
Does every polygon have a vertex with no other $4$ vertices equidistant from it?
Open even for convex polygons.

Danzer has found a convex polygon on 9 points such that every vertex has three vertices equidistant from it (but this distance depends on the vertex), and Fishburn and Reeds have found a convex polygon on 20 points such that every vertex has three vertices equidistant from it (and this distance is the same for all vertices).

If this fails for $4$, perhaps there is some constant for which it holds?

Additional thanks to: Boris Alexeev and Dustin Mixon
Let $h(n)$ be such that any $n$ points in $\mathbb{R}^2$, with no three on a line and no four on a circle, determine at least $h(n)$ distinct distances. Does $h(n)/n\to \infty$?
Erdős could not even prove $h(n)\geq n$. Pach has shown $h(n)<n^{\log_23}$.
$100
Let $A\subseteq\mathbb{R}^2$ be a set of $n$ points with minimum distance equal to 1, chosen to minimise the diameter of $A$. If $n$ is sufficiently large then must there be three points in $A$ which form an equilateral triangle of size 1?
In fact Erdős believes such a set must have very large intersection with the triangular lattice. This is false for $n=4$, for example a square. The behaviour of such sets for small $n$ is explored by Bezdek and Fodor [BeFo99].
Additional thanks to: Boris Alexeev and Dustin Mixon
Let $A\subseteq\mathbb{R}^2$ be a set of $n$ points with distance set $D=\{\lvert x-y\rvert : x\neq y \in A\}$. Suppose that if $d_1\neq d_2\in D$ then $\lvert d_1-d_2\rvert \geq 1$. Is there some constant $c>0$ such that the diameter of $A$ must be at least $cn$?
Perhaps the diameter is $\geq n-1$ for all large $n$ (Piepmeyer has an example of $9$ such points with diameter $<5$).
Additional thanks to: Shengtong Zhang
Let $A$ be a set of $n$ points in $\mathbb{R}^2$ such that all pairwise distances are at least $1$ and if two distinct distances differ then they differ by at least $1$. Is the diameter of $A$ $\gg n$?
Perhaps the diameter is even $\geq n-1$ for sufficiently large $n$. Kanold proved the diameter is $\geq n^{3/4}$. The bounds on the distinct distance problem [89] proved by Guth and Katz [GuKa15] imply a lower bound of $\gg n/\log n$.
Additional thanks to: Boris Alexeev and Dustin Mixon
Let $A\subset \mathbb{R}^2$ be a set of $n$ points. Must there be two distances which occur at least once but between at most $n$ pairs of points?
Asked by Erdős and Pach. Pannowitz proved that this is true for the largest distance between points of $A$, but it is unknown whether a second such distance must occur.
$250
Let $A\subset \mathbb{R}^2$ be a set of $n$ points such that any subset of size $4$ determines at least $5$ distinct distances. Must $A$ determine $\gg n^2$ many distances?
Erdős also makes the even stronger conjecture that $A$ must contain $\gg n$ many points such that all pairwise distances are distinct.
Is there a dense subset of $\mathbb{R}^2$ such that all pairwise distances are rational?
Conjectured by Ulam. Erdős believed there cannot be such a set. This problem is discussed in a blogpost by Terence Tao, in which he shows that there cannot be such a set, assuming the Bombieri-Lang conjecture.
Let $n\geq 4$. Are there $n$ points in $\mathbb{R}^2$, no three on a line and no four on a circle, such that all pairwise distances are integers?
Harborth constructed such a set when $n=5$.
Let $S\subset \mathbb{R}^2$ be such that no two points in $S$ are distance $1$ apart. Must the complement of $S$ contain four points which form a unit square?
The answer is yes, proved by Juhász [Ju79], who proved more generally that the complement of $S$ must contain a congruent copy of any set of four points. This is not true for arbitrarily large sets of points, but perhaps is still true for any set of five points.
Additional thanks to: Bhavik Mehta
For which $n$ are there $n$ points in $\mathbb{R}^2$, no three on a line and no four on a circle, which determine $n-1$ distinct distances and so that (in some ordering of the distances) the $i$th distance occurs $i$ times?
An example with $n=4$ is an isosceles triangle with the point in the centre. Erdős originally believed this was impossible for $n\geq 5$, but Pomerance constructed a set with $n=5$ (see [Er83c] for a description), and 'a Hungarian high school student' gave an unspecified construction for $n=6$. Is this possible for $n=7$?
Let $d\geq 2$ and $n\geq 2$. Let $f_d(n)$ be maximal such that, for any $A\subseteq \mathbb{R}^d$ of size $n$, with diameter $1$, the distance 1 occurs between $f_d(n)$ many pairs of points in $A$. Estimate $f_d(n)$.
Hopf and Pannwitz [HoPa34] proved $f_2(n)=n$. Heppes [He56] and Grünbaum-Strasziewicz independently showed that $f_3(n)=2n-2$.