RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Probl. Peredachi Inf.: Year: Volume: Issue: Page: Find

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

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).

Full text: PDF file (383 kB)
References: PDF file   HTML file

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

Bibliographic databases:

UDC: 621.391.1+519.1
Revised: 25.08.2014

Citation: D. Bartoli, A. A. Davydov, G. Faina, A. A. Kreshchuk, S. Marcugini, F. Pambianco, “Upper bounds on the smallest size of a complete arc in $PG(2,q)$ under a certain probabilistic conjecture”, Probl. Peredachi Inf., 50:4 (2014), 22–42; Problems Inform. Transmission, 50:4 (2014), 320–339

Citation in format AMSBIB
\Bibitem{BarDavFai14} \by D.~Bartoli, A.~A.~Davydov, G.~Faina, A.~A.~Kreshchuk, S.~Marcugini, F.~Pambianco \paper Upper bounds on the smallest size of a~complete arc in $PG(2,q)$ under a~certain probabilistic conjecture \jour Probl. Peredachi Inf. \yr 2014 \vol 50 \issue 4 \pages 22--42 \mathnet{http://mi.mathnet.ru/ppi2151} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3374254} \transl \jour Problems Inform. Transmission \yr 2014 \vol 50 \issue 4 \pages 320--339 \crossref{https://doi.org/10.1134/S0032946014040036} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000347532800003} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84920570985} 

• http://mi.mathnet.ru/eng/ppi2151
• http://mi.mathnet.ru/eng/ppi/v50/i4/p22

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. D. Bartoli, A. A. Davydov, G. Faina, A. A. Kreshchuk, S. Marcugini, F. Pambianco, “Upper Bounds on the Smallest Size of a Complete Arc in a Finite Desarguesian Projective Plane Based on Computer Search”, J. Geom., 107:1 (2016), 89–117
2. A. A. Davydov, S. Marcugini, F. Pambianco, “On almost complete caps in $\mathrm{PG}(N,q)$”, Cybern. Inf. Technol., 18:5, SI (2018), 54–62
3. A. A. Davydov, G. Faina, S. Marcugini, F. Pambianco, “Upper bounds on the smallest size of a complete cap in $\mathrm{PG}(N,q)$, $N\geq 3$, under a certain probabilistic conjecture”, Australas. J. Comb., 72:3 (2018), 516–535
•  Number of views: This page: 318 Full text: 41 References: 21 First page: 8