# Littlewood-Richardson coefficients as a signed sum of Kostka numbers

Sagar Shrivastava  School of mathematics, Tata Institute of Fundamental
Research, Homi Bhabha Road, Mumbai 400005, India<EMAIL_ADDRESS>
###### Abstract.

Littlewood-Richardson (LR) coefficients and Kostka Numbers appear in
representation theory and combinatorics related to $GL_{n}$. It is known that
Kostka numbers can be represented as special Littlewood-Rischardson
coefficient [KTT04]. In this paper, we show how one can represent LR
coefficient as a signed sum of Kostka numbers, and use the formulation to give
a polynomial time algorithm for the same, hence showing that they belong to
the same class of decision problems. As a corollary, we will prove Steinberg’s
formula [Ste61] using Kostant’s partition function.

##  1.. Introduction

Littlewood-Richardson(LR) coefficients can be thought of as the structure
constants for the ring of Symmetric functions (the Grothiendick ring of
characters for $GL_{n}$). Infact we have the following definition of the LR
coefficients:

$S_{\lambda}S_{\mu}=\sum_{\nu}c_{\lambda\mu}^{\nu}S_{\nu},$

where $S_{\lambda},S_{\mu},S_{\nu}$ are the Schur polynomials corresponding to
the highest weights $\lambda,\mu,\nu$ respectively, and the LR coefficient
$c_{\lambda\mu}^{\nu}$ can be seen as the multiplicity of $S_{\nu}$ in the
product decomposition of $S_{\lambda},S_{\mu}$.

Kostka numbers $K_{\lambda\mu}$ are defined as the number of ways one can fill
the boxes of the Young diagram of $\lambda$ with
$\mu_{1}\,1^{\prime}s,\mu_{2}\,2^{\prime}s$ upto $\mu_{n}\,n^{\prime}s$, in
such a way that the entries in each row are non decreasing and in each column
are strictly increasing (A semistandard tableau on $\lambda$ of type $\mu$.)

In [KTT04], it is shown that Kostka numbers can be viewed as a special type of
LR coefficients. To be precise, $K_{\lambda\mu}=c_{\sigma\lambda}^{\tau}$,
where

$\begin{cases}\tau_{i}=\mu_{i}+\mu_{1+1}+\cdots\\\
\sigma_{i}=\mu_{i+1}+\mu_{i+2}+\cdots\end{cases}\quad for\quad i=1,2,\ldots$

In the course of this paper, we will prove certain necessary and sufficient
condition for $K_{\lambda\mu}\neq 0$ (see Section 2, Proposition 1). The
following is the main theorem of this paper, which will be proven in Section
3:

######  Theorem 1.

$S_{\lambda}S_{\mu}=\sum_{\xi\trianglelefteq\mu}K_{\mu\xi}(-1)^{\eta}\sum_{\sigma\in
S_{n}/G(\xi)}S_{\eta(\lambda+\sigma(\xi)+\rho)-\rho}$

where $G(\xi)$ is the stabalizer of $\xi$ in $S_{n}$, $\rho$ is the half sum
of positive roots, $(-1)^{\eta}$ is the sign of $\eta\in S_{n}$ where $\eta\in
S_{n}$ is the unique permutation which brings $\lambda+\sigma(\xi)+\rho$ to
the positive Weyl chamber.

As a corollary to this theorem, we get the following representation of LR
coefficients in terms of Kostka numbers:

######  Corollary 1.

With the above notation, we have that

$c_{\lambda\mu}^{\nu}=\sum_{\begin{subarray}{c}\eta\in S_{n}\\\
\psi\trianglelefteq\mu\end{subarray}}(-1)^{\eta}K_{\mu\psi}$

where $\psi=\tau(\eta(\nu+\rho)-(\lambda+\rho))$, $\tau\in S_{n}$ is the
permutation bringing the touple $(\eta(\nu+\rho)-(\lambda+\rho))$ in the Weyl
chamber to the positive Weyl chamber.

Using this corollary, we will prove Stienberg’s formula [Ste61], by writing
Kostka numbers in terms of Kostant partition functions ($\mathfrak{P}$):

$c_{\lambda\mu}^{\nu}=\sum_{\sigma,\tau\in
S_{n}}(-1)^{\sigma\tau}\mathfrak{P}(\sigma(\lambda+\rho)+\tau(\mu+\rho)-(\nu+2\rho))$

In Section 4, we give the algorithm which allows us to compute LR coefficents
in polynomial time given that we have a black box that provides us with the
values of Kostka numbers in polynomial time, hence showing that computing
Kostka numbers and LR coefficents are in the same class of decision problems.

##  2.. Preliminaries and Notation

By a partition $\lambda$, we refer to a touple of non-negative integers
$(\lambda_{1},\lambda_{2},\ldots,\lambda_{n})$, where
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}\geq 0$. Denote the
content of $\lambda$ by $|\lambda|:=\sum_{i}\lambda_{i}$. We use the term
partitions and highest weight interchangably. Given partitions
$\lambda_{1},\lambda_{2},\ldots,\lambda_{k}$,
$\mathbf{size}(\lambda_{1},\lambda_{2},\ldots,\lambda_{k})$ denotes the number
of bits used in the description of this touple. Another way to look at a
partition is via Young tableau/diagram. A Young tableau corresponding to a
partition $\lambda$ (called a Young tableau of shape $\lambda$) is a
collection of boxes, arranged in left justified rows, such that the first row
has $\lambda_{1}$ boxes, second row has $\lambda_{2}$ boxes, and similarly the
$n^{th}$ row had $\lambda_{n}$ boxes ( the number of boxes per row is weakly
monotonically decreasing as
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}\geq 0$). For example,
$\lambda=(5,3,2)$ , the corresponding Young tableau is

5,3,2

A semistandard Young tableau of shape $\lambda$ is a Young diagram of shape
$\lambda$ in which the boxes are filled with integers in such a way that the
entries in each row are non decreasing and in each column are strictly
increasing.

Kostka numbers $K_{\lambda\mu}$ are defined as the number of ways one can fill
the boxes of the Young diagram of shape $\lambda$ with
$\mu_{1}\,1^{\prime}s,\mu_{2}\,2^{\prime}s$ upto $\mu_{n}\,n^{\prime}s$ such
that we get semistandard Young tableaus called semistandard tableau on
$\lambda$ of type $\mu$). For $\lambda=(5,3,2)$ and $\mu=(4,3,3)$, the
following are the only two semistandard Young tableau with shape $\lambda$ of
type $\mu$:

11112,223,33 11113,222,33

which shows that $K_{(5,3,2)(4,3,3)}=2$.

We will hereby follow the notion that $\mathbf{x}$ would refer to the touple
$(x_{1},x_{2},\ldots,x_{n})$, and similarly $\mathbf{y}$ refers to
$(y_{1},y_{2},\ldots,y_{n})$. We recall that for
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{n})$, the Schur polynomial
$S_{\lambda}$ is defined by the following ratio of alternating polynomials:

$S_{\lambda}(\mathbf{x})=\frac{\det(x_{i}^{\lambda_{j}+n-j})}{\det(x_{i}^{n-j})}.$

The Schur polynomial $S_{\lambda}$ corresponds to the character of
$\mathbf{S}^{\lambda}$, the Schur module which is the irreducible
representation of $GL_{n}(\mathbb{C})$ with highest weight $\lambda$. By
varying over all partitions with atmost $n$ parts ($n$ rows in the
corresponding young diagram), Schur polynomials gives a basis for the ring of
symmetric functions on $n$
variables($\mathbb{C}[x_{1},x_{2},\ldots,x_{n}]^{S_{n}}$).

LR coefficients are the structure constants in the ring of symmetric functions
(the Grothiendick ring of characters for $GL_{n}$). For partitions
$\lambda,\mu,\nu$, such that $|\nu|=|\lambda|+|\mu|$, we have that

$S_{\lambda}S_{\mu}=\sum_{\nu}c_{\lambda\mu}^{\nu}S_{\nu},$

Equivalently, one can state the character (symmetric function) version with
the notion that $\langle,\rangle$ is the Hall inner product on the ring
$\mathbb{C}[x_{1},x_{2},\ldots,x_{n}]^{S_{n}}$.

$c_{\lambda\mu}^{\nu}=\langle S_{\lambda}S_{\mu},S_{\nu}\rangle.$

Equivalently, one can define Kostka numbers as

$H_{\mu}=H_{\mu_{1}}H_{\mu_{2}}\ldots
H_{\mu_{n}}=\sum_{\lambda}K_{\lambda\mu}S_{\lambda},$

where $H_{k}$ correspont to the $k^{th}$ complete symmetric polynomial . We
have the following generating function for $H_{k}$:

$\prod_{i=1}^{n}\frac{1}{1-tx_{i}}=\sum_{k=0}^{\infty}t^{k}H_{k}(\mathbf{x}).$

We make use of the following identity which can be seen in Appendix A of
[FH91].

######  Theorem (Cauchy’s Identity).

$\prod_{1\leq i,j\leq
n}\frac{1}{(1-x_{i}y_{j})}=\sum_{\mu}S_{\mu}(\mathbf{x})S_{\mu}(\mathbf{y}),$

where the sum is over all partitions $\lambda$ with atmost $n$ terms.

We prove the following Proposition, giving a criterion for non-vanishing of
Kostka numbers that we would require in the main result (this can be seen as
Exercise A.11 in [FH91], but for better lack of reference, we give a complete
proof here) :

######  Proposition 1.

$K_{\mu\xi}\neq 0$ _iff_ $|\xi|=|\mu|$ and
$\xi_{1}+\xi_{2}+\cdots+\xi_{i}\leq\mu_{1}+\mu_{2}+\cdots+\mu_{i}$ for all
$i\geq 1$.

If $\trianglelefteq$ denotes the dominance ordering on partions of of same
size, then Lemma 1 is equivalent to saying $K_{\mu\xi}\neq
0\iff\xi\trianglelefteq\mu$

###### Proof.

If $K_{\mu\xi}\neq 0$, then there is a semistandard tableau on $\mu$ of type
$\xi$. In a semistandard tableau, a box with ‘i’ can occur in atmost the
$i^{th}$ row (as columns are strictly increasing). There are
$\xi_{1}\,1^{\prime}s,\xi_{2}\,2^{\prime}s,\ldots\xi_{i}\,i^{\prime}s,$ which
can atmost occur upto the $i^{th}$ row of $\mu$ which immediately gives us the
inequality

$\xi_{1}+\xi_{2}+\cdots+\xi_{i}\leq\mu_{1}+\mu_{2}+\cdots+\mu_{i}.$

Also, $|\xi|=|\mu|$ is a necessary condition for the tableau to be
semistandard.

For the converse, we have that $\xi\trianglelefteq\mu$ is given, we will use
induction on the number of rows of $\xi$, to show that this gives us a
semistandard tableau on $\mu$ of type $\xi$. If there is only one row in
$\xi$, then there is exactly one row in $\mu$ and they have same lenght, so
the base case is true.

Assume that if there are $k-1$ rows in $\eta$ and
$\eta\trianglelefteq\lambda$, then there is a semistandard tableau on
$\lambda$ of type $\eta$. Let $\xi,\mu$ be such that $\xi\trianglelefteq\mu$,
and the number of rows in $\xi$ is $k$. By the inequality, we know that there
exists an $r$, such that $\mu_{r+1}<\xi_{k}\leq\mu_{r}$. Let $m$ be the number
of rows in $\mu$, we fill the tableau of $\mu$ from the bottom, going right to
left, filling atmost $\mu_{m}$ $k^{\prime}s$ in the $m^{th}$ row, atmost
$\mu_{m-1}-\mu_{m}$ $k^{\prime}s$ in the $(m-1)^{th}$ row, and continuing like
this (exhaustively filling right to left, then going to the row above), we
reach the $r^{th}$ row, where the $k^{\prime}s$ get exhausted. Consider
$\mu=(14,11,6,5,3)$ and $\xi=(9,8,8,7,7)$, then $\xi\trianglelefteq\mu$, and
the following Young’s diagram shows how we are filling the seven $5^{\prime}s$

[*(white) 5] 14+0,10+1,5+1,3+2,0+3 *[*(lightgray)]14,11,6,5,3

The boxes in gray are the boxes still empty in the tableau after filling
$5^{\prime}s$,and can be seen as $(14,10,5,3)$. In general, the empty boxes in
the tableau of $\mu$ can be seen as
$\mu^{\prime}=(\mu_{1},\mu_{2},\ldots,\mu_{r-1},\mu_{r}-(\xi_{k}-\mu_{r+1}),\mu_{r+2},\ldots,\mu_{m})$.
We claim that $\xi^{\prime}\trianglelefteq\mu^{\prime}$, where
$\xi^{\prime}=(\xi_{1},\xi_{2},\ldots,\xi_{k-1})$, which has exactly $k-1$
rows. Hence we can use induction hypothesis to get a semistandard tableau on
$\mu$ of type $\xi$ ( as the numbers to be filled are all $\leq k-1$, the
filled boxes filled with $k$ would keep the tableau semistandard). For $1\leq
i\leq r-1$, we get that
$\xi_{1}+\xi_{2}+\cdots+\xi_{i}\leq\mu_{1}+\mu_{2}+\cdots+\mu_{i}$ as
$\xi\trianglelefteq\mu$. Note that $\xi_{s}\geq\xi_{k}$ for all $s$. Hence for
all $s$, such that $r\leq s\leq k-1$, we get that

$\xi_{1}+\xi_{2}+\cdots+\xi_{s}+\xi_{k}\leq\xi_{1}+\xi_{2}+\cdots+\xi_{s}+\xi_{s+1}\leq\mu_{1}+\mu_{2}+\cdots+\mu_{s}+\mu_{s+1}$

which gives us
$\xi_{1}+\xi_{2}+\cdots+\xi_{s}\leq\mu_{1}+\mu_{2}+\cdots+(\mu_{r}+\mu_{r+1}-\xi_{k})+\mu_{r+2}+\cdots\mu_{s}+\mu_{s+1}$,
proving the claim.

∎

Let $\Phi^{+}\subset\Phi$ be a set of positive roots in a root system. The
Kostant partition function $\mathfrak{P}$ for $\Phi^{+}$ is defined via the
relation

$\prod_{\alpha\in\Phi^{+}}\frac{1}{1-\mathbf{e}^{\alpha}}=\sum_{\omega}\mathfrak{P}(\omega)\mathbf{e}^{\omega}$

Note that $\mathbf{e}$ is just a formal variable in this context, but with
this convention $\mathbf{e}^{a}\mathbf{e}^{b}=\mathbf{e}^{a+b}$ . With this
notation in picture, one can show that Kostka numbers can be expressed as a
signed sum of Kostant partition function. If $\lambda,\mu$ are partitions of
$n$, we have the following relation:

$K_{\lambda\mu}=\sum_{\sigma\in
S_{n}}(-1)^{\sigma}\mathfrak{P}(\sigma(\lambda+\rho)-(\mu+\rho))$

We refer the interested reader to [Led06] for a complete proof of the above
equality.

The class $\\#P$ is the class of functions
$f:\cup_{m\in\mathbb{N}}\\{0,1\\}\rightarrow\mathbb{Z}_{\geq 0}$ for which
there exists a polynomial time Turing machine $M$ and a polynomial $p$ such
that $(\forall m\in\mathbb{N}),(\forall
x\in\\{0,1\\}^{m}),f(x)=|\\{y\in\\{0,1\\}^{p(m)}$ such that $M$ accepts
$(x,y)\\}|$. Many counting problems like number of integer points in a
polytope are in $\\#P$. A counting problem $X\in\\#P$ is $\\#P-$complete if
given a black box that provides solutions to instances of $X$ in polynomial
time, any problem in the class $\\#P$ can be solved in polynomial time.

##  3.. Main Theorem

We give a proof of Theorem 1:

###### Proof.

We take the formal product:

$\displaystyle
S_{\lambda}(\mathbf{x})\sum_{\mu}S_{\mu}(\mathbf{x})S_{\mu}(\mathbf{y})$
$\displaystyle=S_{\lambda}(\mathbf{x})\prod_{1\leq i,j\leq
n}\frac{1}{(1-x_{i}y_{j})}$ (1)
$\displaystyle=\frac{\det(x_{i}^{\lambda_{j}+n-j})}{\det(x_{i}^{n-j})}\prod_{1\leq
i,j\leq n}\frac{1}{(1-x_{i}y_{j})}$ (2)
$\displaystyle=\frac{1}{\det(x_{i}^{n-j})}\det\left(\frac{x_{i}^{\lambda_{j}+n-j}}{\prod_{k=1}^{n}(1-x_{i}y_{k})}\right)$
(3)

consider the $ij^{th}$ entry in the above determinant:

$\displaystyle\frac{x_{i}^{\lambda_{j}+n-j}}{\prod_{k=1}^{n}(1-x_{i}y_{k})}$
$\displaystyle=x_{i}^{\lambda_{j}+n-j}\sum_{r=0}^{\infty}x_{i}^{r}H_{r}(\mathbf{y})$
$\displaystyle=\sum_{r=0}^{\infty}x_{i}^{(\lambda_{j}+r)+n-j}H_{r}(\mathbf{y})$

so (3) becomes

$\frac{\det\left(\sum_{k_{ij}=0}^{\infty}x_{i}^{(\lambda_{j}+k_{ij})+n-j}H_{k_{ij}}(\mathbf{y})\right)}{\det(x_{i}^{n-j})}$
(4)

We make a choice of the indices $k_{ij}=k_{j}$ ( specializing with this choice
allows us to expand the determinant along the rows and take
$H_{k_{j}}(\mathbf{y})$ common from them). With this choice, we can write the
$i^{th}$ row as

$\left[\sum_{k_{ij}=0}^{\infty}x_{i}^{(\lambda_{j}+k_{ij})+n-j}H_{k_{ij}}(\mathbf{y})\right]_{i}=\sum_{k_{j}=0}^{\infty}H_{k_{j}}(\mathbf{y})[x_{i}^{(\lambda_{j}+k_{j})+n-j}]_{i}$

this along with the fact that deteminant is an $n$ linear function, we get
that (4) becomes:

$\sum_{(k_{1},k_{2},\ldots,k_{n})\in\mathbb{Z}_{\geq
0}^{n}}\prod_{j=1}^{n}H_{k_{j}}\frac{\det(x_{i}^{(\lambda_{j}+k_{j})+n-j})}{\det(x_{i}^{n-j})}$
(5)

Given $\mathbf{k}=(k_{1},k_{2},\ldots,k_{n})\in\mathbb{Z}_{\geq 0}^{n}$, we
define $G(\mathbf{k})=\\{\sigma\in S_{n}|\sigma(\mathbf{k})=\mathbf{k}\\}$ as
the stabalizer of $\mathbf{k}$, and then $\sigma(\mathbf{k})$ where $\sigma\in
S_{n}/G(\mathbf{k})$ ranges over all possible permutations of $\mathbf{k}$
without double counting. With this, we reindex the sum to be over partitions,
so (5) becomes

$\sum_{\xi}H_{\xi}(\mathbf{y})\sum_{\sigma\in
S_{n}/G(\xi)}\frac{\det(x_{i}^{\lambda_{j}+\xi_{\sigma(j)}+n-j})}{\det(x_{i}^{n-j})}$
(6)

If for any $k\neq j$, if
$\lambda_{j}+\xi_{\sigma(j)}+n-j=\lambda_{k}+\xi_{\sigma(k)}+n-k$, then
$\det(x_{i}^{\lambda_{j}+\xi_{\sigma(j)}+n-j})=0$, so for the ones that
remain, we have that $\lambda_{j}+\xi_{\sigma(j)}+n-j$ are distinct for all
$j$, hence there exists a unique $\eta\in S_{n}$ such that
$\eta(\lambda+\sigma(\xi)+\rho)-\rho$ is a dominant weight ( $\eta$ acts to
bring the touple inside the positive Weyl chamber). The action of $\eta$ will
bring about a sign change as well:

$\displaystyle\sum_{\xi}H_{\xi}(\mathbf{y})\sum_{\sigma\in
S_{n}/G(\xi)}\frac{\det(x_{i}^{\lambda_{j}+\xi_{\sigma(j)}+n-j})}{\det(x_{i}^{n-j})}$
$\displaystyle=\sum_{\xi}H_{\xi}(\mathbf{y})\sum_{\sigma\in
S_{n}/G(\xi)}(-1)^{\eta}S_{\eta(\lambda+\sigma(\xi)+\rho)-\rho}(\mathbf{x})$
(7)
$\displaystyle=\sum_{\xi}\sum_{\nu}K_{\nu\xi}S_{\nu}(\mathbf{y})\sum_{\sigma\in
S_{n}/G(\xi)}(-1)^{\eta}S_{\eta(\lambda+\sigma(\xi)+\rho)-\rho}(\mathbf{x})$
(8)

By Proposition 1, we get that $K_{\nu\xi}\neq 0$ iff $\xi\trianglelefteq\nu$,
so (8) becomes:

$\sum_{\nu}S_{\nu}(\mathbf{y})\left(\sum_{\xi\trianglelefteq\nu}K_{\nu\xi}\sum_{\sigma\in
S_{n}/G(\xi)}(-1)^{\eta}S_{\eta(\lambda+\sigma(\xi)+\rho)-\rho}(\mathbf{x})\right)$
(9)

Comparing this with (1) we get that the coefficient of $S_{\mu}(\mathbf{y})$
in both the equations must be the same, which gives us the following equality:

$S_{\lambda}(\mathbf{x}).S_{\mu}(\mathbf{x})=\sum_{\xi\trianglelefteq\mu}K_{\mu\xi}(-1)^{\eta}\sum_{\sigma\in
S_{n}/G(\xi)}S_{\eta(\lambda+\sigma(\xi)+\rho)-\rho}(\mathbf{x})$

∎

######  Corollary.

With the above notation, we have that

$c_{\lambda\mu}^{\nu}=\sum_{\begin{subarray}{c}\eta\in S_{n}\\\
\psi\trianglelefteq\mu\end{subarray}}(-1)^{\eta}K_{\mu\psi}$

where $\psi=\tau(\eta(\nu+\rho)-(\lambda+\rho))$, $\tau\in S_{n}$ is the
permutation bringing the touple $(\eta(\nu+\rho)-(\lambda+\rho))$ in general
position.

###### Proof.

We know from the theorem that

$S_{\lambda}(\mathbf{x})S_{\mu}(\mathbf{x})=\sum_{\nu}c_{\lambda\mu}^{\nu}S_{\nu}(\mathbf{x})=\sum_{\xi\trianglelefteq\mu}K_{\mu\xi}(-1)^{\eta}\sum_{\sigma\in
S_{n}/G(\xi)}S_{\eta(\lambda+\sigma(\xi)+\rho)-\rho}(\mathbf{x})$

We solve for for $\xi$ in $\nu=\eta(\lambda+\sigma(\xi)+\rho)-\rho$ to get the
coefficient of $S_{\nu}$. We get that
$\sigma(\xi)=\eta^{-1}(\nu+\rho)-(\lambda+\rho)$, where $\sigma(\xi)$ is
supposed to vary over all permutations of $\xi$. We get that by varying
$\eta\in S_{n}$, such that $\eta(\nu+\rho)-(\lambda+\rho)$ lies in the Weyl
chamber, we can recover all the permutations of $\xi$ . There would be a
unique choice of $\tau\in S_{n}$, such that
$\psi=\tau(\eta(\nu+\rho)-(\lambda+\rho))$ is in the positive Weyl chamber,
hence a dominant weight. With these notations, we get that the coefficient of
$S_{\nu}$ is given by

$c_{\lambda\mu}^{\nu}=\sum_{\begin{subarray}{c}\eta\in S_{n}\\\
\psi\trianglelefteq\mu\end{subarray}}(-1)^{\eta}K_{\mu\psi}$

∎

As an example, we can do the computation for
$\lambda=(5,3,2),\mu=(4,3,3),\nu=(9,6,5)$ to see that the value of
$\eta(\nu+\rho)-(\lambda+\rho)$ hence obtained are
$(4,3,3),(5,4,1),(7,3,0),(9,1,0),$ $(7,5,-2),(9,3,-2)$. The last two are not
in the Weyl chamber, $(4,3,3)\trianglelefteq\mu$, and none of the others are
$\trianglelefteq\mu$, so the only contribution comes from
$K_{(4,3,3)(4,3,3)}=1$, which tells us that $c_{(5,3,2)(4,3,3)}^{(9,6,5)}=1$.

Another way to do the same computation, which gives us a polynomial time
algorithm is to firstly find out all the partitions which are
$\trianglelefteq\mu$, and in this case the only such partition is $(4,3,3)$.
Next we see if $(4,3,3)$ can be written as $\eta(\nu+\rho)-(\lambda+\rho)$,
which is true for $\eta$ being the trivial permutation, which tells us that
the only contribution comes from $K_{(4,3,3)(4,3,3)}=1$, hence
$c_{(5,3,2)(4,3,3)}^{(9,6,5)}=1$.

######  Theorem 2 (Stienberg’s formula).

LR-coefficients can be given via the following formula:

$c_{\lambda\mu}^{\nu}=\sum_{\sigma,\tau\in
S_{n}}(-1)^{\sigma\tau}\mathfrak{P}(\sigma(\lambda+\rho)+\tau(\mu+\rho)-(\nu+2\rho))$

where $\mathfrak{P}$ is the Kostant partition function.

###### Proof.

If $\lambda,\mu$ are partitions of $n$, we know that

$K_{\alpha\beta}=\sum_{\sigma\in
S_{n}}(-1)^{\sigma}\mathfrak{P}(\sigma(\alpha+\rho)-(\beta+\rho))$

Also the partition $\beta$ need not be ordered to define Kostka numbers. By
the above corollary, we have that

$c_{\lambda\mu}^{\nu}=\sum_{\eta\in
S_{n}}(-1)^{\eta}K_{\mu\tau(\eta(\nu+\rho)-(\lambda+\rho))}$

if $\tau(\eta(\nu+\rho)-(\lambda+\rho))\trianglelefteq\mu$, then the
corresponding Kostka number is zero. Note that $\tau$ was chosen so that
$\tau(\eta(\nu+\rho)-(\lambda+\rho))$ is in general position. We could make
any choice of $\tau\in S_{n}$ and keep the formula invariant ( a bit more
cumbersome to compute, maybe). We choose $\tau=\eta^{-1}$ for each of the
terms, to get

$\displaystyle c_{\lambda\mu}^{\nu}$ $\displaystyle=\sum_{\tau\in
S_{n}}(-1)^{\tau}K_{\mu\nu+\rho-\tau(\lambda+\rho))}$
$\displaystyle=\sum_{\tau\in S_{n}}(-1)^{\tau}\sum_{\sigma\in
S_{n}}(-1)^{\sigma}\mathfrak{P}(\sigma(\mu+\rho)-(\nu+\rho-\tau(\lambda+\rho)+\rho))$
$\displaystyle=\sum_{\tau\in S_{n}}\sum_{\sigma\in
S_{n}}(-1)^{\tau}(-1)^{\sigma}\mathfrak{P}(\sigma(\mu+\rho)+\tau(\lambda+\rho)-(\nu+2\rho))$
$\displaystyle=\sum_{\tau,\sigma\in
S_{n}}(-1)^{\tau\sigma}\mathfrak{P}(\sigma(\mu+\rho)+\tau(\lambda+\rho)-(\nu+2\rho))$

which proves the Stienberg’s formula. ∎

##  4.. Algorithm

Given a black box which gives us the values of Kostka numbers $K_{\mu\psi}$ in
polynomial time , we will give a polynomial time algorithm to compute the LR
coefficients. This algorithm formalises the idea of the computation in
previous section. We write the steps of the algorithm and then compute the
complexity:

  1. (1)

Input a positive integer $n$ and partitions in the form of an ordered $n-$
touple $\lambda,\mu,\nu$, and initialize the integer $c_{\lambda\mu}^{\nu}=0$.

  2. (2)

List $\psi$ such that $\psi\trianglelefteq\mu$.

  3. (3)

For each $\psi$ in the list, check if
$\psi=\tau(\eta(\nu+\rho)-(\lambda+\rho))$ for some $\eta,\tau\in S_{n}$:

    1. (a)

Set
$\psi^{(1)}:=(\psi_{1}+\lambda_{1}+n-1,\psi_{2}+\lambda_{1}+n-1,\ldots,\psi_{n}+\lambda_{1}+n-1)$
and $(\nu+\rho)^{(1)}:=\nu+\rho$

    2. (b)

If no entries of $\psi^{(1)}$ match with any entries in $(\nu+\rho)^{(1)}$,
then $\psi\neq\tau(\eta(\nu+\rho)-(\lambda+\rho))$ for any $\eta,\tau\in
S_{n}$.

    3. (c)

Otherwise say the $j^{th}$ entry $\psi_{j}+\lambda_{1}+n-1$ is equal to the
$k^{th}$ entry of $(\nu+\rho)$, namely $\nu_{k}+n-k$.

    4. (d)

Set
$\psi^{(2)}:=(\psi_{1}+\lambda_{2}+n-2,\psi_{2}+\lambda_{1}+n-2,\ldots,\widehat{\psi_{j}+\lambda_{2}+n-2},\ldots,\psi_{n}+\lambda_{2}+n-2)$,
where the $j^{th}$ entry has been omitted. Similarly omit the $k^{th}$ entry
from $(\nu+\rho)^{(1)}$ to get $(\nu+\rho)^{(2)}$.

    5. (e)

Repeat Steps $(b),(c),(d)$ on $\psi^{(2)},(\nu+\rho)^{(2)}$, to get
$\psi^{(3)},(\nu+\rho)^{(3)}$, and continue till either no entries match, or
we reach $\psi^{(n+1)},(\nu+\rho)^{(n+1)}$ which are both empty, hence we
stop. In this case, the positions of entries omitted in $(\nu+\rho)$ gives us
the permutation $\eta$.

If true then add $(-1)^{\eta}K_{\mu\psi}$ to $c_{\lambda\mu}^{\nu}$.

  4. (4)

Output $c_{\lambda\mu}^{\nu}$.

Step 2 can be done in $O(\mathbf{size}(\mu)^{n})$ as it involves finding
$\psi=(\psi_{1},\psi_{2},\ldots,\psi_{n})$, and $\psi\trianglelefteq\mu$ gives
us a rough bound that $\psi_{i}\leq|\mu|/i$ .

Step 3 has a loop, where we are trying to find if the given $\psi$ can be
written as $(\nu+\rho)-(\lambda+\rho)$, note that $\psi^{(k)}$ are all
preordered integer touples, so traversing and finding matching with
$(\nu+\rho)^{(k)}$ takes $\sim k$ time, so in total it takes $O(n^{2})$ time.

Step 1 and Step 4 are input and output, so they are
$O(\mathbf{size}(\lambda,\mu,\nu)$.

######  Conclusion.

With this algorithm, we get that knowing Kostka numbers, one can generate LR
coefficents in polynomial time. We already know via [KTT04] that Kostka
numbers can be expressed via LR coefficents in linear (polynomial) time, which
tells us that they belong to the same class of decision problems. In [Nar06],
Hariharan shows that the computational complexity of computing either LR
coefficients or Kostka numbers is $\\#P-$complete. Our result reinforces this
notion by showing polynomial time equivalence between the two.

##  5.. Acknowledgement

I express my gratitude to C.S. Rajan for the many valuable discussions while I
was working on this paper, to Hariharan Narayan and Piyush Srivastava for
informing me about the computational aspects of this problem, and other
possible extensions. I also sincerely thanks to Gaurav Bhatnagar, Manodeep
Raha, Soumyadip Sahu ,Ashutosh Shankar for their suggestions. I’m especially
thankful to Per Alexandersson for pointing out that my initial result could be
used to prove Steinberg’s formula. I’m extremely grateful to Ashoka University
for warm hospitality and for providing a productive working atmosphere during
my visit.

## References

  * [FH91] William Fulton and Joe Harris.  A First Course in Representation Theory, volume 129.  Springer, 1991.
  * [KTT04] Ronald C King, Christophe Tollu, and Frédéric Toumazet.  Stretched Littlewood-Richardson and Kostka coefficients.  In CRM Proceedings and Lecture Notes Vol. 34, pages 99–112. American Mathematical Society, 2004.
  * [Led06] Mathias Lederer.  On a formula for the Kostka numbers.  Annals of Combinatorics, 10(3):389–394, 2006.
  * [Nar06] Hariharan Narayanan.  On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients.  Journal of Algebraic Combinatorics, 24(3):347–354, 2006.
  * [Ste61] Robert Steinberg.  A general Clebsch-Gordan theorem.  Bulletin of the American Mathematical Society, 67(4):406–407, 1961\.


K_{3}}{v_{3}}\left(\frac{\omega_{n}^{2}}{v_{3}^{2}}+q^{2}+\frac{\Delta_{3}^{2}}{v_{3}^{2}}\right)^{-1}\end{pmatrix}$
(114)

Setting the functional derivative $\delta F_{\text{var}}/\delta
G_{ij}(q,\omega_{n})$ to zero, we arrive at the following coupled equations

$\displaystyle G_{11}^{-1}(q,\omega_{n})$ $\displaystyle=\frac{v_{1}}{\pi
K_{1}}\left(\frac{\omega_{n}^{2}}{v_{1}^{2}}+q^{2}\right)+\frac{4}{\pi^{2}\alpha^{2}}\left(|g_{2}|e^{-\frac{2T}{L}\sum_{n,q}[G_{11}+G_{33}]}\cos[4\text{Tr}G_{13}]+|g_{3}|e^{-\frac{2T}{L}\sum_{n,q}[G_{11}+G_{22}]}\cos[4\text{Tr}G_{12}]\right),$
(115) $\displaystyle G_{22}^{-1}(q,\omega_{n})$
$\displaystyle=\frac{v_{2}}{\pi
K_{2}}\left(\frac{\omega_{n}^{2}}{v_{2}^{2}}+q^{2}\right)+\frac{4}{\pi^{2}\alpha^{2}}\left(|g_{1}|e^{-\frac{2T}{L}\sum_{n,q}[G_{22}+G_{33}]}\cos[4\text{Tr}G_{23}]+|g_{3}|e^{-\frac{2T}{L}\sum_{n,q}[G_{11}+G_{22}]}\cos[4\text{Tr}G_{12}]\right),$
$\displaystyle G_{33}^{-1}(q,\omega_{n})$ $\displaystyle=\frac{v_{3}}{\pi
K_{3}}\left(\frac{\omega_{n}^{2}}{v_{3}^{2}}+q^{2}\right)+\frac{4}{\pi^{2}\alpha^{2}}\left(|g_{2}|e^{-\frac{2T}{L}\sum_{n,q}[G_{11}+G_{33}]}\cos[4\text{Tr}G_{13}]+|g_{1}|e^{-\frac{2T}{L}\sum_{n,q}[G_{22}+G_{33}]}\cos[4\text{Tr}G_{23}]\right),$
$\displaystyle G_{12}^{-1}=\Delta_{12}$
$\displaystyle=\frac{4}{\pi^{2}\alpha^{2}}|g_{3}|e^{-\frac{2T}{L}\sum_{n,q}[G_{11}+G_{22}]}\sinh[4\text{Tr}G_{12}],$
$\displaystyle G_{13}^{-1}=\Delta_{13}$
$\displaystyle=\frac{4}{\pi^{2}\alpha^{2}}|g_{2}|e^{-\frac{2T}{L}\sum_{n,q}[G_{11}+G_{33}]}\sinh[4\text{Tr}G_{13}],$
$\displaystyle G_{23}^{-1}=\Delta_{23}$
$\displaystyle=\frac{4}{\pi^{2}\alpha^{2}}|g_{1}|e^{-\frac{2T}{L}\sum_{n,q}[G_{22}+G_{33}]}\sinh[4\text{Tr}G_{23}].$

From the above equations, it is apparent that $\Delta_{ij}=0$ is always
satisfied. Below we adopt this solution, and the equations then become

$\displaystyle G_{1}^{-1}(q,\omega_{n})$ $\displaystyle=\frac{v_{1}}{\pi
K_{1}}\left(\frac{\omega_{n}^{2}}{v_{1}^{2}}+q^{2}\right)+\frac{4}{\pi^{2}\alpha^{2}}\left(|g_{2}|e^{-\frac{2T}{L}\sum_{n,q}[G_{1}(q,\omega_{n})+G_{3}(q,\omega_{n})]}+|g_{3}|e^{-\frac{2T}{L}\sum_{n,q}[G_{1}(q,\omega_{n})+G_{2}(q,\omega_{n})]}\right)$
(116) $\displaystyle G_{2}^{-1}(q,\omega_{n})$ $\displaystyle=\frac{v_{2}}{\pi
K_{2}}\left(\frac{\omega_{n}^{2}}{v_{2}^{2}}+q^{2}\right)+\frac{4}{\pi^{2}\alpha^{2}}\left(|g_{1}|e^{-\frac{2T}{L}\sum_{n,q}[G_{2}(q,\omega_{n})+G_{3}(q,\omega_{n})]}+|g_{3}|e^{-\frac{2T}{L}\sum_{n,q}[G_{1}(q,\omega_{n})+G_{2}(q,\omega_{n})]}\right)$
$\displaystyle G_{3}^{-1}(q,\omega_{n})$ $\displaystyle=\frac{v_{3}}{\pi
K_{3}}\left(\frac{\omega_{n}^{2}}{v_{3}^{2}}+q^{2}\right)+\frac{4}{\pi^{2}\alpha^{2}}\left(|g_{2}|e^{-\frac{2T}{L}\sum_{n,q}[G_{1}(q,\omega_{n})+G_{3}(q,\omega_{n})]}+|g_{1}|e^{-\frac{2T}{L}\sum_{n,q}[G_{2}(q,\omega_{n})+G_{3}(q,\omega_{n})]}\right)$

We can insert Eq.(114) to obtain equations for $\Delta_{i}$. We do this in the
zero temperature limit, where

$-\frac{2T}{L}\sum_{n,q}G_{i}(q,\omega_{n})=-2\pi
K_{i}\int\frac{d^{2}\bm{q}}{(2\pi)^{2}}\frac{1}{\bm{q}^{2}+m_{i}^{2}}\approx-\frac{K_{i}}{2}\ln\left(1+\frac{\Lambda^{2}}{m_{i}^{2}}\right)$
(117)

where $\Lambda$ is some UV cutoff for the momentum. Making use of this result,
the equations for $\Delta_{i}$’s are

$\displaystyle\delta_{1}^{2}$ $\displaystyle=\frac{4K_{1}}{\pi
v_{1}(\alpha\Lambda)^{2}}\left[|g_{2}|\left(\frac{\delta_{1}^{2}}{1+\delta_{1}^{2}}\right)^{\frac{K_{1}}{2}}\left(\frac{\delta_{3}^{2}}{1+\delta_{3}^{2}}\right)^{\frac{K_{3}}{2}}+|g_{3}|\left(\frac{\delta_{1}^{2}}{1+\delta_{1}^{2}}\right)^{\frac{K_{1}}{2}}\left(\frac{\delta_{2}^{2}}{1+\delta_{2}^{2}}\right)^{\frac{K_{2}}{2}}\right]$
(118) $\displaystyle\delta_{2}^{2}$ $\displaystyle=\frac{4K_{2}}{\pi
v_{2}(\alpha\Lambda)^{2}}\left[|g_{1}|\left(\frac{\delta_{2}^{2}}{1+\delta_{2}^{2}}\right)^{\frac{K_{2}}{2}}\left(\frac{\delta_{3}^{2}}{1+\delta_{3}^{2}}\right)^{\frac{K_{3}}{2}}+|g_{3}|\left(\frac{\delta_{1}^{2}}{1+\delta_{1}^{2}}\right)^{\frac{K_{1}}{2}}\left(\frac{\delta_{2}^{2}}{1+\delta_{2}^{2}}\right)^{\frac{K_{2}}{2}}\right]$
$\displaystyle\delta_{3}^{2}$ $\displaystyle=\frac{4K_{3}}{\pi
v_{3}(\alpha\Lambda)^{2}}\left[|g_{2}|\left(\frac{\delta_{1}^{2}}{1+\delta_{1}^{2}}\right)^{\frac{K_{1}}{2}}\left(\frac{\delta_{3}^{2}}{1+\delta_{3}^{2}}\right)^{\frac{K_{3}}{2}}+|g_{1}|\left(\frac{\delta_{2}^{2}}{1+\delta_{2}^{2}}\right)^{\frac{K_{2}}{2}}\left(\frac{\delta_{3}^{2}}{1+\delta_{3}^{2}}\right)^{\frac{K_{3}}{2}}\right]$

where we have used $\delta_{i}=\Delta_{i}/(v_{i}\Lambda)$. We usually deal
with the case that $\delta_{i}\ll 1$, so the above equations become (setting
$\alpha\Lambda=1$)

$\displaystyle\delta_{1}^{2}$ $\displaystyle=\frac{4K_{1}}{\pi
v_{1}}|\delta_{1}|^{K_{1}}\left(|g_{2}||\delta_{3}|^{K_{3}}+|g_{3}||\delta_{2}|^{K_{2}}\right),$
(119) $\displaystyle\delta_{2}^{2}$ $\displaystyle=\frac{4K_{2}}{\pi
v_{2}}|\delta_{2}|^{K_{2}}\left(|g_{1}||\delta_{3}|^{K_{3}}+|g_{3}||\delta_{1}|^{K_{1}}\right),$
$\displaystyle\delta_{3}^{2}$ $\displaystyle=\frac{4K_{3}}{\pi
v_{3}}|\delta_{3}|^{K_{3}}\left(|g_{2}||\delta_{1}|^{K_{1}}+|g_{1}||\delta_{2}|^{K_{2}}\right).$

It is apparent from these equations that $\Delta_{i}=0$ is always a trivial
solution.

The cases with frustration, i.e. when $\operatorname{sgn}(g_{1}g_{2}g_{3})<0$,
are more involved, due to the possible presence of classically degenerate
ground states. For instance, in the case when $g_{1}=g_{2}=g_{3}<0$, there
exist several lines in the parameter space which correspond to the degenerate
classical ground state. However, as we see from the RG analysis, this
accidental symmetric case $g_{1}=g_{2}=g_{3}$ is not protected by any symmetry
and is unstable, so we generally do not expect that they are all equal.
Therefore, without loss of generality, we assume $|g_{1}|>|g_{2}|>|g_{3}|$. In
this case, the classical ground state is unique. For instance, when all
$g_{1,2,3}<0$, the classical ground state is $\phi_{1,2}=0$ and
$\phi_{3}=\pm\pi/2$. After shifting $\phi_{3}$ by $\pm\pi/2$ we can still
average every field around $0$. The derivation of the gap equations is
parallel to outlined above, with the only difference being the replacement of
$|g_{3}|$ with $-|g_{3}|$. Therefore, we obtain the gap equations for the case
with frustration

$\displaystyle\delta_{1}^{2}$ $\displaystyle=\frac{4K_{1}}{\pi
v_{1}}|\delta_{1}|^{K_{1}}\left(|g_{2}||\delta_{3}|^{K_{3}}-|g_{3}||\delta_{2}|^{K_{2}}\right),$
(120) $\displaystyle\delta_{2}^{2}$ $\displaystyle=\frac{4K_{2}}{\pi
v_{2}}|\delta_{2}|^{K_{2}}\left(|g_{1}||\delta_{3}|^{K_{3}}-|g_{3}||\delta_{1}|^{K_{1}}\right),$
$\displaystyle\delta_{3}^{2}$ $\displaystyle=\frac{4K_{3}}{\pi
v_{3}}|\delta_{3}|^{K_{3}}\left(|g_{2}||\delta_{1}|^{K_{1}}+|g_{1}||\delta_{2}|^{K_{2}}\right).$

Figure 9: Solution of the gap equations with and without frustration. Here we
choose $v_{1,2,3}=v$ and $g_{1}=0.3v$, $g_{2}=0.25v$. The Luttinger parameters
are shown in the figure. In the case without frustration (left panel and
solved from Eq.(119)), $\Delta_{1,2,3}$ are comparable to each other. In the
case with frustration (middle and right panels, solved from Eq.(120)), all
gaps get suppressed compared to the case without frustration. In particular,
$\Delta_{1}$ gets suppressed the most and when $|g_{3}|$ gets larger, it
becomes the smallest compared to $\Delta_{2}$ and $\Delta_{3}$.

In Fig.(9), we shown the comparison between the solutions of Eq.(119) and
Eq.(120). We choose the parameters $v_{1,2,3}=v$, $g_{1}=0.3v$, $g_{2}=0.25v$,
$K_{1}-0.2=K_{3}-0.1=K_{2}=K$ such that in the case without frustration all
induced gaps are comparable. We clearly see from the middle and right panels
of Fig.(9) that in the presence of frustration, all gaps get suppressed
compared to the case without frustration. $\Delta_{1}$ gets suppressed the
most and when $|g_{3}|$ gets as large as $0.2v$, it becomes much smaller than
the other two and therefore a gap hierarchy develops.

##  VI VI. Transport property

We first show if only the CDW order is considered in the inter-wire coupling,
there is no transverse current. To see this, we note the inter-wire coupling
Hamiltonian for CDW order is

$\displaystyle H_{c}$ $\displaystyle=J\sum_{\braket{ij}}\int
dxO_{\text{CDW}}^{\dagger}(i,x)O_{\text{CDW}}(j,x)+\text{h.c.}$ (121)
$\displaystyle=J\sum_{\braket{ij},\lambda\lambda^{\prime}}\int
dx\psi^{\dagger}_{i,-,\lambda}(x)\psi_{i,+,\lambda}(x)\psi^{\dagger}_{j,+,\lambda^{\prime}}(x)\psi_{j,-,\lambda^{\prime}}(x)+(i\leftrightarrow
j).$

which is the most relevant one when the system is in the massive phase with
gaps in all $\phi_{2},\phi_{3},\phi_{4}$ sectors and in the presence of strong
repulsion. From this Hamiltonian, one can calculate the current density
operator from the continuity equation $\partial_{y}j_{y}=i[\rho(i,x),H_{c}]=0$
and find the current vanishes. Note the vanishing is local, i.e. it’s not
because two current operators on $i$ and $j$ cancel each other, but rather the
current on each wire vanishes. Therefore, we see that by only turning on the
CDW coupling is not enough for obtaining a finite cross-wire conductivity, we
must have other couplings.

The most trivial one, will be the single particle tunneling (keeping only the
nearest neighbor),

$H_{t}=t_{\bot}\sum_{i,rr^{\prime},\lambda}\int
dx\psi_{r,\lambda}^{\dagger}(i,x)\psi_{r^{\prime},\lambda}(i+1,x)+\text{h.c.}$
(122)

The tunneling charge current due to the presence of this Hamiltonian is given
by the continuity equation, and we obtain

$\displaystyle j_{y}(i,x)$
$\displaystyle=ict_{\bot}\sum_{r,\lambda}\left(\psi^{\dagger}_{r,\lambda}(i,x)\psi_{r,\lambda}(i+1,x)-\psi^{\dagger}_{r,\lambda}(i+1,x)\psi_{r,\lambda}(i,x)\right),$
(123) $\displaystyle j_{y}(q_{y},x)$
$\displaystyle=-2ct_{\bot}\sum_{r,\lambda}\int_{-\pi}^{\pi}dk_{y}\psi^{\dagger}_{r,\lambda}(k_{y}-\frac{q_{y}}{2},x)\psi_{r,\lambda}(k_{y}+\frac{q_{y}}{2},x)\sin
k_{y}e^{i\frac{q_{y}}{2}},$

where $c$ is the spacing between adjacent wires, and since $j_{y}(i,x)$ is
Hermitian, $j_{y}(q_{y},x)^{\dagger}=j_{y}(-q_{y},x).$ Below, we will evaluate
the current-current correlation in the Hamiltonian without $H_{t}$, similar to
the approach in Ref.[110]. However, we will keep $H_{c}$ to the first order as
in a perturbation theory. According to Kubo formula, the real part of
conductivity is given by

$\text{Re}\sigma_{\bot}(\omega)=-\frac{e^{2}}{\omega}\text{Im}\left[\lim_{q_{y}\to
0}\int dx\Pi_{\bot}^{R}(q_{y},x,\omega)\right]$ (124)

where $\Pi_{\bot}^{R}(q_{y},x,\omega)$ is the Fourier transform of the
retarded current-current correlation function, which can be obtained from

$\Pi_{\bot}(q_{y},x,i\omega_{n})=\braket{j_{y}(q_{y},x,i\omega_{n})j_{y}(-q_{y},0,-i\omega_{n})}$
(125)

by analytic continuation. Here we have assumed translation symmetry. To the
first order in $H_{c}$, we have

$\displaystyle\lim_{q_{y}\to 0}\int
dx\Pi_{\bot}(q_{y},x,i\omega_{n})=\frac{1}{\beta}\sum_{ik_{n}}\sum_{r,\lambda}\int\frac{dk_{x}dk_{y}}{(2\pi)^{2}}4c^{2}t_{\bot}^{2}\sin^{2}k_{y}G_{r,\lambda}(k_{x},ik_{n})G_{r,\lambda}(k_{x},ik_{n}+i\omega_{n})$
(126) $\displaystyle+$
$\displaystyle\frac{J}{\beta^{2}}\sum_{ik_{n},ip_{n}}\sum_{r,\lambda}\int\frac{d^{2}\bm{k}d^{2}\bm{p}}{(2\pi)^{4}}4c^{2}t_{\bot}^{2}\sin^{2}k_{y}\sin^{2}p_{y}G_{r,\lambda}(k_{x},ik_{n})G_{r,\lambda}(k_{x},ik_{n}+i\omega_{n})G_{-r,\lambda}(p_{x},ip_{n})G_{-r,\lambda}(p_{x},ip_{n}+i\omega_{n}).$

Here we used the fact that all the Green’s functions are evaluated in the
decoupled Hamiltonian, so these are essentially 1D Hamiltonians and do not
depend on $k_{y}$ or the wire index. Note in the second line of Eq.(126) the
difference in the $r$-index between these Green’s functions are due to the
nature of the CDW interaction $H_{c}$. Upon expressing the Green’s functions
using their spectral representations

$G(k_{x},ik_{n})=\frac{1}{2\pi}\int
d\varepsilon\frac{A(k_{x},\varepsilon)}{ik_{n}-\varepsilon},~{}~{}A(k_{x},\varepsilon)=-2\text{Im}G^{R}(k_{x},\varepsilon)$
(127)

and analytically continuing on the real frequency axis by changing
$i\omega_{n}$ to $\omega+i0^{+}$, we obtain (after summing over $ik_{n}$)

$\displaystyle\text{Re}\sigma_{\bot}(\omega)=\frac{e^{2}ct_{\bot}^{2}}{2\pi}\sum_{r,\lambda}\int
dx\int
d\varepsilon\frac{n_{F}(\varepsilon)-n_{F}(\varepsilon+\omega)}{\omega}A_{r,\lambda}(x,\varepsilon)A_{r,\lambda}(-x,\varepsilon+\omega)$
(128) $\displaystyle+\frac{e^{2}Jt_{\bot}^{2}}{8\pi^{3}}\sum_{r,\lambda}\int
dxdx^{\prime}P\int d\epsilon
d\epsilon^{\prime}\frac{n_{F}(\epsilon)-n_{F}(\epsilon^{\prime})}{\omega+\epsilon-\epsilon^{\prime}}A_{r,\lambda}(x,\epsilon)A_{r,\lambda}(-x,\epsilon^{\prime})\int
d\varepsilon\frac{n_{F}(\varepsilon)-n_{F}(\varepsilon+\omega)}{\omega}A_{-r,\lambda}(x^{\prime},\varepsilon)A_{-r,\lambda}(-x^{\prime},\varepsilon+\omega),$

where in the second line we use $P\int$ to denote the principle value
integral. To proceed with obtaining the temperature , we need the spectral
function for the decoupled 1D system. But here we can estimate the magnitude
of $\sigma_{\bot}$ from the its prefactors (after restoring $\hbar$
everywhere),

$\sigma_{\bot}(T)=\frac{e^{2}}{h}4(ack_{F}^{2})\left(\frac{t_{\bot}}{E_{F}}\right)^{2}F\left(\frac{T}{E_{F}}\right)\approx
18\frac{e^{2}}{h}\left(\frac{t_{\bot}}{E_{F}}\right)^{2}F\left(\frac{T}{E_{F}}\right)~{}~{}\text{for}~{}~{}k_{F}\approx\frac{\pi}{2a}$
(129)

where $F$ is some dimensionless function that comes from the integral
involving the spectral functions.

###  VI.1 A. Single-particle tunneling in the gapless case

We begin by discussing the conductivity due to the single particle tunneling
process in the gapless case, i.e. all the four $\phi_{j}$ fields are gapless.
As shown above, this requires the calculation of the single particle spectral
function. By definition, the retarded single particle Green’s function is
given by

$G^{R}_{r,\lambda}(x,t)=-i\Theta(t)\braket{\\{\psi_{r,\lambda}(x,t),\psi^{\dagger}_{r,\lambda}(0,0)\\}}=-i\Theta(t)(G_{r,\lambda}(x,t)+G_{r,\lambda}(-x,-t))$
(130)

where

$G_{r,\lambda}(x,t)=\lim_{\alpha\to
0}\frac{e^{irk_{F}x}}{2\pi\alpha}\braket{e^{i\theta_{\lambda}(x,t)-ir\phi_{\lambda}(x,t)}e^{-i\theta_{\lambda}(0,0)+ir\phi_{\lambda}(0,0)}}$
(131)

according to Eq.(25). Without loss of generality, we take $r=+$ and
$\lambda=\uparrow u$. Using Eq.(27) we have

$G_{r,\lambda}(x,t)=\lim_{\alpha\to
0}\frac{e^{irk_{F}x}}{2\pi\alpha}\prod_{j=0}^{3}\braket{e^{\frac{i}{2}[\theta_{j}(x,t)-\phi_{j}(x,t)]}e^{-\frac{i}{2}[\theta_{j}(0,0)-\phi_{j}(0,0)]}}_{j}$
(132)

For Gaussian models we have
$\braket{e^{iA}e^{-iB}}=\exp\left(-\frac{1}{2}\braket{A^{2}}-\frac{1}{2}\braket{B^{2}}+\braket{AB}\right)$,
thus

$\braket{e^{\frac{i}{2}[\theta_{j}(x,t)-\phi_{j}(x,t)]}e^{-\frac{i}{2}[\theta_{j}(0,0)-\phi_{j}(0,0)]}}_{j}=\exp\left[\frac{1}{4}\braket{\left(\theta_{j}(x,t)-\phi_{j}(x,t)\right)\left(\theta_{j}(0,0)-\phi_{j}(0,0)\right)}_{j}-\frac{1}{4}\braket{(\theta_{j}-\phi_{j})^{2}}_{j}\right].$
(133)

Using Eq.(46), (47) and (48), it is easy to see

$\braket{e^{\frac{i}{2}[\theta_{j}(x,t)-\phi_{j}(x,t)]}e^{-\frac{i}{2}[\theta_{j}(0,0)-\phi_{j}(0,0)]}}_{j}=\left(\frac{a}{a+i(v_{j}t-x)}\right)^{1/4}\left(\frac{a^{2}}{x^{2}+(iv_{j}t+a)^{2}}\right)^{\frac{K_{j}+\frac{1}{K_{j}}-2}{16}}.$
(134)

As a result, we have,

$G_{+,\uparrow
A}(x,t)=\frac{e^{ik_{F}x}}{2\pi}\prod_{j=0}^{3}\left(\frac{1}{a+i(v_{j}t-x)}\right)^{1/4}\left(\frac{a^{2}}{x^{2}+(iv_{j}t+a)^{2}}\right)^{\gamma_{j}/2},~{}~{}~{}\gamma_{j}=\frac{K_{j}+\frac{1}{K_{j}}-2}{8}$
(135)

In fact, this form does not depend on $\lambda$. For $r=-$, the only changes
is to replace $x$ with $-x$ in the above expression.

For comparison, we note in the conventional two-component case, we have

$G(x,t)\sim\prod_{j=c,s}\left(\frac{1}{a+i(v_{j}t-x)}\right)^{1/2}\left(\frac{a^{2}}{x^{2}+(iv_{j}t+a)^{2}}\right)^{\gamma_{j}/2},~{}~{}~{}\gamma_{j}=\frac{K_{j}+\frac{1}{K_{j}}-2}{4}.$
(136)

Using this result, and if we neglect the correction due to the CDW order
coupling, we have

$\displaystyle\text{Re}\sigma_{\bot}(\omega\to 0,T)$ $\displaystyle\sim\int
dx\int
d\varepsilon\frac{1}{4T}\text{sech}^{2}\left(\frac{\varepsilon}{2T}\right)A(x,\varepsilon)A(-x,\varepsilon+\omega)$
(137) $\displaystyle\sim\int dx\int
d\varepsilon\frac{1}{4T}\text{sech}^{2}\left(\frac{\varepsilon}{2T}\right)F(x,\varepsilon)$

where $F(x,\varepsilon)$ obeys

$F\left(ax,\frac{\varepsilon}{a}\right)=\frac{1}{a^{2\gamma}}F(x,\varepsilon),~{}~{}~{}\gamma=\sum_{j}\gamma_{j}.$
(138)

The spectral function $A(x,\varepsilon)$ has the following properties:

$A(x=0,\varepsilon)=N(\varepsilon)\sim|\varepsilon|^{\gamma},~{}~{}~{}A(x\gg
1/\varepsilon,\varepsilon)\sim\frac{\cos{\varepsilon x}}{x^{\gamma}},$ (139)

so the function $F(x,\varepsilon)$ behaves like

$\displaystyle F(x,\varepsilon)$
$\displaystyle\sim\varepsilon^{2\gamma}~{}\text{for}~{}x\ll 1/\varepsilon,$
(140) $\displaystyle\sim\frac{1}{x^{2\gamma}}~{}\text{for}~{}x\gg
1/\varepsilon.$

Therefore

$\text{Re}\sigma_{\bot}(\omega\to 0,T)\sim\int
d\varepsilon\frac{1}{4T}\text{sech}^{2}\left(\frac{\varepsilon}{2T}\right)\left(\int_{0}^{1/\varepsilon}dx\varepsilon^{2\gamma}+\int_{1/\varepsilon}^{+\infty}dx\frac{\cos{2\varepsilon
x}}{x^{2\gamma}}\right)\sim T^{2\gamma-1}.$ (141)

In the main text, we introduce the scaling dimension of the single particle
hopping $\alpha_{e}$, which is related to $\gamma$ simply by
$\gamma=\alpha_{e}-1$.

###  VI.2 B. Single-particle tunneling in the gapped case

When there is a gap opening in either one or more of the $\phi_{j}$ fields,
the total single particle density of states has a gap structure. This is
because the total real pace Green’s function is a product of the four
component, as shown in Eq.(135). Consequently, the spectral function (and
hence the density of states), which is the Fourier transform of Eq.(135), is a
convolution of different components. It is this convolution that leads to a
gap in the total spectral function. For two component 1DEG this was
demonstrated in Ref.[109] If there is a gap in the total density of states,
the conductivity becomes zero when $T$ is below the gap energy scale. However,
when $T$ is well above the energy scale set by the gap, Eq.(141) still
applies.

###  VI.3 C. Josephson tunneling in the gapped case

Unlike the single particle tunneling, the pair or quadruple hopping process
does not depend on the single particle density of states, and can contribute
to the cross wire conductivity even in the gapped phase and when $T$ not well
above the gap energy scale. Below we discuss this Josephson tunneling due to
charge-2e and charge-4e orders.

####  VI.3.1 charge-2e superconductivity

We take spin-triplet pseudospin-triplet pairing order parameter in Eq.(68) as
an example. Assuming we are in the partially gapped phase when $\phi_{2,3}$
are gapped. The tunneling is governed by the Hamiltonian

$\displaystyle H_{J}$ $\displaystyle=J_{s}\sum_{\braket{y,y^{\prime}}}\int
dxO_{T_{1},S}^{\dagger}(x,y)O_{T_{1},S}(x,y^{\prime})+\text{h.c.}$ (142)
$\displaystyle=\tilde{J}_{s}\sum_{\braket{y,y^{\prime}}}\int
dx\cos\left[\theta_{0}(x,y)+\theta_{1}(x,y)-\theta_{0}(x,y^{\prime})-\theta_{1}(x,y^{\prime})\right],$

where $\tilde{J}_{s}=J_{s}\delta_{2}^{K_{2}/2}\delta_{3}^{K_{3}/2}$ and
$J_{s}\sim t_{\bot}^{2}/E_{F}$. On the other hand, the local charge density
operator is given by $\rho_{0}(x,y)=\frac{1}{\pi}\partial_{x}\phi_{0}(x,y)$.
Then according to the continuity equation, the transverse current density is
found to be

$j_{y}(x)=\tilde{J}_{s}c\sin[\theta_{0}(x,y+1)+\theta_{1}(x,y+1)-\theta_{0}(x,y)-\theta_{1}(x,y)]$
(143)

which is the Josephson current. To evaluate the current-current correlation in
the decoupled 1D system, we note that only the correlation involving two
current operators with the same $y$ survives. Thus we have

$\displaystyle\Pi_{\bot}(x,y,\tau)$
$\displaystyle=\tilde{J}_{s}^{2}c^{2}\braket{\sin[\theta_{0}(x,y+1)+\theta_{1}(x,y+1)-\theta_{0}(x,y)-\theta_{1}(x,y)]\sin[\theta_{0}(0,0+1)+\theta_{1}(0,0+1)-\theta_{0}(0,0)-\theta_{1}(0,0)]}$
(144)
$\displaystyle=\frac{\tilde{J}_{s}^{2}c^{2}}{2}\left(\frac{a^{2}}{x^{2}+v_{0}^{2}\tau^{2}+a^{2}}\right)^{\frac{1}{2K_{0}}+\frac{1}{2K_{1}}}\delta_{y,0}.$

Therefore

$\Pi_{\bot}(\bm{q}\to 0,\omega)=\int dxdte^{i\omega
t}\sum_{y}\Pi_{\bot}(x,y,t)\sim\tilde{J}_{s}^{2}c^{2}\omega^{1/K_{0}+1/K_{1}-2}$
(145)

and

$\text{Re}\sigma(\omega)\sim\tilde{J}_{s}^{2}c^{2}\omega^{1/K_{0}+1/K_{1}-3}\to\text{Re}\sigma(T)\sim\tilde{J}_{s}^{2}c^{2}T^{1/K_{0}+1/K_{1}-3}.$
(146)

####  VI.3.2 charge-4e superconductivity

Like the charge-2e superconductivity case, the tunneling current is determined
by the coupling Hamiltonian,

$\displaystyle H_{J}$
$\displaystyle=\tilde{J}_{s}\sum_{\braket{y,y^{\prime}}}\int
dx\cos\left[2\theta_{0}(x,y)-2\theta_{0}(x,y^{\prime})\right].$ (147)

The resulting current operator is

$j_{y}(x)=\tilde{J}_{s}c\sin[2\theta_{0}(x,y+1)-2\theta_{0}(x,y)].$ (148)

The calculation of conductivity is exactly the same as the 2e-SC case, with
the modification of $\theta_{0}\to 2\theta_{0}$ and hence $1/K_{0}\to
4/K_{0}$, and the final result is

$\text{Re}\sigma(T)\sim\tilde{J}_{s}^{2}c^{2}T^{4/K_{0}-3}$ (149)