2

Suppose A, B are finite binary chains that hold AB = BA (* is the concatenation operator). How can I show there exists a binary chain C such that A, B are of the form CCC...C?

David Dvash
  • 21

1 Answers1

0

By equidivisibility of a free monoid (i.e. the set of finite strings from some alphabet), there exists a $D$ such that either $A = BD = DB$ or $B = AD= DA$. Except in trivial cases ($A = B$, or one of them is the empty string), this now gives you a strictly shorter string to work with. Induction finishes the job.

Arthur
  • 199,419
  • It seems like a simple question but I'm getting lost within it... – David Dvash Apr 18 '15 at 00:19
  • @DavidDvash The set of finite, binary strings together with the concatenation operation is called the free monoid on two elements. A free monoid on any number of elements possesses a property called "equidivisibility". That means that if $AB = XY$, then there is some $S$ such that either $A = XS$ and $SB = Y$, or such that $AS = X$ and $B = SY$. If we actually have $X = B$ and $Y = A$, such as in your case, it becomes what I wrote above. – Arthur Apr 18 '15 at 09:34
  • In this case, since we have either $A = DB = BD$, or $B = AD = DA$, if we're not in a trivial case ($A = B$ or either $A$ or $B$ is the empty string, in which case the result follows immediately), and, say $A = BD = DB$, then $DB$ is strictly shorter than $AB$. Now you can work with induction. The result is obvious if $AB$ is a string of length $1$. For any longer string, either it's trivial, or $A = DB = BD$, and if $D$ and $B$ are both of the form $CC\cdots C$, then so is $A$. – Arthur Apr 18 '15 at 09:38
  • How AB can be of length 1 if A,B are binary? I mean, doesn't A or B must have at least 2 different characters so length(AB) >= 2? – David Dvash Apr 18 '15 at 16:30
  • @DavidDvash No, binary string means that it contains only zeroes and ones. So "0" and "1" are both binary strings, and so is "011100101101". And, importantly, so is " ", which is called the empty string. – Arthur Apr 18 '15 at 17:59
  • Is there a relevant info or more explanation online about this theorm? How does this theorm called? – David Dvash Apr 18 '15 at 19:08