Random Krylov spaces over finite fields^{∗}

Richard P. Brent^{†}, Shuhong Gao^{‡} and Alan G.B. Lauder^{§}

November 5, 2002

Abstract

Motivated by a connection with block iterative methods for solving linear systems over finite fields, we consider the probability that the Krylov space generated by a fixed linear mapping and a random set of elements in a vector space over a finite field equals the space itself. We obtain an exact formula for this probability, and from it we derive good lower bounds that approach 1 exponentially fast as the size of the set increases.

1 Introduction

Let 𝔽_{q} denote the finite field with q elements and 𝔽_{q}[X] the ring of polynomials in one variable over 𝔽_{q}. Let V be a vector space of dimension n over

∗The second author was supported in part by NSF under Grant DMS9970637, NSA under Grant MDA904-00-1-0048, ONR under Grant N00014-00-1-0565, and South Carolina Commission on Higher Education under a research initiative grant. The second author is also grateful to Oxford University Computing Laboratory for their warm hospitality during his visit in July 2001. The third author gratefully acknowledges the support of the EPSRC (Grant GR/N35366/01) and St John’s College, Oxford, and thanks Simon Blackburn for answering a question on group theory. Mathematics Subject Classification 2000: Primary 11T99, 15A04, 15A33. Key words and phrases: finite field, vector space, linear transformation, Krylov subspace

†Computing Laboratory, Oxford University, Oxford OX1 3QD, U.K. E-mail: richard.brent@comlab.ox.ac.uk

‡Department of Mathematical Sciences, Clemson University, Clemson, SC 29634-0975, USA. E-mail: sgao@math.clemson.edu.

§Computing Laboratory, Oxford University, Oxford OX1 3QD, U.K. E-mail:

alan.lauder@comlab.ox.ac.uk. To appear in SIAM Journal on Discrete Mathematics. rpb201

𝔽_{q}. Given a linear mapping T on V and a subset of vectors S ⊆ V of size m the Krylov subspace generated by S under T is defined as

Kry(T, S) := {∑_{i=1}^{m} f_{i}(T)v_{i} : f_{i}(X) ∈ 𝔽_{q}[X] and v_{i} ∈ S for 1 ≤ i ≤ m} .

This is just the space spanned by all vectors of the form T^{i}v over all nonnegative powers of T and vectors v ∈ S. Define

κ_{m}(T) = \frac{1}{q^{mn}} · #\{(v_{1}, …, v_{m}) ∈ V^{m} : Kry(T, \{v_{1}, …, v_{m}\}) = V \},

that is, κ_{m}(T) is the density of m-tuples of vectors in V that generate the whole space V under T. In other words, if one selects m vectors v_{1}, …, v_{m} uniformly at random and independently from V then κ_{m}(T) is the probability that Kry(T, {v_{1}, …, v_{m}}) = V. Our main goal of this paper is to find good lower bounds on κ_{m}(T).

To state our result, we need to define some parameter depending on T. Let ℓ be the minimal number of vectors required to generate V under T. This number ℓ is just the number of invariants in the Frobenius decomposition of V under T. We call ℓ the Frobenius index of T. Our main result is

Theorem. Let T be a linear mapping on a vector space V of dimension n over 𝔽_{q}. Suppose T has Frobenius index ℓ. Then for m ≥ ℓ

κ_{m}(T) ≥ \{ \begin{matrix}\frac{0.04}{1+log_{q}(n−ℓ+1)}, & if m = ℓ \\ \frac{1}{8}, & if m = ℓ + 1 and q = 2 \\ 1 − \frac{3}{2^{m−ℓ}} ≥ \frac{1}{4}, & if m ≥ ℓ + 2 and q = 2 \\ 1 − \frac{2}{q^{m−ℓ}} ≥ \frac{1}{3}, & if m ≥ ℓ + 1 and q > 2. \end{matrix}

When m = ℓ the lower bound is almost tight in the sense that there are values of n such that the probability is arbitrarily close to zero; see the remark following Corollary 10. Hence it is impossible to bound the probability away from zero in this case. For fixed ℓ the probability converges exponentially fast to 1 as m increases.

There are two important special cases. One is when T is the identity map, so ℓ = n. In this case, κ_{m}(T) is equal to the probability that m random vectors in a vector space of dimension n over 𝔽_{q} span the whole space, and a much better lower bound can be proved (see Lemma 7). The other is when ℓ = 1, which means that the minimal polynomial of T equals its characteristic polynomial, and better lower bounds are given in Theorem 9.

Our work was motivated by a connection with block iterative methods for solving large sparse linear systems over finite fields, see [3, 4, 8, 12, 14]. It improves upon the result in the report [15] used in an analysis of the block Wiedemann algorithm. We note that the relation between κ_{m}(T) and the Frobenius index ℓ is studied in [15] (see also [16, Section 6]), although the formulae obtained are less explicit and a somewhat different approach is taken. A more difficult and important question in the analysis of such algorithms is to bound the probability that certain “truncated” Krylov subspaces generate the whole space. More precisely, let

Kry(T, S; t) = {∑_{i=1}^{m} f(T)v_{i} : f_{i}(X) ∈ 𝔽_{q}[X], deg f_{i} ≤ t, and v_{i} ∈ S}.

For t approximately n/|S|, one requires a lower bound on the probability that the above space is the whole space. For large finite fields, relative to the dimension n, Kaltofen [8] and Villard [15, Section 6] obtain such a bound using the Schwartz-Zippel Lemma. For some practical applications, such as integer and polynomial factorization [5, 6, 9, 11], it is desirable to have a good bound for small fields. Using a counting argument Coppersmith obtains a weak bound in [4, 15]; it would be of great interest to strengthen this bound.

We use a module theoretic approach, via a sequence of reductions using standard decomposition theorems and an argument from the theory of abelian groups communicated to us by Simon Blackburn. Using existing results on random elements in vector spaces over finite fields, we then obtain an exact formula (Theorem 5) for the probability depending only on certain properties of the mapping. Finally, good lower bounds for this expression are derived.

2 Reductions

In this section we consider various reductions which allow us to characterise those sets of vectors which generate the whole space under T.

2.1 Module-theoretic interpretation

Let T be a linear mapping on a vector space V of dimension n over 𝔽_{q}. Denote by V_{T} the 𝔽_{q}[X]-module with underlying abelian group V and action of 𝔽_{q}[X] on V defined as

f(X) · v := f(T)v

for any polynomial f ∈ 𝔽_{q}[X]. (Any element v ∈ V may be thought of as lying in V_{T}, and vice-versa. When necessary to distinguish we shall call elements in V “vectors” and those in V_{T} “module elements”.)

Lemma 1 For any set S ⊆ V the Krylov space Kry(T, S) equals V if and only if S generates V_{T} as an 𝔽_{q}[X]-module.

Proof: Let S be such that the Krylov space generated by S under T is V. Let w ∈ V. Thus the vector w equals a linear combination over 𝔽_{q} of vectors of the form T^{i}v where v ∈ V. Hence the module element w is a linear combination over 𝔽_{q} of module elements of the form X^{i}.v for v ∈ S. Thus S generates V_{T} as an 𝔽_{q}[X]-module. The converse is similar.

□

Thus our main question is equivalent to the following: given a set of elements S chosen uniformly at random from the module V_{T} what is the probability that they generate V_{T}?

2.2 Reduction to primary modules

Let the principal ideal (m_{T}) in 𝔽_{q}[X] be the annihilator of the module V_{T}, that is,

(m_{T}) = {g ∈ 𝔽_{q}[x] : g(T)v = 0 for all v ∈ V }.

(Thus m_{T}, which we take to be monic, is just the minimal polynomial of the linear mapping T.) Factorize m_{T} as

m_{T} = ∏_{i=1}^{a} g_{i}^{r_{i}}

where g_{i} are monic irreducible polynomials and each r_{i} ≥ 1. Via the primary decomposition theorem [1, Theorem 3.7.12] the module V_{T} decomposes as

V_{T} = V_{1} ⊕ V_{2} ⊕ … ⊕ V_{a}  (1)

where the annihilator of V_{i} is (g_{i}^{r_{i}}).

For each 1 ≤ i ≤ a, let π_{i} denote the projection of V_{T} onto its ith factor. For a subset S of elements in V_{T} write π_{i}(S) for the image of the set S under this projection.

Lemma 2 Let S be a set of elements in V_{T}. Then S generates V_{T} if and only if π_{i}(S) generates V_{i} for 1 ≤ i ≤ a.

Proof: The forward implication is straightforward. For the reverse, assume that π_{i}(S) generates V_{i} for 1 ≤ i ≤ a. Let v ∈ V_{T}, so π_{i}(v) ∈ V_{i}. We can write π_{i}(v) = ∑_{j=1}^{m} h_{ij}(X).v_{j} where S = {v_{1}, …, v_{m}}. For each j, 1 ≤ j ≤ m using the Chinese Remainder Theorem we can find a polynomial h_{j}(X) such that h_{j}(X) ≡ h_{ij}(X) mod g_{i}(X)^{r_{i}} for each i, 1 ≤ i ≤ a. Here we use the coprimality of the g_{i}(X). Defining w := ∑_{j=1}^{m} h_{j}(X).v_{j} we see that π_{i}(w) = π_{i}(v) for all 0 ≤ i ≤ a, and hence v = w. Thus S generates V_{T} as we wished to show.

□

Thus it suffices to understand the number of generating sets of the primary modules V_{i}.

2.3 Reduction to irreducible exponent case

We now examine the primary parts V_{i} in the decomposition of the module V_{T} given in Equation (1). To this end, let W denote any 𝔽_{q}[X]-module with annihilator the ideal generated by a power g^{r} of an irreducible polynomial g. We need to determine the probability that a set of randomly chosen elements in W generates the whole module.

Let Rad(W) denote the Radical of W. This is defined to be the intersection of all maximal submodules. The following result is a special case of a module-theoretic analogue of a result in the theory of abelian groups, namely “a set of elements generates an abelian group if and only if its image in the quotient by the Frattini subgroup generates the quotient” (see [13, page 135, 5.2,12]).

Lemma 3 Let W be a primary 𝔽_{q}[X]-module with annihilator (g^{r}), where g is irreducible in 𝔽_{q}[X]. A set S ⊆ W is a generating set if and only if S̄ := {s + Rad(W) | s ∈ S} is a generating set in the quotient module W/Rad(W).

Proof: The forward implication is easy. For the reverse, by the cyclic decomposition theorem [1, Theorem 3.7.1] we can write

W = W_{1} ⊕ W_{2} ⊕ … ⊕ W_{b}

where each module W_{i} is cyclic with annihilator the ideal generated by the polynomial g^{r_{i}} for some power of g. We may take r_{i} ≥ r_{i+1} for 1 ≤ i ≤ b−1, and so r_{1} = r. Since each module in the decomposition is cyclic we have the 𝔽_{q}[X]-module isomorphism

W_{i} ≅ 𝔽_{q}[X]/(g^{r_{i}})

and so

W ≅ ⊕_{i=1}^{b}𝔽_{q}[X]/(g^{r_{i}}).

The intersection of all maximal submodules is just

Rad(W) ≅ ⊕_{i=1}^{b}g · (𝔽_{q}[X]/(g^{r_{i}})).

which is just g(X)W. Hence

W/Rad(W) ≅ 𝔽_{q}[X]/(g) ⊕ … ⊕ 𝔽_{q}[X]/(g)

where we have b terms in the sum. Now assume that the images of the elements of S = {v_{i}} in the quotient generate W/Rad(W). Let w ∈ W. Via the isomorphisms described above we have w = (w_{1}, …, w_{b}) where each w_{i} ∈ 𝔽_{q}[X]/(g^{r_{i}}). The image of w in the quotient W/Rad(W) is then w̄ := (w_{1} mod g, …, w_{b} mod g). By assumption we can write w̄ = ∑_{i=1}^{m} h_{i}(X).v̄_{i}. Then w − ∑_{i=1}^{m} h_{i}(X).v_{i} = (gw′_{1}, …, gw′_{b}). Defining w′ = (w′_{1}, …, w′_{b}) ∈ W and repeating the process, we can express w as a combination of the elements v_{i} plus an “error vector” each coefficient of which is divisible by g^{2}. Continuing in this way the error vector eventually reduces to zero, since our module is annihilated by some power of g, and we have the desired combination.

□

As in the proof of the above lemma, for W a primary module with annihilator (g^{r}) the required quotient is just

W/Rad(W) ≅ 𝔽_{q}[X]/(g) ⊕ … ⊕ 𝔽_{q}[X]/(g)

where we have b terms in the sum. Letting d = deg(g) we see that this is just the direct sum of b finite fields of order q^{d}, each viewed as an 𝔽_{q}[X]-module. The action of 𝔽_{q}[X] on each finite field is just defined for α in the finite field by X.α = βα, where β is some element such that g(β) = 0 in the finite field. We have

W/Rad(W) ≅ (𝔽_{q^{d}})^{b}

as an 𝔽_{q}[X]-module. The righthand-side also has the structure of a vector space over 𝔽_{q^{d}}. A set of elements in W/Rad(W) is a generating set if and only if the corresponding elements on the righthand-side of above isomorphism generates the set (𝔽_{q^{d}})^{b} as a 𝔽_{q^{d}}-vector space. This follows from the description of the action of 𝔽_{q}[X] on each vector space in the summand, since 1, β, …, β^{d−1} generates each finite field as a vector space over 𝔽_{q}. Thus we have reduced our problem to the study of generating sets for vector spaces over finite fields.

2.4 Generating sets for vector spaces

For each non-negative integer n, define the real function π(n, x) by

π(n, x) := (1 − x)(1 − x^{2}) … (1 − x^{n}).

The following lemma is “classical”.

Lemma 4 Let U be a vector space of dimension b over 𝔽_{q}. Then the probability that m ≥ b elements of U chosen uniformly at random span U is

\frac{π(m, 1/q)}{π(m − b, 1/q)}.

Proof: We follow the proof for the prime field case in [10], making appropriate modifications. (See also Theorem 1.1 in [2].) Let Φ_{b}(m, r) denote the number of m-tuples of vectors in 𝔽_{q}^{b} which span a subspace of rank r. (Equivalently, the number of rank r matrices of size b × m over 𝔽_{q}.) Dividing such sequences into those whose last vector is linearly dependent/independent on the previous m − 1 we derive the recurrence for m ≥ 1 and r ≥ 1

Φ_{b}(m, r) = q^{r}Φ_{b}(m − 1, r) + (q^{b} − q^{r−1})Φ_{b}(m − 1, r − 1).

We also have the initial conditions Φ_{b}(s, 0) = 1 for all s ≥ 1 (the zero sequence), Φ_{b}(0, 0) = 1 (the empty sequence), and Φ_{b}(0, s) = 0 for all s ≥ 1. One can now verify that the following formula holds for r ≥ 1

Φ_{b}(m, r) = ∏_{i=0}^{r−1}(q^{b} − q^{i})\frac{q^{m−i} − 1}{q^{i+1} − 1}.

Putting r = b and cancelling in a suitable way one finds that

Φ_{b}(m, b) = (q^{m} − 1)(q^{m} − q) … (q^{m} − q^{b−1}).

Dividing by the number of sequences, q^{m}, gives the required probability.

□

3 An exact formula

We now piece together the results proved in Section 2 to obtain an exact formula for the required probability. Let the minimal polynomial of the linear mapping T be denoted m_{T} and the characteristic polynomial c_{T}. Let ℓ be the Frobenius index of T. We consider a cyclic decomposition [1, Theorem 3.7.1] of the module V_{T} as

V_{T} = U_{1} ⊕ U_{2} ⊕ … ⊕ U_{ℓ}

where each U_{i} is a cyclic module with annihilator the ideal generated by a monic polynomial h_{i} satisfying h_{i+1}|h_{i} for 1 ≤ i ≤ ℓ − 1. Thus m_{T} = h_{1} and c_{T} = h_{1}h_{2} … h_{ℓ}. As before, let g_{j}, 1 ≤ j ≤ a, be the irreducible factors of m_{T}. Let d_{j} be the degree of g_{j} and ℓ_{j} the number of polynomials h_{1}, …, h_{l} divisible by g_{j}, 1 ≤ j ≤ a. Thus 1 ≤ ℓ_{j} ≤ ℓ and the cyclic decomposition of the module V_{i} in the primary decomposition of V_{T} (see Equation (1)) has exactly ℓ_{i} factors.

Theorem 5 Let T be a linear mapping on a vector space V of dimension n over 𝔽_{q}. Suppose T has Frobenius index ℓ and m ≥ ℓ. With the notation defined above, we have

κ_{m}(T) = ∏_{j=1}^{a} \frac{π(m, q^{−d_{j}})}{π(m − ℓ_{j}, q^{−d_{j}})}

where π(m, x) = (1 − x)(1 − x^{2}) … (1 − x^{m}).

Proof: By Lemma 1 one may equivalently find the probability that a uniform at random sequence of elements S in V_{T} generates V_{T} as an 𝔽_{q}[X]- module. By Lemma 2 such a set will generate V_{T} if and only if the set π_{j}(S) generates each primary summand V_{j} for 1 ≤ j ≤ a. Now for any choice of subsets S_{j} ⊆ V_{j} of size m, 1 ≤ j ≤ a, there exists exactly one set S in V_{T} such that π_{j}(S) = S_{j} for each 1 ≤ j ≤ a. Conversely, all sets S arise in this way. Thus it suffices to compute the probabilities of generating each primary module V_{i} by m elements separately, and to take the product.

We claim that the jth term in the product in the statement of the theorem is the probability that a sequence of m elements chosen uniformly at random in V_{j} will generate V_{j}. Once this claim is proved the result follows. By Lemma 3 a set of elements S_{j} in V_{j} is a generating set if and only if its image in the quotient by the Radical of V_{j} generates this quotient. If S_{j} is chosen uniformly at random in V_{j}, the corresponding set of elements S̄_{j} in the quotient will be uniform at random (exactly |Rad(V_{j})| elements of V_{j} map onto each element in the quotient). Thus we need to find the probability that m elements chosen uniformly at random in the quotient generate it. But the quotient has the structure of a vector space of dimension ℓ_{j} over 𝔽_{q^{d_{j}}}. From the comments at the end of Section 2.3 this probability is equal to the probability that m elements chosen uniformly at random from a vector space of dimension ℓ_{j} over 𝔽_{q^{d_{j}}} span the space. The result now follows from Lemma 4.

□

4 Lower bounds

The formula in Theorem 5 is elegant, but it is hard to see the magnitude of the probability κ_{m}(T). In this section we shall derive various simple explicit lower bounds for κ_{m}(T).

We shall repeatedly use the following equality and inequality:

\frac{1}{q^{k}} + \frac{1}{q^{k+1}} + ⋯ + \frac{1}{q^{m}} + ⋯ = \frac{1}{q^{k−1}(q−1)},

(1 − x_{1})^{a_{1}}(1 − x_{2})^{a_{2}} ⋯ (1 − x_{m})^{a_{m}} ≥ 1 − (a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{m}x_{m}),

for any real a_{i} ≥ 1, 1 ≥ x_{i} ≥ 0, q > 1, and any integer k ≥ 0. The inequality can be seen as follows. First of all it holds if x_{i} ≥ 1/a_{i} for some i. So we may assume that 0 ≤ x_{i} < 1/a_{i} for all i. Then one sees that the inequality follows by induction from the following two inequalities:

(1 − x_{1})(1 − x_{2}) ≥ 1 − (x_{1} + x_{2}), for x_{1}x_{2} ≥ 0,
(1 − x)^{a} ≥ 1 − ax, for 0 ≤ x < \frac{1}{a}, a ≥ 1.

The latter inequality here holds since the function a ln(1 − x) − ln(1 − ax) strictly increases for 0 ≤ x < 1/a (for any fixed a > 1) and evaluates to 0 when x = 0.

The next lemma is an extremely crude estimation, but already useful for large q.

Lemma 6 Let T be any linear map on a vector space of dimension n over 𝔽_{q}. Let ℓ be the Frobenius index of T. Then, for m ≥ ℓ,

κ_{m}(T) ≥ 1 − \frac{n}{q − 1}.

Proof: With the notation in Theorem 5, as n ≥ a, m ≥ ℓ_{j} and d_{j} ≥ 1, we have

κ_{m}(T) = ∏_{j=1}^{a} ∏_{i=1}^{ℓ_{j}} (1 − (\frac{1}{q^{d_{j}}} )^{m−ℓ_{j}+i})

≥ ∏_{j=1}^{n} ∏_{i=1}^{∞} (1 − (\frac{1}{q})^{i})

≥ (1 − ∑_{i=1}^{∞} \frac{1}{q^{i}} )^{n} ≥ (1 − \frac{1}{q − 1})^{n} ≥ 1 − \frac{n}{q − 1}.

□

The bound in Lemma 6 is good if q is large, but says nothing if q ≤ n+1. To get a good lower bound of κ_{m}(T) for small q, we need a more careful estimation. We start with a simple case when T is the identity map on V.

Lemma 7 Let V be a vector space of dimension n over 𝔽_{q} and let m ≥ n. Then the probability that m random vectors in V span the whole space V is

∏_{i=1}^{n}(1 − \frac{1}{q^{m−n+i}}) ≥ \{ \begin{matrix}0.288, & if m = n and q = 2 \\ 1 − \frac{1}{q^{m−n}(q−1)}, & otherwise. \end{matrix}

Equivalently, this also bounds the probability that a random m × n matrix over 𝔽_{q} has rank n.

Proof: By Lemma 4, the probability is

\frac{π(m, 1/q)}{π(m − n, 1/q)} = (1 − \frac{1}{q^{m−n+1}} )(1 − \frac{1}{q^{m−n+2}} ) ⋯ (1 − \frac{1}{q^{m}})
≥ 1 − (\frac{1}{q^{m−n+1}} + \frac{1}{q^{m−n+2}} + ⋯ + \frac{1}{q^{m}})
≥ 1 − \frac{1}{q^{m−n+1}} (1 + \frac{1}{q} + ⋯ + \frac{1}{q^{n−1}} + ⋯)
≥ 1 − \frac{1}{q^{m−n+1}} \frac{1}{1 − 1/q} ≥ 1 − \frac{1}{q^{m−n}(q − 1)}.

For m = n and q = 2, the above bound is zero, so we need a more careful analysis:

(1 − \frac{1}{2})(1 − \frac{1}{2^{2}} ) ⋯ (1 − \frac{1}{2^{m}})

> (1 − \frac{1}{2})(1 − \frac{1}{2^{2}} )(1 − \frac{1}{2^{3}} )(1 − \frac{1}{2^{4}} )(1 − \frac{1}{2^{5}} ) ⋯ (1 − \frac{1}{2^{m}}) ⋯

> (1 − \frac{1}{2})(1 − \frac{1}{2^{2}} )(1 − \frac{1}{2^{3}} )(1 − \frac{1}{2^{4}} )(1 − (\frac{1}{2^{5}} + ⋯ + \frac{1}{2^{m}} + ⋯))

= (1 − \frac{1}{2})(1 − \frac{1}{2^{2}} )(1 − \frac{1}{2^{3}} )(1 − \frac{1}{2^{4}} )(1 − \frac{1}{2^{4}} )

> 0.288.

This completes the proof.

□

To deal with the general case we need the following result, which reduces the problem for a general polynomial to that of a polynomial with irreducible factors of small degrees only.

Lemma 8 For k ≥ 1, let I_{k} be the number of irreducible polynomials in 𝔽_{q}[X] of degree k. Let f ∈ 𝔽_{q}[X] of degree n and let u = ⌊log_{q} n⌋. Then for any integer q_{1} > 1

∏_{g|f, g irred} (1 − \frac{1}{q_{1}^{deg g}} ) ≥ ∏_{k=1}^{u+1} (1 − \frac{1}{q_{1}^{k}} )^{I_{k}} .

Proof: This result is proved in [7] (i.e., the formula (6) on page 144, with q replaced by q_{1}).

□

We consider the important case when V is cyclic as an 𝔽_{q}[X]-module under T, hence ℓ = 1 and ℓ_{j} = 1 in Theorem 5. In this case, the minimal polynomial of T is equal to its characteristic polynomial, and T is called nonderogatory.

Theorem 9 Let T be a nonderogatory linear map on a vector space V of dimension n over 𝔽_{q}. Then

κ_{m}(T) ≥ \{ \begin{matrix}\frac{0.218}{1+log_{q} n}, & if m = 1, \\ 0.42, & if m = 2 and q = 2, \\ 1 − \frac{1.5}{q^{m−1}} ≥ \frac{1}{2}, & otherwise \end{matrix}

Proof: Let f be the minimal polynomial of T. Then f has degree n and all ℓ_{i} = 1 in Theorem 5. Hence

κ_{m}(T) = ∏_{g|f, g irred} (1 − \frac{1}{q^{m deg g}} ) .

First assume m = 1. Then κ_{1}(T) is the density of polynomials in 𝔽_{q}[X] of degrees < n that are relatively prime to f. In this case, by Theorem 2.1 in [7], we have

κ_{1}(T) ≥ (1 − \frac{1}{q}) · \frac{1}{e^{0.83}(1 + log_{q} n)} > \frac{0.218}{1 + log_{q} n},

where the factor 1−1/q accounts for the irreducible factor X that is excluded in [7].

Now assume m > 1. Let u = ⌊log_{q} n⌋ and I_{k} as in Lemma 8. Note that I_{1} = q and

I_{k} ≤ \frac{q^{k} − 1}{k} ≤ \frac{q^{k}}{2} , k ≥ 2.

By Lemma 8, we have

κ_{m}(T) ≥ ∏_{k=1}^{u+1} (1 − \frac{1}{q^{mk}} )^{I_{k}}

≥ (1 − \frac{1}{q^{m}} )^{q} ∏_{k=2}^{∞} (1 − \frac{1}{q^{mk}} )^{\frac{q^{k}−1}{k}}

≥ (1 − \frac{1}{q^{m}} )^{q} (1 − ∑_{k=2}^{∞} \frac{q^{k} − 1}{kq^{mk}})

≥ (1 − \frac{1}{q^{m}} )^{q} (1 − ∑_{k=2}^{∞} \frac{1}{2q^{(m−1)k}} )
≥ (1 − \frac{1}{q^{m}} )^{q} (1 − \frac{1}{2q^{m−1}(q^{m−1} − 1)})

which is at least 0.42 when m = 2 and q = 2, and generally at least

(1 − \frac{1}{q^{m−1}} ) (1 − \frac{1}{2q^{m−1}(q^{m−1} − 1)}) > 1 − \frac{1}{q^{m−1}} − \frac{1}{2q^{m−1}(q^{m−1} − 1)}
≥ 1 − \frac{1.5}{q^{m−1}}

for all q and m.

□

Theorem 9 can be interpreted for the following situation. Let f ∈ 𝔽_{q}[X] be any polynomial of degree n. Define κ_{m}(f) to be the probability that

gcd(f, g_{1}, …, , g_{m}) = 1

for m random polynomials g_{1}, …, g_{m} ∈ 𝔽_{q}[x] of degrees < n. Note that κ_{1}(f) is the Euler function for the polynomial f. Then for any nonderogatory linear map T on a vector space of dimension n over 𝔽_{q} that has f as its minimal polynomial, we have

κ_{m}(f) = κ_{m}(T) = ∏_{g|f, g irred} (1 − \frac{1}{q^{m deg g}} ) .

Hence the lower bounds in Theorem 9 applies to κ_{m}(f) automatically.

Corollary 10 Let f ∈ 𝔽_{q}[x] of degree n. Then

κ_{m}(f) ≥ \{ \begin{matrix}\frac{0.218}{1+log_{q} n}, & if m = 1, \\ 0.42, & if m = 2 and q = 2, \\ 1 − \frac{1.5}{q^{m−1}} ≥ \frac{1}{2}, & otherwise \end{matrix}

Remark. By Theorem 3.4 in [7], there are infinitely many values of n such that

κ_{1}(x^{n} − 1) ≤ \frac{c}{\sqrt{1 + log_{q} n}}

for some constant c > 0 depending only on q. This means that the probability may be arbitrarily close to zero and our lower bound is quite close to the upper bound. This also applies to the lower bound in Thereom 11 below for m = ℓ.

Now we turn to the general case where we obtain slightly weaker bounds. The next result is the main theorem stated in the introduction.

Theorem 11 Let T be any linear map on a vector space of dimension n over 𝔽_{q}. Let ℓ be the Frobenius index of T and let m ≥ ℓ. Then

κ_{m}(T) ≥ \{ \begin{matrix}\frac{0.04}{1+log_{q}(n−ℓ+1)}, & if m = ℓ \\ \frac{1}{8}, & if m = ℓ + 1 and q = 2 \\ 1 − \frac{3}{2^{m−ℓ}} ≥ \frac{1}{4}, & if m ≥ ℓ + 2 and q = 2 \\ 1 − \frac{2}{q^{m−ℓ}} ≥ \frac{1}{3}, & if m ≥ ℓ + 1 and q > 2. \end{matrix}

Proof: Let f be the minimal polynomial of T. Then deg f ≤ n − ℓ + 1 as at one irreducible factor of f appears ℓ times in the characteristic polynomial of T, which has degree n and is divisible by f. Let u = ⌊log_{q}(n − ℓ + 1)⌋. By Theorem 5 and Lemma 8, we have

κ_{m}(T) = ∏_{j=1}^{a} ∏_{i=1}^{ℓ_{i}} (1 − (\frac{1}{q^{d_{j}}} )^{m−ℓ_{i}+i})

≥ ∏_{j=1}^{a} ∏_{i=1}^{ℓ} (1 − (\frac{1}{q^{d_{j}}} )^{m−ℓ+i})

= ∏_{i=1}^{ℓ} ∏_{g|f, g irred} (1 − (\frac{1}{q^{deg g}} )^{m−ℓ+i})

≥ ∏_{i=1}^{ℓ} ∏_{k=1}^{u+1} (1 − (\frac{1}{q^{k}} )^{m−ℓ+i})^{I_{k}} .  (2)

Assume first that m = ℓ. Then

κ_{m}(T) ≥ ∏_{i=1}^{ℓ} ∏_{k=1}^{u+1} (1 − (\frac{1}{q^{k}} )^{i})^{I_{k}}

≥ ∏_{i=1}^{ℓ} (1 − \frac{1}{q^{i}} ) ∏_{i=1}^{ℓ} ∏_{k=1}^{u+1} (1 − \frac{1}{q^{ki}} )^{\frac{q^{k}−1}{k}}

≥ ∏_{i=1}^{ℓ} (1 − \frac{1}{q^{i}} ) ∏_{k=1}^{u+1} (1 − \frac{1}{q^{k}} )^{\frac{q^{k}−1}{k}} ∏_{k=1}^{∞} ∏_{i=2}^{∞} (1 − \frac{1}{q^{ki}} )^{\frac{q^{k}−1}{k}} .

By Lemma 7, we know the first product is at least 0.288. For the second product, the proof of Theorem 2.1 in [7] implies

∏_{k=1}^{u+1} (1 − \frac{1}{q^{k}} )^{\frac{q^{k}−1}{k}} ≥ \frac{1}{e^{0.83}(1 + u)} ≥ \frac{1}{e^{0.83}(1 + log_{q}(n − ℓ + 1))}.

To estimate the third product, we recall the fact that

ln(1 − x) ≥ −(x + x^{2}), 0 ≤ x ≤ 0.6.

Then

∏_{k=1}^{∞} ∏_{i=2}^{∞} (1 − \frac{1}{q^{ki}} )^{\frac{q^{k}−1}{k}} = exp (∑_{k=1}^{∞} ∑_{i=2}^{∞} \frac{q^{k} − 1}{k} ln(1 − \frac{1}{q^{ki}}))

≥ exp (− ∑_{k=1}^{∞} ∑_{i=2}^{∞} \frac{q^{k} − 1}{k}(\frac{1}{q^{ki}} + \frac{1}{q^{2ki}}))
≥ exp (− ∑_{k=1}^{∞} \frac{q^{k} − 1}{k}(\frac{1}{q^{k}(q^{k} − 1)} + \frac{1}{q^{2k}(q^{2k} − 1)}))
≥ exp (− ∑_{k=1}^{∞}(\frac{1}{q^{k}} + \frac{1}{q^{3k}}))
≥ exp (−(\frac{1}{q − 1} + \frac{1}{q^{3} − 1}))
≥ exp (−(1 + \frac{1}{7})) > 0.3189.

Therefore, when m = ℓ,

κ_{m}(T) > \frac{0.288 · 0.3189}{e^{0.83}} · \frac{1}{1 + log_{q}(n − ℓ + 1)} > \frac{0.04}{1 + log_{q}(n − ℓ + 1)}.

Finally assume m > ℓ. Then from Equation (2)

κ_{m}(T) ≥ ∏_{i=1}^{∞} (1 − \frac{1}{q^{m−ℓ+i}} )^{q} ∏_{k=2}^{∞} ∏_{i=1}^{∞} (1 − \frac{1}{q^{k(m−ℓ+i)}} )^{\frac{q^{k}−1}{k}} .

For the first product, we have

∏_{i=1}^{∞} (1 − \frac{1}{q^{m−ℓ+i}} )^{q} ≥ (1 − \frac{q}{q^{m−ℓ+1}} ) (1 − ∑_{i=2}^{∞} \frac{q}{q^{m−ℓ+i}} )
≥ (1 − \frac{1}{q^{m−ℓ}} ) (1 − \frac{1}{q^{m−ℓ}(q − 1)})

which is 1/4 for m = ℓ + 1 and q = 2. For the second product, we have

∏_{k=2}^{∞} ∏_{i=1}^{∞} (1 − \frac{1}{q^{k(m−ℓ+i)}} )^{\frac{q^{k}−1}{k}} ≥ 1 − ∑_{k=2}^{∞} ∑_{i=1}^{∞} \frac{q^{k} − 1}{kq^{k(m−ℓ+i)}}
≥ 1 − ∑_{k=2}^{∞} ∑_{i=1}^{∞} \frac{1}{kq^{k(m−ℓ+i−1)}}
≥ 1 − ∑_{k=2}^{∞} \frac{1}{kq^{k(m−ℓ−1)}(q^{k} − 1)}

≥ 1 − ∑_{k=2}^{∞} \frac{1}{q^{k(m−ℓ)}}
≥ 1 − \frac{1}{q^{m−ℓ}(q^{m−ℓ} − 1)}

which is 1/2 for m = ℓ + 1 and q = 2. Therefore κ_{m}(T) is at least \frac{1}{4} · \frac{1}{2} = \frac{1}{8} for m = ℓ + 1 and q = 2. In general when m > ℓ it is at least

(1 − \frac{1}{q^{m−ℓ}} ) (1 − \frac{1}{q^{m−ℓ}(q − 1)}) (1 − \frac{1}{q^{m−ℓ}(q^{m−ℓ} − 1)})

≥ 1 − \frac{1}{q^{m−ℓ}} − \frac{1}{q^{m−ℓ}(q − 1)} − \frac{1}{q^{m−ℓ}(q^{m−ℓ} − 1)}

≥ 1 − \frac{q + 1}{q − 1} \frac{1}{q^{m−ℓ}} ≥ 1 − \frac{3}{q^{m−ℓ}} .

For q = 2 and m ≥ ℓ + 2 this is 1 − \frac{3}{2^{m−ℓ}} ≥ \frac{1}{4}, and for q ≥ 3 and m ≥ ℓ + 1 at least 1 − \frac{2}{q^{m−1}} ≥ \frac{1}{3}.

□

References

[1] W. A. Adkins and S. H. Weintraub, Algebra: an approach via module theory, Graduate Texts in Mathematics 136, Springer-Verlag, 1992.

[2] R. P. Brent and B. D. McKay, Determinants and ranks of random matrices over ℤ_{m}, Discrete Mathematics, 66 (1987), pp. 35-49.

[3] D. Coppersmith, Solving linear equations over GF (2): block Lanczos algorithm, Linear Algebra and Its Applications, 192 (1993), pp. 33–60.

[4] D. Coppersmith, Solving homogeneous linear equations over GF (2) via block Wiedemann algorithm, Math. Comp., 62 (1994), no. 205, pp. 333-350.

[5] S. Gao, Factoring multivariate polynomials via partial differential equations, to appear in Math. Comp. (28 pages).

[6] S. Gao and J. von zur Gathen, Berlekamp’s and Niederreiter’s polynomial factorization algorithms, Proc. 2nd International Conference on Finite Fields: Theory, Applications, and Algorithms, Las Vegas, 1993, Contemporary Mathematics, vol. 168, 1994, pp. 101–116.

[7] S. Gao and D. Panario, Density of normal elements in finite fields, Finite Fields and Their Applications, 3 (1997), pp. 141–150.

[8] E. Kaltofen, Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems, Math. Comp., 64 (1995), pp. 777–806.

[9] E. Kaltofen and A. Lobo, Factoring high-degree polynomials by the black box Berlekamp algorithm, in ISSAC’94, pp. 90-98.

[10] G. Landsberg, Über eine Anzahlbestimmung und eine damit zusammenhängende Reihe, J. Reine und Angewandte Math., 111 (1893), pp. 87-88.

[11] A. K. Lenstra and H. W. Lenstra, Jr., editors, The Development of the Number Field Sieve, Lecture Notes in Mathematics, 1554, Springer-Verlag, 1993.

[12] P. L. Montgomery, A block Lanczos Algorithm for finding dependencies over GF (2), Advances in cryptology—EUROCRYPT ’95 (Saint-Malo, 1995), Lecture Notes in Computer Science 921, Springer, Berlin, 1995, pp. 106–120.

[13] D.J.S. Robinson, A course in the theory of groups, Graduate Texts in Mathematics 80, 2nd Edition, Springer-Verlag, 1996.

[14] G. Villard, Further analysis of Coppersmith’s block Wiedemann algorithm for the solution of sparse linear systems, in International Symposium on Symbolic and Algebraic Computation, Maui, Hawaii, USA. ACM Press, July 1997.

[15] G. Villard, A study of Coppersmith’s block Wiedemann algorithm using matrix polynomials, LMC-IMAG, report # 975 IM, April 1997. (38 pages)

[16] D.H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Info. Theory Vol IT-32, No. 1, (1986), 54-62.