text:
\begin{document}

\maketitle
\begin{abstract}
In this paper we investigate connections between linear sets and subspaces of linear maps. We give a geometric interpretation of the results of \cite[Section 5]{Sheekey} on linear sets on a projective line. We extend this to linear sets in arbitrary dimension, giving the connection between two constructions for linear sets defined in \cite{Lunardon}. Finally, we then exploit this connection by using the MacWilliams identities to obtain information about the possible weight distribution of a linear set of rank $n$ on a projective line $\PG(1,q^n)$.

\end{abstract}

{\bf Keywords:} MRD code, weight distribution, linear set, scattered with respect to hyperplanes

\section{Introduction}

Linear sets are important in finite geometry due to their usefulness in constructing and characterising geometrical objects, for example blocking sets and finite semifields; see \cite{olga} for an in-depth treatment of this subject. Scattered linear sets are of particular interest, we refer to \cite{LavScat} for a complete survey.

In this paper we investigate connections between linear sets and subspaces of linear maps. An $\Fq$-subspace $\C$ of $\Fq$-linear maps from $\Fn$ to itself leads naturally to a linear set $\Omega(\C)$ in $\PG(n-1,q^n)$. If such a subspace is in fact a $k$-dimensional $\Fn$-subspace, it also naturally leads to a linear set $\Gamma_\C$ in $\PG(k-1,q^n)$. These two seemingly distinct objects were considered in \cite{Lunardon}, \cite{Sheekey}. In \cite{Sheekey} an algebraic connection was shown between these linear sets in the special case of $k=2$, giving a correspondence between $2$-dimensional $\Fn$-linear {\it MRD codes} and {\it scattered linear sets} of rank $n$ on the projective line $\PG(1,q^n)$. This connection has lead to further investigations in \cite{CsajMarPol,CsajMarPolZan,CsajMarZul}.

In this paper we will give a geometric interpretation of the correspondence of \cite{Sheekey}, and extend it to all dimensions. Specifically, we show that
\[
\Gamma_\C \cong \Sigma/\Omega(\C)^\perp,
\]
where $\Sigma$ is a subgeometry, and show how the distribution of the ranks of the linear maps in $\Omega(\C)$ determine the distribution of weights of the points of $\Gamma_\C$.

Furthermore we characterise the linear sets of rank $n$ in $\PG(k-1,q^n)$ defined by $k$-dimensional $\Fn$-linear MRD-codes. We show that they are precisely those linear sets which are {\it scattered with respect to hyperplanes}, a concept which we introduce and is stronger than a linear set being scattered.

Finally we exploit Delsarte's theory of duality for subspaces of linear maps (in particular the rank-metric MacWilliams identities) to obtain information about the possible weight distribution of linear sets of rank $n$ on a projective line $\PG(1,q^n)$.

\section{Preliminaries}

\subsection{Linear sets}
\subsubsection{Definition}
Throughout this paper, we denote the finite field with $q$ elements by $\Fq$ and a $k$-dimensional vector space over $\F_q$ by $V(k,q)$.

The $(k - 1)$-dimensional projective space corresponding to $V(k, q)$ is denoted by $\PG(k-1, q)$. Points in $\PG(k-1,q)$ correspond to one-dimensional subspaces of $V(k,q)$, and $(j-1)$-dimensional subspaces in $\PG(k-1,q)$ correspond to $j$-dimensional subspaces of $V(k,q)$. In general, if $V$ is a vector space, then $\PG(V)$ denotes the correponding projective space.

If $\Fq$ contains a subfield $\F_{q'}$, then we call a subset $U$ of $V(k,q)$ an $\F_{q'}$-subspace if $U$ is closed under addition, and by scalar multiplication by elements of $\F_{q'}$; i.e. for all $u,v\in U$, $\lambda\in \F_{q'}$, we have that $u+v\in U$ and $\lambda u\in U$.

For any subset $U$ of $V(k,q)$ we denote by $U^{\ast}$ the set of nonzero elements of $U$.

\begin{definition}
Suppose $\F_{q'}$ is a subfield of $\Fq$. An {\it $\F_{q'}$-linear set of rank $s$} in $\PG(k-1,q)$ is a set
\[
L(U) := \{\la u\ra_{\Fq} : u\in U^{\ast}\}
\]
for some $\F_{q'}$-subspace $U$ of $V(k,q)$ with $\dim_{\F_{q'}}(U)=s$. Here $\la u\ra_{\Fq}$ denotes the projective point in $\PG(k-1,q)$, corresponding to the vector $u$, where the notation reflects the fact that all ${\Fq}$-multiples of $u$ define the same projective point.

When $u=(u_0,\ldots,u_k)$ is a vector in $V(k,q)$, then $\la u\ra_{\Fq}=\la (u_0,\ldots,u_k)\ra_{\Fq}$ will be denoted as $(u_0,\ldots,u_k)_{\Fq}$.

\end{definition}

In this paper we will be mostly concerned with $\Fq$-linear sets of rank $n$ in $\PG(k-1,q^n)$. Linear sets of rank $n$ are of interest as they are the largest linear sets in terms of rank which do not necessarily meet every hyperplane. Particular attention will be paid to the case where $k=2$, that is, linear sets on a projective line. The following representation will be used throughout; for the first part of this statement, see also \cite[Lemma 7]{Lunardon}.

\begin{lemma}\label{linsetpol}
Suppose $L$ is an $\Fq$-linear set of rank $n$ in $\PG(k-1,q^n)$. Then there exist $\Fq$-linear maps $f_i:\Fn\rightarrow\Fn$ such that
\[
L = \{(f_1(x),\ldots,f_k(x))_{\Fn}:x\in \Fn^{\ast}\},
\]
and $\ker(f_1)\cap\cdots\cap\ker(f_k)=\{0\}$. If $\dim\la L\ra=k-1$, then the maps $\{f_1,\ldots,f_k\}$ are linearly independent over $\Fn$.

Vice versa, if $f_i:\Fn\rightarrow\Fn$ are $\Fq$-linear maps with $\ker(f_1)\cap\cdots\cap\ker(f_k)=\{0\}$, then $L = \{(f_1(x),\ldots,f_k(x))_{\Fn}:x\in \Fn^{\ast}\}$ is an $\F_q$-linear set of rank $n$ in $\PG(k-1,q^n)$.
\end{lemma}

\begin{proof} As $L$ is an $\Fq$-linear set of rank $n$ in $\PG(k-1,q^n)$, $L=L(U)$ for some $\F_q$-subspace $U$ of rank $n$ of $V(k,q^n)$. The $\Fq$-subspace $U$ is isomorphic to $\Fn$ as an $\Fq$-vector space, let $\phi:U\mapsto \Fn$ be this isomorphism. Then $L(U)=\{\la \phi(x)\ra_{\Fn}:x\in \Fn^{\ast}\}$. Now $\phi(x)$ is an element of $V(k,q^n)$, and hence, can be written as $(f_1(x),\ldots,f_k(x))$ where $f_i=p_i\circ \phi$ and $p_i$ is the projection onto the $i$-th coordinate.

If there is a nonzero element in the intersection of the kernel of the $f_i$'s, then the rank of $L$ is strictly less than $n$. Finally if the maps $\{f_1,\ldots,f_k\}$ are linearly dependent over $\Fn$, then there exist $\alpha_i\in \Fn$, not all zero, such that $\sum_i \alpha_i f_i(x)=0$ for all $x$, implying that $L$ is contained in the hyperplane $(\alpha_1,\ldots,\alpha_k)^\perp$, and hence, $\dim\la L\ra \neq k-1$.

Vice versa, if all $f_i$ are $\Fq$-linear maps, then $\{(f_1(x),\ldots,f_k(x)):x\in \Fn\}$ defines an $\Fq$-subspace $U$ of rank $n$ if and only if $\ker(f_1)\cap\cdots\cap\ker(f_k)=\{0\}$. It follows that $L=L(U)$, and hence, $L$ is an $\Fq$-linear set.
 \end{proof}

We denote the $\Fq$-subspace of $V(k,q^n)$ used in this proof by $U_{f_1,\ldots,f_k}$, i.e.

\[U_{f_1,\ldots,f_k} := \{(f_1(x),\ldots,f_k(x)): x\in \Fn \},
\]

and the associated linear set
\[
L_{f_1,\ldots,f_k} := L(U_{f_1,\ldots,f_k})
\]

\begin{definition}
We say that two $\Fq$-subspaces of $V(k,q^n)$ are {\it equivalent} if there exists an element of $\GammaL(k,q^n)$ mapping $L_1$ to $L_2$.

We say that two linear sets $L_1,L_2$ in $\PG(k-1,q^n)$ are {\it equivalent} if there exists an element of $\PGammaL(k,q^n)$ mapping $L_1$ to $L_2$.
\end{definition}

\begin{remark}\label{slechtequiv}
Clearly, if the subspaces $U_1$ and $U_2$ are equivalent, then the linear sets $L(U_1)$ and $L(U_2)$ are equivalent. However the converse is not true; for example, defining
\begin{align*}
U_s&=\{(x,x^{q^s}):x\in \Fn\}\subset V(2,q^n),
\end{align*}
it holds that for any $s\notin \{1,n-1\}$ such that $(s,n)=1$, we have that $U_1$ is inequivalent to $U_s$, but $L(U_1)=L(U_s)$ (see
\cite[Remark 5.6]{CsajMarPol}).
\end{remark}

\begin{definition}\label{defwt}
For a linear set $L(U)$, we define the {\it weight} of a point $P$ defined by a vector $v\in V$ as
\[
wt_{L(U)}(P):=\dim_{\Fq}(U\cap \langle v\rangle_{q^n}).
\]
For an $(s-1)$-dimensional subspace $\pi = \PG(W,q^n)$, where $W$ is an $s$-dimensional $\Fn$-subspace of $V$, we define, following \cite{olga}, the weight of $\pi$ with respect to $L(U)$ by
\[
wt_{L(U)}(\pi) := \dim_{\Fq}(U\cap W).
\]
\end{definition}

\begin{definition}
A linear set $L(U)$ is said to be {\it scattered} if the weight $w_{L(U)}(P)$ of any point $P$ is at most one.
\end{definition}

Scattered linear sets were introduced in \cite{BlLa2000}, and arise in various areas of finite geometry. See \cite{LavScat} for a recent survey on this topic.

\subsubsection{Linear sets as projected subgeometries}\label{proj}

We recall the following correspondence between linear sets and projected subgeometries from \cite{LP}. Let $\Sigma$ be a canonical subgeometry isomorphic to $\PG(s-1,q)$ of $\Sigma^*=\PG(s-1,q^n)$, let $\Lambda^*$ be a $(k-s-1)$- dimensional subspace of $\Sigma^*$ which is skew from $\Sigma$, and let $\Lambda$ be a $(k-1)$-dimensional subspace of $\Sigma^*$, skew from $\Lambda^*$, then the projection of $\Sigma$ from $\Lambda^*$ onto $\Lambda$, denoted by $p_{\Lambda^*,\Lambda}(\Sigma)$ defines an $\F_q$-linear set of rank $s$ in $\Lambda$. Vice versa, every $\F_q$-linear set of rank $s$ in $\PG(k-1,q^n)$ can be obtained in this way.

The following equivalent point of view for the weight of a point $P$ in a linear set, obtained as a projected subgeometry, has been used in the literature. However, by lack of an explicit proof for the equivalence of both definitions, give a proof here. This result will be used in Proposition \ref{BW}.

\begin{proposition} \label{weightproj} Let $L=p_{\Lambda^*,\Lambda}(\Sigma)$ be a linear set of rank $s$ in $\Lambda=\PG(k-1,q^n)$ obtained by projecting $\Sigma$, an $(s-1)$-dimensional $\Fq$-subgeometry of $\Sigma^*=\PG(s-1,q^n)$ from the $(s-k-1)$-dimensional subspace $\Lambda^*$ of $\Sigma^*$ onto $\Lambda$. Let $\Lambda^*=\PG(Y)$, where $Y$ is an $(s-k)$dimensional $\Fn$-vector space and let $\Lambda=\PG(Z)$, where $Z$ is a $k$-dimensional $\Fn$-vector space. Let $\Sigma=\PG(T)$, where $T$ is an $s$-dimensional $\Fq$-vectorspace, and let $\Sigma^*$ be $\PG(T^*)$ where $T^*=T\otimes\Fn$. Then $L=L(U)$ with $U=Z\cap (Y\oplus T)$, and if $\pi$ is a subspace of $\Lambda$, then $wt_{L(U)}(\pi)$, the weight of $\pi$ with respect to $L(U)$, is equal to one plus the dimension of the $\Fq$-subspace $(\la \pi,\Lambda^*\ra \cap \Sigma)$ of the subgeometry $\Sigma$.

\end{proposition}

\begin{proof}It follows from the construction, given in \cite[Theorem 1]{LP}, that  $p_{\Lambda^*,\Lambda}(\Sigma)=L(U)$ with $U=Z\cap (Y\oplus T)$, where $Y$ and $Z$ are considered as $\Fq$-subspaces of dimensions $n(s-k)$ and $nk$ respectively.

 Now by Definition \ref{defwt}, if $\pi=\PG(W)$, with $W\leq Z$, then $wt_{L(U)}(\pi)$ is equal to $\dim_{\Fq}(U\cap W)=\dim_{\Fq}((Z\cap (Y\oplus T))\cap W)$. Since $W\leq Z$, this is equal to $\dim_{\Fq}( (Y\oplus T)\cap W)$. Now  since $Y,T,W$ are disjoint $\Fq$-subspaces, this equals $\dim_{\Fq}(\la Y,T,W\ra)-\dim_{\Fq}(Y)-\dim_{\Fq}(T)-\dim_{\Fq}(W)=\dim_{\Fq}((Y\oplus W) \cap T)$. The subspace $(Y\oplus W) \cap T$ corresponds to the $\Fq$-subspace $(\la \pi,\Lambda^*\ra \cap \Sigma)$ of the subgeometry $\Sigma$ and the statement follows.
\end{proof}

\subsection{Linear maps and linearised polynomials}

\subsubsection{The spaces $\End_{\Fq}(\F_{q^n})$ and $\PG(\End_{\Fq}(\F_{q^n}))$}

Every $\Fq$-linear map from $\Fn$ to $\Fn$ can be uniquely represented as a linearised polynomial, i.e., as
$$f:x\mapsto \a_0x+\a_1x^q+\a_2x^{q^2}+\ldots+a_{n-1}x^{q^{n-1}},$$ where $\a_0,\ldots,a_{n-1}$ are elements of $\Fn$.
For $f,g$ $\Fq$-linear maps and $\a\in \Fn$, we have that $\a f:=x\mapsto \a f(x)$ and $f+g:=x\mapsto f(x)+g(x)$ are $\Fq$-linear maps as well. Hence, the set of $\Fq$-linear maps of $\Fn$ to $\Fn$, which is denoted by $\End_{\Fq}(\F_{q^n})$, forms an $\Fn$-vector space. Since there are $q^{n^2}$ such maps, $\End_{\Fq}(\F_{q^n})$ is $n$-dimensional over $\Fn$, and so $\E$ is isomorphic to $V(n,q^n)$. From now on we will write $V$ for $V(n,q^n)$.

We consider the projective space $\PG(\V)=\PG(n-1,q^n)$. Every point of $\PG(\V)$ is represented by an $\Fq$-linear map, defined up to a multiple of $\Fn$, so we denote the point corresponding to the map $f$ by $\la f\ran$.

Equivalently, we can make the correspondence $\V\mapsto \PG(n-1,q^n)$ explicit by defining the map $f\mapsto (\a_0,\a_1,\ldots,\a_{n-1})_{q^n}$, if $f:x\mapsto \a_0x+\a_1x^q+\a_2x^{q^2}+\ldots+a_{n-1}x^{q^{n-1}}$. Here, $(\a_0,\a_1,\ldots,\a_{n-1})_{q^n}$ denotes the projective point with homogeneous coordinates $(\a_0,\a_1,\ldots,\a_{n-1})$. We will abuse notation liberally throughout, by using the symbol $f$ to denote both a linearised polynomial and its coefficient vector, and switch freely between the two.

 \begin{definition} Given a linearised polynomial $f$, the {\it rank} of the corresponding vector in $V$ and point in $\PG(n-1,q^n)$ is the rank of $f$ as an element of $\E$. \end{definition}
\begin{definition} We will say a linearised polynomial (and its corresponding vector) is {\it invertible} if it has no non-zero roots in $\Fn$. \end{definition}

We denote the composition of two linearised polynomials $f,g$ as $f\circ g$, i.e. $(f\circ g)(x) := f(g(x))\mod x^{q^n}-x$. We define the dot product of two linearised polynomials $f=\sum \alpha_i x^i$, $g=\sum_i \beta_i x^i$ as the usual dot product of their coefficient vectors, i.e.
 \[
 f\cdot g := \sum_{i=0}^{n-1}\alpha_i \beta_i.
 \]

\subsubsection{The spaces $\Sigma_i$}

Every $\Fq$-linear map of rank $1$ is of the form $\a\Tr(\b x)$, where $\Tr$ is the trace map from $\Fn$ to $\Fq$, i.e., $\Tr:x\mapsto x+x^q+\ldots+x^{q^{n-1}}$. As $\la\a\Tr(\b x)\ran=\la \a' \Tr(\b x)\ran$ and $\la\Tr(\b x)\ran=\la \Tr(\lambda \b x)\ran$ if $\lambda \in \Fq^\ast$, we see that there are exactly $\frac{q^n-1}{q-1}$ projective points  $\la f\ran$ with $f$ a map of rank $1$. Call this set $\Sigma$. We get that
$$\Sigma = \{(\b,\b^q,\b^{q^2},\ldots,\b^{q^{n-1}})_{q^n}\mid \b\in \Fn^\ast\}$$ and
we see that $\Sigma$ defines an $\Fq$-subgeometry of $\PG(n-1,q^n)$.

In general, we define subsets $\Sigma_i$ of $\PG(n-1,q^n)$ by
\[
\Sigma_i = \{(\a_0,\a_1,\ldots,\a_{n-1})_{q^n} : \rank(\a_0x+\a_1x^q+\a_2x^{q^2}+\ldots+a_{n-1}x^{q^{n-1}}) \leq i\}.
\]
or, equivalently,
\[
\Sigma_i = \{\langle f\rangle_{q^n}: f\in V,\rank(f) \leq i\}.
\]
We see that $\Sigma_1$ equals the subgeometry $\Sigma$. It is well-known that any rank $k$ map can be written as the sum of $k$ rank $1$ maps. This means that the points of $\PG(\End_{\Fq}(\F_{q^n}))$ corresponding to maps of rank $k$ are all of the form $$\la \psi_1\Tr(\a_1 x)+\psi_2\Tr(\a_2 x)+\ldots+\psi_k\Tr(\a_k x)\ran$$ for some $\psi_1,\psi_2,\ldots,\psi_k$, and $\a_1,\ldots, \a_k$ in $\Fn$. Geometrically, these points are the points that lie on a subspace spanned by $k$ points of $\Omega$. This means that $\Sigma_i$ is the $(i-1)$-st {\em secant variety} of $\Sigma$. We see that the points in $\Sigma_{i}\backslash \Sigma_{i-1}$ are precisely the points of rank $i$.

\subsection{Rank-metric codes}
\subsubsection{Definition}
A {\it rank-metric code} is a set of maps $\C\subset \End_{\Fq}(\Fn)\simeq V$, with distance defined by the rank-distance;
\[
d(f,g) = \rank(f-g).
\]
As outlined above, we may regard $\C$ as a set of linearised polynomials. We define (following the notation of \cite{Lunardon}) the set $\Omega(\C)\subset \PG(n-1,q^n)$ by
\[
\Omega(\C) := \{\langle f\rangle_{q^n}:f\in \C^\ast\}.
\]
If $\C$ is an $\Fq$-subspace of $V$, then $\Omega(\C)$ is a linear set in $\PG(n-1,q^n)$. If $\C$ is an $\Fn$-subspace of $V$, then $\Omega(\C)$ is a subspace of $\PG(n-1,q^n)$.

\begin{definition}
A set $\C\subset V$ is called a {\it maximum rank distance} code if $|\C|=q^{nk}$ and the rank of any nonzero $f\in \C$ is at least $n-k+1$. The following is immediate by definition (see also \cite{Lunardon}).
\end{definition}

\begin{proposition}
A subset $\C$ of $V$ of size $q^{nk}$ is a maximum rank distance code if and only if $\langle f-g\rangle_{\Fn} \notin \Sigma_{n-k}$ for all $f,g\in \C$ with $f\ne g$.

An additively closed subset $\C$ of $V$ of size $q^{nk}$ is a maximum rank distance code if and only if $\Omega(\C)$ is disjoint from $\Sigma_{n-k}$.
\end{proposition}

This setup is very similar as for the geometric construction of (spread sets for) {\em semifields}, proven in \cite{LavSem}.

\subsubsection{Equivalence for rank-metric codes}

\begin{definition}
Two rank-metric codes $\C_1$ and $\C_2$ are said to be {\it equivalent} if there exist linearised polynomials $g,h,k\in \E$, with $g,h$ invertible, and an automorphism $\rho$ of $\Fn$ (not necessarily fixing $\Fq$), such that
\[
\C_2 = \{g\circ f^\rho\circ h +k : f\in \C_1\}.
\]

The action of $\rho \in \Aut(\F_{q^n})$ is defined by $f^\rho := \sum_{i=0}^{n-1} \a_i^\rho x^{q^i}$; i.e. $f^\rho(x) = (f(x^{\rho^{-1}}))^\rho$.
\end{definition}
 If $\C_1,\C_2$ are $\Fq$-subspaces of $\E$, then we may assume $k=0$.

\begin{definition}(see \cite{morrison})
Two rank-metric codes $\C_1$ and $\C_2$ are said to be {\it semilinearly equivalent} if there exist an invertible linearised polynomial $h\in \E$, an integer $m\in \{0,\ldots,n-1\}$, and an automorphism $\rho$ of $\F_{q^n}$, such that
\[
\C_2 = \{x^{q^m}\circ f^\rho \circ h : f\in \C_1\}.
\]
\end{definition}
Clearly semilinear equivalence implies equivalence.

\begin{proposition}
\label{prop:Fnpreserve}
Suppose $\C$ is an $\Fn$-subspace of $V$. Suppose $g(x) = \sum_{m=0}^{n-1}g_mx^{q^m}$ is an invertible linearised polynomial such that $g\circ \C$ is also an $\Fn$-subspace of $V$. Then for every $m$ such that $g_m\ne 0$, it holds that $g\circ \C = x^{q^m}\circ \C$.
\end{proposition}

\begin{proof}
Suppose $\C$ is $k$-dimensional over $\Fn$. Then $g\circ \C$ is an $\Fn$-subspace if and only if there exists an $(n-k)$-dimensional subspace $\H$ of $V$ such that $(g\circ f)\cdot h=0$ for all $f\in \C,h\in \H$. Furthermore $g'\in g\circ \C$ if and only if $g'\cdot h=0$ for all $h\in \H$. Put $f=\sum_{i=0}^{n-1}f_ix^{q^i}$, $g=\sum_{m=0}^{n-1}g_mx^{q^m}$ and $h=\sum_{i=0}^{n-1}h_i x^{q^i}$. Now as $\alpha f \in \C$ for all $f\in \C$ and all $\alpha \in \Fn$, then for any $h\in \H$ we have
\begin{align*}
(g\circ \alpha f)\cdot h &= \left(\sum_{i=0}^{n-1} \left(\sum_{m=0}^{n-1} g_m \alpha^{q^m} f_{i-m}^{q^m}\right)x^{q^i}\right)\cdot \left(\sum_{i=0}^{n-1} h_i x^{q^i}\right),
\end{align*}
where we have used the convention that $f_l=f_{n-l}$ if $l<0$. Now we find that
\begin{align*}
\left(\sum_{i=0}^{n-1} \left(\sum_{m=0}^{n-1} g_m \alpha^{q^m} f_{i-m}^{q^m}\right)x^{q^i}\right)\cdot \left(\sum_{i=0}^{n-1} h_i x^{q^i}\right)&=  \sum_{i=0}^{n-1} \left(\sum_{m=0}^{n-1} g_m \alpha^{q^m} f_{i-m}^{q^m}\right)h_i\\
&= \sum_{m=0}^{n-1} g_m \left(\sum_{i=0}^{n-1} f_{i-m}^{q^{\color{blue}m}} h_i\right) \alpha^{q^m}\\
&= \sum_{m=0}^{n-1} g_m ((x^{q^m}\circ f) \cdot h)\alpha^{q^m}\\
&=0
\end{align*}
for all $\alpha \in \Fn$. Thus for each $m$ we must have $g_m ((x^{q^m}\circ f) \cdot h)=0$, and so if $g_m\ne 0$ then $(x^{q^m}\circ f) \cdot h = 0$ for all $f\in \C,h\in \H$. But then $x^{q^m}\circ f\in g\circ \C$ for all $f\in \C$, implying $g\circ \C = x^{q^m}\circ \C$, as claimed.
\end{proof}

\begin{proposition}
\label{prop:Fnequiv}
Suppose $\C_1$ and $\C_2$ are $\Fn$-subspaces of $V$. Then $\C_1$ and $\C_2$ are equivalent if and only if they are semilinearly equivalent.
\end{proposition}

\begin{proof}
If $\C_1$ and $\C_2$ are semilinearly equivalent, then by definition they are equivalent. Suppose now $\C_1$ and $\C_2$ are equivalent, i.e. $\C_2^\rho = g\circ \C_1 \circ h$ for some invertible $g,h$. Now $\C_2^\rho\circ h^{-1}$ is an $\Fn$-subspace, and hence, $g\circ \C_1$ is an $\Fn$-subspace. So, by Proposition \ref{prop:Fnpreserve} there exists an $m$ such that $g\circ \C_1 = x^{q^m}\circ \C_1$. Therefore $\C_2^\rho = x^{q^m} \circ \C_1 \circ h$, and so $\C_1$ and $\C_2$ are semilinearly-equivalent, proving the claim.
\end{proof}

\begin{remark}
If we regard $V$ as a vector space over $\Fq$, then the set of rank one maps defines a {\it Segre variety} in $\PG(V,\Fq)\simeq \PG(n^2-1,q)$. The set of one-dimensional $\Fn$-subspaces of $V$ corresponds to a desarguesian spread $\D$, and the Segre variety is partitioned by these spaces. This is the field-reduction of the subgeometry $\PG(n-1,q)$. $\Fn$-subspaces are then precisely those subspaces spanned by elements of $\D$

The collineation group of $\PG(n^2-1,q)$ is $\PGammaL(n^2,q)$. The subgroup of this fixing $\D$ is isomorphic to $\PGammaL(n,q^n)$.

The group induced by the set of equivalences is the set of elements of $\PGammaL(n^2,q)$ which fix the field-reduced subgeometry.

The group induced by the set of semilinear equivalences is the set of elements of $\PGammaL(n,q^n)$ which fix the field-reduced subgeometry. It is well-known that this has the form $\Aut(\Fn:\Fq).\PGammaL(n,q)$.

Hence what we have shown here is that two subspaces of $\PG(n^2-1,q)$ obtained by field-reduction of subspaces of $\PG(n-1,q^n)$ are equivalent under the stabiliser in $\PGammaL(n^2,q)$ of the field-reduced subgeometry if and only if the two subspaces are equivalent under the stabiliser in $\PGammaL(n,q^n)$ of the field-reduced subgeometry.

We suspect that this result may be known. However as we could not find an exact reference, we chose to include a proof. Similar ideas can be found in for example \cite{LiebholdNebe}, \cite{morrison}, though neither imply this result.
\end{remark}

\subsection{Duality in $\E$ and in $\PG(n-1,q^n)$}

Delsarte considered duality in $V=\E$ by representing endomorphisms as matrices over $\Fq$ and defining a symmetric bilinear form
\[
(A,B)\mapsto \Tr(AB^T),
\]
where $\Tr$ denotes the matrix trace. He showed that using this inner product, the rank-distribution of a subspace and its dual are related by a rank-metric version of the MacWilliams identities \cite{Delsarte}.

In this paper we will use a different symmetric bilinear form, more suited to working with linearised polynomials, following \cite{Sheekey}. The dual of a subspace with respect to this form is equivalent to the dual with respect to the form used by Delsarte.

For two elements of $V$ given by $f:x\mapsto \sum_{i=0}^{n-1}f_i x^{q^i}$, $g:x\mapsto \sum_{i=0}^{n-1}g_i x^{q^i}$, we define the symmetric bilinear form
\[
(f,g)\mapsto \tr\left(\sum_{i=0}^{n-1} f_i g_i\right),
\]
where $\tr$ denotes the field trace from $\Fn$ to $\Fq$.

The {\em (Delsarte) dual} of an $\F_q$-subspace $\C$ of $V$ is then defined as
$$\C^{\bot}=\left\{g \in V : \tr\left(\sum_{i=0}^{n-1} f_i g_i\right)=0\ \forall f\in \C\right\}.$$

If $\C$ is an $\Fn$-subspace of $V$, then it is easy to check that the dual of $\C$ with respect to this form is equal to the dual of $\C$ with respect to the form
\[
(f,g)\mapsto \sum_{i=0}^{n-1} f_i g_i = f\cdot g.
\]

Thus we may alternatively define the {\em (Delsarte) dual} of an $\Fn$-subspace $\C$ of $\E$ as
$$\C^{\bot}=\{g \in V : f \cdot g=0\ \forall f\in \C\}.$$
\begin{remark}
Care should be taken when considering duality for rank-metric codes in the non-square case, as duals with respect to this dot product may not be equivalent to duals with respect to Delsarte's form. In this paper we are only concerned with the square case.
\end{remark}

The (Delsarte) dual of an MRD code is again an MRD code. For more information about duality of rank-metric codes, we refer to \cite{Ravagnani}.

The Delsarte dual operation $\bot$ on $\E$ induces a dual operation on $\PG(n-1,q^n)$, which we also will denote by $\bot$. In particular, as seen in the previous subsection, an $\F_{q^n}$-linear subspace $\C$ of $\E$ corresponds to a projective subspace $\Omega(\C)$ of $\PG(n-1,q^n)$ and we have that

 $$\Omega(\C^\perp)=\Omega(\C)^\perp.$$

\section{Linear sets from MRD codes}

In this section we provide a geometric interpretation of the correspondence outlined in \cite{Sheekey} between scattered linear sets on a projective line and certain classes of MRD codes. In Section \ref{new} we will extend this correspondence to MRD codes of higher dimensions. We will incorporate the notion of Delsarte duality of a rank-metric code into this geometric picture, which will allow us to exploit the MacWilliams identities for rank-metric codes to investigate linear sets in Section \ref{mac}.

\subsection{Linear sets in $\PG(k-1,q^n)$ from $\Fn$-subspaces of $V$}\label{omegas}

Suppose $\C$ is a $k$-dimensional $\Fn$-subspace of $V$, and hence $\Omega(\C)$ a $(k-1)$-dimensional subspace of $\PG(n-1,q^n)$. Recall that $\Sigma$ is an $\Fq$-subgeometry of $\PG(n-1,q^n)$.

\begin{proposition}\label{omegabot}
If $\C$ is a $k$-dimensional $\Fn$-subspace of $V$, then $\{x\in \Fn:g(x)=0~\forall g\in \C\}=\{0\}$ if and only if $\Omega(\C)^{\perp}\cap \Sigma=\emptyset$.
\end{proposition}

\begin{proof} If $g\in \C$, then $g$ is a linearised polynomial, so we can write $g(x)=\sum_{i=0}^{n-1} g_i x^{q^i}$.
A point $(x,x^q,\ldots,x^{q^{n-1}})_{q^n}\in \Sigma$ is in $\Omega(\C)^\perp$ if and only if $(x,x^q,\ldots,x^{q^{n-1}})\cdot (g_0,\ldots,g_{n-1})=0$ for all $g\in \C$, if and only if $\sum_{i=0}^{n-1} g_i x^{q^i}=0$ for all $g\in \C$, if and only if $g(x)=0$ for all $g\in \C$.
\end{proof}

As we saw in Lemma \ref{linsetpol}, a $k$-tuple of linearised polynomials gives an $\Fq$-subspace of $V(k,q^n)$
$$U_{f_1,\ldots,f_k}=\{(f_1(x),\ldots,f_k(x))\vert x\in \mathbb{F}_{q^n}\},$$
and a linear set in $\PG(k-1,q^n)$
$$L_{f_1,\ldots,f_k}:=\{(f_1(x),\ldots,f_k(x))_{q^n}\vert x\in \mathbb{F}_{q^n}^*\} = L(U_{f_1,\ldots,f_k}).$$

Thus from a $k$-dimensional $\Fn$-subspace $\C$ of $V$, we can define a family of linear sets in $\PG(k-1,q^n)$.
\begin{definition}
For a $k$-dimensional $\Fn$-subspace $\C$ of $V$, we define a set of $\Fq$-subspaces of $V(k,q^n)$ by
$$\U_\C:=\{U_{f_1,\ldots,f_k}:f_i \in V, \C = \langle f_1,\ldots,f_k\rangle_{q^n}\},$$
and a set of linear sets in $\PG(k-1,q^n)$ by
$$\L_\C:=\{L_{f_1,\ldots,f_k}:f_i \in V, \C = \langle f_1,\ldots,f_k\rangle_{q^n}\}.$$
\end{definition}

Different choices of basis for $\C$ may give different linear sets. However, it is easy to prove that they are all $\PGL(k,q^n)$-equivalent.

\begin{proposition}\label{propeq}
Suppose $\C$ is a $k$-dimensional $\Fn$-subspace of $V$ such that $\Omega(\C)^{\perp}\cap \Sigma=\emptyset$. Then any two elements of $\L_\C$ are $\PGL(k,q^n)$-equivalent linear sets of rank $n$ in $\PG(k-1,q^n)$. Conversely, for any $L\in \L_\C$ and any $\phi \in \PGL(k,q^n)$, it holds that $L^\phi \in \L_\C$. Thus $\L_\C$ is a $\PGL(k,q^n)$-equivalence class of linear sets of rank $n$ in $\PG(k-1,q^n)$.

\end{proposition}

\begin{proof}
Let $L_{f_1,\ldots,f_k}$ be an element of $\L_\C$. If there would be a non-zero element $y\in \Fn$ such that $f_1(y)=\ldots=f_k(y)=0$, then, as $f_1,\ldots,f_k$ is a basis for $\C$, $y$ would be contained in $\{x\in \Fn:g(x)=0~\forall g\in \C\}$, a contradiction by Lemma \ref{omegabot}, since $\Omega(\C)^{\perp}\cap \Sigma=\emptyset$ by our assumption. So this implies that $f_1,\ldots,f_k$ have no non-trivial common zeroes and that $L_{f_1,\ldots,f_k}$ has rank $n$ by Lemma \ref{linsetpol}.

Now consider $L_{f_1,\ldots,f_k}$ and $L_{f_1',\ldots,f_k'}$ in $\L_\C$. As $f_1,\ldots,f_k$ and $f_1',\ldots,f_k'$ each form a basis for $\C$, we know that there is an element $\phi$ of $\GL(k,q^n)$ such that $f_j' = \sum_{i=1}^k \phi_{ij}f_i$. Then
\[
(f_1(x),\ldots,f_k(x))\phi = (f_1'(x),\ldots,f_k'(x))
\]
for all $x$, and so $\la \phi\ra_{q^n}$ is an element of $\PGL(k,q^n)$ mapping $L_{f_1,\ldots,f_k}$ onto $L_{f_1',\ldots,f_k'}$.

Conversely, for any $\phi$ of $\GL(k,q^n)$, and $L_{f_1,\ldots,f_k}\in \L_\C$, define $f_j' = \sum_{i=1}^k \phi_{ij}f_i$. Then $f_1',\ldots,f_k'$ forms a basis for $\C$, and

\[
(L_{f_1,\ldots,f_k})^{\la \phi\ra_{q^n}} = L_{f_1',\ldots,f_k'}\in \L_\C.
\]

\end{proof}

\begin{proposition}\label{propeq2}
If $\C$ and $\C'$ are equivalent $\Fn$-subspaces of $V$, then there exists for every $L\in \L_\C$, an element $\phi\in \PGammaL(k,q^n)$ such that $L^\phi\in \L_{\C'}$.

A linear set $L$ is $\PGammaL(k,q^n)$-equivalent to an element of $\L_\C$ if and only if $L\in \L_{\C^\sigma}$ for some $\sigma\in \Aut(\Fn)$. Thus
\[
\bigcup_{\sigma\in \Aut(\Fn)} \L_{\C^\sigma}
\]
is a $\PGammaL(k,q^n)$-equivalence class of linear sets of rank $n$ in $\PG(k-1,q^n)$.
\end{proposition}

\begin{proof}
Suppose $\C$ and $\C'$ are equivalent $\Fn$-subspaces of $V$. By Proposition \ref{prop:Fnequiv}, we have that $\C' = x^{q^m}\circ \C^{\rho}\circ h$ for some invertible $h$, some integer $m$, and some automorphism $\rho$ of $\F_{q^n}$. For any basis $f_1,\ldots,f_k$ of $\C$, it holds that $x^{q^m}\circ f_1^{\rho}\circ h,\ldots, x^{q^m}\circ f_k^{\rho}\circ h$ is a basis for $\C'$.

Thus
\[
\{((x^{q^m}\circ f_1^{\rho}\circ h)(x),\ldots,(x^{q^m}\circ f_k^{\rho}\circ h)(x))_{q^n}\vert x\in \mathbb{F}_{q^n}^*\} \in \L_{\C'}.
\]

 Defining $y=h(x)^{\rho^{-1}}$, gives
\[\{(f_1(y)^{q^m\rho},\ldots,f_k(y)^{q^m\rho})_{q^n}\vert y\in \mathbb{F}_{q^n}^*\} \in \L_{\C'}.\]

This is clearly $\PGammaL(k,q^n)$-equivalent to $L_{f_1,\ldots,f_k}\in \L_\C$.

\end{proof}
We will give a geometric reason for Proposition \ref{propeq2} in the next section.

\begin{remark}
Note that these results do not imply that if $\L_\C$ and $\L_{\C'}$ are $\PGammaL(k,q^n)$-equivalent then $\C$ and $\C'$ are equivalent; this is not always true. See Remark \ref{slechtequiv}, \ref{mis} and \cite{CsajZan}, \cite{CsajMarPol} for examples in the case $k=2$.
\end{remark}

\subsection{A geometric interpretation}
\label{clou}

In Subsection \ref{omegas}, we have, for a subspace $\C$ of $V$, defined a set of linear sets $\L_\C$. Starting from  the subspace $\C$ of $V$, we will now define a different linear set, as in \cite{Lunardon}. As explained in Subsection \ref{proj}, linear sets can be constructed as projected subgeometries. Using the subgeometry $\Sigma$ of $\PG(V)$, corresponding to the linear maps of rank one, and an $\Fn-$subspace $\C$ of $V$, then
\[
\Sigma/\Omega(\C) \subseteq \PG(n-k-1,q^n).
\]
defines a linear set $L'$ of rank $n$ in $\PG(n-k-1,q^n)$.

Note that in general $L'$ is not a linear set in $\L_\C$, as $\L_\C$ is a set of linear sets in $\PG(k-1,q^n)$ whereas $L'$ lies in $\PG(n-k-1,q^n)$. However we will now show that there is a geometric connection between the two constructions, our main result of this section.
\begin{theorem}
\label{thm:main}
Let $\C$ be an $\Fn$-subspace of $V$ with $\Omega(\C)^\perp\cap \Sigma=\emptyset$. Then for any $\Fn$-basis $\{ f_1,\ldots,f_k\}$ of $\C$ we have
$$U_{f_1,\ldots,f_k}\cong V_0/\C^\perp,$$
where $V_0$ is an $\Fq$-subspace of $V$ satisfying $\Omega(V_0) = \Sigma$, and
$$L_{f_1,\ldots,f_k}\cong \Sigma/\Omega(\C)^\perp.$$
Therefore
\[
\Sigma/\Omega(\C)^\perp \in \L_\C.
\]

\end{theorem}

\begin{proof}

Pick a $(k-1)$-space, say $\Omega(\C_1)=\la  g_1,\ldots,g_{k}\ra_{q^n}$ skew from $\Omega(\C)^\perp$. Then the quotient space $\Sigma/\Omega(\C)^\perp$ is isomorphic to the intersection of the space $\Omega(\C_1)$ with all spaces of the form $\la x,\Omega(\C)^\perp\ra$, where $x\in \Sigma$. We conclude that $\Sigma/\Omega(\C)^\perp$ is isomorphic to the set $M$ of points of the form $\la a_1 g_1+\cdots+a_{k}g_{k}\ra_{q^n}$, with $a_i \in \Fn$ such that $a_1 g_1+\cdots+a_{k}g_{k} = \bar{\beta}+t$ for some $\la\bar{\beta}\ra_{q^n}\in \Sigma,\la t\ra_{q^n}\in \Omega(\C)^\perp$.

Since $\la g_1\ra_{q^n},\ldots,\la g_k\ra_{q^n}$ are different points of $\PG(n-1,q^n)$, the set $M$ contained in $\Omega(\C_1)$ is clearly isomorphic to $M'$ corresponding to the points defined by the vectors from the set
\[
\left\{(a_1,\ldots,a_k):\sum_{i=1}^k a_i g_i =\bar{\beta}+t, \la\bar{\beta}\ra_{q^n}\in \Sigma,\la t\ra_{q^n}\in \Omega(\C)^\perp\right\}.
\]

Now suppose that
\begin{align}\sum_{i=1}^k a_i g_i=\bar{\beta}+t
\end{align}
for $a_i\in \F_{q^n}$ and $\la\bar{\beta}\ra_{q^n}\in \Sigma,\la t\ra_{q^n}\in \Omega(\C)^\perp$. Take the scalar product with $f_j$ on both sides of (1) to find
$$\sum_{i=1}^k a_i (f_j\cdot g_i)=f_j\cdot\bar{\beta}+f_j \cdot t$$
Now recall that $f_j\cdot \bar{\beta}=f_j(\beta)$, and that $f_j\cdot t=0$ since $\la t\ra_{q^n}\in \Omega(\C)^\perp$.
Hence we get that
$$\sum_{i=1}^k a_i (f_j\cdot g_i)=f_j(\beta)$$
for all $j$, which we rewrite as
$$\begin{pmatrix}a_1&\cdots&a_k\end{pmatrix}\phi=\begin{pmatrix}f_1(\beta)&\cdots&f_k(\beta)\end{pmatrix},$$

where $\phi$ is the $k\times k$ matrix with $\phi_{ij} = f_j\cdot g_i$.

We show that $\phi$ is non-singular.
Suppose that this matrix is singular. Then we can find a non-trivial linear combination of its columns that gives the zero row, i.e. we can find  some $\alpha_1,\ldots,\alpha_k \in \F_{q^n}$, not all zero, such that
\[
\sum_{i=1}^k \alpha_i (g_i\cdot f_j) =0
\]
for all $j$. Rearranging this, we find that $f_j \cdot (\sum_{i=1}^k \alpha_i g_i )=0$ for all $j$, implying $\sum_{i=1}^k \alpha_i g_i \in \Omega(\C)^\perp \cap \Omega(\C_1)$, a contradiction since $\Omega(\C)^\perp$ and $\Omega(\C_1)$ are disjoint. Hence $\phi$ is non-singular, as claimed.

Now applying $\phi^{-1}$ to $M'$, we get that $M'$ is isomorphic to the set of points defined by vectors in the set
\[
\{\begin{pmatrix}f_1(\beta)&\cdots&f_k(\beta)\end{pmatrix} : \beta \in \Fn^\ast\},
\]
which by definition is equal to $L_{f_1,\ldots,f_k}$.

We conclude that $\Sigma/\Omega(\C)^\perp\cong M\cong M'\cong L_{f_1,\ldots,f_k} $, as claimed. As we have only used $\PGL$-equivalences, using Proposition \ref{propeq}, we find that $\Sigma/\Omega(\C)^\perp\in \L_\C$.
\end{proof}

We can use this result to give a geometric proof of part of Proposition \ref{propeq2}.

\begin{proof}[Alternate proof of Proposition \ref{propeq2}] Let $\C_1$ and $\C_2$ be equivalent subspaces. Let $L_1=\Sigma/\Omega(\C_i)^\perp$.
By Theorem \ref{thm:main}, we have that $\Sigma/\Omega(\C_i)^\perp\in \L_{\C_i}$ for $i =1,2$. By Proposition \ref{prop:Fnequiv} $\C_1$ and $\C_2$, are equivalent if and only if they are semilinearly equivalent. It is straightforward to check that $\C_1$ and $\C_2$ are semilinearly equivalent if and only if $\C_1^\perp$ and $\C_2^\perp$ are semilinearly equivalent, in which case there is a collineation $\phi$ of $\PG(n-1,q^n)$ fixing $\Sigma$ and mapping $\Omega(\C_1)^\perp$ to $\Omega(\C_2)^\perp$.

Then clearly
\[
L_1^{\phi}= (\Sigma/\Omega(\C_1)^\perp)^\phi = \Sigma^\phi /(\Omega(\C_1)^\perp)^\phi = \Sigma/\Omega(\C_2)^\perp\in \L_{\C_2},
\]
as claimed. \end{proof}

\begin{remark}
We note again that the converse is not necessarily true. Counterexamples can occur when the cone defined by $\Omega(\C_1)$ and $\Sigma$ contains other subgeometries. Counterexamples are known only in the case $k=2$. However we do have the following generalisation of \cite[Theorem 8]{Sheekey}.

\end{remark}

\begin{proposition}\label{equi}

Suppose $\C_1,\C_2$ are $\Fn$-subspaces of $V\simeq \E$. Then $U_{\C_1}$ and $U_{\C_2}$ are $\GammaL(k,q^n)$-equivalent if and only if $\C_1$ and $\C_2$ are equivalent.

\end{proposition}

We conclude this section with a definition.

\begin{definition} The {\it companion} of the set $\U_\C$ of $n$-dimensional $\Fq$-subspaces of  $V(k,q^n)$ is the set $\U_{\C^\perp}$ of  $n$-dimensional $\Fq$-subspaces of  $V(n-k,q^n)$.
\end{definition}

\begin{remark}\label{mis} The corresponding statement for linear sets does not appear to be well-defined. If $\C$ and $\C'$ are inequivalent subspaces but define $\PGammaL$-equivalent linear sets, their duals do not necessarily define $\PGammaL$-equivalent linear sets.

Let $\C_1 = \pt{x,x^q}$ and $\C_2=\pt{x,x^{q^2}}$ be subspaces in $\PG(4,q^5)$, then $\C_1$ and $\C_2$ are inequivalent, but $L_{x,x^q}=L_{x,x^{q^2}}$, and hence, $L_{x,x^{q^2}} \in \L_{\C_1}$ (see \cite{CsajZan}). We have $\C_1^\perp = \pt{x^{q^2},x^{q^3},x^{q^4}}$ and $\C_2^\perp=\pt{x^{q},x^{q^3},x^{q^4}}$. It is not hard too check (e.g. using the GAP package FinInG \cite{fining}) that $L_{x^{q^2},x^{q^3},x^{q^4}}$ and $L_{x^{q},x^{q^3},x^{q^4}}$ are not $\PGammaL$-equivalent for $q=2,3,4$, and hence, $L_{x^{q},x^{q^3},x^{q^4}}\notin \L_{{\C_1}^\perp}$.

However, we will show in the next section that there is a correspondence between the weight distribution of points and hyperplanes in the linear sets in $\L_\C$ and $\L_{\C^\perp}$. So, even though one can take a linear set in $\L_{\C_1^\perp}$ and one in $\L_{\C_2^\perp}$ which are not equivalent, if $\C_1$ and $\C_2$ are equivalent, these will have the same weight distribution.

\end{remark}

\section{The extension of Sheekey's connection between scattered linear sets and MRD codes}\label{new}

Recall that if $\C\subset V$ is an $\F_{q^n}$-linear rank metric code, $\Omega(\C)$ is a subspace of $\PG(n-1,q^n)$. We now relate the rank distribution of the subspace $\Omega(\C)$ in $\PG(n-1,q^n)$ to properties of a linear set in $\L_\C$.

\begin{definition}
The {\it rank distribution} of a subset $\Omega(\C)$ is defined as the vector that has the number of points of $\Omega(\C)$ with rank $i$ on the $i$-th position, i.e.,
\[
rk(\Omega(\C)) := (v_1,\ldots,v_n),\ \mathrm{ with\ } v_i=\mathrm{ number\ of\ points\ of\ }\Omega(\C)\ \mathrm{ with\ rank\ }i.
\]
\end{definition}
\begin{definition}

The {\it weight distribution with respect to $s$-subspaces} of an $\Fq$-linear set $L(U)$ in $\PG(k-1,q^n)$ is defined as the vector
\[
w_s(L(U)) := (v_1,\ldots,v_n),\ \mathrm{ with\ } v_i=\mathrm{ number\ of\ } s-\mathrm{ spaces\ of\ }\PG(k-1,q^n)\ \mathrm{ with\ }wt_{L(U)}(\pi)=i.
\]

We call $w_0(L)$ the {\it weight distribution of $L(U)$}, and we call $w_{k-2}(L(U))$ the {\it weight distribution of $L$ with respect to hyperplanes}.
\end{definition}

We see that $L(U)$ is scattered if $w_0(L)$ has all its entries in $\{0,1\}$.

In \cite{Sheekey}, the following was shown (adapted to the notation of this paper).
\begin{theorem}
Let $\C$ be a two-dimensional $\Fn$-subspace of $V$ (or, equivalently, $\Omega(\C)$ a line in $\PG(n-1,q^n)$. Then a linear set $L\in L_\C$ is scattered if and only if $\C$ is disjoint from $\Sigma_{n-2}$, i.e. if and only if $\C$ is a two-dimensional $\Fn$-linear maximum rank-distance code.
\end{theorem}

We now aim to extend this correspondence to subspaces $\Omega(\C)$ of larger dimension. However it is not true in general to say that if a linear set $L\in L_\C$ is scattered, then $\C$ is maximum rank-distance, as we will illustrate in a later example. In order to characterise linear sets arising from $\Fn$-linear MRD codes, we introduce a new concept for linear sets; that of being {\it scattered with respect to hyperplanes}.

\begin{definition}
An $\F_q$-linear set $L(U)$ of rank $n$ in $\PG(k-1,q^n)$, with $\dim\la L(U)\ra =k-1$,
 is said to be {\it scattered with respect to hyperplanes} if the rank of $L(U)\cap H$ is at most $k-1$ for all hyperplanes $H$ of $\PG(k-1,q^n)$.
\end{definition}
 It is easy to see that an $\F_q$-linear set which is scattered with respect to hyperplanes is necessarily a scattered linear set. Moreover, for every linear set $L$ of rank $n$ in $\PG(k-1,q^n)$, it is easy to find some hyperplane meeting $L$ in a linear set of rank at least $k-1$. Hence, $k-1$ is the smallest possible upper bound for the rank of the intersection of a linear set of rank $n$ with a hyperplane of $\PG(k-1,q)$.

\begin{proposition}\label{weightrank}
Let $L_{f_1,\ldots,f_k} \in L_\C$ be a linear set in $\PG(k-1,q^n)$ defined by a subspace $\Omega(\C) = \langle f_1,\ldots,f_k\rangle_{q^n}\leq \PG(n-1,q^n)$ of dimension $k-1$. Then for any hyperplane $H = (a_1,\ldots,a_k)^{\perp}$, we have that
\[
wt_{L_{f_1,\ldots,f_k}}(H)  = n - \rank\left(\sum_{i=1}^k a_i f_i\right).
\]
\end{proposition}

\begin{proof}
Let $P = \langle(f_1(x_0),\ldots,f_k(x_0))\rangle_{q^n}$, with $x_0\neq 0 \in \Fn$ be a point of $L_{f_1,\ldots,f_k}$. Then $P\in H$ if and only if $a_1f_1(x_0)+\cdots+a_kf_k(x_0)=0$
, which occurs if and only if $x_0\in \ker(a_1f_1+\cdots a_kf_k)$. Hence $L_{f_1,\ldots,f_k}$ defines a linear set such that the weight of the hyperplane $H$ with respect to it is rank $\dim(\ker(a_1f_1+\cdots a_kf_k)) = n-\rank\left(\sum_{i=1}^k a_i f_i\right)$, as claimed.
\end{proof}

We get from the previous proposition that $w_{k-2}(L_{f_1,f_2,\ldots,f_k})=n.{\bf 1}-rk(\Omega(\C))$. As the right hand side is independent of the basis $f_1,\ldots,f_k$ we have chosen for $\C$, we find:

\begin{corollary}
The weight distribution of a linear set $L\in \L_\C$ with respect to hyperplanes is determined by the rank distribution of points in $\Omega(\C)$:
\[
w_{k-2}(L)= n.{\bf 1}-rk(\Omega(\C)),
\]
where $\bf{1}$ is the all-one vector.
\end{corollary}

We get from the previous corollary that the linear set $L$ is scattered with respect to hyperplanes if and only if all the points of $\Omega(\C)$ have rank at least $n-k+1$, which leads to the following statement. Note that when $k=2$, points are hyperplanes, and so setting $k=2$ returns the construction of the MRD codes of dimension 2 given in \cite[Section 5 ]{Sheekey}.

\begin{corollary}
A linear set $L\in \L_\C$ with $\dim \langle L\rangle=k-1$ is scattered with respect to hyperplanes if and only if $\Omega(\C)$ is disjoint from $\Sigma_{n-k}$ in $\PG(n-1,q^n)$, if and only if $\C$ is an $\Fn$-linear MRD code with minimum distance $n-k+1$.
\end{corollary}

\begin{remark}
An example for which a linear set $L(\C)$ is scattered, but not scattered with respect to hyperplanes, is the linear set
\[
L_1 = \{(x,x^q,\Tr(x))_{q^n}:x \in \Fn^\ast\}\subseteq \PG(2,q^n),
\]
where $n>3. $This is scattered, since
\[
(x,x^q,\Tr(x))_{q^n} = (y,y^q,\Tr(y))_{q^n} \Leftrightarrow x/y \in \Fq.
\]
However the line $(0,0,1)^\perp$ meets $L$ in the linear set
\[
 \{(x,x^q,0)_{q^n}:x \in \Fn^\ast, \Tr(x) = 0\},
\]
which is a linear set of rank $n-1>k-1=2$. The subspace $\Omega_1=\langle 1, x^q,\Tr\rangle_{q^n}$ is clearly not disjoint from $\Sigma_{n-3}$, since it contains the point $\langle \Tr\rangle_{q^n}\in \Sigma$.

We see that for $n\geq 4$, the scattered linear set (considered in \cite{BlLa2000})
\[
L_2 = \{(x,x^q,x^{q^2})_{q^n}:x \in \Fn^\ast\}\subseteq \PG(2,q^n),
\]
is both scattered and scattered with respect to hyperplanes, hence $L_2$ corresponds to an $\Fn$-linear MRD code of minimum distance $n-k+1=n-2$. In this case the corresponding MRD code is a Gabidulin code. The subspace $\Omega_2=\langle x,x^q,x^{q^2}\rangle_{q^n}$ is disjoint from $\Sigma_{n-3}$.

For $n=4$, the  linear set
\[
L_3 = \{(x,x^{q^2},\Tr(x))_{q^4}:x \in \F_{q^4}^\ast\}\subseteq \PG(2,q^4),
\]
is neither scattered nor scattered with respect to hyperplanes. Again, it is easy to see that $\Omega_3=\langle x,x^{q^2},\Tr(x)\rangle_{q^4}$ is not disjoint from $\Sigma{1}$ as it contains $\Tr$.

For $n=4$, every linear set of rank $4$ in $\PG(2,q^4)$ spanning $\PG(2,q^4)$ is equivalent to one these three examples $L_1,L_2,L_3$: this is because the dual of a plane in $\PG(3,q^4)$ is a point, and equivalence classes of points in $\PG(n-1,q^n)$ are precisely the sets $\Omega_i$. The three examples $L_1$, $L_2$, $L_3$ here arise from the duals of a point of rank $3$, $4$, and $2$ respectively.
\end{remark}

\section{MacWilliams identities for rank-metric codes and duality for weight distributions}\label{mac}\label{companion}
\subsection{MacWilliams identities}

We recall the result of Delsarte \cite{Delsarte} extending the classical MacWilliams identities for linear codes to rank metric codes. We state instead the following more convenient recursion from \cite{Ravagnani}. Though in this paper we require only the case $m=n$, we state the more general result.

\begin{theorem}\cite[Corollary 33]{Ravagnani}\label{ravagnani} Let $\C$ be an $\Fq$-linear subspace of $Mat(k\times m,\Fq)$.
Let $A_i$ denote the number of codewords of rank $i$ in $\C$ and let $B_i$ denote the number of codewords of rank $i$ in $\C^\perp$.
Put
$$a_{\nu}^k=\frac{q^{m\nu}}{|\C|}\sum_{i=0}^{k-\nu}A_i\left[\begin{array}{c}k-i\\ \nu\end{array}\right],$$
where the square brackets denote the Gaussian coefficient.

Then the $B_j$'s are given by the recursive formula

\begin{align*}
\begin{cases}
B_0&=1\\
B_\nu&=a_{\nu}^k-\sum_{j=0}^{\nu-1}B_j\left[\begin{array}{c}k-j\\ \nu-j\end{array}\right]\\
B_\nu&=0 \quad \mathrm{for}\ \nu>k.
\end{cases}
\end{align*}
\end{theorem}

This theorem tells us that the rank distribution of an $\Fq$-linear code $\C$ determines the rank distribution of the code $\C^\perp$. In Proposition \ref{weightrank}, we have seen that the rank distribution of a code determines the weight  distribution with respect to hyperplanes of the associated linear set. We obtain:

\begin{theorem} The weight distribution of the linear sets in $\L_\C$ determines the weight distribution of the linear sets in $\L_{\C^\perp}$.
\end{theorem}

 In the case that $\Omega(\C)$ is skew from $\Omega(\C)^\perp$, the linear sets $\Sigma/\Omega(\C)^\perp$ and $\Sigma/\Omega(\C)$ can be retrieved from one another:
$\Sigma/\Omega(\C)$ is obtained by projecting $\Sigma$ from $\Omega(\C)$ onto $\Omega(\C)^\perp$, whereas $\Sigma/\Omega(\C)^\perp$ is obtained by projecting $\Sigma$ from $\Omega(\C)^\perp$ onto $\Omega(\C)$. This shows the following:

\begin{corollary} Let $\C=\la f_1,f_2,\ldots,f_k\ra$. To switch between $L_{f_1,f_2,\ldots,f_k}\in \L_\C$ and  $L_{\la f_1,f_2,\ldots,f_k\ra_{q^n}^\perp}\in \L_{\C^\perp}$ in the case that $\Omega(\C)$ is skew from $\Omega(\C)^\perp$ just requires a switch between the subspace from which we are projecting and the subspace we are projecting onto.
\end{corollary}

\begin{remark}
If $n=4$ and $k=2$, then $L_{f_1,f_2}$ and $L_{{ \la f_1,f_2\ra_{q^n}}^\perp}$ are both equivalence classes of linear sets of rank $4$ in $\PG(1,q^4)$. Such linear sets have been classified in \cite{Polverino}.

Note that if $U$ is a four-dimensional $\Fq$-subspace of $V(2,q^4)$, given an $\Fq$-bilinear form on $V(2,q^4)$ we can define $U^\perp$, and hence can define the dual $L(U^\perp)$ of a linear set $L(U)$, as in \cite{olga}. However, if $U$ is such that  $L(U)\in L_\C$, it is not necessarily true that $L(U^\perp)\in L_{\C^\perp}$. Thus mapping $L_{f_1,f_2,\ldots,f_k}$ onto  $L_{\la  f_1,f_2, \ldots,f_k\ra^\perp}$  defines is a new operation {\sout{on equivalence classes}}, different from the dual operation.
\end{remark}

\subsection{An application for linear sets on a line}
If a linear set spans a line, then its weight distribution with respect to hyperplanes is determined by the weights of the points in the set. In this subsection, we will use this fact to deduce one of the MacWilliams identities in a geometric way.

Studying the weight distribution of linear sets on a line was partially motivated by a problem that arose during the study of KM arcs. It was shown in \cite{KMarcs} that translation KM-arcs of type $2^i$ in $\PG(2,2^h)$ are equivalent to $i$-clubs in $\PG(1,2^h)$. These $i$-clubs are $\F_2$-linear sets that have exactly one point of weight $i$ and all others of weight $1$. The existence of $i$-clubs in $\PG(1,2^h)$ is known only for a few parameter values. The case $i=2$ is of particular interest as it is known that there are (small) values of $h$ for which no $2$-clubs in $\PG(1,2^h)$ exist; this is a topic requiring further investigation. In Theorem \ref{wt2} we give an equivalent condition for the existence of linear sets with a fixed number $N$ of points of weight $2$ and all others of weight $1$.

\begin{definition}A {\em proper} linear set is a linear set which contains more than one point.
\end{definition}
\begin{proposition}\label{BW} Let $L$ be a proper linear set of rank $n$, $n\geq 3$,  in $\PG(1,q^n)$ that is obtained by projecting a subgeometry $\Omega=\PG(n-1,q)$ from a subspace $\Pi=\PG(n-3,q^n)$ contained in $\PG(n-1,q^n)$. Let $R_2$ be the number of points of rank $2$ in $\Pi$ and let $W_i$ be the number of points of weight $i$ in $L$, then
$$R_2=\sum_{i=2}^{n-1}W_i\left[\begin{array}{c}i\\2\end{array}\right].$$
\end{proposition}

\begin{proof}If a point $P$ of $L$ has weight $i$, then $\langle P, \Pi\rangle$ meets $\Omega$ in an $(i-1)$-space $\tau$ of $\Omega$ (see Proposition \ref{weightproj}). The extension of this space $\tau$ to a subspace of $\PG(n-1,q^n)$ is denoted by $\bar{\tau}$. Let $\ell$ be a line of $\tau$ and let $\bar{\ell}$ be its extension (which lies in $\bar{\tau}$), then $\bar{\ell}$ meets the hyperplane $\Pi$ of $\langle P,\Pi\rangle$ in a point $Q$.  Note that there are $\left[\begin{array}{c}i\\2\end{array}\right]$ lines in $\tau$.

This point $Q$ lies on an extended line of $\Omega$ and hence, has rank $2$. Now, suppose we have a different extended line $\bar{\ell'}$ that meets $\Pi$ in a point $Q'$. If $Q$ and $Q'$ would coincide, then $Q=Q'$ is the intersection point of $\bar{\ell}$ and $\bar{\ell'}$. But this implies that $\ell$ and $\ell'$ are contained in a plane, and hence, that the intersection point $Q$ is contained in $\Omega$. Since $Q$ is a point of $\Pi$, this in turn implies that $\Pi$ is not skew from $\Omega$, a contradiction. So we may conclude that all lines $\ell$ obtained in this fashion give rise to different points of rank $2$. As a point of weight $i$ gives rise to $\left[\begin{array}{c}i\\2\end{array}\right]$ points of rank $2$, we find in total
$\sum_{i=2}^{n-1}W_i\left[\begin{array}{c}i\\2\end{array}\right]$ points of rank $2$. Note that $W_n=0$ since the existence of a point of weight $n$ in $L$ would imply that $L$ equals that point, a contradiction since $L$ is a proper linear set.

\end{proof}
\begin{corollary}\label{wt1-2}Let $L$ be a proper linear set of rank $n$, $n\geq 3$,  in $\PG(1,q^n)$ that is obtained by projecting a subgeometry $\Omega=\PG(n-1,q)$ from a subspace $\Pi=\PG(n-3,q^n)$ contained in $\PG(n-1,q^n)$.
If $L$ has only points of weight $1$ and $2$, the number of points of weight $2$ in $L$ is the number of points of rank $2$ in $\Pi$.
\end{corollary}

We can use Corollary \ref{wt1-2} to obtain the following geometric construction for linear sets having all but a few points of weight $1$ on a line.
\begin{theorem}\label{wt2}
There exists a linear set of rank $n$ in $\PG(1,q^n)$ containing $N$ points of weight $2$ and all other points of weight at most $1$ if and only if there exists a subspace of co-dimension two in $\PG(n-1,q^n)$ disjoint from $\Sigma$ and meeting $\Sigma_2$ in precisely $N$ points.
\end{theorem}
Unfortunately, it does not appear to be easy to determine the possibilities for the intersection of a subspace with $\Sigma_2$. However, this does provide an alternative approach which may be of benefit, as $\Sigma_2$ is a more convenient variety to work with than $\Sigma_{n-2}$.

\subsection{Using MacWilliams identities to prove Proposition \ref{BW}}

\begin{lemma} Let $\C=\la f_1,f_2\ra$ such that $L\in \L_\C$ is a proper linear set of rank $n$ in $\PG(1,q^n)$, and let $A_i$ denote the number of vectors of rank $i$ in $\C$, then we have that $$\sum_{i=1}^{n-1}A_i\left[\begin{array}{c}n-i\\ 1\end{array}\right]=(q^n-1)\left[\begin{array}{c}n\\ 1\end{array}\right].$$
\end{lemma}

\begin{proof}

Consider the representation of $L$ as the set of elements of a Desarguesian spread meeting an $(n-1)$-dimensional projective space $\pi$. The elements of $\D$ intersecting $\pi$ correspond to the points of $L$. More precisely, we have that a point of $L$ has weight $i$ if and only if the corresponding spread element meets $\pi$ in an $(i-1)$-dimension projective space. The $(i-1)$-spaces corresponding to the points of $L$ form a partition of $\pi$, so we have
$$\sum_{i=1}^{n}W_i\left[\begin{array}{c}i\\ 1\end{array}\right]=\left[\begin{array}{c}n\\ 1\end{array}\right],$$
where $W_i$ is the number of points of weight $i$ in $L$.
First note that $W_n=0$ since $L$ is proper. Secondly, we have seen that a point of weight $i$ in $L$ corresponds to a point of rank $n-i$ in $\Omega(\C)$.
So the number of points with weight $W_i$ is the number of points of rank $n-i$ in $\Omega(\C)$. This number in turns equals $\frac{A_{n-i}}{q^n-1}$ as every point gives rise to $(q^n-1)$ vectors in $\C$. So we obtain that
$$\sum_{i=1}^{n-1}\frac{A_{n-i}}{q^n-1}\left[\begin{array}{c}i\\ 1\end{array}\right]=\left[\begin{array}{c}n\\ 1\end{array}\right],$$ or equivalently
 $$\sum_{i=1}^{n-1}A_i\left[\begin{array}{c}n-i\\ 1\end{array}\right]=(q^n-1)\left[\begin{array}{c}n\\ 1\end{array}\right].$$
\end{proof}

\begin{corollary} \label{An-1}$A_{n-1}=\frac{(q^n-1)^2}{q-1}-\sum_{i=0}^{n-2}A_i\left[\begin{array}{c}n-i\\ 1\end{array}\right]+\left[\begin{array}{c}n\\ 1\end{array}\right]$
\end{corollary}

\begin{lemma} Let $A_i$ be the number of vectors of rank $i$ in $\C=\la f_1,f_2\ra$ and let $B_i$ denote the number of vectors of rank $i$ in $\C^\perp$. Then $B_1$=0.
\end{lemma}
\begin{proof} We use Ravagnani's formulae from Theorem \ref{ravagnani} with $k=m=n$, $|\C|=q^{2n}$ and $\nu=1$. We find
$$B_1=\frac{q^n}{q^{2n}}\left(\sum_{i=0}^{n-1}A_i\left[\begin{array}{c}n-i\\ 1\end{array}\right]\right)-B_0\left[\begin{array}{c}n\\ 1\end{array}\right],$$or
$$B_1=\frac{1}{q^{n}}\left(\sum_{i=0}^{n-3}A_i\left[\begin{array}{c}n-i\\ 1\end{array}\right]\right)+\frac{1}{q^{n}}A_{n-2}\left[\begin{array}{c}2\\ 1\end{array}\right]+\frac{1}{q^{n}}A_{n-1}\left[\begin{array}{c}1\\ 1\end{array}\right]-\left[\begin{array}{c}n\\ 1\end{array}\right].$$

We sustitute $A_{n-1}$ for its value found in Corollary \ref{An-1}, that is

$$A_{n-1}=\frac{(q^n-1)^2}{q-1}-\sum_{i=0}^{n-3}A_i\left[\begin{array}{c}n-i\\ 1\end{array}\right]-A_{n-2}\left[\begin{array}{c}2\\ 1\end{array}\right]+\left[\begin{array}{c}n\\ 1\end{array}\right].$$

Plugging this in the equation for $B_1$, we find that $B_1=0$.

\end{proof}

Now we will only use Theorem \ref{ravagnani} to prove:
\begin{lemma} \label{la}If $A_i$ is the rank distribution of $\C=\la f_1,f_2\ra$, then $$B_2=\sum_{i=1}^{n-2}A_i\left[\begin{array}{c}n-i\\ 2\end{array}\right].$$
\end{lemma}
\begin{proof}
We have that $B_2=a_2^n-B_0\left[\begin{array}{c}n\\ 2\end{array}\right]-B_1\left[\begin{array}{c}n-1\\ 1\end{array}\right]$. Now we have seen that $B_1=0$ in the previous lemma.
Further, we have that $a_2^n=\sum_{i=0}^{n-2}A_i\left[\begin{array}{c}n-i\\ 2\end{array}\right], $ so
$$B_2=\sum_{i=0}^{n-2}A_i\left[\begin{array}{c}n-i\\ 2\end{array}\right]-\left[\begin{array}{c}n\\ 2\end{array}\right]=\sum_{i=1}^{n-2}A_i\left[\begin{array}{c}n-i\\ 2\end{array}\right].$$
\end{proof}

\begin{remark}
We have seen in Proposition \ref{BW} that $$R_2=\sum_{i=2}^{k-1}W_i\left[\begin{array}{c}i\\2\end{array}\right].$$ To retrieve this result, put $R_2=A_2/(q^n-1)$, $W_i=A_{n-i}/(q^n-1)$ and $k=n$ in Lemma \ref{la}.

\end{remark}

\begin{remark} The ideas developed in this section can be used to explicitely compute the weight distributions of the companions of linear sets with prescribed weight distributions. For example, if $L_{f_1,f_2}$ is a linear set of rank $5$ in $\PG(1,q^5)$ that has 1 point of weight $2$ and all others of weight $1$, then the rank distribution of $\la f_1,f_2\ra$ is as follows:

\begin{align*}
A_0&=1\\
A_1&=0\\
A_2&=0\\
A_3&=q^5-1\\
A_4&=(q^5-1)\frac{q^n-q^2}{q-1}\\
A_5&=(q^5-1)\left(q^n-\frac{q^n-q^2}{q-1}\right)
\end{align*}
and we have that the rank distribution of $\Omega(\C)$ is given by the vector $$rk(\Omega(\C))=\left(0,0,1,\frac{q^n-q^2}{q-1},\left(q^n-\frac{q^n-q^2}{q-1}\right)\right).$$ This says that on the line $\la f_1,f_2\ran$, there is one point of rank $3$, $\frac{q^n-q^2}{q-1}$ points of rank $4$ and the remaining $q^n-\frac{q^n-q^2}{q-1}$ ones are of rank $5$.

Applying Theorem \ref{ravagnani} gives us
\begin{align*}
B_0&=1\\
B_1&= 0\\
B_2&=q^5-1\\
B_3&=(q^5-1)(q^6 + q^5 + 2q^4 + 2q^3 + q^2)\\
B_4&=(q^5-1)(q^9 + q^8 - q^6 - 2q^5
    - 3q^4 - 2q^3 - q^2)\\
B_5&=(q^5-1) ( q^{10} - q^9 - q^8 + 2q^5 + q^4).
\end{align*}
and we have that the rank distribution of $\Omega(\C^\bot)$ is given by the vector $$rk(\Omega(\C^\bot))=(0,
1,
q^6 + q^5 + 2q^4 + 2q^3 + q^2,
q^9 + q^8 - q^6 - 2q^5
    - 3q^4 - 2q^3 - q^2,
 q^{10} - q^9 - q^8 + 2q^5 + q^4).$$
We conclude that  $L_{h_1,h_2,h_3}$ with $\la h_1,h_2,h_3\ran=\la f_1,f_2\ran^\bot$ is a linear set in $\PG(2,q^5)$ with the following weight distribution with respect to hyperplanes; i.e., lines:
$$w_{L_{h_1,h_2,h_3}}=( q^{10} - q^9 - q^8 + 2q^5 + q^4,q^9 + q^8 - q^6 - 2q^5
    - 3q^4 - 2q^3 - q^2,q^6 + q^5 + 2q^4 + 2q^3 + q^2,1,0).$$
We find a unique line that has weight $3$ with respect to $L_{h_1,h_2,h_3}$ while all other lines have weight $1$ or $2$ with respect to $L_{h_1,h_2,h_3}$.

\end{remark}

config: arxiv


TITLE: Convergence/Divergence speed of $u_n = \int_0^1 f(x)^n g(x) \textrm{d}x$ given $f, g$ continuous and non-negative
QUESTION [3 upvotes]: Let be $f, g : [0, 1] \to \mathbb{R}_{+}^{*}$ continuous maps such that:
$\forall n \in \mathbb{N}, u_n = \int_0^1 f(x)^n g(x) \textrm{d}x$
I want to show that $v = \left(\dfrac{u_{n + 1}}{u_n}\right)_n$ converges to a finite limit.
What I have done so far, is:
By the second mean value theorem, I have $(c_n)_n \in ]0, 1[^{\mathbb{N}}$ such that:
\begin{equation*}
u_n = f(c_n)^n \int_0^1 g(x) \textrm{dx} = f(c_n)^n u_0
\end{equation*}
Then:
\begin{align*}
\dfrac{u_{n + 1}}{u_n} & = f(c_{n + 1}) \left(\dfrac{f(c_{n + 1})}{f(c_n)}\right)^n
\end{align*}
Now, I'm stuck, because I wish I could know something better on $(c_n)_n$, but all I know is, by Weierstrass: $(c_n)_n$ has at least one accumulation point $c_0$ such that, I know that $v$ has at least one accumulation point, that is: $f(c_0)$.
So, basically, I have to show that the only limit of $v$ is $f(c_0)$ and that will conclude, I have no idea on how to proceed. If I try to consider proof by contradiction, knowing that I have another accumulation point $c_1$ will not help me.
Bonus: I wonder if we can get an asymptotic relation of $(u_n)_n$ like: $u_n \sim f(c_0)^n M$.

REPLY [2 votes]: Note that $$\frac{u_{n+1}}{u_{n}}=\frac{\int_{0}^{1}f\left(x\right)^{n+1}g\left(x\right)dx}{\int_{0}^{1}f\left(x\right)^{n}g\left(x\right)dx}=f\left(\xi_{n}\right)\frac{\int_{0}^{1}f\left(x\right)^{n}g\left(x\right)dx}{\int_{0}^{1}f\left(x\right)^{n}g\left(x\right)dx}=f\left(\xi_{n}\right)\leq M,\,\xi_{n}\in\left(0,1\right)$$ by the mean value theorem and the extreme value theorem, so the sequence $\frac{u_{n+1}}{u_{n}}$ is bounded. Furthermore, by the Cauchy inequality, we have $$\left(\int_{0}^{1}f\left(x\right)^{n+1}g\left(x\right)dx\right)^{2}=\left(\int_{0}^{1}f\left(x\right)^{n/2+1}g\left(x\right)^{1/2}f\left(x\right)^{n/2}g\left(x\right)^{1/2}dx\right)^{2}$$ $$\leq\left(\int_{0}^{1}f\left(x\right)^{n+2}g\left(x\right)dx\right)\left(\int_{0}^{1}f\left(x\right)^{n}g\left(x\right)dx\right)$$ hence $$\frac{u_{n+1}}{u_{n}}\leq\frac{u_{n+2}}{u_{n+1}}$$ and so the sequence is monotone non-decreasing. This allow to conclude that it has a finite limit, by the monotone convergence theorem.


TITLE: The first cohomology of group
QUESTION [4 upvotes]: I would like to ask if G is a group of order $p^4 (p\neq 2)$ as form $C_{p^3}\rtimes C_p$ (a semidirect product of cyclic group of order $p^3$ by a group of order $p$). Then can we obtain the first co-homology $H^1(C_p,C_{p^3} )$?
Is there any upper bound on the order of $H^1(C_p, C_{p^3})$?
yours,

REPLY [1 votes]: There must be a mistake in your notation. Cohomology groups $H^r$(G, A) are defined only for a group G and a G-module A, i.e. an abelian group A on which G acts. If A is not abelian, one can still define $H^1$(G, A) in certain cases,  but it is just a set (see Serre's "Galois Cohomology", chapter 3).
If your $H^1$ notation means that the semi-direct product acts trivially on $C_p$ , then the inflation-restriction exact sequence (= beginning of the Hochschild-Serre spectral sequence) should do the job.


TITLE: Is it true that if a divides bc, then there exist prime factors of a that divide both b and c
QUESTION [1 upvotes]: As per title really.
Is there a theorem (or similar) that states that given three positive integers a, b, c, if a | bc, then there exist prime factors p1, p2 of a such that p1 | b and p2 | c?
The specific case where I've come across this is Shor's algorithm, where a divides (x + 1)(x - 1).

REPLY [2 votes]: No.
If $a=15$ and $b=165$ and $c=91$ then $a \mid bc$ since $\frac{165\times 91}{15}=1001$ but there is no prime factor $p_2$ of $a$ such that $p_2 \mid c$
It becomes true if the highest common factors (greatest common divisors if you prefer) of $a$ and $b$ and of $a$ and $c$ are both greater than $1$.  Here $p_1$ and $p_2$ may be the same prime factor of $a$, for example if $a$ is prime.


TITLE: Prove $f:[0,2] \to \mathbb{R}$ is a continous function where $f(x) = \sqrt{x}$
QUESTION [1 upvotes]: Prove $f:[0,2] \to \mathbb{R}$ is a continuous function where $f(x) = \sqrt{x)}$ using a $\delta - \epsilon$ proof
Letting $a \in [0,2]$ and $\delta_0 = \frac{a}{2}$ gives $|x| \le \frac{3a}{2}$ and $\mid \sqrt{x} - \sqrt {a} \mid \le \mid \sqrt{x} - \sqrt {a} \mid \cdot\mid \sqrt{x} + \sqrt {a} \mid \le \delta_0\cdot 2\sqrt{2}\le \epsilon$ if $\delta < \frac{\epsilon}{2\sqrt{2}}$
Let $\epsilon > 0$ and find $\delta = \text{min}\{\delta_0, \frac{e}{2\sqrt{2}} \}$
Seems pretty straight forward but not sure I am correctly doing this. I wasn't sure what to use as the second possible choice for $\delta$ its been much more clear in other proofs I've done.

REPLY [1 votes]: If $2\geq a > 0, |\sqrt{x}-\sqrt{a}| = \dfrac{|x-a|}{\sqrt{x}+\sqrt{a}}\leq \dfrac{|x-a|}{\sqrt{a}}<\dfrac{\delta}{\sqrt{a}}< \epsilon\iff \delta < \epsilon\cdot \sqrt{a}$. Thus this suggests that you choose $\delta = \dfrac{\epsilon\cdot \sqrt{a}}{2}$ will work.
If $a = 0, |\sqrt{x}-\sqrt{0}|= \sqrt{|x-0|}<\sqrt{\delta}<\epsilon\iff \delta < \epsilon^2$. Thus you can choose $\delta = \dfrac{\epsilon^2}{2}$ will work.


TITLE: Does every nonzero Turing degree adimit a nonzero incompatible degree?
QUESTION [1 upvotes]: It is well known that every nonzero Turing degree $\bf x$ adimits an incomparable degree $\bf y$, that is a degree such that $\bf x\not\le_T\bf y$ and $\bf y\not\le_T\bf x$.
I was wondering whether this statement generalizes to the stronger following one: every nonzero Turing degree $\bf x$ adimits a nonzero degree $\bf y$ which is incompatible with it, meaning that the set $\{\bf x,\bf y\}$ has no nonzero lower bounds.
In case this statement were known to be false, is it known exactly what degrees provide counterexamples to it?

REPLY [2 votes]: Yes, every degree has this property. Specifically, for every Turing degree d there is a minimal Turing degree a not below d (in particular, any sufficiently-Sacks-generic real will have this property, with "sufficiently" depending on d).
Alternatively, we can do a single forcing and produce a perfect set of Turing incomparable minimal degrees; since any Turing degree only computes countably many things, this immediately implies that for every degree d there is a minimal a not below d.
It's worth keeping in mind that the minimal degrees display far more variety and structure than one might guess. In particular, "minimal" does not really mean "small" - for example, for any d$\ge_T0'$  there is some minimal a such that a$'=$ d. (This is due to Cooper.) Similarly, for any degrees d, x there is some minimal a such that a $\vee$ d $=$ x (and this strengthens the affirmative answer to your question given above).
And I can't end without mentioning an interesting open questions about the minimal degrees (I believe each due to Yates). Say that a is a strong minimal cover of d if a $\ge_T$ d and every degree $<_T$ a is $\le_T$ d. (By contrast, a minimal cover simply satisfies $($d, a$)=\emptyset$.) Yates asked - and I believe this is still completely open - whether every minimal Turing degree has a strongly minimal cover. It is known meanwhile that every sufficiently large Turing degree has a strongly minimal cover, and that there are Turing degrees without strongly minimal covers, so really either answer is plausible.


text:
\section{Introduction}
\label{sec:intro}
Over the last decade, a new \emph{linear} approach for obtaining a succinct
representation of $n$-dimensional vectors (or signals) has emerged.
For any signal $x$, the representation is given by $Ax$, where $A$ is an $m \times n$ matrix, or possibly a random variable chosen from a suitable distribution over such matrices.
The vector $Ax$ is referred to as the {\em measurement vector} or \emph{linear sketch} of $x$.
Although $m$ is usually chosen to be much smaller than $n$, the measurement vector $Ax$ often contains plenty of useful information about the signal $x$.

A particularly useful and well-studied problem in this context is that of \emph{robust sparse recovery}.
A vector $x$ is $k$-sparse if it has at most $k$ non-zero coordinates.
The robust sparse recovery problem is typically defined as follows:
given the measurement vector $y=Ax+e$, where $x$ is a $k$-sparse vector and  $e$ is the ``noise'' vector

, find a signal estimate $\xhat$ such that:
\begin{equation}
\label{e:lplq}
\norm{x-\xhat}_2 \; \le \; C \cdot \norm{e}_2 \; .
\end{equation}
Sparse recovery has a tremendous number of applications in areas such as compressive sensing of signals~\cite{cs_incomplete_frequency,cs_donoho}, genetic data analysis~\cite{poolmc}, and data stream algorithms~\cite{M05,cs_sparse_matrices_survey}.

It is known that there exist matrices $A$ and associated recovery algorithms that produce a signal estimate $\xhat$ satisfying Equation~\eqref{e:lplq} with a constant approximation factor $C$ and number of measurements $m=O(k \log (n/k))$.
It is also known that this bound on the number of measurements $m$ is asymptotically \emph{optimal} for some constant $C$; see~\cite{DIPW10} and~\cite{FPRU10} (building upon the classical results of~\cite{K77,GG84,G84}).
The necessity of the ``extra'' logarithmic factor multiplying $k$ is rather unfortunate: the quantity $m$ determines the ``compression rate'', and for large $n$ any logarithmic factor in $m$ can worsen this rate tenfold.

On the other hand, more careful signal \emph{modeling} offers a way to overcome the aforementioned limitation.
Indeed, decades of research in signal processing have shown that not all signal supports (i.e., sets of non-zero coordinates) are equally common in practice.
For example, in the case of certain time-domain signals such as signals transmitted by push-to-talk radios, the dominant coefficients of the signal tend to cluster together in contiguous ``bursts''.
A formal approach to capture this additional \emph{structure} is to assume that the support of the vector $x$ belongs to a given family of supports $\Msupports$, a so-called ``model'' (we say that $x$ is  $\Msupports$-{sparse}).
Note that the original $k$-sparse recovery problem corresponds to the particular case when the model $\Msupports$ is the family of all $k$-subsets of $[n]$.

This modeling approach has several interesting ramifications, particularly in the context of robust sparse recovery.
Recently, Baraniuk et al.\ provided a general framework called \emph{model-based compressive sensing} \cite{modelcs}.
For any ``computationally tractable'' and ``small'' family of supports, the scheme proposed in their work guarantees robust signal recovery with a nearly-optimal number of measurements $m=O(k)$, i.e.,  \emph{without any logarithmic dependence on $n$.}
Several other works have achieved similar performance gains both in theory and in practice; see, for example,~\cite{EldarUSS,DE11,rao2012universal,BJMO12a,Wain14}.

While the model-based compressive sensing framework is general, it relies on two model-specific assumptions:
\begin{enumerate}[label={(\arabic*)}]
\item\emph{Model-based Restricted Isometry Property (RIP)}: The matrix $A$ approximately preserves the $\ell_2$-norm of all $\Msupports$-sparse vectors.
\item\emph{Model projection oracle}: There exists an efficient algorithm that solves the {\em model-projection problem}: given an arbitrary vector $x$, the algorithm finds the $\Msupports$-sparse vector $x'$ that is closest to $x$, i.e., minimizes the $\ell_2$-norm of the ``tail'' error $\|x-x'\|_2$.
\end{enumerate}
By constructing matrices satisfying (1) and algorithms satisfying (2), researchers have developed robust signal recovery schemes for a wide variety of signal models, including block-sparsity~\cite{modelcs}, tree-sparsity~\cite{modelcs}, clustered sparsity~\cite{ModelCSSAMPTA}, and separated spikes~\cite{spikes}, to name a few.

Unfortunately, extending the model-based compressive sensing framework to more general models faces a significant obstacle.
For the framework to apply, the model projection oracle has to be \emph{exact} (i.e., the oracle finds the signal in the model with exactly minimal tail error).
This fact may appear surprising, but in Section~\ref{sec:counterexample} we provide a \emph{negative result} and prove that existing model-based recovery approaches fail to achieve the robust sparse recovery criterion \eqref{e:lplq} if the model projection oracle is not exact.
Consequently, this burden of ``exactness'' excludes several useful design paradigms employed in {\em approximation algorithms}, i.e., algorithms which find a signal in the model that only approximately minimizes the tail error.
A rich and extensive literature on approximation algorithms has emerged over the last 15 years, encompassing a variety of techniques such as greedy optimization, linear programming (LP) rounding, semidefinite programming (SDP) rounding, and Lagrangian relaxation. To the best of our knowledge, existing approaches for the model projection problem have largely focused on exact optimization techniques (e.g. dynamic programming~\cite{modelcs,CT13,ModelCSSAMPTA}, solving LPs without an integrality gap~\cite{spikes}, etc.).

\subsection{Summary of Our Results}

In this paper, we introduce a new framework that we call \emph{approximation-tolerant model-based compressive sensing}.
This framework includes a range of algorithms for sparse recovery that require only \emph{approximate solutions} for the model-projection problem. In essence, our work removes the aforementioned obstacle to model-based compressive sensing and therefore extends the framework to a much wider class of models.
Simultaneously, our framework provides a principled approach to leverage the wealth of approximation algorithms for recovering structured sparse signals from linear measurements.

Instead of requiring one exact model projection oracle, our algorithms assume the existence of \emph{two} oracles with complementary approximation guarantees: (i) Given $x \in \R^n$, a \emph{tail approximation} oracle returns a support $\Omega_t$ in the model such that the norm of the tail $\norm{x-x_{\Omega_t}}_2$ is approximately minimized. (ii) A \emph{head approximation} oracle  returns a support $\Omega_h$ in the model such that the norm of the head $\norm{x_{\Omega_h}}_2$ is approximately maximized.
Formally, we have:
\begin{align}
\norm{x - x_{\Omega_t}}_2 \; &\leq \; c_T \cdot \min_{\Omega \in \Msupports} \norm{x - x_\Omega}_2 \qquad\textrm{and} \label{eq:tail} \\
\norm{x_{\Omega_h}}_2 \; &\geq \; c_H \cdot \min_{\Omega \in \Msupports} \norm{x_\Omega}_2 \label{eq:head}
\end{align}
for some positive constants $c_H \leq 1$ and $c_T \geq 1$. Given access to these approximation oracles, we prove the following main result.

\begin{theorem}[Signal recovery]
\label{thm:mainresult}
Consider a structured sparsity model $\Mmodel \subseteq \reals^n$ and norm parameter $p \in \{1,2\}$.
Suppose that $x \in \Mmodel$ and that we observe $m$ noisy linear measurements $y = Ax + e$.
Suppose further that $A$ satisfies the model-RIP in terms of the $\ell_p$-norm, and that we are given access to head- and tail-approximation oracles $H(\cdot)$ and $T(\cdot)$ satisfying \eqref{eq:tail} and \eqref{eq:head}, respectively. Then there exists an efficient algorithm that outputs a signal estimate $\xhat$ such that $\norm{x - \xhat}_p \leq C \norm{e}_p $ for some constant $C > 0$.
\end{theorem}

We analyze the two cases $p=1$ and $p=2$ separately and develop two different types of recovery algorithms.
The case of $p=2$ is perhaps more well-studied in the literature and corresponds to the ``standard'' notion of the RIP.
In this case, our recovery algorithms are extensions of IHT, CoSaMP, and their model-based counterparts \cite{cosamp,iht,modelcs}.
The case of $p=1$ has received attention in recent years and is applicable to the situation where the measurement matrix $A$ is \emph{itself} sparse.
In this case, our recovery algorithms are extensions of those developed in~\cite{BGIK09,RF13,BBC14}.
For both types of algorithms, the sequence of signal estimates $(x_k)$ produced by our algorithms exhibits \emph{geometric convergence} to the true signal $x$, i.e., the norm of the error $\norm{x_k-x}_p$ decreases by at least a constant factor in every iteration.
The rate of convergence depends on the approximation constants $c_T$ and $c_H$, as well as the RIP constants of the matrix $A$.

As a case study, we instantiate both the $p=1$ and $p=2$ cases in the context of the {\em Constrained Earth Mover's Distance} (CEMD) model introduced in~\cite{HIS}.
In this model, the signal coefficients form an $h \times w$ grid and the support of each column has size at most $s$, for  $n=h \cdot w$ and $k=s \cdot w$.
For each pair of consecutive columns, say $c$ and $c'$, we define the Earth Mover's Distance (EMD) between them to be the minimum cost of matching the support sets of $c$ and $c'$ when viewed as point sets on a line.
A signal support is said to belong to the CEMD model with ``budget'' $B$ if the sum of all EMD distances between the consecutive columns is at most $B$.
See Section~\ref{s:emd} for a formal definition.
Our framework leads to the first \emph{nearly sample-optimal} recovery scheme for signals belonging to this model.
The result is obtained by designing a novel head-approximation algorithm and proving approximation guarantees for the tail-approximation algorithm that was first described in~\cite{HIS}.

\subsection{Paper Outline}

This paper includes the following contributions, organized by section.
Before our contributions, we briefly review some background in Section \ref{sec:prelims}.

\paragraph{A negative result for approximation oracles.}
In Section~\ref{sec:counterexample}, we begin with the following negative result:
combining an apprixmate model-projection oracle with the existing model-based compressive sensing approach of Baraniuk et al.\ \cite{modelcs} \emph{does not suffice} to guarantee robust signal recovery for even the most trivial model.
This serves as the motivation for a more sophisticated approach, which we develop throughout the rest of the paper.

\paragraph{Approximate model-iterative hard threholding (AM-IHT).}
In Section~\ref{sec:amiht}, we propose a new extension of the iterative hard thresholding (IHT) algorithm~\cite{iht}, which we call \emph{approximate model iterative hard thresholding} (or AM-IHT).
Informally, given head- and tail-approximation oracles and measurements $y = Ax + e$ with a matrix $A$ satisfying the model-RIP, AM-IHT returns a signal estimate $\widehat{x}$ satisfying \eqref{e:lplq}.
We show that AM-IHT exhibits {geometric convergence}, and that the recovery guarantee for AM-IHT is asymptotically equivalent to the best available guarantees for model-based sparse recovery, despite using only approximate oracles.

\paragraph{Approximate model-CoSaMP (AM-CoSaMP).}
In Section~\ref{sec:amcosamp}, we propose a new extension of the compressive sampling matching pursuit algorithm (CoSaMP)~\cite{cosamp}, which we call {\em approximate model CoSaMP} (or AM-CoSAMP).
As with AM-IHT, our proposed AM-CoSaMP algorithm requires a head-approximation oracle and a tail-approximation oracle.
We show that AM-CoSaMP also exhibits geometric convergence, and that the recovery guarantee for AM-CoSaMP, as well as the RIP condition on $A$ required for successful signal recovery, match the corresponding parameters for AM-IHT up to constant factors.

\paragraph{AM-IHT with sparse measurement matrices.}
In Section~\ref{sec:modelrip1}, we show that an approximation-tolerant approach similar to AM-IHT succeeds even when the measurement matrix $A$ is {\em itself} sparse.
Our approach leverages the notion of the restricted isometry property in the $\ell_1$-norm, also called the {\em RIP-1}, which was first introduced in~\cite{BGIK09} and developed further in the model-based context by~\cite{IR13,RF13,BBC14}.
For sparse $A$, we propose a modification of AM-IHT, which we call \emph{AM-IHT with RIP-1}.
Our proposed algorithm also exhibits geometric convergence under the {\em model RIP-1} assumption on the measurement matrix $A$.

\paragraph{Compressive sensing with the CEMD Model.}
We design both head- and tail-approximation algorithms for the CEMD model:
(i) Our tail-approximation oracle returns a support set with tail-approximation error at most a constant times larger than the optimal tail error.
At the same time, the EMD-budget of the solution is still $O(B)$ (Theorem~\ref{thm:tailapprox}).
(ii) Our head-approximation oracle returns a support set with head value at least a constant fraction of the optimal head value.
Moreover, the EMD-budget of the solution is $O(B \log \frac{k}{w})$ (Theorem~\ref{thm:headapproxbasic}).
Combining these algorithms into our new framework, we obtain a compressive sensing scheme for the CEMD model using $O(k \log(\frac{B}{k} \log(\frac{k}{w})))$ measurements for robust signal recovery.
For a reasonable choice of parameters, e.g., $B = O(k)$, the bound specializes to $m = O(k \log \log(\frac{k}{w}))$, which is very close to the information-theoretic optimum of $m = O(k)$.

\subsection{Prior Work}
Prior to this paper, several efforts have been made to enable compressive sensing recovery for structured sparse signals with approximate projection oracles.
The paper~\cite{Blum11} discusses a Projected Landweber-type method that succeeds even when the projection oracle is approximate.
However, the author assumes that the projection oracle provides an {\em $\epsilon$-additive} tail approximation guarantee.
In other words, for any given $x \in \R^n$, the model-approximation oracle returns a $\widehat{x} \in \Mmodel$ satisfying:
\begin{equation}
\norm{ x - \widehat{x}}_2 = \min_{x' \in \Mmodel} \norm{x - x'}_2 + \eps
\label{eq:addapprox}
\end{equation}
for some parameter $\eps > 0$.
Under such conditions, there exists an algorithm that returns a signal within an
$O(\epsilon)$-neighborhood of the optimal solution.
However, approximation oracles that achieve low additive approximation guarantees satisfying \eqref{eq:addapprox} are rather rare.

On the other hand, the works~\cite{KC,clash} assume the existence of a head-approximation oracle similar to our definition \eqref{eq:head} and develop corresponding signal recovery algorithms. However, these approaches only provide signal recovery guarantees with an additive error term of $O(\|x_{\Omega}\|)$, where $\Omega$ is the set of the $k$ largest coefficients in $x$. Therefore, this result is not directly comparable to our desired recovery guarantee~\eqref{e:lplq}.

Some more recent works have introduced the use of approximate projection oracles, albeit for a different type of signal model.
There, the underlying assumption is that the signals of interest are sparse in a \emph{redundant dictionary}.
The paper~\cite{GE} presents a sparse recovery algorithm for redundant dictionaries that succeeds with multiplicative approximation guarantees.
However, their framework uses only the tail oracle and therefore is subject to the lower bound that we provide in Section~\ref{sec:counterexample}.
In particular, their guarantees make stringent assumptions on the maximum singular values of the sensing matrix $A$.

The paper~\cite{davenport_redundant} introduces an algorithm called \emph{Signal Space CoSaMP} (SSCoSaMP), which also assumes the existence of multiplicative approximate oracles.
However, the assumptions made on the oracles are restrictive.
Interpreted in the model-based context, the oracles must capture a significant fraction of the optimal support in each iteration, which can be hard to achieve in practice.
The more recent paper~\cite{GN13} proposes a version of SSCoSaMP which succeeds with oracles satisfying both multiplicative head- and tail-approximation guarantees.
Indeed, our AM-CoSaMP algorithm and associated proofs are closely related to this work.
However, AM-CoSaMP requires technically weaker conditions to succeed and our proof techniques are somewhat more concise.
See Section~\ref{sec:amcosamp} for a more detailed discussion on this topic.

In a parallel line of research, there have been several proposals for compressive sensing methods using {\em sparse} measurement matrices~\cite{BGIK09,cs_sparse_matrices_survey}.
Recent efforts have extended this line of work into the model-based setting.
The paper~\cite{IR13} establishes both lower and upper bounds on the number of measurements required to satisfy the model RIP-1 for certain structured sparsity models.
Assuming that the measurement matrix $A$ satisfies the model RIP-1,
the paper~\cite{BBC14} proposes a modification of \emph{expander iterative hard thresholding} (EIHT)~\cite{RF13}, which achieves stable recovery for arbitrary structured sparsity models.
As with the other algorithms for model-based compressive sensing, EIHT only works with \emph{exact} model projection oracles.
In Section~\ref{sec:modelrip1}, we propose a more general algorithm suitable for model-based recovery using only approximate projection oracles.

We instantiate our algorithmic results in the context of the Constrained Earth Mover's Distance (CEMD) model, developed in~\cite{HIS}.
The model was originally motivated by the task of reconstructing time
sequences of spatially sparse signals. There has been a substantial
amount of work devoted to such signals, e.g., \cite{modifiedcs,duartedcs}.
We refer the reader to~\cite{HIS} for a more detailed discussion about the model and its applications.
The paper introduced a tail oracle for the problem and empirically
evaluated the performance of the recovery scheme.
Although the use of the oracle was heuristic, the experiments demonstrate a substantial reduction in the number of measurements needed to recover slowly
varying signals.
In this paper, we provide a rigorous analysis of the tail-approximation oracle originally proposed in~\cite{HIS}, as well as a novel head-approximation algorithm.
Combining these two sub-routines yields a model-based compressive sensing scheme for the CEMD model using a nearly optimal number of measurements.

\subsection{Subsequent Work}

Since the appearance of the conference version of this manuscript~\cite{approxSODA}, a number of works have explored some of its implications. The works~\cite{treesISIT,modelcsICALP} develop approximation algorithms for the \emph{tree-sparsity} model~\cite{modelcs}. These algorithms, coupled with our framework, immediately imply sample-optimal recovery schemes for tree-sparse signals that run in \emph{nearly linear-time}.  Additionally, our approximation oracles for the CEMD model can be of independent interest in signal processing applications. For instance,~\cite{faultICASSP} uses the tail-approximation procedure developed in Section~\ref{sec:tail} for detecting \emph{faults} in subsurface seismic images. Investigations into further extensions are currently underway.


TITLE: Origin of the flag variety
QUESTION [1 upvotes]: When and where were flag varieties (more generally $G/P$'s) first introduced? What was the original motivation to study it?
To my knowledge, I'd say an early motivation to study the Grassmannian was to formalize Schubert calculus, and their use in the theory of characteristic classes later. I also know flag varieties are essential for the splitting principle but surely they did appear before.

REPLY [0 votes]: Question: "When and where were flag varieties (more generally G/P's) first introduced? What was the original motivation to study it?"
Answer: Maybe a Historian should give a precise answer to this, but words such as "Grassmannian" and "Plucker" are the names of mathematicians involved in the study of these varieties in the 1900s.
It is a fact that for any semi simple algebraic group $G$ over a field $k$ of characteristic zero and any parabolic subgroup $P \subseteq G$ the quotient $\pi:G \rightarrow G/P$ is a smooth projective variety - the flag variety of $P$.
Given any invertible sheaf $L \in Pic^G(G/P)$ it follows its global sections $H^0(G/P, L)$ (if non-empty) is a finite dimensional irreducible $G$-module and all finite dimensional irreducible $G$-modules can be constructed in this way (the Borel-Weil-Bott theorem). There is also the study of regular holonomic $D_{G/P}$-modules $E$ on $G/P$ (the Bernstein-Beilinson notion $D$-affinity) and relation to generalized Verma modules. This is a much studied topic: The relation between the representation theory of $G$ and the geometry of $G/P$. The Bezout theorem is a theorem about the intersection of curves in $\mathbb{P}^2_k$, and this goes back to the 1700s and 1800s and Newton and Bezout. This theorem does not hold for plane affine curves.
Comment: "Thank you. I think D-modules on G/P comes much after the introduction of the flag varieties. I was interested in the original motivations to study flag varieties, so I don't think this is an answer to my question. – student"
Answer: Yes, D-modules were introduced in the 1960s/70s. One of the first occurrences of the projective  plane was with the "Bezout theorem", and as mentioned this theorem is not true for the affine plane. The theorem is non-trivial since it speaks of multiplicities: If $C_1,C_2 \subseteq \mathbb{P}^2_k$ are two plane projective curves of degrees $d_1,d_2$ where
$$C_1 \cap C_2=\{P_1,..,P_l\}$$
are their common points (with intersection multiplicity $m_i$) it follows
$$ \sum_i m_i =d_1d_2.$$
Hence the theorem speaks of multiplicity. You may describe $\mathbb{P}^2_k$ as $SL(3,k)/P$ for a parabolic subgroup $P$, hence the projective plane is an example of a "flag variety $G/P$": It is a parameter space parametrizing lines $l$ in $k^3$.
This is what the flag variety does in general: If $1 \leq d_1<d_2<\cdots d_k< d$ is a set $\underline{D}$ of integers, there is the flag variety $\mathbb{F}:=\mathbb{F}(\underline{D},k^d)$. This is a smooth projective variety parametrizing flags $E_i$ in $k^d$ of type $\underline{D}$. There is a parabolic subgroup $P \subseteq SL(d,k)$ and an isomorphism $\mathbb{F}(\underline{D},k^d)\cong SL(d,k)/P$. There is a 1-1 correspondence between
the set of $k$-rational points $\mathbb{F}(k)$ of $\mathbb{F}$ and the set of flags in $k^d$.


TITLE: Examples of Smooth manifolds: Finite dimensional vector space
QUESTION [1 upvotes]: I can't understand why a finite dimensional vector space is a smooth manifold. I think it's a trivial thing, but I can't deal with it.
Let $V$ a finite-dimensional real vector space. $V$ is a topological manifold of dimension $n$. This because $V\simeq\mathbb{R}^n$.
Now, each basis $(E_1,\dots, E_n)$ for $V$ defines a basis isomorphism $E\colon\mathbb{R}^n\to V$ by $$E(x)=\sum_{i=1}^nx_iE_i.$$
This map is a homeomorphism, then $\big(V,E^{-1}\big)$ is a chart. if $\big(F_1,\dots,F_m\big)$ is any other basis and $F(x)=\sum_jx_jF_j$ is the correspondig isomorphism, then there is some invertible matrix $\big(A_j^i \big)$ such that $E_i=\sum_j A_j^{i} F_j$ for each $i$. Up to this point it seems to have been applied, without further explanation.
The transition map between the two charts $\big(V, E^{-1}\big)$, $\big(V, F^{-1}\big)$ is given by $F^{-1}\circ E(x)=\tilde{x}$, where $\tilde{x}=(\tilde{x_1},\dots, \tilde{x_n})$ is determined by $$\sum_{j=1}^n \tilde{x_j} F_j=\sum_{i=1}^{n} x_iE_i=\sum_{i,j}^{n}x_iA_j^{i} F_j$$

Question. Why this thing?

It follows that $\tilde{x}=\sum_i A_i^{j}x_i$.
Thus, the map sending $x$ to $\tilde{x}$ is an invertible linear map.

Question Why the map sending $x$ to $\tilde{x}$ is an invertible linear map?

Thanks!

REPLY [1 votes]: $\tilde{x}=F^{-1}\circ E(x)$, so $F(\tilde{x})=E(x)$, i.e. by definition of $F$ and $E$
$$ \sum_j\tilde{x}_j F_j=\sum_jx_j E_j$$
and since $E_j=\sum_i A^i_j F_j$
$$ \sum_j\tilde{x}_j F_j=\sum_jx_j E_j=\sum_{j,i}x_j A^i_j F_j$$
you might recognize that $\tilde{x}_j=\sum_i A^i_j x_i$ is just the matrix vector multiplication $\tilde{x}=Ax$. Since $A$ maps a basis to a basis, $A$ is an invertible matrix.


TITLE: Have anyone seen an unbound electron absorb/emit a photon via Bremsstrahlung process?
QUESTION [1 upvotes]: I know free electron cannot absorb or emit photon as it cannot satisfy both the conservation of energy and momentum at once but how about in Bremsstrahlung process? The presence of a positively charged particle is used to deflect the trajectory of an unbounded electron causing it to decelerate/accelerate depending if it's inwards or outwards, then it should emit photon no?

REPLY [2 votes]: Bremsstrahlun photons were used in order to  identify  electrons  when studyig elementary particle interactions in cloud chambers and bubble chambers.
Strong magnetic fields were imposed so that charged particles would bend and their momentum measured. The photon from the bending electrons pair-produces in the chamber and thus identify the photon
In this paper one such example is given in page 19,

This unassuming picture is one of the bubble chamber ‘greats’: a tiny electromagnetic shower demonstrates the existence of a very simple, but rare, collision between an anti-muon neutrino ̄νμbeam particle and an atomic electrone−in the bubble chamber liquid

The first e− is the one that was knocked out of an atom by the  ̄νμ. The two little e+e− pairs are produced by bremsstrahlung photons emitted from this first electron, thus identifying it.


TITLE: Misunderstanding in the universal property of the Cartesian product
QUESTION [7 upvotes]: Here' what my book has to say on the universal property and specifically the universal property of the Cartesian product:

I understand the proof and that $\langle f,g\rangle$ is unique and all that.  What I don't get is how this "property" supposedly characterizes the Cartesian product.  The first paragraph says that universal properties "characterize a given construction" but don't we have to know what the Cartesian product is both to state the universal property and to prove it?

REPLY [1 votes]: The Universal property characterizes the cartesian product the following way:
Theorem Let $Z$ be a set and $\pi^Z_1 : Z \to X$ and $\pi^Z_2:Z \to Y$ be any triple which satisfies the same universal property. Then, there exists some bijection $F : Z \to X \times Y$ such that for $j=1,2$ we have
$$\pi_j \circ F = \pi_j^Z$$
Proof Since $\pi^Z_1 : Z \to X$ and $\pi^Z_2:Z \to Y$, by the Universal property from your Theorem there exists an unique $F : Z \to X \times Y$ such that
$$\pi_j \circ F = \pi_j^Z$$
Now, since $\pi_1: X \times Y \to X$ and $\pi_2 : X \times Y \to Y$, by the universal property for $Z$ there exists some $G : X \times Y \to Z$ such that
$$\pi^Z_j \circ G = \pi_j$$
Finally look at $F \circ G : X \times X \to X \times X$. Both $F \circ G$ and $Id$ satisfy the universal property for $<f,g>$
$$f=\pi_1 : X\ times Y \to X \,;\, g=\pi_2 : X \times Y \to Y$$
in your diagram. By the uniqeueness part we get
$$F \circ G= Id$$
Same way, both $G \circ F$ and $Id$ satisfy the universal property for $Z$ hence $G \circ F =Id$.
This shows that $F,G$ are inverses of eachother.