AFTD Auto-Formalizing Theoretical Domains

dual_melas_pattern_count_sum

theoremverified

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

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.

  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.

    lines 3–7

    uses Finset.card_eq_sum_card_fiberwise, Finset.mem_univ, Finset.card_univ, Fintype.card_fin

      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
  2. ∑ 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}.

    lines 8–9

      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

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