SOME FOURTH-ORDER LINEAR DIVISIBILITY SEQUENCES

We extend the Lucas–Lehmer theory for second-order divisibility sequences to a large class of fourth-order sequences, with appropriate laws of apparition and of repetition. Examples are provided by the numbers of perfect matchings, or of spanning trees, in families of graphs, and by the numbers of points on elliptic curves over finite fields. Whether there are fourth-order divisibility sequences not covered by our theory is an open question.