2

Let $d$ and $n$ be natural numbers, and let $\mathbb F_q$ be a finite field. For any injection $\sigma: \{1, \dots, d\} \to \{1, \dots, n\}$, we can define a corresponding linear transformation $T_\sigma: \mathbb F_q^d \to F_q^n$ by $T_\sigma(e_i) = f_{\sigma(i)}$, where $e_1, \dots, e_d$ and $f_1, \dots, f_n$ are the standard bases of $\mathbb F_q^d$ and $\mathbb F_q^n$ respectively. A linear error-correcting code with distance greater than $d$ can then be characterized as a subspace $V$ of $\mathbb F_q^n$ such that $\text{im}(T_\sigma) \cap V = 0$ for all injections $\sigma$.

It is possible to define a sort of dual concept: For any injection $\sigma: \{1, \dots, d\} \to \{1, \dots, n\}$, define $T^\sigma: \mathbb F_q^n \to \mathbb F_q^d$ by $$T^\sigma(f_i) = \begin{cases}e_j, &\text{ if } i=\sigma(j) \\ 0, &\text{ if } i \notin \text{im}(\sigma)\end{cases}.$$ Let's call a subspace $V \subseteq \mathbb F_q^n$ a $d$-dimensional cover if it has the property that $T^\sigma(V) = \mathbb F_q^d$ for all injections $\sigma$.

For example, the subspace of $\mathbb F_2^4$ spanned by the rows of the following matrix is a 3-dimensional cover:

$$\begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix}$$

In general, given a matrix $A$ whose rows form a basis for a subspace $V \subseteq \mathbb F_q^n$, $V$ is a $d$-dimensional cover if and only if every submatrix $B$ formed by selecting $d$ columns of $A$ has the property that the rows of $B$ span $\mathbb F_q^d$, or equivalently, that the columns of $B$ are linearly independent.

I have a few related questions about this concept:

  • Are there any known results about how to construct good $d$-dimensional covers, i.e., ones with relatively large values of $d$ for given values of $n$, $q$, and $k=\text{dim}(V)$? I'm particularly interested in the case where $q=2$ and $k \ll n$.

  • Is there an existing name for this concept in the literature?

  • Are there any known results that precisely relate these structures relate to error-correcting codes (for example, general constructions which, given an error-correcting code, would produce a corresponding $d$-dimensional cover or vice versa)?

I did find this paper which implies a construction for a $d=3$ over $\mathbb F_2^n$ for $n\geq 3$ along with some (mainly) negative results, but it leaves open a wide space and it seems like much better constructions should exist.

Brent Kerby
  • 5,539
  • Undoubtedly you have looked at MDS-codes. I'm not sure there is much else to be said. Need to wrap my head around the question :-) – Jyrki Lahtonen Dec 04 '19 at 10:18
  • 2
    For example, you get Reed-Solomon codes when the matrix has columns of the form $(1,x,x^2,\ldots,x^{d-1})$ with $x$ ranging over $\Bbb{F}_q$, when linear independence of a set of columns follows from Vandermonde determinants. You can tag one more column $(0,0,\ldots,0,1)$ without ruining the argument, and there's another trick I don't remember right away. Anyway, IIRC with MDS codes when $d>1$ we usually have severe problems getting $n$ much higher than $q$. Here is some new material. – Jyrki Lahtonen Dec 04 '19 at 10:29
  • Locally, see this. With $q=2$ there isn't much you can do. – Jyrki Lahtonen Dec 04 '19 at 10:40

0 Answers0