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

Abstract

In a projective plane ${\Pi }_q$ (not necessarily Desarguesian) of order $q,$ a point subset $S$ is saturating (or dense) if any point of ${\Pi }_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 ${\Pi }_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 ${\Pi }_q$ with $2c\sqrt{(q+1)\ln (q+1)}+2\le k<\frac{q^2-1}{q+2}\sim 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 {\Pi }_q$ is $(1,\mu )$-saturating if for every point $Q$ of ${\Pi }_q\setminus S$ the number of secants of $S$ through $Q$ is at least $\mu$, counted with multiplicity. The multiplicity of a secant $\ell$ is computed as $\left(\genfrac{}{}{0ex}{}{\#(\ell \cap S)}{2}\right).$ The following upper bound on the smallest size $s_{\mu }(2,q)$ of a $(1,\mu )$-saturating set in ${\Pi }_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,\mu )$-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

Cited by in corpus (2)

• Tables, bounds and graphics of sizes of complete arcs in the plane $\mathrm{PG}(2,q)$ for all $q\le 321007$ and sporadic $q$ in $[323761\dots 430007]$ obtained by an algorithm with fixed order of points (FOP)
• Upper bounds on the smallest size of a saturating set in projective planes and spaces of even dimension