\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Jack Huizenga}
%
%
\medskip
\noindent
%
%
{\bf The Minimum Size of Complete Caps in $({\Bbb Z}/n{\Bbb Z})^2$}
%
%
\vskip 5mm
\noindent
%
%
%
%
A \emph{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 \emph{cap} if no three of its points are collinear, and $X$ is
\emph{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.
\bye