AFTD Auto-Formalizing Theoretical Domains

dual_melas_pattern_count_cyclic_rotate_left_sum

theoremverified

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.

  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.

    lines 6–7

    uses Equiv.ofBijective, cyclic_rotate_left_bijective

      let e := Equiv.ofBijective (cyclic_rotate_left (α := ZMod 2) k)
        (cyclic_rotate_left_bijective k hk (ZMod 2))
  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.

    lines 8–11

    uses Equiv.sum_comp

      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
  3. 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`.

    line 12

    uses dual_melas_pattern_count_sum

      rw [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

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