Theorem 8.2 — the same factorization with an NP oracle by a zero-error randomized algorithm of expected polynomial running time
OpenNCFactorClosure607.Circuits.Supplement.zero_error_randomized_factorizationcomputational-complexityfactorizationfinite-fieldsoracle-machinesp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1randomized-algorithms
There are a language , one randomized oracle machine reading independent fair coins, and a polynomial bound such that for every input as in Theorem 8.1 (a circuit over an explicitly represented computing a nonzero with ), the machine with oracle :
- terminates with probability one;
- has expected running time at most :
- has zero error: on every coin sequence on which it halts, its output is the encoding of a scalar and a list of circuits over the input field forming a complete ordered irreducible factorization of , of length at most .
This companion theorem replaces the second-level oracle of Theorem 8.1 by an NP oracle at the price of randomness, without any error.
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: Given the circuit and unary degree bound above → for every input (p, φ, m, C, 1^D) encoded as a tuple of self-delimiting strings with C well-formed, C.eval ≠ 0 and deg C.eval ≤ D; inputs outside this promise are unconstrained; reason: the promise of §8 (p.18)
- encoding: a complete ordered irreducible factorization; a scalar and a list of circuits → the encoding of λ ≠ 0 and well-formed circuits over F_q in the input variables whose polynomials f_i are nonconstant and irreducible, with f = λ f_1 ⋯ f_k and the list empty iff f is a scalar; reason: the definitions of p.5 and §8
- encoding: computed with an NP oracle by a zero-error randomized algorithm of expected polynomial running time; terminates with probability one → ∃ O ∈ CookPvsNP.NP Bool and one well-formed randomized oracle machine with a coin tape holding ω ∈ {0,1}^ℕ under the infinite product of fair coin measures: the halting set has measure 1, the lower integral of the running time (∞ when not halting) is ≤ c(|x| + 1)^e, and the output at the first halting step is correct for every ω; reason: the standard meaning of zero error, expected time and almost-sure termination
- encoding: polynomial total encoded length → output length ≤ c(|x| + 1)^e; reason: a polynomial in the input length, which contains D in unary
Preamble
import Mathlib import Definitions.Def_NCFactorClosure607_Circuits_Supplement_Machines
Formal statement
namespace NCFactorClosure607.Circuits.Supplement
open NCFactorClosure607.Circuits Polynomial MeasureTheory
open scoped ENNReal
/-- Theorem 8.2 (Zero-error randomized factorization), p.19. There are a language `O ∈ NP`, one
randomized oracle machine `R` reading independent fair coins, and one polynomial bound
`c (n + 1)^e` such that for every input `x` as in Theorem 8.1 (an explicitly represented finite
field `F_q`, a well-formed circuit over `F_q` computing a nonzero `f`, and a unary bound
`D ≥ deg f`), `R` with oracle `O`:
* terminates with probability one;
* has expected running time at most `c (|x| + 1)^e`;
* has zero error: on every coin sequence on which it halts, its output (at the halting time) is
the encoding of a scalar and a list of circuits over `F_q` forming a complete ordered
irreducible factorization of `f`, of length at most `c (|x| + 1)^e`. -/
theorem zero_error_randomized_factorization :
∃ (O : CookPvsNP.Lang Bool) (R : RandOracleMachine) (c e : ℕ),
O ∈ CookPvsNP.NP Bool ∧ R.WF ∧
∀ (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 →
coinMeasure {ω | ∃ t, R.HaltedAt (langOracle O) (encFactorInput hφ C D) ω t} = 1 ∧
∫⁻ ω, (R.runTime (langOracle O) (encFactorInput hφ C D) ω : ℝ≥0∞) ∂coinMeasure ≤
(CookLevin.polyBound c e (encFactorInput hφ C D).length : ℝ≥0∞) ∧
∀ (ω : ℕ → Bool) (t : ℕ), R.HaltedAt (langOracle O) (encFactorInput hφ C D) ω t →
(∀ t' < t, ¬ R.HaltedAt (langOracle O) (encFactorInput hφ C D) ω t') →
(R.outputAt (langOracle O) (encFactorInput hφ C D) ω t).length ≤
CookLevin.polyBound c e (encFactorInput hφ C D).length ∧
IsFactorizationOutput hφ C.eval
(R.outputAt (langOracle O) (encFactorInput hφ C D) ω t) := 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.19, Theorem 8.2; §8 opening, p.18; proof pp.19–21; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/607.pdf