# Bounds on Subspace Codes Based on Subspaces of Type(

Authors: You Gao; Gang Wang
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

The Sphere-packing bound, Singleton bound, Wang-Xing-Safavi-Naini bound, Johnson bound, and Gilbert-Varshamov bound on the subspace codesn
+
l
,
M
,
d
,
(
m
,
1
)
q based on subspaces of type (
m
,
1
) in singular linear space F
q
(
n
+
l
) over finite fields F
q are presented. Then, we prove that codes based on subspaces of type (
m
,
1
) in singular linear space attain the Wang-Xing-Safavi-Naini bound if and only if they are certain Steiner structures in F
q
(
n
+
l
).


---

## Body

## 1. Introduction

LetF
q be a finite field with q elements, where q is a power of a prime and F
q
(
n
) is the n-dimensional row vector space over F
q, where n is a positive integer. The set of all the subspaces with dimension k of F
q
(
n
) is called Grassmannian space over F
q, denoted by G
q
(
n
,
k
). The set of all the subspaces of F
q
(
n
), including {
0
} and F
q
(
n
), is called projective space of order n over F
q, denoted by P
q
(
n
). For any subspaces U and V in P
q
(
n
), define the distance function between U and V as
(1)
d
(
U
,
V
)
=
dim
⁡
U
+
dim
⁡
V
-
2
dim
⁡
(
U
∩
V
)
.
The function above is proved a metric (see [1]); thus, P
q
(
n
) can be regarded as a metric space.A nonempty collectionC of projective space P
q
(
n
) is called a subspace code and the subspaces in C are codewords of code C. The minimum distance of a subspace code C is
(2)
d
(
C
)
=
min
⁡
{
d
(
U
,
V
)
:
U
≠
V
,
U
,
V
∈
C
}
.
A subspace code C is denoted by (
n
,
M
,
d
)
q, if the size of codewords is M and the minimum distance of C is d. Furthermore, if C
⊆
G
q
(
n
,
k
), C is denoted by (
n
,
M
,
d
,
k
)
q.Subspace code plays an important role in random network coding (see [2, 3]). Koetter et al. [4, 5] defined an operator channel when they studied random network coding. Meanwhile, they showed that the errors and erasures could be corrected by a subspace code (
n
,
M
,
d
,
k
)
q over the operator channel if the sum of errors and erasures is less than d
/
2. These research results motivate many domestic and overseas scholars’ great interest in subspace codes (see [3–8]).Bounds on subspace codes and optimal subspace codes in projective space are considered in recent years. Koetter and Kschischang [1] provided Sphere-packing bound and Singleton bound on subspace codes in projective space, which are regarded as a counterpart of the classical Sphere-packing bound and Singleton bound [9]. Wang et al. [10] provided the Wang-Xing-Safavi-Naini bound on subspace codes in projective space. Etzion and Vardy [11] provided Johnson bound and Gilbert-Varshamov bound on subspace codes in projective space. Meanwhile, Xia and Fu [12] proved that codes in projective space achieved the Wang-Xing-Safavi-Naini bound if and only if they are certain Steiner structures [13, 14] in F
q
(
n
).In this paper, denote byM
(
m
,
1
;
n
+
l
,
n
) the collection of all the subspaces of type (
m
,
1
) in (
n
+
l
)-dimensional singular linear space F
q
(
n
+
l
), where 1
≤
m
≤
n
+
1. For any two subspaces U and V of type (
m
,
1
) in M
(
m
,
1
;
n
+
l
,
n
), the natural distance function between U and V in M
(
m
,
1
;
n
+
l
,
n
) is defined as
(3)
d
(
U
,
V
)
=
2
m
-
2
dim
⁡
(
U
∩
V
)
.
A nonempty collection C of M
(
m
,
1
;
n
+
l
,
n
) is called an (
n
+
l
,
M
,
d
,
(
m
,
1
)
)
q code if it has the size of codewords M and the minimum distance d. Denote by A
q
(
n
+
l
,
d
,
(
m
,
1
)
) the maximum number of codewords in an (
n
+
l
,
M
,
d
,
(
m
,
1
)
)
q code. The goal of this paper is to determine bounds of A
q
(
n
+
l
,
d
,
(
m
,
1
)
) and construct the corresponding optimal subspace codes.The Sphere-packing bound, Singleton bound, Wang-Xing-Safavi-Naini bound, Johnson bound, and Gilbert-Varshamov bound on the subspace codes(
n
+
l
,
M
,
d
,
(
m
,
1
)
)
q based on subspaces of type (
m
,
1
) in singular linear space F
q
(
n
+
l
) over F
q are given for the first time in this paper. We prove that the Steiner structure S
q
(
(
m
-
δ
+
1,0
)
,
(
m
,
1
)
,
n
+
l
) is an (
n
+
l
,
M
,
2
δ
,
(
m
,
1
)
)
q code, which attains the Wang-Xing-Safavi-Naini bound. The study of optimal subspace codes is one of the main research problems in coding theory. The obtained bounds are of vital importance to construct the optimal subspace codes.The rest of the paper is organized as follows. In Section2, the relevant concepts of (
n
+
l
)-dimensional singular linear space F
q
(
n
+
l
) over F
q are introduced and the anzahl formulas in singular linear space F
q
(
n
+
l
) are given. In Section 3, the Sphere-packing bound, Singleton bound, Wang-Xing-Safavi-Naini bound, Johnson bound, and Gilbert-Varshamov bound on the subspace codes (
n
+
l
,
M
,
d
,
(
m
,
1
)
)
q based on subspaces of type (
m
,
1
) in singular linear space F
q
(
n
+
l
) over F
q are presented. In Section 4, we prove that the Steiner structure S
q
(
(
m
-
δ
+
1,0
)
,
(
m
,
1
)
,
n
+
l
) is an (
n
+
l
,
M
,
2
δ
,
(
m
,
1
)
)
q code, which attains the Wang-Xing-Safavi-Naini bound. That is, the Steiner structure S
q
(
(
m
-
δ
+
1,0
)
,
(
m
,
1
)
,
n
+
l
) is an optimal subspace code. In Section 5, a conclusion is made for this paper.


## 2. Preliminaries

LetF
q be a finite field with q elements, where q is a prime power. F
q
(
n
+
l
) is the (
n
+
l
)-dimensional row vector space over F
q, where n and l are two nonnegative integers. The set of all (
n
+
l
)
×
(
n
+
l
) nonsingular matrices over F
q of the form
(4)
(
T
11
T
12
0
T
22
)
,
where T
11 and T
22 are nonsingular n
×
n and l
×
l matrices, respectively, forms a group under matrix multiplication, called the singular general linear group of degree n
+
l over F
q and denoted by G
L
n
+
l
,
n
(
F
q
).We have an action ofG
L
n
+
l
,
n
(
F
q
) on F
q
(
n
+
l
) defined as follows:
(5)
F
q
(
n
+
l
)
×
G
L
n
+
l
,
n
(
F
q
)
⟶
F
q
(
n
+
l
)
,
(
(
x
1
,
…
,
x
n
,
x
n
+
1
,
…
,
x
n
+
l
)
,
T
)
⟼
(
x
1
,
…
,
x
n
,
…
,
x
n
+
l
)
T
.
The vector space F
q
(
n
+
l
), together with the above group action, is called the (
n
+
l
)-dimensional singular linear space over F
q (see [15]).Lete
i
(
1
≤
i
≤
n
+
l
) be the row vector in F
q
(
n
+
l
) whose ith coordinate is 1 and all other coordinates are 0. Denote by E the l-dimensional subspace of F
q
(
n
+
l
) generated by e
n
+
1
,
e
n
+
2
,
…
,
e
n
+
l. An m-dimensional subspace P of F
q
(
n
+
l
) is called a subspace of type (
m
,
k
) if dim
⁡
(
P
∩
E
)
=
k.Introduce the anzahl formulas (see [15]) and use the Gaussian coefficient [16] for brevity:
(6)
[
m
2
m
1
]
q
=
∏
t
=
m
2
-
m
1
+
1
m
2
(
q
t
-
1
)
∏
t
=
1
m
1
(
q
t
-
1
)
.
By convenience, [
m
2
0
]
q
=
1 and [
m
2
m
1
]
q
=
0 whenever m
1
<
0 and m
2
<
m
1.Denote the set of all the subspaces of type(
m
,
k
) in F
q
(
n
+
l
) by M
(
m
,
k
;
n
+
l
,
n
) and let
(7)
N
(
m
,
k
;
n
+
l
,
n
)
=
|
M
(
m
,
k
;
n
+
l
,
n
)
|
.
It is verified that M
(
m
,
k
;
n
+
l
,
n
) is nonempty if and only if
(8)
0
≤
k
≤
l
,
0
≤
m
-
k
≤
n
.
Moreover, if M
(
m
,
k
;
n
+
l
,
n
) is nonempty, then
(9)
N
(
m
,
k
;
n
+
l
,
n
)
=
q
(
m
-
k
)
(
l
-
k
)
[
n
m
-
k
]
q
[
l
k
]
q
.LetP be a fixed subspace of type (
m
,
k
) in F
q
(
n
+
l
). Denote by M
(
m
1
,
k
1
;
m
,
k
;
n
+
l
,
n
) the set of all the subspaces of type (
m
1
,
k
1
) contained in P. Let
(10)
N
(
m
1
,
k
1
;
m
,
k
;
n
+
l
,
n
)
=
|
M
(
m
1
,
k
1
;
m
,
k
;
n
+
l
,
n
)
|
.
It is verified that M
(
m
1
,
k
1
;
m
,
k
;
n
+
l
,
n
) is nonempty if and only if
(11)
0
≤
k
1
≤
k
≤
l
,
0
≤
m
1
-
k
1
≤
m
-
k
≤
n
.
Moreover, if M
(
m
1
,
k
1
;
m
,
k
;
n
+
l
,
n
) is nonempty, then
(12)
N
(
m
1
,
k
1
;
m
,
k
;
n
+
l
,
n
)
=
q
(
m
1
-
k
1
)
(
k
-
k
1
)
[
m
-
k
m
1
-
k
1
]
q
[
k
k
1
]
q
.LetP be a fixed subspace of type (
m
1
,
k
1
) in F
q
(
n
+
l
). Denote by M
′
(
m
1
,
k
1
;
m
,
k
;
n
+
l
,
n
) the set of all the subspaces of type (
m
,
k
) containing P. Let
(13)
N
′
(
m
1
,
k
1
;
m
,
k
;
n
+
l
,
n
)
=
|
M
′
(
m
1
,
k
1
;
m
,
k
;
n
+
l
,
n
)
|
.
It is verified that M
′
(
m
1
,
k
1
;
m
,
k
;
n
+
l
,
n
) is nonempty if and only if
(14)
0
≤
k
1
≤
k
≤
l
,
0
≤
m
1
-
k
1
≤
m
-
k
≤
n
.
Moreover, if M
′
(
m
1
,
k
1
;
m
,
k
;
n
+
l
,
n
) is nonempty, then
(15)
N
′
(
m
1
,
k
1
;
m
,
k
;
n
+
l
,
n
)
=
q
(
l
-
k
)
(
m
-
k
-
m
1
+
k
1
)
[
n
-
(
m
1
-
k
1
)
(
m
-
k
)
-
(
m
1
-
k
1
)
]
q
[
(
l
-
k
1
)
(
k
-
k
1
)
]
q
.


## 3. Bounds on Subspace Codes Based on Subspaces of Type(
m
,
1
) in Singular Linear Space

Denote byA
q
(
n
+
l
,
d
,
(
m
,
1
)
) the maximum number of codewords in an (
n
+
l
,
M
,
d
,
(
m
,
1
)
)
q code based on subspaces of type (
m
,
1
) in singular linear space F
q
(
n
+
l
). By (3), the distance of any two elements in M
(
m
,
1
;
n
+
l
,
n
) must be an even number; thus, we only need to consider A
q
(
n
+
l
,
d
,
(
m
,
1
)
) for even d
=
2
δ.Definition 1.
The sphereS
(
V
,
(
m
,
1
)
,
t
) of radius t centered at a subspace V of type (
m
,
1
) in M
(
m
,
1
;
n
+
l
,
n
) is defined as the set of all subspaces U of type (
m
,
1
) in M
(
m
,
1
;
n
+
l
,
n
) that satisfy d
(
U
,
V
)
≤
2
t. That is,
(16)
S
(
V
,
(
m
,
1
)
,
t
)
=
{
U
∈
M
(
m
,
1
;
n
+
l
,
n
)
:
d
(
U
,
V
)
≤
2
t
}
.Theorem 2.
The number of subspaces of type(
m
,
1
) in S
(
V
,
(
m
,
1
)
,
t
) is independent of the choice of V and
(17)
|
S
(
V
,
(
m
,
1
)
,
t
)
|
=
∑
i
=
0
t
‍
(
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
1
)
)
+
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
0
)
)
)
,
where V
∈
M
(
m
,
1
;
n
+
l
,
n
) is a fixed subspace of type (
m
,
1
) in F
q
(
n
+
l
). N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
1
)
) is the number of elements W
∈
M
(
m
,
1
;
n
+
l
,
n
) satisfying
(18)
V
∩
W
∈
M
(
m
-
i
,
1
;
n
+
l
,
n
)
.
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
0
)
) is the number of elements W
∈
M
(
m
,
1
;
n
+
l
,
n
) satisfying
(19)
V
∩
W
∈
M
(
m
-
i
,
0
;
n
+
l
,
n
)
.Proof.
LetV
∈
M
(
m
,
1
;
n
+
l
,
n
) be a fixed subspace of type (
m
,
1
) in F
q
(
n
+
l
). Let N
q
(
n
+
l
,
(
m
,
1
)
,
(
j
,
1
)
,
(
s
,
1
)
) denote the number of elements W
∈
M
(
j
,
1
;
n
+
l
,
n
) satisfying W
∩
V
∈
M
(
s
,
1
;
n
+
l
,
n
). Choose the subspace of type (
s
,
1
) of intersection in
(20)
N
(
s
,
1
;
m
,
1
;
n
+
l
,
n
)
=
[
m
-
1
s
-
1
]
q
ways. Once this is done, the subspace can be extended to a subspace of type (
j
,
1
) in
(21)
(
(
q
n
+
l
-
q
m
-
q
l
)
(
q
n
+
l
-
q
m
+
1
-
q
l
)
⋯
(
q
n
+
l
-
q
m
+
j
-
s
-
1
-
q
l
)
)
×
(
(
q
j
-
q
s
)
(
q
j
-
q
s
+
1
)
⋯
(
q
j
-
q
j
-
1
)
)
-
1
ways. Thus,
(22)
N
q
(
n
+
l
,
(
m
,
1
)
,
(
j
,
1
)
,
(
s
,
1
)
)
=
[
m
-
1
s
-
1
]
q
×
(
(
q
n
+
l
-
q
m
-
q
l
)
(
q
n
+
l
-
q
m
+
1
-
q
l
)
k
k
k
k
⋯
(
q
n
+
l
-
q
m
+
j
-
s
-
1
-
q
l
)
)
×
(
(
q
j
-
q
s
)
(
q
j
-
q
s
+
1
)
⋯
(
q
j
-
q
j
-
1
)
)
-
1
.
From this,
(23)
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
1
)
)
=
[
m
i
]
q
×
(
(
q
n
+
l
-
q
m
-
q
l
)
(
q
n
+
l
-
q
m
+
1
-
q
l
)
kkkkkkkkk
⋯
(
q
n
+
l
-
q
m
+
i
-
1
-
q
l
)
)
×
(
(
q
m
-
q
m
-
i
)
(
q
m
-
q
m
-
i
+
1
)
⋯
(
q
m
-
q
m
-
1
)
)
-
1
.
LetN
q
(
n
+
l
,
(
m
,
1
)
,
(
j
,
1
)
,
(
s
,
0
)
) denote the number of elements W
∈
M
(
j
,
1
;
n
+
l
,
n
) satisfying W
∩
V
∈
M
(
s
,
0
;
n
+
l
,
n
). Choose the subspace of type (
s
,
0
) of intersection in
(24)
N
(
s
,
0
;
m
,
1
;
n
+
l
,
n
)
=
q
s
[
m
-
1
s
]
q
ways. Once this is done, the subspace can be extended to a subspace of type (
j
,
1
) in
(25)
(
q
l
-
1
q
-
1
-
1
)
×
(
(
q
n
+
l
-
q
m
-
q
l
)
(
q
n
+
l
-
q
m
+
1
-
q
l
)
kkkk
⋯
(
q
n
+
l
-
q
m
+
j
-
s
-
2
-
q
l
)
)
×
(
(
q
j
-
q
s
+
1
)
(
q
j
-
q
s
+
2
)
⋯
(
q
j
-
q
j
-
1
)
)
-
1
ways. Thus,
(26)
N
q
(
n
+
l
,
(
m
,
1
)
,
(
j
,
1
)
,
(
s
,
0
)
)
=
q
s
[
m
-
1
s
]
q
(
q
l
-
1
q
-
1
-
1
)
×
(
(
q
n
+
l
-
q
m
-
q
l
)
(
q
n
+
l
-
q
m
+
1
-
q
l
)
kkkk
⋯
(
q
n
+
l
-
q
m
+
j
-
s
-
2
-
q
l
)
)
×
(
(
q
j
-
q
s
+
1
)
(
q
j
-
q
s
+
2
)
⋯
(
q
j
-
q
j
-
1
)
)
-
1
.
From this,
(27)
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
0
)
)
=
q
m
-
i
[
m
-
1
i
-
1
]
q
(
q
l
-
1
q
-
1
-
1
)
×
(
(
q
n
+
l
-
q
m
-
q
l
)
(
q
n
+
l
-
q
m
+
1
-
q
l
)
kkkki
⋯
(
q
n
+
l
-
q
m
+
j
-
s
-
2
-
q
l
)
)
×
(
(
q
j
-
q
s
+
1
)
(
q
j
-
q
s
+
2
)
⋯
(
q
j
-
q
j
-
1
)
)
-
1
.
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
1
)
) and N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
0
)
) denote the number of subspaces of type (
m
,
1
) at distance 2
i from the fixed subspace V of type (
m
,
1
). Therefore,
(28)
|
S
(
V
,
(
m
,
1
)
,
t
)
|
=
∑
i
=
0
t
‍
(
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
1
)
)
+
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
0
)
)
)
,
which is clearly independent of the choice of V.Theorem 3 (Sphere-packing bound).
Lett
=
⌊
(
δ
-
1
)
/
2
⌋, and then
(29)
A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
)
≤
(
q
(
m
-
1
)
(
l
-
1
)
[
n
m
-
1
]
q
[
l
1
]
q
)
×
(
∑
i
=
0
t
‍
(
+
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
0
)
)
)
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
1
)
)
k
k
k
k
k
k
∑
i
=
0
t
‍
+
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
0
)
)
)
)
-
1
.Proof.
LetC
⊆
M
(
m
,
1
;
n
+
l
,
n
) be an (
n
+
l
,
M
,
2
δ
,
(
m
,
1
)
)
q code and let t
=
⌊
(
δ
-
1
)
/
2
⌋. Then the spheres of radius t centered at every codeword of C disjoint with each other and each of these spheres contains
(30)
∑
i
=
0
t
‍
(
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
1
)
)
k
k
k
+
N
q
(
n
+
l
,
(
m
,
1
)
(
m
,
1
)
,
(
m
-
i
,
0
)
)
)
subspaces of type (
m
,
1
) in M
(
m
,
1
;
n
+
l
,
n
). Since the total number of subspaces of type (
m
,
1
) in F
q
(
n
+
l
) is
(31)
|
M
(
m
,
1
;
n
+
l
,
n
)
|
=
N
(
m
,
1
;
n
+
l
,
n
)
=
q
(
m
-
1
)
(
l
-
1
)
[
n
m
-
1
]
q
[
l
1
]
q
,
M
≤
(
q
(
m
-
1
)
(
l
-
1
)
[
n
m
-
1
]
q
[
l
1
]
q
)
×
(
∑
i
=
0
t
‍
(
(
m
-
i
,
0
)
)
)
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
N
q
(
m
-
i
,
1
)
∑
i
=
0
t
‍
i
(
m
-
i
,
0
)
)
k
k
k
k
k
k
k
k
k
k
k
k
k
N
q
(
m
-
i
,
1
)
)
k
k
k
k
k
k
k
+
N
q
(
(
m
-
i
,
0
)
)
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
k
k
k
k
k
k
k
k
k
k
k
k
∑
i
=
0
t
‍
i
(
m
-
i
,
0
)
)
N
q
(
m
-
i
,
1
)
)
)
)
-
1
.
Then the theorem follows immediately.SupposeC is a collection of subspaces of type (
m
,
1
) in M
(
m
,
1
;
n
+
l
,
n
) and let W
′ be any (
n
+
l
-
1
)-dimensional subspace of F
q
(
n
+
l
). Define
(32)
C
′
=
{
V
′
:
V
′
=
H
m
-
1
(
V
∩
W
′
)
,
V
∈
C
}
by replacing each subspace V
∈
C by V
′
=
H
m
-
1
(
V
∩
W
′
), where H
m
-
1
(
V
∩
W
′
) is defined as follows: V is replaced by V
∩
W
′ if V
∩
W
′ is a subspace of type (
m
-
1,1
) in F
q
(
n
+
l
); otherwise, V is replaced by some subspace of type (
m
-
1,1
) of V.Lemma 4.
IfC
⊆
M
(
m
,
1
;
n
+
l
,
n
) is an (
n
+
l
,
M
,
d
,
(
m
,
1
)
)
q code with d
>
2, then C
′
=
{
V
′
:
V
′
=
H
m
-
1
(
V
∩
W
′
)
,
V
∈
C
} is an (
n
+
l
-
1
,
M
,
d
′
,
(
m
-
1,1
)
)
q code with d
′
≥
d
-
2.Proof.
It is sufficient to consider the cardinality and the minimum distance of codeC
′. Let U and V be any two distinct codewords of code C and the corresponding codewords U
′
=
H
m
-
1
(
U
∩
W
′
) and V
′
=
H
m
-
1
(
V
∩
W
′
) of code C
′ are obtained. Obviously U
′
⊆
U and V
′
⊆
V, and then U
′
∩
V
′
⊆
U
∩
V and
(33)
2
dim
⁡
(
U
′
∩
V
′
)
≤
2
dim
⁡
(
U
∩
V
)
≤
2
m
-
d
,
where the latter inequality follows from the fact that
(34)
d
(
U
,
V
)
=
2
m
-
2
dim
⁡
(
U
∩
V
)
≥
d
.
Considering d
(
U
′
,
V
′
) with (33),
(35)
d
(
U
′
,
V
′
)
=
2
(
m
-
1
)
-
2
dim
⁡
⁡
(
U
′
∩
V
′
)
≥
2
(
m
-
1
)
-
(
2
m
-
d
)
=
d
-
2
,
which implies that d
′
≥
d
-
2.
Byd
>
2, d
(
U
′
,
V
′
)
≥
d
-
2
>
0, so U
′ and V
′ are distinct, which shows that code C
′ has the same number of codewords as code C.Theorem 5 (Singleton bound).
Consider(36)
A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
)
≤
q
(
m
-
δ
)
(
l
-
1
)
[
n
-
δ
+
1
m
-
δ
]
q
[
l
1
]
q
.Proof.
LetC
⊆
M
(
m
,
1
;
n
+
l
,
n
) be an (
n
+
l
,
M
,
2
δ
,
(
m
,
1
)
)
q code. When Lemma 4 is applied (
δ
-
1
) times, an (
n
+
l
-
δ
+
1
,
M
,
2
δ
′
,
(
m
-
δ
+
1,1
)
)
q code is obtained, where every codeword is of subspace of type (
m
-
δ
+
1,1
) in F
q
(
n
+
l
-
δ
+
1
). It is well known that
(37)
|
M
(
m
-
δ
+
1,1
;
n
+
l
-
δ
+
1
,
n
-
δ
+
1
)
|
=
N
(
m
-
δ
+
1,1
;
n
+
l
-
δ
+
1
,
n
-
δ
+
1
)
=
q
(
m
-
δ
)
(
l
-
1
)
[
n
-
δ
+
1
m
-
δ
]
q
[
l
1
]
q
.
Hence
(38)
M
≤
q
(
m
-
δ
)
(
l
-
1
)
[
n
-
δ
+
1
m
-
δ
]
q
[
l
1
]
q
,
where the inequality follows from the fact that the obtained (
n
+
l
-
δ
+
1
,
M
,
2
δ
′
,
(
m
-
δ
+
1,1
)
)
q code cannot have more codewords than the total subspaces of type (
m
-
δ
+
1,1
) in F
q
(
n
+
l
-
δ
+
1
). Then the theorem follows.Theorem 6 (Wang-Xing-Safavi-Naini bound).
Consider(39)
A
q
(
n
+
l
,
2
δ
+
2
,
(
m
,
1
)
)
≤
q
(
m
-
δ
)
(
l
-
1
)
[
n
m
-
δ
]
q
[
m
-
1
m
-
δ
]
q
.Proof.
LetC
⊆
M
(
m
,
1
;
n
+
l
,
n
) be an (
n
+
l
,
M
,
2
δ
+
2
,
(
m
,
1
)
)
q code. On the one hand, each codeword of C contains exactly
(40)
N
(
m
-
δ
,
0
;
m
,
1
;
n
+
l
,
n
)
=
q
(
m
-
δ
)
[
m
-
1
m
-
δ
]
q
subspaces of type (
m
-
δ
,
0
).
On the other hand, ifdim
⁡
(
U
∩
V
)
≥
m
-
δ for any two distinct codewords U and V of C, by (3),
(41)
d
(
U
,
V
)
=
2
m
-
2
dim
⁡
(
U
∩
V
)
≤
2
δ
,
a contradiction to the minimum distance 2
δ
+
2 of C, which implies that a given subspace of type (
m
-
δ
,
0
) in F
q
(
n
+
l
) cannot be contained in two distance codewords of C. The total number of subspaces of type (
m
-
δ
,
0
) in F
q
(
n
+
l
) is
(42)
N
(
m
-
δ
,
0
;
n
+
l
,
n
)
=
q
(
m
-
δ
)
l
[
n
m
-
δ
]
q
,
so M
≤
q
(
m
-
δ
)
(
l
-
1
)
(
[
n
m
-
δ
]
q
/
[
m
-
1
m
-
δ
]
q
).Theorem 7 (Johnson bound).
Consider(43)
A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
)
≤
q
l
(
q
n
-
1
)
q
m
-
q
A
q
(
n
+
l
-
1,2
δ
,
(
m
-
1,1
)
)
.Proof.
LetC
⊆
M
(
m
,
1
;
n
+
l
,
n
) be an (
n
+
l
,
M
,
2
δ
,
(
m
,
1
)
)
q code, which attains the value of A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
); that is, M
=
A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
). Each codeword (subspace of type (
m
,
1
)) of C contains
(44)
q
m
-
q
q
-
1
subspaces of type (
1,0
) in F
q
(
n
+
l
). There are totally
(45)
q
l
(
q
n
-
1
)
q
-
1
subspaces of type (
1,0
) in F
q
(
n
+
l
). Hence, there exists a subspace P of type (
1,0
) satifying the fact that the subspace P is contained in at least
(46)
M
(
q
m
-
q
)
q
l
(
q
n
-
1
)
codewords of C.
LetF
q
(
n
+
l
)
=
P
⊕
W, where W is a subspace of type (
n
+
l
-
1
,
l
) in F
q
(
n
+
l
). Define the following set:
(47)
C
′
=
{
V
∩
W
:
V
∈
C
,
P
⊂
V
}
.
Clearly C
′ consists of the subspaces of type (
m
-
1,1
) of W; thus, C
′ can be regarded as an (
n
+
l
-
1
,
M
′
,
2
δ
′
,
(
m
-
1,1
)
)
q code with the size M
′ and the minimum distance 2
δ
′, where M
′
≥
M
(
q
m
-
q
)
/
q
l
(
q
n
-
1
).
LetU
′ and V
′ be any two codewords of C
′ and there exist two corresponding codewords U and V of C such that U
′
=
U
∩
W and V
′
=
V
∩
W with P
⊂
U and P
⊂
V. Noting that
(48)
U
′
∩
V
′
=
(
U
∩
W
)
∩
(
V
∩
W
)
=
(
U
∩
V
)
∩
W
,
dim
⁡
(
U
′
∩
V
′
)
=
dim
⁡
(
(
U
∩
V
)
∩
W
)
=
dim
⁡
⁡
(
U
∩
V
)
+
dim
⁡
W
-
dim
⁡
(
(
U
∩
V
)
+
W
)
=
dim
⁡
⁡
(
U
∩
V
)
+
(
n
+
l
-
1
)
-
(
n
+
l
)
=
dim
⁡
(
U
∩
V
)
-
1
,
where the third equality follows from the fact that U
∩
V contains P, hence,
(49)
dim
⁡
⁡
(
U
′
∩
V
′
)
=
dim
⁡
⁡
(
U
∩
V
)
-
1
.
By (3) and (49), d
(
U
′
,
V
′
)
=
d
(
U
,
V
) from which δ
=
δ
′ follows. With all the above discussions,
(50)
A
q
(
n
+
l
-
1,2
δ
,
(
m
-
1,1
)
)
≥
M
′
≥
q
m
-
q
q
l
(
q
n
-
1
)
A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
)
.
The theorem is completed.Corollary 8.
Consider(51)
A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
)
≤
q
l
(
m
-
δ
+
1
)
∏
i
=
0
m
-
δ
‍
q
n
-
i
-
1
q
m
-
i
-
q
.Proof.
When Theorem7 is applied iteratively (
m
-
δ
+
1
) times, note the trivial equality
(52)
A
q
(
n
+
l
-
m
+
δ
-
1,2
δ
,
(
δ
-
1,1
)
)
=
1
,
A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
)
≤
q
l
q
n
-
1
q
m
-
q
q
l
q
n
-
1
-
1
q
m
-
1
-
q
⋯
q
l
q
n
-
m
+
δ
-
1
q
δ
-
q
×
A
q
(
n
+
l
-
m
+
δ
-
1,2
δ
,
(
δ
-
1,1
)
)
=
q
l
(
m
-
δ
+
1
)
∏
i
=
0
m
-
δ
q
n
-
i
-
1
q
m
-
i
-
q
.Corollary 9.
Consider(53)
A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
)
≤
q
l
(
m
-
δ
+
1
)
⌊
q
n
-
1
q
m
-
q
⌊
q
n
-
1
-
1
q
m
-
1
-
q
⋯
⌊
q
n
-
m
+
δ
-
1
q
δ
-
q
⌋
⋯
⌋
⌋
.Theorem 10 (Johnson bound).
Consider(54)
A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
)
≤
q
(
m
-
1
)
(
l
-
1
)
(
q
n
-
1
-
1
)
(
q
n
-
1
)
(
q
l
-
1
)
(
q
n
-
m
-
1
)
(
q
n
-
m
+
1
-
1
)
(
q
-
1
)
×
A
q
(
n
+
l
-
1,2
δ
,
(
m
,
1
)
)
.Proof.
LetC
⊆
M
(
m
,
1
;
n
+
l
,
n
) be an (
n
+
l
,
M
,
2
δ
,
(
m
,
1
)
)
q code, which attains the value of A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
); that is, M
=
A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
). For each
(55)
W
∈
M
(
n
-
1,1
;
n
+
l
,
n
)
,
define the following set:
(56)
C
W
=
{
V
:
V
∈
C
,
V
⊂
W
}
.
Clearly, for each W
∈
M
(
n
-
1,1
;
n
+
l
,
n
), C
W is an (
n
+
l
-
1
,
M
W
,
2
δ
′
,
(
m
,
1
)
)
q code with the size M
W and the minimum distance 2
δ
′ and δ
′
≥
δ. There are precisely
(57)
q
(
n
-
m
-
1
)
(
l
-
1
)
(
q
n
-
m
-
1
)
(
q
n
-
m
+
1
-
1
)
(
q
-
1
)
(
q
2
-
1
)
elements containing any given subspace of type (
m
,
1
) in M
(
n
-
1,1
;
n
+
l
,
n
); hence each codeword (subspace of type (
m
,
1
)) of C is contained in
(58)
q
(
n
-
m
-
1
)
(
l
-
1
)
(
q
n
-
m
-
1
)
(
q
n
-
m
+
1
-
1
)
(
q
-
1
)
(
q
2
-
1
)
different codes C
W. Consider
(59)
∑
W
‍
|
C
W
|
=
M
·
q
(
n
-
m
-
1
)
(
l
-
1
)
(
q
n
-
m
-
1
)
(
q
n
-
m
+
1
-
1
)
(
q
-
1
)
(
q
2
-
1
)
,
from which
(60)
∑
W
|
C
W
|
|
M
(
n
-
1,1
;
n
+
l
,
n
)
|
=
M
·
(
q
n
-
m
-
1
)
(
q
n
-
m
+
1
-
1
)
(
q
-
1
)
q
(
l
-
1
)
(
m
-
1
)
(
q
n
-
1
)
(
q
l
-
1
)
,
where
(61)
|
M
(
n
-
1,1
;
n
+
l
,
n
)
|
=
N
(
n
-
1,1
;
n
+
l
,
n
)
=
q
(
n
-
2
)
(
l
-
1
)
(
q
n
-
1
-
1
)
(
q
n
-
1
)
(
q
l
-
1
)
(
q
-
1
)
2
(
q
2
-
1
)
.
Thus, there exists at least one W
∈
M
(
n
-
1,1
;
n
+
l
,
n
) such that
(62)
|
C
W
|
≥
M
·
(
q
n
-
m
-
1
)
(
q
n
-
m
+
1
-
1
)
(
q
-
1
)
q
(
l
-
1
)
(
m
-
1
)
(
q
n
-
1
)
(
q
l
-
1
)
.
Obviously, for any W
∈
M
(
n
-
1,1
;
n
+
l
,
n
),
(63)
A
q
(
n
+
l
-
1,2
δ
,
(
m
,
1
)
)
≥
|
C
W
|
,
and then the theorem follows immediately.Theorem 11 (Gilbert-Varshamov bound).
IfV
∈
(
n
+
l
,
M
,
2
δ
,
(
m
,
1
)
)
q,  M
=
A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
), then
(64)
A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
)
≥
q
(
m
-
1
)
(
l
-
1
)
[
n
m
-
1
]
q
[
l
1
]
q
|
S
(
V
,
(
m
,
1
)
,
(
δ
-
1
)
)
|
,
where
(65)
|
S
(
V
,
(
m
,
1
)
,
(
δ
-
1
)
)
|
=
∑
i
=
0
δ
-
1
(
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
1
)
)
k
i
+
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
0
)
)
)
.Proof.
LetC
⊆
M
(
m
,
1
;
n
+
l
,
n
) be an (
n
+
l
,
M
,
2
δ
,
(
m
,
1
)
)
q code, which attains the value of A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
); that is, M
=
A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
). There is no subspace U of type (
m
,
1
) in M
(
m
,
1
;
n
+
l
,
n
) satisfying
(66)
d
(
U
,
V
)
≥
2
δ
,
for any V
∈
C. Otherwise, by adding the subspace U of type (
m
,
1
) to C, a new (
n
+
l
,
M
+
1,2
δ
,
(
m
,
1
)
)
q code is obtained, which is a contradiction to M
=
A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
). Therefore, for any V
∈
C,
(67)
M
·
|
S
(
V
,
(
m
,
1
)
,
(
δ
-
1
)
)
|
≥
N
(
m
,
1
;
n
+
l
,
n
)
=
q
(
m
-
1
)
(
l
-
1
)
[
n
m
-
1
]
q
[
l
1
]
q
.
That is,
(68)
A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
)
≥
q
(
m
-
1
)
(
l
-
1
)
[
n
m
-
1
]
q
[
l
1
]
q
|
S
(
V
,
(
m
,
1
)
,
(
δ
-
1
)
)
|
,
where
(69)
|
S
(
V
,
(
m
,
1
)
,
(
δ
-
1
)
)
|
=
∑
i
=
0
δ
-
1
‍
(
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
1
)
)
k
k
k
k
k
k
k
k
+
N
q
(
n
+
l
,
(
m
,
1
)
,
(
m
,
1
)
,
(
m
-
i
,
0
)
)
)
.


## 4. Steiner Structure

Definition 12.
A Steiner structureS
q
(
(
m
1
,
0
)
,
(
m
,
1
)
,
n
+
l
) is a collection S of elements from M
(
m
,
1
;
n
+
l
,
n
) satisfying the fact that each element from M
(
m
1
,
0
;
n
+
l
,
n
) is contained in exactly one element of S. The subspaces of type (
m
,
1
) in S are called blocks of the Steiner structure S
q
(
(
m
1
,
0
)
,
(
m
,
1
)
,
n
+
l
).Theorem 13.
The total number of blocks in theS
q
(
(
m
1
,
0
)
,
(
m
,
1
)
,
n
+
l
) is
(70)
q
m
1
(
l
-
1
)
[
n
m
1
]
q
[
m
-
1
m
1
]
q
.Proof.
Each block (subspace of type(
m
,
1
)) of the Steiner structure S
q
(
(
m
1
,
0
)
,
(
m
,
1
)
,
n
+
l
) contains
(71)
N
(
m
1
,
0
;
m
,
1
;
n
+
l
,
n
)
=
q
m
1
[
m
-
1
m
1
]
q
subspaces of type (
m
1
,
0
). By the definition of the Steiner structure S
q
(
(
m
1
,
0
)
,
(
m
,
1
)
,
n
+
l
), each subspace of type (
m
1
,
0
) is contained in exactly one block. The total number of subspaces of type (
m
1
,
0
) in F
q
(
n
+
l
) is
(72)
N
(
m
1
,
0
;
n
+
l
,
n
)
=
q
m
1
l
[
n
m
1
]
q
;
thus, the total number of blocks of the S
q
(
(
m
1
,
0
)
,
(
m
,
1
)
,
n
+
l
) is
(73)
q
m
1
(
l
-
1
)
[
n
m
1
]
q
[
m
-
1
m
1
]
q
.Theorem 14.
The Steiner structureS
q
(
(
m
1
,
0
)
,
(
m
,
1
)
,
n
+
l
) is an (
n
+
l
,
M
,
2
δ
,
(
m
,
1
)
)
q code with the size M
=
q
m
1
(
l
-
1
)
(
[
n
m
1
]
q
/
[
m
-
1
m
1
]
q
) and δ
=
m
-
m
1
+
1.Proof.
By Definition12 and Theorem 13, it is sufficient to prove δ
=
m
-
m
1
+
1. Firstly, for any two distinct blocks X
,
Y
∈
S
q
(
(
m
1
,
0
)
,
(
m
,
1
)
,
n
+
l
),
(74)
dim
⁡
(
X
∩
Y
)
≤
m
1
-
1
,
where the inequality follows from the definition of the Steiner structure S
q
(
(
m
1
,
0
)
,
(
m
,
0
)
,
n
+
l
) in which each subspace of type (
m
1
,
0
) is contained in exactly one block of the S
q
(
(
m
1
,
0
)
,
(
m
,
1
)
,
n
+
l
). By (3) and (74),
(75)
d
(
X
,
Y
)
=
2
m
-
2
dim
⁡
(
X
∩
Y
)
≥
2
(
m
-
m
1
+
1
)
.
Furthermore, 2
δ is the minimum distance of the code; then δ
≥
m
-
m
1
+
1.
Conversely, letV be a fixed subspace of type (
m
1
-
1,0
) in F
q
(
n
+
l
), and then choose two subspaces U
1 and U
2 of type (
m
1
,
0
) in F
q
(
n
+
l
) such that
(76)
V
=
U
1
∩
U
2
.
By the definition of the Steiner structure S
q
(
(
m
1
,
0
)
,
(
m
,
1
)
,
n
+
l
), there exist the uniquely corresponding subspaces X
1 and X
2 of type (
m
,
1
) in the Steiner structure S
q
(
(
m
1
,
0
)
,
(
m
,
1
)
,
n
+
l
) satisfying
(77)
U
1
⊆
X
1
,
U
2
⊆
X
2
,
respectively. Then,
(78)
V
=
U
1
∩
U
2
⊆
X
1
∩
X
2
,
from which
(79)
dim
⁡
(
X
1
∩
X
2
)
≥
dim
⁡
V
=
m
1
-
1
.
By (3) and (79),
(80)
d
(
X
1
,
X
2
)
=
2
m
-
2
dim
⁡
(
X
1
∩
X
2
)
≤
2
(
m
-
m
1
+
1
)
.
Furthermore, 2
δ is the minimum distance of the code, and then δ
≤
m
-
m
1
+
1.
From the above two aspects,δ
=
m
-
m
1
+
1.The sufficient and necessary conditions for an(
n
+
l
,
M
,
2
δ
,
(
m
,
1
)
)
q code to attain the Wang-Xing-Safavi-Naini bound in Theorem 6 are presented below.Theorem 15.
An(
n
+
l
,
M
,
2
δ
,
(
m
,
1
)
)
q code C attains the Wang-Xing-Safavi-Naini bound; that is, M
=
q
(
m
-
δ
+
1
)
(
l
-
1
)
(
[
n
m
-
δ
+
1
]
q
/
[
m
-
1
m
-
δ
+
1
]
q
) if and only if C is the Steiner structure S
q
(
(
m
-
δ
+
1,0
)
,
(
m
,
1
)
,
n
+
l
).Proof.
From Theorems6 and 14, if C is the Steiner structure S
q
(
(
m
-
δ
+
1,0
)
,
(
m
,
1
)
,
n
+
l
), C is an (
n
+
l
,
M
,
2
δ
,
(
m
,
1
)
)
q code with
(81)
M
=
q
(
m
-
δ
+
1
)
(
l
-
1
)
[
n
m
-
δ
+
1
]
q
[
m
-
1
m
-
δ
+
1
]
q
.
Obviously such a code attains the Wang-Xing-Safavi-Naini bound.
Conversely, letC be an (
n
+
l
,
M
,
2
δ
,
(
m
,
1
)
)
q code attaining the Wang-Xing-Safavi-Naini bound; that is,
(82)
M
=
q
(
m
-
δ
+
1
)
(
l
-
1
)
[
n
m
-
δ
+
1
]
q
[
m
-
1
m
-
δ
+
1
]
q
.
Firstly, any subspace of type (
m
-
δ
+
1,0
) cannot be contained in two distinct codewords U and V of C. Otherwise, by (3),
(83)
d
(
U
,
V
)
=
2
m
-
2
dim
⁡
(
U
∩
V
)
≤
2
δ
-
2
,
a contradiction to the minimum distance 2
δ of C. Each codeword of C contains
(84)
N
(
m
-
δ
+
1,0
;
m
,
1
;
n
+
l
,
n
)
=
q
(
m
-
δ
+
1
)
[
m
-
1
m
-
δ
+
1
]
q
distinct subspaces of type (
m
-
δ
+
1,0
); thus, all the codewords of C contain totally
(85)
M
·
q
(
m
-
δ
+
1
)
[
m
-
1
m
-
δ
+
1
]
q
=
q
(
m
-
δ
+
1
)
l
[
n
m
-
δ
+
1
]
q
distinct subspaces of type (
m
-
δ
+
1,0
). There are totally
(86)
q
(
m
-
δ
+
1
)
l
[
n
m
-
δ
+
1
]
q
distinct subspaces of type (
m
-
δ
+
1,0
) in F
q
(
n
+
l
), which implies that each subspace of type (
m
-
δ
+
1,0
) is contained in exactly one codeword of C.
When regarding all the codewords ofC as blocks, code C is the Steiner structure S
q
(
(
m
-
δ
+
1,0
)
,
(
m
,
1
)
,
n
+
l
).Theorem15 shows that certain Steiner structure is an optimal code.Corollary 16.
Consider
A
q
(
n
+
l
,
2
δ
,
(
m
,
1
)
)
=
q
(
m
-
δ
+
1
)
(
l
-
1
)
(
[
n
m
-
δ
+
1
]
q
/
[
m
-
1
m
-
δ
+
1
]
q
) if and only if the Steiner structure S
q
(
(
m
-
δ
+
1,0
)
,
(
m
,
1
)
,
n
+
l
) exists.


## 5. Conclusion

In this paper, a subspace code(
n
+
l
,
M
,
d
,
(
m
,
1
)
)
q based on subspaces of type (
m
,
1
) in singular linear space F
q
(
n
+
l
) over F
q is constructed and the Sphere-packing bound, Singleton bound, Wang-Xing-Safavi-Naini bound, Johnson bound, and Gilbert-Varshamov bound on (
n
+
l
,
M
,
d
,
(
m
,
1
)
)
q code are presented. Meanwhile, we prove that codes based on subspaces of type (
m
,
1
) in singular linear space attain the Wang-Xing-Safavi-Naini bound if and only if they are certain Steiner structures F
q
(
n
+
l
). We could consider whether there exist nontrivial perfect subspace codes in M
(
m
,
1
;
n
+
l
,
n
) in the following steps.



---

*Source: 497958-2014-08-05.xml*