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 Early access  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. CheeY. 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. DavidoffP. 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. GoldreichR. ImpagliazzoL. LevinR. 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. HooryN. 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. LuoX. CaoS. 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. MesnagerF. 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. QiC. Tang and D. Huang, Binary linear codes with few weights, IEEE Commun. Lett., 20 (2016), 208-211.   Google Scholar

[17]

O. ReingoldS. 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. TangN. LiY. QiZ. 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. CheeY. 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. DavidoffP. 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. GoldreichR. ImpagliazzoL. LevinR. 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. HooryN. 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. LuoX. CaoS. 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. MesnagerF. 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. QiC. Tang and D. Huang, Binary linear codes with few weights, IEEE Commun. Lett., 20 (2016), 208-211.   Google Scholar

[17]

O. ReingoldS. 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. TangN. LiY. QiZ. 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]

Gökhan Mutlu. On the quotient quantum graph with respect to the regular representation. Communications on Pure & Applied Analysis, 2021, 20 (2) : 885-902. doi: 10.3934/cpaa.2020295

[2]

J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413

[3]

Ayça Çeşmelioğlu, Wilfried Meidl. Bent and vectorial bent functions, partial difference sets, and strongly regular graphs. Advances in Mathematics of Communications, 2018, 12 (4) : 691-705. doi: 10.3934/amc.2018041

[4]

Chengju Li, Sunghan Bae, Shudi Yang. Some two-weight and three-weight linear codes. Advances in Mathematics of Communications, 2019, 13 (1) : 195-211. doi: 10.3934/amc.2019013

[5]

Yanfeng Qi, Chunming Tang, Zhengchun Zhou, Cuiling Fan. Several infinite families of p-ary weakly regular bent functions. Advances in Mathematics of Communications, 2018, 12 (2) : 303-315. doi: 10.3934/amc.2018019

[6]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

[7]

Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17

[8]

John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16.

[9]

Roberto De Leo, James A. Yorke. The graph of the logistic map is a tower. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021075

[10]

Ayça Çeşmelioǧlu, Wilfried Meidl, Alexander Pott. On the dual of (non)-weakly regular bent functions and self-dual bent functions. Advances in Mathematics of Communications, 2013, 7 (4) : 425-440. doi: 10.3934/amc.2013.7.425

[11]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003

[12]

Roy H. Goodman. NLS bifurcations on the bowtie combinatorial graph and the dumbbell metric graph. Discrete & Continuous Dynamical Systems, 2019, 39 (4) : 2203-2232. doi: 10.3934/dcds.2019093

[13]

Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete & Continuous Dynamical Systems, 2011, 30 (1) : 261-298. doi: 10.3934/dcds.2011.30.261

[14]

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

[15]

Dominique Zosso, Braxton Osting. A minimal surface criterion for graph partitioning. Inverse Problems & Imaging, 2016, 10 (4) : 1149-1180. doi: 10.3934/ipi.2016036

[16]

Mario Jorge Dias Carneiro, Rafael O. Ruggiero. On the graph theorem for Lagrangian minimizing tori. Discrete & Continuous Dynamical Systems, 2018, 38 (12) : 6029-6045. doi: 10.3934/dcds.2018260

[17]

Chun-Xiang Guo, Guo Qiang, Jin Mao-Zhu, Zhihan Lv. Dynamic systems based on preference graph and distance. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1139-1154. doi: 10.3934/dcdss.2015.8.1139

[18]

Liu Hui, Lin Zhi, Waqas Ahmad. Network(graph) data research in the coordinate system. Mathematical Foundations of Computing, 2018, 1 (1) : 1-10. doi: 10.3934/mfc.2018001

[19]

Mario Roy, Mariusz Urbański. Multifractal analysis for conformal graph directed Markov systems. Discrete & Continuous Dynamical Systems, 2009, 25 (2) : 627-650. doi: 10.3934/dcds.2009.25.627

[20]

Mirela Domijan, Markus Kirkilionis. Graph theory and qualitative analysis of reaction networks. Networks & Heterogeneous Media, 2008, 3 (2) : 295-322. doi: 10.3934/nhm.2008.3.295

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (51)
  • HTML views (178)
  • Cited by (0)

Other articles
by authors

[Back to Top]