# Laver table

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Laver_table
> Markdown URL: https://mediated.wiki/source/Laver_table.md
> Source: https://en.wikipedia.org/wiki/Laver_table
> Source revision: 1323991444
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Mathematical concept}}
In [mathematics](/source/mathematics), '''Laver tables''' (named after [Richard Laver](/source/Richard_Laver), who discovered them towards the end of the 1980s in connection with his works on [set theory](/source/set_theory)) are tables of numbers that have certain properties of [algebra](/source/algebra)ic and [combinatorial](/source/combinatorics) interest.  They occur in the study of [racks and quandles](/source/racks_and_quandles).

== Definition ==

For any nonnegative [integer](/source/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](/source/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>} [congruent](/source/modular_arithmetic) to ''x'' [modulo](/source/modular_arithmetic) 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](/source/Shelf_(mathematics)). Thus, the ''n''-th Laver table is just the [multiplication table](/source/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](/source/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](/source/Patrick_Dehornoy) provides a simple [algorithm](/source/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](/source/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? ==
{{unsolved|mathematics|Is ZFC set theory able to prove that the periods of the first rows of Laver tables are 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 [proved](/source/mathematical_proof), ''under the assumption that there exists a [rank-into-rank](/source/rank-into-rank) (a [large cardinal](/source/large_cardinal) property)'', that it actually increases without bound. (It is not known whether this is also provable in [ZFC](/source/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](/source/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](/source/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–Péter function](/source/Ackermann_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

---
Adapted from the Wikipedia article [Laver table](https://en.wikipedia.org/wiki/Laver_table) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Laver_table?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.