Laver table

Laver tables are an infinite family of magmas that give rise to a potentially extremely fast-growing function. (Although the last word of the title of the paper is "itself", there is a typo "Inself" in the arXiv page title.) They were first defined by Richard Laver in 1992. Laver tables are based on the theorem stating that for each \(n \geq 0\), there is a unique binary operator \(\star_n\) over the finite ordinal \(2^n = \{0,1,\ldots,2^n-1\}\):
\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*}
The Laver tables are then the unique \(2^n\times 2^n\) tables with the values of \(a\star_n b\). This theorem can only hold for powers of \(2\). The period of the function 
\begin{eqnarray*}
2^n & \to & 2^n \\
a & \mapsto & 1 \star_n a
\end{eqnarray*}
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\) (), 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.
Define \(q(n)=\min\{N~|~p(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,With \(f_{\alpha + 1}(n) = f_\alpha^{n + 1}(1)\) and \(q(5) > f_9(f_8(f_8(254)))\). Dougherty has expressed pessimism about the complexity of proving better lower bounds, and no stricter upper bounds are known as of yet. Laver tables are computable, thus \(q(n)\) gets outgrown by \(\Sigma(n)\) fairly early on.
Patrick Dehornoy provides a simple algorithm for filling out Laver tables.Dehornoy, Patrick. Laver Tables (starting on slide 26). Retrieved 2018-12-11. However, the size of each table and the cyclical group over which the \(\star\) operator is defined both go up exponentially, thus this is so far an NP problem.
The expected size of \(q(6)\) was very largehttps://googology.wikia.org/wiki/Laver_table?diff=prev&oldid=81250, 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\) needs not outgrow 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.
== Examples ==
The domain \(2^n\) of the binary operator \(\star_n\) is naturally identified with the cyclic group \(\mathbb{Z}_{2^n}\), and \(\mathbb{Z}_{2^n}\) can be also identified with the set \(\{1,2,3,\ldots,2^n\}\) through the canonical projection. Namely, \(2^n\) can be identified with \(\{1,2,\ldots, 2^n\}\) by the bijection assigning \(2^n\) to \(0\) and \(i\) to each non-zero \(i\). Through the identification, the size-2 Laver table is shown below:
 	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\).
The size-3 Laver table is shown below:
 	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 ==
== External Links ==
* 猫山にゃん太, Laver table - レイバーのテーブル, GitHub Page. (javascript program computing the table)
* 猫山にゃん太, レイバーのテーブル, YouTube. (Introduction to Laver table for people who know Japanese)
* Mitsuki1729, scratch巨大数選手権コンテスト レイバーのテーブル, scratch project. (scratch program computing \(q(5)\))
ja:レイバーのテーブル
fr:Table Laver
Category:Functions
Category:Numbers
Category:Unsolved problems
Category:Unnamed numbers