NEW CRITERIA FOR CANONICAL NUMBER SYSTEMS

SHIGEKI AKIYAMA AND HUI RAO

Abstract. Let P (x) = x^{d} + p_{d−1}x^{d−1} + ⋯ + p_{0} be an expanding monic polynomial with integer coefficients. If each element of ℤ[x]/P (x)ℤ[x] has a polynomial representative with coefficients in [0, |p_{0}| − 1] then P (x) is called a canonical number system generating polynomial, or a CNS polynomial in short. A method due to Hollander [6] is employed to study CNS polynomials. Several new criteria for canonical number system generating polynomials are given and a conjecture of S.Akiyama & A.Pethő [3] is proved. The known results, especially an algorithm of H. Brunotte’s in [4] and a recent work of K. Scheicher & J.M.Thuswaldner [15], can be derived by this new method in a simpler way.

1. Introduction

Let P (x) = p_{d}x^{d} + p_{d−1}x^{d−1} + ⋯ + p_{0} be a polynomial of x with integer coefficients and p_{d} = 1. Let R be the quotient ring ℤ[x]/P (x)ℤ[x]. As a ℤmodule, R is naturally isomorphic to ℤ^{d} and each element ξ of R is represented uniquely in the form

(1)  ξ ≡ ∑_{i=0}^{d−1} a_{i}x^{i} (mod P (x))

with a_{i} ∈ ℤ. If an element ξ ∈ R has an expression of the form

ξ ≡ b_{0} + b_{1}x + ⋯ + b_{M−1}x^{M−1} (mod P (x))

with a_{i} ∈ [0, |p_{0}| − 1] ∩ ℤ, then we say that ξ has a canonical expression. If every element ξ ∈ R has a canonical expression, then P (x) is called a canonical number system generating polynomial, or a CNS polynomial in short. Let T : R → R be a map defined by

T (ξ) ≡ ∑_{i=0}^{d−1} (a_{i+1} − p_{i+1} [\frac{a_{0}}{p_{0}} ]) x^{i} (mod P (x)).

1991 Mathematics Subject Classification. 11A63, 37B10. Key words and phrases. Canonical number system, radix representation, symbolic dynamics. The first author is supported by the Japanese Ministry of Education, Culture, Sports, Science

and Technology, Grand-in Aid for fundamental research, 12640017, 2001.

The second author is supported by the Japan Society for the Promotion of Science.

Here we put a_{d} = 0. Let α = x mod P (x). Then R/(α) is isomorphic to ℤ/p_{0}ℤ as a ℤ-module. Denote this isomorphism as τ : R/(α) → ℤ/p_{0}ℤ. Then the map T can be rewritten as

T (ξ) = (ξ − a)/α

where a ∈ [0, |p_{0}| − 1] is the representative of τ(ξ). Denote by T^{m} the m-th iteration of the map T. ξ has a canonical expression (obviously this expression is unique) if and only if there is a non-negative integer M such that T^{M}(x) = 0.

When P (x) is irreducible, R is identified with ℤ[α] with a root α of P (x). This case had been extensively studied. In this case, a pair (α, {0, 1, …, |p_{0}| − 1}) is said to form a canonical number system when P (x) is a CNS polynomial. Here we only refer to the original studies in I. Kátai & J. Szabó [7], I. Kátai & B. Kovács [9], [10], W. Gilbert [5] and B. Kovács & A. Pethő [12].

A. Pethő [13] generalized this study to non irreducible polynomials. It is well known that (see [12])

If P (x) is a CNS polynomial, then P (x) is expanding (,that is, all root of P (x) has modulus greater than one) and P (x) has no positive real root. Especially the last condition implies

(2)  p_{0} > 1.

It is not hard to work out an algorithm to determining whether a polynomial is a CNS polynomial. In Section 2, we will give such an algorithm. However, we want to see whether a given polynomial is a CNS polynomial or not by just looking its coefficients. Many papers are devoted to this problem. Generalizing former results of I. Kátai & B. Kovács [9], [10], B.Kovács proved

If p_{0} ≥ 2 and

(3)  p_{d} ≤ p_{d−1} ≤ ⋯ ≤ p_{0}

hold, then P (x) is a CNS polynomial (see also [5], [13]) provided P (x) is irreducible.

In S. Akiyama & A.Pethő [3], it is proved that

p_{2} ≥ 0, p_{3} ≥ 0, …, p_{d−1} ≥ 0, ∑_{i=1}^{d} p_{i} ≥ 0, and p_{0} > 2 ∑_{i=1}^{d} |p_{i}|

imply that P (x) is a CNS polynomial. In the same paper, they conjectured that the last condition can be relaxed to

(4)  p_{0} > ∑_{i=1}^{d} |p_{i}|.

In this paper, we employ a method of Hollander to study CNS polynomials (He deviced the method for studying of Pisot number system). In section 3, we give two criteria of CNS polynomials. First we will give an affirmative answer to the conjecture of [3] and also deal with a slightly generalized situation

(5)  p_{0} ≥ ∑_{i=1}^{d} |p_{i}|

in Theorem 3.2. Second, when P (x) is a polynomial with (5) and has exactly one negative coefficient, P (x) is a CNS polynomial or not is characterized by one inequality (see Theorem 3.5).

Section 4 is devoted to Bronotte’s algorithm. H. Brunotte [4] discovered a nice method to determine CNS polynomials. The original argument looks not simple. We apply our method and give a short proof of Brunotte’s Lemma (See Lemma 4.1). Also Theorem 4.2 shows that for any expanding P (x), Brunotte’s method actually gives a finite and efficient algorithm to determine CNS polynomials. Moreover, if the dominant condition (5) is assumed, then the algorithm becomes simpler (Theorem 4.3).

While preparing our paper, we are informed that similar results were shown recently by a different approach by K. Scheicher & J.M.Thuswaldner [15]. We would like to express our deep gratitude for their correspondences. It seems worthy to describe in detail the difference of ideas. The main difference is in the ways of description. Our way is algebraic having a flavor of symbolic dynamics. The idea of proofs is originally due to the thesis of M.Hollander [6]. On the other hand, their way depends on the transducer automata. Nevertheless, the basic ideas of two papers are close.

Corollary 4.4 is first proved by [15]. As a generalization of their result, we relax the condition (4) to (5) and get Theorem 4.3. Inspired by their result, easy characterizations of CNS polynomials with (4) of degree not larger than 5 will be given in §5. Our idea in §5 is to use not only Corollary 4.4 but also all known necessary conditions to simplify our arguments. It is shown that the known necessary conditions are not sufficient to characterize degree five CNS polynomials, even if we assume (4).

2. Algorithm.

Here we give a basic proposition.

Proposition 2.1. Assume that P (x) is an expanding polynomial. Then for any ξ ∈ R, the sequence

ξ, T (ξ), T^{2}(ξ), …

is eventually periodic.

Remark 2.2. I. Kátai & I. Kőrnyei [8] proved this in the case when P (x) is expanding and irreducible.

Proof. Let P (x) be an expanding polynomial as in §1 and A be its companion matrix, that is,

A = (\begin{matrix}0 & 0 & 0 & … & 0 & −p_{0} \\ 1 & 0 & 0 & … & 0 & −p_{1} \\ 0 & 1 & 0 & … & 0 & −p_{2} \\ & & ⋮ & & & ⋮ \\ 0 & … & 0 & 1 & 0 & −p_{d−2} \\ 0 & … & … & 0 & 1 & −p_{d−1} \end{matrix}) .

Let D be a complete representative system of ℤ^{d}/Aℤ^{d} of the form

D = {kv | k = 0, 1, …, p_{0} − 1}

with v = (0, …, 0, 1). Let ξ ∈ R and

ξ = ξ_{0} + ξ_{1}α + ⋯ + ξ_{d−1}α^{d−1}.

We can embed R into ℝ^{d} by

π(ξ) := ( ξ_{0} ; ξ_{1} ; ⋮ ; ξ_{d−1}) .

It is easy to check π(αξ) = Aπ(ξ). For any y ∈ ℤ^{d} there is a unique v ∈ D such that A^{−1}(y − v) is an integer. Define

S(y) := A^{−1}(y − v).

To prove {T^{m}(ξ)}_{m≥0} is eventually periodic, we only need to show that {S^{m}(y)}_{m≥0} is eventually periodic. As A is expanding there exists a positive integer k so that the map f_{k} : x → A^{−k}x is a contraction ^{1} on ℝ^{d}. This implies that {S^{m}(y)}_{m≥0} is a bounded sequence in ℤ^{d}, and thus it is eventually periodic. □

Let P be the set of purely periodic elements in R, i.e.,

(6)  P = {ξ ∈ R | ∃M > 0 T^{M}(ξ) = ξ}.

By Proposition 2.1, an expanding polynomial P (x) is a CNS polynomial if and only if P = {0}. It is important to get an algorithmic bound for searching elements of P. In fact, it is easily seen that if P (x) has no multiple root, then

(7)  P ⊂ \{ξ ∈ R | |ξ(α)| ≤ \frac{|p_{0}| − 1}{|α| − 1} for all root α of P (x)\} ,

(see [12], [8] and [13]). Here ξ(α) is well defined by substituting the indeterminate x with α.

1Note that f_{1} is not necessary a contraction.

In the following, we shortly discuss a way to give an explicit upper bound suitable for computation, and this will give us an effective algorithm for determining whether a polynomial is a CNS polynomial.

Decompose the expanding polynomial P (x) = ∏_{i=1}^{n}(x − α_{i})^{e_{i}+1} into factors in ℂ(x). For ξ ∈ R, let

T^{m}(ξ) = \frac{T^{m−1}(ξ) − a_{m−1}}{α}

where a_{m−1} ∈ [0, |p_{0}| − 1] ∩ ℤ is a representative of τ(T^{m−1}(ξ)). Then we have

(8)  ξ = a_{0} + a_{1}α + ⋯ + a_{m−1}α^{m−1} + α^{m}T^{m}(ξ).

We wish to give an upper bound of the set {T^{m}(ξ)}_{m=0,1,...}. Putting ξ = E(x) mod P (x) and T^{m}(ξ) = F_{m}(x) mod P (x), then (8) is rewritten into:

(9)  E(x) = a_{0} + a_{1}x + ⋯ + a_{m−1}x^{m−1} + x^{m}F_{m}(x) + G_{m}(x)P (x),

for some G_{m}(x) ∈ ℤ[x]. We claim that, for any ε > 0,

(10)  |\frac{d^{j}}{dx^{j}} F_{m}(α_{i})| ≤ K_{j}(α_{i}) + ε

for a sufficiently large m where

K_{j}(α_{i}) = \frac{j!(|p_{0}| − 1)}{(|α_{i}| − 1)^{1+j}} .

This is shown by differentiating (9) several times and using an estimate:

|∑_{ℓ=1}^{m} a_{m−ℓ} \frac{(−ℓ)_{j}}{α_{i}^{j+ℓ}} | ≤ (|p_{0}| − 1) ∑_{ℓ=1}^{m} \frac{ℓ(ℓ + 1) … (ℓ + j − 1)}{|α_{i}|^{j+ℓ}} = K_{j}(α_{i})

where

(r)_{j} = \begin{cases}r(r − 1) … (r − j + 1) & ,  j ≥ 1 \\ 1 & ,  j = 0. \end{cases}

On the other hand by (1), there exist integers c_{m,i} that

F_{m}(x) = ∑_{i=0}^{d−1} c_{m,i}x^{i}.

Then we can deduce an upper bound of c_{m,i} from (10). This shows that {T^{m}(ξ)}_{m=0,1,...} is contained in a bounded set which gives an alternative proof of Proposition 2.1. As ξ = E(x) mod P (x) we may define, for i = 1, …, e_{i},

ξ^{(j)}(α_{i}) = \frac{d^{j}}{dx^{j}} E(x)|_{x=α_{i}} .

Then we see Proposition 2.3.

(11) P ⊂ {ξ ∈ R | |ξ^{(j)}(α_{i})| ≤ K_{j}(α_{i}) for i = 1, 2, …, n, j = 0, …, e_{i} } ,

Proof. If ξ ∈ P, then there exist a positive integer M that ξ = T^{M}(ξ). Thus ξ = T^{m}(ξ) = F_{m}(x) mod P (x) ∈ P for any m which is a multiple of M. This means that |ξ^{(j)}(α_{i})| ≤ K_{j}(α_{i}) + ε for any ε > 0, showing the assertion. □

3. Sufficient conditions on CNS

Put α = x mod P (x). Then by (1), R has a base {1, α, α^{2}, …, α^{d−1}} as a ℤmodule. We introduce a different base {w_{1}, w_{2}, …, w_{d}}, which already appeared in [4] [3], [15] and implicitly in [5]:

(w_{1} ; w_{2} ; w_{3} ; ⋮ ; w_{d}) = ( p_{d} 0 . . . . . . . . . 0 ; p_{d−1} p_{d} 0 . . . . . . 0 ; p_{d−2} p_{d−1} p_{d} 0 … 0 ; ⋮ ; p_{1} p_{2} p_{3} … p_{d−1} p_{d}) ( 1 ; α ; α^{2} ; ⋮ ; α^{d−1}) .

Define ι : ℤ^{d} → R by ι(z_{1}, z_{2}, …, z_{d}) = ∑_{i=1}^{d} z_{i}w_{i} and

z_{d+1} = − [\frac{∑_{i=1}^{d} z_{i}p_{d−i+1}}{p_{0}} ] .

Replace (z_{1}, z_{2}, …, z_{d}) by (z_{2}, z_{3}, …, z_{d+1}), where z_{d+1} is determined by the above formula. In this way, once (z_{1}, z_{2}, …, z_{d}) ∈ ℤ^{d} is given, it defines an infinite sequence (z_{1}, z_{2}, …, z_{d}, z_{d+1}, …). Let σ : ℤ^{d} → ℤ^{d} be a ‘shift’ map:

σ(z_{1}, z_{2}, …, z_{d}) = (z_{2}, z_{3}, …, z_{d+1}).

Then we can easily confirm the following commutative diagram:

(12)  \begin{matrix}ℤ^{d} & ⟶^{σ} & ℤ^{d} \\ ^{ι}↓ & & ↓^{ι} \\ R & ⟶_{T} & R \end{matrix}

Hereafter we employ the method due to M. Hollander [6] developed for a different number system attached to Pisot numbers. His main idea is to interpret the map T as a shift on bi-infinite words generated by ℤ. Next proposition is merely a consequence of the definition of z_{i} but we restate it to emphasize his idea.

Proposition 3.1. We have

0 ≤ z_{i}p_{d} + z_{i+1}p_{d−1} + ⋯ + z_{i+d−1}p_{1} + z_{i+d}p_{0} < p_{0},

and z_{d+i} is determined uniquely by this condition.

Theorem 3.2. Assume that P (x) is an expanding polynomial whose coefficients satisfy p_{2} ≥ 0, p_{3} ≥ 0, …, p_{d−1} ≥ 0, ∑_{i=1}^{d} p_{i} ≥ 0 and the dominant condition p_{0} > ∑_{i=1}^{d} |p_{i}|. Then P (x) is a CNS polynomial. The dominant condition can be replaced by p_{0} ≥ ∑_{i=1}^{d} |p_{i}| if one of the following conditions holds:

(1) p_{1} < 0,

(2) p_{i} > 0 for all i = 1, …, d − 1.

Remark 3.3. The dominant condition p_{0} > ∑_{i=1}^{d} |p_{i}| guarantees that the polynomial P (x) is expanding (c.f. Lemma 1 of [3].)

Remark 3.4. The above supplementary condition is necessary when p_{0} = ∑_{i=1}^{d} |p_{i}|. For example, x^{3} + 3x^{2} + 4 is not a CNS polynomial. H. Brunotte kindly pointed out an error in the original manuscript and the example is also due to him.

The proof of Theorem 3.2 is divided into two parts. First we settle the case p_{1} ≥ 0. The case p_{1} < 0 will be shown in a more generalized form in Theorem 3.5.

Proof of Theorem 3.2 when p_{1} ≥ 0. Recall that P is the set of purely periodic elements in R defined by (6). To prove P (x) is CNS polynomial, it suffices to show that P = {0}. Otherwise let ξ = ∑_{i=0}^{d−1} z_{i}w_{i} be a non zero element of P and z_{0}z_{1}z_{2} … be the infinite sequence determined by Proposition 3.1. Since ξ is a non zero purely periodic element, we have z_{0}z_{1}z_{2} ⋯ ≠ 0^{∞} and it is purely periodic. So we can extend it to be a bi-infinite word Ξ = … z_{−2}z_{−1}z_{0}z_{1}z_{2} … and it is easy to see that

(13)  0 ≤ z_{i}p_{d} + z_{i+1}p_{d−1} + ⋯ + z_{i+d−1}p_{1} + z_{i+d}p_{0} < p_{0}

hold for all i ∈ ℤ.

First we argue that there exist i ∈ ℤ such that z_{i} < 0. For if z_{i} ≥ 0 for all i ∈ ℤ, then for an index i such that z_{i+d} > 0 we have

z_{i}p_{d} + z_{i+1}p_{d−1} + ⋯ + z_{i+d−1}p_{1} + z_{i+d}p_{0} ≥ p_{0},

which is a contradiction.

Let min_{i∈ℤ} z_{i} = −κ ≤ −1 and max_{i∈ℤ} z_{i} = η. Note that both κ and η are finite since Ξ is a periodic word. Now we take i such that z_{i+d} = −κ. Then by the left side of (13),

(14)  z_{i}p_{d} + z_{i+1}p_{d−1} + ⋯ + z_{i+d−1}p_{1} ≥ κp_{0}
(15)  η(p_{d} + p_{d−1} + ⋯ + p_{1}) ≥ κp_{0}

which yields

(16)  η > κ ≥ 1

provided p_{0} > ∑_{i=1}^{d} |p_{i}|.

We shall show that the inequality (16) holds in case p_{i} > 0 for i = 1, …, d − 1 and p_{0} = ∑_{i=1}^{d} p_{i}. The above argument shows

η ≥ κ ≥ 1.

Assume η = κ. By (14) and (15), η = κ and p_{i} > 0 implies

(17)  z_{i} = z_{i+1} ⋯ = z_{i+d−1} = η.

Let us consider (13) with i → i − 1. By (17) and the right side of (13),

z_{i−1} + η(p_{d−1} + p_{d−2} + ⋯ + p_{0}) < p_{0}
−κ ≤ z_{i−1} < −η(p_{d−1} + p_{d−2} + ⋯ + p_{1}) + (1 − η)p_{0}
κ > η(p_{d−1} + p_{d−2} + ⋯ + p_{1}).

As p_{d−1} + p_{d−2} + ⋯ + p_{1} > 0 we get κ > η which is absurd. This shows η > κ in any cases.

Let j be an index such that z_{j+d} = η. Now we use (13) again with i = j to get:

z_{j}p_{d} + z_{j+1}p_{d−1} + ⋯ + z_{j+d−1}p_{1} < (1 − η)p_{0} ≤ −κp_{0}
−κ(p_{d} + p_{d−1} + ⋯ + p_{1}) < −κp_{0},

which yields p_{d} + p_{d−1} + ⋯ + p_{1} > p_{0}. This contradicts our assumption. Hence P = {0}. □

Reviewing the above proof, we get a necessary condition for P (x) to be a CNS polynomial. Let k be an integer, 0 < k ≤ d, and consider the sum

C_{k}(ℓ) = ∑_{0≤ki+ℓ≤d} p_{ki+ℓ}, ℓ = 0, 1, …, k − 1.

For certain k, if C_{k}(ℓ) ∈ [0, p_{0} − 1] for all ℓ, then P (x) is not a CNS polynomial. Indeed, a bi-infinite word

Ξ = (\overbrace{00...0}^{k−1} 1)^{∞}

obviously gives an element of P. Therefore, if P (x) is a CNS polynomial then for any k, 0 < k ≤ d, there exist ℓ that C_{k}(ℓ) ∉ [0, p_{0} − 1], which we call the k-subsum condition.

Since P (x) has no positive roots, we see ∑_{i=0}^{d} p_{i} ≥ 0. Hence 1-subsum condition is nothing but

∑_{i=1}^{d} p_{i} ≥ 0,

appeared in the condition of Theorem 3.2. This 1-subsum condition is also seen in Lemma 4 of [3].

Now let us treat polynomials having an isolated negative coefficient p_{k} < 0 and satisfying the dominant condition p_{0} ≥ ∑_{i=1}^{d} |p_{i}|. Under these assumptions, C_{k}(ℓ) (ℓ > 0) must be in [0, p_{0} − 1]. Thus C_{k}(0) ≥ p_{0}, i.e.,

∑_{1≤ki≤d} p_{ki} ≥ 0

is necessary for P (x) to be a CNS polynomial (Note that this implies that k is not greater than d/2). Theorem 3.5 shows that this condition is also sufficient.

Theorem 3.5. Assume that P (x) is an expanding polynomial with the dominant condition p_{0} ≥ ∑_{i=1}^{d} |p_{i}| whose coefficients are non-negative except p_{k} < 0 for a single index 0 < k < d. Then P (x) is a CNS polynomial if and only if

∑_{1≤ki≤d} p_{ki} ≥ 0.

As stated before, the proof of Theorem 3.2 for the case p_{1} < 0 is completed at the same time.

Proof of Theorem 3.5. Suppose P (x) is a polynomial satisfying the assumptions of the theorem and it is not a CNS polynomial. Then similar to the proof of Theorem 3.2, we can construct a non-zero bi-infinite periodic word Ξ = … z_{−2}z_{−1}z_{0}z_{1}z_{2} … satisfying (13). We shall derive a contradiction from the existence of such a word.

Let κ = 0 if z_{i} ≥ 0 for all i ∈ ℤ. Otherwise we define −κ = min_{i∈ℤ} z_{i}. Let η = max_{i∈ℤ} z_{i}.

First we claim that η > κ. In case of κ = 0 this is trivial. Suppose κ < 0. Let i be an index such that z_{i+d} = −κ. Without loss of generality, we assume i = 0. Then

(18)  0 ≤ z_{0}p_{d} + z_{1}p_{d−1} + ⋯ + z_{d−1}p_{1} + z_{d}p_{0} < p_{0}
κp_{0} ≤ z_{0}p_{d} + z_{1}p_{d−1} + ⋯ + z_{d−1}p_{1}
(19)  κp_{0} ≤ κ|p_{k}| + η ∑_{i≠0,k} p_{i}

Inequality (19) implies η ≥ κ. Moreover if z_{d−k} ≠ −κ, then we have the strict inequality:

κp_{0} < κ|p_{k}| + η ∑_{i≠k} p_{i}

which implies η > κ. The remaining case is that z_{d} = z_{d−k} = −κ. If there is some ℓ > 0 such that z_{d−kℓ} ≠ −κ, then by shifting indices, we may assume z_{d} = −κ ≠ z_{d−k} and η > κ follows. If z_{d−kℓ} = −κ for all ℓ = 0, 1, 2, …, using the left side of (18), we have

κ(p_{0} + p_{k} + ⋯ + p_{k[ \frac{d}{k}]}) ≤ η ∑_{k∤i}|p_{i}| < η ∑_{i=1}^{d} |p_{i}| ≤ ηp_{0}.

Hence κ < η by the assumption ∑_{1≤ki≤d} p_{ki} ≥ 0. So our claim is proved.

Our next aim is to show z_{j} = η implies z_{j+kℓ} = η for all ℓ ∈ ℤ. Without loss of generality, we may assume z_{d} = η. If z_{d−k} ≠ η, then by the right side of (18),

p_{0} > z_{0}p_{d} + z_{1}p_{d−1} + ⋯ + z_{d−1}p_{1} + z_{d}p_{0}
≥ −κ ∑_{1≤i≤d^{i≠0, k}} |p_{i}| − (η − 1)|p_{k}| + ηp_{0}

≥ p_{0} + (η − 1)(p_{0} − ∑_{1≤i≤d} p_{i})
≥ p_{0}.

This is a contradiction. So z_{d+kℓ} = η for all ℓ ∈ ℤ. Now (18) become

p_{0} > z_{0}p_{d} + z_{1}p_{d−1} + ⋯ + z_{d−1}p_{1} + z_{d}p_{0}
≥ −κ ∑_{k∤i}|p_{i}| + η ∑_{i≠0^{k|i}} p_{k} + ηp_{0}.

By the assumption ∑_{i≠0^{k|i}} p_{i} ≥ 0, we see κ > 0. Moreover

κ ∑_{k∤i}|p_{i}| > (η − 1)p_{0}.

This shows

∑_{1≤i≤d} |p_{i}| > ∑_{k∤i^{1≤i≤d}}|p_{i}| > p_{0},

which is a desired contradiction. □

Classification of quadratic CNS polynomials x^{2} + p_{1}x + p_{0} was already done by [9], [10], [5] and [16] in several ways. We reprove this result as an application of our discussion.

Corollary 3.6. Let P (x) = x^{2} + p_{1}x + p_{0} be a quadratic polynomial. Then P (x) is a CNS polynomial if and only if −1 ≤ p_{1} ≤ p_{0} and p_{0} ≥ 2.

Proof. If P (x) is a CNS polynomial, then p_{0} ≥ 2 by (2). Since there are no roots in [−1, 0], we have P (−1) > 0 which shows p_{1} ≤ p_{0} and 1-subsum condition implies −1 ≤ p_{1}.

Conversely if −1 ≤ p_{1} ≤ p_{0} and p_{0} ≥ 2 then P (x) must be expanding. If p_{1} < p_{0}, then Theorem 3.2 implies that P (x) is a CNS polynomial as coefficients satisfy the dominant condition. The remaining case p_{1} = p_{0} is settled down by (3), a result of B.Kovács. □

For an expanding polynomial P (x), (7) gives an algorithmic bound of the set P. If P (x) satisfies dominant condition, we can get a bound in another way. Theorem 3.7 is an improvement of Theorem 1 of S.Akiyama and A.Pethő [3], giving such a bound of P. ^{2}

Theorem 3.7. Assume |p_{0}| > ∑_{i=1}^{d} |p_{i}| and ξ = ∑_{i=1}^{d} w_{i}z_{i} ∈ P. Then we have

|z_{i} − \frac{p_{0}}{2 ∑_{i=0}^{d} p_{i}} | ≤ \frac{|p_{0}|}{2 (|p_{0}| − ∑_{i=1}^{d} |p_{i}|)}.

Proof. First we prove the case p_{0} > 0. Putting τ = \frac{p_{0}}{2(∑_{i=0}^{d} p_{i})}, by (13), we have

−\frac{p_{0}}{2} ≤ ∑(z_{i+j} − τ)p_{d−j} < \frac{p_{0}}{2} .

Let η = max_{i∈ℤ} |z_{i} − τ| and choose i such that η = |z_{i+d} − τ|. If z_{i+d} − τ = −η then

η (|p_{d}| + |p_{d−1}| + ⋯ + |p_{1}|) ≥ (η − \frac{1}{2}) p_{0}.

If z_{i+d} − τ = η then

−η (|p_{d}| + |p_{d−1}| + ⋯ + |p_{1}|) < (\frac{1}{2} − η) p_{0}.

Thus in any case, we have

η ∑_{i=1}^{d} |p_{i}| ≥ (η − \frac{1}{2}) p_{0}
η ≤ \frac{p_{0}}{2 (p_{0} − ∑_{i=1}^{d} |p_{i}|)},

which shows our assertion.

Now we wish to show the case p_{0} < 0. For the moment, we permit negative leading coefficient p_{d} = −1 and substitute P (x) by −P (x) to make p_{0} > 0 and p_{d} = −1. Then we easily see that Proposition 3.1 remains true in the same notation. Thus the above proof also works for the case p_{0} < 0. □

2Though it is not explicitly mentioned, the bound of Theorem 1 of [3] is nothing but the bound for P. This fact is easily seen from its proof. Note that we do not assume p_{0} > 0.

4. Some remarks on H. Brunotte’s result

H. Brunotte [4] found an interesting algorithm to determine a polynomial is a CNS polynomial or not. The original proof is not so easy. Recently K. Scheicher & J.M.Thuswaldner [15] gave a simple proof of a similar result by using finite automata. In this section, we give another proof of Brunotte’s Lemma based on the techniques of Section 3. The idea is inspired by [15]. Beside of this, we give several remarks on Brunotte’s algorithm.

Let us define

σ^{∗}(z_{1}, …, z_{d}) = −σ(−z_{1}, −z_{2}, …, −z_{d}),

where σ is defined as in Section 3. As it is seen that σ^{∗}(z_{1}, …, z_{d}) = σ(z_{1} + p_{0} − 1, z_{2}, …, z_{d}). Lemma 2 of [4] reads

Lemma 4.1. Let P (x) be a monic polynomial of degree d with p_{0} ≥ 2. If there is a set E ⊂ ℤ^{d} satisfying the following properties, then P (x) is a CNS polynomial.

3

(i) (0, …, 0), (−1, 0, …, 0), (1, 0, …, 0) ∈ E (ii) (σ(E) ∪ σ^{∗}(E)) ⊆ E. (iii) For any x ∈ E, there exist a positive integer M such that σ^{M}(x) = 0.

Proof. Again let α = x mod P (x). Suppose ξ ∈ R has a canonical expansion and η ∈ ι(E), we argue that ξ + η also has a canonical expansion. Suppose

T (ξ) = \frac{ξ − k_{1}}{α} , T (η) = \frac{η − k_{2}}{α} ,

where k_{1}, k_{2} ∈ {0, 1, ⋯, p_{0} − 1}. If k_{1} + k_{2} < p_{0}, then

T (ξ + η) = \frac{ξ + η − (k_{1} + k_{2})}{α} = T (ξ) + T (η).

If k_{1} + k_{2} ≥ p_{0}, then k_{2} > 0 and

T (−η) = \frac{−η − (p_{0} − k_{2})}{α}.

So we have

T (ξ + η) = \frac{ξ + η − (k_{1} + k_{2}) + p_{0}}{α} = T (ξ) − T (−η).

By the assumption (ii),

−T (−η) = −ι(σ(ι^{−1}(−η))) = ι(σ^{∗}(ι^{−1}(η))) ∈ ι(E).

Repeat this argument, we have for any n,

T^{n}(ξ + η) = T^{n}(ξ) + η^{∗}
(0, …, 0), (−1, 0, …, 0), (0, …, 0, −1) ∈ E.

3There is a minor difference between (i) and the corresponding assumption of Lemma 2 in [4], which is

for some η^{∗} ∈ ι(E). Since ξ has a canonical expansion, so T^{n}(ξ + η) ∈ ι(E) for a large n. Now from assumption (iii), we conclude that ξ + η has a canonical expansion.

As ±1 ∈ ι(E) is seen by the assumption (i), ξ has a canonical expansion implies ξ ± 1 have canonical expansions. Note that ξ has canonical expansion implies αξ has a canonical expansion. Since every element of ℤ(x) can be obtain from 0 by these two operations, so every element of R has a canonical expansion. □

This Lemma 4.1 gives a handy way to determine whether P (x) is a CNS polynomial or not.

(a): Let E_{1} = {(0, …, 0), (−1, 0, …, 0), (1, 0, …, 0)}.

(b): If E_{i} is defined for i < n, then E_{n} is defined by E_{n} = E_{n−1} ∪ σ(E_{n−1}) ∪

σ^{∗}(E_{n−1}). (c): If E_{n} ≠ E_{n−1} then continue this emerging process (b). If E_{n} = E_{n−1}

then we proceed to the next step (d). (d): For each element x of E_{n}, we confirm that there exists M such that

T^{M}(x) = 0. Note that E_{n} = −E_{n} for any n. When P (x) is an expanding polynomial, the

last process (d) will terminate in finite steps since the sequence {T^{i}(x)}_{i=0,1,2,...} is eventually periodic by Proposition 2.1.

Further it is important to point out that the above emerging process (b) also terminate in finite steps. Indeed, as P (x) expanding, we know that both σ and σ^{∗} are eventually contractive. So the sets E_{n} (n = 1, 2, …) must be uniformly bounded. By the discreteness of ℤ^{d} in ℝ^{d} and E_{n} ⊃ E_{n−1} we conclude that the process (b) will certainly stop. Especially, if P (x) is separable then we can give a concrete bound of the sets E_{n}.

Theorem 4.2. If P (x) is an expanding separable polynomial. Let

W = \{ξ ∈ R | |ξ(θ)| ≤ \frac{|p_{0}| − 1}{|θ| − 1} for all root θ of P (x)\} .

Then we have E_{n} ⊂ ι(W) for all n.

Proof. Let us go back to the representation in base {1, α, …, α^{d−1}} and consider the action of T and define T^{∗}(ξ) = −T (−ξ). As P (x) is expanding, E_{1} ⊂ ι(W) is clear. It suffices to show T (W) ∪ T^{∗}(W) ⊂ W. Indeed, it is equivalent to σ(ι(W)) ∪ σ^{∗}(ι(W)) ⊂ ι(W), and so we have σ(E_{n}) ∪ σ^{∗}(E_{n}) ⊂ ι(W) provided E_{n} ⊂ ι(W).

One can easily see that T (ξ) = (ξ −k_{1})/α and T^{∗}(ξ) = (ξ −k_{2})/α with k_{1}, k_{2} ∈ [−p_{0}+1, p_{0}−1]. Let θ be a root of P (x). Then we see that T (ξ(θ)) = (ξ(θ)−k_{1})/θ and T_{1}(ξ(θ)) = (ξ(θ)−k_{2})/θ. Put K(θ) = (|p_{0}|−1)/(|θ|−1). Then |ξ(θ)| ≤ K(θ) implies

|\frac{ξ(θ) − k_{1}}{θ} | ≤ \frac{K(θ) + p_{0} − 1}{|θ|} = K(θ),

showing |T (ξ(θ))| ≤ K(θ) and also |T_{1}(ξ(θ))| ≤ K(θ). This shows T (W) ∪ T^{∗}(W) ⊂ W. □

Thus we have another algorithm to determine whether an polynomial is CNS. This bound W in Theorem 4.2 is the same as (7). Thus this algorithm can not be worse than the one in [12]. If we have a dominant condition as before, then we can say more.

Theorem 4.3. Let P (x) be a monic polynomial with dominant condition p_{0} ≥ ∑_{i=1}^{d} |p_{i}|. Then P (x) is a CNS polynomial if and only if every element of

S = {ξ ∈ R | ξ = ∑_{i=1}^{d} z_{i}w_{i} and |z_{i}| ≤ 1}

has a canonical expression.

Proof. We need only show that the condition is sufficient. Let

S′ = {(z_{1}, …, z_{d}) | z_{i} ∈ {−1, 0, 1}}.

Then S′ fulfills the property (i) of Lemma 4.1. Under dominant condition, it is easy to check that S′ satisfies the property (ii). The assumption on S implies that S′ satisfies the property (iii). Hence P (x) is a CNS polynomial. □

Corollary 4.4. Let P (x) be a monic polynomial satisfying p_{0} > ∑_{i=1}^{d} |p_{i}|. Then P (x) is a CNS polynomial if and only if every element of

{ξ ∈ R | ξ = ∑_{i=1}^{d} z_{i}w_{i} and z_{i} = 0, 1}

has a canonical expression.

Proof. Let S′ be the set defined in Theorem 4.3. Pick any (z_{1}, …, z_{d}) ∈ S′, it define a infinite word (z_{1}, …, z_{d}, z_{d+1}, …). The dominant condition p_{0} > ∑_{i=1}^{d} |p_{i}| implies that d_{i} ∈ {0, 1} for any i > d. Hence there is an integer M > 0 such that σ^{M}(z_{1}, …, z_{d}) = (0, …, 0). Hence P (x) is a CNS polynomial by Lemma 4.1. □

5. Characterizations of CNS polynomials with a dominant condition

This section is inspired by the recent work by K. Scheicher & J.M.Thuswaldner [15]. We shall give some simple necessary and sufficient conditions of CNS polynomial of degree 3, 4 and 5 under the dominant condition p_{0} ≥ ∑_{i=1}^{d} |p_{i}|.

Theorem 3 in S. Akiyama & A. Pethő [3] says that

(20)  p_{ℓ} + ∑_{k=ℓ+1}^{d} |p_{k}| ≥ 0

is a necessary condition for CNS polynomials with p_{0} ≥ ∑_{i=1}^{d} |p_{i}|. The same idea allows us to show a slightly stronger assertion under the dominant condition (4). Namely, if P (x) is a CNS polynomial then

p_{ℓ} + ∑_{p_{k}>0^{k=ℓ+1}}^{d} p_{k} ≥ 0

under (4). To show it, only thing to check is that there are no case ε_{j} = −1 under their notation in [3]. An analogous method allows us to show ^{4}

Lemma 5.1. If P (x) is a CNS polynomial satisfying p_{0} ≥ ∑_{i=1}^{d} |p_{i}| , then 1 + p_{d−1} + p_{d−2} ≥ 0.

Proof. If d = 2, then 1 + p_{d−1} + p_{d−2} ≥ 0 is clear. Thus we show the case d > 2. Assume that 1+p_{d−1}+p_{d−2} < 0 and P (x) is a CNS polynomial. Since 1+p_{d−1} ≥ 0 by (20), we have p_{d−2} < 0. If p_{d−1} ≥ 0 then |p_{d}| + |p_{d−1}| + p_{d−2} < 0 gives a contradiction again by (20). Thus we see that p_{d−1} = −1 and p_{d−2} < 0 holds. Put T^{m}(x) = ∑_{i=0}^{d−1} T_{i}^{m}(x)α^{j} for x ∈ R. Reviewing the definition of the basis {w_{i}}, we have w_{j} = ∑_{k=0}^{j−1} p_{d+1+k−j}α^{k}. Using this we have T_{i}^{m}(x) = ∑_{j=i}^{d−1} z_{j+m+1}p_{d+i−j} with z_{j} ∈ ℤ defined at the beginning of §3. Now we specify x = −1 and define an integer sequence {z_{i}}_{i=1}^{∞}. By using (5), it is easily seen that z_{i} ∈ {0, ±1}. Our aim is to show that for any non-negative integer m, there exist j that T_{j}^{m}(−1) < 0 which proves that P (x) is not a CNS polynomial. This is obviously true when m = 0. If T_{0}^{m−1}(−1) ≥ 0 then it is shown, similarly as in Theorem 3 in [3], that there exist j that T_{j}^{m}(−1) < 0. Let us assume that T_{0}^{m−1}(−1) < 0. By (5), we have z_{m+d} = 1. If z_{m+d−1} ≤ 0 then,

T_{d−2}^{m}(−1) = z_{m+d−1} − z_{m+d} < 0.

If z_{m+d−1} > 0 then,

T_{d−3}^{m}(−1) = z_{m+d−2} − z_{m+d−1} + z_{m+d}p_{d−2} ≤ 1 − 1 + p_{d−2} < 0.

Thus we have shown the Lemma. □

Here it may be convenient to summarize necessary conditions for CNS polynomials with (5).

Theorem 5.2. Let P (x) be an expanding polynomial with the dominant condition (5). Then P (x) is a CNS implies

(a) 1 + p_{d−1} ≥ 0;

(b) 1 + p_{d−1} + p_{d−2} ≥ 0;

(c) ∑_{i=1}^{d} p_{d} ≥ 0;

x^{10} − x^{9} + x^{8} − 2x^{7} + 4x^{6} + 4x^{5} + 4x^{4} − 3x^{3} − x^{2} + 20

4One might hope that ∑_{k=ℓ}^{d} p_{k} ≥ 0 for any ℓ = 1, 2, …, d − 1 are necessary for a CNS polynomial P (x). Unfortunately this is not the case. A counter example is given that is a CNS polynomial but p_{d} + p_{d−1} + p_{d−2} + p_{d−3} < 0.

(d) ∑_{2|i,1≤i≤d} p_{d} ≥ 0.

Proof. Lemma 5.1 and (20) imply (a) and (b). Condition (c) follows from 1subsum condition. We need only prove (d). Suppose not, than by (c), we know ∑_{2∤i,1≤i≤d} p_{d} ≥ 0. By using (5), P (x) is not a CNS polynomial since it does not satisfy 2-subsum condition. □

Theorem 5.3. Let P (x) = x^{3} + p_{2}x^{2} + p_{1}x + p_{0} be a polynomial in ℤ[x] with p_{0} > 1 + |p_{2}| + |p_{1}|. Then P (x) is a CNS polynomial if and only if p_{2} ≥ 0 and 1 + p_{2} + p_{1} ≥ 0.

Proof. Assume that P (x) is a CNS polynomial. Then Theorem 5.2 (b) or (c) implies 1 + p_{2} + p_{1} ≥ 0 and (d) gives p_{2} ≥ 0. (These facts were shown in a different way in Proposition 1 of [3].) The sufficiency follows from Theorem 3.2. □

Theorem 5.4. Let P (x) = x^{4} + p_{3}x^{3} + p_{2}x^{2} + p_{1}x + p_{0} be a polynomial in ℤ[x] with p_{0} > 1 + |p_{3}| + |p_{2}| + |p_{1}|. Then P (x) is a CNS polynomial if and only if five conditions:

p_{3} ≥ −1
p_{2} ≥ −1
p_{3} + p_{2} ≥ −1
1 + p_{3} + p_{2} + p_{1} ≥ 0
p_{3} = −1 ⇒ p_{1} ≤ −2

holds.

Proof. Assume that P (x) is a CNS polynomial. Theorem 5.2 says the first four conditions are necessary. Let p_{3} = −1. Then 1 + p_{3} + p_{2} ≥ 0 implies p_{2} ≥ 0. Let us consider the 3-subsum condition. As p_{3} + p_{0} and p_{2} are in [0, p_{0} − 1] ∩ ℤ, we see 1 + p_{1} must be negative.

Now we wish to show the sufficiency. Note that 1 + p_{3} + p_{2} ≥ 0 shows that not both p_{2} and p_{3} are negative. First we consider the case p_{3} = −1. Then p_{1} ≤ −2 and p_{2} ≥ 2. The proof is done by writing a directed graph consist of 2^{4} = 16 vertices formed by (z_{i}, z_{i+1}, z_{i+2}, z_{i+3}) with z_{i} ∈ {0, 1}. Each vertex (z_{i}, z_{i+1}, z_{i+2}, z_{i+3}) represents an element of

{ξ ∈ R | ξ = ∑_{i=1}^{4} z_{i}w_{i} and z_{i} = 0, 1}

which forms a test set in Corollary 4.4. We write a directed edge from (z_{i}, z_{i+1}, z_{i+2}, z_{i+3}) to (z_{i+1}, z_{i+2}, z_{i+3}, z_{i+4}) if there is a possibility that

σ(z_{i}, z_{i+1}, z_{i+2}, z_{i+3}) = (z_{i+1}, z_{i+2}, z_{i+3}, z_{i+4})

under these five conditions. This was done in Figure 1. Here we omit a self loop from (0, …, 0) to itself. As this graph forms a directed tree having an only

[figure: 1010; 0010; 0100; 0001; 1001; 0101; 1101; 0111; 0011; 1011; 1111; 1110; 0110; 1100; 1000; 0000]

Figure 1. p_{3} = −1, Quartic case

[figure: 1001; 0001; 0010; 0011; 1011; 0101; 0111; 1101; 1111; 1010; 1110; 0110; 0100; 1100; 1000; 0000]
Figure 2. p_{2} = −1, p_{1} < 0, Quartic case

terminal vertex (0, 0, 0, 0), we have completed the case p_{3} = −1. Second we treat the case p_{3} ≥ 0 and p_{2} = −1. If p_{1} ≥ 0, then as 1+p_{2} ≥ 0 we can apply Theorem 3.5 to show that P (x) is a CNS polynomial. Let p_{1} ≤ −1. As 1+p_{3} +p_{2} +p_{1} ≥ 0, we have p_{3} ≥ 1 and p_{3} + p_{1} ≥ 0. Figure 2 gives a similar directed graph showing that P (x) is a CNS polynomial.

Finally if p_{3} ≥ 0 and p_{2} ≥ 0 then as 1 + p_{3} + p_{2} + p_{1} ≥ 0 we can apply Theorem 3.2 to see that P (x) is a CNS polynomial. Thus we have shown the assertion. □

Remark 5.5. Proofs of Theorem 5.3 and 5.4 shows that CNS polynomial with a dominant condition (4) is completely characterized by the known necessary conditions: k-subsum condition, (20) and Lemma 5.1 provided the degree of the polynomial is less than 5.

Theorem 5.6. Let P (x) = x^{5} + p_{4}x^{4} + p_{3}x^{3} + p_{2}x^{2} + p_{1}x + p_{0} be a polynomial in ℤ[x] with p_{0} > 1 + |p_{4}| + |p_{3}| + |p_{2}| + |p_{1}|. Then P (x) is a CNS polynomial if and only if five conditions:

p_{2} + p_{4} ≥ 0
1 + p_{4} + p_{3} + p_{2} + p_{1} ≥ 0
p_{4} < 0 ⇒ p_{4} = −1, p_{3} ≥ 1, p_{1} ≤ −2
p_{3} < 0, p_{1} + p_{4} ≥ 0 ⇒ p_{3} ≥ −1, p_{2} ≤ −2
p_{3} < 0, p_{1} + p_{4} < 0 ⇒ p_{4} ≥ 0, p_{4} + p_{3} ≥ 0

holds.

Proof. Assume that P (x) is a CNS polynomial. First two conditions are shown in Theorem 5.2. Assume that p_{4} < 0. In this case we see by 1 + p_{4} ≥ 0 and 1 + p_{4} + p_{3} ≥ 0 that p_{4} = −1 and p_{3} ≥ 0. p_{2} + p_{4} ≥ 0 shows p_{2} ≥ 1. Using 4-subsum condition, 1 + p_{1} must be negative. Further we can show that p_{3} ≥ 1. For if p_{3} = 0 then 1-subsum condition implies p_{2} + p_{1} ≥ 0 and so we can confirm that

Ξ = (0011)^{∞}

gives an element of P. Thus we have shown that third necessary condition of Theorem 5.6.

Next consider the case p_{3} < 0. As stated above, we have p_{4} ≥ 0. Further assume that p_{1} + p_{4} ≥ 0. By 3-subsum condition, 1 + p_{2} < 0. It is also seen that p_{3} ≥ −1. For if p_{3} ≤ −2 then we can construct a bi-infinite word

Ξ = \begin{cases}(01001)^{∞} & p_{3} + p_{1} ≥ 0 \\ (01001011)^{∞} & p_{3} + p_{1} < 0 \end{cases}

which corresponds to an element of P. This shows the 4-th necessary condition. Assume that p_{3} < 0 and p_{1} + p_{4} < 0. If p_{4} + p_{3} < 0 then we see that

Ξ = \begin{cases}(1001100)^{∞} & 1 + p_{4} + p_{1} ≥ 0 \\ (1001)^{∞} & 1 + p_{4} + p_{1} < 0 \end{cases}

is a corresponding word of a non zero element of P. Thus we have proved five necessary conditions.

We now prove the sufficiency. First note that p_{4} or p_{3} can not be an isolated negative coefficient by the claim before Theorem 3.5. Since 1+p_{4}+p_{3}+p_{2}+p_{1} ≥ 0 and p_{2} + p_{4} ≥ 0 are already assumed, Theorem 3.2 and 3.5 can be applied when there are at most one negative coefficient. Thus we only need to show the sufficiency in the case that there are at least two negative coefficients. In such 4 subcases, we can write down similar directed graphs used in the proof of Theorem 5.4:

(1): p_{4} = −1

(2): p_{3} < 0 and p_{1} + p_{4} ≥ 0 (3): p_{3} < 0 and p_{1} + p_{4} < 0 (4): p_{4} ≥ 0, p_{3} ≥ 0, p_{1} < 0 and p_{2} < 0

In fact, the case (1) is done in Figure 3. In the case (2), it is easy to confirm a directed graph of Figure 4. Here we performed out-going amalgamation for some vertices on the original graphs to simplify them. This means that if two vertices v_{1}, v_{2} have exactly the same follower vertices then such vertices are unified into one vertex (v_{1}, v_{2}) in their graph expression. Last two cases are also completed easily. We left these cases to the reader.

□

Remark 5.7. Theorem 5.6 is restated as follows under the same condition. The polynomial P (x) is a CNS polynomial if and only if it satisfies k-subsum condition (for k = 1, 2, 3, 4), p_{4} ≥ −1, p_{3} + p_{4} ≥ 0 and

p_{1} + p_{4} ≥ 0 ⇒ p_{3} ≥ −1.

To show this, we need only to review the above proof that all five conditions in Theorem 5.6 is derived by these conditions.

Note that last two conditions are not seen by combining k-subsum conditions,

(20) and Lemma 5.1. Thus unfortunately, known necessary conditions on CNS are not enough to characterize CNS polynomials of degree 5.

Remark 5.8. Let us fix a positive integer d and consider expanding polynomials of degree d under the dominant condition (4). We may say that Corollary 4.4 provides an algorithm to describe all such CNS polynomials. However it seems impractical to accomplish it for a large degree.

Indeed, possible lengths of periods of P are not larger than 2^{d}. So we can characterize polynomials which admits non zero periodic words Ξ by finite sets of inequalities. Thus solving all these inequalities, we can describe the set of all CNS polynomials by ruling out such family of non CNS polynomials.

References

[1] S. Akiyama, On the boundary of the tiling generated by Pisot numbers, Journal of Math. Soc. Japan, 54 no. 2 (2002) 283-308.

[2] S. Akiyama and J.M.Thuswaldner, Topological properties of two-dimensional number systems, Journal de Théorie des Nombres de Bordeaux 12 (2000) 69–79.

[3] S. Akiyama and A. Pethő, On canonical number systems, Theoretical Computer Science, 270 (2002) 921-933.

[4] H. Brunotte, On trinomial basis of Radix Representations of Algebraic Integers. to appear in Acta Sci. Math. (Szeged) 67 (2001) 407–413.

[figure: \binom{10101}{00101}; \binom{11101}{01101}; \binom{10010}{00010}; \binom{11010}{01010}; \binom{01011}{11011}; 10110; 10111; 00100; 10100; 01000; 00001; 10001; \binom{01001}{11001}; \binom{00011}{10011}; 00111; 00110; 01100; 01111; 11111; 01110; 11110; 11100; 11000; 10000; 00000]

Figure 3. p_{4} = −1, degree 5

[5] W.J.Gilbert, Radix representations of quadratic number fields, J. Math. Anal. Appl. 83 (1981) 263–274.

[6] M. Hollander, Linear Numeration systems, Finite Beta Expansions, and Discrete Spectrum of Substitution Dynamical Systems, Doctorial thesis for Washington Univ.

[7] I. Kátai and J. Szabó, Canonical number systems for complex integers, Acta Sci. Math. (Szeged) 37 (1975) 255–260.

[8] I. Kátai and I. Kőrnyei, On number systems in algebraic number fields, Publ. Math. Debrecen 41 no. 3–4 (1992) 289–294.

[9] I. Kátai and B. Kovács, Canonical number systems in imaginary quadratic fields, Acta Math. Hungar. 37 (1981) 159–164.

[figure: 00100; \binom{11001}{01001}; \binom{10001}{00001}; 10010; 00010; \binom{00011}{10011}; \binom{10101}{00101}; 00110; \binom{00111}{10111}; 01010; \binom{01011}{11011}; 01111; 10110; 11111; \binom{01110}{11110}; 01101; 11101; 11010; 11100; 01100; 10100; 11000; 01000; 10000; 00000]

Figure 4. p_{4} ≥ 0, p_{3} < 0, p_{1} + p_{4} ≥ 0, degree 5

[10] I. Kátai and B. Kovács, Kanonische Zahlensysteme in der Theorie der quadratischen Zahlen, Acta Sci. Math. (Szeged) 42 (1980) 99–107.

[11] B. Kovács, Canonical number systems in algebraic number fields, Acta Math. Acad. Sci. Hungar. 37 (1981), 405–407.

[12] B. Kovács and A. Pethő, Number systems in integral domains, especially in orders of algebraic number fields, Acta Sci. Math. Szeged, 55 (1991) 287–299.

[13] A. Pethő, On a polynomial transformation and its application to the construction of a public key cryptosystem, Computational Number Theory, Proc., Walter de Gruyter Publ. Comp. Eds.: A. Pethő, M. Pohst, H.G. Zimmer and H.C. Williams, 1991, pp 31-44.

[14] K. Scheicher, Kanonische Ziffernsysteme und Automaten, Grazer Math. Ber., 333 (1997), 1–17.

[15] K. Scheicher and J.M.Thuswaldner, On the characterization of Canonical number system, to appear in Osaka J. Math.

[16] J.M.Thuswaldner, Elementary properties of canonical number systems in quadratic fields, in: Applications of Fibonacci numbers Vol. 7, (Graz, 1996), 405–414, Kluwer Acad. Publ., Dordrecht, 1998.

Shigeki Akiyama Department of Mathematics, Faculty of Science, Niigata University, Ikarashi 2-8050, Niigata 950-2181, Japan e-mail: akiyama@math.sc.niigata-u.ac.jp

Hui Rao Department of Mathematics, Faculty of Science, Wuhan University, 430072, Wuhan, P.R. China e-mail: myhacone@yahoo.com