1
$\begingroup$

Let $\mathbb F_q$ be the finite field with $q$ elements. Suppose $V$ is a linear space of dimension $n$ over $\mathbb F_q$, and $r<n$. What is the maximal $k$ such that for arbitrary $k$ subspaces $W_1,W_2,\dots,W_k$ of $V$ of dimension $r$, there always exists a subspace $U$ of $V$ of dimension $n-r$ which satisfies $U\cap W_i=\{0\}$ for each $W_i$? Thank you.

PS. The choice of $W_i$ is arbitrary, and I didn't say it clearly in the former version, sorry.

PS. I guess the number might be something like $q^{n-r}$, but I don't know how to prove it.

PS. The answer is $k=q$.

$\endgroup$

2 Answers 2

5
$\begingroup$

I think we have $k = q$ (for all $r$).

First, suppose $r = n - 1$. The vector space $V$ can be covered by $q + 1$ codimension-one hyperplanes $W_1,W_2, \ldots,W_{q+1}$ (but no fewer). (If we think of the projective space $[V]$, the most efficient covering is by taking the hyperplane at infinity, plus a set of $q$ parallel hyperplanes in affine space.) Then every $1$-dimensional subspace intersects (in fact, is contained in) some $W_i$. So $k = q$ when $r = n-1$.

To prove $k \le q$ in general, fix a subspace $Z$ of $V$ that has dimension $r + 1$, and use the previous case to choose $q + 1$ subspaces $W_1,\ldots,W_{q+1}$ of dimension $r$ in $Z$, such that every $1$-dimensional subspace of $Z$ is contained in some $W_i$. Since every subspace $U$ of dimension $n - r$ in $V$ contains a subspace of $Z$ that has dimension (at least) $1$, we conclude that $U$ intersects some $W_i$. So $k < q + 1$, as desired.

Now we prove the matching lower bound: $k \ge q$. Let $W_1,W_2, \ldots,W_q$ be any $r$-dimensional subspaces of $V$. Since (as mentioned above), it takes $q + 1$ hyperplanes to cover all of $V$, we know there is some $1$-dimensional subspace $L$ that is not contained in $\bigcup_i W_i$. Let $\overline{V} = V/L$. By induction on $n - r$, there is an $(n-r-1)$-dimensional subspace $\overline{U}$ of $\overline{V}$ that has trivial intersection with every $\overline{W_i}$. Lift $\overline{U}$ to an $(n-r)$-dimensional subspace of $V$. Then $U$ has trivial intersection with every $W_i$.

$\endgroup$
1
  • $\begingroup$ Your answer is excellent! Thank you. $\endgroup$
    – var
    Mar 14, 2015 at 12:53
2
$\begingroup$

EDIT: This answers an earlier version of the question:

Your question seems to be equivalent to fixing $V$ and an $(n-r)$-dimensional subspace $U$ and then asking how many $r$-dimensional subspaces $W$ have $\{0\}$ intersection with that $U$. The number is (unless I've made a silly mistake) $$ \frac {(q^n-q^{n-r})(q^n-q^{n-r+1})\cdots(q^n-q^{n-1})} {(q^r-1)(q^r-q)\cdots(q^r-q^{r-1})}. $$ Here the numerator counts the number of bases $\{b_1,\dots,b_r\}$for such subspaces $W$. The first vector $b_1$ can be any vector $\notin U$; then $b_2$ can be any vector not in the space spanned by $U$ and $b_1$; etc. Similarly, the denominator counts the number of bases for any single $W$, so the quotient counts the $W$'s.

$\endgroup$
7
  • $\begingroup$ I am a little confused that I don't know why your proof is equivalent to what I need, actually all $W_i$ in my problem may be very general. $\endgroup$
    – var
    Mar 13, 2015 at 22:27
  • $\begingroup$ @var Well, if you have, as in the problem, $k$ "very general" subspaces $W_i$ and there exists a $U$ meeting them all at only $\{0\}$, then, for that $U$, your $k$ $W_i$'s would be among the spaces I counted, so $k$ would be at most the number, call it $A$, that I gave in my answer. Conversely, there are $A$ subspaces that satisfy your requirements, namely the $A$ spaces that I counted, because there's a $U$ meeting them all only at $\{0\}$. So, for a collection of $W$'s as in the question, the largest possible $k$ is $A$. $\endgroup$ Mar 13, 2015 at 22:32
  • $\begingroup$ Cancelling denominators, the fraction seems to simplify to $q^{(n-r)r}$. $\endgroup$ Mar 13, 2015 at 22:36
  • 1
    $\begingroup$ @EmilJeřábek You're right. Thanks. Now that you've pointed it out, there's an easier proof. Regard $V$ as $U\oplus Z$ from some $r$-dimensional $Z$, and note that the $W$'s that we need to count are just the graphs of linear maps from $Z$ to $U$. Such a map is given by an $(n-r)$ by $r$ matrix of elements of $\mathbb F_q$. $\endgroup$ Mar 13, 2015 at 22:47
  • 1
    $\begingroup$ @var That seems to be a rather different question. $\endgroup$ Mar 13, 2015 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.