AFTD Auto-Formalizing Theoretical Domains

ternary_line_cover_card_ge

theoremverified

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

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

    lines 4–5

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

    lines 7–13

    uses Function.update_apply, Fin.succ_ne_zero, if_false

      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
  3. 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`.

    lines 14–18

    uses Finset.eq_univ_of_forall, Finset.mem_image.mpr

      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⟩
  4. 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.

    lines 19–22

    uses Finset.card_univ, Finset.card_image_le

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

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

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