AFTD Auto-Formalizing Theoretical Domains

dual_melas_joint_pattern_prob_sum

theoremverified

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.

  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.

    lines 11–19

    uses dual_melas_joint_pattern_prob_sum_aux1, Finset.sum_congr, Finset.filter_filter

      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]
  2. 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.

    lines 20–25

    uses Finset.sum_congr, Finset.card_univ, dual_melas_joint_pattern_prob_sum_aux1

      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)
  3. 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.

    line 33

      unfold dual_melas_joint_pattern_prob
  4. For 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.

    lines 34–39

    uses pow_pos, dual_melas_pattern_count_le

      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
  5. 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.

    lines 40–50

    uses dual_melas_joint_pattern_prob_sum_aux2, ZMod.card

      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]
  6. 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.

    lines 51–58

    uses congrArg

      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
  7. The denominator (2 : ℝ)^k is nonzero.

    Since 2 > 0, 2^k is strictly positive by pow_pos, and therefore nonzero by ne_of_gt.

    line 59

    uses ne_of_gt, pow_pos

      have hD : (2 : ℝ) ^ k ≠ 0 := ne_of_gt (pow_pos (by norm_num) k)
  8. 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.

    lines 60–80

    uses Finset.sum_congr, Finset.sum_div, div_self

      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
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.

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

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
See it in the graphDiscuss this resultChallenge it