Part bounds for the Sylow permutation characters of $S_{n}$

Abstract.

We study the Sylow permutation character of the symmetric group at the prime $2$ and prove some new bounds on the number of parts of partitions corresponding to its constituents.

1. Introduction

Let $G$ be a finite group, let $p$ be a prime and let $P$ be a Sylow $p$-subgroup of $G$. The study of the interplay between the representation theory of $G$ and that of its Sylow subgroups has been an active research theme for decades [Nav18]. The structure of the Sylow permutation character $(1_{P})\uparrow^{G}$ encodes a great deal of information about the algebraic structure of the group $G$. For instance, the normality of $P$ in $G$ can be read off the irreducible constituents of $(1_{P})\uparrow^{G}$ [MN12, GLLV22]. Despite this, very little is known about the decomposition of $(1_{P})\uparrow^{G}$ in general. In this article we focus our attention on the case where $G=S_{n}$ is a symmetric group. From now on we let $\Omega_{p}(n)$ be the subset of $\mathrm{Irr}(S_{n})$ consisting of all the irreducible constituents of $(1_{P})\uparrow^{S_{n}}$. Since irreducible characters of $S_{n}$ are naturally labelled by partitions of $n$, it is convenient to think of $\Omega_{p}(n)$ as a subset of $\mathcal{P}(n)$, the set of partitions of $n$.

In [GL18] Giannelli and Law gave a complete description of $\Omega_{p}(n)$ for every odd prime $p$. In subsequent work, again considering only odd primes, they extended this analysis and described the irreducible constituents of $\theta\uparrow^{S_{n}}$, for every $\theta\in\mathrm{Irr}(P)$ [GL25]. It is surprising that, despite the amount of information accumulated for odd primes, very little is known for the prime $p=2$.

The aim of this note is to start the investigation of the set $\Omega_{2}(n)$. In order to present our main result, we briefly introduce some notation. Let $\mathcal{H}(n)$ be the set of hook partitions of $n$. Namely, partitions of the form $(n-x,1^{x})$, for some $0\leq x\leq n-1$. An easy consequence of [Gia17] is the complete description of the set $\Omega_{2}(n)\cap\mathcal{H}(n)$. For this reason, here we focus on non-hook partitions. With this in mind, the question we ask ourselves is the following one: what is the maximal number $\ell\in\mathbb{N}$ such that every non-hook partition with at most $\ell$ parts lies in $\Omega_{2}(n)$? We call $\Delta(n,k)$ the subset of $\mathcal{P}(n)\smallsetminus\mathcal{H}(n)$ consisting of partitions with at most $k$ parts. The main result of this paper is Theorem 4.3 below, where for every $n$ we determine the maximal $\ell$ such that $\Delta(n,\ell)\subseteq\Omega_{2}(n)$. Ignoring a few exceptions for small values of $n$, our main result can be stated as follows.

Theorem A.

Let $n\in\mathbb{N}$ and let us assume that $n\geq 11$. Let $n=2^{a_{1}}+2^{a_{2}}+\cdots+2^{a_{t}}$ be its binary expansion, where $a_{1}>a_{2}>\cdots>a_{t}\geq 0$. Then

$$\Delta(n,k)\subseteq\Omega_{2}(n)\ \text{if and only if}\ k\leq a_{1}+t-1.$$

Theorem A shows that the irreducible character corresponding to any non-hook partition with few parts is an irreducible constituent of the $2$-Sylow permutation character. This result extends the analysis of the restriction to Sylow $2$-subgroups previously performed in [Gia17] and [GV24]. We conclude by mentioning that we also prove a complementary result to Theorem A. More precisely, in Proposition 2.6 we show that the maximum number of parts of a partition in $\Omega_{2}(n)$ is $\lceil\frac{n}{2}\rceil$. This result may be already known to experts, but we were not able to find a proof of it in the literature.

Acknowledgments

The author thanks Eugenio Giannelli for suggesting this research project and for his invaluable help with the manuscript.

2. Background and Notation

In this section we will establish notation and present some preliminary results required for the proofs in this paper.

2.1. Partitions and characters of $S_{n}$

The reader will most likely be familiar with the following definitions, but we will recall them for the sake of clarity. Let $n$ be a positive integer. A partition of $n$ is a sequence $\lambda=(\lambda_{1},\,\ldots,\,\lambda_{t})$ of non-increasing positive integers such that $\sum_{i=1}^{t}\lambda_{i}=n$. We may sometimes write $\lambda_{s}$ with $s>t$, in this case the number is zero. We use $\mathcal{P}(n)$ to denote the set of all partitions of $n$. The Young diagram (or diagram) of a partition $\lambda$ is the set

$$[\lambda]:=\{(i,j)\in\mathbb{N}\times\mathbb{N}\,|\hskip 5.69046pt1\leq i\hskip 5.69046pt\text{and}\hskip 5.69046pt1\leq j\leq\lambda_{i}\}.$$

The elements of $[\lambda]$ are called cells or boxes, and the two indices are respectively the row index and column index. Given a partition $\lambda$, the symbol $\lambda^{\prime}$ will denote the conjugate partition, which is to say the partition whose diagram is obtained by swapping the coordinates of $[\lambda]$. Note that $\lambda^{\prime}_{1}$ coincides with the number of parts of $\lambda$. The $(i,j)$-hook of a partition $\lambda$ is the subset of $[\lambda]$ defined as follows:

$$H_{ij}(\lambda):=\{(s,t)\in[\lambda]\,|\hskip 5.69046pts=i\hskip 5.69046pt\text{and}\hskip 5.69046ptt\geq j,\text{or}\hskip 5.69046ptt=j\hskip 5.69046pt\text{and}\hskip 5.69046pts\geq i\}.$$

A hook partition is a partition $\lambda$ such that $[\lambda]=H_{11}(\lambda)$. The set of all hook partitions of $n$ will be written $\mathcal{H}(n)$. We will also use the following nonstandard definition: we say that $\lambda$ is an $almost-hook$ partition if $[\lambda]\setminus H_{11}(\lambda)$ has just one element. We will use $\mathcal{AH}(n)$ to denote the set of all almost-hook partitions of $n$.
It is a well known fact (e.g. [Jam78]) that the simple $\mathbb{C}S_{n}$-modules up to isomorphism are the Specht modules indexed by partitions of $n$. For $\lambda\in\mathcal{P}(n)$ we will use $S^{\lambda}$ to denote the corresponding Specht module, and $\chi^{\lambda}$ the character corresponding to such module. We will recall the structure of these modules briefly, since it will be used in the next subsection. If $\lambda\in\mathcal{P}(n)$, a $\lambda$-tableau is a bijection $[\lambda]\rightarrow\{1,\ldots,\,n\}$. $S_{n}$ acts naturally on the set of $\lambda$-tableaux. Let $t$ be a $\lambda$-tableau, $R_{t}$ and $C_{t}$ denote the subgroups of $S_{n}$ that stabilize the rows and columns of $t$ respectively. We define an equivalence relation by $t\sim s$ if $s=t\tau$ for some $\tau\in R_{t}$. The equivalence class of $t$ is denoted by $\{t\}$, and this is called a $\lambda$-tabloid. $S_{n}$ acts naturally on the set of $\lambda$-tabloids. We call the permutation module of $S_{n}$ over this set $M^{\lambda}$. The Specht module $S^{\lambda}$ is the submodule of $M^{\lambda}$ spanned by the $\lambda$-polytabloids: the elements of the form $\sum_{\sigma\in C_{t}}sign(\sigma)\{t\}\sigma$ where $t$ is a $\lambda$-tableau.
Another fundamental result in the representation theory of symmetric groups, which will be essential in almost all the proofs in this paper, is the Littlewood-Richardson Rule. To state it we will need some extra notation. Let $n>m$ be positive integers. Let $\lambda\in\mathcal{P}(n)$ and $\mu\in\mathcal{P}(m)$. We say that $\mu$ is a subpartition of $\lambda$ if $[\mu]\subset[\lambda]$. If $\mu$ is a subpartition of $\lambda$ we define the following set:

$$[\lambda\setminus\mu]:=[\lambda]\setminus[\mu].$$

This is known as a skew diagram. A sequence of positive integers $\mathcal{C}=(c_{1},\ldots,c_{n})$ is said to have weight $\lambda$ if

$$\lambda_{k}=|\{j:\hskip 5.69046ptc_{j}=k\}|$$

for all $k\geq 1$. An element $c_{j}$ in the sequence is said to be good if $c_{j}=1$ or

$$|\{i<j:\hskip 5.69046ptc_{i}=c_{j}\}|<|\{i<j:\hskip 5.69046ptc_{i}=c_{j}-1\}|.$$

If every element in the sequence is good we say that the sequence is good.
If $n>m$ are positive integers, we may identify $S_{m}\times S_{n-m}$ with any subgroup of $S_{n}$ obtained as the direct product of the symmetric group acting on a subset of $\{1,\ldots,\,n\}$ of cardinality $m$ and the symmetric group acting on its complement (these are called Young subgroups, and from now on when we write $S_{m}\times S_{n-m}\leq S_{n}$ it will always be a group of this form). The Littlewood-Richardson Rule allows for the construction of the restrictions of characters of $S_{n}$ to $S_{m}\times S_{n-m}$ and inductions from these subgroups to $S_{n}$.

Theorem 2.1 (Littlewood-Richardson Rule).

Let $n>m$ be positive integers. Let $\mu\in\mathcal{P}(m)$ and $\nu\in\mathcal{P}(n-m)$. Consider $\chi^{\mu}\times\chi^{\nu}\in\mathrm{Irr}(S_{m}\times S_{n-m})$. Then we have:

$$(\chi^{\mu}\times\chi^{\nu})\uparrow^{S_{n}}=\sum_{\lambda\in\mathcal{P}(n)}c^{\lambda}_{\mu\nu}\chi^{\lambda}$$

where $c^{\lambda}_{\mu\nu}$ is the number of ways of filling $[\lambda\setminus\mu]$ with positive numbers such that:
(i) the sequence obtained reading the numbers from right to left, top to bottom is a good sequence of weight $\nu$;
(ii) the numbers are strictly increasing along the columns from top to bottom;
(iii) the numbers are weakly increasing along the rows from left to right.

For a proof see for example [Jam78, The Littlewood-Richardson rule]. We refer to a filling of $[\lambda\setminus\mu]$ of the type above as a Littlewood-Richardson filling of $[\lambda\setminus\mu]$ of weight $\nu$. The above result shows that to prove that $[(\chi^{\mu}\times\chi^{\nu})\uparrow^{S_{n}},\,\chi^{\lambda}]\neq 0$, it suffices to find a Littlewood-Richardson (we will often abbreviate L-R) filling of $[\lambda\setminus\mu]$ of weight $\nu$. This will be used many times in this paper. Let us also highlight two simple but useful facts: by swapping $m$ and $n-m$ we see that if $c^{\lambda}_{\mu\nu}\neq 0$ then $\nu$ is also a subpartition of $\lambda$; furthermore, in this case we have that $\lambda_{1}\leq\mu_{1}+\nu_{1}$ and $\lambda^{\prime}_{1}\leq\mu^{\prime}_{1}+\nu^{\prime}_{1}$. And finally, let us state a simple to prove combinatorial remark, that will be used repeatedly in the sections below.

Remark 2.2.

Let $n>m$ be positive integers. Let $\lambda\in\mathcal{P}(n)$ and $\mu\in\mathcal{P}(m)$, such that $\mu$ is a subpartition of $\lambda$; then the filling of $[\lambda\setminus\mu]$ given by the top to bottom numbering of the boxes of each column is a Littlewood-Richardson filling.

In the following figure we give an example of this filling for the sake of clarity.

    $$\times \times \times \times \times 1 1 \times \times \times \times \times 2 \times \times \times 1 1 3 1 1 2$$                                                                 

Here $\lambda=(7,\,6^{2},\,2,\,1)$, $\mu=(5^{2},\,3)$ and the weight of the filling is $(6,\,2,\,1)$.

2.2. The Sylow Permutation Character

Let $n$ be a positive integer, we define the following sets:

$$\Omega_{p}(n):=\{\lambda\in\mathcal{P}(n)\,|\hskip 5.69046pt[\chi^{\lambda},\,(1_{P_{n}})\uparrow^{S_{n}}]\neq 0\}$$

where $P_{n}$ is a Sylow $p$-subgroup of $S_{n}$. Clearly $\Omega_{p}(n)$ does not depend on the choice of the Sylow $p$-subgroup. The character $(1_{P_{n}})\uparrow^{S_{n}}$ is called a Sylow permutation character, and its significance and the reasons for trying to find its decomposition have been touched on in the introduction. As has been said there, the set $\Omega_{p}(n)$ has been determined in its entirety in [GL18, Theorem A], when $p$ is odd. In this paper we focus instead on the much more irregular $\Omega_{2}(n)$, which still elude a full description.
We will now fix a particular Sylow $2$-subgroup of $S_{n}$ for each $n$. This will allow us to prove two interesting facts about $\Omega_{2}(n)$ before even reducing the problem using Clifford Theory. Both these results may already be known to experts, but we were not able to find proofs of them in the literature. For any $k\geq 0$ we define $P_{2^{k}}$ as the Sylow $2$-subgroup of $S_{2^{k}}$ generated by the elements: $(1,2),(1,3)(2,4),\ldots,(1,2^{k-1}+1)\cdots(2^{k-1},2^{k})$. Let $n>0$ be an integer, and $n=2^{a_{1}}+2^{a_{2}}+\cdots+2^{a_{t}}$ its binary expansion, with $a_{1}>\cdots>a_{t}$. We define $P_{n}$ as the Sylow $2$-subgroup of $S_{n}$ obtained as the product of the natural embeddings of the subgroups $P_{2^{a_{k}}}$ in $S_{\{m+1,\ldots,\,m+2^{a_{k}}\}}$ (the symmetric group acting on the set $\{m+1,\ldots,\,m+2^{a_{k}}\}$) where $m=2^{a_{1}}+\cdots+2^{a_{k-1}}$. With this notation fixed, we may observe that $(2k+1,2k+2)\in P_{n}$ for all $k\geq 0$ such that $2k+2\leq n$, and that $P_{n}$ stabilizes the set $\{\{2k+1,\,2k+2\}:\hskip 5.69046pt2\leq 2k+2\leq n\}$.
We will use the structure of the Specht modules to prove the following two results, so we will need to translate the character theoretic condition for $\lambda\in\Omega_{2}(n)$ into one that can be visualized in $S^{\lambda}$. This is done in the following lemma.

Lemma 2.3.

Let $n>0$ be an integer, and $\lambda\in\mathcal{P}(n)$. Then $\lambda\in\Omega_{2}(n)$ if and only if there exists a $\lambda$-tableau $t$ such that $\sum_{\pi\in P_{n}}e_{t}\pi\neq 0$.

Proof.

The condition $[\,\chi^{\lambda}\downarrow_{P_{n}},\,1_{P_{n}}]\,\neq 0$ is equivalent to

$$\exists v\in S^{\lambda}\setminus\{0\}\hskip 5.69046pt\forall\pi\in P_{n}\hskip 5.69046ptv\pi=v.$$

Since $\mathrm{char}(\mathbb{C})=0$, this in turn is equivalent to

$$\exists w\in S^{\lambda}\hskip 5.69046pt\sum_{\pi\in P_{n}}w\pi\neq 0.$$

Since $S^{\lambda}$ is spanned by the $\lambda$-polytabloids this last condition is equivalent to asking that there exist a $\lambda$-tableau $t$ such that $\sum_{\pi\in P_{n}}e_{t}\pi\neq 0$. ∎

If all the parts of the partition are even, then it is easy to find such a tableau. This is the first result, and it will be used in the proofs leading to the main theorem.

Proposition 2.4.

Let $n>0$ be an integer and $\lambda\in\mathcal{P}(2n)$ a partition whose parts are all even, then $\lambda\in\Omega_{2}(2n)$.

Proof.

We will prove that the $\lambda$-tableau obtained by numbering the cells of $[\lambda]$ from left to right, top to bottom satisfies the condition in Lemma 2.3. Let $t$ be this $\lambda$-tableau. We have

$$\sum_{\pi\in P_{n}}e_{t}\pi=\sum_{\pi\in P_{n}}\sum_{\sigma\in C_{t}}sign(\sigma)\{t\}\sigma\pi.$$

We will show that the coefficient of $\{t\}$ is positive. This coefficient is $\sum_{\pi,\sigma}sign(\sigma)$, where the sum is over all $\pi\in P_{n}$ and $\sigma\in C_{t}$ such that $\{t\}\sigma\pi=\{t\}$, or equivalently $\{t\}\sigma=\{t\}\pi^{-1}$. If $\sigma$ and $\pi$ satisfy this condition, then $sign(\sigma)=1$. This is because $P_{n}$ stabilizes the set $\{\{2k+1,\,2k+2\}:\hskip 5.69046pt0\leq k\leq n-1\}$, so for all such $k$, if $2k+1$ is in a certain row of $\{t\}\pi^{-1}$ then $2k+2$ is in that same row (because this condition is true for $\{t\}$). Any $\sigma\in C_{t}$ is the product of disjoint permutations acting on the individual columns. Since $\{t\}\sigma=\{t\}\pi^{-1}$, the previous condition tells us that the permutation acting on the column $2j+2$ has the same cyclic type as the one acting on the column $2j+1$, since each couple of adjacent elements in these columns of $\{t\}$ is of the type $\{2k+1,\,2k+2\}$. This means that $sign(\sigma)=1$. Since $1\in P_{n}\cap C_{t}$ the coefficient of $\{t\}$ is at least one. ∎

The next result we will prove is the result alluded to in the introduction as complementary to the main theorem. In this case we want to prove that certain partitions are not in $\Omega_{2}(n)$. This can be achieved with the following lemma.

Lemma 2.5.

Let $n>0$ be an integer. If $\lambda\in\mathcal{P}(n)$ is such that $(C_{t}\cap P_{n})\setminus A_{n}\neq\emptyset$ for all $\lambda$-tableaux $t$, then $\lambda\notin\Omega_{2}(n)$.

Proof.

By Lemma 2.3, it is sufficient to prove that $\sum_{\pi\in P_{n}}e_{t}\pi=0$ for all $\lambda$-tableaux $t$. Let $t$ be a $\lambda$-tableau, and let $\tau\in C_{t}\cap P_{n}$ such that $sign(\tau)=-1$. Then we have:

$$\sum_{\pi\in P_{n}}e_{t}\pi=\sum_{\pi\in P_{n}}\sum_{\sigma\in C_{t}}sign(\sigma)\{t\}\sigma\pi=\sum_{\pi\in P_{n}}\sum_{\sigma\in C_{t}}sign(\sigma)\{t\}\sigma(\tau\pi)=$$

$$=\sum_{\pi\in P_{n}}\sum_{\sigma\in C_{t}}sign(\sigma)\{t\}(\sigma\tau)\pi=-\sum_{\pi\in P_{n}}\sum_{\sigma\in C_{t}}sign(\sigma)\{t\}\sigma\pi=-\sum_{\pi\in P_{n}}e_{t}\pi.$$

∎

Proposition 2.6.

Let $n>0$ be an integer. If $\lambda\in\Omega_{2}(n)$ then $\lambda$ has at most $\lceil\frac{n}{2}\rceil$ parts.

Proof.

Let $\lambda\in\Omega_{2}(n)$. We know that $(2k+1,2k+2)\in P_{n}$ for all $k$ such that $2\leq 2k+2\leq n$. By Lemma 2.5, there must be a $\lambda$-tableau $t$ such that none of these $2$-cycles lies in $C_{t}$. In particular, if either of the elements $\{2k+1,2k+2\}$ lies in the first column of $t$, then the other must be in another. This means that the first column of $[\lambda]$ can have at most $\lceil\frac{n}{2}\rceil$ boxes. ∎

This is in fact an exact bound, since by Proposition 2.4 we know that $(2^{n})=(2,\ldots,\,2)\in\Omega_{2}(2n)$, and Proposition 2.8 will also yield $(2^{n},\,1)\in\Omega_{2}(2n+1)$.
We will now prove two useful conditions for constructing $\Omega_{2}(n)$ inductively. These are essentially a slight modification to the arguments used in [GL18] to reduce the odd prime case. The first proposition allows us to construct some of the partitions in $\Omega_{2}(2^{k+1})$ from partitions in $\Omega_{2}(2^{k})$.

Proposition 2.7.

Let $k>0$ be an integer. Let $\mu,\nu\in\Omega_{2}(2^{k})$ such that $\mu\neq\nu$. If $\lambda\in\mathcal{P}(2^{k+1})$ is such that $[\chi^{\lambda},\,(\chi^{\mu}\times\chi^{\nu})\uparrow^{S_{2^{k+1}}}]\neq 0$, then $\lambda\in\Omega_{2}(2^{k+1})$.

Proof.

Suppose $\lambda\in\mathcal{P}(2^{k+1})$ and $\mu,\nu\in\Omega_{2}(2^{k})$ are as stated above. We have a natural embedding $S_{2^{k}}\times S_{2^{k}}\trianglelefteq S_{2^{k}}\wr C_{2}\leq S_{2^{k+1}}$ (where the first is a Young subgroup and $C_{2}$ acts on it by swapping the elements the copies of $S_{2^{k}}$ act on). Then $P_{2^{k}}\times P_{2^{k}}\in\mathrm{Syl}_{2}(S_{2^{k}}\times S_{2^{k}})$ and $P_{2^{k}}\wr C_{2}\in\mathrm{Syl}_{2}(S_{2^{k+1}})$. Since $S_{2^{k}}\times S_{2^{k}}\trianglelefteq S_{2^{k}}\wr C_{2}$ we can apply Clifford Theory to $\chi^{\mu}\times\chi^{\nu}$. The inertial subgroup of this character is $S_{2^{k}}\times S_{2^{k}}$ (since $\mu\neq\nu$), so $(\chi^{\mu}\times\chi^{\nu})\uparrow^{S_{2^{k}}\wr C_{2}}$ is irreducible. This means that $(\chi^{\mu}\times\chi^{\nu})\uparrow^{S_{2^{k}}\wr C_{2}}$ is an irreducible constituent of $\chi^{\lambda}\downarrow_{S_{2^{k}}\wr C_{2}}$. Since $(S_{2^{k}}\times S_{2^{k}})\cap(P_{2^{k}}\wr C_{2})=P_{2^{k}}\times P_{2^{k}}$ and $(S_{2^{k}}\times S_{2^{k}})\cdot(P_{2^{k}}\wr C_{2})=S_{2^{k}}\wr C_{2}$, we have that:

$$[(\chi^{\mu}\times\chi^{\nu})\uparrow^{S_{2^{k}}\wr C_{2}}\downarrow_{P_{2^{k}}\wr C_{2}},\,1_{P_{2^{k}}\wr C_{2}}]=[(\chi^{\mu}\times\chi^{\nu})\downarrow_{P_{2^{k}}\times P_{2^{k}}}\uparrow^{P_{2^{k}}\wr C_{2}},\,1_{P_{2^{k}}\wr C_{2}}]=$$

$$=[(\chi^{\mu}\times\chi^{\nu})\downarrow_{P_{2^{k}}\times P_{2^{k}}},\,1_{P_{2^{k}}\times P_{2^{k}}}]\neq 0$$

since $\mu,\nu\in\Omega_{2}(2^{k})$. ∎

The second proposition allows us to construct the elements of $\Omega_{2}(n)$ starting from $\Omega_{2}(2^{k})$.

Proposition 2.8.

Let $n>0$ be an integer. Write $n=\sum_{i=1}^{t}2^{a_{i}}$ with $a_{i}$ distinct (here we do not require any specific ordering). Let $1\leq j<t$ and $m=\sum_{i=1}^{j}2^{a_{i}}$. Let $\lambda\in\mathcal{P}(n)$. Then $\lambda\in\Omega_{2}(n)$ if and only if there exist $\mu\in\Omega_{2}(m)$ and $\nu\in\Omega_{2}(n-m)$ such that $[\chi^{\lambda},\,(\chi^{\mu}\times\chi^{\nu})\uparrow^{S_{n}}]\neq 0$.

Proof.

Consider the following subgroups $P_{m}\times P_{n-m}\leq S_{m}\times S_{n-m}\leq S_{n}$. $P_{m}\times P_{n-m}$ is a Sylow $2$-subgroup of $S_{n}$. This means that $[\chi^{\lambda}\downarrow_{P_{m}\times P_{n-m}},\,1_{P_{m}\times P_{n-m}}]\neq 0$ if and only if $\chi^{\lambda}\downarrow_{S_{m}\times S_{n-m}}$ has an irreducible constituent whose restriction to $P_{m}\times P_{n-m}$ satisfies the same condition. The irreducible characters of $S_{m}\times S_{n-m}$ satisfying this condition are exactly those of the form $\chi^{\mu}\times\chi^{\nu}$ where $\mu\in\Omega_{2}(m)$ and $\nu\in\Omega_{2}(n-m)$. ∎

Let’s use this proposition to determine the sets $\Omega_{2}(n)\cap\mathcal{H}(n)$ and $\Omega_{2}(n)\cap\mathcal{AH}(n)$. In both cases we choose to parametrize these sets using the number of parts of the partitions.

Lemma 2.9.

Let $n$ be a positive integer and $n=2^{a_{1}}+2^{a_{2}}+\cdots+2^{a_{t}}$ its binary expansion. We have that $(n-(l-1),\,1^{l-1})\in\Omega_{2}(n)\cap\mathcal{H}(n)$ if and only if $l\leq t$.

Proof.

We prove the result by induction on the number of elements in the binary expansion of $n$. If $n$ is a power of $2$ the result follows from [Gia17, Theorem 1.1]. Let $n=2^{a_{1}}+2^{a_{2}}+\cdots+2^{a_{t}}$ with $t\geq 2$. Let $N=2^{a_{1}}+\cdots+2^{a_{t-1}}$. By Proposition 2.8 and the Littlewood-Richardson Rule, $\lambda\in\Omega_{2}(n)$ if and only if there exist $\mu\in\Omega_{2}(N)$ and $\nu\in\Omega_{2}(2^{a_{t}})$ that are both subpartitions of $\lambda$ and such that $[\lambda\setminus\mu]$ has a L-R filling of weight $\nu$. If $\lambda\in\mathcal{H}(n)$ we must have $\mu\in\mathcal{H}(N)$ and $\nu\in\mathcal{H}(2^{a_{t}})$. Therefore, $\mu=(N-(l_{1}-1),\,1^{l_{1}-1})$ with $l_{1}\leq t-1$ and $\nu$ is the trivial partition. This implies that $\lambda$ has at most $t$ parts. Vice versa, if $\lambda=(n-(l-1),\,1^{l-1})$ with $2\leq l\leq t$ (the trivial partition is clearly in $\Omega_{2}(n)$), then we consider $\mu=(N-(l-2),\,1^{l-2})$ and the L-R filling consisting of filling each box with the number $1$. ∎

Let us observe here that, in the case $n=2^{k}$ we have $\Omega_{2}(2^{k})\cap\mathcal{H}(2^{k})=\{(2^{k})\}$. This fact will be used in subsequent proofs without being explicitly recalled.

Lemma 2.10.

Let $n\geq 4$ be a positive integer and $n=2^{a_{1}}+2^{a_{2}}+\cdots+2^{a_{t}}$ its binary expansion, with $a_{1}>\cdots>a_{t}$. We have that $(n-l,\,2,\,1^{l-2})\in\Omega_{2}(n)\cap\mathcal{AH}(n)$ if and only if $l\leq a_{1}+t-1$.

Proof.

We proceed by induction, as in the previous lemma. The base case is given by [GuL25, Theorem 1.3]. Let $n=2^{a_{1}}+2^{a_{2}}+\cdots+2^{a_{t}}$ with $t\geq 2$. Let $N=2^{a_{1}}+\cdots+2^{a_{t-1}}$. By Proposition 2.8 and the L-R Rule, $\lambda\in\Omega_{2}(n)$ if and only if there exist $\mu\in\Omega_{2}(N)$ and $\nu\in\Omega_{2}(2^{a_{t}})$ that are both subpartitions of $\lambda$ and such that $[\lambda\setminus\mu]$ has a Littlewood-Richardson filling of weight $\nu$. If $\lambda\in\mathcal{AH}(n)$ we must have $\mu\in\mathcal{AH}(N)\cup\mathcal{H}(N)$ and $\nu\in\mathcal{AH}(2^{a_{t}})\cup\mathcal{H}(2^{a_{t}})$. Also, at least one of the two must be a hook partition: if $\mu\in\mathcal{AH}(N)$, then any L-R filling of $[\lambda\setminus\mu]$ has weight a hook partition. If $\nu\in\mathcal{H}(2^{a_{t}})\cap\Omega_{2}(2^{a_{t}})$, then it must be the trivial partition. At the same time, $\mu$ has at most $a_{1}+t-2$ parts, so $\lambda$ has at most $a_{1}+t-1$. If $\nu\in\mathcal{AH}(2^{a_{t}})\cap\Omega_{2}(2^{a_{t}})$ (which implies $a_{t}\geq 2$, otherwise there are no almost-hook partitions), then $\nu$ has at most $a_{t}$ parts. In this case $\mu\in\mathcal{H}(N)\cap\Omega_{2}(n)$, so $\mu$ has at most $t-1$ parts. Therefore, $\lambda$ has at most $a_{t}+t-1\leq a_{1}+t-1$ parts. Vice versa, if $\lambda=(n-l,\,2,\,1^{l-2})$ with $3\leq l\leq a_{1}+t-1$, then take $\mu=(N-(l-1),\,2,\,1^{l-3})$ and the Littlewood-Richardson filling of $[\lambda\setminus\mu]$ obtained by filling each box with $1$. The partition $(n-2,\,2)$ is in $\Omega_{2}(n)$, by Proposition 2.4 and the L-R Rule when $n$ is odd. ∎

This second result shows the maximality of the bound that we will prove in Theorem 4.3.

3. The power of 2 case

To simplify notation we will define the following sets of partitions.

Definition 3.1.

Let $n$ and $k$ be positive integers. We let $\Delta(n,k)$ be the subset of $\mathcal{P}(n)\setminus\mathcal{H}(n)$ of partitions with at most $k$ parts.

We will proceed in the natural way suggested by the structure of the Sylow $2$-subgroups of $S_{n}$ and by Propositions 2.7 and 2.8: in this section we will prove the desired result for powers of $2$, and then generalize to all positive integers in the next. For the first step we will use the two following lemmas.

Lemma 3.2.

Let $n\geq 4$ be an integer; then

$$\Delta(2^{n},4)\subseteq\Omega_{2}(2^{n}).$$

Proof.

We prove this lemma by induction. The base case $n=4$ has been checked using [GAP]. Let $n>4$ and $\lambda\in\Delta(2^{n},4)$. We will prove that $\lambda\in\Omega_{2}(2^{n})$ by using Proposition 2.7 and the Littlewood-Richardson Rule: it is sufficient to find a subpartition $\mu\in\Delta(2^{n-1},4)$ of $\lambda$ and a L-R filling of $[\lambda\setminus\mu]$ of weight $\nu\in\Delta(2^{n-1},4)\cup\{(2^{n-1})\}$, such that $\mu\neq\nu$.
Consider the following algorithm: mark the first $2^{n-1}$ boxes of $[\lambda]$ going from top to bottom, from left to right. The marked boxes form the Young diagram of a subpartition $\mu\in\mathcal{P}(2^{n-1})$ of $\lambda$. Furthermore, since $\lambda\notin\mathcal{H}(2^{n})$, we have that $\mu\notin\mathcal{H}(2^{n-1})$ (box $(2,\,2)$ is necessarily marked); therefore $\mu\in\Delta(2^{n-1},4)$, as desired. We then fill $[\lambda\setminus\mu]$ with the L-R filling described in Remark 2.2 and call it’s weight $\nu\in\mathcal{P}(2^{n-1})$. If $\nu\in\Delta(2^{n-1},4)\cup\{(2^{n-1})\}$ and $\mu\neq\nu$, then we have obtained the desired result.
Let’s suppose that $\mu=\nu$. This implies that $\nu^{\prime}_{1}=\mu^{\prime}_{1}=\lambda^{\prime}_{1}$, which means that all columns of $[\mu]$, except possibly the last, must have $\lambda^{\prime}_{1}$ boxes. If $\lambda^{\prime}_{1}=1,\,2,\,4$ then, since $\lambda^{\prime}_{1}$ divides $2^{n-1}$ and $\mu=\nu$, we have that:

$$\lambda\in\{(2^{n}),\,(2^{n-1},\,2^{n-1}),\,(2^{n-2},\,2^{n-2},\,2^{n-2},\,2^{n-2})\}\subseteq\Omega_{2}(2^{n})$$

(by Proposition 2.4). Suppose $\lambda^{\prime}_{1}=3$; if the last column of $[\mu]$ is made of two cells, then $[\nu]$ has a column with just one cell; if the last column of $[\mu]$ has one cell, then $[\nu]$ has a column with two cells. This means that if $\lambda^{\prime}_{1}=3$ then $\mu\neq\nu$.
Suppose $\nu$ is a non-trivial hook partition. For this to occur, $[\lambda\setminus\mu]$ must have a single column with more than one box. Every column of $[\lambda\setminus\mu]$ from the second onward contains all the corresponding boxes in the respective column of $[\lambda]$, due to how the algorithm is defined. For this reason, the column of $[\lambda\setminus\mu]$ with more than one box must be the first or the second.
If the column is the first, we modify the output of the algorithm by marking the last unmarked box in this column, and unmarking the last box of the previous one. We maintain the same filling for all previously unmarked boxes, and input the number $2$ in the newly unmarked one. This is a L-R filling. This gives us two new partitions $\mu^{0}$ and $\nu^{0}$. Now $[\mu^{0}]$ has at least $5$ columns of which all but the last two have at least $2$ boxes. Meanwhile, $[\nu^{0}]$ has exactly two columns with more than one box. This means that both partitions are non hook partitions, and they are distinct.
If instead the column of $[\lambda\setminus\mu]$ is the second one, then we just replace the $1$ in the first column with a $2$, and conclude as before. ∎

The next lemma will allow us to increase the number of parts as we increase $n$.

Lemma 3.3.

Let $n\geq k\geq 4$ be integers such that $\Delta(2^{n},k)\subseteq\Omega_{2}(2^{n})$ and $\Delta(2^{n+1},k)\subseteq\Omega_{2}(2^{n+1})$; then we have that

$$\Delta(2^{n+1},k+1)\subseteq\Omega_{2}(2^{n+1}).$$

Proof.

Suppose that $n$ and $k$ satisfy the above conditions. Let $\lambda\in\Delta(2^{n+1},k+1)\setminus\Delta(2^{n+1},k)$. We will prove that $\lambda\in\Omega_{2}(2^{n+1})$, as in Lemma 3.2, by using Proposition 2.7 and the Littlewood-Richardson Rule. We will construct two partitions $\mu,\nu\in\Delta(2^{n},k)\cup\{(2^{n})\}\subseteq\Omega_{2}(2^{n})$ such that $\mu\neq\nu$ and there is a L-R filling of $[\lambda\setminus\mu]$ of weight $\nu$. Consider the following algorithm on $[\lambda]$: mark the first $k$ boxes of the first column, the first two of the second, and then continue marking from left to right, top to bottom until the marked cells form the Young diagram of a partition $\mu\in\Delta(2^{n},k)$. Note that $\mu$ cannot have $k+1$ parts, because this would require marking more than $2^{n}$ boxes (we will omit similar observations in other subsequent proofs). Then fill the boxes of $[\lambda\setminus\mu]$ as in Remark 2.2 and let $\nu\in\mathcal{P}(2^{n})$ be its weight.
Firstly, let us prove that $\nu$ has at most $k$ parts. To do this, we will prove this slightly stronger fact: in applying the algorithm, we mark at least one cell in every column of $[\lambda]$ with at least $k$ cells. Suppose that $\lambda$ is such that this doesn’t happen. Let $t$ be the index of the first untouched column (which must have at least $k$ elements). Since $k+2\leq n+2<2^{n}$, $t$ must be at least $4$. The number of marked boxes is $k+2+t-3=2^{n}$. The number of unmarked boxes in the first $t$ columns is at least $1+k-2+(k-1)(t-3)+k$, and it must not exceed $2^{n}$ (the total number of unmarked boxes). This gives the following inequality:

$$1+k-2+(k-1)(t-3)+k\leq k+2+t-3$$

$$3\leq(k-2)(t-3)+k-3\leq 0.$$

The reason why we proved this stronger result is that this can also be used to prove that $\mu\neq\nu$. Suppose that $\mu$ and $\nu$ have the same number of parts. By the previous observation there must be at least one column of $[\lambda]$ with $k+1$ boxes of which only one is marked. Due to how the algorithm is defined, this column can’t be the first nor the second. Therefore the second column of $[\lambda]$ is made of $k+1$ boxes, of which only two are marked (the third can’t be marked, otherwise all boxes in the second row would also be marked). This means that $[\mu]$ has one column with $k$ boxes, and all others with two or less. Meanwhile, $\nu$ has a column with $(k+1)-2=k-1\geq 3$ boxes, and therefore $\mu\neq\nu$. This leaves the case in which $\nu$ is a non-trivial hook partition.
Suppose that $\nu$ is a non-trivial hook partition. By the previous observation, $\nu$ cannot have $k$ parts. This means that if we modify the partitions $\mu$ and $\nu$ without changing the number of their parts, then they will still be distinct. Just as in the proof of Lemma 3.2, if $\nu$ is a hook partition, then $[\lambda\setminus\mu]$ has only one column with more than one box. If the other boxes of $[\lambda\setminus\mu]$ are not all in the same row, it suffices to change the content of the last box of the last of these rows (excluding all elements of the column with more than one box) from a $1$ to a $2$. This changes $\nu$ into a non hook partition, without modifiying the number of parts.
The last remaining case is that in which all the cells of $[\lambda\setminus\mu]$ lie in the union of a column and a row. This is impossible. If this were to happen, this would mean that the row considered is the $(k+1)$-th, since the last box of the first column of $[\lambda]$ is left unmarked. Therefore, the number of cells in $[\lambda\setminus\mu]$ is at most $\lambda_{k+1}+k-1$, while the number of marked cells is at least $k(\lambda_{k+1}-1)$; this results in the inequality $\lambda_{k+1}+k-1\geq k(\lambda_{k+1}-1)$, which isn’t satisfiable for $k\geq 4$ and $\lambda_{k+1}\geq 2^{n}-(k-1)\geq 13$. ∎

We will now give an example of the algorithm described in Lemma 3.3.

Example 3.4.

Let $\lambda=(25,\,2^{3},\,1)\in\Delta(32,5)\setminus\Delta(32,4)$. The algorithm gives us the following figure

    $$\times \times \times \times \times \times \times \times \times \times \times \times 1 1 1 1 1 1 1 1 1 1 1 1 1 \times \times \times 1 \times 2 1$$                                                                                     

The output is $\mu=(12,\,2,\,1^{2})$ e $\nu=(15,\,1)$. We have $\nu\in\mathcal{H}(16)\setminus\{(16)\}$ so we must apply the modification described in Lemma 3.3.

    $$\times \times \times \times \times \times \times \times \times \times \times \times 1 1 1 1 1 1 1 1 1 1 1 1 1 \times \times \times 1 \times 2 2$$                                                                                     

Now $\mu=(12,\,2,\,1^{2})$ e $\nu=(14,\,2)$.

The proof of the desired bound in the case of powers of $2$ is now essentially complete.

Proposition 3.5.

Let $n\geq 4$ be an integer. Then

$$\Delta(2^{n},n)\subseteq\Omega_{2}(2^{n}).$$

Proof.

We will prove by induction on $n\geq 4$ that for all $m\geq n$, we have $\Delta(2^{m},n)\subseteq\Omega_{2}(2^{m})$, which is equivalent to the statement above. The base case is given by Lemma 3.2. Let $n>4$ such that for all $N\geq n-1$, we have $\Delta(2^{N},n-1)\subseteq\Omega_{2}(2^{N})$. Let $m\geq n$, then $m,\,m-1\geq n-1\geq 4$, so $\Delta(2^{m-1},n-1)\subseteq\Omega_{2}(2^{m-1})$ and $\Delta(2^{m},n-1)\subseteq\Omega_{2}(2^{m})$. By Lemma 3.3 we have $\Delta(2^{m},n)\subseteq\Omega_{2}(2^{m})$. ∎

To prove the corresponding result for all positive integers we will require a slightly stronger bound for powers of $2$, obtained by excluding almost-hook partitions. This we present as the following proposition.

Proposition 3.6.

If $n\geq 4$ is an integer, then

$$\Delta(2^{n},2n-3)\setminus\mathcal{AH}(2^{n})\subseteq\Omega_{2}(2^{n}).$$

Proof.

We prove this result by induction on $n\geq 4$. The base case has been checked with [GAP]. Let $n>4$, such that the statement is true for $n-1$. Let $\lambda\in\Delta(2^{n},2n-3)\setminus(\Delta(2^{n},n)\cup\mathcal{AH}(2^{n}))$. Let $1\leq k\leq n-3$ be the integer such that $n+k$ is the number of parts of $\lambda$. Just as in Lemma 3.3, we will provide an algorithm that gives two partitions $\mu,\nu\in\Omega_{2}(2^{n-1})$, such that $\mu\neq\nu$ and there is a L-R filling of $[\lambda\setminus\mu]$ of weight $\nu$. The algorithm is the following: mark the first $n-1$ cells in the first column of $[\lambda]$, then the first $\mathrm{max}\{2,\,\lambda_{2}^{\prime}-(n-2)\}$ in the second, then the first $\mathrm{max}\{1,\,\lambda_{i}^{\prime}-(n-1)\}$ in the $i$-th column (starting from $i=3$), until $2^{n-1}$ cells have been marked or the last column has been reached. If the number of marked cells is less than $2^{n-1}$, we reach that number by marking boxes from left to right, top to bottom (we will refer to this phase as the filling phase). As before, we call the partition corresponding to the obtained diagram $\mu$, while $\nu$ is the partition obtained as the weight of the usual filling of $[\lambda\setminus\mu]$ (Remark 2.2). Clearly $\mu\in\Delta(2^{n-1},n-1)$.
Firstly, we will prove that $\nu$ has at most $n-1$ parts. To do this we will prove a stronger fact which will be used later: the algorithm can’t terminate before marking all the required cells in each of the columns with at least $n-1$ boxes, plus one more. If the algorithm were to terminate by marking $\mathrm{max}\{1,\,\lambda_{i}^{\prime}-(n-1)\}$ or less boxes in a column with $n-1$ boxes or more, this would mean that, since each column has at most $2n-3$ boxes, the number of marked cells in each column is at most $n-1$. Let $l$ be the number of columns of $[\lambda]$ with at least $n-1$ cells. The number of marked cells must be $2^{n-1}$, therefore we must have:

$$l\geq\frac{2^{n-1}}{n-1}.$$

Note that, since the filling phase isn’t necessary in this case, in each column with at least $n-1$ elements from the third onward the number of marked cells is strictly smaller than the number of unmarked cells. Let’s call the number of marked cells in these columns $t$: the number of unmarked cells in these columns is at least $t+l-2$. Let $m$ be the number of marked cells in the first $l$ columns and $u$ the number of unmarked cells in these same columns:

$$(n-1)+(k+2)+t\geq m=2^{n-1}\geq u\geq(k+1)+(n-3)+t+l-2$$

$$5\geq l\geq\frac{2^{n-1}}{n-1}.$$

This is possible only when $n=5$. If $n=5$, there are only five partitions of $16$ whose diagrams have at most $4$ rows and $5$ columns: the conjugate partitions of $(4^{4})$, $(4^{3},\,3,\,1)$, $(4^{3},\,2^{2})$, $(4^{2},\,3^{2},\,2)$ e $(4,\,3^{4})$. In this case $2n-3=7$ so $[\lambda]$ has at most $7$ cells in each column. In the situation above, the algorithm marks at most $3$ cells in each column after the second: therefore, $\mu^{\prime}$ can’t be any of the first three. If $\mu^{\prime}$ were one of the other two partitions, then $\mu_{3}^{\prime}=3$, which means that $\lambda_{3}^{\prime}=7$, so $\lambda_{2}^{\prime}=7$ and $\mu_{2}^{\prime}=4$. This leaves $(4^{2},\,3^{2},\,2)$. In this case $\lambda^{\prime}=(7^{4},\,6,\,\ldots)$, which isn’t a partition of $32$. This proves that $\nu$ has at most $n-1$ parts.
Suppose $\mu=\nu$. This means that there is a column in $[\lambda]$ that comes after the second and has $n+i$ boxes, with $i\geq 0$, of which exactly $i+1$ have been marked. We deduce from this that no boxes were marked in the $(i+3)$-th column during the filling phase of the algorithm. The second column is $\lambda_{2}^{\prime}=n+j$ with $j\geq i$. Since $j+2\geq i+2$, exactly $j+2$ boxes have been marked in the second column. Therefore, $[\mu]$ has one column with $n-1$ boxes, and all others with at most $j+2$; meanwhile, $\nu$ has at least one column with $n-1$ boxes and at least one with $n-2$. If $n-2>j+2$, then $\mu\neq\nu$. This leaves $j=n-4,n-3$. In these cases, unmark the last cell marked and mark the first unmarked cell in the first column of $[\lambda]$. We replace $\mu$ with the partition corresponding to the new diagram made of marked boxes. We then fill $[\lambda\setminus\mu]$ using the same rule as before. The new partitions $\mu$ and $\nu$ are now such that $\mu$ has $n-1+1\leq 2(n-1)-3$ parts, and a column with $j+2\geq n-2\geq 3$ boxes, so $\mu\in\Omega_{2}(2^{n-1})$ since it isn’t a hook or almost-hook partition. Meanwhile, $\nu$ has $n-1$ parts and a column with $n-2\geq 3$ boxes, so it isn’t a hook partition.
The remaining case is that in which $\nu$ is a non trivial hook partition. By the proof above, we know that, in this case, $\nu$ has at most $n-2$ parts. Just as in Lemma 3.3 we can suppose that the unmarked cells lie in the union of a column and a row of $[\lambda]$ (otherwise we can change a $1$ to a $2$ in the filling). The column must be the first: we know that the boxes in the $n$-th and $n+1$-th positions of this column are left unmarked. The row must be the first. If this weren’t true, let $l$ be the number of unmarked elements in this row that aren’t in the first column. Counting marked and unmarked boxes, we have $l+(n-2)\geq l+(n-1)$. Therefore the algorithm has terminated before the filling phase, marking all boxes of the columns from the second onward until it stops before a column with just one part. This can only happen if $\lambda\in\mathcal{H}(2^{n})\cup\mathcal{AH}(2^{n})$.

∎

4. The general case

The first step towards generalizing the bound we have now proven for powers of two will be to give a generalization of Proposition 3.6. This will yield most cases and, at the same time, give a useful instrument for handling the rest.

Proposition 4.1.

Let $n\geq 16$ be an integer. Suppose $k$ is the greatest integer such that $2^{k}\leq n$. Then

$$\Delta(n,2k-3)\setminus\mathcal{AH}(n)\subseteq\Omega_{2}(n).$$

Proof.

Suppose $n$ and $k$ satisfy the conditions above, and $\lambda\in\Delta(n,2k-3)\setminus\mathcal{AH}(n)$. We can assume that $n$ is even: if $n$ is odd, just remove any box of $[\lambda]$ such that the remaining diagram doesn’t correspond to a hook or almost-hook partition. We will use the Littlewood-Richardson Rule and Proposition 2.8 to reduce to the base case proven in Proposition 3.6. We will do so by finding $\mu\in\Delta(2^{k},2k-3)\setminus\mathcal{AH}(2^{k})$ a subpartition of $\lambda$, and a L-R filling of $[\lambda\setminus\mu]$ of weight $\nu$, a partition with all parts even (Proposition 2.4).
We define the following algorithm: consider the last box in each column of $[\lambda]$, going from right to left, mark the maximum even number of these, such that the remaining boxes form the diagram of a partition which is not a hook nor an almost-hook partition. Remove the marked boxes of $[\lambda]$ and the columns in which no boxes have been marked. Repeat on the new diagram. Interrupt the algorithm once exactly $n-2^{k}$ boxes have been marked or the diagram that’s left is empty. Let $\mu$ be the subpartition of $\lambda$ corresponding to the diagram made up of all the unmarked cells in $[\lambda]$. Then use the usual L-R filling (Remark 2.2) of $[\lambda\setminus\mu]$: it’s weight is clearly a partition with all parts even ($\nu_{1}$ is the number of cells marked at the first iteration, $\nu_{2}$ the number marked at the second, and so on). All that’s left to prove is that it is, in fact, a partition of $n-2^{k}$. To do this, we will show that the algorithm cannot terminate before marking that many boxes. Suppose that the algorithm ends without marking $n-2^{k}$ boxes (so it reaches an empty set of boxes). Due to the algorithm’s definition there can’t be more than $2k-3$ unmarked boxes in the first column, $2k-4$ in the second, $2k-5$ in the third, and so on. This is clear when the algorithm operates smoothly, by which we mean that we can always mark the maximal number of boxes without leaving a hook or almost-hook partition. If at some iteration the algorithm cannot remove a box from the second column because this would make the remaining diagram an almost-hook partition, this means that there are only three boxes left in the second column and at most two in the ones following it. One box in the fourth column is marked at this iteration. The algorithm resumes its function regularly from the third or fourth column, which means that there are at most $3$ unmarked boxes in the second column, $2$ in the third, and $1$ in the fourth. If the algorithm cannot mark a cell in the third column, this means that there are only two unmarked cells in the second. Just as before we conclude that the number of unmarked boxes is at most $2$ in the second, third, and fourth column, and $1$ in the fifth. Therefore, the number of unmarked boxes can be at most $\frac{(2k-3)(2k-2)}{2}<2^{k}$, so the number of marked boxes must be greater than $n-2^{k}$ which gives a contradiction. ∎

The following example illustrates the functioning of the algorithm described in Proposition 4.1.

Example 4.2.

Let $n=23=16+4+2+1$ and $\lambda=(5^{3},\,4^{2})$. Then we can reduce to $n=22$ by taking for example $(5^{3},\,4,\,3)$. We then apply the algorithm and obtain the following figure.

                                             $$1 1 2 2 1 1$$                                                        

In this case $\mu=(5,\,4,\,3^{2},\,1)$ and $\nu=(4,\,2)$.

For many $n$, Proposition 4.1 gives a stronger result than the one we have set out to prove. In particular, let $n=\sum_{i=1}^{t}2^{a_{i}}$, with $a_{1}>\cdots>a_{t}$, if $a_{1}+t-1\leq 2a_{1}-3$, then Proposition 4.1 and Lemma 2.10 imply the desired result. There are, however, still an infinite number of cases that aren’t included in the above result ($t\in\{a_{1}-1,\,a_{1},\,a_{1}+1\}$). These will be eliminated in the next and final proof of this paper.

Theorem 4.3.

Let $n$ be a positive integer. Let $n=\sum_{i=1}^{t}2^{a_{i}}$, with $a_{1}>\cdots>a_{t}$. Let $k_{n}$ be the maximum integer such that $\Delta(n,k_{n})\subseteq\Omega_{2}(n)$. Then:

$$k_{n}=\begin{cases}\infty&\mbox{if $n\leq 5$ (formally, since $\mathcal{P}(n)\setminus\mathcal{H}(n)\subseteq\Omega_{2}(n)$)}\\ 1&\mbox{if $n=6,8,10$}\\ 2&\mbox{if $n=9$}\\ a_{1}+t-1&\mbox{if $n=7$ or $n\geq 11$}\end{cases}$$

Proof.

All cases up to $n=31$ have been verified using [GAP]. Let $n\geq 32$ and $n=\sum_{i=1}^{t}2^{a_{i}}$ its binary decomposition, with $a_{1}>\cdots>a_{t}$. Firstly, let us remind the reader that Lemma 2.10 provides the description of $\Omega_{2}(n)\cap\mathcal{AH}(n)$, and at the same time proves $k_{n}\leq a_{1}+t-1$, so we just have to prove that $\Delta(n,a_{1}+t-1)\setminus\mathcal{AH}(n)\subseteq\Omega_{2}(n)$. To do this we will use Proposition 2.8 and Proposition 4.1. Let $\lambda\in\Delta(n,a_{1}+t-1)\setminus\mathcal{AH}(n)$. By Proposition 4.1 we may assume that $a_{1}+t-1\geq 2a_{1}-2$ (which is to say $t=a_{1}-1,\,a_{1},\,a_{1}+1$) and that $\lambda$ has at least $2a_{1}-2$ parts. We will proceed by describing a similar algorithm on $[\lambda]$ to the one described in Proposition 4.1, such that the returned partitions $\mu\in\mathcal{P}(2^{a_{1}})$ and $\nu\in\mathcal{P}(n-2^{a_{1}})$ are of the kinds whose behavior has been characterised in the various lemmas and propositions above. In particular we want to be able to apply Proposition 4.1 to $\mu$ and $\nu$, so for this part of the proof we will assume $n-2^{a_{1}}\geq 16$ (equivalently $a_{2}\geq 4$).
The algorithm is the following: mark all boxes in the rows numbered $2a_{1}-2$ onward; if the number of marked boxes hasn’t exceeded $n-2^{a_{1}}$, mark the last box of each column from right to left (if one of such boxes has already been marked, leave as is), then the second last, and so on until $n-2^{a_{1}}$ cells have been marked. During the process, make sure to skip marking a box if the resulting diagram of unmarked boxes does not correspond to a partition or it corresponds to a hook or almost-hook partition. As before, we will call $\mu$ the partition corresponding to the diagram made up of unmarked boxes, and $\nu$ the partition obtained as the weight of the usual L-R filling of $[\lambda\setminus\mu]$ (Remark 2.2). The first thing we must prove is that the algorithm always marks exactly $n-2^{a_{1}}$ cells. The only way this may not occur is if $\lambda_{2a_{1}-2}+\lambda_{2a_{1}-1}+\lambda_{2a_{1}}>n-2^{a_{1}}$. If $a_{1}\geq 6$ some simple approximations show that this is impossible. To simplify notation, let $s:=t-a_{1}+2$ (the maximum number of parts following $\lambda_{2a_{1}-3}$):

$$\lambda_{2a_{1}-2}+\lambda_{2a_{1}-1}+\lambda_{2a_{1}}\leq\frac{n}{2a_{1}-2}\cdot s<\frac{2^{a_{1}+1}}{2a_{1}-2}\cdot s$$

$$n-2^{a_{1}}\geq 1+\cdots+2^{a_{1}+s-4}=2^{a_{1}+s-3}-1$$

$$1\geq\frac{8}{2a_{1}-2}+\frac{1}{2^{a_{1}-2}}\geq\frac{2^{4-s}}{2a_{1}-2}\cdot s+\frac{1}{2^{a_{1}+s-3}}.$$

The inequality for the remaining cases (those with $a_{1}=5$ and $a_{2}=4$) has been checked with [GAP]. This means that $\mu$ and $\nu$ are partitions of the correct numbers. By the definition of the algorithm $\mu\in\Delta(2^{a_{1}},2a_{1}-3)\setminus\mathcal{AH}(2^{a_{1}})$.
Now we will prove that $\nu$ has at most $2a_{2}-3$ parts. If this weren’t true, we would have had to mark more than the set comprised of the last $2a_{2}-3$ boxes in each column (except for the boxes $(1,2)$, $(2,2)$, $(3,2)$ or $(1,2)$, $(2,2)$, $(1,3)$, $(2,3)$). The number of such boxes is at least $\lambda_{1}+\cdots+\lambda_{2a_{2}-3}-4$. Therefore it suffices to prove that $\lambda_{1}+\cdots+\lambda_{2a_{2}-3}-4\geq n-2^{a_{1}}$ or equivalently that $\lambda_{2a_{2}-2}+\cdots+\lambda_{a_{1}+t-1}+4\leq 2^{a_{1}}$. As before, this is easy to prove for large $a_{1}$ (in this case $a_{1}\geq 9$), meanwhile, cases $a_{1}=6,\,7,\,8$ have been checked by hand using better approximations, and the case $a_{1}=5$ has been checked using [GAP]. For $a_{1}\geq 9$ the simple approximations used are the following (again $s:=t-a_{1}+2$):

$$a_{1}+t-1-2a_{2}+3\leq 2a_{1}+s-3-2(a_{1}-4+s)+3=8-s$$

$$\lambda_{2a_{2}-2}+\cdots+\lambda_{a_{1}+t-1}+4\leq\lceil\frac{n}{a_{1}+t-1}\rceil\cdot(8-s)+4<\frac{2^{a_{1}+1}}{2a_{1}-2}\cdot 7+11$$

$$\frac{14}{2a_{1}-2}+\frac{11}{2^{a_{1}}}\leq 1.$$

The only cases remaining now are those in which $\nu\in\mathcal{H}(n-2^{a_{1}})\cup\mathcal{AH}(n-2^{a_{1}})$. In this case we will prove that the number of parts of $\nu$ is at most $3\leq a_{1}-2\leq t-1$ so $\nu\in\Omega_{2}(n-2^{a_{1}})$ (by Lemma 2.9 and Lemma 2.10). Suppose that $\nu$ is a hook or almost-hook partition with at least four parts. This means that the algorithm has continued to the second phase, and has marked the last three cells in each column (excluding the ones of the type mentioned above). Since $[\nu]$ has at most two columns with more than one cell, only one of which (the first) has more than two cells, the first column of $[\nu]$ must correspond to the marked cells in the first column of $[\lambda]$, in which at least three boxes have been marked. At the third pass of the second phase of the algorithm, there must have been only one available cell to mark, and this must have been in the first column; this means that removing any other cell from the diagram gives an almost-hook partition or something that isn’t a partition. This means that $\mu$ is of the form $(m,\,2^{2})^{\prime}$ or $(m,\,3)^{\prime}$ and in both cases $m\leq 2a_{1}-4$. However $m+4\leq 2a_{1}<2^{a_{1}}$ gives a contradiction.
There are now only a finite number of remaining cases: those $n>32$ such that $t\geq a_{1}-1$ and at the same time $a_{2}<4$. These numbers are $39,\,43,\,45,\,46,\,47,\,79$. Each case can be solved by hand by reducing to a smaller $n$. For example, let $\lambda\in\mathcal{P}(39)$ be a partition with $8$ parts. Since $4<\frac{39}{8}<5$, this means that $\lambda_{1}\geq 5$ and $\lambda_{8}\leq 4$. If $\lambda_{8}=1,2,4$, let $\mu\in\mathcal{P}(38),\mathcal{P}(37),\mathcal{P}(35)$ (respectively) be the partition obtained by removing the last part, if $\lambda_{8}=3$, let $\mu\in\mathcal{P}(35)$ be the partition corresponding to the diagram obtained from $[\lambda]$ by removing the last row and the last cell of the last column. In every case $\mu$ is neither a hook nor almost-hook partition and the usual Littlewood-Richardson filling has weight corresponding to the trivial partition (of $1,2$ or $4$). We will omit the proof of the other cases, since they are very similar to the one above. ∎