Lemma 7.1 — one coefficient in field operations, the empty-word coefficient in
OpenNCFactorClosure607.Circuits.Supplement.computing_one_coefficientalgorithmsarithmetic-circuitsnoncommutative-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a field, a set of variables, a circuit and a word of length . There is an absolute constant such that the algorithm returns the coefficient of in the polynomial computed by , and
- if , it performs at most field operations;
- if , it performs at most field operations.
No degree bound on intermediate gates is assumed. The lemma supplies the edge labels of Theorem 7.2 and the coefficient tests of the factorization algorithms.
Differences from the source:
- generalization: X = {x_1, …, x_m} with m ≥ 1 → an arbitrary type X with decidable equality; reason: decidable equality is needed to compare letters; every finite variable set has it
- encoding: the coefficient can be computed in O(size(C)d³) field operations → the explicit algorithm coeffAlgo stores every computed interval coefficient once and returns [w]C with at most K·size(C)·d³ counted field operations; reason: the operation count of the proof’s dynamic program, with later lookups reusing stored values
- encoding: O(size(C)d³) and O(size(C)) → one absolute natural constant K quantified before the field, the variable type, the input and the factors; reason: the O(·) of the source is a uniform absolute constant
- encoding: No degree bound on intermediate gates is needed → no syntactic-degree hypothesis on C; reason: the sentence states the absence of the hypothesis
Preamble
import Mathlib import Definitions.Def_NCFactorClosure607_Circuits_Supplement_CoeffAlgorithm universe u v
Formal statement
namespace NCFactorClosure607.Circuits.Supplement
open NCFactorClosure607.Circuits
/-- Lemma 7.1 (Computing one coefficient), p.17. There is one absolute constant `K` such that for
every field `F`, every type `X` of variables, every well-formed circuit `C` (no degree bound on
any gate) and every word `w`, the algorithm `coeffAlgo` returns the coefficient `[w]C`, using at
most `K · size(C) · d³` field operations when `w` has length `d ≥ 1`, and at most `K · size(C)`
field operations for the empty word. -/
theorem computing_one_coefficient :
∃ K : ℕ, ∀ (F : Type u) [Field F] (X : Type v) [DecidableEq X] (C : Circuit F X)
(w : List X), C.WellFormed →
(coeffAlgo C w).1 = coeff (FreeMonoid.ofList w) C.eval ∧
(1 ≤ w.length → (coeffAlgo C w).2 ≤ K * C.size * w.length ^ 3) ∧
(w = [] → (coeffAlgo C w).2 ≤ K * C.size) := 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, Lemma 7.1 and its proof; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/607.pdf