# Thread: Maximum number of vectors

1. ## Possible Challenge: Maximal set

Let $V$ be an $m$-dimensional vector space over a finite field of order $p^n$ for some prime $p$ and some positive integer $n$. Let $K\subset V$ be a collection of vectors such that every subset $K'\subset K$ with $|K'|=m$ is a basis for $V$. What is the maximum size of $|K|$?

2. ## Re: Maximum number of vectors

For notation, I will use $p$ instead of $p^n$, and just say $p$ is a prime power. I believe $|K|=k$ where $k$ is the smallest integer such that

$\sum_{i=0}^m (-1)^{m-i}\binom{\binom{k}{m-1}}{i}p^i \le 0$

For $p=2$, I find $|K|\le m+1$. For $m=2$, $|K|\le \left\lceil \dfrac{p^2}{p-1}\right\rceil$. I haven't checked for larger $p,m$ yet.

3. ## Re: Maximum number of vectors

I'm wrong. For $p=4, m=2$, $|K|\le 5$.

I know why I was wrong. Suppose $|K|=k$ and we want to add one additional vector. Let's figure out the set of forbidden vectors. The zero vector is forbidden. There are $p-1$ nonzero multiples for each of the $k$ vectors. There are $(p-1)^2$ linear combinations of each of the $\binom{k}{2}$ pairs of vectors. So, the number of forbidden vectors is

$\sum_{i=0}^{m-1}\binom{k}{i}(p-1)^i$

So, we want the smallest positive integer $k$ such that

$\sum_{i=0}^{m-1}\binom{k}{i}(p-1)^i\ge p^m$

For $m=2$, that means $1+k(p-1)\ge p^2$, so $k\ge \dfrac{p^2-1}{p-1}$ means $k\ge p+1$, or $k=p+1$.

For $m=3$, that means $1+k(p-1)+\binom{k}{2}(p-1)^2 \ge p^3$

Simplifying, we have $k^2-k\dfrac{p-3}{p-1}-2\dfrac{p^3-1}{(p-1)^2} \ge 0$

So, $k\ge \dfrac{\sqrt{8p^3+p^2-6p+1}+p-3}{2(p-1)}$

Is that right? Or is there a possibility for overlap? Are linear combinations of 2 vectors unique among other sets of 2 vectors where among the four vectors, any three are linearly independent?