%% This document created by Scientific Word (R) Version 3.0


\documentclass[12pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{amsfonts}

\setcounter{MaxMatrixCols}{10}
%TCIDATA{OutputFilter=Latex.dll}
%TCIDATA{Version=5.00.0.2552}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{LastRevised=Monday, January 05, 2004 12:17:09}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{Language=American English}

\textwidth= 6.25in
\textheight= 9.0in
\topmargin = -10pt
\evensidemargin=10pt
\oddsidemargin=10pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}{Lemma}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{definition}[1][Definitions]{\noindent\textbf{#1.}}{}
\newenvironment{notation}[1][Notation]{\noindent\textbf{#1. }}{}
\newenvironment{proof}[1][Proof]{\noindent{\it #1. }}{\ \rule{0.5em}{0.5em}}
%\input{tcilatex}
\def\func{\mathrm}

\begin{document}


\begin{center}
\textbf{ARITHMETIC ON BLOCKS} \vskip20pt \textbf{Abigail Hoit}\\[0pt]
{\smallit Department of Mathematics, Elmhurst College, Elmhurst, IL 60126}%
\\[0pt]
\texttt{abigailh@elmhurst.edu}\\[0pt]
\end{center}

\vskip 30pt \centerline{\smallit Received: 11/29/02, Revised:
1/5/04, Accepted: 1/21/04, Published: 1/22/04 }
\vskip  30pt

\centerline{\bf Abstract}

\noindent
We \hfil introduce \hfil a \hfil binary \hfil operation \hfil on \hfil
strings
\hfil (blocks)
\hfil of
\hfil elements 
\hfil
 \hfil from \hfil the \hfil set  \\
$\{0,1,\ldots ,m-1\}$ where $m$ is an arbitrary integer greater than 1. 
This operation is an extension of one introduced by Konrad Jacobs and
Michael Keane in the 1960's for blocks of 0's and 1's.  We show that the
extended operation is associative, introduce the concept of similar, cyclic,
and circular blocks and provide a unique factorization theorem under this
operation up to the similarity of the factors.  We also give the
conditions for commutativity of indecomposable blocks.

\pagestyle{myheadings} 
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC
JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 4 (2004), \#A01\hfill}

\thispagestyle{empty} \baselineskip=15pt \vskip 20pt

\section*{\protect\normalsize 1. Introduction}

\hskip\parindent In the late 1960's, Konrad Jacobs and Michael Keane
introduced an associative binary operation on strings (blocks) of 0's and
1's \cite{ja:orig,ke:orig}. This operation, defined in Section 2 below,
produces a new block of 0's and 1's with length equal to the product of the
lengths of the original blocks. Jacobs and Keane used this operation to
define \emph{block product sequences} for use in their work on ergodic
theory. \ These sequences also happen to be equivalent to binary Q-additive
functions \cite[Chapter 3]{mythesis}.

 We \hfil  extend \hfil the \hfil Jacobs\,--\,Keane \hfil
operation
\hfil to \hfil blocks \hfil of \hfil elements \hfil from \hfil the
\hfil set\\$\{0,1,\dots ,m-1\}$ where $m$ is an arbitrary integer
greater than 1. \ We then show that the associativity of the operation is
preserved (Theorem 1 in Section 3). \ In Section 4, we introduce the
definition of
\emph{indecomposable}, \emph{similar}, and \emph{cyclic} blocks and
then give a unique factorization theorem into non-cyclic indecomposable
blocks up to the similarity of the blocks. In Section 5, we state the
definition of a \emph{circular} block and give the conditions for
commutativity of indecomposable blocks as Theorem 3.



For readers who are familiar with the subject of combinatorics on words, we
note that the subject of block products bears some similarity to it. \ The
basic associative operation used in the former subject is not the block
product operation described here, but that of simple concatenation of
strings (words). \ For a thorough introduction to the subject of
combinatorics on words, see \cite{lo:cow}.

\vskip 30pt

\section*{\protect\normalsize 2. Block Products}

\hskip\parindent Define a 2-\emph{block} to be a non-empty string of 0's and
1's. We write $A^{\prime}$ to denote the block that has the same length as $%
A $, but with the 0's and 1's swapped. For example, if $A=00101$, then $%
A^{\prime}=11010$. The operator $\times$, introduced by Konrad Jacobs and
Michael Keane in the 1960's \cite{ja:orig,ke:orig} is defined as follows.


Let $A$ be a 2-block. Then we define 
\begin{equation*}
A\times0=A\text{ and }A\times1=A^{\prime}.
\end{equation*}

If $B=b_{0}b_{1}\cdots b_{k}$ is also a 2-block, then we define 
\begin{equation*}
A\times B=\left( A\times b_{0}\right) \cdot\left( A\times b_{1}\right)
\cdot~\cdots~\cdot\left( A\times b_{k}\right) ,
\end{equation*}
where the $\cdot$ symbol denotes the concatenation of the blocks.

The following examples illustrate the operation $\times$.%
\begin{align*}
00101\times001 & =\left( 00101\times0\right) \cdot\left( 00101\times
0\right) \cdot\left( 00101\times1\right) \\
& =00101\cdot00101\cdot11010 \\
& =001010010111010 \\
& \\
001\times00101 & =\left( 001\times0\right) \cdot\left( 001\times0\right)
\cdot\left( 001\times1\right) \cdot\left( 001\times0\right) \cdot\left(
001\times1\right) \\
& =001\cdot001\cdot110\cdot001\cdot110 \\
& =001001110001110.
\end{align*}

Now, let $m$ be an integer greater than 1. An \emph{m-block} is a non-empty
string of elements from the set $\{0,1,\dots,m-1\}$. We define the
(extended) operator $\times$ as follows.

Let $A=a_{0}a_{1}\cdots a_{j}$ be an $m$-block and $b$ be an integer$,0\leq
b<m$. Then 
\begin{equation*}
A\times b=a_{0}\oplus b\,\,\,\,a_{1}\oplus
b\,\,\,\,\cdots\,\,\,\,a_{j}\oplus b,
\end{equation*}
where $\oplus$ denotes addition modulo $m$. \ If $B=b_{0}b_{1}\cdots b_{k}$
is also a 2-block, then the \emph{block product} $A\times B$ is defined as
before, that is, 
\begin{equation*}
A\times B=\left( A\times b_{0}\right) \cdot\left( A\times b_{1}\right)
\cdot~\cdots~\cdot\left( A\times b_{k}\right) .
\end{equation*}

The following example illustrates this operation for $m=6$.%
\begin{align*}
2450\times23 & =\left( 2450\times2\right) \cdot\left( 2450\times3\right) \\
& =4012\cdot5123 \\
& =40125123
\end{align*}

\begin{notation}
Throughout this paper, $m$ is assumed to be an integer greater than 1. All
blocks are $m$-blocks. \ The operator $\times$ \ is the block product
operator associated with $m$ and addition modulo $m$ is denoted by the
operator $\oplus.$ \ The operator $\cdot$ denotes concatenation. \ If $A$ is
a particular $m$-block, its length is written as $|A|$ and for $0\leq i<|A|,$
$A\left[ i\right] $ is the $(i+1)^{th}$ element of $A$. \ For example, if $%
A=2468,$ then $A\left[ 0\right] =2,$ $A\left[ 1\right] =4,$ and so on.
\end{notation}



It follows immediately from the definition of the block product $A\times B$
that 
\begin{equation}
|A\times B|=|A||B|
\end{equation}
and that, for $0\leq n<|A||B|,$%
\begin{equation}
(A\times B)\left[ n\right] =A\left[ r_{0}\right] \oplus B\left[ r_{1}\right]
,
\end{equation}
where $r_{0}$ and $r_{1}$ are the unique integers (guaranteed by the
division algorithm) for which 
\begin{equation*}
n=r_{0}+r_{1}|A|,\quad0\leq r_{0}<|A|,\quad0\leq r_{1}<\left\vert
B\right\vert .
\end{equation*}

\vskip 30pt

\section*{\protect\normalsize 3. Associativity}

\hskip\parindent We show in Theorem 1 below that $\times$ is associative. \
We first state the following extension of the division algorithm, which can
be easily proved from the division algorithm by mathematical induction.

\begin{lemma}
Let $a_{0},a_{1},\ldots,a_{k}$ be integers greater than 1. \ For each
integer $n$ in the range $0\leq n<a_{0}a_{1}\cdots a_{k},$ there exist
unique integers $r_{0},r_{1},\ldots,r_{k}$ such that 
\begin{equation*}
n=r_{0}+r_{1}a_{0}+r_{2}a_{0}a_{1}+\cdots+r_{k}a_{0}a_{1}\cdots
a_{k-1},\quad0\leq r_{i}<a_{i}\quad(i=0,1,\ldots,k).
\end{equation*}
\end{lemma}

\begin{theorem}
The operator $\times$ is associative.
\end{theorem}

\begin{proof}
Let $A,B,$ and $C$ be blocks. \ We need to show that $(A\times B)\times
C=A\times(B\times C).$ \ We first note that by (1), 
\begin{equation*}
\left\vert \left( A\times B\right) \times C\right\vert =\left\vert
A\right\vert \left\vert B\right\vert \left\vert C\right\vert =\left\vert
A\times\left( B\times C\right) \right\vert .
\end{equation*}
Let $n$ be an integer with $0\leq n<\left\vert A\right\vert \left\vert
B\right\vert \left\vert C\right\vert .$ \ By Lemma 1, there are unique
nonnegative integers $r,s,$ and $t,$ such that%
\begin{equation*}
n=r+s\left\vert A\right\vert +t\left\vert A\right\vert \left\vert
B\right\vert ,\quad0\leq r<\left\vert A\right\vert ,\quad0\leq s<\left\vert
B\right\vert ,\quad0\leq t<\left\vert C\right\vert .
\end{equation*}
By repeated applications of (2), we have%
\begin{equation*}
\left( \left( A\times B\right) \times C\right) \left[ n\right] =A\left[ r%
\right] \oplus B\left[ s\right] \oplus C\left[ t\right] =\left(
A\times\left( B\times C\right) \right) \left[ n\right],
\end{equation*}
which completes the proof.
\end{proof}

We note that the associativity of $\times$ gives the set of $m$-blocks a
monoid structure with (right and left-hand) identity element given by the
singleton block $0.$ \ There is not a group structure, however, because no
inverse exists for any block of length greater than 1.

\vskip 30pt

\section*{\protect\normalsize 4. Unique Factorization}

Because of the associativity of $\times,$ we may write any finite block
product $A_{0}\times A_{1}\times\cdots\times A_{k}$ without ambiguity. \ If,
for a given block $B,$ there exist blocks $A_{0},A_{1},\ldots,A_{k}$ so that 
$B=A_{0}\times A_{1}\times\cdots\times A_{k},$ we call this a \emph{%
factorization} of $B$. \ We say that a block $B$ is called \emph{%
indecomposable} if $B=A\times C$ implies $\left\vert A\right\vert =1$ or $%
\left\vert C\right\vert =1.$ \ Theorem 2 below gives the conditions for
unique factorization of blocks into indecomposable blocks of a certain type.
\ We will need the following definitions and lemmas for the proof of this
theorem.



\begin{definition}
\begin{description}
\item[(a)] The block $B$ is called \emph{cyclic of difference d }if $B\left[
k+1\right] -B\left[ k\right] \equiv d\,\left( \func{mod \,}m\right) $ for
$ 0\leq k<\left\vert B\right\vert -1.$

\item[(b)] The blocks $A$ and $B$ are called \emph{similar} if $\left\vert
A\right\vert =\left\vert B\right\vert $ and $A\left[ k\right] -B\left[ k%
\right] $ is constant modulo $m$ for $0\leq k<\left\vert A\right\vert .$ \
We note that this is clearly an equivalence relation and write $A\cong B$ to
mean that $A$ and $B$ are similar.

\item[(b$^{\prime}$)] An equivalent definition for $A\cong B$ is that $%
A=B\times c$ for some integer $c,\,0\leq c<m.$
\end{description}
\end{definition}



The following lemma gives us left and right cancellation for the $\times$
operator.

\begin{lemma}
Let $A,B,C,$ and $D$ be blocks such that $A\times C\cong B\times D.$ \ Then $%
A\cong B$ if and only if $C\cong D.$
\end{lemma}

\begin{proof}
By the definition of similar blocks, $\left\vert A\times C\right\vert
=\left\vert B\times D\right\vert .$ \ Thus, by (1), we have 
\begin{equation}
\left\vert A\right\vert \left\vert C\right\vert =\left\vert B\right\vert
\left\vert D\right\vert .
\end{equation}
Also, by the definition of similar blocks, there is some positive integer $s$
such that 
\begin{equation}
\left( A\times C\right) \left[ k\right] -\left( B\times D\right) \left[ k%
\right] \equiv s\,\left( \func{mod\,}m\right) ,\quad0\leq k<\left\vert
A\right\vert \left\vert C\right\vert .
\end{equation}

Suppose first that $A\cong B.$ \ Then $\left\vert A\right\vert
=\left\vert B\right\vert ,$ (and hence by (3), we have $\left\vert
C\right\vert =\left\vert D\right\vert ),$ and there exists a positive
integer $t$ such that 
\begin{equation}
A\left[ k\right] -B\left[ k\right] \equiv t\,\left( \func{mod \,}m\right)
,\quad0\leq k<|A|.
\end{equation}
Let $n$ be an integer such that $0\leq n<\left\vert A\right\vert \left\vert
C\right\vert .$ \ By the division algorithm, there exist unique positive
integers $q$ and $r$ such that $0\leq r<\left\vert A\right\vert ,0\leq
q<\left\vert C\right\vert $ and $n=q\left\vert A\right\vert +r.$ \ So, by
(2) and (5), we have 
\begin{equation}
\left( A\times C\right) \left[ n\right] =A\left[ r\right] \oplus C\left[ q%
\right] =B\left[ r\right] \oplus t\oplus C\left[ q\right] .
\end{equation}
On the other hand, since $\left\vert A\right\vert =\left\vert B\right\vert $
and $\left\vert C\right\vert =\left\vert D\right\vert ,$ it also follows
from (2) that 
\begin{equation}
\left( B\times D\right) \left[ n\right] =B\left[ r\right] \oplus D\left[ q%
\right] .
\end{equation}
By (6) and (7) we obtain 
\begin{equation}
\left( A\times C\right) \left[ n\right] -\left( B\times D\right) \left[ n%
\right] \equiv t+C\left[ q\right] -D\left[ q\right] \,\left( \func{mod
\,} m\right) .
\end{equation}
By (4) and (8) it follows that $C\left[ q\right] -D\left[ q\right] \equiv
s-t\,\left( \func{mod \,}m\right) .$ \ Since $q$ varies from $0$ to
$\left\vert C\right\vert -1$ as $n$ varies from $0$ to $\left\vert
A\right\vert
\left\vert C\right\vert -1,$ we have $C\cong D.$

Now suppose that $C\cong D.$ \ As before, by the definition of similarity,
we have $\left\vert A\right\vert =\left\vert B\right\vert $ and $\left\vert
C\right\vert =\left\vert D\right\vert ,$ and we have a positive integer $u$
such that 
\begin{equation}
C\left[ k\right] -D\left[ k\right] \equiv u\,\left( \func{mod\,}m\right)
,\quad0\leq k<|C|.
\end{equation}
If we let $n,r,$ and $q$ be as above, then (7) is still true, and we have,
by (2) and (9), 
\begin{equation}
\left( A\times C\right) \left[ n\right] =A\left[ r\right] \oplus C\left[ q%
\right] =A\left[ r\right] \oplus u\oplus D\left[ q\right] .
\end{equation}
By (4), (7), (9), and (10), it follows that $A\left[ r\right] -B\left[ r%
\right] \equiv s-u\,\left( \func{mod\,}m\right) .$ \ Since $r$ varies from
$0$ to $\left\vert A\right\vert -1$ as $n$ varies from $0$ to $\left\vert
A\right\vert \left\vert C\right\vert -1,$ we have $A\cong B.$
\end{proof}

The next lemma provides unique factorization into 2 indecomposable blocks
with the uniqueness up to blocks that are either similar or cyclic of the
same difference. \ The following notation will be used throughout the proof.
\ The block of the first $k$ elements in a block $A$ will be denoted by $A%
\left[ 0:k-1\right] .$

\begin{lemma}
Let $A$ and $B$ be indecomposable blocks of length greater than 1. \ Suppose
that $A\times C\cong B\times D$ for some blocks $C$ and $D.$ \ Then either $%
A\cong B$ and $C\cong D$ or $A$ and $B$ are both cyclic of the same
difference.
\end{lemma}

\begin{proof}
We first note that since $A\times C\cong B\times D,$ statements (3) and (4)
from the proof of Lemma 2 still hold and for all integers $k,$ with $%
0<k\leq\left\vert A\right\vert \left\vert C\right\vert ,$ we have 
\begin{equation}
\left( A\times C\right) \left[ 0:k-1\right] \cong\left( B\times D\right) %
\left[ 0:k-1\right] .
\end{equation}
We may assume without loss of generality that $\left\vert A\right\vert
\leq\left\vert B\right\vert .$ \ We will distinguish three cases: $%
\left\vert A\right\vert =\left\vert B\right\vert ,$ $\left\vert A\right\vert
<\left\vert B\right\vert $ where $\left\vert A\right\vert $ divides $%
\left\vert B\right\vert $, and $\left\vert A\right\vert <\left\vert
B\right\vert $ where $\left\vert A\right\vert $ does not divide $\left\vert
B\right\vert .$ \ We will show the second case to be impossible.

Suppose first that $\left\vert A\right\vert =\left\vert B\right\vert .$ \ We
observe that $\left( A\times C\right) \left[ 0:\left\vert A\right\vert -1%
\right] =A\times C\left[ 0\right] \cong A$ and $\left( B\times D\right) %
\left[ 0:\left\vert A\right\vert -1\right] =\left( B\times D\right) \left[
0:\left\vert B\right\vert -1\right] =B\times D\left[ 0\right] \cong B.$ \
Thus, it follows from (11) that $A\cong B,$ and hence, from Lemma 2, that $%
C\cong D.$

Now, suppose that $\left\vert A\right\vert <\left\vert B\right\vert $ and $%
\left\vert A\right\vert $ divides $\left\vert B\right\vert ,$ i.e., $%
\left\vert B\right\vert =n\left\vert A\right\vert $ for some integer $%
n\geq2. $ \ Then, by the definition of the block product, 
\begin{align}
\left( A\times C\right) \left[ 0:\left\vert B\right\vert -1\right] & =\left(
A\times C\left[ 0\right] \right) \cdot\left( A\times C\left[ 1\right]
\right) \cdot~\cdots~\cdot\left( A\times C\left[ n-1\right] \right)  \notag
\\
& =A\times C\left[ 0:n-1\right] .
\end{align}
On the other hand, 
\begin{equation}
\left( B\times D\right) \left[ 0:\left\vert B\right\vert -1\right] =B\times D%
\left[ 0\right] \cong B.
\end{equation}
It follows from (11), (12), and (13)$,$ that $B\cong A\times C\left[ 0:n-1%
\right] .$ \ This contradicts the indecomposability of $B.$ \ Therefore, it
is not possible to have $\left\vert A\right\vert <\left\vert B\right\vert $
such that $\left\vert A\right\vert $ divides $\left\vert B\right\vert.$

It remains to consider the situation where $\left\vert A\right\vert
<\left\vert B\right\vert $ and $\left\vert A\right\vert $ does not divide $%
\left\vert B\right\vert .$ \ We will show that in this case, $A$ and $B$ are
both cyclic of the same difference. \ Let $q$ and $r$ be the unique
nonnegative integers guaranteed by the division algorithm such that 
$$
\left\vert B\right\vert =q\left\vert A\right\vert +r,\quad0<r<\left\vert
A\right\vert .
$$
Then
\begin{align}
\left( A\times C\right) \left[ 0:\left\vert B\right\vert -1\right] & =\left(
A\times C\left[ 0\right] \right) \cdot\left( A\times C\left[ 1\right]
\right) \cdot~\cdots~  \notag \\& \qquad
\cdot\left( A\times C\left[ q-1\right] \right) \cdot\left( A\left[
0:r-1\right] \times C\left[ q\right] \right) .
\end{align}
On the other hand, (13) still holds. \ Thus, by (11), (13), and (14), we
have 
\begin{equation}
B\cong\left( A\times C\left[ 0\right] \right) \cdot\left( A\times C\left[ 1%
\right] \right) \cdot~\cdots~\cdot\left( A\times C\left[ q-1\right] \right)
\cdot\left( A\left[ 0:r-1\right] \times C\left[ q\right] \right) .
\end{equation}
Now, the block of the second $\left\vert B\right\vert $ elements of $B\times
D$ is the block $B\times D\left[ 1\right] ,$ and is therefore also similar
to $B.$ \ It follows from (4) that the block of the second $\left\vert
B\right\vert $ elements of $A\times C$ is also similar to $B.$ \ On the
other hand, if we let $S$ be the block at the end of the block $A$, such
that $A=A\left[ 0:r-1\right] \cdot S,$ then the block of the second $%
\left\vert B\right\vert $ elements of $A\times C$ is either given by 
\small
$$
\left( S\times C\left[ q\right] \right) \cdot\left( A\times C\left[ q+1%
\right] \right) \cdot\left( A\times C\left[ q+2\right] \right)
\cdot \, \cdots \, \cdot\left( A\times C\left[ 2q-1\right] \right)
\cdot\left( A%
\left[ 0:2r-1\right] \times C\left[ 2q\right] \right),
$$ \normalsize
if $2r\leq\left\vert A\right\vert ,$ or 
\small
$$
\left( S\times C\left[ q\right] \right) \cdot\left( A\times C\left[ q+1%
\right] \right) \cdot\left( A\times C\left[ q+2\right] \right)
\cdot \,\cdots \,\cdot\left( A\times C\left[ 2q\right] \right) \cdot\left(
A%
\left[ 0:2r-\left\vert A\right\vert -1\right] \times C\left[ 2q+1\right]
\right) ,
$$ \normalsize
if $2r>\left\vert A\right\vert .$ \ In either case, we have 
\begin{equation}
B\cong S\cdot\alpha_{1}\cdot\alpha_{2}\cdot~\cdots~\cdot\alpha_{n}\cdot T,
\end{equation}
where $n=q-1$ or $q,$ each of the $\alpha_{i}$ is similar to $A,$ and $%
T\cong A\left[ 0:2r-1\right] $ or $T\cong A\left[ 0:2r-\left\vert
A\right\vert -1\right] .$ \ Thus from (15) and (16), we have 
\begin{equation}
\left( A\times C\left[ 0\right] \right) \cdot\left( A\times C\left[ 1\right]
\right) \cdot~\cdots~\cdot\left( A\times C\left[ q-1\right] \right)
\cdot\left( A^{r}\times C\left[ q\right] \right) \cong
S\cdot\alpha_{1}\cdot\alpha_{2}\cdot~\cdots~\cdot\alpha_{n}\cdot T.
\end{equation}
By comparing the two sides of (17), and noting that each $\alpha_{i}$ and
each $A\times C(h)$ is similar to $A,$ we see that $A$ begins with a block
that is similar to $S$ and that each successive block of length $\left\vert
S\right\vert $ in $A$ is similar to $S$ as well. \ It follows that for any
integers $j$ and $k,$ with $1\leq j\leq\left\vert A\right\vert -1$ and $%
j+k\left\vert S\right\vert \not \equiv 0\left( \func{mod\,}\left\vert
A\right\vert \right) $, we have%
\begin{equation}
A\left[ \left( j+k\left\vert S\right\vert \right) \func{mod\,}\left\vert
A\right\vert \right] -A\left[ (j-1+k\left\vert S\right\vert )\func{mod\,}
\left\vert A\right\vert \right] \equiv A\left[ j\right] -A\left[ j-1\right]
\,\left( \func{mod\,}m\right) .
\end{equation}
We now show that this equivalence implies that $A$ is cyclic.

Let $g=\gcd\left( \left\vert A\right\vert ,\left\vert B\right\vert \right) .$
\ Suppose, for the sake of contradiction, that $g>1.$ \ If we allow $j$ to
range from 1 through $g-1$ and $k$ to range from 0 through $\frac{\left\vert
A\right\vert }{g}-1$ in (18), we see that the blocks of length $g$ that lie
inside $A$ beginning at positions $\left\{\,\, 0
\,\,\func{mod\,}\left\vert A\right\vert ,\,\,\left\vert S\right\vert
\func{mod\,}\left\vert A\right\vert ,\,\, 2\left\vert S\right\vert
\func{mod\,}\left\vert A\right\vert ,\,\, \dots,\,\, \left( 
\frac{\left\vert A\right\vert }{g}-1\right) \left\vert S\right\vert 
\func{mod\,
}\left\vert A\right\vert \,\,\right\} $\hfil are\hfil similar \hfil to\\
 $A\left[ 0:g-1\right]
.$
\ However, by the definition of $S,$ we have $\left\vert B\right\vert
=\left( q+1\right) \left\vert A\right\vert -\left\vert S\right\vert .$ \
Thus, these positions are exactly $\left\{ 0,g,2g,\dots,\left\vert
A\right\vert -g\right\} ,$ and so $A=\gamma_{1}\cdot\gamma_{2}\cdot~\cdots~%
\cdot\gamma_{\frac{\left\vert A\right\vert }{g}},$ where each of the $%
\gamma_{i}$ is similar to $A\left[ 0:g-1\right] .$ \ That is, $A$ is the
product of $A\left[ 0:g-1\right] $ with some other block of length $\dfrac{%
\left\vert A\right\vert }{g}.$ \ This contradicts the indecomposability of $%
A.$ \ Thus, $g=1.$

By the definition of $S$ and $g,$ we have $\gcd(\left\vert S\right\vert
,\left\vert A\right\vert )=1$ also. \ Therefore, for each $j,$ $2\leq
j\leq\left\vert A\right\vert ,$ there is some integer $k$ such that $\left(
j+k\left\vert S\right\vert \right) \func{mod\,}\left\vert A\right\vert
=j-1,$ and so, by (18), we have 
\begin{equation*}
A\left[ j-1\right] -A\left[ j-2\right] \equiv A\left[ j\right] -A\left[ j-1%
\right] \,\left( \func{mod\,}m\right) ,\quad2\leq j\leq\left\vert
A\right\vert .
\end{equation*}
Thus, $A$ is cyclic. \ It remains only to show that $B$ is cyclic and of the
same difference as $A.$ \ Let $h$ be an integer with $2\leq h\leq\left\vert
B\right\vert .$ \ Consider the two-element blocks in $B$ given by $B\left[
h-1\right] B\left[ h\right] $ and $B\left[ h-2\right] B\left[ h-1\right] $.
\ By (15) and (16), each of these two-element blocks is similar to a block
that lies entirely in $A.$ \ Since $A$ is cyclic, the differences between
the two elements in these blocks must be the same. \ Since $h$ was
arbitrary, we have 
\begin{equation*}
B\left[ h-1\right] -B\left[ h-2\right] \equiv B\left[ h\right] -B\left[ h-1%
\right] \equiv A\left[ 1\right] -A\left[ 0\right] \,\left( \func{mod\,}
m\right) ,\quad2\leq h\leq\left\vert B\right\vert .
\end{equation*}
Thus, $B$ is cyclic of the same difference as $A.$
\end{proof}

\begin{theorem}
(Unique Factorization) \ Let $k\geq1,$ and let $A_{1},A_{2},\dots,A_{k}$ be
indecomposable, non-cyclic blocks of length greater than 1. \ If $%
A_{1}\times A_{2}\times\cdots\times A_{k}=B_{1}\times
B_{2}\times\cdots\times B_{l},$ with $B_{j}$ indecomposable, non-cyclic and
of length greater than 1 for all $j,$ then $l=k$ and $B_{j}\cong A_{j}$ for
all $j,$ $1\leq j\leq l.$
\end{theorem}

\begin{proof}
We note that in Lemma 3, we required only $A$ and $B$ to be indecomposable,
not $C$ and $D.$ \ Thus, this theorem follows immediately from Lemma 3 by
mathematical induction.
\end{proof}

\vskip 30pt

\section*{\protect\normalsize 5. Commutativity}

We can see from the following example that $\times$ is not commutative in
general. \ Let $m=6.$ \ Then, we have 
$$
2450\times23=40125123
$$
and 
$$
23\times2450=45011223,
$$
which are clearly not the same. \ Before we state the conditions for
commutativity of indecomposable blocks, we introduce the following
definition.

\begin{notation}[Definition]
A block is called \emph{circular} if it begins and ends with the same
element.
\end{notation}

\begin{theorem}
(Commutativity of Indecomposables) \ If the blocks $A$ and $B$ are
indecomposable, then $A\times B=B\times A$ if and only if at least one of
the following conditions holds:

\begin{enumerate}
\item[ \ ] 

\begin{enumerate}
\item[ \ ] 

\begin{enumerate}
\item[$\left( i\right) $] $A$ and $B$ are cyclic of the same difference and
circular.

\item[$\left( ii\right) $] $A$ or $B$ has length 1.

\item[$\left( iii\right) $] $A\cong B$.
\end{enumerate}
\end{enumerate}
\end{enumerate}
\end{theorem}

\begin{proof}
For convenience of notation, let $\alpha=\left\vert A\right\vert $ and $%
\beta=\left\vert B\right\vert .$ \ We first show that each of conditions $%
\left( i\right) -\left( iii\right) $ implies $A\times B=B\times A.$ \
Suppose first that $\left( i\right) $ holds, that is, we have 
\begin{equation}
A\left[ \alpha-1\right] =A\left[ 0\right] ,\quad B\left[ \beta-1\right] =B%
\left[ 0\right] ,
\end{equation}
and there is some integer $c$ such that for all integers $j$ and $k,$ with $%
1\leq j\leq\alpha-1$, $1\leq k\leq\beta-1,$%
\begin{equation}
A\left[ j\right] -A\left[ j-1\right] \equiv B\left[ k\right] -B\left[ k-1%
\right] \equiv c\,\left( \func{mod\,}m\right) .
\end{equation}
By repeated applications of (20), we have, for all integers $j$ and $k,$
with $1\leq j\leq\alpha-1$, $1\leq k\leq\beta-1,$%
\begin{equation}
A\left[ j\right] =A\left[ 0\right] \oplus jc,\text{ and }B\left[ k\right] =B%
\left[ 0\right] \oplus kc.
\end{equation}
Setting $j=\alpha-1$ and $k=\beta-1$ in (21), it follows from (19) that 
\begin{equation}
(\alpha-1)c\equiv\left( \beta-1\right) c\equiv0\,\left(
\func{mod\,}m\right) .
\end{equation}
We need to show that $(A\times B)\left[ h\right] =(B\times A)\left[ h\right] 
$ for all integers $h$ with $0\leq h<\left\vert A\times B\right\vert
=\alpha\beta.$

Let $h$ be an integer such that $0\leq h<\alpha\beta.$ \ By the division
algorithm, there exist unique integers $q,r,s,$ and $t,$ such that 
\begin{equation}
h=q\alpha+r=s\beta+t,\quad0\leq r,s<\alpha,\quad0\leq q,t<\beta.
\end{equation}
Now, by (2), (21), (22) and (23) we have 
\begin{align*}
(A\times B)\left[ h\right] & =A\left[ r\right] \oplus B\left[ q\right] \\
& =A[0]\oplus rc\oplus B[0]\oplus qc \\
& =A\left[ s\right] \oplus B\left[ t\right] \oplus s\left( \beta-1\right)
c\oplus q\left( 1-\alpha\right) c \\
& =A\left[ s\right] \oplus B\left[ t\right] \\
& =\left( B\times A\right) \left[ h\right] ,
\end{align*}
as claimed.

We now suppose that $\left( ii\right) $ holds. \ Without loss of generality,
we may assume that $\alpha=1.$ \ That is, $A\ $is the singleton block $a,$
where $a$ is a nonnegative integer smaller than $m.$ \ By the definition of $%
\times,$%
\begin{align*}
A\times B=a\times B & =\left( a\oplus B\left[ 0\right] \right) \cdot\left(
a\oplus B(1)\right) \cdot~\cdots~\cdot\left( a\oplus B(\beta-1)\right) \\
& =\left( B\left[ 0\right] \oplus a\right) \cdot~\cdots~\cdot\left( B\left[ 1%
\right] \oplus a\right) \cdot~\cdots~\cdot\left( B(\beta-1)\oplus a\right) \\
& =B\times a=B\times A.
\end{align*}
Finally, we suppose that $\left( iii\right) $ holds. \ By the (second)
definition of similarity, there exists an integer $d,\,0\leq d<m$ such that $%
A=B\times d.$ \ By the previous argument, the singleton block $d$ commutes
with $B.$ \ Thus, we have 
\begin{equation*}
A\times B=B\times d\times B=B\times B\times d=B\times A.
\end{equation*}

We have shown that each of conditions $\left( i\right) -\left( iii\right) $
imply that $A$ and $B$ commute. \ Now suppose that $A\times B=B\times A.$ \
We will show that at least one of conditions $\left( i\right) -\left(
iii\right) $ holds. \ Suppose that condition $\left( ii\right) $ does not
hold so that $A$ and $B$ both have length greater than 1. \ Since $A\times
B=B\times A$ and $A$ and $B$ are indecomposable, Lemma 3 implies that either 
$A\cong B$, which is condition $\left( iii\right) ,$ or $A$ and $B$ are both
cyclic of the same difference. \ It remains only to show that in the case
that $A$ and $B$ are both cyclic of the same difference but not similar,
they are circular and thus condition $\left( i\right) $ holds.

Let $t$ be an integer, and assume $A\times B=B\times A,$ $A\ncong B,$ and $A$
and $B$ are both cyclic of difference $t$. \ Now $\alpha\neq\beta,$ because
two blocks that are cyclic of the same difference and have the same length
are also similar. \ Without loss of generality, we may assume that $%
\alpha<\beta.$ \ By the definition of $\times,$ we have 
\begin{equation*}
\left( A\times B\right) \left[ \alpha-1\right] =A\left[ \alpha-1\right]
\oplus B\left[ 0\right] \qquad\text{and}\qquad\left( A\times B\right) \left[
\alpha\right] =A\left[ 0\right] \oplus B\left[ 1\right] .
\end{equation*}
Likewise, we have 
\begin{equation*}
\left( B\times A\right) \left[ \alpha-1\right] =B\left[ \alpha-1\right]
\oplus A\left[ 0\right] \qquad\text{and}\qquad\left( B\times A\right) \left[
\alpha\right] =B\left[ \alpha\right] \oplus A\left[ 0\right] .
\end{equation*}
Since $A\times B=B\times A,$ we have 
\begin{equation}
A\left[ \alpha-1\right] \oplus B\left[ 0\right] =B\left[ \alpha-1\right]
\oplus A\left[ 0\right]
\end{equation}
and 
\begin{equation}
A\left[ 0\right] \oplus B\left[ 1\right] =B\left[ \alpha\right] \oplus A%
\left[ 0\right] .
\end{equation}
However, since $B$ is cyclic of difference $t,$%
\begin{equation}
B\left[ 1\right] -B\left[ 0\right] \equiv t\equiv B\left[ \alpha\right] -B%
\left[ \alpha-1\right] ~\left( \func{mod\,}m\right) .
\end{equation}
By (24), (25), and (26), we have 
\begin{equation*}
A\left[ 0\right] -A\left[ \alpha-1\right] \equiv0~\left(
\func{mod\,}m\right) .
\end{equation*}
Since every element in $A$ is from the set $\left\{ 0,1,\ldots,m-1\right\} $%
, we have $A\left[ 0\right] =A\left[ \alpha-1\right] ,$ and hence $A$ is
circular. \ We now show that $B$ is also circular. \ We first note that $%
\alpha$ does not divide $\beta,$ since if $\alpha$ divides $\beta$ and they
are both cyclic of the same difference, $B$ is the product of $A$ with some
other block of length $\beta/\alpha,$ which contradicts the
indecomposability of $B$. \ Let $q$ and $r$ be the unique nonnegative
integers such that 
\begin{equation*}
\beta=q\alpha+r,\quad0\leq r<\alpha.
\end{equation*}
Since $\alpha$ does not divide $\beta,$ $r\geq1.$ \ By (2), we have 
\begin{equation*}
\left( A\times B\right) \left[ \beta-1\right] =A\left[ r-1\right] \oplus B%
\left[ q\right] \qquad\text{and}\qquad\left( A\times B\right) \left[ \beta%
\right] =A\left[ r\right] \oplus B\left[ q\right] .
\end{equation*}
Likewise, by the definition of $\times,$ we have 
\begin{equation*}
\left( B\times A\right) \left[ \beta-1\right] =B\left[ \beta-1\right] \oplus
A\left[ 0\right] \qquad\text{and}\qquad\left( B\times A\right) \left[ \beta%
\right] =B\left[ 0\right] \oplus A\left[ 1\right] .
\end{equation*}
Since $A\times B=B\times A,$ it follows that 
\begin{equation}
A\left[ r-1\right] \oplus B\left[ q\right] =B\left[ \beta-1\right] \oplus A%
\left[ 0\right]
\end{equation}
and 
\begin{equation}
A\left[ r\right] \oplus B\left[ q\right] =B\left[ 0\right] \oplus A\left[ 1%
\right] .
\end{equation}
However, since $A$ is cyclic of difference $t,$%
\begin{equation}
A\left[ 1\right] -A\left[ 0\right] \equiv t\equiv A\left[ r\right] -A\left[
r-1\right] ~\left( \func{mod\,}m\right) .
\end{equation}
Therefore, from (27), (28), and (29), we have 
\begin{equation*}
B\left[ 0\right] -B\left[ \beta-1\right] \equiv0~\left(
\func{mod\,}m\right) .
\end{equation*}
Thus, $B$ is circular and condition $\left( i\right) $ holds.
\end{proof}

\vskip 30pt

\begin{thebibliography}{Ho}
\bibitem[Ho]{mythesis} A. Hoit, \emph{The Distribution of Generalized
Sum-of-Digits Functions}, PhD thesis, Univ. of Illinois at Urbana-Champaign,
1999.

\bibitem[Ja]{ja:orig} K. Jacobs, \textquotedblleft Maschinenerzeugte
0-1-folgen\textquotedblright, Chapter 1 of \emph{Selecta Mathematica}, Vol.
1, Heidelberger Taschenb\"{u}cher Band 49, Springer-Verlag, 1969, pp. 1--27.

\bibitem[Ke]{ke:orig} M. Keane, \emph{Generalized Morse Sequences}, Z.
Wahrscheinlichkeitstheorie und Verw. Gebiete,\emph{\ }10 (1968), 335--353.

\bibitem[Lo]{lo:cow} M. Lothaire, \emph{Combinatorics on words} (A
collective work by Dominique Perrin, Jean Berstel, Christian Choffrut,
Robert Cori, Dominique Foata, Jean Eric Pin, Guiseppe Pirillo, Christophe
Reutenauer, Marcel-P. Sch\"{u}tzenberger, Jacques Sakarovitch and Imre
Simon), Encyclopedia of Mathematics and its Applications, 17, Addison-Wesley
Publishing Co., Reading, Mass, 1983.
\end{thebibliography}

\end{document}