Speaker: Sandeep Murthy

Title: TPP Triples of Subsets of Finite Groups

Abstract: Three subsets \(S,T,U\) of a finite group \(G\), each containing the identity, which satisfy a certain disjointness property are said to satisfy the triple product property (TPP), and thereby form a TPP triple of size \(:= |S||T||U|\) and type \(:= \langle |S|,|T|,|U| \rangle\). Basic combinatorial quantities are the TPP capacity of \(G\), which is the largest size of a TPP triple of \(G\), and the subgroup TPP capacity of \(G\), which is the largest size of a TPP triple of subgroups of \(G\). And the basic problem arises of how to estimate these quantities for a given group \(G\). A computational problem is to find an algorithm that will construct a "maximal size" TPP triple of \(G\) in \(O(|G|)\) operations. Currently, there are GAP search programs which find such triples, but they are exponential in \(|G|\).

TPP triples were originally introduced by H. Cohn and C. Umans in 2003 to study the complexity of matrix multiplication, by embedding a given matrix multiplication map \(f(m,p,q)\), over a field \(K\), into the group algebra \(K[G]\) of a "good" finite group \(G\), provided it has a TPP triple of type \(\langle m,p,q \rangle\). If the character degrees are small enough, with respect to the TPP capacity of G, then a nontrivial upper bound can be obtained for the exponent of matrix multiplication over \(K\), which measures the asymptotic complexity of matrix multiplication over \(K\). A good group will be one which has a large TPP capacity relative to its order, but small character degrees relative to its TPP capacity. The problem is to identify such good groups, or even families of good groups, for matrix multiplication.