A probabilistic construction of small complete caps in projective spaces

2014/06/03 by Daniele Bartoli, Bartoli, Daniele, Stefano Marcugini +3
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1406.5060

openalex publication_date 2014/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this work complete caps in PG(N,q) of size O(q^(N-1)/(2)log³⁰⁰ q) are obtained by probabilistic methods. This gives an upper bound asymptotically very close to the trivial lower bound √(2)q^(N-1)/(2) and it improves the best known bound in the literature for small complete caps in projective spaces of any dimension. The result obtained in the paper also gives a new upper bound for l(m,2,q)₄, that is the minimal length n for which there exists an [n,n-m, 4]_q2 covering code with given m and q.

Related

• Upper bounds on the smallest size of a complete cap in PG(N,q), N≥3, under a certain probabilistic conjecture
• Tables, bounds and graphics of the smallest known sizes of complete caps in the spaces PG(3,q) and PG(4,q)
• New inductive constructions of complete caps in PG(N,q), q even
• Small complete caps in \rm PG(4n + 1, q)
• Small complete caps in PG(4n+1,q)\rm PG(4n+1, q)