Difference sequence

The difference sequence of a given sequence \(a\) is the sequence \(\Delta a\) of differences of its adjacent entries. In this article, we explain the difference sequence system, which is a new method to create a notation appearing in Japanese googology.
== Definition ==
Denote by \(()\) the empty sequence of numbers. Let \(a\) be a sequence of numbers. Denote by \(\textrm{Lng}(a) \in \mathbb{N} \cup \{\infty\}\) the length of \(a\). Put \(L = \textrm{Lng}(a)\). For an \(i \in \mathbb{N}\) smaller than \(L\), denote by \(a_i\) the \((1+i)\)-th entry of \(a\). If \(\textrm{Lng}(a) < \infty\), then \(a\) is expressed as \((a_i)_{i=0}^{L-1}\). Otherwise, \(a\) is expressed as \((a_i)_{i=0}^{\infty}\).
The difference sequence \(\Delta a\) of \(a\) is defined in the following way:
# If \(L = 0\), then \(\Delta a\) is undefined or defined as a specific sequence such as \(()\) depending on the context.
# If \(0 < L < \infty\), then \(\Delta a\) is defined as the finite sequence \((a_{i+1}-a_i)_{i=0}^{L-2}\) of length \(L-1\).
# If \(L = \infty\), \(\Delta a\) is defined as the infinite sequence \((a_{i+1}-a_i)_{i=0}^{\infty}\).
The \(\Delta\) operator can be regarded as a (partial) function assigning a new sequence of numbers to each sequence of numbers. Therefore the composite \(\Delta^n\) makes sense for any \(n \in \mathbb{N}\).
== Relation to Bashicu matrix system ==
The difference sequence appears in various branches of mathematics, and also in the study of Bashicu matrix system in googology. In order to explain the relation to Bashicu matrix system, we prepare convention and terminology on a bad root searching rule.
=== Bad root searching rule ===
Let \(\textrm{FinSeq}\) denote the set of finite sequences of natural numbers, i.e. non-negative integers. A bad root searching ruleThe terminology is originally invented by the Googology Wiki user koteitan in his study of the classification of BMS here. for \(\textrm{FinSeq}\) is a partial computable function
\begin{eqnarray*}
\textrm{Parent} \colon \textrm{FinSeq} \times \mathbb{N} \to \mathbb{N}
\end{eqnarray*}
such that for any \((a,i)\) in the domain of \(\textrm{Parent}\), \(j = \textrm{Parent}(a,i)\) satisfies the following axioms:
# \(i < \textrm{Lng}(a)\)
# \(j < i\)
# \(a_j \leq a_i\)
The recursive binary relation \(j <_a i\) on \((i,j) \in \mathbb{N}^2\) satisfying \(i,j < \textrm{Lng}(a)\) defined as \(j = \textrm{Parent}(a,i)\) extends to a recursive strict partial ordering. Therefore \(\textrm{Parent}\) allows us to give an interpretation of a finite sequence of natural numbers into a finite set of rooted finite trees whose nodes are labelled with natural numbers.
Denote by \(\textrm{FinSeq}_{\leq} \subset \textrm{FinSeq}\) the subset of monotonically increasing finite sequences. Given a bad root searching rule \(\textrm{Parent}\) for \(\textrm{FinSeq}\), define a total computable function
\begin{eqnarray*}
\textrm{Ancestors} \colon \textrm{FinSeq} & \to & \textrm{FinSeq}_{\leq} \\
a & \mapsto & \textrm{Ancestors}(a)
\end{eqnarray*}
in the following recursive way:
# Put \(L = \textrm{Lng}(a) \in \mathbb{N}\).
# If \(L = 0\), then set \(\textrm{Ancestors}(a) = ()\).
# Suppose \(L > 0\).
## If \((a,L-1)\) is not in the domain of \(\textrm{Parent}\), then set \(\textrm{Ancestors}(a) = (L-1)\).
## Suppose that \((a,L-1)\) is in the domain of \(\textrm{Parent}\).
### Put \(p = \textrm{Parent}(a,L-1) \in \mathbb{N}\).
### Put \(a' = (a_i)_{i=0}^{p} \in \textrm{FinSeq}\)
### Then \(\textrm{Ancestors}(a)\) is the concatenation of \(\textrm{Ancestors}(a')\) and \((L-1)\).
Finally, define a total computable map
\begin{eqnarray*}
\textrm{RightNodes} \colon \textrm{FinSeq} & \to & \textrm{FinSeq}_{\leq} \\
a & \mapsto & \textrm{RightNodes}(a)
\end{eqnarray*}
in the following way:
# Put \(A = \textrm{Ancestors}(a)\).
# Put \(L = \textrm{Lng}(A)\).
# Then \(\textrm{RightNodes}(a)\) is the finite sequence \((a_{A_i})_{i=0}^{L-1}\), which is monotonically increasing by the axioms of a bad root searching rule.
Namely, \(\textrm{RightNodes}(a)\) is the finite sequence of labels of the ancestors of the rightmost node of the rightmost component of the finite sequence of rooted finite trees corresponding to \(a\) through \(\textrm{Parent}\). Be careful that \(\textrm{RightNodes}\) heavily depends on the choice of the bad root searching rule \(\textrm{Parent}\) for \(\textrm{FinSeq}\). 
=== Example ===
The most elementary bad root searching rule for \(\textrm{FinSeq}\) is the one in primitive sequence system, which is a subsystem of many of existing versions of Bashicu matrix. Define a partial computable function
\begin{eqnarray*}
\textrm{Parent} \colon \textrm{FinSeq} \times \mathbb{N} & \to & \mathbb{N} \\
(a,i) & \mapsto & \textrm{Parent}(a,i)
\end{eqnarray*}
in the following recursive way:
# Put \(L = \textrm{Lng}(a)\).
# If \(i \geq L\), then \(\textrm{Parent}(a,i)\) is undefined.
# Suppose \(i < L\).
## If there exists a \(j \in \mathbb{N}\) satisfying \(j < i\) and \(a_j < a_i\), then \(\textrm{Parent}(a,i)\) is defined as the maximum of such a \(j\):
## Otherwise, \(\textrm{Parent}(a,i)\) is undefined.
Be careful that the bad root searching rule for the original primitive sequence system is just defined on standard forms, and hence there are several choices of the behaviour of \(\textrm{Parent}\) for non-standard forms.
If \(a\) is the primitive sequence \((0,1,2,3,4,5,1,2,3,4,3,3,1,2,3,4,2,3,1,2,3,3,2,3)\) of standard form of length \(24\), then the recursive binary relation \(j <_a i\) is expressed in the following diagram:
\begin{eqnarray*}
\begin{array}{ccccccccccc}
\underline{0} & <_a & 1 & <_a & 2 & <_a & 3 & <_a & 4 & <_a & 5 \\
& <_a & 6 & <_a & 7 & <_a & 8 & <_a & 9 \\
& & & & & <_a & 10 \\
& & & & & <_a & 11 \\
& <_a & 12 & <_a & 13 & <_a & 14 & <_a & 15 \\
& & & <_a & 16 & <_a & 17 \\
& <_a & \underline{18} & <_a & 19 & <_a & 20 \\
& & & & & <_a & 21 \\
& & & <_a & \underline{22} & <_a & \underline{23}
\end{array}
\end{eqnarray*}
Therefore \(\textrm{Ancestors}(a)\) is the strictly increasing sequence \((0,18,22,23)\), and \(\textrm{RightNodes}(a)\) is the strictly increasing subsequence \((0,1,2,3)\) of \(a\).
If \(a\) is the primitive sequence \((0,1,2,4,8,1,4,6,7,2,4,5,6,5,6,2,4,5,6,5)\) of non-standard form of length \(20\), then the recursive binary relation \(j <_a i\) is expressed in the following diagram:
\begin{eqnarray*}
\begin{array}{ccccccccccc}
\underline{0} & <_a & 1 & <_a & 2 & <_a & 3 & <_a & 4 \\
& <_a & 
\underline{5} & <_a & 6 & <_a & 7 & <_a & 8 \\
& & & <_a & 9 & <_a & 10 & <_a & 11 & <_a & 12 \\
& & & & & & & <_a & 13 & <_a & 14 \\
& & & <_a & 
\underline{15} & <_a & 
\underline{16} & <_a & 17 & <_a & 18 \\
& & & & & & & <_a & 
\underline{19}
\end{array}
\end{eqnarray*}
Therefore \(\textrm{Ancestors}(a)\) is the strictly increasing sequence \((0,5,15,16,19)\), and \(\textrm{RightNodes}(a)\) is the strictly increasing subsequence \((0,1,2,4,5)\) of \(a\).
=== Coding into a hydra diagram ===
Since the difference sequence of a monotonically increasing sequence of natural number is a sequence of a natural number, the composite \(\Delta \circ \textrm{RightNodes}\) gives a total computable function \(\textrm{Kaiser} \colon \textrm{FinSeq} \setminus \{()\} \to \textrm{FinSeq}\).
As the prime factorisation enables us to encode a finite sequence of natural numbers into a natural number, \(\textrm{Kaiser}\) enables us to encode a finite sequence of finite sequences of natural numbers into a finite sequence of natural numbers. As the Goedel correspondence, i.e. the repetition of the coding by the prime factorisation, enables us to encode a rooted finite tree into a natural number, the repetition of \(\textrm{Kaiser}\) enables us to encode a finite matrices of natural numbers into a finite sequence of natural numbers.
As a result, Bashicu matrix system, which is traditionally regarded as a notation based on finite matrices of natural numbers, can be encoded into a notation system based on finite sequences of natural numbers in a way similar to Koteitan's interpretation into hydra diagramsThe Hydra Diagram based on Upper-Branch-Ignoring Model for understanding BM4 structure. Unlike the Goedel correspondence, the coding is given by the repetition of the bad root searching process, and hence is intuitively hand manageable for googologists who are accustomed to Bashicu matrix system.
The notion of the bad root of a finite sequence \(a\) of natural numbers is defined as a specific entry (if exists) of \(\textrm{Ancestors}(a)\) so that the coding of a Bashicu matrix into a finite sequence of natural numbers preserves the bad root. In this sense, the bad root searching rule actually gives an algorithm to determine the bad root.
== References ==
== See also ==
There are several notations based on difference sequences, which are designed to be variants or extensions of specific versions of Bashicu matrix system or their subsystems. Here are examples of such systems:
* Hyper primitive sequence system
* Y sequence
* YY sequence
* N primitive
Category:Functions
Category:Difference sequence system
Category:Googology in Asia
Category:Sequences