Tag: Larson

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’

4 Comments