Skip to main content
added 945 characters in body; added 52 characters in body; added 21 characters in body; added 23 characters in body
Source Link
Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741

I can satisfy conditions 1, 3 and almost satisfy condition 2. Letting $f_n(t) = {t+n-1 \choose n}$ we have the well-known generating function

$\displaystyle \sum_{n \ge 0} f_n(t) x^n = \frac{1}{(1 - x)^{-t}}$

which is rational in $x$ for any fixed integer value of $t$. I think condition 2 will end up being the hardest to satisfy because rational functions are quite rigid.


MyEdit 1: My current opinion is that the conditions are not satisfiable. Based on the analogous situation with linear homogeneous recurrences on the integers I am going to conjecture that any polynomial sequence which obeys a polynomial linear recurrence and is not essentially a geometric series has terms divisible by irreducible polynomials of arbitrarily high order.

Edit 2: A very strong result available in the integer case is Zsigmondy's theorem, but we don't need a result this strong. Here's a nice result in the integer case. Suppose an integer sequence $a_n$ satisfies a linear homogeneous recurrence with integer coefficients, and let $p$ be a prime not dividing those coefficients. Then the sequence $a_n \bmod p$ is periodic (not just eventually periodic) $\bmod p$ by Pigeonhole. If in addition there exists $n$ such that $a_n = 0$ and $a_n$ is unbounded, then it follows that there is a nonzero term of the sequence divisible by $p$. For example, this is true of the Fibonacci sequence; in fact we have the much stronger result that for $p > 5$, either $p | F_{p+1}$ or $p | F_{p-1}$.

My guess is that a result like this holds in the polynomial case with $p$ replaced by a monic irreducible polynomial (say, of degree $2$), although the argument above breaks down as written.

I can satisfy conditions 1, 3 and almost satisfy condition 2. Letting $f_n(t) = {t+n-1 \choose n}$ we have the well-known generating function

$\displaystyle \sum_{n \ge 0} f_n(t) x^n = \frac{1}{(1 - x)^{-t}}$

which is rational in $x$ for any fixed integer value of $t$. I think condition 2 will end up being the hardest to satisfy because rational functions are quite rigid.


My current opinion is that the conditions are not satisfiable. Based on the analogous situation with linear homogeneous recurrences on the integers I am going to conjecture that any polynomial sequence which obeys a polynomial linear recurrence and is not essentially a geometric series has terms divisible by irreducible polynomials of arbitrarily high order.

I can satisfy conditions 1, 3 and almost satisfy condition 2. Letting $f_n(t) = {t+n-1 \choose n}$ we have the well-known generating function

$\displaystyle \sum_{n \ge 0} f_n(t) x^n = \frac{1}{(1 - x)^{-t}}$

which is rational in $x$ for any fixed integer value of $t$. I think condition 2 will end up being the hardest to satisfy because rational functions are quite rigid.


Edit 1: My current opinion is that the conditions are not satisfiable. Based on the analogous situation with linear homogeneous recurrences on the integers I am going to conjecture that any polynomial sequence which obeys a polynomial linear recurrence and is not essentially a geometric series has terms divisible by irreducible polynomials of arbitrarily high order.

Edit 2: A very strong result available in the integer case is Zsigmondy's theorem, but we don't need a result this strong. Here's a nice result in the integer case. Suppose an integer sequence $a_n$ satisfies a linear homogeneous recurrence with integer coefficients, and let $p$ be a prime not dividing those coefficients. Then the sequence $a_n \bmod p$ is periodic (not just eventually periodic) $\bmod p$ by Pigeonhole. If in addition there exists $n$ such that $a_n = 0$ and $a_n$ is unbounded, then it follows that there is a nonzero term of the sequence divisible by $p$. For example, this is true of the Fibonacci sequence; in fact we have the much stronger result that for $p > 5$, either $p | F_{p+1}$ or $p | F_{p-1}$.

My guess is that a result like this holds in the polynomial case with $p$ replaced by a monic irreducible polynomial (say, of degree $2$), although the argument above breaks down as written.

added 362 characters in body; added 12 characters in body
Source Link
Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741

I can satisfy conditions 1, 3 and almost satisfy condition 2. Letting $f_n(t) = {t+n-1 \choose n}$ we have the well-known generating function

$\displaystyle \sum_{n \ge 0} f_n(t) x^n = \frac{1}{(1 - x)^{-t}}$

which is rational in $x$ for any fixed integer value of $t$. I think condition 2 will end up being the hardest to satisfy because rational functions are quite rigid.


My current opinion is that the conditions are not satisfiable. Based on the analogous situation with linear homogeneous recurrences on the integers I am going to conjecture that any polynomial sequence which obeys a polynomial linear recurrence and is not essentially a geometric series has terms divisible by irreducible polynomials of arbitrarily high order.

I can satisfy conditions 1, 3 and almost satisfy condition 2. Letting $f_n(t) = {t+n-1 \choose n}$ we have the well-known generating function

$\displaystyle \sum_{n \ge 0} f_n(t) x^n = \frac{1}{(1 - x)^{-t}}$

which is rational in $x$ for any fixed integer value of $t$. I think condition 2 will end up being the hardest to satisfy because rational functions are quite rigid.

I can satisfy conditions 1, 3 and almost satisfy condition 2. Letting $f_n(t) = {t+n-1 \choose n}$ we have the well-known generating function

$\displaystyle \sum_{n \ge 0} f_n(t) x^n = \frac{1}{(1 - x)^{-t}}$

which is rational in $x$ for any fixed integer value of $t$. I think condition 2 will end up being the hardest to satisfy because rational functions are quite rigid.


My current opinion is that the conditions are not satisfiable. Based on the analogous situation with linear homogeneous recurrences on the integers I am going to conjecture that any polynomial sequence which obeys a polynomial linear recurrence and is not essentially a geometric series has terms divisible by irreducible polynomials of arbitrarily high order.

Source Link
Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741

I can satisfy conditions 1, 3 and almost satisfy condition 2. Letting $f_n(t) = {t+n-1 \choose n}$ we have the well-known generating function

$\displaystyle \sum_{n \ge 0} f_n(t) x^n = \frac{1}{(1 - x)^{-t}}$

which is rational in $x$ for any fixed integer value of $t$. I think condition 2 will end up being the hardest to satisfy because rational functions are quite rigid.