An algorithm for finding symmetric Grobner bases in infinite dimensional rings

ABSTRACT

A symmetric ideal I ⊂ R = K[x₁,x₂,...] is an ideal that is invariant under the natural action of the infinite symmetric group. We give an explicit algorithm to find Grobner bases for symmetric ideals in the infinite dimensional polynomial ring R. This allows for symbolic computation in a new class of rings. In particular, we solve the ideal membership problem for symmetric ideals of R.

REFERENCES

• 1: M. Aschenbrenner and C. J. Hillar. Finite generation of symmetric ideals. Trans. Amer. Math. Soc., 359(11):5171--5192, 2007.
• 2: B. Buchberger. Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems. Aequationes Math., 4:374--383, 1970.
• 3: David A. Cox , John Little , Donal O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3/e (Undergraduate Texts in Mathematics), Springer-Verlag New York, Inc., Secaucus, NJ, 2007
• 4: D. A. Cox, J. Little, and D. O'Shea. Using algebraic geometry, volume 185 of Graduate Texts in Mathematics. Springer, New York, second edition, 2005.
• 5: M. Drton, B. Sturmfels, and S. Sullivant. Algebraic factor analysis: tetrads, pentads and beyond. Probab. Theory Related Fields, 138(3-4):463--493, 2007.
• 6: Jean Charles Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F₅), Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.75-83, July 07-10, 2002, Lille, France [doi>10.1145/780506.780516]
• 7: C. J. Hillar and T. Windfeldt. Minimal generators for symmetric ideals. Proc. Amer. Math. Soc., to appear.
• 8: A. Mead, E. Ruch, and A. Schönhofer. Theory of chirality functions, generalized for molecules with chiral ligands. Theor. Chim. Acta, 29:269--304, 1973.
• 9: E. Ruch and A. Schönhofer. Theorie der chiralit\"atsfunktionen. Theor. Chim. Acta, 19:225--287, 1970.
• 10: E. Ruch, A. Schönhofer, and I. Ugi. Die vandermondesche determinante als n\"aherungsansatz für eine chiralit\"atsbeobachtung, ihre verwendung in der stereochemie und zur berechnung der optischen aktivitat. Theor. Chim. Acta, 7:420--432, 1967.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.m Miscellaneous

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Chemistry; Mathematics and statistics

General Terms:
Algorithms, Theory

Keywords:
Grobner basis, algorithm, invariant ideal, partial ordering, polynomial reduction, symmetric group