The carry propagation of the successor function (Q2197902)

Given a numeration system defined by a language \(L\), the \emph{carry propagation} occurs at a nonnegative integer \(N\) if the number of digits representing \(N\) is different from that representing \(N+1\). More precisely, the carry propagation \(cp_L(i)\) at position \(i\) is defined by \[ cp_L(i)=\Delta(\langle i\rangle_L, \langle i+1\rangle_L), \] where \(\langle i\rangle_L\in L\) denotes the digit representation of an integer \(i\), and for two words \(u=u_1\ldots u_k, v=v_1\ldots v_\ell\in L\) we set \[ \Delta(u,v)=\left\{\begin{array} {lll} \max\{k, \ell\}&\textrm{if}& k\ne \ell,\\ k-\max\{i\ge 0: u_1\ldots u_i=v_1\ldots v_i\}&\textrm{if}& k=\ell. \end{array}\right. \] Then the \emph{amortized carry propagation} \(CP_L\) of \(L\) is defined by \[ CP_L=\lim_{N\to\infty}\frac{1}{N}\sum_{i=0}^{N-1}cp_L(i), \] assuming the limit exists. Furthermore, if \(CP_L\) exists, then it can be explicitly calculated: \[ CP_L=\frac{\gamma_L}{\gamma_L-1}, \] where \(\gamma_L=\lim_{\ell\to\infty}\mathbf u_L(\ell+1)/\mathbf u_L(\ell)\) is the local growth rate of \(L\). Here \(\mathbf u_L(\ell)\) is the number of all length-\(\ell\) words of \(L\). The main results of this paper provides three different types of sufficient conditions to guarantee the existence of \(CP_L\) by using combinatorial, algebraic and ergodic methods, respectively. Firstly, the combinatorial method shows that \(CP_L\) exists if the language \(L\) is prefix-closed and right extendable, and has an eventually periodic signature. It has application in rational base numeration systems. Secondly, the algebraic method considers the generating function of \((\mathbf u_L(\ell))\), and shows that \(CP_L\) exists if the local growth rate of \(w^{-1}L=\{v: wv\in L\}\) exists for every \(w\in L\). It has applications in those numeration systems with the language generated by an automaton. Finally, the ergodic theory method extends the language \(L\) to a dynamical system \((\mathcal K_L,\tau_L)\). As applications in greedy numeration systems with \(G=(G_\ell)_{\ell\ge 0}\) they show that \(CP_G\) exists if \((K_G, \tau_G)\) is uniquely ergodic and the summation \(\sum_{k=0}^\infty\frac{k}{G_k}\) is bounded. The proofs in the paper are more self-contained. Furthermore, the paper contains many literature on carry propagation in numeration systems. It is an important and valuable reference paper in this field.