Endomorphic Laver tables can be computed efficiently

The partially endomorphic Laver tables are the generalizations of the notion of the classical Laver table to algebraic structures which may have an arbitrary number of fundamental operations each of arbitrary arity and where only some of the fundamental operations are required to be self-distributive. While the endomorphic Laver tables have much richer combinatorial structure than is found in the corresponding classical Laver tables and multigenic Laver tables, we are still able to somewhat efficiently compute information about the output of the fundamental operations on endomorphic Laver tables. In fact, as I have mentioned before, you may compute in endomorphic Laver tables here and here.

Since we are able to compute the endomorphic Laver tables, it is plausible that the endomorphic Laver tables could be used as platforms for cryptosystems which are secure against classical attacks and even quantum attacks, but much more research still needs to be done on this topic.

The definition of Laver-like partially endomorphic algebras and partially endomorphic Laver tables

The definition of the partially endomorphic Laver tables is somewhat complicated. For simplicity, we shall only define the well-founded partially endomorphic Laver tables induced from known partially endomorphic Laver-like algebras.

Suppose that $X$ is a set and $E,F$ are sets of operations on $X$. Suppose that each $\mathfrak{g}\in F$ has arity $n_{\mathfrak{g}}$ and each $f\in E$ has arity $n_{f}+1$. If $f\in E,a_{1},…,a_{n_{f}}\in X$ then let $L_{f,a_{1},…,a_{n_{f}}}:X\rightarrow X$ be the mapping defined by $L_{f,a_{1},…,a_{n_{f}}}(x)=f(a_{1},…,a_{n_{f}},x)$. Then we say that $(X,E,F)$ is an endomorphic algebra if each mapping $L_{f,a_{1},…,a_{n_{f}}}$ is an endomorphism of $(X,E,F)$. In other words, the partially endomorphic algebras are precisely the algebras where one has the notion of an inner endomorphism. If $F=\emptyset$ and $(X,E,F)$ is a partially endomorphic algebra, then we say that $(X,E)$ is an endomorphic algebra. We say that an algebra $(X,*)$ is an LD-system (or left-distributive algebra) if $(X,*)$ satisfies the identity $x*(y*z)=(x*y)*(x*z)$.

Suppose that $(X,*)$ is a left-distributive algebra. Then we say that a subset $L\subseteq X$ is a left-ideal if $x*y\in L$ whenever $y\in L$. We say that an element $x\in X$ is a left-identity if $x*y=y$ for all $y\in X$. Let $\mathrm{Li}(X)$ denote the set of all left-identities in $X$. A left-distributive algebra $(X,*)$ is said to be Laver-like if $\mathrm{Li}(X)$ is a left-ideal and whenever $x_{n}\in X$ for all $n\in\omega$ there is some $N$ where $x_{0}*…*x_{N}\in\mathrm{Li}(X)$.

If $(X,*)$ is Laver-like, then define $\preceq$ to be the smallest partial ordering on $X$ where $x\preceq x*y$ whenever $x\in X\setminus\mathrm{Li}(X)$. Then $(X,\preceq)$ is a dual well-founded partially ordered set and the dual well-foundedness of $(X,\preceq)$ is necessary for all inductive proofs involving the generalizations of Laver tables.

If $(X,E)$ is an endomorphic algebra, then define the hull $\Gamma(X,E)$ of $(X,E)$ to be the algebra with underlying set
$\bigcup_{f\in E}\{f\}\times X^{n_{f}}$ and binary operation $*$ defined by
$$(f,x_{1},…,x_{n_{f}})*(g,y_{1},…,y_{n_{g}})$$
$$=(g,f(x_{1},…,x_{n_{f}},y_{1}),…,f(x_{1},…,x_{n_{f}},y_{n_{g}})).$$ Then the hull $\Gamma(X,E)$ of an endomorphic algebra is always a left-distributive algebra. We say that a partially endomorphic algebra $(X,E,F)$ is Laver-like if $\Gamma(X,E)$ is Laver-like.

Suppose that $\mathcal{V}=(V,(f^{\mathcal{V}})_{f\in E},(\mathfrak{g}^{\mathcal{V}})_{\mathfrak{g}\in F})$ is a Laver-like partially endomorphic algebra. Suppose furthemore that $X$ is a set of variables and $v_{x}\in V$ for all $x\in X$. For each $x\in X$ and $f\in E$, let $f_{x}$ be an $n_{f}$-ary function symbol. Let $\mathcal{G}=\{f_{x}\mid f\in E,x\in X\}\cup F$. Let $\mathbf{T}_{\mathcal{G}}[X]$ be the set of all terms in the language $\mathcal{G}$ with variables in $X$. Let $L$ be the subset of $\mathbf{T}_{\mathcal{G}}[X]$ and let $\phi:L\rightarrow V$ be the mappings defined by induction on the complexity of the term $\ell\in\mathbf{T}_{\mathcal{G}}[X]$ according to the following rules:

  1. $X\subseteq L$ and $\phi(x)=v_{x}$ for each $x\in X$.
  2. If $\mathfrak{g}\in F$ and $\ell_{1},…,\ell_{n_{\mathfrak{g}}}\in L$, then $\mathfrak{g}(\ell_{1},…,\ell_{n_{\mathfrak{g}}})\in L$ and
    $\phi(\mathfrak{g}(\ell_{1},…,\ell_{n_{\mathfrak{g}}}))=\mathfrak{g}(\phi(\ell_{1}),…,\phi(\ell_{n_{\mathfrak{g}}}))$.
  3. if $f\in E,x\in X$ and $\ell_{1},…,\ell_{n_{f}}\in L$, then $f_{x}(\ell_{1},…,\ell_{n_{f}})\in L$ if and only if
    $$(f,\phi(\ell_{1}),…,\phi(\ell_{n_{f}}))\not\in\mathrm{Li}(\Gamma(V,(f^{\mathcal{V}})_{f\in E})).$$
    If $f_{x}(\ell_{1},…,\ell_{n_{f}})\in L$, then
    $$\phi(f_{x}(\ell_{1},…,\ell_{n_{f}}))=f^{\mathcal{V}}(\phi(\ell_{1}),…,\phi(\ell_{n_{f}}),v_{x})).$$

For each $f\in E$, define an operation $f^{\sharp}$ on $L$ by
$f^{\sharp}(\ell_{1},…,\ell_{n},\ell)=\ell$ whenever $f_{x}(\ell_{1},…,\ell_{n})\in L$ and if
$f_{x}(\ell_{1},…,\ell_{n})\not\in L$ then

  1. $f^{\sharp}(\ell_{1},…,\ell_{n},x)=f_{x}(\ell_{1},…,\ell_{n})$
  2. $f^{\sharp}(\ell_{1},…,\ell_{n},\mathfrak{g}(u_{1},…,u_{n_{g}}))
    =\mathfrak{g}(f^{\sharp}(\ell_{1},…,\ell_{n},u_{1}),…,f^{\sharp}(\ell_{1},…,\ell_{n},u_{n_{g}})),$
  3. $f^{\sharp}(\ell_{1},…,\ell_{n},g_{x}(u_{1},…,u_{n_{g}}))
    =g^{\sharp}(f^{\sharp}(\ell_{1},…,\ell_{n_{g}},u_{1}),…,f^{\sharp}(\ell_{1},…,\ell_{n_{g}},u_{n_{g}}),f_{x}(\ell_{1},…,\ell_{n_{g}})).$

Then we shall write $\mathbf{L}((v_{x})_{x\in X},\mathcal{V})$ for the algebra $(L,(f^{\sharp})_{f\in E},F)$. The algebra $(L,(f^{\sharp})_{f\in E},F)$ is a Laver-like partially endomorphic algebra.

Endomorphic Laver tables are usually infinite

The classical Laver tables and multigenic Laver tables are always locally finite. Furthermore, every Laver-like LD-system is locally finite. In particular, the quotient algebra of elementary embeddings $\mathcal{E}_{\lambda}/\equiv^{\gamma}$ is always locally finite. On the other hand, the partially endomorphic Laver tables with at least one fundamental operation of arity at least 3 that we have looked at are all infinite. Since the endomorphic Laver tables that we have looked at are all infinite, it is unclear as to how these endomorphic Laver tables could arise naturally from the algebras of rank-into-rank embeddings.

Endomorphic Laver tables are abundant

There are many ways to construct $N$-ary operations $t:A_{n}^{N}\rightarrow A_{n}$ with $x*t(x_{1},…,x_{N})=t(x*x_{1},\ldots,x*x_{N})$. If $t$ satisfies the identity $x*t(x_{1},…,x_{N})=t(x*x_{1},\ldots,x*x_{N})$, then define a mapping $T:A_{n}^{N+1}\rightarrow A_{n}$ by letting $T(x_{1},…,x_{N},x)=t(x_{1},…,x_{N})*x$. Then $(X,T)$ is a Laver-like $N+1$-ary algebra.

Every term $t$ in the language of LD-systems satisfies the identity $x*t(x_{1},…,x_{N})=t(x*x_{1},\ldots,x*x_{N})$.

Let $(x)_{r}$ be the unique natural number such that $1\leq(x)_{r}\leq r$ and $(x)_{r}=x\mod\,r$. Then define a mapping $\pi_{n,m}:A_{n}\rightarrow A_{m}$ by $\pi_{n,m}(x)=(x)_{2^{m}}$ whenever $n\geq m$. If $x,y\in A_{n}$, then say that $x\leq^{L}y$ if $x=y$ or if $m$ is the least natural number with $\pi_{n,m}(x)\neq\pi_{n,m}(y)$, then $\pi_{n,m}(x)<\pi_{n,m}(y).$ Then $\leq^{L}$ is a linear ordering with $y\leq^{L}z\rightarrow x*y\leq^{L}x*z$ whenever $x,y,z\in A_{n}$. Define an operation $T_{k,r}:A_{n}^{r}\rightarrow A_{n}$ by letting $T_{k,r}(x_{1},...,x_{r})=x_{\sigma(k)}$ where $\sigma$ is a permutation of $\{1,...,r\}$ with $x_{\sigma(1)}\leq^{L}...\leq^{L}x_{\sigma(n)}$. Then $A_{n}$ satisfies the identity $x*T_{k,r}(x_{1},...,x_{r})=T_{k,r}(x*x_{1},...,x*x_{r})$ as well. There are more complex techniques for constructing mappings $t:A_{n}^{N}\rightarrow A_{n}$ that satisfy the identity $x*t(x_{1},...,x_{N})=t(x*x_{1},\ldots,x*x_{N})$.

At least exponential growth in output length

Let $e$ be a variable. Let $\ell_{1}=e$. Let $\mathcal{V}=(A_{n},t^{\mathcal{V}})$ where $t^{\mathcal{V}}$ is the operation defined by $t^{\mathcal{V}}(x,y,z)=y*z$. Let $L=\mathbf{L}((1)_{r\in\{e\}},\mathcal{V})$. For $1\leq i<2^{n}$, let $\ell_{i+1}=t(\ell_{i},\ell_{i})$. Then the term $\ell_{i}$ has $2^{i-1}$ instances of the variable $e$ and by induction one can show that in $L$, we have $t^{\sharp}(\ell_{r},\ell_{r},\ell_{s})=\ell_{r*_{n}s}$. Such large output is typical for endomorphic Laver table operations. Therefore the output of an endomorphic Laver table operation is often too large to be stored completely by a computer. Some computer experiments suggest that the output size of the endomorphic Laver table operations may be super-exponential.

The trick to computing endomorphic Laver tables

In one sense, the endomorphic Laver table operations are not efficiently computable since our output grows at least exponentially, but we are able to find a sense in which the endomorphic Laver table operations are efficiently computable. The first idea to computing endomorphic Laver tables is not to compute the entire term $t^{\sharp}(\ell_{1},…,\ell_{n},\ell)$ but to recursively compute just a piece of information from the term $t^{\sharp}(\ell_{1},…,\ell_{n},\ell)$ or an approximation of the term $t^{\sharp}(\ell_{1},…,\ell_{n},\ell)$. We shall see that these approximations of the term $t^{\sharp}(\ell_{1},…,\ell_{n},\ell)$ are analogous to how floating point numbers approximate the real numbers. The second idea is to use the original endomorphic Laver-like algebra to extract the necessary information about the terms.

For simplicity of notation, assume that $(X,t^{\bullet})$ is an $n+1$-ary Laver-like algebra.

Let $\Diamond(X,t^{\bullet})$ be the set of all functions $\mathfrak{l}:\{1,…,n\}^{*}\rightarrow X\cup\{\#\}$ that satisfy the following conditions:

  1. $\mathfrak{l}(\varepsilon)\in X$.
  2. If $\mathfrak{l}(\mathbf{x})=\#$, then $\mathfrak{l}(i\mathbf{x})=\#$ for $1\leq i\leq n$.
  3. If $\mathfrak{l}(\mathbf{x})\in X$, then either $\mathfrak{l}(i\mathbf{x})\in X$ for $1\leq i\leq n$ or
    $\mathfrak{l}(i\mathbf{x})=\#$ for $1\leq i\leq n$.
  4. If $\mathfrak{l}(i\mathbf{x})\in X$ for $1\leq i\leq n$, then
    $(\mathfrak{l}(1\mathbf{x}),…,\mathfrak{l}(n\mathbf{x}))\not\in\mathrm{Li}(\Gamma(X,t^{\bullet}))$.
  5. If $\mathfrak{l}(i\mathbf{x})\in X$ for $1\leq i\leq n$, then there is some $x\in X$ where
    $t^{\bullet}(\mathfrak{l}(1\mathbf{x}),…,\mathfrak{l}(n\mathbf{x}),x)=\mathfrak{l}(\mathbf{x})$.
  6. $\mathfrak{l}(\mathbf{x})\in X$ for only finitely many $\mathbf{x}\in X$.

Now if $\mathfrak{l}_{1},…,\mathfrak{l}_{n}\in\Diamond(X,t^{\bullet})^{n}$ and
$(\mathfrak{l}_{1}(\varepsilon),…,\mathfrak{l}_{n}(\varepsilon))\not\in\mathrm{Li}(\Gamma(X,t^{\bullet}))$, and
$x\in X$, then define $t_{x}(\mathfrak{l}_{1},…,\mathfrak{l}_{n}):\{1,…,n\}^{*}\rightarrow X\cup\{\#\}$ by letting
$t_{x}(\mathfrak{l}_{1},…,\mathfrak{l}_{n})(\varepsilon)=t^{\bullet}(\mathfrak{l}_{1}(\varepsilon),…,\mathfrak{l}_{n}(\varepsilon),x)$ and where $t_{x}(\mathfrak{l}_{1},…,\mathfrak{l}_{n})(\mathbf{x}i)=\mathfrak{l}_{i}(\mathbf{x})$ whenever $i\mathbf{x}\in\{1,…,n\}^{*}$.

Then there is a unique operation $t^{\sharp}:\Diamond(X,t^{\bullet})^{n+1}\rightarrow\Diamond(X,t^{\bullet})$ such that

  1. $t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{l})=\mathfrak{l}$ whenever
    $(\mathfrak{l}_{1}(\varepsilon),…,\mathfrak{l}_{n}(\varepsilon))\in\mathrm{Li}(\Gamma(X,t^{\bullet}))$,
  2. Otherwise, if $\mathfrak{l}(i)=\#$ for $1\leq i\leq n$, then
    $t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{l})=t_{\mathfrak{l}(\varepsilon)}(\mathfrak{l}_{1},…,\mathfrak{l}_{n})$, and
  3. $$t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},t^{\sharp}(\mathfrak{u}_{1},…,\mathfrak{u}_{n},\mathfrak{u}))$$
    $$=t^{\sharp}(t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{u}_{1}),…,
    t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{u}_{n}),t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{u})).$$

Then the algebra $\Diamond(X,t^{\bullet})$ is isomorphic to a quotient of the endomorphic Laver table $\mathbf{L}((x)_{x\in X},(X,t^{\bullet}))$ by a very small congruence. Furthermore, it is easy to embed any desired endomorphic Laver table into an algebra of the form $\Diamond(X,t^{\bullet})$. Instead of computing the entire output $t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{l})$, one could just compute $t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{l})(\mathbf{x})$ for some string $\mathbf{x}$.

Endomorphic Laver tables can be computed quickly

Suppose that $(X,t^{\bullet})$ is an $r+1$-ary Laver-like algebra. By our experiments, we have concluded that if $f(x_{1},…,x_{r})$ is a term whose only function symbol is $t^{\sharp}$, then in $\Diamond(X,t^{\bullet})$, the value of
$f(\mathfrak{l}_{1},…,\mathfrak{l}_{r})(\mathbf{x})$ is usually computable in a few seconds as long as $|\mathbf{x}|<500$ or so in the language JavaScript on a web browser. When $\mathbf{x}$ gets to long, I usually run out of memory or the computation fails from too deep recursion errors.

A limitless source of combinatorial complexity.

While the classical Laver tables and multigenic Laver tables collectively can be thought of as an unlimited source of combinatorial complexity, since every classical Laver table and multigenic Laver table is locally finite, each classical Laver table and multigenic Laver table must only have a limited amount of combinatorial complexity. However, each endomorphic Laver table seems to contain an unlimited amount of combinatorial complexity and there does not appear to be a formula for computing $t^{\bullet}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{l})(\mathbf{x})$ even for endomorphic Laver tables originally obtained from $A_{5}$. The output of an endomorphic Laver table operation is usually unpredictable, but among the complexity of the output of the endomorphic Laver tables, there is some order amidst the complexity. The output of endomorphic Laver table operations seem to exhibit a sort of periodicity which is similar to the periodicity found in the classical and multigenic Laver tables.

Possible applications to public key cryptography

The endomorphic Laver tables incorporate the following attributes which are necessary for public key cryptography.

  1. The classical Laver tables are combinatorially complicated since they may be used to produce recursive functions which grow faster than the Ackermann function. The multigenic Laver tables are even more complicated. However, the combinatorial richness of the classical Laver tables and multigenic Laver tables is surpassed by the combinatorial complexity that arises from the endomorphic Laver tables.
  2. While the endomorphic Laver tables are combinatorially intricate, the endomorphic Laver tables still retain much algebraic structure. In other words, there is order to the chaos that arises from endomorphic Laver tables.
  3. The endomorphic Laver tables are fairly easy to compute.
  4. The endomorphic Laver tables currently have nothing to do with linear algebra, fourier transforms, or anything of that sort. This is an advantage since quantum algorithms tend to rely on these techniques that have nothing to do with Laver tables. Therefore since quantum algorithms do not seem to help with calculating anything related to Laver tables, endomorphic Laver tables may be useful in post-quantum cryptography (post-quantum cryptography refers to the study of public key cryptosystems that resist attacks from parties that have access to quantum computers).

I will put up a post soon about the various endomorphic Laver tables based cryptosystems along with a preliminary analysis of one of those cryptosystems. It is currently unclear as to whether endomorphic Laver table based cryptosystems are secure and much more investigation on endomorphic Laver tables is necessary before I can gain any confidence about the security of endomorphic Laver table based cryptosystems.

Leave a Reply

Your email address will not be published. Required fields are marked *

× one = ten