The minimum size of complete caps in \(({\mathbb Z}/n{\mathbb Z})^2\)
The electronic journal of combinatorics, Tome 13 (2006)
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.
@article{10_37236_1084,
author = {Jack Huizenga},
title = {The minimum size of complete caps in \(({\mathbb {Z}/n{\mathbb} {Z})^2\)}},
journal = {The electronic journal of combinatorics},
year = {2006},
volume = {13},
doi = {10.37236/1084},
zbl = {1165.51302},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1084/}
}
Jack Huizenga. The minimum size of complete caps in \(({\mathbb Z}/n{\mathbb Z})^2\). The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1084
Cité par Sources :