Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Algebraic independence in positive characteristic: A $ p$-adic calculus


Authors: Johannes Mittmann, Nitin Saxena and Peter Scheiblechner
Journal: Trans. Amer. Math. Soc. 366 (2014), 3425-3450
MSC (2010): Primary 12Y05, 13N05, 14F30, 03D15, 68Q17, 68W30
DOI: https://doi.org/10.1090/S0002-9947-2014-06268-5
Published electronically: March 14, 2014
MathSciNet review: 3192602
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [AB09] Sanjeev Arora and Boaz Barak, Computational complexity, Cambridge University Press, Cambridge, 2009. A modern approach. MR 2500087 (2010i:68001)
  • [ASSS12] 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, https://doi.org/10.1145/2213977.2214033
  • [Ber84] 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 (85k:65111), https://doi.org/10.1016/0020-0190(84)90018-8
  • [BHLV09] 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 (2010b:68059), https://doi.org/10.1016/j.ipl.2008.09.029
  • [BMS13] M. Beecken, J. Mittmann, and N. Saxena, Algebraic independence and blackbox identity testing, Inform. and Comput. 222 (2013), 2-19. MR 3000958, https://doi.org/10.1016/j.ic.2012.10.004
  • [BS83] Walter Baur and Volker Strassen, The complexity of partial derivatives, Theoret. Comput. Sci. 22 (1983), no. 3, 317-330. MR 693063 (84c:68027), https://doi.org/10.1016/0304-3975(83)90110-X
  • [CDV06] 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 (2007h:14026)
  • [Del74] Pierre Deligne, La conjecture de Weil. I, Inst. Hautes Études Sci. Publ. Math. 43 (1974), 273-307 (French). MR 0340258 (49 #5013)
  • [Del80] Pierre Deligne, La conjecture de Weil. II, Publications Mathématiques de L'IHÉS 52 (1980), 137-252.
  • [DF92] 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.
  • [DGRV11] 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.
  • [DGW09] Zeev Dvir, Ariel Gabizon, and Avi Wigderson, Extractors and rank extractors for polynomial sources, Comput. Complexity 18 (2009), no. 1, 1-58. MR 2505192 (2010b:68174), https://doi.org/10.1007/s00037-009-0258-4
  • [DV06] 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 (2007c:11075), https://doi.org/10.1016/j.ffa.2005.01.003
  • [Dvi09] Zeev Dvir, Extractors for varieties, 24th Annual IEEE Conference on Computational Complexity, IEEE Computer Soc., Los Alamitos, CA, 2009, pp. 102-113. MR 2932459, https://doi.org/10.1109/CCC.2009.7
  • [Dwo60] Bernard Dwork, On the rationality of the zeta function of an algebraic variety, Amer. J. Math. 82 (1960), 631-648. MR 0140494 (25 #3914)
  • [Eis95] David Eisenbud, Commutative algebra, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. With a view toward algebraic geometry. MR 1322960 (97a:13001)
  • [FMM12] 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
  • [For91] K. Forsman, Constructive commutative algebra in nonlinear control theory, Ph.D. thesis, Dept. of Electrical Engg., Linköping University, Sweden, 1991.
  • [Ger07] Ralf Gerkmann, Relative rigid cohomology and deformation of hypersurfaces, Int. Math. Res. Pap. IMRP 1 (2007), Art. ID rpm003, 67. MR 2334009 (2008f:14036)
  • [GG01] 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.
  • [Gro65] 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
  • [Haz78] Michiel Hazewinkel, Formal groups and applications, Pure and Applied Mathematics, vol. 78, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York, 1978. MR 506881 (82a:14020)
  • [Ill79] Luc Illusie, Complexe de deRham-Witt et cohomologie cristalline, Ann. Sci. École Norm. Sup. (4) 12 (1979), no. 4, 501-661 (French). MR 565469 (82d:14013)
  • [Ill94] 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 (95a:14021)
  • [Jac41] C. G. J. Jacobi, De determinantibus functionalibus, J. Reine Angew. Math. 22 (1841), no. 4, 319-359.
  • [Kal85] K. A. Kalorkoti, A lower bound for the formula size of rational functions, SIAM J. Comput. 14 (1985), no. 3, 678-687. MR 795939 (87a:68088), https://doi.org/10.1137/0214050
  • [Kay09] 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, https://doi.org/10.1109/CCC.2009.37
  • [Ked01] Kiran S. Kedlaya, Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, J. Ramanujan Math. Soc. 16 (2001), no. 4, 323-338. MR 1877805 (2002m:14019)
  • [Kem96] Gregor Kemper, A constructive approach to Noether's problem, Manuscripta Math. 90 (1996), no. 3, 343-363. MR 1397662 (97d:13005), https://doi.org/10.1007/BF02568311
  • [Kob84] 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 (86c:11086)
  • [KR00] Martin Kreuzer and Lorenzo Robbiano, Computational commutative algebra. 1, Springer-Verlag, Berlin, 2000. MR 1790326 (2001j:13027)
  • [KS11] 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
  • [Lan84] S. Lang, Algebra, 2nd ed., Addison-Wesley, 1984.
  • [Len91] H. W. Lenstra Jr., Finding isomorphisms between finite fields, Math. Comp. 56 (1991), no. 193, 329-347. MR 1052099 (91d:11151), https://doi.org/10.2307/2008545
  • [Lub68] 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 (37 #215)
  • [L'v84] M. S. Lvov, Calculation of invariants of programs interpreted over an integral domain, Kibernetika (Kiev) 4 (1984), i, 23-28, 133 (Russian, with English summary). MR 788653 (86i:68090)
  • [LW08] 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 (2009j:14029)
  • [Men12] S. Mengel, On degenerate polynomials, Private communication, 2012.
  • [Mil80] James S. Milne, Étale cohomology, Princeton Mathematical Series, vol. 33, Princeton University Press, Princeton, N.J., 1980. MR 559531 (81j:14002)
  • [Mul11] Ketan D. Mulmuley, On P vs. NP and geometric complexity theory, J. ACM 58 (2011), no. 2, Art. 5, 26. MR 2786586 (2012a:68094), https://doi.org/10.1145/1944345.1944346
  • [Per27] O. Perron, Algebra I (Die Grundlagen), W. de Gruyter, Berlin, 1927.
  • [Pło05] A. Płoski, Algebraic Dependence of Polynomials After O. Perron and Some Applications, Computational Commutative and Non-Commutative Algebraic Geometry, 2005, pp. 167-173.
  • [Rag69] R. Raghavendran, Finite associative rings, Compositio Math. 21 (1969), 195-229. MR 0246905 (40 #174)
  • [RS62] J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64-94. MR 0137689 (25 #1139)
  • [Sat00] 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 (2001j:11049)
  • [Sax09] Nitin Saxena, Progress on polynomial identity testing, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 99 (2009), 49-79. MR 2589248 (2011d:68070)
  • [Sch80] J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), no. 4, 701-717. MR 594695 (82m:68078), https://doi.org/10.1145/322217.322225
  • [Ser79] Jean-Pierre Serre, Local fields, Graduate Texts in Mathematics, vol. 67, Springer-Verlag, New York, 1979. Translated from the French by Marvin Jay Greenberg. MR 554237 (82e:12016)
  • [Sin80] 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 (82k:10008)
  • [SS95] Michael Shub and Steve Smale, On the intractability of Hilbert's Nullstellensatz and an algebraic version of `` $ {\rm NP}\not ={\rm P}$?'', Duke Math. J. 81 (1995), no. 1, 47-54 (1996). A celebration of John F. Nash, Jr. MR 1381969 (97h:03067), https://doi.org/10.1215/S0012-7094-95-08105-8
  • [SY10] 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 (2011m:68089), https://doi.org/10.1561/0400000039
  • [Val79] L. G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979), no. 2, 189-201. MR 526203 (80f:68054), https://doi.org/10.1016/0304-3975(79)90044-6
  • [Wan03] Zhe-Xian Wan, Lectures on finite fields and Galois rings, World Scientific Publishing Co. Inc., River Edge, NJ, 2003. MR 2008834 (2004h:11101)
  • [Wit36] E. Witt, Zyklische Körper und Algebren der Characteristik $ p$ vom Grade $ p^n$, J. Reine Angew. Math. (1936), no. 176, 126-140.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 12Y05, 13N05, 14F30, 03D15, 68Q17, 68W30

Retrieve articles in all journals with MSC (2010): 12Y05, 13N05, 14F30, 03D15, 68Q17, 68W30


Additional Information

Johannes Mittmann
Affiliation: Hausdorff Center for Mathematics, Endenicher Allee 62, D-53115 Bonn, Germany
Email: johannes.mittmann@hcm.uni-bonn.de

Nitin Saxena
Affiliation: Department of Computer Science & Engineering, IIT Kanpur, 208016 Kanpur, India
Email: nitin@cse.iitk.ac.in

Peter Scheiblechner
Affiliation: Hochschule Luzern - Technik & Architektur, Technikumstrasse 21, CH-6048 Horw, Switzerland
Email: peter.scheiblechner@hslu.ch

DOI: https://doi.org/10.1090/S0002-9947-2014-06268-5
Keywords: Algebraic independence, crystalline cohomology, de Rham, differential, finite field, Galois ring, identity testing, Jacobian, K\"ahler, $p$-adic, Teichm\"uller, Witt, zeta function
Received by editor(s): May 14, 2012
Published electronically: March 14, 2014
Article copyright: © Copyright 2014 American Mathematical Society

American Mathematical Society