Automatic congruences for diagonals of rational functions

Rowland, Eric; Yassawi, Reem

Journal de théorie des nombres de Bordeaux, Tome 27 (2015) no. 1, pp. 245-288.

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^{\alpha }$, 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^{\alpha }$ 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$.

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^{\alpha }$, 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^{\alpha }$ for all primes $p$, but is significantly slower. Finally, we show that a broad range of multidimensional sequences possess Lucas products modulo $p$.

[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 | Zbl

[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

[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 | Zbl

[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 | Zbl

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

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

[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 | Zbl

[Beu95] F. Beukers, Consequences of Apéry’s work on $\zeta \left(3\right)$, 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 | Zbl

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

[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

[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 | Zbl

[Del13] E. Delaygue, Arithmetic properties of Apéry-like numbers, (2013). | arXiv

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

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

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

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

[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 | Zbl

[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

[KM13] C. Krattenthaler and T. W. Müller, A method for determining the mod-3${}^k$ behaviour of recursive sequences, (2013), . | arXiv

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

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

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

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

[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 | Zbl

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

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

[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

[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

[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 | Zbl

[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

[SvS09] K. Samol and D. van Straten, Dwork congruences and reflexive polytopes, (2009). | arXiv | MR

[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 | Zbl