Laver Table

Laver 表（Laver Table）是 Richard Laver 在 1992 年提出的一个增长速度很快的表。

定义

考虑作用于 $\{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$ 将不是存在且唯一的。

我们定义如下函数的周期为 p(n):

• $2^n\to 2^n$
• $a\mapsto 1{\star }_{n}a$

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

取值

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)$

强度

Dougherty 证明了 $q^n(1)>f_{\omega +1}(\lfloor log3n\rfloor -1)$。

事实上，二元关系 ${\star }_n$ 的存在唯一性以及函数 p(n) 的发散性并非显然的结果，它实际上与集合论中的嵌入有着深刻的联系。

事实上，p(n) 发散的结论是在 I3 公理下才能够得到证明的。因此，作为一个快速增长的函数，q(n) 的完全性（即在所有自然数 n 下都有定义）在 ZFC+I3

下得到了证明。用 googology 更熟悉（但是并不严格）的说法，我们目前认为 q(n) 的增长率的上界为 PTO(ZFC+I3)。