Algorithms for fundamental invariants and equivariants of finite groups. (English) Zbl 1542.13005
Given a linear action of a finite group GG on a vector space, one is often interested in computing bases for which the group action can be expressed in a favorable way. In the case of polynomials, such symmetry-adapted bases are related to basic equivariants, which realize the equivariants as finite modules over the invariant ring. The present article introduces three algorithms to compute a generating set of invariants and basic equivariants for a finite group by exploiting the orthogonal complement of the ideal generated by invariants.
The first algorithm, applicable to reflection groups, is based on the observation that it is possible to obtain the fundamental invariants and equivariants via an application of ideal interpolation with symmetry.
The second algorithm takes as input the primary invariants and generates secondary invariants and free bases for modules of basic equivariants, using a symmetry-adapted basis of the orthogonal complement in the polynomial ring.
The third, and main, algorithm computes simultaneously fundamental invariants and equivariants degree by degree, forming an H-basis of the Hilbert ideal and utilizing a symmetry-adapted basis of the orthogonal complement.
These algorithms provide a valuable key to utilizing symmetry in various computational applications. Moreover, the authors implement these algorithms in the Maple library SyCo (http://www-sop.inria.fr/members/Evelyne.Hubert/SyC), which is also used to complement the paper with illustrative examples.
The first algorithm, applicable to reflection groups, is based on the observation that it is possible to obtain the fundamental invariants and equivariants via an application of ideal interpolation with symmetry.
The second algorithm takes as input the primary invariants and generates secondary invariants and free bases for modules of basic equivariants, using a symmetry-adapted basis of the orthogonal complement in the polynomial ring.
The third, and main, algorithm computes simultaneously fundamental invariants and equivariants degree by degree, forming an H-basis of the Hilbert ideal and utilizing a symmetry-adapted basis of the orthogonal complement.
These algorithms provide a valuable key to utilizing symmetry in various computational applications. Moreover, the authors implement these algorithms in the Maple library SyCo (http://www-sop.inria.fr/members/Evelyne.Hubert/SyC), which is also used to complement the paper with illustrative examples.
Reviewer: Cordian Riener (Tromsø)
MSC:
| 13A50 | Actions of groups on commutative rings; invariant theory |
| 68W30 | Symbolic computation and algebraic computation |
| 13P10 | Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) |
Keywords:
finite groups; representation theory; polynomial invariants; equivariants; covariants; symmetry adapted bases; H-basis; interpolation; computational invariant theoryReferences:
| [1] | Ariki, Susumu, Higher Specht polynomials, Hiroshima Math. J., 177-188 (1997) · Zbl 0886.20009 |
| [2] | Grove, L. C., Finite Reflection Groups, Graduate Texts in Mathematics, x+133 pp. (1985), Springer-Verlag, New York · Zbl 0579.20045 · doi:10.1007/978-1-4757-1869-0 |
| [3] | Bergeron, Fran\c{c}ois, Algebraic Combinatorics and Coinvariant Spaces, CMS Treatises in Mathematics, viii+221 pp. (2009), Canadian Mathematical Society, Ottawa, ON; A K Peters, Ltd., Wellesley, MA · Zbl 1185.05002 · doi:10.1201/b10583 |
| [4] | Cassam-Chena\"{\i }, Patrick, A fast algorithm for the construction of integrity bases associated to symmetry-adapted polynomial representations: application to tetrahedral \(\text{XY}_4\) molecules, J. Math. Chem., 58-85 (2015) · Zbl 1307.92365 · doi:10.1007/s10910-014-0410-5 |
| [5] | Cassam-Chena\"{\i }, Patrick, Symmetry-adapted polynomial basis for global potential energy surfaces-applications to \(\text{XY}_4\) molecules, J. Math. Chem., 938-966 (2008) · Zbl 1243.81237 · doi:10.1007/s10910-008-9354-y |
| [6] | Chevalley, Claude, Invariants of finite groups generated by reflections, Amer. J. Math., 778-782 (1955) · Zbl 0065.26103 · doi:10.2307/2372597 |
| [7] | Chossat, Pascal, Methods in Equivariant Bifurcations and Dynamical Systems, Advanced Series in Nonlinear Dynamics, xvi+404 pp. (2000), World Scientific Publishing Co., Inc., River Edge, NJ · Zbl 0968.37001 · doi:10.1142/4062 |
| [8] | M. Collowald, Multivariate moment problems : applications of the reconstruction of linear forms on the polynomial ring, Theses, Universit\'e Nice Sophia Antipolis, December 2015. |
| [9] | M. Collowald and E. Hubert, A moment matrix approach to computing symmetric cubatures, https://hal.inria.fr/hal-01188290, also part of Collowald15phd, 2015. · Zbl 1409.65009 |
| [10] | Cox, David A., Using Algebraic Geometry, Graduate Texts in Mathematics, xii+572 pp. (2005), Springer, New York · Zbl 1079.13017 |
| [11] | Cox, David A., Ideals, Varieties, and Algorithms, Undergraduate Texts in Mathematics, xvi+646 pp. (2015), Springer, Cham · Zbl 1335.13001 · doi:10.1007/978-3-319-16721-3 |
| [12] | de Boor, Carl, The least solution for the polynomial interpolation problem, Math. Z., 347-378 (1992) · Zbl 0735.41001 · doi:10.1007/BF02571803 |
| [13] | Derksen, Harm, Computation of invariants for reductive groups, Adv. Math., 366-384 (1999) · Zbl 0927.13007 · doi:10.1006/aima.1998.1787 |
| [14] | Derksen, Harm, Computational Invariant Theory, Encyclopaedia of Mathematical Sciences, xxii+366 pp. (2015), Springer, Heidelberg · Zbl 1332.13001 · doi:10.1007/978-3-662-48422-7 |
| [15] | Dhont, Guillaume, 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, 035201, 19 pp. (2015) · Zbl 1315.13018 · doi:10.1088/1751-8113/48/3/035201 |
| [16] | F\"{a}ssler, A., Group Theoretical Methods and Their Applications, xii+296 pp. (1992), Birkh\"{a}user Boston, Inc., Boston, MA · Zbl 0769.20002 · doi:10.1007/978-1-4612-0395-7 |
| [17] | Faug\`ere, Jean-Charles, ISSAC 2009-Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation. Solving systems of polynomial equations with symmetries using SAGBI-Gr\"{o}bner bases, 151-158 (2009), ACM, New York · Zbl 1237.13052 · doi:10.1145/1576702.1576725 |
| [18] | Faug\`ere, Jean-Charles, ISSAC 2013-Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation. Gr\"{o}bner bases of ideals invariant under a commutative group: the non-modular case, 347-354 (2013), ACM, New York · Zbl 1360.68931 · doi:10.1145/2465506.2465944 |
| [19] | Fox, Kenneth, Computation of cubic harmonics, J. Comput. Phys., 386-408 (1977) · Zbl 0368.65010 · doi:10.1016/0021-9991(77)90005-5 |
| [20] | 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. |
| [21] | Gatermann, Karin, Computer Algebra Methods for Equivariant Dynamical Systems, Lecture Notes in Mathematics, xvi+153 pp. (2000), Springer-Verlag, Berlin · Zbl 0944.65131 · doi:10.1007/BFb0104059 |
| [22] | Gatermann, Karin, Gr\"{o}bner bases, invariant theory and equivariant dynamics, J. Symbolic Comput., 275-302 (1999) · Zbl 0939.68171 · doi:10.1006/jsco.1998.0277 |
| [23] | Gatermann, Karin, Symmetry groups, semidefinite programs, and sums of squares, J. Pure Appl. Algebra, 95-128 (2004) · Zbl 1108.13021 · doi:10.1016/j.jpaa.2003.12.011 |
| [24] | Golub, Gene H., Matrix Computations, Johns Hopkins Series in the Mathematical Sciences, xvi+476 pp. (1983), Johns Hopkins University Press, Baltimore, MD · Zbl 0559.65011 |
| [25] | Golubitsky, Martin, Singularities and Groups in Bifurcation Theory. Vol. II, Applied Mathematical Sciences, xvi+533 pp. (1988), Springer-Verlag, New York · Zbl 0691.58003 · doi:10.1007/978-1-4612-4574-2 |
| [26] | G\"{o}rlach, Paul, Rational invariants of even ternary forms under the orthogonal group, Found. Comput. Math., 1315-1361 (2019) · Zbl 1439.13019 · doi:10.1007/s10208-018-9404-1 |
| [27] | Grace, John Hilton, The Algebra of Invariants, Cambridge Library Collection, ii+viii+384 pp. (2010), Cambridge University Press, Cambridge · Zbl 1206.13003 · doi:10.1017/CBO9780511708534 |
| [28] | Hilbert, David, Ueber die Theorie der algebraischen Formen, Math. Ann., 473-534 (1890) · JFM 22.0133.01 · doi:10.1007/BF01208503 |
| [29] | Hubert, Evelyne, ISSAC 2012-Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation. Rational invariants of scalings from Hermite normal forms, 219-226 (2012), ACM, New York · Zbl 1323.68605 · doi:10.1145/2442829.2442862 |
| [30] | Hubert, Evelyne, Scaling invariants and symmetry reduction of dynamical systems, Found. Comput. Math., 479-516 (2013) · Zbl 1284.34045 · doi:10.1007/s10208-013-9165-9 |
| [31] | Hubert, Evelyne, Computation of invariants of finite abelian groups, Math. Comp., 3029-3050 (2016) · Zbl 1361.13005 · doi:10.1090/mcom/3076 |
| [32] | Kane, Richard, Reflection Groups and Invariant Theory, CMS Books in Mathematics/Ouvrages de Math\'{e}matiques de la SMC, x+379 pp. (2001), Springer-Verlag, New York · Zbl 0986.20038 · doi:10.1007/978-1-4757-3542-0 |
| [33] | Kemper, Gregor, An algorithm to calculate optimal homogeneous systems of parameters, J. Symbolic Comput., 171-184 (1999) · Zbl 0933.68163 · doi:10.1006/jsco.1998.0247 |
| [34] | King, Simon A., Minimal generating sets of non-modular invariant rings of finite groups, J. Symbolic Comput., 101-109 (2013) · Zbl 1314.13013 · doi:10.1016/j.jsc.2012.05.002 |
| [35] | Lercier, Reynald, Explicit Galois obstruction and descent for hyperelliptic curves with tamely cyclic reduced automorphism group, Math. Comp., 2011-2045 (2016) · Zbl 1343.14047 · doi:10.1090/mcom3032 |
| [36] | Macaulay, F. S., The Algebraic Theory of Modular Systems, Cambridge Mathematical Library, xxxii+112 pp. (1994), Cambridge University Press, Cambridge · Zbl 0802.13001 |
| [37] | Mestre, Jean-Fran\c{c}ois, Effective methods in algebraic geometry. Construction de Courbes de Genre \(2\) \`a partir de leurs Modules, Progr. Math., 313-334 (1990), Birkh\"{a}user Boston, Boston, MA · Zbl 0752.14027 |
| [38] | Michel, L., Symmetry, invariants, topology. Basic tools, Phys. Rep., 11-84 (2001) · Zbl 0971.22500 · doi:10.1016/S0370-1573(00)00088-0 |
| [39] | M\"{o}ller, H. Michael, \(H\)-bases for polynomial interpolation and system solving, Adv. Comput. Math., 335-362 (2000) · Zbl 0943.65059 · doi:10.1023/A:1018937723499 |
| [40] | Muggli, J\"{u}rg, Cubic harmonics as linear combinations of spherical harmonics, Z. Angew. Math. Phys., 311-317 (1972) · Zbl 0239.65019 · doi:10.1007/BF01593094 |
| [41] | J. Mundy, A. Zisserman, and D. Forsyth (eds.), Application of Invariance in Computer Vision, Lecture Notes in Computer Science, Springer-Verlag, 1992. |
| [42] | Olive, Marc, About Gordan’s algorithm for binary forms, Found. Comput. Math., 1407-1466 (2017) · Zbl 1408.13017 · doi:10.1007/s10208-016-9324-x |
| [43] | 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. · Zbl 0789.14008 |
| [44] | Riener, Cordian, Exploiting symmetries in SDP-relaxations for polynomial optimization, Math. Oper. Res., 122-141 (2013) · Zbl 1291.90167 · doi:10.1287/moor.1120.0558 |
| [45] | Rodriguez Bazan, Erick, Multivariate interpolation: preserving and exploiting symmetry, J. Symbolic Comput., 1-22 (2021) · Zbl 1479.41002 · doi:10.1016/j.jsc.2021.01.004 |
| [46] | E. Rodriguez Bazan and E. Hubert, Symmetry in multivariate ideal interpolation, Journal of Symbolic Computation (2022). · Zbl 07300098 |
| [47] | Serre, Jean-Pierre, Linear Representations of Finite Groups, Graduate Texts in Mathematics, Vol. 42, x+170 pp. (1977), Springer-Verlag, New York-Heidelberg · Zbl 0355.20006 |
| [48] | Specht, Wilhelm, Die irreduziblen Darstellungen der symmetrischen Gruppe, Math. Z., 696-711 (1935) · Zbl 0011.10301 · doi:10.1007/BF01201387 |
| [49] | Stanley, Richard P., Invariants of finite groups and their applications to combinatorics, Bull. Amer. Math. Soc. (N.S.), 475-511 (1979) · Zbl 0497.20002 · doi:10.1090/S0273-0979-1979-14597-X |
| [50] | Sturmfels, Bernd, Algorithms in Invariant Theory, Texts and Monographs in Symbolic Computation, vi+197 pp. (1993), Springer-Verlag, Vienna · Zbl 0802.13002 · doi:10.1007/978-3-7091-4368-1 |
| [51] | Terasoma, Tomohide, Higher Specht polynomials for the symmetric group, Proc. Japan Acad. Ser. A Math. Sci., 41-44 (1993) · Zbl 0811.20011 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
