AFTD Auto-Formalizing Theoretical Domains

magic_square_guess_fn

def

magic_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 → Bool) → Matrix (Fin dA) (Fin dA) ℂ, B : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dB) (Fin dB) ℂ, a complex matrix ρ indexed by (Fin dA × Fin dB) × Fin dE, and M : (Fin 3 → Bool) → Matrix (Fin dE) (Fin dE) ℂ with magic_square_strategy_valid A B ρ, is_povm dE M, w ≤ magic_square_score A B ρ and p = magic_square_key_guess_success A ρ M. This is g(w): the supremum, over all finite-dimensional magic-square strategies with quantum side information whose score is at least w, of the adversary's guessing probability p_guess(K | E, x = 0) for Alice's complete first-row answer K (itself the supremum over the adversary's guessing POVMs).

Statement

noncomputable def magic_square_guess_fn (w : ℝ) : ℝ
Defined in
arXiv:2610.12001 (Exact value and rigidity of the 2x3 magic rectangle), Sec. 6, the function g(w) defined before Corollary 6.2.
Verified
02 Nov 2026
Axioms
none listed
Built on 4
  • 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…
  • 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_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…
  • 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…
Used by 2
  • magic_square_guess_fn_concaveOnThe function g = magic_square_guess_fn — g(w) is the supremum of the adversary's probability of guessing Alice's complete first-row answer…
  • 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 declaration defines a function magic_square_guess_fn : ℝ → ℝ that maps a target winning score w : ℝ to the real supremum (sSup) of all key-guessing probabilities p : ℝ achievable by Eve in a device-independent quantum Mermin–Peres magic square game. Specifically, for a given w : ℝ, magic_square_guess_fn w is the supremum of the set of all p : ℝ such that there exist: 1. Dimensions dA, dB, dE : ℕ, 2. Alice's measurement strategy A : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dA) (Fin dA) ℂ, 3. Bob's measurement strategy B : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dB) (Fin dB) ℂ, 4. A shared tripartite quantum state ρ : Matrix ((Fin dA × Fin dB) × Fin dE) ((Fin dA × Fin dB) × Fin dE) ℂ, and 5. Eve's measurement strategy M : (Fin 3 → Bool) → Matrix (Fin dE) (Fin dE) ℂ, satisfying: - magic_square_strategy_valid A B ρ: - For each row input x : Fin 3, A x is a POVM on Fin dA indexed by Fin 3 → Bool; - For each x and output assignment s : Fin 3 → Bool, if the parity xor (xor (s 0) (s 1)) (s 2) = true (odd parity), then A x s = 0 (Alice's outputs must have even parity); - For each column input j : Fin 3, B j is a POVM on Fin dB indexed by Fin 3 → Bool; - For each j and output assignment c : Fin 3 → Bool, if the parity xor (xor (c 0) (c 1)) (c 2) = false (even parity), then B j c = 0 (Bob's outputs must have odd parity); - ρ is positive semidefinite and has trace 1 (a valid density matrix); - is_povm dE M: M is a POVM on Fin dE indexed by Fin 3 → Bool (each M k is positive semidefinite and their sum over k is the identity matrix); - w ≤ magic_square_score A B ρ: the expected winning probability of strategy (A, B, ρ) in the magic square game is at least w; - p = magic_square_key_guess_success A ρ M: p equals Eve's probability of correctly guessing Alice's outcome for input x = 0 using POVM M.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- `g(w)` of arXiv:2610.12001, Sec. 6: the supremum of the adversary's guessing probability `p_guess(K | E, x = 0)` for Alice's first-row answer `K`, over all valid finite-dimensional magic-square strategies with score at least `w` and all of the adversary's guessing POVMs. -/
noncomputable def magic_square_guess_fn (w : ℝ) : ℝ :=
  sSup {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}
See it in the graphDiscuss this resultChallenge it