op462_lt101_of_integer_witness
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_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
EuclideanSpace ℝ (Fin 3)is a counterexample to Gale's conjecture in dimension 3…
- min_gale_counterexample_card_threeThe minimum cardinality
- Used by 1
- op_462_min_gale_counterexample_card_three_lt_101Open Problem OP-462: the minimum cardinality
min_gale_counterexample_card_threeof a finite counterexample to Gale's conjecture in…
- op_462_min_gale_counterexample_card_three_lt_101Open Problem OP-462: the minimum cardinality
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.
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).
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
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).
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_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, 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
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).
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. 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).
have hsig : 0 < gale_sigma_three := by unfold gale_sigma_three positivity
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).
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 = 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).
uses
Finset.mem_image.mpr,Finset.mem_univ,Metric.diam_le_of_forall_dist_le,Finset.mem_image.mplet 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
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).
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)
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.
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
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).
uses
Nat.sInf_le,Finset.card_image_lehave 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.
- The positivity of the Gale threshold constant gale_sigma_three = √((3+√3)/6) (Step 4) and the non-linear arithmetic deductions comparing distances and squared distances (Steps 3 and 5) are closed automatically using Lean's positivity and nlinarith tactics.
- The graph coloring condition on V is formulated on the subtype elements representing the vertices of V, requiring coercions and Subtype.val to relate them to points in Euclidean space.
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.
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)