BRICS RS-97-44 G. S. Frandsen: On the Density of Normal Bases in Finite Fields BRICS

Basic Research in Computer Science

On the Density of Normal Bases in Finite Fields

Gudmund Skovbjerg Frandsen BRICS Report Series RS-97-44 ISSN 0909-0878 December 1997 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1997, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/97/44/

On the Density of Normal Bases in Finite Fields^{∗}

Gudmund Skovbjerg Frandsen

BRICS^{†}

Department of Computer Science University of Aarhus Ny Munkegade DK-8000 Aarhus C DENMARK.

                gudmund@brics.dk

Abstract

Let 𝔽_{q^{n}} denote the finite field with q^{n} elements, for q being a prime power. 𝔽_{q^{n}} may be regarded as an n-dimensional vector space over 𝔽_{q}. α ∈ 𝔽_{q^{n}} generates a normal basis for this vector space (𝔽_{q^{n}} : 𝔽_{q}), if {α, α^{q}, α^{q^{2}}, …, α^{q^{n−1}}} are linearly independent over 𝔽_{q}. Let N(q, n) denote the number of elements in 𝔽_{q^{n}} that generate a normal basis for 𝔽_{q^{n}} : 𝔽_{q}, and let ν(q, n) = \frac{N(q,n)}{q^{n}} denote the frequency of such elements.

We show that there exists a constant c > 0 such that

ν(q, n) ≥ c\frac{1}{\sqrt{⌈log_{q} n⌉}}, for all n, q ≥ 2

and this is optimal up to a constant factor in that we show

0.28477 ≤ lim_{n→∞} inf ν(q, n)\sqrt{log_{q} n} ≤ 0.62521, for all q ≥ 2

We also obtain an explicit lower bound:

ν(q, n) ≥ \frac{1}{e⌈log_{q} n⌉}, for all n, q ≥ 2

∗Supported by the ESPRIT Long Term Research Programme of the EU, under project number 20244 (ALCOM-IT)

†Basic Research in Computer Science, Centre of the Danish National Research Foundation.

1 Introduction

When implementing arithmetic in a finite field 𝔽_{q^{n}}, one may represent elements in 𝔽_{q^{n}} as n-vectors over 𝔽_{q}. In this way addition becomes coefficient-wise addition on the n-vectors. Multiplication may be more or less difficult depending on the basis chosen. Any basis on the form {α, α^{q}, α^{q^{2}}, …, α^{q^{n−1}}} where α ∈ 𝔽_{q^{n}} is called a normal basis. When using a normal basis, raising to the q’th power is simply a cyclic shift of the coordinates in the vector representation. This has motivated an interest in normal bases.

According to the historical remarks in Bach and Shallit [1], Eisenstein [4] stated as early as 1850 that any finite field has a normal basis, and Hensel [7] published an explicit characterisation of the number of distinct normal bases in 1888. We describe the characterisation here, since our later analysis will build upon it. Our terminology is partly borrowed from Lidl and Niederreiter [9].

We need a function Φ_{q} that is an analogue of Euler’s ϕ-function, but defined for polynomials over 𝔽_{q}.

Definition 1 For f ∈ 𝔽_{q}[x], define Φ_{q}(f) to be the number of polynomials g ∈ 𝔽_{q}[x] such that (i) deg(g) < deg(f) and (ii) gcd(f, g) = 1.

Let N(q, n) denote the number of elements in 𝔽_{q^{n}} that generate a normal basis for 𝔽_{q^{n}} : 𝔽_{q}. The characterisation is N(q, n) = Φ_{q}(x^{n} − 1).

The bounds c\frac{n}{ln ln n} ≤ ϕ(n) ≤ n on Eulers ϕ-function are wellknown. There are similar bounds on Φ_{q}(f). The upper bound Φ_{q}(f) ≤ q^{n} is trivial and in Section 2, we prove the lower bound:

Theorem 2 For any finite field 𝔽_{q} and for any polynomial f ∈ 𝔽_{q}[x] of degree n ≥ 2 and such that f(0) ≠ 0, we have

Φ_{q}(f) ≥ \frac{q^{n}}{e⌈log_{q} n⌉}.

In particular, the theorem translates to a bound on the frequency ν(q, n) of normal basis elements for 𝔽_{q^{n}} : 𝔽_{q}, since ν(q, n) = \frac{N(q,n)}{q^{n}} = Φ_{q}(x^{n} − 1) · q^{−n} ≥ \frac{1}{e⌈log_{q} n⌉}.

This result improves the lower bound on ν(q, n) given by von zur Gathen and Giesbrecht [11] by a constant factor.

However, there is an asymptotically stronger bound for Φ_{q}(x^{n} −1). In Section 3, we prove the following result:

Theorem 3 There is a constant c_{1} such that

ν(q, n) ≥ .28477\frac{1}{\sqrt{log_{q} n}}, for all q ≥ 2 and n ≥ q^{c_{1}}.

Combining this asymptotic bound with the simple bound ν(q, n) ≥ \frac{1}{e⌈log_{q} n⌉} for all q, n leads to an absolute bound:

Corollary 4 There is a constant c such that

ν(q, n) ≥ c\frac{1}{\sqrt{⌈log_{q} n}⌉}, for all q, n ≥ 2.

In Section 4, we show the preceding result to be optimal in that

Theorem 5 For every primepower q,

ν(q, n) < .62521\frac{1}{\sqrt{log_{q} n}}, for infinitely many n.

2 A general lower bound for Φ_{q}(f)

We will use a multiplicative characterisation of Φ_{q}(f). Let f ∈ 𝔽_{q}[x] with f(0) ≠ 0 have the complete factorisation f = ∏_{i=1}^{t} f_{i}^{e_{i}} over 𝔽_{q} (i.e. the irreducible factors f_{i}, f_{j} are distinct, when i ≠ j). Then

Φ_{q}(f) = q^{n} · ∏_{i=1}^{t}(1 − \frac{1}{q^{n_{i}}}),  (1)

where n_{i} is the degree of f_{i}, and n ≥ 1 is the degree of f (see [9] for a proof).

From (1), we see that Φ_{q}(f) only depends on the number of distinct irreducible factors f has of each degree. We introduce some useful notation:

Definition 6 Let Irr(q, d) denote the number of monic irreducible polynomials g ∈ 𝔽_{q}[x], such that (i) g has degree d and (ii) g(0) ≠ 0.

Let Irr(q, d; f) denote the number of monic irreducible polynomials g ∈ 𝔽_{q}[x], such that (i) g has degree d, (ii) g(0) ≠ 0 and (iii) g divides f.

In this notation, (1) translates into

Φ_{q}(f) = q^{n} · ∏_{d=1}^{n}(1 − \frac{1}{q^{d}})^{Irr(q,d;f)}.  (2)

Clearly,

deg(f) ≥ ∑_{d=1}^{n} d · Irr(q, d; f),  (3)

and equality holds precisely, when f is square free. At this point, we observe that for a fixed n = deg(f), the minimal value of Φ_{q}(f) occurs, when f has as many distinct small degree factors as allowed by (3); i.e. if k is any integer such that deg(f) ≤ 1 + ∑_{d=1}^{k} d · Irr(q, d), then

Φ_{q}(f) ≥ q^{n} · ∏_{d=1}^{k}(1 − \frac{1}{q^{d}})^{Irr(q,d)}.  (4)

To bound the right hand side of (4), we need upper bounds on both Irr(q, d) and possible values for k. It is known (see Lidl and Niederreiter [9]) that

q^{k} − 1 = ∑_{d|k} d · Irr(q, d).  (5)

From (5), we see that n ≤ 1 + ∑_{d=1}^{k} d · Irr(q, d) for k = ⌈log_{q} n⌉. It is also implied that

Irr(q, d) ≤ \frac{q^{d} − 1}{d}.  (6)

Combining with (4), we find

Φ_{q}(f) ≥ q^{n} · ∏_{d=1}^{⌈log_{q} n⌉}(1 − \frac{1}{q^{d}})^{\frac{q^{d}−1}{d}} .  (7)

Using that (1 − \frac{1}{c})^{c−1} ≥ \frac{1}{e}, for c > 1, this can be rephrased to

Φ_{q}(f) ≥ q^{n} · e^{− ∑_{d=1}^{⌈log_{q} n⌉} \frac{1}{d}} ,  (8)

and using that \frac{1}{2} + \frac{1}{3} + ⋯ + \frac{1}{k} ≤ ln k, we finally get

Φ_{q}(f) ≥ q^{n} · \frac{1}{e⌈log_{q} n⌉}.  (9)

Remark. The above bound is only valid for polynomials f for which f(0) ≠ 0. When changing the argument to general f, one needs to consider the irreducible polynomial x of degree 1, implying that the value of Irr(q, 1) increases by 1. The above analysis can be adjusted to this case resulting in the slightly worse bound Φ_{q}(f) ≥ q^{n} · \frac{1}{4⌈log_{q} n⌉}.

3 A stronger lower bound for Φ_{q}(x^{n} − 1)

In our proof of the lower bound for Φ_{q}(f), f being arbitrary, we considered a worst case, where all irreducible polynomials of small degree were factors of f. Intuitively, one might hope that x^{n} − 1 would never factorise in that way, i.e. for every n there would be a lot of small degree polynomials that did not divide x^{n} − 1. This intuition turns out to be true, and when stated in a suitably formal manner it suffices to prove the stronger bound of Theorem 3.

From (6), we know that Irr(q, d; x^{n} − 1) ≤ \frac{q^{d}−1}{d}. We will divide the possible degrees d in two sets according to whether Irr(q, d; x^{n} − 1) has a value close to this upper bound or not.

Definition 7 Let A_{n,q} be the set of those degrees d ∈ {1, …, n} for which

Irr(q, d; x^{n} − 1) > \frac{q^{d} − 1}{d^{3}}.

Let B_{n,q} be the set of those degree d ∈ {1, …, n} for which

Irr(q, d; x^{n} − 1) ≤ \frac{q^{d} − 1}{d^{3}}.

We can basically ignore the contribution from degrees in B_{n,q}:

Lemma 8

ν(n, q) ≥ \{ \begin{matrix}e^{−ζ(3)} ≈ .30058, & for A_{n,q} = ∅, \\ e^{−γ} · e^{− \frac{1}{|An,q|}} \frac{1}{|A_{n,q}|}, & for A_{n,q} ≠ ∅, \end{matrix}

where γ denotes Euler’s constant, and ζ is Riemann’s function.

Proof. With arguments analogous to those used in section 2, we obtain a bound:

ν(n, q) = Φ_{q}(x^{n} − 1) · q^{−n}
≥ ∏_{d∈A_{n,q}}(1 − \frac{1}{q^{d}})^{\frac{q^{d}−1}{d}} · ∏_{d∈B_{n,q}}(1 − \frac{1}{q^{d}})^{\frac{q^{d}−1}{d^{3}}}
≥ e^{− ∑_{d∈An,q} \frac{1}{d}} · e^{− ∑_{d∈Bn,q} \frac{1}{d^{3}}}
≥ e^{− ∑_{d=1}^{|An,q|} \frac{1}{d}} · e^{− ∑_{d=|An,q|+1}^{n} \frac{1}{d^{3}}}

In the case of A_{n,q} = ∅, we use the fact that ∑_{d=1}^{∞} \frac{1}{d^{3}} = ζ(3), to get the bound

ν(n, q) ≥ e^{−ζ(3)} ≈ .30058

In the case of A_{n,q} ≠ ∅, we use the two inequalities ∑_{d=1}^{s} \frac{1}{d} ≤ ln s + γ + \frac{1}{2s} and ∑_{d=s+1}^{∞} \frac{1}{d^{3}} ≤ \frac{1}{2s^{2}} , to get the bound

ν(n, q) ≥ e^{−γ} · e^{− \frac{1}{|An,q|}} \frac{1}{|A_{n,q}|}.

Our next task is to find an upper bound on |A_{n,q}|. We will do that implicitly by expressing a lower bound for n in terms of |A_{n,q}|. We start by improving the simple bound Irr(q, d; x^{n} − 1) ≤ \frac{q^{d}−1}{d}:

Lemma 9

Irr(q, d; x^{n} − 1) ≤ \frac{gcd(q^{d} − 1, n)}{d}.

Proof. Let the monic irreducible polynomial g ∈ 𝔽_{q}[x] of degree d be a factor of x^{n} − 1, and let α be a root of g.

Since g divides x^{n} − 1 it follows that α^{n} = 1. Since g is irreducible, of degree d, it follows that α ∈ 𝔽_{q^{d}} and therefore α^{q^{d}−1} = 1. Combining, we get that α^{gcd(q^{d}−1,n)} = 1. Since there are at most k distinct k’th roots of unity in a field, we see that there are at most gcd(q^{d} − 1, n) distinct possible α’s. Because g has precisely d distinct roots, and distinct g’s have no common roots, there are at most gcd(q^{d} − 1, n)/d possible g’s.

Combining this result with the lower bound Irr(q, d; x^{n} − 1) > \frac{q^{d}−1}{d^{3}} implied by d ∈ A_{q,n}, we can get our first lower bound on n.

Lemma 10

n ≥ \frac{lcm_{d∈A_{q,n}}(q^{d} − 1)}{∏_{d∈A_{q,n}}(d^{2})}

Proof. Assume d ∈ A_{q,n}. Combining the definition of A_{q,n} with Lemma 9, we see that \frac{q^{d}−1}{d^{3}} ≤ \frac{gcd(q^{d}−1,n)}{d}, or equivalently, gcd(q^{d} − 1, n) ≥ \frac{q^{d}−1}{d^{2}}. One may interpret this bound to say that n contains q^{d} − 1 as a factor except possibly for something very small (bounded by d^{2}). Since this is true for any d ∈ A_{q,n}, we see that n contains the least common multiple of the (q^{d} − 1)’s as a factor except possible for something small (bounded by the product of the d’s squared).

The next step will be to phrase the preceding bound in terms of |A_{q,n}|.

Lemma 11 Let A be a finite set of natural numbers, let k = |A|, and let q be a prime power, then

\frac{lcm_{d∈A}(q^{d} − 1)}{∏_{d∈A}(d^{2})} ≥ q^{ck^{2}−o(k^{2})}

where c = \frac{ζ(6)}{2ζ(2)ζ(3)} ≈ .25726.

Proof. The proof will consist in combining three lemmas that we state and prove separately in Section 5.

Let C_{n} ∈ ℚ[z] denote the nth cyclotomic polynomial. From Lemma 16 we have

lcm_{d∈A}(q^{d} − 1) = ∏_{{e |∃d∈A such that e divides d }} C_{e}(q) ≥ ∏_{d∈A} C_{d}(q).

For ϕ denoting Euler’s ϕ-function, we get in addition by Lemma 17

lcm_{d∈A}(q^{d} − 1) ≥ ∏_{d∈A} q^{ϕ(d)−2}.

Combining this calculation with Lemma 19, we find

\frac{lcm_{d∈A}(q^{d} − 1)}{∏_{d∈A}(d^{2})} ≥ q^{∑_{d∈A}(ϕ(d)−2 log_{2} d−2)}
≥ q^{ck^{2}−o(k^{2})}.

Proof of Theorem 3. In the case of A_{q,n} = ∅, it suffices by lemma 8 to note that e^{−ζ(3)} ≈ .30058 > .28477.

In the case of A_{q,n} ≠ ∅, we combine Lemmas 10 and 11, and find

log_{q} n ≥ c|A_{q,n}|^{2} − o(|A_{q,n}|^{2})  (10)

for c = \frac{ζ(6)}{2ζ(2)ζ(3)}. This may be reformulated as follows: For all c′ < c there exists c′′ > 0, such that for all n ≥ q^{c′′}:

|A_{q,n}| ≤ \frac{1}{\sqrt{c′}} \sqrt{log_{q} n}

Combining this with Lemma 8 and the fact that e^{− \frac{1}{x}} → 1 for x → ∞, we see that for any c′ < c we can find c′′, such that for all n ≥ q^{c′′}, we have

ν(q, n) ≥ e^{−γ}\sqrt{c′} \frac{1}{\sqrt{log_{q} n}}  (11)

The statement of the theorem follows from noting that e^{−γ}\sqrt{c} > .28477.

4 Optimality of the lower bound on Φ_{q}(x^{n} − 1)

It will be argued that the lower bound of Theorem 3 is optimal up to a constant factor. The proof will consist in constructing an infinite sequence {n_{k}}_{k=1}^{∞} such that 𝔽_{q^{n}} : 𝔽_{q} has exceptionally few normal bases for n ∈ {n_{k}}. The sequence {n_{k}} will depend on q. Each number n_{k} will have the property that all irreducible polynomials of degrees at most k divides x^{n_{k}} − 1 (except for the irreducible polynomial x that can never divide any polynomial of the form x^{n} − 1).

Definition 12 For a given prime power q, define the infinite sequence {n_{k}}_{k=1}^{∞} by

n_{k} = lcm_{d=1}^{k}(q^{d} − 1)

This definition serves our purpose in that

Lemma 13 For n_{k} as defined above, Irr(q, d; x^{n_{k}} − 1) = Irr(q, d) for all d ≤ k.

Proof. Every irreducible polynomial of degree d divides x^{q^{d}−1} − 1 (as usual we make an exception for the irreducible polynomial x) (see Lidl and Niederreiter [9]), and since x^{a} − 1 divides x^{ab} − 1 for any positive integers a, b, we also have that x^{q^{d}−1} − 1 divides x^{n_{k}} − 1.

The size of n_{k} is also kept fairly small:

Lemma 14 For all prime powers q, for all integers k > 0, and with n_{k} as defined above, it is the case that

log_{q} n_{k} = ck^{2} + O(k log k),

where c = \frac{1}{2ζ(2)} = \frac{3}{π^{2}} ≈ .30396

Proof. By lemma 16, we may express n_{k} in terms of cyclotomic polynomials

n_{k} = ∏_{d=1}^{k} C_{d}(q).

When using Lemma 17 to bound C_{d}(q) in terms of Euler’s ϕ-function and taking logarithms on both sides, we find

log_{q} n_{k} = ∑_{d=1}^{k} ϕ(d) + O(k).

The value of the accumulated sum of the ϕ-function is known (see Lemma 20), and we have

log_{q} n_{k} = ck^{2} + O(k log k).

We will first find a bound on ν(n_{k}, q) in terms of k and then combine this with the previous bound on k in terms of n_{k}.

Lemma 15

ν(n_{k}, q) ≤ 1.1340 · \frac{1}{k}.

Proof. Using the multiplicative characterisation of Φ from section 2, we find that

ν(n_{k}, q) = ∏_{d=1}^{n_{k}}(1 − \frac{1}{q^{d}})^{Irr(q,d,x^{n_{k}} −1)}.

By Lemma 13, the dependence of n_{k} can be restricted to the occurrence of k in the multiplication bound:

ν(n_{k}, q) ≤ ∏_{d=1}^{k}(1 − \frac{1}{q^{d}})^{Irr(q,d)}.

To get the bound of the lemma, we show that

∏_{d=1}^{l}(1 − \frac{1}{q^{d}})^{Irr(q,d)} ≤ 1.08\frac{1}{l} for l ≤ 12  (12)

and

∏_{d=l+1}^{k}(1 − \frac{1}{q^{d}})^{Irr(q,d)} ≤ 1.05 · \frac{l}{k} for l ≥ 12.  (13)

Clearly, inequalities (12) and (13) combined imply the lemma. (12) may be verified by an explicit calculation using that q ≥ 2, Irr(q, 1) = q − 1, Irr(q, 2) = (q^{2} − q)/2, Irr(q, 3) = (q^{3} − q)/3, Irr(q, 4) = (q^{4} − q^{2})/4 etc. (details are omitted for technical simplicity). To prove (13), we use that (1 − \frac{1}{c})^{c} ≤ \frac{1}{e} for c > 1, and find that

∏_{d=l+1}^{k}(1 − \frac{1}{q^{d}})^{Irr(q,d)} ≤ e^{− ∑_{d=l+1}^{k} Irr(q,d)/q^{d}}.

It is well known (see Lidl and Niederreiter [9]) that (for d ≥ 2 only, since we exclude the degree 1 polynomium x)

Irr(q, d) = \frac{1}{d} ∑_{e|d} μ(e)q^{d/e}.

This implies in particular that (for d, q ≥ 2)

Irr(q, d)/q^{d} ≥ \frac{1}{d} − \frac{2}{d}(\sqrt{2})^{−d}.

Using the elementary inequalities ∑_{d=l+1}^{k} \frac{1}{d} ≥ ln \frac{k}{l} − \frac{1}{2l} and ∑_{d=l+1}^{k} \frac{2}{d}(\sqrt{2})^{−d} ≤ \frac{2}{l+1} \frac{1}{\sqrt{2}−1}(\sqrt{2})^{−l} combined with the inequality

e^{\frac{1}{2l} + \frac{2}{l+1} \frac{1}{\sqrt{2}−1} (\sqrt{2})^{−l}} ≤ 1.05 for l ≥ 12,

we obtain (13).

Proof of Theorem 5. From Lemma 14, we have that c· \frac{1}{\sqrt{log_{q} n_{k}}} ≥ \frac{1}{k} for infinitely

many k for any c > 1/\sqrt{2ζ(2)} < .55133. Combining with Lemma 15, we see that ν(q, n) ≤ .55133 · 1.1340 · \frac{1}{\sqrt{log_{q} n}} for infinitely many n.

5 Auxiliary results

Lemma 16 Let A be a finite set of natural numbers, let q be a prime power, and let C_{n}(z) denote the nth cyclotomic polynomial. Then

lcm_{d∈A}(q^{d} − 1) = ∏_{{e |∃d∈A such that e divides d }} C_{e}(q).

Proof. Let C_{n}(z) denote the nth cyclotomic polynomial. It is known that C_{n}(z) is irreducible over the field ℚ and that z^{d} − 1 = ∏_{e|d} C_{e}(z) (see Hungerford [8, Prop. 8.2 and Prop 8.3]). In particular this implies

gcd_{d∈A}(z^{d} − 1) = ∏_{e| gcd_{d∈A}(d)} C_{e}(z) = z^{gcd_{d∈A}(d)} − 1  (14)

and

lcm_{d∈A}(z^{d} − 1) = ∏_{{e |∃d∈A such that e divides d }} C_{e}(z).  (15)

It might be tempting to substitute q for z in (15) and call it a proof of the lemma. However, the validity of such substitution needs a careful argument. To see this, observe that it fails in a rather similar looking situation: Using that C_{2}(z) = z+1 and C_{6}(z) = z^{2} − z + 1, we see that lcm(C_{2}(z), C_{6}(z)) = C_{2}(z) · C_{6}(z). However, lcm(C_{2}(2), C_{6}(2)) = lcm(3, 3) = 3 ≠ 9 = C_{2}(2) · C_{6}(2). The reason for this failure is of course that the “lcm” in (15) is taken in the polynomial ring ℚ[z], whereas the “lcm” of the lemma must be taken in the integer ring ℤ. We therefore need a more elaborate argument.

For both ℚ[z] and ℤ, the following generalisation of the classical formula lcm(x, y) = xy/ gcd(x, y) is valid (Marsh [10]). Let M be a finite subset of either ℚ[z] or ℤ:

lcm_{m∈M}(m) = \frac{∏_{I⊆M,|I| odd} gcd_{m∈I}(m)}{∏_{I⊆M,|I| even} gcd_{m∈I}(m)}.  (16)

This formula tells us that the least common multiple of a set of numbers M (or set of polynomials) is determined uniquely from the gcd’s of all possible subsets of M. This means that if substitution of q for z is always valid in (14), then it is also always valid to substitute q for z in (15). Hence, we need only prove

gcd_{d∈A}(q^{d} − 1) = q^{gcd_{d∈A}(d)} − 1,  (17)

which follows from observing that a prime power p^{k} divides q^{d} − 1 precisely when the order of q (modulo p^{k}) divides d.

Lemma 17 Let n be a natural number, let q be a prime power, and let C_{n}(z) denote the nth cyclotomic polynomial. Then

\frac{1}{4}q^{ϕ(n)} ≤ C_{n}(q) ≤ 4q^{ϕ(n)}

where ϕ denotes Euler’s ϕ-function.

Proof. The nth cyclotomic polynomial C_{n}(z) is monic of degree ϕ(n). One might therefore expect C_{n}(q) to have a value not far from q^{ϕ(n)}. To prove the bound of the lemma, we will use the multiplicative characterisation

C_{n}(z) = ∏_{d|n}(z^{n/d} − 1)^{μ(d)},  (18)

where μ denotes the Möbius function. We will also need a corresponding characterisation of ϕ (see Hardy and Wright [6]):

ϕ(n) = ∑_{d|n} μ(d)\frac{n}{d}.  (19)

Exponentiating with base q on both sides of (19) and combining with (18), where q is substituted for z, we find

C_{n}(q) = q^{ϕ(n)} ∏_{d|n}(1 − \frac{1}{q^{n/d}})^{μ(d)}.  (20)

To bound the size of the right factor in (20), we use that μ(d) ∈ {−1, 0, 1} and therefore

∏_{d|n}(1 − \frac{1}{q^{n/d}})^{μ(d)} ≥ ∏_{d|n}(1 − \frac{1}{q^{n/d}}) ≥ ∏_{i=1}^{∞}(1 − \frac{1}{q^{i}}).  (21)

If we take the natural logarithm and use that ln(1 − s) ≥ s ln \frac{1}{4} for 0 ≤ s ≤ \frac{1}{2}, we find (for q ≥ 2)

ln (∏_{i=1}^{∞}(1 − \frac{1}{q^{i}})) ≥ (ln \frac{1}{4}) ∑_{i=1}^{∞} \frac{1}{q^{i}} ≥ ln \frac{1}{4},

from which it follows that C_{q}(n) ≥ \frac{1}{4}q^{ϕ(n)}. The upper bound on C_{q}(n) is proved similarly.

Lemma 18 Let A be a finite set of natural numbers, let k = |A|, and let ϕ denote Euler’s ϕ-function, then

∑_{d∈A} ϕ(d) ≥ ck^{2} − o(k^{2})

where c = \frac{ζ(6)}{2ζ(2)ζ(3)} ≈ .25726.

Proof. The lower bound on ∑_{d∈A} ϕ(d) relies on using Dressler’s result that only few integers are mapped to small values by ϕ. To state it formally, we define M_{n} = {x ∈ ℕ|ϕ(x) ≤ n}. Dressler [3] proved (see also Erdös [5] and Bateman [2]):

|M_{n}| = c′n + o(n) for c′ = \frac{ζ(2)ζ(3)}{ζ(6)} ≈ 1.9436.  (22)

It is clear that if A has the form M_{n} for some n, then ∑_{d∈A} ϕ(d) is minimised (with respect to a fixed |A|). Therefore choose l maximal such that |M_{l}| ≤ |A|, and we have

∑_{d∈A} ϕ(d) ≥ ∑_{d∈M_{l}} ϕ(d)  (23)

In order to lower bound the latter sum, we observe that ϕ(d) = n for d ∈ M_{n} − M_{n−1}, implying that

∑_{d∈M_{n}} ϕ(d) = ∑_{i=1}^{n} i(|M_{i}| − |M_{i−1}|)

= n · |M_{n}| − ∑_{i=1}^{n−1} |M_{i}|.

Combining with (22), we get

∑_{d∈M_{n}} ϕ(d) = n · c′n − ∑_{i=1}^{n−1} c′i + o(n^{2})  (24)
= \frac{c′}{2} n^{2} + o(n^{2}).  (25)

Finally, combining the definition of l with (22), we see that l = \frac{1}{c′} |A| + o(|A|), which combined with (23) and (25) leads to

∑_{d∈A} ϕ(d) ≥ \frac{1}{2c′} |A|^{2} − o(|A|^{2}).

Lemma 19 Let A be a finite set of natural numbers, let k = |A|, and let ϕ denote Euler’s ϕ-function, then

∑_{d∈A}(ϕ(d) − 2 log_{2} d) ≥ ck^{2} − o(k^{2})

where c = \frac{ζ(6)}{2ζ(2)ζ(3)} ≈ .25726.

Proof. This lemma is a technical variation of Lemma 18. The proof of the latter lemma also applies here, except that we need in addition to argue that ∑_{d∈A} log_{2} d is bounded by o(k^{2}). In the following, use the terminology from the proof of Lemma 18.

It is known that ϕ(n) = Ω(\frac{n}{ln ln n}) (see Hardy and Wright [6]), which implies that log_{2} d ≤ 2 log_{2} ϕ(d) for d sufficiently large. We therefore get the following modified version of (23)

∑_{d∈A}(ϕ(d) − 2 log_{2} d) ≥ ∑_{d∈M_{l}} ϕ(d) − 4 ∑_{d∈M_{l}} log_{2} ϕ(d) − O(1).  (26)

Using that ϕ(d) ≤ d, it follows from the definition of l that ∑_{d∈M_{l}} log ϕ(d) = O(|A| log |A|), which combined with (26) and the proof of Lemma 18 implies

∑_{d∈A}(ϕ(d) − 2 log_{2} d) ≥ \frac{1}{2c′} |A|^{2} − o(|A|^{2}).

Lemma 20 Let ϕ denote Euler’s ϕ-function, then

∑_{d=1}^{k} ϕ(d) = ck^{2} + O(k log k)

where c = \frac{1}{2ζ(2)} ≈ .30396.

Proof. This is well known, see Hardy and Wright [6].

References

[1] Erik Bach and Jeffrey Shallit. Algorithmic Number Theory. Volume I: Efficient algorithms. MIT Press, 1996.

[2] Paul T. Bateman. The distribution of values of the Euler function. Acta Arith. 21 (1972), 329–345.

[3] Robert E. Dressler. A density which counts multiplicity. Pacific J. Math. 34 (1970), 371–378.

[4] G. Eisenstein. Lehrsätze. J. Reine Angew. Math. 39 (1850), 180–182.

[5] Paul Erdös. Some remarks on Euler’s ϕ-function and some related problems. Bull. Amer. Math. Soc. 51 (1945), 540–544.

[6] G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers. (Third Edition). Oxford University Press, 1954.

[7] K. Hensel. Ueber die Darstellung der Zahlen eines Gattungsbereiches für einen beliebigen Primdivisor. J. Reine Angew. Math. 103 (1888), 230–237.

[8] Thomas W. Hungerford. Algebra. Springer-Verlag, 1974.

[9] R. Lidl and H. Niederreiter. Finite Fields, Vol. 20 of Encyclopedia of Mathematics and its Applications. Addison Wesley, 1983.

[10] D. C. B. Marsh. Solution to problem E 2229. Amer. Math. Monthly 78 (1971), 299.

[11] Joachim von zur Gathen and Mark Giesbrecht. Constructing normal bases in finite fields. J. Symbolic Computation 10 (1990), 547–570.

Recent BRICS Report Series Publications

RS-97-44 Gudmund Skovbjerg Frandsen. On the Density of Normal Bases in Finite Fields. December 1997. 14 pp.

RS-97-43 Vincent Balat and Olivier Danvy. Strong Normalization by Run-

Time Code Generation. December 1997.

RS-97-42 Ulrich Kohlenbach. On the No-Counterexample Interpretation. December 1997. 26 pp.

RS-97-41 Jon G. Riecke and Anders B. Sandholm. A Relational Account of Call-by-Value Sequentiality. December 1997. 24 pp. Appears in Twelfth Annual IEEE Symposium on Logic in Computer Science, LICS ’97 Proceedings, pages 258–267.

RS-97-40 Harry Buhrman, Richard Cleve, and Wim van Dam. Quantum Entanglement and Communication Complexity. December 1997. 14 pp.

RS-97-39 Ian Stark. Names, Equations, Relations: Practical Ways to Reason about ‘new’. December 1997. ii+33 pp. This supersedes the earlier BRICS Report RS-96-31. It also expands on the paper presented in Groote and Hindley, editors, Typed Lambda Calculi and Applications: 3rd International Conference, TLCA ’97 Proceedings, LNCS 1210, 1997, pages 336–353.

RS-97-38 Micha� Hańćkowiak, Micha� Karoński, and Alessandro Panconesi. On the Distributed Complexity of Computing Maximal Matchings. December 1997. 16 pp. To appear in The Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’98.

RS-97-37 David A. Grable and Alessandro Panconesi. Fast Distributed Algorithms for Brooks-Vizing Colourings (Extended Abstract). December 1997. 20 pp. To appear in The Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’98.

RS-97-36 Thomas Troels Hildebrandt, Prakash Panangaden, and Glynn Winskel. Relational Semantics of Non-Deterministic Dataflow. December 1997. 21 pp.

RS-97-35 Gian Luca Cattani, Marcelo P. Fiore, and Glynn Winskel. A Theory of Recursive Domains with Applications to Concurrency. December 1997. ii+23 pp.