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:

- Is there a fast way to calculate these, compared to the naive approach above?
- 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?