op462_counterexample_extend_card
A finite three-dimensional counterexample can be enlarged to any prescribed larger finite cardinality by adding points inside its convex hull.
Statement
theorem op462_counterexample_extend_card (V : Finset (EuclideanSpace ℝ (Fin 3))) (hV : is_gale_counterexample_three V)
(n : ℕ) (hn : V.card ≤ n) :
∃ W : Finset (EuclideanSpace ℝ (Fin 3)), W.card = n ∧ is_gale_counterexample_three W- 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
To enlarge a finite counterexample $V \subset \mathbb{R}^3$ to a prescribed cardinality $n \ge |V|$, we add $n - |V|$ points chosen from the convex hull of $V$ outside $V$ itself. The convex hull is infinite because $V$ has positive diameter (hence at least two points) and convex sets in Euclidean space are connected. Adding points from the convex hull does not change the diameter of the set, so all original edges of the Gale distance graph are preserved. Any 4-coloring of the enlarged set would therefore restrict to a valid 4-coloring of $V$, which is impossible.
The convex hull of $V$ is an infinite set.
Because $V$ is a Gale counterexample, its diameter is strictly positive, so $V$ cannot be a subsingleton and must contain at least two distinct points. Its convex hull contains $V$, hence is also nontrivial. In Euclidean space, the convex hull is convex and therefore preconnected; any nontrivial preconnected set is infinite.
uses
Set.not_subsingleton_iff.mp,Metric.diam_subsingleton,convex_convexHull,subset_convexHullclassical have hnontriv : (V : Set (EuclideanSpace ℝ (Fin 3))).Nontrivial := Set.not_subsingleton_iff.mp (fun hs => hV.1.ne' (Metric.diam_subsingleton hs)) have hinf : (convexHull ℝ (V : Set (EuclideanSpace ℝ (Fin 3)))).Infinite := (convex_convexHull ℝ _).isPreconnected.infinite_of_nontrivial (hnontriv.mono (subset_convexHull ℝ _))
There exists a finite set $U$ of $n - |V|$ points in the convex hull of $V$ that is disjoint from $V$.
Removing the finite set $V$ from the infinite set $\operatorname{conv}(V)$ leaves an infinite set, which must contain a finite subset $U$ of size $n - |V|$. Because every element of $U$ belongs to $\operatorname{conv}(V) \setminus V$, the sets $V$ and $U$ share no points.
uses
exists_subset_card_eq,Finset.disjoint_leftobtain ⟨U, hU, hcardU⟩ := (hinf.sdiff V.finite_toSet).exists_subset_card_eq (n - V.card) have hdisj : Disjoint V U := by rw [Finset.disjoint_left] intro x hxV hxU exact (hU hxU).2 hxV
The union $V \cup U$ is contained in the convex hull of $V$.
Every point of $V \cup U$ is either in $V \subseteq \operatorname{conv}(V)$ or in $U \subseteq \operatorname{conv}(V) \setminus V \subseteq \operatorname{conv}(V)$.
uses
Finset.mem_union.mp,subset_convexHullhave hsub : ((V ∪ U : Finset _) : Set (EuclideanSpace ℝ (Fin 3))) ⊆ convexHull ℝ (V : Set (EuclideanSpace ℝ (Fin 3))) := by intro x hx rcases Finset.mem_union.mp hx with hx | hx · exact subset_convexHull ℝ _ hx · exact (hU hx).1
The diameter of $V \cup U$ is equal to the diameter of $V$.
We show equality by mutual inequality. On the one hand, $V \cup U \subseteq \operatorname{conv}(V)$, and since $V$ is finite (hence bounded), $\operatorname{diam}(V \cup U) \le \operatorname{diam}(\operatorname{conv}(V)) = \operatorname{diam}(V)$. On the other hand, $V \subseteq V \cup U$ implies $\operatorname{diam}(V) \le \operatorname{diam}(V \cup U)$.
uses
le_antisymm,Metric.diam_mono,isBounded_convexHull.mpr,trans_eq,convexHull_diam,Finset.mem_union_lefthave hdiam : Metric.diam ((V ∪ U : Finset _) : Set (EuclideanSpace ℝ (Fin 3))) = Metric.diam (V : Set (EuclideanSpace ℝ (Fin 3))) := by apply le_antisymm · exact (Metric.diam_mono hsub (isBounded_convexHull.mpr V.finite_toSet.isBounded)).trans_eq (convexHull_diam _) · exact Metric.diam_mono (by intro x hx; exact Finset.mem_union_left U hx) (V ∪ U).finite_toSet.isBounded
The candidate set $W = V \cup U$ has cardinality $n$.
We choose $W = V \cup U$. Since $V$ and $U$ are disjoint, $|V \cup U| = |V| + |U| = |V| + (n - |V|) = n$, where the arithmetic simplification holds because $|V| \le n$.
uses
Finset.card_union_of_disjoint,Nat.add_sub_of_lerefine ⟨V ∪ U, ?_, ?_⟩ · rw [Finset.card_union_of_disjoint hdisj, hcardU, Nat.add_sub_of_le hn]
The enlarged set $V \cup U$ is also a Gale counterexample.
First, $\operatorname{diam}(V \cup U) = \operatorname{diam}(V) > 0$. Second, suppose for contradiction that the Gale distance graph of $V \cup U$ has a 4-coloring $c$. Restricting $c$ along the canonical injection $V \hookrightarrow V \cup U$ would define a 4-coloring of $V$: if two vertices $x, y \in V$ are adjacent in the Gale graph of $V$, they are distinct and satisfy $\operatorname{dist}(x, y) > \sigma_3 \operatorname{diam}(V) = \sigma_3 \operatorname{diam}(V \cup U)$, so they are also adjacent in the Gale graph of $V \cup U$ and must receive distinct colors $c(x) \ne c(y)$. This restriction contradicts the fact that $V$ is not 4-colorable.
uses
SimpleGraph.Coloring.mk,Finset.mem_union_left,Subtype.ext,congrArg· refine ⟨by simpa only [hdiam] using hV.1, ?_⟩ rintro ⟨c⟩ apply hV.2 refine ⟨SimpleGraph.Coloring.mk (fun x => c ⟨x.val, Finset.mem_union_left U x.property⟩) ?_⟩ intro x y hxy apply c.valid change (⟨x.val, Finset.mem_union_left U x.property⟩ : ↥(V ∪ U)) ≠ ⟨y.val, Finset.mem_union_left U y.property⟩ ∧ _ constructor · intro heq exact hxy.1 (Subtype.ext (congrArg (fun z : ↥(V ∪ U) => z.val) heq)) · simpa only [hdiam] using hxy.2
Set.not_subsingleton_iff.mp- A set that is not a subsingleton is nontrivial, meaning it contains at least two distinct elements.
Metric.diam_subsingleton- A subsingleton set in a metric space has diameter zero.
convex_convexHull- The convex hull of any set in a real vector space is convex.
subset_convexHull- Every set is a subset of its convex hull.
exists_subset_card_eq- Any infinite set contains a finite subset of any prescribed cardinality.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_union.mp- If an element belongs to a union of two finite sets, it belongs to the first or to the second.
le_antisymm- If $a \le b$ and $b \le a$ in a partial order, then $a = b$.
Metric.diam_mono- If $s \subseteq t$ and $t$ is bounded, the diameter of $s$ is at most the diameter of $t$.
isBounded_convexHull.mpr- The convex hull of a bounded set is bounded.
trans_eq- If $a \le b$ and $b = c$, then $a \le c$.
convexHull_diam- In a real normed space, the diameter of the convex hull of a set equals the diameter of the set itself.
Finset.mem_union_left- An element of a finite set $s$ is also an element of the union $s \cup t$.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Nat.add_sub_of_le- For natural numbers with $a \le b$, $a + (b - a) = b$.
SimpleGraph.Coloring.mk- Constructs a proper graph coloring from a vertex color assignment and a proof that adjacent vertices receive distinct colors.
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
congrArg- A function applied to equal arguments yields equal values.
- The theorem relies on the Gale distance graph threshold $\sigma_3 = \sqrt{(3 + \sqrt{3})/6}$. Adding points from the convex hull preserves the diameter and cannot create edges between points in $V$ that were not already present, ensuring the obstruction to 4-colorability is inherited.
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_extend_card (V : Finset (EuclideanSpace ℝ (Fin 3))) (hV : is_gale_counterexample_three V) (n : ℕ) (hn : V.card ≤ n) : ∃ W : Finset (EuclideanSpace ℝ (Fin 3)), W.card = n ∧ is_gale_counterexample_three W := by classical have hnontriv : (V : Set (EuclideanSpace ℝ (Fin 3))).Nontrivial := Set.not_subsingleton_iff.mp (fun hs => hV.1.ne' (Metric.diam_subsingleton hs)) have hinf : (convexHull ℝ (V : Set (EuclideanSpace ℝ (Fin 3)))).Infinite := (convex_convexHull ℝ _).isPreconnected.infinite_of_nontrivial (hnontriv.mono (subset_convexHull ℝ _)) obtain ⟨U, hU, hcardU⟩ := (hinf.sdiff V.finite_toSet).exists_subset_card_eq (n - V.card) have hdisj : Disjoint V U := by rw [Finset.disjoint_left] intro x hxV hxU exact (hU hxU).2 hxV have hsub : ((V ∪ U : Finset _) : Set (EuclideanSpace ℝ (Fin 3))) ⊆ convexHull ℝ (V : Set (EuclideanSpace ℝ (Fin 3))) := by intro x hx rcases Finset.mem_union.mp hx with hx | hx · exact subset_convexHull ℝ _ hx · exact (hU hx).1 have hdiam : Metric.diam ((V ∪ U : Finset _) : Set (EuclideanSpace ℝ (Fin 3))) = Metric.diam (V : Set (EuclideanSpace ℝ (Fin 3))) := by apply le_antisymm · exact (Metric.diam_mono hsub (isBounded_convexHull.mpr V.finite_toSet.isBounded)).trans_eq (convexHull_diam _) · exact Metric.diam_mono (by intro x hx; exact Finset.mem_union_left U hx) (V ∪ U).finite_toSet.isBounded refine ⟨V ∪ U, ?_, ?_⟩ · rw [Finset.card_union_of_disjoint hdisj, hcardU, Nat.add_sub_of_le hn] · refine ⟨by simpa only [hdiam] using hV.1, ?_⟩ rintro ⟨c⟩ apply hV.2 refine ⟨SimpleGraph.Coloring.mk (fun x => c ⟨x.val, Finset.mem_union_left U x.property⟩) ?_⟩ intro x y hxy apply c.valid change (⟨x.val, Finset.mem_union_left U x.property⟩ : ↥(V ∪ U)) ≠ ⟨y.val, Finset.mem_union_left U y.property⟩ ∧ _ constructor · intro heq exact hxy.1 (Subtype.ext (congrArg (fun z : ↥(V ∪ U) => z.val) heq)) · simpa only [hdiam] using hxy.2