Date: 2023/07/19
Occasion: ACA 2023 (Applications of Computer Algebra), Session on D-Finite Functions and Beyond: Algorithms, Combinatorics, and Arithmetic
Place: Warsaw, Poland
Abstract
Rowland and Zeilberger devised an approach to algorithmically determine the modulo \(p^r\) reductions of values of combinatorial sequences representable as constant terms (building on work of Rowland and Yassawi). The resulting \(p\)-schemes are systems of recurrences and, depending on their shape, are classified as automatic or linear. We review this approach and suggest a third natural type of scheme that combines benefits of automatic and linear ones. As an example of the utility of these "scaling" schemes, we confirm and extend a conjecture of Rowland and Yassawi on Motzkin numbers. It is a well-known and beautiful classical result of Lucas that, modulo a prime \(p\), the binomial coefficients satisfy the congruences \[ \binom{n}{k} \equiv \binom{n_0}{k_0} \binom{n_1}{k_1} \cdots \binom{n_r}{k_r}, \] where \(n_i\), respectively \(k_i\), are the \(p\)-adic digits of \(n\) and \(k\). Many interesting integer sequences have been shown to satisfy versions of these congruences. For instance, Gessel has done so for the numbers used by Apéry in his proof of the irrationality of \(\zeta(3)\). We make the observation that a sequence satisfies Lucas congruences modulo \(p\) if and only if its values modulo \(p\) can be described by a linear (or scaling) \(p\)-scheme with a single state. This simple observation suggests natural generalizations of the notion of Lucas congruences. To illustrate this point, we derive explicit generalized Lucas congruences for integer sequences that can be represented as certain constant terms. This part of the talk is based on joint work with Joel Henningsen.Download
| Link | Size | Description | Hits |
|---|---|---|---|
| 2023lucascongruences-aca2023.pdf | 1.36 MB | Slides (PDF, 73 pages) | 389 |