An operation on binary strings

Question

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?

Answer 1

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)$.

Answer 2

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.