# Covering the finite plane with lines

This is, essentially, a geometrically rendered version of the question I asked a week ago, with the emphases slightly shifted; it seems more natural and appealing (to me, at least) in this form.

Let $$p\ge 3$$ be a prime number. Suppose we are given $$N$$ lines $$l_1,\dotsc,l_N\subset\mathbb F_p^2$$, and we want to translate them to get new lines $$l_1',\dotsc,l_N'$$ (which are either parallel, or identical to the original lines) so as to have the whole vector space $$\mathbb F_p^2$$ covered by these new lines: $$l_1'\cup\dotsb\cup l_N'=\mathbb F_p^2$$. This can be impossible if $$N\le2(p-1)$$, as it follows by considering the system of $$p-1$$ "vertical" and $$p-1$$ "horizontal" lines. Is this always possible if $$N\ge 2p-1$$?

More generally, given $$(p-1)n+1$$ affine hyperplanes in $$\mathbb F_p^n$$, can one always translate them so that the resulting translates cover the whole space $$\mathbb F_p^n$$?

• This is true for lines with three distinct directions. Already for four directions (say, vertical, horizontal, parallel to $x\pm y=0$) not clear for me. – Fedor Petrov Nov 28 '18 at 21:21
• @FedorPetrov The answer to the question, as posed, is "certainly not". If $N(p)$ is the minimal $N$ with the property that any $N$ lines can be shifted to cover $\mathbb F_p^2$, then $\lim_{p\to\infty}(N(p)-2p)=+\infty$. The trick is to consider $p-3$ vertical lines, $p-b$ horizontal lines and choose all other directions more or less at random, so it would be pretty hard to cover any $3\times b$ rectangular arrangement by just $b+C$ lines. However, I still do not know even if $N\ge 2.00001p$ would suffice for large enough $p$. – fedja Nov 29 '18 at 3:14
• @fedja: Could you expand your remark (the "pretty hard to cover" statement) and, maybe, convert it to an answer? – Seva Dec 1 '18 at 19:53
• @Seva Sure. I just wanted to prove something more interesting but since you asked and since I'm failing so far, I'll do it later today. – fedja Dec 1 '18 at 22:23
• @FedorPetrov For the 4 directions you consider, lines $x=k$, $y=k$, $x+y=k$ and $x-y=k$ for $-p/4 < k < p/4$ cover all points in $\mathbb{F}_p^2$. (Consider cases based on which of the intervals $(-p/2,-p/4)$, $(-p/4,p/4)$ and $(p/4, p/2)$ has a representative of $x$, and of $y$, in them.) But if you take $a \approx \sqrt{p}$ and look at lines parallel to $x=0$, $y=0$, $x=y$ and $x = ay$, I don't know what happens. – David E Speyer Dec 4 '18 at 3:45

Let $$C>0$$ be any fixed number. Take $$p-3$$ horizontal lines and $$p-b$$ vertical lines where $$p\gg b\gg C$$. If we want to stay within $$2p+C-3$$ lines, we should be able to cover some $$3\times b$$ rectangular configuration by at most $$b+C$$ lines of any prescribed slopes $$a_1,\dots, a_{b+C}\ne 0$$. Notice that we have $$3b$$ points to cover and each line can cover at most $$3$$ points, so we can afford only $$3C$$ lines that cover $$2$$ points or fewer. Thus some $$b-2C$$ lines should pass through $$3$$ points.
Let $$x_1,x_2,\dots,x_b$$ be the base of our $$3\times b$$ configuration and $$u,v,w$$ be its "vertical side". Then for each slanted line coming through $$3$$ points, we have some triple $$i,j,k$$ such that $$(w-u)(x_j-x_i)=(v-u)(x_k-x_i) \tag {*}$$ and the slope of the corresponding line is determined by that triple. Notice also that those triples cover at least $$b-6C$$ indices $$1,\dots,b$$ (the indices not taken by the exceptional $$3C$$ lines). Thus we can choose $$\frac b3-2C$$ linearly independent equations of the type ($$*$$) (just take an equation including some index not used yet every time until you run out of them). There are some $$K(b)$$ possible arrangements of those equations and $$p^3$$ choices of $$u,v,w$$, so we see that we can have at most $$K(b)p^{3+\frac 23b+2C}$$ arrangements that are coverable by $$b+C$$ slanted lines in principle and all slopes (and even lines) except $$3C$$ are determined by $$x_j$$ and the ($$*$$)-equations up to the order. That results in the bound $$K(b)(b+C)!p^{3+\frac 23b+5C}$$ for the number of choices of $$b+C$$ slopes that can be used to cover any $$3\times b$$ configuration, which falls short of $$(p-1)^{b+C}$$ available choices if $$b\gg C$$ and $$p>p(b)$$.
If you do it carefully, you get the lower bound of the type $$N(p)\ge 2p+p^\alpha$$ for large $$p$$ with some $$\alpha\in(0,1)$$, but it is still only a rather pitiful improvement of the trivial lower bound $$2p-1$$, so I didn't try to be very precise in the estimates.