BLOCK COMPANION SINGER CYCLES, PRIMITIVE RECURSIVE VECTOR SEQUENCES, AND COPRIME POLYNOMIAL PAIRS OVER FINITE FIELDS

SUDHIR R. GHORPADE AND SAMRITH RAM

Abstract. We discuss a conjecture concerning the enumeration of nonsingular matrices over a finite field that are block companion and whose order is the maximum possible in the corresponding general linear group. A special case is proved using some recent results on the probability that a pair of polynomials with coefficients in a finite field is coprime. Connection with an older problem of Niederreiter about the number of splitting subspaces of a given dimension are outlined and an asymptotic version of the conjectural formula is established. Some applications to the enumeration of nonsingular Toeplitz matrices of a given size over a finite field are also discussed.

1. Introduction

Let 𝔽_{q} denote the finite field with q elements and let m, n be positive integers. For any positive integer d, we denote by M_{d}(𝔽_{q}) the set of all d × d matrices with entries in 𝔽_{q}, and by GL_{d}(𝔽_{q}) the group of all nonsingular matrices in M_{d}(𝔽_{q}). By an (m, n)-block companion matrix over 𝔽_{q} we mean T ∈ M_{mn}(𝔽_{q}) of the form

(1)  T = (\begin{matrix}0 & 0 & 0 & . & . & 0 & 0 & C_{0} \\ I_{m} & 0 & 0 & . & . & 0 & 0 & C_{1} \\ . & . & . & . & . & . & . & . \\ . & . & . & . & . & . & . & . \\ 0 & 0 & 0 & . & . & I_{m} & 0 & C_{n−2} \\ 0 & 0 & 0 & . & . & 0 & I_{m} & C_{n−1} \end{matrix}) ,

where C_{0}, C_{1}, …, C_{n−1} ∈ M_{m}(𝔽_{q}) and I_{m} denotes the m × m identity matrix over 𝔽_{q}, while 0 indicates the zero matrix in M_{m}(𝔽_{q}). If such a matrix T is a Singer cycle in GL_{mn}(𝔽_{q}), that is, if T is nonsingular and the order of T in the group GL_{mn}(𝔽_{q}) is the maximum possible (viz., q^{mn}−1), then we will call it a (m, n)-block companion Singer cycle over 𝔽_{q}. We are primarily interested in the following.

Conjecture 1.1. The number of (m, n)-block companion Singer cycles over 𝔽_{q} is

(2)  \frac{ϕ(q^{mn} − 1)}{mn} q^{m(m−1)(n−1)} ∏_{i=1}^{m−1}(q^{m} − q^{i}),

where ϕ is the Euler totient function.

Date: February 25, 2011.

2000 Mathematics Subject Classification. 11T35, 11T06, 20G40, 15B05.

Key words and phrases. Singer cycle, Block companion matrix, Multiple Recursive Matrix Method, Linear Feedback Shift Register (LFSR), Splitting subspace, Toeplitz matrix.

To appear in: Finite Fields Appl. (2011).

This conjecture arose in the study by Zeng, Han and He [20] of word-oriented linear feedback shift registers, called σ-LFSRs and is equivalent to showing that the number of primitive σ-LFSRs of order n over 𝔽_{q^{m}} is given by (2) above. It may be noted that a special case of σ-LFSRs appears earlier in the work of Tsaban and Vishne [18]. Moreover, the σ-LFSRs turn out to be essentially the same as recursive vector sequences studied by Niederreiter [14, 15] in the context of his work on pseudorandom number generation and his multiple-recursive matrix method. As such the question about the enumeration of block companion Singer cycles over 𝔽_{q} is intimately related to the open problem about the determination of the total number of σ-splitting subspaces over 𝔽_{q} of a given dimension. (See Section 5 for details.) Nonetheless, the explicit conjectural formula (2) should be attributed to Zeng, Han and He [20], at least in the binary case, whereas the above formulation in the q-ary case is as in [7]. Although there is significant numerical evidence in its favour, Conjecture 1.1 is open, in general, except in the trivial case m = 1 (and any n) and the not-so-trivial special case n = 1 (and any m), where it is proved in [7]. A plausible approach to proving Conjecture 1.1 in the general case was proposed in [7] and a more refined, but perhaps more amenable, conjecture called the Fiber Conjecture was formulated there.

In this paper, we prove that the Fiber Conjecture and, as an immediate consequence, Conjecture 1.1, holds in the affirmative in the case m = 2 (and any n). In fact, we consider a more general version of the Fiber Conjecture, called Irreducible Fiber Conjecture, and show that it is valid when m = 2. One of the key tools used is the recent work on the question of determining the probability of two randomly chosen polynomials of a given positive degree with coefficients in 𝔽_{q} being relatively prime. This question can be traced back to an exercise in Knuth’s book [12, §4.6.1, Ex. 5] (see also [6, Rem. 4.2]). More recently, it arose in the study by Corteel, Savage, Wilf, and Zeilberger [2] of Euler’s pentagonal sieve in the theory of partitions and has led to a number of developments; we refer to the subsequent work of Reifegerate [16], Benjamin and Bennett [1], Gao and Panario [5], Hao and Mullen [9], and of García-Armas, Ghorpade and Ram [6] for more on this topic. While the general case of Conjecture 1.1 as well as Niederreiter’s splitting subspace problem still remains open, we provide a quantitative version of the latter together with a refinement, which imply the former. (See Section 5 for details). Moreover, in Section 6, we give an asymptotic formula for the cardinality of an irreducible fiber, which appears to strengthen the validity of the conjectural formula (2). Finally, as an application of some of the methods used in our proof, we deduce a formula for the number of nonsingular Toeplitz matrices (or equivalently, the number of nonsingular Hankel matrices) over 𝔽_{q}, which has also been of some recent interest.

2. The Characteristic Map

Denote, as usual, by 𝔽_{q}[X] the ring of polynomials in one variable X with coefficients in 𝔽_{q}. Recall that a polynomial in 𝔽_{q}[X] of degree d ≥ 1 is said to be primitive if it is the minimal polynomial over 𝔽_{q} of a generator of the cyclic group 𝔽_{q^{d}}^{∗} of nonzero elements of the finite field 𝔽_{q^{d}}. Fix, throughout this paper, positive integers m and n. Let

𝒫(mn; q) := {p(X) ∈ 𝔽_{q}[X] : p(X) is primitive of degree mn}

and let

ℐ(mn; q) := {p(X) ∈ 𝔽_{q}[X] : p(X) is monic and irreducible of degree mn} .

Evidently, 𝒫(mn; q) ⊆ ℐ(mn; q), but the reverse inclusion is not true, in general. The cardinalities of these sets are well known (cf. [7, §2], [13, p. 93]); namely,

(3)  |𝒫(mn; q)| = \frac{ϕ(q^{mn} − 1)}{mn} and |ℐ(mn; q)| = \frac{1}{mn} ∑_{d|mn} μ (\frac{mn}{d}) q^{d},

where μ denotes the Möbius function.

The map which associates to an mn × mn matrix its characteristic polynomial, viz.,

Φ : M_{mn}(𝔽_{q}) → 𝔽_{q}[X] defined by Φ(T) := det (XI_{mn} − T)

will often be referred to as the characteristic map. We denote by BCMS(m, n; q) the set of (m, n)-block companion Singer cycles over 𝔽_{q}, and by BCMI(m, n; q) the set of (m, n)-block companion matrices over 𝔽_{q} having an irreducible characteristic polynomial. Evidently, BCMS(m, n; q) ⊆ BCMI(m, n; q) and Φ maps BCMI(m, n; q) into ℐ(mn; q). A little less obvious, yet elementary, fact is that a nonsingular matrix is a Singer cycle if and only if its characteristic polynomial is primitive (see, e.g., [7, Prop. 3.1]); in particular, Φ maps BCMS(m, n; q) into 𝒫(mn; q). As a result, restrictions of Φ yield the following maps:

Ψ : BCMS(m, n; q) → 𝒫(mn; q) and Θ : BCMI(m, n; q) → ℐ(mn; q).

The following result is proved in [7, Theorem 6.1].

Proposition 2.1. Ψ is surjective.

Here is a small generalization of Proposition 2.1 for which a proof is included. This can also be viewed as an alternative, and slightly shorter, proof of Proposition 2.1 compared to the one given in [7].

Proposition 2.2. Θ is surjective and hence so is Ψ.

Proof. Let f ∈ ℐ(mn; q). If α ∈ 𝔽_{q^{mn}} is a root of f, then 𝔽_{q^{mn}} = 𝔽_{q}(α) = 𝔽_{q^{m}}(α). In particular, [𝔽_{q^{m}}(α) : 𝔽_{q^{m}}] = n and moreover, if g ∈ 𝔽_{q^{m}}[X] denotes the minimal polynomial of α over 𝔽_{q^{m}}, then deg g = n and g divides f in 𝔽_{q^{m}}[X]. Write g = X^{n} − β_{n−1}X^{n−1} − ⋯ − β_{1}X − β_{0}. Now for any β ∈ 𝔽_{q^{m}}, let L_{β} : 𝔽_{q^{m}} → 𝔽_{q^{m}} denote the 𝔽_{q}-linear transformation defined by L_{β}(x) := βx, and let A_{β} ∈ M_{m}(𝔽_{q}) be the matrix of L_{β} with respect to a fixed 𝔽_{q}-basis of 𝔽_{q^{m}}. It is clear that for any β, γ ∈ 𝔽_{q^{m}} and λ ∈ 𝔽_{q}, we have

(4)  A_{β+γ} = A_{β} + A_{γ}, A_{βγ} = A_{β}A_{γ} and A_{λβ} = λA_{β}.

Consider the companion matrix C_{g} ∈ M_{n}(𝔽_{q^{m}}) of g and the corresponding (m, n)- block companion matrix T ∈ M_{mn}(𝔽_{q}), namely,

C_{g} = (\begin{matrix}0 & 0 & … & 0 & β_{0} \\ 1 & 0 & … & 0 & β_{1} \\ ⋮ & & ... & & ⋮ \\ 0 & 0 & … & 1 & β_{n−1} \end{matrix}) and T = (\begin{matrix}0 & 0 & … & 0 & C_{0} \\ I_{m} & 0 & … & 0 & C_{1} \\ ⋮ & & ... & . & ⋮ \\ 0 & 0 & … & I_{m} & C_{n−1} \end{matrix}) ,

where we have let C_{i} = A_{β_{i}} for i = 0, 1, …, n − 1. By the Cayley-Hamilton Theorem, g(C_{g}) = 0 and hence f(C_{g}) = 0. The last equation corresponds to n^{2} polynomial expressions in β_{0}, β_{1}, …, β_{n−1} with coefficients in 𝔽_{q} being equal to zero. In view of (4), these equations continue to hold if β_{i}’s are replaced by C_{i}’s. Consequently, f(T) = 0. Since f ∈ 𝔽_{q}[X] is monic and irreducible of degree mn, it follows that f is the characteristic polynomial of T, i.e., f = Θ(T). □

As an immediate consequence of Proposition 2.2, we obtain natural decompositions of BCMS(m, n; q) and BCMI(m, n; q) as disjoint unions of the fibers of the maps Ψ and Θ, respectively. This decomposition of BCMS(m, n; q) and Proposition 2.1 suggested the following refined version proposed in [7] of Conjecture 1.1.

Conjecture 2.3. |Ψ^{−1} (f)| = q^{m(m−1)(n−1)} ∏_{i=1}^{m−1}(q^{m} − q^{i}) for any f ∈ 𝒫(mn; q).

In light of Proposition 2.2, we propose the following more general version of Conjecture 2.3.

Conjecture 2.4. |Θ^{−1} (f)| = q^{m(m−1)(n−1)} ∏_{i=1}^{m−1}(q^{m} − q^{i}) for any f ∈ ℐ(mn; q).

It is clear that if Conjecture 2.4 holds in the affirmative, then so do Conjecture 2.3 and Conjecture 1.1. We may refer to Conjecture 2.4 as the Irreducible Fiber Conjecture. Moreover, Conjecture 2.3, which has hitherto been called Fiber Conjecture, may now be referred to as the Primitive Fiber Conjecture.

3. Relatively Prime Polynomials

Let us begin by recalling a result about relatively prime polynomials, namely, [2, Prop. 3] (see also [12, Exer. 5 of §4.6.1] and [6, Thm. 4.1]), which was alluded to in the introduction. In this section, r will denote an integer ≥ 2 and, as before, n is a fixed positive integer.

Proposition 3.1. The number of coprime r-tuples of monic polynomials of degree n over 𝔽_{q} is q^{rn} − q^{r(n−1)+1}. Alternatively, if r monic polynomials in 𝔽_{q}[X] are chosen independently and uniformly at random, then the probability that they are relatively prime is 1 − 1/q^{r−1}.

A special case of the above result implies that there is a 50% chance that two monic polynomials of a given positive degree in 𝔽_{2}[X] are coprime. With this in view, Corteel, Savage, Wilf, and Zeilberger [2] asked for an explicit bijection between coprime and non-coprime pairs of monic polynomials of a given positive degree in 𝔽_{2}[X]. A nice answer was given by Benjamin and Bennett who proved, more generally, the following result in [1, Cor. 6].

Proposition 3.2. If r polynomials of degree lees than n in 𝔽_{q}[X] are randomly chosen, then the probability that they are relatively prime is

1 − \frac{1}{q^{r−1}} + \frac{q − 1}{q^{rn}}.

For our purpose, the following consequence of the above result will be useful.

Corollary 3.3. Let Σ denote the set of pairs (f, g) of nonzero polynomials in 𝔽_{q}[X] of degree < n such that f and g are relatively prime and moreover g is monic. Then the cardinality of Σ is equal to (q^{2n−1} − 1).

Proof. Since the number of pairs of polynomials of degree < n in 𝔽_{q}[X] is q^{2n}, by Proposition 3.2, the number of coprime pairs of polynomials in 𝔽_{q}[X] of degree < n is equal to (q^{2n−1} + 1)(q − 1). Now, as per the standard conventions, the only polynomials that are coprime to the zero polynomial are the nonzero constant polynomials. Hence if Σ_{1} denotes the set of coprime pairs of nonzero polynomials in 𝔽_{q}[X] of degree < n, then |Σ_{1}| = (q^{2n−1} +1)(q−1)−2(q−1) = (q^{2n−1} −1)(q−1). Finally, since Σ = {(f, g) ∈ Σ_{1} : g is monic}, it follows that |Σ| = |Σ_{1}| /(q − 1). □

4. The Case m = 2

Given any α, v_{1}, v_{2} ∈ 𝔽_{q^{2n}}, we let

ℬ_{(v_{1},v_{2})}^{α} := {v_{1}, v_{2}, αv_{1}, αv_{2}, …, α^{n−1}v_{1}, α^{n−1}v_{2}} ,

with the proviso that ℬ_{(v_{1},v_{2})}^{α} is to be regarded as an ordered set with 2n elements; in most applications it will be an ordered basis of 𝔽_{q^{2n}} over 𝔽_{q}. Our first step is to relate the fibers of Θ to ordered bases of the form ℬ_{(v_{1},v_{2})}^{α}.

Lemma 4.1. Let f ∈ ℐ(2n; q) and let α ∈ 𝔽_{q^{2n}} be a root of f. As before, let L_{α} : 𝔽_{q^{2n}} → 𝔽_{q^{2n}} denote the 𝔽_{q}-linear transformation defined by L_{α}(x) := αx for x ∈ 𝔽_{q^{2n}}, and let T ∈ M_{2n}(𝔽_{q}). Then T ∈ Θ^{−1}(f) if and only if T is the matrix of L_{α} with respect to an ordered basis of the form ℬ_{(v_{1},v_{2})}^{α} for some v_{1}, v_{2} ∈ 𝔽_{q^{2n}}.

Proof. Since f is irreducible, {1, α, …, α^{2n−1}} is an 𝔽_{q}-basis of 𝔽_{q^{2n}}. Moreover, since f is also monic, the matrix of L_{α} with respect to this basis is precisely the companion matrix C_{f} of f.

Suppose T ∈ Θ^{−1}(f). Then the monic irreducible polynomial f is the characteristic polynomial of T. It follows that T and C_{f} have the same invariant factors and hence they are similar. Consequently, T is the matrix of L_{α} with respect to some ordered 𝔽_{q}-basis ℬ of 𝔽_{q^{2n}}. Further since T is a (2, n)-block companion matrix, we see that ℬ must be of the form ℬ_{(v_{1},v_{2})}^{α} for some v_{1}, v_{2} ∈ 𝔽_{q^{2n}}.

Conversely, suppose T is the matrix of L_{α} with respect to an ordered basis of the form ℬ_{(v_{1},v_{2})}^{α} for some v_{1}, v_{2} ∈ 𝔽_{q^{2n}}. Then T is clearly a (2, n)-block companion matrix and moreover, T is similar to C_{f}. It follows that T ∈ Θ^{−1}(f). □

The next step is to count the number of ordered bases of the form ℬ_{(v_{1},v_{2})}^{α}, and this is where the results of the previous section will turn out to be handy.

Lemma 4.2. Fix f ∈ ℐ(2n; q) and a root α ∈ 𝔽_{q^{2n}} of f. Then the number of ordered bases of the form ℬ_{(v_{1},v_{2})}^{α}, as v_{1}, v_{2} vary over 𝔽_{q^{2n}}, is equal to q^{2n−1}(q −1)(q^{2n} −1).

Proof. First, fix any v_{1} ∈ 𝔽_{q^{2n}} with v_{1} ≠ 0. Then for any v_{2} ∈ 𝔽_{q^{2n}}, the ordered set ℬ_{(v_{1},v_{2})}^{α} is an 𝔽_{q}-basis of 𝔽_{q^{2n}} if and only if the ordered set

𝒮_{β} := {1, β, α, αβ, …, α^{n−1}, α^{n−1}β}

is linearly independent over 𝔽_{q}, where β := v_{2}/v_{1}. Now, 1, α, …, α^{2n−1} are linearly independent over 𝔽_{q} and in particular, so are 1, α, …, α^{n−1}. Thus for any β ∈ 𝔽_{q^{2n}}^{∗}, the ordered set 𝒮_{β} is 𝔽_{q}-independent if and only if β cannot be expressed as

\frac{a_{0} + a_{1}α + ⋯ + a_{n−1}α^{n−1}}{b_{0} + b_{1}α + ⋯ + b_{n−1}α^{n−1}}

for some a_{i}, b_{i} ∈ 𝔽_{q} such that not all a_{i} are zero and not all b_{i} are zero (0 ≤ i ≤ n−1). It follows that {β ∈ 𝔽_{q^{2n}}^{∗} : 𝒮_{β} is linearly independent} = 𝔽_{q^{2n}}^{∗} \ Σ_{α}, where

Σ_{α} := \{\frac{f(α)}{g(α)} : f, g ∈ 𝔽_{q}[X]^{∗}, deg(f) ≤ n − 1, and deg(g) ≤ n − 1 \} .

Now if Σ is as in Corollary 3.3, then the map Σ → Σ_{α} given by (f, g) ↦ f(α)/g(α) is clearly well defined and surjective. Moreover, if (f_{1}, g_{1}), (f_{2}, g_{2}) ∈ Σ are such that f_{1}(α)g_{2}(α) = f_{2}(α)g_{1}(α), then f_{1}(X)g_{2}(X) = f_{2}(X)g_{1}(X) because the minimal polynomial of α over 𝔽_{q} has degree 2n. Further since f_{i} and g_{i} are coprime for i = 1, 2 and since g_{1}, g_{2} are monic, it follows that g_{1} = g_{2} and therefore f_{1} = f_{2}. Thus Σ_{α} is in bijection with Σ, and hence by Corollary 3.3,

|{β ∈ 𝔽_{q^{2n}}^{∗} : 𝒮_{β} is linearly independent }| = (q^{2n} − 1) − (q^{2n−1} − 1) = q^{2n−1}(q − 1).

Finally, if we vary v_{1} over the (q^{2n}−1) elements of 𝔽_{q^{2n}}^{∗}, then we readily see that the number of ordered bases of the form ℬ_{(v_{1},v_{2})}^{α} is equal to q^{2n−1}(q − 1)(q^{2n} − 1). □

It is possible that two different bases of the form ℬ_{(v_{1},v_{2})}^{α} can give rise to the same matrix. This redundancy can be quantified using the centralizer.

Lemma 4.3. Let f, α and L_{α} be as in Lemma 4.1. Then there are exactly (q^{2n} −1) ordered bases of the form ℬ_{(v_{1},v_{2})}^{α} such that that the matrix of L_{α} with respect to each of these bases is the same.

Proof. Suppose T is the matrix of L_{α} with respect to an ordered basis ℬ_{(v_{1},v_{2})}^{α} for some v_{1}, v_{2} ∈ 𝔽_{q^{2n}}. If T is also the matrix of L_{α} with respect to ℬ_{(w_{1},w_{2})}^{α} for some w_{1}, w_{2} ∈ 𝔽_{q^{2n}}, then the “change of basis matrix” that transforms ℬ_{(v_{1},v_{2})}^{α} into ℬ_{(w_{1},w_{2})}^{α} is a 2n×2n invertible matrix P over 𝔽_{q} with the property that P^{−1}T P = T. Conversely if P ∈ GL_{2n}(𝔽_{q}) is in the centralizer Z(T), that is, if P^{−1}T P = T, then P transforms ℬ_{(v_{1},v_{2})}^{α} into an ordered basis with respect to which the matrix of L_{α} is T and (therefore) it is necessarily of the form ℬ_{(w_{1},w_{2})}^{α} for some w_{1}, w_{2} ∈ 𝔽_{q^{2n}}. It follows that the desired number of ordered bases is |Z(T)|. Finally, since the linear transformation L_{α} is cyclic with f as its minimal (as well as characteristic) polynomial, by a theorem of Frobenius [10, Thm. 3.16 and its corollary], we see that Z(T) consists only of polynomials in T. Consequently, Z(T)∪{0} is the 𝔽_{q}-algebra of polynomials in T, which is isomorphic to 𝔽_{q}[X]/ ⟨f⟩. Hence |Z(T)| = q^{2n}−1. □

The following result shows that Conjectures 2.4, 2.3, and 1.1 hold in the affirmative when m = 2.

Theorem 4.4. |Θ^{−1} (f)| = q^{2n−1}(q − 1) for any f ∈ ℐ(2n; q). In particular, |Ψ^{−1} (f)| = q^{2n−1}(q − 1) for any f ∈ 𝒫(2n; q). Consequently,

|BCMS(2, n; q)| = \frac{ϕ(q^{2n} − 1)}{2n} q^{2n−1}(q − 1)

and

|BCMI(2, n; q)| = \frac{1}{2n} (∑_{d|2n} μ (\frac{2n}{d}) q^{d}) q^{2n−1}(q − 1).

Proof. By Lemmas 4.1, 4.2, and 4.3, we readily see that

|Θ^{−1} (f)| = \frac{q^{2n−1}(q − 1)(q^{2n} − 1)}{(q^{2n} − 1)} = q^{2n−1}(q − 1) for any f ∈ ℐ(2n; q).

Since a nonsingular matrix is a Singer cycle if and only if its characteristic polynomial is primitive [7, Prop. 3.1], this implies, in particular, that |Ψ^{−1} (f)| = q^{2n−1}(q − 1) for any f ∈ 𝒫(2n; q). Consequently, we obtain the desired formulae for |BCMS(2, n; q)| and |BCMI(2, n; q)| using (3) and Proposition 2.2. □

5. Splitting Subspaces

Let σ ∈ 𝔽_{q^{mn}}. Following Niederreiter [15], we call an m-dimensional 𝔽_{q}-linear subspace W of 𝔽_{q^{mn}} to be σ-splitting if 𝔽_{q^{mn}} = W ⊕ σW ⊕ ⋯ ⊕ σ^{n−1}W. Define

S(σ, m, n; q) := the number of σ-splitting subspaces of 𝔽_{q^{mn}} of dimension m.

Note that for an arbitrary σ ∈ 𝔽_{q^{mn}}, there may not be any σ-splitting subspace; for example, if σ ∈ 𝔽_{q}, then σ^{i}W = W for every m-dimensional subspace W and every i ≥ 0, and so W cannot be σ-splitting if n > 1. But if n = 1, then the only m-dimensional subspace, viz., W = 𝔽_{q^{mn}}, is σ-splitting for every σ ∈ 𝔽_{q^{mn}}; in particular, S(σ, m, 1; q) = 1. On the other hand, if m = 1 and if α ∈ 𝔽_{q^{mn}} = 𝔽_{q^{n}} is such that 𝔽_{q^{mn}} = 𝔽_{q}(α), then every 1-dimensional subspace is α-splitting and so S(α, 1, n; q) = (q^{n} − 1)/(q − 1).

Determination of S(σ, m, n; q), where σ is a primitive element of 𝔽_{q^{mn}}^{∗}, is stated as an open problem in [15, p. 11] and Professor Niederreiter has informed us that the problem is still open. We shall see below that this problem is essentially equivalent to the Irreducible Fiber Conjecture, and this will allow us to formulate a quantitative version of the problem.

First, let us observe that some of the notions and results of Section 4 extend readily to the case of arbitrary m. Given any α, v_{1}, …, v_{m} ∈ 𝔽_{q^{mn}}, we let

ℬ_{(v_{1},...,v_{m})}^{α} := {v_{1}, …, v_{m}, αv_{1}, …, αv_{m}, …, α^{n−1}v_{1}, …, α^{n−1}v_{m}} ,

with the proviso that ℬ_{(v_{1},...,v_{m})}^{α} is to be regarded as an ordered set with mn elements. Also, let L_{α} : 𝔽_{q^{mn}} → 𝔽_{q^{mn}} denote the 𝔽_{q}-linear transformation defined by L_{α}(x) := αx for x ∈ 𝔽_{q^{mn}}. Proofs of the following two results are straightforward extensions of the proofs of Lemmas 4.1 and 4.3 and are left to the reader.

Lemma 5.1. Let T ∈ M_{mn}(𝔽_{q}), f ∈ ℐ(mn; q) and let α ∈ 𝔽_{q^{mn}} be a root of f. Then T ∈ Θ^{−1}(f) if and only if T is the matrix of L_{α} with respect to an ordered basis of the form ℬ_{(v_{1},...,v_{m})}^{α} for some v_{1}, … v_{m} ∈ 𝔽_{q^{mn}}.

Proof. Similar to the proof of Lemma 4.1. □

Lemma 5.2. Let f ∈ ℐ(mn; q) and let α ∈ 𝔽_{q^{mn}} be a root of f. Then there are exactly (q^{mn} − 1) ordered bases of the form ℬ_{(v_{1},...,v_{m})}^{α} such that that the matrix of L_{α} with respect to each of these bases is the same.

Proof. Similar to the proof of Lemma 4.3. □

Determining the number of bases of the form ℬ_{(v_{1},...,v_{m})}^{α} seems quite difficult, in general, but we can certainly give this a name. Thus, for any α ∈ 𝔽_{q^{mn}} such that 𝔽_{q^{mn}} = 𝔽_{q}(α), we define

N(α, m, n; q) := the number of ordered bases of 𝔽_{q^{mn}} of the form ℬ_{(v_{1},...,v_{m})}^{α}.

As an immediate consequence of Lemmas 5.1 and 5.2, we see that

(5) |Θ^{−1}(f)| = \frac{N(α, m, n; q)}{q^{mn} − 1} for any f ∈ ℐ(mn; q) and any root α ∈ 𝔽_{q^{mn}} of f.

In particular, N(α, m, n; q) is unchanged if α is replaced by any of its conjugates with respect to the field extension 𝔽_{q^{mn}}/𝔽_{q}.

The relation between splitting subspaces of 𝔽_{q^{mn}} of dimension m and ordered bases of the form ℬ_{(v_{1},...,v_{m})}^{α} should be quite clear by now. For ease of reference, this is stated below and we remark that this is just a paraphrasing of [15, Lem. 3].

Lemma 5.3. Let α ∈ 𝔽_{q^{mn}} be such that 𝔽_{q^{mn}} = 𝔽_{q}(α), and let v_{1}, …, v_{m} ∈ 𝔽_{q^{mn}}. Also let W denote the 𝔽_{q}-linear subspace of 𝔽_{q^{mn}} spanned by v_{1}, …, v_{m}. Then ℬ_{(v_{1},...,v_{m})}^{α} is an ordered basis of 𝔽_{q^{mn}} if and only if W is an m-dimensional splitting subspace of 𝔽_{q^{mn}}.

Proof. Straightforward. □

Corollary 5.4. Let α ∈ 𝔽_{q^{mn}} be such that 𝔽_{q^{mn}} = 𝔽_{q}(α). Then

S(α, m, n; q) = \frac{N(α, m, n; q)}{|GL_{m}(𝔽_{q})|}, that is, N(α, m, n; q) = S(α, m, n; q) ∏_{i=0}^{m−1}(q^{m}−q^{i}).

Proof. Follows from Lemma 5.3 and the fact that the number of distinct ordered bases of an m-dimensional vector space over 𝔽_{q} is |GL_{m}(𝔽_{q})| = ∏_{i=0}^{m−1}(q^{m} −q^{i}). □

In view of (5) and Corollary 5.4, we can formulate the following quantitative formulation of (a slightly more general version of) Niederreiter’s problem.

Conjecture 5.5 (Splitting Subspace Conjecture). Let α ∈ 𝔽_{q^{mn}} be such that 𝔽_{q^{mn}} = 𝔽_{q}(α). Then

S(α, m, n; q) = \frac{q^{mn} − 1}{q^{m} − 1} q^{m(m−1)(n−1)}.

The above discussion makes it clear that Irreducible Fiber Conjecture (2.4) and the Splitting Subspace Conjecture (5.5) are equivalent to each other. In particular, Theorem 4.4 implies that the Splitting Subspace Conjecture holds in the affirmative when m = 2. It may also be noted that the Splitting Subspace Conjecture is trivially valid when either m = 1 or n = 1, and thus this equivalent formulation of a more general version of the Primitive Fiber Conjecture (2.3) subsumes [7, Thm. 7.1].

In the remainder of this section, we will use some elementary observations to formulate a refined version of the Splitting Subspace Conjecture that seems particularly amenable to tackle. Let us first make some definitions. For α ∈ 𝔽_{q^{mn}}, let 𝔖_{α} denote the set of all m-dimensional α-splitting subspaces of 𝔽_{q^{mn}}. By a pointed α-splitting subspace of dimension m we shall mean a pair (W, x) where W ∈ 𝔖_{α} and x ∈ W. The element x may be referred to as the base point of (W, x). Given any x ∈ 𝔽_{q^{mn}}, we let 𝔖_{α}^{x} := {W ∈ 𝔖_{α} : x ∈ W } .

Proposition 5.6. Let α ∈ 𝔽_{q^{mn}} be such that 𝔽_{q^{mn}} = 𝔽_{q}(α). Then:

(i) 𝔖_{α} is nonempty. Also, if W ∈ 𝔖_{α} and β ∈ 𝔽_{q^{mn}}^{∗}, then βW ∈ 𝔖_{α}.

(ii) 𝔖_{α}^{x} is nonempty for any x ∈ 𝔽_{q^{mn}}^{∗}.

(iii) |𝔖_{α}^{x}| = |𝔖_{α}^{y}| for any x, y ∈ 𝔽_{q^{mn}}^{∗}.

(iv) |𝔖_{α}| = |𝔖_{α}^{x}| (q^{mn} − 1)/(q^{m} − 1) for any x ∈ 𝔽_{q^{mn}}^{∗}.

Proof. (i) Let U be the 𝔽_{q}-linear span of {α^{in} : 0 ≤ i ≤ m − 1}. Then U ∈ 𝔖_{α}. Also, if W ∈ 𝔖_{α} and β ∈ 𝔽_{q^{mn}}^{∗}, then βW ∈ 𝔖_{α} since α^{j}β = βα^{j} for 0 ≤ j ≤ n − 1.

(ii) If U is as in (i), then xU ∈ 𝔖_{α}^{x} for any x ∈ 𝔽_{q^{mn}}^{∗}.

(iii) If x, y ∈ 𝔽_{q^{mn}}^{∗} and β = y/x, then W ↦ βW gives a bijection of 𝔖_{α}^{x} onto 𝔖_{α}^{y}. (iv) Counting the set {(W, x) : W ∈ 𝔖_{α} and x ∈ W with x ≠ 0} of all pointed

α-splitting subspaces with a nonzero base point in two different ways, we find |𝔖_{α}| (q^{m} − 1) = |𝔖_{α}^{x}| (q^{mn} − 1) for any x ∈ 𝔽_{q^{mn}}^{∗}. □

In view of parts (iii) and (iv) of Proposition 5.6, we can formulate the following refined version of the Splitting Subspace Conjecture.

Conjecture 5.7 (Pointed Splitting Subspace Conjecture). Let α ∈ 𝔽_{q^{mn}} be such that 𝔽_{q^{mn}} = 𝔽_{q}(α) and let x ∈ 𝔽_{q^{mn}}^{∗}. Then the number of m-dimensional pointed α-splitting subspaces of 𝔽_{q^{mn}} with base point x is equal to q^{m(m−1)(n−1)}.

It should be clear that the Pointed Splitting Subspace Conjecture implies all of the conjectures stated earlier, and also that the former is completely trivial when either m = 1 or n = 1. It may also be noted that part (i) of Proposition 5.6 implies Proposition 2.2. Finally, we remark that q^{m(m−1)} is the number of nilpotent m×m matrices over 𝔽_{q}, thanks to an old result of Fine and Herstein [4], and thus a particularly nice way to prove the Pointed Splitting Subspace Conjecture could be to set up a natural bijection between 𝔖_{α}^{x} and the set of (n − 1)-tuples (or if one prefers, pointed n-tuples) of nilpotent m × m matrices over 𝔽_{q}.

6. Asymptotic Formula

The Irreducible Fiber Conjecture (2.4) states that for any f ∈ ℐ(mn; q), the cardinality of Θ^{−1}(f) is q^{m(m−1)(n−1)} ∏_{i=1}^{m−1}(q^{m} − q^{i}). This expression is clearly a polynomial in q of degree mn(m − 1). Even though the conjecture remains open, in general, we will show that asymptotically the size of each irreducible fiber is like q^{mn(m−1)}. To this end, we use (5), and obtain suitable lower and upper bounds for N(α, m, n; q) by adapting an argument in the proof of [15, Thm. 5].

Lemma 6.1. Let α ∈ 𝔽_{q^{mn}} be such that 𝔽_{q^{mn}} = 𝔽_{q}(α). Then

\frac{(q − 2)q^{mn} + 1}{(q − 1)} q^{mn(m−1)} ≤ N(α, m, n; q) ≤ ∏_{i=0}^{m−1}(q^{mn} − q^{i}).

Proof. Let us write

𝔙 = {(v_{1}, …, v_{m}) ∈ 𝔽_{q^{mn}}^{m} : ℬ_{(v_{1},...,v_{m})}^{α} is an ordered 𝔽_{q}-basis of 𝔽_{q^{mn}}} .

Evidently, if (v_{1}, …, v_{m}) ∈ 𝔙, then v_{1}, …, v_{m} are linearly independent. Hence

N(α, m, n; q) = |𝔙| ≤ ∏_{i=0}^{m−1}(q^{mn} − q^{i}).

On the other hand, if (v_{1}, …, v_{m}) ∈ 𝔽_{q^{mn}}^{m} \ 𝔙, then there is a nonzero mn-tuple

c = (c_{11}, …, c_{1n}, …, c_{m1}, …, c_{mn}) ∈ 𝔽_{q}^{mn} such that ∑_{i=1}^{m} ∑_{j=1}^{n} c_{ij}v_{i}α^{j−1} = 0.

In other words, (v_{1}, …, v_{m}) is in the kernel of the linear map ϕ_{c} : 𝔽_{q^{mn}}^{m} → 𝔽_{q^{mn}} given by

ϕ_{c}(u_{1}, …, u_{m}) := γ_{1}u_{1} + ⋯ + γ_{m}u_{m}, where γ_{i} := ∑_{j=1}^{n} c_{ij}α^{j−1} for 1 ≤ i ≤ m.

It is clear that if c is replaced by a proportional tuple λc, where λ ∈ 𝔽_{q}^{∗}, then ker ϕ_{c} = ker ϕ_{λc}. Moreover, since c ≠ 0 and α is of degree ≥ n over 𝔽_{q}, not all γ_{1}, …, γ_{m} are zero, and therefore by the Rank-Nullity Theorem, ker ϕ_{c} is of dimension m − 1 over 𝔽_{q^{mn}}. It follows that

𝔽_{q^{mn}}^{m} \ 𝔙 ⊆ ⋃_{c∈ℙ(𝔽_{q}^{mn})} ker ϕ_{c} and |𝔽_{q^{mn}}^{m} \ 𝔙| ≤ \frac{q^{mn} − 1}{q − 1} q^{mn(m−1)}.

Consequently,

N(α, m, n; q) ≥ (q^{mn})^{m} − \frac{q^{mn} − 1}{q − 1} q^{mn(m−1)} = \frac{(q − 2)q^{mn} + 1}{(q − 1)} q^{mn(m−1)}.

This completes the proof. □

Theorem 6.2. For any f ∈ ℐ(mn; q), the fiber cardinality |Θ^{−1}(f)| is asymptotically equivalent to q^{mn(m−1)} as q → ∞.

Proof. Let f ∈ ℐ(mn; q) and let α ∈ 𝔽_{q^{mn}} be a root of f. From (5) and Lemma 6.1, we see that L(q) ≤ |Θ^{−1}(f)| ≤ U(q), where

L(q) := \frac{(q − 2)q^{mn} + 1}{(q − 1)(q^{mn} − 1)} q^{mn(m−1)} and U(q) := ∏_{i=1}^{m−1}(q^{mn} − q^{i}).

Further if we let L^{∗}(q) := ((q −2)q^{mn} +1)q^{mn(m−2)−1}, then L^{∗}(q) ≤ L(q) for q > 2. Since both L^{∗}(q) and U(q) are monic polynomials in q of degree mn(m − 1), we obtain the desired result. □

It is clear that if α ∈ 𝔽_{q^{mn}} is such that 𝔽_{q^{mn}} = 𝔽_{q}(α), then similar asymptotic formulae can be easily obtained for N(α, m, n; q) and S(α, m, n; q).

7. Application to Toeplitz matrices

Recall that a square matrix A = (a_{ij}) is said to be a Toeplitz matrix if a_{ij} = a_{rs} whenever i − j = r − s. Thus every n × n Toeplitz matrix looks like

(6) T_{c} = (c_{n+i−j}) = (\begin{matrix}c_{n} & … & c_{2} & c_{1} \\ c_{n+1} & ... & & c_{2} \\ ⋮ & ... & ... & ⋮ \\ c_{2n−1} & … & c_{n+1} & c_{n} \end{matrix}) where c = (c_{1}, c_{2}, …, c_{2n−1}) .

We denote by T_{n}(𝔽_{q}) the set of all Toeplitz matrices with entries in 𝔽_{q} and let TGL_{n}(𝔽_{q}) := T_{n}(𝔽_{q}) ∩ GL_{n}(𝔽_{q}). It is clear that |T_{n}(𝔽_{q})| = q^{2n−1}. Determining |TGL_{n}(𝔽_{q})| is far less obvious, but it is also given by a nice formula, namely,

(7)  |TGL_{n}(𝔽_{q})| = q^{2n−1} − q^{2n−2} = q^{2n−1} (1 − \frac{1}{q}) .

A fairly involved proof of (7) has recently been given by Kaltofen and Lobo [11] who also point out that Toeplitz matrices and the corresponding systems of equations are of much recent interest in symbolic computation. In fact, Toeplitz matrices are essentially equivalent to Hankel matrices and in this setting, (7) was proved much earlier by Daykin [3]. Here we will relate the determination of |TGL_{n}(𝔽_{q})| to the results of Section 4 and the existence of an irreducible trinomial (or binomial).

Proposition 7.1. Let q and n be such that there exists an irreducible polynomial in 𝔽_{q}[X] of the form X^{2n}−aX−b, where a, b ∈ 𝔽_{q}. Then |TGL_{n}(𝔽_{q})| = q^{2n−1}−q^{2n−2}.

Proof. Let f = X^{2n} − aX − b be an irreducible polynomial in 𝔽_{q}[X] and let α be a root of f in 𝔽_{q^{2n}}. Given any β ∈ 𝔽_{q^{2n}}, there are unique c_{0}, c_{1}, …, c_{2n−1} ∈ 𝔽_{q} such that β = c_{0} + c_{1}α + ⋯ + c_{2n−1}α^{2n−1}. Now α^{2n} = aα + b and therefore α^{2n−1+s} = aα^{s} + bα^{s−1} for 1 ≤ s ≤ n − 1. This implies that in the unique expression for βα^{j−1} as an 𝔽_{q}-linear combination of 1, α, …, α^{2n−1}, the coefficient of α^{n+i−1} is c_{n+i−j} for 1 ≤ i, j ≤ n. In other words, the matrix whose columns represent the coordinates of 1, α, … α^{n−1}, β, αβ, …, α^{n−1}β with respect to the ordered basis {1, α, …, α^{2n−1}} is a 2n × 2n block matrix of the form

(\begin{matrix}I_{n} & B \\ 0 & T_{c} \end{matrix}) ,

where B ∈ M_{n}(𝔽_{q}) and T_{c} is the Toeplitz matrix as in (6) above. It follows that 𝒮_{β} = {1, β, α, αβ, …, α^{n−1}, α^{n−1}β} is an ordered 𝔽_{q}-basis of 𝔽_{q^{2n}} if and only if the Toeplitz matrix T_{c} is nonsingular. Moreover, if c = (c_{1}, c_{2}, …, c_{2n−1}) ∈ 𝔽_{q}^{2n−1} is such that T_{c} is nonsingular, then there are exactly q values of β = c_{0} +c_{1}α+⋯+ c_{2n−1}α^{2n−1} (corresponding to different choices for c_{0}) such that 𝒮_{β} is an ordered 𝔽_{q}-basis of 𝔽_{q^{2n}}. But we have seen in the proof of Lemma 4.2 that the number of β ∈ 𝔽_{q^{2n}} for which 𝒮_{β} is an 𝔽_{q}-basis of 𝔽_{q^{2n}} is q^{2n−1}(q − 1). Consequently, |TGL_{n}(𝔽_{q})| = q^{2n−1}(q − 1)/q, as desired. □

The question as to whether for every prime power q and positive integer d, there is an irreducible trinomial in 𝔽_{q}[X] of degree d appears to be rather delicate. For example, Swan [17] showed that if d is a multiple of 8, then there are no irreducible trinomials over 𝔽_{2} of degree d. We refer to the papers of von zur Gathen [19] and Hanson, Panario and Thomson [8] for the current state of art on this topic. At any rate, a trinomial (that can possibly be a binomial) meeting the hypothesis of Proposition 7.1 does exist in many cases. To illustrate some of these, we will simply use the following classical result.

Proposition 7.2 ([13, Thm. 3.75]). Let d be a positive integer ≥ 2 and b ∈ 𝔽_{q} be such that b ≠ 0. Also let e be the order of b in 𝔽_{q}^{∗}. Then X^{d} − b is irreducible in 𝔽_{q}[X] if and only if each prime factor of d divides e but not (q −1)/e, and moreover q ≡ 1(mod 4) whenever d ≡ 0(mod 4).

Corollary 7.3. Assume that q is a power of an odd prime that is not a Fermat prime. Then there are infinitely many positive integers n such that X^{2n} − b is irreducible in 𝔽_{q}[X] for some b ∈ 𝔽_{q}.

Proof. The assumption on q implies that q − 1 = 2^{r}s for some integers r, s such that r ≥ 1, s > 1, and s is odd. Now let ℓ be a prime factor of s and n = ℓ^{i} be any power of ℓ, where i ≥ 1. Also let b be a primitive element of 𝔽_{q}^{∗}. Then X^{2n} − b satisfies the hypothesis of Proposition 7.2. □

We remark that some of the ideas in this section have eventually led to nice new proofs of (7) in the general case; for details, we refer to [6].

Acknowledgments

We are grateful to Sartaj Ul Hasan for his careful reading of a preliminary version of this paper and some helpful suggestions.

References

[1] A. T. Benjamin and C. D. Bennett, The probability of relatively prime polynomials, Math. Mag. 80 (2007), 196-202.

[2] S. Corteel, C. Savage, H. Wilf, and D. Zeilberger, A Pentagonal Number Sieve, J. Combin. Theory Ser. A 82 (1998), 186-192.

[3] D. E. Daykin, Distribution of bordered persymmetric matrices in a finite field, J. Reine Angew. Math. 203 (1960), 47–54.

[4] N. J. Fine and I. N. Herstein, The probability that a matrix be nilpotent, Illinois J. Math. 2 (1958), 499–504.

[5] Z. Gao and D. Panario, Degree distribution of the greatest common divisor of polynomials over 𝔽_{q}, Random Structures Algorithms 29 (2006), 26–37.

[6] M. García-Armas, S. R. Ghorpade, and S. Ram, Relatively prime polynomials and nonsingular Hankel matrices over finite fields, J. Combin. Theory Ser. A 118 (2011), 819–828.

[7] S. R. Ghorpade, S. U. Hasan, and M. Kumari, Primitive polynomials, Singer cycles, and word-oriented linear feedback shift registers, Des. Codes Cryptogr. 58 (2011), 123–134.

[8] B. Hanson, D. Panario and D. Thomson, Swan-like results for binomials and trinomials over 𝔽_{q}, q odd, Des. Codes Cryptogr. (2011), to appear, doi:10.1007/s10623-010-9476-7.

[9] X. Hou and G.L. Mullen, Number of irreducible polynomials and pairs of relatively prime polynomials in several variables over finite fields, Finite Fields Appl. 15 (2009), 304–331.

[10] N. Jacobson, Basic Algebra I, Second Ed., W. H. Freeman, New York, 1985.

[11] E. Kaltofen and A. Lobo, On rank properties of Toeplitz matrices over finite fields, pp. 241–249, Proc. 1996 Internat. Symp. Symbolic Algebraic Comput. (ISSAC ’96), ACM Press, New York, 1996.

[12] D. E. Knuth, The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, First Ed., Addison Wesley, Reading, MA, 1969.

[13] R. Lidl and H. Niederreiter, Finite Fields, Enc. of Math. and its Appl., Vol. 20, Cambridge University Press, Cambridge, 1983.

[14] H. Niederreiter, Factorization of polynomials and some linear-algebra problems over finite fields, Linear Algebra Appl. 192 (1993), 301–328.

[15] H. Niederreiter, The multiple-recursive matrix method for pseudorandom number generation , Finite Fields Appl. 1 (1995), 3–30.

[16] A. Reifegerate, On an involution concerning pairs of polynomials in 𝔽_{2}, J. Combin. Theory Ser. A 90 (2000), 216-220.

[17] R. G. Swan, Factorization of polynomials over finite fields, Pacific J. Math. 12 (1962), 1099–1106.

[18] B. Tsaban and U. Vishne, Efficient linear feedback shift registers with maximal period, Finite Fields Appl. 8 (2002), 256–267.

[19] J. von zur Gathen, Irreducible trinomials over finite fields, Math. Comp. 72 (2003), 1987– 2000.

[20] G. Zeng, W. Han and K. He, Word-Oriented Feedback Shift Register: σ-LFSR, http://eprint.iacr.org/2007/114 (Cryptology ePrint Archive: Report 2007/114).

Department of Mathematics, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India.

E-mail address: srg@math.iitb.ac.in

Department of Mathematics, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India.

E-mail address: samrithram@gmail.com