magic_square_guess_fn_concaveOn
The function g = magic_square_guess_fn — g(w) is the supremum of the adversary's probability of guessing Alice's complete first-row answer in the magic-square game, over finite-dimensional strategies with quantum side information and score at least w — is concave on the interval (-∞, 1] (ConcaveOn ℝ (Set.Iic 1)).
Statement
theorem magic_square_guess_fn_concaveOn : ConcaveOn ℝ (Set.Iic 1) magic_square_guess_fn- Related work
- OP-730: arXiv:2610.12001 (Exact value and rigidity of the 2x3 magic rectangle), Sec. 8 asks for the exact function g(w) and its slope c* at the threshold; Corollary 6.2 bounds 1 - g(β₀+δ) between (9/2)δ and 3δ/(4(1-β₀)).
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- magic_square_guess_fnmagic_square_guess_fn w is the real supremum (sSup in ℝ) of the set of reals p for which there exist dA dB dE : ℕ, A : Fin 3 → (Fin 3 →…
- magic_square_strategy_validGiven dA dB dE : ℕ, Alice's effects A : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA) (Fin dA) ℂ (A x s: row x, then answer s), Bob's effects B…
- magic_square_key_guess_successGiven dA dB dE : ℕ, Alice's effects A : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA) (Fin dA) ℂ, a complex matrix ρ indexed by (Fin dA × Fin…
- ProbabilisticTheory.instArchimedeanOrderUnitSpaceRealThe real numbers form an Archimedean order-unit space.
- is_povmA finite family of complex d×d matrices indexed by a finite outcome set is a POVM (positive-operator-valued measure): each effect is…
- ProbabilisticTheory.OrderedVectorSpaceAn ordered real vector space.
- magic_square_scoreGiven dA dB dE : ℕ, Alice's effects A : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA) (Fin dA) ℂ (A x s: row x, then answer s), Bob's effects B…
- ProbabilisticTheory.ArchimedeanOrderUnitSpaceAn order-unit space whose distinguished order unit is Archimedean.
- ProbabilisticTheory.OrderUnitSpaceAn ordered real vector space whose distinguished element
1is an order unit: it is nonnegative, and every element is bounded above by a…
- Used by 1
- magic_square_guess_fn_ge_linearFor 0 ≤ δ ≤ 1 - β₀, with β₀ = (2 + √(2/3))/3 the magic-square threshold: 1 - g(β₀ + δ) ≤ 3δ / (4(1 - β₀)), where β₀ =…
Read back from the Lean
The function magic_square_guess_fn is concave on the interval $(-\infty, 1]$ (i.e., Set.Iic 1).
Here, magic_square_guess_fn(w) is defined as the supremum of the key guessing probabilities $p \in \mathbb{R}$ achievable by Eve over all finite-dimensional quantum strategies $(dA, dB, dE, A, B, \rho, M)$ such that:
1. $A$ is a family of POVMs for Alice (indexed by row $x \in \{0, 1, 2\}$, with outcomes in $\{0, 1\}^3$) such that outcomes with odd parity have measurement operator 0;
2. $B$ is a family of POVMs for Bob (indexed by column $j \in \{0, 1, 2\}$, with outcomes in $\{0, 1\}^3$) such that outcomes with even parity have measurement operator 0;
3. $\rho$ is a valid density operator (positive semidefinite with trace 1) on the tripartite space $\mathbb{C}^{dA} \otimes \mathbb{C}^{dB} \otimes \mathbb{C}^{dE}$;
4. $M$ is a POVM on $\mathbb{C}^{dE}$ indexed by $\{0, 1\}^3$ (Eve's measurement to guess Alice's output);
5. the expected score of Alice and Bob in the magic square game under strategy $(A, B, \rho)$ is at least $w$; and
6. $p$ is Eve's success probability of guessing Alice's outcome for row $0$ using measurement $M$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The adversary's optimal guessing probability g(w) is defined as the supremum of key-guessing success probabilities over valid quantum strategies that achieve a game score of at least w. To prove concavity on (-∞, 1], given strategies achieving scores w₁, w₂ and guess probabilities p₁, p₂, one forms a direct-sum strategy using block-diagonal POVMs and a convex mixture of density matrices a ρ₁ ⊕ b ρ₂. By orthogonality of the direct-sum blocks, the score and guessing success of the mixed strategy are strictly linear, showing that a p₁ + b p₂ is achievable with score at least a w₁ + b w₂. Evaluating the supremum over ε-approximations of g(w₁) and g(w₂), enabled by non-emptiness of the strategy set via the explicit perfect Mermin-Peres strategy, establishes that g(a w₁ + b w₂) ≥ a g(w₁) + b g(w₂).
The inclusion matrices incL and incR embed ℂⁿ and ℂᵐ isometrically and orthogonally into ℂⁿ⁺ᵐ, with incL * incLᴴ = 1, incR * incRᴴ = 1, incL * incRᴴ = 0, and incLᴴ * incL + incRᴴ * incR = 1
The index set Fin (n + m) is partitioned into Fin n via castAdd and Fin m via natAdd, which never overlap (shown by omega). Expanding matrix products entrywise shows that incL and incR are co-isometries whose ranges are mutually orthogonal, and splitting index cases with Fin.addCases confirms that their projections sum to the identity.
uses
iff_false,Fin.addCases@[simp] lemma castAdd_eq_natAdd_iff {n m : ℕ} (i : Fin n) (j : Fin m) : Fin.castAdd m i = Fin.natAdd n j ↔ False := by simp only [Fin.ext_iff, Fin.val_castAdd, Fin.val_natAdd, iff_false]; omega @[simp] lemma natAdd_eq_castAdd_iff {n m : ℕ} (i : Fin n) (j : Fin m) : Fin.natAdd n j = Fin.castAdd m i ↔ False := by simp only [Fin.ext_iff, Fin.val_castAdd, Fin.val_natAdd, iff_false]; omega /-- inclusion of the first block -/ def incL (n m : ℕ) : Matrix (Fin n) (Fin (n + m)) ℂ := Matrix.of fun i j => if j = Fin.castAdd m i then 1 else 0 def incR (n m : ℕ) : Matrix (Fin m) (Fin (n + m)) ℂ := Matrix.of fun i j => if j = Fin.natAdd n i then 1 else 0 lemma incL_mul_conj (n m : ℕ) : incL n m * (incL n m)ᴴ = 1 := by ext i i' simp [incL, Matrix.mul_apply, Matrix.conjTranspose_apply, Matrix.one_apply, eq_comm] lemma incR_mul_conj (n m : ℕ) : incR n m * (incR n m)ᴴ = 1 := by ext i i' simp [incR, Matrix.mul_apply, Matrix.conjTranspose_apply, Matrix.one_apply, eq_comm] lemma incL_mul_conjR (n m : ℕ) : incL n m * (incR n m)ᴴ = 0 := by ext i i' simp [incL, incR, Matrix.mul_apply, Matrix.conjTranspose_apply] lemma incR_mul_conjL (n m : ℕ) : incR n m * (incL n m)ᴴ = 0 := by ext i i' simp [incL, incR, Matrix.mul_apply, Matrix.conjTranspose_apply] lemma conj_inc_add (n m : ℕ) : (incL n m)ᴴ * incL n m + (incR n m)ᴴ * incR n m = 1 := by ext j j' refine Fin.addCases (fun i => ?_) (fun i => ?_) j <;> refine Fin.addCases (fun i' => ?_) (fun i' => ?_) j' <;> simp [incL, incR, Matrix.mul_apply, Matrix.conjTranspose_apply, Matrix.one_apply, eq_comm]
Block-diagonal direct sums blk(X, Y) preserve matrix operations, positive semidefiniteness, and the POVM property
The block sum blk(X, Y) = incLᴴ * X * incL + incRᴴ * Y * incR compresses back to X and Y via compL_blk and compR_blk because cross-terms vanish. Since each summand is a congruence of a positive semidefinite matrix, blk preserves positive semidefiniteness; and since blk distributes over addition and maps (1, 1) to 1, the block sum of two POVMs is a valid POVM of dimension n + m.
uses
incL_mul_conj,incR_mul_conj,incL_mul_conjR,incR_mul_conjL,conj_inc_add/-- block-diagonal sum -/ def blk {n m : ℕ} (X : Matrix (Fin n) (Fin n) ℂ) (Y : Matrix (Fin m) (Fin m) ℂ) : Matrix (Fin (n + m)) (Fin (n + m)) ℂ := (incL n m)ᴴ * X * incL n m + (incR n m)ᴴ * Y * incR n m lemma compL_blk {n m : ℕ} (X : Matrix (Fin n) (Fin n) ℂ) (Y : Matrix (Fin m) (Fin m) ℂ) : incL n m * blk X Y * (incL n m)ᴴ = X := by simp only [blk, Matrix.mul_add, Matrix.add_mul, ← Matrix.mul_assoc, incL_mul_conj, incL_mul_conjR, Matrix.one_mul, Matrix.zero_mul] simp [Matrix.mul_assoc, incL_mul_conj] lemma compR_blk {n m : ℕ} (X : Matrix (Fin n) (Fin n) ℂ) (Y : Matrix (Fin m) (Fin m) ℂ) : incR n m * blk X Y * (incR n m)ᴴ = Y := by simp only [blk, Matrix.mul_add, Matrix.add_mul, ← Matrix.mul_assoc, incR_mul_conj, incR_mul_conjL, Matrix.one_mul, Matrix.zero_mul] simp [Matrix.mul_assoc, incR_mul_conj] lemma blk_psd {n m : ℕ} {X : Matrix (Fin n) (Fin n) ℂ} {Y : Matrix (Fin m) (Fin m) ℂ} (hX : X.PosSemidef) (hY : Y.PosSemidef) : (blk X Y).PosSemidef := (hX.conjTranspose_mul_mul_same _).add (hY.conjTranspose_mul_mul_same _) lemma blk_zero (n m : ℕ) : blk (0 : Matrix (Fin n) (Fin n) ℂ) (0 : Matrix (Fin m) (Fin m) ℂ) = 0 := by simp [blk] lemma blk_one (n m : ℕ) : blk (1 : Matrix (Fin n) (Fin n) ℂ) (1 : Matrix (Fin m) (Fin m) ℂ) = 1 := by simp [blk, conj_inc_add] lemma blk_sum {n m : ℕ} {ι : Type} [Fintype ι] (X : ι → Matrix (Fin n) (Fin n) ℂ) (Y : ι → Matrix (Fin m) (Fin m) ℂ) : ∑ i, blk (X i) (Y i) = blk (∑ i, X i) (∑ i, Y i) := by simp [blk, Finset.sum_add_distrib, Matrix.sum_mul, Matrix.mul_sum] lemma blk_povm {n m : ℕ} {ι : Type} [Fintype ι] {X : ι → Matrix (Fin n) (Fin n) ℂ} {Y : ι → Matrix (Fin m) (Fin m) ℂ} (hX : is_povm n X) (hY : is_povm m Y) : is_povm (n + m) (fun i => blk (X i) (Y i)) := ⟨fun i => blk_psd (hX.1 i) (hY.1 i), by rw [blk_sum, hX.2, hY.2, blk_one]⟩
Kronecker products of isometries compress density matrices while preserving trace and commuting cyclically under the trace
Cyclicity of trace (Matrix.trace_mul_comm) allows shifting the conjugate isometric embedding (VAᴴ ⊗ VBᴴ ⊗ VEᴴ) onto the tripartite observable X ⊗ Y ⊗ Z, yielding the compressed observable (VA * X * VAᴴ) ⊗ (VB * Y * VBᴴ) ⊗ (VE * Z * VEᴴ). When VA, VB, VE are co-isometries (V * Vᴴ = 1), their compressed identity is the identity, so compressing any density matrix preserves its trace (iso_trace).
uses
Matrix.trace_mul_comm,Matrix.conjTranspose_kronecker,Matrix.mul_kronecker_mul,Matrix.one_kronecker_one/-- the trace-linear-form fact: compression through a Kronecker isometry -/ lemma tr_kron_conj {a a' b b' e e' : ℕ} (VA : Matrix (Fin a) (Fin a') ℂ) (VB : Matrix (Fin b) (Fin b') ℂ) (VE : Matrix (Fin e) (Fin e') ℂ) (X : Matrix (Fin a') (Fin a') ℂ) (Y : Matrix (Fin b') (Fin b') ℂ) (Z : Matrix (Fin e') (Fin e') ℂ) (ρ : Matrix ((Fin a × Fin b) × Fin e) ((Fin a × Fin b) × Fin e) ℂ) : (((X ⊗ₖ Y) ⊗ₖ Z) * (((VAᴴ ⊗ₖ VBᴴ) ⊗ₖ VEᴴ) * ρ * ((VAᴴ ⊗ₖ VBᴴ) ⊗ₖ VEᴴ)ᴴ)).trace = ((((VA * X * VAᴴ) ⊗ₖ (VB * Y * VBᴴ)) ⊗ₖ (VE * Z * VEᴴ)) * ρ).trace := by rw [← Matrix.mul_assoc, ← Matrix.mul_assoc, Matrix.trace_mul_comm, ← Matrix.mul_assoc] congr 2 simp only [Matrix.conjTranspose_kronecker, Matrix.conjTranspose_conjTranspose, ← Matrix.mul_kronecker_mul, Matrix.mul_assoc] lemma compL_one (n m : ℕ) : incL n m * (1 : Matrix (Fin (n + m)) (Fin (n + m)) ℂ) * (incL n m)ᴴ = 1 := by rw [Matrix.mul_one, incL_mul_conj] lemma compR_one (n m : ℕ) : incR n m * (1 : Matrix (Fin (n + m)) (Fin (n + m)) ℂ) * (incR n m)ᴴ = 1 := by rw [Matrix.mul_one, incR_mul_conj] lemma iso_trace {a a' b b' e e' : ℕ} (VA : Matrix (Fin a') (Fin a) ℂ) (VB : Matrix (Fin b') (Fin b) ℂ) (VE : Matrix (Fin e') (Fin e) ℂ) (hA : VA * VAᴴ = 1) (hB : VB * VBᴴ = 1) (hE : VE * VEᴴ = 1) (ρ : Matrix ((Fin a' × Fin b') × Fin e') ((Fin a' × Fin b') × Fin e') ℂ) : (((VAᴴ ⊗ₖ VBᴴ) ⊗ₖ VEᴴ) * ρ * ((VAᴴ ⊗ₖ VBᴴ) ⊗ₖ VEᴴ)ᴴ).trace = ρ.trace := by rw [Matrix.trace_mul_comm, ← Matrix.mul_assoc] simp only [Matrix.conjTranspose_kronecker, Matrix.conjTranspose_conjTranspose, ← Matrix.mul_kronecker_mul, hA, hB, hE, Matrix.one_kronecker_one, Matrix.one_mul]
For valid quantum strategies and convex weights a, b ≥ 0 with a + b = 1, the block-mixture strategy mixρ with block POVMs is a valid quantum strategy
The mixed state mixρ(a, b, ρ₁, ρ₂) is the convex combination of ρ₁ and ρ₂ embedded via (incLᴴ)⊗³ and (incRᴴ)⊗³. By iso_trace, Tr(mixρ) = a Tr(ρ₁) + b Tr(ρ₂) = a + b = 1. The state is positive semidefinite as the sum of positive semidefinite matrices, the block POVMs are valid by blk_povm, and they vanish on impossible parity outcomes since each block component vanishes (blk_zero). Linearity of the trace against block observables is established by tr_mix.
uses
tr_kron_conj,compL_blk,compR_blk,blk_povm,blk_zero,iso_tracesection mix variable {dA1 dB1 dE1 dA2 dB2 dE2 : ℕ} noncomputable def mixρ (a b : ℝ) (ρ1 : Matrix ((Fin dA1 × Fin dB1) × Fin dE1) ((Fin dA1 × Fin dB1) × Fin dE1) ℂ) (ρ2 : Matrix ((Fin dA2 × Fin dB2) × Fin dE2) ((Fin dA2 × Fin dB2) × Fin dE2) ℂ) : Matrix ((Fin (dA1 + dA2) × Fin (dB1 + dB2)) × Fin (dE1 + dE2)) ((Fin (dA1 + dA2) × Fin (dB1 + dB2)) × Fin (dE1 + dE2)) ℂ := (a : ℂ) • ((((incL dA1 dA2)ᴴ ⊗ₖ (incL dB1 dB2)ᴴ) ⊗ₖ (incL dE1 dE2)ᴴ) * ρ1 * (((incL dA1 dA2)ᴴ ⊗ₖ (incL dB1 dB2)ᴴ) ⊗ₖ (incL dE1 dE2)ᴴ)ᴴ) + (b : ℂ) • ((((incR dA1 dA2)ᴴ ⊗ₖ (incR dB1 dB2)ᴴ) ⊗ₖ (incR dE1 dE2)ᴴ) * ρ2 * (((incR dA1 dA2)ᴴ ⊗ₖ (incR dB1 dB2)ᴴ) ⊗ₖ (incR dE1 dE2)ᴴ)ᴴ) lemma tr_mix (a b : ℝ) (ρ1 : Matrix ((Fin dA1 × Fin dB1) × Fin dE1) ((Fin dA1 × Fin dB1) × Fin dE1) ℂ) (ρ2 : Matrix ((Fin dA2 × Fin dB2) × Fin dE2) ((Fin dA2 × Fin dB2) × Fin dE2) ℂ) (X1 : Matrix (Fin dA1) (Fin dA1) ℂ) (X2 : Matrix (Fin dA2) (Fin dA2) ℂ) (Y1 : Matrix (Fin dB1) (Fin dB1) ℂ) (Y2 : Matrix (Fin dB2) (Fin dB2) ℂ) (Z1 : Matrix (Fin dE1) (Fin dE1) ℂ) (Z2 : Matrix (Fin dE2) (Fin dE2) ℂ) : (((blk X1 X2 ⊗ₖ blk Y1 Y2) ⊗ₖ blk Z1 Z2) * mixρ a b ρ1 ρ2).trace.re = a * (((X1 ⊗ₖ Y1) ⊗ₖ Z1) * ρ1).trace.re + b * (((X2 ⊗ₖ Y2) ⊗ₖ Z2) * ρ2).trace.re := by rw [mixρ, Matrix.mul_add, Matrix.mul_smul, Matrix.mul_smul, Matrix.trace_add, Matrix.trace_smul, Matrix.trace_smul, tr_kron_conj, tr_kron_conj, compL_blk, compL_blk, compL_blk, compR_blk, compR_blk, compR_blk] simp [Complex.add_re] lemma blk_one' (n m : ℕ) : (1 : Matrix (Fin (n + m)) (Fin (n + m)) ℂ) = blk 1 1 := (blk_one n m).symm open scoped ComplexOrder in lemma mixρ_valid (a b : ℝ) (ha : 0 ≤ a) (hb : 0 ≤ b) (hab : a + b = 1) {A1 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA1) (Fin dA1) ℂ} {B1 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dB1) (Fin dB1) ℂ} {ρ1 : Matrix ((Fin dA1 × Fin dB1) × Fin dE1) ((Fin dA1 × Fin dB1) × Fin dE1) ℂ} {A2 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA2) (Fin dA2) ℂ} {B2 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dB2) (Fin dB2) ℂ} {ρ2 : Matrix ((Fin dA2 × Fin dB2) × Fin dE2) ((Fin dA2 × Fin dB2) × Fin dE2) ℂ} (h1 : magic_square_strategy_valid A1 B1 ρ1) (h2 : magic_square_strategy_valid A2 B2 ρ2) : magic_square_strategy_valid (fun x s => blk (A1 x s) (A2 x s)) (fun j c => blk (B1 j c) (B2 j c)) (mixρ a b ρ1 ρ2) := by obtain ⟨hA1, hA1z, hB1, hB1z, hρ1, htr1⟩ := h1 obtain ⟨hA2, hA2z, hB2, hB2z, hρ2, htr2⟩ := h2 refine ⟨fun x => blk_povm (hA1 x) (hA2 x), fun x s hs => ?_, fun j => blk_povm (hB1 j) (hB2 j), fun j c hc => ?_, ?_, ?_⟩ · simp only [hA1z x s hs, hA2z x s hs, blk_zero] · simp only [hB1z j c hc, hB2z j c hc, blk_zero] · refine Matrix.PosSemidef.add ((hρ1.mul_mul_conjTranspose_same _).smul ?_) ((hρ2.mul_mul_conjTranspose_same _).smul ?_) · exact_mod_cast ha · exact_mod_cast hb · rw [mixρ, Matrix.trace_add, Matrix.trace_smul, Matrix.trace_smul, iso_trace _ _ _ (incL_mul_conj _ _) (incL_mul_conj _ _) (incL_mul_conj _ _), iso_trace _ _ _ (incR_mul_conj _ _) (incR_mul_conj _ _) (incR_mul_conj _ _), htr1, htr2] simp only [smul_eq_mul, mul_one] exact_mod_cast hab
The magic-square score and key guessing success of the mixed strategy are the exact convex combinations of the scores and guessing successes of the constituent strategies
The game score is a weighted sum over question pairs of traces against ρ with the eavesdropper's factor equal to 1. By tr_mix, each trace term decomposes into a times the first strategy's term plus b times the second strategy's term, proving mix_score. The same trace linearity applies to Eve's key guessing success probability against Alice's row-0 measurement, proving mix_guess.
uses
magic_square_score,tr_mix,magic_square_key_guess_successlemma mix_score (a b : ℝ) (A1 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA1) (Fin dA1) ℂ) (B1 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dB1) (Fin dB1) ℂ) (ρ1 : Matrix ((Fin dA1 × Fin dB1) × Fin dE1) ((Fin dA1 × Fin dB1) × Fin dE1) ℂ) (A2 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA2) (Fin dA2) ℂ) (B2 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dB2) (Fin dB2) ℂ) (ρ2 : Matrix ((Fin dA2 × Fin dB2) × Fin dE2) ((Fin dA2 × Fin dB2) × Fin dE2) ℂ) : magic_square_score (fun x s => blk (A1 x s) (A2 x s)) (fun j c => blk (B1 j c) (B2 j c)) (mixρ a b ρ1 ρ2) = a * magic_square_score A1 B1 ρ1 + b * magic_square_score A2 B2 ρ2 := by simp only [magic_square_score, blk_one', tr_mix] simp only [Finset.mul_sum, ← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun x _ => Finset.sum_congr rfl fun j _ => Finset.sum_congr rfl fun s _ => Finset.sum_congr rfl fun c _ => ?_ split_ifs <;> ring lemma mix_guess (a b : ℝ) (A1 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA1) (Fin dA1) ℂ) (ρ1 : Matrix ((Fin dA1 × Fin dB1) × Fin dE1) ((Fin dA1 × Fin dB1) × Fin dE1) ℂ) (M1 : (Fin 3 → Bool) → Matrix (Fin dE1) (Fin dE1) ℂ) (A2 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA2) (Fin dA2) ℂ) (ρ2 : Matrix ((Fin dA2 × Fin dB2) × Fin dE2) ((Fin dA2 × Fin dB2) × Fin dE2) ℂ) (M2 : (Fin 3 → Bool) → Matrix (Fin dE2) (Fin dE2) ℂ) : magic_square_key_guess_success (fun x s => blk (A1 x s) (A2 x s)) (mixρ a b ρ1 ρ2) (fun k => blk (M1 k) (M2 k)) = a * magic_square_key_guess_success A1 ρ1 M1 + b * magic_square_key_guess_success A2 ρ2 M2 := by simp only [magic_square_key_guess_success, blk_one', tr_mix] simp only [Finset.mul_sum, ← Finset.sum_add_distrib] end mix
The integer matrices PA and PB define projective measurements on ℂ⁴ that win the magic-square game on all 576 valid question-answer configurations automation
Nine commuting Pauli-type observables Obs(x, j) over ℤ are combined with sign parities to define PA(x, s) and PB(j, c). Kernel evaluation (decide +kernel) proves that these matrices are symmetric and idempotent up to a factor of 4, sum over outcomes to 4 • 1, and produce a total unnormalized winning correlation sum of 576.
def Obs : Fin 3 → Fin 3 → Matrix (Fin 4) (Fin 4) ℤ := ![![!![0, 0, 1, 0; 0, 0, 0, 1; 1, 0, 0, 0; 0, 1, 0, 0], !![0, 1, 0, 0; 1, 0, 0, 0; 0, 0, 0, 1; 0, 0, 1, 0], !![0, 0, 0, 1; 0, 0, 1, 0; 0, 1, 0, 0; 1, 0, 0, 0]], ![!![1, 0, 0, 0; 0, -1, 0, 0; 0, 0, 1, 0; 0, 0, 0, -1], !![1, 0, 0, 0; 0, 1, 0, 0; 0, 0, -1, 0; 0, 0, 0, -1], !![1, 0, 0, 0; 0, -1, 0, 0; 0, 0, -1, 0; 0, 0, 0, 1]], ![!![0, 0, -1, 0; 0, 0, 0, 1; -1, 0, 0, 0; 0, 1, 0, 0], !![0, -1, 0, 0; -1, 0, 0, 0; 0, 0, 0, 1; 0, 0, 1, 0], !![0, 0, 0, -1; 0, 0, 1, 0; 0, 1, 0, 0; -1, 0, 0, 0]]] def perf_sg (b : Bool) : ℤ := if b then -1 else 1 def PA (x : Fin 3) (s : Fin 3 → Bool) : Matrix (Fin 4) (Fin 4) ℤ := if xor (xor (s 0) (s 1)) (s 2) = true then 0 else (1 + perf_sg (s 0) • Obs x 0) * (1 + perf_sg (s 1) • Obs x 1) def PB (j : Fin 3) (c : Fin 3 → Bool) : Matrix (Fin 4) (Fin 4) ℤ := if xor (xor (c 0) (c 1)) (c 2) = false then 0 else (1 + perf_sg (c 0) • Obs 0 j) * (1 + perf_sg (c 1) • Obs 1 j) set_option maxRecDepth 100000 in theorem PA_proj : ∀ x s, PA x s * PA x s = 4 • PA x s ∧ (PA x s).transpose = PA x s := by decide +kernel set_option maxRecDepth 100000 in theorem PB_proj : ∀ j c, PB j c * PB j c = 4 • PB j c ∧ (PB j c).transpose = PB j c := by decide +kernel set_option maxRecDepth 100000 in theorem PA_sum : ∀ x, ∑ s, PA x s = 4 • (1 : Matrix (Fin 4) (Fin 4) ℤ) := by decide +kernel set_option maxRecDepth 100000 in theorem PB_sum : ∀ j, ∑ c, PB j c = 4 • (1 : Matrix (Fin 4) (Fin 4) ℤ) := by decide +kernel set_option maxRecDepth 100000 in theorem win_sum : (∑ x : Fin 3, ∑ j : Fin 3, ∑ s : Fin 3 → Bool, ∑ c : Fin 3 → Bool, if s j = c x then ∑ a : Fin 4, ∑ a' : Fin 4, PA x s a a' * PB j c a a' else 0) = 576 := by decide +kernel
Rescaling the integer projectors by 1/4 and pairing them with the maximally entangled state ρc yields a valid quantum strategy achieving the maximum score of 1
Any symmetric integer matrix with P² = 4P satisfies (1/4 P) = (1/4 P)(1/4 P)ᴴ, which is positive semidefinite by Matrix.posSemidef_self_mul_conjTranspose, so Ac = (1/4) PA and Bc = (1/4) PB are valid POVMs. The maximally entangled state ρc = |ψ⟩⟨ψ| is positive semidefinite with trace 1. Its game score is (1/9) * (576 / 64) = 1, verified from the total correlation sum win_sum.
uses
Matrix.posSemidef_self_mul_conjTranspose,Matrix.posSemidef_vecMulVec_self_star,win_sumopen Matrix in noncomputable def Ac (x : Fin 3) (s : Fin 3 → Bool) : Matrix (Fin 4) (Fin 4) ℂ := (1 / 4 : ℂ) • (Int.castRingHom ℂ).mapMatrix (PA x s) open Matrix in noncomputable def Bc (j : Fin 3) (c : Fin 3 → Bool) : Matrix (Fin 4) (Fin 4) ℂ := (1 / 4 : ℂ) • (Int.castRingHom ℂ).mapMatrix (PB j c) noncomputable def perf_psi : (Fin 4 × Fin 4) × Fin 1 → ℂ := fun i => if i.1.1 = i.1.2 then 1 / 2 else 0 noncomputable def ρc : Matrix ((Fin 4 × Fin 4) × Fin 1) ((Fin 4 × Fin 4) × Fin 1) ℂ := Matrix.vecMulVec perf_psi (star perf_psi) open Matrix in open scoped ComplexOrder in lemma psd_of_proj (P : Matrix (Fin 4) (Fin 4) ℤ) (h : P * P = 4 • P ∧ P.transpose = P) : ((1 / 4 : ℂ) • (Int.castRingHom ℂ).mapMatrix P).PosSemidef := by have hc : ((1 / 4 : ℂ) • (Int.castRingHom ℂ).mapMatrix P)ᴴ = (1 / 4 : ℂ) • (Int.castRingHom ℂ).mapMatrix P := by ext i j have := congrFun (congrFun h.2 i) j simp only [Matrix.transpose_apply] at this simp [Matrix.conjTranspose_apply, this] have hm : (1 / 4 : ℂ) • (Int.castRingHom ℂ).mapMatrix P = ((1 / 4 : ℂ) • (Int.castRingHom ℂ).mapMatrix P) * ((1 / 4 : ℂ) • (Int.castRingHom ℂ).mapMatrix P)ᴴ := by rw [hc, Matrix.smul_mul, Matrix.mul_smul, ← map_mul, h.1, map_nsmul, ← Nat.cast_smul_eq_nsmul ℂ, smul_smul, smul_smul] norm_num rw [hm] exact Matrix.posSemidef_self_mul_conjTranspose _ lemma perf_tr_rho (X Y : Matrix (Fin 4) (Fin 4) ℂ) : (((X ⊗ₖ Y) ⊗ₖ (1 : Matrix (Fin 1) (Fin 1) ℂ)) * ρc).trace = (1 / 4) * ∑ a : Fin 4, ∑ a' : Fin 4, X a a' * Y a a' := by simp [Matrix.trace, Matrix.mul_apply, ρc, Matrix.vecMulVec_apply, perf_psi, Fintype.sum_prod_type, Matrix.kroneckerMap_apply, Fin.sum_univ_four, map_ofNat] ring open scoped ComplexOrder in lemma perf_valid : magic_square_strategy_valid Ac Bc ρc := by refine ⟨fun x => ⟨fun s => psd_of_proj _ (PA_proj x s), ?_⟩, fun x s hs => ?_, fun j => ⟨fun c => psd_of_proj _ (PB_proj j c), ?_⟩, fun j c hc => ?_, ?_, ?_⟩ · simp only [Ac] rw [← Finset.smul_sum, ← map_sum, PA_sum, map_nsmul, map_one, ← Nat.cast_smul_eq_nsmul ℂ, smul_smul] norm_num · simp [Ac, PA, hs] · simp only [Bc] rw [← Finset.smul_sum, ← map_sum, PB_sum, map_nsmul, map_one, ← Nat.cast_smul_eq_nsmul ℂ, smul_smul] norm_num · simp [Bc, PB, hc] · exact Matrix.posSemidef_vecMulVec_self_star perf_psi · simp [ρc, Matrix.trace, Matrix.vecMulVec_apply, perf_psi, Fintype.sum_prod_type, map_ofNat] norm_num lemma perf_entry (x j : Fin 3) (s c : Fin 3 → Bool) : (((Ac x s ⊗ₖ Bc j c) ⊗ₖ (1 : Matrix (Fin 1) (Fin 1) ℂ)) * ρc).trace.re = 1 / 64 * ((∑ a : Fin 4, ∑ a' : Fin 4, PA x s a a' * PB j c a a' : ℤ) : ℝ) := by rw [perf_tr_rho] have : (1 / 4 : ℂ) * ∑ a : Fin 4, ∑ a' : Fin 4, Ac x s a a' * Bc j c a a' = ((1 / 64 * ((∑ a : Fin 4, ∑ a' : Fin 4, PA x s a a' * PB j c a a' : ℤ) : ℝ) : ℝ) : ℂ) := by simp only [Ac, Bc, Matrix.smul_apply, RingHom.mapMatrix_apply, Matrix.map_apply, eq_intCast, smul_eq_mul] push_cast simp only [Finset.mul_sum] refine Finset.sum_congr rfl fun a _ => Finset.sum_congr rfl fun a' _ => ?_ ring rw [this, Complex.ofReal_re] lemma score_one : magic_square_score Ac Bc ρc = 1 := by have h := congrArg (Int.cast : ℤ → ℝ) win_sum push_cast at h have : magic_square_score Ac Bc ρc = 1 / 576 * (∑ x : Fin 3, ∑ j : Fin 3, ∑ s : Fin 3 → Bool, ∑ c : Fin 3 → Bool, if s j = c x then ∑ a : Fin 4, ∑ a' : Fin 4, ((PA x s a a' : ℝ) * (PB j c a a' : ℝ)) else 0) := by rw [magic_square_score] simp only [perf_entry, Finset.mul_sum] refine Finset.sum_congr rfl fun x _ => Finset.sum_congr rfl fun j _ => Finset.sum_congr rfl fun s _ => Finset.sum_congr rfl fun c _ => ?_ split_ifs · push_cast; simp only [Finset.mul_sum] refine Finset.sum_congr rfl fun a _ => Finset.sum_congr rfl fun a' _ => ?_ ring · simp rw [this, h] norm_num
In any valid quantum strategy, Eve's success probability of guessing Alice's complete first-row answer is at most 1
The product of positive semidefinite matrices has non-negative real trace (tr_psd_mul), proved using square roots from continuous functional calculus. Since 1 - M(k) is positive semidefinite for any POVM element (one_sub_povm), replacing M(k) by 1 increases the trace. Summing over all keys k collapses Alice's POVM to 1, bounding the total guessing probability by Tr(ρ) = 1.
uses
tr_psd_mul,one_sub_povm,Matrix.posSemidef_sumopen scoped ComplexOrder MatrixOrder in lemma tr_psd_mul {n : Type} [Fintype n] [DecidableEq n] {P ρ : Matrix n n ℂ} (hP : P.PosSemidef) (hρ : ρ.PosSemidef) : 0 ≤ (P * ρ).trace.re := by obtain ⟨X, hX, -, rfl⟩ := CFC.exists_sqrt_of_isSelfAdjoint_of_quasispectrumRestricts hP.isHermitian (QuasispectrumRestricts.nnreal_of_nonneg hP.nonneg) rw [Matrix.mul_assoc, Matrix.trace_mul_comm, Matrix.mul_assoc, ← Matrix.mul_assoc] have h := hρ.mul_mul_conjTranspose_same X rw [← Matrix.star_eq_conjTranspose, hX.star_eq] at h exact (Complex.nonneg_iff.1 h.trace_nonneg).1 open scoped ComplexOrder in lemma one_sub_povm {d : ℕ} {M : (Fin 3 → Bool) → Matrix (Fin d) (Fin d) ℂ} (hM : is_povm d M) (k : Fin 3 → Bool) : (1 - M k).PosSemidef := by have : 1 - M k = ∑ i ∈ Finset.univ.erase k, M i := by rw [← hM.2, ← Finset.add_sum_erase _ _ (Finset.mem_univ k)] abel rw [this] exact Matrix.posSemidef_sum _ fun i _ => hM.1 i lemma guess_le_one {dA dB dE : ℕ} {A : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA) (Fin dA) ℂ} {B : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dB) (Fin dB) ℂ} {ρ : Matrix ((Fin dA × Fin dB) × Fin dE) ((Fin dA × Fin dB) × Fin dE) ℂ} {M : (Fin 3 → Bool) → Matrix (Fin dE) (Fin dE) ℂ} (hv : magic_square_strategy_valid A B ρ) (hM : is_povm dE M) : magic_square_key_guess_success A ρ M ≤ 1 := by obtain ⟨hA, -, -, -, hρ, htr⟩ := hv have key : ∀ k, (((A 0 k ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ M k) * ρ).trace.re ≤ (((A 0 k ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ (1 : Matrix (Fin dE) (Fin dE) ℂ)) * ρ).trace.re := by intro k have h := tr_psd_mul (((hA 0).1 k).kronecker Matrix.PosSemidef.one |>.kronecker (one_sub_povm hM k)) hρ have hk : ((A 0 k ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ (1 - M k)) = ((A 0 k ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ 1) - ((A 0 k ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ M k) := by rw [eq_sub_iff_add_eq, ← Matrix.kronecker_add, sub_add_cancel] rw [hk, Matrix.sub_mul, Matrix.trace_sub, Complex.sub_re] at h linarith have hsum : ∑ k, (((A 0 k ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ (1 : Matrix (Fin dE) (Fin dE) ℂ)) * ρ).trace.re = 1 := by have h1 : ∑ k, ((A 0 k ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ (1 : Matrix (Fin dE) (Fin dE) ℂ)) = 1 := by have h2 : ∑ k, ((A 0 k ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ (1 : Matrix (Fin dE) (Fin dE) ℂ)) = (((∑ k, A 0 k) ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ (1 : Matrix (Fin dE) (Fin dE) ℂ)) := by ext i j simp [Matrix.sum_apply, Matrix.kroneckerMap_apply, Finset.sum_mul] rw [h2, (hA 0).2, Matrix.one_kronecker_one, Matrix.one_kronecker_one] rw [← Complex.re_sum, ← Matrix.trace_sum, ← Finset.sum_mul, h1, Matrix.one_mul, htr, Complex.one_re] rw [magic_square_key_guess_success, ← hsum] exact Finset.sum_le_sum fun k _ => key k
The achievable guessing probability set gset(w) is non-empty for w ≤ 1, bounded above by 1, and closed under convex mixtures
By guess_le_one, 1 bounds gset(w) from above. For any w ≤ 1, the perfect strategy (Ac, Bc, ρc) scoring 1 with the trivial deterministic POVM M₀ witnesses that gset(w) is non-empty. For p₁ ∈ gset(w₁) and p₂ ∈ gset(w₂), their direct-sum mixture achieves score at least a w₁ + b w₂ and guess probability a p₁ + b p₂, showing gset is closed under convex combinations.
uses
guess_le_one,perf_valid,score_one,mixρ_valid,mix_score,mix_guessdef gset (w : ℝ) : Set ℝ := {p : ℝ | ∃ (dA dB dE : ℕ) (A : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA) (Fin dA) ℂ) (B : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dB) (Fin dB) ℂ) (ρ : Matrix ((Fin dA × Fin dB) × Fin dE) ((Fin dA × Fin dB) × Fin dE) ℂ) (M : (Fin 3 → Bool) → Matrix (Fin dE) (Fin dE) ℂ), magic_square_strategy_valid A B ρ ∧ is_povm dE M ∧ w ≤ magic_square_score A B ρ ∧ p = magic_square_key_guess_success A ρ M} lemma g_eq (w : ℝ) : magic_square_guess_fn w = sSup (gset w) := rfl lemma gset_bdd (w : ℝ) : BddAbove (gset w) := by refine ⟨1, ?_⟩ rintro p ⟨dA, dB, dE, A, B, ρ, M, hv, hM, -, rfl⟩ exact guess_le_one hv hM noncomputable def M0 : (Fin 3 → Bool) → Matrix (Fin 1) (Fin 1) ℂ := fun k => if k = (fun _ => false) then 1 else 0 open scoped ComplexOrder in lemma M0_povm : is_povm 1 M0 := by refine ⟨fun k => ?_, ?_⟩ · unfold M0 split_ifs · exact Matrix.PosSemidef.one · exact Matrix.PosSemidef.zero · simp [M0] lemma gset_nonempty {w : ℝ} (hw : w ≤ 1) : (gset w).Nonempty := ⟨_, 4, 4, 1, Ac, Bc, ρc, M0, perf_valid, M0_povm, hw.trans score_one.ge, rfl⟩ lemma gset_mix {w1 w2 p1 p2 a b : ℝ} (ha : 0 ≤ a) (hb : 0 ≤ b) (hab : a + b = 1) (h1 : p1 ∈ gset w1) (h2 : p2 ∈ gset w2) : a * p1 + b * p2 ∈ gset (a * w1 + b * w2) := by obtain ⟨dA1, dB1, dE1, A1, B1, ρ1, M1, hv1, hM1, hs1, rfl⟩ := h1 obtain ⟨dA2, dB2, dE2, A2, B2, ρ2, M2, hv2, hM2, hs2, rfl⟩ := h2 refine ⟨dA1 + dA2, dB1 + dB2, dE1 + dE2, fun x s => blk (A1 x s) (A2 x s), fun j c => blk (B1 j c) (B2 j c), mixρ a b ρ1 ρ2, fun k => blk (M1 k) (M2 k), mixρ_valid a b ha hb hab hv1 hv2, blk_povm hM1 hM2, ?_, ?_⟩ · rw [mix_score] exact add_le_add (mul_le_mul_of_nonneg_left hs1 ha) (mul_le_mul_of_nonneg_left hs2 hb) · rw [mix_guess] end MagicSquareConcave
The adversary guessing function magic_square_guess_fn is concave on (-∞, 1]
The domain (-∞, 1] is convex (convex_Iic). For w₁, w₂ ≤ 1, a, b ≥ 0 with a + b = 1, and any ε > 0, since gset is non-empty there exist achievable points p₁ ∈ gset(w₁) and p₂ ∈ gset(w₂) within ε of the suprema g(w₁) and g(w₂). Their mixture a p₁ + b p₂ belongs to gset(a w₁ + b w₂), which implies g(a w₁ + b w₂) ≥ a p₁ + b p₂ > a g(w₁) + b g(w₂) - ε. Since ε > 0 is arbitrary, g(a w₁ + b w₂) ≥ a g(w₁) + b g(w₂), establishing concavity.
uses
convex_Iic,le_of_forall_pos_le_add,exists_lt_of_lt_csSup,sub_lt_self,le_csSuptheorem magic_square_guess_fn_concaveOn : ConcaveOn ℝ (Set.Iic 1) magic_square_guess_fn := by refine ⟨convex_Iic 1, fun w1 hw1 w2 hw2 a b ha hb hab => ?_⟩ simp only [smul_eq_mul, MagicSquareConcave.g_eq] apply le_of_forall_pos_le_add intro ε hε obtain ⟨p1, hp1, hlt1⟩ := exists_lt_of_lt_csSup (MagicSquareConcave.gset_nonempty hw1) (sub_lt_self (sSup (MagicSquareConcave.gset w1)) hε) obtain ⟨p2, hp2, hlt2⟩ := exists_lt_of_lt_csSup (MagicSquareConcave.gset_nonempty hw2) (sub_lt_self (sSup (MagicSquareConcave.gset w2)) hε) have hle := le_csSup (MagicSquareConcave.gset_bdd _) (MagicSquareConcave.gset_mix ha hb hab hp1 hp2) have e1 := mul_le_mul_of_nonneg_left hlt1.le ha have e2 := mul_le_mul_of_nonneg_left hlt2.le hb nlinarith
Fin.addCases- Case analysis on Fin (m + n): every index is either castAdd n i or natAdd m j
iff_false- An equivalence between a proposition and False is equivalent to the negation of the proposition
incL_mul_conj- The left block inclusion matrix times its conjugate transpose equals the identity matrix
incR_mul_conj- The right block inclusion matrix times its conjugate transpose equals the identity matrix
incL_mul_conjR- The left block inclusion matrix times the conjugate transpose of the right inclusion matrix is zero
incR_mul_conjL- The right block inclusion matrix times the conjugate transpose of the left inclusion matrix is zero
conj_inc_add- The sum of the conjugate transpose projections of the block inclusions is the full identity matrix
Matrix.trace_mul_comm- The trace of a product of two matrices is invariant under cyclic permutation
Matrix.conjTranspose_kronecker- The conjugate transpose of a Kronecker product is the Kronecker product of conjugate transposes
Matrix.mul_kronecker_mul- Kronecker product distributes over matrix multiplication: (A ⊗ B)(C ⊗ D) = (AC) ⊗ (BD)
Matrix.one_kronecker_one- The Kronecker product of identity matrices is the identity matrix
tr_kron_conj- Compressing a state by a tensor product of isometries equals compressing the observable by those isometries under the trace
compL_blk- Compressing a block-diagonal matrix by the left inclusion recovers the upper-left block
compR_blk- Compressing a block-diagonal matrix by the right inclusion recovers the lower-right block
blk_povm- The block sum of two POVMs is a valid POVM on the direct sum space
blk_zero- The block sum of two zero matrices is the zero matrix
iso_trace- Compressing a density matrix by a tensor product of co-isometries preserves its trace
magic_square_score- The expected score in the magic square game is the average winning probability over all nine question pairs
tr_mix- The trace of a block observable against a convex mixture state is the convex combination of the traces
magic_square_key_guess_success- The success probability of an adversary guessing Alice's complete first-row answer using measurement M
Matrix.posSemidef_self_mul_conjTranspose- For any matrix A, the product A * Aᴴ is positive semidefinite
Matrix.posSemidef_vecMulVec_self_star- The outer product of any vector with its conjugate transpose is positive semidefinite
win_sum- The unnormalized sum of winning correlations for the Mermin-Peres magic square game strategy equals 576
tr_psd_mul- The product of two positive semidefinite matrices has non-negative real trace
one_sub_povm- For any POVM element M(k), the operator 1 - M(k) is positive semidefinite
Matrix.posSemidef_sum- A finite sum of positive semidefinite matrices is positive semidefinite
guess_le_one- Eve's key guessing success probability in any valid magic square strategy is at most 1
perf_valid- The explicit Mermin-Peres strategy Ac, Bc, ρc is a valid quantum strategy
score_one- The explicit Mermin-Peres strategy achieves a score of 1 in the magic square game
mixρ_valid- The convex mixture of two valid strategies via block direct sum is a valid quantum strategy
mix_score- The score of a block direct-sum mixture strategy is the convex combination of the scores
mix_guess- The key guessing success probability of a block mixture strategy is the convex combination of guessing probabilities
convex_Iic- The interval (-∞, r] is convex in an ordered vector space
le_of_forall_pos_le_add- If a ≤ b + ε for every positive ε, then a ≤ b
exists_lt_of_lt_csSup- If a set is non-empty and b < sup s, there exists an element a ∈ s with b < a
sub_lt_self- Subtracting a positive number from a strictly decreases it
le_csSup- Any element of a set bounded above is at most the supremum of the set
- The verification that the Mermin-Peres magic square strategy achieves score 1 (lines 216–235) relies on kernel evaluation (`decide +kernel`), which checks matrix identities and counts winning question-answer pairs by finite reflection.
- The direct sum of Hilbert spaces is represented concretely through block inclusion matrices `incL` and `incR` into `Fin (n + m)`, requiring elementary matrix algebra lemmas for block composition.
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.
namespace MagicSquareConcaveopen Matrixopen scoped Kroneckeropen scoped ComplexOrder@[simp] lemma castAdd_eq_natAdd_iff {n m : ℕ} (i : Fin n) (j : Fin m) : Fin.castAdd m i = Fin.natAdd n j ↔ False := by simp only [Fin.ext_iff, Fin.val_castAdd, Fin.val_natAdd, iff_false]; omega@[simp] lemma natAdd_eq_castAdd_iff {n m : ℕ} (i : Fin n) (j : Fin m) : Fin.natAdd n j = Fin.castAdd m i ↔ False := by simp only [Fin.ext_iff, Fin.val_castAdd, Fin.val_natAdd, iff_false]; omega/-- inclusion of the first block -/def incL (n m : ℕ) : Matrix (Fin n) (Fin (n + m)) ℂ := Matrix.of fun i j => if j = Fin.castAdd m i then 1 else 0def incR (n m : ℕ) : Matrix (Fin m) (Fin (n + m)) ℂ := Matrix.of fun i j => if j = Fin.natAdd n i then 1 else 0lemma incL_mul_conj (n m : ℕ) : incL n m * (incL n m)ᴴ = 1 := by ext i i' simp [incL, Matrix.mul_apply, Matrix.conjTranspose_apply, Matrix.one_apply, eq_comm]lemma incR_mul_conj (n m : ℕ) : incR n m * (incR n m)ᴴ = 1 := by ext i i' simp [incR, Matrix.mul_apply, Matrix.conjTranspose_apply, Matrix.one_apply, eq_comm]lemma incL_mul_conjR (n m : ℕ) : incL n m * (incR n m)ᴴ = 0 := by ext i i' simp [incL, incR, Matrix.mul_apply, Matrix.conjTranspose_apply]lemma incR_mul_conjL (n m : ℕ) : incR n m * (incL n m)ᴴ = 0 := by ext i i' simp [incL, incR, Matrix.mul_apply, Matrix.conjTranspose_apply]lemma conj_inc_add (n m : ℕ) : (incL n m)ᴴ * incL n m + (incR n m)ᴴ * incR n m = 1 := by ext j j' refine Fin.addCases (fun i => ?_) (fun i => ?_) j <;> refine Fin.addCases (fun i' => ?_) (fun i' => ?_) j' <;> simp [incL, incR, Matrix.mul_apply, Matrix.conjTranspose_apply, Matrix.one_apply, eq_comm]/-- block-diagonal sum -/def blk {n m : ℕ} (X : Matrix (Fin n) (Fin n) ℂ) (Y : Matrix (Fin m) (Fin m) ℂ) : Matrix (Fin (n + m)) (Fin (n + m)) ℂ := (incL n m)ᴴ * X * incL n m + (incR n m)ᴴ * Y * incR n mlemma compL_blk {n m : ℕ} (X : Matrix (Fin n) (Fin n) ℂ) (Y : Matrix (Fin m) (Fin m) ℂ) : incL n m * blk X Y * (incL n m)ᴴ = X := by simp only [blk, Matrix.mul_add, Matrix.add_mul, ← Matrix.mul_assoc, incL_mul_conj, incL_mul_conjR, Matrix.one_mul, Matrix.zero_mul] simp [Matrix.mul_assoc, incL_mul_conj]lemma compR_blk {n m : ℕ} (X : Matrix (Fin n) (Fin n) ℂ) (Y : Matrix (Fin m) (Fin m) ℂ) : incR n m * blk X Y * (incR n m)ᴴ = Y := by simp only [blk, Matrix.mul_add, Matrix.add_mul, ← Matrix.mul_assoc, incR_mul_conj, incR_mul_conjL, Matrix.one_mul, Matrix.zero_mul] simp [Matrix.mul_assoc, incR_mul_conj]lemma blk_psd {n m : ℕ} {X : Matrix (Fin n) (Fin n) ℂ} {Y : Matrix (Fin m) (Fin m) ℂ} (hX : X.PosSemidef) (hY : Y.PosSemidef) : (blk X Y).PosSemidef := (hX.conjTranspose_mul_mul_same _).add (hY.conjTranspose_mul_mul_same _)lemma blk_zero (n m : ℕ) : blk (0 : Matrix (Fin n) (Fin n) ℂ) (0 : Matrix (Fin m) (Fin m) ℂ) = 0 := by simp [blk]lemma blk_one (n m : ℕ) : blk (1 : Matrix (Fin n) (Fin n) ℂ) (1 : Matrix (Fin m) (Fin m) ℂ) = 1 := by simp [blk, conj_inc_add]lemma blk_sum {n m : ℕ} {ι : Type} [Fintype ι] (X : ι → Matrix (Fin n) (Fin n) ℂ) (Y : ι → Matrix (Fin m) (Fin m) ℂ) : ∑ i, blk (X i) (Y i) = blk (∑ i, X i) (∑ i, Y i) := by simp [blk, Finset.sum_add_distrib, Matrix.sum_mul, Matrix.mul_sum]lemma blk_povm {n m : ℕ} {ι : Type} [Fintype ι] {X : ι → Matrix (Fin n) (Fin n) ℂ} {Y : ι → Matrix (Fin m) (Fin m) ℂ} (hX : is_povm n X) (hY : is_povm m Y) : is_povm (n + m) (fun i => blk (X i) (Y i)) := ⟨fun i => blk_psd (hX.1 i) (hY.1 i), by rw [blk_sum, hX.2, hY.2, blk_one]⟩/-- the trace-linear-form fact: compression through a Kronecker isometry -/lemma tr_kron_conj {a a' b b' e e' : ℕ} (VA : Matrix (Fin a) (Fin a') ℂ) (VB : Matrix (Fin b) (Fin b') ℂ) (VE : Matrix (Fin e) (Fin e') ℂ) (X : Matrix (Fin a') (Fin a') ℂ) (Y : Matrix (Fin b') (Fin b') ℂ) (Z : Matrix (Fin e') (Fin e') ℂ) (ρ : Matrix ((Fin a × Fin b) × Fin e) ((Fin a × Fin b) × Fin e) ℂ) : (((X ⊗ₖ Y) ⊗ₖ Z) * (((VAᴴ ⊗ₖ VBᴴ) ⊗ₖ VEᴴ) * ρ * ((VAᴴ ⊗ₖ VBᴴ) ⊗ₖ VEᴴ)ᴴ)).trace = ((((VA * X * VAᴴ) ⊗ₖ (VB * Y * VBᴴ)) ⊗ₖ (VE * Z * VEᴴ)) * ρ).trace := by rw [← Matrix.mul_assoc, ← Matrix.mul_assoc, Matrix.trace_mul_comm, ← Matrix.mul_assoc] congr 2 simp only [Matrix.conjTranspose_kronecker, Matrix.conjTranspose_conjTranspose, ← Matrix.mul_kronecker_mul, Matrix.mul_assoc]lemma compL_one (n m : ℕ) : incL n m * (1 : Matrix (Fin (n + m)) (Fin (n + m)) ℂ) * (incL n m)ᴴ = 1 := by rw [Matrix.mul_one, incL_mul_conj]lemma compR_one (n m : ℕ) : incR n m * (1 : Matrix (Fin (n + m)) (Fin (n + m)) ℂ) * (incR n m)ᴴ = 1 := by rw [Matrix.mul_one, incR_mul_conj]lemma iso_trace {a a' b b' e e' : ℕ} (VA : Matrix (Fin a') (Fin a) ℂ) (VB : Matrix (Fin b') (Fin b) ℂ) (VE : Matrix (Fin e') (Fin e) ℂ) (hA : VA * VAᴴ = 1) (hB : VB * VBᴴ = 1) (hE : VE * VEᴴ = 1) (ρ : Matrix ((Fin a' × Fin b') × Fin e') ((Fin a' × Fin b') × Fin e') ℂ) : (((VAᴴ ⊗ₖ VBᴴ) ⊗ₖ VEᴴ) * ρ * ((VAᴴ ⊗ₖ VBᴴ) ⊗ₖ VEᴴ)ᴴ).trace = ρ.trace := by rw [Matrix.trace_mul_comm, ← Matrix.mul_assoc] simp only [Matrix.conjTranspose_kronecker, Matrix.conjTranspose_conjTranspose, ← Matrix.mul_kronecker_mul, hA, hB, hE, Matrix.one_kronecker_one, Matrix.one_mul]section mixvariable {dA1 dB1 dE1 dA2 dB2 dE2 : ℕ}noncomputable def mixρ (a b : ℝ) (ρ1 : Matrix ((Fin dA1 × Fin dB1) × Fin dE1) ((Fin dA1 × Fin dB1) × Fin dE1) ℂ) (ρ2 : Matrix ((Fin dA2 × Fin dB2) × Fin dE2) ((Fin dA2 × Fin dB2) × Fin dE2) ℂ) : Matrix ((Fin (dA1 + dA2) × Fin (dB1 + dB2)) × Fin (dE1 + dE2)) ((Fin (dA1 + dA2) × Fin (dB1 + dB2)) × Fin (dE1 + dE2)) ℂ := (a : ℂ) • ((((incL dA1 dA2)ᴴ ⊗ₖ (incL dB1 dB2)ᴴ) ⊗ₖ (incL dE1 dE2)ᴴ) * ρ1 * (((incL dA1 dA2)ᴴ ⊗ₖ (incL dB1 dB2)ᴴ) ⊗ₖ (incL dE1 dE2)ᴴ)ᴴ) + (b : ℂ) • ((((incR dA1 dA2)ᴴ ⊗ₖ (incR dB1 dB2)ᴴ) ⊗ₖ (incR dE1 dE2)ᴴ) * ρ2 * (((incR dA1 dA2)ᴴ ⊗ₖ (incR dB1 dB2)ᴴ) ⊗ₖ (incR dE1 dE2)ᴴ)ᴴ)lemma tr_mix (a b : ℝ) (ρ1 : Matrix ((Fin dA1 × Fin dB1) × Fin dE1) ((Fin dA1 × Fin dB1) × Fin dE1) ℂ) (ρ2 : Matrix ((Fin dA2 × Fin dB2) × Fin dE2) ((Fin dA2 × Fin dB2) × Fin dE2) ℂ) (X1 : Matrix (Fin dA1) (Fin dA1) ℂ) (X2 : Matrix (Fin dA2) (Fin dA2) ℂ) (Y1 : Matrix (Fin dB1) (Fin dB1) ℂ) (Y2 : Matrix (Fin dB2) (Fin dB2) ℂ) (Z1 : Matrix (Fin dE1) (Fin dE1) ℂ) (Z2 : Matrix (Fin dE2) (Fin dE2) ℂ) : (((blk X1 X2 ⊗ₖ blk Y1 Y2) ⊗ₖ blk Z1 Z2) * mixρ a b ρ1 ρ2).trace.re = a * (((X1 ⊗ₖ Y1) ⊗ₖ Z1) * ρ1).trace.re + b * (((X2 ⊗ₖ Y2) ⊗ₖ Z2) * ρ2).trace.re := by rw [mixρ, Matrix.mul_add, Matrix.mul_smul, Matrix.mul_smul, Matrix.trace_add, Matrix.trace_smul, Matrix.trace_smul, tr_kron_conj, tr_kron_conj, compL_blk, compL_blk, compL_blk, compR_blk, compR_blk, compR_blk] simp [Complex.add_re]lemma blk_one' (n m : ℕ) : (1 : Matrix (Fin (n + m)) (Fin (n + m)) ℂ) = blk 1 1 := (blk_one n m).symmopen scoped ComplexOrder inlemma mixρ_valid (a b : ℝ) (ha : 0 ≤ a) (hb : 0 ≤ b) (hab : a + b = 1) {A1 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA1) (Fin dA1) ℂ} {B1 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dB1) (Fin dB1) ℂ} {ρ1 : Matrix ((Fin dA1 × Fin dB1) × Fin dE1) ((Fin dA1 × Fin dB1) × Fin dE1) ℂ} {A2 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA2) (Fin dA2) ℂ} {B2 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dB2) (Fin dB2) ℂ} {ρ2 : Matrix ((Fin dA2 × Fin dB2) × Fin dE2) ((Fin dA2 × Fin dB2) × Fin dE2) ℂ} (h1 : magic_square_strategy_valid A1 B1 ρ1) (h2 : magic_square_strategy_valid A2 B2 ρ2) : magic_square_strategy_valid (fun x s => blk (A1 x s) (A2 x s)) (fun j c => blk (B1 j c) (B2 j c)) (mixρ a b ρ1 ρ2) := by obtain ⟨hA1, hA1z, hB1, hB1z, hρ1, htr1⟩ := h1 obtain ⟨hA2, hA2z, hB2, hB2z, hρ2, htr2⟩ := h2 refine ⟨fun x => blk_povm (hA1 x) (hA2 x), fun x s hs => ?_, fun j => blk_povm (hB1 j) (hB2 j), fun j c hc => ?_, ?_, ?_⟩ · simp only [hA1z x s hs, hA2z x s hs, blk_zero] · simp only [hB1z j c hc, hB2z j c hc, blk_zero] · refine Matrix.PosSemidef.add ((hρ1.mul_mul_conjTranspose_same _).smul ?_) ((hρ2.mul_mul_conjTranspose_same _).smul ?_) · exact_mod_cast ha · exact_mod_cast hb · rw [mixρ, Matrix.trace_add, Matrix.trace_smul, Matrix.trace_smul, iso_trace _ _ _ (incL_mul_conj _ _) (incL_mul_conj _ _) (incL_mul_conj _ _), iso_trace _ _ _ (incR_mul_conj _ _) (incR_mul_conj _ _) (incR_mul_conj _ _), htr1, htr2] simp only [smul_eq_mul, mul_one] exact_mod_cast hablemma mix_score (a b : ℝ) (A1 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA1) (Fin dA1) ℂ) (B1 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dB1) (Fin dB1) ℂ) (ρ1 : Matrix ((Fin dA1 × Fin dB1) × Fin dE1) ((Fin dA1 × Fin dB1) × Fin dE1) ℂ) (A2 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA2) (Fin dA2) ℂ) (B2 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dB2) (Fin dB2) ℂ) (ρ2 : Matrix ((Fin dA2 × Fin dB2) × Fin dE2) ((Fin dA2 × Fin dB2) × Fin dE2) ℂ) : magic_square_score (fun x s => blk (A1 x s) (A2 x s)) (fun j c => blk (B1 j c) (B2 j c)) (mixρ a b ρ1 ρ2) = a * magic_square_score A1 B1 ρ1 + b * magic_square_score A2 B2 ρ2 := by simp only [magic_square_score, blk_one', tr_mix] simp only [Finset.mul_sum, ← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun x _ => Finset.sum_congr rfl fun j _ => Finset.sum_congr rfl fun s _ => Finset.sum_congr rfl fun c _ => ?_ split_ifs <;> ringlemma mix_guess (a b : ℝ) (A1 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA1) (Fin dA1) ℂ) (ρ1 : Matrix ((Fin dA1 × Fin dB1) × Fin dE1) ((Fin dA1 × Fin dB1) × Fin dE1) ℂ) (M1 : (Fin 3 → Bool) → Matrix (Fin dE1) (Fin dE1) ℂ) (A2 : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA2) (Fin dA2) ℂ) (ρ2 : Matrix ((Fin dA2 × Fin dB2) × Fin dE2) ((Fin dA2 × Fin dB2) × Fin dE2) ℂ) (M2 : (Fin 3 → Bool) → Matrix (Fin dE2) (Fin dE2) ℂ) : magic_square_key_guess_success (fun x s => blk (A1 x s) (A2 x s)) (mixρ a b ρ1 ρ2) (fun k => blk (M1 k) (M2 k)) = a * magic_square_key_guess_success A1 ρ1 M1 + b * magic_square_key_guess_success A2 ρ2 M2 := by simp only [magic_square_key_guess_success, blk_one', tr_mix] simp only [Finset.mul_sum, ← Finset.sum_add_distrib]end mixdef Obs : Fin 3 → Fin 3 → Matrix (Fin 4) (Fin 4) ℤ := ![![!![0, 0, 1, 0; 0, 0, 0, 1; 1, 0, 0, 0; 0, 1, 0, 0], !![0, 1, 0, 0; 1, 0, 0, 0; 0, 0, 0, 1; 0, 0, 1, 0], !![0, 0, 0, 1; 0, 0, 1, 0; 0, 1, 0, 0; 1, 0, 0, 0]], ![!![1, 0, 0, 0; 0, -1, 0, 0; 0, 0, 1, 0; 0, 0, 0, -1], !![1, 0, 0, 0; 0, 1, 0, 0; 0, 0, -1, 0; 0, 0, 0, -1], !![1, 0, 0, 0; 0, -1, 0, 0; 0, 0, -1, 0; 0, 0, 0, 1]], ![!![0, 0, -1, 0; 0, 0, 0, 1; -1, 0, 0, 0; 0, 1, 0, 0], !![0, -1, 0, 0; -1, 0, 0, 0; 0, 0, 0, 1; 0, 0, 1, 0], !![0, 0, 0, -1; 0, 0, 1, 0; 0, 1, 0, 0; -1, 0, 0, 0]]]def perf_sg (b : Bool) : ℤ := if b then -1 else 1def PA (x : Fin 3) (s : Fin 3 → Bool) : Matrix (Fin 4) (Fin 4) ℤ := if xor (xor (s 0) (s 1)) (s 2) = true then 0 else (1 + perf_sg (s 0) • Obs x 0) * (1 + perf_sg (s 1) • Obs x 1)def PB (j : Fin 3) (c : Fin 3 → Bool) : Matrix (Fin 4) (Fin 4) ℤ := if xor (xor (c 0) (c 1)) (c 2) = false then 0 else (1 + perf_sg (c 0) • Obs 0 j) * (1 + perf_sg (c 1) • Obs 1 j)set_option maxRecDepth 100000 intheorem PA_proj : ∀ x s, PA x s * PA x s = 4 • PA x s ∧ (PA x s).transpose = PA x s := by decide +kernelset_option maxRecDepth 100000 intheorem PB_proj : ∀ j c, PB j c * PB j c = 4 • PB j c ∧ (PB j c).transpose = PB j c := by decide +kernelset_option maxRecDepth 100000 intheorem PA_sum : ∀ x, ∑ s, PA x s = 4 • (1 : Matrix (Fin 4) (Fin 4) ℤ) := by decide +kernelset_option maxRecDepth 100000 intheorem PB_sum : ∀ j, ∑ c, PB j c = 4 • (1 : Matrix (Fin 4) (Fin 4) ℤ) := by decide +kernelset_option maxRecDepth 100000 intheorem win_sum : (∑ x : Fin 3, ∑ j : Fin 3, ∑ s : Fin 3 → Bool, ∑ c : Fin 3 → Bool, if s j = c x then ∑ a : Fin 4, ∑ a' : Fin 4, PA x s a a' * PB j c a a' else 0) = 576 := by decide +kernelopen Matrix innoncomputable def Ac (x : Fin 3) (s : Fin 3 → Bool) : Matrix (Fin 4) (Fin 4) ℂ := (1 / 4 : ℂ) • (Int.castRingHom ℂ).mapMatrix (PA x s)open Matrix innoncomputable def Bc (j : Fin 3) (c : Fin 3 → Bool) : Matrix (Fin 4) (Fin 4) ℂ := (1 / 4 : ℂ) • (Int.castRingHom ℂ).mapMatrix (PB j c)noncomputable def perf_psi : (Fin 4 × Fin 4) × Fin 1 → ℂ := fun i => if i.1.1 = i.1.2 then 1 / 2 else 0noncomputable def ρc : Matrix ((Fin 4 × Fin 4) × Fin 1) ((Fin 4 × Fin 4) × Fin 1) ℂ := Matrix.vecMulVec perf_psi (star perf_psi)open Matrix inopen scoped ComplexOrder inlemma psd_of_proj (P : Matrix (Fin 4) (Fin 4) ℤ) (h : P * P = 4 • P ∧ P.transpose = P) : ((1 / 4 : ℂ) • (Int.castRingHom ℂ).mapMatrix P).PosSemidef := by have hc : ((1 / 4 : ℂ) • (Int.castRingHom ℂ).mapMatrix P)ᴴ = (1 / 4 : ℂ) • (Int.castRingHom ℂ).mapMatrix P := by ext i j have := congrFun (congrFun h.2 i) j simp only [Matrix.transpose_apply] at this simp [Matrix.conjTranspose_apply, this] have hm : (1 / 4 : ℂ) • (Int.castRingHom ℂ).mapMatrix P = ((1 / 4 : ℂ) • (Int.castRingHom ℂ).mapMatrix P) * ((1 / 4 : ℂ) • (Int.castRingHom ℂ).mapMatrix P)ᴴ := by rw [hc, Matrix.smul_mul, Matrix.mul_smul, ← map_mul, h.1, map_nsmul, ← Nat.cast_smul_eq_nsmul ℂ, smul_smul, smul_smul] norm_num rw [hm] exact Matrix.posSemidef_self_mul_conjTranspose _lemma perf_tr_rho (X Y : Matrix (Fin 4) (Fin 4) ℂ) : (((X ⊗ₖ Y) ⊗ₖ (1 : Matrix (Fin 1) (Fin 1) ℂ)) * ρc).trace = (1 / 4) * ∑ a : Fin 4, ∑ a' : Fin 4, X a a' * Y a a' := by simp [Matrix.trace, Matrix.mul_apply, ρc, Matrix.vecMulVec_apply, perf_psi, Fintype.sum_prod_type, Matrix.kroneckerMap_apply, Fin.sum_univ_four, map_ofNat] ringopen scoped ComplexOrder inlemma perf_valid : magic_square_strategy_valid Ac Bc ρc := by refine ⟨fun x => ⟨fun s => psd_of_proj _ (PA_proj x s), ?_⟩, fun x s hs => ?_, fun j => ⟨fun c => psd_of_proj _ (PB_proj j c), ?_⟩, fun j c hc => ?_, ?_, ?_⟩ · simp only [Ac] rw [← Finset.smul_sum, ← map_sum, PA_sum, map_nsmul, map_one, ← Nat.cast_smul_eq_nsmul ℂ, smul_smul] norm_num · simp [Ac, PA, hs] · simp only [Bc] rw [← Finset.smul_sum, ← map_sum, PB_sum, map_nsmul, map_one, ← Nat.cast_smul_eq_nsmul ℂ, smul_smul] norm_num · simp [Bc, PB, hc] · exact Matrix.posSemidef_vecMulVec_self_star perf_psi · simp [ρc, Matrix.trace, Matrix.vecMulVec_apply, perf_psi, Fintype.sum_prod_type, map_ofNat] norm_numlemma perf_entry (x j : Fin 3) (s c : Fin 3 → Bool) : (((Ac x s ⊗ₖ Bc j c) ⊗ₖ (1 : Matrix (Fin 1) (Fin 1) ℂ)) * ρc).trace.re = 1 / 64 * ((∑ a : Fin 4, ∑ a' : Fin 4, PA x s a a' * PB j c a a' : ℤ) : ℝ) := by rw [perf_tr_rho] have : (1 / 4 : ℂ) * ∑ a : Fin 4, ∑ a' : Fin 4, Ac x s a a' * Bc j c a a' = ((1 / 64 * ((∑ a : Fin 4, ∑ a' : Fin 4, PA x s a a' * PB j c a a' : ℤ) : ℝ) : ℝ) : ℂ) := by simp only [Ac, Bc, Matrix.smul_apply, RingHom.mapMatrix_apply, Matrix.map_apply, eq_intCast, smul_eq_mul] push_cast simp only [Finset.mul_sum] refine Finset.sum_congr rfl fun a _ => Finset.sum_congr rfl fun a' _ => ?_ ring rw [this, Complex.ofReal_re]lemma score_one : magic_square_score Ac Bc ρc = 1 := by have h := congrArg (Int.cast : ℤ → ℝ) win_sum push_cast at h have : magic_square_score Ac Bc ρc = 1 / 576 * (∑ x : Fin 3, ∑ j : Fin 3, ∑ s : Fin 3 → Bool, ∑ c : Fin 3 → Bool, if s j = c x then ∑ a : Fin 4, ∑ a' : Fin 4, ((PA x s a a' : ℝ) * (PB j c a a' : ℝ)) else 0) := by rw [magic_square_score] simp only [perf_entry, Finset.mul_sum] refine Finset.sum_congr rfl fun x _ => Finset.sum_congr rfl fun j _ => Finset.sum_congr rfl fun s _ => Finset.sum_congr rfl fun c _ => ?_ split_ifs · push_cast; simp only [Finset.mul_sum] refine Finset.sum_congr rfl fun a _ => Finset.sum_congr rfl fun a' _ => ?_ ring · simp rw [this, h] norm_numopen scoped ComplexOrder MatrixOrder inlemma tr_psd_mul {n : Type} [Fintype n] [DecidableEq n] {P ρ : Matrix n n ℂ} (hP : P.PosSemidef) (hρ : ρ.PosSemidef) : 0 ≤ (P * ρ).trace.re := by obtain ⟨X, hX, -, rfl⟩ := CFC.exists_sqrt_of_isSelfAdjoint_of_quasispectrumRestricts hP.isHermitian (QuasispectrumRestricts.nnreal_of_nonneg hP.nonneg) rw [Matrix.mul_assoc, Matrix.trace_mul_comm, Matrix.mul_assoc, ← Matrix.mul_assoc] have h := hρ.mul_mul_conjTranspose_same X rw [← Matrix.star_eq_conjTranspose, hX.star_eq] at h exact (Complex.nonneg_iff.1 h.trace_nonneg).1open scoped ComplexOrder inlemma one_sub_povm {d : ℕ} {M : (Fin 3 → Bool) → Matrix (Fin d) (Fin d) ℂ} (hM : is_povm d M) (k : Fin 3 → Bool) : (1 - M k).PosSemidef := by have : 1 - M k = ∑ i ∈ Finset.univ.erase k, M i := by rw [← hM.2, ← Finset.add_sum_erase _ _ (Finset.mem_univ k)] abel rw [this] exact Matrix.posSemidef_sum _ fun i _ => hM.1 ilemma guess_le_one {dA dB dE : ℕ} {A : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA) (Fin dA) ℂ} {B : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dB) (Fin dB) ℂ} {ρ : Matrix ((Fin dA × Fin dB) × Fin dE) ((Fin dA × Fin dB) × Fin dE) ℂ} {M : (Fin 3 → Bool) → Matrix (Fin dE) (Fin dE) ℂ} (hv : magic_square_strategy_valid A B ρ) (hM : is_povm dE M) : magic_square_key_guess_success A ρ M ≤ 1 := by obtain ⟨hA, -, -, -, hρ, htr⟩ := hv have key : ∀ k, (((A 0 k ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ M k) * ρ).trace.re ≤ (((A 0 k ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ (1 : Matrix (Fin dE) (Fin dE) ℂ)) * ρ).trace.re := by intro k have h := tr_psd_mul (((hA 0).1 k).kronecker Matrix.PosSemidef.one |>.kronecker (one_sub_povm hM k)) hρ have hk : ((A 0 k ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ (1 - M k)) = ((A 0 k ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ 1) - ((A 0 k ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ M k) := by rw [eq_sub_iff_add_eq, ← Matrix.kronecker_add, sub_add_cancel] rw [hk, Matrix.sub_mul, Matrix.trace_sub, Complex.sub_re] at h linarith have hsum : ∑ k, (((A 0 k ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ (1 : Matrix (Fin dE) (Fin dE) ℂ)) * ρ).trace.re = 1 := by have h1 : ∑ k, ((A 0 k ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ (1 : Matrix (Fin dE) (Fin dE) ℂ)) = 1 := by have h2 : ∑ k, ((A 0 k ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ (1 : Matrix (Fin dE) (Fin dE) ℂ)) = (((∑ k, A 0 k) ⊗ₖ (1 : Matrix (Fin dB) (Fin dB) ℂ)) ⊗ₖ (1 : Matrix (Fin dE) (Fin dE) ℂ)) := by ext i j simp [Matrix.sum_apply, Matrix.kroneckerMap_apply, Finset.sum_mul] rw [h2, (hA 0).2, Matrix.one_kronecker_one, Matrix.one_kronecker_one] rw [← Complex.re_sum, ← Matrix.trace_sum, ← Finset.sum_mul, h1, Matrix.one_mul, htr, Complex.one_re] rw [magic_square_key_guess_success, ← hsum] exact Finset.sum_le_sum fun k _ => key kdef gset (w : ℝ) : Set ℝ := {p : ℝ | ∃ (dA dB dE : ℕ) (A : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA) (Fin dA) ℂ) (B : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dB) (Fin dB) ℂ) (ρ : Matrix ((Fin dA × Fin dB) × Fin dE) ((Fin dA × Fin dB) × Fin dE) ℂ) (M : (Fin 3 → Bool) → Matrix (Fin dE) (Fin dE) ℂ), magic_square_strategy_valid A B ρ ∧ is_povm dE M ∧ w ≤ magic_square_score A B ρ ∧ p = magic_square_key_guess_success A ρ M}lemma g_eq (w : ℝ) : magic_square_guess_fn w = sSup (gset w) := rfllemma gset_bdd (w : ℝ) : BddAbove (gset w) := by refine ⟨1, ?_⟩ rintro p ⟨dA, dB, dE, A, B, ρ, M, hv, hM, -, rfl⟩ exact guess_le_one hv hMnoncomputable def M0 : (Fin 3 → Bool) → Matrix (Fin 1) (Fin 1) ℂ := fun k => if k = (fun _ => false) then 1 else 0open scoped ComplexOrder inlemma M0_povm : is_povm 1 M0 := by refine ⟨fun k => ?_, ?_⟩ · unfold M0 split_ifs · exact Matrix.PosSemidef.one · exact Matrix.PosSemidef.zero · simp [M0]lemma gset_nonempty {w : ℝ} (hw : w ≤ 1) : (gset w).Nonempty := ⟨_, 4, 4, 1, Ac, Bc, ρc, M0, perf_valid, M0_povm, hw.trans score_one.ge, rfl⟩lemma gset_mix {w1 w2 p1 p2 a b : ℝ} (ha : 0 ≤ a) (hb : 0 ≤ b) (hab : a + b = 1) (h1 : p1 ∈ gset w1) (h2 : p2 ∈ gset w2) : a * p1 + b * p2 ∈ gset (a * w1 + b * w2) := by obtain ⟨dA1, dB1, dE1, A1, B1, ρ1, M1, hv1, hM1, hs1, rfl⟩ := h1 obtain ⟨dA2, dB2, dE2, A2, B2, ρ2, M2, hv2, hM2, hs2, rfl⟩ := h2 refine ⟨dA1 + dA2, dB1 + dB2, dE1 + dE2, fun x s => blk (A1 x s) (A2 x s), fun j c => blk (B1 j c) (B2 j c), mixρ a b ρ1 ρ2, fun k => blk (M1 k) (M2 k), mixρ_valid a b ha hb hab hv1 hv2, blk_povm hM1 hM2, ?_, ?_⟩ · rw [mix_score] exact add_le_add (mul_le_mul_of_nonneg_left hs1 ha) (mul_le_mul_of_nonneg_left hs2 hb) · rw [mix_guess]end MagicSquareConcavetheorem magic_square_guess_fn_concaveOn : ConcaveOn ℝ (Set.Iic 1) magic_square_guess_fn := by refine ⟨convex_Iic 1, fun w1 hw1 w2 hw2 a b ha hb hab => ?_⟩ simp only [smul_eq_mul, MagicSquareConcave.g_eq] apply le_of_forall_pos_le_add intro ε hε obtain ⟨p1, hp1, hlt1⟩ := exists_lt_of_lt_csSup (MagicSquareConcave.gset_nonempty hw1) (sub_lt_self (sSup (MagicSquareConcave.gset w1)) hε) obtain ⟨p2, hp2, hlt2⟩ := exists_lt_of_lt_csSup (MagicSquareConcave.gset_nonempty hw2) (sub_lt_self (sSup (MagicSquareConcave.gset w2)) hε) have hle := le_csSup (MagicSquareConcave.gset_bdd _) (MagicSquareConcave.gset_mix ha hb hab hp1 hp2) have e1 := mul_le_mul_of_nonneg_left hlt1.le ha have e2 := mul_le_mul_of_nonneg_left hlt2.le hb nlinarith