AFTD Auto-Formalizing Theoretical Domains

bit_persuasion_even_prior_is_uniform

theoremverified

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.

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

    lines 4–12

    uses card_sdiff_of_subset, subset_univ, card_univ, Fintype.card_fin, card_pair, exists_subset_card_eq

      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
  2. 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$.

    lines 13–31

    uses mem_sdiff, mem_insert, mem_singleton, Or.inl, Or.inr, card_insert_of_notMem, mem_insert_self, not_or, Ne.symm

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

    lines 32–43

      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
  4. 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)$.

    lines 48–55

    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
  5. 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`.

    lines 62–66

    uses if_neg, sum_congr, sum_const_zero

      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]
  6. 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`.

    lines 72–73

    uses bit_persuasion_even_prior_is_bit_prior

      unfold is_uniform_bit_prior
      refine ⟨bit_persuasion_even_prior_is_bit_prior m hm, ?_, ?_⟩
  7. 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$.

    lines 74–91

    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]
  8. 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})$.

    lines 92–102

    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.

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