2015, 9(1): 63-85. doi: 10.3934/amc.2015.9.63

Multiple coverings of the farthest-off points with small density from projective geometry

1. 

Department of Mathematics and Informatics, Perugia University, Perugia, 06123

2. 

Institute for Information Transmission Problems (Kharkevich institute), Russian Academy of Sciences, GSP-4, Moscow, 127994, Russian Federation

3. 

Department of Mathematics and Computer Science, University of Perugia, Perugia, 06123, Italy

Received  May 2014 Published  February 2015

In this paper we deal with the special class of covering codes consisting of multiple coverings of the farthest-off points (MCF). In order to measure the quality of an MCF code, we use a natural extension of the notion of density for ordinary covering codes, that is the $\mu$-density for MCF codes; a generalization of the length function for linear covering codes is also introduced. Our main results consist in a number of upper bounds on such a length function, obtained through explicit constructions, especially for the case of covering radius $R=2$. A key tool is the possibility of computing the $\mu$-length function in terms of Projective Geometry over finite fields. In fact, linear $(R,\mu )$-MCF codes with parameters $ [n,n-r,d]_{q}R$ have a geometrical counterpart consisting of special subsets of $n$ points in the projective space $PG(n-r-1,q)$. We introduce such objects under the name of $(\rho,\mu)$-saturating sets and we provide a number of example and existence results. Finally, Almost Perfect MCF (APMCF) codes, that is codes for which each word at distance $R$ from the code belongs to {exactly} $\mu $ spheres centered in codewords, are considered and their connections with uniformly packed codes, two-weight codes, and subgroups of Singer groups are pointed out.
Citation: 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
References:
[1]

N. Anbar, D. Bartoli, M. Giulietti and I. Platoni, Small complete caps from nodal cubics,, preprint, ().

[2]

N. Anbar, D. Bartoli, M. Giulietti and I. Platoni, Small complete caps from singular cubics, II,, J. Algebraic Combin., 41 (2015), 185. doi: 10.1007/s10801-014-0532-7.

[3]

U. Bartocci, Dense $k$-systems in Galois planes,, Boll. Un. Mat. Ital. D(6), 2 (1983), 71.

[4]

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, (2012), 53.

[5]

L. A. Bassalygo, G. V. Zaitsev and V. A. Zinov'ev, Uniformly Packed Codes,, Probl. Inf. Transmis., 10 (1974), 6.

[6]

L. M. Batten and J. M. Dover, Some sets of type $(m,n)$ in cubic order planes,, Des. Codes Cryptogr., 16 (1999), 211. doi: 10.1023/A:1008397209409.

[7]

E. Boros, T. Szőnyi and K. Tichler, On defining sets for projective planes,, Discrete Math., 303 (2005), 17. doi: 10.1016/j.disc.2004.12.015.

[8]

R. A. Brualdi, V. S. Pless and R. M. Wilson, Short codes with a given covering radius,, IEEE Trans. Inform. Theory, 35 (1989), 99. doi: 10.1109/18.42181.

[9]

R. Calderbank, On uniformly packed [n,n-k,4] codes over GF(q) and a class of caps in PG(k-1,q),, J. London Math. Soc., 26 (1982), 365. doi: 10.1112/jlms/s2-26.2.365.

[10]

R. Calderbank and W. M. Kantor, The geometry of two-weight codes,, Bull. London Math. Soc., 18 (1986), 97. doi: 10.1112/blms/18.2.97.

[11]

G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes,, North-Holland, (1997).

[12]

A. A. Davydov, Constructions and families of covering codes and saturated sets of points in projective geometry,, IEEE Trans. Inform. Theory, 41 (1995), 2071. doi: 10.1109/18.476339.

[13]

A. A. Davydov, G. Faina, M. Giulietti, S. Marcugini and F. Pambianco, On constructions and parameters of symmetric configurations $v_k$,, Des. Codes Cryptogr., ().

[14]

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, (2009), 59.

[15]

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. doi: 10.3934/amc.2011.5.119.

[16]

A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Some combinatorial aspects of constructing bipartite-graph codes,, Graphs Combin., 29 (2013), 187. doi: 10.1007/s00373-011-1103-5.

[17]

S. Fanali and M. Giulietti, On the number of rational points of generalized Fermat curves over finite fields,, Int. J. Number Theory, 8 (2012), 1087. doi: 10.1142/S1793042112500650.

[18]

A. Gács and T. Szőnyi, Random constructions and density results,, Des. Codes Cryptogr., 47 (2008), 267. doi: 10.1007/s10623-007-9149-3.

[19]

M. Giulietti, On small dense sets in Galois planes,, Electr. J. Combin., 14 (2007).

[20]

M. Giulietti, Small complete caps in PG(N,q), q even,, J. Combin. Des., 15 (2007), 420. doi: 10.1002/jcd.20131.

[21]

M. Giulietti, The geometry of covering codes: small complete caps and saturating sets in Galois spaces,, in Surveys in Combinatorics, (2013), 51.

[22]

M. Giulietti and F. Pasticci, Quasi-perfect linear codes with minimum distance 4,, IEEE Trans. Inform. Theory, 53 (2007), 1928. doi: 10.1109/TIT.2007.894688.

[23]

M. Giulietti and F. Torres, On dense sets related to plane algebraic curves,, Ars Combinatoria, 72 (2004), 33.

[24]

J. M. Goetals and H. C. Tilborg, Uniformly packed codes,, Philips Res. Repts., 30 (1975), 9.

[25]

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. doi: 10.1007/BF01388486.

[26]

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. doi: 10.1137/S0895480193252100.

[27]

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. doi: 10.2307/2974552.

[28]

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. doi: 10.1016/0097-3165(91)90024-B.

[29]

N. Hamilton and T. Penttila, Sets of type (a,b) from subgroups of L(1,$p^R$),, J. Algebr. Combin., 13 (2001), 67. doi: 10.1023/A:1008775818040.

[30]

J. W. P. Hirschfeld, Projective Geometries over Finite Fields, $2^{nd}$ edition,, Oxford University Press, (1998).

[31]

I. S. Honkala, On the normality of multiple covering codes,, Discrete Math., 125 (1994), 229. doi: 10.1016/0012-365X(94)90164-3.

[32]

I. Honkala and S. Litsyn, Generalizations of the covering radius problem in coding theory,, Bull. Inst. Combin., 17 (1996), 39.

[33]

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

[34]

R. Lidl and H. Niederreiter, Finite Fields,, Addison-Wesley, (1983).

[35]

J. H. van Lint, Codes,, in Handbook of Combinatorics (eds. R. Graham, (1995), 772.

[36]

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. doi: 10.1023/A:1008228721072.

[37]

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.

[38]

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.

[39]

J. Quistorff, On Codes with given minimum distance and covering radius,, Beiträge Algebra Geom., 41 (2000), 469.

[40]

J. Quistorff, Correction: On codes with given minimum distance and covering radius,, Beiträge Algebra Geom., 42 (2001), 601.

[41]

T. Szőnyi, Complete arcs in finite projective geometries,, Ph.D thesis, (1984).

[42]

T. Szőnyi, Complete arcs in Galois planes: a survey,, in Quaderni del Seminario di Geometrie Combinatorie 94, (1989).

[43]

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.

show all references

References:
[1]

N. Anbar, D. Bartoli, M. Giulietti and I. Platoni, Small complete caps from nodal cubics,, preprint, ().

[2]

N. Anbar, D. Bartoli, M. Giulietti and I. Platoni, Small complete caps from singular cubics, II,, J. Algebraic Combin., 41 (2015), 185. doi: 10.1007/s10801-014-0532-7.

[3]

U. Bartocci, Dense $k$-systems in Galois planes,, Boll. Un. Mat. Ital. D(6), 2 (1983), 71.

[4]

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, (2012), 53.

[5]

L. A. Bassalygo, G. V. Zaitsev and V. A. Zinov'ev, Uniformly Packed Codes,, Probl. Inf. Transmis., 10 (1974), 6.

[6]

L. M. Batten and J. M. Dover, Some sets of type $(m,n)$ in cubic order planes,, Des. Codes Cryptogr., 16 (1999), 211. doi: 10.1023/A:1008397209409.

[7]

E. Boros, T. Szőnyi and K. Tichler, On defining sets for projective planes,, Discrete Math., 303 (2005), 17. doi: 10.1016/j.disc.2004.12.015.

[8]

R. A. Brualdi, V. S. Pless and R. M. Wilson, Short codes with a given covering radius,, IEEE Trans. Inform. Theory, 35 (1989), 99. doi: 10.1109/18.42181.

[9]

R. Calderbank, On uniformly packed [n,n-k,4] codes over GF(q) and a class of caps in PG(k-1,q),, J. London Math. Soc., 26 (1982), 365. doi: 10.1112/jlms/s2-26.2.365.

[10]

R. Calderbank and W. M. Kantor, The geometry of two-weight codes,, Bull. London Math. Soc., 18 (1986), 97. doi: 10.1112/blms/18.2.97.

[11]

G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes,, North-Holland, (1997).

[12]

A. A. Davydov, Constructions and families of covering codes and saturated sets of points in projective geometry,, IEEE Trans. Inform. Theory, 41 (1995), 2071. doi: 10.1109/18.476339.

[13]

A. A. Davydov, G. Faina, M. Giulietti, S. Marcugini and F. Pambianco, On constructions and parameters of symmetric configurations $v_k$,, Des. Codes Cryptogr., ().

[14]

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, (2009), 59.

[15]

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. doi: 10.3934/amc.2011.5.119.

[16]

A. A. Davydov, M. Giulietti, S. Marcugini and F. Pambianco, Some combinatorial aspects of constructing bipartite-graph codes,, Graphs Combin., 29 (2013), 187. doi: 10.1007/s00373-011-1103-5.

[17]

S. Fanali and M. Giulietti, On the number of rational points of generalized Fermat curves over finite fields,, Int. J. Number Theory, 8 (2012), 1087. doi: 10.1142/S1793042112500650.

[18]

A. Gács and T. Szőnyi, Random constructions and density results,, Des. Codes Cryptogr., 47 (2008), 267. doi: 10.1007/s10623-007-9149-3.

[19]

M. Giulietti, On small dense sets in Galois planes,, Electr. J. Combin., 14 (2007).

[20]

M. Giulietti, Small complete caps in PG(N,q), q even,, J. Combin. Des., 15 (2007), 420. doi: 10.1002/jcd.20131.

[21]

M. Giulietti, The geometry of covering codes: small complete caps and saturating sets in Galois spaces,, in Surveys in Combinatorics, (2013), 51.

[22]

M. Giulietti and F. Pasticci, Quasi-perfect linear codes with minimum distance 4,, IEEE Trans. Inform. Theory, 53 (2007), 1928. doi: 10.1109/TIT.2007.894688.

[23]

M. Giulietti and F. Torres, On dense sets related to plane algebraic curves,, Ars Combinatoria, 72 (2004), 33.

[24]

J. M. Goetals and H. C. Tilborg, Uniformly packed codes,, Philips Res. Repts., 30 (1975), 9.

[25]

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. doi: 10.1007/BF01388486.

[26]

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. doi: 10.1137/S0895480193252100.

[27]

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. doi: 10.2307/2974552.

[28]

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. doi: 10.1016/0097-3165(91)90024-B.

[29]

N. Hamilton and T. Penttila, Sets of type (a,b) from subgroups of L(1,$p^R$),, J. Algebr. Combin., 13 (2001), 67. doi: 10.1023/A:1008775818040.

[30]

J. W. P. Hirschfeld, Projective Geometries over Finite Fields, $2^{nd}$ edition,, Oxford University Press, (1998).

[31]

I. S. Honkala, On the normality of multiple covering codes,, Discrete Math., 125 (1994), 229. doi: 10.1016/0012-365X(94)90164-3.

[32]

I. Honkala and S. Litsyn, Generalizations of the covering radius problem in coding theory,, Bull. Inst. Combin., 17 (1996), 39.

[33]

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

[34]

R. Lidl and H. Niederreiter, Finite Fields,, Addison-Wesley, (1983).

[35]

J. H. van Lint, Codes,, in Handbook of Combinatorics (eds. R. Graham, (1995), 772.

[36]

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. doi: 10.1023/A:1008228721072.

[37]

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.

[38]

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.

[39]

J. Quistorff, On Codes with given minimum distance and covering radius,, Beiträge Algebra Geom., 41 (2000), 469.

[40]

J. Quistorff, Correction: On codes with given minimum distance and covering radius,, Beiträge Algebra Geom., 42 (2001), 601.

[41]

T. Szőnyi, Complete arcs in finite projective geometries,, Ph.D thesis, (1984).

[42]

T. Szőnyi, Complete arcs in Galois planes: a survey,, in Quaderni del Seminario di Geometrie Combinatorie 94, (1989).

[43]

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.

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

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

[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 & Continuous Dynamical Systems - A, 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]

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

[10]

Maciej J. Capiński, Piotr Zgliczyński. Covering relations and non-autonomous perturbations of ODEs. Discrete & Continuous Dynamical Systems - A, 2006, 14 (2) : 281-293. doi: 10.3934/dcds.2006.14.281

[11]

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

[12]

Roland Hildebrand. Barriers on projective convex sets. Conference Publications, 2011, 2011 (Special) : 672-683. doi: 10.3934/proc.2011.2011.672

[13]

Maciej J. Capiński, Piotr Zgliczyński. Cone conditions and covering relations for topologically normally hyperbolic invariant manifolds. Discrete & Continuous Dynamical Systems - A, 2011, 30 (3) : 641-670. doi: 10.3934/dcds.2011.30.641

[14]

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 & Management Optimization, 2015, 11 (2) : 575-594. doi: 10.3934/jimo.2015.11.575

[15]

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

[16]

Simon Lloyd, Edson Vargas. Critical covering maps without absolutely continuous invariant probability measure. Discrete & Continuous Dynamical Systems - A, 2019, 39 (5) : 2393-2412. doi: 10.3934/dcds.2019101

[17]

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

[18]

J. C. Alvarez Paiva and E. Fernandes. Crofton formulas in projective Finsler spaces. Electronic Research Announcements, 1998, 4: 91-100.

[19]

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

[20]

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

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (3)
  • HTML views (0)
  • Cited by (2)

[Back to Top]