1

1

Cubic CNS polynomials, notes on a conjecture of W.J. Gilbert

Shigeki Akiyama^{†} Department of Mathematics, Faculty of Science, Niigata University, Ikarashi 2-8050, Niigata 950-2181, Japan, Horst Brunotte Haus-Endt-Str. 88, D - 40593 Düsseldorf, Germany and Attila Pethő^{‡} Institute of Mathematics and Computer Science, University of Debrecen, P.O. Box 12, H - 4010 Debrecen, Hungary

October 14, 2002

Abstract

A conjecture of W. J. Gilbert’s on canonical number systems which are defined by cubic polynomials is partially proved, and it is shown that the conjecture is not complete. Applications to power integral bases of simplest and pure cubic number fields are given thereby extending results of S. Körmendi.

1 Introduction

Let P ∈ Z[X] be a monic polynomial with |P (0)| > 1 and N = {0, 1, …, |P (0)| − 1}. The pair (P, N) is called a canonical number system (CNS) if every non-zero element of R := Z[X]/P Z[X] can uniquely be written in the form

(1)  a_{0} + a_{1}x + ⋯ + a_{l}x^{l}

with a_{0}, ..., a_{l} ∈ N, a_{l} ≠ 0; here x denotes the image of X under the canonical epimorphism from Z[X] to R. In other words this means that every coset Q + P Z[X] (Q ∈ Z[X], deg Q < deg P) includes a polynomial with coefficients belonging to N.

∗Mathematics subject classification numbers: 11R04, 11R16, 11R21, 12D99

†Supported by the Japanese Ministry of Education, Culture, Sports, Science and Technology, Grand-in Aid for fundamental research 14540015, 2002–2005.

‡Research partially supported by Hungarian National Foundation for Scientific Research Grant Nos 29330 and 38225.

The concept of canonical number systems in the general form described above was introduced by the third author [16]; canonical number systems with more restrictions on the defining polynomials have been studied by several authors (see e.g. the introduction of [1] or [2] and the references given there). Remark that W.J. Gilbert [9] used the terminology radix representation instead of canonical number system. The first and third authors [1] suggested that the characterization problem of canonical number systems is only related to the coefficients of the defining polynomial. Therefore the term CNS polynomial (see the definition below) seems to be reasonable (cf. [2]). CNS polynomials can be applied to cryptography [16] and fractal tilings of the Euclidean space [3]. The problem of characterizing CNS polynomials is still open. It is very easy to show that linear CNS polynomials are given by X +p_{0} with p_{0} ≥ 2. Quadratic CNS polynomials were classified by I. Kátai and B. Kovács [10, 11] and independently by W. J. Gilbert [9] (see also S. Akiyama and H. Rao [2] or [5] for the general setting). Under additional hypotheses cubic and quartic CNS polynomials were characterized by K. Scheicher and J. M. Thuswaldner ([17], Theorem 7.1 and Theorem 7.2) and S. Akiyama and H. Rao ([2], Theorem 5.4 and Theorem 5.5); S. Akiyama and H. Rao also dealt with quintic polynomials ([2], Theorem 5.7). CNS trinomials were classified by the second author [5]. The present note aims at a partial proof of a conjecture of W. J. Gilbert [9] on the characterization of cubic CNS polynomials. We also show that his conjecture is not complete. Further applications to some classes of cubic number fields are described. The second author would like to express his heartfelt gratitude for the hospitality of the University of Debrecen on the occasion of discussing the outline of this paper.

2 Notation and basic results on CNS polynomials

As usual we denote by Z the ring of integers and by N the set of nonnegative integers. Let P = ∑_{i=0}^{d} p_{i}X^{i} ∈ Z[X] with d > 0, p_{d} = 1 and |p_{0}| > 1.

Definition 2.1 P is a CNS polynomial if the pair (P, N) forms a canonical number system. The set of CNS polynomials will be denoted by C.

For the convenience of the reader we formally list some well known results which will be used in the sequel.

Lemma 2.2 (W. J. Gilbert [9], A. Pethő [16]) If P ∈ C then all real zeroes of P are less than −1 and the absolute values of all complex roots of P exceed 1. In particular p_{0} > 1.

In view of Lemma 2.2 we shall suppose p_{0} > 1 from now on.

Theorem 2.3 (B. Kovács [12]) If p_{0} ≥ p_{1} ≥ … ≥ p_{d−1} ≥ 1 and none of the roots of P is a root of unity then P ∈ C.

Remark 2.4 B. Kovács proved this theorem under the hypothesis that P be irreducible; in this case the assumption on the roots of P is trivially satisfied. The extension to not necessarily irreducible polynomials is due to the third author [16].

The algorithm to express any element of R in the form (1) can clearly be described by the map^{1} T : R ⟶ R, ∑_{j=0}^{d−1} z_{j}x^{j} ↦ ∑_{j=0}^{d−1}(z_{j+1} − p_{j+1} ⌊\frac{z_{0}}{p_{0}} ⌋)x^{j} with z_{d} := 0 (cf. [1]). Using the Z-basis w_{j} = ∑_{i=j}^{d} p_{i}x^{i−j} (j = 1, …, d) of R and the group isomorphism ι : Z^{d} ⟶ R, (z_{1}, …, z_{d}) ↦ ∑_{j=1}^{d} z_{j}w_{j}, one easily verifies the relation

(2)  ι ∘ τ = T ∘ ι

with

τ : Z^{d} ⟶ Z^{d}, (z_{1}, …, z_{d}) ↦ (− ⌊\frac{p_{1}z_{1} + ⋯ + p_{d}z_{d}}{p_{0}} ⌋ , z_{1}, …, z_{d−1})

(cf. [4]).

Lemma 2.5 (i) P ∈ C if and only if for every z ∈ Z^{d} we can find some l ∈ N such that τ^{l}(z) = 0. (ii) If there exists 0 ≠ z ∈ Z^{d} and 0 ≠ k ∈ N with τ^{k}(z) = z (i.e. z is a non-zero periodic element) then P ∉ C.

Proof. The first part is a consequence of (2) and ([1], Lemma 4) and obviously implies the second part. □

Lemma 2.6 Let E ⊆ Z^{d} have the following properties:

(i) (1, 0, …, 0) ∈ E (ii) −E ⊆ E (iii) τ(E) ⊆ E (iv) For every e ∈ E there exists some k ∈ N with τ^{k}(e) = 0. Then P ∈ C.

Proof. Observing that we have

τ(z_{1}, …, z_{d} + a) ∈ {τ(z), −τ(−z)}

for every z = (z_{1}, …, z_{d}) ∈ Z^{d} and a ∈ N the proof of ([4], Lemma 2) can be adapted. □

1 ⌊…⌋ denotes the integer part function.

3 Cubic CNS polynomials

From now on we shall concentrate on cubic polynomials. Therefore we let P = X^{3} + p_{2}X^{2} + p_{1}X + p_{0} ∈ Z[X] be a monic cubic polynomial throughout this section. Under the additional hypothesis that P be irreducible W.J. Gilbert [9] stated the following Conjecture. P ∈ C if and only if

(i) p_{0} ≥ 2, (ii) p_{2} ≥ 0, (iii) p_{1} + p_{2} ≥ −1, (iv) p_{1} − p_{2} ≤ p_{0} − 2,

(v) p_{2} ≤ \{ \begin{matrix}p_{0} − 2, if & p_{1} ≤ 0, \\ p_{0} − 1, if & 1 ≤ p_{1} ≤ p_{0} − 1, \\ p_{0}, if & p_{1} ≥ p_{0}. □ \end{matrix}

The next theorem shows that W.J. Gilbert’s conditions are in fact necessary. It was proved by him [9] for irreducible polynomials.

Theorem 3.1 Let P ∈ C. Then

(i) p_{0} ≥ 2, (ii) 1 + p_{1} + p_{2} ≥ 0, (iii) p_{1} − p_{2} ≤ p_{0} − 2, (iv) p_{1} ≤ 0 implies 0 ≤ p_{2} ≤ min{p_{0} − 2, (p_{0}^{2} + p_{1} − 2)/p_{0}},

(v) 1 ≤ p_{1} ≤ p_{0} − 1 implies 0 ≤ p_{2} ≤ p_{0} − 1, (vi) p_{1} ≥ p_{0} implies 2 ≤ p_{2} ≤ p_{0}.

Proof. In view of ([1], Proposition 1) we are left to show that the following values of p_{2} are excluded: p_{2} = p_{0} − 1 in case (iv), p_{2} = p_{0} in case (v) and p_{2} = p_{0} + 1 in case (vi). In all these cases we easily check that the element (1, 0, −1) ∈ Z^{3} is periodic and so the assertion follows from Lemma 2.5. □ The following four counterexamples show that W. J. Gilbert’s conditions are not sufficient. We continue to assume p_{0} ≥ 2 throughout. We thank Tibor Borbély, whose program made it possible to find counterexamples (ii) and (iii). Counterexamples. (i) p_{1} ≤ 0. Let 2 ≤ p_{1} + p_{2} ≤ −p_{1} and p_{0} ≤ min{p_{2} − p_{1}, p_{1} + 2p_{2} + 1} then the element (1, −1, −1) is periodic and the period is always (1, −1, −1), (2, 1, −1), (1, 2, 1), (−1, 1, 2), (−1, −1, 1). Taking p_{2} = 2m, p_{1} = −m or −m − 1, p_{0} = 3m (m > 2) we obtain a parametrized family of non CNS polynomials.

(ii) 1 ≤ p_{1} ≤ p_{0} − 1. Let \frac{7p_{0}−5p_{2}}{6} + 1 ≤ p_{1} ≤ −p_{0} + \frac{3}{2}p_{2}. Then the element (1, −3, 1) is periodic with period (1, −3, 1), (3, 1, −3), (−2, 3, 1), (−2, −2, 3), (3, −2, −2), (1, 3, −2), (−3, 1, 3) provided p_{0} ≥ 28. (iii) p_{1} > p_{0}. Let p_{0} + \frac{1}{2}p_{2} + 1 ≤ p_{1} < p_{0} + \frac{2}{3}p_{2} − \frac{1}{3}. Then the element (3, −2, 1) is periodic with period (3, −2, 1), (−2, 3, −2), (1, −2, 3), (1, 1, −2), (−2, 1, 1). The same element is periodic, but with period (3, −2, 1), (−3, 3, −2), (3, −3, 3), (−2, 3, −3), (1, −2, 3), (1, 1, −2), (−2, 1, 1) provided p_{0} + \frac{2}{3}p_{2} − \frac{1}{3} ≤ p_{1} ≤ 2p_{2} − 4. One can easily find parametrized families of non CNS polynomials satisfying these conditions. □ In the following proofs we often use Lemma 2.6. In these cases we restrict ourselves to explicitly specifying an appropriate (finite) set E ⊂ Z^{3} such that E_{+} ∪ (0, 0, 0) ∪ (−E_{+}) satisfies the prerequisites of this lemma where we put E_{+} = E ∪{(0, 0, 1), (1, 0, 0)}. The verification that this set does in fact have the required properties can easily be performed by looking at the respective graphs (see [2] or [4]) and is left to the reader (an example of this graph is drawn in the proof of Proposition 3.2). In an effort to prove sufficiency of the conditions of the conjecture W.J. Gilbert’s result suggests the treatment of four different types of polynomials according to the size of the linear coefficient of the polynomial. Therefore we first deal with negative coefficients p_{1}.

Proposition 3.2 Let p_{1} ≤ −1, p_{2} ≤ p_{0} − 2 and −1 ≤ p_{1} + p_{2} ≤ 0. Then P ∈ C.

Proof. Let E_{0} = {(0, 1, 0), (0, 1, 1), (1, 0, −1), (1, 1, 0)} and choose E = E_{0} ∪ {(1, 1, 1)} in case p_{1} + p_{2} = −1 and E = E_{0} otherwise. To illustrate our method the graph of this case is shown in Figure 1. □

Proposition 3.3 Let p_{1} ≤ −1, 0 ≤ p_{2} < min{p_{0} − 1, 2p_{0}/3} and 1 + p_{1} + p_{2} ≥ 0. Then P ∈ C.

Proof. Using Proposition 3.2 we may suppose p_{1} + p_{2} ≥ 1. In view of ([17], Theorem 7.1) or ([2], Theorem 5.4) we may assume p_{1} − p_{2} ≤ −p_{0} + 1. Let E_{0} = {(0, 1, 0), (0, 1, 1), (0, 2, 1), (1, −1, −1), (1, 0, −2), (1, 0, −1), (1, 1, −1), (1, 1, 0), (1, 2, 1), (2, 0, −2), (2, 1, −1)}. We distinguish two cases. Case I. p_{1} + 2p_{2} ≤ p_{0} − 1 Let E_{1} = E_{0} ∪ {(0, 1, 2), (1, −1, −2)}. If 2p_{1} ≤ −p_{0} + 1 let

E_{11} = E_{1} ∪ {(0, 2, 2), (1, −2, −2), (1, 1, −2), (1, 2, 0), (2, 1, −2), (2, 2, 0)}

[figure: −1, −1, 0; −1, 0, 0; 0, −1, −1; 0, −1, 0; 0, 0, −1; 1, 0, −1; 1, 0, 0; −1, 0, 1; 1, 1, 0; 0, 1, 0; 0, 1, 1; 0, 0, 1; 0, 0, 0] Figure 1: −p^{0} + 2 ≤ p^{1} ≤ −1, p^{2} = −p^{1}

and put E = E_{11} ∪ {(1, 1, 1)} if p_{1} + p_{2} = 1 and E = E_{11} otherwise. If 2p_{1} ≥ −p_{0} + 2 put E = E_{1} ∪ {(0, 2, 0), (1, 2, 0)}. Case II. p_{1} + 2p_{2} = p_{0} Let E = E_{0} ∪ {(0, 1, 2), (0, 2, 0), 0, 2, 2), (1, −2, −2), (1, −1, −2), (1, 1, −2), (1, 2, −1), (1, 2, 0), (2, −1, −2), (2, 1, −2), (2, 2, −1)}. □

Proposition 3.4 If 1 + p_{1} + p_{2} ≥ 0, −p_{0} + p_{2} + 1 ≤ p_{1} ≤ −1 then P ∈ C.

Proof. In case p_{1}+p_{2} ≤ 0 the assertion is a consequence of Proposition 3.3, otherwise we assume p_{1}+p_{2} > 0 and define E = {(0, 1, −1), (0, 1, 0), (0, 1, 1), (1, −1, −1), (1, 0, −1), (1, 1, −1), (1, 1, 0)}. □ The following statement which is an immediate consequence of Proposition 3.4 shows that W.J. Gilbert’s conjecture holds in case p_{1} = −1.

Corollary 3.5 If p_{1} = −1 and 0 ≤ p_{2} ≤ p_{0} − 2 then P ∈ C.

In contrast to Proposition 3.3 we add some results valid for p_{2} = p_{0} − 2.

Proposition 3.6 Let −p_{0} + 1 ≤ p_{1} ≤ −1 and p_{2} = p_{0} − 2.

(i) If p_{0} ≤ 5 or if p_{0} ≥ 6 and p_{1} = −p_{0} + 1 or p_{1} = −p_{0} + 2 then P ∈ C. (ii) If p_{0} ≥ 6 and −p_{0} + 4 ≤ p_{1} ≤ 1 − p_{0}/2 then P ∉ C. (iii) If p_{0} ≥ 6 and p_{1} = −p_{0} + 3 then for every element of the form e = (e_{1}, e_{2}, e_{3}) ∈ Z^{3} such that e_{i} = −1, 0, 1, i = 1, 2, 3 we can find some l ∈ lN such that τ^{l}(e) = 0.

Proof. (i) The case p_{0} ≤ 5 can easily be derived from Corollary 3.5, Proposition 3.2 and Proposition 3.3. While the cases for p_{0} ≥ 6 follow immediately from Proposition 3.2. (ii) The element (1, −1, −1) is periodic. (iii) This can easily be checked. □

Remark 3.7 (i) This result shows in particular that W.J. Gilbert’s conjecture does not hold for p_{1} = −2. The polynomial X^{3} + 4X^{2} − 2X + 6, for example, is irreducible, satisfies Gilbert’s conjecture, but is not a CNS polynomial. (ii) If Conjecture 2 of [1] holds true then X^{3} + (p_{0} − 2)X^{2} − (p_{0} − 3)X + p_{0} ∈ C for any p_{0} ≥ 6 (see also the remarks on this conjecture in [17]). We checked by a computer that X^{3} + (p_{0} − 2)X^{2} − (p_{0} − 3)X + p_{0} ∈ C for any 6 ≤ p_{0} ≤ 20. The program showed that the set of witnesses, i.e. the sets E = E(p_{0}), is growing with p_{0}. So far we were unable to understand the structure of E(p_{0}).

In case of vanishing linear coefficient we immediately derive a necessary and sufficient condition from the result on trinomials quoted above (see ([5], Theorem 3) thereby showing the truth of W.J. Gilbert’s conjecture in this case.

Theorem 3.8 X^{3} + p_{2}X^{2} + p_{0} ∈ Z[X] is a CNS polynomial if and only if 0 ≤ p_{2} ≤ p_{0} − 2.

Thirdly, we deal with small positive coefficients p_{1}.

Theorem 3.9 If

(1) 1 ≤ p_{2} ≤ p_{1} ≤ p_{0} − 1 or

(2) p_{1} = p_{0} and 2 ≤ p_{2} ≤ p_{0} then P ∈ C.

Proof. As P does not vanish at any root of unity this is clear by Theorem 2.3. □ For not necessarily monotonously increasing coefficients we can prove the following results.

Proposition 3.10 If 1 ≤ p_{1} ≤ p_{0} − 1 and 0 ≤ p_{2} ≤ (2p_{0} − 1)/3 then P ∈ C.

Proof. In view of Theorem 3.9 we assume p_{2} > p_{1}. Notice that p_{2} = p_{0} −1 ≤ (2p_{0} −1)/3 implies p_{0} ≤ 2. Hence p_{0} = 2, p_{2} = 1 and p_{1} = 0, which is excluded. Thus p_{2} ≤ p_{0} − 2. Let E_{0} = {(0, 1, −1), (0, 1, 0), (1, −1, 0), (1, 0, −1), (1, 1, −1)}. We distinguish two cases. Case I. p_{1} + p_{2} ≤ p_{0} Put E = E_{0} ∪ {(0, 1, 1), (1, −1, −1)}. Case II. p_{1} + p_{2} > p_{0} Let E_{2} = E_{0} ∪ {(0, 1, −2), (0, 2, −1), (1, −2, 0), (1, −2, 1), (1, −1, −1), (1, 0, −2), (1, 1, −2), (2, −1, −1), (2, 0, −2)}. If p_{1} + p_{2} = p_{0} + 1 put E = E_{2} ∪ {(0, 1, 1), (0, 2, 0)}. Finally suppose p_{1} + p_{2} > p_{0} + 1. Then 2p_{1} > p_{2} + 2. If 2p_{1} ≤ p_{0} + 1 take E = E_{2} ∪ {(0, 2, 0)} otherwise put E = E_{2} ∪ {(0, 2, −2), (1, −1, −2), (1, 2, −2), (2, −2, 0), (2, −1, −2)}. □ As we are particularly interested in relatively small p_{1} we state the following result.

Proposition 3.11 Let 1 ≤ t ≤ p_{0}. Then X^{3} + (p_{0} − t)X^{2} + X + p_{0} ∈ C if and only if (p_{0}, t) ≠ (2, 2).

Proof. Let E_{0} = {(0, 1, −1), (0, 1, 0), (1, −1, 0), (1, 0, −1)}. We distinguish three cases. Case I. t = 1 Put E = E_{0} if p_{0} = 2 and E = E_{0} ∪ {(0, 1, 1), (1, −1, −1), (1, 1, −1)} otherwise. Case II. t = 2 If p_{0} = 2 then the assertion follows from Theorem 3.1 (iii). If p_{0} = 3 choose E = E_{0}. Finally if p_{0} > 3 put E = E_{0} ∪ {(0, 1, 1), (1, −1, −1), (1, 1, −1)}. Case III. t > 2 The assertion follows from ([17], Theorem 7.1) or ([2], Theorem 5.4). □ Finally, we deal with large positive coefficients p_{1}. The case p_{1} = p_{0} was completely described in Theorem 3.9. Therefore we assume p_{1} > p_{0} in the next proposition.

Proposition 3.12 If p_{0} < p_{1} then P ∈ C if one of the following conditions holds:

(1) p_{1} = p_{0} + 1 and 3 ≤ p_{2} ≤ p_{0},

(2) p_{1} = p_{0} + 2 and p_{2} = (p_{0} + 4)/2,

(3) p_{0} < p_{1}, p_{1} − p_{2} < p_{0} − 1, 3p_{2} < 2p_{0}, 4p_{1} − 3p_{2} < 4p_{0} − 2, (4) p_{2} ≤ p_{0}, p_{1} − p_{2} < p_{0} − 2, 0 ≤ p_{1} − 2p_{2}, 2p_{1} − p_{2} ≤ 2p_{0},

(5) p_{1} − p_{2} < p_{0} − 1, −2 ≤ p_{1} − 2p_{2}, 2p_{1} − p_{2} < 2p_{0},

(6) 3 ≤ p_{2} ≤ p_{0}, p_{1}−p_{2} < p_{0}−1, p_{1}−2p_{2} ≤ −2, 2p_{1}−p_{2} ≤ 2p_{0}, p_{0}−1 ≤ 2p_{1}−2p_{2}, p_{1}+p_{2} ≤ 2p_{0}+2.

Proof. Let E_{0} = {(0, 1, −1), (1, −1, 0), (1, −1, 1), (1, 0, −1), (2, −1, 0)}.

(1) Take E_{01} = {(0, 1, −2), (1, −2, 2), (2, −2, 1)} and E_{02} = {(1, −1, −1), (1, 1, −2), (2, −1, −1)}. Case I. p_{2} < p_{0}/2 + 2 Put E_{1} = E_{0} ∪ E_{01} ∪ {(1, −2, 1), (1, −1, 2), (2, −2, 2)} and choose E = E_{1} ∪ E_{02} if p_{1} − 2p_{2} = −2 and E = E_{1} otherwise. Case II. p_{2} ≥ p_{0}/2 + 2 Let E = E_{0} ∪ E_{01} ∪ E_{02} ∪ {(0, 2, −2), (1, 0, −2), (2, −2, 0), (2, 0, −2)}.

(2) Take E = E_{0} ∪ {(0, 1, −2), (1, −2, 2), (1, −2, 1), (1, 1, −2), (2, −2, 1), (2, −2, 2), (2, −1, −1)}.

(3) Using (1) we may assume p_{1} > p_{0} + 1. Case I. 2p_{1} − p_{2} ≤ 2p_{0} − 1 Define E_{1} = E_{0} ∪ {(0, 1, −2), (1, −2, 1), (2, −2, 1)}. Case I.1 p_{1} − 2p_{2} ≤ −2 Let E_{11} = E_{1} ∪ {(1, −1, −1), (1, 1, −2), (2, −1, −1)}. Case I.1.1 2p_{1} − 2p_{2} ≤ p_{0} − 2 Put E_{111} = E_{11} ∪ {(0, 1, −3), (0, 2, −3), (0, 2, −2), (1, −2, 2), (1, −2, 3), (1, 0, −2), (1, 1, −3), (2, −3, 2), (2, −2, 0), (2, −2, 1), (2, 0, −2), (3, −2, 0)} and choose E = E_{111} ∪ {(1, −3, 2)} if 3p_{1} − 2p_{2} ≤ 2p_{0} − 1 and E = E_{111} ∪ {(1, −3, 3), (2, −3, 3), (3, −3, 2))} otherwise. Case I.1.2 2p_{1} − 2p_{2} > p_{0} − 2 Let E = E_{11} ∪ {(2, −2, 2)}. Case I.2 p_{1} − 2p_{2} > −2 Choose E = E_{1} ∪ {(1, −2, 2), (1, −1, 2), (2, −2, 2)}. Case II. 2p_{1} − p_{2} > 2p_{0} − 1 Define E_{2} = E_{0} ∪ {(0, 1, −2), (1, −2, 2), (1, −1, 2), (2, −2, 1), (2, −2, 2), (3, −2, 1)}. Case II.1 3p_{1} − 2p_{2} ≤ 3p_{0} − 2 Let E_{21} = E_{2} ∪ {((1, −2, 3), 2, −3, 2), (2, −3, 3), (3, −3, 2), (3, −3, 3)} and choose E = E_{21} ∪ {(0, 2, −3), (1, 0, −2), (2, −2, 0), (2, 0, −2), (3, −2, 0)} if 2p_{1} − 3p_{2} ≤ p_{0} − 3 and E = E_{21} ∪ {(2, −2, 3)} otherwise.

Case II.2 3p_{1} − 2p_{2} > 3p_{0} − 2 Let E_{22} = E_{2} ∪ {(2, −3, 3), (3, −3, 2), (3, −3, 3), (4, −3, 2)}. Case II.2.1 2p_{1} − 3p_{2} ≤ p_{0} − 4 Put E_{221} = E_{22} ∪ {(0, 1, −3), (0, 2, −3), (1, −3, 4), (1, −2, 3), ((1, −1, −1), 1, 0, −2), (1, 1, −3), (2, −3, 4), (2, −1, −1), (2, 0, −2), (3, −4, 3), (3, −4, 4), (3, −2, 0), (4, −4, 3), (4, −4, 4)} and choose E = E_{221} if p_{1} + p_{2} ≤ 2p_{0} + 2 and E = E_{221} ∪ {(3, −3, 1), (3, −1, −1), (4, −3, 1)} otherwise. Case II.2.2 2p_{1} − 3p_{2} > p_{0} − 4 Take E_{222} = E_{22} ∪ {(1, −2, 3), (2, −2, 3), (3, −4, 3), (3, −4, 4), (4, −4, 3), (4, −4, 4)}. Case II.2.2.1 3p_{1} − 4p_{2} ≤ 2p_{0} − 4 Define E_{2221} = E_{222} ∪ {(1, −3, 4), (2, −3, 4)}. Case II.2.2.1.1 p_{1} − 3p_{2} ≤ −5 Let E_{22211} = E_{2221} ∪ {(0, 1, −3), (1, 1, −3), (2, −1, −1)} and choose E = E_{22211} ∪ {(1, −1, −1)} if p_{1} + p_{2} ≤ 2p_{0} + 2 and E = E_{22211} ∪ {(3, −3, 1), (3, −3, 3), (3, −1, −1), (4, −3, 1)} otherwise. Case II.2.2.1.2 p_{1} − 3p_{2} > −5 Let E = E_{2221} ∪ {(0, 1, −3), (1, 1, −3)}. Case II.2.2.2 3p_{1} − 4p_{2} > 2p_{0} − 4 Define E = E_{222} ∪ {(2, −3, 4), (3, −3, 3), (3, −3, 4)}.

(4) Choose E = E_{0} ∪ {(0, 1, −2), (1, −2, 1), (1, −2, 2), (1, −1, 2), (2, −2, 1), (2, −2, 2)}.

(5) Using (1) we may assume p_{1} > p_{0} + 1 and using (4) we may further assume p_{1} − 2p_{2} ≤ −1. Define E_{1} = E_{0} ∪ {(0, 1, −2), (1, −2, 1), (1, −2, 2), (2, −2, 1), (2, −2, 2)} and choose E = E_{1} ∪ {(1, −1, 2)} if p_{1} − 2p_{2} = −1 and E = E_{1} ∪ {(1, −1, −1), (1, 1, −2), (2, −1, −1)} otherwise.

(6) Choose E = E_{0} ∪ {(0, 1, −2), (1, −2, 1), (1, −2, 2), (1, −1, −1), (1, 1, −2), (2, −2, 1), (2, −2, 2), (2, −1, −1)}. □ Example. Using the same method as in the proof of the last Proposition it can easily be checked that X^{3} + p_{0}X^{2} + (p_{0} + 2)X + p_{0} ∈ C for p_{0} = 4, 5, 6. By Theorem 3.1 (iii) it is clearly not a CNS polynomial for p_{0} = 2, 3.

4 Applications

In this section we apply the known results on cubic CNS polynomials to two classes of algebraic number fields which have extensively been studied in the literature. For convenience we make use of the following definition.

Definition 4.1 Let α be an algebraic integer. We call α a basis of a canonical number system if the minimal polynomial of α is a CNS polynomial.

4.1 Canonical number systems in simplest cubic fields

Let f = X^{3} − tX^{2} − (t + 3)X − 1, where t denotes a positive integer parameter. Let ϑ = ϑ_{1} denote the root of f with t + 1 < ϑ < t + 1 + 1/t. It is easy to see that the other roots of f are ϑ_{2} = −\frac{ϑ+1}{ϑ} and ϑ_{3} = −\frac{1}{ϑ+1}. E. Thomas and M. Mignotte proved the following theorem.

Theorem 4.2 (E. Thomas [18], M. Mignotte [14]) Let t ≥ 3. Then the only integer solutions of the Thue equation

X^{3} − tX^{2}Y − (t + 3)XY^{2} − Y^{3} = 1

are (x, y) = (1, 0), (0, −1), (−1, 1).

From this result it is easy to derive the following theorem (see also I. Gaál [8], Theorem 5.2.1)

Theorem 4.3 Up to translation by an integer the only β ∈ Z[ϑ] with Z[β] = Z[ϑ] are β = ϑ, −tϑ + ϑ^{2} and (t + 1)ϑ − ϑ^{2}. In particular, if Z[ϑ] coincides with the maximal order Z_{K} of the algebraic number field K = Q(ϑ) then up to translation by a rational integer the only power integral bases are generated by are β = ϑ, −tϑ + ϑ^{2} and (t + 1)ϑ − ϑ^{2}.

Using this theorem we will establish all bases of CNS in Z[ϑ].

Theorem 4.4 The element γ ∈ Z[ϑ] is the basis of a CNS in Z[ϑ] if and only if γ = ϑ + n, n ≤ −t − 3, γ = −ϑ + n, n ≤ −3, γ = ϑ^{2} − tϑ + n, n ≤ −t − 5, γ = −ϑ^{2} + tϑ + n, n ≤ −1, γ = ϑ^{2} − (t + 1)ϑ + n, n ≤ −t − 5, γ = −ϑ^{2} + (t + 1)ϑ + n, n ≤ −1.

Proof. For every β listed in Theorem 4.3 we have to find all integers n such that β + n and −β + n respectively are bases of CNS in Z[ϑ]. First we establish the largest (if β > 0 ) or least (if β < 0 ) n_{0} such that all conjugates of β + n_{0} and −β + n_{0} respectively are less than −1 (cf. Lemma 2.2). To simplify the text assume that β > 0. Then for all n ≤ n_{0} all conjugates of β + n are less than −1. In the second step we compute the minimal polynomial of β + n_{0} and check whether it belongs to C. If not then test the minimal polynomials of β + n_{0} − 1, β + n_{0} − 2, … until one of them, for the first time, belongs to C. For simplicity denote this integer again by n_{0}. Hence n_{0} is the largest integer such that β + n_{0} generates a CNS. It follows from the proof of the Theorem of Kovács [12] that there exists n_{1} such that the minimal polynomial of β + n satisfies for all n ≤ n_{1} the conditions of Theorem 2.3. One has obviously n_{1} ≤ n_{0}. Finally one has to test the elements of the finite set {β + n : n_{1} ≤ n ≤ n_{0}} to determine which ones generate a CNS. Notice that in the actual proof we always have n_{1} = n_{0}, which considerably simplifies the proof. After describing the general strategy, we turn to the concrete cases. Case I+, β = ϑ. We have t + 1 < β_{1} < t + 1 + 1/t, −1 − 1/t < β_{2} < −1, −1/t < β_{3} < 0. The largest integer n_{0} such that β_{i} + n_{0} < −1, i = 1, 2, 3 is n_{0} = −t − 3. The minimal polynomial of β − t − 3 is X^{3} + (2t + 9)X^{2} + (t^{2}11t + 24)X + 2t^{2} + 12t + 17. It is easy to check that the conditions of Theorem 2.3 are satisfied for this polynomial. If n = −t − 3 − k, k ≥ 0 then the difference of the minimal polynomial of β + n and of β − t − 3 is

3X^{2}k + (18k + 3k^{2} + 4tk)X + 9k^{2} + 24k + 11tk + t^{2}k + 2tk^{2} + k^{3},

thus the conditions of Theorem 2.3 remain true for the minimal polynomial of β + n, too. This solves the first case. Case I-, β = −ϑ. As −(t + 1 + 1/t) < −β_{1} < −(t + 1), 1 < −β_{2} < 1 + 1/t, 0 < −β_{3} < 1/t we may take n_{0} = −3. The minimal polynomial of −β − 3 is X^{3} + (t + 9)X^{2} + (24 + 5t)X + 6t + 19 and we can conclude that −β + n is a basis of a CNS if and only if n ≤ −3. Case II+, β = −tϑ+ϑ^{2}. The minimal polynomial of β is X^{3}−(2t+6)X^{2}+(t^{2}+7t+9)X−t^{2}−3t−1. Using the same order of conjugates as above we have t + 3 < β_{1} < t + 3 + 1/t, t + 2 < β_{2} < t + 2 + 1/t, 1 − 2/t < β_{3} < 1 hence we have to take n_{0} = −(t + 5). The minimal polynomial of β − t − 5 is X^{3} + (t + 9)X^{2} + (5t + 24)X + 6t + 19. Hence β + n is a basis of a CNS if and only if n ≤ −t − 5. Case II-, β = tϑ − ϑ^{2}. As −(t + 3 + 1/t) < β_{1} < −(t + 3), −(t + 2 + 1/t) < β_{2} < −(t + 2), −1 < β_{3} < −1 + 2/t we may take n_{0} = −1. The minimal polynomial of β − 1 is X^{3} + (2t + 9)X^{2} + (t^{2} + 11t + 24)X + 2t^{2} + 12t + 17. Hence β + n is a basis of a CNS if and only if n ≤ −1. Case III+, β = −(t + 1)ϑ + ϑ^{2}. It is easy to see that ϑ_{2} = −\frac{1}{ϑ+1} = ϑ^{2} − (t + 1)ϑ − 2, i.e. β = ϑ_{2}. In Case I+ we proved that ϑ + n is a CNS basis if and only if n ≤ −(t + 3). This implies that ϑ_{2} + n is a CNS basis if and only if n ≤ −(t + 3). As β + n = ϑ_{2} + n + 2 the element β + n is a CNS basis if and only if n + 2 ≤ −t − 3, i.e. n ≤ −t − 5. Case III-, β = (t + 1)ϑ − ϑ^{2}. Arguing analogously as in Case III+ we obtain that β + n is a CNS basis if and only if n ≤ −1. The theorem is completely proved. □

4.2 Canonical number systems in pure cubic fields

B. N. Delaunay [6]and T. Nagell [15] proved that if d ∈ lN is cube free then the diophantine equation

(3)  X^{3} − dY^{3} = 1

has at most one solution (x, y) ∈ Z^{2} with xy ≠ 0. Moreover, if d is square free then an integral basis of the algebraic number field K = Q(ϑ), ϑ = ^{3} \sqrt{d} is given by 1, ϑ, ϑ^{2} if d ≢ ±1 (mod 9) and 1, ϑ, (ϑ^{2} ± ϑ + 1)/3 otherwise. In the first case the index form equation of K is the diophantine equation (3), i.e. for β = n + xϑ + yϑ^{2} ∈ Z[ϑ] we have: Z[β] = Z[ϑ] if and only if (x, y) ∈ Z^{2} is a solution of (3). Generally, it is hard to decide when (3) has a non-trivial solution, i.e. one with xy ≠ 0. But in the special case d = m^{3} + 1 this is a simple task because (x, y) = (−m, −1). Therefore if d is square free and m ≢ 0 (mod 3) then ±ϑ + n and ±(ϑ^{2} + mϑ) + n (n ∈ Z) are the only generators of power integral bases of K. Choosing m = 3k ± 1, m is certainly not divisible by 3. Then d = 27k^{3} + 27k^{2} + 9k + 2. By a result of P. Erdős [7] there exist infinitely many values of k for which d is square-free. In these cases ϑ = ^{3} \sqrt{d} generates the maximal order Z_{K} of the algebraic number field K = Q(ϑ). Using these results our aim is to extend the results which S. Körmendi [13] achieved for the particular cubic number field Q( ^{3} \sqrt{2}). We can prove the following

Theorem 4.5 Let m be a positive integer not divisible by 3 such that d = m^{3} + 1 is square-free. Put ϑ = ^{3} \sqrt{d}. Then γ ∈ Z[ϑ] is the basis of a CNS in Z[ϑ] if and only if γ = ϑ + n, n ≤ −m − 2, γ = −ϑ + n, n ≤ 0, γ = ϑ^{2} + mϑ + n, n ≤ −2m^{2} − 2, γ = −(ϑ^{2} + mϑ) + n, n ≤ −m^{2} − 2.

Proof. As the case m = 1 has been treated by S. Körmendi ([13], see also [4]) we may assume m > 1. Case I+, γ = ϑ + n. The minimal polynomial of γ is X^{3} − 3nX^{2} + 3n^{2}X − m^{3} − n^{3} − 1. By Theorem 3.1 (iii) the inequality 3n^{2} + 3n ≤ −m^{3} − n^{3} − 3 must hold, which implies n ≤ −m − 2. If n ≤ −m − 2 then −3n < 3n^{2} < −m^{3} − n^{3} − 1, hence the converse follows from Theorem 2.3. Case I-, γ = −ϑ + n. The minimal polynomial of γ is X^{3} − 3nX^{2} + 3n^{2}X + m^{3} − n^{3} + 1. Hence clearly n ≤ 0 by Theorem 3.1 (i) if γ is a CNS basis. On the other hand if n = 0 then γ is a CNS basis by Theorem 3.8 (or by direct checking). Finally if n ≤ −1 the assertion follows from Theorem 2.3. Case II+, γ = ϑ^{2} + mϑ + n. The minimal polynomial of β is X^{3} − 3nX^{2} + (3n^{2} − 3m^{4} − 3m)X + 3m^{4}n − 2m^{6} − 3m^{3} − 1 + 3mn − n^{3}. Let γ be a CNS basis and define β = −n − 2m^{2}. Using ϑ > m we find β > 1 by Lemma 2.2. Thus n has the desired shape. The converse can easily be derived from Theorem 2.3. Case II-, γ = −(ϑ^{2} + mϑ) + n. The minimal polynomial of γ is X^{3} − 3nX^{2} + (3n^{2} − 3m^{4} − 3m)X + 3m^{4}n + 2m^{6} + 3m^{3} + 1 + 3mn − n^{3}. Let γ be a CNS basis. By Theorem 3.1 (ii) we find n ≤ −m^{2} and we exclude equality by Theorem 3.1 (i). The assumption n = −m^{2} −1 contradicts the fact p_{2} ≤ p_{0}. Conversely, firstly assume n ≤ −m^{2} − 3. Then our assertion follows from Theorem 2.3. Finally, if n = −m^{2} − 2 then we can easily apply Proposition 3.12 (5) to complete the proof. □

5 Concluding Remarks

Summing up the results of K. Scheicher and J.M. Thuswaldner [17] and of ours we conclude that Gilbert’s conjecture holds at least in the following cases:

(1) p_{1} = −1, 0, 1, p_{0}, p_{0} + 1,

(2) 1 ≤ p_{2} ≤ p_{1} ≤ p_{0} − 1,

(3) 1 + |p_{1}| + p_{2} < p_{0},

(4) 1 ≤ p_{1} ≤ p_{0} − 1 and 0 ≤ p_{2} ≤ (2p_{0} − 1)/3. The problem of characterizing CNS polynomials seems to be a hard one — it may even not be solved algebraically. Trivially, in case of non linear polynomials the conditions on the roots of the polynomial stated in Lemma 2.2 do not imply that the given polynomial is a CNS polynomial (e.g. the roots of the non CNS polynomial X^{2} − 2X + 2 are 1 ± \sqrt{−1}). The class of CNS polynomials is not closed under addition (of polynomials of different degrees) or multiplication: By ([1], Theorem 3) the square of the CNS polynomial X^{2} − X + p_{0} is not a CNS polynomial in case p_{0} ≥ 5; the sum X^{3} + 5X^{2} − 3X + 8 of the CNS polynomials X^{3} + 4X^{2} − 5X + 6 (see Proposition 3.2) and X^{2} +2X +2 (see [9], Theorem 1) is not a CNS polynomial since the element (1, −1, −1) is periodic.

References

[1] S. Akiyama and A. Pethő, On canonical number systems, Theoret. Comp. Sci. 270, 921 – 933 (2002).

[2] S. Akiyama and H. Rao, New criteria for canonical number systems, preprint

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

[4] H. Brunotte, On trinomial bases of radix representations of algebraic integers, Acta Sci. Math. (Szeged) 67, 521 – 527 (2001).

[5] H. Brunotte, Characterization of CNS trinomials, Acta Sci. Math. (Szeged), to appear [6] B. N. Delaunay, Vollständige Lösung der unbestimmten Gleichung X^{3}q + Y^{3} = 1 in

ganzen Zahlen, Math. Z. 28, 1 – 9 (1928).

[7] P. Erdős, Arithmetical properties of polynomials, J. London Math. Soc. 28, 416-425 (1953).

[8] I. Gaál, Diophantine equations and power integral bases - New computational methods, Birhäuser Verlag, 2002.

[9] W.J. Gilbert, Radix representations of quadratic fields, J. Math. Anal. and Appl. 83, 264 – 274 (1981).

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

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

[12] B. Kovács, Canonical number systems in algebraic number fields, Acta Math. Hung. 37, 405 – 407 (1981).

[13] S. Körmendi, Canonical number systems in Q( ^{3} \sqrt{2}), Acta Sci. Math. (Szeged) 50, 351 – 357 (1986).

[14] M. Mignotte, Verification of a conjecture of E. Thomas, J. Number Theory 44, 172 – 177 (1993).

[15] T. Nagell, Zur Theorie der kubischen Irrationalitäten, Acta Math. 55, 33 – 65 (1930).

[16] 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, 31 – 44 (1991).

[17] K. Scheicher and J. M. Thuswaldner, On the characterization of canonical number systems, preprint.

[18] E. Thomas, Solutions to certain families of Thue equations, J. Number Theory 43, 319–369 (1993).