Mulmuley–Sohoni occurrence-obstruction conjecture

For n>mn>m, let Zn,mZ_{n,m} be the orbit closure of the padded permanent X11nmpermX_{11}^{n-m}\mathrm{per}_m in SymnCn2\mathsf{Sym}^n\mathbb{C}^{n^2}, and let Detn{{\mathcal{D}}et}_n be the orbit closure of the determinant. A partition λ\lambda occurs in a coordinate ring when the corresponding irreducible polynomial representation occurs in that coordinate ring. Mulmuley–Sohoni's occurrence-obstruction conjecture. For every cN1c\in\mathbb{N}_{\ge 1}, for infinitely many mm, there exists a partition λ\lambda occurring in C[Zmc,m]\mathbb{C}[Z_{m^c,m}] but not in \mathbb{C}[{{\mathcal{D}}et_{m^c}]. The existence of such a partition would obstruct the containment Zmc,mDetmcZ_{m^c,m}\subseteq{{\mathcal{D}}et}_{m^c} and hence yield a lower bound for the determinantal complexity of the permanent. The conjecture was proposed as a strategy for proving the border determinantal complexity conjecture, but the source explicitly states that it is false.

Sources & referencesView supporting material

Primary source

Peter Bürgisser, Christian Ikenmeyer and Greta Panova, “No occurrence obstructions in geometric complexity theory”, arXiv:1604.06431 (2018).

Additional references

3 papers in this index state this conjecture (2009–2016). The statement above is taken from the most recent of them; the others are arXiv:0910.2443, arXiv:0907.2850.

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.