Abstract
The tensor square conjecture states that for \(n \ge 10\), there is an irreducible representation V of the symmetric group \(S_n\) such that \(V \otimes V\) contains every irreducible representation of \(S_n\). Our main result is that for large enough n, there exists an irreducible representation V such that \(V^{\otimes 4}\) contains every irreducible representation. We also show that tensor squares of certain irreducible representations contain \((1-o(1))\)-fraction of irreducible representations with respect to two natural probability distributions. Our main tool is the semigroup property, which allows us to break partitions down into smaller ones.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction and main results
Much of the representation theory of the symmetric group \(S_n\) is well understood. Its irreducible representations have known explicit descriptions. One poorly understood facet, however, is the decomposition of tensor products of its representations into irreducibles. This paper focuses on a conjecture related to these decompositions, which was introduced in [12].
Conjecture 1.1
(Tensor square conjecture) For every n except 2, 4, 9, there exists an irreducible representation V of the symmetric group \(S_n\) such that the tensor square \(V \otimes V\) contains every irreducible representation of \(S_n\) as a summand with positive multiplicity.
We first remark that for any faithful representation V of a finite group G, i.e. a representation such that each \(g\in G\) acts differently on V, there is some n such that the tensor power \(V^{\otimes n}\) contains every irreducible representation of G ([9] Ex. 2.37). In the case of \(G=S_n\), the standard representation of \(S_n\) contains a faithful and irreducible representation V of dimension \(n-1\), so a sufficiently large tensor power \(V^{\otimes k}\) contains every irreducible representation. However, the tensor square conjecture is a much stronger statement than this because it requires such a small exponent.
As is well known (e.g. [9]), there is an explicit correspondence between the set of irreducible representations of \(S_n\) over \(\mathbb {C}\) and the set \(P_n\) of partitions \(\lambda \) of n, i.e. sequences \(\lambda =(\lambda _1,\lambda _2,\ldots )\) of non-negative integers with \(\lambda _1\ge \lambda _2\ge \cdots \) and \(\sum _{i\ge 1}\lambda _i=n\). By associating \(\lambda \) to the Young diagram with \(\lambda _i\) boxes in row i, we may equivalently correspond each irreducible representation of \(S_n\) with a Young diagram with n boxes. This correspondence allows the use of combinatorial tools in analysing many aspects of the representation theory of \(S_n\). Because these notions are equivalent for our purposes, we will freely denote by (e.g.) \(\lambda \) both the partition or Young diagram corresponding to \(\lambda \) and the associated irreducible representation of \(S_n\).
In view of this correspondence, we may express the tensor square conjecture in terms of partitions.
Conjecture 1.1
(Tensor square conjecture) For every n except 2, 4, 9, there exists a partition \(\lambda \vdash n\) such that the tensor square \(\lambda \otimes \lambda \) contains every irreducible representation of \(S_n\) as a summand with positive multiplicity.
This conjecture can also be restated in terms of positivity of Kronecker coefficients \(g_{\lambda \mu }^{\nu }\), the multiplicities of \(\nu \) in the tensor product \(\lambda \otimes \mu \): it asserts the existence of \(\lambda \) such that \(g_{\lambda \lambda }^{\nu }>0\) for all \(\nu \). Unlike many other coefficients arising in the representation theory of \(S_n\), the Kronecker coefficients lack a known combinatorial interpretation. Indeed, finding one has been said to be “one of the last major open problems in the ordinary representation theory of the symmetric group” [13]. The computation of Kronecker coefficients has been shown to be computationally hard [5].
In [12], Pak et al. studied the tensor square conjecture and suggested two families of partitions which might satisfy the conjecture, the staircase, and caret partitions. The conjecture that the staircase partition suffices is also known as the Saxl conjecture (see [10, 12]).
Definition 1
For \(m\ge 1\), the staircase partition \(\rho _m\vdash \left( {\begin{array}{c}m+1\\ 2\end{array}}\right) \) is
Definition 2
For \(m\ge 1\), the caret partition \(\gamma _m\vdash 3m^2\) is
Conjecture 1.2
(Saxl conjecture) For \(n=\left( {\begin{array}{c}m+1\\ 2\end{array}}\right) \), all partitions of n are contained in \(\rho _m^{\otimes 2}\).
Conjecture 1.3
For \(n=3m^2\), all partitions of n are contained in \(\gamma _m^{\otimes 2}\).
Previous work made progress towards the tensor square conjecture and towards the Saxl conjecture in particular. Pak, Panova, and Vallejo used a lemma on nonzero character values to show that the tensor square of the staircase contains all hooks, partitions with two rows, and some partitions with three rows or with two rows plus an extra column [12]. Similar results were shown for the tensor square of the caret shape. They also showed that the staircase partition \(\rho _k\) contains at least \(3^{\lceil k/2\rceil -1}\) distinct partitions in its tensor square. This is noteworthy since the total number of partitions of \(n=\frac{k(k+1)}{2}\) is also roughly on the order of \(e^{ck}\) for some c.
Ikenmeyer [10] further generalized some of this progress by showing a result based on comparability of partitions to the staircase in dominance order. This result, which we will use heavily in our work, will be described in greater detail in Sect. 2.2.
Although preliminary evidence suggests that there could in fact be many shapes \(\lambda \) that satisfy the tensor square conjecture for each n, several simple criteria are known. For example, \(\lambda ^{\otimes 2}\) contains the alternating representation \(1^n\) if and only if \(\lambda \) is identical to its conjugate \(\lambda '\) [12], which means that only symmetric \(\lambda \) can satisfy the full tensor square conjecture.
We obtain several results towards the tensor square conjecture. The primary result is the following.
Theorem 1.4
For sufficiently large n, there exists \(\lambda \vdash n\) such that \(\lambda ^{\otimes 4}\) contains all partitions of n.
The partitions \(\lambda \) we use are staircases \(\rho _m\) when n is a triangular number and slight adjustments of them when n is not.
We prove Theorem 1.4 by combining two results that are of independent interest: we define a simple metric on the set of partitions of n and show that the set of partitions appearing in \(\lambda ^{\otimes 2}\) is dense in an appropriate sense. We also show that all partitions close to the trivial representation are contained in \(\lambda ^{\otimes 2}\). Together, these results almost immediately imply that \(\lambda ^{\otimes 4}\) contains all partitions of n (when n is sufficiently large).
In addition, we prove some probabilistic results towards the Saxl conjecture.
Theorem 1.5
Let \(m\ge 0\). Then, \(\rho _m^{\otimes 2}\) contains almost all partitions of \(\left( {\begin{array}{c}m+1\\ 2\end{array}}\right) \) in the uniform measure, in which all distinct partitions are given the same probability.
Theorem 1.6
Let \(m \ge 0\). Then, \(\rho _m^{\otimes 2}\) contains almost all partitions of \(\left( {\begin{array}{c}m+1\\ 2\end{array}}\right) \) with respect to the Plancherel measure.
Remark
We use the phrases “almost all” and “with high probability” throughout this paper to mean that a sequence of probabilities tends to 1 as the parameter n or m tends to infinity. For example, Theorem 1.5 states that the probability p(m) that a uniformly random partition \(\lambda \vdash \left( {\begin{array}{c}m\\ 2\end{array}}\right) \) is contained in \(\rho _m^{\otimes 2}\) converges to 1 as m grows large. In particular, this language implies nothing about the rate of convergence.
The Plancherel measure will be discussed in Sect. 3.1.
2 Basic tools
2.1 Partitions and representations
Recall that irreducible representations of the symmetric group \(S_n\) correspond to Young diagrams, or equivalently to partitions \(\lambda \vdash n\) of n. We will use Young diagrams and partitions interchangeably, and we denote by \(P_n\) the set of partitions of n. We will use multiple orientations on Young diagrams: as is conventional, we call the coordinates depicted below at left English, those in the middle French, and those at right Russian. We use \(1_n\) to denote the trivial representation, \(1^n\) the alternating representation, and \(\lambda '\) the conjugate of \(\lambda \) (Figs. 1, 2, 3).
English coordinates
French coordinates
Russian coordinates
Lemma 2.1
[9, Section 4.1] Let \(\lambda \vdash n\). Then \(\lambda ' = \lambda \otimes 1^n\).
For simplicity, we define an indicator function for constituency.
Definition 3
Let \(c(\lambda ,\mu ,\nu )\) be the statement that \(g_{\lambda ,\mu }^{\nu }>0\).
We first establish some well-known, basic properties of \(c(\lambda ,\mu ,\nu )\).
Lemma 2.2
The function c is symmetric in its three arguments.
Proof
Let \(\chi ^V:S_n\rightarrow \mathbb C\) denote the character function for a representation V. We have
and similarly for other permutations. Here, we use the facts that all representations of \(S_n\) have real characters and that \(\chi ^{V\otimes W}=\chi ^V\chi ^W\).\(\square \)
Lemma 2.3
If \(c(\lambda ,\mu ,\nu )\) then \(c(\lambda ',\mu ',\nu )\).
Proof
By Lemma 2.1, we have \(\lambda '\otimes \mu '= (\lambda \otimes 1^n) \otimes (\mu \otimes 1^n)=(\lambda \otimes \mu ) \otimes (1^n\otimes 1^n) = \lambda \otimes \mu \), so the result follows by the definition of the Kronecker coefficient.\(\square \)
There is one more special representation that we will use repeatedly.
Definition 4
The standard representation of \(S_n\) is \(\tau _n={\text {Ind}}_{S_{n-1}}^{S_n}(1)\). Equivalently, \(\tau _n\) is the n-dimensional representation in which \(S_n\) acts by permuting n basis vectors \(v_1\ldots v_n\) in the usual way.
It is well known that \(\tau _n\) is the sum of the irreducible representations corresponding to the partitions \((n), (n-1,1)\); the trivial component comes from the vector \((v_1+\cdots +v_n)\), which all elements of \(S_n\) fix. It is easy to see from the above description that the remaining part corresponding to \((n-1,1)\) is a faithful representation, as claimed above.
It is known that for an irreducible representation \(\lambda \), the tensor product \(\tau _n \otimes \lambda \) is the formal sum (with multiplicity) of all partitions which can be formed by moving a single square in the Young diagram for \(\lambda \) (including \(\lambda \) itself). (Pieri’s Rule, [9] Ex. 4.44). This fact will be used extensively later in the paper.
Finally, we recall the definition of the Durfee square.
Definition 5
The Durfee length \(d(\lambda )\) of a partition \(\lambda \) is the largest integer r with \(\lambda _r\ge r\).
Definition 6
The Durfee square of a partition \(\lambda \) is the square of side length \(d(\lambda )\) with the principal diagonal as its diagonal (beginning in the upper left corner in English coordinates), considered as a subset of \(\lambda \) in the plane.
2.2 The semigroup property and dominance ordering
We extensively use the \(\textit{semigroup property}\), which was proved in [6]. To state this, we first define the horizontal sum of partitions, in which we add row lengths, or equivalently take the disjoint union of the multisets of column lengths.
Definition 7
The horizontal sum \(\lambda +_{_H}\lambda _2\) of partions \(\lambda =(\lambda _1,\lambda _2, \ldots ) \vdash n_1\) and \(\mu =(\mu _1, \mu _2 \ldots ) \vdash n_2\) is the partition \((\lambda _1+\mu _1, \lambda _2+\mu _2, \ldots ) \vdash (n_1+n_2)\).
We also define horizontal scalar multiplication by positive integers on partitions, simply by repeated addition.
Definition 8
For \(k\ge 0\), define the horizontal scalar multiple \(k_{_H}\lambda \) by \(k_{_H}\lambda =\lambda +_{_H}\lambda +_{_H}\cdots +_{_H}\lambda \), where we add k copies of \(\lambda \).
We also define vertical addition and scalar multiplication analogously, by adding column lengths instead.
Definition 9
We define the vertical sum \(\lambda _1+_{_V}\lambda _2\) of \(\lambda _1,\lambda _2\) to be \((\lambda _1'+_{_H}\lambda _2')'\)
Definition 10
Define the vertical scalar multiple \(k_{_V}\lambda \) by \(k_{_V}\lambda =\lambda +_{_V}\lambda +_{_V}\cdots \lambda \) where we add k copies of \(\lambda \).
We now state the semigroup property.
Theorem 2.4
(Semigroup property, [6, Theorem 3.1]) If \(c(\lambda _1, \lambda _2, \lambda _3)\) and \(c(\mu _1,\mu _2, \mu _3)\), then \(c(\lambda _1+_{_H}\mu _1, \lambda _2+_{_H}\mu _2, \lambda _3 +_{_H}\mu _3).\)
We can use induction on Theorem 2.4 to extend the semigroup property to arbitrary numbers of partitions. However, we will not need this for the bulk of our paper, so we refer the reader to Appendix 10.2.
We now give a modified version of 2.4 using vertical sums.
Corollary 2.5
If \(c(\lambda _1, \lambda _2, \lambda _3)\) and \(c(\mu _1,\mu _2, \mu _3)\), then \(c(\lambda _1+_{_V}\mu _1, \lambda _2+_{_V}\mu _2, \lambda _3 +_{_H}\mu _3).\)
Proof
By Lemma 2.3, we have \(c(\lambda '_1,\lambda '_2,\lambda _3)\) and \(c(\mu '_1,\mu '_2,\mu _3)\). Then, the semigroup property yields \(c(\lambda '_1+_{_H}\mu '_1,\lambda '_2+_{_H}\mu '_2,\lambda _3+_{_H}\mu _3)\). Applying Lemma 2.3 again yields the result.\(\square \)
In other words, in using the semigroup property, we are allowed to use an even number of vertical additions in each step. It is not true that vertically adding all 3 partitions preserves constituency. For example, we have c((1), (1), (1)) for the trivial representations of \(S_1\), but vertically adding this to itself gives that the alternating representation of \(S_2\) is contained in its own tensor square. This tensor square is just the trivial representation which, of course, does not contain the alternating representation.
We will also extensively use the following result from [10]. First, we recall the notion of dominance ordering, which gives a partial ordering on partitions of n.
Definition 11
Let \(\lambda , \mu \vdash n\). We say that \(\lambda \) dominates \(\mu \) (or \(\lambda \succeq \mu \)) if for all \(k \ge 1\), \(\sum _{i=1}^{k}\lambda _i \ge \sum _{i=1}^{k}\mu _i\).
Theorem 2.6
[10, Theorem 2.1] Let \(m\ge 1\). Then, \(\rho _m \otimes \rho _m\) contains all partitions \(\lambda \) which are dominance comparable to \(\rho _m\).
Remark
We have also generalized Theorem 2.6 to arbitrary partitions with distinct row lengths (see Theorem 9.1), which seems potentially useful for extending the applicability of the semigroup property.
The main method used throughout the paper will be to try to express triples \((\rho _k,\rho _k,\lambda )\) as sums of smaller triples, each of which satisfies constituency because of Theorem 2.6, and then conclude \(c(\rho _k,\rho _k,\lambda )\) via the semigroup property. This method is powerful because small staircases can be added together to form larger staircases. This will be explained throughout the following sections, which contain overviews of the proofs of our main results.
3 Overview of the probabilistic approach
3.1 Partition measures
In this section, we address a probabilistic weakening of the tensor square conjecture:
Question
For large m, what is the probability that a random partition of \(\left( {\begin{array}{c}m+1\\ 2\end{array}}\right) \) is a constituent in the tensor square \(\rho _m^{\otimes 2}\)?
To answer this question, we must first put a probability distribution on the set \(P_n\) of partitions of n. The most obvious choice is the uniform distribution.
Definition 12
The uniform measure \(U_n\) assigns probability \(\frac{1}{|P_n|}\) to each distinct partition of n.
There is another natural family of probability distributions on \(P_n\) we investigate, which is rooted in representation theory.
Definition 13
The Plancherel measure \(M_n\) assigns to each \(\lambda \vdash n\) probability \(\frac{\dim (\lambda )^2}{n!}\). Here, \(\dim (\lambda )\) is the dimension of \(\lambda \) as a representation of \(S_n\).
The value \(\dim (\lambda )\) has the following famous combinatorial interpretation: it is the number of standard Young tableau of shape \(\lambda \), i.e. bijective assignments of \((1,2,\ldots ,n)\) to the boxes of \(\lambda \) such that the numbers increase along each row and column [14].
3.2 Limit shapes of partition measures
The uniform and Plancherel measures \(U_n\) and \(M_n\) give rise to different smooth limit shapes for large n; in each case, we may speak of the “typical shape” of a large random partition. Given a Young diagram \(\lambda \) of size n, we may shrink it by a linear scale factor of \(\frac{\sqrt{2}}{\sqrt{n}}\) so that it has area 2, and rotate it into Russian (diagonal) coordinates. This results in the graph of a function \(f_{\lambda }\), and by defining \(f_{\lambda }(x)=|x|\) past the boundary of the Young diagram, we get a function defined on the whole real line which satisfies
and
and
Definition 14
The set \(\mathscr {CY}\) of continuous Young diagrams is the set of functions \(\mathbb {R}\rightarrow \mathbb {R}\) satisfying (1), (2), and (3).
We also define a family \(\mathscr {SY}\) of continuous Young diagrams in French coordinates, this time with area 1. Given \(f_1, f_2 \in \mathscr {CY}\), we change them into \(F_1, F_2\) in French coordinates by simply rotating and then reflecting, and also dilating by a linear scale factor of \(\frac{1}{\sqrt{2}}\). Taking the càdlàg version, we obtain a non-increasing function \((0,\infty ) \rightarrow [0,\infty )\).
Definition 15
Let \(\mathscr {SY}\) be the set of functions \((0,\infty ) \rightarrow [0,\infty )\) which are non-increasing, càdlàg, and have total integral 1.
Definition 16
For \(f_1 \in \mathscr {CY}\), the straightening \(F_1 = S(f_1) \in \mathscr {SY}\) is the right-continuous function \(\mathbb {R}^+ \rightarrow \mathbb {R}^+\) given by rotation to English coordinates of the graph of \(f_1\) followed by reflection over the x-axis, and then dilation by a factor of \(\frac{1}{\sqrt{2}}\).
Definition 17
For \(\lambda \vdash n\), define \(F_{\lambda }=S(f_{\lambda })\).
On \(\mathscr {CY}\), we will use the supremum norm \(d(f,g)=||f-g||_{\infty }\). We define the metric on \(\mathscr {SY}\) to agree with d under the canonical bijection S. This makes d on \(\mathscr {SY}\) simply twice the Lévy metric [3].
Using the canonical map \(P_n \rightarrow \mathscr {CY}\) given by \(\lambda \mapsto f_{\lambda }\), we may pushforward the measures \(M_n, U_n\) to finitely supported measures on \(\mathscr {CY}\). This allows us to state the limit shape results precisely.
Theorem 3.1
[16] The pushforwards of the measures \(M_n\) converge in probability to the delta measure on the function
Theorem 3.2
[15] The pushforwards of the measures \(U_n\) converge in probability to the delta measure on the function
where \(b=\frac{\pi }{2\sqrt{6}}\).
So under both uniform and Plancherel measure, for large n, almost all Young diagrams look like a smooth limiting curve if we zoom out to a constant-size scale. The limit shapes for the Plancherel and uniform measures are, respectively, shown below (Figs. 4, 5).
Plancherel limit shape
Uniform limit shape
The limit shape of \(U_n\) may be more elegantly described in French coordinates, where it is the graph of \(e^{-\frac{\pi x}{\sqrt{6}}}+ e^{-\frac{\pi y}{\sqrt{6}}}=1\).
We will extend the definitions of length and height of Young diagrams to the continuous Young diagrams. For ordinary Young diagrams \(\lambda \vdash n\), we have that the length of \(\lambda \) is \(\lambda _1=\sqrt{n}\sup (\{x|f_{\lambda }(x)=-x\})\) and the height is \(\lambda '_1=\sqrt{n}\inf (\{x|f_{\lambda }(x)=x\})\), given by the lowest spots on the rotated axes that the functions meet. Defining the normalized length and height by \(\ell (\lambda ):=\frac{\lambda _1}{\sqrt{n}}, h(\lambda ):=\frac{\lambda '_1}{\sqrt{n}}\), we may extend the rescaled length and height to \(\mathscr {CY}\) and hence also to \(\mathscr {SY}\):
Definition 18
For \(f \in \mathscr {CY}\), define its (possibly infinite) length and height as
Definition 19
For \(F\in \mathscr {SY}\), let \(\ell (F)=\inf (\{x|F(x)=0\})\).
Definition 20
For \(F\in \mathscr {SY}\), let \(h(F)=\lim _{t\rightarrow 0^+} F(t)\).
Note that these definitions respect the bijection S because of the area difference between the types of continuous Young diagrams.
We define \(C_f\) to be the region between \(f \in \mathscr {CY}\) and the graph of \(y=|x|\), and \(S_F\) the corresponding notion for \(F\in \mathscr {SY}\).
Definition 21
For \(f\in \mathscr {CY}\), let \(C_f=\{(x,y)|f(x)\ge y\ge |x|\}\).
Definition 22
For \(F\in \mathscr {SY}\), let \(S_F=\{(x,y)\in (\mathbb {R}^+)^2|y\le F(x)\}\).
We now extend the dominance ordering to continuous Young diagrams.
Definition 23
For \(F \in \mathscr {SY}\), define \(H_F(t)=\int _0^{t} F(x) \mathrm{d}x \).
Definition 24
For \(F_1, F_2 \in \mathscr {SY}\), we say that \(F_1 \succeq F_2\) if they satisfy
for all t.
Definition 25
For \(f_1, f_2 \in \mathscr {CY}\), we say that \(f_1\succeq f_2\) if \(S(f_1)\succeq S(f_2)\).
It is clear that these dominance orders are extensions of the ordinary dominance order. That is, if \(\lambda ,\mu \vdash n\) then \(\lambda \succeq \mu \) if and only if \(f_{\lambda }\succeq f_{\mu }\).
We also define \(\rho _{\infty }\).
Definition 26
Let \(\rho _{\infty }\) be the continuous Young diagram which is an isosceles right triangle, so
We now establish a few simple lemmas on the geometry of continuous Young diagrams.
Definition 27
For A a subset of \(\mathbb {R}^2\), let \(A^{\varepsilon }=\{x\in \mathbb {R}^2|d(x,A)\le \varepsilon \}\) and \(A_{\varepsilon }=((A^{C})^{\varepsilon })^C\), where \(A^C\) is the complement of A.
Definition 28
For \(A\subseteq \mathbb {R}^2\), we denote by m(A) the Lebesgue measure of A (assuming it exists).
Lemma 3.3
The functions \(\ell , h :\mathscr {CY}\rightarrow \mathbb {R}\) are lower semi-continuous with respect to the norm d.
Proof
We show the result for h, the other case being exactly the same. Suppose \(h(f) > A\). We show that for g sufficiently close to f, we have \(h(g) >A\). Indeed, for some \(x>A\), we have \(f(x)-|x|=c>0\). For \(|f-g| < c\), we have \(g(x)-|x|>0\), implying \(h(g)>A\) as desired. \(\square \)
Lemma 3.4
For fixed \(F\in \mathscr {SF}\), if \(S_F\) is a bounded subset of the plane then we have
Proof
It is clear that we have \(m(S_F)=1\). We proceed with the remaining claims.
We note that the closure \(\overline{S_F}\) and the interior \(\overset{\circ }{S_F}\) have equal measure. Indeed, \(\overline{S_F}-(\overset{\circ }{S_F})\) consists of a countable number of vertical lines (corresponding to the discontinuities of F) and the graph of F, each of which has measure 0 by Fubini’s theorem. Now, as \(\varepsilon \) approaches 0, the sets \((S_F)^{\varepsilon }\) intersect to \(\overline{S_F}\). Since \(S_F\) is bounded, these sets converge in measure to \(\overline{S_F}\) by the dominated convergence theorem. Similarly, as \(\varepsilon \) approaches 0, the sets \((S_F)_{\varepsilon }\) converge in measure to \(\overset{\circ }{S_F}\). Since we have \(m(\overline{S_F})=m(S_F)=m(\overset{\circ }{S_F})\), the lemma follows.\(\square \)
Lemma 3.5
Given \(f_1, f_2 \in \mathscr {CY}\), assume that \(f_1(x)=f_2(x)>|x|\) has at most 1 solution in x and that \(\ell (f_1)>\ell (f_2),\) \(h(f_1) < h(f_2)\). Then, \(f_1(x)=f_2(x)>|x|\) has a unique solution and \(f_1 \succeq f_2\). Moreover, there exists \(\varepsilon >0\) such that the following holds: for all continuous Young diagrams \(g_1, g_2\) with \(||g_i-f_i||_{\infty } \le \varepsilon \) for \(i \in \{1,2\}\) and also \(|\ell (f_2)-\ell (g_2)| \le \varepsilon \) and \(|h(f_1)-h(g_1)| \le \varepsilon \), we have \(g_1\succeq g_2\).
Proof of Lemma 3.5
The following pictures will probably be helpful aids for understanding the proof. They correspond to Russian and French coordinates, respectively, with the blue curve as \(f_1\) and \( F_1=S(f_1)\) and the green line as \(f_2\) and \( F_2=S(f_2)\).
First, we establish that
has a solution. This is simple: we have \(f_1(-\ell (f_2)) > f_2(-\ell (f_2))=\ell (f_2)\) and \(f_2(h(f_1))>f_1(h(f_1))=h(f_1))\), so we may apply the intermediate value theorem to find a real number \(c \in (-\ell (f_2),h(f_1))\) for which \(f_1(c)=f_2(c)\). By the Lipschitz condition on \(\mathscr {CY}\), c clearly satisfies \(f_1(c)=f_2(c)>|c|.\)
Consider the continuous function \(f_3(x)=f_1(x)-f_2(x)\). We have that the equation
has a unique solution c, and also that \(\{x|f_1(x)=f_2(x)=|x|\}=(-\infty ,-\ell (f_1))\cup (h(f_2),\infty ).\) Therefore, \(f_3^{-1}(0)=(-\infty ,-\ell (f_1))\cup \{c\} \cup (h(f_2),\infty )\). We have again that \(f_1(-\ell (f_2)) > f_2(-\ell (f_2))=\ell (f_2)\) and \(f_2(h(f_1))\ge f_1(h(f_1))=h(f_1)\), which yield \(f_3(-\ell (f_2))\ge 0\) and \(f_3(h(f_1))\le 0\). By continuity, we therefore see that \(f_3(x)>0\) for \(x\in (-\ell (f_1),c)\) and \(f_3(x)<0\) for \(x\in (c,h(f_2))\).
Let us straighten this picture into French coordinates, with \(F_1=S(f_1), F_2=S(f_2)\) and \((c,f_1(c))\) becoming \((k, F_1(k))\). Then, our last deduction translates into the fact that \(F_2-F_1\) is positive on (0, k), 0 at k, negative on \([k,\ell (f_1))\) and 0 on \([\ell (f_1),\infty )\). Since both functions have integral 1, it is clear to see that the function \(I(t)=H_{F_2}(t)-H_{F_1}(t)\) is 0 at 0, positive on \((0,\ell (f_1))\) and 0 on \([\ell (f_1),\infty )\). Therefore, \(f_1\succeq f_2\).
We now establish \(g_1\succeq g_2\) for \(g_i\) satisfying the conditions in the lemma statement for small \(\varepsilon \). Define \(G_1, G_2 \in \mathscr {SY}\) as \(S(g_1),S(g_2)\), and \(J(t)=H_{G_2}(t)-H_{G_1}(t)\). We show \(J(t)\ge 0\) for all t, when \(\varepsilon \) is small enough. First, the condition \(|\ell (f_2)-\ell (g_2)| \le \varepsilon \) combined with 3.3 guarantees that J(t) is positive near \(\ell (f_1)\), because for small enough \(\varepsilon \), we have \(\ell (G_1)>\ell (G_2)\). Similarly, the condition \(|h(f_1)-h(g_1)| \le \varepsilon \) combined with 3.3 ensures that the initial “columns” of \(G_2\) are larger than that those of \(G_1\), i.e. that \(G_2(x)-G_1(x)>0\) for x small. So for \(\varepsilon \) small, J(t) is positive near 0.
Now, we need only show that \(J(t)\ge 0\) for \(t\in [\alpha ,\ell (f_1)-\alpha ]\) for some \(\alpha > 0\). Note that because \(I(t)>0\) on \([\alpha ,\ell (f_1)-\alpha ]\), by compactness there exists \(\delta > 0\) with \(I(t) > \delta \) for \(t \in [\alpha ,\ell (F_1)-\alpha ]\).
Now, we claim that \((S_{F_2})_{\varepsilon \sqrt{2}} \subseteq S_{G_2}\). Indeed, if \((x,y) \in (S_{F_2})_{\varepsilon \sqrt{2}}\), then
as desired. Therefore, by Lemma 3.4, picking \(\varepsilon \) small forces \(S_{F_2}, S_{G_2}\) to be arbitrarily close in measure. We have
so by picking \(\varepsilon \) small we force \(|J(t)-I(t)|\) to be uniformly small. Since I(t) is bounded away from 0 on the interval \([\alpha ,\ell (F_1)-\alpha ]\), for small \(\varepsilon \) we have \(J(t)>0\) on that interval. This shows we can force \(J(t)>0\) for all \(t\in \mathbb {R}\), concluding the proof.\(\square \)
Continuous young diagrams in English coordinates
Continuous young diagrams in Russian coordinates
Lemma 3.6
For \(F \in \mathscr {SY}\), let \(H_F(t)=\int _{0}^t F(t) \mathrm{d}t\). For every \(\varepsilon > 0\), there exists \(\delta \) such that the following holds: if \(G \in \mathscr {SY}\) satisfies \(d(F,G) \le \delta \) then \(|H_F-H_G|_{\infty } \le \varepsilon \).
Proof of Lemma 3.6
Fix \(\varepsilon \) as in the statement. By exhaustion take a, b such that \(\int _a^b F(t) \mathrm{d}t \ge 1-\frac{\varepsilon }{4}\). Now pick \(\delta \) such that if \(d(F,G)\le \delta \) then \(|F(x)-G(x)| \le \frac{\varepsilon }{4(b-a)}\) for \(x \in [a,b]\). Then \(\int _a^b G(t) \mathrm{d}t \ge 1-\frac{\varepsilon }{2}\) and so \(\int _0^a G(t) \mathrm{d}t \le \frac{\varepsilon }{2}, \int _b^{\infty } G(t) \mathrm{d}t \le \frac{\varepsilon }{2}\) because \(\int _0^{\infty } G(t) \mathrm{d}t =1\). Therefore, for \(x \not \in [a,b]\) the desired \(|H_F(x)-H_G(x)| \le \varepsilon \) holds. For \(x \in [a,b]\) we have \(|H_F(x)-H_G(x)| \le |H_F(a)-H_G(a)|+|\int _a^x F(x)-G(x)| \le \frac{\varepsilon }{2}+\frac{\varepsilon }{2}= \varepsilon \). \(\square \)
3.3 Overview of proofs for probabilistic results
For both \(U_n\) and \(M_n\), we know now the overall shape of a generic partition \(\lambda \vdash n\). Our strategy is the following: we will decompose these partitions into pieces, handle each piece using Theorem 2.6 on dominance, and combine these pieces using the semigroup property. We will need a way to combine smaller staircases into larger ones. For this section, we will use the following identities (Figs. 6, 7).
Proposition 3.7
We have the identities
Visual depictions for both cases when \(k=2\) are below (Figs. 8, 9).
Decomposition of \(\rho _4\)
Deomposition of \(\rho _5\)
This means that we can break a large staircase of size n into four staircases of size roughly \(\frac{n}{4}\). Supposing for convenience that \(m=2k\) is even, by the above proposition, to show \(c(\rho _m,\rho _m,\lambda )\) for some \(\lambda \), it suffices to write \(\lambda \) as
where \(c(\rho _{k-1},\rho _{k-1},\lambda _1)\) and \(c(\rho _k,\rho _k,\lambda _i)\) for \(i \in \{2,3,4\}\). For in such a case, the semigroup property gives
Perhaps surprisingly, this method suffices to show constituency in \(\rho _m^{\otimes 2}\) for almost all partitions in both the uniform and Plancherel cases. In each case, we can break the limit shape into four pieces of approximately equal area. For the uniform shape, we use vertical cuts as depicted at right. For the Plancherel limit shape, we evenly distribute the columns among the four smaller pieces, so that each smaller piece has approximately the same shape.
In each case, the dominance comparability of the smaller pieces with a staircase partition follows by geometric reasoning on the limit shapes. What is a bit more subtle is ensuring that these decompositions can be done precisely: to apply the semigroup property, each of our four pieces must have size exactly equal to that of a certain staircase partition. For this point, our strategy is to divide almost all of the large partition into our four pieces but reserve some very short columns for the end of the process. We distribute these short columns to the pieces such that each piece has exactly the correct size, without affecting their overall shapes significantly. To justify all of these details requires a bit of care, and we do this in the following section.
4 Proofs of probabilistic results
4.1 The uniform case
Theorem 1.5
Let \(m\ge 0\). Then, \(\rho _m^{\otimes 2}\) contains almost all partitions of \(\left( {\begin{array}{c}m+1\\ 2\end{array}}\right) \) in the uniform measure, in which all distinct partitions are given the same probability.
Proof
Our plan is to use the semigroup property to add together smaller cases that can be proven by dominance ordering.
We use Proposition 5.4 in the \(k=2\) case, to give the following: suppose we have partitions \(\lambda _1, \lambda _2,\lambda _3,\lambda _4\) which are dominance comparable to \(\rho _{\lfloor \frac{m+1}{2}\rfloor }, \rho _{\lfloor \frac{m}{2}\rfloor },\rho _{\lfloor \frac{m}{2}\rfloor },\rho _{\lfloor \frac{m-1}{2}\rfloor }\), respectively. Repeated application of the semigroup property yields
and hence \(c(\rho _{m},\rho _{m},\lambda _1 +_{_H}\lambda _2 +_{_H}\lambda _3 +_{_H}\lambda _4)\).
It now suffices to take a \(U_n\)-typical partition \(\lambda \) and show that it can be written as
where \(\lambda _1,\) \( \lambda _2,\) \(\lambda _3,\) \(\lambda _4\) are dominance comparable to the correspondingly sized staircases.
We will do so by partitioning the columns into four sets corresponding to \(\lambda _1,\ldots ,\lambda _4\) such that each is dominance comparable to \(\rho _{\lfloor \frac{m+1}{2}\rfloor }\) or \(\rho _{\lfloor \frac{m-1}{2}\rfloor }\). We give an algorithm that works for almost all partitions. On a macroscopic scale, we essentially will split the limit shape into 4 pieces of equal area by cutting it up vertically, as depicted below. We will then use some columns of length 1 to ensure that each \(\lambda _i\) has exactly the correct total size, without interfering significantly with their overall shapes. We will denote by \(\mu _1,\ldots ,\mu _4\) the 4 straightened continuous Young diagrams formed from the limit shape in this way. A figure below depicts the decomposition (Figs. 10).
Decomposition of the uniform limit shape by column size
Here, the purple diagonal line represents the rescaled staircase partition \(\rho _{{\lfloor \frac{m}{2}\rfloor }}\), shifted right so that its corner is at the bottom of the green line (the line separating \(\mu _2\) from \(\mu _3\)). We now briefly explain why the hypotheses of Lemma 3.5 hold for each piece against a \(\frac{1}{4}\)-area \(\rho _{\infty }\). The exact equation for the curve of the limit shape boundary is
A convexity argument shows that on this curve, \(x+y\) is minimized at \(x=y=\frac{\sqrt{6}}{\pi }\log 2\). Therefore, to ensure that the purple line does not intersect the curve, we need to verify that the x-coordinate for the green line is less than \((\frac{2\sqrt{6}}{\pi }\log 2)-\frac{1}{\sqrt{2}}\approx 0.37\). Indeed, the green x-coordinate can easily be checked to be approximately 0.33, which is smaller as desired. Therefore, the boundaries of \(\rho _{\infty }\) and \(\mu _3\) intersect only once, including at the endpoints, so Lemma 3.5 ensures dominance comparability. It is clear that dominance of \(\mu _3\) implies the same for \(\mu _2, \mu _1\). For \(\mu _4\), it is easy to check that the red line meets the blue boundary curve at approximately (0.78, 0.36). Because this height is less than \(\frac{1}{\sqrt{2}}\approx 0.71\), \(\rho _{\infty }\) has larger height than \(\mu _4\). So it remains to check that the boundary curves of \(\mu _4,\rho _{\infty }\) intersect only at most 1 time. This is true because the boundary of \(\mu _4\) consists only of points (x, y) with \(x>y\), and it is easily seen that the derivative of the boundary curve lies in the interval \((-1,0)\) on this region, so it cannot intersect a line of slope -1 twice.
We will now decompose \(\lambda \) by greedily partitioning the columns into four sets corresponding to \(\lambda _1,\ldots ,\lambda _4\) as follows. We fix some small \(\varepsilon >0\) to be chosen later and freely take n to be large. Order the column lengths \({\lambda }_1^t\ge {\lambda }_2^t\ge \cdots \), and let \(n_1\) be the largest integer such that \(\sum _{i=1}^{n_1}{\lambda }_i^t\le \left( {\begin{array}{c}k+1\\ 2\end{array}}\right) \), and assign to \(\lambda _1\) the columns \({\lambda }_1^t \ldots {\lambda }_{n_1}^t\). By Lemma 3.6, the rescaled position of column \(n_1\) is, with high probability, very close to the first vertical line in the diagram. Because it is also true w.h.p. that \(\lambda \) is close to the limit shape in the metric on \(\mathscr {SY}\), it is true w.h.p that no 2 subsequent adjacent columns \(\lambda _m^t, \lambda _{m+1}^t\) \((m>n_1)\) differ by more than \(\varepsilon \sqrt{n}\). This is simply because to the right of the orange line, the limit shape graph is uniformly continuous.
Therefore, w.h.p. we may add one more column \(\lambda _m^t\) to \(\lambda _1\) so that \(0 \le \left( {\begin{array}{c}k+1\\ 2\end{array}}\right) -|\lambda _1| \le \varepsilon \sqrt{n}\), just by taking the largest column size \(\lambda _m^t\) preserving the property \(0 \le \left( {\begin{array}{c}k+1\\ 2\end{array}}\right) -|\lambda _1|\).
We similarly form \(\lambda _2,\lambda _3\) by greedily adding columns, and then (if necessary) adding one more column to give total size in the interval \([\left( {\begin{array}{c}k+1\\ 2\end{array}}\right) -i\varepsilon \sqrt{n},\left( {\begin{array}{c}k+1\\ 2\end{array}}\right) ]\). (We have a factor of \(i \in \{2,3\}\) because the fact that we used out-of-place columns for previous \(\lambda _j\) could increase the gap size between available columns for subsequent \(\lambda _i\).) We then greedily fill \(\lambda _4\) with the remaining columns which are not of size 1. Note that \(n_2\) and \(n_3\) correspond almost exactly to the vertical boundaries between \(\mu _i\), again by Lemma 3.6.
We now use the pieces of size 1 to smooth the exact sizes of \(\lambda _i\). This is possible because of the following proposition.\(\square \)
Proposition 4.1
[7, Theorem 2.1] Let \(X_1(\lambda )\) be the number of columns of size 1 contained in a partition \(\lambda \). For each \(v\ge 0\), if \(\lambda \) is a uniformly random partition of n,
Because of this proposition, by picking \(\varepsilon \) small, we have w.h.p. at least \(6\varepsilon \sqrt{n}\) columns of size 1, enough to distribute to \(\lambda _1,\lambda _2,\lambda _3\) in order to give them the correct sizes. We checked earlier that the condition for Lemma 3.5 was satisfied for each \(\mu _i\), so by also picking \(\varepsilon \) small enough so as to use Lemma 3.5, we also have that dominance is preserved when we do this, so \(\lambda _1,\lambda _2,\lambda _3\) are taken care of.
We now just add all remaining parts of size 1 to \(\lambda _4\). Each other \(\lambda _i\) is the correct total size, so having used all the columns of \(\lambda \), we see that \(\lambda _4\) is also the correct size. Because \(\mu _4\) dominates the infinite staircase \(\rho _{\infty }\), by Lemma 3.5 again, with \(\varepsilon \) sufficiently small the dominance will be preserved. (Note that because \(\lambda _4\) dominates the corresponding staircase instead of being dominated as was the case for the other \(\lambda _i\), we do not need to worry about adding too many singleton columns to \(\lambda _4\).) \(\square \)
4.2 The Plancherel case
Theorem 1.6
Let \(m\ge 1\). Then, \(\rho _m^{\otimes 2}\) contains almost all partitions of \(\left( {\begin{array}{c}m+1\\ 2\end{array}}\right) \) with respect to the Plancherel measure.
Proof of Theorem 1.6
For this proof, we assume the following technical result, which will be proven in a later section.\(\square \)
Definition 29
Let \(\beta \) be a positive real number. A partition \(\lambda \) of n is called \(\beta \)-sum flexible if it satisfies the following property: when its column lengths are sorted in increasing order \(a_1 \le \ldots a_m\), we have \(a_1=1\), and for all \(1\le k \le m\) we have \(a_k \le \left\lceil \beta \sum _{j=1}^{k} a_j \right\rceil \).
Theorem 4.2
For any \(\beta >0\), let \(P(n,\beta )\) denote the probability that a (Plancherel) random partition of n is \(\beta \)-sum flexible. Then, we have
for all \(\beta \).
To show Theorem 1.6, we use the same summation identities for staircase partitions as above. Again, for simplicity, we discuss only the \(n=2k\) case, the other case being nearly identical.
Similarly to the uniform case, we will take a \(M_n\)-typical partition \(\lambda \) and write it as
where \(\lambda _1,\) \( \lambda _2,\) \(\lambda _3\) are dominance comparable to \(\rho _k\) and \(\lambda _4\) is comparable to \(\rho _{k-1}\). Unlike in the above, we can make each piece roughly the same shape. We will do so by grouping most of the column lengths \(\lambda _1'\ge \lambda _2' \ge \cdots \) into sets of four consecutive sizes, and dividing them cyclically among \(\lambda _i\). We will use Theorem 4.2 to distribute the smallest columns, in such a way that \(|\lambda _1|=\lambda _2|=|\lambda _3|=\left( {\begin{array}{c}k+1\\ 2\end{array}}\right) \) and \(|\lambda _4|=\left( {\begin{array}{c}k\\ 2\end{array}}\right) \). Similarly to the uniform case, define \(\mu \) to be the Plancherel limit shape, but transformed by the linear map \((x,y)\rightarrow (\frac{x}{2},2y)\).
We first argue that \(\mu , \rho _{\infty }\) satisfy the hypotheses of Lemma 3.5. We have \(\ell (\rho _{\infty })=h(\rho _{\infty })=1, \ell (\mu )=\frac{1}{\sqrt{2}}, h(\mu )=2\sqrt{2}\), so it remains to check that their boundaries intersect only once off of the axes. In Russian coordinates, extend the boundary of \(\mu \) along the axes to a convex function f defined on all of \(\mathbb {R}\) by setting \(f(x)=|x|\) outside the boundary curve of \(\mu \). Since f is convex, it can only meet any line twice. The boundary of \(\rho _{\infty }\) is a line, and one intersection point is (1, 1). Therefore, the boundaries of \(\mu ,\rho _{\infty }\) intersect at most once, so they do meet the conditions of Lemma 3.5.
Fix a miniscule \(\varepsilon > 0\). We order the column lengths \(\lambda _1^t \ge \lambda _2^t \ge \cdots \). Take all columns with size at least \(\varepsilon n^{1/2}\) and add column \(\lambda _i^t\) to partition k if i and k are congruent modulo 4. Because each partition’s total size corresponds essentially to a Riemann integral of the limit shape, each partition now has size \(n(\frac{1}{4}-\delta +o(1))\), where \(\delta \) is the area of the limit shape covered by columns which are size less than \(\varepsilon \) after rescaling [1]. This means that each partial partition is smaller than the size of the corresponding \(\lambda _i\), which all have size \(n(\frac{1}{4}-o(1))\). By Theorem 4.2, we may distribute the remaining columns to give each partition the correct overall size. We claim that these remaining small parts occupy an infinitesimal area in the rescaled diagram: they fit into a square of arbitrary small side length, for \(\varepsilon \) sufficiently small. To verify this, we need that the longest row of \(\lambda \) is of size \((2+o(1))\sqrt{n}\) with high probability, i.e. the same length as predicted by the length of the limit shape. This is indeed true, see [1].
This implies that the resulting shapes are very close to \(\mu \) in the metric on \(\mathscr {SY}\), meaning that, assuming we picked a sufficiently small \(\varepsilon \) value originally, we may apply Lemma 3.5 to conclude that we have dominance.
In summary, we have decomposed a generic large partition as a horizontal sum of 4 almost equally shaped partitions, each comparable to their size of staircase via the dominance ordering. Hence, this generic large partition is a constituent of \(\rho _m^{\otimes 2}\), by the semigroup property, and so we have established Theorem 1.6. \(\square \)
5 Overview of the deterministic approach
In this section, we consider a different weakening of the tensor square conjecture:
Question
What is the smallest integer f(m) such that \(\rho _m^{\otimes f(m)}\) contains every partition of \(n=\frac{m(m+1)}{2}\)?
The conjecture is that \(f(m)=2\); we seek here to find any good upper bound on f(m). It may seem natural to attempt to use the semigroup property directly for this question; we can in fact define higher-length Kronecker coefficients via constituency in longer tensor products, and the semigroup property still holds for these longer sequences in the same way (see Appendix 10.2). However, we take a different approach, by instead allowing for additional factors of the standard representation \(\tau _n\), and then replacing these factors with factors of \(\rho _m\) to answer the above question.
5.1 Blockwise distances
The square-moving interpretation of tensoring a representation with \(\tau _n\) motivates the following definition:
Definition 30
The blockwise distance \(\varDelta (\lambda ,\mu )\) between two partitions \(\lambda ,\mu \) of n is the smallest number of single blocks that need to be moved to form \(\lambda \) from \(\mu \).
Equivalently, the blockwise distance is the smallest \(\varDelta \) such that \(\lambda \otimes \tau _n^{\otimes \varDelta }\) contains \(\mu \). To motivate our approach in this section, consider the graph of Young diagrams of size n in which \(\lambda \) and \(\mu \) are adjacent if and only if they differ by the movement of exactly 1 block. Then, \(\lambda \otimes \tau _n\) is the formal sum of \(\lambda \) (possibly many times) and all of its neighbours (once each). If we are only concerned (as we are) with which representations appear at all, we see that tensoring with \(\tau _n\) corresponds simply to “spreading out” along this graph. This leads us to another weakening of the tensor square conjecture:
Definition 31
Define H(m) to be the minimum non-negative integer \(\ell \) such that \(\rho _m^{\otimes 2}\otimes \tau _n^{\otimes \ell }\) contains all partitions of n as constituents, where \(n=\frac{m(m+1)}{2}\).
Question
How quickly does H(m) grow with m?
If H(m) is small, then partitions contained in \(\rho _m^{\otimes 2}\) are “dense” in the graph described above. In this section, we find an upper bound for the number of standard representation factors required and then translate this into a bound f(m). We also define a slightly more general distance which allows differently sized partitions to be compared.
Definition 32
The generalized blockwise distance \(\varDelta (\lambda ,\mu )\) between two partitions \(\lambda \vdash n_1,\mu \vdash n_2\) is the smallest number of single blocks that need to be added, removed, and/or moved to form \(\lambda \) from \(\mu \).
Remark
When \(\lambda ,\mu \) are partitions of the same n, the generalized distance \(\varDelta ({\lambda ,\mu })\) is the same as the regular blockwise distance.
First, we verify that horizontally adding partitions interact simply with blockwise distances.
Proposition 5.1
If \(\lambda _1,\mu _1,\lambda _2,\mu _2\) are integer partitions, then \(\varDelta (\lambda _1,\lambda _2)+\varDelta (\mu _1,\mu _2)\ge \varDelta (\lambda _1+_{_H}\mu _1,\lambda _2+_{_H}\mu _2)\).
Proof
Consider a sequence of \(d_1\) operations on the columns of \(\lambda _1\) that can be done to result in \(\lambda _2\), and consider the analogous sequence for transforming \(\mu _1\) to \(\mu _2\). Since horizontal addition simply combines the multisets of column sizes, it suffices to show that the same two sequences of moves can be performed separately on the sets of columns of \(\lambda _1+_{_H}\mu _1\) corresponding to \(\lambda _1\) and \(\mu _1\), respectively, to achieve the same transformation as before for each of the two parts.
This follows because the basic operations, when performed on the columns of \(\lambda _1+_{_H}\mu _1\) corresponding to \(\lambda _1\), do not affect those corresponding to \(\mu _1\), and vice versa; when the relative sizes of two columns would change, we can simply reorder the columns without affecting the result.\(\square \)
Note that \(\varDelta ({\lambda ,\mu })\le n-1\) for all \(\lambda ,\mu \vdash n\). As a demonstration of what using standard representations can give us, we give the following pair of weak but instructive results:
Proposition 5.2
Let \(n=\frac{m(m+1)}{2}\). If \(\lambda \vdash n\) is such that \(\lambda \) is contained in \(\tau _n^{\otimes m}\), then \(\lambda \) is contained in \(\rho _m^{\otimes 2}\).
Proof
The irreducible components of \(\tau _n^{\otimes m}\) are precisely those that correspond to partitions \(\lambda \) of n whose blockwise distance from \(1_n\) is at most m. If this blockwise distance is at most \(m-1\), then \(\lambda \), minus its top row, is contained within \(\rho _{m-1}\), and so \(\lambda \) is comparable to \(\rho _m\) in dominance order. Thus, we get \(c(\rho _m,\rho _m,\lambda )\).
If the distance is m, the only way for \(\lambda \) not to be comparable to \(\rho _m\) is if \(\lambda =(n-m,1,1,\ldots ,1)\). But in this case, we have \(c(\rho _m,\rho _m,\lambda )\) anyway by the semigroup property, because \(\lambda \) is a hook [10].\(\square \)
Proposition 5.3
Let \(n=\frac{m(m+1)}{2}\). All \(\lambda \vdash n\) are contained in \(\rho _m^{\otimes 2\lceil \frac{m+1}{2}\rceil }\).
Proof
All \(\lambda \vdash n\) are contained in \(\tau _n^{\otimes n-1}\) and thus in \(\tau _n^{\otimes m\lceil \frac{m+1}{2}\rceil }\). So for each \(\lambda \), there exist irreducible representations \(\mu _1,\ldots ,\mu _{\lceil \frac{m+1}{2}\rceil }\), each contained in \(\tau _n^{\otimes m}\), whose tensor product contains \(\lambda \). Thus, \(\lambda \) is in the tensor product of \(\lceil \frac{m+1}{2}\rceil \) irreducible representations each contained in \(\rho _m^{\otimes 2}\), and thus, \(\lambda \) is contained in \(\rho _m^{\otimes 2\lceil \frac{m+1}{2}\rceil }\) \(\square \)
Remark
This already shows that \(f(n)=O(\sqrt{n})\). As we will soon see, we can do much better.
5.2 Staircase sum identities
As seen previously, staircases can be added to form larger staircases. The most straightforward way follows and is a generalization of the identities used in the previous section (which we recover when \(k=2\)). We use the symbols \(\varSigma _{H},\varSigma _{V}\) for iterated applications of \(+_{_H},+_{_V}\).
Proposition 5.4
For any n, k, we have:
Proof
Recall Hermite’s identity, which states that for any \(x\in \mathbb R\), we have
Thus, the jth term in the vertical sum is a partition whose largest row has size
Since the k summands are all staircases with length differing by at most one, the other rows in the sum have size \(n-j-k, n-j-2k,\ldots \). Thus, the vertical sum creates a partition with row sizes \(n,n-1,\ldots ,1\), which is what we want. \(\square \)
For example, for \(k=2\), we recover the identities we used in the previous section:
As was visually demonstrated before, these identities may be understood as beginning with a square grid of staircases \(\rho _{\lfloor \frac{n+i-j}{k}\rfloor }\) and horizontally adding the rows, and then vertically adding the resulting sums. Of course, we could also first add vertically by column, and then horizontally by row.
This square grid of staircase partitions can also be added in an entirely different order to produce the same result. Instead of adding all the staircases in each row together, we can first add an i-by-i square and then add a length-i column and a length \(i+1\) row to get an \((i+1)\)-by-\((i+1)\) square. However, some slightly messy rearrangement of the pieces is needed, and the following proposition is the result.
Proposition 5.5
For any n, k, we have:
-
1.
$$\begin{aligned} \left( \rho _n+_{_H}((k-1)_{_V}\rho _{\lfloor \frac{n}{k-1}\rfloor })\right) +_{_V}\left( \mathop {\sum \nolimits _V}\limits _{i=0}^{k-1}\left( \rho _{\left\lfloor \frac{n+\lfloor \frac{n}{k-1}\rfloor -k+1+i}{k}\right\rfloor }\right) \right) =\rho _{n+\lfloor \frac{n}{k-1}\rfloor }, \end{aligned}$$
-
2.
$$\begin{aligned} \left( \rho _n+_{_H}\left( (k-1)_{_V}\rho _{\lfloor \frac{n}{k-1}\rfloor }\right) \right) +_{_V}\left( \mathop {\sum \nolimits _V}\limits _{i=0}^{k-1}\left( \rho _{\left\lfloor \frac{n+\lfloor \frac{n}{k-1}\rfloor +1+i}{k}\right\rfloor }\right) \right) =\rho _{n+\lfloor \frac{n}{k-1}\rfloor +1}. \end{aligned}$$
The proof of this proposition will be given in Sect. 6.1.
Layer decomposition
Below is a visual illustration of case 1 with \(k=4, n=7\), where the pieces combine to make a \(\rho _9\) (Fig. 11).
Using the above, we can construct a decomposition of any large staircase into a staircase of about \((\frac{i}{k})^2\) times its area and \(k^2-i^2\) staircases of about \(\frac{1}{k^2}\) times its area. This may be done by repeatedly applying Theorem 5.5.
5.3 Overview of Proof of Theorem 1.4
Here is our main result, stated again.
Theorem 1.4
For sufficiently large n, there exists \(\lambda \vdash n\) such that \(\lambda ^{\otimes 4}\) contains all partitions of n.
For this overview, we will focus on the case of a triangular number \(n=\frac{m(m+1)}{2}\), using for \(\lambda \) the staircase \(\rho _m\). The general case will augment most steps simply by adding the appropriate number of extra blocks in the form of a trivial representation. The detailed proof can be found in Sect. 6.
The primary ingredient is the following theorem.
Theorem 5.6
For all m, \(\rho _m^{\otimes 2}\otimes \tau ^{\otimes O(m)}\) contains all partitions of \(n=\left( {\begin{array}{c}m+1\\ 2\end{array}}\right) \).
Equivalently, we will show that every partition is in \(\rho _m^{\otimes 2}\otimes \tau ^{\otimes \lfloor c\sqrt{n}\rfloor }\) for an absolute constant c.
We defined earlier H(m) to be the minimum number of tensor factors of \(\tau _n\) needed so that \(\rho _m^{\otimes 2}\otimes \tau _n^{\otimes H(m)}\) contains every partition, so Theorem 5.6 states that \(H(m)=O(m)\). For convenience, we define a maximal function for the function H.
Definition 33
For \(m\ge 0\), let \(M(m)=\max \{H(1),H(2),\ldots ,H(m)\}.\)
It is clear that \(M(m)=O(m) \iff H(m)=O(m)\), and so we will show the former.
Proof Outline for Theorem 5.6
We use Proposition 5.5 to decompose \(\rho _m\) as
where up to O(1) error, we have \(x\approx \frac{3m}{4},\) \( y\approx z_i\approx \frac{m}{4}\).
Suppose that we have eight partitions \(\lambda _0\ldots \lambda _{7}\) each contained in the tensor square of one of the above staircases. Then, repeatedly combining the partitions and using the semigroup property gives us
So, we only need to show how to decompose an arbitrary partition \(\mu \) as a horizontal sum of many smaller partitions comparable to staircases, using standard representations to move a few blocks around as necessary. We will plan for all but two of these smaller partitions to be dominance comparable to the staircase. These will then be the only two smaller partitions that need additional tweaking with standard representations.
The idea is the following: we cut off a large chunk A of \(\mu \), of about \(\frac{7}{16}\) its size. The remainder \(\lambda _0\) (consisting of the larger end of the columns) is modified recursively to be contained in the tensor square of the staircase of size about \(\frac{9}{16}n\); A itself is broken into 7 pieces which can be modified to be suitable \(\lambda _i\). This breaking is done contiguously, so that columns in a piece are either all at least as tall or all at least as short as columns in a given other piece. If all columns in one of these pieces are either very tall or very short, we can conclude dominance comparability with the staircase. By further breaking down the smaller pieces, we can ensure using this criterion that most of the small parts in our decomposition are dominance comparable to the corresponding staircases. The subadditivity of blockwise distance allows us to derive a recursion for M(m) from this decomposition, and we do not have recursive terms corresponding to most of these smaller pieces. The end result is the following recurrence.
Solving this recurrence by strong induction gives
for some constant C (see Sect. 6.2 for an explicit C which works for large n). This proves that \(M(m)=O(m)\), and hence Theorem 5.6. \(\square \)
To conclude Theorem 1.4, it remains to show that for any c, for large enough n, any irreducible representation in \(\tau ^{\otimes \lfloor c\sqrt{n}\rfloor }\) is contained in \(\rho _m^{\otimes 2}\). In the next section, we explain our results in more detail and fill in this last step to complete the proof of Theorem 1.4 even in non-triangular number cases.
6 Detailed Proof of Theorem 1.4
We follow the same plan as in the proof overview, giving more detail and showing the extensions to non-triangular values of n. First, we rigorize some of our earlier work with staircase sum identities.
6.1 Staircase sum identities, revisited
Here is a result we used in the overview, which will now be proven.
Proposition 5.5
For any n, k, we have:
-
1.
$$\begin{aligned} \left( \rho _n+_{_H}\left( (k-1)_{_V}\rho _{\lfloor \frac{n}{k-1}\rfloor }\right) \right) +_{_V}\left( \mathop {\sum \nolimits _V}\limits _{i=0}^{k-1}\left( \rho _{\left\lfloor \frac{n+\lfloor \frac{n}{k-1}\rfloor -k+1+i}{k}\right\rfloor }\right) \right) =\rho _{n+\lfloor \frac{n}{k-1}\rfloor }, \end{aligned}$$
-
2.
$$\begin{aligned} \left( \rho _n+_{_H}\left( (k-1)_{_V}\rho _{\lfloor \frac{n}{k-1}\rfloor }\right) \right) +_{_V}\left( \mathop {\sum \nolimits _V}\limits _{i=0}^{k-1}\left( \rho _{\left\lfloor \frac{n+\lfloor \frac{n}{k-1}\rfloor +1+i}{k}\right\rfloor }\right) \right) =\rho _{n+\lfloor \frac{n}{k-1}\rfloor +1}. \end{aligned}$$
Proof
We simply check each equality by evaluating the left sides. We begin with 1. We have \(\rho _n=(n,n-1,\ldots 1)\). Because vertical addition is equivalent to taking the disjoint union of the row-multisets, we have \((k-1)_{_V}\rho _{\lfloor \frac{n}{k-1}\rfloor }=(\lfloor \frac{n}{k-1}\rfloor ,\lfloor \frac{n}{k-1}\rfloor ,\ldots , 1)\) where each distinct value is repeated \(k-1\) times. Therefore,
where the omitted row lengths are precisely the values \(n+\lfloor \frac{n}{k-1}\rfloor +1-jk\) for positive integral j. Again using the fact that the vertical addition is simply disjoint union of row lengths, it suffices to check that
consists of precisely these row lengths. That the largest row lengths match follows from Hermite’s identity. Because the k numbers \({\left\lfloor \frac{n+\lfloor \frac{n}{k-1}\rfloor -k+1+i}{k}\right\rfloor }\) differ pairwise by at most 1, the row lengths of
will decrease by k until reaching 0, which is exactly the correct behaviour.
The proof of 2 is identical, except now the omitted row lengths are those of the form \(n+\left\lfloor \frac{n}{k-1}\right\rfloor +1-jk\) for non-negative integers j.\(\square \)
It is easy to see that the function \(f(n)=n+\left\lfloor \frac{n}{k-1}\right\rfloor \) attains all integer values except those congruent to \(-1 \mod k\). Such values are attained by \(f(n)+1\), so Proposition 5.5 suffices to break up any staircase into smaller pieces.
We now use the above proposition to construct a decomposition of any large staircase into a staircase of about \((\frac{i}{k})^2\) times its area and \(k^2-i^2\) staircases of about \(\frac{1}{k^2}\) its area, for any fixed \(i<k\).
Definition 34
Define a k-layer decomposition of \(\rho _m\) as a decomposition of \(\rho _m\) into 2k staircases which have sizes given by the left-hand side of Eq. 1 of Proposition 5.5, where \(m=n+\left\lfloor \frac{n}{k-1}\right\rfloor \), and which sum to \(\rho _m\) in the way indicated by that equation. The piece \(\rho _n\) in this decomposition is called the core.
For \(1\le i\le k-1\), define a (k, i)-layer decomposition of \(\rho _m\) recursively as follows:
A \((k,k-1)\)-layer decomposition of \(\rho _m\) is a k-layer decomposition of \(\rho _m\).
For \(i<k-1\), a (k, i)-layer decomposition of \(\rho _m\) is the result of taking a \((k,i+1)\)-layer decomposition of \(\rho _m\), and further decomposing its core through a \((k-1,i)\)-layer decomposition.
Thus, a (k, i)-layer decomposition is a decomposition of \(\rho _m\) into \(k^2-i^2+1\) smaller staircases. We extend the definition of the core to these decompositions and introduce a related term for the remaining pieces.
Definition 35
We call the large part of a (k, i)-layer decomposition of \(\rho _m\) the core and the other \(k^2-i^2\) parts the flakes.
It is clear that, for fixed (i, k), the flakes formed differ by only O(1) in length.
In fact, as long as \(2i\le k\), by using Proposition 5.5 intelligently, we can ensure that they differ by at most 1.
Definition 36
We call a (k, i)-layer decomposition of \(\rho _m\) into parts where all flakes pairwise differ in length by at most 1 a smooth layer decomposition.
Proposition 6.1
For any (m, k, i) with \(2i\le k\), there is a smooth (k, i)-layer decomposition of \(\rho _m\).
Proof
We first examine based on the value of j to see which flake lengths can arise in a (k, 1) decomposition.
If \(0\le j\le k-2\), then we may use part 1. of Proposition 5.5. The core length is \(n=t(k-1)+j\), which means the flake lengths are \(\left\lfloor \frac{n}{k-1}\right\rfloor =t\) and \({\left\lfloor \frac{n+\left\lfloor \frac{n}{k-1}\right\rfloor -k+1+i}{k}\right\rfloor }=\left\lfloor \frac{t(k-1)+j+t-k+1+i}{k}\right\rfloor =\left\lfloor \frac{(t-1)(k)+j+1+i}{k}\right\rfloor \). Because \(i\le k-1\) we have \((t-1)k+j+1+i<(t+1)k\), so these numbers range over the set \(\{t-1,t\}\).
If \(1\le j\le k-1\), then we may use part 2. of Proposition 5.5. The core length is \(n=t(k-1)+j-1\), which makes the flake lengths \(\left\lfloor \frac{n}{k-1}\right\rfloor =t\) and \({\left\lfloor \frac{n+\left\lfloor \frac{n}{k-1}\right\rfloor +1+i}{k}\right\rfloor }=\left\lfloor \frac{t(k-1)+j-1+t+1+i}{k}\right\rfloor =t+\left\lfloor \frac{j+i}{k}\right\rfloor \). This clearly ranges over \(\{t,t+1\}\).
Now, assume first that \(j<k-i\). Then, we may use 1. of Proposition 5.5 i times, having after \(\ell \) iterations a core of length \(t(k-\ell )+j\) and all flakes of lengths in \(\{t-1,t\}\). Because \(j<k-i\), we always have \(j\le k-\ell -2\) for \(\ell \le k-1\), so we can complete the i iterations in this way.
If \(j\ge k-i\), then as \(2i\le k\) we have \(j\ge i\). Then, we may instead use only part 2. of the proposition, which after \(\ell \) iterations leaves a core of length \(t(k-\ell )+j-\ell \). Because \(j\ge i\), this is strictly greater than \(t(k-\ell )\) for all \(\ell < i\), so we can again run this process to completion, with all flakes of length in \(\{t,t+1\}\). In either case, we are done.\(\square \)
6.2 Proof of Theorem 5.6
We now prove Theorem 5.6, restated with an explicit asymptotic constant.
Theorem 5.6
(With explicit constant) For all m, \(\rho _m^{\otimes 2}\otimes \tau ^{\otimes (1184m+O(1))}\) contains all partitions of \(n=\left( {\begin{array}{c}m+1\\ 2\end{array}}\right) \).
Proof
We use Proposition 5.5 to write \(\rho _m\) as a (k, 1) decomposition
where up to O(1) error, we have \(x\approx \frac{(k-1)m}{k},\) \( y\approx z_i\approx \frac{m}{k}\).
Now, suppose that we have partitions \(\lambda _0\ldots \lambda _{2k-1}\) such that
for \(1 \le j \le k-1\) and
for \(0\le i \le k-1\).
Then, repeated application of the semigroup property implies
which in turn imply
and so
Thus, we only need to show how to decompose an arbitrary partition as a horizontal sum of many smaller partitions.\(\square \)
Lemma 6.2
Suppose \(\lambda \vdash n\), where \(n=\frac{k(k+1)}{2}\), and the columns of \(\lambda \) have sizes \(c_1\ge c_2\ge \cdots \ge c_l\). Then, if either \(c_l\ge k\) or \(c_1\le \left\lfloor \frac{k}{2}\right\rfloor +1\), we have \(c(\rho _k,\rho _k,\lambda )\).
Proof
First, consider the case where \(c_l\ge k\). Then, for \(1\le j \le l\), we have \(\sum _{i=1}^j c_i\ge kj\ge k+(k-1)+\cdots +(k-(j-1))\), while for \(j>l\), \(\sum _{i=1}^j c_i\ge n\). So, \(\lambda \) is clearly dominance comparable to the staircase.
Now, consider the case where \(c_1\le \left\lfloor \frac{k}{2}\right\rfloor +1\). Now for any \(j<k\), the leftmost j columns of \(\rho _k\) have average size \(\frac{k+(k-j+1)}{2}\ge \frac{k+2}{2}\), which is at least the average size of the first j columns of \(\lambda \). For \(j\ge k\), the sizes of the leftmost j columns of \(\rho _k\) sum to n. So, \(\lambda \) and \(\rho _k\) are again comparable in the dominance order.
Thus, in either case, \(c(\rho _k,\rho _k,\lambda )\) follows by Theorem 2.6.\(\square \)
We now introduce a lemma which allows us to break up a partition \(\mu \) with bounded height into partitions contained in staircase tensor squares. The reader may wish to note that only the first part of the lemma is needed to conclude that \(O(\sqrt{n})\) standard representations suffice to give every representation, by taking, e.g. \((k,i)=(7,5)\) instead of \(((k,i)=(4,3)\). However, using the second part results in a better constant factor. Recall that we defined \(M(m)=\max \{H(1),H(2),\ldots ,H(m)\}\), where H(m) was the minimal non-negative integer \(\ell \) such that \(\rho _m^{\otimes 2}\otimes \tau _n^{\otimes \ell }\) contains all partitions of n as constituents.
Lemma 6.3
Consider a partition \(\mu \) and staircases \(\rho _{s_1}, \ldots , \rho _{s_r}\) with \(s_i \in \{b-1,b\}\) for all i. Assume that the height of the largest column \(c_1\) satisfies \(c_1\le C\) and also \(0\le (\sum _{i} |\rho _{s_i}|)-|\mu | \le C\). Then, there exists a partition \(\widehat{\mu }\) such that \(c\left( \mathop {\sum \nolimits _H}\nolimits _{i=1}^r \rho _{s_i},\mathop {\sum \nolimits _H}\nolimits _{i=1}^r \rho _{s_i},\widehat{\mu }\right) \) and also the generalized blockwise distance \(\varDelta =\varDelta (\widehat{\mu },\mu )\) between \(\widehat{\mu }\) and \(\mu \) satisfies
-
(1)
\(\varDelta \le (4r-3)C+M(b)\) and
-
(2)
\(\varDelta \le (4r+9)C+M(\lceil \frac{b}{2}\rceil )\)
Proof
We break up \(\mu \) by its column lengths \(c_1\ge c_2\cdots \ge c_h\). We will construct partitions \(\zeta _1\ldots \zeta _{r}\) which horizontally sum to \(\widehat{\mu } \approx \mu \). We begin by constructing partitions \(\zeta _i^*\), and then adjusting each \(\zeta _i^*\) to form \(\zeta _i\).
To form \(\zeta _i^*\), we preliminarily use the greedy algorithm to assign to \(\zeta _1^*\) as many columns from \(\mu \) as possible subject to \(|\zeta _1^*|\le |\rho _{s_1}|\) starting from the smallest column \(c_h\) and then continue similarly with \(\zeta _2^*\) and so on through \(\zeta _r^*\). Note that some columns of \(\mu \) may be included in none of the \(\zeta _i^*\). The assumptions \(c_1\le C\) and \(0\le \sum _{i} |\rho _{s_i}|-|\mu | \le C\) guarantee that for each i, we have
Now, we modify each \(\zeta _i^*\) based on the height condition of Lemma 6.2. For each i, set \(X_i\) to be the height of the smallest column of \(\zeta _i\) and \(Y_i\) to be the height of the largest. Clearly, we have \(X_1\le Y_1\le X_2 \ldots \le X_r \le Y_r\). We leave alone those \(\zeta _i^*\) with \(Y_i \le \lceil \frac{b}{2} \rceil \) - such \(\zeta _i\) can easily be modified to satisfy dominance by Lemma 6.2 as we will see later.
We have some remaining set S of i such that \(Y_i > \lceil \frac{b}{2} \rceil \). Now, because we have \(X_{i+1}\ge Y_i\), at most 1 value of \(i\in S\) satisfies \(X_i \le \lceil \frac{b}{2}\rceil \), namely only the minimal value \(i_0\) of S. Therefore, for all \(i \in S\backslash \{i_0\}\), we have \(X_i > \lceil \frac{b}{2}\rceil \).
For each \(i\in S\backslash \{i_0\}\), we break \(\rho _{s_i}\) into a sum of 4 smaller staircases \(\rho _{s_{i,1}}\ldots \rho _{s_{i,4}}\) by setting \(k=2\) in Proposition 5.4. We also use the same greedy algorithm as before to extract from \(\zeta _i^*\) four partitions \(\zeta ^*_{i,1}\ldots \zeta ^*_{i,4}\) such that \(|\rho _{s_{i,j}}|-C\le |\zeta ^*_{i,j}|\le |\rho _{s_{i,j}}|\) and the \(\zeta ^*_{i,j}\) use distinct columns of \(\zeta ^*_i\).
Because \(s_i\le b\), we have \(s_{i,j} \le \lceil \frac{b}{2} \rceil \). For all \(i\in S\backslash \{i+0\}\), \(X_i > \lceil \frac{b}{2}\rceil \), and the smallest column in any \(\zeta ^*_{i,j}\) is certainly at least as large as \(X_i\). This means that the \(\zeta ^*_{i,j}\) now satisfy the other size condition in Lemma 6.2; by breaking down our partitions, we have preserved the “tallness” of the \(\zeta ^*_i\) in the \(\zeta ^*_{i,j}\) while decreasing the total size, making them sufficiently “relatively tall” to apply Lemma 6.2.
Now, we finish part (1). We will add squares to the small staircases \(\zeta ^*_i\), \(\zeta ^*_{i,j}\) while preserving the respective height conditions of Lemma 6.2. Let R be the set of partitions consisting of \(\zeta _i\) for \(i\not \in S\) and \(\zeta _{i,j}\) for \(i\in S\backslash \{i_0\}\). We know that for each partition in R, we can bring its total size to the size of the corresponding staircase \(\rho _{s_i}\) or \(\rho _{s_{i,j}}\) by adding at most C squares.
We consider \(\mu \) as the disjoint union of column-length multisets of the partitions in R, \(\zeta ^*_{i_0}\), and the remaining leftover columns. We make block moves to bring each partition \(\zeta ^*_i\) or \(\zeta ^*_{i,j}\) in R to be of size \(s_i\) or \(s_{i,j}\), while preserving the respective condition from Lemma 6.2. Note that because we have \(|\zeta ^*_i|\le |\rho _{s_i}|\) and \(|\zeta ^*_{i,j}| \le |\rho _{s_{i,j}}|\), we can achieve the first goal with all block moves being the addition of a new block.
We show that we can add new blocks freely without destroying our height conditions. For \(i \not \in S\), we need to avoid increasing the height of \(\zeta ^*_i\), and we do this by adding additional blocks only as new columns of length 1. The resulting modifications of \(\zeta ^*_i\) are our desired \(\zeta ^*_i\). For \(i\in S\backslash \{i_0\}\), we need to avoid decreasing the minimum height of the columns of \(\zeta ^*_{i,j}\), and we do this by adding blocks only as rows of length 1, or equivalently increasing the longest column length. The resulting modifications of \(\zeta ^*_{i,j}\) are our \(\zeta _{i,j}\).
We clearly have \(|R|\le 4r-4\). Recall that we are consider \(\mu \) as a disjoint union of the partitions of R, as well as \(\zeta ^*_{i_0}\) and some leftovers columns. We claim that by the above procedure, we can perform at most \((4r-4)C\) block moves on \(\mu \) to modify all partitions \(\zeta ^*_i,\zeta ^*_{i,j}\) in R into \(\zeta _i,\zeta _{i,j}\) without affecting \(\zeta ^*_{i_0}\). This is simple: we repeatedly move a block from the leftovers columns onto \(\zeta ^*_i\) or \(\zeta ^*_{i,j}\) in the manner described above. If the leftover column runs out, we instead create a brand new block to add to the partition being modified, so this procedure carries out the desired function.
Now, we modify \(\zeta ^*_{i_0}\). We can add at most C blocks from the remainder of the leftover columns or out of nowhere to \(\zeta ^*_{i_0}\). This forms \(\zeta ^{**}_{i_0}\) with \(|\zeta ^{**}_{i_0}|= |\rho _{s_{i_0}}|\). By definition of M, we can then modify at most \(M(s_{i_0})\) blocks in order to reach a partition \(\zeta _{i_0}\) appearing in \(\rho _{s_{i_0}}^{\otimes 2}\). Because we assumed
if we used a leftover column block whenever possible, we are now completely out of leftover column blocks, which means that our block moves have resulted in only the partitions \(\zeta _i,\zeta _{i_0},\zeta _{i,j}\).
In all, we have made at most \((4r-4)+1\) sets of at most C block moves each, as well as an additional \(M(s_{i_0})\le M(b)\). We now let \(\widehat{\mu }\) the partition formed from the horizontal sum of the resulting \(\zeta _i\), \(\zeta _{i,j}\), and \(\zeta _{i_0}\). Because we assumed \(0\le \sum _{i} |\rho _{s_i}|-|\mu |\), we must have consumed all of the leftover squares, so \(\widehat{\mu }\) is precisely a horizontal sum of partitions comparable to the staircases \(\rho _{s_i}\). Using the semigroup property first to combine the modifications of \(\zeta _{i,j}\) and then to combine all the \(\zeta _i\), we have that \(\widehat{\mu }\) is a constituent in the horizontal sum
We made at most \((4r-3)C+M(b)\) block moves in transforming \(\mu \) into \(\widehat{\mu }\). Thus, part (1) is proved.
The modification to prove part (2) is simple: assuming \(X_{i_0} \le \lceil \frac{b}{2}\rceil \), we go one step further and split \(\rho _{s_{i_0}}\) into 4 staircases, and split \(\zeta _{i_0}\) as with the other \(\zeta _i\). We now repeat the argument above just to these 4 parts \(\zeta _{i_0,j}\): some parts have a small maximum height, and of those that do not, at most 1 fails to have a sufficiently small maximum height after another level of subdivision. The modification of the expression in the conclusion results from the subdivision of the exception case \(i_0\) into smaller parts: there are additional 12 pieces which need C block moves each, but on the other hand, the size of the exceptional piece is halved.
We now get on with the main proof of Theorem 5.6. Fix an arbitrary partition \(\mu \vdash n\).
Recall from Proposition 5.5 that we may write \(\rho _m\) as
where up to O(1) error, we have \(x\approx \frac{(k-1)m}{k}, y\approx z_i\approx \frac{m}{k}\). By Proposition 6.1, we may take \(y, z_i\) pairwise differing by at most 1. The idea is to split \(\mu \) into a large part corresponding to \(\rho _x\) and smaller parts corresponding to the other terms and then make some minor modifications to each part via block moves and apply the semigroup property. We will set \(k=4\), so \(x\approx \frac{3m}{4}\) and \( y\approx z_i\approx \frac{m}{4}\)
We first split \(\mu \) according to its Durfee square. Specifically, we may partition the blocks of \(\mu \) into 3 pieces: the Durfee square D, the blocks \(T_1\) to the right of D, and the blocks \(T_2\) below D. WLOG, we may assume \(|T_1| \ge |T_2|\), as otherwise we could conjugate \(\mu \) and start over; since the staircases are symmetric, this does not affect anything. Let D have side length d.
If the columns of \(\mu \) are \(c_1\ge c_2\ge \cdots \ge c_l\), consider the smallest j such that \(\sum _{i=1}^j c_i\ge |\rho _x|\). Since \(|T_1|\ge |T_2|\), we have that \(\sum _{i=1}^{\left\lfloor \frac{d}{2}\right\rfloor } c_i \le \frac{|D|}{2} + |T_2| \le \frac{1}{2}n<|\rho _x|\approx \frac{9n}{16}\). So \(j> \frac{d}{2}\), and thus \(n\ge jc_j > \frac{d}{2} c_j\), yielding \(c_j < \frac{2n}{d}\).
Furthermore, if \(d^2=|D|\le \frac{1}{8}n\), then \(j> d\), so \(c_j\le d\le \frac{1}{2\sqrt{2}}\sqrt{n}\) by definition of the Durfee square. So either \(c_j\le \frac{1}{2\sqrt{2}}\sqrt{n}\), or \(d>\frac{1}{2\sqrt{2}}\sqrt{n}\) and \(c_j< \frac{2n}{d}<4\sqrt{2n}.\) So, \(c_j<4\sqrt{2n}\) in either case.
We now split off the region of the partition corresponding to the first j columns. Let the portion split off be \(\lambda _0\), and let the remaining portion of the partition be A. By definition of j, we have \(0\le \left( 3|\rho _y|+\sum _{i=0}^{3}|\rho _{z_i}| \right) -|A| \le c_j \le 4\sqrt{2n}\).
To finish, we need to split A into smaller staircase-sized partitions in such a way that makes the total number of block movements needed small. To this end, we apply Lemma 6.3 with \(r=2k-1\), where \(s_1=\cdots =s_{k-1}=y\) and \(s_{k+i}=z_i\) for \(0\le i\le k-1\). Here, we set \(k=4\). Since the largest column involved has size \(\mu _1'<4\sqrt{2n}\), we can set \(C=4\sqrt{2n}\) and get
for some \(\widehat{\mu }\) such that \(\varDelta (A,\widehat{\mu })\le 37C+M(\lceil \frac{y}{2}\rceil ).\) Since \(|A|\le |\widehat{\mu }|\), \(\mu =\lambda _0+_{_H}A\) can be transformed into \(\lambda _0^*+_{_H}\widehat{\mu }\) by at most \(37C+M(\lceil \frac{y}{2}\rceil )\) block moves. Because blockwise distance between equally sized partitions is simply the number of blocks which need to be moved to go from one to the other, this means that
contains our original partition \(\mu \), where \(\lambda _0^*\) is some partition of size \(|\rho _x|\).
By definition, there is a partition \(\lambda _0^{**}\) of size \(|\rho _x|\) such that \(c(\rho _x,\rho _x,\lambda _0^{**})\) and \(\varDelta (\lambda _0^{*},\lambda _0^{**})\le M(x)\). So, by subadditivity of blockwise distance, as well as the layer decomposition for \(\rho _m\), we have
as \(C=4\sqrt{2n}=4m+O(1)\). It is easy to see by strong induction that this recurrence gives
\(\square \)
6.3 Generalization to all n
We now carry out the comparatively simple procedure of extending Theorem 5.6 to non-triangular values of n. Since staircases can only have triangular sizes, we make a simple modification to the partitions \(\rho _m\) to give them the correct size.
Definition 37
The irregular staircase \(\xi _n\) of size \(n=\frac{m(m+1)}{2}+k\), where \(0\le k\le m\), is the partition \(\xi _n=\rho _m +_{_H}1_k\).
So, an irregular staircase is a staircase with a trivial representation horizontally added to give it the desired total size. Note that (m, k) are uniquely determined by n in the above.
Corollary 6.4
For all n, \(\xi _n^{\otimes 2}\otimes \tau ^{\otimes (1185+o(1))\sqrt{2n}}\) contains all partitions of n.
Proof
We use Theorem 5.6. Given n, take the largest m such that \(\left( {\begin{array}{c}m+1\\ 2\end{array}}\right) \le n\). Let \(k=n-\left( {\begin{array}{c}m+1\\ 2\end{array}}\right) \), so \(k\le m\). Then, \(\xi _n = \rho _{m} +_{_H}1_{k}\). We show that an arbitrary partition \(\mu \) of n may be transformed into a partition \(\widehat{\mu }\) of \(n-k\) horizontally summed with \(1_k\), using m block movements. As \(k\le m\), it suffices to transform \(\mu \) into a partition with at least m parts of length 1. But this is trivial: repeatedly remove a block from a column of length at least 2, and move the block to create a column of length 1. If we can make m such moves, we are done. If not, when we cannot make any more moves, the current partition is a horizontal strip, and we are again done.
Now that this is shown, we have that \(\mu \) is contained in \((\widehat{\mu } +_{_H}1_{k}) \otimes \tau _n^{\otimes m}\). By Theorem 5.6, we have that \(\widehat{\mu }\) is contained in \(\rho _m^{\otimes 2}\otimes \tau _{n-k} ^{\otimes (1184+o(1))m}\). Thus, there exists \(\nu \) such that \(c(\rho _m,\rho _m,\nu )\) with blockwise distance \(\varDelta (\nu ,\widehat{\mu }) \le (1184+o(1))m\). The semigroup property gives
We have \(\varDelta (\nu +1_{k},\widehat{\mu }+1_{k}) \le (1184+o(1))m\) by Proposition 5.1. Since also \(\varDelta (\widehat{\mu }+1_{k},\mu )\le m\), we conclude that \(\varDelta (\mu ,\nu +1_{k})\le (1185+o(1))m\). Since \(\mu \) was arbitrary, we have shown that
contains all partitions of n.
From \(\sqrt{2n}=m+O(1)\), we conclude the desired result. \(\square \)
6.4 Replacing the standard representations
Lemma 6.5
For any \(\ell >0\), for large \(n=\frac{m(m+1)}{2}\), if \(\lambda \) is an irreducible representation of \(S_n\) such that \(\lambda \) is a component of \(\tau _n^{\otimes \lfloor \ell m\rfloor }\), then \(\lambda \) is a component of \(\rho _m^{\otimes 2}\).
Proof
The irreducible components of \(\tau _n^{\otimes \lfloor \ell m\rfloor }\) are precisely those that correspond to partitions \(\lambda \) of n whose blockwise distance from \(1_n\) is at most \(\lfloor \ell m\rfloor \).
We use Proposition 5.5 with \(k=\ell _1 m^{\frac{1}{2}}\) for \(\ell _1\) depending on \(\ell \). This decomposes \(\rho _m\) into a large piece of side length about \(m-\frac{m^{\frac{1}{2}}}{\ell _1}\), as well as about \(2k-1\) small pieces of side length \(\frac{m^{\frac{1}{2}}}{\ell _1}\) and area \(\frac{m}{2(\ell _1)^2}\).
Each column of \(\lambda \) has size at most \(\ell m+1\), and there are at least \(n-2\ell m\) columns of height 1. So, as long as \(\frac{1}{\ell _1^2}>2\ell \), we can use each of the \(2k-1\) small staircase pieces to cover, in their tensor square, a hook consisting of one of the \(2k-1\) tallest columns along with part of the first row (chosen to give the correct total size). By an easy induction using the semigroup property (see [10]), hooks are contained in the tensor square of staircases.
The remaining columns are necessarily very short: letting \(c_1\ge c_2\ge \cdots \) be the column lengths, we have \((2k)(c_{2k})\le \sum _{i=1}^{2k} c_i\le \ell m+2k=O(m).\) Therefore, the remaining columns are all of size \(O(m^{\frac{1}{2}})\). By Lemma 6.2, we conclude that this remaining large part of \(\lambda \) is dominance comparable to the corresponding-size staircase. The semigroup property now yields the lemma. \(\square \)
We can also extend Lemma 6.5 to irregular staircases.
Lemma 6.6
For any \(\ell >0\), for large enough n, if \(\lambda \) is an irreducible representation of \(S_n\) such that \(\lambda \) is a component of \(\tau _n^{\otimes \lfloor \ell \sqrt{n}\rfloor }\), then \(\lambda \) is a component of \(\xi _n^{\otimes 2}\), the tensor square of the irregular staircase.
Proof
The irreducible components of \(\tau _n^{\otimes \lfloor \ell \sqrt{n}\rfloor }\) are precisely those that correspond to partitions \(\lambda \) of n whose blockwise distance from \(1_n\) is at most \(\lfloor \ell \sqrt{n}\rfloor \). So, there are at least \(n-2\ell \sqrt{n}\) columns of height 1. Again take the largest m such that \(\left( {\begin{array}{c}m+1\\ 2\end{array}}\right) \le n\), and let \(k=n-\left( {\begin{array}{c}m+1\\ 2\end{array}}\right) \). For large enough n, we can remove k columns of size 1 and leave a partition \(\lambda _0\) of \(n_0=\left( {\begin{array}{c}m+1\\ 2\end{array}}\right) \) that has distance at most \(\ell \sqrt{n}\le (1.1)\ell \sqrt{n_0}\) from the trivial representation of size \(n_0\). By Lemma 6.5, for large enough n, all such \(\lambda \) are contained in \(\rho _m^{\otimes 2}\), and so by the semigroup property, after adding the trivial representation back, we must have \(\xi _n^{\otimes 2}\) which contains \(\lambda \).\(\square \)
We can finally prove Theorem 1.4 on tensor fourth powers, with an explicit choice \(\lambda =\xi _n\).
Theorem 1.4
For sufficiently large n, the tensor fourth power \(\xi _n^{\otimes 4}\) contains all partitions of n.
Proof
Corollary 6.4 implies that for sufficiently large n, \(\xi _n^{\otimes 2}\otimes \tau _n^{\otimes \lfloor 1186\sqrt{2n}\rfloor }\) contains all partitions of n. So for any \(\mu \vdash n\), \(\xi _n^{\otimes 2}\otimes \nu \) contains \(\mu \) for some \(\nu \) contained in \(\tau _n^{\otimes \lfloor 1186\sqrt{2n}\rfloor }\). Lemma 6.6 thus implies that \(\mu \) is contained in \(\xi _n^{\otimes 4}\), as claimed. \(\square \)
7 Concluding remarks
We have shown that staircase tensor squares \(\rho _m^{\otimes 2}\) contain almost all partitions in 2 natural probability distributions and that there are partitions \(\lambda \vdash n\) for all large n such that \(\lambda ^{\otimes 4}\) contains all partitions of n.
Remark
The argument used to show that tensor 4th powers contain every representation proceeds by showing first that every partition \(\lambda \) is near another partition contained in the tensor square \(\rho ^{\otimes 2}\), and then shows that the nearness can be encompassed in another \(\rho ^{\otimes 2}\) factor. To prove the full tensor square conjecture using our semigroup methods, one would need to remove all of the standard representations, which means each semigroup property application would need to be exactly correct. As a result, improving the exponent from 4 to 2 seems more difficult. Intuitively, our value 4 is really \( 2\lceil 1+\varepsilon \rceil \).
Remark
Our results in this paper focused on the staircase partitions, but many of the arguments can be adapted for partitions which can be similarly broken down into staircase pieces. For instance, the caret partition \(\gamma _k\) mentioned in the introduction may be expressed as \(\gamma _k=(\rho _{2k}+_{_H}\rho _{k-1})+_{_V}\rho _{k-1}\). By breaking down the \(\rho _{2k}\) into 4 pieces, we have broken \(\gamma _k\) into 6 approximately equal staircases. As a result, the proof of Theorem 1.6 on Plancherel-random partitions applies to \(\gamma _k^{\otimes 2}\) as well.
Remark
Intuitively, the rectangular Young diagrams should be the most difficult to deal with using the semigroup property: if \(\lambda \) is rectangular and \(\lambda =\lambda _1+_{_H}\lambda _2\), both \(\lambda _1\) and \(\lambda _2\) must be rectangular. Therefore, we have very little freedom in applying the semigroup property. It is, however, easy to show that rectangles are constituents of the tensor cubes \(\rho _m^{\otimes 3}\); see Appendix 10.2 for details. Further exploration could yield more insight into how difficult general partitions are to fit into a tensor cube.
Remark
The question of whether the semigroup property combined with combinatorial arguments involving dominance and symmetry suffices to prove the full tensor square conjecture remains open. Regardless, checking for Kronecker coefficient positivity inductively using the semigroup property seems much faster than directly computing Kronecker coefficients. Of course, the semigroup property may fail to detect positive Kronecker coefficients.
Remark
We have, using a computer to implement the semigroup property in conjunction with Theorem 2.6 on dominance ordering, verified the Saxl conjecture up to \(\rho _9\). These two facts suffice for all cases except the 6 by 6 square in \(\rho _8^{\otimes 2}\). This case follows from the semigroup property using the additional fact that \(c(\lambda ,\lambda ,\lambda )\) holds for every symmetric partition \(\lambda \) [2], but our construction seems rather ad hoc. We explain it here using some helpful visuals. In the diagram (below), each colour corresponds to an application of the semigroup property, beginning with the red squares (which satisfy constituency by the theorem mentioned above). Thus, the 3 depicted partitions yield a positive Kronecker coefficient.
We now add the rectangle to itself and add the other 2 partitions to each other, giving \(c(\rho _8,\rho _8,\mu )\) for \(\mu \) the 6 by 6 square (Fig. 12).
A triple with positive Kronecker coefficient
References
Baik, J., Deift, P., Johansson, K.: On the distribution of the length of the longest increasing subsequence of random permutations. J. Am. Math. Soc. 12(4), 1119–1178 (1999)
Bessenrodt, C., Behns, C.: On the Durfee size of Kronecker products of characters of the symmetric group and its double covers. J. Algebra 280(1), 132–144 (2004)
Billingsley, P.: Probability and Measure, vol. 939. Wiley, New York (2012)
Borodin, A., Okounkov, A., Olshanski, G.: Asymptotics of Plancherel measures for symmetric groups. J. Am. Math. Soc. 3, 481–5150 (2000). (electronic)
Bürgisser, P., Ikenmeyer, C.: The complexity of computing Kronecker coefficients. In: 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), Discrete Mathematics & Theoretical Computer Science Proceedings, AJ. Assoc. Discrete Mathematics & Theoretical Computer Science, Nancy, pp. 357–368 (2008)
Christandl, M., Harrow, A.W., Mitchison, G.: Nonzero Kronecker coefficients and what they tell us about spectra. Commun. Math. Phys. 270(3), 575–585 (2007)
Fristedt, B.: The structure of random partitions of large integers. Trans. Am. Math. Soc. 337(2), 703–735 (1993)
Fulman, J.: Stein’s method and Plancherel measure of the symmetric group. Trans. Am. Math. Soc. 357(2), 555–570 (2005)
Fulton, W., Harris, J.: Representation Theory, vol. 129. Springer, Berlin (1991)
Ikenmeyer, C.: The Saxl conjecture and the dominance order. Discret. Math. 338(11), 1970–1975 (2015)
Krasikov, I.: Uniform bounds for Bessel functions. J. Appl. Anal. 12(1), 83–91 (2006)
Pak, I., Panova, G., Vallejo, E.: Kronecker Products, Characters, Partitions, and the Tensor Square Conjectures. arXiv preprint arXiv:1304.0738 (2013)
Regev, A.: Kronecker multiplicities in the \((k,\ell )\) hook are polynomially bounded. Isr. J. Math. 200(1), 39–48 (2014)
Stanley, R.P.: Enumerative Combinatorics, vol. 2, vol. 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge (1999). With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin
Vershik, A.M.: Statistical mechanics of combinatorial partitions, and their limit configurations. Funktsional. Anal. i Prilozhen. 30(2), 19–39 (1996)
Veršik, A.M., Kerov, S.V.: Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux. Dokl. Akad. Nauk SSSR 233(6), 1024–1027 (1977)
Acknowledgments
The authors thank their MIT SPUR 2015 mentor, Dongkwan Kim, for his valuable feedback and advice. They also thank Nathan Harman for suggesting this problem, and professors Alexei Borodin, David Jerison, and Ankur Moitra for their helpful input and advice. They thank Mitchell Lee for help with editing, and finally thank the MIT SPUR program for the opportunity to conduct this research project.
Author information
Authors and Affiliations
Corresponding author
Appendices
Appendix 1: Technical lemma on \(\beta \)-sum flexibility
1.1 Overview of the proof
We conclude by proving the key technical result used in the proof of Theorem 1.6. This result is restated below:
Theorem 4.2
For any \(\beta >0\), let \(P(n,\beta )\) denote the probability that a (Plancherel) random partition of n is \(\beta \)-sum flexible. Then we have
for all \(\beta \).
We will estimate the typical value for the maximum height among the smallest \(n^{\alpha }\) columns, for \(\frac{1}{6} < \alpha \le \frac{1}{2}\). These bounds will enable us to conclude Theorem 4.2. We first recall from, e.g. [4] that, for a random partition of n, the number \(\lambda _1-\lambda _2\) of columns of size 1 is \(\Theta (n^{1/6})\) with high probability. In fact, \(\frac{\lambda _1-\lambda _2}{n^{1/6}}\) converges weakly to a non-trivial limiting density.
This result tells us that for any \(\varepsilon \) there exists \(\delta \) such that, for large n, we will have at least \(\delta n^{1/6}\) parts of size 1 with probability at least \(1-\varepsilon \). This means that the condition in Theorem 4.2 is safe for all columns of size at most \(\delta n^{1/6}\). If the sum of all these columns is of size \(\Theta ({n^{\alpha }})\), the condition in Theorem 4.2 is now safe for all columns with at most \(c n^{\alpha }\) size, for some c. Our plan is to “bootstrap” in this manner up to \(\Theta ({n^{1/2}})\). If we can achieve the condition up to this point, we will have proved (4), because for pieces of size \(\Theta ({n^{1/2}})\) the limit shape easily implies Theorem 4.2.
We actually estimate a closely related quantity, for which explicit formulae exist. For a partition \(\lambda \), we follow [4] in denoting by \(D(\lambda )\) the set \(\{\lambda _i - i\}\). We will also work with poissonized Plancherel measure \(M^{\theta }\) instead of ordinary Plancherel measure \(M_n\). At the end, we will depoissonize to recover information about the measures \(M_n\). The use of Poissonized Plancherel measure is that useful exact formulae describe the behaviour of a random partition.
Definition 38
For \(\theta \in \mathbb {R}^+\), the Poissonized Plancherel measure \(M^{\theta }\) is a probability distribution over all partitions \(\lambda \), with
Conceptually, we pick a \(M^{\theta }\) partition by first taking n to be Poisson with mean \(\theta \), and then picking a Plancherel random \(\lambda \vdash n\).
The formulas to follow will allow us to estimate the mean and variance \(\mu _{\theta , w}, \sigma _{\theta ,w}^2\) of \(T(\lambda ,w)=|D(\lambda ) \cap \mathbb {Z}_{\ge w}|\), where \(\lambda \) is taken from poissonized Plancherel measure with mean \(\theta \). Because the set \(D(\lambda )\) corresponds to the vertical border edges of the Young diagram, this approximately gives the height of the wth smallest column. By setting \(w=2\sqrt{n}-Kn^{\alpha }\), knowledge of these quantities will allow us to understand roughly the value of the maximum-size column among the first \(\Theta (n^{\alpha })\).
We now list the formulas and bounds we will use for these computations.
1.2 Formulas for poissonized Plancherel measure
Definition 39
The Bessel function of the first kind \(J_{\nu }\) is defined as
Definition 40
The Airy function Ai is defined as
Definition 41
For a partition \(\lambda =(\lambda _1,\lambda _2,\ldots \), define \(D(\lambda )\) to be the set \(\{\lambda _i-i\}\).
Definition 42
Define the function \(\mathbf J (x,y;\theta )\) as
Lemma 8.1
[4, Theorem 2, Proposition 2.9] Let \(\lambda \) be chosen according to \(M^{\theta }\). Then for any finite \(X=\{x_1,x_2\ldots x_s\} \subseteq \mathbb {Z}\), the probability that \(D(\lambda ) \supseteq X\) is
Lemma 8.2
[11] \(J_{\nu }(x) \le x^{-1/3}\) and \(J_{\nu }(x) \le \nu ^{-1/3}\).
Lemma 8.3
[4, Lemma 4.4] For \(x \in \mathbb {R}\) we have
where additionally the implicit constant in \(O(n^{-1/6})\) is uniform for x in any compact set.
Lemma 8.4
[4, Proposition 4.3] For fixed \(a \in \mathbb {R}\),
Specializing to \(a=0\) gives
Lemma 8.5
Lemma 8.6
[4, Lemma 4.5] There exist \(C_1, C_2, C_3, \varepsilon > 0\) such that for sufficiently large n, for any \(A>0\), \(s > 0\), we have
for all \(r\gg 0\).
Setting \(r=2n^{\frac{1}{2}}\) and \(A=2^{-\frac{1}{3}}\) in Lemma 8.6, squaring, and adjusting the values \(C_i\) as needed, we have the following for all s, for some fixed values \(C_i, \varepsilon \), and large enough n.
Lemma 8.7
There exist \(C_1, C_2, C_3, \varepsilon > 0\) such that for sufficiently large n, for any \(s > 0\), we have
1.3 Proof of Theorem 4.2
We proceed as described in Sect. 8.1. First, direct application of Lemma 8.1 in the case \(|X|=1\), combined with linearity of expectation, yields that
where the last equality is a simple sum rearrangement. Now let \(\theta =n, w=2n^{1/2}-Kn^{\alpha }, \frac{1}{6} < \alpha \le \frac{1}{2}\), as alluded to before. We will now establish the bounds on this expectation.
Lemma 8.8
\(\mu _{n,(2n^{1/2}-Kn^{\alpha })}=\varOmega \left( n^{\alpha -\frac{1}{6}}\right) \).
Proof
Taking n sufficiently large, we have that
Because the Airy function has no zeros in the interval \([-1,1]\) and is continuous, the uniformity in Lemma 8.3 implies that each squared term in this last sum is of size \(\Theta (n^{-1/3})\). Since we have \(\Theta (n^{1/6})\) terms in the sum, we conclude that for large n,
\(\square \)
Lemma 8.9
\(\mu _{n,(2n^{1/2}-Kn^{\alpha })}=O\left( n^{2\alpha -\frac{1}{3}}\right) \). Further, given fixed \(\alpha \), the implicit constant in \(O(n^{2\alpha -\frac{1}{3}})\) is \(O(K^2)\)
Proof
Using Lemma 8.5, we see that
Expanding out the definition of \(\mathbf J (y,y,n)\) we have that
where the last equality follows from another simple regrouping of terms. By Lemma 8.2, for any value of \(\ell \) we have \(J_{\ell +s+1}(2n^{1/2}) \le n^{-1/6}\). Thus, we have that the first sum is of appropriate size:
To establish Lemma 8.9, it remains to show that the latter term
is of appropriate size. First, note that from Lemma 8.2 again,
where the last equality follows from the assumption \(\alpha > \frac{1}{6}\). We are left with upper-bounding the sum
Now, using Lemma 8.7, take suitable constants \(C_1, C_2, C_3, \varepsilon \), and let n be large enough, so that we have for all s
We claim that the above sum is also \(O(n^{\alpha -\frac{1}{6}})\), or equivalently that
For the first of these 2 sums, we have
For the second, we have
Note that only the first part of our bounding affects the eventual constant in the \(O(n^{2\alpha -\frac{1}{3}})\) of the lemma statement, because the other terms are \(O(n^{\alpha -\frac{1}{6}})=o(n^{2\alpha -\frac{1}{3}})\). So, combining these separate bounds, we have established the lemma.\(\square \)
Now we verify that \(T(n,2n^{1/2}-Kn^{\alpha })\) is concentrated around its mean.
Lemma 8.10
If \(\lambda \) is distributed according to poissonized \(M^n\), then \(T=T(\lambda ,2n^{1/2}-Kn^{\alpha })\) is concentrated near its mean \(\mu =\mu _{n,(2n^{1/2}-Kn^{\alpha })}\), in the sense that for all \(\varepsilon > 0\),
Proof
To show the lemma, we estimate the variance \(\sigma ^2\) of \(T(\lambda ,2n^{1/2}-Kn^{\alpha })\). Perhaps surprisingly, this is very easy. We will show that
which suffices by the Chebyshev inequality, since \(\mu \) grows to infinity with n by Lemma 8.8. To show this, we note the following general fact (Lemma 8.11): if \(X=\sum _{j=0}^{\infty }x_j\) is a finite-expectation sum of Bernoulli (0 or 1) random variables with pairwise non-positive covariances, then \(\sigma _X^2 \le \mu _X\).
In our case, this lemma easily implies the result: when \(\lambda \) is distributed according to poissonized \(M^n\) we have
where the indicator variables I are 0 or 1 according to the truth value of their argument. We need only check that \({{\mathrm{Cov}}}(I(x \in D(\lambda )),I(y \in D(\lambda ))) \le 0\) for \(x \ne y\). We have
Using Lemma 8.1, this is
since J(x, y; n) is symmetric in x and y. Therefore, the covariances are all negative, so it only remains to verify Lemma 8.11 \(\square \)
Lemma 8.11
\(X=\sum _{j=0}^{\infty }x_j\) is a finite-expectation sum of Bernoulli variables with pairwise non-positive covariances, then \(\sigma _X^2 \le \mu _X\)
Proof
To prove this, we simply compute \(\sigma _X^2=\mathbb {E}[X^2]-\mathbb {E}[X]^2\). The condition on covariances is equivalent to \(\mathbb {E}[x_ix_j] \le \mathbb {E}[x_i]\mathbb {E}[x_j]\) for all \(i \ne j\). Because \(\mathbb {E}[x]=\sum _{i=0}^{\infty } \mathbb {E}[x_i]\) is finite, its square is finite, so we have
Because \(\mathbb {E}[x_ix_j] \le \mathbb {E}[x_i]\mathbb {E}[x_j]\), we find that
\(\square \)
We now know that the bounds in lemmas 8.8, 8.9 apply to almost all partitions \(\lambda \), not only “average” partitions: for some constants \(B_1(K,\alpha ), B_2(K,\alpha )\) where \(B_2=O(K^2)\) for fixed \(\alpha \), if \(\lambda \) is distributed according to \(M^n\) we have
with probability \(1-o(1)\) as \(n \rightarrow \infty \). We now depoissonize the result. The key observation, as described in [8], is that simple Plancherel measures \(M_n\) may be viewed as samplings at time n of a growth process on partitions, in which we begin with an empty partition and add additional blocks randomly at each step. It is clear that adding a block to \(\lambda \) cannot decrease the value of \(T(\lambda ,w)\). So because we can embed these Plancherel measures into a growth process, the expectations are monotone: for \(\ell <n\) we have
and for \(\ell > n\) we have
We claim that, for n large, the probability of a Poisson variable with mean n to be less than n converges to \(\frac{1}{2}\). Indeed, this is an immediate result of the Central Limit Theorem for independent, identically distributed random variables applied to the Poisson random variable with mean 1. Therefore,
and similarly for the upper bound; a low probability of deviation for poissonized Plancherel measure directly implies the same bound (up to a factor of 2) for standard Plancherel measure. So, we have
with probability \(1-o(1)\) for \(\lambda \) distributed according to \(M_n\) measure.
Now we establish the connection between \(T(\lambda ,2n^{1/2}-Kn^{\alpha })\) and the column sizes. It will be valuable to visualize a Young diagram (in English coordinates) as a block-walk beginning from the far-right of the top border line, with coordinates (n, 0). In this model, every down-move corresponds to a value \((\lambda _i-i)\) and every left-move corresponds to the end of a column. With this in mind, \(T(\lambda ,2n^{1/2}-Kn^{\alpha })\) is essentially the height of the largest column so far after \(n-2n^{1/2}+Kn^{\alpha }\) moves from the starting point. The idea is that our upper bound lets us move far out without fearing that our largest column is too big. Our lower bound tells us that many of the columns we have formed are large, implying that the sum of their sizes is large. The only caveat is that if we are moving vertically, T measures the current vertical distance moved, but may not exactly measure a column height; we may be in the middle of a column. However, we will circumvent this issue by using multiple values of K simultaneously, and showing that in between there must be many horizontal moves.
Pick an \(\varepsilon > 0\). We will give a bootstrapping argument that gives result (4) for parameter \(\beta \) with probability \(1-6\varepsilon \). First, because the number of size-1 columns \(\lambda _1-\lambda _2\) satisfies \(\frac{\lambda _1-\lambda _2}{n^{1/6}}\) converges in distribution to a limiting density, there exists \(\delta _1\) such that (for large n) with probability at least \(1-\varepsilon \), there are at least \(\frac{\delta _1}{\beta }n^{1/6}\) parts of size 1. Using lemmas 8.8 and 8.9, since \(\frac{1}{4}-\frac{1}{6}=\frac{1}{12}\) and \(\frac{2}{4}-\frac{1}{3}=\frac{1}{6}\), we may pick \(\delta _2,\) and then \( \delta _3\), such that for large n, with probability at least \(1-\varepsilon \),
and
(for the second inequality, we use the fact that the constant factor in Lemma 8.9 is \(O(K^2)\)). Now, for large n, we have \(\delta _2n^{1/4} -\delta _1n^{\frac{1}{6}} \ge \frac{\delta _2}{2}n^{1/4}\). This implies that \(D(\lambda )\) cannot contain more than \(\frac{\delta _2}{2}n^{1/4}\) of the interval of integers \([2n^{1/2}-2\delta _2n^{1/4}, 2n^{1/2}-\delta _2n^{1/4}]\) as this would violate the latter inequality above. In view of our block-walking model, this is equivalent to at least \(\frac{\delta _2}{2}n^{1/4}\) horizontal move being made in between the steps \(n-2n^{1/2}+\delta _2n^{1/4}, n-2n^{1/2}+2\delta _2n^{1/4}\) meaning that at least \(\frac{\delta _2}{2}n^{1/4}\) columns in this range have height at least \(\delta _3n^{\frac{1}{12}}\) (this lower bound on the height comes from the first inequality above). Because the largest column among these is smaller than \(\delta _1n^{\frac{1}{6}}\), the condition in result (4) holds for all columns up to size \(\delta _1n^{\frac{1}{6}}\). Therefore, by bootstrapping, it holds for all columns with size at most \(\beta \) times the sum of their sizes, or at most
Now we repeat the argument once more. Again using Lemma 8.9, we pick \(\delta _5\) such that with probability \(1-\varepsilon \),
and
The first is possible because the constant in Lemma 8.9 is \(O(K^2)\), implying that it is o(K) for K small. Given \(\delta _5\) we can then pick \(\delta _6\) such that with probability \(1-\varepsilon \),
The first inequality above implies that of the \(\delta _5n^{1/3}\) block moves from step \(n-2n^{1/2}+\delta _5n^{1/3}\) to step \(n-2n^{1/2}+2\delta _5n^{1/3}\), we may make at most \(\frac{\delta _5}{2}n^{1/3}\) vertical moves. Hence, we make at least \(\frac{\delta _5}{2}n^{1/3}\) horizontal moves in this span. By the definition of \(\delta _6\), we make a column of size at least \(\delta _6n^{\frac{1}{6}}\) each time, giving a total column size sum of \(\frac{\delta _5\delta _6}{2}n^{1/2}\).
Now we are almost done. Our bootstrapping has shown Theorem 4.2 for columns of size at most \(\frac{\beta \delta _5\delta _6}{2}=\delta _7n^{1/2}\) with probability at least \(1-4\varepsilon \). Bootstrapping once more, we can now sum up all the column lengths of size at most \(\delta _7n^{1/2}\). At scale \(\Theta (n^{1/2})\), we can simply apply the limit shape theorem to conclude that for almost all partitions, the sum of such column lengths is \(\Theta (n)\), a constant fraction of the total size, because we are collecting a positive-area amount of the limit shape. Because almost all partitions have all columns of size \(O(\sqrt{n})\), we have bootstrapped to completion with error probability \(6\varepsilon \) and so the result is proved.
Appendix 2: Generalization of dominance result
We extensively used Theorem 2.6 stating that if \(\rho _m,\lambda \) are dominance comparable, then \(c(\rho _m,\rho _m,\lambda )\). We present a generalization.
Theorem 9.1
For partitions \(\mu ,\) \(\nu \vdash n\), if \(\mu \) has distinct row lengths and \(\nu \succeq \mu \), then \(c(\mu ,\mu ,\nu )\).
This is strictly more general than Theorem 2.6 because in the case when \(\mu =\rho _m\) we have \(c(\mu ,\mu ,\nu )\) for all \(\nu \succeq \mu \). Since \(\mu =\mu '\), conjugating gives \(c(\mu ,\mu ,\nu ')\) as well, and so we have recovered both cases of Theorem 2.6.
Proof
The proof of this generalization requires only slight modification of the proof of the original result in [10]. We quote from there the following definition.\(\square \)
Definition 43
Let \(d=|\lambda |=|\mu |=|\nu |\). A Young hypergraph H of type \((\lambda ,\mu ,\nu )\), is a hypergraph with d vertices such that
-
1.
The are three layers of hyperedges \(E_{\lambda },E_{\mu },E_{\nu }\).
-
2.
Each of \(E_{\lambda },E_{\mu },E_{\nu }\) contains each vertex in exactly 1 hyperedge.
-
3.
There is a bijection between the vertices of H and the boxes of \(\lambda \) such that 2 vertices lie in a common hyperedge of \(E_{\lambda }\) iff the corresponding boxes in \(\lambda \) lie in the same column. Analogously for \(E_{\mu }\) and \(\mu \) and for \(E_{\nu }\) and \(\nu \).
Given a Young hypergraph of type \((\lambda ,\mu ,\nu )\), we consider the ways to label its vertices with positive integers. In particular, we have the following definitions.
Definition 44
We call a labelling of the vertex set of a Young hypergraph of type \((\lambda ,\mu ,\nu )\) \(\lambda \)-permuting if for each hyperedge \(e_{\lambda }\) of \(\lambda \) with \(|e_{\lambda }|=k\), the labels of the vertices of \(e_{\lambda }\) are a permutation of \(\{1,2,\ldots ,k\}\). We define \(\mu \)-permuting and \(\nu \)-permuting analogously.
Definition 45
We call a labelling of the vertex set of a Young hypergraph of type \((\lambda ,\mu ,\nu )\) \(\lambda \)-distinct if for each hyperedge \(e_{\lambda }\) of \(\lambda \) with \(|e_{\lambda }|=k\), the labels of the vertices of \(e_{\lambda }\) consist of distinct numbers. We define \(\mu \)-distinct and \(\nu \)-distinct analogously.
Definition 46
We call a labelling of the vertex set of a \((\lambda ,\mu ,\nu )\) Young hypergraph H perfect if it is \(\lambda \)-permuting, \(\mu \)-permuting, and \(\nu \)-distinct.
Then the finish of the proof of [10][2.1] (see Section 5) amounts to the following lemma.
Lemma 9.2
If there exists a Young hypergraph such that there is exactly 1 perfect labelling of its vertices then \(c(\lambda ,\mu ,\nu )\) holds.
The proof in [10] uses as Young hypergraphs for \(\rho _m\) the rows and columns of the Ferrers diagram of \(\rho _m\), which works because \(\rho _m\) is symmetric. We now adapt this to an arbitrary \(\mu \) with distinct row lengths; for any \(\nu \succeq \mu \) we show there exists a perfect Young hypergraph of type \((\mu ,\mu ,\nu )\). We use the Ferrers diagram for \(\mu \) as the vertex set. For the first hypergraph \(H_1\) corresponding to \(\mu \), we simply take the columns of \(\mu \) as the hyperedges. Note that in English coordinates this amounts to, for each hyperedge, greedily taking the left-most vertex in each available row. For our second hypergraph \(H_2\) corresponding to \(\mu \) we greedily take vertices from the right of each row instead. For example, when \(\mu =\rho _m\) this amounts to taking the diagonals as hyperedges. It is easy to see that \(H_2\) is also a hypergraph of type \(\mu \). We claim that \(H_1\) and \(H_2\) already limit the possible vertex labellings to a unique one, namely the labelling which assigns to each vertex its row number.
Lemma 9.3
There is only one vertex labelling of the Ferrers diagram of \(\mu \) which is \(\mu \)-permuting with respect to both \(H_1\) and \(H_2\). This labelling assigns to each vertex its row number.
Proof
We first make an easy observation. For any vertex v of our hypergraph, the hyperedge of \(H_2\) containing v also contains a vertex in each higher row, all of which are strictly to the right of v. This is clear because the rows of \(\mu \) have distinct lengths.
Now we inductively show that any such labelling must just be the row numbering. We induct on columns, starting from the furthest right. Clearly the rightmost column’s unique vertex is labelled 1, because it is contained in a size 1 hyperedge of \(H_1\).
For each subsequent column, assume that all columns to the right are labelled by row numbers. We do a further induction within the column, starting from the bottom vertex. Call the column under consideration C, and say its vertices are \(v_1\) in row 1, and so on to \(v_k\) in row k. For some vertex \(v_i\) in C, assume that \(v_j\) is labelled j for all \(j>i\); we show \(v_i\) is labelled as i.
To do so, note that by our initial observation, \(v_i\) must be labelled at least i; its hyperedge in \(H_2\) contains labels from 1 to \((i-1)\) already. However, its hyperedge in \(H_1\) is simply C, which already contains all labels greater than i. Therefore the only choice for \(v_i\) is to be labelled i.
This completes the induction. Clearly the described labelling indeed satisfies the given conditions, so the lemma is proved.\(\square \)
Now the combination of the above lemmas implies that if we can find a perfect \((\mu ,\mu ,\nu )\) Young hypergraph for the above vertex labelling extending \(H_1, H_2\) above, then we have \(c(\mu ,\mu ,\nu )\). In fact, we can do so for precisely those \(\nu \) which dominate \(\mu \). It is clear that to find a \(E_{\nu }\) hypergraph which yields a perfect Young hypergraph, it is equivalent to find a filling of \(\nu \) with content \(\mu \) such that each column has distinct entries. (By such a filling of \(\nu \) with content \(\mu \) we mean a labelling of the boxes of \(\nu \) such that the number of k labels is the size \(\mu _k\) of the kth row of \(\mu \).) By [10][4.1], the existence of such a filling is equivalent to \(\nu \succeq \mu \), so the proof of Theorem 9.1 is complete. \(\square \)
Appendix 3: The generalized semigroup property and tensor cubes
1.1 The semigroup property for many partitions
We first generalize \(c(\cdot ,\cdot ,\cdot )\) to longer sequences of representations.
Definition 47
For k a positive integer let
denote the assertion that \(\lambda _1\) is a constituent of \(\lambda _2\otimes \lambda _3\otimes \ldots \lambda _k.\)
As in the \(k=3\) case, c is symmetric because it simply asserts the positivity of
We now show that the semigroup property still applies for longer sequences using induction.
Lemma 10.1
If \(c(\lambda _1, \ldots \lambda _k)\) and \(c(\mu _1,\ldots \mu _k)\) then also \(c(\lambda _1+_{_H}\mu _1, \ldots , \lambda _k +_{_H}\mu _k).\)
Proof
First, the result is trivially true for \(k\le 2\) since \(c(\lambda _1)=1 \iff \lambda _1\) is trivial and \(c(\lambda _1,\lambda _2) \iff \lambda _1=\lambda _2\). For \(k\ge 3\) we induct from base case of 2.4. So take \(k>3\) and assume the result for \(k-1\).
Because \(c(\lambda _1, \ldots \lambda _k)\) there exists a partition \(\alpha \) such that \(c(\lambda _1,\lambda _2,\ldots \lambda _{(k-2)},\alpha )\) and \(c(\lambda _{(k-1)},\lambda _k,\alpha )\). Similarly there exists \(\beta \) such that \(c(\mu _1,\ldots , \mu _{(k-2)},\beta )\) and \(c(\mu _{(k-1)},\mu _k,\beta )\). We now conclude using the inductive hypothesis that
and
Together these imply \(c(\lambda _1+_{_H}\mu _1, \ldots , \lambda _k +_{_H}\mu _k)\) as desired. \(\square \)
As in the \(k=3\) case, we may vertically add any even number of partitions in applying the semigroup property: this is because conjugating an even number of the partitions does not change the truth of \(c(\lambda _1,\ldots \lambda _k)\).
1.2 Rectangles appear in \(\rho _m^{\otimes 3}\)
As mentioned in the remarks, rectangles are difficult to control using the semigroup property because they can only be broken up into smaller rectangles. This suggests that rectangles should be the hardest case for the Saxl conjecture. In this section, we show that despite this, rectangles appear in the tensor cube of the staircase. In fact, the proof is a fairly simple induction.
Definition 48
The rectangle partition R(a, b) is the rectangular Young diagram \((a,a,\ldots a)\) with b rows.
Theorem 10.2
Any rectangular partition \(\lambda =R(a,b)\) of size \(\left( {\begin{array}{c}m+1\\ 2\end{array}}\right) \) is a constituent in the tensor cube \(\rho _m^{\otimes 3}\). Equivalently, if \(ab=\left( {\begin{array}{c}m+1\\ 2\end{array}}\right) \) then \(c(\rho _m,\rho _m,\rho _m,R(a,b))\).
Proof
We induct on m. Assume WLOG that \(a\ge b\). If \(a\ge m\) then \(b \le \frac{m+1}{2}\) and by Lemma 6.2, \(\lambda \) and \(\rho _m\) are dominance comparable. Thus, the result follows in this case.
Thus, we may assume that \(\frac{m+1}{2}<a<m\). Then we have that \((2a-m)\) and \( (2m-a-1)\) are positive. We prove some simple lemmas. \(\square \)
Lemma 10.3
\(b+2a-2m-1\ge 0\) and \(a(b+2a-m-1)=|\rho _{2a-m-1}|\).
Proof
\(0\le \frac{(2a-m)(2a-m-1)}{2}=\frac{m^2+m}{2}+2a^2-2am-a=ab+2a^2-2am-a=a(b+2a-2m-1)\). Because \(a\ge 0\), \(b+2a-2m-1\ge 0\) follows.\(\square \)
Lemma 10.4
If \(\mu =R(2a-m,2m-a-1)\) then
Proof
In fact this holds for any \(\mu \) at all. We have
\(\square \)
Lemma 10.5
Proof
This follows from the inductive hypothesis because the total number of blocks in the rectangle and staircases are clearly equal. \(\square \)
Lemma 10.6
Proof
This follows from the inductive hypothesis and Lemma 10.3.\(\square \)
Now note that
while
This latter identity is a rewriting of the geometrically obvious
Theorem 10.1 applied to these lemmas and identities gives the result; because 4 is even, it is permissible to vertically add all 4 partitions when using the semigroup property. Geometrically, we are simply combining shapes as below (Fig. 13).
A geometric proof that rectangles are contained in \(\rho _m^{\otimes 3}\)
Rights and permissions
About this article
Cite this article
Luo, S., Sellke, M. The Saxl conjecture for fourth powers via the semigroup property. J Algebr Comb 45, 33–80 (2017). https://doi.org/10.1007/s10801-016-0700-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10801-016-0700-z