February  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, ().   Google Scholar

[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.  Google Scholar

[3]

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

[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.   Google Scholar

[5]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

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

[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.  Google Scholar

[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., ().   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

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

[20]

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

[21]

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

[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.  Google Scholar

[23]

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

[24]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[30]

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

[31]

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

[32]

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

[33]

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

[34]

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

[35]

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

[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.  Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[39]

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

[40]

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

[41]

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

[42]

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

[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.   Google Scholar

show all references

References:
[1]

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

[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.  Google Scholar

[3]

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

[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.   Google Scholar

[5]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

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

[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.  Google Scholar

[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., ().   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

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

[20]

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

[21]

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

[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.  Google Scholar

[23]

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

[24]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[30]

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

[31]

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

[32]

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

[33]

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

[34]

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

[35]

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

[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.  Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[39]

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

[40]

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

[41]

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

[42]

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

[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.   Google Scholar

[1]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118

[2]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272

[3]

Héctor Barge. Čech cohomology, homoclinic trajectories and robustness of non-saddle sets. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020381

[4]

Meng Chen, Yong Hu, Matteo Penegini. On projective threefolds of general type with small positive geometric genus. Electronic Research Archive, , () : -. doi: 10.3934/era.2020117

[5]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044

[6]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[7]

Reza Lotfi, Zahra Yadegari, Seyed Hossein Hosseini, Amir Hossein Khameneh, Erfan Babaee Tirkolaee, Gerhard-Wilhelm Weber. A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020158

[8]

Federico Rodriguez Hertz, Zhiren Wang. On $ \epsilon $-escaping trajectories in homogeneous spaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 329-357. doi: 10.3934/dcds.2020365

[9]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250

[10]

Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of a Sobolev type impulsive functional evolution system in Banach spaces. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020049

[11]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073

[12]

Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103

2019 Impact Factor: 0.734

Metrics

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

[Back to Top]