Explicit Lower Bounds via Geometric Complexity Theory

Acknowledgments

We are grateful to Matthias Christandl, Jon Hauenstein, Jesko Hüttenhain, J.M. Landsberg, and Michael Walter for important discussions. We also thank Hang Guo, Stefan Mengel, and Tyson Williams for a valuable discussion on the coloring problem.

Introduction

The complexity of matrix multiplication is captured by the rank of the matrix multiplication tensor, a quantity that, despite intense research efforts, is little understood. Strassen already observed that the closely related notion of border rank has a natural formulation as a specific orbit closure problem. The work applied and further developed the collection of ideas from Mulmuley and Sohoni to the tensor framework, which is simpler than the one for permanent versus determinant. However, the lower bound obtained in for the border rank $\underline{R}(\matheulerscript{M}_{m})$ of the $m\times m$ matrix multiplication tensor $\matheulerscript{M}_{m}$ is ridiculously small. In this work, we considerably improve this bound and obtain the first significant lower bounds obtained within the GCT program.

Evaluating $f_{\mathcal{H}}$, or testing whether $f_{\mathcal{H}}$ equals the zero polynomial, are challenging problems. It would be interesting to analyzing their complexity.

Our lower bound on the border rank of $\matheulerscript{M}_{m}$ is slightly below the one by Strassen and Lickteig , and also weaker than the very recent improvement by Landsberg and Ottaviani . We note that the recent preprint by Grigoriev et al. also uses representation theory for proving lower bounds on border rank of $\matheulerscript{M}_{m}$. (However, the lower bounds in are substantially worse than the ones by Strassen and Lickteig.)

The main message of our paper is that significant lower bounds can be obtained with geometric complexity theory (GCT). As a further evidence for this, we note that recently, in collaboration with Jon Hauenstein and J.M. Landsberg, we managed to prove $\underline{R}(\matheulerscript{M}_{2})=7$ using an explicit construction of highest weight vectors of weight $\lambda=(5,5,5,5)^{3}$ and relying on computer calculations. This is remarkable, since this was a long-standing open problem since the 70s, which was only settled in 2005 by Landsberg using very different methods.

As a further contribution, we add to the discussion on the feasibility of the GCT approach by pointing out that in a modification of the approach, proving lower bounds is actually equivalent to providing the existence of obstructions (in the sense of highest weight vectors instead of just highest weights), cf. Proposition 3.3.

This work contains results from the PhD thesis of the second author .

Orbit Closure Problems

Suppose that $\underline{R}(w)\geq m$ to avoid trivial cases. Then it is easy to see that $\underline{R}(w)\leq n$ iff $w\in{\overline{G{\matheulerscript{E}_{n}}}}$, cf. .

The tensor corresponding to the $m\times m$ matrix multiplication map can be succinctly written as

2 Approximate Determinantal Complexity

In Mulmuley and Sohoni conjectured the following:

Here $\textup{per}_{m}\in W$ denotes the permanent of the $m\times m$ matrix in the variables $X_{1},\ldots,X_{m^{2}}$.

An affirmative answer to this conjecture implies that $\textup{det}_{n}$ cannot be computed by weakly skew circuits of size polynomial in $m$, (cf. ), which is a version of Valiant’s Conjecture .

3 Unifying Notation

The tensor scenario and the polynomial scenario discussed before have much in common and we strive to treat both situations simultaneously. Hence for fixed $n$ and $m$ we want to use the notations summarized in the following table.

The symbol $\mathpzc{h}$ stands for the hard problem for which we want to prove lower bounds and the orbit closure \overline{G\mathchoice{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\scriptstyle\mathpzc{c}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{c}}}_{n}} is exactly the set of all elements in $V$ with complexity at most $n$. In both scenarios, for a given $m$, we try to find $n$ as large as possible such that

Since the orbit closure is the smallest closed set containing the orbit, this is equivalent to proving {\overline{G\mathchoice{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\scriptstyle\mathpzc{h}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{h}}}_{m,n}}}\not\subseteq\overline{G\mathchoice{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\scriptstyle\mathpzc{c}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{c}}}_{n}}. If we want to treat G\mathchoice{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\scriptstyle\mathpzc{c}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{c}}} and G\mathchoice{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\scriptstyle\mathpzc{h}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{h}}} simultaneously, we just write $Gv$.

The Flip via Obstructions

We call such polynomials $f$ that separate $\mathpzc{h}$ from \overline{G\mathchoice{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\scriptstyle\mathpzc{c}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{c}}}} polynomial obstructions. By Proposition 3.1, they are guaranteed to exist if \mathchoice{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\scriptstyle\mathpzc{h}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{h}}}\notin\overline{G\mathchoice{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\scriptstyle\mathpzc{c}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{c}}}}. We want to investigate whether there are “short encodings” of polynomial obstructions $f$ and whether there are “short proofs” that $f$ is an obstruction. Representation theory provides a natural framework to address these questions.

Let $U_{n}\subseteq\mathsf{GL}_{n}$ denote the group of upper triangular matrices with 1s on the main diagonal, the so-called maximal unipotent group. A weight vector $f\in\mathscr{V}$ that is fixed under the action of $U_{n}$, i.e., $\forall u\in U_{n}:uf=f$, is called a highest weight vector (HWV) of $\mathscr{V}$. The vector space of HWVs of weight $\lambda$ is denoted by $\mathsf{HWV}_{\lambda}(\mathscr{V})$. The following is well known.

Each irreducible rational $\mathsf{GL}_{n}$-representation $\mathscr{W}$ contains, up to scalar multiples, exactly one nonzero HWV $f$. The representation $\mathscr{W}$ is the linear span of the $\mathsf{GL}_{n}$-orbit of $f$. Two irreducible representations are isomorphic iff the weights of their HWVs coincide.

2 HWV Obstructions

The following result shows that when searching for polynomial obstructions, we can restrict ourselves to HWVs.

The fact f(\overline{G\mathchoice{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\scriptstyle\mathpzc{c}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{c}}}})=0 means that $f$ is contained in the vanishing ideal I(\overline{G\mathchoice{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\scriptstyle\mathpzc{c}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{c}}}}). But I(\overline{G\mathchoice{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\scriptstyle\mathpzc{c}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{c}}}}) is a graded $G$-representation. Hence we can write $f=\sum_{d,\lambda}f_{d,\lambda},$ where f_{d,\lambda}\in I(\overline{G\mathchoice{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\scriptstyle\mathpzc{c}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{c}}}})_{d} are elements from the isotypic component of type $\lambda$ in the homogeneous part I(\overline{G\mathchoice{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\scriptstyle\mathpzc{c}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{c}}}})_{d}. By Lemma 3.2, it follows that we can write $f_{d,\lambda}=\sum_{i}g_{d,\lambda,i}f_{d,\lambda,i},$ where $g_{d,\lambda,i}\in G$ and $f_{d,\lambda,i}$ is a HWV in I(\overline{G\mathchoice{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\scriptstyle\mathpzc{c}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{c}}}})_{d} of weight $\lambda$.

Let $g\in G$ with f(g\mathchoice{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\scriptstyle\mathpzc{h}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{h}}})\neq 0. Then g_{d,\lambda,i}f_{d,\lambda,i}(g\mathchoice{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\scriptstyle\mathpzc{h}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{h}}})\neq 0 for some $d,\lambda,i$. This means f_{d,\lambda,i}(g_{d,\lambda,i}^{-1}g\mathchoice{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\scriptstyle\mathpzc{h}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{h}}})\neq 0, which proves the proposition. ∎

We call such $f_{\lambda}$ a HWV obstruction against \mathchoice{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\scriptstyle\mathpzc{h}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{h}}}\in\overline{G\mathchoice{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\scriptstyle\mathpzc{c}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{c}}}}. We will show that some HWVs have a succinct encoding, which is linear in their degree $d$.

While Proposition 3.3 tells us that \mathchoice{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\scriptstyle\mathpzc{h}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{h}}}\not\in\overline{G\mathchoice{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\scriptstyle\mathpzc{c}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{c}}}} can, in principle, always be proven by exhibiting a HWV obstruction, it is unclear whether this is also the case for occurence obstructions. We state this as an important open problem.

For the scenarios in Subsection 2.3, if \mathchoice{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\mathpzc{h}}}{\scalebox{1.1}{\scriptstyle\mathpzc{h}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{h}}}_{m,n}\notin\overline{G\mathchoice{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\mathpzc{c}}}{\scalebox{1.1}{\scriptstyle\mathpzc{c}}}{\scalebox{1.1}{\scriptscriptstyle\mathpzc{c}}}_{n}}, is there an occurence obstruction proving this?

Mulmuley and Sohoni conjecture that (2.2) can be proved with occurence obstructions, see [22, §3].

Main Results

For a triple $\lambda=(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)})$ of partitions, henceforth called partition triple, we use the short notation \lambda\smash{\mathord{\mathchoice{\lx@xy@svg{\hbox{\raise 2.5pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 0.52827pt\raise-2.50694pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.50694pt\hbox{\textstyle{\scriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 0.95132pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 1.52827pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{n}}}}}}}}{\hbox{\kern 6.99988pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.5pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.97166pt\raise-2.50694pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.50694pt\hbox{\textstyle{\scriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.54861pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 0.02834pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{n}}}}}}}}{\hbox{\kern 4.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.5pt\hbox{\kern 1.20203pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-1.20203pt\raise-2.07639pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.07639pt\hbox{\textstyle{\scriptscriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-1.04865pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern-0.20203pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptscriptstyle{n}}}}}}}}{\hbox{\kern 2.99994pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{}}}d to express that \lambda^{(k)}\smash{\mathord{\mathchoice{\lx@xy@svg{\hbox{\raise 2.5pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 0.52827pt\raise-2.50694pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.50694pt\hbox{\textstyle{\scriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 1.52827pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{n}}}}}}}}{\hbox{\kern 6.99988pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.5pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.97166pt\raise-2.50694pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.50694pt\hbox{\textstyle{\scriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 0.02834pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{n}}}}}}}}{\hbox{\kern 4.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.5pt\hbox{\kern 1.20203pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-1.20203pt\raise-2.07639pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.07639pt\hbox{\textstyle{\scriptscriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern-0.20203pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptscriptstyle{n}}}}}}}}{\hbox{\kern 2.99994pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{}}}d for all $k\in\{1,2,3\}$.

A set partition $\Lambda$ of a set $S$ is a set of subsets of $S$ such that for all $s\in S$ there exists exactly one $e_{s}\in\Lambda$ with $s\in e_{s}$. If $\mu$ denotes the partition obtained from sorting the multiset $\{|e|:e\in\Lambda\}$, then we call the partition ${{{}^{t}\!}{\mu}}$ the type of $\Lambda$. (The reason for taking the transpose will become clear soon.)

2 Obstruction Designs Encoding HWVs

The following reasonings require some multilinear algebra.

More specifically, the polynomial $f_{\mathcal{H}}$ can be described as follows. Suppose that the tensor $w$ is decomposed into distinct rank 1 tensors as $w=\sum_{i=1}^{r}w^{(1)}_{i}\otimes w^{(2)}_{i}\otimes w^{(3)}_{i}$. We have

Consider the set $\mathscr{T}:=\{(w^{(1)}_{i},w^{(2)}_{i},w^{(3)}_{i})\mid 1\leq i\leq r\}$ of triples of vectors. The maps $I\colon[d]\to[r]$ correspond bijectively to the triple labelings $J\colon\mathcal{H}\to\mathscr{T}$ defined by $J^{(k)}(s):=w_{I(s)}^{(k)}$. Therefore,

By symmetry, $f_{\mathcal{H}}(w)$ does not depend on the chosen ordering of $\mathcal{H}$.

3 Chromatic Index of Obstruction Designs

We describe here a simple combinatorial condition for $f_{\mathcal{H}}$ vanishing on all tensors of border rank at most $r$. Let us stress that this condition is sufficient, but far from being necessary.

By a proper coloring of an obstruction design $\mathcal{H}$ with $c$ colors we shall understand a map $\sigma\colon\mathcal{H}\to[c]$ such that in each slice of $\mathcal{H}$, the colors of points are pairwise different. The chromatic index $\chi^{\prime}(\mathcal{H})$ is defined as the least number of colors sufficient for coloring $\mathcal{H}$.

It is therefore desirable to find obstruction designs with large chromatic index. There is a limit though.

We have $\chi^{\prime}(\mathcal{H})\leq 3n-2$ for any obstruction design of type \lambda\smash{\mathord{\mathchoice{\lx@xy@svg{\hbox{\raise 2.55554pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 0.61713pt\raise-2.50694pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.50694pt\hbox{\textstyle{\scriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.04018pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 1.61713pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{n}}}}}}}}{\hbox{\kern 7.17758pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.55554pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.91612pt\raise-2.50694pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.50694pt\hbox{\textstyle{\scriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.49307pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 0.08388pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{n}}}}}}}}{\hbox{\kern 4.11108pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.55554pt\hbox{\kern 1.15761pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-1.15761pt\raise-2.07639pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.07639pt\hbox{\textstyle{\scriptscriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-1.00423pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern-0.15761pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptscriptstyle{n}}}}}}}}{\hbox{\kern 3.08878pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{}}}d.

$\chi^{\prime}(\mathcal{H})$ equals the chromatic number of the graph $G$ with vertex set $\mathcal{H}$, in which two nodes are connected iff they lie in a same slice. Each node in this graph has degree at most $\Delta=3(n-1)$, since there are at most $n$ nodes in each slice. It is well known from graph theory that $1+\Delta$ is an upper bound on the chromatic number of $G$. ∎

This result shows that $3n-2$ is the best lower bound on border rank that can be shown based on Proposition 4.2. Unfortunately, the limit seems even smaller.

We next show that we can achieve this lower bound for the matrix multiplication tensor.

4 Lower Bound for Matrix Multiplication

In Section 6 we shall prove the following technical result.

There exists a matrix triple $A\in(\mathsf{GL}_{m^{2}})^{3}$ such that $f_{\mathcal{H}_{\kappa}}(A\matheulerscript{M}_{m})\neq 0$, where $\kappa:=\frac{m^{2}-1}{2}$ for $m>1$ odd.

Combined with Proposition 4.2, this implies the following result if $m$ is odd. (The proof where $m$ is even is omitted.)

We have $\underline{R}(\matheulerscript{M}_{m})\geq\frac{3}{2}m^{2}-\frac{1}{2}$ if $m$ is odd. Moreover, $\underline{R}(\matheulerscript{M}_{m})\geq\frac{3}{2}m^{2}-2$ if $m$ is even.

The same proof gives the same lower bound on the s-rank of the matrix multiplication tensor.

5 Comments, Examples, Open Questions

We have $k({\lambda})\leq N(\lambda)$ for \lambda\smash{\mathord{\mathchoice{\lx@xy@svg{\hbox{\raise 2.55554pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 0.61713pt\raise-2.50694pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.50694pt\hbox{\textstyle{\scriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.04018pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 1.61713pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{n}}}}}}}}{\hbox{\kern 7.17758pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.55554pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.91612pt\raise-2.50694pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.50694pt\hbox{\textstyle{\scriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.49307pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 0.08388pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{n}}}}}}}}{\hbox{\kern 4.11108pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.55554pt\hbox{\kern 1.15761pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-1.15761pt\raise-2.07639pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.07639pt\hbox{\textstyle{\scriptscriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-1.00423pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern-0.15761pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptscriptstyle{n}}}}}}}}{\hbox{\kern 3.08878pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{}}}d.

Mulmuley conjectures that deciding $k({\lambda})>0$ is possible in polynomial time. This should be contrasted with the following result, which follows from .

Given a partition triple \lambda\smash{\mathord{\mathchoice{\lx@xy@svg{\hbox{\raise 2.55554pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 0.61713pt\raise-2.50694pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.50694pt\hbox{\textstyle{\scriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.04018pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 1.61713pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{n}}}}}}}}{\hbox{\kern 7.17758pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.55554pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.91612pt\raise-2.50694pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.50694pt\hbox{\textstyle{\scriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.49307pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 0.08388pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{n}}}}}}}}{\hbox{\kern 4.11108pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.55554pt\hbox{\kern 1.15761pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-1.15761pt\raise-2.07639pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.07639pt\hbox{\textstyle{\scriptscriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-1.00423pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern-0.15761pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptscriptstyle{n}}}}}}}}{\hbox{\kern 3.08878pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{}}}d encoded in unary. Then it is NP-complete to decide whether there exists an obstruction design of type $\lambda$.

Deciding whether $f_{\mathcal{H}}$ vanishes identically can be difficult even in seemingly simple situations.

Let $\mathcal{H}_{n}:=\{(i,j,n(i-1)+j)\}\subseteq[n]\times[n]\times[n^{2}]$ and $w:=\sum_{i=1}^{n}|ii1\rangle$. Identifying $\mathscr{T}$ with $[n]$, we can interpret a labeling $J\colon\mathcal{H}_{n}\to[n]$ with the filling of an $n\times n$ square with numbers in $[n]$. It is easy to see that $\mathsf{eval}_{\mathcal{H}_{n}}(J)=0$ unless $J$ is a Latin square, i.e., each number $j\in[n]$ occurs in each row and each column of the square exactly once. In this case, $J$ defines a permutation of $[n]$ in each row and each column of the Latin square. It is straightforward to see that $\mathsf{eval}_{E^{(1)}}(J)$ equals the product of the signs of the row permutations and $\mathsf{eval}_{E^{(2)}}(J)$ equals the product of the signs of the column permutations. Moreover, $\mathsf{eval}_{E^{(3)}}(J)=1$. Let us call the Latin square even if $\mathsf{eval}_{E^{(1)}}(J)\cdot\mathsf{eval}_{E^{(2)}}(J)=1$ and odd if this value equals $-1$.

Equation (4.2) implies that $f_{\mathcal{H}_{n}}(w)$ equals the difference of the number of even and the number of odd Latin squares.

It is easy to see that $f_{\mathcal{H}_{n}}(w)=0$ if $n$ is odd (exchange two rows). The Alon-Tarsi Conjecture states $f_{\mathcal{H}_{n}}(w)\neq 0$ if $n$ is even. For instance, this conjecture is known to be true for $n\leq 24$ or if $n$ differs from an odd prime exactly by $1$, cf. . The general case, however, is wide open. We note that $f_{\mathcal{H}_{n}}\neq 0$ iff $f_{\mathcal{H}_{n}}(w)\neq 0$.

The construction of explicit highest weight vectors in the polynomial scenario leads to questions regarding Latin squares and the Alon-Tarsi Conjecture as well, cf. Kumar .

The following fundamental questions arise when studying the highest weight vectors $f_{\mathcal{H}}$ labeled by obstruction designs $\mathcal{H}$.

Given an obstruction design $\mathcal{H}$ of type \lambda\smash{\mathord{\mathchoice{\lx@xy@svg{\hbox{\raise 2.55554pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 0.61713pt\raise-2.50694pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.50694pt\hbox{\textstyle{\scriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.04018pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 1.61713pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{n}}}}}}}}{\hbox{\kern 7.17758pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.55554pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.91612pt\raise-2.50694pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.50694pt\hbox{\textstyle{\scriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.49307pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 0.08388pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{n}}}}}}}}{\hbox{\kern 4.11108pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.55554pt\hbox{\kern 1.15761pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-1.15761pt\raise-2.07639pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.07639pt\hbox{\textstyle{\scriptscriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-1.00423pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern-0.15761pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptscriptstyle{n}}}}}}}}{\hbox{\kern 3.08878pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{}}}d. What is the complexity of deciding whether $f_{\mathcal{H}}=0$?

For a given partition triple \lambda\smash{\mathord{\mathchoice{\lx@xy@svg{\hbox{\raise 2.55554pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 0.61713pt\raise-2.50694pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.50694pt\hbox{\textstyle{\scriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.04018pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 1.61713pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{n}}}}}}}}{\hbox{\kern 7.17758pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.55554pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.91612pt\raise-2.50694pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.50694pt\hbox{\textstyle{\scriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.49307pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 0.08388pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{n}}}}}}}}{\hbox{\kern 4.11108pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.55554pt\hbox{\kern 1.15761pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-1.15761pt\raise-2.07639pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.07639pt\hbox{\textstyle{\scriptscriptstyle n}}}}\kern 3.0pt}}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-1.00423pt\raise 2.62846pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.62846pt\hbox{\textstyle{\scriptstyle\ast}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern-0.15761pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptscriptstyle{n}}}}}}}}{\hbox{\kern 3.08878pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.55554pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{}}}d, explicitly describe a maximal linear independent subset of the set of obstruction designs of type $\lambda$!

Let $[{\lambda^{(k)}}]$ denote the irreducible $\mathsf{S}_{d}$-representation corresponding to $\lambda^{(k)}$ (Specht-module). An answer to Question 4.7(3) would result in an explicit basis of $([{\lambda^{(1)}}]\otimes[{\lambda^{(2)}}]\otimes[{\lambda^{(3)}}])^{\mathsf{S}_{d}}$ and solve one of the most fundamental open questions in the representation theory of the symmetric groups.

6 Determinantal Complexity

where $\mathchoice{\mathsf{sk}{\big({\lambda};\big(n\mathord{\times}d\big)^{2}\big)}}{\mathsf{sk}{\big({\lambda};\big(n\mathord{\times}d\big)^{2}\big)}}{\mathsf{sk}{({\lambda};(n\mathord{\times}d)^{2})}}{\mathsf{sk}{({\lambda};(n\mathord{\times}d)^{2})}}$ is the symmetric Kronecker coefficients, defined in . A sufficient criterion for the existence of a HWV of weight $\lambda^{*}$ in the vanishing ideal $I(\mathsf{GL}_{n^{2}}\textup{det}_{n})$ is given by

since $\mult_{\lambda^{*}}(I(\mathsf{GL}_{n^{2}}\textup{det}_{n}))\ \stackrel{{\scriptstyle\eqref{eq:multipl-det}}}{{\geq}}\ p_{\lambda}({d[n]})-\mathchoice{\mathsf{sk}{\big({\lambda};\big(n\mathord{\times}d\big)^{2}\big)}}{\mathsf{sk}{\big({\lambda};\big(n\mathord{\times}d\big)^{2}\big)}}{\mathsf{sk}{({\lambda};(n\mathord{\times}d)^{2})}}{\mathsf{sk}{({\lambda};(n\mathord{\times}d)^{2})}}$.

Here are two examples of partitions satisfying (4.9), found by computer calculations: (13,13,2,2,2,2,2)\smash{\mathord{\mathchoice{\lx@xy@svg{\hbox{\raise 2.5pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0069pt\raise-3.25555pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-2.25555pt\hbox{\textstyle{\scriptstyle 7}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 2.00688pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{7}}}}}}}}{\hbox{\kern 6.99988pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.5pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.49304pt\raise-3.25555pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-2.25555pt\hbox{\textstyle{\scriptstyle 7}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 0.50694pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{7}}}}}}}}{\hbox{\kern 4.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.5pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.70145pt\raise-2.61111pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.6111pt\hbox{\textstyle{\scriptscriptstyle 7}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 0.29855pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptscriptstyle{7}}}}}}}}{\hbox{\kern 2.99994pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{}}}36 in degree $\tfrac{36}{3}=12$ and (15,5,5,5,5,5,5)\smash{\mathord{\mathchoice{\lx@xy@svg{\hbox{\raise 2.5pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0069pt\raise-3.25555pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-2.25555pt\hbox{\textstyle{\scriptstyle 7}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 2.00688pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{7}}}}}}}}{\hbox{\kern 6.99988pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.5pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.49304pt\raise-3.25555pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-2.25555pt\hbox{\textstyle{\scriptstyle 7}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 0.50694pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptstyle{7}}}}}}}}{\hbox{\kern 4.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{\lx@xy@svg{\hbox{\raise 2.5pt\hbox{\kern 1.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&&\crcr}}}\ignorespaces{\hbox{\kern-1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern 1.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@stopper}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern-0.70145pt\raise-2.61111pt\hbox{{}\hbox{\kern 0.0pt\raise-0.00002pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern-2.0pt\raise-1.6111pt\hbox{\textstyle{\scriptscriptstyle 7}}}}\kern 3.0pt}}}}}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern 0.29855pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\textstyle{\phantom{\scriptscriptstyle{7}}}}}}}}{\hbox{\kern 2.99994pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 1.0pt\raise-2.5pt\hbox{\textstyle{}}}}}}}}\ignorespaces}}}}\ignorespaces}{}}}45 in degree $\tfrac{45}{3}=15$. An abundance of other partitions satisfying (4.9) is given in [13, Appendix].

Explicit HWVs

The goal of this section is to prove Theorem 4.1.

Let $\mu:={{{}^{t}\!}{\lambda}}$ denote the transposed partition of $\lambda$ and consider the following set partition of $[d]$ of type $\lambda$:

A moment’s thought reveals that $\mathsf{eval}_{\Lambda_{\lambda}}=\bigotimes_{i=1}^{\lambda_{1}}\langle\widehat{\mu_{i}}|$. From this description, it is readily checked that $\mathsf{eval}_{\Lambda_{\lambda}}$ is a HWV of weight $\lambda^{*}$.

All $\mathsf{eval}_{\Lambda}$ are obtained from from $\mathsf{eval}_{\Lambda_{\lambda}}$ by applying arbitrary permutations in $\mathsf{S}_{d}$.

Recall that $\{{\lambda}\}$ and $[{\lambda}]$ denote the irreducible $\mathsf{GL}_{n}$-representation and irreducible $\mathsf{S}_{d}$-representation corresponding to $\lambda$, respectively. The fundamental Schur-Weyl duality states that

as $\mathsf{GL}_{n}\times\mathsf{S}_{d}$-representations, e.g., see [11, Sec. 4.2.4].

2 Proof of Theorem 4.1

Suppose now that $V$ is an abstract finite set endowed with three set partitions $\Lambda^{(k)}$ of the set $V$ satisfying the above intersection property. Then the incidence structure

is an obstruction design (after numbering each of the sides $\Lambda^{(k)}$). This obstruction design allows to retrieve the set $V$ and the partitions $\Lambda^{(k)}$. In fact, $\mathcal{H}\to V,\,(e^{(1)},e^{(2)},e^{(3)})\mapsto v$ such that $\{v\}=e^{(1)}\cap e^{(2)}\cap e^{(3)}$ is a bijection. Moreover, this maps the $1$-slice $\{(e^{(2)},e^{(3)})\mid(e^{(1)},e^{(2)},e^{(3)})\in\mathcal{H}\}$ to $e^{(1)}$. Similarly for the other slices.

If the three set partitions $\Lambda^{(k)}$ satisfy the above intersection property, then they define an obstruction design $\mathcal{H}$ by the above reasoning. Moreover, we have $f_{\mathcal{H}}=\big(\mathsf{eval}_{\Lambda^{(1)}}\otimes\mathsf{eval}_{\Lambda^{(2)}}\otimes\mathsf{eval}_{\Lambda^{(3)}}\big)\circ\mathcal{P}_{d}$ by the definition of $f_{\mathcal{H}}$.

To complete the proof of Theorem 4.1, it therefore suffices to show that if the intersection property is violated, then the resulting form vanishes.

Suppose that there are $e^{(k)}\in\Lambda^{(k)}$ for $k=1,2,3$ such that $e^{(1)}\cap e^{(2)}\cap e^{(3)}$ contains more than one element. Then $\big(\mathsf{eval}_{\Lambda^{(1)}}\otimes\mathsf{eval}_{\Lambda^{(2)}}\otimes\mathsf{eval}_{\Lambda^{(3)}}\big)\circ\mathcal{P}_{d}$ vanishes.

Writing $F:=\mathsf{eval}_{\Lambda^{(1)}}\otimes\mathsf{eval}_{\Lambda^{(2)}}\otimes\mathsf{eval}_{\Lambda^{(3)}}$ we obtain $F(J)=(-1)^{3}F(J\circ\tau)$. It follows that

Proof of Lemma 4.4

Recall from Section 5.2 that we may interpret an obstruction design $\mathcal{H}$ as a set $V(\mathcal{H})$ endowed with three set partitions $E^{(k)}$ of $V$ satisfying the intersection property.

The obstruction design $\mathcal{H}_{\kappa}$ introduced in Section 4.4 then can be visualized as follows (see Figure 1). The vertex set $V(\mathcal{H})$ is partioned into disjoint sets $V^{(1)}\mathrel{\dot{\cup}}V^{(2)}\mathrel{\dot{\cup}}V^{(3)}\mathrel{\dot{\cup}}\{y^{0}\}$, where $|V^{(k)}|=\kappa$ for all $k$. Each $E^{(k)}$ consists of one hyperedge $e^{(k)}\coloneqq V^{(k+1)}\cup V^{(k+2)}\cup\{y^{0}\}$ of size $2\kappa+1$ (addition mod $3$ in the exponent) and $\kappa$ singletons.

We outline now the proof of Lemma 4.4. For notational convenience, we define the triples of vectors

(omitting parentheses) and put $\mathscr{T}\coloneqq\{t_{ijl}\mid 1\leq i,j,l\leq m\}$. Recall from (2.1):

After fixing a numbering of the vertices of $\mathcal{H}$, Equation (4.2) can be written as

We use the short notation $\mathsf{eval}_{e}(J)\coloneqq\textup{det}J^{(k)}|_{e}$ for a hyperedge $e\in E^{(k)}$ and a triple labeling $J$.

It suffices to show the claim for a transposition $\sigma$ exchanging two elements of $V^{(1)}$, because the situation for $V^{(2)}$ and $V^{(3)}$ is completely symmetric. We have $\prod_{e\in E^{(1)}}\mathsf{eval}_{e}(J)=\prod_{e\in E^{(1)}}\mathsf{eval}_{e}(J\circ\sigma)$, because, up to reordering, both products have the same factors. For $k\in\{2,3\}$ we have $\mathsf{eval}_{e}(J)=\mathsf{eval}_{e}(J\circ\sigma)$ for every singleton hyperedge $e\in E^{(k)}$ and $\mathsf{eval}_{e^{(k)}}(J)=-\mathsf{eval}_{e^{(k)}}(J\circ\sigma)$. Therefore $\prod_{e\in E^{(k)}}\mathsf{eval}_{e}(J)=-\prod_{e\in E^{(k)}}\mathsf{eval}_{e}(J\circ\sigma)$. As a result we get $\mathsf{eval}_{\mathcal{H}}(J)=(-1)^{2}\mathsf{eval}_{\mathcal{H}}(J\circ\sigma).$

2 Special Structure of the Matrix Triple

For each $1\leq k\leq 3$ we define the matrix $A^{(k)}$ of format $(m\times m)\times m^{2}$ with the following affine linear entries in $X_{i}^{(k)}$:

where we arranged the rows and columns as follows: The left $m$ columns correspond to the vectors $|i\bar{i}\rangle$, where the leftmost one corresponds to $|aa\rangle$. The top row corresponds to the vector $|1\rangle$ and the following $m-1$ rows correspond to the vectors $|\varphi(i\bar{i})\rangle$. Recall that $f_{\mathcal{H}}(A\matheulerscript{M}_{m})$ is a sum of products of determinants of submatrices of the $A^{(k)}$.

The sum $f_{\mathcal{H}}(A\matheulerscript{M}_{m})$ is an element of $\Gamma$ and we are interested in its coefficient of the monomial $\mathcal{X}$, where

We remark that the degree of $\mathcal{X}$ is $3(1+\sum_{i=1}^{m}|i-\bar{i}|)$. It is readily checked that $\sum_{i=1}^{m}|i-\bar{i}|=\kappa$.

We call a triple labeling $J\colon V(\mathcal{H})\to\mathscr{T}$ nonzero, if the coefficient of $\mathcal{X}$ in the polynomial $\mathsf{eval}_{\mathcal{H}}(AJ)$ is nonzero. We will count and classify all nonzero triple labelings $J$ and show that all $\mathsf{eval}_{\mathcal{H}}(AJ)$ contribute the same coefficient with respect to the monomial $\mathcal{X}$. This implies that the coefficient of $\mathcal{X}$ in $f_{\mathcal{H}}(A\matheulerscript{M}_{m})$ is a sum without cancellations and hence is nonzero.

3 Separate Analysis of the Three Layers

We fix a nonzero triple labeling $J\colon V(\mathcal{H})\to\mathscr{T}$ and write $J=(J^{(1)},J^{(2)},J^{(3)})$. Recall that the hyperedge $e^{(k)}$ has size $2\kappa+1=m^{2}$. Since $J$ is nonzero, $J^{(k)}$ is injective on hyperedges and therefore $|\{J^{(k)}(y):y\in e^{(k)}\}|=m^{2}$. Hence $J^{(k)}$ is bijective on $e^{(k)}$.

For all $y\in V^{(k)}$ we have $J^{(k)}(y)=|i\bar{i}\rangle$ for some $1\leq i\leq m$.

Since $\{y\}\in E^{(k)}$ and $J$ is nonzero, we have $\langle 1|A^{(k)}|J^{(k)}(y)\rangle\neq 0$. From the definition of $A$ it follows that $J^{(k)}(y)=|ij\rangle$ and the third case $j\neq\bar{i}$ is excluded. Hence $j=\bar{i}$.

We have $J(y^{0})=(|aa\rangle,|aa\rangle,|aa\rangle)$.

For the following argument it is important to keep the structure of the matrix $A^{(k)}$ in mind, cf. (6.2). Recall that $f_{\mathcal{H}}(A\matheulerscript{M}_{m})$ is a sum of products of certain subdeterminants of $A^{(k)}$ that are determined by the hyperedges in $E^{(k)}(\mathcal{H})$. The coefficient of $\mathcal{X}$ in $\mathsf{eval}_{\mathcal{H}}(AJ(1),\ldots,AJ(d))$ is nonzero as $J$ is nonzero. Fix $k$. Since the degree of $X_{a}^{(k)}$ in $\mathcal{X}$ is one, there is exactly one vertex $y_{k}\in V(\mathcal{H})$ with $J^{(k)}(y)=|aa\rangle$. But we know that $J^{(k)}$ bijective on $e^{(k)}$, so $y_{k}\in e^{(k)}$.

It is now sufficient to show that $y_{1}=y_{2}=y_{3}$ (since $e^{(1)}\cap e^{(2)}\cap e^{(3)}=\{y^{0}\}$).

The structure of the matrix multiplication tensor implies that $J(y_{1})=(|aa\rangle,|ai\rangle,|ia\rangle)$ for some $1\leq i\leq m$.

In the case $a=i$, by definition of $y_{2}$ and $y_{3}$ and uniqueness, we have $y_{1}=y_{2}=y_{3}$ and we are done.

So consider the case where $a\neq i$. If $y_{1}\neq y^{0}$ we may assume w.l.o.g. $y_{1}\in V^{(3)}$. Using Claim 2 we conclude that $J^{(3)}(y_{1})=|i\bar{i}\rangle$ for some $1\leq i\leq m$. Hence $\bar{i}=a$ contradicting $i\neq a$. So we must have $y_{1}=y^{0}$.

Similarly, we show that $y_{2}=y_{3}=y^{0}$ and the assertion follows.

We have $J^{(k)}(V^{(k)})=\{|i\bar{i}\rangle\mid 1\leq i\leq m\}\setminus\{|aa\rangle\}$, where the preimage of each $|i\bar{i}\rangle$ under $J^{(k)}$ has size $|i-\bar{i}|$.

According to Claim 3 we have $J(y^{0})=(|aa\rangle,|aa\rangle,|aa\rangle)$. Since $A^{(k)}|aa\rangle$ is a multiple of $|1\rangle$, $\mathsf{eval}_{e^{(k)}}(J^{(k)})$ is a multiple of $X_{a}^{(k)}$, cf. (6.2). Moreover, for $i\neq a$, the variable $X_{i}^{(k)}$ does not appear in the expansion of $\mathsf{eval}_{e^{(k)}}(J^{(k)})$. Since there are $\kappa=\sum_{i=1}^{m}|i-\bar{i}|$ many contributions of a factor $X_{i}^{(k)}$ in the monomial $\mathcal{X}$, these factors must be contributed at vertices in $V^{(k)}$. Moreover $|V^{(k)}|=\kappa$, so the only possibility is that all $y\in V^{(k)}$ satisfy $J^{(k)}(y)=|i\bar{i}\rangle$ for some $1\leq i\leq m$, $i\neq a$. The specific requirement for the number of factors $X_{i}^{(k)}$ which are encoded in $\mathcal{X}$ in (6.12) finishes the proof.

4 Coupling the Analysis of the Three Layers

It will be convenient to identify the sets $J^{(k)}(V^{(k^{\prime})})$ with their corresponding subsets of $O_{m}$.

Consider the bijective map $\tau\colon O_{m}\to O_{m},\ \tau(ij)=(j\bar{i}),$ which corresponds to the rotation by $90^{\circ}$. Clearly, $\tau^{4}=\id$. The map $\tau$ induces a map $\wp(O_{m})\to\wp(O_{m})$ on the powerset, which we also denote by $\tau$.

Taking the complement defines the involution $\iota\colon\wp(O_{m})\to\wp(O_{m}),\ S\mapsto O_{m}\setminus S.$ Clearly, we have $\tau\circ\iota=\iota\circ\tau$. We will only be interested in subsets $S\subseteq O_{m}$ with exactly $|O_{m}|/2=\kappa$ many elements and their images under $\tau$ and $\iota$. The subsets $S\subseteq O_{m}$ that satisfy $\iota(S)=\tau(S)$ will be of special interest. Geometrically, these are the sets that get inverted when rotating by $90^{\circ}$.

In Claim 4 we analyzed the labels $J^{(k)}(V^{k})$. In the next claim we turn to $J^{(k)}(V^{k^{\prime}})$, where $k\neq k^{\prime}$.

Every nonzero triple labeling $J$ is completely determined by the image $J^{(1)}(V^{(3)})$ (up to permutations in the $V^{(k)}$, see Claim 1) as follows.

$J^{(2)}(V^{(3)})=\tau(J^{(1)}(V^{(3)}))$,

$J^{(2)}(V^{(1)})=\iota(J^{(2)}(V^{(3)}))$,

$J^{(3)}(V^{(1)})=\tau(J^{(2)}(V^{(1)}))$,

$J^{(3)}(V^{(2)})=\iota(J^{(3)}(V^{(1)}))$,

$J^{(1)}(V^{(2)})=\tau(J^{(3)}(V^{(2)}))$.

Moreover, $\tau(J^{(1)}(V^{(3)}))=\iota(J^{(1)}(V^{(3)}))$.

According to Claim 4, each vertex $y\in V^{(3)}$ satisfies

for some $1\leq i,j\leq m$, $i\neq a$. In particular,

Recall that $J^{(2)}$ is bijective on $e^{(2)}$. Using $e^{(2)}=V^{(1)}\mathrel{\dot{\cup}}V^{(3)}\mathrel{\dot{\cup}}\{y^{0}\}$ we see that

For the same reason, we can deduce $J^{(3)}(V^{(1)})=\tau(J^{(2)}(V^{(1)}))$ and $J^{(3)}(V^{(2)})=\iota(J^{(3)}(V^{(1)}))$. And applying these arguments one more time we get $J^{(1)}(V^{(2)})=\tau(J^{(3)}(V^{(2)}))$ and $J^{(1)}(V^{(3)})=\tau(J^{(1)}(V^{(2)}))$. Summarizing (recall $\tau\circ\iota=\iota\circ\tau$) we have

which is equivalent to $\tau(J^{(1)}(V^{(3)}))=\iota(J^{(1)}(V^{(3)}))$.

A subset $S\subseteq O_{m}$ is called valid, if

$|p^{-1}(i)|=|i-\bar{i}|$ for all $1\leq i\leq m$

where $p\colon S\to\{1,\ldots,m\}$ is the projection to the first component.

$J^{(1)}(V^{(3)})$ is a valid set for all nonzero triple labelings $J$. On the other hand, for every valid set $S$ there exists exactly one nonzero triple labeling $J$ with $J^{(1)}(V^{(3)})=S$, up to permutations in the $V^{(k)}$.

For the first statement, property (2) of Def. 6.6 follows from Claim 5 and property (3) of Def. 6.6 follows from Claim 4. The second statement can be readily checked with Claim 3 and Claim 5.

Figure 2 gives an example for the case $m=9$. Vertices that appear in all valid sets are drawn with a solid border. Vertices that appear in no valid set are drawn with a dotted border. Vertices that appear in half of all valid sets are drawn with a dashed border. These contain a vertex label $x_{i}$ or $\overline{x_{i}}$. Each valid set corresponds to a choice vector $x\in\{\text{true},\text{false}\}^{4}$ determining whether the $x_{i}$ or the $\overline{x_{i}}$ are contained in $S$. This results in $2^{4}=16$ valid sets $S\subseteq O_{m}$.

The next claim classifies all valid sets.

A set $S\subseteq O_{m}$ is valid iff the following conditions are all satisfied (see Figure 2 for an illustration):

$\Big\{(ij)\mid(i<j\textup{ and }i<\bar{j})\textup{ or }(i>j\textup{ and }i>\bar{j})\Big\}\subseteq S$, represented by solid vertices in Figure 2.

$\Big\{(ij)\mid(i>j\textup{ and }i<\bar{j})\textup{ or }(i<j\textup{ and }i>\bar{j})\Big\}\cap S=\emptyset$, represented by dotted vertices in Figure 2.

For all $1\leq i\leq\frac{m-1}{2}$ there are two mutually exclusive cases, (a) and (b), represented by the two vertices $x_{i}$ and the two vertices $\overline{x_{i}}$, respectively, in Figure 2.

$\{(ii),(\bar{i}\bar{i})\}\subseteq S$ and $\{(i\bar{i}),(\bar{i}i)\}\cap S=\emptyset$,

$\{(i\bar{i}),(\bar{i}i)\}\subseteq S$ and $\{(ii),(\bar{i}\bar{i})\}\cap S=\emptyset$.

These choices result in $2^{\frac{m-1}{2}}$ valid sets.

As indicated in Figure 2, for each tuple $(ij)$ we call $i$ the row of $(ij)$. For $S$ to be valid, according to Def. 6.6(3), $S$ must contain $|i-\bar{i}|$ elements in row $i$ and according to Def. 6.6(2), $\tau(s)\notin S$ for all $s\in S$.

In particular, $S$ must contain $m-1$ elements in row 1. If $(11)\in S$, then $(1m)\notin S$, because $\tau(11)=(1m)$. Hence there are only two possibilities: (a): $\{(1j)\mid 1\leq j<m\}\subseteq S$ or (b): $\{(1j)\mid 1<j\leq m\}\subseteq S$. By symmetry, for row $m$ we get (a’): $\{(mj)\mid 1\leq j<m\}\subseteq S$ or (b’): $\{(mj)\mid 1<j\leq m\}\subseteq S$. But since $\tau(1m)=(mm)$ and $\tau(m1)=(11)$, the fact $\tau(S)=\iota(S)$ implies that (a) iff (b’) and that (a’) iff (b). We are left with the two possibilities $\big($(a) and (b’)$\big)$ or $\big($(a’) and (b)$\big)$.

Now consider row 2. We have $\tau(21)=(1,m-1)\in S$ and hence $(21)\notin S$. In the same manner we see $(2m)\notin S$. We are left to choose $m-3$ elements from the $m-2$ remaining elements in row 2. The same argument as for row 1 gives two possibilities: (a): $\{(2j)\mid 2\leq j<m-1\}\subseteq S$ or (b): $\{(2j)\mid 2<j\leq m-1\}\subseteq S$. Analogously for row $m-1$ we have (a’): $\{(m-1,j)\mid 2\leq j<m-1\}\subseteq S$ or (b’): $\{(m-1,j)\mid 2<j\leq m-1\}\subseteq S$. With the same reasoning as for the rows $1$ and $m$ we get (a) iff (b’) and that (a’) iff (b). Again we are left with the two possibilities $\big($(a) and (b’)$\big)$ or $\big($(a’) and (b)$\big)$.

Continuing these arguments we end up with $2^{\frac{m-1}{2}}$ possibilities. It is easy to see that each of these possibilities gives a valid set.

The following claim finishes the proof of Lemma 4.4.

All nonzero triple labelings $J$ have the same coefficient of $\mathcal{X}$ in $\mathsf{eval}_{\mathcal{H}}(AJ)$.

Take two nonzero triple labelings $J$ and $J^{\prime}$. According to Proposition 6.7, both sets $J^{(1)}(V^{(3)})$ and ${J^{\prime}}^{(1)}(V^{(3)})$ are valid sets. Because of Lemma 6.9, it suffices to consider only the case where $J^{(1)}(V^{(3)})$ and $J^{\prime(1)}(V^{(3)})$ differ by a single involution $\sigma\colon O_{m}\to O_{m}$, where for some fixed $1\leq i\leq\frac{m-1}{2}$ we have $\sigma(ii)=(i\bar{i})$ and $\sigma(\bar{i}\bar{i})=(\bar{i}i)$, and $\sigma$ is constant on all other pairs.

We analyze the labels that are affected by $\sigma$. We only perform the analysis for one of the two symmetric cases, namely for $\{|ii\rangle,|\bar{i}\bar{i}\rangle\}\subseteq J^{(1)}(V^{(3)})$. Note that this implies

according to Claim 4. We adapt the notation from (6.1) to our special situation and write $t_{000}\coloneqq t_{\bar{i}\bar{i}\bar{i}}$, $t_{001}\coloneqq t_{\bar{i}\bar{i}i}$, $\ldots$, $t_{111}\coloneqq t_{iii}$. Using this notation, ( ♢ ‣ 6.11) reads as follows: $\{t_{110},t_{001}\}\subseteq J(V^{(3)})$. Using Claim 5 we get

Applying $\sigma$ to $J^{(1)}(V^{(3)})$, we can use Claim 4 again to get

Applying Claim 5 and using our short syntax, we get:

We see that exactly the same triples occur in $J(V(\mathcal{H}))$ as in $J^{\prime}(V(\mathcal{H}))$. We focus now on $J^{(1)}$ and $J^{\prime(1)}$ and see that:

This gives exactly two switches of positions in $e^{(1)}=V^{(2)}\mathrel{\dot{\cup}}V^{(3)}\mathrel{\dot{\cup}}\{y^{0}\}$, hence

Analogously we can prove that $\mathsf{eval}_{e^{(k)}}(AJ)=\mathsf{eval}_{e^{(k)}}(AJ^{\prime})$ for all $k\in\{2,3\}$ and therefore $\mathsf{eval}_{\mathcal{H}}(AJ)=\mathsf{eval}_{\mathcal{H}}(AJ^{\prime})$.

References