Laver table

Last updated December 31, 2024

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ⁿ × 2ⁿ table whose entry in the cell at row p and column q (1 ≤ p,q ≤ 2ⁿ) is defined as^[1]

L_{n}(p,q):=p\star _{n}q

where $\star _{n}$ is the unique binary operation that satisfies the following two equations for all p, q in {1,...,2ⁿ}:

p\star _{n}1=p+1\mod {2^{n}}

1

and

p\star _{n}(q\star _{n}r)=(p\star _{n}q)\star _{n}(p\star _{n}r).

2

Note: Equation ( 1 ) uses the notation $x{\bmod {2}}^{n}$ to mean the unique member of {1,...,2ⁿ} congruent to x modulo 2ⁿ.

Equation ( 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ⁿ}, $\star _{n}$ ) that satisfies Equation ( 1 ).

Examples: Following are the first five Laver tables,^[2] i.e. the multiplication tables for the shelves ({1,...,2ⁿ}, $\star _{n}$ ), n = 0, 1, 2, 3, 4:

$\star _{0}$	1
1	1

$\star _{1}$	1	2
1	2	2
2	1	2

$\star _{2}$	1	2	3	4
1	2	4	2	4
2	3	4	3	4
3	4	4	4	4
4	1	2	3	4

$\star _{3}$	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

$\star _{4}$	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

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

Properties

For all p, q in {1,...,2ⁿ}: $\ \ 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\neq 2^{n}$ .
For all p in {1,...,2ⁿ}: $\ \ (p\star _{n}q)_{q=1,2,3,...}$ is periodic with period π_n(p) equal to a power of two.
For all p in {1,...,2ⁿ}: $\ \ (p\star _{n}q)_{q=1,2,3,...,\pi _{n}(p)}$ is strictly increasing from $p\star _{n}1=p+1\$ to $\ p\star _{n}\pi _{n}(p)=2^{n}$ .
For all p,q: $\ p\star _{n}q=(p+1)^{(q)},{\text{ where }}x^{(1)}=x,\ x^{(k+1)}=x^{(k)}\star _{n}x.$ ^[1]

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, ... (sequence A098820 in the OEIS ). 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.)^[5] 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.^[6]

Related Research Articles

Informally, a definable real number is a real number that can be uniquely specified by its description. The description may be expressed as a construction or as a formula of a formal language. For example, the positive square root of 2, $, can be defined as the unique positive solution to the equation, and it can be constructed with a compass and straightedge.$

The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter $ζ$ (zeta), is a mathematical function of a complex variable defined as $for, and its analytic continuation elsewhere.$

<span class="mw-page-title-main">Imaginary unit</span> Principal square root of −1

The imaginary unit or unit imaginary number is a mathematical constant that is a solution to the quadratic equation $x 2 + 1 = 0.$ Although there is no real number with this property, $i$ can be used to extend the real numbers to what are called complex numbers, using addition and multiplication. A simple example of the use of $i$ in a complex number is $2 + 3 i .$

<span class="mw-page-title-main">Exponentiation</span> Arithmetic operation

In mathematics, exponentiation is an operation involving two numbers: the base and the exponent or power. Exponentiation is written as $b n$ , where $b$ is the base and $n$ is the power; often said as " $b$ to the power $n$ ". When $n$ is a positive integer, exponentiation corresponds to repeated multiplication of the base: that is, $b n$ is the product of multiplying $n$ bases: $In particular, .$

<span class="mw-page-title-main">Euler's constant</span> Constant value used in mathematics

Euler's constant is a mathematical constant, usually denoted by the lowercase Greek letter gamma, defined as the limiting difference between the harmonic series and the natural logarithm, denoted here by $log$ :

In mathematics, the orthogonal group in dimension $n$ , denoted $O(n)$ , is the group of distance-preserving transformations of a Euclidean space of dimension $n$ that preserve a fixed point, where the group operation is given by composing transformations. The orthogonal group is sometimes called the general orthogonal group, by analogy with the general linear group. Equivalently, it is the group of $n \times n$ orthogonal matrices, where the group operation is given by matrix multiplication (an orthogonal matrix is a real matrix whose inverse equals its transpose). The orthogonal group is an algebraic group and a Lie group. It is compact.

In mathematics, the Cayley–Dickson construction, sometimes also known as the Cayley–Dickson process or the Cayley–Dickson procedure produces a sequence of algebras over the field of real numbers, each with twice the dimension of the previous one. It is named after Arthur Cayley and Leonard Eugene Dickson. The algebras produced by this process are known as Cayley–Dickson algebras, for example complex numbers, quaternions, and octonions. These examples are useful composition algebras frequently applied in mathematical physics.

In mathematics, a transcendental function is an analytic function that does not satisfy a polynomial equation whose coefficients are functions of the independent variable that can be written using only the basic operations of addition, subtraction, multiplication, and division. This is in contrast to an algebraic function.

In number theory, a formula for primes is a formula generating the prime numbers, exactly and without exception. Formulas for calculating primes do exist; however, they are computationally very slow. A number of constraints are known, showing what such a "formula" can and cannot be.

In differential geometry, a field in mathematics, a Poisson manifold is a smooth manifold endowed with a Poisson structure. The notion of Poisson manifold generalises that of symplectic manifold, which in turn generalises the phase space from Hamiltonian mechanics.

In mathematics, Mathieu functions, sometimes called angular Mathieu functions, are solutions of Mathieu's differential equation

In mathematics, a translation plane is a projective plane which admits a certain group of symmetries. Along with the Hughes planes and the Figueroa planes, translation planes are among the most well-studied of the known non-Desarguesian planes, and the vast majority of known non-Desarguesian planes are either translation planes, or can be obtained from a translation plane via successive iterations of dualization and/or derivation.

In mathematics, a Gelfand pair is a pair (G, K ) consisting of a group G and a subgroup K (called a Euler subgroup of G) that satisfies a certain property on restricted representations. The theory of Gelfand pairs is closely related to the topic of spherical functions in the classical theory of special functions, and to the theory of Riemannian symmetric spaces in differential geometry. Broadly speaking, the theory exists to abstract from these theories their content in terms of harmonic analysis and representation theory.

In mathematics, a Pfister form is a particular kind of quadratic form, introduced by Albrecht Pfister in 1965. In what follows, quadratic forms are considered over a field F of characteristic not 2. For a natural number n, an n-fold Pfister form over F is a quadratic form of dimension 2ⁿ that can be written as a tensor product of quadratic forms

In mathematics, an elliptic hypergeometric series is a series Σc_n such that the ratio c_n/c_n−1 is an elliptic function of n, analogous to generalized hypergeometric series where the ratio is a rational function of n, and basic hypergeometric series where the ratio is a periodic function of the complex number n. They were introduced by Date-Jimbo-Kuniba-Miwa-Okado (1987) and Frenkel & Turaev (1997) in their study of elliptic 6-j symbols.

The Tracy–Widom distribution is a probability distribution from random matrix theory introduced by Craig Tracy and Harold Widom. It is the distribution of the normalized largest eigenvalue of a random Hermitian matrix. The distribution is defined as a Fredholm determinant.

In mathematics, the pentagram map is a discrete dynamical system on the moduli space of polygons in the projective plane. The pentagram map takes a given polygon, finds the intersections of the shortest diagonals of the polygon, and constructs a new polygon from these intersections. Richard Schwartz introduced the pentagram map for a general polygon in a 1992 paper though it seems that the special case, in which the map is defined for pentagons only, goes back to an 1871 paper of Alfred Clebsch and a 1945 paper of Theodore Motzkin. The pentagram map is similar in spirit to the constructions underlying Desargues' theorem and Poncelet's porism. It echoes the rationale and construction underlying a conjecture of Branko Grünbaum concerning the diagonals of a polygon.

This is a glossary of properties and concepts in algebraic topology in mathematics.

In mathematics, an algebra such as $has multiplication whose associativity is well-defined on the nose. This means for any real numbers we have$

In mathematics, a sparse polynomial is a polynomial that has far fewer terms than its degree and number of variables would suggest. For example, $is a sparse polynomial as it is a trinomial with a degree of .$

References

1 2 Biane, Philippe (2019). "Laver tables and combinatorics". arXiv: 1810.00548 [math.CO].
↑ Dehornoy, Patrick (2014). "Two- and three-cocycles for Laver tables". arXiv: 1401.2335 [math.KT].
↑ Lebed, Victoria (2014), "Laver Tables: from Set Theory to Braid Theory", Annual Topology Symposium, Tohoku University, Japan (PDF). See slide 8/33.
↑ Dehornoy, Patrick. Laver Tables (starting on slide 26). Retrieved 2018-12-11.
↑ Laver, Richard (1995), "On the algebra of elementary embeddings of a rank into itself", Advances in Mathematics , 110 (2): 334–346, doi: 10.1006/aima.1995.1014 , hdl: 10338.dmlcz/127328 , MR 1317621 .
↑ Dougherty, Randall (1993), "Critical points in an algebra of elementary embeddings", Annals of Pure and Applied Logic, 65 (3): 211–241, arXiv: math.LO/9205202 , doi:10.1016/0168-0072(93)90012-3, MR 1263319, S2CID 13242324 .