Existence proof of large scattered subspaces in finite vector spaces
A probabilistic construction of maximum $h$-scattered subspaces
Information Theory
Summary
The paper studies special kinds of subspaces called maximum h-scattered subspaces within vector spaces over finite fields. These subspaces have important connections to certain error-correcting codes known as MRD codes, which are useful for data transmission. The authors prove that such maximum h-scattered subspaces exist under specific conditions related to the dimensions and divisibility properties of the spaces involved. They use probabilistic methods involving random matrices over extended algebraic structures to establish their results. This extends the known existence of MRD codes for more parameters.
What this means in practice
- •For network engineers: Design error-correcting codes with guaranteed existence for various data transmission settings using the newly proven maximum h-scattered subspaces.
- •For coding theory developers: Construct maximum rank distance codes with specific lengths and dimensions determined by the paper’s divisibility conditions to improve reliability in storage systems.
A theory result. No direct application yet.
Authors
Alessandro Giannoni, Alessandro Neri
Abstract
Let $1\le h\le n-2$ and $g=\gcd(n,h+1)$. We prove that, for every prime power $q$, a maximum $h$-scattered $\mathbb{F}_q$-subspace of $V(r,q^n)$ exists whenever $(h+1)\mid rn$ and $$r\ge\frac{h+1}{g}\bigl(h(n-h-2)+1\bigr).$$ In particular, for fixed $n$ and minimum distance $δ\in\{2,\ldots,n-1\}$, $\mathbb{F}_{q^n}$-linear MRD codes of length $N$ exist for every $q$ and every sufficiently large $N$ such that $n$ divides $(n-δ+1)N$, with a bound on $N$ depending only on $n$ and $δ$. We take the $\mathbb{F}_{q^s}$-span of the columns of a random matrix $A$ over the algebra $R=\mathbb{F}_{q^n}\otimes_{\mathbb{F}_q}\mathbb{F}_{q^s}$, for a suitable $s$. Such a subspace is maximum $h$-scattered if and only if the kernel of $A$ contains no nonzero vector whose expansion with respect to an $\mathbb{F}_q$-basis of $\mathbb{F}_{q^s}$ has rank weight at most $h+1$. When $\gcd(n,s)=1$, $R$ is a field, and a first-moment argument, counting these vectors up to multiplication by $\mathbb{F}_{q^n}^*\mathbb{F}_{q^s}^*$, shows that with positive probability the kernel contains none of them if $s>h(n-h-2)$. When $d=\gcd(n,s)>1$, $R$ is a product of $d$ fields, and vectors vanishing in some factors lie in the kernel with larger probability. We control them by proving that, for an $(h+1)$-dimensional $\mathbb{F}_q$-subspace $D$ of $\mathbb{F}_{q^n}$, the elements of $D\otimes_{\mathbb{F}_q}\mathbb{F}_{q^s}$ vanishing outside $k$ given factors, $0<k<d$, form an $\mathbb{F}_{q^s}$-space of dimension at most $(h+1)k/d$, with equality only if $D$ is linear over a subfield of $\mathbb{F}_{q^n}$ larger than $\mathbb{F}_q$. Taking $s=gr/(h+1)$ gives the bound on $r$. Finally, if $(n-h-1)\mid(h+1)$, then for every $r$ satisfying the above inequality there is an $h$-scattered $\mathbb{F}_q$-subspace of $V(r,q^n)$ of dimension $\lfloor rn/(h+1)\rfloor$, without a divisibility condition on $rn$.