rank_two_frame_compression_no_parent
For r greater than one, no positive 2-by-2 parent has the displayed total matrix and three displayed marginals.
Statement
theorem rank_two_frame_compression_no_parent (r : ℝ) (hr : 1 < r) : ¬ ∃ G : (Fin 3 → Bool) → Matrix (Fin 2) (Fin 2) ℂ, (∀ s, (G s).PosSemidef) ∧ (∑ s, G s = !![2, 1; 1, 2]) ∧ (∑ s, if s 0 then G s else 0) = !![1, 0; 0, 0] ∧ (∑ s, if s 1 then G s else 0) = 1 ∧ (∑ s, if s 2 then G s else 0) = (1/2 : ℝ) • (!![2, 1; 1, 2] - r • !![1, 1; 1, 1])
- Source
- Helper excluding a four-outcome rank-one-frame construction for OP-693; exact compressed matrices in experiment 22918.
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- subspace_incompatible_family_of_mic_dataFor all d k : ℕ, let g : Fin k → Fin d → ℂ, write G i = Matrix.vecMulVec (g i) (star (g i)) (the rank-one positive matrix g_i g_i^*), let…
- FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via
ZMod.
The proof, explained
The proof proceeds by contradiction: assuming a positive semidefinite parent family G exists, each matrix G(s) is bounded above in the Loewner order by rank-one marginals or their complements. Because any positive semidefinite matrix dominated by a rank-one matrix v v* is a non-negative scalar multiple of v v*, each G(s) must be proportional to F_3, F_2, or F_0, and must vanish when s 0 = true and s 1 = false. This forces the real part of the off-diagonal entry (G(s)) 0 1 to be non-negative for every s, which implies that the third marginal sum must also have a non-negative (0, 1)-entry. Evaluating this entry directly from the given marginal gives (1 - r) / 2 ≥ 0, which contradicts r > 1.
The outer products v_0 v_0*, v_2 v_2*, and v_3 v_3* equal the rank-one matrices F_0, F_2, and F_3 respectively. automation
By extensionality on 2-by-2 matrices, each entry is checked across the finite index cases {0, 1} × {0, 1} and evaluated by numeric computation.
uses
vecMulVec_applyprivate lemma in767_outer0 : vecMulVec in767_v0 (star in767_v0) = in767_F0 := by ext i j; fin_cases i <;> fin_cases j <;> norm_num [vecMulVec_apply,in767_v0,in767_F0] private lemma in767_outer2 : vecMulVec in767_v2 (star in767_v2) = in767_F2 := by ext i j; fin_cases i <;> fin_cases j <;> norm_num [vecMulVec_apply,in767_v2,in767_F2] private lemma in767_outer3 : vecMulVec in767_v3 (star in767_v3) = in767_F3 := by ext i j; fin_cases i <;> fin_cases j <;> norm_num [vecMulVec_apply,in767_v3,in767_F3]
The matrix algebraic relations F_S - I = F_0 and I - F_3 = F_2 hold. automation
By checking each matrix entry over the four index combinations using the definition of the identity matrix.
uses
Matrix.one_applyprivate lemma in767_Ssub : in767_FS - 1 = in767_F0 := by ext i j; fin_cases i <;> fin_cases j <;> norm_num [in767_FS,in767_F0,Matrix.one_apply] private lemma in767_Isub : (1 : Matrix (Fin 2) (Fin 2) ℂ) - in767_F3 = in767_F2 := by ext i j; fin_cases i <;> fin_cases j <;> norm_num [in767_F3,in767_F2,Matrix.one_apply]
Assume for contradiction that a family G of positive semidefinite matrices exists satisfying the total sum and three marginals.
We introduce the assumed witness G with its properties: each G(s) is positive semidefinite, their total sum is F_S, and their marginals along coordinate directions 0, 1, and 2 are F_3, I, and (1/2) • (F_S - r • F_0), respectively.
classical rintro ⟨G, hG, hsum, h0, h1, h2⟩
For any index s with s 0 = true, F_3 - G(s) is positive semidefinite.
Isolating G(s) from the marginal sum over all s with s 0 = true, the difference F_3 - G(s) equals the sum of the remaining terms. Since each term G(a) is positive semidefinite (or 0 when a 0 is false), their sum is positive semidefinite.
uses
Finset.add_sum_erase,Finset.mem_univ,if_pos,add_sub_cancel_left,Matrix.posSemidef_sum,Matrix.PosSemidef.zerohave h0le : ∀ s, s 0 = true → (in767_F3 - G s).PosSemidef := by intro s hs have he := h0 rw [← Finset.add_sum_erase _ _ (Finset.mem_univ s), if_pos hs] at he rw [← he, add_sub_cancel_left] exact Matrix.posSemidef_sum _ fun a _ => by split_ifs · exact hG a · exact Matrix.PosSemidef.zero
The sum of G(s) over all s with s 1 = false equals F_0.
The sum over s with s 1 = false is obtained by subtracting the marginal sum where s 1 = true (which equals I) from the total sum (which equals F_S). By the algebraic relation F_S - I = F_0, this sum is F_0.
uses
Finset.sum_sub_distrib,Finset.sum_congr,in767_Ssublet F : (Fin 3 → Bool) → Matrix (Fin 2) (Fin 2) ℂ := fun s => if s 1 then 0 else G s have hFsum : ∑ s, F s = in767_F0 := by calc ∑ s, F s = (∑ s, G s) - ∑ s, (if s 1 then G s else 0) := by rw [← Finset.sum_sub_distrib] refine Finset.sum_congr rfl fun s _ => ?_ cases hs : s 1 <;> simp [F,hs] _ = in767_F0 := by rw [hsum,h1,in767_Ssub]
For any index s with s 1 = false, F_0 - G(s) is positive semidefinite.
Isolating G(s) from the sum over all s with s 1 = false, the difference F_0 - G(s) is the sum over the remaining indices of terms that are each positive semidefinite (or 0), hence positive semidefinite.
uses
Finset.add_sum_erase,Finset.mem_univ,Bool.false_eq_true,if_false,add_sub_cancel_left,Matrix.posSemidef_sum,Matrix.PosSemidef.zerohave h1le : ∀ s, s 1 = false → (in767_F0 - G s).PosSemidef := by intro s hs have he := hFsum rw [← Finset.add_sum_erase _ _ (Finset.mem_univ s)] at he simp only [F,hs,Bool.false_eq_true,if_false] at he rw [← he, add_sub_cancel_left] exact Matrix.posSemidef_sum _ fun a _ => by split_ifs · exact Matrix.PosSemidef.zero · exact hG a
If s 0 = true and s 1 = false, then G(s) = 0.
Such a G(s) is positive semidefinite and Loewner-dominated by both rank-one matrices F_3 = v_3 v_3* and F_0 = v_0 v_0*. Dominance by a rank-one matrix implies G(s) = a • F_3 and G(s) = b • F_0 for non-negative scalars a and b. Comparing the off-diagonal (0, 1)-entry shows (a • F_3) 0 1 = 0 while (b • F_0) 0 1 = b, forcing b = 0 and thus G(s) = 0.
uses
in767_outer3,in767_outer0,rank_one_psd_dominated_eq_smul,congrArg,zero_smulhave hzero : ∀ s, s 0 = true → s 1 = false → G s = 0 := by intro s hs0 hs1 have hA := h0le s hs0 have hB := h1le s hs1 rw [← in767_outer3] at hA rw [← in767_outer0] at hB obtain ⟨a, ha, ea⟩ := rank_one_psd_dominated_eq_smul (G s) in767_v3 (hG s) hA obtain ⟨b, hb, eb⟩ := rank_one_psd_dominated_eq_smul (G s) in767_v0 (hG s) hB rw [in767_outer3] at ea rw [in767_outer0] at eb have e := congrArg (fun X : Matrix (Fin 2) (Fin 2) ℂ => (X 0 1).re) (ea.symm.trans eb) have hb0 : b = 0 := by simpa [in767_F0,in767_F3] using e.symm rw [eb, hb0, zero_smul]
The sum of G(s) over all s with s 0 = false and s 1 = true equals F_2.
Subtracting the marginal sum where s 0 = true from the marginal sum where s 1 = true yields I - F_3 = F_2. In this difference, the terms where s 0 = true and s 1 = true cancel, the terms where s 0 = true and s 1 = false vanish because G(s) = 0, and the terms where both are false are zero, leaving precisely the sum over indices where s 0 = false and s 1 = true.
uses
Finset.sum_sub_distrib,Finset.sum_congr,in767_Isublet R : (Fin 3 → Bool) → Matrix (Fin 2) (Fin 2) ℂ := fun s => if s 1 then (if s 0 then 0 else G s) else 0 have hRsum : ∑ s, R s = in767_F2 := by calc ∑ s, R s = (∑ s, if s 1 then G s else 0) - ∑ s, (if s 0 then G s else 0) := by rw [← Finset.sum_sub_distrib] refine Finset.sum_congr rfl fun s _ => ?_ by_cases hs0 : s 0 = true <;> by_cases hs1 : s 1 = true · simp [R,hs0,hs1] · have hz := hzero s hs0 (by simpa using hs1) simp [R,hs0,hs1,hz] · simp [R,hs0,hs1] · simp [R,hs0,hs1] _ = in767_F2 := by rw [h1,h0,in767_Isub]
For any index s with s 0 = false and s 1 = true, F_2 - G(s) is positive semidefinite.
Isolating G(s) from the sum over all s with s 0 = false and s 1 = true, the difference F_2 - G(s) is a sum of positive semidefinite matrices (or zeros), hence positive semidefinite.
uses
Finset.add_sum_erase,Finset.mem_univ,if_true,Bool.false_eq_true,if_false,add_sub_cancel_left,Matrix.posSemidef_sum,Matrix.PosSemidef.zerohave h2le : ∀ s, s 0 = false → s 1 = true → (in767_F2 - G s).PosSemidef := by intro s hs0 hs1 have he := hRsum rw [← Finset.add_sum_erase _ _ (Finset.mem_univ s)] at he simp only [R,hs0,hs1,if_true,Bool.false_eq_true,if_false] at he rw [← he, add_sub_cancel_left] exact Matrix.posSemidef_sum _ fun a _ => by split_ifs · exact Matrix.PosSemidef.zero · exact hG a · exact Matrix.PosSemidef.zero
For every index s, the real part of the (0, 1)-entry of G(s) is non-negative.
We examine the three possible cases for the pair (s 0, s 1): if s 0 = true, G(s) is a multiple of F_3, whose (0, 1)-entry is 0; if s 0 = false and s 1 = true, G(s) is a multiple of F_2, whose (0, 1)-entry is 0; if both are false, G(s) is a non-negative multiple of F_0, whose (0, 1)-entry is 1 ≥ 0. In all cases, Re((G(s)) 0 1) ≥ 0.
uses
in767_outer3,rank_one_psd_dominated_eq_smul,in767_outer2,in767_outer0have hentry : ∀ s, 0 ≤ (G s 0 1).re := by intro s by_cases hs0 : s 0 = true · have hA := h0le s hs0 rw [← in767_outer3] at hA obtain ⟨a,ha,ea⟩ := rank_one_psd_dominated_eq_smul (G s) in767_v3 (hG s) hA rw [in767_outer3] at ea rw [ea] simp [in767_F3] · have hs0' : s 0 = false := by simpa using hs0 by_cases hs1 : s 1 = true · have hA := h2le s hs0' hs1 rw [← in767_outer2] at hA obtain ⟨a,ha,ea⟩ := rank_one_psd_dominated_eq_smul (G s) in767_v2 (hG s) hA rw [in767_outer2] at ea rw [ea] simp [in767_F2] · have hs1' : s 1 = false := by simpa using hs1 have hA := h1le s hs1' rw [← in767_outer0] at hA obtain ⟨a,ha,ea⟩ := rank_one_psd_dominated_eq_smul (G s) in767_v0 (hG s) hA rw [in767_outer0] at ea rw [ea] simpa [in767_F0] using ha
The marginal sum along coordinate 2 yields a contradiction r ≤ 1. automation
Since each G(s) has non-negative real part in its (0, 1)-entry, the (0, 1)-entry of the sum over s with s 2 = true has non-negative real part. But by assumption, this sum equals (1/2) • (F_S - r • F_0), whose (0, 1)-entry has real part (1 - r) / 2. Hence 0 ≤ (1 - r) / 2, which implies r ≤ 1, contradicting 1 < r.
uses
Matrix.sum_apply,Complex.re_sum,Finset.sum_nonneghave hnonneg : 0 ≤ ((∑ s : (Fin 3 → Bool), if s 2 then G s else 0) 0 1).re := by simp only [Matrix.sum_apply, Complex.re_sum] exact Finset.sum_nonneg fun s _ => by split_ifs <;> simp_all rw [h2] at hnonneg norm_num [in767_FS,in767_F0] at hnonneg linarith
No such parent matrix family G exists for r > 1.
The main theorem rank_two_frame_compression_no_parent is an immediate restatement of in767_frame_no_parent with explicit matrix literals.
uses
in767_frame_no_parenttheorem rank_two_frame_compression_no_parent (r : ℝ) (hr : 1 < r) : ¬ ∃ G : (Fin 3 → Bool) → Matrix (Fin 2) (Fin 2) ℂ, (∀ s, (G s).PosSemidef) ∧ (∑ s, G s = !![2, 1; 1, 2]) ∧ (∑ s, if s 0 then G s else 0) = !![1, 0; 0, 0] ∧ (∑ s, if s 1 then G s else 0) = 1 ∧ (∑ s, if s 2 then G s else 0) = (1/2 : ℝ) • (!![2, 1; 1, 2] - r • !![1, 1; 1, 1]) := by exact in767_frame_no_parent r hr
vecMulVec_apply- The (i, j)-entry of the outer product of vectors w and v is w i * v j.
Matrix.one_apply- The (i, j)-entry of the identity matrix is 1 if i = j and 0 otherwise.
Finset.add_sum_erase- A finite sum over a set s can be decomposed into an element f a and the sum over s without a.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
if_pos- If a condition c holds, the conditional expression (if c then t else e) equals t.
add_sub_cancel_left- In an additive group, subtracting a from a + b leaves b.
Matrix.posSemidef_sum- A finite sum of positive semidefinite matrices is positive semidefinite.
Matrix.PosSemidef.zero- The zero matrix is positive semidefinite.
Finset.sum_sub_distrib- A finite sum of differences equals the difference of the finite sums.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree at every index.
in767_Ssub- The matrix difference F_S - I equals F_0.
Bool.false_eq_true- The boolean value false does not equal true.
if_false- A conditional expression with a false condition evaluates to its second branch.
if_true- A conditional expression with a true condition evaluates to its first branch.
in767_outer3- The outer product of v_3 = (1, 0) with its conjugate transpose equals the matrix F_3 = !![1, 0; 0, 0].
in767_outer0- The outer product of v_0 = (1, 1) with its conjugate transpose equals the all-ones matrix F_0 = !![1, 1; 1, 1].
in767_outer2- The outer product of v_2 = (0, 1) with its conjugate transpose equals the matrix F_2 = !![0, 0; 0, 1].
rank_one_psd_dominated_eq_smul- If a positive semidefinite matrix A is dominated by the rank-one matrix v v*, then A is a non-negative scalar multiple of v v*.
congrArg- Applying a function to equal arguments produces equal results.
zero_smul- Scalar multiplication of any element by zero gives zero.
in767_Isub- The matrix difference I - F_3 equals F_2.
Matrix.sum_apply- The (i, j)-entry of a finite sum of matrices equals the sum of their (i, j)-entries.
Complex.re_sum- The real part of a finite sum of complex numbers is the sum of their real parts.
Finset.sum_nonneg- A finite sum of non-negative real numbers is non-negative.
in767_frame_no_parent- For r > 1, no family of positive semidefinite matrices matches the total matrix F_S and the three prescribed marginals.
- The rank-one domination lemma rank_one_psd_dominated_eq_smul is the key structural result: any positive semidefinite matrix dominated in the Loewner order by a rank-one matrix v v* must be a non-negative scalar multiple of v v*.
- Automation via norm_num handles the finite entry-by-entry verification of matrix outer products and differences, while linarith derives the final contradiction between 0 ≤ (1 - r) / 2 and 1 < r.
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 ComplexOrder Matrix BigOperatorsset_option maxHeartbeats 4000000private noncomputable def in767_F0 : Matrix (Fin 2) (Fin 2) ℂ := !![1, 1; 1, 1]private noncomputable def in767_F2 : Matrix (Fin 2) (Fin 2) ℂ := !![0, 0; 0, 1]private noncomputable def in767_F3 : Matrix (Fin 2) (Fin 2) ℂ := !![1, 0; 0, 0]private noncomputable def in767_FS : Matrix (Fin 2) (Fin 2) ℂ := !![2, 1; 1, 2]private noncomputable def in767_v0 : Fin 2 → ℂ := ![1,1]private noncomputable def in767_v2 : Fin 2 → ℂ := ![0,1]private noncomputable def in767_v3 : Fin 2 → ℂ := ![1,0]private lemma in767_outer0 : vecMulVec in767_v0 (star in767_v0) = in767_F0 := by ext i j; fin_cases i <;> fin_cases j <;> norm_num [vecMulVec_apply,in767_v0,in767_F0]private lemma in767_outer2 : vecMulVec in767_v2 (star in767_v2) = in767_F2 := by ext i j; fin_cases i <;> fin_cases j <;> norm_num [vecMulVec_apply,in767_v2,in767_F2]private lemma in767_outer3 : vecMulVec in767_v3 (star in767_v3) = in767_F3 := by ext i j; fin_cases i <;> fin_cases j <;> norm_num [vecMulVec_apply,in767_v3,in767_F3]private lemma in767_Ssub : in767_FS - 1 = in767_F0 := by ext i j; fin_cases i <;> fin_cases j <;> norm_num [in767_FS,in767_F0,Matrix.one_apply]private lemma in767_Isub : (1 : Matrix (Fin 2) (Fin 2) ℂ) - in767_F3 = in767_F2 := by ext i j; fin_cases i <;> fin_cases j <;> norm_num [in767_F3,in767_F2,Matrix.one_apply]private theorem in767_frame_no_parent (r : ℝ) (hr : 1 < r) : ¬ ∃ G : (Fin 3 → Bool) → Matrix (Fin 2) (Fin 2) ℂ, (∀ s, (G s).PosSemidef) ∧ (∑ s, G s = in767_FS) ∧ (∑ s, if s 0 then G s else 0) = in767_F3 ∧ (∑ s, if s 1 then G s else 0) = 1 ∧ (∑ s, if s 2 then G s else 0) = (1/2 : ℝ) • (in767_FS - r • in767_F0) := by classical rintro ⟨G, hG, hsum, h0, h1, h2⟩ have h0le : ∀ s, s 0 = true → (in767_F3 - G s).PosSemidef := by intro s hs have he := h0 rw [← Finset.add_sum_erase _ _ (Finset.mem_univ s), if_pos hs] at he rw [← he, add_sub_cancel_left] exact Matrix.posSemidef_sum _ fun a _ => by split_ifs · exact hG a · exact Matrix.PosSemidef.zero let F : (Fin 3 → Bool) → Matrix (Fin 2) (Fin 2) ℂ := fun s => if s 1 then 0 else G s have hFsum : ∑ s, F s = in767_F0 := by calc ∑ s, F s = (∑ s, G s) - ∑ s, (if s 1 then G s else 0) := by rw [← Finset.sum_sub_distrib] refine Finset.sum_congr rfl fun s _ => ?_ cases hs : s 1 <;> simp [F,hs] _ = in767_F0 := by rw [hsum,h1,in767_Ssub] have h1le : ∀ s, s 1 = false → (in767_F0 - G s).PosSemidef := by intro s hs have he := hFsum rw [← Finset.add_sum_erase _ _ (Finset.mem_univ s)] at he simp only [F,hs,Bool.false_eq_true,if_false] at he rw [← he, add_sub_cancel_left] exact Matrix.posSemidef_sum _ fun a _ => by split_ifs · exact Matrix.PosSemidef.zero · exact hG a have hzero : ∀ s, s 0 = true → s 1 = false → G s = 0 := by intro s hs0 hs1 have hA := h0le s hs0 have hB := h1le s hs1 rw [← in767_outer3] at hA rw [← in767_outer0] at hB obtain ⟨a, ha, ea⟩ := rank_one_psd_dominated_eq_smul (G s) in767_v3 (hG s) hA obtain ⟨b, hb, eb⟩ := rank_one_psd_dominated_eq_smul (G s) in767_v0 (hG s) hB rw [in767_outer3] at ea rw [in767_outer0] at eb have e := congrArg (fun X : Matrix (Fin 2) (Fin 2) ℂ => (X 0 1).re) (ea.symm.trans eb) have hb0 : b = 0 := by simpa [in767_F0,in767_F3] using e.symm rw [eb, hb0, zero_smul] let R : (Fin 3 → Bool) → Matrix (Fin 2) (Fin 2) ℂ := fun s => if s 1 then (if s 0 then 0 else G s) else 0 have hRsum : ∑ s, R s = in767_F2 := by calc ∑ s, R s = (∑ s, if s 1 then G s else 0) - ∑ s, (if s 0 then G s else 0) := by rw [← Finset.sum_sub_distrib] refine Finset.sum_congr rfl fun s _ => ?_ by_cases hs0 : s 0 = true <;> by_cases hs1 : s 1 = true · simp [R,hs0,hs1] · have hz := hzero s hs0 (by simpa using hs1) simp [R,hs0,hs1,hz] · simp [R,hs0,hs1] · simp [R,hs0,hs1] _ = in767_F2 := by rw [h1,h0,in767_Isub] have h2le : ∀ s, s 0 = false → s 1 = true → (in767_F2 - G s).PosSemidef := by intro s hs0 hs1 have he := hRsum rw [← Finset.add_sum_erase _ _ (Finset.mem_univ s)] at he simp only [R,hs0,hs1,if_true,Bool.false_eq_true,if_false] at he rw [← he, add_sub_cancel_left] exact Matrix.posSemidef_sum _ fun a _ => by split_ifs · exact Matrix.PosSemidef.zero · exact hG a · exact Matrix.PosSemidef.zero have hentry : ∀ s, 0 ≤ (G s 0 1).re := by intro s by_cases hs0 : s 0 = true · have hA := h0le s hs0 rw [← in767_outer3] at hA obtain ⟨a,ha,ea⟩ := rank_one_psd_dominated_eq_smul (G s) in767_v3 (hG s) hA rw [in767_outer3] at ea rw [ea] simp [in767_F3] · have hs0' : s 0 = false := by simpa using hs0 by_cases hs1 : s 1 = true · have hA := h2le s hs0' hs1 rw [← in767_outer2] at hA obtain ⟨a,ha,ea⟩ := rank_one_psd_dominated_eq_smul (G s) in767_v2 (hG s) hA rw [in767_outer2] at ea rw [ea] simp [in767_F2] · have hs1' : s 1 = false := by simpa using hs1 have hA := h1le s hs1' rw [← in767_outer0] at hA obtain ⟨a,ha,ea⟩ := rank_one_psd_dominated_eq_smul (G s) in767_v0 (hG s) hA rw [in767_outer0] at ea rw [ea] simpa [in767_F0] using ha have hnonneg : 0 ≤ ((∑ s : (Fin 3 → Bool), if s 2 then G s else 0) 0 1).re := by simp only [Matrix.sum_apply, Complex.re_sum] exact Finset.sum_nonneg fun s _ => by split_ifs <;> simp_all rw [h2] at hnonneg norm_num [in767_FS,in767_F0] at hnonneg linariththeorem rank_two_frame_compression_no_parent (r : ℝ) (hr : 1 < r) : ¬ ∃ G : (Fin 3 → Bool) → Matrix (Fin 2) (Fin 2) ℂ, (∀ s, (G s).PosSemidef) ∧ (∑ s, G s = !![2, 1; 1, 2]) ∧ (∑ s, if s 0 then G s else 0) = !![1, 0; 0, 0] ∧ (∑ s, if s 1 then G s else 0) = 1 ∧ (∑ s, if s 2 then G s else 0) = (1/2 : ℝ) • (!![2, 1; 1, 2] - r • !![1, 1; 1, 1]) := by exact in767_frame_no_parent r hr