On vanishing of Kronecker coefficients

Introduction

One class of representation-theoretic obstructions in the context of the geometric complexity theory (GCT) approach to the permanent vs. determinant problem (Mulmuley & Sohoni, 2008; Mulmuley, 2011) is based on the existence of vanishing rectangular Kronecker coefficients (Mulmuley & Sohoni, 2008; Bürgisser et al., 2011a; Kumar, 2015). These are called occurrence-based obstructions, as opposed to the more general multiplicity-based obstructions. We refer to Bürgisser et al. (2011b); Bürgisser (2016) for introduction and background. It is now known that such occurrence-based obstructions based on vanishing of Kronecker coefficients cannot be used for proving superpolynomial lower bounds for the permanent (Ikenmeyer & Panova, 2016). However, they may still be useful for proving modest polynomial lower bounds. The partition triples associated with the rectangular Kronecker coefficients lie in the moment cone (Kirwan, 1984) associated with the Kronecker coefficients, called the Kronecker cone (Bürgisser et al., 2011a; Kumar, 2015). As pointed out in Kumar (2015), this makes the problem of showing the existence of such partition triples rather challenging, since the asymptotic techniques of algebraic geometry and representation theory, such as the ones based on the effective descriptions of the linear inequalities defining the Kronecker cone (Berenstein & Sjamaar, 2000; Klyachko, 2004; Ressayre, 2010; Vergne & Walter, 2017), cannot be used to prove this existence.

The main result in this article (1.5) establishes the existence of a superpolynomial number of partition triples with vanishing Kronecker coefficients, in the Kronecker cone for the given partition size, and satisfying a relaxed form of the additional shape restrictions that arise in GCT.

Its proof, based on the explicit proof strategy of GCT (Mulmuley, 2011, 2010a, 2010b), also yields results concerning the complexity of Kronecker coefficients that are of independent interest. The first such result (1.1) shows that the problem of deciding positivity of Kronecker coefficients is NP-hard. The second result (1.3) gives the first known instance of a positive ($\#P$) formula for a subclass of Kronecker coefficients whose positivity is NP-hard to decide.

We now state these results in more detail after the following preliminary section.

When we encode partitions as bit strings there are two fundamentally different ways of doing it: As a list of numbers in binary or as a list of numbers in unary. Note that in unary transposing a partition does not significantly change its encoding size, but in binary the 1-row partition $(n)$ can be encoded using $O(\log n)$ bits, while $(n)^{T}=(1,1,\ldots,1)$ requires $O(n)$ bits. We will mostly encode partitions in unary.

It is natural to interpret partitions as vectors with integer entries, so that we have a well-defined addition and scalar multiplication with nonnegative integers. Moreover, dividing a partition by an integer results in a vector with rational entries.

Let $G:=\operatorname{GL}_{r}$ denote the general linear group, i.e., the group of invertible $r\times r$ matrices. Let $V$ be a finite dimensional vector space and let $\operatorname{GL}(V)$ denote the set of linear isomorphisms of $V$. A group homomorphism $\varrho:G\to\operatorname{GL}(V)$ is called a representation of $G$. We say that $V$ is a representation if $\varrho$ is clear from the context. We say that $G$ acts linearly on $V$ and use the short notation $gv:=(\varrho(g))(v)$ for $g\in G$, $v\in V$. If all the coordinate functions of $\varrho$ are given by multivariate polynomials in the $r^{2}$ coordinate variables of $\operatorname{GL}_{r}$, then we call $\varrho$ a polynomial representation.

A linear subspace $W\subseteq V$ that satisfies $\forall w\in W,\,g\in G:gw\in W$, is called a subrepresentation. Subrepresentations of polynomial representations are always polynomial. For every representation $V$, the zero vector space and $V$ itself are two subrepresentations. If $V$ has only these two subrepresentations, then $V$ is called irreducible. Given two representations $(V,\rho_{V})$ and $(W,\rho_{W})$, then a linear map $\varphi:V\to W$ is called equivariant if $g\varphi(v)=\varphi(gv)$ for all $g\in G$, $v\in V$. If $\varphi$ is an equivariant isomorphism of vector spaces, then $\varphi$ is called a $G$-isomorphism and the representations $V$ and $W$ are called isomorphic. The different types of isomorphic irreducible polynomial representations of $G$ have been classified completely: They are indexed by partitions of height at most $r$. In a representation $V$ the sum of all subrepresentations of type $\lambda$ is called the $\lambda$-isotypic component. Every representation decomposes into a direct sum of isotypic components.

The multiplicity of the type $\lambda$ in a representation $V$ is the dimension of the vector space of highest weight vectors of type $\lambda$. If we decompose $V$ into a direct sum of irreducibles, then this multiplicity counts how often a copy of type $\lambda$ appears in the decomposition.

If we have $k$ commuting actions of several copies of $G$ on $V$, then we use the representation theory of the cartesian powers $G^{k}$, which is very similar to the representation theory of $G$. We will mainly be concerned with $k=2$ and $k=3$. The types of irreducible representations of $G^{k}$ are given by $k$-tuples of partitions, weight vectors are defined by their scaling behavior under $k$-tuples of diagonal matrices, and the Lie algebra action is defined via $k$-tuples of matrices, where the raising operators are $k$-tuples of matrices in which only one matrix is nonzero. Irreducible representations of $G$ are called Weyl modules, while irreducible representations of $G^{k}$ are isomorphic to a $k$-fold tensor product of Weyl modules.

The Kronecker coefficient arises as a multiplicity in several other representation theoretic decompositions, for example as the multiplicity of $V_{\lambda}(\operatorname{GL}_{r})\otimes V_{\mu}(\operatorname{GL}_{r})\otimes V_{\pi}(\operatorname{GL}_{r})$ in $V_{(n)}(\operatorname{GL}_{r^{3}})$ via the group homomorphism $\operatorname{GL}_{r}^{3}\to\operatorname{GL}_{r^{3}}$, $(g,g^{\prime},g^{\prime\prime})\mapsto g\otimes g^{\prime}\otimes g^{\prime\prime}$, where $\lambda$, $\mu$, and $\pi$ have exactly $n$ boxes.

For $k^{\lambda}_{\mu,\pi}$ to be positive it is required that $\lambda$, $\mu$, and $\pi$ are partitions of the same number, i.e., $|\lambda|=|\mu|=|\pi|=n$ for some $n$. This implies that if $k^{\lambda}_{\mu,\pi}>0$, then the rescaled partitions $\lambda/n$, $\mu/n$, and $\pi/n$ are three discrete probability distributions. Another necessary condition for $k^{\lambda}_{\mu,\pi}>0$ is $\operatorname{ht}(\lambda)\leq\operatorname{ht}(\mu)\cdot\operatorname{ht}(\pi)$. The coefficient is invariant under permuting the three parameters, so

Moreover, transposing any two of the three parameters does not change the coefficient:

Given two partition triples $(\lambda,\mu,\pi)$ and $(\lambda^{\prime},\mu^{\prime},\pi^{\prime})$ such that $k^{\lambda}_{\mu,\pi}>0$ and $k^{\lambda^{\prime}}_{\mu^{\prime},\pi^{\prime}}>0$, then $k^{\lambda+\lambda^{\prime}}_{\mu+\mu^{\prime},\pi+\pi^{\prime}}>0$. This is called the semigroup property. The convex cone defined by

Finding a combinatorial description of $k^{\lambda}_{\mu,\pi}$ is an important outstanding problem (see 1.3 below). Only for some special cases is a combinatorial description known, for example for the Littlewood-Richardson coefficients. The Littlewood-Richardson coefficients are those $k^{\lambda}_{\mu,\pi}$ for which $\lambda$, $\mu$, and $\pi$ have a sufficiently long first row such that $|\overline{\lambda}|=|\overline{\mu}|+|\overline{\pi}|$, where $\overline{\lambda}$ is the partition $\lambda$ with its longest row removed. The positivity of Littlewood-Richardson coefficients can be decided in strongly polynomial time (Knutson & Tao, 2001; Mulmuley et al., 2011).

Another important subclass of Kronecker coefficients are the rectangular Kronecker coefficients. For a given partition $\lambda$ with size $|\lambda|$ divisible by $r$, let $\delta(\lambda)$ denote the rectangular partition $(d,\ldots,d)$ ($r$ times), where $d=|\lambda|/r$. We call the Kronecker coefficient $k^{\lambda}_{\delta(\lambda),\delta(\lambda)}$ rectangular. Rectangular Kronecker coefficients play a special role in geometric complexity theory (see 1.4 below).

2 NP-hardness of deciding positivity of Kronecker coefficients

Let Kronecker be the problem of deciding positivity of $k_{\mu,\pi}^{\lambda}$, given as input the three partitions $\lambda$, $\mu$, and $\pi$ in unary. This problem is of fundamental interest in the context of the explicit proof strategy of GCT (Mulmuley, 2011, 2010a, 2010b). Our first result is the following:

It was conjectured in Mulmuley (2010b) that the problem of deciding positivity of Kronecker coefficients is in $P$. 1.1 shows that this is not so, in general, assuming that $P\not=NP$. This is in contrast to the special case of the Littlewood-Richardson coefficients, where positivity can be decided in strongly polynomial time, as explained above.

3 A #​P#𝑃\#P-formula for a subclass of partitions of type NP

To find a positive formula for Kronecker coefficients “akin to” the well known positive Littlewood-Richardson rule is an unsolved problem in classical representation theory. We refer to Stanley (2002) for the history and importance of this problem, where it is listed as one of the twenty-five “outstanding open problems”. In classical representation theory, the phrase “akin to” is used only informally. A formal complexity-theoretic version of this problem is to find a $\#P$-formula for Kronecker coefficients. By a $\#P$-formula for the Kronecker coefficient $k^{\lambda}_{\mu,\pi}$, we mean a formula of the form:

where, for a partition $\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{l})$, $\langle\lambda\rangle$ denotes the total bitlength of the specification of $\lambda_{j}$’s in binary, $p(\langle\lambda\rangle,\langle\mu\rangle,\langle\pi\rangle)$ is a polynomially-bounded function of the bit-lengths $\langle\lambda\rangle,\langle\mu\rangle$, and $\langle\pi\rangle$, and $F(\lambda,\mu,\pi,\sigma)$ is a polynomial-time-computable -$1$ function of $\lambda,\mu,\pi$, and the bit-string $\sigma$. By a positive formula, we mean a $\#P$-formula henceforth.

Let $\Pi$ be a class of partition triples. We say that $\Pi$ is of type NP if the problem of deciding positivity of $k^{\lambda}_{\mu,\pi}$, with $(\lambda,\mu,\pi)\in\Pi$, is NP-hard. (The problem mentioned here is a promise problem. That is, we are promised that the input triple is in the subclass $\Pi$.) Likewise, we say that $\Pi$ is of type P if the problem of deciding positivity of $k^{\lambda}_{\mu,\pi}$, with $(\lambda,\mu,\pi)\in\Pi$, is in P.

All positive rules known so far for restricted classes of Kronecker coefficients have been for subclasses of partition triples that are either known or conjectured to be of type P. For example, the classical Littlewood-Richardson rule gives a positive rule for Littlewood-Richardson coefficients, which, as already mentioned, constitute a special class of Kronecker coefficients. The corresponding subclass of partition triples is of type P, since the problem of deciding positivity of Littlewood-Richardson coefficients is in $P$ (Knutson & Tao, 2001; Mulmuley et al., 2011). Blasiak et al. (2015) give a positive rule for Kronecker coefficients when two of the partitions have height at most two. The corresponding subclass of partition triples is of type P, since the Kronecker coefficient can be computed in this case (and more generally, for partitions of bounded height) in polynomial time (Christandl et al. (2012); Baldoni et al. (2017)). Blasiak (2017) gives a positive rule for Kronecker coefficients when one of the partitions is a hook. The corresponding subclass of partition triples is conjectured to be of type P, since the problem of deciding positivity of Kronecker coefficients, when one of the partitions is a hook, is believed to be in $P$ (in view of 6.10).

The following result gives the first known instance of a positive rule for Kronecker coefficients for a subclass of partition triples of type NP.

There exists a $\#P$-formula for Kronecker coefficients for a subclass of partition triples of type NP. Here the partition triples can be specified in unary or binary.

The proof of this result exhibits an explicit such subclass of partition triples of type NP (see 2 and 3).

1.3 provides good evidence in support of the conjecture in Mulmuley (2010b) that there exists a $\#P$-formula for Kronecker coefficients in general. This would in particular imply that Kronecker is in NP, which is not known so far.

4 Exceptional Kronecker coefficients

In order for a Kronecker coefficient $k_{\mu,\pi}^{\lambda}$ to be useful for proving a polynomial lower bound for the permanent, the partition triple must have a number of exceptional properties (Mulmuley & Sohoni, 2008; Bürgisser et al., 2011b). This is captured by the following definition:

Fix any constant $0<\epsilon\leq 1$, and a constant $b>1$. We call a partition triple $(\lambda,\mu,\pi)$ with $\lvert\lambda\rvert=\lvert\mu\rvert=\lvert\pi\rvert$ $(\epsilon,b)$-exceptional if:

$\mu=\pi=\delta(\lambda)$, with $|\lambda|=|\mu|=|\pi|$ divisible by $r:=\operatorname{ht}(\mu)=\operatorname{ht}(\pi)$,

$\operatorname{ht}(\lambda)\leq r^{\epsilon}$,

$(\lambda,\mu,\pi)\in\operatorname{Kron}(r)$,

$\lambda_{0}\geq|\lambda|(1-r^{\epsilon/2-1})$.

We also call a partition tuple merely exceptional, without mentioning $\epsilon$ and $b$, if it is understood that $\epsilon$ can be chosen to be arbitrarily small, with $b$ a large enough constant depending on $\epsilon$, and $r\rightarrow\infty$.

By Bürgisser et al. (2011a), 2 implies 4, assuming that the height of $\lambda$ is $\leq r^{2}$, which is so by 3.

The constraint 4 is significant. Proving existence of the partition triples as in 1.4 is delicate because of this constraint. Indeed, it may be possible to prove existence of superpolynomially many partition triples satisfying the constraints other than 2 and 4 using the known linear inequalities defining the Kronecker cone (Berenstein & Sjamaar, 2000; Klyachko, 2004; Ressayre, 2010; Vergne & Walter, 2017). But the constraint 4 implies that such asymptotic techniques based on the description of the Kronecker cone cannot be used to demonstrate existence of partition triples as in 1.4. This is the main significance of the results in Bürgisser et al. (2011a); Kumar (2015).

By the Saturation Theorem (Knutson & Tao, 1999; Derksen & Weyman, 2000), the Littlewood-Richardson coefficients cannot vanish for the partition triples that lie in the analogously defined Littlewood-Richardson cone. The constraint 4 also implies that in order to prove existence of the partition triples as in 1.4, one needs to understand the failure of the saturation property for the Kronecker coefficients in one way or another.

The constraint 7 is motivated by Kadish & Landsberg (2014). There, it is shown that this condition holds if $V_{\lambda}(G)$ is a representation-theoretic obstruction (Mulmuley & Sohoni, 2008).

It is a priori not at all clear that for any given constant $0<\epsilon\leq 1$ and a large enough constant $b>1$ depending on $\epsilon$, exceptional partition triples exist for arbitrary $r$. The experimental evidence in Ikenmeyer (2012) for small values of $r$ (with suitable $\epsilon$ and $b$) suggests that they are very rare, though they do exist for these small values. In summary, although their density can be expected to be extremely small, it is a relevant and rather non-trivial problem in the context of GCT to show that exceptional partition triples exist and that their number is large enough.

5 Construction of superpolynomially many partition triples in the Kronecker cone with vanishing Kronecker coefficients

As the first step towards this goal, we relax the condition 2 to the weaker requirement that only $\mu=\pi$, the condition 6 to the weaker requirement weaker that $\lambda$ is not a hook (since it can be shown that $p(\lambda)=0$ if $\lambda$ is a hook), and ignore the condition 7. A priori, it is not clear that partition triples with these properties exist even after this shape relaxation, since condition 4 is retained. The following result shows that the number of Kronecker coefficients with this relaxation of 1.4 is superpolynomial.

For any $0<\epsilon\leq 1$, there exists $0<a<1$, such that, for all $m$, there exist $\Omega(2^{m^{a}})$ partition triples $(\lambda,\mu,\pi)$ such that

$\operatorname{ht}(\mu)=m$, and $\operatorname{ht}(\lambda)\leq m^{\epsilon}$,

$(\lambda,\mu,\pi)\in\operatorname{Kron}(m)$,

Assuming coNP $\neq$ NP, the set of partition triples satisfying constraints 1–\short6 as well as

$(\lambda^{T},\mu^{T},\mu)\in\operatorname{Kron}(m^{\prime})$, where $m^{\prime}$ is the maximum of the heights of $\lambda^{T}$, $\mu^{T}$ and $\mu$, and

$(\lambda,\mu^{T},\mu^{T})\in\operatorname{Kron}(m^{\prime\prime})$, where $m^{\prime\prime}$ is the maximum of the heights of $\lambda$ and $\mu^{T}$,

is superpolynomial in $m$, as $m\rightarrow\infty$.

The constraints \short4, 7, and 8 together guarantee that the vanishing of $k^{\lambda}_{\mu,\mu}$ cannot be directly shown using the defining inequalities of the Kronecker cone (Berenstein & Sjamaar, 2000; Klyachko, 2004; Ressayre, 2010; Vergne & Walter, 2017) in conjunction with the known symmetries 1 and 2.

Our proof of 1.5 shows that the partition triples $(\lambda,\mu,\mu)$ satisfying the constraints therein can even be constructed explicitly. This means there is a one-to-one map from the set of Boolean strings of length $\leq m^{a}$ to the set of partitions triples $(\lambda,\mu,\mu)$ with properties \short1–\short6 that can be computed in $\operatorname{poly}(m)$ time.

While 1.5 shows existence of superpolynomially many partition triples satisfying the constraints therein, the density of such partition triples is exponentially small, since $a$ therein is much smaller than $1$ (see 5.6). This may explain why vanishing Kronecker coefficients with the partition triples in the Kronecker cone occur so rarely in computer experiments, as observed in Ikenmeyer (2012).

6 Proof technique

1.1 is proved by extending the NP-completeness technique in Brunetti et al. (2001) in conjunction with the fundamental lower and upper bounds on Kronecker coefficients established in Manivel (1997); Bürgisser & Ikenmeyer (2013); Vallejo (2000). 1.3 is a byproduct of this proof.

A refined form of 1.1 lies at the heart of the proof of 1.5. Specifically, we show in 4.2 that the problem of deciding positivity of $k^{\lambda}_{\mu,\pi}$ remains NP-hard under polynomial-time many-one reductions (Karp, 1972) even when the partitions $(\lambda,\mu,\pi)$ are required to satisfy the constraints 2–\short6. This is done by extending the proof technique of 1.5 using the result in Bürgisser et al. (2011a) that $(\lambda,\delta(\lambda),\delta(\lambda))$, for $|\lambda|$ divisible by $r$, lies in the Kronecker cone whenever the height of $\lambda$ is $\leq r^{2}$. By Fortune (1979), if there exists a co-sparse NP-complete language under polynomial-time many-one-reductions, then P=NP. (Here we call a language sparse if the number of strings in it of bitlength $\leq N$ is bounded by a fixed polynomial in $N$. It is called co-sparse if its complement is sparse.) Hence 4.2 in conjunction with Fortune (1979) implies that the set of partition triples satisfying the constraints 1–\short6 is non-sparse, i.e., has size superpolynomial in $m$, assuming that P$\neq$NP.

To prove 1.5, we have to discard of the assumption that P=NP and replace the superpolynomial bound by $\Omega(2^{m^{a}})$ bound for some $a>0$. This is done in 5.3 by exhibiting a polynomial-time one-one reduction from the 3D Matching problem (Garey & Johnson, 1979) to the problem of deciding positivity of Kronecker coefficients, with the partition triples satisfying the constraints 2–\short6, where a polynomial-time one-one reduction means an injective polynomial-time many-one reduction. Hence, the $\Omega(2^{m^{a}})$ bound in 1.5 follows from a similar lower bound on the number of instances of the 3D Matching problem with a “NO” answer. The proof automatically shows that $\Omega(2^{m^{a}})$ partition triples satisfying the constraints in 1.5 can be constructed explicitly. This follows by fixing a suitable set of $2^{N^{b}}$ instances, for some constant $b>0$, of the 3D Matching problem of bitlength $\leq N$ with “NO” answer, and mapping them injectively, via a sequence of polynomial time one-one reductions, to $\Omega(2^{m^{a}})$ such partition triples.

1.6 is proved by extending the proof of 1.5 using an auxiliary result, 5.7, which extends the hardness vs. non-sparseness result in Fortune (1979), together with the result in Bürgisser et al. (2017) which asserts that the membership problem for the Kronecker cone is in $\mbox{NP}\cap\mbox{coNP}$.

7 Effectiveness of the explicit proof strategy

Perhaps the most novel aspect of this paper is the synthesis of the representation theory of Kronecker coefficients with the theory of NP-completeness to prove unconditionally existence of superpolynomially many partition triples in the Kronecker cone with vanishing Kronecker coefficients.

In principle, the existence of partition triples satisfying the constraints in 1.5 may be proved by a nonconstructive technique. Yet, the only way we can prove this existence at present is by constructing such partitions explicitly, using the theory of algorithms, as done in the proof of 1.5. Thus this proof illustrates effectiveness of the explicit proof strategy of GCT (Mulmuley, 2011, 2010a, 2010b) in a nontrivial setting.

8 Organization

The rest of this article is organized as follows. 2 describes the lower and upper bounds for the Kronecker coefficients that are needed for the proofs of 1.1 and 1.3. These proofs are given in 3. A refinement of 1.1, which is needed for the proof of 1.5, is proved in 4. 1.5 and 1.6 are proved in 5. 6 proves additional results in support of the conjecture in Mulmuley (2010b) that the problem of deciding positivity of rectangular Kronecker coefficients is in $P$.

Lower and upper bounds for the Kronecker coefficient

In this section, we give representation-theoretic proofs of some known lower and upper bounds from Manivel (1997); Bürgisser & Ikenmeyer (2013); Vallejo (2000) for the Kronecker coefficients. These bounds as well as their representation-theoretic interpretation given here will play a crucial role in the proofs of 1.1 and 1.3 in 3. We begin with the following well-known result (whose proof we include for the sake of completeness):

Since $[\lambda^{T}]=[\lambda]\otimes[(1^{n})]$, $[(1^{n})]\otimes[(1^{n})]=[(n)]$, and $[(n)]$ is the trivial representation, 3 follows at once.

Given a (finite) point set $P\subseteq\{0,\dots,r-1\}^{3}$, let $x_{P}(i)$, $0\leq i\leq r-1$, be the number of points in $P$ with the $x$-coordinate $i$. We call $x_{P}=(x_{P}(0),\ldots,x_{P}(r-1))$ the $x$-marginal of $P$. We similarly define the $y$-marginal $y_{P}$ and the $z$-marginal $z_{P}$. The triple $(x_{P},y_{P},z_{P})$ is called the marginals of $P$.

We define $t^{\lambda}_{\mu,\pi}$ as the number of point sets $P\subseteq\{0,\dots,r-1\}^{3}$ with marginals $(\lambda^{T},\mu^{T},\pi^{T})$.

Note that $\lambda^{T}_{i}$ is the number of boxes in the $i$-th column of $\lambda$.

The coefficients $t^{\lambda}_{\mu,\pi}$ have a pleasant representation-theoretical interpretation that is closely related to 2.1. To see this, observe that we can associate with any point set

Following Vallejo (2000), we call a subset $P\subseteq\{0,\dots,r-1\}^{3}$ a pyramid if, for any $(x,y,z)\in P$ and $0\leq x^{\prime}\leq x$, $0\leq y^{\prime}\leq y$, $0\leq z^{\prime}\leq z$, we have that $(x^{\prime},y^{\prime},z^{\prime})\in P$. (It would also be natural to call such $P$ a 3-partition; cf. Manivel (1997).)

Let $p^{\lambda}_{\mu,\pi}$ denote the number of pyramids with marginals $(\lambda^{T},\mu^{T},\pi^{T})$.

From our representation-theoretic interpretation, we directly obtain the following fundamental bounds, which were proved previously using different methods in Manivel (1997); Bürgisser & Ikenmeyer (2013) (cf. Vallejo, 2000):

For all partitions $\lambda,\mu,\pi$, we have $p^{\lambda}_{\mu,\pi}\leq k^{\lambda}_{\mu,\pi}\leq t^{\lambda}_{\mu,\pi}$.

is a pyramid with marginals $(\lambda^{T},\mu^{T},\pi^{T})$. We will show that $\psi_{P}$ is not only a weight vector, but in fact a highest weight vector. For this, we need to argue that $\psi$ is annihilated by all raising operators (cf. 1.1). Thus consider $(E_{x^{\prime},x},0,0)$, where $E_{x^{\prime},x}$ denotes the upper triangular matrix with a single 1 in the $x^{\prime}$-th row and $x$-th column, and otherwise zero (here $x^{\prime}<x$). Its action on $\psi_{P}$ is given by

since each summand vanishes individually. Indeed, if $x\neq x_{j}$ then $\delta_{x,x_{j}}=0$ and so the summand is zero. Otherwise, if $x=x_{j}$ then $(x_{j},y_{j},z_{j})\in P$ and $x^{\prime}<x$ imply that $(x^{\prime},y_{j},z_{j})\in P$ by the pyramid condition; therefore $e_{x^{\prime}}\otimes e_{y_{j}}\otimes e_{z_{j}}$ appears twice in the wedge product and so the summand vanishes as well. The same argument applies to the other generators $(0,E_{y^{\prime},y},0)$ and $(0,0,E_{z^{\prime},z})$ of $\mathfrak{n}$. Thus we conclude that the pyramid condition ensures that $\psi_{P}$ is a highest weight vector.

Let $\lambda$, $\mu$, $\pi$ be partitions such that any point set with marginals $(\lambda^{T},\mu^{T},\pi^{T})$ is necessarily a pyramid. Then $k^{\lambda}_{\mu,\pi}=t^{\lambda}_{\mu,\pi}=p^{\lambda}_{\mu,\pi}$.

Kronecker coefficients with #P-formulae

For this, we first derive a sufficient condition on the marginals $(\lambda^{T},\mu^{T},\pi^{T})$ such that any compatible point set is necessarily a pyramid (and hence 2.8 is applicable). Adapting the approach of Brunetti et al. (2001), we consider a point set $P$ such that $P_{r}\subseteq P\subsetneq P_{r+1}$, where

denotes the simplex of side length $r\geq 1$. Let $n$ denote the total number of points in $P$. Then the projection of the barycenter $b_{P}:=\sum_{p\in P}p$ of $P$ onto the diagonal $(1,1,1)$ can be computed as follows:

where $b_{r}$ denotes the barycenter of the simplex $P_{r}$. Note that this formula depends only $n$, the number of points in the point set $P$. We can thus define a function $p(n)$ by 4, first for all $n$ such that $\lvert P_{r}\rvert\leq n<\lvert P_{r+1}\rvert$, and then, by varying $r$, for all $n$. Explicitly,

where $r(n)$ is the maximal $r$ such that $\lvert P_{r}\rvert=r(r+1)(r+2)/6\leq n$.

Let us call $(\lambda,\mu,\pi)$, with $|\lambda|=|\mu|=|\pi|=n\not=0$, simplex-like if there exists some $r$ such that the Young diagrams of $\lambda,\mu$, and $\pi$ have at most $r+1$ columns, and

Whether $(\lambda,\mu,\pi)$ is simplex-like can be checked in polynomial time (even assuming that $\lambda,\mu$ and $\pi$ are given in binary).

The following lemma justifies the term “simplex-like”.

Let $(\lambda,\mu,\pi)$ be simplex-like. Then any point set $P$ with marginals $(\lambda^{T},\mu^{T},\pi^{T})$ is necessarily of the form $P_{r}\subseteq P\subsetneq P_{r+1}$, for some $r\geq 1$. In particular, $P$ is a pyramid.

The last step follows because $(\lambda,\mu,\pi)$ is simplex-like.

Let $(\lambda,\mu,\pi)$ be simplex-like. Then $k^{\lambda}_{\mu,\pi}=t^{\lambda}_{\mu,\pi}=p^{\lambda}_{\mu,\pi}$. In particular, this family of Kronecker coefficients has a $\#P$-formula. Here, $\lambda,\mu$ and $\pi$ can be given in unary or binary.

This follows from 3.2, 2.8, and the fact that $t^{\lambda}_{\mu,\pi}$ has a $\#P$-formula. The last assertion follows because the bit-length of the unary specification of a simplex-like partition triple is polynomial in the bit-length of its binary specification.

One important class of simplex-like marginals is the following. Let $(\varphi^{T},\varphi^{T},\varphi^{T})$ denote the marginals of the simplex $P_{2r}$, where $r\geq 1$. Define

Since $\lvert P_{2r}\rvert\leq n=\lvert P_{2r}\rvert+(r+1)<\lvert P_{2r+1}\rvert$, this is indeed equal to $p(n)$, where $n$ is the number of boxes of each of $\lambda$, $\mu$, and $\pi$ (compare with 5). These marginals arise when embedding permutation matrices on top of the simplex $P_{2r}$, and in Brunetti et al. (2001) it was shown using this construction that:

The problem of deciding positivity of $t^{\lambda}_{\mu,\pi}$, given $\lambda,\mu,\pi$ in unary, is NP-hard with respect to polynomial-time many-one reductions, even when $(\lambda^{T},\mu^{T},\pi^{T})$ is restricted to be of the form 6.

Thus it follows at once from 3.4, in conjunction with this result, that:

The problem of deciding positivity of the Kronecker coefficient $k^{\lambda}_{\mu,\pi}$, given $\lambda,\mu,\pi$ in unary, is NP-hard with respect to polynomial-time many-one reductions, even when $(\lambda^{T},\mu^{T},\pi^{T})$ is restricted to be of the form 6.

This proves 1.1. 1.3 follows from this result and 3.4.

Refined NP-hardness result

Let Restricted Kronecker be the problem of deciding positivity of $k^{\lambda}_{\mu,\pi}$, when $\lambda,\mu,\pi$ satisfy the constraints 2–\short6. Specifically:

$\operatorname{ht}(\lambda)\leq m^{\epsilon}$,

$(\lambda,\mu,\pi)$ is in the Kronecker cone $\operatorname{Kron}(m)$,

For the proof of 1.5, we need the following refinement of 3.7:

Restricted Kronecker is NP-hard with respect to polynomial-time many-one reductions.

Let $\lambda$ and $\mu$ be partitions so that $\operatorname{ht}(\lambda)\leq h^{2}$, where $h$ is the height of the smallest column of $\mu$. Then $(\lambda,\mu,\mu)$ is in the Kronecker cone $\operatorname{Kron}(l)$, where $l=\max\{\operatorname{ht}(\lambda),\operatorname{ht}(\mu)\}$.

It is shown in Bürgisser et al. (2011a) that $(\lambda,\delta,\delta)$ is in the Kronecker cone whenever $\delta$ is a rectangle of height at least $h$, and $\operatorname{ht}(\lambda)\leq h^{2}$. As the Kronecker cone is a cone, this is also true if we rescale each of $\lambda$ and $\delta$ by an arbitrary positive number.

Let us write $\mu$ as a sum of rectangles $\delta^{(1)}+\dots+\delta^{(k)}$, where our assumption implies that each $\delta^{(j)}$ has height at least $h$. It is easy to see that $\lambda$ can be written as a sum $\lambda^{(1)}+\dots+\lambda^{(k)}$, where each $\lambda^{(j)}$ is a rational partition with the same size as $\delta^{(j)}$ (i.e., $|\lambda^{(j)}|=|\delta^{(j)}|$), and with no more than $h^{2}$ rows. By the preceding argument, each $(\lambda^{(j)},\delta^{(j)},\delta^{(j)})$ is in the Kronecker cone $\operatorname{Kron}(l)$. As cones are closed under addition, $(\lambda,\mu,\mu)$ is likewise in the Kronecker cone.

Next, we generalize 3.4 to a larger class of marginals. Let $(\lambda,\mu,\pi)$ be simplex-like, and let $P$ be a corresponding point set with marginals $(\lambda^{T},\mu^{T},\pi^{T})$, so that $P_{r}\subseteq P\subsetneq P_{r+1}$ for some $r$ (3.2). Let $Q$ denote the following point set obtained by adjoining $P$ to a rectangular box of size $a\times b\times c$, where $b,c\geq r+1$:

Then we have the following generalization of 3.2.

We apply the pedestal construction to marginals of the form 6. Let us choose a rectangular box of size $c\times s\times s$, where $s=2r+1$. That is, we set

The problem of deciding positivity of $k^{\lambda}_{\mu,\pi}$, with $(\lambda,\mu,\pi)$ restricted as above, is NP-hard, since by 4.8, these Kronecker coefficients agree with the ones in 3.7, and we can transform instances of the latter to instances of the former in polynomial time (as $\epsilon$ is fixed).

We now verify that the five constraints in 4.1 are all satisfied. The first is clearly satisfied. For the second,

by our choice of $c=c(s)$. The third follows from 4.3, as $\operatorname{ht}(\lambda)=s^{2}$, while every column in $\mu$ is of height at least $cs\geq s$. The fourth follows, since

assuming that $r$ is large enough. Finally, it is clear that $\lambda$ is not a hook.

Construction of vanishing Kronecker coefficients with partition triples in the Kronecker cone

By Fortune (1979), if there exists a co-sparse NP-complete language under polynomial-time many-one-reductions, then P=NP. 4.2, in conjunction with this result, implies that, assuming P$\neq$NP, the set of partitions triples satisfying the constraints 1–\short6 is non-sparse, i.e, its cardinality is superpolynomial in $m$. (The result in Fortune (1979) applies to NP-complete sets, rather than NP-hard sets. But we can still apply this result to the NP-complete set of simplex-like partition triples (cf. 3.7) with positive Kronecker coefficients to get the desired conclusion.) To prove 1.5, we have to get rid of the assumption that P$\neq$NP and replace the superpolynomial bound by $\Omega(2^{m^{a}})$ bound, for some positive constant $a$. This will be achieved by 5.1 and 5.3 below.

Recall from Garey & Johnson (1979) that the 3D Matching problem is to decide, given a set $M\subseteq W\times X\times Y$, where $W$, $X$, $Y$ are disjoint sets of size $q$, whether $M$ contains a (perfect) matching, i.e., a subset $M^{\prime}\subseteq M$ of size $q$ such that no two elements of $M^{\prime}$ agree in any coordinate. Without loss of generality, we assume henceforth that each element in $W\cup X\cup Y$ appears in some triple of $M$. We denote instances of 3D Matching by tuples $(M,W,X,Y,q)$. It is known that the 3D Matching problem is NP-complete (Garey & Johnson, 1979).

The number of instances $(M,W,X,Y,q)$ of the 3D Matching problem with total bit-length $\leq N$ such that $M$ does not have a matching is $\Omega(2^{N^{b}})$ for some positive constant $b<1$.

Furthermore, such instances can be constructed explicitly. That is, for some positive constant $b<1$, there is a polynomial-time-computable one-to-one function that maps any pair of the form $(N,\sigma)$, where $N$ is a positive integer and $\sigma$ is a binary string of length $\leq N^{b}$, to an instance of 3D Matching problem without matching of bitlength $\leq N$.

Consider any fixed instance $(M_{0},W_{0},X_{0},Y_{0},q_{0})$ of 3D Matching, such that $M_{0}$ does not have a matching. Its bitlength is thus a constant. Given any instance $(M,W,X,Y,q)$ of 3D Matching, with $W,X$ and $Y$ disjoint from $W_{0},X_{0}$ and $Y_{0}$, consider the padded instance $(M\cup M_{0},W\cup W_{0},X\cup X_{0},Y\cup Y_{0},q+q_{0})$. Clearly, $M\cup M_{0}$ also does not have a matching. The number of instances of the form $(M\cup M_{0},W\cup W_{0},X\cup X_{0},Y\cup Y_{0},q+q_{0})$ with bitlength $\leq N$ is clearly $\Omega(2^{N^{b}})$ for some positive constant $b<1$. This is because, for a given $q$, the total number of instances of the form $(M,W,X,Y,q)$ is $2^{q^{3}}$, and the bit-length of the specification of any instance of this form is $O(q^{3})$. (We assume that $M$ is specified by its $q\times q\times q$ adjacency matrix.) Furthermore, it is easy to show that the padded instances of the form $(M\cup M_{0},W\cup W_{0},X\cup X_{0},Y\cup Y_{0},q+q_{0})$ can be constructed explicitly.

Recall (cf. 1.6) that a polynomial-time one-one reduction means an injective polynomial-time many-one reduction.

There exists a polynomial-time one-one reduction $\phi$ from the set of instances $(M,W,X,Y,q)$ of 3D Matching of total bit-length $n$ to the set of partition triples $(\lambda,\mu,\pi)$ satisfying the conditions 2–\short6 (i.e., instances of Restricted Kronecker), with $m=\operatorname{poly}(n)$, such that $M$ contains a matching iff the Kronecker coefficient associated with the partition triple $\phi(E)$ is positive.

Since 3D Matching is in NP, it follows from 4.2 that there exists a polynomial-time many-one reduction $\phi$ from 3D Matching to the Restricted Kronecker problem of deciding positivity of the Kronecker coefficient $k^{\lambda}_{\mu,\pi}$, with $(\lambda,\mu,\pi)$ satisfying the constraints 2–\short6. We have to show that this reduction $\phi$ can be chosen to be injective. We can obtain such an injective reduction $\phi$ by composing the following sequence of polynomial-time computable one-one-reductions (1):

From 3D Matching to 4-Partition (cf. Theorem 4.3 in Garey & Johnson, 1979):

The 4-Partition problem is to decide, given a set $A$ of size $4m$, a positive integer bound $B$, a positive integer size $s(a)$ for each $a\in A$ such that $B/5<s(a)<B/3$ and $\sum_{a\in A}s(a)=mB$, whether $A$ can be partitioned into $m$ disjoint subsets $A_{1},\ldots,A_{m}$, each of size four, such that, for each $1\leq i\leq m$, $\sum_{a\in A_{i}}s(a)=B$. We denote such an instance of 4-Partition by the tuple $(A,m,B,s)$.

The reduction in Garey & Johnson (1979) maps a given instance $(M,W,X,Y,q)$ of 3D Matching to an instance $(A,m,B,s)$ of 4-partition, where:

The set $A$ has $4|M|=O(q^{3})$ elements, one for each occurrence of a member of $W\cup X\cup Y$ in a triple in $M$ and one for each triple in $M$.

Let $W=\{w_{1},\ldots,w_{q}\}$, $X=\{x_{1},\ldots,x_{q}\}$, and $Y=\{y_{1},\ldots,y_{q}\}$. Given any $z\in W\cup X\cup Y$, let $N(z)$ denote the number of triples in $M$ that contain $z$, and let $z,z,\ldots,z[N(z)]$ denote the elements in $A$ corresponding to $z$. Let $r=32q$, and define

Let $u_{l}$ denote the single element corresponding to a particular triple $m_{l}=(w_{i},x_{j},y_{k})\in M$. For any such $u_{l}$, let $s(u_{l})=10r^{4}-kr^{3}-jr^{2}-ir+8$.

Note that $\max\{s(a)|a\in A\}\leq 2^{16}|A|^{4}$. This means 4-Partition is NP-complete in the strong sense Garey & Johnson (1979). It can be checked that this reduction is injective.

From 4-Partition to 3-Partition (cf. Theorem 4.4 in Garey & Johnson (1979)):

The 3-Partition problem is to decide, given a set $A$ of size $3m$, a positive integer bound $B$, a positive integer size $s(a)$ for each $a\in A$ such that $B/4<s(a)<B/2$ and $\sum_{a\in A}s(a)=mB$, whether $A$ can be partitioned into $m$ disjoint subsets $A_{1},\ldots,A_{m}$, each of size three, such that, for each $1\leq i\leq m$, $\sum_{a\in A_{i}}s(a)=B$. We denote an instance of 3-Partition by the tuple $(A,m,B,s)$.

The reduction in Garey & Johnson (1979) maps an instance $(A,m,B,s)$ of 4-Partition, with $|A|=4m$ and $\max\{s(a)|a\in A\}\leq 2^{16}|A|^{4}$, to the instance $(A^{\prime},m^{\prime},B^{\prime},s^{\prime})$ of 3-Partition, where $A^{\prime}$ has $m^{\prime}=O(m^{2})$ elements: one element $w_{i}$ for each element $a_{i}$ of $A$, two elements $u_{i,j}$ and $\bar{u}_{i,j}$ for each pair $(a_{i},a_{j})$ of elements from $A$, and $8m^{2}-3m$ filler elements $u^{*}_{k}$, $1\leq k\leq 8m^{2}-3m$. Their sizes are:

We let $B^{\prime}=64B+4$. It can be checked that this reduction is injective.

From 3-Partition to Machine Flow, the decision version of the two-machine flow scheduling problem with unit processing times defined in Chapter 3 in Yu (1996) (where it is called F2UD’):

The Machine Flow problem is to decide, given two machines M1 and M2, each of which can process at most one job at a time, and $n$ jobs $j$, $1\leq j\leq n$, where each job takes unit processing time and the job $j$ is assigned a delay $l_{j}$ that describes the minimum amount of time between the completion of the job $j$ on M1 and its start on M2, and a threshold $y$, whether there exists a feasible schedule of the jobs so that the last job is completed before time $y$.

The reduction in Yu (1996) from 3-Partition to Machine Flow goes as follows. Without loss of generality, we consider a modified version of 3-Partition by multiplying the partition elements by $4m$. Thus we are given a set of positive integers $A=\{a_{1},\ldots,a_{3m}\}$ and a positive integer $B$ such that (1) $B<a_{i}<2B$ for all $i$, (2) $\sum_{j}a_{j}=4mB$, (3) $a_{i}=0$ (mod $m$) for all $i$, and (4) $4B=0$ (mod $m$). The problem is to decide if $A$ can be partitioned into $m$ disjoint 3-element subsets $A_{1},\ldots,A_{m}$ such that $\sum_{a_{j}\in A_{i}}a_{j}=4B$, for all $i$. An instance of this modified version of 3-Partition is mapped to an instance of Machine Flow with delays (1) $l_{j}=a_{j}$ for $1\leq j\leq 3m$, (2) $l_{j}=0$ for $3m+1\leq j\leq 4mB$, (3) $l_{j}=u+1$ for $4mB+1\leq j\leq mu$, where $u=4(m+1)B$, and (4) the threshold $y=n+4mB+2$, where $n=mu$ is the total number of jobs. It can be checked that this reduction is injective.

From Machine Flow to RN3DM (Restricted Numerical 3-Dimensional Matching, cf. page 31 in Yu, 1996):

The RN3DM problem is to decide, given a positive integer set $U=\{u_{1},\ldots,u_{n}\}$ and a positive integer $e$ such that $\sum_{j=1}^{n}u_{j}+n(n+1)=ne$, whether there exist two $n$-permutations $\lambda$ and $\mu$ such that $j+\lambda(j)+u_{\mu(j)}=e$ for $1\leq j\leq n$. (It can be assumed that each $u_{i}<e-1$).

The reduction (Corollary 3 on page 32 in Yu, 1996) maps an instance of Machine Flow to that of RN3DM given by $u_{j}=l_{j}$ for $1\leq j\leq n$, and $e=y$. We assume that the instance of Machine Flow here arises in the reduction from 3-Partition to Machine Flow given in (III) above. This will ensure that $\sum_{j}u_{j}+n(n+1)=ne$ and each $u_{i}<e-1$, which we require for (V) below to be injective. It can be checked that this reduction is injective.

From RN3DM to RNMTS (Restricted Numerical Matching with Target Sums, cf. Brunetti et al., 2008):

The RNMTS problem is to decide, given positive integers $y_{1},\ldots,y_{n}$ such that $2\leq y_{1}\leq y_{2}\leq\cdots\leq y_{n}\leq 2n$ and $\sum_{i}y_{i}=n(n+1)$, if there exist $n$-permutations $\sigma$ and $\pi$ such that $\sigma(k)+\pi(k)=y_{k}$ for $1\leq k\leq n$.

RN3DM is mapped to RNMTS by letting $y_{j}=e-u_{j}$ and then reordering the $y_{j}$ as per their values. It can be checked that this reduction is injective.

The Permutation problem (page 69 in Brunetti et al., 2008, where it is called Permutation ($S_{3}$)) is to decide, given non-negative integers $z_{2},\ldots,z_{2n}\in\{0,\ldots,n\}$, whether there exists an $n\times n$ permutation matrix $P$ such that $\sum_{i,j:i+j=l}P_{i,j}=z_{l}$ for $2\leq l\leq 2n$.

The reduction in Brunetti et al. (2008) maps an instance $y=(y_{1},\ldots,y_{n})$ of RNMTS to an instance $z=(z_{2},\ldots,z_{2n})$ of Permutation by setting $z_{l}=|\{k\leq n\ |\ y_{k}=l\}|$. It can be checked that this reduction is injective.

Special Consistency is the problem addressed in 3.6, namely, the problem of deciding positivity of $t^{\lambda}_{\mu,\pi}$, given $\lambda,\mu$ and $\pi$ in unary, when $(\lambda^{T},\mu^{T},\pi^{T})$ is restricted to be of the form 6.

The reduction in Brunetti et al. (2001) maps an instance $z=(z_{2},\ldots,z_{2n})$ of Permutation to an instance $(\lambda,\mu,\pi)$ of Special Consistency satisfying 6, with $r=n-1$ and $d_{i}=z_{i+2}$, $0\leq i\leq 2r$ (it can be shown that $\sum_{k}d_{k}=r+1$, and $\sum_{k}kd_{k}=r(r+1)$). This reduction is injective.

From Special Consistency to Restricted Kronecker:

The reduction given in the proof of 4.2 is also injective.

1.5 follows from 5.1 and 5.3. This proof also shows that the superpolynomially many partition triples in 1.5 can be constructed explicitly (as defined in 1.5).

In the preceding proof, we can use, in place of 3D Matching, any problem in NP which has a polynomial-time-computable padding function (Berman & Hartmanis, 1977), and which can be reduced by a polynomial-time one-one reduction to Restricted Kronecker. For example, Sat also has a polynomial-time-computable padding function, and it can also be reduced by a polynomial-time one-one reduction to Restricted Kronecker. This reduction is obtained by composing the injective reduction from Sat to 3D Matching given in Garey & Johnson (1979) with the injective reduction from 3D Matching to Restricted Kronecker given in the proof of 5.3.

Though the reduction $\phi$ in 5.3 is polynomial-time computable, the blow-up in size can be substantial. For example, let us start with a trivial instance of the 3D Matching problem, wherein $q=2$, $W=\{w_{1},w_{2}\}$, $X=\{x_{1},x_{2}\}$, $Y=\{y_{1},y_{2}\}$, and $M=\{(w_{1},x_{1},y_{1}),(w_{2},x_{1},y_{2}),(w_{1},x_{2},y_{2})\}$. Clearly, $M$ does not contain a matching.

It can be checked that $\phi(M,W,X,Y,q)$, with $\epsilon=1$ in condition 3, is a partition triple whose height is $>10^{16}$ and the total size is $>10^{46}$. By 5.3, the Kronecker coefficient associated with this partition triple is zero. One cannot verify this fact directly using a computer, since computation of Kronecker coefficients for partition triples of this height and size is far beyond the reach of computer algebra systems. Thus 5.3 maps instances of 3D Matching which do not contain matching for trivial reasons to partition triples whose associated Kronecker coefficients vanish for highly nontrivial reasons. Thus the image of something trivial is highly nontrivial. This happens because of the nontriviality of the sequence of reductions that produce the image.

2 Proof of 1.6

For the proof of 1.6, we need the following lemma, which proves a variant of the result in Fortune (1979) that coNP-complete languages cannot be sparse unless P=NP.

Let $\mathcal{L}$ be a coNP-hard language given as a disjoint union

where $\mathcal{L}^{\prime}$ is sparse (i.e., there are only $\operatorname{poly}(n)$ words of length $n$ in $\mathcal{L}^{\prime}$) and $\mathcal{L}^{\prime\prime}\in\mbox{NP}\cap\mbox{coNP}$. Then $\mbox{coNP}=\mbox{NP}$.

We will show that the assumptions imply that $\mbox{SAT}^{c}$ (the complement of SAT) is in NP – this would imply that $\mbox{coNP}\subseteq\mbox{NP}$, and hence, $\mbox{coNP}=\mbox{NP}$. For this, we adapt the proof in Mahaney (1982); Fortune (1979).

Since $\mathcal{L}$ is coNP-hard, there exists a polynomial-time many-one reduction $R$ such that $R(\mbox{SAT})\subseteq{\mathcal{L}}^{c}$ and $R(\mbox{SAT}^{c})\subseteq\mathcal{L}$. Since $\mathcal{L}^{\prime\prime}$ is in $\mbox{NP}\cap\mbox{coNP}$, there exist non-deterministic Turing machines $M_{1}$ and $M_{2}$ such that, given input $x$, $M_{1}$ halts (in polynomial time) if and only if $x\in\mathcal{L}^{\prime\prime}$, while $M_{2}$ halts (in polynomial time) if and only if $x\not\in\mathcal{L}^{\prime\prime}$.

Let $F$ be a formula for which we have to decide unsatisfiability. We perform depth-first search on the binary tree obtained by self-reducing $F$ (the root of this tree is $F$, and the children of a node $G$ are $G_{0}$ and $G_{1}$, the formulas of smaller size obtained by specializing the first variable in $G$ to true or false, and applying trivial simplifications), starting at the root node. We maintain a table $\mathcal{U}$ of labels ($R$-values) of unsatisfiable formulae, starting with $\mathcal{U}:=\{R(\mbox{false})\}$. At each node $G$, we first compute $R(G)$ and then do one of the following:

If $R(G)\in\mathcal{U}$, prune the subtree and return to the parent node.

Otherwise, if $G=\mbox{true}$, enter an infinite loop.

Otherwise, run both non-deterministic Turing machines $M_{1}$ and $M_{2}$ in parallel on the input $R(G)$ until one of the two halts (which will always happen, for some sequence of non-deterministic choices, in polynomial time):

If $M_{1}$ halts (in which case $R(G)\in\mathcal{L}^{\prime\prime}\subseteq\mathcal{L}$, and hence, $G$ is unsatisfiable), add $R(G)$ to $\mathcal{U}$, prune the subtree and return to the parent node.

If $M_{2}$ halts, visit both children $G_{0}$ and $G_{1}$. Upon return (if this happens), it will always be true that $G_{0}$ and $G_{1}$ are unsatisfiable, and hence $R(G_{0}),R(G_{1})\in\mathcal{U}$ and $G$ is unsatisfiable. Thus add $R(G)$ to $\mathcal{U}$ and return to the parent node.

It is clear that this algorithm can be understood as a non-deterministic Turing machine that halts if and only if $F$ is unsatisfiable.

It suffices to show that, if $F$ is unsatisfiable, this algorithm halts in polynomial time. For this, it suffices to show that the number of interior nodes that are visited by the algorithm is polynomial in the size $|F|$ of the formula $F$ (since the tree is binary, the number of visited leaves is at most twice the number of visited interior nodes). Now observe that interior nodes only arise in the case where $M_{2}$ halts on input $R(G)$, in which case $R(G)\in\mathcal{L}^{\prime}$. Thus any interior node is necessarily labeled by an element of the sparse set $\mathcal{L}^{\prime}$. We can thus conclude the argument precisely as in Lemma 2.2 of Mahaney (1982): If $G$ and $G^{\prime}$ are two interior nodes that have the same label, $R(G)=R(G^{\prime})\in\mathcal{L}^{\prime}$, then they necessarily ought to appear in the same branch of the search tree (because we proceed by depth-first search). As the depth of the tree is no more than $m$ – the number of variables in $F$ – we find that each label can occur at most $m$ times. Therefore, the number of visited interior nodes can be upper bounded by $m\cdot p(q(\lvert F\rvert))$, where $q$ is a polynomial that bounds the increase in length induced by the reduction $R$ and $p=p(n)$ is a polynomial that bounds the number of strings of length $\leq n$ in the sparse set $\mathcal{L}^{\prime}$. We conclude that $\mbox{SAT}^{c}\in\mbox{NP}$.