bit_persuasion_even_prior_is_uniform
For every natural number m with 1 ≤ m, the function bit_persuasion_even_prior m is a uniform bit prior on 2 * m states (is_uniform_bit_prior (2 * m) (bit_persuasion_even_prior m)).
Statement
open Finset in theorem bit_persuasion_even_prior_is_uniform (m : ℕ) (hm : 1 ≤ m) : is_uniform_bit_prior (2 * m) (bit_persuasion_even_prior m)
- Source
- OP-1547; arXiv:2606.22226
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- is_uniform_bit_priorA real-valued function μ on ι → Bool is a uniform bit prior on k states if it is a bit prior whose support {x | μ x ≠ 0} has cardinality k…
- 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…
- bit_persuasion_even_prior_is_bit_priorFor every natural number m ≥ 1, the function bit_persuasion_even_prior m is a bit prior (is_bit_prior (bit_persuasion_even_prior m)).
- is_bit_priorA probability distribution on {0,1}^ι.
- 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_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…
Read back from the Lean
For every natural number $m$ satisfying $1 \le m$, the prior bit_persuasion_even_prior m is a uniform bit prior of size $2m$ (i.e., it satisfies is_uniform_bit_prior (2 * m)). That is, it is a valid probability distribution on the space of bit configurations bit_persuasion_even_coord m → Bool, its support has cardinality $2m$, and on its support it evaluates to $1 / (2m)$.
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 uniform bit prior on $2m$ states, the theorem establishes that it is a valid prior, that its support has size $2m$, and that it takes the constant value $1/(2m)$ on its support. The core step is proving that the state embedding `bit_persuasion_even_state m` is injective: for any two distinct states $s_1 \ne s_2$, one can construct an $m$-element subset containing $s_1$ but not $s_2$, producing a coordinate where their bit values differ. Because the state mapping is injective, the support of the prior is precisely the image of the $2m$ states, each assigned probability $1/(2m)$ while every other bit vector receives probability 0.
To prove injectivity of `bit_persuasion_even_state m`, assume for contradiction that two distinct states $s_1 \ne s_2$ produce identical state vectors, and find a subset $t \subseteq \text{univ} \setminus \{s_1, s_2\}$ of cardinality $m - 1$.
Assume $s_1 \ne s_2$ but their assigned state bit vectors are identical. The complement of the two-element set $\{s_1, s_2\}$ in the universe of $2m$ states has cardinality $2m - 2$. Since $1 \le m$, we have $m - 1 \le 2m - 2$, so there exists a subset $t \subseteq \text{univ} \setminus \{s_1, s_2\}$ of size exactly $m - 1$.
uses
card_sdiff_of_subset,subset_univ,card_univ,Fintype.card_fin,card_pair,exists_subset_card_eqintro s1 s2 h by_contra hne have h_univ : (univ \ {s1, s2} : Finset (Fin (2 * m))).card = 2 * m - 2 := by rw [card_sdiff_of_subset (subset_univ _)] rw [card_univ, Fintype.card_fin, card_pair hne] have h_le : m - 1 ≤ (univ \ {s1, s2} : Finset (Fin (2 * m))).card := by rw [h_univ] omega obtain ⟨t, ht_sub, ht_card⟩ := exists_subset_card_eq h_le
Neither $s_1$ nor $s_2$ belongs to $t$, and the set $B = \{s_1\} \cup t$ has cardinality $m$, with $s_1 \in B$ and $s_2 \notin B$.
Because $t$ is contained in the complement of $\{s_1, s_2\}$, neither $s_1$ nor $s_2$ belongs to $t$. Defining $B$ by inserting $s_1$ into $t$, its cardinality is $(m - 1) + 1 = m$. By definition, $s_1 \in B$, while $s_2 \notin B$ because $s_2 \ne s_1$ and $s_2 \notin t$.
uses
mem_sdiff,mem_insert,mem_singleton,Or.inl,Or.inr,card_insert_of_notMem,mem_insert_self,not_or,Ne.symmhave hs1_notin_t : s1 ∉ t := by intro hs1 have := ht_sub hs1 rw [mem_sdiff, mem_insert, mem_singleton] at this exact this.2 (Or.inl rfl) have hs2_notin_t : s2 ∉ t := by intro hs2 have := ht_sub hs2 rw [mem_sdiff, mem_insert, mem_singleton] at this exact this.2 (Or.inr rfl) let B : Finset (Fin (2 * m)) := insert s1 t have hB_card : B.card = m := by dsimp [B] rw [card_insert_of_notMem hs1_notin_t, ht_card] omega have hs1_in_B : s1 ∈ B := mem_insert_self s1 t have hs2_notin_B : s2 ∉ B := by rw [mem_insert, not_or] exact ⟨Ne.symm hne, hs2_notin_t⟩
Evaluating the two states at the coordinate corresponding to $B$ yields a contradiction, establishing injectivity.
Since $0 < 3m$, we construct a coordinate $c$ in the second layer of the coordinate space associated with the $m$-element subset $B$ and index 0. By definition of `bit_persuasion_even_state`, the bit value at $c$ indicates whether a state belongs to $B$: it is `true` for $s_1$ because $s_1 \in B$, but `false` for $s_2$ because $s_2 \notin B$. However, the two state vectors were assumed equal, forcing `true = false`, a contradiction.
have hj : 0 < 3 * m := by omega let c : bit_persuasion_even_coord m := Sum.inr (⟨B, hB_card⟩, ⟨0, hj⟩) have h1 : bit_persuasion_even_state m s1 c = true := by dsimp [bit_persuasion_even_state, c] simp [hs1_in_B] have h2 : bit_persuasion_even_state m s2 c = false := by dsimp [bit_persuasion_even_state, c] simp [hs2_notin_B] have hc : bit_persuasion_even_state m s1 c = bit_persuasion_even_state m s2 c := by rw [h] rw [h1, h2] at hc cases hc
For every state $s \in \text{Fin}(2m)$, the prior evaluated at $\text{state}(s)$ is $1 / (2m)$.
Unfolding `bit_persuasion_even_prior`, the value is a sum over all states $s'$ of $1 / (2m)$ when $\text{state}(s') = \text{state}(s)$ and 0 otherwise. By injectivity of `bit_persuasion_even_state`, the condition $\text{state}(s') = \text{state}(s)$ is equivalent to $s' = s$. The sum therefore collapses to the single term where $s' = s$, which evaluates to $1 / (2m)$.
uses
bit_persuasion_even_prior_is_uniform_state_injective,sum_ite_eq'unfold bit_persuasion_even_prior have hinj := bit_persuasion_even_prior_is_uniform_state_injective m hm have h_eq : ∀ s', (bit_persuasion_even_state m s' = bit_persuasion_even_state m s) ↔ s' = s := by intro s' exact hinj.eq_iff simp_rw [h_eq] rw [sum_ite_eq'] simp
For any bit vector $x$ that does not equal $\text{state}(s)$ for any state $s$, the prior evaluated at $x$ is 0.
Unfolding `bit_persuasion_even_prior`, each term in the sum over $s$ tests whether $\text{state}(s) = x$. Since by assumption $\text{state}(s) \ne x$ for all $s$, every summand evaluates to 0 by `if_neg`. The sum of zeros is 0 by `sum_const_zero`.
uses
if_neg,sum_congr,sum_const_zerounfold bit_persuasion_even_prior have : ∀ s ∈ (univ : Finset (Fin (2 * m))), (if bit_persuasion_even_state m s = x then 1 / (2 * (m : ℝ)) else 0) = 0 := by intro s _ rw [if_neg (hx s)] rw [sum_congr rfl this, sum_const_zero]
Verify that the prior is a valid bit prior, reducing the theorem to checking the cardinality and uniformity of its support.
Unfolding `is_uniform_bit_prior`, we must show three properties: that `bit_persuasion_even_prior m` is a bit prior (a probability distribution on coordinate bit vectors), that its support has size $2m$, and that it takes the uniform value $1 / (2m)$ on all elements of its support. The first property is supplied directly by `bit_persuasion_even_prior_is_bit_prior`.
uses
bit_persuasion_even_prior_is_bit_priorunfold is_uniform_bit_prior refine ⟨bit_persuasion_even_prior_is_bit_prior m hm, ?_, ?_⟩
The support of the prior has cardinality $2m$.
We show that the support $\{x \mid \mu(x) \ne 0\}$ equals the image of `bit_persuasion_even_state m`. Any vector outside the image has prior 0 by `bit_persuasion_even_prior_is_uniform_prior_eq_zero_of_not_mem`. Conversely, any vector in the image has prior $1 / (2m) > 0$ by `bit_persuasion_even_prior_is_uniform_prior_eq_of_mem` and positivity of $m$. Since the state mapping is injective by `bit_persuasion_even_prior_is_uniform_state_injective`, the image has cardinality equal to that of $\text{Fin}(2m)$, which is $2m$.
uses
bit_persuasion_even_prior_is_uniform_prior_eq_zero_of_not_mem,bit_persuasion_even_prior_is_uniform_prior_eq_of_mem,card_image_of_injective,bit_persuasion_even_prior_is_uniform_state_injective,card_univ,Fintype.card_fin· have h_supp : (univ.filter (fun x => bit_persuasion_even_prior m x ≠ 0)) = univ.image (bit_persuasion_even_state m) := by ext x simp only [mem_filter, mem_univ, true_and, mem_image] constructor · intro hne by_contra h_not apply hne apply bit_persuasion_even_prior_is_uniform_prior_eq_zero_of_not_mem intro s hs exact h_not ⟨s, hs⟩ · rintro ⟨s, _, rfl⟩ rw [bit_persuasion_even_prior_is_uniform_prior_eq_of_mem m hm s] have hm0 : (m : ℝ) ≠ 0 := by positivity positivity rw [h_supp] rw [card_image_of_injective _ (bit_persuasion_even_prior_is_uniform_state_injective m hm)] rw [card_univ, Fintype.card_fin]
On every element of its support, the prior evaluates to $1 / (2m)$.
Given any bit vector $x$ with non-zero prior probability, $x$ must be in the image of `bit_persuasion_even_state` (otherwise its prior would be 0 by `bit_persuasion_even_prior_is_uniform_prior_eq_zero_of_not_mem`, a contradiction). Writing $x = \text{state}(s)$ for some state $s$, `bit_persuasion_even_prior_is_uniform_prior_eq_of_mem` evaluates the prior at $x$ to $1 / (2m)$, which equals $1 / (2 * m : \mathbb{R})$.
uses
bit_persuasion_even_prior_is_uniform_prior_eq_zero_of_not_mem,bit_persuasion_even_prior_is_uniform_prior_eq_of_mem· intro x hx have h_ex : ∃ s, bit_persuasion_even_state m s = x := by by_contra h_not apply hx apply bit_persuasion_even_prior_is_uniform_prior_eq_zero_of_not_mem intro s hs exact h_not ⟨s, hs⟩ obtain ⟨s, rfl⟩ := h_ex rw [bit_persuasion_even_prior_is_uniform_prior_eq_of_mem m hm s] push_cast rfl
card_sdiff_of_subset- If $s \subseteq t$ for finite sets, then $|t \setminus s| = |t| - |s|$.
subset_univ- Every finite set of elements of a finite type is a subset of the universal set of that type.
card_univ- The cardinality of the universal finset `Finset.univ` equals the cardinality of the underlying finite type.
Fintype.card_fin- The finite type `Fin n` has cardinality $n$.
card_pair- A pair of distinct elements has cardinality 2.
exists_subset_card_eq- If $n \le |s|$ for a finite set $s$, then $s$ contains a subset of cardinality $n$.
mem_sdiff- An element belongs to $s \setminus t$ if and only if it belongs to $s$ and not to $t$.
mem_insert- An element belongs to the insert $\{b\} \cup s$ if and only if it equals $b$ or belongs to $s$.
mem_singleton- An element belongs to the singleton $\{a\}$ if and only if it equals $a$.
Or.inl- From a proposition $a$, one can deduce the disjunction $a \lor b$.
Or.inr- From a proposition $b$, one can deduce the disjunction $a \lor b$.
card_insert_of_notMem- Inserting an element not already present into a finite set increases its cardinality by 1.
mem_insert_self- An element $a$ always belongs to the set $\{a\} \cup s$.
not_or- The negation of a disjunction $p \lor q$ is equivalent to $\neg p \land \neg q$.
Ne.symm- Inequality is symmetric: if $a \ne b$, then $b \ne a$.
bit_persuasion_even_prior_is_uniform_state_injective- For $m \ge 1$, the state mapping `bit_persuasion_even_state m` from `Fin (2 * m)` to coordinate bit vectors is injective.
sum_ite_eq'- A sum over a finite set whose summands test equality with an element $a$ simplifies to the value at $a$ if $a$ belongs to the set, and 0 otherwise.
if_neg- An if-then-else expression evaluates to its false/else branch when the condition is false.
sum_congr- Two sums over finite sets are equal if the sets are equal and the summands agree on every element.
sum_const_zero- The sum of zeros over any finite set is 0.
bit_persuasion_even_prior_is_bit_prior- For $m \ge 1$, `bit_persuasion_even_prior m` is a valid probability distribution on coordinate bit vectors (nonnegative and summing to 1).
bit_persuasion_even_prior_is_uniform_prior_eq_zero_of_not_mem- The prior assigns probability 0 to any bit vector that is not the state vector of some state $s$.
bit_persuasion_even_prior_is_uniform_prior_eq_of_mem- For $m \ge 1$, the prior evaluates to $1 / (2m)$ at the state vector of every state $s \in \text{Fin}(2m)$.
card_image_of_injective- The image of a finite set under an injective function has the same cardinality as the original set.
- The coordinate space `bit_persuasion_even_coord m` is a disjoint union of two layers; the injectivity proof selects a coordinate in the second layer (`Sum.inr`), whose elements correspond to subsets of size $m$.
- Linear arithmetic inequalities (such as $m - 1 \le 2m - 2$ given $1 \le m$) are verified automatically by the `omega` tactic.
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 inlemma bit_persuasion_even_prior_is_uniform_state_injective (m : ℕ) (hm : 1 ≤ m) : Function.Injective (bit_persuasion_even_state m) := by intro s1 s2 h by_contra hne have h_univ : (univ \ {s1, s2} : Finset (Fin (2 * m))).card = 2 * m - 2 := by rw [card_sdiff_of_subset (subset_univ _)] rw [card_univ, Fintype.card_fin, card_pair hne] have h_le : m - 1 ≤ (univ \ {s1, s2} : Finset (Fin (2 * m))).card := by rw [h_univ] omega obtain ⟨t, ht_sub, ht_card⟩ := exists_subset_card_eq h_le have hs1_notin_t : s1 ∉ t := by intro hs1 have := ht_sub hs1 rw [mem_sdiff, mem_insert, mem_singleton] at this exact this.2 (Or.inl rfl) have hs2_notin_t : s2 ∉ t := by intro hs2 have := ht_sub hs2 rw [mem_sdiff, mem_insert, mem_singleton] at this exact this.2 (Or.inr rfl) let B : Finset (Fin (2 * m)) := insert s1 t have hB_card : B.card = m := by dsimp [B] rw [card_insert_of_notMem hs1_notin_t, ht_card] omega have hs1_in_B : s1 ∈ B := mem_insert_self s1 t have hs2_notin_B : s2 ∉ B := by rw [mem_insert, not_or] exact ⟨Ne.symm hne, hs2_notin_t⟩ have hj : 0 < 3 * m := by omega let c : bit_persuasion_even_coord m := Sum.inr (⟨B, hB_card⟩, ⟨0, hj⟩) have h1 : bit_persuasion_even_state m s1 c = true := by dsimp [bit_persuasion_even_state, c] simp [hs1_in_B] have h2 : bit_persuasion_even_state m s2 c = false := by dsimp [bit_persuasion_even_state, c] simp [hs2_notin_B] have hc : bit_persuasion_even_state m s1 c = bit_persuasion_even_state m s2 c := by rw [h] rw [h1, h2] at hc cases hcopen Finset inlemma bit_persuasion_even_prior_is_uniform_prior_eq_of_mem (m : ℕ) (hm : 1 ≤ m) (s : Fin (2 * m)) : bit_persuasion_even_prior m (bit_persuasion_even_state m s) = 1 / (2 * (m : ℝ)) := by unfold bit_persuasion_even_prior have hinj := bit_persuasion_even_prior_is_uniform_state_injective m hm have h_eq : ∀ s', (bit_persuasion_even_state m s' = bit_persuasion_even_state m s) ↔ s' = s := by intro s' exact hinj.eq_iff simp_rw [h_eq] rw [sum_ite_eq'] simpopen Finset inlemma bit_persuasion_even_prior_is_uniform_prior_eq_zero_of_not_mem (m : ℕ) (x : bit_persuasion_even_coord m → Bool) (hx : ∀ s, bit_persuasion_even_state m s ≠ x) : bit_persuasion_even_prior m x = 0 := by unfold bit_persuasion_even_prior have : ∀ s ∈ (univ : Finset (Fin (2 * m))), (if bit_persuasion_even_state m s = x then 1 / (2 * (m : ℝ)) else 0) = 0 := by intro s _ rw [if_neg (hx s)] rw [sum_congr rfl this, sum_const_zero]open Finset in/-- The two-layer prior on 2m states is a uniform bit prior on 2m states. -/theorem bit_persuasion_even_prior_is_uniform (m : ℕ) (hm : 1 ≤ m) : is_uniform_bit_prior (2 * m) (bit_persuasion_even_prior m) := by unfold is_uniform_bit_prior refine ⟨bit_persuasion_even_prior_is_bit_prior m hm, ?_, ?_⟩ · have h_supp : (univ.filter (fun x => bit_persuasion_even_prior m x ≠ 0)) = univ.image (bit_persuasion_even_state m) := by ext x simp only [mem_filter, mem_univ, true_and, mem_image] constructor · intro hne by_contra h_not apply hne apply bit_persuasion_even_prior_is_uniform_prior_eq_zero_of_not_mem intro s hs exact h_not ⟨s, hs⟩ · rintro ⟨s, _, rfl⟩ rw [bit_persuasion_even_prior_is_uniform_prior_eq_of_mem m hm s] have hm0 : (m : ℝ) ≠ 0 := by positivity positivity rw [h_supp] rw [card_image_of_injective _ (bit_persuasion_even_prior_is_uniform_state_injective m hm)] rw [card_univ, Fintype.card_fin] · intro x hx have h_ex : ∃ s, bit_persuasion_even_state m s = x := by by_contra h_not apply hx apply bit_persuasion_even_prior_is_uniform_prior_eq_zero_of_not_mem intro s hs exact h_not ⟨s, hs⟩ obtain ⟨s, rfl⟩ := h_ex rw [bit_persuasion_even_prior_is_uniform_prior_eq_of_mem m hm s] push_cast rfl