AFTD Auto-Formalizing Theoretical Domains

op462_lt101_of_integer_witness

theoremverified

An integer coordinate certificate on fewer than 101 indexed points, with unit diameter bound, a strict threshold gap and a non-four-colorable edge graph, implies the strict-101 bound.

Statement

theorem op462_lt101_of_integer_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) : min_gale_counterexample_card_three < 101
Source
Helper formalizing the known 65-point example accompanying arXiv:2610.28828, https://github.com/vsvor/Gale-conjecture/tree/bd6dc9594c589791f599a0bf4685841bcb5b4486/best_known/3d_65p_088808. Exact data and independent computation: experiment 4045. Trimmed LRAT dependency graph: experiment 4047.
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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.
  • 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…
Used by 1

The proof, explained

The theorem deduces that the minimal cardinality of a Gale counterexample in ℝ³ is strictly less than 101 from a discrete certificate on n < 101 points. Scaling the integer coordinates by 1/S embeds the configuration into ℝ³ as a finite point set V with diameter at most 1, with an edge in E witnessing that the diameter is strictly positive. Every edge of E has Euclidean distance exceeding gale_sigma_three ≥ gale_sigma_three · diam(V), so any 4-coloring of V's Gale distance graph would induce a proper 4-coloring of E. This contradicts the non-colorability hypothesis, proving that V is a Gale counterexample whose cardinality |V| ≤ n < 101 bounds the minimal counterexample size.

  1. Define the scaled Euclidean configuration p(i) = P(i)/S in ℝ³ and establish that S > 0 and S² > 0 in ℝ.

    Using classical logic (line 11), each integer coordinate vector P(i) is divided by S to define a point p(i) in the 3-dimensional Euclidean space ℝ³ (lines 12–13). The integer positivity hypothesis S > 0 is cast to the real numbers (line 14), which ensures that the squared denominator S² is strictly positive by sq_pos_of_pos (line 15).

    lines 11–15

    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. The squared Euclidean distance between p(i) and p(j) equals (∑ₖ (P(i)ₖ - P(j)ₖ)²) / S².

    The squared distance between p(i) and p(j) in Euclidean space expands into a sum of squared coordinate differences via EuclideanSpace.dist_sq_eq (line 18). Simplifying this expression unfolds the embedding p with PiLp.toLp_apply, rewrites the 1D real distance via Real.dist_eq and sq_abs, casts integer sums, powers, and differences to real numbers using Int.cast_sum, Int.cast_pow, and Int.cast_sub, and pulls the common divisor S² out of the sum using Finset.sum_div (lines 19–20). Applying congruence of finite sums (Finset.sum_congr) and polynomial ring arithmetic (ring) verifies that each coordinate summand matches the right-hand side (lines 21–23).

    lines 16–23

    uses EuclideanSpace.dist_sq_eq, PiLp.toLp_apply, 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, PiLp.toLp_apply, 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. All pairwise Euclidean distances satisfy dist(p(i), p(j)) ≤ 1.

    Using the squared distance formula hdistsq, the integer bound ∑ₖ (P(i)ₖ - P(j)ₖ)² ≤ S² from hunit is divided by S² > 0 via div_le_div_of_nonneg_right, showing that dist(p(i), p(j))² ≤ S² / S² = 1 via div_self (lines 25–31). Since distances are non-negative (dist_nonneg), non-linear arithmetic (nlinarith) concludes that dist(p(i), p(j)) ≤ 1 (line 32).

    lines 24–32

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

    Unfolding the definition gale_sigma_three = √((3 + √3) / 6) (line 34), automated positivity reasoning (positivity) establishes that this constant is strictly positive (line 35).

    lines 33–35

      have hsig : 0 < gale_sigma_three := by
        unfold gale_sigma_three
        positivity
  5. For every edge e ∈ E, the distance dist(p(e.1), p(e.2)) is strictly greater than gale_sigma_three.

    For any edge e ∈ E, the boolean hypothesis hedge implies by List.all_eq_true.mp and of_decide_eq_true that Q ≤ ∑ₖ (P(e.1)ₖ - P(e.2)ₖ)² (lines 38–39). Dividing by S² > 0 via div_le_div_of_nonneg_right and rewriting with hdistsq gives Q / S² ≤ dist(p(e.1), p(e.2))² (lines 40–43). Since gale_sigma_three² < Q / S² by hgap and distances are non-negative (dist_nonneg), non-linear arithmetic (nlinarith) deduces that gale_sigma_three < dist(p(e.1), p(e.2)) (line 44).

    lines 36–44

    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 point set V = p(Fin n) has diameter diam(V) ≤ 1.

    The set V ⊂ ℝ³ is defined as the image of the universal index set under p (line 45), so each point p(i) belongs to V by Finset.mem_image.mpr and Finset.mem_univ (lines 46–47). Applying Metric.diam_le_of_forall_dist_le reduces the diameter bound to showing that all points x, y ∈ V satisfy dist(x, y) ≤ 1 (lines 48–49). Expressing x and y as images p(i) and p(j) via Finset.mem_image.mp (lines 51–52), the pairwise distance bound dist(p(i), p(j)) ≤ 1 proved in hdistle completes the step (line 53).

    lines 45–53

    uses Finset.mem_image.mpr, Finset.mem_univ, Metric.diam_le_of_forall_dist_le, Finset.mem_image.mp

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

    The assumed edge (a, b) ∈ E provides two points with dist(p(a), p(b)) > gale_sigma_three > 0. Since p(a), p(b) ∈ V and the finite set V is bounded, Metric.dist_le_diam_of_mem gives dist(p(a), p(b)) ≤ diam(V) (line 56). Transitivity of strict inequality via lt_of_lt_of_le then shows that 0 < diam(V) (line 55).

    lines 54–56

    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)
  8. V is a Gale counterexample: it has positive diameter and its Gale distance graph is not 4-colorable.

    By definition, is_gale_counterexample_three V requires diam(V) > 0 (proved in hdiampos) and the non-existence of a valid 4-coloring of its Gale distance graph (lines 57–58). Suppose, for contradiction, that a 4-coloring c exists (line 59); this induces a 4-coloring on the index set Fin n by i ↦ c(p(i)) (line 60). For any edge e ∈ E, the distance dist(p(e.1), p(e.2)) exceeds gale_sigma_three, which is at least gale_sigma_three * diam(V) since diam(V) ≤ 1 (mul_le_of_le_one_right and lt_of_le_of_lt, line 69). Since this distance is positive, the endpoints are distinct (dist_pos.mp, line 64), meaning their subtype representations in V are distinct via congrArg Subtype.val (line 68). Therefore, the endpoints form an edge in the Gale graph, so c forces distinct colors on e.1 and e.2 (line 62). This contradicts the hypothesis hnotcolor that E admits no proper 4-coloring.

    lines 57–69

    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
  9. The minimal cardinality of a Gale counterexample in ℝ³ is strictly less than 101.

    Unfolding the definition of min_gale_counterexample_card_three as the infimum of cardinalities of all Gale counterexamples (line 71), V witnesses that this infimum is at most |V| via Nat.sInf_le (line 72). The cardinality |V| is bounded by the number of indices n via Finset.card_image_le (lines 73–74). Chaining the inequalities min_gale_counterexample_card_three ≤ |V| ≤ n < 101 closes the theorem (line 75).

    lines 70–75

    uses Nat.sInf_le, Finset.card_image_le

      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 hmin.trans_lt (hcard.trans_lt hn)
sq_pos_of_pos
The square of a strictly positive element is strictly positive.
EuclideanSpace.dist_sq_eq
In Euclidean space, the squared distance between two points equals the sum of the squared distances between their individual coordinates.
PiLp.toLp_apply
Evaluating the coordinate of a vector in an Lp space yields the coordinate value of the underlying function.
Real.dist_eq
The Euclidean distance between two real numbers equals the absolute value of their difference.
sq_abs
The square of the absolute value of a real number equals the square of the number itself.
Int.cast_sum
The canonical injection from integers into a ring distributes over finite sums.
Int.cast_pow
The canonical injection from integers into a ring preserves natural powers.
Int.cast_sub
The canonical injection from integers into a ring preserves subtraction.
Finset.sum_div
Dividing a finite sum by a scalar equals the sum of the divided terms.
Finset.sum_congr
Two finite sums are equal if their index sets are identical and their summands agree at every index.
div_le_div_of_nonneg_right
Dividing both sides of an inequality by a non-negative number preserves the inequality.
div_self
Any non-zero element divided by itself equals 1.
dist_nonneg
The distance between any two points in a metric space is non-negative.
List.all_eq_true.mp
If a boolean predicate holds for all elements of a list, then it holds for each member of that list.
of_decide_eq_true
If the decidable boolean check of a proposition evaluates to true, then the proposition holds.
Finset.mem_image.mpr
An element is in the image of a finite set under a map if there exists a preimage in the set mapping to it.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set of that type.
Metric.diam_le_of_forall_dist_le
If all pairwise distances between points in a set are bounded by C ≥ 0, then the diameter of the set is at most C.
Finset.mem_image.mp
If an element belongs to the image of a finite set under a map, then it has a preimage in that set.
lt_of_lt_of_le
If a < b and b ≤ c, then a < c.
Metric.dist_le_diam_of_mem
In a bounded metric space, the distance between any two points of a set is at most the diameter of the set.
dist_pos.mp
Two points whose distance is strictly positive are not equal.
congrArg
Applying a function to equal arguments produces equal results.
Subtype.val
The canonical projection that extracts the underlying value from an element of a subtype.
lt_of_le_of_lt
If a ≤ b and b < c, then a < c.
mul_le_of_le_one_right
Multiplying a non-negative real number by a factor at most 1 yields a result at most the original number.
Nat.sInf_le
The infimum of a set of natural numbers is less than or equal to any element in the set.
Finset.card_image_le
The cardinality of the image of a finite set under a function is at most the cardinality of the original finite set.

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

open scoped BigOperatorstheorem op462_lt101_of_integer_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) : min_gale_counterexample_card_three < 101 := 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, PiLp.toLp_apply, 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 hmin.trans_lt (hcard.trans_lt hn)
See it in the graphDiscuss this resultChallenge it