階差数列

この記事はスタブ (書きかけ) です。拡充することによって巨大数研究 Wiki を支援することができます。

数列 \(a\) の階差数列 (Difference sequence) は、隣り合う要素との差 \(\Delta a\) を並べた数列である。この記事では、階差数列を利用した巨大数表記システムである階差数列システムについて記述する。

定義[]

空の数列を \(()\) と表記する。数列を \(a\) と表記する。\(a\) の長さ、すなわち要素の個数を \(\textrm{Lng}(a) \in \mathbb{N} \cup \{\infty\}\) と表記する。\(L = \textrm{Lng}(a)\) とする。\(L\) よりも小さな \(i \in \mathbb{N}\) に対して、\(a\) の \((1+i)\) 番目の要素を \(a_i\) とする。\(\textrm{Lng}(a) < \infty\) であれば、\(a\) は \((a_i)_{i=0}^{L-1}\) と表記できる。そうでなければ、\(a\) は \((a_i)_{i=0}^{\infty}\) と表記できる。

\(a\) の階差数列 \(\Delta a\) は、次のように定義される。

\(L = 0\) のとき、\(\Delta a\) は定義されないか、あるいは文脈によっては\(()\) のような特定の数列として定義される。
\(0 < L < \infty\) のとき、\(\Delta a\) は長さ \(L-1\) の有限数列 \((a_{i+1}-a_i)_{i=0}^{L-2}\) によって定義される。
\(L = \infty\) のとき、\(\Delta a\) は無限数列 \((a_{i+1}-a_i)_{i=0}^{\infty}\) によって定義される。

\(\Delta\) 演算子は数列に対して新しい数列を対応させる（部分）関数であるとみなすことができる。したがって、\(n \in \mathbb{N}\) に対して合成関数 \(\Delta^n\) を定めることができる。

バシク行列システムとの関係[]

階差数列は数学の様々な分野で使われ、巨大数論におけるバシク行列システムの研究でも使われる。バシク行列システムとの関係を説明するために、bad root 探索ルールの用語と計算方法を準備する。

Bad root 探索ルール[]

Let \(\textrm{FinSeq}\) denote the set of finite sequences of natural numbers, i.e. non-negative integers. A bad root searching rule^[1] 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\).
1. If \((a,L-1)\) is not in the domain of \(\textrm{Parent}\), then set \(\textrm{Ancestors}(a) = (L-1)\).
2. Suppose that \((a,L-1)\) is in the domain of \(\textrm{Parent}\).
  1. Put \(p = \textrm{Parent}(a,L-1) \in \mathbb{N}\).
  2. Put \(a' = (a_i)_{i=0}^{p} \in \textrm{FinSeq}\)
  3. 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}\).

例[]

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\).
1. 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\):
2. 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,2,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\).

ヒドラ図への変換[]

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 diagrams^[2]. 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.

出典[]

↑ The terminology is originally invented by the Googology Wiki user koteitan in his study of the classification of BMS here.
↑ The Hydra Diagram based on Upper-Branch-Ignoring Model for understanding BM4 structure