We say that a variety $V$ is reversible if for each $n>0$ and $n$-ary fundamental operation $f$, there is some $m\geq n$ and $r$ along with terms $T_{2},\dotsc,T_{r},S_{1},\dotsc,S_{m}$ such that $G$, $H$ are inverses where

  1. $G(x_{1},\dotsc,x_{m})=(f(x_{1},\dotsc,x_{n}),T_{2}(x_{1},\dotsc,x_{m}),\dotsc,T_{r}(x_{1},\dotsc,x_{m}))$, and

  2. $H(y_{1},\dotsc,y_{r})=(S_{1}(y_{1},\dotsc,y_{r}),\dotsc,S_{m}(y_{1},\dotsc,y_{r}))$.

The following varieties are reversible:

  1. Groups.

  2. Racks, quandles, and biracks.

  3. Jónsson–Tarski algebras.

  4. The variety consisting of all algebras $(X,f,g)$ where $f,g:X\rightarrow X$ are inverse functions.

  5. The variety of all heaps.

  6. The variety of quasigroups.

  7. The variety $K_{X}$ where $K_{X}$ is generated by the algebra $(X,\mathcal{F})$ where $\mathcal{F}$ consists of all functions $f:X^{n}\rightarrow X$ where $\lvert f^{-1}[\{a\}]\rvert=\lvert f^{-1}[\{b\}]\rvert$ for each $a,b\in X$.

  8. The variety consisting of sets without any fundamental operations.

In addition to these varieties, one can artificially create (hopefully non-trivial) reversible varieties since the fact that $G$, $H$ are inverses is clearly axiomatized by identities. Also, every subvariety of a reversible variety is reversible. It is therefore quite easy to contrive new reversible varieties from old ones.

If $X$ is a finite algebra in a reversible variety and $f$ is an $n$-ary fundamental operation and $a\in X$, then $$\lvert\{(x_{1},\dotsc,x_{n})\in X^{n}\mid f(x_{1},\dots,x_{n})=a\}\rvert=\lvert X\rvert^{n-1}.$$

Observe that the reversible varieties are the varieties consisting of algebras that are “almost groups” in the sense that one often associates these algebras with canonical groups and because these algebras feel like groups.

What are some more examples of reversible varieties that occur naturally and in practice and are not just constructed for the sole purpose of being reversible? Is there a good reference for reversible varieties?


1 Answer 1


I consider the variety of quasigroups to be one of the main examples of reversible varieties since the quasigroups are simply the algebraic structures $(X,\cdot,\backslash,/)$ such that the mappings $(x,y)\mapsto(x\cdot y,y),(x,y)\mapsto(x/y,y)$ are inverses and the mappings $(x,y)\mapsto(x,x\cdot y),(x,y)\mapsto(x,x\backslash y)$ are also inverses. There are ways to generalize the variety of quasigroups to more complicated reversible varieties such as varieties of mutually orthogonal Latin squares.

The variety of quasigroups also generalizes to reversible varieties with operations of higher arity, and the finite algebras in some of these varieties are up-to-isomorphism in a many-to-one correspondence with the square matrices $A$ such that every entry in $A$ is a $0$ or a $1$ and each entry in $A^{k}$ is $1$. I don't think that anyone has studied these varieties before, but they seem to be interesting and maybe even useful in cryptography for block ciphers where the block size is $k$ times as long as the round key size.

$k+1$-ary quasigroups

Suppose that $X$ is a set and $$S_{1},\dots,S_{k},T_{1},\dots,T_{k}:X^{k+1}\rightarrow X,\Gamma_{1},\dots,\Gamma_{k}:X^{2k}\rightarrow X$$ are operations. For each $i\in X$, define $f_{i}:X^{k}\rightarrow X^{k}$ by letting $$f_{i}(u_{1},\dots,u_{k})=(S_{1}(i,u_{1},\dots,u_{k}),\dots,S_{k}(i,u_{1},\dots,u_{k})),$$ and define $$g_{i}(u_{1},\dots,u_{k})=(T_{1}(i,u_{1},\dots,u_{k}),\dots,T_{k}(i,u_{1},\dots,u_{k})).$$ Define binary operations $\cdot,\backslash,/$ on $X^{k}$ by letting $(u_{1},\dots,u_{k})\cdot(v_{1},\dots,v_{k})=f_{u_{1}}\circ\dots\circ f_{u_{k}}(v_{1},\dots,v_{k})$ and $$(u_{1},\dots,u_{k})\backslash(v_{1},\dots,v_{k})=g_{u_{k}}\circ\dots\circ g_{u_{1}}(v_{1},\dots,v_{k})$$ and $$(u_{1},\dots,u_{k})/(v_{1},\dots,v_{k})=(w_{1},\dots,w_{k})$$ where we define $w_{i}=\Gamma_{i}(u_{1},\dots,u_{k},v_{1},\dots,v_{k})$ for $1\leq i\leq k$. Then we say that $$(X,S_{1},\dots,S_{k},T_{1},\dots,T_{k},\Gamma_{1},\dots,\Gamma_{k})$$ is a $k+1$-ary quasigroup if $(X^{k},\cdot,\backslash,/)$ is a quasigroup and $f_{i},g_{i}$ are inverses for each $i\in X$. The class of all $k+1$-ary quasigroups is a reversible variety. If $k=1$, then the $k+1$-ary quasigroups are precisely the quasigroups.

Obtaining $k+1$-ary quasigroups from matrices

We shall now discuss a way to obtain $k+1$-ary quasigroups from certain matrices. Let us begin with a couple lemmas.

Lemma: Suppose that $R,S$ are both $n\times n$-matrices. Suppose that the sum of each row in $R$ is $r$, the sum of each column in $R$ is $r$, the sum of each row in $S$ is $s$, and the sum of each column in $S$ is $s$. Then the sum of each row in $RS$ is $rs$, and the sum of each column in $RS$ is $rs$.

Lemma: Suppose that $A$ is an $n\times n$-matrix where each entry in $A$ is a $0$ or a $1$ and each entry in $A^{k}$ is $1$. Then $n=m^{k}$ for some natural number $m$ where the sum of each row of $A$ is $m$ and the sum of each column of $A$ is $m$ as well.

Proof: Suppose that $A=(a_{i,j})_{i,j}$. Then $$A^{k+1}=A\cdot A^{k}=(a_{i,j})_{i,j}\cdot(1)_{i,j}=(\sum_{\ell}a_{i,\ell})_{i,j}.$$ Similarly, $$A^{k+1}=A^{k}\cdot A=(1)_{i,j}(a_{i,j})=(\sum_{\ell}a_{\ell,j})_{i,j}.$$ Therefore, we have $\sum_{\ell}a_{i,\ell}=\sum_{\ell}a_{\ell,j}$ for each $i,j$. Therefore, there exists some $m$ such that the sum of each row in $A$ is $m$ and the sum of each column in $A$ is $m$ as well. By the above lemma, we conclude that the sum of each row and column in $A^{k}$ is $m^{k}$. Therefore, $n=m^{k}$. Q.E.D.

Suppose now that $A$ is a matrix where every entry in $A$ is a $0$ or a $1$ and every entry in $A^{k}$ is $1$. If $f$ is a permutation, then let $\phi(f)$ denote its corresponding permutation matrix. Then there are permutations $f_{1},\dots,f_{m}\in S_{n}$ such that $A=\phi(f_{1})+\dots+\phi(f_{m})$ and such permutations $f_{1},\dots,f_{m}$ are easy to compute (you obtain such a decomposition using the Birkhoff-von-Neumann algorithm)).

By associating $[n]$ with $[m]^{k}$, we can assume that $f_{1},\dots,f_{m}$ are bijections from $[m]^{k}$ to $[m]^{k}$ such that whenever $u_{1},\dots,u_{k},v_{1},\dots,v_{k}\in[m]$ there is a unique tuple $(w_{1},\dots,w_{k})$ such that $$f_{w_{1}}\circ\dots\circ f_{w_{k}}(u_{1},\dots,u_{k})=(v_{1},\dots,v_{k}).$$ From the functions $f_{1},\dots,f_{m}$, we obtain our $k+1$-ary quasigroup $$([m],S_{1},\dots,S_{k},T_{1},\dots,T_{k},\Gamma_{1},\dots,\Gamma_{k})$$ by letting $S_{i}(j,u_{1},\dots,u_{k})=\pi_{i}f_{j}(u_{1},\dots,u_{k})$ and $T_{i}(j,u_{1},\dots,u_{k})=\pi_{i}f_{j}^{-1}(u_{1},\dots,u_{k})$. Define operations $\Gamma_{1},\dots,\Gamma_{k}:[m]^{2k}\rightarrow[m]$ by letting $\Gamma_{i}(u_{1},\dots,u_{k},v_{1},\dots,v_{k})=w_{i}$ for $1\leq i\leq k$ such that $$(f_{w_{1}}\circ\dots\circ f_{w_{k}})(v_{1},\dots,v_{k})=(u_{1},\dots,u_{k}).$$

Likewise, every $k+1$-ary quasi-group with underlying set $[m]$ produces a matrix $A$ where each entry in $A$ is a $0$ or a $1$ and each entry in $A^{k}$ is $1$.

There are plenty of non-trivial examples of matrices $A$ where each entry in $A$ is a $0$ or a $1$ and each entry in $A^{k}$ is $1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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