Harder-Narasimhan theory for linear codes (with an appendix on Riemann-Roch theory). (English) Zbl 1409.14047
G. Harder and M. S. Narasimhan [Math. Ann. 212, 215–248 (1975; Zbl 0324.14006)] proposed a method to study the cohomology of moduli spaces over finite fields. They introduce notions such as slopes, canonical filtration or semistability. An analogue for Euclidean and Hermitian lattices was developed later, see [D. Grayson, Comment. Math. Helv. 59, 600–634 (1984; Zbl 0564.20027)]. The present paper first develops Harder-Narasimhan (HN) theory for combinatorial lattices and then applies it to linear error-correcting codes.
Section 1 studies HN theory for modular lattices \(L\) of finite length. \(L\) equipped with a semimodular function deg: \(L\rightarrow\mathbb{R}\) is called a HN lattice (Definition 1). Then the paper gives the concepts of slopes, canonical filtration and semistability. Example 11 shows that the theory is applicable to matroids. Theorem 17 shows that a Galois connection between two lattices \(L\) and \(M\) induces a degree function making both \(L\) and \(M\) HN lattices.
Section 2 provides HN structures on the lattice \(L_C\) of a \((n,k)\) linear code \(C\). For so doing the paper uses three approaches: the relation between linear codes and Euclidean lattices, see [J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups. With additional contributions by E. Bannai, R. E. Borcherds, J. Leech, S. P. Norton, A. M. Odlyzko, R. A. Parker, L. Queen and B. B. Venkov. 3rd ed. New York, NY: Springer (1999; Zbl 0915.52003)], the algebraic-geometric codes point of view, see [M. A. Tsfasman and S. G. Vlǎduţ, Algebraic-geometric codes. Transl. from the Russian. Dordrecht etc.: Kluwer Academic Publishers (1991; Zbl 0727.94007)] and a Galois connection between \(L_C\) and the lattice of the subsets of \(\{1,\dots,n\}\). Proposition 19 proves that the three HN structures are the same.
Section 3 studies the relationship between the canonical filtration and the slopes of a code \(C\) and those of its dual code (Corollary 36). Corollary 37 states that \(C\) is semistable if and only if its dual is. Section 4 shows that if two codes \(A\) and \(B\) are semistables their tensor product \(A\otimes B\) is also semistable (Theorem 39).
Finally an Appendix develops a Riemann-Roch theory for linear codes and matroids.
Section 1 studies HN theory for modular lattices \(L\) of finite length. \(L\) equipped with a semimodular function deg: \(L\rightarrow\mathbb{R}\) is called a HN lattice (Definition 1). Then the paper gives the concepts of slopes, canonical filtration and semistability. Example 11 shows that the theory is applicable to matroids. Theorem 17 shows that a Galois connection between two lattices \(L\) and \(M\) induces a degree function making both \(L\) and \(M\) HN lattices.
Section 2 provides HN structures on the lattice \(L_C\) of a \((n,k)\) linear code \(C\). For so doing the paper uses three approaches: the relation between linear codes and Euclidean lattices, see [J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups. With additional contributions by E. Bannai, R. E. Borcherds, J. Leech, S. P. Norton, A. M. Odlyzko, R. A. Parker, L. Queen and B. B. Venkov. 3rd ed. New York, NY: Springer (1999; Zbl 0915.52003)], the algebraic-geometric codes point of view, see [M. A. Tsfasman and S. G. Vlǎduţ, Algebraic-geometric codes. Transl. from the Russian. Dordrecht etc.: Kluwer Academic Publishers (1991; Zbl 0727.94007)] and a Galois connection between \(L_C\) and the lattice of the subsets of \(\{1,\dots,n\}\). Proposition 19 proves that the three HN structures are the same.
Section 3 studies the relationship between the canonical filtration and the slopes of a code \(C\) and those of its dual code (Corollary 36). Corollary 37 states that \(C\) is semistable if and only if its dual is. Section 4 shows that if two codes \(A\) and \(B\) are semistables their tensor product \(A\otimes B\) is also semistable (Theorem 39).
Finally an Appendix develops a Riemann-Roch theory for linear codes and matroids.
Reviewer: Juan Tena Ayuso (Valladolid)
MSC:
| 14G50 | Applications to coding theory and cryptography of arithmetic geometry |
| 94B27 | Geometric methods (including applications of algebraic geometry) applied to coding theory |
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
| 06C05 | Modular lattices, Desarguesian lattices |
| 06C10 | Semimodular lattices, geometric lattices |
| 11H71 | Relations with coding theory |
| 14G40 | Arithmetic varieties and schemes; Arakelov theory; heights |
| 14H60 | Vector bundles on curves and their moduli |
| 14L24 | Geometric invariant theory |
| 94B05 | Linear codes (general theory) |
| 94B75 | Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory |
Keywords:
Harder-Narasimhan theory; Euclidean and Hermitian lattices; combinatorial lattices; linear codes; matroids; slopes; canonical filtration; semistability; Galois connection; sphere-packing; algebraic-geometric codes; Riemann-Roch theoremReferences:
| [1] | André, Y., Slope filtrations, Confluentes Math., 1, 1-85 (2009) · Zbl 1213.14039 |
| [2] | Assmus, E., The category of linear codes, IEEE Trans. Inf. Theory, 44, 612-629 (1998) · Zbl 1105.94335 |
| [3] | Birkhoff, G., Lattice Theory, Colloquium Publ., vol. 25 (1979), Amer. Math. Soc.: Amer. Math. Soc. Providence · Zbl 0126.03801 |
| [4] | Borek, T., Successive minima and slopes of Hermitian vector bundles over number fields, J. Number Theory, 113, 380-388 (2005) · Zbl 1100.14513 |
| [5] | Borel, A.; Serre, J.-P., Corners and arithmetic groups, Comment. Math. Helv., 48, 436-491 (1973) · Zbl 0274.22011 |
| [6] | Bost, J.-B.; Chen, H., Concerning the semistability of tensor products in Arakelov geometry, J. Math. Pures Appl., 99, 436-488 (2013) · Zbl 1286.14040 |
| [7] | Bost, J.-B.; Künnemann, K., Hermitian vector bundles and extension groups on arithmetic schemes. I. Geometry of numbers, Adv. Math., 223, 987-1106 (2010) · Zbl 1187.14027 |
| [8] | Chen, H., Harder-Narasimhan categories, J. Pure Appl. Algebra, 214, 187-200 (2010) · Zbl 1186.18006 |
| [9] | H. Chen, Personal communication, 2016.; H. Chen, Personal communication, 2016. |
| [10] | Conway, J.; Sloane, N., Sphere Packings, Lattices and Groups, Grundlehren der Math. Wissenschaften, vol. 290 (1999), Springer-Verlag: Springer-Verlag New York · Zbl 0915.52003 |
| [11] | Cornut, C., On Harder-Narasimhan filtrations and their compatibility with tensor products, Confluentes Math. (2018), in press · Zbl 1484.18018 |
| [12] | Dolgachev, I., Lectures on Invariant Theory, London Mathematical Society Lecture Note Series, vol. 296 (2003), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1023.13006 |
| [13] | Dolgachev, I.; Ortland, D., Point sets in projective spaces and theta functions, Astérisque, 165 (1988) · Zbl 0685.14029 |
| [14] | Ebeling, W., Lattices and Codes, Advanced Lectures in Math. (2013), Springer Spektrum: Springer Spektrum Wiesbaden · Zbl 1257.11066 |
| [15] | Faltings, G.; Wüstholz, G., Diophantine approximations on projective spaces, Invent. Math., 116, 109-138 (1994) · Zbl 0805.14011 |
| [16] | Gaudron, É.; Rémond, G., Minima, pentes et algèbre tensorielle, Isr. J. Math., 195, 565-591 (2013) · Zbl 1295.11126 |
| [17] | Gieseker, D., Stable vector bundles and the Frobenius morphism, Ann. Sci. Éc. Norm. Supér. (4), 6, 95-101 (1973) · Zbl 0281.14013 |
| [18] | Grayson, D., Reduction theory using semistability, Comment. Math. Helv., 59, 600-634 (1984) · Zbl 0564.20027 |
| [19] | Harder, G.; Narasimhan, M., On the cohomology groups of moduli spaces of vector bundles on curves, Math. Ann., 212, 215-248 (1975) · Zbl 0324.14006 |
| [20] | Mumford, D.; Fogarty, J.; Kirwan, F., Geometric Invariant Theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (2), vol. 34 (1994), Springer-Verlag: Springer-Verlag Berlin · Zbl 0797.14004 |
| [21] | Oxley, J., Matroid Theory, Oxford Science Publications (1992), The Clarendon Press, Oxford University Press: The Clarendon Press, Oxford University Press New York · Zbl 0784.05002 |
| [22] | Randriambololona, H., On products and powers of linear codes under componentwise multiplication, (Algorithmic Arithmetic, Geometry, and Coding Theory. Algorithmic Arithmetic, Geometry, and Coding Theory, Contemp. Math., vol. 637 (2015), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 3-78 · Zbl 1397.94119 |
| [23] | Schaathun, H., The weight hierarchy of product codes, IEEE Trans. Inf. Theory, 46, 2648-2651 (2000) · Zbl 1001.94053 |
| [24] | Slepian, D., Some further theory of group codes, Bell Syst. Tech. J., 39, 1219-1252 (1960) |
| [25] | Stuhler, U., Eine Bemerkung zur Reduktionstheorie quadratischer Formen, Arch. Math., 27, 604-610 (1976) · Zbl 0338.10024 |
| [26] | Totaro, B., Tensor products of semistables are semistable, (Geometry and Analysis on Complex Manifolds (1994), World Sci. Publ.: World Sci. Publ. River Edge, NJ), 242-250 · Zbl 0873.14016 |
| [27] | Tsfasman, M.; Vladut, S., Algebraic-Geometric Codes, Mathematics and Its Appl. (Soviet Series), vol. 58 (1991), Kluwer Acad. Publ. Group: Kluwer Acad. Publ. Group Dordrecht · Zbl 0727.94007 |
| [28] | Tsfasman, M.; Vladut, S., Geometric approach to higher weights, IEEE Trans. Inf. Theory, 41, 1564-1588 (1995) · Zbl 0853.94023 |
| [29] | Wei, V., Generalized Hamming weights for linear codes, IEEE Trans. Inf. Theory, 37, 1412-1418 (1991) · Zbl 0735.94008 |
| [30] | Wei, V.; Yang, K., On the generalized Hamming weights of product codes, IEEE Trans. Inf. Theory, 39, 1709-1713 (1993) · Zbl 0801.94016 |
| [31] | Whitney, H., On the abstract properties of linear independence, Am. J. Math., 57, 509-533 (1935) · JFM 61.0073.03 |
| [32] | Adiprasito, K.; Huh, J.; Katz, E., Hodge theory for combinatorial geometries (2015), Preprint |
| [33] | Baker, M.; Norine, S., Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math., 215, 766-788 (2007) · Zbl 1124.05049 |
| [34] | Borisov, A., Convolution structures and arithmetic cohomology, Compos. Math., 136, 237-254 (2003) · Zbl 1158.11340 |
| [35] | Bost, J.-B., Theta invariants of Euclidean lattices and infinite-dimensional Hermitian vector bundles over arithmetic curves (2015), Preprint |
| [36] | Britz, T.; Johnsen, T.; Mayhew, D.; Shiromoto, K., Wei-type duality theorems for matroids, Des. Codes Cryptogr., 62, 331-341 (2012) · Zbl 1236.05054 |
| [37] | Duursma, I., Weight distributions of geometric Goppa codes, Trans. Am. Math. Soc., 351, 3609-3639 (1999) · Zbl 0927.94019 |
| [38] | Duursma, I., Combinatorics of the two-variable zeta function, (Finite Fields and Applications. Finite Fields and Applications, Lecture Notes in Comput. Sci., vol. 2948 (2004), Springer: Springer Berlin), 109-136 · Zbl 1080.11063 |
| [39] | Forney, G., Dimension/length profiles and trellis complexity of linear block codes, IEEE Trans. Inf. Theory, 40, 1741-1752 (1994) · Zbl 0826.94019 |
| [40] | van der Geer, G.; Schoof, R., Effectivity of Arakelov divisors and the theta divisor of a number field, Sel. Math. New Ser., 6, 377-398 (2000) · Zbl 1030.11063 |
| [41] | Gillet, H.; Soulé, C., On the number of lattice points in convex symmetric bodies and their duals, Isr. J. Math., 74, 347-357 (1991) · Zbl 0752.52008 |
| [42] | Groenewegen, R., An arithmetic analogue of Clifford’s theorem, J. Théor. Nr. Bordx., 13, 143-156 (2001) · Zbl 1069.11044 |
| [43] | Katz, E., Matroid theory for algebraic geometers, (Baker, M.; Payne, S., Nonarchimedean and Tropical Geometry. Nonarchimedean and Tropical Geometry, Simons Symposia (2016), Springer), 435-517 · Zbl 1353.05034 |
| [44] | Munuera, C., On the generalized Hamming weights of geometric Goppa codes, IEEE Trans. Inf. Theory, 40, 2092-2099 (1994) · Zbl 0826.94023 |
| [45] | Roessler, D., The Riemann-Roch Theorem for Arithmetic Curves (1993), ETH Diplomarbeit |
| [46] | Schmidt, F. K., Analytische Zahlentheorie in Körpern der Charakteristik \(p\), Math. Z., 33, 1-32 (1931) · Zbl 0001.05401 |
| [47] | Soulé, C., Hermitian vector bundles on arithmetic varieties, (Algebraic Geometry—Santa Cruz 1995. Algebraic Geometry—Santa Cruz 1995, Proc. Sympos. Pure Math., vol. 62(1) (1997), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 383-419 · Zbl 0926.14011 |
| [48] | Stichtenoth, H., Algebraic Function Fields and Codes, Graduate Texts in Math., vol. 254 (2009), Springer-Verlag: Springer-Verlag Berlin · Zbl 1155.14022 |
| [49] | Szpiro, L., Degrés, intersections, hauteurs, Séminaire sur les pinceaux arithmétiques. La conjecture de Mordell. Séminaire sur les pinceaux arithmétiques. La conjecture de Mordell, Astérisque, 127, 445-450 (1985) · Zbl 1182.11029 |
| [50] | Tate, J., Fourier Analysis in Number Fields, and Hecke’s Zeta-Functions, (Cassels, J.; Fröhlich, A., Algebraic Number Theory (1986), Academic Press: Academic Press London) (1950), Princeton University, Reprinted · Zbl 1492.11154 |
| [51] | Yang, K.; Kumar, P. V.; Stichtenoth, H., On the weight hierarchy of geometric Goppa codes, IEEE Trans. Inf. Theory, 40, 913-920 (1994) · Zbl 0821.94031 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
