The minimum size of complete caps in \(({\mathbb Z}/n{\mathbb Z})^2\) (Q2500977)

Summary: A line in \(({\mathbb Z}/n{\mathbb Z})^2\) is any translate of a cyclic subgroup of order \(n\). A subset \(X\subset ({\mathbb Z}/n{\mathbb 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 \(({\mathbb Z}/n{\mathbb Z})^2\). The other natural extremal question of determining the maximum size of a cap in \(({\mathbb Z}/n{\mathbb 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.