3
$\begingroup$

Is there a known example of an algebra $(A, +, \cdot)$ with two binary commutative (see P.S below) and idempotent operations $+$ and $\cdot$ satisfying the identity $(a+b)(c+d)=ac+bd$?


Actually I need to know is there any algebra $A$ having signature $\mathcal{L}$ such that for any $n$-ary $f\in \mathcal{L}$ and any $m$-ary $g\in\mathcal{L}$ we have $$ f(g(x_{11}, \ldots, x_{1m}), \ldots, g(x_{n1}, \ldots,x_{nm}))=g(f(x_{11}, \ldots,x_{n1}), \ldots, f(x_{1m},\ldots, x_{nm})) $$ Also I need to have all operations idempotent. As my motivation, I should say that for any variety of such algebras, we have the following interesting property: Let $F=F_V(x_1,\ldots,x_n)$ be a relative free algebra in $V$. Then the solution set of any system of equations in $F$ is a subalgebra of $F^k$ where $k$ is the number of indeterminate.

P.S. Instead of commutativity, consider the next two weaker conditions:

  1. $(a+b)+(c+d)=(a+c)+(b+d)$.

  2. $(ab)(cd)=(ac)(bd)$. \

P.S.2. It is good to use the phrase Medial instead of Commutative. So my question becomes: Is there a known example of an algebra $(A, +, \cdot)$ with two binary medial and idempotent operations satisfying the identity $(a+b)(c+d)=ac+bd$?

$\endgroup$
7
  • 4
    $\begingroup$ What kind of example? $(A,\land,\land)$ has these properties for any semilattice $(A,\land)$. $\endgroup$ Jan 14, 2014 at 20:50
  • $\begingroup$ Letting $b = 1$, $c = 0$, and $d = 1$ (are we allowed to assume there's a multiplicative identity?), the first equation in your question implies $a+1 = 1$, so $a = 0$. Thus $A = 0$. $\endgroup$
    – KConrad
    Jan 14, 2014 at 20:50
  • 3
    $\begingroup$ Of course, if you consider the special case $(a+b)^2 = a^2 + b^2$, then according to the work on many student exams (at least in the US) the real numbers are apparently an example. $\endgroup$
    – KConrad
    Jan 14, 2014 at 20:52
  • $\begingroup$ @KConrad: there is no zero, no one. $\endgroup$
    – Sh.M1972
    Jan 14, 2014 at 20:53
  • 1
    $\begingroup$ Although your answer likely lies among entropic algebras, you might note that idempotency and your identity give four one-sided distributive laws. You might look at near-rings for possible examples. $\endgroup$ Jan 15, 2014 at 5:41

4 Answers 4

5
$\begingroup$

Assuming the properties of idempotency and commutativity, $a+b=(a+b)(a+b)=(a+b)(b+a)=ab+ba=ab+ab=ab$. So you will have essentially identical operations for + and *. I don't know what happens if you drop one or more of idempotency or commutativity.

$\endgroup$
8
  • 1
    $\begingroup$ The form smells of mediality or decomposition operations or commuting operations. You might phrase it in terms of semigroups to see what responses you get. $\endgroup$ Jan 14, 2014 at 21:22
  • $\begingroup$ In fact I don't need the commutativity, but instead I need a weaker conditions: $(a+b)+(c+d)=(a+c)+(b+d)$ and $(ab)(cd)=(ac)(bd)$. See below. $\endgroup$
    – Sh.M1972
    Jan 14, 2014 at 22:03
  • 1
    $\begingroup$ @TheMaskedAvenger, why do you say only "essentially" identical? It seems to me that your argument shows that the two operations are fully identical. $\endgroup$ Jan 15, 2014 at 0:38
  • $\begingroup$ @Joel, I am being sloppy with language here (on more than one level). As functions from the (square of the) underlying set to itself, + and * will be the same in this setup. As terms in the absolutely free term algebra of language <2,2>, they will land in the same invariant congruence class generated by congruences for the properties assumed above. But in the type of algebras used, one goes in the first slot of the ordered tuple of functions, the other goes in the second, so they are linguistically (and inessentially in many views) distinct. Also in print, * has more pointy bits than +. $\endgroup$ Jan 15, 2014 at 1:19
  • 1
    $\begingroup$ My point was that as binary functions, the two operations have exactly the same domain, the same target space, and (by your argument) the same values at each pair of points in the domain. Doesn't this make them identical as functions? So, the "essential" qualification is misplaced. $\endgroup$ Jan 15, 2014 at 3:13
7
$\begingroup$

There are large classes of algebras with two (or more) operations satisfying your identities. They are called modes. There is a monograph by Romanowska and Smith, called Modes, on this very topic. Here is a recent survey paper on the topic by Smith.

$\endgroup$
2
$\begingroup$

If you weaken your identities, then you end up with commuting one dimensional cellular automata. It turns out that commuting one dimensional cellular automata can essentially be represented as finite algebras $(A,+,\cdot)$ that satisfy the identity $(x\cdot y)+(y\cdot z)=(x+y)\cdot(y+z)$. Therefore, the algebras that you have mentioned will definitely produce commuting cellular automata.

Suppose $A$ is a finite set. Then $A^{\mathbb{Z}}$ becomes a compact space with the product topology. Let $\Phi:A^{\mathbb{Z}}\rightarrow A^{\mathbb{Z}}$ be the function defined by $\Phi(a_{r})_{r\in\mathbb{Z}}=(a_{r+1})_{r\in\mathbb{Z}}$. Then a one-dimensional cellular automaton with values in $A$ is a continuous function $G:A^{\mathbb{Z}}\rightarrow A^{\mathbb{Z}}$ such that $G\Phi=\Phi G$. It is well known that a function $G:A^{\mathbb{Z}}\rightarrow A^{\mathbb{Z}}$ is a cellular automaton if and only if there is some $n$ and function $F:A^{2n+1}\rightarrow A$ such that $G(a_{r})_{r\in\mathbb{Z}}=(F(a_{r-n},...,a_{r},...,a_{r+n}))_{r\in\mathbb{Z}}$. In other words, the cellular automaton function $G$ is determined by local coordinates and it is translation invariant. One may easily translate any cellular automata into a cellular automata of the form $G:A^{\mathbb{Z}}\rightarrow A^{\mathbb{Z}}$ such that there is a binary operation $+$ on $A$ such that $G(a_{r})_{r\in\mathbb{Z}}=(a_{r}+a_{r+1})_{r\in\mathbb{Z}}$.

$\textbf{Proposition}$ Suppose that $F,G:A^{\mathbb{Z}}\rightarrow A^{\mathbb{Z}}$ are cellular automata such that $F(a_{r})_{r\in\mathbb{Z}}=(a_{r}+a_{r+1})_{r\in\mathbb{Z}},G(a_{r})_{r\in\mathbb{Z}}=(a_{r}\cdot a_{r+1})_{r\in\mathbb{Z}}$. Then $FG=GF$ if and only if the algebra $(A,+,\cdot)$ satisfies the identity $(x+y)\cdot(y+z)=(x\cdot y)+(y\cdot z)$.

$\textbf{Proof}$ This result follows from the observation that $$FG(a_{r})_{r\in\mathbb{Z}}=f((a_{r}\cdot a_{r+1})_{r\in\mathbb{Z}})= ((a_{r}\cdot a_{r+1})+(a_{r+1}\cdot a_{r+2}))_{r\in\mathbb{Z}}$$ and $$GF(a_{r})_{r\in\mathbb{Z}}=((a_{r}+a_{r+1})\cdot(a_{r+1}+a_{r+2})).$$ $\mathbf{QED}$

The reader is referred to the paper [1] for more information on commuting cellular automata and algebras that satisfy the identity $(x\cdot y)+(y\cdot z)=(x+y)\cdot(y+z)$.

  1. Moore, Cristopher; Boykett, Timothy. Commuting cellular automata. Complex Systems 11 (1997), no. 1, 55–64.
$\endgroup$
2
  • $\begingroup$ What happens if $A$ is infinite? $\endgroup$
    – Sh.M1972
    Jan 15, 2014 at 10:26
  • $\begingroup$ One still has a correspondence between commuting cellular automata and algebras satisfying that identity even if $A$ is infinite. I however restricted my attention to finite sets $A$ since cellular automata usually just deal with just finite sets $A$ of states. $\endgroup$ Jan 15, 2014 at 22:22
1
$\begingroup$

This answer is similar to the other answer that I gave but here I claim that the identity $(a\cdot b)+(c\cdot d)=(a+c)\cdot(b+d)$ is equivalent to whether two 2-dimensional cellular automata commute.

Suppose that $A$ is a finite set and $\cdot,+$ are binary operations on $A$. Then we may define cellular automata $F,G:A^{\mathbb{Z}^{2}}\rightarrow A^{\mathbb{Z}^{2}}$ by letting $F(a_{r,s})_{r,s\in\mathbb{Z}}=(a_{r,s}+a_{r+1,s})_{r,s\in\mathbb{Z}}$ and $G(a_{r,s})_{r,s\in\mathbb{Z}}=(a_{r,s}\cdot a_{r,s+1})_{r,s\in\mathbb{Z}}$. Then it can easily be shown that $F\circ G=G\circ F$ if and only if the identity $(w\cdot x)+(y\cdot z)=(w+y)\cdot(x+ z)$ holds.

$\textbf{A Generalization}$ (edited November 15, 2014).

It turns out the more general identity asked in the question involving operations of higher arity still reduces to the notion of whether $``$orthogonal$"$ cellular automata commute with each other.

Let $A$ be a set. Let $s:A^{m}\rightarrow A,t:A^{n}\rightarrow A$ be functions.

Define maps $G,H:A^{\mathbb{Z}^{n+m}}\rightarrow A^{\mathbb{Z}^{n+m}}$ by letting

$$\large G(x_{i_{1},...,i_{n+m}})_{i_{1},...,i_{n+m}\in\mathbb{Z}}$$ $$\large =s(x_{i_{1}+1,...,i_{m},i_{m+1},...,i_{m+n}},...,x_{i_{1},...,i_{m}+1,i_{m+1},...,i_{m+n}})$$

and

$$\large H((x_{i_{1},...,i_{n+m}})_{i_{1},...,i_{n+m}\in\mathbb{Z}})$$

$$\large=(t(x_{i_{1},...,i_{m},i_{m+1}+1,...,i_{m+n}},...,x_{i_{1},...,i_{m},i_{m+1},...,i_{m+n}+1})_{i_{1},...,i_{m+n}\in\mathbb{Z}}.$$

Then the cellular automata mappings $G$ and $H$ commute (i.e. $G\circ H=H\circ G$) if and only if the operations $s$ and $t$ satisfy the entropic identity: $$s(t(z_{1,1},...,z_{1,n}),...,t(z_{m,1},...,z_{m,n})) =t(s(z_{1,1},...,z_{m,1}),...,s(z_{1,n},...,z_{m,n})).$$

I am unsure if the relation between modes and entropic algebras and commutative cellular automata which act on orthogonal dimensions has been studied before.

$\endgroup$

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.