Consider the “product” $\gamma = \alpha \times \beta$ of two binary strings $\alpha$, $\beta$ $\in \lbrace 0,1\rbrace^+$ which one gets by replacing every 1 in $\beta$ by $\alpha$ and each 0 in $\beta$ by $\overline{\alpha}$, with $\overline{\alpha}$ being the negation of $\alpha$, which one gets by replacing every 1 in $\alpha$ by 0 and vice versa.


$$(\alpha \times \beta)[k] = \begin{cases} 1 & \text{if}\ \ \alpha[k\ \text{mod}\ a] = \beta[k\ \text{div}\ a] \\\ 0 & \text{otherwise} \end{cases}$$

for $a=|\alpha|, b=|\beta|, k = 0,\dots,ab-1$.

Maybe it comes as a surprise - at least for me it did - and it's a little bit cumbersome to prove, that the operation $\times$ - even though it is not commutative - is associative, i.e. $\alpha \times (\beta \times \gamma) = (\alpha \times \beta) \times \gamma$.

Is there an elegant argument to see that $\times$ is associative? (I had to go through a couple of case discriminations and some equivalencies of modulo arithmetic like $(k\ \text{mod}\ ab)\ \text{div}\ a = (k\ \text{div}\ a)\ \text{mod}\ b$ to get to the result.)

Since $1$ is a neutral element ($\alpha \times 1 = 1 \times \alpha = \alpha$), the tuple $(\lbrace 0,1\rbrace^+,\times,1)$ is a monoid.

In this monoid it seems that each $\sigma$ has a unique “factorization” into “primes” (upto associativity). If the length of $\sigma$ is prime, $\sigma$ itself is necessarily “prime”. If $\sigma$ has length $2^n$ it can have up to $n$ prime factors, e.g. $10010110 = 10 \times 10 \times 10$. But it can also be prime, e.g. $1110$.

In which contexts and under which name has this monoid been investigated?

  • $\begingroup$ What does $ \beta[k\ \text{div}\ a]$ mean? $\endgroup$ – Boris Novikov May 23 '13 at 9:59
  • $\begingroup$ It's the $k\ \text{div}\ a$-th entry in $\beta$. (MathJax did not support subscript indices à la $\beta_{k\ \text{div}\ a}$ in the $$ math environment.) Consistently I should have written $(\alpha \times \beta)[k]$... $\endgroup$ – Hans-Peter Stricker May 23 '13 at 10:06
  • $\begingroup$ Sorry, I didn't understand $\text{div}\ a$ $\endgroup$ – Boris Novikov May 23 '13 at 10:28
  • $\begingroup$ Sorry $k\ \text{div}\ a$ is just $\lfloor k/a\rfloor$. $\endgroup$ – Hans-Peter Stricker May 23 '13 at 10:30
  • $\begingroup$ I recommend k going from 1 to ab. Gerhard "Index Checking Is Always Worthwhile" Paseman, 2013.05.23 $\endgroup$ – Gerhard Paseman May 23 '13 at 15:28

I think it's less confusing if you swap the roles of 0 and 1, as then the basic operation you're using to generate the entries of $\alpha\times\beta$ is addition mod 2.

Then, if you write $\alpha_i$ for the $i$th entry of a string $\alpha$, associativity follows because the entries of $\alpha\times\beta\times\gamma$ are just the $\alpha_i+\beta_j+\gamma_k$ (mod 2), listed in lexicographic order of $(k,j,i)$.

  • $\begingroup$ This answers perfectly my first question. Thanks! $\endgroup$ – Hans-Peter Stricker May 23 '13 at 11:01

The monoid has a central subgroup $\{0,1\}$ (the group of units). One needs to take that into account when talking about primes. There is the induced congruence on the monoid $u\sim v$ iff $u=v$ or $u=0\cdot v$. The factor-monoid is free. That can be proved using Levi's theorem (Theorem 1.8.4 in my book ):

Suppose that $S$ is a cancellative semigroup without an identity element, in which every element is a product of indecomposable elements, and for every four elements $a,u,v,c$ from $S$ the equality $au = vc$, implies either $u=c$ or $u=bc$ or $c=bu$ for some $b$. Then $S$
is a free semigroup and the set of indecomposable elements of $S$ is its free generating set.

Correction. The factor-monoid is not free. Indeed, $11\cdot 111=111111=111\cdot 11$. It would be interesting to find a presentation of this monoid. I think that the defining relations should be related to periodicity and a presentation should not be too complicated.

  • $\begingroup$ Do you suggest to see the monoid as a string rewriting system, with two rules for every string $\sigma$: $1 \rightarrow \sigma$, $0 \rightarrow \overline{\sigma}$? Do you treat this string rewriting system explicitly in your book? $\endgroup$ – Hans-Peter Stricker May 23 '13 at 11:54
  • $\begingroup$ No, this rewriting system is not interesting because it is not terminating. Your monoid seems to be isomorphic to the direct product of the free monoid of countable rank and the 2-element group. Indeed, consider the set $S_1$ of all words starting with 1. It is a submonoid. Every element either is in $S_1$ or is equal to $0\cdot u$ where $u\in S_1$. This decomposition is unique and $(0\cdot u)\cdot (0\cdot v)=u\cdot v=1\cdot (u\cdot v)$. $\endgroup$ – user6976 May 23 '13 at 12:32

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.