AFTD Auto-Formalizing Theoretical Domains

finite_three_binary_hidden_model_has_parent

theoremverified

A finite hidden-variable model for three binary effects yields a joint positive parent, also for a subnormalized total.

Statement

theorem finite_three_binary_hidden_model_has_parent :
  ∀ (n m : ℕ) (Q : Fin m → Matrix (Fin n) (Fin n) ℂ)
    (p : Fin 3 → Fin m → ℝ) (P : Matrix (Fin n) (Fin n) ℂ),
    (∀ t, (Q t).PosSemidef) → (∑ t, Q t) = P →
    (∀ 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
Source
Helper for OP-693, using the rank-four PPT source from https://arxiv.org/abs/1405.4502 and the normal-completion context https://arxiv.org/abs/0903.0090.
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The theorem establishes that any finite hidden-variable model for three binary quantum effects admits a joint positive semidefinite parent matrix. For each hidden state t, the independent Bernoulli product measure defines probability weights on the 8 binary configurations from the marginal success probabilities p_j(t). The parent matrix G(s) for each configuration s is defined as the convex combination of the positive semidefinite components Q_t weighted by these probabilities. Positivity follows because non-negative linear combinations of positive semidefinite matrices are positive semidefinite, and the marginal sums match the target effects by exchanging the order of summation and applying the marginal summation properties of the product weights.

  1. The Bernoulli product weight w(p, s) is non-negative for every binary outcome s.

    The probability weight is defined as the product over the three coordinates of p_j (if s_j is true) or 1 - p_j (if s_j is false). Since each p_j lies in [0, 1], both p_j and 1 - p_j are non-negative, so their product is non-negative by Finset.prod_nonneg.

    lines 11–13

    uses Finset.prod_nonneg

      apply Finset.prod_nonneg
      intro j hj
      split <;> linarith [hp j]
  2. The probability weights sum to 1 over all eight binary outcomes.

    Applying Finset.sum_prod_piFinset transforms the sum over configurations of the product weight into the product over coordinates of the sum (p_j + (1 - p_j)) = 1, which evaluates to 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_hiddenproof_probability_weight, Fintype.sum_bool] using hh
  3. The indicator of s_j = true times the probability weight factors into a coordinate-wise product.

    We define an auxiliary factor function f that replaces the j-th Bernoulli weight by p_j when true and 0 when false, leaving the other coordinates unchanged. By case analysis over all 3 coordinates and 8 binary assignments, Lean verifies with Fin.prod_univ_three that the product of these factors matches the conditional weight.

    lines 24–28

    uses Fin.prod_univ_three

      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_hiddenproof_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_hiddenproof_probability_weight, Fin.prod_univ_three, h0,h1,h2]
  4. The marginal sum of weights with s_j = true equals p_j.

    Using Finset.sum_prod_piFinset, the sum over binary strings factors into the product of the coordinate sums of f. At coordinate j the sum is p_j + 0 = p_j, while at the other two coordinates it is p_i + (1 - p_i) = 1, so the overall product is p_j.

    lines 29–32

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

      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
  5. Define the candidate parent matrix G(s) as a mixture of the components Q_t.

    For each binary configuration s, we define G(s) to be the sum over hidden states t of the component Q_t scaled by the product weight w(p(·, t), s). We then decompose the goal into checking positive semidefiniteness, the total sum, and the marginal sums.

    lines 42–44

      let G : (Fin 3 → Bool) → Matrix (Fin n) (Fin n) ℂ := fun s =>
        ∑ t, in767_hiddenproof_probability_weight (fun j => p j t) s • Q t
      refine ⟨G, ?_, ?_, ?_⟩
  6. Each parent matrix G(s) is positive semidefinite.

    We prove by induction on finite subsets of hidden states (using Finset.induction_on) that the partial sum is positive semidefinite. The base case is the zero matrix (Matrix.PosSemidef.zero). For the inductive step, adding a component scaled by the non-negative weight (in767_hiddenproof_probability_weight_nonneg) preserves positive semidefiniteness via Finset.sum_insert.

    lines 45–53

    uses Finset.induction_on, Matrix.PosSemidef.zero, Finset.sum_insert, in767_hiddenproof_probability_weight_nonneg

      · intro s
        change (∑ t, in767_hiddenproof_probability_weight (fun j => p j t) s • Q t).PosSemidef
        have H (T : Finset (Fin m)) : (∑ t ∈ T, in767_hiddenproof_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_hiddenproof_probability_weight_nonneg _ (fun j => hp j t) s)).add ih
        exact H Finset.univ
  7. The sum of G(s) over all binary configurations equals P.

    Swapping the double summation over s and t (Finset.sum_comm) and factoring out Q_t (Finset.sum_smul), the inner sum over s of the weights equals 1 by in767_hiddenproof_probability_weight_sum. The remaining sum over t of Q_t equals P by the assumption hsum.

    lines 54–60

    uses Finset.sum_comm, Finset.sum_smul, in767_hiddenproof_probability_weight_sum

      · change (∑ s, ∑ t, in767_hiddenproof_probability_weight (fun j => p j t) s • Q t) = P
        rw [Finset.sum_comm]
        calc
          (∑ t, ∑ s, in767_hiddenproof_probability_weight (fun j => p j t) s • Q t) =
              ∑ t, (∑ s, in767_hiddenproof_probability_weight (fun j => p j t) s) • Q t := by simp [Finset.sum_smul]
          _ = ∑ t, Q t := by simp [in767_hiddenproof_probability_weight_sum]
          _ = P := hsum
  8. The marginal sums of G(s) for s_j = true match the target effects ∑_t p_j(t) • Q_t.

    Distributing the condition s_j = true inside the sum over t and swapping the summations (Finset.sum_comm), the coefficient of Q_t simplifies by in767_hiddenproof_probability_weight_marginal to p_j(t).

    lines 61–72

    uses Finset.sum_comm, Finset.sum_smul, in767_hiddenproof_probability_weight_marginal

      · intro j
        change (∑ s, if s j then (∑ t, in767_hiddenproof_probability_weight (fun k => p k t) s • Q t) else 0) = _
        have heq (s : Fin 3 → Bool) :
            (if s j then (∑ t, in767_hiddenproof_probability_weight (fun k => p k t) s • Q t) else 0) =
            ∑ t, (if s j then in767_hiddenproof_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_hiddenproof_probability_weight (fun k => p k t) s else 0) • Q t) =
              ∑ t, (∑ s, if s j then in767_hiddenproof_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_hiddenproof_probability_weight_marginal]
  9. Normalize the weighted model components and probabilities.

    We define Q'_t = r_t • Q_t and normalized probabilities p'_j(t) = p_j(t) / r_t (setting 0 when r_t = 0). Since r_t ≥ 0 and Q_t is positive semidefinite, Q'_t is positive semidefinite. Moreover, 0 ≤ p_j(t) ≤ r_t implies p'_j(t) lies in [0, 1] using 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⟩
  10. Construct the parent state for the weighted model and verify its marginals.

    We apply in767_hiddenproof_hidden_model_parent to the normalized data Q' and p' to obtain a parent G. For each coordinate j, Finset.sum_congr compares the terms: when r_t = 0, p_j(t) = 0 and both sides vanish; when r_t > 0, the factors of r_t cancel via mul_smul, establishing that the marginal sums match.

    lines 92–104

    uses in767_hiddenproof_hidden_model_parent, Finset.sum_congr, if_false, mul_smul

      obtain ⟨G,hG,hGsum,hGmarg⟩ := in767_hiddenproof_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]
  11. Every finite hidden-variable model for three binary effects has a positive parent.

    The theorem finite_three_binary_hidden_model_has_parent is directly proven by applying in767_hiddenproof_hidden_model_parent to the provided components Q and probabilities p.

    lines 114–115

    uses in767_hiddenproof_hidden_model_parent

      intro n m Q p P hQ hsum hp
      exact in767_hiddenproof_hidden_model_parent n m Q p P hQ hsum hp
Finset.prod_nonneg
A product of non-negative elements over a finite set is non-negative.
Finset.sum_prod_piFinset
The sum over all functions in a Cartesian product of the product of coordinate terms factors into the product of the sums over each coordinate.
Fintype.piFinset_univ
The product set piFinset with universal coordinate sets equals the universal set of functions.
Fintype.sum_bool
The sum of a function over the booleans equals the sum of its values at true and false.
Fin.prod_univ_three
The product of a function on Fin 3 is the product of its values at 0, 1, and 2.
Finset.induction_on
A property holds for all finite sets if it holds for the empty set and is preserved under adjoining an element.
Matrix.PosSemidef.zero
The zero matrix is positive semidefinite.
Finset.sum_insert
Summing a function over insert a s (with a not in s) is the term at a plus the sum over s.
in767_hiddenproof_probability_weight_nonneg
The Bernoulli product weight of any binary string is non-negative whenever the coordinate probabilities lie in [0, 1].
Finset.sum_comm
Finite double summations can be exchanged.
Finset.sum_smul
Scalar multiplication distributes over finite sums.
in767_hiddenproof_probability_weight_sum
The sum of the Bernoulli product weights over all 8 binary strings equals 1.
in767_hiddenproof_probability_weight_marginal
The marginal sum of Bernoulli product weights over strings with j-th coordinate true equals the j-th coordinate probability.
lt_of_le_of_ne
If a ≤ b and a ≠ b in a partial order, then a < b.
Ne.symm
Inequality is symmetric: if a ≠ b then b ≠ a.
if_false
An if-then-else statement with a false condition evaluates to the else branch.
div_nonneg
The quotient of two non-negative numbers is non-negative.
div_le_one
For positive denominator b, a / b ≤ 1 if and only if a ≤ b.
in767_hiddenproof_hidden_model_parent
Any finite hidden-variable model for three binary effects with unweighted positive semidefinite components admits a joint positive semidefinite parent.
Finset.sum_congr
Two finite sums are equal if their domains and summands coincide.
mul_smul
Scalar multiplication is associative with respect to scalar multiplication in the field: (x * y) • b = x • y • b.

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_hiddenproof_probability_weight (p : Fin 3 → ℝ) (s : Fin 3 → Bool) : ℝ :=  ∏ j, if s j then p j else 1-p jprivate lemma in767_hiddenproof_probability_weight_nonneg (p : Fin 3 → ℝ)    (hp : ∀ j, 0 ≤ p j ∧ p j ≤ 1) (s : Fin 3 → Bool) :    0 ≤ in767_hiddenproof_probability_weight p s := by  apply Finset.prod_nonneg  intro j hj  split <;> linarith [hp j]private lemma in767_hiddenproof_probability_weight_sum (p : Fin 3 → ℝ) :    (∑ s : Fin 3 → Bool, in767_hiddenproof_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_hiddenproof_probability_weight, Fintype.sum_bool] using hhprivate lemma in767_hiddenproof_probability_weight_marginal (p : Fin 3 → ℝ) (j : Fin 3) :    (∑ s : Fin 3 → Bool, if s j then in767_hiddenproof_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_hiddenproof_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_hiddenproof_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_hiddenproof_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_hiddenproof_probability_weight (fun j => p j t) s • Q t  refine ⟨G, ?_, ?_, ?_⟩  · intro s    change (∑ t, in767_hiddenproof_probability_weight (fun j => p j t) s • Q t).PosSemidef    have H (T : Finset (Fin m)) : (∑ t ∈ T, in767_hiddenproof_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_hiddenproof_probability_weight_nonneg _ (fun j => hp j t) s)).add ih    exact H Finset.univ  · change (∑ s, ∑ t, in767_hiddenproof_probability_weight (fun j => p j t) s • Q t) = P    rw [Finset.sum_comm]    calc      (∑ t, ∑ s, in767_hiddenproof_probability_weight (fun j => p j t) s • Q t) =          ∑ t, (∑ s, in767_hiddenproof_probability_weight (fun j => p j t) s) • Q t := by simp [Finset.sum_smul]      _ = ∑ t, Q t := by simp [in767_hiddenproof_probability_weight_sum]      _ = P := hsum  · intro j    change (∑ s, if s j then (∑ t, in767_hiddenproof_probability_weight (fun k => p k t) s • Q t) else 0) = _    have heq (s : Fin 3 → Bool) :        (if s j then (∑ t, in767_hiddenproof_probability_weight (fun k => p k t) s • Q t) else 0) =        ∑ t, (if s j then in767_hiddenproof_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_hiddenproof_probability_weight (fun k => p k t) s else 0) • Q t) =          ∑ t, (∑ s, if s j then in767_hiddenproof_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_hiddenproof_probability_weight_marginal]private lemma in767_hiddenproof_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_hiddenproof_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_three_binary_hidden_model_has_parent :  ∀ (n m : ℕ) (Q : Fin m → Matrix (Fin n) (Fin n) ℂ)    (p : Fin 3 → Fin m → ℝ) (P : Matrix (Fin n) (Fin n) ℂ),    (∀ t, (Q t).PosSemidef) → (∑ t, Q t) = P →    (∀ 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  intro n m Q p P hQ hsum hp  exact in767_hiddenproof_hidden_model_parent n m Q p P hQ hsum hp
See it in the graphDiscuss this resultChallenge it