2026-07-23T22:21:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10627 2024-03-06T10:46:19Z ddc:004 open_access

On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions Dörfler, Julian Ikenmeyer, Christian Panova, Greta Algebraic complexity theory geometric complexity theory Waring rank plethysm coefficients occurrence obstructions multiplicity obstructions Geometric Complexity Theory as initiated by Mulmuley and Sohoni in two papers (SIAM J Comput 2001, 2008) aims to separate algebraic complexity classes via representation theoretic multiplicities in coordinate rings of specific group varieties. We provide the first toy setting in which a separation can be achieved for a family of polynomials via these multiplicities. Mulmuley and Sohoni’s papers also conjecture that the vanishing behavior of multiplicities would be sufficient to separate complexity classes (so-called occurrence obstructions). The existence of such strong occurrence obstructions has been recently disproven in 2016 in two successive papers, Ikenmeyer-Panova (Adv. Math.) and Bürgisser-Ikenmeyer-Panova (J. AMS). This raises the question whether separating group varieties via representation theoretic multiplicities is stronger than separating them via occurrences. We provide first finite settings where a separation via multiplicities can be achieved, while the separation via occurrences is provably impossible. These settings are surprisingly simple and natural: We study the variety of products of homogeneous linear forms (the so-called Chow variety) and the variety of polynomials of bounded border Waring rank (i.e. a higher secant variety of the Veronese variety). As a side result we prove a slight generalization of Hermite’s reciprocity theorem, which proves Foulkes' conjecture for a new infinite family of cases. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julian Dörfler and Christian Ikenmeyer and Greta Panova 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.51 urn:nbn:de:0030-drops-106276 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.51 eng https://creativecommons.org/licenses/by/3.0/legalcode