AFTD Auto-Formalizing Theoretical Domains

finite_weighted_three_binary_hidden_model_has_parent

theoremverified

Subnormalized finite hidden weights for three binary effects yield a joint positive parent.

Statement

theorem finite_weighted_three_binary_hidden_model_has_parent :
  ∀ (n m : ℕ) (Q : Fin m → Matrix (Fin n) (Fin n) ℂ)
    (r : Fin m → ℝ) (p : Fin 3 → Fin m → ℝ) (P : Matrix (Fin n) (Fin n) ℂ),
    (∀ t, (Q t).PosSemidef) → (∑ t, (r t) • Q t) = P →
    (∀ t, 0 ≤ r t) → (∀ j t, 0 ≤ p j t ∧ p j t ≤ r t) →
    ∃ G : (Fin 3 → Bool) → Matrix (Fin n) (Fin n) ℂ,
      (∀ s, (G s).PosSemidef) ∧ (∑ s, G s) = P ∧
      ∀ j : Fin 3, (∑ s, if s j then G s else 0) = ∑ t, (p j t) • Q t
Source
Product-state parent helper for OP-693.
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 2

The proof, explained

The proof establishes that a finite hidden-variable model for three binary measurements admits a joint positive parent measurement by constructing the parent as a mixture of factorized Bernoulli distributions over the hidden states. For unweighted models with response probabilities in [0, 1], each joint effect G(s) is defined by weighting the hidden states Q(t) by the product distribution of three independent Bernoulli variables. The operators G(s) are positive semidefinite as non-negative sums of positive semidefinite matrices, sum to the total operator P because the Bernoulli probabilities sum to 1, and have the correct marginals because the Bernoulli marginals match the individual probabilities. The general weighted case is reduced to the unweighted one by absorbing the weights r(t) into rescaled operators Q'(t) = r(t) Q(t) and normalizing the response probabilities to p'(j, t) = p(j, t) / r(t) when r(t) > 0.

  1. For any probability vector p with components in [0, 1] and any boolean triple s, the product weight w(p, s) is non-negative.

    The product weight is defined as ∏ j, (if s j then p j else 1 - p j). By Finset.prod_nonneg, it suffices to show each factor is non-negative. Splitting on whether s(j) is true or false gives p(j) or 1 - p(j), both of which are non-negative since 0 ≤ p(j) ≤ 1.

    lines 11–13

    uses Finset.prod_nonneg

      apply Finset.prod_nonneg
      intro j hj
      split <;> linarith [hp j]
  2. The sum of the product weights w(p, s) over all boolean triples s equals 1.

    Applying Finset.sum_prod_piFinset exchanges the sum over boolean functions and the product over j ∈ Fin 3, rewriting the sum of products into the product of sums ∏ j, (p(j) + (1 - p(j))). Since each sum evaluates to 1 by Fintype.sum_bool, the product is 1.

    lines 17–20

    uses Finset.sum_prod_piFinset, Fintype.piFinset_univ, Fintype.sum_bool

      have hh := Finset.sum_prod_piFinset (ι := Fin 3) (Finset.univ : Finset Bool)
        (fun j b => if b then p j else 1-p j)
      simp only [Fintype.piFinset_univ] at hh
      simpa [in767_weightedproof_probability_weight, Fintype.sum_bool] using hh
  3. For each measurement j ∈ Fin 3, the sum of weights over configurations where s(j) is true equals p(j). automation

    We express the indicator weight as a product of auxiliary factors f(i, s(i)) where setting i = j replaces 1 - p(j) with 0. By Finset.sum_prod_piFinset, the sum over all configurations factors into ∏ i, ∑ b, f(i, b). For i = j the sum is p(j), and for i ≠ j the sum is p(i) + (1 - p(i)) = 1, leaving p(j). Lean checks this via exhaustive case split across all 3 indices and 8 boolean values.

    lines 24–32

    uses Fin.prod_univ_three, Finset.sum_prod_piFinset, Fintype.piFinset_univ, Fintype.sum_bool

      let f : Fin 3 → Bool → ℝ := fun i b => if i=j then if b then p i else 0 else if b then p i else 1-p i
      have hprod (s : Fin 3 → Bool) : (∏ i, f i (s i)) =
          if s j then in767_weightedproof_probability_weight p s else 0 := by
        fin_cases j <;> cases h0 : s 0 <;> cases h1 : s 1 <;> cases h2 : s 2 <;>
          simp [f, in767_weightedproof_probability_weight, Fin.prod_univ_three, h0,h1,h2]
      have hh := Finset.sum_prod_piFinset (ι := Fin 3) (Finset.univ : Finset Bool) f
      simp only [Fintype.piFinset_univ] at hh
      simp_rw [hprod] at hh
      fin_cases j <;> simp [f, Fintype.sum_bool, Fin.prod_univ_three] at hh ⊢ <;> linarith
  4. In the unweighted model, the candidate parent operators G(s) are positive semidefinite.

    Define G(s) = ∑ t, w(p(·, t), s) • Q(t). We show by finite-set induction (Finset.induction_on) that any partial sum over a subset T of hidden states is positive semidefinite. The empty sum is 0, which is positive semidefinite by Matrix.PosSemidef.zero. For the inductive step, adjoining t adds a non-negative scalar multiple of the positive semidefinite matrix Q(t) to the previous sum, preserving positive semidefiniteness.

    lines 42–53

    uses Finset.induction_on, Matrix.PosSemidef.zero, Finset.sum_insert, in767_weightedproof_probability_weight_nonneg, Finset.univ

      let G : (Fin 3 → Bool) → Matrix (Fin n) (Fin n) ℂ := fun s =>
        ∑ t, in767_weightedproof_probability_weight (fun j => p j t) s • Q t
      refine ⟨G, ?_, ?_, ?_⟩
      · intro s
        change (∑ t, in767_weightedproof_probability_weight (fun j => p j t) s • Q t).PosSemidef
        have H (T : Finset (Fin m)) : (∑ t ∈ T, in767_weightedproof_probability_weight (fun j => p j t) s • Q t).PosSemidef := by
          induction T using Finset.induction_on with
          | empty => simpa using (Matrix.PosSemidef.zero : (0 : Matrix (Fin n) (Fin n) ℂ).PosSemidef)
          | @insert t T ht ih =>
            rw [Finset.sum_insert ht]
            exact ((hQ t).smul (in767_weightedproof_probability_weight_nonneg _ (fun j => hp j t) s)).add ih
        exact H Finset.univ
  5. In the unweighted model, the candidate operators G(s) sum to P.

    Summing G(s) over all s and exchanging the order of summation using Finset.sum_comm gives ∑ t, (∑ s, w(p(·, t), s)) • Q(t). By in767_weightedproof_probability_weight_sum, the inner sum equals 1 for each t, reducing the total sum to ∑ t, Q(t) = P.

    lines 54–60

    uses Finset.sum_comm, Finset.sum_smul, in767_weightedproof_probability_weight_sum

      · change (∑ s, ∑ t, in767_weightedproof_probability_weight (fun j => p j t) s • Q t) = P
        rw [Finset.sum_comm]
        calc
          (∑ t, ∑ s, in767_weightedproof_probability_weight (fun j => p j t) s • Q t) =
              ∑ t, (∑ s, in767_weightedproof_probability_weight (fun j => p j t) s) • Q t := by simp [Finset.sum_smul]
          _ = ∑ t, Q t := by simp [in767_weightedproof_probability_weight_sum]
          _ = P := hsum
  6. In the unweighted model, the marginals of G(s) match the measurements ∑ t, p(j, t) • Q(t).

    Summing G(s) over all s with s(j) = true and swapping the sums yields ∑ t, (∑ s, (if s(j) then w(p(·, t), s) else 0)) • Q(t). By in767_weightedproof_probability_weight_marginal, the inner sum simplifies to p(j, t), matching the target marginal measurement.

    lines 61–72

    uses Finset.sum_comm, Finset.sum_smul, in767_weightedproof_probability_weight_marginal

      · intro j
        change (∑ s, if s j then (∑ t, in767_weightedproof_probability_weight (fun k => p k t) s • Q t) else 0) = _
        have heq (s : Fin 3 → Bool) :
            (if s j then (∑ t, in767_weightedproof_probability_weight (fun k => p k t) s • Q t) else 0) =
            ∑ t, (if s j then in767_weightedproof_probability_weight (fun k => p k t) s else 0) • Q t := by
          cases hs : s j <;> simp [hs]
        simp_rw [heq]
        rw [Finset.sum_comm]
        calc
          (∑ t, ∑ s, (if s j then in767_weightedproof_probability_weight (fun k => p k t) s else 0) • Q t) =
              ∑ t, (∑ s, if s j then in767_weightedproof_probability_weight (fun k => p k t) s else 0) • Q t := by simp [Finset.sum_smul]
          _ = ∑ t, (p j t) • Q t := by simp [in767_weightedproof_probability_weight_marginal]
  7. The weighted model reduces to an unweighted model by scaling Q'(t) = r(t) • Q(t) and p'(j, t) = p(j, t) / r(t).

    Define Q'(t) = r(t) • Q(t) and p'(j, t) = p(j, t) / r(t) when r(t) ≠ 0 (and 0 otherwise). Since r(t) ≥ 0, each Q'(t) is positive semidefinite. When r(t) = 0, p'(j, t) = 0 ∈ [0, 1]. When r(t) > 0, 0 ≤ p(j, t) ≤ r(t) implies 0 ≤ p'(j, t) ≤ 1 via div_nonneg and div_le_one.

    lines 82–91

    uses lt_of_le_of_ne, Ne.symm, if_false, div_nonneg, div_le_one

      let Q' : Fin m → Matrix (Fin n) (Fin n) ℂ := fun t => r t • Q t
      let p' : Fin 3 → Fin m → ℝ := fun j t => if r t=0 then 0 else p j t / r t
      have hQ' : ∀ t, (Q' t).PosSemidef := fun t => (hQ t).smul (hr t)
      have hp' : ∀ j t, 0 ≤ p' j t ∧ p' j t ≤ 1 := by
        intro j t
        by_cases h : r t=0
        · simp [p', h]
        · have hpos : 0 < r t := lt_of_le_of_ne (hr t) (Ne.symm h)
          simp only [p', h, if_false]
          exact ⟨div_nonneg (hp j t).1 (hr t), (div_le_one hpos).2 (hp j t).2⟩
  8. The parent operators G obtained from the rescaled model satisfy the marginal conditions for the original weighted model.

    Applying in767_weightedproof_hidden_model_parent to Q' and p' yields parent operators G summing to P. For each measurement j, the marginal sum is ∑ t, p'(j, t) • Q'(t). When r(t) = 0, both p(j, t) and Q'(t) vanish. When r(t) > 0, p'(j, t) • Q'(t) = (p(j, t) / r(t)) • (r(t) • Q(t)) = p(j, t) • Q(t) by canceling r(t).

    lines 92–104

    uses in767_weightedproof_hidden_model_parent, Finset.sum_congr, if_false, mul_smul

      obtain ⟨G,hG,hGsum,hGmarg⟩ := in767_weightedproof_hidden_model_parent n m Q' p' P hQ' hsum hp'
      refine ⟨G,hG,hGsum,?_⟩
      intro j
      rw [hGmarg j]
      apply Finset.sum_congr rfl
      intro t ht
      dsimp [Q',p']
      by_cases h : r t=0
      · have hpzero : p j t=0 := by have := hp j t; linarith
        simp [h,hpzero]
      · simp only [h, if_false, ← mul_smul]
        congr 1
        field_simp [h]
  9. The main theorem finite_weighted_three_binary_hidden_model_has_parent holds.

    Introducing all parameters and hypotheses, the result follows immediately by invoking in767_weightedproof_weighted_hidden_model_parent.

    lines 114–115

    uses in767_weightedproof_weighted_hidden_model_parent

      intro n m Q r p P hQ hsum hr hp
      exact in767_weightedproof_weighted_hidden_model_parent n m Q r p P hQ hsum hr hp
Finset.prod_nonneg
A finite product of non-negative elements in an ordered semiring is non-negative.
Finset.sum_prod_piFinset
The sum over all functions f from a finite index type into a finite set s of the product of g(i, f(i)) equals the product over i of the sum of g(i, j) over j in s.
Fintype.piFinset_univ
The finite set of all functions from a finite type to universal sets is the universal set of functions.
Fintype.sum_bool
The sum of a function over the boolean domain equals its value at true plus its value at false.
Fin.prod_univ_three
The product of a function over Fin 3 equals the product of its values at 0, 1, and 2.
Finset.induction_on
Induction principle on finite sets: a property holds for all finite sets if it holds for the empty set and is preserved when adjoining a fresh element.
Matrix.PosSemidef.zero
The zero matrix is positive semidefinite.
Finset.sum_insert
The sum over a finite set with an adjoined element a not in s equals the term at a plus the sum over s.
in767_weightedproof_probability_weight_nonneg
The Bernoulli product weight w(p, s) is non-negative whenever every probability p(j) lies in [0, 1].
Finset.univ
The finset containing all elements of a finite type.
Finset.sum_comm
Finite summations can be exchanged: the sum over s of the sum over t equals the sum over t of the sum over s.
Finset.sum_smul
Scalar multiplication distributes over a finite sum of scalars.
in767_weightedproof_probability_weight_sum
The sum of the Bernoulli product weights over all 8 boolean outcome triples equals 1.
in767_weightedproof_probability_weight_marginal
The sum of the product weights over all outcome configurations where the j-th outcome is true equals p(j).
lt_of_le_of_ne
If a ≤ b and a ≠ b, then a < b.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
if_false
An if-then-else expression whose condition is False simplifies to the false branch.
div_nonneg
The quotient of two non-negative numbers is non-negative.
div_le_one
For positive b, a / b ≤ 1 if and only if a ≤ b.
in767_weightedproof_hidden_model_parent
In the unweighted model (r ≡ 1), positive semidefinite hidden states with response probabilities in [0, 1] admit a joint positive semidefinite parent measurement.
Finset.sum_congr
Two finite sums are equal if their index sets are identical and their terms agree on all indices.
mul_smul
Scalar multiplication by a product of scalars equals iterated scalar multiplication: (x * y) • b = x • y • b.
in767_weightedproof_weighted_hidden_model_parent
In the weighted model with non-negative weights r and response probabilities bounded by r, there exists a joint positive semidefinite parent measurement.

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 Matrixopen scoped BigOperators Matrix ComplexOrderset_option backward.isDefEq.respectTransparency falseset_option linter.unusedSimpArgs falseprivate noncomputable def in767_weightedproof_probability_weight (p : Fin 3 → ℝ) (s : Fin 3 → Bool) : ℝ :=  ∏ j, if s j then p j else 1-p jprivate lemma in767_weightedproof_probability_weight_nonneg (p : Fin 3 → ℝ)    (hp : ∀ j, 0 ≤ p j ∧ p j ≤ 1) (s : Fin 3 → Bool) :    0 ≤ in767_weightedproof_probability_weight p s := by  apply Finset.prod_nonneg  intro j hj  split <;> linarith [hp j]private lemma in767_weightedproof_probability_weight_sum (p : Fin 3 → ℝ) :    (∑ s : Fin 3 → Bool, in767_weightedproof_probability_weight p s) = 1 := by  have hh := Finset.sum_prod_piFinset (ι := Fin 3) (Finset.univ : Finset Bool)    (fun j b => if b then p j else 1-p j)  simp only [Fintype.piFinset_univ] at hh  simpa [in767_weightedproof_probability_weight, Fintype.sum_bool] using hhprivate lemma in767_weightedproof_probability_weight_marginal (p : Fin 3 → ℝ) (j : Fin 3) :    (∑ s : Fin 3 → Bool, if s j then in767_weightedproof_probability_weight p s else 0) = p j := by  let f : Fin 3 → Bool → ℝ := fun i b => if i=j then if b then p i else 0 else if b then p i else 1-p i  have hprod (s : Fin 3 → Bool) : (∏ i, f i (s i)) =      if s j then in767_weightedproof_probability_weight p s else 0 := by    fin_cases j <;> cases h0 : s 0 <;> cases h1 : s 1 <;> cases h2 : s 2 <;>      simp [f, in767_weightedproof_probability_weight, Fin.prod_univ_three, h0,h1,h2]  have hh := Finset.sum_prod_piFinset (ι := Fin 3) (Finset.univ : Finset Bool) f  simp only [Fintype.piFinset_univ] at hh  simp_rw [hprod] at hh  fin_cases j <;> simp [f, Fintype.sum_bool, Fin.prod_univ_three] at hh ⊢ <;> linarithprivate lemma in767_weightedproof_hidden_model_parent    (n m : ℕ) (Q : Fin m → Matrix (Fin n) (Fin n) ℂ)    (p : Fin 3 → Fin m → ℝ) (P : Matrix (Fin n) (Fin n) ℂ)    (hQ : ∀ t, (Q t).PosSemidef) (hsum : (∑ t, Q t)=P)    (hp : ∀ j t, 0 ≤ p j t ∧ p j t ≤ 1) :    ∃ G : (Fin 3 → Bool) → Matrix (Fin n) (Fin n) ℂ,      (∀ s, (G s).PosSemidef) ∧ (∑ s, G s) = P ∧      ∀ j : Fin 3, (∑ s, if s j then G s else 0) = ∑ t, (p j t) • Q t := by  let G : (Fin 3 → Bool) → Matrix (Fin n) (Fin n) ℂ := fun s =>    ∑ t, in767_weightedproof_probability_weight (fun j => p j t) s • Q t  refine ⟨G, ?_, ?_, ?_⟩  · intro s    change (∑ t, in767_weightedproof_probability_weight (fun j => p j t) s • Q t).PosSemidef    have H (T : Finset (Fin m)) : (∑ t ∈ T, in767_weightedproof_probability_weight (fun j => p j t) s • Q t).PosSemidef := by      induction T using Finset.induction_on with      | empty => simpa using (Matrix.PosSemidef.zero : (0 : Matrix (Fin n) (Fin n) ℂ).PosSemidef)      | @insert t T ht ih =>        rw [Finset.sum_insert ht]        exact ((hQ t).smul (in767_weightedproof_probability_weight_nonneg _ (fun j => hp j t) s)).add ih    exact H Finset.univ  · change (∑ s, ∑ t, in767_weightedproof_probability_weight (fun j => p j t) s • Q t) = P    rw [Finset.sum_comm]    calc      (∑ t, ∑ s, in767_weightedproof_probability_weight (fun j => p j t) s • Q t) =          ∑ t, (∑ s, in767_weightedproof_probability_weight (fun j => p j t) s) • Q t := by simp [Finset.sum_smul]      _ = ∑ t, Q t := by simp [in767_weightedproof_probability_weight_sum]      _ = P := hsum  · intro j    change (∑ s, if s j then (∑ t, in767_weightedproof_probability_weight (fun k => p k t) s • Q t) else 0) = _    have heq (s : Fin 3 → Bool) :        (if s j then (∑ t, in767_weightedproof_probability_weight (fun k => p k t) s • Q t) else 0) =        ∑ t, (if s j then in767_weightedproof_probability_weight (fun k => p k t) s else 0) • Q t := by      cases hs : s j <;> simp [hs]    simp_rw [heq]    rw [Finset.sum_comm]    calc      (∑ t, ∑ s, (if s j then in767_weightedproof_probability_weight (fun k => p k t) s else 0) • Q t) =          ∑ t, (∑ s, if s j then in767_weightedproof_probability_weight (fun k => p k t) s else 0) • Q t := by simp [Finset.sum_smul]      _ = ∑ t, (p j t) • Q t := by simp [in767_weightedproof_probability_weight_marginal]private lemma in767_weightedproof_weighted_hidden_model_parent    (n m : ℕ) (Q : Fin m → Matrix (Fin n) (Fin n) ℂ)    (r : Fin m → ℝ) (p : Fin 3 → Fin m → ℝ) (P : Matrix (Fin n) (Fin n) ℂ)    (hQ : ∀ t, (Q t).PosSemidef) (hsum : (∑ t, (r t) • Q t)=P)    (hr : ∀ t, 0 ≤ r t) (hp : ∀ j t, 0 ≤ p j t ∧ p j t ≤ r t) :    ∃ G : (Fin 3 → Bool) → Matrix (Fin n) (Fin n) ℂ,      (∀ s, (G s).PosSemidef) ∧ (∑ s, G s) = P ∧      ∀ j : Fin 3, (∑ s, if s j then G s else 0) = ∑ t, (p j t) • Q t := by  let Q' : Fin m → Matrix (Fin n) (Fin n) ℂ := fun t => r t • Q t  let p' : Fin 3 → Fin m → ℝ := fun j t => if r t=0 then 0 else p j t / r t  have hQ' : ∀ t, (Q' t).PosSemidef := fun t => (hQ t).smul (hr t)  have hp' : ∀ j t, 0 ≤ p' j t ∧ p' j t ≤ 1 := by    intro j t    by_cases h : r t=0    · simp [p', h]    · have hpos : 0 < r t := lt_of_le_of_ne (hr t) (Ne.symm h)      simp only [p', h, if_false]      exact ⟨div_nonneg (hp j t).1 (hr t), (div_le_one hpos).2 (hp j t).2⟩  obtain ⟨G,hG,hGsum,hGmarg⟩ := in767_weightedproof_hidden_model_parent n m Q' p' P hQ' hsum hp'  refine ⟨G,hG,hGsum,?_⟩  intro j  rw [hGmarg j]  apply Finset.sum_congr rfl  intro t ht  dsimp [Q',p']  by_cases h : r t=0  · have hpzero : p j t=0 := by have := hp j t; linarith    simp [h,hpzero]  · simp only [h, if_false, ← mul_smul]    congr 1    field_simp [h]theorem finite_weighted_three_binary_hidden_model_has_parent :  ∀ (n m : ℕ) (Q : Fin m → Matrix (Fin n) (Fin n) ℂ)    (r : Fin m → ℝ) (p : Fin 3 → Fin m → ℝ) (P : Matrix (Fin n) (Fin n) ℂ),    (∀ t, (Q t).PosSemidef) → (∑ t, (r t) • Q t) = P →    (∀ t, 0 ≤ r t) → (∀ j t, 0 ≤ p j t ∧ p j t ≤ r t) →    ∃ G : (Fin 3 → Bool) → Matrix (Fin n) (Fin n) ℂ,      (∀ s, (G s).PosSemidef) ∧ (∑ s, G s) = P ∧      ∀ j : Fin 3, (∑ s, if s j then G s else 0) = ∑ t, (p j t) • Q t := by  intro n m Q r p P hQ hsum hr hp  exact in767_weightedproof_weighted_hidden_model_parent n m Q r p P hQ hsum hr hp
See it in the graphDiscuss this resultChallenge it