×

On sizes of complete arcs in \(PG(2,q)\). (English) Zbl 1235.51012

Summary: New upper bounds on the smallest size \(t_2(2,q)\) of a complete arc in the projective plane \(PG(2,q)\) are obtained for \(853\leq q\leq 5107\) and \(q\in T_1\cup T_2\), where \(T_1=\{173,181,193,229,243,257,271,277,293,343,373,409,443, 449,457,461,463,467,479,487,491,499,529,563,569,571,577,587,593,599,601,607,613,617,619,631,641,661,673,677,683,691,709\}\), and \(T_2=\{5119,5147,5153,5209,5231,5237, 5261,5279,5281,5303,5347,5641,5843,6011,8192\}\). From these new bounds it follows that for \(q\leq 2593\) and \(q=2693,2753\), the relation \(t_2(2,q)<4.5\sqrt q\) holds. Also, for \(q\leq 5107\) we have \(t_2(2,q)<4.79\sqrt q\). It is shown that for \(23\leq q\leq 5107\) and q\(\in T_2\cup \{2^{14},2^{15},2^{18}\}\), the inequality \(t_2(2,q)<\sqrt q\ln^{0,75}q\) is true. Moreover, the results obtained allow us to conjecture that this estimate holds for all \(q\geq 23\).
The new upper bounds are obtained by finding new small complete arcs with the help of a computer search using randomized greedy algorithms. Also new constructions of complete arcs are proposed. These constructions form families of \(k\)-arcs in \(PG(2,q)\) containing arcs of all sizes \(k\) in a region \(k_{\min}\leq k\leq k_{\max}\), where \(k_{\min}\) is of order \(\tfrac 13 q\) or \(\tfrac 14 q\) while \(k_{\max}\) has order \(\tfrac 12 q\). The completeness of the arcs obtained by the new constructions is proved for \(q\leq 2063\). There is reason to suppose that the arcs are complete for all \(q>2063\). New sizes of complete arcs in \(PG(2,q)\) are presented for \(169\leq q\leq 349\) and \(q=1013,2003\).

MSC:

51E20 Combinatorial structures in finite projective spaces
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abatangelo, V., A class of complete \([(q + 8) / 3]\)-arcs of \(PG(2, q)\), with \(q = 2^h\) and \(h(\geq 6)\) even, Ars Combin., 16, 103-111 (1983) · Zbl 0535.51015
[2] Coolsaet, K.; Sticker, H., Arcs with large conical subsets, Electron. J. Combin., 17 (2010), #R112 · Zbl 1196.51007
[3] 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) · Zbl 1086.51011
[4] A.A. Davydov, G. Faina, S. Marcugini, F. Pambianco, On the spectrum of sizes of complete caps in projective spaces \(\operatorname{PG} ( n , q )\) http://www.moi.math.bas.bg/acct2008/b10.pdf; A.A. Davydov, G. Faina, S. Marcugini, F. Pambianco, On the spectrum of sizes of complete caps in projective spaces \(\operatorname{PG} ( n , q )\) http://www.moi.math.bas.bg/acct2008/b10.pdf
[5] Davydov, 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) · Zbl 1178.51009
[6] A.A. Davydov, G. Faina, S. Marcugini, F. Pambianco, New sizes of complete arcs in \(\operatorname{PG} ( 2 , q )\); A.A. Davydov, G. Faina, S. Marcugini, F. Pambianco, New sizes of complete arcs in \(\operatorname{PG} ( 2 , q )\)
[7] A.A. Davydov, G. Faina, S. Marcugini, F. Pambianco, New sizes of complete arcs in \(\operatorname{PG} ( 2 , q )\) http://arxiv.org/PS_cache/arxiv/pdf/1004/1004.2817v5.pdf; A.A. Davydov, G. Faina, S. Marcugini, F. Pambianco, New sizes of complete arcs in \(\operatorname{PG} ( 2 , q )\) http://arxiv.org/PS_cache/arxiv/pdf/1004/1004.2817v5.pdf · Zbl 1086.51011
[8] Davydov, A. A.; Giulietti, M.; Marcugini, S.; Pambianco, F., On sharply transitive sets in \(PG(2, q)\), Innov. Incidence Geom., 6-7, 139-151 (2009) · Zbl 1178.51010
[9] Davydov, A. A.; Giulietti, M.; Marcugini, S.; Pambianco, F., New inductive constructions of complete caps in \(PG(N, q), q\) even, J. Combin. Des., 18, 176-201 (2010) · Zbl 1277.51008
[10] Davydov, 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) · Zbl 1229.94056
[11] Davydov, A. A.; Marcugini, S.; Pambianco, F., Complete caps in projective spaces \(PG(n, q)\), J. Geom., 80, 23-30 (2004) · Zbl 1059.51012
[12] Davydov, A. A.; Marcugini, S.; Pambianco, F., Complete \((q^2 + q + 8) / 2\)-caps in the spaces \(PG(3, q), q \equiv 2(\operatorname{mod} 3)\) an odd prime, and a complete 20-cap in \(PG(3, 5)\), Des. Codes Cryptogr., 50, 359-372 (2009) · Zbl 1404.51008
[13] A.A. Davydov, S. Marcugini, F. Pambianco, A geometric construction of complete arcs sharing \(( q + 3 ) / 2\); A.A. Davydov, S. Marcugini, F. Pambianco, A geometric construction of complete arcs sharing \(( q + 3 ) / 2\)
[14] Faina, G.; Giulietti, M., On small dense arcs in Galois planes of square order, Discrete Math., 267, 113-125 (2003) · Zbl 1023.51008
[15] Faina, G.; Pambianco, F., A class of complete \(k\)-caps in \(PG(3, q)\) for \(q\) an odd prime, J. Geom., 57, 93-105 (1996) · Zbl 0871.51006
[16] Faina, 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) · Zbl 0917.51016
[17] Faina, 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) · Zbl 0939.51015
[18] Giordano, V., Arcs in cyclic affine planes, Innov. Incidence Geom., 6-7, 203-209 (2009) · Zbl 1181.51008
[19] Giulietti, M., Small complete caps in \(PG(2, q)\) for \(q\) an odd square, J. Geom., 69, 110-116 (2000) · Zbl 0969.51012
[20] Giulietti, M., Small complete caps in Galois affine spaces, J. Algebraic Combin., 25, 149-168 (2007) · Zbl 1115.51005
[21] Giulietti, M., Small complete caps in \(PG(N, q), q\) even, J. Combin. Des., 15, 420-436 (2007) · Zbl 1134.51006
[22] M. Giulietti, G. Korchmáros, S. Marcugini, F. Pambianco, Transitive \(A_6kP G ( 2 , q )\) http://arxiv.org/abs/1108.0358; M. Giulietti, G. Korchmáros, S. Marcugini, F. Pambianco, Transitive \(A_6kP G ( 2 , q )\) http://arxiv.org/abs/1108.0358
[23] Giulietti, M.; Ughi, E., A small complete arc in \(PG(2, q), q = p^2, p \equiv 3(\operatorname{mod} 4)\), Discrete Math., 208-209, 311-318 (1999) · Zbl 0943.51009
[24] Hartman, A.; Raskin, L., Problems and algorithms for covering arrays, Discrete Math., 284, 149-156 (2004) · Zbl 1044.05029
[25] Hirschfeld, J. W.P., Maximum sets in finite projective spaces, (Lloyd, E. K., Surveys in Combinatorics. Surveys in Combinatorics, London Math. Soc. Lecture Note Ser., vol. 82 (1983), Cambridge University Press: Cambridge University Press Cambridge), 55-76 · Zbl 0521.05020
[26] Hirschfeld, J. W.P., Projective Geometries Over Finite Fields (1998), Clarendon Press: Clarendon Press Oxford · Zbl 0899.51002
[27] Hirschfeld, J. W.P.; Storme, L., The packing problem in statistics, coding theory and finite projective spaces, J. Statist. Plann. Inference, 72, 355-380 (1998) · Zbl 0958.51013
[28] Hirschfeld, J. W.P.; Storme, L., The packing problem in statistics, coding theory and finite geometry: update 2001, (Blokhuis, A.; Hirschfeld, J. W.P.; Jungnickel, D.; Thas, J. A., Finite Geometries. Finite Geometries, Proc. of the Fourth Isle of Thorns Conf., Chelwood Gate, 2000. Finite Geometries. Finite Geometries, Proc. of the Fourth Isle of Thorns Conf., Chelwood Gate, 2000, Developments of Mathematics, vol. 3 (2001), Kluwer), 201-246 · Zbl 1025.51012
[29] Keri, G., Types of superregular matrices and the number of \(n\)-arcs and complete \(n\)-arcs in \(PG(r, q)\), J. Combin. Des., 14, 363-390 (2006) · Zbl 1136.51008
[30] Kim, J. H.; Vu, V., Small complete arcs in projective planes, Combinatorica, 23, 311-363 (2003) · Zbl 1027.05015
[31] Korchmáros, G., New examples of complete \(k\)-arcs in \(PG(2, q)\), European J. Combin., 4, 329-334 (1983) · Zbl 0537.51011
[32] Korchmáros, G.; Pace, N., Infinite family of large complete arcs in \(PG(2, q^n)\), with \(q\) odd and \(n > 1\) odd, Des. Codes Cryptogr., 55, 285-296 (2010) · Zbl 1207.51005
[33] Korchmáros, G.; Sonnino, A., Complete arcs arising from conics, Discrete Math., 267, 181-187 (2003) · Zbl 1028.51011
[34] Korchmáros, G.; Sonnino, A., On arcs sharing the maximum number of points with an oval in a Desarguesian plane of odd order, J. Combin. Des., 18, 25-47 (2010) · Zbl 1287.05019
[35] Lisone˘k, P.; Marcugini, S.; Pambianco, F., Constructions of small complete arcs with prescribed symmetry, Contrib. Discrete Math., 3, 14-19 (2008) · Zbl 1189.51007
[36] Lombardo-Radice, L., Sul problema dei \(k\)-archi completi di \(S_{2, q}\), Boll. Unione Mat. Ital., 11, 178-181 (1956) · Zbl 0074.15302
[37] Marcugini, S.; Milani, A.; Pambianco, F., Minimal complete arcs in \(PG(2, q), q \leq 29\), J. Combin. Math. Combin. Comput., 47, 19-29 (2003) · Zbl 1044.51007
[38] S. Marcugini, A. Milani, F. Pambianco, Minimal complete arcs in \(\operatorname{PG} ( 2 , q ), q \leq 32\); S. Marcugini, A. Milani, F. Pambianco, Minimal complete arcs in \(\operatorname{PG} ( 2 , q ), q \leq 32\)
[39] Östergård, P. R.J., Computer search for small complete caps, J. Geom., 69, 172-179 (2000) · Zbl 0969.51013
[40] Pambianco, F., A class of complete \(k\)-caps of small cardinality in projective spaces over fields of characteristic three, Discrete Math., 208-209, 463-468 (1999) · Zbl 0939.51019
[41] Pambianco, F.; Ughi, E., A class of \(k\)-caps having \(k - 2\) points in common with an elliptic quadric and two points on an external line, Australas. J. Combin., 21, 299-310 (2000) · Zbl 0955.51007
[42] Pellegrino, G., Un’osservazione sul problema dei \(k\)-archi completi in \(S_{2, q}\), con \(q \equiv 1(\operatorname{mod} 4)\), Atti Accad. Naz. Lincei Rend., 63, 33-44 (1977)
[43] Pellegrino, G., Sur les \(k\)-arcs complets des plans de Galois d’ordre impair, Ann. Discrete Math., 18, 667-694 (1983) · Zbl 0517.51016
[44] Pellegrino, 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)
[45] Pellegrino, 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)
[46] Polverino, O., Small minimal blocking sets and complete \(k\)-arcs in \(PG(2, p^3)\), Discrete Math., 208-209, 469-476 (1999) · Zbl 0941.51008
[47] Segre, B., Le geometrie di Galois, Ann. Mat. Pura Appl., 48, 1-97 (1959) · Zbl 0093.33604
[48] Segre, B., Ovali e curve \(\sigma\) nei piani di Galois di caratteristica due, Atti Accad. Naz. Lincei Rend., 32, 785-790 (1962) · Zbl 0107.38102
[49] Segre, B., Introduction to Galois geometries, Atti Accad. Naz. Lincei Mem., 8, 133-236 (1967) · Zbl 0194.21503
[50] Szőnyi, T., Small complete arcs in Galois planes, Geom. Dedicata, 18, 161-172 (1985) · Zbl 0566.51012
[51] Szőnyi, T., Note on the order of magnitude of \(k\) for complete \(k\)-arcs in \(PG(2, q)\), Discrete Math., 66, 279-282 (1987) · Zbl 0623.51005
[52] T. Szőnyi, Complete arcs in Galois planes: survey, Quaderni del Seminario di Geometrie Combinatorie, Università degli Studi di Roma, La Sapienza, vol. 94, 1989.; T. Szőnyi, Complete arcs in Galois planes: survey, Quaderni del Seminario di Geometrie Combinatorie, Università degli Studi di Roma, La Sapienza, vol. 94, 1989.
[53] T. Szőnyi, Arcs, caps, codes and 3-independent subsets, in: G. Faina, G. Tallini (Eds.), Giornate di Geometrie Combinatorie, Università degli Studi di Perugia, Perugia, 1993, pp. 57-80.; T. Szőnyi, Arcs, caps, codes and 3-independent subsets, in: G. Faina, G. Tallini (Eds.), Giornate di Geometrie Combinatorie, Università degli Studi di Perugia, Perugia, 1993, pp. 57-80. · Zbl 0791.51010
[54] Thas, J. A., M.D.S. codes and arcs in projective spaces: a survey, Matematiche (Catania), 47, 315-328 (1992) · Zbl 0801.51009
[55] Voloch, J. F., On the completeness of certain plane arcs II, European J. Combin., 11, 491-496 (1990) · Zbl 0712.51008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.