Theorem A.2 — one-factor gain for an arbitrary -admissible target space
ProvedAC02Frege.Supplement.theorem_A_2ac0-2-fregemajority-liftingp2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-calculusproof-complexityres-pc
Let be a -admissible subspace of the multilinear polynomials over in variables, . Fix a line with multilinear of degree at most , and a current approximator , each (products multilinearized). Suppose
Then there is such that, with and ,
equivalently, .
Here and . Appending one well-chosen affine factor to the approximator removes at least half of the error conditions counted at degree . The case is Pang's Lemma 3.10, and with is the toy model of Appendix A.1.
Differences from the source:
- encoding: V = V_n, functions on the cube identified with multilinear polynomials; the line's polynomials u_i ∈ V_n with deg u_i ≤ r → u_i : MvPolynomial (Fin n) (ZMod 2), multilinear, totalDegree ≤ r; s arbitrary; reason: same instances
- encoding: D ∈ ℕ ∪ {∞}; C an F₂-subspace of V_n → D : ℕ∞; C a Submodule of multilinear polynomials with IsAdmissible D C; reason: same instances
- encoding: P = ∏ν q_ν, q_ν = 1 + Σ_i a{νi} u_i, products multilinearized; P′ = Pq; deg P → P = ML(∏_{ν<t} q_ν) for any t ≥ 0 and a : Fin t → Fin s → ZMod 2; P′ = ML(P · q); deg P = totalDegree of the multilinear P; reason: same instances
- encoding: c_P′(K) ≤ c_P(K) − ½ c_P(K − r); equivalently dim Z_P′(K) ≥ dim Z_P(K) + ½ c_P(K − r) → both inequalities, for the same ε, in ℝ; c_P(j) = monoCount n j − finrank(span Z_P(j)); K − r natural subtraction with K ≥ r; reason: same statement
Preamble
import Mathlib import Definitions.Def_AC02Frege_ML import Definitions.Def_AC02Frege_rankCounts import Definitions.Def_AC02Frege_Supplement_admissible
Formal statement
namespace AC02Frege.Supplement
open MvPolynomial
/-- Alekseev–Gryaznov–Pitassi–Robere–Shekhovtsov–Tzameret, *Progress on AC0[2]-Frege Lower
Bounds*, manuscript (sha256 88d149fa…), Theorem A.2, p.36 (one-factor gain, general form; proof
p.42). Fix a `D`-admissible `C`, a line `L = ⋁_{i=1}^s (u_i = 1)` with `deg u_i ≤ r`, and a
current approximator `P = ∏_ν q_ν`, each `q_ν = 1 + Σ_i a_{ν,i} u_i`. Suppose `K ≥ r` and
`deg P + K + 2r ≤ D` (46). Then there is `ε ∈ 𝔽₂^s` such that, with `q = 1 + Σ_i ε_i u_i` and
`P′ = Pq`, `c_{P′}(K) ≤ c_P(K) − ½ c_P(K − r)`; equivalently
`dim Z_{P′}(K) ≥ dim Z_P(K) + ½ c_P(K − r)`.
**Formalization Note** Polynomials are in `n` variables `Fin n`; the `u_i` are multilinear
(elements of `V_n`) of total degree at most `r`, and `s` is arbitrary. `P = ML(∏_{ν<t} q_ν)` for
any number `t ≥ 0` of factors, and `P′ = ML(P q)`; `deg P` is the total degree of the multilinear
`P`. `D ∈ ℕ ∪ {∞}` is `ℕ∞`. Both forms of the conclusion are stated, for the same `ε`, as real
inequalities (`½` is real). `K − r` is natural subtraction, harmless since `K ≥ r`. -/
theorem theorem_A_2 {n s t : ℕ} (D : ℕ∞) (C : Submodule (ZMod 2) (MvPolynomial (Fin n) (ZMod 2)))
(hC : IsAdmissible D C) (r K : ℕ) (u : Fin s → MvPolynomial (Fin n) (ZMod 2))
(hu : ∀ i, IsMultilinear (u i) ∧ (u i).totalDegree ≤ r)
(a : Fin t → Fin s → ZMod 2) (hKr : r ≤ K)
(hdeg : (((approxProd u a).totalDegree + K + 2 * r : ℕ) : ℕ∞) ≤ D) :
∃ ε : Fin s → ZMod 2,
((cErrC C u (ML (approxProd u a * (1 + ∑ i, ε i • u i))) K : ℕ) : ℝ) ≤
(cErrC C u (approxProd u a) K : ℝ) - (cErrC C u (approxProd u a) (K - r) : ℝ) / 2 ∧
(AC02Frege.dimSpan (ZsolC C u (approxProd u a) K) : ℝ) +
(cErrC C u (approxProd u a) (K - r) : ℝ) / 2 ≤
(AC02Frege.dimSpan (ZsolC C u (ML (approxProd u a * (1 + ∑ i, ε i • u i))) K) : ℝ) := by sorry
end AC02Frege.Supplement
Source
Alekseev, Gryaznov, Pitassi, Robere, Shekhovtsov, Tzameret, Progress on AC0[2]-Frege Lower Bounds (manuscript dated November 3, 2026, STOC 2027 submission, sha256 88d149fa2bcae702e55a6b72efecda2b4137fd18dca3e23a056c3db5da0ece61), Theorem A.2, p.36 (proof p.42); Definition A.1, p.35