10 - Linearly recursive sequences and Dynkin diagrams

Summary

Introduction

Sequences of natural numbers have always been the subject of all kind of investigations. Among them is the famous Fibonacci sequence, related to the well-known Golden Ratio. This sequence is the paradigmatic example of a sequence satisfying a linear recursion. Latter sequences are of fundamental importance in algebra, combinatorics, and number theory, as well as in automata theory, since they count languages associated with finite automata.

The first scope of the present chapter is to prove a classification theorem: it characterises a class of sequences associated with certain quivers (directed graphs); in general these sequences satisfy non-linear recursions; it turns out that these sequences satisfy also a linear recursion exactly when the undirected underlying graph is of Dynkin, or extended Dynkin, type. This is perhaps the first example of a classification theorem, that uses Dynkin diagrams, in the realm of integer sequences.

Note that, for the sake of simplicity, we have dealt here with diagrams and quivers, whose underlying graphs are simple graphs; the corresponding Dynkin diagrams are sometimes called simply laced. The whole theory may be done with more general diagrams, that is, using Cartan matrices, see (Assem et al., 2010).

The sequences we consider are called friezes: they were introduced by Philippe Caldero and they satisfy non-linear recursions associated with quivers. Such a recursion is a particular case of a mutation, an operation introduced by Fomin and Zelevinsky in their theory of cluster algebras. The recursion does not show at all that these sequences are integer-valued. This must be proved separately and for this we follow Fomin and Zelevinsky's Laurent phenomenon (Fomin and Zelevinsky, 2002a,b), for which a proof is given.

We shall explain all details about Dynkin and extended Dynkin diagrams. These diagrams have been used to classify several mathematical objects, starting with the Cartan–Killing classification of simple Lie algebras. There is a simple combinatorial characterisation of these diagrams, due to (Vinberg, 1971) for Dynkin diagrams, and to (Berman et al., 1971/72) for extended Dynkin diagrams: they are characterised by the existence of a certain function on the graph, which must be subadditive or additive. See Section 10.8 for more detail.