# American Institute of Mathematical Sciences

doi: 10.3934/amc.2020133

## Connection of $p$-ary $t$-weight linear codes to Ramanujan Cayley graphs with $t+1$ eigenvalues

 1 Konkuk University, Glocal Campus, 268 Chungwon-daero Chungju-si Chungcheongbuk-do 27478, South Korea 2 Department of Mathematics, Ewha Womans University, Seoul 03760, South Korea 3 School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China

Received  May 2020 Published  March 2021

Fund Project: Jong Yoon Hyun was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government(MEST)(NRF-2017R1D1A1B05030707). Yoonjin Lee is a corresponding author and was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education (Grant No. 2019R1A6A1A11051177) and also by the National Research Foundation of Korea(NRF) grant funded by the Korea government (MEST)(NRF-2017R1A2B2004574)

We characterize the connection between $p$-ary linear codes and Ramanujan Cayley graphs. We explicitly determine an equivalence between $t$-weight linear codes over the finite field $\Bbb F_p$ and Ramanujan Cayley graphs with $t+1$ eigenvalues. In particular, we get an explicit criterion on the equivalence between two-weight linear codes and Ramanujan strongly regular graphs with explicit parameters. Using this characterization, we construct several families of Ramanujan Cayley graphs with two or three eigenvalues from known linear codes with two or three weights, respectively.

Citation: 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, doi: 10.3934/amc.2020133
##### References:
 [1] R. Calderbank and W. M. Kantor, The geometry of two-weight codes, Bull. London Math. Soc., 18 (1986), 97-122.  doi: 10.1112/blms/18.2.97.  Google Scholar [2] Y. M. Chee, Y. Tan and X. D. Zhang, Strongly regular graphs constructed from $p$-ary bent functions, J. Algebraic Combin., 34 (2011), 251-266.  doi: 10.1007/s10801-010-0270-4.  Google Scholar [3] G. Davidoff, P. Sarnak and A. Valette, Elementary Number Theory, Group Theory, and Ramanujan Graphs, Cambridge Univ. Press, 2003.  doi: 10.1017/CBO9780511615825.  Google Scholar [4] C. Ding, Linear codes from some 2-designs, IEEE Trans. Inform. Theory, 61 (2015), 3265-3275.  doi: 10.1109/TIT.2015.2420118.  Google Scholar [5] K. Ding and C. Ding, A class of two-weight and three-weight codes and their applications in secret sharing, IEEE Trans. Inform. Theory, 61 (2015), 5835-5842.  doi: 10.1109/TIT.2015.2473861.  Google Scholar [6] C. Ding and H. Niederreiter, Cyclotomic linear codes of order 3, IEEE Trans. Inform. Theory, 53 (2007), 2274-2277.  doi: 10.1109/TIT.2007.896886.  Google Scholar [7] C. D. Godsil, Algebraic Combinatorics, Chapman & Hall/CRC, 1993.  Google Scholar [8] O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesan and D. Zuckerman, Security preserving amplification of hardness, 31st Annual Symposium on Foundations of Computer Science, 1 (1990), 318-326.  doi: 10.1109/FSCS.1990.89550.  Google Scholar [9] Z. Heng and Q. Yue, A construction of $q$-ary linear codes with two weights, Finite Fields Their Appl., 48 (2017), 20-42.  doi: 10.1016/j.ffa.2017.07.006.  Google Scholar [10] S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc., 43 (2006), 439-561.  doi: 10.1090/S0273-0979-06-01126-8.  Google Scholar [11] A. Lubotzky, Expander graphs in pure and applied mathematics, Bull. Amer. Math. Soc., 49 (2012), 113-162.  doi: 10.1090/S0273-0979-2011-01359-3.  Google Scholar [12] G. Luo, X. Cao, S. Xu and J. Mi, Binary linear codes with two or three weights from Niho exponents, Cryptogr. Commun., 10 (2018), 301-318.  doi: 10.1007/s12095-017-0220-2.  Google Scholar [13] S. Mesnager, Linear codes with few weights from weakly regular bent functions based on a generic construction, Cryptogr. Commun., 9 (2017), 71-84.  doi: 10.1007/s12095-016-0186-5.  Google Scholar [14] S. Mesnager, F. Ozbudak and A. Sinak, Linear codes from weakly regular plateaued functions and their secret sharing schemes, Des. Codes Cryptogr., 87 (2019), 463-480.  doi: 10.1007/s10623-018-0556-4.  Google Scholar [15] N. Pippenger, Sorting and selecting in rounds, SIAM J. Comput., 16 (1987), 1032-1038.  doi: 10.1137/0216066.  Google Scholar [16] Y. Qi, C. Tang and D. Huang, Binary linear codes with few weights, IEEE Commun. Lett., 20 (2016), 208-211.   Google Scholar [17] O. Reingold, S. Vadhan and A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders, Ann. of Math., 155 (2002), 157-187.  doi: 10.2307/3062153.  Google Scholar [18] C. Tang, N. Li, Y. Qi, Z. Zhou and T. Helleseth, Linear codes with two or three weights from weakly regular bent functions, IEEE Trans. Inform. Theory, 62 (2016), 1166-1176.  doi: 10.1109/TIT.2016.2518678.  Google Scholar [19] C. Williamson, Spectral Graph Theory, Expanders, and Ramanujan Graphs, University of Washington, 2014. Available from: https://sites.math.washington.edu/morrow/papers/chris-thesis.pdf. Google Scholar [20] C. Xiang, It is indeed a fundamental construction of all linear codes, arXiv: 1610.06355. Google Scholar

show all references

##### References:
 [1] R. Calderbank and W. M. Kantor, The geometry of two-weight codes, Bull. London Math. Soc., 18 (1986), 97-122.  doi: 10.1112/blms/18.2.97.  Google Scholar [2] Y. M. Chee, Y. Tan and X. D. Zhang, Strongly regular graphs constructed from $p$-ary bent functions, J. Algebraic Combin., 34 (2011), 251-266.  doi: 10.1007/s10801-010-0270-4.  Google Scholar [3] G. Davidoff, P. Sarnak and A. Valette, Elementary Number Theory, Group Theory, and Ramanujan Graphs, Cambridge Univ. Press, 2003.  doi: 10.1017/CBO9780511615825.  Google Scholar [4] C. Ding, Linear codes from some 2-designs, IEEE Trans. Inform. Theory, 61 (2015), 3265-3275.  doi: 10.1109/TIT.2015.2420118.  Google Scholar [5] K. Ding and C. Ding, A class of two-weight and three-weight codes and their applications in secret sharing, IEEE Trans. Inform. Theory, 61 (2015), 5835-5842.  doi: 10.1109/TIT.2015.2473861.  Google Scholar [6] C. Ding and H. Niederreiter, Cyclotomic linear codes of order 3, IEEE Trans. Inform. Theory, 53 (2007), 2274-2277.  doi: 10.1109/TIT.2007.896886.  Google Scholar [7] C. D. Godsil, Algebraic Combinatorics, Chapman & Hall/CRC, 1993.  Google Scholar [8] O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesan and D. Zuckerman, Security preserving amplification of hardness, 31st Annual Symposium on Foundations of Computer Science, 1 (1990), 318-326.  doi: 10.1109/FSCS.1990.89550.  Google Scholar [9] Z. Heng and Q. Yue, A construction of $q$-ary linear codes with two weights, Finite Fields Their Appl., 48 (2017), 20-42.  doi: 10.1016/j.ffa.2017.07.006.  Google Scholar [10] S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc., 43 (2006), 439-561.  doi: 10.1090/S0273-0979-06-01126-8.  Google Scholar [11] A. Lubotzky, Expander graphs in pure and applied mathematics, Bull. Amer. Math. Soc., 49 (2012), 113-162.  doi: 10.1090/S0273-0979-2011-01359-3.  Google Scholar [12] G. Luo, X. Cao, S. Xu and J. Mi, Binary linear codes with two or three weights from Niho exponents, Cryptogr. Commun., 10 (2018), 301-318.  doi: 10.1007/s12095-017-0220-2.  Google Scholar [13] S. Mesnager, Linear codes with few weights from weakly regular bent functions based on a generic construction, Cryptogr. Commun., 9 (2017), 71-84.  doi: 10.1007/s12095-016-0186-5.  Google Scholar [14] S. Mesnager, F. Ozbudak and A. Sinak, Linear codes from weakly regular plateaued functions and their secret sharing schemes, Des. Codes Cryptogr., 87 (2019), 463-480.  doi: 10.1007/s10623-018-0556-4.  Google Scholar [15] N. Pippenger, Sorting and selecting in rounds, SIAM J. Comput., 16 (1987), 1032-1038.  doi: 10.1137/0216066.  Google Scholar [16] Y. Qi, C. Tang and D. Huang, Binary linear codes with few weights, IEEE Commun. Lett., 20 (2016), 208-211.   Google Scholar [17] O. Reingold, S. Vadhan and A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders, Ann. of Math., 155 (2002), 157-187.  doi: 10.2307/3062153.  Google Scholar [18] C. Tang, N. Li, Y. Qi, Z. Zhou and T. Helleseth, Linear codes with two or three weights from weakly regular bent functions, IEEE Trans. Inform. Theory, 62 (2016), 1166-1176.  doi: 10.1109/TIT.2016.2518678.  Google Scholar [19] C. Williamson, Spectral Graph Theory, Expanders, and Ramanujan Graphs, University of Washington, 2014. Available from: https://sites.math.washington.edu/morrow/papers/chris-thesis.pdf. Google Scholar [20] C. Xiang, It is indeed a fundamental construction of all linear codes, arXiv: 1610.06355. Google Scholar
 [1] Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68. [2] Rui Wang, Rundong Zhao, Emily Ribando-Gros, Jiahui Chen, Yiying Tong, Guo-Wei Wei. HERMES: Persistent spectral graph software. Foundations of Data Science, 2021, 3 (1) : 67-97. doi: 10.3934/fods.2021006 [3] 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 [4] Yusra Bibi Ruhomally, Muhammad Zaid Dauhoo, Laurent Dumas. A graph cellular automaton with relation-based neighbourhood describing the impact of peer influence on the consumption of marijuana among college-aged youths. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021011 [5] Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Existence results and stability analysis for a nonlinear fractional boundary value problem on a circular ring with an attached edge : A study of fractional calculus on metric graph. Networks & Heterogeneous Media, 2021, 16 (2) : 155-185. doi: 10.3934/nhm.2021003 [6] Irena PawŃow, Wojciech M. Zajączkowski. Global regular solutions to three-dimensional thermo-visco-elasticity with nonlinear temperature-dependent specific heat. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1331-1372. doi: 10.3934/cpaa.2017065 [7] Fuzhi Li, Dongmei Xu. Regular dynamics for stochastic Fitzhugh-Nagumo systems with additive noise on thin domains. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3517-3542. doi: 10.3934/dcdsb.2020244 [8] 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 [9] Markus Harju, Jaakko Kultima, Valery Serov, Teemu Tyni. Two-dimensional inverse scattering for quasi-linear biharmonic operator. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021026 [10] Andrea Scapin. Electrocommunication for weakly electric fish. Inverse Problems & Imaging, 2020, 14 (1) : 97-115. doi: 10.3934/ipi.2019065 [11] Hui Yang, Yuzhu Han. Initial boundary value problem for a strongly damped wave equation with a general nonlinearity. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021019 [12] Oleksandr Boichuk, Victor Feruk. Boundary-value problems for weakly singular integral equations. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021094 [13] Ricardo A. Podestá, Denis E. Videla. The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021002 [14] Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709 [15] Pengyan Ding, Zhijian Yang. Well-posedness and attractor for a strongly damped wave equation with supercritical nonlinearity on $\mathbb{R}^{N}$. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1059-1076. doi: 10.3934/cpaa.2021006 [16] Abderrazak Chrifi, Mostafa Abounouh, Hassan Al Moatassime. Galerkin method of weakly damped cubic nonlinear Schrödinger with Dirac impurity, and artificial boundary condition in a half-line. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021030 [17] 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 [18] Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018 [19] Raimund Bürger, Christophe Chalons, Rafael Ordoñez, Luis Miguel Villada. A multiclass Lighthill-Whitham-Richards traffic model with a discontinuous velocity function. Networks & Heterogeneous Media, 2021, 16 (2) : 187-219. doi: 10.3934/nhm.2021004 [20] Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247

2019 Impact Factor: 0.734

Article outline