# Ubiquitous Zimin words

Let $w$ be a word in letters $x_1,...,x_n$. A value of $w$ is any word of the form $w(u_1,...,u_n)$ where $u_1,...,u_n$ are words. For example, $abaaba$ is a value of $x^2$. A word $u$ is called unavoidable if every infinite word in a finite alphabet contains a value of $u$ as a subword. There is a nice characterization of unavoidable words due to Zimin. A word $u$ in $n$ letters is unavoidable if and only if a value of $u$ is a subword of the $n$th Zimin word $Z_n$ defined by induction: $Z_1=x_1$,...,$Z_n=Z_{n-1}x_nZ_{n-1}$, that is $Z_1=x_1, Z_2=x_1x_2x_1, Z_3=x_1x_2x_1x_3x_1x_2x_1,...$. Zimin words appear very often in algebra. For example, if one lists binary expressions of all numbers $1,2,3,...$ and records the numbers of 0s at the end of the numbers plus 1, one will get $12131214121...$ which is the infinite Zimin word. Values of Zimin words also appeared as $m$-sequences in Levitzki's description of Baer radical (see Jacobson's book "Structure of rings") and in the work of Schutzenberger. The Zimin words have obvious fractal structure, so these words could have appeared in other areas of mathematics as well.

Question. Do Zimin words appear in your area of mathematics?

This might be a "big list" question. But I do not know how big the list is, it may be empty. If it turn out to be big, I will make the question "community wiki".

Update 1. Googling 121312141213121 ($=Z_4$) returns 439 results including a discussion at reddit.

Update 2. The most curious among these links is this link to a US patent. It looks like Zimin words up to $Z_5$ at least have been patented before Zimin introduced them.

Update 3. This is needed for the book with the current title "Words and their meaning" which we are writing together with Mikhail Volkov. There we already have four different applications of Zimin words to different areas of algebra and would like to mention applications outside algebra as well.

-
Mark, is this an updated version of your old notes? – Benjamin Steinberg Jan 2 '12 at 2:41
@Ben: Yes, it is. – Mark Sapir Jan 3 '12 at 2:45
It's a trivial comment, but seems worth making: this sequence is the sequence 2-adic valuations of the integers. – James Cranch Sep 30 '12 at 12:49
@James: Yes, this is in my question, the number of zeroes at the end of binary expansions of integers. – Mark Sapir Sep 30 '12 at 13:35
Oops, sorry! I suppose it's not the worst thing in the world if that particular interpretation of the sequence is said in several different ways. – James Cranch Sep 30 '12 at 14:42

Yes. However, the initial application is related to semigroup varieties, so it is likely very boring to you.

In studying the hyperidentity for associativity, one can look at its representation on algebras of type <2>, a.k.a. groupoids or magmas or sets with one binary operation. Such an algebra is hyperassociative if each of the derived terms is an associative binary operation. Thus, such an algebra must be a semigroup and also satisfy xyxzxyx=xyzyx . As a result, the variety of such semigroups is locally finite, and this leads to a nice representation of all hyperassociative semigroups as a finitely based variety, with additional equations stating that x^2, x^2y, and xy^2 are also associative. Libor Polak published his analysis of this in Algebra Universalis, v 36, pp 363-378 (1996) and in an additional paper which discussed certain subvarieties of this variety.

I studied hyperassociativity (whether it could be represented as a finite set of identities) in other similarity types as well, but did not use Zimin words as much. However, a weaker version of hyperidentities involving (essentially) a subset of derived terms was studied by Denecke and others, and for hyperassociativity I believe small Zimin words were used. However, my recollection on this is hazy, and should not be relied upon.