1 Introduction
Introduced by Wills [Reference Wills35] in 1967, and then independently by Cusick [Reference Cusick9], the lonely runner conjecture (LRC) concerns the following problem. On a unit-length circular track one considers
$m$
runners who all start at the same place and at the same time, each runner having a constant speed, with speeds being pairwise distinct. We say that a runner is lonely if all the other runners are at a distance at least
$1/m$
from her. A well-known reformulation of the problem [Reference Bohman, Holzman and Kleitman6], provided below, states the problem in terms of integer speeds, with one of the runners having zero speed. Throughout, let
$\Vert x\Vert$
denote the distance from a real number
$x$
to the nearest integer.
Conjecture 1.1 (LRC).
Let
$D$
be a set of
$k$
positive integers. Then there exists
$t\in \mathbb{R}$
such that
$$\begin{eqnarray}\Vert t\cdot d\Vert \geqslant \frac{1}{k+1},\quad \text{for all }d\in D.\end{eqnarray}$$
At present, the problem is open for
$k\geqslant 7$
, that is, for eight or more runners. For
$k=1$
the conjecture is trivial, and the
$k=2$
case is resolved during the first lap of the slower non-stationary runner. The case
$k=3$
was solved by Betke and Wills [Reference Betke and Wills4] and Cusick [Reference Cusick9–Reference Cusick11] as a problem in diophantine approximation. Cusick and Pomerance [Reference Cusick and Pomerance12] established the conjecture for
$k=4$
by extending Cusick’s previous work with additional estimates on certain exponential sums, though their proof needed a computer check for certain cases. Later Biennia et al [Reference Biennia, Goddyn, Gvozdjak, Sebő and Tarsi5] presented a much simpler proof of the
$k=3,4$
cases, and additionally connected the lonely runner conjecture with a conjecture on flows in matroids. The case
$k=5$
was first solved by Bohman, Holzman and Kleitman [Reference Bohman, Holzman and Kleitman6], and then Renault [Reference Renault29] provided a shorter proof. Finally, Barajas and Serra [Reference Barajas and Serra3] settled the case
$k=6$
.
There has been recent progress for large values of
$k$
. For instance, Dubickas [Reference Dubickas16] employed the Lovász local lemma [Reference Alon and Spencer2] to establish the conjecture for certain lacunary sequences of speeds. For any set
$D$
of
$k$
non-zero integers, define
$$\begin{eqnarray}\unicode[STIX]{x1D6FF}_{k}(D):=\sup _{t\in \mathbb{R}/\mathbb{Z}}\min _{d\in D}\Vert dt\Vert ,\end{eqnarray}$$
and let
$\unicode[STIX]{x1D6FF}_{k}$
be the infimum over all such sets
$D$
. We note that Dirichlet’s approximation theorem in the form of [Reference Vaughan32, Lemma 2.1] yields
$\unicode[STIX]{x1D6FF}_{k}\leqslant 1/(k+1)$
, and the LRC states that
$\unicode[STIX]{x1D6FF}_{k}\geqslant 1/(k+1)$
. The union bound
$$\begin{eqnarray}\mathbb{P}_{t\in \mathbb{R}/\mathbb{Z}}\biggl(\Vert dt\Vert \geqslant \frac{1}{2k+\unicode[STIX]{x1D700}},~\forall d\in D\biggr)\geqslant 1-k\frac{2}{2k+\unicode[STIX]{x1D700}}>0\end{eqnarray}$$
implies that
$\unicode[STIX]{x1D6FF}_{k}\geqslant 1/2k$
. Until recently, previous work [Reference Chen7, Reference Chen and Cusick8, Reference Perarnau and Serra27] had only improved the denominator by an additive constant. Tao [Reference Tao30] showed that there exists an absolute constant
$c>0$
such that
$$\begin{eqnarray}\unicode[STIX]{x1D6FF}_{k}\geqslant \frac{1}{2k}+\frac{c\log k}{k^{2}(\log \log k)^{2}}\end{eqnarray}$$
for all sufficiently large
$k$
. In addition, he showed that it is enough to verify the conjecture for speeds at most
$k^{O(k^{2})}$
, and also that the conjecture holds when the speeds are all small.
Theorem 1.2 [Reference Tao30].
Let
$k\geqslant 1$
and suppose that
$\max _{d\in D}|d|\leqslant 1.2k$
. Then
$\unicode[STIX]{x1D6FF}_{k}(D)\geqslant 1/(k+1)$
.
Czerwiński and Grytczuk [Reference Czerwiński and Grytczuk14] proved that the conjecture holds provided one is allowed to make a runner invisible to the other runners.
Theorem 1.3 [Reference Czerwiński and Grytczuk14].
Let
$k$
and
$s$
be integers such that
$0\leqslant s<k$
. Then for every set
$D$
of
$k$
positive integers there exists a subset
$S\subseteq D$
of size
$k-s$
such that
$$\begin{eqnarray}\unicode[STIX]{x1D6FF}_{k-s}(S)\geqslant \frac{s+1}{2k}.\end{eqnarray}$$
Recently Perarnau and Serra [Reference Perarnau and Serra27] extended this result by showing that there exists a time when either a runner is lonely or four runners are “almost lonely”. Finally, Czerwiński [Reference Czerwiński13] confirmed the conjecture for a random set of positive integer speeds (see also [Reference Alon1]), establishing the inequality
$$\begin{eqnarray}\unicode[STIX]{x1D6FF}_{k}(D)\geqslant {\textstyle \frac{1}{2}}-\unicode[STIX]{x1D700}\end{eqnarray}$$
with high probability, for any
$\unicode[STIX]{x1D700}>0$
.
In this paper we formulate an analogue of the lonely runner problem in function fields, and prove results of a similar flavour to (1.1), Theorems 1.2 and 1.3. We shall see, however, that our methods are very different.
1.1 Function fields
The analogy between number fields and function fields [Reference van der Geer, Moonen and Schoof31] has a long and distinguished history, dating back at least to a famous 1882 paper by Weber and Dedekind [Reference Weber and Dedekind33]. A significant milestone was reached by Weil [Reference Weil34], who established the Riemann hypothesis for algebraic curves defined over finite fields, otherwise known as the “Riemann hypothesis for function fields”. Since then, this connection has been deeply investigated in many contexts, and function field models have provided a valuable testing ground for building intuition, making predictions and developing proof techniques [Reference Ellenberg, Venkatesh and Westerland17, Reference Entin18, Reference Ganguly and Ghosh20, Reference Katz and Sarnak23–Reference Liu and Wooley25].
Let
$q$
be a prime power, and let
$\mathbb{F}_{q}$
denote the field of
$q$
elements. We have the following analogy (see for instance [Reference Liu and Wooley25, §2]):
In order to measure loneliness, we require a notion of distance. For
$$\begin{eqnarray}\unicode[STIX]{x1D6FC}=\mathop{\sum }_{i=-\infty }^{n}x_{i}T^{i}\in \mathbb{F}_{q}((T^{-1})),\end{eqnarray}$$
let
$\text{ord}(\unicode[STIX]{x1D6FC})$
be the greatest integer
$i$
for which
$x_{i}\neq 0$
, and write
$\langle \unicode[STIX]{x1D6FC}\rangle =q^{\text{ord}(\unicode[STIX]{x1D6FC})}$
. We adopt the convention that
$\text{ord}(0)=-\infty$
and
$\langle 0\rangle =0$
. Our analogue of the unit track shall be the compact additive subgroup
$$\begin{eqnarray}\mathbb{T}=\{\unicode[STIX]{x1D6FC}\in \mathbb{K}_{\infty }:\langle \unicode[STIX]{x1D6FC}\rangle <1\}\end{eqnarray}$$
of
$\mathbb{K}_{\infty }$
, and the “norms” in
$\mathbb{T}$
take values in
$\{0\}\cup \{q^{-1},q^{-2},\ldots \}.$
Observe that any element
$\unicode[STIX]{x1D6FC}\in \mathbb{K}_{\infty }$
can be uniquely decomposed as
$$\begin{eqnarray}\unicode[STIX]{x1D6FC}=[\unicode[STIX]{x1D6FC}]+\Vert \unicode[STIX]{x1D6FC}\Vert ,\end{eqnarray}$$
where
$[\unicode[STIX]{x1D6FC}]\in \mathbb{F}_{q}[t]$
and
$\Vert \unicode[STIX]{x1D6FC}\Vert \in \mathbb{T}$
; this corresponds to decomposing an integer into its integer and fractional parts. For convenience, write
$$\begin{eqnarray}|\unicode[STIX]{x1D6FC}|:=\langle \Vert \unicode[STIX]{x1D6FC}\Vert \rangle ;\end{eqnarray}$$
this corresponds to the distance from a real number to the nearest integer.
By analogy with the notation from the real setting, we define the loneliness of a set
${\mathcal{F}}\subseteq \mathbb{F}_{q}[T]\setminus \{0\}$
by
$$\begin{eqnarray}\unicode[STIX]{x1D6FF}({\mathcal{F}}):=\sup _{\unicode[STIX]{x1D6FC}\in \mathbb{T}}\min _{f\in {\mathcal{F}}}|\unicode[STIX]{x1D6FC}f|.\end{eqnarray}$$
We formulate the lonely runner conjecture in the function field setting as follows.
Conjecture 1.4 (LRC in function fields).
Let
${\mathcal{F}}\subseteq \mathbb{F}_{q}[T]\setminus \{0\}$
be such that
$$\begin{eqnarray}1\leqslant |{\mathcal{F}}|<\frac{q^{k+1}-1}{q-1}.\end{eqnarray}$$
Then
$$\begin{eqnarray}\unicode[STIX]{x1D6FF}({\mathcal{F}})\geqslant q^{-k}.\end{eqnarray}$$
We shall assume throughout that all polynomials in
${\mathcal{F}}$
are monic. We lose nothing in doing so, for if
$c\in \mathbb{F}_{q}\setminus \{0\}$
and
$f\in \mathbb{F}_{q}[T]$
then
$|\unicode[STIX]{x1D6FC}f|=|\unicode[STIX]{x1D6FC}(cf)|$
.
1.2 Principal findings
The upper bound on
$|{\mathcal{F}}|$
is necessary, as illustrated by the following example. Let
$$\begin{eqnarray}{\mathcal{F}}_{k}:=\mathop{\bigcup }_{j=0}^{k}\{T^{j}+i_{j-1}T^{j-1}+\cdots +i_{1}T+i_{0}:i_{0},\ldots ,i_{j-1}\in \mathbb{F}_{q}\}.\end{eqnarray}$$
Note that
$|{\mathcal{F}}_{k}|=\sum _{j=0}^{k}q^{j}=(q^{k+1}-1)/(q-1)$
, and we claim that
$\unicode[STIX]{x1D6FF}({\mathcal{F}}_{k})\leqslant q^{-(k+1)}$
. Indeed, for
$\unicode[STIX]{x1D6FC}\in \mathbb{T}$
, the system of
$k$
linear equations in
$k+1$
variables
$$\begin{eqnarray}\langle \unicode[STIX]{x1D6FC}f\rangle [T^{-1}]=\langle \unicode[STIX]{x1D6FC}f\rangle [T^{-2}]=\cdots =\langle \unicode[STIX]{x1D6FC}f\rangle [T^{-k}]=0\end{eqnarray}$$
always has solutions in
$\mathbb{F}_{q}^{k+1}$
, where
$\langle g\rangle [T^{m}]$
denotes the coefficient of
$T^{m}$
in
$g$
. Therefore, for each
$\unicode[STIX]{x1D6FC}\in \mathbb{T}$
we can find
$f\in {\mathcal{F}}_{k}$
such that
$|\unicode[STIX]{x1D6FC}f|\leqslant q^{-(k+1)}$
, verifying our claim.
The lower bounds on the size threshold turn to be much more demanding, and we provide only partial answers in this paper. Our first result is that
$q^{k}$
is the correct order of magnitude. The theorem below confirms Conjecture 1.4 for
$k=1$
.
Theorem 1.5. Let
${\mathcal{F}}\subseteq \mathbb{F}_{q}[T]\setminus \{0\}$
be of size at most
$q^{k}$
. Then
$\unicode[STIX]{x1D6FF}({\mathcal{F}})\geqslant q^{-k}$
.
By essentially the same proof, one finds that maximal loneliness is always attained when the coefficient field is infinite. Precisely, if
$K$
is an infinite field and
${\mathcal{F}}$
is a finite subset of
$K[T]\setminus \{0\}$
then there exists
$$\begin{eqnarray}\unicode[STIX]{x1D6FC}=\mathop{\sum }_{i=1}^{\infty }x_{-i}T^{-i}\quad (x_{-i}\in K)\end{eqnarray}$$
such that
$(\unicode[STIX]{x1D6FC}f)[T^{-1}]\neq 0$
, for all
$f\in {\mathcal{F}}$
.
Our second result is that for
$k>1$
, Conjecture 1.4 holds provided that
$D:=\max _{f\in {\mathcal{F}}}\text{deg}(f)\leqslant q-O(1)$
, which can be thought of as an analogue of Theorem 1.2. In order to state the result we denote by
$N(m,q)$
the number of irreducible monic polynomials of degree
$m$
over
$\mathbb{F}_{q}$
. Gauss established the well-known formula
$$\begin{eqnarray}N(m,q)=\frac{1}{m}\mathop{\sum }_{d\mid m}\unicode[STIX]{x1D707}(d)q^{m/d},\end{eqnarray}$$
where
$\unicode[STIX]{x1D707}$
is the Möbius function. In particular,
$$\begin{eqnarray}N(m,q)\geqslant \frac{q^{m}-q^{m-1}-\cdots -q}{m}.\end{eqnarray}$$
Theorem 1.6 (Small degrees).
Let
$k>1$
, let
$q$
and
$D$
be such that
$$\begin{eqnarray}\frac{N(k+1,q)}{q^{k}+\cdots +q}>\biggl\lfloor\frac{D}{k+1}\biggr\rfloor.\end{eqnarray}$$
Then for any set of non-zero polynomials
${\mathcal{F}}$
of size at most
$$\begin{eqnarray}\frac{q^{k+1}-1}{q-1}-1\end{eqnarray}$$
whose degrees are at most
$D$
, we have
$\unicode[STIX]{x1D6FF}({\mathcal{F}})\geqslant q^{-k}$
.
Our final result is a non-trivial lower bound on the number of polynomials, irrespective of
$D$
. We are able to get close to halfway between Theorem 1.5 and Conjecture 1.4 in the case
$k=2$
.
Theorem 1.7 (Almost halfway there).
There exists a universal constant
$C$
such that the following holds. Let
${\mathcal{F}}$
be a set of non-zero polynomials such that
$$\begin{eqnarray}|{\mathcal{F}}|\leqslant q^{2}+0.4877q-C.\end{eqnarray}$$
Then
${\mathcal{F}}$
is of loneliness at least
$q^{-2}$
.
Carefully following the proof of Theorem 1.7, one could obtain
$C$
to be
$6$
.
1.3 Methods
The first step is to recast the question at hand as a covering problem. In the process we associate to each runner a partial circulant matrix; these are well studied [Reference Davis15] and, for instance, have important applications to compressed sensing [Reference Rauhut, Romberg and Tropp28, Reference Yin, Morgan, Yang and Zhang36]. Once viewed as a covering problem, Theorem 1.5 follows straightforwardly from the union bound. We prove Theorem 1.6 by exploiting the structure that irreducible polynomials bring to the covering problem. We argue that if the set of speeds lacks multiples of an irreducible polynomial of degree
$k+1$
, then one requires many runners to cover the missing structure.
Our proof of Theorem 1.7 is considerably more involved. It uses a very particular structure known as a sunflower; see for instance [Reference Jukna22]. Formally, a sunflower is a family of subsets for which there exists a core
$K$
such that for every pair of distinct subsets in the family, their intersection is precisely
$K$
. Large sunflowers whose core has generic dimension are very efficient at covering many vectors, and these play an indispensable role in our proof. Several authors have investigated upper bounds on the size of a sunflower-free family of sets, and this topic has recently received some attention [Reference Hegedüs21, Reference Naslund and Sawin26]. On the other hand, sunflowers have a fascinating structure, and there appear to be few instances in which this structure has been brought to bear on a separate problem. In the proof of Theorem 1.7 we are able to exploit the structure inherent in vector subspaces forming a sunflower. Sunflowers in this linear setting have been useful in coding theory; see [Reference Etzion and Raviv19] and the references within. We consider our use of sunflowers to be an interesting feature in its own right. We ultimately consider two cases, according to whether or not the set of speeds contains a large sunflower.
2 A covering problem
In this section we connect Conjecture 1.4 with a covering problem in which we cover a vector space by certain subspaces. We will be studying the lonely runner conjecture in this formulation for the remainder of the paper. We finish the section by proving Theorem 1.5.
We will use the following set-up for the rest of the paper, unless stated otherwise. For
$k,D\in \mathbb{N}$
let
${\mathcal{F}}$
be a set of non-zero polynomials in
$\mathbb{F}_{q}[T]$
of maximal degree at most
$D$
, and suppose we want to check whether
$\unicode[STIX]{x1D6FF}({\mathcal{F}})\geqslant q^{-k}$
. We can write any
$f\in {\mathcal{F}}$
as
$$\begin{eqnarray}f=a_{0}^{(f)}+a_{1}^{(f)}T+\cdots +a_{D}^{(f)}T^{D},\end{eqnarray}$$
for some non-zero vector
$(a_{0}^{(f)},\ldots ,a_{D}^{(f)})\in \mathbb{F}_{q}^{D+1}$
. Note that there is a one-to-one correspondence between vectors in
$\mathbb{F}_{q}^{D+k}$
and polynomials of degree at most
$D+k-1$
. To each
$f\in {\mathcal{F}}$
we associate a partial circulant matrix
$$\begin{eqnarray}\displaystyle A_{f} & = & \displaystyle \left[\begin{array}{@{}ccccccccc@{}}a_{0}^{(f)} & a_{1}^{(f)} & \ldots \, & a_{k-1}^{(f)} & \ldots \, & a_{D}^{(f)} & & & \\ & a_{0}^{(f)} & \ldots \, & a_{k-2}^{(f)} & \ldots \, & a_{D-1}^{(f)} & a_{D}^{(f)} & & \\ & & \ddots & \ldots & \ldots & \ldots & \ldots & \ddots & \\ & & & a_{0}^{(f)} & \ldots \, & a_{D-k+1}^{(f)} & a_{D-k+2}^{(f)} & \ldots \, & a_{D}^{(f)}\end{array}\right]\nonumber\\ \displaystyle & = & \displaystyle \left[\begin{array}{@{}c@{}}f\\ Tf\\ \vdots \\ T^{k-1}f\end{array}\right],\nonumber\end{eqnarray}$$
whose size is
$k\times (D+k)$
. We may assume that the time
$\unicode[STIX]{x1D6FC}$
takes the form
$$\begin{eqnarray}\unicode[STIX]{x1D6FC}=x_{-1}T^{-1}+x_{-2}T^{-2}+\cdots +x_{-(D+k)}T^{-(D+k)},\end{eqnarray}$$
since further terms do not affect whether or not
$|\unicode[STIX]{x1D6FC}f|\geqslant q^{-k}$
. We also associate to
$\unicode[STIX]{x1D6FC}$
the column vector
$$\begin{eqnarray}x=[x_{-1}~x_{-2}~\ldots ~x_{-(D+k)}]^{T}.\end{eqnarray}$$
Now
$|\unicode[STIX]{x1D6FC}f|\geqslant q^{-k}$
for all
$f\in {\mathcal{F}}$
is equivalent to
$$\begin{eqnarray}A_{f}x\neq 0,\quad \text{for all }f\in {\mathcal{F}}.\end{eqnarray}$$
It is easy to see that the vector subspace
$$\begin{eqnarray}\ker (A_{f})=\langle f,Tf,\ldots ,T^{k-1}f\rangle ^{\bot }\leqslant \mathbb{F}_{q}^{D+k}\end{eqnarray}$$
has codimension
$k$
. Defining
$\ker (f)=\ker (A_{f})$
, we obtain the following lemma.
Lemma 2.1 (Covering version).
A set
${\mathcal{F}}$
, comprising non-zero polynomials of degree at most
$D$
, is of loneliness at least
$q^{-k}$
if and only if
$$\begin{eqnarray}\mathop{\bigcup }_{f\in {\mathcal{F}}}\ker (f)\neq \mathbb{F}_{q}^{D+k}.\end{eqnarray}$$
This simple reformulation of the problem already provides us with the means to prove Theorem 1.5. One only needs to observe that each subspace contains the origin, and apply the union bound.
Proof of Theorem 1.5.
As mentioned, for each
$f\in {\mathcal{F}}$
, the subspace
$\ker (f)$
has codimension
$k$
in
$\mathbb{F}_{q}^{D+k}$
, meaning that each
$\ker (f)$
covers at most
$q^{D}-1$
non-zero vectors of
$\mathbb{F}_{q}^{D+k}$
. Therefore, by the union bound, assuming
$|{\mathcal{F}}|\leqslant q^{k}$
, the number of non-zero vectors covered by
$\bigcup _{f\in {\mathcal{F}}}\ker (f)$
is at most
$$\begin{eqnarray}\biggl|\mathop{\bigcup }_{f\in {\mathcal{F}}}\ker (f)\setminus \{0\}\biggr|\leqslant \mathop{\sum }_{f\in {\mathcal{F}}}|\text{ker}\,(f)\setminus \{0\}|\leqslant |{\mathcal{F}}|(q^{D}-1)\leqslant q^{D+k}-q^{k}<q^{D+k}-1,\end{eqnarray}$$
which gives
$\bigcup _{f\in {\mathcal{F}}}\ker (f)\neq \mathbb{F}_{q}^{D+k}$
, from which Lemma 2.1 yields
$\unicode[STIX]{x1D6FF}({\mathcal{F}})\geqslant q^{-k}$
.◻
3 Low-degree polynomials
In this section we prove Theorem 1.6. To do so, we exploit the fact that irreducible polynomials have a particular kernel structure. In particular, we use this to prove that every irreducible polynomial of degree
$k+1$
has to be observed in our set of speeds, at least as a factor. We formalize this in the following way.
Lemma 3.1 (Irreducible polynomials are factors).
Let
${\mathcal{F}}$
be a set of non-zero polynomials such that
$|{\mathcal{F}}|\leqslant (q^{k+1}-1)/(q-1)-1$
and
$\bigcup _{f\in {\mathcal{F}}}\ker (f)=\mathbb{F}_{q}^{D+k}$
. Then for each irreducible monic polynomial
$G_{k+1}$
of degree
$k+1$
, there exists
$f\in {\mathcal{F}}$
such that
$G_{k+1}\mid f$
.
Proof of Theorem 1.6, assuming Lemma 3.1.
For the sake of contradiction suppose that
$\unicode[STIX]{x1D6FF}({\mathcal{F}})<q^{-k}$
, or equivalently, by Lemma 2.1, that
$\bigcup _{f\in {\mathcal{F}}}\ker (f)=\mathbb{F}_{q}^{D+k}$
. In view of the assumption
$|{\mathcal{F}}|\leqslant (q^{k+1}-1)/(q-1)-1$
, Lemma 3.1 tells us that for each irreducible polynomial
$G_{k+1}$
of degree
$k+1$
we can find
$f\in {\mathcal{F}}$
such that
$G_{k+1}\mid f$
. Since the degree of each
$f\in {\mathcal{F}}$
is bounded by
$D$
, a single
$f$
can contain at most
$\lfloor D/(k+1)\rfloor$
such
$G_{k+1}$
as factors. Consequently, we need at least
$$\begin{eqnarray}\frac{N(k+1,q)}{\lfloor D/(k+1)\rfloor }\end{eqnarray}$$
polynomials in
${\mathcal{F}}$
. This yields
$$\begin{eqnarray}\frac{N(k+1,q)}{\lfloor D/(k+1)\rfloor }\leqslant |{\mathcal{F}}|\leqslant \frac{q^{k+1}-1}{q-1}-1=q^{k}+\cdots +q,\end{eqnarray}$$
contradicting our hypotheses. This completes the proof of Theorem 1.6, given Lemma 3.1. ◻
It remains to prove Lemma 3.1. The pivotal idea is that if an irreducible polynomial is not a divisor of some
$f\in {\mathcal{F}}$
, we can lower-bound the number of lines one needs to cover the missing (
$k+1$
)-dimensional space.
Lemma 3.2 (Covering with lines).
Let
$V$
be a vector space over
$\mathbb{F}_{q}$
such that
$\text{dim}(V)=k+1$
, and let
$V_{1},\ldots ,V_{R}\leqslant V$
be subspaces such that
$\text{dim}(V_{i})=1$
,
$1\leqslant i\leqslant R$
. If
$R\leqslant (q^{k+1}-1)/(q-1)-1$
then
$$\begin{eqnarray}V\neq \mathop{\bigcup }_{i=1}^{R}V_{i}.\end{eqnarray}$$
Proof. We need to cover
$q^{k+1}-1$
non-zero vectors with
$R$
lines through the origin. Note that each such line has at most
$q-1$
non-zero points, so the union bound gives
$$\begin{eqnarray}\left|\mathop{\bigcup }_{i=1}^{R}V_{i}\setminus \{0\}\right|\leqslant \mathop{\sum }_{i=1}^{R}|V_{i}\setminus \{0\}|\leqslant \biggl(\frac{q^{k+1}-1}{q-1}-1\biggr)(q-1)=q^{k+1}-q<q^{k+1}-1,\end{eqnarray}$$
concluding the proof of Lemma 3.2. ◻
Let
${\mathcal{P}}_{=m}$
denote the set of all monic polynomials of degree
$m$
, and write
${\mathcal{P}}_{{\leqslant}m}=\bigcup _{i=0}^{m}{\mathcal{P}}_{i}$
. Define
$$\begin{eqnarray}{\mathcal{P}}_{{\leqslant}m}{\mathcal{F}}=\{Pf:P\in {\mathcal{P}}_{{\leqslant}m},f\in {\mathcal{F}}\}.\end{eqnarray}$$
Recall that in our covering problem we seek to prove that
$\bigcup _{f\in {\mathcal{F}}}\ker (f)\neq \mathbb{F}_{q}^{D+k}$
. The following lemma provides a sufficient condition for this to hold.
Lemma 3.3. Let
$V\leqslant \mathbb{F}_{q}^{D+k}$
be such that
$\text{dim}(V^{\bot })=k+1$
, and let
${\mathcal{F}}$
be such that
$|{\mathcal{F}}|\leqslant (q^{k+1}-1)/(q-1)-1$
. If
${\mathcal{P}}_{{\leqslant}k-1}{\mathcal{F}}\cap V=\emptyset$
then
$$\begin{eqnarray}\mathop{\bigcup }_{f\in {\mathcal{F}}}\ker (f)\neq \mathbb{F}_{q}^{D+k}.\end{eqnarray}$$
Proof. Let
$V=\langle v_{1},\ldots ,v_{D-1}\rangle$
. The assumption
${\mathcal{P}}_{{\leqslant}k-1}{\mathcal{F}}\cap V=\emptyset$
implies that for each
$f\in {\mathcal{F}}$
the set
$B_{f}=\{v_{1},\ldots ,v_{D-1},f,Tf,\ldots ,T^{k-1}f\}$
is a linearly independent set of vectors in
$\mathbb{F}_{q}^{D+k}$
, and so
$$\begin{eqnarray}\text{dim}(\text{span}(B_{f})^{\bot })=1,\quad \text{for all }f\in {\mathcal{F}}.\end{eqnarray}$$
Lemma 3.2 finishes the proof, since
$|{\mathcal{F}}|\leqslant (q^{k+1}-1)/(q-1)-1$
. Indeed, our kernels fail to cover
$V^{\bot }$
so they cannot cover the entire space.◻
We conclude this section by proving Lemma 3.1.
Proof of Lemma 3.1.
Define
$V_{G_{k+1}}=\langle G_{k+1},TG_{k+1},\ldots ,T^{D-2}G_{k+1}\rangle$
. The assumption that
$\bigcup _{f\in {\mathcal{F}}}\ker (f)=\mathbb{F}_{q}^{D+k}$
, combined with Lemma 3.3, gives that there exist
$P\in {\mathcal{P}}_{{\leqslant}k-1}$
and
$f\in {\mathcal{F}}$
such that
$Pf\in V_{G_{k+1}}$
. Thus, there exists a polynomial
$p$
such that
$Pf=G_{k+1}p$
. Now the fact that
$G_{k+1}$
is an irreducible monic polynomial of degree
$k+1$
, coupled with the fact that
$P$
is of degree at most
$k-1$
, yields
$G_{k+1}\mid f$
.◻
4 Getting close to halfway when
$k=2$
In this section we prove Theorem 1.7, making use of the combinatorial notion of a sunflower. Although we do not use any of the existing results on sunflowers, we are confident that this language will help the reader to understand the main ideas, and that the questions arising are of independent interest.
Definition 4.1. A collection of sets
${\mathcal{S}}$
forms a sunflower if there exists a set
$K$
such that for each
$S_{1},S_{2}\in {\mathcal{S}}$
with
$S_{1}\neq S_{2}$
, we have
$$\begin{eqnarray}S_{1}\cap S_{2}=K.\end{eqnarray}$$
We say that
$K$
is the core and we call an element
$S\in {\mathcal{S}}$
a petal. If
${\mathcal{S}}$
is a collection of vector subspaces then we say that
${\mathcal{S}}$
is a sunflower of codimension
$d$
if
$K$
is of codimension
$d$
.
When considering loneliness
$\unicode[STIX]{x1D6FF}({\mathcal{F}})\geqslant q^{-2}$
, the ambient space is
$\mathbb{F}_{q}^{D+2}$
, and we will be interested in collections that are formed by the kernels of polynomials in
${\mathcal{F}}$
. A petal thus takes the form
$\ker (f)$
, for some polynomial
$f\in {\mathcal{F}}$
. The fact that we work with subspaces provides us with an additional tool: we have a notion of dimension, which forces the cardinality of a subspace to be a power of
$q$
. Observe that a “generic” intersection of two kernels has codimension
$4$
, being the null space of a rank-four matrix. In light of this, one might attempt to efficiently cover the space by starting with a large sunflower of codimension 4. This motivates us to consider a largest such sunflower, that is, one with the most petals.
We consider two cases: first, when there exists a large codimension-four sunflower in the set of speeds; and second, when all codimension-four sunflowers are small. We remark that in the former scenario it is possible to sharpen the bound provided here to get the full statement of Conjecture 1.4; see Proposition 4.6 and Remark 4.7 below. In this section, we prove a slightly weaker statement in order to make the paper easier to follow, as the real improvement needs to be made in the second case. We discuss the latter further in the appendix.
We divide the section into several parts, emphasizing the connection between sunflowers and the covering statement in Lemma 2.1. We think of
$\ker (f)$
,
$f\in {\mathcal{F}}$
, as being introduced in some order. In order to improve on the union bound, we shall consider the contribution of each polynomial with respect to previous ones, meaning the number of points that
$\ker (f)$
covers that were not already covered by the previously introduced polynomials.
The objective of our first lemma is to explain how the existence of a sunflower in the set of speeds reduces the contribution of the remaining polynomials. Moreover, it highlights the role played by the size of a largest sunflower.
Lemma 4.2 (After the sunflower).
Let
${\mathcal{S}}=\{f_{1},\ldots ,f_{n}\}$
be a sunflower of codimension
$4$
of maximal size in
${\mathcal{F}}$
, and let
$f\in {\mathcal{F}}\setminus {\mathcal{S}}$
. Then the contribution of
$f$
is bounded from above by
Proof. For ease of notation define
$K_{i}=\ker (f_{i})$
, for
$1\leqslant i\leqslant n$
, and write
$K_{f}=\ker (f)$
. Let
$K$
be the core of
${\mathcal{S}}$
, meaning that for all
$1\leqslant i<j\leqslant n$
we have
$K=K_{i}\cap K_{j}$
. The contribution from
$f$
is bounded above by
where
$V_{i}=K_{i}\cap K_{f}$
(
$1\leqslant i\leqslant n$
). Note that
$$\begin{eqnarray}\displaystyle |V_{1}\cup \cdots \cup V_{n}| & = & \displaystyle |V_{1}|+\mathop{\sum }_{j=2}^{n}|V_{j}\setminus (V_{1}\cup \cdots \cup V_{j-1})|\nonumber\\ \displaystyle & = & \displaystyle |V_{1}|+\mathop{\sum }_{j=2}^{n}(|V_{j}|-|(V_{j}\cap V_{1})\cup \cdots \cup (V_{j}\cap V_{j-1})|).\nonumber\end{eqnarray}$$
For
$1\leqslant i<j\leqslant n$
we have
$V_{j}\cap V_{i}=K\cap K_{f}$
, giving
Suppose first that
$|K\cap K_{f}|=q^{D-2}$
. In this case
$K\cap K_{f}=K$
, since
$K\cap K_{f}$
is a subspace of
$K$
and is of the same dimension. If each
$V_{j}$
is of size
$q^{D-2}$
then
$V_{j}=K$
for each
$j$
, so
$K_{f}$
is a petal, contradicting the maximality of
$n$
. Therefore there exists
$V_{j}$
properly containing
$K$
, so
$|V_{j}|=q^{D-1}$
for some
$j$
. Now (4.2) gives
since
$|V_{j}|\geqslant q^{D-2}$
for
$1\leqslant j\leqslant n$
.
If instead
$|K\cap K_{f}|\leqslant q^{D-3}$
, then (4.2) becomes
completing the proof. ◻
Examining the proof of Lemma 4.2, we see that there are two important subsets of polynomials in
${\mathcal{F}}$
:
∙ a codimension-four sunflower
${\mathcal{S}}=\{f_{1},\ldots ,f_{n}\}\subseteq {\mathcal{F}}$
of maximal size, with core
$K$
;∙ a set
${\mathcal{S}}^{\prime }\subseteq {\mathcal{F}}\setminus {\mathcal{S}}$
defined by (4.3)noting from the proof of Lemma 4.2 that if$$\begin{eqnarray}{\mathcal{S}}^{\prime }:=\{f\in {\mathcal{F}}\setminus {\mathcal{S}}:\ker (f)\cap K=K\},\end{eqnarray}$$
$f\in {\mathcal{S}}^{\prime }$
then there exists
$i\in \{1,2,\ldots ,n\}$
such that
$K$
is a proper subspace of
$\ker (f)\cap \ker (f_{i})$
.
We will use this notation for the rest of the section.
4.1 The structure of a sunflower
As discussed, Lemma 4.2 suggests that the size of a maximal codimension-four sunflower plays an important role. In this subsection we establish an upper bound on the size of a sunflower.
Lemma 4.3 (Maximal size of a sunflower).
Let
${\mathcal{S}}\subseteq {\mathcal{F}}$
be a sunflower of codimension
$4$
. Then
$$\begin{eqnarray}|{\mathcal{S}}|\leqslant 1+\frac{q^{2}+q}{2}.\end{eqnarray}$$
We prove the above lemma by exploiting the fact that the sunflowers in
${\mathcal{F}}$
come in two types, both easy to bound in size. Before stating that result, we prove that the core has a particular structure, a fact that will be used often in the remainder of this section.
Lemma 4.4 (The core).
Suppose that
${\mathcal{S}}$
is a sunflower. Define
$$\begin{eqnarray}K_{f,f^{\prime }}=\langle f,Tf,f^{\prime },Tf^{\prime }\rangle ^{\bot }.\end{eqnarray}$$
Then the core
$K$
satisfies
$K=K_{f,f^{\prime }}$
for all
$f,f^{\prime }\in {\mathcal{S}}$
,
$f\neq f^{\prime }$
.
Proof. By the definition of a sunflower, for all distinct
$f,f^{\prime }\in {\mathcal{S}}$
we have
$$\begin{eqnarray}K=\ker (f)\cap \ker (f^{\prime }).\end{eqnarray}$$
Note that
$\ker (f)\cap \ker (f^{\prime })$
corresponds to the kernel of the matrix with rows
$f,Tf,f^{\prime },Tf^{\prime },$
from which the claim follows.◻
We are ready to prove that there are only two types of sunflowers.
Proposition 4.5 (Structure of a sunflower).
For every sunflower
${\mathcal{S}}\subseteq {\mathcal{F}}$
one of the following holds.
(i) (Type I) There exists a polynomial
$P$
such that for all
$f\in {\mathcal{S}}$
, one can find a polynomial
$Q_{f}$
such that
$f=Q_{f}P$
, with
$Q_{f}$
being at most quadratic.(ii) (Type II) For all
$f,f^{\prime },f^{\prime \prime }\in {\mathcal{S}}$
we have
$f=\unicode[STIX]{x1D706}f^{\prime }+\unicode[STIX]{x1D707}f^{\prime \prime }$
, for some scalars
$\unicode[STIX]{x1D706},\unicode[STIX]{x1D707}\in \mathbb{F}_{q}$
.
Proof. Let
$f_{1}\neq f_{2}$
be arbitrary elements of
${\mathcal{S}}$
, and let
$P=(f_{1},f_{2})$
. Since each
$f\in {\mathcal{S}}$
forms a sunflower with
$f_{1},f_{2}$
, we have
$\langle f_{1},f_{2},Tf_{1},Tf_{2}\rangle ^{\bot }\subseteq K_{f}$
, and thus
$f\in \langle f_{1},f_{2},Tf_{1},Tf_{2}\rangle$
. Therefore we can find polynomials
$L_{1},L_{2}$
of degree at most 1 such that
$$\begin{eqnarray}f=L_{1}f_{1}+L_{2}f_{2}\equiv 0\hspace{0.6em}({\rm mod}\hspace{0.2em}P),\end{eqnarray}$$
which yields
$P\mid f$
for all
$f\in {\mathcal{F}}$
. Thus, defining
$g_{f}=f/P$
, note that the set
$$\begin{eqnarray}{\mathcal{S}}_{P}:=\{g_{f}:f\in {\mathcal{S}}\}\end{eqnarray}$$
is a well-defined set of polynomials. Moreover, it constitutes a sunflower, for if
$g_{f_{1}},g_{f_{2}}\in {\mathcal{S}}_{P}$
are distinct then
$$\begin{eqnarray}\displaystyle (K_{g_{f_{1}}}\cap K_{g_{f_{2}}})^{\bot } & = & \displaystyle \langle f_{1}/P,f_{2}/P,Tf_{1}/P,Tf_{2}/P\rangle \nonumber\\ \displaystyle & = & \displaystyle \{h/P:h\in \langle f_{1},f_{2},Tf_{1},Tf_{2}\rangle \}\nonumber\\ \displaystyle & = & \displaystyle \{h/P:h\in K^{\bot }\}.\nonumber\end{eqnarray}$$
Finally, note that for all distinct
$g,g^{\prime }\in {\mathcal{S}}_{P}$
we have
$(g,g^{\prime })=1$
.
Now let
$g,g^{\prime },g^{\prime \prime }\in {\mathcal{S}}_{P}$
be pairwise distinct. Since
${\mathcal{S}}_{P}$
is a sunflower, we can find polynomials
$L_{0},L_{1},L_{2},L_{2}^{\prime }$
of degree at most 1 such that
$$\begin{eqnarray}\displaystyle \begin{array}{@{}rcl@{}}g\ & =\ & L_{1}g^{\prime }+L_{2}g^{\prime \prime },\\ g^{\prime }\ & =\ & L_{0}g+L_{2}^{\prime }g^{\prime \prime },\end{array} & & \displaystyle\end{eqnarray}$$
giving
$$\begin{eqnarray}(1-L_{0}L_{1})g=(L_{1}L_{2}^{\prime }+L_{2})g^{\prime \prime }.\end{eqnarray}$$
Suppose first that
$L_{0}L_{1}\neq 1$
. Since
$g,g^{\prime \prime }\in {\mathcal{S}}_{P}$
are coprime, we see that they are at most quadratic, and by a similar argument
$\text{deg}(g^{\prime })\leqslant 2$
, so we are in the type I case.
Next, suppose instead that
$1-L_{0}L_{1}=L_{1}L_{2}^{\prime }+L_{2}=0$
, giving
$L_{0},L_{1}\in \mathbb{F}_{q}^{\times }$
. Since
${\mathcal{S}}_{P}$
is a sunflower, we can also find polynomials
$L_{0}^{\prime },L_{1}^{\prime }$
of degree at most 1 such that
$$\begin{eqnarray}g^{\prime \prime }=L_{0}^{\prime }g+L_{1}^{\prime }g^{\prime },\end{eqnarray}$$
which combined with (4.4) yields
$$\begin{eqnarray}(1-L_{0}^{\prime }L_{2})g=(L_{1}^{\prime }L_{2}+L_{1})g^{\prime }.\end{eqnarray}$$
If
$L_{0}^{\prime }L_{2}\neq 1$
we are again in the type I case. Otherwise
$L_{0}^{\prime },L_{2}\in \mathbb{F}_{q}^{\times }$
, and by symmetry we are in the type II case.◻
We are ready to bound the size of a sunflower.
Proof of Lemma 4.3.
Recall that we assumed without loss that all
$f\in {\mathcal{F}}$
are monic. If
${\mathcal{S}}$
is of type II, then counting the polynomials projectively yields
$$\begin{eqnarray}|{\mathcal{S}}|\leqslant |\mathbb{P}_{\mathbb{F}_{q}}^{1}|=\frac{q^{2}-1}{q-1}=q+1.\end{eqnarray}$$
Now suppose
${\mathcal{S}}$
is of type I, with
$P$
defined accordingly. We may assume that
$P$
is monic. Let
$K$
be the core of
${\mathcal{S}}$
. Then
$K$
contains the codimension-four subspace
$\{PC:\text{deg}\hspace{2.22198pt}C\leqslant 3\}^{\bot }$
, and so
$$\begin{eqnarray}K=\{PC:\text{deg}\hspace{2.22198pt}C\leqslant 3\}^{\bot }.\end{eqnarray}$$
For each pair
$f\neq f^{\prime }\in {\mathcal{S}}$
, we now have
$$\begin{eqnarray}\langle f,Tf,f^{\prime },Tf^{\prime }\rangle =\{PC:\text{deg}\hspace{2.22198pt}C\leqslant 3\}.\end{eqnarray}$$
Note that
$\{f/P:f\in {\mathcal{S}}\}$
is a set of monic polynomials of degree at most 2. Fix an ordering
$\unicode[STIX]{x1D706}_{1},\ldots ,\unicode[STIX]{x1D706}_{q}$
of
$\mathbb{F}_{q}$
and consider the following colouring of the set of monic polynomials of degree at most 2:
∙ the polynomial 1 has its own colour
$c$
;∙ each irreducible quadratic
$Q$
has its own colour
$c_{Q}$
;∙ for
$1\leqslant i\leqslant q$
, multiples of
$T-\unicode[STIX]{x1D706}_{i}$
, but not of
$T-\unicode[STIX]{x1D706}_{j}$
for
$j<i$
, have colour
$c_{i}$
.
This induces a colouring of
${\mathcal{S}}$
in the obvious way. Observe from (4.5) that distinct
$f$
and
$f^{\prime }$
satisfy
$\gcd (f,f^{\prime })=P$
. Therefore the sunflower cannot contain two polynomials of the same colour, so the total number satisfies
$$\begin{eqnarray}|{\mathcal{S}}|\leqslant 1+\frac{q^{2}-q}{2}+q,\end{eqnarray}$$
since the number of monic irreducible quadratics is
${\textstyle \frac{1}{2}}(q^{2}-q)$
.◻
4.2 The case when there exists a large sunflower
Here we consider the case in which there is a large codimension-four sunflower in the set of speeds, that is, a sunflower of size
$n\geqslant q+1$
. In this case, we see from Lemma 4.2 that all but
$n$
polynomials cover at most
$q^{D}-q^{D-1}$
new points. This gives a non-trivial bound on the number of polynomials needed.
Proposition 4.6 (Large sunflower implies halfway).
Let
${\mathcal{F}}$
be of loneliness at most
$q^{-3}$
. If there exists a sunflower of codimension
$4$
and size at least
$q+1$
, then
$$\begin{eqnarray}|{\mathcal{F}}|\geqslant q^{2}+\frac{q+1}{2}.\end{eqnarray}$$
Remark 4.7. In the large-sunflower case, one can work harder to establish the sharp inequality
$|{\mathcal{F}}|\geqslant q^{2}+q+1$
. To ease the exposition, we presently only prove a weaker result that corresponds to the bound we obtain in the case when all sunflowers are small. We provide, in the appendix, a proof of the inequality
$|{\mathcal{F}}|\geqslant q^{2}+q+1$
, assuming the existence of a sunflower of codimension 4 and size at least
$q+2$
, and that
$q\geqslant 8$
.
Proof. By Lemma 2.1 we see that
$\bigcup _{f\in {\mathcal{F}}}\ker (f)=\mathbb{F}_{q}^{D+2}$
. Let
${\mathcal{S}}$
be a codimension-four sunflower of maximal size, and let
$n=|{\mathcal{S}}|$
. Since
$n\geqslant q+1$
, we have
$$\begin{eqnarray}\max \{q^{D}-q^{D-1},~q^{D}-nq^{D-2}+(n-1)q^{D-3}\}=q^{D}-q^{D-1}.\end{eqnarray}$$
Defining
$R=|{\mathcal{F}}|$
and using Lemma 4.2, we get
$$\begin{eqnarray}\displaystyle q^{D+2} & = & \displaystyle |\mathbb{F}_{q}^{D+2}|=\biggl|\mathop{\bigcup }_{f\in {\mathcal{F}}}\ker (f)\biggr|\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \biggl|\mathop{\bigcup }_{f^{\prime }\in {\mathcal{S}}}\ker (f^{\prime })\biggr|+\mathop{\sum }_{f\in {\mathcal{F}}\setminus {\mathcal{S}}}\biggl|\text{ker}(f)\backslash \mathop{\bigcup }_{f^{\prime }\in {\mathcal{S}}}\ker (f^{\prime })\biggr|\nonumber\\ \displaystyle & {\leqslant} & \displaystyle (q^{D}+(n-1)(q^{D}-q^{D-2}))+(R-n)(q^{D}-q^{D-1}).\nonumber\end{eqnarray}$$
Expanding the right-hand side gives
$$\begin{eqnarray}R\geqslant q^{2}+q+\frac{q+1-n}{q},\end{eqnarray}$$
which together with Lemma 4.3 yields
4.3 The case when all sunflowers are small
Here we discuss the remaining case, when all codimension-four sunflowers have at most
$q$
petals. This turns out to be much more demanding, as the bound (4.1) becomes less powerful. In what follows we are able to improve on (4.1) in this case, by showing that there are many distinct pairwise intersections. In doing so we have to increase the influence of threefold intersections, and thus are not able to establish Conjecture 1.4 in full. However, the aforementioned improvement of (4.1) yields a significant gain over Theorem 1.5 in the case
$k=2$
.
Proposition 4.8 (Small sunflowers imply almost halfway).
Let
${\mathcal{F}}$
be such that all sunflowers in
${\mathcal{F}}$
of codimension
$4$
are of size at most
$q$
. If
${\mathcal{F}}$
is of loneliness at most
$q^{-3}$
, then there exists a universal constant
$C\in \mathbb{R}$
such that
$|{\mathcal{F}}|\geqslant q^{2}+0.4877q-C$
.
The rest of the paper will be devoted to the proof of this proposition. By Lemma 2.1, we have that loneliness at most
$q^{-3}$
implies
$\bigcup _{f\in {\mathcal{F}}}\ker (f)=\mathbb{F}_{q}^{D+2}$
. Define
$R=|{\mathcal{F}}|$
, and let
$n\leqslant q$
be the size of a maximal codimension-four sunflower
${\mathcal{S}}$
in
${\mathcal{F}}$
. We order the runners
$f_{1},f_{2},\ldots ,f_{R}$
in such a way that the twofold intersections all have codimension 4, until the change point, after which all the contributions are at most
$q^{D}-q^{D-1}$
.
As in the proof of Proposition 4.6, we bound the contribution from the first
$n$
runners (those that are in
${\mathcal{S}}$
) by a total of
$q^{D}+(n-1)(q^{D}-q^{D-2})$
, and the next
$(n-1)^{2}$
runners by
$q^{D}-nq^{D-2}+(n-1)q^{D-3}$
each, using Lemma 4.2. We call this the initial phase.
Next we consider runner
$m>n(n-1)+1$
. Using the same notation as in the proof of Lemma 4.2, namely that
$K_{i}=\ker (f_{i})$
and
$V_{i}=K_{i}\cap K_{m}$
, the covering contribution of
$f_{m}$
is
$$\begin{eqnarray}q^{D}-|V_{1}\cup \cdots \cup V_{m-1}|.\end{eqnarray}$$
As mentioned in the paragraph at the beginning of this case, the main idea is that there exist sufficiently many distinct twofold intersections.
Claim 1. Let
$t\geqslant 2$
be an integer, and assume that at
$m$
we have not yet reached the change point. Then there are at least
$t$
distinct sets among
$V_{1},\ldots ,V_{m-1}$
, provided that
$$\begin{eqnarray}m-1>(t-1)(n-1).\end{eqnarray}$$
Moreover, the sets
$V_{1},\ldots ,V_{n}$
are distinct, and the core
$K$
of
${\mathcal{S}}$
satisfies
$$\begin{eqnarray}|K\cap K_{m}|\leqslant q^{D-3}.\end{eqnarray}$$
Proof. Since we have not passed the change point, all of the
$V_{i}$
have codimension
$4$
. If
$V_{i}=V_{j}$
, then
$K_{i},K_{j},K_{m}$
form a sunflower of codimension 4, as
$K_{i}\cap K_{j}\subseteq V_{i}=V_{j}$
. Since
$n$
is the maximum size of a sunflower, we see that for each
$V_{i}$
there can be at most
$n-1$
indices
$j\in \{1,2,\ldots ,m-1\}$
such that
$V_{i}=V_{j}$
. In view of inequality (4.6), the pigeonhole principle ensures that there are at least
$t$
distinct sets among
$V_{1},\ldots ,V_{m-1}$
.
For the second part, assume for a contradiction that for some
$1\leqslant i<j\leqslant n$
we have
$V_{i}=V_{j}$
. Then the core
$K$
of
${\mathcal{S}}$
satisfies
$$\begin{eqnarray}K\cap K_{m}=V_{i}\cap V_{j}=V_{i}=V_{j},\end{eqnarray}$$
implying that
$K\cap K_{m}$
has codimension
$4$
. Now
$K\cap K_{m}=K$
, so by the definition of
${\mathcal{S}}^{\prime }$
following Lemma 4.2, we have that
$f_{m}\in {\mathcal{S}}^{\prime }$
. However, as discussed following that definition, this implies that there exists
$i\in \{1,2,\ldots ,n\}$
such that
$K$
is a proper subspace of
$V_{i}$
, contradicting the assumption that we have not passed the change point. Therefore the sets
$V_{1},\ldots ,V_{n}$
are pairwise distinct, and so
$|K\cap K_{m}|\leqslant q^{D-3}$
.◻
Claim 2. The next
$(n-1)(q-n)$
runners after the initial phase contribute a total of at most
$$\begin{eqnarray}(n-1)\mathop{\sum }_{t=n+1}^{q}\biggl(q^{D}-tq^{D-2}+\biggl[\binom{t}{2}-\binom{n-1}{2}\biggr]q^{D-3}\biggr).\end{eqnarray}$$
Proof. Consider runner
$m>n(n-1)+1$
, and suppose for the time being that this process precedes the change point. If
$m$
is among the first
$n-1$
runners after the initial phase, we may assume, by Claim 1, that
$V_{1},\ldots ,V_{t}$
are distinct with
$t=n+1$
. In this case the contribution of runner
$m$
is at most
$$\begin{eqnarray}q^{D}-\mathop{\sum }_{j=1}^{t}|V_{j}|+(n-1)|K\cap K_{m}|+\mathop{\sum }_{j=n+1}^{t}|V_{j}\cap (V_{1}\cup \cdots \cup V_{j-1})|,\end{eqnarray}$$
since
$V_{i}\cap V_{j}=K\cap K_{m}$
for all
$1\leqslant i<j\leqslant n$
. Note that for distinct
$V_{i}$
and
$V_{j}$
the codimension of
$V_{i}\cap V_{j}$
is at least 5, so the quantity in (4.8) is bounded from above by
$$\begin{eqnarray}\displaystyle & & \displaystyle q^{D}-tq^{D-2}+(n-1)q^{D-3}+q^{D-3}\mathop{\sum }_{j=n+1}^{t}(j-1)\nonumber\\ \displaystyle & & \displaystyle \qquad =q^{D}-tq^{D-2}+\biggl[\binom{t}{2}-\binom{n-1}{2}\biggr]q^{D-3}.\nonumber\end{eqnarray}$$
The contribution from the next
$n-1$
runners is the same, but with
$t=n+2$
, and so on. To conclude, observe that the result remains valid even if we cross the change point, as the above bounds on the individual contributions exceed
$q^{D}-q^{D-1}$
.◻
Now suppose we are in the final stage, meaning that
$$\begin{eqnarray}m>q(n-1)+1.\end{eqnarray}$$
Then we may apply Claim 1 with
$t=q$
. Expression (4.7) in Claim 2 has a minimum at
$t=q+{\textstyle \frac{1}{2}}$
, so there is nothing to be gained from choosing a larger value of
$t$
. Therefore the contribution of each runner in the final stage is bounded by
$$\begin{eqnarray}q^{D}-\frac{q^{D-1}+q^{D-2}}{2}-\binom{n-1}{2}q^{D-3},\end{eqnarray}$$
which holds irrespective of whether or not we have crossed the change point.
Combining everything, we find that
$$\begin{eqnarray}q^{D+2}=|\mathbb{F}_{q}^{D+2}|=\biggl|\mathop{\bigcup }_{i=1}^{R}K_{i}\biggr|\leqslant S_{1}+S_{2}+S_{3},\end{eqnarray}$$
where
$$\begin{eqnarray}S_{1}=q^{D}+(n-1)(q^{D}-q^{D-2})+(n-1)^{2}(q^{D}-nq^{D-2}+(n-1)q^{D-3})\end{eqnarray}$$
comes from the initial phase,
$$\begin{eqnarray}S_{2}=(n-1)\mathop{\sum }_{t=n+1}^{q}\left(q^{D}-tq^{D-2}+\biggl[\binom{t}{2}-\binom{n-1}{2}\biggr]q^{D-3}\right)\end{eqnarray}$$
comes from Claim 2, and
$$\begin{eqnarray}S_{3}=(R-1-q(n-1))\biggl(q^{D}-\frac{q^{D-1}+q^{D-2}}{2}-\binom{n-1}{2}q^{D-3}\biggr)\end{eqnarray}$$
comes from the final stage, using (4.9) for these final polynomials.
We may assume without loss that
$R=O(q^{2})$
. Simplifying the right-hand side of (4.10), dividing by
$q^{D-3}$
, and then grouping together all the summands that are
$O(q^{3})$
gives
$$\begin{eqnarray}\displaystyle R\biggl(q^{3}-\frac{q^{2}+n^{2}}{2}\biggr) & {\geqslant} & \displaystyle q^{5}+n^{3}q-\frac{1}{2}nq^{3}-\frac{1}{2}n^{4}\nonumber\\ \displaystyle & & \displaystyle +\,n\mathop{\sum }_{t=n+1}^{q}\biggl(tq-\binom{t}{2}\biggr)-C_{1}q^{3},\nonumber\end{eqnarray}$$
since
$n\leqslant q$
. Note that
$$\begin{eqnarray}\displaystyle \biggl(q+\frac{1}{2}\biggr)\mathop{\sum }_{t=n+1}^{q}t-\frac{1}{2}\mathop{\sum }_{t=n+1}^{q}t^{2}=q\frac{q^{2}-n^{2}}{2}+\frac{n^{3}-q^{3}}{6}+O(q^{2}), & & \displaystyle \nonumber\end{eqnarray}$$
which yields
$$\begin{eqnarray}\displaystyle R\biggl(q^{3}-\frac{q^{2}+n^{2}}{2}\biggr) & {\geqslant} & \displaystyle q^{2}\biggl(q^{3}-\frac{q^{2}+n^{2}}{2}\biggr)\nonumber\\ \displaystyle & & \displaystyle -\,\frac{2n^{4}-3n^{3}q-3n^{2}q^{2}+nq^{3}-3q^{4}}{6}-C_{2}q^{3}.\nonumber\end{eqnarray}$$
Determining
$\unicode[STIX]{x1D706}=n/q\in [0,1]$
numerically to maximize
$$\begin{eqnarray}\frac{2n^{4}-3n^{3}q-3n^{2}q^{2}+nq^{3}}{q^{4}}=2\unicode[STIX]{x1D706}^{4}-3\unicode[STIX]{x1D706}^{3}-3\unicode[STIX]{x1D706}^{2}+\unicode[STIX]{x1D706},\end{eqnarray}$$
we see that
$$\begin{eqnarray}R\biggl(q^{3}-\frac{q^{2}+n^{2}}{2}\biggr)\geqslant q^{2}\biggl(q^{3}-\frac{q^{2}+n^{2}}{2}\biggr)+0.4877q^{4}-C_{2}q^{3},\end{eqnarray}$$
giving
$$\begin{eqnarray}R\geqslant q^{2}+0.4877q-C.\end{eqnarray}$$
This completes the proof of Proposition 4.8.
Acknowledgements
The first named author was supported by EPSRC Programme Grant EP/J018260/1 at the University of York, and by the National Science Foundation under Grant No. DMS-1440140 while in residence at the Mathematical Sciences Research Institute in Berkeley, California, during the Spring 2017 semester. The second named author was supported by the School of Mathematics at the University of Bristol. This work began when the authors were graduate students together at the University of Bristol, and forms part of the second named author’s dissertation. We thank Julia Wolf and Trevor Wooley for their enthusiastic guidance and unwavering support. In particular, we are grateful to the latter for suggesting the project. Thanks to Tom Bloom and the rest of the HARICOT members for useful discussions. Finally, we are grateful to the anonymous referees for their feedback.
A. Appendix. Large sunflowers
Here we establish the following strong form of Proposition 4.6, as promised in Remark 4.7.
Proposition A.1. Let
${\mathcal{F}}$
be of loneliness at most
$q^{-3}$
. If
$q\geqslant 8$
and there exists a sunflower of codimension
$4$
and size at least
$q+2$
, then
$$\begin{eqnarray}|{\mathcal{F}}|\geqslant q^{2}+q+1.\end{eqnarray}$$
We start by recalling the proof of Lemma 4.2 and, in particular, the definitions of
${\mathcal{S}}$
and
${\mathcal{S}}^{\prime }$
, which we will use for the rest of this appendix. Let
${\mathcal{S}}$
be a sunflower of codimension 4 that is of maximal size in
${\mathcal{F}}$
, denote its core by
$K$
, and define
${\mathcal{S}}^{\prime }$
by (4.3). Put
$$\begin{eqnarray}n:=|{\mathcal{S}}|,\qquad k:=|{\mathcal{S}}^{\prime }|,\end{eqnarray}$$
observing that
$n\geqslant q+2$
. We order the polynomials in
${\mathcal{F}}$
so that
$$\begin{eqnarray}{\mathcal{S}}=\{f_{1},\ldots ,f_{n}\},\qquad {\mathcal{S}}^{\prime }=\{f_{n+1},\ldots ,f_{n+k}\},\end{eqnarray}$$
and define
${\mathcal{S}}^{\prime \prime }:={\mathcal{F}}\setminus ({\mathcal{S}}\cup {\mathcal{S}}^{\prime })$
. Lemma 4.2 and its proof imply that for each
$f\in {\mathcal{S}}^{\prime }$
we have
and for each
$f\in {\mathcal{S}}^{\prime \prime }$
we have
Our strategy is as follows. As before, we consider the covering problem arising from Lemma 2.1. We first show that in order for
$\bigcup _{f\in {\mathcal{F}}}\ker (f)=\mathbb{F}_{q}^{D+2}$
to hold when there exists a large sunflower in the set of speeds, we need both
$n$
and
$k$
to be close to maximal. Moreover, we prove that
${\mathcal{S}}$
and
${\mathcal{S}}^{\prime }$
are “closely connected”: loosely speaking, the sunflower
${\mathcal{S}}$
should be thought of as comprising almost all irreducible polynomials of degree at most
$2$
, and
${\mathcal{S}}^{\prime }$
comprising almost all reducible quadratic polynomials. Then
${\mathcal{S}}^{\prime \prime }$
has to include any remaining quadratics; thus,
${\mathcal{F}}$
has to look like the example in (1.2), up to multiplication by a polynomial.
Lemma A.2 (
${\mathcal{S}}\cup {\mathcal{S}}^{\prime }$
is large).
Let
${\mathcal{F}}$
be of loneliness at most
$q^{-3}$
and let
${\mathcal{S}}$
be a sunflower of codimension
$4$
that is of maximal size. If
$|{\mathcal{F}}|\leqslant q^{2}+q$
and
$|{\mathcal{S}}|\geqslant q+2$
, then for
${\mathcal{S}}^{\prime }$
defined as above we have
$|{\mathcal{S}}|+|{\mathcal{S}}^{\prime }|\geqslant q^{2}.$
Proof. Recall the definitions of
$n$
and
$k$
, and let
$r_{n},r_{k}\in \mathbb{R}$
be such that
$$\begin{eqnarray}n=|{\mathcal{S}}|={\textstyle \frac{1}{2}}q^{2}+r_{n},\qquad k=|{\mathcal{S}}^{\prime }|={\textstyle \frac{1}{2}}q^{2}+r_{k}.\end{eqnarray}$$
Then the assumption that
${\mathcal{F}}$
is of loneliness at most
$q^{-3}$
, combined with Lemma 2.1 and the above discussion, yields
$$\begin{eqnarray}\displaystyle \hspace{-7.0pt}q^{D+2} & {\leqslant} & \displaystyle \underbrace{\biggl(q^{D}+\biggl(\frac{q^{2}}{2}+r_{n}-1\biggr)(q^{D}-q^{D-2})\biggr)}_{=S_{1}}+\underbrace{\biggl(\frac{q^{2}}{2}+r_{k}\biggr)(q^{D}-q^{D-1})}_{=S_{2}}\nonumber\\ \displaystyle & & \displaystyle +\,\underbrace{(q-r_{n}-r_{k})\biggl(\frac{1}{2}q^{D}-r_{n}q^{D-2}+\frac{1}{2}q^{D-1}+(r_{n}-1)q^{D-3}\biggr)\!}_{=S_{3}}.\quad ~\end{eqnarray}$$
Here
$S_{1},S_{2}$
and
$S_{3}$
are upper bounds for the covering contributions of
${\mathcal{S}}$
,
${\mathcal{S}}^{\prime }$
and
${\mathcal{S}}^{\prime \prime }$
, respectively. We compute that
$$\begin{eqnarray}\displaystyle S_{1}+S_{2}+S_{3} & = & \displaystyle q^{D+2}+(r_{n}+r_{k})q^{D-3}({\textstyle \frac{1}{2}}q^{3}-{\textstyle \frac{3}{2}}q^{2}+r_{n}q-(r_{n}-1))\nonumber\\ \displaystyle & = & \displaystyle q^{D+2}+(r_{n}+r_{k})q^{D-3}(q-1)(n-(q+1)).\end{eqnarray}$$
Since
$n>q+1$
, we deduce from (A.2) and (A.3) that
$r_{n}+r_{k}\geqslant 0$
, completing the proof.◻
In the course of the proof of Lemma 4.3, we showed that any type II sunflower (in the sense of Proposition 4.5) has size at most
$q+1$
. As
$n>q+1$
, the sunflower
${\mathcal{S}}$
must therefore be of type I. In other words, there exist a polynomial
$P$
and at most quadratic polynomials
$Q_{1},\ldots ,Q_{n}$
such that
$f_{i}=Q_{i}P$
, for all
$i\in \{1,2,\ldots ,n\}$
. We now show that
${\mathcal{S}}^{\prime }$
has the same structure, with the additional information that most of the polynomials involved are reducible quadratics.
Proposition A.3 (
${\mathcal{S}}^{\prime }$
is an extension of
${\mathcal{S}}$
).
For each
$f\in {\mathcal{S}}^{\prime }$
, there exists a polynomial
$Q_{f}$
, at most quadratic, such that
$f=PQ_{f}$
. Moreover, if
$Q_{f}$
is of degree
$2$
, then
$Q_{f}$
is reducible.
Proof. First we prove that
$f=PQ_{f}$
for some polynomial
$Q_{f}$
of degree at most 2. The way that
${\mathcal{S}}^{\prime }$
is constructed implies that
$K\cap \ker (f)=K$
. Hence we can find
$L_{1},L_{1}^{\prime },L_{2},L_{2}^{\prime }$
, at most linear, such that
$$\begin{eqnarray}\displaystyle f & = & \displaystyle L_{1}f_{1}+L_{2}f_{2}=P(L_{1}Q_{1}+L_{2}Q_{2}),\nonumber\\ \displaystyle Tf & = & \displaystyle L_{1}^{\prime }f_{1}+L_{2}^{\prime }f_{2}=P(L_{1}^{\prime }Q_{1}+L_{2}^{\prime }Q_{2}).\nonumber\end{eqnarray}$$
The first equation gives
$P\mid f$
, and the second implies that
$\text{deg}(f)\leqslant \text{deg}(P)+2$
, which combine to give the existence of an at most quadratic
$Q_{f}$
such that
$f=PQ_{f}$
.
Now suppose that
$Q_{f}$
is of degree 2. Since
$f\in {\mathcal{S}}^{\prime }$
, we can find
$i\in \{1,2,\ldots ,n\}$
such that
$|\text{ker}(f)\cap \ker (f_{i})|=q^{D-1}$
. Therefore, there exist polynomials
$L$
and
$L_{i}$
, at most linear, such that
$$\begin{eqnarray}LPQ_{f}=Lf=L_{i}f_{i}=L_{i}PQ_{i}.\end{eqnarray}$$
Observe that
$Q_{f}$
being an irreducible quadratic would imply
$f=f_{i}$
. Therefore
$Q_{f}$
must instead be reducible.◻
As an immediate consequence we obtain
$|{\mathcal{S}}^{\prime }|\leqslant \frac{1}{2}(q^{2}+3q+2)$
. The aforementioned upper bounds on
$|{\mathcal{S}}|$
and
$|{\mathcal{S}}^{\prime }|$
, together with Lemma A.2, imply that both
$|{\mathcal{S}}|$
and
$|{\mathcal{S}}^{\prime }|$
are close to maximal. Moreover, Propositions 4.5, A.3, and Lemma A.2 imply that at least
$q^{2}$
polynomials in
${\mathcal{F}}$
are of the form
$f=PQ_{f}$
, with
$Q_{f}$
at most quadratic. This brings us very close to showing that
${\mathcal{F}}$
indeed looks like the example in (1.2).
The fact that
${\mathcal{S}}$
and
${\mathcal{S}}^{\prime }$
make up most of the set
${\mathcal{F}}$
allows us to improve on the bound in Lemma 4.2. Informally, the following lemma asserts that it is sufficient to be able to add a small set as a “bridge” between
${\mathcal{S}}$
and
${\mathcal{S}}^{\prime }$
, in order that for the remaining polynomials the contribution bound in Lemma 4.2 may be improved to
$q^{D}-2q^{D-1}+q^{D-2}$
.
Lemma A.4 (Sufficient connections between
${\mathcal{S}}$
and
${\mathcal{S}}^{\prime }$
).
Let
${\mathcal{F}}$
be of loneliness at most
$q^{-3}$
such that a sunflower
${\mathcal{S}}\subseteq {\mathcal{F}}$
of maximal size satisfies
$|{\mathcal{S}}|\geqslant 2q+1$
. Suppose that there exists
${\mathcal{C}}\subseteq {\mathcal{F}}\setminus {\mathcal{S}}$
such that
$$\begin{eqnarray}2|{\mathcal{S}}|+|{\mathcal{C}}|<(q+1)^{2},\end{eqnarray}$$
and such that for all
$f\in {\mathcal{S}}^{\prime }\setminus {\mathcal{C}}$
there exist distinct
$f_{i},f_{j}\in {\mathcal{S}}\cup {\mathcal{C}}$
satisfying
$$\begin{eqnarray}\displaystyle |\text{ker}(f)\,\cap \,\ker (f_{i})| & = & \displaystyle |\text{ker}(f)\,\cap \,\ker (f_{j})|=q^{D-1},\nonumber\\ \displaystyle |\text{ker}(f_{i})\,\cap \,\ker (f_{j})| & = & \displaystyle q^{D-2}.\end{eqnarray}$$
Then
$$\begin{eqnarray}|{\mathcal{F}}|\geqslant q^{2}+q+1.\end{eqnarray}$$
Remark A.5. The assumption on
$|{\mathcal{S}}|$
in Lemma A.4 is stronger than in previous instances of the large-sunflower case. As
$q\geqslant 8$
, this will cost us nothing, since Lemma A.4 will only be applied when
$|{\mathcal{S}}|\approx q^{2}/2$
.
Proof. Let
$R:=|{\mathcal{F}}|$
and
$r:=|{\mathcal{C}}|$
. Lemma 4.2 implies that the covering contribution of each
$f\in {\mathcal{C}}$
is at most
$q^{D}-q^{D-1}$
, since
${\mathcal{C}}\subseteq {\mathcal{S}}^{\prime }\cup {\mathcal{S}}^{\prime \prime }$
and
$n=|{\mathcal{S}}|\geqslant 2q+1$
.
Let
$f\in {\mathcal{S}}^{\prime }\setminus {\mathcal{C}}$
, and let
$f_{i},f_{j}\in {\mathcal{S}}\cup {\mathcal{C}}$
be such that (A.5) holds. Then the contribution of
$f$
is bounded from above by
$$\begin{eqnarray}\displaystyle |\text{ker}(f)\setminus (\text{ker}(f_{i})\cup \ker (f_{j}))|\leqslant q^{D}-2q^{D-1}+q^{D-2}. & & \displaystyle \nonumber\end{eqnarray}$$
Moreover, we know from (A.1) that the contribution of any
$f\in {\mathcal{S}}^{\prime \prime }$
is at most
$$\begin{eqnarray}q^{D}-nq^{D-2}+(n-1)q^{D-3}\leqslant q^{D-2}(q-1)^{2},\end{eqnarray}$$
since
$n\geqslant 2q+1$
. Thus, for all
$f\in {\mathcal{S}}^{\prime }\cup {\mathcal{S}}^{\prime \prime }\setminus {\mathcal{C}}$
the contribution of
$f$
is at most
$q^{D-2}(q-1)^{2}$
. Summing all the contributions and using the assumption that
$\unicode[STIX]{x1D6FF}({\mathcal{F}})\leqslant q^{-3}$
via Lemma 2.1, we have
$$\begin{eqnarray}\displaystyle q^{D+2} & {\leqslant} & \displaystyle q^{D}+(n-1)(q^{D}-q^{D-2})+r(q^{D}-q^{D-1})\nonumber\\ \displaystyle & & \displaystyle +\,(R-n-r)q^{D-2}(q-1)^{2}.\nonumber\end{eqnarray}$$
This in turn implies that
$$\begin{eqnarray}R\geqslant q^{2}+q+\frac{(q+1)^{2}-(2n+r)}{q-1}>q^{2}+q,\end{eqnarray}$$
using the assumption
$2n+r<(q+1)^{2}$
.◻
We are ready to establish the main result of this appendix. The key step is to construct the set
${\mathcal{C}}$
appearing in Lemma A.4.
Proof of Proposition A.1.
Let
$R=|{\mathcal{F}}|$
,
$n=|{\mathcal{S}}|$
and
$k=|{\mathcal{S}}^{\prime }|$
, as before. For the sake of obtaining a contradiction, suppose
$R\leqslant q^{2}+q$
. By increasing the size of
${\mathcal{F}}$
if necessary, we may in fact assume that
$$\begin{eqnarray}R=q^{2}+q.\end{eqnarray}$$
Recall from Lemma A.2 that
$$\begin{eqnarray}n+k\geqslant q^{2}.\end{eqnarray}$$
As
$q\geqslant 8$
we have
$$\begin{eqnarray}k\leqslant \frac{q^{2}+3q+2}{2}\leqslant q^{2}-2q-1,\end{eqnarray}$$
so (A.7) ensures that
$n\geqslant 2q+1$
. This formalizes Remark A.5, and confirms one of the hypotheses of Lemma A.4.
Claim. For each
$\unicode[STIX]{x1D706}\in \mathbb{F}_{q}$
we can find an at most linear polynomial
$L$
such that
$$\begin{eqnarray}P(T-\unicode[STIX]{x1D706})L\in {\mathcal{F}}.\end{eqnarray}$$
Proof. Suppose to the contrary that there exists
$\unicode[STIX]{x1D706}\in \mathbb{F}_{q}$
such that
$$\begin{eqnarray}P(T-\unicode[STIX]{x1D706})L\notin {\mathcal{F}}\end{eqnarray}$$
for all
$L$
that are at most linear. Then (A.7), together with Propositions 4.5 and A.3, implies that
$$\begin{eqnarray}{\mathcal{S}}\cup {\mathcal{S}}^{\prime }=\{PQ:(T-\unicode[STIX]{x1D706})\nmid Q\},\end{eqnarray}$$
since
$|\{PQ:(T-\unicode[STIX]{x1D706})\nmid Q\}|=q^{2}$
. Hence the largest sunflower has
$\frac{1}{2}(q^{2}+q)$
petals, and is formed by multiplying a polynomial
$P$
by all (monic) irreducible quadratic polynomials, and all
$L^{2}$
, for
$L\neq T-\unicode[STIX]{x1D706}$
at most linear. We wish to prove that in this case
${\mathcal{S}}$
satisfies the assumptions of Lemma A.4, with
${\mathcal{C}}=\emptyset$
. Indeed, let
$f=PL_{i}L_{j}\in {\mathcal{S}}^{\prime }$
be arbitrary. Since
$L_{i},L_{j}\neq T-\unicode[STIX]{x1D706}$
, it is easy to see that (A.5) holds with
$f_{i}:=PL_{i}^{2}$
and
$f_{j}:=PL_{j}^{2}\in {\mathcal{S}}$
. Now Lemma A.4 delivers a contradiction, as we assumed
$R\leqslant q^{2}+q$
.◻
Let
$$\begin{eqnarray}{\mathcal{S}}_{\max }:=\{{\mathcal{S}}\subset {\mathcal{F}}:{\mathcal{S}}\text{ is a maximal sunflower}\}.\end{eqnarray}$$
To each
${\mathcal{S}}\in {\mathcal{S}}_{\max }$
we associate the set
$$\begin{eqnarray}\unicode[STIX]{x1D706}_{{\mathcal{S}}}:=\{\unicode[STIX]{x1D706}\in \mathbb{F}_{q}:\exists Q_{\unicode[STIX]{x1D706}}\text{ such that }(T-\unicode[STIX]{x1D706})|Q_{\unicode[STIX]{x1D706}}\text{ and }PQ_{\unicode[STIX]{x1D706}}\in {\mathcal{S}}\}.\end{eqnarray}$$
The colouring argument in the proof of Lemma 4.3 ensures that for
$\unicode[STIX]{x1D706}\in \unicode[STIX]{x1D706}_{{\mathcal{S}}}$
the polynomial
$Q_{\unicode[STIX]{x1D706}}$
is unique. Define
$\unicode[STIX]{x1D706}_{{\mathcal{S}}}^{c}:=\mathbb{F}_{q}\setminus \unicode[STIX]{x1D706}_{{\mathcal{S}}}$
, and let
${\mathcal{S}}\in {\mathcal{S}}_{\max }$
be such that
$|\unicode[STIX]{x1D706}_{{\mathcal{S}}}^{c}|$
is maximal, and such that if
$PL^{2}\in {\mathcal{F}}$
then
$PL\notin {\mathcal{S}}$
.
Observe that if
$\unicode[STIX]{x1D706},\unicode[STIX]{x1D706}^{\prime }\in \unicode[STIX]{x1D706}_{{\mathcal{S}}}^{c}$
then
$P(T-\unicode[STIX]{x1D706})(T-\unicode[STIX]{x1D706}^{\prime })\notin {\mathcal{F}}$
, for otherwise we could add
$P(T-\unicode[STIX]{x1D706})(T-\unicode[STIX]{x1D706}^{\prime })$
to
${\mathcal{S}}$
, contradicting its maximality. In particular,
$P(T-\unicode[STIX]{x1D706})^{2}\notin {\mathcal{F}}$
for
$\unicode[STIX]{x1D706}\in \unicode[STIX]{x1D706}_{{\mathcal{S}}}^{c}$
. With
$\ell :=|\unicode[STIX]{x1D706}_{{\mathcal{S}}}^{c}|$
we have
$$\begin{eqnarray}n\leqslant 1+\frac{q^{2}+q}{2}-\ell ;\end{eqnarray}$$
this bound follows from a variant of the colouring argument in the proof of Lemma 4.3.
Roughly speaking, we want
${\mathcal{S}}$
to attain the fewest distinct elements of
$\mathbb{F}_{q}$
as roots, so that we may construct
${\mathcal{C}}$
efficiently. Choosing
${\mathcal{S}}$
as above ensures that if
$L$
is at most linear then
$PL^{2}\notin {\mathcal{F}}\setminus {\mathcal{S}}$
. Indeed, first consider when
$L=1$
, supposing for a contradiction that
$P\in {\mathcal{F}}\setminus {\mathcal{S}}$
. If
${\mathcal{S}}$
contains no linear multiples of
$P$
, then we can contradict its maximality by including
$P$
. If, on the other hand,
${\mathcal{S}}$
contains a linear multiple of
$P$
, then we can put
$P$
in
${\mathcal{S}}$
instead of it, to contradict the maximality of
$|\unicode[STIX]{x1D706}_{S}^{c}|$
. We conclude that
$P\notin {\mathcal{F}}\setminus {\mathcal{S}}$
.
Otherwise
$L=T-\unicode[STIX]{x1D706}$
. Suppose for a contradiction that
$PL^{2}\in {\mathcal{F}}\setminus {\mathcal{S}}$
. Then we must have
$\unicode[STIX]{x1D706}\in \unicode[STIX]{x1D706}_{S}$
, so
$PLL^{\prime }\in {\mathcal{S}}$
for some
$L^{\prime }$
at most linear. Moreover, we must have
$L^{\prime }=1$
, for otherwise we could replace
$PLL^{\prime }$
by
$PL^{2}$
in
${\mathcal{S}}$
to increase
$|\unicode[STIX]{x1D706}_{{\mathcal{S}}}^{c}|$
. Now
$PL^{2}\in {\mathcal{F}}$
and
$PL\in {\mathcal{S}}$
, which is impossible, by our choice of
${\mathcal{S}}$
.
We split our argument into two cases. Case A applies when for each
$\unicode[STIX]{x1D706}\in \unicode[STIX]{x1D706}_{{\mathcal{S}}}^{c}$
we can find two distinct polynomials
$L_{1}^{(\unicode[STIX]{x1D706})},L_{2}^{(\unicode[STIX]{x1D706})}$
, of degree at most 1, such that
$$\begin{eqnarray}f_{\unicode[STIX]{x1D706},1}=P(T-\unicode[STIX]{x1D706})L_{1}^{(\unicode[STIX]{x1D706})},\qquad f_{\unicode[STIX]{x1D706},2}=P(T-\unicode[STIX]{x1D706})L_{2}^{(\unicode[STIX]{x1D706})}\in {\mathcal{F}}.\end{eqnarray}$$
Case B applies when there exists
$\unicode[STIX]{x1D706}\in \mathbb{F}_{q}$
for which there is only one
$$\begin{eqnarray}f_{\unicode[STIX]{x1D706}}=P(T-\unicode[STIX]{x1D706})L_{\unicode[STIX]{x1D706}}\in {\mathcal{F}}.\end{eqnarray}$$
First consider case A. For
$\unicode[STIX]{x1D706}\in \unicode[STIX]{x1D706}_{{\mathcal{S}}}^{c}$
choose distinct
$f_{\unicode[STIX]{x1D706},1},f_{\unicode[STIX]{x1D706},2}\in {\mathcal{F}}$
as in (A.8) and add them to
${\mathcal{C}}$
, with
$L_{\unicode[STIX]{x1D706},1}=1$
if
$P(T-\unicode[STIX]{x1D706})\in {\mathcal{F}}$
. Note that
${\mathcal{S}}$
and
${\mathcal{C}}$
are disjoint, and
$$\begin{eqnarray}2|{\mathcal{S}}|+|{\mathcal{C}}|\leqslant 2\biggl(1+\frac{q^{2}+q}{2}-\ell \biggr)+2\ell <(q+1)^{2}.\end{eqnarray}$$
We proceed to confirm the hypotheses (A.5) of Lemma A.4. Let
$$\begin{eqnarray}f=P(T-\unicode[STIX]{x1D706}_{i})(T-\unicode[STIX]{x1D706}_{j})\in {\mathcal{S}}^{\prime }\setminus {\mathcal{C}},\end{eqnarray}$$
and observe that
$\unicode[STIX]{x1D706}_{i}\neq \unicode[STIX]{x1D706}_{j}$
, since we showed that if
$PL^{2}\in {\mathcal{F}}$
then
$PL^{2}\in {\mathcal{S}}$
. If
$\unicode[STIX]{x1D706}_{i},\unicode[STIX]{x1D706}_{j}\in \unicode[STIX]{x1D706}_{{\mathcal{S}}}$
then we can find
$f_{i}=P(T-\unicode[STIX]{x1D706}_{i})L_{i}$
and
$f_{j}=P(T-\unicode[STIX]{x1D706}_{j})L_{j}$
in
${\mathcal{S}}$
, whereupon (A.5) holds. If
$\unicode[STIX]{x1D706}_{i}\in \unicode[STIX]{x1D706}_{{\mathcal{S}}}$
and
$\unicode[STIX]{x1D706}_{j}\in \unicode[STIX]{x1D706}_{{\mathcal{S}}}^{c}$
, then we can find
$f_{i}=P(T-\unicode[STIX]{x1D706}_{i})L_{i}\in {\mathcal{S}}$
and
$$\begin{eqnarray}f_{\unicode[STIX]{x1D706}_{j},1}=P(T-\unicode[STIX]{x1D706}_{j})L_{1}^{(\unicode[STIX]{x1D706}_{j})},\qquad f_{\unicode[STIX]{x1D706}_{j},2}=P(T-\unicode[STIX]{x1D706}_{j})L_{2}^{(\unicode[STIX]{x1D706}_{j})}\in {\mathcal{C}}.\end{eqnarray}$$
Choose
$m\in \{1,2\}$
such that
$L_{m}^{(\unicode[STIX]{x1D706}_{j})}\neq L_{i}$
and define
$f_{j}:=f_{\unicode[STIX]{x1D706}_{j},m}$
to get (A.5) again, noting that
$f\in {\mathcal{S}}^{\prime }\setminus {\mathcal{C}}$
implies
$f_{j}\neq f$
. Since we proved that there is no polynomial in
${\mathcal{F}}$
for which
$\unicode[STIX]{x1D706}_{i},\unicode[STIX]{x1D706}_{j}\in \unicode[STIX]{x1D706}_{{\mathcal{S}}}^{c}$
, this analysis covers all possibilities.
To conclude case A it remains to consider
$f=P(T-\unicode[STIX]{x1D706}_{i})\in {\mathcal{S}}^{\prime }\setminus {\mathcal{C}}$
, and show that it satisfies (A.5) for some
$f_{i},f_{j}\in {\mathcal{S}}\cup {\mathcal{C}}$
. As
$L_{1}^{(\unicode[STIX]{x1D706}_{i})}=1$
had priority over genuinely linear polynomials in the construction of
${\mathcal{C}}$
, we see that
$P(T-\unicode[STIX]{x1D706}_{i})\in {\mathcal{S}}^{\prime }\setminus {\mathcal{C}}$
only if
$\unicode[STIX]{x1D706}_{i}\in \unicode[STIX]{x1D706}_{{\mathcal{S}}}$
. Hence there exists
$f_{i}=P(T-\unicode[STIX]{x1D706}_{i})L_{i}\in {\mathcal{S}}$
. If there were no linear
$L$
such that
$PL\in {\mathcal{S}}$
, then we could have chosen
$P(T-\unicode[STIX]{x1D706}_{i})$
to place in
${\mathcal{S}}$
instead of
$f_{i}$
, and this contradicts the minimality of
$|\unicode[STIX]{x1D706}_{{\mathcal{S}}}|$
. Therefore there exists
$L_{j}\neq T-\unicode[STIX]{x1D706}_{i}$
, at most linear, such that
$f_{j}=PL_{j}\in {\mathcal{S}}$
, giving (A.5).
Putting everything together, we see that
${\mathcal{S}}$
and
${\mathcal{C}}$
satisfy the assumptions of Lemma A.4, which implies
$R\geqslant q^{2}+q+1$
as desired.
Finally, suppose that we are in case B, so that there exists
$\unicode[STIX]{x1D706}\in \mathbb{F}_{q}$
such that there is a unique
$f_{\unicode[STIX]{x1D706}}=P(T-\unicode[STIX]{x1D706})L_{\unicode[STIX]{x1D706}}$
in
${\mathcal{F}}$
. Then, by (A.6), there is at most one polynomial from the set
$$\begin{eqnarray}X:=\{PQ:(T-\unicode[STIX]{x1D706})\nmid Q,\hspace{2.22198pt}\text{deg}\hspace{2.22198pt}Q\leqslant 2\}\end{eqnarray}$$
that is not in
${\mathcal{F}}$
, as
$|X|=q^{2}$
. We initially choose
$$\begin{eqnarray}{\mathcal{C}}=\left\{\begin{array}{@{}ll@{}}\{f_{\unicode[STIX]{x1D706}}\}\setminus {\mathcal{S}},\quad & \text{if }P\in {\mathcal{F}},\\ \{f_{\unicode[STIX]{x1D706}}\}\cup \{P(T-\unicode[STIX]{x1D705})\in {\mathcal{F}}:\unicode[STIX]{x1D705}\in \mathbb{ F}_{q}\}\setminus {\mathcal{S}},\quad & \text{if }P\notin {\mathcal{F}}.\end{array}\right.\end{eqnarray}$$
If
$P(T-\unicode[STIX]{x1D706}^{\prime })^{2}\notin {\mathcal{F}}$
for some
$\unicode[STIX]{x1D706}^{\prime }\neq \unicode[STIX]{x1D706}$
, then for some
$\unicode[STIX]{x1D706}^{\prime \prime }\notin \{\unicode[STIX]{x1D706},\unicode[STIX]{x1D706}^{\prime }\}$
we replace
$P(T-\unicode[STIX]{x1D706}^{\prime \prime })^{2}$
by
$P(T-\unicode[STIX]{x1D706}^{\prime })(T-\unicode[STIX]{x1D706}^{\prime \prime })$
in
${\mathcal{S}}$
, and also append
$P(T-\unicode[STIX]{x1D706}^{\prime \prime })^{2}$
to
${\mathcal{C}}$
. When
$P\notin {\mathcal{F}}$
, we note that
$$\begin{eqnarray}2|{\mathcal{S}}|+|{\mathcal{C}}|\leqslant (q^{2}+q)+q<(q+1)^{2}.\end{eqnarray}$$
Inequality (A.4) also holds when
$P\in {\mathcal{F}}$
.
We showed in case A that if
$L$
is at most linear then
$PL^{2}\notin {\mathcal{F}}\setminus {\mathcal{S}}$
; the argument still works in case B (wherein
${\mathcal{S}}$
has possibly been modified) unless
$L=T-\unicode[STIX]{x1D706}^{\prime \prime }$
, and in the latter case
$PL^{2}\in {\mathcal{C}}$
. Thus, if
$f\in {\mathcal{S}}^{\prime }\setminus {\mathcal{C}}$
then either
(i)
$f=P(T-\unicode[STIX]{x1D706}_{i})(T-\unicode[STIX]{x1D706}_{j})$
with
$\unicode[STIX]{x1D706}_{i},\unicode[STIX]{x1D706}_{j},\unicode[STIX]{x1D706}\in \mathbb{F}_{q}$
pairwise distinct, or(ii)
$f=P(T-\unicode[STIX]{x1D706}_{j})$
for some
$\unicode[STIX]{x1D706}_{j}\neq \unicode[STIX]{x1D706}$
.
In scenario (i) we obtain (A.5) by choosing
$f_{i}=P(T-\unicode[STIX]{x1D706}_{i})^{2}$
and
$f_{j}=P(T-\unicode[STIX]{x1D706}_{j})^{2}$
, or instead
$f_{j}=P(T-\unicode[STIX]{x1D706}^{\prime })(T-\unicode[STIX]{x1D706}^{\prime \prime })$
if, say,
$\unicode[STIX]{x1D706}_{j}\in \{\unicode[STIX]{x1D706}^{\prime },\unicode[STIX]{x1D706}^{\prime \prime }\}$
. In scenario (ii) we must have
$P\in {\mathcal{F}}$
, by our choice of
${\mathcal{C}}$
, and so
$P\in {\mathcal{S}}$
. We may therefore choose
$f_{i}=P$
and
$f_{j}=P(T-\unicode[STIX]{x1D706}_{j})^{2}$
, as long as
$\unicode[STIX]{x1D706}_{j}\notin \{\unicode[STIX]{x1D706}^{\prime },\unicode[STIX]{x1D706}^{\prime \prime }\}$
. If
$\unicode[STIX]{x1D706}_{j}\in \{\unicode[STIX]{x1D706}^{\prime },\unicode[STIX]{x1D706}^{\prime \prime }\}$
then we may choose
$f_{j}=P(T-\unicode[STIX]{x1D706}^{\prime })(T-\unicode[STIX]{x1D706}^{\prime \prime })$
instead.
Therefore
${\mathcal{S}}$
and
${\mathcal{C}}$
satisfy the hypotheses of Lemma A.4, which completes the proof of Proposition A.1.◻
