Automatic congruences for diagonals of rational functions

Rowland, Eric and Yassawi, Reem (2015). Automatic congruences for diagonals of rational functions. Journal de Théorie des Nombres de Bordeaux, 27(1) pp. 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.

Viewing alternatives

Download history


Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions