Brown – neverendingbooks

The Fibonacci sequence reappears a bit later in Dan Brown’s book ‘The Da Vinci Code’ where it is used to login to the bank account of Jacques Sauniere at the fictitious Parisian branch of the Depository Bank of Zurich.

Last time we saw that the Hankel matrix of the Fibonacci series $F = (1, 1, 2, 3, 5, \dots)$ is invertible over $Z$
$H (F) = [\begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix}] \in S L_{2} (Z)$
and we can use the rule for the co-multiplication $Δ$ on $ℜ (Q)$ , the algebra of rational linear recursive sequences, to determine $Δ (F)$ .

For a general integral linear recursive sequence the corresponding Hankel matrix is invertible over $Q$ , but rarely over $Z$ . So we need another approach to compute the co-multiplication on $ℜ (Z)$ .

Any integral sequence $a = (a_{0}, a_{1}, a_{2}, \dots)$ can be seen as defining a $Z$ -linear map $λ_{a}$ from the integral polynomial ring $Z [x]$ to $Z$ itself via the rule $λ_{a} (x^{n}) = a_{n}$ .

If $a \in ℜ (Z)$ , then 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$

Alternatively, we can look at $a$ as defining a $Z$ -linear map $λ_{a}$ from the quotient ring $Z [x] / (f (x))$ to $Z$ .

The multiplicative structure on $Z [x] / (f (x))$ dualizes to a co-multiplication $Δ_{f}$ on the set of all such linear maps $(Z [x] / (f (x)))^{*}$ and we can compute $Δ_{f} (a)$ .

We see that the set of all integral linear recursive sequences can be identified with the direct limit
$ℜ (Z) = \underset{\underset{f | g}{\to}}{l i m} (\frac{Z [x]}{(f (x))})^{*}$
(where the directed system is ordered via division of monic integral polynomials) and so is equipped with a co-multiplication $Δ = \underset{\to}{l i m} Δ_{f}$ .

Btw. the ring structure on $ℜ (Z) \subset (Z [x])^{*}$ comes from restricting to $ℜ (Z)$ the dual structures of the co-ring structure on $Z [x]$ given by
$Δ (x) = x \otimes x and ϵ (x) = 1$

From this description it is clear that you need to know a hell of a lot number theory to describe this co-multiplication explicitly.

As most of us prefer to work with rings rather than co-rings it is a good idea to begin to study this co-multiplication $Δ$ by looking at the dual ring structure of
$ℜ (Z)^{*} = \underset{\underset{f | g}{\leftarrow}}{l i m} \frac{Z [x]}{(f (x))}$
This is the completion of $Z [x]$ at the multiplicative set of all monic integral polynomials.

This is a horrible ring and very little is known about it. Some general remarks were proved by Kazuo Habiro in his paper Cyclotomic completions of polynomial rings.

In fact, Habiro got interested is a certain subring of $ℜ (Z)^{*}$ which we now know as the Habiro ring and which seems to be a red herring is all stuff about the field with one element, $F_{1}$ (more on this another time). Habiro’s ring is

$\hat{Z [q]} = \underset{\underset{n | m}{\leftarrow}}{l i m} \frac{Z [q]}{(q^{n} - 1)}$

and its elements are all formal power series of the form
$a_{0} + a_{1} (q - 1) + a_{2} (q^{2} - 1) (q - 1) + \dots + a_{n} (q^{n} - 1) (q^{n - 1} - 1) \dots (q - 1) + \dots$
with all coefficients $a_{n} \in Z$ .

Here’s a funny property of such series. If you evaluate them at $q \in C$ these series are likely to diverge almost everywhere, but they do converge in all roots of unity!

Some people say that these functions are ‘leaking out of the roots of unity’.

If the ring $ℜ (Z)^{*}$ is controlled by the absolute Galois group $G a l (\overset{―}{Q} / Q)$ , then Habiro’s ring is controlled by the abelianzation $G a l (\overset{―}{Q} / Q)^{a b} ≃ {\hat{Z}}^{*}$ .

Comments closed

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 $ℜ (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), and a^{'} = (a_{0}^{'}, a_{1}^{'}, a_{2}^{'}, \dots) \in ℜ (Z)$

then the sequences

$a + a^{'} = (a_{0} + a_{0}^{'}, a_{1} + a_{1}^{'}, a_{2} + a_{2}^{'}, \dots) and 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 $ℜ (Z)$ has a co-unit, that is, a ring morphism

$ϵ : ℜ (Z) \to 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 $ℜ (Z)$ also has a co-multiplication

$Δ : ℜ (Z) \to ℜ (Z) \otimes_{Z} ℜ (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 $ℜ (Q)$ of all rational linear recursive sequences.

For such a sequence $q = (q_{0}, q_{1}, q_{2}, \dots) \in ℜ (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{matrix} 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_{2 k - 2} \end{matrix}]$
The Hankel matrix of $q$ , $H (q)$ is $H_{k} (q)$ where $k$ is maximal such that $d e t H_{k} (q) \neq 0$ , that is, $H_{k} (q) \in G L_{k} (Q)$ .

Let $S (q) = (s_{i j})$ be the inverse of $H (q)$ , then the co-multiplication map
$Δ : ℜ (Q) \to ℜ (Q) \otimes ℜ (Q)$
sends the sequence $q = (q_{0}, q_{1}, \dots)$ to
$Δ (q) = \sum_{i, j = 0}^{k - 1} s_{i j} (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 ℜ (Z)$ is such that $H (a) \in G L_{k} (Z)$ then the same formula gives $Δ (a)$ in $ℜ (Z)$ .

For the Fibonacci sequences $F$ the Hankel matrix is
$H (F) = [\begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix}] \in G L_{2} (Z) with inverse S (F) = [\begin{matrix} 2 & - 1 \\ - 1 & 1 \end{matrix}]$
and therefore
$Δ (F) = 2 F \otimes F - D F \otimes F - F \otimes D F + D F \otimes D F$
There’s a lot of number theoretic and Galois-information encoded into the co-multiplication on $ℜ (Q)$ .

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

$ℜ (\overset{―}{Q}) ≃ (\overset{―}{Q} [{\overset{―}{Q}}_{\times}^{*}] \otimes \overset{―}{Q} [d]) \oplus \sum_{i = 0}^{\infty} \overset{―}{Q} S_{i}$

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

$\overset{―}{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
$Δ (d) = d \otimes 1 + 1 \otimes d and ϵ (d) = 0$

Finally, the co-algebra maps on the elements $S_{i}$ are given by
$Δ (S_{i}) = \sum_{j = 0}^{i} S_{j} \otimes S_{i - j} and ϵ (S_{i}) = δ_{0 i}$

That is, the co-multiplication on $ℜ (\overset{―}{Q})$ is completely known. To deduce from it the co-multiplication on $ℜ (Q)$ we have to consider the invariants under the action of the absolute Galois group $G a l (\overset{―}{Q} / Q)$ as
$ℜ (\overset{―}{Q})^{G a l (\overset{―}{Q} / Q)} ≃ ℜ (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 $ℜ (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

Tag: Brown

From the Da Vinci code to Habiro

From the Da Vinci code to Galois