Automatic congruences for diagonals of rational functions

作者:Rowland Eric*; Yassawi Reevi
来源:Journal de Theorie des Nombres de Bordeaux, 2015, 27(1): 245-288.
DOI:10.5802/jtnb.901

摘要

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 pa, 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 Apery numbers. We also give a second method, which applies to an algebraic sequence modulo pa for all primes p, but is significantly slower. Finally, we show that a broad range of multidimensional sequences possess Lucas products modulo p.