Algebraic solutions of linear differential equations: An arithmetic approach

Bostan, Alin; Caruso, Xavier; Roques, Julien

doi:10.1090/bull/1835

Algebraic solutions of linear differential equations: An arithmetic approach
HTML articles powered by AMS MathViewer

by Alin Bostan, Xavier Caruso and Julien Roques;

Bull. Amer. Math. Soc. 61 (2024), 609-658

DOI: https://doi.org/10.1090/bull/1835

Published electronically: August 15, 2024

HTML | PDF

Abstract:

Given a linear differential equation with coefficients in $\mathbb {Q}(x)$, an important question is to know whether its full space of solutions consists of algebraic functions, or at least if one of its specific solutions is algebraic. After presenting motivating examples coming from various branches of mathematics, we advertise in an elementary way a beautiful local-global arithmetic approach to these questions, initiated by Grothendieck in the late sixties. This approach has deep ramifications and leads to the still unsolved Grothendieck–Katz $p$-curvature conjecture.

References

Boris Adamczewski and Tanguy Rivoal, Exceptional values of $E$-functions at algebraic points, Bull. Lond. Math. Soc. 50 (2018), no. 4, 697–708. MR 3870952, DOI 10.1112/blms.12168
Gert Almkvist and Doron Zeilberger, The method of differentiating under the integral sign, J. Symbolic Comput. 10 (1990), no. 6, 571–591. MR 1087980, DOI 10.1016/S0747-7171(08)80159-9
Yves André, Quatre descriptions des groupes de Galois différentiels, Séminaire d’algèbre Paul Dubreil et Marie-Paule Malliavin (Paris, 1986) Lecture Notes in Math., vol. 1296, Springer, Berlin, 1987, pp. 28–41 (French). MR 932051, DOI 10.1007/BFb0078522
Yves André, $G$-functions and geometry, Aspects of Mathematics, E13, Friedr. Vieweg & Sohn, Braunschweig, 1989. MR 990016, DOI 10.1007/978-3-663-14108-2
Y. André. Sur la conjecture des $p$-courbures de Grothendieck-Katz et un problème de Dwork. In Geometric aspects of Dwork theory. Vol. I, II, pages 55–112. Walter de Gruyter, Berlin, 2004.
Vladimir G. Berkovich, Spectral theory and analytic geometry over non-Archimedean fields, Mathematical Surveys and Monographs, vol. 33, American Mathematical Society, Providence, RI, 1990. MR 1070709, DOI 10.1090/surv/033
E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853–1859. MR 219231, DOI 10.1002/j.1538-7305.1967.tb03174.x
Olivier Bernardi, Mireille Bousquet-Mélou, and Kilian Raschel, Counting quadrant walks via Tutte’s invariant method, Comb. Theory 1 (2021), Paper No. 3, 77. MR 4396208, DOI 10.5070/C61055360
Marco Bertola, Boris Dubrovin, and Di Yang, Simple Lie algebras and topological ODEs, Int. Math. Res. Not. IMRN 5 (2018), 1368–1410. MR 3801466, DOI 10.1093/imrn/rnw285
F. Beukers and G. Heckman, Monodromy for the hypergeometric function $_nF_{n-1}$, Invent. Math. 95 (1989), no. 2, 325–354. MR 974906, DOI 10.1007/BF01393900
Jean-Paul Bézivin, Les suites $q$-récurrentes linéaires, Compositio Math. 80 (1991), no. 3, 285–307 (French). MR 1134257
Jean-Benoît Bost, Algebraic leaves of algebraic foliations over number fields, Publ. Math. Inst. Hautes Études Sci. 93 (2001), 161–221 (English, with English and French summaries). MR 1863738, DOI 10.1007/s10240-001-8191-3
Alin Bostan, Computer algebra in the service of enumerative combinatorics, ISSAC ’21—Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation, ACM, New York, [2021] ©2021, pp. 1–8. MR 4398758, DOI 10.1145/3452143.3465507
Alin Bostan, Xavier Caruso, and Éric Schost, A fast algorithm for computing the characteristic polynomial of the p-curvature, ISSAC 2014—Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2014, pp. 59–66. MR 3239909, DOI 10.1145/2608628.2608650
Alin Bostan, Xavier Caruso, and Éric Schost, A fast algorithm for computing the $p$-curvature, ISSAC’15—Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2015, pp. 69–76. MR 3388284
Alin Bostan, Xavier Caruso, and Éric Schost, Computation of the similarity class of the $p$-curvature, Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2016, pp. 111–118. MR 3565704, DOI 10.1145/2930889.2930897
A. Bostan, F. Chyzak, F. Ollivier, B. Salvy, É. Schost, and A. Sedoglavic, Fast computation of power series solutions of systems of differential equations, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2007, pp. 1012–1021. MR 2485252
Alin Bostan, Frédéric Chyzak, Mark van Hoeij, Manuel Kauers, and Lucien Pech, Hypergeometric expressions for generating functions of walks with small steps in the quarter plane, European J. Combin. 61 (2017), 242–275. MR 3588720, DOI 10.1016/j.ejc.2016.10.010
Alin Bostan and Manuel Kauers, The complete generating function for Gessel walks is algebraic, Proc. Amer. Math. Soc. 138 (2010), no. 9, 3063–3078. With an appendix by Mark van Hoeij. MR 2653931, DOI 10.1090/S0002-9939-2010-10398-2
A. Bostan, I. Kurkova, and K. Raschel, A human proof of Gessel’s lattice path conjecture, Trans. Amer. Math. Soc. 369 (2017), no. 2, 1365–1393. MR 3572277, DOI 10.1090/tran/6804
Alin Bostan, Tanguy Rivoal, and Bruno Salvy, Minimization of differential equations and algebraic values of $E$-functions, Math. Comp. 93 (2024), no. 347, 1427–1472. MR 4709207, DOI 10.1090/mcom/3912
A. Bostan, B. Salvy, and M. Singer, On deciding transcendence of power series, In preparation.
Alin Bostan and Éric Schost, Fast algorithms for differential equations in positive characteristic, ISSAC 2009—Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2009, pp. 47–54. MR 2742690, DOI 10.1145/1576702.1576712
Alin Bostan and Sergey Yurkevich, On a class of hypergeometric diagonals, Proc. Amer. Math. Soc. 150 (2022), no. 3, 1071–1087. MR 4375704, DOI 10.1090/proc/15693
Mireille Bousquet-Mélou, Rational and algebraic series in combinatorial enumeration, International Congress of Mathematicians. Vol. III, Eur. Math. Soc., Zürich, 2006, pp. 789–826. MR 2275707
Mireille Bousquet-Mélou, An elementary solution of Gessel’s walks in the quadrant, Adv. Math. 303 (2016), 1171–1189. MR 3552547, DOI 10.1016/j.aim.2016.08.038
Mireille Bousquet-Mélou and Marni Mishna, Walks with small steps in the quarter plane, Algorithmic probability and combinatorics, Contemp. Math., vol. 520, Amer. Math. Soc., Providence, RI, 2010, pp. 1–39. MR 2681853, DOI 10.1090/conm/520/10252
Timothy Budd, Winding of simple walks on the square lattice, J. Combin. Theory Ser. A 172 (2020), 105191, 59. MR 4046317, DOI 10.1016/j.jcta.2019.105191
Antoine Chambert-Loir, Théorèmes d’algébricité en géométrie diophantienne (d’après J.-B. Bost, Y. André, D. & G. Chudnovsky), Astérisque 282 (2002), Exp. No. 886, viii, 175–209 (French, with French summary). Séminaire Bourbaki, Vol. 2000/2001. MR 1975179
G. Christol. Fonctions hypergéométriques bornées. Groupe de travail d’analyse ultramétrique, 14, 1986-1987. Talk:8.
Gilles Christol, Diagonales de fractions rationnelles, Séminaire de Théorie des Nombres, Paris 1986–87, Progr. Math., vol. 75, Birkhäuser Boston, Boston, MA, 1988, pp. 65–90 (French). MR 990506
Gilles Christol, Globally bounded solutions of differential equations, Analytic number theory (Tokyo, 1988) Lecture Notes in Math., vol. 1434, Springer, Berlin, 1990, pp. 45–64. MR 1071744, DOI 10.1007/BFb0097124
G. Christol and B. Dwork, Modules différentiels sur des couronnes, Ann. Inst. Fourier (Grenoble) 44 (1994), no. 3, 663–701 (French, with English and French summaries). MR 1303881, DOI 10.5802/aif.1414
G. Christol, Solutions algébriques des équations différentielles $p$-adiques, Seminar on number theory, Paris 1981–82 (Paris, 1981/1982) Progr. Math., vol. 38, Birkhäuser Boston, Boston, MA, 1983, pp. 51–58 (French). MR 729159
D. V. Chudnovsky and G. V. Chudnovsky, Applications of Padé approximations to the Grothendieck conjecture on linear differential equations, Number theory (New York, 1983–84) Lecture Notes in Math., vol. 1135, Springer, Berlin, 1985, pp. 52–100. MR 803350, DOI 10.1007/BFb0074601
Olivier Cormier, Michael F. Singer, Barry M. Trager, and Felix Ulmer, Linear differential operators for polynomial equations, J. Symbolic Comput. 34 (2002), no. 5, 355–398. MR 1937466, DOI 10.1006/jsco.2002.0564
Lucia Di Vizio, Arithmetic theory of $q$-difference equations: the $q$-analogue of Grothendieck-Katz’s conjecture on $p$-curvatures, Invent. Math. 150 (2002), no. 3, 517–578. MR 1946552, DOI 10.1007/s00222-002-0241-z
Thomas Dreyfus, Charlotte Hardouin, Julien Roques, and Michael F. Singer, On the nature of the generating series of walks in the quarter plane, Invent. Math. 213 (2018), no. 1, 139–203. MR 3815564, DOI 10.1007/s00222-018-0787-z
Ran Duan, Hongxun Wu, and Renfei Zhou, Faster matrix multiplication via asymmetric hashing, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science—FOCS 2023, IEEE Computer Soc., Los Alamitos, CA, [2023] ©2023, pp. 2129–2138. MR 4720372, DOI 10.1109/FOCS57990.2023.00130
Boris Dubrovin, Di Yang, and Don Zagier, Geometry and arithmetic of integrable hierarchies of KdV type. I. Integrality, Adv. Math. 433 (2023), Paper No. 109311, 73. MR 4650621, DOI 10.1016/j.aim.2023.109311
Bernard Dwork, Differential operators with nilpotent $p$-curvature, Amer. J. Math. 112 (1990), no. 5, 749–786. MR 1073008, DOI 10.2307/2374806
A. Errera. Zahlentheoretische Lösung einer functionentheoretischen Frage. Rend. Circ. Mat. Palermo, 35:107–144, 1913.
L. Euler, Specimen de constructione aequationum differentialium sime indeterminatarum separatione, Commentarii academiae scientiarum Petropolitanae, 6:168–174. 1733.
Benson Farb and Mark Kisin, Rigidity, locally symmetric varieties, and the Grothendieck-Katz conjecture, Int. Math. Res. Not. IMRN 22 (2009), 4159–4167. MR 2552299, DOI 10.1093/imrn/rnp082
Guy Fayolle, Roudolf Iasnogorodski, and Vadim Malyshev, Random walks in the quarter-plane, Applications of Mathematics (New York), vol. 40, Springer-Verlag, Berlin, 1999. Algebraic methods, boundary value problems and applications. MR 1691900, DOI 10.1007/978-3-642-60001-2
Philippe Flajolet, Analytic models and ambiguity of context-free languages, Theoret. Comput. Sci. 49 (1987), no. 2-3, 283–309. Twelfth international colloquium on automata, languages and programming (Nafplion, 1985). MR 909335, DOI 10.1016/0304-3975(87)90011-9
Philippe Flajolet and Robert Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009. MR 2483235, DOI 10.1017/CBO9780511801655
François Foucault, Équations de Picard-Fuchs et invariants des courbes de genre $2$, C. R. Acad. Sci. Paris Sér. I Math. 314 (1992), no. 8, 617–619 (French, with English summary). MR 1158748
François Foucault and Philippe Toffin, Courbes hyperelliptiques de genre trois et application de Kodaira-Spencer, C. R. Math. Acad. Sci. Paris 345 (2007), no. 12, 685–687 (French, with English and French summaries). MR 2376639, DOI 10.1016/j.crma.2007.10.030
F. Fürnsinn and H. Hauser, Fuchs’ theorem on linear differential equations in arbitrary characteristic, Preprint, arXiv:2307.01712, (2023).
F. Fürnsinn and S. Yurkevich, Algebraicity of hypergeometric functions with arbitrary parameters, Bull. Lond. Math. Soc., 23 pages, in print, https://doi.org/10.1112/blms.13103 (2024).
Harry Furstenberg, Algebraic functions over finite fields, J. Algebra 7 (1967), 271–277. MR 215820, DOI 10.1016/0021-8693(67)90061-0
Taira Honda, Algebraic differential equations, Symposia Mathematica, Vol. XXIV (Sympos., INDAM, Rome, 1979) Academic Press, London-New York, 1981, pp. 169–204. MR 619247
Nathan Jacobson, Abstract derivation and Lie algebras, Trans. Amer. Math. Soc. 42 (1937), no. 2, 206–224. MR 1501922, DOI 10.1090/S0002-9947-1937-1501922-7
Nicholas M. Katz, A conjecture in the arithmetic theory of differential equations, Bull. Soc. Math. France 110 (1982), no. 2, 203–239 (English, with French summary). MR 667751, DOI 10.24033/bsmf.1960
Nicholas M. Katz, Algebraic solutions of differential equations ($p$-curvature and the Hodge filtration), Invent. Math. 18 (1972), 1–118. MR 337959, DOI 10.1007/BF01389714
Nicholas M. Katz, Exponential sums and differential equations, Annals of Mathematics Studies, vol. 124, Princeton University Press, Princeton, NJ, 1990. MR 1081536, DOI 10.1515/9781400882434
Manuel Kauers, Christoph Koutschan, and Doron Zeilberger, Proof of Ira Gessel’s lattice path conjecture, Proc. Natl. Acad. Sci. USA 106 (2009), no. 28, 11502–11505. MR 2538821, DOI 10.1073/pnas.0901678106
Kiran S. Kedlaya, Local monodromy of $p$-adic differential equations: an overview, Int. J. Number Theory 1 (2005), no. 1, 109–154. MR 2172335, DOI 10.1142/S179304210500008X
Kiran S. Kedlaya, $p$-adic differential equations, Cambridge Studies in Advanced Mathematics, vol. 125, Cambridge University Press, Cambridge, 2010. MR 2663480, DOI 10.1017/CBO9780511750922
Richard Kelisky, The numbers generated by $\textrm {exp}(\textrm {arctan}$ $x)$, Duke Math. J. 26 (1959), 569–581. MR 109229
Jerald J. Kovacic, An algorithm for solving second order linear homogeneous differential equations, J. Symbolic Comput. 2 (1986), no. 1, 3–43. MR 839134, DOI 10.1016/S0747-7171(86)80010-4
J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London-New York, 1977, pp. 409–464. MR 447191
Edmund Landau, Eine Anwendung des Eisensteinschen Satzes auf die Theorie der Gaussschen Differentialgleichung, J. Reine Angew. Math. 127 (1904), 92–102 (German). MR 1580634, DOI 10.1515/crll.1904.127.92
E. Landau. Über einen zahlentheoretischen Satz und seine Anwendung auf die hypergeometrische Reihe. Sitzungsber. Heidelb. Akad. Wiss. Math.-Natur. Kl., 18:3–38, 1911.
L. Lipshitz, The diagonal of a $D$-finite power series is $D$-finite, J. Algebra 113 (1988), no. 2, 373–378. MR 929767, DOI 10.1016/0021-8693(88)90166-4
Stephen Melczer, An invitation to analytic combinatorics—from one to several variables, Texts and Monographs in Symbolic Computation, Springer, Cham, [2021] ©2021. With a foreword by Robin Pemantle and Mark Wilson. MR 4241372, DOI 10.1007/978-3-030-67080-1
Harald Niederreiter, A new efficient factorization algorithm for polynomials over small finite fields, Appl. Algebra Engrg. Comm. Comput. 4 (1993), no. 2, 81–87. MR 1223850, DOI 10.1007/BF01386831
Pierre Deligne, James S. Milne, Arthur Ogus, and Kuang-yen Shih, Hodge cycles, motives, and Shimura varieties, Lecture Notes in Mathematics, vol. 900, Springer-Verlag, Berlin-New York, 1982. MR 654325, DOI 10.1007/978-3-540-38955-2
Raphaël Pagès, Computing characteristic polynomials of $p$-curvatures in average polynomial time, ISSAC ’21—Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation, ACM, New York, [2021] ©2021, pp. 329–336. MR 4398801, DOI 10.1145/3452143.3465524
Anand Patel, Ananth N. Shankar, and Junho Peter Whang, The rank two $p$-curvature conjecture on generic curves, Adv. Math. 386 (2021), Paper No. 107800, 33. MR 4270046, DOI 10.1016/j.aim.2021.107800
Jérôme Poineau, La droite de Berkovich sur $\mathbf Z$, Astérisque 334 (2010), viii+xii+284 (French, with English and French summaries). MR 2759805
G. Pólya, Sur les séries entières, dont la somme est une fonction algébrique, Enseign. Math., 22:38–47, 1921/1922.
E. G. C. Poole, Introduction to the theory of linear differential equations, Dover Publications, Inc., New York, 1960. MR 111886
Alain M. Robert, A course in $p$-adic analysis, Graduate Texts in Mathematics, vol. 198, Springer-Verlag, New York, 2000. MR 1760253, DOI 10.1007/978-1-4757-3254-2
H. A. Schwarz, Ueber diejenigen Fälle, in welchen die Gaussische hypergeometrische Reihe eine algebraische Function ihres vierten Elementes darstellt, J. Reine Angew. Math. 75 (1873), 292–335 (German). MR 1579568, DOI 10.1515/crll.1873.75.292
Jean-Pierre Serre, Quelques applications du théorème de densité de Chebotarev, Inst. Hautes Études Sci. Publ. Math. 54 (1981), 323–401 (French). MR 644559
Jean-Pierre Serre, On a theorem of Jordan, Bull. Amer. Math. Soc. (N.S.) 40 (2003), no. 4, 429–440. MR 1997347, DOI 10.1090/S0273-0979-03-00992-3
Ananth N. Shankar, The $p$-curvature conjecture and monodromy around simple closed loops, Duke Math. J. 167 (2018), no. 10, 1951–1980. MR 3827814, DOI 10.1215/00127094-2018-0008
Michael F. Singer, Algebraic solutions of $n$th order linear differential equations, Proceedings of the Queen’s Number Theory Conference, 1979 (Kingston, Ont., 1979) Queen’s Papers in Pure and Appl. Math., vol. 54, Queen’s Univ., Kingston, ON, 1980, pp. 379–420. MR 634699
Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354–356. MR 248973, DOI 10.1007/BF02165411
E. Stridsberg. Sur le théorème d’Eisenstein et l’équation différentielle de Gauss. Ark. Mat. Astron. Fys., 6(35):1–17, 1911.
Yunqing Tang, Algebraic solutions of differential equations over $\Bbb P^1-\{0,1,\infty \}$, Int. J. Number Theory 14 (2018), no. 5, 1427–1457. MR 3806314, DOI 10.1142/S1793042118500884
Marius van der Put, Reduction modulo $p$ of differential equations, Indag. Math. (N.S.) 7 (1996), no. 3, 367–387. MR 1621401, DOI 10.1016/0019-3577(96)83726-8
Marius van der Put, Grothendieck’s conjecture for the Risch equation $y’=ay+b$, Indag. Math. (N.S.) 12 (2001), no. 1, 113–124. MR 1908143, DOI 10.1016/S0019-3577(01)80009-4
Marius van der Put and Michael F. Singer, Galois theory of linear differential equations, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 328, Springer-Verlag, Berlin, 2003. MR 1960772, DOI 10.1007/978-3-642-55750-7
Daniel Vargas-Montoya, Algébricité modulo $p$, séries hypergéométriques et structures de Frobenius fortes, Bull. Soc. Math. France 149 (2021), no. 3, 439–477 (French, with English and French summaries). MR 4349570, DOI 10.24033/bsmf.2834
S. Yurkevich. The art of algorithmic guessing in gfun. Maple Trans., 2(1):14421:1–14421:19, 2022.
Don Zagier, The arithmetic and topology of differential equations, European Congress of Mathematics, Eur. Math. Soc., Zürich, 2018, pp. 717–776. MR 3890449