op462_counterexample_of_integer_witness
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 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
EuclideanSpace ℝ (Fin 3)is a counterexample to Gale's conjecture in dimension 3…
- gale_distance_graphFor a finite subset V of the 3-dimensional Euclidean space
- Used by 1
- op_462_gale_counterexample_card_three_le_101There exists a finite subset V of
EuclideanSpace ℝ (Fin 3)with cardinality 101 that is a counterexample to Gale's conjecture in…
- op_462_gale_counterexample_card_three_le_101There exists a finite subset V of
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.
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.
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 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.
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
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.
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 constant gale_sigma_three is strictly positive. automation
Unfolding gale_sigma_three gives √((3 + √3) / 6), which is strictly positive by positivity reasoning.
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 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)).
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 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.
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 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.
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 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.
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 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.
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
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.
uses
Finset.card_image_leexact ⟨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.
- The embedding into Euclidean 3-space uses Mathlib's `EuclideanSpace ℝ (Fin 3)`, defined as `WithLp 2 (Fin 3 → ℝ)`.
- A Gale counterexample `is_gale_counterexample_three V` requires both that `Metric.diam V > 0` and that the distance graph with edges at distance strictly greater than `gale_sigma_three * Metric.diam V` has no valid 4-coloring.
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.
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⟩