Regenerated from the community database (Apache-2.0), dated, and linked back to it from every problem. erdosproblems.com no longer shows statuses (Bloom's reasons); this is the database's record, not our verdict.
908 of 1221 statements are formalized in Lean (Formal Conjectures) · 107 carry an Erdős prize · 3 are independent of ZFC and 9 more can't be proved, or can't be disproved, from ZFC alone · “open” counts the computable and Lean-checked ones too.
Erdős distance problem
Erdős [Er46] asked whether every set of \(n\) distinct points in \(\mathbb{R}^2\) determines \(\gg \frac{n}{\sqrt{\log n}}\) many distinct distances.
unit distance problem
Does every set of \(n\) distinct points in \(\mathbb{R}^2\) contain at most \(n^{1+O(\frac{1}{\log\log n})}\) many pairs which are distance \(1\) apart? This was…
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.
If \(n\) distinct points in \(\mathbb{R}^2\) form a convex polygon then they determine at least \(\lfloor \frac{n}{2}\rfloor\) distinct distances. Solved by Altman [Al63].
Suppose \(n\) points in \(\mathbb{R}^2\) determine a convex polygon and the set of distances between them is \(\{u_1,\ldots,u_t\}\). Suppose \(u_i\) appears as the distance between \(f(u_i)\) many pairs of points. Then \[\sum_i f(u_i)^2…
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…
If \(n\) points in \(\mathbb{R}^2\) form a convex polygon then there are \(O(n)\) many pairs which are distance \(1\) apart.
Does every convex polygon have a vertex with no other 4 vertices equidistant from it?
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\)?
For sufficiently large n, is it the case that any set of n points with minimum distance \(1\) that minimizes diameter must contain an equilateral triangle of side length 1?
Is the diameter of \(A\) at least \(Cn\) for some constant \(C > 0\)?
Let \(h(n)\) count the number of incongruent sets of \(n\) points in \(\mathbb{R}^2\) which minimise the diameter subject to the constraint that \(d(x,y)\geq 1\) for all points \(x\neq y\). Is it true that \(h(n)\to \infty\)?
Is there a dense subset of ℝ^2 such that all pairwise distances are rational?
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?
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…
What is the size of the largest \(A\subseteq \mathbb{R}^n\) such that there are only two distinct distances between elements of \(A\)? That is, \[\# \{ \lvert x-y\rvert : x\neq y\in A\} = 2.\] Asked to Erdős by Coxeter. Bannai, Bannai, and…
What is the size of the largest \(A \subseteq \mathbb{R}^n\) such that every three points from \(A\) determine an isosceles triangle? That is, for any three points \(x\), \(y\), \(z\) from \(A\), at least two of the distances \(|x - y|\),…
pinned distance problem
Given \(n\) distinct points \(A\subset\mathbb{R}^2\), must there be a point \(x\in A\) such that \[\#\{ d(x,y) : y \in A\} \gg n^{1-o(1)}?\] This is the pinned distance problem, a stronger form of Problem 89. Here \(n^{1-o(1)}\) means: for…
Let \(x_1,\ldots,x_n\in \mathbb{R}^2\) and let \(R(x_i)=\#\{ \lvert x_j-x_i\rvert : j\neq i\}\), where the points are ordered such that \[R(x_1)\leq \cdots \leq R(x_n).\] Let \(\alpha_k\) be minimal such that, for all large enough \(n\),…
Let \(x_1,\ldots,x_n\in \mathbb{R}^2\) and let \(R(x_i)=\#\{ \lvert x_j-x_i\rvert : j\neq i\}\), where the points are ordered such that \[R(x_1)\leq \cdots \leq R(x_n).\] Let \(g(n)\) be the maximum number of distinct values the \(R(x_i)\)…
ambiguous statement
Let \(x_1,\ldots,x_n\in \mathbb{R}^2\) be such that no circle whose centre is one of the \(x_i\) contains three other points. Are there at least \[(1+c)\frac{n}{2}\] distinct distances determined between the \(x_i\), for some constant…
Is it true that if \(A\subset \mathbb{R}^2\) is a set of \(n\) points such that every subset of \(3\) points determines \(3\) distinct distances (that is, \(A\) has no isosceles triangles, degenerate ones included) then \(A\) determines at…
Is there a set of \(n\) points in \(\mathbb{R}^2\) such that every subset of \(4\) points determines at least \(3\) distances, yet the total number of distinct distances is \(\ll \frac{n}{\sqrt{\log n}}\)? There does exist such a set: a…
ambiguous statement
Let \(x_1, \ldots, x_n \in \mathbb{R}^3\) be the vertices of a convex polyhedron. Are there at least \[(1 - o(1)) \frac{n}{2}\] many distinct distances between the \(x_i\)? The \((1 - o(1)) \frac{n}{2}\) lower bound is formalised as: for…
Are there, for all large \(n\), some points \(x_1,\ldots,x_n,y_1,\ldots,y_n\in \mathbb{R}^2\) such that the number of distinct distances \(d(x_i,y_j)\) is \[o\left(\frac{n}{\sqrt{\log n}}\right)?\] We require all \(2n\) points to be…
ambiguous statement
Is it true that the number of incongruent sets of \(n\) points in \(\mathbb{R}^2\) which maximise the number of unit distances tends to infinity as \(n\to\infty\)? The actual maximal number of unit distances is the subject of [Erdős…
Let \(A\subseteq \mathbb{R}^d\) be a set of \(n\) points such that all pairwise distances differ by at least \(1\). Is the diameter of \(A\) at least \((1+o(1))n^2\)? The quantifiers in the source are ambiguous. Following the remarks on…
Let \(A\subset \mathbb{R}^2\) be a set of \(n\) points. Can there be \(\gg n\) many distinct distances each of which occurs for more than \(n\) many pairs from \(A\)? The answer is yes: Bhowmick [Bh24] constructs a set of \(n\) points in…
What is the supremum of the set of admissible numbers?
Let \(A\subset \mathbb{R}^2\) be a finite set of size \(n\), and let \(\{d_1,\ldots,d_k\}\) be the set of distances determined by \(A\). Let \(f(d)\) be the multiplicity of \(d\), that is, the number of unordered pairs from \(A\) of…
Let \(A\subseteq \mathbb{R}^2\) be a set of size \(n\) and let \(\{d_1,\ldots,d_k\}\) be the set of distinct distances determined by \(A\). Let \(f(d)\) be the number of times the distance \(d\) is determined, ordered so that…
If \(n\) distinct points in \(\mathbb{R}^2\) form a convex polygon then some vertex has at least \(\lfloor\frac{n}{2}\rfloor\) different distances to other vertices.
Let \(A\subset \mathbb{R}^2\) be a set of \(n\) points with no three on a line. Does \(A\) determine at least \(\lfloor n/2\rfloor\) distinct distances?
Let \(d\geq 3\), and let \(f_d(n)\) be the minimal \(m\) such that every set of \(n\) points in \(\mathbb{R}^d\) determines at least \(m\) distinct distances. Estimate \(f_d(n)\) - in particular, is it true that…
contact number problem
Let \(g_d(n)\) be minimal such that every collection of \(g_d(n)\) points in \(\mathbb{R}^d\) determines at least \(n\) many distinct distances. Estimate \(g_d(n)\). In particular, does \[\lim_{d \to \infty} \frac{g_d(n)}{d^{n-1}}\] exist?…
Let \(P_d(n)\) be such that in any set of \(n\) points in \(\mathbb{R}^d\) there exist at least \(P_d(n)\) many points which do not contain an isosceles triangle. Estimate \(P_d(n)\) - in particular, is it true that \[P_2(n)<n^{1-c}\] for…