LLL_for_linear_recurrences.sagews

Linear Recurrences with LLL

Given (a_1, a_2, \ldots, a_n) decide if there is a recurrence which will predict (a_{n+1})

Suppose (a_n = c_{n-1} \cdot a_{n-1} + \cdots + c_0 \cdot a_0 ) for some small/pleasant (c_i)

Then the lattice generated by (e_i) augmented with ( a_i \cdot C ) would have ((c_0, \ldots, c_{n-1}, -1, 0)) in it, but the wrong relationship might have a large last value (or I might have several to build from)

#Grabbed from oeis.org/A101399
A = [1, 2, 5, 10, 22]#, 47]#, 101, 217]#, 466, 1001, 2150, 4618, 9919, 21305]

C=10^3
X = Matrix(ZZ, A).transpose()
I = identity_matrix(X.nrows())
M = I.augment(C*X)
print M

[ 1 0 0 0 0 1000] [ 0 1 0 0 0 2000] [ 0 0 1 0 0 5000] [ 0 0 0 1 0 10000] [ 0 0 0 0 1 22000]

M.LLL()

[ -2 1 0 0 0 0] [ 0 0 -2 1 0 0] [ 0 -1 0 -2 1 0] [ -1 -2 1 0 0 0] [ 1 0 0 0 0 1000]

hmmm... could be better

hmmm... could be better

What if I also append (a_{i-1})? Then a row which goes to zero in that column and the pervious column will work at two levels!

def shift_by(A, k):
    L = [A[i+k] for i in range(len(A)-k)]
    return L + [0 for i in range(k)]
A1 = shift_by(A,1)
print A1

[2, 5, 10, 22, 0]

X

[ 1] [ 2] [ 5] [10] [22]

XX = X.augment(Matrix(ZZ, shift_by(A,1)).transpose())
print XX

[ 1 2] [ 2 5] [ 5 10] [10 22] [22 0]

C=10^4
M = identity_matrix(X.nrows()).augment(C*XX)
print M

[ 1 0 0 0 0 10000 20000] [ 0 1 0 0 0 20000 50000] [ 0 0 1 0 0 50000 100000] [ 0 0 0 1 0 100000 220000] [ 0 0 0 0 1 220000 0]

M.LLL()

[ -1 -2 -1 1 0 0 0] [ -4 2 2 -1 0 0 0] [ -5 24 -33 10 1 0 0] [ -2 1 0 0 0 0 10000] [ 0 -2 1 0 0 10000 0]