AFTD Auto-Formalizing Theoretical Domains

op462_counterexample_extend_card

theoremverified

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 t is…
  • gale_sigma_threeThe real constant gale_sigma_three is 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…
Used by 1

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.

  1. 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.

    lines 4–9

    uses Set.not_subsingleton_iff.mp, Metric.diam_subsingleton, convex_convexHull, subset_convexHull

      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 ℝ _))
  2. 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.

    lines 10–14

    uses exists_subset_card_eq, Finset.disjoint_left

      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
  3. 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)$.

    lines 15–20

    uses Finset.mem_union.mp, subset_convexHull

      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
  4. 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)$.

    lines 21–27

    uses le_antisymm, Metric.diam_mono, isBounded_convexHull.mpr, trans_eq, convexHull_diam, Finset.mem_union_left

      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
  5. 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$.

    lines 28–29

    uses Finset.card_union_of_disjoint, Nat.add_sub_of_le

      refine ⟨V ∪ U, ?_, ?_⟩
      · rw [Finset.card_union_of_disjoint hdisj, hcardU, Nat.add_sub_of_le hn]
  6. 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.

    lines 30–41

    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.

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

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
See it in the graphDiscuss this resultChallenge it