An additive construction that would give matrix multiplication exponent two
A positive answer would give $\omega = 2$ for the exponent of matrix multiplication: $n \times n$ matrices could be multiplied using $n^{2 + o(1)}$ multiplications. Blasiak, Church, Cohn, Grochow, Naslund, Sawin and Umans showed that groups of bounded exponent cannot give such a construction.
Problem. For arbitrarily large $n$, is there an abelian group $H$ with $|H| = n^{2 + o(1)}$ and subsets $A_1, \dots, A_n, B_1, \dots, B_n$ of $H$ with $|A_i||B_i| \ge n^{2 - o(1)}$ and $|A_i + B_i| = |A_i||B_i|$, such that each $A_i + B_i$ is disjoint from every $A_j + B_k$ with $j \ne k$?
Source: H. Cohn, R. Kleinberg, B. Szegedy and C. Umans, Group-theoretic algorithms for matrix multiplication (2005), Conjecture 4.7. Listed as Problem 36 in B. Green, 100 open problems (version of January 2026).
Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
Classification
- Primary
- CO — Combinatorics
- Secondary
- GR
- Keywords
- abelian groups, group-theoretic method, matrix multiplication, sumsets
- Literature checked
- Oct. 26, 2026 by clemens-admin
References
@inproceedings{cohn2005group,
author = {Cohn, Henry and Kleinberg, Robert and Szegedy, Bal{\'a}zs and Umans, Christopher},
title = {Group-theoretic algorithms for matrix multiplication},
booktitle = {46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)},
pages = {379--388},
year = {2005},
doi = {10.1109/SFCS.2005.39},
eprint = {math/0511460},
archivePrefix = {arXiv},
note = {Conjecture 4.7}
}
@article{blasiak2017cap,
author = {Blasiak, Jonah and Church, Thomas and Cohn, Henry and Grochow, Joshua A. and Naslund, Eric and Sawin, William F. and Umans, Chris},
title = {On cap sets and the group-theoretic approach to matrix multiplication},
journal = {Discrete Analysis},
pages = {Paper No. 3},
year = {2017},
doi = {10.19086/da.1245}
}
@inproceedings{pratt2024corners,
author = {Pratt, Kevin},
title = {On generalized corners and matrix multiplication},
booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
series = {LIPIcs},
volume = {287},
pages = {89:1--89:17},
year = {2024},
doi = {10.4230/LIPIcs.ITCS.2024.89}
}
@misc{green100open,
author = {Green, Ben},
title = {100 open problems},
howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
note = {Problem 36; version of January 2026, most recent update December 2025},
year = {2026}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00985, "An additive construction that would give matrix multiplication exponent two", clopen.solutions.