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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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

This article is cited in 3 scientific papers (total in 3 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).

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
Received: 19.04.2014
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}


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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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  crossref  mathscinet  zmath  isi  elib  scopus
    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  crossref  mathscinet  isi  scopus
    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  mathscinet  zmath  isi
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:318
    Full text:41
    References:21
    First page:8

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020