Computations with $p$-adic numbers

Caruso, Xavier

Journées Nationales de Calcul Formel. 16 – 20 Janvier 2017, Les cours du CIRM, no. 1 (2017), Exposé no. 2, 75 p.

Ce texte est une version étendue des notes d’un cours que j’ai donné en janvier 2018 aux « Journées Nationales de Calcul Formel » (JNCF). Ce cours portait sur l’algorithmique sous-jacente à l’implémentation bas niveau des nombres $p$-adiques sur machine. Il est divisé en deux grandes parties : dans un premier temps, nous présentons et comparons divers paradigmes couramment utilisés pour implémenter les nombres $p$-adiques puis, dans un second temps, nous introduisons un cadre général permettant d’étudier la propagation de la précision dans le monde $p$-adique puis nous l’appliquons dans plusieurs situations concrètes.

This document contains the notes of a lecture I gave at the “Journées Nationales du Calcul Formel(French) National Computer Algebra Days” (JNCF) on January 2017. The aim of the lecture was to discuss low-level algorithmics for $p$-adic numbers. It is divided into two main parts: first, we present various implementations of $p$-adic numbers and compare them and second, we introduce a general framework for studying precision issues and apply it in several concrete situations.

[1] Jounaïdi Abdeljaoued and Henri Lombardi. Méthodes matricielles, introduction à la complexité algébrique. Springer Verlag, Berlin, Heidelberg (2004) | Zbl

[2] Yvette Amice. Les nombres p-adiques. PUF (1975) | Zbl

[3] Micheal Bartholomew-Biggs, Steven Brown, Bruce Christianson and Laurence Dixon. Automatic differentiation of algorithms. Journal of Comp. and App. Math. 124 (2000), 171–190 | DOI | MR | Zbl

[4] Christian Batut, Karim Belabas, Dominique Benardi, Henri Cohen and Michel Olivier. User’s guide to PARI-GP. (1985–2013).

[5] Laurent Berger. La correspondance de Langlands locale $p$-adique pour ${\text{GL}}_2\left({\mathbb{Q}}_p\right)$. Astérisque 339 (2011), 157–180 | Numdam | Zbl

[6] Pierre Berthelot and Arthur Ogus. Notes on Crystalline Cohomology. Princeton University Press (1978) | DOI | Zbl

[7] Jérémy Berthomieu, Joris van der Hoeven, and Grégoire Lecerf. Relaxed algorithms for $p$-adic numbers. J. Number Theor. Bordeaux 23 (2011), 541–577 | DOI | MR | Zbl

[8] Jérémy Berthomieu and Romain Lebreton. Relaxed $p$-adic Hensel lifting for algebraic systems. In ISSAC’12 (2012), 59–66 | DOI | Zbl

[9] Bhargav Bhatt. What is... a Perfectoid Space? Notices of the Amer. Math. Soc. 61 (2014), 1082–1084 | DOI | MR

[10] Richard Bird. A simple division-free algorithm for computing determinants. Information Processing Letters 111 (2011), 1072–1074 | DOI | MR | Zbl

[11] Wieb Bosma, John Cannon, and Catherine Payoust. The Magma algebra system. I. The user language. J. Symbolic Comput. 24 (1997), 235–265 | DOI | MR | Zbl

[12] Alin Bostan, Frédéric Chyzak, Grégoire Lecerf, Bruno Salvy and Éric Schost. Differential equations for algebraic functions. In ISSAC’07 (2007), 25–32 | DOI | Zbl

[13] Alin Bostan, Laureano González-Vega, Hervé Perdry and Éric Schost. From Newton sums to coefficients: complexity issues in characteristic $p$. In MEGA’05 (2005)

[14] Olivier Brinon and Brian Conrad. CMI Summer School notes on p-adic Hodge theory. Available at http://math.stanford.edu/~conrad/papers/notes.pdf (2009)

[15] Joe Buhler and Kiran Kedlaya. Condensation of determinants and the Robbins phenomenon. Microsoft Research Summer Number Theory Day, Redmond (2012), available at http://kskedlaya.org/slides/microsoft2012.pdf

[16] Xavier Caruso. Random matrices over a DVR and LU factorization. J. Symbolic Comput. 71 (2015), 98–123 | DOI | MR | Zbl

[17] Xavier Caruso. Numerical stability of Euclidean algorithm over ultrametric fields. to appear at J. Number Theor. Bordeaux | DOI | MR | Zbl

[18] Xavier Caruso, David Roe and Tristan Vaccon. Tracking $p$-adic precision. LMS J. Comp. and Math. 17 (2014), 274–294 | DOI | MR | Zbl

[19] Xavier Caruso, David Roe and Tristan Vaccon. $p$-adic stability in linear algebra. In ISSAC’15 (2015) | DOI | Zbl

[20] Xavier Caruso, David Roe and Tristan Vaccon. Characteristic polynomials of $p$-adic matrices. In preparation | DOI | Zbl

[21] Man-Duen Choi. Tricks or treats with the Hilbert matrix., Amer. Math. Monthly (1983), 301–312 | DOI | MR | Zbl

[22] John Coates. On $p$-adic $L$-functions. Astérisque 177 (1989), 33–59 | Numdam | Zbl

[23] Henri Cohen, A course in computational algebraic number theory, Springer Verlag, Berlin (1993) | Zbl

[24] Pierre Colmez. Integration sur les variétés $p$-adiques. Astérisque 248 (1998) | Numdam | Zbl

[25] Pierre Colmez, Fonctions d’une variable $p$-adique, Astérisque 330 (2010), 13–59 | Numdam | Zbl

[26] Marc Daumas, Jean-Michel Muller et al. Qualité des Calculs sur Ordinateur. Masson, Paris (1997)

[27] Roberto Dvornicich and Carlo Traverso. Newton symmetric functions and the arithmetic of algebraically closed fields. In AAECC-5, LNCS 356, Springer, Berlin (1989), 216–224 | DOI | MR | Zbl

[28] David Eisenbud. Commutative Algebra: with a view toward algebraic geometry. Springer Science & Business Media 150 (1995) | DOI | Zbl

[29] Sergey Fomin and Andrei Zelevinsky. The Laurent phenomenon. Advances in Applied Math. 28 (2002), 119–144 | DOI | MR | Zbl

[30] Martin Fürer. Faster integer multiplication. SIAM J. Comput. 39 (2009), 979–1005 | DOI | MR | Zbl

[31] Alexander Grothendieck et al. Séminaire de géométrie algébrique du Bois-Marie. (1971–1977)

[32] Pierrick Gaudry, Thomas Houtmann, Annegret Weng, Christophe Ritzenthaler and David Kohel. The $2$-adic CM method for genus $2$ curves with application to cryptography. In Asiacrypt 2006, LNCS 4284, 114–129 | DOI | Zbl

[33] Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra. Cambridge University Press, Cambridge (2003) | Zbl

[34] Fernando Gouvêa. Arithmetic of $p$-adic modular forms. Lecture Notes in Math. 1304, Springer-Verlag, Berlin, New-York (1988) | DOI | Zbl

[35] Fernando Gouvêa. $p$-adic Numbers: An Introduction. Springer (1997) | DOI | MR | Zbl

[36] Über eine neue Begründung der Theorie der algebraischen Zahlen. Jahresbericht der Deutschen Mathematiker-Vereinigung 6 (1897), 83–88 | Zbl

[37] James Hafner and Kevin McCurley. Asymptotically fast triangularization of matrices over rings. SIAM Journal of Comp. 20 (1991), 1068–1083 | DOI | MR | Zbl

[38] David Harari. Zéro-cycles et points rationnels sur les fibrations en variétés rationnellement connexes (d’après Harpaz et Wittenberg). Séminaire Bourbaki, Exp. 1096, Astérisque 380 (2016), 231–262

[39] Yonatan Harpaz and Olivier Wittenberg. On the fibration method for zero-cycles and rational points. Ann. of Math. 183 (2016), 229–295. | DOI | MR | Zbl

[40] David Harvey, Joris van der Hoeven and Grégoire Lecerf. Even faster integer multiplication. J. Complexity 36 (2015), 1–30 | DOI | MR | Zbl

[41] Francis Hilbebrand. Introduction to Numerical Analysis. McGraw-Hill, New York (1956)

[42] Joris van der Hoeven. Lazy multiplication of formal power series. In ISSAC’97 (1997), 17–20 | DOI | Zbl

[43] Joris van der Hoeven. Relax, but don’t be too lazy. J. Symbolic Comput. 34 (2002), 479–542 | DOI | MR | Zbl

[44] Joris van der Hoeven. New algorithms for relaxed multiplication. J. Symbolic Comput. 42 (2007), 792–802 | DOI | MR | Zbl

[45] Joris van der Hoeven, Grégoire Lecerf and Bernard Mourrain The Mathemagix Language, 2002–2012

[46] Alston Householder, The Theory of Matrices in Numerical Analysis. (1975) | Zbl

[47] IEEE Computer Society. IEEE Standard for Floating-Point Arithmetic, IEEE Standard 754-2008. IEEE Computer Society, New York (2008)

[48] Erich Kaltofen and Gilles Villard. On the complexity of computing determinants. Comp. Complexity 13 (2005), 91–130 | DOI | MR | Zbl

[49] Kiran Kedlaya. Counting points on hyperelliptic curves using Monsky–Washnitzer cohomology. J. Ramanujan Math. Soc. 16 (2001), 323–338 | MR | Zbl

[50] Kiran Kedlaya. $p$-adic Differential Equations. Cambridge University Press (2010) | DOI | Zbl

[51] Kiran Kedlaya and David Roe. Two specifications for $p$-adic floating-point arithmetic: a Sage enhancement proposal. Personal communication

[52] Neal Koblitz. $p$-adic Numbers, $p$-adic Analysis, and Zeta-Functions. Graduate Texts in Math. 58, Berlin, New York, Springer-Verlag (1984) | DOI

[53] Pierre Lairez and Tristan Vaccon, On $p$-adic differential equations with separation of variables. In ISSAC’16 (2016) | DOI | Zbl

[54] Alan Lauder. Deformation theory and the computation of zeta functions. Proc. London Math. Soc. 88 (2004), 565–602 | DOI | MR | Zbl

[55] Romain Lebreton. Relaxed Hensel lifting of triangular sets. In MEGA´13 (2013) | DOI | MR | Zbl

[56] Arjen Lenstra, Hendrik Lenstra and László Lovász. Factoring polynomials with rational coefficients. Math. Ann. 261 (1982), 515–534 | DOI | MR | Zbl

[57] Reynald Lercier and Thomas Sirvent. On Elkies subgroups of $\ell$-torsion points in elliptic curves defined over a finite field. J. Number Theor. Bordeaux 20 (2008), 783–797 | DOI | MR | Zbl

[58] Bernard Le Stum. Rigid cohomology. Cambridge University Press (2007) | DOI

[59] Carla Limongelli and Roberto Pirastu. Exact solution of linear systems over rational numbers by parallel $p$-adic arithmetic. In Parallel Processing: CONPAR 94-VAPP VI (1994), 313–323 | DOI

[60] Kurt Mahler. An interpolation series for continuous functions of a $p$-adic variable. J. reine und angew. Mathematik 199 (1958), 23–34 | DOI | MR | Zbl

[61] Yuri Manin. Le groupe de Brauer-Grothendieck en géométrie diophantienne. In Actes du Congrés International des Mathématiciens (Nice, 1970), Tome 1, Gauthier-Villars, Paris (1971), 401–411 | DOI

[62] Jean-Michel Muller. Arithmétique des ordinateurs. Masson, Paris (1989)

[63] Jean-Michel Muller et al. Handbook of floating-point arithmetic. Birkhauser, Boston (2009) | DOI

[64] Richard Neidinger, Introduction to Automatic Differentiation and MATLAB Object-Oriented Programming. SIAM Review 52 (2010), 545–563 | DOI | MR | Zbl

[65] Jurgen Neurkich. Algebraic Number Theory. Springer, Berlin, New York (1999)

[66] Jurgen Neurkich, Class Field Theory. The Bonn lectures. Edited by Alexander Schmidt. Springer, Berlin, London (2013)

[67] Alain Robert. A course in $p$-adic analysis. Springer Science & Business Media 198 (2000) | DOI | Zbl

[68] R. Tyrell Rockafellar. Variational Analysis. Grundlehren der Mathematischen Wissenschaften 317, Springer-Verlag (1997) | DOI

[69] Pierre Samuel. Algebraic theory of numbers. Paris, Hermann (1972)

[70] Peter Schneider. $p$-Adic Lie groups. Grundlehren der mathematischen Wissenschaften 344. Springer, Berlin (2011) | DOI

[71] Peter Scholze. Perfectoid spaces: A survey. Current Developments in Mathematics (2012) | DOI

[72] Peter Scholze. Perfectoid spaces and their Applications. Proceedings of the ICM 2014 (2014) | Zbl

[73] Arnold Schönhage, The fundamental theorem of algebra in terms of computational complexity. Technical report, Univ. Tübingen (1982)

[74] Jean-Pierre Serre. Corps locaux. Hermann Paris (1962)

[75] Jean-Pierre Serre. Cours d’arithmétique. PUF (1970) | Zbl

[76] Michael Somos. Problem 1470. Crux Mathematicorum 15 (1989), 208–208.

[77] William Stein et al. Sage Mathematics Software, The Sage Development Team, 2005–2017.

[78] Richard Taylor and Andrew Wiles. Ring theoretic properties of certain Hecke algebras. Ann. of Math. 141 (1995), 553–572 | DOI | MR | Zbl

[79] Tristan Vaccon. Précision $p$-adique. PhD Thesis (2015). Available at https://tel.archives-ouvertes.fr/tel-01205269

[80] André Weil. Numbers of solutions of equations in finite fields. Bull. Amer. Math. Soc. 55 (1949), 497–508 | DOI | MR | Zbl

[81] Andrew Wiles. Modular elliptic curves and Fermat’s Last Theorem. Ann. of Math. 141 (1995), 443–551 | DOI | MR | Zbl

[82] Franz Winkler. Polynomial Algorithms in Computer Algebra. Springer Wien New Work (1996) | DOI | MR | Zbl