One may also impose a vector space structure on DF (V ), in a very natural

way: for π, π ∈ DF (V ), the map π + π sends δ ∈ V to π(δ) + π (δ), and

for c ∈ F , the map cπ sends δ ∈ V to cπ(δ). By the observations in the

previous paragraph, DF (V ) is an F -vector space of dimension ; indeed, the

sum and scalar multiplication operations on DF (V ) correspond to analogous

operations on coordinate vectors.

One last fact we need about the dual space is the following:

Theorem 19.3. Let V be an F -vector space of ¬nite dimension > 0. For

any linearly independent vectors δ1 , . . . , δm ∈ V , and any a1 , . . . , am ∈ F ,

there exists π ∈ DF (V ) such that π(δi ) = ai for i = 1, . . . , m.

Proof. Fix any ordered basis for V , and let M be the m— matrix whose ith

row is the coordinate vector of δi with respect to this ordered basis. Let v

be the m — 1 column vector whose ith coordinate is ai . As the δi are linearly

independent, the rows of M must also be linearly independent. Therefore,

the F -linear map that sends w ∈ F —1 to M w ∈ F m—1 is surjective. It

follows that any solution w to the equation v = M w is the coordinate

vector of a map π ∈ DF (V ) that satis¬es the requirements of the theorem.

2

That completes our digression on the dual space. We now return to the

problem of computing the minimal polynomial φ of the linearly generated

sequence S = (±0 , ±1 , . . .). Assume we have a bound M on the degree of φ.

As we are assuming S has full rank, we may assume that M ¤ . For any π ∈

DF (V ), we may consider the projected sequence Sπ = (π(±0 ), π(±1 ), . . .).

Observe that φ is a generating polynomial for Sπ ; indeed, for any polynomial

g ∈ F [X], we have g Sπ = π(g S), and hence, for all i ≥ 0, we have

(Xi φ) Sπ = π((Xi φ) S) = π(0) = 0. Let φπ ∈ F [X] denote the minimal

polynomial of Sπ . Since φπ divides any generating polynomial of Sπ , and

since φ is a generating polynomial for Sπ , it follows that φπ is a divisor of

φ.

This suggests the following algorithm for e¬ciently computing the mini-

mal polynomial of S:

19.3 Computing minimal polynomials: a more general case 431

Algorithm MP:

g ← 1 ∈ F [X]

repeat

choose π ∈ DF (V ) at random

compute the ¬rst 2M terms of the projected sequence Sπ

use the algorithm in §19.2 to compute the minimal polynomial

φπ of Sπ

g ← lcm(g, φπ )

until g S = 0

output g

A few remarks on the above procedure are in order:

• in every iteration of the main loop, g is the least common multiple of

a number of divisors of φ, and hence is itself a divisor of φ;

• under our assumption that S has full rank, and since g is a monic

divisor of φ, if g S = 0, we may safely conclude that g = φ;

• under our assumption that F is ¬nite, choosing a random element π

of DF (V ) amounts to simply choosing at random the entries of the

coordinate vector of π, relative to some ordered basis for V ;

• we also assume that elements of V are represented as coordinate

vectors, so that applying a projection π ∈ DF (V ) to a vector in V

takes O( ) operations in F ;

• similarly, adding two elements of V , or multiplying an element of V

times a scalar, takes O( ) operations in F .

Based on the above observations, it follows that when the algorithm halts,

its output is correct, and that the cost of each loop iteration is O(M )

operations in F . The remaining question to be answered is this: what is

the expected number of iterations of the main loop? The answer to this

question is O(1), which leads to a total expected cost of Algorithm MP of

O(M ) operations in F .

The key to establishing that the expected number of iterations of the main

loop is constant is provided by the following theorem.

Theorem 19.4. Let S = (±0 , ±1 , . . .) be a linearly generated sequence over

the ¬eld F , where the ±i are elements of a vector space V of ¬nite dimension

> 0. Let φ be the minimal polynomial of S over F , let m := deg(φ), and

assume that S has full rank (i.e., ±0 , . . . , ±m’1 are linearly independent).

Under the above assumptions, there exists a surjective F -linear map σ :

DF (V ) ’ F [X]<m such that for all π ∈ DF (V ), the minimal polynomial φπ

432 Linearly generated sequences and applications

of the projected sequence Sπ := (π(±0 ), π(±1 ), . . .) satis¬es

φ

φπ = .

gcd(σ(π), φ)

Recall that F [X]<m denotes the m-dimensional vector space of polynomials

in F [X] of degree less than m.

Proof. While the statement of this theorem looks a bit complicated, its proof

is quite straightforward, given our characterization of linearly generated

sequences in Theorem 19.2 in terms of rational functions. We build the

linear map σ as the composition of two linear maps, σ0 and σ1 .

Let us de¬ne the map

σ0 : DF (V ) ’ F ((X’1 ))

∞

π(±i )X’(i+1) .

π’

i=0

We also de¬ne the map σ1 to be the φ-multiplication map on F ((X’1 )), that

is, the map that sends z ∈ F ((X’1 )) to φ · z ∈ F ((X’1 )). The map σ is just

the composition σ = σ1 —¦ σ0 . It is clear that both σ0 and σ1 are F -linear

maps, and hence, so is σ.

First, observe that for π ∈ DF (V ), the series z := σ0 (π) is the series

associated with the projected sequence Sπ , as in Theorem 19.2. Let φπ be

the minimal polynomial of Sπ . Since φ is a generating polynomial for S,

it is also a generating polynomial for Sπ . Therefore, Theorem 19.2 tells us

that

h := σ(π) = φ · z ∈ F [X]<m ,

and that φπ is the denominator of z when expressed as a fraction in lowest

terms. Now, we have z = h/φ, and it follows that φπ = φ/ gcd(h, φ) is this

denominator.

Second, the hypothesis that ±0 , . . . , ±m’1 are linearly independent, to-

gether with Theorem 19.3, implies that dimF (img(σ0 )) ≥ m. Also, ob-

serve that σ1 is an injective map (indeed, it is surjective as well). There-

fore, dimF (img(σ)) ≥ m. In the previous paragraph, we observed that

img(σ) ⊆ F [X]<m , and since dimF (F [X]<m ) = m, we may conclude that

img(σ) = F [X]<m . That proves the theorem. 2

Given the above theorem, we can analyze the expected number of itera-

tions of the main loop of Algorithm MP.

First of all, we may as well assume that the degree m of φ is greater than

0, as otherwise, we are sure to get φ in the very ¬rst iteration. Let π1 , . . . , πs

19.3 Computing minimal polynomials: a more general case 433

be the random projections chosen in the ¬rst s iterations of Algorithm MP.

By Theorem 19.4, the polynomials σ(π1 ), . . . , σ(πs ) are uniformly and inde-

pendently distributed over F [X]<m , and we have g = φ at the end of loop

iteration s if and only if gcd(φ, σ(π1 ), . . . , σ(πs )) = 1.

Let us de¬ne Λφ (s) to be the probability that gcd(φ, f1 , . . . , fs ) = 1, where

F

f1 , . . . , fs are randomly chosen from F [X]<m . Thus, the probability that we

have g = φ at the end of loop iteration s is equal to Λφ (s). While one

F

φ

can analyze the quantity ΛF (s), it turns out to be easier, and su¬cient for

our purposes, to analyze a di¬erent quantity. Let us de¬ne Λm (s) to be the

F

probability that gcd(f1 , . . . , fs ) = 1, where f1 , . . . , fs are randomly chosen

from F [X]<m . Clearly, Λφ (s) ≥ Λm (s).F

F

Theorem 19.5. If F is a ¬nite ¬eld of cardinality q, and m and s are

positive integers, then we have

Λm (s) = 1 ’ 1/q s’1 + (q ’ 1)/q sm .

F

Proof. For any positive integer n, let Un be the set of all tuples of polynomials

(f1 , . . . , fs ) ∈ F [X]—s with gcd(f1 , . . . , fs ) = 1, and let un = |Un |. First, let

<n

h be any monic polynomial with k := deg(h) < n. The set Un,h of all s-

tuples of polynomials of degree less than n whose gcd is h is in one-to-one

correspondence with Un’k , via the map that sends (f1 , . . . , fs ) ∈ Un,h to

(f1 /h, . . . , fs /h) ∈ Un’k . As there are q k possible choices for h of degree

k, we see that the set Vn,k , consisting of tuples (f1 , . . . , fs ) ∈ F [X]—s with

<n

deg(gcd(f1 , . . . , fs )) = k, has cardinality q k un’k . Every non-zero element of