Remark 4.2 — every factor of a circuit of syntactic degree has a circuit of size and syntactic degree
OpenNCFactorClosure607.Circuits.Supplement.common_bound_for_all_factorsarithmetic-circuitsfactorizationnoncommutative-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a field and a set of noncommuting variables. There is an absolute constant such that for every circuit of size and syntactic degree at most , where , every factor of the polynomial it computes ( with ) has a circuit of size at most
and syntactic degree at most .
The bound is in terms of the original circuit; it does not grow when a factor is split further, which is what the bounded search of Theorems 8.1 and 8.2 relies on.
Differences from the source:
- generalization: X = {x_1, …, x_m} with m ≥ 1 → an arbitrary type X of noncommuting variables; reason: the statement for every type specializes to every finite nonempty variable set
- reading: fix an absolute constant K ≥ 1 large enough that B(s, D) = KsD⁶ bounds the above construction. Every factor has a circuit of size at most B(s, D) → ∃ K ≥ 1 such that every factor has a well-formed circuit of size ≤ K·s·D⁶ and syntactic degree ≤ D; reason: the Remark's conclusion; the last sentence is explanatory
Preamble
import Mathlib import Definitions.Def_NCFactorClosure607_Circuits_Circuit import Definitions.Def_NCFactorClosure607_Circuits_Polynomials universe u v
Formal statement
namespace NCFactorClosure607.Circuits.Supplement
open NCFactorClosure607.Circuits
/-- Remark 4.2 (A common bound for all factors), p.10. There is one absolute constant `K ≥ 1`
such that for every field `F`, every type `X` of noncommuting variables, every well-formed
circuit `C` of size `s` and syntactic degree at most `D ≥ 1`, and every factor `g` of its output
(`C.eval = a g b` with `a, g, b ≠ 0`), `g` has a circuit of size at most `B(s, D) = K s D⁶` and
syntactic degree at most `D`. -/
theorem common_bound_for_all_factors :
∃ K : ℕ, 1 ≤ K ∧ ∀ (F : Type u) [Field F] (X : Type v) (C : Circuit F X) (D : ℕ),
C.WellFormed → 1 ≤ D → C.synDeg ≤ D →
∀ a g b : FreeAlgebra F X, C.eval = a * g * b → a ≠ 0 → g ≠ 0 → b ≠ 0 →
∃ C' : Circuit F X, C'.WellFormed ∧ C'.eval = g ∧ C'.size ≤ K * C.size * D ^ 6 ∧
C'.synDeg ≤ D := 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.10, Remark 4.2; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/607.pdf