google-deepmind / google-deepmind/formal-conjectures
Formalize the matrix multiplication exponent conjecture (ω = 2)
- Dominant language
- Lean
- Stars
- 1.3k
- Forks
- 485
- Avg merge
- 1d 20h
- Merged PRs (30d)
- 327
Description
The matrix multiplication exponent conjecture states that ω = 2: for every ε > 0, two n × n matrices over ℂ can be multiplied using O(n^(2+ε)) arithmetic operations.
A tensor-rank formulation asks that, for every ε > 0, there exists C > 0 such that the rank of the matrix multiplication tensor is at most C n^(2+ε) for every positive n. The tensor is the coefficient tensor of (A, B, C) ↦ tr(ABC), with three modes of size n².
References:
- Cohn, Kleinberg, Szegedy, and Umans, [Group-theoretic Algorithms for Matrix Multiplication](https://arxiv.org/abs/math/0511460), introduction and §1.1.
- Chiantini, Hauenstein, Ikenmeyer, Landsberg, and Ottaviani, [Polynomials and the exponent of matrix multiplication](https://arxiv.org/abs/1706.05074), §1.
I am preparing a draft formalization using Mathlib's `Holor.cprank`. The existing Green 36 statements concern related sufficient combinatorial conjectures.
Contributor guide
Research direction
Start by reading Mathlib's `Holor.cprank` and the cited introductions and §1.1, then compare the existing Green 36 statements in this repository. The work is done when the matrix multiplication exponent conjecture is stated formally in Lean using the tensor-rank formulation described here.
Written by the indexing model from the issue text.
Assessment
- Domain
- devtools
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Needs clarification
- Newbie friendliness
- 30/100