Further results on multiple coverings of the farthest-off points

Previous Article
On self-dual MRD codes
AMC Home
This Issue
Next Article
The non-existence of $(104,22;3,5)$-arcs

August 2016, 10(3): 613-632. doi: 10.3934/amc.2016030

Further results on multiple coverings of the farthest-off points

Daniele Bartoli ^1, , Alexander A. Davydov ^2, , Massimo Giulietti ^3, , Stefano Marcugini ^3, and Fernanda Pambianco ^3,

1.	Department of Mathematics, Ghent University, Gent, 9000, Belgium
2.	Institute for Information Transmission Problems (Kharkevich institute), Russian Academy of Sciences, GSP-4, Moscow, 127994, Russian Federation
3.	Department of Mathematics and Informatics, Perugia University, Perugia, 06123, Italy, Italy, Italy

Received May 2015 Revised October 2015 Published August 2016

Abstract
Related Papers

Multiple coverings of the farthest-off points ($(R,\mu)$-MCF codes) and the corresponding $(\rho,\mu)$-saturating sets in projective spa\-ces $\mathrm{PG}(N,q)$ are considered. We propose some methods which allow us to obtain new small $(1,\mu)$-saturating sets and short $(2,\mu)$-MCF codes with $\mu$-density either equal to 1 (optimal saturating sets and almost perfect MCF-codes) or close to 1 (roughly $1+1/cq$, $c\ge1$). In particular, we provide some algebraic constructions and bounds. Also, we classify minimal and optimal $(1,\mu)$-saturating sets in $\mathrm{PG}(2,q)$, $q$ small.

Keywords: farthest-off points, Multiple coverings, covering density., covering codes, saturating sets in projective spaces.

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

Citation: Daniele Bartoli, Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Further results on multiple coverings of the farthest-off points. Advances in Mathematics of Communications, 2016, 10 (3) : 613-632. doi: 10.3934/amc.2016030

References:

[1]	D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Multiple coverings of the farthest-off points and multiple saturating sets in projective spaces, in Proc. XIII Int. Workshop Algebr. Combin. Coding Theory, ACCT2012, Pomoria, Bulgaria, 2012, 53-59.
[2]	D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Multiple coverings of the farthest-off points with small density from projective geometry, Adv. Math. Commun., 9 (2015), 63-85. doi: 10.3934/amc.2015.9.63.
[3]	D. Bartoli, G. Faina, S. Marcugini and F. Pambianco, On the minimum size of complete arcs and minimal saturating sets in projective planes, J. Geom., 104 (2013) 409-419. doi: 10.1007/s00022-013-0178-y.
[4]	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.
[5]	R. A. Brualdi, S. Litsyn and V. S. Pless, Covering radius, in Handbook of Coding Theory (eds. V.S. Pless, W.C. Huffman and R.A. Brualdi), Elsevier, Amsterdam, 1998, 755-826.
[6]	G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes, North-Holland, Amsterdam, 1997.
[7]	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.
[8]	A. A. Davydov, G. Faina, M. Giulietti, S. Marcugini and F. Pambianco, On constructions and parameters of symmetric configurations $v_k$, Des. Codes Cryptogr., 80 (2016), 125-147. doi: 10.1007/s10623-015-0070-x.
[9]	A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, On the spectrum of possible parameters of symmetric configurations, in Proc. XII Int. Symp. Probl. Redundancy Inform. Control Systems, Saint-Petersburg, Russia, 2009, 59-64.
[10]	A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, New inductive constructions of complete caps in $PG(N,q)$, $q$ even, J. Comb. Des., 18 (2010), 176-201.
[11]	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.
[12]	A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Some combinatorial aspects of constructing bipartite-graph codes, Graphs Combin., 29 (2013), 187-212. doi: 10.1007/s00373-011-1103-5.
[13]	M. Giulietti, On small dense sets in Galois planes, Electr. J. Combin., 14 (2007), #75.
[14]	M. Giulietti, Small complete caps in $PG(N,q), q$ even, J. Combin. Des., 15 (2007), 420-436. doi: 10.1002/jcd.20131.
[15]	M. Giulietti, The geometry of covering codes: small complete caps and saturating sets in Galois spaces, in Surveys in Combinatorics, Cambridge Univ. Press, 2013, 51-90.
[16]	M. Giulietti and F. Pasticci, Quasi-perfect linear codes with minimum distance 4, IEEE Trans. Inform. Theory, 53 (2007), 1928-1935. doi: 10.1109/TIT.2007.894688.
[17]	M. Giulietti and F. Torres, On dense sets related to plane algebraic curves, Ars Combin., 72 (2004), 33-40.
[18]	H. O. Hämäläinen, I. S. Honkala, M. K. Kaikkonen and S. N. Litsyn, Bounds for binary multiple covering codes, Des. Codes Cryptogr., 3 (1993), 251-275. doi: 10.1007/BF01388486.
[19]	H. O. Hämäläinen, I. S. Honkala, S. N. Litsyn and P. R. J. Östergård, Bounds for binary codes that are multiple coverings of the farthest-off points, SIAM J. Discrete Math., 8 (1995), 196-207. doi: 10.1137/S0895480193252100.
[20]	H. Hämäläinen, I. Honkala, S. Litsyn and P. Östergård, Football pools - a game for mathematicians, Amer. Math. Monthly, 102 (1995), 579-588. doi: 10.2307/2974552.
[21]	H. O. Hämäläinen and S. Rankinen, Upper bounds for football pool problems and mixed covering codes, J. Combin. Theory Ser. A, 56 (1991), 84-95. doi: 10.1016/0097-3165(91)90024-B.
[22]	J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Oxford Univ. Press, 1998.
[23]	I. S. Honkala, On the normality of multiple covering codes, Discrete Math., 125 (1994), 229-239. doi: 10.1016/0012-365X(94)90164-3.
[24]	I. Honkala and S. Litsyn, Generalizations of the covering radius problem in coding theory, Bull. Inst. Combin., 17 (1996), 39-46.
[25]	P. R. J. Östergård and H. O. Hämäläinen, A new table of binary/ternary mixed covering codes, Des. Codes Cryptogr., 11 (1997), 151-178. doi: 10.1023/A:1008228721072.
[26]	F. Pambianco, D. Bartoli, G. Faina and S. Marcugini, Classification of the smallest minimal 1-saturating sets in $PG(2,q)$, $q\le 23$, Electron. Notes Discrete Math., 40 (2013) 229-233.
[27]	F. Pambianco, A. A. Davydov, D. Bartoli, M. Giulietti and S. Marcugini, A note on multiple coverings of the farthest-off points, Electron. Notes Discrete Math., 40 (2013) 289-293.
[28]	J. Quistorff, On Codes with given minimum distance and covering radius, Beiträge Algebra Geom., 41 (2000) 469-478.
[29]	J. Quistorff, Correction: On codes with given minimum distance and covering radius, Beiträge Algebra Geom., 42 (2001), 601-611.
[30]	T. Szőnyi, Complete arcs in Galois planes: a survey, in Quaderni del Seminario di Geometrie Combinatorie 94, Univ. degli Studi di Roma "La Sapienza'', Roma, 1989.
[31]	G. J. M. van Wee, G. D. Cohen and S. N. Litsyn, A note on perfect multiple coverings of the Hamming space, IEEE Trans. Inform. Theory, 37 (1991), 678-682.

show all references

References:

[1]	D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Multiple coverings of the farthest-off points and multiple saturating sets in projective spaces, in Proc. XIII Int. Workshop Algebr. Combin. Coding Theory, ACCT2012, Pomoria, Bulgaria, 2012, 53-59.
[2]	D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Multiple coverings of the farthest-off points with small density from projective geometry, Adv. Math. Commun., 9 (2015), 63-85. doi: 10.3934/amc.2015.9.63.
[3]	D. Bartoli, G. Faina, S. Marcugini and F. Pambianco, On the minimum size of complete arcs and minimal saturating sets in projective planes, J. Geom., 104 (2013) 409-419. doi: 10.1007/s00022-013-0178-y.
[4]	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.
[5]	R. A. Brualdi, S. Litsyn and V. S. Pless, Covering radius, in Handbook of Coding Theory (eds. V.S. Pless, W.C. Huffman and R.A. Brualdi), Elsevier, Amsterdam, 1998, 755-826.
[6]	G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes, North-Holland, Amsterdam, 1997.
[7]	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.
[8]	A. A. Davydov, G. Faina, M. Giulietti, S. Marcugini and F. Pambianco, On constructions and parameters of symmetric configurations $v_k$, Des. Codes Cryptogr., 80 (2016), 125-147. doi: 10.1007/s10623-015-0070-x.
[9]	A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, On the spectrum of possible parameters of symmetric configurations, in Proc. XII Int. Symp. Probl. Redundancy Inform. Control Systems, Saint-Petersburg, Russia, 2009, 59-64.
[10]	A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, New inductive constructions of complete caps in $PG(N,q)$, $q$ even, J. Comb. Des., 18 (2010), 176-201.
[11]	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.
[12]	A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Some combinatorial aspects of constructing bipartite-graph codes, Graphs Combin., 29 (2013), 187-212. doi: 10.1007/s00373-011-1103-5.
[13]	M. Giulietti, On small dense sets in Galois planes, Electr. J. Combin., 14 (2007), #75.
[14]	M. Giulietti, Small complete caps in $PG(N,q), q$ even, J. Combin. Des., 15 (2007), 420-436. doi: 10.1002/jcd.20131.
[15]	M. Giulietti, The geometry of covering codes: small complete caps and saturating sets in Galois spaces, in Surveys in Combinatorics, Cambridge Univ. Press, 2013, 51-90.
[16]	M. Giulietti and F. Pasticci, Quasi-perfect linear codes with minimum distance 4, IEEE Trans. Inform. Theory, 53 (2007), 1928-1935. doi: 10.1109/TIT.2007.894688.
[17]	M. Giulietti and F. Torres, On dense sets related to plane algebraic curves, Ars Combin., 72 (2004), 33-40.
[18]	H. O. Hämäläinen, I. S. Honkala, M. K. Kaikkonen and S. N. Litsyn, Bounds for binary multiple covering codes, Des. Codes Cryptogr., 3 (1993), 251-275. doi: 10.1007/BF01388486.
[19]	H. O. Hämäläinen, I. S. Honkala, S. N. Litsyn and P. R. J. Östergård, Bounds for binary codes that are multiple coverings of the farthest-off points, SIAM J. Discrete Math., 8 (1995), 196-207. doi: 10.1137/S0895480193252100.
[20]	H. Hämäläinen, I. Honkala, S. Litsyn and P. Östergård, Football pools - a game for mathematicians, Amer. Math. Monthly, 102 (1995), 579-588. doi: 10.2307/2974552.
[21]	H. O. Hämäläinen and S. Rankinen, Upper bounds for football pool problems and mixed covering codes, J. Combin. Theory Ser. A, 56 (1991), 84-95. doi: 10.1016/0097-3165(91)90024-B.
[22]	J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Oxford Univ. Press, 1998.
[23]	I. S. Honkala, On the normality of multiple covering codes, Discrete Math., 125 (1994), 229-239. doi: 10.1016/0012-365X(94)90164-3.
[24]	I. Honkala and S. Litsyn, Generalizations of the covering radius problem in coding theory, Bull. Inst. Combin., 17 (1996), 39-46.
[25]	P. R. J. Östergård and H. O. Hämäläinen, A new table of binary/ternary mixed covering codes, Des. Codes Cryptogr., 11 (1997), 151-178. doi: 10.1023/A:1008228721072.
[26]	F. Pambianco, D. Bartoli, G. Faina and S. Marcugini, Classification of the smallest minimal 1-saturating sets in $PG(2,q)$, $q\le 23$, Electron. Notes Discrete Math., 40 (2013) 229-233.
[27]	F. Pambianco, A. A. Davydov, D. Bartoli, M. Giulietti and S. Marcugini, A note on multiple coverings of the farthest-off points, Electron. Notes Discrete Math., 40 (2013) 289-293.
[28]	J. Quistorff, On Codes with given minimum distance and covering radius, Beiträge Algebra Geom., 41 (2000) 469-478.
[29]	J. Quistorff, Correction: On codes with given minimum distance and covering radius, Beiträge Algebra Geom., 42 (2001), 601-611.
[30]	T. Szőnyi, Complete arcs in Galois planes: a survey, in Quaderni del Seminario di Geometrie Combinatorie 94, Univ. degli Studi di Roma "La Sapienza'', Roma, 1989.
[31]	G. J. M. van Wee, G. D. Cohen and S. N. Litsyn, A note on perfect multiple coverings of the Hamming space, IEEE Trans. Inform. Theory, 37 (1991), 678-682.

[1]	Daniele Bartoli, Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Multiple coverings of the farthest-off points with small density from projective geometry. Advances in Mathematics of Communications, 2015, 9 (1) : 63-85. doi: 10.3934/amc.2015.9.63
[2]	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
[3]	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
[4]	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
[5]	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
[6]	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
[7]	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
[8]	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
[9]	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, 2022 doi: 10.3934/amc.2021074
[10]	Daniele Bartoli, Lins Denaux. Minimal codewords arising from the incidence of points and hyperplanes in projective spaces. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021061
[11]	Tuvi Etzion, Alexander Vardy. On $q$-analogs of Steiner systems and covering designs. Advances in Mathematics of Communications, 2011, 5 (2) : 161-176. doi: 10.3934/amc.2011.5.161
[12]	Maciej J. Capiński, Piotr Zgliczyński. Covering relations and non-autonomous perturbations of ODEs. Discrete and Continuous Dynamical Systems, 2006, 14 (2) : 281-293. doi: 10.3934/dcds.2006.14.281
[13]	Emily McMillon, Allison Beemer, Christine A. Kelley. Extremal absorbing sets in low-density parity-check codes. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021003
[14]	Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010
[15]	Roland Hildebrand. Barriers on projective convex sets. Conference Publications, 2011, 2011 (Special) : 672-683. doi: 10.3934/proc.2011.2011.672
[16]	Simon Lloyd, Edson Vargas. Critical covering maps without absolutely continuous invariant probability measure. Discrete and Continuous Dynamical Systems, 2019, 39 (5) : 2393-2412. doi: 10.3934/dcds.2019101
[17]	Maciej J. Capiński, Piotr Zgliczyński. Cone conditions and covering relations for topologically normally hyperbolic invariant manifolds. Discrete and Continuous Dynamical Systems, 2011, 30 (3) : 641-670. doi: 10.3934/dcds.2011.30.641
[18]	Belma Yelbay, Ş. İlker Birbil, Kerem Bülbül. The set covering problem revisited: An empirical study of the value of dual information. Journal of Industrial and Management Optimization, 2015, 11 (2) : 575-594. doi: 10.3934/jimo.2015.11.575
[19]	Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83
[20]	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

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Daniele Bartoli Alexander A. Davydov Massimo Giulietti Stefano Marcugini Fernanda Pambianco
on Google Scholar
Daniele Bartoli Alexander A. Davydov Massimo Giulietti Stefano Marcugini Fernanda Pambianco

[Back to Top]