Notes on CNS polynomials and integral interpolation

Attila Pethő^{∗}

Dedicated to the 70th birthday of Professors Vera Sós and András Hajnal.

1 Introduction

1.1 CNS polynomials

Let P (x) = p_{d}x^{d} + ⋯ + p_{0} ∈ ℤ[x], with p_{d}=1. It is called a CNS polynomial if every element of the factor ring R = ℤ[x]/P (x)ℤ(x) has a unique representative of form

∑_{i=0}^{ℓ} a_{i}x^{i}, 0 ≤ a_{i} < |p_{0}|, 0 ≤ i ≤ ℓ.  (1)

This definition is equivalent with the following one: for any A(x) ∈ ℤ[x] there exist uniquely integers ℓ, 0 ≤ a_{i} < |p_{0}|, 0 ≤ i ≤ ℓ, p_{ℓ} ≠ 0 if ℓ > 0, such that

A(x) ≡ ∑_{i=0}^{ℓ} a_{i}x^{i} (mod P).  (2)

In the sequel the polynomial staying on the right hand side of (2) will be called the CNS representation of A(x).

It is clear that there exist for any A(x) ∈ ℤ[x] unique integers, A_{0}, …, A_{d}, such that

A(x) ≡ ∑_{i=0}^{d−1} A_{i}x^{i} (mod P).  (3)

One gets ∑_{i=0}^{d−1} A_{i}x^{i} from A(x) by dividing it by P (x). In contrast one obtains

∑_{i=0}^{ℓ} a_{i}x^{i} from A(x) by a “backward” division process with P (x). More precisely, let A(x) = ∑_{i=0}^{∞} A_{i}x^{i} ∈ ℤ[x], A_{i} = 0 for all but finitely many indices, and let

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

T (A) = ∑_{i=0}^{∞} (A_{i+1} − p_{i+1} ⌊\frac{A_{0}}{p_{0}} ⌋) x^{i},

where ⌊x⌋ denotes the integer part of x. Then

A(x) = A_{0} − p_{0} ⌊\frac{A_{0}}{p_{0}} ⌋ + xT (A).

To obtain the CNS representation of A one has to compute T (A), T^{2}(A), … until T^{ℓ}(A) = 0 for some ℓ ≥ 0.

Unfortunately this “backward” division process often does not serve finite representation; it can become divergent (e.g. −1 for P (x) = x^{2} + 4x + 2) or ultimately periodic (e.g. −1 for P (x) = x − 2). Therefore the characterization of CNS polynomials is not a trivial problem. In the sequel the set of CNS polynomials will be denoted by C.

The concept of CNS polynomials was introduced in [14] as a generalization of canonical number systems [7], [6], [8] or radix representations [5] in algebraic number fields. Generalizing a result of [9] I gave the following algorithmic characterization of square-free CNS polynomials [14].

Theorem AR. Let P (x) ∈ ℤ[x] be square-free. Let α_{1}, …, α_{d} and D denote its zeroes and discriminant respectively. Then P (x) ∈ C if and only if

(i) |α_{i}| > 1 and α_{i} < −1, if α_{i} ∈ ℝ, 1 ≤ i ≤ d,

(ii) every A(x) = ∑_{i=0}^{d−1} A_{i}x^{i} ∈ ℤ[x] with

|A_{i}| ≤ |D|^{−2}(dh(P)^{d−1})^{d/2} max_{1≤j≤d} \frac{|α_{j}|}{|α_{j}| − 1}, i = 0, …, d − 1

has a CNS representation. Here h(P) denotes the maximum of the absolute values of the coefficients of P (x).

This result was generalized for not necessarily square-free polynomials, but without giving an explicit upper bound for the A_{i}′s in [3].

By changing the basis 1, x, …, x^{d−1} of R to ω_{1}, ω_{2}, …, ω_{d} where ω_{i} =

∑_{j=0}^{i} p_{d−j}x^{j}, i = 1, …, d, H. Brunotte [4] realized that the CNS property

of polynomials can be characterized by properties of the mapping τ : ℤ^{d} → ℤ^{d},

τ((a_{1}, …, a_{d})^{T} ) = (− ⌊\frac{a_{1}p_{1} + ⋯ + a_{d}p_{d}}{p_{0}} ⌋ , a_{1}, …, a_{d−1})^{T} .  (4)

His original algorithm was simplified in [3]. We give here the version appeared in [1, Lemma 2.6].

Lemma B. Let E ⊆ ℤ^{d} has the following properties

(i) (1, 0, …, 0) ∈ E,

(ii) −E ⊆ E,

(iii) τ(E) ⊆ E,

(iv) for every e ∈ E there exists some k ∈ ℕ with τ^{k}(e) = 0.

Then P ∈ C.

Akiyama and Rao [3] pointed out, that if all zeroes of P (x) are lying outside the closed unit disc then τ is ultimately contractive, i.e. there exists a finite set E ⊆ ℤ^{d} satisfying (i)–(iii) of Lemma B. Their argument is based on Theorem AR and the connection between the mappings T and τ. Here we will give a direct proof of the following theorem.

Theorem 1. Let P (x) be such that all of its zeroes are lying outside the closed unit disc. Then there exists a constant c depending only on d and H(P) such that if

E = {(a_{1}, …, a_{d})^{T} ∈ ℤ^{d} : max{|a_{i}|, 1 ≤ i ≤ d} ≤ c}

then there exist for any b ∈ ℤ^{d} a, k ∈ ℕ with τ^{k}(b) ∈ E.

In the case when P (x) is square-free, i.e. P (x) has no multiple roots, we are able to give a nice explicit form for c.

Theorem 2. Let P (x) be square-free and denote α_{1}, …, α_{d} its zeros. Assume that |α_{i}| > 1, 1 ≤ i ≤ d. Then we may take

c = ⌊p_{0} ∑_{i=1}^{d} \frac{|α_{i}|^{d−1}}{(|α_{i}| − 1)|P′(α_{i})|}⌋ ,

where P′(x) denotes the derivative of P (x).

1.2 Integral interpolation

Let m_{1}, …, m_{d} ∈ ℤ be pairwise distinct and a_{1}, …, a_{d} ∈ ℤ. We call a = (a_{1}, …, a_{d})^{T} ∈ ℤ^{d} integral interpolable by m = (m_{1}, …, m_{d})^{T} it there exists an I(x) ∈ ℤ(x) such that

I(m_{i}) = a_{i}, i = 1, …, d.  (5)

It is well known that there exists always an I(x) ∈ ℚ[x] satisfying (5), but very often I(x) has non-integer coefficients. The Chinese remainder theorem (see e.g. Mignotte and Stefanescu [12] ) gives necessary and sufficient condition for the solvability of the integral interpolation problem, but it is usually very complicated. We are intend to give here an other condition based on CNS polynomials.

The vector a ∈ ℤ^{d} is called simultaneously representable by m ∈ ℤ^{d} if there exist integers 0 ≤ q_{0}, …, q_{ℓ} < M = |m_{1} … m_{d}| such that

a_{i} = ∑_{j=0}^{ℓ} q_{j}m_{i}^{j},  i = 1, …, d.  (6)

This concept was introduced by Indlekofer, Kátai and Racskó [11].

We start with a simple observation.

Proposition 1. If a ∈ ℤ^{d} is simultaneously representable by m then it is integral interpolable by m.

Proof. If (6) holds then take I(x) = ∑_{j=0}^{ℓ} q_{j}x^{j} ∈ ℤ[x], which satisfies obvi-

ously (5).

The converse of Proposition 1 is not true. Take for example m_{1} = 1, m_{2} = 2, then for any pair (a_{1}, a_{2})^{T} ∈ ℤ^{2} the polynomial I(x) = (a_{2} − a_{1})x + (2a_{1} − a_{2}) satisfies (5). On the other hand, if a_{1} or a_{2} is negative, then (6) can never hold, because its right hand side is always non-negative.

The next theorem connects integral interpolation, simultaneous representation and CNS polynomials.

Theorem 3. Let P (x) = ∏_{i=1}^{d}(x − m_{i}) ∈ C. Then a ∈ ℤ^{d} is simultaneously

representable by m if and only if it is integral interpolable by m.

Proof. By Proposition 1 it is enough to consider the case, when a is integral interpolable by m. Then there exists an I(x) ∈ ℤ[x] satisfying (5). As P (x) is a CNS polynomial, whose constant term is (−1)^{d}m_{1} … m_{d}, there exist integers 0 ≤ q_{0}, …, q_{ℓ} < M = |m_{1} … m_{d}| such that

I(x) = ∑_{j=0}^{ℓ} q_{j}x^{j} (mod P (x)),

which means

I(x) = ∑_{j=0}^{ℓ} q_{j}x^{j} + Q(x)P (x)

with a Q(x) ∈ ℤ[x]. Substituting here x = m_{1}, …, m_{d} and using (5) and P (m_{i}) = 0, i = 1, …, d we obtain (6).

Remark that if P (x) = ∏_{i=1}^{d}(x − m_{i}) ∉ C then there exist infinitely many a ∈

ℤ^{d} which is integral interpolable by m, but not simultaneously representable. Indeed, as P ∉ C there exists I(x) ∈ ℤ[x] of degree less then d, which does not have a CNS representation with respect to P (x). Choosing a_{i} = I(m_{i}), i = 1, …, d the vector a = (a_{1}, …, a_{d})^{T} is integral interpolable by m. If a would be simultaneously representable by m then there would exist integers 0 ≤ q_{1}, …, q_{ℓ} < M such that

a_{i} = ∑_{j=0}^{ℓ} q_{j}m_{i}^{j}, i = 1, …, d.

Taking J(x) = ∑_{j=0}^{ℓ} q_{j}x^{j} then I(x) ≡ J(x) mod (x − m_{i}), i = 1, …, d hold and

as the polynomials x−m_{i} are pairwise relatively primes I(x) ≡ J(x) (mod P (x)) by the chinese remainder theorem. Hence J(x) would be the CNS representation of I(x) with respect to P (x) which is a contradiction. Hence a is not integral representable by m.

Let Q(x) = ∑_{i=0}^{h} q_{i}x^{i} ∈ ℤ[x] with 0 ≤ q_{i} < M. Then I_{Q}(x) = Q(x)+x^{h+1}I(x)

does not have a CNS representation because T^{h+1}(I_{Q}(x)) = I(x). The set

S = {(a_{Q_{1}}, …, a_{Q_{d}}) : a_{Q_{i}} = I_{Q}(m_{i}), Q as above}

is obviously infinite. The elements of S are not simultaneously representable by m.

In the sequel we will prove under some assumptions that ∏_{i=1}^{d}(x−m_{i}) belongs

to C.

Theorem 4. Let m_{1}, …, m_{d} ≤ −2 be such that

∑_{i=1}^{d} \frac{1}{|m_{i}|} ≤ 1.

Then P (x) = ∏_{i=1}^{d}(x − m_{i}) ∈ C.

Proof. Let ∏_{i=1}^{d}(x − m_{i}) = x^{d} + p_{d−1}x^{d−1} + ⋯ + p_{0}. By the assumptions all

coefficients of P (x) are positive. We have p_{j} = ∑_{1≤i_{1}<···<i_{d−j}≤d} |m|_{i_{1}} … |m|_{i_{d−j}},

j = 0, …, d − 1. Further

(\frac{p_{j}}{\binom{d}{j}})^{2} ≥ \frac{p_{j+1}}{\binom{d}{j+1}} · \frac{p_{j−1}}{\binom{d}{j−1}},  j = 0, …, d − 2  (7)

hold by Newton’s inequality between symmetric means. (See [10, p. 52] or the original work of I. Newton [13].)

We have

\frac{p_{1}}{p_{0}} = ∑_{i=1}^{d} \frac{1}{|m_{i}|} ≤ 1,

i.e. p_{0} ≥ p_{1}. Assume that we proved already p_{0} ≥ p_{1} ≥ ⋯ ≥ p_{j} for some 1 ≤ j < d − 2. Applying (7) we obtain

p_{j+1} ≤ \binom{d}{j − 1} · \binom{d}{j + 1} · \binom{d}{j}^{−2} · \frac{p_{j}}{p_{j−1}} · p_{j} < p_{j}.

The theorem is proved.

In the next theorem we show that the same assertion is true if d is small.

Theorem 5. Let d ≤ 4 and m_{1}, …, m_{d} ≤ −2 be pairwise distinct integers.

Then P (x) = ∏_{j=1}^{d}(x − m_{j}) ∈ C.

To prove Theorem 5 we need a lemma.

Lemma 1. Let P (x) = x^{4} + p_{3}x^{3} + p_{2}x^{2} + p_{1}x + p_{0} ∈ ℤ[x] be such that

(i) p_{1} > p_{0} > p_{1} − p_{2}/2 + p_{3},

(ii) p_{1} ≤ 2p_{2} ≥ 8p_{3}, p_{3} ≤ 3.

Then P (x) ∈ C.

Proof. Consider the following set of quadruples

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

and put E = E_{0} ∪−E_{0}. Notice that if (a_{1}, a_{2}, a_{3}, a_{4})^{T} ∈ E, then a_{i}a_{j mod 4} ≤ 0 and if a_{i} = ±2, then a_{i+1} ≠ 0. It is easy to see that E satisfies the conditions (i) and (ii) of Lemma B. It remains to show (iii) and (iv), which will be done by considering several cases. If τ(e_{1}) = e_{2}, then we will write e_{1} → e_{2}. Further e →^{A} means that τ(e) belongs to case A considered earlier.

I (0, 1, a_{3}, a_{4}) ⟶ (0, 0, 1, a_{3}) ⟶ (0, 0, 0, 1) ⟶ 0

II a_{2} < 0, (1, a_{2}, a_{3}, a_{4}) ⟶ (0, 1, a_{2}, a_{3}) ⟶^{I}

III a_{1} > 0, (−1, a_{2}, a_{3}, a_{4}) ⟶ (1, −1, a_{2}, a_{3}) ⟶^{II}

IV (1, 0, a_{3}, a_{4}) ⟶ \{ \begin{matrix}(−1, 1, 0, a_{3}) ⟶^{III}, & if p_{1} + a_{3}p_{3} + a_{4} > p_{0} \\ (0, 1, 0, a_{3}) ⟶^{I} & otherwise \end{matrix}

V (2, a_{2}, a_{3}, a_{4}) ⟶ (−1, 2, a_{2}, a_{3}) ⟶^{III}

VI (0, −1, a_{3}, a_{4}) ⟶ (1, 0, −1, a_{3}) ⟶^{IV}

VII (0, 0, −1, a_{4}) ⟶ (1, 0, 0, −1) ⟶^{IV}

VIII (0, 0, 0, −1) ⟶ (1, 0, 0, 0) ⟶^{IV}

IX (−2, a_{2}, a_{3}, a_{4}) ⟶ (2, −2, a_{2}, a_{3}) ⟶^{V}

This shows that (iii) and (iv) hold for our set E, hence P (x) ∈ C. Proof of Theorem 5. If ∑_{i=1}^{d} \frac{1}{|m_{i}|} ≤ 1 then the assertion follows from Theorem 4.

If d ≤ 3 then ∑_{i=1}^{d} \frac{1}{|m_{i}|} ≤ 1 holds except when (m_{1}, m_{2}, m_{3}) = (−2, −3, −4), (−2, −3, −5). The corresponding polynomials x^{3}+9x^{2}+26x+24 and x^{3}+10x^{2}+ 31x + 30 belong to C by Proposition 3.12 (3) and (1) of [2].

Let d = 4. Then there are three infinite families (m_{1}, m_{2}, m_{3}, m_{4}) = (−2, −3, −4, −m), (−2, −3, −5, −m) and (−2, −3, −6, −m) with m = 5, 6 and 7 respectively and 64 further values

\begin{matrix}(−2, −3, −7, −m), & 8 ≤ m ≤ 41, \\ (−2, −3, −8, −m), & 9 ≤ m ≤ 23, \\ (−2, −3, −9, −m), & 10 ≤ m ≤ 17, \\ (−2, −3, −10), & 11 ≤ m ≤ 14 and \\ (−2, −3, −11, −m), & 12 ≤ m ≤ 13 \end{matrix}

for which ∑_{i=1}^{4} \frac{1}{|m_{i}|} > 1.

It is easy to see that the corresponding polynomials satisfy the assumptions of Lemma 1, thus they belong to C. □

Using the method of the proof of Theorem 5 one could probably prove the same assertion for d = 5 too. Unfortunately the number of cases, which must be handled separately is much larger, one has three two parametric and 64 one parametric families and a lot of sporadic cases. Hence we need new ideals.

On the other hand, in light of Theorems 4 and 5 we do not see any reason not to formulate the following conjecture.

Conjecture 1. Let m_{1}, …, m_{d} ≤ −2 be pairwise distinct integers. Then P (x) =

∏_{i=1}^{d}(x − m_{i}) ∈ C.

2 Proof of Theorems 1 and 2

To prove Theorems 1 and 2 we need some preparation from linear algebra and from linear recurring sequences. More precisely we have to analyze the mapping τ defined by equation (4). For a ∈ ℤ^{d} let us define

τ^{k}(a) = \begin{cases}a, & if k = 0, \\ τ(τ^{k−1}(a)), & if k > 0. \end{cases}

Further let P ∈ ℤ^{d×d} be the matrix

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

With these definitions we have the following assertion

Lemma 2. Let a = (a_{1}, …, a_{d})^{T} ∈ ℤ^{d} and 1 ≤ k ∈ ℤ. Then τ^{k}(a) ∈ ℤ^{d} and there exist −1 < δ_{1}, …, δ_{k} ≤ 0 such that

τ^{k}(a) = P^{k}a + ∑_{j=1}^{k} P^{k−j}δ_{j}

holds, where δ_{j} = (δ_{j}, 0, …, 0)^{T} ∈ ℝ^{d}.

Proof. Let k = 1. Then τ(a) ∈ ℤ^{d}, which can be written in the form

τ(a) = (−\frac{a_{1}p_{1} + ⋯ + a_{d}p_{d}}{p_{0}} + δ_{1}, a_{1}, …, a_{d−1})^{T} = Pa + δ_{1},

where δ_{1} = (δ_{1}, 0, …, 0)^{T} ∈ ℝ^{d} with −1 < δ_{1} ≤ 0.

Assume that the assertion is true for k − 1 ≥ 0. Then τ^{k−1}(a) ∈ ℤ^{d}, thus τ^{k}(a) ∈ ℤ^{d} is true by (4) too. Let τ^{k−1}(a) = (a_{1}^{(k−1)}, …, a_{d}^{(k−1)})^{T} ∈ ℤ^{d} then

τ^{k}(a) = (− ⌊\frac{a_{1}^{(k−1)}p_{1} + ⋯ + a_{d}^{(k−1)}p_{d}}{p_{0}} ⌋ , a_{1}^{(k−1)}, …, a_{d−1}^{(k−1)})^{T}

= (−\frac{a_{1}^{(k−1)}p_{1} + ⋯ + a_{d}^{(k−1)}p_{d}}{p_{0}} + δ_{k}, a_{1}^{(k−1)}, …, a_{d−1}^{(k−1)})^{T} ,

where δ_{k} satisfies the inequalities −1 < δ_{k} ≤ 0 by the definition of the integer part function. Thus

τ^{k}(a) = Pτ^{k−1}(a) + (δ_{k}, 0, …, 0)^{T}

and by the induction hypothesis the assertion of the lemma follows.

Let {G_{n}}_{n=0}^{∞} be the linear recurring sequence defined by the initial terms G_{0} = … G_{d−2} = 0, G_{d−1} = 1 and by the difference equation

G_{n+d} = −\frac{p_{1}}{p_{0}} G_{n+d−1} − ⋯ − \frac{p_{d}}{p_{0}} G_{n}.  (8)

Let further G_{n} = (G_{n+d−1}, …, G_{n})^{T} and for n ≥ d − 1 denote by G_{n} the d × d matrix, whose columns are G_{n}, …, G_{n−d+1}. Then we have obviously

G_{n} = PG_{n−1} for n = d, d + 1, ….

This implies

G_{n+d−1} = P^{n} G_{d−1}  for n ≥ 0.  (9)

As G_{d−1} is a non singular matrix we obtain

P^{n} = G_{n+d−1}G_{d−1}^{−1}.  (10)

On the other hand if β_{1}, …, β_{h} denote the distinct zeroes of the polynomial

P^{∗}(x) = x^{d} + \frac{p_{1}}{p_{0}} x^{d−1} + ⋯ + \frac{p_{d}}{p_{0}} = x^{d}P (\frac{1}{x})

with multiplicity e_{1}, …, e_{h} ≥ 1, then

G_{n} = g_{1}(n)β_{1}^{n} + ⋯ + g_{h}(n)β_{h}^{n}  (11)

hold for any n ≥ 0, where g_{i}(x), 1 ≤ i ≤ h denote polynomials with coefficients of the field ℚ(β_{1}, …, β_{h}) of degree at most e_{i} − 1. (See [15].)

Denoting by p_{ij}^{(n)}, 1 ≤ i, j ≤ d, n ≥ 0 the entries of P^{n} then (10) and (11) imply

p_{ij}^{(n)} = ∑_{ℓ=1}^{h} g_{ijℓ}(n)β_{ℓ}^{n}.  (12)

Proof of Theorem 1. As we explained in the introduction it is enough to consider polynomials of degree at most d − 1, say

A(x) = ∑_{i=0}^{d−1} a_{i}x^{i}, a_{i} ∈ ℤ.

Let a = (a_{0}, …, a_{d−1})^{T} ∈ ℤ^{d}. We have to prove that there exists a k ≥ 0 such that τ^{k}(a) ∈ E. From the proof it will be clear how to choose the constant c.

Let k ≥ 1. Then there exist by Lemma 2 −1 < δ_{1}, …, δ_{k} ≤ 0 such that

τ^{k}(a) = P^{k}a + ∑_{j=1}^{k} P^{k−j}δ_{j}.  (13)

In the sequel let τ^{k}(a)_{i} denote the i-th coordinate of τ^{k}(a). Then (13) implies

τ^{k}(a)_{i} = ∑_{j=1}^{d} p_{ij}^{(k)}a_{j} + ∑_{j=1}^{k} p_{i1}^{(k−j)}δ_{j}.

Observe that by (9) the first column of P^{n} is exactly G_{n}. Using this, (11), (12) and the last equation we obtain

τ^{k}(a)_{i} = ∑_{j=1}^{d} a_{j} ∑_{ℓ=1}^{h} g_{ijℓ}(k)β_{ℓ}^{k} + ∑_{ℓ=1}^{h} ∑_{j=0}^{k−1} δ_{k−j}g_{ℓ}(j)β_{ℓ}^{i}.

Thus

|τ^{k}(a)_{i}| ≤ ∑_{j=1}^{d} |a_{j}| ∑_{ℓ=1}^{h} |g_{ijℓ}(k)| |β_{ℓ}|^{k} + ∑_{ℓ=1}^{h} ∑_{j=0}^{k−1} |δ_{k−j}| |g_{ℓ}(j)| |β_{ℓ}|^{j}.  (14)

The roots of P^{∗}(x) are the reciprocal of the roots of P (x), hence |β_{ℓ}| < 1, 1 ≤ ℓ ≤ h. If k is large enough then the first summand of (14) is less than 1. Similarly, there exists a j_{0} such that if j > j_{0} then |g_{ℓ}(j)| |β_{ℓ}|^{j} < |β_{ℓ}|^{j/2}. As |δ_{j}| ≤ 1, j ≥ 1 we can estimate the second summand of (14) as follows

∑_{ℓ=1}^{h} ∑_{j=0}^{k−1} |δ_{k−j}| |g_{ℓ}(j)| |β_{ℓ}|^{j} ≤ ∑_{ℓ=1}^{h} ∑_{j=0}^{j_{0}} |g_{ℓ}(j)| |β_{ℓ}|^{j} + ∑_{ℓ=1}^{h} ∑_{j=j_{0}+1}^{j_{0}} |β_{ℓ}|^{j/2}

≤ ∑_{ℓ=1}^{h} ∑_{j=0}^{j_{0}} |g_{ℓ}(j)| |β_{ℓ}|^{j} + ∑_{ℓ=1}^{h} \frac{|β_{ℓ}|^{(j_{0}+1)/2}}{1 − |β_{ℓ}|^{1/2}} .

Hence, taking

c = 1 + ∑_{ℓ=1}^{h} ∑_{j=0}^{j_{0}} |g_{ℓ}(j)| |β_{ℓ}|^{j} + ∑_{ℓ=1}^{h} \frac{|β_{ℓ}|^{(j_{0}+1)/2}}{1 − |β_{ℓ}|^{1/2}}

then

|τ^{k}(a)_{i}| ≤ c

and c depends only on the height and degree of P (x). □

To prove Theorem 2 we need one more lemma

Lemma 3. Let the linear recurring sequence {G_{n}}_{n=0}^{∞} be defined by (8). Assume that P (x) is square-free and denote α_{1}, …, α_{d} its roots. Then

G_{n} = −p_{0} ∑_{h=1}^{d} \frac{α_{h}^{d−n−2}}{P′(α_{h})} .

Proof. By a result of M. Ward [16] we have

G_{n} = ∑_{h=1}^{d} \frac{β_{h}^{n}}{P^{∗′}(β_{h})}.

As β_{h} = \frac{1}{α_{h}}, h = 1, …, d and

P^{∗′}(β_{h}) = ∏_{{j=1 \atop j≠h}}^{d}(β_{h} − β_{j}) = ∏_{{j=1 \atop j≠h}}^{d} (\frac{1}{α_{h}} − \frac{1}{α_{j}} ) = \frac{(−1)^{2d−1}}{p_{0}α_{h}^{d−2}} ∏_{{j=1 \atop j≠h}}^{d}(α_{h} − α_{j}).

Proof of Theorem 2. We are using the notations introduced in the proof of Theorem 1. As the roots of P (x) are simple the polynomials g_{ijℓ}(x) are constants. Further β_{h} = 1/α_{h}, h = 1, …, d. After these preparations, using also Lemma 3 inequality (14) can be rewritten as

|τ^{k}(a)_{i}| ≤ ∑_{j=1}^{d} |a_{j}| ∑_{ℓ=1}^{d} |g_{ijℓ}| |\frac{1}{α_{ℓ}} |^{k} + ∑_{ℓ=1}^{d} ∑_{j=0}^{k−1} |δ_{k−j}p_{0}|\frac{|α_{ℓ}|^{d−2}}{|p′(α_{ℓ})|}|α_{ℓ}|^{−j}.

Now there exists for any ε > 0 a k_{0} such that if k > k_{0} then the first summand is less than ε. For the second summand we obtain

∑_{ℓ=1}^{d} |p_{0}|\frac{|α_{ℓ}|^{d−2}}{|p′(α_{ℓ})|} ∑_{j=0}^{k−1} |δ_{k−j}| |α_{ℓ}|^{−j} ≤ ∑_{ℓ=1}^{d} |p_{0}|\frac{|α_{ℓ}|^{d−2}}{|p′(α_{ℓ})|} · \frac{1}{1 − \frac{1}{|α_{ℓ}|}}

= |p_{0}| ∑_{ℓ=1}^{d} \frac{|α_{ℓ}|^{d−1}}{(|α_{ℓ}| − 1)|p′(α_{ℓ})|}.

Hence

|τ^{k}(a)_{i}| ≤ ε + |p_{0}| ∑_{ℓ=1}^{d} \frac{|α_{ℓ}|^{d−1}}{(|α_{ℓ}| − 1)|p′(α_{ℓ})|}.

As τ^{k}(a)_{i} ∈ ℤ and ε can be chosen arbitrary small we obtain

|τ^{k}(a)_{i}| ≤ ⌊|p_{0}| ∑_{ℓ=1}^{d} \frac{|α_{ℓ}|^{d−1}}{(|α_{ℓ}| − 1)|p′(α_{ℓ})|}⌋. □

References

[1] Sh. Akiyama, H. Brunotte and A. Pethő, Cubic CNS polynomials, notes on a conjecture of W.J. Gilbert, J. Math. Anal. and Appl., submitted.

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

[3] Sh. Akiyama and H. Rao, New criteria for canonical number systems, preprint

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

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

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

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

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

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

[10] G. Hardy, J.E. Littlewood and G. Pólya, Inequalities, Cambridge the University Press, 2nd ed. 1952.

[11] K.-H. Indlekofer, I. Kátai and P. Racskó, Number systems and fractal geometry, Probability theory and applications, Essays to the Mem. of J. Mogyordi, Math. Appl. 80, 319 – 334 (1992).

[12] M. Mignotte and D. Stefanescu, Polynomials: an algorithmic approach, Singapore: Springer, 1999.

[13] I. Newton, Arithmetica universalis: sive de compositione et resolutione arithemetic liber, 1701.

[14] 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)

[15] T.N. Shorey and R. Tijdeman, Exponential Diophantine Equations, Cambridge Univ. Press 1986.

[16] M. Ward, The maximal prime divisors of linear recurrences, Can. J. Math. 6 (1954) 455–462.

Department of Computer Science University of Debrecen H-4010 Debrecen P.O. Box 12, Hungary

email:pethoe@math.klte.hu