Near the Top: Many Lines per Direction

When $r$ is close to $q$ it is convenient to think of the $q-r$ lines per direction that are omitted rather than the $r$ that are chosen. Write $s=q-r$.

5.1 Complements

Lemma 5.1. Let $\mathcal L$ be an $r$-fold configuration and $\mathcal L^c$ the set of the $s(q+1)$ affine lines not in $\mathcal L$, $s=q-r$. A point $P$ lies outside $U(\mathcal L)$ if and only if all $q+1$ lines through $P$ belong to $\mathcal L^c$. Hence

$$\kappa_{q-s}(q)=q^2-\tau_s(q),\qquad\tau_s(q):=\max\{|T|:T\subseteq AG(2,q)\text{ and every direction has at most }s\text{ lines meeting }T\}.$$

Proof. $P\notin U$ iff no line of $\mathcal L$ passes through $P$ iff every line through $P$ is omitted. Given $\mathcal L$, let $T=AG(2,q)\setminus U$; every line through a point of $T$ is omitted, so in each direction the lines meeting $T$ are among the $s$ omitted ones. Conversely, given $T$ with at most $s$ lines per direction meeting it, omit those lines together with enough further lines to make $s$ per direction; the resulting $\mathcal L$ has $T\cap U=\emptyset$, so $|U|\le q^2-|T|$. Minimising $|U|$ is therefore the same as maximising $|T|$. ∎

For $s=q-1$ this says $\kappa_1(q)=q^2-\tau_{q-1}(q)$, where $\tau_{q-1}(q)$ is the largest set missed by at least one line in every direction, i.e. the largest complement of a Kakeya set; the Blokhuis–Mazzocca theorem gives $\tau_{q-1}(q)=(q-1)^2/2$ for odd $q$ and $q(q-1)/2$ for even $q$. At the other end $\tau_1(q)=1$: if $T$ contains two points $P,Q$, then in every direction other than that of $PQ$ they lie on two distinct lines. The interesting question is where $\tau_s(q)$ stops being $s$.

5.2 Sets determining all directions

A set $T$ determines the direction $d$ if two points of $T$ lie on a common line of direction $d$. Let

$$D(q)=\min\{|T|:T\subseteq AG(2,q)\text{ determines all }q+1\text{ directions}\}.$$

Call a set $T$ $s$-valid if at most $s$ lines of every direction meet it, so that $\tau_s(q)$ is the largest size of an $s$-valid set.

Lemma 5.2. (a) $\tau_s(q)\ge s$ for $1\le s\le q$. (b) Every subset of an $s$-valid set is $s$-valid. (c) A set $T$ with $|T|=s+1$ is $s$-valid if and only if $T$ determines all directions.

Proof. (a) Take $s$ points on one line $M$: the direction of $M$ contributes one line, every other direction exactly $s$ lines. (b) is clear. (c) Since $|T|=s+1$, at most $s$ lines of direction $d$ meet $T$ iff two points of $T$ lie on a common line of direction $d$ iff $T$ determines $d$. ∎

Lemma 5.3. $\tau_s(q)\ge s+1$ if and only if $D(q)\le s+1$.

Proof. Suppose $\tau_s(q)\ge s+1$ and let $T$ be $s$-valid with $|T|\ge s+1$. By Lemma 5.2(b) any $(s+1)$-subset of $T$ is $s$-valid, and by 5.2(c) it determines all directions; so $D(q)\le s+1$. Conversely suppose $D(q)\le s+1$ and let $T_0$ be a determining set with $|T_0|=D(q)$. By Lemma 5.2(c), $T_0$ is met by at most $D(q)-1\le s$ lines in every direction. If $|T_0|=s+1$ we are done. Otherwise choose a line $M$ through two points of $T_0$ and let $T$ consist of $T_0$ together with $s+1-D(q)$ further points of $M$, which is possible since $M$ has $q\ge s+1$ points. In the direction of $M$ the lines meeting $T$ are those meeting $T_0$, at most $D(q)-1\le s$ of them. In any other direction each new point lies on a line of its own, so at most $(D(q)-1)+(s+1-D(q))=s$ lines meet $T$. Thus $T$ is $s$-valid with $|T|=s+1$. ∎

Theorem 5.4 (Theorem C). For $1\le s\le D(q)-2$, $\tau_s(q)=s$ and hence $\kappa_{q-s}(q)=q^2-s$. For $s=D(q)-1$, $\tau_s(q)\ge s+1$ and $\kappa_{q-s}(q)\le q^2-s-1$.

Proof. For $s\le D(q)-2$ we have $D(q)>s+1$, so $\tau_s(q)<s+1$ by Lemma 5.3, and $\tau_s(q)=s$ by Lemma 5.2(a); Lemma 5.1 gives $\kappa_{q-s}(q)=q^2-s$. For $s=D(q)-1$, Lemma 5.3 gives $\tau_s(q)\ge s+1$. ∎

5.3 A lower bound on $D(q)$

Proposition 5.5. $D(q)\ge t_0(q):=\min\{t:\binom t2\ge q+1\}$. Consequently $\kappa_{q-s}(q)=q^2-s$ whenever $s(s+1)<2(q+1)$, in particular for all $s\le\sqrt{2q}-1$.

Proof. A set of $t$ points determines at most $\binom t2$ directions, one for each pair, so a determining set has $\binom t2\ge q+1$ and $D(q)\ge t_0(q)$. If $s(s+1)<2(q+1)$ then $\binom{s+1}2<q+1$, so no $(s+1)$-set determines all directions, $D(q)\ge s+2$, and Theorem 5.4 applies. The last clause follows from $(\sqrt{2q}-1)\sqrt{2q}<2q<2(q+1)$. ∎

The bound $t_0(q)$ is $\lceil(1+\sqrt{8q+9})/2\rceil$; for $q=3,\dots,16$ it is $4,4,4,5,5,5,6,6,7$. A set attaining $D(q)=t_0(q)$ with $\binom{t_0}2=q+1$ exactly would have all its $\binom{t_0}2$ pair-directions distinct: no two of its joining lines parallel. Such sets exist for $q=5$ ($4$ points, $6$ directions) but, remarkably, not for $q=9$ ($5$ points, $10$ directions), as the next section shows.

5.4 Computing $D(q)$

$D(q)$ was computed by exhaustive search for $q\le16$ (Appendix A.4), using that the affine group is transitive on ordered pairs of points, so that a determining set may be assumed to contain $(0,0)$ and $(1,0)$. The results:

(Points are written $xy$; field elements of $\mathbb F_4,\mathbb F_8,\mathbb F_9,\mathbb F_{16}$ are encoded as integers as described in Appendix A.) The counting bound is attained except at $q=9$, where the search shows that no $5$-set of $AG(2,9)$ has ten pairwise non-parallel joining lines. I do not have a conceptual explanation of this; it would follow from a structural result on sets with no two parallel chords in $AG(2,9)$, and such sets ("no parallelograms and no trapezoids" in the language of the Euclidean problem) are a natural object of study in their own right.

Corollary 5.6. The following values are exact:

and in each case $\kappa_{q-s}(q)\le q^2-s-1$ for $s=D(q)-1$.

The exhaustive computations of Chapter 7 confirm these where they overlap ($q\le7$: $\kappa_4(7)=46=49-3$, $\kappa_3(5)=23$, $\kappa_2(4)=14$, $\kappa_1(3)=7$, all $=q^2-s$), and give $\kappa_3(7)=44=49-5$ for $s=4=D(7)-1$, so $\tau_4(7)=5=s+1$: the upper bound of Theorem 5.4 is attained there. For $q=8$, $s=4$, Theorem 5.4 gives $\kappa_4(8)\le59$ and Theorem A gives $\kappa_4(8)\ge58$; the search of Appendix A did not decide between them.

5.5 The general bound on $\tau_s(q)$

For completeness, the counting argument of Theorem A, run in the complement picture, gives the general inequality

$$\tau_s(q)\le\frac{qs}{q+1-s}\qquad(1\le s\le q),\tag{5.1}$$

which is equivalent to $\kappa_{q-s}(q)\ge\frac{q-s}{q-s+1}q(q+1)$. It is tight at $s=q-1$ for even $q$ (dual hyperovals) and at $s=1$, and gives $\tau_s(q)\le s$ iff $s^2\le q$, a weaker threshold than Proposition 5.5. I note it because its proof is instructive: for a valid $T$ with $|T|=t$, each direction has at most $s$ lines meeting $T$, and by convexity the number of pairs of $T$ on lines of that direction is at least $t^2/(2s)-t/2$; summing over $q+1$ directions and comparing with $\binom t2$ gives (5.1). The direction-determination argument replaces convexity by the observation that a valid $(s+1)$-set must determine every direction, which is sharper because it uses the integrality of the line counts.