2012/02/20 by Johannes Mittmann, Mittmann, Johannes, Nitin Saxena +3
Computer Science · Mathematics · #03D15 #12Y05 (Primary) 13N05 #14F30 #68Q17 #68W30 (Secondary) #Commutative Algebra (math.AC) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Dynamics and Fractals #Polynomial and algebraic computation #Topological and Geometric Data Analysis #cs.CC #math.AC #msc:03D15 #msc:12Y05 #msc:13N05 #msc:14F30 #msc:68Q17 #msc:68W30
paper · pdf · doi:10.48550/arxiv.1202.4301
arxiv created 2012/02/20 · openalex publication_date 2012/02/20 · arxiv updated 2012/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A set of multivariate polynomials, over a field of zero or large characteristic, can be tested for algebraic independence by the well-known Jacobian criterion. For fields of other characteristic p>0, there is no analogous characterization known. In this paper we give the first such criterion. Essentially, it boils down to a non-degeneracy condition on a lift of the Jacobian polynomial over (an unramified extension of) the ring of p-adic integers. Our proof builds on the de Rham-Witt complex, which was invented by Illusie (1979) for crystalline cohomology computations, and we deduce a natural generalization of the Jacobian. This new avatar we call the Witt-Jacobian. In essence, we show how to faithfully differentiate polynomials over Fp (i.e. somehow avoid dxp/dx=0) and thus capture algebraic independence. We apply the new criterion to put the problem of testing algebraic independence in the complexity class NP^#P (previously best was PSPACE). Also, we give a modest application to the problem of identity testing in algebraic complexity theory.