AFTD Auto-Formalizing Theoretical Domains

op_462_min_counterexample_card_three_in_range

theoremverifiedformalization

There exists a unique natural number m in the range 5 ≤ m ≤ 101 such that m is the least element of the set of cardinalities of all finite counterexamples to Gale's conjecture in dimension 3.

Statement

theorem op_462_min_counterexample_card_three_in_range :
    ∃! m : ℕ, 5 ≤ m ∧ m ≤ 101 ∧
      IsLeast {k : ℕ | ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = k ∧ is_gale_counterexample_three V} m
Formalizes
arXiv:2610.28828 Sec. 5, Question 2
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
  • gale_distance_graphFor a finite subset V of the 3-dimensional Euclidean space EuclideanSpace ℝ (Fin 3) and a real number t, gale_distance_graph V t is…
  • is_gale_counterexample_threeA finite subset V of the 3-dimensional Euclidean space EuclideanSpace ℝ (Fin 3) is a counterexample to Gale's conjecture in dimension 3…
  • op462_no_four_coloring65No map from the 65 points to four colors separates every witness edge.
  • op462_edges65The 859 witness edges on the 65 indexed points in the primary repository.
  • gale_sigma_threeThe real constant gale_sigma_three is defined as the square root of (3 + sqrt(3)) / 6.
  • op_462_gale_counterexample_card_three_ge_fiveFor every finite subset V of EuclideanSpace ℝ (Fin 3), if V is a counterexample to Gale's conjecture in dimension 3…
  • op462_coords65_diameter_squared_leEvery squared distance between the scaled integer points is at most 10^34.
  • op462_coords65The exact integer coordinates of the 65 indexed points, obtained by multiplying the primary decimal coordinates by 10^17.
  • op462_coords65_edges_squared_geEvery witness edge has scaled squared distance at least 7887420401648046950672144846523981.

Read back from the Lean

There exists a unique natural number $m$ such that $5 \le m \le 101$ and $m$ is the least element of the set of cardinalities of all finite subsets $V$ of Euclidean space $\mathbb{R}^3$ that satisfy is_gale_counterexample_three V (that is, $V$ has strictly positive diameter and the graph on $V$ where an edge connects distinct points at distance strictly greater than $\sqrt{(3 + \sqrt{3})/6} \cdot \mathrm{diam}(V)$ cannot be properly 4-colored).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem shows there is a unique natural number m in the range 5 to 101 that is the minimum cardinality of a 3-dimensional finite counterexample to Gale's conjecture. An explicit 65-vertex configuration with integer coordinates is scaled to produce a counterexample of size at most 65, establishing that the set of counterexample sizes is non-empty and has a minimum m <= 65 <= 101. General theory ensures any counterexample in dimension 3 has at least 5 vertices, and the least element of a set of natural numbers is unique.

  1. Define the scaled points p_i and establish denominator positivity

    Define p i = P i / S in R^3 and note that S > 0 implies S^2 > 0.

    lines 10–14

    uses sq_pos_of_pos

      classical
      let p : Fin n → EuclideanSpace ℝ (Fin 3) :=
        fun i => WithLp.toLp 2 (fun k => (P i k : ℝ) / (S : ℝ))
      have hSreal : (0 : ℝ) < S := by exact_mod_cast hS
      have hden : (0 : ℝ) < (S : ℝ)^2 := sq_pos_of_pos hSreal
  2. Compute the squared distance between any two points

    The squared distance between p i and p j equals the integer sum of coordinate differences squared divided by S^2.

    lines 15–22

    uses EuclideanSpace.dist_sq_eq, Finset.sum_congr, Finset.sum_div, Int.cast_pow, Int.cast_sub, Int.cast_sum, Real.dist_eq, sq_abs

      have hdistsq (i j : Fin n) :
          dist (p i) (p j)^2 = ((∑ k : Fin 3, (P i k - P j k)^2 : ℤ) : ℝ) / (S : ℝ)^2 := by
        rw [EuclideanSpace.dist_sq_eq]
        simp only [p, Real.dist_eq, sq_abs, Int.cast_sum, Int.cast_pow,
          Int.cast_sub, Finset.sum_div]
        apply Finset.sum_congr rfl
        intro k _
        ring
  3. Pairwise distances are at most 1

    Since the integer sum is at most S^2, the squared distance is at most 1, so distance is at most 1.

    lines 23–31

    uses dist_nonneg, div_le_div_of_nonneg_right, div_self

      have hdistle (i j : Fin n) : dist (p i) (p j) ≤ 1 := by
        have hh : dist (p i) (p j)^2 ≤ 1 := by
          rw [hdistsq]
          calc
            _ ≤ (S : ℝ)^2 / (S : ℝ)^2 := by
              apply div_le_div_of_nonneg_right _ hden.le
              exact_mod_cast hunit i j
            _ = 1 := div_self hden.ne'
        nlinarith [dist_nonneg (x := p i) (y := p j)]
  4. gale_sigma_three is strictly positive

    Positivity tactic verifies sigma_3 > 0.

    lines 32–34

      have hsig : 0 < gale_sigma_three := by
        unfold gale_sigma_three
        positivity
  5. Distances on edges exceed gale_sigma_three

    For any edge e in E, the integer sum is at least Q, so dist(p e.1, p e.2)^2 >= Q/S^2 > sigma_3^2, giving dist > sigma_3.

    lines 35–43

    uses List.all_eq_true.mp, dist_nonneg, div_le_div_of_nonneg_right, of_decide_eq_true

      have hdistedge (e : Fin n × Fin n) (he : e ∈ E) :
          gale_sigma_three < dist (p e.1) (p e.2) := by
        have he' := (List.all_eq_true.mp hedge) e he
        have hi : Q ≤ ∑ k : Fin 3, (P e.1 k - P e.2 k)^2 := of_decide_eq_true he'
        have hh : (Q : ℝ) / (S : ℝ)^2 ≤ dist (p e.1) (p e.2)^2 := by
          rw [hdistsq]
          apply div_le_div_of_nonneg_right _ hden.le
          exact_mod_cast hi
        nlinarith [dist_nonneg (x := p e.1) (y := p e.2)]
  6. Define the point set V

    Let V be the image of Fin n under p, and note every p i is in V.

    lines 44–46

    uses Finset.mem_image.mpr, Finset.mem_univ

      let V : Finset (EuclideanSpace ℝ (Fin 3)) := Finset.univ.image p
      have hp (i : Fin n) : p i ∈ (V : Set (EuclideanSpace ℝ (Fin 3))) := by
        exact Finset.mem_image.mpr ⟨i, Finset.mem_univ _, rfl⟩
  7. The diameter of V is at most 1

    Since all pairwise distances are at most 1, the diameter is at most 1.

    lines 47–52

    uses Finset.mem_image.mp, Metric.diam_le_of_forall_dist_le

      have hdiamle : Metric.diam (V : Set (EuclideanSpace ℝ (Fin 3))) ≤ 1 := by
        apply Metric.diam_le_of_forall_dist_le (by norm_num)
        intro x hx y hy
        obtain ⟨i, _, rfl⟩ := Finset.mem_image.mp hx
        obtain ⟨j, _, rfl⟩ := Finset.mem_image.mp hy
        exact hdistle i j
  8. The diameter of V is strictly positive

    The edge (a,b) in E gives two points at distance > sigma_3 > 0, so the diameter is positive.

    lines 53–55

    uses Metric.dist_le_diam_of_mem, lt_of_lt_of_le

      have hdiampos : 0 < Metric.diam (V : Set (EuclideanSpace ℝ (Fin 3))) := by
        apply lt_of_lt_of_le (hsig.trans (hdistedge (a,b) hab))
        exact Metric.dist_le_diam_of_mem V.finite_toSet.isBounded (hp a) (hp b)
  9. V is a Gale counterexample in dimension 3

    Any 4-coloring of the Gale distance graph would induce a valid 4-coloring of (Fin n, E), contradiction.

    lines 56–68

    uses Subtype.val, congrArg, dist_pos.mp, lt_of_le_of_lt, mul_le_of_le_one_right

      have hV : is_gale_counterexample_three V := by
        refine ⟨hdiampos, ?_⟩
        rintro ⟨c⟩
        apply hnotcolor (fun i => c ⟨p i, hp i⟩)
        intro e he
        apply c.valid
        have hed := hdistedge e he
        have hne : p e.1 ≠ p e.2 := dist_pos.mp (hsig.trans hed)
        change (⟨p e.1, hp e.1⟩ : V) ≠ ⟨p e.2, hp e.2⟩ ∧
          gale_sigma_three * Metric.diam (V : Set (EuclideanSpace ℝ (Fin 3))) < dist (p e.1) (p e.2)
        constructor
        · exact fun hh => hne (congrArg Subtype.val hh)
        · exact lt_of_le_of_lt (mul_le_of_le_one_right hsig.le hdiamle) hed
  10. The cardinality of V is at most 101

    V has cardinality at most n < 101.

    lines 69–70

    uses Finset.card_image_le.trans_eq

      have hcard : V.card ≤ n := Finset.card_image_le.trans_eq (by simp)
      exact ⟨V, by omega, hV⟩
  11. Verify the numerical gap for the 65-vertex configuration

    Check sigma_3^2 < Q/S^2 for the chosen constants.

    lines 76–81

    uses Real.sq_sqrt

      classical
      have hgap : gale_sigma_three^2 <
          ((7887420401648046950672144846523981 : ℤ) : ℝ) / ((10^17 : ℤ) : ℝ)^2 := by
        unfold gale_sigma_three
        rw [Real.sq_sqrt (by positivity)]
        num_ineq
  12. Obtain a concrete counterexample with at most 65 vertices

    Apply the witness lemma to the 65-vertex graph and coordinate data.

    lines 82–86

    uses op462_coords65, op462_coords65_diameter_squared_le, op462_coords65_edges_squared_ge, op462_edges65, op462_no_four_coloring65, op_462_min_counterexample_card_three_in_range_witness

      obtain ⟨V, hcard, hV⟩ :=
        op_462_min_counterexample_card_three_in_range_witness 65 (by decide) (10^17)
          7887420401648046950672144846523981 (by norm_num) op462_coords65 op462_edges65
          op462_coords65_diameter_squared_le op462_coords65_edges_squared_ge hgap
          op462_no_four_coloring65 0 1 (by decide)
  13. Define T and obtain its minimum element

    Let T be the set of cardinalities of Gale counterexamples. Since V witnesses T is nonempty, T has a least element sInf T.

    lines 87–90

    uses Nat.sInf_le, Nat.sInf_mem

      let T : Set ℕ := {k : ℕ | ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = k ∧ is_gale_counterexample_three V}
      have hne : T.Nonempty := ⟨V.card, V, rfl, hV⟩
      have hmem : sInf T ∈ T := Nat.sInf_mem hne
      have hleast : IsLeast T (sInf T) := ⟨hmem, fun b hb => Nat.sInf_le hb⟩
  14. Show 5 <= sInf T <= 101

    Any 3D counterexample has cardinality at least 5, and sInf T <= |V| <= 101.

    lines 91–95

    uses Nat.sInf_le, op_462_gale_counterexample_card_three_ge_five

      refine ⟨sInf T, ⟨?_, ?_, hleast⟩, ?_⟩
      · have hmem' : ∃ W : Finset (EuclideanSpace ℝ (Fin 3)), W.card = sInf T ∧ is_gale_counterexample_three W := hmem
        obtain ⟨W, hWc, hW⟩ := hmem'
        exact hWc ▸ op_462_gale_counterexample_card_three_ge_five W hW
      · exact (Nat.sInf_le (show V.card ∈ T from ⟨V, rfl, hV⟩)).trans hcard
  15. Uniqueness of the minimum

    The least element of a partially ordered set is unique.

    lines 96–97

    uses IsLeast.unique

      · intro m hm
        exact (hm.2.2).unique hleast

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

lemma op_462_min_counterexample_card_three_in_range_witness    (n : ℕ) (hn : n < 101) (S Q : ℤ) (hS : 0 < S)    (P : Fin n → Fin 3 → ℤ) (E : List (Fin n × Fin n))    (hunit : ∀ i j, (∑ k : Fin 3, (P i k - P j k)^2) ≤ S^2)    (hedge : E.all (fun e => decide (Q ≤ ∑ k : Fin 3, (P e.1 k - P e.2 k)^2)) = true)    (hgap : gale_sigma_three^2 < (Q : ℝ) / (S : ℝ)^2)    (hnotcolor : ∀ c : Fin n → Fin 4, (∀ e ∈ E, c e.1 ≠ c e.2) → False)    (a b : Fin n) (hab : (a,b) ∈ E) :    ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card ≤ 101 ∧ is_gale_counterexample_three V := by  classical  let p : Fin n → EuclideanSpace ℝ (Fin 3) :=    fun i => WithLp.toLp 2 (fun k => (P i k : ℝ) / (S : ℝ))  have hSreal : (0 : ℝ) < S := by exact_mod_cast hS  have hden : (0 : ℝ) < (S : ℝ)^2 := sq_pos_of_pos hSreal  have hdistsq (i j : Fin n) :      dist (p i) (p j)^2 = ((∑ k : Fin 3, (P i k - P j k)^2 : ℤ) : ℝ) / (S : ℝ)^2 := by    rw [EuclideanSpace.dist_sq_eq]    simp only [p, Real.dist_eq, sq_abs, Int.cast_sum, Int.cast_pow,      Int.cast_sub, Finset.sum_div]    apply Finset.sum_congr rfl    intro k _    ring  have hdistle (i j : Fin n) : dist (p i) (p j) ≤ 1 := by    have hh : dist (p i) (p j)^2 ≤ 1 := by      rw [hdistsq]      calc        _ ≤ (S : ℝ)^2 / (S : ℝ)^2 := by          apply div_le_div_of_nonneg_right _ hden.le          exact_mod_cast hunit i j        _ = 1 := div_self hden.ne'    nlinarith [dist_nonneg (x := p i) (y := p j)]  have hsig : 0 < gale_sigma_three := by    unfold gale_sigma_three    positivity  have hdistedge (e : Fin n × Fin n) (he : e ∈ E) :      gale_sigma_three < dist (p e.1) (p e.2) := by    have he' := (List.all_eq_true.mp hedge) e he    have hi : Q ≤ ∑ k : Fin 3, (P e.1 k - P e.2 k)^2 := of_decide_eq_true he'    have hh : (Q : ℝ) / (S : ℝ)^2 ≤ dist (p e.1) (p e.2)^2 := by      rw [hdistsq]      apply div_le_div_of_nonneg_right _ hden.le      exact_mod_cast hi    nlinarith [dist_nonneg (x := p e.1) (y := p e.2)]  let V : Finset (EuclideanSpace ℝ (Fin 3)) := Finset.univ.image p  have hp (i : Fin n) : p i ∈ (V : Set (EuclideanSpace ℝ (Fin 3))) := by    exact Finset.mem_image.mpr ⟨i, Finset.mem_univ _, rfl⟩  have hdiamle : Metric.diam (V : Set (EuclideanSpace ℝ (Fin 3))) ≤ 1 := by    apply Metric.diam_le_of_forall_dist_le (by norm_num)    intro x hx y hy    obtain ⟨i, _, rfl⟩ := Finset.mem_image.mp hx    obtain ⟨j, _, rfl⟩ := Finset.mem_image.mp hy    exact hdistle i j  have hdiampos : 0 < Metric.diam (V : Set (EuclideanSpace ℝ (Fin 3))) := by    apply lt_of_lt_of_le (hsig.trans (hdistedge (a,b) hab))    exact Metric.dist_le_diam_of_mem V.finite_toSet.isBounded (hp a) (hp b)  have hV : is_gale_counterexample_three V := by    refine ⟨hdiampos, ?_⟩    rintro ⟨c⟩    apply hnotcolor (fun i => c ⟨p i, hp i⟩)    intro e he    apply c.valid    have hed := hdistedge e he    have hne : p e.1 ≠ p e.2 := dist_pos.mp (hsig.trans hed)    change (⟨p e.1, hp e.1⟩ : V) ≠ ⟨p e.2, hp e.2⟩ ∧      gale_sigma_three * Metric.diam (V : Set (EuclideanSpace ℝ (Fin 3))) < dist (p e.1) (p e.2)    constructor    · exact fun hh => hne (congrArg Subtype.val hh)    · exact lt_of_le_of_lt (mul_le_of_le_one_right hsig.le hdiamle) hed  have hcard : V.card ≤ n := Finset.card_image_le.trans_eq (by simp)  exact ⟨V, by omega, hV⟩/-- Open Problem OP-462: there is a unique natural number m between 5 and 101 that is the minimum cardinality of a finite counterexample to Gale's conjecture in dimension 3. -/theorem op_462_min_counterexample_card_three_in_range :    ∃! m : ℕ, 5 ≤ m ∧ m ≤ 101 ∧      IsLeast {k : ℕ | ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = k ∧ is_gale_counterexample_three V} m := by  classical  have hgap : gale_sigma_three^2 <      ((7887420401648046950672144846523981 : ℤ) : ℝ) / ((10^17 : ℤ) : ℝ)^2 := by    unfold gale_sigma_three    rw [Real.sq_sqrt (by positivity)]    num_ineq  obtain ⟨V, hcard, hV⟩ :=    op_462_min_counterexample_card_three_in_range_witness 65 (by decide) (10^17)      7887420401648046950672144846523981 (by norm_num) op462_coords65 op462_edges65      op462_coords65_diameter_squared_le op462_coords65_edges_squared_ge hgap      op462_no_four_coloring65 0 1 (by decide)  let T : Set ℕ := {k : ℕ | ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = k ∧ is_gale_counterexample_three V}  have hne : T.Nonempty := ⟨V.card, V, rfl, hV⟩  have hmem : sInf T ∈ T := Nat.sInf_mem hne  have hleast : IsLeast T (sInf T) := ⟨hmem, fun b hb => Nat.sInf_le hb⟩  refine ⟨sInf T, ⟨?_, ?_, hleast⟩, ?_⟩  · have hmem' : ∃ W : Finset (EuclideanSpace ℝ (Fin 3)), W.card = sInf T ∧ is_gale_counterexample_three W := hmem    obtain ⟨W, hWc, hW⟩ := hmem'    exact hWc ▸ op_462_gale_counterexample_card_three_ge_five W hW  · exact (Nat.sInf_le (show V.card ∈ T from ⟨V, rfl, hV⟩)).trans hcard  · intro m hm    exact (hm.2.2).unique hleast
See it in the graphDiscuss this resultChallenge it