The Minimum Size of Complete Caps in $({\Bbb Z}/n{\Bbb Z})^2$

Jack Huizenga

Abstract


A line in $({\Bbb Z}/n{\Bbb Z})^2$ is any translate of a cyclic subgroup of order $n$. A subset $X\subset ({\Bbb Z}/n{\Bbb Z})^2$ is a cap if no three of its points are collinear, and $X$ is complete if it is not properly contained in another cap. We determine bounds on $\Phi(n)$, the minimum size of a complete cap in $({\Bbb Z}/n{\Bbb Z})^2$. The other natural extremal question of determining the maximum size of a cap in $({\Bbb Z}/n{\Bbb Z})^2$ is considered in a separate preprint by the present author. These questions are closely related to well-studied questions in finite affine and projective geometry. If $p$ is the smallest prime divisor of $n$, we prove that $$\max\{4,\sqrt{2p}+{1\over2}\}\leq \Phi(n)\leq \max\{4,p+1\}.$$ We conclude the paper with a large number of open problems in this area.


Full Text: PDF