Acta Polytechnica doi:10.14311/AP.2018.58.0285 Acta Polytechnica 58(5):285–291, 2018 © Czech Technical University in Prague, 2018 available online at http://ojs.cvut.cz/ojs/index.php/ap MINIMAL NON-INTEGER ALPHABETS ALLOWING PARALLEL ADDITION Jan Legerskýa, b a Research Institute for Symbolic Computation, Johannes Kepler University Altenbergerstraße 69, A-4040 Linz, Austria b Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague Trojanova 13, 120 00 Praha 2, Czech Republic correspondence: jan.legersky@risc.jku.at Abstract. Parallel addition, i.e., addition with limited carry propagation has been so far studied for complex bases and integer alphabets. We focus on alphabets consisting of integer combinations of powers of the base. We give necessary conditions on the alphabet allowing parallel addition. Under certain assumptions, we prove the same lower bound on the size of the generalized alphabet that is known for alphabets consisting of consecutive integers. We also extend the characterization of bases allowing parallel addition to numeration systems with non-integer alphabets. Keywords: numeration system, parallel addition, minimal alphabet. 1. Introduction The concept of parallel addition in a numeration sys- tem with a base β and alphabet A was introduced by A. Avizienis [1]. The crucial difference from standard addition is that carry propagation is limited and hence an output digit depends only on bounded number of input digits. Therefore, the whole operation can run in constant time in parallel. It is known that the alphabet A must be redun- dant [2], otherwise parallel addition is not possible. Necessary conditions on the base and alphabet were fur- ther studied by C. Frougny, P. Heller, E. Pelantová, and M. Svobodová [3–5] under assumption that the alphabet A consists of consecutive integers containing 0. It was shown that there exists an integer alphabet allowing parallel addition if and only if the base is an algebraic number with no conjugates of modulus 1. Lower bounds on the size of the alphabet were given. The main result of this paper is generalization of these results to non-integer alphabets, namely A⊂ Z[β]. Such alphabets might have elements smaller in modulus comparing to integer ones. This is useful for instance in online multiplication and division [6]. Parallel addition algorithms that use non-integer alphabets are discussed in [7]. The paper [8] discusses consequences of parallel addition for eventually periodic representations in Q(β). This paper is organized as follows: in Section 2, we recall the necessary definitions and show that for parallel addition we can consider only bases being algebraic numbers. In Section 3, we prove that if (β,A) allows parallel addition and β′ is a conjugate of β, then there is an alphabet A′ such that (β′,A′) allows parallel addition. If A[β] = Z[β], we show that A must contain all representatives modulo β and β − 1. If β is an algebraic integer, a consequence is the same lower bound on the size of A⊂ Z[β] as for integer alphabets. The assumption A[β] = Z[β] or existence of parallel addition without anticipation implies that β is expanding, i.e., all its conjugates are greater than one in modulus. The key result from [3] is generalized to A⊂ Z[β] in Section 4. Namely, there is an alphabet in Z[β] allowing so-called k-block parallel addition if and only if β is an algebraic number with no conjugates of modulus one. 2. Preliminaries The concept of positional numeration systems with integer bases and digits is very old and can be easily generalized: Definition 2.1. If β ∈ C is such that |β| > 1 and A⊂ C is a finite set containing 0, then the pair (β,A) is called a numeration system with a base β and digit set A, usually called an alphabet. Numbers in a numeration system (β,A) are rep- resented in the following way: let x be a complex number and xn,xn−1,xn−2, . . . ∈ A,n ≥ 0. We say that ω0xnxn−1 · · ·x1x0 •x−1x−2 · · · is a (β,A)- representation of x if x = ∑n j=−∞xjβ j, where ω0 denotes the left-infinite sequence of zeros. The set of all numbers which have a (β,A)- representation with only finitely many non-zero digits is denoted by FinA(β) := { n∑ j=−m xjβ j : n,m ∈ N,xj ∈A } . The set of all numbers with a finite (β,A)-representation with only non-negative powers of β is denoted by A[β] := { n∑ j=0 xjβ j : n ∈ N,xj ∈A } . We remark that the definition of A[β] is analogous to the one of Z[β], i.e. the smallest ring containing Z 285 http://dx.doi.org/10.14311/AP.2018.58.0285 http://ojs.cvut.cz/ojs/index.php/ap Jan Legerský Acta Polytechnica and β, which is equivalent to the set of all sums of powers of β with integer coefficients. Now we show that whenever we require the alphabet to be finite and the sum of two numbers with finite (β,A)-representations to have again a finite (β,A)- representation (which is the case of parallel addition), then we can consider only bases which are algebraic numbers. Lemma 2.2. Let β be a complex number such that |β| > 1 and A⊂ Z[β] be a finite alphabet with 0 ∈A and 1 ∈ FinA(β). If N ⊂ FinA(β), then β is an algebraic number. Proof. Since A⊂ Z[β], all digits can be expressed as finite integer combinations of powers of β. Let d be the maximal exponent of β occurring in these expressions and C be the maximal absolute value of the integer coefficients of all digits in A. Hence, for every N ∈ N, there exist m,n ∈ N and a−m, . . . ,an ∈A, where ai = ∑d j=0 αijβ j with αij ∈ Z and |αij| ≤ C, such that N = n∑ i=−m aiβ i = n∑ i=−m d∑ j=0 αijβ i+j. Suppose for contradiction that β is transcendental. Therefore, the corresponding integer coefficients of pow- ers of β on the left hand side and on the right hand side must be equal, particularly∑ i+j=0 0≤j≤d,−m≤i≤n αij = N. This is a contradiction, since the left hand side is bounded by (d + 1) ·C, whereas N can be arbitrarily large. Corollary 2.3. Let β be a complex number such that |β| > 1 and let A ⊂ Z[β] be a finite alphabet with 0 ∈ A and 1 ∈ FinA(β), resp. 1 ∈ A[β]. If the set FinA(β), resp. A[β], is closed under addition, then β is an algebraic number. Proof. The closedness of FinA(β) under addition and 1 ∈ FinA(β) implies N ⊂ FinA(β). If A[β] is closed under addition and 1 ∈ A[β] ⊂ FinA(β), then N ⊂ A[β] ⊂ FinA(β). In both cases, Lemma 2.2 applies. The concept of parallelism for operations on repre- sentations is formalized by the following definition. Definition 2.4. Let A and B be alphabets. A function ϕ : BZ →AZ is said to be p-local if there exist r,t ∈ N satisfying p = r + t + 1 and a function φ : Bp → A such that, for any w = (wj)j∈Z ∈BZ and its image z = ϕ(w) = (zj)j∈Z ∈AZ, we have zj = φ(wj+t, · · · ,wj−r) for every j ∈ Z. The parameter t, resp. r, is called anticipation, resp. memory. In other words, every digit can by determined from only limited number of neighboring input digits. Since a (β,A + A)-representation of sum of two numbers can be easily obtained by digit-wise addition, the crucial part of parallel addition is conversion from the alphabet A + A to A. Definition 2.5. Let β be a base and let A and B be alphabets containing 0. A function ϕ : BZ →AZ such that (1.) for any w = (wj)j∈Z ∈ BZ with finitely many non-zero digits, z = ϕ(w) = (zj)j∈Z ∈AZ has only finite number of non-zero digits, and (2.) ∑ j∈Z wjβ j = ∑ j∈Z zjβ j, is called a digit set conversion in the base β from B to A. Such a conversion ϕ is said to be computable in parallel if ϕ is a p-local function for some p ∈ N. Parallel addition in a numeration system (β,A) is a digit set conversion in the base β from A + A to A, which is computable in parallel. 3. Necessary conditions on alphabets allowing parallel addition in A⊂ Z[β] Through this section, we assume that the base β is an algebraic number and the alphabet A is a finite subset of Z[β] such that {0} ( A. The finiteness of the alphabet is a natural assumption for a practical numeration system, whereas the requirement that β is an algebraic number is justified by Corollary 2.3. We recall that for an algebraic number β, if α,γ,δ are elements of Z[β], then γ is congruent to δ modulo α in Z[β], denoted by γ ≡α δ, if there exists ε ∈ Z[β] such that γ − δ = αε. In this section, we recall the known results on neces- sary properties of integer alphabets allowing parallel addition, and we extend them to non-integer alphabets. In [4], the following statement is proven: Theorem 3.1. Let (β,A) be a numeration system such that A⊂ Z[β]. If there exists a p-local parallel addition in (β,A) defined by a function φ : (A+A)p →A, then φ(b, . . . ,b) ≡β−1 b for any b ∈A + A. The same paper explain that, when considering only integer alphabets A⊂ Z from the perspective of par- allel addition algorithms, all the numbers β, 1/β, and their algebraic conjugates behave analogously: parallel addition algorithms exist either for all, or for none of them. This statement can be extended to non-integer alphabets as well – the following lemma summarizes that if we have a parallel addition algorithm for a base β, then we easily obtain such an algorithm also for conjugates of β by field isomorphism. Regarding the base 1/β, we can use the equality FinA(β) = FinA(1/β) to transfer the parallel addition algorithm, and thus in fact drop the requirement on the base to be greater than 1 in modulus. 286 vol. 58 no. 5/2018 Minimal Non-Integer Alphabets Allowing Parallel Addition Lemma 3.2. Let (β,A) be a numeration system such that A⊂ Z[β] and β is an algebraic number. Let β′ be a conjugate of β such that |β′| 6= 1 and σ : Q(β) 7→ Q(β′) be the corresponding field isomorphism. If there is a p-local parallel addition function ϕ in (β,A), then there exists a p-local parallel addition function ϕ′ in (β′,A′), where A′ = {σ(a) : a ∈A}. Proof. Let φ : Ap →A be a mapping which defines ϕ with p = r+t+ 1. We define a mapping φ′ : (A′)p →A′ by φ′(w′j+t, . . . ,w ′ j−r) = σ ( φ(σ−1(w′j+t), . . . ,σ −1(w′j−r)) ) . Next, we define a digit set conversion ϕ′ : (A′ + A′) → A′ by ϕ′(w′) = (z′j)j∈Z, where w ′ = (w′j)j∈Z and z′j = φ ′(w′j+t, . . . ,w ′ j−r). Obviously, if w ′ has only finitely many non-zero entries, then there is only finitely many non-zeros in (z′j)j∈Z, since φ′(0, . . . , 0) = σ ( φ(σ−1(0), . . . ,σ−1(0)) ) = σ ( φ(0, . . . , 0) ) = σ ( 0 ) = 0. The value of the number represented by w′ is also preserved: ∑ j∈Z w′jβ ′j = ∑ j∈Z σ(wj)σ(β)j = σ (∑ j∈Z wjβ j ) = σ (∑ j∈Z zjβ j ) = σ (∑ j∈Z φ ( wj+t, . . . ,wj−r ) βj ) = ∑ j∈Z σ ( φ ( wj+t, . . . ,wj−r )) β′ j = ∑ j∈Z z′jβ ′j, where wj = σ−1(w′j) for j ∈ Z and ϕ((wj)j∈Z) = (zj)j∈Z. Next, it is shown again in [4] that if a base β has a real conjugate greater than one, then there are some extra requirements on the alphabet A ⊂ Z[β]. The following lemma strengthens the results a bit. Lemma 3.3. Let (β,A) be a numeration system such that A ⊂ Z[β] and 1 < β ∈ R. Let λ = minA and Λ = maxA. If there exists a p-local parallel addition in (β,A), with p = r + t + 1, defined by a mapping φ: (A + A)p →A, then: (1.) φ(b, . . . ,b) 6= λ for all b ∈ A + A such that b > λ∧ (b ≥ 0 ∨ t = 0), (2.) φ(b, . . . ,b) 6= Λ for all b ∈ A + A such that b < Λ ∧ (b ≤ 0 ∨ t = 0), (3.) If Λ 6= 0, then φ(Λ, . . . , Λ) 6= Λ, (4.) If λ 6= 0, then φ(λ,. . . ,λ) 6= λ. Proof. (1.): Let b ∈A+A be such that b > λ. Assume, for contradiction, that φ(b, . . . ,b) = λ. We follow the proof of Claim 3.5. in [4]. For any n ∈ N,n ≥ 1, we consider the number represented by ω0 b. . .b︸ ︷︷ ︸ t b. . .b︸ ︷︷ ︸ n • b. . .b︸ ︷︷ ︸ r 0ω . Its representation after the digit set conversion has the form ω0 wr+t . . .w1︸ ︷︷ ︸ βnW λ.. .λ︸ ︷︷ ︸ n •w̃1 . . . w̃r+t0ω, where W = ∑r+t j=1 wjβ j−1 and wj, w̃j ∈A. Since both representations have the same value, we get: b n+t−1∑ j=−r βj = βnW + λ n−1∑ j=0 βj + r+t∑ j=1 w̃jβ −j for all n ≥ 1. Corollary 3.6. in [4] gives that W = bβ t−λ β−1 . Thus, b −1∑ j=−r βj + b βn+t − 1 β − 1 = βn bβt −λ β − 1 + λ βn − 1 β − 1 + t+r∑ j=1 w̃jβ −j. Hence b ( r∑ j=1 1 βj + −1 β − 1 ) = λ −1 β − 1 + t+r∑ j=1 w̃j 1 βj ≥ λ ( −1 β − 1 + t+r∑ j=1 1 βj ) . Using 1 β−1 = ∑∞ j=1 1 βj , we get − b 1 βr 1 β − 1 = −b ∞∑ j=r+1 1 βj ≥−λ ∞∑ j=r+t+1 1 βj = −λ 1 βr+t 1 β − 1 . Thus, we have λ ≥ bβt. If t = 0, then it contradicts the assumption b > λ. If b ≥ 0, then λ ≥ bβt ≥ b since β > 1, which is also a contradiction. The proof of (2.) is similar. For (3.) and (4.), see [4]. Now we can conclude with the following statement. Theorem 3.4. Let (β,A) be a numeration system such that A⊂ Z[β], β is an algebraic number with a positive real conjugate and there is parallel addition in (β,A). Let λ = minA and Λ = maxA. If λ ≡β−1 Λ, then there exists c ∈A,λ 6= c 6= Λ such that λ ≡β−1 c ≡β−1 Λ. If λ 6≡β−1 Λ, then there exist a,b ∈A,a 6= λ,b 6= Λ such that a ≡β−1 λ and b ≡β−1 Λ. 287 Jan Legerský Acta Polytechnica Proof. By Lemma 3.2, we can assume that the base β itself is real and greater than one. Let φ be a mapping which defines the parallel addition. Since {0} ( A, we know that Λ > 0 or λ < 0. Assume that Λ > 0, the latter one is analogous. By Theorem 3.1 and Lemma 3.3, Λ ≡β−1 φ(Λ, . . . , Λ) ∈ A and λ 6= φ(Λ, . . . , Λ) 6= Λ. Hence, φ(Λ, . . . , Λ) is a digit of A which belongs to the same congruence class as Λ. If λ ≡β−1 Λ, the claim follows, with c = φ(Λ, . . . , Λ). The case that λ 6≡β−1 Λ is divided into two sub-cases. If λ 6= 0, then we have λ ≡β−1 φ(λ,. . . ,λ) ∈ A and φ(λ,. . . ,λ) 6= λ again by Theorem 3.1 and Lemma 3.3, which implies the statement, with a = φ(λ,. . . ,λ) and b = φ(Λ, . . . , Λ). If λ = 0, then all elements of A + Λ are positive. Suppose, for contradiction, that there is no nonzero element of the alphabet A congruent to 0 modulo β−1. Let k be the number of congruence classes occurring in A and let R be a subset of A such that there is exactly one representative of each of those k congruence classes. For d ∈ Λ + R, the value φ(d,. . . ,d) ∈A is not congruent to 0, as φ(d,. . . ,d) 6= λ = 0 by Lemma 3.3 and the congruence class containing zero has only one element in A, by the previous assumption. Therefore, the values fj = φ(dj, . . . ,dj) ∈A for k distinct digits dj = Λ + ej ∈ Λ + R belong to only k − 1 congruence classes modulo β − 1. Hence, there exist two distinct elements d1,d2 ∈ Λ + R such that f1 ≡β−1 f2. Due to fj = φ(dj, . . . ,dj) ≡β−1 dj = Λ + ej for each j , we obtain also e1 ≡β−1 e2 which contradicts the con- struction of the set R. 3.1. A[β] closed under addition In order to express the properties of the alphabet A allowing parallel addition in terms of representatives modulo β and β − 1, we restrict ourselves to alpha- bets such that A[β] is closed under addition, or even slightly stronger condition that A[β] = Z[β]. The fol- lowing theorem summarizes some consequences of these assumptions. Theorem 3.5. Let (β,A) be a numeration system such that A ⊂ Z[β] and 1 ∈ A[β]. The following statements hold: (1.) If A[β] is closed under addition, then N[β] ⊂A[β]. (2.) A[β] is additive Abelian group if and only if A[β] = Z[β]. (3.) If N ⊂ A[β], then β is expanding, i.e., β is an algebraic number with all conjugates greater than 1 in modulus. Proof. (1.): Obviously, if A[β] is closed under addition, then N ⊂A[β]. Since 0 ∈A by our general assumption, also β ·A[β] ⊂A[β]. Therefore, β ·N ⊂A[β] and the claim N[β] ⊂A[β] follows by induction. (2.): The assumption that A[β] is closed also under subtraction and (1.) imply that Z[β] = N[β] −N[β] ⊂ A[β], and obviously A[β] ⊂ Z[β]. The opposite impli- cation is trivial. (3.): By Lemma 2.2, β is an algebraic number since A[β] ⊂ FinA(β). The proof that β must be expanding is based on the paper of S. Akiyama and T. Zäimi [9]. Let β′ be an algebraic conjugate of β and σ : Q(β) → Q(β′) be the field isomorphism such that σ(β) = β′. Since N ⊂ A[β], for all n ∈ N there exist a0, . . . ,aN ∈ A such that N∑ i=0 aiβ i = n = σ(n) = N∑ i=0 σ(ai)(β′)i . Denoting m̃ := max{|σ(a)|: a ∈A}, we have n = |n| ≤ N∑ i=0 |σ(ai)| · |β′|i ≤ ∞∑ i=0 |σ(ai)| · |β′|i ≤ m̃ ∞∑ i=0 |β′|i . As n is arbitrarily large, the sum on the right side di- verges, which implies that |β′| ≥ 1. Thus, all conjugates of β are at least one in modulus. If the degree of β is one, the statement is obvious. Therefore, we may assume that deg β ≥ 2. Suppose for contradiction that |β′| = 1 for an alge- braic conjugate β′ of β. The complex conjugate β′ is also an algebraic conjugate of β. Take any algebraic con- jugate γ of β and the isomorphism σ′ : Q(β′) → Q(γ) given by σ′(β′) = γ. Now 1 γ = 1 σ′(β′) = σ′ ( 1 β′ ) = σ′ ( β′ β′β′ ) = σ′ ( β′ |β′|2 ) = σ′(β′) . Hence, 1 γ is also an algebraic conjugate of β. Moreover,∣∣ 1 γ ∣∣ ≥ 1 and |γ| ≥ 1, which implies that |γ| = 1. We may choose γ = β, which contradicts |β| > 1. Thus all conjugates of β are greater than one in modulus, i.e., β is an expanding algebraic number. Let us remark that the assumption on A[β] to be closed under addition is satisfied by a wide class of numeration systems. Namely, if a numeration system (β,A) allows p-local parallel addition such that p = r+1, i.e., there is no anticipation, then A[β] is obviously closed under addition. Hence, (1.) and (3.) give the following corollary. Corollary 3.6. Let (β,A) be a numeration system such that 1 ∈A[β] and A⊂ Z[β]. If (β,A) allows par- allel addition without anticipation, then β is expanding. For β expanding, Lemma 8 in [10] provides a so called weak representation of zero property such that the absolute term is dominant, and hence parallel addition in the base β without anticipation is obtained for some integer alphabet Aint according Theorem 4.3. in [5]. 288 vol. 58 no. 5/2018 Minimal Non-Integer Alphabets Allowing Parallel Addition In what follows, we assume A[β] = Z[β], although the weaker assumption, A[β] being closed under addition, would be sufficient. The reason is that subtraction is also required in applications using parallel addition, such as on-line multiplication and division. Hence the assumption is justified by (2.) of Theorem 3.5. Let us mention that, for instance, the numeration system (2,{0, 1, 2}) allows parallel addition, but (2,{0, 1, 2}) is obviously not closed under subtraction. Theorem 3.7. If a numeration system (β,A) with A[β] = Z[β] allows parallel addition, then the alphabet A contains at least one representative of each congruence class modulo β and modulo β − 1 in Z[β]. Proof. Let x = ∑N i=0 xiβ i be an element of Z[β]. Since x0 ∈ Z ⊂A[β], we have x ≡β x0 = n∑ i=0 aiβ i ≡β a0 , where ai ∈A. Hence, for any element x ∈ Z[β], there is a digit a0 ∈A such that x ≡β a0. In order to prove that there is an element of A congruent to x modulo β − 1, we use the binomial theorem: x = N∑ i=0 xiβ i = N∑ i=0 xi(β − 1 + 1)i = N∑ i=0 x′j(β − 1) j, for some x′j ∈ Z. Hence x ≡β−1 x′0 = n∑ i=0 aiβ i , for some ai ∈A. We prove by induction with respect to n that x′0 ≡β−1 a for some a ∈ A. If n = 0, then x′0 = a0 ∈A. For n + 1, we have x′0 = n+1∑ i=0 aiβ i = a0 + (β − 1) n∑ i=0 ai+1β i + n∑ i=0 ai+1β i ≡β−1 a0 + a′ ≡β−1 a ∈A , where we use the induction assumption∑n i=0 ai+1β i ≡β−1 a′ ∈ A and the statement of Theorem 3.1, i.e, for each digit b ∈ A + A there is a digit a ∈A such that b ≡β−1 a. 3.2. Lower bound on #A When deriving the minimal size of alphabets for parallel addition, we assume that the base β is an algebraic integer (in this whole subsection), since it enables us to count the number of congruence classes, and hence to provide an explicit lower bound on the size of alphabet allowing parallel addition. In what follows, the monic minimal polynomial of an algebraic integer α is denoted by mα. Let d be the degree of β. It is well known that Z[β] = {∑d−1 i=0 xiβ i : xi ∈ Z } if and only if β is an algebraic integer. Hence, there is an obvious bijection π : Z[β] → Zd given by π(u) = (u0,u1, · · · ,ud−1)T for every u = ∑d−1 i=0 uiβ i ∈ Z[β]. Moreover, the addi- tive group Zd can be equipped with a multiplication such that π is a ring isomorphism. In order to do that, we recall the concept of companion matrix. Definition 3.8. Let p(x) = xd + pd−1xd−1 + · · · + p1x + p0 ∈ Z[x] be a monic polynomial with integer coefficients, d ≥ 1. The matrix S :=   0 0 · · · 0 −p0 1 0 · · · 0 −p1 0 1 · · · 0 −p2 ... ... ... 0 0 · · · 1 −pd−1   ∈ Z d×d is the companion matrix of the polynomial p. It is well known (see for instance [11]) that the characteristic polynomial of the companion matrix S is p. The matrix S is also root of the polynomial p. The claim of the following theorem, which provides the required multiplication in Zd, is discussed in [12]. These topics are also more elaborated in [13, 14]. Theorem 3.9. Let β be an algebraic integer of degree d ≥ 1 and let S be the companion matrix of mβ. If the multiplication �β : Zd ×Zd → Zd is defined by u�β v := (d−1∑ i=0 uiS i ) ·v for all u = (u0,u1, · · · ,ud−1)T ,v ∈ Zd, then (Zd, +,�β) is a commutative ring which is isomorphic to Z[β] by the mapping π. One of the consequences is the following lemma. Although it is a known result, we include its proof here, to be more self-contained. Let us recall that for a non-singular integer matrix M ∈ Zd×d, two vectors x,y ∈ Zd are congruent modulo M in Zd, denoted by x ≡M y, if x−y ∈ MZd. Lemma 3.10. Let β be an algebraic integer of degree d and α ∈ Z[β] be such that deg α = deg β. The number of congruence classes modulo α in Z[β] is |mα(0)|. Proof. The number α is an algebraic integer, since it is well known that sum and product of algebraic integers is an algebraic integer. Let γ,δ ∈ Z[β] and let S be the companion matrix of the minimal polynomial mβ of the algebraic integer β. Let π(α) = (a0,a1, · · · ,ad−1)T , with α = ∑d−1 i=0 aiβ i. If we set Sα := ∑d−1 i=0 aiS i, then the congruences ≡α in Z[β] and ≡Sα in Zd fulfill: γ ≡α δ ⇐⇒ ∃ε ∈ Z[β] : γ −δ = αε ⇐⇒ ∃z = π(ε) ∈ Zd : π(γ) −π(δ) = = π(γ −δ) = π(α) �β z = Sα ·z ⇐⇒ π(γ) ≡Sα π(δ) . 289 Jan Legerský Acta Polytechnica Thus, the number of congruence classes modulo α in Z[β] equals the number of congruence classes modulo Sα in Zd, which is known to be |det Sα|. To show that |det Sα| = |mα(0)|, we proceed in the following way: the characteristic polynomial of the com- panion matrix S is the same as the minimal polynomial of β. Since minimal polynomials have no multiple roots, S is diagonalizable over C, i.e., S = P−1DP where D is a diagonal matrix with the conjugates of β on the diagonal, and P is a non-singular complex matrix. The matrix Sα is also diagonalized by P : Sα = d−1∑ i=0 aiS i = d−1∑ i=0 ai(P−1DP)i = P−1 (d−1∑ i=0 aiD i ) ︸ ︷︷ ︸ Dα P . It is known (see for instance [15]) that if σ : Q(β) → Q(β′) is a field isomorphism and α ∈ Q(β), then σ(α) is a conjugate of α, and we obtain all conjugates of α in this way. Since α = ∑d−1 i=0 aiβ i, deg α = deg β and D has conjugates of β on the diagonal, the diagonal elements of the diagonal matrix Dα are precisely all conjugates of α. Hence, |det Sα| equals absolute value of the product of all conjugates of α, which is |mα(0)|. Finally, we put together the fact that the alphabet A for parallel addition in base β contains all representatives modulo β and modulo β − 1, the derived formula for the number of congruence classes, and also specific restrictions on alphabets for parallel addition in a base with some positive real conjugate. Theorem 3.11. Let (β,A) be a numeration system such that β is an algebraic integer and A[β] = Z[β]. If the numeration system (β,A) allows parallel addition, then #A≥ max { |mβ(0)|, |mβ(1)| } . Moreover, if β has a positive real conjugate, then #A≥ max { |mβ(0)|, |mβ(1)| + 2 } . Proof. By Theorem 3.7, the alphabet A for parallel addition must contain all representatives modulo β and modulo β − 1 in Z[β]. The numbers of congruence classes are |mβ(0)| and |mβ−1(0)|, respectively, by Lemma 3.10. Obviously, mβ−1(x) = mβ(x + 1). Thus mβ−1(0) = mβ(1). Theorem 3.4 ensures that if the minimal and maximal element of A are congruent modulo β−1, then there are at least three digits of A in this class. Otherwise, the class of the minimal and also the class of the maximal element of A have at least two elements. Both lead to the conclusion that #A≥ |mβ(1)| + 2. We remark that the obtained bound is basically the same as the one for integer alphabets in [4]. 4. Necessary and sufficient condition on bases for parallel addition P. Kornerup [2] proposed a more general concept of parallel addition called k-block parallel addition. The idea is that blocks of k digits are considered as one digit in the new numeration system with base being the k-th power of the original one. Definition 4.1. For a positive integer k, the numer- ation system (β,A) allows k-block parallel addition if there exists parallel addition in (βk,A(k)), where A(k) = {ak−1βk−1 + · · · + a1β + a0 : ai ∈A}. We remark that 1-block parallel addition is the same as parallel addition. C. Frougny, P. Heller, E. Pelantová and M. Svobodová [3] showed that for a given base β, there exists an integer alphabet A such that (β,A) allows parallel addition if and only if β is an algebraic number with no conjugates of modulus 1. Moreover, it was shown that the concept of k-block parallel addition does not enlarge the class of basis allowing parallel addition in case of integer alphabets. We prove an extension of these statements also to alphabets being subsets of Z[β] in Theorem 4.2. Although the k-block concept does not enlarge the class of bases for parallel addition, it might decrease the minimal size of the alphabet. Theorem 4.2. Let β be a complex number such that |β| > 1. There exists an alphabet A⊂ Z[β] with 0 ∈A and 1 ∈ FinA(β) which allows k-block parallel addition in (β,A) for some k ∈ N, if and only if β is an algebraic number with no conjugate of modulus 1. If this is the case, then there also exists an alphabet in Z allowing 1-block parallel addition in base β. Proof. If the base β is an algebraic number with no conjugates of modulus 1, then [5] provides a ∈ N such that the alphabet A = {−a,−a+ 1, . . . , 0, . . . ,a−1,a} allows 1-block parallel addition. Obviously, 0 ∈A⊂ Z and 1 ∈ FinA(β). For the opposite implication, β is an algebraic number by Corollary 2.3. Let r,s ∈ N and u−r, . . . ,us ∈A be such that s∑ j=−r ujβ j = 1 ∈ FinA(β) . (1) Now we slightly modify the proof from [3] to show that if β has a conjugate of modulus 1, then there is no alphabet in Z[β] allowing block parallel addition. Let γ be a conjugate of β such that |γ| = 1 and let σ : Q(β) → Q(γ) be the field isomorphism such that σ(β) = γ. Let A′ := {σ(a) : a ∈ A}. Assume, for contradiction, that there are k,p ∈ N such that there exists p-local function performing k-block parallel addition on (β,A). We denote S := max {∣∣∣∣pk−1∑ j=0 ajγ j ∣∣∣∣: aj ∈A′ } . 290 vol. 58 no. 5/2018 Minimal Non-Integer Alphabets Allowing Parallel Addition Since there are infinitely many j such that Re γj > 12 , there exists N > p and indices 0 ≤ j1 < · · · < jm ≤ kN − 1 satisfying ji+1 − ji > r + s for all i ∈{1, . . . ,m− 1} such that 2S < Re kN−1∑ j=0 εjγ j ≤ ∣∣∣∣kN−1∑ j=0 εjγ j ∣∣∣∣, where εj = 1 if j = ji for some i ∈ {1, . . . ,m} and εj = 0 otherwise. By using the representation (1) of 1 and the fact that ji+1 − ji > r + s, we have∑kN−1 j=0 εjγ j = ∑m i=1 1 ·γ ji = ∑kN−1+s j=−r v ′ jγ j for some v′j ∈A ′. Hence 2S < T := max {∣∣∣∣kN−1+s∑ j=−r ajγ j ∣∣∣∣: aj ∈A′ } . Let x′ = ∑kN−1+s j=−r σ(xj)γ j, where x−r, . . . , xkN−1+s ∈ A, be such that |x′| = T. Let x =∑kN−1+s j=−r xjβ j, i.e., x′ = σ(x). Since there is a k- block parallel addition in (β,A), we have x+x = k(N+p)−1+s∑ j=kN+s zjβ j+ kN−1+s∑ j=−r zjβ j+ −r−1∑ j=−kp−r zjβ j, where zj ∈A. We denote z′j := σ(zj). Hence, z ′ j ∈A ′, and |x′| + 2S < |x′| + |x′| = |x′ + x′| ≤ ∣∣∣∣ k(N+p)−1+s∑ j=kN+s z′jγ j ∣∣∣∣+ ∣∣∣∣kN−1+s∑ j=−r z′jγ j ∣∣∣∣+ ∣∣∣∣ −r−1∑ j=−kp−r z′jγ j ∣∣∣∣ ≤ |γkN+s|S + |x′| + |γ−kp−r|S = 2S + |x′| , which is a contradiction. 5. Conclusion We have shown that the necessary conditions on β and A allowing parallel addition that were known for alphabets consisting of consecutive integers can be largely extended to alphabets A being subsets of Z[β]. During our investigation, we also considered even more general case: β ∈ Z[ω] and A ⊂ Z[ω], where ω is an algebraic number. Clearly, Z[β] ⊂ Z[ω], but if Z[β] ( Z[ω], then congruences modulo β or β − 1 behave differently in Z[ω] than in Z[β]. Due to this fact, Theorem 3.7 does not hold in the Z[ω] setting, see a counterexample: let ω = 12 √ 5 + 12 , β = −2ω+ 1 = − √ 5 and A = {−2,−1, 0, 1, 2, 3}⊂ Z[ω]. This numeration system allows parallel addition, but −2 ≡β−1 0 ≡β−1 2 and −1 ≡β−1 1 ≡β−1 3, with ≡β−1 in Z[ω]. The minimal polynomial of β is x2 − 5, thus there are six congruence classes modulo β − 1 in Z[ω], i.e., A does not contain representatives of all congruence classes. See [14] for further elaboration. We conjecture the converse of Corollary 3.6, that is: let (β,A) be a numeration system such that 1 ∈A[β] and A ⊂ Z[β]. Let (β,A) allow parallel addition by p-local function with p = r + t + 1. If β is expanding, then the parallel addition is without anticipation, i.e., t = 0. 6. Acknowledgments This work was supported by GAČR 13-03538S and SGS 17/193/OHK4/3T/14. The author thanks to Milena Svobodová and Edita Pelantová for fruitful discussions. References [1] A. Avizienis. Signed-digit number representations for fast parallel arithmetic. IEEE Trans Comput 10:389–400, 1961. [2] P. Kornerup. Necessary and sufficient conditions for parallel, constant time conversion and addition. Proc 14th IEEE Symp on Comp Arith pp. 152–155, 1999. [3] C. Frougny, P. Heller, E. Pelantová, M. Svobodová. k-block parallel addition versus 1-block parallel addition in non-standard numeration systems. Theoret Comput Sci 543:52–67, 2014. [4] C. Frougny, E. Pelantová, M. Svobodová. Minimal digit sets for parallel addition in non-standard numeration systems. J Integer Seq 16:36, 2013. [5] C. Frougny, E. Pelantová, M. Svobodová. Parallel addition in non-standard numeration systems. Theoret Comput Sci 412:5714–5727, 2011. [6] M. Brzicová, C. Frougny, E. Pelantová, M. Svobodová. On-line Multiplication and Division in Real and Complex Bases. In 2016 IEEE 23nd Symp. Comput. Arith. (ARITH), pp. 134–141. IEEE, 2016. doi:10.1109/ARITH.2016.13. [7] J. Legerský, M. Svobodová. Construction of Algorithms for Parallel Addition, 2018. http://arxiv.org/abs/1801.01062. [8] S. Baker, Z. Masáková, E. Pelantová, T. Vávra. On periodic representations in non-Pisot bases. Monatshefte für Math 184(1):1–19, 2017. doi:10.1007/s00605-017-1063-9. [9] S. Akiyama, T. Zaïmi. Comments on the height reducing property. Cent Eur J Math 11:1616–1627, 2013. [10] S. Akiyama, P. Drungilas, J. Jankauskas. Height reducing problem on algebraic integers. Funct Approx Comment Math 47:105–119, 2012. doi:10.7169/facm/2012.47.1.9. [11] R. A. Horn, C. R. Johnson. Matrix Analysis. Cambridge University Press, 1990. [12] I. Kátai. Generalized number systems in Euclidean spaces. Math Comput Model 38:883 – 892, 2003. [13] J. Legerský. Construction of algorithms for parallel addition. Research project, Czech Technical University in Prague, FNSPE, Czech Republic, 2015. http://jan.legersky.cz/pdf/research_project_ parallel_addition.pdf. [14] J. Legerský. Construction of algorithms for parallel addition in non-standard numeration systems. Master Thesis, Czech Technical University in Prague, FNSPE, Czech Republic, 2016. http://jan.legersky.cz/pdf/ master_thesis_parallel_addition.pdf. [15] R. Chapman. Algebraic Number Theory – summary of notes. http://empslocal.ex.ac.uk/people/staff/ rjchapma/notes/ant2.pdf. Accessed: 2017-12-16. 291 http://dx.doi.org/10.1109/ARITH.2016.13 http://arxiv.org/abs/1801.01062 http://dx.doi.org/10.1007/s00605-017-1063-9 http://dx.doi.org/10.7169/facm/2012.47.1.9 http://jan.legersky.cz/pdf/research_project_parallel_addition.pdf http://jan.legersky.cz/pdf/research_project_parallel_addition.pdf http://jan.legersky.cz/pdf/master_thesis_parallel_addition.pdf http://jan.legersky.cz/pdf/master_thesis_parallel_addition.pdf http://empslocal.ex.ac.uk/people/staff/rjchapma/notes/ant2.pdf http://empslocal.ex.ac.uk/people/staff/rjchapma/notes/ant2.pdf Acta Polytechnica 58(5):285–291, 2018 1 Introduction 2 Preliminaries 3 Necessary conditions on alphabets allowing parallel addition in A subset Z[beta] 3.1 A[beta] closed under addition 3.2 Lower bound on A 4 Necessary and sufficient condition on bases for parallel addition 5 Conclusion 6 Acknowledgments References