The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs

Ricardo A. Podestá; Denis E. Videla

doi:10.3934/amc.2021002

Previous Article
On $ \sigma $-self-orthogonal constacyclic codes over $ \mathbb F_{p^m}+u\mathbb F_{p^m} $
AMC Home
This Issue
Next Article
On the exponents of APN power functions and Sidon sets, sum-free sets, and Dickson polynomials

doi: 10.3934/amc.2021002

Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs

Ricardo A. Podestá ^, and Denis E. Videla

FaMAF-CIEM (CONICET), Universidad Nacional de Córdoba, Av. Medina Allende 2144, Ciudad Universitaria, Córdoba (5000), República Argentina

^* Corresponding author: Ricardo A. Podestá

Received February 2020 Revised February 2021 Early access March 2021

Fund Project: Partially supported by CONICET, FonCyT (BID-PICT 2018-02073) and SECyT-UNC

We use known characterizations of generalized Paley graphs which are Cartesian decomposable to explicitly compute the spectra of the corresponding associated irreducible cyclic codes. As applications, we give reduction formulas for the number of rational points in Artin-Schreier curves defined over extension fields and to the computation of Gaussian periods.

Keywords: Irreducible cyclic codes, generalized Paley graphs, weight distribution, spectra, Cartesian decomposable.

Mathematics Subject Classification: Primary: 94B15, 05C25; Secondary: 05C50, 05C76.

Citation: Ricardo A. Podestá, Denis E. Videla. The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs. Advances in Mathematics of Communications, doi: 10.3934/amc.2021002

References:

[1]	R. Akhtar, T. Jackson-Henderson, R. Karpman, M. Boggess, I. Jiménez, A. Kinzel and D. Pritikin, On the unitary Cayley graph of a finite ring, Electron. J. Combin., 16 (2009), 117-130. Google Scholar
[2]	L. D. Baumert and R. J. McEliece, Weights of irreducible cyclic codes, Information and Control, 20 (1972), 158-175. doi: 10.1016/S0019-9958(72)90354-3. Google Scholar
[3]	B. Berndt, R. J. Evans and K. Williams, Gauss and Jacobi Sums, Wiley, New York, 1998. Google Scholar
[4]	D. Cvetkovic, M. Doobs and H. Sachs, Spectra of Graphs, Pure and Applied Mathematics, Academic Press, 1980. Google Scholar
[5]	C. Ding, The weight distribution of some irreducible cyclic codes, IEEE Trans. Inform. Theory, 55 (2009), 955-960. doi: 10.1109/TIT.2008.2011511. Google Scholar
[6]	C. Ding, A class of three-weight and four-weight codes, Lecture Notes in Computer Science, 5557, Springer Verlag, (2009) 34–42. doi: 10.1007/978-3-642-01877-0_4. Google Scholar
[7]	C. Ding and J. Yang, Hamming weights in irreducible cyclic codes, Discrete Mathematics, 313 (2013), 434-446. doi: 10.1016/j.disc.2012.11.009. Google Scholar
[8]	H. Q. Dinh, C. Li and Q. Yue, Recent progress on weight distributions of cyclic codes over finite fields, J. Algebra Comb. Discrete Struct. Appl., 2 (2015), 39-63. Google Scholar
[9]	K. Feng and J. Luo, Weight distribution of some reducible cyclic codes, Finite Fields Appl., 14 (2008), 390-409. doi: 10.1016/j.ffa.2007.03.003. Google Scholar
[10]	C. D. Godsil and G. F. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, Springer, 2001. doi: 10.1007/978-1-4613-0163-9. Google Scholar
[11]	A. Garcia and H. Stichtenoth, Topics in Geometry, Coding Theory and Cryptography, Algebra and Applications, Springer, 2007. Google Scholar
[12]	R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, CRC Press 2nd edition, 2011. Google Scholar
[13]	W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition, Wiley-Interscience, 2000. Google Scholar
[14]	S. Li, S. Hu, T. Feng and G. Ge, The weight distribution of a class of cyclic codes related to Hermitian forms graphs, IEEE Trans. Inform. Theory, 59 (2013), 3064-3067. doi: 10.1109/TIT.2013.2242957. Google Scholar
[15]	C. Li, Q. Yue and F. Li, Weight distributions of cyclic codes with respect to pairwise coprime order elements, Finite Fields Appl., 28 (2014), 94-114. doi: 10.1016/j.ffa.2014.01.009. Google Scholar
[16]	T. K. Lim and C. Praeger, On Generalised Paley Graphs and their automorphism groups, Michigan Math. J., 58 (2009), 293-308. doi: 10.1307/mmj/1242071694. Google Scholar
[17]	R. J. McEliece, Irreducible cyclic codes and Gauss sums, Combinatorics in: Proc. NATO Adv. Study Inst., Breukelen, 1974. Math. Centre Tracts 55, Math. Centrum, Amsterdam, 1974. Google Scholar
[18]	G. Pearce and C. Praeger, Generalised Paley graphs with a product structure, Ann. Comb., 23 (2019), 171-182. doi: 10.1007/s00026-019-00423-0. Google Scholar
[19]	R. A. Podestá and D. E. Videla, The spectra of generalized Paley graphs of $q^{\ell}+1$ powers and applications, preprint, arXiv: 1812.03332. Google Scholar
[20]	R. A. Podestá and D. E. Videla, Spectral properties of generalized Paley graphs and of their associated irreducible cyclic codes, preprint, arXiv: 1908.08097v2. Google Scholar
[21]	R. A. Podestá and D. E. Videla, The Waring's problem over finite fields through generalized Paley graphs, Discrete Mathematics, 344 (2021), 112324. doi: 10.1016/j.disc.2021.112324. Google Scholar
[22]	A. Rao and N. Pinnawala, A family of two-weight irreducible cyclic codes, IEEE Trans. Inform. Theory, 56 (2010), 2568-2570. doi: 10.1109/TIT.2010.2046201. Google Scholar
[23]	G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canadian Journal of Mathematics, 9 (1957), 515-525. doi: 10.4153/CJM-1957-060-7. Google Scholar
[24]	G. Sabidussi, Graph multiplication, Mathematische Zeitschrift, 72 (1960), 446-457. doi: 10.1007/BF01162967. Google Scholar
[25]	B. Schmidt and C. White, All two weight irreducible cyclic codes, Finite Fields Appl., 8 (2002), 1-17. doi: 10.1006/ffta.2000.0293. Google Scholar
[26]	A. Sharma and G. K. Bakshi, The weight distribution of some irreducible cyclic codes, Finite Fields Appl., 18 (2012), 144-159. doi: 10.1016/j.ffa.2011.07.002. Google Scholar
[27]	T. Storer., Cyclotomy and Difference Sets, Markham Publishing Co., Chicago, 1967. Google Scholar
[28]	G. Vega and J. Wolfmann, New classes of 2-weight cyclic codes, Des. Codes Cryptogr., 42 (2007), 327-334. doi: 10.1007/s10623-007-9038-9. Google Scholar
[29]	Z. Zhou, A. Zhang, C. Ding and M. Xiong, The weight enumerator of three families of cyclic codes, IEEE Trans. Inform. Theory, 59 (2013), 6002-6009. doi: 10.1109/TIT.2013.2262095. Google Scholar

show all references

References:

[1]	R. Akhtar, T. Jackson-Henderson, R. Karpman, M. Boggess, I. Jiménez, A. Kinzel and D. Pritikin, On the unitary Cayley graph of a finite ring, Electron. J. Combin., 16 (2009), 117-130. Google Scholar
[2]	L. D. Baumert and R. J. McEliece, Weights of irreducible cyclic codes, Information and Control, 20 (1972), 158-175. doi: 10.1016/S0019-9958(72)90354-3. Google Scholar
[3]	B. Berndt, R. J. Evans and K. Williams, Gauss and Jacobi Sums, Wiley, New York, 1998. Google Scholar
[4]	D. Cvetkovic, M. Doobs and H. Sachs, Spectra of Graphs, Pure and Applied Mathematics, Academic Press, 1980. Google Scholar
[5]	C. Ding, The weight distribution of some irreducible cyclic codes, IEEE Trans. Inform. Theory, 55 (2009), 955-960. doi: 10.1109/TIT.2008.2011511. Google Scholar
[6]	C. Ding, A class of three-weight and four-weight codes, Lecture Notes in Computer Science, 5557, Springer Verlag, (2009) 34–42. doi: 10.1007/978-3-642-01877-0_4. Google Scholar
[7]	C. Ding and J. Yang, Hamming weights in irreducible cyclic codes, Discrete Mathematics, 313 (2013), 434-446. doi: 10.1016/j.disc.2012.11.009. Google Scholar
[8]	H. Q. Dinh, C. Li and Q. Yue, Recent progress on weight distributions of cyclic codes over finite fields, J. Algebra Comb. Discrete Struct. Appl., 2 (2015), 39-63. Google Scholar
[9]	K. Feng and J. Luo, Weight distribution of some reducible cyclic codes, Finite Fields Appl., 14 (2008), 390-409. doi: 10.1016/j.ffa.2007.03.003. Google Scholar
[10]	C. D. Godsil and G. F. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, Springer, 2001. doi: 10.1007/978-1-4613-0163-9. Google Scholar
[11]	A. Garcia and H. Stichtenoth, Topics in Geometry, Coding Theory and Cryptography, Algebra and Applications, Springer, 2007. Google Scholar
[12]	R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, CRC Press 2nd edition, 2011. Google Scholar
[13]	W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition, Wiley-Interscience, 2000. Google Scholar
[14]	S. Li, S. Hu, T. Feng and G. Ge, The weight distribution of a class of cyclic codes related to Hermitian forms graphs, IEEE Trans. Inform. Theory, 59 (2013), 3064-3067. doi: 10.1109/TIT.2013.2242957. Google Scholar
[15]	C. Li, Q. Yue and F. Li, Weight distributions of cyclic codes with respect to pairwise coprime order elements, Finite Fields Appl., 28 (2014), 94-114. doi: 10.1016/j.ffa.2014.01.009. Google Scholar
[16]	T. K. Lim and C. Praeger, On Generalised Paley Graphs and their automorphism groups, Michigan Math. J., 58 (2009), 293-308. doi: 10.1307/mmj/1242071694. Google Scholar
[17]	R. J. McEliece, Irreducible cyclic codes and Gauss sums, Combinatorics in: Proc. NATO Adv. Study Inst., Breukelen, 1974. Math. Centre Tracts 55, Math. Centrum, Amsterdam, 1974. Google Scholar
[18]	G. Pearce and C. Praeger, Generalised Paley graphs with a product structure, Ann. Comb., 23 (2019), 171-182. doi: 10.1007/s00026-019-00423-0. Google Scholar
[19]	R. A. Podestá and D. E. Videla, The spectra of generalized Paley graphs of $q^{\ell}+1$ powers and applications, preprint, arXiv: 1812.03332. Google Scholar
[20]	R. A. Podestá and D. E. Videla, Spectral properties of generalized Paley graphs and of their associated irreducible cyclic codes, preprint, arXiv: 1908.08097v2. Google Scholar
[21]	R. A. Podestá and D. E. Videla, The Waring's problem over finite fields through generalized Paley graphs, Discrete Mathematics, 344 (2021), 112324. doi: 10.1016/j.disc.2021.112324. Google Scholar
[22]	A. Rao and N. Pinnawala, A family of two-weight irreducible cyclic codes, IEEE Trans. Inform. Theory, 56 (2010), 2568-2570. doi: 10.1109/TIT.2010.2046201. Google Scholar
[23]	G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canadian Journal of Mathematics, 9 (1957), 515-525. doi: 10.4153/CJM-1957-060-7. Google Scholar
[24]	G. Sabidussi, Graph multiplication, Mathematische Zeitschrift, 72 (1960), 446-457. doi: 10.1007/BF01162967. Google Scholar
[25]	B. Schmidt and C. White, All two weight irreducible cyclic codes, Finite Fields Appl., 8 (2002), 1-17. doi: 10.1006/ffta.2000.0293. Google Scholar
[26]	A. Sharma and G. K. Bakshi, The weight distribution of some irreducible cyclic codes, Finite Fields Appl., 18 (2012), 144-159. doi: 10.1016/j.ffa.2011.07.002. Google Scholar
[27]	T. Storer., Cyclotomy and Difference Sets, Markham Publishing Co., Chicago, 1967. Google Scholar
[28]	G. Vega and J. Wolfmann, New classes of 2-weight cyclic codes, Des. Codes Cryptogr., 42 (2007), 327-334. doi: 10.1007/s10623-007-9038-9. Google Scholar
[29]	Z. Zhou, A. Zhang, C. Ding and M. Xiong, The weight enumerator of three families of cyclic codes, IEEE Trans. Inform. Theory, 59 (2013), 6002-6009. doi: 10.1109/TIT.2013.2262095. Google Scholar

Table 1. Weight distribution of $ \mathcal{C} $ with $ p\equiv 2,5,7\pmod 9 $ and $ p>5 $

weight	frequency	weight	frequency
$ w_{0,0} = 0 $	$ A_{0,0}=1 $	$w_{0,2}=p^2-1$	$A_{0,2}=3(\tfrac{p^{2}-1}2)^{2}$
$ w_{1,0}=\tfrac{(p-1)^2}2 $	$ A_{1,0}=3(\tfrac{p^{2}-1}2) $	$w_{0,3}=\tfrac{3(p^{2}-1)}2$	$A_{0,3}=(\tfrac{p^{2}-1}2)^3$
$ w_{2,0}=(p-1)^2 $	$ A_{2,0}=3(\tfrac{p^{2}-1}2)^{2} $	$w_{1,1}=p(p-1)$	$A_{1,1}=6(\tfrac{p^{2}-1}2)^{2}$
$ w_{3,0}=\tfrac{3(p-1)^2}2 $	$ A_{3,0}=(\tfrac{p^{2}-1}2)^3 $	$w_{2,1}=\tfrac{p-1}{2} (3p-1)$	$A_{2,1}=3(\tfrac{p^{2}-1}2)^3$
$ w_{0,1}=\tfrac{p^{2}-1}2 $	$ A_{0,1}=3(\tfrac{p^{2}-1}2) $	$w_{1,2}=\tfrac{p-1}{2} (3p+1)$	$A_{1,2}=3(\tfrac{p^{2}-1}2)^3$

Table Options

Download as excel

weight	frequency	weight	frequency
$ w_{0,0} = 0 $	$ A_{0,0}=1 $	$w_{0,2}=p^2-1$	$A_{0,2}=3(\tfrac{p^{2}-1}2)^{2}$
$ w_{1,0}=\tfrac{(p-1)^2}2 $	$ A_{1,0}=3(\tfrac{p^{2}-1}2) $	$w_{0,3}=\tfrac{3(p^{2}-1)}2$	$A_{0,3}=(\tfrac{p^{2}-1}2)^3$
$ w_{2,0}=(p-1)^2 $	$ A_{2,0}=3(\tfrac{p^{2}-1}2)^{2} $	$w_{1,1}=p(p-1)$	$A_{1,1}=6(\tfrac{p^{2}-1}2)^{2}$
$ w_{3,0}=\tfrac{3(p-1)^2}2 $	$ A_{3,0}=(\tfrac{p^{2}-1}2)^3 $	$w_{2,1}=\tfrac{p-1}{2} (3p-1)$	$A_{2,1}=3(\tfrac{p^{2}-1}2)^3$
$ w_{0,1}=\tfrac{p^{2}-1}2 $	$ A_{0,1}=3(\tfrac{p^{2}-1}2) $	$w_{1,2}=\tfrac{p-1}{2} (3p+1)$	$A_{1,2}=3(\tfrac{p^{2}-1}2)^3$

Table 2. Weight distribution of $ \mathcal{C}(516,7^6) $

weight	frequency	weight	frequency
$ w_{0,0,0}=0 $	$ A_{0,0,0}=1 $	$w_{0,2,0}=216$	$A_{0,2,0}=114^2$
$ w_{1,0,0}=96 $	$ A_{1,0,0}=228 $	$w_{0,0,2}=180$	$ A_{0,0,2}=114^2$
$ w_{0,1,0}=108 $	$ A_{0,1,0}=228 $	$ w_{1,1,0}=204$	$A_{1,1,0}=2\cdot 114^2$
$ w_{0,0,1}=90 $	$ A_{0,0,1}=228 $	$w_{1,0,1}=186$	$ A_{1,0,1}=2\cdot 114^2$
$ w_{2,0,0}=192 $	$ A_{2,0,0}=114^2 $	$w_{0,1,1}=198$	$A_{0,1,1}=2\cdot 114^2$

Table Options

Download as excel

weight	frequency	weight	frequency
$ w_{0,0,0}=0 $	$ A_{0,0,0}=1 $	$w_{0,2,0}=216$	$A_{0,2,0}=114^2$
$ w_{1,0,0}=96 $	$ A_{1,0,0}=228 $	$w_{0,0,2}=180$	$ A_{0,0,2}=114^2$
$ w_{0,1,0}=108 $	$ A_{0,1,0}=228 $	$ w_{1,1,0}=204$	$A_{1,1,0}=2\cdot 114^2$
$ w_{0,0,1}=90 $	$ A_{0,0,1}=228 $	$w_{1,0,1}=186$	$ A_{1,0,1}=2\cdot 114^2$
$ w_{2,0,0}=192 $	$ A_{2,0,0}=114^2 $	$w_{0,1,1}=198$	$A_{0,1,1}=2\cdot 114^2$

[1]	Gerardo Vega, Jesús E. Cuén-Ramos. The weight distribution of families of reducible cyclic codes through the weight distribution of some irreducible cyclic codes. Advances in Mathematics of Communications, 2020, 14 (3) : 525-533. doi: 10.3934/amc.2020059
[2]	Lanqiang Li, Shixin Zhu, Li Liu. The weight distribution of a class of p-ary cyclic codes and their applications. Advances in Mathematics of Communications, 2019, 13 (1) : 137-156. doi: 10.3934/amc.2019008
[3]	Pankaj Kumar, Monika Sangwan, Suresh Kumar Arora. The weight distributions of some irreducible cyclic codes of length $p^n$ and $2p^n$. Advances in Mathematics of Communications, 2015, 9 (3) : 277-289. doi: 10.3934/amc.2015.9.277
[4]	Dina Ghinelli, Jennifer D. Key. Codes from incidence matrices and line graphs of Paley graphs. Advances in Mathematics of Communications, 2011, 5 (1) : 93-108. doi: 10.3934/amc.2011.5.93
[5]	Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433
[6]	Alexander A. Davydov, Stefano Marcugini, Fernanda Pambianco. On the weight distribution of the cosets of MDS codes. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021042
[7]	Long Yu, Hongwei Liu. A class of $p$-ary cyclic codes and their weight enumerators. Advances in Mathematics of Communications, 2016, 10 (2) : 437-457. doi: 10.3934/amc.2016017
[8]	Nigel Boston, Jing Hao. The weight distribution of quasi-quadratic residue codes. Advances in Mathematics of Communications, 2018, 12 (2) : 363-385. doi: 10.3934/amc.2018023
[9]	Eimear Byrne. On the weight distribution of codes over finite rings. Advances in Mathematics of Communications, 2011, 5 (2) : 395-406. doi: 10.3934/amc.2011.5.395
[10]	Sergio R. López-Permouth, Steve Szabo. On the Hamming weight of repeated root cyclic and negacyclic codes over Galois rings. Advances in Mathematics of Communications, 2009, 3 (4) : 409-420. doi: 10.3934/amc.2009.3.409
[11]	Chengju Li, Qin Yue, Ziling Heng. Weight distributions of a class of cyclic codes from $\Bbb F_l$-conjugates. Advances in Mathematics of Communications, 2015, 9 (3) : 341-352. doi: 10.3934/amc.2015.9.341
[12]	M. DeDeo, M. Martínez, A. Medrano, M. Minei, H. Stark, A. Terras. Spectra of Heisenberg graphs over finite rings. Conference Publications, 2003, 2003 (Special) : 213-222. doi: 10.3934/proc.2003.2003.213
[13]	Anuradha Sharma, Saroj Rani. Trace description and Hamming weights of irreducible constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (1) : 123-141. doi: 10.3934/amc.2018008
[14]	Fengwei Li, Qin Yue, Fengmei Liu. The weight distributions of constacyclic codes. Advances in Mathematics of Communications, 2017, 11 (3) : 471-480. doi: 10.3934/amc.2017039
[15]	Tim Alderson, Alessandro Neri. Maximum weight spectrum codes. Advances in Mathematics of Communications, 2019, 13 (1) : 101-119. doi: 10.3934/amc.2019006
[16]	Tongjiang Yan, Yanyan Liu, Yuhua Sun. Cyclic codes from two-prime generalized cyclotomic sequences of order 6. Advances in Mathematics of Communications, 2016, 10 (4) : 707-723. doi: 10.3934/amc.2016036
[17]	Srimathy Srinivasan, Andrew Thangaraj. Codes on planar Tanner graphs. Advances in Mathematics of Communications, 2012, 6 (2) : 131-163. doi: 10.3934/amc.2012.6.131
[18]	Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2020133
[19]	Shuangliang Tian, Ping Chen, Yabin Shao, Qian Wang. Adjacent vertex distinguishing edge-colorings and total-colorings of the Cartesian product of graphs. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 49-58. doi: 10.3934/naco.2014.4.49
[20]	Petr Lisoněk, Layla Trummer. Algorithms for the minimum weight of linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 195-207. doi: 10.3934/amc.2016.10.195

2020 Impact Factor: 0.935

Tools

Metrics

Tools

Article outline

Figures and Tables

2020 Impact Factor: 0.935

Tools

Figures and Tables

2020 Impact Factor: 0.935

American Institute of Mathematical Sciences

The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors