A left distributive algebra is a set $A$ together with a binary operation, $\cdot$, satisfying $a\cdot(b\cdot c)=(a\cdot b)\cdot(a\cdot c)$.

One important example of left distributive algebras arises in set theory. For $\lambda$ a limit cardinal let $\mathcal{E}_\lambda$ be the set of elementary embeddings $j: V_\lambda\rightarrow V_\lambda$. Suppose $\lambda$ is such that $\mathcal{E}_\lambda\not=\emptyset$ (this is a very large cardinal axiom, called "rank-into-rank" or more precisely "$I_3$"). Then for $j, k\in \mathcal{E}_\lambda$, we can define $$j\cdot k=\bigcup_{\alpha<\lambda}j(k\cap V_\alpha)$$ where we view $k$ as a set of ordered pairs, so that $k\subset V_{\lambda+1}$. Then it turns out that $j\cdot k\in\mathcal{E}_\lambda$ and that $(\mathcal{E}_\lambda, \cdot)$ is a left distributive algebra. Fixing $j\in\mathcal{E}_\lambda$ and letting $\mathcal{A}_j$ be the closure of $\{j\}$ in $\mathcal{E}_\lambda$, Laver (1992, http://www.sciencedirect.com/science/article/pii/000187089290016E#) proved that $\mathcal{A}_j$ is the free left distributive algebra on one generator. He also showed (under the assumption that such a $j$ exists, that is, $I_3$) that the word problem for the free left distributive algebra on one generator is decidable.

There has been extensive work on the strength of various results around left distributive algebras. My question is about this last point:

Is it known (within ZFC) if the word problem for the free left distributive algebra with one generator is decidable?

Since the only proof of decidability I know of uses the normal form theorem, I suspect the answer is no, but I haven't been able to find out myself.

Note: I've tagged this "universal algebra" as that seemed the most relevant algebraic tag. If there is a better tag, or if this tag is just too irrelevant, feel free to replace/remove it.

  • $\begingroup$ www.math.unicaen.fr/~dehornoy/Papers/Dfb.pdf $\endgroup$ – Emil Jeřábek Jul 27 '14 at 22:53

Yes. If by the word problem for left-distributive algebras, we mean determining if two elements of a free left-distributive algebra (with any number of generators) are equal. In the Handbook of Set Theory, Theorem 2.11 in the chapter on algebras of elementary embeddings states that in ZFC left division in the free left distributive algebra with one generator has no cycle (i.e. we cannot have $(...((x*x_{1})*x_{2})*...)*x_{n}=x$ where the operation is application of elementary embeddings). Theorem 2.1 in the same chapter states that if there is a left-distributive algebra where left division has no cycle, then the word problem for left distributive algebras is decidable. Combining these results we conclude that the word problem form left distributive algebras on one generator is decidable without using the I3 axiom.

$\textbf{Added some time later}$

I should also mention that there are ways to represent the free LD-system with one generator without using large cardinal embeddings. From these representations, one can solve the word problem for LD-systems with one generator. Let $B_{\infty}$ denote the braid group on infinitely many strands. The braid group $B_{\infty}$ is the direct limit of the braid groups $B_{n}$ on finitely many generators. Then the braid group $B_{\infty}$ can not only be endowed with a group operation, but $B_{\infty}$ can also be given a self-distributive operation as well as follows. Let $\sigma_{i}$ be the canonical generators of $B_{\infty}$. In other words, $\sigma_{i}$ is the braid that twists the $i$-th strand with the $i+1$-th strand. Then let $\textrm{sh}:B_{\infty}\rightarrow B_{\infty}$ be the homomorphism mapping where $\textrm{sh}(\sigma_{i})=\sigma_{i+1}$. In other words, $\textrm{sh}$ is the shift map. Define an operation $*$ on $B_{\infty}$ where $a*b=a \textrm{sh}(b)\sigma_{1}\textrm{sh}(a^{-1})$. Then $*$ is a self-distributive operation on $B_{\infty}$. Furthermore, left division in $B_{\infty}$ has no cycles. Therefore for each $b\in B_{\infty}$, the LD-system $\langle b\rangle$ generated by $b$ is freely generated by $b$. Therefore the word problem for LD-systems generated by one element reduces to the word problem for braid groups.

Not only is the word problem for braid groups solvable, but there are several known algorithms for the word problem on braid groups. An algorithm for the word problem for braid groups was formulated in 1969 by Garside. Presumably, the best algorithm for determining if two braid words $w_{1},w_{2}$ represent the same braid has complexity $O(l^2n)$ where $l$ is the length of the longest braid word and $n$ is the number of strings that one twists.

These facts may be found in Patrick Dehornoy's book Braids and Self-Distributivity.

  • $\begingroup$ I don't have the handbook with me - are these results proved in ZFC alone? $\endgroup$ – Noah Schweber Jul 27 '14 at 22:44
  • $\begingroup$ Yes. These results can be proven in ZFC alone, and the Handbook of Set Theory outlines ZFC proofs of these results even though the proofs are not very set theoretical. $\endgroup$ – Joseph Van Name Jul 27 '14 at 22:55
  • $\begingroup$ I should mention that the word problem for the free left-distributive algebra an arbitrary number of generators is also solvable and that the free left-distributive algebras on multiple generators embed into some generalizations of the braid groups such as the charged braid groups. $\endgroup$ – Joseph Van Name Feb 8 '17 at 3:25
  • $\begingroup$ The $O(l^{2}n)$ time algorithm is based upon putting the braid words into the Birman-Ko-Lee normal form. There are faster algorithms though. Two braids $b,c$ are equal if and only if they have the same Dynnikov coordinates and one can compute the Dynnikov coordinates of a braid in $O(l^{2})$ time by computing $O(l)$ integer addition and integer comparison operations. $\endgroup$ – Joseph Van Name Jan 3 '19 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.