# Polynomial recurrence relation covering the integers (and then Gaussian integers)

Say that a polynomial recurrence relation (my terminology) for $f_i$ is:

• $k$ initial conditions setting $f_1,\ldots,f_k$ to integers ($\in \mathbb{Z})$.
• A recurrence equation of the form $f_i =$ a polynomial in $f_{i-1},\ldots,f_{i-k}$.

Example 1: ($k=2$): $\;f_1=1,\; f_2=1$, and $f_i=f_{i-1}+f_{i-2}$. $\implies$ the Fibonacci sequence.
Example 2: ($k=1$): $\;f_1=1$, and $f_i=f_{i-1}+1$. $\implies$ $\mathbb{N}$.

Q1. Is there a polynomial recurrence relation that covers $\mathbb{Z}$?

In other words, I would like every integer (positive or negative) to be "reached" by some $f_i$. This may be obvious, in which case I apologize.

I arrived at this question from another direction:

Q2. Is there a polynomial recurrence relation over the Gaussian integers that covers the Gaussian integers?

• Might $f_i$ have non trivial constant term ? In this case, $f_i=f_{i-1}+1$ would do the job ... – few_reps Oct 24 '14 at 22:49
• @few_reps: Could you please specify the initial conditions? I don't see how that reaches all negative integers from any initial conditions. I must be missing something... – Joseph O'Rourke Oct 24 '14 at 23:38
• I can't imagine that allowing polynomial as opposed to just linear recurrence relations buys you anything except to make it harder to write down a negative result. Note that away from the zero locus of a polynomial it grows faster than linearly, so if the recurrence stays away from the zero locus it will eventually grow faster than linearly and so won't even be able to cover $\mathbb{Z}$, let alone $\mathbb{Z}[i]$. If the recurrence doesn't stay away from the zero locus then, well, this case seems complicated but I can't imagine that anything good comes of it. – Qiaochu Yuan Oct 25 '14 at 0:22
• The paper of Gerry Myerson and Alf van der Poorten that Gerry mentions in his comment to the answer of Richard Stanley shows, by the way, that for linear recurrences it is impossible to have all Gaussian integers appear (see end of page 8). – Vladimir Dotsenko Oct 25 '14 at 10:47
• If you allow sqrt(),floor(),Re(),Im() the cantor pairing and its inverse will cover Z[i] I believe. – joro Oct 25 '14 at 13:40

For the first question, let $f_1=0$, $f_2=1$, $f_3=-1$, and $f_i=-f_{i-1}+f_{i-2}+f_{i-3}$.
• Beautiful solution to Q1! : $\;0, 1, -1, 2, -2, 3, -3, 4, -4, 5, 5, \ldots$. – Joseph O'Rourke Oct 24 '14 at 23:57
• @Joseph: as opposed to polynomial recurrences, the theory of linear recurrences is well-understood, and in particular it's well-understood exactly what sequences can be described in this way: they are precisely the sequences of the form $f(n) = \sum_i p_i(n) r_i^n$ where the $p_i$ are polynomials. The sequence in question here is $(0, 1, 0, 2, 0, 3, \dots) + (0, 0, -1, 0, -2, 0, -3, \dots)$ which is $\frac{1 + (-1)^n}{2} \frac{n}{2} - \frac{1 - (-1)^n}{2} \frac{n-1}{2}$ and it's not hard to reverse-engineer the recurrence from here. – Qiaochu Yuan Oct 25 '14 at 0:13