Let $m\ge 2$ be an integer and $\mathbb{F}$ be a finite field of order $p^k$. I want to construct as many as possible $m$-dimensional vectors $v_1,v_2,\ldots,v_n$ in field $\mathbb{F}$ such that any $m$ of these vectors are independent. What is the maximal value for $n$. How to construct these vectors.

Denote elements in $F$ by $a_1,\ldots,a_{p^k}$. If we define $v_i=(1,a_i,a_i^2,\ldots,a_i^{m-1})$ for $i$ between 1 and $p^k$, then clearly any $m$ of these vectors are independent. Thus $n\ge p^k$.

On the other hand, since there are exactly $p^{km}-1$ nonzero vectors and each vector can be used at most once in any legal construction, we see that $n\le p^{km}-1$.

Are there any references discussing the problem?

  • 10
    $\begingroup$ Such a collection of vectors corresponds to MDS codes. An easy to prove bound is that there are at most $q + m - 1$ such vectors, where $q = p^k$. Google "MDS codes", and "MDS conjecture" (recently solved in the prime case by Simeon Ball). $\endgroup$ – Anurag Mar 17 '16 at 1:28
  • $\begingroup$ @ Anurag. This looks very good, thank you. $\endgroup$ – W. Wang Mar 17 '16 at 2:12
  • $\begingroup$ Here are some links for you and others interested in this question: www-ma4.upc.es/~simeon/jems-mds-conj-revised.pdf, www-ma4.upc.es/~simeon/mdsconj.pdf, arxiv.org/abs/1511.03623. See the references in these papers for more. $\endgroup$ – Anurag Mar 21 '16 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.