Search and test algorithms for triple product property triples. (Q2905579)

The classical algorithm for multiplying two \(n\times n\) matrices requires \(O(n^3)\) field element operations. In 1969 \textit{V. Strassen} [Numer. Math. 13, 354-356 (1969; Zbl 0185.40101)] gave the surprising result that there is a \(O(n^{2.81})\) algorithm for this problem. Since then there have been numerous attempts to find the infimum \(\omega\) of the exponents \(r\) such that two \(n\times n\) matrices can be multiplied using \(O(n^r)\) operations. It has been conjectured that \(\omega=2\) but the current best bound seems to be \(\omega<2.3727\) (see [\textit{D. Coopersmith} and \textit{S. Winograd}, J. Symb. Comput. 9, No. 3, 251-280 (1990; Zbl 0702.65046)] and [\textit{V. V. Williams}, ``Breaking the Coopersmith-Vinograd barrier'', preprint (2011) \texttt{www.cs.berkeley.edu/symbol{126}virgi/matrixmult.pdf}]). These methods (computations in tensor algebras) become increasingly complicated to validate, and in 2005 an alternative approach using group theory was proposed [\textit{H. Cohn, R. Kleinberg, B. Szegedy} and \textit{C. Umans}, ``Group-theoretic algorithms for matrix multiplication'', in: Proc. 46th Annual Symp. Found. Comput. Sci., IEEE Comput. Soc. 379-388 (2005)]. The latter method has not been successful in breaking earlier bounds, but it does offer what appears to be a simpler framework for investigating the question.NEWLINENEWLINE Briefly the idea is the following. Let \(G\) be a finite group and for each subset \(X\) define \(Q(X):=\{xy^{-1}\mid x,y\in X\}\). Then a triple \((S,T,U)\) of nonempty subsets of \(G\) is said to have the triple product property (TPP) if for \(s\in Q(S)\), \(t\in Q(T)\) and \(u\in Q(U)\): \(stu=1\implies s=t=u=1\). Define \(\beta(G)\) to be the maximum of \(|S||T||U|\) such that \((S,T,U)\) has the TPP. Let \(d_i\) (\(i=1,\dots,k\)) be the degrees of the irreducible characters of \(G\) and put \(D_r(G):=\sum d_i^r\). Then the paper referred to above shows that \(\beta(G)^{\omega/3}\leq D_\omega(G)\) which gives a nontrivial bound on \(\omega\) provided we can find a group with \(\beta(G)>D_3(G)\). The authors of the current paper analyse properties of TPP triples, giving criteria which might be helpful in a computer search for groups with large \(\beta(G)\). They provide the exact values of \(\beta(G)\) for all groups of size \(\leq 32\) and compute \(\beta_g(G)\) (where \(S,T\) and \(U\) are restricted to being subgroups of \(G\)) for a range of other larger groups. Their results are largely negative in terms of obtaining good bounds for \(\omega\). For example, they prove that the use of TPP triples cannot be used to improve the known bounds for multiplication of \(3\times3\) and \(4\times4\) matrices. They also conjecture from their computations that \(\beta_g(G)\leq D_3(G)\) for all \(G\) and so subgroup TPP triples only give trivial bounds on \(\omega\).