# Automata and Arithmetics in Canonical Number Systems
## 2 Definitions and Results Related to Canonical Number Systems
Similarly, as before, if we set \(B(x)=x^{7}+x^{6}+2x^{5}+x+1\), then \(B(\alpha)=16\)._  
_The above example illustrates how numbers in this algebraic number system can be expressed as polynomials, extending the classical notion of number systems into the realm of algebraic integers._  
[PERSON] in [7] and later [PERSON] et al. [18] have stated a necessary condition for CNS polynomials. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Iter.** & **N** & **q** & **s** & **r** \\ \hline
1 & 16 & 5 & \(-5x-5\) & 1 \\ \hline
2 & \(-5x-5\) & \(-2\) & \(2x-3\) & 1 \\ \hline
3 & \(2x-3\) & \(-1\) & \(x+3\) & 0 \\ \hline
4 & \(x+3\) & 1 & \(-x\) & 0 \\ \hline
5 & \(-x\) & 0 & \(-1\) & 0 \\ \hline
6 & \(-1\) & -1 & \(x+1\) & 2 \\ \hline
7 & \(x+1\) & 0 & 1 & 1 \\ \hline
8 & 1 & 0 & 0 & 1 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: steps for decomposing the number \(16\) in the number system \((x^{2}+x+3,\{0,1,2\})\). **Theorem 2**. : _If \(P(x)\) is a CNS polynomial, then all roots of \(P(x)\) lie outside the closed unit circle and all real roots of \(P(x)\) are less than \(-1\)._  
Now, we define the information quantity of a polynomial. Later, at the end of this section, we will show the relation between the information quantity and the length of the canonical representation of a polynomial in Theorem 4. In Section 3, we will use this definition in Theorem 5 for the proof of the existence of addition automata in canonical number systems. **Definition 2**. : _Let \(P(x)\) be a CNS polynomial of degree \(d\), \(\alpha_{1},\ldots,\alpha_{d}\) be the (not necessarily different) roots of \(P\), and let \(A(x)\in\mathbb{Z}[x]\). We define the relative information quantity of \(A\) as_  
\[\mathbb{I}(A)=\mathbb{I}_{P}(A)=\max_{ \begin{subarray}{c}1\leq i\leq d\\ A(\alpha_{i})\
eq 0\end{subarray} }\frac{\log|A(\alpha_{i})|}{\log|\alpha_{i}|}\.\]  
_In the special case of \(A\) is divisible by \(P\), we set \(\mathbb{I}(A)=0\)._  
**Example 4**. : _Let \(P(x)=x^{4}+2\). In the paper of \(A\). [PERSON] [10], it is proven that \(P\) is a CNS polynomial. The roots of \(P\) are_  
\[\frac{2^{\frac{3}{4}}}{2}+I\frac{2^{\frac{3}{4}}}{2},\ \frac{2^{\frac{3}{4}}}{2}-I \frac{2^{\frac{3}{4}}}{2},\ -\frac{2^{\frac{3}{4}}}{2}-I\frac{2^{\frac{3}{4}}}{2},\ -\frac{2^{\frac{3}{4}}}{2}+I\frac{2^{ \frac{3}{4}}}{2}\,\]  
_where \(I\) is the imaginary unit. The modulus of the roots are identical and equal to \(\left|\frac{2^{\frac{3}{4}}}{2}+I\frac{2^{\frac{3}{4}}}{2}\right|=2^{\frac{1}{ 4}}\)._  
_Based on the properties of the logarithm, any base of the logarithm provides the same value for the relative information quantity; thus, for the sake of simplicity, let \(\log\) be the base-\(2\) logarithm. Then, \(\log\left|\frac{2^{\frac{3}{4}}}{2}+I\frac{2^{\frac{3}{4}}}{2}\right|=\frac{1 }{4}\) (and the same is true for all the roots)._  
1. _Let_ \(A(x)=x^{3}+x+1\)_. Substituting the four roots to_ \(A\) _and calculating the base-_\(2\) _logarithm of the absolute value of_ \(A(\alpha)\)_, according to the order of the roots, we obtain the approximate values_ \[1.0923,1.0923,1.2851,1.2851\.\] _Then, we obtain_ \[\mathbb{I}(A)=\frac{1.2851}{1/4}\approx 5.1406\.\] 2. _Let_ \(A(x)=x^{4}+x+1\)_. As before, execute the same operations. We obtain the logarithms of the absolute values of the substituted roots as_ \[-0.2246,-0.2246,1.0171,1.0171\,\] _whence_ \[\mathbb{I}(A)=\frac{1.0171}{1/4}\approx 4.0684\.\] 3. _Let_ \(A(x)=x^{5}+x+1\)_. Then, one can see that for_ \(\mathbb{I}(A)\)_, we obtain get exactly the same value as in case (b)._ _The equality of case (b) and (c) can be seen if we notice that if_ \(\alpha\) _is one of the roots of_ \(P\)_, then_ \(\alpha^{4}=-2\)_, whence in case (b),_ \(A(\alpha)=\alpha-1\)_, while in case (c)_ \(A(\alpha)=-2\cdot\alpha+\alpha-1=-\alpha+1\)_._  
**Lemma 1**. : _Let \(P(x)\) be a CNS polynomial and \(A(x),B(x)\in\mathbb{Z}[x]\). Then,_\(