Article Contents
Article Contents

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

• * Corresponding author: Alexander A. Davydov
• 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$.

Mathematics Subject Classification: Primary: 94B05; Secondary: 51E21, 51E22.

 Citation:

• 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$
•  [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. Bartoli, A. A. Davydov, M. Giulietti, S. 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. Boros, T. 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. Brualdi, S. 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. Corless, G. H. Gonnet, D. E. G. Hare, D. 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. Davydov, M. Giulietti, S. 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. Davydov, S. 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. [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. Guo, T. 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. Ho, J. 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.

Figures(1)

Tables(1)