In The Da Vinci Code, Dan Brown feels he need to bring in a French cryptologist, Sophie Neveu, to explain the mystery behind this series of numbers:

13 – 3 – 2 – 21 – 1 – 1 – 8 – 5

The Fibonacci sequence, 1-1-2-3-5-8-13-21-34-55-89-144-… is such that any number in it is the sum of the two previous numbers.

It is the most famous of all **integral linear recursive sequences**, that is, a sequence of integers

\[

a = (a_0,a_1,a_2,a_3,\dots) \]

such that there is a monic polynomial with integral coefficients of a certain degree $n$

\[

f(x) = x^n + b_1 x^{n-1} + b_2 x^{n-2} + \dots + b_{n-1} x + b_n \]

such that for every integer $m$ we have that

\[

a_{m+n} + b_1 a_{m+n-1} + b_2 a_{m+n-2} + \dots + b_{n-1} a_{m+1} + a_m = 0 \]

For the Fibonacci series $F=(F_0,F_1,F_2,\dots)$, this polynomial can be taken to be $x^2-x-1$ because

\[

F_{m+2} = F_{m+1}+F_m \]

The set of **all** integral linear recursive sequences, let’s call it $\Re(\mathbb{Z})$, is a beautiful object of great complexity.

For starters, it is a **ring**. That is, we can add and multiply such sequences. If

\[

a=(a_0,a_1,a_2,\dots),~\quad \text{and}~\quad a’=(a’_0,a’_1,a’_2,\dots)~\quad \in \Re(\mathbb{Z}) \]

then the sequences

\[

a+a’ = (a_0+a’_0,a_1+a’_1,a_2+a’_2,\dots) \quad \text{and} \quad a \times a’ = (a_0.a’_0,a_1.a’_1,a_2.a’_2,\dots) \]

are again linear recursive. The zero and unit in this ring are the constant sequences $0=(0,0,\dots)$ and $1=(1,1,\dots)$.

So far, nothing terribly difficult or exciting.

It follows that $\Re(\mathbb{Z})$ has a **co-unit**, that is, a ring morphism

\[

\epsilon~:~\Re(\mathbb{Z}) \rightarrow \mathbb{Z} \]

sending a sequence $a = (a_0,a_1,\dots)$ to its first entry $a_0$.

It’s a bit more difficult to see that $\Re(\mathbb{Z})$ also has a **co-multiplication**

\[

\Delta~:~\Re(\mathbb{Z}) \rightarrow \Re(\mathbb{Z}) \otimes_{\mathbb{Z}} \Re(\mathbb{Z}) \]

with properties dual to those of usual multiplication.

To describe this co-multiplication in general will have to await another post. For now, we will describe it on the easier ring $\Re(\mathbb{Q})$ of all **rational** linear recursive sequences.

For such a sequence $q = (q_0,q_1,q_2,\dots) \in \Re(\mathbb{Q})$ we consider its Hankel matrix. From the sequence $q$ we can form symmetric $k \times k$ matrices such that the opposite $i+1$-th diagonal consists of entries all equal to $q_i$

\[

H_k(q) = \begin{bmatrix} q_0 & q_1 & q_2 & \dots & q_{k-1} \\

q_1 & q_2 & & & q_k \\

q_2 & & & & q_{k+1} \\

\vdots & & & & \vdots \\

q_{k-1} & q_k & q_{k+1} & \dots & q_{2k-2} \end{bmatrix} \]

The Hankel matrix of $q$, $H(q)$ is $H_k(q)$ where $k$ is maximal such that $det~H_k(q) \not= 0$, that is, $H_k(q) \in GL_k(\mathbb{Q})$.

Let $S(q)=(s_{ij})$ be the inverse of $H(q)$, then the co-multiplication map

\[

\Delta~:~\Re(\mathbb{Q}) \rightarrow \Re(\mathbb{Q}) \otimes \Re(\mathbb{Q}) \]

sends the sequence $q = (q_0,q_1,\dots)$ to

\[

\Delta(q) = \sum_{i,j=0}^{k-1} s_{ij} (D^i q) \otimes (D^j q) \]

where $D$ is the shift operator on sequence

\[

D(a_0,a_1,a_2,\dots) = (a_1,a_2,\dots) \]

If $a \in \Re(\mathbb{Z})$ is such that $H(a) \in GL_k(\mathbb{Z})$ then the same formula gives $\Delta(a)$ in $\Re(\mathbb{Z})$.

For the Fibonacci sequences $F$ the Hankel matrix is

\[

H(F) = \begin{bmatrix} 1 & 1 \\ 1& 2 \end{bmatrix} \in GL_2(\mathbb{Z}) \quad \text{with inverse} \quad S(F) = \begin{bmatrix} 2 & -1 \\ -1 & 1 \end{bmatrix} \]

and therefore

\[

\Delta(F) = 2 F \otimes ~F – DF \otimes F – F \otimes DF + DF \otimes DF \]

There’s a lot of number theoretic and Galois-information encoded into the co-multiplication on $\Re(\mathbb{Q})$.

To see this we will describe the co-multiplication on $\Re(\overline{\mathbb{Q}})$ where $\overline{\mathbb{Q}}$ is the field of all algebraic numbers. One can show that

\[

\Re(\overline{\mathbb{Q}}) \simeq (\overline{\mathbb{Q}}[ \overline{\mathbb{Q}}_{\times}^{\ast}] \otimes \overline{\mathbb{Q}}[d]) \oplus \sum_{i=0}^{\infty} \overline{\mathbb{Q}} S_i \]

Here, $\overline{\mathbb{Q}}[ \overline{\mathbb{Q}}_{\times}^{\ast}]$ is the group-algebra of the multiplicative group of non-zero elements $x \in \overline{\mathbb{Q}}^{\ast}_{\times}$ and each $x$, which corresponds to the geometric sequence $x=(1,x,x^2,x^3,\dots)$, is a group-like element

\[

\Delta(x) = x \otimes x \quad \text{and} \quad \epsilon(x) = 1 \]

$\overline{\mathbb{Q}}[d]$ is the universal Lie algebra of the $1$-dimensional Lie algebra on the primitive element $d = (0,1,2,3,\dots)$, that is

\[

\Delta(d) = d \otimes 1 + 1 \otimes d \quad \text{and} \quad \epsilon(d) = 0 \]

Finally, the co-algebra maps on the elements $S_i$ are given by

\[

\Delta(S_i) = \sum_{j=0}^i S_j \otimes S_{i-j} \quad \text{and} \quad \epsilon(S_i) = \delta_{0i} \]

That is, the co-multiplication on $\Re(\overline{\mathbb{Q}})$ is completely known. To deduce from it the co-multiplication on $\Re(\mathbb{Q})$ we have to consider the invariants under the action of the absolute Galois group $Gal(\overline{\mathbb{Q}}/\mathbb{Q})$ as

\[

\Re(\overline{\mathbb{Q}})^{Gal(\overline{\mathbb{Q}}/\mathbb{Q})} \simeq \Re(\mathbb{Q}) \]

Unlike the Fibonacci sequence, not every integral linear recursive sequence has an Hankel matrix with determinant $\pm 1$, so to determine the co-multiplication on $\Re(\mathbb{Z})$ is even a lot harder, as we will see another time.

**Reference**: Richard G. Larson, Earl J. Taft, ‘The algebraic structure of linearly recursive sequences under Hadamard product’

>the group-algebra of the multiplicative group of non-zero elements

should this be denoted \Qbar[\Qbar^*_\times]? As stated it looks like a typo 🙂

I think the standard notation for the complex group algebra of a group $G$ is $\mathbb{C} G$, but in this case with the two \overline ‘s it is a bit confusing so I changed it. Thanks!

Hi,

I took a look at the reference you mentioned and they do not seem to treat the integral case or mention any connection with the absolute Galois group.

I guess you will write about it in the next post but could you suggest a reference for the integral/number theoretic stuff?

Asvin, in the paper Larson and Taft describe he case over algebraically closed fields, and as the continuous dual behaves under extension of scalars, Galois descent gives it over any field. Some more details about the (algebraically closed) field case can be found in Peterson-Taft The Hopf algebra of linearly recursive sequences.

For the integral case, you can for example look at this paper. But, probably i’ll write some follow-up posts soon.