If for two strings a+b=b+a holds true, what properties can we derive about such strings?

Question

Given two strings a and b such that a+b = b+a, what can we infer about such strings? Its like an abstract question where we don't know anything else but want to know about the properties of such strings.

Example:

a = ABC
b = ABCABC
a+b = ABCABCABC
b+a = ABCABCABC

I think the following holds true but I believe we can take this further -

• If |a| = |b| then it implies both strings are equal.
• If |a| < |b|, then b contains a as proper prefix as well as proper suffix.
• I believe we can also prove that there exists some string t which is repeating in both strings a and b but I can't prove it. Any help would be appreciated.

In general, I have seen a+b and b+a comparisons, and not just equality are very useful.

Answer 1

I'm going to denote concatenation of $a$ and $b$ by $ab$, rather than $a + b$. If I want $n$ copies of $a$ in a row, I will denote it by $a^n$.

We can do a kind of Euclidean algorithm-style argument to establish that there is some atomic string $c$ such that both $a$ and $b$ are a number of copies of $c$ end-to-end.

Take $a_0 = a$ and $b_0 = b$, assuming that $|b| \ge |a|$. Otherwise, switch their roles. For $n \ge 0$, let us perform the following step, recursively.

Step $n$: we begin with two strings $a_n, b_n$ such that $a_nb_n = b_na_n$, and $|a_n| \le |n_0|$. Let $m_n$ be the greatest number of copies of $a_n$ that we can fit as a prefix of $b_n$. That is, $m_n$ is the largest number such that there exists some $c$ such that $b_n = a_n^{m_n} c$. Let $a_{n+1}$ be such a string $c$, and let $b_{n+1} = a_n$. If $a_{n+1}$ is an empty string, return $b_{n+1}$ and terminate, otherwise proceed to Step $n+1$.

I claim that, given $a_n, b_n$ as above, we also have $a_{n+1}b_{n+1} = b_{n+1}a_{n+1}$. Given that $b_{n+1} = a_n$ and $b_n = a^{m_n}_n a_{n+1}$, we get \begin{align*} a_n^{m_n} b_{n+1} a_{n+1} &= a_n^{m_n + 1} a_{n+1} \\ &= a_n b_n \\ &= b_n a_n \\ &= a^{m_n}_n a_{n+1} a_n \\ &= a^{m_n}_n a_{n+1} b_{n+1}. \end{align*} Since both strings on either side have the same prefix of $a_n^{m_n}$, we may cancel it to get $$b_{n+1} a_{n+1} = a_{n+1}b_{n+1}$$ as required.

Further, we can conclude that $|a_{n+1}| \le |b_{n+1}|$, as before, as if we had $|a_{n+1}| > |b_{n+1}|$ then from the previous claim, both $a_{n+1} b_{n+1}$ and $b_{n+1} a_{n+1}$ would start with the same $|b_{n+1}|$ symbols, which means both have a prefix of $b_{n+1}$. Thus, $a_{n+1}$ must begin with $b_{n+1}$, i.e. there is a $d$ such that $a_{n+1} = b_{n+1} d = a_n d$. We also know that $b_n = a_n^{m_n} a_{n+1} = a_n^{m_n+1}d$, but this contradicts our definition of $m_n$: it was supposed to be as large as possible. Thus, $|a_{n+1}| \le |b_{n+1}|$ as required.

So, each Step $n+1$ can be completed, with all the assumptions in tact, if Step $n$ can be completed.

I also claim that the procedure terminates. Our construction has: $$|b_0| \ge |a_0| = |b_1| \ge |a_1| = |b_2| \ge \ldots$$ While the steps are not terminated, to get from Step $n$ to Step $n+1$, we are removing at least one copy of $a_n$ from $b_n$ (there can't be zero copies as in the previous argument: $b_n a_n = a_n b_n$, so one copy or more of $a_n$ must lie in $b_n$). Hence, the strings are getting strictly shorter, while still being non-negative. Eventually, we must have $a_n$ be the empty string, and $b_n$ will be returned.

Let $c$ be this returned string. Can we show that each $a_n$ is a power of this string? To do this, we could do a reverse Euclidean algorithm-style induction. Certainly, if $k$ was the final step, then $a_{k+1}$ is empty and hence equal to $c^0$, and $b_{k+1} = c^1$. So, this gives us a base case.

Now, suppose that $a_{n+1} = c^p$ and $b_{n+1} = c^q$ for some $p, q \ge 0$. Then $a_n = b_{n+1} = c^q$, and $b_n = a_n^{m_n} a_{n+1} = (c^q)^{m_n}c^p = c^{qm_n + p}$. Thus, by backwards induction all of our $a_n$s and $b_n$s are powers of $c$, including $a = a_0$ and $b = b_0$.