# Estimating deep Littlewood-Richardson Coefficients

Hariharan Narayanan*

Dep. of Statistics and Dep. of Mathematics, University of Washington, USA

**Abstract:** Littlewood Richardson coefficients are structure constants appearing in the representation theory of the general linear groups ($GL_n$). The main results of this paper are:

1. A strongly polynomial randomized approximation scheme for Littlewood-Richardson coefficients corresponding to indices sufficiently far from the boundary of the Littlewood Richardson cone.

2. A proof of approximate log-concavity of the above mentioned class of Littlewood-Richardson coefficients.

**Résumé:** Coefficients de Littlewood Richardson sont des constantes de structure apparaissant dans la théorie de la représentation des groupes linéaires généraux ($GL_n$). Les principaux résultats de cette étude sont les suivants:

1. Un schéma d'approximation polynomiale randomisée fortement pour des coefficients de Littlewood-Richardson correspondant aux indices suffisamment loin de la limite du cône Littlewood Richardson.

2. Une preuve de l'approximatif log-concavité de la classe de coefficients de Littlewood-Richardson mentionné ci-dessus.

**Keywords:** Convex polytopes, Littlewood-Richardson coefficients, Log-concavity

## 1 Introduction

Littlewood Richardson coefficients are structure constants appearing in the representation theory of the general linear groups ($GL_n$). They are ubiquitous in mathematics, appearing in representation theory, algebraic combinatorics, and the study of tilings. They appear in physics in the context of the fine structure of atomic spectra since Wigner [22]. They count the number of tilings using squares and triangles of certain domains [18]. They play a role in Geometric Complexity Theory, which seeks to separate complexity classes such as $P$ and $NP$ by associating group-theoretic varieties to them, and then proving the non-existence of injective morphisms from one to the other by displaying representation theoretic obstructions [13, 14]. Thus, computing or estimating Littlewood-Richardson coefficients is important in several areas of science. Results for testing the positivity of a Littlewood-Richardson coefficient may be found in [15, 1]. For the case where the Lie group has a fixed rank, efficient (i. e. polynomial time) computation is possible based on Barvinok's algorithm (see "LATTE" [4]), or by using vector partition functions

<footnote>*Email: harin@uw.edu</footnote>
(see [3]). The degree of the polynomial in the runtime depends on the rank. Unfortunately Littlewood-Richardson coefficients are #P-complete (see [16]), and so in the case of variable rank, under the widely held complexity theoretic belief that $P \neq NP$, they cannot be computed exactly in polynomial time.

We are thus lead to the question of efficient approximation:

**Question 1** Is there an algorithm which takes as input the labels $\lambda, \mu, \nu$ of a Littlewood-Richardson coefficient $c_{\lambda\mu}^{\nu}$, and produces in polynomial time an $1 \pm \epsilon$ approximation with probability more than $1 - \delta$?

We do not settle the above question. However we do provide an algorithm that works on “most” instances, in a certain precise sense given by Theorem 4.

**Definition 1.1** We say that an algorithm for estimating a quantity $f(x)$, where $x \in \mathbb{Q}^n$ runs in randomized strongly polynomial time, if the number of “standard” operations that it uses depends polynomially on $n$, but is independent of the bit-length of those rational numbers. We require that there be a universal constant $C$ such that the algorithm output a random rational number $\hat{f}(x)$ with the property that

$$ \mathbb{P}\left[\left[\frac{\hat{f}(x)}{f(x)} \in (1 - C\epsilon, 1 + C\epsilon)\right] > 1 - C\delta\right]. $$

We allow a polynomial dependence in $n$, $\epsilon^{-1}$ and the negative logarithm $-\log \delta$ but not the bitlength of $x$. Our set of standard operations consists of additions, subtractions, multiplications, divisions, comparisons and taking square-roots. We allow the use of random numbers whose bitlength depends on the bitlength of the input, provided the operations done on them are standard.

While Okounkov’s question on the log-concavity of Littlewood-Richardson coefficients in [21] has been answered in the negative by [2], we show a form of approximate log-concavity does hold among a subset of the coefficients.

Our approach was influenced by a result of Kannan and Vempala, who show in [7] that the number of integer points in an $n$-dimensional polytope with $r$-faces containing a Euclidean ball of radius $O(n\sqrt{\log r})$ is within a constant factor of the volume. We prove a slightly stronger result (getting rid of the $\sqrt{\log r}$) applicable to the “hive polytopes” associated with Littlewood-Richardson coefficients from scratch. Even if we were to make an “off-the-shelf” application of the Kannan-Vempala result, we would still need to prove that a large class of hive polytopes contain large balls, requiring most of the material of this paper.

## 1.1 Group Representations

Suppose $V$ is a complex vector space and $G$ and $GL(V)$ are respectively a group and the group of automorphisms of $V$, then given a homomorphism $\rho: G \to GL(V)$, we call $V$ a representation of $G$. If no non-trivial proper subspace of $V$ is mapped to itself by all $g \in G$, $V$ is said to be irreducible. Littlewood-Richardson coefficients appear in the representation theory of the general linear group $GL_n(\mathbb{C})$. Suppose $V_\lambda$, $V_\mu$ and $V_\nu$ are irreducible representations of $GL_n(\mathbb{C})$. The Littlewood-Richardson coefficient $c_{\lambda\mu}^{\nu}$ is the multiplicity of $V_\nu$ in $V_\lambda \otimes V_\mu$.

$$ V_{\lambda} \otimes V_{\mu} = \bigoplus_{\nu} V_{\nu}^{c_{\lambda\mu}^{\nu}}. \qquad (1.1) $$
<figure><img src="image_1.png" /><figcaption>Fig. 1: LRC and LRC + ($\Delta$, $\Delta$, $\Delta'$)</figcaption></figure>

## 1.2 Littlewood-Richardson Cone

Given a symmetric non-negative definite matrix $X$, let $eig(X)$ denote the eigenvalues of $X$ listed in non-increasing order. The Littlewood-Richardson cone (or LRC) is defined as the cone of $3$-tuples $(eig(U), eig(V), eig(W))$, where $U, V, W$ are symmetric positive definite and $U + V = W$.

Knutson and Tao proved the following in [10].

**Theorem 2** The Littlewood-Richardson coefficient $c_{\lambda\mu}^{\nu}$ is greater than 0 if and only if $(\lambda, \mu, \nu)$ is an integer point in the Littlewood-Richardson cone.

In the remainder of this paper, $C, C_1, \dots$ will denote sufficiently large absolute constants.

Let

$$ \Delta = 2(n^3, n^3 - n^2, \dots, n^3 - kn^2, \dots, n^2), $$

$$ \Delta' = (3n^3 + n^2, 3n^3 - n^2, \dots, 3n^3 - (2k-1)n^2, \dots, n^3 + 3n^2). $$

For $n^2\epsilon^{-1} \in \mathbb{N}$, let $\Delta_{\epsilon} = (\frac{2}{\epsilon}) (n^3, n^3 - n^2, \dots, n^2)$, and $\Delta'_{\epsilon} = (\frac{1}{\epsilon}) (3n^3 + n^2, 3n^3 - n^2, \dots, n^3 + 3n^2)$.

Note that if a point in the Littlewood-Richardson cone is sufficiently far from the boundary then it lies in $LRC + (\Delta, \Delta, \Delta')$ (See Figure 1.2).

**Theorem 3** If $(\lambda, \mu, \nu) \in (\Delta, \Delta, \Delta') + LRC$, then $c_{\lambda\mu}^{\nu}$ can be approximated in randomized strongly polynomial time.

**Theorem 4** There is an absolute constant $C$ such that for $n > C$, and $\gamma > Cn^5$, there is a randomized strongly polynomial time algorithm for approximating a $1 - C(\frac{n^5}{\gamma})$ fraction of all $c_{\lambda\mu}^{\nu}$ corresponding to integer points in

$$ LRC \cap \{\|(\lambda, \mu, \nu)\|_1 \le \gamma\}. $$

In particular, as $\gamma$ tends to infinity, the fraction of all $c_{\lambda\mu}^{\nu}$ corresponding to integer points in

$$ LRC \cap \{\|(\lambda, \mu, \nu)\|_1 \le \gamma\} $$

that can be approximated, tends to 1.

Theorem 4 is shown by proving (in Lemma 12 of [17]) that the fraction of all $c_{\lambda\mu}^{\nu}$ corresponding to integer points in

$$ ((\Delta, \Delta, \Delta') + LRC) \cap \{\|(\lambda, \mu, \nu)\|_1 \le \gamma\} $$
<figure><img src="image_2.png" /><figcaption>Fig. 2: Hive model for LR coefficients</figcaption></figure>

in LRC ∩ {‖(λ, μ, ν)‖₁ ≤ γ} is at least 1 − C(n^5/γ).

The following result shows that a form of approximate log-concavity holds among the coefficients corresponding to integer points in (1/ε)(Δ, Δ, Δ') + LRC.

**Theorem 5** Suppose $n > C$ and each of $(\lambda, \mu, \nu)$, $(\hat{\lambda}, \hat{\mu}, \hat{\nu})$ and $(\bar{\lambda}, \bar{\mu}, \bar{\nu})$ corresponds to a Littlewood-Richardson coefficient and is in $(1/\epsilon)(\Delta, \Delta, \Delta') + \text{LRC}$ for some $\epsilon > 0$. Suppose $\theta(\lambda, \mu, \nu) + (1 - \theta)(\bar{\lambda}, \bar{\mu}, \bar{\nu}) = (\lambda, \bar{\mu}, \bar{\nu})$, where $\theta \in (0, 1)$ is some arbitrary real number in the interval. Then

$$ \log(c_{\lambda\mu}^{\nu}) + C\epsilon \geq \theta \log(c_{\lambda\hat{\mu}}^{\hat{\nu}}) + (1-\theta) \log(c_{\lambda\bar{\mu}}^{\bar{\nu}}). $$

In what follows, we refer to Littlewood-Richardson coefficients with indices in LRC + (Δ, Δ, Δ') as deep Littlewood-Richardson coefficients. We remark that since there exists a polynomial time algorithm for testing membership in the LRC (see [15, 11]), there also exists a polynomial time algorithm for testing membership in LRC + (Δ, Δ, Δ').

# 2 Preliminaries

## 2.1 Hive model and rhombus inequalities for Littlewood-Richardson coefficients

Let $\lambda, \mu, \nu$ be vectors in $\mathbb{Z}^n$ whose entries are non-increasing non-negative integers. In all subsequent appearances, this will be assumed of $\lambda, \mu$ and $\nu$. Let the sum of the entries of a vector $\alpha$ be denoted $|\alpha|$. Further, let $|\lambda| + |\mu| = |\nu|$. Take an equilateral triangle $\tau_n$ of side $n$. Tessellate it with unit equilateral triangles. Assign boundary values to $\tau_n$ as in Figure 1; Clockwise, assign the values 0, $\lambda_1$, $\lambda_1 + \lambda_2$, ..., $|\lambda|$, $|\lambda| + \mu_1$, ..., $|\lambda| + |\mu|$. Then anticlockwise, on the horizontal side, assign 0, $\nu_1$, $\nu_1 + \nu_2$, ..., $|\nu|$.

Knutson and Tao defined this hive model for Littlewood-Richardson coefficients in [9]. They proved that the Littlewood-Richardson coefficient $c_{\lambda\mu}^{\nu}$ is given by the number of ways of assigning integer values to the interior nodes of the triangle, such that the piecewise linear extension to the interior of $\tau_n$ is a concave function $f$ from $\tau_n$ to $\mathbb{R}$. Another way of stating this condition is that for every rhombus such as that in Figure 2, if the values taken at the nodes are $w, x, y, z$ where $y$ and $w$ correspond to 120° angles,
then $y + w \ge x + z$. Let $L$ denote the unit triangular lattice that subdivides $\tau_n$. We refer to any map from $\tau_n \cap L$ to $\mathbb{Z}$ that satisfies the rhombus inequalities as a *hive*.

**Definition 2.1** Let $P_{\lambda\mu}^{\nu}$ be a subset of $\mathbb{R}^{\binom{n}{2}}$. Let the canonical basis correspond to the set of interior nodes in the corresponding hive. (see Figure 2). Let $P_{\lambda\mu}^{\nu}$ denote the hive polytope corresponding to $(\lambda, \mu, \nu)$ defined by the above inequalities, one for every unit rhombus.

### 3 Proof of Theorem 3

<figure><img src="image_3.png" /></figure>

The number of points in $P_{\lambda\mu}^{\nu} \cap \mathbb{Z}^{\binom{n}{2}}$ is equal to the volume of the set

$$ \zeta_{\lambda\mu}^{\nu} := \left\{ x \mid \inf_{y \in P_{\lambda\mu}^{\nu} \cap \mathbb{Z}^{\binom{n}{2}}} \|x - y\|_{\infty} < \frac{1}{2} \right\}. \qquad (3.1) $$

Let $P_{\lambda\mu}^{\nu}$ be described as

$$ Ax - b_{\lambda\mu}^{\nu} \le \vec{0}, \qquad (3.2) $$

where the rows of $A$ correspond to rhombus inequalities.

We make the following observation.

**Observation 1** Each row of $A$ has at most 4 non-zero entries. Each of these entries equals $\pm 1$.

The vector $b_{\lambda\mu}^{\nu}$ depends on $\lambda, \mu, \nu$ in a way that reflects the boundary conditions of the hive.

Let $Q_{\lambda\mu}^{\nu}$ denote the polytope defined by the inequalities

$$ Ax - b_{\lambda\mu}^{\nu} \le \vec{2}. \qquad (3.3) $$

Let $O_{\lambda\mu}^{\nu}$ denote the polytope defined by the inequalities

$$ Ax - b_{\lambda\mu}^{\nu} \le -\vec{2}. \qquad (3.4) $$

By (3.2), (3.3) and (3.4),

$$ O_{\lambda\mu}^{\nu} \subseteq \zeta_{\lambda\mu}^{\nu} \subseteq Q_{\lambda\mu}^{\nu}. \qquad (3.5) $$
## 3.1 A Randomized Approximation Scheme for deep Littlewood-Richardson coefficients

**Lemma 6** If $(\lambda, \mu, \nu) \in (\Delta_{\epsilon}, \Delta_{\epsilon}, \Delta'_{\epsilon}) + LRC$, then $P_{\lambda\mu}^{\nu}$ contains a Euclidean ball of radius $(\frac{n}{2})/2\epsilon$.

**Proof:** By results of Knutson-Tao [9] every integer triple in the rational cone generated by triples corresponding to non-zero Littlewood-Richardson coefficients also corresponds to a non-zero Littlewood-Richardson coefficient. Fix $\hat{\lambda} = \lambda - \Delta_{\epsilon}$, $\hat{\mu} = \mu - \Delta_{\epsilon}$ and $\hat{\nu} = \nu - \Delta'_{\epsilon}$. Let $z$ denote an arbitrary integer point in $P_{\lambda\hat{\mu}}^{\hat{\nu}}$ (which exists by the last remark). By (3.2) and the corresponding set of inequalities for $P_{\Delta_{\epsilon}\Delta_{\epsilon}}^{\Delta'_{\epsilon}}$, we see that $z + P_{\Delta_{\epsilon}\Delta_{\epsilon}}^{\Delta'_{\epsilon}} \subseteq P_{\lambda\mu}^{\nu}$. To prove the lemma, it thus suffices to show that $P_{\Delta'_{\epsilon}\Delta_{\epsilon}}^{\Delta_{\epsilon}}$ contains a ball of radius $(\frac{n}{2})$. We first describe the center of this ball. Let $(0, 0)$ be the leftmost – bottommost corner of the hive in question. Here $u$ is the coordinate corresponding to the $x$ direction, and $v$ is the coordinate corresponding to the $x/2 + \frac{\sqrt{3}}{2}y$ direction. Consider the restriction of the following function to $\tau_n \cap L$:

$$f(u, v) = \left(\frac{1}{\epsilon}\right) \left( (3n^3 + n^2)u + (2n^3)v - (n^2 - n)(u^2 + v^2) \right).$$

This corresponds to a hive. Moreover, the resulting vector $x_f$ satisfies

$$Ax_f - b_{\Delta_{\epsilon}\Delta_{\epsilon}}^{\Delta'_{\epsilon}} \leq -\left(\frac{2}{\epsilon}\right)\left(\frac{\vec{n}}{2}\right). \qquad (3.6)$$

Therefore, by Observation 1, for any vector $y \in \mathbb{R}^{(n/2)}$ such that $\|y\|_{\infty} \leq \frac{(n/2)}{2\epsilon}$.

$$A(x_f + y) - b_{\Delta_{\epsilon}\Delta_{\epsilon}}^{\Delta'_{\epsilon}} \leq \vec{0}. \qquad (3.7)$$

In particular, this means that $P_{\lambda\mu}^{\nu}$ contains a ball of radius $(\frac{n}{2})/2\epsilon$. $\square$

**Lemma 7** If $n > C$, and $n^2\epsilon^{-1} \in \mathbb{N}$ then if $(\lambda, \mu, \nu) \in (\Delta_{\epsilon}, \Delta_{\epsilon}, \Delta'_{\epsilon}) + LRC$

$$1 - C\epsilon \leq \frac{\mathrm{vol} \, \zeta_{\lambda\mu}^{\nu}}{\mathrm{vol} \, Q_{\lambda\mu}^{\nu}} \leq 1. \qquad (3.8)$$

**Proof:** Let $\hat{\lambda} = \lambda - \Delta_{\epsilon}$, $\hat{\mu} = \mu - \Delta_{\epsilon}$ and $\hat{\nu} = \nu - \Delta'_{\epsilon}$. By results of Knutson-Tao [9] $P_{\lambda\hat{\mu}}^{\hat{\nu}}$ contains an integer point. Let this point be $z$.

**Claim 1** Let the origin be translated so that centered at $z + (\Delta_{\epsilon}, \Delta_{\epsilon}, \Delta'_{\epsilon})$ is the new origin. Let $d := (\frac{n}{2})$ and $n \geq C$. Then,

$$\left(1 + \frac{C_1 \epsilon}{d}\right) O_{\lambda\mu}^{\nu} \supseteq Q_{\lambda\mu}^{\nu}. \qquad (3.9)$$
**Proof:** This follows from Lemma 6 and elementary geometry.

<figure><img src="image_4.png" /></figure>

Consequently

$$ \mathrm{vol} \, \zeta_{\lambda\mu}^{\nu} \geq \left(1 + \frac{C_1 \epsilon}{d}\right)^{-d} (\mathrm{vol} \, Q_{\lambda\mu}^{\nu}). \qquad (3.10) $$

Thus,

$$ \mathrm{vol} \, \zeta_{\lambda\mu}^{\nu} \geq \left(1 + \frac{C_1 \epsilon}{d}\right)^{-d} (\mathrm{vol} \, Q_{\lambda\mu}^{\nu}). \qquad (3.11) $$

$$ \geq e^{-C_1 \epsilon} (\mathrm{vol} \, Q_{\lambda\mu}^{\nu}). \qquad (3.12) $$

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

**Proof of Theorem 3:** We denote by $W_{\infty}(\nu_1, \nu_2)$ the infinity-Wasserstein distance between two measures $\nu_1$ and $\nu_2$ supported on a metric space $X$. This is defined as

$$ \inf_{\nu} \sup_{(x_1, x_2) \in \mathrm{supp}(\nu)} \|x_1 - x_2\|, \qquad (3.13) $$

where the infimum is over all measures on $X \times X$ such that the marginal on the first factor is $\nu_1$ and the marginal on the second factor is $\nu_2$. The Dikin walk [6], started at the point $x_0 \in Q_{\lambda\mu}^{\nu}$ can be used to sample from a distribution $\mu$ that satisfies the following property in strongly polynomial time: there is a measure $\hat{\mu}$ such that $W_{\infty}(\hat{\mu}, \mu) < e^{-(\|(\lambda, \mu, \nu)\|_1)(\frac{n}{\epsilon})^C}$ and $\|\hat{\mu} - \hat{\mu}'\|_{TV} < \epsilon$, where $\hat{\mu}'$ is the uniform measure on $Q_{\lambda\mu}^{\nu}$. We note that this involves using random numbers whose bitlength depends on $\|(\lambda, \mu, \nu)\|$, however the number of operations on these random numbers depends polynomially on $n$, $\epsilon$ and $\log \frac{1}{\delta}$.

This allows us to produce $s$ i.i.d random points in $TQ_{\lambda\mu}^{\nu}$, each from a distribution $\mu$ that is close to $\hat{\mu}'$ in the above sense.

## 3.2 Step 1. of the Algorithm

There are a number of algorithms that compute estimates of the volume of a convex set $K$ in polynomial time as a function of $n$ and the ratio between a the radius $R_K$ of a ball containing $K$ and the radius $r_K$ of another ball contained in $K$. The most efficient of these is the algorithm of Lovász and Vempala [12].
Step 1. Produce an estimate $\hat{V}$ of the volume $V$ of the polytope $Q_{\lambda\mu}^{\nu}$ in strongly polynomial time that has the following property:

$$ \mathbb{P}\left[\frac{\hat{V}}{V} \in [1-\epsilon, 1+\epsilon]\right] > 1-\delta. \qquad (3.14) $$

Step 2. Produce $s = \frac{C \log \frac{1}{\delta}}{\epsilon^2}$ samples from a distribution $\mu$ such that the following holds. There is a measure $\hat{\mu}$ such that $W_{\infty}(\hat{\mu}, \mu) < e^{-(\|(\lambda, \mu, \nu)\|_1)(\frac{n}{\epsilon})^C}$ and $\|\hat{\mu} - \hat{\mu}'\|_{TV} < \epsilon$, where $\hat{\mu}'$ is the uniform measure on $Q_{\lambda\mu}^{\nu}$. Take the nearest lattice point to each sample, and compute the fraction $f$ of the resulting points that lie in $P_{\lambda\mu}^{\nu}$.

Step 3. Output $f\hat{V}$ (an estimate of vol $\zeta_{\lambda\mu}^{\nu}$).

However, we wish to compute this estimate using a number of operations that is polynomial in $n$ rather than the bitlength, and therefore we cannot afford any dependence on $\frac{R_K}{r_K}$. To this end, given polytope $Q_{\lambda\mu}^{\nu}$, we describe below, how to find in strongly polynomial time, a linear transformation $T$ such that for a $TQ_{\lambda\mu}^{\nu}$ contains a ball of radius 1 and is contained inside a ball of radius $m^{\frac{3}{2}}$, where $m$ is the number of constraints.

Let $Q$ be a polytope given by $Ax \le 1$. Then, the Dikin ellipsoid $D_{x_0}(r)$ of radius $r$ centered at a point $x_0$ is the set of all $y$ such that

$$ \{y : (x_0 - y)^T \left( \sum_{i=1}^{m} \frac{a_i a_i^T}{(1 - a_i^T x_0)^2} \right) (x_0 - y) \le r^2\}. \qquad (3.15) $$

For every codimension 1 facet $f$ of $Q_{\lambda\mu}^{\nu}$, consider the vector $v_f$ orthogonal to the hyperplane containing $f$. Use the strongly polynomial time linear programming algorithm of Tardos [20] as in [15] to maximize both $\langle x, v_f \rangle$ and $\langle x, -v_f \rangle$ over all $x$ in $Q_{\lambda\mu}^{\nu}$. If both of the resulting points are contained in $f$, we declare the polytope $Q_{\lambda\mu}^{\nu}$ to be contained in the affine span of $f$, and therefore have 0 volume. Otherwise, exactly one of the points is not in $f$. Denote this point by $x_f$. Let $x_0$ be the average of all points $x_f$ as $f$ ranges over the codimension 1 facets of $Q_{\lambda\mu}^{\nu}$. Define $T$ to be a linear transformation that maps the Dikin ellipsoid $D_{x_0}(1)$ of $Q_{\lambda\mu}^{\nu}$ onto the unit ball. Suppose $Q_{\lambda\mu}^{\nu}$ is expressed as $Cx \le 1$. Such a $T$ can be found using the Cholesky decomposition of

$$ \left( \sum_{i=1}^{m} \frac{c_i c_i^T}{(1 - c_i^T x_0)^2} \right), $$

where $m$ is the number of rows in $C$, which can be found in strongly polynomial time provided one can find square-roots in one operation. We have assumed this in our model of computation.

### 3.2.1 Correctness of Step 1.

Let $K \cap (x - K)$ be defined to be the symmetrization around $x$ of the convex set $K$. Then, translating the origin to $x_0$ we have the following lemma.
**Lemma 8** 1. $\frac{1}{\sqrt{m}}(Q_{\lambda\mu}^{\nu} \cap (-Q_{\lambda\mu}^{\nu})) \subseteq D_{x_0}(1) \subseteq Q_{\lambda\mu}^{\nu} \cap (-Q_{\lambda\mu}^{\nu})$.

2. $\frac{1}{m-1}Q_{\lambda\mu}^{\nu} \subseteq Q_{\lambda\mu}^{\nu} \cap (-Q_{\lambda\mu}^{\nu})$.

**Proof:** Consider an arbitrary chord of ab of $Q_{\lambda\mu}^{\nu}$ through the origin $x_0$. Identify it with the real line. Let $\pm t$ be the points where the chord intersects the ellipsoid. Let $\pm t_1, \pm t_2, \dots$ be the intersections of the chord with the extended facets of the symmetrized body. Then,

$$ \frac{1}{t^2} = \sum_i \frac{1}{t_i^2}. $$

It follows that

$$ \frac{1}{\sqrt{m}} \min_i |t_i| \le |t| \le \min_i |t_i|. \qquad (3.16) $$

This completes the proof of the first part of the lemma. To see the second part, consider again the same arbitrary chord ab through $x_0$. Suppose without loss of generality that $|t_1| \le |t_2| \le \dots$, and that $a = -t_1$ and $b = t_k$. Let $a$ lie on the face $f$. Let $a'$ be the intersection with the hyperplane containing face $f_1 := f$ of the line through $x_0$ and $x_f$. Then, by the definition of $x_f$,

$$ \frac{|x_f|}{|a'|} \ge \frac{|b|}{|a|}. \qquad (3.17) $$

It thus suffices to show that $m - 1 \ge \frac{|x_f|}{|a'|}$. As $f_i$ ranges over the faces of $Q_{\lambda\mu}^{\nu}$, all the points $x_{f_i}$ lie on the same side of the affine span of $f_1$. Therefore their average $x_{2,av} := (\frac{1}{m-1}) \sum_{i \ge 2} x_{f_i}$ lies on the same side of the affine span of $f_1$ as does $x_{f_1}$. However $x_{2,av}$ lies on the line joining $x_{f_1}$ and $x_0 = (1/m) \sum_{i \ge 1} x_{f_i}$. Therefore

$$ m - 1 = \frac{|x_f|}{|x_{2,av}|} \ge \frac{|x_f|}{|a'|} \ge \frac{|b|}{|a|}. \qquad (3.18) $$

This proves the lemma.

□

### 3.3 Step 2. of the Algorithm

We observe that the fraction $f$ mentioned in Step 2 is the average of i.i.d $0-1$ random variables $x_i$, each having a success probability $p$ that satisfies $p - \epsilon < \frac{\text{vol} \zeta_{\lambda\mu}^{\nu}}{\text{vol} Q_{\lambda\mu}^{\nu}} < p + \epsilon$. By (7) $\frac{1}{C} \le p \le 1$ for each $i$.

By the below Proposition 3.1,

$$ \mathbb{P}\left[\left|f - \frac{\text{vol} \zeta_{\lambda\mu}^{\nu}}{\text{vol} Q_{\lambda\mu}^{\nu}}\right| \ge 2\epsilon\right] \le \delta. \qquad (3.19) $$

The following Proposition is a consequence of Theorem 1 of Hoeffding [5].

**Proposition 3.1** Let a coin have success probability $p$. Let $\hat{m}$ be the number of successes after $m$ proper trials. Then

$$ \mathbb{P}\left[\left|\frac{\hat{m}}{m} - p\right| \ge \alpha p\right] \le 2e^{-\frac{\alpha^2 mp}{3}}. $$
### 3.3.1 Correctness of Step 2.

Provided we work with numbers whose bitlength is

$$ \| (\lambda, \mu, \nu) \|_1 \left(\frac{n}{\epsilon}\right)^C, $$

we can produce $\mu$ such that there exists $\hat{\mu}$ satisfying the following.

$$ W_{\infty}(\hat{\mu}, \mu) < e^{-(\| (\lambda, \mu, \nu) \|_1) \left(\frac{n}{\epsilon}\right)^C} \quad (3.20) $$

and

$$ \| \hat{\mu} - \hat{\mu}' \|_{TV} < \epsilon, \quad (3.21) $$

where $\hat{\mu}'$ is the uniform measure on $Q_{\lambda\mu}^{\nu}$. In a real number model of computation, Dikin walk produces a sample from $\hat{\mu}$ in polynomial time. By truncating these real numbers at every step to a bit-length of $((\| (\lambda, \mu, \nu) \|_1) \left(\frac{n}{\epsilon}\right)^C)$, the errors do not accumulate to beyond a multiplicative factor of $O(n^C)$ and the resulting measure $\mu$ satisfies the above conditions (3.20) and (3.21).

This completes the proof of Theorem 3. $\square$

**Proof of Theorem 4:** This follows from Theorem 3 and Lemma 12 of [17]. $\square$

## 4 Approximate Log-Concavity

In [21], Okounkov raised the question of whether the Littlewood-Richardson coefficients $c_{\lambda\mu}^{\nu}$ are a log-concave function of $\lambda, \mu, \nu$. Chindris, Derkson and Weyman showed in [2] that this is false in general. In this section, we show that certain Littlewood-Richardson coefficients satisfy a form of approximate log-concavity by proving Theorem 5. We will need the Brunn-Minkowski Theorem stated below.

**Theorem 9 (Brunn-Minkowski)** Let $Q_1, Q_2$ and $Q_3$ be convex subsets of $\mathbb{R}^n$ and $\theta \in (0, 1)$, such that $\theta Q_1 + (1-\theta)Q_3 \subseteq Q_2$. where + denotes Minkowski addition. Then,

$$ (\mathrm{vol} Q_2)^{\frac{1}{n}} \geq \theta (\mathrm{vol} Q_1)^{\frac{1}{n}} + (1-\theta) (\mathrm{vol} Q_3)^{\frac{1}{n}}. $$

**Proof of Theorem 5:** Recall that (3.3), $Q_{\lambda\mu}^{\nu}$ is described by the system of inequalities

$$ Ax - b_{\lambda\mu}^{\nu} \leq \vec{2}. $$

If $\theta(\lambda, \mu, \nu) + (1-\theta)(\hat{\lambda}, \hat{\mu}, \hat{\nu}) = (\bar{\lambda}, \bar{\mu}, \bar{\nu})$, and each vector indexes a Littlewood-Richardson coefficient, then, because $Q_{\lambda\mu}^{\nu}, Q_{\lambda\hat{\mu}}^{\nu}$ and $Q_{\bar{\lambda}\hat{\mu}}^{\bar{\nu}}$ are described by rhombus inequalities, we have

$$ \theta Q_{\lambda\mu}^{\nu} + (1-\theta) Q_{\lambda\hat{\mu}}^{\nu} \subseteq Q_{\lambda\bar{\mu}}^{\bar{\nu}}. \quad (4.1) $$

Therefore, by the Brunn-Minkowski inequality,

$$ (\mathrm{vol} Q_{\lambda\mu}^{\nu})^{\frac{1}{n}} \geq \theta (\mathrm{vol} Q_{\lambda\hat{\mu}}^{\nu})^{\frac{1}{n}} + (1-\theta) (\mathrm{vol} Q_{\lambda\bar{\mu}}^{\bar{\nu}})^{\frac{1}{n}}. $$
Hence, by the concavity and monotonicity of the logarithm,

$$ \log (\mathrm{vol} Q_{\lambda\mu}^{\nu}) \geq \theta \log (\mathrm{vol} Q_{\lambda\hat{\mu}}^{\hat{\nu}}) + (1 - \theta) \log (\mathrm{vol} Q_{\lambda\bar{\mu}}^{\bar{\nu}}). $$

By Lemma 7, if $n > C$, and $n^2\epsilon^{-1} \in \mathbb{N}$ then if $(\lambda, \mu, \nu) \in (1/\epsilon)(\Delta, \Delta, \Delta') + LRC$

$$ 1 - C\epsilon \leq \frac{c_{\lambda\mu}^{\nu}}{\mathrm{vol} Q_{\lambda\mu}^{\nu}} \leq 1, $$

and corresponding statements hold for $(\lambda, \mu, \nu)$ and $(\bar{\lambda}, \bar{\mu}, \bar{\nu})$. $\square$

<figure><img src="image_7.png" /></figure>

# 5 Concluding Remarks

In this paper, we developed a strongly polynomial randomized approximation scheme for Littlewood-Richardson coefficients that belong to a translate of the Littlewood-Richardson cone by the vector $(\Delta, \Delta, \Delta')$. We show that a form of approximate log-concavity holds among a subset of the set of Littlewood-Richardson coefficients. It would be of interest to extend these results to the entire Littlewood-Richardson cone.

# 6 Acknowledgements

I thank Ketan Mulmuley for suggesting the question of computing Littlewood-Richardson coefficients, and Ravi Kannan for bringing [7] to my notice.

# References

[1] P. Bürgisser, C. Ikenmeyer, “A max-flow algorithm for positivity of Littlewood-Richardson coefficients,” FPSAC 2009, 357-368

[2] C. Chindris, H. Derksen, J. Weyman, “Non-log-concave Littlewood-Richardson coefficients,” Compos. Math. 43 (2007), 1545-1557

[3] E. Rassart, “A polynomiality property for Littlewood-Richardson coefficients.” Journal of Combinatorial Theory, Series A 107 (2004), no. 2, 161-179

[4] M. Köppe, J. De Loera, “Lattice Point Enumeration Software,” https://www.math.ucdavis.edu/latte/

[5] W. Hoeffding, “Probability inequalities for sums of bounded random variables”. Journal of the American Statistical Association 58 (301): 13-30

[6] R. Kannan and H. Narayanan, “Random walks on polytopes and an affine interior point algorithm for linear programming,” Mathematics of Operations Research, February 2012

[7] R. Kannan, V. Vempala, “Sampling Lattice Points,” Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, (1997)
[8] Kirszbraun, M. D. (1934). “Über die zusammenziehende und Lipschitzsche Transformationen”. Fund. Math. 22: 77-108

[9] A. Knutson, T. Tao, “The honeycomb model of $GL_n(\mathbb{C})$ tensor products I: proof of the saturation conjecture,” J. Amer. Math. Soc. 12 (1999) 1055–1090.

[10] A. Knutson, T. Tao, and C. Woodward, “The honeycomb model of $GL_n(\mathbb{C})$ tensor products II. Puzzles determine facets of the Littlewood-Richardson cone,” J. Amer. Math. Soc. 17 (2004), no. 1, 1948

[11] J. De Loera and T. McAllister, “On the computation of Clebsch-Gordan coefficients and the dilation effect,” Experiment. Math. 15 (2006), no. 1, 7–20.

[12] L. Lovász and S. Vempala, “Simulated annealing in convex bodies and an $O*(n^4)$ volume algorithm” Proc. of the 44th IEEE Foundations of Computer Science (FOCS ’03), Boston, 2003.

[13] K. Mulmuley, M. Sohoni, “Geometric complexity theory I: An approach to the P vs. NP and related problems,” SIAM J. Comput., vol 31, no. 2, pp. 496–526, (2001).

[14] K. Mulmuley, M. Sohoni, “Geometric complexity theory II: Towards explicit obstructions for embeddings among class varieties.” SIAM J. Comput., Vol. 38, Issue 3, June 2008.

[15] K. D. Mulmuley, H. Narayanan, and M. Sohoni, “Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient.” J. Algebraic Combin. 36 (2012), no. 1, 103-110.

[16] H. Narayanan, “On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients”, Journal of Algebraic Combinatorics, Volume 24, Issue 3, November 2006

[17] H. Narayanan, “Estimating Certain Non-zero Littlewood-Richardson Coefficients”, arxiv preprint, http://arxiv.org/pdf/1306.4060.pdf

[18] K. Purbhoo, “Puzzles, Tableaux and Mosaics,” Journal of Algebraic Combinatorics, 28 (2008) no. 4, 461-480.

[19] R. Schneider, “Convex bodies: the Brunn-Minkowski Theory,” Cambridge University Press, Feb 25, 1993

[20] E. Tardos, “A strongly polynomial algorithm to solve combinatorial linear programs,” Operations Research, Vol. 34, No. 2 (Mar. - Apr., 1986), pp. 250–256

[21] A. Okounkov, “Why would multiplicities be log-concave?”, The Orbit Method in Geometry and Physics, Progress in Mathematics, Volume 213, 2003, pp 329–347

[22] Wigner, E. P., “Group Theory and Its Application to the Quantum Mechanics of Atomic Spectra, expanded and improved,” ed. New York: Academic Press, 1959.