11,329
pages

Laver tables are an infinite family of magmas that may give rise to a large number function.[1] They were first defined by Richard Laver in 1992. For $$n \geq 0$$, the size-$$n$$ Laver table is a binary operator $$\star$$ over $$\mathbb{Z}_{2^n}$$, with the following properties:

\begin{eqnarray*} a \star 0 & = & 0 \\ a \star 1 & = & a+1 \\ a \star b & = & (a \star (b-1)) \star (a \star 1) \ (b \neq 0,1) \end{eqnarray*}

The period of the function $$a \mapsto 1 \star a$$ depends on $$n$$, and we will denote it by $$p(n)$$. The first few values of $$p(n)$$ are $$1, 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, \ldots$$ (OEIS A098820), a slow-growing function. $$p$$ is provably divergent in the system ZFC + "there exists a rank-into-rank cardinal." Unfortunately, the latter axiom is so strong that there are a few specialists who doubt the consistency of the system. Since the divergence of $$p$$ has not been proven otherwise, it remains an unsolved problem.

Let $$q(n)$$ be minimal so that $$p(q(n)) \geq 2^n$$, the "pseudoinverse" of $$p$$. $$q$$ is a fast-growing function that is total iff $$p$$ is divergent. The first few values of $$q$$ are $$0, 2, 3, 5, 9$$. The existence of $$q(n)$$ for $$n \geq 5$$ has not even been confirmed, but under the assumption of the previously mentioned axiom, Randall Dougherty has shown that $$q^n(1) > f_{\omega+1}(\lfloor \log_3 n \rfloor - 1)$$ in a slightly modified version of the fast-growing hierarchy,[2] and $$q(5) > f_9(f_8(f_8(254)))$$.[3] Dougherty has expressed pessimism about the complexity of proving better lower bounds, and no upper bounds are known as of yet.

Patrick Dehornoy provides a simple algorithm for filling out Laver tables.[4]

The expected size of $$q(6)$$ was very large[5], however no reasoning or proof has been given other than "the strength of set theories required to prove a computable function total", however a computable function $$f$$ need not outgrows all computable functions provably total in a set theory that is known to be required to prove that the function is total.

## Explanation

For $$\lambda \in \text{Lim}$$, let $$\mathcal{E}_\lambda$$ be the set of elementary embeddings $$V_\lambda \mapsto V_\lambda$$. For $$j,k \in \mathcal{E}_\lambda$$, we define the operator $$j\cdot k$$ (or $$jk$$) as follows:

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

Here, $$k \cap V_\alpha$$ is the restriction of $$k$$ to the subset $$\{x \in V_\alpha \mid (x,k(x)) \in V_\alpha\}$$. Although $$k$$ is not an element of the domain $$V_\lambda$$ of $$j$$, $$k \cap V_\alpha$$ is an element of it. That is, we "apply $$j$$ to $$k$$ approaching $$V_\lambda$$." This operator has $$j(kl) = (jk)(jl)$$, a property known as left-selfdistributivity. Laver table is known to be isomorphic to a magma associated to $$\mathcal{E}_\lambda$$ using critical points, and hence is deeply related to a large cardinal axiom.[1]

## Examples

The cyclic group $$\mathbb{Z}_{2^n}$$ can be identified with the set $$\{1,2,3,\ldots,2^n\}$$ through the canonical projection. A size-2 Laver table is shown below:[4]

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

The entries at the first row repeat with a period of 2, and therefore $$p(2) = 2$$.

A size-3 Laver table is shown below:[4]

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

The entries at the first row repeat with a period of 4, and therefore $$p(3) = 4$$.

## Sources

1. Laver, Richard. On the Algebra of Elementary Embeddings of a Rank into Itself. Retrieved 2014-08-23. (Although the last word of the title of the paper is "itself", there is a typo "Inself" in the arXiv page title.)
2. With $$f_{\alpha + 1}(n) = f_\alpha^{n + 1}(1)$$
3. Dougherty, Randall. Critical points in an algebra of elementary embeddings. Retrieved 2014-08-23.
4. Dehornoy, Patrick. Laver Tables (starting on slide 26). Retrieved 2018-12-11.
5. https://googology.wikia.org/wiki/Laver_table?diff=prev&oldid=81250