New bounds for covering codes of radius 3 and codimension $ 3t+1 $

Alexander A. Davydov; Stefano Marcugini; Fernanda Pambianco

doi:10.3934/amc.2023042

Article Contents

2023. Doi: 10.3934/amc.2023042

Previous Article Next Article

Early Access

Early Access 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). Early Access publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Early Access articles via the “Early Access” tab for the selected journal.

New bounds for covering codes of radius 3 and codimension $ 3t+1 $

1.
Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow, 127051, Russian Federation
2.
Department of Mathematics and Computer Science, University of Perugia, Perugia, 06123, Italy

^* Corresponding author: Fernanda Pambianco
^* Corresponding author: Fernanda Pambianco

Received: May 2023

Revised: October 2023

Early access: October 2023

Abstract Full Text(HTML) Figure(3) / Table(1) Related Papers Cited by

Abstract

The smallest possible length of a $ q $-ary linear code of covering radius $ R $ and codimension (redundancy) $ r $ is called the length function and is denoted by $ \ell_q(r, R) $. In this work, for $ q $ an arbitrary prime power, we obtain the following new constructive upper bounds on $ \ell_q(3t+1,3) $:

$ \begin{equation*} \begin{split} &\bullet\; \ell_q(r,3)\lessapprox \sqrt[3]{k}\cdot q^{(r-3)/3}\cdot\sqrt[3]{\ln q}, \; r = 3t+1, \; t\ge1, \; q\ge\lceil \mathcal{W}(k)\rceil, \\ &\phantom{\bullet\; }18 <k\le20.339, \; \mathcal{W}(k){\text{ is a decreasing function of }}k ;\\ &\bullet\; \ell_q(r,3)\lessapprox \sqrt[3]{18}\cdot q^{(r-3)/3}\cdot\sqrt[3]{\ln q}, \; r = 3t+1, \; t\ge1, \; q{\text{ large enough}}. \end{split} \end{equation*} $

For $ t = 1 $, we use a one-to-one correspondence between codes of covering radius 3 and codimension 4, and 2-saturating sets in the projective space $ {\mathrm{PG}}(3, q) $. A new construction providing sets of small size is proposed. The codes, obtained by geometrical methods, are taken as the starting ones in the lift-constructions (so-called "$ q^m $-concatenating constructions") to obtain infinite families of codes with radius 3 and growing codimension $ r = 3t + 1 $, $ t\ge1 $. The new bounds are essentially better than the known ones.

Keywords:

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

Citation:

FullText(HTML)

Figure 1. Upper bounds on the length function $ \ell_q(4,3) $ divided by $ \sqrt[3]{q\ln q} $: implicit Bound A (3.5)–(3.6) for $ 8233\le q<10^5 $ (the second curve), computer Bound E (3.25) for $ 13\le q\le8231 $ (the bottom curve) vs the known bound (5.1)–(5.2) for $ 14983\le q<10^5 $ (the top curve)

Download: Full-size image PowerPoint slide

Figure 2. Upper bounds on the length function $ \ell_q(4,3) $ divided by $ \sqrt[3]{q\ln q} $: implicit Bound A (3.5)–(3.6) (the bottom, solid curve), implicit Bound B (3.10)–(3.11) (the second, dashed curve), and explicit Bound C (points $ 1 $, $ 2 $, and $ 3 $ correspond to $ n^{\text{C}}_{4, q}(k)/\sqrt[3]{ q\ln q} $ with $ k = 20.339, \;20 $, and $ 19.7 $, by Table 1) vs the known bound (5.1)–(5.2) (the top, solid curve), $ 10^5< q<5\cdot10^6 $

Download: Full-size image PowerPoint slide

Figure 3. The ratio $ n^{knw}_{4, q}/n^{\mathrm{A}}_{4, q} $ of the known [17] upper bound $ n^{knw}_{4, q} $ (5.1)–(5.2) on the length function $ \ell_q(4,3) $ and the new one $ n^{\mathrm{A}}_{4, q} $ (3.5)–(3.6), $ 14983\le q<5\cdot10^6 $

Download: Full-size image PowerPoint slide

Table 1. Values of $ \lceil \mathcal{W}(k)\rceil $ for $ 18.0001\le k\le 20.340 $ and values of $ n^{\text{C}}_{4, q}(k)/\sqrt[3]{ q\ln q} $, $ n^{knw}_{4, q}/\sqrt[3]{q\ln q} $ (the known bound), $ n^{knw}_{4, q}/n^{\text{C}}_{4, q}(k) $ for $ q = \lceil \mathcal{W}(k)\rceil $, $ 18.0001\le k\le 20.339 $. ($ \mathcal{V} = 1516750 $)

$ k $	$ \lceil \mathcal{W}(k)\rceil $	$ \frac{n^{\text{C}}_{4, q}(k)}{\sqrt[3]{ q\ln q}} $	$ \frac{n^{knw}_{4, q}}{\sqrt[3]{q\ln q}} $	$ \frac{n^{knw}_{4, q}}{n^{\text{C}}_{4, q}(k)} $
20.340	$ 1515738\thickapprox1.516\cdot10^{6}< \mathcal{V} $
20.339	$ 1517567\thickapprox1.518\cdot10^{6}> \mathcal{V} $	2.7368	5.2500	1.9183
20.335	$ 1524915\thickapprox1.525\cdot10^{6}> \mathcal{V} $	2.7367	5.2495	1.9182
20	$ 2374364\thickapprox2.374\cdot10^{6}> \mathcal{V} $	2.7205	5.2087	1.9146
19.7	$ 3820987\thickapprox3.821\cdot10^{6}> \mathcal{V} $	2.7059	5.1716	1.9112
19	$ 19178705\thickapprox1.918\cdot10^{7}> \mathcal{V} $	2.6713	5.0828	1.9027
18.5	$ 171670620\thickapprox1.717\cdot10^{8}> \mathcal{V} $	2.6461	5.0180	1.8963
18.1	$ 30640000001\thickapprox3.064\cdot10^{10}> \mathcal{V} $	2.6258	4.9659	1.8912
18.05	$ 294427001643\thickapprox2.944\cdot10^{11}> \mathcal{V} $	2.6233	4.9593	1.8905
18.01	$ 52060446118120\thickapprox5.206\cdot10^{13}> \mathcal{V} $	2.6212	4.9542	1.8900
18.001	$ \thickapprox7.880\cdot 10^{16}> \mathcal{V} $	2.6208	4.9530	1.8899
18.0001	$ \thickapprox1.109\cdot 10^{20}> \mathcal{V} $	2.6207	4.9529	1.8899

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	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, St. Petersburg, Russia, Sept., (2016), 18-22. doi: 10.1109/RED.2016.7779320.
[2]	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, Lecture Notes in Computer Science, Springer, Cham, 10495 (2017), 1-10. doi: 10.1007/978-3-319-66278-7_1.
[3]	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.
[4]	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.
[5]	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.
[6]	R. A. Brualdi, S. Litsyn and V. S. Pless, Covering radius, Handbook of Coding Theory, North-Holland, Amsterdam, 1, 2 (1998), 755-826.
[7]	H. Chen, L. Qu, C. Li, S. Lyu and L. Xu, Generalized Singleton type upper bounds, preprint, arXiv: 2208.01138.
[8]	G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes, North-Holland Math. Library, 54. Elsevier, Amsterdam, The Netherlands, 1997.
[9]	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.
[10]	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.
[11]	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.
[12]	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.
[13]	A. A. Davydov, S. Marcugini and F. Pambianco, Linear codes with covering radius 2, 3, and saturating sets in projective geometry, IEEE Trans. Inform. Theory, 50 (2004), 537-541. doi: 10.1109/TIT.2004.825503.
[14]	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.
[15]	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), Moscow, Russia, Oct. 2019, IEEE Xplore, (2020), 47-52. doi: 10.1109/REDUNDANCY48165.2019.9003348.
[16]	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 conjecture, 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.
[17]	A. A. Davydov, S. Marcugini and F. Pambianco, Upper bounds on the length function for covering codes with covering radius $R$ and codimension $tR+1$, Adv. Math. Commun., 17 (2023), 98-118. doi: 10.3934/amc.2021074.
[18]	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.
[19]	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.
[20]	L. Denaux, Constructing saturating sets in projective spaces using subgeometries, Des. Codes Cryptogr., 90 (2022), 2113-2144. doi: 10.1007/s10623-021-00951-y.
[21]	L. Denaux, Higgledy-piggledy sets in projective spaces of small dimension, Electron. J. Combin., 29 (2022), 25 pp. doi: 10.37236/10736.
[22]	T. Etzion and L. Storme, Galois geometries and coding theory, Des. Codes Cryptogr., 78 (2016), 311-350. doi: 10.1007/s10623-015-0156-5.
[23]	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, Cambridge University Press, Cambridge, 409 (2013), 51-90. doi: 10.1017/CBO9781139506748.003.
[24]	T. Héger and Z. L. Nagy, Short minimal codes and covering codes via strong blocking sets in projective spaces, IEEE Trans. Inform. Theory, 68 (2022), 881-890. doi: 10.1109/TIT.2021.3123730.
[25]	J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions, Oxford Univ. Press, Oxford, 1985.
[26]	J. W. P. Hirschfeld, Projective Geometries over Finite Fields, 2$^{nd}$ edition, Oxford Math. Monogr., The Clarendon Press, Oxford University Press, New York, 1998.
[27]	J. W. P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces: Update 2001, Finite Geometries, Develop. Math., Kluwer, Dordrecht, 3 (2001), 201-246. doi: 10.1007/978-1-4613-0283-4_13.
[28]	W. C. Huffman and V. S. Pless, Fundamentals of Error-Correcting Codes, Cambridge Univ. Press, 2003. doi: 10.1017/CBO9780511807077.
[29]	A. Jeffrey and H. H. Dai, Handbook of Mathematical Formulas and Integrals, 4$^{th}$ edition, Elsevier, Academic Press, Amsterdam, 2008.
[30]	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.
[31]	A. Lobstein, Covering radius, an online bibliography, (2023), Available from: https://www.lri.fr/lobstein/bib-a-jour.pdf.
[32]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, 3$^{rd}$ edition, North-Holland, Amsterdam, The Netherlands, 1981.
[33]	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.
[34]	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.
[35]	R. Struik, Covering Codes, Ph.D thesis, Eindhoven University of Technology, The Netherlands, 1994.