8
$\begingroup$

Let $a_n$ is a binomial sum, for example $$ a_n := \sum_{k} \binom{n-k}{k} \quad \text{or} \quad \sum_{k=0}^n\binom{n+k}{n-k}\binom{2k}{k} \quad \text{or} \quad \sum_{k=0}^n\sum_{\ell=0}^k\binom{n}{k}\binom{n+k}{k}\binom{k}{\ell}^3 $$ These are Fibonacci, Delannoy and Apéry numbers. More generally, we can consider the sequence $\{a_n\}$ obtained as a diagonal of a rational function over $\Bbb Z$ (so in particular it is P-recursive), see e.g. Stanley, "Enumerative Combinatorics", Chapter 6.

Question: Given $m\in \Bbb N$ and a binomial sum $\{a_n\}$, is it decidable whether $m$ divides $a_n$ for all $n\in \Bbb N$?

This might seem a bit naive, and I supect this should be true, but couldn't find the reference. Note the Skolem's Problem which is different but has a similar flavor (and not known to be decidable).

Improve this question
$\endgroup$
1
  • $\begingroup$ A partial answer is given in works of E. Rowland and R. Yassawi. Namely, for certain binomial sums $\{ a_n\}$, if $m$ is a prime power then $\{a_n \bmod m\}$ is automatic, and so a finite computation will tell you if it is divisible by $m$ always or not. This approach led them to solve conjectures about your third example of Apéry numbers. See specifically their paper ``Automatic congruences for diagonals of rational functions''. $\endgroup$
    – Ofir Gorodetsky
    Commented Sep 18, 2022 at 23:26

2 Answers 2

Reset to default
5
$\begingroup$

I found the reference: Theorem 9.1 in Boris Adamczewski and Jason P. Bell, Diagonalization and Rationalization of algebraic Laurent series, Ann. Sci. Éc. Norm. Supér. 46 (2013), 963–1004.

The authors even discuss the Apéry sequence modulo 5, right after the theorem.

It's sort of amazing when the reference request works out so well. I thank Boris Adamczewski and Jason Bell for telling me about this remarkable work.

Improve this answer
$\endgroup$
2
$\begingroup$

These binomial sequences, and diagonals, are holonomic, meaning that they satisfy recurrence relations with polynomial coefficients. If the leading coefficient has no roots modulo m, then the question becomes easy. But I guess that in many situations, this polynomial does have roots modulo m. If one can find a closed form expression for the generating function of such the sequence, then that can also be a way for proving that the sequence (divided by m) is an integer sequence. I don't know of any holonomic sequence with integer terms for which there is no known formula that proves that the terms are integers (an integer-but-not-proven-integer holonomic sequence). But a general decision procedure to prove/disprove that a holonomic sequence (divided by m) has integer entries, I don't think that is known.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .