ternary_line_cover_card_ge
For every natural number n ≥ 1 and every ternary line cover B in (Fin n → ZMod 3), the cardinality of B is at least 3^(n - 1).
Statement
theorem ternary_line_cover_card_ge (n : ℕ) (hn : 1 ≤ n) (B : Finset (Fin n → ZMod 3)) (hB : is_ternary_line_cover n B) : 3 ^ (n - 1) ≤ B.card- Source
- step towards op_668_ternary_line_cover_first_gap_and_repair
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_ternary_line_coverGiven an explicit natural number n, a finite set B : Finset (Fin n → ZMod 3) is a ternary line cover if for every coordinate i : Fin n and…
- Used by 1
- bicirculant_cardFor any positive modulus m and any connection subsets R, S, T of ZMod m, the vertex set (Fin 2) × (ZMod m) of the bicirculant graph has…
The proof, explained
We write the dimension as n = m + 1 and consider the projection π from (Fin (m + 1) → ZMod 3) to (Fin m → ZMod 3) that drops the first coordinate. Because B is a ternary line cover, it intersects every line parallel to the first coordinate axis, meaning every point in the target space has a preimage in B under π. Consequently, the image of B under π is the entire space of 3^m functions. Since the cardinality of the image cannot exceed |B|, we conclude |B| ≥ 3^m = 3^(n - 1).
The dimension n is expressed as m + 1, and the projection π dropping the first coordinate is defined.
Since 1 ≤ n, integer linear arithmetic (`omega`) allows writing n = m + 1 with m = n - 1. We then define the coordinate projection π : (Fin (m + 1) → ZMod 3) → (Fin m → ZMod 3) that sends a vector v to the vector of its remaining coordinates indexed via `Fin.succ`.
obtain ⟨m, rfl⟩ : ∃ m, n = m + 1 := ⟨n - 1, by omega⟩ let π : (Fin (m + 1) → ZMod 3) → (Fin m → ZMod 3) := fun v j => v (Fin.succ j)
Every point d : Fin m → ZMod 3 has a preimage in B under the projection π.
Given any d : Fin m → ZMod 3, we extend it to dimension m + 1 by prepending 0 at index 0 using `Fin.insertNth`. Because B is a ternary line cover, the line passing through this vector along coordinate direction 0 must intersect B at some point with 0-th coordinate t ∈ ZMod 3. Updating coordinate 0 to t gives a vector v in B. Since any successor index j.succ is non-zero (`Fin.succ_ne_zero`), updating index 0 does not change the j-th coordinate (`Function.update_apply`, `if_false`), which equals d j. Thus π v = d.
uses
Function.update_apply,Fin.succ_ne_zero,if_falsehave hsurj : ∀ d : Fin m → ZMod 3, ∃ v ∈ B, π v = d := by intro d obtain ⟨t, ht⟩ := hB 0 (Fin.insertNth (α := fun _ => ZMod 3) 0 0 d) refine ⟨Function.update (Fin.insertNth (α := fun _ => ZMod 3) 0 0 d) 0 t, ht, ?_⟩ funext j simp only [π, Function.update_apply, Fin.succ_ne_zero, if_false] rfl
The image of B under π is the entire universal set Finset.univ.
To show a finset equals the full universe `Finset.univ`, it suffices to verify that every element belongs to it (`Finset.eq_univ_of_forall`). For every d : Fin m → ZMod 3, the surjectivity step yields a preimage v ∈ B with π v = d, which places d in `Finset.image π B` by `Finset.mem_image.mpr`.
uses
Finset.eq_univ_of_forall,Finset.mem_image.mprhave himage : Finset.image π B = Finset.univ := by apply Finset.eq_univ_of_forall intro d obtain ⟨v, hv, hvd⟩ := hsurj d exact Finset.mem_image.mpr ⟨v, hv, hvd⟩
The cardinality of the universal set is 3^m, which bounds B.card from below.
The number of functions Fin m → ZMod 3 is 3^m, computed by `simp`. This is the cardinality of `Finset.univ` by `Finset.card_univ`. Since `Finset.image π B = Finset.univ`, its cardinality is also 3^m. Finally, the size of the image of a finset cannot exceed the size of the set itself (`Finset.card_image_le`), which yields 3^(n - 1) ≤ B.card.
uses
Finset.card_univ,Finset.card_image_lecalc 3 ^ m = Fintype.card (Fin m → ZMod 3) := by simp _ = (Finset.univ : Finset (Fin m → ZMod 3)).card := (Finset.card_univ).symm _ = (Finset.image π B).card := by rw [himage] _ ≤ B.card := Finset.card_image_le
Function.update_apply- Evaluating an updated function `Function.update f a' b` at `a` yields `b` if `a = a'` and `f a` otherwise.
Fin.succ_ne_zero- For any element `k` in `Fin n`, its successor `k.succ` is not equal to `0` in `Fin (n + 1)`.
if_false- An if-then-else expression whose condition is `False` reduces to its else branch.
Finset.eq_univ_of_forall- A finset in a finite type α equals the universal finset `Finset.univ` if every element of α belongs to it.
Finset.mem_image.mpr- If an element `y` equals `f x` for some `x ∈ s`, then `y` belongs to the image finset `Finset.image f s`.
Finset.card_univ- The cardinality of the universal finset of a finite type α equals the total number of elements `Fintype.card α`.
Finset.card_image_le- The cardinality of the image of a finset under any function is at most the cardinality of the original finset.
- In Lean, points in the affine space are represented as functions from the index type `Fin n`, so coordinate projection and specifying an axis-parallel line are expressed using `Fin.succ`, `Fin.insertNth`, and `Function.update` rather than coordinate slicing.
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.
/-- Every ternary line cover in dimension n ≥ 1 has cardinality at least 3^(n - 1). -/theorem ternary_line_cover_card_ge (n : ℕ) (hn : 1 ≤ n) (B : Finset (Fin n → ZMod 3)) (hB : is_ternary_line_cover n B) : 3 ^ (n - 1) ≤ B.card := by -- Write n = m + 1 and project along coordinate 0. obtain ⟨m, rfl⟩ : ∃ m, n = m + 1 := ⟨n - 1, by omega⟩ let π : (Fin (m + 1) → ZMod 3) → (Fin m → ZMod 3) := fun v j => v (Fin.succ j) -- The projection π is surjective when restricted to B. have hsurj : ∀ d : Fin m → ZMod 3, ∃ v ∈ B, π v = d := by intro d obtain ⟨t, ht⟩ := hB 0 (Fin.insertNth (α := fun _ => ZMod 3) 0 0 d) refine ⟨Function.update (Fin.insertNth (α := fun _ => ZMod 3) 0 0 d) 0 t, ht, ?_⟩ funext j simp only [π, Function.update_apply, Fin.succ_ne_zero, if_false] rfl have himage : Finset.image π B = Finset.univ := by apply Finset.eq_univ_of_forall intro d obtain ⟨v, hv, hvd⟩ := hsurj d exact Finset.mem_image.mpr ⟨v, hv, hvd⟩ calc 3 ^ m = Fintype.card (Fin m → ZMod 3) := by simp _ = (Finset.univ : Finset (Fin m → ZMod 3)).card := (Finset.card_univ).symm _ = (Finset.image π B).card := by rw [himage] _ ≤ B.card := Finset.card_image_le