3
$\begingroup$

An algebra $(X,*)$ is said to be self-distributive if it satisfies the identity $x*(y*z)=(x*y)*(x*z)$ for all $x,y,z\in X$. If $(X,*)$ is an algebra, then a subset $L\subseteq X$ is said to be a left-ideal if $x*y\in L$ whenever $y\in L$. An element $x$ is said to be a left-identity if $x*y=y$ for $y\in X$. Let $\mathrm{Li}(X)$ denote the set of all left-identities in the algebra $(X,*)$.

A finite self-distributive algebra $X$ is said to be Laver-like if $\mathrm{Li}(X)$ is a left ideal and if there exists some finite linearly ordered set $L$ and a surjective function $\mathrm{crit}:X\rightarrow L$ such that

  1. $\mathrm{crit}(x)=\max(L)$ if and only if $x\in\mathrm{Li}(X)$,

  2. $\mathrm{crit}(x*y)>\mathrm{crit}(y)$ whenever $\mathrm{crit}(y)\geq\mathrm{crit}(x)$, and

  3. $\mathrm{crit}(x*y)=\mathrm{crit}(y)$ whenever $\mathrm{crit}(y)<\mathrm{crit}(x)$.

The function $\mathrm{crit}$ is unique up to isomorphism. We shall say that the algebra $X$ has $|L|$ critical points.

Suppose that $X$ is a finite Laver-like algebra with $n$ critical points generated $(x_{a})_{a\in A}$. Then does there necessarily exist a finite Laver-like algebra $Y$ with $n+1$ critical points generated by $(y_{a})_{a\in A}$ and surjective homomorphism $\phi:Y\rightarrow X$ where $\phi(y_{a})=x_{a}$ for $a\in A$?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

Multigenic Laver tables can go extinct. Examples of multigenic Laver tables that go extinct with 2 generators are rare; one is not likely to find a multigenic Laver table that goes extinct unless one is looking for a multigenic Laver table that goes extinct, and one needs to use computer calculations to produce such an example and prove that it works.

Let us hold to the convention that the implied parentheses are always on the left. For example, $a*b*c*d=((a*b)*c)*d$. If $(X,*)$ is a Laver-like algebra generated by the set $(x_a)_{a\in A}$, then the multigenic Laver table associated with $(X,*)$ and generating set $(x_a)_{a\in A}$ is the algebra $M=M(X,(x_a)_{a\in A})\subseteq A^+$ where $a_1\dots a_r\in M$ if and only if whenever $1\leq s<r$, we have $x_{a_1}*\dots *x_{a_r}\not\in\text{Li}(X)$. The multigenic Laver table $M$ can be endowed with a unique self-distributive operation $*$ such that $\mathbf{x}*a=\mathbf{x}a$ whenever $\mathbf{x}a\in M,a\in A,\mathbf{x}\in M,|\mathbf{x}|>0$ and where $\mathbf{x}*\mathbf{y}=\mathbf{y}$ whenever $\mathbf{x},\mathbf{y}\in M,a\in A,\mathbf{x}a\not\in M$.

Let $X$ be a Laver-like algebra generated by $(x_a)_{a\in A}$, and let $M=M(X,(x_a)_{a\in A})$ denote its multigenic Laver table. Then let $\text{Cov}(M)$ denote the collection of all multigenic Laver tables of the form $N=M(Y,(y_a)_{a\in A})$ where $Y$ is generated by $(y_a)_{a\in A}$ and where there is a homomorphism $\phi:Y\rightarrow X$ with $\phi(y_a)=x_a$ for $a\in A$ and where $Y$ has one more critical point than $X$. It suffices to produce a multigenic Laver table $M$ where $\text{Cov}(M)=\emptyset$. Let $\text{Cov}^*(M)$ be the smallest collection of multigenic Laver tables with $M\in\text{Cov}^*(M)$ and where if $N\in\text{Cov}^*(M)$, then $\text{Cov}(N)\subseteq\text{Cov}^*(N)$. Let $\text{Cov}^+(M)=\text{Cov}^*(M)\setminus\{M\}$.

Let $X$ be a Laver-like algebra generated by $(x_a)_{a\in A}$ and where $\text{crit}:X\rightarrow\{0,\dots,n\}$. Then let $c_0,\dots,c_n\in X$ be elements with $c_i*c_i\in\text{Li}(X)$ and $\text{crit}(c_i)=i$ whenever $0\leq i\leq n$. For $0\leq i<n$, let $p_i((z_a)_{a\in A})$ (haha, that spells pizza) be the non-commutative polynomial defined by $$p_i((z_a)_{a\in A})=\sum\{z_{a_0}\dots z_{a_s}:\text{crit}(x_{a_0}*\dots*x_{a_s})=i,\forall r<s,\text{crit}(x_{a_0}*\dots*x_{a_r})<i\}.$$ If $X$ is a multigenic Laver table over the alphabet $A$ and $x_a=a$ for $a\in A$, then let $\text{Poly}(X)=(p_0((z_a)_{a\in A}),\dots,p_{n-1}((z_a)_{a\in A})).$ If $M$ is a multigenic Laver table, then $M$ can be easily recovered from $\text{Poly}(X)$ since $$\sum\{z_{a_1}\dots z_{a_r}\mid a_1\dots a_r\in M\}=\big(1+p_{n-1}((z_a)_{a\in A})\big)\dots\big(1+p_0((z_a)_{a\in A})\big)\sum_{a\in A}z_a.$$

If $X$ is a Laver-like algebra, then let $\preceq$ be smallest partial ordering where if $x\in X\setminus\text{Li}(X),y\in X$, then $x\preceq x*y$.

Example: Let $M$ be the multigenic Laver table generated by two elements with the following non-commutative polynomial sequence: $$\text{Poly}(M)=( x, x^2, y, x^4, x\cdot y+x^2\cdot y+x^8, x^3\cdot y, x^5\cdot y+x^6\cdot y+x^9\cdot y+x^{10}\cdot y+x^{16}, y^2, y\cdot x^4, y\cdot x\cdot y, (y\cdot x^4)^2, y\cdot x^3\cdot y+y\cdot x^3\cdot (x\cdot y)^2, y\cdot x^2\cdot y+(y\cdot x^4)^4 ).$$

Then $M$ is a multigenic Laver table with $\text{Cov}(M)=\emptyset$ where $|M|=2^{12}\cdot 3^3$.

We found the multigenic Laver table $M$ in two steps. We first search for a multigenic Laver table $N$ with alphabet $\{0,1\}$ with $|\text{Cov}(N)|<3$. After we do this, we search for the multigenic Laver table $M\in\text{Cov}^+(N)$ with $|\text{Cov}(M)|=0$.

A glimpse of the algorithm for computing $\text{Cov}(M)$.

We observe that $|X|\leq|M(X,(x_a)_{a\in A})|$ whenever $X$ is a Laver-like algebra generated by $(x_a)_{a\in A}$. In particular, the algebra $M(X,(x_a)_{a\in A})$ is generally too large to hold in memory when doing computations. On the other hand, given a multigenic Laver table $M$, the smallest algebra $(X,(x_a)_{a\in A})$ with $M=M(X,(x_a)_{a\in A})$ is insufficient for computational purposes; if $N\in\text{Cov}(M)$, then we cannot in general find a $(Y,(y_a)_{a\in A})$ with $N=M(Y,(y_a)_{a\in A})$ where $X$ embeds in $Y$ (we can write $X$ as a quotient of $Y$, but I have found it easier to undo the process of taking a subalgebra than to undo the process of taking a quotient algebra).

Give Laver-like algebra $X$, let $\mathcal{I}_X$ be the smallest congruence on $X$ where if $c,d\in X,\text{crit}(c)=\text{crit}(d),c*c,d*d\in\mathrm{Li}(X)$, then $(c,d)\in\mathcal{I}_X$. If $M$ is a multigenic Laver table, then the quotient algebra $M/\mathcal{I}_M$ is typically small enough to hold in memory and $M=M(M/\mathcal{I}_M,([a])_{a\in A})$ while retaining the algebraic properties that allow for efficient computer calculations.

Suppose that $M$ is a multigenic Laver table over the alphabet $A$ and $N\in\text{Cov}(M)$. Now let $\mathbf{c}\in \text{Li}(M)\setminus\text{Li}(N)$. Then there are homomorphisms $\iota_\mathbf{c}:M\rightarrow N,j:N\rightarrow M$ where $\iota(\mathbf{x})=\mathbf{cx}$ for $\mathbf{x}\in M$ and $j(a)=a$ for $a\in A$. The mappings $\iota_\mathbf{c},j$ induce mappings $\iota^\sharp:M/\mathcal{I}_M\rightarrow N/\mathcal{I}_N,j^\sharp:N/\mathcal{I}_N\rightarrow M/\mathcal{I}_M$ where $\iota^\sharp([\mathbf{x}]_M)=[\mathbf{cx}]_N$ and $j^\sharp([\mathbf{x}]_N)=[j(\mathbf{x})]_M$. The mapping $\iota^\sharp$ is an embedding. The algorithm for computing $N/\mathcal{I}_N$ from $M/\mathcal{I}_M$ consists of extending the algebra $M/\mathcal{I}_M$ to $N/\mathcal{I}_N$; we use backtracking to find all possible extensions of $M/\mathcal{I}_M$ that could possibly be extended to $N/\mathcal{I}_N$ which are isomorphic to the subalgebras of the form $\{[\mathbf{w}]_N:\mathbf{w}\in N,\mathbf{z}\preceq\mathbf{w}\}\subseteq N/\mathcal{I}_N$ for some $\mathbf{z}\in M$.

Here is the code that I have written in the language GAP for which one can compute $\text{Cov}(M)$. For 2 generators, this backtracking algorithm for computing $\text{Cov}(M)$ runs quickly (as long as $\text{Cov}(M)$ and each element in $\text{Cov}(M)$ are not very large) even though I have not been able to obtain any theoretical results on the speed of such a backtracking algorithm. I suspect that this algorithm is not the best algorithm for computing $\text{Cov}(M)$ since $M/\mathcal{I}_M$ can still be quite large, but this algorithm is sufficient for our purposes.

More information about $M$

The algebra $M/\mathcal{I}_M$ has $260$ elements. If $X$ is a Laver-like algebra, then let $\simeq_{\text{cmx}}$ be the congruence on $X$ where we have $x\simeq_{\text{cmx}}y$ if and only if $$c*x*a_1*\dots*a_r\in\text{Li}(X)\Leftrightarrow c*y*a_1*\dots*a_r\in\text{Li}(X)$$ whenever $c,a_1,\dots,a_r\in X$. Then $|M/\simeq_{\text{cmx}}|=86$. The quotient $M/\simeq_{\text{cmx}}$ is the smallest Laver-like algebra where $M(M/\simeq_{\text{cmx}})=M$. I have not been able to find a Laver-like algebra $X$ with 2 generators and fewer than 86 elements with $\text{Cov}(X)=\emptyset$. This procedure also produces many other examples of multigenic Laver tables $P$ with $\text{Cov}(P)=\emptyset.$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .