Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Bounded modular certificates characterize rational image dimension

Proved
APSCounting893.Main.bounded_modular_dimension_certificates

by Shuze Chen · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

algebraic-geometryapscomplexity-theoryjacobian

Let CCC be a valid arithmetic circuit over Q\mathbb QQ, including circuits with division gates whose outputs are promised polynomials. Let FCF_CFC​ be its polynomial map over C\mathbb CC, and let YCY_CYC​ be the Zariski closure of its image. Let Cert⁡(C,k)\operatorname{Cert}(C,k)Cert(C,k) be the bounded modular Jacobian-certificate predicate defined in the accompanying module. Then there is a natural number rrr such that

dim⁡YC=r,k≤r  ⟺  Cert⁡(C,k)for every k≥0.\dim Y_C=r,\qquad k\le r\iff\operatorname{Cert}(C,k)\quad\text{for every }k\ge0.dimYC​=r,k≤r⟺Cert(C,k)for every k≥0.

In this predicate, a certificate consists of distinct output and variable indices, a prime ppp, and a sparse integer point where the cleared Jacobian minor is nonzero modulo ppp. For circuit encoding length LLL, selected variable indices have at most LLL bits, ppp has at most 128(L+1)+8128(L+1)+8128(L+1)+8 bits, and the encoded sparse point has length at most 32(L+1)232(L+1)^232(L+1)2.

This connects algebraic image dimension with bounded finite arithmetic data. It applies even when the declared number of variables is given in binary and many variables are unused. The empty-output and zero-dimensional cases are included. This theorem supplies the mathematical certificate equivalence; the uniform finite-machine search is a separate theorem.

Preamble
import Definitions.Def_APSCounting893_Main_ModularJacobianData
set_option autoImplicit false
Formal statement
theorem APSCounting893.Main.bounded_modular_dimension_certificates {n : ℕ} (C : APSCounting893.Main.ArithmeticCircuit n)
    (hvalid : APSCounting893.Main.ValidCircuit .rational C) :
    ∃ r : ℕ,RSCapacity.algDim (APSCounting893.Main.imageClosure (APSCounting893.Main.rationalComplexPolynomials C))=
      ((r : ℕ∞) : WithBot ℕ∞) ∧
      ∀ k : ℕ,k≤r ↔ APSCounting893.Main.ModularJacobianCertificate C k := by sorry
Source
Agarwal, Hari, Pandey and Shukla, Approximate Polynomial Satisfiability and Integral Closure Membership in the Counting Hierarchy, STOC 2027 submission #893, Section 6, Lemma 6.1 and proof, p.23. Auxiliary modular implementation of its characteristic-zero Jacobian-rank step; explicit witness bounds are proved here. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/893.pdf#page=23 . Schwartz–Zippel: Mathlib 0df444a, Mathlib/Algebra/MvPolynomial/SchwartzZippel.lean, schwartz_zippel_totalDegree; modular witness: Mathlib/NumberTheory/Chebyshev.lean, two_pow_le_mul_lcmUpto.

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