dual_melas_pattern_count_sum
For any field F finite-dimensional over ZMod 2, natural number k, and elements α, c ∈ F, the sum over all binary words w : Fin k → ZMod 2 of dual_melas_pattern_count k α c w is equal to 2 ^ k - 1.
Statement
theorem dual_melas_pattern_count_sum {F : Type*} [Field F] [Algebra (ZMod 2) F] [FiniteDimensional (ZMod 2) F] (k : ℕ) (α c : F) : ∑ w : Fin k → ZMod 2, dual_melas_pattern_count k α c w = 2 ^ k - 1
- Source
- scout/2610-38017-on-the-b-symbol-weight-distribution-of-dual-melas-codes-and.md:1189
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- dual_melas_pattern_countFor a field F finite-dimensional over ZMod 2, natural number k, elements α, c : F, and word w : Fin k → ZMod 2, dual_melas_pattern_count k…
- dual_melas_windowFor a field F finite-dimensional over ZMod 2, natural number k, elements α, c : F, and index i : ℕ, dual_melas_window k α c i is the word…
- Used by 1
- dual_melas_pattern_count_cyclic_rotate_left_sumFor any field F finite-dimensional over ZMod 2, positive natural number k, and elements α, c ∈ F, the sum over all words w : Fin k → ZMod…
Read back from the Lean
For any field $F$ which is a finite-dimensional algebra over $\mathbb{Z}/2\mathbb{Z}$, any $k \in \mathbb{N}$, and any elements $\alpha, c \in F$, the sum over all binary patterns $w : \mathrm{Fin}\ k \to \mathbb{Z}/2\mathbb{Z}$ of the pattern count dual_melas_pattern_count k α c w is equal to $2^k - 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
The sum of the pattern counts over all 2 ^ k binary words of length k equals the period length 2 ^ k - 1 by double counting (fiberwise partition). The starting indices Fin (2 ^ k - 1) are partitioned according to the length-k window sequence they produce under the window function. Since the pattern count for any word w is defined precisely as the size of the fiber over w, summing these counts recovers the total number of starting positions, 2 ^ k - 1.
2 ^ k - 1 = ∑ w : Fin k → ZMod 2, #{i : Fin (2 ^ k - 1) | dual_melas_window k α c i.val = w}
We apply fiberwise counting (Finset.card_eq_sum_card_fiberwise) to partition the domain Fin (2 ^ k - 1) of starting indices into the fibers of the window map i ↦ dual_melas_window k α c i.val. The trivial inclusion of window values into the universal set of words is verified by Finset.mem_univ. Simplifying the cardinality of the domain with Finset.card_univ and Fintype.card_fin evaluates the left-hand side to 2 ^ k - 1.
uses
Finset.card_eq_sum_card_fiberwise,Finset.mem_univ,Finset.card_univ,Fintype.card_finhave h := Finset.card_eq_sum_card_fiberwise (s := (Finset.univ : Finset (Fin (2 ^ k - 1)))) (t := (Finset.univ : Finset (Fin k → ZMod 2))) (f := fun i : Fin (2 ^ k - 1) => dual_melas_window k α c i.val) (fun x _ => Finset.mem_univ _) simp only [Finset.card_univ, Fintype.card_fin] at h
∑ w : Fin k → ZMod 2, dual_melas_pattern_count k α c w = 2 ^ k - 1
Substituting the fiberwise sum for 2 ^ k - 1 into the goal using the equality established in the previous step, the two sides become identical by definition: by definition, dual_melas_pattern_count k α c w is the cardinality of the fiber #{i : Fin (2 ^ k - 1) | dual_melas_window k α c i.val = w}.
rw [h] rfl
Finset.card_eq_sum_card_fiberwise- For any map f between finite sets s and t, the cardinality of s equals the sum over all b in t of the cardinalities of the fibers of f over b.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type itself.
Fintype.card_fin- The cardinality of the finite type Fin n is n.
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 sum of pattern counts N_w over all 2^k words of length k equals the period length 2^k - 1. -/theorem dual_melas_pattern_count_sum {F : Type*} [Field F] [Algebra (ZMod 2) F] [FiniteDimensional (ZMod 2) F] (k : ℕ) (α c : F) : ∑ w : Fin k → ZMod 2, dual_melas_pattern_count k α c w = 2 ^ k - 1 := by have h := Finset.card_eq_sum_card_fiberwise (s := (Finset.univ : Finset (Fin (2 ^ k - 1)))) (t := (Finset.univ : Finset (Fin k → ZMod 2))) (f := fun i : Fin (2 ^ k - 1) => dual_melas_window k α c i.val) (fun x _ => Finset.mem_univ _) simp only [Finset.card_univ, Fintype.card_fin] at h rw [h] rfl