bit_persuasion_even_prior_is_bit_prior
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
- bit_persuasion_even_prior_is_uniformFor every natural number m with 1 ≤ m, the function bit_persuasion_even_prior m is a uniform bit prior on 2 * m states…
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.
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).
uses
sum_nonneg,le_reflrefine ⟨fun x => sum_nonneg fun s _ => ?_, ?_⟩ · split_ifs · positivity · exact le_refl 0
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.
uses
sum_comm· unfold bit_persuasion_even_prior rw [sum_comm]
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.
uses
sum_ite_eq,Finset.mem_univ,if_true,Finset.sum_const,card_univ,Fintype.card_fin,nsmul_eq_mulsimp only [sum_ite_eq, Finset.mem_univ, if_true, Finset.sum_const, card_univ, Fintype.card_fin, nsmul_eq_mul] push_cast
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.
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
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.
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