6
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ Might $f_i$ have non trivial constant term ? In this case, $f_i=f_{i-1}+1$ would do the job ... $\endgroup$
    – few_reps
    Oct 24, 2014 at 22:49
  • $\begingroup$ @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... $\endgroup$ Oct 24, 2014 at 23:38
  • 3
    $\begingroup$ 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. $\endgroup$ Oct 25, 2014 at 0:22
  • 2
    $\begingroup$ 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). $\endgroup$ Oct 25, 2014 at 10:47
  • 1
    $\begingroup$ If you allow sqrt(),floor(),Re(),Im() the cantor pairing and its inverse will cover Z[i] I believe. $\endgroup$
    – joro
    Oct 25, 2014 at 13:40

1 Answer 1

12
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Beautiful solution to Q1! : $\;0, 1, -1, 2, -2, 3, -3, 4, -4, 5, 5, \ldots$. $\endgroup$ Oct 24, 2014 at 23:57
  • 5
    $\begingroup$ @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. $\endgroup$ Oct 25, 2014 at 0:13
  • 2
    $\begingroup$ To follow up on Qiaochu's comment, this is exactly how I found the recurrence. $\endgroup$ Oct 25, 2014 at 0:24
  • 7
    $\begingroup$ This sequence is the first thing in a paper I wrote with Alf van der Poorten some years ago. maths.mq.edu.au/~alf/www-centre/alfpapers/a106.pdf $\endgroup$ Oct 25, 2014 at 3:31
  • 1
    $\begingroup$ @GerryMyerson: Great paper, Gerry! So many nice questions and results. E.g., "it is impossible for every rational number to occur in a recurrence sequence." $\endgroup$ Oct 25, 2014 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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