# An operation on binary strings

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.

Formally:

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

-
What does $\beta[k\ \text{div}\ a]$ mean? –  Boris Novikov May 23 '13 at 9:59
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]$... –  Hans Stricker May 23 '13 at 10:06
Sorry, I didn't understand $\text{div}\ a$ –  Boris Novikov May 23 '13 at 10:28
Sorry $k\ \text{div}\ a$ is just $\lfloor k/a\rfloor$. –  Hans Stricker May 23 '13 at 10:30
I recommend k going from 1 to ab. Gerhard "Index Checking Is Always Worthwhile" Paseman, 2013.05.23 –  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)$.

-
This answers perfectly my first question. Thanks! –  Hans 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.

-
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? –  Hans Stricker May 23 '13 at 11:54
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)$. –  Mark Sapir May 23 '13 at 12:32