Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?

share|improve this question
2  
What kind of example? $(A,\land,\land)$ has these properties for any semilattice $(A,\land)$. –  Emil Jeřábek Jan 14 at 20:50
    
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$. –  KConrad Jan 14 at 20:50
3  
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. –  KConrad Jan 14 at 20:52
    
@KConrad: there is no zero, no one. –  M. Shahryari Jan 14 at 20:53
1  
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. –  The Masked Avenger Jan 15 at 5:41

4 Answers 4

up vote 4 down vote accepted

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.

share|improve this answer
1  
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. –  The Masked Avenger Jan 14 at 21:22
    
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. –  M. Shahryari Jan 14 at 22:03
1  
@TheMaskedAvenger, why do you say only "essentially" identical? It seems to me that your argument shows that the two operations are fully identical. –  Joel David Hamkins Jan 15 at 0:38
    
@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 +. –  The Masked Avenger Jan 15 at 1:19
    
Oh, they have different names, but like the morning star and the evening star, the referent of those names is identical, the very same function, or the very same planet Venus, as the case may be. –  Joel David Hamkins Jan 15 at 1:22

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.
share|improve this answer
    
What happens if $A$ is infinite? –  M. Shahryari Jan 15 at 10:26
    
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. –  Joseph Van Name Jan 15 at 22:22

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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