## 1. Introduction

Let be a polynomial ring over a finite field with the standard grading, , let be an integer, and let be the convex hull in of all integral points such that , where is the -th unit vector in . The lattice polytope is called the -th hypersimplex of [15, p. 84]. The affine torus of the affine space is given by , where is the multiplicative group of , and the projective torus of the projective space over the field is given by , where is the image of under the map , . The cardinality of , denoted , is equal to . The vanishing ideal of , denoted , is the graded ideal of generated by all homogeneous polynomials of that vanish at all points of . If and , we denote the set of zeros of in by , and the set of zeros of in by .

The projective toric code of of degree , denoted or simply , is the image of the evaluation map

where is the -vector subspace of generated by all , , such that and is the set of all points of the projective torus of . We may assume that the first entry of each is . A monomial of is in if and only if is squarefree and has degree , that is, an integral point of is in if and only if is in , where . The basic parameters of are the length , the dimension , and the minimum distance

Toric codes were introduced by Hansen [7] and have been actively studied in the last decade, see [13] and the references therein. These codes are affine-variety codes in the sense of [3, p. 1]. If we replace by in the evaluation map, the image of the resulting map is the projective Reed–Muller-type code over the projective torus . The minimum distance of was determined in [12, Theorem 3.5]. Note that is the projective toric code of the convex hull in of all points in such that .

We are set out to solve part of the following problem using the projective footprint function of a graded ideal [9, 10].

###### Problem 1.1.

Find formulas for the minimum distance or more generally for the generalized Hamming weights of the projective toric code .

## 2. Minimum distance of certain projective toric codes

In this section we determine the basic parameters of . To avoid repetitions, we continue to employ the notations and definitions used in Section 1.

Let be a graded ideal of of Krull dimension . The Hilbert function of is:

where . By a theorem of Hilbert [14, p. 58], there is a unique polynomial of degree such that for . The degree of the zero polynomial is .

The degree or multiplicity of , denoted , is the positive integer given by

and if . If , the ideal is referred to as a colon ideal. Note that is a zero-divisor of if and only if .

###### Lemma 2.1.

[9, Lemma 3.2] Let be a subset of the projective space over the finite field and let be its graded vanishing ideal. If is homogeneous, then

###### Lemma 2.2.

[10, Lemma 3.3] Let be the ideal of generated by . If is a zero-divisor of and , then

To prove the next result we use the footprint technique for projective Reed–Muller-type codes introduced in [9]. A polynomial is called squarefree if all its monomials are squarefree.

###### Proposition 2.3.

If , and , then

###### Proof.

We set . If , the inequality clearly holds because its right hand side is positive. Thus we may assume . Hence, by Lemma 2.1, one has and

(2.1) |

Let be the lexicographical order on with . As the ideal is generated by the set [5] and is a Gröbner basis of , the initial ideal of is generated by the set of monomials . Let be the initial term of . Since is squarefree, so is . Note that is a zero-divisor of . Indeed if is regular on , then and because the only associated prime of is , a contradiction because . As , cannot be in . Therefore, by Lemma 2.2, we get

Since , we obtain

(2.2) |

According to [9, Lemma 4.1] the following inequality holds

(2.3) |

Therefore the inequality follows at once from Eqs. (2.1)–(2.3). ∎

###### Lemma 2.4.

Let be a squarefree polynomial of . If for some and , then is a polynomial in the variables and is squarefree.

###### Proof.

We can write , , for , and distinct monomials. Then

(2.4) |

We proceed by contradiction assuming that divides for some and choose and such that divides and does not divides for . As is squarefree, by Eq. (2.4), the monomial must be equal to for some , a contradiction because does not divides . This proves that is a polynomial in the variables . Hence are distinct monomials. As is squarefree, by Eq. (2.4), is squarefree for , that is, is squarefree, as required. ∎

###### Proposition 2.5.

Let be a squarefree polynomial in of total degree at most and let be the affine torus of . If and , then

###### Proof.

We proceed by induction on . Note that because is squarefree. Assume that . Then because . If is a monomial, then and the inequality holds. Thus we may assume that is not a monomial. As and , there are essentially three cases to consider: (a) , where for , (b) , with , and (c) , with . To show the case we need to prove that . Take root of in . In case (a) one has

Then and . Thus has at most roots in , as required. The cases (b) and (c) are also easy to show.

Assume . Then , and . By permuting variables we may assume that occurs in some monomial of of degree .

Case (I): for some . Setting and fixing a graded monomial order on with , by the division algorithm [1, Theorem 1.5.9, p. 30], we can write , for some in such that does not divide any monomial of , that is, is a polynomial in the variables . Making in this equality, we obtain that is the zero polynomial. Thus . If , then and

Thus we may assume that and . As is squarefree and , by Lemma 2.4, it follows that does not contain , is squarefree, and the total degree of is at most . Hence, by induction hypothesis, one has

(2.5) |

where is the affine torus . Let be the elements of . Then

and . Therefore, using the equalities and , together with Eq. (2.5), we get

Case (II): for all . Let be the elements of , let be the polynomial for , and let be the affine torus . There is an inclusion

Hence, applying the induction hypothesis to each , one has

This completes the proof of the inequality. ∎

###### Proposition 2.6.

Let be the projective toric code of of degree . Then

###### Proof.

Assume that . The number of squarefree monomial of of degree is . Then one has . Hence it suffices to show that the evaluation map is injective. Take in , that is, is in . Using that is generated by the set [5], , and the monomials of are squarefree, it follows readily that .

Assume that . Then , , , and . ∎

We come to our main result.

###### Theorem 2.7.

Let be the projective toric code of of degree and let be its minimum distance. Then

###### Proof.

Assume that and . We set and . Let and be the affine and projective torus in and , respectively. There is such that

(2.6) |

Thus, by Proposition 2.3, one has . Consider the squarefree homogeneous polynomial of degree

where for . By Eq. (2.6), to prove the inequality it suffices to show that the polynomial has exactly roots in . If , one has . Thus we need only show the equality . As is equal to , using the inclusion-exclusion principle [2, p. 38, Formula 2.12], we get

The variables occurring in and are disjoint for . Thus counting monomials in each of the intersections one obtains

and consequently the number of zeros of in is given by

(2.7) | |||||

Assume that , and . There is such that . We set and . To prove the inequality pick such that

We can write in standard form . Then is a zero of in if and only if is a zero of in . Setting and noticing , by Proposition 2.5, one has

Thus , as required. Consider the squarefree homogeneous polynomial of degree

where for . To prove the inequality it suffices to show that the polynomial has exactly roots in . Thus we need only show the equality . Since is equal to , , and , using Eq. (2.7) with and noticing , we get

Assume that . Then is generated by and the toric code is generated by , . Since for all , one has .

Assume that . Then , , and . Thus . ∎

The minimum distance of the projective Reed–Muller-type code is non-increasing as a function of [11, Proposition 5.2]. This is no longer the case for the minimum distance of the projective toric code as the next simple example shows.

###### Example 2.8.

For and , the list of values of the length, dimension and minimum distance of are given by the following table.

## Acknowledgments

Computations with Macaulay [6] were important to study some examples to have a better understanding of toric codes over hypersimplices.

## References

- [1] W. W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, GSM 3, American Mathematical Society, 1994.
- [2] M. Aigner, Combinatorial Theory, Springer, 1997.
- [3] E. Ballico, M. Elia and M. Sala, On the evaluation of multivariate polynomials over finite fields, J. Symbolic Comput. 50 (2013), 255–262.
- [4] D. Cox, J. Little and D. O’Shea, Ideals, Varieties, and Algorithms, Springer-Verlag, 1992.
- [5] M. González-Sarabia, C. Rentería and M. Hernández de la Torre, Minimum distance and second generalized Hamming weight of two particular linear codes, Congr. Numer. 161 (2003), 105–116.
- [6] D. Grayson and M. Stillman, Macaulay, 1996. Available via anonymous ftp from math.uiuc.edu.
- [7] J. Hansen, Toric surfaces and error-correcting codes in Coding Theory, Cryptography, and Related Areas, Springer, 132–142, 2000.
- [8] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-correcting Codes, North-Holland, 1977.
- [9] J. Martínez-Bernal, Y. Pitones and R. H. Villarreal, Minimum distance functions of graded ideals and Reed–Muller-type codes, J. Pure Appl. Algebra 221 (2017), 251–275.
- [10] J. Martínez-Bernal, Y. Pitones and R. H. Villarreal, Minimum distance functions of complete intersections, J. Algebra Appl. 17 (2018), no. 11, 1850204 (22 pages).
- [11] C. Rentería, A. Simis and R. H. Villarreal, Algebraic methods for parameterized codes and invariants of vanishing ideals over finite fields, Finite Fields Appl. 17 (2011), no. 1, 81–104.
- [12] E. Sarmiento, M. Vaz Pinto and R. H. Villarreal, The minimum distance of parameterized codes on projective tori, Appl. Algebra Engrg. Comm. Comput. 22 (2011), no. 4, 249–264.
- [13] I. Soprunov, Lattice polytopes in coding theory, J. Algebra Comb. Discrete Struct. Appl. 2 (2015), no. 2, 85–94.
- [14] R. Stanley, Hilbert functions of graded algebras, Adv. Math. 28 (1978), 57–83.
- [15] B. Sturmfels, Gröbner Bases and Convex Polytopes, University Lecture Series 8, American Mathematical Society, Rhode Island, 1996.
- [16] M. Tsfasman, S. Vladut and D. Nogin, Algebraic geometric codes: basic notions, Mathematical Surveys and Monographs 139, American Mathematical Society, Providence, RI, 2007.
- [17] R. H. Villarreal, Monomial Algebras, Second Edition, Monographs and Research Notes in Mathematics, Chapman and Hall/CRC, 2015.

Comments

There are no comments yet.