MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Supppose there are integers $a_1,a_2,\dots$ and a polynomial $p$ so that the integers $p(a_1),p(a_2)...$ satisfy some linear recurrence, i.e. $\sum p(a_i)x^i$ is a rational function of $x$. Must integers $b_i\in p^{-1}(p(a_i))$ so that $\sum b_ix^i$ is a rational function, necessarily exist?

(The answer is no if we ask for the function $\sum a_i x^i$ to be rational, as can be seen when $p(t)=t^2$ and $a_i$ being a random sequence of $\pm1$)

share|cite|improve this question
I'm not sure if I understand the question. For your example, could we choose b_i = +1 for all i, and thus get a positive answer ( since +1 certainly is in p^{-1}(p(a_i)) as p(+1) = p(a_i) ) ? – j.c. Dec 26 '09 at 22:41
You're right, it's not a counter-example, I just mentioned it to clarify why I'm looking for the $b_i$'s and not directly for the $a_i$'s to satisfy a linear recurrence. – Gjergji Zaimi Dec 26 '09 at 22:47
I've often wondered about this myself. You probably already know this, but when p is a power function and p(a_i) is itself a polynomial I think this is known and I think there is a proof somewhere in Titu Andreescu and Gabriel Dospinescu's "Problems from the Book" by finite differences. – Qiaochu Yuan Dec 27 '09 at 1:15
up vote 3 down vote accepted

If $p(x)=x^d$ then this question coincides with Pisot's d'th root conjecture. A proof is given in this paper of Zannier, I'm not sure if it's the one that Qiaochu was referring to in the comments.

Edit: A more general question was answered in the subsequent article Equations in the Hadamard ring of rational functions by Andrea Ferretti and Umberto Zannier.

share|cite|improve this answer

Your Answer


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.