Uniform Counting Hierarchy language for modular Jacobian thresholds
ProvedAPSCounting893.Main.modular_jacobian_threshold_language_in_chThere is one total language at one fixed level of the Counting Hierarchy such that, for every valid rational arithmetic circuit and every nonnegative integer ,
Here is the bounded modular Jacobian certificate predicate: it selects injective output and variable indices, a prime of the stated linear bit-length bound, and a sparsely encoded integer assignment of the stated quadratic length bound, at which the cleared integer Jacobian minor is nonzero modulo that prime. Divisions are interpreted in the circuit's rational-function field before the polynomial-output promise is applied. The variable count and unused variable labels may be given in binary.
The language and its hierarchy level are fixed before every circuit and every threshold. This is the threshold-decision component of uniform image-dimension computation in Lemma 6.1; answers on words outside the valid circuit encodings are unrestricted.
import Definitions.Def_APSCounting893_Main_ModularJacobianData import Definitions.Def_APSCounting893_Main_OracleProofPrimitives set_option autoImplicit false open APSCounting893.Main
theorem APSCounting893.Main.modular_jacobian_threshold_language_in_ch :
∃ A : Language,InCountingHierarchy A ∧
∀ (n : ℕ) (C : ArithmeticCircuit n),ValidCircuit .rational C →
∀ k : ℕ,A (pairWord C.encode (encodeNat k)) ↔ ModularJacobianCertificate C k := by sorry