finite_weighted_three_binary_hidden_model_has_parent
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
- finite_three_binary_hidden_model_has_parentA finite hidden-variable model for three binary effects yields a joint positive parent, also for a subnormalized total.
- Used by 2
- ppt_qutrit_steered_effect_all_proper_subspaces_compatibleEvery proper subspace compression of the three normalized steered effects has a joint parent.
- open_problem_693_three_dim_fewer_than_nineThere exists a natural number k strictly less than 9 such that has_subspace_compatible_incompatible_family 3 k holds, meaning there is a…
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.
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.
uses
Finset.prod_nonnegapply Finset.prod_nonneg intro j hj split <;> linarith [hp j]
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.
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_weightedproof_probability_weight, Fintype.sum_bool] using hh
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.
uses
Fin.prod_univ_three,Finset.sum_prod_piFinset,Fintype.piFinset_univ,Fintype.sum_boollet 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
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.
uses
Finset.induction_on,Matrix.PosSemidef.zero,Finset.sum_insert,in767_weightedproof_probability_weight_nonneg,Finset.univlet 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
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.
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
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.
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]
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.
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⟩
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).
uses
in767_weightedproof_hidden_model_parent,Finset.sum_congr,if_false,mul_smulobtain ⟨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]
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.
uses
in767_weightedproof_weighted_hidden_model_parentintro 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.
- The helper lemma `in767_weightedproof_probability_weight_marginal` relies on exhaustive case analysis (`fin_cases` and `cases`) across all 3 measurement settings and 8 boolean outcome configurations to establish the marginal distribution property.
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_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