Affine factor complexity of infinite words associated with simple Parry numbers

Zuzana Masáková Czech Technical University, Prag, Czech Republic

Coauthor(s): Julien Bernat and Edita Pelantová

We consider the factor complexity of a fixed point of a primitive substitution canonically defined by a $\beta$-numeration system. Let $\beta$ be a simple Parry number, i.e. such that its Rényi expansion of $1$ is finite, $d_\beta(1)=t_1\cdots t_m$. The canonical substitution corresponding to $\beta$ is a substitution $\varphi_\beta$ over the alphabet $\mathcal{A}=\{0,1,\dots,m-1\}$, given by

$$\varphi_{\beta}(j)=0^{t_{j+1}}(j+1) , \hbox{ for }j=0,\dots,m-2,\qquad \varphi_\beta(m-1)=0^{t_m} .$$

Such a substitution is primitive and admits a unique fixed point, namely the infinite word

$$u_\beta:=\lim_{n\to\infty}\varphi_\beta^n(0) .$$

The factor complexity of the infinite word $u_\beta$ is known for example if $t_1=t_2=\cdots = t_{m-1}$ and $t_m=1$. In this case, $u_\beta$ is an Arnoux-Rauzy word of order $m$, which means that $u_\beta$ has exactly one left and one right special factor of every length with $m$ left (right) extensions, and its complexity function is $\mathcal{C}(n)=(m-1)n+1$, for all $n\in\mathbb{N}$.

The structure of left special factors is however not that simple for general $d_\beta(1)=t_1\cdots t_m$ and also the complexity has been described sofar only partially.

In this presentation we characterize the substitutions $\varphi_\beta$, for which the fixed point $u_\beta$ has affine factor complexity, that is, such that $\mathcal{C}(n)=an+b$ for any $n\in\mathbb{N}$. We prove the following theorem.

Theorem. Let $\beta$ be a simple Parry number with the Rényi expansion of unity $d_\beta(1)=t_1\cdots t_m$, and let $u_\beta$ be the fixed point of the substitution $\varphi_\beta$. Then the factor complexity of $u_\beta$ is an affine function if and only if the coefficients $t_1,\dots,t_m$ satisfy

1)

$t_m=1$

2)

If there exists a non-empty word $w$ and $\alpha\in\mathbb{Q}$ such that $t_1\cdots t_{m-1}=w^\alpha$, then $\alpha\in\mathbb{N}$.

Let us mention that condition 2) of the above theorem means that either $t_1\cdots t_{m-1}$ is equal to $w^k$ for $k\in\mathbb{N}$, $k\geq 2$, or no word can be both a proper prefix and a proper suffix of $t_1\cdots t_{m-1}$.

In order to prove that conditions $1)$ and $2)$ of the Theorem are sufficient for affine factor complexity, we use purely the tools of combinatorics on words. For the opposite implication, we use the geometric representation of the factors of the word $u_\beta$ as coding of patterns occurring in the set of $\beta$-integers.