AFTD Auto-Formalizing Theoretical Domains

op_462_not_is_gale_counterexample_three_of_card_le_four

theoremverified

For every finite subset V of EuclideanSpace ℝ (Fin 3), if the cardinality of V is at most 4, then V is not a counterexample to Gale's conjecture in dimension 3 (that is, ¬ is_gale_counterexample_three V).

Statement

theorem op_462_not_is_gale_counterexample_three_of_card_le_four (V : Finset (EuclideanSpace ℝ (Fin 3))) (hV : V.card ≤ 4) : ¬ is_gale_counterexample_three V
Source
arXiv:2610.28828, Sec. 5, Question 2
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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 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.
Used by 1

Read back from the Lean

For every finite subset $V$ of 3-dimensional Euclidean space $\mathbb{R}^3$ (EuclideanSpace ℝ (Fin 3)), if the cardinality of $V$ is at most 4, then $V$ is not a 3-dimensional Gale counterexample (¬ is_gale_counterexample_three V).

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

By definition, a counterexample to Gale's conjecture in dimension 3 must have a distance graph that cannot be properly 4-colored. However, any graph on a vertex set V with |V| ≤ 4 is 4-colorable by assigning each vertex a distinct color. Since adjacent vertices in a simple graph are distinct, this injective assignment is a valid proper coloring, showing that V cannot be a counterexample.

  1. To derive a contradiction, it suffices to exhibit a proper 4-coloring of the Gale distance graph on V.

    Assume for contradiction that V is a counterexample to Gale's conjecture in dimension 3. By definition, this requires V to have positive diameter and its Gale distance graph to not be 4-colorable. Applying the non-colorability hypothesis (hcol), it suffices to prove that the distance graph is in fact 4-colorable.

    lines 3–5

      intro h
      obtain ⟨hdiam, hcol⟩ := h
      apply hcol
  2. The subtype of elements of V has cardinality at most 4 as a finite type.

    By Fintype.card_coe, the cardinality of V considered as a finite type (Fintype.card V) equals the cardinality of the finset V, which is at most 4 by hypothesis hV.

    line 6

    uses Fintype.card_coe

      have hcard : Fintype.card V ≤ 4 := by rw [Fintype.card_coe]; exact hV
  3. Define a candidate 4-coloring by embedding V injectively into Fin 4.

    Using Fintype.equivFin, choose a bijection e from V to Fin (Fintype.card V). Since |V| ≤ 4, we cast each index into Fin 4 via Fin.castLE. To show this yields a valid 4-coloring with SimpleGraph.Coloring.mk, it remains to verify that adjacent vertices receive distinct colors.

    lines 7–8

    uses Fintype.equivFin, SimpleGraph.Coloring.mk, Fin.castLE

      let e : V ≃ Fin (Fintype.card V) := Fintype.equivFin V
      refine ⟨SimpleGraph.Coloring.mk (fun v => Fin.castLE hcard (e v)) ?_⟩
  4. Adjacent vertices receive distinct colors, completing the proof of 4-colorability.

    Let v and w be adjacent vertices in the Gale distance graph. By definition of adjacency in a simple graph, v ≠ w. If their assigned colors were equal, injectivity of Fin.castLE (Fin.castLE_injective) would imply e(v) = e(w), and the injectivity of the bijection e would force v = w, contradicting v ≠ w.

    lines 9–14

    uses Fin.castLE_injective

      intro v w hadj
      have hne : v ≠ w := hadj.1
      intro hEq
      apply hne
      apply e.injective
      exact Fin.castLE_injective hcard hEq
Fintype.card_coe
The cardinality of a finite set viewed as a subtype is equal to its cardinality as a Finset.
Fintype.equivFin
Every finite type α is in bijection with the canonical finite set Fin |α| = {0, ..., |α|-1}.
SimpleGraph.Coloring.mk
Constructs a proper graph coloring from a vertex color assignment and a proof that adjacent vertices receive different colors.
Fin.castLE
Embeds Fin n into Fin m when n ≤ m, preserving numerical values.
Fin.castLE_injective
The inclusion map Fin n → Fin m (for n ≤ m) is injective.

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

/-- Any subset of R^3 of cardinality at most 4 is not a counterexample to Gale's conjecture. -/theorem op_462_not_is_gale_counterexample_three_of_card_le_four (V : Finset (EuclideanSpace ℝ (Fin 3))) (hV : V.card ≤ 4) : ¬ is_gale_counterexample_three V := by  intro h  obtain ⟨hdiam, hcol⟩ := h  apply hcol  have hcard : Fintype.card V ≤ 4 := by rw [Fintype.card_coe]; exact hV  let e : V ≃ Fin (Fintype.card V) := Fintype.equivFin V  refine ⟨SimpleGraph.Coloring.mk (fun v => Fin.castLE hcard (e v)) ?_⟩  intro v w hadj  have hne : v ≠ w := hadj.1  intro hEq  apply hne  apply e.injective  exact Fin.castLE_injective hcard hEq
See it in the graphDiscuss this resultChallenge it