AFTD Auto-Formalizing Theoretical Domains

dual_melas_pattern_count_le

theoremverified

For any 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 α c w ≤ 2 ^ k - 1.

Statement

theorem dual_melas_pattern_count_le
    {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
step towards dual_melas_adjacent_cyclic_patterns_bivariate_poisson_limit
Verified
03 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 2

The proof, explained

The pattern count is defined as the number of indices in Fin (2 ^ k - 1) whose sliding window matches the given binary word w. Because this count is the cardinality of a filtered subset of the finite universe Fin (2 ^ k - 1), it is bounded above by the total number of elements in that universe, which is 2 ^ k - 1.

  1. The pattern count is expressed as the cardinality of a filtered subset of Fin (2 ^ k - 1).

    Unfolding the definition of `dual_melas_pattern_count` reveals that it counts the indices i : Fin (2 ^ k - 1) whose dual Melas window matches w, represented as the cardinality of a sub-finset of `Finset.univ`.

    line 6

      unfold dual_melas_pattern_count
  2. The size of this filtered subset is at most 2 ^ k - 1.

    By `Finset.card_filter_le`, filtering elements of a finite set never increases its cardinality, so the count is bounded by the cardinality of `Finset.univ` on Fin (2 ^ k - 1). The universal set of Fin (2 ^ k - 1) has cardinality 2 ^ k - 1, which simp evaluates to complete the inequality via transitivity.

    line 7

    uses Finset.card_filter_le

      exact (Finset.card_filter_le _ _).trans (by simp)
Finset.card_filter_le
For any finite set s and predicate p, the cardinality of the filtered subset of elements satisfying p is at most the cardinality of s.

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 pattern count for any binary word in the dual Melas sequence is at most 2^k - 1. -/theorem dual_melas_pattern_count_le    {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  unfold dual_melas_pattern_count  exact (Finset.card_filter_le _ _).trans (by simp)
See it in the graphDiscuss this resultChallenge it