Editing Laver table

{{Short description|Mathematical concept}}
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 [[algebra]]ic and [[combinatorics|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<ref name="Biane19">{{cite arXiv |last1=Biane |first1=Philippe |title=Laver tables and combinatorics |year=2019 |class=math.CO |eprint=1810.00548 }}</ref>

:<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'':

{{NumBlk|:|<math>p \star_n 1 = p+1 \mod{2^n}</math>|{{EquationRef|1}}}}

and 

{{NumBlk|:|<math>p \star_n (q \star_n r) = (p \star_n q) \star_n (p \star_n r).</math>|{{EquationRef|2}}}}

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

Equation ({{EquationNote|2}}) is known as the ''(left) self-distributive law'', and a set endowed with ''any'' binary operation satisfying this law is called a [[Shelf (mathematics)|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 ({{EquationNote|1}}).

'''Examples''': Following are the first five Laver tables,<ref>{{cite arXiv |last1=Dehornoy |first1=Patrick |title=Two- and three-cocycles for Laver tables |year=2014 |class=math.KT |eprint=1401.2335 }}</ref> i.e. the multiplication tables for the shelves ({1,...,2<sup>''n''</sup>}, <math>\star_n</math>), ''n'' = 0, 1, 2, 3, 4:

<div style=display:inline-table>
{| class=wikitable style="text-align: center;"
! <math>\star_0</math>
! 1
|-
! 1
| 1
|}
</div>
<div style=display:inline-table>
{|
|}</div>
<div style=display:inline-table>
{| class=wikitable style="text-align: center;"
! <math>\star_1</math>
! 1
! 2
|-
! 1
| 2 || 2
|-
! 2
| 1 || 2
|}
</div>
<div style=display:inline-table>
{|
|}</div>
<div style=display:inline-table>
{| 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 style=display:inline-table>
{|
|}</div>
<div style=display:inline-table>
{| 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 style=display:inline-table>
{|
|}</div>
<div style=display:inline-table>
{| class=wikitable style="text-align: center;"
! <math>\star_4</math>
!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
|-
|}
</div>

There is no known [[closed-form expression]] to calculate the entries of a Laver table directly,<ref>{{citation|contribution=Laver Tables: from Set Theory to Braid Theory|title=Annual Topology Symposium, Tohoku University, Japan|year=2014|first=Victoria|last=Lebed|url=http://www.maths.tcd.ie/~lebed/Lebed_ATS14_beamer.pdf}}. See slide 8/33.</ref> but Patrick Dehornoy provides a simple [[algorithm]] for filling out Laver tables.<ref name="Dehornoy">Dehornoy, Patrick. [https://dehornoy.lmno.cnrs.fr/Talks/Dyz.pdf Laver Tables] (starting on slide 26). Retrieved 2025-05-06.</ref>

== 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><ref name="Biane19" />

== Are the first-row periods unbounded? ==

Looking at just the first row in the ''n''-th Laver table, for ''n'' = 0, 1, 2,&nbsp;..., 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&nbsp;2 above. The first few periods are 1, 1, 2, 4, 4, 8, 8, 8, 8, 16, 16,&nbsp;... {{OEIS|A098820}}. This sequence is nondecreasing, and in 1995 Richard Laver [[mathematical proof|proved]], ''under the assumption that there exists a [[rank-into-rank]] (a [[large cardinal]] property)'', that it actually increases without bound. (It is not known whether this is also provable in [[ZFC]] without the additional large-cardinal axiom.)<ref>{{citation
 | last = Laver | first = Richard
 | doi = 10.1006/aima.1995.1014 | doi-access=free
 | issue = 2
 | journal = [[Advances in Mathematics]]
 | mr = 1317621
 | pages = 334–346
 | title = On the algebra of elementary embeddings of a rank into itself
 | volume = 110
 | year = 1995
 | hdl = 10338.dmlcz/127328
 | hdl-access = free
 }}.</ref> 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,&nbsp;A(8,&nbsp;A(8,&nbsp;254))), where A denotes the [[Ackermann function|Ackermann–Péter function]].<ref>{{citation
 | last = Dougherty | first = Randall |author-link=Randall Dougherty 
 | arxiv = math.LO/9205202
 | doi = 10.1016/0168-0072(93)90012-3
 | issue = 3
 | journal = Annals of Pure and Applied Logic
 | mr = 1263319
 | pages = 211–241
 | title = Critical points in an algebra of elementary embeddings
 | volume = 65
 | year = 1993
 | s2cid = 13242324 }}.</ref>

== References ==
{{reflist}}

== Further reading ==
* {{citation |author-link=Patrick Dehornoy |first=Patrick |last=Dehornoy |title=Das Unendliche als Quelle der Erkenntnis |journal=Spektrum der Wissenschaft Spezial |issue=1 |pages=86–90 |year=2001 }}.
* {{citation |first=Patrick |last=Dehornoy |chapter=Diagrams colourings and applications |title=Proceedings of the East Asian School of Knots, Links and Related Topics |year=2004 |chapter-url=http://knot.kaist.ac.kr/2004/proceedings/DEHORNOY.pdf |pages=37–64}}.
* Shelves and the infinite: https://johncarlosbaez.wordpress.com/2016/05/06/shelves-and-the-infinite/

{{DEFAULTSORT:Laver Table}}
[[Category:Mathematical logic]]
[[Category:Combinatorics]]