"Nyldon words": understanding a class of words factorizing the free monoid increasingly

Question

BACKGROUND.

Let me first introduce some classical definitions, which appear, e.g., in §5 of Lothaire's Combinatorics on Words, in §5.1 of Reutenauer's Free Lie algebras, and in §6.1 of Victor Reiner's and my Hopf algebras in Combinatorics. If you are not a stranger to combinatorics on words, scroll right down to the question.

Words. Let $\mathfrak A$ be a finite totally ordered set. We call $\mathfrak A$ the alphabet, and refer to the elements of $\mathfrak A$ as letters. Let $\mathfrak A^\ast$ be the disjoint union of the sets $\mathfrak A^n$ over all $n \in \mathbb{N} = \left\{0, 1, 2, \ldots\right\}$. The elements of $\mathfrak A^\ast$ are called words (over the alphabet $\mathfrak A$). The concatenation of two words $u = \left(u_1, u_2, \ldots, u_n\right) \in \mathfrak A^\ast$ and $v = \left(v_1, v_2, \ldots, v_m\right) \in \mathfrak A^\ast$ is defined to be the word $\left(u_1, u_2, \ldots, u_n, v_1, v_2, \ldots, v_m\right)$; it is denoted by $uv$. The set $\mathfrak A^\ast$, equipped with concatenation as a binary operation, becomes a monoid (the neutral element is the empty word, denoted by $\varnothing$); this is the free monoid on the set $\mathfrak A$. A word $u$ is said to be a prefix of a word $w$ if and only if there exists a word $v$ (possibly empty) satisfying $w = uv$.

Lexicographic order. We define a relation $\leq$ on $\mathfrak A^\ast$ by letting two words $u = \left(u_1, u_2, \ldots, u_n\right) \in \mathfrak A^\ast$ and $v = \left(v_1, v_2, \ldots, v_m\right) \in \mathfrak A^\ast$ satisfy $u \leq v$ if and only if either there exists a positive integer $i \leq \min\left\{n,m\right\}$ such that $u_i < v_i$ and ($u_j = v_j$ for every $j < i$), or the word $u$ is a prefix of $v$. This relation $\leq$ is (the smaller-or-equal relation of) a total order on $\mathfrak A^\ast$; this order is the so-called lexicographic order (or dictionary order) on $\mathfrak A^\ast$. It satisfies many of the properties one would expect from an order on words, but one must keep in mind that while $u \leq v$ always implies $wu \leq wv$ for words $u,v,w$, it does not always imply $uw \leq vw$.

Lyndon words. A Lyndon word is defined to be a nonempty word $w \in \mathfrak A^\ast$ satisfying one of the following three equivalent assertions:

1. If $u$ and $v$ are any two nonempty words such that $w = uv$, then $v > w$.

2. If $u$ and $v$ are any two nonempty words such that $w = uv$, then $v > u$.

3. If $u$ and $v$ are any two nonempty words such that $w = uv$, then $vu > uv$.

Notice that the equivalence of these three assertions is not trivial; if we would restrict the assertions to a particular choice of $u$ and $v$, then they would cease to be equivalent.

For example, if $\mathfrak A = \mathbb N$ with the usual total order, then the words $4$, $223$, $04044$ and $0303304$ are Lyndon, while the words $\varnothing$, $10$, $11$ and $242$ are not.

Chen-Fox-Lyndon factorization. Lyndon words have a multitude of curious properties as well as applications to algebra (free groups, free Lie algebras, shuffle algebras, quasisymmetric functions etc.). Probably the most important result that is "behind" these applications is the Chen-Fox-Lyndon factorization theorem, which states that for every word $w \in \mathfrak A^\ast$, there exists a unique tuple $\left(a_1, a_2, \ldots, a_k\right)$ of Lyndon words satisfying $w = a_1 a_2 \cdots a_k$ and $a_1 \geq a_2 \geq \cdots \geq a_k$.

For instance, if $\mathfrak A = \mathbb N$ with the usual total order, for $w = 104029423402010110101$, this tuple is $\left(1, 04, 0294234, 02, 01011, 01, 01\right)$.

This factorization can be used as an alternative way to define Lyndon words. Indeed, assume that we are given some positive integer $N$, and we have defined the notion of Lyndon words of length $< N$. Then, we can define the notion of a Lyndon word of length $N$ as being a word of length $N$ for which there exists no tuple $\left(a_1, a_2, \ldots, a_k\right)$ of Lyndon words of length $< N$ satisfying $w = a_1 a_2 \cdots a_k$ and $a_1 \geq a_2 \geq \cdots \geq a_k$. This definition is implicit and impractical, and it does not help proving the uniqueness of the factorization, but I would not be surprised if it is how people actually discovered Lyndon words.

Necklaces. A necklace (also known as a circular word) means an equivalence class of words modulo cyclic rotation. A necklace of nonempty words is said to be aperiodic if the number of its representatives equals the length of each of its representatives. For instance, the necklaces $\overline{1213}$ and $\overline{24424}$ are aperiodic, while $\overline{1212}$ and $\overline{404040}$ are not. Here, $\overline{w}$ denotes the necklace containing a word $w$; so we have $\overline{1213} = \overline{2131} = \overline{1312} = \overline{3121} = \left\{ 1213, 2131, 1312, 3121 \right\}$. A known fact states that every aperiodic necklace contains precisely one representative which is a Lyndon word, whereas any non-aperiodic necklace contains no such representative. Thus, if the alphabet $\mathfrak A$ has finite cardinality $q$, then the number of Lyndon words of length $n$ (for fixed positive integer $n$) equals the number of aperiodic necklaces of $n$-letter words. This number is $\dfrac{1}{n} \sum\limits_{d\mid n} \mu\left(n/d\right) q^d$.

QUESTION.

Nyldon words. We can define the notion of Nyldon words by recalling our alternative definition of Lyndon words using Chen-Fox-Lyndon factorization, and replacing the condition $a_1 \geq a_2 \geq \cdots \geq a_k$ by $a_1 \leq a_2 \leq \cdots \leq a_k$. In more detail:

• There are no Nyldon words of length $< 1$.

• Assume that we are given some positive integer $N$, and we have defined the notion of Nyldon words of length $< N$. Then, we define the notion of a Nyldon word of length $N$ as being a word of length $N$ for which there exists no tuple $\left(a_1, a_2, \ldots, a_k\right)$ of Nyldon words of length $< N$ satisfying $w = a_1 a_2 \cdots a_k$ and $a_1 \leq a_2 \leq \cdots \leq a_k$.

Conjecture 1. For every word $w$, there exists a unique tuple $\left(a_1, a_2, \ldots, a_k\right)$ of Nyldon words satisfying $w = a_1 a_2 \cdots a_k$ and $a_1 \leq a_2 \leq \cdots \leq a_k$.

The existence part of this is obvious, but the uniqueness is interesting. I have checked it by computer for $\mathfrak A = \left\{0, 1\right\}$ and word length up to $18$.

Conjecture 2. Every aperiodic necklace contains precisely one representative which is a Nyldon word, whereas any non-aperiodic necklace contains no such representative.

This is checked for $\mathfrak A = \left\{0, 1\right\}$ and word length up to $15$.

Each of the Conjectures 1 and 2 would imply that the number of Nyldon words of given length over a given alphabet equals the number of Lyndon words of the same data. This is, in fact, equivalent to Conjecture 1 (because one can WLOG assume $\mathfrak A$ finite, and then argue using the fact that surjections between finite sets of equal size must be injections), so Conjecture 2 can be regarded as a stronger version of Conjecture 1.

EXPERIMENTAL DATA.

For $\mathfrak A = \left\{0, 1\right\}$, here are the Nyldon words of lengths up to $6$:

length $0$: none.

length $1$: the words $0$ and $1$. (For comparison: The Lyndon words are $0$ and $1$.)

length $2$: the word $10$. (For comparison: The Lyndon words are $01$.)

length $3$: the words $100$ and $101$. (For comparison: The Lyndon words are $001$ and $011$.)

length $4$: the words $1000$, $1001$ and $1011$. (For comparison: The Lyndon words are $0001$, $0011$ and $0111$.)

length $5$: the words $10000$, $10001$, $10010$, $10011$, $10110$ and $10111$. (For comparison: The Lyndon words are $00001$, $00011$, $00101$, $00111$, $01011$ and $01111$.)

length $6$: the words $100000$, $100001$, $100010$, $100011$, $100110$, $100111$, $101100$, $101110$ and $101111$. (For comparison: The Lyndon words are $000001$, $000011$, $000101$, $000111$, $001011$, $001101$, $001111$, $010111$ and $011111$.)

Answer 1

My co-authors (Émilie Charlier, Manon Philibert) and I give positive answers to Grinberg's conjectures in the paper E. Charlier, M. Philibert, M. Stipulanti, Nyldon words. So it is true that there are equally many Nyldon words and Lyndon words of a given length. In addition, we show that the set of Nyldon words is a Hall set (more precisely, we prove that it is a Lazard factorization, but the notions are equivalent). In this paper, we also compare Lyndon and Nyldon words regarding different properties such as standard and Širšov factorizations, circular and comma-free codes, and Lazard factorizations. We also leave in the paper open questions for future work. I hope you will enjoy it!

Answer 2

It seems, experimentally, that the set of nyldon words is a Hall set, with the same construction of the basis as for Lyndon words, that is if $w=uv$ where $w,u,v$ are nyldon words and $|v|$ is maximal, then $\pi(w)= \pi(u) \pi(v)$ (note that, by definition, we have $u>_{lex} v$). To show that this mapping gives a Hall set, it suffice to show (I think, I am not an expert on Hall set...) that (1) $w>_{lex}v$, (2) $u>_{lex}v$ and (3) if $u$ is not a single letter then $y\le_{lex} v$, where $u=xy$, $x,y$ are nyldon words and $|y|$ maximal. (2) is true by definition, so (1) is true. Maybe we can show (3) using the maximality of $|v|$...

Moreover, it seems that we have the same properties for other total orderings on words: "shortlex" (i.e. $u<v$ if $|u|<|v|$, or $|u|=|v|$ and $u<_{lex} v$) and (say) "shortrevlex" (i.e. $u<v$ if $|u|<|v|$, or $|u|=|v|$ and $u>_{lex} v$).

More strangely, Conjecture 1 and 2 seem true also for "longlex" ($u<v$ if $|u|>|v|$, or $|u|=|v|$ and $u<_{lex} v$) and "longrevlex" ($u<v$ if $|u|>|v|$, or $|u|=|v|$ and $u>_{lex} v$), but the mapping $\pi(w)= \pi(u) \pi(v)$ with $w=uv$ and $|v|$ maximal do not gives a Hall set... (And neiter if $|v|$ is minimal instead of maximal.)

edit:

I quickly look in "Algebres de Lie Libres et Monoides Libres" from Viennot, and some things are more clear now.

Nyldon words seem to be a Lazard right factorization. I.e. the following procedure seems to give all Nyldon words of size at most n:

$Y_0 := \{0,1\}$ and $i:=0$

While $Y_i$ has words of size at most n :

• $u_{i+1}$ = $\min_{lex} \{ y : y \in Y_i \text{ s.t } | y | <= n\}$

• $Y_{i+1}$ = $( Y_i \setminus \{ u_{i+1}\} ) u_i^*$

• $i:=i+1$

Eg for $n=4$ $Y_0 : \{0, 1\}$, $u_1 : 0 $, $Y_1 : \{1, 10, 100, 1000, ...\}$, $u_2 : 1 $, $Y_2 : \{10, 100, 1000, 1001, 101, 1011, ...\}$, $u_3 : 10 $, $Y_3 : \{100, 1000, 1001, 101, 1011, ...\}$, $u_4 : 100 $, $Y_4 : \{1000, 1001, 101, 1011, ...\}$, $u_5 : 1000 $, $Y_5 : \{1001, 101, 1011, ...\}$, $u_6 : 1001 $, $Y_6 : \{101, 1011, ...\}$, $u_7 : 101 $, $Y_7 : \{1011, ...\}$, $u_8 : 1011$

(where ... represents words of size >n)

This is not the usual Lazard (left) factorization definition, but it is if we take the mirror.

(Note: Lyndon words are left and right Lazard factorizations, thus are called "regular factorization" in [Viennot]. Nyldon words are not a left Lazard factorization, so I think it is difficult to find direct correspondence between Lyndon and Nyldon words...)

Let $U_n$ be the output (the set of all $u_i$) of the procedure with a fixed n, and $U=\cup_{n\in N} U_n$. It is known that $U$ is a factorization, since it is a Lazard elimination procedure, thus Conjectures 1 and 2 are true for the set $U$.

Now it suffice to show that $U$ are exactly Nyldon words, thus U_n are Nyldon words of size <=n. Maybe we can follow the following way. (Note that the procedure gives the set U_n in the lexicographic order.)

• For every proper suffix s of $u_i$, $s \cap Y_i = \emptyset$

• For every proper suffix s of $u_i$, $s \cap Y_i^* = \emptyset$

• For every $w\in U$ and s suffix of w, if $s\in U$ then $s<_{lex} w$

• By induction, $U_n$ is a set of Nyldon words.

Answer 3

New attempt after my comment to the OP (but this one is too long for a comment):
EDITED after comments from user38477.

Let $r,s,t$ be non empty words such that $tst$ is Nyldon, $tstr$ is not Nyldon, and $r<_{lex}tst$. Then call $\ tst.tst.r$ an S-word. e.g. t=10, s=0, r=0 yield $10010100100$. Are there square-initial Nyldon words not fitting this pattern?

Assume wlog $\mathfrak A=\{1,...,k\}$ and let $w$ be a word on $\mathfrak A$ that doesn't start with $k$, i.e. $w<_{lex}k$. Then $kwkkwkw$ (compare with @IlyaBogdanov's $1011010$!) is Nyldon, and I think I can show that all square-initial Nyldon words (i.e. those starting with a square) are of this form. Call those S-words. Note that $w$ can contain $k$'s at non-ínitial places, those do not give any trouble.

The new conjecture would be:

For a given necklace, its Nyldon representative (exists and) is the biggest shift in alphabetical order, excluding all the square-initial shifts that are not S-words.