Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Spectral adversary ratio and value SA(Φ)\mathrm{SA}(\Phi)SA(Φ)

Definition
TarskiBootstrap_Dimensional_Supplement_SpectralAdversary

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

adversary-methodp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-query-complexitytarski-fixed-points

Let Φ\PhiΦ be a function on a set S⊆ΣIS\subseteq\Sigma^IS⊆ΣI of query strings, with III and Σ\SigmaΣ finite; the oracle of an input x∈Sx\in Sx∈S is the string xxx itself, and Δi[x,y]=1\Delta_i[x,y]=1Δi​[x,y]=1 exactly when xi≠yix_i\ne y_ixi​=yi​ (Definition 2.5). For a real matrix Γ\GammaΓ indexed by SSS, its adversary ratio is

∥Γ∥max⁡i∈I∥Γ∘Δi∥,\frac{\|\Gamma\|}{\max_{i\in I}\|\Gamma\circ\Delta_i\|},maxi∈I​∥Γ∘Δi​∥∥Γ∥​,

where ∥⋅∥\|\cdot\|∥⋅∥ is the spectral (Euclidean operator) norm and ∘\circ∘ the entrywise product. The spectral adversary value is

SA(Φ)=sup⁡{∥Γ∥max⁡i∈I∥Γ∘Δi∥  :  Γ≠0 a nonnegative adversary matrix for Φ∣S},\mathrm{SA}(\Phi)=\sup\Bigl\{\frac{\|\Gamma\|}{\max_{i\in I}\|\Gamma\circ\Delta_i\|}\;:\;\Gamma\ne0\text{ a nonnegative adversary matrix for }\Phi|_S\Bigr\},SA(Φ)=sup{maxi∈I​∥Γ∘Δi​∥∥Γ∥​:Γ=0 a nonnegative adversary matrix for Φ∣S​},

with SA(Φ)=0\mathrm{SA}(\Phi)=0SA(Φ)=0 when no nonzero nonnegative adversary matrix exists, i.e. when Φ\PhiΦ is constant on SSS.

This is equation (2.8). For a nonzero nonnegative adversary matrix the denominator is positive and the ratio is at most ∣I∣|I|∣I∣, and the supremum is attained, so the supremum coincides with the maximum of (2.8).

Formalization Note The ratio is stated for an arbitrary oracle; a zero denominator yields the Lean value 000 (it never occurs for nonzero adversary matrices of string inputs). The supremum is a real sSup, which is 000 on the empty set, matching the convention for constant Φ\PhiΦ. Only the values of Φ\PhiΦ on SSS enter.

Definition code
import Definitions.Def_TarskiBootstrap_Dimensional_Adversary
import Definitions.Def_TarskiBootstrap_Dimensional_QueryMask

open scoped Matrix

namespace TarskiBootstrap.Dimensional.Supplement

/-- The adversary ratio `‖Γ‖ / max_i ‖Γ ∘ Δ_i‖` of (2.8), PDF/printed p. 7, with
real Euclidean (spectral) operator norms and the distinguisher matrices `Δ_i` of
Definition 2.5 for the given oracle. The maximum over the finite query set is a real
`⨆`; a zero denominator gives the Lean value `0`. -/
noncomputable def adversaryRatio {S Q O : Type*} [Fintype S]
    (oracle : S → Q → O) (Γ : Matrix S S ℝ) : ℝ := by
  classical
  exact ‖Matrix.toEuclideanCLM (𝕜 := ℝ) Γ‖ /
    ⨆ x : Q, ‖Matrix.toEuclideanCLM (𝕜 := ℝ) (Γ ⊙ queryMask oracle x)‖

/-- The spectral adversary value `SA(Φ)` of (2.8), PDF/printed p. 7, for a function
`Φ` on a set `S ⊆ Σ^I` of query strings (`I`, `Σ` finite): the supremum, over all
nonzero nonnegative adversary matrices `Γ` for `Φ|S` (Definition 2.4), of
`‖Γ‖ / max_{i ∈ I} ‖Γ ∘ Δ_i‖`. The oracle of an input is the string itself.
If no nonzero nonnegative adversary matrix exists (`Φ` constant on `S`), the set is
empty and the value is `sSup ∅ = 0`, the convention of p. 7. Only the values of `Φ`
on `S` matter. -/
noncomputable def spectralAdversary {I Sig Out : Type*} [Finite I] [Finite Sig]
    (S : Set (I → Sig)) (Φ : (I → Sig) → Out) : ℝ := by
  classical
  haveI : Fintype S := Fintype.ofFinite S
  exact sSup {r : ℝ | ∃ Γ : Matrix S S ℝ, Γ ≠ 0 ∧
    NonnegativeAdversary (fun x : S => Φ x.val) Γ ∧
    r = adversaryRatio (fun x : S => x.val) Γ}

end TarskiBootstrap.Dimensional.Supplement
Source
Li, Ma, Yang and Zhao, Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points, STOC 2027 submission #6 (2026), frozen preprint, equation (2.8) and Definitions 2.4–2.5, PDF/printed p. 7, SHA-256 320afa8333f95589a388b30ffbfd6d7b7e5d93cdf07fa8630825fbf7d0107d59; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/6.pdf. Printed page = PDF page. No arXiv identifier/version supplied.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me