Laver table

For any nonnegative integer n, the n-th Laver table is the 2ⁿ × 2ⁿ table whose entry in the cell at row p and column q (1 ≤ p,q ≤ 2ⁿ) is defined as^[1]

${\displaystyle L_{n}(p,q):=p\star _{n}q}$

where ${\displaystyle \star _{n}}$ is the unique binary operation on {1,...,2ⁿ} that satisfies the following two equations for all p, q:

${\displaystyle p\star _{n}1=p+1\mod {2^{n}}}$

1

and

${\displaystyle p\star _{n}(q\star _{n}r)=(p\star _{n}q)\star _{n}(p\star _{n}r).}$

2

Note: Equation (1) uses the notation ${\displaystyle x{\bmod {2}}^{n}}$ to mean the unique member of {1,...,2ⁿ} congruent to x modulo 2ⁿ.

Equation (2) is known as the (left) self-distributive law, and a set endowed with any binary operation satisfying this law is called a shelf. Thus, the n-th Laver table is just the multiplication table for the unique shelf ({1,...,2ⁿ}, ${\displaystyle \star _{n}}$) that satisfies Equation (1).

Examples: Following are the first five Laver tables,^[2] i.e. the multiplication tables for the shelves ({1,...,2ⁿ}, ${\displaystyle \star _{n}}$), n = 0, 1, 2, 3, 4:

${\displaystyle \star _{0}}$	1
1	1

${\displaystyle \star _{1}}$	1	2
1	2	2
2	1	2

${\displaystyle \star _{2}}$	1	2	3	4
1	2	4	2	4
2	3	4	3	4
3	4	4	4	4
4	1	2	3	4

${\displaystyle \star _{3}}$	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

${\displaystyle \star _{4}}$	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

There is no known closed-form expression to calculate the entries of a Laver table directly,^[3] but Patrick Dehornoy provides a simple algorithm for filling out Laver tables.^[4]

1. For all p, q in {1,...,2ⁿ}: ${\displaystyle \ \ 2^{n}\star _{n}q=q;\ \ p\star _{n}2^{n}=2^{n};\ \ (2^{n}-1)\star _{n}q=2^{n};\ \ p\star _{n}2^{n-1}=2^{n}{\text{ if }}p\neq 2^{n}}$.
2. For all p in {1,...,2ⁿ}: ${\displaystyle \ \ (p\star _{n}q)_{q=1,2,3,...}}$ is periodic with period π_n(p) equal to a power of two.
3. For all p in {1,...,2ⁿ}: ${\displaystyle \ \ (p\star _{n}q)_{q=1,2,3,...,\pi _{n}(p)}}$ is strictly increasing from ${\displaystyle p\star _{n}1=p+1\ }$ to ${\displaystyle \ p\star _{n}\pi _{n}(p)=2^{n}}$.
4. For all p,q: ${\displaystyle \ p\star _{n}q=(p+1)^{(q)},{\text{ where }}x^{(1)}=x,\ x^{(k+1)}=x^{(k)}\star _{n}x.}$^[1]