Lemma C.2 — properties of the threshold weight
OpenParityDegreeDepth.Main.Supplement.lemma_C_2Let . For a sign function , a margin-one sign witness is a real with for all , and is the least spectral norm of a witness. An affine subspace is written as with injective and linear, and . For , . For a polynomial of degree at most , the polar form is bilinear and its rank, the polar rank, is even.
- (Restriction.) Let be a sign function, any real function, injective linear and . If witnesses then witnesses , and . Moreover .
- (Products and derivatives.) If are sign functions and witnesses for , then witnesses and . For every sign function , every and every ,
- (Quadratic phases.) If , has polar rank and , then every margin-one sign witness for satisfies , and .
- (Nontriviality.) If and , then .
These four properties are exactly what the threshold-weight extension (Theorem 1.5) needs: restriction monotonicity lets every branch of the recursion use the original , the derivative bound and the quadratic identity convert into a bound on the binary contraction rank, and nontriviality makes the per-degree costs nonnegative.
Formalization Note Sign functions are real functions with values in ; degrees are degrees of the algebraic normal form; the polar rank is the rank of the matrix , encoded exactly as in the mission's Lemma 2.6.
Differences from the source:
- encoding: sign functions f, f₁, f₂ : 𝔽₂ⁿ → {−1,1} → real-valued functions with f x = −1 ∨ f x = 1 at every x; reason: the same functions
- encoding: W(f) defined as a minimum → the real infimum of the same set of spectral norms; reason: the minimum is attained (paper's remark after Definition C.1), so the values agree; for ±1-valued f the set is nonempty and bounded below
- encoding: every affine subspace H and f|H, g|H → every injective 𝔽₂-linear B : 𝔽₂ᵐ → 𝔽₂ⁿ (every m, m = 0 included) and shift a, with f ∘ (a + B·) and g ∘ (a + B·); reason: every affine subspace has such a parametrization, and the restricted functions are taken in its coordinates, as in the mission's Lemma 2.2
- encoding: D_{h₁}⋯D_{h_k} f → signDerivatives f h for h : Fin k → 𝔽₂ⁿ, every k ≥ 0, arbitrary (possibly zero or repeated) h_i; reason: the published iterated multiplicative derivative, same function
- encoding: degree at most 2 / exactly d, polar rank 2r → anfDegree p ≤ 2 / anfDegree p = d in WithBot ℕ, and rank of the polar-form matrix (contraction of topForm p 2 at the empty anchor tuple) = 2r; reason: the published Context's degree and the mission's Lemma 2.6 encoding of polar rank
import Mathlib import Definitions.Def_ParityDegreeDepth_Main_Context import Definitions.Def_ParityDegreeDepth_Main_Supplement_ThresholdWeight open scoped BigOperators noncomputable section
namespace ParityDegreeDepth.Main.Supplement
open ParityDegreeDepth.Main
/-- Zhang, STOC 2027 submission #798, Lemma C.2 (a)–(d), PDF p. 25 (printed p. 24).
SHA-256 02e6bad861054e233c6877aa352d0014cf84172cde536433dd6e24588277680b.
(a) affine restriction along every injective linear `B` and shift `a`;
(b) products of witnesses, and the derivative bound `W(D_{h₁}⋯D_{h_k} f) ≤ W(f)^(2^k)`;
(c) quadratic phases of polar rank `2r`: every witness has norm `≥ 2^r`, and `W = 2^r`;
(d) `W > 1` for phases of exact degree `d ≥ 2`. -/
theorem lemma_C_2 :
-- (a)
(∀ (n m : ℕ) (f g : Vec n (ZMod 2) → ℝ)
(B : Vec m (ZMod 2) →ₗ[ZMod 2] Vec n (ZMod 2)) (a : Vec n (ZMod 2)),
(∀ x, f x = -1 ∨ f x = 1) → Function.Injective B →
(IsSignWitness f g →
IsSignWitness (f ∘ affineMap B a) (g ∘ affineMap B a) ∧
spectralNorm (g ∘ affineMap B a) ≤ spectralNorm g) ∧
thresholdWeight (f ∘ affineMap B a) ≤ thresholdWeight f) ∧
-- (b)
(∀ (n : ℕ) (f₁ f₂ g₁ g₂ : Vec n (ZMod 2) → ℝ),
(∀ x, f₁ x = -1 ∨ f₁ x = 1) → (∀ x, f₂ x = -1 ∨ f₂ x = 1) →
IsSignWitness f₁ g₁ → IsSignWitness f₂ g₂ →
IsSignWitness (fun x => f₁ x * f₂ x) (fun x => g₁ x * g₂ x) ∧
spectralNorm (fun x => g₁ x * g₂ x) ≤ spectralNorm g₁ * spectralNorm g₂) ∧
(∀ (n k : ℕ) (f : Vec n (ZMod 2) → ℝ) (h : Fin k → Vec n (ZMod 2)),
(∀ x, f x = -1 ∨ f x = 1) →
thresholdWeight (signDerivatives f h) ≤ thresholdWeight f ^ (2 ^ k)) ∧
-- (c)
(∀ (n r : ℕ) (p : Vec n (ZMod 2) → ZMod 2),
anfDegree p ≤ (2 : WithBot ℕ) →
(contraction (topForm p 2) (fun i => Fin.elim0 i)).rank = 2 * r →
(∀ g, IsSignWitness (phase p) g → (2 : ℝ) ^ r ≤ spectralNorm g) ∧
thresholdWeight (phase p) = (2 : ℝ) ^ r) ∧
-- (d)
(∀ (n d : ℕ) (p : Vec n (ZMod 2) → ZMod 2),
2 ≤ d → anfDegree p = (d : WithBot ℕ) →
1 < thresholdWeight (phase p)) := by sorry
end ParityDegreeDepth.Main.Supplement