Determining a recurrence relation

Question

I would like to solve the general problem of determining a linear recurrence relation that fits a given integer sequence of length $n$, or stating that none exists (with fewer than $n/2-k$ coefficients for some reasonable fixed $k$, perhaps 2, to ensure that I'm not overfitting). Actually, I'd like to find the smallest one.

Of course the problem is apparently easy: just search for one of length 1, 2, ..., n/2-k until one is found. At each step all that is needed is to solve the appropriate matrix equation (tried to write it out, no tabular environment here, but it's obvious) and check the result against the unused members of the sequence. But for reasonably large $n$ this is impractical: the linear algebra is too difficult.

Unfortunately, it's not rare for me to work with a sequence that is clearly a recurrence relation, but which appears to have a large order, so I can't simply assume that not finding a relation with order below 100 means that none exists. This raises two questions for me:

1. Is there a fast way to calculate these, compared to the naive approach above?
2. If one recurrence is known, can this be used to speed the search for recurrences of smaller order (or to prove that none exist)?

One unenlightened approach that comes to mind for #1 is to solve the matrix over the real numbers (using floating-point approximations) rather than solving it exactly over $\mathbb{Q}$. This seems reasonable, but it's not obvious how much precision is needed nor how far the numbers could be if a solution was actually found (in which case, presumably, the system should be re-solved exactly). Although solving systems this way results in serious speedup even using quadruple precision, without appropriate numerical analysis I don't think it's usable. Hopefully there is a better way.

On #2, consider a (periodic) sequence with recurrence relation $a_n=a_{n-6}.$ Basic algebra suffices to show that any recurrence of the form $a_n=2a_{n-1}-2a_{n-2}+a_{n-3}$ is also of that form, so some sequences of order 6 can be simplified (nontrivially, that is not just removing trailing zeros) to order 3. Does it suffice, for example, to check only orders dividing 6?

Answer 1

This problem comes up often in coding theory, and it can be solved efficiently by the Berlekamp-Massey algorithm (Wikipedia has pseudo-code). This is more or less equivalent to using continued fractions, although many expositions don't present it that way: given a sequence $a_0,a_1,\dots,a_N$, look at the rational function $\sum_{i=0}^N a_i x^{-i}$ and compute its continued fraction expansion, with coefficients that are polynomials in $x$. That just amounts to applying Euclid's algorithm to the polynomials $\sum_{i=0}^{N} a_i x^{N-i}$ and $x^N$.

A degree $d$ linear recurrence must be satisfied by more than $2d$ terms of the sequence to mean anything, and any such recurrence will be detected by this method. Specifically, that means the corresponding rational function with degree $d$ denominator must be a convergent to the continued fraction.

In practice, as Charles Matthews suggested, you can generally speed up the arithmetic substantially by working modulo a prime (say, a fairly large random prime). This is particularly an issue when there isn't a low-degree recurrence, since in that case generically you'll get a lot of partial quotients of degree $1$ with rapidly growing denominators. Checking that there's no low-degree recurrence modulo a prime will be much faster, since it will avoid the huge denominators.

Answer 2

For the second question: attached to each linear recurrence relation $$ a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_m a_{n-m} $$ is its characteristic polynomial $$ x^m - c_1 x^{m-1} - c_2 x^{m-2} - \cdots - c_m. $$ For example, the polynomial attached to the recurrence relation $a_n = 2a_{n-1} - 2a_{n-2} + a_{n-3}$ is $x^3-2x^2+2x-1$; the polynomial attached to the recurrence relation $a_n = a_{n-6}$ is $x^6-1$. Of course one can go from characteristic polynomial to recurrence relation as well.

The relevant fact about linear recurrences is this: for every recurrence sequence $S$, there exists a (unique) monic polynomial $p(x)$ of minimal degree with the property that the recurrence relations satisfied by $S$ are exactly the ones whose characteristic polynomial is a multiple of $p(x)$. Note that $x^3-2x^2+2x-1$ does indeed divide $x^6-1$ in the above example.

So if you have a known recurrence relation for a given sequence and you want to find the shortest one, the only recurrence relations you have to consider are the ones whose characteristic polynomials are the factors of the known recurrence relation's characteristic polynomial (and all such recurrence relations could possibly be the answer).

Answer 3

I'd certainly expect to acquire some useful information by modular arithmetic, in a given situation. For example modulo a prime p, if there is a linear recurrence, then the sequence of residues must actually be periodic. Further, the period will be a factor of the order mod p of the matrix you are seeking, in the group of invertible matrices, unless you have hit a prime dividing the determinant. Looking modulo a number of smallish primes may yield some insight. From another perspective, the characteristic polynomial of the matrix factorises over some number field, and you may gain clues as to what it is. (There is probably some theory here.)

Answer 4

There's a theorem in Raphael Salem's book, Algebraic Numbers and Fourier Analysis, which goes something like this (I don't have the reference handy, so I'm not going to get it exactly right):

Let $$A_{n.k}=\det\pmatrix{a_n&a_{n+1}&\dots&a_{n+k}\cr a_{n+1}&a_{n+2}&\dots&a_{n+k+1}\cr\dots&\dots&\dots&\dots\cr a_{n+k}&a_{n+k+1}&\dots&a_{n+2k}\cr}$$ Then the $a_r$ satisfy a linear constant coefficient recurrence of order $m$ if and only if $A_{n,m}=0$ for all $n$.

EDIT: I looked it up. It's Lemma III on page 5, due to Kronecker. It says that $\sum_0^{\infty}c_nz^n$ is a rational function if and only if the determinants $$\Delta_m=\det\pmatrix{c_0&c_1&\dots&c_m\cr c_1&c_2&\dots&c_{m+1}\cr\dots&\dots&\dots&\dots\cr c_m&c_{m+1}&\dots&c_{2m}\cr}$$ are zero for all $m\ge m_1$. Lemma I says that the power series represents a rational function if and only if its coefficients satisfy a linear homogeneous constant-coefficient recurrence relation from some point on.