Reed-Muller type codes over a combinatorial simplex: an algebraic description
For coding theorists, this work offers algebraic tools to analyze CAP codes, which are important for achieving high rates with fixed minimum distance.
The paper provides an algebraic description of CAP codes, a high-rate alternative to Reed-Muller codes, using commutative algebra. It gives a universal Gröbner basis for the vanishing ideal of a combinatorial simplex, describes generalized Hamming weights in terms of the footprint, and proves a closed formula for minimum distance.
Given an ordered set $B$ of a finite field, a combinatorial simplex over $B$ is defined as the set of vectors such that the positions of the entries, with respect to $B$, sum up to a fixed integer. CAP codes are Reed-Muller type codes defined over a combinatorial simplex. They were recently introduced by Kopparty et al. as a high-rate alternative to classical Reed-Muller codes, capable of achieving arbitrarily high rates close to one for any fixed minimum distance. In this paper, we use tools from commutative algebra to analyze a combinatorial simplex and its associated CAP code. We give a universal Gröbner basis for the vanishing ideal of a combinatorial simplex. We describe the generalized Hamming weights of a CAP code in terms of the footprint of the vanishing ideal. For the minimum distance case, we proved a closed formula. We give a set of polynomials whose evaluations on the combinatorial simplex generate the dual of the CAP code. We describe the affine permutations that leave invariant a combinatorial simplex and use this information to prove that, in some cases, the permutation group of a CAP code is a symmetric group.