dual_melas_pattern_count_cyclic_rotate_left_sum
For 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 2 of dual_melas_pattern_count k α c (cyclic_rotate_left k w) equals 2^k - 1.
Statement
theorem dual_melas_pattern_count_cyclic_rotate_left_sum {F : Type*} [Field F] [Algebra (ZMod 2) F] [FiniteDimensional (ZMod 2) F] (k : ℕ) (hk : 0 < k) (α c : F) : ∑ w : Fin k → ZMod 2, dual_melas_pattern_count k α c (cyclic_rotate_left k w) = 2 ^ k - 1
- Source
- step towards dual_melas_adjacent_cyclic_patterns_bivariate_poisson_limit
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- dual_melas_pattern_count_sumFor 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…
- cyclic_rotate_left_bijectiveFor any positive natural number k and any type α, cyclic_rotate_left k is a bijection on Fin k → α.
- 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…
- cyclic_rotate_leftGiven a type α, a natural number k, and a word w : Fin k → α, cyclic_rotate_left k w is the function Fin k → α mapping each index j : Fin…
The proof, explained
Because cyclic left rotation on binary words of length k is a bijection, it induces a permutation of the domain of summation. Reindexing the sum by this equivalence shows that the sum of the rotated pattern counts equals the sum of the unrotated pattern counts. The claim then follows from the established theorem that the unrotated pattern counts sum to 2^k - 1.
Cyclic left rotation defines an equivalence (permutation) on binary words of length k.
Since k > 0, the cyclic left shift on words of length k is bijective (`cyclic_rotate_left_bijective`). Upgrading this bijection to an equivalence via `Equiv.ofBijective` yields a permutation e on the space of binary words Fin k → ZMod 2.
uses
Equiv.ofBijective,cyclic_rotate_left_bijectivelet e := Equiv.ofBijective (cyclic_rotate_left (α := ZMod 2) k) (cyclic_rotate_left_bijective k hk (ZMod 2))The sum of the pattern counts over rotated words equals the sum over unrotated words.
Summing over a finite type is invariant under reindexing by an equivalence (`Equiv.sum_comp`). Applying this with the permutation e equates the sum over unrotated words with the sum over rotated words e(w), which matches definitionally.
uses
Equiv.sum_comphave hsum : ∑ w : Fin k → ZMod 2, dual_melas_pattern_count k α c (cyclic_rotate_left k w) = ∑ w : Fin k → ZMod 2, dual_melas_pattern_count k α c w := by rw [← Equiv.sum_comp e (fun w => dual_melas_pattern_count k α c w)] rfl
The sum of the rotated pattern counts equals 2^k - 1.
Rewriting by the reindexed sum reduces the expression to the sum of unrotated pattern counts, which evaluates to 2^k - 1 by `dual_melas_pattern_count_sum`.
uses
dual_melas_pattern_count_sumrw [hsum, dual_melas_pattern_count_sum k α c]
Equiv.ofBijective- A bijective map between two types induces an equivalence (bijection) between them.
cyclic_rotate_left_bijective- For any positive length k, cyclic left rotation on words of length k is a bijection.
Equiv.sum_comp- Summing a function over a finite type is invariant under reindexing by an equivalence.
dual_melas_pattern_count_sum- The sum of the pattern counts over all binary words of length k in the dual Melas code equals 2^k - 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
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.
/-- Sum of rotated pattern counts over all binary words equals 2^k - 1. -/theorem dual_melas_pattern_count_cyclic_rotate_left_sum {F : Type*} [Field F] [Algebra (ZMod 2) F] [FiniteDimensional (ZMod 2) F] (k : ℕ) (hk : 0 < k) (α c : F) : ∑ w : Fin k → ZMod 2, dual_melas_pattern_count k α c (cyclic_rotate_left k w) = 2 ^ k - 1 := by let e := Equiv.ofBijective (cyclic_rotate_left (α := ZMod 2) k) (cyclic_rotate_left_bijective k hk (ZMod 2)) have hsum : ∑ w : Fin k → ZMod 2, dual_melas_pattern_count k α c (cyclic_rotate_left k w) = ∑ w : Fin k → ZMod 2, dual_melas_pattern_count k α c w := by rw [← Equiv.sum_comp e (fun w => dual_melas_pattern_count k α c w)] rfl rw [hsum, dual_melas_pattern_count_sum k α c]