# An upper bound on the number of sets of parallel lines covering points in a finite plane?

Let $\mathbb{F}$ be a finite field of characteristic $2$. Let $L_m$ denote the set of lines in $\mathbb{F}^2$ with slope $m\in\mathbb{F}$, that is, all parallel lines of the form $y=mx+b$. Consider a subset $P$ of $n$ points in $\mathbb{F}^2$, then we call $L_m$ an even cover of $P$ if every line in $L_m$ contains an even number of points from $P$ (lines may contain no points).

Given an arbitrary set of $n$ points $P$, how many even covers are there of $P$?

We're looking for the sharpest possible bounds as a function of $n$. We've looked at small values of $n$, and so far there seems to be at most 2 even covers. If we change the requirement from containing an even number of points to containing at least 2 points, then we've found sets of points with more than two covers. Any ideas or references are very much welcome.

• What do you mean, "every point in $P$ is on a line in $L_m$?" Parallel lines partition the points so the condition seems meaningless. Are you looking for upper bounds on the number of even covers as a function of $n$? If you don't restrict the number of points, you can have sets with $|\mathbb{F}|+1 = q+1$ even covers. For example, take a hyper-oval in the projective plane. This has $q+1$ points and every line intersects it in $0$ or $2$ points. Delete a line not intersecting the hyper-oval to get a set with $q+1$ even covers in an affine plane. – Douglas Zare Apr 27 '15 at 16:08
• Also, the points $\{(0,0),(0,1),(1,0),(1,1)\}$ have $3$ even covers: $L_0, L_1, L_\infty$. – Douglas Zare Apr 27 '15 at 16:10
• I've updated the question: I've removed the meaningless condition on the cover, and we are looking for upper bounds as a function of $n$, in particular we're interesting in values of $n$ which are much smaller than $|\mathbb{F}|$. Furthermore, we're not including $L_\infty$, although that's not an important restriction. – pxdnr Apr 27 '15 at 22:18
• Also, thank you for the hyper-oval example. – pxdnr Apr 27 '15 at 22:27

If a set $S$ is evenly covered by lines in $n$ slopes, then $n \le |S|-1$ because through every point $p$, there are at most $|S|-1$ lines connecting $p$ to other points in the set, and any other slope of line would include a line intersecting $S$ in just $p$.
A hyperoval in the projective plane over a finite field $\mathbb{F}_q$ of characteristic $2$ is a set of $q+2$ points in the projective plane over $\mathbb{F}_q$ so that every line meets the set in $0$ or $2$ points. An example is $\lbrace(1,t,t^2)~\bigg|~t\in\mathbb{F}_q \rbrace \cup \lbrace(0,1,0)\rbrace \cup \lbrace(0,0,1)\rbrace$. For some $q \gt 8$ there are many non-isomorphic hyperovals.
There are $q+2 \choose 2$ lines out of $q^2+q+1$ that intersect the hyperoval in $2$ points. The remaining $q \choose 2$ lines do not intersect the hyperoval. The complement of a line disjoint from the hyperoval gives a set of $q+2$ points in the affine plane over $\mathbb{F}_q$ which intersects every line in $0$ or $2$ points. For example, if $q=2$, this is the whole plane.
Let $\mathbb{F}_{q'} \subset \mathbb{F}_q$. We can construct a hyperoval within the subplane $\lbrace (a,b)|a,b \in \mathbb{F}_{q'} \rbrace$ consisting of $q'+2$ points so that for every slope in $\mathbb{F}_{q'} \cup \lbrace \infty \rbrace$, the lines of that slope intersect the hyperoval in $0$ or $2$ points. If you don't like the vertical lines of slope $\infty$, then if $q' \lt q$, you can take an automorphism of the plane taking a slope in the complement $\mathbb{F}_q \setminus \mathbb{F}_{q'}$ to $\infty$, and this will take the hyperoval to a set evenly covered by $q'+1$ parallelism classes of finite slopes.
So, if $q=2^k$ then for every $d|k, d\lt k$ there are sets of $2^{d}+2$ points evenly covered by $2^{d}+1$ slopes. This includes $d=1$: $\lbrace (0,0), (1,0),(x,1),(x+1,1) \rbrace$ for some $x \in \mathbb{F}_q \setminus \lbrace 0,1 \rbrace$, which is evenly covered by the slopes $0$, $1/x$, and $1/(x+1)$.