# Automata and Arithmetics in Canonical Number Systems
## 2 Definitions and Results Related to Canonical Number Systems
\begin{array}{ll}\text{(i)}&0\leq\mathbb{I}(A)\text{;}\\ \text{(ii)}&\text{If }\varphi(A)=\varphi(B)\text{, then }\mathbb{I}(A)=\mathbb{I}(B) \text{;}\\ \text{(iii)}&\mathbb{I}(A+B)\leq\max\{\mathbb{I}(A),\mathbb{I}(B)\}+\mathbb{I}(2 )\text{;}\\ \text{(iv)}&\mathbb{I}(A\cdot B)\leq\mathbb{I}(A)+\mathbb{I}(B)\text{;}\\ \text{(v)}&\mathbb{I}(x\cdot A)=\mathbb{I}(A)+1\text{;}\\ \text{(vi)}&\mathbb{I}(A^{n})=n\mathbb{I}(A)\text{.}\end{array} \)  
Proof. : (i) Let \(P^{\prime}\) be an irreducible divisor of \(P\) of degree \(d^{\prime}\), and for the sake of simplicity, assume that \(\alpha_{1},\dots,\alpha_{d^{\prime}}\) are the roots of \(P^{\prime}\). Assume that \(A\) is not divisible by \(P^{\prime}\). Since \(P\) is a CNS polynomial, by Theorem 2, \(|\alpha|>1\) for any root of \(P\) and hence for any root of \(P^{\prime}\) as well. \(P^{\prime}\) is irreducible and does not divide \(A\), thus the roots of \(P^{\prime}\) are not roots of \(A\), whence \(A(\alpha_{i})\
eq 0\) for all \(i=1,\dots,d^{\prime}\). By definition \(P\in\mathbb{Z}[x]\), consequently, \(P^{\prime}\in\mathbb{Z}[x]\), whence \(\alpha_{1},\dots,\alpha_{d^{\prime}}\) are algebraic integers. Since \(A\in\mathbb{Z}[x]\), the values \(A(\alpha_{1}),\dots,A(\alpha_{d^{\prime}})\) are algebraic integers as well. The roots \(\alpha_{1},\dots,\alpha_{d^{\prime}}\) form a complete set of algebraic conjugates over \(\mathbb{Q}\), which means that the set \(A(\alpha_{1}),\dots,A(\alpha_{d^{\prime}})\) is also a complete set of algebraic conjugates over \(\mathbb{Q}\) with each value appearing in the same number. This implies that  
\[\prod_{1\leq i\leq d^{\prime}}A(\alpha_{i})\in\mathbb{Q}\text{.} \tag{1}\]  
The product of algebraic integers is an algebraic integer, hence, together with Equation (1),  
\[0\
eq\prod_{1\leq i\leq d^{\prime}}A(\alpha_{i})\]  
is a rational integer. If \(|A(\alpha_{i})|<1\) for all \(1\leq i\leq d^{\prime}\), then  
\[1>\prod_{1\leq i\leq d^{\prime}}|A(\alpha_{i})|\text{,}\]  
which is a contradiction, whence at least one of the roots \(\alpha\) of \(P^{\prime}\) is such that \(|A(\alpha)|\geq 1\). For this \(\alpha\), we have  
\[0\leq\frac{\log|A(\alpha)|}{\log|\alpha|}\text{,}\]  
whence by definition \(0\leq\mathbb{I}(A)\). (ii) If \(\varphi(A)=\varphi(B)\), then \(A(x)\equiv B(x)\mod P(x)\), i.e., \(A(x)=Q(x)P(x)+B(x)\) with some \(Q\in\mathbb{Z}[x]\). This yields that \(A(\alpha)=B(\alpha)\) for any root of \(P\), which implies \(\mathbb{I}(A)=\mathbb{I}(B)\). (iii) Let \(\alpha\) be a root of \(P\). In the general case, when we do not assume that \(\varphi(A)=\varphi(B)\), we cannot state \(A(\alpha)=B(\alpha)\). For the sake of simplicity, assume that \(|A(\alpha)|\geq|B(\alpha)|\). Then, \(\log(|A(\alpha)+B(\alpha)|)\leq\log(|A(\alpha)|+|B(\alpha)|)\leq\log(2|A( \alpha)|)=\log(2)+\log(|A(\alpha)|)\), which implies the statement. (iv)-(vi) These statements can be proven by similar arguments using the additive property of the logarithm. Theorem 3.3: _Let \(\alpha\in\mathbb{C}\) with \(1<|\alpha|\), and assume that \(\alpha\) is not a positive real number. Then, there exists a constant \(c<1\) depending only on \(\alpha\) such that for every \(0<N\in\mathbb{Z}\), and for any sequence \(a_{0},a_{1},\dots\) of integers satisfying \(0\leq a_{i}\leq N\) for all \(i=0,1,\dots\), we have_\[\left|\sum_{i=0}^{k-1}a_{i}a^{i}\right|\leq cN\frac{|\alpha|^{k}}{|\alpha|-1}\, \tag{2}\]  
for any \(1<k\in\mathbb{Z}\). **Remark 4**. : _In Theorem 3, we assume that \(2\leq k\), thus a natural lower bound on \(c\) can be obtained from inequality (2) if we set \(k=2\). Then, we have_  
\[|\alpha+1|\leq c\frac{|\alpha|^{2}}{|\alpha|-1}\,\]  
_which implies_  
\[|\alpha+1|\frac{|\alpha|-1}{|\alpha|^{2}}\leq c\.\]  
_To present this lower bound in a more expressive form, we multiply the left-hand side by \(\frac{|\alpha|+1}{|\alpha|+1}\).