Lyndon basis

Remarks

Example: let $A = \set{a, b}$ with $a < b$. The Lyndon words of length at most $3$ are $a$, $b$, $ab$, $aab$ and $abb$. For $aab$, the proper suffixes $ab$ and $b$ are both larger than $aab$, and the longest Lyndon suffix is $ab$, so $P_{aab} = [a, [a, b]]$. For $abb$, the suffix $bb$ is not a Lyndon word, so the standard factorization is $ab \cdot b$ and $P_{abb} = [[a, b], b]$.

Non-example: $abab$ is not a Lyndon word, since its suffix $ab$ is a proper prefix and hence smaller than $abab$.

If $A$ has $q$ elements, the number of Lyndon words of length $n$ is $$\frac{1}{n} \sum_{d \mid n} \mu(d)\, q^{n/d},$$ where $\mu$ is the Möbius function. By the basis theorem, this is also the dimension of the homogeneous component of degree $n$ of $L(A)$, which is Witt's formula. An equivalent definition: a nonempty word is a Lyndon word if and only if it is strictly smaller than all its nontrivial cyclic rotations.