On canonical number systems

Shigeki Akiyama and Attila Pethő^{∗}

1 Introduction

Let P (x) = p_{d}x^{d} + … + p_{0} ∈ ℤ[x] be such that, d ≥ 1 and p_{d} = 1. Let R denote the quotient ring ℤ[x]/P (x)ℤ[x]. Then all α ∈ R can be represented in the form

α = a_{0} + a_{1}x + … + a_{d−1}x^{d−1}

with a_{i} ∈ ℤ, i = 0, …, d − 1.

The pair {P (x), N } with N = {0, 1, …, |p_{0}| − 1} is called canonical number system, CNS if every α ∈ R, α ≠ 0 can be written uniquely in the form

α = ∑_{j=0}^{ℓ(α)} a_{j}x^{j},  (1)

where a_{j} ∈ N , j = 0, …, ℓ(α), a_{ℓ(α)} ≠ 0.

If P (x) is irreducible, then let γ denote one of its zeros. In this case ℤ[x]/P (x)ℤ[x] is isomorphic to ℤ[γ], the minimal ring generated by γ and ℤ, hence we may replace x to γ in the above expansions. Moreover N forms a complete representative system mod γ in ℤ[γ]. We simplify in this case the notation {P (x), N } to {γ, N }.

Extending the results of [6] and [2], I. Kátai and B. Kovács classified all quadratic CNS, provided the corresponding P (x) is irreducible. B. Kovács [7] proved that in any algebraic number field there exists an element γ such that {γ, N } is a CNS ^{1} . J. Thuswaldner [12] gave in the quadratic and K. Scheicher [11] in the general case a new proof of the above theorems based on automaton theory. B. Kovács [7] proved further that if p_{d} ≤ p_{d−1} ≤ p_{d−2} ≤ … ≤ p_{0}, p_{0} ≥ 2, and if P (x) is irreducible and γ is a zero of P (x) then {γ, N } is a CNS in ℤ[γ]. In [8] B. Kovács and A. Pethő gave also a characterization of those irreducible polynomials P (x), whose zeros are bases of CNS.

Interesting connections between CNS and fractal tilings of the Euclidean space were discussed by several mathematicians. D.E. Knuth [6] seems to be the first finder of this phenomenon in case x = −1 + \sqrt{−1}. For the recent results on this topic, the reader can consult [3] or [1] and their references.

∗Research supported in part by the Hungarian Foundation for Scientific Research, Grant N0. 25157/98.

1 We need a slight explanation of their results, since their definition of canonical number system is more restricted than ours. In fact, they assumed still more that ℤ[γ] coincides with the integer ring of ℚ(γ), the field generated by γ over the field of rational numbers.

The concept of CNS was generalized to arbitrary polynomials with leading coefficient one by the second author [10]. He extended most of the results of [7] and [8] and proved among others that if {P (x), N } is a CNS then all real zeroes of P (x) are less then −1 and the absolute value of all the complex roots are larger then 1. This implies that if {P (x), N } is a CNS then p_{0} > 0, which we will assume throughout this paper.^{2}

The aim of the present paper is to give a new characterization of CNS provided p_{0} is large enough. It enables us to prove for a large class of polynomials that their zeros together with the corresponding set N consist a CNS. Unfortunately our criterion in Theorem 1 cannot be adapted to polynomials with small p_{0}, but it suggests us that the characterization problem of CNS is relevant not to the corresponding field structure, such as fundamental units, ramifications or discriminants, but only to the coefficients of defining polynomials.

2 Notations and results

For a polynomial P (x) = p_{d}x^{d} + … + p_{0} ∈ ℤ[x], let

L(P) = ∑_{i=1}^{d} |p_{i}|,

which we call the length of P. Every α ∈ R = ℤ[x]/P (x)ℤ[x] has a unique representation in the form

α = ∑_{j=0}^{d−1} a_{j}x^{j}.

Put q = [\frac{a_{0}}{p_{0}} ] , where [ ] denotes the integer part function. Let us define the map T : R → R by

T (α) = ∑_{j=0}^{d−1}(a_{j+1} − qp_{j+1})x^{j},

where a_{d} = 0.. Putting

T^{(0)}(α) = α and T^{(i+1)}(α) = T (T^{(i)}(α))

we define the iterates of T. As T^{(i)}(α) ∈ R for all non-negative integers i, and α ∈ R, the element T^{(i)}(α) can be represented with integer coefficients in the basis 1, x, …, x^{d−1}. The coefficients of this representation will be denoted by T_{j}^{(i)}(α), i ≥ 0, 0 ≤ j ≤ d − 1. It is sometimes convenient to extend this definition by putting T_{j}^{(i)}(α) = 0 for j ≥ d. This map T obviously describes the algorithm to express any α ∈ R in a form (1) since we have

α = ∑_{j=0}^{ℓ(α)} [\frac{T_{0}^{(j)}(α)}{p_{0}} ] x^{j},

2 In Theorem 6.1 of [10] it is assumed that g(t) is square-free, but this assumption is necessary only for the proof of (iii).

when {P (x), N } is a CNS. With this notation we have

α = ∑_{j=0}^{d−1} T_{j}^{(0)}(α)x^{j},

and

T^{(i)}(α) = ∑_{j=0}^{d−1} T_{j}^{(i)}(α)x^{j},  (2)

= ∑_{j=0}^{d−1}(T_{j+1}^{(i−1)}(α) − q_{i−1}p_{j+1})x^{j}  (3)

where q_{i−1} = [\frac{T_{0}^{(i−1)}(α)}{p_{0}} ] for i ≥ 1.

For α ∈ R let

L(α) = ∑_{j=0}^{d−1} |T_{j}^{(0)}(α)| and h(α) = max {|T_{j}^{(0)}(α)| , 0 ≤ j ≤ d − 1}

denote the length and the height of α respectively.

After this preparation we are in the position to formulate our results. The first assertion is a new characterization of CNS provided p_{0} > L(P). By Lemma 1 in §3, the roots of such a P have moduli greater than 1, which is a necessary condition for a CNS. So we are interested in such a class of polynomials. The spirit of Theorem 1 below and Theorems 3 of [8] and 6.1 of [10] is the same: it is proved that {P (x), N } is a CNS in R if and only if every element of bounded size of R is representable in {P (x), N }. The difference is in the choice of the size. Kovács and Pethő used the height, we however use the weight, defined by (13) in §4.

Theorem 1 Let M be a positive integer. Assume p_{0} ≥ (1 + 1/M)L(P) if p_{i} ≠ 0 for i = 1, ⋯, d − 1 and p_{0} > (1 + 1/M)L(P) otherwise. The pair {P (x), N } is a CNS in R if and only if all α ∈ R:

α = ∑_{i=0}^{d−1} (∑_{j=i}^{d−1} ε_{j}p_{d+i−j}) x^{i}  (4)

with ε_{j} ∈ [1 − M, M] ∩ ℤ (0 ≤ j ≤ d − 1) have a representation in {P (x), N }.

Our algorithm is more easy and suitable for handy calculation than the one in [8] and [10], since we do not need any information on the roots of P. We need only to confirm whether (2M)^{d} elements have representations in {P (x), N } or not. Running time estimate for the method of [8] is difficult, since it depends on the distribution of the roots of P. But in many cases, our method is very rapid when p_{0} or d is large.

Example 1 We compare the number of elements needed to be in {P (x), N } by two algorithms for three CNS polynomials.

Case x^{3} + x^{2} + 5.

(Our algorithm) 8 elements (M=1)

(K.P. algorithm) 89 elements

Case x^{3} + 2x^{2} − x + 7

(Our algorithm) 64 elements (M=2)

(K.P. algorithm) 123 elements

Case x^{4} + x^{3} − x^{2} + x + 8

(Our algorithm) 16 elements (M=1)

(K.P. algorithm) 1427 elements

Using Theorem 1 we are able to prove that a wide class of polynomials correspond to a CNS. Similar results were proven in [7] and in [10]. Using the idea of B. Kovács [7] it was proved in [10] that if 0 < p_{d−1} ≤ … ≤ p_{0}, p_{0} ≥ 2 then {P (x), N } is a CNS. We however do not assume the monotonicity of the sequence of the coefficients. Moreover p_{1} is allowed to be negative.

Theorem 2 Assume that p_{2}, …, p_{d−1}, ∑_{i=1}^{d} p_{i} ≥ 0 and p_{0} > 2 ∑_{i=1}^{d} |p_{i}| Then {P (x), N } is a CNS in R. The last inequality can be replaced by p_{0} ≥ 2 ∑_{i=1}^{d} |p_{i}| when all p_{i} ≠ 0.

Note that the conditions p_{2}, …, p_{d−1}, ∑_{i=1}^{d} p_{i} ≥ 0 are necessary if d = 3 by Proposition 1 in §3. So Theorem 2 gives us a characterization of all cubic CNS provided p_{0} > 2L(P). Generally, the inequality ∑_{i=1}^{d} p_{i} ≥ 0 is by Lemma 2 below necessary for {P (x), N } to be a CNS. On the other hand the following examples show that the inequalities p_{2}, …, p_{d−1} ≥ 0 are not necessary if d ≥ 4.

Example 2 In fact, we can show that the roots of each polynomials

x^{4} + 2x^{3} − x^{2} − x + 5, x^{4} − x^{3} + 2x^{2} − 2x + 3, x^{5} + x^{4} + x^{3} − x^{2} − x + 4

forms a CNS by the criterion of [8].

We are also able to prove that p_{d−1} cannot be too small. More precisely the following theorem is true.

Theorem 3 If p_{0} ≥ ∑_{i=1}^{d} |p_{i}| and {P (x), N } is a CNS then p_{ℓ} + ∑_{j=ℓ+1}^{d} |p_{j}| ≥ 0 holds for all ℓ ≥ 0. Especially p_{d−1} ≥ −1.

The characterization of higher dimensional CNS provided p_{0} is large is an interesting problem left to the reader. Numerical evidence supports the following:

Conjecture 1 Assume that p_{2}, …, p_{d−1}, ∑_{i=1}^{d} p_{i} ≥ 0 and p_{0} > ∑_{i=1}^{d} |p_{i}|. Then {P (x), N } is a CNS.

Conjecture 2 The pair {P (x), N } is a CNS in R if and only if all α ∈ R of the form (4) with ε_{j} ∈ {0, 1} (0 ≤ j ≤ d − 1) have a representation in {P (x), N }.

3 Auxiliary results

Several general properties of CNS are shown in this section. Some of them are used in the proof of our Theorems.

Lemma 1 If p_{0} > L(P) then each root of P has modulus greater than 1.

Proof: Assume that γ is a root of P with |γ| ≤ 1. Then we have

|∑_{i=1}^{d} p_{i}γ^{i}| ≤ L(P) < p_{0},

which is absurd. □

Lemma 2 If {P (x), N } is a CNS, then ∑_{i=1}^{d} p_{i} ≥ 0.

Proof: By the results of [10], stated in the introduction, we have P (1) = ∑_{i=0}^{d} p_{i} > 0, since otherwise P (x) would have a real root greater or equal to 1.

Assume that ∑_{i=1}^{d} p_{i} < 0. Then P (1) = p_{0} + ∑_{i=1}^{d} p_{i} < p_{0}, i.e., P (1) ∈ N . Let

α = ∑_{i=0}^{d−1} ∑_{j=i}^{d−1} p_{d+i−j}x^{i}.

Then T_{0}^{(0)}(α) = ∑_{i=1}^{d} p_{i}, hence −p_{0} < T_{0}^{(0)}(α) < 0, which implies q = [T_{0}^{(0)}(α)/p_{0}] = −1. Thus T (α) = α ≠ 0 and α does not have a representation in {P (x), N } by Lemma 4 below. □

In the sequel we will put T_{j}^{(i)}(α) = 0 for j > d − 1 and p_{j} = 0 for j > d.

Lemma 3 Let α ∈ R and i, j, k be non-negative integers such that k ≥ i. Let q_{k} = [\frac{T_{0}^{(k)}(α)}{p_{0}}] . Then

T_{j}^{(k)}(α) = T_{j+i}^{(k−i)}(α) − ∑_{ℓ=1}^{i} q_{k−ℓ}p_{j+ℓ},  (5)

α = ∑_{ℓ=0}^{k−1}(T_{0}^{(ℓ)}(α) − q_{ℓ}p_{0})x^{ℓ} + x^{k}T^{(k)}(α).  (6)

Proof: Identity (5) is obviously true if i = 0. Assume that it is true for an i such that 0 ≤ i < k. We have

T_{j+i}^{(k−i)}(α) = T_{j+i+1}^{(k−i−1)}(α) − q_{k−i−1}p_{j+i+1}

by (3). Inserting this into (5) we obtain at once the stated identity for i + 1.

Identity (6) is obviously true for k = 0. Assume that it is true for k − 1 ≥ 0. Using that P (x) = 0 in R we have

T^{(k−1)}(α) = ∑_{j=0}^{d−1} T_{j}^{(k−1)}(α)x^{j}

= ∑_{j=0}^{d−1} T_{j}^{(k−1)}(α)x^{j} − q_{k−1} ∑_{j=0}^{d} p_{j}x^{j}

= ∑_{j=0}^{d}(T_{j}^{(k−1)}(α) − q_{k−1}p_{j})x^{j}
= (T_{0}^{(k−1)}(α) − q_{k−1}p_{0}) + xT^{(k)}(α).

Considering (6) for k − 1 and using the last identity we obtain

α = ∑_{ℓ=0}^{k−2}(T_{0}^{(ℓ)}(α) − q_{ℓ}p_{0})x^{ℓ} + x^{k−1}T^{(k−1)}(α)

= ∑_{ℓ=0}^{k−2}(T_{0}^{(ℓ)}(α) − q_{ℓ}p_{0})x^{ℓ} + x^{k−1}((T_{0}^{(k−1)}(α) − q_{k−1}p_{0}) + xT^{(k)}(α))

= ∑_{ℓ=0}^{k−1}(T_{0}^{(ℓ)}(α) − q_{ℓ}p_{0})x^{ℓ} + x^{k}T^{(k)}(α).

Thus (6) is proved for all k ≥ 0. □

Lemma 4 The element α ∈ R is representable in {P (x), N } if and only if there exists a k ≥ 0 for which T^{(k)}(α) = 0.

Proof: The condition is sufficient, because if α is representable in {P (x), N } then we can take k = d.

To prove the necessity, assume that there exists a k ≥ 0 for which T^{(k)}(α) = 0. Then

α = ∑_{ℓ=0}^{k−1}(T_{0}^{(ℓ)}(α) − q_{ℓ}p_{0})x^{ℓ}

by Lemma 3, which is the representation of α in {P (x), N }.

The lemma is proved. □

We wish to summarize here some inequalities satisfied by a cubic CNS.

Proposition 1 Let {P (x), N } be a cubic CNS. Then we have the following inequalities:

1 + p_{1} + p_{2} ≥ 0  (7)
p_{0} + p_{2} > 1 + p_{1}  (8)
p_{0}p_{2} + 1 < p_{0}^{2} + p_{1}  (9)
p_{2} ≤ p_{0} + 1  (10)
p_{1} < 2p_{0}  (11)
p_{2} ≥ 0  (12)

Proof: Lemma 2 implies (7). By an argument similar to the proof of Lemma 2, we see P (−1) > 0. This shows (8). If P (−p_{0}) ≥ 0 then there exists a real root less than or equal to −p_{0}. Since p_{0} is the product of the three roots of P (x), this implies that there exists a root with modulus less than or equal to 1. This shows P (−p_{0}) < 0 which is (9).

Let γ_{i} (i = 1, 2, 3) be the roots of P (x). Noting xy + 1 > x + y for x, y > 1, we see

|p_{2}| = |γ_{1} + γ_{2} + γ_{3}| < |γ_{1}γ_{2}| + |γ_{3}| + 1 < |γ_{1}γ_{2}γ_{3}| + 2 = p_{0} + 2.

Thus we have (10). Using (8) we have (11).

Finally we want to show (12). By (7), if p_{2} < 0 then p_{1} ≥ 0. Let w = x + p_{2}. By (8), we have p_{2} > −p_{0}. Thus

T (w) = x^{2} + p_{2}x + p_{1} + 1.

Since 1 ≤ p_{1} + 1 ≤ p_{0} + p_{2} < p_{0}, we see p_{1} + 1 ∈ N. Thus we have

T^{(2)}(w) = x + p_{2} = w.

Hence T^{(2k)}(w) = w and T^{(2k+1)}(w) = x^{2} + p_{2}x + p_{1} + 1 for all k ≥ 0, i.e., T^{(j)}(w) ≠ 0 holds for all j ≥ 0. By Lemma 4 w is not representable in {P (x), N }. This completes the proof of the proposition. □

We can find a CNS with p_{d−1} = −1 when d = 2 or d ≥ 4.

4 Proof of Theorem 1.

Proof:

Let η be a positive number and put p_{i}^{∗} = p_{i} if p_{i} ≠ 0 and p_{i}^{∗} = η otherwise. Taking a small η, we may assume

p_{0} ≥ (1 + 1/M) ∑_{i=1}^{d} |p_{i}^{∗}|.

Define the weight of α ∈ R by

W(α) = max \{M, max_{i=0,1,···,d−1} \frac{|T_{i}^{(0)}(α)|}{∑_{k=i+1}^{d} |p_{k}^{∗}|}\} .  (13)

Obviously the weight of α takes discrete values. We have

|T_{i}^{(0)}(α)| ≤ W(α) ∑_{k=i+1}^{d} |p_{k}^{∗}|,

by definition. Remark that this inequality is also valid when i = d. First we show that W(T (α)) ≤ W(α) for any α ∈ R. If |T_{0}^{(0)}(α)/p_{0}| ≥ M then we have

|[\frac{T_{0}^{(0)}(α)}{p_{0}} ]| < |\frac{T_{0}^{(0)}(α)}{p_{0}} | + 1 ≤ (1 + \frac{1}{M} ) |\frac{T_{0}^{(0)}(α)}{p_{0}} | ≤ \frac{|T_{0}^{(0)}(α)|}{∑_{k=1}^{d} |p_{k}^{∗}|} ≤ W(α).

If |T_{0}^{(0)}(α)/p_{0}| < M, we see [T_{0}^{(0)}(α)/p_{0}] ∈ [−M, M − 1] ∩ ℤ. (Here we used the fact that M is a positive integer.) This shows |[T_{0}^{(0)}(α)/p_{0}]| ≤ M ≤ W(α). So we have shown

|[\frac{T_{0}^{(0)}(α)}{p_{0}} ]| ≤ W(α)

for any α. We note that the equality holds only when q_{0} = [T_{0}^{(0)}(α)/p_{0}] = −M. This fact will be used later. Remind the relation:

T (α) = ∑_{i=0}^{d−1}(T_{i+1}^{(0)}(α) − q_{0}p_{i+1})x^{i}

with q_{0} = [T_{0}^{(0)}(α)/p_{0}]. So we have

\frac{|T_{i+1}^{(0)}(α) − q_{0}p_{i+1}|}{∑_{k=i+1}^{d} |p_{k}^{∗}|} ≤ \frac{W(α) ∑_{k=i+2}^{d} |p_{k}^{∗}| + W(α)|p_{i+1}|}{∑_{k=i+1}^{d} |p_{k}^{∗}|}
≤ W(α),

which shows W(T (α)) ≤ W(α). Assume that {P (x), N } is not a canonical number system. Then there exist elements of R which do not have any representation in {P (x), N }. Let κ ∈ R be such an element of minimum weight. Our purpose is to prove that there exists some m such that T^{(m)}(κ) must have the form (4). First we show W(κ) = M. So assume that W(κ) > M. Then we have

W(κ) = max_{i=0,1,···,d−1} \frac{|T_{i}^{(0)}(κ)|}{∑_{k=i+1}^{d} |p_{k}^{∗}|}.

Since p_{i}^{∗} ≠ 0, reviewing the above proof, we easily see W(T (κ)) < W(κ) when q_{0} ≠ −M. By the minimality of κ, we see [T_{0}^{(0)}(κ)/p_{0}] = −M and W(T (κ)) = W(κ). Repeating this argument we have

q_{j} = [\frac{T_{0}^{(j)}(κ)}{p_{0}} ] = −M, j = 0, 1, ⋯, d − 1.

By (5) with k = i = d and α = κ, we have

T_{j}^{(d)}(κ) = − ∑_{ℓ=1}^{d−j} q_{d−ℓ}p_{j+ℓ}

= − ∑_{ℓ=j+1}^{d} q_{d−ℓ+j}p_{ℓ}

= M ∑_{ℓ=j+1}^{d} p_{ℓ},

but this implies W(T^{(d)}(κ)) = M, which contradicts the inequality W(κ) > M. This shows W(κ) = M and moreover W(T^{(j)}(κ)) = M for any j. So we have

\frac{|T_{0}^{(j)}(κ)|}{p_{0}} ≤ \frac{|T_{0}^{(j)}(κ)|}{(1 + 1/M) ∑_{k=1}^{d} |p_{k}^{∗}|} ≤ \frac{M^{2}}{1 + M} < M,

which shows q_{j} = [−M, M − 1] ∩ ℤ for j ≥ 0. Again by (5) with k = i = d and α = κ, we have

T_{ℓ}^{(d)}(κ) = − ∑_{j=ℓ}^{d−1} q_{j}p_{d+ℓ−j}.

Letting ε_{j} = −q_{j} ∈ [1 − M, M] ∩ ℤ, we have

T^{(d)}(κ) = ∑_{ℓ=0}^{d−1} (∑_{j=ℓ}^{d−1} ε_{j}p_{d+ℓ−j}) x^{ℓ}.

This proves the assertion in light of Lemma 4. □

Remark 1 The integer assumption on M is not necessary for the above proof but we cannot get a better bound by choosing non-integer M ≥ 1.

Remark 2 To derive a result of this type, we first used the length of α instead of the weight and used a technique inspired by the analysis of the running time of the euclidean algorithm. (See e.g. [9].) Under this choice, we could only show a rather bad bound but it was an inspiring experience for us.

5 Proof of Theorem 2.

Proof: The assumption of Theorem 1 is satisfied with M = 1, thus it is enough to prove that every element of the form

α(ε_{0}, …, ε_{d−1}) = α = ∑_{i=0}^{d−1} (∑_{j=i}^{d−1} ε_{j}p_{d+i−j}) x^{i}

with ε_{j} ∈ {0, 1}, 0 ≤ j ≤ d−1 is representable in {P (x), N }. A simple computation shows that

|T_{i}^{(0)}(α)| ≤ L(P) < p_{0}.

This means that if T_{i}^{(0)}(α) ≥ 0 for some i, then T_{i}^{(0)}(α) ∈ N , otherwise p_{0} − T_{i}^{(0)}(α) ∈ N .

If p_{1} ≥ 0, then T_{i}^{(0)}(α) ≥ 0 for all i, such that 0 ≤ i ≤ d − 1 and for all choices of ε_{j} ∈ {0, 1}, 0 ≤ j ≤ d − 1. Similarly, as p_{2}, …, p_{d−1} are non-negative T_{i}^{(0)}(α) ≥ 0 for all i, such that 1 ≤ i ≤ d − 1. If ε_{d−1} = 0 then T_{0}^{(0)}(α) = ∑_{j=0}^{d−2} ε_{j}p_{d−j} > 0. In these cases every α of form (4) is representable in {P (x), N }.

We assume p_{1} < 0 and ε_{d−1} = 1 in the sequel. Let ε_{j} ∈ {0, 1}, 0 ≤ j ≤ d − 1 be fixed. Put α = α(ε_{0}, …, ε_{d−1}). If T_{0}^{(0)}(α) ≥ 0, then α is representable in {P (x), N }. Thus we may assume T_{0}^{(0)}(α) < 0. Then there exists an i with 0 ≤ i < d − 1 such that ε_{i} = 0 because ∑_{j=1}^{d} p_{j} ≥ 0 by Lemma 3. Let j be the index such that ε_{j} = … = ε_{d−1} = 1, but ε_{j−1} = 0. We apply to α the transformation T several times and ultimately we obtain an element, which is represented in {P (x), N }.

Indeed, as T_{0}^{(0)}(α) < 0 we have q_{0} = [\frac{T_{0}^{(0)}(α)}{p_{0}} ] = −1. Putting ε_{d} = 1 we obtain

T^{(1)}(α) = ∑_{i=0}^{d−1} (∑_{j=i}^{d−1} ε_{j+1}p_{d+i−j}) x^{i}.

Hence T^{(1)}(α) = α(ε_{1}, …, ε_{d}). If T_{0}^{(1)}(α) ≥ 0 then this is already the representation of T^{(1)}(α) in {P (x), N }. Otherwise, i.e., if T_{0}^{(1)}(α) < 0 we continue the process with

q_{1} = [\frac{T_{0}^{(1)}(α)}{p_{0}} ] = −1 and ε_{d+1} = 1. Hence either T_{0}^{(k)}(α) ≥ 0 for some k < j − 1 or

T_{0}^{(k)}(α) < 0 for all k with 0 ≤ k < j−1. In the second case we have T^{(j−1)}(α) = α(1, …, 1). Thus there exists always a k ≥ 0 such that T^{(k)}(α) is representable in {P (x), N }. Theorem 2 follows now immediately from Lemma 4. □

6 Proof of Theorem 3.

For

α = α(ε_{0}, …, ε_{d−1}) = ∑_{i=0}^{d−1}(∑_{j=i}^{d−1} ε_{j}p_{d+i−j})x^{i}  (14)

with ε_{i} ∈ ℤ, i = 0, …, d − 1 let

E(α) = max{|ε_{i}|, i = 0, …, d − 1}.

With this notation we prove the following useful lemma.

Lemma 5 Assume that p_{0} ≥ L(P) and that α is given in the form (14). Then

E(T (α)) ≤ E(α).

Proof: Taking

q = [\frac{1}{p_{0}} ∑_{j=0}^{d−1} ε_{j}p_{d−j}]

we have

\frac{1}{p_{0}} ∑_{j=0}^{d−1} ε_{j}p_{d−j} − 1 < q ≤ \frac{1}{p_{0}} ∑_{j=0}^{d−1} ε_{j}p_{d−j}.

The inequality

|\frac{1}{p_{0}} ∑_{j=0}^{d−1} ε_{j}p_{d−j}| ≤ \frac{E(α)L(P)}{p_{0}} ≤ E(α)

implies

|q| ≤ E(α).

Putting ε_{d} = −q we obtain

T (α) = ∑_{i=0}^{d−1}(∑_{j=i}^{d−1} ε_{j+1}p_{d+i−j})x^{i},

which implies

E(T (α)) = max{|ε_{1}|, …, |ε_{d−1}|, |ε_{d}|} ≤ E(α).

The lemma is proved. □

Now we are in the position to prove Theorem 3.

Assume that there exists some ℓ with 0 < ℓ < d, such that p_{ℓ} + ∑_{j=ℓ+1}^{d} |p_{j}| < 0. We show that −1 is not representable in {P (x), N }. More precisely we prove for all k ≥ 0 that at least one of T_{j}^{(k)}(−1), j = 0, …, d − 1, is negative.

This assertion is obviously true for k = 0. Let k ≥ 0 and assume that at least one of T_{j}^{(k)}(−1), j = 0, …, d − 1, is negative. We have

−1 = ∑_{i=0}^{d−1}(∑_{j=i}^{d−1} ε_{j}p_{d+i−j})x^{i}

with ε_{0} = −1 and ε_{j} = 0, j = 1, …, d − 1. Hence

T^{(k)}(−1) = ∑_{i=0}^{d−1}(∑_{j=i}^{d−1} ε_{j+k}p_{d+i−j})x^{i}

holds with |ε_{j+k}| ≤ 1, j = 0, …, d − 1, by Lemma 5 for all k ≥ 0. Hence we have

T^{(k+1)}(−1) = ∑_{i=0}^{d−1}(∑_{j=i}^{d−1} ε_{j+k+1}p_{d+i−j})x^{i}

with ε_{d+k} = −[T_{0}^{(k)}(−1)/p_{0}]. We distinguish three cases according to the values of ε_{d+k}.

Case 1: ε_{d+k} = −1. Then T_{d−1}^{(k+1)}(−1) = ε_{d+k}p_{d} = −1 hence the assertion is true for k + 1.

Case 2: ε_{d+k} = 0. Then T_{j}^{(k+1)}(−1) = T_{j+1}^{(k)}(−1) for j = 0, …, d − 2, and T_{d−1}^{(k+1)}(−1) = 0. There exists by the hypothesis a j with 0 ≤ j ≤ d − 1 such that T_{j}^{(k)}(−1) < 0. This index cannot be zero because ε_{d+k} = 0. Hence j > 0 and T_{j−1}^{(k+1)}(−1) = T_{j}^{(k)}(−1) < 0. The assertion is true again.

Case 3: ε_{d+k} = 1. In this case we have

T_{ℓ−1}^{(k+1)}(−1) = ε_{k+ℓ}p_{d} + … + ε_{k+d−1}p_{ℓ+1} + ε_{k+d}p_{ℓ}
= ε_{k+ℓ}p_{d} + … + ε_{k+d−1}p_{ℓ+1} + p_{ℓ} ≤ p_{ℓ} + ∑_{j=ℓ+1}^{d} |p_{j}| < 0

because |ε_{k+j}| ≤ 1, j = ℓ, …, d − 1, by Lemma 5. Theorem 3 is proved.

References

[1] S. Akiyama and J. Thuswaldner, Topological properties of two-dimensional number systems, to appear in Journal de Théorie des Nombres de Bordeaux.

[2] I. Kátai and J. Szabó, Canonical Number Systems for Complex Integers, Acta Sci. Math. (Szeged) 37 (1975) 255–260.

[3] I. Kátai and I. Kőrnyei, On Number Systems in Algebraic Number Fields, Publ. Math. Debrecen 41 no. 3–4 (1992) 289–294.

[4] I. Kátai and B. Kovács, Canonical Number Systems in Imaginary Quadratic Fields, Acta Math. Hungar. 37 (1981) 159–164.

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

[6] D. E. Knuth The Art of Computer Programming, Vol. 2 Semi numerical Algorithms, Addison Wesley (1998) London 3rd-edition.

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

[8] 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.

[9] A. Pethő, Algebraische Algorithmen, Vieweg Verlag, 1999.

[10] 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.

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

[12] J. 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

Attila Pethő Institute of Mathematics and Computer Science, University of Debrecen, H-4010 Debrecen P.O.Box 12, Hungary e-mail: pethoe@math.klte.hu