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

Jong Yoon Hyun; Yoonjin Lee; Yansheng Wu

doi:10.3934/amc.2020133

Article Contents

2023, Volume 17, Issue 2: 367-380. Doi: 10.3934/amc.2020133

This issue Previous Article Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems Next Article Character sums over a non-chain ring and their applications

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

Early access: March 2021

Published: April 2023

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)

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 11T71, 05E30, 94B05, 94C11,.

Citation:

Full Text(HTML)

Related Papers

Cited by

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.
[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.
[3]	G. Davidoff, P. Sarnak and A. Valette, Elementary Number Theory, Group Theory, and Ramanujan Graphs, Cambridge Univ. Press, 2003. doi: 10.1017/CBO9780511615825.
[4]	C. Ding, Linear codes from some 2-designs, IEEE Trans. Inform. Theory, 61 (2015), 3265-3275. doi: 10.1109/TIT.2015.2420118.
[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.
[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.
[7]	C. D. Godsil, Algebraic Combinatorics, Chapman & Hall/CRC, 1993.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[15]	N. Pippenger, Sorting and selecting in rounds, SIAM J. Comput., 16 (1987), 1032-1038. doi: 10.1137/0216066.
[16]	Y. Qi, C. Tang and D. Huang, Binary linear codes with few weights, IEEE Commun. Lett., 20 (2016), 208-211.
[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.
[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.
[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.
[20]	C. Xiang, It is indeed a fundamental construction of all linear codes, arXiv: 1610.06355.