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

2025, Volume 19, Issue 1: 126-139. Doi: 10.3934/amc.2023042

This issue Previous Article Message recovery attack on NTRU using a lattice independent from the public key Next Article The MacWilliams identity for the skew rank metric

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

Published: February 2025

Abstract / Introduction 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:

Full Text(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.