# Chebyshev-like polynomials with integral roots

Chebyshev polynomials have real roots and satisfy a recurrence relation. I was wondering if one can find a sequence of polynomials with integral or rational roots with similar properties. More precisely, one is looking for a sequence of polynomials $(f_n),f_n\in\mathbf{Q}[t]$ such that

1. $\deg f_n\to\infty$ as $n\to\infty$;

2. $\sum_{n=0}^\infty f_n(t) x^n$ is (the Taylor series of) a rational function $F$ in $x$ and $t$.

3. All roots of any $f_n$ are integer and have multiplicity 1. (A weaker version: the roots are allowed to be rational and are allowed to have multiplicity $>1$ but there should be an $a>0$ such that the number of distinct roots of $f_n$ is at least $a\deg f_n$.)

-

Here's one thought. For each integer k, f_n(k) satisfies a recurrence relation. If the roots of f_n are all integers, then f_n(k) and f_n(k+1) have to be "in sync" in the sense that they never have opposite sign. This is a strong condition! For instance, suppose the sequences f_n(k) and f_n(k+1) each have unique largest eigenvalue: then these eigenvalues would have to have the same argument.

Update: Qiaochu's answer suggests that in fact working mod p would be just better than the "archimedean" picture sketched above, since it is really F_q[t], not Z[t] or Q[t], that is analogous to the integers. Let F_n(t) be the reduction of f_n(t) to F_p[t]. If f_n(t) has all roots rational for every n, then the reduction of f_n(t) mod p has the same property. But now we are saying something quite strong; that f_n(t) lies in a finitely generated subgroup of F_q(t)^*! This is presumably ruled out by Mason's theorem (ABC for function fields.) Indeed, you could probably prove in this way that not only are the roots of f_n(t) not rational, but f_n(t) has irreducible factors of arbitrarily large degree.

I don't think this approach would touch a harder question along the same lines like this one.

-
Thanks, JSE! It looks like my initial guess was too optimistic. –  algori Dec 8 '09 at 4:11

I can satisfy conditions 1, 3 and almost satisfy condition 2. Letting $f_n(t) = {t+n-1 \choose n}$ we have the well-known generating function

$\displaystyle \sum_{n \ge 0} f_n(t) x^n = \frac{1}{(1 - x)^{-t}}$

which is rational in $x$ for any fixed integer value of $t$. I think condition 2 will end up being the hardest to satisfy because rational functions are quite rigid.

Edit 1: My current opinion is that the conditions are not satisfiable. Based on the analogous situation with linear homogeneous recurrences on the integers I am going to conjecture that any polynomial sequence which obeys a polynomial linear recurrence and is not essentially a geometric series has terms divisible by irreducible polynomials of arbitrarily high order.

Edit 2: A very strong result available in the integer case is Zsigmondy's theorem, but we don't need a result this strong. Here's a nice result in the integer case. Suppose an integer sequence $a_n$ satisfies a linear homogeneous recurrence with integer coefficients, and let $p$ be a prime not dividing those coefficients. Then the sequence $a_n \bmod p$ is periodic (not just eventually periodic) $\bmod p$ by Pigeonhole. If in addition there exists $n$ such that $a_n = 0$ and $a_n$ is unbounded, then it follows that there is a nonzero term of the sequence divisible by $p$. For example, this is true of the Fibonacci sequence; in fact we have the much stronger result that for $p > 5$, either $p | F_{p+1}$ or $p | F_{p-1}$.

My guess is that a result like this holds in the polynomial case with $p$ replaced by a monic irreducible polynomial (say, of degree $2$), although the argument above breaks down as written.

-
Thanks, Qiaochu! That's a good example. But it gives a recurrence relation for $(f_n(t))$ for any individual integer $t$, rather than for $(f_n)$. By the way, this is also the problem with the "weaker form" of condition 2 in my posting. Sorry for confusion. –  algori Dec 6 '09 at 23:24
What analogy with the integers do you have in mind? –  JSE Dec 7 '09 at 4:37
Qiaochu: re the new version -- do you mean irreducible over $\mathbf{Z}$ or $\mathbf{Q}$? –  algori Dec 7 '09 at 4:38
JSE, algori: I've added some details. –  Qiaochu Yuan Dec 7 '09 at 5:05