5
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ 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) ) ? $\endgroup$
    – j.c.
    Commented Dec 26, 2009 at 22:41
  • $\begingroup$ 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. $\endgroup$
    – Gjergji Zaimi
    Commented Dec 26, 2009 at 22:47
  • $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    Commented Dec 27, 2009 at 1:15

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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