Automatic congruences for diagonals of rational functions

Abstract

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$.

42 pages, many figures; final version (minor changes)

Cited by in corpus (6)

• Selected non-holonomic functions in lattice statistical mechanics and enumerative combinatorics
• Profinite automata
• $p$-adic asymptotic properties of constant-recursive sequences
• Lucas' theorem modulo $p^2$
• Fast Computation of the Nth Term of an Algebraic Series over a Finite Prime Field
• An elementary proof of Bridy's theorem