On formal inverse of the Prouhet-Thue-Morse sequence

Abstract

Let $p$ be a prime number and consider a $p$-automatic sequence $\mathbf{u}=(u_n{)}_{n\in \mathbb{N}}$ and its generating function $U(X)={\sum }_{n=0}^{\infty }{u}_n{X}^n\in {\mathbb{F}}_p[[X]]$. Moreover, let us suppose that $u_0=0$ and $u_1\ne 0$ and consider the formal power series $V\in {\mathbb{F}}_p[[X]]$ which is a compositional inverse of $U(X)$, i.e., $U(V(X))=V(U(X))=X$. In this note we initiate the study of arithmetic properties of the sequence of coefficients of the power series $V(X)$. We are mainly interested in the case when $u_n=t_n$, where $t_n=s_2(n)(\mathrm{mod}2)$ and $\mathbf{t}=(t_n{)}_{n\in \mathbb{N}}$ is the Prouhet-Thue-Morse sequence defined on the two letter alphabet $\{0,1\}$. More precisely, we study the sequence $\mathbf{c}=(c_n{)}_{n\in \mathbb{N}}$ which is the sequence of coefficients of the compositional inverse of the generating function of the sequence $\mathbf{t}$. This sequence is clearly 2-automatic. We describe the sequence $\mathbf{a}$ characterizing solutions of the equation $c_n=1$. In particular, we prove that the sequence $\mathbf{a}$ is 2-regular. We also prove that an increasing sequence characterizing solutions of the equation $c_n=0$ is not $k$-regular for any $k$. Moreover, we present a result concerning some density properties of a sequence related to $\mathbf{a}$.

16 pages; revised version will appear in Discrete Mathematics