3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Douglas Zare Apr 27 '15 at 16:08
  • $\begingroup$ Also, the points $\{(0,0),(0,1),(1,0),(1,1)\}$ have $3$ even covers: $L_0, L_1, L_\infty$. $\endgroup$ – Douglas Zare Apr 27 '15 at 16:10
  • $\begingroup$ 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. $\endgroup$ – pxdnr Apr 27 '15 at 22:18
  • $\begingroup$ Also, thank you for the hyper-oval example. $\endgroup$ – pxdnr Apr 27 '15 at 22:27
3
$\begingroup$

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

Here are some examples achieving that bound: Hyperovals in subfields.

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)$.

$\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.