Insertion and deletion of cubed words $w^3$

Question

Evan Chen's seminal text presents the following as (spicy) problem 11C:

Consider the set of finite binary words. Show that you can't get from $01$ to $10$ using only the operation "insert or delete any cubed word $www$."

Given a word $w = a_1 a_2 \cdots a_n$, we can define an invariant $$f(w) := a_1 - a_2 + a_4 - a_5 + a_7 - a_8 + \cdots$$ and it's not hard to show that if $v$ and $w$ are equivalent under the operation, then $f(v) \equiv f(w) \pmod{3}$. Thus, $1 = f(10) \not\equiv f(01) = 2 \pmod{3}$ tells us $10$ and $01$ are inequivalent.

But this problem appears in Evan's section on group actions. Is there a group-theoretic way to preempt the invariant defined above? (I thought of it by guessing a bunch of things)

Edit: Here is a proof that the above $f$ is invariant. Start with the binary word $v:= a_1 \cdots a_n$ and insert the cubed word $(b_1 \cdots b_m)^{3}$ between $a_k$ and $a_{k+1}$. Denote the new word by $w:= c_1 \cdots c_{n+3m}$.

Let $\chi: \mathbb{Z}/3 \to \{-1,0,1\}$ be given by $\chi(1) = 1$, $\chi(2) = -1$, and $\chi(3) = 0$.

Then we have $$f(w) = \sum_{j=1}^{n+3m} \chi(j) c_j = \sum_{j=1}^{k} \chi(j) c_j + \sum_{j=k+1}^{k+3m} \chi(j) c_j + \sum_{j = k+3m+1}^{n+3m} \chi(j) c_j$$ $$ = \sum_{j=1}^{k} \chi(j) a_j + \sum_{j=1}^{m} (\chi(k+j) + \chi(k+j+m) + \chi(k+j+2m)) b_j + \sum_{j=k+1}^{n} \chi(j) a_j$$ Since $\chi(x) + \chi(x+a) + \chi(x+2a) \equiv 0 \pmod{3}$ for any $x$, $a$, we see that $$f(w) \equiv \sum_{j=1}^{n} \chi(j) a_j = f(v) \pmod{3}$$ as desired.

Answer 1

You can express your solution in the language of group theory as follows.

Let $G$ be the verbal subgroup $w^3$ on two generators $x$ and $y$. This means that $G$ has a presentation with generators $x$ and $y$ and defining relations the set of all words over $x$ and $y$ of the form $w^3$ for some word $w$ over $x$ and $y$.

We can represent each binary string to an element of $G$ by sending $0$ to $x$ and $1$ to $y$ and then extending letter by letter. In particular, the two strings of interest, $01$ and $10$, are mapped to $xy$ and $yx$, respectively.

To ask if two binary strings are equivalent via insertions and deletions of words of the form $w^3$ is the same as asking if their representatives are equal in $G$. I'll explain this in more detail in what follows.

Binary strings under the operation of concatenation/juxtaposition correspond to elements of the free monoid on $\{x,y\}$. Their images in $G$, of course, have inverses; for example, $x(x^2) = (x^2)x = 1$ so $x^{-1} = x^2$. Two words over a presentation define the same element of the group defined by the presentation if and only if there is a finite sequence of moves consisting of inserting or deleting trivial relators, i.e. $xx^{-1}$ or $x^{-1}x$ for a generator $x$, or inserting or deleting defining relators. In the group $G$, insertion or deletion of a trivial relator $xx^{-1}$ is the same as insertion or deletion of $x(x^2)$, a defining relator. All this is to say that deciding if two binary strings under concatenation modulo insertion/deletion of words of the form $w^3$ are equivalent is the same as determining if their images in $G$ are equivalent.

Now for the problem of arguing that $xy$ and $yx$ define different elements of $G$. We need a homomorphism to a well-understood non-abelian group with the property that every nontrivial element has order 3. Fortunately, there is such a group: $3 \times 3$ unitriangular matrices with coefficients in a field of three elements, $H= U(3, \mathbb{F}_3)$.

More precisely, map $x$ to the matrix $(a_{ij})$ with $a_{12} = 1$ and other off-diagonal entries zero. Map $y$ to $(b_{ij})$ with $b_{23} = 1$ and other off-diagonal entries zero. Since every element of $H$ has order 3, this map defines a homomorphism $f:G \to H$. Since $xy$ and $yx$ have different images, they represent distinct elements in $G$.

The argument above also shows that $01$ and $10$ are inequivalent under insertion and deletion of binary words of the form $w^p$ for a fixed prime $p > 2$.

The argument doesn't work for $p=2$, since in this case the verbal group $G$ (with defining relations $w^p$) is abelian and $xy$ and $yx$ have the same image. Indeed, $xy \to xy(yxyx) \to xxyx \to yx$ inserts the word $(yx)^2$ and then deletes the words $y^2$ and $x^2$.

Answer 2

This is not a new answer. It is a comment to Robert Bell's answer. In the end, it is unnecessary to introduce the "verbal group" $G$ at all. You only need a non-commutative group $H$ such that each non-identity element of $H$ has order $3$. Let $M_2$ be the free monoid on two letters $a, b$. Let $a', b'$ be two non-commuting elements of $H$. There exists a unique monoid homomorphism from $M_2$ to $H$ sending $a \to a'$ and $b \to b'$. Denote this homomorphism by $x \mapsto x'$. By hypothesis on $H$, $(ab)' \ne (ba)'$. However any cube $w^3$ in $M_2$ satisfies $(w^3)' = 1$. Hence if $ab$ and $ba$ were equivalent in $M_2$ by insertion and deletion of cubed words, it would follow that $(ab)' = (ba)'$. As this is false, $ab$ and $ba$ are not equivalent in $M_2$ by insertion and deletion of cubed words.

Edit: I will add a more "grouplike" description of Sameer Kailasa's original solution. There is also nothing very new or different here. Sameer's solution involves a sort of Fourier transform with values in $\mathbb Z_3$. Let $a : \mathbb Z \to \mathbb Z_3$ be any function with finite support; i.e. $a(j) = 0$ except for finitely many values of $j$. Let $\chi: \mathbb Z \to \mathbb Z_3$ be a non-trivial character; thus $\chi(j) = j \,\chi(1)$ and $\chi(1) \ne 0$. We can define the Fourier transform $$\mathcal F a(\chi) = \sum_j a(j) \chi(j).$$ If we are given a finite sequence with values in $\mathbb Z_3$, $a = (a_1, a_2, \dots, a_n)$, pad it by declaring $a_j = 0$ for $j \le 0$ or $j >n$, and compute $\mathcal F a(\chi)$ by the same rule. In particular, $\mathcal F{(1, 0)}(\chi) = \chi(1)$ and $\mathcal F{(0, 1)} = \chi(2) = 2 \chi(1)$. (These are the Fourier transforms of "delta functions".)

Sameer's calculation shows that $\mathcal F a$ is unchanged if a cubed word is inserted into $a$. For this the crucial property is that $\chi(k) + \chi(k + r) + \chi(k + 2r) = 0$ for any $k$ and $r$, and any character $\chi$.