dual_melas_joint_pattern_prob_sum
For 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 b over all a, b < 2^k equals 1.
Statement
theorem dual_melas_joint_pattern_prob_sum {F : Type*} [Field F] [Algebra (ZMod 2) F] [FiniteDimensional (ZMod 2) F] (k : ℕ) (α c : F) : ∑ a ∈ Finset.range (2 ^ k), ∑ b ∈ Finset.range (2 ^ k), 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 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…
- 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…
- 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…
The proof, explained
The proof unfolds the definition of the joint pattern probability as a fiber cardinality divided by 2^k and factors the division out of the double sum. The double sum of fiber cardinalities over all a, b < 2^k is evaluated by an auxiliary partitioning lemma (dual_melas_joint_pattern_prob_sum_aux2), which proves that the fibers of two bounded functions on a finite domain partition the domain. Since the domain of binary words of length k has size 2^k, the double sum equals 2^k, and the probability sum simplifies to 2^k / 2^k = 1.
For each fixed a, summing the joint fiber cardinalities over b < N gives the size of the fiber where f(x) = a.
Fix a. By applying dual_melas_joint_pattern_prob_sum_aux1 to the fiber s = {x | f(x) = a} and the bounded function g, summing over b < N partitions s into subfibers {x ∈ s | g(x) = b}. Rewriting this condition using Finset.filter_filter expresses each subfiber as the joint fiber {x | f(x) = a ∧ g(x) = b}, and Finset.sum_congr applies this termwise across the sum over b.
uses
dual_melas_joint_pattern_prob_sum_aux1,Finset.sum_congr,Finset.filter_filterhave step : ∀ a, ∑ b ∈ Finset.range N, (Finset.univ.filter (fun x => f x = a ∧ g x = b)).card = (Finset.univ.filter (fun x => f x = a)).card := by intro a rw [← dual_melas_joint_pattern_prob_sum_aux1 (Finset.univ.filter (fun x => f x = a)) g N (fun x _ => hg x)] apply Finset.sum_congr rfl intro b _ rw [Finset.filter_filter]
The double sum of the joint fiber cardinalities over all a, b < N equals the cardinality of the type X.
Using Finset.sum_congr across the outer sum over a, we replace the inner sum with the marginal fiber size #{x | f(x) = a} from the previous step. Summing these marginal fiber sizes over all a < N via dual_melas_joint_pattern_prob_sum_aux1 on Finset.univ evaluates the total sum to |Finset.univ|, which equals Fintype.card X by Finset.card_univ.
uses
Finset.sum_congr,Finset.card_univ,dual_melas_joint_pattern_prob_sum_aux1have h1 : (∑ a ∈ Finset.range N, ∑ b ∈ Finset.range N, (Finset.univ.filter (fun x => f x = a ∧ g x = b)).card) = ∑ a ∈ Finset.range N, (Finset.univ.filter (fun x => f x = a)).card := Finset.sum_congr rfl (fun a _ => step a) rw [h1, ← Finset.card_univ] exact dual_melas_joint_pattern_prob_sum_aux1 Finset.univ f N (fun x _ => hf x)
The goal is expressed in terms of the cardinalities of joint pattern count fibers.
We unfold the definition of dual_melas_joint_pattern_prob, which defines the probability as the cardinality of binary words w whose pattern count is a and whose cyclically rotated pattern count is b, divided by 2^k.
unfold dual_melas_joint_pattern_probFor every binary word w : Fin k → ZMod 2, the pattern count of w is strictly less than 2^k. automation
By dual_melas_pattern_count_le, the pattern count is at most 2^k - 1. Since 2^k > 0 by pow_pos, linear integer arithmetic (omega) deduces that the count is strictly less than 2^k.
uses
pow_pos,dual_melas_pattern_count_lehave hbound : ∀ w : Fin k → ZMod 2, dual_melas_pattern_count k α c w < 2 ^ k := by intro w have hp : 0 < 2 ^ k := pow_pos (by norm_num) k have h := dual_melas_pattern_count_le k α c w omega
The double sum of the joint pattern count fiber cardinalities over all a, b < 2^k equals 2^k.
We apply the auxiliary lemma dual_melas_joint_pattern_prob_sum_aux2 with bound N = 2^k to the word pattern count and its cyclic rotation, both of which are bounded by 2^k. This shows the double sum of fiber sizes equals the cardinality of the space of binary words Fin k → ZMod 2. Since |ZMod 2| = 2 by ZMod.card, the total number of words is 2^k.
uses
dual_melas_joint_pattern_prob_sum_aux2,ZMod.cardhave hcard : ∑ a ∈ Finset.range (2 ^ k), ∑ b ∈ Finset.range (2 ^ k), (Finset.univ.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)).card = (2 : ℕ) ^ k := by have h := dual_melas_joint_pattern_prob_sum_aux2 (fun w : Fin k → ZMod 2 => dual_melas_pattern_count k α c w) (fun w : Fin k → ZMod 2 => dual_melas_pattern_count k α c (cyclic_rotate_left k w)) (2 ^ k) hbound (fun x => hbound (cyclic_rotate_left k x)) rw [h] simp [ZMod.card]
Casting the double sum of fiber cardinalities to the real numbers yields (2 : ℝ)^k.
We apply the coercion map from ℕ to ℝ using congrArg to both sides of the cardinality equality and push the cast through the double sum and exponent.
uses
congrArghave hcardR : (∑ a ∈ Finset.range (2 ^ k), ∑ b ∈ Finset.range (2 ^ k), ((Finset.univ.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)).card : ℝ)) = (2 : ℝ) ^ k := by have h := congrArg (fun n : ℕ => (n : ℝ)) hcard push_cast at h ⊢ exact h
The denominator (2 : ℝ)^k is nonzero.
Since 2 > 0, 2^k is strictly positive by pow_pos, and therefore nonzero by ne_of_gt.
uses
ne_of_gt,pow_poshave hD : (2 : ℝ) ^ k ≠ 0 := ne_of_gt (pow_pos (by norm_num) k)
The sum of the joint probabilities over all a, b < 2^k equals 1.
Using Finset.sum_div twice (with Finset.sum_congr for the inner sum), we factor the divisor 2^k out of both sums, expressing the total sum as the double sum of fiber counts divided by 2^k. Substituting the previously computed value (2 : ℝ)^k for the numerator, the fraction becomes 2^k / 2^k, which simplifies to 1 by div_self.
uses
Finset.sum_congr,Finset.sum_div,div_selfcalc ∑ a ∈ Finset.range (2 ^ k), ∑ b ∈ Finset.range (2 ^ k), ((Finset.univ.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)).card : ℝ) / (2 : ℝ) ^ k = ∑ a ∈ Finset.range (2 ^ k), (∑ b ∈ Finset.range (2 ^ k), ((Finset.univ.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)).card : ℝ)) / (2 : ℝ) ^ k := Finset.sum_congr rfl (fun a _ => (Finset.sum_div (Finset.range (2 ^ k)) _ _).symm) _ = (∑ a ∈ Finset.range (2 ^ k), ∑ b ∈ Finset.range (2 ^ k), ((Finset.univ.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)).card : ℝ)) / (2 : ℝ) ^ k := (Finset.sum_div (Finset.range (2 ^ k)) _ _).symm _ = (2 : ℝ) ^ k / (2 : ℝ) ^ k := by rw [hcardR] _ = 1 := div_self hD
dual_melas_joint_pattern_prob_sum_aux1- For any finite set s and function f : X → ℕ with f x < N for all x ∈ s, the sum over b < N of the sizes of the fibers {x ∈ s | f x = b} equals the cardinality of s.
Finset.filter_filter- Filtering a finite set by predicate p and then by predicate q is equivalent to filtering by the conjunction p x ∧ q x.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Finset.sum_congr- If two finite index sets are equal and two summand functions agree on the index set, then their sums are equal.
dual_melas_joint_pattern_prob_sum_aux2- For two functions f, g on a finite type X bounded by N, the double sum over a, b < N of the joint fiber cardinalities #{x | f x = a ∧ g x = b} equals the cardinality of X.
dual_melas_pattern_count_le- The number of windows of length k matching a pattern w in a dual Melas sequence of period 2^k - 1 is at most 2^k - 1.
pow_pos- In an ordered semiring, raising a strictly positive element to any natural power yields a strictly positive element.
ZMod.card- The cardinality of the finite type ZMod n is n.
congrArg- Applying a function to both sides of an equality preserves the equality.
ne_of_gt- A strictly greater element is not equal to the smaller element.
Finset.sum_div- A finite sum of terms each divided by a scalar equals the sum of the terms divided by that scalar.
div_self- Any nonzero element in a group with zero divided by itself equals 1.
- The auxiliary lemma dual_melas_joint_pattern_prob_sum_aux2, proved in lines 7–26, partitions the space X into joint fibers and forms the combinatorial core of the theorem.
- The inequality dual_melas_pattern_count k α c w < 2^k in step 4 is closed automatically by omega using the bound dual_melas_pattern_count_le and 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.
private lemma dual_melas_joint_pattern_prob_sum_aux1 {X : Type*} [DecidableEq X] (s : Finset X) (f : X → ℕ) (N : ℕ) (h : ∀ x ∈ s, f x < N) : ∑ b ∈ Finset.range N, (s.filter (fun x => f x = b)).card = s.card := (Finset.card_eq_sum_card_fiberwise (f := f) (s := s) (t := Finset.range N) (fun x hx => Finset.mem_range.mpr (h x hx))).symmprivate lemma dual_melas_joint_pattern_prob_sum_aux2 {X : Type*} [Fintype X] [DecidableEq X] (f g : X → ℕ) (N : ℕ) (hf : ∀ x, f x < N) (hg : ∀ x, g x < N) : ∑ a ∈ Finset.range N, ∑ b ∈ Finset.range N, (Finset.univ.filter (fun x => f x = a ∧ g x = b)).card = Fintype.card X := by have step : ∀ a, ∑ b ∈ Finset.range N, (Finset.univ.filter (fun x => f x = a ∧ g x = b)).card = (Finset.univ.filter (fun x => f x = a)).card := by intro a rw [← dual_melas_joint_pattern_prob_sum_aux1 (Finset.univ.filter (fun x => f x = a)) g N (fun x _ => hg x)] apply Finset.sum_congr rfl intro b _ rw [Finset.filter_filter] have h1 : (∑ a ∈ Finset.range N, ∑ b ∈ Finset.range N, (Finset.univ.filter (fun x => f x = a ∧ g x = b)).card) = ∑ a ∈ Finset.range N, (Finset.univ.filter (fun x => f x = a)).card := Finset.sum_congr rfl (fun a _ => step a) rw [h1, ← Finset.card_univ] exact dual_melas_joint_pattern_prob_sum_aux1 Finset.univ f N (fun x _ => hf x)/-- Sum of dual Melas joint pattern probabilities over range 2^k is 1. -/theorem dual_melas_joint_pattern_prob_sum {F : Type*} [Field F] [Algebra (ZMod 2) F] [FiniteDimensional (ZMod 2) F] (k : ℕ) (α c : F) : ∑ a ∈ Finset.range (2 ^ k), ∑ b ∈ Finset.range (2 ^ k), dual_melas_joint_pattern_prob k α c a b = 1 := by unfold dual_melas_joint_pattern_prob have hbound : ∀ w : Fin k → ZMod 2, dual_melas_pattern_count k α c w < 2 ^ k := by intro w have hp : 0 < 2 ^ k := pow_pos (by norm_num) k have h := dual_melas_pattern_count_le k α c w omega have hcard : ∑ a ∈ Finset.range (2 ^ k), ∑ b ∈ Finset.range (2 ^ k), (Finset.univ.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)).card = (2 : ℕ) ^ k := by have h := dual_melas_joint_pattern_prob_sum_aux2 (fun w : Fin k → ZMod 2 => dual_melas_pattern_count k α c w) (fun w : Fin k → ZMod 2 => dual_melas_pattern_count k α c (cyclic_rotate_left k w)) (2 ^ k) hbound (fun x => hbound (cyclic_rotate_left k x)) rw [h] simp [ZMod.card] have hcardR : (∑ a ∈ Finset.range (2 ^ k), ∑ b ∈ Finset.range (2 ^ k), ((Finset.univ.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)).card : ℝ)) = (2 : ℝ) ^ k := by have h := congrArg (fun n : ℕ => (n : ℝ)) hcard push_cast at h ⊢ exact h have hD : (2 : ℝ) ^ k ≠ 0 := ne_of_gt (pow_pos (by norm_num) k) calc ∑ a ∈ Finset.range (2 ^ k), ∑ b ∈ Finset.range (2 ^ k), ((Finset.univ.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)).card : ℝ) / (2 : ℝ) ^ k = ∑ a ∈ Finset.range (2 ^ k), (∑ b ∈ Finset.range (2 ^ k), ((Finset.univ.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)).card : ℝ)) / (2 : ℝ) ^ k := Finset.sum_congr rfl (fun a _ => (Finset.sum_div (Finset.range (2 ^ k)) _ _).symm) _ = (∑ a ∈ Finset.range (2 ^ k), ∑ b ∈ Finset.range (2 ^ k), ((Finset.univ.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)).card : ℝ)) / (2 : ℝ) ^ k := (Finset.sum_div (Finset.range (2 ^ k)) _ _).symm _ = (2 : ℝ) ^ k / (2 : ℝ) ^ k := by rw [hcardR] _ = 1 := div_self hD