Theorem 8.1 — a complete ordered irreducible factorization of a circuit over is computable in
OpenNCFactorClosure607.Circuits.Supplement.deterministic_factorizationThere are a language and one deterministic oracle transducer with a polynomial bound such that the following holds. Let be an explicitly represented finite field, let a circuit over in variables compute a nonzero polynomial , and let . The transducer is clocked to halt within steps on every bit string and for every membership oracle; the promise restricts correctness only. On the encoded input , the machine with oracle halts within steps and outputs the encoding of a scalar and a list of circuits over with
the list being empty exactly when is a scalar; the output has length at most .
This companion theorem turns the uniform factor-size bound of Remark 4.2 into a deterministic factorization algorithm relative to a second-level oracle.
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 in FP^{Σ₂^P} → ∃ O ∈ BudgetCoreExchange.Sigma2P Bool and one well-formed ConsModCount oracle transducer, clocked within c(|x| + 1)^e on all bit strings and for every membership oracle, whose output with oracle O is correct on every promised input; reason: the polynomial-time oracle-transducer normal form; only correctness depends on the promise
- encoding: total encoded length polynomial in the input length and D → output length ≤ c(|x| + D + 1)^e; reason: a polynomial in both parameters
import Mathlib import Definitions.Def_NCFactorClosure607_Circuits_Supplement_Machines
namespace NCFactorClosure607.Circuits.Supplement
open NCFactorClosure607.Circuits Polynomial
/-- Theorem 8.1 (Deterministic factorization), p.18. There are a language `O ∈ Σ₂^P` and one
deterministic polynomial-time oracle transducer `Mo` such that: for every explicitly represented
finite field `F_q = F_p[t]/(φ)`, every well-formed circuit `C` over `F_q` in `m` variables
computing a nonzero `f`, and every degree bound `D ≥ deg f` (in unary), `Mo` with oracle `O`, on
the encoded input `x`, halts within `c (|x| + 1)^e` steps and outputs the encoding of a scalar `λ`
and a list of circuits over `F_q` forming a complete ordered irreducible factorization
`f = λ f_1 ⋯ f_k`, of length at most `c (|x| + D + 1)^e`. The transducer is clocked to halt
within the same polynomial on every bit string and for every membership oracle; only output
correctness is restricted to the input promise. -/
theorem deterministic_factorization :
∃ (O : CookPvsNP.Lang Bool) (Mo : ConsModCount.OracleMachine) (c e : ℕ),
O ∈ BudgetCoreExchange.Sigma2P Bool ∧ Mo.WF ∧ OraclePolyTime Mo c e ∧
∀ (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 →
∃ y : List Bool,
OracleOutputsIn Mo (langOracle O) (encFactorInput hφ C D)
(CookLevin.polyBound c e (encFactorInput hφ C D).length) y ∧
y.length ≤ CookLevin.polyBound c e ((encFactorInput hφ C D).length + D) ∧
IsFactorizationOutput hφ C.eval y := by sorry
end NCFactorClosure607.Circuits.Supplement