# Determining a recurrence relation

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?

-
Only a comment, since I'm not sure whether it answers your question 1): is the approach taken in arxiv.org/abs/math/0702086 useful to you (under the name guessPade)? Essentially it's Hermite-Pade using modular arithmetic. –  Martin Rubey Jun 2 '11 at 15:59
@Martin Rubey: Yes, that's precisely what I need (assuming it can give negative answers as well, i.e. "no such rational gf exists with sum of degrees < N" rather than "no rational gf found"). Is the source code available? –  Charles Jun 2 '11 at 17:30
Yes, if guessPade does not return a function this means that there is no such function with the given sum of degrees. The package is part of FriCAS, fricas.sourceforge.net. The source code of the solver itself is in the file modhpsol.spad.pamphlet, the user interface in mantepse.spad.pamphlet. The algorithm (but without the modular arithmetic) is due to Beckermann and Labahn, see the reference in the paper. –  Martin Rubey Jun 3 '11 at 11:58
@Martin Rubey: Ah, I had seen the pamphlet files (grepping the FriCAS source) but assumed they were documentation because of the TeX header. –  Charles Jun 3 '11 at 14:10

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.

-
I like the answer but wonder abut the comment 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. I take it that that is a rule of thumb? One never knows for sure if there is an irregularity further ahead. And ( for $d$ not too small) would observing a possible order $d$ recurrence after $2d-2$ steps mean so much less than after $2d$ steps? –  Aaron Meyerowitz Jun 2 '11 at 20:57
When I say matching $2d$ or fewer terms doesn't mean anything, I mean there is always a rational function with numerator and denominator of degree at most $d$ that matches $2d$ terms. The denominator might vanish at $0$ (which would mess up the recurrence interpretation), but another way to look at it is that one can generically choose $d$ coefficients for the recurrence so that running it starting with the first $d$ terms matches the next $d$. So seeing this happen shouldn't carry much weight. –  Henry Cohn Jun 2 '11 at 22:15
On the other hand, as soon as you match $2d+1$ terms something nontrivial is happening, although the pattern might not continue. Berlekamp-Massey finds all these cases, so in particular if there is an actual recurrence of degree $d$ and the algorithm is given more than $2d$ terms, then it is guaranteed to find the true recurrence. –  Henry Cohn Jun 2 '11 at 22:15

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).

-
Excellent! I was calculating the characteristic polynomials (and even factoring them, for other purposes) but I didn't see the connection. It's all clear now. –  Charles Jun 2 '11 at 14:47

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.)

-
Well, this is only obviously true if the recurrence has integer coefficients. (I think this is known to be true, and there was an MO question about it, but it's not trivial.) –  Qiaochu Yuan Jun 2 '11 at 11:38
To my doppelgänger: That idea is so obvious and useful I can't believe I missed it. Thank you. –  Charles Jun 2 '11 at 14:42

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.

-