Algebraic independence in positive characteristic: A 𝑝-adic calculus

Mittmann, Johannes; Saxena, Nitin; Scheiblechner, Peter

doi:10.1090/S0002-9947-2014-06268-5

Algebraic independence in positive characteristic: A $p$-adic calculus
HTML articles powered by AMS MathViewer

by Johannes Mittmann, Nitin Saxena and Peter Scheiblechner PDF

Trans. Amer. Math. Soc. 366 (2014), 3425-3450 Request permission

Abstract:

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$, no analogous characterization is 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 functorial de Rham-Witt complex, which was invented by Illusie (1979) for crystalline cohomology computations, and we deduce a natural explicit generalization of the Jacobian. We call this new avatar 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 give two applications of this criterion in algebraic complexity theory.

References

Sanjeev Arora and Boaz Barak, Computational complexity, Cambridge University Press, Cambridge, 2009. A modern approach. MR 2500087, DOI 10.1017/CBO9780511804090
Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, and Nitin Saxena, Jacobian hits circuits: hitting-sets, lower bounds for depth-$D$ occur-$k$ formulas & depth-3 transcendence degree-$k$ circuits, STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 599–613. MR 2961534, DOI 10.1145/2213977.2214033
Stuart J. Berkowitz, On computing the determinant in small parallel time using a small number of processors, Inform. Process. Lett. 18 (1984), no. 3, 147–150. MR 760366, DOI 10.1016/0020-0190(84)90018-8
Markus Bläser, Moritz Hardt, Richard J. Lipton, and Nisheeth K. Vishnoi, Deterministically testing sparse polynomial identities of unbounded degree, Inform. Process. Lett. 109 (2009), no. 3, 187–192. MR 2485086, DOI 10.1016/j.ipl.2008.09.029
M. Beecken, J. Mittmann, and N. Saxena, Algebraic independence and blackbox identity testing, Inform. and Comput. 222 (2013), 2–19. MR 3000958, DOI 10.1016/j.ic.2012.10.004
Walter Baur and Volker Strassen, The complexity of partial derivatives, Theoret. Comput. Sci. 22 (1983), no. 3, 317–330. MR 693063, DOI 10.1016/0304-3975(83)90110-X
W. Castryck, J. Denef, and F. Vercauteren, Computing zeta functions of nondegenerate curves, IMRP Int. Math. Res. Pap. (2006), Art. ID 72017, 57. MR 2268492
Pierre Deligne, La conjecture de Weil. I, Inst. Hautes Études Sci. Publ. Math. 43 (1974), 273–307 (French). MR 340258
Pierre Deligne, La conjecture de Weil. II, Publications Mathématiques de L’IHÉS 52 (1980), 137–252.
E. Delaleau and M. Fliess, An algebraic interpretation of the structure algorithm with an application to feedback decoupling, 2nd IFAC Symposium Nonlinear Control Systems Design, 1992, pp. 489–494.
Z. Dvir, D. Gutfreund, G.N. Rothblum, and S.P. Vadhan, On approximating the entropy of polynomial mappings, Innovations in Computer Science (ICS), 2011, pp. 460–475.
Zeev Dvir, Ariel Gabizon, and Avi Wigderson, Extractors and rank extractors for polynomial sources, Comput. Complexity 18 (2009), no. 1, 1–58. MR 2505192, DOI 10.1007/s00037-009-0258-4
Jan Denef and Frederik Vercauteren, Counting points on $C_{ab}$ curves using Monsky-Washnitzer cohomology, Finite Fields Appl. 12 (2006), no. 1, 78–102. MR 2190188, DOI 10.1016/j.ffa.2005.01.003
Zeev Dvir, Extractors for varieties, 24th Annual IEEE Conference on Computational Complexity, IEEE Computer Soc., Los Alamitos, CA, 2009, pp. 102–113. MR 2932459, DOI 10.1109/CCC.2009.7
Bernard Dwork, On the rationality of the zeta function of an algebraic variety, Amer. J. Math. 82 (1960), 631–648. MR 140494, DOI 10.2307/2372974
David Eisenbud, Commutative algebra, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. With a view toward algebraic geometry. MR 1322960, DOI 10.1007/978-1-4612-5350-1
Hervé Fournier, Guillaume Malod, and Stefan Mengel, Monomials in arithmetic circuits: complete problems in the counting hierarchy, 29th International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 14, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2012, pp. 362–373. MR 2909328
K. Forsman, Constructive commutative algebra in nonlinear control theory, Ph.D. thesis, Dept. of Electrical Engg., Linköping University, Sweden, 1991.
Ralf Gerkmann, Relative rigid cohomology and deformation of hypersurfaces, Int. Math. Res. Pap. IMRP 1 (2007), Art. ID rpm003, 67. MR 2334009
P. Gaudry and N. Gürel, An extension of Kedlaya’s point-counting algorithm to superelliptic curves, Advances in cryptology—ASIACRYPT 2001 (Gold Coast), Lecture Notes in Comput. Sci., vol. 2248, Springer, Berlin, 2001, pp. 480–494.
Alexander Grothendieck, Formule de Lefschetz et rationalité des fonctions $L$, Séminaire Bourbaki, Vol. 9, Soc. Math. France, Paris, 1995, pp. Exp. No. 279, 41–55 (French). MR 1608788
Michiel Hazewinkel, Formal groups and applications, Pure and Applied Mathematics, vol. 78, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1978. MR 506881
Luc Illusie, Complexe de de Rham-Witt et cohomologie cristalline, Ann. Sci. École Norm. Sup. (4) 12 (1979), no. 4, 501–661 (French). MR 565469
Luc Illusie, Crystalline cohomology, Motives (Seattle, WA, 1991) Proc. Sympos. Pure Math., vol. 55, Amer. Math. Soc., Providence, RI, 1994, pp. 43–70. MR 1265522, DOI 10.1090/pspum/055.1/1265522
C. G. J. Jacobi, De determinantibus functionalibus, J. Reine Angew. Math. 22 (1841), no. 4, 319–359.
K. A. Kalorkoti, A lower bound for the formula size of rational functions, SIAM J. Comput. 14 (1985), no. 3, 678–687. MR 795939, DOI 10.1137/0214050
Neeraj Kayal, The complexity of the annihilating polynomial, 24th Annual IEEE Conference on Computational Complexity, IEEE Computer Soc., Los Alamitos, CA, 2009, pp. 184–193. MR 2932466, DOI 10.1109/CCC.2009.37
Kiran S. Kedlaya, Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, J. Ramanujan Math. Soc. 16 (2001), no. 4, 323–338. MR 1877805
Gregor Kemper, A constructive approach to Noether’s problem, Manuscripta Math. 90 (1996), no. 3, 343–363. MR 1397662, DOI 10.1007/BF02568311
Neal Koblitz, $p$-adic numbers, $p$-adic analysis, and zeta-functions, 2nd ed., Graduate Texts in Mathematics, vol. 58, Springer-Verlag, New York, 1984. MR 754003, DOI 10.1007/978-1-4612-1112-9
Martin Kreuzer and Lorenzo Robbiano, Computational commutative algebra. 1, Springer-Verlag, Berlin, 2000. MR 1790326, DOI 10.1007/978-3-540-70628-1
Neeraj Kayal and Chandan Saha, On the sum of square roots of polynomials and related problems, 26th Annual IEEE Conference on Computational Complexity, IEEE Computer Soc., Los Alamitos, CA, 2011, pp. 292–299. MR 3025383
S. Lang, Algebra, 2nd ed., Addison-Wesley, 1984.
H. W. Lenstra Jr., Finding isomorphisms between finite fields, Math. Comp. 56 (1991), no. 193, 329–347. MR 1052099, DOI 10.1090/S0025-5718-1991-1052099-2
Saul Lubkin, A $p$-adic proof of Weil’s conjectures, Ann. of Math. (2) 87 (1968), 105-194; ibid. (2) 87 (1968), 195–255. MR 0224616, DOI 10.2307/1970597
M. S. L′vov, Calculation of invariants of programs interpreted over an integral domain, Kibernetika (Kiev) 4 (1984), i, 23–28, 133 (Russian, with English summary). MR 788653
Alan G. B. Lauder and Daqing Wan, Counting points on varieties over finite fields of small characteristic, Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 579–612. MR 2467558
S. Mengel, On degenerate polynomials, Private communication, 2012.
James S. Milne, Étale cohomology, Princeton Mathematical Series, No. 33, Princeton University Press, Princeton, N.J., 1980. MR 559531
Ketan D. Mulmuley, On P vs. NP and geometric complexity theory, J. ACM 58 (2011), no. 2, Art. 5, 26. MR 2786586, DOI 10.1145/1944345.1944346
O. Perron, Algebra I (Die Grundlagen), W. de Gruyter, Berlin, 1927.
A. Płoski, Algebraic Dependence of Polynomials After O. Perron and Some Applications, Computational Commutative and Non-Commutative Algebraic Geometry, 2005, pp. 167–173.
R. Raghavendran, Finite associative rings, Compositio Math. 21 (1969), 195–229. MR 246905
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
Takakazu Satoh, The canonical lift of an ordinary elliptic curve over a finite field and its point counting, J. Ramanujan Math. Soc. 15 (2000), no. 4, 247–270. MR 1801221
Nitin Saxena, Progress on polynomial identity testing, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 99 (2009), 49–79. MR 2589248
J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), no. 4, 701–717. MR 594695, DOI 10.1145/322217.322225
Jean-Pierre Serre, Local fields, Graduate Texts in Mathematics, vol. 67, Springer-Verlag, New York-Berlin, 1979. Translated from the French by Marvin Jay Greenberg. MR 554237
David Singmaster, Divisibility of binomial and multinomial coefficients by primes and prime powers, A collection of manuscripts related to the Fibonacci sequence, Fibonacci Assoc., Santa Clara, Calif., 1980, pp. 98–113. MR 624104
Michael Shub and Steve Smale, On the intractability of Hilbert’s Nullstellensatz and an algebraic version of “$\textrm {NP}\not =\textrm {P}$?”, Duke Math. J. 81 (1995), no. 1, 47–54 (1996). A celebration of John F. Nash, Jr. MR 1381969, DOI 10.1215/S0012-7094-95-08105-8
Amir Shpilka and Amir Yehudayoff, Arithmetic circuits: a survey of recent results and open questions, Found. Trends Theor. Comput. Sci. 5 (2009), no. 3-4, 207–388 (2010). MR 2756166, DOI 10.1561/0400000039
L. G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979), no. 2, 189–201. MR 526203, DOI 10.1016/0304-3975(79)90044-6
Zhe-Xian Wan, Lectures on finite fields and Galois rings, World Scientific Publishing Co., Inc., River Edge, NJ, 2003. MR 2008834, DOI 10.1142/5350
E. Witt, Zyklische Körper und Algebren der Characteristik $p$ vom Grade $p^n$, J. Reine Angew. Math. (1936), no. 176, 126–140.