Let $V$ be a $m$-dimensional vector space over $\mathbb{F}_q$ and $1<\ell<m-1$. Let $r$ be a positive integer such that $r\ell\leq m$.

QUESTION. What is the maximum number of elements in the union of $r$ subspaces of $V$, each of dimension $m-\ell$?

For $r=2$ this number is $2q^{m-\ell}-q^{m-2\ell}$. I want this in general or when $r>2$.


1 Answer 1


Pick naturals $q,m,l,r$. Assume $q$ is a prime power and $2l\leq m$. If $r\leq q^l+1$ then the maximal size of the union of $r$ many $(m-l)$-dimensional sub-vector spaces of $V=\mathbb{F}_q^m$ is $S=rq^{m-l}-(r-1)q^{m-2l}$. If $r\geq q^l+1$ then the size is $q^m$.

Note that for $r=q^l+1$ we get $S=q^m$. Since the maximal size of the union is obviously bounded from above by $q^m$ and is non-decreasing as a function of $r$, it is enough then to show that for $r\leq q^l+1$ the maximal size of the union is $S$. Below we do assume $r\leq q^l+1$.

Assume having such $r$ subspaces with maximal union size. Since the intersection of each two has dimension bounded from below by $m-2l$, the size of the intersection is bounded from above by $S$ and this is obtained iff they all have a common intersection of dimension $m-2l$. In this case we may pass to the quotient space obtained by moding up this subspace, thus reduce to the special case $m=2l$ which is dealt by the following

Lemma: The maximal size of a collection of pairwise trivially intersecting $l$-dimensional subspace of $\mathbb{F}_q^{2l}$ is $q^l+1$.

An example of $q^l+1$ many such subspace is obtained by considerng the collection of lines inside a 2-dimensional space over $\mathbb{F}_{q^l}$.

On the other hand, if we have $s$ such subspaces and $s>q^l+1$ then the size of their union is $sq^l-(s-1)>q^{2l}$, which is an absurd.

Bonus exercise: based on the proof of the lemma above, prove that for general $l$ and $m$, the maximal number of pairwise trivially intersecting $l$-dimensional subspaces of $\mathbb{F}_q^m$ is $\frac{q^{\lfloor \frac{m}{l}\rfloor\cdot l}-1}{q^l-1}$.

  • $\begingroup$ Thanks! I have verified the proof and indeed this is what I was expecting but was not able to give a proper argument and also the condition on $r$. Do you think it will be similar to deal with r subspaces of different dimension. More precisely if we take union of $r$ subspaces $V_i\; 1\leq i\leq r$ and $\dim V_i= m-\ell_i$ and we may assume $\ell_1\leq\ldots\leq \ell_r$. $\endgroup$
    – user100393
    Oct 29, 2016 at 16:05
  • $\begingroup$ I don't understand the second paragraph : that it suffices to assume $r\leq q^l+1$ because the two values coincide. Anyway, since the given value for $r\geq q^l+1$ is $q^m$, the number of points of $\mathbf F_q^m$, one may even assume that $r\leq q^l$. $\endgroup$
    – ACL
    Oct 29, 2016 at 16:23
  • $\begingroup$ @user100393 I think that if you are willing to choose $q$ large enough (after fixing all other parameters) then you will get a similar answer (namely $\sum_{i\leq r} q^{m-\ell_i}-\sum_{i<r} q^{m-\ell_r-\ell_i}$ if I get it right) and that if $r$ is large enough (after fixing all other parameters) than the answer will be $q^m$. But I suppose dealing with intermediate values might be harder... I will think of this (if I'll find the time). $\endgroup$
    – Uri Bader
    Oct 29, 2016 at 16:44
  • $\begingroup$ @ACL the second paragraph is rewritten now for extra clarity. $\endgroup$
    – Uri Bader
    Oct 29, 2016 at 22:07

Your Answer

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