Generalized de Bruijn words for Primitive words and Powers

Abstract

We show that for every $n\ge 1$ and over any finite alphabet, there is a word whose circular factors of length $n$ have a one-to-one correspondence with the set of primitive words. In particular, we prove that such a word can be obtained by a greedy algorithm, or by concatenating all Lyndon words of length $n$ in increasing lexicographic order. We also look into connections between de Bruijn graphs of primitive words and Lyndon graphs. Finally, we also show that the shortest word that contains every $p$-power of length $pn$ over a $k$-letter alphabet has length between $p{k}^n$ and roughly $(p+\frac{1}{k})k^n$, for all integers $p\ge 1$. An algorithm that generates a word which achieves the upper bound is provided.

arXiv commentRevisions made for publication