Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

Computation of invariants of finite abelian groups


Authors: Evelyne Hubert and George Labahn
Journal: Math. Comp. 85 (2016), 3029-3050
MSC (2010): Primary 13A50, 15A72; Secondary 12Y05, 13P25, 13P15, 14L30
DOI: https://doi.org/10.1090/mcom/3076
Published electronically: January 14, 2016
MathSciNet review: 3522980
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1145/2442829.2442837
  • [2] 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 (2003a:90032), https://doi.org/10.1287/moor.26.2.304.10555
  • [3] 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 (2008f:13007), https://doi.org/10.1093/qmath/ham011
  • [4] A. Charnow, On the fixed field of a linear abelian group, J. London Math. Soc. (2) 1 (1969), 348-350. MR 0246860 (40 #129)
  • [5] Harm Derksen and Gregor Kemper, Computational Invariant Theory, Invariant Theory and Algebraic Transformation Groups, I, Encyclopaedia of Mathematical Sciences, 130, Springer-Verlag, Berlin, 2002. MR 1918599 (2003g:13004)
  • [6] Jean-Charles Faugére, A new efficient algorithm for computing Gröbner bases $ (F_4)$, Effective methods in algebraic geometry (Saint-Malo, 1998), J. Pure Appl. Algebra 139 (1999), no. 1-3, 61-88. MR 1700538 (2000c:13038), https://doi.org/10.1016/S0022-4049(99)00005-5
  • [7] 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 (electronic). MR 2035234 (2005c:13033), https://doi.org/10.1145/780506.780516
  • [8] 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 (94k:68095), https://doi.org/10.1006/jsco.1993.1051
  • [9] 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, https://doi.org/10.1145/2465506.2465943
  • [10] 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, https://doi.org/10.1145/2465506.2465944
  • [11] 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.
  • [12] E. Fischer, Zur Theorie der endlichen Abelschen Gruppen, Math. Ann. 77 (1915), no. 1, 81-88 (German). MR 1511847, https://doi.org/10.1007/BF01456820
  • [13] 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 (2008e:13003), https://doi.org/10.1016/j.jalgebra.2005.06.038
  • [14] 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.
  • [15] Roger A. Horn and Charles R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985. MR 832183 (87e:15001)
  • [16] John A. Howell, Spans in the module $ (Z_m)^s$, Linear and Multilinear Algebra 19 (1986), no. 1, 67-77. MR 835631 (88h:15031), https://doi.org/10.1080/03081088608817705
  • [17] 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
  • [18] 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.
  • [19] 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 (2007i:13009), https://doi.org/10.1016/j.jsc.2006.03.005
  • [20] 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 (2008m:22031), https://doi.org/10.1007/s10208-006-0219-0
  • [21] 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, https://doi.org/10.1145/2442829.2442862
  • [22] Evelyne Hubert and George Labahn, Scaling invariants and symmetry reduction of dynamical systems, Found. Comput. Math. 13 (2013), no. 4, 479-516. MR 3085676, https://doi.org/10.1007/s10208-013-9165-9
  • [23] Tobias Kamke and Gregor Kemper, Algorithmic invariant theory of nonreductive groups, Qual. Theory Dyn. Syst. 11 (2012), no. 1, 79-110. MR 2902726, https://doi.org/10.1007/s12346-011-0059-4
  • [24] Ming-chang Kang, Fixed fields of triangular matrix groups, J. Algebra 302 (2006), no. 2, 845-847. MR 2293785 (2007m:13006), https://doi.org/10.1016/j.jalgebra.2006.03.037
  • [25] 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 (2008m:13011), https://doi.org/10.1007/s00031-007-0056-5
  • [26] H. W. Lenstra Jr., Rational functions invariant under a finite abelian group, Invent. Math. 25 (1974), 299-325. MR 0347788 (50 #289)
  • [27] Takehiko Miyata, Invariants of certain groups. I, Nagoya Math. J. 41 (1971), 69-73. MR 0272923 (42 #7804)
  • [28] 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, https://doi.org/10.1145/2608628.2608652
  • [29] 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 (2002f:13011), https://doi.org/10.1007/3-540-46796-3_37
  • [30] M. D. Neusel and M. Sezer,
    Characterizing separating invariants,
    http://hopf.math.purdue.edu/Neusel-Sezer/separating.pdf, 2010.
  • [31] 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 (91c:92007), https://doi.org/10.1137/0149109
  • [32] 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 (2000b:13039), https://doi.org/10.1007/s002000050108
  • [33] È. 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 (92d:14010)
  • [34] Alexander Schrijver, Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. MR 874114 (88m:90090)
  • [35] A. Storjohann,
    Algorithms for Matrix Canonical Forms,
    PhD thesis, Department of Computer Science, Swiss Federal Institute of Technology--ETH, 2000.
  • [36] 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.
  • [37] 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 (2000a:65056), https://doi.org/10.1007/3-540-68530-8_12
  • [38] Bernd Sturmfels, Algorithms in Invariant Theory, Texts and Monographs in Symbolic Computation, Springer-Verlag, Vienna, 1993. MR 1255980 (94m:13004)
  • [39] Richard G. Swan, Invariant rational functions and a problem of Steenrod, Invent. Math. 7 (1969), 148-158. MR 0244215 (39 #5532)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 13A50, 15A72, 12Y05, 13P25, 13P15, 14L30

Retrieve articles in all journals with MSC (2010): 13A50, 15A72, 12Y05, 13P25, 13P15, 14L30


Additional Information

Evelyne Hubert
Affiliation: INRIA Méditerranée, 06902 Sophia Antipolis, France
Email: evelyne.hubert@inria.fr

George Labahn
Affiliation: Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada N2L 3G1
Email: glabahn@uwaterloo.ca

DOI: https://doi.org/10.1090/mcom/3076
Keywords: Finite groups, rational invariants, matrix normal form, polynomial system reduction, constructive Noether's problem
Received by editor(s): January 24, 2014
Received by editor(s) in revised form: September 4, 2014, and April 27, 2015
Published electronically: January 14, 2016
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society