Results 1 to 3 of 3

Math Help - Maximum number of vectors

  1. #1
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,930
    Thanks
    782

    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|$?
    Last edited by SlipEternal; June 13th 2014 at 11:44 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,930
    Thanks
    782

    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.
    Last edited by SlipEternal; June 13th 2014 at 03:11 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,930
    Thanks
    782

    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?
    Last edited by SlipEternal; June 13th 2014 at 04:24 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Maximum Number of bit Strings
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 28th 2012, 02:02 AM
  2. Finding the Maximum Number of Areas
    Posted in the Math Puzzles Forum
    Replies: 1
    Last Post: June 11th 2012, 10:35 AM
  3. maximum number of circles in a rectangle?
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: May 5th 2012, 06:37 AM
  4. Maximum number of linearly independent solutions
    Posted in the Differential Equations Forum
    Replies: 4
    Last Post: January 3rd 2012, 08:33 AM
  5. Replies: 1
    Last Post: April 6th 2010, 07:25 AM

Search Tags


/mathhelpforum @mathhelpforum