/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil public import FormalConjectures.ErdosProblems.«90»

Erdős Problem 668

References:

    erdosproblems.com/668

    A385657

    [AMP25] B. Alexeev, D. Mixon, and H. Parshall, The Erdős unit distance problem for small point sets. arXiv:2412.11914 (2025).

    [EHSVZ25] P. Engel, O. Hammond-Lee, Y. Su, D. Varga, and P. Zsámboki, Diverse beam search to find densest-known planar unit distance graphs. arXiv:2406.15317 (2025).

    [Er97f] Erdős, Paul, Some unsolved problems. Combinatorics, geometry and probability (Cambridge, 1993) (1997), 1-10.

@[expose] public sectionopen Filteropen scoped EuclideanGeometrynamespace Erdos668open Erdos90

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 Problem 90.

Two sets of points are congruent if an isometry of the plane maps one onto the other.

@[category research open, question, AMS 52] theorem erdos_668.parts.i : ∀ m : ℕ, ∀ᶠ n in atTop, ∃ A : Fin m → Finset ℝ², (∀ i, (A i).card = n ∧ unitDistNum (A i) = maxUnitDistances n) ∧ ∀ i j, i ≠ j → ¬ ∃ f : ℝ² ≃ᵢ ℝ², f '' A i = A j := ⊢ ∀ (m : ℕ), ∀ᶠ (n : ℕ) in atTop, ∃ A, (∀ (i : Fin m), (A i).card = n ∧ unitDistNum (A i) = maxUnitDistances n) ∧ ∀ (i j : Fin m), i ≠ j → ¬∃ f, ⇑f '' ↑(A i) = ↑(A j) All goals completed! 🐙

Is it always $>1$ for $n>3$?

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

@[category research solved, question, AMS 52] theorem erdos_668.parts.ii : ¬ ∀ n : ℕ, 3 < n → ∃ A B : Finset ℝ², A.card = n ∧ B.card = n ∧ unitDistNum A = maxUnitDistances n ∧ unitDistNum B = maxUnitDistances n ∧ ¬ ∃ f : ℝ² ≃ᵢ ℝ², f '' A = B := ⊢ ¬∀ (n : ℕ), 3 < n → ∃ A B, A.card = n ∧ B.card = n ∧ unitDistNum A = maxUnitDistances n ∧ unitDistNum B = maxUnitDistances n ∧ ¬∃ f, ⇑f '' ↑A = ↑B All goals completed! 🐙

For $n=4$ there is, up to congruence, exactly one set of points in $\mathbb{R}^2$ which maximises the number of unit distances: two unit equilateral triangles $abc$ and $bcd$ joined by the edge $bc$, with $a\neq d$.

@[category research solved, AMS 52] theorem erdos_668.variants.four_points : ∃ a b c d : ℝ², dist a b = 1 ∧ dist a c = 1 ∧ dist b c = 1 ∧ dist b d = 1 ∧ dist c d = 1 ∧ ({a, b, c, d} : Finset ℝ²).card = 4 ∧ ∀ B : Finset ℝ², B.card = 4 → (unitDistNum B = maxUnitDistances 4 ↔ ∃ f : ℝ² ≃ᵢ ℝ², f '' {a, b, c, d} = B) := ⊢ ∃ a b c d, dist a b = 1 ∧ dist a c = 1 ∧ dist b c = 1 ∧ dist b d = 1 ∧ dist c d = 1 ∧ {a, b, c, d}.card = 4 ∧ ∀ (B : Finset ℝ²), B.card = 4 → (unitDistNum B = maxUnitDistances 4 ↔ ∃ f, ⇑f '' {a, b, c, d} = ↑B) All goals completed! 🐙

Erdos668.erdos_668.variants.four_points settles Erdos668.erdos_668.parts.ii at $n = 4$.

a:ℝ²b:ℝ²c:ℝ²d:ℝ²h:∀ (B : Finset ℝ²), B.card = 4 → (unitDistNum B = maxUnitDistances 4 ↔ ∃ f, ⇑f '' {a, b, c, d} = ↑B)H:∀ (n : ℕ), 3 < n → ∃ A B, A.card = n ∧ B.card = n ∧ unitDistNum A = maxUnitDistances n ∧ unitDistNum B = maxUnitDistances n ∧ ¬∃ f, ⇑f '' ↑A = ↑BA:Finset ℝ²B:Finset ℝ²hA:A.card = 4hB:B.card = 4hAm:unitDistNum A = maxUnitDistances 4hBm:unitDistNum B = maxUnitDistances 4hAB:¬∃ f, ⇑f '' ↑A = ↑Bf:ℝ² ≃ᵢ ℝ²hf:⇑f '' {a, b, c, d} = ↑Ag:ℝ² ≃ᵢ ℝ²hg:⇑g '' {a, b, c, d} = ↑B⊢ (fun x ↦ (f.symm.trans g) (f x)) '' {a, b, c, d} = ⇑g '' {a, b, c, d}; All goals completed! 🐙⟩end Erdos668