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?

1more comment