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?

Improve this question
$\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
    Commented 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$
    – Joseph O'Rourke
    Commented 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$
    – Qiaochu Yuan
    Commented 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$
    – Vladimir Dotsenko
    Commented 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
    Commented Oct 25, 2014 at 13:40

1 Answer 1

Reset to default
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}$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Beautiful solution to Q1! : $\;0, 1, -1, 2, -2, 3, -3, 4, -4, 5, 5, \ldots$. $\endgroup$
    – Joseph O'Rourke
    Commented 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$
    – Qiaochu Yuan
    Commented Oct 25, 2014 at 0:13
  • 2
    $\begingroup$ To follow up on Qiaochu's comment, this is exactly how I found the recurrence. $\endgroup$
    – Richard Stanley
    Commented 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$
    – Gerry Myerson
    Commented 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$
    – Joseph O'Rourke
    Commented Oct 25, 2014 at 12:24

You must log in to answer this question.

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