Article Contents
Article Contents

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

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.

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

 Citation:

•  [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.