Counting the Restricted Gaussian Partitions of a Finite Vector Space

Fusun Akman and Papa A. Sissokho 4520 Mathematics Department Illinois State University Normal, IL 61790-4520 USA

                   akmanf@ilstu.edu
                   psissok@ilstu.edu

Abstract

A subspace partition Π of a finite vector space V = V (n, q) of dimension n over GF(q) is a collection of subspaces of V such that their union is V, and the intersection of any two subspaces in Π is the zero vector. The multiset T_{Π} of dimensions of subspaces in Π is called the type of Π, or, a Gaussian partition of V. Previously, we showed that subspace partitions of V and their types are natural, combinatorial q-analogues of the set partitions of {1, …, n} and integer partitions of n respectively. In this paper, we connect all four types of partitions through the concept of “basic” set, subspace, and Gaussian partitions, corresponding to the integer partitions of n. In particular, we combine Beutelspacher’s classic construction of subspace partitions with some additional conditions to derive a special subset G of Gaussian partitions of V. We then show that the cardinality of G is a rational polynomial R(q) in q, with R(1) = p(n), where p is the integer partition function.

1 Introduction

1.1 The background

Let n be a positive integer and q be a prime power. Let V = V (n, q) denote the n-dimensional vector space over GF(q). A subspace partition (also known as vector space partition) of V is a collection of subspaces of V such that their union is V, and the intersection of any two subspaces in Π is the zero vector; for example, see the recent survey by Heden [14]. Subspace partitions are used to construct translation planes and nets [3, 4, 8], error-correcting codes [15, 20, 21, 23], orthogonal arrays [12], and designs [13, 26]. The origins of subspace partitions can be traced back to the general problem of partitioning a finite group into subgroups intersecting only at the identity element [19, 24, 27].

Let Π be a subspace partition of V = V (n, q). Suppose that Π consists of x_{i} subspaces of dimension d_{i} for 1 ≤ i ≤ k. The multiset T_{Π} = d_{1}^{x_{1}} … d_{k}^{x_{k}} of dimensions is then called a partition type of V. Clearly, not every multiset T that contains plausible dimensions is a partition type of V. However, if T is a partition type, then it must satisfy certain necessary conditions. One such condition, called the packing condition, is obtained by counting the nonzero vectors of V in two ways:

∑_{i=1}^{k} x_{i}(q^{d_{i}} − 1) = (q^{n} − 1).  (1)

A second necessary condition comes from dimension considerations. If U and W are subspaces of V (n, q), then it is well known that the subspace spanned by U ∪W has dimension dim(U) + dim(W) − dim(U ∩ W). Therefore, if T is a partition type, then it must satisfy

\begin{cases}2d_{i} ≤ n, & if x_{i} ≥ 2; \\ d_{i} + d_{j} ≤ n, & if i ≠ j. \end{cases}  (2)

The necessary conditions (1) and (2) are not sufficient in general. For instance, 2^{10}1^{1} is not a partition type of V (5, 2). There are several other nontrivial necessary conditions [16, 17, 18].

In previous papers [1, 2], we studied the lattice of subspace partitions of V = V (n, q) and the poset of partition types of V (which we called the Gaussian partitions of V). We proved several results, revealing these two objects as natural, combinatorial q-analogues of the set partitions of n = {1, …, n} and the integer partitions of n respectively. In this paper, we connect all four types of partitions through the concept of “basic” set, subspace, and Gaussian partitions, which correspond to the integer partitions of n. In particular, we distinguish “regular” subspace partitions as those that owe their existence to the most natural construction due to Beutelspacher [6] and give an argument on why it is not practical at this point to count the “irregular” Gaussian partitions. We then impose additional conditions on the regular subspace (and hence Gaussian) partitions and call them the “restricted” partitions, which are certain refinements of the basic ones. Our main result is as follows:

Theorem 1. Let q be a prime power and n be a positive integer. Then the number of restricted Gaussian partitions of V (n, q) is a rational polynomial R(q) in q. Moreover, we have R(1) = p(n), where p is the integer partition function.

This is the counterpart of an earlier result of ours [1], which states that the number of the full set of subspace partitions of V is congruent to the Bell number B_{n}, the number of set partitions of n, modulo q − 1.

1.2 Why consider restricted partitions?

The techniques we used in our first article [1] in this series to count the subspace partitions of V = V (n, q) are not applicable to the process of enumerating the set of all Gaussian partitions; new methods need to be developed. In our second article [2], we demonstrated that counting the Gaussian partitions of V for n ≤ 5 by brute force was fairly straightforward, but that as soon as we reached n = 6, we were stymied: we simply do not have much information about the existence of maximal subspace partitions that are not constructed by traditional means. Some exotic examples (used to disprove conjectures), such as a subspace partition of V (8, 2) with 34 subspaces of dimension 3 and 17 subspaces of dimension 1, are often constructed by the aid of computers [2, 12]. However, an analysis conducted by Lambert [22] shows that there is no apparent structure in the aforementioned example, making it difficult to generalize. Hence, the problem of determining the maximum-size partial spreads remains largely unsolved. Similarly, finding the maximal partial spread partitions of V (n, q) for n ≥ 4 is currently intractable. This makes the precise counting of all Gaussian partitions an essentially impossible task. Nevertheless, it would still be interesting to count certain subsets of the Gaussian partitions, in particular, those that could provide a q-analogue of integer partitions.

As a first step towards conquering the counting problem, we propose to consider only those subspace partitions that are constructed from V by the Beutelspacher method described in Section 2.2.2. This method is crucial in constructing examples for the applications we referred to in the previous section. We will designate the resulting subspace and Gaussian partitions as regular. This convention is akin to leaving out the exceptional groups in the classification of finite simple groups, whose existence and structures require the use of more customized techniques. Unfortunately, the resulting poset of regular Gaussian partitions is still very difficult to count — we had to stop at n = 7. The problem stems from the fact that the same regular Gaussian partition may be obtained by more than one sequence of consecutive “refinements” of subspace dimensions, and there seems to be no consistent way to prefer one construction over the others. That is, there is no good way of building a tree structure out of all regular Gaussian partitions with respect to preferred refinements. However, regular Gaussian partitions can conceivably be counted by sheer computer power for a specific dimension n in terms of q. For n ≤ 6, the numbers of regular Gaussian partitions of V (n, q) turned out to be rational polynomials in q with the value p(n) at q = 1, placing regular Gaussian partitions among strong contenders for a q-analogue of the integer partition function.

As a second step, we propose counting a subset of regular Gaussian partitions (defined by simple rules) while maintaining the property that this set of Gaussian partitions provides a qanalogue of integer partitions. To that end, we enumerate the restricted Gaussian partitions of V (n, q), described in detail in Section 3.2. This method requires that as a starting point, we introduce the notions of basic set, basic subspace, and basic Gaussian partitions that naturally correspond to the integer partitions of n (the basic set and basic Gaussian partitions are in fact in 1-1 correspondence with the integer partitions). We then apply the Beutelspacher method of refinement selectively, so that the new subspace dimensions that are created from any one dimension can be squeezed in between the existing ones, without disturbing the nonincreasing sequence (there are a few more conditions). Our claim that the choice of restricted Gaussian partitions is a reasonable compromise is validated by the fact that these partitions do form a q-analogue for integer partitions, as proven in Theorem 1.

Our ultimate goal is to find simple enough rules to capture the largest subset of Gaussian partitions (ideally all of them) forming a q-analogue of integer partitions that counts combinatorial objects. We realized a similar goal in our first paper [1] by showing that the full lattice of subspace partitions is the natural q-analogue of the lattice of set partitions.

2 Set, integer, and subspace partitions

2.1 Set partitions

Definition 2 (Split of subset). A split of a subset D of n = {1, …, n} with d = |D| ≥ 2 is a refinement operation denoted by (a, b), where a + b = d and a ≥ b ≥ 1, that results in partitioning D into two disjoint subsets A and B of cardinalities a and b respectively.

The partition {A, B} of D is not unique as defined. However, we can make it unique as follows:

Definition 3 (Ordering split of subset). An ordering split of a subset D of n is a split (a, b) as in the above definition such that any element of A is strictly less than any element of B.

Lemma 4. Any set partition of n can be obtained by applying a sequence of splits to n (after the first split, we understand that each subsequent split is applied to a smaller subset generated previously). The empty sequence corresponds to the partition {n} with one part.

Definition 5 (Basic set partition). A set partition of n = {1, …, n} with k parts will be called basic if its parts can be labeled D_{1}, …, D_{k}, with cardinalities d_{1}, …, d_{k} respectively, in such a way that:

1. d_{1} ≥ ⋯ ≥ d_{k} ≥ 1, and

2. for all i with 1 ≤ i ≤ k, the collection D_{1}, …, D_{i} is a set partition of d = {1, ⋯, d}, where d = d_{1} + ⋯ + d_{i}.

For the next two lemmas, let us adopt the notation of Definition 5.

Lemma 6. The set of basic set partitions of n is in one-to-one correspondence with the integer partitions of n, via

{D_{1}, …, D_{k}} ⟷ d_{1} … d_{k}.

Remark 7. Note that we are only interested in the unordered integer partitions of n here. For instance, the sequence 5 · 3 · 1 · 1 and its permutations (e.g., 3 · 5 · 1 · 1) will all represent the same integer partition of n = 10.

Example 8. The collection {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13}, {14}, {15}, {16}, {17}} is the basic set partition of 17 corresponding to the integer partition 5^{2}3^{1}1^{4} of 17.

Lemma 9. Any basic set partition of n with parts described as in Definition 5 can be obtained by applying the sequence

(d_{1} + ⋯ + d_{k−1}, d_{k}), (d_{1} + ⋯ + d_{k−2}, d_{k−1}), …, (d_{1}, d_{2})

of ordering splits to n. By definition, the empty sequence corresponds to {n}.

2.2 Regular, basic, and restricted subspace partitions

2.2.1 Splits of subspaces

The study of all possible subspace partitions and their types considered in [1, 2] is hampered by the fact that even in small dimensions, the maximal subspace partitions of V (n, q) have not been enumerated for all q, and even their types remain a mystery. Examples are the number of 2-spreads of V (4, q) and the types of the exceptional partitions of V (6, q) that we mentioned elsewhere [2]. As a matter of fact, when we put aside the dozens of special cases of partition constructions of novel types [7, 17, 25], there have been only two basic existence theorems in the literature that are used consistently:

(A) If d divides n, then André [3] proved that V (n, q) has a refinement of type d^{\frac{q^{n}−1}{q^{d}−1}} , which is better known as a d-spread of V (n, q).

(B) If 1 ≤ d < n/2, then it was proved by Beutelspacher [6], and independently by Bu [7], that V (n, q) has a refinement of type (n − d)^{1} d^{q^{n−d}}.

The case d = n/2 is covered by (A). If d divides n but is not equal to n/2, then finitely many applications of the move (B) will give us a spread as in (A). Thus, these two refinements can be combined into a single one:

(C) If 1 ≤ d ≤ n/2, then V (n, q) has a refinement of type (n − d)^{1} d^{q^{n−d}}.

Definition 10 (Split of subspace). A split is a refinement of the form (C) on any one subspace in a subspace partition. We will let (a, b) (for a ≥ b ≥ 1) denote a subspace split that produces the refinement (a + b)^{1} → a^{1}b^{q^{a}} of the type (a + b)^{1}.

Note that a split only shows the type of the move and not the subspace it is applied to. It is possible to obtain many different refined subspace partitions (of the same type) by applying a split to a specific subspace partition, just as in the case of set partitions.

2.2.2 The mechanism for creating regular subspace partitions

We will use the construction of Beutelspacher [6] and Bu [7] that yields the partitions in the statement (B) discussed earlier. This construction starts from a given direct sum decomposition W ⊕ U of V (n, q) and a partition of U to give us a partition of V (n, q) that includes U and W. Moreover, the new subspaces in the partition reproduce the dimension of U.

Theorem 11 (Beutelspacher [6]). Let V = V (n, q), U and W be subspaces of V such that V = W ⊕ U, and s = dim(W) ≥ dim(U) = t. Let {w_{1}, …, w_{s}} be a basis of W, and {u_{1}, …, u_{t}} be a basis of U. Moreover, we identify W with the field GF(q^{s}). For every element γ ∈ W, define a subspace U_{γ} of V by

U_{γ} = span({u_{1} + γw_{1}, …, u_{t} + γw_{t}}).

Then dim(U_{γ}) = t, U_{γ} ∩ U_{γ′} = {0} for γ ≠ γ′, and the collection

{W } ∪ {U_{γ} : γ ∈ W }

of subspaces forms a partition of V.

Theorem 11 can be used to accomplish refinements described in (C):

Corollary 12. Choosing dim(W) = n − d and dim(U) = d (where d ≤ n/2) in Theorem 11, we obtain a subspace partition of V (n, q) of type (n − d)^{1}d^{q^{n−d}}.

We will informally designate the new subspaces U_{γ} created in the above corollary, for which γ ≠ 0, as “copies” of U = U_{0}.

Definition 13 (Regular subspace partition). A regular subspace partition of V = V (n, q) is one that is obtained from V via a finite number of splits of type (C), employing the mechanism described in Corollary 12.

2.2.3 Basic subspace partitions

Let us fix a basis S = {e_{1}, …, e_{n}} of V = V (n, q), and identify it with n via the subscripts.

Definition 14 (Ordering split of special subspace). Let D be a nonempty subset of S. An ordering split of type (a, b) of ⟨D⟩, the subspace of V (n, q) generated by D, is one that is created by applying the ordering split (a, b) to the set D to obtain a partition {A, B} of D, then applying the construction in Corollary 12 to ⟨D⟩ = ⟨A⟩ ⊕ ⟨B⟩, with W = ⟨A⟩ and U = ⟨B⟩.

Definition 15 (Basic subspace partition). We call a regular subspace partition Π of V basic if it can be obtained by applying a sequence of ordering splits to V = ⟨S⟩ that would have resulted in the corresponding basic set partition of S.

Lemma 16. Let Π be a basic subspace partition as described above, and let {D_{1}, …, D_{k}} be the corresponding basic set partition of the basis S of V. Then Π contains the subspaces ⟨D_{1}⟩, …, ⟨D_{k}⟩ of V.

Note that due to the different choices of identification of W with GF(q^{s}) in Theorem 11, there may be multiple basic subspace partitions associated with an integer partition of n. However, all of these basic subspace partitions are in the same orbit under the action by GL(n, q).

2.2.4 Restricted subspace partitions

Definition 17 (Left/right subspaces). Consider a subspace W of V of dimension a+b, with a ≥ b ≥ 1. We will call the a-dimensional subspace that results from a split of W of type (a, b) a left subspace and the q^{a} dimensional subspaces of dimension b that are produced in the same split right subspaces.

Even if a = b, there is still one distinguished left subspace due to the construction in Theorem 11.

From this point on, we will only consider regular subspace partitions of V (n, q) that are either basic or are obtained from a basic one by finitely many splits via the mechanism described in Corollary 12 and three additional rules that we will outline below.

Definition 18 (Restricted subspace partition). Let V = V (n, q). A regular subspace partition Γ of V is called a restricted subspace partition if it is basic, or if it can be obtained from a basic subspace partition Π (as given in Definition 15 and Lemma 16) by refinements of type (C) according to the following rules:

1. The unique ancestor rule: The subspaces ⟨D_{i}⟩ in Π will be left intact.

2. The left-right rule: Only copies of ⟨D_{i}⟩ and subsequently the resulting left subspaces can be split.

3. The dimension rule: If f_{1} ⋯ f_{s} is the Gaussian partition describing the nonincreasing dimensions of the subspaces that exist at any stage of the construction, then applying a split (a, b) to a subspace of dimension f_{i} with i < s will result in the ordering f_{i} > a ≥ b ≥ f_{i+1}. Exception: The same split (a, b) may be applied to several subspaces of dimension f_{i} simultaneously.

Remark 19. The untouched subspaces ⟨D_{i}⟩ reflect the corresponding partitioning of the basis S of V as a set. This way, we can trace every restricted subspace partition back to a unique basic set partition as well as a unique integer partition. The dimension rule dictates that the parts a and b of the split cannot be strictly smaller than the dimensions to the right of f_{i}, if any.

3 Restricted Gaussian partitions extend integer partitions

3.1 Basic Gaussian partitions

Definition 20 (Basic Gaussian partition). A regular Gaussian partition of V (n, q) is called basic if it is the type of a basic subspace partition of V (n, q).

Proposition 21. The basic Gaussian partitions of V (n, q) and the basic set partitions of n are in one-to-one correspondence with the integer partitions of n.

Example 22. The integer partition 5^{2}3^{1}1^{4} of n = 17 is represented by the basic Gaussian partition

5^{1}5^{q^{5}}3^{q^{10}}1^{q^{13}}1^{q^{14}}1^{q^{15}}1^{q^{16}} = 5^{1+q^{5}}3^{q^{10}}1^{q^{13}+q^{14}+q^{15}+q^{16}}

of V (17, q). Note that the exponent of 5^{q^{5}} tells us that the sum of the dimensions that come before (equivalently, the parts of the corresponding integer partition) is 5, the exponent of 3^{q^{10}} tells us that the previous sum is 10, and the exponent of 1^{q^{13}} tells us that the previous dimensions add up to 13, etc.

The following proposition provides an explicit shape for basic Gaussian partitions.

Proposition 23.

(1) The basic Gaussian partition of V (n, q) that corresponds to the integer partition d_{1} ⋯ d_{k} of n, with d_{1} ≥ ⋯ ≥ d_{k}, is given by

T = d_{1}^{1}d_{2}^{q^{d_{1}}}d_{3}^{q^{d_{1}+d_{2}}} ⋯ d_{k}^{q^{d_{1}+···+d_{k−1}}}.

Conversely, a partition of type T, where d_{1} ≥ ⋯ ≥ d_{k} and d_{1} + ⋯ + d_{k} = n, is basic.

(2) (The Addition Property) For a Gaussian partition written as in part (1), the exponent q^{t} of any dimension d_{i} reflects the sum t = d_{1} + ⋯ + d_{i−1} of the parts of the corresponding integer partition that come before d_{i} (the empty sum is zero).

(3) If we require the dimensions d_{i} to be distinct, then the basic Gaussian partition corresponding to the integer partition d_{1}^{n_{1}} ⋯ d_{k}^{n_{k}} of n, with d_{1} > ⋯ > d_{k}, is given by

T = d_{1}^{1+q^{d_{1}}+···+q^{(n_{1}−1)d_{1}}}d_{2}^{q^{n_{1}d_{1}}+q^{n_{1}d_{1}+d_{2}}+···+q^{n_{1}d_{1}+(n_{2}−1)d_{2}}} ⋯
d_{k}^{q^{(n_{1}d_{1}+···+n_{k−1}d_{k−1})}+···+q^{(n_{1}d_{1}+···+(n_{k}−1)d_{k})}}.

Moreover, the uniqueness of the exponents in T as a polynomial in q with integer coefficients 0 or 1 follows from the uniqueness of digits in the base-q representation of positive integers.

The two depictions of T in Proposition 23, parts (1) and (3), correspond to the left- and right-hand sides of the equation in Example 22 respectively.

3.2 Restricted Gaussian partitions

The definition and notation of splits can be applied to the regular Gaussian partitions associated with V (n, q). The subspace dimensions in a Gaussian partition T will be written in nonincreasing order, with or without exponents.

Definition 24 (Dimension-preserving split of Gaussian partition). Let T = f_{1}^{x_{1}} ⋯ f_{k}^{x_{k}} with f_{1} ≥ ⋯ ≥ f_{k} be a Gaussian partition, and suppose that f_{i} = a + b with a ≥ b ≥ 1 and i < k. Then the split (a, b) of the dimension f_{i} is called dimension-preserving provided that f_{i} > a ≥ b ≥ f_{i+1}. Splits of the last dimension, f_{k}, are always dimension-preserving. Simultaneous applications of the same dimension-preserving split (a, b) to several of the dimensions f_{i} are also considered to be dimension-preserving.

After applying a dimension-preserving split (a, b) to one of the dimensions f_{i} as above, we will replace the segment f_{i}^{x_{i}}f_{i+1}^{x_{i+1}} in T by f_{i}^{x_{i}−1}a^{1}b^{q^{a}}f_{i+1}^{x_{i+1}}. If x_{i} ≥ j, then j simultaneous applications of (a, b) to the f_{i}’s will result in the expression f_{i}^{x_{i}−j}a^{j}b^{jq^{a}}f_{i+1}^{x_{i+1}}, so that the nonincreasing order is preserved.

Definition 25 (Left/right dimensions). Let (a, b) be a split to be applied to a dimension f = a+b. Then a^{1} is called a left dimension and the dimensions b appearing in b^{q^{a}} are called right dimensions, even if a = b.

A restricted Gaussian partition T_{Γ} is just the type of a restricted subspace partition Γ. However, it is possible to describe a restricted Gaussian partition without any reference to a restricted subspace partition by applying the principles in Section 2.2.4.

Definition 26 (Restricted Gaussian partition, Spine, Spinelet). Let V = V (n, q) and T be a basic Gaussian partition of V, written

T = d_{1}^{1+q^{d_{1}}+···+q^{(n_{1}−1)d_{1}}}d_{2}^{q^{n_{1}d_{1}}+q^{n_{1}d_{1}+d_{2}}+···+q^{n_{1}d_{1}+(n_{2}−1)d_{2}}} ⋯
d_{k}^{q^{(n_{1}d_{1}+···+n_{k−1}d_{k−1})}+···+q^{(n_{1}d_{1}+···+(n_{k}−1)d_{k})}} (d_{1} > ⋯ > d_{k})

as in Proposition 23(3). The partition T and any regular Gaussian partition T′ obtained from T by dimension-preserving splits according to the following rules are called restricted Gaussian partitions of V:

1. A split (a, b) may only be applied to the dimension d_{i} in T if the exponent of d_{i} is not equal to 1.

2. At most N = q^{u} − 1 splits of the same type (a, b) may be applied simultaneously to repeated dimensions d_{i} in the basic partition T, where q^{u} is the unique largest power of q in the exponent of d_{i}. The linearly ordered collection of N Gaussian partitions obtained by applying (a, b) to the d_{i}’s 1 through N times is called the spine corresponding to the split (a, b).

3. At any regular Gaussian partition containing a power a^{k} of a left dimension a (where 1 ≤ k ≤ N) on a spine, we may apply a dimension-preserving split (c, d) up to k times to a, obtaining a linearly ordered collection of k Gaussian partitions called a spinelet corresponding to (c, d). Any subsequent linear side branch constructed by up to l repeated dimensionpreserving splits of the same kind to left dimensions c^{l} is also called a spinelet, and so on.

Examples of spines and spinelets can be seen in Example 28 as well as Figure 1. Note that we are allowed to completely dissolve powers of left dimensions on a spine or spinelet, whereas the number of applications of any one order-preserving split to the basic Gaussian partition T is bounded.

Remark 27.

1. The tree of various spines and spinelets emanating from T help us visualize the universe of possibilities for restricted Gaussian partitions T′ constructed from T and eventually help us explicitly count all such partitions.

2. Suppose T were written in the form

T = d_{1}^{1}d_{2}^{q^{d_{1}}}d_{3}^{q^{d_{1}+d_{2}}} ⋯ d_{k}^{q^{d_{1}+···+d_{k−1}}} (d_{1} ≥ ⋯ ≥ d_{k})

as in Proposition 23(1). Clearly, strictly smaller dimensions a and b cannot be placed in between the same two integers d_{i} and d_{i+1} in T by the dimension rule for subspaces, and splitting the unique subspace ⟨D_{i}⟩ of dimension d_{i} is prohibited by the unique ancestor rule. Hence, for any distinct dimension of T, with largest power of q in its exponent equal to q^{u}, we may only dissolve (refine) at most q^{u} − 1 copies of it.

3. Only one kind of dimension-preserving split (a, b) may be applied to a dimension d_{i} during a particular construction. If a different one, say (r, s) with a > r and b < s is attempted before or after (a, b), then the resulting order of dimensions would be d_{i}, r, s, a, b, d_{i+1} or d_{i}, a, b, r, s, d_{i+1}, violating the dimension rule.

4. By the same reasoning as above, only one type of dimension-preserving split may be applied to a subsequently formed left dimension.

5. None of the dimension-preserving splittings whose results are placed between powers of dimensions d_{i} and d_{i+1} ends in another basic Gaussian partition. However, if we were to split the last dimension d_{i} at the end of a spine (corresponding to the subspace ⟨D_{i}⟩) using an (N + 1)st split (a, b), then we would arrive at another basic Gaussian partition. This is stated as Proposition 29.

6. The construction process of any restricted Gaussian partition T′ is unique up to order. That is, it can be traced back to a unique basic Gaussian partition T, and there is only one possible set of splits that results in T′ (splits starting out of different places in T commute). This is stated as Proposition 30.

Example 28 (The Gaussian partitions of V (6, q)). The 11 = p(6) basic Gaussian partitions of V (6, q) are 6^{1}, 5^{1}1^{q^{5}}, 4^{1}1^{q^{4}+q^{5}}, 3^{1}1^{q^{3}+q^{4}+q^{5}}, 2^{1}1^{q^{2}+q^{3}+q^{4}+q^{5}}, 1^{1+q+q^{2}+q^{3}+q^{4}+q^{5}}, 4^{1}2^{q^{4}}, 3^{1+q^{3}}, 3^{1}2^{q^{3}}1^{q^{5}}, 2^{1+q^{2}+q^{4}}, and 2^{1+q^{2}}1^{q^{4}+q^{5}}. The first five cannot be split further without running into another basic partition, and the sixth one is already minimal. The non-basic restricted Gaussian partitions obtained from the remaining five are described in the following table:

Basic  Splits  Non-basics  Range
4^{1}2^{q^{4}}  (1, 1)  4^{1}2^{q^{4}−i}1^{i(q+1)}  1 ≤ i ≤ q^{4} − 1
3^{1+q^{3}}  (2, 1)  3^{1+q^{3}−i}2^{i}1^{iq^{2}}  1 ≤ i ≤ q^{3} − 1
3^{1+q^{3}}  (2, 1) and (1, 1) 3^{1+q^{3}−i}2^{i−j}1^{iq^{2}+j(q+1)} 1 ≤ i ≤ q^{3} − 1; 1 ≤ j ≤ i
3^{1}2^{q^{3}}1^{q^{5}}  (1, 1)  3^{1}2^{q^{3}−i}1^{i(q+1)+q^{5}}  1 ≤ i ≤ q^{3} − 1
2^{1+q^{2}+q^{4}}  (1, 1)  2^{1+q^{2}+q^{4}−i}1^{i(q+1)}  1 ≤ i ≤ q^{4} − 1
2^{1+q^{2}}1^{q^{4}+q^{5}}  (1, 1)  2^{1+q^{2}−i}1^{i(q+1)+q^{4}+q^{5}}  1 ≤ i ≤ q^{2} − 1

Consider the number of non-basic regular Gaussian partitions of V (6, q): there are

s(q) = ∑_{i=1}^{q^{3}−1} ∑_{j=0}^{i} 1 = ∑_{i=1}^{q^{3}−1}(i + 1) = \frac{(q^{3} − 1)q^{3}}{2} + (q^{3} − 1)

of them that are obtained from 3^{1+q^{3}}, and the total is

(q^{4} − 1) + s(q) + (q^{3} − 1) + (q^{4} − 1) + (q^{2} − 1),

a rational polynomial in q with root q = 1.

In this table, we can see the spines corresponding to the separate splits of types (1, 1) and (2, 1) as well as the spinelets resulting from (2, 1)’s followed by (1, 1)’s. See Figure 1, where the basic Gaussian partitions, spines, and spinelets for n = 6 are laid out in tree form.

Proposition 29. Let

T = d_{1}^{1+q^{d_{1}}+···+q^{(n_{1}−1)d_{1}}}d_{2}^{q^{n_{1}d_{1}}+q^{n_{1}d_{1}+d_{2}}+···+q^{n_{1}d_{1}+(n_{2}−1)d_{2}}} ⋯
d_{k}^{q^{(n_{1}d_{1}+···+n_{k−1}d_{k−1})}+···+q^{(n_{1}d_{1}+···+(n_{k}−1)d_{k})}},

with dimensions d_{1} > ⋯ > d_{k}, be a basic Gaussian partition. If (a, b) is a dimensionpreserving split with a + b = d_{i}, then neither the spine obtained by applying (a, b) to T simultaneously one through q^{n_{1}d_{1}+···+(n_{i}−1)d_{i}} − 1 times, nor the set of restricted Gaussian partitions obtained from the spine, contains a basic partition. However, with an additional application of the split (a, b) to the last partition on the spine, we obtain another basic Gaussian partition T′.

Proof. As long as the largest power of q in the exponent of d_{i} is partially decomposed, the Gaussian partition cannot be basic, because the exponent of d_{i} does not correctly reflect the Addition Property in Proposition 23. However, once the highest power of q in the exponent of d_{i} is completely dissolved, we do get a basic partition: this partition is

T′ = d_{1}^{1+q^{d_{1}}+···+q^{(n_{1}−1)d_{1}}} ⋯ d_{i}^{q^{(n_{1}d_{1}+···+n_{i−1}d_{i−1})}+···+q^{(n_{1}d_{1}+···+(n_{i}−2)d_{i})}}
a^{q^{(n_{1}d_{1}+···+(n_{i}−1)d_{i})}}b^{q^{(n_{1}d_{1}+···+(n_{i}−1)d_{i}+a)}}d_{i+1}^{q^{(n_{1}d_{1}+···+n_{i}d_{i})}+···} ⋯

PSfrag replacements

6^{1}
5^{1}1^{q5}
4^{1}1^{q4+q5}
3^{1}2^{q3} 1^{q5}
3^{1}1^{q3+q4+q5}
2^{1+q2} 1^{q4+q5}
2^{1}1^{q2+...+q5}

2^{q2} 1^{(q+1)+q4+q5}

1^{1+q+...+q5}

2^{2}1^{(q2−1)(q+1)+q4+q5}

3^{1}2^{q3−1}1^{(q+1)+q5} 3^{1}2^{1}1^{(q3−1)(q+1)+q5}

4^{1}2^{q4}

2^{1+q2+q4}
4^{1}2^{q4−1}1^{q+1}
2^{q2+q4} 1^{q+1}

4^{1}2^{1}1^{(q4−1)(q+1)} 2^{2+q2} 1^{(q4−1)(q+1)}

3^{1+q3}

3^{q3} 2^{1}1^{q2}

3^{q3} 1^{q2+(q+1)} 3^{q3−1}2^{2}1^{2q2}

3^{q3−1}2^{1}1^{2q2+(q+1)} 3^{q3−1}1^{2q2+2(q+1)} 3^{2}2^{q3−1}1^{(q3−1)q2}

3^{2}1^{(q3−1)q2+(q3−1)(q+1)} link between basic partitions

spines ;

spinelets

Figure 1: Basic Gaussian partitions, spines, and spinelets for n = 6

The exponents of a and b, as well as the expression q^{n_{1}d_{1}} in the exponent of d_{i+1}, conform to the addition property; note that a + b = d_{i}, and equalities in the expression a ≥ b ≥ d_{i+1} are allowed.

Proposition 30. A restricted Gaussian partition is uniquely defined by its basic ancestor and the set of splits applied to it.

Proof. This proof depends implicitly on the uniqueness of the base-q representation of positive integers. Every non-basic restricted Gaussian partition T′ starts from some basic Gaussian partition T by definition. It turns out that T can be uniquely reconstructed due to the structure of basic partitions described in Proposition 23: let

T = d_{1}^{1}d_{2}^{q^{d_{1}}}d_{3}^{q^{d_{1}+d_{2}}} ⋯ d_{k}^{q^{d_{1}+···+d_{k−1}}}.

The original dimensions d_{1} ≥ ⋯ ≥ d_{k} of T are all present in T′. In fact, if k ≥ 2, then d_{1} and d_{2} must be the leftmost two numbers in T′, when dimensions are written in nonincreasing order without exponents, because of Definition 26. If the total exponent of d_{2} is already q^{d_{1}}, then we factor out this power, and the next number to the right has to be d_{3} < d_{2}. If the total exponent exceeds q^{d_{1}}, then we understand that d_{3} = d_{2}, separate d_{2}^{q^{d_{1}}}, and check if the total exponent of d_{3} is q^{d_{1}+d_{2}}, etc. As soon as we hit an exponent of some d_{i} that falls short of the Addition Property in Proposition 23, the first split (a, b) applied to d_{i} can be identified by the first integer a < d_{i} to the right of the d_{i}’s. If a^{α} is the collection of all a’s in T′, then we can locate (d_{i} − a)^{αq^{a}} = b^{αq^{a}} somewhere to the right (and the next integer, if any, must be d_{i+1}). All subsequent splits in nested intervals, if any, can be put together in this fashion, from outside towards inside, owing to Definition 26. Then we start working on d_{i+1}, and so on, until all splits are repaired backwards and T is re-created.

3.3 Some preliminary counting

We will use the following lemma, which states Faulhaber’s formula [9] for the sums of consecutive powers.

Lemma 31 (Sums of Consecutive Powers [9]). Let N and m be any nonnegative integers. Then the familiar sum

θ_{m}(N) = ∑_{k=1}^{N} k^{m}

of the first N consecutive m-th powers of k is a rational polynomial in N, with θ_{m}(0) = 0 (when N = 0, the empty sum is equal to zero). An explicit formula for θ_{m}(N) can be given in terms of the Bernoulli numbers B_{k}:

θ_{m}(N) = \frac{1}{m + 1} ∑_{k=0}^{m} \binom{m + 1}{k}(−1)^{k}B_{k} N^{m+1−k}.  (3)

Corollary 32. Let N be a positive integer, and S(x) be any rational polynomial. Then the sum

U(N) = ∑_{k=1}^{N} S(k)

is a rational polynomial in N, with U(0) = 0.

Proof. Let S(x) = a_{0} + a_{1}x + ⋯ + a_{t}x^{t}, with a_{i} ∈ ℚ. Then, in the notation of Lemma 31, the sum

U(N) = a_{0} ∑_{k=1}^{N} 1 + a_{1} ∑_{k=1}^{N} k + ⋯ + a_{t} ∑_{k=1}^{N} k^{t} = a_{0}θ_{0}(N) + a_{1}θ_{1}(N) + ⋯ + a_{t}θ_{t}(N)

is a ℚ-linear combination of rational polynomials in N with N = 0 as a root.

Let N be an unspecified positive integer and k be a variable that may take on the integer values 1, 2, …, N. Recall that we denote the set {1, 2, …, k} by k. We define a sequence of multisets A_{0}(N), A_{1}(N), A_{2}(N), ... by the following recursive rule: we set A_{0}(N) = {N}, and replace each occurrence of an integer k in the set A_{i}(N) by all elements of the set k in A_{i+1}(N). Thus

A_{i+1}(N) = ⨄_{k=1}^{N} A_{i}(k),

where ⊎ denotes the multiset sum. The first few multisets in this sequence are

A_{0}(N) = {N}, A_{1}(N) = ⨄_{k=1}^{N} A_{0}(k) = N = {1, 2, …, N}, and

A_{2}(N) = ⨄_{k=1}^{N} A_{1}(k) = 1 ⊎ 2 ⊎ ⋯ ⊎ N = {1} ⊎ {1, 2} ⊎ ⋯ ⊎ {1, 2, …, N}.

Corollary 33. Let 1_{A_{i}(N)}(k) denote the multiplicity of the integer k in the multiset A_{i}(N). For i ≥ 0, let

S_{i}(N) = ∑_{k=1}^{N} k · 1_{A_{i}(N)}(k),

the sum of all elements of the multiset A_{i}(N) counted with multiplicities. Then (1) For each i ≥ 0, we have

S_{i+1}(N) = ∑_{k=1}^{N} S_{i}(k).

(2) For each i ≥ 0, the expression S_{i}(N) is a rational polynomial in N, with S_{i}(0) = 0.

Proof. Part (1) follows immediately from the definition of A_{i} as a sum of multisets and the additive property of the multiplicity function. For part (2), we note that S_{0}(N) = N = θ_{0}(N), and

S_{1}(N) = ∑_{k=1}^{N} k = ∑_{k=1}^{N} S_{0}(k) = θ_{1}(N).

By Corollary 32 and part (1), it is clear that each subsequent S_{i}(N) is a polynomial with the desired properties.

3.4 Adding up

Proposition 34. Let T be a basic Gaussian partition of V (n, q) given by

T = d_{1}^{1}d_{2}^{q^{d_{1}}}d_{3}^{q^{d_{1}+d_{2}}} ⋯ d_{k}^{q^{d_{1}+···+d_{k−1}}},

where d_{1} ≥ ⋯ ≥ d_{k} and d_{1} + … + d_{k} = n. Then the number of all restricted Gaussian partitions obtained from T is a rational polynomial in q. Moreover, q = 1 is a root of this polynomial.

Remark 35. The restricted Gaussian partitions obtained from T according to the rules in Section 3.2 are necessarily non-basic by Proposition 29.

Proof. In the special cases of a basic Gaussian partition T for which the only dimensionpreserving splits create other basic partitions, or where all d_{i} = 1, the polynomial in question is the zero polynomial. Henceforth, we assume that it is possible to obtain non-basic regular Gaussian partitions from T. Since sequences of splits are applied to one dimension d_{i} at a time, it suffices to show that the number of Gaussian partitions obtained from one d_{i} is a polynomial P_{i}(q) of the desired type. Again, we single out the cases where it is not possible to fit any splits to d_{i}, and declare that in these cases P_{i}(q) = 1. However, there will be at least one factor P_{i}(q) that is a rational polynomial with 1 as a root by our assumption. The total number for T will be the product P_{T} (q) of all P_{i}(q).

Thus, assume that the restricted Gaussian partitions obtained from T only contain changes to d_{i}, and that q^{u} is the largest power of q in the exponent of d_{i}. Let N = q^{u} − 1 and recall the notation of Corollary 33. Now, several different splits (a, b) may be allowed for d_{i} (i.e., we have a + b = d_{i} and d_{i} > a ≥ b ≥ d_{i+1}), but any given restricted Gaussian partition may contain only one of these, possibly applied several times (see Section 3.2). Simultaneous applications of a split (a, b) results in a total of N = S_{0}(N) possible Gaussian partitions on a spine, where the set of exponents of a is {1, 2, …, N} = A_{1}(N). If there are t_{0} = t_{0}(i) possible splits (a, b) of d_{i}, then there must be t_{0}S_{0}(N) Gaussian partitions that have exactly one more kind of split than T has in their construction, because spines are disjoint by Proposition 30.

For any one of the first splits (a, b) of d_{i}, let (c, d) be one of the next generation of splits (that is, c + d = a, and a > c ≥ d ≥ b). Then each a^{k} on the spine will generate a new set of exponents for c on a spinelet, namely, k = {1, 2, …, k}. The multiset A_{2}(N) will contain all exponents of c thus generated, and S_{1}(N) new Gaussian partitions that contain only (a, b) and (c, d) in their construction sequence (starting from T) will be created. If there are t_{1} = t_{1}(i) possible sets of back-to-back splits (a, b) and (c, d) applied to d_{i}, then the number of Gaussian partitions that are obtained from T by splitting d_{i} with only two kinds of new splits is t_{1}S_{1}(N), as once again Proposition 30 tells us that there cannot be any repetitions of Gaussian partitions when different sequences of splits are employed. We continue in this manner as far as possible.

If t_{r} = t_{r}(i) denotes the number of all distinct back-to-back split sequences of length r +1 applied to d_{i}, and if the maximum possible length of such sequences is m = m(i), then the total number of restricted Gaussian partitions that can be obtained from T by splitting only d_{i} is given by the rational polynomial

P_{i}(q) = t_{0}S_{0}(N) + ⋯ + t_{m−1}S_{m−1}(N),

which must have q = 1 as a root by Corollary 33. The product

P_{T} (q) = ∏_{i=1}^{k} P_{i}(q)

is hence the total number of restricted Gaussian partitions obtained from T, a rational polynomial with P_{T} (1) = 0. Note that the numbers u, N, m, and t_{1}, …, t_{m−1} depend on i, but we are suppressing references to i for simplicity of notation.

As an immediate corollary of Proposition 34, we obtain the proof of our main result. Proof of Theorem 1. The total number of basic Gaussian partitions is p(n), and each basic partition T produces P_{T} (q) non-basic restricted partitions. Then the total number of restricted Gaussian partitions of V (n, q) is given by

R(q) = p(n) + ∑_{T} P_{T} (q),

which is a rational polynomial in q with R(1) = p(n) + ∑_{T} 0 = p(n).

4 Acknowledgment

We thank the referee whose comments helped improve the presentation of this paper.

References

[1] F. Akman and P. Sissokho, The lattice of finite subspace partitions, Discrete Math. 312 (2012), 1487–1491.

[2] F. Akman and P. Sissokho, Gaussian partitions, Ramanujan J. 28 (2012), 125–138.

[3] J. André, Über nicht-Desarguessche Ebenen mit transitiver Translationsgruppe, Math. Z. 60 (1954), 156–186.

[4] R. Baer, Partitionen endlicher Gruppen, Math. Z. 75 (1960/61), 333–372.

[5] A. Beutelspacher, Partial spreads in finite projective spaces and partial designs, Math. Z. 145 (1975), 211–229.

[6] A. Beutelspacher, Partitions of finite vector spaces: an application of the Frobenius number in geometry, Arch. Math. 31 (1978), 202–208.

[7] T. Bu, Partitions of a vector space, Discrete Math. 31 (1980), 79–83.

[8] R. Bruck and R. Bose, The construction of translation planes from projective planes, J. Algebra 1 (1964), 85–102.

[9] J. Conway and R. Guy, The Book of Numbers, Springer, 1996, p. 107.

[10] D. Drake and J. Freeman, Partial t-spreads and group constructible (s, r, μ)-nets, J. Geom. 13 (1979), 211–216.

[11] J. Eisfeld, L. Storme, and P. Sziklai, On the spectrum of the sizes of maximal partial line spreads in P G(2n, q), n ≥ 3, Des. Codes Cryptogr. 36 (2005), 101–110.

[12] S. El-Zanati, H. Jordon, G. Seelinger, P. Sissokho, and L. Spence, The maximum size of a partial 3-spread in a finite vector space over GF(2), Des. Codes Cryptogr. 54 (2010), 101–107.

[13] S. El-Zanati, G. Seelinger, P. Sissokho, L. Spence, and C. Vanden Eynden, Partitions of finite vector spaces into subspaces, J. Combin. Des. 16 (2008), 329–341.

[14] O. Heden, A survey of the different types of vector space partitions, Disc. Math. Algo. Appl. 4 (2012), 1–14.

[15] O. Heden, A survey on perfect codes, Adv. Math. Commun. 2 (2008), 223–247.

[16] O. Heden, On the length of the tail of a vector space partition, Discrete Math. 309 (2009), 6169–6180.

[17] J. Lehmann and O. Heden, Some necessary conditions for vector space partitions, Discrete Math. 312 (2012), 351–361.

[18] O. Heden, J. Lehmann, E. Năstase, and P. Sissokho, The supertail of a subspace partition, Des. Codes Cryptogr. 69 (2013), 305–316.

[19] M. Herzog and J. Schönheim, Group partition, factorization and the vector covering problem, Canad. Math. Bull. 15 (1972), 207–214.

[20] S. Hong and A. Patel, A general class of maximal codes for computer applications, IEEE Trans. Comput. C-21 (1972), 1322–1331.

[21] R. Koetter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Infor. Theor. 54 (2008), 3579–3591.

[22] L. Lambert, Random network coding and designs over 𝔽_{q}, Master’s thesis Ghent University, Belgium, 2013.

[23] B. Lindström, Group partitions and mixed perfect codes, Canad. Math. Bull. 18 (1975), 57–60.

[24] G. Miller, Groups in which all operators are contained in a series of subgroups such that any two have only the identity in common, Bull. Amer. Math. Soc. 12 (1905– 1906), 446–449.

[25] G. Seelinger, P. Sissokho, L. Spence, and C. Vanden Eynden, Partitions of V (n, q) into 2-and s-dimensional subspaces, J. Combin. Des. 20 (2012), 467–482.

[26] S. Thomas, Designs over finite fields, Geom. Dedicata 24 (1987), 237–242.

[27] G. Zappa, Partitions and other coverings of finite groups, Illinois J. Math., 47 (2003), 571–580.

2010 Mathematics Subject Classification: Primary 05A17; Secondary 11P83, 51E20. Keywords: subspace partition, vector space partition, Gaussian partition, integer partition, q-analogue.

Received September 5 2014; revised versions received December 16 2014; July 15 2015. Published in Journal of Integer Sequences, July 16 2015.

Return to Journal of Integer Sequences home page.