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.

[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. 

[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.

[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.

[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.

[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.

[7]

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

[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.

[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.

[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.

[11]

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

[12]

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

[13]

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

[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.

[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.

[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.

[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.

[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.

[19]

A. A. DavydovS. Marcugini and F. Pambianco, New covering codes of radius $mathbb{R}^{N}$, 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.

[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.

[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.

[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.

[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.

[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.

[25]

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

[26]

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

[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.

[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.

[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.

[30]

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

[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.

[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.

[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.

[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.

[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.

[36] J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions, Oxford Univ. Press, Oxford, 1985. 
[37] J. W. P. Hirschfeld, Projective Geometries over Finite Fields, 2$^{nd}$ edition, Oxford Univ. Press, Oxford, 1998. 
[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.

[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.

[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.

[41] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge Univ. Press, 2003.  doi: 10.1017/CBO9780511807077.
[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.

[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.

[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.

[45]

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

[46]

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

[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.

[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.

[49]

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

[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.

[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.

[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.

[53] R. M. Roth, Introduction to Coding Theory, Cambridge, Cambridge Univ. Press, 2006.  doi: 10.1017/CBO9780511808968.
[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.

[55]

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

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.

[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. 

[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.

[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.

[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.

[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.

[7]

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

[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.

[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.

[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.

[11]

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

[12]

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

[13]

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

[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.

[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.

[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.

[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.

[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.

[19]

A. A. DavydovS. Marcugini and F. Pambianco, New covering codes of radius $mathbb{R}^{N}$, 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.

[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.

[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.

[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.

[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.

[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.

[25]

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

[26]

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

[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.

[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.

[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.

[30]

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

[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.

[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.

[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.

[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.

[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.

[36] J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions, Oxford Univ. Press, Oxford, 1985. 
[37] J. W. P. Hirschfeld, Projective Geometries over Finite Fields, 2$^{nd}$ edition, Oxford Univ. Press, Oxford, 1998. 
[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.

[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.

[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.

[41] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge Univ. Press, 2003.  doi: 10.1017/CBO9780511807077.
[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.

[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.

[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.

[45]

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

[46]

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

[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.

[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.

[49]

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

[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.

[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.

[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.

[53] R. M. Roth, Introduction to Coding Theory, Cambridge, Cambridge Univ. Press, 2006.  doi: 10.1017/CBO9780511808968.
[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.

[55]

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

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 and 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 and 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 (222)
  • HTML views (142)
  • Cited by (0)

[Back to Top]