AFTD Auto-Formalizing Theoretical Domains

bit_persuasion_even_prior_is_bit_prior

theoremverified

For every natural number m ≥ 1, the function bit_persuasion_even_prior m is a bit prior (is_bit_prior (bit_persuasion_even_prior m)).

Statement

open Finset in
theorem bit_persuasion_even_prior_is_bit_prior (m : ℕ) (hm : 1 ≤ m) :
    is_bit_prior (bit_persuasion_even_prior m)
Source
arXiv:2606.22226
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • bit_persuasion_even_coordThe type of coordinates of the two-layer prior for 2m states, defined as the coproduct type of ({A : Finset (Fin (2 * m)) // A.card = m -…
  • bit_persuasion_even_priorThe function bit_persuasion_even_prior m of type (bit_persuasion_even_coord m → Bool) → ℝ mapping each configuration x to the sum over all…
  • is_bit_priorA probability distribution on {0,1}^ι.
  • bit_persuasion_even_stateThe bit-vector state corresponding to s ∈ Fin (2m) in the two-layer construction, where coordinate c is 1 if and only if s is an element…
Used by 1

Read back from the Lean

For every natural number $m$ such that $1 \le m$, the function bit_persuasion_even_prior m satisfies is_bit_prior, meaning that it defines a probability distribution on the type of boolean configurations bit_persuasion_even_coord m → Bool (it takes non-negative values for all configurations and sums to $1$ over all configurations).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To prove that bit_persuasion_even_prior m is a valid probability distribution (a bit prior), the argument directly verifies non-negativity and total probability 1. Non-negativity holds because each term in the sum defining the prior is either 1 / (2m) ≥ 0 (since m ≥ 1) or 0. The total probability is evaluated by swapping the double sum: because every state maps to a unique bit string, the inner sum collapses to 1 / (2m), and summing this constant over all 2m states yields (2m) * (1 / (2m)) = 1.

  1. The prior is non-negative everywhere: for every bit string x, bit_persuasion_even_prior m x ≥ 0.

    By definition of is_bit_prior, we must verify that the prior is non-negative for every bit string x and that its total sum is 1. The prior at x is defined as a sum over states s ∈ Fin (2m) of an indicator term. By sum_nonneg, it suffices to show that each term in this sum is non-negative. We split into cases on whether bit_persuasion_even_state m s = x. If equality holds, the term is 1 / (2m), which is non-negative by positivity because m ≥ 1. If equality does not hold, the term is 0, which is non-negative by reflexivity (le_refl).

    lines 5–8

    uses sum_nonneg, le_refl

      refine ⟨fun x => sum_nonneg fun s _ => ?_, ?_⟩
      · split_ifs
        · positivity
        · exact le_refl 0
  2. The total probability is rewritten as a double sum with the outer sum over states and the inner sum over bit strings.

    We unfold the definition of bit_persuasion_even_prior, which expresses the total sum as ∑ x, ∑ s, ... Applying sum_comm swaps the order of summation to ∑ s, ∑ x, ..., so that we sum over states s ∈ Fin (2m) on the outside and bit strings x on the inside.

    lines 9–10

    uses sum_comm

      · unfold bit_persuasion_even_prior
        rw [sum_comm]
  3. Evaluating the inner and outer sums reduces the total probability to 2m * (1 / (2m)) = 1.

    For each fixed state s, the condition bit_persuasion_even_state m s = x is satisfied by exactly one bit string x. By sum_ite_eq and Finset.mem_univ, the inner sum collapses to the single value 1 / (2m). The outer sum is then the sum of this constant over all s ∈ Fin (2m). Using Finset.sum_const, card_univ, and Fintype.card_fin, the number of states is 2m, so the sum evaluates to (2m) * (1 / (2m)) via nsmul_eq_mul. Finally, push_cast casts the natural factor 2m to the real numbers.

    lines 11–13

    uses sum_ite_eq, Finset.mem_univ, if_true, Finset.sum_const, card_univ, Fintype.card_fin, nsmul_eq_mul

        simp only [sum_ite_eq, Finset.mem_univ, if_true, Finset.sum_const, card_univ, Fintype.card_fin,
          nsmul_eq_mul]
        push_cast
  4. The total probability equals 1, completing the proof that the distribution is a bit prior.

    Since m ≥ 1, positivity shows that m ≠ 0 as a real number. Using this non-zero hypothesis, field_simp cancels the non-zero factor 2m in 2m * (1 / (2m)), closing the goal 1 = 1.

    lines 14–15

        have hm0 : (m : ℝ) ≠ 0 := by positivity
        field_simp
sum_nonneg
A finite sum of non-negative elements is non-negative.
le_refl
The preorder relation ≤ is reflexive: a ≤ a for every a (here, 0 ≤ 0).
sum_comm
The order of summation in a finite double sum can be swapped: ∑ x ∈ s, ∑ y ∈ t, f x y = ∑ y ∈ t, ∑ x ∈ s, f x y.
sum_ite_eq
Summing an indicator of the form (if a = x then b x else 0) over x in a finite set s evaluates to b a if a ∈ s and 0 otherwise.
Finset.mem_univ
Every element of a finite type belongs to the universal finset univ.
if_true
A conditional expression if True then t else e simplifies to t.
Finset.sum_const
Summing a constant value b over a finset s equals the cardinality |s| times b.
card_univ
The cardinality of Finset.univ for a finite type is the type's cardinality Fintype.card.
Fintype.card_fin
The cardinality of the finite type Fin n is n.
nsmul_eq_mul
Scalar multiplication n • a by a natural number n equals the algebraic product n * a.

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

open Finset in/-- For m ≥ 1, the two-layer prior on 2m states is a valid probability distribution on bit strings. -/theorem bit_persuasion_even_prior_is_bit_prior (m : ℕ) (hm : 1 ≤ m) :    is_bit_prior (bit_persuasion_even_prior m) := by  refine ⟨fun x => sum_nonneg fun s _ => ?_, ?_⟩  · split_ifs    · positivity    · exact le_refl 0  · unfold bit_persuasion_even_prior    rw [sum_comm]    simp only [sum_ite_eq, Finset.mem_univ, if_true, Finset.sum_const, card_univ, Fintype.card_fin,      nsmul_eq_mul]    push_cast    have hm0 : (m : ℝ) ≠ 0 := by positivity    field_simp
See it in the graphDiscuss this resultChallenge it