# Are the terms of a linear recurrence integral?

Given rational numbers $a_1,\ldots, a_k$ and $u_0, \ldots, u_k$, let $(u_n)_{n \geq k}$ be the linear recurrence defined by $$u_n := a_1 u_{n-1} + \cdots + a_k u_{n-k}, \text{ for } n \geq k .$$ Obviously, $u_n \in \mathbb{Q}$ for any $n \geq 0$.

My question is: Is there an effective way to decide if it is true that $u_n \in \mathbb{Z}$ for all sufficiently large $n$ ?

• Perhaps one should study the polynomial $\sum_{i}a_{i}X^{i}$. Sep 16 '16 at 10:57
• This sounds similar to the Skolem problem or the positivity problem. I would thus guess the problem is open. Sep 16 '16 at 12:43
• I am already stuck with a linear recurrence of order $2$ such as $u_n = \lambda_1^n + \lambda_2^n$ with $\lambda_i \in \mathbb{Q}$ for which the Skolem problem is solvable. Indeed, I have no idea whether $(1 + 3^n)/2^n$ is an integer for infinitely many $n$ or not. In other words, what do we know about the limit points of $3^n$ in the ring $\mathbb{Z}_2$ of the $2$-adic integers? Sep 16 '16 at 14:00
• @LucGuyot $3^n + 1 = u_{2n} / u_n$ where $u_n := (3^n - 1) /(3 - 1)$ is a Lucas sequence. Formulas for the $p$-adic valuation of Lucas sequence are given in C. Sanna, The p-adic valuation of Lucas sequences, The Fibonacci Quarterly 54, 118–124 (a preprint here: researchgate.net/publication/…), in particular $v_2(u_n) = v_2(n) + 1$ if $2 \nmid n$ and $v_2(u_n) = 0$ is $2 \nmid n$. Therefore, $v_2(3^n + 1) \leq v_2(u_{2n}) = v_2(n) + 2 \ll \log n$ so that $(1+3^n) / 2^n$ is not an integer for all large $n$.
– user40023
Sep 16 '16 at 14:44
• @LucGuyot: $1+3^n$ is 2-divisible at most by 4. For, the binomial formula of $(1+2)^n$ gives $1+3^n=2(1+n^2+4(...))$ and $1+n^2\equiv 2(4)$ for $n$ odd. Sep 16 '16 at 15:00

The problem is effectively decidable. To test whether $u_n$ is eventually integral, first use the recurrence relation for $u_n$ to construct relatively prime polynomials $A,B\in \mathbb{Z}[x]$ such that the rational function $A/B$ has power series expansion $\sum_nu_nx^n$. (Here relatively prime will always mean no common factor in the ring $\mathbb{Z}[x]$ besides $\pm1$.) Then the following Lemma provides an effective test on $A$ and $B$ that determines whether or not $u_n$ is eventually integral.

Lemma. Suppose that $A,B\in \mathbb{Z}[x]$ are relatively prime, and that $A/B$ has power series expansion $\sum_{n\ge0}u_nx^n$. Let $B=cC$, where $c$ is the gcd of the coefficients of $B$. Then the sequence $u_n$ is eventually integral if and only if

1. $B(0)=\pm c$.
2. $A$ is an element of the ideal of $\mathbb{Z}[x]$ generated by $c$ and $C$.

Proof of the Lemma. The if direction: we assume that Conditions 1 and 2 hold, and prove that the sequence $u_k$ is eventually integral.

By Condition 2, $$A=cD+CE,$$ for some choice of $D,E\in \mathbb{Z}[x].$ Dividing by $B$, and using $B=cC$, $$\tag{*}\dfrac{A}{B}=\dfrac{D}{C}+\dfrac{E}{c}.$$ But Condition 1 implies that $C$ has the form $\pm(1-xC_1)$, for some $C_1\in \mathbb{Z}[x]$. Therefore $D/C$ has the form $$\pm D(1+(xC_1)+(xC_1)^2+\ldots).$$ It follows that the power series for $D/C$ has all integral coefficients. Since $E/c$ is a polynomial with rational coefficients, it follows from ($*$) that the power series $\sum u_kx^k$ for $A/B$ eventually has integral coefficients.

The only if direction: We assume that the sequence $u_k$ is eventually integral, and verify Conditions 1 and 2.

Remark. At this point it will be convenient to extend the usual notion of the content of a polynomial to power series $f=\sum_nu_nx^n$ with eventually integral coefficients. Define $$\gamma(f)=\prod_{p \text{ prime}}p^{\min_n(v_p(u_n))},$$ where $v_p(u_n)$ is the exponent to which $p$ appears in the rational number $u_n$. If $P\in \mathbb{Z}[x]$ then the product $Pf$ again has eventually integral coefficients, and it holds that $\gamma(Pf)=\gamma(P)\gamma(f)$. The proof is similar to the case of two polynomials.

Proof of Condition 1. Since $A$ and $B$ are relatively prime, there are polynomials $U,V\in \mathbb{Z}[x]$ and an integer $m\ne0$ such that $AU+BV=m$. Let $f=\sum_nu_nx^n$ be the power series expansion of $A/B$. By factoring out $B$, write the equation $AU+BV=m$ in the form $$\tag{**}B(fU+V)=m.$$ Since $c=\gamma(B)$, the multiplicativity of the content function $\gamma$ implies that $$c\gamma(fU+V)=m.$$ But ($**$) implies that $B(0)t=m$, where $t$ is the constant term of $fU+V$. Therefore $B(0)t=c\gamma(fU+V)$, or equivalently $$\dfrac{B(0)}{c}\cdot \dfrac{t}{\gamma(fU+V)}=1.$$ Since the two factors are both integers, it follows that $B(0)=\pm c$. This proves Condition 1.

Proof of Condition 2. As before, let $f$ denote the power series for $A/B$. We note that the power series $cf$ has all integer coefficients. Indeed, taking the content of both sides of the equation $A=Bf$, we have $$\gamma(A)=c\gamma(f)=\gamma(cf).$$ The equation implies that $cf$ has integer content. Therefore all coefficients of $cf$ are integers.

It follows that $f$ has the form $D/c+g$, for some $D\in \mathbb{Z}[x]$ and some power series $g$ with integer coefficients. Multiplying the equation $A/B=D/c+g$ by $B$ and using the definition $B=cC$, we conclude that $$A=CD+c\cdot(Cg).$$ But $Cg$ is visibly a polynomial, being a difference of two polynomials. Therefore $A$ is an element of the ideal of $\mathbb{Z}[x]$ generated by $c$ and $C$. This completes the proof of the Lemma.

Notes.

1. For the connection between generating functions of recurrence sequences and rational functions, see Chapter 4 of Richard Stanley's book Enumerative Combinatorics, v1.
2. Concerning Condition 2 of the Lemma, an algorithm for ideal membership in the ring $\mathbb{Z}[x]$ is given in Chapter 10 of Ideals Varieties and Algorithms by Cox, Little and OShea. But anyway in this case we need only determine whether $C$ divides $A$ in the ring $\mathbb{Z}/c\mathbb{Z}[x]$.
3. The proof of Condition 1 in the only if part of the Lemma is substantially the same as in the solution to Exercise 2a in Chapter 4 of Stanley's book.
4. Condition 1 in the Lemma by itself is equivalent to the requirement that the $u_n$ have bounded denominators, that is, that there is a nonzero integer $M$ such that for all $n$, $Mu_n\in\mathbb{Z}$.