dual_melas_joint_pattern_prob_eq_zero_of_ge
For 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 ≤ b, dual_melas_joint_pattern_prob k α c a b = 0.
Statement
theorem dual_melas_joint_pattern_prob_eq_zero_of_ge {F : Type*} [Field F] [Algebra (ZMod 2) F] [FiniteDimensional (ZMod 2) F] (k : ℕ) (α c : F) (a b : ℕ) (h : 2 ^ k ≤ a ∨ 2 ^ k ≤ b) : dual_melas_joint_pattern_prob k α c a b = 0
- Source
- step towards dual_melas_adjacent_cyclic_patterns_bivariate_poisson_limit
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- dual_melas_joint_pattern_probFor a field F finite-dimensional over ZMod 2, natural number k, elements α, c : F, and natural numbers a, b : ℕ,…
- dual_melas_pattern_count_leFor 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…
- 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…
- 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…
The proof, explained
The joint pattern probability is defined as the number of length-k patterns with count a whose cyclic shift has count b, divided by 2^k. By dual_melas_pattern_count_le, every pattern count in the dual Melas sequence is at most 2^k - 1, which implies both a and b must be at most 2^k - 1 for any such pattern to exist. Under the assumption that 2^k ≤ a or 2^k ≤ b, no pattern can satisfy both conditions; hence the set of matching patterns is empty, and the probability evaluates to 0.
The joint pattern probability is expressed as the cardinality of the set of patterns satisfying both count conditions divided by 2^k.
Unfolding the definition of dual_melas_joint_pattern_prob writes the probability as the fraction |S| / 2^k, where S is the set of all binary patterns w of length k whose pattern count is a and whose cyclically rotated pattern count is b.
unfold dual_melas_joint_pattern_probThe set of patterns satisfying both count conditions is empty.
By Finset.filter_eq_empty_iff, it suffices to show that no pattern w can satisfy both count conditions simultaneously. For any pattern w, dual_melas_pattern_count_le shows that its count and the count of its cyclic shift cyclic_rotate_left k w are each bounded above by 2^k - 1. Assuming a pattern w has count a and its shift has count b, we would have a ≤ 2^k - 1 and b ≤ 2^k - 1. Using the fact that 0 < 2^k from Nat.two_pow_pos, we split into cases on the hypothesis h : 2^k ≤ a ∨ 2^k ≤ b: the first case gives 2^k ≤ a ≤ 2^k - 1, and the second gives 2^k ≤ b ≤ 2^k - 1. Both cases are contradictions in linear natural arithmetic, closed by omega.
uses
Finset.filter_eq_empty_iff,dual_melas_pattern_count_le,Nat.two_pow_poshave h_empty : Finset.filter (fun (w : Fin k → ZMod 2) => dual_melas_pattern_count k α c w = a ∧ dual_melas_pattern_count k α c (cyclic_rotate_left k w) = b) Finset.univ = ∅ := by rw [Finset.filter_eq_empty_iff] intro w _ have h1 := dual_melas_pattern_count_le k α c w have h2 := dual_melas_pattern_count_le k α c (cyclic_rotate_left k w) have hk : 0 < 2 ^ k := Nat.two_pow_pos k intro ⟨hwa, hwb⟩ rcases h with ha | hb · omega · omega
dual_melas_joint_pattern_prob k α c a b = 0
Rewriting with h_empty replaces the filtered set by the empty set ∅. Since the cardinality of ∅ is 0, the numerator is 0 and the ratio 0 / 2^k simplifies to 0 via simp.
rw [h_empty] simp
Finset.filter_eq_empty_iff- A filtered finite set is empty if and only if no element in the ambient set satisfies the filtering predicate.
dual_melas_pattern_count_le- The count of any pattern w of length k in the dual Melas sequence is at most 2^k - 1.
Nat.two_pow_pos- The power 2^w is strictly positive for every natural number w.
- In line 14, the strict positivity 0 < 2^k is explicitly introduced via Nat.two_pow_pos as a formal detail so that the integer arithmetic tactic omega can correctly handle truncated subtraction on natural numbers (namely, that a ≤ 2^k - 1 and 2^k ≤ a are contradictory only when 2^k > 0).
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.
/-- Joint pattern probability vanishes when either count is at least 2^k. -/theorem dual_melas_joint_pattern_prob_eq_zero_of_ge {F : Type*} [Field F] [Algebra (ZMod 2) F] [FiniteDimensional (ZMod 2) F] (k : ℕ) (α c : F) (a b : ℕ) (h : 2 ^ k ≤ a ∨ 2 ^ k ≤ b) : dual_melas_joint_pattern_prob k α c a b = 0 := by unfold dual_melas_joint_pattern_prob have h_empty : Finset.filter (fun (w : Fin k → ZMod 2) => dual_melas_pattern_count k α c w = a ∧ dual_melas_pattern_count k α c (cyclic_rotate_left k w) = b) Finset.univ = ∅ := by rw [Finset.filter_eq_empty_iff] intro w _ have h1 := dual_melas_pattern_count_le k α c w have h2 := dual_melas_pattern_count_le k α c (cyclic_rotate_left k w) have hk : 0 < 2 ^ k := Nat.two_pow_pos k intro ⟨hwa, hwb⟩ rcases h with ha | hb · omega · omega rw [h_empty] simp