From the Da Vinci code to Galois

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}+\cdots +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}+\cdots +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 $\mathrm{\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 ),\text{and}{a}^{\prime }=(a_0^{\prime },a_1^{\prime },a_2^{\prime },\dots )\in \mathrm{\Re }(\mathbb{Z})$$

then the sequences

$$a+a^{\prime }=(a_0+a_0^{\prime },a_1+a_1^{\prime },a_2+a_2^{\prime },\dots )\text{and}a\times a^{\prime }=(a_0.a_0^{\prime },a_1.a_1^{\prime },a_2.a_2^{\prime },\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 $\mathrm{\Re }(\mathbb{Z})$ has a co-unit, that is, a ring morphism

$$ϵ:\mathrm{\Re }(\mathbb{Z})\to \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 $\mathrm{\Re }(\mathbb{Z})$ also has a co-multiplication

$$\mathrm{\Delta }:\mathrm{\Re }(\mathbb{Z})\to \mathrm{\Re }(\mathbb{Z}){\otimes }_{\mathbb{Z}}\mathrm{\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 $\mathrm{\Re }(\mathbb{Q})$ of all rational linear recursive sequences.

For such a sequence $q=(q_0,q_1,q_2,\dots )\in \mathrm{\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)=\left[\begin{array}{ccccc}{q}_0& q_1& q_2& \dots & q_{k-1}\\ q_1& q_2& & & q_k\\ q_2& & & & q_{k+1}\\ ⋮& & & & ⋮\\ q_{k-1}& q_k& q_{k+1}& \dots & q_{2k-2}\end{array}\right]$$
The Hankel matrix of $q$, $H(q)$ is $H_k(q)$ where $k$ is maximal such that $det{H}_k(q)\ne 0$, that is, $H_k(q)\in G{L}_k(\mathbb{Q})$.

Let $S(q)=(s_{ij})$ be the inverse of $H(q)$, then the co-multiplication map
$$\mathrm{\Delta }:\mathrm{\Re }(\mathbb{Q})\to \mathrm{\Re }(\mathbb{Q})\otimes \mathrm{\Re }(\mathbb{Q})$$
sends the sequence $q=(q_0,q_1,\dots )$ to
$$\mathrm{\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 \mathrm{\Re }(\mathbb{Z})$ is such that $H(a)\in G{L}_k(\mathbb{Z})$ then the same formula gives $\mathrm{\Delta }(a)$ in $\mathrm{\Re }(\mathbb{Z})$.

For the Fibonacci sequences $F$ the Hankel matrix is
$$H(F)=\left[\begin{array}{cc}1& 1\\ 1& 2\end{array}\right]\in G{L}_2(\mathbb{Z})\text{with inverse}S(F)=\left[\begin{array}{cc}2& -1\\ -1& 1\end{array}\right]$$
and therefore
$$\mathrm{\Delta }(F)=2F\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 $\mathrm{\Re }(\mathbb{Q})$.

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

$$\mathrm{\Re }(\bar{\mathbb{Q}})\simeq (\bar{\mathbb{Q}}[{\bar{\mathbb{Q}}}_{\times }^{\ast }]\otimes \bar{\mathbb{Q}}[d])\oplus \sum _{i=0}^{\mathrm{\infty }}\bar{\mathbb{Q}}{S}_i$$

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

$\bar{\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
$$\mathrm{\Delta }(d)=d\otimes 1+1\otimes d\text{and}ϵ(d)=0$$

Finally, the co-algebra maps on the elements $S_i$ are given by
$$\mathrm{\Delta }(S_i)=\sum _{j=0}^i{S}_j\otimes S_{i-j}\text{and}ϵ(S_i)={\delta }_{0i}$$

That is, the co-multiplication on $\mathrm{\Re }(\bar{\mathbb{Q}})$ is completely known. To deduce from it the co-multiplication on $\mathrm{\Re }(\mathbb{Q})$ we have to consider the invariants under the action of the absolute Galois group $Gal(\bar{\mathbb{Q}}/\mathbb{Q})$ as
$$\mathrm{\Re }(\bar{\mathbb{Q}}{)}^{Gal(\bar{\mathbb{Q}}/\mathbb{Q})}\simeq \mathrm{\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 $\mathrm{\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’