doi: 10.3934/amc.2020133
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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.

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

[3] G. DavidoffP. 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. 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.

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

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

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

[15]

N. Pippenger, Sorting and selecting in rounds, SIAM J. Comput., 16 (1987), 1032-1038.  doi: 10.1137/0216066.

[16]

Y. QiC. Tang and D. Huang, Binary linear codes with few weights, IEEE Commun. Lett., 20 (2016), 208-211. 

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

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

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

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.

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

[3] G. DavidoffP. 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. 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.

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

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

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

[15]

N. Pippenger, Sorting and selecting in rounds, SIAM J. Comput., 16 (1987), 1032-1038.  doi: 10.1137/0216066.

[16]

Y. QiC. Tang and D. Huang, Binary linear codes with few weights, IEEE Commun. Lett., 20 (2016), 208-211. 

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

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

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

[1]

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

[2]

Rumi Melih Pelen. Three weight ternary linear codes from non-weakly regular bent functions. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022020

[3]

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

[4]

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

[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]

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

[7]

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

[8]

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

[9]

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

[10]

Roberto De Leo, James A. Yorke. The graph of the logistic map is a tower. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 5243-5269. doi: 10.3934/dcds.2021075

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Tonghui Zhang, Hong Lu, Shudi Yang. Two-weight and three-weight linear codes constructed from Weil sums. Mathematical Foundations of Computing, 2022, 5 (2) : 129-144. doi: 10.3934/mfc.2021041

[19]

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

[20]

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

2020 Impact Factor: 0.935

Article outline

[Back to Top]