Laver table

In mathematics, Laver tables (named after Richard Laver, who discovered them towards the end of the 1980s in connection with his works on set theory) are tables of numbers that have certain properties of algebraic and combinatorial interest. They occur in the study of racks and quandles.

Definition

For any nonnegative integer n, the n-th Laver table is the 2<sup>n</sup> × 2<sup>n</sup> table whose entry in the cell at row p and column q (1 ≤ p,q ≤ 2<sup>n</sup>) is defined as

:<math>L_n(p, q) := p \star_n q</math>

where <math>\star_n</math> is the unique binary operation on {1,...,2<sup>n</sup>} that satisfies the following two equations for all p, q:

and

Note: Equation () uses the notation <math>x \bmod 2^n</math> to mean the unique member of {1,...,2<sup>n</sup>} congruent to x modulo 2<sup>n</sup>.

Equation () 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<sup>n</sup>}, <math>\star_n</math>) that satisfies Equation ().

Examples: Following are the first five Laver tables, i.e. the multiplication tables for the shelves ({1,...,2<sup>n</sup>}, <math>\star_n</math>), n = 0, 1, 2, 3, 4:

{| class=wikitable style="text-align: center;"

! <math>\star_0</math>

! 1

| 1

</div>

|}</div>

{| class=wikitable style="text-align: center;"

! <math>\star_1</math>

! 1

! 2

! 1

| 2 || 2

! 2

| 1 || 2

</div>

|}</div>

{| class=wikitable style="text-align: center;"

! <math>\star_2</math>

! 1

! 2

! 3

! 4

! 1

| 2 || 4 || 2 || 4

! 2

| 3 || 4 || 3 || 4

! 3

| 4 || 4 || 4 || 4

! 4

| 1 || 2 || 3 || 4

</div>

|}</div>

{| class=wikitable style="text-align: center;"

! <math>\star_3</math>

! 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

</div>

|}</div>

{| class=wikitable style="text-align: center;"

! <math>\star_4</math>

!10

!11

!12

!13

!14

!15

!16

| 2 || 12 || 14 || 16 || 2 || 12 || 14 || 16 || 2 || 12 || 14 || 16 || 2 || 12 || 14 || 16

| 3 || 12 || 15 || 16 || 3 || 12 || 15 || 16 || 3 || 12 || 15 || 16 || 3 || 12 || 15 || 16

| 4 || 8 || 12 || 16 || 4 || 8 || 12 || 16 || 4 || 8 || 12 || 16 || 4 || 8 || 12 || 16

| 5 || 6 || 7 || 8 || 13 || 14 || 15 || 16 || 5 || 6 || 7 || 8 || 13 || 14 || 15 || 16

| 6 || 8 || 14 || 16 || 6 || 8 || 14 || 16 || 6 || 8 || 14 || 16 || 6 || 8 || 14 || 16

| 7 || 8 || 15 || 16 || 7 || 8 || 15 || 16 || 7 || 8 || 15 || 16 || 7 || 8 || 15 || 16

| 8 || 16 || 8 || 16 || 8 || 16 || 8 || 16 || 8 || 16 || 8 || 16 || 8 || 16 || 8 || 16

| 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16 || 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16

| 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

</div>

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

Properties

For all p, q in {1,...,2<sup>n</sup>}: <math>\ \ 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\ne 2^n</math>.
For all p in {1,...,2<sup>n</sup>}: <math>\ \ (p \star_n q)_{q=1,2,3,...}</math> is periodic with period π<sub>n</sub>(p) equal to a power of two.
For all p in {1,...,2<sup>n</sup>}: <math>\ \ (p \star_n q)_{q=1,2,3,...,\pi_n(p)}</math> is strictly increasing from <math>p \star_n 1 = p+1\ </math> to <math>\ p \star_n \pi_n(p) = 2^n</math>.
For all p,q: <math>\ p \star_n q = (p+1)^{(q)}, \text{ where } x^{(1)}=x,\ x^{(k+1)}=x^{(k)} \star_n x.</math> In any case, it grows extremely slowly; Randall Dougherty showed that 32 cannot appear in this sequence (if it ever does) until n > A(9, A(8, A(8, 254))), where A denotes the Ackermann–Péter function.

Definition

Properties

References

Further reading