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 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<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>} congruent to ''x'' 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. 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:

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? == {{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, ..., 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, ... {{OEIS|A098820}}. This sequence is nondecreasing, and in 1995 Richard Laver 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, A(8, A(8, 254))), where A denotes the 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