American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2021002

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

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

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

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

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

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

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

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

Tim Alderson, Alessandro Neri. Maximum weight spectrum codes. Advances in Mathematics of Communications, 2019, 13 (1) : 101-119. doi: 10.3934/amc.2019006
[14]

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

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

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

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

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

Xiangrui Meng, Jian Gao. Complete weight enumerator of torsion codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020124
[20]

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

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (21)
  • HTML views (39)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences