Upper bounds on the smallest size of a complete cap in PG(N,q), N 3, under a certain probabilistic conjecture

MaRDI QIDQ4622636zbMATH OpenFDO

Authors Alexander A. Davydov, Giorgio Faina, Stefano Marcugini, Fernanda Pambianco

Publication date 13 February 2019

Full work available at URL https://arxiv.org/abs/1706.01941, http://ajc.maths.uq.edu.au/pdf/72/ajc_v72_p516.pdf

zbMATH Keywords

complete caps

Mathematics Subject Classification ID

Combinatorial structures in finite projective spaces (51E20)

Abstract: In the projective space $mathrmPG(N,q)$ over the Galois field of order $q$, $Nge3$, an iterative step-by-step construction of complete caps by adding a new point on every step is considered. It is proved that uncovered points are evenly placed on the space. A natural conjecture on an estimate of the number of new covered points on every step is done. For a part of the iterative process, this estimate is proved rigorously. Under the conjecture mentioned, new upper bounds on the smallest size $t_2(N,q)$ of a complete cap in $mathrmPG(N,q)$ are obtained, in particular, �egin{align*} t_{2}(N,q)<frac{sqrt{q^{N+1}}}{q-1}left(sqrt{(N+1)ln q}+1 ight)+2 hicksim q^frac{N-1}{2}sqrt{(N+1)ln q},quad Nge3. end{align*} A connection with the Birthday problem is noted. The effectiveness of the new bounds is illustrated by comparison with sizes of complete caps obtained by computer in wide regions of $q$.

Recommendations

• Conjectural upper bounds on the smallest size of a complete cap in \(\mathrm{PG}(N,q)\), \(N\geq 3\)
• New upper bounds on the smallest size of a complete cap in the spaces \(\mathrm{PG}(3,q)\) and \(\mathrm{PG}(4,q)\).
• Upper bounds on the smallest size of a complete cap in \(\mathrm{PG}(3, q)\) and \(\mathrm{PG}(4, q)\)
• A construction of small complete caps in projective spaces
• New upper bounds on the smallest size of a complete cap in the space \(\mathrm{PG}(3,q)\)

Cites work

• A (probably) exact solution to the birthday problem
• A construction of small complete caps in projective spaces
• Bicovering arcs and small complete caps from elliptic curves
• Complete caps in \(\mathrm{AG}(3, q)\) from elliptic curves
• Complete caps in projective spaces PG\((n,q)\)
• Conjectural upper bounds on the smallest size of a complete cap in \(\mathrm{PG}(N,q)\), \(N\geq 3\)
• scientific article; zbMATH DE number 1284421 (Why is no real title available?)
• scientific article; zbMATH DE number 475084 (Why is no real title available?)
• scientific article; zbMATH DE number 1024657 (Why is no real title available?)
• scientific article; zbMATH DE number 1795248 (Why is no real title available?)
• Linear codes with covering radius 2 and other new covering codes
• Majorization and the Birthday Inequality
• Maximum scattered linear sets and complete caps in Galois spaces
• New inductive constructions of complete caps in \(\mathrm{PG}(N, q)\), \(q\) even
• New quantum caps in \(\mathrm{PG}(4, 4)\)
• New types of estimates for the smallest size of complete arcs in a finite Desarguesian projective plane
• New upper bounds on the smallest size of a complete arc in a finite Desarguesian projective plane
• On complete caps and ovaloids in three-dimensional Galois spaces of characteristic two
• On sizes of complete arcs in \(PG(2,q)\)
• On sizes of complete caps in projective spaces \(\mathrm{PG}(n, q)\) and arcs in planes \(\mathrm{PG}(2, q)\)
• Open problems in finite projective spaces
• Quantum codes from caps
• Quasi-Perfect Linear Codes With Minimum Distance $4$
• Recursive constructions of complete caps
• Small complete arcs in projective planes
• Small Complete Caps from Singular Cubics
• Small complete caps from singular cubics. II
• Small complete caps in PG(N, q), q even
• Small complete caps in Galois affine spaces
• Small complete caps in Galois spaces.
• Small complete caps in spaces of even characteristic
• Small complete caps in three-dimensional Galois spaces
• The Birthday Problem Revisited
• The geometry of covering codes: small complete caps and saturating sets in Galois spaces
• The packing problem in statistics, coding theory and finite projective spaces
• Upper bounds on the smallest size of a complete arc in \(\mathrm{PG}(2, {q})\) under a certain probabilistic conjecture
• Upper bounds on the smallest size of a complete arc in a finite Desarguesian projective plane based on computer search
• Upper bounds on the smallest size of a complete cap in \(\mathrm{PG}(3, q)\) and \(\mathrm{PG}(4, q)\)

Cited in

(9)

• On the size of a cap in \(\text{PG} (n,q)\) with \(q\) even and \(n\geq 3\)
• Conjectural upper bounds on the smallest size of a complete cap in \(\mathrm{PG}(N,q)\), \(N\geq 3\)
• Upper bounds on the smallest size of a complete cap in \(\mathrm{PG}(3, q)\) and \(\mathrm{PG}(4, q)\)
• The smallest size of a complete cap in PG(3,\,7)
• New upper bounds on the smallest size of a complete cap in the spaces \(\mathrm{PG}(3,q)\) and \(\mathrm{PG}(4,q)\).
• scientific article; zbMATH DE number 5180842 (Why is no real title available?)
• On the size of complete caps in PG\((3,2^{h}\))
• Small complete caps in PG(4n+1,q)${\rm PG}(4n+1, q)$
• Projective sets with no trisecant lines

This page was built for publication: Upper bounds on the smallest size of a complete cap in \(\mathrm{PG}(N,q)\), \(N \geq 3\), under a certain probabilistic conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4622636)