Generalized minimum distance functions

DOI10.1007/S10801-018-0855-XMaRDI QIDQ2011392zbMATH OpenOpenAlexFDO

Authors José Martínez-Bernal, Rafael H. Villarreal, Carlos E. Vivares, Manuel González Sarabia

Publication date 6 December 2019

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.03285

footprint function higher weights Hilbert function Reed-Muller type codes

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Applications to coding theory and cryptography of arithmetic geometry (14G50) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)

Abstract: Using commutative algebra methods we study the generalized minimum distance function (gmd function) and the corresponding generalized footprint function of a graded ideal in a polynomial ring over a field. The number of solutions that a system of homogeneous polynomials has in any given finite set of projective points is expressed as the degree of a graded ideal. If

m a t h b b X

is a set of projective points over a finite field and

I

is its vanishing ideal, we show that the gmd function and the Vasconcelos function of

I

are equal to the

r

-th generalized Hamming weight of the corresponding Reed-Muller-type code

C_{m} a t h b b X (d)

of degree

d

. We show that the generalized footprint function of

I

is a lower bound for the

r

-th generalized Hamming weight of

C_{m} a t h b b X (d)

. Then we present some applications to projective nested cartesian codes. To give applications of our lower bound to algebraic coding theory, we show an interesting integer inequality. Then we show an explicit formula and a combinatorial formula for the second generalized Hamming weight of an affine cartesian code.

Review text

The higher Hamming weights of a linear code, a natural generalization of the minimum distance of the code, introduced by \textit{V. K. Wei}, IEEE Trans. Inf. Theory 37, No. 5, 1412--1418 (1991; Zbl 0735.94008)], are important parameters of the code, in particular for their applications to cryptography. In [\textit{J. Martínez-Bernal} et al., J. Pure Appl. Algebra 221 No. 2, 251--275 (2017; Zbl 1352.13016)] the authors introduced the notion of \textit{minimum distance function} of a graded ideal as a generalization of the minimum distance of Reed-Muller codes. In the paper under review, the authors consider an extension of this notion introducing the concept of \textit{generalized minimum distance function} \(\delta_I(d,r)\) of a graded ideal \(I\) of a polynomial ring \(S=K[t_1,\ldots,t_s]\) over a field \(K\), with the usual grading. The motivating idea is that this concept would generalize the higher Hamming weights of a linear code and also recovers the minimum distance function of a graded ideal when \(r=1\). One of their firsts results (Theorem 4.5) shows that if \(X\subseteq {\mathbb P}^{s-1}\) is a subset of the projective space over a finite field \({\mathbb F}_q\) and if \(I(X)\) is its vanishing ideal, the generalized minimum distance function \(\delta_{I(X)}(d,r)\) of \(I(X)\) is the \(r\)-th higher weight of the corresponding Reed-Muller type code of degree \(d\). With the aim of finding lower bounds for the generalized minimum distance function \(\delta_I(d,r)\) the authors introduce a generalization of the footprint function of a graded ideal and prove in Theorem 4.9 that this generalized footprint function of \(I\) is a lower bound of the higher weight of the corresponding Reed-Muller type code of degree \(d\). As an application the authors consider projective nested codes [\textit{C. Carvalho} et al., Bull. Braz. Math. Soc. (NS) 48 No. 2, 283--302 (2017; Zbl 1386.14099)] and give a lower bound for the minimum distance of some of these codes in Theorem 5.5. Using \texttt{Macaulay2} in Sections 6 and 7 the authors compute some examples that illustrate how to use their methods giving the corresponding procedures for each example. Further applications include an explicit combinatorial formula for the second higher Hamming weight of an affine Cartesian code (Theorem 9.3).

Recommendations

Cites work

Cited in

(24)

Describes a project that uses

Uses Software

Macaulay2

This page was built for publication: Generalized minimum distance functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2011392)