C L.'s periodic sequences

If $a=b=c=d=0$ then $x_n=0$ for all $n \ge 4$ , and so the sequence eventually has period $1$ . Let us assume now that at least one of $a,b,c,d$ is nonzero. We shall call the defining polynomial to be f(z) \; = \; \left\{ \begin{array}{l@{\qquad}l} z^4 - az^3 - bz^2 - cz - d & d \neq 0 \\ z^3 - az^2 - bz - c & c \neq 0, d=0 \\ z^2 - az - b & b \neq 0, c=d=0 \\ z-a & a \neq 0, b=c=d=0 \end{array}\right. Then the solutions to the recurrence relation are given in term of powers of the roots of the defining polynomial.

1. All of these roots are nonzero.

2. If $\lambda$ is a root of $f(z)$ , it would be possible to choose $x_0,x_1,x_2,x_3$ so that $x_n=\lambda^n$ for all $n \ge 0$ . Since this sequence has to be periodic, it follows that $\lambda$ must be a root of unity. The minimal polynomial of $\lambda$ is thus one of the cyclotomic polynomials, and divides $f(z)$ .

3.If $f(z)$ had a repeated root $\lambda$ , it would be possible to choose $x_0,x_1,x_2,x_3$ so that $x_n = n\lambda^n$ for all $n \ge 0$ , and this sequence would not be periodic. Thus we deduce that $f(z)$ has no repeated roots.

Thus we deduce that $f(z)$ must be a product of distinct cyclotomic polynomials, while having degree no greater than $4$ . The cyclotomic polynomials of low degree are $\begin{array}{ll} \mbox{Degree} & \mbox{Polynomial} \\ 1 & \Phi_1,\Phi_2 \\ 2 & \Phi_3,\Phi_4,\Phi_6 \\ 4 & \Phi_5,\Phi_8,\Phi_{10},\Phi_{12} \end{array}$ because $\varphi(n) > 4$ for all positive integers $n$ other than $1,2,3,4,5,6,8,10,12$ . Thus the possible values for the defining polynomial $f(z)$ are: $\begin{array}{ll} \mbox{Degree} & \mbox{Polynomial} \\ 1 & \Phi_1,\Phi_2 \\ 2 & \Phi_1\Phi_2, \Phi_3,\Phi_4,\Phi_6 \\ 3 & \Phi_1\Phi_3,\Phi_1\Phi_4,\Phi_1\Phi_6,\Phi_2\Phi_3,\Phi_2\Phi_4,\Phi_2\Phi_6 \\ 4 & \Phi_5,\Phi_8,\Phi_{10},\Phi_{12},\Phi_3\Phi_4,\Phi_3\Phi_6,\Phi_4\Phi_6 \\ & \Phi_1\Phi_2\Phi_3,\Phi_1\Phi_2\Phi_4,\Phi_1\Phi_2\Phi_6 \end{array}$ If the defining polynomial is $\Phi_a$ , any sequence it defines will have period $a$ or $1$ .

If the defining polynomial is $\Phi_a\Phi_b$ where $a \neq b$ , any sequence it defines will have period $1$ or $a$ or $b$ or $\{a,b\}$ (the LCM of $a$ and $b$ ).

If the defining polynomial is $\Phi_a\Phi_b\Phi_c$ where $a,b,c$ are distinct, any sequence it defines will have period $1$ or $a$ or $b$ or $c$ or $\{a,b\}$ or $\{a,c\}$ or $\{b,c\}$ or $\{a,b,c\}$ .

Running through the possible cases for $f(z)$ , we see that the possible orders are $1,2,3,4,5,6,8,10,12$ , which sum to $51$ .

We'll start by assuming that $d \neq 0$ . Our logic can be extended to most of the other cases by ignoring any trailing zeroes in the tuple $(a, b, c, d)$ , and reducing the order of the matrices we use. Having $d \neq 0$ is nice since it means the sequence can always be extended backward uniquely, given any consecutive four terms at any point --- the sequence is completely periodic.

We can write the recurrence as a matrix equation, for reasons that will soon be clear:

$\begin{pmatrix} x_{i+1} \\ x_{i+2} \\ x_{i+3} \\ x_{i+4} \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ d & c & b & a \end{pmatrix} \begin{pmatrix} x_i \\ x_{i+1} \\ x_{i+2} \\ x_{i+3} \end{pmatrix}$

Let the $4 \times 4$ matrix there be $A$ . Note that since $d \neq 0$ , the matrix $A$ is invertible.

The periodicity of the sequence is equivalent to saying that for an arbitrary $X = (x_0, x_1, x_2, x_3)^T$ , there exists positive integer $n$ such that $A^nX = X$ . Plug in the four obvious unit basis vectors as $X$ and take the LCM of the resulting $n$ to see that we have a positive integer $n$ such that $A^n = I$ . Furthermore, if we also pick $n$ to be minimal, then there exists an initial vector $X$ such that $A^iX \neq X$ for $0 < i < n$ , since otherwise $A^iX \equiv A^jX$ would imply that $A^i = A^j$ and $A^{|i-j|} = I$ .

Then all of $A$ 's eigenvalues are roots of unity (write it out in Jordan canonical form, and note that if $e$ is on the diagonal, then $A^n$ has $e^n$ in its place, so $e^n = 1$ ). In fact, $A$ is diagonalizable (clear from the form of powers of a Jordan block ). So by diagonalizing $A$ we see that the period $n$ is the LCM of the orders of the roots of unity that are $A$ 's eigenvalues.

The characteristic polynomial of $A$ is $\lambda^4 - a\lambda^3 - b\lambda^2 - c\lambda - d$ , and $a, b, c, d$ are integers. In order for a root of unity with order $r$ to be a root of such an integer polynomial, the $r$ th cyclotomic polynomial has to divide the characteristic polynomial, which is attainable iff $\varphi(r) \leq 4$ (all cyclotomic polynomials have integer coefficients and are monic, so we only need the degree to be small enough). So all $r$ that satisfy $\varphi(r) \leq 4$ work.

In fact, they are the only ones that work, although there are other cases to consider: we have to check for cases where we squeeze two (or more!) separate cyclotomic polynomial factors into the characteristic polynomial, so the period will be the LCM of the numbers of the cyclotomic polynomials. After some checking, this doesn't result in any new periods.

If $d = 0$ and $c \neq 0$ , etc., similar logic will lead us again to similar conditions $\varphi(r) \leq 3, 2, 1$ , which doesn't give us any new solutions.

So, we have our answer: $1+2+3+4+5+6+8+10+12 = \boxed{51}$