The dual of an evaluation code (Q2035444)

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 \textit{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 \textit{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.