In the N-dimensional projective space PG(N, q) over the Galois field of order q, N ≥ 3, an iterative step-by-step construction of complete caps by adding a new point in every step is considered. It is proved that uncovered points are uniformly distributed in the space. A natural conjecture on an estimate of the number of new covered points in 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 t2(N, q) of a complete cap in PG(N, q), N ≥ 3, are obtained, in particular, (Formula presented) ln q. 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.
Upper bounds on the smallest size of a complete cap in PG(N,q), N ≥ 3, under a certain probabilistic conjecture
Giorgio Faina;Stefano Marcugini;Fernanda Pambianco;
2018
Abstract
In the N-dimensional projective space PG(N, q) over the Galois field of order q, N ≥ 3, an iterative step-by-step construction of complete caps by adding a new point in every step is considered. It is proved that uncovered points are uniformly distributed in the space. A natural conjecture on an estimate of the number of new covered points in 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 t2(N, q) of a complete cap in PG(N, q), N ≥ 3, are obtained, in particular, (Formula presented) ln q. 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
