Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
Thanks, JSE! It looks like my initial guess was too optimistic. –  algori Dec 8 '09 at 4:11
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.