doi: 10.3934/amc.2021002

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

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.

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. AkhtarT. Jackson-HendersonR. KarpmanM. BoggessI. JiménezA. 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. DinhC. 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. LiS. HuT. 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. LiQ. 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. ZhouA. ZhangC. 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. AkhtarT. Jackson-HendersonR. KarpmanM. BoggessI. JiménezA. 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. DinhC. 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. LiS. HuT. 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. LiQ. 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. ZhouA. ZhangC. 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$
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$
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]

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

[2]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79

[3]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265

[4]

Yun Gao, Shilin Yang, Fang-Wei Fu. Some optimal cyclic $ \mathbb{F}_q $-linear $ \mathbb{F}_{q^t} $-codes. Advances in Mathematics of Communications, 2021, 15 (3) : 387-396. doi: 10.3934/amc.2020072

[5]

Antonio Cossidente, Sascha Kurz, Giuseppe Marino, Francesco Pavese. Combining subspace codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021007

[6]

Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907

[7]

Andrey Kovtanyuk, Alexander Chebotarev, Nikolai Botkin, Varvara Turova, Irina Sidorenko, Renée Lampe. Modeling the pressure distribution in a spatially averaged cerebral capillary network. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021016

[8]

Yao Nie, Jia Yuan. The Littlewood-Paley $ pth $-order moments in three-dimensional MHD turbulence. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3045-3062. doi: 10.3934/dcds.2020397

[9]

Yuta Ishii, Kazuhiro Kurata. Existence of multi-peak solutions to the Schnakenberg model with heterogeneity on metric graphs. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021035

[10]

Soonki Hong, Seonhee Lim. Martin boundary of brownian motion on Gromov hyperbolic metric graphs. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3725-3757. doi: 10.3934/dcds.2021014

[11]

Naeem M. H. Alkoumi, Pedro J. Torres. Estimates on the number of limit cycles of a generalized Abel equation. Discrete & Continuous Dynamical Systems, 2011, 31 (1) : 25-34. doi: 10.3934/dcds.2011.31.25

[12]

Ethan Akin, Julia Saccamano. Generalized intransitive dice II: Partition constructions. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021005

[13]

Ritu Agarwal, Kritika, Sunil Dutt Purohit, Devendra Kumar. Mathematical modelling of cytosolic calcium concentration distribution using non-local fractional operator. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021017

[14]

Alfonso Castro, Jorge Cossio, Sigifredo Herrón, Carlos Vélez. Infinitely many radial solutions for a $ p $-Laplacian problem with indefinite weight. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021058

[15]

Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3651-3682. doi: 10.3934/dcds.2021011

[16]

Quan Hai, Shutang Liu. Mean-square delay-distribution-dependent exponential synchronization of chaotic neural networks with mixed random time-varying delays and restricted disturbances. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3097-3118. doi: 10.3934/dcdsb.2020221

[17]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022

[18]

Shuting Chen, Zengji Du, Jiang Liu, Ke Wang. The dynamic properties of a generalized Kawahara equation with Kuramoto-Sivashinsky perturbation. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021098

[19]

Simão Correia, Mário Figueira. A generalized complex Ginzburg-Landau equation: Global existence and stability results. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021056

[20]

Zhenquan Zhang, Meiling Chen, Jiajun Zhang, Tianshou Zhou. Analysis of non-Markovian effects in generalized birth-death models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3717-3735. doi: 10.3934/dcdsb.2020254

2019 Impact Factor: 0.734

Article outline

Figures and Tables

[Back to Top]