Skip to main content

24.09.2023 | Original Paper

Fuchsian holonomic sequences

verfasst von: Joris van der Hoeven

Erschienen in: Applicable Algebra in Engineering, Communication and Computing

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Many sequences that arise in combinatorics and the analysis of algorithms turn out to be holonomic (note that some authors prefer the terminology D-finite). In this paper, we study various basic algorithmic problems for such sequences \((f_n)_{n \in {\mathbb {N}}}\): how to compute their asymptotics for large n? How to evaluate \(f_n\) efficiently for large n and/or large precisions p? How to decide whether \(f_n > 0\) for all n? We restrict our study to the case when the generating function \(f = \sum _{n \in {\mathbb {N}}} f_n z^n\) satisfies a Fuchsian differential equation (often it suffices that the dominant singularities of f be Fuchsian). Even in this special case, some of the above questions are related to long-standing problems in number theory. We will present algorithms that work in many cases and we carefully analyze what kind of oracles or conjectures are needed to tackle the more difficult cases.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Fußnoten
1
If f has no singularities in \({\mathbb {C}}\), then the assumption that f is Fuchsian at infinity implies that f is actually a polynomial. In what follows, we will discard this trivial case and assume that f has at least one singularity in \({\mathbb {C}}\).
 
2
The classical Mellin transform uses a straight integration path from \(z = 0\) to \(+ \infty \) instead of a Hankel contours around \(\alpha _k\). We will say that our Mellin integral is “based at \(\alpha _k\)”. The use of a Hankel contours extends the definition to the case when f is not integrable at \(\alpha _k\). In the context of difference equations, certain authors prefer the terminology “Laplace transform”, “Pincherle transform”, or “Nörlund transform” instead of “Mellin transform”.
 
Literatur
1.
Zurück zum Zitat van der Hoeven, J.: The Jolly Writer. Your Guide to GNU TeXmacs, Scypress (2020) van der Hoeven, J.: The Jolly Writer. Your Guide to GNU TeXmacs, Scypress (2020)
2.
3.
Zurück zum Zitat Flajolet, P., Sedgewick, R.: Analytic combinatorics. Cambridge University Press, Cambridge (2009)CrossRefMATH Flajolet, P., Sedgewick, R.: Analytic combinatorics. Cambridge University Press, Cambridge (2009)CrossRefMATH
4.
Zurück zum Zitat Kenison, G., Lipton, R., Ouaknine, J., Worrell, J.: On the Skolem problem and prime powers. In Proc. of the 45th Intern. Symp. on Symbolic and AlgebraicComputation, ISSAC ’20, pp. 289–296. ACM, (2020) Kenison, G., Lipton, R., Ouaknine, J., Worrell, J.: On the Skolem problem and prime powers. In Proc. of the 45th Intern. Symp. on Symbolic and AlgebraicComputation, ISSAC ’20, pp. 289–296. ACM, (2020)
5.
Zurück zum Zitat Nosan, K., Pouly, A., Shirmohammadi, M., Worrell, J.: The membership problem for hypergeometric sequences with rational parameters. In Proc. ISSAC ’22, pp. 381–389. (2022) Nosan, K., Pouly, A., Shirmohammadi, M., Worrell, J.: The membership problem for hypergeometric sequences with rational parameters. In Proc. ISSAC ’22, pp. 381–389. (2022)
7.
Zurück zum Zitat Chudnovsky, D. V., Chudnovsky, G. V.: Computer algebra in the service of mathematical physics and number theory (Computers in mathematics, Stanford, CA, 1986). In Lect. Notes in Pure and Applied Math., vol. 125, pp. 109–232. New-York, (1990) Chudnovsky, D. V., Chudnovsky, G. V.: Computer algebra in the service of mathematical physics and number theory (Computers in mathematics, Stanford, CA, 1986). In Lect. Notes in Pure and Applied Math., vol. 125, pp. 109–232. New-York, (1990)
9.
Zurück zum Zitat van der Hoeven, J.: Fast evaluation of holonomic functions near and in singularities. JSC 31, 717–743 (2001)MathSciNetMATH van der Hoeven, J.: Fast evaluation of holonomic functions near and in singularities. JSC 31, 717–743 (2001)MathSciNetMATH
10.
Zurück zum Zitat Mezzarobba, M.: Autour de l’évaluation numérique des fonctions D-finies. PhD thesis, École polytechnique, Palaiseau, France Mezzarobba, M.: Autour de l’évaluation numérique des fonctions D-finies. PhD thesis, École polytechnique, Palaiseau, France
12.
Zurück zum Zitat Dong, R.: Computing error bounds for asymptotic expansions of regular P-recursive sequences. Master’s thesis, École polytechnique,: Unpublished. Supervised by S. Melczer and M, Mezzarobba (2021) Dong, R.: Computing error bounds for asymptotic expansions of regular P-recursive sequences. Master’s thesis, École polytechnique,: Unpublished. Supervised by S. Melczer and M, Mezzarobba (2021)
14.
Zurück zum Zitat Gerhold, S., Kauers, M.: A procedure for proving special function inequalities involving a discrete parameter. In Proc. of the 2005 Intern.Symp. on Symbolicand AlgebraicComputation, ISSAC 2005, pp. 156–162. ACM, (2005) Gerhold, S., Kauers, M.: A procedure for proving special function inequalities involving a discrete parameter. In Proc. of the 2005 Intern.Symp. on Symbolicand AlgebraicComputation, ISSAC 2005, pp. 156–162. ACM, (2005)
15.
Zurück zum Zitat Kauers, M., Pillwein, V.: When can we detect that a p-finite sequence is positive? In Proc. of the 2010 Intern. Symp. on Symbolic and Algebraic Computation, ISSAC 2010, pp. 195–201. ACM, (2010) Kauers, M., Pillwein, V.: When can we detect that a p-finite sequence is positive? In Proc. of the 2010 Intern. Symp. on Symbolic and Algebraic Computation, ISSAC 2010, pp. 195–201. ACM, (2010)
16.
Zurück zum Zitat Pincherle, S.: Sur la génération de systèmes récurrents au moyen d’une équation linéaire différentielle. Acta Math. 16, 341–363 (1892)MathSciNetCrossRefMATH Pincherle, S.: Sur la génération de systèmes récurrents au moyen d’une équation linéaire différentielle. Acta Math. 16, 341–363 (1892)MathSciNetCrossRefMATH
17.
Zurück zum Zitat van der Hoeven, J.: On the computation of limsups. J. Pure Appl. Algebra 117(118), 381–394 (1996)MathSciNetMATH van der Hoeven, J.: On the computation of limsups. J. Pure Appl. Algebra 117(118), 381–394 (1996)MathSciNetMATH
18.
Zurück zum Zitat Nörlund, N.E.: Fractions continues et différences réciproques. Acta Math. 34, 1–108 (1910)CrossRefMATH Nörlund, N.E.: Fractions continues et différences réciproques. Acta Math. 34, 1–108 (1910)CrossRefMATH
19.
Zurück zum Zitat Galbrun, H.: Sur la représentation des solutions d’une équation linéaire aux différences finies pour les grandes valeurs de la variable. Acta Math. 36, 1–68 (1913)MathSciNetCrossRefMATH Galbrun, H.: Sur la représentation des solutions d’une équation linéaire aux différences finies pour les grandes valeurs de la variable. Acta Math. 36, 1–68 (1913)MathSciNetCrossRefMATH
20.
Zurück zum Zitat Nörlund, N.E.: Vorlesungen über Differenzenrechnung. Springer Verlag, Berlin (1924)CrossRefMATH Nörlund, N.E.: Vorlesungen über Differenzenrechnung. Springer Verlag, Berlin (1924)CrossRefMATH
21.
Zurück zum Zitat Galbrun, H.: Sur certaines solutions exceptionnelles d’une équation linéaire aux différences finies. Bull. S.M.F. 49, 206–241 (1921)MathSciNetMATH Galbrun, H.: Sur certaines solutions exceptionnelles d’une équation linéaire aux différences finies. Bull. S.M.F. 49, 206–241 (1921)MathSciNetMATH
22.
Zurück zum Zitat Duval, A.: Équations aux différences dans le champ complexe. PhD thesis, IRMA, Strasbourg, France, (1984) Duval, A.: Équations aux différences dans le champ complexe. PhD thesis, IRMA, Strasbourg, France, (1984)
23.
Zurück zum Zitat Barkatou, M.A.: Contributions à l’étude d’équations différentielleset aux différencesdans le champ complexe. PhD thesis, Institut National Polytechnique de Grenoble, (1989) Barkatou, M.A.: Contributions à l’étude d’équations différentielleset aux différencesdans le champ complexe. PhD thesis, Institut National Polytechnique de Grenoble, (1989)
24.
Zurück zum Zitat Immink, G.K.: On the relation between global properties of linear difference and differential equations with polynomial coefficients. I. J. Diff. Eq. 113, 201–233 (1994)MathSciNetCrossRefMATH Immink, G.K.: On the relation between global properties of linear difference and differential equations with polynomial coefficients. I. J. Diff. Eq. 113, 201–233 (1994)MathSciNetCrossRefMATH
25.
Zurück zum Zitat Immink, G.K.: On the relation between global properties of linear difference and differential equations with polynomial coefficients. II. J. Diff. Eq. 128, 168–205 (1996)MathSciNetCrossRefMATH Immink, G.K.: On the relation between global properties of linear difference and differential equations with polynomial coefficients. II. J. Diff. Eq. 128, 168–205 (1996)MathSciNetCrossRefMATH
26.
Zurück zum Zitat Immink, G.K.: On the relation between global properties of linear difference and differential equations with polynomial coefficients. Math. Nachr. 200, 59–76 (1999)MathSciNetCrossRefMATH Immink, G.K.: On the relation between global properties of linear difference and differential equations with polynomial coefficients. Math. Nachr. 200, 59–76 (1999)MathSciNetCrossRefMATH
27.
Zurück zum Zitat Fuchs, L.: Zur Theorie der Linearen Differentialgleichungen mit veränderlichen Coefficienten. J. für die reine une angewandte Math. 66(2), 121–160 (1866)MATH Fuchs, L.: Zur Theorie der Linearen Differentialgleichungen mit veränderlichen Coefficienten. J. für die reine une angewandte Math. 66(2), 121–160 (1866)MATH
28.
Zurück zum Zitat van der Put, M., Singer, M.: Galois Theory of Linear Differential Equations, volume 328 of Grundlehren der mathematischen Wissenschaften. Springer, (2003) van der Put, M., Singer, M.: Galois Theory of Linear Differential Equations, volume 328 of Grundlehren der mathematischen Wissenschaften. Springer, (2003)
31.
Zurück zum Zitat Whittaker, E.T., Watson, G.N.: A Course of Modern Analysis, 4th edn. Cambridge University Press, Cambridge (1996)CrossRefMATH Whittaker, E.T., Watson, G.N.: A Course of Modern Analysis, 4th edn. Cambridge University Press, Cambridge (1996)CrossRefMATH
32.
Zurück zum Zitat Th. Skolem. Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit anwendung auf diophantische Gleichungen. Oslo Vid. akad. Skrifter, 1(6), (1933) Th. Skolem. Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit anwendung auf diophantische Gleichungen. Oslo Vid. akad. Skrifter, 1(6), (1933)
33.
Zurück zum Zitat Mahler, K.: Eine arithmetische Eigenschaft der Taylor-koeffizienten rationaler Funktionen. Proc. Akad. Wetensch. Amsterdam 38, 50–60 (1935)MATH Mahler, K.: Eine arithmetische Eigenschaft der Taylor-koeffizienten rationaler Funktionen. Proc. Akad. Wetensch. Amsterdam 38, 50–60 (1935)MATH
35.
Zurück zum Zitat Berstel, J., Mignotte, M.: Deux propriétés décidables des suites récurrentes linéaires. Bull. de la S.M.F. 104, 175–184 (1976)MATH Berstel, J., Mignotte, M.: Deux propriétés décidables des suites récurrentes linéaires. Bull. de la S.M.F. 104, 175–184 (1976)MATH
36.
Zurück zum Zitat Ouaknine, J., Worrell, J.: Decision problems for linear recurrence sequences. In Reachability Problems: 6th International Workshop, RP 2012, volume 7550 of Lect.Notesin Comp. Science, pages 21–28. Bordeaux, France, September (2012). Springer-Verlag Ouaknine, J., Worrell, J.: Decision problems for linear recurrence sequences. In Reachability Problems: 6th International Workshop, RP 2012, volume 7550 of Lect.Notesin Comp. Science, pages 21–28. Bordeaux, France, September (2012). Springer-Verlag
37.
Zurück zum Zitat Rosser, J.B., Schoenfeld, L.: Approximate formulas for some functions of prime numbers. Illinois J. Math. 6(1), 64–94 (1962)MathSciNetCrossRefMATH Rosser, J.B., Schoenfeld, L.: Approximate formulas for some functions of prime numbers. Illinois J. Math. 6(1), 64–94 (1962)MathSciNetCrossRefMATH
38.
39.
Zurück zum Zitat Baker, A.: Linear forms in the logarithms of algebraic numbers (III). Mathematika 14(2), 220–228 (1967)CrossRefMATH Baker, A.: Linear forms in the logarithms of algebraic numbers (III). Mathematika 14(2), 220–228 (1967)CrossRefMATH
40.
Zurück zum Zitat van der Hoeven, J.: Zero-testing, witness conjectures and differential diophantine approximation. Technical Report 2001-62, Prépublications d’Orsay, (2001) van der Hoeven, J.: Zero-testing, witness conjectures and differential diophantine approximation. Technical Report 2001-62, Prépublications d’Orsay, (2001)
41.
44.
Zurück zum Zitat Bourbaki, N.: Fonctions d’une variable réelle. Éléments de Mathématiques (Chap. 5). Hermann, 2-nd edition, (1961) Bourbaki, N.: Fonctions d’une variable réelle. Éléments de Mathématiques (Chap. 5). Hermann, 2-nd edition, (1961)
45.
Zurück zum Zitat Basu, S., Pollack, R., Roy, M.-F.: Algorithms in real algebraic geometry, volume 10 of Algorithms and Computation in Mathematics. Springer-Verlag, 2-nd edition to appear (2006) Basu, S., Pollack, R., Roy, M.-F.: Algorithms in real algebraic geometry, volume 10 of Algorithms and Computation in Mathematics. Springer-Verlag, 2-nd edition to appear (2006)
49.
Zurück zum Zitat van der Hoeven, J.: Efficient accelero-summation of holonomic functions. JSC 42(4), 389–428 (2007)MathSciNetMATH van der Hoeven, J.: Efficient accelero-summation of holonomic functions. JSC 42(4), 389–428 (2007)MathSciNetMATH
Metadaten
Titel
Fuchsian holonomic sequences
verfasst von
Joris van der Hoeven
Publikationsdatum
24.09.2023
Verlag
Springer Berlin Heidelberg
Erschienen in
Applicable Algebra in Engineering, Communication and Computing
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-023-00616-4