10
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Mark, is this an updated version of your old notes? $\endgroup$
    – Benjamin Steinberg
    Commented Jan 2, 2012 at 2:41
  • $\begingroup$ @Ben: Yes, it is. $\endgroup$
    – user6976
    Commented Jan 3, 2012 at 2:45
  • $\begingroup$ It's a trivial comment, but seems worth making: this sequence is the sequence 2-adic valuations of the integers. $\endgroup$
    – James Cranch
    Commented Sep 30, 2012 at 12:49
  • $\begingroup$ @James: Yes, this is in my question, the number of zeroes at the end of binary expansions of integers. $\endgroup$
    – user6976
    Commented Sep 30, 2012 at 13:35
  • $\begingroup$ 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. $\endgroup$
    – James Cranch
    Commented Sep 30, 2012 at 14:42

2 Answers 2

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! I knew of some semigroup applications including finite bases properties but not these. $\endgroup$
    – user6976
    Commented Dec 30, 2011 at 20:12
  • $\begingroup$ You're welcome. If and when I get back to hyperidentities, I may use a generalization of Zimin words to see what results I can get for other similarity types; I'll add to this answer anything interesting and Zimin-related that comes up. Gerhard "Ask Me About System Design" Paseman, 2011.12.30 $\endgroup$
    – Gerhard Paseman
    Commented Dec 30, 2011 at 20:22
5
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Is the candidate concerned with decidability or recursion theoretic aspects? I am interested in the decidability of a problem which may be related. Gerhard "Ask Me About System Design" Paseman, 2012.09.30 $\endgroup$
    – Gerhard Paseman
    Commented Sep 30, 2012 at 18:38

You must log in to answer this question.