Lie complexity of words

Abstract

Given a finite alphabet $\hat{I}\pounds$ and a right-infinite word $\mathbf{w}$ over $\hat{I}\pounds$, we define the Lie complexity function $L_{\mathbf{w}}:\mathbb{N}\to \mathbb{N}$, whose value at $n$ is the number of conjugacy classes (under cyclic shift) of length-$n$ factors $x$ of $\mathbf{w}$ with the property that every element of the conjugacy class appears in $\mathbf{w}$. We show that the Lie complexity function is uniformly bounded for words with linear factor complexity, and as a result we show that words of linear factor complexity have at most finitely many primitive factors $y$ with the property that $y^n$ is again a factor for every $n$. We then look at automatic sequences and show that the Lie complexity function of a $k$-automatic sequence is again $k$-automatic.

13 pages