A $\sqrt{n}\times\sqrt{n}$ integer grid shows that this would be the best possible. Nearly solved by Guth and Katz [GuKa15] who proved that there are always $\gg n/\log n$ many distinct distances.

A stronger form (see [604]) may be true: is there a single point which determines $\gg n/\sqrt{\log n}$ distinct distances, or even $\gg n$ many such points, or even that this is true averaged over all points - for example, if $d(x)$ counts the number of distinct distances from $x$ then in [Er75f] Erdős conjectured\[\sum_{x\in A}d(x) \gg \frac{n^2}{\sqrt{\log n}},\]where $A\subset \mathbb{R}^2$ is any set of $n$ points.

See also [661], and [1083] for the generalisation to higher dimensions.

View the LaTeX source

This page was last edited 15 October 2025.

The unit distance problem. In [Er94b] Erdős dates this conjecture to 1946. In [Er82e] he offers \$300 for the upper bound $n^{1+o(1)}$.

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 [SST84]. In [Er83c] and [Er85] Erdős offers \$250 for an upper bound of the form $n^{1+o(1)}$.

Part of the difficulty of this problem is explained by a result of Valtr (see [Sz16]), who constructed a metric on $\mathbb{R}^2$ and a set of $n$ points with $\gg n^{4/3}$ unit distance pairs (with respect to this metric). The methods of the upper bound proof of Spencer, Szemerédi, and Trotter [SST84] generalise to include this metric. Therefore to prove an upper bound better than $n^{4/3}$ some special feature of the Euclidean metric must be exploited.

See a survey by Szemerédi [Sz16] for further background and related results.

See also [92], [96], [605], and [956]. The higher dimensional generalisation is [1085].

View the LaTeX source

This page was last edited 15 October 2025.

For $n=3$ the equilateral triangle is the only such set. For $n=4$ the square or two equilateral triangles sharing an edge give two non-similar examples.

For $n=5$ the regular pentagon is the unique such set (which has two distinct distances). Erdős mysteriously remarks in [Er90] this was proved by 'a colleague'. (In [Er87b] this is described as 'a colleague from Zagreb (unfortunately I do not have his letter)'.) A published proof of this fact is provided by Kovács [Ko24c].

In [Er87b] Erdős says that there are at least two non-similar examples for $6\leq n\leq 9$.

The minimal possible number of distinct distances is the subject of [89].

View the LaTeX source

This page was last edited 01 December 2025.

This is a stronger form of the unit distance conjecture (see [90]).

The set of lattice points imply $f(n) > n^{c/\log\log n}$ for some constant $c>0$. Erdős offered \$500 for a proof that $f(n) \leq n^{o(1)}$ but only \$100 for a counterexample.

It is trivial that $f(n) \ll n^{1/2}$. A result of Pach and Sharir implies $f(n) \ll n^{2/5}$. Hunter has observed that the circle-point incidence bound of Janzer, Janzer, Methuku, and Tardos [JJMT24] implies\[f(n) \ll n^{4/11}.\]Fishburn (personal communication to Erdős) proved that $6$ is the smallest $n$ such that $f(n)=3$ and $8$ is the smallest $n$ such that $f(n)=4$, and suggested that the lattice points may not be best example.

See also [754].

View the LaTeX source

This page was last edited 15 October 2025.

Solved by Altman [Al63]. The stronger variant that says there is one point which determines at least $\lfloor \frac{n}{2}\rfloor$ distinct distances (see [982]) is still open. Fishburn in fact conjectures that if $R(x)$ counts the number of distinct distances from $x$ then\[\sum_{x\in A}R(x) \geq \binom{n}{2}.\]Szemerédi conjectured a stronger form in which the convexity is replaced by the assumption that there are no three points on a line - see [1082].

See also [660].

View the LaTeX source

This page was last edited 19 October 2025.

In [Er97c] Erdős claims that Fishburn solved this, but gives no reference. Note it is trivial that $\sum f(u_i)=\binom{n}{2}$.

Lefmann and Theile [LeTh95] prove a stronger version of this question, that\[\sum_i f(u_i)^2 \ll n^3\]under the weaker assumption that no three points are on a line. A sketch of this proof is given in the comments by serge.

Erdős and Fishburn also make the stronger conjecture that $\sum f(u_i)^2$ is maximal for the regular $n$-gon (for large enough $n$).

In [Er92e] Erdős offered £25 for a resolution of this problem. (This has been converted to $44 using approximate 1992 exchange rates.)

See also [95].

View the LaTeX source

This page was last edited 05 December 2025.

The case when the points determine a convex polygon was 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.\]See also [94].

View the LaTeX source

Conjectured by Erdős and Moser. In [Er92e] Erdős credits the conjecture that the true upper bound is $2n$ to himself and Fishburn. Füredi [Fu90] proved an upper bound of $O(n\log n)$. A short proof of this bound was given by Brass and Pach [BrPa01]. The best known upper bound is\[\leq n\log_2n+4n,\]due to Aggarwal [Ag15].

Edelsbrunner and Hajnal [EdHa91] have constructed $n$ such points with $2n-7$ pairs distance $1$ apart. (This disproved an early stronger conjecture of Erdős and Moser, that the true answer was $\frac{5}{3}n+O(1)$.)

A positive answer would follow from [97]. See also [90].

In [Er92e] Erdős makes the stronger conjecture that, if $g(x)$ counts the largest number of points equidistant from $x$ in $A$, then\[\sum_{x\in A}g(x)< 4n.\]He notes that the example of Edelsbrunner and Hajnal shows that $\sum_{x\in A}g(x)>4n-O(1)$ is possible.

View the LaTeX source

Erdős originally conjectured this (in [Er46b]) with no $3$ vertices equidistant, but Danzer found a convex polygon on 9 points such that every vertex has three vertices equidistant from it (but this distance depends on the vertex). Danzer's construction is explained in [Er87b]. Fishburn and Reeds [FiRe92] 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? In [Er75f] Erdős claimed that Danzer proved that this false for every constant - in fact, for any $k$ there is a convex polygon such that every vertex has $k$ vertices equidistant from it. Since this claim was not repeated in later papers, presumably Erdős was mistaken here.

Erdős suggested this as an approach to solve [96]. Indeed, if this problem holds for $k+1$ vertices then, by induction, this implies an upper bound of $kn$ for [96].

The answer is no if we omit the requirement that the polygon is convex (I thank Boris Alexeev and Dustin Mixon for pointing this out), since for any $d$ there are graphs with minimum degree $d$ which can be embedded in the plane such that each edge has length one (for example one can take the $d$-dimensional hypercube graph on $2^d$ vertices). One can then connect the vertices in a cyclic order so that there are no self-intersections and no three consecutive vertices on a line, thus forming a (non-convex) polygon.

View the LaTeX source

This page was last edited 27 October 2025.

Erdős could not even prove $h(n)\geq n$. Pach has shown $h(n)<n^{\log_23}$. Erdős, Füredi, and Pach [EFPR93] have improved this to\[h(n) < n\exp(c\sqrt{\log n})\]for some constant $c>0$.

View the LaTeX source

This page was last edited 15 October 2025.

Thue proved that the minimal such diameter is achieved (asymptotically) by the points in a triangular lattice intersected with a circle. In general Erdős believed such a set must have very large intersection with the triangular lattice (perhaps as many as $(1-o(1))n$).

Erdős [Er94b] wrote 'I could not prove it but felt that it should not be hard. To my great surprise both B. H. Sendov and M. Simonovits doubted the truth of this conjecture.' In [Er94b] he offers \$100 for a counterexample but only \$50 for a proof.

The stated problem is false for $n=4$, for example taking the points to be vertices of a square. The behaviour of such sets for small $n$ is explored by Bezdek and Fodor [BeFo99].

See also [103].

View the LaTeX source

Perhaps the diameter is even $\geq n-1$ for sufficiently large $n$. Piepmeyer has an example of $9$ such points with diameter $<5$. 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$.

View the LaTeX source

It is not even known whether $h(n)\geq 2$ for all large $n$.

See also [99].

View the LaTeX source

Asked by Erdős and Pach. Hopf and Pannowitz [HoPa34] proved that the largest distance between points of $A$ can occur at most $n$ times, but it is unknown whether a second such distance must occur.

It may be true that there are at least $n^{1-o(1)}$ many such distances. In [Er97e] Erdős offers \$100 for 'any nontrivial result'.

Erdős [Er84c] believed that for $n\geq 5$ there must always exist at least two such distances. This is false for $n=4$, as witnessed by two equilateral triangles of the same side-length glued together. Erdős and Fishburn [ErFi95] proved this is true for $n=5$ and $n=6$.

Clemen, Dumitrescu, and Liu [CDL25] have proved that there always at least two such distances if $A$ is in convex position (that is, no point lies inside the convex hull of the others). They also prove it is true if the set $A$ is 'not too convex', in a specific technical sense.

See also [223], [756], and [957].

View the LaTeX source

A problem of Erdős and Gyárfás. Erdős could not even prove that the number of distances is at least $f(n)n$ where $f(n)\to \infty$. Erdős [Er97b] also makes the even stronger conjecture that $A$ must contain $\gg n$ many points such that all pairwise distances are distinct.

Answered in the negative by Tao [Ta24c], who proved that for any large $n$ there exists a set of $n$ points in $\mathbb{R}^2$ such that any four points determine at least five distinct distances, yet there are $\ll n^2/\sqrt{\log n}$ distinct distances in total. Tao discusses his solution in a blog post.

More generally, one can ask how many distances $A$ must determine if every set of $p$ points determines at least $q$ distances.

See also [136] and [657].

View the LaTeX source

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. The same conclusion was independently obtained by Shaffaf [Sh18].

Indeed, Shaffaf and Tao actually proved that such a rational distance set must be contained in a finite union of real algebraic curves. Solymosi and de Zeeuw [SdZ10] then proved (unconditionally) that a rational distance set contained in a real algebraic curve must be finite, unless the curve contains a line or a circle.

Ascher, Braune, and Turchet [ABT20] observed that, combined, these facts imply that a rational distance set in general position must be finite (conditional on the Bombieri-Lang conjecture).

In [Er87b] Erdős mentions that Besicovitch conjectured that the limit points of a rational distance set cannot contain arbitrarily large convex sets.

View the LaTeX source

This page was last edited 16 October 2025.

Anning and Erdős [AnEr45] proved there cannot exist an infinite such set. Harborth constructed such a set when $n=5$. The best construction to date, due to Kreisel and Kurz [KK08], has $n=7$.

Ascher, Braune, and Turchet [ABT20] have shown that there is a uniform upper bound on the size of such a set, conditional on the Bombieri-Lang conjecture. Greenfeld, Iliopoulou, and Peluse [GIP24] have shown (unconditionally) that any such set must be very sparse, in that if $S\subseteq [-N,N]^2$ has no three on a line and no four on a circle, and all pairwise distances integers, then\[\lvert S\rvert \ll (\log N)^{O(1)}.\]See also [130].

View the LaTeX source

This page was last edited 16 October 2025.

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.

View the LaTeX source

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 Palásti has proved such sets exist for all $n\leq 8$.

Erdős believed this is impossible for all sufficiently large $n$. This would follow from $h(n)\geq n$ for sufficiently large $n$, where $h(n)$ is as in [98].

View the LaTeX source

This page was last edited 02 October 2025.

In [Er46b] Erdős says this was a conjecture of Vázsonyi.

• Hopf and Pannwitz [HoPa34] proved $f_2(n)=n$ (with an elegant simple proof described by Erdős in [Er46b]).


• Grünbaum [Gr56], Heppes [He56], and Strasziewicz [St57] independently showed that $f_3(n)=2n-2$.


• Erdős [Er60b] proved that, for $d\geq 4$, $f_d(n)=(\frac{p-1}{2p}+o(1))n^2$ where $p=\lfloor d/2\rfloor$.


• Swanepoel [Sw09] gave, for all $d\geq 4$, an exact description of $f_d(n)$ for all $n$ sufficiently large depending on $d$, and also gave the extremal configurations.

See also [132], and [1084] for the analogous problem with minimal distance $1$.

View the LaTeX source

This page was last edited 28 October 2025.

A question of Moser [Mo66]. A lower bound of $m_1\geq \pi/8\sqrt{3}\approx 0.2267$ is given by taking the union of open circular discs of radius $1/2$ at a regular hexagonal lattice suitably spaced apart. Croft [Cr67] gives a small improvement of $m_1\geq 0.22936$.

The trivial upper bound is $m_1\leq 1/2$, since for any unit vector $u$ the sets $A$ and $A+u$ must be disjoint. Erdős' question was solved by Ambrus, Csiszárik, Matolcsi, Varga, and Zsámboki [ACMVZ23] who proved that $m_1\leq 0.247$.

View the LaTeX source

This page was last edited 02 October 2025.

Asked to Erdős by Coxeter. Erdős thought he could show that $\lvert A\rvert \leq n^{O(1)}$, but later discovered a mistake in his proof, and his proof only gave $\leq \exp(n^{1-o(1)})$.

Bannai, Bannai, and Stanton [BBS83] have proved that\[\lvert A\rvert \leq \binom{n+2}{2}.\]A simple proof of this upper bound was given by Petrov and Pohoata [PePo21].

Shengtong Zhang has observed that a simple lower bound of $\binom{n}{2}$ is given by considering all points with exactly two coordinates equal to $1$ and all others equal to $0$. In fact, since these points are on a hyperplane, a suitable projection gives an improved lower bound of $\binom{n+1}{2}$ (see the construction of Alweiss given in [503]).

View the LaTeX source

When $d=2$ the answer is $6$ (due to Kelly [ErKe47] - an alternative proof is given by Kovács [Ko24c]). When $d=3$ the answer is $8$ (due to Croft [Cr62]). The best upper bound known in general is due to Blokhuis [Bl84] who showed that\[\lvert A\rvert \leq \binom{d+2}{2}.\]Alweiss has observed a lower bound of $\binom{d+1}{2}$ follows from considering the subset of $\mathbb{R}^{d+1}$ formed of all vectors $e_i+e_j$ where $e_i,e_j$ are distinct coordinate vectors. This set can be viewed as a subset of some $\mathbb{R}^d$, and is easily checked to have the required property.

Weisenberg observed in the comments that an additional point can be added to Alweiss' construction, giving a lower bound of $\binom{d+1}{2}+1$.

The fact that the truth for $d=3$ is $8$ suggests that neither of these bounds is the truth.

See also [1088] for a generalisation.

View the LaTeX source

This page was last edited 28 October 2025.

The pinned distance problem, a stronger form of [89]. The example of an integer grid show that $n/\sqrt{\log n}$ would be best possible.

It may be true that there are $\gg n$ many such points, or that this is true on average - for example, if $d(x)$ counts the number of distinct distances from $x$ then in [Er75f] Erdős conjectured\[\sum_{x\in A}d(x) \gg \frac{n^2}{\sqrt{\log n}},\]where $A\subset \mathbb{R}^2$ is any set of $n$ points.

In [Er97e] Erdős offers \$500 for a solution to this problem, but it is unclear whether he intended this for proving the existence of a single such point or for $\gg n$ many such points.

In [Er97e] Erdős wrote that he initially 'overconjectured' and thought that the answer to this problem is the same as for the number of distinct distances between all pairs (see [89]), but this was disproved by Harborth. It could be true that the answers are the same up to an additive factor of $n^{o(1)}$.

The best known bound is\[\gg n^{c-o(1)},\]due to Katz and Tardos [KaTa04], where\[c=\frac{48-14e}{55-16e}=0.864137\cdots.\]

View the LaTeX source

This page was last edited 15 October 2025.

See also [90]. This was solved by Erdős, Hickerson, and Pach [EHP89]. For $D>1$ and $n\geq 2$ let $u_D(n)$ be such that there is a set of $n$ points on the sphere in $\mathbb{R}^3$ with radius $D$ such that there are $u_D(n)$ many pairs which are distance $1$ apart (so that this problem asked for $u_D(n)\geq f(n)n$ for some $D$).

Erdős, Hickerson, and Pach [EHP89] proved that $u_{\sqrt{2}}(n)\asymp n^{4/3}$ and $u_D(n)\gg n\log^*n$ for all $D>1$ and $n\geq 2$ (where $\log^*$ is the iterated logarithm function).

This lower bound was improved by Swanepoel and Valtr [SwVa04] to $u_D(n) \gg n\sqrt{\log n}$. The best upper bound for general $D$ is $u_D(n)\ll n^{4/3}$.

View the LaTeX source

It is trivial that $R(x_1)=1$ is possible, and that $R(x_2) \ll n^{1/2}$ is also possible, but we always have\[R(x_1)R(x_2)\gg n.\]Erdős originally conjectured that $R(x_3)/n^{1/2}\to \infty$ as $n\to \infty$, but Elekes proved that for every $k$ and $n$ sufficiently large there exists some set of $n$ points with $R(x_k)\ll_k n^{1/2}$.

View the LaTeX source

Erdős and Fishburn proved $g(n)>\frac{3}{8}n$ and Csizmadia proved $g(n)>\frac{7}{10}n$. Both groups proved $g(n) < n-cn^{2/3}$ for some constant $c>0$.

View the LaTeX source

It is clear that every point has at least $\frac{n-1}{3}$ distinct distances to other points in the set.

In [Er87b] and [ErPa90] Erdős and Pach ask this under the additional assumption that there are no three points on a line (so that the points are in general position), although they only ask the weaker question whether there is a lower bound of the shape $(\tfrac{1}{3}+c)n$ for some constant $c>0$.

They suggest the lower bound $(1-o(1))n$ is true under the assumption that any circle around a point $x_i$ contains at most $2$ other $x_j$.

View the LaTeX source

This page was last edited 02 October 2025.

A problem of Erdős and Pach. It is easy to see that this assumption implies that there are at least $\frac{n-1}{2}$ distinct distances determined by every point.

Zach Hunter has observed that taking $n$ points equally spaced on a circle disproves this conjecture. In the spirit of related conjectures of Erdős and others, presumably some kind of assumption that the points are in general position (e.g. no three on a line and no four on a circle) was intended.

View the LaTeX source

In [Er73] Erdős attributes this problem (more generally in $\mathbb{R}^k$) to himself and Davies. In [Er97e] he does not mention Davis, but says this problem was investigated by himself, Füredi, Ruzsa, and Pach.

In [Er73] Erdős says it is not even known in $\mathbb{R}$ whether $f(n)\to \infty$. Sarosh Adenwalla has observed that this is equivalent to minimising the number of distinct differences in a set $A\subset \mathbb{R}$ of size $n$ without three-term arithmetic progressions. Dumitrescu [Du08] proved that, in these terms,\[(\log n)^c \leq f(n) \leq 2^{O(\sqrt{\log n})}\]for some constant $c>0$.

Hunter observed in the comments that a result of Ruzsa coupled with standard tools of additive combinatorics (with details given by Alfaiz and Tang) allow recent progress on the size of subsets without three-term arithmetic progression (see [BlSi23] which improves slightly on the bounds due to Kelley and Meka [KeMe23]) yield\[2^{c(\log n)^{1/9}}\leq f(n)\]for some constant $c>0$.

Straus has observed that if $2^k\geq n$ then there exist $n$ points in $\mathbb{R}^k$ which contain no isosceles triangle and determine at most $n-1$ distances.

See also [135].

View the LaTeX source

This page was last edited 15 October 2025.

Erdős believed this should be possible, and should imply effective upper bounds for [658] (presumably the version with no alignment restrictions on the squares).

View the LaTeX source

For the similar problem in $\mathbb{R}^2$ there are always at least $n/2$ distances, as proved by Altman [Al63] (see [93]). In [Er75f] Erdős claims that Altman proved that the vertices determine $\gg n$ many distinct distances, but gives no reference.

View the LaTeX source

This page was last edited 24 October 2025.

One can also ask this for points in $\mathbb{R}^3$. In $\mathbb{R}^4$ Lenz observed that there are $x_1,\ldots,x_n,y_1,\ldots,y_n\in \mathbb{R}^4$ such that $d(x_i,y_j)=1$ for all $i,j$, taking the points on two orthogonal circles.

More generally, if $F(2n)$ is the minimal number of such distances, and $f(2n)$ is minimal number of distinct distances between any $2n$ points in $\mathbb{R}^2$, then is $f =o(F)$?

See also [89].

View the LaTeX source

A problem of Erdős, Lovász, and Vesztergombi.

This is essentially verbatim the problem description in [Er97e], but this does not make sense as written; there must be at least one typo. Suggestions about what this problem intends are welcome.

Erdős also goes on to write 'Perhaps the following stronger conjecture holds: Let $t_1<t_2<\cdots$ be the set of distances occurring in the triangular lattice. $t_1=1$ $t_2=\sqrt{3}$ $t_3=3$ $t_4=5$ etc. Is it true that there is an $\epsilon_n$ so that for every set $y_1,\ldots,$ with $d(y_i,y_j)\geq 1$ the number of distances $d(y_i,y_j)<t_n$ is less than $f(t_n)$?'

Again, this is nonsense interpreted literally; I am not sure what Erdős intended.

View the LaTeX source

In fact this is $=1$ also for $n=4$, the unique example given by two equilateral triangles joined by an edge.

Computational evidence of Engel, Hammond-Lee, Su, Varga, and Zsámboki [EHSVZ25] and Alexeev, Mixon, and Parshall [AMP25] suggests that this count is $=1$ for various other $5\leq n\leq 21$ (although these calculations were checking only up to graph isomorphism, rather than congruency).

View the LaTeX source

The lower bound of $\binom{n}{2}$ for the diameter is trivial. Erdős [Er97f] proved the claim when $d=1$.

View the LaTeX source

Avis, Erdős, and Pach [AEP88] proved that\[\frac{n}{2}+2 \leq f(n) \leq (1+o(1))\frac{n}{2}.\]This was proved by Swanepoel [Sw13], who in fact proved more generally that, in any finite set $A\subset \mathbb{R}^4$ of size $n$ and any choice of distance $d(x)$ for each $x\in A$,\[\sum_{x\in A}\sum_{y\in A}1_{\lvert x-y\rvert =d(x)}\leq \tfrac{1}{2}n^2+O(n),\]and proved similar results for finite point sets in higher dimensional space.

View the LaTeX source

Asked by Erdős and Pach in the stronger form of whether all distances (aside from the largest) can occur with multiplicity $>n$. Hopf and Pannowitz [HoPa34] proved that the largest distance between points of $A$ can occur at most $n$ times, but it is unknown whether a second such distance must occur (see [132]).

The answer is yes: Bhowmick [Bh24] constructs a set of $n$ points in $\mathbb{R}^2$ such that $\lfloor\frac{n}{4}\rfloor$ distances occur at least $n+1$ times. More generally, they construct, for any $m$ and large $n$, a set of $n$ points such that $\lfloor \frac{n}{2(m+1)}\rfloor$ distances occur at least $n+m$ times.

Further investigations were undertaken by Clemen, Dumitrescu, and Liu [CDL25], who proved, amongst other results, that if we take $A$ to be the square grid of $n$ points, then there are at least $n^{c/\log\log n}$ many distances which occur with multiplicity at least $n^{1+c/\log\log n}$ (for some constant $c>0$).

See also [132] and [957].

View the LaTeX source

For comparison, note that if $B$ were a Sidon set then $\lvert B-B\rvert=13$, so this condition is saying that at most one difference is 'missing' from $B-B$. Equivalently, one can view $A$ as a set such that every four points determine at least five distinct distances, and ask for a subset with all distances distinct.

Erdős and Sós proved that $c\geq 1/2$. Gyárfás and Lehel [GyLe95] proved\[\frac{1}{2}<c<\frac{3}{5}.\](The example proving the upper bound is the set of the first $n$ Fibonacci numbers.)

View the LaTeX source

A problem of Erdős and Sárközi. Erdős [Er77c] writes that 'Sárközi has the sharpest results, but nothing has been published yet'.

The trivial upper bound is $O(r)$. Kovac has observed that Sárközy's lower bound in [466] can be adapted to give a lower bound of $\gg r^{0.26}$ for this problem.

See also [465] for a similar problem (concerning upper bounds) and [466] for a similar problem (concerning lower bounds).

View the LaTeX source

This page was last edited 16 September 2025.

A problem of Erdős and Pach [ErPa90], who proved that $h(n) \ll n^{4/3}$. They also consider the related function where we consider $n$ disjoint convex sets (not necessarily translates), for which they give an upper bound of $\ll n^{7/5}$.

It is trivial that $h(n)\geq f(n)$, where $f(n)$ is the maximal number of unit distances determined by $n$ points in $\mathbb{R}^2$ (see [90]).

View the LaTeX source

A question of Erdős and Pach [ErPa90], who write that an 'easy' unpublished construction of Makai shows that this would be the best possible, and that it is 'not difficult' to prove\[f(d_1)+f(d_k) \leq 3n -c\sqrt{n}+o(\sqrt{n})\]for some $c>0$, and ask what the best possible value of $c$ is.

A stronger version of this problem (which implies the inequality in the problem statement) is that\[f(d_1)\leq 3n-2m+o(\sqrt{n}),\]where $m$ is the number of vertices of the convex hull of $A$.

The odd regular polygon shows that it is possible for $f(d_i)\geq n$ for all $i$.

The original problem was solved by Dumitrescu [Du19], who proved that\[f(d_1)f(d_k)\leq \frac{9}{8}n^2+O(n).\]See also [132] and [756].

View the LaTeX source

Erdős conjectured that the answer is no, and other such configurations exist.

This was proved by Clemen, Dumitrescu, and Liu [CDL25], who observed that equidistant points on a short circular arc on a circle of radius $1$, together with the centre, are also an example.

View the LaTeX source

More generally, one can ask about\[\max (f(d_r)-f(d_{r+1})).\]Clemen, Dumitrescu, and Liu [CDL25], have shown that\[\max (f(d_1)-f(d_2))\gg n\log n.\]More generally, for any $1\leq k\leq \log n$, there exists a set $A$ of $n$ points such that\[f(d_r)-f(d_{r+1})\gg \frac{n\log n}{r}.\]They conjecture that $n\log n$ can be improved to $n^{1+c/\log\log n}$ for some constant $c>0$.

View the LaTeX source

The regular polygon shows that $\lfloor n/2\rfloor$ is the best possible here.

This would be implied if there was a vertex such that no three vertices of the polygon are equally distant to it, which was originally also conjectured by Erdős [Er46b], but this is false (see [97]).

Let $f(n)$ be the maximal number of such distances that are guaranteed. Moser [Mo52] proved that\[f(n) \geq \left\lceil\frac{n}{3}\right\rceil.\]This was improved by Erdős and Fishburn [ErFi94] to\[f(n) \geq \left\lfloor \frac{n}{3}+1\right\rfloor,\]then\[f(n) \geq \left\lceil \frac{13n-6}{36}\right\rceil\]by Dumitrescu [Du06b], and most recently\[f(n) \geq \left(\frac{13}{36}+\frac{1}{22701}\right)n-O(1)\]by Nivasch, Pach, Pinchasi, and Zerbib [NPPZ13].

In [Er46b] Erdős makes the even stronger conjecture that on every convex curve there exists a point $p$ such that every circle with centre $p$ intersects the curve in at most $2$ points. Bárány and Roldán-Pensado [BaRo13] noted that the boundary of any acute triangle is a counterexample.

Bárány and Roldán-Pensado prove that, for any planar convex body, there is a point $p$ on the boundary such that every circle with centre $p$ intersects the boundary in at most $O(1)$ (where the implied constant depends on the convex body). They conjecture that there this can be bounded by an absolute constant - that is, Erdős's conjecture is true if we replace $2$ by some larger constant $C$.

See also [93].

View the LaTeX source

This page was last edited 19 October 2025.

A conjecture of Szemerédi, who proved this with $n/2$ replaced by $n/3$. More generally, Szemerédi gave a simple proof that if there are no $k$ points on a line then some point determines $\gg n/k$ distinct distances (a weak inverse result to the distinct distance problem [89]).

This is a stronger form of [93]. The second question is a stronger form of [982].

Szemerédi's proof is unpublished, but given in [Er75f].

In [Er75f] Erdős asks whether, given $n$ points in $\mathbb{R}^3$ with no three on a line, do they determine $\gg n$ distances? Altman proved the answer is yes if the points form the vertices of a convex polyhedron (see [660] for a stronger form of this), and Szemerédi proved the answer is yes if there are no four points on a plane.

View the LaTeX source

This page was last edited 24 October 2025.

A generalisation of the distinct distance problem [89] to higher dimensions. Erdős [Er46b] proved\[n^{1/d}\ll_d f_d(n)\ll_d n^{2/d},\]the upper bound construction being given by a set of lattice points.

• Clarkson, Edelsbrunner, Gubias, Sharir, and Welzl [CEGSW90] proved $f_3(n)\gg n^{1/2}$.


• Aronov, Pach, Sharir, and Tardos [APST04] proved $f_d(n)\gg n^{\frac{1}{d-90/77}-o(1)}$ for any $d\geq 3$ (for example, $f_3(n)\gg n^{0.546}$).


• Solymosi and Vu [SoVu08] proved $f_3(n) \gg n^{3/5}$ and\[ f_d(n)\gg_d n^{\frac{2}{d}-\frac{c}{d^2}}\]for all $d\geq 4$ for some constant $c>0$. (The result in their paper for $d=3$ is slightly weaker than stated here, but uses as a black box the bound for distinct distances in $2$ dimensions; we have recorded the consequence of combining their method with the work of Guth and Katz on [89].)

The function $f_d(n)$ is essentially the inverse of the function $g_d(n)$ considered in [1089] - with our definitions, $g_d(n)>m$ if and only if $f_d(m)<n$. The emphasis in this problem is, however, on the behaviour as $d$ is fixed and $n\to \infty$.

View the LaTeX source

This page was last edited 16 October 2025.

It is easy to see that $f_1(n)=n-1$ and $f_2(n)<3n$ (since there can be at most $6$ points of distance $1$ from any point). Erdős [Er46b] showed\[f_2(n)<3n-cn^{1/2}\]for some constant $c>0$, which the triangular lattice shows is the best possible up to the value of $c$. In [Er75f] he speculated that the triangular lattice is exactly the best possible, and in particular\[f_2(3n^2+3n+1)=9n^2+6n.\]In [Er75f] he claims the existence of $c_1,c_2>0$ such that\[6n-c_1n^{2/3}< f_3(n) < 6n-c_2n^{2/3}.\]See [223] for the analogous problem with maximal distance $1$.

View the LaTeX source

This page was last edited 15 October 2025.

The most difficult cases are $d=2$ and $d=3$. When $d=2$ this is the unit distance problem [90], and the best known bounds are\[n^{1+\frac{c}{\log\log n}}< f_2(n) \ll n^{4/3}\]for some constant $c>0$, the lower bound by Erdős [Er46b] and the upper bound by Spencer, Szemerédi, and Trotter [SST84].

When $d=3$ the best known bounds are\[n^{4/3}\log\log n \ll f_3(n) \ll n^{3/2}\beta(n)\]where $\beta(n)$ is a very slowly growing function, the lower bound by Erdős [Er60b] and the upper bound by Clarkson, Edelsbrunner, Guibas, Sharir, and Welzl [CEGSW90].

A construction of Lenz (taking points on orthogonal circles) shows that, for $d\geq 4$,\[f_d(n)\geq \frac{p-1}{2p}n^2-O(1)\]with $p=\lfloor d/2\rfloor$. Erdős [Er60b] showed that the Erdős-Stone theorem implies\[f_d(n) \leq \left(\frac{p-1}{2p}+o(1)\right)n^2\]for $d\geq 4$.

Erdős [Er67e] determined $f_d(n)$ up to $O(1)$ for all even $d\geq 4$. Brass [Br97] determined $f_4(n)$ exactly. Swanepoel [Sw09] determined $f_d(n)$ exactly for even $d\geq 6$. For odd $d\geq 5$ Erdős and Pach [ErPa90] proved that there exist constants $c_1(d),c_2(d)>0$ such that\[\frac{p-1}{2p}n^2 +c_1n^{4/3}\leq f_d(n) \leq \frac{p-1}{2p}n^2 +c_2n^{4/3}.\]

View the LaTeX source

This page was last edited 17 October 2025.

Equivalently, how many triangles of area $1$ can a set of $n$ points in $\mathbb{R}^2$ determine? Erdős and Purdy attribute this question to Oppenheim. Erdős and Purdy [ErPu71] proved\[n^2\log\log n \ll g(n) \ll n^{5/2},\]and believed the lower bound to be closer to the truth. The upper bound has been improved a number of times - by Pach and Sharir [PaSh92], Dumitrescu, Sharir, and Tóth [DST09], Apfelbaum and Sharir [ApSh10], and Apfaulbaum [Ap13]. The best known bound is\[g(n) \ll n^{20/9}\]by Raz and Sharir [RaSh17].

Erdős and Purdy also ask a similar question about the higher-dimensional generalisations - more generally, let $g_d^{r}(n)$ be minimal such that any set of $n$ points in $\mathbb{R}^d$ contains the vertices of at most $g_d^{r}(n)$ many $r$-dimensional simplices with the same volume.

Erdős and Purdy [ErPu71] proved $g_3^2(n) \ll n^{8/3}$, and Dumitrescu, Sharir, and Tóth [DST09] improved this to $g_3^2(n) \ll n^{2.4286}$.
Erdős and Purdy [ErPu71] proved $g_6^2(n)\gg n^3$. Purdy [Pu74] proved\[g_4^2(n)\leq g^2_5(n) \ll n^{3-c}\]for some constant $c>0$. An observation of Oppenheim (using a construction of Lenz) detailed in [ErPu71] shows that\[g_{2k+2}^k(n)\geq \left(\frac{1}{(k+1)^{k+1}}+o(1)\right)n^{k+1}\]and Erdős and Purdy conjecture this is the best possible.

See also [90] and [755].

View the LaTeX source

This page was last edited 16 October 2025.

A question of Erdős and Purdy [ErPu71], who proved\[n^3\log n \ll f(n) \ll n^{7/2}.\]

View the LaTeX source

A question of Kelly. Erdős [Er75f] writes it is 'easy' to see that $g_d(n)\gg d^{n-1}$. Erdős and Straus proved (in unpublished work mentioned in [Er75f]) that\[g_d(n) \leq c^{d^{1-b_n}}\]for some constants $c>0$ and $b_n>0$.

It is trivial that $g_1(3)=4$, and easy to see that $g_2(3)=6$. Croft [Cr62] proved $g_3(3)=7$. The vertices of a $d$-dimensional cube demonstrate that\[g_d(d+1)>2^d.\]The function $g_d(n)$ is essentially the inverse of the function $f_d(n)$ considered in [1083] - with our definitions, $g_d(n)>m$ if and only if $f_d(m)<n$. The emphasis in this problem is, however, on the behaviour for fixed $n$ as $d\to\infty$.

View the LaTeX source

This page was last edited 16 October 2025.