Uniform CH search for the largest modular Jacobian certificate
ProvedAPSCounting893.Main.modular_dimension_certificate_search_in_chFor valid rational arithmetic circuits, one fixed Counting Hierarchy oracle permits a deterministic polynomial-time machine to return the largest size of a bounded modular Jacobian certificate.
There exist a total language and a total function such that, for every valid circuit , some natural number satisfies
The machine, polynomial time bound and hierarchy level precede all circuits and all input lengths. Answers outside the circuit promises are unrestricted. The certificate predicate uses integer cross multiplication, cleared Jacobian minors, bounded sparse assignments and prime residues, rather than an APS or image-dimension oracle.
Together with the mathematical certificate theorem, this is the computational part of the image-dimension milestone.
import Definitions.Def_APSCounting893_Main_ModularJacobianData set_option autoImplicit false
theorem APSCounting893.Main.modular_dimension_certificate_search_in_ch :
∃ (A : APSCounting893.Main.Language) (f : APSCounting893.Main.Word → APSCounting893.Main.Word),
APSCounting893.Main.InCountingHierarchy A ∧ APSCounting893.Main.FunctionInPWithOracle A f ∧
∀ (n : ℕ) (C : APSCounting893.Main.ArithmeticCircuit n), APSCounting893.Main.ValidCircuit .rational C →
∃ r : ℕ,f C.encode=APSCounting893.Main.encodeNat r ∧
∀ k : ℕ,k≤r ↔ APSCounting893.Main.ModularJacobianCertificate C k := by sorry