Problemy Peredachi Informatsii
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors

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


Problemy Peredachi Informatsii, 2014, Volume 50, Issue 4, Pages 22–42 (Mi ppi2151)  

This article is cited in 6 scientific papers (total 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
Full-text PDF (383 kB) Citations (6)
References:
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).
Received: 19.04.2014
Revised: 25.08.2014
English version:
Problems of Information Transmission, 2014, Volume 50, Issue 4, Pages 320–339
DOI: https://doi.org/10.1134/S0032946014040036
Bibliographic databases:
Document Type: Article
UDC: 621.391.1+519.1
Language: Russian
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{https://mathscinet.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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000347532800003}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84920570985}
Linking options:
  • https://www.mathnet.ru/eng/ppi2151
  • https://www.mathnet.ru/eng/ppi/v50/i4/p22
  • This publication is cited in the following 6 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Проблемы передачи информации Problems of Information Transmission
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025