bicirculant_card
For 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 cardinality 2 * m.
Statement
theorem bicirculant_card (m : ℕ) [NeZero m] (R S T : Finset (ZMod m)) : Fintype.card (Fin 2 × ZMod m) = 2 * m- Source
- folklore
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- ternary_line_cover_card_geFor 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).
Read back from the Lean
For any natural number $m$ such that $m \neq 0$ (given by [NeZero m]), and for any finite sets $R, S, T \subseteq \mathbb{Z}/m\mathbb{Z}$, the cardinality of the product type $\mathrm{Fin}(2) \times (\mathbb{Z}/m\mathbb{Z})$ is equal to $2m$.
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
The vertex set of the bicirculant graph is the Cartesian product (Fin 2) × (ZMod m). Its cardinality is the product of the cardinalities of Fin 2 (which has 2 elements) and ZMod m (which has m elements, since m is non-zero). Lean's simplifier evaluates this product cardinality directly to 2 * m, closing the goal.
The vertex set (Fin 2) × (ZMod m) has cardinality 2 * m. automation
The goal is to compute the cardinality of the product type (Fin 2) × (ZMod m). Lean's simplifier (invoked by `simpa`) computes the cardinality of a Cartesian product as the product of the factor cardinalities: |Fin 2| = 2 and |ZMod m| = m (since m is non-zero). This simplifies the left-hand side to 2 * m, completing the proof by reflexivity.
uses
ternary_line_cover_card_getheorem bicirculant_card (m : ℕ) [NeZero m] (R S T : Finset (ZMod m)) : Fintype.card (Fin 2 × ZMod m) = 2 * m := by first | exact ternary_line_cover_card_ge | (apply ternary_line_cover_card_ge <;> assumption) | (apply ternary_line_cover_card_ge <;> simp_all) | simpa using ternary_line_cover_card_ge
ternary_line_cover_card_ge- For any dimension n ≥ 1, any subset of (ZMod 3)^n that intersects every combinatorial line has cardinality at least 3^(n - 1).
- The proof script uses a fallback search (`first | ... | simpa using ternary_line_cover_card_ge`) that references `ternary_line_cover_card_ge`, an unrelated lemma about combinatorial line covers in ternary vector spaces. This lemma is completely unused: the `simpa` tactic simplifies the product cardinality `Fintype.card (Fin 2 × ZMod m)` directly to `2 * m`, closing the goal by reflexivity before ever using the provided lemma.
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.
/-- The vertex set (Fin 2) × (ZMod m) of a bicirculant graph on ZMod m has cardinality 2 * m. -/theorem bicirculant_card (m : ℕ) [NeZero m] (R S T : Finset (ZMod m)) : Fintype.card (Fin 2 × ZMod m) = 2 * m := by first | exact ternary_line_cover_card_ge | (apply ternary_line_cover_card_ge <;> assumption) | (apply ternary_line_cover_card_ge <;> simp_all) | simpa using ternary_line_cover_card_ge