用户: Smile/0-Y 序列

$0$-Y 序列是初等序列的一个扩展, “Y” 得名于其发明者 Yukito. 它与超初等序列 (的典范形式) 在小于 $0\text{-}Y(1,3,6)=hprss(1,4)$ 的部分相同. 它能表示的序数远大于超初等序列, 也超过序数坍缩函数的一些简单扩展所能表示的序数的上界. $0$-Y 序列所能表达的最大序数有时称为 $0$-Y 序数, 记为 $0\text{-}Y(1,\omega )$.

1定义动机

$0$-Y 序列是对超初等序列的一个改进. 直观上, 为了提高整数列表达序数的能力, 进位应该发生得尽可能晚. 在超初等序列中我们已经见过这样的情况: $(1,3,4,5,6,7,\cdots )=(1,3,4,6)$, 而非直接进位为 $(1,3,5)$. 这实际上是标准的 $BO$-九头蛇模式, 于是超初等序列的极限为 $BO$. 若非如此, 则这序列的极限将十分小, 不超过 Veblen 函数能表达的范围.

$0$-Y 序列通过合理的定义, 系统性地增加了晚进位的情形. 例如, $(1,3,5,7,9,\cdots )=(1,3,6)$, 而 $(1,4)=(1,3,6,10,15,21,\cdots )$. 直观上, $(1,4)$ 的展开式中阶差是无界的, 而 $0$-Y 序列的表达能力不弱于超初等序列, 因此可以猜想 $0\text{-}Y(1,4)\ge hprss(1,\omega )$. 事实也确实如此, 且等号成立.

下面我们来解释 $0$-Y 序列的定义. 考虑非空数列 $V=V^0=(a_0,\cdots ,a_m)$. 我们递归地定义一族数列 $V^k,P^k$, 其中 $V^k$ 称为 $V$ 的 $k$ 次阶差, $P^k$ 是 $V^k$ 的父节点偏移量列表.

首先看 $P^0$. 对 $V^0$ 来说, 所谓父节点, 就是在当前位置之前比当前数小的最后一个数 (的位置). 我们规定, 若一个数不大于它之前的所有数, 则父节点是自己. 例如, 序列 $1,4,6,3,7,9,7$ 的父节点偏移量列表为 $0,1,1,3,1,1,3$. 给定了某一层级的父节点偏移量列表 $P^k$, 实际上我们就可以确定这一层级的父节点树. 若一个节点可以通过对另一个节点取若干次父节点得到, 则称它为祖先节点.

我们定义阶差数列 $V^1$ 为对 $V^0$ 除第一项外每项减去父节点的值. 在上面的例子中, $V^1=(1,3,2,2,4,2,4)$.

在定义 $P^1$ 时, 我们有如下额外的限制: $V^1$ 中各项的父节点必须为 $V^0$ 中的祖先节点. 因此, $a_6^1=4$ 的父节点为 $a_3^1$ 而非 $a_5^1$.

我们用箭头表示父节点, 绘图如下. 注意红色项的父节点并非它之前最近的比它小的数.

$$1463797132242412112121100101$$

当取出的阶差以 $1$ 结尾时, 这过程终止.

下面考虑展开. 逐次阶差的最后一行以 $1$ 结尾, 我们不考虑. 对于倒数第二行, 我们记住最后一个元素的父节点, 它正是循环节的开始. 然后我们删去最后一个元素, 再把循环节无限重复, 即得到这一行的展开. 展开中的每个元素的父节点按以下方法决定: (i) 非循环部分元素的父节点即为原先元素的父节点. (ii) 循环部分元素, 其对应原先元素的父节点落在非循环部分的, 则其父节点即为原先元素的父节点. (iii) 循环部分元素, 其对应原先元素的父节点落在循环部分的, 则其父节点即为原先元素的父节点在当前循环节的对应元素.

在上面例子中, $V^2$ 的展开如图所示, 其中绿色为非循环部分, 蓝色与青色为循环部分.

$$121121121121121$$

我们递归地自底而上构造展开, 从而我们假设 $V_{k+1}$ 的末项不为 $1$ 且展开已经构造完成. 为构造 $V_k$, 我们先构造每个节点的父节点. (i) 非循环部分元素的父节点即为原先元素的父节点. (ii) 第一个循环节的首项父节点为原先元素的父节点; 此后各循环节的首项的父节点为前一个循环节的首项. (iii) 循环部分元素除首项外, 其对应原先元素的父节点落在非循环部分的, 则其父节点即为原先元素的父节点. (iv) 循环部分元素除首项外, 其对应原先元素的父节点落在循环部分的, 则其父节点即为原先元素的父节点在当前循环节的对应元素.

下面我们根据父节点来计算 $V_k$ 的展开. 当一个元素的父节点为自身时, 令它的值为 $1$, 否则为父节点的值加上此处阶差数列 $V_{k+1}$ 的值.

在上面的例子中, 我们有如下各阶阶差数列的展开:

$$14637961113101618152224132242352462572121121121121121$$

从而, $(1,4,6,3,7,9,7)=(1,4,6,3,7,9,6,11,13,10,16,18,\cdots )$.

2定义

设 $V=(a_0,\cdots ,a_m)$ 为有限长非空数列, 且满足首项 $a_0=1$, 末项 $a_m\ne 1$.

定义 2.1 (山脉). 我们归纳定义两族长度与 $V$ 相同的数列 $V^k$, $P^k$, 及以下概念:

1.	令 $P^{-1}=(0,)+(1,)\times m$ 为 $0$ 与 $m$ 个 $1$ 构成的数列. 令 $V^0=V$.
2.	假设 $P^k$ 已经定义. 对于每个 $1\le l\le m$, $l-P_l^k$ 称为 $l$ 的 ($k$ 阶) 父节点, 记为 $p_k(l)$.
3.	假设 $P^{k-1}$ 和 $V^k$ 已经定义, 且 $V^k$ 不以 $1$ 结尾. 我们构造 $k$ 阶父节点索引序列 $P^k$. 若 $V_l^k=1$, 令 $P_l^k=0$. 否则令$$P_l^k=l-\max \{x|x\le l且V_x^k\le V_l^k且\exists m,p_{k-1}^m(l)=x\}.$$此即使得其 $k$ 阶父节点为 $k-1$ 阶祖先节点中最近的小于自身的节点.
4.	假设 $V^{k-1}$ 和 $P^{k-1}$ 已经定义, 我们构造 $k$ 阶阶差序列 $V^k$. 令 $V_0^k=1$. 对 $l\ge 2$, 令$$V_l^k=V_l^{k-1}-V_{p_{k-1}(l)}^{k-1}.$$此即 $V^{k-1}$ 中当前节点与父节点的值之差.

令 $K$ 为唯一的正整数 $k$ 使得 $V_m^k=1$. 则现在定义了数列 $V^k$ ($0\le k\le K$) 及 $P^k$ ($-1\le k<K$).

定义 2.2. 给定自然数 $n$, 我们反向归纳定义一族有限长数列 $V^{\prime k}$ 及 $P^{\prime k}$ ($0\le k<K$) 如下:

1.	令 $r=p_{K-1}(m)$ 为 $m$ 的最高阶父节点.
2.	对所有自然数 $0\le k<K$, 令 $V{G}^k=(V_0^k,\cdots ,V_{r-1}^k)$, $V{B}^k=(V_r^k,\cdots ,V_{m-1}^k)$ 分别为 $V^k$ 的前 $r$ 项子列与剩余部分子列, 称为非循环部分与循环部分. 类似定义 $P{G}^k$, $P{B}^k$.
3.	对 $k=K-1$, 令 $V^{\prime k}=V{G}^k+V{B}^k\times n$.
4.	对 $k=K-1$, 令 $P^{\prime k}=P{G}^k+{\sum }_{i=0}^{n}P{B}^{k,(i)}$. 其中, 当 $l-P{B}_l^k<0$ 时, $P{B}_l^{k,(i)}=P{B}_l^k+(m-r)i$, 否则 $P{B}_l^{k,(i)}=P{B}_l^k$.
5.	对 $k<K-1$, 令 $P^{\prime k}=P{G}^k+{\sum }_{i=0}^{n}P{B}^{k,(i)}$. 其中, $P{B}_0^{k,(0)}=P{B}_0^k$, 而当 $i>0$ 时 $P{B}_0^{k,(i)}=m-r$. 对 $l>0$, 当 $l-P{B}_l^k<0$ 时, $P{B}_l^{k,(i)}=P{B}_l^k+(m-r)i$, 否则 $P{B}_l^{k,(i)}=P{B}_l^k$.
6.	对 $k<K-1$, $0\le l<r+(m-r)n$, 若 $P_l^{\prime k}=0$, 则令 $V_l^{\prime k}=1$, 否则令 $V_l^{\prime k}=V_{l-P_l^{\prime k}}^{\prime k}+V_l^{\prime k+1}$.

定义 2.3. 对一个首项为 $1$, 末项大于 $1$ 的有限长正整数序列 $V$, 上述两个定义给出的 $V^{\prime 0}$ 称为 $V$ 的 $n$ 阶 $0$-Y 序列展开, 记为 $Expand(V,n)$.

通过与初等序列, 超初等序列完全相同的办法, 我们可以定义一个 $0$-Y 序列 $V$ 对应的序数 $0\text{-}Y(V)$, 定义 $0$-Y 序列典范形式, 及 $0$-Y 序列大数表示法. 本文略去.

3参考文献

•	Yukito. 0-Y 数列の定義とバシク行列. https://googology.fandom.com/ja/wiki/%E3%83%A6%E3%83%BC%E3%82%B6%E3%83%BC%E3%83%96%E3%83%AD%E3%82%B0:Koteitan/0%E6%95%B0%E5%88%97%E3%81%AE%E5%AE%9A%E7%BE%A9%E3%81%A8%E3%83%90%E3%82%B7%E3%82%AF%E8%A1%8C%E5%88%97.