op_462_min_card_le_of_integer_witness
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_threeof 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 tis… - gale_sigma_threeThe real constant
gale_sigma_threeis defined as the square root of (3 + sqrt(3)) / 6.
- is_gale_counterexample_threeA finite subset V of the 3-dimensional Euclidean space
- Used by 2
- op_462_min_gale_counterexample_card_three_range_sixty_fiveThe minimum cardinality
min_gale_counterexample_card_threeof a finite counterexample to Gale's conjecture in dimension 3 satisfies 5 ≤… - op_462_min_gale_counterexample_card_three_le_sixty_fiveThe minimum cardinality
min_gale_counterexample_card_threeof a finite counterexample to Gale's conjecture in dimension 3 is at most 65.
- op_462_min_gale_counterexample_card_three_range_sixty_fiveThe minimum cardinality
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.
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).
uses
sq_pos_of_posclassical 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
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².
uses
EuclideanSpace.dist_sq_eq,Real.dist_eq,sq_abs,Int.cast_sum,Int.cast_pow,Int.cast_sub,Finset.sum_div,Finset.sum_congrhave 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
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.
uses
div_le_div_of_nonneg_right,div_self,dist_nonneghave 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)]
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.
have hsig : 0 < gale_sigma_three := by unfold gale_sigma_three positivity
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.
uses
List.all_eq_true.mp,of_decide_eq_true,div_le_div_of_nonneg_right,dist_nonneghave 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)]
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.
uses
Finset.mem_image.mpr,Finset.mem_univlet 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⟩
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.
uses
Metric.diam_le_of_forall_dist_le,Finset.mem_image.mphave 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
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.
uses
lt_of_lt_of_le,Metric.dist_le_diam_of_memhave 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)
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.
uses
dist_pos.mp,congrArg,Subtype.val,lt_of_le_of_lt,mul_le_of_le_one_righthave 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
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.
uses
Nat.sInf_lehave hmin : min_gale_counterexample_card_three ≤ V.card := by unfold min_gale_counterexample_card_three exact Nat.sInf_le ⟨V, rfl, hV⟩
V.card ≤ n.
The cardinality of the image of Fin n under p is at most the cardinality of Fin n, which is n.
uses
Finset.card_image_le.trans_eqhave hcard : V.card ≤ n := by exact Finset.card_image_le.trans_eq (by simp)
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.
uses
le_transexact 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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