More Like this

1. Finite Matrix Multiplication Algorithms from Infinite Groups

   https://doi.org/10.4230/LIPIcs.ITCS.2025.18  

   Blasiak, Jonah; Cohn, Henry; Grochow, Joshua A; Pratt, Kevin; Umans, Chris (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   The Cohn-Umans (FOCS '03) group-theoretic framework for matrix multiplication produces fast matrix multiplication algorithms from three subsets of a finite group G satisfying a simple combinatorial condition (the Triple Product Property). The complexity of such an algorithm then depends on the representation theory of G. In this paper we extend the group-theoretic framework to the setting of infinite groups. In particular, this allows us to obtain constructions in Lie groups, with favorable parameters, that are provably impossible in finite groups of Lie type (Blasiak, Cohn, Grochow, Pratt, and Umans, ITCS '23). Previously the Lie group setting was investigated purely as an analogue of the finite group case; a key contribution in this paper is a fully developed framework for obtaining bona fide matrix multiplication algorithms directly from Lie group constructions. As part of this framework, we introduce "separating functions" as a necessary new design component, and show that when the underlying group is G = GL_n, these functions are polynomials with their degree being the key parameter. In particular, we show that a construction with "half-dimensional" subgroups and optimal degree would imply ω = 2. We then build up machinery that reduces the problem of constructing optimal-degree separating polynomials to the problem of constructing a single polynomial (and a corresponding set of group elements) in a ring of invariant polynomials determined by two out of the three subgroups that satisfy the Triple Product Property. This machinery combines border rank with the Lie algebras associated with the Lie subgroups in a critical way. We give several constructions illustrating the main components of the new framework, culminating in a construction in a special unitary group that achieves separating polynomials of optimal degree, meeting one of the key challenges. The subgroups in this construction have dimension approaching half the ambient dimension, but (just barely) too slowly. We argue that features of the classical Lie groups make it unlikely that constructions in these particular groups could produce nontrivial bounds on ω unless they prove ω = 2. One way to get ω = 2 via our new framework would be to lift our existing construction from the special unitary group to GL_n, and improve the dimension of the subgroups from (dim G)/2 - Θ(n) to (dim G)/2 - o(n). 

   more » « less
2. Irreducible characters of even degree and normal Sylow 2-subgroups

   https://doi.org/10.1017/S0305004116000669  

   HUNG, NGUYEN NGOC; TIEP, PHAM HUU (March 2017, Mathematical Proceedings of the Cambridge Philosophical Society)

   Abstract The classical Itô-Michler theorem on character degrees of finite groups asserts that if the degree of every complex irreducible character of a finite group G is coprime to a given prime p , then G has a normal Sylow p -subgroup. We propose a new direction to generalize this theorem by introducing an invariant concerning character degrees. We show that if the average degree of linear and even-degree irreducible characters of G is less than 4/3 then G has a normal Sylow 2-subgroup, as well as corresponding analogues for real-valued characters and strongly real characters. These results improve on several earlier results concerning the Itô-Michler theorem. 

   more » « less
3. The equivariant degree and an enriched count of rational cubics

   Bethea, Candace; Wickelgren, Kirsten (February 2025, arXiv pre-print repository)

   NA (Ed.)

   We define the equivariant degree and local degree of a proper G-equivariant map between smooth G-manifolds when G is a compact Lie group and prove a local to global result. We show the local degree can be used to compute the equivariant Euler characteristic of a smooth, compact G-manifold and the Euler number of a relatively oriented G-equivariant vector bundle when G is finite. As an application, we give an equivariantly enriched count of rational plane cubics through a G-invariant set of 8 general points in ℂℙ2, valued in the representation ring and Burnside ring of a finite group. When ℤ/2 acts by pointwise complex conjugation this recovers a signed count of real rational cubics. 

   more » « less
4. An enriched count of nodal orbits in an invariant pencil of conics

   Bethea, Candace (October 2023, arXiv pre-print repository)

   This work gives an equivariantly enriched count of nodal orbits in a general pencil of plane conics that is invariant under a linear action of a finite group on CP2. This can be thought of as spearheading equivariant enumerative enrichments valued in the Burnside Ring, both inspired by and a departure from R(G)-valued enrichments such as Roberts’ equivariant Milnor number and Damon’s equivariant signature formula. Given a G-invariant general pencil of conics, the weighted sum of nodal orbits in the pencil is a formula in terms of the base locus considered as a G-set. We show this is true for all finite groups except Z/2 × Z/2 and D8 and give counterexamples for the two exceptional groups. 

   more » « less
5. A General Framework for Robust G-Invariance in G-Equivariant Networks

   Sanborn, Sophia; Miolane, Nina (December 2023, NeurIPS 2023)

   We introduce a general method for achieving robust group-invariance in group-equivariant convolutional neural networks (G-CNNs), which we call the G-triple-correlation (G-TC) layer. The approach leverages the theory of the triple-correlation on groups, which is the unique, lowest-degree polynomial invariant map that is also complete. Many commonly used invariant maps--such as the max--are incomplete: they remove both group and signal structure. A complete invariant, by contrast, removes only the variation due to the actions of the group, while preserving all information about the structure of the signal. The completeness of the triple correlation endows the G-TC layer with strong robustness, which can be observed in its resistance to invariance-based adversarial attacks. In addition, we observe that it yields measurable improvements in classification accuracy over standard Max G-Pooling in G-CNN architectures. We provide a general and efficient implementation of the method for any discretized group, which requires only a table defining the group's product structure. We demonstrate the benefits of this method for G-CNNs defined on both commutative and non-commutative groups--SO(2), O(2), SO(3), and O(3) (discretized as the cyclic C8, dihedral D16, chiral octahedral O and full octahedral Oh groups)--acting on ℝ2 and ℝ3 on both G-MNIST and G-ModelNet10 datasets. 

   more » « less