New upper bounds on the smallest size of a complete arc in a finite Desarguesian projective plane

摘要

In the projective planes PG(2, q), more than 1230 new small complete arcs are obtained for ({q leq 13627}) and ({q in G}) where G is a set of 38 values in the range 13687,..., 45893; also, ({2^{18} in G}). This implies new upper bounds on the smallest size t 2(2, q) of a complete arc in PG(2, q). From the new bounds it follows that$$t_{2}(2, q) < 4.5sqrt{q} , {rm for} , q leq 2647$$and q = 2659,2663,2683,2693,2753,2801. Also,$$t_{2}(2, q) < 4.8sqrt{q} , {rm for} , q leq 5419$$and q = 5441,5443,5449,5471,5477,5479,5483,5501,5521. Moreover,$$t_{2}(2, q) < 5sqrt{q} , {rm for} , q leq 9497$$and q = 9539,9587,9613,9623,9649,9689,9923,9973. Finally,$$t_{2}(2, q) <5 .15sqrt{q} , {rm for} , q leq 13627$$and q = 13687,13697,13711,14009. Using the new arcs it is shown that$$t_{2}(2, q) < sqrt{q}ln^{0.73}q {rm for} 109 leq q leq 13627, {rm and}, q in G.$$Also, as q grows, the positive difference ({sqrt{q}ln^{0.73} q-overline{t}_{2}(2, q)}) has a tendency to increase whereas the ratio ({overline{t}_{2}(2, q)/(sqrt{q}ln^{0.73} q)}) tends to decrease. Here ({overline{t}_{2}(2, q)}) is the smallest known size of a complete arc in PG(2,q). These properties allow us to conjecture that the estimate ({t_{2}(2,q) < sqrt{q}ln ^{0.73}q}) holds for all ({q geq 109.}) The new upper bounds are obtained by finding new small complete arcs in PG(2,q) with the help of a computer search using randomized greedy algorithms. Finally, new forms of the upper bound on t 2(2,q) are proposed. Mathematics Subject Classification (2010) 51E21 51E22 94B05 Keywords Projective planes complete arcs small complete arcs Page %P Close Plain text Look Inside Reference tools Export citation EndNote (.ENW) JabRef (.BIB) Mendeley (.BIB) Papers (.RIS) Zotero (.RIS) BibTeX (.BIB) Add to Papers Other actions Register for Journal Updates About This Journal Reprints and Permissions Share Share this content on Facebook Share this content on Twitter Share this content on LinkedIn Related Content Supplementary Material (0) References (52) ReferencesAbatangelo, V.: A class of complete [(q + 8)/3]-arcs of PG(2,q), with q = 2 h and ({h (geq 6)}) even Ars Combinatoria. 16, 103–111 (1983)Ball S.: On small complete arcs in a finite plane. Discrete Math. 74, 29–34 (1997)CrossRefBartoli D., Davydov A.A., Faina G., Marcugini S., Pambianco F.: On sizes of complete arcs in PG(2, q). Discrete Math. 312, 680–698 (2012)MathSciNetMATHCrossRefBartoli, D., Davydov, A.A., Faina, G., Marcugini, S., Pambianco, F.: New upper bounds on the smallest size of a complete arc in the plane PG(2, q). In: Proc. XIII International Workshop on Algebraic and Combinational Coding Theory, ACCT2012, Pomorie, Bulgaria, pp. 60–66 (2012). http://​www.​moi.​math.​bas.​bg/​moiuser/​~ACCT2012/​b10.​pdf Bartoli, D., Davydov, A.A., Marcugini, S., Pambianco, F.: New type of estimate for the smallest size of complete arcs in PG(2, q). In: Proceedings of the XIII International Workshop on Algebraic and Combinational Coding Theory, ACCT2012, Pomorie, Bulgaria, pp. 67–72 (2012). http://​www.​moi.​math.​bas.​bg/​moiuser/​~ACCT2012/​b11.​pdf Bartoli D., Davydov A.A., Marcugini S., Pambianco F.: The minimum order of complete caps in PG(4,4). Adv. Math. Commun. 5, 37–40 (2011)MathSciNetMATHCrossRefBierbrauer, J., Bartoli, D., Faina, G., Marcugini, S., Pambianco, F., Edel, Y.: The structure of quaternary quantum caps. Des. Codes Cryptogr. doi:10.​1007/​s10623-013-9796-5 Davydov A.A., Faina G., Marcugini S., Pambianco F.: Computer search in projective planes for the sizes of complete arcs. J. Geom. 82, 50–62 (2005)MathSciNetMATHCrossRefDavydov A.A., Faina G., Marcugini S., Pambianco F.: On sizes of complete caps in projective spaces PG(n,q) and arcs in planes PG(2, q). J. Geom. 94, 31–58 (2009)MathSciNetMATHCrossRefDavydov A.A., Giulietti M., Marcugini S., Pambianco F.: On sharply transitive sets in PG(2, q). Innov. Incid. Geom. 6(−7), 139–151 (2009)MathSciNetDavydov A.A., Giulietti M., Marcugini S., Pambianco F.: New inductive constructions of complete caps in PG(N,q), q even. J. Comb. Des. 18, 176–201 (2010)MathSciNetDavydov A.A., Giulietti M., Marcugini S., Pambianco F.: Linear nonbinary covering codes and saturating sets in projective spaces. Adv. Math. Commun. 5, 119–147 (2011)MathSciNetMATHCrossRefDavydov A.A., Marcugini S., Pambianco F.: Complete caps in projective spaces PG(n,q). J. Geom. 80, 23–30 (2004)MathSciNetMATHCrossRefFaina G., Giulietti M.: On small dense arcs in Galois planes of square order. Discrete Math. 267, 113–125 (2003)MathSciNetMATHCrossRefFaina G., Pambianco F.: On the spectrum of the values k for which a complete k-cap in PG(n,q) exists. J. Geom. 62, 84–98 (1998)MathSciNetMATHCrossRefFaina G., Pambianco F.: On some 10-arcs for deriving the minimum order for complete arcs in small projective planes. Discrete Math. 208(209), 261–271 (1999)MathSciNetCrossRefGács A., Szőnyi T.: Random constructions and density results. Des. Codes Cryptogr. 47, 267–287 (2008)MathSciNetCrossRefGiulietti M.: Small complete caps in PG(2, q) for q an odd square. J. Geom. 69, 110–116 (2000)MathSciNetMATHCrossRefGiulietti M.: Small complete caps in Galois affine spaces. J. Algebraic. Combin. 25, 149–168 (2007)MathSciNetMATHCrossRefGiulietti M.: Small complete caps in PG(N,q), q even. J. Combin. Des. 15, 420–436 (2007)MathSciNetMATHCrossRefGiulietti, M., Korchmáros, G., Marcugini, S., Pambianco, F.: Transitive A 6-invariant k-arcs in PG(2, q). Des. Codes Cryptogr. doi:10.​1007/​s10623-012-9619-0 (to appear).Giulietti, M., Ughi, E.: A small complete arc in PG(2, q), q =  p 2, p ≡ 3 (mod 4). Discrete Math. 208–209, 311–318 (1999)Hadnagy E.: Small Complete Arcs in PG(2,p). Finite Fields Appl. 5, 1–12 (1999)MathSciNetMATHCrossRefHartman A., Raskin L.: Problems and algorithms for covering arrays. Discrete Math. 284, 149–156 (2004)MathSciNetMATHCrossRefHirschfeld, J.W.P.: Maximum sets in finite projective spaces. In: Lloyd, E.K. (ed.) Surveys in Combinatorics. Lecture Note Series, vol. 82, pp. 55–76. London Math. Soc., Cambridge University Press, Cambridge (1983)Hirschfeld, J.W.P.: Projective geometries over finite fields, 2nd edn. Clarendon Press, Oxford (1998)Hirschfeld J.W.P., Storme L.: The packing problem in statistics, coding theory and finite projective spaces. J. Stat. Planning Infer. 72, 355–380 (1998)MathSciNetMATHCrossRefHirschfeld, J.W.P., Storme, L.: The packing problem in statistics, coding theory and finite geometry: update 2001. In: Blokhuis, A., Hirschfeld, J.W.P. et al. (eds.) Finite Geometries, Developments of Mathematics. Proceedings of the Fourth Isle of Thorns Conference, Chelwood Gate 2000, vol. 3, pp. 201–246. Kluwer Academic Publisher, Boston (2001)Keri G.: Types of superregular matrices and the number of n-arcs and complete n-arcs in PG(r,q). J. Comb. Des. 14, 363–390 (2006)MathSciNetMATHCrossRefKim J.H., Vu V.: Small complete arcs in projective planes. Combinatorica 23, 311–363 (2003)MathSciNetMATHCrossRefKorchmáros G.: New examples of complete k-arcs in PG(2, q). Europ. J. Combin. 4, 329–334 (1983)MATHLombardo-Radice L.: Sul problema dei k-archi completi di S 2,q . Boll. Un. Mat. Ital. 11, 178–181 (1956)MathSciNetMATHLisonᄕk P., Marcugini S., Pambianco F.: Constructions of small complete arcs with prescribed symmetry. Contribut. Discrete Math. 3, 14–19 (2008)Marcugini, S., Milani, A., Pambianco, F.: Minimal complete arcs in PG(2, q), q ≤  29. J. Combin. Math. Combin. Comput. 47, 19–29 (2003)Marcugini, S., Milani, A., Pambianco, F.: Minimal complete arcs in PG(2, q), q ≤  32. In: Proceedings of the XII International Workshop on Algebraic and Combinational Coding Theory, ACCT2010, Novosibirsk, Russia, pp. 217–222 (2010)Östergård P.R.J.: Computer search for small complete caps. J. Geom. 69, 172–179 (2000)Pellegrino G.: Un’osservazione sul problema dei k-archi completi in S 2,q , con q ≡ 1 (mod 4). Atti Accad. Naz. Lincei Rend. 63, 33–44 (1977)MathSciNetPellegrino G.: Sugli archi completi dei piani PG(2, q), con q dispari, contenenti (q + 3)/2 punti di una conica. Rend. Mat. 12, 649–674 (1992)MathSciNetMATHPellegrino, G.: Archi completi, contenenti (q + 1)/2 punti di una conica, nei piani di Galois di ordine dispari. Rend. Circ. Mat. Palermo (2) 62, 273–308 (1993)Polverino O.: Small minimal blocking sets and complete k-arcs in PG(2,p3). Discrete Math. 208(−209), 469–476 (1999)MathSciNetCrossRefSegre B.: Le geometrie di Galois. Ann. Mat. Pura Appl. 48, 1–97 (1959)MathSciNetMATHCrossRefSegre B.: Ovali e curve σ nei piani di Galois di caratteristica due. Atti Accad. Naz. Lincei Rend. 32, 785–790 (1962)MathSciNetMATHSegre B.: Introduction to Galois geometries. Atti Accad. Naz. Lincei Mem. 8, 133–236 (1967)MathSciNetMATHSzőnyi T.: Small complete arcs in Galois planes. Geom. Dedicata 18, 161–172 (1985)MathSciNetCrossRefSzőnyi T.: Note on the order of magnitude of k for complete k-arcs in PG(2, q). Discrete Math. 66, 279–282 (1987)MathSciNetCrossRefSzőnyi, T.: Complete arcs in Galois planes: Survey. Quaderni del Seminario di Geometrie Combinatorie, vol. 94. Università degli studi di Roma, La Sapienza (1989).Szőnyi, T.: Arcs, caps, codes and 3-independent subsets. In: Faina, G., et al. (eds.) Giornate di Geometrie Combinatorie, Università degli studi di Perugia, pp. 57–80, Perugia (1993)Szőnyi, T.: Some applications of algebraic curves in finite geometry and combinatorics. In: Bailey, R.A. (ed.) Surveys in Combinatorics, pp. 198–236. Cambridge University Press, Cambridge (1997)Thas J.A.: M.D.S. codes and arcs in projective spaces: a survey. Le Matematiche (Catania) 47, 315–328 (1992)MathSciNetMATHUghi, E.: The values ({sqrt{2q}}) and log 2 q: their relationship with k-arcs. Ars Combinatoria. 57, 201–207 (2000).Ughi E.: Small almost complete arcs. Discrete Math. 255, 367–379 (2002)MathSciNetMATHCrossRefVoloch J.F.: On the completeness of certain plane arcs II. Eur. J. Combin. 11, 491–496 (1990)MathSciNetMATH About this Article Title New upper bounds on the smallest size of a complete arc in a finite Desarguesian projective plane Journal Journal of Geometry Volume 104, Issue 1 , pp 11-43 Cover Date2013-04 DOI 10.1007/s00022-013-0154-6 Print ISSN 0047-2468 Online ISSN 1420-8997 Publisher SP Birkhäuser Verlag Basel Additional Links Register for Journal Updates Editorial Board About This Journal Manuscript Submission Topics Geometry Keywords 51E21 51E22 94B05 Projective planes complete arcs small complete arcs Industry Sectors Finance, Business & Banking Authors Daniele Bartoli (1) Alexander A. Davydov (2) Giorgio Faina (3) Stefano Marcugini (3) Fernanda Pambianco (3) Author Affiliations 1. Dipartimento di Matematica e Informatica, Università degli Studi di Perugia, Via Vanvitelli 1, Perugia, 06123, Italy 2. Institute for Information Transmission Problems (KharkevichInstitute), Russian Academy of Sciences, Bol’shoi Karetnyiper. 19, GSP-4, Moscow, 127994, Russian Federation 3. Dipartimento di Matematica e Informatica, Università degli Studi di Perugia, Via Vanvitelli 1, Perugia, 06123, Italy Continue reading... To view the rest of this content please follow the download PDF link above.