AFTD Auto-Formalizing Theoretical Domains

magic_square_guess_fn_concaveOn

theoremverifiedoriginal

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
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₂).

  1. 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.

    lines 6–43

    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]
    
  2. 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.

    lines 44–79

    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]⟩
    
  3. 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).

    lines 80–107

    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]
    
  4. 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.

    lines 108–162

    uses tr_kron_conj, compL_blk, compR_blk, blk_povm, blk_zero, iso_trace

    section 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
    
  5. 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.

    lines 163–191

    uses magic_square_score, tr_mix, magic_square_key_guess_success

    lemma 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
  6. 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.

    lines 192–235

    
    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
    
  7. 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.

    lines 236–321

    uses Matrix.posSemidef_self_mul_conjTranspose, Matrix.posSemidef_vecMulVec_self_star, win_sum

    open 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
    
  8. 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.

    lines 322–369

    uses tr_psd_mul, one_sub_povm, Matrix.posSemidef_sum

    open 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
    
  9. 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.

    lines 370–411

    uses guess_le_one, perf_valid, score_one, mixρ_valid, mix_score, mix_guess

    def 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
  10. 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.

    lines 412–425

    uses convex_Iic, le_of_forall_pos_le_add, exists_lt_of_lt_csSup, sub_lt_self, le_csSup

    theorem 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

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

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
See it in the graphDiscuss this resultChallenge it