ECCC-Report TR12-014https://eccc.weizmann.ac.il/report/2012/014Comments and Revisions published for TR12-014en-usThu, 23 Feb 2012 09:33:43 +0200
Paper TR12-014
| Algebraic Independence in Positive Characteristic -- A p-Adic Calculus |
Johannes Mittmann,
Nitin Saxena,
Peter Scheiblechner
https://eccc.weizmann.ac.il/report/2012/014A 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 $\mathbb{F}_p$ (i.e. somehow avoid $\partial x^p/\partial x=0$) and thus capture algebraic independence.
We apply the new criterion to put the problem of testing algebraic independence in the complexity class $\mbox{NP}^\mbox{#P}$ (previously best was PSPACE). Also, we give a modest application to the problem of identity testing in algebraic complexity theory.Thu, 23 Feb 2012 09:33:43 +0200https://eccc.weizmann.ac.il/report/2012/014