Simultaneous double product property conjecture for abelian groups

From papers

Let nn be a positive integer. A collection of pairs of subsets Ai,BiA_i,B_i of an abelian group HH satisfies the simultaneous double product property when the pairs satisfy the double product property and the corresponding difference-set disjointness conditions described in the paper. The parameters are measured by H|H| and the products AiBi|A_i||B_i|.

Simultaneous double product property conjecture. For arbitrarily large nn, there exists an abelian group HH with nn pairs of subsets Ai,BiA_i,B_i satisfying the simultaneous double product property such that

H=n2+o(1)|H|=n^{2+o(1)}

and

AiBin2o(1).|A_i||B_i|\ge n^{2-o(1)}.

If true, this would provide the algebraic route to the optimal matrix multiplication exponent ω=2\omega=2. The preceding parameter bounds show that α=β=2\alpha=\beta=2 is the only possible way to achieve this exponent; existence of such families remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Henry Cohn, Robert Kleinberg, Balazs Szegedy and Christopher Umans, “Group-theoretic algorithms for matrix multiplication”, arXiv:math/0511460 (2005).

Solutions 0

No solutions have been posted yet.