AFTD Auto-Formalizing Theoretical Domains

binary_code_parity_class_card

theoremverified

For any integer n ≥ 1 and any parity ε : Fin 2, the set of words x : Fin n → Fin 2 whose sum of coordinates in Fin 2 equals ε has cardinality 2 ^ (n - 1).

Statement

theorem binary_code_parity_class_card (n : ℕ) (hn : 1 ≤ n) (ε : Fin 2) : (Finset.univ.filter (fun x : Fin n → Fin 2 => (∑ i, x i) = ε)).card = 2 ^ (n - 1)
Source
arXiv:2611.04523, Proposition 3.1
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For any natural number $n$ with $1 \le n$ and any $\varepsilon \in \text{Fin } 2$, the cardinality of the finset of functions $x : \text{Fin } n \to \text{Fin } 2$ whose sum over all $i \in \text{Fin } n$ equals $\varepsilon$ (under addition in $\text{Fin } 2$) is equal to $2^{n - 1}$.

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

Since n ≥ 1, we can write n = m + 1. We establish a bijection between the parity class of words of length m + 1 and the set of all unrestricted binary words of length m by projecting onto the first m coordinates. The inverse map appends the unique final coordinate needed to achieve total coordinate sum ε; because there are 2^m unrestricted words of length m, the parity class has cardinality 2^m = 2^(n - 1).

  1. We can write n = m + 1 for some natural number m, and define s as the parity class of words of length m + 1 and t as the set of all binary words of length m.

    Since n ≥ 1 > 0, n is positive, so it is the successor m + 1 of some natural number m. We let s be the subset of (Fin (m + 1) → Fin 2) consisting of words whose coordinate sum equals ε, and let t be the entire set of binary words of length m.

    lines 3–6

    uses Nat.exists_eq_succ_of_ne_zero, Nat.ne_of_gt, Nat.lt_of_lt_of_le, Nat.zero_lt_one

      obtain ⟨m, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (Nat.ne_of_gt (Nat.lt_of_lt_of_le Nat.zero_lt_one hn))
      classical
      let s : Finset (Fin (m + 1) → Fin 2) := Finset.univ.filter (fun x => (∑ i, x i) = ε)
      let t : Finset (Fin m → Fin 2) := Finset.univ
  2. To show |s| = |t|, it suffices to establish that the restriction map dropping the last coordinate is a bijection from s to t, and this map is well-defined.

    We apply `Finset.card_bij` with the map sending each word x ∈ s to its restriction (x₀, …, x_{m-1}) of length m. Since t contains all binary words of length m, every word restricts to an element of t.

    lines 7–10

    uses Finset.card_bij

      have hcard : s.card = t.card := by
        refine Finset.card_bij (fun x _ => fun i : Fin m => x i.castSucc) ?_ ?_ ?_
        · intro x hx
          simp [t]
  3. The restriction map from s to t is injective.

    Suppose x, y ∈ s have the same restriction to their first m coordinates. Since both coordinate sums equal ε, decomposing each sum into the sum of the first m coordinates plus the final coordinate gives ∑_{i < m} x_i + x_m = ε = ∑_{i < m} y_i + y_m. Because the initial segments agree, their prefix sums are identical, and cancelling this sum yields x_m = y_m. Recombining the identical initial segments with the identical final coordinates implies x = y.

    lines 11–34

    uses Finset.mem_filter.mp, Fin.sum_univ_castSucc, add_left_cancel, Fin.snoc_init_self

        · intro x hx y hy hxy
          have hxsum : (∑ i, x i) = ε := by
            simpa [s] using (Finset.mem_filter.mp hx).2
          have hysum : (∑ i, y i) = ε := by
            simpa [s] using (Finset.mem_filter.mp hy).2
          have hrest : (fun i : Fin m => x i.castSucc) = (fun i : Fin m => y i.castSucc) := hxy
          have hxy_sum : (∑ i : Fin m, x i.castSucc) = (∑ i : Fin m, y i.castSucc) := by
            rw [hrest]
          have hx' := hxsum
          rw [Fin.sum_univ_castSucc] at hx'
          have hy' := hysum
          rw [Fin.sum_univ_castSucc] at hy'
          have hlast : x (Fin.last m) = y (Fin.last m) := by
            have h1 : (∑ i : Fin m, x i.castSucc) + x (Fin.last m) =
                (∑ i : Fin m, y i.castSucc) + y (Fin.last m) := by
              rw [hx', hy']
            apply add_left_cancel (a := (∑ i : Fin m, x i.castSucc))
            rw [h1, ← hxy_sum]
          calc
            x = Fin.snoc (Fin.init x) (x (Fin.last m)) := (Fin.snoc_init_self x).symm
            _ = Fin.snoc (fun i : Fin m => x i.castSucc) (x (Fin.last m)) := by rfl
            _ = Fin.snoc (fun i : Fin m => y i.castSucc) (y (Fin.last m)) := by rw [hrest, hlast]
            _ = Fin.snoc (Fin.init y) (y (Fin.last m)) := by rfl
            _ = y := Fin.snoc_init_self y
  4. The restriction map from s to t is surjective.

    Given any binary word y of length m, we extend it to a word x of length m + 1 by appending the coordinate ε - ∑_{i < m} y_i. The coordinate sum of x is (∑_{i < m} y_i) + (ε - ∑_{i < m} y_i) = ε, so x ∈ s, and its restriction to the first m coordinates is y by construction.

    lines 35–44

    uses Fin.sum_snoc, add_sub_cancel

        · intro y hy
          let x : Fin (m + 1) → Fin 2 := Fin.snoc y (ε - ∑ i, y i)
          refine ⟨x, ?_, ?_⟩
          · have hsum : (∑ i : Fin (m + 1), x i) = ε := by
              dsimp [x]
              rw [Fin.sum_snoc]
              exact add_sub_cancel _ _
            simp [s, hsum]
          · funext i
            simp [x]
  5. The cardinality of the parity class s is 2 ^ (n - 1). automation

    Because |s| = |t|, the problem reduces to computing the size of t. The set t of all functions from a set of size m to a set of size 2 has cardinality 2^m, which equals 2 ^ (n - 1) since n = m + 1.

    lines 45–46

      rw [hcard]
      simp [t]
Nat.ne_of_gt
A natural number with a strictly smaller natural number is not equal to that smaller number.
Nat.exists_eq_succ_of_ne_zero
Every non-zero natural number is the successor of some natural number.
Nat.lt_of_lt_of_le
Strict inequality is preserved when composed with a weak inequality: if n < m and m ≤ k, then n < k.
Nat.zero_lt_one
Zero is strictly less than one.
Finset.card_bij
Two finite sets have equal cardinality if there exists a well-defined bijection between them.
Finset.mem_filter.mp
An element in a filtered finite set satisfies the defining predicate.
Fin.sum_univ_castSucc
The sum of a sequence of length n + 1 equals the sum of its first n elements plus the value at the final index.
add_left_cancel
In an additive structure with left-cancellation, a + b = a + c implies b = c.
Fin.snoc_init_self
Appending the last element of a sequence of length n + 1 to its initial segment of length n reconstructs the original sequence.
Fin.sum_snoc
The sum of a sequence of length n with an element appended at the end equals the sum of the sequence plus that element.
add_sub_cancel
In an additive group, a + (b - a) = b.

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 set of binary words of given coordinate-sum parity has cardinality 2^(n-1). -/theorem binary_code_parity_class_card (n : ℕ) (hn : 1 ≤ n) (ε : Fin 2) : (Finset.univ.filter (fun x : Fin n → Fin 2 => (∑ i, x i) = ε)).card = 2 ^ (n - 1) := by  obtain ⟨m, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (Nat.ne_of_gt (Nat.lt_of_lt_of_le Nat.zero_lt_one hn))  classical  let s : Finset (Fin (m + 1) → Fin 2) := Finset.univ.filter (fun x => (∑ i, x i) = ε)  let t : Finset (Fin m → Fin 2) := Finset.univ  have hcard : s.card = t.card := by    refine Finset.card_bij (fun x _ => fun i : Fin m => x i.castSucc) ?_ ?_ ?_    · intro x hx      simp [t]    · intro x hx y hy hxy      have hxsum : (∑ i, x i) = ε := by        simpa [s] using (Finset.mem_filter.mp hx).2      have hysum : (∑ i, y i) = ε := by        simpa [s] using (Finset.mem_filter.mp hy).2      have hrest : (fun i : Fin m => x i.castSucc) = (fun i : Fin m => y i.castSucc) := hxy      have hxy_sum : (∑ i : Fin m, x i.castSucc) = (∑ i : Fin m, y i.castSucc) := by        rw [hrest]      have hx' := hxsum      rw [Fin.sum_univ_castSucc] at hx'      have hy' := hysum      rw [Fin.sum_univ_castSucc] at hy'      have hlast : x (Fin.last m) = y (Fin.last m) := by        have h1 : (∑ i : Fin m, x i.castSucc) + x (Fin.last m) =            (∑ i : Fin m, y i.castSucc) + y (Fin.last m) := by          rw [hx', hy']        apply add_left_cancel (a := (∑ i : Fin m, x i.castSucc))        rw [h1, ← hxy_sum]      calc        x = Fin.snoc (Fin.init x) (x (Fin.last m)) := (Fin.snoc_init_self x).symm        _ = Fin.snoc (fun i : Fin m => x i.castSucc) (x (Fin.last m)) := by rfl        _ = Fin.snoc (fun i : Fin m => y i.castSucc) (y (Fin.last m)) := by rw [hrest, hlast]        _ = Fin.snoc (Fin.init y) (y (Fin.last m)) := by rfl        _ = y := Fin.snoc_init_self y    · intro y hy      let x : Fin (m + 1) → Fin 2 := Fin.snoc y (ε - ∑ i, y i)      refine ⟨x, ?_, ?_⟩      · have hsum : (∑ i : Fin (m + 1), x i) = ε := by          dsimp [x]          rw [Fin.sum_snoc]          exact add_sub_cancel _ _        simp [s, hsum]      · funext i        simp [x]  rw [hcard]  simp [t]
See it in the graphDiscuss this resultChallenge it