Mulmuley–Sohoni occurrence-obstruction conjecture

About 17 years old · traced to

For n>mn>m, let Zn,mZ_{n,m} be the orbit closure of the padded permanent X11n−mpermX_{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 c∈N≥1c\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,m⊆DetmcZ_{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.

References

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.