Gröbner bases of symmetric ideals. (English) Zbl 1277.13001

Steidel, Stefan

J. Symb. Comput. 54, 72-86 (2013).

Summary: We present two new algorithms to compute the Gröbner basis of an ideal that is invariant under certain permutations of the ring variables and which are both implemented in Singular (cf. Decker et al., 2012). The first and major algorithm is most performant over finite fields whereas the second algorithm is a probabilistic modification of the modular computation of Gröbner bases based on the articles by [E. A. Arnold, J. Symb. Comput. 35, No. 4, 403-419 (2003; Zbl 1046.13018); N. Idrees, G. Pfister and S. Steidel, J. Symb. Comput. 46, No. 6, 672–684 (2011; Zbl 1229.13002)] and M. Noro and K. Yokoyama [“Usage of modular techniques for efficient computation of ideal operation”, in preparation (2012)]. In fact, the first algorithm that mainly uses the given symmetry, improves the necessary modular calculations in positive characteristic in the second algorithm. Particularly, we could, for the first time even though probabilistic, compute the Gröbner basis of the famous ideal of cyclic 9-roots (cf. [G. Björck and R. Fröberg, J. Symb. Comput. 12, 329–336 (1991; Zbl 0751.12001)]) over the rationals with Singular.

MSC:

13-04	Software, source code, etc. for problems pertaining to commutative algebra
13P10	Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30	Symbolic computation and algebraic computation
13F20	Polynomial rings and ideals; rings of integer-valued polynomials

Keywords:

Gröbner bases; symmetry; modular computation; parallel computation

Citations:

Zbl 1046.13018; Zbl 1229.13002; Zbl 0751.12001

Software:

SINGULAR

References:

[1]	Arnold, E. A., Modular algorithms for computing Gröbner bases, Journal of Symbolic Computation, 35, 403-419 (2003) · Zbl 1046.13018
[2]	Aschenbrenner, M.; Hillar, C., Finite generation of symmetric ideals, Transactions of the American Mathematical Society, 359, 5171-5192 (2007) · Zbl 1129.13008
[3]	Aschenbrenner, M.; Hillar, C., An algorithm for finding symmetric Gröbner bases in infinite dimensional rings (2008), Preprint, available at · Zbl 1487.13054
[4]	Björck, G., Functions of modulus on \(Z_p\) whose Fourier transforms have constant modulus, (Proc. A. Haar Memorial Conference. Proc. A. Haar Memorial Conference, Colloquia Mathematica Societatis János Bolyai, vol. 49 (1985), Budapest), 193-197
[5]	Björck, G., Functions of modulus on \(Z_n\) whose Fourier transforms have constant modulus, and “cyclic \(n\)-roots”, (Byrnes, J. S.; Byrnes, J. F., Recent Advances in Fourier Analysis and its Applications. Recent Advances in Fourier Analysis and its Applications, NATO Advanced Study Institutes Series. Series C, Mathematical and Physical Sciences (1990), Kluwer), 131-140 · Zbl 0726.43004
[6]	Björck, G.; Fröberg, G., A faster way to count the solution of inhomogeneous systems of algebraic equations, with applications to cyclic \(n\)-roots, Journal of Symbolic Computation, 12, 329-336 (1991) · Zbl 0751.12001
[8]	Decker, W.; Greuel, G.-M.; Pfister, G.; Schönemann, H., Singular 3-1-6 — A computer algebra system for polynomial computations (2012)
[9]	Faugère, J.-C.; Gianni, P.; Lazard, D.; Mora, T., Efficient computation of zero-dimensional Gröbner bases by change of ordering, Journal of Symbolic Computation, 16, 329-344 (1993) · Zbl 0805.13007
[11]	Greuel, G.-M.; Pfister, G., A Singular Introduction to Commutative Algebra (2007), Springer
[12]	Idrees, N.; Pfister, G.; Steidel, S., Parallelization of modular algorithms, Journal of Symbolic Computation, 46, 672-684 (2011) · Zbl 1229.13002
[13]	Malle, G., Fields of definition of some three point ramified field extensions, (The Grothendieck Theory of Dessins dʼEnfants. The Grothendieck Theory of Dessins dʼEnfants, London Mathematical Society Lecture Notes, vol. 200 (1994), Cambridge University Press: Cambridge University Press Cambridge), 147-168 · Zbl 0871.14021
[14]	Malle, G.; Matzat, B. H., Inverse Galois Theory (1999), Springer · Zbl 0940.12001
[15]	Matzat, B. H., Konstruktive Galoistheorie, Lecture Notes in Mathematics, vol. 1284 (1987), Springer · Zbl 0634.12011
[17]	Pachter, L.; Sturmfels, B., Algebraic Statistics for Computational Biology (2005), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1108.62118
[18]	Serre, J.-P., Linear Representations of Finite Groups, Graduate Texts in Mathematics, vol. 42 (1996), Springer
[19]	Sturmfels, B., Open problems in algebraic statistics, (Putinar, M.; Sullivant, S., Emerging Applications of Algebraic Geometry. Emerging Applications of Algebraic Geometry, I.M.A. Volumes in Mathematics and Its Applications, vol. 149 (2008), Springer), 351-364
[20]	Yokoyama, K., Usage of modular techniques for efficient computation of ideal operations (Invited talk), (Gerdt, V. P.; Koepf, W.; Mayr, E. W.; Vorozhtsov, E. V., Computer Algebra in Scientific Computing. Computer Algebra in Scientific Computing, Lecture Notes in Computer Science, vol. 7442 (2012), Springer), 361-362
[21]	Zhu, M.; Jiang, G.; Gao, S., Solving the 100 Swiss Francs Problem, Mathematics in Computer Science, 5, 195-207 (2011) · Zbl 06112129