text:
\begin{document}

\title[An Assmus-Mattson Theorem for Rank Metric Codes]{An Assmus-Mattson Theorem for Rank Metric Codes}
\author[Eimear Byrne]{Eimear Byrne}
\address{School of Mathematics and Statistics, University College Dublin, Belfield, Ireland}
\curraddr{}
\email{ebyrne@ucd.ie}
\thanks{}

\author[Alberto Ravagnani]{Alberto Ravagnani$^*$}
\address{School of Mathematics and Statistics, University College Dublin, Belfield, Ireland}
\curraddr{}
\email{alberto.ravagnani@ucd.ie}
\thanks{$^*$The author was partially supported by the Swiss National Science Foundation through grant n. P2NEP2\_168527 and by the the Marie Curie Research Grants
	Scheme, grant n. 740880.}

\subjclass[2010]{ 11T71, 05B05, 05E20}

\keywords{subspace design, design over $\GFq$, rank metric code, Assmus-Mattson Theorem, weight distribution, MacWilliams identities.}

\maketitle

\thispagestyle{empty}

\begin{abstract}
A $t$-$(n,d,\lambda)$ design over $\GFq$, or a subspace design,
	is a collection of $d$-dimensional subspaces of $\GFq^n$, called {\em blocks}, with the property that every
	$t$-dimensional subspace of $\GFq^n$ is contained in the same number $\lambda$ of blocks.
	A collection of matrices in $\GFq^{n \times m}$ is said to hold a $t$-design over $\GFq$ if the set of column spaces
	 of its elements forms the blocks of a subspace design.
	 We use notions of puncturing and shortening of rank metric codes and the rank-metric MacWilliams identities to establish conditions under which the words of a given rank in a linear rank metric code hold a $t$-design over $\GFq$.
     We show that for $\fqm$-linear vector rank metric codes, the property of a code being MRD is equivalent to its minimal weight codewords holding trivial subspace designs and show that this characterization does not hold for $\GFq$-linear matrix MRD code that are not linear over $\fqm$.
\end{abstract}

\section*{Introduction}\label{sec:intro}

The celebrated Assmus-Mattson Theorem \cite{AM} is among the best-known results in the theory of codes and designs. It has led to several constructions of $t$-designs \cite{AM,assmuskey,cameronvanlint,hupless,macws} and has been the subject of a number of generalizations \cite{bachoc,calddelsloane,del,moralestanaka,shinkumahelleseth}.

The theorem specifies criteria under which the blocks of a combinatorial design are {\em held} by the words of a fixed weight in a linear code. It shows, in particular, that if the dual of a code has few non-zero weights in an interval, then the supports of codewords of fixed Hamming weight close enough to the minimum distance of the code form the blocks of a design.

The notion of a $t$-design over $\GFq$ (or a subspace design) has appeared in the literature since the 1970s \cite{cambcc}, and various constructions of such objects were given in the past \cite{Itoh,thomas,suzuki92}.
A $t$-$(n,d,\lambda)$ design over $\GFq$ is a collection of $d$-dimensional subspaces of $\GFq^n$, called {\em blocks}, with the property that every $t$-dimensional subspace of $\GFq^n$ is contained in the same number $\lambda$ of blocks.
There was a resurgence of interest in such designs during the last decade, due in part to the fact that some subspace designs are optimal as constant weight subspace codes. Subspace codes have been shown to have applications to error correction in network coding \cite{kk}.
It was shown in \cite{flv} that non-trivial subspace designs exist over any finite field and for every value of $t$, as long as the parameters $n,d,\lambda$ are sufficiently large.
There are now several papers showing the existence of such objects for various parameter sets, most of which rely on assumptions of their automorphism groups \cite{braun05,braunetz,bkkljcta,braunkierwass,braunkierwass2}.

In this paper we give conditions under which a linear rank metric code yields a $t$-design over $\GFq$.
Explicitly, we show that if $\mC$ and its dual $\mC^*$ are $w$ and $w^*$-{\em invariant}, respectively, and $\mC^*$ has at most $d-t$ non-zero weights in $\{1,...,n-t\}$, then the codewords of $\mC$ and $\mC^*$ of ranks $w$ and $w^*$, respectively, hold $t$-designs over $\F_q$. This result offers a new approach to the difficult problem of constructing new subspace designs and a motivation to study new classes of rank metric codes.
We also consider existence problems applying recent results on the covering radius and the external distance of codes. These arguments apply to both the rank and the Hamming metric.

In Section 2 we give preliminary results on rank metric codes and on subspace designs. In Section 3 we present our main result, the rank-metric analogue of the Assmus-Mattson Theorem.
In Section 4 we restrict to the class of $\fqm$-$[n,k,d]$ linear codes, which are always $d$-invariant. We show that the {\em maximum rank distance} (MRD) codes, those with parameters $\fqm$-$[n,k,n-k+1]$, are characterized as precisely the codes whose minimal weight codewords hold {\em trivial} $t$-designs. We show, furthermore, that the codes that are linear only over $\fq$ do not satisfy this property. In Section 5 we discuss asymptotic existence of codes satisfying the hypothesis of the Assmus-Mattson Theorem, for both the Hamming and the rank metric.

\section{Preliminaries}

\subsection{Matrix Rank Metric Codes}

We outline some preliminary results on rank metric codes. Throughout the paper, $q$ denotes a fixed prime power and $m,n$ are integers with
$m,n \ge 2$. We let $\F_q$ be the finite field with $q$ elements.

Given a pair of nonnegative integers $N$ and $M$, the $q$-\textbf{binomial} or \textbf{Gaussian coefficient} counts the number of $M$-dimensional subspaces of an $N$-dimensional subspace over $\fq$ and is given by:
$$\qbin{N}{M}{q}:=\prod_{i=0}^{M-1}\frac{q^N-q^i}{q^M-q^i}.$$

For a subspace $U$ of $\fq^n$ we define $U^\perp:=\{ v \in \fq^n : u \cdot v = 0\}$ to be the orthogonal space of $U$ with respect to the standard
inner product $u\cdot v =\sum_{i=1}^{n} u_i v_i$.

\begin{definition}
	The \textbf{rank distance} between a pair of matrices $X,Y \in \F_{q}^{n\times m}$ is defined to be the rank of their difference:
	$$d_{\rk}(X,Y):=\rk(X-Y).$$
\end{definition}

\begin{definition}
	A (linear) \textbf{matrix code} $\mC$ is an $\fq$-subspace of $\F_q^{n \times m}$.

	The \textbf{minimum distance} of $\mC$ is $$d_\rk(\mC):= \min\{d_{rk}(X,Y) : X,Y \in \mC, \ X \neq Y\} =
	\min\{\rk(X) : X \in \mC, \ X \neq 0\}.$$
	We say that $\mC$ is an $\fq$-$[n \times m,k,d]$ code if it has $\fq$-dimension $k$ and minimum rank distance $d$.
	The code $\mC^*$ denotes the \textbf{dual code} of $\mC$ with respect to the bilinear form on $\mat$ defined by
	$(X,Y) \mapsto  \langle X,Y \rangle := \Tr(XY^\top)$,
	that is,
	$$ \mC^*:= \{ Y \in \fq^{n \times m}: \Tr(XY^\top)=0  \mbox{ for all }  X \in \mC\}.$$
\end{definition}

\begin{definition}
	Let $\mC$ be an $\fq$-$[n \times m, k,d]$ matrix code.
	We define
	$$W_i(\mC):=|\{X \in \mC : \rk(X)=i \}|,$$ which is the number of codewords of $\mC$ of rank $i$.
	The
	(\textbf{rank}) \textbf{weight distribution} of $\mC$ is the sequence $(W_i(\mC):  i \in \N)$. We say that an integer $i$ is a \textbf{non-zero weight} of $\mC$ if $W_i(\mC) \neq 0$.
\end{definition}

The weight distributions of a linear matrix code and its dual are related by the rank metric MacWilliams identities \cite{del}. We will use the following formulation from~\cite[Theorem 31]{alb1}.

\begin{theorem}\label{th:macwids}
	Let $\mC$ be an $\fq$-$[n \times m,k,d]$ matrix code. Then for each $\ell \in \{0,...,n\}$ we have:
	\begin{eqnarray}\label{eq:macw}
	\sum_{i=0}^{n-\ell} W_{i}(\mC^*)\qbin{n-i}{\ell}{q} & = & q^{m(n-\ell)k}
	\sum_{i=0}^{\ell} W_{i}(\mC)\qbin{n-i}{\ell-i}{q}.
	\end{eqnarray}
\end{theorem}

The left-hand side of (\ref{eq:macw}) corresponds to multiplication of the weight distribution of $\mC$ by the upper triangular $q$-Pascal matrix
$$ M = \left(  \qbin{n-i}{\ell}{q} \right)_{0 \leq i,\ell \leq n}.$$
The $\ell \times \ell$ minors found in the first $\ell$ rows of $M$ can be expressed as
\begin{eqnarray}\label{eq:minors}
\det \left(  \qbin{r_i}{j-1}{q} \right)_{1 \leq i,j \leq \ell} = q^{\binom{\ell}{2}} \prod_{1\leq i < j \leq \ell} \frac{q^{r_j}-q^{r_i}}{q^j -q^i},
\end{eqnarray}
for some $r_1,...,r_\ell \in \{1,...,n\}$, (see, for example, \cite{dodgy}).

Clearly the determinant shown above is non-zero if the $r_j$ are all distinct and in particular if $r_j=n-i_j$, for distinct $i_1,...,i_\ell$. We will use this to establish invariance of the weight distribution of certain puncturings of a code whose dual code has few non-zero weights.

In the construction of a design over $\F_{q}$ from a set or space of matrices, we will identify the {\em blocks} of the design with the column spaces of the matrices.
This is the matrix analogue of the notion of the support of a vector.

Given a matrix $X$ over $\fq$, we write $\sigma(X)$ to denote its column space, which we call the \textbf{support} of $X$.
In fact this concept can be viewed in the more general lattice-theoretic setting of additive codes in groups \cite{alblatt}.

\begin{definition}
	Let $\mC$ be an $\fq$-$[n \times m, k,d]$ code.

	Let $U$ be a subspace of $\fq^n$.
	We define
	\begin{equation*}
	\mC(U):= \{ X \in \mC : {\rm \sigma}(X) \le U \} \qquad \text{ and } \qquad \mC_=(U):= \{ X \in \mC : {\rm \sigma}(X) = U \}.
	\end{equation*}
	Note that $\mC(U)$ is the subcode of $\mC$ consisting of all codewords of $\mC$ whose supports are contained in $U$.
	The set $\mC_=(U)$ comprises those codewords with support equal to $U$.
\end{definition}

\begin{definition}
	Let $\mC$ be an $\fq$-$[n \times m, k,d]$ code.
	Let $U$ be a $u$-dimensional subspace of $\fq^n$.
	We say that $U$ is a \textbf{$u$-support} of $\mC$ if $\mC_=(U) \neq \emptyset$.
\end{definition}

\begin{definition}
	Let $\mC$ be an $\fq$-$[n \times m, k,d]$ code, let $A \in \GL_n(\fq)$ and let $S \subset [n]$.
	For each matrix $X \in \fq^{n\times m}$, we denote by $X_S$ the $|S| \times m$ matrix obtained from $X$ by deleting each $i$th row of $X$ for $i \notin S$.
	That is, $X_S$ is the projection of $X$ onto the rows indexed by $S$.
	We define the projection map
	$$\pi_s: \fq^{n\times m} \to \fq^{(n-s) \times m}, \qquad X \mapsto X_{\{s+1,...,n\}}.$$
	We define $A \mC:=\{A X : X \in \mC \}$.
	Let $1 \leq s \leq n$.
	The \textbf{punctured code} of $\mC$ with respect to $A$ and $s$ is
	$$\Pi(\mC,A,s):=\left\{ \pi_s(AX) = (AX)_{\{s+1,...,n\}} \ : \ X \in \mC \right\}.$$
	We define the \textbf{shortened code} of $\mC$ with respect to $A$ and $s$ by
	$$\Sigma(\mC,A,s):=\left\{ \pi_s(AX) \ : \ X \in \mC, \  (AX)_{\{1,...,s\}}=0 \right\}.$$
\end{definition}
In the case that $A$ is the identity matrix, the corresponding punctured code is found simply by deleting the first $s$ rows and the shortened code is found by selecting the codewords whose first $s$ rows are all-zero and then deleting these rows from each selected codeword.
We have the following duality result \cite{byrneravagnani}.
\begin{lemma} \label{lem:duality}
	Let $\mC$ be an $\fq$-$[n \times m, k,d]$ code and let $A \in \GL_n(\fq)$. Let $1 \leq s \leq n$ be an integer.
	Then
	\begin{equation*}
	\Pi(\mC,A,s)^* = \Sigma(\mC^*,(A^\top)^{-1},s).
	\end{equation*}
	In particular, $(A\mC)^*=(A^\top)^{-1} \mC^*$ for any $A\in \GL_n(\fq)$.
\end{lemma}

We will apply Lemma \ref{lem:duality} a number of times throughout the paper.

\subsection{Designs over $\F_q$}

We briefly recall the definition of $q$-design and the known constructions. In this paper, we only treat simple $q$-designs.

\begin{definition}
	Let $n\geq r \geq t$ be positive integers and let
	$\mD$ be a collection of $r$-dimensional subspaces of $\fq^n$. We say that $\mD$ forms (the \textbf{blocks} of) a \textbf{$t$-design} over $\fq$ if every $t$-dimensional subspace of $\fq^n$ is contained in the same number $\lambda$ of elements of $\mD$. In this case we say that $\mD$ is a $t$-$(n,r,\lambda)$ design over $\fq$.
\end{definition}

Designs over $\fq$ are also known as {\em subspace designs} and as \textit{designs over finite fields}. A $t$-$(n,r,1)$ subspace design is called a $q$-Steiner system.
The interested reader is referred to the survey \cite{braunkierwass} and the references therein for an outline of the state of the art on designs over finite fields.

We have the following notion of a \textbf{dual subspace design} \cite{KP,suzuki}.

\begin{lemma}\label{lem:dualdesign}
	Let $n,r,t,\lambda$ be positive integers and let $\mD$ be a $t$-$(n,r,\lambda)$ design over $\fq$. Define
	$\mD^\perp:=\{ U^\perp : U \in \mD \}$. Then
	$\mD^\perp$ is a $$t- \left(n,n-r,\lambda\qbin{n-t}{r}{q}\qbin{n-t}{r-t}{q}^{-1} \right)$$ design over $\fq$.
\end{lemma}

The {\em intersection numbers} associated with a subspace design were given in \cite{suzuki}. These fundamental design invariants often play an important role in establishing the non-existence of a design for a given set of parameters.

\begin{lemma}
	Let $n,r,t,\lambda$ be positive integers and let $\mD$ be a $t$-$(n,r,\lambda)$ design over $\fq$.
	Let $I,J$ be $i,j$ dimensional subspaces of $\fq^n$ satisfying $i+j \leq t$ and $I \cap J = \{0\}$.
	Then the number
	$$\lambda_{i,j}:=|\{ U \in \mD : I \subseteq U, \ J \cap U = \{0\} \}| $$
	depends only on $i$ and $j$, and is given by the formula
	$$ \lambda_{i,j} = q^{j(r-i)}\lambda \qbin{n-i-j}{r-i}{q}\qbin{n-t}{r-t}{q}^{-1} .$$
\end{lemma}

We list in Table \ref{taa} the known algebraic constructions of infinite families of
{$t$-$(n,r,\lambda)$} subspace designs that do not rely on the existence of other subspace designs.
This list is still rather short, although many specific numerical parameter sets are known to be realizable \cite{bkkljcta,braunkierwass,braunkierwass2}.
In most cases a computer search is combined with an assumed automorphism group, often in fact the normalizer of a Singer cycle group. One of the first such examples is the construction of a $3$-$(8,4,11)$ design over $\F_2$; see~\cite{braun05}.

The only known parameters of a $q$-Steiner system with $t \ge 2$ are given by
$2$-$(13,3,1)$ over $\F_2$. Subspace designs for these parameters were found by an application of the Kramer-Mesner method and required significant computation \cite{braunetz}. The existence of the $q$-Fano plane, namely a $2$-$(7,3,1)$ design over $\fq$ is still an open problem.

\medskip

{\small

	\begin{table}[h]
		\centering

		\begin{tabular}{|l|l|l|l|}
			\hline
			$t$-$(n,r,\lambda)$  & $\fq$ & Constraints & Refs               \\
			\hline \hline
			$2$-$(n,3,7)$ & $\F_2$ & $(n,6)=1, \ n \ge 7$&  \cite{thomas}\\
			\hline
			$2$-$\left(n,3,\qbin{3}{1}{q}\right)$ &$\fq$& $(n,6)=1, \ n \ge 7$ &  \cite{suzuki92}\\

			\hline
			$2$-$\left(n,r, {\displaystyle \frac{1}{2}}\qbin{n-2}{r-2}{q}\right)$ & $\F_3,\F_5$ &
			\begin{tabular}{ll}
				$n \ge 6$,
				$n \equiv 2 \mod 4$,\\
				$3 \le r \le n-3$,
				$r \equiv 3 \mod 4$
			\end{tabular} &  \cite{bkkljcta}\\
			\hline
		\end{tabular}

		\caption{Known primary constructions of infinite families of subspace designs.}
		\label{taa}
	\end{table}
}

Other realizable parameter sets can be obtained on condition of the existence of other subspace designs.
In \cite{Itoh}, Itoh establishes the following construction.
\begin{theorem}
	Let $n \equiv 5 \mod 6(q-1)$. Suppose there exists a
	$$\mbox{2-$\left(n,3, q^3\qbin{n-5}{1}{q}\right)$}$$ design over $\F_q$ that
	that is invariant under the action of a Singer cycle of $\GL(n,q)$. Then for each $r \geq 3$, there exists a
	$$\mbox{$2$-$\left(rn,3,q^3\qbin{n-5}{1}{q}\right)$}$$ design over $\F_q$ that is invariant under the action of $\SL(r,q^n)$.
\end{theorem}

As an example, one of Suzuki's $\mbox{$2$-$\left(n,3,\qbin{3}{1}{q}\right)$}$ designs over $\F_q$ yields a\\ $\mbox{$2$-$\left(n,3,q^3\qbin{n-5}{1}{q}\right)$}$ subspace design, whose $\qbin{n}{3}{q}-\qbin{3}{1}{q}$ blocks form
the complement of the set of blocks of the original design. Moreover, both of these are invariant under the action of a Singer cycle in $\GL(n,q)$.
Hence the infinite family of designs constructed in \cite{suzuki92} yields a new infinite family via Itoh's construction.
Some further infinite families of $2$-$(rn,3,\lambda)$ designs over $\F_q$ have been constructed by Itoh's result, based on sporadic examples of $2$-$(n,3,\lambda)$ Singer cycle invariant subspace designs found by computer search; see \cite[Table 5]{braunkierwass}.

Finally, in \cite{bkkljcta}, the authors show how to construct new {\em large sets} of designs from existing ones. An $LS_q[N](t,r,n)$ large set is a partition of the set of $\qbin{n}{r}{q}$ $r$-dimensional subspaces of $\F_q^n$
into $N$ disjoint $t$-$\left(n,r,\qbin{n-t}{r-t}{q}N^{-1}\right)$ designs. It is known, for example, that $LS_q[N](2,r,n)$ large sets exist for $q=3,5$, $n\geq 6$ such that $n\equiv 2 \mod 4, $ and $3\leq r \leq n-3$ satisfying $r \equiv 3 \mod 4$. In \cite[Table 7]{braunkierwass} the authors list 5 large set parameters that are known to be {\em realizable}, and many more that are {\em admissable} but for which existence is not yet established.
The interested reader is referred to \cite{bkkljcta} for further details.

\section{An Assmus-Mattson Theorem for the Rank Metric}

The main result of this section is Theorem \ref{th:AM}, which gives criteria under which the $w$-supports of an $\fq$-$[n \times m,k,d]$
form a design over $\fq$. This is a rank-metric analogue of the Assmus-Mattson theorem, connecting codes and subspace designs.

Throughout this section, if $\mC$ is an $\fq$-$[n \times m, k,d]$ code and $U \le \F_q^n$ is a subspace, then we let
$$\mC_{\ge}(U,d):= \{X \in \mC : \rk (X) = d, \ \sigma(X) \ge U\} \subseteq \mC.$$
We also define
$$\pi_{t}(\mC)_{\ell}:=\{X \in \pi_t(\mC) \ : \  \rk(X)=\ell\} \qquad \text{and} \qquad \Pi(\mC,A,t)_{\ell} := \pi_t(A\mC)_\ell.$$

We start with a series of preliminary results. In the sequel, we let $e_i$ denote the unit or standard basis vectors.

\begin{lemma} \label{lem:canspaces}
	Let $\mC$ be an $\fq$-$[n \times m, k,d]$ code. Let
	$0 \le t  <d$ be an integer, and let $E:= \langle e_i \ : \  1 \le i \le t \rangle \le \F_q^n$.
	There is a one-to-one correspondence
	between the words of rank $d$ in $\mC$ whose supports contain $E$ and the elements of the punctured code $\pi_t(\mC)$ of rank $d-t$. More precisely, the restriction of $\pi_t$ to
	$\mC_{\ge}(E,d)$ is a bijection:
	$$\pi_t:\mC_{\ge}(E,d) \to \pi_{t}(\mC)_{d-t}.$$
\end{lemma}
\begin{proof}
	First observe that $\pi_t$ is an $\fq$-linear homomorphism of $\mC$ onto $\pi_t(\mC)$ and moreover is an injection, since for any non-zero $X \in \mC$,
	the rank of $\pi_t(X)$ is at least $d-t >0$.
	Let $X \in \mC_{\ge}(E,d)$. Since $E \le \sigma(X)$, there exists an invertible matrix $G \in \GL_m(\F_q)$ such that
	\begin{equation*} \label{dec1}
	X= \begin{pmatrix} I_t & 0 \\ 0 & Z \end{pmatrix}  G,
	\end{equation*}
	for some $(n-t) \times (m-t)$ matrix $Z$ of rank $d-t$. Therefore, $\pi_t(X)= \begin{pmatrix} 0& Z \end{pmatrix} G$
	and $d=\rk(X)=t+\rk(Z)$.
	In particular, $$\rk(\pi_t(X)) =\rk(Z)=d-t.$$
	This shows that $\pi_t$ is a well-defined, injective map from $\mC_{\ge}(E,d)$ to
	$$\pi_{t}(\mC)_{d-t} =\{X \in \pi_t(\mC) \ : \  \rk(X)=d-t\} .$$

	Let $Y \in \pi_t(\mC)$ such that $\rk(Y)=d-t$. By definition, there exists $X \in \mC$ such that $\pi_t(X)=Y$.
	Since $d-t>0$, we have $X \neq 0$. Therefore
	$$d \le \rk(X) \le \rk(\pi_t(X))+t=\rk(Y)+t=(d-t)+t=d.$$
	It follows that $\rk(X)=d$.
	We will show that $E \le \sigma(X)$. Towards a contradiction, suppose that
	$\sigma(X)$ does not contain $E$. Define the $n \times (m+t)$ matrix
	$$\overline{X}:= \begin{pmatrix} X & e_1^\top & \cdots & e_t^\top\end{pmatrix}.$$
	We then have $\rk(\overline{X}) \ge \rk(X)+1$, as the span of
	$e_1^\top,...,e_t^\top$ is not contained in the span of the columns of $X$. Therefore
	\begin{equation*} \label{contr}
	\rk(\pi_t(\overline{X})) \ge \rk(\overline{X})-t \ge \rk(X)+1-t=d+1-t.
	\end{equation*}
	On the other hand, by construction of $\overline{X}$ we have
	$$\rk(\pi_t(\overline{X})) = \rk(\pi_t(X))=\rk(Y)=d-t,$$
	yielding a contradiction. We deduce that $\pi_t$ is a bijection onto $\pi_t(\mC)_{d-t}$.
\end{proof}

\begin{corollary} \label{pr:1}
	Let $\mC$ be an $\fq$-$[n \times m, k,d]$ code. Let
	$0 \le t  <d$ be an integer, and let $T\le \F_q^n$ be a subspace of dimension $t$. There exists
	$A \in \GL_n(\F_q)$ such that the
	words of weight $d$ in $\mC$ whose support contains $T$ are in one-to-one correspondence with the words of weight $d-t$ in $\Pi(\mC,A,t)$.
\end{corollary}

\begin{proof}
	Let $f:\F_q^n \to \F_q^n$ be an $\F_q$-isomorphism with the property that $f(T)=E= \langle e_i \ : \  1 \le i \le t \rangle$. Let $A \in \GL_n(\F_q)$ be a representation of $f$. Define $\overline{\mC}:=A\mC$.
	Multiplication by $A$ from the left gives a bijection from $\mC_{\ge}(T,d)$ onto $\overline{\mC}_{\ge}(E,d)$.

	The result now follows since,
	by Lemma \ref{lem:canspaces}, we have
	$$|\overline{\mC}_{\ge}(E,d)|=| \pi_t(\overline{\mC})_{d-t}|=W_{d-t}(\pi_t(A\mC))=W_{d-t}(\Pi(\mC,A,t)).$$
	We have shown that for an arbitrary $t$-dimensional space $T$, there is a bijection between $\mC_\geq(T,d)$ and $\Pi(\mC,A,t)_{d-t}$, where $A$ is an invertible matrix mapping a basis of~$T$ to $\{e_1,...,e_t\}$.
\end{proof}

\begin{proposition}\label{prop:punwd}
	Let $\mC$ be an $\F_{q}$-$[n\times m,k,d]$. Let $t <d$ and let $W_i(\mC^*)$ be non-zero for at most $d-t$ values of $i$ in $\{1,...,n-t\}$.
	Let $A$ be an invertible matrix in $\fq^{n \times n}$.
	Then the weight distribution of $\Pi(\mC,A,t)$ is determined and is independent of~$A$.
\end{proposition}

\begin{proof}
	Let $\{i_1,...,i_r\}$ be the set of non-zero weights of $\mC^*$  in $\{1,...,n-t\}$, for some $r \leq d-t$.

	Let $E=\langle e_{t+1},...,e_{n} \rangle$.
	The non-zero weights in $\{1,...,n-t\}$ of
	$\mC^*(E) \subseteq \mC^*$
	form a subset of $\{i_1,...,i_r\}$ and since every element of $\mC^*(E)$ has rank at most $n-t=\dim E$, all of the weights of $\mC^*(E)$ lie in $\{i_1,...,i_r\}$.
	Moreover, since the first $t$ rows of each element of $\mC^*(E)$ are all zero, the map
	$$\Phi:\mC^*(E) \longrightarrow \Sigma(\mC^*,I,t) \ : \  X \mapsto \pi_t(X)$$
	is a rank preserving bijection. As a consequence, the
	non-zero weights of the code $\Sigma(\mC^*,I,t) = \Pi(\mC,I,t)^*$ form a subset of $\{i_1,...,i_r\}$. Clearly, the non-zero weights of $\mC^*$ are precisely the non-zero weights of $(A\mC)^*$. Therefore, we may apply the same argument with
	$A\mC$ in the place of $\mC$ to conclude that the non-zero weights of $$\Pi(\mC,A,t)^*=\Sigma(\mC^*,(A^\top)^{-1},t)=\Sigma((A\mC)^*,I,t) $$ form a subset of $\{i_1,...,i_r\}$, the weights of $\mC^*$ in $\{1,...,n-t\}$.

	Now observe that $W_i(\Pi(\mC,A,t))=0$ for $i=1,...,d-t-1$, since the minimum distance of $\Pi(\mC,A,t)$ is at least $d-t$.
	In particular, at least $d-t$ of the values of the weight distribution of $\Pi(\mC,A,t)$ are known.

	The MacWilliams duality theorem for rank metric codes \cite{del,alb1} then yields a system of $d-t$ equations in at most $d-t$ unknowns.
	In fact, using Theorem \ref{th:macwids}, for $\ell = 0,...,d-t-1$ these equations are explicitly given by
	\begin{eqnarray*}
		\sum_{i=0}^{n-\ell} W_{i}(\Pi(\mC,A,t)^*)\qbin{n-i}{\ell}{q} & = & q^{m(n-\ell)-k}
		\sum_{i=0}^{\ell} W_{i}(\Pi(\mC,A,t))\qbin{n-i}{\ell-i}{q},
	\end{eqnarray*}
	which is equivalent to the system,
	\begin{eqnarray*}
		\sum_{j=1}^{r} W_{i_j}(\Pi(\mC,A,t)^*)\qbin{n-i_j}{\ell}{q} & = &
		(q^{m(n-\ell)-k}-1)\qbin{n}{\ell}{q} .
	\end{eqnarray*}
	From (\ref{eq:minors}), this system can be solved
	for unique $W_{i_j}(\Pi(\mC,A,t)^*), 1 \leq j \leq r$. Furthermore, this solution is independent of $A$, so
	the weight enumerator of $\Pi(\mC,A,t)^*$, and hence $\Pi(\mC,A,t)$, is independent of $A$.
\end{proof}

We require one more definition before proving the main result of this section.

\begin{definition} \label{def:u-inv}
	Let $\mC$ be an $\F_{q}$-$[n\times m,k,d]$ code and let $w$ be an integer satisfying $d \leq u \leq n$.
	We say that $\mC$ is \textbf{$u$-invariant} if $|\mC_=(U)|$ depends only on $u$ for each $u$-support $U$.
	If $\mC$ is $u$-invariant we define $\mu(\mC,u):=|\mC_=(U)|$, where $U$ is any $u$-support.
\end{definition}

\begin{lemma}\label{lem:inv}
	Let $\mC$ be an $\F_{q}$-$[n\times m,k,d]$ $w$-invariant code for some $d\le w \le n$. Let
	$A \in \GL_n(\fq)$. Then $A\mC$ is also $w$-invariant and
	$\mu(\mC,w) = \mu(A\mC,w)$.
\end{lemma}

\begin{proof}
	The map $f: \mC \longrightarrow A\mC : X \mapsto AX$ is a rank preserving bijection.
	Let $U \leq \fq^n$ be a $w$-dimensional space and let $X \in \mC$. Then $U = \sigma (X)=\{ Xv^\top:v \in \fq^n\}$
	if and only if $f(U) = \{AXv^\top:v \in \fq^n \} = \sigma(AX)$. The result follows.
\end{proof}

The following is a rank metric analogue of the Assmus-Mattson Theorem \cite[Theorem 4.2]{AM}. As in the classical case, we show that if the dual code of a $w$-invariant
rank metric code has few weights, then the $w$-supports of $\mC$ form the blocks of a subspace design.

\begin{theorem} \label{th:AM}
	Let $\mC$ be an $\fq$-$[n \times m, k,d]$ code. Let $1 \le t<d$ be an integer, and assume that
	$$|\{1 \le i \le n-t \ : \ W_i(\mC^*) \neq 0\}| \le d-t.$$
	Denote by $d^*$ the minimum distance of $\mC^*$, and let $w,w^*$ be integers satisfying $d \leq w \leq n$ and $d^* \leq w^* \leq n$. Suppose that $\mC$ (resp. $\mC^*$) is $u$-invariant for each $u\leq w$ (resp. $u\leq w^*$).
	Then the $u$-supports of $\mC$ (resp. $\mC^*$) form the blocks of a $t$-design over $\fq$ for each $d\leq u \leq w$ (resp. $d^* \leq u \leq \min \{w^*,n-t\}$).

\end{theorem}

\begin{proof}

	Throughout this proof, let $T$ be a fixed $t$-dimensional subspace of $\fq^n$, let $E=\langle e_1,...,e_t \rangle$ and let $A$ be a matrix representation of the $\fq$-isomorphism that maps $T$ to $E$. From Lemma \ref{lem:canspaces} and the proof of
	Corollary \ref{pr:1}, the words of weight $d$ in $\mC$ whose supports contain $T$ are in one-to-one correspondence with the words of weight $d-t$ in the punctured code $\Pi(\mC,A,t)$. That is, there is a bijection from $\mC_\geq(T,d)$ to $\Pi(\mC,A,t)_{d-t}$.

	We will count in two ways the elements of the set:
	$$P=\{(U,X) \ : \  U \le \F_q^n, \ \dim(U)=d, \ T \le  U , \ X \in \mC, \  \sigma(X)=U\}.$$
	On one hand, since $\mC$ is $d$-invariant by hypothesis, we have:
	$$|P|= \sum_{T \leq U, \ \dim U=d } |\mC_=(U)| \ = \  \mu(\mC,d)  |\{U \le \F_q^n \ : \  U \mbox{ is a $d$-support of $\mC$}, T \le  U \}|.$$
	On the other hand, since each $X \in \mC$ has a uniquely determined support $U=\sigma(X)$ we have:
	$$|P|= |\{X \in \mC \ : \  \rk(X)=d, \ T \le \sigma(X) \}| =|\mC_\geq(T,d)|.$$
	By Corollary \ref{pr:1}, there exists $A \in \GL_n(\F_q)$ such that
	$|P| = W_{d-t}(\Pi(\mC,A,t))$. By Proposition \ref{prop:punwd}, the value of $W_{d-t}(\Pi(\mC,A,t))$ only depends on $k$, $d$ and $t$.

	Now,
	$$W_{d-t}(\Pi(\mC,A,t)) = \sum_{\substack{U \ge T \\ \dim U=d}} |\mC_=(U)|  \ = \ \mu(\mC,d)|  \{ U \ : \ T\leq U \text{ is a }d\text{-support of }\mC\}|,$$
	and hence the number of $d$-supports of $\mC$ that contain $T$ is independent of the choice of $T$ of dimension $t$.
	We deduce that the $d$-supports of $\mC$ form the blocks of a $t$-design over $\fq$.

	We now apply an inductive argument to show that the $u$-supports of $\mC$ form the blocks of a $t$-design for each $d\leq u \leq w$. Suppose the result holds
	for $d\leq u<w$.
	Let $\lambda_{k,\ell}(r)$ denote the number of $r$-supports $U$ of $\mC$ satisfying $U \cap L = \{0\}$ and $K \subseteq U$ for a fixed $k$-dimensional space $K$ and an $\ell$-dimensional space $L$. In other words, the $\lambda_{k,\ell}(r)$ are the intersection numbers of the designs held by the words of rank $r$ in $\mC$.
	We will count the number of words of $\Pi(\mC,A,t)$ of weight $w-t$. Let $\lambda_T(w)$ denote the number of $w$-supports of $\mC$ that contain $T$.

	Let $Y \in \Pi(\mC,A,t)$ have rank $w-t$. Since $\pi_t$ is an injection on $\mC$, $Y=\pi_t(AX)$ for a unique matrix $X \in \mC$ of rank at most $w$.
	If $\dim(\sigma(X) \cap T)=t-\ell$, then there exists an invertible matrix $B$ such that
	$$ AXB =  \begin{pmatrix}
	M_1 &| & M_2 \\
	0   &| & M_3
	\end{pmatrix},$$
	for some matrices $M_i$, where $M_1$ is a $t \times t$ matrix of rank $t-\ell$ and $M_3$ is a matrix of rank $w-t$, satisfying
	$$\sigma\left(\left[ \begin{array}{c}
	M_1 \\
	0
	\end{array}\right] \right)=\sigma(AX) \cap E \text{ and } \sigma(M_3)=\sigma(Y),$$ in which case $\rk(X) = w-\ell$.
	Therefore every word of rank $w-t$ in $\Pi(\mC,A,t)$ corresponds to a unique word in $\mC$ of weight $w -\ell$ whose support meets $T$ in a space of dimension $t-\ell$.

	Now let $V$ be a $(t-\ell)$-dimensional subspace of $T$
	and let $L$ be an $\ell$-dimensional subspace of $T$ satisfying $T = V + L$. Clearly, $L \cap \sigma(X)=\{0\}$ for any $X \in \mC$ with
	$\sigma(X) \cap T = V$.

	Then $$|\{ X \in \mC \ : \ \rk(\pi_t(X)) = w-\ell, \ L \cap \sigma(X) =\{0\}, \ V \subset \sigma(X) \}|=\mu(\mC,w-\ell)\lambda_{t-\ell,\ell}(w-\ell).$$
	It follows that
	$$W_{w-t}(\Pi(\mC,A,t))= \lambda_T(w)\mu(\mC,w) + \sum_{\ell=1}^{w-t} \qbin{t}{\ell}{q} \lambda_{t-\ell,\ell}(w-\ell) \mu(\mC,w-\ell).$$
	Then $\lambda_T(w)$ is independent of $T$ and hence the $w$-supports of $\mC$ are the blocks of a $t$-design over $\fq$.

	Now consider the words of weight $d^*$ in $\mC^*$. We claim the $d^*$-supports of $\mC^*$ are the blocks of a $t$-design over $\fq$.
	For each $d^*$-dimensional subspace $U \le \fq^n$ define
	\begin{eqnarray*}
		\mS(\mC^*,U) &:=&
		\{\sigma(X) \ : \  X \in \mC^*(U), \ \rk(X)=d^* \} \\ &=& \{\sigma(X) \ : X \in \mC^*,  \ \sigma(X) \le U, \ \rk(X)=d^*\}.
	\end{eqnarray*}
	Furthermore, define $\mS^\perp(\mC^*,U):=\{ V^\perp  \ : \ V \in \mS(\mC^*,U) \}$.
	Note that $U^\perp$ is contained in every element of $\mS^\perp(\mC^*,U)$ as
	$\sigma(X) \le U$ if and only if $U^\perp \le \sigma(X)^\perp$ for each $X \in \mC^*$.

	Recall $E=\langle e_1,...,e_t \rangle$ and so $E^\perp = \langle e_{t+1},...,e_n \rangle$.
	We now compute $|\mS^\perp(\mC^*,E^\perp)|$, which is equal to $|\mS(\mC^*,E^\perp)|$.

	The map
	$$\Phi : \mC^*(E^\perp) \longrightarrow \Sigma(\mC^*,I,t) \ : \ X \mapsto \pi_t(X),$$
	is a rank preserving bijection, as any $n \times m$ matrix with column space in $E^\perp$ has its first $t$ rows all-zeroes.
	In particular,
	$$W_{d^*}(\mC^*(E^\perp)) = W_{d^*}(\Sigma(\mC^*,I,t))= W_{d^*}(\Pi(\mC,I,t)^*)=W_{d^*}(\pi_t(\mC)^*). $$
	By assumption, $\mC^*$ and hence $\mC^*(E^\perp)$ is $d^*$-invariant, so that
	\begin{equation}\label{eq:supp}
	|\mS(\mC^*,E^\perp)|  \mu(\mC^*,d^*)  =  W_{d^*}(\mC^*(E^\perp)) = W_{d^*}(\Pi(\mC,I,t)^*).
	\end{equation}

	We can now compute $|\mS^\perp(\mC^*,T^\perp)|$. Since $\sigma(X) \leq E^\perp$ if and only if $\sigma(AX) \leq T^\perp$, we have that
	\begin{eqnarray*}
		\mS(\mC^*,E^\perp) & =&
		\{ \sigma(X) \ : \ \sigma(AX) \le T^\perp, \ \rk(X)=d^*, \ X \in \mC^* \}\\
		& = &
		\{ \sigma(A^{-1} X) \ : \ \sigma(X) \le T^\perp, \ \rk(X)=d^* , \ X \in A(\mC^*) \}
	\end{eqnarray*}

	Substituting $A^\top\mC$ for $\mC$ in the above and the fact that
	$(B\mC)^* = (B^\top)^{-1} \mC^*$ for any $B \in$ GL$_n(\fq)$ yields
	$$	    \mS((A^\top\mC)^*,E^\perp)  =
	\{ \sigma(A^{-1}X) \ : \ \sigma(X) \le T^\perp,  \ \rk(X)=d^* , \ X \in A(A^\top\mC)^*=\mC^* \}.
	$$
	It follows that $|\mS((A^\top\mC)^*,E^\perp)| = |\mS(\mC^*,T^\perp)|$.

	Since $\mu(A^\top \mC,d^*)=\mu(\mC,d^*)$ from Lemma \ref{lem:inv}, again substituting $A^\top\mC$ for $\mC$ in~(\ref{eq:supp}), we get that
	$$|\mS^\perp(\mC^*,T^\perp)| = |\mS((A^\top\mC)^*,E^\perp)|= \frac{W_{d^*}(\Pi(\mC^*,A^\top,t))}{\mu(\mC^*,d^*)}. $$
	Since the weight distribution of $\Pi(\mC^*,A^\top,t))$ is independent of $A$, it follows that the number $|\mS^\perp(\mC^*,T^\perp)| $ is independent
	of $T$ of dimension $t$.

	Let $\mB$ be the set of $d^*$-supports of $\mC^*$ and let $\mB^\perp:=\{U^\perp  : U \in \mB\}$.
	The argument just given shows that every $t$-dimensional subspace $T$ is contained in the same number of elements of $\mB^\perp$, which is therefore a $t$-design over $\fq$. Therefore $\mB$ forms the blocks of $t$-design, which is the {\em dual} subspace design (as described in Lemma \ref{lem:dualdesign}) of $\mB^\perp$.

	Using the same inductive argument as before, along with the fact that the weight distribution of $\Pi(\mC,A,t)^*$ is determined, we see that the words of weight $i$ for each $t \le i \leq \min \{n-t,w^*\}$ form the blocks of a $t$-design.
\end{proof}

\section{Vector Rank Metric Codes and $q$-Designs}

Rank metric codes that arise from a vector code $C$ that is linear over an extension field $\F_{q^m}$ are natural candidates as
$u$-invariant codes (see Definition~\ref{def:u-inv}). As the reader will see, such a code $C$ always induces a $d$-invariant matrix rank metric code, where $d$ denotes the minimum distance of $C$.

\begin{definition}
	Let $\Gamma$ be a basis of $\F_{q^m}$ over $\fq$.
	For each $x \in \F_{q^m}^n$, we write $\Gamma(x)$ to denote the $n \times m$ matrix over $\fq$ whose $i$th row is the coordinate vector of
	the $i$th coefficient of $x$ with respect to the basis $\Gamma$. In other words, $\Gamma(x)$ is defined via
	$$x_i=\sum_{j=1}^m \Gamma(x)_{ij} \gamma_j, \qquad 1 \le i \le n.$$
	The \textbf{rank} of $x$ is the rank of the matrix $\Gamma(x)$. Note that the rank of $x$ is well-defined, as it does not depend on the choice of the basis $\Gamma$.
\end{definition}

The spaces $\fq^{n\times m}$ and $\F_{q^m}^n$ are isomorphic as $\fq$-vector spaces with respect to the map $x \mapsto \Gamma(x)$, which, by abuse of notation, we denote by $\Gamma$ as well. The image
of an $\fqm$-linear subspace $C \le \fqmn$ under $\Gamma$ is therefore the matrix code
$\Gamma(C)= \{ \Gamma(x): x \in \mC \}$.
We have $$\dim_{\F_q}(\Gamma(C)) = m  \dim_{\fqm}(C).$$

\begin{definition}
	A (linear rank-metric) \textbf{vector code} $C$ is an $\fqm$-subspace of $\fqmn$ with $C \neq \{0\}$ and $C \neq \fqmn$.
	The \textbf{minimum distance} of $C$ is the minimum distance of $\Gamma(C)$, where $\Gamma$ is any $\F_q$-basis of $\fqm$.
	We say that $C$ is an $\F_{q^m}$-$[n,k,d]$ code if it has $\fqm$-dimension $k$ and $\Gamma(C)$ has minimum rank distance $d$.
	The code $C^\perp$ denotes the \textbf{dual code} of $C$ with respect to the standard inner product of $\fqmn$.
\end{definition}

We have the following duality result (see \cite[Theorem 21]{alb1}).

\begin{lemma}\label{dualalb}
	Let $C \le \fqmn$ be a vector code.
	Let $\Gamma$ be an $\F_q$-basis of $\fqm$, and let $\overline{\Gamma}$ denote the
	trace-dual basis of $\Gamma$. We have $$\Gamma(C)^* = \overline{\Gamma}(C^\perp).$$
\end{lemma}

We also recall the Singleton-type bound for $\F_q$-linear matrix codes \cite{del}.

\begin{proposition}\label{stbound}
	Let $\mC$ be an $\fq$-$[n \times m, k,d]$ matrix code. Then the dimension of $\mC$ is upper bounded as follows:
	$$k \le \max\{n,m\}  (\min\{n,m\}-d+1).$$
\end{proposition}

Codes that meet the bound of Proposition \ref{stbound} are called \textbf{maximum rank distance} (MRD) codes.

\begin{definition}
	An $\F_{q^m}$-$[n,k,d]$ vector code is called \textbf{MRD} if one of the following equivalent properties hold:
	\begin{itemize}
		\item $\Gamma(C)$ is MRD for some $\fq$-basis $\Gamma$ of $\fqm$.
		\item $\Gamma(C)$ is MRD for all $\fq$-basis $\Gamma$ of $\fqm$.
	\end{itemize}
\end{definition}

It is known \cite{del} that $\fqm$-linear vector MRD codes exist for all choices of the admissible parameters. In particular, $\F_q$-linear MRD matrix codes exist for all choices of the admissible parameters.

An $\fq$-$[n \times m, k,d]$ matrix code $\mC \le \mat$ is called \textbf{dually QMRD} if $$d_\rk(\mC)+d_\rk(\mC^\perp)=\min\{m,n\}+1.$$ These codes can be regarded as the best alternative to MRD codes for dimensions that are not a multiple of $\max\{m,n\}$. They share with MRD codes some important rigidity properties. We refer the interested reader to \cite{cruzrav} for further details.
As with MRD codes, an $\F_{q^m}$-$[n,k,d]$ vector code $C$ is dually QMRD if
$\Gamma(C)$ is dually QMRD for some $\fq$-basis $\Gamma$ of $\fqm$.

\begin{lemma} \label{lem:bnd}
	Let $C$ be an $\F_{q^m}$-$[n,k,d]$ code, and let $U \le \F_q^n$ be a subspace of dimension $u \ge d+1$. For all $\F_q$-bases $\Gamma$
	of $\fqm$ we have
	$$\dim_{\F_q} (\Gamma(C)(U)) \leq m(u - d +1).$$
\end{lemma}
\begin{proof}
	Let $\mC:=\Gamma(C)$, let $E= \langle e_1,...,e_u \rangle$ and let $f:\F_q^n \to \F_q^n$ be an $\F_q$-isomorphism such that $f(U) =E$.
	Then $\mC(U) = (A\mC)(E)$.
	Clearly, $\mC$ and $A\mC$ have the same minimum distance. Therefore we can view $(A\mC)(E)$ as a code in $\F_q^{u \times m}$ of minimum distance at least $d$. By the Singleton bound for the rank metric we deduce that
	$\dim_{\F_q}((A\mC)(E)) \le m(u-d+1)$.
\end{proof}

Lemma \ref{lem:bnd} implies the $d$-invariance of codes arising from vector rank metric codes. In the proof of the following proposition, we will need the following observation.

\begin{remark} \label{remreader}
	Let $\Gamma$ be a $\F_q$-basis of $\F_{q^m}$. Then for $x \in \F_{q^m}^n$ and all $\alpha \in \F_{q^m}$ with $\alpha \neq 0$ we have
	$\sigma(\Gamma(x))=\sigma(\Gamma(\alpha x))$.
\end{remark}

\begin{proposition}\label{cor:dsupps}
	Let $C$ be an $\F_{q^m}$-$[n,k,d]$ code. Then for all
	$\F_q$-bases $\Gamma$
	of $\fqm$ the code $\Gamma(C)$ is $d$-invariant with
	$$\mu(\Gamma(C),d)=q^m-1.$$
\end{proposition}
\begin{proof}
	Let $\mC:=\Gamma(C)$, and let $U$ be an $d$-support of $\mC$. Then by Lemma \ref{lem:bnd} we have
	$|\mC_=(U)| \le q^{m}-1$. Let $x \in C$ be a codeword such that $\sigma(\Gamma(x)) =U$. By Remark~\ref{remreader}, the set
	$$\{\Gamma(\alpha x) \ : \ \alpha \in \fqm \setminus \{0\}\} \subseteq \mC$$
	is made of matrices whose support is $U$. Moreover, it has cardinality $q^m-1$.
	Therefore we have $|\mC_=(U)| \ge q^{m}-1$, concluding the proof.
\end{proof}

We can now combine the results obtained so far as follows.

\begin{corollary}\label{th:fqmam}
	Let $C$ be an $\F_{q^m}$-$[n,k,d]$ code. Let $1 \le t<d$ be an integer, and assume that
	$$|\{1 \le i \le n-t \ : \  W_i(C^\perp) \neq 0\}| \le d-t.$$
	Let $d^\perp$ be the minimum distance of $C^\perp$. Then for every $\F_q$-basis of $\fqm$
	the $d$-supports of $\Gamma(C)$ and the $d^\perp$-supports of $\Gamma(C)^*$ form the blocks of a $t$-design over $\fq$.
\end{corollary}

\begin{proof}
	From Proposition \ref{cor:dsupps}, $\Gamma(C)$ is $d$-invariant. Denote by $\overline{\Gamma}$ the trace-dual of the basis $\Gamma$. Then by Lemma \ref{dualalb} we have $\Gamma(C)^*=\overline{\Gamma}(C^\perp)$. Therefore by Proposition~\ref{cor:dsupps} the code
	$\Gamma(C^\perp)$ is $d^\perp$-invariant as well.
	Again by Lemma \ref{dualalb}, the codes $C^\perp$ and $\Gamma(C)^*$ have the same
	weight distribution.
	The desired result now follows as an immediate consequence of Theorem \ref{th:AM}.
\end{proof}

In \cite[Theorem 5.3]{eejit}, the authors show that a $\fqm$-$[2d,d,d]$ code with no words of weight $d+1$ give rise to a Steiner system from the supports of its
words of weight $d$; that result may also be seen to be a consequence of Corollary \ref{th:fqmam}.

\begin{example}
	Let $s$ be a positive integer and let $m=2s$. Let $\{\alpha_1,...\alpha_m\}$ be a basis of $\fqm$ over $\fq$.
	Let $C$ be the $\fqm$-$[m,m-2,2]$ vector rank metric code with parity check matrix
	$$H = \left[  \begin{array}{llll}
	\alpha_1 & \alpha_2 & \cdots & \alpha_m \\
	\alpha_1^{q^s} & \alpha_2^{q^s} & \cdots & \alpha_m^{q^s}
	\end{array}\right]. $$
	It can be checked that
	$$W_0(C^\perp)=1, \quad W_s(C^\perp) = \frac{(q^{2s}-1)^2}{q^s-1},\quad W_{2s}(C^\perp) = q^{4s}-\frac{(q^{2s}-1)^2}{q^s-1}-1,$$
	and that $W_i(C^\perp)=0$ otherwise.
	In particular, $C^\perp$ has $\fq$-ranks $\{0,s,2s\}$ and so $C$ satisfies the hypothesis of Corollary \ref{th:fqmam} with $t=1$.
	That is, $C^\perp$ has exactly one weight $s$ in $\{1,...,2s-1\}$.
	The supports of the codewords of $C$ of rank $2$ form a $1$-design over $\fq$ and the words of rank $s$ in $C^\perp$
	form a $1$-$(m,s,1)$ subspace design, which is in fact a spread of $\fq^n$.

\end{example}

In the sequel, we will use the following characterization of
MRD codes.

\begin{proposition} \label{projcriterion}
	Let $\mC$ be an $\fq$-$[n \times m, k,d]$ code, and assume $m \ge n$. The following are equivalent:
	\begin{enumerate}
		\item $\mC$ is MRD, \label{uu}
		\item $d_\rk(\mC)+d_\rk(\mC^*)=n+2$, \label{dd}
		\item the projection on the last $n-d+1$ rows $\mC \to \F_q^{(n-d+1) \times m}$  is surjective.
	\end{enumerate}
\end{proposition}

\begin{proof}
	The projection is injective, as $\mC$ has minimum distance $d$. Therefore it is surjective if and only if
	$\dim(\mC)=m(n-d+1)$, i.e., if and only if $\mC$ is MRD.
	Since a code is MRD if and only if its dual is also MRD \cite{del}, from the MRD Singleton bound it follows that (\ref{uu}) and (\ref{dd}) are equivalent.
\end{proof}

We will use the following result from \cite[Lemma 28]{alb1}, which is actually a special case of \cite[Lemma 48]{alblatt}.
The following rank metric specialization is more convenient for readers unfamiliar with lattices.

\begin{lemma}\label{lem:cu}
	Let $m \geq n$ and let $\mC$ be an $\fq$-$[n \times m, k,d]$ code. Let $U$ be a $u$-dimensional subspace of $\fq^n$. Then
	$$|\mC(U)| = q^{k-m(n-u)}|\mC^\perp(U)|. $$
\end{lemma}

\begin{corollary}\label{cor:mrddsupps}
	Let $\mC$ be an $\fq$-$[n \times m, m(n-d+1),d]$ code and let $U$ be a $d$-dimensional subspace of $\fq^n$. Then
	$|\mC(U)| = q^m$.
\end{corollary}

\begin{proof}
	Since $\mC$ is MRD by hypothesis, so is its dual code $\mC^*$, which has minimum distance $d^*=n-d+2$.
	Therefore, $\mC^*(U^\perp) = \{0\}$, since no non-zero word in $\mC^*$ has column space contained in an $(n-d)$-dimensional subspace
	of $\fq^n$. The result now follows directly from Lemma \ref{lem:cu}.
\end{proof}

The next result shows that if $m \ge n$ the minimum weight codewords of an MRD $\fqmn$-linear code always hold a trivial design, and that these are the only codes with this property.
Note that the trivial design has as blocks the collection of all  $k$-dimensional subspaces of $\F_q^n$ and has parameters $$t\mbox{-}\left(n,k,\qbin{n-t}{k-t}{q}\right)_q.$$

\begin{proposition} \label{prop:MRDtrivial}
	Let $C$ be an $\F_{q^m}$-$[n,k,d]$ code, and let $\Gamma$ be any $\F_q$-basis of $\fqm$. Assume $m \ge n$. Then the following are equivalent.
	\begin{enumerate}
		\item $C$ is MRD, \label{uno}
		\item the words of rank $d$ in $\Gamma(C)$ hold a trivial design over $\fq$. \label{due}
	\end{enumerate}
\end{proposition}

\begin{proof}
	Suppose that $C$ is MRD. Then $\Gamma(C)$ is MRD as well and so by Corollary~\ref{cor:mrddsupps}, for all $U \le \F_q^n$ of dimension $d$ we have
	$|\Gamma(C)(U)|=q^m$.
	Since $C$ and $\Gamma(C)$ have minimum distance $d$, there exists $X \in \Gamma(C)$ such that $\sigma(X)=U$. Since $U$ was arbitrary, the words of rank $d$ in $\Gamma(C)$ hold the trivial design. This shows that (\ref{uno}) implies (\ref{due}).

	Let us show that (\ref{due}) implies (\ref{uno}).
	Suppose that $v \in \fqmn$ is a vector, and that $\Gamma$ and $\Gamma'$ are $\F_q$-bases of $\fqm$. Then it is easy to see that
	$\Gamma'(v)=\Gamma(v)  A$, where $A$ is an invertible matrix. Therefore it suffices to prove that (\ref{due}) implies (\ref{uno}) for a basis $\Gamma$ of our choice.

	We henceforth assume that $\Gamma$ is given by the powers of a primitive element $\alpha$ of $\F_{q^m}$, i.e.,
	$\Gamma=\{1,\alpha,\alpha^2,...,\alpha^{m-1}\}$.

	For every $i \in \{d,...,n\}$ we fix $x_i \in C$ with $\sigma(\Gamma(x_i))=\langle e_1,...,e_{d-1},e_i\rangle$. Then for all $i \in \{d,...,n\}$ the projection
	$\pi_{d-1}(\Gamma(x_i))$ is a matrix having only one non-zero row for all $i$, namely the $(i-d+1)$th row.

	We now fix an arbitrary $i \in \{d,...,n\}$.
	In the sequel, we denote by $M_i$ the $i$th row of a matrix $M$.
	We clearly have
	$$(\Gamma(x_i)M)_i = \Gamma(x_i)_i M$$
	for every matrix $M$.
	Observe that multiplication by $\alpha$ corresponds to multiplication from the right by $M(\alpha)$, the companion matrix of the minimal polynomial of $\alpha$. More precisely, we have
	$\Gamma(\alpha x)=\Gamma(x)M(\alpha)$ for all $x \in \F_{q^m}^n$.

	We will now show that the $m$ vectors
	\begin{equation} \label{list}\Gamma(x_i)_i ,\ \Gamma(x_i)_iM(\alpha),...,\ \Gamma(x_i)_iM(\alpha)^{m-1} \ \in \F_q^m
	\end{equation} are $\F_q$-linearly independent. Towards a contradiction, suppose that there exist elements
	$\lambda_0,...,\lambda_{m-1} \in \F_q$, not all zero, such that
	$$\sum_{j=0}^{m-1} \lambda_j \Gamma(x_i)_i M(\alpha)^{j}=0.$$
	Then we have
	\begin{equation} \label{par}
	\Gamma(x_i)_i \left(\sum_{j=0}^{m-1} \lambda_j M(\alpha)^{j}\right)=0.
	\end{equation}
	The matrix in parentheses in (\ref{par}) is invertible by the properties of the companion matrix $M(\alpha)$. This implies
	$\Gamma(x_i)_i=0$, a contradiction, and therefore the vectors in~(\ref{list}) are linearly independent.

	All of this shows that the projection $$\Gamma(\mC) \to \F_q^{(n-d+1) \times m}$$ on the last $n-d+1$ rows is surjective. Therefore $\Gamma(C)$ is MRD by Proposition \ref{projcriterion}, which in turn implies that
	$C$ is MRD by definition.
\end{proof}

\begin{remark}
	We can also see that \ref{uno}. implies \ref{due}. in Proposition~\ref{prop:MRDtrivial} by the following simple argument. If $C$ is MRD then its weight distribution is determined~\cite{del}, and in particular
	$$W_d(C)=W_d(\Gamma(C))=\qbin{n}{d}{q}(q^m-1).$$
	From Proposition \ref{cor:dsupps}, $\mu(\Gamma(C),d)=q^m-1$, which is the number of words of $C$ that have the same $d$-support. But then the total number of $d$-supports of $C$ is $$\qbin{n}{d}{q}.$$
\end{remark}

\begin{remark}
	It was shown in \cite{AM} that a Hamming metric code is MDS if and only if
	its minimum weight codewords hold a trivial design.
	This can be also seen using an argument very similar to that given in Proposition \ref{prop:MRDtrivial}, as we now show.

	If the codewords of weight $d$ in an $\fq$-$[n,k,d]$ code $C$
	hold a trivial design then,
	in particular, $\{1,2,...,d-1,i\}$ is the support of a word of $C$ for each
	$i \in \{d,...,n\}$.
	If $C'$ is obtained from $C$ by puncturing the first $d-1$ coordinates of $C$ then $C'$ contains all the standard basis vectors of $\fq^{n-d+1}$. Therefore $C'$, and hence $C$, has dimension $n-d+1$.
\end{remark}

As the next result shows, $\fqm$-linearity is crucial in the proof of Proposition \ref{prop:MRDtrivial}. In fact, the same result does not hold in general unless we assume that the code $\Gamma(C)$ arises from an $\fqm$-linear code, even if we consider the larger class of dually quasi-MRD codes.

\begin{proposition}
	Assume $m \ge n+1$, and let $1 \le d \le n-1$ be an integer. There exists a code
	$\mC \le \F_q^{n \times m}$ with the following properties:
	\begin{enumerate} \setlength\itemsep{0em}
		\item $\mC$ is not MRD,
		\item $\mC$ is not dually QMRD,
		\item the minimum weight codewords of $\mC$ hold the trivial $d$-design.
	\end{enumerate}
\end{proposition}
\begin{proof}
	Since $m \ge n+1$, there exists an MRD code $\mD \le \F_q^{n \times (m-1)}$ of minimum distance $d$.  For $M \in \mD$, let $z(M) \in \F_q^{n \times m}$ be the matrix obtained from $M$ by appending a zero column. Define the code
	$\mC:=\{z(M) : M \in \mD\} \le \F_q^{n \times m}$.

	Since $M$ and $z(M)$ have the same support for all $M \in \mD$, the codes $\mD$ and $\mC$ have the same minimum distance. Moreover, the minimum weight codewords of $\mC$
	hold the trivial design. On the other hand, $\mC^*$ has minimum distance 1, and therefore $d_\rk(\mC)+d_\rk(\mC^*)=d+1 \le n-1+1=n$.
	In particular, $\mC$ is neither MRD (by Proposition~\ref{projcriterion}), nor dually QMRD.
\end{proof}

\section{Existence Results}
We now discuss the existence of codes that meet the hypotheses of the Assmus-Mattson Theorem for the rank metric.
We use results on the external distance and the covering radius of a  code to derive necessary conditions for a matrix code $\mC$ to satisfy the hypotheses of Theorem \ref{th:AM}, for $m$ sufficiently large. Using similar arguments, we also obtain results that apply to codes for the Hamming distance.

Recall that the \textbf{external distance} of an $\F_{q}$-$[n\times m,k,d]$ code $\mC$ is defined to be the integer
$$\tau(\mC) := |\{1 \le i \le n  \ : \ W_i(\mC^*) \neq 0 \}|.$$

The {\em external distance bound}~\cite[Theorem 27]{byrneravagnani} for an $\fq$-$[n \times m,k,d]$
code $\mC$ relates the covering radius of $\mC$ to the number of non-zero weights of $\mC^*$.
More precisely, we have:
$$\rho(\mC) \leq \tau(\mC).$$

We also have the following lower bound on the rank-metric covering radius;
see~\cite[Theorem 8.12]{byrravpart} for details.

\begin{theorem}\label{CRmax}
	Let $\mC$ be an $\fq$-$[n \times m,k,d]$ linear code and
	let $1 \leq r\leq d$ be an integer satisfying
	$(r-1)m \ge \log_q(4)+n^2/4$. Then
	$$\rho(\mC) \ge d-r+1.$$
\end{theorem}

The previous theorem implies that if $m \geq \log_q(4)+n^2/4$, then $\rho(\mC) \ge d-1$. Combining this with the external distance bound we obtain that the number of non-zero weights in the dual code $\mC^*$ is at least $d-1$.

Now suppose that $\mC$ is an $\fq$-$[n \times m,k,d]$ linear code satisfying the hypothesis of Theorem~\ref{CRmax}. For each $1\le t \le d-1$ define $X_t:=|\{ 1 \le i \le n-t : W_i(\mC^*) \neq 0\}| $ and
$Y_t:=|\{n-t+1 \le i \le n : W_i(\mC^*) \neq 0 \}|$. Then $X_t+Y_t = \tau(\mC)$ and $Y_t \leq t$.
In order for the hypothesis of Theorem \ref{th:AM} to hold for $\mC$, we require that
$$d-1 - Y_t \le \tau(\mC)-Y_t = X_t \leq d-t.$$
In particular, $Y_t \in \{t,t-1\}$.
If $Y_t = t-1$, then we have $X_t \geq d-t$, and hence $X_t=d-t$ by hypothesis. This forces $\tau(\mC) = d-1$.
If $Y_t = t$, then $X_t \geq d-t-1$, so either $X_t= d-t-1$ and $\tau(\mC)=d-1$, or $X_t=d-t$ and $\tau(\mC)=d$.
Therefore we have shown the following result.

\begin{proposition}
	Suppose that $\mC$ is an $\fq$-$[n \times m,k,d]$ linear code satisfying the hypothesis of Theorem \ref{th:AM}. If
	$m \geq \log_q(4)+n^2/4$, then $\tau(\mC) \in \{d-1,d\}$.
\end{proposition}

In the case that $C$ is an $\fqm$-$[n,k,d]$ linear code, it has been shown in \cite[Proposition 8.4]{byrravpart} that for sufficiently large
$m$ one has $ \rho(C) = n-k$. Therefore
by the {external distance bound} we have:
\begin{equation}\label{eq:tau}
d-1 \le n-k = \rho(C) \le \tau(C) \in \{d-1,d\}.
\end{equation}
Thus
$n-k \in \{d-1,d\}$ if $m \ge n$ is sufficiently large.

We remark that if $\tau(C)=d$, then we must have $n-k=d$. To see this, suppose that $n-k=d-1$. Then $C$ is MRD, so its dual code has $n-k$ weights yielding the contradiction $\tau(C) =n-k<d$.
Therefore, if $m \ge n$ is sufficiently large then from~(\ref{eq:tau}) either
\begin{itemize}
	\item $\tau(C)=d-1=n-k$, in which case $C$ is MRD,
	\item $\tau(C)=\rho(C)=d = n-k$, in which case $C$ is not MRD.
\end{itemize}

The next result follows directly from (\ref{eq:tau}).
\begin{proposition}
	Let $C$ be an $\fqm$-$[n,k,d]$ linear code and let $1\leq t \leq d-1$. If $m \ge n$ is sufficiently large and if $C$ satisfies the hypothesis of Theorem \ref{th:AM}, then $d \in \{n-k,n-k+1\}$. Furthermore, if $d=n-k+1$ then $C$ holds the trivial design.
\end{proposition}

\begin{remark}
	In fact, a similar conclusion can be drawn for Hamming metric codes satisfying the classical Assmus-Mattson Theorem \cite[Theorem 4.2]{AM}. For sufficiently large $q$, the Hamming metric covering radius of an $\fq$-$[n,k,d]$ code is equal to~$n-k$; see~\cite[Theorem 8.3]{byrravpart}. Therefore, from the Hamming metric external distance bound~\cite[Chapter 6]{macws} we have that $n-k = \rho(\mC) \leq \tau(\mC)$. We summarize this as follows.
\end{remark}

\begin{proposition}
	Let $C$ be an $\fq$-$[n,k,d]$ linear code and let $1\leq t \leq d-1$. If $q$ is sufficiently large and if $C$ satisfies the hypothesis of the classical Assmus-Mattson Theorem, then $d \in \{n-k,n-k+1\}$. Furthermore, if $d=n-k+1$ then $C$ holds the trivial design.
\end{proposition}

In the Hamming metric, the canonical example of a code yielding a 2-design (the Fano plane) is the binary Hamming $[7,4,3]$ code. This can be easily seen using the classical Assmus-Mattson Theorem, observing that its dual code, the simplex code, has only one non-zero weight.
In contrast to this, the next result shows that in the rank metric any code whose dual has only one non-zero weight must have minimum distance upper bounded by 2.

\begin{proposition}
	Let $\mC$ be an $\fq$-$[n\times m,k,d]$ matrix code. Suppose that $\mC^*$ has only one non-zero weight. Then
	$d\le 2$.
\end{proposition}

\begin{proof}
	We can assume $m \ge n$ without loss of generality. Since $\mC^*$ has only one non-zero weight, we have
	$\tau(\mC) \le 1$. By the external distance bound \cite[Theorem 27]{byrneravagnani} we then have
	$\rho(\mC) \le 1$. Since $m,n \ge 2$ by assumption, the code $\mC$ cannot be the entire space, and therefore $\rho(\mC)=1$.
	As a consequence, the balls of radius 1 centered at the codewords of $\mC$ cover the entire space. In particular,
	$$|\mC| \cdot b(1) \ge q^{mn},$$
	where
	$b(1):=1+(q^n-1)(q^m-1)/(q-1)$ is the cardinality of a ball of radius 1 in the metric space $(\mat,d_\rk)$.
	By the Singleton bound (Proposition \ref{stbound}) we conclude that
	$$\frac{q^{mn}}{b(1)} \le |\mC| \le q^{m(n-d+1)}.$$
	Therefore
	$$d \le 1+\log_q(b(1))/m <3,$$
	where the latter inequality follows from the fact that $b(1)<q^{2m}$, as the reader can verify using elementary methods from Calculus. This implies $d \le 2$, as desired.
\end{proof}

\bibliographystyle{siamplain}

config: arxiv


TITLE: Extracting function from sensor
QUESTION [0 upvotes]: and sorry if I am on the wrong stackexchange.
I have a problem. I have collected data from a distance sensor and extracted its function with respect to temperature. The data extracted proved that the sensor is completely linear (mx + b).
The problem is that at different distances, the m and b coefficiente of the lines change. Of course b will change, but my problem is with the m coefficient. The slope coefficient changes according to the real distance and as stated above the distance read changes according to temperature in a very linear manner.
How would I go about extracting this behaviour and putting it into a function.
EDIT:
Ok. I was not very clear, so I'll try to add more information.
I noticed that my sensor was behaving very strangely during hot days. This is normal for well ... everything, however this specific distance sensor I'm using is incredibly more sensitive to temperature.
With that problem I tried analyzing my sensor's behaviour over temperature and noticed that the output distance changes with temperature in a line (mx + b). This behaviour repeats itself for several distances. I noticed that m and b coefficients change according to its actual distance (the m coefficient has the Ae^(-Db)+c, where D is the real distance).
So, distance measured changes with temperature, slope (m) coefficient changes with real distance, as well as c.
Since I can't actually know the real distance and my code has to give ma that information, I was trying to regress a function that could give me this information.
However, if I try to regress it according to mx+b, it will work correctly over a small distance range, and I can't use real distance (I think) for the m and c coefficients because I don't know it. How would I go about measuring the distance using only the temperature and given distance by the sensor? Is it possible?
Below it's possible to see what I'm talking about. The x axis is temperature, the y axis is measured distance and the different lines are the lines at 5 different distances (5, 4, 3, 2 and 1 m)

REPLY [2 votes]: PRELIMINARY COMMENT :
The data is not given on the form of numerical table. A "subsitute" of data was made thanks to scanning the graph provided by the OP. This isn't an accurate way. As a consequence the below numerical results are more or less biaised.
ANSWER TO THE QUESTION :
As far as I can understand the question, it seems that it is a simple problem of fitting a function $y(x,D)$ of two variables. $x$ is the variable on the horizontal axis of the graph. $D$ is the so called "Distance". $y$ is the value of the function on the vertical axis.
A very simple function can be :
$$y(x,D)\simeq (a+bD)x+(p+qD)$$
$a,b,p,q$ are the parameters which can be approximately computed thank to a classical linear regression.
The result is (The fitted function is represented by the black lines)  :

Of course a much better fitting can be obtained with more terms in the polynomial function, for example :
$$y(x,D)\simeq (a+bD+cD^2+dD^3)x+(p+qD+rD^2+sD^3)$$
$a,b,c,d,p,q,r,s$ are the parameters which can be approximately computed thank to a classical linear regression.
The result is (The fitted function is represented by the black lines)  :

Instead of polynomial function one could use other kind of functions $f(D)$ and $g(D)$ :
$$y(x,D)=f(D)x+g(D)$$
For example those functions might include exponentials. But the regression would be non-linear which requires more complicated and difficult methods generally iterative.


TITLE: How to evaluate derivative in the form of $\log^n_nx$
QUESTION [0 upvotes]: How does one evaluate this derivative?
$$\frac d{dx}\left[\sum^N_{n=2}\log^n_nx\right]$$

Work so far:
The differentiation operator and the sigma can be easily swapped but it's more of a question about a general derivative for $$\frac d{dx}\log^n_nx, \qquad\forall n\ge2.$$

REPLY [1 votes]: $$\log_n^n{x} = \left ( \frac{\log{x}}{\log{n}}\right)^n$$
$$\frac{d}{dx} \left ( \frac{\log{x}}{\log{n}}\right)^n = \frac{n}{\log^n{n}} \frac{\log^{n-1}{x}}{x}$$
It's basically the chain rule at work.
One way to write the derivative of the above sum is
$$\frac d{dx}\left[\sum^N_{n=2}\log^n_nx\right] = \frac{1}{x \log{x}} \sum^N_{n=2} n\log^n_nx$$


TITLE: Is the structure $(\mathbb{R}, *)$ "weakly minimal" in this precise sense?
QUESTION [1 upvotes]: This is a follow-up to my previous question about definability in the structure $(\mathbb{R}. *)$ The definition of a minimal structure is that every parameter-definable subset of that structure is finite or cofinite. Now, certainly the structure $(\mathbb{R}, *)$ is not minimal. However, I conjecture that it does have the following weaker property: that every parameter-definable set is either finite, cofinite, the positive reals modulo a finite set, or the negative reals modulo a finite set. By modulo a finite set, I mean the set with some finite number of elements added and/or removed. Is this conjecture true? I would be very surprised if it was false.

REPLY [4 votes]: $\mathcal{R}=(\mathbb{R};*)$, while not itself minimal, has a strongly minimal subset which really captures the whole: namely, $\mathcal{R}^+=(\mathbb{R}_{>0},*)$. $\mathcal{R}$ is basically two copies of $\mathcal{R}^+$, plus a definable singleton, glued together in a definable way, so we can often derive results about $\mathcal{R}$ from results about $\mathcal{R}^+$.
In particular, we have via an appropriate interpretation of $\mathcal{R}$ in $\mathcal{R}^+$:

If $X$ is a definable-with-parameters subset of $\mathcal{R}$, then $\{\vert c\vert: c\in X\}$ is a definable-with-parameters subset of $\mathcal{R}^+$.

Now unlike $\mathcal{R}$, the substructure $\mathcal{R}^+$ actually is minimal: it's just a $\mathbb{Q}$-vector space (think about the map $x\mapsto e^x$). This lets us rule out counterexamples to the conjecture in the OP as follows. Given a definable-with-parameters $X$ in $\mathcal{R}$, let $X_+=X\cap\mathbb{R}_{>0}$ and $X_-=X\cap\mathbb{R}_{<0}$. By the facts above, both $X_-$ and $X_+$ must be either finite or cofinite, so we're done.
More snappily, this is a general feature of any "finite cover" of a minimal structure in the appropriate sense.


TITLE: Find the integral $\int f(x)f'''(x) dx$.
QUESTION [0 upvotes]: I stuck to find the integral $\int f(x)f'''(x)\ dx$.
I found the rule $\int f(x)f'(x)\ dx=\frac{1}{2}f^2(x)+c$. How can I proceed?

REPLY [2 votes]: $$\int f(x)f'''(x)dx=f(x)f''(x)-\int f'(x)f''(x)dx$$
Now:
$$\int f'(x)f''(x)dx=f'(x)^2-\int f''(x)f'(x)dx$$
So you can show:
$$\int f'(x)f''(x)dx=\frac12f'(x)^2$$
And so:
$$\int f'(x)f'''(x)=f(x)f''(x)-\frac12f'(x)^2+C$$


TITLE: Assume $(x_n)$ is a sequence converging to $\bar x$ and that $\|x_n\| < \epsilon$ for all $n \in \mathbb N$. Then $\|\bar x\| \le \epsilon$
QUESTION [2 upvotes]: I'm trying to prove this below theorem:

Assume that $(x_n)$ is a sequence converging to $\bar x$ and that $\|x_n\| < \epsilon$ for all $n \in \mathbb N$. Then $\|\bar x\| \le \epsilon$.

Could you please verify whether my attempt is fine or contains mistakes? Thank you so much!

We have $\|\bar x\| = \|(\bar x -x_n) + x_n\| \le \|\bar x - x_n \| + \|x_n\|$. Taking the limit $n \to \infty$, we have $$\|\bar x\| \le \lim_{n \to \infty}\|\bar x - x_n \| +  \lim_{n \to \infty} \|x_n\| = \lim_{n \to \infty} \|x_n\| \le \epsilon$$
Hence $\|\bar x\| \le \epsilon$.

REPLY [1 votes]: Your proof is fine. To be pedantically rigorous, it could be written like this: Choose $N_1$ such that $n\geqslant N_1$ implies $\|x_n\|<\frac\varepsilon2$ and $N_2$ such that $n\geqslant N_2$ implies $\|x_n-\bar x\|<\frac\varepsilon2$. Let $N=\max\{N_1,N_2\}$, then for $n\geqslant N$ we have
$$
\|\bar x\| \leqslant \|\bar x-x_n\| + \|x_n\| = \frac\varepsilon2+\frac\varepsilon2=\varepsilon.
$$


TITLE: The Nth number with M prime factors
QUESTION [5 upvotes]: Hi.
Suppose we arrange all natural numbers in a matrix P defined as follows:
P[I][J] = The Jth number with I prime factors. So P looks something like:
1
2 ,    3 ,    5 ,    7 ,   11 ,   13 ,   17 ,   19 ,   23 ,   29 ,   31 ,   37 ,   41 ,   43 ,   47 , ...
4 ,    6 ,    9 ,   10 ,   14 ,   15 ,   21 ,   22 ,   25 ,   26 ,   33 ,   34 ,   35 ,   38 ,   39 , ...
8 ,   12 ,   18 ,   20 ,   27 ,   28 ,   30 ,   42 ,   44 ,   45 ,   50 ,   52 ,   63 ,   66 ,   68 , ...
16 ,   24 ,   36 ,   40 ,   54 ,   56 ,   60 ,   81 ,   84 ,   88 ,   90 ,  100 ,  104 ,  126 ,  132 , ...
32 ,   48 ,   72 ,   80 ,  108 ,  112 ,  120 ,  162 ,  168 ,  176 ,  180 ,  200 ,  208 ,  243 ,  252 , ...
64 ,   96 ,  144 ,  160 ,  216 ,  224 ,  240 ,  324 ,  336 ,  352 ,  360 ,  400 ,  416 ,  486 ,  504 , ...
I noticed that P[i][j] = P[i-1][j]*2 if and only if j < O(1.666^i).
Examples:
i =  2 AND j <   2
i =  3 AND j <   4
i =  4 AND j <   7
i =  5 AND j <  13
i =  6 AND j <  22
i =  7 AND j <  38
i =  8 AND j <  63
i =  9 AND j < 102
i = 10 AND j < 168
i = 11 AND j < 268
i = 12 AND j < 426
I suppose that there is a more accurate approximation of the condition above.
What work has been previously done on the relation between "The Nth number with M prime factors" and "The Nth number with M-1 prime factors"?
Thanks

REPLY [2 votes]: Each sequence of "$n$-almost-primes" opens with a string of even numbers that are twice the entries that begin the previous sequence.  The first odd $n$-almost-prime is $3^n$.  Thus the sequence the OP has observed, $2,4,7,13,22,38,63,\ldots$, is basically the sequence A078843 $(3,5,8,14,23,39,64,\ldots)$ in the OEIS.  There's a recursive formula given there, attributed to Max Alekseyev:
$$a(n) = a(n-1) + \text{appi}3(n-k,[3^n/2^k]),$$
 where $k = \text{ceil}(nc)$ with $c = \log(5/3)/\log(5/2) = 0.55749295\ldots$ and $\text{appi}3(k,n)$ is the number of $k$-almost-primes not divisible by $3$ and not exceeding $n$.  This might supply the "more accurate approximation" the OP referred to.  The ratio of consecutive terms in A078843 seems to be tending to around $1.53$-something, far less than the OP's $1.666$, but all that could be quite illusory.
The link from the OEIS entry to the MathWorld entry on "Almost Primes" may also be of interest.


text:
\begin{document}

\title{To Catch a Falling Robber}

\author{
William B. Kinnersley\thanks{Department of Mathematics, Ryerson University
Toronto, ON, Canada, M5B 2K3, wkinners@ryerson.ca.}\, and
Douglas B. West\thanks{Departments of Mathematics, Zhejiang Normal University,
Jinhua, China 321004,
and  University of Illinois, Urbana, IL 61801, west@math.uiuc.edu.
Research supported by Recruitment Program of Foreign Experts,
1000 Talent Plan, State Administration of Foreign Experts Affairs, China.}
}

\date{}
\maketitle

\begin{abstract}
We consider a Cops-and-Robber game played on the subsets of an $n$-set.
The robber starts at the full set; the cops start at the empty set.
On each turn, the robber moves down one level by discarding an element,
and each cop moves up one level by gaining an element.  The question is
how many cops are needed to ensure catching the robber when the robber
reaches the middle level.  A.~Hill posed the problem and provided a lower
bound of $2^{n/2}$ for even $n$ and $\CH{n}{\CL{n/2}}2^{-\FL{n/2}}$ for odd $n$.
We prove an upper bound that is within a factor of $O(\ln n)$ times this
lower bound.\\
Keywords: Cops-and-robber game; cop number; hypercube; $n$-dimensional cube
\end{abstract}

\baselineskip=16pt

\section{Introduction}
The game of {\it Cops-and-Robber} is a pursuit game on a graph.
In the classical form, there is one robber and some number of cops.
The players begin by occupying vertices, first the cops and then the robber.
In each subsequent round, each cop and then the robber can move along an
edge to an adjacent vertex.  The cops win if at some point there is a cop
occupying the same vertex as the robber.  The {\it cop number} of a graph $G$,
written $c(G)$, is the least number of cops that can guarantee winning.

The game of Cops-and-Robber was independently introduced by
Quilliot~\cite{Qui78} and by Nowakowski and Winkler~\cite{NW83}; both
papers characterized the graphs with cop number $1$.  The cop number as
a graph invariant was then introduced by Aigner and Fromme~\cite{AF84}.
Analysis of the cop number is the central problem in the study of the game
and often is quite challenging.  The foremost open problem in the field is
Meyniel's conjecture that $c(G) = O(\sqrt{n})$ for every $n$-vertex connected
graph $G$ (first published in~\cite{F}).  For more background on
Cops-and-Robber, see~\cite{BN11}.

We consider a variant of the Cops-and-Robber game on a hypercube, introduced in
the thesis of A.~Hill~\cite{Hil08}.  This variant restricts the initial
positions and the allowed moves.  The $n$-dimensional hypercube is the graph
with vertex set $\{0,1\}^n$ (the set of binary $n$-tuples) in which vertices
are adjacent if and only if they differ in one coordinate.  View the vertices
as subsets of $\{1,\ldots,n\}$, and let the {\it $k$th level} consist of the
vertices whose size as subsets if $k$.

The robber starts at the full set $\{1,\ldots,n\}$; the cops start at the
empty set $\nul$.  On the $k$th round, the cops all move from level $k-1$ to
level $k$, and then the robber moves from level $n+1-k$ to level $n-k$.
If the cops catch the robber, then they do so on round $\CL{n/2}$ at level
$\CL{n/2}$, when they move if $n$ is odd, and by the robber moving onto them if
$n$ is even.

Let $c_n$ denote the minimum number of cops that can guarantee winning the
game.  Hill~\cite{Hil08} provided the lower bound $2^{n/2}$ for even $n$ and
$\CH{n}{\CL{n/2}}$ for odd $n$.  Note that in this variant the cops have in
some sense only one chance to catch the robber, on the middle level.  When
the cops have the opportunity to chase the robber by moving both up and down,
it is known that the value is much smaller, with the cop number of the
$n$-dimensional hypercube graph being $\CL{(n+1)/2}~\cite{MM87}$.

We first include a proof of Hill's lower bound, since its ideas motivate our
arguments.  We then prove our main result: an upper bound that is within a
factor of $O(\ln n)$ times this lower bound.

\bigskip

\begin{theorem}[\cite{Hil08}]\label{lower}
$c_n \ge
\left \{ \begin{array}{ll}
   2^{m},                   &n=2m;\\
   2^{-m}\binom{2m+1}{m+1}, &n=2m+1.
\end{array} \right.$
\end{theorem}
\begin{proof}
After each move by the robber, some cops may no longer lie below the robber.
Such cops are effectively eliminated from the game.  We call them {\em evaded
cops}; cops not yet evaded are {\em surviving cops}.

Consider the robber strategy that greedily evades as many cops as possible with
each move.  Deleting an element from the set at the robber's current position
evades all cops whose set contains that element.  On the $k$th round, the
surviving cops sit at sets of size $k$, and the robber has $n-k+1$ choices of
an element to delete.  Since each surviving cop can be evaded in $k$ ways,
the fraction of the surviving cops that the robber can evade on this move is
at least $\FR k{n-k+1}$.

After the first $m$ rounds, where $m=\FL{n/2}$, the fraction of the cops that
survive is at most $\prod_{i=1}^{m} \left ( 1 - \frac{i}{n-i+1} \right )$.
When $n=2m$, we compute
$$
\PE i1m \left(1-\frac{i}{2m-i+1}\right)
= \PE i1m \frac{2m-2i+1}{2m-i+1}
= \frac{(2m)!}{(2m)!\cdot2^m} = 2^{-m}.
$$
When $n=2m+1$, we compute
$$
\prod_{i=1}^{m} \left(1-\frac{i}{2m-i+2} \right)
= \prod_{i=1}^{m} \frac{2m-2i+2}{2m-i+2}
= \frac{2^m m! (m+1)!}{(2m+1)!}
= 2^m \Big/ \binom{2m+1}{m+1}.
$$
In either case, with fewer than the number of cops specified, the number of
cops surviving to catch the robber after $m$ moves by the robber is less than
$1$, and the robber wins.
\end{proof}

\section{The Upper Bound}

If there are enough cops to cover the entire middle level, then the robber
cannot sneak through.  The size of the middle level is asymptotic to
$2^n/\sqrt{\pi n/2}$.  This trivial upper bound is roughly the square of the
lower bound above.  When n is odd one can reduce the upper bound slightly by
observing that one only needs to reach a subset of level $(n-1)/2$ that hits
the neighborhoods of all the sets at level $(n+1)/2$.  However, as the robber
starts to move, the family of sets that need to be protected shrinks.

Our upper bound on $c_n$ is within a factor of $O(\ln n)$ of the lower bound in
Theorem~\ref{lower}.

\bigskip

\begin{theorem}\label{upper}
$c_n \le
\left \{ \begin{array}{ll}
   O(2^{m}\ln n ),                   &n=2m;\\
   O(2^{-m}\binom{2m+1}{m+1}\ln n ), &n=2m+1.
\end{array} \right.$
\end{theorem}
\begin{proof}
We again use the terminology of evaded and surviving cops.  The cops win if
some cop survives through $m$ rounds.  We consider the case $n=2m$ first,
returning later to the case $n=2m+1$.

Initially, some number $C$ of cops begin at $\nul$.  Let $R$ be the current
set occupied by the robber.  On his $k$th turn, for $k\le m-7$, each surviving
cop at set $S$ chooses the next element for his set uniformly at random from
among $R-S$.  For their last seven turns, the cops use a slightly different
strategy, which we explain later.  We claim that for any strategy used by
the robber, this cop strategy succeeds with positive probability when
$C=(c\ln n)2^{m}$, for some constant $c$ to be specified later.  That is,
some outcome of random choices in the cop strategy in response to the robber
strategy catches the robber.

We argued in Theorem~\ref{lower} that the robber can evade the fraction
$\FR k{n-k+1}$ of the surviving cops in round $k$.  We aim to show that the
robber cannot do much better than this against the random strategy for the cops.
Let $B_k$ be the event that the robber can, by deleting an appropriate element
of his current set $R$, evade more than the fraction $(1+\eps_k)\kfrac$ of the
surviving cops on his $k$th move, where $\eps_k = 1/k^3$.  We claim that, with
positive probability, all the events $\VEC B1{m-7}$ fail to occur.

Suppose that the robber deletes element $i$ on round $k$.  The probability that
a given surviving cop at level $k$ sits at a set $S$ containing $i$ is the
probability that it added $i$ to $S$ sometime during the first $k$ rounds.  A
surviving cop sits at a set contained in $R$, and the robber has made no
distinction among the elements of $R$.  Also, given $S\esub R$, the $k$-lists
of elements from $R$ are equally likely to have been the list of elements added
to $S$ by the cop.  Since $k$ of the elements have been selected by the cop
from the $(n-k+1)$-set $R$, the probability that any one of them was added is
exactly $\kfrac$.

Hence the probability that a given surviving cop will be evaded when the
robber deletes $i$ is $\kfrac$.  Letting $X_{k,i}$ be the number of surviving
cops in round $k$ who are evaded when the robber deletes $i$, we have
$\expect{X_{k,i}}=N_k\cdot\kfrac$, where $N_k$ is the number of surviving cops
at level $k$.  We need the probability that $X_{k,i}$ does not differ much from
its expectation.  Let $p = \kfrac$ and $\mu = N_kp$.  By the Union Bound,
$$\prob{B_k} \le \sum_i \prob{X_{k,i} > (1+\eps_k)\mu} = (n-k+1)\prob{X > (1+\eps_k)\mu},$$
where $X \sim \mathrm{Bin}(N_k, p)$.  The Chernoff Bound now yields
\begin{equation}
\prob{B_k} \le 2(n-k+1)e^{-\eps_k^2\mu/3}.
\end{equation}

Note that $\mu$ decreases as $N_k$ decreases, so we obtain an upper bound on
$\prob{B_k}$ by substituting for $N_k$ a lower bound on $N_k$.  For $k \le m-7$,
if all of $\VEC B1{k-1}$ fail to occur, then
\begin{equation}
N_k\ge C\cdot\PE i1{k-1} \left(1-(1+\eps_i)\frac{i}{n-i+1} \right).
\end{equation}
Since the factors are less than $1$, the lower bound on $N_k$ decreases as
$k$ increases.  To facilitate comparison of this product to the product in
Theorem~\ref{lower}, we compute
\begin{align*}
\PE i1m \frac{1 - \frac{i}{n-i+1}}{1 - (1+\eps_i)\frac{i}{n-i+1}}
          &= \PE i1m \frac{n-2i+1}{n-2i+1-i\eps_i}
           = \PE i1m \left ( 1 + \frac{i\eps_i}{n-2i+1-i\eps_i} \right )\\
          &= \PE i1m \left ( 1 + \frac{1/i^2}{n-2i+1-1/i^2} \right )
         \le \PE i1m \left ( 1 + \frac{1}{i^2} \right )
         \le \prod_{i=1}^{\infty} \left ( 1 + \frac{1}{i^2} \right ).
\end{align*}
Note that $1+\FR{1/i^2}{n-2i+1-1/i^2}>1+1/i^2$ when $i=m=n/2$; if $m\ge2$,
then this factor can be combined with another to get the inequality in the
right direction.
The final product converges to some value $P$.  (The convergence of the product
can be shown by taking the logarithm and using the Integral Test to verify the
convergence of the resulting sum; the details are routine but mildly tedious.)
Thus
$$\prod_{i=1}^{m} \left ( 1 - (1+\eps_i)\frac{i}{n-i+1} \right ) \ge \frac{1}{P} \prod_{i=1}^{m} \left ( 1 - \frac{i}{n-i+1} \right ) = \frac{1}{P}2^{-m}.$$
For $k \le m-7$, the lower bound in (2) has at most $m-8$ factors.  Comparing
it to the full product, we obtain
\begin{align*}
N_k &\ge C \cdot \PE i1{m-8} \left ( 1 - (1+\eps_i)\frac{i}{n-i+1} \right )
 = C\cdot\FR{\PE i1m \left(1-(1+\eps_i)\frac{i}{n-i+1} \right )}
         {\PE i{m-7}m\left(1-(1+\eps_i)\frac{i}{n-i+1} \right )}\\
  &\ge C\cdot\FR{\FR1P 2^{-m}}{\PE i{m-7}m \left(1-\frac{i}{n-i+1}\right)}
   = \frac{C}{P} 2^{-m} \frac{(m+8)(m+7)\cdots(m+1)}{(15)(13) \cdots (3)(1)}\\
    &\ge \frac{C}{P} 2^{-m} \frac{n^8}{5.2 \cdot 10^8}
      = \frac{c}{P \cdot 5.2 \cdot 10^8}n^8 \ln n.
\end{align*}
By (1),
$$
\prob{B_k} \le 2(n-k+1)e^{-\FR1{3k^6}\kfrac\FR c{P\cdot5.2\cdot10^8}n^8\ln n}
\le 2ne^{-\frac{c}{3P \cdot 5.2 \cdot 10^8}n^2 \ln n}.
$$
By the Union Bound,
$$
\prob{\UE k1{m-7} B_k} \le n(n-14)n^{-\frac{c}{3P \cdot 5.2 \cdot 10^8}n^2}.
$$
The bound tends to $0$ as $n$ tends to infinity, so almost always none of
$\VEC B1{m-7}$ occur.

Now consider the state of the game just before the cops move to level $m-6$.
Let $N$ be the number of surviving cops.  Assuming that no $B_k$ has occurred,
the argument above (with a few small changes) shows that $N$ is at least
$\frac{c}{P \cdot 1.8 \cdot 10^7}n^7 \ln n$; denote this lower bound by $N^*$.
The cops now adopt a different strategy.  Let $\cS$ denote the family of sets
at level $m$ that remain under the robber.  Each surviving cop chooses a path
to some point in $\cS$ that it can reach, uniformly at random, and follows this
path for the remainder of the game regardless of the robber's moves.
We have argued earlier that at any level, each surviving cop is equally likely
to sit at any set under the robber.  Since this is true at level $m-7$,
and each set in $\cS$ is reached by the same number of paths from level $m-7$,
each cop that survives to level $m-7$ is equally likely to reach any vertex
of $\cS$ (not conditioned on its location on level $m-7$; conditioned only
on it surviving to level $m-7$).

If each point in $\cS$ is reached by at least one cop, then the cops win, since
the robber then cannot reach any point at level $m$ without being caught.  For
$A \in \cS$, let $X_A$ denote the event that no cop reaches $A$.  We have argued
that each of the $N$ cops surviving to level $m-7$ will by level $m$ have
traversed a chain from $\nul$ to $\cS$, with all such chains being equally
likely.  We have $\size{\cS} = \binom{m+7}{7}<(\FR{ne}{14})^7$ for sufficiently
large $n$.  Letting $b=(14/e)^7$,
$$
\prob{X_A} \le \left (1 - \frac{b}{n^7}\right )^{N^*}
\le e^{-\frac{b}{n^7}N^*} \le e^{-\frac{c}{30P} \ln n}.
$$
Now the Union Bound yields
$$
\prob{\bigcup_{A \in \cS} X_A} \le \frac{n^7}{b}e^{-\frac{c}{30P} \ln n}
= \frac{n^7}{b}n^{-\frac{c}{30P}}.
$$

If none of the events $B_k$ and $X_A$ occur, then the cops win.  But
$$
\prob{\left(\UE k1{m-7} B_k \right)\cup\left(\bigcup_{A \in \cS} X_A \right)}
\le n^2 e^{-\frac{c}{3P \cdot 5.2 \cdot 10^8}n \ln n}
+ \frac{n^7}{b}n^{-\frac{c}{30P}}.
$$
Taking $c=210P$, this probability tends to $1/b$ as $n$ tends to infinity.
Hence the cops win with positive probability, which completes the proof for
$n = 2m$.

When $n=2m+1$, the cops use the same strategy until their final move (from level
$m$ to $m+1$).  We claim that this strategy succeeds with positive probability
when $C = c \ln n 2^{(m+1)}/\sqrt{n}$ for some constant $c$.  This is
equivalent to the claimed bound, since
$\binom{2m+1}{m+1} \sim 2^{2m+1} / \sqrt{m\pi}$.  As before,
$\prob{\bigcup_{k=1}^{m-7} B_k}$ tends to 0 as $n$ tends to infinity.  Let $N$
denote the number of surviving cops just before round $m-6$; arguments like
those used above yield $N \ge N^*$, where $N^*=\FR{cn^7}{P\cdot8.3\cdot10^7}$.

Consider the state of the game just before round $m-6$.  Let $\cS$ and $\cS'$
denote the families of sets at levels $m$ and $m+1$, respectively, still below
the robber.  As before, each cop now follows a uniformly randomly chosen path
to $\cS$.  After the robber's $m$th move, the cops sit at sets in $\cS$, and the
robber sits somewhere in $\cS'$.  If some cop still remains below the robber,
then that cop captures the robber and the cops win; otherwise, the robber wins.
Hence it suffices to ensure that, for each $A \in \cS'$, some cop reaches a
set below $A$ in $\cS$.

Since $\size{\cS'} = \binom{m+8}{7}$ and $\size{\cS} = \binom{m+8}{8}$, we have
$\size{\cS'} \le n^7/b$ and $\size{\cS} \le n^8/b'$ for sufficiently large $n$,
where $b'=(16/e)^8$.  For $A \in \cS'$, let $X_A$ denote the event that no cop
reaches a set below $A$.  For each surviving cop, the chains from $\nul$ to
$\cS$ are equally likely to be followed during the game.  Since $A$ has $m+1$
neighbors in $\cS$, a given cop reaches some set below $A$ with probability at
least $\frac{m+1}{n^8/b'}$, which is at least $\frac{b'/2}{n^7}$.  Thus
$$
\prob{X_A} \le \left (1 - \frac{b'/2}{n^7}\right )^{N^*} \le
e^{-\frac{b'/2}{n^7}N^*} \le e^{-\frac{3c}{5P} \ln n}.
$$
By the Union Bound,
$$
\prob{\bigcup_{A \in \cS'} X_A} \le \frac{n^7}{b}e^{-\frac{3c}{5P} \ln n} =
\frac{n^7}{b}n^{-\frac{3c}{5P}}.
$$
Taking $c = 35P/3$, the claim follows as before.
\end{proof}

By more careful analysis, one can allow the cops to change strategies at level
$m-5$ instead of level $m-7$.  This does not affect the asymptotics of the
bound, but it does yield some improvement in the leading constant.


TITLE: self similar solution for porous medium equation
QUESTION [0 upvotes]: firstly
what does the in-variance under the scaling transformation mean ?
secondly
let $u$ be a function invariant under the scaling transformation $$u_k(x,t)=k^nu(kx,k^{2+(m-1)n}t)$$ $k>0$
such that $$u_k(x,t)=u(x,t)$$ $x\in R^n$ ,$t>0$ , $k>0$ is satisfied .
then he said $u$ can be expressed by $$u(x,t)=t^{-l}w(t^{-l/n}x)$$ with $w(y)=u(y,1)$ $y\in R^n$ $k=t^{-l/n}$ $l=\frac{n}{2+(m-1)n}$
where did the the expression come from ?

REPLY [2 votes]: Invariance of an equation with respect a transformation (or more generally a group of transformations) meas that if $u$ is a solution of the equation and $v$ is the scaled solution (i.e., $u$ subject to he transformation) then $v$ is also a solution.
In the example you give, it would mean that if $u$ is a solution, then $u_k$ is also a solution. The solution $u$ is called self-similar if $u_k=u$ for all $k$. This type of solution s important for several reasons, among them:

Sometimes can be obtained explkiciteky
Often they represent a generic behavior of the solutions, for instance, the asymptotic behavior.

As for your last question, set $k=t^{-l/n}$, where $l$ is a constant to be determined. Then
\begin{align}
u(x,t)&=k^n\,u(k\,x,k^{2+(m-1)n}t)\\
&=t^{-l}\,u(t^{-l/n}\,x,t^{-2l/n-l(m-1)+1}).
\end{align}
Now choose $l$ so that $-2\,l/n-l\,(m-1)+1=0$.


TITLE: Why does the sigma algebra generated by a rectangle include one side of a number line?
QUESTION [0 upvotes]: Consider an open interval $(-\infty, a)$, where $a \in \mathbb{Q}$. Why does it hold that
$$
\left\{ (-\infty, a) \mid a \in \mathbb{Q} \right\} \subset \sigma \left( \{ [x,y) \mid x,y, \in \mathbb{Q} \} \right)
$$
I know that you can write $(-\infty, a)$ as $ \bigcup_{n=1}^\infty [-n, a) $ but I struggle to see how that is an element of the sigma algebra generated by some rational interval $[x, y)$. I'm assuming that you cannot just simply set $x = -n$ since $x$ is fixed.

REPLY [2 votes]: You can simply set $x=-n$.  The notation $$\{ [x,y) \mid x,y, \in \mathbb{Q} \}$$ means the set whose elements are $[x,y)$ where $x$ and $y$ range over all elements of $\mathbb{Q}$, not just some fixed elements.  So the $\sigma$-algebra generated by this set contains the interval $[x,y)$ for all $x,y\in\mathbb{Q}$.  In particular, for any $n\in\mathbb{N}$, we can set $x=-n$ and $y=a$ to conclude that $[-n,a)$ is in the $\sigma$-algebra.