On upper bounds on the smallest size of a saturating set in a projective plane

Abstract

In a projective plane $Π_{q}$ (not necessarily Desarguesian) of order $q,$ a point subset $S$ is saturating (or dense) if any point of $Π_{q}\setminus S$ is collinear with two points in$~S$. Using probabilistic methods, the following upper bound on the smallest size $ s(2,q)$ of a saturating set in $Π_{q}$ is proved: \begin{equation*} s(2,q)\leq 2\sqrt{(q+1)\ln (q+1)}+2\thicksim 2\sqrt{q\ln q}. \end{equation*} We also show that for any constant $c\ge 1$ a random point set of size $k$ in $Π_{q}$ with $ 2c\sqrt{(q+1)\ln(q+1)}+2\le k<\frac{q^{2}-1}{q+2}\thicksim q$ is a saturating set with probability greater than $1-1/(q+1)^{2c^{2}-2}.$ Our probabilistic approach is also applied to multiple saturating sets. A point set $S\subset Π_{q}$ is $(1,μ)$-saturating if for every point $Q$ of $Π_{q}\setminus S$ the number of secants of $S$ through $Q$ is at least $μ$, counted with multiplicity. The multiplicity of a secant $ \ell $ is computed as ${\binom{\#(\ell \,\cap S)}{2}}.$ The following upper bound on the smallest size $s_{μ}(2,q)$ of a $(1,μ)$-saturating set in $Π_{q}$ is proved: \begin{equation*} s_{μ}(2,q)\leq 2(μ+1)\sqrt{(q+1)\ln (q+1)}+2\thicksim 2(μ+1)\sqrt{ q\ln q}\,\text{ for }\,2\leq μ\leq \sqrt{q}. \end{equation*} By using inductive constructions, upper bounds on the smallest size of a saturating set (as well as on a $(1,μ)$-saturating set) in the projective space $PG(N,q)$ are obtained. All the results are also stated in terms of linear covering codes.

15 pages, 24 references, misprints are corrected, Sections 3-5 and some references are added