A connection between sumsets and covering codes of a module

Previous Article
On self-orthogonal designs and codes related to Held's simple group
AMC Home
This Issue
Next Article
Parameters of LCD BCH codes with two lengths

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.
[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.
[3]	W. A. Carnielli, Hyper-rook domain inequalities, Stud. Appl. Math., 82 (1990), 59-69. doi: 10.1002/sapm199082159.
[4]	A. Cauchy, Recherches sur les nombres, Oeuvres completes, (2009), 39-63. doi: 10.1017/CBO9780511702501.004.
[5]	G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes, North-Holland, Amsterdam, 1997.
[6]	H. Davenport, On the addition of residue classes, J. London Math. Soc., 10 (1935), 30-32.
[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.
[8]	P. Erdős, Problems and Results on Combinatorial Number Theory Ⅲ, in Lecture Notes in Math., Springer- Verlag, Berlin, (1977), 43-72.
[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.
[10]	I. Honkala, On lengthening of covering codes, Discrete Math., 106/107 (1992), 291-295. doi: 10.1016/0012-365X(92)90556-U.
[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.
[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.
[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.
[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.
[15]	T. Tao and V. Vu, Additive Combinatorics, Cambridge Studies in Advanced Mathematics, 105 Cambridge University Press, Cambridge, 2006. doi: 10.1017/CBO9780511755149.
[16]	O. Taussky and J. Todd, Covering theorems for groups, Ann. Soc. Polonaise Math., 21 (1948), 303-305.
[17]	J. H. van Lint Jr., Covering Radius Problems, M. Sc. Thesis, Eindhoven University of Technology, The Netherlands, 1988.
[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.

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.
[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.
[3]	W. A. Carnielli, Hyper-rook domain inequalities, Stud. Appl. Math., 82 (1990), 59-69. doi: 10.1002/sapm199082159.
[4]	A. Cauchy, Recherches sur les nombres, Oeuvres completes, (2009), 39-63. doi: 10.1017/CBO9780511702501.004.
[5]	G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes, North-Holland, Amsterdam, 1997.
[6]	H. Davenport, On the addition of residue classes, J. London Math. Soc., 10 (1935), 30-32.
[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.
[8]	P. Erdős, Problems and Results on Combinatorial Number Theory Ⅲ, in Lecture Notes in Math., Springer- Verlag, Berlin, (1977), 43-72.
[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.
[10]	I. Honkala, On lengthening of covering codes, Discrete Math., 106/107 (1992), 291-295. doi: 10.1016/0012-365X(92)90556-U.
[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.
[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.
[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.
[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.
[15]	T. Tao and V. Vu, Additive Combinatorics, Cambridge Studies in Advanced Mathematics, 105 Cambridge University Press, Cambridge, 2006. doi: 10.1017/CBO9780511755149.
[16]	O. Taussky and J. Todd, Covering theorems for groups, Ann. Soc. Polonaise Math., 21 (1948), 303-305.
[17]	J. H. van Lint Jr., Covering Radius Problems, M. Sc. Thesis, Eindhoven University of Technology, The Netherlands, 1988.
[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.

[1]	María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021018
[2]	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
[3]	Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete and Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889
[4]	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
[5]	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
[6]	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
[7]	Andrea Seidl, Stefan Wrzaczek. Opening the source code: The threat of forking. Journal of Dynamics and Games, 2022 doi: 10.3934/jdg.2022010
[8]	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
[9]	Jianying Fang. 5-SEEDs from the lifted Golay code of length 24 over Z₄. Advances in Mathematics of Communications, 2017, 11 (1) : 259-266. doi: 10.3934/amc.2017017
[10]	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
[11]	Sascha Kurz. The $[46, 9, 20]_2$ code is unique. Advances in Mathematics of Communications, 2021, 15 (3) : 415-422. doi: 10.3934/amc.2020074
[12]	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 and Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407
[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]	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
[15]	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
[16]	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
[17]	Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$₄-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
[18]	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
[19]	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
[20]	Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Otávio J. N. T. N. dos Santos Emerson L. Monte Carmelo
on Google Scholar
Otávio J. N. T. N. dos Santos Emerson L. Monte Carmelo

2020 Impact Factor: 0.935

Tools

Article outline

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Otávio J. N. T. N. dos Santos Emerson L. Monte Carmelo
on Google Scholar
Otávio J. N. T. N. dos Santos Emerson L. Monte Carmelo

[Back to Top]