AFTD Auto-Formalizing Theoretical Domains

op_462_min_card_le_of_integer_witness

theoremverifiedoriginal

For any positive integer scale S, integer threshold Q, and n points in ℤ³ with unit diameter bound and edge list E at squared distance at least Q whose edge graph is not 4-colorable and with squared gap exceeding gale_sigma_three squared, the minimum cardinality min_gale_counterexample_card_three is at most n.

Statement

theorem op_462_min_card_le_of_integer_witness
    (n : ℕ) (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) : min_gale_counterexample_card_three ≤ n
Related work
arXiv:2610.28828 Sec. 3
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • min_gale_counterexample_card_threeThe minimum cardinality min_gale_counterexample_card_three of a finite counterexample to Gale's conjecture in dimension 3 is the infimum…
  • 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…
  • gale_sigma_threeThe real constant gale_sigma_three is defined as the square root of (3 + sqrt(3)) / 6.
Used by 2

Read back from the Lean

Given: - a natural number n, - integers S and Q with 0 < S, - a point assignment P : Fin n → Fin 3 → ℤ (embedding n vertices into ℤ³), - an edge list E : List (Fin n × Fin n), - a hypothesis hunit that for all i, j : Fin n, the squared Euclidean distance between P i and P j is at most S^2 (i.e., ∑ k : Fin 3, (P i k - P j k)^2 ≤ S^2), - a hypothesis hedge that every edge e ∈ E has squared Euclidean distance at least Q (i.e., E.all (fun e => decide (Q ≤ ∑ k : Fin 3, (P e.1 k - P e.2 k)^2)) = true), - a hypothesis hgap that gale_sigma_three^2 < (Q : ℝ) / (S : ℝ)^2, - a hypothesis hnotcolor that the graph (Fin n, E) is not 4-colorable (i.e., for every coloring c : Fin n → Fin 4, there exists some e ∈ E such that c e.1 = c e.2), - indices a, b : Fin n with (a, b) ∈ E (guaranteeing E is non-empty), the theorem asserts that min_gale_counterexample_card_three ≤ n, where min_gale_counterexample_card_three is the minimum cardinality of a finite subset of 3-dimensional Euclidean space that forms a Gale counterexample.

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 proof shows that an integer coordinate certificate bounds the minimum cardinality of a 3-dimensional Gale counterexample by n. It constructs a candidate point set V in ℝ³ by scaling the n integer coordinates by 1/S, showing that the pairwise distances are at most 1, so the metric diameter is at most 1. The edge certificate and gap condition guarantee that each edge in E has scaled distance strictly exceeding the Gale threshold σ, which is at least σ · diam(V), while the existence of an edge ensures the diameter is strictly positive. Consequently, any 4-coloring of the Gale distance graph on V would produce a valid 4-coloring of the edge graph, contradicting the non-colorability hypothesis; thus V is a Gale counterexample whose cardinality is at most n.

  1. The scaled points p(i) = P(i)/S ∈ ℝ³ are defined, with S > 0 and S² > 0 in ℝ.

    Working classically, we define p : Fin n → ℝ³ by scaling each integer vector P(i) by 1/S. The integer hypothesis 0 < S casts to 0 < S in ℝ (hSreal), from which sq_pos_of_pos establishes 0 < S² (hden).

    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. For any indices i and j, dist(p(i), p(j))² = (∑ₖ (P(i,k) - P(j,k))²) / S².

    By EuclideanSpace.dist_sq_eq, the squared distance is the sum of coordinate squared differences. Expanding the definition of p, casting integers to ℝ, and pulling the factor 1/S² out of the sum, ring arithmetic verifies that coordinatewise (P(i,k)/S - P(j,k)/S)² = (P(i,k) - P(j,k))² / S².

    lines 15–22

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

      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. Every pair of points satisfies dist(p(i), p(j)) ≤ 1.

    The unit diameter bound hunit guarantees ∑ₖ (P(i,k) - P(j,k))² ≤ S². Dividing by S² > 0 gives dist(p(i), p(j))² ≤ S² / S² = 1. Since distance is non-negative (dist_nonneg), non-linear arithmetic (nlinarith) concludes dist(p(i), p(j)) ≤ 1.

    lines 23–31

    uses div_le_div_of_nonneg_right, div_self, dist_nonneg

      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. The Gale threshold constant gale_sigma_three is strictly positive.

    Unfolding the definition gale_sigma_three = √((3 + √3)/6), the positivity tactic closes the goal because the radicand is strictly positive.

    lines 32–34

      have hsig : 0 < gale_sigma_three := by
        unfold gale_sigma_three
        positivity
  5. For every edge e ∈ E, dist(p(e.1), p(e.2)) > gale_sigma_three.

    The certificate hedge ensures that all edges e ∈ E satisfy Q ≤ ∑ₖ (P(e.1,k) - P(e.2,k))². Dividing by S² gives Q/S² ≤ dist(p(e.1), p(e.2))². Combining this with the strict hypothesis gale_sigma_three² < Q/S² and non-negativity of distance, non-linear arithmetic (nlinarith) yields dist(p(e.1), p(e.2)) > gale_sigma_three.

    lines 35–43

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

      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. The finite set V ⊂ ℝ³ is the image of p, and each p(i) belongs to V.

    We define V as the image of the universal finset Finset.univ under p. Membership of each p(i) in V is verified directly by exhibiting the preimage i.

    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 metric diameter of V is at most 1.

    Every point in V is of the form p(i). Since dist(p(i), p(j)) ≤ 1 for all i, j, Metric.diam_le_of_forall_dist_le implies diam(V) ≤ 1.

    lines 47–52

    uses Metric.diam_le_of_forall_dist_le, Finset.mem_image.mp

      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 metric diameter of V is strictly positive.

    The witness edge (a, b) ∈ E provides two points in V whose distance satisfies dist(p(a), p(b)) > gale_sigma_three > 0. Since dist(p(a), p(b)) ≤ diam(V) for points in a bounded set, diam(V) is strictly positive.

    lines 53–55

    uses lt_of_lt_of_le, Metric.dist_le_diam_of_mem

      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. The point set V is a Gale counterexample in ℝ³ (is_gale_counterexample_three V).

    A Gale counterexample requires diam(V) > 0 (established above) and non-4-colorability of its Gale distance graph at threshold gale_sigma_three * diam(V). Given any 4-coloring c of this graph, restricting to indices i ↦ c(p(i)) would 4-color the edge list E: for any e ∈ E, dist(p(e.1), p(e.2)) > gale_sigma_three ≥ gale_sigma_three * diam(V) (since diam(V) ≤ 1) and dist > 0 implies p(e.1) ≠ p(e.2), so e is an edge in the Gale graph. This contradicts hnotcolor.

    lines 56–68

    uses dist_pos.mp, congrArg, Subtype.val, 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. min_gale_counterexample_card_three ≤ V.card.

    The minimum counterexample cardinality is defined as the infimum of cardinalities of all Gale counterexamples. Since V is such a counterexample, Nat.sInf_le bounds the infimum by V.card.

    lines 69–71

    uses Nat.sInf_le

      have hmin : min_gale_counterexample_card_three ≤ V.card := by
        unfold min_gale_counterexample_card_three
        exact Nat.sInf_le ⟨V, rfl, hV⟩
  11. V.card ≤ n.

    The cardinality of the image of Fin n under p is at most the cardinality of Fin n, which is n.

    lines 72–73

    uses Finset.card_image_le.trans_eq

      have hcard : V.card ≤ n := by
        exact Finset.card_image_le.trans_eq (by simp)
  12. min_gale_counterexample_card_three ≤ n.

    Combining min_gale_counterexample_card_three ≤ V.card and V.card ≤ n by transitivity of inequality (le_trans) completes the proof.

    line 74

    uses le_trans

      exact le_trans hmin hcard
sq_pos_of_pos
If a > 0 in a partially ordered monoid with zero, then a² > 0.
EuclideanSpace.dist_sq_eq
The squared distance between two points in a Euclidean space equals the sum of the squared distances of their coordinates.
Real.dist_eq
The distance between two real numbers x and y is |x - y|.
sq_abs
For any real number a, |a|² = a².
Int.cast_sum
The cast of a finite sum of integers is the sum of the cast integers.
Int.cast_pow
The cast of an integer power nᵐ is the m-th power of the cast integer.
Int.cast_sub
The cast of an integer difference m - n is the difference of the casts.
Finset.sum_div
Dividing a sum by a scalar equals summing the terms divided by that scalar.
Finset.sum_congr
If two sums have identical index sets and their terms agree on all elements, the sums are equal.
div_le_div_of_nonneg_right
If a ≤ b and c ≥ 0, then a / c ≤ b / c.
div_self
For any nonzero element a, a / a = 1.
dist_nonneg
The distance between any two points in a metric space is non-negative.
List.all_eq_true.mp
If List.all evaluates to true for a list, the predicate holds for every element in the list.
of_decide_eq_true
If decide p = true, then the proposition p holds.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
Finset.mem_image.mpr
An element is in the image of a finset under f if it has a preimage in the finset.
Finset.mem_image.mp
If an element is in the image of a finset under f, then it has a preimage in the finset.
Metric.diam_le_of_forall_dist_le
If 0 ≤ C and all pairwise distances in a set are at most C, the diameter of the set is at most C.
lt_of_lt_of_le
If a < b and b ≤ c, then a < c.
Metric.dist_le_diam_of_mem
For points x, y in a bounded set, the distance between them is at most the diameter of the set.
dist_pos.mp
If the distance between two points is strictly positive, the points are not equal.
congrArg
If a₁ = a₂, then f(a₁) = f(a₂).
Subtype.val
The canonical projection from a subtype to its underlying carrier type.
lt_of_le_of_lt
If a ≤ b and b < c, then a < c.
mul_le_of_le_one_right
If 0 ≤ a and b ≤ 1, then a * b ≤ a.
Nat.sInf_le
For any set of natural numbers s, if m ∈ s then the infimum of s is at most m.
Finset.card_image_le.trans_eq
The cardinality of the image f(s) is at most any integer c known to equal |s|.
le_trans
If a ≤ b and b ≤ c, then a ≤ c.

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

/-- An integer coordinate certificate on n indexed points with unit diameter, strict threshold gap, and non-four-colorable edge graph implies min_gale_counterexample_card_three ≤ n. -/theorem op_462_min_card_le_of_integer_witness    (n : ℕ) (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) : min_gale_counterexample_card_three ≤ n := 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 hmin : min_gale_counterexample_card_three ≤ V.card := by    unfold min_gale_counterexample_card_three    exact Nat.sInf_le ⟨V, rfl, hV⟩  have hcard : V.card ≤ n := by    exact Finset.card_image_le.trans_eq (by simp)  exact le_trans hmin hcard
See it in the graphDiscuss this resultChallenge it