Gröbner bases over Galois rings with an application to decoding alternant codes (Q5938546)

A theory of Gröbner bases over Galois rings is developed in a manner similar to that available for finite fields. All rings considered are finite, local, commutative with unity. Let \(T\) have a maximal ideal \(\langle p\rangle\) for some prime \(p\) and call \(f \in T[x]\) a basic irreducible if it is irreducible modulo \(p\). For \(m, n\) positive integers let \(f \in {\mathbb Z}_{p^n} [x]\) be a basic irreducible polynomial of degree \(m\). The quotient ring \({\mathbb Z}_{p^n} [x]/\langle f\rangle\) is called the Galois ring of order \(p^{mn}\) and characteristic \(p^n\), denoted by \(\text{GR}(p^{mn} ,p^n)\). An arbitrary Galois ring is denoted \(R\), its multiplicative group of units \(R^*\), \(k_R\) the residue field of \(R\) and \(\mu\) the natural endomorphism defined by: \(\mu : R \rightarrow k_R : a \mapsto a+\langle p\rangle\). The notion of Gröbner bases in \(R[x]\) is investigated first by considering the division process in \(R\) in which, due to the presence of zero divisors, the process is generalized to the process of reduction. This is used to give a division algorithm in \(R[x]\) and then a characterization of Gröbner bases in \(R[x]\). It is shown how to use these notions to compute a Gröbner basis for an ideal from a given generating set. The approach is essentially a generalization of Buchberger's algorithm. The application of the theory is to the problem of decoding alternant codes over Galois rings. In this application the module \[ M = \{ (a,b) : aS \equiv b \pmod{x^r } \} \] is the set of all solutions to the key equation for decoding alternant codes, where \(S\) is the syndrome polynomial. A solution is sought satisfying certain conditions. Such a solution is found in a Gröbner basis and an algorithm is given to determine this solution using the techniques of the paper.