zbMATH — the first resource for mathematics

The dual of an evaluation code. (English) Zbl 07363100
Let \(S = K[t_1, \ldots , t_s]\) be a polynomial ring over a finite field \( K \) and \( X = \{P_1, \ldots, P_m\}\), \(m\geq 2\), be a set of distinct points in the space \(K^s\). The evaluation map is the K-linear map defined by \(ev: S \rightarrow K^m, f \mapsto (f (P_1), \ldots , f (P_m))\). Let \(L\) be a linear subspace of \(S\). The image of \(L\) under the evaluation map, denoted \(L_X\), is called an evaluation code on \(X\). In this paper, the dual code of \(L_X\), \((L_X)^{\perp}\), is studied by fixing a graded monomial order on \( S\) and using the information encoded in the linear space \(L\), and the quotient ring \(S/I\), where \(I\) is the vanishing ideal of \(X\) consisting of the polynomials of \(S\) that vanish at all points of \(X\). It is shown that the dual of an evaluation code is the evaluation code of the algebraic dual, and an algorithm for computing a basis for the algebraic dual is presented. If \(C_1\) and \(C_2\) are linear codes spanned by standard monomials, then a combinatorial condition for the monomial equivalence of \(C_1\) and the dual \(C_2^{\perp}\) is given. Furthermore, an explicit description of a generator matrix of \(C_2^{\perp}\) in terms of that of \(C_1\) and coefficients of indicator functions is obtained. Moreover, a duality criterion is given for Reed-Muller-type codes in terms of the \(v\)-number and the Hilbert function of a vanishing ideal, which provide an explicit duality for those corresponding to Gorenstein ideals. Finally, in case where the evaluation code is monomial and the set of evaluation points is a degenerate affine space, a classification is given when the dual is a monomial code. An appendix with implementations of the presented algorithms in Macaulay2 is given.
13P25 Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)
14G50 Applications to coding theory and cryptography of arithmetic geometry
94B27 Geometric methods (including applications of algebraic geometry) applied to coding theory
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
Full Text: DOI
[1] Becker, T.; Weispfenning, V., Gröbner bases A Computational Approach to Commutative Algebra, in cooperation with Heinz Kredel, Graduate Texts in Mathematics 141 (1993), New York: Springer, New York · Zbl 0772.13010
[2] Beelen, P.; Datta, M., Generalized Hamming weights of affine Cartesian codes, Finite Fields Appl., 51, 130-145 (2018) · Zbl 1416.94077
[3] Ball T., Camps E., Chimal-Dzul H., Jaramillo-Velez D., López H., Nichols N., Perkins M., Soprunov I., Vera G., Whieldon G.: Coding Theory Package for Macaulay2, submitted. https://arxiv.org/pdf/2007.06795.pdf
[4] Bras-Amorós, M.; O’Sullivan, ME, Duality for some families of correction capability optimized evaluation codes, Adv. Math. Commun., 2, 1, 15-33 (2008) · Zbl 1275.94048
[5] Bruns, W.; Herzog, J., Cohen-Macaulay Rings (1993), Cambridge: Cambridge University Press, Cambridge · Zbl 0788.13005
[6] Camps E., López H., Matthews G., Sarmiento E.: Monomial-Cartesian codes closed under divisibility. De Gruyter Proceedings in Mathematics 199-208 (2020).
[7] Camps E., López H., Matthews, G., Sarmiento, E.: Polar decreasing monomial-Cartesian codes. IEEE Trans. Inform. Theory. 2020. doi:10.1109/TIT.2020.3047624
[8] Carvalho, C., On the second Hamming weight of some Reed-Muller type codes, Finite Fields Appl., 24, 88-94 (2013) · Zbl 1306.94118
[9] Celebi Demirarslan P., Soprunov I.: On dual toric complete intersection codes. Finite Fields Appl. 33 (2015), 118-136. · Zbl 1372.14045
[10] Cooper S.M., Seceleanu A., Tohǎneanu S.O., Vaz Pinto M., Villarreal R.H.: Generalized minimum distance functions and algebraic invariants of Geramita ideals. Adv. Appl. Math. 112 (2020), 101940. · Zbl 1428.13048
[11] Cox, D.; Little, J.; O’Shea, D., Ideals, Varieties, and Algorithms (1992), New York: Springer, New York
[12] Delsarte, P.; Goethals, JM; MacWilliams, FJ, On generalized Reed-Muller codes and their relatives, Inf. Control, 16, 403-442 (1970) · Zbl 0267.94014
[13] Duursma, IM; Rentería, C.; Tapia-Recillas, H., Reed-Muller codes on complete intersections, Appl. Algebra Eng. Commun. Comput., 11, 6, 455-462 (2001) · Zbl 1076.94043
[14] Eisenbud, D., Commutative Algebra with a view toward Algebraic Geometry, Graduate Texts in Mathematics 150 (1995), New York: Springer, New York · Zbl 0819.13001
[15] Eisenbud, D., The Geometry of Syzygies: A Second Course in Commutative Algebra and Algebraic Geometry (2005), New York: Springer, New York · Zbl 1066.14001
[16] Fröberg F., Laksov D.: Compressed Algebras, Lecture Notes in Mathematics 1092 (1984), Springer, pp. 121-151. · Zbl 0558.13007
[17] Geil O.: Evaluation codes from an affine variety code perspective, Advances in algebraic geometry codes, 153-180, Ser. Coding Theory Cryptol., 5, World Sci. Publ., Hackensack, NJ, 2008. · Zbl 1178.94244
[18] Geil, O.; Høholdt, T., Footprints or generalized Bezout’s theorem, IEEE Trans. Inform. Theory, 46, 2, 635-641 (2000) · Zbl 1001.94040
[19] Geil, O.; Pellikaan, R., On the structure of order domains, Finite Fields Appl., 8, 3, 369-396 (2002) · Zbl 1008.13007
[20] Geramita, AV; Kreuzer, M.; Robbiano, L., Cayley-Bacharach schemes and their canonical modules, Trans. Am. Math. Soc., 339, 1, 163-189 (1993) · Zbl 0793.14002
[21] González-Sarabia, M.; Martínez-Bernal, J.; Villarreal, RH; Vivares, CE, Generalized minimum distance functions, J. Algebraic Combin., 50, 3, 317-346 (2019) · Zbl 1430.13049
[22] González-Sarabia, M.; Rentería, C., The dual code of some Reed-Muller type codes, Appl. Algebra Eng. Commun. Comput., 14, 329-333 (2004) · Zbl 1058.94020
[23] González-Sarabia, M.; Rentería, C.; Tapia-Recillas, H., Reed-Muller-type codes over the Segre variety, Finite Fields Appl., 8, 4, 511-518 (2002) · Zbl 1020.94029
[24] Grayson D., Stillman M.: Macaulay \(2, 1996\). Available at http://www.math.uiuc.edu/Macaulay2/.
[25] Heijnen, P.; Pellikaan, R., Generalized Hamming weights of \(q\)-ary Reed-Muller codes, IEEE Trans. Inform. Theory, 44, 1, 181-196 (1998) · Zbl 1053.94581
[26] Higashitani, A., Almost Gorenstein homogeneous rings and their \(h\)-vectors, J. Algebra, 456, 190-206 (2016) · Zbl 1401.13073
[27] Huffman, WC; Pless, V., Fundamentals of Error-Correcting Codes (2003), Cambridge: Cambridge University Press, Cambridge · Zbl 1191.94107
[28] Jaramillo D., Vaz Pinto M., Villarreal R.H.: Evaluation codes and their basic parameters. Des. Codes Cryptogr 89(2), 269-300 (2021). · Zbl 1456.14034
[29] Kreuzer, M.; Robbiano, L., Computational Commutative Algebra 2 (2005), Berlin: Springer, Berlin · Zbl 1090.13021
[30] Little, J., Remarks on generalized toric codes, Finite Fields Appl., 24, 1-14 (2013) · Zbl 1305.94116
[31] López, HH; Manganiello, F.; Matthews, G., Affine Cartesian codes with complementary duals, Finite Fields Appl., 57, 13-28 (2019) · Zbl 07067776
[32] López, HH; Matthews, G.; Soprunov, I., Monomial-Cartesian codes and their duals, with applications to LCD codes, quantum codes, and locally recoverable codes, Des. Codes Cryptogr., 88, 8, 1673-1685 (2020) · Zbl 1454.94127
[33] López, HH; Rentería, C.; Villarreal, RH, Affine cartesian codes, Des. Codes Cryptogr., 71, 1, 5-19 (2014) · Zbl 1312.94118
[34] López H.H., Sarmiento E., Vaz Pinto M., Villarreal R.H.: Parameterized affine codes. Studia Sci. Math. Hungar. 49(3), 406-418 (2012) · Zbl 1289.13022
[35] MacWilliams, FJ; Sloane, NJA, The Theory of Error-Correcting Codes (1977), North-Holland: Elsevier, North-Holland · Zbl 0369.94008
[36] Ruano, D., On the structure of generalized toric codes, J. Symbol. Comput., 44, 5, 499-506 (2009) · Zbl 1163.14017
[37] Soprunov, I., Lattice polytopes in coding theory, J. Algebra Comb. Discrete Struct. Appl., 2, 2, 85-94 (2015) · Zbl 1348.14074
[38] Sørensen, A., Projective Reed-Muller codes, IEEE Trans. Inform. Theory, 37, 6, 1567-1576 (1991) · Zbl 0741.94016
[39] Stanley, R., Hilbert functions of graded algebras, Adv. Math., 28, 57-83 (1978) · Zbl 0384.13012
[40] Stichtenoth, H., Algebraic Function Fields and Codes, Second Edition, Graduate Texts in Mathematics 254 (2009), Berlin: Springer, Berlin
[41] Tochimani, A.; Villarreal, RH, Vanishing ideals over finite fields, Math. Notes, 105, 3, 429-438 (2019) · Zbl 1420.14112
[42] Tsfasman, M.; Vladut, S.; Nogin, D., Algebraic Geometric Codes: Basic Notions (2007), Providence, RI: American Mathematical Society, Providence, RI · Zbl 1127.94001
[43] Villarreal R.H.: Monomial Algebras, 2nd edn. Monographs and Research Notes in Mathematics, Chapman and Hall/CRC, Boca Raton, FL (2015).
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.