Tables of subspace codes
Daniel Heinlein, Michael Kiermaier, Sascha Kurz, and Alfred Wassermann∗

arXiv:1601.02864v2 [math.CO] 12 Dec 2017

December 13, 2017

The main problem of subspace coding asks for the maximum possible cardinality of a
subspace code with minimum distance at least d over Fnq , where the dimensions of the
codewords, which are vector spaces, are contained in K ⊆ {0, 1, . . . , n}. In the special
case of K = {k} one speaks of constant dimension codes. Since this emerging field is very
prosperous on the one hand side and there are a lot of connections to classical objects from
Galois geometry it is a bit difficult to keep or to obtain an overview about the current state of
knowledge. To this end we have implemented an on-line database of the (at least to us) known
results at subspacecodes.uni-bayreuth.de. The aim of this technical report is to
provide a user guide how this technical tool can be used in research projects and to describe
the so far implemented theoretic and algorithmic knowledge.
Keywords: Galois geometry, subspace codes, partial spreads, constant dimension codes
MSC: 51E23; 05B40, 11T71, 94B25

1. Introduction
The seminal paper by Kötter and Kschischang [60] started the interest in subspace codes which are sets of
subspaces of the Fq -vector space Fnq . Two widely used distance measures for subspace codes (motivated by
an information-theoretic analysis of the Kötter-Kschischang-Silva model, see e.g. [77]) are the subspace
distance
dS (U, W ) := dim(U + W ) − dim(U ∩ W ) = 2 · dim(U + W ) − dim(U ) − dim(W )
and the injection distance
dI (U, W ) := max {dim(U ), dim(W )} − dim(U ∩ W ),
where U and W are subspaces of Fnq . The two metrics are equivalent, i.e., it is known that dI (U, W ) ≤
dS (U, W ) ≤ 2dI (U, W ). Here, we restrict ourselves to the subspace distance.
 
The set of all k-dimensional subspaces of an Fq -vector space V will be denoted by Vk q . For n =
dim(V ), its cardinality is given by the Gaussian binomial coefficient
( n
 
(q −1)(q n−1 −1)···(q n−k+1 −1)
n
if 0 ≤ k ≤ n;
(q k −1)(q k−1 −1)···(q−1)
=
k q
0
otherwise.
∗ All

authors are with the Department of Mathematics, Physics, and Computer Science, University of Bayreuth, Bayreuth,
GERMANY. email: firstname.lastname@uni-bayreuth.de
The work was supported by the ICT COST Action IC1104 and grants KU 2430/3-1, WA 1666/9-1 – “Integer Linear Programming
Models for Subspace Codes and Finite Geometry” – from the German Research Foundation.

1

A set C of subspaces of V is called a subspace code. The minimum distance of C is given by d =
min{dS (U, W ) | U, W ∈ C, U 6= W }. If the dimensions of the codewords, i.e., the elements of C are
contained in some set K ⊆ {1, . . . , n}, C is called an (n, #C, d; K)q subspace code. In the unrestricted
case K = {0, . . . , n}, also called mixed dimension case, we use the notation (n, #C, d)q subspace code.
In the other extreme case K = {k}, we use the notation (n, #C, d; k)q and call C a constant dimension
code.
For fixed ambient parameters q, n, K and d, the main problem of subspace coding asks for the
determination of the maximum possible size Aq (n, d; K) := M of an (n, M, ≥ d; K)q subspace code
and – as a refinement – the classification of all corresponding optimal codes up to isomorphism. Again, the
simplified notations Aq (n, d) and Aq (n, d; k) are used for the unrestricted case K = {0, . . . , n} and the
constant dimension case K = {k}, respectively. Note that in the latter case dS (U, W ) = 2 · dI (U, W ) ∈
2 · N is an even number.
In general, the exact determination of Aq (n, d; K) is a hard problem, both on the theoretic and the
algorithmic side. Therefore, lower and upper bounds on Aq (n, d; K) have been intensively studied in the
last years, see e.g. [20]. Since the underlying discrete structures arose under different names in different
fields of discrete mathematics, it is even more difficult to get an overview of the state of the art. For
example, geometers are interested in so-called partial (k − 1)-spreads of PG(n − 1, q). Following the
track of partial spreads, one can end up with orthogonal arrays or (s, r, µ)-nets. Furthermore, q-analogs
of Steiner systems provide optimal constant dimension codes. For some sets of parameters constant
dimension codes are in one-to-one correspondence with so-called vector space partitions.
The aim of this report is to describe the underlying theoretical base of an on-line database, found at
http://subspacecodes.uni-bayreuth.de
and maintained by the authors that tries to collect up-to-date information on the best lower and upper
bounds for subspace codes. Whenever the exact value Aq (n, d; K) could be determined, we ask for
a complete classification of all optimal codes up to isomorphism. Occasionally we list classifications
for non-maximum codes, too. Since the overall task is rather comprehensive, we start by focusing on
the special cases of constant dimension codes, Aq (n, d; k), and (unrestricted) subspace codes, Aq (n, d),
using the subspace distance as metric. For a more comprehensive survey on network coding we refer the
interested reader e.g. to [6]. For algorithmic aspects we refer the interested reader e.g. to [61].
The remaining part of this report is structured as follows. In Section 2 we outline how to use the tables.
Constant dimension codes (CDC) are treated in Section 3, where the currently implemented lower bounds,
constructions, and upper bounds are described in Subsection 3.1 and Subsection 3.2, respectively. Mixed
dimension codes (MDC) are treated in Section 4, where the implemented lower bounds, constructions,
and upper bounds are described in Subsection 4.1 and Subsection 4.2, respectively. The application
programming interface (API) is the topic of Section 5. Finally we draw a conclusion in Section 6 and list
some explicit tables on upper and lower bounds in an appendix.

2. How to use the tables
On the website the two special cases Aq (n, d; k) and Aq (n, d) can be accessed via the menu items CDC
(constant dimension code) and MDC (mixed dimension code), see Figure 1. Selecting the item Table
yields the rough data that we will outline in this section. Selecting the item Constraints yields
information about the so far implemented lower and upper bounds.

2.1. Constant dimension codes – CDC
For a constant dimension code the dimension n of the ambient space (first selection row) and the field size
q (second selection row) can be chosen. The current limits are 2 ≤ q ≤ 9 and 4 ≤ n ≤ 19 (resp. in the

2

large view 1 ≤ n ≤ 19). For each chosen pair of those parameters a table with the information on lower
and upper bounds on constant dimension codes over Fnq is displayed.

Figure 1: Tables of constant dimension codes
The rows of those tables are labeled by the minimum distance d = dS (?) and the columns are labeled
by the dimension k of the codewords. In the third selection row several views can be picked. The first three
options, short, normal, and large, specify the subset of possible values for the parameters d and k.
In the most extensive view large, k can take all integers between 0 and n. For d the integers between 1
and n are considered. As
• Aq (n, d; 0) = 1 for all 1 ≤ d ≤ n;
• Aq (n, d; k) = Aq (n, d; n − k);
• Aq (n, 2d0 + 1; k) = Aq (n, 2d0 + 2; k) for all d0 ∈ N;
one may assume 1 ≤ k ≤ bn/2c, 2 ≤ d ≤ n, and d ∈ 2N. These assumptions are implemented in the
view normal. However, some exact values of Aq (n, d; k) are rather easy to determine

3

• Aq (n, 2; k) =
of at least 2;

n

k q,

since any two different k-dimensional subspaces of Fnq have a subspace distance

• if d > 2k, then we can have at most one codeword, i.e., Aq (n, d; k) = 1.
Thus, we may assume 2 ≤ k ≤ bn/2c, 4 ≤ d ≤ 2k, and d ∈ 2N. These assumptions are implemented in
the view short. The standard selection is given by n = 4, q = 2 and the view short.
Given one of these three views, a table entry may consist of
• a range l–u: An example is given by the parameters q = 2, n = 7, d = 4, k = 3, where l = 333 and
u = 381. The meaning is that for the corresponding maximum cardinality of a constant dimension
code only the lower bound l and the upper bound u is known, i.e., 333 ≤ A2 (7, 4; 3) ≤ 381 in the
example.
• a bold number m: An example is given by the parameters q = 2, n = 10, d = 8, k = 4, where
m = 65. The meaning is that the corresponding maximum cardinality of a constant dimension code
is exactly determined, i.e., A2 (10, 8; 4) = 65 in the example.
• a bold number m with an asterisk and a number l in brackets: An example is given by the parameters
q = 2, n = 6, d = 4, k = 3, where m = 77 and l = 5. The meaning is that the corresponding
maximum cardinality of a constant dimension code is exactly determined and all optimal codes have
been classified up to isomorphism, i.e., A2 (6, 4; 3) = 77 and there are exactly 5 isomorphism types
in the example, see [51]. Another example is given for the parameters q = 2, n = 6, d = 4, and
k = 2, where there are exactly 131, 044 isomorphism types of constant dimension codes attaining
cardinality A2 (6, 4; 2) = 21, see [68].
• a bold number m with a lower bound ≥ l in brackets: An example is given by the parameters q = 2,
n = 13, d = 4, k = 3, where m = 1597245 and l = 512. The meaning is that the corresponding
maximum cardinality of a constant dimension code is exactly determined and there are at least l
isomorphism classes of optimal codes.
Each nontrivial table entry is clickable and then yields further information on several lower and upper
bounds, see Subsection 3.1 and Subsection 3.2 for the details.
In some cases, e.g., for the parameters q = 2, n = 6, d = 4, and k = 3, the corresponding codes are
also available for download using the button called “file”. The format of these codes is mostly GAP1 or
MAGMA2 .
Besides the views short, normal, and large for the selection of ranges for the parameters d and k,
there are some additional views. The views relative gap and ratio of bounds condense the
current lack of knowledge on the exact value of Aq (n, d; k) to a single number. For the view relative
gap this number is given by the formula
upper bound − lower bound
,
lower bound
i.e., we obtain a non-negative real number. While principally any number in R≥0 can be obtained, the
largest relative gap in our database is currently given by about 0.727 for the parameters q = 2, n = 19, d =
4, k = 9. A gap of 0.0 corresponds to the determination of the exact value Aq (n, d; k). The mentioned
formula is also displayed on the webpage, when you move your mouse over the word relative gap.
For the view ratio of bounds the corresponding number is given by the formula
lower bound
,
upper bound
1 http://www.gap-system.org
2 http://magma.maths.usyd.edu.au

4

which may take any real number in (0, 1]. The smallest ratio of bounds in our database is given by
about 0.579 for the same parameters as above. Clearly, the largest relative gap yields the smallest ratio
of bounds and vice versa as the function x 7→ x1 − 1 is strictly decreasing in (0, 1]. A ratio of bounds
of 1.0 corresponds to the determination of the exact value Aq (n, d; k). The mouse-over effect is also
implemented in that case.
The views density and realized density compare the Anticode bound, see (Theorem 3.33),
to the best known upper bound and best known lower bound, respectively, i.e.,
best known upper bound
best known lower bound
,
and
.
Anticode bound
Anticode bound
Hence, they are a measure how dense it is possible to fill the Grassmannian with codewords. Note that
in the case of Steiner Systems, both bounds, the density and the realized density, are one since
the size of a Steiner System is exactly the size of the Anticode bound.
Another type of view arose from some of the various constructions described in Subsection 3.1. They
are labeled as amount pending dots and amount lifted mrd and condense the strength of a
certain construction to a single number in R≥1 . This number is always given as the quotient between the
currently best known lower bound and the value obtained by the respective construction. Here, a value of
one means that the currently best known code can be obtained by the respective construction. A value
larger than 1 measures how much better a more tailored construction is for this specific set of parameters
compared to the respective general construction method. We remark that amount pending dots is
still experimental and in some cases there may still be better codes obtained from the underlying very
general construction technique, which has quite some degrees of freedom. With respect to upper bounds
the additional view amount mrd bound is introduced. Here the displayed single number is given by
the currently best known lower bound divided by the so-called MRD bound, see Subsection 3.2.3.
The view files is like the view short but the background gets a green color if there is a downloadable
file for these parameters.
2.1.1. Toplist
These statistics, see Figure 2, show how often a single constraint yields the best known bound for the
parameters 2 ≤ q ≤ 9, 4 ≤ n ≤ 19, 2 ≤ k ≤ bn/2c, and 4 ≤ d ≤ 2k, where d is even. For each set of
parameters in which a single constraint yields the best known value, it scores a point. This score is then
divided by the size of the set of parameters, i.e., all constant dimension code parameters in the database.
Constraints are grouped into two categories: lower and upper bounds and then ordered by their normalized
score. The special constraints that yield the exact code sizes appear in both categories and are denoted
with an asterisk (*).
Currently the lower bound with the highest score is the improved linkage construction, see
Theorem 3.18, and it yields the best known lower bound in 69.1% of the constant dimension code
parameters of the database.
The upper bound improved johnson has currently the highest score for upper bounds with 90.2%.
2.1.2. Views for single CDCs
Each constant dimension code entry provides multiple level of details which are also called views, see
Figure 3.
The view all shows all constraints.
The view short is the default and displays only the best instances for the same constraint but with
different parameters.

5

Figure 2: Toplist of constant dimension codes
The third view, dominance, performs like short but incorporates an additional filtering due to
known relationships between constraints. Hence, if a constraint is always worse than another constraint
that is present, it is omitted.
Currently dominance respects for the parameters of this database the following relations between
upper bounds:
sphere packing ≤ all subs
anticode ≤ sphere packing
anticode ≤ singleton
johnson 1 ≤ johnson 2
johnson 1 ≤ anticode
johnson 1 ≤ ilp 1
ilp 1 ≤ ilp 2
ilp 4 ≤ ilp 3
johnson 2 ≤ ilp 4

6

Ahlswede Aydinian ≤ johnson 1
Ahlswede Aydinian ≤ johnson 2
And between lower bounds:
sphere covering ≤ trivial 1
echelon ferrers ≤ lin poly
ef computation ≤ echelon ferrers
improved linkage ≤ linkage GLT
improved linkage ≤ linkage ST

Figure 3: Views of constant dimension code entries

7

2.2. Mixed dimension codes – MDC
For a subspace code with mixed dimensions the field size q (selection row number one) can be chosen.
The current limits are given by 2 ≤ q ≤ 9. For each chosen parameter a table with the information on
lower and upper bounds on Aq (n, d) over Fnq (n ≤ 19) is displayed, see Figure 4.

Figure 4: Tables of (mixed dimension) subspace codes
The rows of those tables are labeled by the distance d = dS (?) and the columns are label by the
dimension n of the ambient space Fnq . In the second selection row several views can be picked. The
view normal, c.f. Subsection 2.1, already incorporates the restriction to 1 ≤ d ≤ n ≤ 19. The views
relative gap and ratio of bounds condense the current lack of knowledge on the exact value
of Aq (n, d) to a single number. For the view relative gap this number is given by the formula
upper bound − lower bound
,
lower bound
i.e. we obtain a non-negative real number. While principally any number in R≥0 can be obtained, the largest
relative gap in our database is currently given by about 2.493 for the parameters q = 2, n = 19, d = 4. A

8

relative gap of 0.0 corresponds to the determination of the exact value Aq (n, d). The mentioned formula
is also displayed on the webpage, when you move your mouse over the word relative gap. For the
view ratio of bounds the corresponding number is given by the formula
lower bound
,
upper bound
which may take any real number in (0, 1]. The smallest ratio of bounds in our database is given by
about 0.29 for the same parameters as above. Clearly the largest relative gap yields the smallest ratio of
bounds and vice versa as the function x 7→ x1 − 1 is strictly decreasing in (0, 1]. A ratio of bounds of 1.0
corresponds to the determination of the exact value Aq (n, d). The mouse-over effect is also implemented
in that case.
The view files is like the view normal but the background gets a green color if there is a downloadable file for these parameters.
2.2.1. Toplist
These statistics show how often a single constraint yields the best known bound for the parameters
2 ≤ q ≤ 9, 4 ≤ n ≤ 19, and 1 ≤ d ≤ n. For each set of parameters in which a single constraint yields the
best known value, it scores a point. This score is then divided by the size of the set of parameters, i.e., all
mixed dimension code parameters in the database. Constraints are grouped into two categories: lower and
upper bounds and then ordered by their normalized score. The special constraints that yield the exact code
sizes appear in both categories and are denoted with an asterisk (*).
Currently the lower bound with the highest score is layer construction (Theorem 4.5) and it
yields the best known lower bound in 78.7% of the mixed dimension code parameters of the database.
The upper bound improved cdc upper bound (Theorem 4.14) has currently the highest score for
upper bounds with 73.1%, see Figure 5.
2.2.2. MDC table for arbitrary q
This table has the same layout as the other MDC tables. The benefit is that the optimal sizes for Aq (n, d) is
known for all q and n ≤ 5, as well as the number of isomorphism types in some of these cases. This table,
see Figure 6, show the sizes in terms of q-polynomials that may even be evaluated for specific q values by
entering them in the input box and pressing the “Compute” button or the “Enter” key. It is possible to leave
the input field blank to get the q-polynomials back or to enter non prime power, even negative, numbers.

3. Bounds for CDCs
For constant dimension codes much more bounds are known than for mixed dimension codes. We state
lower bounds, i.e., constructions, in Subsection 3.1 and upper bounds in Subsection 3.2.

3.1. Lower bounds and constructions for CDCs
Any subspace code is a set and hence its size is at least zero. This most trivial bound Aq (n, d; k) ≥
0 is trivial 1. Lifted MRD codes, see Subsection 3.1.1, are one type of building blocks of the
Echelon-Ferrers construction, see Subsection 3.1.2. The latter is a nice interplay between the subspace
distance, the rank distance and the Hamming distance. Another construction based on similar ideas is
the so-called Coset construction, see Subsection 3.1.3. The most effective general recursive construction
is the so-called linkage construction and its generalization, see Subsection 3.1.4. The expurgationaugmentation method, starting from a lifted MRD code and then adding and removing codewords, is

9

Figure 5: Toplist of (mixed dimension) subspace codes
briefly describe in Subsection 3.1.5. Constant dimension codes with prescribed automorphisms are the
topic of Subsection 3.1.6. Also the non-constructive lower bounds for classical codes in the Hamming
metric can be transferred, see Subsection 3.1.7. Last but not least, also geometrical ideas can be employed
in order to obtain good constructions for constant dimension codes, see Subsection 3.1.8.
3.1.1. Lifted MRD codes
For matrices A, B ∈ Fm×n
the rank distance is defined via dR (A, B) := rk(A − B). It is indeed a metric,
q
as observed in [29].
Theorem 3.1. (see [29]) Let m, n ≥ d be positive integers, q a prime power, and C ⊆ Fm×n
be a
q
max{n,m}·(min{n,m}−d+1)
rank-metric code with minimum rank distance d. Then, #C ≤ q
.
Codes attaining this upper bound are called maximum rank distance (MRD) codes. They exist for
all (suitable) choices of parameters. If m < d or n < d, then only #C = 1 is possible, which may be

10

Figure 6: Mixed dimension subspace codes for arbitrary q


summarized to the single upper bound #C ≤ q max{n,m}·(min{n,m}−d+1) . Using an m × m identity
matrix as a prefix one obtains the so-called lifted MRD codes.
Theorem 3.2. (see [77]) For positive integers k, d, n with k ≤ n, d ≤ 2 min{k, n − k}, and d ≡ 0
 q
(mod 2), the size of a lifted MRD code in Fnk with subspace distance d is given by
M (q, k, n, d) := q max{k,n−k}·(min{k,n−k}−d/2+1) .
If d > 2 min{k, n − k}, then we have M (q, k, n, d) = 1.
As MRD codes can be obtained from linearized polynomials, we have the very same bound implemented
as lin poly:
Theorem 3.3. (Linearized polynomials, see [60] and Section 3.1.1)
Aq (n, d; k) ≥ q (n−k)(k−d/2+1)
3.1.2. Echelon-Ferrers or multilevel construction
In [22] a generalization, the so-called multi-level construction, based on lifted MRD codes was presented.
Let 1 ≤ k ≤ n be integers and v ∈ Fn2 a binary vector of weight k. By EFq (v) we denote the set of
all k × n matrices over Fq that are in row-reduced echelon form, i.e., the Gaussian algorithm had been
applied, and the pivot columns coincide with the positions where v has a 1-entry.

11

Theorem 3.4. (see [22]) For integers k, n, δ with 1 ≤ k ≤ n and 1 ≤ δ ≤ min{k, n − k}, let B be a
binary constant weight code of length n, weight k, and minimum Hamming distance 2δ. For each b ∈ B
let Cb be a code in EFq (b) with minimum rank distance at least δ. Then, ∪b∈B Cb is a constant dimension
code of dimension k having a subspace distance of at least 2δ.
The code B is also called skeleton code. For Cb we have the following upper bound:
Theorem 3.5. (see [22]) Let F be the Ferrers diagram of EFq (v) and C ⊆ EFq (v) be a subspace code
having a subspace distance of at least 2δ, then
#C ≤ q min{νi : 0≤i≤δ−1} ,
where νi is the number of dots in F, which are neither contained in the first i rows nor contained in the
rightmost δ − 1 − i columns.
The authors of [22] conjecture that Theorem 3.5 is tight for all parameters q, F, and δ, which is still
unrebutted. Constructions settling the conjecture in several cases are given in [21].
There is one rather obvious skeleton code that needs to be considered. Taking binary vectors with k
consecutive ones we are in the classical MRD case. So, taking binary vectors vi , where the ones are located
in positions (i − 1)k + 1 to ik for all 1 ≤ i ≤ bn/kc, clearly gives a binary constant weight code of length
n, weight k, and minimum Hamming distance 2k.
Observation 3.6. (see e.g. [64]) For positive integers k, n with n > 2k and n 6≡ 0 (mod k), there exists
 q
a constant dimension code in Fnk with subspace distance 2k having cardinality
bn/kc−1

1+

X

q n−ik = 1 + q k+(n mod k) ·

i=1

q n−k−(n mod k) − 1
q n − q k+(n mod k) + q k − 1
=
.
qk − 1
qk − 1

The observation is implemented as multicomponent. We remark that a more general construction,
among similar lines and including explicit formulas for the respective cardinalities, has been presented in
[78]. This lower bound for partial spreads, i.e., d = 2k, is exactly the same as:
Theorem 3.7. (Partial spreads, see [26]) If d = 2k then:
Aq (n, d; k) ≥

q n − q k (q (n mod k) − 1) − 1
qk − 1

This lower bound is implemented as partial spread 3 and equals the size of the construction of
Beutelspacher, see [8].
We remark that the general Echelon-Ferrers or multilevel construction contains the mentioned observation as a very easy special case. However, our knowledge on the size of an MRD code over EFq (v) is still
very limited. As mentioned, there is an explicit conjecture, which so far is neither proven nor disproved.
Let the field size q, the constant dimension k, and the minimum subspace distance d be fix, in order to
ease the notation. By V we denote the set of binary vectors of weight k in {0, 1}n . Let c(v) denote the
maximum size of a known MRD code over EFq (v) matching distance d. The optimal Echelon-Ferrers
construction can be modeled as an ILP:
max

X

c(v) · xv

v∈Fn
2

∀a 6= b ∈ Fn2 : dH (a, b) < d

s. t.xa + xb ≤ 1

∀v ∈ Fn2 .

xv ∈ {0, 1}

12

This is implemented as echelon ferrers. However, the evaluation of this ILP is only feasible
for rather moderate sized parameters. More sophisticated algorithmic considerations, unfortunately still
unpublished, give bounds for the exact optimum of the Echelon-Ferrers construction, which is implemented
as ef computation. A greedy-type approach has been considered by Alexander Shishkin, see [74] and
also [75]. It is implemented as greedy multicomponent. (However, we have not checked that all
corresponding MRD codes for the involved Ferrers diagrams exist.) In [30, 31] the authors considered
block designs as skeleton codes.
By choosing some explicit skeleton code and constructing the corresponding MRD codes in EFq (v),
one can obtain explicit lower bounds:
Theorem 3.8 ([38, Example 59]). For q > 2:
Aq (10, 6, 5) ≥ q 15 + q 6 + 2q 2 + q + 1,
Aq (11, 6, 5) ≥ q 18 + q 9 + q 6 + q 4 + 4q 3 + 3q 2 ,
Aq (14, 6, 4) ≥ q 20 + q 14 + q 10 + q 9 + q 8 + 2(q 6 + q 5 + q 4 ) + q 3 + q 2 ,
Aq (14, 8, 5) ≥ q 18 + q 10 + q 3 + 1, and
Aq (15, 10, 6) ≥ q 18 + q 5 + 1
This is implemented as Gorla Ravagnani 2014.
The Echelon-Ferrers construction has even been fine-tuned to the so-called pending dots [23] implemented as pending dots, and the so-called pending blocks [76] constructions. Of course, these variants
have even more degrees of freedom, so that a general solution of the best codes within these classes of
constructions is out of sight.
Explicit series of constructions using pending dots are given by:
Theorem 3.9 ([23, Construction 1, see chapter IV, Theorem 16]).
Aq (n, 2(k − 1); k) ≥ q 2(n−k) + Aq (n − k, 2(k − 2), k − 1)
if q 2 + q + 1 ≥ s with s = n − 4 if n is odd and s = n − 3 else
This is implemented as construction 1.
Theorem 3.10 ([23, Construction 2, see chapter IV, Theorem 17]).
Aq (n, 4; 3) ≥ q 2(n−3) +

α
X

q 2(n−3−(q

2

+q+2)i)

i=1

if q 2 + q + 1 < s with s = n − 4 if n is odd and s = n − 3 else and α =

j

n−3

k

q 2 +q+2

This is implemented as construction 2.
Explicit series of constructions using pending blocks are given by:
2

Theorem 3.11 ([76, Construction A, see chapter III, Theorem 19, Corollary 20]). Let n ≥ k +3k−2
and
2
k2 +k−6
k2 +k−6
k2 +k−4
k2 +k−6
2
q + q + 1 ≥ `, where ` = n −
for odd n −
(or ` = n −
for even n −
).
2
2
2
2
Pk

k2 +k−6 
P
k−1
n−
2(n−
i)
2
i=j
Then Aq (n, 2k − 2; k) ≥ q 2(n−k) + j=3 q
+
.
2
q
This is implemented as construction ST A 1.
Theorem 3.12 ([76, Construction
B, see chapter IV, theorem 26, Corollary 27]). Let 
n ≥ 2k + 2. Then

Pb n−2
(q 2(k−2) −1)(q 2(n−ik−1) −1) (k−3)(n−ik−2)+4
(k−1)(n−ik)
k c−1
Aq (n, 4; k) ≥ i=1
q
+
q
.
(q 4 −1)2
This is implemented as construction ST B.

13

3.1.3. Coset construction
The so-called Coset construction, see [46], grounds, similar as the Echelon-Ferrers construction, on the
interplay between the subspace distance, the rank distance and the Hamming distance. Another way to
look at it is that it generalizes the construction from [23, Theorem 18], which yields A2 (8, 4; 4) ≥ 4797.
Implemented as construction 3, we have for general prime powers q:

Theorem 3.13 ([23, Construction 3, see chapter V, Theorem 18, Remark 6]). Aq (8, 4; 4) ≥ q 12 + 42 q (q 2 +
1)q 2 + 1
Even more than the Echelon-Ferrers construction, it is a rather general approach that restricts the
general optimization problem of determining the subspace codes with the maximum cardinality to the best
combination of some structured building blocks. Here the building blocks are even more sophisticated than
the MRD codes over EFq (v), so that in general only lower and upper bounds for their sizes are known.
Two explicit parameterized constructions are given by;

Theorem 3.14 ([46, Section V-A, Theorem 11]). For all q, we have Aq (8, 4; 4) ≥ q 12 + 42 q (q 2 +1)q 2 +1.
For each k ≥ 4 and arbitrary q we have Aq (3k − 3, 2k − 2; k) ≥ q 4k−6 +

q 2k−3 −q
q k−2 −1

− q + 1.

This is implemented as coset construction.
 ni 
Theorem 3.15 ([46, Theorem 9]). If Fkqi admit parallelisms, i.e., a partition into spreads, for i = 1, 2
ni

−1
then Aq (n1 + n2 , 4; k1 + k2 ) ≥ s1 · s2 · min{p1 , p2 } · m, where si = qqki −1
is the size of a spread and
ni
Fnq i 
[ k i ]q
pi = si is the size of a parallelism in ki for i = 1, 2, and m = dq max{k1 ,n2 −k2 }(min{k1 ,n2 −k2 }−1) e
is the size of an MRD code with shape k1 × (n2 − k2 ) and rank distance 2 over Fq .
Fn 
Unfortunately, the existence question for parallelisms in kq is still open in general. They are known to
exist for:

1. q = 2, k = 2 and n even;
2. k = 2, all q and n = 2m for m ≥ 2;
3. n = 4, k = 2, and q ≡ 2 (mod 3);
4. q = 2, k = 3, n = 6,
see e.g. [24]. All applicable parameter combinations for (n1 , k1 ) and (n2 , k2 ) are implemented as
coset construction parallelism part.
Based on a packing of a (6, 77, 4; 3) code into several subcodes with minimum subspace distance 6,
a construction for A2 (10, 4; 4) ≥ 4173 was obtained in [46, Theorem 13]. This is still the best known
code for these parameters and can be downloaded as a file. For q ≥ 3 it remains unknown whether a
similar construction can improve upon the best known construction obtained from the Echelon-Ferrers
construction.
3.1.4. Linkage constructions
A powerful construction to obtain large codes from a given code C is to append all possible choices of
an MRD code to the matrices in row-echelon form of the codewords of C. This resulting size of the
constructed code is the size of C times the size of the MRD code. This approach is called Construction D
in [76], see [76, Theorem 37] and also [36, Theorem 5.1].
Performing a tighter analysis of the occurring subspace distances one notices that one can add further
codewords from a code in a smaller ambient space to Construction D. This gives:

14

Theorem 3.16. (linkage by Silberstein and (Horlemann-)Trautmann, see [76, Corollary 39]) For 3k ≤ n
and k ≤ ∆ ≤ n we have:
Aq (n, d; k) ≥ q ∆(k−d/2+1) Aq (n − ∆, d; k) + Aq (∆, d; k)
This bound is implemented as linkage ST. Without the assumption 3k ≤ n, the same bound is
independently obtained in:
Theorem 3.17. (linkage by Gluesing-Luerssen and Troha [37, Theorem 2.3]) For k ≤ m ≤ n − k we
have:
l
m
Aq (n, d; k) ≥ Aq (m, d; k) · q (n−m)(k−d/2+1) + Aq (n − m, d; k)
We remark that for n < 3k better constructions are known, see e.g. [45, Footnote 2]. An improved
analysis of the involved distances yields:
Theorem 3.18. (improved linkage) For k ≤ m ≤ n − d/2 we have:
l
m
Aq (n, d; k) ≥ Aq (m, d; k) · q max{n−m,k}(min{n−m,k}−d/2+1) + Aq (n − m + k − d/2, d; k)
This bound is implemented as improved linkage. The description of the application of all three
constraints contains ∆ respective m in brackets.
3.1.5. The expurgation-augmentation method
The success of the Echelon–Ferrers and the coset construction is mainly given by the fact that lifted MRD
codes have a quite large cardinality, which is asymptotically optimal in a certain sense. While both two
methods try to append some additional subcodes, the linkage constructions employ the MRD codes in a
product type construction. Another approach is to start from a lifted MRD code, remove some codewords
in order to add more codewords again. This approach is coined expurgation-augmentation and invented by
Thomas Honold.
The starting point is possible a computer–free construction for the lower bound A2 (7, 4; 3) ≥ 329, see
[40], which was previously obtained by a computer search using prescribed automorphisms, see [11].
Successors are:
Theorem 3.19 ([51, Theorem 2]). Aq (6, 4; 3) ≥ q 6 + 2q 2 + 2q + 1 for 3 ≤ q
This is implemented as HonoldKiermaierKurz n6 d4 k3. Note that the right hand side in
Theorem 3.19 is larger for all q ≥ 3 than the right hand side in Theorem 3.30.
Theorem 3.20 ([49]). Aq (7, 4; 3) ≥ q 8 + q 5 + q 4 − q − 1
This is implemented as construction honold and superseded by construction HK15.
Theorem 3.21 ([50, Theorem 4]). A2 (7, 4; 3) ≥ 329, A3 (7, 4; 3) ≥ 6977, Aq (7, 4; 3) ≥ q 8 + q 5 + q 4 +
q2 − q
This is implemented as construction HK15.
While the sketched idea of the expurgation-augmentation method is rather general, several theoretical
insights are possible. Prescribing automorphisms in the constructions also helps to obtain optimization
problems that are more structured and computationally feasible. A whole theoretical framework is
introduced in [2]. As a purely analytical result we have:

15

 
Theorem 3.22 ([2, Main Theorem]). A2 (v, 4; 3) ≥ 22(v−3) + 98 v−3
2 2 for v ≡ 7 (mod 8)
 
81 v−3
2(v−3)
A2 (v, 4; 3) ≥ 2
+ 64 2 2 for v ≡ 3 (mod 8) and v ≥ 11
This is implemented as expurgation augmentation general.
Explicit computer calculations allow further improvements:
Theorem 3.23 ([2, Table 1]). A2 (7, 4; 3) ≥ 28 + 45,
A2 (8, 4; 3) ≥ 210 + 93,
A2 (9, 4; 3) ≥ 212 + 756,
A2 (10, 4; 3) ≥ 214 + 2540,
A2 (11, 4; 3) ≥ 216 + 13770,
A2 (12, 4; 3) ≥ 218 + 47523,
A2 (13, 4; 3) ≥ 220 + 239382,
A2 (14, 4; 3) ≥ 222 + 775813,
A2 (15, 4; 3) ≥ 224 + 3783708, and
A2 (16, 4; 3) ≥ 226 + 12499466
This is implemented as expurgation augmentation special cases.
3.1.6. Codes with prescribed automorphisms
The computational complexity of the general optimization problem for Aq (n, d; k) can be reduced if one
assumes that the desired constant dimension code C admits some automorphisms, see [61]. So, the idea
is to prescribe some subgroup G of the automorphism group. If G is cyclic, then some authors speak of
cyclic orbit codes, see e.g. [12, 35, 36, 55, 79]. For these objects one can utilize the theory of subspace
polynomials, see [7, 71], and Sidon spaces, see [72]. The Singer cycle is one prominent example since it
acts transitively on the one-dimensional subspaces of Fnq . We restate the computational results from [61]
for A2 (n, 4; 3):
n
6
7
8
9
10
11
12
13
14

k
3
3
3
3
3
3
3
3
3

l
1
2
5
11
21
39
77
141
255

# orbits
19
93
381
1542
6205
24893
99718
399165
1597245

# codewords
1 · 63 = 63
2 · 127 = 254
5 · 255 = 1275∗
11 · 511 = 5621∗
21 · 1023 = 21483∗
39 · 2047 = 79833∗
77 · 4095 = 315315∗
141 · 8191 = 1154931
255 · 16383 = 4177665

d
4
4
4
4
4
4
4
4
4

Here l denotes the number of chosen orbits from the total number of orbits. Those code sizes that were
the best known lower bound at that time are marked with an asterisk. We remark that the stated values
correspond to the optimal solutions of the corresponding ILP for 6 ≤ n ≤ 8. For n = 9 it was reported
that l = 12 might be possible, which would be larger than the best known code for A2 (9, 4; 3) ≥ 5986
found in [10]. Later on the following, partially weaker, results have been obtained using the normalizer of
the Singer cycle:
Theorem 3.24 ([5, Example 2.7 and 2.8]). A2 (n, 4; 3) ≥ n · (2n − 1) for 12 ≤ n ≤ 20,
A2 (8, 4; 3) ≥ 2 · (28 − 1),
A2 (9, 4; 3) ≥ 9 · (29 − 1),
A2 (13, 6; 4) ≥ 13 · (213 − 1), and
A2 (17, 6; 4) ≥ 17 · (217 − 1)

16

This is implemented as Bardestani Iranmanesh.
A slight variation of cyclic subspace codes was considered in [33, 39].
3.1.7. Transferred classical non-constructive lower bounds
The classical Gilbert-Varshamov lower bound, based on sphere coverings, has been transferred to constant
dimension codes:
Theorem 3.25. (Sphere covering, see [60])


 


(d/2−1)+1  
X
2
n
k
n−k
Aq (n, d; k) ≥
/
·
· qi 
k q
i
i
q
q
i=0
This lower bound is implemented as sphere covering.
A Graham-Sloane type bound was obtained in [80]:
Theorem 3.26. (Graham, Sloane, see [80])
Aq (n, d; k) ≥

(q − 1)

n
k q

(q n − 1)q n(d/2−2)

This lower bound is implemented as graham sloane. For minimum subspace distance d = 4 is
yields a strictly larger lower bound than Theorem 3.25.
3.1.8. Geometric constructions
Geometric concepts like the Segre variety and the Veronese variety where also used to obtain constructions
for constant dimension codes:
Theorem 3.27 ([13, Theorem 3.11]). If n ≥ 5 is odd, then
  r−j
Pn−2   Pr
Qn−1
2
Aq (2n, 4; n) ≥ q n −n + r=2 nr q j=2 (−1)(r−j) rj q ( 2 ) (q n(j−1) − 1) + i=1 (q i + 1) −
q
   (n−1)(n−2)
(n−1)(n−3) Q n−1
n(n−1)
2i−1
2
2
4
−q
q 2 − n1 q q
(q
−
1)
+ y(y − 1) + 1, using y := q n−2 + q n−4 +
i=1
· · · + q 3 + 1.
This is implemented as CossidentePavese14 theorem311.
Theorem 3.28 ([13, Theorem 3.8]). If n ≥ 4 is even, then
 
 X
r
r−j
(r−j) r
(−1)
q ( 2 ) (q n(j−1) − 1)
Aq (2n, 4; n) ≥ q
+
j q
q j=2
r=2


!
n
n
n
n−1
2
Y
n(n−1)
n(n−2) Y
2
+(q + 1) 
(q i + 1) − 2q 2 + q 4
(q 2i−1 − 1) − q · |G| + 2
−1 +1
1
1
2
q
q2
i=1
i=1
n2 −n

n−2
X

n
r

Qn/2−1
Qn/2−1
using |G| = 2 i=1 (q 2i +1)−2q (n(n−2)/4) if n/2 is odd and |G| = 2 i=1 (q 2i +1)−2q (n(n−2)/4) +
Q
n/4
q n(n−4)/8 i=1 (q 4i−2 − 1) if n/2 is even.
This is implemented as CossidentePavese14 theorem38.

17

Theorem 3.29 ([13, Theorem 4.3]). Aq (8, 4; 4) ≥ q 12 + q 2 (q 2 + 1)2 (q 2 + q + 1) + 1
This is implemented as CossidentePavese14 theorem43.
Theorem 3.30 ([14, Corollary 7.4]). Aq (6, 4; 3) ≥ q 3 (q 2 − 1)(q − 1)/3 + (q 2 + 1)(q 2 + q + 1)
This is implemented as CossidentePavese n6 d4 k3.

3.2. Upper bounds for CDCs
Surveys and partial comparisons of upper bounds for constant dimension codes can e.g. be found in
[4, 45, 58].
Assuming 0 ≤ k ≤ n we always have Aq (n, d; k) ≥ 1. Since we can take
  no more than all subspaces
of a given dimension, we obtain the trivial upper bound Aq (n, d; k) ≤ nk q which is implemented as
all subs. Transferred bounds from classical coding theory are stated in Subsection 3.2.1. Of special
importance is the Johnson bound, so that implications are treated in Subsection 3.2.2. In our description of
known constructions we have seen that the lifted MRD codes play a major role in many constructions. For
those codes tighter upper bounds are known, see Subsection 3.2.3. As the Johnson bound recurs back to
bounds for partial spreads we state the corresponding bounds in Subsection 3.2.4. Everything else that
does not fit into the previous categories is collected in Subsection 3.2.5.
Nevertheless there is a large variety of upper bounds for constant dimension codes, the picture for
the currently tightest known bounds is pretty clear. Besides the exact values A2 (6, 4; 3) = 77 and
A2 (8, 6; 4) = 257, obtained with integer linear programming techniques, see Subsection 3.2.5, all upper
bounds are given by formula (4), which refers to partial spreads. For partial spreads, Theorem 3.42 (the
construction for spreads), Theorem 3.54, Theorem 3.55, and Theorem 3.58 are sufficient. The latter three
results are implications of the Delsarte linear programming method for projective linear divisible codes
with respect to the Hamming metric.
3.2.1. Classical coding theory bounds
Theorem 3.31. (Singleton bound, see [60])


n − d/2 + 1
Aq (n, d; k) ≤
k − d/2 + 1 q
This upper bound is implemented as singleton.
Theorem 3.32. (Sphere packing bound, see [60])



 



b(d/2−1)/2c  
X
 n

2
k
n
−
k
i
Aq (n, d; k) ≤ 
/
·
· q 
k q
i q
i
q
i=0
This upper bound is implemented as sphere packing.
Theorem 3.33. (Anticode bound, see [26])
$  
 %
n
n − k + d/2 − 1
Aq (n, d; k) ≤
/
k q
d/2 − 1
q
This upper bound is implemented as anticode.
In 1962 Johnson obtained several bounds for constant weight codes, see [57]. All of them could be
transferred to constant dimension codes:

18

Theorem 3.34 ([81, Theorem 2]). Aq (n, d; k) ≤

j

(q k −q k−d/2 )(q n −1)
(q k −1)2 −(q n −1)(q k−d/2 −1)

k

if (q k − 1)2 − (q n −

1)(q k−d/2 − 1) > 0
This is implemented as XiaFuJohnson1. We remark that requested condition can be simplified
considerably, see [45] and also [32].
Proposition 3.35. For 0 ≤ k < v, the bound in Theorem 3.34 is applicable iff d = 2 min{k, v − k} and
k ≥ 1. Then, it is equivalent to
qv − 1
.
Aq (v, d; k) ≤ min{k,v−k}
q
−1
In other words, Theorem 3.34 is a, rather weak, bound for partial spreads obtained by dividing the
number of points of the ambient space by the number of points of the codewords.
Theorem 3.36. (Johnson bounds, see [26])
 n

(q − 1) · Aq (n − 1, d; k − 1)
Aq (n, d; k) ≤
qk − 1
and


Aq (n, d; k) ≤

(q n − 1) · Aq (n − 1, d; k)
q n−k − 1

(1)


(2)

These upper bounds are implemented asj johnson
1 and johnson 2, respectively. Note that for
k
v
d = 2k Inequality (1) gives Aq (v, 2k; k) ≤ qqk −1
since
we have Aq (v − 1, 2k; k − 1) = 1 by definition.
−1
j v
k
q −1
Similarly, for d = 2(v − k), Inequality (2) gives Aq (v, 2v − 2k; k) ≤ qv−k
. Some sources like [81,
−1
Theorem 3] list just Inequality 1 and omit Inequality 2. This goes in line with the treatment of the classical
Johnson type bound II for binary error-correcting codes, see e.g. [67, Theorem 4 on page 527], where the
other bound is formulated as Problem (2) on page 528 with the hint that ones should be replaced by zeros.
Analogously, we can consider orthogonal codes:
Proposition 3.37 ([45, Proposition 2], cf. [27, Section III, esp. Lemma 13]). Inequality (1) and Inequality (2) are equivalent using orthogonality.
3.2.2. Implications and generalizations of the Johnson bounds
The constraints of the binary linear program
X

max

xU

Fn
q
k

U ∈[

s. t.

]
X

 n
Fq
∀w ∈ {1, . . . , k − 1}
w
 n
F
∀A ∈ q ∀a ∈ {k + 1, . . . , n − 1}
a
 n
F
∀U ∈ q
k

xU ≤ Aq (n − w, d; k − w)

∀W ∈

U ≥W

X

xU ≤ Aq (a, d; k)

U ≤A

xU ∈ {0, 1}
can be combined to get:

19

[wn ]q
A (n − w, d; k − w) ∀w ∈ {1, . . . , k − d/2} ilp 1
[wk ]q q
[wn ]
ilp 2
Aq (n, d; k) ≤ k q ∀w ∈ {k − d/2 + 1, . . . , k − 1}
[w]q
[na]
Aq (n, d; k) ≤ n−kq ∀a ∈ {k + 1, . . . , k + d/2 − 1}
ilp 3
[a−k ]q
[na]
Aq (n, d; k) ≤ n−kq Aq (a, d; k) ∀a ∈ {k + d/2, . . . , n − 1}
ilp 4
[a−k ]q
Note that ilp 2 is ilp 1 using Aq (n − w, d; k − w) = 1 for w ∈ {k − d/2 + 1, . . . , k − 1}. The
same is true for ilp 3 and ilp 4 using Aq (a, d; k) = 1 for a ∈ {k + 1, . . . , k + d/2 − 1}. Also, note
that ilp 1 is for w = 1 johnson 1, ilp 2 is for w = k − d/2 + 1 anticode, and ilp 4 is for
a = n − 1 johnson 2. In general, all these upper bounds are obtained from iterative applications of the
Johnson bound from Theorem 3.36. As it turns out that this bound is one of the tightest known bounds,
we look at it in more detail. In the classical Johnson space the optimal combination of the corresponding
two inequalities in a recursive application is unclear, see e.g. [67, Research Problem 17.1]. For constant
dimension codes there is an easy criterion for the optimal choice:
Aq (n, d; k) ≤

Proposition 3.38 ([45, Proposition 3]). For k ≤ n/2 we have
 n
  n

q −1
q −1
Aq (n − 1, d; k − 1) ≤ n−k
Aq (n − 1, d; k) ,
qk − 1
q
−1
where equality holds iff n = 2k.
With this the following non-recursive upper bound can be obtained:
$
$
$ 0
% %%%
$
q n−1 − 1
q n +1 − 1
qn − 1
0
0
· k−1
· ··· ·
· Aq (n , d; d ) . . .
,
Aq (n, d; k) ≤
qk − 1
q
−1
q d0 +1 − 1

(3)

where d0 = d/2 and n0 = n − k + d0 , i.e., the unknown value on the right hand side corresponds to the
case of a partial spread. Some authors plug in Theorem 3.44 in order to obtain an explicit upper bound.
However, for partial spreads tighter bounds are available, see Subsection 3.2.4.
There is a recent improvement of Inequality (3) or Theorem 3.36. The idea behind Inequality (1) is that
we can recursively determine an upper bound Λ on the number
that can be incident with a
  of codewords

given point. With this the number of codewords is at most Λ n1 q / k1 q . If this number is not an integer it
can be rounded down. In that case it means that some points are not incident to Λ codewords. Consider the
multiset of points with multiplicity Λ minus the number of incidences with codewords. This multiset is
equivalent to a linear code over Fq , whose Hamming weights are divisible by q k−1 , see [59]. Actually,
this is a generalization of the concept of holes and linear projective divisible codes, see Subsection 3.2.4.
Theorem 3.39 ([59, Theorem 3 and Theorem 4]). Let
 
  $ n · A (n − 1, d; k − 1) %  
q
v
k
k
1 q
m=
· Aq (n − 1, d; k − 1) −
·
+
·δ
k 
1 q
1 q
1 q
1
q

for some δ ∈ N0 . If no q k−1 -divisible multiset of points in Fvq of cardinality m exists, then
$ n
%
1 q · Aq (n − 1, d; k − 1)
− δ − 1.
Aq (n, d; k) ≤
k
1 q

Moreover, there exists a q r -divisible multiset of points of cardinality n if and only if there are nonPr
i+1
negative integers a0 , . . . , ar with n = i=0 ai sqi,r , where sqi,r = q r−i · q q−1−1 .

20

This is implemented as improved johnson. The iterated version is given by:


( ( 0
)
)
 q n −1  q n−1 −1
q n +1 −1
Aq (n, d; k) ≤
...
...
Aq (n0 , d; d0 )
 q k −1  q k−1 −1
q d0+1 −1
0
d +1

k−2











k−1

,

(4)

k

n   o
where d0 = d/2, n0 = v − k + d0 , and a/ k1 q
:= b with maximal b ∈ N permitting a representation
k
k
i+1
of a − b · 1 q as non-negative integer combination of the summands q k−1−i · q q−1−1 for 0 ≤ i ≤ k − 1.3
3.2.3. MRD bound
Since the size of the lifted MRD code, see Theorem 3.1, is quite competitive, it is interesting to compare
the best known constructions with this very general explicit construction. Even more, lifted MRD codes
are the basis for more involved constructions, see Subsection 3.1.2. From this point of view it is very
interesting that an upper bound for the cardinality of constant dimension codes containing the lifted MRD
code (of shape k × (n − k) and rank distance d/2) can be stated:
Theorem 3.40. (see [20, Theorem 10 and 11]) Let C be a constant dimension code with given parameters
q, n, d, and k that contains a lifted MRD code. Then:
• if d = 2(k − 1) and k ≥ 3 then |C| ≤ q 2(n−k) + Aq (n − k, 2(k − 2); k − 1);

 qn −qn−2k
• if d = 2k then |C| ≤ q (n−2k)(k+1) + n−2k
+ Aq (n − 2k, 2k; 2k).
k
q q 2k −q k
Theorem 3.41 ([42, Proposition 1]). For 2 ≤ d/2 ≤ k ≤ v − k let C be a (v, #C, d; k)q CDC that
contains an LMRD code.
If k < d ≤ 2/3 · v we have
#C ≤ q (v−k)(k−d/2+1) + Aq (v − k, 2(d − k); d/2).

If additionally d = 2k, r ≡ v mod k, 0 ≤ r < k, and 1r q < k, then the right hand side is equal to
Aq (v, d; k) and achievable in all cases.
If (n, d, k) ∈ {(6 + 3l, 4 + 2l, 3 + l), (6l, 4l, 3l) | l ≥ 1}, then there is a CDC containing an LMRD
with these parameters whose cardinality achieves the bound.
If k < d and v < 3d/2 we have
#C ≤ q (v−k)(k−d/2+1) + 1
and this cardinality is achieved.
If d ≤ k < 3d/2 we have
#C ≤ q (v−k)(k−d/2+1) + Aq (v − k, 3d − 2k; d)

 



v−k
k
k − d/2
+
q (k−d+1)(v−k−d/2) /
.
d/2 q d − 1 q
d/2 − 1 q
n 
  o

9
an example we consider A2 (9; 6; 4) ≤
A (8, 6; 3)/ 41 q
= 17374
using A2 (8, 6; 3) = 34. We have
1 q 2
15
4
4
 17374 
=
1158,
17374
−
1158
·
15
=
4,
17374
−
1157
·
15
=
19,
and
17374
−
1156
· 15 = 34. Since 4 and 19 cannot
15
be written as a non-negative linear combination of 8, 12, 14, and 15, but 34 = 14 + 12 + 8, we have A2 (9; 6; 4) ≤ 1156,
which improves upon the iterative Johnson bound by two. We remark that [59] contains an easy and fast algorithm to check the
presentability as non-negative integer combination as specified above.

3 As

21

3.2.4. Bounds for partial spreads
Partial spreads attain the maximum possible subspace distance d = 2k for constant dimension codes with
codewords of dimension k. So, it does not surprise that good bounds are known for this special case.
In this context it makes sense to write n = tk + r, where 0 ≤ r < k. The cases r = 0 and r = 1 are
completely resolved:
Theorem 3.42. ([73]; see also [3], [17, p. 29], Result 2.1 in [8]) Fnq contains a k-spread if and only if k
divides n, where we assume 1 ≤ k ≤ n and k, n ∈ N.
The corresponding exact value is implemented as upper bound spread.
Theorem 3.43. ([8]; see also [48] for the special case q = 2) For positive integers 1 ≤ k ≤ n be positive
n
n−1
n
k+1
−q
−1
+q k −1
integers with n ≡ 1 (mod k) we have Aq (n, 2k; k) = qqk −1
.
−q+1 = q· q qk −1
−q+1 = q −qqk −1
The corresponding exact value is implemented as upper bound partial spread 2.
 
 
n
−1
Since Fnq contains n1 q = qq−1
points and each k-dimensional codeword contains k1 q =
we have:
j n k
−1
Theorem 3.44. Aq (n, 2k; k) ≤ qqk −1

q k −1
q−1

point,

This is implemented as spread bound and is equivalent to Theorem 3.34. It is tight if and only if
r = 0, where it then matches Theorem 3.42.
j n k
−1
Theorem 3.45 ([26]). d = 2k ∧ k - n ⇒ Aq (n, d; k) ≤ qqk −1
−1
This is implemented as partial spread 5. We remark that tighter bounds are known if either r > 1
or q > 2, i.e., it is tight for (r, q) = (1, 2), where
Theorem 3.43. Given the trivial upper bound
j it matches
k
n

−1
of Theorem 3.44, one defines Aq (n, 2k; k) = qqk −1
− σ, where σ is called the deficiency. In these terms,
we have σ = 0 iff r = 0 and σ = q − 1 if r = 1.

For q = 2 and k = 3, then requiring r ∈ {0, 1, 2}, the value of A2 (n, 6; 3) can be determined exactly:
Theorem 3.46. (see [19]) For each integer m ≥ 2 we have
(a) A2 (3m, 6; 3) =

23m −1
;
7

(b) A2 (3m + 1, 6; 3) =

23m+1 −9
;
7

(c) A2 (3m + 2, 6; 3) =

23m+2 −18
.
7

The corresponding upper bound is implemented as partial spread 1. We remark that it is sufficient
to construct a code matching A2 (8, 6; 3) = 34, which was found by a computer search in [19], to conclude
3m+2
A2 (3m + 2, 6; 3) = 2 7 −18 for all m ≥ 2, since σ is a non-increasing function in n, see [54, Lemma 4].
The other cases are special instances of r = 0 and r = 1.
For r = 2 there are the following results:
Theorem 3.47. (Theorem 4.3 in [64]) For each pair of integers t ≥ 1 and k ≥ 4 we have A2 (k(t + 1) +
k(t+1)+2
−3·2k −1
2, 2k; k) = 2
.
2k −1
The corresponding upper bound is implemented as partial spread kurz q2.
Lemma 3.48. (Lemma 4.6 in [64]) For integers t ≥ 1 and k ≥ 4 we have A3 (k(t + 1) + 2, 2k; k) ≤
2
3k(t+1)+2 −32
− 3 2+1 .
3k −1

22

The corresponding upper bound is implemented as partial spread kurz q3. We remark that the
above two theorems are improvements over the following general upper bound from 1979:
Theorem 3.49. (Corollary 8 in [18]) If n = k(t + 1) + r with 0 < r < k, then
Aq (n, 2k; k) ≤

t
X

q ik+r − bθc − 1 = q r ·

i=0

where 2θ =

p

q k(t+1) − 1
− bθc − 1,
qk − 1

1 + 4q k (q k − q r ) − (2q k − 2q r + 1).

We remark that this theorem is also restated as Theorem 13 in [20] and as Theorem 44 in [25] with the
small typo of not rounding down θ (Ω in their notation). The corresponding upper bound is implemented
as DrakeFreeman.
Not too long ago it was shown that the construction of Observation 3.6, i.e., the Echelon-Ferrers
construction with a skeleton code of disjoint codewords, gives the optimal value if r ≥ 1 and k is large
enough, i.e., it is asymptotically optimal:

Theorem 3.50. (see [70, Theorem 5]) For r = n (mod k) and k > 1r q we have:
Aq (n, 2k; k) =

q n − q k+r
+1
qk − 1

This
  is implemented as partial spread NS. Theorem 3.47 is just a very special case of it. If
k = 1r q similar techniques allow to obtain an improved upper bound:

Theorem 3.51 ([70, Lemma 10 and Remark 11]). r = n (mod k) ∧ k = 1r q < n ∧ r ≥ 2 ⇒
Aq (n, 2k; k) ≤ lq k + min{q, dq r /2e} where l =

q n−k −q r
q k −1

This is implemented as partial spread NS upper bound.
Invoking a result on the existence of so-called vector space partitions, see [41, Theorem 1], the authors
of [70] obtained the following tightenings:

n
t+r
Theorem 3.52 ([69, Theorem 6]). r = n (mod t) ∧ 2 ≤ r < t ≤ 1r q ⇒ Aq (n, 2t; t) ≤ q q−q
+ qr −
t −1
(
q q 2 | (q − 1)(t − 2) + c1
(q − 1)(t − 2) − c1 + c2 where c1 = 2 − t (mod q) and c2 =
such that
0 else
−q + 1 ≤ −c1 + c2 ≤ q
This is implemented as partial spread NS 2 Theorem6.
Theorem 3.53 ([69, Theorem 7]). r = n (mod t) ∧ 2 ≤ r < t ≤ 2r − 1 ⇒ A2 (n, 2t; t) ≤
(
1 4|t−1
2r − t + 1 + c where c =
0 else

2n −2t+r
2t −1

+

This is implemented as partial spread NS 2 Theorem7.
The four bounds mentioned above can possibly be best explained using the concept of divisible codes,
see [54]. To this end we call a point that is not contained in any k-dimensional codeword of a partial spread
a hole. Taking the set of holes as columns of a generator matrix, we obtain a projective linear code over Fq
of dimension k and the number of holes as length. It turns out that the Hamming weights of all codewords

23

are divisible by q k−1 , see [54, Theorem 8]. Those codes have to satisfy the famous MacWilliams Identities,
see [66],


n−i 
i 
X
X
n−j
n−j
Aj = q k−i ·
A⊥
for 0 ≤ i ≤ n,
(5)
j
i
n
−
i
j=0
j=0
where Aj denotes the number of codewords of Hamming weight j and A⊥
j denotes the number of
⊥
codewords of weight j of the dual code. We have A0 = A⊥
=
1
and
A
=
0.
Projectivity of the code is
0
1
equivalent to A⊥
=
0
and
the
divisibility
conditions
says
that
A
=
0
for
all
indices
j that are not divisible
j
2
by q k−1 . Moreover, the residual codes are q k−2 -divisible, which can be applied recursively. The first two
MacWilliams Identities can be used to exclude the existence of quite some lengths of projective linear
q r -divisible codes. Translated back to partial spreads, this gives:

Theorem 3.54 ([62, 65]). r ≥ 1 ∧ k ≥ 2 ∧ z, u ≥ 0 ∧ t = 1r q + 1 − z + u > r ⇒ Aq (n, 2t; t) ≤
lq t + 1 + z(q − 1) where l =

q n−t −q r
q t −1

and n = kt + r

This is implemented as partial spread kurz16 28 and contains Theorem 3.50 and Theorem 3.51
as a special case. If the infeasibility of the first three MacWilliams Identities is used, one obtains:
Theorem 3.55 ([65, Theorem 2.10],[54, Theorem 10]). r ≥ 1 ∧ t ≥ 2 ∧ y ≥ max{r, 2} ∧ z ≥

v−k
−q r
0 ∧ r, t, y, z ∈ Z ∧ u = q y ∧ y ≤ k ∧ k = 1r q + 1 − z > r ∧ v = kt + r ∧ l = q qk −1
⇒ Aq (v, 2k; k) ≤
p
k
lq + du − 1/2 − 1/2 1 + 4u(u − (z + y − 1)(q − 1) − 1)e Note that the description contains the value
of y in brackets
This is implemented as partial spread HKK16 T10. Setting y = k in Theorem 3.55 gives
Theorem 3.49, i.e., the classical result of Drake and Freeman. We remark that the combination of
Theorem 3.54 and Theorem 3.55 is at least as tight as the combination of Theorem 3.50, Theorem 3.51,
Theorem 3.52 and Theorem 3.53 and in several cases the first mentioned two theorems are strictly tighter.
This statement was numerically verified for all 2 ≤ q ≤ 9, 1 ≤ n, k ≤ 100 in [54]. There is also a
conceptual reason: The result of Heden on the existence of vector space partitions, see [41, Theorem 1],
can be improved by using the implications of the first three MacWilliams Identities for divisible codes, see
[54, Theorem 12], which classifies the possible length n of q r -divisible codes for all n ≤ rq r+1 . For larger
n some partial numerical results are obtained in [44]. A further, more direct, improvement of Heden’s
result can be found in [63].
Excluding codes by showing that the Equation (5) has no non-negative real solution is known as the
linear programming method, which generally works for association schemes, see [15]. For Theorem 3.54
and Theorem 3.55 only a first few equations are taken into account and an analytical solution was obtained.
For the first four equations of (5) the following analytical criterion was stated in [54]:
P
Lemma 3.56. Let C be ∆-divisible over Fq of cardinality n > 0 and t ∈ Z. Then i≥1 ∆2 (i − t)(i − t −
1) · (g1 · i + g0 ) · Ai∆ + qhx = n(q − 1)(n − t∆)(n − (t + 1)∆)g2 , where g1 = ∆qh, g0 = −n(q − 1)g2 ,
g2 = h − (2∆qt + ∆q − 2nq + 2n + q − 2) and h = ∆2 q 2 t2 + ∆2 q 2 t − 2∆nq 2 t − ∆nq 2 + 2∆nqt +
n2 q 2 + ∆nq − 2n2 q + n2 + nq − n.
Corollary 3.57. If there exists t ∈ Z, using the notation of Lemma 3.56, with n/∆ ∈
/ [t, t+1], h ≥ 0, and
g2 < 0, then there is no ∆-divisible set over Fq of cardinality n.
Numerically evaluating this criterion or numerically solving the corresponding linear programs, and
taking into account that the deficiency σ is non-increasing in n, gives:
Theorem 3.58 ([62, 65]). A2 (4k + 3, 8; 4) ≤ 24 l + 4, where l =
6

A2 (6k + 4, 12; 6) ≤ 2 l + 8, where l =

26k−2 −24
26 −1

and k ≥ 2,

24

24k−1 −23
24 −1

and k ≥ 2,

26k−1 −25
and k ≥ 2,
26 −1
34k−1 −33
4
3, 8; 4) ≤ 3 l + 14, where l = 34 −1 and k ≥ 2,
5k−2
−35
3, 10; 5) ≤ 35 l + 13, where l = 3 33 −1
and k ≥ 2,
35k−1 −34
5
4, 10; 5) ≤ 3 l + 44, where l = 35 −1 and k ≥ 2,
6k−2
−34
4, 12; 6) ≤ 36 l + 41, where l = 3 36 −1
and k ≥ 2,
36k−1 −35
6
5, 12; 6) ≤ 3 l + 133, where l = 36 −1 and k ≥ 2,
7k−3
−34
4, 14; 7) ≤ 37 l + 40, where l = 3 37 −1
and k ≥ 2,
45k−2 −43
5
3, 10; 5) ≤ 4 l + 32, where l = 45 −1 and k ≥ 2,
6k−3
−43
and k ≥ 2,
3, 12; 6) ≤ 46 l + 30, where l = 4 46 −1
46k−1 −45
6
5, 12; 6) ≤ 4 l + 548, where l = 46 −1 and k ≥ 2,
7k−3
−44
4, 14; 7) ≤ 47 l + 128, where l = 4 47 −1
and k ≥ 2,
55k−3 −52
5
2, 10; 5) ≤ 5 l + 7, where l = 55 −1 and k ≥ 2,
5k−1
−54
and k ≥ 2,
4, 10; 5) ≤ 55 l + 329, where l = 5 55 −1
5k−1
7
−72
5
4, 10; 5) ≤ 7 l + 1246, where l = 75 −1 and k ≥ 2,
4k−1
−83
3, 8; 4) ≤ 84 l + 264, where l = 8 84 −1
and k ≥ 2,
85k−3 −82
5
2, 10; 5) ≤ 8 l + 25, where l = 85 −1 and k ≥ 2,
6k−4
−82
and k ≥ 2,
2, 12; 6) ≤ 86 l + 21, where l = 8 86 −1
93k−1 −92
3
2, 6; 3) ≤ 9 l + 41, where l = 93 −1 and k ≥ 2, and
5k−2
−93
3, 10; 5) ≤ 95 l + 365, where l = 9 95 −1
and k ≥ 2

A2 (6k + 5, 12; 6) ≤ 26 l + 18, where l =
A3 (4k +
A3 (5k +
A3 (5k +
A3 (6k +
A3 (6k +
A3 (7k +
A4 (5k +
A4 (6k +
A4 (6k +
A4 (7k +
A5 (5k +
A5 (5k +
A7 (5k +
A8 (4k +
A8 (5k +
A8 (6k +
A9 (3k +
A9 (5k +

This is implemented as partial spread kurz16 additional. We remark that we are not
aware of a set of parameters, where considering more than four equations from (5) yields an improvement.
3.2.5. Further upper bounds
Theorem 3.59. (see [1, Theorem 3]) For 0 ≤ t < r ≤ k, k − t ≤ m ≤ v, and t ≤ v − m we have:
n
k q Aq (m, 2r − 2t; k − t)
Aq (n, 2r; k) ≤ Pt
  n−m
i(m+i−k) m
i=0 q
k−i q
i
q
Note that the description of the application of the constraint contains t, m, and an optional o, indicating
the application on the parameters of the orthogonal code, in brackets. This bound is implemented as
Ahlswede Aydinian. We remark that there are typos in the formulation in [1, 58]. The corrected
stated version can also be found in [45]. The authors of [1] have observed that Theorem 3.59 contains
Theorem 3.36, i.e., the Johnson bound, as a special case. In [45] it was numerically checked that
Theorem 3.59 does not give strictly tighter bounds than Theorem 3.36 for all 2 ≤ q ≤ 9, 4 ≤ v ≤ 100,
and 4 ≤ d ≤ 2k ≤ v.
The Delsarte linear programming bound for the q-Johnson scheme, which is an association scheme, was
obtained in [16]. However, numerical computations indicate that it is not better than the Anticode bound,
see [4]. In [82] it was shown that the Anticode bound is implied by the Delsarte linear programming bound.
In [4] it was shown that a semidefinite programming formulation, that is equivalent to the Delsarte linear
programming bound, implies the Anticode bound of Theorem 3.33, the sphere-packing of Theorem 3.32,
the weak Johnson bound of Theorem 3.34, and the Johnson bound of Theorem 3.36 (without rounding).
This makes perfectly sense, since Theorem 3.32 and Theorem 3.34 are implied by Theorem 3.33 and

25

the iteration of Theorem 3.36 without rounding gives exactly Theorem 3.33. Using Maple and exact
arithmetic, we have checked that for all 2 ≤ q ≤ 9, 4 ≤ n ≤ 19, 2 ≤ k ≤ n/2, 4 ≤ d ≤ 2k the optimal
value of the Delsarte linear programming bound is indeed the Anticode bound. Given the result from [82]
it remains to construct a feasible solution of the Delsarte linear programming formulation whose target
value equals the Anticode bound. Such a feasible solution can also be constructed recursively. To this end,
let x0 , . . . , xk−1 denote a primal solution for the parameters of Aq (n − 1, d, k − 1), then z0 , . . . , zk is a
   
feasible solution for the parameters of Aq (n, d, k) setting zi = xi · k1 q k−i
1 q for all 0 ≤ i ≤ k − 1 and
n n−k+d/2−1
zk = k q /
− z0 − · · · − zk−1 . For the mentioned parameter space this conjectured primal
d/2−1
q

solution is feasible with the Anticode bound as target value. Due to the property of the symmetry group of
(Fnq , dS ), i.e., two-point homogeneous, the symmetry reduced version of the semidefinite programming
formulation of the maximum clique problem formulation collapses the Delsarte linear programming bound
for the q-Johnson scheme.
Another rather general technique to obtain upper bounds for the maximum cliques size of a graph is to
p-ranks, see e.g. [56, Lemma 1.3].
Lemma 3.60. Let G be a graph with adjacency matrix A and Y be a clique of G, then

rankp (A) + 1
if p divides |Y | − 1,
|Y | ≤
rankp (A)
otherwise.
Some numerical experiments suggest that the resulting upper bounds are rather weak, e.g., A2 (4, 4; 2) ≤
5, A2 (5, 4; 2) ≤ 19, A2 (6, 4; 2) ≤ 49, A2 (6, 4; 3) ≤ 223, and A2 (6, 6; 3) ≤ 19.
We close this section by upper bounds obtained from tailored integer linear programming computations.
The five optimal isomorphism types for A2 (6, 4; 3) = 77 have been determined in [51]. The upper bound
A2 (8, 6; 4) ≤ 272 was obtained in [47] and is implemented as special case 2 8 6 4. A little later
the exact value A2 (8, 6; 4) = 257 and its two optimal isomorphism types were determined, see [43].

4. Bounds for MDCs
For mixed dimension subspace codes the choice between the subspace distance dS and the injection
distance dI really makes a difference. Here we consider the subspace distance only. Subsection 4.1 is
devoted to constructions and upper bounds are presented in Subsection 4.2. In general, mixed dimension
subspace codes have obtained much less attention than constant dimension codes. Obtaining bounds seems
to be more challenging. For surveys we refer e.g. to [4, 53, 58].

4.1. Lower bounds and constructions
Of course the empty set is a mixed dimension code for any dimension and subspace distance. Aq (n, d) ≥ 0
is implemented as trivial 2. If d ≤ 2n and n ≥ 1, then {h0i, Fnq } is a mixed dimension codes, so
that Aq (n, d) ≥ 2. This is implemented as trivial 4. We structure the following lower bounds and
constructions into nonrecursive, see Subsection 4.1.1, and recursive lower bounds, see Subsection 4.1.2.
Some constraints leading to exact values are also collected in Subsection 4.3.
4.1.1. Nonrecursive lower bounds
The Echelon-Ferrers construction also works for mixed dimension codes, see e.g. [22, 38]. Also the
stated ILP formulation directly transfers, which is implemented as echelon ferrers. A more sophisticated search for the optimal construction within this setting is implemented as ef computation, cf.
Subsection 3.1.2.

26

Similar to the sphere covering bound for constant dimension codes in Theorem 3.25, there exists a
version for mixed dimension codes.:
Theorem 4.1 ([26, Theorem 9]).
Pn

Aq (n, d) ≥

Pn

n
n
j=0 k q j q
Pn Pd−1 Pj n k n−k i(j−i)
k=0
j=0
i=0 k q i q j−i q q
k=0

   

This is implemented as gilbert varshamov.
Theorem 4.2 ([53, Theorem 3.3.ii]). Aq (v, v − 2) ≥ 2q k+1 + 1 for v = 2k + 1 ≥ 5
This is implemented as nodd deqnm2 l.
4.1.2. Recursive lower bounds
l
m
n+1−k
k
−2
Theorem 4.3 ([22]). maxnk=0 q qn+1+q
·
A
(n
+
1,
d
+
1;
k)
≤ Aq (n, d)
q
−1
This is implemented as cdc average argument.
Theorem 4.4. maxnk=0 Aq (n, d; k) ≤ Aq (n, d)
This is implemented as cdc lower bound.
Theorem 4.5 ([53, Lower bound of Theorem 2.5]).
Pv−dd/2e
2 + k=dd/2e Aq (v, 2dd/2e; k)

Pv

k=0∧k≡bv/2c (mod d)

Aq (v, 2dd/2e; k) ≤ Aq (v, d) ≤

This is implemented as improved cdc lower bound.
P
Theorem 4.6 ([53]). The bound is Aq (n, d) ≥ max{ k∈K Aq (n, d; k) | K ⊆ {0, . . . , n} : |k1 −
k2 | ≥P
d ∀k1 6= k2 ∈ K}. This is computed using dynamic programming and the function L(N ) :=
max{ k∈K Aq (n, d; k) | K ⊆ {0, . . . , N } : |k1 − k2 | ≥ d ∀k1 6= k2 ∈ K} = max{L(N − 1), L(N −
d) + Aq (n, d; N )} for all N = 0, . . . , n.
This is implemented as layer construction.

4.2. Implemented upper bounds
Quoting [4], bounds for mixed dimension codes are much harder to obtain than for constant dimension
codes, since, for example, the size of balls in this space depends not only on their radius, but also on
the dimension of their center. We structure the upper bound into nonrecursive, see Subsection 4.2.1, and
recursive bound, see Subsection 4.2.2. Some constraints leading to exact values are also collected in
Subsection 4.3.
4.2.1. Nonrecursive upper bounds
Theorem 4.7. If d = n then the whole vector space is the direct sum of each pair of codewords. If a code
had three codewords, then 2k = n which is impossible for n odd.
This is implemented as nodd deqn.
Theorem 4.8 ([53, Upper bound of Theorem 3.3.ii]). Aq (v, v − 2) ≤ 2q k+1 + 2 for v = 2k + 1 ≥ 5.

27

This is implemented as nodd deqnm2 u.
For the mixed dimension case the acting symmetry group is not 2-point homogeneous, so that the
semidefinite programming formulation of the maximum clique problem after symmetrization does not
collapse to a linear program. Numerical evaluations of this SLP are given by:
Theorem 4.9 ([4]). A2 (4, 3) ≤ 6, A2 (5, 3) ≤ 20, A2 (6, 3) ≤ 124, A2 (7, 3) ≤ 776, A2 (7, 5) ≤ 35,
A2 (8, 3) ≤ 9268, A2 (8, 5) ≤ 360, A2 (9, 3) ≤ 107419, A2 (9, 5) ≤ 2485, A2 (10, 3) ≤ 2532929,
A2 (10, 5) ≤ 49394, A2 (10, 7) ≤ 1223, A2 (11, 5) ≤ 660285, A2 (11, 7) ≤ 8990, A2 (12, 7) ≤ 323374,
A2 (12, 9) ≤ 4487, A2 (13, 7) ≤ 4691980, A2 (13, 9) ≤ 34306, A2 (14, 9) ≤ 2334086, A2 (14, 11) ≤
17159, A2 (15, 11) ≤ 134095, and A2 (16, 13) ≤ 67079.
This is implemented as semidefinite programming.
Theorem 4.10 ([53]). A2 (6, 3) ≤ 118 and A2 (7, 4) ≤ 407
This is implemented as special cases upper notderived.
Theorem 4.11. A subspace code is a subset of the subspaces of Fnq , i.e., Aq (n, d) ≤

Pn

n
k=0 k q .

 

This is implemented as trivial 3.
4.2.2. Recursive upper bounds
Pn
Theorem 4.12. Aq (n, d) ≤ k=0 Aq (n, d; k)
This is implemented as cdc upper bound.
The following approach generalizes the sphere-packing bound for constant dimension codes facing the
fact that the spheres have different sizes. To that end let B(V, e) denote the ball with center V and radius e.
Those balls around codewords are pairwise disjoint.
Theorem 4.13. [26, Theorem 10] Denoting the number of k-dimensional subspaces contained in B(V, e)
with dim(V ) = i by c(i, k, e), we have
min{k,i}

c(i, k, e) =

X
j=d i+k−e
e
2

  

i
n − i (i−j)(k−j)
q
.
j q k−j q

Thus, Aq (n, 2e + 1) is at most as large as the target value of:
max

n
X
ai

(6)

i=0

subject to ai ≤ Aq (n, 2e + 2; i)
 
n
X
n
c(i, k, e)·ai ≤
k q
i=0

∀0 ≤ i ≤ n

ai ∈ N

∀0 ≤ i ≤ n

∀0 ≤ k ≤ n

This is implemented as Etzion Vardy ilp.
[58, Theorem 10] refers to another LP upper bound by Ahlswede and Aydinian, see [1].
Pv
Theorem 4.14 ([53, Upper bound of Theorem 2.5]). k=0∧k≡bv/2c (mod d) Aq (v, 2dd/2e; k) ≤ Aq (v, d) ≤
Pv−dd/2e
2 + k=dd/2e Aq (v, 2dd/2e; k)

28

This is implemented as improved cdc upper bound.
Theorem 4.15. 2 - d ⇒ Aq (n, d) ≤ Aq (n, d − 1)
This is implemented as relax d. This innocent and trivial looking inequality produces the tightest
known upper bound in our database since e.g. Theorem 4.9 and Theorem 4.13 are not evaluated for all
parameters.

4.3. Further constraints which determine an exact value
Theorem 4.16 ([53, Theorem 3.4]). Aq (v, 2) =

P

0≤i≤v∧i≡k (mod 2)

v 
i q

This is implemented as d2.
Theorem 4.17 ([53, Theorem 3.1.ii]). Aq (v, v) = q k + 1 for v = 2k
This is implemented as neqdeven.
Theorem 4.18 ([53, Theorem 3.2.i]). Aq (v, v − 1) = q k + 1 for v = 2k ≥ 4
This is implemented as neven deqnm1.
Theorem 4.19 ([53, Theorem 3.2.ii]). Aq (v, v − 1) = q k+1 + 1 for v = 2k + 1 ≥ 5
This is implemented as nodd deqnm1.
Theorem 4.20 ([53, Theorem 3.3.ii]; see also [34] and footnote 44 in [53] referring to independent (still
unpublished) work of Cossidente, Pavese and Storme). Aq (5, 3) = 2q 3 + 2
This is implemented as n5 d3 CPS.
Theorem 4.21 ([53, Theorem 3.3.ii]). Aq (5, 3) = 2q 3 + 2 for all q and A2 (7, 5) = 34
This is implemented as nodd deqnm2 e. We remark that the 20 isomorphism types of all latter
optimal codes have been classified in [52].
Theorem 4.22. If the distance is 0 or 1 then the optimal subspace code consists of all subspaces of Fnq ,
Pn  
i.e., d ≤ 1 ⇒ Aq (n, d) = k=0 nk q .
This is implemented as trivial dle1.

5. Application programming interface
There is also an API available to access most data of the database. It is inspired by the REST (representational state transfer) style and only GET queries are supported. In order to access the data for the constant
dimension case with parameters q, n, d and k, you query the URL
http://subspacecodes.uni-bayreuth.de/api/q/n/d/k/
Similarly in the mixed dimension case, the URL is
http://subspacecodes.uni-bayreuth.de/api/q/n/d/
The result is a JSON file which contains a subset of the following attributes:

29

• request = contains your specified q, n, d and k
• {lower,upper} bound = lower or upper bound for the value Aq (n, d; k)
• comments = commentaries to this entry
• nondeduced = if the parameters are no parameters that are also viewable in the “short” mode, then
they are trivial or computed using other parameters. nondeduced lists these other parameters.
• {lower,equal,upper} bound constraints = list of tuples which contain name, parameter and value of
the applied constraints
• classified = boolean that is true if Aq (n, d; k) is classified up to isomorphism
• known codes = list of tuples of size, details, file (to enable automatic downloads) and nrisotypes (the
number of isomorphism types of this entry)
• liftedmrdsizebound = the bound for codes that contains the lifted MRD code as described in
Subsection 3.2.3
In order to download the codes, you have to use the attribute file above and the URL
http://subspacecodes.uni-bayreuth.de/codes/file
We want to remark that the API (as well as the whole homepage) is still in an early evolutionary phase and
therefore changes are likely to occur. As an example, the URL
http://subspacecodes.uni-bayreuth.de/api/2/6/4/3/
yields the output:
{”upper bound constraints”: [{”parameter”: ””, ”name”: ”all subs”, ”value”: 1395}, {”parameter”: ””, ”name”: ”singleton”, ”value”: 155}, {”parameter”: ”2”, ”name”: ”ilp 2”, ”value”: 93}, {”parameter”: ”4”, ”name”: ”ilp 3”, ”value”: 93},
{”parameter”: ””, ”name”: ”anticode”, ”value”: 93}, {”parameter”: ””, ”name”: ”linear programming bound”, ”value”: 93},
{”parameter”: ””, ”name”: ”sphere packing”, ”value”: 1395}, {”parameter”: ”1”, ”name”: ”ilp 1”, ”value”: 81}, {”parameter”:
”5”, ”name”: ”ilp 4”, ”value”: 81}, {”parameter”: ””, ”name”: ”johnson 1”, ”value”: 81}, {”parameter”: ””, ”name”: ”johnson 2”, ”value”: 81}, {”parameter”: ”0, 3”, ”name”: ”Ahlswede Aydinian”, ”value”: 1395}, {”parameter”: ”0, 4”, ”name”:
”Ahlswede Aydinian”, ”value”: 93}, {”parameter”: ”0, 5”, ”name”: ”Ahlswede Aydinian”, ”value”: 81}, {”parameter”:
”1, 2”, ”name”: ”Ahlswede Aydinian”, ”value”: 93}, {”parameter”: ”1, 3”, ”name”: ”Ahlswede Aydinian”, ”value”: 98},
{”parameter”: ”1, 4”, ”name”: ”Ahlswede Aydinian”, ”value”: 112}, {”parameter”: ”1, 5”, ”name”: ”Ahlswede Aydinian”,
”value”: 155}, {”parameter”: ”0, 3, o”, ”name”: ”Ahlswede Aydinian”, ”value”: 1395}, {”parameter”: ”0, 4, o”, ”name”:
”Ahlswede Aydinian”, ”value”: 93}, {”parameter”: ”0, 5, o”, ”name”: ”Ahlswede Aydinian”, ”value”: 81}, {”parameter”: ”1,
2, o”, ”name”: ”Ahlswede Aydinian”, ”value”: 93}, {”parameter”: ”1, 3, o”, ”name”: ”Ahlswede Aydinian”, ”value”: 98},
{”parameter”: ”1, 4, o”, ”name”: ”Ahlswede Aydinian”, ”value”: 112}, {”parameter”: ”1, 5, o”, ”name”: ”Ahlswede Aydinian”,
”value”: 155}, {”parameter”: ””, ”name”: ”improved johnson”, ”value”: 81}], ”known codes”: [{”nrisotypes”: ”5”, ”details”: ””, ”file”: ”code 2 6 4 3 optimal size 77.zip”, ”size”: 77}], ”upper bound”: 77, ”classified”: true, ”lower bound”: 77,
”lower bound constraints”: [{”parameter”: ””, ”name”: ”trivial 1”, ”value”: 0}, {”parameter”: ””, ”name”: ”lin poly”, ”value”:
64}, {”parameter”: ””, ”name”: ”sphere covering”, ”value”: 15}, {”parameter”: ””, ”name”: ”graham sloane”, ”value”:
23}, {”parameter”: ””, ”name”: ”construction 1”, ”value”: 71}, {”parameter”: ””, ”name”: ”multicomponent”, ”value”: 65},
{”parameter”: ””, ”name”: ”HonoldKiermaierKurz n6 d4 k3”, ”value”: 77}, {”parameter”: ”[(0, 1, 2), (0, 3, 4), (1, 3, 5), (2,
4, 5)]”, ”name”: ”ef computation”, ”value”: 71}, {”parameter”: ””, ”name”: ”CossidentePavese n6 d4 k3”, ”value”: 43},
{”parameter”: ”3”, ”name”: ”linkage GLT”, ”value”: 65}, {”parameter”: ”3”, ”name”: ”improved linkage”, ”value”: 65},
{”parameter”: ”4”, ”name”: ”improved linkage”, ”value”: 9}], ”request”: [2, 6, 4, 3], ”liftedmrdsizebound”: 71, ”comments”:
””, ”equal bound constraints”: []}

30

6. Conclusion
The collection of the known results on lower and upper bounds for subspace codes is an ongoing project.
So far we have merely implemented the tip of the iceberg of the available knowledge. Even for upper
bounds for constant dimension codes, which is the most advanced part of our summary, there are several
pieces of work left. We still hope that the emerging on-line data base and the accompanying user’s guide
is already valuable for researchers in the field at this stage. One yardstick for our knowledge is the
fraction between the best known lower bound and the best known upper bound for constant dimension
codes. To be able to state some parametrical results, we compare the size of the lifted MRD code with
the Singleton or theQAnticode bound
 as done in [45]. To this end we utilize
Qnthe so called q-Pochhammer
n−1
symbol (a; q)n := i=0 1 − aq i and its specialization (1/q; 1/q)n = i=1 1 − 1/q i .
Proposition 6.1. [45, Proposition 7] For k ≤ n − k the ratio of the size of an LMRD code divided by
the size of the Singleton bound converges for n → ∞ monotonically decreasing to (1/q; 1/q)k−d/2+1 ≥
(1/2; 1/2)∞ > 0.288788.
Proposition 6.2. [45, Proposition 8] For k ≤ n − k the ratio of the size of an LMRD code divided
(1/q;1/q)k
≥
by the size of the Anticode bound converges for n → ∞ monotonically decreasing to (1/q;1/q)
d/2−1
q
q−1 · (1/q; 1/q)k ≥ 2 · (1/2; 1/2)∞ > 0.577576.
The largest gap of this estimate is attained for d = 4 and k = bn/2c. We remark that for this special
case none of the mentioned upper bounds yields an asymptotic improvement over the Anticode bound and
none of the described constructions yields an asymptotic improvement over the LMRD code construction.
If k does not vary with n (or does increase very slowly), then the Anticode bound can be asymptotically be
attained by an optimal code, see [28, Theorem 4.1] and also [9].
For mixed dimension codes comparatively little is known and more research is sorely needed. If you
want to support us in our task, please let us know any known constructions, bounds or papers that we have
missed so far via daniel.heinlein@uni-bayreuth.de or the Contribute-button in the upper right corner of the
webpage subspacecodes.uni-bayreuth.de.
Tracing back results to their original source is a task on its own. We want to work on that issue more
intensively in the future. If you observe possible enhancements in that direction, please let us know.
Critique, suggestions for improvements and feature requests are also highly welcome.

7. Acknowledgement
The authors want to thank the contributors Alexander Shishkin, Ivan David Molina Naizir, and Francesco
Pavese.

References
[1] Rudolf Ahlswede and Harout Aydinian. On error control codes for random network coding. In
Network Coding, Theory, and Applications, 2009. NetCod’09. Workshop on, pages 68–73. IEEE,
2009.
[2] Jingmei Ai, Thomas Honold, and Haiteng Liu. The expurgation-augmentation method for constructing good plane subspace codes. arXiv preprint 1601.01502, 2016.
[3] Johannes André. Über nicht-desarguessche Ebenen mit transitiver Translationsgruppe. Mathematische Zeitschrift, 60(1):156–186, 1954.

31

[4] Christine Bachoc, Alberto Passuello, and Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 7(2):127–145, 2013.
[5] F. Bardestani and Ali Iranmanesh. Cyclic orbit codes with the normalizer of a Singer subgroup. J.
Sci. Islam. Repub. Iran, 26(1):49–55, 2015.
[6] Riccardo Bassoli, Hugo Marques, Jonathan Rodriguez, Kenneth W. Shum, and Rahim Tafazolli.
Network coding theory: A survey. Communications Surveys & Tutorials, IEEE, 15(4):1950–1978,
2013.
[7] Eli Ben-Sasson, Tuvi Etzion, Ariel Gabizon, and Netanel Raviv. Subspace polynomials and cyclic
subspace codes. IEEE Transactions on Information Theory, 62(3):1157–1165, 2016.
[8] Albrecht Beutelspacher. Partial spreads in finite projective spaces and partial designs. Mathematische
Zeitschrift, 145(3):211–229, 1975.
[9] Simon R Blackburn and Tuvi Etzion. The asymptotic behavior of grassmannian codes. IEEE
Transactions on Information Theory, 58(10):6605–6609, 2012.
[10] Michael Braun, Patric R. J. Östergård, and Alfred Wassermann. New lower bounds for binary
constant-dimension subspace codes. Experimental Mathematics, 0(0):1–5, 2016.
[11] Michael Braun and Jan Reichelt. q-analogs of packing designs. Journal of Combinatorial Designs,
22(7):306–321, 2014.
[12] Joan-Josep Climent, Verónica Requena, and Xaro Soler-Escrivà. A construction of orbit codes. In
International Castle Meeting on Coding Theory and Applications, pages 72–83. Springer, 2017.
[13] Antonio Cossidente and Francesco Pavese. Subspace codes in P G(2n − 1, q). Combinatorica, pages
1–23, 2016.
[14] Antonio Cossidente and Francesco Pavese. Veronese subspace codes. Des. Codes Cryptogr.,
81(3):445–457, 2016.
[15] Philippe Delsarte. An algebraic approach to the association schemes of coding theory. PhD thesis,
Philips Research Laboratories, 1973.
[16] Philippe Delsarte. Hahn polynomials, discrete harmonics, and t-designs. SIAM Journal on Applied
Mathematics, 34(1):157–166, 1978.
[17] P. Dembowski. Finite Geometries: Reprint of the 1968 Edition. Springer Science & Business Media,
2012.
[18] David A. Drake and J.W. Freeman. Partial t-spreads and group constructible (s, r, µ)-nets. Journal
of Geometry, 13(2):210–216, 1979.
[19] Saad El-Zanati, Heather Jordon, George F. Seelinger, Papa Sissokho, and Lawrence Spence. The
maximum size of a partial 3-spread in a finite vector space over GF (2). Designs, Codes and
Cryptography, 54(2):101–107, 2010.
[20] Tuvi Etzion. Problems on q-analogs in coding theory. arXiv preprint: 1305.6126, 37 pages, 2013.
[21] Tuvi Etzion, Elisa Gorla, Alberto Ravagnani, and Antonia Wachter-Zeh. Optimal Ferrers diagram
rank-metric codes. IEEE Trans. Inform. Theory, 62(4):1616–1630, 2016.

32

[22] Tuvi Etzion and Natalia Silberstein. Error-correcting codes in projective spaces via rank-metric codes
and Ferrers diagrams. IEEE Transactions on Information Theory, 55(7):2909–2919, 2009.
[23] Tuvi Etzion and Natalia Silberstein. Codes and designs related to lifted MRD codes. IEEE Trans.
Inform. Theory, 59(2):1004–1017, 2013.
[24] Tuvi Etzion and Leo Storme. Galois geometries and coding theory. Designs, Codes and Cryptography,
pages 1–40, 2015.
[25] Tuvi Etzion and Leo Storme. Galois geometries and coding theory. Designs, Codes and Cryptography,
78(1):311–350, to appear.
[26] Tuvi Etzion and Alexander Vardy. Error-correcting codes in projective space. IEEE Transactions on
Information Theory, 57(2):1165–1173, 2011.
[27] Tuvi Etzion and Alexander Vardy. Error-correcting codes in projective space. IEEE Transactions on
Information Theory, 57(2):1165–1173, 2011.
[28] P. Frankl and V. Rödl. Near perfect coverings in graphs and hypergraphs. European Journal of
Combinatorics, 6(4):317–326, 1985.
[29] Ernst M. Gabidulin. Theory of codes with maximum rank distance. Problemy Peredachi Informatsii,
21(1):3–16, 1985.
[30] Ernst M. Gabidulin and Nina I. Pilipchuk. New multicomponent network codes based on block
designs. In Proc. Int. Mathematical Conf.50 years of IITP, Moscow, 2011.
[31] Ernst M. Gabidulin and Nina I. Pilipchuk. Rank subcodes in multicomponent network coding.
Problems of Information Transmission, 49(1):40–53, 2013.
[32] Ernst M. Gabidulin and Nina I. Pilipchuk. New constructions of multicomponent codes. In International conference ACCT-2016, 2016.
[33] Ismael Gutierrez Garcia and Ivan Molina Naizir. On quasi-cyclic subspace codes. arXiv preprint
608.03215, 2016.
[34] Anirban Ghatak. Optimal binary (5, 3) projective space codes from maximal partial spreads. arXiv
preprint 1701.07245, 2017.
[35] Heide Gluesing-Luerssen, Katherine Morrison, and Carolyn Troha. On the cardinality and distance
of cyclic orbit codes based on stabilizer subfields. In 21st International Symposium on Mathematical
Theory of Networks and Systems, July 7-11, 2014. Groningen, The Netherlands, pages 1406–1408,
2014.
[36] Heide Gluesing-Luerssen, Katherine Morrison, and Carolyn Troha. Cyclic orbit codes and stabilizer
subfields. Advances in Mathematics of Communications, 9(2):177–197, 2015.
[37] Heide Gluesing-Luerssen and Carolyn Troha. Construction of subspace codes through linkage.
Advances in Mathematics of Communications, 10(3):525–540, 2016.
[38] Elisa Gorla and Alberto Ravagnani. Subspace codes from Ferrers diagrams. Journal of Algebra and
Its Applications, 16(7):23p., 2017. arXiv preprint 1405.2736.
[39] Ismael Gutierrez and Ivan Molina. Some constructions of cyclic and quasi-cyclic subspaces codes.
arXiv preprint 1504.04553, 2015.

33

[40] Liu Haiteng and Thomas Honold. Poster: A new approach to the main problem of subspace coding.
In Communications and Networking in China (CHINACOM), 2014 9th International Conference on,
pages 676–677. IEEE, 2014.
[41] Olof Heden. On the length of the tail of a vector space partition. Discrete Mathematics, 309(21):6169–
6180, 2009.
[42] Daniel Heinlein. LMRD bounds for constant dimension codes. in preparation, 2017.
[43] Daniel Heinlein, Thomas Honold, Michael Kiermaier, Sascha Kurz, and Alfred Wassermann. Classifying optimal binary subspace codes of length 8, constant dimension 4 and minimum distance 6.
arXiv preprint 1711.06624, 2017.
[44] Daniel Heinlein, Thomas Honold, Michael Kiermaier, Sascha Kurz, and Alfred Wassermann. Projective divisible binary codes. The Tenth International Workshop on Coding and Cryptography, 2017.
arXiv preprint 1703.08291.
[45] Daniel Heinlein and Sascha Kurz. Asymptotic bounds for the sizes of constant dimension codes
and an improved lower bound. In Ángela I. Barbero, Vitaly Skachek, and Øyvind Ytrehus, editors,
Coding Theory and Applications: 5th International Castle Meeting, ICMCTA 2017, Vihula, Estonia,
August 28-31, 2017, Proceedings, volume 10495 of Lecture Notes in Computer Science, pages
163–191, Cham, 2017. Springer International Publishing. arXiv preprint 1703.08712.
[46] Daniel Heinlein and Sascha Kurz. Coset construction for subspace codes. IEEE Transactions on
Information Theory, 63(12):7651–7660, 2017. arXiv preprint 1512.07634.
[47] Daniel Heinlein and Sascha Kurz. An upper bound for binary subspace codes of length 8, constant dimension 4 and minimum distance 6. The Tenth International Workshop on Coding and Cryptography,
2017. arXiv preprint 1705.03835.
[48] Se June Hong and A.M. Patel. A general class of maximal codes for computer applications. IEEE
Transactions on Computers, 100(12):1322–1331, 1972.
[49] Thomas Honold. Remarks on constant-dimension subspace codes, 2015. Talk at ALCOMA15 on
March 16, 2015.
[50] Thomas Honold and Michael Kiermaier. On putative q-analogues of the Fano plane and related
combinatorial structures. In Dynamical systems, number theory and applications, pages 141–175.
World Sci. Publ., Hackensack, NJ, 2016.
[51] Thomas Honold, Michael Kiermaier, and Sascha Kurz. Optimal binary subspace codes of length 6,
constant dimension 3 and minimum distance 4. Contemp. Math., 632:157–176, 2015.
[52] Thomas Honold, Michael Kiermaier, and Sascha Kurz. Classification of large partial plane spreads
in PG(6, 2) and related combinatorial objects. arXiv preprint 1606.07655, 2016.
[53] Thomas Honold, Michael Kiermaier, and Sascha Kurz. Constructions and bounds for mixeddimension subspace codes. Advances in Mathematics of Communications, 10(3):649–682, 2016.
[54] Thomas Honold, Michael Kiermaier, and Sascha Kurz. Partial spreads and vector space partitions.
arXiv preprint 1611.06328, 2016.
[55] Anna-Lena Horlemann-Trautmann, Felice Manganiello, Michael Braun, and Joachim Rosenthal.
Correction to cyclic orbit codes. IEEE Transactions on Information Theory, 63(11):7616–7616,
2017.

34

[56] Ferdinand Ihringer, Peter Sin, and Qing Xiang. New bounds for partial spreads of h(2d − 1, q 2 ) and
partial ovoids of the ree-tits octagon. arXiv preprint 1604.06172, 2016.
[57] Selmer Johnson. A new upper bound for error-correcting codes. IRE Transactions on Information
Theory, 8(3):203–207, 1962.
[58] Azadeh Khaleghi, Danilo Silva, and Frank R. Kschischang. Subspace codes. In IMA International
Conference on Cryptography and Coding, pages 1–21. Springer, 2009.
[59] Michael Kiermaier and Sascha Kurz. An improvement of the johnson bound for subspace codes.
arXiv preprint 1707.00650, 2017.
[60] Ralf Koetter and Frank R. Kschischang. Coding for errors and erasures in random network coding.
IEEE Transactions on Information Theory, 54(8):3579–3591, 2008.
[61] Axel Kohnert and Sascha Kurz. Construction of large constant dimension codes with a prescribed
minimum distance. In Mathematical methods in computer science, pages 31–42. Springer, 2008.
[62] Sascha Kurz. Upper bounds for partial spreads. arXiv preprint 1606.08581, 2016.
[63] Sascha Kurz. Heden’s bound on the tail of a vector space partition. arXiv preprint 1708.01113, 2017.
[64] Sascha Kurz. Improved upper bounds for partial spreads. Designs, Codes and Cryptography,
85(1):97–106, 2017.
[65] Sascha Kurz. Packing vector spaces into vector spaces. The Australasian Journal of Combinatorics,
68(1):122–130, 2017.
[66] Florence J. MacWilliams. A theorem on the distribution of weights in a systematic code. The Bell
System Technical Journal, 42(1):79–94, 1963.
[67] Florence J. MacWilliams and Neil J. A. Sloane. The theory of error-correcting codes. II. NorthHolland Publishing Co., Amsterdam-New York-Oxford, 1977. North-Holland Mathematical Library,
Vol. 16.
[68] Zlatka T. Mateva and Svetlana T. Topalova. Line spreads of PG(5, 2). J. Combin. Des., 17(1):90–102,
2009.
[69] Esmeralda Năstase and Papa Sissokho. The maximum size of a partial spread II: Upper bounds. The
maximum size of a partial spread II: Upper bounds. Discrete Math., 340:1481–1487, 2017.
[70] Esmeralda Năstase and Papa Sissokho. The maximum size of a partial spread in a finite projective
space. J. Combin. Theory Ser. A, 152:353–362, 2017.
[71] Kamil Otal and Ferruh Özbudak. Cyclic subspace codes via subspace polynomials. Designs, Codes
and Cryptography, 85(2):191–204, 2017.
[72] Ron M. Roth, Netanel Raviv, and Itzhak Tamo. Construction of Sidon spaces with applications to
coding. arXiv preprint 1705.04560, 2017.
[73] Beniamino Segre. Teoria di galois, fibrazioni proiettive e geometrie non desarguesiane. Annali di
Matematica Pura ed Applicata, 64(1):1–76, 1964.
[74] Alexander Shishkin. A combined method of constructing multicomponent network codes. MIPT
Proceedings, 6(2):188–194, 2014. (in Russian), https://mipt.ru//upload/medialibrary/4fe/188-194.pdf.

35

[75] Alexander Shishkin, Ernst M. Gabidulin, and Nina I. Pilipchuk. On cardinality of network subspace
codes. In Proceeding of the Fourteenth Int. Workshop on Algebraic and Combinatorial Coding
Theory (ACCT-XIV), volume 7, 2014.
[76] Natalia Silberstein and Anna-Lena Trautmann. Subspace codes based on graph matchings, Ferrers
diagrams, and pending blocks. IEEE Trans. Inform. Theory, 61(7):3937–3953, 2015.
[77] Danilo Silva, Frank R. Kschischang, and Ralf Kötter. A rank-metric approach to error control in
random network coding. IEEE Transactions on Information Theory, 54(9):3951–3967, 2008.
[78] Vitaly Skachek. Recursive code construction for random networks. IEEE transactions on Information
Theory, 56(3):1378–1382, 2010.
[79] Anna-Lena Trautmann, Felice Manganiello, Michael Braun, and Joachim Rosenthal. Cyclic orbit
codes. IEEE Transactions on Information Theory, 59(11):7386–7404, 2013.
[80] Shu-Tao Xia. A Graham-Sloane type construction of constant dimension codes. In Network Coding,
Theory and Applications, 2008. NetCod 2008. Fourth Workshop on, pages 1–5. IEEE, 2008.
[81] Shu-Tao Xia and Fang-Wei Fu. Johnson type bounds on constant dimension codes. Designs, Codes
and Cryptography, 50(2):163–172, 2009.
[82] Zong-Ying Zhang, Yong Jiang, and Shu-Tao Xia. On the linear programming bounds for constant
dimension codes. In Network Coding (NetCod), 2011 International Symposium on, pages 1–4. IEEE,
2011.

36

A. Tables for binary constant dimension codes
n=6
4
6
n=7
4
6
n=8
4
6
8
n=9
4
6
8
n = 10
4
6
8
10
n = 11
4
6
8
10
n = 12
4
6
8
10
12
n = 13
4
6
8
10
12

2
21 * (131044)
2
41
2
85

3
77 * (5)
9 * (1)

3
333 - 381
17 * (715)
3
1326 - 1493
34 (≥ 624)

4
4801 - 6477
257 * (2)
17
2
3
4
169
5986 - 6205
36945 - 50861
73
1033 - 1156
33
2
3
4
341
23870 - 24697
297829 - 423181
145
4173 - 4977
65
2
681

2
1365

2
2729

5
1178539 - 1678413
32890 - 38148
1025 - 1089
33
3
4
5
97526 - 99717
2383041 - 3370315
18728043 - 27943597
290
16669 - 19785
262996 - 328641
129 - 132
4097 - 4289
65
3
4
5
385515 - 398385
19664917 - 27222741
299769965 - 445207739
585
66680 - 79170
2104384 - 2613533
273
16401 - 17436
129
3
1597245 (≥ 512)
1169

4
157319501 - 217544769
266891 - 319449
545

6
1212491081 - 1816333805
16813481 - 21361665
262165 - 278785
4097 - 4225
65
5
6
4794061075 - 7192950693
38325127529 - 57884072859
16835124 - 20918754
269057345 - 339800773
65793 - 72131
2097225 - 2266956
257 - 259
16385 - 16769
129

B. Tables for ternary constant dimension codes
n=6
4
6
n=7
4
6
n=8
4
6
8
n=9
4
6
8

2
91
2
271
2
820

2
2458

3
754 - 784
28 * (7)
3
6978 - 7651
82
3
60259 - 68374
244 - 248

4
543142 - 627382
6562 - 6724
82
3
4
549667 - 620740
14581540 - 16821712
757
59077 - 61010
244

37

n = 10
4
6
8
10
n = 11
4
6
8
10

2
7381

3
5086963 - 5582305
2269

2
22141

3
45782686 - 50289022
6805 - 6809

4
394061122 - 458168194
532183 - 558739
730 - 732

5
3554720608 - 4104497728
14349660 - 14886440
59050 - 59536
244
4
5
10639658410 - 12361037515
286680643528 - 335382904522
4789648 - 5024299
387447165 - 409001563
2188 - 2201
531442 - 535824
730

C. Tables for quaternary constant dimension codes
n=6
4
6
n=7
4
6
n=8
4
6
8
n=9
4
6
8
n = 10
4
6
8
10
n = 11
4
6
8
10

2
273
2
1089
2
4369

3
4137 - 4225
65
3
66828 - 70993
257
3
1054373 - 1132817
1025 - 1033

4
16874321 - 18245201
65537 - 66049
257
2
3
4
17473
16945153 - 18179409
1078530305 - 1164549201
4161
1048641 - 1061929
1025
2
3
4
69905
273727489 - 290821441 69038576145 - 74754799185
16641
16781333 - 17110273
4097 - 4102
2
279617

3
4379639873 - 4654011921
66561 - 66569

5
1105471620389 - 1193662931025
1073745960 - 1088477225
1048577 - 1050625
1025
4
5
4418468947289 - 4783502911565
282679561437637 - 306494895880785
268501329 - 273715273
68719805936 - 70152169473
16385 - 16418
16777217 - 16818202
4097

D. Table for (unrestricted) binary subspace codes
q=2
1
2
3
4
5
6
7
8
9

1
2 * (1)

2
5 * (1)
3 * (1)

3
16 * (1)
8 * (1)
2 * (2)

4
67 * (1)
37 * (1)
5 * (3)
5 * (1)

5
374 * (1)
187 * (1)
18 * (24298)
9 * (7)
2 * (3)

38

6
2825 * (1)
1521 * (1)
108 - 118
77 * (4)
9 * (4)
9 * (1)

7
29212 * (1)
14606 * (1)
614 - 776
334 - 463
34 * (20)
17 * (928)
2 * (4)

8
417199 * (1)
222379 * (1)
5687 - 9268
4803 - 9635
263 - 327
257 - 327
17
17 * (7)

9
8283458 * (1)
4141729 * (1)
71427 - 107419
36947 - 114472
1994 - 2460
1034 - 2460
65 - 66
33
2 * (5)

E. Table for (unrestricted) ternary subspace codes
q=3
1
2
3
4
5
6
7
8
9

1
2 * (1)

2
6 * (1)
4 * (1)

3
28 * (1)
14 * (1)
2 * (2)

4
212 * (1)
132 * (1)
10
10 * (2)

5
2664 * (1)
1332 * (1)
56
28
2 * (3)

6
56632 * (1)
34608 * (1)
764 - 968
754 - 968
28
28 * (7)

7
2052656 * (1)
1026328 * (1)
13248 - 15846
6979 - 15846
163 - 164
82
2 * (4)

8
127902864 * (1)
77705744 * (1)
544431 - 765772
543144 - 765772
6574 - 7222
6562 - 7222
82
82

9
13721229088 * (1)
6860614544 * (1)
29137055 - 34889822
14581542 - 34889822
117621 - 123536
59078 - 123536
487 - 488
244
2 * (5)

F. Table for (unrestricted) quaternary subspace codes
q=4
1
2
3
4
5
6
7
8

1
2 * (1)

2
7 * (1)
5 * (1)

3
44 * (1)
22 * (1)
2 * (2)

4
529 * (1)
359 * (1)
17
17 * (3)

5
12278 * (1)
6139 * (1)
130
65
2 * (3)

39

6
565723 * (1)
379535 * (1)
4154 - 4773
4137 - 4773
65
65

7
51409856 * (1)
25704928 * (1)
131318 - 144166
66829 - 144166
513 - 514
257
2 * (4)

8
9371059621 * (1)
6269331761 * (1)
16881731 - 20519575
16874323 - 20519575
65557 - 68117
65537 - 68117
257
257

