op_462_min_counterexample_card_three_in_range
There exists a unique natural number m in the range 5 ≤ m ≤ 101 such that m is the least element of the set of cardinalities of all finite counterexamples to Gale's conjecture in dimension 3.
Statement
theorem op_462_min_counterexample_card_three_in_range :
∃! m : ℕ, 5 ≤ m ∧ m ≤ 101 ∧
IsLeast {k : ℕ | ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = k ∧ is_gale_counterexample_three V} m- Formalizes
- arXiv:2610.28828 Sec. 5, Question 2
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- 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… - 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… - op462_no_four_coloring65No map from the 65 points to four colors separates every witness edge.
- op462_edges65The 859 witness edges on the 65 indexed points in the primary repository.
- gale_sigma_threeThe real constant
gale_sigma_threeis defined as the square root of (3 + sqrt(3)) / 6. - op_462_gale_counterexample_card_three_ge_fiveFor every finite subset V of
EuclideanSpace ℝ (Fin 3), if V is a counterexample to Gale's conjecture in dimension 3… - op462_coords65_diameter_squared_leEvery squared distance between the scaled integer points is at most 10^34.
- op462_coords65The exact integer coordinates of the 65 indexed points, obtained by multiplying the primary decimal coordinates by 10^17.
- op462_coords65_edges_squared_geEvery witness edge has scaled squared distance at least 7887420401648046950672144846523981.
- gale_distance_graphFor a finite subset V of the 3-dimensional Euclidean space
Read back from the Lean
There exists a unique natural number $m$ such that $5 \le m \le 101$ and $m$ is the least element of the set of cardinalities of all finite subsets $V$ of Euclidean space $\mathbb{R}^3$ that satisfy is_gale_counterexample_three V (that is, $V$ has strictly positive diameter and the graph on $V$ where an edge connects distinct points at distance strictly greater than $\sqrt{(3 + \sqrt{3})/6} \cdot \mathrm{diam}(V)$ cannot be properly 4-colored).
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 theorem shows there is a unique natural number m in the range 5 to 101 that is the minimum cardinality of a 3-dimensional finite counterexample to Gale's conjecture. An explicit 65-vertex configuration with integer coordinates is scaled to produce a counterexample of size at most 65, establishing that the set of counterexample sizes is non-empty and has a minimum m <= 65 <= 101. General theory ensures any counterexample in dimension 3 has at least 5 vertices, and the least element of a set of natural numbers is unique.
Define the scaled points p_i and establish denominator positivity
Define p i = P i / S in R^3 and note that S > 0 implies S^2 > 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
Compute the squared distance between any two points
The squared distance between p i and p j equals the integer sum of coordinate differences squared divided by S^2.
uses
EuclideanSpace.dist_sq_eq,Finset.sum_congr,Finset.sum_div,Int.cast_pow,Int.cast_sub,Int.cast_sum,Real.dist_eq,sq_abshave 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
Pairwise distances are at most 1
Since the integer sum is at most S^2, the squared distance is at most 1, so distance is at most 1.
uses
dist_nonneg,div_le_div_of_nonneg_right,div_selfhave 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)]
gale_sigma_three is strictly positive
Positivity tactic verifies sigma_3 > 0.
have hsig : 0 < gale_sigma_three := by unfold gale_sigma_three positivity
Distances on edges exceed gale_sigma_three
For any edge e in E, the integer sum is at least Q, so dist(p e.1, p e.2)^2 >= Q/S^2 > sigma_3^2, giving dist > sigma_3.
uses
List.all_eq_true.mp,dist_nonneg,div_le_div_of_nonneg_right,of_decide_eq_truehave 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)]
Define the point set V
Let V be the image of Fin n under p, and note every p i is in V.
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
Since all pairwise distances are at most 1, the diameter is at most 1.
uses
Finset.mem_image.mp,Metric.diam_le_of_forall_dist_lehave 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 edge (a,b) in E gives two points at distance > sigma_3 > 0, so the diameter is positive.
uses
Metric.dist_le_diam_of_mem,lt_of_lt_of_lehave 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 in dimension 3
Any 4-coloring of the Gale distance graph would induce a valid 4-coloring of (Fin n, E), contradiction.
uses
Subtype.val,congrArg,dist_pos.mp,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 cardinality of V is at most 101
V has cardinality at most n < 101.
uses
Finset.card_image_le.trans_eqhave hcard : V.card ≤ n := Finset.card_image_le.trans_eq (by simp) exact ⟨V, by omega, hV⟩
Verify the numerical gap for the 65-vertex configuration
Check sigma_3^2 < Q/S^2 for the chosen constants.
uses
Real.sq_sqrtclassical have hgap : gale_sigma_three^2 < ((7887420401648046950672144846523981 : ℤ) : ℝ) / ((10^17 : ℤ) : ℝ)^2 := by unfold gale_sigma_three rw [Real.sq_sqrt (by positivity)] num_ineq
Obtain a concrete counterexample with at most 65 vertices
Apply the witness lemma to the 65-vertex graph and coordinate data.
uses
op462_coords65,op462_coords65_diameter_squared_le,op462_coords65_edges_squared_ge,op462_edges65,op462_no_four_coloring65,op_462_min_counterexample_card_three_in_range_witnessobtain ⟨V, hcard, hV⟩ := op_462_min_counterexample_card_three_in_range_witness 65 (by decide) (10^17) 7887420401648046950672144846523981 (by norm_num) op462_coords65 op462_edges65 op462_coords65_diameter_squared_le op462_coords65_edges_squared_ge hgap op462_no_four_coloring65 0 1 (by decide)
Define T and obtain its minimum element
Let T be the set of cardinalities of Gale counterexamples. Since V witnesses T is nonempty, T has a least element sInf T.
uses
Nat.sInf_le,Nat.sInf_memlet T : Set ℕ := {k : ℕ | ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = k ∧ is_gale_counterexample_three V} have hne : T.Nonempty := ⟨V.card, V, rfl, hV⟩ have hmem : sInf T ∈ T := Nat.sInf_mem hne have hleast : IsLeast T (sInf T) := ⟨hmem, fun b hb => Nat.sInf_le hb⟩
Show 5 <= sInf T <= 101
Any 3D counterexample has cardinality at least 5, and sInf T <= |V| <= 101.
uses
Nat.sInf_le,op_462_gale_counterexample_card_three_ge_fiverefine ⟨sInf T, ⟨?_, ?_, hleast⟩, ?_⟩ · have hmem' : ∃ W : Finset (EuclideanSpace ℝ (Fin 3)), W.card = sInf T ∧ is_gale_counterexample_three W := hmem obtain ⟨W, hWc, hW⟩ := hmem' exact hWc ▸ op_462_gale_counterexample_card_three_ge_five W hW · exact (Nat.sInf_le (show V.card ∈ T from ⟨V, rfl, hV⟩)).trans hcard
Uniqueness of the minimum
The least element of a partially ordered set is unique.
uses
IsLeast.unique· intro m hm exact (hm.2.2).unique hleast
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.
lemma op_462_min_counterexample_card_three_in_range_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) : ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card ≤ 101 ∧ 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 have hcard : V.card ≤ n := Finset.card_image_le.trans_eq (by simp) exact ⟨V, by omega, hV⟩/-- Open Problem OP-462: there is a unique natural number m between 5 and 101 that is the minimum cardinality of a finite counterexample to Gale's conjecture in dimension 3. -/theorem op_462_min_counterexample_card_three_in_range : ∃! m : ℕ, 5 ≤ m ∧ m ≤ 101 ∧ IsLeast {k : ℕ | ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = k ∧ is_gale_counterexample_three V} m := by classical have hgap : gale_sigma_three^2 < ((7887420401648046950672144846523981 : ℤ) : ℝ) / ((10^17 : ℤ) : ℝ)^2 := by unfold gale_sigma_three rw [Real.sq_sqrt (by positivity)] num_ineq obtain ⟨V, hcard, hV⟩ := op_462_min_counterexample_card_three_in_range_witness 65 (by decide) (10^17) 7887420401648046950672144846523981 (by norm_num) op462_coords65 op462_edges65 op462_coords65_diameter_squared_le op462_coords65_edges_squared_ge hgap op462_no_four_coloring65 0 1 (by decide) let T : Set ℕ := {k : ℕ | ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = k ∧ is_gale_counterexample_three V} have hne : T.Nonempty := ⟨V.card, V, rfl, hV⟩ have hmem : sInf T ∈ T := Nat.sInf_mem hne have hleast : IsLeast T (sInf T) := ⟨hmem, fun b hb => Nat.sInf_le hb⟩ refine ⟨sInf T, ⟨?_, ?_, hleast⟩, ?_⟩ · have hmem' : ∃ W : Finset (EuclideanSpace ℝ (Fin 3)), W.card = sInf T ∧ is_gale_counterexample_three W := hmem obtain ⟨W, hWc, hW⟩ := hmem' exact hWc ▸ op_462_gale_counterexample_card_three_ge_five W hW · exact (Nat.sInf_le (show V.card ∈ T from ⟨V, rfl, hV⟩)).trans hcard · intro m hm exact (hm.2.2).unique hleast