RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 2014 Volume 50, Issue 4, Pages 22–42 (Mi ppi2151)

This article is cited in 6 papers

Coding Theory

Upper bounds on the smallest size of a complete arc in $PG(2,q)$ under a certain probabilistic conjecture

D. Bartolia, A. A. Davydovb, G. Fainaa, A. A. Kreshchukb, S. Marcuginia, F. Pambiancoa

a Department of Mathematics and Computer Sciences, Università degli Studi di Perugia, Perugia, Italy
b Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow, Russia

Abstract: In the projective plane $PG(2,q)$, we consider an iterative construction of complete arcs which adds a new point in each step. It is proved that uncovered points are uniformly distributed over the plane. For more than half of steps of the iterative process, we prove an estimate for the number of newly covered points in every step. A natural (and well-founded) conjecture is made that the estimate holds for the other steps too. As a result, we obtain upper bounds on the smallest size $t_2(2,q)$ of a complete arc in $PG(2,q)$, in particular,
\begin{align*} &t_2(2,q)<\sqrt q\sqrt{3\ln q+\ln\ln q+\ln 3}+\sqrt{\frac q{3\ln q}}+3,\\ &t_2(2,q)<1{,}87\sqrt{q\ln q}. \end{align*}
Nonstandard types of upper bounds on $t_2(2,q)$ are considered, one of them being new. The effectiveness of the new bounds is illustrated by comparing them with the smallest known sizes of complete arcs obtained in recent works of the authors and in the present paper via computer search in a wide region of $q$. We note a connection of the considered problems with the so-called birthday problem (or birthday paradox).

UDC: 621.391.1+519.1

Received: 19.04.2014
Revised: 25.08.2014


 English version:
Problems of Information Transmission, 2014, 50:4, 320–339

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024