Counting arcs in ${\mathbb{F}}_q^2$

Abstract

An arc in ${\mathbb{F}}_q^2$ is a set $P\subset {\mathbb{F}}_q^2$ such that no three points of $P$ are collinear. We use the method of hypergraph containers to prove several counting results for arcs. Let $\mathcal{A}(q)$ denote the family of all arcs in ${\mathbb{F}}_q^2$. Our main result is the bound \[ |\mathcal A(q)| \leq 2^{(1+o(1))q}. \] This matches, up to the factor hidden in the $o(1)$ notation, the trivial lower bound that comes from considering all subsets of an arc of size $q$. We also give upper bounds for the number of arcs of a fixed (large) size. Let $k=q^t$ for some $t>2/3$, and let $\mathcal{A}(q,k)$ denote the family of all arcs in ${\mathbb{F}}_q^2$ with cardinality $k$. We prove that, for all $\gamma >0$ \[ |\mathcal A(q,k)| \leq \binom{(1+γ)q}{k}. \] This result improves a bound of Roche-Newton and Warren. A nearly matching lower bound \[ |\mathcal A(q,k)| \geq \binom{q}{k} \] follows by considering all subsets of size $k$ of an arc of size $q$.