Erdős Problem #91

Erdős Problem 91: uniqueness of distance-minimizing configurations

1. Statement and scope

2. Existence and small orders

At most three planar points can have every pair at the same positive distance. Indeed, normalize two to $(0,0)$ and $(1,0)$. A third must be $(1/2,\sqrt3/2)$ or $(1/2,-\sqrt3/2)$. These two possible third points have mutual distance $\sqrt3$, so they cannot both belong to such a configuration. It follows that $g(3)=1$, with a unique similarity class, the equilateral triangle, and $g(n)\ge2$ for $n\ge4$.

A square has distance set $\{1,\sqrt2\}$ after normalization. The four points \[ (0,0),\quad(1,0),\quad(1/2,\sqrt3/2),\quad(1/2,-\sqrt3/2) \] have distance set $\{1,\sqrt3\}$. Both configurations attain $g(4)=2$, and they are not similar because the ratio of their largest to smallest distance differs. A regular pentagon has just its side and diagonal lengths, so $g(5)=2$ as well. This last observation supplies an optimum, not a proof about how many optimal pentagon configurations exist.

3. An exact polynomial formulation

One must still quotient solutions by relabeling and congruence; different coordinates alone do not prove different shapes. This can be done exactly by distance matrices. Two normalized configurations are congruent if their full matrices of squared distances agree after a permutation of labels. To prove the nontrivial direction, subtract the first point and observe that \[ \langle p_i-p_1,p_j-p_1\rangle =\frac{|p_i-p_1|^2+|p_j-p_1|^2-|p_i-p_j|^2}{2}.\tag{3} \] Equal distance matrices give equal Gram matrices. The map sending each first configuration vector to its counterpart is well-defined and inner-product preserving on their spans: any linear relation has squared norm zero in one span if and only if it does in the other. Extending this isometry between subspaces to an orthogonal map of $\mathbb R^2$ proves congruence, including a possible reflection. Since both minimum distances are one, similarity is now the same as congruence.

Consequently, the existence of two optimal similarity classes for this fixed $n$ has the following precise formulation: find two solutions of the systems at $s=g(n)$ such that, for every permutation of labels, at least one corresponding squared distance differs. This is a finite collection of polynomial equalities and strict inequalities. We have not asserted that there are finitely many solutions or similarity classes; a polynomial system can have a continuum of solutions.

4. What is missing

Source: https://www.erdosproblems.com/91. All results asserted as established in this attempt are proved above; no classification of optimal configurations at larger orders is imported.

Completion rate estimate: 20%.

FORMAL RESTATEMENT. For $n\ge 2$ define \[ g(n):=\min\{D(A): A\subset\mathbb{R}^2,\ |A|=n\}, \] where $D(A)$ is the number of distinct Euclidean distances determined by unordered pairs from $A$. Call two finite point sets $A,B\subset\mathbb{R}^2$ similar if $B$ is obtained from $A$ by a similarity transformation (composition of a rigid motion and a uniform scaling; optionally allowing reflection---either choice does not affect the arguments below). Let $\mathcal{M}_n$ be the set of similarity classes of minimisers: \[ \mathcal{M}_n:=\{[A]_{\sim}: |A|=n,\ D(A)=g(n)\}. \] Question: prove that for all sufficiently large $n$ there are at least two non-similar minimisers, i.e. \[ |\mathcal{M}_n|\ge 2\qquad\text{for all large }n. \]

QUICK LITERATURE/CONTEXT CHECK. The problem statement gives small-$n$ facts: for $n=3$ the equilateral triangle is the unique minimiser; for $n=4$ there are at least two non-similar minimisers; for $n=5$ the regular pentagon is claimed to be the unique minimiser (with a cited proof). I do not use results beyond these statements; instead I verify the $n=4$ and the value $g(5)=2$ directly.

ATTACK PLAN.

• Reality check: verify the minimisation claims for $n=4,5$ directly by elementary arguments.
• General strategy (unresolved): attempt to build, for large $n$, two different-looking configurations $A,B$ with $D(A)=D(B)=g(n)$, e.g. by producing two distinct constructions achieving the same (conjecturally optimal) order of magnitude.

WORK.

Lemma 91.1 ($n=4$: two non-similar minimisers). We have $g(4)=2$, and there are at least two non-similar point sets $A\subset\mathbb{R}^2$ with $|A|=4$ and $D(A)=2$. Proof. Step 1: $g(4)\ge 2$. If $D(A)=1$, then all $\binom{4}{2}=6$ pairwise distances in $A$ are equal to some $r>0$. But in the plane, there is no set of 4 points that are pairwise equidistant: among any three of the points we get an equilateral triangle of side $r$; a fourth point at distance $r$ from all three would have to lie in the intersection of three circles of radius $r$ around the triangle's vertices. The first two circles intersect in at most two points, and neither of those points is at distance $r$ from the third vertex (the third circle), so the triple intersection is empty. Thus $D(A)\ne 1$ and $g(4)\ge 2$.

Step 2: two explicit examples with $D=2$.

• Square. Take the unit square with vertices $(0,0),(1,0),(1,1),(0,1)$. The pairwise distances are $1$ (edges) and $\sqrt2$ (diagonals), so $D=2$.
• Two equilateral triangles sharing an edge. Take points $B=(0,0)$, $C=(1,0)$, $A=(\tfrac12,\tfrac{\sqrt3}{2})$, $D=(\tfrac12,-\tfrac{\sqrt3}{2})$. Then $AB=AC=BC=1$ and $BD=CD=BC=1$, while $AD=\sqrt3$. Thus the distinct distances are $\{1,\sqrt3\}$, so again $D=2$.

Combining Steps 1--3 shows $g(4)=2$ and $|\mathcal{M}_4|\ge 2$. $\square$

Lemma 91.2 ($n=5$: the minimum value is 2). We have $g(5)=2$. Proof. As in Lemma 91.1, $g(5)\ge 2$ because 5 points cannot be pairwise equidistant in the plane. It remains to exhibit 5 points with exactly 2 distinct distances. Take a regular pentagon with side length $1$. In a regular pentagon, the pairwise distances are either the side length or the diagonal length, and there are no other distances among vertex pairs. More concretely, on a circle of radius $R=\left(2\sin(\pi/5)\right)^{-1}$, let $p_k=(R\cos(2\pi k/5),R\sin(2\pi k/5))$ for $k=0,1,2,3,4$. Then consecutive vertices satisfy $|p_{k+1}-p_k|=1$ by the choice of $R$, while nonconsecutive pairs are all diagonals and have the same length (by rotational symmetry). Therefore $D(\{p_0,\dots,p_4\})=2$, so $g(5)\le 2$. Thus $g(5)=2$. $\square$

FAST REALITY CHECK (explicit distance computations). A direct computation of squared distances for the configurations above gives:

Square: squared distances = {1, 2}
Two equilateral triangles sharing an edge: squared distances = {1, 3}
Regular pentagon (side=1): distances = {1, 1.6180339...}

VERIFICATION.

• The nonexistence of 4 (or 5) pairwise equidistant points in $\mathbb{R}^2$ follows from the fact that two circles intersect in at most two points.
• The regular pentagon argument uses only rotational symmetry: all sides equal; all diagonals equal; no other pairs.
• Non-similarity check is by the invariant distance ratio $\max\{|x-y|\}/\min\{|x-y|\}$.

FINAL. UNRESOLVED

1. (i) Strongest proved partial result. We verified $g(4)=2$ and exhibited two non-similar minimisers for $n=4$ (Lemma 91.1). We also proved $g(5)=2$ by exhibiting a regular pentagon with two distances (Lemma 91.2).
2. (ii) First gap (crisp). For large $n$, prove existence of two non-similar minimisers: construct $A,B$ with $|A|=|B|=n$, $D(A)=D(B)=g(n)$, and $A\not\sim B$.
3. (iii) Top 3 next moves.
   • For moderately small $n$ (say $6\le n\le 12$), run constrained numeric optimisation / discrete searches (e.g. restricting to small integer grids) to guess candidate minimisers and test for non-uniqueness.
   • Prove stability/rigidity results: if $A$ is a minimiser with near-grid structure, show that small deformations strictly increase $D(A)$, then look for a different structured family with the same $D$.
   • Attempt a "two constructions" approach: produce two explicit infinite families (e.g. square grids vs. certain circular-arc constructions) with the same asymptotic $D$ and then prove that this asymptotic is optimal for $g(n)$.
4. (iv) Likely structure of a minimal counterexample. A minimal counterexample would be an $n_0$ such that every minimiser for $g(n_0)$ is unique up to similarity, while for all smaller $n$ there are at least two classes. Such a unique minimiser would likely be extremely symmetric/rigid (analogous to the equilateral triangle for $n=3$), suggesting a highly constrained distance multiset.

OUTPUT 1) FORMAL RESTATEMENT Definitions/Conventions. For a finite set $A\subset\mathbb R^2$, define the number of distinct distances \[D(A):=\big|\{|x-y|: x,y\in A,\ x\ne y\}\big|.\] Let \[D_{\min}(n):=\min\{D(A): A\subset\mathbb R^2,\ |A|=n\}.\] Say that $A$ is an extremizer if $|A|=n$ and $D(A)=D_{\min}(n)$. Two sets are similar if one can be obtained from the other by a similarity transformation (composition of isometry and scaling).

Question. For large $n$, prove that there exist at least two non-similar extremizers $A$ for $D_{\min}(n)$.

2) QUICK LITERATURE/CONTEXT CHECK Web browsing is not available in this session. I will not use external results about $D_{\min}(n)$ beyond the small-$n$ examples stated in the problem text.

3) ATTACK PLAN Proof track ideas: 1. Understand small-$n$ extremizers and extract a mechanism for nonuniqueness (e.g. different combinatorial distance graphs). 2. Attempt to show that for large $n$, extremizers must be "highly structured" but not uniquely so, by comparing regular polygons vs. other configurations.

Disproof track ideas: 1. Try to show uniqueness of extremizers for infinitely many $n$; the problem statement suggests this is false for large $n$.

Chosen path in this attempt: establish the $n=4$ nonuniqueness rigorously as a model case by proving (i) $D_{\min}(4)=2$ and (ii) there are at least two non-similar extremizers achieving it.

4) WORK Lemma 1 (Four points determine at least two distinct distances). For any set $A\subset\mathbb R^2$ with $|A|=4$, one has $D(A)\ge 2$.

Proof. Assume for contradiction that $D(A)=1$. Then all pairwise distances between distinct points in $A$ are equal to some value $d>0$; i.e. $A$ is a set of four pairwise equidistant points. Pick three points $x,y,z\in A$. Since $|x-y|=|y-z|=|z-x|=d$, the triangle $xyz$ is equilateral. Let $O$ be the circumcenter of triangle $xyz$; in an equilateral triangle, the circumcenter is unique and satisfies $|O-x|=|O-y|=|O-z|=d/\sqrt3$.

Let $w$ be the fourth point in $A$. Because $|w-x|=|w-y|=d$, the point $w$ lies on the perpendicular bisector of segment $xy$. Similarly, $w$ lies on the perpendicular bisector of $xz$. The intersection of these two perpendicular bisectors is unique and equals the circumcenter $O$. Therefore $w=O$. But then $|w-x|=|O-x|=d/\sqrt3\ne d$, contradiction. Hence $D(A)\ge 2$. $\square$

Lemma 2 (Two non-similar extremizers for $n=4$). There exist two non-similar 4-point sets $A,B\subset\mathbb R^2$ with $D(A)=D(B)=2$.

Proof. Let $A$ be the vertices of a square of side length $1$. Then the pairwise distances among vertices are either $1$ (sides) or $\sqrt2$ (diagonals), so $D(A)=2$.

Let $B$ be the vertices of a rhombus with side length $1$ and acute angle $60^\circ$ (equivalently, two equilateral triangles sharing an edge). Then distances among its vertices are either $1$ (edges) or $\sqrt3$ (the longer diagonal), so again $D(B)=2$.

By Lemma 1, any 4-point set has at least 2 distinct distances, so $D_{\min}(4)=2$, and both $A$ and $B$ are extremizers. They are not similar because in a square the ratio of diagonal to side is $\sqrt2$, while in the $60^\circ$ rhombus the longer diagonal to side ratio is $\sqrt3$; similarity preserves this ratio. Thus $A$ and $B$ are non-similar extremizers. $\square$

FAST REALITY CHECK The problem statement says: $n=3$ has a unique extremizer (equilateral), $n=4$ has at least two, $n=5$ is unique (regular pentagon). Lemma 2 confirms the $n=4$ nonuniqueness with a complete proof.

5) VERIFICATION - Lemma 1's key fact is that the intersection of perpendicular bisectors of $xy$ and $xz$ is unique; this is standard Euclidean geometry. - Lemma 2 checks the distance sets explicitly and uses diagonal/side ratio as a similarity invariant.

6) FINAL UNRESOLVED

(i) Strongest fully proved partial result: I proved that $D_{\min}(4)=2$ and that there are at least two non-similar extremizers achieving it (Lemmas 1--2).

(ii) First gap: Extend beyond small $n$ and prove that for all sufficiently large $n$ there are at least two non-similar extremizers for $D_{\min}(n)$.

(iii) Top 3 next moves (concrete): 1. For each $n$, characterize the distance graph structure of extremizers (which distances occur with which multiplicities) and look for incompatible structures that can both realize $D_{\min}(n)$. 2. For $6\le n\le 9$ (where Erdős claimed nonuniqueness), write down explicit non-similar candidate extremizers and verify they achieve the same minimal number of distances. 3. Investigate whether known near-extremal constructions for the distinct distances problem (e.g. subsets of grids, regular polygons) can be perturbed in two inequivalent ways without increasing $D(A)$.

(iv) What a minimal counterexample would likely look like (structure/parameters): An infinite sequence $n_i\to\infty$ for which the extremizer is unique up to similarity, i.e. any $A$ with $|A|=n_i$ and $D(A)=D_{\min}(n_i)$ must be similar to a single canonical configuration.