Laver table


In mathematics, Laver tables 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 2n × 2n table whose entry in the cell at row p and column q is defined as
where is the unique binary operation on that satisfies the following two equations for all p, q:
and
Note: Equation uses the notation to mean the unique member of congruent to x modulo 2n.
Equation is known as the 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 that satisfies Equation.
Examples: Following are the first five Laver tables, i.e. the multiplication tables for the shelves, n = 0, 1, 2, 3, 4:









1234
12424
23434
34444
41234





12345678
124682468
234783478
348484848
456785678
568686868
678787878
788888888
812345678





12345678910111213141516
12121416212141621214162121416
23121516312151631215163121516
3481216481216481216481216
4567813141516567813141516
5681416681416681416681416
6781516781516781516781516
7816816816816816816816816
8910111213141516910111213141516
910121416101214161012141610121416
1011121516111215161112151611121516
1112161216121612161216121612161216
1213141516131415161314151613141516
1314161416141614161416141614161416
1415161516151615161516151615161516
1516161616161616161616161616161616
1612345678910111213141516


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

  1. For all p, q in :.
  2. For all p in : is periodic with period πn equal to a power of two.
  3. For all p in : is strictly increasing from to.
  4. For all p,''q'':

    Are the first-row periods unbounded?

Looking at just the first row in the n-th Laver table, for n = 0, 1, 2, ..., the entries in each first row are seen to be periodic with a period that's always a power of two, as mentioned in Property 2 above. The first few periods are 1, 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, .... This sequence is nondecreasing, and in 1995 Richard Laver proved, under the assumption that there exists a rank-into-rank , that it actually increases without bound. In any case, it grows extremely slowly; Randall Dougherty showed that 32 cannot appear in this sequence until n > A, where A denotes the Ackermann–Péter function.