Algorithms for fundamental invariants and equivariants of finite groups

Hubert, Evelyne; Rodriguez Bazan, Erick

doi:10.1090/mcom/3749

Algorithms for fundamental invariants and equivariants of finite groups
HTML articles powered by AMS MathViewer

by Evelyne Hubert and Erick Rodriguez Bazan HTML | PDF

Math. Comp. 91 (2022), 2459-2488 Request permission

Abstract:

For a finite group, we present three algorithms to compute a generating set of invariants simultaneously to generating sets of basic equivariants, i.e., equivariants for the irreducible representations of the group. The main novelty resides in the exploitation of the orthogonal complement of the ideal generated by invariants. Its symmetry adapted basis delivers the fundamental equivariants.

Fundamental equivariants allow to assemble symmetry adapted bases of polynomial spaces of higher degrees, and these are essential ingredients in exploiting and preserving symmetry in computations. They appear within algebraic computation and beyond, in physics, chemistry and engineering.

Our first construction applies solely to reflection groups and consists in applying symmetry preserving interpolation, as developed by the same authors, along an orbit in general position. The fundamental invariants can be read off the H-basis of the ideal of the orbit while the fundamental equivariants are obtained from a symmetry adapted basis of an invariant direct complement to this ideal in the polynomial ring.

The second algorithm takes as input primary invariants and the output provides not only the secondary invariants but also free bases for the modules of basic equivariants. These are constructed as the components of a symmetry adapted basis of the orthogonal complement, in the polynomial ring, to the ideal generated by primary invariants.

The third and main algorithm proceeds degree by degree, determining the fundamental invariants as forming a H-basis of the Hilbert ideal, i.e., the polynomial ideal generated by the invariants of positive degree. The fundamental equivariants are simultaneously computed degree by degree as the components of a symmetry adapted basis of the orthogonal complement of the Hilbert ideal.

References

Susumu Ariki, Tomohide Terasoma, and Hiro-Fumi Yamada, Higher Specht polynomials, Hiroshima Math. J. 27 (1997), no. 1, 177–188. MR 1437932
L. C. Grove and C. T. Benson, Finite reflection groups, 2nd ed., Graduate Texts in Mathematics, vol. 99, Springer-Verlag, New York, 1985. MR 777684, DOI 10.1007/978-1-4757-1869-0
François Bergeron, Algebraic combinatorics and coinvariant spaces, CMS Treatises in Mathematics, Canadian Mathematical Society, Ottawa, ON; A K Peters, Ltd., Wellesley, MA, 2009. MR 2538310, DOI 10.1201/b10583
Patrick Cassam-Chenaï, Guillaume Dhont, and Frédéric Patras, A fast algorithm for the construction of integrity bases associated to symmetry-adapted polynomial representations: application to tetrahedral $\textrm {XY}_4$ molecules, J. Math. Chem. 53 (2015), no. 1, 58–85. MR 3297947, DOI 10.1007/s10910-014-0410-5
Patrick Cassam-Chenaï and Frédéric Patras, Symmetry-adapted polynomial basis for global potential energy surfaces-applications to $\rm XY_4$ molecules, J. Math. Chem. 44 (2008), no. 4, 938–966. MR 2452487, DOI 10.1007/s10910-008-9354-y
Claude Chevalley, Invariants of finite groups generated by reflections, Amer. J. Math. 77 (1955), 778–782. MR 72877, DOI 10.2307/2372597
Pascal Chossat and Reiner Lauterbach, Methods in equivariant bifurcations and dynamical systems, Advanced Series in Nonlinear Dynamics, vol. 15, World Scientific Publishing Co., Inc., River Edge, NJ, 2000. MR 1831950, DOI 10.1142/4062
M. Collowald, Multivariate moment problems : applications of the reconstruction of linear forms on the polynomial ring, Theses, Université Nice Sophia Antipolis, December 2015.
M. Collowald and E. Hubert, A moment matrix approach to computing symmetric cubatures, https://hal.inria.fr/hal-01188290, also part of \cite{Collowald15phd}, 2015.
David A. Cox, John Little, and Donal O’Shea, Using algebraic geometry, 2nd ed., Graduate Texts in Mathematics, vol. 185, Springer, New York, 2005. MR 2122859
David A. Cox, John Little, and Donal O’Shea, Ideals, varieties, and algorithms, 4th ed., Undergraduate Texts in Mathematics, Springer, Cham, 2015. An introduction to computational algebraic geometry and commutative algebra. MR 3330490, DOI 10.1007/978-3-319-16721-3
Carl de Boor and Amos Ron, The least solution for the polynomial interpolation problem, Math. Z. 210 (1992), no. 3, 347–378. MR 1171179, DOI 10.1007/BF02571803
Harm Derksen, Computation of invariants for reductive groups, Adv. Math. 141 (1999), no. 2, 366–384. MR 1671758, DOI 10.1006/aima.1998.1787
Harm Derksen and Gregor Kemper, Computational invariant theory, Second enlarged edition, Encyclopaedia of Mathematical Sciences, vol. 130, Springer, Heidelberg, 2015. With two appendices by Vladimir L. Popov, and an addendum by Norbert A’Campo and Popov; Invariant Theory and Algebraic Transformation Groups, VIII. MR 3445218, DOI 10.1007/978-3-662-48422-7
Guillaume Dhont, Frédéric Patras, and Boris I. Zhilinskií, The action of the special orthogonal group on planar vectors: integrity bases via a generalization of the symbolic interpretation of Molien functions, J. Phys. A 48 (2015), no. 3, 035201, 19. MR 3299621, DOI 10.1088/1751-8113/48/3/035201
A. Fässler and E. Stiefel, Group theoretical methods and their applications, Birkhäuser Boston, Inc., Boston, MA, 1992. Translated from the German by Baoswan Dzung Wong. MR 1158662, DOI 10.1007/978-1-4612-0395-7
Jean-Charles Faugère and Sajjad Rahmany, Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases, ISSAC 2009—Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2009, pp. 151–158. MR 2742703, DOI 10.1145/1576702.1576725
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
Kenneth Fox and Burton J. Krohn, Computation of cubic harmonics, J. Comput. Phys. 25 (1977), no. 4, 386–408. MR 474720, DOI 10.1016/0021-9991(77)90005-5
K. Gatemann, Symbolic solution polynomial equation systems with symmetry, Proceedings of the International Symposium on Symbolic and Algebraic Computation (New York, NY, USA), ISSAC ’90, Association for Computing Machinery, 1990, pp. 112–119.
Karin Gatermann, Computer algebra methods for equivariant dynamical systems, Lecture Notes in Mathematics, vol. 1728, Springer-Verlag, Berlin, 2000. MR 1755001, DOI 10.1007/BFb0104059
Karin Gatermann and Frédéric Guyard, Gröbner bases, invariant theory and equivariant dynamics, J. Symbolic Comput. 28 (1999), no. 1-2, 275–302. Polynomial elimination—algorithms and applications. MR 1709907, DOI 10.1006/jsco.1998.0277
Karin Gatermann and Pablo A. Parrilo, Symmetry groups, semidefinite programs, and sums of squares, J. Pure Appl. Algebra 192 (2004), no. 1-3, 95–128. MR 2067190, DOI 10.1016/j.jpaa.2003.12.011
Gene H. Golub and Charles F. Van Loan, Matrix computations, Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1983. MR 733103
Martin Golubitsky, Ian Stewart, and David G. Schaeffer, Singularities and groups in bifurcation theory. Vol. II, Applied Mathematical Sciences, vol. 69, Springer-Verlag, New York, 1988. MR 950168, DOI 10.1007/978-1-4612-4574-2
Paul Görlach, Evelyne Hubert, and Théo Papadopoulo, Rational invariants of even ternary forms under the orthogonal group, Found. Comput. Math. 19 (2019), no. 6, 1315–1361. MR 4029843, DOI 10.1007/s10208-018-9404-1
John Hilton Grace and Alfred Young, The algebra of invariants, Cambridge Library Collection, Cambridge University Press, Cambridge, 2010. Reprint of the 1903 original. MR 2850282, DOI 10.1017/CBO9780511708534
David Hilbert, Ueber die Theorie der algebraischen Formen, Math. Ann. 36 (1890), no. 4, 473–534 (German). MR 1510634, DOI 10.1007/BF01208503
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
Evelyne Hubert and George Labahn, Computation of invariants of finite abelian groups, Math. Comp. 85 (2016), no. 302, 3029–3050. MR 3522980, DOI 10.1090/mcom/3076
Richard Kane, Reflection groups and invariant theory, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, vol. 5, Springer-Verlag, New York, 2001. MR 1838580, DOI 10.1007/978-1-4757-3542-0
Gregor Kemper, An algorithm to calculate optimal homogeneous systems of parameters, J. Symbolic Comput. 27 (1999), no. 2, 171–184. MR 1672128, DOI 10.1006/jsco.1998.0247
Simon A. King, Minimal generating sets of non-modular invariant rings of finite groups, J. Symbolic Comput. 48 (2013), 101–109. MR 2980468, DOI 10.1016/j.jsc.2012.05.002
Reynald Lercier, Christophe Ritzenthaler, and Jeroen Sijsling, Explicit Galois obstruction and descent for hyperelliptic curves with tamely cyclic reduced automorphism group, Math. Comp. 85 (2016), no. 300, 2011–2045. MR 3471117, DOI 10.1090/mcom3032
F. S. Macaulay, The algebraic theory of modular systems, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1994. Revised reprint of the 1916 original; With an introduction by Paul Roberts. MR 1281612
Jean-François Mestre, Construction de courbes de genre $2$ à partir de leurs modules, Effective methods in algebraic geometry (Castiglioncello, 1990) Progr. Math., vol. 94, Birkhäuser Boston, Boston, MA, 1991, pp. 313–334 (French). MR 1106431
L. Michel and B. I. Zhilinskií, Symmetry, invariants, topology. Basic tools, Phys. Rep. 341 (2001), no. 1-6, 11–84. Symmetry, invariants, topology. MR 1845460, DOI 10.1016/S0370-1573(00)00088-0
H. Michael Möller and Thomas Sauer, $H$-bases for polynomial interpolation and system solving, Adv. Comput. Math. 12 (2000), no. 4, 335–362. Multivariate polynomial interpolation. MR 1768955, DOI 10.1023/A:1018937723499
Jürg Muggli, Cubic harmonics as linear combinations of spherical harmonics, Z. Angew. Math. Phys. 23 (1972), 311–317 (English, with German summary). MR 339457, DOI 10.1007/BF01593094
J. Mundy, A. Zisserman, and D. Forsyth (eds.), Application of Invariance in Computer Vision, Lecture Notes in Computer Science, Springer-Verlag, 1992.
Marc Olive, About Gordan’s algorithm for binary forms, Found. Comput. Math. 17 (2017), no. 6, 1407–1466. MR 3735859, DOI 10.1007/s10208-016-9324-x
V. L. Popov and Eh. B. Vinberg, Invariant theory, (English. Russian original) Zbl 0789.14008 Algebraic geometry. IV: Linear algebraic groups, invariant theory, Encycl. Math. Sci. 55, 123–278 (1994); translation from Itogi Nauki Tekh., Ser. Sovrem. Probl. Mat., Fundam. Napravleniya 55, 137–309 (1989). https://link.springer.com/chapter/10.1007/978-3-662-03073-8_2.
Cordian Riener, Thorsten Theobald, Lina Jansson Andrén, and Jean B. Lasserre, Exploiting symmetries in SDP-relaxations for polynomial optimization, Math. Oper. Res. 38 (2013), no. 1, 122–141. MR 3029481, DOI 10.1287/moor.1120.0558
Erick Rodriguez Bazan and Evelyne Hubert, Multivariate interpolation: preserving and exploiting symmetry, J. Symbolic Comput. 107 (2021), 1–22. MR 4215093, DOI 10.1016/j.jsc.2021.01.004
E. Rodriguez Bazan and E. Hubert, Symmetry in multivariate ideal interpolation, Journal of Symbolic Computation (2022).
Jean-Pierre Serre, Linear representations of finite groups, Graduate Texts in Mathematics, Vol. 42, Springer-Verlag, New York-Heidelberg, 1977. Translated from the second French edition by Leonard L. Scott. MR 0450380, DOI 10.1007/978-1-4684-9458-7
Wilhelm Specht, Die irreduziblen Darstellungen der symmetrischen Gruppe, Math. Z. 39 (1935), no. 1, 696–711 (German). MR 1545531, DOI 10.1007/BF01201387
Richard P. Stanley, Invariants of finite groups and their applications to combinatorics, Bull. Amer. Math. Soc. (N.S.) 1 (1979), no. 3, 475–511. MR 526968, DOI 10.1090/S0273-0979-1979-14597-X
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
Tomohide Terasoma and Hirofumi Yamada, Higher Specht polynomials for the symmetric group, Proc. Japan Acad. Ser. A Math. Sci. 69 (1993), no. 2, 41–44. MR 1210951, DOI 10.1007/978-3-662-03073-8_{2}