Contemporary Mathematics

Enumeration of Splitting Subspaces over Finite Fields

Sudhir R. Ghorpade and Samrith Ram

Abstract. We discuss an elementary, yet unsolved, problem of Niederreiter concerning the enumeration of a class of subspaces of finite dimensional vector spaces over finite fields. A short and self-contained account of some recent progress on this problem is included and some related problems are discussed.

1. Introduction

Finite fields have a remarkable property that finite dimensional vector spaces over them are naturally endowed with a canonical and compatible field structure. Indeed, we can simply “move the d” so as to write 𝔽_{q}^{d} ≃ 𝔽_{q^{d}}, where d is any positive integer and as usual, 𝔽_{q} denotes the finite field with q elements. This leads to some interesting notions where the field structure and the linear structure are intertwined. One such notion is that of a splitting subspace, which appears to go back at least to Niederreiter (1995) in connection with his work on pseudorandom number generation. Here is the definition:

Let m, n be positive integers, q a prime power, and α ∈ 𝔽_{q^{mn}}. An m-dimensional 𝔽_{q}-linear subspace W of 𝔽_{q^{mn}} is said to be α-splitting if

𝔽_{q^{mn}} = W ⊕ αW ⊕ ⋯ ⊕ α^{n−1}W.

Concerning these, Niederreiter [12] asked the following: given α ∈ 𝔽_{q^{mn}} such that 𝔽_{q^{mn}} = 𝔽_{q}(α), what is the number of m-dimensional α-splitting subspaces of 𝔽_{q^{mn}}?

Actually, the above question is a slightly more general version of the original question stated as an open problem in [12, p. 11] where it is assumed that q is prime and α is a primitive element of 𝔽_{q^{mn}} in the sense that it is a generator of the cyclic group 𝔽_{q^{mn}}^{∗} of nonzero elements of 𝔽_{q^{mn}}. But this general version seems quite natural and we will always consider Niederreiter’s question in this setting.

The main aim of this article is to make Niederreiter’s question better known and to facilitate further research on it. We were motivated by the fact that till recently there had not been any significant progress on this question since it was posed more than 15 years ago. Recent progress came about primarily by relating this question to seemingly different questions in cryptography. This brought to the fore exciting connections not only with cryptography but also matrix theory and finite projective geometry via the so called block companion Singer cycles. As a

\begin{matrix}c \\ ◯ \end{matrix}0000 (copyright holder)

2010 Mathematics Subject Classification. Primary 15A03, 11T06 05E99 Secondary 11T71.

result, a quantitative formulation of Niederreiter’s question suggested itself and a small breakthrough was obtained in the form of a solution in the case of splitting planes, i.e., when m = 2. We refer to Appendix A and to [14, 6, 7, 9] for these developments. While the myriad connections are no doubt interesting, we wish to underline the fact that Niederreiter’s question is a beautiful problem that is easy to state and is of interest in itself. With this in view, we give here an account of the recent progress on this question by focusing mainly on splitting subspaces per se and relegating its connections to cryptography and such to an appendix at the end. In particular, we include a short and self-contained proof of the solution to Niederreiter’s question in the case of splitting planes. Our original proof (cf. [7]) in the case m = 2 used a result of Benjamin and Bennett [1], which in turn was motivated by a question of Corteel, Savage, Wilf, and Zeilberger [2] (see [5, Rem. 4.2] for more historical information). Here we have removed the dependence on Benjamin and Bennett [1] by means of an auxiliary result (Lemma 3.3) and given a quick and independent proof of it by modifying an argument in [5, Thm. 4.1]. We have also used this opportunity to include certain variants of Niederreiter’s question and some preliminary results concerning them. Finally, for the convenience of the reader (and at the suggestion of a referee), we include a brief appendix where interconnections with cryptography, Singer cycles, etc., have been outlined.

2. Easy cases and guesses

Fix, throughout this paper, positive integers m, n and a prime power q. Let us first 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. To avoid such situations, we will always assume that α ∈ 𝔽_{q^{mn}} satisfies 𝔽_{q^{mn}} = 𝔽_{q}(α). In this case, {1, α, α^{2}, …, α^{mn−1}} forms a 𝔽_{q}-basis of 𝔽_{q^{mn}} and hence {1, α^{n}, α^{2n}, …, α^{(m−1)n}} spans an m-dimensional α-splitting subspace of 𝔽_{q^{mn}}, say Λ. Let us define

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

Niederreiter’s question is to determine (a nice formula for) S(α, m, n; q). The case when m or n is equal to 1 is quite trivial. Indeed, if n = 1, then the only mdimensional subspace, viz., W = 𝔽_{q^{mn}}, is α-splitting for every α ∈ 𝔽_{q^{mn}}. 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. Thus

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

In fact, the fraction on the right is always a lower bound for S(α, m, n; q). To see this, it suffices to note two things: (i) if Λ is as above, then βΛ is an m-dimensional α-splitting subspace for every β ∈ 𝔽_{q^{mn}}^{∗}, since α^{j}β = βα^{j} for 0 ≤ j ≤ n−1, and (ii) Λ = 𝔽_{q}(α^{n}) and Λ^{∗} is a subgroup of the cyclic group 𝔽_{q^{mn}}^{∗} of index (q^{mn}−1)/(q^{m}−1) so that if we let β ∈ 𝔽_{q^{mn}}^{∗} vary over representatives of distinct cosets of Λ^{∗} in 𝔽_{q^{mn}}^{∗}, then the corresponding subspaces βΛ are distinct (in fact, essentially disjoint). To work out a slightly nontrivial example, let us suppose m = 2 and n = 2. Recall that for any integers a, b with a ≥ b ≥ 0, the number of b-dimensional subspaces of an a-dimensional vector space over 𝔽_{q} is given by the Gaussian binomial coefficient

\left[{a \atop b}\right]_{q} := \frac{(q^{a} − 1)(q^{a} − q) ⋯ (q^{a} − q^{b−1})}{(q^{b} − 1)(q^{b} − q) ⋯ (q^{b} − q^{b−1})}.

Let W be subspace of 𝔽_{q^{4}}. Note that W = αW if and only if W = 0 or W = 𝔽_{q^{4}} (indeed, if 0 ≠ x ∈ W = αW, then W contains the linearly independent elements x, αx, α^{2}x, α^{3}x and so W = 𝔽_{q^{4}}). Now suppose dim W = 2 and W is not αsplitting. Then L = W ∩ αW is a 1-dimensional and W = L + α^{−1}L. Conversely, if L is a 1-dimensional subspace of 𝔽_{q^{4}}, then L + α^{−1}L is a 2-dimensional subspace of 𝔽_{q^{4}} that is not α-splitting. It follows that

S(α, 2, 4; q) = \left[{4 \atop 2}\right]_{q} − \left[{4 \atop 1}\right]_{q} = \frac{q^{4} − 1}{q^{2} − 1} q^{2}.

We now take an inspired leap and propose the following quantitative formulation of Niederreiter’s question.

Splitting Subspace Conjecture: Let α ∈ 𝔽_{q^{mn}} satisfy 𝔽_{q^{mn}} = 𝔽_{q}(α). Then

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

To be sure, the conjectural formula fits well with the examples considered above as well as the general lower bound for S(α, m, n; q). Still to arrive at it based only on a few examples is indeed quite a leap. As alluded to in the Introduction and explained in the appendix, the true inspiration, in fact, comes from a recent conjecture of Zeng, Han and He [14] and the subsequent work in [6] and [7]. But at any rate, we have a nice specific problem, which seems to be open, in general. Its solution in the only nontrivial case known so far will be considered next.

3. Splitting planes

We begin with a simple but useful observation that goes back to Niederreiter [12, Lem. 3] and says the enumeration of splitting subspaces of 𝔽_{q^{mn}} is equivalent to the enumeration of certain ordered bases of 𝔽_{q^{mn}}. To make this more precise, let us introduce some notation.

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 understanding that ℬ_{(v_{1},...,v_{m})}^{α} is to be regarded as an ordered set with mn elements. In case ℬ_{(v_{1},...,v_{m})}^{α} is an ordered basis of 𝔽_{q^{mn}}, the set {v_{1}, …, v_{m}} is necessarily a 𝔽_{q}-basis of an m-dimensional subspace of 𝔽_{q^{mn}} and we will refer to ℬ_{(v_{1},...,v_{m})}^{α} as an α-splitting ordered basis of 𝔽_{q^{mn}}. The number of α-splitting ordered bases of 𝔽_{q^{mn}} will be denoted by N(α, m, n; q).

Lemma 3.1. Let α ∈ 𝔽_{q^{mn}} satisfy 𝔽_{q^{mn}} = 𝔽_{q}(α), and let v_{1}, …, v_{m} ∈ 𝔽_{q^{mn}}. Then ℬ_{(v_{1},...,v_{m})}^{α} is an ordered basis of 𝔽_{q^{mn}} if and only if {v_{1}, …, v_{m}} span an m-dimensional α-splitting subspace of 𝔽_{q^{mn}}. Consequently,

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. The first assertion is obvious. The second follows from the first by noting 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}). □

From now on, we will focus on the case of splitting planes, i.e., the case m = 2.

Lemma 3.2. Let α ∈ 𝔽_{q^{2n}} be such that 𝔽_{q^{2n}} = 𝔽_{q}(α). Then

N(α, 2, n; q) = (q^{2n} − ν − 1) (q^{2n} − 1),

where ν denotes the cardinality of the set Σ of pairs (f_{1}, f_{2}) of nonzero polynomials in 𝔽_{q}[X] of degree < n with f_{2} monic and f_{1}, f_{2} relatively prime.

Proof. Fix v_{1} ∈ 𝔽_{q^{2n}} with v_{1} ≠ 0. Then for any v_{2} ∈ 𝔽_{q^{2n}}, the ordered set

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

is a 𝔽_{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{p_{1}(α)}{p_{2}(α)} : p_{i} ∈ 𝔽_{q}[X]^{∗} with deg(p_{i}) < n for i = 1, 2\} .

Now consider

Σ := \{\frac{f_{1}}{f_{2}} : f_{i} ∈ 𝔽_{q}[X]^{∗} with deg(f_{i}) < n for i = 1, 2 and GCD(f_{1}, f_{2}) = 1\} .

The map Σ → Σ_{α} given by (f_{1}, f_{2}) ↦ f_{1}(α)/f_{2}(α) is clearly well-defined and surjective. Moreover, if (f_{1}, f_{2}), (g_{1}, g_{2}) ∈ Σ are such that f_{1}(α)g_{2}(α) = g_{1}(α)f_{2}(α), then f_{1}g_{2} = g_{1}f_{2} because the minimal polynomial of α over 𝔽_{q} has degree 2n. Further since GCD(f_{1}, f_{2}) = 1 = GCD(g_{1}, g_{2}) and since f_{2}, g_{2} are monic, it follows that f_{2} = g_{2} and therefore f_{1} = g_{1}. Thus Σ_{α} is in bijection with Σ, and hence upon letting ν = |Σ|, we find

|{β ∈ 𝔽_{q^{2n}}^{∗} : 𝒮_{β} is linearly independent }| = (q^{2n} − 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^{2n} − 1). □

The cardinality ν of the set Σ appearing in Lemma 3.2 will be determined using the following more general result concerning pairs of relatively prime polynomials.

Lemma 3.3. Let N_{1}, N_{2} be positive integers with N_{1} ≥ N_{2} and let ν(N_{1}, N_{2}) denote the number of ordered pairs (f_{1}, f_{2}) of coprime nonzero polynomials in 𝔽_{q}[X] with f_{2} monic and deg f_{i} < N_{i} for i = 1, 2. Then ν(N_{1}, N_{2}) = q^{N_{1}+N_{2}−1} − 1.

Proof. We can partition the set of ordered pairs (f_{1}, f_{2}) of nonzero polynomials in 𝔽_{q}[X] with f_{2} monic and deg f_{i} < N_{i} for i = 1, 2 into disjoint subsets S_{d} (0 ≤ d < N_{2}), where S_{d} consists of pairs whose GCD is of degree d. Given any monic polynomial h ∈ 𝔽_{q}[X] of degree d and any coprime pair (g_{1}, g_{2}) of nonzero polynomials with g_{2} monic and deg g_{i} < N_{i} − d for i = 1, 2, it is easy to see that (hg_{1}, hg_{2}) ∈ S_{d}. Conversely, if (f_{1}, f_{2}) ∈ S_{d}, then the polynomial h = GCD(f_{1}, f_{2}) is monic of degree d and (f_{1}/h, f_{2}/h) is a coprime pair comprising of a nonzero polynomial of degree N_{1} − d and a monic polynomial of degree N_{2} − d. This shows that |S_{d}| = q^{d}ν(N_{1} − d, N_{2} − d) for 0 ≤ d < N_{2}. Since for any positive integer N, there are (q^{N} −1) nonzero polynomials in 𝔽_{q}[X] of degree < N and of these exactly (q^{N} − 1)/(q − 1) are monic, it follows that

(3.1)  (q^{N_{1}} − 1) \frac{(q^{N_{2}} − 1)}{q − 1} = ∑_{0≤d<N_{2}} |S_{d}| = ∑_{0≤d<N_{2}} q^{d}ν (N_{1} − d, N_{2} − d) .

If N_{2} = 1, we immediately obtain ν(N_{1}, N_{2}) = q^{N_{1}} − 1. On the other hand, if N_{2} > 1, then substituting N_{i} − 1 for N_{i} (i = 1, 2) in the above relation yields

(3.2)  (q^{N_{1}−1} − 1) \frac{(q^{N_{2}−1} − 1)}{q − 1} = ∑_{1≤d<N_{2}} q^{d−1}ν (N_{1} − d, N_{2} − d) .

Multiplying equation (3.2) by q and subtracting the result from (3.1), and then making an elementary calculation, we see that ν (N_{1}, N_{2}) = q^{N_{1}+N_{2}−1} − 1. □

It is now a simple matter to show that the Splitting Subspace Conjecture holds in the affirmative when m = 2 (and n is arbitrary).

Theorem 3.4. Let α ∈ 𝔽_{q^{2n}} be such that 𝔽_{q^{2n}} = 𝔽_{q}(α). Then

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

Proof. Follows from Lemmas 3.1, 3.2, and 3.4. □

4. Refinements and Extensions

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 4.1. Let α ∈ 𝔽_{q^{mn}} be such that 𝔽_{q^{mn}} = 𝔽_{q}(α). Then
|𝔖_{α}^{x}| = |𝔖_{α}^{y}| for any x, y ∈ 𝔽_{q^{mn}}^{∗}.

Moreover, for any x ∈ 𝔽_{q^{mn}}^{∗}, the set 𝔖_{α}^{x} is nonempty and

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

Proof. If x, y ∈ 𝔽_{q^{mn}}^{∗} and β = y/x, then W ↦ βW gives a bijection of 𝔖_{α}^{x} onto 𝔖_{α}^{y}. Moreover, for any x ∈ 𝔽_{q^{mn}}^{∗}, the 𝔽_{q}-linear span of {xα^{in} : 0 ≤ i < m} is clearly in 𝔖_{α}^{x} and thus 𝔖_{α}^{x} is nonempty. Finally, by counting in two different ways the set {(W, x) : W ∈ 𝔖_{α} and x ∈ W } of all pointed α-splitting subspaces, we find |𝔖_{α}| (q^{m} − 1) = |𝔖_{α}^{x}| (q^{mn} − 1), as desired. □

It may be remarked that the lower bound for S(α, m, n; q) discussed in Section 2 is an immediate consequence of Proposition 4.1. In light of Proposition 4.1, we see that the Splitting Subspace Conjecture is equivalent to the following simpler looking conjecture.

Conjecture 4.2 (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)}.

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]. 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 ntuples) of nilpotent m × m matrices over 𝔽_{q}.

If the Splitting Subspace Conjecture were to hold in the affirmative, then an obvious consequence would be that the number of m-dimensional pointed α-splitting subspaces of 𝔽_{q^{mn}} is independent of the choice of α ∈ 𝔽_{q^{mn}} as long as it satisfies 𝔽_{q^{mn}} = 𝔽_{q}(α). In other words, for any α, β ∈ 𝔽_{q^{mn}},

S(α, m, n; q) = S(β, m, n; q) provided 𝔽_{q^{mn}} = 𝔽_{q}(α) = 𝔽_{q}(β).

In general we do not know if this weaker statement is true. The following result summarizes the cases where the answer is known.

Proposition 4.3. Let α ∈ 𝔽_{q^{mn}} be such that 𝔽_{q^{mn}} = 𝔽_{q}(α). If
β = \frac{aα^{q^{r}} + b}{cα^{q^{r}} + d} for some nonnegative integer r and (\begin{matrix}a & b \\ c & d \end{matrix}) ∈ GL_{2}(𝔽_{q}),

then 𝔽_{q^{mn}} = 𝔽_{q}(β) and S(α, m, n; q) = S(β, m, n; q).

Proof. First, note that if β = cα for some c ∈ 𝔽_{q}^{∗} or β = α + d for some d ∈ 𝔽_{q}, then 𝔽_{q^{mn}} = 𝔽_{q}(β) and in view of Lemma 3.1, we see that 𝔖_{α} = 𝔖_{β} and so S(α, m, n; q) = S(β, m, n; q). Further, if α ≠ 0 (which is necessarily the case if mn > 1), then 𝔽_{q^{mn}} = 𝔽_{q}(1/α) and again in view of Lemma 3.1 and the fact that multiplication by the nonzero element α^{−(n−1)} preserves linear independence, it follows that 𝔖_{1/α} = 𝔖_{α} and so S(α, m, n; q) = S(1/α, m, n; q). Finally, note that for any nonnegative integer r, the elements α and α^{q^{r}} are Galois conjugate, i.e., they have the same minimal polynomial over 𝔽_{q}, and therefore 𝔽_{q^{mn}} = 𝔽_{q} (α^{q^{r}}) and there is a one-to-one correspondence between α-splitting and α^{q^{r}}-splitting subspaces, induced by the corresponding element of the Galois group of 𝔽_{q^{mn}} over 𝔽_{q}. Combining these, we obtain the desired result. □

It may be remarked that in view of Proposition 4.3 and the normal basis theorem [10, p. 60], we see that there is a 𝔽_{q}-basis ℬ of 𝔽_{q^{mn}} such that each element of ℬ generates 𝔽_{q^{mn}} over 𝔽_{q} and S(α, m, n; q) = S(β, m, n; q) for all α, β ∈ ℬ.

Finally, we note that Niederreiter’s question can also be posed in a more general situation where instead of considering multiples of an m-dimensional subspace by powers of α, we consider its transforms by an endomorphism of 𝔽_{q^{mn}}. More precisely, given any 𝔽_{q}-linear endomorphism T : 𝔽_{q^{mn}} → 𝔽_{q^{mn}}, we say that an m-dimensional subspace W of 𝔽_{q^{mn}} is T -splitting if

𝔽_{q^{mn}} = W ⊕ T (W) ⊕ T^{2}(W) ⊕ ⋯ ⊕ T^{n−1}(W),

where T^{j} denotes the j-fold composite of T with itself (0 ≤ j < n). We let

S_{T} (m, n; q) = the number of m-dimensional T -splitting subspaces of 𝔽_{q^{mn}}.

Evidently, if T is the 𝔽_{q}-linear endomorphism of 𝔽_{q^{mn}} given by x ↦ αx, then S_{T} (m, n; q) = S(α, m, n; q). A more general variant of Niederreiter’s question is to determine S_{T} (m, n; q) for every 𝔽_{q}-linear endomorphism T of 𝔽_{q^{mn}}. An answer to this question does not seem to be known, even conjecturally. It should be noted, however, that certain restrictions on the structure of T will be needed in order that S_{T} (m, n; q) is nonzero and independent of the choice of T in a suitable class. For example, if m = 1, then the existence of m-dimensional T -splitting subspaces of 𝔽_{q^{mn}} evidently forces T to be cyclic and the minimal polynomial of T to be the characteristic polynomial of T. A complete answer to the above variant of Niederreiter’s question in this case is given below. On the other hand, if n = 1, then W = 𝔽_{q^{mn}} is obviously the only m-dimensional T -splitting subspace, for any T : 𝔽_{q^{mn}} → 𝔽_{q^{mn}} and thus S_{T} (m, 1; q) = 1.

Proposition 4.4. Let T : 𝔽_{q^{n}} → 𝔽_{q^{n}} be a cyclic 𝔽_{q}-linear endomorphism and let p_{T} ∈ 𝔽_{q}[X] be the minimal polynomial of T. Suppose p_{T} = f_{1}^{e_{1}} ⋯ f_{k}^{e_{k}} is the factorization of p_{T} into positive powers of distinct monic irreducible polynomials f_{i} ∈ 𝔽_{q}[X] with deg(f_{i}) = n_{i} for i = 1, …, k. Then

S_{T} (1, n; q) = \frac{q^{n}}{q − 1} ∏_{i=1}^{k} (1 − \frac{1}{q^{n_{i}}} ) .

Proof. Clearly any 1-dimensional T -splitting subspace W of 𝔽_{q^{n}} is spanned by a cyclic vector for T. So it suffices to count the number of cyclic vectors for T. Let v ∈ 𝔽_{q^{n}} be a cyclic vector for T. Then any other cyclic vector w ∈ 𝔽_{q^{n}} of T is necessarily of the form f(T)v where f ∈ 𝔽_{q}[X] is such that deg f ≤ n − 1. Hence w is cyclic only if the T -annihilator of w is precisely p_{T}. Now the annihilator of f(T)v is p_{T} if and only if gcd(f, p_{T}) = 1. Thus the number of f ∈ 𝔽_{q}[X] with deg f ≤ n − 1 such that w = f(T)v is cyclic is equal to the number of polynomials in 𝔽_{q}[X] of degree ≤ n − 1 that are coprime to p_{T}. This is given by the q-analogue of the Euler totient function (cf. [10, p. 122]) evaluated at the minimal polynomial of T, namely,

Φ_{q}(p_{T}) = q^{n} ∏_{i=1}^{k} (1 − \frac{1}{q^{n_{i}}} ) .

Note that f_{1}(T)v ≠ f_{2}(T)v for distinct polynomials f_{1}, f_{2} of degree at most n − 1, for otherwise p_{T} | (f_{1} − f_{2}), which is a contradiction. Thus there are Φ_{q}(p_{T}) distinct cyclic vectors for T. Since each 1-dimensional T -splitting subspace of 𝔽_{q^{n}} is spanned by precisely q − 1 distinct cyclic vectors, it follows that the number of 1-dimensional T -splitting subspaces of 𝔽_{q^{n}} is Φ_{q} (p_{T}) /(q − 1), as desired. □

It may be noted that if α ∈ 𝔽_{q^{mn}} is such that 𝔽_{q^{mn}} = 𝔽_{q}(α) and if T is the 𝔽_{q}-linear endomorphism of 𝔽_{q^{mn}} given by x ↦ αx, then the minimal polynomial p_{T} of T is precisely the minimal polynomial of α over 𝔽_{q}. Hence p_{T} is irreducible and therefore the formula in Proposition 4.4 reduces to S(α, 1, n; q) = (q^{n} − 1)/(q − 1), exactly as observed in the beginning of Section 3.

Appendix A. Vector Recurrences and Singer Cycles

As before, we fix positive integers m, n and a prime power q. For any positive integer d, we denote, as usual, 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}).

Let C_{0}, C_{1}, …, C_{n−1} ∈ M_{m}(𝔽_{q}). Given any initial state in (𝔽_{q}^{m})^{n}, i.e., an ntuple (s_{0}, …, s_{n−1}) of (row) vectors in 𝔽_{q}^{m}, the vector recurrence (of order n over 𝔽_{q}^{m})

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

generates an infinite sequence s^{∞} = (s_{0}, s_{1}, …) of vectors in 𝔽_{q}^{m}. It is easy to see that there are integers r, n_{0} with 1 ≤ r ≤ q^{mn} − 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 vector recurrence (A.1) is said to be primitive if for any choice of nonzero initial state, the infinite sequence generated by it is periodic of period q^{mn} − 1. Vector recurrences are also known as word oriented linear feedback shift registers or σ-LFSRs, and they reduce to classical LFSRs or homogeneous linear recurrences of order n (with coefficients in 𝔽_{q}) when m = 1. Primitive vector recurrences are of interest in cryptography since they are useful in pseudorandom number generation, or alternatively, for designing fast, secure, and efficient stream ciphers. While the study of (ordinary) LFSRs is classical (see, e.g., [10, Chap. 8]), vector recurrences and the corresponding multiple recursive method appears to have been first studied by Niederreiter [11, 12]. This method seems to have been rediscovered by Zeng, Han and He [14] in the guise of σ-LFSRs. Prior to that, generalizations of LFSRs (that turn out to be special cases of vector recurrences of Niederreiter) were studied by Tsaban and Vishne [13] and later by Dewar and Panario [3], and these are called transformation shift registers or TSRs. We refer to the recent paper of Hasan, Panario and Wang [8] for more on TSRs and related developments.

Enumerating primitive LFSRs of a given order is easy and well-known, whereas it is an open question in the case of σ-LFSRs. The following conjectural formula was proposed in [6] as a q-ary version of a conjecture of Zeng, Han and He [14].

Primitive Vector Recurrence Conjecture (PVRC): The number of primitive vector recurrences of order n over 𝔽_{q}^{m} is

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

To relate the above to matrices, note that the maximum possible order of an element of the finite group GL_{d}(𝔽_{q}) is q^{d} − 1 (see, e.g., [6, Prop. 3.1]) and elements of order q^{d} − 1 are called Singer cycles in GL_{d}(𝔽_{q}). By an (m, n)-block companion Singer cycle over 𝔽_{q} we shall mean a Singer cycle T in GL_{mn}(𝔽_{q}) of the form

(A.3)  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 relation between (m, n)- block companion matrices such as T above and vector recurrences will be clearer if one observes that (A.1) is equivalent to the relation S_{i+1} = S_{i}T for i ≥ 0, where S_{i} is the i^{th} state vector (s_{i}, …, s_{i+n−1}) and T is as in (A.3). Primitive vector recurrences correspond precisely to (m, n)-block companion Singer cycles [6, Thm. 5.2] and thus the PVRC is equivalent to

Block Companion Singer Cycle Conjecture (BCSCC): The number of (m, n)-block companion Singer cycles over 𝔽_{q} is given by (A.2).

It turns out that the map that sends a matrix in M_{mn}(𝔽_{q}) to its characteristic polynomial maps the set of (m, n)-block companion Singer cycles over 𝔽_{q} onto the set of primitive polynomials in 𝔽_{q}[X] of degree mn (cf. [6, Thm. 6.1]). Recall that a polynomial in 𝔽_{q}[X] of degree d 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 𝔽_{q^{d}}. Evidently, the number of primitive polynomials in 𝔽_{q}[X] of degree d is φ(q^{d} − 1)/d. With this in view, BCSCC is implied by the following stronger conjecture.

Primitive Fiber Conjecture (PFC): For any primitive polynomial f in 𝔽_{q}[X] of degree mn, the number of (m, n)-block companion Singer cycles over 𝔽_{q} having f as its characteristic polynomial is

(A.4)  q^{m(m−1)(n−1)} ∏_{i=1}^{m−1}(q^{m} − q^{i}).

The above conjecture, proposed first in [6], was further strengthened in [7] as follows.

Irreducible Fiber Conjecture (IFC): For any irreducible polynomial f in 𝔽_{q}[X] of degree mn, the number of (m, n)-block companion Singer cycles over 𝔽_{q} having f as its characteristic polynomial is given by (A.4).

To relate irreducible fibers to splitting subspaces, it suffices to observe (see, e.g., Lemmas 5.1 and 5.2 of [7]) that if f ∈ 𝔽_{q}[X] is an irreducible polynomial of degree mn and if α ∈ 𝔽_{q^{mn}} is any root of f, then the the number of (m, n)- block companion Singer cycles over 𝔽_{q} having f as its characteristic polynomial is precisely N(α, m, n; q)/(q^{mn}−1), where N(α, m, n; q) is as in Section 3 above. With this in view, the relation between the conjectures stated above and the Splitting Subspace Conjecture (SSC) as well as the Pointed Splitting Subspace Conjecture (PSSC) stated earlier in this paper can be summarized as follows.

PSSC ⟺ SSC ⟺ IFC ⟹ PFC ⟹ BCSCC ⟺ PVRC.

In view of the results proved in the previous sections, it is seen that each of these conjectures holds in the affirmative when m ≤ 2 or n ≤ 1. It may also be remarked that in order to prove the PFC, one may fix a primitive polynomial f ∈ 𝔽_{q}[X] of degree mn and a matrix T ∈ M_{mn}(𝔽_{q}) with f as its characteristic polynomial. Then matrices in M_{mn}(𝔽_{q}) having f as its characteristic polynomial are necessarily similar to T. With this in view, Lachaud [9] has made a fine analysis of the similarity class of T and the collection of (m, n)-block companion matrices in it. He shows that T may be chosen to be a block diagonal matrix and the (m, n)-block companion matrices in the similarity class of T correspond to V^{−1}T V, where V is a so called block Vandermonde matrix. This analysis and the results of Lachaud [9] lend further insight into the above conjectures. Nonetheless, the general case remains open.

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. M. Dewar and D. Panario, Linear transformation shift registers, IEEE Trans. Inform. Theory, 49 (2003), 2047–2052.

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

5. 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.

6. 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.

7. S. R. Ghorpade and S. Ram, Block companion Singer cycles, primitive recursive vector sequences, and coprime polynomial pairs over finite fields, Finite Fields Appl. 17 (2011), 461–472.

8. S. U. Hasan, D. Panario, and Q. Wang, Word-oriented transformation shift registers and their linear complexity, Sequences and Their Applications – SETA 2012, Lecture Notes in Comput. Sci., Springer, Berlin (2012), to appear.

9. G. Lachaud, Construction of block companion matrices in a conjugacy class, preprint, 2011.

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

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

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

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

14. G. Zeng, W. Han and K. He, High efficiency feedback shift register: σ-LFSR, Cryptology e-Print Archive: Report 2007/114 (available: http://eprint.iacr.org/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: samrith@gmail.com