Simultaneous double product property conjecture for abelian groups

At least 20 years old · documented by

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 ∣Ai∣∣Bi∣|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

∣Ai∣∣Bi∣≥n2−o(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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.