Margin-one sign witnesses and the threshold weight
DefinitionParityDegreeDepth_Main_Supplement_ThresholdWeightLet and let be a sign function. A real function is a margin-one sign witness for when
The witness is an arbitrary real function: it need not be sign-valued, integer-valued or of low degree. The threshold weight of is the least spectral norm of a witness,
where is the sum of the absolute normalized Walsh coefficients , as in the mission's published operational context.
Taking shows , so the threshold weight refines the spectral norm in the depth bounds of the mission.
Formalization Note is the real infimum (sInf) of the set of spectral norms of witnesses. For a -valued this set is nonempty and bounded below by ; the paper remarks that the minimum is attained, but attainment is not built into the definition. Functions are real-valued, so a function with no witness (one vanishing somewhere) gets the default value ; every statement that uses assumes is -valued.
import Mathlib
import Definitions.Def_ParityDegreeDepth_Main_Context
open scoped BigOperators
noncomputable section
namespace ParityDegreeDepth.Main.Supplement
open ParityDegreeDepth.Main
/-- Zhang, STOC 2027 submission #798, Definition C.1 (PDF p. 25, printed p. 24):
`g` is a margin-one sign witness for `f` when `f x * g x ≥ 1` at every point.
The witness `g` is an arbitrary real function. -/
def IsSignWitness {n : ℕ} (f g : Vec n (ZMod 2) → ℝ) : Prop :=
∀ x, 1 ≤ f x * g x
/-- Threshold weight `W(f)` (Definition C.1; also PDF p. 4, printed p. 3): the infimum of the
spectral norm `‖ĝ‖₁` over all real margin-one sign witnesses `g` of `f`.
For a `±1`-valued `f` the set is nonempty (`g = f`) and bounded below by `0`; attainment of the
minimum is a remark of the paper and is not built into the definition. For an `f` with no
witness (e.g. `f x = 0` somewhere) Lean's `sInf ∅ = 0`; every statement using `W` assumes
`f` is `±1`-valued. -/
def thresholdWeight {n : ℕ} (f : Vec n (ZMod 2) → ℝ) : ℝ :=
sInf {w : ℝ | ∃ g : Vec n (ZMod 2) → ℝ, IsSignWitness f g ∧ spectralNorm g = w}
end ParityDegreeDepth.Main.Supplement