6
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Fedor Petrov Nov 28 '18 at 21:21
  • $\begingroup$ @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$. $\endgroup$ – fedja Nov 29 '18 at 3:14
  • $\begingroup$ @fedja: Could you expand your remark (the "pretty hard to cover" statement) and, maybe, convert it to an answer? $\endgroup$ – Seva Dec 1 '18 at 19:53
  • $\begingroup$ @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. $\endgroup$ – fedja Dec 1 '18 at 22:23
  • $\begingroup$ @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. $\endgroup$ – David E Speyer Dec 4 '18 at 3:45
4
$\begingroup$

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.

$\endgroup$

Your Answer

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

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