finite_three_binary_hidden_model_has_parent
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
- finite_weighted_three_binary_hidden_model_has_parentSubnormalized finite hidden weights for three binary effects yield a joint positive parent.
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.
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.
uses
Finset.prod_nonnegapply Finset.prod_nonneg intro j hj split <;> linarith [hp j]
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.
uses
Finset.sum_prod_piFinset,Fintype.piFinset_univ,Fintype.sum_boolhave 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
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.
uses
Fin.prod_univ_threelet 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]
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.
uses
Finset.sum_prod_piFinset,Fintype.piFinset_univ,Fintype.sum_bool,Fin.prod_univ_threehave 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
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.
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, ?_, ?_, ?_⟩
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.
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
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.
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
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).
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]
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.
uses
lt_of_le_of_ne,Ne.symm,if_false,div_nonneg,div_le_onelet 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⟩
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.
uses
in767_hiddenproof_hidden_model_parent,Finset.sum_congr,if_false,mul_smulobtain ⟨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]
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.
uses
in767_hiddenproof_hidden_model_parentintro 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.
- The source file contains an auxiliary lemma (in767_hiddenproof_weighted_hidden_model_parent) that generalizes the result to subnormalized component weights, but the main theorem finite_three_binary_hidden_model_has_parent directly invokes the unweighted version in767_hiddenproof_hidden_model_parent.
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 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