AFTD Auto-Formalizing Theoretical Domains

dual_melas_joint_pattern_prob_le_one

theoremverified

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.

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

    lines 6–9

    uses div_le_one

      unfold dual_melas_joint_pattern_prob
      have hpos : (0 : ℝ) < (2 : ℝ) ^ k := by positivity
      rw [div_le_one hpos]
      norm_cast
  2. 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.

    line 10

      have hcard : Fintype.card (Fin k → ZMod 2) = 2 ^ k := by simp
  3. 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.

    lines 11–12

    uses Finset.card_le_univ

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

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