Spectral adversary ratio and value
DefinitionTarskiBootstrap_Dimensional_Supplement_SpectralAdversaryLet be a function on a set of query strings, with and finite; the oracle of an input is the string itself, and exactly when (Definition 2.5). For a real matrix indexed by , its adversary ratio is
where is the spectral (Euclidean operator) norm and the entrywise product. The spectral adversary value is
with when no nonzero nonnegative adversary matrix exists, i.e. when is constant on .
This is equation (2.8). For a nonzero nonnegative adversary matrix the denominator is positive and the ratio is at most , 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 (it never occurs for nonzero adversary matrices of string inputs). The supremum is a real sSup, which is on the empty set, matching the convention for constant . Only the values of on enter.
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