AFTD Auto-Formalizing Theoretical Domains

dual_melas_joint_pattern_prob_eq_zero_of_ge

theoremverified

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.

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

    line 6

      unfold dual_melas_joint_pattern_prob
  2. The 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.

    lines 7–18

    uses Finset.filter_eq_empty_iff, dual_melas_pattern_count_le, Nat.two_pow_pos

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

    lines 19–20

      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.

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

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