Automatic congruences for diagonals of rational functions
Journal de théorie des nombres de Bordeaux, Volume 27 (2015) no. 1, p. 245-288

In this paper we use the framework of automatic sequences to study combinatorial sequences modulo prime powers. Given a sequence whose generating function is the diagonal of a rational power series, we provide a method, based on work of Denef and Lipshitz, for computing a finite automaton for the sequence modulo p α , for all but finitely many primes p. This method gives completely automatic proofs of known results, establishes a number of new theorems for well-known sequences, and allows us to resolve some conjectures regarding the Apéry numbers. We also give a second method, which applies to an algebraic sequence modulo p α for all primes p, but is significantly slower. Finally, we show that a broad range of multidimensional sequences possess Lucas products modulo p.

Dans cet article nous utilisons le cadre de suites automatiques pour étudier des suites combinatoires modulo des puissances de nombres premiers. Etant donné une suite dont la série génératrice est la diagonale d’une fonction rationnelle, nous présentons une procédure, basée sur le travail de Denef et Lipshitz, pour calculer un automate fini pour la suite modulo p α , pour presque tout premier p. Cette méthode donne des preuves complètement automatiques de résultats connus, établit de nouveaux théorèmes pour des suites bien connues, et nous permet de résoudre quelques conjectures sur les nombres d’Apéry. Nous donnons une deuxième méthode, que nous pouvons appliquer à toute suite algébrique modulo p α pour chaque premier p, mais qui est nettement plus lente. Enfin, nous démontrons qu’un large éventail de suites multidimensionnelles possèdent des produits de Lucas modulo p.

DOI : https://doi.org/10.5802/jtnb.901
Classification:  11A07,  11B50,  11B85
@article{JTNB_2015__27_1_245_0,
     author = {Rowland, Eric and Yassawi, Reem},
     title = {Automatic congruences for diagonals of rational functions},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {27},
     number = {1},
     year = {2015},
     pages = {245-288},
     doi = {10.5802/jtnb.901},
     mrnumber = {3346972},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_2015__27_1_245_0}
}
Rowland, Eric; Yassawi, Reem. Automatic congruences for diagonals of rational functions. Journal de théorie des nombres de Bordeaux, Volume 27 (2015) no. 1, pp. 245-288. doi : 10.5802/jtnb.901. http://www.numdam.org/item/JTNB_2015__27_1_245_0/

[AB12] B. Adamczewski and J. P. Bell, On vanishing coefficients of algebraic power series over fields of positive characteristic, Inventiones Mathematicae, 187, (2), (2012), 343–393. | MR 2885622 | Zbl 1257.11027

[AB13] B. Adamczewski and J. P. Bell, Diagonalization and rationalization of algebraic Laurent series, Annales Scientifiques de l’École Normale Supérieure, 46,(6), (2013), 963–1004. | MR 3134685

[AK73] R. Alter and K. K. Kubota, Prime and prime power divisibility of Catalan numbers, Journal of Combinatorial Theory, Series A, 15,(3), (1973), 243–256. | MR 325520 | Zbl 0273.10010

[ARS09] J.-P. Allouche, N. Rampersad and J. Shallit, Periodicity, repetitions, and orbits of an automatic sequence, Theoretical Computer Science, 410,(30–32), (2009), 2795–2803. | MR 2543333 | Zbl 1173.68044

[AS92] J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Science, 98,(2), (1992), 163–197. | MR 1166363 | Zbl 0774.68072

[AS03] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, Cambridge, (2003). | MR 1997038 | Zbl 1086.11015

[Atk98] M. D. Atkinson, Permutations which are the union of an increasing and a decreasing subsequence, The Electronic Journal of Combinatorics, 5:#R6, (1998). | MR 1490467 | Zbl 0885.05011

[Beu95] F. Beukers, Consequences of Apéry’s work on ζ(3), Rencontres Arithmétiques de Caen, (1995).

[Bón98] M. Bóna, The permutation classes equinumerous to the smooth class, The Electronic Journal of Combinatorics, 5:#R31, (1998). | MR 1626487 | Zbl 0899.05001

[CCC80] S. Chowla, J. Cowles and M. Cowles, Congruence properties of Apéry numbers, Journal of Number Theory, 12,(2), (1980), 188–190. | MR 578810 | Zbl 0428.10008

[Chr74] G. Christol, Éléments analytiques uniformes et multiformes, Séminaire Delange-Pisot-Poitou. Théorie des nombres, 1,(15), (1973-1974), 1–18. | Numdam | Zbl 0328.12013

[CKMFR80] G. Christol, T. Kamae, M. Mendès France and G. Rauzy, Suites algébriques, automates et substitutions, Bulletin de la Société Mathématique de France, 108,(4), (1980), 401–419. | Numdam | MR 614317 | Zbl 0472.10035

[Del13] E. Delaygue, Arithmetic properties of Apéry-like numbers, (2013). http://arxiv.org/abs/1310.4131.

[DL87] J. Denef and L. Lipshitz, Algebraic power series and diagonals, Journal of Number Theory, 26,(1), (1987), 46–67. | MR 883533 | Zbl 0609.12020

[DS06] E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, Journal of Number Theory, 117, (1), (2006), 191–215. | MR 2204742 | Zbl 1163.11310

[DW90] K. S. Davis and W. A. Webb, Lucas’ theorem for prime powers, European Journal of Combinatorics, 11, (3), (1990), 229–233. | MR 1059553 | Zbl 0704.11002

[Eil74] S. Eilenberg, Automata, languages, and machines. Vol. A, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York, 1974, Pure and Applied Mathematics, 58. | MR 530382 | Zbl 0317.94045

[ELY08] S.-P. Eu, S.-C. Liu and Y.-N. Yeh, Catalan and Motzkin numbers modulo 4 and 8, European Journal of Combinatorics, 29, (6), (2008), 1449–1466. | MR 2423733 | Zbl 1149.11008

[Fur67] H. Furstenberg, Algebraic functions over finite fields, Journal of Algebra, 7, (1967), 271–277. | MR 215820 | Zbl 0175.03903

[Ges82] I. Gessel, Some congruences for Apéry numbers, Journal of Number Theory, 14,(3), (1982), 362–368. | MR 660381 | Zbl 0482.10003

[Gra97] A. Granville, Arithmetic properties of binomial coefficients. I. Binomial coefficients modulo prime powers, in Organic Mathematics Burnaby, BC, CMS Conf. Proc. 20, (1995), 253–276. Amer. Math. Soc., Providence, RI, 1997. | MR 1483922 | Zbl 0903.11005

[KKM12] M. Kauers, C. Krattenthaler and T. W. Müller, A method for determining the mod-2 k behaviour of recursive sequences, with applications to subgroup counting, The Electronic Journal of Combinatorics, 18, (2),#P37, (2012). | Zbl 1260.05008

[KM13] C. Krattenthaler and T. W. Müller, A method for determining the mod-3 k behaviour of recursive sequences, (2013), http://arxiv.org/abs/1308.2856.

[KM15] C. Krattenthaler and T. W. Müller, Generalised Apéry numbers modulo 9, Journal of Number Theory, 147, (2015), 708–720. | MR 3276349 | Zbl 1302.05008

[Le05] I. Le, Wilf classes of pairs of permutations of length 4, The Electronic Journal of Combinatorics, 12,#R25, (2005). | MR 2156679 | Zbl 1081.05002

[Lin12] H.-Y. Lin, Odd Catalan numbers modulo 2 k , Integers, 12, (2), (2012), 161–165. | MR 2955673 | Zbl 1251.11010

[LY10] S.-C. Liu and J.-C. Yeh, Catalan numbers modulo 2 k , Journal of Integer Sequences, 13, (2010), Article 10.5.4. | MR 2647167 | Zbl 1230.05013

[Noe06] T. D. Noe, On the divisibility of generalized central trinomial coefficients, Journal of Integer Sequences, 9, (2), (2006), Article 06.2.7, 12. | MR 2247938 | Zbl 1102.05009

[Pet03] M. Peter, The asymptotic distribution of elements in automatic sequences, Theoretical Computer Science, 301, (1-3), (2003), 285–312. | MR 1975230 | Zbl 1028.68081

[Row10] E. Rowland, Pattern avoidance in binary trees, Journal of Combinatorial Theory, Series A, 117, (6), (2010), 741–758. | MR 2645188 | Zbl 1221.05058

[RY12] E. Rowland and R. Yassawi, A characterization of p-automatic sequences as columns of linear cellular automata, Adv. in Applied Math. 63, (2015) 68–89. | MR 3283830

[RZ14] E. Rowland and D. Zeilberger, A case study in meta-automation: automatic generation of congruence automata for combinatorial sequences, Journal of Difference Equations and Applications, 20, (2014), 973–988. | MR 3210325

[Sal87] O. Salon, Suites automatiques à multi-indices et algébricité, Comptes Rendus des Séances de l’Académie des Sciences, Série I. Mathématique, 305, (12), (1987), 501–504. | MR 916320 | Zbl 0628.10007

[Slo] N. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[Str14] A. Straub, Multivariate Apéry numbers and supercongruences of rational functions, Algebra & Number Theory 8, (2014) 1985–2008. | MR 3285621

[SvS09] K. Samol and D. van Straten, Dwork congruences and reflexive polytopes, (2009). http://arxiv.org/abs/0911.0797. | MR 2665001

[XX11] G. Xin and J.-F. Xu, A short approach to Catalan numbers modulo 2 r , The Electronic Journal of Combinatorics, 18:#P177, (2011). | MR 2836812 | Zbl 1234.05018