Theorem 7.2 — every factor has an affine layered ABP of length , width , with a polynomial-length succinct description and polynomial-time edge queries
OpenNCFactorClosure607.Circuits.Supplement.local_representation_of_factoralgebraic-branching-programsalgebraic-complexityfinite-fieldsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1turing-machines
Let be an explicitly represented finite field. There are one deterministic multi-tape Turing machine and one polynomial bound such that the following holds. Suppose a circuit of size over computes a nonzero polynomial of degree at most in variables, and let be any factor of ( with ). Then there is an affine layered ABP with
- length exactly and one source and one sink,
- width at most ,
- value ,
and a succinct description of (its layer sizes and an auxiliary string) of length at most with , such that on every edge query — vertex of layer , vertex of layer — the machine , given the description, halts within steps with the encoded label of that edge.
The ABP itself may have exponential width; the theorem gives a deterministic polynomial-time local evaluator for it.
Differences from the source:
- encoding: an explicitly represented finite field F_q = F_p[t]/(φ(t)) with φ irreducible, supplied in a valid encoding → AdjoinRoot φ for φ : (ZMod p)[X] monic and irreducible, p prime; elements encoded by the binary coefficients of their representative of degree < deg φ; reason: the representation of §2.1; monicity normalizes φ and changes no field
- generalization: m ≥ 1 variables (§2) → any m : ℕ, including m = 0; reason: the statement for every m specializes to every m ≥ 1
- encoding: polynomial length in s, D, m, log q; edge labels computable in deterministic polynomial time in these parameters → one fixed Cook–Levin multi-tape machine M and one bound c(N+1)^e, N = s + D + m + ⌊log₂ q⌋, both quantified before the field, the circuit and the factor; M halts within the bound on every in-range query; reason: class membership with a uniform evaluator
- encoding: a description that gives the layer sizes → a bit string with the layer sizes in binary followed by an auxiliary string; queries (i, j, k) in binary; labels output as the encodings of their m + 1 coefficients; reason: the succinct-description convention of §7
- encoding: every factor → every P with f = a P b, a, b ≠ 0; reason: the definition of factor on p.5
Preamble
import Mathlib import Definitions.Def_NCFactorClosure607_Circuits_Supplement_ABP
Formal statement
namespace NCFactorClosure607.Circuits.Supplement
open NCFactorClosure607.Circuits Polynomial
/-- Theorem 7.2 (Local representation of a factor), p.17. There are one deterministic multi-tape
Turing machine `M` (the edge-label evaluator) and one polynomial bound `c (N + 1)^e` such that the
following holds. Let `F_q = F_p[t]/(φ)` be an explicitly represented finite field, and let a
circuit `C` of size `s` over `F_q` in `m` variables compute a nonzero `f` of degree at most `D`.
Then every factor `P` of `f` (`f = a P b` with `a, b ≠ 0`) is computed by an affine layered ABP of
length `D + 1` and width at most `Σ_{j=0}^{D} m^j` that has a succinct description (its layer
sizes and an auxiliary string) of length at most the bound at `N = s + D + m + log₂ q`, and on
every edge query `(i, j, k)` the machine `M`, given the description, halts within that many steps
with the encoded edge label. -/
theorem local_representation_of_factor :
∃ (M : CookLevin.Machine) (kT G c e : ℕ), CookLevin.TuringMachine kT G M ∧
∀ (p : ℕ) [Fact p.Prime] (φ : (ZMod p)[X]) [Fact (Irreducible φ)] (hφ : φ.Monic) (m : ℕ)
(C : Circuit (AdjoinRoot φ) (Fin m)) (D : ℕ),
C.WellFormed → C.eval ≠ 0 → DegLE C.eval D →
∀ a P b : FreeAlgebra (AdjoinRoot φ) (Fin m), C.eval = a * P * b → a ≠ 0 → b ≠ 0 →
∃ (A : LayeredABP (AdjoinRoot φ) m) (aux : List Bool),
A.WellFormed ∧ A.len = D + 1 ∧
A.width ≤ ∑ j ∈ Finset.range (D + 1), m ^ j ∧ A.eval = P ∧
(descriptionString A.layerSizes aux).length ≤
CookLevin.polyBound c e (C.size + D + m + Nat.log 2 (fieldCard p φ)) ∧
∀ (k : Fin A.len) (i : Fin (A.layer k.castSucc)) (j : Fin (A.layer k.succ)),
HaltsWithOutput M kT (edgeQuery A.layerSizes aux i.val j.val (k.val + 1))
(CookLevin.polyBound c e (C.size + D + m + Nat.log 2 (fieldCard p φ)))
(encLabel hφ (A.label k i j)) := by sorry
end NCFactorClosure607.Circuits.Supplement
Source
V. Arvind, Pushkar S Joglekar, Factor Closure in Noncommutative Algebraic Complexity, STOC 2027 submission #607 (October 2026), p.17, Theorem 7.2 and its proof (pp.17–18); §7 opening, p.17; §2.1, p.6; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/607.pdf