Abstract
Standard bases of ideals of the polynomial ring R[X] = R[x 1, …, x k ] over a commutative Artinian chain ring R that are concordant with the norm on R have been investigated by D. A. Mikhailov, A. A. Nechaev, and the author. In this paper we continue this investigation. We introduce a new order on terms and a new reduction algorithm, using the coordinate decomposition of elements from R. We prove that any ideal has a unique reduced (in terms of this algorithm) standard basis. We solve some classical computational problems: the construction of a set of coset representatives, the finding of a set of generators of the syzygy module, the evaluation of ideal quotients and intersections, and the elimination problem. We construct an algorithm testing the cyclicity of an LRS-family L R (I), which is a generalization of known results to the multivariate case. We present new conditions determining whether a Ferre diagram \(\mathcal{F}\) and a full system of \(\mathcal{F}\)-monic polynomials form a shift register. On the basis of these results, we construct an algorithm for lifting a reduced Gröbner basis of a monic ideal to a standard basis with the same cardinality.
Similar content being viewed by others
References
W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, American Mathematical Society, Providence (1994), Graduate Studies in Mathematics, Vol. 3.
J. Apel, “Computational ideal theory infinitely generated extension rings,” J. Theoretical Computer Science, 244, 1–33 (2000).
M. F. Atiyah and I. G. MacDonald, Introduction to Commutative Algebra, Addison-Wesley (1969).
E. Byrne and P. Fitzpatrick, “Gröbner bases over Galois rings with an application to decoding alternant codes,” J. Symbolic Comput., 31, 565–584 (2001).
D. Cox, J. Little, and D. O’Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer, Berlin-New York (1992).
C. Faith, Algebra II. Ring Theory, Springer, Berlin (1976).
E. V. Gorbatov, “Standard basis of a polynomial ideal over commutative Artinian chain ring,” Discrete Math. Appl., 14, No. 1, 75–101 (2004).
E. V. Gorbatov and A. A. Nechaev, “A criterion of the cyclicity of a family of linear recurring sequences over a QF-module,” Usp. Mat. Nauk, 56, No. 4 (2001).
F. Kasch, Moduln und Ringe, Teubner, Stuttgart (1977).
L. Kronecker, Vorlesungen über Zahlentheorie, Bd. 1, Teubner, Leipzig (1901).
W. Krull, “Algebraische Theorie der Ringe, II,” Math. Ann., 91, 1–46 (1923).
V. L. Kurakin, A. S. Kuzmin, A. V. Mikhalev, and A. A. Nechaev, “Linear recurring sequences over rings and modules,” J. Math. Sci., 76, No. 6, 2793–2915 (1995).
V. L. Kurakin, A. V. Mikhalev, A. A. Nechaev, and V. N. Tsypyschev, “Linear and polylinear recurring sequences over Abelian groups and modules,” J. Math. Sci., 102, No. 6, 4598–4626 (2000).
V. N. Latyshev, Combinatorial Ring Theory, Standard Bases [in Russian], Izd. Mosk. Univ., Moscow (1988).
P. Lu, A Criterion for Annihilating Ideals of Linear Recurring Sequences over Galois Rings, AAECC-417.
D. A. Mikhailov and A. A. Nechaev, “Canonical generating system of a monic polynomial ideal over a commutative Artinian chain ring,” Diskret. Mat., 13, No. 4, 3–42 (2001).
D. A. Mikhailov and A. A. Nechaev, “Solving systems of polynomial equations over Galois-Eisenstein rings with the use of the canonical generating systems of polynomial ideals,” Discrete Math. Appl., 14, No. 1, 41–73 (2004).
T. Mora, Seven Variations on Standard Bases, Preprint, Univ. de Genova, Dip. di Mathematica, No. 45 (1986).
A. A. Nechaev, “Linear recurring sequences over commutative rings,” Diskret. Mat., 3, No. 4, 105–127 (1991).
A. A. Nechaev, “Linear recurring sequences over quasi-Frobenius modules,” Russian Math. Surveys, 48, No. 3 (1993).
A. A. Nechaev, “Finite quasi-Frobenius modules, applications to codes and linear recurrences,” Fund. Prikl. Mat., 1, No. 1, 229–254 (1995).
A. A. Nechaev, “Polylinear recurring sequences over modules and quasi-Frobenius modules,” in: Proc. First Int. Tainan-Moscow Algebra Workshop, 1994, Walter de Gruyter, Berlin-New York (1996), pp. 283–298.
G. H. Norton and A. Salagean, “Strong Gröbner bases and cyclic codes over a finite-chain ring,” in: Proceedings of the International Workshop on Coding and Cryptography, Paris (2001), pp. 8–12.
L. Robbiano, “On the theory of graded structures,” J. Symbolic Comput., 2, 139–170 (1986).
Author information
Authors and Affiliations
Additional information
__________
Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 10, No. 3, pp. 23–71, 2004.
Rights and permissions
About this article
Cite this article
Gorbatov, E.V. Standard bases concordant with the norm and computations in ideals and polylinear recurring sequences. J Math Sci 139, 6672–6707 (2006). https://doi.org/10.1007/s10958-006-0384-3
Issue Date:
DOI: https://doi.org/10.1007/s10958-006-0384-3