AFTD Auto-Formalizing Theoretical Domains

bicirculant_card

theoremverified

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.

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

    line 2

    uses ternary_line_cover_card_ge

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

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

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