Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-23T03:14:38.348Z Has data issue: false hasContentIssue false
  • English
  • Français

A note on the triple product property for subsets of finite groups

Part of: Representation theory of groups Discrete mathematics in relation to computer science

Published online by Cambridge University Press:  01 September 2011

Peter M. Neumann
Peter M. Neumann*
Affiliation:
The Queen’s College, Oxford OX1 4AW, United Kingdom (email: [email protected])

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The triple product property (TPP) for subsets of a finite group was introduced by Henry Cohn and Christopher Umans in 2003 as a tool for the study of the complexity of matrix multiplication. This note records some consequences of the simple observation that if (S1,S2,S3) is a TPP triple in a finite group G, then so is (dS1a,dS2b,dS3c) for any a,b,c,d∈G.

Let si:=∣Si∣ for 1≤i≤3. First we prove the inequality s1(s2+s3−1)≤∣G∣ and show some of its uses. Then we show (something a little more general than) that if G has an abelian subgroup of index v, then s1s2s3 ≤v2 ∣G∣.

MSC classification

Secondary: 20D60: Arithmetic and combinatorial problems 68R05: Combinatorics
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 14 , 2011 , pp. 232 - 237
Copyright
Copyright © London Mathematical Society 2011

References

[1]Cohn, Henry and Umans, Christopher, ‘A group-theoretic approach to fast matrix multiplication’, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS’03) (IEEE, 2003) 438–449.Google Scholar
[2]Cohn, Henry, Kleinberg, Robert, Szegedy, Balázs and Umans, Christopher, ‘Group-theoretic algorithms for matrix multiplication’, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) (IEEE, 2005) 379–388.CrossRefGoogle Scholar
[3]Curtis, Charles W., Pioneers of representation theory: Frobenius, Burnside, Schur, and Brauer, AMS–LMS Series on History of Mathematics 15 (American Mathematical Society, 1999).CrossRefGoogle Scholar