% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all commands that change parameters such as
%    margins or page sizes.

% Packages amssymb and amsthm are already loaded.
% We recommend these AMS packages:
\usepackage{amsmath,amssymb}
% We recommend the graphicx package for importing figures:
\usepackage{graphicx}
% Use this command to create hyperlinks (optional and recommended):
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\deff}{\mbox{$\stackrel{\rm def}{=}$}}
\newcommand{\Span}[1]{{\left\langle {#1} \right\rangle}}

\makeatletter
 \DeclareRobustCommand{\nsbinom}{\genfrac[]\z@{}}
 \makeatother
 \newcommand{\sbinom}[2]{\nsbinom{{#1}}{{#2}}}
 \newcommand{\sbinomq}[2]{\nsbinom{{#1}}{{#2}}_{q}}
  \newcommand{\sbinomtwo}[2]{\nsbinom{{#1}}{{#2}}_{2}}

\newcommand{\field}[1]{\mathbb{#1}}
\newcommand{\F}{\field{F}}
\newcommand{\T}{\field{T}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\cG}{{\cal G}}
\newcommand{\dS}{\field{S}}
\newcommand{\cA}{{\cal A}}
\newcommand{\cB}{{\cal B}}
\newcommand{\cC}{{\cal C}}
\newcommand{\cD}{{\cal D}}
\newcommand{\cM}{{\cal M}}
\newcommand{\cN}{{\cal N}}
\newcommand{\cP}{{\cal P}}
\newcommand{\cY}{{\cal Y}}
\newcommand{\cZ}{{\cal Z}}

% Theorem-like environments that are declared in the style file are:
% theorem, lemma, corollary, proposition, fact, observation, claim,
% definition, example, conjecture, open, problem, question, remark, note

%%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Give the submission and acceptance dates in the format shown.
% The editors will insert the publication date in the third argument.
\dateline{June 19, 2017}{March 25, 2018}{TBD}

% Give one or more subject codes separated by commas.
% Codes are available from http://www.ams.org/mathscinet/freeTools.html
\MSC{94B25, 05B40, 51E10}

% Uncomment exactly one of the following copyright statements.  Alternatively,
% you can write your own copyright statement subject to the approval of the journal.
% See https://creativecommons.org/licenses/ for a full explanation of the
% Creative Commons licenses.
%
% We strongly recommend CC BY-ND or CC BY. Both these licenses allow others
% to freely distribute your work while giving credit to you. The difference between
% them is that CC BY-ND only allows distribution unchanged and in whole, while
% CC BY also allows remixing, tweaking and building upon your work.
%
%    One author:
%\Copyright{The author.}
%\Copyright{The author. Released under the CC BY license (International 4.0).}
%\Copyright{The author. Released under the CC BY-ND license (International 4.0).}
%    More than one author:
%\Copyright{The authors.}
%\Copyright{The authors. Released under the CC BY license (International 4.0).}
\Copyright{  The authors. Released under the CC BY-ND license (International 4.0).}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% If needed, include a line break (\\) at an appropriate place in the title.
\title{A New Approach for Examining $q$-Steiner Systems}

% Input author, affiliation, address and support information as follows;
% The address should include the country, but does not have to include
%    the street address. Give at least one email address.

\author{Tuvi Etzion\thanks{Supported in part by Israel Science Foundation (ISF), Jerusalem, Israel under Grant 10/12.}\\
\small Department of Computer Science\\[-0.8ex]
\small Technion\\[-0.8ex]
\small Haifa 3200003, IOsrael\\
\small\tt etzion@cs.technion.ac.il}


\begin{document}

\maketitle



\begin{abstract}
One of the most intriguing problems in $q$-analogs of designs and codes is the existence question of
an infinite family of $q$-analog of Steiner systems (spreads not included) in general,
and the existence question for the $q$-analog of the Fano plane in particular.

We exhibit a completely new method to attack this problem. In the process we define
a new family of designs whose existence is implied by the
existence of $q$-Steiner systems, but could exist even if the
related $q$-Steiner systems do not exist.

The method is based on a possible system obtained by puncturing
all the subspaces of the $q$-Steiner system several times.
We define the punctured system as a new type of design and
enumerate the number of subspaces of various types that it might have.
It will be evident
that its existence does not imply the existence of the related $q$-Steiner system.
On the other hand, this type of design demonstrates how close can we get to
the related $q$-Steiner system.

Necessary conditions for the existence
of such designs are presented. These necessary conditions will be also necessary conditions
for the existence of the related $q$-Steiner system.
Trivial and nontrivial direct constructions
and a nontrivial recursive construction for such designs are given.
Some of the designs have a symmetric structure, which is uniform in
the dimensions of the existing subspaces in the system. Most constructions are based
on this uniform structure of the design or its punctured designs.
\end{abstract}

\section{Introduction}

Let $\F_q$ be the finite field with $q$ elements
and let $\F_q^n$ be the set of all vectors
of length $n$ over~$\F_q$. $\F_q^n$ is a vector
space with dimension $n$ over $\F_q$. For a given integer $k$,
$0 \leq k \leq n$, let $\cG_q(n,k)$ denote the set of all
$k$-dimensional subspaces ($k$-\emph{subspaces} in short) of $\F_q^n$. $\cG_q(n,k)$ is often
referred to as a Grassmannian. It is well known that
$$ \begin{small}
| \cG_q (n,k) | = \sbinomq{n}{k}
\deff \frac{(q^n-1)(q^{n-1}-1) \cdots
(q^{n-k+1}-1)}{(q^k-1)(q^{k-1}-1) \cdots (q-1)}
\end{small}
$$
where $\sbinomq{n}{k}$ is the $q$-\emph{binomial coefficient} (known also
as the \emph{Gaussian coefficient}~\cite[pp. 325-332]{vLWi92}).

A \emph{Grassmannian code} (known better as a \emph{constant dimension code})
$\C$ is a subset of
$\cG_q(n,k)$. In recent years there has been an increasing
interest in Grassmannian codes as a result of their
application to error-correction in random network coding which was
demonstrated in the seminal work by Koetter and Kschischang~\cite{KoKs08}.
This work has motivated lot of research on coding for
Grassmannian codes (see for example~\cite{EtSi13,EtVa11}
and references therein). But the
interest in these codes has been also before this application,
since Grassmannian codes are the $q$-analogs of the well
studied constant weight codes~\cite{BSSS}. The Grassmann scheme is the $q$-analog of
the Johnson scheme, where $q$-analogs replace concepts of subsets by concepts of subspaces when
problems on sets are transferred to problems on subspaces
over the finite field $\F_q$.
For example, the size of a set is replaced by the dimension of a subspace,
the binomial coefficients are replaced by the Gaussian coefficients, etc.
One example of such $q$-analog problem in coding theory is the nonexistence of nontrivial perfect codes
in the Grassmann scheme which was proved in~\cite{Chi87,MaZh95}. This problem is the $q$-analog for the nonexistence
problem of perfect codes in the Johnson scheme, which is a well-known
open problem~\cite{Del73,Etz96,EtSc04}. Also, the $q$-analogs of other various
combinatorial objects are well known~\cite[pp. 325-332]{vLWi92}.
The work of Koetter and Kschischang~\cite{KoKs08} has motivated also
increasing interest and lot of research work on these related $q$-analog of designs
(see for example~\cite{BEOVW,Etz14,EtVa11a} and references therein).
The most intriguing question is the existence of $q$-analogs for Steiner systems
which is the topic of the research in this paper.


A \emph{Steiner system} $S(t,k,n)$ is a set $S$ of $k$-subsets (called \emph{blocks})
from an $n$-set~$\cN$ such that each $t$-subset of $\cN$ is contained
in exactly one block of $S$. Steiner systems were subject to an
extensive research in combinatorial designs~\cite{CoDi07}.
A Steiner system is
also equivalent to an optimal constant weight code in
the Hamming scheme. It is well-known that if a Steiner system
$S(t,k,n)$ exists, then for all $0 \leq i \leq t-1$,
$\frac{\binom{n-i}{t-i}}{\binom{k-i}{t-i}}$ must be integers.
It was proved only recently that these necessary conditions for the
existence of a Steiner system $S(t,k,n)$ are also sufficient for each $t$ and $k$
such that $0 < t <k$, except for a finite number of values of~$n$~\cite{GKLO16,Kee14}.

Cameron~\cite{Cam74,Cam74a} and Delsarte~\cite{Del76} have
extended the notions of block design and Steiner systems
to vector spaces.
A \emph{$q$-Steiner system} $\dS_q(t,k,n)$ is a set $\dS$ of
$k$-subspaces of $\F_q^n$ (called \emph{blocks}) such that each $t$-subspace of $\F_q^n$
is contained in exactly one block of $\dS$.
A $q$-Steiner system $\dS_q(t,k,n)$ is an optimal constant dimension
code~\cite{EtVa11,EtVa11a}. Similarly, to Steiner systems, simple necessary divisibility conditions
for the existence of a given $q$-Steiner system were developed~\cite{ScEt,Suz90}.

\begin{theorem}
\label{thm:derived}
If a $q$-Steiner system $\dS_q (t,k,n)$ exists, then
for each $i$, $1 \leq i \leq t-1$, a $q$-Steiner system
$\dS_q(t-i,k-i,n-i)$ exists.
\end{theorem}

\begin{corollary}
\label{cor:ness}
If a $q$-Steiner system $\dS_q(t,k,n)$ exists, then for all $0 \leq i \leq t-1$,
$$
\frac{\sbinomq{n-i}{t-i}}{\sbinomq{k-i}{t-i}}
$$
must be integers.
\end{corollary}

While a lot of information is known about the existence of Steiner systems~\cite{CoDi07,GKLO16,Kee14}, our knowledge
about the existence of $q$-Steiner systems is quite limited.
Until recently, the only known $q$-Steiner systems $\dS_q(t,k,n)$ were either trivial or
for $t=1$, where such systems exist if and only if $k$ divides $n$.
These systems are known as \emph{spreads} in finite geometries and they will be used in Section~\ref{sec:recursion}.
Thomas~\cite{Tho96} showed that certain kind of $q$-Steiner
systems $\dS_2(2,3,7)$ cannot exist. Metsch~\cite{Met99} conjectured
that nontrivial $q$-Steiner systems with $t \geq 2$ do not exist.
The concept of $q$-Steiner systems appeared also in connection of diameter perfect
codes in the Grassmann scheme. It was proved in~\cite{AAK01}
that the only diameter perfect codes in the Grassmann scheme
are the $q$-Steiner systems.
Recently, the first $q$-Steiner system $\dS_q(t,k,n)$
with $t \geq 2$ was found.
This is a $q$-Steiner system $\dS_2(2,3,13)$ which have a large
automorphism group~\cite{BEOVW}. Using $q$-analog of derived and residual designs
it was proved that sometimes the necessary conditions for the existence
of a $q$-Steiner system $\dS_q(t,k,n)$ are not sufficient~\cite{KiLa15}.
The first set of parameters ($t$, $k$, and $n$) for which the existence question of $q$-Steiner systems
is not settled is the parameters for the $q$-analog
of the Fano plane, i.e. the $q$-Steiner systems $\dS_q(2,3,7)$, which
will be called also in this paper the $q$-\emph{Fano plane}. There was a lot of effort to
find whether the $q$-Fano plane, especially for $q=2$, exists or does not exist, e.g.~\cite{BKN15,EtVa11a,Tho96}
All these attempts didn't provide any answer for the existence question. It was proved recently
in~\cite{BKN15} that if such system exists for $q=2$, then its automorphism group has a small order.


In this paper we present a completely new approach to examine the existence of $q$-Steiner systems.
This approach is based on the structure obtained by puncturing some coordinates from all the subspaces of the possible
$q$-Steiner system. This is equivalent to say that the projection of the other coordinates is considered
for all the subspaces of the system. This idea was suggested first in~\cite{Etz13} and this paper
completes and proves all the ideas mentioned in~\cite{Etz13}.
The sizes of punctured subspaces and the numbers involved are sometimes the same as
those in~\cite{KiPa15}, where intersection numbers of combinatorial designs were considered.
But, the objects considered in these two papers are different and the results are different.
We consider (and define) this structure, obtained by puncturing all the subspaces
of the system, as a new type of design, which exists if
the related $q$-Steiner system exists, but could exist even if the
related $q$-Steiner system does not exist. If this design does not exist,
then the related $q$-Steiner system does not exist.
To highlight our main contributions in this paper are:
\begin{enumerate}
\item A definition of a new method to examine the existence of a $q$-Steiner system.

\item A definition for a new type of designs which are close to $q$-Steiner systems
and their construction might be a first step to find the related $q$-Steiner system.
Some constructions for these designs are given.

\item A method which hopefully will improve our understanding of the structure of the $q$-Fano plane for $q \geq 2$,
and maybe will help to find such a structure or to prove its nonexistence.
Indeed, the method in this paper led to a breakthrough, in this area, presented in~\cite{EtHo17}, i.e.
a construction for a punctured $q$-Fano plane (or so called residual $q$-Fano plane) for all prime powers $q \geq 2$.
\end{enumerate}

The rest of this paper is organized as follows. In Section~\ref{sec:punctured},
the definition of punctured $q$-Steiner systems and other related definitions,
are presented. We prove some properties of punctured
systems, define the new type of design, and examine some of its properties.
An inverse operation for puncturing and related operations are also presented and the
number of subspaces which are generated by the inverse operation are computed.
In Section~\ref{sec:system}, a system of equations, which form the necessary
conditions for the existence of the related punctured $q$-Steiner system, is presented. These systems of equations are
obtained by precise enumeration of covering $t$-subspaces by $k$-subspaces in the the
$q$-Steiner system as reflected by the punctured system. In Section~\ref{sec:examples},
a sequence of examples for punctured $q$-Steiner systems $\dS_q(k-1,k,n)$,
i.e. a sequence of examples for the new defined design, is presented.
In Section~\ref{sec:recursion}, a recursive construction for punctured $q$-Steiner systems
$\dS_q(2,3,n)$ is presented. One of the important ingredients, for this construction, is a large set of spreads.
Conclusions are given in Section~\ref{sec:conclude}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Punctured $q$-Steiner Systems}
\label{sec:punctured}

Given an $n \times m$ matrix $A$, the \emph{punctured} matrix $A'$ is an $n \times (m-1)$
matrix obtained from~$A$ by deleting one of the columns from~$A$. Codes and punctured
codes in the Hamming space are well established in coding theory~\cite[pp. 27-32]{McSl77}.
A $q$-analog of punctured codes for subspace codes (codes whose codewords are
subspaces such as the Grassmannian codes),
was defined in~\cite{EtSi09}, but this is not the puncturing considered in this paper.

A subspace $X \in \cG_q(n,k)$, i.e. a $k$-subspace of $\F_q^n$, consists of
$q^k$ vectors of length $n$ with elements taken from $\F_q$.
The punctured subspace $X'$ by the $i$th coordinate is defined
as the subspace obtained from $X$ by deleting coordinate $i$ in all the vectors of $X$.
The result of this puncturing is a new subspace of
$\F_q^{n-1}$. If $X$ does not contain the unity vector with an \emph{one} in the $i$th coordinate, $e_i$,
then $X'$ is a subspace in $\cG_q(n-1,k)$. If $X$ contains the unity vector with a \emph{one} in the $i$th coordinate,
then $X'$ is a subspace in $\cG_q(n-1,k-1)$.
Assume that we are given a set $\dS$ of subspaces from $\cG_q(n,k)$. The \emph{punctured set}
$\dS'$ is defined as $\dS' = \{ X' ~:~ X \in \dS \}$, where all subspaces are
punctured in the same coordinate, and it can contain subspaces only from
$\cG_q(n-1,k)$ or from $\cG_q(n-1,k-1)$. The set~$\dS'$ is regarded as multi-set and hence $|\dS'|=|\dS|$
(since two distinct $k$-subspaces of $\F_q^n$ can be punctured into the same $k$-subspaces of $\F_q^{n-1}$).
When the punctured coordinate is not mentioned it will be assumed that the last coordinate was punctured.
A subspace can be punctured several times. A $k$-subspace~$X$, of~$\F_q^n$, is
punctured $p$ times ($p$-\emph{punctured}) to a $p$-\emph{punctured subspace}~$Y$
of $\F_q^{n-p}$. The subspace~$Y$ can be an $s$-subspace for any $s$
such that $\max \{ 0, k-p \} \leq s \leq \min \{ k, n-p \}$.
Similarly we define a $p$-\emph{punctured set}. We summarize this brief
introduction on punctured subspaces with the main observation.

\begin{lemma}
\label{lem:1-punctured}
A $k$-subspace of $\F_q^n$, $k >0$, is punctured either into a $k$-subspace or into a $(k-1)$-subspace of $\F_q^{n-1}$.
A $k$-subspace of $\F_q^n$ is $p$-punctured into an $s$-subspace such that
$\max \{ 0, k-p \} \leq s \leq \min \{ k, n-p \}$.
\end{lemma}

If $\dS$ is a $q$-Steiner system $\dS_q(t,k,n)$, we would like to know if the $p$-punctured system~$\dS'$
has some interesting properties, i.e. $\dS'$ has some uniqueness properties
related to the punctured $k$-subspaces and the punctured (contained)
$t$-subspaces. The motivation is to define a new set of designs which must exist
if the related $q$-Steiner systems $\dS_q(t,k,n)$ exist. But, these new designs can exist even if the
related $q$-Steiner systems do not exist. If the nonexistence of such designs can be proved,
then the related $q$-Steiner systems won't exist too. On the other hand, the existence of such a design
might lead to a construction for the related $q$-Steiner system.

For puncturing there is an inverse operation called \emph{extension}.
A related operation for our discussion, which is completely of a different nature from extension, is
the \emph{expansion}. These two operations are defined next.

A $t$-subspace $X$ of $\F_q^m$ is \emph{extended} to a $t'$-subspace $Y$ of $\F_q^{m'}$, where
$t' \geq t$, $m'>m$, and $m'-m \geq t'-t$, if $X$ is the subspace obtained from $Y$ by
puncturing $Y$ $m'-m$ times. Note, that the \emph{extension} of a subspace is not always unique, as we will
prove in the sequel (see lemma~\ref{lem:addNone}), but there is always a unique outcome for puncturing. In other words, a
$p$-punctured $t$-subspace $X$ of $\F_q^m$
can be obtained from a few different $t'$-subspaces of $\F_q^{m+p}$.
The new columns are added as the last columns of extended subspace. But, similarly to
puncturing, they can added theoretically between any set of columns.
To make the paper consistent, we will make the extensions only to the end of the
columns of the related subspaces, unless otherwise is specifically stated.

To prove our claims we will need some general way to represent subspaces,
in such a way that the representation of the punctured subspace $X'$ will be derived directly
from the representation of the subspace $X$. For this purpose two different
representations will be used for a $k$-subspace $X$ of $\F_q^m$.
The first representation is by an $(q^k-1) \times m$ matrix which contains
the $q^k-1$ nonzero vectors of $X$. Each nonzero vector of $X$ is a row in this matrix.
% The second representation
%is by an $\frac{q^k-1}{q-1} \times m$ matrix which contains
%one representative vector from each 1-subspace of $X$.
The second representation is by
a $k \times m$ matrix which is the generator matrix for $X$ in reduced row echelon form.
A $k \times n$ matrix with rank $k$ is in {\it reduced row echelon
form} if the following conditions are satisfied.
\begin{itemize}
\item The leading coefficient of a row is always to the right of
the leading coefficient of the previous row.

\item All leading coefficients are {\it ones}.

\item Every leading coefficient is the only nonzero entry in its
column.
\end{itemize}

The next definition of virtual subspace is essential in understanding our exposition.
An $r$-subspace $Y$ of $\F_q^m$ is called a \emph{virtual} $k$-\emph{subspace} of $\F_q^m$,
$r \leq k$, if $Y$ was punctured from a $k$-subspace $X$
of $\F_q^n$, $n>m$ and it is represented by a $(q^k-1) \times m$ matrix which
represents the actual outcome when $Y$ was punctured. In other words the representation of $Y$ is
obtained by the deleting the last $n-m$ columns from the $(q^k-1) \times n$ matrix which
represents $X$. It is important to understand that $Y$ has exactly one representation
as a virtual $k$-subspace, no matter from which subspace it was punctured.
Using this representation, $Y$ has $\sbinomq{k}{t}$ $t$-subspaces for each
$0 \leq t \leq k$, some of them are identical and some of them are virtual (see Example~\ref{ex:virtual}).
This will be used later in our enumerations.
Note, that with the virtual $k$-subspace of the punctured subspace, it is easier to see how
the $t$-subspaces were punctured. This is easily seen in Example~\ref{ex:virtual}.
Finally, note that a $k$-subspace of $\F_q^m$ is always also a virtual $k$-subspace
of $\F_q^m$, where both have the same matrix representation.

An $r$-subspace $X$ of $\F_q^m$ is \emph{expanded} to a (virtual) $k$-subspace $Y$ of $\F_q^m$, $r \leq k$, if
$X$ can be obtained by puncturing a $k$-subspace $Z$, and $Y$ is the representation of $X$
by a $(q^k-1) \times m$ matrix after the
puncturing. The virtual $k$-subspace $Y$ is also called the $k$-\emph{expansion} of $X$.

%A $t$-subspace $X$ of $\F_q^m$ is extended and expended to a virtual $k$-subspace, $k>t$, of $\F_q^n$, $n>m$,
%if it is extended to a subspace in $\F_q^n$ and then expanded to a $k$-subspace.

\begin{lemma}[\bf from a $t$-subspace to a $t$-subspace, extension of one column]
\label{lem:addNone}
If $X$ is a $t$-subspace of $\F_q^m$, then it can be extended
in exactly $q^t$ distinct ways to a $t$-subspaces of $\F_q^{m+1}$.
\end{lemma}
\begin{proof}
Any one of the $q^t$ distinct linear combinations of the columns of $X$ can be appended as the new $(m+1)$th column and
each such linear combination, appended as the $(m+1)$th column, yields a different $t$-subspace of $\F_q^{m+1}$.
\end{proof}

\begin{example}
Let $X$ be the following 2-subspace of $\F_2^4$ represented by the $3 \times 4$ matrix,
$$
X=\begin{array}{c}
0100 \\
0010 \\
0110
\end{array}~,
$$
It can be extended in exactly 4 distinct ways to 2-subspaces of $\F_2^5$, represented by the $3 \times 5$ matrices,
$$
\begin{array}{c}
01000 \\
00100 \\
01100
\end{array}, ~~
\begin{array}{c}
01001 \\
00100 \\
01101
\end{array},~~
\begin{array}{c}
01000 \\
00101 \\
01101
\end{array},~~
\begin{array}{c}
01001 \\
00101 \\
01100
\end{array} ~.
$$
\end{example}

\begin{lemma}[\bf from $t$-subspace to $(t+1)$-subspace, extension of one column]
\label{lem:addOne}
If $X$ is a $t$-subspace of $\F_q^m$, then it can be extended
in exactly one way to a $(t+1)$-subspace of~$\F_q^{m+1}$.
\end{lemma}
\begin{proof}
Any extension which increase the dimension by one is equivalent to first adding a column of
zeroes to the existing $t$-subspace $X$ to form the $t$-subspace $\hat{X}$ of $\F_q^{m+1}$.
Then the only extension to a $(t+1)$-subspace is $\Span{\hat{X},e_{m+1}}$, where $\Span{Z}$
denotes the linear span of~$Z$.
\end{proof}

\begin{example}
\label{ex:virtual}
Let $X$ be the following 2-subspace of $\F_2^4$ represented by the $3 \times 4$ matrix,
$$
X=\begin{array}{c}
0100 \\
0010 \\
0110
\end{array} ~,
$$
and let
$$
Y=\begin{array}{c}
01000 \\
00100 \\
01100
\end{array}~,
$$
be one of its extensions to a 2-subspace of $\F_2^5$ represented by the $3 \times 5$ matrix.
$X$ can be extended in a unique way to a 3-subspace of $\F_2^5$, and $Y$ has a unique representation as
a virtual 3-subspace (up to permutations of rows). They are represented by the two $7 \times 5$ matrices, respectively,
$$
\begin{array}{c}
01000 \\
00100 \\
01100 \\
01001 \\
00101 \\
01101 \\
00001
\end{array}, ~~
\begin{array}{c}
01000 \\
00100 \\
01100 \\
01000 \\
00100 \\
01100 \\
00000
\end{array}~.
$$
The extended 3-subspace contains the following seven 2-subspaces
$$
\begin{array}{c}
01000 \\
00100 \\
01100
\end{array}, ~~
\begin{array}{c}
01000 \\
00101 \\
01101
\end{array},~~
\begin{array}{c}
00100 \\
01001 \\
01101
\end{array},~~
\begin{array}{c}
01100 \\
01001 \\
00101
\end{array},~~
\begin{array}{c}
01000 \\
01001 \\
00001
\end{array},~~
\begin{array}{c}
00100 \\
00101 \\
00001
\end{array},~~
\begin{array}{c}
01100 \\
01101 \\
00001
\end{array},
$$
while the virtual 3-subspace contains the following related seven 2-subspaces, from which three are virtual
(note that the distinction between the two sets of seven subspaces is the last column),
$$
\begin{array}{c}
01000 \\
00100 \\
01100
\end{array}, ~~
\begin{array}{c}
01000 \\
00100 \\
01100
\end{array},~~
\begin{array}{c}
00100 \\
01000 \\
01100
\end{array},~~
\begin{array}{c}
01100 \\
01000 \\
00100
\end{array},~~
\begin{array}{c}
01000 \\
01000 \\
00000
\end{array},~~
\begin{array}{c}
00100 \\
00100 \\
00000
\end{array},~~
\begin{array}{c}
01100 \\
01100 \\
00000
\end{array}~.
$$
\end{example}

Finally, in this section we consider the outcome of puncturing a $q$-Steiner systems
and some properties of the related puncturing. For this purpose we need to use
the following well-known equation~\cite[p. 444]{McSl77}.

\begin{lemma}
\label{eq:gauss1}
If $1 \leq k \leq n-1$, then $\sbinomq{n}{k} = q^k \sbinomq{n-1}{k} + \sbinomq{n-1}{k-1}$, where
$\sbinomq{n}{0} = \sbinomq{n}{n} =1$.
\end{lemma}

\begin{theorem}
\label{thm:Sd1}
If $\dS$ is a $q$-Steiner system $\dS_q(t,k,n)$, then the punctured system $\dS'$
contain exactly $\frac{\sbinomq{n-1}{t-1}}{\sbinomq{k-1}{t-1}}$ distinct $(k-1)$-subspaces
which form a $q$-Steiner system $\dS_q(t-1,k-1,n-1)$, denoted by $\tilde{\dS}$. Each $t$-subspace of $\F_q^{n-1}$
which is contained in a $(k-1)$-subspace of $\tilde{\dS}$ is not contained
in any of the $k$-subspaces of $\dS'$.
Each $t$-subspace of $\F_q^{n-1}$ which is not contained in a $(k-1)$-subspace of $\tilde{\dS}$,
appears exactly $q^t$ times in the $k$-subspaces of $\dS'$.
\end{theorem}
\begin{proof}
By Lemma~\ref{lem:1-punctured}, $\dS'$ can contain only $(k-1)$-subspaces and $k$-subspaces.
A~$k$-subspace which contains the unity vector with a \emph{one} in the last coordinate
is punctured into a $(k-1)$-subspace, while other $k$-subspaces are punctured into $k$-subspaces.

Let $X$ be a $(t-1)$-subspace of $\F_q^{n-1}$. By Lemma~\ref{lem:addOne}, there is a unique way
to extend it to a $t$-subspace $Y$ of $\F_q^n$. Therefore, since $\dS$ is a $q$-Steiner system $\dS_q(t,k,n)$, it follows
that $Y$ is contained in exactly one $k$-subspace $Z$ of $\dS$. Clearly, $Z$ is a $k$-subspace
in $\F_q^n$ which contains the unity vector with a \emph{one} in the last coordinate.
Hence, $Z$ is punctured into a $(k-1)$-subspace $Z'$ which is the only $(k-1)$-subspace
of $\dS'$ containing $X$. Therefore, all the $k$-subspaces of $\dS$ which contain
the unity vector with a \emph{one} in the last coordinate are punctured into
a $q$-Steiner system $\dS_q(t-1,k-1,n-1)$.


Let $Z$ be a $k$-subspace of $\F_q^n$ which contains $\Span{e_n}$. The
virtual $k$-subspace, obtained from the punctured $(k-1)$-subspace $Z'$,
contains $\sbinomq{k}{t}$ $t$-subspaces, some of them are identical
and some of them are virtual $t$-subspaces (see Example~\ref{ex:virtual}).
Since $\Span{e_n} \subset Z$ it follows that $Z$ has $\sbinomq{k-1}{t-1}$ $t$-subspaces
which contains $\Span{e_n}$ and hence $\sbinomq{k}{t}-\sbinomq{k-1}{t-1}$ $t$-subspaces
which do not contain $\Span{e_n}$. These are the only $t$-subspaces contained in $Z$.
Since $\Span{e_n} \subset Z$ it follows that $Z'$ is a $(k-1)$-subspace and hence it has
$\sbinomq{k-1}{t}$ distinct $t$-subspaces. The $\sbinomq{k}{t}-\sbinom{k-1}{t-1}$ $t$-subspaces
of $Z$ which do not contain $\Span{e_n}$ are punctured, and each $(t-1)$-subspace obtained in
this way is obtained the same amount of times in the set of punctured $(t-1)$-subspaces.
Therefore, each such $(t-1)$-subspace is contained $\frac{\sbinomq{k}{t}-\sbinomq{k-1}{t-1}}{\sbinomq{k-1}{t}}$
times in the punctured $t$-subspaces of $\F_q^{n-1}$ obtained from $\dS$.
By Lemma~\ref{eq:gauss1} we have $\frac{\sbinomq{k}{t}-\sbinomq{k-1}{t-1}}{\sbinomq{k-1}{t}}=q^t$
(by Lemma~\ref{lem:addNone} these are exactly all their appearances and hence no one could have appeared more times).

By Lemma~\ref{lem:addNone}, each $t$-subspace of $\F_q^{n-1}$ can be extended in $q^t$
distinct ways to a $t$-subspace of $\F_q^n$.
This implies, that each $t$-subspace which is not contained in $\tilde{\dS}$,
appears exactly $q^t$ times in the other $k$-subspaces of $\dS'$. Simple counting shows
that we have covered all the subspaces of the punctured system,
which completes the proof of the theorem.
\end{proof}

\begin{corollary}
\label{cor:Sd1}
If $\dS$ is a $q$-Steiner system $\dS_q(k-1,k,n)$, then the punctured system $\dS'$
has a set $\tilde{\dS}$ with $\frac{\sbinomq{n-1}{k-2}}{\sbinomq{k-1}{k-2}}$ different $(k-1)$-subspaces
which form a $q$-Steiner system $\dS_q(k-2,k-1,n-1)$. Each other $(k-1)$-subspace
which is not contained in $\tilde{\dS}$, appears exactly $q^{k-1}$ times in the $k$-subspaces of $\dS'$.
\end{corollary}

We note, that the $q$-Steiner system $\dS_q(t-1,k-1,n-1)$ of Theorem~\ref{thm:Sd1}
is the same as the one constructed in~\cite{ScEt}. In~\cite{ScEt}, two subspaces
$U_1$ and $U_{n-1}$ are chosen, where $U_i$ has dimension $i$ and $U_{n-1} + U_1 = \F_q^n$.
If $\dS$ is a $q$-Steiner system $\dS_q(t,k,n)$,
then the subset $\{ X \cap U_{n-1} ~:~ X \in \dS, ~ U_1 \subset X \}$ is
$q$-Steiner system $\dS_q(t-1,k-1,n-1)$. Our punctured system is obtained when
$e_n \in U_1$ and $U_{n-1}$ is the $(n-1)$-subspace of $\F_q^n$ which contains all
the vectors whose last coordinate is a \emph{zero}.
The extra factor of Theorem~\ref{thm:Sd1} are
the $k$-subspaces which do not belong to the $q$-Steiner system.
We note that puncturing is equivalent to the projection
$X \rightarrow (X+U)/U$, where $U$ is a fixed 1-subspace. If $H$ is a hyperplane in $\F_q^n$
and $U$ is a 1-subspace not contained in $H$, then puncturing of a subspace~$X$ is
equivalent to $H \cap \Span{X,U}$.


The first goal of this paper is to define a new type of design $\dS_q(t,k,n;m)$ which
contains the possible subspaces punctured from a $q$-Steiner system $\dS_q(t,k,n)$.
This is done in the following definition.

\begin{definition}
A $p$-\emph{punctured} $q$-\emph{Steiner system} $\dS_q(t,k,n;m)$, $m=n-p$,
is a multi-set~$\dS$ of subspaces of $\F_q^m$, satisfying the following two requirements.

\begin{enumerate}
\item The number of subspaces in $\dS$ is the same as the number of subspaces in
a $q$-Steiner system $\dS_q(t,k,n)$.

\item Let $\tilde{\dS}$ be a system which contains the virtual $k$-subspaces
of the subspaces in $\dS$ ($\dS$ and $\tilde{\dS}$ have the same size).
Let $\T$ be the set of all $t$-subspaces of $\F_q^n$ and $\T'$ be the set
of all $p$-punctured $t$-subspaces of $\F_q^m$. For each subspace $X \in \T'$ let
$$\lambda (X) = |  \{ Y ~:~ Y \in \T , ~ X ~ \text{is a}~ p\text{-punctured}~ t\text{-subspace of} ~ Y  \} |~.$$
It is required that for each $X \in \T'$, $X$ will be appear $\lambda (X)$ times as a virtual
$t$-subspace in the virtual $k$-subspaces of $\tilde{\dS}$.
\end{enumerate}
\end{definition}

%\begin{definition}
%A $p$-\emph{punctured} $q$-\emph{Steiner system} $\dS_q(t,k,n;m)$, $m=n-p$, is a multi-set $\dS$ of subspaces of $\F_q^m$,
%in which each $t$-subspace of $\F_q^n$ can be obtained exactly once by extending
%$p$ times all the subspaces of $\dS$, where the appearances of the same
%subspace of $\F_q^m$ in $\dS$ are extended together (in parallel) for this purpose.
%The appearances of distinct subspaces of $\F_q^m$ in $\dS$ are extended in a sequence,
%where the order of the different subspaces of $\dS$ in this sequence is arbitrary.
%\end{definition}

\begin{example}
Let $\dS$ be a system which consists of 336 1-subspaces and 45 0-subspaces of~$\F_2^1$.
There are $\sbinomtwo{6}{2} =651$ 2-subspaces of $\F_2^7$ whose first column is the all-zero column.
Each extension of an 1-subspace of $\F_2^1$ will contribute one 2-subspaces of $\F_2^7$
whose first column is all-zero, while
each extension of a 0-subspace of $\F_2^1$ will contribute seven 2-subspaces of $\F_2^7$
whose first column is all-zero. Hence, the extension produces $336+45 \cdot 7 =651$
such subspaces as required. The same goes for the other 2-subspaces and hence $\dS$ is
a 6-punctured $q$-Steiner system $\dS_2(2,3,7;1)$.
\end{example}

The following lemma can be easily verified..
\begin{lemma}
\label{lem:punct_punct}
If there exists a $p$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$, $1 < m \leq n$, then
there exists a $(p+1)$-punctured $q$-Steiner system $\dS_q(t,k,n;m-1)$.
\end{lemma}


The following theorem is given for a punctured $q$-Steiner system $\dS_q(t,k,n;n-1)$.
It can be generalized to other $p$-punctured $q$-Steiner systems, $p>1$. For simplicity
and since the case $p=1$ is the most informative
we prove only this case.

%In several proofs we will need to use concatenation of two matrices. Let $X_1$ and $X_2$
%be two $\ell \times m_1$ and $\ell \times m_2$ matrices, respectively. The
%\emph{concatenation} of $X_1$ and $X_2$, $X_1 \circ X_2$ ($X_1$ or $X_2$ can be also columns)
%is an $\ell \times (m_1 + m_2)$ matrix whose first $m_1$ columns is $X_1$ and its
%last $m_2$ columns is $X_2$.

\begin{theorem}
\label{thm:diff_punc}
If $\dS'$, a punctured $q$-Steiner system $\dS_q(t,k,n;n-1)$, $1 < t < k <n$, was
obtained by puncturing a $q$-Steiner system $\dS_q(t,k,n)$, then all subspaces
of $\dS'$ are distinct.
\end{theorem}
\begin{proof}
Let $\dS$ be a $q$-Steiner system $\dS_q(t,k,n)$.
By Theorem~\ref{thm:Sd1}, all the $(k-1)$-subspaces of $\dS'$,
the punctured $q$-Steiner systems $\dS_q(t,k,n;n-1)$,
are distinct since they form a $q$-Steiner system $\dS_q(t-1,k-1,n-1)$.
Hence, we only have to prove that there are no two
equal $k$-subspaces in $\dS'$.

Let $X,Y \in \dS$, $H$ an hyperplane in $\F_q^n$ and $U$ a 1-subspace not contained
in $X$, $Y$, and~$H$. Clearly,
$$
\dim ((H \cap \Span{X,U}) \cap (H \cap \Span{Y,U})) = \dim (\Span{X,U} \cap \Span{Y,U} ) -1 \leq \dim (X \cap Y) +1 \leq t<k,
$$
which completes the proof.
\end{proof}


\section{System of Equations}
\label{sec:system}

Corollary~\ref{cor:ness} yields a set of necessary conditions for the existence of a $q$-Steiner system $\dS_q(t,k,n)$.
Similar necessary conditions can be derived for any $p$-punctured
$q$-Steiner system. Some of these conditions yield new interesting equations which must be satisfied.
In this section we will derive these new necessary conditions.

Let $\tilde{\dS}$ be an $(n-m)$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$ and let $p=n-m$, i.e. $\dS_q(t,k,n;m)$
is a $p$-punctured $q$-Steiner system. We start with two simple lemmas which are implied by our
previous discussion on punctured subspaces. The first lemma is an immediate
consequence of Lemma~\ref{lem:1-punctured}.


\begin{lemma}[\bf dimension of subspaces to be covered]
\label{lem:s_dim}
Suppose $\dS$ is a $q$-Steiner system $\dS_q(t,k,n)$. Let $\T$ be the set of $t$-subspaces
which are covered by the blocks of $\dS$. Then in the $p$-punctured $q$-Steiner
system $\dS_q(t,k,n;m)$, $p=n-m$, derived from $\dS$, each element of $\T$ corresponds to
a $p$-punctured $s$-subspace, where $\max \{0,t-p\} \leq s \leq \min \{t,m\}$.
\end{lemma}


\begin{lemma}[\bf dimension of subspaces which cover the $p$-punctured $s$-subspaces]
\label{lem:r_dim}
Suppose $\dS$ is a $q$-Steiner system $\dS_q(t,k,n)$.
Let $\T$ be the $t$-subspaces which are covered by the blocks of $\dS$.
Then in the $p$-punctured $q$-Steiner
system $\dS_q(t,k,n;m)$, $p=n-m$, derived from $\dS$, each element of $\T$ corresponds to
a $p$-punctured $s$-subspace, covered by a $p$-punctured $r$-subspace,
where $\max \{ k-p,s \} \leq r \leq \min \{k-t+s,m\}$.
\end{lemma}
\begin{proof}
The lower bound is a consequence of Lemma~\ref{lem:1-punctured} and the fact
that an $s$-subspace cannot be covered by a subspace of a smaller dimension.
Since the subspaces of $\dS_q(t,k,n;m)$ are subspaces of $\F_q^m$, it follows that
$r \leq m$. Finally, if a $t$-subspace $X$ was punctured to an $s$-subspace then
the $k$-subspace $Y$ which covers $X$ must also be reduced by at least $t-s$ times
in its dimension and hence $r \leq k-t+s$.
\end{proof}

We are now in a position to describe a set of equations, related to the
$p$-punctured ${q\text{-Steiner}}$ system $\dS_q(t,k,n;m)$, which must be satisfied
if the $p$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$ exists.
Each $s$-subspace $X$ of $\F_q^m$, $\max \{0,t-p\} \leq s \leq \min \{t,m\}$, yields
one equation related to the way it is covered by $\dS_q(t,k,n;m)$.
Each $r$-subspace $Y$ of $\F_q^m$, $\max \{ k-p,0 \} \leq r \leq \min \{k,m\}$,
yields one nonnegative integer variable, $a_Y$, which is the number of appearances of $Y$ in
the $p$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$. In the equation
for the $s$-subspace $X$ we have a linear combination of the variables for the ${r\text{-subspaces}}$
of $\F_q^m$ which contain $X$.

\begin{example}
Assume that we want to examine the 5-punctured $q$-Steiner system $\dS_2(2,3,7;2)$.
Clearly, by Lemma~\ref{lem:s_dim}, the 2-subspaces of $\F_2^7$ were punctured to $s$-subspaces of~$\F_2^2$,
where $0 \leq s \leq 2$. There is exactly one 0-subspace, three 1-subspaces, and one
2-subspaces, of~$\F_2^2$, represented as virtual 2-subspaces by the following five
$3 \times 2$ matrices.
$$
\begin{array}{c}
00 \\
00 \\
00
\end{array}, ~~
\begin{array}{c}
10 \\
10 \\
00
\end{array},~~
\begin{array}{c}
01 \\
01 \\
00
\end{array},~~
\begin{array}{c}
11 \\
11 \\
00
\end{array},~~
\begin{array}{c}
01 \\
10 \\
11
\end{array}~.
$$
Clearly, by Lemma~\ref{lem:r_dim} these s-subspaces of $\F_2^7$ are covered by $r$-subspaces of~$\F_2^2$,
where $0 \leq r \leq 2$. There is exactly one 0-subspace, three 1-subspaces, and one
2-subspaces, of~$\F_2^2$, represented as virtual 3-subspaces by the following five
$7 \times 2$ matrices.
$$
X=\begin{array}{c}
00 \\
00 \\
00 \\
00 \\
00 \\
00 \\
00
\end{array}, ~~
Y=\begin{array}{c}
10 \\
10 \\
10 \\
10 \\
00 \\
00 \\
00
\end{array},~~
Z=\begin{array}{c}
01 \\
01 \\
01 \\
01 \\
00 \\
00 \\
00
\end{array},~~
U=\begin{array}{c}
11 \\
11 \\
11 \\
11 \\
00 \\
00 \\
00
\end{array},~~
V=\begin{array}{c}
01 \\
01 \\
10 \\
10 \\
11 \\
11 \\
00
\end{array}~.
$$
Therefore, we have 5 variables $a_X$, $a_Y$, $a_Z$, $a_U$, and $a_V$. The system of equations
consists of the following five equations:
$$
\begin{array}{c}
155 = 7 \cdot a_X +a_Y + a_Z + a_U \\
496 = 6 \cdot a_Y + a_V \\
496 = 6 \cdot a_Z + a_V \\
496 = 6 \cdot a_U + a_V \\
1024 = 4 \cdot a_V
\end{array}~.
$$
The first equation is constructed as follows: there are $\sbinomtwo{5}{2}=155$
2-subspaces whose first two columns are \emph{zeroes}. For all the seven 2-subspaces
resulting from the virtual 3-subspace~$X$ the first two columns are \emph{zeroes}. Only for one such 2-subspaces
resulting from $Y$, $Z$, or $U$ the first two columns are \emph{zeroes}.
This explains the first equation. The other four equations are constructed in a similar way.
There is a unique solution for this set of equations, $a_X=5$, $a_Y=a_Z=a_U=40$, and $a_V=256$,
and hence the 5-punctured $q$-Steiner system $\dS_2(2,3,7;2)$ exists.
\end{example}

The variables which appear in each equation and their coefficients in the equation
should be computed in advance as will be done next.
First we have to compute the number of $t$-subspaces in $\F_q^n$
which are formed by extending an $s$-subspace $X$ of $\F_q^m$.
Let $N_{(s,m),(t,n)}$ be the number of distinct $t$-subspaces in
$\F_q^n$ which are formed by extending a given $s$-subspace $X$ of $\F_q^m$.

\begin{example}
Let $X$ be the following 2-subspace of $\F_2^5$ represented by the $3 \times 5$ matrix,
$$
X=\begin{array}{c}
01001 \\
00101 \\
01100
\end{array} ~.
$$
It can be extended to the following $N_{(2,5),(3,7)}=12$ 3-subspaces of $\F_2^7$ represented by the $7 \times 7$ matrices,
$$
\begin{array}{c}
0100100 \\
0010100 \\
0110000 \\
0100101 \\
0010101 \\
0110001 \\
0000001
\end{array},~~
\begin{array}{c}
0100110 \\
0010110 \\
0110000 \\
0100111 \\
0010111 \\
0110001 \\
0000001
\end{array},~~
\begin{array}{c}
0100110 \\
0010100 \\
0110010 \\
0100111 \\
0010101 \\
0110011 \\
0000001
\end{array},~~
\begin{array}{c}
0100100 \\
0010110 \\
0110010 \\
0100101 \\
0010111 \\
0110011 \\
0000001
\end{array},~~
\begin{array}{c}
0100100 \\
0010100 \\
0110000 \\
0100110 \\
0010110 \\
0110010 \\
0000010
\end{array},~~
\begin{array}{c}
0100101 \\
0010100 \\
0110001 \\
0100111 \\
0010110 \\
0110011 \\
0000010
\end{array},~~
$$
$$
\begin{array}{c}
0100100 \\
0010101 \\
0110001 \\
0100110 \\
0010111 \\
0110011 \\
0000010
\end{array},~~
\begin{array}{c}
0100101 \\
0010101 \\
0110000 \\
0100111 \\
0010111 \\
0110010 \\
0000010
\end{array},~~
\begin{array}{c}
0100100 \\
0010100 \\
0110000 \\
0100111 \\
0010111 \\
0110011 \\
0000011
\end{array},~~
\begin{array}{c}
0100101 \\
0010100 \\
0110001 \\
0100110 \\
0010111 \\
0110010 \\
0000011
\end{array},~~
\begin{array}{c}
0100100 \\
0010101 \\
0110001 \\
0100111 \\
0010110 \\
0110010 \\
0000011
\end{array},~~
\begin{array}{c}
0100101 \\
0010101 \\
0110000 \\
0100110 \\
0010110 \\
0110011 \\
0000011
\end{array}~.
$$
\end{example}

Some of the claims in Lemmas~\ref{lem:var1}, \ref{lem:var2}, and \ref{lem:var3}, which follow,
can be proved by using coordinate-free notation. But, we will continue with our
coordinate notation since it is simpler at this point of our exposition.

\begin{lemma}
\label{lem:var1}
If $0<m<n$ and $0 \leq s \leq t$, then $N_{(s,m),(t,n)}=q^{s(n-m-t+s)} \sbinomq{n-m}{t-s}$.
\end{lemma}
\begin{proof}
The $s$-subspace $X$ of $\F_q^m$ is represented by an $s \times m$ matrix $G_1$ in reduced row echelon form.
A $t$-subspace $Y$ formed by extending $X$ to a $t$-subspace
of $\F_q^n$ is represented by a $t\times n$ generator
matrix $G$ in reduced row echelon form. The upper left $s \times m$ matrix of $G$ is the
generator matrix $G_1$ of $X$ and hence $G$ has the following structure.
\begin{large}
\begin{align*}
\left[ \begin{array}{cc}
G_1 & B\\
{\bf 0} & G_2
\end{array}
\right] .
\end{align*}
\end{large}
The new $n-m$ columns (in $G$ relatively to $G_1$), restricted
to the last $t-s$ rows, forms a generator matrix for a $(t-s)$-subspace of $\F_q^{n-m}$. This
$(t-s) \times (n-m)$ generator matrix~$G_2$ is in reduced row echelon form, where the
columns with leading \emph{ones} are the ones in which the dimension is
increased during the extension (see Lemma~\ref{lem:addOne}). This generator matrix can be chosen in
$\sbinomq{n-m}{t-s}$ distinct ways since it forms a $(t-s)$-subspace of $\F_q^{n-m}$.
In the other new $n-m-t+s$ columns of $G$ (columns with no leading \emph{ones})
the dimension is not increased compared to the original $s$-subspace $X$ and
hence they can be chosen (after the columns with the leading \emph{ones} of $G_2$
are fixed; see Lemma~\ref{lem:addNone}) in $q^{s(n-m-t+s)}$ distinct ways. The reason is that $B$ has
$s$ rows and $n-m$ columns from which the entries of $n-m-t+s$ columns can be chosen arbitrarily from $\F_q$.
It leads to a total of $q^{s(n-m-t+s)} \sbinomq{n-m}{t-s}$ distinct ways to form this extension.
Note, that the columns of $G_2$ do not (and need not) contribute to these extensions.
Each $(t-s)$-subspace of $\F_q^{n-m}$ is combined
with the related $s$-subspace in $\F_q^m$ to form a $t$-subspace of $\F_q^n$.
\end{proof}



For a given $s$-subspace $X$ of $\F_q^m$, $N_{(s,m),(t,n)}$ should be equal to the number
of $r$-subspaces in the $p$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$,
$\max \{ k-p,s \} \leq r \leq \min \{k-t+s,m\}$, which contains $X$.
Note, that if $r<k$, then there are $r$-subspaces in $\dS_q(t,k,n;m)$ which contain $X$
more than once, since we should look on the $k$-expansion of the $r$-subspace.
Clearly, for this purpose we also have to consider
the $t$-expansion of the related $s$-subspace~$X$.
Let $C_{(s,t),(r,k)}$ be the number of copies of the $t$-expansion $\tilde{X}$ obtained from the $s$-subspace $X$
in $\F_q^m$ (note that $X$ is $t$-expanded in a unique way),
which are contained in the $k$-expansion $\tilde{Y}$ of an $r$-subspace $Y$ in $\F_q^m$,
such that $X$ is a subspace of $Y$.

\begin{example}
Let $X$ be the following 2-subspace of $\F_2^4$ represented by the $3 \times 4$ matrix,
$$
X=\begin{array}{c}
0100 \\
0010 \\
0110
\end{array} ~.
$$
If $Y=X$, then the 3-expansion $\tilde{Y}$ of $Y$ is represented by $7 \times 4$ matrix,
and one of its extensions $\hat{Y}$ for a 3-subspace is represented by a $7 \times 7$ matrix as follows:
$$
\tilde{Y}=\begin{array}{c}
0100 \\
0010 \\
0110 \\
0100 \\
0010 \\
0110 \\
0000
\end{array} ,~~~
\hat{Y}=\begin{array}{c}
0100000 \\
0010000 \\
0110000 \\
0100101 \\
0010101 \\
0110101 \\
0000101
\end{array} ~.
$$
$\hat{Y}$ contains $C_{(2,2),(2,3)}=4$ 2-subspaces extended from $X$ represented by the $3 \times 7$ matrices,
$$
\begin{array}{c}
0100000 \\
0010000 \\
0110000
\end{array} ,~~
\begin{array}{c}
0100000 \\
0010101 \\
0110101
\end{array} ,~~
\begin{array}{c}
0100101 \\
0010000 \\
0110101
\end{array} ,~~
\begin{array}{c}
0100101 \\
0010101 \\
0110000
\end{array} ~.
$$
\end{example}

\begin{lemma}
\label{lem:var2}
If $0 \leq s \leq t <k$ and $s \leq r \leq k-t+s$, then $C_{(s,t),(r,k)}=\sbinomq{k-r}{t-s} q^{s(k-r-t+s)}$.
\end{lemma}
\begin{proof}
An $r$-subspace $Y$ of $\F_q^m$ can be represented by a $(q^r-1) \times m$ matrix
whose rows are the nonzero vectors of $Y$. This $r$-subspace $Y$ is $k$-expanded in $\F_q^m$
by writing in a $(q^k-1)\times m$ matrix vertically $q^{k-r}$ copies of $Y$ and after them
$(q^{k-r} -1) \times m$ all-zero matrix $Z$. This forms a $(q^k-1) \times m$ matrix
which represents the $k$-expansion of $Y$.
If $Y$ was $p$-punctured from a $k$-subspace $W$ of $\F_q^n$, then $W$ is formed from
the $k$-expansion of $Y$ by concatenating to $Z$ a $(q^{k-r} -1) \times (n-m)$
matrix $\tilde{Z}$ which represent a $(k-r)$-subspace of $\F_q^{n-m}$.
The $k$-subspace of $\F_q^n$ is a direct sum of this
$(k-r)$-subspace in $\F_q^n$ with an extension of $Y$ to an $r$-subspace in~$\F_q^n$,

Similarly, the $s$-subspace $X$, which
is a subspace of $Y$, is extended and expanded to a $(k-r+s)$-subspace by writing in a
$(q^k-1)\times m$ matrix vertically $q^{k-r}$
copies of~$X$ and after them $(q^{k-r} -1) \times m$ all-zero matrix~$Z$. Each $t$-subspace in $\F_q^n$ which
is extended from $X$, in the $q$-Steiner system $\dS_q(t,k,n)$, is constructed by first choosing
a $(t-s)$-subspace from $\tilde{Z}$, which can be done in $\sbinomq{k-r}{t-s}$
different ways. The $(t-s)$-subspace is completed to a $t$-subspace by performing
direct sum with the extension of $X$. The $s$-subspace $X$ can be chosen in a few distinct ways
from the $k$-expansion of $Y$. Each vector from a given
basis of $X$ can be chosen in $q^{k-r}$ distinct ways (since $q^{k-r}$ copies of~$Y$
were written). But, since each vector of~$X$ appears
$q^{t-s}$ times in the $t$-expansion of~$X$, it follows that each choice of~$X$ is chosen
in $(\frac{q^{k-r}}{q^{t-s}})^s$ distinct ways. This implies that
$C_{(s,t),(r,k)}=\sbinomq{k-r}{t-s} (\frac{q^{k-r}}{q^{t-s}})^s=\sbinomq{k-r}{t-s} q^{s(k-r-t+s)}$
\end{proof}

Now, for a given $s$-subspace $X$ of $\F_q^m$, $N_{(s,m),(t,n)}$ should be equal
to the sum over all $r$-subspaces which contain $X$, where $C_{(s,t),(r,k)}$, for a given $r$-subspace $Y$, is multiplied
by $a_Y$ (see the definitions after Lemma~\ref{lem:r_dim}),
the number of appearance of $Y$ in the $p$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$.
For a given $r$, $\max \{ k-p,s \} \leq r \leq \min \{k-t+s,m\}$, let
$D_{s,r,m}$ be the number of $r$-subspaces which contain a given
$s$-subspace in $\F_q^m$. In other words, $D_{s,r,m}$ is the number of variables for $r$-subspaces
which appear in the equation for any given $s$-subspace.


\begin{lemma}
\label{lem:var3}
If $0 \leq s \leq r \leq m$, then $D_{s,r,m}= \sbinomq{m-s}{r-s}$.
\end{lemma}
\begin{proof}
Let $X$ be an $s$-subspace of $\F_q^m$. We enumerate the number of distinct
$r$-subspaces which contain $X$ in $\F_q^m$, by adding linearly independent vectors one by one to $X$.
The first vector can be chosen in $q^m-q^s$ distinct ways, the second in $q^m-q^{s+1}$ distinct ways and the
last in $q^m - q^{r-1}$ different ways, for a total of $\Pi_{i=r-1}^s (q^m-q^i)$ different ways.
Similarly, a given $r$-subspace $Y$ which is formed in this way can be constructed in
$\Pi_{i=r-1}^s (q^r-q^i)$ distinct ways (the first vector can be chosen in $q^r-q^s$ distinct ways and so on).
Hence, the total number of distinct $r$-subspaces formed in this way is
$$\frac{\prod_{i=r-1}^s (q^m-q^i)}{\prod_{i=r-1}^s (q^r-q^i)}=\prod_{i=r-1}^s \frac{q^m-q^i}{q^r-q^i}
=\prod_{i=r-1}^s \frac{q^{m-i}-1}{q^{r-i}-1}=\sbinomq{m-s}{m-r}=\sbinomq{m-s}{r-s}$$
\end{proof}

So far, we have described the computation of the components in the
equations that should be satisfied if a $p$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$ exists.
The solution for the variables must be nonnegative integers. Before we describe the specific
equations, and before we reduce the number of equations
in some cases, we compute the total number of equations and the total number
of variables in the equations for the $p$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$.

\begin{lemma}
\label{lem:num_eq}
The number of equations for the $p$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$, $m=n-p$, is
$$
\sum_{s= \max \{0,t-p\}}^{\min\{t,m\}} \sbinomq{m}{s} ~,
$$
i.e. $\sbinomq{m}{s}$ equations for all the $s$-subspaces of $\F_q^m$,
where $\max \{0,t-p\} \leq s \leq \min \{t,m\}$.
\end{lemma}
\begin{proof}
The range of $s$ is a direct consequence from Lemma~\ref{lem:s_dim}. For each
$s$-subspaces of $\F_q^m$ we have one equation and hence there are $\sbinomq{m}{s}$
equations for each $s$.
\end{proof}

\begin{lemma}
\label{lem:num_var}
The number of variables for the $p$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$, $m=n-p$, is
$$
\sum_{r= \max \{0,k-p\}}^{\min\{k,m\}} \sbinomq{m}{r} ~,
$$
i.e. $\sbinomq{m}{r}$ variables for all the $r$-subspaces of $\F_q^m$,
where $\max \{0,k-p\} \leq r \leq \min \{k,m\}$.
\end{lemma}
\begin{proof}
The range of $r$ is a direct consequence from Lemma~\ref{lem:r_dim} by noting that either $s$ gets the value of $t$ for a given $t$
and if $m < t$ then also $m < k$ and the value of $r$ is at most $m$. For each
$r$-subspaces of $\F_q^m$ we have one variable and hence there are $\sbinomq{m}{r}$
variables for each~$r$.
\end{proof}

\begin{corollary}
If $m \leq t$, then the number of variables is equal to the number of equations,
for the $p$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$. This number is equal to
$$
\sum_{e=0}^m \sbinomq{m}{e} ~.
$$
If the equations are linearly independent, then there is a unique solution to
the set of equations in this case (when the variables
ore not constrained). If the solution consists of nonnegative integers then the
$p$-punctured $q$-Steiner system $\dS_q(t,t+1,n;m)$ exists.
\end{corollary}

\begin{corollary}
If $m = t+2$, then the number of variables
for the $p$-punctured $q$-Steiner system $\dS_q(t,t+1,n;m)$, $m=n-p$, is equal to
$$
\sum_{r=0}^{t+1} \sbinomq{t+2}{r} ~.
$$
The number of equations in this case is equal to
$$
\sum_{s=0}^t \sbinomq{t+2}{s} ~.
$$
If we set the value of the variable which corresponds to the 0-subspace of $\F_q^m$ to be
$\frac{\sbinomq{n-m}{t}}{\sbinomq{k}{t}}$ and the equations are linearly independent,
then there is a unique solution to the set of equations in this case (when the variables
ore not constrained). If the solution consists of nonnegative integers then the
$p$-punctured $q$-Steiner system $\dS_q(t,t+1,n;m)$ exists.
\end{corollary}
\begin{proof}
If the variable related to the 0-subspace of $\F_q^m$ is set to $\frac{\sbinomq{n-m}{t}}{\sbinomq{k}{t}}$, then
all the $\sbinomq{t+2}{1}$ variables related to the 1-subspaces of $\F_q^m$ are equal to 0. Therefore, the
number of equations in the new set of equations is
$$
\sum_{s=1}^t \sbinomq{t+2}{s} ~.
$$
The number of variables which are not assigned with values is this new set of equations is
$$
\sum_{r=2}^{t+1} \sbinomq{t+2}{r} ~.
$$
Clearly, these two summations are equal and the claim follows.
\end{proof}

\begin{corollary}
If $m = t+1$, then the number of variables
for the $p$-punctured $q$-Steiner system $\dS_q(t,t+1,n;m)$, $m=n-p$, is equal to
$$
\sum_{r=0}^{t+1} \sbinomq{t+1}{r} ~.
$$
The number of equations in this case is equal to
$$
\sum_{s=0}^t \sbinomq{t+1}{s} ~.
$$
If we set the value of the variable which corresponds to the 0-subspace of $\F_q^m$ to be
$\frac{\sbinomq{n-m}{t}}{\sbinomq{k}{t}}$ and the equations are linearly independent, then there is a unique solution to
the set of equations in this case (when the variables
ore not constrained). If the solution consists of nonnegative integers then the
$p$-punctured $q$-Steiner system $\dS_q(t,t+1,n;m)$ exists.
\end{corollary}

Note, that if there is a unique solution to the set of equations, then the existence of the
related design, i.e. $p$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$ is not guaranteed yet.
Only if the unique solution is a nonnegative integer solution, then the design exists.
We also did not consider the linear independence of the equations, although it can be proved
in some cases. It is also important to understand that the number of equations and the number
of variables can be large, and in most cases the number of variables is much larger than
the number of equations. In this case there are many free variables, which usually make it even harder
to find if the set of equations have a solution with nonnegative integer values for the variables.

In the sequel we will examine cases, where the set of equations have a solution
with nonnegative integers. In these cases it will be proved that the
$p$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$ exists. In most cases we will consider
\emph{uniform solutions}, i.e. solutions in which for each $r$, the number of $r$-subspaces
in the systems is equal for any two $r$-subspaces of~$\F_q^m$, i.e. the related variables have the same value. The
related design will be called a \emph{uniform design}. For such systems we can reduce
the number of variables and the number of equations. The choice of uniform solution is usually a good choice
when the equations are linearly independent. In such a case the solution is uniform
in many cases.
%It is important to note that
%Lemma~\ref{lem:punct_punct} does not hold for uniform designs, i.e. the punctured
%system of a uniform design is not necessarily uniform.

Let $\dS$ be a uniform $p$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$, $m=n-p$.
Let $Z$ be an $r$-subspace of $\F_q^m$ and let $X_{r,m}$ be the number of appearances
of $Y$ in $\dS$.
The conclusion of our discussion is the following set of equations for uniform designs.


%\vspace{0.3cm}
%
%\noindent
%{\large {\bf Equations for a uniform $p$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$}}

\begin{theorem}[\bf Equations for a uniform $p$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$]
Let $\dS$ be a uniform $p$-punctured $q$-Steiner system $\dS_q(t,k,n;m)$, $m=n-p$.
For each $s$, $\max \{0,t-p\} \leq s \leq \min \{t,m\}$, the following equation must be satisfied.

$$
N_{(s,m),(t,n)} = \sum_{r=\max \{ k-p,s  \} }^{\min \{ k-t+s,m \} }  D_{s,r,m} \cdot C_{(s,t),(r,k)} \cdot X_{r,m}~.
$$
\end{theorem}
\begin{proof}
The left side of the equation is the number of distinct $t$-subspaces in $\F_q^n$
which are formed by extending a given $s$-subspace $Y$ of $\F_q^m$. The right hand side
is summing over all the $r$-subspaces of $\F_q^m$ which contain $Y$ (the range
is obtained from Lemma~\ref{lem:r_dim}), where $D_{s,r,m}$ is the number of $r$-subspaces
which contain $X$, $C_{(s,t),(r,k)}$ is the number of appearances of $Y$ in such a given $r$-subspace,
and $X_{r,m}$ is the number of appearances of each $r$-subspace in~$\dS$.
\end{proof}

%\vspace{0.2cm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Examples for Existing Systems}
\label{sec:examples}

In this section we will give examples of $p$-punctured $q$-Steiner system
$\dS_q (t,k,n;m)$ for various parameters. We start with the 3-punctured
$q$-Fano plane $\dS_q(2,3,7;4)$ and continue with $\dS_q(3,4,8;4)$, $\dS_2(3,4,8;5)$,
$\dS_q(4,5,11;6)$, and $\dS_q(5,6,12;6)$. We conclude with a more general example for
the $k$-punctured $q$-Steiner system $\dS_q (3,4,2k;k)$, $k \equiv 2$ or $4~(\text{mod}~6)$, $k \geq 4$.

\vspace{0.3cm}

\noindent
{\bf The 3-punctured $q$-Steiner system $\dS_q(2,3,7;4)$:}

\vspace{0.1cm}

There are $\sbinomq{4}{s}$ equations
for each $0 \leq s \leq 2$, for a total of $1+(q^3+q^2+q+1)+(q^2+1)(q^2+q+1)$ equations.
There are $\sbinomq{4}{r}$ variables
for each $0 \leq r \leq 3$, for a total of $1+(q^3+q^2+q+1)+(q^2+1)(q^2+q+1) +(q^3+q^2+q+1)$ variables.

For $s=0$, there is a unique equation for the $0$-subspace (the null space) given by
$$
\sbinomq{3}{2} = (q^2+q+1)a +  b_{i_1}+b_{i_2} + \cdots + b_{i_{q^3+q^2+q+1}}~,
$$
where $a$ is the unique variable related to the $0$-subspace, while $b_{i_j}$ is
a variable for an $1$-subspace.
To have a unique solution we must have linearly independent equations in which
the number of variables equals the number of equations.
Hence, we set $a=1$ which implies that $b_{i_j}=0$ for each~$j$.

For $s=1$, there are $q^3+q^2+q+1$ equations related to the $1$-subspaces, where each equation is of the form
$$
q^2 \sbinomq{3}{1} =  (q^2+q)b + c_{i_1}+c_{i_2} + \cdots + c_{i_{q^2+q+1}}~,
$$
where $b$ is a variable related to an $1$-subspace and hence $b=0$, while $c_{i_j}$ is
a variable for a $2$-subspace.

For $s=2$, there are $(q^2+1)(q^2+q+1)$ equations for $2$-subspaces, where each equation is of the form
$$
q^6 \sbinomq{3}{0} = q^2 c + d_{i_1}+d_{i_2} + \cdots + d_{i_{q+1}}~,
$$
where $c$ is a variable related to a $2$-subspace, while $d_{i_j}$ is
a variable related to a $3$-subspace.

This system of equations has a unique solution, which is also a solution for
a uniform design (uniform punctured system), $X_{0,4}=1$, $X_{1,4}=0$, $X_{2,4}=q^2$, and $X_{3,4}=q^4(q-1)$.

\vspace{0.2cm}

\noindent
{\bf The 4-punctured $q$-Steiner system $\dS_q(3,4,8;4)$:}

\vspace{0.1cm}

There are $\sbinomq{4}{s}$ equations
for each $0 \leq s \leq 3$, and
there are $\sbinomq{4}{r}$ variables
for each $0 \leq r \leq 4$.
To have a unique solution, which also forms a uniform design, we set $X_{0,4}=1$
which implies that $X_{1,4}=0$, and the system of equations has
the unique solution, $X_{2,4}=q^2 (q^2+1)$, $X_{3,4}=q^4(q^4-1)$, and $X_{4,4}=q^{12}-q^{11}+q^7$.

\vspace{0.2cm}

\noindent
{\bf The 3-punctured $q$-Steiner system $\dS_q(3,4,8;5)$:}

\vspace{0.1cm}


It is left for the reader to verify that the following set $\T$ is a 3-punctured $q$-Steiner system $\dS_q(3,4,8;5)$.
contains:
\begin{enumerate}
\item One 1-subspace which is punctured into the unique 0-subspace of $\F_q^4$.

\item The $q^2(q^2+1)(q^2+q+1)$ distinct 2-subspaces of $\F_q^5$, which are
punctured into a 2-subspace of $\F_q^4$, each one is contained exactly once in $\T$.

\item The $(q^2+q+1)(q^2+1)$ distinct 3-subspaces of $\F_q^5$, which are
punctured into a 2-subspace of $\F_q^4$, each one is contained $q^4$ times in $\T$.

\item The $q^3 (q^3+q^2+q+1)$ distinct 3-subspaces of $\F_q^5$, which are
punctured into a 3-subspace of $\F_q^4$, each one is contained $q(q^3-1)$ times in $\T$.

\item The $q^3+q^2+q+1$ distinct 4-subspaces of $\F_q^5$, which are
punctured into a 3-subspace of $\F_q^4$, each one is contained $q^7 (q-1)$ times in $\T$.

\item The $q^4$ distinct 4-subspaces of $\F_q^5$, which are
punctured into the unique 4-subspace of $\F_q^4$, each one is contained $q^8-q^7+q^3$ times in $\T$.
\end{enumerate}

\noindent
{\bf The 5-punctured $q$-Steiner system $\dS_q(4,5,11;6)$:}

\vspace{0.1cm}

There are $\sbinomq{6}{s}$ equations
for each $0 \leq s \leq 4$ and
there are $\sbinomq{6}{r}$ variables
for each $0 \leq r \leq 5$.
To have a uniform design we set $X_{0,6}=1$ which implies that $X_{1,6}=0$ and the system of equations
will have a unique solution $X_{2,6}= q^2 (q^2+1)$, $X_{3,6}=q^9+q^7-q^4$,
$X_{4,6}=q^{14}-q^9+q^7$, and $X_{5,6}=(q^{18}+q^{11})(q-1)$.

\vspace{0.2cm}

\noindent
{\bf The 6-punctured $q$-Steiner system $\dS_q(5,6,12;6)$:}

\vspace{0.1cm}


There are $\sbinomq{6}{s}$ equations
for each $0 \leq s \leq 5$ and
there are $\sbinomq{6}{r}$ variables
for each $0 \leq r \leq 6$.
A solution for a uniform design for the system of equations is $X_{0,6}=1$, $X_{1,6}=0$,
$X_{2,6}=q^2 (q^4+q^2+q)$, $X_{3,6}=q^4 (q^8+q^6+q^5-1)$, $X_{4,6}=q^7 (q^{11}+q^9+q^7-q^6+1)$,
$X_{5,6}=q^{11} (q^{13}-q^7+q^6-1)$, and $X_{6,6}=q^{16} (q^{14}-q^{13}+q^7-q^6+1)$.

\vspace{0.2cm}

\noindent
{\bf The $k$-punctured $q$-Steiner system $\dS_q (3,4,2k;k)$, $k \equiv 2$ or $4~(\text{mod}~6)$, $k \geq 4$:}

\vspace{0.1cm}

In this case, we will consider only a possible uniform design.
For this design we have that $X_{0,k}=  \frac{\sbinomq{k}{3}}{\sbinomq{4}{3}}$,
$X_{1,k}=0$, $X_{2,k}=q^{k-2} \frac{q^k-1}{q^2-1}$, $X_{3,k}=q^k (q^k-1)$, and
$X_{4,k}=\frac{(q^{3k}-q^{2k+3}+q^{k+3})(q-1)}{q^{k-3}-1}$. We note that the reminder in the division of the polynomials
in~$X_{4,k}$ is $q^7 - q^6$ and hence $X_{4,k}$ is an integer only for
$k=4$ and all $q$'s. This solution was given in a previous example for $\dS_q(3,4,8;4)$.

\vspace{0.2cm}

\noindent
{\bf The $k$-punctured $q$-Steiner system $\dS_q (2,3,2k+1;k+1)$, $k \equiv 1$ or $3~(\text{mod}~6)$, $k \geq 3$:}

\vspace{0.1cm}

The number of equations in the system is $\sum_{s=0}^2 \sbinomq{k+1}{s}$. The number of variables
is $\sum_{r=0}^3 \sbinomq{k+1}{r}$. We will consider only uniform designs and hence we only have 3 equations
and 4 variables.

The first equation for the $0$-subspace of $\F_q^{k+1}$ is $N_{(0,k+1),(2,2k+1)}= D_{0,0,k+1} \cdot C_{(0,2)(0,3)} \cdot X_{0,k+1}
+ D_{0,1,k+1} \cdot C_{(0,2)(1,3)} \cdot X_{1,k+1}$
which is equal to $\sbinomq{k}{2} =  \sbinomq{3}{2} \cdot X_{0,k+1}+ \sbinomq{k+1}{1} \cdot X_{1,k+1}$. If we set
$X_{0,k+1} = \frac{\sbinomq{k}{2}}{\sbinomq{3}{2}}$, then we have $X_{1,k+1}=0$.

The second equation for 1-subspaces is $N_{(1,k+1),(2,2k+1)}= D_{1,1,k+1} \cdot C_{(1,2)(1,3)} \cdot X_{1,k+1}
+ D_{1,2,k+1} \cdot C_{(1,2)(2,3)} \cdot X_{2,k+1}$.
Since $N_{(1,k+1),(2,2k+1)}=q^{k-1} \sbinomq{k}{1} = q^{k-1} \frac{q^k-1}{q-1}$ and
$D_{1,2,k+1} = \sbinomq{k}{1}= \frac{q^k-1}{q-1}=q^{k-1}+q^{k-2}+\cdots +q+1$,
it follows that
$$
q^{k-1} \sbinomq{k}{1} = q^{k-1} \frac{q^k -1}{q-1} =  (q^2+q) X_{1,k+1}+ (q^{k-1}+q^{k-2}+\cdots +q+1 ) X_{2,k+1} ~.
$$

The third equation for 2-subspaces is
$N_{(2,k+1),(2,2k+1)}= D_{2,2,k+1} \cdot C_{(2,2)(2,3)} \cdot X_{2,k+1} + D_{2,3,k+1} \cdot C_{(2,2)(3,3)} \cdot X_{3,k+1}$.
Since $N_{(2,k+1),(2,2k+1)}=q^{2k}$ and $D_{2,3,k+1} = \sbinomq{k-1}{1}= \frac{q^{k-1}-1}{q-1}=q^{k-2}+q^{k-3}+\cdots +q+1$,
it follows that
$$
q^{2k} =  q^2 X_{2,k+1} + (q^{k-2}+q^{k-3}+\cdots +q+1) X_{3,k+1} ~.
$$

The solution for this set of equations is $X_{0,k+1}= \frac{\sbinomq{k}{2}}{\sbinomq{3}{2}}$,
$X_{1,k+1}=0$, $X_{2,k+1}=q^{k-1}$, and $X_{3,k+1}=q^{k+1} (q-1)$.


\section{A Recursive Construction}
\label{sec:recursion}

In this section we present a recursive construction for a $p$-punctured
$q$-Steiner system $\dS_q (2,3,2k+1;k+1 +\lfloor \frac{k+1}{3} \rfloor )$,
$p=k- \lfloor \frac{k+1}{3} \rfloor$, where
$k \equiv 1$ or $3~(\text{mod}~6)$. The basis for the construction
is the trivial $q$-Steiner system $\dS_q(2,3,3)$.

Let $k \equiv 1$ or $3~(\text{mod}~6)$, which implies that $2k+1 \equiv 3$ or $7~(\text{mod}~12)$,
and assume that there exists a $p$-punctured $q$-Steiner system $\dS_q(2,3,k;\lfloor \frac{k+1}{3} \rfloor)$, $p=k- \lfloor \frac{k+1}{3} \rfloor$.
Let~$\dS$ be a $k$-punctured $q$-Steiner system $\dS_q(2,3,2k+1;k+1)$ presented in Section~\ref{sec:examples}.
For~$\dS$ we have that $X_{0,k+1}= \frac{\sbinomq{k}{2}}{\sbinomq{3}{2}}$,
$X_{1,k+1}=0$, $X_{2,k+1}=q^{k-1}$, and $X_{3,k+1}=q^{k+1} (q-1)$.
In the recursive construction, we will generate a system $\T$, a $p$-punctured
$q$-Steiner system $\dS_q(2,3,2k+1;k+1 + \lfloor \frac{k+1}{3} \rfloor )$, $p=k- \lfloor \frac{k+1}{3} \rfloor$.


Let $r= \lfloor \frac{k+1}{3} \rfloor$ be the number of columns that
should be appended to the subspaces
(of dimension 0, 2, and 3) of $\dS$ to form $\T$. To each one of
the $\sbinomq{k+1}{3}$ distinct $3$-subspaces of~$\dS$ we append the $q^{3r}$ possible combinations of $r$ columns.
Each column has $q^3$ possible combinations by Lemma~\ref{lem:addNone}.
Since $X_{3,k+1}=q^{k+1} (q-1)$, it follows that each such combination
(a $3$-subspace of $\F_q^{k+1+r}$), whose $r$-punctured subspace is also a 3-subspace,
will appear $q^{k+1-3r} (q-1)$ times in $\T$.
To the $\frac{\sbinomq{k}{2}}{\sbinomq{3}{2}}$ $0$-subspaces of $\dS$ we append
the subspaces of a $(k-r)$-punctured $q$-Steiner system $\dS_q(2,3,k;r)$ system which
exists by our assumption. Hence, we have completed
the extension of the 0-subspaces and 3-subspaces of~$\dS$. To complete our construction we have
to extend the 2-subspaces of~$\dS$.

For the extension of the 2-subspaces we need two more concepts, namely spreads and large sets in $\cG_q(k+1,2)$
(known as 1-spreads and 1-parallelisms in PG($k,q$) ~).
A \emph{spread} in $\cG_q(k+1,2)$ is a set of 2-subspaces
whose nonzero elements form a partition of all the elements of $\F_q^{k+1} \setminus \{ 0 \}$, i.e.
each nonzero vector of $\F_q^{k+1}$ appears in exactly one 2-subspace of the spread.
In other words, a spread in $\cG_q(k+1,2)$ is a $q$-Steiner system $\dS_q(1,2,k+1)$.
A \emph{large set} (1-parallelism) of $q$-Steiner systems $\dS_q(1,2,k+1)$ is a partition
of all 2-subspaces of $\cG_q(k+1,2)$ into $q$-Steiner systems $\dS_q(1,2,k+1)$ (spreads).
If $q=2$, then such large sets are known to exist whenever $k+1$ is even~\cite{Bak76}

We continue by considering the case of $q=2$.
Note, that $k+1$ is even and hence there exists a spread in $\cG_2(k+1,2)$.
The size of such spread is $\frac{2^{k+1}-1}{3}$, i.e. it contain
$\frac{2^{k+1}-1}{3}$ subspaces. The total number of
subspaces in $\cG_2 (k+1,2)$ is $\sbinomtwo{k+1}{2} = \frac{(2^{k+1}-1)(2^k-1)}{3}$.
There exists a partition (large set) of these 2-subspaces into disjoint spreads and
hence there are $2^k-1$ disjoint spreads in such a large set. We continue and
arbitrarily partition these $2^k-1$ disjoint spreads into $2^r$ sets of spreads, one set with
$2^{k-r}-1$ spreads and $2^r-1$ sets each one with $2^{k-r}$ spreads.
%Each spread contains each nonzero vector of length $k+1$ exactly once.
To each one of these $2^r-1$ sets we assign arbitrarily a different nonzero row vector
of length $r$, and the all-zero vector of length $r$ is assigned to the set of size $2^{k-r}-1$.

For demonstration of the construction, each 2-subspace of
$\dS$ is represented by
a ${3 \times (k+1)}$ matrix, each 2-subspace of
$\T$ is represented by
a ${3 \times (k+1+r)}$ matrix, and  each 3-subspace of
$\T$ is represented by
a ${7 \times (k+1+r)}$ matrix.

Consider now these two sets of spreads:
\begin{enumerate}
\item For the set which contains $2^{k-r}-1$ spreads, each 2-subspace $X$ from
each spread is contained $2^{k-1}$ times in the
$\dS$. The 2-subspaces
$X$ is extended to several 2-subspaces in $\F_2^{k+1+r}$ as follows.
The first $k+1$ columns which represent these 2-subspaces are equal to the
$3 \times (k+1)$ matrix which represents $X$. In the last $r$ columns
there are 4 possible options in each column and thus $2^{2r}$ distinct combinations
of $r$ columns. Each such combination will appear $2^{k-1-2r}$ times in $\T$.

\item For a set which contains $2^{k-r}$ spreads (there are $2^r-1$ such sets in the
partition), each 2-subspace $X$ from each
spread is contained $2^{k-1}$ times in $\dS$.
There is a nonzero vector $v$ of length $r$ which is assigned to this set.
The 2-subspace $X$ is extended to several 3-subspaces in $\F_2^{k+1+r}$ as follows.
The first three rows in the first $k+1$ columns which represent these subspaces are equal to the
$3 \times (k+1)$ matrix which represents $X$.
The next three rows in these $k+1$ columns are also equal to the
$3 \times (k+1+r)$ matrix which represents $X$. The seventh and the last
row in these $k+1$ columns is a row of \emph{zeroes}.
We turn now to complete the last $r$ columns in the $7 \times (k+1+r)$ matrices
which represents the 3-subspaces extended from $X$. The entries of the last (seventh) row in these columns
are assigned with the values of $v$. The first column in which $v$ has a \emph{one}
has values which corresponds to the unique extension from a 2-subspace to a 3-subspace
as proved in Lemma~\ref{lem:addOne}. Finally, in each other column there are 4 possible distinct
combinations: if the related entry in $v$ is a \emph{zero}, it relates to the extension
from 2-subspace to 2-subspace; and if the related entry in $v$ is a \emph{one}
it relates to the extension from 3-subspace to 3-subspace in which there are
4 combinations, out of the 8 combinations, with a \emph{one} in a given coordinate.
In total there are $2^{2(r-1)}$ distinct combinations for these $r$ columns.
Each such combination will appear $2^{k-1-2(r-1)}$ times in $\T$.
\end{enumerate}

The proof that $\T$ is $p$-punctured
$q$-Steiner system $\dS_q(2,3,2k+1;k+1 + r )$, $p=k-r$,
follows immediately from the described construction.

The generalization for $q>2$ is similar, as explained before the requirement is the existence of large set
of $q$-Steiner system $\dS_q(1,2,k+1)$, where $k \equiv 1$ or $3~(\text{mod}~6)$.
Such a large set is known to exist for $q>2$ only if
$k+1$ is a power of 2~\cite{Beu74}, making the possible generalizations for $q>2$
with limited number of parameters.
The recursive construction, with the basis of $\dS_q(2,3,3)$, leads to the following theorem.

\begin{theorem}
There exists a $p$-punctured
$q$-Steiner system $\dS_q (2,3,2^\ell -1;2^\ell -1 -\lfloor \frac{2^\ell -1}{3} \rfloor )$,
$p=\lfloor \frac{2^\ell -1}{3} \rfloor$, $\ell \geq 3$.
\end{theorem}

For $q=2$ the construction can be applied also by starting with the $q$-Steiner system $\dS_2 (2,3,13)$~\cite{BEOVW}.



\section{Conclusions}
\label{sec:conclude}

We have presented a new framework to examine the existence of $q$-Steiner systems.
Based on this framework we have defined a new set of $q$-designs which are
punctured $q$-Steiner systems. Necessary conditions for the existence of such designs were presented.
Several parameters where these new designs exist, were given. A recursive
construction for one set of parameter for such designs was given. For future research the main problem in this direction
is to find lower bounds on $m$ for any given $(n-m)$-punctured
$q$-Steiner system $\dS_q(t,k,n;m)$.

The new framework was as a basis to find a punctured $q$-Fano
plane (also known as a residual $q$-Fano plane), i.e. a punctured $q$-Steiner system $\dS_q(2,3,7;6)$,
for each prime power $q \geq 2$~\cite{EtHo17}.
The construction is based
on extending the 3-punctured $q$-Steiner system $\dS_q(2,3,7;4)$.
This system is very interesting. It consists of 2-subspaces of $\F_q^6$, which form
a spread. Each 2-subspace of $\F_q^6$ which is not part of the spread is contained in exactly $q^2$
3-subspaces of the system. These new findings give us a renewed hope to construct a $q$-Fano plane
for $q>2$, as the system cannot be extended for $q=2$.

The new framework can be used to prove that in the $q$-Fano plane (if exists) we can force
three 3-subspaces with four columns of zeroes - one in the first four columns, one in the last
four columns, and one in the first two and the last two columns. Such a result as well as other
derived properties are left as an exercise to the interested reader.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}

The author want to thank an anonymous reviewer whose comments taught him where
the earlier version of this paper needs to be amended. His comments have contributed
to the readability of the paper. The author also thanks Professor Alexander Vardy for many
helpful discussions during the last ten years on the problem.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% You do not have to use the same format for your references, but
%    include everything in this file.  Don't use natbib please.
% If you use BibTeX to create a bibliography, copy the .bbl file into here.

\begin{thebibliography}{99}

\bibitem{AAK01}
     {\sc R. Ahlswede, H. K. Aydinian, and L. H. Khachatrian,}
     {\sl On perfect codes and related concepts,}
     {\em Designs, Codes, and Cryptography,} 22 (2001), 221--237.
\bibitem{Bak76}
     {\sc R. D. Baker,}
     {\sl Partitioning the planes AG$_{2m}$(2) into 2-designs},
     {\em Discrete Math.}, 15 (1976), 205--211.
\bibitem{Beu74}
     {\sc A. Beutelspacher,}
     {\sl On parallelisms in finite projective spaces,}
     {\em Geometriae Dedicata,} 3 (1974), 35--40.
\bibitem{BEOVW}
     {\sc M. Braun, T. Etzion, P. R. J. \"Osterg\aa rd, A. Vardy, and A. Wassermann}
     {\sl Existence of $q$-Analogs of Steiner Systems,}
     {\em Forum of Mathematics, Pi}, 4 (2016), 1--14.
\bibitem{BKN15}
     {\sc M. Braun, M. Kiermaier, and A. Naki\'{c}}
     {\sl On the automorphism group of a binary $q$-analog of the Fano plane,}
    {\em European Journal of Combinatorics,} 51 (2016), 443--457.
\bibitem{BSSS}
    {\sc A. E. Brouwer, James B. Shearer, N. J. A. Sloane, and Warren D. Smith,}
    {\sl A new table of constant weight codes,}
    {\em IEEE Trans. on Inform. Theory},  36 (1990), 1334--1380.
\bibitem{Cam74}
    P.\,{\sc Cameron},
    Generalisation of Fisher's inequality to fields with more than one element,
    in T.P.\,{\sc McDonough} and V.C.\,{\sc Mavron}, Eds.,
		\emph{Combinatorics},
    London Math.\ Soc.\ Lecture Note Ser.\ 13
    Cambridge Univ.\ Press, Cambridge,		
    1974, pp.~9--13.
\bibitem{Cam74a}
    {\sc P. Cameron},
    {\sl Locally symmetric designs},
    {\em Geometriae Dedicata,} 3 (1974), 65--76.
\bibitem{Chi87}
    {\sc L. Chihara,}
    {\sl On the zeros of the Askey-Wilson polynomials, with
        applications to coding theory,}
    {\em SIAM J. Math. Anal.,} 18 (1987), 191--207.
\bibitem{CoDi07}
    C. J. Colbourn and J. H. Dinitz,
    {\em Handbook of Combinatorial Designs},
    Boca Raton, Florida: Chapman and Hall/CRC, 2007.
\bibitem{Del73}
    {\sc P. Delsarte},
    {\sl An algebraic approach to the association schemes of coding theory},
    {\em Philips Res. Repts. Suppl.,} 10 (1973), 1--97.
\bibitem{Del76}
    {\sc P. Delsarte},
    {\sl Association schemes and $t$-designs in regular semilattices},
    {\em Journal of Combinatorial Theory, Series A,} 20 (1976), 230--243.
\bibitem{Etz96}
    {\sc T. Etzion,}
    {\sl On the nonexistence of perfect codes in the Johnson
     scheme,}
    {\em SIAM Journal on Discrete Mathematics,} 9 (1996), 201--209.
\bibitem{Etz13}
     {\sc T. Etzion,}
     {\sl Problems on q-analogs in coding theory,}
     {\em arxiv.org/abs/1305.6126, May 2013}.
\bibitem{Etz14}
    {\sc T. Etzion,}
    {\sl Covering of subspaces by subspaces,}
    {\em Designs, Codes, and Cryptography,} 72 (2014), 405--421.
\bibitem{EtHo17}
     {\sc T. Etzion and N. Hooker,}
     {\sl Residual $q$-Fano plane and related structures,}
     {\em Electronic Journal of Combinatorics, to appear}.
\bibitem{EtSc04}
    {\sc T. Etzion and M. Schwartz,}
    {\sl Perfect constant-weight codes,}
    {\em IEEE Transactions on Information Theory,} IT-50 (2004), 2156--2165.
\bibitem{EtSi09}
    {\sc T. Etzion and N. Silberstein,}
    {\sl Error-correcting codes in projective space via rank-metric codes and Ferrers
         diagrams,}
    {\em IEEE Trans.\ Inform. Theory}, 55 (2009), 2909--2919.
\bibitem{EtSi13}
    {\sc T. Etzion and N. Silberstein,}
    {\sl Codes and designs related to lifted MRD codes,}
    {\em IEEE Trans.\ Inform. Theory}, 59 (2013), 1004--1017.
\bibitem{EtVa11}
    {\sc T. Etzion and A. Vardy,}
    {\sl Error-correcting codes in projective spaces,}
    {\em IEEE Trans.\ Inform. Theory}, 57 (2011), 1165--1173.
\bibitem{EtVa11a}
     {\sc T. Etzion and A. Vardy,}
     {\sl On $q$-analogs for Steiner systems and covering designs,}
     {\em Advances in Mathematics of Communications}, 5 (2011), 161--176.
\bibitem{GKLO16}
     {\sc S. Glock, D. K\"{u}hn, A.Lo, and D. Osthus,}
     {\sl The existence of designs via iterative absorption,}
     {\em arxiv.org/abs/1611.06827}, November 2016.
%\bibitem{HeSi16}
%     {\sc O. Heden and P. A. Sissokho,}
%     {\sl On the existence of a (2,3)-spread in $V(7,2)$,}
%     {\em Ars Combinatoria}, 124 (2016), 161--164.
\bibitem{Kee14}
     {\sc P. Keevash,}
     {\sl The existence of designs,}
     {\em arxiv.org/abs/1401.3665, January 2014}.
\bibitem{KiLa15}
     {\sc M. Kiermaier and R. Laue,}
     {\sl Derived and residual subspace designs,}
     {\em Advances in Mathematics of Communications}, 9 (2015), 105--115.
\bibitem{KiPa15}
     {\sc M. Kiermaier and M. O. Pav\v{c}evi\'{c},}
     {\sl Imntersection numbers for subspace designs,}
     {\em Journal of Combinatorial Designs}, 23 (2015), 463--480.
\bibitem{KoKs08}
    {\sc R. Koetter and F. R. Kschischang,}
    {\sl Coding for errors and erasures in random network coding,}
    {\em IEEE Trans. on Inform. Theory},  54 (2008), 3579--3591.
\bibitem{MaZh95}
    {\sc W. J. Martin and X. J. Zhu,}
    {\sl Anticodes for the Grassmann and bilinear forms graphs,}
    {\em Designs, Codes, and Cryptography,} 6 (1995), 73--79.
\bibitem{McSl77}
     {\sc F. J. MacWilliams and N. J. A. Sloane,}
     {\em The Theory of Error-Correcting Codes},
     {\sl Amsterdam: North-Holland, 1977}.
\bibitem{Met99}
    {\sc K. Metsch},
	{\sl Bose-Burton type theorems for finite projective, affine and polar spaces,}
		in J.D.\,{\sc Lamb} and D.A.\,{\sc Preece}, Eds.,
    {\em Surveys in Combinatorics, 1999},
                London Math.\ Soc.\ Lecture Note Ser.\ 267,
		Cambridge Univ.\ Press, Cambridge, pp.~137--166, 1999.
\bibitem{ScEt}
    {\sc M. Schwartz and T. Etzion,}
    {\sl Codes and anticodes in the Grassman graph,}
    {\em Journal Combinatorial Theory, Series A,} 97 (2002), 27--42.
\bibitem{Suz90}
    {\sc H. Suzuki,}
    {\sl On the inequalities of $t$-designs over a finite field,}
    {\em European Journal of Combinatorics,} 11 (2014), 601--607.
\bibitem{Tho96}
    {\sc S. Thomas,}
    {\sl Designs and partial geometries over finite fields,}
    {\em Geometriae Dedicata,} 63 (1996), 247--253.
\bibitem{vLWi92}
    {\sc J. H. van Lint and R. M. Wilson,}
    {\em A course in Combinatorics},
    Cambridge University Press, 1992.

\end{thebibliography}

\end{document} 