doi: 10.3934/amc.2021074
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Upper bounds on the length function for covering codes with covering radius $ R $ and codimension $ tR+1 $

1. 

Institute for Information Transmission Problems (Kharkevich institute), Russian Academy of Sciences, Moscow, 127051, Russian Federation

2. 

Department of Mathematics and Computer Science, University of Perugia, Perugia, 06123, Italy

* Corresponding author: Alexander A. Davydov

Received  August 2021 Revised  November 2021 Early access January 2022

The length function
$ \ell_q(r,R) $
is the smallest length of a
$ q $
-ary linear code with codimension (redundancy)
$ r $
and covering radius
$ R $
. In this work, new upper bounds on
$ \ell_q(tR+1,R) $
are obtained in the following forms:
$ \begin{equation*} \begin{split} &(a)\; \ell_q(r,R)\le cq^{(r-R)/R}\cdot\sqrt[R]{\ln q},\; R\ge3,\; r = tR+1,\; t\ge1,\\ &\phantom{(a)\; } q\;{\rm{ is \;an\; arbitrary \;prime\; power}},\; c{\rm{ \;is\; independent \;of\; }}q. \end{split} \end{equation*} $
$ \begin{equation*} \begin{split} &(b)\; \ell_q(r,R)< 3.43Rq^{(r-R)/R}\cdot\sqrt[R]{\ln q},\; R\ge3,\; r = tR+1,\; t\ge1,\\ &\phantom{(b)\; } q\;{\rm{ is \;an\; arbitrary\; prime \;power}},\; q\;{\rm{ is \;large\; enough}}. \end{split} \end{equation*} $
In the literature, for
$ q = (q')^R $
with
$ q' $
a prime power, smaller upper bounds are known; however, when
$ q $
is an arbitrary prime power, the bounds of this paper are better than the known ones.
For
$ t = 1 $
, we use a one-to-one correspondence between
$ [n,n-(R+1)]_qR $
codes and
$ (R-1) $
-saturating
$ n $
-sets in the projective space
$ \mathrm{PG}(R,q) $
. A new construction of such saturating sets providing sets of small size is proposed. Then the
$ [n,n-(R+1)]_qR $
codes, obtained by geometrical methods, are taken as the starting ones in the lift-constructions (so-called "
$ q^m $
-concatenating constructions") for covering codes to obtain infinite families of codes with growing codimension
$ r = tR+1 $
,
$ t\ge1 $
.
Citation: Alexander A. Davydov, Stefano Marcugini, Fernanda Pambianco. Upper bounds on the length function for covering codes with covering radius $ R $ and codimension $ tR+1 $. Advances in Mathematics of Communications, doi: 10.3934/amc.2021074
References:
[1]

S. Aravamuthan and S. Lodha, Covering codes for Hats-on-a-line, Electron. J. Combin., 13 (2006), Research Paper 21, 12 pp. doi: 10.37236/1047.  Google Scholar

[2]

J. T. Astola and R. S. Stanković, Determination of sparse representations of multiple-valued logic functions by using covering codes, J. Mult.-Valued Logic Soft Comput., 19 (2012), 285-306.   Google Scholar

[3]

D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, New upper bounds on the smallest size of a saturating set in a projective plane, 2016 XV Int. Symp. Problems of Redundancy in Inform. and Control Systems (REDUNDANCY), IEEE Xplore (2016), 18–22. doi: 10.1109/RED.2016.7779320.  Google Scholar

[4]

D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, New bounds for linear codes of covering radius 2, Coding Theory and Applications – 5 ICMCTA 2017, Lecture Notes in Computer Science, Springer, Cham, 10495 (2017), 1–10. doi: 10.1007/978-3-319-66278-7_1.  Google Scholar

[5]

D. BartoliA. A. DavydovM. GiuliettiS. Marcugini and F. Pambianco, New bounds for linear codes of covering radii 2 and 3, Crypt. Commun., 11 (2019), 903-920.  doi: 10.1007/s12095-018-0335-0.  Google Scholar

[6]

D. Bartoli, A. A. Davydov, S. Marcugini and F. Pambianco, Tables, bounds and graphics of short linear codes with covering radius 3 and codimension 4 and 5, preprint, arXiv: 1712.07078. Google Scholar

[7]

J. Bierbrauer, Introduction to Coding Theory, Chapman & Hall/CRC, Boca Raton, FL, 2005.  Google Scholar

[8]

J. Bierbrauer and J. Fridrich, Constructing good covering codes for applications in steganography, Transactions on Data Hiding and Multimedia Security III, Lecture Notes in Computer Science, Springer, Cham, 4920 (2008), 1–22. doi: 10.1007/978-3-540-69019-1_1.  Google Scholar

[9]

E. BorosT. Szőnyi and K. Tichler, On defining sets for projective planes, Discrete Math., 303 (2005), 17-31.  doi: 10.1016/j.disc.2004.12.015.  Google Scholar

[10]

R. C. Bose and R. C. Burton, A characterization of flat spaces in a finite geometry and the uniqueness of the Hamming and McDonald codes, J. Comb. Theory, 1 (1966), 96-104.  doi: 10.1016/S0021-9800(66)80007-8.  Google Scholar

[11]

R. A. BrualdiS. Litsyn and V. Pless, Covering radius, Handbook of Coding Theory, North-Holland, Amsterdam, 1 (1998), 755-826.   Google Scholar

[12]

H. Chen, List-decodable codes and covering codes, arXiv: 2109.02818 Google Scholar

[13]

G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes, North-Holland Mathematical Library, 54. North-Holland Publishing Co., Amsterdam, 1997.  Google Scholar

[14]

R. M. CorlessG. H. GonnetD. E. G. HareD. J. Jeffrey and D. E. Knuth, On the Lambert $W$ function (PostScript), Adv. Computat. Math., 5 (1996), 329-359.  doi: 10.1007/BF02124750.  Google Scholar

[15]

A. A. Davydov, Construction of linear covering codes, Probl. Inform. Transmiss., 26 (1990), 317–331, Available from: http://iitp.ru/upload/publications/6833/ConstrCoverCodes.pdf.  Google Scholar

[16]

A. A. Davydov, Constructions and families of covering codes and saturated sets of points in projective geometry, IEEE Trans. Inform. Theory, 41 (1995), 2071-2080.  doi: 10.1109/18.476339.  Google Scholar

[17]

A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Linear covering codes over nonbinary finite fields, Eleventh International Workshop on Algebraic and Combinatorial Coding Theory, (2008), 70–75, Available from: http://www.moi.math.bas.bg/acct2008/b12.pdf. Google Scholar

[18]

A. A. DavydovM. GiuliettiS. Marcugini and F. Pambianco, Linear nonbinary covering codes and saturating sets in projective spaces, Adv. Math. Commun., 5 (2011), 119-147.  doi: 10.3934/amc.2011.5.119.  Google Scholar

[19]

A. A. DavydovS. Marcugini and F. Pambianco, New covering codes of radius $R$, codimension $tR$ and $tR+\frac{R}{2}$, and saturating sets in projective spaces, Des. Codes Cryptogr., 87 (2019), 2771-2792.  doi: 10.1007/s10623-019-00649-2.  Google Scholar

[20]

A. A. Davydov, S. Marcugini and F. Pambianco, New bounds for linear codes of covering radius 3 and 2-saturating sets in projective spaces, Proc. 2019 XVI Int. Symp. Problems Redundancy Inform. Control Systems (REDUNDANCY), IEEE Xplore (2020), 47–52. doi: 10.1109/REDUNDANCY48165.2019.9003348.  Google Scholar

[21]

A. A. Davydov, S. Marcugini and F. Pambianco, Bounds for complete arcs in ${\mathrm{PG}}(3, q)$ and covering codes of radius 3, codimension 4, under a certain probabilistic onjecture, Computational Science and Its Applications–ICCSA 2020, Lecture Notes in Computer Science, Springer, Cham, 12249 (2020), 107–122. doi: 10.1007/978-3-030-58799-4_8.  Google Scholar

[22]

A. A. Davydov and P. R. J. Östergård, On saturating sets in small projective geometries, European J. Combin., 21 (2000), 563-570.  doi: 10.1006/eujc.1999.0373.  Google Scholar

[23]

A. A. Davydov and P. R. J. Östergård, Linear codes with covering radius $R = 2, 3$ and codimension $tR$, IEEE Trans. Inform. Theory, 47 (2001), 416-421.  doi: 10.1109/18.904551.  Google Scholar

[24]

A. A. Davydov and P. R. J. Östergård, Linear codes with covering radius 3, Des. Codes Cryptogr., 54 (2010), 253-271.  doi: 10.1007/s10623-009-9322-y.  Google Scholar

[25]

L. Denaux, Constructing saturating sets in projective spaces using subgeometries, Des. Codes Cryptogr., 2021. doi: 10.1007/s10623-021-00951-y.  Google Scholar

[26]

L. Denaux, Higgledy-piggledy sets in projective spaces of small dimension, arXiv: 2109.08572. Google Scholar

[27]

T. Etzion and L. Storme, Galois geometries and coding theory, Des. Codes Cryptogr., 78 (2016), 311-350.  doi: 10.1007/s10623-015-0156-5.  Google Scholar

[28]

G. Exoo, V. Junnila, T. Laihonen and S. Ranto, Constructions for identifying codes, Proc. XI Int. Workshop Algebraic Combin. Coding Theory, ACCT2008, Pamporovo, Bulgaria, (2008), 92–98. Available from: http://www.moi.math.bas.bg/acct2008/b16.pdf. Google Scholar

[29]

F. Galand and G. Kabatiansky, Information hiding by coverings, Proc. 2003 IEEE Inform. Theory Workshop (Cat. No. 03EX674), IEEE Xplore (2003), 151–154. doi: 10.1109/ITW.2003.1216717.  Google Scholar

[30]

F. Galand and G. Kabatiansky, Coverings, centered codes, and combinatorial steganography, Probl. Inf. Transm., 45 (2009), 289-294.  doi: 10.1134/S0032946009030107.  Google Scholar

[31]

C. Garcia and C. Peyrat, Large Cayley graphs on an abelian group, Discrete Appl. Math., 75 (1997), 125-133.  doi: 10.1016/S0166-218X(96)00084-4.  Google Scholar

[32]

M. Giulietti, The geometry of covering codes: Small complete caps and saturating sets in Galois spaces, Surveys in Combinatorics 2013, London Math. Soc., Lecture Note Series, 409 (2013), 51–90. doi: 10.1017/CBO9781139506748.003.  Google Scholar

[33]

R. L. Graham and N. J. A. Sloane, On the covering radius of codes, IEEE Trans. Inform. Theory, 31 (1985), 385-401.  doi: 10.1109/TIT.1985.1057039.  Google Scholar

[34]

Q. GuoT. Johansson and C. Löndahl, Solving LPN using covering codes, J. Cryptology, 33 (2020), 1-33.  doi: 10.1007/s00145-019-09338-8.  Google Scholar

[35]

T. Héger and Z. L. Nagy, Short minimal codes and covering codes via strong blocking sets in projective spaces, IEEE Trans. Inform. Theory, (2021), 1–1. doi: 10.1109/TIT.2021.3123730.  Google Scholar

[36] J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions, Oxford Univ. Press, Oxford, 1985.   Google Scholar
[37] J. W. P. Hirschfeld, Projective Geometries over Finite Fields, 2$^{nd}$ edition, Oxford Univ. Press, Oxford, 1998.   Google Scholar
[38]

J. W. P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces: Update 2001, Finite Geometries, Develop. Math., 3, Kluwer, Dordrecht, (2001), 201–246. doi: 10.1007/978-1-4613-0283-4_13.  Google Scholar

[39]

J. W. P. Hirschfeld and J. A. Thas, Open problems in finite projective spaces, Finite Fields Appl., 32 (2015), 44-81.  doi: 10.1016/j.ffa.2014.10.006.  Google Scholar

[40]

C. T. HoJ. Bruck and R. Agrawal, Partial-sum queries in OLAP data cubes using covering codes, IEEE Trans. Computers, 47 (1998), 1326-1340.  doi: 10.1109/12.737680.  Google Scholar

[41] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge Univ. Press, 2003.  doi: 10.1017/CBO9780511807077.  Google Scholar
[42]

G. Kiss, I. Kovács, K. Kutnar, J. Ruff and P. Šparl, A note on a geometric construction of large Cayley graphs of given degree and diameter, Stud. Univ. Babe\c{s}–Bolyai, Math., 54 (2009), 77–84. Available from: http://www.cs.ubbcluj.ro/ studia-m/2009-3/kiss.pdf.  Google Scholar

[43]

A. Klein and L. Storme, Applications of finite geometry in coding theory and cryptography, Information Security, Coding Theory and Related Combinatorics, 29 (2011), 38-58.  doi: 10.3233/978-1-60750-663-8-38.  Google Scholar

[44]

C. E. Koksal, An analysis of blocking switches using error control codes, IEEE Trans. Inform. Theory, 53 (2007), 2892-2897.  doi: 10.1109/TIT.2007.901191.  Google Scholar

[45]

S. J. Kovács, Small saturated sets in finite projective planes, Rend. Mat. Appl., Ser. Ⅶ, 12 (1992), 157–164.  Google Scholar

[46]

T. K. Laihonen, Sequences of optimal identifying codes, IEEE Trans. Inform. Theory, 48 (2002), 774-776.  doi: 10.1109/18.986043.  Google Scholar

[47]

I. Landjev and L. Storme, Galois geometry and coding theory, Current Research Topics in Galois geometry, Chapter 8, NOVA Academic, New York, 2011,187–214. Google Scholar

[48]

H. W. Lenstra, Jr., and G. Seroussi, On hats and other covers, Proc. IEEE Int. Symp. Inform. Theory, IEEE Xplore, Lausanne, Switzerland, (2002), 342–342. doi: 10.1109/ISIT.2002.1023614.  Google Scholar

[49]

A. Lobstein, Covering radius, 2021, an online bibliography, Available from: https://www.lri.fr/ lobstein/bib-a-jour.pdf Google Scholar

[50]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.  Google Scholar

[51]

B. Mennink and S. Neves, On the resilience of Even-Mansour to invariant permutations, Des. Codes Cryptogr., 89 (2021), 859-893.  doi: 10.1007/s10623-021-00850-2.  Google Scholar

[52]

Z. L. Nagy, Saturating sets in projective planes and hypergraph covers, Discrete Math., 341 (2018), 1078-1083.  doi: 10.1016/j.disc.2018.01.011.  Google Scholar

[53] R. M. Roth, Introduction to Coding Theory, Cambridge, Cambridge Univ. Press, 2006.  doi: 10.1017/CBO9780511808968.  Google Scholar
[54]

A. Sonnino, Transitive $PSL(2, 7)$-invariant 42-arcs in 3-dimensional projective spaces, Des. Codes Cryptogr., 72 (2014), 455-463.  doi: 10.1007/s10623-012-9778-z.  Google Scholar

[55]

R. Struik, Covering Codes, Ph.D thesis, Eindhoven University of Technology, The Netherlands, 1994. doi: 10.6100/IR425174.  Google Scholar

show all references

References:
[1]

S. Aravamuthan and S. Lodha, Covering codes for Hats-on-a-line, Electron. J. Combin., 13 (2006), Research Paper 21, 12 pp. doi: 10.37236/1047.  Google Scholar

[2]

J. T. Astola and R. S. Stanković, Determination of sparse representations of multiple-valued logic functions by using covering codes, J. Mult.-Valued Logic Soft Comput., 19 (2012), 285-306.   Google Scholar

[3]

D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, New upper bounds on the smallest size of a saturating set in a projective plane, 2016 XV Int. Symp. Problems of Redundancy in Inform. and Control Systems (REDUNDANCY), IEEE Xplore (2016), 18–22. doi: 10.1109/RED.2016.7779320.  Google Scholar

[4]

D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, New bounds for linear codes of covering radius 2, Coding Theory and Applications – 5 ICMCTA 2017, Lecture Notes in Computer Science, Springer, Cham, 10495 (2017), 1–10. doi: 10.1007/978-3-319-66278-7_1.  Google Scholar

[5]

D. BartoliA. A. DavydovM. GiuliettiS. Marcugini and F. Pambianco, New bounds for linear codes of covering radii 2 and 3, Crypt. Commun., 11 (2019), 903-920.  doi: 10.1007/s12095-018-0335-0.  Google Scholar

[6]

D. Bartoli, A. A. Davydov, S. Marcugini and F. Pambianco, Tables, bounds and graphics of short linear codes with covering radius 3 and codimension 4 and 5, preprint, arXiv: 1712.07078. Google Scholar

[7]

J. Bierbrauer, Introduction to Coding Theory, Chapman & Hall/CRC, Boca Raton, FL, 2005.  Google Scholar

[8]

J. Bierbrauer and J. Fridrich, Constructing good covering codes for applications in steganography, Transactions on Data Hiding and Multimedia Security III, Lecture Notes in Computer Science, Springer, Cham, 4920 (2008), 1–22. doi: 10.1007/978-3-540-69019-1_1.  Google Scholar

[9]

E. BorosT. Szőnyi and K. Tichler, On defining sets for projective planes, Discrete Math., 303 (2005), 17-31.  doi: 10.1016/j.disc.2004.12.015.  Google Scholar

[10]

R. C. Bose and R. C. Burton, A characterization of flat spaces in a finite geometry and the uniqueness of the Hamming and McDonald codes, J. Comb. Theory, 1 (1966), 96-104.  doi: 10.1016/S0021-9800(66)80007-8.  Google Scholar

[11]

R. A. BrualdiS. Litsyn and V. Pless, Covering radius, Handbook of Coding Theory, North-Holland, Amsterdam, 1 (1998), 755-826.   Google Scholar

[12]

H. Chen, List-decodable codes and covering codes, arXiv: 2109.02818 Google Scholar

[13]

G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes, North-Holland Mathematical Library, 54. North-Holland Publishing Co., Amsterdam, 1997.  Google Scholar

[14]

R. M. CorlessG. H. GonnetD. E. G. HareD. J. Jeffrey and D. E. Knuth, On the Lambert $W$ function (PostScript), Adv. Computat. Math., 5 (1996), 329-359.  doi: 10.1007/BF02124750.  Google Scholar

[15]

A. A. Davydov, Construction of linear covering codes, Probl. Inform. Transmiss., 26 (1990), 317–331, Available from: http://iitp.ru/upload/publications/6833/ConstrCoverCodes.pdf.  Google Scholar

[16]

A. A. Davydov, Constructions and families of covering codes and saturated sets of points in projective geometry, IEEE Trans. Inform. Theory, 41 (1995), 2071-2080.  doi: 10.1109/18.476339.  Google Scholar

[17]

A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Linear covering codes over nonbinary finite fields, Eleventh International Workshop on Algebraic and Combinatorial Coding Theory, (2008), 70–75, Available from: http://www.moi.math.bas.bg/acct2008/b12.pdf. Google Scholar

[18]

A. A. DavydovM. GiuliettiS. Marcugini and F. Pambianco, Linear nonbinary covering codes and saturating sets in projective spaces, Adv. Math. Commun., 5 (2011), 119-147.  doi: 10.3934/amc.2011.5.119.  Google Scholar

[19]

A. A. DavydovS. Marcugini and F. Pambianco, New covering codes of radius $R$, codimension $tR$ and $tR+\frac{R}{2}$, and saturating sets in projective spaces, Des. Codes Cryptogr., 87 (2019), 2771-2792.  doi: 10.1007/s10623-019-00649-2.  Google Scholar

[20]

A. A. Davydov, S. Marcugini and F. Pambianco, New bounds for linear codes of covering radius 3 and 2-saturating sets in projective spaces, Proc. 2019 XVI Int. Symp. Problems Redundancy Inform. Control Systems (REDUNDANCY), IEEE Xplore (2020), 47–52. doi: 10.1109/REDUNDANCY48165.2019.9003348.  Google Scholar

[21]

A. A. Davydov, S. Marcugini and F. Pambianco, Bounds for complete arcs in ${\mathrm{PG}}(3, q)$ and covering codes of radius 3, codimension 4, under a certain probabilistic onjecture, Computational Science and Its Applications–ICCSA 2020, Lecture Notes in Computer Science, Springer, Cham, 12249 (2020), 107–122. doi: 10.1007/978-3-030-58799-4_8.  Google Scholar

[22]

A. A. Davydov and P. R. J. Östergård, On saturating sets in small projective geometries, European J. Combin., 21 (2000), 563-570.  doi: 10.1006/eujc.1999.0373.  Google Scholar

[23]

A. A. Davydov and P. R. J. Östergård, Linear codes with covering radius $R = 2, 3$ and codimension $tR$, IEEE Trans. Inform. Theory, 47 (2001), 416-421.  doi: 10.1109/18.904551.  Google Scholar

[24]

A. A. Davydov and P. R. J. Östergård, Linear codes with covering radius 3, Des. Codes Cryptogr., 54 (2010), 253-271.  doi: 10.1007/s10623-009-9322-y.  Google Scholar

[25]

L. Denaux, Constructing saturating sets in projective spaces using subgeometries, Des. Codes Cryptogr., 2021. doi: 10.1007/s10623-021-00951-y.  Google Scholar

[26]

L. Denaux, Higgledy-piggledy sets in projective spaces of small dimension, arXiv: 2109.08572. Google Scholar

[27]

T. Etzion and L. Storme, Galois geometries and coding theory, Des. Codes Cryptogr., 78 (2016), 311-350.  doi: 10.1007/s10623-015-0156-5.  Google Scholar

[28]

G. Exoo, V. Junnila, T. Laihonen and S. Ranto, Constructions for identifying codes, Proc. XI Int. Workshop Algebraic Combin. Coding Theory, ACCT2008, Pamporovo, Bulgaria, (2008), 92–98. Available from: http://www.moi.math.bas.bg/acct2008/b16.pdf. Google Scholar

[29]

F. Galand and G. Kabatiansky, Information hiding by coverings, Proc. 2003 IEEE Inform. Theory Workshop (Cat. No. 03EX674), IEEE Xplore (2003), 151–154. doi: 10.1109/ITW.2003.1216717.  Google Scholar

[30]

F. Galand and G. Kabatiansky, Coverings, centered codes, and combinatorial steganography, Probl. Inf. Transm., 45 (2009), 289-294.  doi: 10.1134/S0032946009030107.  Google Scholar

[31]

C. Garcia and C. Peyrat, Large Cayley graphs on an abelian group, Discrete Appl. Math., 75 (1997), 125-133.  doi: 10.1016/S0166-218X(96)00084-4.  Google Scholar

[32]

M. Giulietti, The geometry of covering codes: Small complete caps and saturating sets in Galois spaces, Surveys in Combinatorics 2013, London Math. Soc., Lecture Note Series, 409 (2013), 51–90. doi: 10.1017/CBO9781139506748.003.  Google Scholar

[33]

R. L. Graham and N. J. A. Sloane, On the covering radius of codes, IEEE Trans. Inform. Theory, 31 (1985), 385-401.  doi: 10.1109/TIT.1985.1057039.  Google Scholar

[34]

Q. GuoT. Johansson and C. Löndahl, Solving LPN using covering codes, J. Cryptology, 33 (2020), 1-33.  doi: 10.1007/s00145-019-09338-8.  Google Scholar

[35]

T. Héger and Z. L. Nagy, Short minimal codes and covering codes via strong blocking sets in projective spaces, IEEE Trans. Inform. Theory, (2021), 1–1. doi: 10.1109/TIT.2021.3123730.  Google Scholar

[36] J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions, Oxford Univ. Press, Oxford, 1985.   Google Scholar
[37] J. W. P. Hirschfeld, Projective Geometries over Finite Fields, 2$^{nd}$ edition, Oxford Univ. Press, Oxford, 1998.   Google Scholar
[38]

J. W. P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces: Update 2001, Finite Geometries, Develop. Math., 3, Kluwer, Dordrecht, (2001), 201–246. doi: 10.1007/978-1-4613-0283-4_13.  Google Scholar

[39]

J. W. P. Hirschfeld and J. A. Thas, Open problems in finite projective spaces, Finite Fields Appl., 32 (2015), 44-81.  doi: 10.1016/j.ffa.2014.10.006.  Google Scholar

[40]

C. T. HoJ. Bruck and R. Agrawal, Partial-sum queries in OLAP data cubes using covering codes, IEEE Trans. Computers, 47 (1998), 1326-1340.  doi: 10.1109/12.737680.  Google Scholar

[41] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge Univ. Press, 2003.  doi: 10.1017/CBO9780511807077.  Google Scholar
[42]

G. Kiss, I. Kovács, K. Kutnar, J. Ruff and P. Šparl, A note on a geometric construction of large Cayley graphs of given degree and diameter, Stud. Univ. Babe\c{s}–Bolyai, Math., 54 (2009), 77–84. Available from: http://www.cs.ubbcluj.ro/ studia-m/2009-3/kiss.pdf.  Google Scholar

[43]

A. Klein and L. Storme, Applications of finite geometry in coding theory and cryptography, Information Security, Coding Theory and Related Combinatorics, 29 (2011), 38-58.  doi: 10.3233/978-1-60750-663-8-38.  Google Scholar

[44]

C. E. Koksal, An analysis of blocking switches using error control codes, IEEE Trans. Inform. Theory, 53 (2007), 2892-2897.  doi: 10.1109/TIT.2007.901191.  Google Scholar

[45]

S. J. Kovács, Small saturated sets in finite projective planes, Rend. Mat. Appl., Ser. Ⅶ, 12 (1992), 157–164.  Google Scholar

[46]

T. K. Laihonen, Sequences of optimal identifying codes, IEEE Trans. Inform. Theory, 48 (2002), 774-776.  doi: 10.1109/18.986043.  Google Scholar

[47]

I. Landjev and L. Storme, Galois geometry and coding theory, Current Research Topics in Galois geometry, Chapter 8, NOVA Academic, New York, 2011,187–214. Google Scholar

[48]

H. W. Lenstra, Jr., and G. Seroussi, On hats and other covers, Proc. IEEE Int. Symp. Inform. Theory, IEEE Xplore, Lausanne, Switzerland, (2002), 342–342. doi: 10.1109/ISIT.2002.1023614.  Google Scholar

[49]

A. Lobstein, Covering radius, 2021, an online bibliography, Available from: https://www.lri.fr/ lobstein/bib-a-jour.pdf Google Scholar

[50]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.  Google Scholar

[51]

B. Mennink and S. Neves, On the resilience of Even-Mansour to invariant permutations, Des. Codes Cryptogr., 89 (2021), 859-893.  doi: 10.1007/s10623-021-00850-2.  Google Scholar

[52]

Z. L. Nagy, Saturating sets in projective planes and hypergraph covers, Discrete Math., 341 (2018), 1078-1083.  doi: 10.1016/j.disc.2018.01.011.  Google Scholar

[53] R. M. Roth, Introduction to Coding Theory, Cambridge, Cambridge Univ. Press, 2006.  doi: 10.1017/CBO9780511808968.  Google Scholar
[54]

A. Sonnino, Transitive $PSL(2, 7)$-invariant 42-arcs in 3-dimensional projective spaces, Des. Codes Cryptogr., 72 (2014), 455-463.  doi: 10.1007/s10623-012-9778-z.  Google Scholar

[55]

R. Struik, Covering Codes, Ph.D thesis, Eindhoven University of Technology, The Netherlands, 1994. doi: 10.6100/IR425174.  Google Scholar

Figure 1.  The sizes $ \overline{t}(3,q) $ of the smallest known complete arcs in $ \mathrm{PG}(3,q) $ (bottom curve) vs upper bounds of Theorem 6.10 and Theorem 3.3 (top curve) for $ R = 3 $, $ t = 1 $; the sizes and bounds are divided by $ \sqrt[3]{q\ln q} $; $ \lambda = 3 $
Table 1.  Examples of values connected with upper bounds of Theorem 6.10 and Theorem 3.3 for $ t = 1 $; $ Q_0\in\{5\cdot10^4,15\cdot10^4\} $, $ E = e^{R-1} $
$ R \\E$ $ \lambda $ $ \Upsilon_{\lambda,R}(E) $ $ Q_{\lambda,R} $ $ C_{\lambda,R} $ $ \Omega_{\lambda,R}(Q_{0})\\Q_0= 5\cdot10^4 $ $ \Omega_{\lambda,R}(Q_0) \\Q_0=15\cdot10^4$ $ D_{\lambda,R} $
3 2.35 2.25 1007 9.50 6.43 6.17 5.61
7.39 3 3.67 7186 7.14 5.90 5.60 5
$ \lambda_{\min}= $3.302 4.44 14974 6.69 5.93 5.58 $ 4.953=D^{\min}_R =1.651R$
4 2.2 1.91 6826 25.9 18.49 16.42 11.22
20.1 2.5 2.80 61724 16.5 14.30 8.64
$ \lambda_{\min}= 4.120$ 12.55 118409572 6.89 $ 5.493=D^{\min}_R =1.373R$
5 2.3 1.59 21242 84.3 68.53 55.4 23.74
54.6 2.5 2.22 283935 45.1 17.86
$ \lambda_{\min}= 4.743$ 28.72 $ 5.929=D^{\min}_R =1.186R$
6 2.5 1.35 37774 337 304.6 217.7 46.73
148 $ \lambda_{\min}= 5.277$ 56.67 $ 6.333=D^{\min}_R =1.056R$
7 2.95 1.80 9125037 265 56.48
403 $ \lambda_{\min}= 5.765$ 100.5 $ 6.726=D^{\min}_R =0.961R$
$ R \\E$ $ \lambda $ $ \Upsilon_{\lambda,R}(E) $ $ Q_{\lambda,R} $ $ C_{\lambda,R} $ $ \Omega_{\lambda,R}(Q_{0})\\Q_0= 5\cdot10^4 $ $ \Omega_{\lambda,R}(Q_0) \\Q_0=15\cdot10^4$ $ D_{\lambda,R} $
3 2.35 2.25 1007 9.50 6.43 6.17 5.61
7.39 3 3.67 7186 7.14 5.90 5.60 5
$ \lambda_{\min}= $3.302 4.44 14974 6.69 5.93 5.58 $ 4.953=D^{\min}_R =1.651R$
4 2.2 1.91 6826 25.9 18.49 16.42 11.22
20.1 2.5 2.80 61724 16.5 14.30 8.64
$ \lambda_{\min}= 4.120$ 12.55 118409572 6.89 $ 5.493=D^{\min}_R =1.373R$
5 2.3 1.59 21242 84.3 68.53 55.4 23.74
54.6 2.5 2.22 283935 45.1 17.86
$ \lambda_{\min}= 4.743$ 28.72 $ 5.929=D^{\min}_R =1.186R$
6 2.5 1.35 37774 337 304.6 217.7 46.73
148 $ \lambda_{\min}= 5.277$ 56.67 $ 6.333=D^{\min}_R =1.056R$
7 2.95 1.80 9125037 265 56.48
403 $ \lambda_{\min}= 5.765$ 100.5 $ 6.726=D^{\min}_R =0.961R$
[1]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119

[2]

Roland Hildebrand. Barriers on projective convex sets. Conference Publications, 2011, 2011 (Special) : 672-683. doi: 10.3934/proc.2011.2011.672

[3]

Steve Hofmann, Dorina Mitrea, Marius Mitrea, Andrew J. Morris. Square function estimates in spaces of homogeneous type and on uniformly rectifiable Euclidean sets. Electronic Research Announcements, 2014, 21: 8-18. doi: 10.3934/era.2014.21.8

[4]

Manish K. Gupta, Chinnappillai Durairajan. On the covering radius of some modular codes. Advances in Mathematics of Communications, 2014, 8 (2) : 129-137. doi: 10.3934/amc.2014.8.129

[5]

Ivan Landjev. On blocking sets in projective Hjelmslev planes. Advances in Mathematics of Communications, 2007, 1 (1) : 65-81. doi: 10.3934/amc.2007.1.65

[6]

J. C. Alvarez Paiva and E. Fernandes. Crofton formulas in projective Finsler spaces. Electronic Research Announcements, 1998, 4: 91-100.

[7]

Rafael Arce-Nazario, Francis N. Castro, Jose Ortiz-Ubarri. On the covering radius of some binary cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 329-338. doi: 10.3934/amc.2017025

[8]

Otávio J. N. T. N. dos Santos, Emerson L. Monte Carmelo. A connection between sumsets and covering codes of a module. Advances in Mathematics of Communications, 2018, 12 (3) : 595-605. doi: 10.3934/amc.2018035

[9]

Feng Luo. Geodesic length functions and Teichmuller spaces. Electronic Research Announcements, 1996, 2: 34-41.

[10]

Jesús Carrillo-Pacheco, Felipe Zaldivar. On codes over FFN$(1,q)$-projective varieties. Advances in Mathematics of Communications, 2016, 10 (2) : 209-220. doi: 10.3934/amc.2016001

[11]

Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127-145. doi: 10.3934/amc.2013.7.127

[12]

Thomas Honold, Ivan Landjev. The dual construction for arcs in projective Hjelmslev spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 11-21. doi: 10.3934/amc.2011.5.11

[13]

Linda Beukemann, Klaus Metsch, Leo Storme. On weighted minihypers in finite projective spaces of square order. Advances in Mathematics of Communications, 2015, 9 (3) : 291-309. doi: 10.3934/amc.2015.9.291

[14]

Domenico Mucci. Maps into projective spaces: Liquid crystal and conformal energies. Discrete & Continuous Dynamical Systems - B, 2012, 17 (2) : 597-635. doi: 10.3934/dcdsb.2012.17.597

[15]

Maciej J. Capiński. Covering relations and the existence of topologically normally hyperbolic invariant sets. Discrete & Continuous Dynamical Systems, 2009, 23 (3) : 705-725. doi: 10.3934/dcds.2009.23.705

[16]

Masaaki Harada, Akihiro Munemasa. Classification of self-dual codes of length 36. Advances in Mathematics of Communications, 2012, 6 (2) : 229-235. doi: 10.3934/amc.2012.6.229

[17]

Masaaki Harada, Akihiro Munemasa. On the covering radii of extremal doubly even self-dual codes. Advances in Mathematics of Communications, 2007, 1 (2) : 251-256. doi: 10.3934/amc.2007.1.251

[18]

Tsonka Baicheva, Iliya Bouyukliev. On the least covering radius of binary linear codes of dimension 6. Advances in Mathematics of Communications, 2010, 4 (3) : 399-404. doi: 10.3934/amc.2010.4.399

[19]

Víctor Jiménez López, Gabriel Soler López. A topological characterization of ω-limit sets for continuous flows on the projective plane. Conference Publications, 2001, 2001 (Special) : 254-258. doi: 10.3934/proc.2001.2001.254

[20]

Dean Crnković, Nina Mostarac, Bernardo G. Rodrigues, Leo Storme. $ s $-PD-sets for codes from projective planes $ \mathrm{PG}(2,2^h) $, $ 5 \leq h\leq 9 $. Advances in Mathematics of Communications, 2021, 15 (3) : 423-440. doi: 10.3934/amc.2020075

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (26)
  • HTML views (29)
  • Cited by (0)

[Back to Top]