Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 8.2 — the same factorization with an NP oracle by a zero-error randomized algorithm of expected polynomial running time

Open
NCFactorClosure607.Circuits.Supplement.zero_error_randomized_factorization

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

computational-complexityfactorizationfinite-fieldsoracle-machinesp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1randomized-algorithms

There are a language O∈NPO\in\mathrm{NP}O∈NP, one randomized oracle machine RRR reading independent fair coins, and a polynomial bound c(n+1)ec(n+1)^ec(n+1)e such that for every input x=(p,φ,m,C,1D)x=(p,\varphi,m,C,1^D)x=(p,φ,m,C,1D) as in Theorem 8.1 (a circuit over an explicitly represented Fq\mathbb F_qFq​ computing a nonzero fff with deg⁡f≤D\deg f\le Ddegf≤D), the machine RRR with oracle OOO:

  1. terminates with probability one;
  2. has expected running time at most c(∣x∣+1)ec(|x|+1)^ec(∣x∣+1)e:
Eω[timeR(x,ω)]≤c(∣x∣+1)e;\mathbb E_\omega[\mathrm{time}_R(x,\omega)]\le c(|x|+1)^e;Eω​[timeR​(x,ω)]≤c(∣x∣+1)e;
  1. 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 fff, of length at most c(∣x∣+1)ec(|x|+1)^ec(∣x∣+1)e.

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

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me