Computation of invariants of finite abelian groups

Hubert, Evelyne; Labahn, George

doi:10.1090/mcom/3076

Computation of invariants of finite abelian groups
HTML articles powered by AMS MathViewer

by Evelyne Hubert and George Labahn PDF

Math. Comp. 85 (2016), 3029-3050 Request permission

Abstract:

We investigate the computation and applications of rational invariants of the linear action of a finite abelian group in the nonmodular case. By diagonalization, such a group action can be described by integer matrices of orders and exponents. We make use of integer linear algebra to compute a minimal generating set of invariants along with the substitution needed to rewrite any invariant in terms of this generating set. In addition, we show how to construct a minimal generating set that consists only of polynomial invariants. As an application, we provide a symmetry reduction scheme for polynomial systems whose solution set is invariant by a finite abelian group action. Finally, we also provide an algorithm to find such symmetries given a polynomial system.

References

Danko Adrovic and Jan Verschelde, Computing Puiseux series for algebraic surfaces, ISSAC 2012—Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2012, pp. 20–27. MR 3206282, DOI 10.1145/2442829.2442837
Alexander Bockmayr and Friedrich Eisenbrand, Cutting planes and the elementary closure in fixed dimension, Math. Oper. Res. 26 (2001), no. 2, 304–312. MR 1895830, DOI 10.1287/moor.26.2.304.10555
H. E. A. Campbell and J. Chuai, Invariant fields and localized invariant rings of $p$-groups, Q. J. Math. 58 (2007), no. 2, 151–157. MR 2334859, DOI 10.1093/qmath/ham011
A. Charnow, On the fixed field of a linear abelian group, J. London Math. Soc. (2) 1 (1969), 348–350. MR 246860, DOI 10.1112/jlms/s2-1.1.348
Harm Derksen and Gregor Kemper, Computational invariant theory, Invariant Theory and Algebraic Transformation Groups, I, Springer-Verlag, Berlin, 2002. Encyclopaedia of Mathematical Sciences, 130. MR 1918599, DOI 10.1007/978-3-662-04958-7
Jean-Charles Faugére, A new efficient algorithm for computing Gröbner bases $(F_4)$, J. Pure Appl. Algebra 139 (1999), no. 1-3, 61–88. Effective methods in algebraic geometry (Saint-Malo, 1998). MR 1700538, DOI 10.1016/S0022-4049(99)00005-5
Jean-Charles Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero $(F_5)$, Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2002, pp. 75–83. MR 2035234, DOI 10.1145/780506.780516
J. C. Faugère, P. Gianni, D. Lazard, and T. Mora, Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symbolic Comput. 16 (1993), no. 4, 329–344. MR 1263871, DOI 10.1006/jsco.1993.1051
Jean-Charles Faugère, Mohab Safey El Din, and Thibaut Verron, On the complexity of computing Gröbner bases for quasi-homogeneous systems, ISSAC 2013—Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2013, pp. 189–196. MR 3206357, DOI 10.1145/2465506.2465943
Jean-Charles Faugère and Jules Svartz, Gröbner bases of ideals invariant under a commutative group: the non-modular case, ISSAC 2013—Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2013, pp. 347–354. MR 3206377, DOI 10.1145/2465506.2465944
E. Fischer, Die Isomorphie der Invariantenkörper der endlicher Abelschen Gruppen linearer Transformationen. Nachr. Ges. Wiss. Göttingen, Math.-Phys. Kl., 1915:77–80, 1915.
E. Fischer, Zur Theorie der endlichen Abelschen Gruppen, Math. Ann. 77 (1915), no. 1, 81–88 (German). MR 1511847, DOI 10.1007/BF01456820
Peter Fleischmann, Gregor Kemper, and Chris Woodcock, Homomorphisms, localizations and a new algorithm to construct invariant rings of finite groups, J. Algebra 309 (2007), no. 2, 497–517. MR 2303190, DOI 10.1016/j.jalgebra.2005.06.038
K. Gatermann, Symbolic solution of polynomial equation systems with symmetry, in Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC’90, pages 112–119, ACM, New York, 1990.
Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 832183, DOI 10.1017/CBO9780511810817
John A. Howell, Spans in the module $(Z_m)^s$, Linear and Multilinear Algebra 19 (1986), no. 1, 67–77. MR 835631, DOI 10.1080/03081088608817705
Evelyne Hubert, Algebraic and differential invariants, Foundations of computational mathematics, Budapest 2011, London Math. Soc. Lecture Note Ser., vol. 403, Cambridge Univ. Press, Cambridge, 2013, pp. 165–187. MR 3137638
E. Hubert, Rational invariants of a group action, in P. Boito, G. Chèze, C. Pernet, and M. Safey El Din, editors, Journees Nationales de Calcul Formel, volume 3 of Les cours du CIRM, 10pp., CEDRAM - Center for Diffusion of Academic Mathematical Journals, Marseille, France, 2013.
Evelyne Hubert and Irina A. Kogan, Rational invariants of a group action. Construction and rewriting, J. Symbolic Comput. 42 (2007), no. 1-2, 203–217. MR 2284293, DOI 10.1016/j.jsc.2006.03.005
Evelyne Hubert and Irina A. Kogan, Smooth and algebraic invariants of a group action: local and global constructions, Found. Comput. Math. 7 (2007), no. 4, 455–493. MR 2352606, DOI 10.1007/s10208-006-0219-0
Evelyne Hubert and George Labahn, Rational invariants of scalings from Hermite normal forms, ISSAC 2012—Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2012, pp. 219–226. MR 3206307, DOI 10.1145/2442829.2442862
Evelyne Hubert and George Labahn, Scaling invariants and symmetry reduction of dynamical systems, Found. Comput. Math. 13 (2013), no. 4, 479–516. MR 3085676, DOI 10.1007/s10208-013-9165-9
Tobias Kamke and Gregor Kemper, Algorithmic invariant theory of nonreductive groups, Qual. Theory Dyn. Syst. 11 (2012), no. 1, 79–110. MR 2902726, DOI 10.1007/s12346-011-0059-4
Ming-chang Kang, Fixed fields of triangular matrix groups, J. Algebra 302 (2006), no. 2, 845–847. MR 2293785, DOI 10.1016/j.jalgebra.2006.03.037
Gregor Kemper, The computation of invariant fields and a constructive version of a theorem by Rosenlicht, Transform. Groups 12 (2007), no. 4, 657–670. MR 2365439, DOI 10.1007/s00031-007-0056-5
H. W. Lenstra Jr., Rational functions invariant under a finite abelian group, Invent. Math. 25 (1974), 299–325. MR 347788, DOI 10.1007/BF01389732
Takehiko Miyata, Invariants of certain groups. I, Nagoya Math. J. 41 (1971), 69–73. MR 272923, DOI 10.1017/S0027763000014069
Bernard Mourrain and Philippe Trébuchet, Toric border basis, ISSAC 2014—Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2014, pp. 343–350. MR 3239945, DOI 10.1145/2608628.2608652
Jörn Müller-Quade and Thomas Beth, Calculating generators for invariant fields of linear algebraic groups, Applied algebra, algebraic algorithms and error-correcting codes (Honolulu, HI, 1999) Lecture Notes in Comput. Sci., vol. 1719, Springer, Berlin, 1999, pp. 392–403. MR 1846513, DOI 10.1007/3-540-46796-3_{3}7
M. D. Neusel and M. Sezer, Characterizing separating invariants, http://hopf.math.purdue.edu/Neusel-Sezer/separating.pdf, 2010.
V. W. Noonburg, A neural network modeled by an adaptive Lotka-Volterra system, SIAM J. Appl. Math. 49 (1989), no. 6, 1779–1792. MR 1025961, DOI 10.1137/0149109
Franz Pauer and Andreas Unterkircher, Gröbner bases for ideals in Laurent polynomial rings and their application to systems of difference equations, Appl. Algebra Engrg. Comm. Comput. 9 (1999), no. 4, 271–291. MR 1683300, DOI 10.1007/s002000050108
È. B. Vinberg and V. L. Popov, Invariant theory, Algebraic geometry, 4 (Russian), Itogi Nauki i Tekhniki, Akad. Nauk SSSR, Vsesoyuz. Inst. Nauchn. i Tekhn. Inform., Moscow, 1989, pp. 137–314, 315 (Russian). MR 1100485
Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR 874114
A. Storjohann, Algorithms for Matrix Canonical Forms, PhD thesis, Department of Computer Science, Swiss Federal Institute of Technology—ETH, 2000.
A. Storjohann and G. Labahn, Asymptotically fast computation of Hermite normal forms of integer matrices, in Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC’96, pages 259–266, ACM, New York, 1996.
Arne Storjohann and Thom Mulders, Fast algorithms for linear algebra modulo $N$, Algorithms—ESA ’98 (Venice), Lecture Notes in Comput. Sci., vol. 1461, Springer, Berlin, 1998, pp. 139–150. MR 1683348, DOI 10.1007/3-540-68530-8_{1}2
Bernd Sturmfels, Algorithms in invariant theory, Texts and Monographs in Symbolic Computation, Springer-Verlag, Vienna, 1993. MR 1255980, DOI 10.1007/978-3-7091-4368-1
Richard G. Swan, Invariant rational functions and a problem of Steenrod, Invent. Math. 7 (1969), 148–158. MR 244215, DOI 10.1007/BF01389798