Ubiquitous Zimin words - MathOverflow

Ubiquitous Zimin words

2011-12-30T19:25:59Z

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.

Answer by Gerhard Paseman for Ubiquitous Zimin words

2011-12-30T20:03:53Z

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.

Gerhard "Ask Me About Hyperassociative Algebras" Paseman, 2011.12.30

Answer by Petar Markovic for Ubiquitous Zimin words

2012-09-30T09:07:02Z

I am about to go chair a dissertation defence where the candidate uses an endomorphic image of Zimin words (of his invention) to construct various counterexamples to questions in combinatorics of finite and infinite words, mainly to do with counting palindromes in subwords and scattered subwords of finite and infinite words. The image in question are words on a three-letter alphabet of the form w_0=a, w_1=aba, w_{n+1}=w_nc^nw_n, which the candidate Bojan Basic calls highly potential words. This is obviously a related sequence to Zimin words, and the candidate managed to construct several examples and counterexamples using these, including a counterexample to an already published "theorem" by non-unknown authors.

I suppose it qualifies as an application of Zimin words as highly potential ones are clearly homomorphic images of Zimin words and inspired by them. Don't know if it is too late for your book. Counter-question: has anybody seen these highly potential words before?

Petar Markovic