PRIMITIVE POLYNOMIALS, SINGER CYCLES, AND WORD-ORIENTED LINEAR FEEDBACK SHIFT REGISTERS

SUDHIR R. GHORPADE, SARTAJ UL HASAN, AND MEENA KUMARI

Abstract. Using the structure of Singer cycles in general linear groups, we prove that a conjecture of Zeng, Han and He (2007) holds in the affirmative in a special case, and outline a plausible approach to prove it in the general case. This conjecture is about the number of primitive σ-LFSRs of a given order over a finite field, and it generalizes a known formula for the number of primitive LFSRs, which, in turn, is the number of primitive polynomials of a given degree over a finite field. Moreover, this conjecture is intimately related to an open question of Niederreiter (1995) on the enumeration of splitting subspaces of a given dimension.

1. Introduction

Denote, as usual, by 𝔽_{q} the finite field with q elements and by 𝔽_{q}[X] the ring of polynomials in one variable X with coefficients in 𝔽_{q}. It is elementary and well known that if f(X) ∈ 𝔽_{q}[X] is of degree n and f(0) ≠ 0, then f(X) divides X^{e} − 1 for some positive integer e ≤ q^{n} − 1. The least such e is called the order of f(X) and is denoted by ord f(X). We say that a monic polynomial f(X) ∈ 𝔽_{q}[X] of degree n is primitive if f(0) ≠ 0 and ord f(X) = q^{n} − 1. The study of primitive polynomials goes back to Gauss and is an interesting and important part of the theory of finite fields. A basic reference is [11, Ch. 3] and some of the relevant facts about primitive polynomials are stated in Section 2 below.

Elements of the maximum possible order in the finite group GL_{n}(𝔽_{q}) of n × n nonsingular matrices with entries in 𝔽_{q} are called Singer cycles. These are closely related to primitive polynomials since this maximum possible order is, in fact, q^{n}−1, and moreover, characteristic polynomials of Singer cycles are primitive. We refer to [9] and [18] for some basic aspects of the study of Singer cycles and provide, for the convenience of the reader, a brief outline of basic results together with consequences that are useful for this paper in Section 3.

Linear feedback shift registers (LFSRs) are devices frequently used in cryptography and coding theory (cf. [8, 11]). In effect, a LFSR can be viewed as an infinite sequence of elements of 𝔽_{q} generated by finitely many initial values and a homogeneous linear recurrence relation. In the binary case (q = 2), these sequences are used for efficient encryption of data in designing stream ciphers. In general, it can be shown that these sequences are (ultimately) periodic and the maximum possible period of an n^{th} order linear recurring sequence is q^{n} −1. (See Section 2 for details.) In order to have good cryptographic properties [8], one is mainly interested in the sequences that have the maximum period. The LFSRs corresponding to sequences with maximum period are known as primitive LFSRs. Using the connection with primitive polynomials or otherwise, it is readily seen that the number of primitive LFSRs of order n over 𝔽_{q} is given by

Date: March 28, 2010.

Key words and phrases. Primitive polynomial, Linear Feedback Shift Register (LFSR), Singer cycle, Singer subgroup, splitting subspaces.

(1)  \frac{ϕ(q^{n} − 1)}{n}

where ϕ is the Euler totient function.

In this paper, we consider a recent generalization due to Zeng, Han and He [19] of a (traditional) LFSR to a word-oriented linear feedback shift register, called σ-LFSR. It is argued in [19] that the σ-LFSRs meet the dual demands of high efficiency and good cryptographic properties, and that these can be viewed as a solution to a problem of Preneel [16] on designing fast and secure LFSRs with the help of the word operations of modern processors and the techniques of parallelism. Notions of primitivity readily extend from LFSRs to σ-LFSRs although the connection with primitive polynomials and matrices is a little more intricate. Unlike (1), a simple formula for the number of primitive σ-LFSRs of order n over 𝔽_{q^{m}} is not known, but an intriguing explicit formula in the binary case has been conjectured. The main aim of this paper is to elucidate, extend and understand this conjectural formula of Zeng, Han and He [19]. In general, the conjecture is that the number of primitive σ-LFSRs of order n over 𝔽_{q^{m}} is given by

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

After a preliminary version of this paper was prepared, we found that the seemingly new notion of a σ-LFSR can, in fact, be traced back to the work of Niederreiter (1993-1996) mainly in the context of pseudorandom number generation. Indeed, in a series of papers [12, 13, 14, 15], Niederreiter has introduced the so called multiple recursive matrix method and the notion of recursive vector sequences. The latter are essentially the same as sequences generated by a σ-LFSR, modulo a natural isomorphism between the field 𝔽_{q^{m}} with q^{m} elements and the vector space 𝔽_{q}^{m} of dimension m over The question of counting the number of primitive σ-LFSRs of a given order n over 𝔽_{q^{m}} is considered in [13, p. 11] under a different guise (cf. Remark 6.3), and is termed as open problem. However, no explicit formula for this number is given, even conjecturally, in the work of Niederreiter, and therefore, the credit for formulating (2) should go to Zeng, Han and He [19] at least in the binary case. Moreover, in a personal communication, Professor Niederreiter has informed us that the problem of counting the number of primitive σ-LFSRs of a given order n over 𝔽_{q^{m}} is still open to the best of his knowledge.

Our main results are as follows. We work throughout in the general q-ary case and first give an alternative formulation of the conjecture in terms of the enumeration of certain Singer cycles (Theorem 5.2). Next, we give a plausible approach to derive (2) by noting that it suffices to analyze the image and the fibers of a natural map from a certain class of mn × mn matrices to the set of primitive polynomials of degree mn. We accomplish the first task by showing that this map is surjective (Theorem 6.1). As for the second, we give a conjectural description of the fibers (Conjecture 6.2). Moreoever, we use certain properties of Singer cycles to prove that (2) as well as the more refined Fiber Conjecture hold when n = 1 and m is arbitrary (Theorem 7.1). It may be noted that in the other initial case m = 1, (2) is an immediate consequence of (1).

PRIMITIVE POLYNOMIALS, SINGER CYCLES AND σ-LFSRs 3

This paper is written in a fairly self-contained manner with the hope that it would stimulate some interest even among those that are not interested in cryptographic applications per se, in proving formula (2) and taking up allied problems.

2. Primitive Polynomials and Primitive LFSRs

By a primitive element in a finite cyclic group G we mean a generator of G. Primitive polynomials in 𝔽_{q}[X], as defined in the Introduction, are related to primitive elements by the following characterization [11, Thm. 3.16], which is sometimes used to give an alternative definition of primitive polynomials.

Proposition 2.1. Let f(X) ∈ 𝔽_{q}[X] be of degree n ≥ 1. Then f(X) is a primitive polynomial if and only if f(X) is the minimal polynomial of a primitive element of the cyclic group 𝔽_{q^{n}}^{∗} of nonzero elements of the finite field 𝔽_{q^{n}}.

Using the above theorem together with the fact that the number of primitive elements in a cyclic group of order N is ϕ(N), we readily see that the number of primitive polynomials in 𝔽_{q}[X] of degree n is given by (1).

We shall now proceed to review the basic definitions and some of the basic results concerning linear feedback shift registers.

Definition 2.2. Let n be a positive integer and let c_{0}, c_{1}, …, c_{n−1} ∈ 𝔽_{q}. Given any n-tuple (s_{0}, s_{1}, …, s_{n−1}) ∈ 𝔽_{q}^{n}, let s^{∞} = (s_{0}, s_{1}, …) denote the infinite sequence of elements of 𝔽_{q} determined by the following linear recurrence relation:

s_{i+n} = s_{i}c_{0} + s_{i+1}c_{1} + ⋯ + s_{i+n−1}c_{n−1} for i = 0, 1, … (3)

The system (3) is called a linear feedback shift register (LFSR) of order n over 𝔽_{q}, while the sequence s^{∞} is referred to as the sequence generated by the LFSR (3). The n-tuple (s_{0}, s_{1}, ⋯, s_{n−1}) is called the initial state of the LFSR (3) and the polynomial X^{n} − c_{n−1}X^{n−1} − ⋯ − c_{1}X − c_{0} is called the characteristic polynomial of the LFSR (3). The sequence s^{∞} is said to be ultimately periodic if there are integers r, n_{0} with r ≥ 1 and n_{0} ≥ 0 such that s_{j+r} = s_{j} for all j ≥ n_{0}. The least positive integer r with this property is called the period of s^{∞} and the corresponding least nonnegative integer n_{0} is called the preperiod of s^{∞}. The sequence s^{∞} is said to be periodic if its preperiod is 0.

Some basic facts about LFSRs are summarized in the two propositions below. Proofs can be found, for example, in [11, Ch. 8].

Proposition 2.3. For the sequence s^{∞} generated by the LFSR (3) of order n over 𝔽_{q}, we have the following.

(i) s^{∞} is ultimately periodic and its period is ≤ q^{n} − 1.

(ii) If c_{0} ≠ 0, then s^{∞} is periodic. Conversely, if s^{∞} is periodic whenever the initial state is of the form (b, 0, …, 0), where b ∈ 𝔽_{q} with b ≠ 0, then c_{0} ≠ 0.

We say that a LFSR of order n over 𝔽_{q} is primitive if for any choice of a nonzero initial state, the sequence generated by that LFSR is periodic of period q^{n} − 1. Primitive LFSRs admit the following characterization.

Proposition 2.4. A LFSR of order n over 𝔽_{q} is primitive if and only if its characteristic polynomial is a primitive polynomial of degree n in 𝔽_{q}[X].

As an immediate consequence of Propositions 2.1 and 2.4, we see that the number of primitive LFSRs of order n over 𝔽_{q} is given by (1).

3. Singer Cycles and Singer Subgroups

The following result about orders of elements in a general linear group over finite field is well known. We include a more elaborate version and a quick proof since it seems a bit difficult to locate in or extract from the literature. An alternative (and somewhat longer) proof of the inequality below can be found, for example, in [4, p. 742]. In what follows, for an element A of a finite group G, we denote by o(A) the order of A in G.

Proposition 3.1. Let A ∈ GL_{n}(𝔽_{q}) and let p(X) ∈ 𝔽_{q}[X] be the minimal polynomial of A and χ(X) ∈ 𝔽_{q}[X] be the characteristic polynomial of A. Then p(0) ≠ 0 and o(A) = ord p(X). In particular, o(A) ≤ q^{n} − 1, and moreover, if the equality holds, then p(X) = χ(X). Also, we have:

(4) o(A) = q^{n} − 1 ⟺ p(X) is primitive of degree n ⟺ χ(X) is primitive.

Proof. Since A is nonsingular, 0 is not an eigenvalue of A and hence p(0) ≠ 0. Now, if I denotes the n × n identity matrix over 𝔽_{q}, then for any positive integer e, we clearly have

A^{e} = I ⟺ p(X) divides X^{e} − 1.

Consequently, o(A) = ord p(X). Further, deg χ(X) = n and in view of the Cayley-Hamilton Theorem, p(X) divides χ(X). In particular, deg p(X) ≤ n and hence o(A) = ord p(X) ≤ q^{n} − 1. Moreover, if ord p(X) = q^{n} − 1, then deg p(X) = n = deg χ(X), and hence p(X) = χ(X). On the other hand, if χ(X) is primitive, then it is irreducible and so χ(X) = p(X). This yields the equivalence in (4). □

A cyclic subgroup of GL_{n}(𝔽_{q}) of order e = q^{n} − 1 is called a Singer subgroup of GL_{n}(𝔽_{q}) and an element of GL_{n}(𝔽_{q}) of order e is called a Singer cycle in GL_{n}(𝔽_{q}). This terminology stems from [18] and seems appropriate since GL_{n}(𝔽_{q}) can be viewed as a subgroup of the symmetric group 𝔖_{e} via the natural transitive action of GL_{n}(𝔽_{q}) on the set 𝔽_{q}^{n} \ {0}, and elements of GL_{n}(𝔽_{q}) of order e evidently correspond to e-cycles in 𝔖_{e}. We now recall two results from [9, II.§7] (see also [2]) about Singer subgroups that will be useful to us later.

Proposition 3.2. Any two Singer subgroups in GL_{n}(𝔽_{q}) are conjugate.

Proposition 3.3. Let σ be the Frobenius automorphism of order n of the field 𝔽_{q^{n}}. Identify 𝔽_{q^{n}} with the vector space 𝔽_{q}^{n} and regard σ as an element of GL_{n}(𝔽_{q}). Also, let H be a Singer subgroup of GL_{n}(𝔽_{q}) and N denote its normalizer in GL_{n}(𝔽_{q}). Then N is isomorphic to the semi-direct product H ⋊ ⟨σ⟩ of H and the cyclic subgroup of GL_{n}(𝔽_{q}) generated by σ.

It may be noted that Proposition 3.1 relates Singer cycles to primitive polynomials. To work in the other direction, we can use companion matrices. Recall that if f(X) = X^{n} − c_{n−1}X^{n−1} − ⋯ − c_{1}X − c_{0} is a monic polynomial of degree n ≥ 1 in 𝔽_{q}[X], then the companion matrix C_{f} of f(X) is the n × n matrix

C_{f} = (\begin{matrix}0 & 0 & 0 & . & . & 0 & 0 & c_{0} \\ 1 & 0 & 0 & . & . & 0 & 0 & c_{1} \\ . & . & . & . & . & . & . & . \\ . & . & . & . & . & . & . & . \\ 0 & 0 & 0 & . & . & 1 & 0 & c_{n−2} \\ 0 & 0 & 0 & . & . & 0 & 1 & c_{n−1} \end{matrix}) .

It is clear that det C_{f} = (−1)^{n+1}c_{0}. In particular, C_{f} ∈ GL_{n}(𝔽_{q}) if and only if f(0) ≠ 0. Also, we know from linear algebra that f(X) is the minimal polynomial as well as the characteristic polynomial of C_{f}. Thus, in view of Proposition 3.1, we see that if f(0) ≠ 0, then ord f(X) = o(C_{f}) and that f(X) is a primitive polynomial if and only if C_{f} is a Singer cycle in GL_{n}(𝔽_{q}). In turn, primitive LFSRs of order n over 𝔽_{q} are related to Singer cycles in GL_{n}(𝔽_{q}). To see the latter in a more direct way, it may be useful to observe that the companion matrix, say A, of the characteristic polynomial of the LFSR (3) is its state transition matrix. Indeed, the k^{th} state S_{k} := (s_{k}, s_{k+1}, …, s_{k+n−1}) of the LFSR (3) is obtained from the initial state S_{0} := (s_{0}, s_{1}, …, s_{n−1}) by S_{k} = S_{0}A^{k}, for any k ≥ 0.

4. Word-Oriented Feedback Shift Register: σ-LFSR

Given any ring R and any positive integer d, let M_{d}(R) denote the set of all d × d matrices with entries in R. Fix throughout this and the subsequent sections, positive integers m and n, and a vector space basis {α_{0}, …, α_{m−1}} of 𝔽_{q^{m}} over 𝔽_{q}. Given any s ∈ 𝔽_{q^{m}}, there are unique a_{0}, …, a_{m−1} ∈ 𝔽_{q} such that s = a_{0}α_{0} + ⋯ + a_{m−1}α_{m−1}, and we shall denote the corresponding co-ordinate vector (a_{0}, …, a_{m−1}) of s by s. Evidently, the association s ⟼ s gives a vector space isomorphism of 𝔽_{q^{m}} onto 𝔽_{q}^{m}. Elements of 𝔽_{q}^{m} may be thought of as row vectors and so sC is a well-defined element of 𝔽_{q}^{m} for any s ∈ 𝔽_{q}^{m} and C ∈ M_{m}(𝔽_{q}). Following [19], and in analogy with LFSRs, we define a (q-ary) σ-LFSR as follows.

Definition 4.1. Let C_{0}, C_{1}, …, C_{n−1} ∈ M_{m}(𝔽_{q}). Given any n-tuple (s_{0}, …, s_{n−1}) of elements of 𝔽_{q^{m}}, let s^{∞} = (s_{0}, s_{1}, …) denote the infinite sequence of elements of 𝔽_{q^{m}} determined by the following linear recurrence relation:

s_{i+n} = s_{i}C_{0} + s_{i+1}C_{1} + ⋯ + s_{i+n−1}C_{n−1} for i = 0, 1, … (5)

The system (5) is called a sigma linear feedback shift register (σ-LFSR) of order n over 𝔽_{q^{m}}, while the sequence s^{∞} is referred to as the sequence generated by the σ-LFSR (5). The n-tuple (s_{0}, s_{1}, ⋯, s_{n−1}) is called initial state of the σ-LFSR (5) and the polynomial X^{n} − C_{n−1}X^{n−1} − ⋯ − C_{1}X − C_{0} with matrix coefficients is called the σ-polynomial of the σ-LFSR (5). The sequence s^{∞} is said to be ultimately periodic if there are integers r, n_{0} with r ≥ 1 and n_{0} ≥ 0 such that s_{j+r} = s_{j} for all j ≥ n_{0}. The least positive integer r with this property is called the period of s^{∞} and the corresponding least nonnegative integer n_{0} is called the preperiod of s^{∞}. The sequence s^{∞} is said to be periodic if its preperiod is 0.

The following analogue of Proposition 2.3 is easily proved in a similar manner as in the classical case of LFSRs.

Proposition 4.2. For the sequence s^{∞} generated by the σ-LFSR (5) of order n over 𝔽_{q^{m}}, we have the following.

(i) s^{∞} is ultimately periodic, and its period is ≤ q^{mn} − 1.

(ii) If C_{0} is nonsingular, then s^{∞} is periodic. Conversely, if s^{∞} is periodic whenever the initial state is of the form (b, 0, …, 0), where b ∈ 𝔽_{q^{m}} with b ≠ 0, then C_{0} is nonsingular.

We say that a σ-LFSR of order n over 𝔽_{q^{m}} is primitive if for any choice of nonzero initial state, the sequence generated by that σ-LFSR is periodic of period q^{mn} − 1. In view of Proposition 4.2, if X^{n} −C_{n−1}X^{n−1} −⋯−C_{1}X −C_{0} ∈ M_{m}(𝔽_{q})[X] is the σ-polynomial of a primitive σ-LFSR, then the matrix C_{0} is necessarily nonsingular.

Since the σ-polynomial of a σ-LFSR has coefficients in the noncommutative ring of matrices, notions such as irreducibility or primitivity are not readily applicable to it, and an analogue of Proposition 2.4 is not obvious. However, as stated in [19, Thm. 2] and proved in [20, Thm. 3] (see also [12, Thm. 4]), we have the following characterization of primitive σ-LFSRs.

Proposition 4.3. Let f(X) = X^{n} − C_{n−1}X^{n−1} − ⋯ − C_{1}X − C_{0} ∈ M_{m}(𝔽_{q})[X] be the σ-polynomial of a σ-LFSR of order n over 𝔽_{q^{m}}, where C_{0} ∈ GL_{m}(𝔽_{q}) and C_{ℓ} ∈ M_{m}(𝔽_{q}) for ℓ = 1, …, n − 1. For 1 ≤ i, j ≤ m, let f^{ij}(X) ∈ 𝔽_{q}[X] be the polynomial of degree n given by

f^{ij}(X) = δ^{ij}X^{n} − ∑_{ℓ=0}^{n−1} c_{ℓ}^{ij}X^{ℓ},

where δ^{ij} is the Kronecker delta and c_{ℓ}^{ij} is the (i, j)^{th} entry of the m × m matrix C_{ℓ} for ℓ = 0, 1, …, n − 1. Finally, let Δ(X) denote the determinant of the m × m matrix (f^{ij}(X)) with polynomial entries. Then the σ-LFSR is primitive if and only if the Δ(X) is a primitive polynomial over 𝔽_{q} of degree mn.

The q-ary version of Conjecture 1 of [19] is the following.

Conjecture 4.4. The number of primitive σ-LFSR of order n over 𝔽_{q^{m}} is given by the formula (2) stated in the Introduction.

We note that since |GL_{m}(𝔽_{q})| = (q^{m} − 1)(q^{m} − q) ⋯ (q^{m} − q^{m−1}), the formula (2) can be equivalently written as

(6)  Υ(m, n; q) = \frac{|GL_{m}(𝔽_{q})|}{q^{m} − 1}.\frac{ϕ(q^{mn} − 1)}{mn}.q^{m(m−1)(n−1)}

In fact, it appears in [19] in this form in the case q = 2. As noted in [19], the number Υ(m, n; q) is significantly larger than the number of traditional LFSRs of order n over 𝔽_{q^{m}}, namely, ϕ(q^{mn} − 1)/n, and this is partly a reason why σ-LFSRs are deemed superior than the LFSRs.

Remark 4.5. The significance of the power of q in Υ(m, n; q) is not completely clear. We merely mention that q^{m(m−1)} is the number of nilpotent m × m matrices over 𝔽_{q}, thanks to an old result of Fine and Herstein [5] (see [3] or [6] for a more accessible proof). Consequently, |GL_{m}(𝔽_{q})|q^{m(m−1)(n−1)} is the number of n-tuples (C_{0}, C_{1}, …, C_{n−1}) of m × m matrices over 𝔽_{q} where C_{0} is nonsingular and C_{1}, …, C_{n−1} are nilpotent. However, the relation of such tuples with primitive σ-LFSRs is not at all clear.

5. Block Companion Matrices

By a (m, n)-block companion matrix over 𝔽_{q} we mean T ∈ M_{mn}(𝔽_{q}) of the form

(7)  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}). The set of all (m, n)-block companion matrices over 𝔽_{q} shall be denoted by BCM(m, n; q). Using a Laplace expansion or a suitable sequence of elementary column operations, we see that if T ∈ BCM(m, n; q) is given by (7), then det T = ± det C_{0}. Consequently,

(8)  T ∈ GL_{mn}(𝔽_{q}) ⟺ C_{0} ∈ GL_{m}(𝔽_{q}).

It may be noted that the block companion matrix (7) is the state transition matrix for the σ-LFSR (5).

The following elementary observation reduces the calculation of a mn × mn determinant to an m × m determinant. It is implicit in [20] in the binary case, while a proof in the general case can be gleamed from [12, Thm. 4 and its proof].

Lemma 5.1. Let T ∈ BCM(m, n; q) be given by (7) and let F (X) ∈ M_{m} (𝔽_{q}[X]) be defined by F (X) := I_{m}X^{n} − C_{n−1}X^{n−1} − ⋯ − C_{1}X − C_{0}. Then the characteristic polynomial of T is equal to det F (X).

As a corollary, we can obtain a more amenable form of Conjecture 4.4.

Theorem 5.2. Conjecture 4.4 is equivalent to showing that

(9)  |{T ∈ BCM(m, n; q) ∩ GL_{mn}(𝔽_{q}) : o(T) = q^{mn} − 1}| = Υ(m, n; q),

where Υ(m, n; q) is given by the formula (2) or the equivalent formula (6).

Proof. If T ∈ BCM(m, n; q) ∩ GL_{mn}(𝔽_{q}) is given by (7) and if F (X) is as in Lemma 5.1, then det F (X) is precisely the polynomial Δ(X) in Proposition 4.3. Now, the desired result follows readily from Propositions 3.1 and 4.3 together with Lemma 5.1. □

6. The Characteristic Map

Let

BCMS(m, n; q) := {T ∈ BCM(m, n; q) ∩ GL_{mn}(𝔽_{q}) : o(T) = q^{mn} − 1}

be the set of Singer cycles among (m, n)-block companion matrices, and

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

be the set of all primitive polynomials of degree mn over 𝔽_{q}. In view of Proposition 3.1, the restriction to BCMS(m, n; q) of the characteristic map

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

gives a map from BCMS(m, n; q) to 𝒫(mn; q), which we shall denote by Ψ. Clearly,

BCMS(m, n; q) = ∐_{f(X)∈ im(Ψ)} Ψ^{−1} (f(X)) ,

where, as usual, ∐ denotes disjoint union, im(Ψ) denotes the image of Ψ, and Ψ^{−1} (f(X)) := {T ∈ BCMS(m, n; q) : Ψ(T) = f(X)} denotes the fiber of f(X) for any f(X) ∈ 𝒫(mn; q). Thus, to prove (9), it suffices to determine im(Ψ) and the cardinality of each of the fibers. The former is answered by the following.

Theorem 6.1. The map Ψ : BCMS(m, n; q) → 𝒫(mn; q) is surjective.

Proof. Let f(X) ∈ 𝒫(mn; q). By Proposition 2.1, there is a primitive element γ of 𝔽_{q^{mn}}^{∗} such that f(γ) = 0. Since f(X) ∈ 𝔽_{q}[X], the Frobenius automorphism x ⟼ x^{q} of 𝔽_{q^{mn}} permutes the roots of f(X), and thus γ, γ^{q}, γ^{q^{2}}, …, γ^{q^{mn−1}} are precisely the mn distinct roots of f(X). Hence

f(X) = ∏_{j=0}^{m−1} f_{j}(X) where f_{j}(X) := ∏_{i=0}^{n−1} (X − γ^{q^{im+j}}) for j = 0, …, m − 1.

Note that the map given by x ⟼ x^{q^{m}} is a generator of the Galois group of 𝔽_{q^{mn}} over 𝔽_{q^{m}}, and for each j = 0, …, m − 1, it permutes the roots of f_{j}(X) among themselves, and so f_{j}(X) ∈ 𝔽_{q^{m}}[X]. Moreover, since q^{j} and q^{mn} − 1 are relatively prime, we see that each f_{j}(X) is the minimal polynomial over 𝔽_{q^{m}} of a primitive element of 𝔽_{q^{mn}}^{∗}, namely, γ^{q^{j}}, and thus f_{j}(X) is a primitive polynomial in 𝔽_{q^{m}}[X]; in particular, f_{j}(X) is irreducible in 𝔽_{q^{m}}[X] and f_{j}(0) ≠ 0 for j = 0, …, m − 1. Write

f_{0}(X) = X^{n} − β_{n−1}X^{n−1} − ⋯ − β_{1}X − β_{0} where β_{0}, β_{1}, …, β_{n−1} ∈ 𝔽_{q^{m}}.

Let B = C_{f_{0}} be the companion matrix of f_{0}(X). By the Cayley-Hamilton Theorem, f_{0}(B) = 0 and hence f(B) = 0. Now, choose a Singer cycle A ∈ GL_{m}(𝔽_{q}) and let g(X) ∈ 𝔽_{q}[X] be the minimal polynomial of A. By Proposition 3.1, we have g(X) ∈ 𝒫(m; q). Moreover, p(X) ⟼ p(A) defines a 𝔽_{q}-algebra homomorphism of 𝔽_{q}[X] into M_{m}(𝔽_{q}) and its image is the group algebra 𝔽_{q}[A] of the cyclic subgroup of GL_{m}(𝔽_{q}) generated by A while its kernel is the ideal of 𝔽_{q}[X] generated by g(X). Since g(X) is irreducible of degree m, the residue class ring 𝔽_{q}[X]/ ⟨g(X)⟩ is 𝔽_{q}-isomorphic to 𝔽_{q^{m}}. Thus we obtain a 𝔽_{q}-algebra isomorphism θ : 𝔽_{q^{m}} → 𝔽_{q}[A], which induces a 𝔽_{q}-algebra homomorphism

θ̂: M_{n} (𝔽_{q^{m}}) → M_{n} (M_{m}(𝔽_{q})) ≃ M_{mn}(𝔽_{q}) given by θ̂((β_{ij})) = (θ (β_{ij}))

of the corresponding rings of matrices. It may be noted that since o(A) = q^{m}−1, we have 𝔽_{q}[A] = {0, A, A^{2}, …, A^{q^{m}−1}}, where 0 denotes the zero matrix in M_{m}(𝔽_{q}). Now let C_{i} := θ(β_{i}) for i = 0, …, n − 1, and let T ∈ BCM(m, n; q) be the matrix given by (7) corresponding to these m × m matrices C_{0}, C_{1}, …, C_{m−1}. Note that since β_{0} = f_{0}(0) ≠ 0 and θ is an isomorphism, C_{0} is nonsingular and hence by (8), T ∈ BCM(m, n; q) ∩ GL_{mn}(𝔽_{q}). Also note that T = θ̂(B). Now, since f(B) = 0 and θ̂ is a 𝔽_{q}-algebra homomorphism, it follows that f(T) = 0. Moreover, since f(X) ∈ 𝔽_{q}[X] is primitive of degree mn, it must be the minimal polynomial of T and further, by Proposition 3.1, we see that o(T) = q^{mn} − 1 and f(X) is the characteristic polynomial of T. Thus, T ∈ BCMS(m, n; q) and Φ(T) = f(X). This proves that Ψ is surjective. □

As for the fibers of Ψ, we propose the following.

Conjecture 6.2 (Fiber Conjecture). For any f(X) ∈ 𝒫(mn; q), the cardinality of the fiber Ψ^{−1} (f(X)) := {T ∈ BCMS(m, n; q) : Ψ(T) = f(X)} is independent of the choice of f(X) and, in fact, given by the following formula:

|Ψ^{−1} (f(X))| = q^{m(m−1)(n−1)} ∏_{i=1}^{m−1}(q^{m} − q^{i}).

It is clear that Conjecture 6.2 together with Theorem 6.1 implies Conjecture 4.4. We remark that the fibers of the ambient map Φ have been studied in the literature (cf. [6, 17]). The Fiber Conjecture facilitates a connection between Conjecture 4.4 and a question of Niederreiter (which is still open) as indicated below.

Remark 6.3. Let α be a primitive element of 𝔽_{q^{mn}}^{∗}. A subspace W of 𝔽_{q^{mn}} of dimension m is said to be α-splitting if 𝔽_{q^{mn}} = W ⊕αW ⊕⋯⊕α^{n−1}W. Niederreiter [13, p. 11] asks for the total number of α-splitting subspaces of dimension m. In view of Proposition 2.1, fixing a primitive element of 𝔽_{q^{mn}}^{∗} is essentially the same as fixing a primitive polynomial in 𝔽_{q}[X] of degree mn. Now let L_{α} : 𝔽_{q^{mn}} → 𝔽_{q^{mn}} be the linear transformation defined by L_{α}(x) := αx. Note that the characteristic polynomial of L_{α} is precisely the minimal polynomial of α. Moreover, if a subspace W of dimension m is α-splitting and {u_{1}, …, u_{m}} is an ordered basis of W, then B_{(u_{1},...,u_{m})}^{α} = {u_{1}, …, u_{m}, αu_{1}, …, αu_{m}, …, α^{n−1}u_{1}, …, α^{n−1}u_{m}} is a 𝔽_{q}-basis of 𝔽_{q^{mn}} and with respect to this ordered basis, the matrix of L_{α} is a (m, n)-block companion matrix. Moreover, thanks to Proposition 3.1, this block companion matrix is a Singer cycle. Conversely, a Singer cycle in GL_{mn}(𝔽_{q}) of the form (7) must be the matrix of L_{α} with respect to a basis of the form B_{(u_{1},...,u_{m})}^{α} and then {u_{1}, …, u_{m}} clearly spans a α-splitting subspace. In this way, the enumeration of α-splitting subspaces of dimension m is essentially equivalent to the determination of cardinalities of the fibers of Ψ. We refer to the forthcoming paper [7] for more on this equivalence and some further progress on Conjectures 4.4 and 6.2.

7. The Case n = 1

As noted in the introduction, when m = 1, (2) reduces to (1) and hence Conjecture 4.4 readily follows from Proposition 2.1. Also, when m = 1, the map Ψ is clearly bijective and hence Conjecture 6.2 holds trivially. We will show below that when n = 1, both the conjectures follow from the structure of Singer cycles.

Theorem 7.1. If n = 1, then Conjecture 4.4 as well as Conjecture 6.2 hold in the affirmative.

Proof. Suppose n = 1. Then BCMS(m, n; q) is simply the set of all Singer cycles in GL_{m}(𝔽_{q}). By Proposition 3.2, GL_{m}(𝔽_{q}) acts transitively on the set of all Singer subgroups by conjugation, and hence the number of Singer subgroups of GL_{m}(𝔽_{q}) is given by |GL_{m}(𝔽_{q})| /|N|, where N denotes the normalizer of a Singer subgroup of GL_{m}(𝔽_{q}). Moreover, by Proposition 3.3, we see that |N| = m(q^{m} − 1). Finally, since any Singer subgroup of GL_{m}(𝔽_{q}) contains ϕ(q^{m} −1) generators, i.e., ϕ(q^{m} −1) Singer cycles, it follows that

|BCMS(m, 1; q)| = \frac{|GL_{m}(𝔽_{q})|}{m(q^{m} − 1)}ϕ(q^{m} − 1) = Υ(m, 1; q).

Thus, in view of Theorem 5.2, Conjecture 4.4 is established when n = 1. To show more generally, that Conjecture 6.2 holds in the affirmative when n = 1, let f(X) ∈ 𝒫(m; q) and T ∈ BCMS(m, 1; q) be such that Ψ(T) = f(X). By Proposition 3.1, the minimal polynomial as well as the characteristic polynomial of T is f(X). In particular, T and the companion matrix C_{f} of f(X) have the same set of invariant factors, and therefore, they are similar (cf. [1, p. VII.32]). It follows that Ψ^{−1}(f(X)) = {P^{−1}C_{f}P : P ∈ GL_{m}(𝔽_{q})}. Consequently,

|Ψ^{−1}(f(X))| = \frac{|GL_{m}(𝔽_{q})|}{|Z(C_{f})|} where Z(C_{f}) := \{P ∈ GL_{m}(𝔽_{q}) : C_{f}P = P C_{f}\} .

Further, the linear transformation of 𝔽_{q^{m}} ≃ 𝔽_{q}^{m} corresponding to C_{f} is cyclic and hence by a theorem of Frobenius [10, Thm. 3.16 and its Corollary], the centralizer Z(C_{f}) of C_{f} consists only of polynomials in C_{f}. Now, the 𝔽_{q}-algebra of polynomials in C_{f} is readily seen to be isomorphic to 𝔽_{q}[X]/ ⟨f(X)⟩, and so its cardinality is q^{m}. Consequently, Z(C_{f}) = {C_{f}^{j} : 0 ≤ j < q^{m}} and |Z(C_{f})| = q^{m} − 1. Thus,

|Ψ^{−1}(f(X))| = \frac{|GL_{m}(𝔽_{q})|}{q^{m} − 1} = ∏_{i=1}^{m−1}(q^{m} − q^{i}),

as desired. □

Remark 7.2. An alternative proof of Conjecture 6.2 in the case n = 1 can be obtained using the Reiner-Gerstenhaber formula for the number of square matrices over 𝔽_{q} with the given characteristic polynomial (cf. [17, Thm. 2] and [6, §2]) together with Proposition 3.1.

8. Examples

In this section we outline some small examples to illustrate Conjecture 4.4 and its refined version Conjecture 6.2. Throughout, we take q = 2 and for 1 ≤ i, j ≤ 2, we let e_{ij} denote the 2 × 2 matrix over 𝔽_{q} with 1 in (i, j)^{th} place and 0 elsewhere. Also, let I = e_{11} + e_{22} be the 2 × 2 identity matrix and J = e_{11} + e_{12} + e_{21} + e_{22} be the 2 × 2 matrix with all the entries equal to 1.

Example 8.1. Consider m = 2 and n = 2. There are only 2 primitive polynomials of degree 2 × 2 = 4 over 𝔽_{2} and, in fact, we have 𝒫(4, 2) = {x^{4} + x + 1, x^{4} + x^{3} + 1}. It is easily verified that |BCMS(2, 2; 2)| = 16, i.e., the number of nonsingular (2, 2)- block companion matrices over 𝔽_{2} of order 2^{4} − 1 = 15 is 16, as predicted by Conjecture 4.4. Moreover, the elements

T = (\begin{matrix}0 & C_{0} \\ I & C_{1} \end{matrix})

of BCMS(2, 2; 2) for which Ψ(T) = x^{4} + x + 1 are precisely those for which the corresponding pair (C_{0}, C_{1}) of 2 × 2 matrices is given by either of the following.

(J − e_{21}, e_{21}) , (J − e_{21}, J) , (e_{12} + e_{21}, e_{21}) , (e_{12} + e_{21}, e_{12}) ,
(J − e_{11}, I) , (J − e_{22}, I) , (J − e_{12}, e_{12}) , (J − e_{12}, J) .

On the other hand, T ∈ BCMS(2, 2; 2) for which Ψ(T) = x^{4} + x^{3} + 1 are precisely those for which the corresponding pair (C_{0}, C_{1}) is given by either of the following.

(J − e_{21}, e_{21} + e_{22}) , (J − e_{21}, e_{11} + e_{21}) , (e_{12} + e_{21}, e_{22}) , (e_{12} + e_{21}, e_{11}), (J − e_{11}, J − e_{11}) , (J − e_{22}, J − e_{22}) , (J − e_{12}, e_{12} + e_{22}) , (J − e_{12}, e_{11} + e_{12}). Thus, both the fibers have cardinality 8, as predicted by Conjecture 6.2.

Example 8.2. Consider m = 2 and n = 3. Then 𝒫(6, 2) consists of six polynomials, namely, x^{6}+x^{5}+x^{4}+x+1, x^{6}+x+1, x^{6}+x^{5}+x^{3}+x^{2}+1, x^{6}+x^{5}+1, x^{6}+x^{4}+x^{3}+x+1, and x^{6} + x^{5} + x^{2} + x + 1. The fibers of Ψ for each of these consists of 32 elements of BCMS(2, 3; 2), which together, constitute the 192 elements of BCMS(2, 3; 2). It is seen, therefore, that Conjecture 4.4 as well as Conjecture 6.2 is valid in this case.

Acknowledgments

We are grateful to Surinder Singh Bedi, Gilles Lachaud, Harish Pillai, Samrith Ram, Sivaramakrishnan Sivasubramanian, and Patrick Solé for helpful discussions, and to Harald Niederreiter for helpful correspondence. The last two authors are also grateful to Director, SAG for his permission to publish this paper.

References

[1] N. Bourbaki, Algèbre, Chapitres 4 à 7, Masson, Paris, 1981.

[2] A. Cossidente and M. J. de Resmini, Remarks on Singer cyclic groups and their normalizers, Des. Codes Cryptogr. 32 (2004), 97–102.

[3] M. C. Crabb, Counting nilpotent endomorphisms, Finite Fields Appl. 12 (2006), 151–154.

[4] M.R. Darafsheh, Order of elements in the groups related to the general linear group, Finite Fields Appl. 11 (2005), 738-747.

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

[6] M. Gerstenhaber, On the number of nilpotent matrices with coefficients in a finite field, Illinois J. Math. 5 (1961), 330–333.

[7] S. R. Ghorpade and S. Ram, Block companion Singer cycles, primitive recursive vector sequences, and coprime polynomial pairs over finite fields, in preparation.

[8] S. W. Golomb, Shift Register Sequences, Holden-Day, San Francisco, 1967.

[9] B. Huppert, Endliche Gruppen I, Springer-Verlag, Berlin, 1967.

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

[11] R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 1983.

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

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

[14] H. Niederreiter, Psedorandom vector generation by the multiple-recursive matrix method, Math. Comp. 64 (1995), pp. 279–294.

[15] H. Niederreiter, Improved bound in the multiple-recursive matrix method for psedorandom number and vector generation, Finite Fields Appl. 2 (1996), pp. 225–240.

[16] B. Preneel, Introduction to the Proceedings of the Second Workshop on Fast Software Encryption (Leuven, Belgium, Dec 1994), pp. 1-5, Lecture Notes in Comput. Sci., 1008, Springer, Berlin, 1995.

[17] I. Reiner, On the number of matrices with given characteristic polynomial, Illinois J. Math. 5 (1961), 324-329.

[18] J. Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43 (1938), 377–385.

[19] 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).

[20] G. Zeng, W. Han, K. He and S. Fan High Efficiency Feedback Shift Register: σ-LFSR, preprint 2008.

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 and Scientific Analysis Group, Defense Research and Development Organisation Metcalfe House, Delhi 110054, India

E-mail address: sartajulhasan@gmail.com

Scientific Analysis Group, Defense Research and Development Organisation Metcalfe House, Delhi 110054, India

E-mail address: rameena10@yahoo.co.in