American Institute of Mathematical Sciences

Advanced
August  2018, 12(3): 595-605. doi: 10.3934/amc.2018035

A connection between sumsets and covering codes of a module

Otávio J. N. T. N. dos Santos 1, and  Emerson L. Monte Carmelo 2,,

1. 

Universidade Estadual de Mato Grosso do Sul, Unidade de Ponta Porã, Rua Itiberé Vieira, S/N, Ponta Porã-MS, CEP 79907-414, Brazil
2. 

Universidade Estadual de Maringá, Departamento de Matemática, Av. Colombo, 5790 - Campus Universitário, Maringá-PR, CEP 87020-900, Brazil

* Corresponding author: elmcarmelo@uem.br

Received  October 2017 Published  July 2018

Fund Project: The first author is partially supported by FUNDECT/CNPq grant 054/2015
The second author is partially supported by CNPq/MCT grant 311793/2016-0.

In this work we focus on a connection between sumsets and covering codes in an arbitrary finite module. For this purpose, bounds on a new problem on sumsets are obtained from well-known results of additive number theory, namely, the Cauchy-Davenport theorem, the Vosper theorem and a theorem due to Hamidoune-Rødseth. As an application, the approach is able to extend the Blokhuis-Lam theorems and a construction of covering codes by Honkala to an arbitrary module.

Keywords: Sumset, arithmetic progression, covering code, code over a ring, matrix method, bound on code.
Mathematics Subject Classification: Primary: 11T71; Secondary: 11P70, 13M99, 94B75.
Citation: 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
References:
[1]

A. Blokhuis and C. W. H. Lam, More covering by rook domains, J. Combin. Theory Ser. A, 36 (1984), 240-244.  doi: 10.1016/0097-3165(84)90010-4.  Google Scholar

[2]

W. A. Carnielli, On covering and coloring problems for rook domains, Discrete Math., 57 (1985), 9-16.  doi: 10.1016/0012-365X(85)90152-9.  Google Scholar

[3]

W. A. Carnielli, Hyper-rook domain inequalities, Stud. Appl. Math., 82 (1990), 59-69.  doi: 10.1002/sapm199082159.  Google Scholar

[4]

A. Cauchy, Recherches sur les nombres, Oeuvres completes, (2009), 39-63.  doi: 10.1017/CBO9780511702501.004.  Google Scholar

[5]

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

[6]

H. Davenport, On the addition of residue classes, J. London Math. Soc., 10 (1935), 30-32.   Google Scholar

[7]

O. J. N. T. N. dos Santos and E. L. Monte Carmelo, Invariant sets under linear operator and covering codes over modules, Linear Algebra Appl., 444 (2014), 42-52.  doi: 10.1016/j.laa.2013.11.034.  Google Scholar

[8]

P. Erdős, Problems and Results on Combinatorial Number Theory Ⅲ, in Lecture Notes in Math., Springer- Verlag, Berlin, (1977), 43-72.  Google Scholar

[9]

Y. O. Hamidoune and Ø. J. Rødseth, An inverse theorem mod $p$, Acta Arithmetica, 92 (2000), 251-262.  doi: 10.4064/aa-92-3-251-262.  Google Scholar

[10]

I. Honkala, On lengthening of covering codes, Discrete Math., 106/107 (1992), 291-295.  doi: 10.1016/0012-365X(92)90556-U.  Google Scholar

[11]

H. J. L. Kamps and J. H. van Lint, A covering problem, in Combinatorial theory and its applications Ⅱ (Colloquia Mathematica Societatis Jànos Bolyai), North-Holland, Amsterdam, (1970), 679-685.  Google Scholar

[12]

I. N. Nakaoka and O. J. N. T. N. dos Santos, A covering problem over finite rings, Appl. Math. Lett., 23 (2010), 322-326.  doi: 10.1016/j.aml.2009.09.022.  Google Scholar

[13]

I. N. Nakaoka, E. L. Monte Carmelo and O. J. N. T. N. dos Santos, Sharp covering of a module by cyclic submodules, Linear Algebra Appl., 458 (2014), 387-402.  doi: 10.1016/j.laa.2014.06.019.  Google Scholar

[14]

M. B. Nathanson, Additive Number Theory. Inverse Problems and the Geometry of Sumsets, Springer-Verlag, New York, 1996. doi: 10.1007/978-1-4757-3845-2.  Google Scholar

[15]

T. Tao and V. Vu, Additive Combinatorics, Cambridge Studies in Advanced Mathematics, 105 Cambridge University Press, Cambridge, 2006. doi: 10.1017/CBO9780511755149.  Google Scholar

[16]

O. Taussky and J. Todd, Covering theorems for groups, Ann. Soc. Polonaise Math., 21 (1948), 303-305.   Google Scholar

[17]

J. H. van Lint Jr., Covering Radius Problems, M. Sc. Thesis, Eindhoven University of Technology, The Netherlands, 1988. Google Scholar

[18]

G. Vosper, The critical pairs of subsets of a group of prime order, J. London Math. Soc., 31 (1956), 200-205.  doi: 10.1112/jlms/s1-31.2.200.  Google Scholar

show all references

References:
[1]

A. Blokhuis and C. W. H. Lam, More covering by rook domains, J. Combin. Theory Ser. A, 36 (1984), 240-244.  doi: 10.1016/0097-3165(84)90010-4.  Google Scholar

[2]

W. A. Carnielli, On covering and coloring problems for rook domains, Discrete Math., 57 (1985), 9-16.  doi: 10.1016/0012-365X(85)90152-9.  Google Scholar

[3]

W. A. Carnielli, Hyper-rook domain inequalities, Stud. Appl. Math., 82 (1990), 59-69.  doi: 10.1002/sapm199082159.  Google Scholar

[4]

A. Cauchy, Recherches sur les nombres, Oeuvres completes, (2009), 39-63.  doi: 10.1017/CBO9780511702501.004.  Google Scholar

[5]

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

[6]

H. Davenport, On the addition of residue classes, J. London Math. Soc., 10 (1935), 30-32.   Google Scholar

[7]

O. J. N. T. N. dos Santos and E. L. Monte Carmelo, Invariant sets under linear operator and covering codes over modules, Linear Algebra Appl., 444 (2014), 42-52.  doi: 10.1016/j.laa.2013.11.034.  Google Scholar

[8]

P. Erdős, Problems and Results on Combinatorial Number Theory Ⅲ, in Lecture Notes in Math., Springer- Verlag, Berlin, (1977), 43-72.  Google Scholar

[9]

Y. O. Hamidoune and Ø. J. Rødseth, An inverse theorem mod $p$, Acta Arithmetica, 92 (2000), 251-262.  doi: 10.4064/aa-92-3-251-262.  Google Scholar

[10]

I. Honkala, On lengthening of covering codes, Discrete Math., 106/107 (1992), 291-295.  doi: 10.1016/0012-365X(92)90556-U.  Google Scholar

[11]

H. J. L. Kamps and J. H. van Lint, A covering problem, in Combinatorial theory and its applications Ⅱ (Colloquia Mathematica Societatis Jànos Bolyai), North-Holland, Amsterdam, (1970), 679-685.  Google Scholar

[12]

I. N. Nakaoka and O. J. N. T. N. dos Santos, A covering problem over finite rings, Appl. Math. Lett., 23 (2010), 322-326.  doi: 10.1016/j.aml.2009.09.022.  Google Scholar

[13]

I. N. Nakaoka, E. L. Monte Carmelo and O. J. N. T. N. dos Santos, Sharp covering of a module by cyclic submodules, Linear Algebra Appl., 458 (2014), 387-402.  doi: 10.1016/j.laa.2014.06.019.  Google Scholar

[14]

M. B. Nathanson, Additive Number Theory. Inverse Problems and the Geometry of Sumsets, Springer-Verlag, New York, 1996. doi: 10.1007/978-1-4757-3845-2.  Google Scholar

[15]

T. Tao and V. Vu, Additive Combinatorics, Cambridge Studies in Advanced Mathematics, 105 Cambridge University Press, Cambridge, 2006. doi: 10.1017/CBO9780511755149.  Google Scholar

[16]

O. Taussky and J. Todd, Covering theorems for groups, Ann. Soc. Polonaise Math., 21 (1948), 303-305.   Google Scholar

[17]

J. H. van Lint Jr., Covering Radius Problems, M. Sc. Thesis, Eindhoven University of Technology, The Netherlands, 1988. Google Scholar

[18]

G. Vosper, The critical pairs of subsets of a group of prime order, J. London Math. Soc., 31 (1956), 200-205.  doi: 10.1112/jlms/s1-31.2.200.  Google Scholar

[1]

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

Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889
[3]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1
[4]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003
[5]

Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45
[6]

Sihuang Hu, Gabriele Nebe. There is no $[24,12,9]$ doubly-even self-dual code over $\mathbb F_4$. Advances in Mathematics of Communications, 2016, 10 (3) : 583-588. doi: 10.3934/amc.2016027
[7]

Jianying Fang. 5-SEEDs from the lifted Golay code of length 24 over Z4. Advances in Mathematics of Communications, 2017, 11 (1) : 259-266. doi: 10.3934/amc.2017017
[8]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399
[9]

Sascha Kurz. The $[46, 9, 20]_2$ code is unique. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020074
[10]

M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407
[11]

Masaaki Harada, Takuji Nishimura. An extremal singly even self-dual code of length 88. Advances in Mathematics of Communications, 2007, 1 (2) : 261-267. doi: 10.3934/amc.2007.1.261
[12]

José Gómez-Torrecillas, F. J. Lobillo, Gabriel Navarro. Information--bit error rate and false positives in an MDS code. Advances in Mathematics of Communications, 2015, 9 (2) : 149-168. doi: 10.3934/amc.2015.9.149
[13]

Jorge P. Arpasi. On the non-Abelian group code capacity of memoryless channels. Advances in Mathematics of Communications, 2020, 14 (3) : 423-436. doi: 10.3934/amc.2020058
[14]

M. De Boeck, P. Vandendriessche. On the dual code of points and generators on the Hermitian variety $\mathcal{H}(2n+1,q^{2})$. Advances in Mathematics of Communications, 2014, 8 (3) : 281-296. doi: 10.3934/amc.2014.8.281
[15]

Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$4-linear code of high minimum Lee distance derived from a hyperoval. Advances in Mathematics of Communications, 2011, 5 (2) : 275-286. doi: 10.3934/amc.2011.5.275
[16]

Anna-Lena Horlemann-Trautmann, Kyle Marshall. New criteria for MRD and Gabidulin codes and some Rank-Metric code constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 533-548. doi: 10.3934/amc.2017042
[17]

Masaaki Harada, Ethan Novak, Vladimir D. Tonchev. The weight distribution of the self-dual $[128,64]$ polarity design code. Advances in Mathematics of Communications, 2016, 10 (3) : 643-648. doi: 10.3934/amc.2016032
[18]

Denis S. Krotov, Patric R. J.  Östergård, Olli Pottonen. Non-existence of a ternary constant weight $(16,5,15;2048)$ diameter perfect code. Advances in Mathematics of Communications, 2016, 10 (2) : 393-399. doi: 10.3934/amc.2016013
[19]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2019  doi: 10.3934/amc.2020046
[20]

Daniel Heinlein, Michael Kiermaier, Sascha Kurz, Alfred Wassermann. A subspace code of size $ \bf{333} $ in the setting of a binary $ \bf{q} $-analog of the Fano plane. Advances in Mathematics of Communications, 2019, 13 (3) : 457-475. doi: 10.3934/amc.2019029

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (105)
  • HTML views (182)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences