Theorem A.5 — Pang's matrix lemma
ProvedAC02Frege.theorem_A_5_pang_matrix_lemmaac0-2-fregemajority-liftingp2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-calculusproof-complexity
Let be matrices over of the same shape, and let be the rank of the stacked map . Let be the field of rational functions in formal variables, and regard
as matrices over . Suppose
Then , and . In particular some has .
This is the algebraic core of the one-factor gain: a random -combination of the error matrices keeps half of their joint rank.
Differences from the source:
- encoding: E = F2(λ_1, …, λ_s); the expectation over ϵ ∈ F2^s → FractionRing (MvPolynomial (Fin s) (ZMod 2)) with λ_i the image of X i; the average of Matrix.rank over all 2^s points; reason: same field and same average
- encoding: the stacked map v ↦ (M_1 v, …, M_s v) → the matrix with rows indexed by Fin s × Fin p; reason: same linear map
Preamble
import Mathlib
Formal statement
namespace AC02Frege
open MvPolynomial Matrix
/-- Alekseev–Gryaznov–Pitassi–Robere–Shekhovtsov–Tzameret, *Progress on AC0[2]-Frege Lower Bounds*, manuscript (sha256 88d149fa…), Theorem A.5, (48), p.39 (Pang's matrix lemma [Pan26, Lemma 3.3]): let `M_1, …, M_s` be
matrices over `𝔽₂` of the same shape, let `c` be the rank of the stacked map
`v ↦ (M_1 v, …, M_s v)`, and suppose `ker_E M(λ) ⊆ ker_E M(λ²)` over
`E = 𝔽₂(λ_1, …, λ_s)`, where `M(λ) = Σ λ_i M_i` and `M(λ²) = Σ λ_i² M_i`. Then
`rank_E M(λ) = c` and `E_{ϵ ∈ 𝔽₂^s} rank_{𝔽₂} M(ϵ) ≥ c/2`; in particular some `ϵ` has
`rank M(ϵ) ≥ c/2`.
**Formalization Note** `E` is `FractionRing (MvPolynomial (Fin s) (ZMod 2))`, `λ_i` the image of
`X i`; the stacked map is the matrix with rows indexed by `Fin s × Fin p`; the expectation is
the average over all `2^s` points `ϵ : Fin s → ZMod 2`. -/
theorem theorem_A_5_pang_matrix_lemma {s p q : ℕ} (M : Fin s → Matrix (Fin p) (Fin q) (ZMod 2)) :
let E := FractionRing (MvPolynomial (Fin s) (ZMod 2))
let lam : Fin s → E := fun i => algebraMap (MvPolynomial (Fin s) (ZMod 2)) E (X i)
let Mlam : Matrix (Fin p) (Fin q) E := ∑ i, lam i • (M i).map (algebraMap (ZMod 2) E)
let Mlam2 : Matrix (Fin p) (Fin q) E := ∑ i, (lam i) ^ 2 • (M i).map (algebraMap (ZMod 2) E)
let c : ℕ := (Matrix.of (fun (ik : Fin s × Fin p) (j : Fin q) => M ik.1 ik.2 j)).rank
(∀ v : Fin q → E, Mlam *ᵥ v = 0 → Mlam2 *ᵥ v = 0) →
Mlam.rank = c ∧
(c : ℝ) / 2 ≤ (∑ ε : Fin s → ZMod 2, ((∑ i, ε i • M i).rank : ℝ)) / 2 ^ s ∧
∃ ε : Fin s → ZMod 2, (c : ℝ) / 2 ≤ ((∑ i, ε i • M i).rank : ℝ) := by sorry
end AC02Frege
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.5, (48), p.39
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.