AFTD Auto-Formalizing Theoretical Domains

op462_counterexample_of_integer_witness

theoremverified

An exact integer coordinate certificate and a non-four-colorable witness graph produce a finite counterexample with cardinality at most the number of indexed points.

Statement

theorem op462_counterexample_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) : ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card ≤ n ∧ is_gale_counterexample_three V
Source
Helper for arXiv:2610.28828, Theorem 2. Reuses the exact coordinate and coloring certificates recorded in experiments 4045 and 4047; convex hull padding is elementary.
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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

We construct a finite point set V in Euclidean 3-space by rescaling the given integer coordinates P by the integer scale factor S. The upper-bound hypothesis ensures that all pairwise distances in V are at most 1, so the metric diameter of V is at most 1. Meanwhile, the lower-bound hypothesis and the gap condition guarantee that every edge of the witness graph E corresponds to a pair of points at distance strictly greater than the Gale constant gale_sigma_three ≥ gale_sigma_three * diam(V). Consequently, any 4-coloring of the Gale distance graph on V would restrict to a valid 4-coloring of E, contradicting the assumption that E is not 4-colorable. Thus V is a Gale counterexample with cardinality at most n.

  1. Embed each index i ∈ Fin n as a point p(i) = P(i)/S in Euclidean 3-space, noting that S > 0 and S² > 0 in ℝ.

    We work classically and define p(i) by dividing the integer coordinates P(i) by S. Because the integer scale satisfies S > 0, casting to ℝ gives S > 0, and squaring gives S² > 0.

    lines 8–12

    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 all indices i and j, the squared distance dist(p(i), p(j))² equals (∑ₖ (P(i,k) - P(j,k))²) / S².

    By EuclideanSpace.dist_sq_eq, the squared Euclidean distance is the sum over the three coordinates of the squared coordinate differences. Rewriting with p(i)_k = P(i,k)/S and factoring out 1/S² via Finset.sum_div and ring arithmetic establishes the identity.

    lines 13–20

    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. For all indices i and j, dist(p(i), p(j)) ≤ 1.

    Using the squared distance formula and the hypothesis hunit, the integer sum of squared coordinate differences is at most S². Dividing by S² > 0 yields dist(p(i), p(j))² ≤ S²/S² = 1. Non-linear arithmetic with dist_nonneg concludes dist(p(i), p(j)) ≤ 1.

    lines 21–29

    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 constant gale_sigma_three is strictly positive. automation

    Unfolding gale_sigma_three gives √((3 + √3) / 6), which is strictly positive by positivity reasoning.

    lines 30–32

      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 hypothesis hedge guarantees Q ≤ ∑ₖ (P(e.1,k) - P(e.2,k))² for every edge e ∈ E. Dividing by S² gives Q/S² ≤ dist(p(e.1), p(e.2))². Since gale_sigma_three² < Q/S² by hgap, non-linear arithmetic with non-negative distances implies gale_sigma_three < dist(p(e.1), p(e.2)).

    lines 33–41

    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 is defined as the image of p over Finset.univ, and each p(i) belongs to V.

    We set V = Finset.univ.image p. Every p(i) is in V because i is trivially an element of Finset.univ.

    lines 42–44

    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.

    To bound the diameter of V by 1, it suffices to check that any two points x, y ∈ V have distance at most 1. Every point in V is of the form p(i) for some index i, and we already proved all pairwise distances satisfy dist(p(i), p(j)) ≤ 1.

    lines 45–50

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

    The witness edge (a,b) ∈ E provides two points p(a), p(b) ∈ V whose distance exceeds gale_sigma_three > 0. Since V is finite and hence bounded, dist(p(a), p(b)) ≤ diam(V), which forces diam(V) > 0.

    lines 51–53

    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 set V is a Gale counterexample in ℝ³, meaning its diameter is strictly positive and its Gale distance graph cannot be 4-colored.

    We already know diam(V) > 0. If there were a proper 4-coloring c of the Gale distance graph at threshold gale_sigma_three * diam(V), we could pull it back to Fin n via i ↦ c(p(i)). For each edge e ∈ E, dist(p(e.1), p(e.2)) > gale_sigma_three ≥ gale_sigma_three * diam(V) (since diam(V) ≤ 1) and the endpoints are distinct, so (p(e.1), p(e.2)) would be an edge in the Gale distance graph with different colors. This would produce a valid 4-coloring of the witness graph E, contradicting hnotcolor.

    lines 54–66

    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. There exists a Gale counterexample V with |V| ≤ n.

    The set V is a Gale counterexample, and its cardinality is at most |Fin n| = n because the cardinality of an image is at most the cardinality of its domain.

    line 67

    uses Finset.card_image_le

      exact ⟨V, Finset.card_image_le.trans_eq (by simp), hV⟩
sq_pos_of_pos
The square of a strictly positive number is strictly positive: 0 < a → 0 < a^2.
EuclideanSpace.dist_sq_eq
In Euclidean space, the squared distance between two points equals the sum of the squared distances of their coordinates.
Real.dist_eq
The metric distance between real numbers is the absolute difference |x - y|.
sq_abs
The square of an absolute value equals the square of the value: |a|^2 = a^2.
Int.cast_sum
The real coercion of a sum of integers equals the sum of the coerced integers.
Int.cast_pow
The real coercion of an integer power equals the power of the coerced integer: ↑(n^m) = (↑n)^m.
Int.cast_sub
The real coercion of a difference of integers equals the difference of the coerced integers: ↑(m - n) = ↑m - ↑n.
Finset.sum_div
Dividing a finite sum by a scalar equals summing the divided terms: (∑ i, f i) / a = ∑ i, (f i / a).
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree at each point.
div_le_div_of_nonneg_right
Dividing both sides of an inequality by a non-negative scalar preserves the inequality: a ≤ b and 0 ≤ c imply a / c ≤ b / c.
div_self
Any non-zero element divided by itself equals 1: a ≠ 0 → a / a = 1.
dist_nonneg
The metric distance between any two points is non-negative: 0 ≤ dist x y.
List.all_eq_true.mp
If a boolean condition holds for all elements of a list, then it holds for each element in the list.
of_decide_eq_true
If a decidable proposition evaluates to true via `decide`, then the proposition holds.
Finset.mem_image.mpr
An element belongs to the image of a finset under a function if it has a preimage in the finset.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
Metric.diam_le_of_forall_dist_le
If all pairs in a set have distance at most C (with C ≥ 0), then the diameter of the set is at most C.
Finset.mem_image.mp
An element in the image of a finset has a preimage in that finset.
lt_of_lt_of_le
Strict inequality is transitive with weak inequality: a < b and b ≤ c imply a < c.
Metric.dist_le_diam_of_mem
The distance between any two points in a bounded set 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
Applying a function to equal arguments produces equal values: a₁ = a₂ → f a₁ = f a₂.
Subtype.val
Projects an element of a subtype to the underlying carrier type.
lt_of_le_of_lt
Weak inequality is transitive with strict inequality: a ≤ b and b < c imply a < c.
mul_le_of_le_one_right
Multiplying a non-negative number by a factor at most 1 yields at most the original number: 0 ≤ a and b ≤ 1 imply a * b ≤ a.
Finset.card_image_le
The cardinality of the image of a finset under a function is at most the cardinality of the original finset.

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

theorem op462_counterexample_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) : ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card ≤ n ∧ 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  exact ⟨V, Finset.card_image_le.trans_eq (by simp), hV⟩
See it in the graphDiscuss this resultChallenge it