Strong blocking sets and minimal codes from expander graphs

Alon, Noga; Bishnoi, Anurag; Das, Shagnik; Neri, Alessandro

doi:10.1090/tran/9205

Strong blocking sets and minimal codes from expander graphs
HTML articles powered by AMS MathViewer

by Noga Alon, Anurag Bishnoi, Shagnik Das and Alessandro Neri;

Trans. Amer. Math. Soc. 377 (2024), 5389-5410

DOI: https://doi.org/10.1090/tran/9205

Published electronically: June 11, 2024

HTML | PDF | Request permission

Abstract:

A strong blocking set in a finite projective space is a set of points that intersects each hyperplane in a spanning set. We provide a new graph theoretic construction of such sets: combining constant-degree expanders with asymptotically good codes, we explicitly construct strong blocking sets in the $(k-1)$-dimensional projective space over $\mathbb {F}_q$ that have size at most $c q k$ for some universal constant $c$. Since strong blocking sets have recently been shown to be equivalent to minimal linear codes, our construction gives the first explicit construction of $\mathbb {F}_q$-linear minimal codes of length $n$ and dimension $k$, for every prime power $q$, for which $n \leq c q k$. This solves one of the main open problems on minimal codes.

References

Gianira N. Alfarano, Martino Borello, and Alessandro Neri, A geometric characterization of minimal codes and their asymptotic performance, Adv. Math. Commun. 16 (2022), no. 1, 115–133. MR 4393725, DOI 10.3934/amc.2020104
Gianira N. Alfarano, Martino Borello, and Alessandro Neri, Outer strong blocking sets, Electron. J. Combin. 31 (2024), no. 2, Paper No. 2.18, 28. MR 4734456, DOI 10.37236/12046
Gianira N. Alfarano, Martino Borello, Alessandro Neri, and Alberto Ravagnani, Three combinatorial perspectives on minimal codes, SIAM J. Discrete Math. 36 (2022), no. 1, 461–489. MR 4381528, DOI 10.1137/21M1391493
Noga Alon, Explicit expanders of every degree and size, Combinatorica 41 (2021), no. 4, 447–463. MR 4328718, DOI 10.1007/s00493-020-4429-x
N. Alon, J. Bruck, J. Naor, M. Naor, and R. M. Roth, Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs, IEEE Trans. Inform. Theory 38 (1992), no. 2, 509–516.
A. Ashikhmin and A. Barg, Minimal vectors in linear codes, IEEE Trans. Inform. Theory 44 (1998), no. 5, 2010–2017. MR 1664103, DOI 10.1109/18.705584
K. S. Bagga, L. W. Beineke, W. D. Goddard, M. J. Lipman, and R. E. Pippert, A survey of integrity, Discrete Appl. Math. 37/38 (1992), 13–28. MR 1176842, DOI 10.1016/0166-218X(92)90122-Q
József Balogh, Tamás Mészáros, and Adam Zsolt Wagner, Two results about the hypercube, Discrete Appl. Math. 247 (2018), 322–326. MR 3843345, DOI 10.1016/j.dam.2018.03.086
C. A. Barefoot, Roger Entringer, and Henda Swart, Vulnerability in graphs—a comparative survey, Proceedings of the first Carbondale combinatorics conference (Carbondale, Ill., 1986), 1987, pp. 13–22. MR 888829
Daniele Bartoli and Matteo Bonini, Minimal linear codes in odd characteristic, IEEE Trans. Inform. Theory 65 (2019), no. 7, 4152–4155. MR 3964847, DOI 10.1109/TIT.2019.2891992
Daniele Bartoli and Martino Borello, Small strong blocking sets by concatenation, SIAM J. Discrete Math. 37 (2023), no. 1, 65–82. MR 4535329, DOI 10.1137/21M145032X
Daniele Bartoli, Antonio Cossidente, Giuseppe Marino, and Francesco Pavese, On cutting blocking sets and their codes, Forum Math. 34 (2022), no. 2, 347–368. MR 4388346, DOI 10.1515/forum-2020-0338
D. Benko, C. Ernst, and D. Lanphier, Asymptotic bounds on the integrity of graphs and separator theorems for graphs, SIAM J. Discrete Math. 23 (2008/09), no. 1, 265–277. MR 2476827, DOI 10.1137/070692698
A. Bishnoi, J. D’haeseleer, D. Gijswijt, and A. Potukuchi, Blocking sets, minimal codes and trifferent codes, arXiv:2301.09457, 2023.
A. Blokhuis, P. Sziklai, and T. Szonyi, Blocking sets in projective spaces, Current Research Topics in Galois Geometry, 2011, pp. 61–84.
Matteo Bonini and Martino Borello, Minimal linear codes arising from blocking sets, J. Algebraic Combin. 53 (2021), no. 2, 327–341. MR 4238182, DOI 10.1007/s10801-019-00930-6
A. E. Brouwer and A. Schrijver, The blocking number of an affine space, J. Combinatorial Theory Ser. A 24 (1978), no. 2, 251–253. MR 480094, DOI 10.1016/0097-3165(78)90013-4
Hervé Chabanne, Gérard Cohen, and Alain Patey, Towards secure two-party computation from the wire-tap channel, Information security and cryptology—ICISC 2013, Lecture Notes in Comput. Sci., vol. 8565, Springer, Cham, 2014, pp. 34–46. MR 3297255, DOI 10.1007/978-3-319-12160-4_{3}
Gérard Cohen and Abraham Lempel, Linear intersecting codes, Discrete Math. 56 (1985), no. 1, 35–43. MR 808084, DOI 10.1016/0012-365X(85)90190-6
Gérard Cohen, Sihem Mesnager, and Hugues Randriam, Yet another variation on minimal linear codes, Adv. Math. Commun. 10 (2016), no. 1, 53–61. MR 3471060, DOI 10.3934/amc.2016.10.53
Gérard D. Cohen, Sihem Mesnager, and Alain Patey, On minimal and quasi-minimal linear codes, Cryptography and coding, Lecture Notes in Comput. Sci., vol. 8308, Springer, Heidelberg, 2013, pp. 85–98. MR 3163591, DOI 10.1007/978-3-642-45239-0_{6}
G. D. Cohen and G. Zémor, Intersecting codes and independent families, IEEE Trans. Inform. Theory 40 (1994), no. 6, 1872–1881.
Alain Couvreur and Hugues Randriambololona, Algebraic geometry codes and some applications, Concise encyclopedia of coding theory, CRC Press, Boca Raton, FL, 2021, pp. 307–361. MR 4598747
Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, and Fernanda Pambianco, Linear nonbinary covering codes and saturating sets in projective spaces, Adv. Math. Commun. 5 (2011), no. 1, 119–147. MR 2770105, DOI 10.3934/amc.2011.5.119
Cunsheng Ding, Linear codes from some 2-designs, IEEE Trans. Inform. Theory 61 (2015), no. 6, 3265–3275. MR 3352515, DOI 10.1109/TIT.2015.2420118
Gy. Dósa, I. Szalkai, and C. Laflamme, The maximum and minimum number of circuits and bases of matroids, Pure Math. Appl. 15 (2004), no. 4, 383–392 (2006). MR 2257751
Szabolcs L. Fancsali and Péter Sziklai, Lines in higgledy-piggledy arrangement, Electron. J. Combin. 21 (2014), no. 2, Paper 2.56, 15. MR 3244822, DOI 10.37236/4149
Arnaldo García and Henning Stichtenoth, A tower of Artin-Schreier extensions of function fields attaining the Drinfel′d-Vlăduţ bound, Invent. Math. 121 (1995), no. 1, 211–222. MR 1345289, DOI 10.1007/BF01884295
Arnaldo Garcia and Henning Stichtenoth, On the asymptotic behaviour of some towers of function fields over finite fields, J. Number Theory 61 (1996), no. 2, 248–273. MR 1423052, DOI 10.1006/jnth.1996.0147
V. Guruswami, A. Rudra, and M. Sudan. Essential coding theory. Draft available at https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/web-coding-book.pdf, 2022.
Tamás Héger and Zoltán Lóránt Nagy, Short minimal codes and covering codes via strong blocking sets in projective spaces, IEEE Trans. Inform. Theory 68 (2022), no. 2, 881–890. MR 4395448, DOI 10.1109/TIT.2021.3123730
Tamás Héger, Balázs Patkós, and Marcella Takáts, Search problems in vector spaces, Des. Codes Cryptogr. 76 (2015), no. 2, 207–216. MR 3357242, DOI 10.1007/s10623-014-9941-9
Shlomo Hoory, Nathan Linial, and Avi Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439–561. MR 2247919, DOI 10.1090/S0273-0979-06-01126-8
Tai Yang Hwang, Decoding linear block codes for minimizing word error rate, IEEE Trans. Inform. Theory 25 (1979), no. 6, 733–737. MR 551274, DOI 10.1109/TIT.1979.1056120
Robert E. Jamison, Covering finite fields with cosets of subspaces, J. Combinatorial Theory Ser. A 22 (1977), no. 3, 253–266. MR 439664, DOI 10.1016/0097-3165(77)90001-2
Jørn Justesen, A class of constructive asymptotically good algebraic codes, IEEE Trans. Inform. Theory IT-18 (1972), 652–656. MR 384313, DOI 10.1109/tit.1972.1054893
T. Kövari, V. T. Sós, and P. Turán, On a problem of K. Zarankiewicz, Colloq. Math. 3 (1954), 50–57. MR 65617, DOI 10.4064/cm-3-1-50-57
Michel Lavrauw and Geertrui Van de Voorde, Field reduction and linear sets in finite geometry, Topics in finite fields, Contemp. Math., vol. 632, Amer. Math. Soc., Providence, RI, 2015, pp. 271–293. MR 3329986, DOI 10.1090/conm/632/12633
A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261–277. MR 963118, DOI 10.1007/BF02126799
G. A. Margulis, Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators, Problemy Peredachi Informatsii 24 (1988), no. 1, 51–60 (Russian); English transl., Problems Inform. Transmission 24 (1988), no. 1, 39–46. MR 939574
J. L. Massey, Minimal codewords and secret sharing, In Proceedings of the 6th joint Swedish-Russian international workshop on information theory, 1993, pp. 276–279.
D. Miklós, Linear binary codes with intersection properties, Discrete Appl. Math. 9 (1984), no. 2, 187–196. MR 761601, DOI 10.1016/0166-218X(84)90018-0
Moshe Morgenstern, Existence and explicit constructions of $q+1$ regular Ramanujan graphs for every prime power $q$, J. Combin. Theory Ser. B 62 (1994), no. 1, 44–62. MR 1290630, DOI 10.1006/jctb.1994.1054
A. Nilli, On the second eigenvalue of a graph, Discrete Math. 91 (1991), no. 2, 207–210. MR 1124768, DOI 10.1016/0012-365X(91)90112-F
Martin Scotti, On the lower bound for the length of minimal codes, Discrete Math. 347 (2024), no. 1, Paper No. 113676, 10. MR 4644284, DOI 10.1016/j.disc.2023.113676
Michael Sipser and Daniel A. Spielman, Expander codes, IEEE Trans. Inform. Theory 42 (1996), no. 6, 1710–1722. Codes and complexity. MR 1465731, DOI 10.1109/18.556667
Amnon Ta-Shma, Explicit, almost optimal, epsilon-balanced codes, STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2017, pp. 238–251. MR 3678185, DOI 10.1145/3055399.3055408
Chunming Tang, Yan Qiu, Qunying Liao, and Zhengchun Zhou, Full characterization of minimal linear codes as cutting blocking sets, IEEE Trans. Inform. Theory 67 (2021), no. 6, 3690–3700. MR 4289345, DOI 10.1109/TIT.2021.3070377
R. Michael Tanner, A recursive approach to low complexity codes, IEEE Trans. Inform. Theory 27 (1981), no. 5, 533–547. MR 650686, DOI 10.1109/TIT.1981.1056404
M. A. Tsfasman and S. G. Vlăduţ, Algebraic-geometric codes, Mathematics and its Applications (Soviet Series), vol. 58, Kluwer Academic Publishers Group, Dordrecht, 1991. Translated from the Russian by the authors. MR 1186841, DOI 10.1007/978-94-011-3810-9
M. A. Tsfasman, S. G. Vlăduţ, and Th. Zink, Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound, Math. Nachr. 109 (1982), 21–28. MR 705893, DOI 10.1002/mana.19821090103
Salil P. Vadhan, Pseudorandomness, Found. Trends Theor. Comput. Sci. 7 (2011), no. 1-3, front matter, 1–336. MR 3019182, DOI 10.1561/0400000010
A. Vince, The integrity of a cubic graph, Discrete Appl. Math. 140 (2004), no. 1-3, 223–239. MR 2064118, DOI 10.1016/j.dam.2003.07.002
Huaxiong Wang and Chaoping Xing, Explicit constructions of perfect hash families from algebraic curves over finite fields, J. Combin. Theory Ser. A 93 (2001), no. 1, 112–124. MR 1807113, DOI 10.1006/jcta.2000.3068