# Automata and Arithmetics in Canonical Number Systems
## 1 Introduction  
In their first appearance, canonical number systems (CNSs) were natural generalizations of the positional numeral systems of rational integers to algebraic integers. [PERSON], in his famous book [1] (Ch. 4), studied the history of the radix representation of integers. He described various canonical number systems, and he proved that the complex number \(-1+i\) is a possible base of the number system representing Gaussian integers. His result was further generalized by [PERSON] and [PERSON]. In [2], they proved the existence of other bases, but still in the set of Gaussian integers. Later, [PERSON] and [PERSON] in [3], [PERSON] in [4], and [PERSON] and [PERSON] in [5] and [6] extended the concept of canonical number systems for the ring of algebraic integers and they proved their existence in some particular cases. In [7], [PERSON] first used the notion, and [PERSON] and [PERSON] in [8] continued the development of results of CNSs over polynomials. [PERSON] and [PERSON] in [9] dealt with canonical number systems over Euclidean domains. In [4], a simple condition is given for the construction of CNSs, but in general, they are not easy to find. [PERSON] [10] presented a complete description of binary canonical number systems of degrees not greater than 8. Later, [PERSON] and [PERSON] [11] extended the results for CNSs of degrees 9, 10, and 11. The arithmetic in a canonical number system is similar to that of rational integers within the classical digit representation. However, calculating the digits requires a more complex reduction operation. [PERSON], [PERSON], and [PERSON] in [12] introduced the concept of counting automata (increasing by 1) for Gaussian integers, which was generalized to quadratic number fields by [PERSON] [13]. [PERSON], [PERSON], and [PERSON] in [14] proved the existence of addition and multiplication by a constant in algebraic number fields. [PERSON] and [PERSON] in [15] introduced a fractal approach for the detailed analysis of counting automata. Transducers were extensively studied by [PERSON] in Automata, Languages and Machines [16], and further developed by [PERSON] and [PERSON] in Semirings, Automata, Languages [17]. In the present paper, we prove that for every CNS polynomial, an automaton can be constructed to perform digit-wise addition (Theorem 5). This relies on several assertions, which are detailed in Section 2. We implement a program for the calculation of addition automata in binary CNSs and summarize our experiments in Section 4. The rest of the paper is organized as follows. In Section 2, we introduce the concepts and key results related to canonical number systems. We also define a useful measure for the information quantity of a polynomial and outline its fundamental properties. One of the main results of the section is Theorem 3, which establishes a general bound on geometric sums of complex numbers \(\alpha\) with modulus greater than \(1\), under the condition that \(\alpha\) is not a positive real number. The proof of this statement requires some further lemmas concerning the behavior of geometric sums, which we address in the subsequent paragraphs. Using these lemmas, we present an algorithm, which is designed to calculate a reasonably small constant appearing in Theorem 3. In the last part of the section, we prove Theorem 4, which discusses the relationship between the length of a polynomial \(A\) in canonical representation and the information quantity of \(A\). The constants referenced in this theorem are derived using Theorem 3, and thus can be calculated by an algorithm explained after the theorem. In Section 3, we define the concept of finite transducer automata. In Theorem 5, we show that for every canonical number system, there exists a transducer automaton executing the addition operation for polynomials in canonical representation. The proof is constructive, and the automaton produced is minimal (Theorem 6).