---
abstract: |
    Understanding the difference between group orbits and their closures is a key difficulty in geometric complexity theory (GCT): While the GCT program is set up to separate certain orbit closures, many beautiful mathematical properties are only known for the group orbits, in particular close relations with symmetry groups and invariant spaces, while the orbit closures seem much more difficult to understand. However, in order to prove lower bounds in algebraic complexity theory, considering group orbits is not enough.

    In this paper we tighten the relationship between the orbit of the power sum polynomial and its closure, so that we can separate this orbit closure from the orbit closure of the product of variables by just considering the symmetry groups of both polynomials and their representation theoretic decomposition coefficients. In a natural way our construction yields a multiplicity obstruction that is neither an occurrence obstruction, nor a so-called vanishing ideal occurrence obstruction. All multiplicity obstructions so far have been of one of these two types. Our paper is the first implementation of the ambitious approach that was originally suggested in the first papers on geometric complexity theory by Mulmuley and Sohoni (SIAM J Comput 2001, 2008): Before our paper, all existence proofs of obstructions only took into account the symmetry group of one of the two polynomials (or tensors) that were to be separated. In our paper the multiplicity obstruction is obtained by comparing the representation theoretic decomposition coefficients of both symmetry groups. Our proof uses a semi-explicit description of the coordinate ring of the orbit closure of the power sum polynomial in terms of Young tableaux, which enables its comparison to the coordinate ring of the orbit.
author:
- 'Christian Ikenmeyer[^1]  and Umangathan Kandasamy[^2]'
date: 'November 10, 2019'
title: 'Implementing geometric complexity theory: On the separation of orbit closures via symmetries'
---

[0.9]{} **Acknowledgements:** This paper was written partially when CI was at the Max Planck Institute for Informatics, at the Max Planck Institute for Software Systems, and at the University of Liverpool. This paper contains results that are present in UK’s master’s thesis at the Universität des Saarlandes.

[0.9]{} **2012 ACM CCS:** Theory of computation $\rightarrow$ Algebraic complexity theory

[0.9]{} **Keywords:** Geometric complexity theory, group orbit, orbit closure, multiplicity obstruction

Motivation: Geometric complexity theory
=======================================

#### Symmetries

The idea of using the symmetries of the determinant ${\textup{det}}_n := \sum_{\pi \in {\mathfrak{S}}_n}{\textup{sgn}}(\pi)\prod_{i=1}^n x_{i,\pi(i)}$ and the permanent ${\textup{per}}_m := \sum_{\pi \in {\mathfrak{S}}_m} \prod_{i=1}^m x_{i,\pi(i)}$ to separate algebraic complexity classes was pioneered by Mulmuley and Sohoni in 2001 [@MS:01]. This approach is based on the observation that ${\textup{det}}_n$ and ${\textup{per}}_m$ are both characterized by their respective symmetry groups. For example, consider homogeneous degree $n$ polynomials in $n^2$ variables $x_{1,1},\ldots,x_{n,n}$. Let $X$ denote the $n \times n$ matrix whose entry in row $i$ and column $j$ is $x_{i,j}$. Then ${\textup{det}}(X)={\textup{det}}_n$. Now, for matrices $A,B \in {\textup{SL}}_n({\mathbb{C}})$ the entries of the matrix $AXB$ are homogeneous linear polynomials in the $n^2$ variables. The crucial fact is that every homogeneous degree $n$ polynomial $q$ in $n^2$ variables that satisfies $q(AXB)=q(X)$ equals $\alpha \cdot {\textup{det}}_n$ for some scalar $\alpha \in {\mathbb{C}}$. This means that ${\textup{det}}_n$ is *characterized by its symmetries*. For the permanent polynomial, an analogous statement holds, and also for many other structurally simpler polynomials, for example for the power sum polynomial $x_1^D+\cdots+x_m^D$ and for the product of variables $x_1 x_2 \cdots x_D$, see [@Ike:19].

#### Algebraic complexity theory

An *affine projection* of a polynomial is its evaluation at a point whose coordinates are given by affine linear polynomials, e.g., $(x_1+x_2+1)^2 = x_1^2 + 2 x_1 x_2 + x_2^2 + 2 x_1 + 2 x_2 + 1$ is an affine projection of $x_1^2$. Kayal proved that it is ${\textup{\textsf{NP}}}$-hard to decide whether a polynomial is an affine projection of another polynomial [@Kay:12]. Valiant proved [@Val:79b] that every polynomial $p$ is an affine projection of some ${\textup{det}}_n$ for $n$ large enough. The smallest $n$ for which this is possible is called the *determinantal complexity* ${\textup{\textsf{dc}}}(p)$. The class of sequences of polynomials $(p_m)$ whose sequence of natural numbers ${\textup{\textsf{dc}}}(p_m)$ is polynomially bounded is called ${\ensuremath{\textup{\textsf{VP}}_{\textsf{s}}}}$. For the permanent we can define the *permanental complexity* ${\textup{\textsf{pc}}}(p)$ in a completely analogous manner: ${\textup{\textsf{pc}}}(p)$ is the smallest $n$ such that $p$ is an affine projection of ${\textup{per}}_n$. The class of sequences of polynomials $(p_m)$ whose ${\textup{\textsf{pc}}}(p_m)$ is polynomially bounded is called ${\textup{\textsf{VNP}}}$. Since ${\textup{\textsf{pc}}}({\textup{det}}_n)$ is polynomially bounded, ${\ensuremath{\textup{\textsf{VP}}_{\textsf{s}}}}\subseteq {\textup{\textsf{VNP}}}$. Valiant’s flagship conjecture in algebraic complexity theory, which is also known as the *determinant versus permament* conjecture can be succinctly phrased as ${\ensuremath{\textup{\textsf{VP}}_{\textsf{s}}}}\neq {\textup{\textsf{VNP}}}$. This is equivalent to conjecturing that ${\textup{\textsf{dc}}}({\textup{per}}_m)$ grows superpolynomially fast.

#### Homogeneous projections and endomorphism orbits

It will be beneficial to phrase Valiant’s conjecture in a homogeneous setting: A *homogeneous projection* of a homogeneous polynomial (i.e., all monomials have the same total degree) is its evaluation at a point whose coordinates are given by homogeneous linear polynomials. The set of all homogeneous projections of ${\textup{det}}_n$ to polynomials in the variables $x_1,\ldots,x_N$ can then be written as $\{{\textup{det}}_n(\ell_1,\ldots,\ell_{n^2}) \mid \text{$\ell_i$ is a homogeneous linear polynomial in $x_1,\ldots,x_N$}\}$. Note that we put the $n \times n = n^2$ inputs of the determinant in a linear order. The polynomial function $(x_{1,1},\ldots,x_{n,n}) \mapsto {\textup{det}}_n(\ell_1,\ldots,\ell_{n^2})$ equals the composition ${\textup{det}}_n \circ A$, where $A$ is the linear map $(x_{1,1},\ldots,x_{n,n}) \mapsto (\ell_1,\ldots,\ell_{n^2})$. As it is common in representation theory, we write $A \cdot {\textup{det}}_n$ or just $A {\textup{det}}_n$ for ${\textup{det}}_n \circ A$. The *endomorphism orbit* ${\textup{End}}_{n^2}{\textup{det}}_n$ is defined as $\{A {\textup{det}}_n \mid A \in {\mathbb{C}}^{n^2 \times n^2}\}$, which is the set of all homogeneous projections of ${\textup{det}}_n$ to polynomials in at most $n^2$ variables. Since all polynomials in $A {\textup{det}}_n$ are homogeneous of degree $n$, we have ${\textup{per}}_m \notin {\textup{End}}_{n^2} {\textup{det}}_n$ for any $m \neq n$. This slight technicality is treated by a procedure called *padding*: For fixed $m$, $n$ with $m < n$, define the *padded permanent* ${\textup{per}}_{m,n} := (x_{n,n})^{n-m}\cdot {\textup{per}}_m$. Let ${\textup{\textsf{dc}}}'({\textup{per}}_{m,n})$ denote the smallest $n$ such that ${\textup{per}}_{m,n} \in {\textup{End}}_{n^2} {\textup{det}}_n$. A short calculation shows that Valiant’s conjecture is equivalent to the conjecture that ${\textup{\textsf{dc}}}'({\textup{per}}_m)$ grows superpolynomially.

#### Group orbits

It turns out that if we restrict ${\textup{End}}_{n^2} {\textup{det}}_n$ to only the points $A{\textup{det}}_n$ for which $A$ is invertible, we get the much simpler *group orbit* ${\textup{GL}}_{n^2}{\textup{det}}_n := \{g {\textup{det}}_n \mid g \in {\textup{GL}}_{n^2}\} \subseteq {\textup{End}}_{n^2} {\textup{det}}_n$. The group orbit of the determinant consists of “determinants in disguise”, i.e., determinants after a base change. The question whether a polynomial $p$ lies in ${\textup{GL}}_{n^2}{\textup{det}}_n$ can be answered in randomized polynomial time [@Kay:12]. Finding $g \in {\textup{GL}}_{n^2}$ such that $p = g {\textup{det}}_n$ is called the *reconstruction* problem, which is the focus of several recent papers, where the determinant is replaced with other algebraic computational models, see e.g.[@GKQ:14], [@KS:19], [@KNS:19].

#### Representation theory

Let $H_{{\textup{det}}_n}\subseteq {\textup{GL}}_{n^2}$ denote the symmetry group of ${\textup{det}}_n$. From the viewpoint of algebraic geometry, the set ${\textup{GL}}_{n^2}{\textup{det}}_n$ is an affine variety ([@BLMW:11 Sec 4.2], [@Mat:60 Cor., p. 206]) and a homogeneous space that is isomorphic to the quotient ${\textup{GL}}_{n^2}/H_{{\textup{det}}_n}$. It is crucial to note here that the group $H_{{\textup{det}}_n}$ does not carry any information about the fact that we study a space of polynomials! In this way, we study the orbit ${\textup{GL}}_{n^2}{\textup{det}}_n$ independently of its embedding into the space of polynomials. This gives a particularly beautiful description of its coordinate ring via invariant theory: $${\mathbb{C}}[{\textup{GL}}_{n^2}{\textup{det}}_n] = {\mathbb{C}}[{\textup{GL}}_{n^2}]^{H_{{\textup{det}}_n}},$$ where ${\mathbb{C}}[{\textup{GL}}_{n^2}]^{H_{det_n}}$ is the set of regular $H_{{\textup{det}}_n}$-invariant functions on the variety ${\textup{GL}}_{n^2}$ [@BLMW:11 (5.2.6)]. The coordinate ring of ${\textup{GL}}_{n^2}$ has classically been studied: It is a ${\textup{GL}}_{n^2} \times {\textup{GL}}_{n^2}$-representation whose representation theoretic decomposition is multiplicity free: $$\label{eq:algpeterweyl}
{\mathbb{C}}[{\textup{GL}}_{n^2}] = \bigoplus_{{\lambda}}\{{\lambda}\} \otimes \{{\lambda}^*\},$$ where ${\lambda}$ runs over all nondecreasing lists of $n^2$ integers and $\{{\lambda}\}$ denotes the irreducible rational representation of ${\textup{GL}}_{n^2}$ corresponding to ${\lambda}$ (see e.g. Section \[sec:prelrepr\] or the textbooks [@FH:91; @MaD:95; @fult:97] for more information). Eq.  is known as the algebraic Peter-Weyl theorem. It implies that the multiplicity of ${\lambda}^*$ in ${\mathbb{C}}[{\textup{GL}}_{n^2}{\textup{det}}_n]$ equals the dimension of the $H_{{\textup{det}}_n}$-invariant space $\{{\lambda}\}^{H_{{\textup{det}}_n}}$. This coefficient $\dim \{{\lambda}\}^{H_{{\textup{det}}_n}}$ is known as the symmetric rectangular Kronecker coefficient and has been the object of several papers [@BOR:09; @Man:11; @IP:17]. Even though Kronecker coefficients are mysterious, many properties are known (see e.g. [@CDW:12; @Bla:12; @SS:16; @IMW:17; @Liu:17; @BCMW:17] for some recent advances), and character theory is available to compute their values in many cases, see e.g. [@ike:12b Appendix]. A better understanding of Kronecker coefficients could lead to a better understanding of ${\textup{GL}}_{n^2}{\textup{det}}_n$, which could eventually help to separate points from ${\textup{End}}_{n^2}{\textup{det}}_n$.

If we replace ${\textup{det}}_n$ by other polynomials, we get an analogous theory that is often equally beautiful. The power sum polynomial and the product $x_1 \cdots x_D$ will be of particular interest in this paper. The corresponding coefficients are not Kronecker coefficients, but plethysm coefficients and related coefficients that appear in algebraic combinatorics, see Proposition \[pro:gctandsymmetries\] for the power sum and for the product of variables.

#### Closures

As we just have seen, group orbits have several desirable properties and can be understood directly via symmetry groups and algebraic combinatorics. But endomorphism orbits do not behave that nicely. In general, ${\textup{End}}_{n^2}{\textup{det}}_n$ is not a variety. In order to enable the study of ${\textup{End}}_{n^2}{\textup{det}}_n$ with methods from algebraic geometry, we go to the closure (Euclidean closure and Zariski closure coincide here by general principles, see [@Mum:95 §2.C]): $\overline{{\textup{End}}_{n^2}{\textup{det}}_n}$, which coincides with the group orbit closure $\overline{{\textup{GL}}_{n^2}{\textup{det}}_n}$, see e.g. [@BI:18 Sec. 3.5]. Hence we have a chain of inclusions ${\textup{GL}}_{n^2}{\textup{det}}_n \subseteq {\textup{End}}_{n^2}{\textup{det}}_n \subseteq \overline{{\textup{GL}}_{n^2}{\textup{det}}_n}$. The border determinantal complexity ${\underline{\textup{\textsf{dc}}}}({\textup{per}}_m)$ is defined as the smallest $n$ such that ${\textup{per}}_{m,n} \in \overline{{\textup{GL}}_{n^2}{\textup{det}}_n}$. Mulmuley and Sohoni’s conjecture (closely related to Bürgisser’s conjecture [@Bue:01 hypothesis (7)]) is that ${\underline{\textup{\textsf{dc}}}}({\textup{per}}_m)$ grows superpolynomially. Since ${\underline{\textup{\textsf{dc}}}}({\textup{per}}_m) \leq {\textup{\textsf{dc}}}'({\textup{per}}_m)$, this would imply Valiant’s conjecture. Mulmuley and Sohoni’s conjecture can be attacked by representation theoretic multiplicities (see Section \[sec:preliminaries\]) as follows. If we assume for the sake of contradiction that $\overline{{\textup{GL}}_{n^2}{\textup{per}}_{m,n}} \subseteq \overline{{\textup{GL}}_{n^2}{\textup{det}}_n}$, then by Schur’s lemma (see [@FH:91 Lemma 1.7]) the multiplicities satisfy ${\textup{mult}}_{\lambda}{\mathbb{C}}[\overline{{\textup{GL}}_{n^2}{\textup{per}}_{m,n}}] \leq {\textup{mult}}_{\lambda}{\mathbb{C}}[\overline{{\textup{GL}}_{n^2}{\textup{det}}_n}]$. Thus, if there exists $({\lambda},d)$ that satisfies $$\label{eq:ineq}
{\textup{mult}}_{\lambda}{\mathbb{C}}[\overline{{\textup{GL}}_{n^2}{\textup{per}}_{m,n}}]_d > {\textup{mult}}_{\lambda}{\mathbb{C}}[\overline{{\textup{GL}}_{n^2}{\textup{det}}_n}]_d,$$ then ${\underline{\textup{\textsf{dc}}}}(m)>n$. Such a pair $({\lambda},d)$ is called a *multiplicity obstruction*.

#### Orbits vs orbit closures

The algebraic geometry of $\overline{{\textup{GL}}_{n^2}{\textup{det}}_n}$ and the representation theory of its coordinate ring are rather difficult to understand, see e.g. [@Kum:15; @BHI:17]. But the close relationship between orbit and orbit closure gives hope that results can be transferred from the orbit to the closure. Indeed, ${\mathbb{C}}[\overline{{\textup{GL}}_{n^2}{\textup{det}}_n}] \subseteq {\mathbb{C}}[{\textup{GL}}_{n^2}{\textup{det}}_n]$ is a subalgebra, and hence we have ${\textup{mult}}_{\lambda}{\mathbb{C}}[{\textup{GL}}_{n^2} {\textup{det}}_n] \geq {\textup{mult}}_{\lambda}{\mathbb{C}}[\overline{{\textup{GL}}_{n^2} {\textup{det}}_n}]$. Getting lower bounds on multiplicities in ${\mathbb{C}}[\overline{{\textup{GL}}_{n^2} {\textup{det}}_n}]$ seems much harder. For example, the result in [@Kum:15] holds for those $n$ for which the Alon-Tarsi property holds, in particular if $n$ is an odd prime number $\pm 1$, see Section \[sec:notoccobsorvanidoccobs\]. The occurrence results in [@BIP:19] use explicit constructions using Young symmetrizers, which is a laborious process. But as a first step towards lower bounds on ${\textup{mult}}_{\lambda}{\mathbb{C}}[\overline{{\textup{GL}}_{n^2} {\textup{det}}_n}]$, [@BI:17] proved that ${\textup{GL}}_{n^2} {\textup{det}}_n$ is open in its closure and that the ring ${\mathbb{C}}[{\textup{GL}}_{n^2} {\textup{det}}_n]$ is a localization of ${\mathbb{C}}[\overline{{\textup{GL}}_{n^2} {\textup{det}}_n}]$.

Our contribution
================

In this paper we tighten the results from [@BI:17] in the case of the power sum polynomial. For $m \geq D$ let $p := x_1^D + x_2^D + \cdots + x_m^D$ and let $q := x_1 x_2 \cdots x_D$. Let $G := {\textup{GL}}_{m}$. For $m=D$ we separate the two families of orbit closures $\overline {Gp} \not\subseteq \overline {Gq}$ of polynomials $p$ and $q$ using multiplicity obstructions ${\lambda}$, i.e., ${\textup{mult}}_{\lambda}{\mathbb{C}}[\overline{Gp}]>{\textup{mult}}_{\lambda}{\mathbb{C}}[\overline{Gq}]$. Our key contribution is a proof method that for the first time implements closely the strategy in [@MS:01; @MS:08]: Both the lower bound on ${\textup{mult}}_{\lambda}{\mathbb{C}}[\overline{Gp}]$ and the upper bound on ${\textup{mult}}_{\lambda}{\mathbb{C}}[\overline{Gq}]$ are obtained directly from the symmetry groups of $p$ and $q$ and the dimension of the spaces of $H_p$- and $H_q$-invariants in irreducible ${\textup{GL}}_m$-representations. This is the result of our tightening of the relationship between ${\textup{mult}}_{\lambda}{\mathbb{C}}[Gp]$ and ${\textup{mult}}_{\lambda}{\mathbb{C}}[\overline{Gp}]$, see Theorem \[thm:proofofconcept\].

Before our paper, all existence proofs of multiplicity obstructions $\overline{Gp} \not\subseteq \overline{Gq}$ for any $p$ and $q$ required to explicitly construct (with multilinear algebra) copies of irreducible representations in ${\textup{mult}}_{\lambda}{\mathbb{C}}[\overline{Gp}]$. These papers only took into account the symmetry group of $q$ instead of both symmetry groups, see [@BI:11; @BI:13; @GIP:17; @DIP:19].

In particular, we prove $\overline{Gp}\not\subseteq\overline{Gq}$ by explicitly constructing a multiplicity obstruction ${\lambda}$ in Theorem \[thm:proofofconcept\] using the symmetry groups of $p$ and $q$ and their representation theoretic decomposition coefficients, but we do *not* construct an explicit function that separates the two orbit closures! Since our obstruction is neither an occurrence obstruction, nor a vanishing ideal occurrence obstruction (see next paragraph), the separating function is quite nontrivial to recover. This is a step in the right direction, since the explicit construction of separating functions for Valiant’s conjecture could turn out to be problematic because of the algebraic natural proofs barrier [@FSV:17; @GKSS:17; @BIJL:18].

Occurrence obstructions and vanishing ideal occurrence obstructions {#occurrence-obstructions-and-vanishing-ideal-occurrence-obstructions .unnumbered}
-------------------------------------------------------------------

The classical approach of Mulmuley and Sohoni [@MS:01; @MS:08] conjectures the existence of so-called *occurrence obstructions*, which are types ${\lambda}$ for which the stronger property ${\textup{mult}}_{\lambda}{\mathbb{C}}[\overline{G{\textup{per}}_{m,n}}] > 0 = {\textup{mult}}_{\lambda}{\mathbb{C}}[\overline{G{\textup{det}}_n}]$ holds. These obstructions are not enough to prove strong complexity lower bounds (at least not in the classical setting of ${\textup{det}}_n$ vs ${\textup{per}}_{m,n}$), see [@IP:17; @BIP:19]. Recently it was shown that there are settings in which multiplicity obstructions are provably stronger than just occurrence obstructions [@DIP:19]. The types ${\lambda}$ that are used in [@DIP:19] occur in the vanishing ideal of one orbit closure, but not in the vanishing ideal of the other, hence we call them *vanishing ideal occurrence obstructions*. How useful vanishing ideal occurrence obstructions are for separating orbit closures is an open question, but it seems unlikely that strong complexity lower bounds can be proved by using only vanishing ideal occurrence obstructions.

The techniques that we develop in this paper study multiplicities and go beyond just occurrence obstructions and vanishing ideal occurrence obstructions. Theorem \[thm:proofofconcept\] gives the first family of multiplicity obstructions that are neither occurrence obstructions nor vanishing ideal occurrence obstructions, see Proposition \[pro:alontarsi\]. To prove this fact, we make use of Drisko’s and Glynn’s progress on the Alon-Tarsi conjecture about the difference between the number of even and odd Latin squares of a given size.

The toy setting as a starting point {#the-toy-setting-as-a-starting-point .unnumbered}
-----------------------------------

Our separation $\overline{Gp}\not\subseteq\overline{Gq}$ with $p=x_1^D+\cdots+x_m^D$ and $q=x_1\cdots x_D$ is clearly a toy problem, but even though its complexity theoretic relevance is quite limited (multivariate factorization of a power sum) it shares all (as far as we know) crucial geometric and representation theoretic features with the determinant versus permanent problem: Both problems are problems about orbit closures of polynomials, and the group action is the same canonical action. The only difference between the two setups are the specific polynomials $p$ and $q$. Even though $p$ and $q$ do not share the complexity theoretic properties of the determinant and the permanent, $p$ and $q$ are characterized by their symmetry groups and are stable points (see [@BI:17]). Therefore this setup can be seen a starting point from which $p$ and $q$ could now be gradually adjusted until some orbit closure separations can be obtained that give lower bounds in algebraic complexity theory.

Structure of the paper {#structure-of-the-paper .unnumbered}
----------------------

In Section \[sec:preliminaries\] we start with preliminaries that are necessary to state our results precisely in Section \[sec:resultdetails\]. The main connection between representation theory and tableau combinatorics is discussed in Sections \[sec:prelrepr\]–\[sec:hworbitclosure\]. Section \[sec:threetableaux\] proves a technical result about plethysm coefficients that was postponed from Section \[sec:resultdetails\]. Section \[sec:proofmain\] proves the main technical theorem under the assumption that the so-called *Tableau Lifting Theorem* \[thm:prolongation\] is true. The rest of the paper (Sections \[EVENsec:hypergraphsevenD\] to \[sec:psipropertiesDodd\]) is then used to prove the Tableau Lifting Theorem using elementary but subtle Young tableau combinatorics. Even and odd degrees $D$ are treated mostly independently, where the odd degree case is much more involved.

Preliminaries {#sec:preliminaries}
=============

A *partition* ${\lambda}$ is a nonincreasing finite sequence of natural numbers $({\lambda}_1,{\lambda}_2,\ldots)$. We identify a partition with its *Young diagram*, which is a top-left aligned array of boxes with ${\lambda}_i$ boxes in row $i$. For example, the Young diagram for ${\lambda}=(4,3,1)$ is $\tiny\yng(4,3,1)$. The *length* $\ell({\lambda})$ is the number of rows in the Young diagram of ${\lambda}$, formally $\ell({\lambda})=\max\{i \mid {\lambda}_i>0\}$. The *number of boxes* of ${\lambda}$ is defined as $|{\lambda}|:=\sum_{i\in{\mathbb{N}}} {\lambda}_i$. We also define $|\varrho|:=\sum_{i\in{\mathbb{N}}} \varrho_i$ in the case where $\varrho$ is not a partition. The *transpose* ${\lambda}^t$ of a partition ${\lambda}$ is the partition corresponding to the Young diagram that is the reflection of ${\lambda}$ at the main diagonal, e.g., $(4,3,1)^t = (3,2,2,1)$. The entries of ${\lambda}^t$ are the column lengths of ${\lambda}$. For a partition of length $\leq m$ and $\delta$ many boxes, we write ${\lambda}\vdash_m \delta$. For two partitions ${\lambda}$ and $\mu$ we define their sum ${\lambda}+\mu$ in a row-wise fashion: $({\lambda}+\mu)_i:={\lambda}_i+\mu_i$. For natural numbers $a,b$ let $a \times b$ denote the partition that corresponds to the rectangular Young diagram with $a$ rows and $b$ columns, i.e., $a \times b := (b,b,\ldots,b)$.

Fix $m \in {\mathbb{N}}$. For a partition ${\lambda}\vdash_m \delta$ we write $\{{\lambda}\}$ to denote the irreducible ${\textup{GL}}_m$-representation of type ${\lambda}$. These $\{{\lambda}\}$ form a pairwise non-isomorphic list of irreducible polynomial ${\textup{GL}}_m$-representations, see [@fult:97]. The dual ($=$contragredient) representation of $\{{\lambda}\}$ is denoted by $\{{\lambda}^*\}$. Since $G$ is a reductive group, every finite dimensional $G$-representation ${\mathscr{V}}$ can be decomposed into a direct sum of irreducible $G$-representations, and we write ${\textup{mult}}_{\lambda}{\mathscr{V}}$ for the multiplicity of $\{{\lambda}\}$ in such a decomposition (although the decomposition might not be unique, the multiplicity is the same in any decomposition).

A *tableau of shape* $\lambda$ over some finite *alphabet* $\mathcal{A}$ is a mapping $\lambda \rightarrow \mathcal{A}$ of boxes to elements in $\mathcal{A}$. For example a tableau of shape $(4,3,1)$ over the alphabet $\mathbb{N}$ is given by $\Yvcentermath1\tiny\young(1322,232,1)$. For a tableau $T$ let ${\textup{\textsf{sh}}}(T):= \lambda$ denote its *shape*, i.e., its vector of row lengths. For a tableau $T$ of shape $\lambda \vdash_m \delta$ over the alphabet $\{1,\dots,m\}$ we define its *content* to be the vector $\varrho \in (\mathbb{N}_{\geq 0})^m$ where $\varrho_i$ counts the number of occurrences of $i$ in $T$. For example, the tableau $\Yvcentermath1\tiny\young(1322,232,1)$ has content $(2,4,2)$. The *sorted content* of a tableau is the partition obtained by sorting the entries in the content in a decreasing order, e.g. $(4,2,2)$ in the preceding example. For two tableaux $T$ and $S$ we define their *concatenation* $T+S$ by concatenating rows. The resulting tableau $T+S$ has shape ${\textup{\textsf{sh}}}(T)+{\textup{\textsf{sh}}}(S)$. For example, $\Yvcentermath1\tiny\young(1111,2222,3333) + \Yvcentermath1\tiny\young(444,55,6) = \Yvcentermath1\tiny\young(1111444,222255,33336)$. A tableau with entries from $\mathbb{N}$ is called *semistandard* if the entries of each row are nondecreasing from left to right and the entries of each column are strictly increasing from top to bottom. A semistandard tableau of shape ${\lambda}$ is called *standard* if every number $1,\ldots,|{\lambda}|$ appears exactly once. A column of a tableau $T$ is called *regular* if it does not have a repeated entry. A tableau $T$ is called *regular* if each of its columns is regular. A tableau $L$ is called *duplex* if each column in $L$ appears an even number of times. For example, $L={\Yvcentermath1\tiny\young(11113344,2222,3344)}$ is duplex, while $L={\Yvcentermath1\tiny\young(11112344,2223,3344)}$ is not duplex. Duplex tableaux are the main idea behind the construction in [@bci:10], see also [@ike:12b Sec. 6.2].

Let ${\textup{Poly}}^D {\mathbb{C}}^m$ denote the vector space of homogeneous degree $D$ polynomials in $m$ variables. Let $G := {\textup{GL}}_m$. The group $G$ acts on ${\textup{Poly}}^D {\mathbb{C}}^m$ via $(gp)(x) := p(g^t x)$ for all $g \in G$, $p \in {\textup{Poly}}^D {\mathbb{C}}^m$, $x \in {\mathbb{C}}^m$, where the transpose makes this a left action. We consider the power sum polynomial $p := x_1^D + \cdots + x_m^D \in {\textup{Poly}}^D {\mathbb{C}}^m$. Clearly $p$ is fixed by permuting variables and by rescaling any variable by $D$th roots of unity. For $D\geq 3$ these group elements generate the whole stabilizer of $p$, see e.g. [@CKW:10]. Let $H := {\text{stab\,}}p = {\mathbb{Z}}_D^m \rtimes {\mathfrak{S}}_m \subseteq G$ denote the stabilizer of $p$. Let $q := x_1 \cdots x_D$. Clearly $q$ is fixed under permuting the variables and under rescaling each variable by a scalar $\alpha_i$ such that their product $\prod_{i=1}^D \alpha_i$ equals 1. These elements generate the stabilizer of $q$, see e.g. [@Ike:19 Prop. 3.1].

Considering ${\textup{Poly}}^D {\mathbb{C}}^m$ as a vector space with a $G$-action, let ${\mathbb{C}}[{\textup{Poly}}^D {\mathbb{C}}^m]_d$ be the vector space of homogeneous degree $d$ polynomials on ${\textup{Poly}}^D {\mathbb{C}}^m$. In a natural way, ${\mathbb{C}}[{\textup{Poly}}^D {\mathbb{C}}^m]_d$ is a $G$-representation: $(gf)(q) := f(g^{-1} q)$ for all $g \in G$, $f \in {\mathbb{C}}[{\textup{Poly}}^D {\mathbb{C}}^m]_d$, $q \in {\textup{Poly}}^D {\mathbb{C}}^m$. The multiplicity ${\textup{mult}}_{\nu^*} {\mathbb{C}}[{\textup{Poly}}^D {\mathbb{C}}^m]_d$ is called the *plethysm coefficient*, denoted by $a_\nu(d,D)$. Note that it does not depend on $m$ for $m \geq \ell({\lambda})$, see e.g. [@ike:12b Sec. 4.3]. For the empty partition $(0)$ we define $a_{(0)}(0,i)=1$. Whether or not the plethysm coefficient has a nice combinatorial description is an open research question in algebraic combinatorics, see Problem 9 in [@sta:00]. Among computer scientists, this question is commonly phrased as whether or not the map $(\nu,d,D)\mapsto a_\nu(d,D)$ is in the complexity class $\#{\textup{\textsf{P}}}$.

Given two irreducible $G$-representations $\{\mu\}$ and $\{\nu\}$, their tensor product $\{\mu\}\otimes\{\nu\}$ is a $G \times G$-representation. Embedding $G \hookrightarrow G \times G$ diagonally via $g \mapsto (g,g)$ the tensor product $\{\mu\}\otimes\{\nu\}$ becomes a $G$-representation that decomposes into irreducibles. The multiplicity ${\textup{mult}}_{\lambda}\{\mu\}\otimes\{\nu\}$ is called the *Littlewood-Richardson coefficient* $c^{\lambda}_{\mu,\nu}$. This quantity has numerous beautiful combinatorial interpretations, see e.g. [@bz:92], [@fult:97 Sec. 5], [@knta:99], [@buc:00], [@ike:12b Sec. 10] and many more. In particular, the map $({\lambda},\mu,\nu)\mapsto c^{\lambda}_{\mu,\nu}$ is in the complexity class $\#{\textup{\textsf{P}}}$. Even though the exact computation of $c^{\lambda}_{\mu,\nu}$ is ${\textup{\textsf{NP}}}$-hard [@nara:06], deciding its positivity is possible in polynomial time [@DLM:06], [@MNS:12], [@BI:13LRC]. Completely analogous properties hold when we take tensor products of polynomially many irreducible $G$-representations $\{\mu^1\}\otimes \cdots \otimes \{\mu^d\}$ and embed $G \hookrightarrow G \times G \times \cdots \times G$. The corresponding coefficient is called the *multi-Littlewood-Richardson coefficient* $c_{\mu^1,\mu^2,\ldots,\mu^d}^{\lambda}$.

For a partition $\varrho \vdash_m d$ the *frequency notation* $\hat\varrho \in {\mathbb{N}}^m$ is defined via $\hat\varrho_i := |\{j \mid \varrho_j = i\}|$. For example, the frequency notation of $\varrho=(3,3,2,0)$ is $\hat\varrho=(0,1,2,0)$. We observe that $|\varrho|=\sum_i i \hat\varrho_i$.

Result details {#sec:resultdetails}
==============

The following Proposition \[pro:gctandsymmetries\] writes the multiplicity ${\textup{mult}}_{{\lambda}^*} {\mathbb{C}}[G p]$ as a nonnegative sum of products of multi-Littlewood-Richardson coefficients and plethysm coefficients.

\[pro:gctandsymmetries\] Let ${\lambda}\vdash_m dD$. Define $$b({\lambda},\varrho,D,d) := \sum_{\mu^1,\mu^2,\ldots,\mu^d \atop \mu^i \vdash D i \hat\varrho_i} c_{\mu^1,\mu^2,\ldots,\mu^d}^{\lambda}\prod_{i=1}^d a_{\mu^i}(\hat\varrho_i,iD).$$ Then $${\textup{mult}}_{{\lambda}^*} {\mathbb{C}}[G p] = \sum_{\varrho\vdash_m d} b({\lambda},\varrho,D,d).$$

The proof technique is based on the technique in [@BI:11]. The proof is postponed to Section \[sec:gctandsymmetries\].

We remark that if Problem 9 in [@sta:00] is resolved positively, then Proposition \[pro:gctandsymmetries\] implies that the multiplicity ${\textup{mult}}_{{\lambda}^*}{\mathbb{C}}[Gp]$ has a combinatorial description, i.e., the map $({\lambda},m,d,D)\mapsto {\textup{mult}}_{{\lambda}^*}{\mathbb{C}}[Gp]$ is in $\#{\textup{\textsf{P}}}$. The same holds also for its summands $b(\lambda,\varrho,D,d)$. It is known that ${\textup{mult}}_{{\lambda}^*}{\mathbb{C}}[Gq] = a_{\lambda}(D,d)$ (see e.g. [@Lan:17 Sec. 9.2.3]), so the same holds for ${\textup{mult}}_{{\lambda}^*}{\mathbb{C}}[Gq]$.

Our main technical theorem that enables us to find obstructions is the following.

\[thm:main\] Let $m, d, D \in {\mathbb{N}}$. If $D$ is odd, we assume that ${{2(D-1)}\choose{D-1}} \geq 2(m-1)$. Let ${\lambda}\vdash_m dD$. For each $\varrho\vdash_m d$ define the number $e_\varrho$ as follows:

-   if $D$ is even, let $e_\varrho := \sum_{i=1}^{m} \lceil \frac{\varrho_i}{D-2} \rceil$.

-   if $D$ is odd, let $e_\varrho := \sum_{i=1}^{m} 2\lceil \frac{\varrho_i}{2(D-2)} \rceil$.

Let $\Xi$ be a subset of the set of all partitions $\varrho\vdash_m d$. Let $e_\Xi := \max\{e_\varrho \mid \varrho \in \Xi\}$. Then $${\textup{mult}}_{({\lambda}+(m \times e_\Xi D))^*} {\mathbb{C}}[\overline{Gp}] \geq \sum_{\varrho \in \Xi} b({\lambda},\varrho,D,d).$$

The proof of Theorem \[thm:main\] is postponed to Section \[sec:proofmain\].

Explicit obstructions via symmetries {#explicit-obstructions-via-symmetries .unnumbered}
------------------------------------

We use Theorem \[thm:main\] as follows to construct obstructions.

\[thm:proofofconcept\] Let $m=D\geq 4$ be even. Let $d=2$. Let ${\lambda}= (2m)$ and let $\nu = (2m)+(m\times 2m)$. Let $p:=x_1^m+\cdots+x_m^m$ and $q := x_1 x_2 \cdots x_m$. Let $\Xi = \{(2),(1,1)\}$. In the notation of Theorem \[thm:main\] we have $e_{(2)}=1$ and $e_{(1,1)}=2$, thus $e_\Xi = 2$. Note that $\nu = {\lambda}+ (m \times e_\Xi D)$. We have

-   $b((2m),(2),m,2)=1$ and $b((2m),(1,1),m,2)=1$ and hence with Theorem \[thm:main\] we have ${\textup{mult}}_{\nu^*} {\mathbb{C}}[\overline{Gp}] \geq 2$.

-   $1 \geq {\textup{mult}}_{\nu^*} {\mathbb{C}}[G q] \geq {\textup{mult}}_{\nu^*} {\mathbb{C}}[\overline{G q}]$.

In particular ${\textup{mult}}_{\nu^*} {\mathbb{C}}[\overline{Gp}] \geq 2 > 1 \geq {\textup{mult}}_{\nu^*} {\mathbb{C}}[\overline{Gq}]$ and hence $\nu$ is a multiplicity obstruction that proves the separation $\overline{Gp}\not\subseteq\overline{Gq}$.

We use the following well-known properties about Littlewood-Richardson coefficients (see e.g. [@fult:97 Ch. 5]).\
$\bullet$ The Littlewood-Richardson coefficient is symmetric in the subscript parameters: $c_{\mu,\nu}^{\lambda}= c_{\nu,\mu}^{\lambda}$.\
$\bullet$ $c_{\mu,(0)}^{\lambda}$ equals 1 iff $\mu={\lambda}$, otherwise $c_{\mu,(0)}^{\lambda}=0$.

Recall that $\hat\varrho$ is the frequency notation of $\varrho$. We calculate $$\begin{aligned}
b({\lambda},(2),m,2) &=& \sum_{\mu^1,\mu^2 \atop \mu^i \vdash m i \widehat{(2)}_i} c_{\mu^1,\mu^2}^{\lambda}\prod_{i=1}^2 a_{\mu^i}(\widehat{(2)}_i,im) \\
&=&
\sum_{\mu^2 \vdash 2D} c_{(0),\mu^2}^{\lambda}\cdot
a_{(0)}(\widehat{(2)}_1,m) \cdot a_{\mu^2}(\widehat{(2)}_2,2m)
\underbrace{=}_{c_{(0),\mu}^{\lambda}= \delta_{\mu,{\lambda}}}
a_{(0)}(\widehat{(2)}_1,m) \cdot a_{{\lambda}}(\widehat{(2)}_2,2m) \\
&=&
a_{(0)}(0,m) \cdot a_{(2m)}(1,2m) = 1 \cdot 1 = 1.\end{aligned}$$ Here we used the trivial fact that $a_{(\delta)}(1,\delta)=1$ for all $\delta$. $$\begin{aligned}
b({\lambda},(1,1),m,2) &=& \sum_{\mu^1,\mu^2 \atop \mu^i \vdash m i \widehat{(1,1)}_i} c_{\mu^1,\mu^2}^{\lambda}\prod_{i=1}^2 a_{\mu^i}(\widehat{(1,1)}_i,im) \\
&=&
\sum_{\mu^1 \vdash m} c_{\mu^1,(0)}^{\lambda}\cdot
a_{\mu^1}(\widehat{(1,1)}_1,m) \cdot a_{(0)}(\widehat{(1,1)}_2,2m)
\underbrace{=}_{c_{\mu,(0)}^{\lambda}= \delta_{\mu,{\lambda}}}
a_{{\lambda}}(\widehat{(1,1)}_1,m) \cdot a_{(0)}(\widehat{(1,1)}_2,2m) \\
&=&
a_{(2m)}(2,m) \cdot a_{(0)}(0,2m) = 1 \cdot 1 = 1.\end{aligned}$$ Here we used the classical fact that $a_{{\lambda}}(2,m)=1$ if ${\lambda}$ has $2m$ boxes and at most 2 rows and both rows have even length (see the formula for $h_2 \circ h_n$ in [@MaD:95 I.8, Exa. 9(a), p. 140]). This proves the first part of the claim.

${\mathbb{C}}[\overline{Gq}] \subseteq {\mathbb{C}}[Gq]$ is a subalgebra, so ${\textup{mult}}_{\nu^*} {\mathbb{C}}[\overline{Gq}] \leq {\textup{mult}}_{\nu^*} {\mathbb{C}}[Gq]$. To show ${\textup{mult}}_{\nu^*} {\mathbb{C}}[Gq] \leq 1$ we use that $$\label{eq:reverseplethysm}
{\textup{mult}}_{\nu^*} {\mathbb{C}}[Gq] = a_\nu(m,2m+2),$$ see e.g. [@Lan:17 Sec. 9.2.3]. We apply the upper bound given by the Kostka numbers $a_\nu(m,2m+2) \leq K(\nu,m \times (2m+2))$, which is the number of semistandard tableaux of shape $\nu$ and content $m \times (2m+2)$. This classical upper bound can be deduced for example from [@Gay:76], see also [@ike:12b Sec. 4.3(A)]. It is clear from the special shape of $\nu$ that this Kostka number is 1. As an illustration, we give an example of this tableau in the case where $m=4$:

[(1111111111223344,22222222,33333333,44444444) ]{}

In Section \[sec:notoccobsorvanidoccobs\] we prove that the obstructions in Theorem \[thm:proofofconcept\] are neither occurrence obstructions nor vanishing ideal occurrence obstructions (in infinitely many cases. This holds in *all* cases if the Alon-Tarsi conjecture is true).

#### A remark on plethysm coefficients

As far as we know, Theorem \[thm:main\] is the first result of its type in the literature so far. Even the following direct corollary about plethysm coefficient positivity is new.

\[cor:plethpos\] Let $D\geq 3$ be odd and let $m$ be arbitrary with $\binom{2(D-1)}{D-1}\geq 2(m-1)$. Let $d$ be arbitrary. Let $e=2\lceil\frac d {2(D-2)}\rceil$. Then $a_{(dD)+m\times eD}(d+me,D)\geq 1$.

Let $\lambda=(dD)$ and $\varrho=(d)$, $\Xi = \{(d)\}$. Theorem \[thm:main\] implies ${\textup{mult}}_{((dD)+(m \times e D))^*} {\mathbb{C}}[\overline{Gp}] \geq b((dD),(d),D,d) = 1$. Since $\overline{Gp}$ is a subvariety of ${\textup{Poly}}^D{\mathbb{C}}^m$, it follows $a_{(dD)+m\times eD}(d+me,D)\geq 1$.

Many additional direct corollaries of this type can be drawn from Theorem \[thm:main\].

Neither occurrence obstructions nor vanishing ideal occurrence obstructions {#sec:notoccobsorvanidoccobs}
===========================================================================

The main new property of our obstructions in Theorem \[thm:proofofconcept\] is that they use both the symmetry group of $p$ and the symmetry group of $q$. This is a fundamentally new way of constructing obstructions. To highlight the novelty of the approach, in this section we prove that the obstructions in Theorem \[thm:proofofconcept\] are not vanishing ideal occurrence obstructions. We also prove that they are not occurrence obstructions, provided a property of Latin squares is true (which we know is true for an infinite number of cases). The novelty of our method gives hope that more and stronger results can be proved in a similar way.

Recall the following proposition from [@BI:17]:

\[lem:shift\] If $D$ is even, then ${\textup{mult}}_{{\lambda}^*} {\mathbb{C}}[G p] = {\textup{mult}}_{({\lambda}+(m \times D))^*} {\mathbb{C}}[G p]$. If $D$ is odd, then ${\textup{mult}}_{{\lambda}^*} {\mathbb{C}}[G p] = {\textup{mult}}_{({\lambda}+(m \times 2D))^*} {\mathbb{C}}[G p]$.

\[lem:cormain\] Let ${\lambda}\vdash_m dD$. If $D$ is even, let $$e := \begin{cases}
     d & \text{ if } d\leq m \\
     m + \lfloor \frac{d-m}{D-2} \rfloor & \text{ if } d\geq m
     \end{cases}.$$ If $D$ is odd and ${{2(D-1)}\choose{D-1}} \geq 2(m-1)$, let $$e := \begin{cases}
     2d & \text{ if } d\leq m \\
     2m + 2\lfloor \frac{d-m}{2(D-2)} \rfloor & \text{ if } d\geq m
     \end{cases}.$$ In both cases we have ${\textup{mult}}_{({\lambda}+(m \times e D))^*} {\mathbb{C}}[\overline{Gp}] = {\textup{mult}}_{{\lambda}^*} {\mathbb{C}}[G p] = {\textup{mult}}_{({\lambda}+(m \times e D))^*} {\mathbb{C}}[Gp]$.

The second equality follows from Lemma \[lem:shift\].

Let $\Xi$ denote the set of *all* partitions $\varrho\vdash_m d$. Using Theorem \[thm:main\], then according to Proposition \[pro:gctandsymmetries\] we have $${\textup{mult}}_{({\lambda}+(m \times e_\Xi D))^*} {\mathbb{C}}[\overline{Gp}] \geq {\textup{mult}}_{{\lambda}^*} {\mathbb{C}}[G p].$$ Using Lemma \[lem:shift\] (and the fact that $e_\Xi$ is even if $D$ is odd) we see that $${\textup{mult}}_{({\lambda}+(m \times e_\Xi D))^*} {\mathbb{C}}[\overline{Gp}] = {\textup{mult}}_{{\lambda}^*} {\mathbb{C}}[G p].$$ It remains to show that $e_\Xi = e$. Recall that for natural numbers $a,b$ we have $\lceil\frac{1+a}{b}\rceil-1=\lfloor\frac a b\rfloor$.

Let $D$ be even and $d \leq m$. Then the number of nonzero $\varrho_i$ is at most $d$. Hence $e_\varrho \leq d$. On the other hand, $\varrho=(1,1,\ldots,1,0,0,\ldots,0) \vdash_m d$ provides $e_\varrho = d$, so the bound is tight. The argument for $D$ odd and $d \leq m$ is completely analogous and yields $e = 2d$.

Let $D$ be even and $d \geq m$. Then $\varrho = (1+d-m,1,1,\ldots,1)\vdash_m d$ provides $e_\varrho = m+(\lceil\frac{1+d-m}{D-2}\rceil-1) = m + \lfloor \frac{d-m}{D-2}\rfloor$. The upper bound is provided via $$\textstyle e_\varrho = {\displaystyle\sum_{i=1}^m}\lceil\frac{\varrho_i}{D-2}\rceil = {\displaystyle\sum_{i=1}^m}\left(\lceil\frac{\varrho_i+1-1}{D-2}\rceil+1-1\right) = {\displaystyle\sum_{i=1}^m} \left( \lfloor\frac{\varrho_i-1}{D-2}\rfloor +1 \right) = m+\underbrace{\textstyle{\displaystyle{\displaystyle\sum_{i=1}^m}}\lfloor\frac{\varrho_i-1}{D-2}\rfloor}_{\leq \lfloor\frac{d-m}{D-2}\rfloor} \leq m+\lfloor\frac{d-m}{D-2}\rfloor.$$

Let $D$ be odd and $d \geq m$. Then $\varrho = (1+d-m,1,1,\ldots,1)\vdash_m d$ provides $e_\varrho = 2m+2(\lceil\frac{1+d-m}{2(D-2)}\rceil-1) = 2m + 2\lfloor \frac{d-m}{2(D-2)}\rfloor$. The upper bound is provided via $$\begin{aligned}
\textstyle e_\varrho &=& {\displaystyle\sum_{i=1}^m}2\lceil\tfrac{\varrho_i}{2(D-2)}\rceil = {\displaystyle\sum_{i=1}^m}2\left(\lceil\tfrac{\varrho_i+1-1}{2(D-2)}\rceil+1-1\right) = {\displaystyle\sum_{i=1}^m} 2\left( \lfloor\tfrac{\varrho_i-1}{2(D-2)}\rfloor +1 \right) \\
&=& 2m+2\underbrace{\textstyle{\displaystyle{\displaystyle\sum_{i=1}^m}}\lfloor\tfrac{\varrho_i-1}{2(D-2)}\rfloor}_{\leq \lfloor\tfrac{d-m}{2(D-2)}\rfloor} 
\leq 2m+2\lfloor\tfrac{d-m}{2(D-2)}\rfloor.\end{aligned}$$

A Latin square of dimension $m$ is an $m \times m$ matrix for which in each row and in each column each number $1,\ldots,m$ appears exactly once. The *sign* of a column is 1 if the permutation in the column is even, and $-1$ otherwise. The *sign* of a Latin square is defined as the product of all column signs. A Latin square is called *even* if its sign is 1, and *odd* otherwise. If $m$ is odd, then it is easy to construct an involution on the set of all $m \times m$ Latin squares that pairs each even Latin square with an odd one. Hence, if $m$ is odd, then the number of even $m \times m$ Latin squares equals the number of odd $m \times m$ Latin squares. If $m$ is even, then Alon and Tarsi [@AT:92] conjecture that the number of even $m \times m$ Latin squares *differs from* the number of odd $m \times m$ Latin squares (see also [@HR:94] and [@KL:15] for equivalent formulations). This is proved for all $m=\tau+1$ [@Dri:97] for an odd prime number $\tau$ and for all $m=\tau-1$ [@Gly:10] for an odd prime number $\tau$, making $m=26$ the smallest open case. If the number of even $m \times m$ Latin squares differs from the number of odd $m \times m$ Latin squares, then we say that $m$ satisfies the *Alon-Tarsi condition*. The Alon-Tarsi condition first appeared in connection with geometric complexity theory in [@Kum:15].

\[pro:alontarsi\] Let $\nu$, $m$, $D$, $d$ be as in Theorem \[thm:proofofconcept\].

-   ${\textup{mult}}_{\nu^*} {\mathbb{C}}[\overline{Gp}]< a_\nu(2(m+2),m)$ and hence $\nu$ is not a vanishing ideal occurrence obstruction.

-   If $m$ satisfies the Alon-Tarsi condition, then ${\textup{mult}}_{\nu^*} {\mathbb{C}}[\overline{Gq}] > 0$ and hence $\nu$ is not an occurrence obstruction. In particular this is true for $m=\tau\pm1$ for all odd primes $\tau$.

The first bullet point is treated as follows. ${\textup{mult}}_{\nu^*} {\mathbb{C}}[\overline{Gp}] = {\textup{mult}}_{\nu^*} {\mathbb{C}}[{Gp}]$ by Lemma \[lem:cormain\]. Moreover, ${\textup{mult}}_{\nu^*} {\mathbb{C}}[{Gp}]=2$ (Proposition \[pro:gctandsymmetries\] and Theorem \[thm:proofofconcept\]). It remains to prove that $a_\nu(2(m+1),m)\geq 3$, which is postponed to Proposition \[pro:threetableaux\].

The second bullet point is treated as follows. Kumar proved [@Kum:15] that ${\textup{mult}}_{(m)^*} {\mathbb{C}}[\overline{G(x_1\cdots x_m)}] \geq 1$ and that ${\textup{mult}}_{(m \times m)^*} {\mathbb{C}}[\overline{G(x_1\cdots x_m)}] \geq 1$, provided that $m$ satisfies the Alon-Tarsi condition. Since $\nu = (m \times m) + (m \times m) + (m) + (m)$, the semigroup property for occurrences in ${\mathbb{C}}[\overline{G(x_1\cdots x_m)}]$ (see e.g. [@DIP:19]) yields that ${\textup{mult}}_{\nu^*} {\mathbb{C}}[\overline{G(x_1\cdots x_m)}] \geq 1$.

The rest of this paper (besides Section \[sec:threetableaux\]) is dedicated to the proof of Theorem \[thm:main\].

Preliminaries - Representation Theory {#sec:prelrepr}
=====================================

In the remainder of this paper we write $G:=\textup{GL}_m(\mathbb{C})$ to denote the general linear group for some fixed natural number $m$. A *representation* of $G$ is a finite dimensional complex vector space $\mathscr{V}$ together with a group homomorphism $\xi: G \rightarrow \textup{GL}(\mathscr{V})$. If $\xi$ is given by a polynomial map, then we call $(\mathscr{V},\xi)$ a *polynomial representation*. We write $gf := \xi(g)(f)$ for all $g \in G$ and $f \in \mathscr{V}$. A linear subspace $\mathscr{W} \subseteq \mathscr{V}$ that is closed under the action of $G$ is called a *subrepresentation*. A representation $\mathscr{V}$ is called *irreducible* iff it has only two subrepresentations, namely the zero-dimensional subspace and $\mathscr{V}$ itself.

For a $G$-representation $\mathscr{V}$, a *highest weight vector* $f \in \mathscr{V}$ of weight $\lambda \in {\mathbb{Z}}^m$ is defined to be a vector that satisfies the following two properties:

-   for all upper triangular matrices $g$ with 1s on the main diagonal we have $gf=f$, and

-   for all diagonal matrices $g := \textup{diag}(a_1,\dots, a_m)$ we have $gf = a_1^{\lambda_1}\dots a_m^{\lambda_m} f$.

We denote by ${\textup{HWV}}_\lambda(\mathscr{V})$ the vector space of highest weight vectors of weight $\lambda$ in $\mathscr{V}$. It turns out that for an irreducible polynomial $G$-representation $\mathscr{V}$ there is exactly one partition $\lambda \in \mathbb{N}^m$ such that ${\textup{HWV}}_\lambda(\mathscr{V})$ has dimension $=1$, while for all $\mu\neq{\lambda}$ we have $\dim{\textup{HWV}}_\mu(\mathscr{V})=0$. In this case we write $\mathscr{V} = \{\lambda\}$. Moreover, for each partition $\lambda \vdash_m$ there is an irreducible polynomial $G$-representation $\{\lambda\}$ and we call it the irreducible $G$-representation of *isomorphism type* $\lambda$. Furthermore, these $\{\lambda\}$ are pairwise non-isomorphic. We can now define the *multiplicity* $\textup{mult}_\lambda(\mathscr{V})$ of $\{\lambda\}$ in $\mathscr{V}$ as $$\begin{aligned}
\textup{mult}_\lambda(\mathscr{V}) = \dim {\textup{HWV}}_\lambda(\mathscr{V}),\end{aligned}$$ which is the same as the multiplicity with which $\{{\lambda}\}$ appears as a summand in a decomposition of $\mathscr{V}$ into a direct sum of irreducible $G$-representations.

The irreducible $G$-representations {#the-irreducible-g-representations .unnumbered}
-----------------------------------

In the following exposition we closely follow [@fult:97].

For a tablean $T$ let $T(r,c)$ denote the entry of $T$ in row $r$ and column $c$. Let $(e_i)_i$ be the standard basis of ${\mathbb{C}}^m$. Let $\mu = \lambda^t$.

To each tableau $T : {\lambda}\to \{1,\ldots,m\}$ we assign a tensor $$e_{T(1,1)} \otimes e_{T(2,1)} \otimes \cdots \otimes e_{T(\mu_1,1)} \otimes e_{T(1,2)} \otimes e_{T(2,2)} \otimes \cdots \otimes e_{T(\mu_2,2)} \otimes \cdots \cdots \otimes e_{T(\mu_{{\lambda}_1},{\lambda}_1)}.$$

These form a basis of ${\textstyle\bigotimes}^{|{\lambda}|}{\mathbb{C}}^m$. In this way, the space ${\textstyle\bigotimes}^{|{\lambda}|}{\mathbb{C}}^m$ is isomorphic to the space of formal linear combinations of tableaux $T : {\lambda}\to \{1,\ldots,m\}$. Using this isomorphism, the space of tableaux inherits the natural $G$-action on ${\textstyle\bigotimes}^{|{\lambda}|}{\mathbb{C}}^m$, which is given by $$\begin{aligned}
g(v_1 \otimes \dots \otimes v_{|\lambda|}) = g(v_1) \otimes \dots \otimes g(v_{|\lambda|}).\end{aligned}$$ The following vectors span the linear subspace $K({\lambda})$ of *Grassmann-Plücker relations* (sometimes called *shuffle relations*), which is invariant under the $G$-action:

-   $T+T'$, where $T'$ is a tableau that arises from $T$ by switching two numbers within one column.

-   $T-\Sigma S$, where for two fixed columns $j,j'$ and a fixed number of entries $k$ the sum is over all tableaux $S$ that arise from $T$ by exchanging the top $k$ entries in column $j$ with any $k$ entries in column $j'$, preserving the internal vertical order.

It turns out that $\{{\lambda}\} \simeq ({\textstyle\bigotimes}^{|{\lambda}|}{\mathbb{C}}^m) / K({\lambda})$, see [@fult:97 Ch. 8]. A basis of $\{\lambda\}$ is given by the semistandard tableaux of shape $\lambda$ with entries from $\{1,\dots,m\}$. The unique highest weight vector (up to scale) in $\{\lambda\}$ is the *superstandard tableau* of shape $\lambda$, which is the semistandard tableau that has only entries $i$ in row $i$. It has weight $\lambda$.

Two similar projections of tableaux {#sec:twoprojections}
===================================

In this section we present two symmetrizations that look quite similar on the basis of tableaux. We crucially use this similarity in Section \[sec:proofmain\] in the proof of the Main Theorem \[thm:main\]. Indeed, this peculiarity is the driving force behind our result.

We embed $\mathfrak{S}_m \subseteq G$ via permutation matrices. Given a tableau $S:\lambda \rightarrow \{1,\dots,m\}$ we define: $$\begin{aligned}
        P_m S := \sum_{\pi \in \mathfrak{S}_m} \pi S\end{aligned}$$ Interpreting a tableau $S:\lambda \rightarrow \{1,\dots,m\}$ as an element in $\{\lambda\}$ this can be seen as a map $P_m: \{\lambda\} \rightarrow \{\lambda\}^{\mathfrak{S}_m}$, where $\{\lambda\}^{\mathfrak{S}_m}$ consists of the elements in $\{\lambda\}$ that are invariant under the action of $\mathfrak{S}_m$. For example, using the Grassmann-Plücker relations we get that: $$\begin{aligned}
        P_{3}\,{\Yvcentermath1\small\young(1122,33)} &=& {\Yvcentermath1\small\young(1122,33)}+\underbrace{{\Yvcentermath1\small\young(2211,33)}}_{=\,{\Yvcentermath1\tiny\young(1133,22)}\,-2\,{\Yvcentermath1\tiny\young(1123,23)}\,+\,{\Yvcentermath1\tiny\young(1122,33)}}+\underbrace{{\Yvcentermath1\small\young(3322,11)}}_{=\,{\Yvcentermath1\tiny\young(1122,33)}}\\
        &+&{\Yvcentermath1\small\young(1133,22)} + \underbrace{{\Yvcentermath1\small\young(2233,11)}}_{=\,{\Yvcentermath1\tiny\young(1133,22)}}+\underbrace{{\Yvcentermath1\small\young(3311,22)}}_{=\,{\Yvcentermath1\tiny\young(1133,22)}\,-2\,{\Yvcentermath1\tiny\young(1123,23)}\,+\,{\Yvcentermath1\tiny\young(1122,33)}} \\
        &=& 4\,{\Yvcentermath1\small\young(1122,33)}-4\,{\Yvcentermath1\small\young(1123,23)}+4\,{\Yvcentermath1\small\young(1133,22)}\end{aligned}$$

Now we consider tableaux that have $\delta$ many symbols. Let $\varphi: \{1,\dots,\delta\} \rightarrow \{1,\dots,m\}$ be a map. For a tableau $T: \lambda \rightarrow \{1,\dots,\delta\}$, we define $\varphi T$ as the tableau that is the result of replacing the entries from $\{1,\dots,\delta\}$ in $T$ with entries from $\{1,\dots,m\}$. Let $$\mathcal{M}_{\delta,m} := \{\varphi \mid \varphi: \{1,\dots,\delta\} \rightarrow \{1,\dots,m\} \; \text{is a map}\}.$$ We use this to define $$\begin{aligned}
M_{\delta,m}T:=\sum_{\varphi \in \mathcal M_{\delta,m}} \varphi T \in \{{\lambda}\}^{{\mathfrak{S}}_m}.\end{aligned}$$

Tableau contraction {#sec:tableaucontraction}
===================

Let ${\mathbb{S}}\in \{{\lambda}\}$ be the superstandard tableau. Let $\gamma \in \{{\lambda}\}^*$ denote the vector dual to ${\mathbb{S}}$, i.e., the linear map that satisfies $\gamma({\mathbb{S}})=1$ and $\gamma(T)=0$ for every semistandard tableau $T \neq {\mathbb{S}}$.

In the following our goal is to understand $\gamma$ explicitly in terms of determinants, see eq.  below. For a matrix $g$ let $g_{1..j,i} \in {\mathbb{C}}^j$ denote the vector that consists of the top $j$ elements in the $i$th column of $g$. We interpret a list of $j$ vectors in ${\mathbb{C}}^i$ as an $i \times j$ matrix of column vectors. A determinant of a matrix with more rows than columns is defined as the determinant of the square matrix of its top rows. For a tableau $T : {\lambda}\to \{1,\ldots,m\}$ let $T(r,c) \in \{1,\ldots,m\}$ denote the number in row $r$ and column $c$.

\[lem:coldets\] For $g\in{\mathbb{C}}^{m \times m}$ we have $$\label{eq:gammadet}
\gamma(gT) = \prod_{c=1}^{{\lambda}_1}{\textup{det}}(g_{1..\mu_c, T(1,c)},\ldots,g_{1..\mu_c, T(\mu_c,c)}),$$ where $\mu={\lambda}^t$.

$$gT = \sum_{S:{\lambda}\to\{1,\ldots,m\}} \left(\prod_{(r,c)\in {\lambda}} g_{S(r,c),T(r,c)} \right) S = \sum_{S:{\lambda}\to\{1,\ldots,m\}\atop S \text{ regular}} \left(\prod_{(r,c)\in {\lambda}} g_{S(r,c),T(r,c)} \right) S$$ The fact that ${\mathbb{S}}$ is superstandard implies that $\gamma(S)=0$ for all $S$ that do not have a permutation of $\{1,\ldots,\mu_i\}$ in column $i$ for all $1 \leq i \leq {\lambda}_1$. Therefore $$\gamma(gT) = \sum_{S:{\lambda}\to\{1,\ldots,m\}\atop S \text{ is a col-perm.\ of ${\mathbb{S}}$}} \left(\prod_{(r,c)\in {\lambda}} g_{S(r,c),T(r,c)} \right) \gamma(S) =
\sum_{S:{\lambda}\to\{1,\ldots,m\}\atop S \text{ is a col-perm.\ of ${\mathbb{S}}$}} \left(\prod_{(r,c)\in {\lambda}} g_{S(r,c),T(r,c)} \right) \prod_{\text{column }c} {\textup{sgn}}(S,c),$$ where ${\textup{sgn}}(S,c)$ is the sign of the permutation of column $c$ of $S$. We conclude $$\gamma(gT) = \prod_{c=1}^{{\lambda}_1} \sum_{\pi \in {\mathfrak{S}}_{\mu_c}} {\textup{sgn}}(\pi) \left(\prod_{r=1}^{\mu_c} g_{\pi(r),T(r,c)} \right),$$ which finishes the proof.

We draw three quick corollaries:

\[cor:gammafactorization\] $\gamma(gT) = \prod_{c=1}^{{\lambda}_1}\gamma(g {\textup{\textsf{col}}}_c),$ where ${\textup{\textsf{col}}}_c$ is the $c$-th column of $T$.

Obvious from Lemma \[lem:coldets\].

\[cor:pm1\] For a tableau $T$ that consists of a single regular column of $m$ boxes, we have $\gamma(gT) \in \{-{\textup{det}}(g),{\textup{det}}(g)\}$. In particular, if $g \in {\textup{SL}}_m$, we have $\gamma(gT) \in \{-1,1\}$.

Since $T$ is regular, the entries of $T$ are precisely all numbers $1,\ldots,m$, not necessarily sorted. Thus according to Lemma \[lem:coldets\], $\gamma(gT)\in\{-{\textup{det}}(g),{\textup{det}}(g)\}$.

\[cor:gammazero\] If $T$ is not regular, then $\gamma(gT)=0$, independent of $g$.

$\gamma(gT)$ factorizes according to Cor. \[cor:gammafactorization\]. Since $T$ is not regular, there is a column with a repeated entry. Thus, according to Lemma \[lem:coldets\], one of the factors of $\gamma(gT)$ equals the determinant of a matrix with a repeated column, and hence is zero.

Highest weight functions on the orbit {#sec:hworbit}
=====================================

In this section we prove the following theorem.

\[thm:functionsonorbit\] The vector space ${\textup{HWV}}_{{\lambda}^*}({\mathbb{C}}[Gp]_d)$ decomposes into a direct sum of vector spaces ${\textup{HWV}}_{{\lambda}^*}({\mathbb{C}}[Gp]_d) = \bigoplus_{\varrho\vdash_m d} {\mathscr{W}}_\varrho$, and each ${\mathscr{W}}_\varrho$ is generated by the functions $$g \mapsto \gamma(g P_m S),$$ where $S$ runs over all semistandard tableaux $S$ of shape ${\lambda}$ and content $\varrho D$.

Let ${\mathscr{W}}_\varrho'$ denote the linear space spanned by all semistandard tableaux $S$ of shape ${\lambda}$ whose sorted content is $\varrho D$. Then ${\mathscr{W}}_\varrho$ is isomorphic to the ${\mathfrak{S}}_m$-invariant subspace of ${\mathscr{W}}_\varrho'$.

Explicit algebraic Peter-Weyl theorem {#explicit-algebraic-peter-weyl-theorem .unnumbered}
-------------------------------------

$G \subseteq {\mathbb{C}}^{m \times m}$ is the nonvanishing set of a polynomial and thus $G$ is a variety. It carries a canonical action of $G\times G$ via $(h',h)g := h' g h^{-1}$ for all $g,h,h'\in G$. This action lifts to to the coordinate ring ${\mathbb{C}}[G]$ via the canonical pullback: $((h',h)f)(g) := f({h'}^{-1} g h)$ for all $g,h,h'\in G$, $f \in {\mathbb{C}}[G]$.

\[thm:explalgpeterweyl\] As a $G \times G$-representation we have $${\mathbb{C}}[G] = \bigoplus_{{\lambda}} \{{\lambda}\}^* \otimes \{{\lambda}\}$$ If we embed $G \hookrightarrow G \times G$ via $g \mapsto (g,\textup{id})$, then the ${\lambda}^*$-isotypic component of ${\mathbb{C}}[G]$ is $\{{\lambda}\}^* \otimes \{{\lambda}\}$, which is spanned by functions $$g \mapsto l(gv),$$ where $l\in\{{\lambda}\}^*$ and $v \in \{{\lambda}\}$.

$H$-invariants {#h-invariants .unnumbered}
--------------

Recall the definition of the symmetry subgroup $H \leq G$ from Section \[sec:preliminaries\]. Again, consider the action of $G\times G$ on $G$ via $(h',h)g := h' g h^{-1}$ for all $g,h,h'\in G$. The action of $G\times G$ lifts to the coordinate ring ${\mathbb{C}}[G]$ and we denote by ${\mathbb{C}}[G]^{\vv H}$ the linear subspace of right $H$-invariants. ${\mathbb{C}}[G]^{\vv H}$ carries a left $G$-action. There is a bijection $gp \sim gH$ between points in the orbit $Gp$ and left cosets of $H$. This leads to the following explicit $G$-equivariant algebra isomorphism [@TY:05 25.4.6, Prop.]: $$\begin{aligned}
{\mathbb{C}}[G p] &\stackrel{\sim}{\longrightarrow}& {\mathbb{C}}[G]^{\vv H} \label{eq:algiso}\\
F & \mapsto & [g \mapsto F(gp)] \nonumber\\
\mbox{~} [gp \mapsto f(g)] & \reflectbox{\ensuremath{\mapsto}} & f \nonumber\end{aligned}$$

Taking right $H$-invariants in Theorem \[thm:explalgpeterweyl\] yields: $${\mathbb{C}}[G]^{\vv H} = \bigoplus_{{\lambda}} \{{\lambda}\}^* \otimes \{{\lambda}\}^H,$$ and explicitly: the left ${\lambda}^*$-isotypic component of ${\mathbb{C}}[G]^{\vv H}$ is spanned by functions $$g \mapsto l(gv),$$ where $l\in\{{\lambda}\}^*$ and $v \in \{{\lambda}\}^H$.

Taking left highest weight functions, we see that ${\textup{HWV}}_{{\lambda}^*}({\mathbb{C}}[G]^{\vv H}) \simeq \{{\lambda}\}^H$ and that ${\textup{HWV}}_{{\lambda}^*}({\mathbb{C}}[G]^{\vv H})$ is spanned by functions $$\label{eq:ggammagv}
g \mapsto \gamma(gv),$$ where $v \in \{{\lambda}\}^H$. In the next subsection we will use the special structure of $H$ to finish the proof of Theorem \[thm:functionsonorbit\].

The coordinate ring of the orbit of the power sum {#the-coordinate-ring-of-the-orbit-of-the-power-sum .unnumbered}
-------------------------------------------------

Considering eq. , in order to understand ${\textup{HWV}}_{{\lambda}^*}({\mathbb{C}}[G]^{\vv H})$ we need to understand the $H$-invariant space $\{{\lambda}\}^H$. The group $H$ is the semidirect product $\{{\lambda}\}^H = (\{{\lambda}\}^{{\mathbb{Z}}_D^m})^{{\mathfrak{S}}_m}$, which enables us to analyze $\{{\lambda}\}^H$ via a two-step process by first analyzing $\{{\lambda}\}^{{\mathbb{Z}}_D^m}$ and then taking ${\mathfrak{S}}_m$-invariants. We consider the basis of $\{{\lambda}\}$ given by the semistandard tableaux $S:{\lambda}\to\{1,\ldots,m\}$. Note that for $g \in {\mathbb{Z}}_D^m$ we have that $S$ and $gS$ coincide up to rescaling with a $D$th root of unity. Indeed, if any symbol in the tableau $S$ does not occur a multiple of $D$ times, then $S$ vanishes under the symmetrization $$S \mapsto \frac{1}{D^m} \sum_{g \in {\mathbb{Z}}_D^m} \pi S.$$ Moreover, each $S$ in which every number appears a multiple of $D$ many times is fixed under this symmetrization map. Hence $\{{\lambda}\}^{{\mathbb{Z}}_D^m}$ has a basis given by semistandard tableaux of shape ${\lambda}$ in which each number appears a multiple of $D$ many times. For a partition $\varrho$ let ${\mathscr{W}}_\varrho'$ denote the linear space spanned by all semistandard tableaux of shape ${\lambda}$ whose sorted content is $\varrho D$. This gives a decomposition $\{{\lambda}\}^{{\mathbb{Z}}_D^m} = \bigoplus_{\varrho}{\mathscr{W}}_\varrho'$ as a direct sum. The action of ${\mathfrak{S}}_m$ leaves ${\mathscr{W}}_\varrho'$ fixed. Hence $(\{{\lambda}\}^{{\mathbb{Z}}_D^m})^{{\mathfrak{S}}_m} = \bigoplus_\varrho ({\mathscr{W}}_\varrho')^{{\mathfrak{S}}_m}$. A generating set for $\{{\lambda}\}^H$ is thus obtained by taking the ${\mathscr{W}}_\varrho'$ and their tableau bases and independently symmetrizing over $\mathfrak S_m$, which is done (up to scale) by applying $P_m$. Using eq.  we thus obtain the following proposition.

The vector space ${\textup{HWV}}_{{\lambda}^*}({\mathbb{C}}[G]^{\vv H}_d)$ decomposes into a direct sum of vector spaces ${\textup{HWV}}_{{\lambda}^*}({\mathbb{C}}[G]^{\vv H}_d) = \bigoplus_{\varrho\vdash_m d} {\mathscr{W}}_\varrho$, and each ${\mathscr{W}}_\varrho$ is generated by the functions $$g \mapsto \gamma(g P_m S),$$ where $S$ runs over all semistandard tableaux $S$ of shape ${\lambda}$ and content $\varrho D$.

Let ${\mathscr{W}}_\varrho'$ denote the linear space spanned by all semistandard tableaux $S$ of shape ${\lambda}$ whose sorted content is $\varrho D$. Then ${\mathscr{W}}_\varrho$ is isomorphic to the ${\mathfrak{S}}_m$-invariant subspace of ${\mathscr{W}}_\varrho'$.

Theorem \[thm:functionsonorbit\] now follows immediately by applying the algebra isomorphism .

A formula for the multiplicities in the coordinate ring of the orbit of the power sum (Proof of Prop. ) {#sec:gctandsymmetries}
=======================================================================================================

Crucial parts of this section are the result of a collaboration with Greta Panova and appeared in the first author’s unpublished lecture notes for a winter 2017/2018 course on geometric complexity theory [@Ike:19].

In this section we prove Proposition \[pro:gctandsymmetries\]. In fact, we prove a slightly stronger result as follows.

\[pro:precisedecomposition\] Let $\{{\lambda}\}_{\varrho} \subseteq \{{\lambda}\}$ denote the linear subspace spanned by the tableaux whose sorted content is $\varrho D$. Then $\dim (\{{\lambda}\}_{\varrho})^{{\mathfrak{S}}_m} = b({\lambda},\varrho,D,d)$.

Let $\{{\lambda}\}^\varrho$ denote the $\varrho$-weight space, i.e., the linear space spanned by tableaux of shape ${\lambda}$ and content $\varrho$. Then $\{{\lambda}\}_\varrho = \bigoplus_{\gamma \in {\mathfrak{S}}_m\varrho} \{\lambda\}^\gamma$.

For a partition $\varrho \vdash_m d$ let ${\mathfrak{S}}_m\varrho \subseteq {\mathbb{N}}^m$ denote the orbit of $\varrho$. Note that $\varrho$ is the only partition in its orbit, while the other lists are not in the correct order. Let ${\text{stab\,}}\varrho \leq {\mathfrak{S}}_m$ denote the stabilizer of $\varrho$.

$\dim (\{{\lambda}\}_\varrho)^{{\mathfrak{S}}_m} = \dim\left(\{\lambda\}^\varrho\right)^{{\text{stab\,}}\varrho}.$

We construct an isomorphism of vector spaces.

Let $W := \{{\lambda}\}$. Let $\pi_1,\ldots,\pi_r$ be a system of representatives of left cosets for ${\text{stab\,}}\varrho \leq {\mathfrak{S}}_m$ with $\pi_1 = \text{id}$, i.e., ${\mathfrak{S}}_m = \pi_1 {\text{stab\,}}\varrho \ \dot\cup \ \cdots \ \dot\cup \ \pi_r{\text{stab\,}}\varrho$ and we have ${\mathfrak{S}}_m \varrho = \{\pi_1 \varrho , \ldots, \pi_r \varrho\}$. Therefore we have the decomposition $$W_\varrho = \bigoplus_{j=1}^r \pi_j W^\varrho.$$ Let $\overline p : W_\varrho \twoheadrightarrow W^\varrho$ be the projection according to this decomposition. We claim that the restriction $$p : \left(W_\varrho\right)^{{\mathfrak{S}}_m} \to \left(W^\varrho\right)^{{\text{stab\,}}\varrho}$$ is an isomorphism of vector spaces. This then finishes the proof. We verify well-definedness, injectivity, and surjectivity of $p$.

Well-definedness: The spaces $\pi_1 W^\varrho,\ldots,\pi_r W^\varrho$ are permuted by ${\mathfrak{S}}_m$. Every $\sigma \in {\text{stab\,}}\varrho$ fixes $W^\varrho$, thus $\sigma v_1 = v_1$ if $v_1 \in W^\varrho$. Thus the map $v = \sum_{j=1}^r v_j \stackrel{\overline p}{\mapsto} v_1$ maps $W_\varrho$ to $(W^\varrho)^{{\text{stab\,}}\varrho}$.

Injectivity: If $v \in (W_\varrho)^{{\mathfrak{S}}_m}$, then $v = \pi v = \sum_j \pi v_j$. Therefore $v_j = \pi_j v_1$. If $p(v)=0$, then $v_1=0$, thus all $v_j=0$, which proves injectivity.

Surjectivity: Let $v_1 \in (W^\varrho)^{{\text{stab\,}}\varrho}$. Set $v_j := \pi_j v_1$ and put $v:=\sum_j v_j$. Clearly $p(v)=v_1$. It remains to verify that $v$ is ${\mathfrak{S}}_m$-invariant. $$v = \sum_{j=1}^r \pi_j v_1 = \sum_{j=1}^r \tfrac{1}{|{\text{stab\,}}\varrho|} \sum_{\tau \in {\text{stab\,}}\varrho} \pi_j \tau v_1 = \tfrac{1}{|{\text{stab\,}}\varrho|} \sum_{\pi \in {\mathfrak{S}}_m}\pi v_1,$$ which is ${\mathfrak{S}}_m$-invariant.

We are left with determining $\dim\left(\{{\lambda}\}^{\varrho}\right)^{{\text{stab\,}}\varrho}$. We use a detour via Specht modules: the Specht module $[{\lambda}]$ is an irreducible ${\mathfrak{S}}_{|{\lambda}|}$-representation that can be constructed as the subrepresentation of $\{{\lambda}\}$ spanned by all standard tableaux. Define the Young subgroup $G_\varrho \subseteq {\mathfrak{S}}_{dD} := {\mathfrak{S}}_{\varrho_1 D} \times \cdots \times {\mathfrak{S}}_{\varrho_m D}$. We use that $\{{\lambda}\}^{\varrho} \simeq [{\lambda}]^{G_\varrho}$, see e.g. [@ike:12b Sec. 4.3(A)].

Schur-Weyl duality implies that $$\begin{aligned}
\dim\left([{\lambda}]^{G_\varrho}\right)^{{\text{stab\,}}\varrho} = \dim{\textup{HWV}}_{\lambda}(\{{\lambda}\}\otimes ([{\lambda}]^{G_\varrho})^{{\text{stab\,}}\varrho} ) = \dim{\textup{HWV}}_{\lambda}((\otimes^{dD}V)^{G_\varrho\rtimes{{\text{stab\,}}\varrho}})\end{aligned}$$ for $V$ having large enough dimension.

$$\begin{aligned}
(\otimes^{dD}V)^{G_\varrho\rtimes{{\text{stab\,}}\varrho}} &=& ({\textup{Poly}}^{D\varrho_1}V \otimes \cdots \otimes {\textup{Poly}}^{D\varrho_m}V)^{{\text{stab\,}}\varrho}\\
&=& \left(\bigotimes^{\hat\varrho_1}{\textup{Poly}}^{D}V \otimes \bigotimes^{\hat\varrho_2}{\textup{Poly}}^{2D}V \otimes \cdots \otimes \bigotimes^{\hat\varrho_d}{\textup{Poly}}^{dD}V\right)^{{\text{stab\,}}\varrho} \\
&=& \underbrace{{\mathbb{C}}[{\textup{Poly}}^{D}V]^*_{\hat\varrho_1}}_{=\bigoplus_{\mu^1} \{\mu^1\}^{\oplus a_{\mu^1}(\hat\varrho_1,D)}} \otimes {\mathbb{C}}[{\textup{Poly}}^{2D}V]^*_{\hat\varrho_2} \otimes \cdots \otimes \underbrace{{\mathbb{C}}[{\textup{Poly}}^{dD}V]^*_{\hat\varrho_d}}_{{=\bigoplus_{\mu^d} \{\mu^d\}^{\oplus a_{\mu^d}(\hat\varrho_d,dD)}}} \quad\quad\quad\hfill(\dagger).\end{aligned}$$

The multiplicity of $\{\mu^i\}^*$ in ${\mathbb{C}}[{\textup{Poly}}^{iD}V]_{\hat\varrho_i}$ is $a_{\mu^i}(\hat\varrho_i,iD)$. Using distributivity we obtain that the multiplicity of $\{{\lambda}\}$ in the representation $(\dagger)$ equals $$\sum_{\mu^1,\mu^2,\ldots,\mu^d \atop \mu^i \vdash \hat\varrho_i D i} c_{\mu^1,\mu^2,\ldots,\mu^d}^{\lambda}\prod_{i=1}^d a_{\mu^i}(\hat\varrho_i,iD)$$

${\textup{mult}}_{\lambda}{\mathbb{C}}[Gp]_d \stackrel{\text{Thm. }\ref{thm:functionsonorbit}}{=} \sum_{\varrho\vdash_m d}({\mathscr{W}}_\varrho)^{{\mathfrak{S}}_m} \stackrel{\text{Prop.~\ref{pro:precisedecomposition}}}{=} \sum_{\varrho\vdash_m d} b({\lambda},\varrho,D,d)$.

Highest weight functions on the orbit closure {#sec:hworbitclosure}
=============================================

In this section we study the coordinate ring ${\mathbb{C}}[\overline{Gp}]$. Much less is known about this ring compared to ${\mathbb{C}}[Gp]$, in particular we do not have formulas for ${\mathbb{C}}[\overline{Gp}]$ that are comparable to Prop. \[pro:gctandsymmetries\]. Nevertheless, the following theorem provides a way to analyze ${\mathbb{C}}[\overline{Gp}]$ and connect it to ${\mathbb{C}}[Gp]$.

For an $m \times n$ matrix $A$ let $A p := \ell_1^D+\ell_2^D+\cdots+\ell_n^D$, where $\ell_i$ is the linear form given by the $i$-th column of $A$. Note that this is a generalization of $gp$ for $g \in {\textup{GL}}_m$.

\[thm:functionsonorbitclosure\] If $|{\lambda}|$ is not divisible by $D$, then ${\textup{HWV}}_{{\lambda}^*}({\mathbb{C}}[\overline{Gp}])=0$.

Let ${\lambda}\vdash \delta D$. The vector space ${\textup{HWV}}_{{\lambda}^*}({\mathbb{C}}[\overline{Gp}])$ is generated by the functions $$g \mapsto \gamma(g M_{\delta,m} T),$$ where $T$ runs over all semistandard tableaux of shape ${\lambda}$ in which each entry $1,\ldots,\delta$ appears exactly $D$ many times.

Additionally, for a semistandard tableau $T$ of shape ${\lambda}$ in which each entry $1,\ldots,\delta$ appears exactly $D$ many times, the function $$A \mapsto \gamma(A M_{\delta,m} T)$$ is either zero or a HWV of weight ${\lambda}^*$ in ${\mathbb{C}}[{\textup{Poly}}^D {\mathbb{C}}^m]$.

This is a rephrasing of [@AIR:16], which is a special case of [@BIP:19 Prop. 4.5 and Thm. 4.7]. Indeed, [@BIP:19] covers more general cases. For the sake of completeness and to highlight that the proof technique is very different from the technique in Section \[sec:hworbit\], we prove Theorem \[thm:functionsonorbitclosure\].

The first observation follows from the fact that $\overline{Gp} \subseteq {\textup{Poly}}^D{\mathbb{C}}^m$ is a closed subvariety that is closed under rescaling, and hence ${\mathbb{C}}[\overline{Gp}]$ is a graded subalgebra of ${\mathbb{C}}[{\textup{Poly}}^D{\mathbb{C}}^m]$. We know that in each degree $\delta$ component ${\mathbb{C}}[{\textup{Poly}}^D{\mathbb{C}}^m]_\delta$ of ${\mathbb{C}}[{\textup{Poly}}^D{\mathbb{C}}^m]$ the only types ${\lambda}^*$ that occur satisfy ${\lambda}\vdash \delta D$, see e.g. [@ike:12b Lemma 4.3.3].

Schur-Weyl duality yields that $$\label{eq:schurweyl}
{\textstyle\bigotimes}^{\delta D} {\mathbb{C}}^{m*} = \bigoplus_{{\lambda}\vdash_m \delta D} \{{\lambda}^*\} \otimes [{\lambda}].$$ A highest weight vector of weight ${\lambda}^*$ in ${\textstyle\bigotimes}^{\delta D} {\mathbb{C}}^{m*}$ is given for example by $$v_{\lambda}:= x_1 \wedge x_2 \wedge \cdots \wedge x_{\mu_1} \otimes x_1 \wedge x_2 \wedge \cdots \wedge x_{\mu_2} \otimes \cdots \cdots \otimes x_1 \wedge x_2 \wedge \cdots \wedge x_{\mu_{{\lambda}_1}},$$ where $\mu = {\lambda}^t$ and $\{x_i\}_i$ is the basis of ${\mathbb{C}}^{m*}$. Let $T_{\lambda}$ denote the column-standard tableau of shape ${\lambda}$, i.e., the tableau that is filled with the numbers $1,\ldots,|{\lambda}|$ in a columnwise fashion from left to right, top to bottom. Since $[{\lambda}]$ is irreducible, from we see that ${\textup{HWV}}_{{\lambda}^*}({\textstyle\bigotimes}^{\delta D}{\mathbb{C}}^{m*})$ is generated by the set $\{v_{\lambda}\pi \mid \pi \in {\mathfrak{S}}_{\delta D} \text{ s.t. $\pi T_{\lambda}$ is standard}\}$.

By the polarization principle (see e.g. [@ike:12b Claim 4.2.13]), all functions $f$ in ${\mathbb{C}}[{\textup{Poly}}^D{{\mathbb{C}}^{m*}}]_\delta$ can be obtained via some tensor $v_f \in {\textstyle\bigotimes}^{\delta D}{\mathbb{C}}^m$ and defining $$f(y) := \langle v_f , y^{\otimes \delta}\rangle.$$ The resulting function $f$ is a highest weight function iff $v_f$ is a HWV. Thus we see that ${\textup{HWV}}_{{\lambda}^*}({\mathbb{C}}[{\textup{Poly}}^D{\mathbb{C}}^m]_\delta)$ is generated by the functions $$f(y) := \langle \pi v_{\lambda}, y^{\otimes \delta}\rangle.$$ In the following we analyze how to restrict these functions to $\overline{Gp}$. When $y = gp = \ell_1^D+\cdots+\ell_m^D$ is in the orbit of the power sum, then clearly $$y^{\otimes \delta} = \sum_{\varphi:\{1,\ldots,\delta\}\to\{1,\ldots,m\}} \ell_{\varphi(1)}^D \otimes \cdots \otimes \ell_{\varphi(\delta)}^D.$$ The linear forms $\ell_i$ correspond to the vectors $g_{1..m,i}$. We evaluate $$f(y) := \langle \pi v_{\lambda}, y^{\otimes \delta}\rangle = \langle v_{\lambda}, \pi(y^{\otimes \delta})\rangle$$ $$= \sum_{\beta:\{1,\ldots,\delta D\}\to\{1,\ldots,m\}\atop\text{respecting $\pi T_{\lambda}$}} \prod_{c=1}^{{\lambda}_1}{\textup{det}}(g_{1..\mu_c, \beta(\pi T_{\lambda}(1,c))},\ldots,g_{1..\mu_c, \beta(\pi T_{\lambda}(\mu_c,c))}),$$ where $\beta$ *respects* a tableau $S$ if all numbers $1,\ldots,D$ are mapped to the same value, and all numbers $D+1,\ldots,2D$ are mapped to the same value, and so on.

Therefore the vector space ${\textup{HWV}}_{{\lambda}^*}({\mathbb{C}}[\overline{Gp}])$ is generated by the functions $$\label{eq:respectS}
g \mapsto \sum_{\beta:\{1,\ldots,Dd\}\to\{1,\ldots,m\}\atop\text{respecting $S$}} \prod_{c=1}^{{\lambda}_1}{\textup{det}}(g_{1..\mu_c, \beta(S(1,c))},\ldots,g_{1..\mu_c, \beta(S(\mu_c,c))}),$$ where $S$ runs over all standard tableaux of shape ${\lambda}$.

Given a standard tableau $S$ we define a tableau $T$ by replacing the first $D$ entries $1,\ldots,D$ by the number $1$, the next $D$ entries $D+1,\ldots,2D$ by the number $2$, and so on. It is easy to check that if $T$ is not regular, then the function corresponding to $S$ describes the zero function, because each summand in has a zero factor that is the determinant of a matrix with a repeating column. We assume from now on that $T$ is regular. Since $T$ is regular and $S$ is standard, $T$ is semistandard. We rewrite as follows:

$$\label{eq:sumsofprodofdets}
g \mapsto \sum_{\varphi:\{1,\ldots,\delta\}\to\{1,\ldots,m\}} \prod_{c=1}^{{\lambda}_1}{\textup{det}}(g_{1..\mu_c, \varphi(T(1,c))},\ldots,g_{1..\mu_c, \varphi(T(\mu_c,c))})$$

Using , we can write this in terms of $\gamma$ as follows:

$$g \mapsto \sum_{\varphi:\{1,\ldots,\delta\}\to\{1,\ldots,m\}} \gamma(g \varphi T).$$

By definition of $M_{\delta,m}$, this can be rewritten as:

$$g \mapsto \gamma(g M_{\delta,m} T),$$ which finishes the proof of the second part of Theorem \[thm:functionsonorbitclosure\].

For the last claim, we note that in this construction of highest weight functions we did not use that $g$ is a square matrix. A rectangular matrix $A$ works in the same way.

An equation for Waring rank (Proof of the missing part in Prop. ) {#sec:threetableaux}
=================================================================

In this section we prove the following proposition that was used in the proof of Proposition \[pro:alontarsi\].

\[pro:threetableaux\] Let $\nu = (2m)+m\times 2m$. Then $a_\nu(2(m+1),m) > 2$.

By Proposition \[pro:gctandsymmetries\] and Lemma \[lem:cormain\] we have ${\textup{mult}}_{\nu^*} {\mathbb{C}}[\overline{Gp}] = {\textup{mult}}_{\nu^*} {\mathbb{C}}[{Gp}] = 2.
$ This means that there are two linearly independent HWVs of weight $\nu^*$ that do not vanish on $Gp$. To finish the proof it suffices to construct a nonzero HWV of weight $\nu^*$ that vanishes on $Gp$, because then these three HWVs are linearly independent. Note that in particular we construct an equation that vanishes on all polynomials of Waring rank at most $m$.

We use the last part of Theorem \[thm:functionsonorbitclosure\] to construct this third function. Let $n := 2m+2$. Let $T_\textsf{left}$ be the $m \times (m+2)$ tableau that is filled in a rowwise fashion from top to bottom and from left to right with $m$ many 1s, then $m$ many 2s, and so on, until $m$ many $(m+2)$s. For example, if $m=6$, then $$T_\textsf{left} =
{\ytableausetup{boxsize=1.1em}
\ytableaushort{
11111122,
22223333,
33444444,
55555566,
66667777,
77888888
}}$$ We remark that the function corresponding to $T_\textsf{left}$ via Theorem \[thm:functionsonorbitclosure\] is a generalization of Aronhold’s degree 4 invariant on ternary cubics, see also [@BI:17] for other (related) generalizations.

Let $T_\textsf{right}$ be the $(m \times 2)+(m^2-2m)$ tableau whose first two columns are equal and consist of the entries $m+3,m+4,\ldots,2m+2$ from top to bottom. The remaining singleton columns get filled with $m-2$ many entries $m+3$, $m-2$ many entries $m+4$, $m-2$ many entries $m+5$, and so on, until $m-2$ many entries $2m+2$. For example, if $m=6$, then $$T_\textsf{right} =
{\ytableausetup{boxsize=1.1em}
\ytableaushort{
999999{10}{10}{10}{10}{11}{11}{11}{11}{12}{12}{12}{12}{13}{13}{13}{13}{14}{14}{14}{14},
{10}{10},
{11}{11},
{12}{12},
{13}{13},
{14}{14}
}}$$ The tableau $T$ is defined as the concatenation $T := T_\textsf{left}+T_\textsf{right}$. We observe that $T$ is duplex.

By Theorem \[thm:functionsonorbitclosure\] the function $f : A \mapsto \gamma(A M_{n,n} T)$ is either zero or a HWV of weight $\nu^*$ in ${\mathbb{C}}[{\textup{Poly}}^m {\mathbb{C}}^m]$.

$f$ does not vanish on ${\textup{Poly}}^m{\mathbb{C}}^m$.

This is due to the fact that $T$ is duplex, in complete analogy to [@bci:10]. Choose $A$ to be an $m \times n$ matrix whose entries are real numbers chosen generically (one can alternatively think of the entries being chosen uniformly at random for example from a Gaussian distribution). Since $T$ is duplex, each summand in $\gamma(A M_{n,n}T)$ is a product of determinants (see ), but each factor in the product appears an even number of times and hence the product is nonnegative. Since $A$ was chosen generically, for the identity map $\textsf{id} \in \mathcal M_{n,n}$ we have $\gamma(A \,\textsf{id}\, T) > 0$. Any finite sum of nonnegative numbers that contains at least one positive number is nonzero, so $\gamma(A M_{n,n}T)$ is nonzero. This finishes the proof.

The preceding claim implies that $f$ is a nonzero HWV of weight $\nu^*$ in ${\mathbb{C}}[{\textup{Poly}}^m {\mathbb{C}}^m]$. To finish the proof of Proposition \[pro:threetableaux\] it suffices to prove that $f$ vanishes on $Gp$. The crucial property is that no tableau in $\mathcal M_{m+2,m}T_\textsf{left}$ is regular: Since $T_\textsf{left}$ is rectangular with the maximum number of rows, a regular tableau in $\mathcal M_{m+2,m}T_\textsf{left}$ has $m+2$ many 1s, $m+2$ many 2s, and so on, but every symbol in $\mathcal M_{m+2,m}T_\textsf{left}$ appears a multiple of $m$ many times. Since no tableau in $\mathcal M_{m+2,m}T_\textsf{left}$ is regular, no tableau in $\mathcal M_{n,m}T$ is regular. Hence all summands in $\gamma(g M_{n,m}T)$ are zero, see Corollary \[cor:gammazero\]. This finishes the proof of Proposition \[pro:threetableaux\].

Proof of the Main Technical Theorem \[thm:main\] using the Tableau Lifting Theorem {#sec:proofmain}
==================================================================================

In this section we prove Theorem \[thm:main\], based on the following combinatorial Tableau Lifting Theorem \[thm:prolongation\] whose long and combinatorial proof we will develop during the remaining sections of this paper. Much simpler forms of other tableau lifting theorems appeared in [@KL:12; @BIP:19].

Fix a shape ${\lambda}$ and natural numbers $m$ and $e$. For a tableau $T$ of shape $(m \times e) + {\lambda}$ we define ${\textup{\textsf{leftpart}}}(T)$ to be the $m\times e$ rectangular subtableau consisting of the leftmost $e$ columns, and we define ${\textup{\textsf{rightpart}}}(T)$ to be the shape ${\lambda}$ subtableau consisting of the rightmost ${\lambda}_1$ columns. In particular, we have $T = {\textup{\textsf{leftpart}}}(T)+{\textup{\textsf{rightpart}}}(T)$. For $\varrho \in ({\mathbb{N}}_{\geq 0})^m$ a tableau $S$ has content $D\varrho$ if each number $i$ appears exactly $D\varrho_i$ many times in $S$.

\[thm:prolongation\] Let $D \geq 3$ and $m \geq 2$. Given a regular tableau $S$ of shape $\lambda \vdash_m dD$ and content $D \varrho$ for $\varrho\vdash_m d$. Let

-   $e_\varrho:=\sum_{i=1}^{m} \lceil \frac{\varrho_i}{D-2} \rceil$ in the case where $D$ is even

-   and $e_\varrho:=\sum_{i=1}^{m} 2\lceil \frac{\varrho_i}{2(D-2)} \rceil$ in the case where $D$ is odd and ${{2(D-1)}\choose{D-1}} \geq 2(m-1)$.

Let $\delta := m e_\varrho+d$. In both cases there exists a tableau $T:\lambda +(m \times e_\varrho D) \rightarrow \{1,\dots,\delta\}$ in which every entry appears exactly $D$ many times such that

1.  \[enum:rightpartinSmS\] For each $\varphi \in \mathcal{M}_{\delta,m}$ for which $\varphi(T)$ is regular we have that ${\textup{\textsf{rightpart}}}(\varphi(T))\in{\mathfrak{S}}_m S$,

2.  \[enum:duplex\] For each $\varphi \in \mathcal{M}_{\delta,m}$ for which $\varphi(T)$ is regular we have that ${\textup{\textsf{leftpart}}}(\varphi(T))$ is duplex,

3.  \[enum:existspreimage\] there exists $\varphi\in\mathcal{M}_{\delta,m}$ such that $\varphi(T)$ is regular and ${\textup{\textsf{rightpart}}}(\varphi(T))=S$.

By Theorem \[thm:functionsonorbit\] and Proposition \[pro:precisedecomposition\] we know that there exists a set of regular tableaux $\{S_{\varrho,i}\mid \varrho\in\Xi, \ 1 \leq i \leq b({\lambda},\varrho,D,d)\}$ of shape ${\lambda}$ such that each $S_{\varrho,i}$ has content $D\varrho$ and the set of corresponding functions $$f^{S_{\varrho,i}}\in {\mathbb{C}}[Gp], \quad gp \mapsto \gamma(g P_m S_{\varrho,i}).$$ is linearly independent. Since all these functions $f^{S_{\varrho,i}}$ are homogeneous of the same degree $d$, they are not only linearly independent as functions on ${\textup{GL}}_m p$, but also their restrictions to ${\textup{SL}}_m p$ are linearly independent. Using the Tableau Lifting Theorem \[thm:prolongation\], for each $S_{\varrho,i}$ we construct a tableau $T_{\varrho,i}$ of shape ${\lambda}+(m\times e_\varrho D)$ satisfying the properties listed in Theorem \[thm:prolongation\]. We claim that for all $\varrho,i$ there exists $\alpha\neq 0$ such that $$\label{eq:alpha}\tag{$\ast$}
\begin{minipage}{\textwidth-2cm}
under the map $\psi : \varphi\mapsto{\textup{\textsf{rightpart}}}(\varphi T_{\varrho,i})$ that maps from $\mathcal M_{\delta,m}$ to the set of tableaux of shape $\lambda$,
each tableau in ${\mathfrak{S}}_m S_{\varrho,i}$
has exactly $\alpha$ many preimages in $\mathcal{M}_{\delta,m}$ for which $\varphi T_{\varrho,i}$ is regular.
\end{minipage}$$ Proof of : Clearly $\varphi T_{\varrho,i}$ is regular iff $\pi \varphi T_{\varrho,i}$ is regular. Note that $\psi$ is ${\mathfrak{S}}_m$-equivariant in the following sense: $\psi(\pi \circ \varphi) = \pi\psi(\varphi)$. Hence taking the preimage $\psi^{-1}$ is also ${\mathfrak{S}}_m$-equivariant. Thus for all $\hat S \in {\mathfrak{S}}_m S_{\varrho,i}$ we have $\varphi \in \psi^{-1}(\hat S)$ iff $\pi \circ \varphi \in \psi^{-1}(\pi \hat S)$. Thus the application of $\pi$ gives a bijection between the preimages of $\hat S$ and $\pi \hat S$. To prove claim  it remains to show that $\alpha \neq 0$. This follows from Thm. \[thm:prolongation\]. $\square$

According to [@BI:17 Prop. 3.25] there exists an ${\textup{SL}}_m$-invariant function $\Phi$ in ${\mathbb{C}}[\overline{Gp}]$ with $\Phi(p)=1$, called the fundamental invariant. Moreover, $$\begin{cases}
\text{$\Phi$ has degree $m$ and $\Phi(gp) = {\textup{det}}(g)^D p$ for $g \in {\textup{GL}}_m$} & \text{ if $D$ is even} \\
\text{$\Phi$ has degree $2m$ and $\Phi(gp) = {\textup{det}}(g)^{2D} p$ for $g \in {\textup{GL}}_m$} & \text{ if $D$ is odd and $2m \leq \binom{2D}{D}$}.
\end{cases}$$ Since orbit closures are irreducible varieties, given two highest weight vectors $f$ of weight ${\lambda}$ and $\tilde f$ of weight $\tilde {\lambda}$ in ${\mathbb{C}}[\overline{Gp}]$, their product $f \cdot \tilde f$ is nonzero and a highest weight vector of weight ${\lambda}+\tilde {\lambda}$. Let $\overline{f}^{S_{\varrho,i}}$ be the product of $\Phi^{e_\Xi-e_\varrho}$ ($\Phi^{(e_\Xi-e_\varrho)/2}$ if $D$ is odd) and the function corresponding to $T_{\varrho,i}$: $$\overline{f}^{S_{\varrho,i}}(gp) = {\textup{det}}(g)^{D(e_\Xi-e_\varrho)}\cdot \gamma(g M_{m,d} T_{\varrho,i}) \quad\quad\text{(holds for $D$ even and odd.)}$$ We claim that $\overline{f}^{S_{\varrho,i}}$ coincides with $f^S_{\varrho,i}$ when restricted to ${\textup{SL}}_m p$ (up to nonzero a factor), which can be seen as follows. For $g \in {\textup{SL}}_m$ we have $$\begin{aligned}
 \overline{f}^{S_{\varrho,i}}(gp) &=& 1 \cdot \gamma(g M_{m,d} T_{\varrho,i}) 
 = \sum_{\varphi \in \mathcal M_{m,d}}\gamma(g \varphi T_{\varrho,i}) \\
 &\stackrel{\text{Cor.}~\ref{cor:gammazero}}{=}& \sum_{\substack{\varphi \in \mathcal M_{m,d}\\\varphi T_{\varrho,i}\text{ regular}}}\gamma(g \varphi T_{\varrho,i}) \\
 &\stackrel{\text{Cor.}~\ref{cor:gammafactorization}\text{ and Cor.}~\ref{cor:pm1}\text{ and Thm.}~\ref{thm:prolongation}\eqref{enum:duplex}}{=}&(\pm 1)^2\sum_{\substack{\varphi \in \mathcal M_{m,d}\\\varphi T_{\varrho,i}\text{ regular}}}\gamma(g {\textup{\textsf{rightpart}}}(\varphi T_{\varrho,i})) \\
 &\stackrel{\text{Thm.~}\ref{thm:prolongation}\eqref{enum:rightpartinSmS}\text{ and }\eqref{eq:alpha}}{=}& \alpha \sum_{\hat S \in {\mathfrak{S}}_m S_{\varrho,i}}\gamma(g \hat S) 
 = \tfrac{|{\mathfrak{S}}_m S_{\varrho,i}|\alpha}{m!} \gamma(g P_m S_{\varrho,i}) \\
 &=& \tfrac{|{\mathfrak{S}}_m S_{\varrho,i}|\alpha}{m!} f^{S_{\varrho,i}}(gp).\end{aligned}$$ Since each $\overline{f}^{S_{\varrho,i}}$ coincides with $f^{S_{\varrho,i}}$ when restricted to ${\textup{SL}}_m p$ (up to a nonzero factor), the $\overline f^{S_{\varrho,i}}$ are linearly independent. It follows from Theorem \[thm:functionsonorbitclosure\] that the $\overline{f}^{S_{\varrho,i}}$ are restrictions of functions in ${\textup{HWV}}_{({\lambda}+(m\times e_\Xi D))^*}{\mathbb{C}}[\overline{Gp}]$. This proves the main Theorem \[thm:main\].

It remains to prove the Tableau Lifting Theorem \[thm:prolongation\], whose purely combinatorial proof will be the focus of the rest of the paper. The construction for odd $D$ is more complicated than for even $D$, which is why we focus on the case where $D$ is even first.

We will construct ${\textup{\textsf{leftpart}}}(T)$ and ${\textup{\textsf{rightpart}}}(T)$ mainly independently.

For even $D$, the alphabet that we are using for $T$ is not $\{1,\ldots,\delta\}$, but a more descriptive alphabet using the symbols $i_\ell$ and $j_k^i$. For each box $\square$ in $S$, if $\square$ has the entry $i$, then the box corresponding to $\square$ in ${\textup{\textsf{rightpart}}}(T)$ has the symbol $i_\ell$ for some $\ell$. The only other constraints for ${\textup{\textsf{rightpart}}}(T)$ are concerned with how often the different symbols $i_\ell$ appear. The symbols $j_k^i$ do not appear in ${\textup{\textsf{rightpart}}}(T)$, but only in ${\textup{\textsf{leftpart}}}(T)$. The tableau ${\textup{\textsf{leftpart}}}(T)$ is constructed in several steps, starting with a tableau obtained from a set of hypergraphs $H^{(i)}$, and then reordering entries within the rows.

For odd $D$ the situation is similar. The alphabet that we are using for $T$ is not $\{1,\ldots,\delta\}$, but a more descriptive alphabet using the symbols $i_\ell$, $j_k^i$, $j_{\overline k}^i$. For each box $\square$ in $S$, if $\square$ has the entry $i$, then the box corresponding to $\square$ in ${\textup{\textsf{rightpart}}}(T)$ has the symbol $i_\ell$ for some $\ell$. The only other constraints for ${\textup{\textsf{rightpart}}}(T)$ are concerned with how often the different symbols $i_\ell$ appear. Symbols $j_k^i$ and $j_{\overline k}^i$ do not appear in ${\textup{\textsf{rightpart}}}(T)$, but only in ${\textup{\textsf{leftpart}}}(T)$. The tableau ${\textup{\textsf{leftpart}}}(T)$ is constructed in several steps, starting with a tableau obtained from a set of hypergraphs $H^{(i)}$ (similar to those hypergraphs in the case where $D$ is even), and then reordering entries within the rows.

The construction for odd $D$ has many more subtleties than the construction for even $D$ and there are numerous slight differences between the two cases. We think that the readability would suffer greatly if we did not explain the whole construction again for odd $D$ in a self-contained manner, including the parts that are very similar to the even case. Therefore in the following sections we first treat the case for even $D$ and then treat the case for odd $D$ in a fairly self-contained manner. The reader will see that much more care and attention to the details is necessary in the case where $D$ is odd.

The hypergraphs $H^{(i)}$ for even $D$ {#EVENsec:hypergraphsevenD}
======================================

Let $I := \{i \mid \varrho_i \neq 0\}$. In order to construct ${\textup{\textsf{leftpart}}}(T)$ we will first constuct a so-called $(D,\varrho_i)$-hypergraph for each $i \in I$. We refer to that hypergraph as $H^{(i)}$. The number of columns in ${\textup{\textsf{leftpart}}}(T)$ will precisely be the number of vertices in all these hypergraphs together. So we want the hypergraphs to be as small as possible.

We first recall some basic terms. Let $H = (V,E)$ by a hypergraph and $e \in E$ be an edge. Then we define the *size* of an edge ${\textup{\textsf{size}}}(e)$ as the number of vertices in $e$. Let $v,w \in V$. Then a *path* between $v$ and $w$ is a sequence of edges $(e_1,e_2,\ldots,e_l)$ such that $v \in e_1$, $w \in e_l$, and $e_i \cap e_{i+1} \neq \emptyset$. We say that two vertices are connected in $H$ iff there exists a path between them. We say that a hypergraph is *connected* iff every pair of vertices is connected. For a nonempty set $X$ a *set partition* $P$ of $X$ is a set of pairwise disjoint subsets whose union is $X$.

\[def:dkhypergraph\] Let $D,K$ be integers. A *$(D,K)$-hypergraph* is defined to be a hypergraph $H=(V,E)$ that satisfies the following properties:

1.  $H$ is connected. \[eq:def:connected\]

2.  $H$ has two different types of hyperedges: the *block edges* and the *name edges*. \[eq:def:blockandnameedges\]

3.  Each block edge has size $D$, and the set of block edges $E_{\text{Block}} \subseteq E$ is a set partition of $V$. \[eq:def:blockedgessizeD\]

4.  Each name edge has size strictly less than $D$, but at least size $1$, and the set of name edges $E_{\text{Name}} \subseteq E$ is a set partition of $V$. \[eq:def:nameedgessizelessthanD\]

5.  $|E_{\text{Name}}| - |E_{\text{Block}}| = K$.\[eq:def:nameblockdifference\]

6.  There exists a name edge $e_{\text{Name}}$ and a block edge $e_{\text{Block}}$ whose intersection contains at least 2 vertices. We choose one of these two vertices and call it the *link vertex*. \[prop:hypergraphshareblockname\]

Several examples for $(6,K)$-hypergraphs are given in Figure \[EVENfig:6Khypergraphs\].

\[EVENprop:hypergraph\] For even $D \geq 4$, $K\neq 0$, there exists a $(D,K)$-hypergraph that has exactly $\lceil \frac{K}{D-2} \rceil$ many block edges.

Let $n := \lceil \frac{K}{(D-2)} \rceil$. We start the construction by considering $n$ many disjoint block edges with $D$ many vertices each. We arrange the vertices in a linear fashion as in Figure \[EVENfig:6Khypergraphs\]. The leftmost vertex is the link vertex. We now place the vertices in $K+n$ many name edges as follows. As in Figure \[EVENfig:6Khypergraphs\], the rightmost vertex of every block edge but the last shall be placed in a size 2 name edge with the leftmost vertex of the next block edge. The resulting hypergraph is connected. At this point we have $nD-2(n-1)=n(D-2)+2$ vertices that are not in name edges yet; and we have $K+n-(n-1) = K+1$ name edges left to put vertices in. Since $$(n(D-2)+2)-(K+1) =
(\lceil \tfrac{K}{(D-2)} \rceil(D-2)+2)-(K+1)
\geq
(K+2)-(K+1) = 1 > 0,$$ we can position the name edges so that the link vertex is in a name edge of size at least $2$. Moreover, we position that name edge of size at least 2 in such a way that the link vertex has a vertex that not only lies in the same name edge, but also in the same block edge.

Construction of ${\textup{\textsf{leftpart}}}(T)$ for even $D$ {#EVENsec:rightpartevenD}
==============================================================

For each $i \in I$ let $H^{(i)}$ be a $(D,\varrho_i)$-hypergraph from Proposition \[EVENprop:hypergraph\]. We write $E_{\text{Block}}^{(i)}$ to denote its set of block edges and $E_{\text{Name}}^{(i)}$ to denote its set of name edges.

In this section, for every $i \in I$ and every $e \in E_{\text{Block}}^{(i)}$ we construct an $m \times D$ block tableau $\check B_e$ such that ${\textup{\textsf{leftpart}}}(T)$ is constructed as the concatenation $$\label{EVENeq:leftpartmadefromblocks}
{\textup{\textsf{leftpart}}}(T) := \sum_{i\in I} \sum_{e \in E_{\text{Block}}^{(i)}} \check B_e.$$ Notice that since every block edge has size $D$ (see Def. \[def:dkhypergraph\]), this implies that the number of columns in ${\textup{\textsf{leftpart}}}(T)$ is equal to the total number of vertices in the hypergraphs $H^{(i)}$, $i \in I$.

Each $m\times D$ block tableau $\check B_e$ is constructed in three steps: First we construct an $m\times D$ block tableau $B_e$ in which each column corresponds to a vertex in $H^{(i)}$, then we exchange entries between columns that correspond to link vertices.

Let $\zeta^{(i)}$ denote the link vertex in $H^{(i)}$. We attach some additional data to each $H^{(i)}$ as follows. We put a linear order on the set of name edges $E_{\text{name}}^{(i)}$ and for each vertex $v$ in $H^{(i)}$ we define $\ell(v)$ to be the index of its corresponding name edge. Here $\ell(v)=1$ if $v$ lies in the first name edge, $\ell(v)=2$ for the next name edge, and so on. We ensure that $$\label{EVENeq:ellzetaione}
\ell(\zeta^{(i)})=1.$$ In the same way, we put a linear order on the set of block edges; for each block edge $e$ we write $k(e)$ for its index and for each vertex $v$ in $H^{(i)}$ we define $k(v)$ to be the index of its corresponding block edge. We ensure that $$\label{EVENeq:kzetaione}
k(\zeta^{(i)})=1.$$ Moreover, for every vertex $v$ in any $H^{(i)}$ we define $i(v):=i$.

In the following, for each vertex $v$ we define an $m \times 1$ rectangular tableau (i.e., a column of length $m$) called $B_v$. Concatenating them results in $B_e := \sum_{v \in e} B_v$. The order of columns does not matter, but it is convenient to have the vertices of $H^{(i)}$ ordered from left to right in the same way as the columns of ${\textup{\textsf{leftpart}}}(T)$. Later we define $\check B_e$, from which we can extract $\check B_v$ for $v \in e$ as follows: If $B_v$ is the $n$-th column of $B_e$, then $\check B_v$ is the $n$-th column of $\check B_e$.

Starting with $B$ {#starting-with-b .unnumbered}
-----------------

Let $e$ be in the $k$-th block edge in $H^{(i)}$ and let $v \in e$. The column $B_v$ is defined by the following properties. $$\begin{aligned}
 \text{ the $i$-th entry of } B_v \text{ is } i_{\ell(v)} \label{EVENeq:niBv}\\
 \text{ the $j$-th entry ($j \neq i$) of } B_v \text{ is } j_{k}^{i}
 \label{EVENeq:njBv}\end{aligned}$$ An example is given in Figure \[EVENfig:exampleB\].

From $B$ to $\check B$ {#from-b-to-check-b .unnumbered}
----------------------

Most columns $B_v$ and $\check B_v$ coincide, as we define $\check B_v := B_v$ if $v \notin \{\zeta^{(i)} \mid i \in I\}$. This means that only the columns corresponding to link vertices are adjusted.

Let $h$ denote the smallest number in $I$. For $i \in I$, $i \neq h$, the column $\check B_{\zeta^{(i)}}$ arises from $B_{\zeta^{(i)}}$ by switching the $i$-th entry with the $i$-th entry in $B_{\zeta^{(h)}}$. This means that the column $\check B_{\zeta^{(h)}}$ arises from $B_{\zeta^{(i)}}$ by switching the $i$-th entry with the $i$-th entry in $B_{\zeta^{(i)}}$ for all $i \in I$.

The columnwise description of $\check B_v$ thus as follows.

-   If $v$ is not a link vertex, then $$\begin{aligned}
     \text{ the $i$-th entry of } \check B_v \text{ is } i_{\ell(v)} \label{EVENeq:iBv}\\
     \text{ the $j$-th entry ($j \neq i$) of } \check B_v \text{ is } j_{k(v)}^{(i)} \label{EVENeq:jBv}\end{aligned}$$

-   If $i \neq h$, then $$\begin{aligned}
     \text{ the $i$-th entry of } \check B_{\zeta^{(i)}} \text{ is } i_{k(v)}^h \label{EVENeq:iBzetaioneh}\\
     \text{ the $j$-th entry ($j \neq i$) of } \check B_{\zeta^{(i)}} \text{ is } j_{k(v)}^i \label{EVENeq:iBzetajoneh}\end{aligned}$$

-   Moreover, $$\begin{aligned}
     \text{ the $h$-th entry of } \check B_{\zeta^{(h)}} \text{ is } h_1 \label{EVENeq:hBzetah}\\
     \text{ for $j \neq h$, $j \in I$, the $j$-th entry of } \check B_{\zeta^{(h)}} \text{ is } j_1 \label{EVENeq:jBzetahneq}\\
     \text{ for $j \neq h$, $j \notin I$, the $j$-th entry of } \check B_{\zeta^{(h)}} \text{ is } j_{1}^h\label{EVENeq:jBzetaheq}\end{aligned}$$

An example is provided in Figure \[EVENfig:examplecheckB\].

at (0.05,0) ; at (-0.05,-1.6) [ ]{}; at (-0.05,-4.5) [ ]{};

We quickly observe the following.

\[EVENcla:acutecheck\] For $i \in I$ and a block edge $e$ in $H^{(i)}$ we have that

-   if $\zeta^{(i)} \notin e$, then $B_e = \check B_e$,

-   if $\zeta^{(i)} \in e$, $i \neq h$, then $B_e$ and $\check B_e$ differ only in a single entry: The $i$-th entry of the column $\check B_{\zeta^{(i)}}$ is $i^{h}_{1}$ instead of $i_{1}$.

This follows from and using and .

\[EVENcla:leftpart\] In each row $j$ of ${\textup{\textsf{leftpart}}}(T)$ there are only entries $j_\ell$ for some $\ell$, or $j_k^i$ for some $k$, $i$.

Recall . The claim now follows from combining , , , , , , and .

\[EVENcla:symbolsleft\] If $i \notin I$, then no symbol $i_\ell$ appears in ${\textup{\textsf{leftpart}}}(T)$ for any $\ell$. For a fixed $i \in I$, the symbol $i_\ell$ appears in ${\textup{\textsf{leftpart}}}(T)$ iff there is a vertex $v$ in $H^{(i)}$ with $\ell(v)=\ell$. Moreover, $i_\ell$ appears exactly as many times as there are vertices $v$ in $H^{(i)}$ with $\ell(v)=\ell$.

Consider and observe that ${\textup{\textsf{leftpart}}}(T)$ is obtained by a permutation of the entries of the tableau $$\sum_{i\in I} \sum_{e \in E_{\text{Block}}^{(i)}} B_e.$$ Now use and .

Construction of ${\textup{\textsf{rightpart}}}(T)$ for even $D$ {#EVENsec:constructC}
===============================================================

The tableau ${\textup{\textsf{rightpart}}}(T)$ is constructed in any way (for example in a greedy fashion) such that the following constraints are satisfied:

\[EVENeq:sameshape\] &&

$$\label{EVENeq:directreplacement}
\begin{minipage}{15.1cm}
a box in $S$ has entry $i$ iff there is some $\ell$ for which the corresponding box in ${\textup{\textsf{rightpart}}}(T)$ has entry $i_\ell$,
\end{minipage}$$

\[EVENeq:symbolsappearDtimes\] &&

\[EVENeq:allsymbolsappearleftiffright\] . &&

Such a tableau might not be unique, but we only care about its existence. The existence can be shown as follows.

Let $n(i_\ell)$ denote the number of times the symbol $i_\ell$ appears in ${\textup{\textsf{leftpart}}}(T)$. If $n(i_\ell)>0$, then Claim \[EVENcla:symbolsleft\] implies that there are $n(i_\ell)>0$ many vertices $v$ in $H^{(i)}$ with $\ell(v)=i$. By Def. \[def:dkhypergraph\] we know that $n(i_\ell)<D$. We construct ${\textup{\textsf{rightpart}}}(T)$ by arbitrarily replacing $D-n(i_\ell)$ many entries $i$ in $S$ by the symbol $i_\ell$ for each $i$, $\ell$ for which $n(i_\ell)>0$. Claim \[EVENcla:divisibility\] below shows that this procedure replaces exactly all entries of $S$ (recall that $i$ appears in $S$ exactly $D\varrho_i$ many times). It is clear that this construction satisfies , and . Since $0 < n(i_\ell) < D$ iff $0 < D-n(i_\ell) < D$, we conclude .

\[EVENcla:divisibility\] $$\forall i\in I: \quad \sum_{\ell \textup{ with } n(i_\ell)>0} (D-n(i_\ell)) = D\varrho_i.$$

Since $H^{(i)}$ satisfies Def. \[def:dkhypergraph\]\[eq:def:nameblockdifference\] we have that $$|E^{(i)}_{\text{Name}}|-|E^{(i)}_{\text{Block}}| = \varrho_i$$ and hence $$\label{EVENproof_C_*}
D|E^{(i)}_{\text{Name}}|-D|E^{(i)}_{\text{Block}}| = D\varrho_i \tag{*}.$$ Moreover Def. \[def:dkhypergraph\]\[eq:def:blockedgessizeD\] states that block edges form a set partition of $V$ and each block edge has size $D$. Together with the fact that the name edges form a set partition of $V$ (Def. \[def:dkhypergraph\]\[eq:def:nameedgessizelessthanD\]) we see that $
D|E^{(i)}_{\text{Block}}| = \sum_{e \in E_{\text{Name}}^{(i)}} {\textup{\textsf{size}}}(e).
$ Together with we obtain $
D|E^{(i)}_{\text{Name}}| - \sum_{e \in E_{\text{Name}}^{(i)}} {\textup{\textsf{size}}}(e) = D\varrho_i
$ and hence $$\sum_{e \in E_{\text{Name}}^{(i)}} (D-{\textup{\textsf{size}}}(e)) = D\varrho_i.$$

Since for each vertex $v$ in a name edge $e$ the value $\ell(v)$ is the same, we write $\ell(e):=\ell(v)$. From Claim \[EVENcla:symbolsleft\] we know that for all $e\in E_{\text{Name}}^{(i)}$ we have $n(i_{\ell(e)})={\textup{\textsf{size}}}(e)$. Therefore $$\sum_{e \in E_{\text{Name}}^{(i)}} (D-n(i_{\ell(e)})) = D\varrho_i$$

All numbers $\ell(e)$, $e \in E_{\text{Name}}^{(i)}$, are distinct by definition. Hence all symbols $i_{\ell(e)}$ are distinct. All $i_{\ell(e)}$ satisfy $n(i_{\ell(e)})>0$ by Claim \[EVENcla:symbolsleft\]. Moreover, for each $\ell$ with $n(i_\ell)>0$ there exists some $e$ with $\ell(e)=\ell$ also by Claim \[EVENcla:symbolsleft\]. Therefore we can rewrite the sum as $$\sum_{\ell \textup{ with } n(i_\ell)>0} (D-n(i_\ell)) = D\varrho_i,$$ which concludes the proof.

An example of the whole construction can be seen in Figure \[EVENfig:fullexample\].

at (-3,0) [ ]{}; at (0,0) [ ]{};

We draw some quick corollaries.

\[EVENcla:symbols\] If $i \notin I$, then the symbol $i_\ell$ does not appear in $T$ for any $\ell$. For a fixed $i \in I$, the symbol $i_\ell$ appears in $T$ iff $i_\ell$ appears in ${\textup{\textsf{leftpart}}}(T)$ iff $i_\ell$ appears in ${\textup{\textsf{rightpart}}}(T)$ iff there is a vertex $v$ in $H^{(i)}$ with $\ell(v)=\ell$.

We combine Claim \[EVENcla:symbolsleft\] and .

\[EVENcla:jki\] If a symbol $j_k^i$ appears in $T$, then it appears exactly $D$ many times in $T$.

By the symbols $j_k^i$ only appear in ${\textup{\textsf{leftpart}}}(T)$. Consider and observe that ${\textup{\textsf{leftpart}}}(T)$ is obtained by a permutation of the entries of the tableau $$\sum_{i\in I} \sum_{e \in E_{\text{Block}}^{(i)}} B_e.$$ Now use Def. \[def:dkhypergraph\], , and .

Proof of the Tableau Lifting Theorem \[thm:prolongation\] for even $D$ {#EVENsec:psipropertiesDodd}
======================================================================

In this section we prove the Tableau Lifting Theorem \[thm:prolongation\] for even $D$.

First we observe that the shape of $T$ is indeed the required shape: This follows from Proposition \[EVENprop:hypergraph\], , and the fact that $B_e$ and $\check B_e$ have the same rectangular shape $m \times D$.

We remark that every symbol in $T$ appears exactly $D$ many times: For the symbols $j_k^i$ this follows from Claim \[EVENcla:jki\]. For the symbols $i_\ell$ this follows from .

It remains to prove the parts , , and of Theorem \[thm:prolongation\]. We start with part , then build up insights that then eventually lead to the proof of parts  and .

Proof of part  of Theorem \[thm:prolongation\] {#proof-of-part-of-theoremthmprolongation .unnumbered}
----------------------------------------------

Part  of Theorem \[thm:prolongation\] is proved as follows. We choose $\varphi(i_\ell) := i$ and $\varphi(j_k^i) := j$. We observe that ${\textup{\textsf{rightpart}}}(\varphi(T))=S$, see . Since $S$ is regular, ${\textup{\textsf{rightpart}}}(\varphi(T))$ is regular. It remains to show that ${\textup{\textsf{leftpart}}}(\varphi(T))$ is also regular. From Claim \[EVENcla:leftpart\] we see that every column of ${\textup{\textsf{leftpart}}}(\varphi(T))$ contains all entries $1,\ldots,m$, sorted from top to bottom. Thus ${\textup{\textsf{leftpart}}}(\varphi(T))$ is regular. Since ${\textup{\textsf{leftpart}}}(\varphi(T))$ and ${\textup{\textsf{rightpart}}}(\varphi(T))$ are both regular, we conclude that $\varphi(T)$ is regular, which finishes the proof of part of Theorem \[thm:prolongation\].

Parts  and  of Theorem \[thm:prolongation\]: Preliminaries {#parts-and-of-theoremthmprolongation-preliminaries .unnumbered}
----------------------------------------------------------

In order to prove parts and of Theorem \[thm:prolongation\], we start with some preliminary observations.

\[EVENcla:varphii\] If $\varphi(T)$ is regular, then for each $i \in I$ we have: For every $i_\ell$ that appears in $T$, $\varphi(i_\ell)$ only depends on $i$ and does not depend on $\ell$.

By definition, for every name edge $e$ in $H^{(i)}$ the values $\ell(v)$ coincide for all $v \in e$. This trivially implies that $$\label{EVENeq:nameedgevarphicoincideNEW}
\text{for every name edge $e$ in $H^{(i)}$:
the values $\varphi(i_{\ell(v)})$ coincide for all $v \in e$.}$$

We claim that $$\label{EVENeq:blockedgevarphicoincideNEW}
\text{for every block edge $e$ in $H^{(i)}$:
the values $\varphi(i_{\ell(v)})$ coincide for all $v \in e$.}$$ Proof of : Let $k:=k(e)$. According to Def. \[def:dkhypergraph\] there exists a vertex $\xi^{(i)}\neq\zeta^{(i)}$ that has the same name edge and block edge as $\zeta^{(i)}$, i.e., $\ell(\zeta^{(i)}) = \ell(\xi^{(i)})$ and $k=k(\zeta^{(i)}) = k(\xi^{(i)})$. For each $v \in e$, $v \neq \zeta^{(i)}$ we have that the $j$-th entry ($j \neq i$) of $\check B^{(i)}_v$ is $j_k^i$, see . Moreover, the symbol that appears as the $i$-th entry of $\check B^{(i)}_v$ is $i_{\ell(v)}$, see . By construction of $T$, we have that $\check B^{(i)}_v$ is a column in $T$. Since by assumption $\varphi(T)$ is regular, it follows that $\varphi(\check B^{(i)}_v)$ is regular. Hence if $v \neq \zeta^{(i)}$, the $\varphi(j_k^i)$ are pairwise distinct. Thus $\varphi(i_{\ell(v)})$ equals the one element in $\{1,\ldots,m\} \setminus \{\varphi(j_k^i) \mid 1 \leq j \leq m, \ j\neq i\}$. This is independent of $\ell$. Hence the values $\varphi(i_{\ell(v)})$ coincide for all $v \in e$, $v \neq \zeta^{(i)}$. This proves for all $v\in e$, $v \neq \zeta^{(i)}$. Now, if $\zeta^{(i)} \in e$, then $\xi^{(i)} \in e$, for which we have $\ell(\zeta^{(i)}) = \ell(\xi^{(i)})$, and thus clearly $\varphi(i_{\ell(\zeta^{(i)})})=\varphi(i_{\ell(\xi^{(i)})})$. This proves the claim .

Since $H^{(i)}$ is connected (Def. \[def:dkhypergraph\]\[eq:def:connected\]), we conclude with and : The values $\varphi(i_{\ell(v)})$ coincide for all $v$ in $H^{(i)}$. Since the symbol $i_\ell$ appears in $T$ iff there is some vertex $v$ in $H^{(i)}$ with $\ell(v)=\ell$ (see Claim \[EVENcla:symbols\]), Claim \[EVENcla:varphii\] follows.

For $i\in I$ we define $$\label{EVENeq:defvarphii}
\varphi^{\circ}(i):=\varphi(i_1).$$ This definition is natural, because we saw in Claim \[EVENcla:varphii\] that if $\varphi(T)$ is regular, then $$\varphi^{\circ}(i)=\varphi(i_1)=\varphi(i_2)=\ldots$$

\[EVENcla:differentphiNEW\] Let $\varphi(T)$ be regular. Let $i, j \in I$, $i\neq j$. Then $\varphi^{\circ}(i)\neq \varphi^{\circ}(j)$.

The column $\check B_{\zeta^{(h)}}$ contains the symbol $i_1$ in row $i$ and the symbol $j_1$ in row $j$, see and . The fact that $\varphi(T)$ is regular implies that $\varphi(i_1)\neq\varphi(j_1)$. By this concludes the proof.

\[EVENcla:droph\] Let $\varphi(T)$ be regular. Let $i \in I$, $i \neq h$. Then $\varphi(i_1^h) = \varphi(i_1) = \varphi^{\circ}(i)$.

The last equality is . We now prove the first equality. Let $e$ be the block edge in $H^{(i)}$ that contains the link vertex $\zeta^{(i)}$. Then $\check B_e^{(i)}$ is an $m \times D$ subtableau of ${\textup{\textsf{leftpart}}}(T)$, which differs from $B_e^{(i)}$ only in a single entry in the length $m$ column corresponding to $\zeta^{(i)}$: The $i$-th entry of the column $\check B_{\zeta^{(i)}}$ is $i^{h}_{1}$ instead of $i_{1}$, see Claim \[EVENcla:acutecheck\]. Hence $\varphi(B_{\zeta^{(i)}})$ and $\varphi(\check B_{\zeta^{(i)}})$ are columns that coincide in all but at most this single box. Since $\varphi(T)$ is regular and the $\varphi(T)$ only contains entries from $\{1,\ldots,m\}$ and the columns $\varphi(B_{\zeta^{(i)}})$ and $\varphi(\check B_{\zeta^{(i)}})$ are of length $m$, we conclude that $\varphi(i^{h}_{1}) = \varphi(i_{1})$.

Proof of part  of Theorem \[thm:prolongation\] {#proof-of-part-of-theoremthmprolongation-1 .unnumbered}
----------------------------------------------

We now prove part of Theorem \[thm:prolongation\]. The tableau ${\textup{\textsf{rightpart}}}(T)$ only contains entries $i_\ell$ and no entries $j_k^i$, see . As also seen in , if ${\textup{\textsf{rightpart}}}(T)$ contains an entry $i_\ell$, then the corresponding entry of $S$ is $i$. Therefore $\varphi^{\circ}(S) = \varphi({\textup{\textsf{rightpart}}}(T))$, where we lifted the map $\varphi^{\circ} : I \to \{1,\ldots,m\}$ to a map with the same name that is defined on tableaux with entries from $I$. Claim \[EVENcla:differentphiNEW\] proves property of Theorem \[thm:prolongation\].

Proof of part  of Theorem \[thm:prolongation\] {#proof-of-part-of-theoremthmprolongation-2 .unnumbered}
----------------------------------------------

The rest of this section is devoted to proving part \[enum:duplex\] of Theorem \[thm:prolongation\]. A rectangular tableau whose columns all coincide is called *uniform*. In the following proof we will crucially use that a uniform tableau with an even number of columns is duplex. Indeed, we prove part \[enum:duplex\] of Theorem \[thm:prolongation\] by showing that if $\varphi(T)$ is regular, then for every block edge $e$:

-   $\varphi(\check B_{e})$ is uniform if $e$ does not contain any link vertex $\zeta^{(i)}$,

-   $\varphi(\check B_{e})$ is uniform if $\zeta^{(i)} \in e$ for $i \neq h$, and

-   $\varphi(\check B_{e})$ is uniform if $\zeta^{(h)} \in e$.

It is clear that these three properties cover all cases and hence $\varphi(T)$ is uniform by construction . This implies part \[enum:duplex\] of Theorem \[thm:prolongation\].

We start with proving (I).

\[EVENcla:ithentry\] Let $\varphi(T)$ be regular. Given a block edge $e$ in $H^{(i)}$. For all $v \in e$, $v \neq \zeta^{(i)}$, we have that the $i$-th entry of $\varphi(\check B_v)$ is $\varphi^{\circ}(i)$.

Combine and Claim \[EVENcla:varphii\].

\[EVENcla:jBvneqzeta\] Let $\varphi(T)$ be regular. Given a block edge $e$ in $H^{(i)}$. For all $j \neq i$ we have that the set $$\{
\text{$j$-th entry of $\varphi(\check B_v)$} \mid v \in e, v \neq \zeta^{(i)}
\}$$ consists of the single element $\varphi(j_{k(e)}^{i})$.

This follows from .

Combining Claim \[EVENcla:ithentry\] and Claim \[EVENcla:jBvneqzeta\] we see that (I) is true.

We now prove (II). Let $i \neq h$ and let $e$ be the block edge in $H^{(i)}$ that contains $\zeta^{(i)}$. Note that $k(e)=1$.

\[EVENcla:almostexceptionalcolumn\] Let $\varphi(T)$ be regular. Then $\varphi(\check B_{\zeta^{(i)}})$ coincides with $\varphi(\check B_v)$, $v \in e$, $i \neq h$.

We compare the columns entrywise. Note that $k(v)=k(\zeta^{(i)})=1$. We make a case distinction.

Case 1: Let $j \neq i$. The $j$-th entry of $\check B_v$ is $j_{1}^i$, see . The $j$-th entry of $\check B_{\zeta^{(i)}}$ is $j_{1}^i$, see . Hence the $j$-th entry of $\varphi(\check B_v)$ equals the $j$-th entry of $\varphi(\check B_{\zeta^{(i)}})$.

Case 2: The $i$-th entry of $\check B_v$ is $i_1$, see . The $i$-th entry of $\check B_{\zeta^{(i)}}$ is $i_1^h$, see . Hence Claim \[EVENcla:droph\] implies that the $i$-th entry of $\varphi(\check B_v)$ equals the $i$-th entry of $\varphi(\check B_{\zeta^{(i)}})$.

It follows from Claim \[EVENcla:almostexceptionalcolumn\] that all columns in $\varphi(\check B_e)$ coincide, i.e., $\varphi(\check B_e)$ is uniform. Thus (II) is proved.

It remains to show (III), i.e., that $\varphi(\check B_{e})$ is uniform if $\zeta^{(h)} \in e$.

\[EVENcla:hthentry\] Let $\varphi(T)$ be regular and $\zeta^{(h)}$ the link vertex in the block edge $e$. For all $v \in e$, $v \neq \zeta^{(h)}$, we have that the $h$-th entry of $\varphi(\check B_v)$ is $\varphi^{\circ}(h)$.

This is a direct implication of Claim \[EVENcla:ithentry\].

\[EVENcla:exceptionalcolumn\] Let $\varphi(T)$ be regular and $\zeta^{(h)} \in e$. Then $\varphi(\check B_{\zeta^{(h)}})$ coincides with $\varphi(\check B_{v})$, $v \in e$.

We compare the columns entrywise, considering three cases.

Case 1: We compare the $h$-th entry: According to Claim \[EVENcla:hthentry\], the $h$-th entry of $\varphi(\check B_{v})$ is $\varphi^{\circ}(h)$. According to the $h$-th entry of $\check B_{\zeta^{(h)}}$ is $h_1$, so the $h$-th entry of $\varphi(\check B_{\zeta^{(h)}})$ is $\varphi(h_1)=\varphi^{\circ}(h)$, see .

Case 2: We compare the $j$-th entry, $j \neq h$, in the case $j \notin I$: According to , the $j$-th entry of $\check B_{v}$ is $j_1^{h}$. The $j$-th entry of $\check B_{\zeta^{(h)}}$ is also $j_1^{h}$, see . Therefore the $j$-th entry of $\varphi(\check B_{v})$ equals the $j$-th entry of $\varphi(\check B_{\zeta^{(h)}})$.

Case 3: We compare the $j$-th entry, $j \neq h$, in the case $j\in I$: According to , the $j$-th entry of $\check B_{v}$ is $j_1^{h}$. The $j$-th entry of $\check B_{\zeta^{(h)}}$ is $j_1$, see . Claim \[cla:droph\] shows that the $j$-th entry of $\varphi(\check B_{v})$ equals the $j$-th entry of $\varphi(\check B_{\zeta^{(h)}})$.

It follows from Claim \[EVENcla:exceptionalcolumn\] that all columns in $\varphi(\check B_e)$ coincide, i.e., $\varphi(\check B_e)$ is uniform. Thus (III) is proved. This finishes the proof of part \[enum:duplex\] of Theorem \[thm:prolongation\].

Theorem \[thm:prolongation\] is now completely proved for even $D$.

The hypergraphs $H^{(i)}$ for odd $D$ {#sec:hypergraphsoddD}
=====================================

Let $I := \{i \mid \varrho_i \neq 0\}$. In order to construct ${\textup{\textsf{leftpart}}}(T)$ we will first construct a so-called $(D,\varrho_i)$-paired-hypergraph for each $i \in I$. The number of columns in ${\textup{\textsf{leftpart}}}(T)$ will be precisely the number of vertices in all these hypergraphs together. So we want the hypergraphs to be as small as possible.

We will need the basic terms from section \[EVENsec:hypergraphsevenD\]. Moreover, we will need the definition of a $(D,K)$-hypergraph (Def. \[def:dkhypergraph\]).

\[def:dkpairedhypergraph\] Let $D,K$ be integers. A *$(D,K)$-paired-hypergraph* is defined to be a $(D,K)$-hypergraph $H=(V,E)$ that satisfies the following additional property: $$\begin{minipage}{\textwidth-2cm}
Each block edge $e \in E_{\text{Block}}$ is paired with another block edge $\overline{e} \in E_{\text{Block}}$ such that they are connected by a name edge, i.e., there are vertices $v \in e$ and $\overline{v} \in \overline{e}$ called \emph{bridge vertices} and a name edge $e_{\text{Name}} \in E_{\text{Name}}$ such that $v,\overline{v} \in e_{\text{Name}}$. In other words, the set of block edges can be written as a disjoint union of sets of cardinality two such that the elements of each of the sets are connected by a name edge.
        \end{minipage}
         \label{eq:hypergraphoddpairs}$$

Several examples for $(5,K)$-paired-hypergraphs are given in Figure \[fig:5Kpairedhypergraphs\]. For a block edge $e$ we write $\overline e$ to denote the other block edge in its pair, and $\overline{\overline e} = e$.

\[prop:hypergraphodd\] For odd $D \geq 3$, $K \neq 0$, there exists a $(D,K)$-paired-hypergraph that has exactly $2\lceil \frac{K}{2(D-2)} \rceil$ many block edges.

Let $n := 2\lceil \frac{K}{2(D-2)} \rceil$. We start the construction by considering $n$ many disjoint block edges with $D$ many vertices each. We arrange the vertices in a linear fashion as in Figure \[fig:5Kpairedhypergraphs\]. The leftmost vertex is the link vertex. We now place these vertices in $K+n$ many name edges as follows. As in Figure \[fig:5Kpairedhypergraphs\], the rightmost vertex of every block edge but the last shall be placed in a size 2 name edge with the leftmost vertex of the next block edge. The resulting hypergraph is connected. The rightmost vertex of every odd block edge and the leftmost vertex of every even block edge are bridge vertices. At this point we have $nD-2(n-1)=n(D-2)+2$ vertices that are not in name edges yet; and we have $K+n-(n-1) = K+1$ name edges left to put vertices in. Since $$(n(D-2)+2)-(K+1) =
(2\lceil \tfrac{K}{2(D-2)} \rceil(D-2)+2)-(K+1)
\geq
(K+2)-(K+1) = 1 > 0,$$ we can position the name edges so that the link vertex is in a name edge of size at least $2$. Moreover, we position that name edge of size at least 2 in such a way that the link vertex has a vertex that not only lies in the same name edge, but also in the same block edge.

Construction of ${\textup{\textsf{leftpart}}}(T)$ for odd $D$ {#sec:rightpartoddD}
=============================================================

For each $i \in I$ let $H^{(i)}$ be the $(D,\varrho_i)$-paired-hypergraph from Proposition \[prop:hypergraphodd\]. We write $E_{\text{Block}}^{(i)}$ to denote its set of block edges and $E_{\text{Name}}^{(i)}$ to denote its set of name edges.

In this section, for every $i \in I$ and every $e \in E_{\text{Block}}^{(i)}$ we construct an $m \times D$ block tableau $\check B_e$ such that ${\textup{\textsf{leftpart}}}(T)$ is constructed as the concatenation $$\label{eq:leftpartmadefromblocks}
{\textup{\textsf{leftpart}}}(T) := \sum_{i\in I} \sum_{e \in E_{\text{Block}}^{(i)}} \check B_e.$$ Notice that since every block edge has size $D$ (see Def. \[def:dkhypergraph\]), this implies that the number of columns in ${\textup{\textsf{leftpart}}}(T)$ is equal to the sum of numbers of vertices in the hypergraphs $H^{(i)}$, $i \in I$.

Each $m\times D$ block tableau $\check B_e$ is constructed in three steps: First we construct an $m\times D$ block tableau $B_e$, then we modify its entries to $\acute B_e$, and the we make final adjustments to the entries to obtain $\check B_e$.

Let $\zeta^{(i)}$ denote the link vertex in $H^{(i)}$. We attach some additional data to each $H^{(i)}$ as follows. We put a linear order on the set of name edges $E_{\text{name}}^{(i)}$ and for each vertex $v$ in $H^{(i)}$ we define $\ell(v)$ to be the index of its corresponding name edge. Here $\ell(v)=1$ if $v$ lies in the first name edge, $\ell(v)=2$ for the next name edge, and so on. We ensure that $$\label{eq:ellzetaione}
\ell(\zeta^{(i)})=1.$$ In the same way, we put a linear order on the set of block edge pairs; for each block edge $e$ we write $k(e)$ for the index of its corresponding block edge pair and for each vertex $v$ in $H^{(i)}$ we define $k(v)$ to be the index of its corresponding block edge pair. We ensure that $$\label{eq:kzetaione}
k(\zeta^{(i)})=1.$$ Moreover, for every vertex $v$ in any $H^{(i)}$ we define $i(v):=i$.

In the following, for each vertex $v$ we define an $m \times 1$ rectangular tableau (i.e., a column of length $m$) called $B_v$. Concatenating them results in $B_e$: $B_e := \sum_{v \in e} B_v$. The order of columns does not matter. Analogously, later we define $\acute B_e := \sum_{v \in e} \acute B_v$ and $\check B_e := \sum_{v \in e} \check B_v$.

Starting with $B$ {#starting-with-b-1 .unnumbered}
-----------------

For each block edge pair we choose one block edge to be the *barred* block edge, and the other one to be the *unbarred* block edge.

Let $e$ be in the $k$-th pair of block edges in $H^{(i)}$ and let $v \in e$. The column $B_v$ is defined by the following properties. $$\begin{aligned}
 \text{ the $i$-th entry of } B_v \text{ is } i_{\ell(v)} \label{eq:niBv}\\
 \text{ the $j$-th entry ($j \neq i$) of } B_v \text{ is } \begin{cases}
                                                            j_{k}^{i} & \text{ if } e \text{ is unbarred} \\
                                                            j_{\overline k}^{i} & \text{ if } e \text{ is barred} \\
                                                           \end{cases}
 \label{eq:njBv}\end{aligned}$$ An example is given in Figure \[fig:exampleB\].

From $B$ to $\acute B$ {#from-b-to-acute-b .unnumbered}
----------------------

Fix $i \in I$. To go from $B_e$ to $\acute B_e$ we switch some entries $j_k^{i}$ to $j_{\overline k}^{i}$ and vice versa. We do this by considering the concatenation $B_e+B_{\overline{e}}$ and permuting some entries within the rows of this $m \times (2D)$ block tableau to obtain $\acute B_e+\acute B_{\overline{e}}$. For each $1 \leq k \leq |E_{\text{Block}}^{(i)}|$, let $\{e,\overline e\}$ denote the $k$-th pair of block edges in $H^{(i)}$ and choose a set of $m-1$ many distinct cardinality $D$ subsets ${\textup{\textsf{barred}}}(i,j,k)$ of the vertex set $e \cup \overline e$ such that $$\label{eq:bridgebar}
\begin{minipage}{16cm}
one of the two bridge vertices is contained in \emph{all} the $m-1$ many sets ${\textup{\textsf{barred}}}(i,j,k)$, $1 \leq j \leq m$, $j \neq i$, and the other bridge vertex is contained in \emph{none} of those sets.
\end{minipage}$$

We define $${\textup{\textsf{k-bar}}}(i,j,v) := \begin{cases}
                 \overline{k(v)} & \text{ if } v \in {\textup{\textsf{barred}}}(i,j,k(v)) \\
                 k(v) & \text{otherwise}
                \end{cases}.$$ Now we define $$\begin{aligned}
 \text{ the $i$-th entry of } \acute B_v \text{ is } i_{\ell(v)}  \label{eq:acuteiBv}\\
 \text{ the $j$-th entry ($j \neq i$) of } \acute B_v \text{ is } j_{{\textup{\textsf{k-bar}}}(i,j,v)}^{i}\label{eq:acutejBv}\end{aligned}$$

An example is provided in Figure \[fig:exampleacuteB\].

Since the sets ${\textup{\textsf{barred}}}(i,j,k)$ have cardinality $D$, it follows: For $i \in I$ and a block edge $e\in H^{(i)}$ we have that $$\label{eq:shuffleacute}
 B_e+B_{\overline e} \text{ and } \acute B_e+\acute B_{\overline e} \text{ differ only by permutations of boxes within rows, while row $i$ stays the same.}$$ For $1 \leq j \leq m$, $j \neq i$, it is now straightforward to see that $$\label{eq:Dmanysymbols}
\text{${B}_{e} + {B}_{\overline e}$ contains exactly the symbols $j_k^i$ and $j_{\overline k}^i$, both exactly $D$ many times.}$$

We state another insight at this point: In $H^{(i)}$, for the pair of bridge vertices $v$, $w$ of the $k$-th block edge pair pair we have that $$\label{eq:bridge}
\text{$\acute B_v + \acute B_w$ contains all symbols from $S$},$$ where $S := \{j_k^i \mid 1 \leq j \leq m, j \neq i\} \cup \{j_{\overline k}^i \mid 1 \leq j \leq m, j \neq i\}$.

This follows from combining and : For all $j \neq i$ we have that $j_k^i$ is the $j$-th entry of $\acute B_v$ and $j_{\overline k}^i$ is the $j$-th entry of $\acute B_w$ (or vice versa).

From $\acute B$ to $\check B$ {#from-acute-b-to-check-b .unnumbered}
-----------------------------

Most columns $\acute B_v$ and $\check B_v$ coincide, as we define $\check B_v := \acute B_v$ if $v \notin \{\zeta^{(i)} \mid i \in I\}$. This means that only the columns corresponding to link vertices are adjusted.

Let $h$ denote the smallest number in $I$. For $i \in I$, $i \neq h$, the column $\check B_{\zeta^{(i)}}$ arises from $\acute B_{\zeta^{(i)}}$ by switching the $i$-th entry with the $i$-th entry in $\acute B_{\zeta^{(h)}}$. This means that the column $\check B_{\zeta^{(h)}}$ arises from $\acute B_{\zeta^{(i)}}$ by switching the $i$-th entry with the $i$-th entry in $\acute B_{\zeta^{(i)}}$ for all $i \in I$.

The columnwise description of $\check B_v$ thus as follows.

-   If $v$ is not a link vertex, then $$\begin{aligned}
     \text{ the $i$-th entry of } \check B_v \text{ is } i_{\ell(v)} \label{eq:iBv}\\
     \text{ the $j$-th entry ($j \neq i$) of } \check B_v \text{ is } j_{{\textup{\textsf{k-bar}}}(i,j,v)}^{(i)} \label{eq:jBv}\end{aligned}$$

-   If $i \neq h$, then $$\begin{aligned}
     \text{ the $i$-th entry of } \check B_{\zeta^{(i)}} \text{ is } i_{{\textup{\textsf{k-bar}}}(h,i,\zeta^{(i)})}^h \label{eq:iBzetaioneh}\\
     \text{ the $j$-th entry ($j \neq i$) of } \check B_{\zeta^{(i)}} \text{ is } j_{{\textup{\textsf{k-bar}}}(i,j,\zeta^{(i)})}^i \label{eq:iBzetajoneh}\end{aligned}$$

-   Moreover, $$\begin{aligned}
     \text{ the $h$-th entry of } \check B_{\zeta^{(h)}} \text{ is } h_1 \label{eq:hBzetah}\\
     \text{ for $j \neq h$, $j \in I$, the $j$-th entry of } \check B_{\zeta^{(h)}} \text{ is } j_1 \label{eq:jBzetahneq}\\
     \text{ for $j \neq h$, $j \notin I$, the $j$-th entry of } \check B_{\zeta^{(h)}} \text{ is } j_{{\textup{\textsf{k-bar}}}(h,j,\zeta^{(h)})}^h\label{eq:jBzetaheq}\end{aligned}$$

An example is provided in Figure \[fig:examplecheckB\].

We quickly observe the following.

\[cla:acutecheck\] For $i \in I$ and a block edge $e\in H^{(i)}$ we have that

-   if $\zeta^{(i)} \notin e$, then $\acute B_e = \check B_e$,

-   if $\zeta^{(i)} \in e$, $i \neq h$, then $\acute B_e$ and $\check B_e$ differ only in a single entry: The $i$-th entry of the column $\check B_{\zeta^{(i)}}$ is $i^{h}_{1}$ or $i^{h}_{\overline 1}$ instead of $i_{1}$.

This follows from and using and .

\[cla:leftpart\] In each row $j$ of ${\textup{\textsf{leftpart}}}(T)$ there are only entries $j_\ell$ for some $\ell$, or $j_k^i$ or $j_{\overline k}^i$ for some $k$, $i$.

Recall . The claim now follows from combining , , , , , , and .

\[cla:symbolsleft\] If $i \notin I$, then no symbol $i_\ell$ appears in ${\textup{\textsf{leftpart}}}(T)$ for any $\ell$. For a fixed $i \in I$, the symbol $i_\ell$ appears in ${\textup{\textsf{leftpart}}}(T)$ iff there is a vertex $v$ in $H^{(i)}$ with $\ell(v)=\ell$. Moreover, $i_\ell$ appears exactly as many times as there are vertices $v$ in $H^{(i)}$ with $\ell(v)=\ell$.

Consider and observe that ${\textup{\textsf{leftpart}}}(T)$ is obtained by a permutation of the box entries of the tableau $$\sum_{i\in I} \sum_{e \in E_{\text{Block}}^{(i)}} B_e.$$ Now use and .

Construction of ${\textup{\textsf{rightpart}}}(T)$ for odd $D$ {#sec:constructC}
==============================================================

The tableau ${\textup{\textsf{rightpart}}}(T)$ is constructed in any way (for example in a greedy fashion) such that the following constraints are satisfied:

\[eq:sameshape\] &&

$$\label{eq:directreplacement}
\begin{minipage}{15.1cm}
a box in $S$ has entry $i$ iff there is some $\ell$ for which the corresponding box in ${\textup{\textsf{rightpart}}}(T)$ has entry $i_\ell$,
\end{minipage}$$

\[eq:symbolsappearDtimes\] &&

\[eq:allsymbolsappearleftiffright\] . &&

Such a tableau might not be unique, but we only care about its existence. The existence can be shown as follows.

Let $n(i_\ell)$ denote the number of times the symbol $i_\ell$ appears in ${\textup{\textsf{leftpart}}}(T)$. If $n(i_\ell)>0$, then Claim \[cla:symbolsleft\] implies that there are $n(i_\ell)>0$ many vertices $v$ in $H^{(i)}$ with $\ell(v)=i$. Using Def. \[def:dkhypergraph\] we see that $n(i_\ell)<D$. We construct ${\textup{\textsf{rightpart}}}(T)$ by arbitrarily replacing $D-n(i_\ell)$ many entries $i$ in $S$ by the symbol $i_\ell$ for each $i$, $\ell$ for which $n(i_\ell)>0$. This replaces exactly all entries of $S$, as Claim \[cla:divisibility\] below shows (recall that $i$ appears in $S$ exactly $D\varrho_i$ many times). It is clear that this construction satisfies , and . Since $0 < n(i_\ell) < D$ iff $0 < D-n(i_\ell) < D$, we conclude .

\[cla:divisibility\] $$\forall i\in I: \quad \sum_{\ell \textup{ with } n(i_\ell)>0} (D-n(i_\ell)) = D\varrho_i.$$

Since $H^{(i)}$ satisfies Def. \[def:dkhypergraph\]\[eq:def:nameblockdifference\] we have that $$|E^{(i)}_{\text{Name}}|-|E^{(i)}_{\text{Block}}| = \varrho_i$$ and hence $$\label{proof_C_*}
D|E^{(i)}_{\text{Name}}|-D|E^{(i)}_{\text{Block}}| = D\varrho_i \tag{*}.$$ Moreover Def. \[def:dkhypergraph\]\[eq:def:blockedgessizeD\] states that block edges form a set partition of $V$ and each block edge has size $D$. Together with the fact that the name edges form a set partition of $V$ (Def. \[def:dkhypergraph\]\[eq:def:nameedgessizelessthanD\]) we see that $
D|E^{(i)}_{\text{Block}}| = \sum_{e \in E_{\text{Name}}^{(i)}} {\textup{\textsf{size}}}(e).
$ Together with we obtain $
D|E^{(i)}_{\text{Name}}| - \sum_{e \in E_{\text{Name}}^{(i)}} {\textup{\textsf{size}}}(e) = D\varrho_i
$ and hence $$\sum_{e \in E_{\text{Name}}^{(i)}} (D-{\textup{\textsf{size}}}(e)) = D\varrho_i.$$

Since for each vertex $v$ in a name edge $e$ the value $\ell(v)$ is the same, we write $\ell(e):=\ell(v)$. From Claim \[cla:symbolsleft\] we know that for all $e\in E_{\text{Name}}^{(i)}$ we have $n(i_{\ell(e)})={\textup{\textsf{size}}}(e)$. Therefore $$\sum_{e \in E_{\text{Name}}^{(i)}} (D-n(i_{\ell(e)})) = D\varrho_i$$

All numbers $\ell(e)$, $e \in E_{\text{Name}}^{(i)}$, are distinct by definition. Hence all symbols $i_{\ell(e)}$ are distinct. All $i_{\ell(e)}$ satisfy $n(i_{\ell(e)})>0$ by Claim \[cla:symbolsleft\]. Moreover, for each $\ell$ with $n(i_\ell)>0$ there exists some $e$ with $\ell(e)=\ell$ also by Claim \[cla:symbolsleft\]. Therefore we can rewrite the sum as $$\sum_{\ell \textup{ with } n(i_\ell)>0} (D-n(i_\ell)) = D\varrho_i,$$ which concludes the proof.

An example of the whole construction can be seen in Figure \[fig:fullexample\].

We draw some quick corollaries.

\[cla:symbols\] If $i \notin I$, then the symbol $i_\ell$ does not appear in $T$ for any $\ell$. For a fixed $i \in I$, the symbol $i_\ell$ appears in $T$ iff $i_\ell$ appears in ${\textup{\textsf{leftpart}}}(T)$ iff $i_\ell$ appears in ${\textup{\textsf{rightpart}}}(T)$ iff there is a vertex $v$ in $H^{(i)}$ with $\ell(v)=\ell$.

We combine Claim \[cla:symbolsleft\] and .

\[cla:jki\] If a symbol $j_k^i$ or $j_{\overline{k}}^i$ appears in $T$, then it appears exactly $D$ many times in $T$.

By the symbols $j_k^i$ and $j_{\overline{k}}^i$ only appear in ${\textup{\textsf{leftpart}}}(T)$. Consider and observe that ${\textup{\textsf{leftpart}}}(T)$ is obtained by a permutation of the box entries of the tableau $$\sum_{i\in I} \sum_{e \in E_{\text{Block}}^{(i)}} B_e.$$ Now use Def. \[def:dkpairedhypergraph\], , and .

Proof of the Tableau Lifting Theorem \[thm:prolongation\] for odd $D$ {#sec:psipropertiesDodd}
=====================================================================

In this section we prove the Tableau Lifting Theorem \[thm:prolongation\] for odd $D$.

First we observe that the shape of $T$ is indeed the required shape: This follows from Proposition \[prop:hypergraphodd\], , and the fact that $B_e$ and $\check B_e$ have the same rectangular shape $m \times D$.

We remark that every symbol in $T$ appears exactly $D$ many times: For the symbols $j_k^i$ and $j_{\overline{k}}^i$ this follows from Claim \[cla:jki\]. For the symbols $i_\ell$ this follows from .

It remains to prove the parts , , and of Theorem \[thm:prolongation\]. We start with part , then build up insights that then eventually lead to the proof of part  and .

Proof of part  of Theorem \[thm:prolongation\] {#proof-of-part-of-theoremthmprolongation-3 .unnumbered}
----------------------------------------------

Part  of Theorem \[thm:prolongation\] is proved as follows. We choose $\varphi(i_\ell) := i$ and $\varphi(j_k^i) := j$ and $\varphi(j_{\overline k}^i) := j$. We observe that ${\textup{\textsf{rightpart}}}(\varphi(T))=S$, see . Since $S$ is regular, ${\textup{\textsf{rightpart}}}(\varphi(T))$ is regular. It remains to show that ${\textup{\textsf{leftpart}}}(\varphi(T))$ is also regular. From Claim \[cla:leftpart\] we see that every column of ${\textup{\textsf{leftpart}}}(\varphi(T))$ contains all entries $1,\ldots,m$, sorted from top to bottom. Thus ${\textup{\textsf{leftpart}}}(\varphi(T))$ is regular. Since ${\textup{\textsf{leftpart}}}(\varphi(T))$ and ${\textup{\textsf{rightpart}}}(\varphi(T))$ are both regular, we conclude that $\varphi(T)$ is regular, which finishes the proof of part of Theorem \[thm:prolongation\].

Parts  and  of Theorem \[thm:prolongation\]: Preliminaries {#parts-and-of-theoremthmprolongation-preliminaries-1 .unnumbered}
----------------------------------------------------------

In order to prove parts and of Theorem \[thm:prolongation\], we start with some preliminary observations.

\[cla:barcoincide\] If $\varphi(T)$ is regular, then for each $i \in I$, $j \neq i$, $k$ we have: $\varphi(j_k^i) = \varphi(j_{\overline k}^i)$.

Fix $i,k$, but do not fix $j$. For notational convenience we define $\acute B := \acute B_{e} + \acute B_{\overline e}$. Let $$S := \{j_k^i \mid j \neq i\} \cup \{j_{\overline k}^i \mid j \neq i\}$$ denote the set of symbols in $\acute B$ in all rows $j \neq i$ (which is the same as the set of symbols in $B_e + B_{\overline e}$ in all rows $j \neq i$, see ). Note that $|S| = 2(m-1) = 2m-2$. Since ${B}_{e} + {B}_{\overline e}$ contains exactly the symbols $j_k^i$ and $j_{\overline k}^i$, both exactly $D$ many times (see ), the same is true for row $j$ of $\acute{B}$ (again, by ).

The tableau $\check B_{e} + \check B_{\overline e}$ differs from $\acute B$ iff $\zeta^{(i)} \in e \cup \overline e$. In this case all differences are in the column that corresponds to the link vertex $\zeta^{(i)}$ (see Claim \[cla:acutecheck\]).

If $\zeta^{(i)} \in e \cup \overline e$, then define $\acute B'$ as the $m \times (2D-1)$ tableau that is obtained from $\acute B$ by removing the column corresponding to $\zeta^{(i)}$. Note that $\zeta^{(i)}$ is not a bridge vertex. If $\zeta^{(i)} \notin e \cup \overline e$, then define $\acute B'$ as the $m \times (2D-1)$ tableau that is obtained from $\acute B$ by removing a single arbitrary column that does not correspond to a bridge vertex.

A symbol $s \in S$ is called *abound* if it appears $D$ many times in $\acute B'$. If $s \in S$ appears $D-1$ many times in $\acute B'$, then $s$ is called *scarce*. Note that each $s\in S$ is either abound or scarce.

Note that $\acute B'$ is a subtableau of $T$ and hence $\varphi(\acute B')$ is regular. Let $v,w$ denote the two bridge vertices. Since by definition they lie in the same name edge, we have $\ell(v)=\ell(w)$. Let $\ell := \ell(v)$. Note that $\acute B_v$ and $\acute B_w$ both have the symbol $i_\ell$ in row $i$, see . Since $\varphi(\acute B_v + \acute B_w)$ is regular and since the rows $j\neq i$ of $\acute B_v + \acute B_w$ contains all symbols from $S$ (see ), it follows that $$\label{eq:P}
\forall s \in S: \ \varphi(s) \in \underbrace{\{1,\ldots,m\}\setminus\{\varphi(i_\ell)\}}_{=: P}.$$ Note that $|P| = m-1$.

Two symbols $s,t \in S$ are called *partners* if $s$ appears exactly in those columns of $\acute B$ in which $t$ does not appear. In this case (by construction) we have $s=j_k^i$ and $t=j_{\overline k}^i$, or $t=j_k^i$ and $s=j_{\overline k}^i$. If two symbols $s,t$ are not partners, then there exists a column in $\acute B$ that contains both $s$ and $t$, because both $s$ and $t$ appear in exactly $D$ many columns in the shape $m\times (2D)$ tableau $\acute B$.

Clearly, for each partnership one partner is abound and the other is scarce.

Since $\varphi(B')$ has shape $m \times (2D-1)$, every symbol from $\{1,\ldots,m\}$ appears exactly $2D-1$ times in $\varphi(B')$. Therefore for every symbol $p \in P$ there is at most one abound symbol $s \in S$ with $\varphi(s)=p$. Since $S$ contains $m-1$ many abound symbols, from it follows that for each $p \in P$ there is *exactly* one abound symbol $s \in S$ with $\varphi(s)=p$. Having seen this, it follows that for each $p\in P$ there is at most one scarce symbol $t \in S$ with $\varphi(s)=p$. Again, since $S$ contains $m-1$ many scarce symbols and because of , there is *exactly* one scarce symbol $t \in S$ with the property that $\varphi(t)=p$.

Given an abound symbol $s \in S$ and a symbol $t\in S$ that is not the partner of $s$, then in $\acute B'$ there is a column that contains both $s$ and $t$. Therefore $\varphi(s)\neq \varphi(t)$ if $s$ is abound and $t$ is not the partner of $s$. We conclude that for every $p \in P$ there is exactly one abound $s \in S$ and its scarce partner $t\in S$ that have $\varphi(s)=\varphi(t) = p$. This implies the claim.

\[cla:varphii\] If $\varphi(T)$ is regular, then for each $i \in I$ we have: For every $i_\ell$ that appears in $T$, $\varphi(i_\ell)$ only depends on $i$ and does not depend on $\ell$.

By definition, for every name edge $e$ in $H^{(i)}$ the values $\ell(v)$ coincide for all $v \in e$. This trivially implies that $$\label{eq:nameedgevarphicoincideNEW}
\text{for every name edge $e$ in $H^{(i)}$:
the values $\varphi(i_{\ell(v)})$ coincide for all $v \in e$.}$$

We claim that $$\label{eq:blockedgevarphicoincideNEW}
\text{for every block edge $e$ in $H^{(i)}$:
the values $\varphi(i_{\ell(v)})$ coincide for all $v \in e$.}$$ Proof: Let $k:=k(e)$. According to Def. \[def:dkhypergraph\] there exists a vertex $\xi^{(i)}\neq\zeta^{(i)}$ that has the same name edge and block edge as $\zeta^{(i)}$, i.e., $\ell(\zeta^{(i)}) = \ell(\xi^{(i)})$ and $k=k(\zeta^{(i)}) = k(\xi^{(i)})$. For each $v \in e$, $v \neq \zeta^{(i)}$ we have that from each of the $m-1$ sets $\{j_k^i,j_{\overline k}^i\}$, $1\leq j \leq m$, $j \neq i$, there is one symbol in the column $\check B^{(i)}_v$, see . Moreover, the symbol that appears as the $i$-th entry of $\check B^{(i)}_v$ is $i_{\ell(v)}$, see . Since $\varphi(T)$ is regular, Claim \[cla:barcoincide\] implies that $\varphi(j_k^i)=\varphi(j_{\overline k}^i)$, which we will use implicitly in the upcoming argument. For each $v \neq \zeta^{(i)}$ we have that $\check B^{(i)}_v$ is a column in $T$. In this case, since by assumption $\varphi(T)$ is regular, it follows that $\varphi(\check B^{(i)}_v)$ is regular and hence the $\varphi(j_k^i)$ are pairwise distinct. Thus $\varphi(i_{\ell(v)})$ equals the one element in $\{1,\ldots,m\} \setminus \{\varphi(j_k^i) \mid 1 \leq j \leq m, \ j\neq i\}$, which is independent of $\ell$. This implies that the values $\varphi(i_{\ell(v)})$ coincide for all $v \in e$, $v \neq \zeta^{(i)}$. This proves for all $v\in e$, $v \neq \zeta^{(i)}$. Now, if $\zeta^{(i)} \in e$, then $\xi^{(i)} \in e$, for which we have $\ell(\zeta^{(i)}) = \ell(\xi^{(i)})$, and thus clearly $\varphi(i_{\ell(\zeta^{(i)})})=\varphi(i_{\ell(\xi^{(i)})})$. This proves the claim .

Since $H^{(i)}$ is connected (Def. \[def:dkhypergraph\]\[eq:def:connected\]), we conclude with and : The values $\varphi(i_{\ell(v)})$ coincide for all $v$ in $H^{(i)}$. Since the symbol $i_\ell$ appears in $T$ iff there is some vertex $v$ in $H^{(i)}$ with $\ell(v)=\ell$ (see Claim \[cla:symbols\]), Claim \[cla:varphii\] follows.

For $i\in I$ we define $$\label{eq:defvarphii}
\varphi^{\circ}(i):=\varphi(i_1).$$ This definition is natural, because we saw in Claim \[cla:varphii\] that if $\varphi(T)$ is regular, then $$\varphi^{\circ}(i)=\varphi(i_1)=\varphi(i_2)=\ldots$$

\[cla:differentphiNEW\] Let $\varphi(T)$ be regular. Let $i, j \in I$, $i\neq j$. Then $\varphi^{\circ}(i)\neq \varphi^{\circ}(j)$.

The column $\check B_{\zeta^{(h)}}$ contains the symbol $i_1$ in row $i$ and the symbol $j_1$ in row $j$, see and . The fact that $\varphi(T)$ is regular implies that $\varphi(i_1)\neq\varphi(j_1)$. By definition , this concludes the proof.

\[cla:droph\] Let $\varphi(T)$ be regular. Let $i \in I$, $i \neq h$. Then $\varphi(i_{\overline 1}^h) = \varphi(i_1^h) = \varphi(i_1) = \varphi^{\circ}(i)$.

The first equality follows from Claim \[cla:barcoincide\]. The last equality is . We now prove the second equality. Let $e$ be the block edge in $H^{(i)}$ that contains the link vertex $\zeta^{(i)}$. Then $\check B_e^{(i)}$ is an $m \times D$ subtableau of ${\textup{\textsf{leftpart}}}(T)$, which differs from $\acute B_e^{(i)}$ only in a single entry in the length $m$ column corresponding to $\zeta^{(i)}$: The $i$-th entry of the column $\check B_{\zeta^{(i)}}$ is $i^{h}_{1}$ or $i^{h}_{\overline 1}$ instead of $i_{1}$, see Claim \[cla:acutecheck\]. Hence $\varphi(\acute B_{\zeta^{(i)}})$ and $\varphi(\check B_{\zeta^{(i)}})$ are columns that coincide in all but at most this single box. Since $\varphi(T)$ is regular and the $\varphi(T)$ only contains entries from $\{1,\ldots,m\}$ and the columns $\varphi(\acute B_{\zeta^{(i)}})$ and $\varphi(\check B_{\zeta^{(i)}})$ are of length $m$, we conclude with Claim \[cla:barcoincide\] (i.e., $\varphi(i^{h}_{1})=\varphi(i^{h}_{\overline 1})$) that $\varphi(i^{h}_{1}) = \varphi(i_{1})$.

Proof of part  of Theorem \[thm:prolongation\] {#proof-of-part-of-theoremthmprolongation-4 .unnumbered}
----------------------------------------------

We now prove part of Theorem \[thm:prolongation\]. The tableau ${\textup{\textsf{rightpart}}}(T)$ only contains entries $i_\ell$ and no entries $j_k^i$ or $j_{\overline k}^i$, see . As also seen in , if ${\textup{\textsf{rightpart}}}(T)$ contains an entry $i_\ell$, then the corresponding entry of $S$ is $i$. Therefore $\varphi^{\circ}(S) = \varphi({\textup{\textsf{rightpart}}}(T))$, where we lifted the map $\varphi^{\circ} : I \to \{1,\ldots,m\}$ to a map with the same name that is defined on tableaux with entries from $I$. Claim \[cla:differentphiNEW\] proves property of Theorem \[thm:prolongation\].

Proof of part  of Theorem \[thm:prolongation\] {#proof-of-part-of-theoremthmprolongation-5 .unnumbered}
----------------------------------------------

The rest of this section is devoted to proving part \[enum:duplex\] of Theorem \[thm:prolongation\]. A rectangular tableau whose columns all coincide is called *uniform*. In the following proof we will crucially use that a uniform tableau with an even number of columns is duplex. Indeed, we prove part \[enum:duplex\] of Theorem \[thm:prolongation\] by showing that if $\varphi(T)$ is regular, then:

-   $\varphi(\check B_{e})$ is uniform if $e$ does not contain any link vertex $\zeta^{(i)}$,

-   $\varphi(\check B_{e})$ is uniform if $\zeta^{(i)} \in e$ for $i \neq h$, and

-   $\varphi(\check B_{e})$ is uniform if $\zeta^{(h)} \in e$.

It is clear that these three properties cover all cases and hence $\varphi(T)$ is uniform by construction . This implies part \[enum:duplex\] of Theorem \[thm:prolongation\].

We start with proving (I).

\[cla:ithentry\] Let $\varphi(T)$ be regular. Given a block edge $e$ in $H^{(i)}$. For all $v \in e$, $v \neq \zeta^{(i)}$, we have that the $i$-th entry of $\varphi(\check B_v)$ is $\varphi^{\circ}(i)$.

Combine and Claim \[cla:varphii\].

\[cla:jBvneqzeta\] Let $\varphi(T)$ be regular. Given a block edge $e$ in $H^{(i)}$. For all $j \neq i$ we have that the set $$\{
\text{$j$-th entry of $\varphi(\check B_v)$} \mid v \in e, v \neq \zeta^{(i)}
\}$$ consists of the single element $\varphi(j_{k(e)}^{i})$.

Combine and Claim \[cla:barcoincide\].

Combining Claim \[cla:ithentry\] and Claim \[cla:jBvneqzeta\] we see that (I) is true.

We now prove (II). Let $i \neq h$ and let $e$ be the block edge in $H^{(i)}$ that contains $\zeta^{(i)}$. Note that $k(e)=1$.

\[cla:almostexceptionalcolumn\] Let $\varphi(T)$ be regular. Then $\varphi(\check B_{\zeta^{(i)}})$ coincides with $\varphi(\check B_v)$, $v \in e$, $i \neq h$.

We compare the columns entrywise. Note that $k(v)=k(\zeta^{(i)})=1$. We make a case distinction.

Case 1: Let $j \neq i$. The $j$-th entry of $\check B_v$ is either $j_{1}^i$ or $j_{\overline 1}^i$, see . The $j$-th entry of $\check B_{\zeta^{(i)}}$ is either $j_{1}^i$ or $j_{\overline 1}^i$, see . Using Claim \[cla:barcoincide\] we see that the $j$-th entry of $\varphi(\check B_v)$ equals the $j$-th entry of $\varphi(\check B_{\zeta^{(i)}})$.

Case 2: The $i$-th entry of $\check B_v$ is $i_1$, see . The $i$-th entry of $\check B_{\zeta^{(i)}}$ is $i_1^h$, see . Hence Claim \[cla:droph\] implies that the $i$-th entry of $\varphi(\check B_v)$ equals the $i$-th entry of $\varphi(\check B_{\zeta^{(i)}})$.

It follows from Claim \[cla:almostexceptionalcolumn\] that all columns in $\varphi(\check B_e)$ coincide, i.e., $\varphi(\check B_e)$ is uniform. Thus (II) is proved.

It remains to show (III), i.e., that $\varphi(\check B_{e})$ is uniform if $\zeta^{(h)} \in e$.

\[cla:hthentry\] Let $\varphi(T)$ be regular and $\zeta^{(h)}$ the link vertex in the block edge $e$. For all $v \in e$, $v \neq \zeta^{(h)}$, we have that the $h$-th entry of $\varphi(\check B_v)$ is $\varphi^{\circ}(h)$.

This is a direct implication of Claim \[cla:ithentry\].

\[cla:exceptionalcolumn\] Let $\varphi(T)$ be regular and $\zeta^{(h)} \in e$. Then $\varphi(\check B_{\zeta^{(h)}})$ coincides with $\varphi(\check B_{v})$, $v \in e$.

We compare the columns entrywise, considering three cases.

Case 1: We compare the $h$-th entry: According to Claim \[cla:hthentry\], the $h$-th entry of $\varphi(\check B_{v})$ is $\varphi^{\circ}(h)$. According to the $h$-th entry of $\check B_{\zeta^{(h)}}$ is $h_1$, so the $h$-th entry of $\varphi(\check B_{\zeta^{(h)}})$ is $\varphi(h_1)=\varphi^{\circ}(h)$, see .

Case 2: We compare the $j$-th entry, $j \neq h$, in the case $j \notin I$: According to , the $j$-th entry of $\check B_{v}$ is either $j_1^{h}$ or $j_{\overline 1}^{h}$. The $j$-th entry of $\check B_{\zeta^{(h)}}$ is $j_1^{h}$, see . Therefore Claim \[cla:barcoincide\] shows that the $j$-th entry of $\varphi(\check B_{v})$ equals the $j$-th entry of $\varphi(\check B_{\zeta^{(h)}})$.

Case 3: We compare the $j$-th entry, $j \neq h$, in the case $j\in I$: According to , the $j$-th entry of $\check B_{v}$ is either $j_1^{h}$ or $j_{\overline 1}^{h}$. The $j$-th entry of $\check B_{\zeta^{(h)}}$ is $j_1$, see . Combining Claim \[cla:barcoincide\] and Claim \[cla:droph\] shows that the $j$-th entry of $\varphi(\check B_{v})$ equals the $j$-th entry of $\varphi(\check B_{\zeta^{(h)}})$.

It follows from Claim \[cla:exceptionalcolumn\] that all columns in $\varphi(\check B_e)$ coincide, i.e., $\varphi(\check B_e)$ is uniform. Thus (III) is proved. This finishes the proof of part \[enum:duplex\] of Theorem \[thm:prolongation\].

Theorem \[thm:prolongation\] is now completely proved for odd $D$.

[BCMW17]{}

A. Abdesselam, C. Ikenmeyer, and Gordon Royle. 16,051 formulas for [O]{}ttaviani’s invariant of cubic threefolds. , 447:649–663, 2016.

N. Alon and M. Tarsi. Colorings and orientations of graphs. , 12(2):125–134, 1992.

Peter Bürgisser, Matthias Christandl, and Christian Ikenmeyer. Even partitions in plethysms. , 328(1):322 – 329, 2011.

Peter Bürgisser, Matthias Christandl, Ketan Mulmuley, and Michael Walter. Membership in moment polytopes is in [N]{}[P]{} and co[N]{}[P]{}. , 46(3):972–991, 2017.

Peter B[ürgisser]{}, Jesko H[ü]{}ttenhain, and Christian Ikenmeyer. Permanent versus determinant: Not via saturations. , 145:1247–1258, 2017.

Peter B[ü]{}rgisser and Christian Ikenmeyer. Geometric complexity theory and tensor rank. , pages 509–518, 2011.

Peter B[ü]{}rgisser and Christian Ikenmeyer. Deciding positivity of [L]{}ittlewood–[R]{}ichardson coefficients. , 27(4):1639––1681, 2013.

Peter Bürgisser and Christian Ikenmeyer. Explicit lower bounds via geometric complexity theory. In [*Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing*]{}, STOC ’13, pages 141–150, New York, NY, USA, 2013. ACM.

Peter B[ü]{}rgisser and Christian Ikenmeyer. Fundamental invariants of orbit closures. , 477(Supplement C):390 – 434, 2017.

Markus Bl[ä]{}ser and Christian Ikenmeyer. Introduction to geometric complexity theory. <http://pcwww.liv.ac.uk/~iken/teaching_sb/summer17/introtogct/gct.pdf>, 2018.

Markus Bläser, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov. Generalized matrix completion and algebraic natural proofs. In [*Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing*]{}, STOC 2018, pages 1193–1206, New York, NY, USA, 2018. ACM.

Peter B[ü]{}rgisser, Christian Ikenmeyer, and Greta Panova. No occurrence obstructions in geometric complexity theory. , 32:163–193, 2019. A conference version appeared in: Proceedings IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS 2016), 386–395.

Jonah Blasiak. Kronecker coefficients for one hook shape. preprint, arXiv:1209.2018, 2012.

Peter Bürgisser, J.M. Landsberg, Laurent Manivel, and Jerzy Weyman. An overview of mathematical issues arising in the [G]{}eometric complexity theory approach to [VP]{} v.s. [VNP]{}. , 40(4):1179–1209, 2011.

Emmanuel Briand, Rosa Orellana, and Mercedes Rosas. educed [K]{}ronecker coefficients and counter-examples to [M]{}ulmuley’s strong saturation conjecture [S]{}[H]{}. , 18:577–600, 2009.

Anders Skovsted Buch. he saturation conjecture (after [A]{}. [K]{}nutson and [T]{}. [T]{}ao) with an appendix by [W]{}illiam [F]{}ulton. , 2(46):43–60, 2000.

Peter B[ü]{}rgisser. The complexity of factors of multivariate polynomials. In [*42nd [IEEE]{} [S]{}ymposium on [F]{}oundations of [C]{}omputer [S]{}cience ([L]{}as [V]{}egas, [NV]{}, 2001)*]{}, pages 378–385. IEEE Computer Soc., Los Alamitos, CA, 2001.

A. D. Berenstein and A. V. Zelevinsky. Triple multiplicities for sl(r + 1) and the spectrum of the exterior algebra of the adjoint representation. , 1(1):7–22, 1992.

Matthias Christandl, Brent Doran, and Michael Walter. Computing multiplicities of [L]{}ie group representations. In [*Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science*]{}, FOCS ’12, pages 639–648, Washington, DC, USA, 2012. IEEE Computer Society.

Xi Chen, Neeraj Kayal, and Avi Wigderson. Partial derivatives in arithmetic complexity and beyond. , 2010.

Julian Dörfler, Christian Ikenmeyer, and Greta Panova. On geometric complexity theory: Multiplicity obstructions are stronger than occurrence obstructions. In [*Proceedings of the 46th International Colloquium on Automata, Languages, and Programming*]{}, ICALP 2019, pages 51:1–51:14, 2019.

Jes[ú]{}s A. De Loera and Tyrrell B. McAllister. On the computation of [C]{}lebsch-[G]{}ordan coefficients and the dilation effect. , 15(1):7–19, 2006.

Arthur A Drisko. On the number of even and odd [L]{}atin squares of order $p+1$. , 128(1):20–35, 1997.

William Fulton and Joe Harris. , volume 129 of [ *Graduate Texts in Mathematics*]{}. Springer, 1991.

Michael A. Forbes, Amir Shpilka, and Ben Lee Volk. Succinct hitting sets and barriers to proving algebraic circuits lower bounds. In [*Proceedings of the 49th Annual [ACM]{} [SIGACT]{} Symposium on Theory of Computing, [STOC]{} 2017, Montreal, QC, Canada, June 19-23, 2017*]{}, pages 653–664, 2017.

William Fulton. , volume 35 of [*London Mathematical Society Student Texts*]{}. Cambridge University Press, Cambridge, 1997.

David A. Gay. Characters of the [W]{}eyl group of [S]{}[U]{}(n) on zero weight spaces and centralizers of permutation representations. , 6(3), 1976.

Fulvio Gesmundo, Christian Ikenmeyer, and Greta Panova. Geometric complexity theory and matrix powering. , 55:106 – 127, 2017. Geometry and complexity theory.

Ankit Gupta, Neeraj Kayal, and Youming Qiao. Random arithmetic formulas can be reconstructed efficiently. , 23(2):207–303, Jun 2014.

Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, and Shubhangi Saraf. Towards an algebraic natural proofs barrier via polynomial identity testing. , abs/1701.01717, 2017.

David G. Glynn. The conjectures of [A]{}lon-[T]{}arsi and [R]{}ota in dimension prime minus one. , 24(2):394–399, 2010.

Rosa Huang and Gian-Carlo Rota. On the relations of various conjectures on [L]{}atin squares and straightening coefficients. , 128:225–236, 1994.

Christian Ikenmeyer. . PhD thesis, Institute of Mathematics, University of Paderborn, 2012. Online available at <http://nbn-resolving.de/urn:nbn:de:hbz:466:2-10472>.

Christian Ikenmeyer. and symmetries, version: January 30, 2019. <http://pcwww.liv.ac.uk/~iken/teaching_sb/winter1718/gct2/symmetries.pdf>, 2019.

Christian Ikenmeyer, Ketan D. Mulmuley, and Michael Walter. On vanishing of [K]{}ronecker coefficients. , 26(4):949–992, December 2017.

Christian Ikenmeyer and Greta Panova. Rectangular [K]{}ronecker coefficients and plethysms in geometric complexity theory. , 319:40–66, 2017. A conference version was presented at the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) 2016 in New Brunswick, New Jersey.

Neeraj Kayal. Affine projections of polynomials: Extended abstract. In [*Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing*]{}, STOC ’12, pages 643–662, New York, NY, USA, 2012. ACM.

Harlan Kadish and J. M. Landsberg. Padded polynomials, their cousins, and geometric complexity theory. , 42(5):2171–2180, 2014.

Shrawan Kumar and J.M. Landsberg. Connections between conjectures of [A]{}lon–[T]{}arsi, [H]{}adamard–[H]{}owe, and integrals over the special unitary group. , 338(7):1232 – 1238, 2015.

Neeraj Kayal, Vineet Nair, and Chandan Saha. Average-case linear matrix factorization and reconstruction of low width algebraic branching programs. , 28(4):749–828, Dec 2019.

Neeraj Kayal and Chandan Saha. Reconstruction of non-degenerate homogeneous depth three circuits. In [*Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing*]{}, STOC 2019, pages 413–424, New York, NY, USA, 2019. ACM.

Allen Knutson and Terence Tao. The honeycomb model of [${\rm GL}\sb n({\bf C})$]{} tensor products. [I]{}. [P]{}roof of the saturation conjecture. , 12(4):1055–1090, 1999.

Shrawan Kumar. A study of the representations supported by the orbit closure of the determinant. , 151(2):292–312, 2015.

J. M. Landsberg. . Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2017.

Ricky Ini Liu. A simplified [K]{}ronecker rule for one hook shape. , 145:3657–3664, 2017.

I. G. Macdonald. . Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York, second edition, 1995. With contributions by A. Zelevinsky, Oxford Science Publications.

Laurent Manivel. On rectangular [K]{}ronecker coefficients. , 33(1):153–162, 2011.

Yozô Matsushima. Espaces homogènes de [S]{}tein des groupes de [L]{}ie complexes. , 16:205–218, 1960.

Ketan D. Mulmuley, Hariharan Narayanan, and Milind Sohoni. Geometric complexity theory [III]{}: on deciding nonvanishing of a [L]{}ittlewood–[R]{}ichardson coefficient. , 36(1):103–110, 2012.

Ketan D. Mulmuley and Milind Sohoni. Geometric complexity theory. [I]{}. [A]{}n approach to the [P]{} vs. [NP]{} and related problems. , 31(2):496–526 (electronic), 2001.

Ketan D. Mulmuley and Milind Sohoni. Geometric complexity theory [II]{}. [T]{}owards explicit obstructions for embeddings among class varieties. , 38(3):1175–1206, 2008.

David Mumford. . Classics in Mathematics. Springer-Verlag, Berlin, 1995. Complex projective varieties, Reprint of the 1976 edition.

Hariharan Narayanan. On the complexity of computing [K]{}ostka numbers and [L]{}ittlewood-[R]{}ichardson coefficients. , 24(3):347–354, 2006.

Steven V. Sam and Andrew Snowden. Proof of [S]{}tembridge’s conjecture on stability of [K]{}ronecker coefficients. , 43(1):1–10, Feb 2016.

Richard P. Stanley. Positivity problems and conjectures in algebraic combinatorics. In [*Mathematics: frontiers and perspectives*]{}, pages 295–319. Amer. Math. Soc., Providence, RI, 2000.

Patrice Tauvel and Rupert W. T. Yu. . Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2005.

L. G. Valiant. Completeness classes in algebra. In [*Conference [R]{}ecord of the [E]{}leventh [A]{}nnual [ACM]{} [S]{}ymposium on [T]{}heory of [C]{}omputing ([A]{}tlanta, [G]{}a., 1979)*]{}, pages 249–261. ACM, New York, 1979.

[^1]: University of Liverpool, christian.ikenmeyer$@$liverpool.ac.uk

[^2]: Universität des Saarlandes, umangathan.kandasamy@outlook.de
