Algebraic Independence in Positive Characteristic -- A p-Adic Calculus

Details Algebraic Independence in Positive Characteristic -- A p-Adic Calculus Algebraic Independence in Positive Characteristic -- A p-Adic Calculus

2012-02-20

arxiv.org/abs/1202.4301v1

Computer Science

Computational Complexity

Scientific paper

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 F_p (i.e. somehow avoid dx^p/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.

Affiliated with

Also associated with

No associations

Rating

Algebraic Independence in Positive Characteristic -- A p-Adic Calculus does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algebraic Independence in Positive Characteristic -- A p-Adic Calculus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algebraic Independence in Positive Characteristic -- A p-Adic Calculus will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-564641