Polynomial-time modular Jacobian inverse verification
ProvedAPSCounting893.Main.native_modular_jacobian_verificationFor every modulus , evaluate the row-cleared Jacobian matrix of a rational arithmetic circuit at a sparse integer assignment, with chosen output and variable indices. A supplied finite list encodes the entries of a matrix in row order. The executable verification procedure satisfies
The verifier is computed by one finite deterministic binary multitape Turing machine in polynomial time in the complete encoded input length. The polynomial bounds both time and space uniformly over every circuit, modulus, assignment, index list and proposed inverse, including malformed values outside the algebraic promises. The semantic identity uses the actual integer-polynomial numerator–denominator pairs and their formal derivatives. No determinant expansion is part of the algorithm.
This result provides a uniform finite certificate checker for the nonzero-minor condition in the image-dimension procedure.
import Definitions.Def_APSCounting893_Main_ModularJacobianComputation import Definitions.Def_APSCounting893_Main_ModularJacobianData import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_PolyTime set_option autoImplicit false set_option backward.isDefEq.respectTransparency.types false open APSCounting893.Main
theorem APSCounting893.Main.native_modular_jacobian_verification :
Turing.MultiTapeTM.ComputableInPolyTime
(fun q : MatrixParameters × List ℕ => residueMatrixInverseTest q.1 q.2)
(Turing.MultiTapeTM.encPair encMatrixParameters (Turing.MultiTapeTM.encList Turing.MultiTapeTM.encNat))
Turing.MultiTapeTM.encBool ∧
(∀ (n k p : ℕ) (hp : 2 ≤ p) (C : ArithmeticCircuit n) (a : List (Fin n × ℤ))
(o : Fin k → Fin C.outputs.length) (v : Fin k → Fin n) (inverse : List ℕ),
residueMatrixInverseTest
(p,(C.raw,(rawAssignmentOf a,(List.ofFn (fun i => (o i).val),List.ofFn (fun j => (v j).val)))))
inverse = true ↔
(clearedIntegerMatrix (circuitJacobianIntegerPairs C o v)).map
(MvPolynomial.eval₂Hom (Int.castRingHom (ZMod p)) (fun l => (sparseAssignmentPoint a l : ZMod p)))*
Matrix.of (fun i j : Fin k => (inverse.getD (i.val*k+j.val) 0 : ZMod p))=1) := by sorry