AFTD Auto-Formalizing Theoretical Domains

bit_persuasion_even_scheme_obedient

theoremverified

For every natural number m ≥ 1, bit_persuasion_even_scheme m is an obedient direct scheme for bit_persuasion_even_prior m (is_obedient_direct_scheme (bit_persuasion_even_prior m) (bit_persuasion_even_scheme m)).

Statement

open Finset in
theorem bit_persuasion_even_scheme_obedient (m : ℕ) (hm : 1 ≤ m) :
    is_obedient_direct_scheme (bit_persuasion_even_prior m) (bit_persuasion_even_scheme m)
Source
arXiv:2606.22226
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • 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…
  • bit_persuasion_even_schemeThe direct signaling scheme bit_persuasion_even_scheme m of type (bit_persuasion_even_coord m → Bool) → (bit_persuasion_even_coord m →…
  • is_obedient_direct_schemeAn obedient direct scheme for the prior μ on {0,1}^ι.
  • persuasion_pair_or_scheme_obedientThe pair-OR scheme of a nonnegative symmetric coupling with first marginal μ is obedient.
  • 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…
  • bit_persuasion_even_couplingThe function bit_persuasion_even_coupling m of type (bit_persuasion_even_coord m → Bool) → (bit_persuasion_even_coord m → Bool) → ℝ…

Read back from the Lean

For every natural number $m$ such that $1 \le m$, the direct signaling scheme bit_persuasion_even_scheme m is obedient with respect to the prior distribution bit_persuasion_even_prior m (that is, is_obedient_direct_scheme (bit_persuasion_even_prior m) (bit_persuasion_even_scheme m) holds).

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 show that the pair-OR signaling scheme for the even-layer construction is obedient, the proof applies the general criterion persuasion_pair_or_scheme_obedient, which reduces obedience to three properties of the underlying coupling: non-negativity, symmetry, and marginal compatibility with the prior. Non-negativity holds because each non-zero term in the coupling is positive for m ≥ 1, and symmetry follows from the symmetry of the indicator conditions under exchanging the index pair (s, t). Marginal compatibility is established by collapsing the inner sum over states y to an indicator that s ≠ t, and then counting the 2 * m - 1 indices t distinct from s, so that the normalization factor (2 * m - 1) / (2 * m * (2 * m - 1)) simplifies to the prior weight 1 / (2 * m).

  1. For any index s ∈ Fin (2 * m), the number of indices t ∈ Fin (2 * m) distinct from s is 2 * m - 1.

    The subset of elements t distinct from s is equal to the universe with s removed, univ.erase s, by set extensionality and symmetry of inequality (ne_comm). Removing an element from a finite set decreases its cardinality by 1 (card_erase_of_mem), and the total size of Fin (2 * m) is 2 * m (card_univ, Fintype.card_fin), yielding 2 * m - 1.

    lines 5–8

    uses ne_comm, card_erase_of_mem, mem_univ, card_univ, Fintype.card_fin

      have : (univ.filter (fun t : Fin (2 * m) => s ≠ t)) = univ.erase s := by
        ext t
        simp [ne_comm]
      rw [this, card_erase_of_mem (mem_univ s), card_univ, Fintype.card_fin]
  2. The coupling is non-negative for all states x, y when m ≥ 1.

    Unfolding bit_persuasion_even_coupling, the coupling is a double sum of conditional expressions over indices s and t. Because a sum of non-negative terms is non-negative (sum_nonneg), it suffices to check each term: if the indicator fails, the term is 0; if it holds, the term is 1 / (2 * m * (2 * m - 1)), which is strictly positive because m ≥ 1 implies 2 * m > 0 and 2 * m - 1 > 0.

    lines 13–21

    uses sum_nonneg

      unfold bit_persuasion_even_coupling
      apply sum_nonneg; intro s _
      apply sum_nonneg; intro t _
      split_ifs
      · have hm1 : (1 : ℝ) ≤ m := by exact_mod_cast hm
        have hpos1 : (0 : ℝ) < 2 * m := by linarith
        have hpos2 : (0 : ℝ) < 2 * m - 1 := by linarith
        positivity
      · rfl
  3. The coupling is symmetric: the probability assigned to (x, y) equals that assigned to (y, x).

    Unfolding the definition and exchanging the sums over s and t using sum_comm, the indicator condition that t ≠ s with states x and y is logically equivalent to s ≠ t with states y and x. Thus, by case analysis on whether this condition holds (if_pos, if_neg), the summands agree pointwise, and sum_congr equates the two sums.

    lines 26–37

    uses sum_comm, sum_congr, if_pos, if_neg

      unfold bit_persuasion_even_coupling
      rw [sum_comm]
      apply sum_congr rfl; intro s _
      apply sum_congr rfl; intro t _
      by_cases h : t ≠ s ∧ bit_persuasion_even_state m t = x ∧ bit_persuasion_even_state m s = y
      · have h' : s ≠ t ∧ bit_persuasion_even_state m s = y ∧ bit_persuasion_even_state m t = x :=
          ⟨h.1.symm, h.2.2, h.2.1⟩
        rw [if_pos h, if_pos h']
      · have h' : ¬(s ≠ t ∧ bit_persuasion_even_state m s = y ∧ bit_persuasion_even_state m t = x) := by
          rintro ⟨h1, h2, h3⟩
          exact h ⟨h1.symm, h3, h2⟩
        rw [if_neg h, if_neg h']
  4. For fixed s such that state(s) = x, summing the coupling summand over y collapses to 1 / (2 * m * (2 * m - 1)) when s ≠ t, and 0 when s = t.

    Unfolding the coupling and prior, we swap the sum over y to the inside using sum_comm. When state(s) = x (handled by if_pos), we evaluate the inner sum over y for each t: if s ≠ t, the condition specifies that y must match state(t), so the sum over all y collapses via sum_ite_eq to the single term 1 / (2 * m * (2 * m - 1)); if s = t, the condition s ≠ t is false, leaving a sum of zeros.

    lines 42–57

    uses sum_comm, sum_congr, if_pos, true_and, if_true, ne_eq, not_false_eq_true, sum_ite_eq

      classical
      unfold bit_persuasion_even_coupling bit_persuasion_even_prior
      rw [sum_comm]
      apply sum_congr rfl; intro s _
      rw [sum_comm]
      by_cases hs : bit_persuasion_even_state m s = x
      · rw [if_pos hs]
        have e : ∀ t, (∑ y, if s ≠ t ∧ bit_persuasion_even_state m s = x ∧
            bit_persuasion_even_state m t = y then 1 / ((2 * m : ℝ) * (2 * m - 1)) else 0) =
            if s ≠ t then 1 / ((2 * m : ℝ) * (2 * m - 1)) else 0 := by
          intro t
          by_cases ht : s ≠ t
          · simp only [ht, hs, true_and, if_true, ne_eq, not_false_eq_true]
            rw [sum_ite_eq]
            simp
          · simp [ht]
  5. Summing the coupling over y recovers the prior: ∑ y, coupling(x, y) = prior(x).

    When state(s) = x, the sum over t simplifies to a constant sum over the {t | s ≠ t}, which has cardinality 2 * m - 1 by bit_persuasion_even_scheme_obedient_card_ne. The product (2 * m - 1) * (1 / (2 * m * (2 * m - 1))) simplifies to 1 / (2 * m). When state(s) ≠ x, both sides are zero (sum_eq_zero, if_neg).

    lines 58–69

    uses sum_congr, sum_filter, Finset.sum_const, bit_persuasion_even_scheme_obedient_card_ne, nsmul_eq_mul, if_neg, sum_eq_zero

        rw [sum_congr rfl (fun t _ => e t), ← sum_filter, Finset.sum_const,
          bit_persuasion_even_scheme_obedient_card_ne, nsmul_eq_mul]
        have hm1 : (1 : ℝ) ≤ m := by exact_mod_cast hm
        have h1 : (2 * (m : ℝ) - 1 : ℝ) ≠ 0 := by linarith
        have h2 : (2 * (m : ℝ) : ℝ) ≠ 0 := by linarith
        have hle : 1 ≤ 2 * m := by omega
        push_cast [hle]
        field_simp
      · rw [if_neg hs]
        apply sum_eq_zero; intro t _
        apply sum_eq_zero; intro y _
        simp [hs]
  6. The signaling scheme bit_persuasion_even_scheme m is an obedient direct scheme for bit_persuasion_even_prior m.

    The result follows directly by applying persuasion_pair_or_scheme_obedient, which establishes that any pair-OR scheme built from a non-negative, symmetric coupling whose marginal matches the prior is obedient, using the three properties established in the preceding lemmas.

    lines 75–78

    uses persuasion_pair_or_scheme_obedient, bit_persuasion_even_scheme_obedient_coupling_nonneg, bit_persuasion_even_scheme_obedient_coupling_symm, bit_persuasion_even_scheme_obedient_coupling_marginal

      exact persuasion_pair_or_scheme_obedient _ _
        (bit_persuasion_even_scheme_obedient_coupling_nonneg m hm)
        (bit_persuasion_even_scheme_obedient_coupling_symm m)
        (bit_persuasion_even_scheme_obedient_coupling_marginal m hm)
ne_comm
Inequality is symmetric: a ≠ b if and only if b ≠ a.
card_erase_of_mem
Removing an element from a finite set decreases its cardinality by 1.
mem_univ
Every element of a finite type belongs to the universal finset.
card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin
The finite type Fin n has exactly n elements.
sum_nonneg
A sum of non-negative real numbers is non-negative.
sum_comm
The order of two finite summations can be swapped.
sum_congr
Two sums are equal if their index sets are equal and their summands agree at every index.
if_pos
A conditional expression equals its then-branch when the condition is true.
if_neg
A conditional expression equals its else-branch when the condition is false.
true_and
The conjunction of True and p simplifies to p.
if_true
A conditional with condition True evaluates to the then-branch.
ne_eq
The notation a ≠ b is defined as the negation of a = b.
not_false_eq_true
The negation of False is True.
sum_ite_eq
Summing an indicator that tests equality to a selects the value at a if a belongs to the set, and 0 otherwise.
sum_filter
A sum over a filtered sub-finset equals the sum of the conditional indicator over the entire finset.
Finset.sum_const
The sum of a constant value over a finite set equals the cardinality of the set multiplied by that constant.
bit_persuasion_even_scheme_obedient_card_ne
In Fin (2 * m), the number of elements distinct from a fixed element s is 2 * m - 1.
nsmul_eq_mul
Natural number scalar multiplication in a semiring equals multiplication by the natural number cast into the semiring.
sum_eq_zero
If every summand in a finite sum is zero, the sum is zero.
persuasion_pair_or_scheme_obedient
A pair-OR signaling scheme constructed from a coupling ν is an obedient direct scheme for prior μ, provided ν is non-negative, symmetric, and has μ as its marginal.
bit_persuasion_even_scheme_obedient_coupling_nonneg
The coupling for the even-layer construction takes only non-negative values when m ≥ 1.
bit_persuasion_even_scheme_obedient_coupling_symm
The coupling for the even-layer construction is symmetric under swapping its two arguments.
bit_persuasion_even_scheme_obedient_coupling_marginal
Summing the coupling over the second state recovers the prior distribution for the even-layer construction when m ≥ 1.

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 Finsetlemma bit_persuasion_even_scheme_obedient_card_ne (m : ℕ) (s : Fin (2 * m)) :    (univ.filter (fun t : Fin (2 * m) => s ≠ t)).card = 2 * m - 1 := by  have : (univ.filter (fun t : Fin (2 * m) => s ≠ t)) = univ.erase s := by    ext t    simp [ne_comm]  rw [this, card_erase_of_mem (mem_univ s), card_univ, Fintype.card_fin]lemma bit_persuasion_even_scheme_obedient_coupling_nonneg (m : ℕ) (hm : 1 ≤ m)    (x y : bit_persuasion_even_coord m → Bool) :    0 ≤ bit_persuasion_even_coupling m x y := by  unfold bit_persuasion_even_coupling  apply sum_nonneg; intro s _  apply sum_nonneg; intro t _  split_ifs  · have hm1 : (1 : ℝ) ≤ m := by exact_mod_cast hm    have hpos1 : (0 : ℝ) < 2 * m := by linarith    have hpos2 : (0 : ℝ) < 2 * m - 1 := by linarith    positivity  · rfllemma bit_persuasion_even_scheme_obedient_coupling_symm (m : ℕ)    (x y : bit_persuasion_even_coord m → Bool) :    bit_persuasion_even_coupling m x y = bit_persuasion_even_coupling m y x := by  unfold bit_persuasion_even_coupling  rw [sum_comm]  apply sum_congr rfl; intro s _  apply sum_congr rfl; intro t _  by_cases h : t ≠ s ∧ bit_persuasion_even_state m t = x ∧ bit_persuasion_even_state m s = y  · have h' : s ≠ t ∧ bit_persuasion_even_state m s = y ∧ bit_persuasion_even_state m t = x :=      ⟨h.1.symm, h.2.2, h.2.1⟩    rw [if_pos h, if_pos h']  · have h' : ¬(s ≠ t ∧ bit_persuasion_even_state m s = y ∧ bit_persuasion_even_state m t = x) := by      rintro ⟨h1, h2, h3⟩      exact h ⟨h1.symm, h3, h2⟩    rw [if_neg h, if_neg h']lemma bit_persuasion_even_scheme_obedient_coupling_marginal (m : ℕ) (hm : 1 ≤ m)    (x : bit_persuasion_even_coord m → Bool) :    ∑ y, bit_persuasion_even_coupling m x y = bit_persuasion_even_prior m x := by  classical  unfold bit_persuasion_even_coupling bit_persuasion_even_prior  rw [sum_comm]  apply sum_congr rfl; intro s _  rw [sum_comm]  by_cases hs : bit_persuasion_even_state m s = x  · rw [if_pos hs]    have e : ∀ t, (∑ y, if s ≠ t ∧ bit_persuasion_even_state m s = x ∧        bit_persuasion_even_state m t = y then 1 / ((2 * m : ℝ) * (2 * m - 1)) else 0) =        if s ≠ t then 1 / ((2 * m : ℝ) * (2 * m - 1)) else 0 := by      intro t      by_cases ht : s ≠ t      · simp only [ht, hs, true_and, if_true, ne_eq, not_false_eq_true]        rw [sum_ite_eq]        simp      · simp [ht]    rw [sum_congr rfl (fun t _ => e t), ← sum_filter, Finset.sum_const,      bit_persuasion_even_scheme_obedient_card_ne, nsmul_eq_mul]    have hm1 : (1 : ℝ) ≤ m := by exact_mod_cast hm    have h1 : (2 * (m : ℝ) - 1 : ℝ) ≠ 0 := by linarith    have h2 : (2 * (m : ℝ) : ℝ) ≠ 0 := by linarith    have hle : 1 ≤ 2 * m := by omega    push_cast [hle]    field_simp  · rw [if_neg hs]    apply sum_eq_zero; intro t _    apply sum_eq_zero; intro y _    simp [hs]open Finset in/-- For m ≥ 1, the pair-OR signaling scheme for the two-layer construction is obedient. -/theorem bit_persuasion_even_scheme_obedient (m : ℕ) (hm : 1 ≤ m) :    is_obedient_direct_scheme (bit_persuasion_even_prior m) (bit_persuasion_even_scheme m) := by  exact persuasion_pair_or_scheme_obedient _ _    (bit_persuasion_even_scheme_obedient_coupling_nonneg m hm)    (bit_persuasion_even_scheme_obedient_coupling_symm m)    (bit_persuasion_even_scheme_obedient_coupling_marginal m hm)
See it in the graphDiscuss this resultChallenge it