dual_melas_pattern_count_le
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
- dual_melas_joint_pattern_prob_sumFor any field F finite-dimensional over ZMod 2, natural number k, and elements α, c ∈ F, the sum of dual_melas_joint_pattern_prob k α c a…
- dual_melas_joint_pattern_prob_eq_zero_of_geFor any field F finite-dimensional over ZMod 2, natural number k, elements α, c ∈ F, and natural numbers a, b such that 2^k ≤ a or 2^k ≤…
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.
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`.
unfold dual_melas_pattern_countThe 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.
uses
Finset.card_filter_leexact (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
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 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)