dual_melas_joint_pattern_prob_le_one
For any field F finite-dimensional over ZMod 2, natural number k, elements α, c ∈ F, and natural numbers a, b, dual_melas_joint_pattern_prob k α c a b is at most 1.
Statement
theorem dual_melas_joint_pattern_prob_le_one {F : Type*} [Field F] [Algebra (ZMod 2) F] [FiniteDimensional (ZMod 2) F] (k : ℕ) (α c : F) (a b : ℕ) : dual_melas_joint_pattern_prob k α c a b ≤ 1
- Source
- step towards dual_melas_adjacent_cyclic_patterns_bivariate_poisson_limit
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- dual_melas_joint_pattern_probFor a field F finite-dimensional over ZMod 2, natural number k, elements α, c : F, and natural numbers a, b : ℕ,…
- 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 binary words of length k satisfying the Melas pattern conditions divided by 2^k. Since 2^k is strictly positive, the probability is at most 1 if and only if the count of such words is at most 2^k. Because the words satisfying the conditions form a subset of all 2^k binary words of length k, their count cannot exceed 2^k, which establishes the inequality.
The inequality reduces to showing that the number of binary words of length k satisfying the joint pattern condition is at most 2^k.
By definition, the joint pattern probability is the fraction of binary words of length k (functions from Fin k to ℤ/2ℤ) satisfying the pattern count conditions, divided by 2^k. Because 2^k > 0, clearing the denominator transforms the inequality into an upper bound on the numerator. Casting from real numbers to natural numbers then reduces the goal to an inequality between natural numbers.
uses
div_le_oneunfold dual_melas_joint_pattern_prob have hpos : (0 : ℝ) < (2 : ℝ) ^ k := by positivity rw [div_le_one hpos] norm_cast
The total number of binary words of length k is 2^k.
The type of binary words of length k is the function space from Fin k to ℤ/2ℤ. Since each of the k positions has 2 choices, the cardinality of this space is 2^k.
have hcard : Fintype.card (Fin k → ZMod 2) = 2 ^ k := by simp
The number of words satisfying the pattern condition is at most 2^k, completing the proof.
The words satisfying the given pattern counts form a subset of all binary words of length k. By Finset.card_le_univ, the size of any subset is bounded by the cardinality of the ambient space. Since the ambient space has size 2^k, the bound holds by linear arithmetic.
uses
Finset.card_le_univhave hle := Finset.card_le_univ {w | dual_melas_pattern_count k α c w = a ∧ dual_melas_pattern_count k α c (cyclic_rotate_left k w) = b} omega
div_le_one- For an element b > 0 in a linearly ordered semifield, a / b ≤ 1 if and only if a ≤ b.
Finset.card_le_univ- The cardinality of any finite subset of a finite type is at most the cardinality of the entire type.
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 joint pattern probability in the dual Melas sequence is at most 1. -/theorem dual_melas_joint_pattern_prob_le_one {F : Type*} [Field F] [Algebra (ZMod 2) F] [FiniteDimensional (ZMod 2) F] (k : ℕ) (α c : F) (a b : ℕ) : dual_melas_joint_pattern_prob k α c a b ≤ 1 := by unfold dual_melas_joint_pattern_prob have hpos : (0 : ℝ) < (2 : ℝ) ^ k := by positivity rw [div_le_one hpos] norm_cast have hcard : Fintype.card (Fin k → ZMod 2) = 2 ^ k := by simp have hle := Finset.card_le_univ {w | dual_melas_pattern_count k α c w = a ∧ dual_melas_pattern_count k α c (cyclic_rotate_left k w) = b} omega