Laver Table

Laver 表，是一种无限族的原群，它们产生了一个可能增长极快的函数。它们由理查德·拉弗（Richard Laver）于 1992 年首次定义。

定义

Laver 表基于以下定理：对于每个$n\ge 0$，在有限序数集 $\{1,\cdots ,2^n\}$ 上存在唯一的二元运算 ${\star }_n$，满足：​

\begin{eqnarray*}a \star_n 0 & = & 0 \\a \star_n 1 & = & (a+1) \mod 2^n \\a \star_n i & = & (a \star_n (i-1)) \star_n (a \star_n 1) \ (i \neq 0,1)\end{eqnarray*}

Laver 表 $A_n$ 定义为唯一的取值为 $a{\star }_{n}b$ 的 $2^n\times 2^n$ 表。Laver 表可以用此进行计算。

注意这一定理仅适用于 2 的幂。假如我们考虑的二元运算作用于一般的 $\{1,\cdots ,a\}$ 上，其中 $a\ne 2^n$，则这样的二元运算 ${\star }_n$ 将不是存在且唯一的。

我们定义函数 $a\mapsto 1{\star }_{n}a$ 的周期为 p(n)。

定义 q(n) 为函数 p(n) 的“伪逆”，即 $q(n)=\min \{N|p(N)\ge 2^n\}$。

强度

p(n) 的前几个值为1, 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, …，这是一个增长缓慢的函数。

p 在 ZFC+存在 rank-into-rank 基数（或 ZFC+I3）公理系统中被证明是发散的。但遗憾的是，后者这一公理过于强大，以至于少数专家对其系统的相容性存疑。由于 p 的发散性尚未通过其他方式证明，这仍是一个未解问题。用 googology 更熟悉（但是并不严格）的说法，我们目前认为 q(n) 的增长率的上界为 PTO(ZFC+I3)。

q 是一个快速增长的函数，其全域性当且仅当 p 发散。q(n) 的前几个值为 0, 2, 3, 5, 9。尽管 n≥5 时 q(n) 的存在性尚未被确认，但在上述公理假设下，Randall Dougherty 证明，在快速增长层级结构的一个稍作修改的版本中，$q^n(1)>f_{\omega +1}(\lfloor {\log }_{3}n\rfloor -1)$，且 $q(5)>f_9(f_8(f_8(254)))$。Dougherty 对证明更优下界的可能性表示悲观，目前也没有更严格的上界已知。Laver 表是可计算的，因此 q(n)在较小时会被忙碌海狸函数 Σ(n) 超越。

Patrick Dehornoy 提供了一种填充 Laver 表的简单算法。然而，每个表格的大小以及 $\star$ 运算所定义的循环群的规模都呈指数级增长，因此这目前是一个NP问题。

q(6) 的预期规模非常大，但除了“证明可计算函数全域所需的集合论强度”外，没有给出其他理由或证明。然而，一个可计算函数f并不需要超过所有在已知需要证明该函数全域的集合论中可证明全域的可计算函数。

第六个 Laver 表的灰度图

解释

对于极限序数 $\lambda$，设 ${{ℰ}}_{\lambda }$​ 为所有初等嵌入 $V_{\lambda }\mapsto V_{\lambda }$​ 的集合。对 $j,k\in {{ℰ}}_{\lambda }$​，我们定义运算符 $j\cdot k$（或记为 $jk$）如下：

$j\cdot k=\bigcup _{\alpha <\lambda }j(k\cap V_{\alpha })$

此处，$k\cap V_{\alpha }$​ 表示 $k$ 在集合 $\{x\in V_{\alpha }\mid (x,k(x))\in V_{\alpha }\}$ 上的限制。虽然 $k$ 本身不属于 $j$ 的定义域 $V_{\lambda }$​，但 $k\cap V_{\alpha }$​ 是它的元素。这一操作可理解为“对逐渐接近 $V_{\lambda }$ 的 $k$ 应用 $j$”。该运算符满足性质 $j(kl)=(jk)(jl)$，此性质被称为左自分布性（left-selfdistributivity）。已知 Laver 表与通过临界点关联到 ${{ℰ}}_{\lambda }$ 的原群同构，因此与大基数公理密切相关。

取值

Laver 表

以下展示了前 6 个 Laver 表。

${\star }_0$ 的 Laver 表

	1
1	1

${\star }_1$ 的 Laver 表

	1	2
1	2	2
2	1	2

${\star }_2$ 的 Laver 表

	1	2	3	4
1	2	4	2	4
2	3	4	2	4
3	4	4	4	4
4	1	2	3	4

${\star }_3$ 的 Laver 表

	1	2	3	4	5	6	7	8
1	2	4	6	8	2	4	6	8
2	3	4	7	8	3	4	7	8
3	4	8	4	8	4	8	4	8
4	5	6	7	8	5	6	7	8
5	6	8	6	8	6	8	6	8
6	7	8	7	8	7	8	7	8
7	8	8	8	8	8	8	8	8
8	1	2	3	4	5	6	7	8

${\star }_4$ 的 Laver 表

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1	2	12	14	16	2	12	14	16	2	12	14	16	2	12	14	16
2	3	12	15	16	3	12	15	16	3	12	15	16	3	12	15	16
3	4	8	12	16	4	8	12	16	4	8	12	16	4	8	12	16
4	5	6	7	8	13	14	15	16	5	6	7	8	13	14	15	16
5	6	8	14	16	6	8	14	16	6	8	14	16	6	8	14	16
6	7	8	15	16	7	8	15	16	7	8	15	16	7	8	15	16
7	8	16	8	16	8	16	8	16	8	16	8	16	8	16	8	16
8	9	10	11	12	13	14	15	16	9	10	11	12	13	14	15	16
9	10	12	14	16	10	12	14	16	10	12	14	16	10	12	14	16
10	11	12	15	16	11	12	15	16	11	12	15	16	11	12	15	16
11	12	16	12	16	12	16	12	16	12	16	12	16	12	16	12	16
12	13	14	15	16	13	14	15	16	13	14	15	16	13	14	15	16
13	14	16	14	16	14	16	14	16	14	16	14	16	14	16	14	16
14	15	16	15	16	15	16	15	16	15	16	15	16	15	16	15	16
15	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16	16
16	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16

${\star }_5$ 的 Laver 表

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
1	2	12	14	16	18	28	30	32	2	12	14	16	18	28	30	32	2	12	14	16	18	28	30	32	2	12	14	16	18	28	30	32
2	3	12	15	16	19	28	31	32	3	12	15	16	19	28	31	32	3	12	15	16	19	28	31	32	3	12	15	16	19	28	31	32
3	4	8	12	16	20	24	28	32	4	8	12	16	20	24	28	32	4	8	12	16	20	24	28	32	4	8	12	16	20	24	28	32
4	5	6	7	8	13	14	15	16	21	22	23	24	29	30	31	32	5	6	7	8	13	14	15	16	21	22	23	24	29	30	31	32
5	6	24	30	32	6	24	30	32	6	24	30	32	6	24	30	32	6	24	30	32	6	24	30	32	6	24	30	32	6	24	30	32
6	7	24	31	32	7	24	31	32	7	24	31	32	7	24	31	32	7	24	31	32	7	24	31	32	7	24	31	32	7	24	31	32
7	8	16	24	32	8	16	24	32	8	16	24	32	8	16	24	32	8	16	24	32	8	16	24	32	8	16	24	32	8	16	24	32
8	9	10	11	12	13	14	15	16	25	26	27	28	29	30	31	32	9	10	11	12	13	14	15	16	25	26	27	28	29	30	31	32
9	10	28	30	32	10	28	30	32	10	28	30	32	10	28	30	32	10	28	30	32	10	28	30	32	10	28	30	32	10	28	30	32
10	11	28	31	32	11	28	31	32	11	28	31	32	11	28	31	32	11	28	31	32	11	28	31	32	11	28	31	32	11	28	31	32
11	12	16	28	32	12	16	28	32	12	16	28	32	12	16	28	32	12	16	28	32	12	16	28	32	12	16	28	32	12	16	28	32
12	13	14	15	16	29	30	31	32	13	14	15	16	29	30	31	32	13	14	15	16	29	30	31	32	13	14	15	16	29	30	31	32
13	14	16	30	32	14	16	30	32	14	16	30	32	14	16	30	32	14	16	30	32	14	16	30	32	14	16	30	32	14	16	30	32
14	15	16	31	32	15	16	31	32	15	16	31	32	15	16	31	32	15	16	31	32	15	16	31	32	15	16	31	32	15	16	31	32
15	16	32	16	32	16	32	16	32	16	32	16	32	16	32	16	32	16	32	16	32	16	32	16	32	16	32	16	32	16	32	16	32
16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
17	18	28	30	32	18	28	30	32	18	28	30	32	18	28	30	32	18	28	30	32	18	28	30	32	18	28	30	32	18	28	30	32
18	19	28	31	32	19	28	31	32	19	28	31	32	19	28	31	32	19	28	31	32	19	28	31	32	19	28	31	32	19	28	31	32
19	20	24	28	32	20	24	28	32	20	24	28	32	20	24	28	32	20	24	28	32	20	24	28	32	20	24	28	32	20	24	28	32
20	21	22	23	24	29	30	31	32	21	22	23	24	29	30	31	32	21	22	23	24	29	30	31	32	21	22	23	24	29	30	31	32
21	22	24	30	32	22	24	30	32	22	24	30	32	22	24	30	32	22	24	30	32	22	24	30	32	22	24	30	32	22	24	30	32
22	23	24	31	32	23	24	31	32	23	24	31	32	23	24	31	32	23	24	31	32	23	24	31	32	23	24	31	32	23	24	31	32
23	24	32	24	32	24	32	24	32	24	32	24	32	24	32	24	32	24	32	24	32	24	32	24	32	24	32	24	32	24	32	24	32
24	25	26	27	28	29	30	31	32	25	26	27	28	29	30	31	32	25	26	27	28	29	30	31	32	25	26	27	28	29	30	31	32
25	26	28	30	32	26	28	30	32	26	28	30	32	26	28	30	32	26	28	30	32	26	28	30	32	26	28	30	32	26	28	30	32
26	27	28	31	32	27	28	31	32	27	28	31	32	27	28	31	32	27	28	31	32	27	28	31	32	27	28	31	32	27	28	31	32
27	28	32	28	32	28	32	28	32	28	32	28	32	28	32	28	32	28	32	28	32	28	32	28	32	28	32	28	32	28	32	28	32
28	29	30	31	32	29	30	31	32	29	30	31	32	29	30	31	32	29	30	31	32	29	30	31	32	29	30	31	32	29	30	31	32
29	30	32	30	32	30	32	30	32	30	32	30	32	30	32	30	32	30	32	30	32	30	32	30	32	30	32	30	32	30	32	30	32
30	31	32	31	32	31	32	31	32	31	32	31	32	31	32	31	32	31	32	31	32	31	32	31	32	31	32	31	32	31	32	31	32
31	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32	32
32	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32

q 函数

事实上 $p(n)$ 是一个增长速度非常缓慢的函数。

我们有

• $q(0)=0$
• $q(1)=2$
• $q(2)=3$
• $q(3)=5$
• $q(4)=9$
• $q(5)>f_9(f_8(f_8(254)))$，其中这里的 FGH 改版定义为 $f_{\alpha +1}(n)=f_{\alpha }^{n+1}(n)$