Let $\mathbb F_5=\{0,1,2,3,4\}$ is finite field of size $5$. I am trying to find minimal $n$ so that vector space of dimension $n$ over $\mathbb F_5$ contains $2$ linearly independent vectors so that all vectors of their linear span contains $1$ as a coordinate. In other words there should be linear subspace of dimension $2$ so that all vectors contains $1$ coordinate (except trivial vector).

For $n=8$ there is a solution: $(1,2,3,4,0,0,0,0)$ and $(0,0,0,0,1,2,3,4)$.

I need hint to prove that no solution for $n<8$ exist.

  • $\begingroup$ I took the liberty of adding the combinatorial-designs tag. There is a good chance that users with expertise in the combinatorics of finite affine planes can say something about my "conjecture" right away. $\endgroup$ Dec 31, 2015 at 21:12

1 Answer 1


This is a tough nut to crack (or, more likely, I'm looking at it all wrong). Anyway, I think I found a promising way to look at it.

Conjecture. It is impossible to cover all the points of the punctured plane $\Bbb{F}_5^2\setminus\{(0,0)\}$ by seven lines, none passing through the origin.

This is just a conjecture. I think it's true, but I'm not betting a fortune on it yet. At the bottom I will share my thoughts, but let's first show how this settles your question.

Claim. There aren't any 2-dimensional subspace of the prescribed type for $n<8$.

Proof. (Assuming the above conjecture.) Assume contrariwise that such a subspace $V$ exists. Let $u=(u_1,u_2,\ldots,u_n)$ and $v=(v_1,v_2,\ldots,v_n)$ be a basis of $V$. The required property says that for all $(x,y)\in \Bbb{F}_5^2\setminus\{(0,0)\}$ there exists an index $i, 1\le i\le n$ such that $xu_i+yv_i=1$. This implies that the set $\Bbb{F}_5^2\setminus\{(0,0)\}$ is covered by the $n$ lines $u_ix+v_iy=1$. Clearly none of those pass through the origin. Therefore the conjecture implies that $n>7$.

Remark. Observe that 2-dimensional subspace of $\Bbb{F}_5^6$ spanned by $(0,1,1,1,1,1)$ and $(1,0,1,2,3,4)$ has the property that all the non-trivial vectors have exactly one component equal to zero. Getting a fixed non-zero component to appear is more difficult as witnessed here. Of course, scalar multiplication allows us to replace $1$ with any other non-zero scalar.

How might the conjecture be verified? The lines in the plane $\Bbb{F}_5^2$ can have one of six directions, either parallel to the $y$-axis or one of the five possible slopes. Therefore among the seven lines (assuming that the conjecture could be false) there is at least one parallel pair. This leads to a systematic (IMO manageable) case-by-case analysis.

  • We cannot have five parallel lines, because one of them would pass through the origin.
  • If we have four parallel lines, then the they cover 20 points out of 24. The remaining 4 points form a line through the origin, so no line avoiding the origin can cover more than one of those points. Therefore we need eight lines total. In light of the idea of the "proof" this is exactly the $n=8$ solution discovered by the OP:
  • If we have three parallel lines (but the others are non-parallel to these three) they cover 15 points. The remaining lines intersect all those parallel ones, so they can only cover two previously uncovered points. Nine points remain to be covered, so we need at least five more lines. This, again, brings the total to eight.
  • If we have two pairs of parallel lines, and the other lines are not parallel to either of these, then we can argue as follows. By a suitable choice of a coordinate system those two parallel pairs of lines have equations $y=1, y=2$ and $x=1,x=2$. We see that the points $(0,3),(0,4)$, $(3,0),(3,3),(3,4)$, $(4,0),(4,3),(4,4)$ - a total of eight - are still uncovered. The remaining lines must have a non-zero finite slopes, so there will be no repetitions among the coordinates of their points. This implies that the only possible line "wasting" only two of its points as intersections of the two parallel pairs must pass through $(1,2)$ and $(2,1)$. The line passing through $(1,1)$ and $(2,2)$ also passes through the origin. So we can have one more line bringing in 3 previous uncovered points, and after that we max out at two. Therefore we need four more lines to cover those eight points. A total of eight.
  • This leaves open the case of covering the plane with a single pair of parallel lines and five others. W.l.o.g. we can assume that the parallel lines are $x=1$ and $x=2$. The five remaining lines then must have distinct slopes $\in\Bbb{F}_5$. Leaving this case to somebody else. At least for now :-)
  • $\begingroup$ Your conjecture is indeed correct. Proof can be found here ac.els-cdn.com/0097316577900012/… $\endgroup$
    – Ashot
    Dec 31, 2015 at 22:12
  • $\begingroup$ For $q$ and $n$ minimal number of cosets needed to cover all vectors of $\mathbb F_q^n/\{(0,..,0)\}$ is $n(q-1)$. In fact I was trying to find another proof of that result :) I was thinking that posted problem is easier than orignal one but seems that they are equivalet and both doesn't have combinatorial proof. $\endgroup$
    – Ashot
    Dec 31, 2015 at 22:14
  • $\begingroup$ @Ashot: For the first hour or so I was hoping to reduce this to a coding theoretical result but I couldn't think of anything suitable. $\endgroup$ Dec 31, 2015 at 22:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .