3·1. A sketch of the proof of Aldous’ conjecture on graphs

The proof scheme of Theorem 1·1 in [ Reference Caputo, Liggett and RichthammerCLR10 ] builds on [ Reference Handjani and JungreisHJ96 ] and uses induction on the number of vertices in the graph G. Assume the statement of Theorem 1·1 is true for every weighted graph on $n-1$ vertices. Because the weights on the edges of G may be zero, we may assume without loss of generality that G is the full graph on n vertices numbered $1,\ldots,n$ with non-negative weights $c_{i,j}\ge0$ for every $1\le i{\,\lt\,}j\le n$ . As in (1·2), write $\Sigma=\sum_{i{\,\lt\,}j}c_{i,j}\left(i\;j\right)$ . Our goal is to prove that $\lambda_{2}\left(\Sigma,{\mathrm{\mathbf{D}}}\right)=\lambda_{2}\left(\Sigma,{\mathrm{\mathbf{R}}}\right)$ . By Lemma 2·1, this is equivalent to that $\lambda_{1}\left(\Sigma,V_{\mu}\right)\le\lambda_{1}\left(\Sigma,V_{\left(n-1,1\right)}\right)$ for every $\mu\vdash n$ such that $\mu\ne\left(n\right),\left(n-1,1\right)$ . Equivalently, if we let

\[S_{G}=\sum_{i{\,\lt\,}j}c_{i,j}\alpha_{\left\{ i,j\right\} }=\sum_{i{\,\lt\,}j}c_{i,j}\left({\mathrm{id}}-\left(i\;j\right)\right)=\left(\sum_{i{\,\lt\,}j}c_{i,j}\right)-\Sigma\in\mathbb{R}\left[{\mathrm{Sym}}_{n}\right]\!,\]

we ought to show that

\[\lambda_{\min}\left(S_{G},V_{\mu}\right)\ge\lambda_{\min}\left(S_{G},V_{\left(n-1,1\right)}\right)\]

for every $\mu\vdash n$ as above, where $\lambda_{\min}\left(S_{G},V_{\mu}\right)=\lambda_{\min}\left(S_{G}|_{V_{\mu}}\right)$ is the smallest eigenvalue of $S_{G}|_{V_{\mu}}$ . Recall from Lemma 2·3 that $\alpha_{A}\ge0$ for every $A\subseteq\left[n\right]$ so $S_{G}\ge0$ . If G is disconnected (when disregarding weight-0 edges), then $\lambda_{\min}\left(S_{G},V_{\left(n-1,1\right)}\right)=0$ and we are done. So we may assume that G is connected, and in particular that for every vertex, the sum of the weights of edges incident to it is positive.

Define a weighted graph H on the vertices $2,\ldots,n$ as follows: For every $2\le i{\,\lt\,}j\le n$ , the weight of the edge $\left\{ i,j\right\} $ is $c_{i,j}+c_{1,i}c_{1,j}/\sum_{k=2}^n c_{1,k}$ . Denote by $S_{H}$ the corresponding element of $\mathbb{R}$ $\left[{\mathrm{Sym}}_{n-1}\right]$ , and by $S_{H\sqcup\left\{ 1\right\} }$ the image of $S_{H}$ through the embedding of ${\mathrm{Sym}}_{n-1}$ in ${\mathrm{Sym}}_{n}$ as the stabilizer of the point 1. We have

(3·1) \begin{equation}\Delta\,{\stackrel{\mathrm{def}}{=}}\, S_{G}-S_{H\sqcup\left\{ 1\right\} }=\sum_{j=2}^{n}c_{1,j}\alpha_{\left\{ 1,j\right\} }-\frac{1}{\sum_{j=2}^{n}c_{1,j}}\cdot\sum_{2\le i{\,\lt\,}j\le n}c_{1,i}c_{1,j}\alpha_{\left\{ i,j\right\} }\end{equation}

is (up to a constant) the “octopus element” from Theorem 1·6. We claim that the following equality and inequalities hold for every $\mu\vdash n$ with $\mu\ne\left(n\right),\left(n-1,1\right)$ , yielding Theorem 1·1

(3·2) \begin{eqnarray}\lambda_{\min}\left(S_{G},V_{\mu}\right) & \stackrel{\left(1\right)}{\ge} & \lambda_{\min}\left(S_{H\sqcup\left\{ 1\right\} },V_{\mu}\right)\nonumber \\ & \stackrel{\left(2\right)}{=} & \min_{\mu'=\mu-\square}\lambda_{\min}\left(S_{H},V_{\mu'}\right)\nonumber \\ & \stackrel{\left(3\right)}{\ge} & \lambda_{\min}\left(S_{H},V_{\left(n-2,1\right)}\right)\nonumber \\ & \stackrel{\left(4\right)}{\ge} & \lambda_{\min}\left(S_{G},V_{\left(n-1,1\right)}\right)\!.\end{eqnarray}

Indeed,

1. (i) The inequality $\left(1\right)$ uses the Octopus Inequality from Theorem 1·6: $S_{G}-S_{H\sqcup\left\{ 1\right\} }\ge0$ as an operator by (1·7), which means that $\left(S_{G}-S_{H\sqcup\left\{ 1\right\} }\right)|_{V_{\mu}}\ge0$ for every $\mu\vdash n$ and $\left(1\right)$ follows.

2. (ii) The equality $\left(2\right)$ follows from the branching rule in ${\mathrm{Sym}}_{n}$ [ Reference Fulton and HarrisFH13 , exercise 4·53]: the element $S_{H\sqcup\left\{ 1\right\} }$ is supported on the subgroup $\mathrm{Stab}_{{\mathrm{Sym}}_{n}}\left(1\right)\cong{\mathrm{Sym}}_{n-1}$ and the restriction of $V_{\mu}$ to ${\mathrm{Sym}}_{n-1}$ satisfies $V_{\mu}\cong\bigoplus_{\mu'=\mu-\square}V_{\mu'}$ , where the sum is over all Young diagrams $\mu'$ with $n-1$ squares obtained from $\mu$ by removing a single square (which must be the rightmost square of some row of $\mu$ and the bottom square of some column).

3. (iii) The inequality $\left(3\right)$ follows from the induction hypothesis together with the observation that as $\mu\ne\left(n\right)\!,\left(n-1,1\right)$ then after removing a single square we get that $\mu'\ne\left(n-1\right)$ .

4. (iv) Finally, let us justify the inequality $\left(4\right)$ . Consider the standard representation ${\mathrm{\mathbf{D}}}_{n-1}\cong V_{\left(n-2,1\right)}\oplus V_{\left(n-1\right)}$ of ${\mathrm{Sym}}_{n-1}$ . Recall that $V_{\left(n-1\right)}={\mathrm{\mathbf{I}}}_{n-1}$ is the trivial representation so $\alpha_{A}|_{V_{\left(n-1\right)}}=0$ for all A and $S_{H}|_{V_{\left(n-1\right)}}=0$ . As $S_{H}\ge0$ , we get that $\lambda_{\min}\left(S_{H},V_{\left(n-2,1\right)}\right)$ is the second smallest eigenvalue of $S_{H}|_{{\mathrm{\mathbf{D}}}_{n-1}}$ . Considering $S_{H}|_{{\mathrm{\mathbf{D}}}_{n-1}}$ and $S_{H\sqcup\left\{ 1\right\} }|_{{\mathrm{\mathbf{D}}}_{n}}$ as matrices in the standard basis corresponding to the elements $\left\{ 2,\ldots,n\right\} $ and $\left[n\right]$ , respectively, we see that $S_{H\sqcup\left\{ 1\right\} }|_{{\mathrm{\mathbf{D}}}_{n}}$ is obtained from $S_{H}|_{{\mathrm{\mathbf{D}}}_{n-1}}$ by adding a zero row and a zero column, so $\lambda_{\min}\left(S_{H},V_{\left(n-2,1\right)}\right)$ is the third smallest eigenvalue of $S_{H\sqcup\left\{ 1\right\} }|_{{\mathrm{\mathbf{D}}}_{n}}$ . Finally, Lemma 2·9 shows that the octopus element $\Delta$ from (3·1) satisfies that $\Delta|_{{\mathrm{\mathbf{D}}}_{n}}$ is a rank-1 (non-negative) element. By Cauchy’s interlacing formula (e.g., [ Reference Marcus, Spielman and SrivastavaMSS14 , lemma 3·4]) the eigenvalues $\lambda_{n}\le\dotsb\le\lambda_{1}$ of $S_{H\sqcup\left\{ 1\right\} }|_{{\mathrm{\mathbf{D}}}_{n}}$ interlace the eigenvalues $\rho_{n}\le\dotsb\le\rho_{1}$ of $S_{G}|_{{\mathrm{\mathbf{D}}}_{n}}=\left(S_{H\sqcup\left\{ 1\right\} }+\Delta\right)|_{{\mathrm{\mathbf{D}}}_{n}}$ in the sense that

   \[\lambda_{n}\le\rho_{n}\le\lambda_{n-1}\le\rho_{n-1}\le\dotsb\le\lambda_{1}\le\rho_{1},\]
   so $\lambda_{\min}\left(S_{H},V_{\left(n-2,1\right)}\right)=\lambda_{n-2}\ge\rho_{n-1}=\lambda_{\min}\left(S_{G},V_{\left(n-1,1\right)}\right)$ .

3·2. A general inequality scheme

Recall that our goal is to generalise Aldous’ conjecture to hypergraphs, in the form of Conjecture 1·2’. This conjecture asserts that $U=\sum_{A\subseteq\left[n\right]}w_{A}J_{A}$ as in (1·5) satisfies $\lambda_{2}\left(U,{\mathrm{\mathbf{D}}}\right)=\lambda_{2}\left(U,{\mathrm{\mathbf{R}}}\right)$ . By Lemma 2·1, this is equivalent to that $\lambda_{1}\left(U,V_{\mu}\right)\le\lambda_{1}\left(U,V_{\left(n-1,1\right)}\right)$ for all $\mu\vdash n$ with $\mu\ne\left(n\right)$ , $\left(n-1,1\right)$ . As $\alpha_{A}=\left|A\right|-{J_{A}}/{\left(\left|A\right|-1\right)!}$ , Conjecture 1·2’ is also equivalent to that for arbitrary non-negative weights $\left\{ w_{A}\right\} _{A\subseteq\left[n\right]}$ , the element $S_{G}=\sum_{A\subseteq\left[n\right]}w_{A}\alpha_{A}$ satisfies $\lambda_{\min}\left(S_{G},V_{\mu}\right)\ge\lambda_{\min}\left(S_{G},V_{\left(n-1,1\right)}\right)$ for all $\mu\vdash n$ with $\mu\ne\left(n\right)$ , $\left(n-1,1\right)$ .

In an attempt to generalise to hypergraphs the argument summarised in (3·2), one may try to use induction on the number of vertices again. If, as above, 1 is the “pivotal” vertex one tries to omit, one may hope to find an inequality similar to the Octopus Inequality (1·7), where one side (the larger side) is a weighted sum over all $\alpha_{A}$ with A an hyper-edge containing 1 (and coefficients corresponding to the weights), and the other side consists of $\alpha_{A}$ ’s with A’s not containing 1. Such an inequality would allow us to imitate the first step $\left(1\right)$ in (3·2). Steps $\left(2\right)$ and $\left(3\right)$ are true by the branching rule and induction hypothesis for general hypergraphs. Finally, in order to recover the inequality $\left(4\right)$ in (3·2), it could be desirable that the difference between the two sides of our inequality, when restricted to the standard representation ${\mathrm{\mathbf{D}}}_{n}$ , be of rank 1.

Such considerations lead us to the following proposed inequality. Let $A_{1},\dotsc,A_{t}\subseteq\{2,3,\dotsc,n\}$ , and let $c_{1},\dotsc,c_{t}\geq0$ be non-negative weights. Denote $C\,{\stackrel{\mathrm{def}}{=}}\,\sum c_{i}\left|A_{i}\right|$ . When does the following inequality hold?

(3·3) \begin{equation}C\cdot\sum c_{i}\alpha_{A_{i}\cup\{1\}}\stackrel{?}{\ge}\sum(C\cdot c_{i}+c_{i}^{2})\alpha_{A_{i}}+\sum_{i{\,\lt\,}j}c_{i}c_{j}\left(\alpha_{A_{i}\cup A_{j}}+\alpha_{A_{i}\cap A_{j}}-\alpha_{A_{i}\setminus A_{j}}-\alpha_{A_{j}\setminus A_{i}}\right).\end{equation}

This inequality indeed generalises the Octopus Inequality (1·7) (there $A_{1},\ldots,A_{t}$ are all singletons, and recall that $\alpha_{\left\{ i\right\} }=\alpha_{\emptyset}=0$ ). It also has the property that restricted to the standard representation ${\mathrm{\mathbf{D}}}$ , it coincides with the Octopus Inequality: this is the content of Lemma 3·2 below. Therefore, restricted to the standard representation ${\mathrm{\mathbf{D}}}$ , the difference between the two sides of (3·3) is rank-1 non-negative by Lemma 2·9, and step $\left(4\right)$ in (3·2) holds for this generalised inequality as well.

However, there are two main problems with this attempt to generalise the argument in (3·2) to hypergraphs:

1. (i) First, the right-hand side of (3·3) contains $\alpha_{A}$ ’s with negative coefficients, which means that if we simply replace in our weighted hypergraph all the hyper-edges containing 1 (represented in the left-hand side of (3·3)) with the hyper-edges as in the right-hand side of (3·3), we may get a new hypergraph with some of its weights negative, and in this regime Conjecture 1·2 is not true in general.

2. (ii) Second, and more importantly, the inequality (3·3) in this general form, does always not hold. For example, it does not hold for $n=4$ , $A_{1}=\left\{ 2\right\} $ , $A_{2}=\left\{ 2,3,4\right\} $ and $c_{1}=c_{2}=1$ . See Section 8 for more details.

However, the inequality (3·3) does hold true if certain restrictions on the $A_{i}$ ’s are set. First, as mentioned above, if all $A_{i}$ ’s are singletons, (3·3) becomes the Octopus Inequality from Theorem 1·6. More generally, (3·3) holds if all the $A_{i}$ ’s are disjoint – this is the content of Theorem 1·7; if all the $A_{i}$ ’s are of size k or $k-1$ and all contain some fixed subset of size $k-1$ , where $k\in\left[n\right]$ – this is the content of Theorem 1·8; and if all sets are of size k or $k-1$ and all are contained in the some fixed subset of $\left[n\right]$ of size k – this is the content of Theorem 1·9.

As stated above, the following lemma shows that for general sets $A_{1},\dotsc,A_{t}$ and weights $c_{1},\dotsc,c_{t}$ , the inequality (3·3) restricted to the standard representation becomes an Octopus Inequality.

Lemma 3·2. Let $A_{1},\dotsc,A_{t}\subseteq\{2,3,\dotsc,n\}$ , let $c_{1},\dotsc,c_{t}\geq0$ and denote $C=\sum c_{i}\left|A_{i}\right|$ . Consider the difference between the two sides of (3·3):

\[\Delta\,{\stackrel{\mathrm{def}}{=}}\, C\cdot\sum_{i}c_{i}\alpha_{A_{i}\cup\{1\}}-\sum_{i}(C\cdot c_{i}+c_{i}^{2})\alpha_{A_{i}}-\sum_{i{\,\lt\,}j}c_{i}c_{j}\left(\alpha_{A_{i}\cup A_{j}}+\alpha_{A_{i}\cap A_{j}}-\alpha_{A_{i}\setminus A_{j}}-\alpha_{A_{j}\setminus A_{i}}\right)\!.\]

There exist non-negative reals $x_{2},\ldots,x_{n}$ such that

\[\Delta=_{\mathbf{D}}\left(\sum_{2\leq i\leq n}x_{i}\right)\left(\sum_{2\leq j\leq n}x_{j}\alpha_{\left\{ 1,j\right\} }\right)-\sum_{2\leq i{\,\lt\,}j\leq n}x_{i}x_{j}\alpha_{\left\{ i,j\right\} }.\]

In particular, $\Delta|_{{\mathrm{\mathbf{D}}}}$ is a non-negative rank-1 (or zero) operator by Lemma 2·9.

Proof. For $2\leq i\leq n$ define

\[x_{i}=\sum_{j\colon i\in A_{j}}c_{j}.\]

Note that $\sum x_{i}=\sum_{i}\sum_{j:i\in A_{j}}c_{j}=\sum_{j}c_{j}|A_{j}|=C$ . By Lemma 2·6, we have

\begin{align*}\sum c_{i}\left(\alpha_{A_{i}\cup\{1\}}-\alpha_{A_{i}}\right) & =_{\mathbf{D}}\frac{1}{2}\sum_{i}c_{i}\left(\sum_{j,k\in A_{i}\cup\left\{ 1\right\} }\alpha_{\left\{ j,k\right\} }-\sum_{j,k\in A_{i}}\alpha_{\left\{ j,k\right\} }\right)\\ & =\sum_{i}c_{i}\sum_{j\in A_{i}}\alpha_{\left\{ 1,j\right\} }=\sum_{j}\alpha_{\{1,j\}}\sum_{i:j\in A_{i}}c_{i}=\sum_{j}x_{j}\alpha_{\left\{ 1,j\right\} }.\end{align*}

It remains to prove that

(3·4) \begin{equation}\sum_{2\leq i{\,\lt\,}j\leq n}x_{i}x_{j}\alpha_{\left\{ i,j\right\} }=_{\mathbf{D}}\sum_{i}c_{i}^{2}\alpha_{A_{i}}+\sum_{i{\,\lt\,}j}c_{i}c_{j}\left(\alpha_{A_{i}\cup A_{j}}+\alpha_{A_{i}\cap A_{j}}-\alpha_{A_{i}\setminus A_{j}}-\alpha_{A_{j}\setminus A_{i}}\right)\!.\end{equation}

We start by calculating

(3·5) \begin{align}\sum_{2\leq i{\,\lt\,}j\leq n}x_{i}x_{j}\alpha_{\left\{ i,j\right\} } & =\frac{1}{2}\sum_{i,j}\alpha_{\left\{ i,j\right\} }\sum_{s_{1}\colon i\in A_{s_{1}}}\sum_{s_{2}\colon j\in A_{s_{2}}}c_{s_{1}}c_{s_{2}}\nonumber \\ & =\frac{1}{2}\sum_{s_{1},s_{2}}c_{s_{1}}c_{s_{2}}\sum_{\left(i,j\right)\in A_{s_{1}}\times A_{s_{2}}}\alpha_{\left\{ i,j\right\} }.\end{align}

If $s_{1}=s_{2}$ we have by Lemma 2·6 that

(3·6) \begin{equation}\frac{1}{2}\sum_{(i,j)\in A_{s_{1}}\times A_{s_{1}}}\alpha_{\{i,j\}}=_{\mathbf{D}}\alpha_{A_{s_{1}}}.\end{equation}

We now deal with the case $s_{1}\ne s_{2}$ . Consider the following multiset identity, valid for any sets A and B:

\[A\times B+B\times A=\left(A\cup B\right)^{2}+\left(A\cap B\right)^{2}-\left(A\backslash B\right)^{2}-\left(B\backslash A\right)^{2}\!.\]

By this identity and Lemma 2·6, in the case $s_{1}\ne s_{2}$ we have that

(3·7) \begin{align}&{{\frac{1}{2}\left[\sum_{\left(i,j\right)\in A_{s_{1}}\times A_{s_{2}}}+\sum_{\left(i,j\right)\in A_{s_{2}}\times A_{s_{1}}}\right]\alpha_{\{i,j\}}}}\qquad\qquad\nonumber \\ & \qquad\quad =\frac{1}{2}\left[\sum_{(i,j)\in\left(A_{s_{1}}\cup A_{s_{2}}\right)^{2}}+\sum_{(i,j)\in\left(A_{s_{1}}\cap A_{s_{2}}\right)^{2}}-\sum_{(i,j)\in\left(A_{s_{1}}\backslash A_{s_{2}}\right)^{2}}-\sum_{(i,j)\in\left(A_{s_{1}}\backslash A_{s_{2}}\right)^{2}}\right]\alpha_{\{i,j\}}\nonumber \\ &\qquad\quad =_{\mathbf{D}}\alpha_{A_{s_{1}}\cup A_{s_{2}}}+\alpha_{A_{s_{1}}\cap A_{s_{2}}}-\alpha_{A_{s_{1}}\setminus A_{s_{2}}}-\alpha_{A_{s_{2}}\setminus A_{s_{1}}}.\end{align}

Putting (3·6) and (3·7) into (3·5), we get (3·4) as needed.

3·3. Reducing Theorem 1·3’ to Theorem 1·8

We can now prove our main result about hypergraphs — Theorem 1·3’ — assuming Theorem 1·8, which generalises the Octopus Inequality. Theorem 1·8 is proved in Section 5.

Proof of Theorem 1·3’ assuming Theorem 1·8. Let $B\subseteq\left[n\right]$ . We need to show that

\[U=\sum_{\substack{B\subseteq A\subseteq\left[n\right]\colon\\\left|A\setminus B\right|\le2}}w_{A}J_{A}\in\mathbb{R}\left[{\mathrm{Sym}}_{n}\right]\]

satisfies $\lambda_{2}\left(U,{\mathrm{\mathbf{D}}}\right)=\lambda_{2}\left(U,{\mathrm{\mathbf{R}}}\right)$ for arbitrary non-negative weights $\left\{ w_{A}\right\} _{A}$ . By Lemma 2·1 and the definition of $\alpha_{A}$ , this is equivalent to that for arbitrary non-negative weights $\left\{ w_{A}\right\} _{A}$ , the element

\[S_{G}=\sum_{\substack{B\subseteq A\subseteq\left[n\right]\colon\\\left|A\setminus B\right|\le2}}w_{A}\alpha_{A}\in\mathbb{R}\left[{\mathrm{Sym}}_{n}\right]\]

satisfies that for every $\mu\vdash n$ with $\mu\ne\left(n\right),\left(n-1,1\right)$

\[\lambda_{\min}\left(S_{G},V_{\mu}\right)\ge\lambda_{\min}\left(S_{G},V_{\left(n-1,1\right)}\right)\!.\]

We prove this by induction on $n-\left|B\right|$ . If $B=\left[n\right]$ , then $S_{G}=w_{B}\alpha_{B}$ , by Lemma 2·4 $\lambda_{\min}\left(S_{G},V_{\mu}\right)=\omega_{B}n$ for every $\mu\vdash n$ with $\mu\ne\left(n\right)$ and we are done.

Now assume that $\left|B\right|{\,\lt\,}n$ and assume the theorem is true whenever $n-\left|B\right|$ is smaller. As in Section 3·1, if the hypergraph G is disconnected (disregarding weight-0 hyper-edges), then $S_{G}\ge0$ and $\lambda_{\min}\left(S_{G},V_{\left(n-1,1\right)}\right)=0$ and we are done. So we may assume that G is connected. In particular, every vertex is contained in a hyper-edge with a positive weight. Let $v\in\left[n\right]\setminus B$ be a vertex outside B. Without loss of generality, we may assume that $v=1$ .

Denote $t=n-1-\left|B\right|$ , $A_{0}=B$ and $c_{0}=w_{B\cup\left\{ 1\right\} }$ . Let $\left[n\right]\setminus B=\left\{ 1,m_{1},\ldots,m_{t}\right\} $ and for every $i=1,\ldots,t$ let $A_{i}=B\cup\left\{ m_{i}\right\} $ and $c_{i}=w_{A_{i}\cup\left\{ 1\right\} }$ . Also denote $C=\sum_{i=0}^{t}c_{i}\left|A_{i}\right|$ , and note that $C{\,\gt\,}0$ by our assumption that every vertex is contained in a positive-weight hyper-edge.

Now define a hypergraph H on the vertices $\left\{ 2,\ldots,n\right\} $ with hyper-edges consisting of all subsets A containing B and satisfying $\left|A\setminus B\right|\le2$ , with the following non-negative weights $\overline{w}_{A}$ :

(3·8) \begin{equation}\overline{w}_{A}=\begin{cases}w_{A}+c_{0}+\frac{1}{C}\left(c_{0}^{\;2}+\sum_{0\le i{\,\lt\,}j\le t}c_{i}c_{j}\right) & \mathrm{if}\;A=B,\\w_{A}+c_{i}+\frac{1}{C}\left(c_{i}^{\;2}+c_{0}c_{i}\right) & \mathrm{if}\;A=B\cup\left\{ m_{i}\right\} ,1\le i\le t\\w_{A}+\frac{1}{C}c_{i}c_{j} & \mathrm{if}\;A=B\cup\left\{ m_{i},m_{j}\right\} ,1\le i{\,\lt\,}j\le t.\end{cases}\end{equation}

Note that the hypergraph H satisfies the assumptions of Theorem 1·3’ with vertex set $\left\{ 2,\ldots,n\right\} $ and the same special subset B. We denote

\[S_{H\cup\left\{ 1\right\} }=\sum_{\substack{B\subseteq A\subseteq\left\{ 2,\ldots,n\right\} \colon\\\left|A\setminus B\right|\le2}}\overline{w}_{A}\alpha_{A}\in\mathbb{R}\left[{\mathrm{Sym}}_{n}\right]\!,\]

and $S_{H}$ the corresponding element of $\mathbb{R}\;\left[{\mathrm{Sym}}_{n-1}\right]$ (here ${\mathrm{Sym}}_{n-1}$ is embedded in ${\mathrm{Sym}}_{n}$ as the stabiliser of the point 1). By the induction hypothesis, $\lambda_{\min}\left(S_{H},V_{\mu'}\right)\ge\lambda_{\min}\left(S_{H},V_{\left(n-2,1\right)}\right)$ for every $\mu'\vdash n-1$ with $\mu'\ne\left(n-1\right)\!,\left(n-2,1\right)$ . The proof can now be completed as in (3·2). Indeed, for every $\mu\vdash n$ we have

(3·9) \begin{align}\lambda_{\min}\left(S_{G},V_{\mu}\right) & \stackrel{\left(1\right)}{\ge}\lambda_{\min}\left(S_{H\sqcup\left\{ 1\right\} },V_{\mu}\right)\stackrel{\left(2\right)}{=}\min_{\mu'=\mu-\square}\lambda_{\min}\left(S_{H},V_{\mu'}\right)\nonumber \\ & \stackrel{\left(3\right)}{\ge}\lambda_{\min}\left(S_{H},V_{\left(n-2,1\right)}\right)\stackrel{\left(4\right)}{\ge}\lambda_{\min}\left(S_{G},V_{\left(n-1,1\right)}\right)\!.\end{align}

The inequality $\left(1\right)$ follows from that $S_{G}-S_{H\cup\left\{ 1\right\} }$ is, up to a multiplicative constant, the operator which is non-negative by Theorem 1·8. The equality $\left(2\right)$ follows from the branching rule in ${\mathrm{Sym}}_{n}$ [ Reference Fulton and HarrisFH13 , exercise 4·53]. The inequality $\left(3\right)$ holds by the induction hypothesis. Finally, $S_{G}-S_{H\cup\left\{ 1\right\} }$ is a special case of the difference between the two sides of (3·3), so $\left(S_{G}-S_{H\cup\left\{ 1\right\} }\right)\!|_{{\,\mathrm{\mathbf{D}}}}$ coincides with an octopus element by Lemma 3·2, and thus the inequality $\left(4\right)$ is true similarly to the inequality $\left(4\right)$ in (3·2).

5·1. The easy cases: $\mu_{1}\le k-1$ or $\mu_{1}\ge\left|E\right|-1$

Proof. By Lemma 5·2, it is enough to prove that $\Gamma_{ij\ell m}$ is non-negative on $\ker\alpha_{A_{0}}\subseteq V_{\mu}$ . In that subspace $\alpha_{A_{0}}=0$ , and by Corollary 2·5, $\alpha_{B}=\left|B\right|$ for every $A_{0}\subsetneqq B\subseteq E$ . Hence all the operators $\alpha_{A_{i}}$ are scalars, and consequently, so are the operators $U_{ef}$ for all $e,f\in\left\{ i,j,\ell,m\right\} $ . By (5·4) we have

\[U_{ef}=\begin{cases}k\left(k-1\right) & 0=e=f,\\0 & 1\le e=f,\\k^{2}-1 & 0=e{\,\lt\,}f,\\k-1 & 1\le e{\,\lt\,}f.\end{cases}\]

Comparing these constants with $w_{ef}$ from (5·5), we see that $0\leq U_{ef}\leq2w_{ef}$ for all $e,f\in\left\{ i,j,\ell,m\right\} $ , so $|U_{ef}-w_{ef}|\leq w_{ef}$ . We conclude that

\[\left|(U_{ef}-w_{ef})\;{\mathrm{\star}}\;(U_{e'f'}-w_{e'f'})\right|=\left|(U_{ef}-w_{ef})\cdot(U_{e'f'}-w_{e'f'})\right|\leq w_{ef}w_{e'f'},\]

so

\[\Lambda_{efe'f'}=w_{ef}w_{e'f'}-\left(U_{ef}-w_{ef}\right){\mathrm{\star}}\left(U_{e'f'}-w_{e'f'}\right)\geq0.\]

By (5·7) we have $\Gamma_{{ij\ell m}}\geq_{V_{\mu}}0$ .

At this point we have established that $\Gamma_{{ij\ell m}}\ge0$ when $\left|E\right|\le k+1$ , namely, for $\Gamma_{0000}$ , $\Gamma_{000i}$ , $\Gamma_{00ii}$ , $\Gamma_{0iii}$ and $\Gamma_{iiii}$ for every $1\le i\le t$ .

5·2. The case $\mu_{1}=k$

In this subsection we deal with the case that $\mu\vdash\left|E\right|$ with $\mu_{1}=k$ . We assume that $k{\,\lt\,}\left|E\right|-1$ , for otherwise the case $\mu_{1}=k$ is contained in Lemma 5·5. Lemma 5·6 below proves that $\Gamma_{{ij\ell m}}\ge_{V_{\mu}}0$ when $i,j,\ell,m$ are all positive and not necessarily distinct, Lemma 5·7 addresses the case of $\Gamma_{00ij}$ with i and j distinct, Lemma 5·8 the case of $\Gamma_{0iij}$ with i and j distinct, and Lemma 5·9 the case of $\Gamma_{0ij\ell}$ with $i,j,\ell$ distinct. As mentioned above, the remaining cases – $\Gamma_{0000}$ , $\Gamma_{000i}$ , $\Gamma_{00ii}$ , $\Gamma_{0iii}$ and $\Gamma_{iiii}$ – have already been established in Section 5·1.

Proof. By Lemma 5·2, it is enough to prove that $\Gamma_{ij\ell m}$ is non-negative on $\ker\alpha_{A_{0}}\subseteq V_{\mu}$ . By Corollary 2·5, we have $\alpha_{B}=_{V_{\mu}}k+1$ for every $B\subset E$ with $\left|B\right|=k+1$ . As we now show, this fact guarantees that

(5·9) \begin{equation}\left\Vert U_{ef}-w_{ef}\right\Vert \le w_{ef}\end{equation}

for all $e,f{\,\gt\,}0$ . Recall that by Lemma 2·8, $\left\Vert \alpha_{A}-{|A|}/{2}\right\Vert ={{{|A|}/{2}}}$ for any $A\subseteq E$ .

Let us consider first the case $1\le e=f$ . We have by (5·4) and (5·5) that

\begin{eqnarray*}\left\Vert U_{ee}-w_{ee}\right\Vert & = & \left\Vert k\alpha_{A_{e}\cup\{1\}}-(k+1)\alpha_{A_{e}}-\frac{k\left(k+1\right)}{2}\right\Vert \\ & = & \left\Vert k\left(k+1\right)-\left(k+1\right)\alpha_{A_{e}}-\frac{k\left(k+1\right)}{2}\right\Vert \\ & = & \left\Vert \left(k+1\right)\left(\frac{k}{2}-\alpha_{A_{e}}\right)\right\Vert =\left(k+1\right)\frac{k}{2}=w_{ee}.\end{eqnarray*}

In the case $1\le e{\,\lt\,}f$ :

\begin{align*}\left\Vert U_{ef}-w_{ef}\right\Vert & = \big\Vert k(\alpha_{A_{e}\cup\{1\}}+\alpha_{A_{f}\cup\{1\}}-\alpha_{A_{e}}-\alpha_{A_{f}})-\alpha_{A_{e}\cup A_{f}}-\alpha_{A_{0}}-\big(k^{2}+k-1\big)\big\Vert \\ & = \big\Vert k\big(2k+2-\alpha_{A_{e}}-\alpha_{A_{f}}\big)-(k+1)-\big(k^{2}+k-1\big)\big\Vert \\ & = \left\Vert k\left(k-\alpha_{A_{e}}-\alpha_{A_{f}}\right)\right\Vert =k\left\Vert \left(\frac{k}{2}-\alpha_{A_{e}}\right)+\left(\frac{k}{2}-\alpha_{A_{f}}\right)\right\Vert \\ & \quad \leq k\left\Vert \frac{k}{2}-\alpha_{A_{e}}\right\Vert +k\left\Vert \frac{k}{2}-\alpha_{A_{f}}\right\Vert =k^{2}\le k^{2}+k-1=w_{ef}.\end{align*}

As in the proof of Lemma 5·4, we conclude that

\[\left\Vert \left(U_{ef}-w_{ef}\right){\mathrm{\star}}\left(U_{e'f'}-w_{e'f'}\right)\right\Vert \leq w_{ef}w_{e'f'},\]

so $\Lambda_{efe'f'}\geq_{V_{\mu}}0$ whenever $\left\{ e,f,e',f'\right\} =\left\{ i,j,\ell,m\right\} $ , and by (5·7), $\Gamma_{ijlm}\geq_{V_{\mu}}0$ .

Proof. By Corollary 2·5, $\alpha_{A_{i}\cup\left\{ 1\right\} }=_{V_{\mu}}\alpha_{A_{j}\cup\left\{ 1\right\} }=_{V_{\mu}}\alpha_{A_{i}\cup A_{j}}=_{V_{\mu}}k+1$ . As before, it is enough to prove the non-negativity on $V_{\mu}\cap\ker\alpha_{A_{0}}$ , so we assume that $\alpha_{A_{0}}=0$ . We therefore get from (5·4)

\begin{eqnarray*}U_{00} & = & \left(k-1\right)\alpha_{A_{0}\cup\left\{ 1\right\} },\\U_{0i} & = & k\left(\alpha_{A_{0}\cup\left\{ 1\right\} }-\alpha_{A_{i}}\right)+k^{2}-1,\\U_{ij} & = & 2k^{2}+k-1-k\left(\alpha_{A_{i}}+\alpha_{A_{j}}\right)\!.\end{eqnarray*}

With (5·5) we have

\begin{eqnarray*}U_{00}-w_{00} & = & \left(k-1\right)\left(\alpha_{A_{0}\cup\left\{ 1\right\} }-\frac{k}{2}\right)\!,\\U_{0i}-w_{0i} & = & k\left(\alpha_{A_{0}\cup\left\{ 1\right\} }-\alpha_{A_{i}}\right),\\U_{ij}-w_{ij} & = & k^{2}-k\left(\alpha_{A_{i}}+\alpha_{A_{j}}\right)\!.\end{eqnarray*}

By Lemma 2·8(4) we get the operator norm bounds

\begin{eqnarray*}\left\Vert U_{00}-w_{00}\right\Vert & = & \frac{\left(k-1\right)k}{2},\\\left\Vert U_{0i}-w_{0i}\right\Vert & = & k\left\Vert \left(\alpha_{A_{0}\cup\left\{ 1\right\} }-\frac{k}{2}\right)-\left(\alpha_{A_{i}}-\frac{k}{2}\right)\right\Vert \le k^{2},\\\left\Vert U_{ij}-w_{ij}\right\Vert & = & k\left\Vert \left(\frac{k}{2}-\alpha_{A_{i}}\right)+\left(\frac{k}{2}-\alpha_{A_{j}}\right)\right\Vert \le k^{2}.\end{eqnarray*}

By (5·7) we have that in $\ker\alpha_{A_{0}}\cap V_{\mu}$

\begin{align*}\Gamma_{00ij} & = 2(\Lambda_{00ij}+\Lambda_{0i0j})\\ & = 2w_{00}w_{ij}-2\left(U_{00}-w_{00}\right){\mathrm{\star}}\left(U_{ij}-w_{ij}\right)\\ & \quad + 2w_{0i}w_{0j}-2\left(U_{0i}-w_{0i}\right){\mathrm{\star}}\left(U_{0j}-w_{0j}\right)\!,\end{align*}

so it is enough to show that

\[\left\Vert \left(U_{00}-w_{00}\right){\mathrm{\star}}\left(U_{ij}-w_{ij}\right)+\left(U_{0i}-w_{0i}\right){\mathrm{\star}}\left(U_{0j}-w_{0j}\right)\right\Vert \le w_{00}w_{ij}+w_{0i}w_{0j}.\]

The left-hand side is bounded from above by $({\left(k-1\right)k}/{2})\cdot k^{2}+k^{4}$ . The right-hand side is equal to $({\left(k-1\right)k}/{2})\cdot\left(k^{2}+k-1\right)+\left(k^{2}-1\right)^{2}$ . So our claim holds if

\[\frac{\left(k-1\right)k}{2}\cdot k^{2}+k^{4}\le\frac{\left(k-1\right)k}{2}\cdot\left(k^{2}+k-1\right)+\left(k^{2}-1\right)^{2}\!,\]

which is equivalent to

\[k^{3}-6k^{2}+k+2\ge0.\]

This inequality holds for $k\ge6$ . ForFootnote ⁵ $k=2,3,4,5$ we verified by computer that $\Gamma_{00ij}\ge_{V_{\mu}}0$ – see Appendix B.

Proof. This proof is similar to the proof of Lemma 5·7. We have $\left|E\right|=k+2$ . As before, it is enough to prove the non-negativity of $\Gamma_{0iij}$ on $V_{\mu}\cap\ker\alpha_{A_{0}}$ . In this subspace, $\alpha_{A_{i}\cup\left\{ 1\right\} }=_{V_{\mu}}\alpha_{A_{j}\cup\left\{ 1\right\} }=_{V_{\mu}}\alpha_{A_{i}\cup A_{j}}=_{V_{\mu}}k+1$ and $\alpha_{A_{0}}=_{V_{\mu}}0$ .

We have seen in the proof of Lemma 5·7, that in this situation we have $\left\Vert U_{0i}-w_{0i}\right\Vert \leq k^{2}$ and $\left\Vert U_{ij}-w_{ij}\right\Vert \leq k^{2}$ . Let us estimate $\left\Vert U_{ii}-w_{ii}\right\Vert $ . By (5·4),

\[U_{ii}=k\alpha_{A_{i}\cup\left\{ 1\right\} }-\left(k+1\right)\alpha_{A_{i}}=k\left(k+1\right)-\left(k+1\right)\alpha_{A_{i}},\]

and with (5·5) we have

\[U_{ii}-w_{ii}=\frac{k\left(k+1\right)}{2}-\left(k+1\right)\alpha_{A_{i}}.\]

As $\left\Vert \alpha_{A}-{\left|A\right|}/{2}\right\Vert ={\left|A\right|}/{2}$ by Lemma 2·8(4) we get

\[\left\Vert U_{ii}-w_{ii}\right\Vert =(k+1)\left\Vert \frac{k}{2}-\alpha_{A_{i}}\right\Vert \le\frac{k\left(k+1\right)}{2}.\]

By (5·7) (assuming without loss of generality that $i{\,\lt\,}j$ – this only affects the notation),

\begin{align*}\Gamma_{0iij} & = 2(\Lambda_{0iij}+\Lambda_{0jii})\\ & = 2w_{0i}w_{ij}-2\left(U_{0i}-w_{0i}\right){\mathrm{\star}}\left(U_{ij}-w_{ij}\right)\\ & \quad +\,2w_{0j}w_{ii}-2\left(U_{0j}-w_{0j}\right){\mathrm{\star}}\left(U_{ii}-w_{ii}\right),\end{align*}

so it is enough to show that

(5·10) \begin{equation}\left\Vert \left(U_{0i}-w_{0i}\right){\mathrm{\star}}\left(U_{ij}-w_{ij}\right)+\left(U_{0j}-w_{0j}\right){\mathrm{\star}}\left(U_{ii}-w_{ii}\right)\right\Vert \le w_{0i}w_{ij}+w_{0j}w_{ii}.\end{equation}

The left-hand side is bounded from above by $k^{4}+k^{2}\cdot({k(k+1)}/{2})$ . The right-hand side is equal to $\left(k^{2}-1\right)\cdot\left(k^{2}+k-1\right)+\left(k^{2}-1\right)\cdot({k(k+1)}/{2})$ . So our claim holds if

\[k^{4}+\frac{k^{3}(k+1)}{2}\le\big(k^{2}-1\big)\cdot\big(k^{2}+k-1\big)+\big(k^{2}-1\big)\cdot\frac{k(k+1)}{2},\]

which is equivalent to

\[2k^{3}-5k^{2}-3k+2\ge0.\]

This inequality holds for $k\ge3$ . For $k=2$ we verified by computer that $\Gamma_{0iij}\ge0$ – see Appendix B.

Proof. This proof is similar to the proof of the last two lemmas. As before, we consider only the restriction of $\Gamma_{0ij\ell}$ to $\ker\alpha_{A_{0}}\cap V_{\mu}$ , where $\alpha_{A_{i}\cup\left\{ 1\right\} }=_{V_{\mu}}\alpha_{A_{j}\cup\left\{ 1\right\} }=_{V_{\mu}}\alpha_{A_{i}\cup A_{j}}=_{V_{\mu}}k+1$ and $\alpha_{A_{0}}=_{V_{\mu}}0$ .

By (5·7),

\begin{eqnarray*}\Gamma_{0ij\ell} & = & 2(\Lambda_{0ij\ell}+\Lambda_{0ji\ell}+\Lambda_{0\ell ij})\\ & = & 2w_{0i}w_{j\ell}-2\left(U_{0i}-w_{0i}\right){\mathrm{\star}}\left(U_{j\ell}-w_{j\ell}\right)\\ & & +\,2w_{0j}w_{i\ell}-2\left(U_{0j}-w_{0j}\right){\mathrm{\star}}\left(U_{i\ell}-w_{i\ell}\right)\\ & & +\,2w_{0\ell}w_{ij}-2\left(U_{0\ell}-w_{0\ell}\right){\mathrm{\star}}\left(U_{ij}-w_{ij}\right)\!,\end{eqnarray*}

so it is enough to show that

\[\begin{array}{l}\left\Vert \left(U_{0i}-w_{0i}\right){\mathrm{\star}}\left(U_{j\ell}-w_{j\ell}\right)+\left(U_{0j}-w_{0j}\right){\mathrm{\star}}\left(U_{i\ell}-w_{i\ell}\right)+\left(U_{0\ell}-w_{0\ell}\right){\mathrm{\star}}\left(U_{ij}-w_{ij}\right)\right\Vert \\ \le w_{0i}w_{j\ell}+w_{0j}w_{i\ell}+w_{0\ell}w_{ij}.\end{array}\]

We have seen in the proof of Lemma 5·7, that in this situation we have $\left\Vert U_{0e}-w_{0e}\right\Vert \leq k^{2}$ and $\left\Vert U_{ef}-w_{ef}\right\Vert \leq k^{2}$ for all distinct $e,f\in\{i,j,\ell\}$ . Hence, the left-hand side is bounded from above by $3k^{4}$ . The right-hand side is equal to $3\cdot\left(k^{2}-1\right)\cdot\left(k^{2}+k-1\right)$ . So our claim holds if

\[k^{4}\le\left(k^{2}-1\right)\cdot\left(k^{2}+k-1\right)\!,\]

which is equivalent to

\[k^{3}-2k^{2}-k+1\ge0.\]

This inequality holds for $k\ge3$ . For $k=2$ we verified by computer that in these representations $\Gamma_{0ij\ell}\ge0$ – see Appendix B.

At this point we have established that $\Gamma_{{ij\ell m}}\ge0$ also when $\left|E\right|=k+2$ , namely, for $\Gamma_{00ij}$ , $\Gamma_{0iij}$ , $\Gamma_{iiij}$ , and $\Gamma_{iijj}$ for every $i\ne j$ with $i,j\in\left\{ 1,\ldots,t\right\} $ .

5·3. The case $k+1\le\mu_{1}\le\left|E\right|-2$

Recall that $\left|E\right|\le k+4$ , so if $k+1\le\mu_{1}\le\left|E\right|-2$ then necessarily $\left|E\right|=k+3$ or $\left|E\right|=k+4$ . Namely, the cases we ought to consider are the following three:

1. (1) prove that $\Gamma_{ij\ell m}\ge_{V_{\mu}}0$ when $i,j,\ell,m{\,\gt\,}0$ are distinct and $\mu\vdash k+4$ with $\mu_{1}=k+1$ or $\mu_{1}=k+2$ ;

2. (2) prove that $\Gamma_{iij\ell}\ge_{V_{\mu}}0$ when $i,j,\ell{\,\gt\,}0$ are distinct and $\mu\vdash k+3$ with $\mu_{1}=k+1$ ;

3. (3) prove that $\Gamma_{0ij\ell}\ge_{V_{\mu}}0$ when $i,j,\ell{\,\gt\,}0$ are distinct and $\mu\vdash k+3$ with $\mu_{1}=k+1$ .

Without loss of generality, we assume that $A_{0}=\left\{ 2,\ldots,k\right\} $ and $A_{i}=A_{0}\cup\left\{ k+1\right\} $ , $A_{j}=A_{0}\cup\left\{ k+2\right\} $ , $A_{\ell}=A_{0}\cup\left\{ k+3\right\} $ and $A_{m}=A_{0}\cup\left\{ k+4\right\} $ .

By Young’s rule (2·5), all the representations in the first claimFootnote ⁶ are subrepresentations of the reducible representation $W_{\left(k+1,1,1,1\right)}$ – the action of ${\mathrm{Sym}}_{k+4}$ on ordered triplets of distinct numbers from $\left\{ 1,\ldots,k+4\right\} $ . Likewise, we need to prove that $\Gamma_{iij\ell}\ge0$ and $\Gamma_{0ij\ell}\ge0$ on irreducible representations $V_{\mu}$ of ${\mathrm{Sym}}_{k+3}$ with $\mu_{1}=k+1$ , all of which are subrepresentations of the reducible representation $W_{\left(k+1,1,1\right)}$ – the action of ${\mathrm{Sym}}_{k+3}$ on ordered pairs of distinct numbers from $\left\{ 1,\ldots,k+3\right\} $ .

Our strategy for all three cases is similar, and we illustrate it by the first one – $\Gamma_{ij\ell m}$ . By Lemma 5·2, $V_{k}:=W_{\left(k+1,1,1,1\right)}\cap\ker\alpha_{A_{0}}$ is invariant under $\Gamma_{ij\ell m}$ , and it is enough to prove that $\Gamma_{ij\ell m}\ge0$ in this $V_{k}$ . Since $({1}/{k-1})\alpha_{A_{0}}=\mathrm{id}-({1}/{\left(k-1\right)!})\sum_{\sigma\in\mathrm{Sym}\left(A_{0}\right)}\sigma$ , $V_{k}$ consists of linear combinations of triplets which are invariant under ${\mathrm{Sym}}_{A_{0}}$ . Therefore, for all $k\ge4$ , the following list of vectors forms a linear basis for $V_{k}$ :

1. (i) $v_{x,y,z}\,{\stackrel{\mathrm{def}}{=}}\,\left(x,y,z\right)$ for distinct $x,y,z\in\left\{ 1,k+1,k+2,k+3,k+4\right\} $ ;

2. (ii) ${\displaystyle v_{x,y,*}\,{\stackrel{\mathrm{def}}{=}}\,\sum_{s\in\left\{ 2,\ldots,k\right\} }\left(x,y,s\right)}$ and similarly $v_{x,*,y}$ and $v_{*,x,y}$ for distinct $x,y\in\{1,k+1,k+2,k+3,k+4\}$ ;

3. (iii) ${\displaystyle v_{x,*,*}\,{\stackrel{\mathrm{def}}{=}}\,\sum_{\substack{s,t\in\left\{ 2,\ldots,k\right\} \colon\\s\ne t}}\left(x,s,t\right)}$ and similarly $v_{*,x,*}$ and $v_{*,*,x}$ for $x\in\{1,k+1,k+2,k+3,k+4\}$ ;

4. (iv) ${\displaystyle v_{*,*,*}\,{\stackrel{\mathrm{def}}{=}}\,\sum_{s,t,r\in\left\{ 2,\ldots,k\right\} \colon\;s,t,r\;\mathrm{distinct}}\left(s,t,r\right)}$ .

In particular, the dimension of $V_{k}$ is the same, 136, for every $k\ge4$ . (For $k\le3$ some of these elements vanish. For example, for $k=3$ , the element $V_{*,*,*}=0$ . We check these cases separately and directly by computer — see Appendix B.)

Our next goal is to construct an explicit $136\times136$ matrix giving the action of $\Gamma_{ij\ell m}$ on $V_{k}$ with respect to this given basis. We will show that the entries of this matrix are rational functions of the parameter k, namely, elements in $\mathbb{Q}\left(k\right)$ . As $\Gamma_{ij\ell m}\,|\,_{V_{k}}$ is a (quadratic) polynomial in the operators $\alpha_{B}\,|\,_{V_{k}}$ with $A_{0}\subseteq B\subseteq\{1,\ldots,k+4\}$ , it is enough to describe the $136\times136$ matrix corresponding to each such $\alpha_{B}$ .

Fix a subset B as above. Let $v=v_{x,y,z}$ be a basis element, where $x,y,z\in\{1,k+1,k+2,k+3,k+4,*\}$ . Pick a triplet $\left(a,b,c\right)\in\{1,\dotsc,k+4\}^{3}$ in the support of the sum defining v and define $O_{B}(v)$ as the ${\mathrm{Sym}}_{B}$ -orbit of (a,b,c). Since $A_{0}\subseteq B,$ we have that $O_{B}(v)$ does not depend on the choice of (a, b, c) but only on B and v. Let $T_{B}\left(v\right)$ be the set of all basis elements v ^′ supported on $O_{B}\left(v\right)$ . So $O_{B}\left(v\right)\subseteq\left[k+4\right]^{3}$ and $T_{B}\left(v\right)$ is a subset of the 136 basis elements.

Lemma 5·10. Fix B and $v=v_{x,y,z}$ a basis element as above. Let $n_{*}\left(v\right)$ denote the number of stars among x,y,z and $n_{B}\left(v\right)$ denote the number of x,y,z which are either a star or an element of $B\setminus A_{0}$ . The action of $\alpha_{B}$ on v is given by:

(5·11) \begin{equation}\alpha_{B}\cdot v=\left|B\right|v-\frac{(\left|B\right|-n_{B}(v))!\cdot\left(k-1\right)\cdots\left(k-n_{*}\left(v\right)\right)}{(|B|-1)!}\sum_{v'\in T_{B}\left(v\right)}v'.\end{equation}

Proof. Recall that $J_{B}=\sum_{\sigma\in\mathrm{Sym}(B)}\sigma$ , so $\alpha_{B}=\left|B\right|-{J_{B}}/{\left(\left|B\right|-1\right)!}$ . It is enough to prove that:

(5·12) \begin{equation}\frac{J_{B}}{\left(\left|B\right|-1\right)!}\cdot v=\frac{(\left|B\right|-n_{B}(v))!\cdot\left(k-1\right)\cdots\left(k-n_{*}\left(v\right)\right)}{(\left|B\right|-1)!}\sum_{v'\in T_{B}\left(v\right)}v'.\end{equation}

We have $|O_{B}(v)|=\left|B\right|!/(|B|-n_{B}(v))!$ , since within the triplet defining v, only the $n_{B}(v)$ elements belonging to B can be moved by ${\mathrm{Sym}}_{B}$ , and they all move to distinct places within B. Hence, for every $t\in O_{B}\left(v\right)$ ,

\[\left(\sum_{\sigma\in{\mathrm{Sym}}_{B}}\sigma\right)t=\frac{\left|{\mathrm{Sym}}_{B}\right|}{\left|O_{B}\left(v\right)\right|}\left(\sum_{s\in O_{B}\left(v\right)}s\right)=\frac{\left|B\right|!}{\left|B\right|!/(|B|-n_{B}(v))!}\left(\sum_{s\in O_{B}\left(v\right)}s\right)\!.\]

Summing the above equality over all $\left(k-1\right)\cdots\left(k-n_{*}\left(v\right)\right)$ triplets in the support of the sum defining v, and as $\sum_{s\in O_{B}\left(v\right)}s=\sum_{v'\in T_{B}\left(v\right)}v'$ , we obtain (5·12).

Denote by $M\left(\Gamma_{ij\ell m}\right)$ the matrix of the operator $\Gamma_{ij\ell m}$ in its action on $V_{k}$ , with respect to the above basis.

Proof. By the formulas (5·7), (5·4) and (5·5), $\Gamma_{ij\ell m}$ is a quadratic polynomial in the operators $\alpha_{B}$ for some sets $A_{0}=\{2,\dotsc,k\}\subseteq B\subseteq\{1,\dotsc,k+4\}$ such that $k-1\leq|B|\leq k+1$ , with coefficients in $\mathbb{Z}[k]$ . For each such B, consider the coefficient

\[\frac{\left(|B|-n_{B}(v)\right)!\left(k-1\right)\cdots\left(k-n_{*}\left(v\right)\right)}{\left(|B|-1\right)!}=\frac{|B|\left(k-1\right)\cdots\left(k-n_{*}\left(v\right)\right)}{\left|B\right|\left(|B|-1\right)\cdots\left(|B|-n_{B}\left(v\right)+1\right)}\]

in (5·11). We have $|B|=k-1+|B\backslash A_{0}|$ and $n_{B}(v)\leq n_{*}(v)+|B\backslash A_{0}|,$ hence

\[|B|-n_{B}(v)+1\geq k-1+|B\backslash A_{0}|-\left(n_{*}(v)+|B\backslash A_{0}|\right)+1=k-n_{*}(v).\]

As $|B|\leq k+1$ , all the terms in the denominator, with the possible exception of k (if $\left|B\right|-1=k$ ), are canceled by terms in the numerator. We conclude that the matrix of $\alpha_{B}$ is in $({1}/{k})M_{136}(\mathbb{Z}[k])$ , hence $M(\Gamma_{ij\ell m})\in({1}/{k^{2}})M_{136}(\mathbb{Z}[k])$ .

Using a computer (see Appendix A), we calculated the matrix $A=k^{2}M(\Gamma_{ijlm})$ , and found its characteristic polynomial $p(k,t)\in\mathbb{Z}[k][t]$ . We then calculated $q(k,t):=p(k+3,-t)$ . As it turns out, all the coefficients of q are non-negative. Therefore, for each $k\geq1$ , q(k, t) has no positive real roots, hence for each $k\geq4$ , the characteristic polynomial of $M(\Gamma_{ij\ell m})$ has no negative roots, so the operator $\Gamma_{ij\ell m}$ has no negative eigenvalues. We conclude that $\Gamma_{ij\ell m}\geq_{V_{k}}0$ for $k\ge4$ . The cases $k=2,3$ were verified separately and directly – see Appendix B.

The other two cases – of $\Gamma_{iij\ell}$ and of $\Gamma_{0ij\ell}$ – are proven similarly, with the computerized proof for $k\ge3$ appearing in Appendix A·2, and the computerized proof for $k=2$ appearing in Appendix B.

This concludes the proof of Theorem 1·8.