Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma C.2 — properties of the threshold weight

Open
ParityDegreeDepth.Main.Supplement.lemma_C_2

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

boolean-functionscomplexity-theoryfourier-analysisp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let Vn=F2nV_n=\mathbb F_2^nVn​=F2n​. For a sign function f:Vn→{−1,1}f:V_n\to\{-1,1\}f:Vn​→{−1,1}, a margin-one sign witness is a real ggg with f(x)g(x)≥1f(x)g(x)\ge1f(x)g(x)≥1 for all xxx, and W(f)W(f)W(f) is the least spectral norm ∥g^∥1\|\widehat g\|_1∥g​∥1​ of a witness. An affine subspace HHH is written as H={a+By:y∈F2m}H=\{a+By: y\in\mathbb F_2^m\}H={a+By:y∈F2m​} with B:F2m→F2nB:\mathbb F_2^m\to\mathbb F_2^nB:F2m​→F2n​ injective and linear, and f∣H(y)=f(a+By)f|_H(y)=f(a+By)f∣H​(y)=f(a+By). For h∈Vnh\in V_nh∈Vn​, Dhf(x)=f(x)f(x+h)D_hf(x)=f(x)f(x+h)Dh​f(x)=f(x)f(x+h). For a polynomial p:Vn→F2p:V_n\to\mathbb F_2p:Vn​→F2​ of degree at most 222, the polar form βp(u,v)=p(u+v)+p(u)+p(v)+p(0)\beta_p(u,v)=p(u+v)+p(u)+p(v)+p(0)βp​(u,v)=p(u+v)+p(u)+p(v)+p(0) is bilinear and its rank, the polar rank, is even.

  1. (Restriction.) Let fff be a sign function, ggg any real function, BBB injective linear and a∈Vna\in V_na∈Vn​. If ggg witnesses fff then g∣Hg|_Hg∣H​ witnesses f∣Hf|_Hf∣H​, and ∥g∣H^∥1≤∥g^∥1\|\widehat{g|_H}\|_1\le\|\widehat g\|_1∥g∣H​​∥1​≤∥g​∥1​. Moreover W(f∣H)≤W(f)W(f|_H)\le W(f)W(f∣H​)≤W(f).
  2. (Products and derivatives.) If f1,f2f_1,f_2f1​,f2​ are sign functions and gig_igi​ witnesses fif_ifi​ for i=1,2i=1,2i=1,2, then g1g2g_1g_2g1​g2​ witnesses f1f2f_1f_2f1​f2​ and ∥g1g2^∥1≤∥g1^∥1∥g2^∥1\|\widehat{g_1g_2}\|_1\le\|\widehat{g_1}\|_1\|\widehat{g_2}\|_1∥g1​g2​​∥1​≤∥g1​​∥1​∥g2​​∥1​. For every sign function fff, every k≥0k\ge0k≥0 and every h1,…,hk∈Vnh_1,\dots,h_k\in V_nh1​,…,hk​∈Vn​,
W(Dh1⋯Dhkf)≤W(f)2k.W(D_{h_1}\cdots D_{h_k}f)\le W(f)^{2^k}.W(Dh1​​⋯Dhk​​f)≤W(f)2k.
  1. (Quadratic phases.) If deg⁡p≤2\deg p\le 2degp≤2, ppp has polar rank 2r2r2r and f=(−1)pf=(-1)^pf=(−1)p, then every margin-one sign witness ggg for fff satisfies ∥g^∥1≥2r\|\widehat g\|_1\ge 2^r∥g​∥1​≥2r, and W(f)=2rW(f)=2^rW(f)=2r.
  2. (Nontriviality.) If deg⁡p=d≥2\deg p=d\ge2degp=d≥2 and f=(−1)pf=(-1)^pf=(−1)p, then W(f)>1W(f)>1W(f)>1.

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 W(f)W(f)W(f), the derivative bound and the quadratic identity convert WWW 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 {−1,1}\{-1,1\}{−1,1}; degrees are degrees of the algebraic normal form; the polar rank is the rank of the matrix (βp(ei,ej))i,j\bigl(\beta_p(e_i,e_j)\bigr)_{i,j}(βp​(ei​,ej​))i,j​, 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
Preamble
import Mathlib
import Definitions.Def_ParityDegreeDepth_Main_Context
import Definitions.Def_ParityDegreeDepth_Main_Supplement_ThresholdWeight

open scoped BigOperators
noncomputable section
Formal statement
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
Source
Shengyu Zhang, STOC 2027 submission #798 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/798.pdf, SHA-256 02e6bad861054e233c6877aa352d0014cf84172cde536433dd6e24588277680b, Lemma C.2 (a)–(d), PDF p. 25 (printed p. 24); Definition C.1 same page; Eq. (5) PDF p. 5 (printed p. 4); polar rank PDF p. 6 (printed p. 5).

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