# Schubert Products for Permutations with Separated Descents

Daoji Huang

###### Abstract

We say that two permutations $\pi$ and $\rho$ have _separated descents_ at
position $k$ if $\pi$ has no descents before position $k$ and $\rho$ has no
descents after position $k$. We give a counting formula, in terms of reduced
word tableaux, for computing the structure constants of products of Schubert
polynomials indexed by permutations with separated descents. Our approach uses
generalizations of Schützenberger’s jeu de taquin algorithm and the Edelman-
Greene correspondence via bumpless pipe dreams.

##  Introduction

Schubert polynomials are representatives of Schubert classes of the full flag
variety. Products of Schubert polynomials expand into a positive
$\mathbb{Z}$-linear combination of Schubert polynomials, and the coefficients
in this expansion are known as the _Schubert structure constants_. It is a
famous open problem in algebraic combinatorics to model the structure
constants nonnegatively using combinatorial objects that bypass geometry in
full generality; or in other words, to find a #P-algorithm that computes the
structure constants. For a more extensive introduction of this problem, see
e.g. [Len10].

The goal of this paper is to make some progress on this problem. We say that a
pair of permutations $\pi$ and $\rho$ have separated descents at position $k$
if $\pi$ has no descents before position $k$ and $\rho$ has no descents after
position $k$. This notion was first brought forth by Knutson and Zinn-Justin
[KZJ], where they derived a puzzle rule for this problem (that generalizes to
equivariant K-theory) from studying quiver varieties. The rule presented in
our work is a tableaux rule and uses only elementary combinatorial methods. In
particular, our result generalizes results of Kogan [Kog00], Knutson–Yong
[KY04], Lenart [Len10], Assaf [Ass17] where different rules were given for
solving the separated descents problem when one of the permutations is
grassmannian (i.e., has only a single descent). Our rule is also natural for
computing products of multiple Schubert polynomials indexed by permutations
with separated descents. This gives a generalization of Purbhoo–Sottile
[PS09], where products of multiple grassmannian permutations were considered.
We note that even under the condition that every permutation in the indexing
set is grassmannian, our rule is still more general, since it is able to
compute the coefficients of all terms in the product, whereas in [PS09] only
those coefficients of grassmannian permutations were considered.

Our main theorem is as follows:

Theorem 3.1. Let $\pi,\rho\in S_{n}$ where $\pi$ has no descents before
position $k$ and $\rho$ has no descents after position $k$. Define

$\pi\star\rho(i)=\begin{cases}\pi(i+k)-k&\text{ if }i\in[1-k,0]\\\
\rho(i)+n-k&\text{ if }i\in[1,k]\\\ \pi(i)-k&\text{ if }i\in[k+1,n]\\\
{\begin{subarray}{c}(i-n)\text{th smallest number in }\\\
[1-k,2n-k]\setminus\pi\star\rho([1-k,n])\end{subarray}}&\text{ if
}i\in[n+1,2n-k].\end{cases}$

Let $\sigma\in S_{2n-k}$ such that
$\ell(\pi\star\rho)-\ell(\sigma)=\ell((\pi\star\rho)\sigma^{-1})=k(n-k)$. The
Schubert structure constant $c_{\pi,\rho}^{\sigma}$ is equal to the number of
reduced word tableaux $T$ of shape $k\times(n-k)$ such that the permutation
given by the reading word of $T$ (see Section 2.2 for conventions) is
$(\pi\star\rho)\sigma^{-1}$. Furthermore, $c_{\pi,\rho}^{\sigma}=0$ for all
other $\sigma$ (even though the number of tableaux may be nonzero). We show an
example that illustrates the statement of the theorem. Let $n=6$, $k=3$,
$\pi=135264,\rho=513246$. Then $\pi\star\rho=[-2,0,2,8,4,6,-1,3,1,5,7,9]$. We
have the following Schubert product expansion:

$\mathfrak{S}_{\pi}\mathfrak{S}_{\rho}=\mathfrak{S}_{615243}+\mathfrak{S}_{534162}+\mathfrak{S}_{625134}+\mathfrak{S}_{526143}+2\mathfrak{S}_{624153}+\mathfrak{S}_{7152346}+\mathfrak{S}_{7142536}+\mathfrak{S}_{7231546}.$

For $\sigma=624153$, there are two Coxeter-Knuth classes of reduced words for
$(\pi\star\rho)\sigma^{-1}$ whose reduced word tableaux are of shape $3\times
3$. These are:

For $\sigma=7142536$, there is one Coxeter-Knuth class of reduced words for
$(\pi\star\rho)\sigma^{-1}$ whose reduced word tableau is of shape $3\times
3$:

We take a moment to elaborate on the journey that lead to the discovery. The
first idea was to generalize Schützenberger’s jeu de taquin algorithm using
bumpless pipe dreams. The key challenge here was to come up with a bumpless
pipe dream analogue of skew tableaux. To achieve this, we introduce a
simulation of jeu de taquin using semi-standard tableaux, and use the direct
bijection between bumpless pipe dreams for $k$-grassmannian permutations and
semi-standard Young tableaux of the corresponding shape to obtain a version of
jeu de taquin with bumpless pipe dreams. The second challenge was to figure
out to what extent the algorithm can be generalized beyond grassmannian
permutations. It turns out that the separated descents condition fits the
bill, and the rectification process by jeu de taquin with bumpless pipe dreams
for $k$-grassmannian permutations uses moves very much like those described in
[LLS18], where a bumpless pipe dream version of Edelman-Greene correspondence
is given. The full result is hence achieved by considering a generalization of
the Edelman-Greene correspondence using bumpless pipe dreams.

The organization of the paper is as follows. Section 2 provides background and
set conventions for the paper. Section 3 states and proves our main result,
Theorem 3.1, as well as the necessary technical lemmas. Section 4 discusses
the extension of our result to Schubert products for for multiple permutations
with separated descents. Section 5 spells out the connection of our
construction to the original jeu de taquin, and Section 6 ends with some
concluding remarks.

Acknowledgments. I am grateful to my advisor Allen Knutson for many in-depth
discussions and inspiring questions, as well as extensive comments on the
paper. I would also like to thank Thomas Lam and Alex Yong for helpful
discussions. This material is based upon work supported by the National
Science Foundation under Grant No. DMS-1439786 while I was in residence at the
Institute for Computational and Experimental Research in Mathematics in
Providence, RI, during the Combinatorial Algebraic Geometry program.

##  Preliminaries

We introduce some notation. For $m,n\in\mathbb{Z}$, $m\leq n$ we write
$[m,n]:=\\{m,m+1,\cdots,n\\}$. Let $S_{[m,n]}$ denote the set of permutations
on the alphabet $[m,n]$. As usual, $S_{n}$ denotes the set of permutations on
$\\{1,\cdots,n\\}$.

### 2.1 Bumpless pipe dreams and Schubert polynomials

Bumpless pipe dreams were introduced in [LLS18]. A bumpless pipe dream for a
permutation $\pi\in S_{[m,n]}$ is a tiling of an $(m-n+1)\times(m-n+1)$ grid
with rows and columns indexed by numbers in $[m,n]$ by the following six kinds
of tiles, such that $m-n+1$ pipes that travel from the south border and exit
from the east border are formed. The tile where two pipes “bump” is forbidden,
and hence the name “bumpless pipe dream.”

We also impose the “reducedness” condition, that no two pipes are allowed to
cross twice. The pipes are labelled from $m$ to $n$ on the south border, and
reading off the labels from top to bottom on the east border gives a
permutation in $S_{[m,n]}$. Given a permutation $\pi\in S_{[m,n]}$, we denote
the set of bumpless pipe dreams of this permutation by
$\operatorname{BPD}(\pi)$. The Rothe bumpless pipe dream
$\operatorname{rothe}(\pi)$ is the unique bumpless pipe dream of $\pi$ that
does not contain any -tiles111These are pronounced “jay” as in “j”, whereas
the -tiles are pronounced “are”.. It was shown in [LLS18, Section 5.2] any
$D\in\operatorname{BPD}(\pi)$ can be obtained from $\operatorname{rothe}(\pi)$
by performing a sequence of droop moves, defined in the same section.

Given $\pi\in S_{n}$, define the bumpless pipe dream polynomial $P_{\pi}$ by

$P_{\pi}(\mathbf{x}):=\sum_{D\in\operatorname{BPD}(\pi)}\prod_{(i,j)\in\text{blank}(D)}x_{i},$

where $\text{blank}(D)$ is the set of blank tiles in $D$. The tiles in a
bumpless pipe dreams are indexed with matrix coordinates.

Meanwhile, Schubert polynomials were defined by Lascoux and Schützenberger via
divded difference operators $\partial_{i}$, defined as

$\partial_{i}f:=\frac{f-s_{i}f}{x_{i}-x_{i+1}},$

where $f$ is a polynomial, and $s_{i}$ acts by swapping the variables $x_{i}$
with $x_{i+1}$. The Schubert polynomial $\mathfrak{S}_{\pi}$ for $\pi\in
S_{n}$ is defined as follows:

$\mathfrak{S}_{\pi}:=\begin{cases}x_{1}^{n-1}x_{2}^{n-2}\cdots x_{n-1}&\text{
if }\pi=n,(n-1),\cdots,2,1\\\ \partial_{i}\mathfrak{S}_{\pi s_{i}}&\text{ if
}\pi(i)<\pi(i+1).\end{cases}$

It was proved in [LLS18] and in [Wei20] that $P_{\pi}=\mathfrak{S}_{\pi}$. We
give another proof by directly computing how divided difference operators act
on bumpless pipe dream polynomials. The operations defined on bumpless pipe
dreams in the proof are analogous to the “mitosis” operations for pipe dreams.
See [KM05] and [Mil03].

######  Proposition 2.1.

Let $\pi\in S_{n}$. If $\pi(i)<\pi(i+1)$, then $\partial_{i}P_{\pi}=0$.
Otherwise, $\partial_{i}P_{\pi}=P_{\pi s_{i}}.$

###### Proof.

We define an equivalence relation on $\operatorname{BPD}(\pi)$, where
$D_{1}\sim D_{2}$ if $D_{1}$ and $D_{2}$ are the same outside of row $i$ and
$i+1$, and are related by a sequence of droop/undroop moves within row $i$ and
$i+1$. Let $\mathcal{D}$ be an equivalence class. We define
$P_{\mathcal{D}}:=\sum_{D\in\mathcal{D}}\prod_{(i,j)\in\text{blank}(D)}x_{i}$,
and notice that
$P_{\mathcal{D}}=p(x_{1},\cdots,x_{i-1},x_{i+2},\cdots,x_{n-1})(f(x_{i},x_{i+1})+x_{i}^{m})$,
where $p$ is a polynomial in variables not involving $x_{i}$ and $x_{i+1}$,
$f$ is symmetric in $x_{i}$ and $x_{i+1}$, and $m$ is a nonnegative integer.
(Combinatorially, $m$ counts the number of blank tiles in every
$D\in\mathcal{D}$ that are unaffected by the droop/undroop moves within row
$i$ and $i+1$.) We will show that

$\partial P_{\mathcal{D}}:=\begin{cases}0&\text{ if }m=0\\\
P_{\mathcal{D^{\prime}}}&\text{ otherwise},\end{cases}$

where $\mathcal{D}^{\prime}$ is defined in the next paragraph. If
$\pi(i)<\pi(i+1)$, the pipes $\pi(i)$ and $\pi(i+1)$ do not cross in any
element of $\operatorname{BPD}(\pi)$. This implies $m=0$ and $P_{\mathcal{D}}$
is symmetric in $x_{i}$ and $x_{i+1}$, so $\partial_{i}P_{\mathcal{D}}=0$.
Since $\mathcal{D}$ is arbitrary, $\partial_{i}P=0$. Otherwise, pick
$D\in\mathcal{D}$, let $y_{i}$ be the column index of the last -tile on row
$i$ in $D$, and $y_{i+1}$ be the column index of the last -tile on row $i+1$
in $D$. By assumption, $y_{i+1}<y_{i}$. Notice that $m$ is the number of blank
tiles on row $i$ with column index $y$ with $y_{i+1}\leq y<y_{i}$ that are
present in all bumpless pipe dreams in $\mathcal{D}$. Again, if $m=0$ then
$\partial_{i}P_{\mathcal{D}}=0$.

If $m>0$, consider the following map that sends $\mathcal{D}$ to an
equivalence class $\mathcal{D}^{\prime}$ in $\operatorname{BPD}(\pi s_{i})$.
Pick any $D\in\mathcal{D}$, and perform the row move on $D$ that replaces the
cross of pipes $\pi(i)$ and $\pi(i+1)$ with a -tile, and undroop the NW-elbow
into one of these $m$ boxes in row $i$, as illustrated below.

Figure 1: row move

Call the resulting diagram $D^{\prime}$, and let $\mathcal{D}^{\prime}$ be the
class of $D^{\prime}$. Notice that
$\partial_{i}P_{\mathcal{D}}=p(x_{1},\cdots,x_{i-1},x_{i+2},\cdots,x_{n-1})(x_{i}^{m-1}+x_{i}^{m-2}x_{i+1}+\cdots
x_{i+1}^{m-1})=P_{\mathcal{D}^{\prime}}$. By performing the inverse operation
of the row move we see that every equivalence class in $\operatorname{BPD}(\pi
s_{i})$ can be obtained this way, and each class has a unique preimage. We can
then conclude that $\partial_{i}P_{\pi}=P_{\pi s_{i}}$. ∎

######  Corollary 2.1 ([LLS18]).

For every $\pi\in S_{n}$, $P_{\pi}=\mathfrak{S}_{\pi}$.

###### Proof.

When $\pi=n,n-1,\cdots,1$, $\operatorname{BPD}(\pi)$ contains a singleton
rothe bumpless pipe dream, and $P_{\pi}=x_{1}^{n-1}x_{2}^{n-2}\cdots x_{n-1}$.
The inductive case is given by Proposition 2.1. ∎

### 2.2 Edelman-Greene correspondence

We recall some results about the Edelman-Greene correspondence, and set some
conventions for this paper.

######  Definition 2.1 (Coxeter-Knuth insertion).

Suppose $P$ is a standard Young tableau. Let $x$ be a number to be inserted
into $P$. Initialize the row index $i=1$, and follow the steps below.

  1. 1.

If $x$ is larger than or equal to all numbers in row $i$ or if row $i$ is
empty, append $x$ at the end of the row, and stop.

  2. 2.

Otherwise, let $z$ be the leftmost number in row $i$ larger than $x$.

    1. (a)

If $z=x+1$ and the value of $x$ is already present in row $i$, leave row $i$
unchanged, increment $x$ by 1, increment $i$ by 1, and go to Step 1. Otherwise
go to Step 2(b).

    2. (b)

Put $x$ in the position of $z$ in $P$ and let $z$ be the new value of $x$.
Increment $i$ by 1, then go to Step 1.

######  Definition 2.2 (Edelman-Greene map).

Suppose $\pi$ is a permutation and $\mathbf{i}=i_{1}i_{2}\cdots i_{\ell}$ is a
reduced word of $\pi$. Initialize $P^{0}$ and $Q^{0}$ to both be empty
standard Young tableax. For each $j=1,2,\cdots,\ell$, construct $P^{j}$ by
inserting the number $i_{\ell+1-j}$ into $P^{j-1}$ using the Coxeter-Knuth
insertion, and $Q_{j}$ by adding a new box to $Q^{j-1}$ so that $P^{j}$ and
$Q^{j}$ have the same shape, and fill this box with $i$. Let the _insertion
tableau_ $P(\mathbf{i})$ be $P^{\ell}$ and the _recording tableau_
$Q(\mathbf{i})$ be $Q^{\ell}$.

######  Remark 2.1.

Note that we insert a reduced word from right to left into a tableau, which is
the opposite of the conventional order. This choice is made for the
convenience of stating our main theorem, and is consistent with the convention
used in [LLS18]. For this reason, we will define our reading order for the
insertion tableau to be row-by-row from top to bottom, and right-to-left
within each row.

######  Definition 2.3.

The Coxeter-Knuth equivalence on the set of reduced words of $\pi$ is
generated by the following elementary relations:

  1. (a)

$\cdots jik\cdots\sim\cdots jki\cdots$ if $i<j<k$,

  2. (b)

$\cdots ikj\cdots\sim\cdots kij\cdots$ if $i<j<k$,

  3. (c)

$\cdots i(i+1)i\cdots\sim(i+1)i(i+1)$.

Recall that the descent sets of a standard tableau of shape $\lambda$ is
defined as $\operatorname{Des}(S):=\\{j:j+1\text{ appears in a lower row than
}j\\}$, and the descent set of a reduced word $\mathbf{i}=i_{1}\cdots i_{l}$
is $\operatorname{Des}(\mathbf{i})=\\{j:i_{j}>i_{j+1}\\}$. We write the
reverse of a reduced word $\mathbf{i}$ as $\mathbf{i}^{-1}$.

######  Theorem 2.1 (Edelman-Greene correspondence).

The map

$\operatorname{EG}:\mathbf{i}\mapsto(P(\mathbf{i}),Q(\mathbf{i}))$

is an injective map from the set of reduced words for $\pi$,
$\operatorname{red}(\pi)$, to the set of pairs of tableaux $(P,Q)$ where $P$
is row and column strict and $Q$ is standard. This map has the following
properties:

  1. (a)

For each $P$, every standard tableau $Q$ with the same shape as $P$ appears in
the image.

  2. (b)

Two reduced words of $\pi$ are Coxeter-Knuth equivalent if and only if they
have the same insertion tableau.

  3. (c)

If $\operatorname{EG}(\mathbf{i})=(P,Q)$ and $Q^{\prime}$ is another standard
tableau, then $\operatorname{EG}^{-1}(P,Q^{\prime})$ is Coxeter-Knuth
equivalent to $\mathbf{i}$.

  4. (d)

For each $\mathbf{i}\in\operatorname{red}(\pi)$,
$\operatorname{Des}(\mathbf{i}^{-1})=\operatorname{Des}(Q(\mathbf{i}))$.

### 2.3 Jeu de taquin

We recall Schützenberger’s jeu de taquin algorithm on semi-standard skew
tableaux. Our reference is [Ful97, Chapter 1].

Let $T$ be a semi-standard skew tableau of shape $\nu/\mu$. The jeu de taquin
algorithm on $T$ rectifies $T$ into a semi-standard tableau by iterating the
following steps.

  1. (1)

Pick a SE-most empty box in the NW empty region to be “active”.

  2. (2)

Repeat this step until the current active empty box is on the SE border: pick
the smaller number from the box to the right and the box directly below the
active empty box, and slide that box into the active empty box. If there is a
tie, pick the box below. The newly created empty box after sliding becomes the
new active empty box.

It is well-known that the final output is independent of the choice made in in
Step (1). Given partitions $\lambda,\mu,\nu$, the Littlewood-Richardson
coefficient $c_{\lambda,\mu}^{\nu}$ is the number of standard Young tableaux
of shape $\nu/\mu$ that are jeu de taquin equivalent to some fixed standard
Young tableau of shape $\lambda$.

##  Schubert products for permutations with separated descents

### 3.1 The star operation for permutations with separated descents

We say that a permutation $\pi\in S_{n}$ has a descent at position $i$ if
$\pi(i)>\pi(i+1)$. We denote the set of $\pi$’s descents
$\operatorname{Des}(\pi):=\\{i\in\\{1,2,\cdots,n-1\\}:\pi(i)>\pi(i+1)\\}$.

Suppose $\pi$ and $\rho$ have separated descents at position $k$; namely for
all $i\in\operatorname{Des}(\pi)$, $i\geq k$ and for all
$i\in\operatorname{Des}(\rho)$, $i\leq k$ . Let $D\in\operatorname{BPD}(\pi)$
and $E\in\operatorname{BPD}(\rho)$. We define a procedure to produce a
bumpless pipe dream $D\star E$ in the $2n\times 2n$ grid with indices
$1-k,\cdots,2n-k$ by the following operations.

  1. (1)

Place $D$ left of $E$ to cover an $n\times 2n$ grid. Increment the indices of
$E$’s pipes by $n-k$, and decrement the indices of $D$’s pipes by $k$, so that
the $2n$ pipes are labeled with $[1-k,2n-k]$.

  2. (2)

For all $i\in[k+1,n]$, delete $E$’s pipe with index $\rho(i)$, and extend
$D$’s pipe with index $\pi(i)$ all the way to the east.

  3. (3)

For each $i\in\\{k,k-1,\cdots,1\\}$ (in decreasing order), reroute $\pi(i)$ so
that it exits from row $i-k$, and does so (a) without affecting $E$’s grid or
existing blank tiles in $D$, and (b) using tiles as southwest as possible.

  4. (4)

Fill the remaining $n-k$ rows on the bottom in increasing order by either
extending an existing pipe vertically if possible, or otherwise placing an
-tile in the first emtpy column and extend all the way to the east and the
south.

(a) $D\in\operatorname{BPD}(\pi)$, $E\in\operatorname{BPD}(\rho)$,
$\pi=13542$, $k=21435$, $n=5$, $k=3$

(b) $D\star E\in\operatorname{BPD}^{\square}(\pi\star\rho)$

Figure 2: Combining bumpless pipe dreams of $\pi$ and $\rho$ with the $\star$
operation

Keeping the same assumption of separated descents on $\pi$ and $\rho$, we
define the operation $\star$ on permutations $\pi$ and $\rho$ as follows:

$\pi\star\rho(i)=\begin{cases}\pi(i+k)-k&\text{ if }i\in[1-k,0]\\\
\rho(i)+n-k&\text{ if }i\in[1,k]\\\ \pi(i)-k&\text{ if }i\in[k+1,n]\\\
\begin{subarray}{c}(i-n)\text{th smallest number in }\\\
[1-k,2n-k]\setminus\pi\star\rho([1-k,n])\end{subarray}&\text{ if
}i\in[n+1,2n-k].\end{cases}$

Note that $\pi\star\rho\in S_{[1-k,2n-k]}$.

Let $\operatorname{BPD}^{\square}(\pi\star\rho)$ denote the set of bumpless
pipe dreams of $\pi\star\rho$ such that the first $k$ rows are of the form
that the initial $k$ columns are blank, followed by $k$ non-intersecting hook-
shaped pipes that completely occupy the $k\times(n+k)$ remaining columns, as
shown below:

By construction, it is easy to see that $D\star
E\in\operatorname{BPD}^{\square}(\pi\star\rho)$. See Figure 2(b).

######  Lemma 3.1.

There is a direct bijection between
$\operatorname{BPD}^{\square}(\pi\star\rho)$ and
$\operatorname{BPD}(\pi)\times\operatorname{BPD}(\rho)$. In particular, if
$F\in\operatorname{BPD}^{\square}(\pi\star\rho)$ corresponds to
$(D,E)\in\operatorname{BPD}(\pi)\times\operatorname{BPD}(\rho)$ under the
bijection, then for each $1\leq i\leq n$ the number of blank tiles in row $i$
of $F$ is equal to the total number of blank tiles in row $i$ of $D$ and $E$.

###### Proof.

Suppose $F\in\operatorname{BPD}^{\square}(\pi\star\rho)$. By the definition of
$\pi\star\rho$, the rows $[n+1,2n-k]$ of $F$ do not contain any blank tiles
and are completely determined by the rows above. First consider the
$(n-k)\times n$ region of $F$ with rows $[k+1,n]$ and columns $[1-k,n-k]$. The
pipes $\pi\star\rho(i)=\pi(i)-k\leq n-k$ for $i\in[k+1,n]$. This means that
these $n-k$ pipes travel from the south edge of the region and exit from the
east edge of this region. The pipes $\pi(i+k)-k\leq n-k$ for $i\in[1-k,0]$
travel from the south edge and exit from the north edge of this region. Their
configuration agrees with the last $(n-k)$ rows of a bumpless pipe dream of
$\pi$.

Now consider the $k\times n$ region of $F$ with rows $[1,k]$ and columns
$[1-k,n-k]$. By the definition of $\pi\star\rho$, since $\rho(i)+n-k>n$, the
only pipes in this region have indices $\pi(i+k)-k\leq n-k$ for $i\in[1-k,0]$,
and all pipes with indices $\pi(i+k)-k$ for $i\in[1-k,0]$ enter this region
from the south edge and exit from columns $[n-k+1,n]$ of the north edge
without ever crossing each other. If we reroute these pipes by modifying the
tiles in the triangular region (weakly) above the $k$th diagonal counting from
the NE corner of this region, so that the pipes exit from the east edge
instead, we can make this region agree with the first $k$ rows of a bumpless
pipe dream of $\pi$, which can be combined with the bottom region to make up a
bumpless pipe dream of $\pi$.

Consider the $k\times n$ region of $F$ with rows $[1,k]$ and columns
$[n-k+1,2n-k]$. By the definition of $\pi\star\rho$ and the discussion above,
the only pipes that show up in this region are $\rho(i)+n-k>n-k$, and these
pipes enter from the south edge of this region and exit from the east.
Therefore, this region agrees with the first $k$ rows of a bumpless pipe dream
of $\rho$. Furthermore, there are no blank tiles in the $(n-k)\times n$ region
with rows $[k+1,n]$ and columns $[n-k+1,2n-k]$. Since $\rho$ has no descents
after $k$, its bumpless pipe dream is completely determined by the first $k$
rows. This gives us a bumpless pipe dream of $\rho$.

It is easy to see that the inverse of this process is the procedure of
constructing $D\star E$ as described above. We have established the desired
bijection. ∎

### 3.2 Rectification and Insertion

Let $\sigma\in S_{[a,b]}$, and $F\in\operatorname{BPD}(\sigma)$. Suppose
$\lambda$ is a partition contained inside the connected region of blank tiles
at the NW corner of $F$ (with its NW corner anchored at the NW corner of $F$).
We mark the tiles in $\lambda$ with a label “$\mathsf{x}$”. We will now
describe a rectification process on $F$ that iteratively removes these marked
tiles and produces a reduced word of length $|\lambda|$. During the entire
rectification process, we also will make sure to maintain the invariance of
the number of non-marked blank tiles in each row.

To start, let $\mathbf{i}$ be the empty reduced word. In each iteration of the
rectification, we choose a SE-most marked tile, and perform the following
operations. The process completes when there are no marked tiles in the grid.

  1. (1)

If the marked tile is not the rightmost tile of a contiguous block of blank
tiles on a row, slide the mark to the rightmost tile.

  2. (2)

When one of the following forward-direction column moves is possible, perform
the move. Repeat Steps (1) and (2) when possible; otherwise go to Step (3).

Figure 3: Column moves (rectifying rightward, inserting leftward)

Intuitively, each column move amounts to, if the current marked tile is at
coordinate $(i,j)$, and there is a pipe that occupies a -tile at
$(i^{\prime},j+1)$ for a minimal $i^{\prime}>i$ such that it is possible to
undroop this pipe so that it occupies $(i,j)$, do so and adjust other pipes
between these two rows so that their “kinks shift left”, as shown in Figure 3.

  3. (3)

If the current marked tile is at $(i,j)$, replace the cross of pipe $j$ and
$j+1$ at $(i^{\prime},j+1)$ with a -tile, and resolve this bump by undrooping
the NW-elbow into $(i,j)$, and adjust other pipes if necessary as shown in
Figure 4. This move decrements the number of marked tile by 1 and is the end
of this iteration of rectification. Append $j$ to the end of the reduced word
$\mathbf{i}$.

Figure 4: Delete or insert a marked blank tile (rectifying rightward,
inserting leftward)

######  Remark 3.1.

These column moves are slight generalizations of (the backward direction of)
the column moves defined in [LLS18, Section 5.7]. The only difference is that
here blank tiles strictly between rows $i$ and $i^{\prime}$ are allowed,
whereas in [LLS18] they are forbidden. In Step (1) we have the extra sliding
move that sends the marked tile across a contiguous block of blank tiles from
one end to the other, which was not needed in their setting. For this reason,
the next few lemmas are direct generalizations of Lemmas 5.22, 5.24, and 5.25
in [LLS18], with only slight differences in technical details.

With the inverses of these column moves we may define an insertion algorithm
on a bumpless pipe dream $F\in\operatorname{BPD}(\sigma)$ for some $\sigma\in
S_{[a,b]}$. Let $w\in S_{[a,b]}$, and $\mathbf{i}=i_{1}i_{2}\cdots i_{\ell}$ a
reduced word for $w$. Suppose also that $\ell(w\sigma)=\ell(w)+\ell(\sigma).$
We describe a procedure that inserts $\mathbf{i}$ into $F$ to get a bumpless
pipe dream of $w\sigma$, where each simple reflection adds a marked blank
tile. To begin, by the assumption that $w$ and $\sigma$ are length-additive,
the pipes $i:=i_{l}$ and $i+1$ do not cross in $F$. We insert a marked tile at
column $i$ using the inverse operation of Step (2) above. Then we repeatedly
apply the inverse operation of Step (1) above until we exhaust the moves.
Following the notations introduced in [LLS18], we denote the resulting
bumpless pipe dream after inserting a blank tile in column $i$ into $F$ using
this insertion algorithm with $F\leftarrow i$. Define the insertion footprints
for $F\leftarrow i$ as the set of positions the marked tile appears at _that
later become -tiles_ during the insertion process, plus its final position. We
observe that an insertion footprints set consists of tiles that run SW to NE,
with no two tiles on the same row or column. Let $\lambda(F\leftarrow i)$
denote the partition formed by the marked tiles in the diagram. Define
$F\leftarrow\mathbf{i}$ as $(((F\leftarrow i_{\ell})\leftarrow
i_{\ell-1})\leftarrow\cdots)\leftarrow i_{1}$. _In order for the marked blank
tiles to form a partition at the NW corner, we may need to consider $\sigma$
as a permutation in $S_{[a^{\prime},b]}$ for some $a^{\prime}<a$ small enough
(namely, enlarge $F$ by adding enough pipes that give the identity permutation
outside the NW corner of $F$). This is always possible given $w$. We refer to
this process as back-stabilizing $F$.)_ The saturated chain of partitions
$\lambda(F\leftarrow i_{l})\subset\lambda((F\leftarrow i_{l})\leftarrow
i_{l-1})\subset\cdots\subset\lambda(F\leftarrow\mathbf{i})$ gives rise to a
standard Young tableau of shape $\lambda(F\leftarrow\mathbf{i})$, which we
denote by $Q(F\leftarrow\mathbf{i})$.

Figure 5: Insertion of $i$. Gray marks indicate all locations the new marked
tile has been, and tiles with red shading are the insertion footprints.

######  Lemma 3.2.

Suppose $i<j$.

  1. (1)

The insertion footprints for $(F\leftarrow i)\leftarrow j$ are strictly to the
N/E/NE of the insertion footprints for $F\leftarrow i$. Or in other words, no
insertion footprint of $F\leftarrow i$ is N/E/NE of any insertion footprint of
$(F\leftarrow i)\leftarrow j$.

  2. (2)

The insertion footprints for $(F\leftarrow j)\leftarrow i$ are strictly to the
S/W/SW of the insertion footprints for $F\leftarrow j$.

###### Proof.

We show (1); (2) is similar.

Suppose the first tile in the insertion footprints of $F\leftarrow i$ is
$(x_{1},y_{1})$, and consider the bumpless pipe dream $F\leftarrow i$. We know
that $y_{1}\leq i$. We consider the set of tiles that either lies in the
“upper hook” inside the width 2 rectangle that bounds the column move that
_has happened for inserting $i$_, or in a contiguous block of blank tiles on a
row that bounds the “sliding” move of the marked tile. Note that the insertion
footprints are the tiles at the SW corners of the green “zigzag” strip
illustrated in Figure 6.

Figure 6: Insertion footprints for $F\leftarrow i$ (green) and $(F\leftarrow
i)\leftarrow j$ (red) for $i<j$ in the bumpless pipe dream $F\leftarrow i$

Notice that the southernmost possible coordinate of the lowest -tile in column
$i+1$ is $(x_{1},i+1)$. Therefore, the first tile in the insertion path of
$(F\leftarrow i)\leftarrow j$ with column index no greater than $i+1$ is at or
above row $x_{1}$. If it is at row $x_{1}$, its coordinate must be
$(x_{1}^{\prime},y_{1}^{\prime})=(x_{1},y_{1}+1)$. In this case, the insertion
footprints for $(F\leftarrow i)\leftarrow j$ are exactly the set of tiles
immediately to the right of each tile in the insertion footprints of
$(F\leftarrow i)$. Otherwise, it is on $(x_{1}^{\prime},y_{1}^{\prime})$ with
$x_{1}^{\prime}<x_{1}$. We consider the set of tiles that lie in the “lower
hook” inside the width 2 rectangles that bound column moves that are _about to
happen for inserting $j$_, union the contiguous blocks of blank tiles on a row
that bound the sliding moves of the marked tile. The insertion footprints of
$(F\leftarrow i)\leftarrow j$ are the tiles immediately to the right of the SW
corners of this zigzag strip. Now imagine travelling from
$(x_{1}^{\prime},y_{1}^{\prime})$ along this region. Since going west
horizontally allows only the use of blank tiles, we may never cross past the
green strip. In the case when two red and green vertical segments coincide, we
end up in the same situation as the first case. Thus our claim about the
insertion footprints follows. ∎

The following is immediate by Lemma 3.2.

######  Corollary 3.1.

$\operatorname{Des}(Q(F\leftarrow\mathbf{i}))=\operatorname{Des}(\mathbf{i}^{-1})$.

######  Lemma 3.3.

Suppose $i<j<k$. When all the insertions are defined,

  1. (1)

$((F\leftarrow j)\leftarrow i)\leftarrow k=((F\leftarrow j)\leftarrow
k)\leftarrow i$

  2. (2)

$((F\leftarrow i)\leftarrow k)\leftarrow j=((F\leftarrow k)\leftarrow
i)\leftarrow j$.

###### Proof.

The proof is similar to the proof of [LLS18, Lemma 5.24]. In particular, we
supply the details omitted in part (2) of their proof.

To show (1), we notice that since the insertion footprints of $(F\leftarrow
j)\leftarrow i$ lie SW of the insertion footprints of $(F\leftarrow j)$ by
Lemma 3.2, the area NE of the insertion footprints is not affected by the
insertion of $i$. Similarly, the area SW of the insertion footprints
$(F\leftarrow j)$ is not affected by the insertion $(F\leftarrow j)\leftarrow
k$. Therefore, after the insertion $(F\leftarrow j)$, the insertions of $i$
and $k$ commute.

To show (2), first we consider the case when there is no tile $(x,y)$ in the
insertion footprints of $F\leftarrow i$ such that $(x,y+1)$ is in the
insertion footprints of $F(\leftarrow i)\leftarrow k$. In this case, the
insertion footprints of $(F\leftarrow i)$ still are -tiles in the bumpless
pipe dream $(F\leftarrow i)\leftarrow k$. This means that we can undo the
insertion of $i$ in $(F\leftarrow i)\leftarrow k$ and get $(F\leftarrow k)$.
In other words, in this case $(F\leftarrow i)\leftarrow k=(F\leftarrow
k)\leftarrow i$.

Otherwise, let $(x,y)$ be the first tile in the insertion footprints of
$F\leftarrow i$ such that $(x,y+1)$ is in the insertion footprints of
$(F\leftarrow i)\leftarrow k$. This means that the insertion of $i$ and $k$
_before either path reaches $(x,y)$_ commute, and therefore the footprints of
$((F\leftarrow i)\leftarrow k)\leftarrow j$ are the same as $((F\leftarrow
k)\leftarrow i)\leftarrow j$ in this initial segment and is NE of the path for
$i$ and SW of the path for $j$.

Now consider the situation where we insert $i$ until the marked tile reaches
$(x_{i},y+1)$ for some $x_{i}>x$, and then insert $k$ until the marked tile
reaches the furthest tile $(x_{k},y_{k})$ where $x<x_{k}<x_{i}$ and
$y_{k}>y+1$. (Note that $(x_{k},y_{k})$ might be the rightmost tile of some
contiguous block of blank tiles, in which case it will not become a footprint.
It’s easy to check given our conditions these tiles must exist.) Then, we
insert $j$ until it reaches the furthest tile $(x_{j},y_{j})$ with $y_{j}>y+1$
and $x_{j}>x_{k}$. One can check that it must be the case that $x_{j}\leq
x_{i}$ and $y_{j}\leq y_{k}$.

We now perform three droops moves that advance the marked tiles for $i,j,k$ in
that order. Notice that all three moves belong to the same active pipe, and
the results are the same as if the moves were done in the order $k,i,j$, as
illustrated below.

Figure 7: Advancing marks for $i$, $k$, $j$ vs. advancing marks for $k$, $i$,
$j$. Blue represents $i$, red represents $k$, and green represents $j$. The
-tile in the top diagram has coordinate $(x,y)$.

From the diagram on the left, we continue the insertion process by completing
the insertion of $i$, and then $k$, and finally $j$. From the diagram on the
right, we do so in the order $k,i,j$. By similar reasoning as in part (1), we
see that these result in the same diagram when finished. ∎

######  Lemma 3.4.

When all the insertions are defined $((F\leftarrow i)\leftarrow i+1)\leftarrow
i=((F\leftarrow i+1)\leftarrow i)\leftarrow i+1$.

###### Proof.

The same reasoning in the proof of [LLS18, Lemma 5.25] applies here. ∎

######  Lemma 3.5.

Let $P$ be a bumpless pipe dream with a region of marked blank tiles of shape
$\lambda$ at its NW corner, and let $Q$ be a standard tableau of shape
$\lambda$. Let $\mathbf{i}$ be the reduced word produced by running the
rectification algorithm (the insertion algorithm in reverse) according to the
order specified by $Q$. The Coxeter-Knuth class of $\mathbf{i}$ does not
depend on the order specified by $Q$.

###### Proof.

This can be proved by running the arguments in the reverse direction of Lemmas
3.2, 3.3, and 3.4. We omit the details. ∎

The following proposition generalizes [LLS18, Theorem 5.18].

######  Proposition 3.1.

Let $\sigma\in S_{[a,b]}$, and let $w\in S_{[a,b]}$ be a permutation such that
$\ell(w\sigma)=\ell(w)+\ell(\sigma)$. Let $\mathbf{i}$ be a reduced word of
$w$ and suppose its reduced word tableau is of shape $\lambda$. Let $F$ be a
bumpless pipe dream for $\sigma$. After back-stabilizing $F$ by an appropriate
amount if necessary, the insertion of $\mathbf{i}$ produces a bumpless pipe
dream $P=(F\leftarrow{\mathbf{i}})$. Furthermore, the set
$C_{P}=\\{\mathbf{j}\in\operatorname{red}(w):F\leftarrow\mathbf{j}=P\\}$ is a
single Coxeter-Knuth equivalence class. The shape of
$Q(F\leftarrow\mathbf{i})$ is $\lambda$.

###### Proof.

That $C_{P}$ is a single Coxeter-Knuth equivalence class follows from Lemmas
3.3, 3.4, and 3.5. The last claim can be proved in the same way as the last
paragraph of the proof of [LLS18, Theorem 5.18]. ∎

######  Theorem 3.1.

Suppose $\pi,\rho\in S_{n}$ such that $\pi$ has no descents before position
$k$ and $\rho$ has no descents after position $k$. Let $\sigma\in S_{2n-k}$
such that
$\ell(\pi\star\rho)-\ell(\sigma)=\ell((\pi\star\rho)\sigma^{-1})=k(n-k)$. The
Schubert structure constant $c_{\pi,\rho}^{\sigma}$ is equal to the number of
reduced word tableaux $T$ of shape $k\times(n-k)$ such that the permutation
given by the reading word of $T$ is $(\pi\star\rho)\sigma^{-1}$. Furthermore,
$c_{\pi,\rho}^{\sigma}=0$ for all other $\sigma$ (even though the number of
tableaux may be nonzero).

###### Proof.

Let $\sigma\in S_{2n-k}$ such that
$\ell(\pi\star\rho)-\ell(\sigma)=\ell((\pi\star\rho)\sigma^{-1})=k(n-k)$, and
suppose $\mathbf{i}$ is a reduced word of $(\pi\star\rho)\sigma^{-1}$ whose
Coxeter-Knuth equivalence class $[\mathbf{i}]$ corresponds to a reduced word
tableau of the $k\times(n-k)$ rectangular shape. Consider $\sigma$ as an
element of $S_{[1-k,2n-k]}$, so that the NW corner of any bumpless pipe dream
of $\sigma$ is at $(1-k,1-k)$. Notice that for any
$F\in\operatorname{BPD}(\sigma)$,
$(F\leftarrow\mathbf{i})\in\operatorname{BPD}^{\square}(\pi\star\rho)$. If
$\mathbf{j}$ is another reduced word of $(\pi\star\rho)\sigma^{-1}$ where
$[\mathbf{j}]$ corresponds to a different reduced word tableau of shape
$k\times(n-k)$, then $(F\leftarrow\mathbf{i})\neq(F\leftarrow\mathbf{j})$ by
Proposition 3.1. Therefore, each pair $(\sigma,[\mathbf{i}])$ identifies
$|\operatorname{BPD}(\sigma)|$ many elements in
$\operatorname{BPD}^{\square}(\pi\star\rho)$. The insertion algorithm
preserves the number of unmarked blank tiles on each row, so
$\operatorname{BPD}(\sigma)$ and
$\\{F\leftarrow\mathbf{i}:F\in\operatorname{BPD}(\sigma)\\}$ represent the
same multiset of monomials (recall that marked tiles do not contribute to
monomials).

On the other hand, for any $D\in\operatorname{BPD}(\pi)$ and
$E\in\operatorname{BPD}(\rho)$, rectifying $D\star E$ produces some
$F\in\operatorname{BPD}(\sigma)$ for some $\sigma\in S_{2n-k}$ and a reduced
word $\mathbf{i}$ such that the shape of the reduced word tableau for
$[\mathbf{i}]$ is $k\times(n-k)$. So $(\sigma,[\mathbf{i}])$ is such a pair as
described in the previous paragraph, and $D\star E=F\leftarrow\mathbf{i}$.

The bijection in Lemma 3.1 then completes the proof. ∎

##  Multiple permutations with separated descents

Equipped with the techniques developed in Section 3, we can easily generalize
the result to Schubert products for multiple permutations with separated
descents. To be precise, suppose $\pi_{0},\pi_{1},\cdots\pi_{m}\in S_{n}$ and
$1\leq k_{1}<k_{2}<\cdots<k_{m}\leq n-1$, where
$\operatorname{Des}(\pi_{0})\subseteq[1,k_{1}]$,
$\operatorname{Des}(\pi_{1})\subseteq[k_{1},k_{2}]$, $\cdots$
$\operatorname{Des}(\pi_{i})\subseteq[k_{i},k_{i+1}]$ $\cdots$,
$\operatorname{Des}(\pi_{m})\subseteq[k_{m},n-1]$. The star operation can be
generalized to the $(m+1)$-ary version, as follows.

$\star(\pi_{m},\cdots,\pi_{1},\pi_{0})(i)=\begin{cases}\pi_{m}(i+\sum_{\alpha=1}^{m}k_{\alpha})-(\sum_{\alpha=1}^{m}k_{\alpha})&\text{
if }i\in[1-\sum_{\alpha=1}^{m}k_{\alpha},-\sum_{\alpha=1}^{m-1}k_{\alpha}]\\\
\pi_{m-1}(i+\sum_{\alpha=1}^{m-1}k_{\alpha})-(\sum_{\alpha=1}^{m-1}k_{\alpha})&\text{
if
}i\in[1-\sum_{\alpha=1}^{m-1}k_{\alpha},-\sum_{\alpha=1}^{m-2}k_{\alpha}]\\\
\vdots&\\\ \pi_{1}(i+k_{1})-k_{1}&\text{ if }i\in[1-k_{1},0]\\\
\pi_{0}(i)+mn-\sum_{\alpha=1}^{m}k_{\alpha}&\text{ if }i\in[1,k_{1}]\\\
\pi_{1}(i)+(m-1)n-\sum_{\alpha=1}^{m}k_{\alpha}&\text{ if
}i\in[k_{1}+1,k_{1}+k_{2}]\\\ \vdots&\\\
\pi_{m}(i)-\sum_{\alpha=1}^{m}k_{\alpha}&\text{ if
}i\in[(\sum_{\alpha=1}^{m-1}k_{\alpha})+1,n]\\\ \phi(i)&\text{ if
}i\in[n+1,2n-k].\end{cases}$

where $\phi(i)$ is the $(i-n)$th smallest number in
$[1-\sum_{\alpha=1}^{m}k_{\alpha},mn-\sum_{\alpha=1}^{m}k_{\alpha}]\setminus\pi\star\rho([1-\sum_{\alpha=1}^{m}k_{\alpha},n])$.

Define also $\operatorname{BPD}^{\square}(\star(\pi_{m},\cdots\pi_{0}))$ as
the set of $D\in\operatorname{BPD}(\star(\pi_{m},\cdots\pi_{0}))$ such that
rows $[1-\sum_{\alpha=1}^{m}k_{\alpha},0]$ are of the following form. We
denote the shape of the partition at the NW corner as
$\lambda(k_{1},\cdots,k_{m},n)$.

Figure 8: First $\sum_{\alpha=1}^{m}k_{\alpha}$ rows of
$D\in\operatorname{BPD}^{\square}(\star(\pi_{m},\cdots\pi_{0}))$

We can easily generalize the procedure described in Section 3.1 and define the
$\star$-operation on
$D_{m}\in\operatorname{BPD}(\pi_{m}),\cdots,D_{0}\in\operatorname{BPD}(\pi_{0})$.
The resulting bumpless pipe dream is an element of
$\operatorname{BPD}^{\square}(\star(\pi_{m},\cdots\pi_{0}))$. Furthermore,
$\operatorname{BPD}^{\square}(\star(\pi_{m},\cdots\pi_{0}))$ is in direct
bijection with
$\operatorname{BPD}(\pi_{m})\times\cdots\times\operatorname{BPD}(\pi_{0})$.

Our main theorem generalizes to Schubert products for multiple permutations
with separated descents.

######  Theorem 4.1.

Suppose $\pi_{0},\pi_{1},\cdots\pi_{m}\in S_{n}$ and $1\leq
k_{1}<k_{2}<\cdots<k_{m}\leq n-1$, where
$\operatorname{Des}(\pi_{0})\subseteq[1,k_{1}]$,
$\operatorname{Des}(\pi_{1})\subseteq[k_{1},k_{2}]$,
$\cdots$,$\operatorname{Des}(\pi_{i})\subseteq[k_{i},k_{i+1}]$,$\cdots$,
$\operatorname{Des}(\pi_{m})\subseteq[k_{m},n-1]$. Let $\sigma\in
S_{mn-\sum_{\alpha=1}^{m}k_{\alpha}}$. such that
$\ell(\star(\pi_{m},\cdots,\pi_{0}))-\ell(\sigma)=\ell((\pi\star\rho)\sigma^{-1})=|\lambda(k_{1},\cdots,k_{m},n)|$.
The Schubert structure constant $c_{\pi_{m},\cdots,\pi_{0}}^{\sigma}$ is equal
to the number of reduced word tableaux $T$ of shape
$\lambda(k_{1},\cdots,k_{m},n)$ such that the permutation given by the reading
word of $T$ is $(\pi\star\rho)\sigma^{-1}$. Furthermore,
$c_{\pi_{m},\cdots,\pi_{0}}^{\sigma}=0$ for all other $\sigma$.

######  Remark 4.1.

Given $\pi_{0},\pi_{1},\pi_{2}$ that satisfy the separated descent conditions
as stated in the theorem, it is not difficult to check that for any
$D_{0}\in\operatorname{BPD}(\pi_{0})$, $D_{1}\in\operatorname{BPD}(\pi_{1})$,
$D_{2}\in\operatorname{BPD}(\pi_{2})$,
$\operatorname{rect}(\star(D_{0},D_{1},D_{2}))=\operatorname{rect}(D_{0}\star(\operatorname{rect}(D_{1}\star
D_{2})))=\operatorname{rect}(\operatorname{rect}(D_{0}\star D_{1})\star
D_{2})$.

##  Connection to jeu de taquin

The construction of the star operation and the rectification process were
inspired by the celebrated jeu de taquin algorithm on skew tableaux. We
discuss the connection in this section.

Let $\lambda\in S_{n}$ be a $k$-Grassmannian permutation. Namely, $\lambda$
has a single descent at position $k$. For any
$D\in\operatorname{BPD}(\lambda)$, associate a semi-standard Young tableau
$T_{D}$ to $D$ as follows. Label each blank tile in $D$ with its row index,
and perform all possible droop moves in $D$. Each droop moves a blank tile
towards the NW direction together with its label. When finished, the semi-
standard Young tableau at the NW corner is $T_{D}$. Denote the shape of
$T_{D}$ as $\lambda$ (by abuse of notation). It is known from [LLS18] that
this map $D\mapsto T_{D}$ gives a bijection between
$\operatorname{BPD}(\lambda)$ and $\operatorname{SSYT}_{k}(\lambda)$, where
$\operatorname{SSYT}_{k}(\lambda)$ denotes the set of semi-standard Young
tableaux of shape $\lambda$ with entries no greater than $k$. The following
picture shows an example of the map.

Figure 9: Correspondence between $\operatorname{BPD}(\lambda)$ and
$\operatorname{SSYT}_{k}(\lambda)$

Let $\nu=(\nu_{1},\cdots,\nu_{m})$ and $\mu=(\mu_{1},\cdots,\mu_{l})$ be
partitions such that $l<m$ and $\mu_{i}\leq\nu_{i}$ for each $i$. Suppose
$k\geq m$. Let $T\in\operatorname{SSYT}_{k}(\nu/\mu)$. We complete $T$ into a
semi-standard tableau of shape $\nu$ by filling in for each row
$i=l,l-1,\cdots,1$, the number $i-l$ in each box on row $i$ that belongs to
$\mu$. We also mark these entries with a different color. Call the resulting
marked semi-standard tableau $T^{\prime}$. We define a rectification algorithm
on $T^{\prime}$ by iterating the following procedure until there are no more
marked entries.

  1. 1.

Pick a SE most marked number in the NW marked region to be “active” in this
iteration.

  2. 2.

Increment the active marked number by 1. If this number is equal to $k$ and at
the SE border, delete it and end the iteration. Otherwise:

    1. (a)

If the active marked number is equal to the number below, increment the number
below as well and move the mark there. Repeat this until we get a valid
tableau again.

    2. (b)

If the active marked number is equal to the number to the right, move the mark
to the rightmost number with this value on this row.

Repeat this step.

######  Proposition 5.1.

The rectification algorithm on $T^{\prime}$ described above simulates jeu de
taquin on $T$. Furthermore, the algorithm agrees with the rectification
algorithm defined on marked bumpless pipe dreams in each step when each
intermediate marked tableau is mapped to its corresponding marked bumpless
pipe dream.

###### Proof.

Step 2(a) simulates consecutive vertical slides in jeu de taquin, and Step
2(b) simulates consecutive horizontal slides. Furthermore, Step 2(a)
corresponds to an undroop column move as defined in Section 3.2, and Step 2(b)
corresponds to moving a mark to the rightmost tile in a consecutive block of
blank tiles on a row in a bumpless pipe dream. Finally, in a bumpless pipe
dream of a $k$-grassmannian permutation, the column move that removes a cross
is only available when the marked tile is in row $k$. This determines the
terminating condition in Step 2. ∎

##  Final remarks

It was shown in [LLS18] that bumpless pipe dreams compute double Schubert
polynomials, and further explained in [Wei20] that they also compute double
Grothendieck polynomials. We note that our construction cannot be easily
extended to an equivariant setting, because the $\star$-operation and the
insertion/rectification algorithm are row-biased and do not maintain the
necessary invariance for columns. A similar phenomenon is exhibited in [KY04].
However, it should be possible to generalize our result to K-theory. A
K-theoretic version of Edelman-Greene insertion for bumpless pipe dreams would
be necessary. We leave this for future work.

## References

  * [Ass17] Sami Assaf.  Multiplication of a Schubert polynomial by a Stanley symmetric polynomial.  arXiv preprint arXiv:1702.00132, 2017.
  * [Ful97] William Fulton.  Young tableaux: with applications to representation theory and geometry.  Number 35. Cambridge University Press, 1997.
  * [KM05] Allen Knutson and Ezra Miller.  Gröbner geometry of schubert polynomials.  Annals of Mathematics, pages 1245–1318, 2005.
  * [Kog00] Mikhail Kogan.  Schubert geometry of flag varieties and Gelfand-Cetlin theory.  PhD thesis, Citeseer, 2000.
  * [KY04] Allen Knutson and Alexander Yong.  A formula for K-theory truncation Schubert calculus.  International Mathematics Research Notices, 2004(70):3741–3756, 2004.
  * [KZJ] Allen Knutson and Paul Zinn-Justin.  Schubert calculus and quiver varieties.  http://pi.math.cornell.edu/~allenk/boston2019.pdf.  Pages 12–13.
  * [Len10] Cristian Lenart.  Growth diagrams for the Schubert multiplication.  Journal of Combinatorial Theory, Series A, 117(7):842–856, 2010\.
  * [LLS18] Thomas Lam, Seung Jin Lee, and Mark Shimozono.  Back stable Schubert calculus.  arXiv preprint arXiv:1806.11233, 2018.
  * [Mil03] Ezra Miller.  Mitosis recursion for coefficients of Schubert polynomials.  Journal of Combinatorial Theory, Series A, 103(2):223–235, 2003\.
  * [PS09] Kevin Purbhoo and Frank Sottile.  A Littlewood-Richardson rule for Grassmannian permutations.  Proceedings of the American Mathematical Society, 137(6):1875–1882, 2009.
  * [Wei20] Anna Weigandt.  Bumpless pipe dreams and alternating sign matrices.  arXiv preprint arXiv:2003.07342, 2020.


11institutetext: Loughborough University 11email:
<EMAIL_ADDRESS>Beijing University of Posts and
Telecommunications 22email<EMAIL_ADDRESS>33institutetext: Università
degli Studi dell’Aquila 33email<EMAIL_ADDRESS>44institutetext: University of Waterloo 44email<EMAIL_ADDRESS>55institutetext: University of Birmingham 55email<EMAIL_ADDRESS>66institutetext: University College London 66email: {w.langdon,
<EMAIL_ADDRESS>
# GreenStableYolo: Optimizing Inference Time and Image Quality of Text-to-
Image Generation

Jingzhi Gong 11 0000-0003-4551-0701 Sisi Li 22 0000-0001-5376-5144 Giordano
d’Aloisio 33 0000-0001-7388-890X Zishuo Ding 44 0000-0002-0803-5609 Yulong Ye
55 0000-0002-2478-778X William B. Langdon 66 0000-0002-6388-4160 Federica
Sarro 66 0000-0002-9146-442X

###### Abstract

Tuning the parameters and prompts for improving AI-based text-to-image
generation has remained a substantial yet unaddressed challenge. Hence we
introduce GreenStableYolo, which improves the parameters and prompts for
Stable Diffusion to both reduce GPU inference time and increase image
generation quality using NSGA-II and Yolo. Our experiments show that despite a
relatively slight trade-off (18%) in image quality compared to StableYolo
(which only considers image quality), GreenStableYolo achieves a substantial
reduction in inference time (266% less) and a 526% higher hypervolume, thereby
advancing the state-of-the-art for text-to-image generation.

###### Keywords:

SBSE ANN GenAI Text2Image Stable Diffusion Yolo

##  1 Introduction

In recent years Generative Artificial Intelligence (GenAI) has emerged as a
powerful approach encompassing various techniques that enable machines to
generate new content, such as text [13], images [19], and videos [14].
Particularly, image generation and text-to-image synthesis have garnered
significant attention due to their potential in bridging the gap between
textual descriptions and visual representations [18]. It enables systems to
understand and interpret human language and automatically translate it to a
visually meaningful way, facilitating tasks such as generating accompanying
images for books [4], generating product images for advertising [22], and
inspiring artists to create new forms of art [12].

However, achieving optimal performance in image generation tasks involves
fine-tuning various aspects of a GenAI model, such as the number of inference
steps, positive and negative prompts [1, 3]. These parameters play a crucial
role in determining the quality and efficiency of the generated images and
tuning these parameters is essential to unlock the full potential of image
generation models [3, 15]. At the same time, GenAI model are energy demanding
and largely contribute to the increased CO2 emissions[8, 20].

Berger et al. [3] proposed a search-based approach, dubbed StableYolo, to
optimize the image quality of Stable Diffusion by assessing image quality
using Yolo [17]. However, their approach do not take into account the aspect
of inference time, which is a cornerstone for both ensuring user experience
and minimizing the energy consumption of GenAI models. Especially in real-
world scenarios, where responsiveness and energy efficiency are vital,
addressing this aspect is vital for the widespread adoption of such models [5,
11, 20, 21].

To address this gap, we present GreenStableYolo, a novel approach that
addresses the challenge of optimizing the trade-off between inference time and
image quality using a search-based multi-objective optimization method, namely
Non-dominated Sorting Genetic Algorithm (NSGA-II) [6]. We provide initial
empirical evidence that by using GreenStableYolo Stable Diffusion achieves a
satisfactory equilibrium between inference time and image quality, making it
suitable for real-world applications where both factors play a crucial role.

In a nutshell, the key contributions of this work include:

  * •

The development of a novel system that seeks for an optimal trade-off between
inference time and image quality by optimizing the prompts and parameters for
Stable Diffusion, dubbed GreenStableYolo;

  * •

Empirical evidence on the effectiveness of GreenStableYolo in achieving
significantly less inference time and higher hypervolume compared to
StableYolo, thereby advancing the state-of-the-art multi-objective
optimization for text-to-image generation;

  * •

A comprehensive analysis to understand the influence of different parameters
and prompts on both inference time and image quality in Stable Diffusion.

##  2 Related Work

To improve image generation quality, Berger et al. [3] were the first to
propose the use of a Genetic Algorithm (GA) able to simultaneously tune the
prompt and parameters of Stable Diffusion. Magliani et al. [15] use GA to find
the best diffusion parameters for automated image retrieval from a dataset.
While some research [5, 11] has been carried out to optimize inference time,
from hardware design to model architecture, there has been limited work
focusing on optimizing the prompts and parameters. Our work builds upon
previous work by considering both inference time and image quality as
optimization objectives.

##  3 Methodology

To mitigate the aforementioned challenge, we propose GreenStableYolo, a novel
multi-objective search-based approach that, given a text prompt for image
generation, searches for the optimal parameters that can strike a balance
between: (1) Inference time, which is measured by the GPU time taken for the
execution of the StableDiffusionPipeline; and (2) Image quality, which is
determined by performing object recognition with Yolo, then selecting objects
that match the input prompt, and computing their average probabilities [3].

NSGA-II Optimization Algorithm To simultaneously enhance image quality and
reduce inference time, we leverage NSGA-II, a well-known and efficient multi-
objective evolutionary algorithm [10, 16]. Specifically, NSGA-II works as
follows: (1) Initialize a population with $N$ individuals; (2) Perform
crossover and mutation operations, generating an offspring population denoted
as $P_{o}$; (3) Reassemble the parent population $P_{t-1}$ and $P_{o}$ into a
temporary population with the size of $2N$, and formulate individuals into $i$
non-inferior frontier through fast non-dominating sorting; (4) Select $N$
individuals from the temporary population to form the next population for the
$t^{th}$ iteration, denoted as $P_{t}$. (5) Repeat steps (2)-(4) until the
termination condition is met; and (6) The algorithm ends up and returns the
current Pareto-Optimal set.

Selected Parameters  To make a straightforward comparison with StableYolo, we
adopt the same settings as used by Berger et al. [3]. Specifically, the
following parameters and prompts are tuned and searched with NSGA-II: (1)
Inference steps (1 to 100): the AI’s image generation iterations; (2) Guidance
scale (1 to 20): the impact of the prompt on image generation; (3) Guidance
rescale (0 to 1): rescales the guidance factor to prevent over-fitting; (4)
Seed (1 to 512): randomization seed; (5) Positive prompt: used to describe
images and improve their details, e.g., “photograph”, “color”, and “ultra
real” [2]; and (6) Negative prompt: avoided description during image
generation, e.g., “sketch”, “cropped”, and “low quality” [2].

##  4 Evaluation

To evaluate our proposal, we address the following research questions (RQs):

➤ RQ1: To what extent can GreenStableYolo improve image quality and inference
time compared with StableYolo?

➤ RQ2: How do parameters/prompts of Stable Diffusion influence the inference
time for image generation?

➤ RQ3: How do parameters/prompts of Stable Diffusion influence the quality of
the generated images?

Experimental Setup  To ensure a fair evaluation of the optimization
effectiveness, we employed the same hyperparameter setup as StableYolo for
NSGA-II, e.g., the population size was set to 25, the number of generations
was set to 50, and both the mutation rate and crossover rate were set to 0.2.
We selected the weights of 0.001 for image quality and -1000 for inference
time based on empirical investigation of different weight combinations. In
addition, we used Stable Diffusion version v2 and Yolo version v8. To assess
variability, we evaluated each model 15 times using different random seeds,
focusing solely on the prompt “two people and a bus” due to time constraints.
Any future studies can explore additional prompts. All experiments were
conducted on a virtual machine hosted on Google Colaboratory, with an NVIDIA
Tesla T4 GPU with 16 GB of RAM.

RQ1 Results  Figure 1 presents the performance comparisons between
GreenStableYolo and StableYolo. Specifically, Figure 1(a) reveals that
GreenStableYolo achieves an average inference time of 9.4 seconds with an
interquartile range (IQR) of 4.7 seconds. Conversely, StableYolo exhibits an
average inference time of 25.0 seconds, which is 1.66 times higher than
GreenStableYolo, with an IQR of 9.1 seconds. That is, GreenStableYolo
generates images much faster.

This improvement in inference time comes at a slight cost to image quality. As
illustrated in Figure 1(b), GreenStableYolo experiences approximately an
average degradation of 0.18 points in image quality. We also compute the
hypervolume [9] for both models for a more comprehensive
comparison111Hypervolume is a fundamental metric used in multi-objective
optimization problems that indicates the dominance of a solution in the
objective space.. Figure 1(c) presents the hypervolume values with the
reference point set as (1, 50000), where GreenStableYolo achieves an average
hypervolume of 29074.11, surpassing StableYolo’s score of 4642.17 by 5.26
times. _This substantial difference demonstrates the clear dominance of
GreenStableYolo over StableYolo in this two-objective optimization problem for
text-to-image generation._

(a) Inference time

(b) Yolo quality measure

(c) Hypervolume

Figure 1: Comparison of GreenStableYolo and StableYolo on 15 independent runs

RQs2-3 Results  To investigate RQs2–3, we followed previous work [7] and built
two Random Forest regression models using scikit-learn. The features of these
models include the number of iteration steps, guidance scale, guidance
rescale, positive prompts, and negative prompts (excluding the random seed).
The target variables are inference time and image quality score, respectively.
We use the RandomizedSearchCV function from scikit-learn to find the optimal
hyperparameters during model training. The feature_importances_ function is
then used to compute the importance of each parameter and prompt based on the
Mean Decrease Impurity (MDI), a.k.a. as Gini importance. To ensure
reliability, we repeat this process 10 times.

Figures 2(a) and 2(b) present the calculated importance of parameters and
prompts based on the mean decrease in impurity, with respect to inference time
and image quality scores, respectively. As shown in Figure 2(a), the number of
inference steps emerges as a significant factor affecting inference time. This
is expected, as more steps involve more computations, thereby resulting in
higher inference time. Meanwhile, for image quality (Figure 2(b)), parameters
like guidance rescale and positive prompts play a relatively more critical
role.

(a) RQ2: MDI w.r.t. inference time

(b) RQ3: MDI w.r.t. image quality

Figure 2: Parameters/prompts importance based on the mean decrease in impurity

These findings confirm the value of our work: _increased computational
resources do not necessarily translate to better image quality; instead,
appropriate model parameter settings are more crucial_. This highlights the
importance of identifying optimal parameter combinations during model
inference to balance computational efficiency and output quality.

Threats to Validity The limited exploration of prompts, the randomness in the
optimization process, and the specific configuration for NSGA-II may introduce
internal threats. Besides, external threats may include the choice of the
GenAI model, the noise when measuring the inference time, and the evaluation
of image quality based on object recognition using Yolo.

##  5 Conclusion

In GenAI text-to-image, achieving images of high-quality is often not the only
important aspect to consider, as inference time, which directly impacts user
experience and energy consumption, also plays a critical role. In this work we
introduced GreenStableYolo, the first approach leveraging NSGA-II to strike an
optimal trade-off between these two objectives for Stable Diffusion.
Experimental comparisons with StableYolo demonstrate that GreenStableYolo
achieves significantly reduced inference time while maintaining a relatively
high image quality. Future research can expand upon our evaluation by
incorporating alternative initial prompts, optimizing different performance
metrics such as energy consumption, and broadening to other GenAI systems such
as DALL-E, ImageFX, or Midjourney.

Availability  Repository available at
https://github.com/gjz78910/GreenStableYolo.

Acknowledgments  Work supported by the ERC grant no. 741278.

## References

  * [1] Stable diffusion documentation https://huggingface.co/docs/diffusers/api/pipelines/stable_diffusion/text2img
  * [2] Stable diffusion photorealistic prompts https://prompthero.com/stable-diffusion-photorealistic-prompts
  * [3] Berger, H., Dakhama, A., Ding, Z., Even-Mendoza, K., Kelly, D., Menéndez, H.D., Moussa, R., Sarro, F.: StableYolo: Optimizing image generation for large language models. In: SSBSE 2023. LNCS, vol. 14415, pp. 133–139
  * [4] Bruens, J.D., Meissner, M.: Do you create your content yourself? using generative artificial intelligence for social media content creation diminishes perceived brand authenticity. Journal of Retailing and Consumer Services 79, 103790 (2024)
  * [5] Cao, Y., Li, S., Liu, Y., Yan, Z., Dai, Y., Yu, P.S., Sun, L.: A comprehensive survey of AI-generated content (AIGC): a history of generative AI from GAN to ChatGPT. arXiv 2303.04226 (2023)
  * [6] Deb, K., Agrawal, S., Pratap, A., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)
  * [7] Ding, Z., Chen, J., Shang, W.: Towards the use of the readily available tests from the release pipeline as performance tests: are we there yet? p. 1435–1446. ICSE ’20
  * [8] Georgiou, S., Kechagia, M., Sharma, T., Sarro, F., Zou, Y.: Green ai: do deep learning frameworks have different costs? In: Procs. of the ICSE’22. p. 1082–1094
  * [9] Guerreiro, A.P., Fonseca, C.M., Paquete, L.: The hypervolume indicator: Computational problems and algorithms. ACM Computing Surveys 54(6), 1–42 (2021)
  * [10] Ji, B., Huang, H., Yu, S.S.: An enhanced NSGA-II for solving berth allocation and quay crane assignment problem with stochastic arrival times. IEEE Trans.
  * [11] Kim, S., Hooper, C., Wattanawong, T., Kang, M., Yan, R., Genc, H., Dinh, G., Huang, Q., Keutzer, K., Mahoney, M.W., Shao, Y.S., Gholami, A.: Full stack optimization of transformer inference: a survey. arXiv 2302.14017 (2023)
  * [12] Ko, H., et al.: Large-scale text-to-image generation models for visual artists’ creative works. In: Intelligent User Interfaces, IUI 2023. pp. 919–933
  * [13] Li, J., Tang, T., Zhao, W.X., Wen, J.R.: Pretrained language models for text generation: A survey. arXiv 2105.10311 (25 May 2021)
  * [14] Long, F., Qiu, Z., Yao, T., Mei, T.: VideoDrafter: Content-consistent multi-scene video generation with LLM. arXiv 2401.01256 (2 Jan 2024)
  * [15] Magliani, F., Sani, L., Cagnoni, S., Prati, A.: Genetic algorithms for the optimization of diffusion parameters in content-based image retrieval. In: ICDSC 2019
  * [16] Rashid, T.A., Majidpour, J., Thinakaran, R., Batumalay, M., Dewi, D.A., Hassan, B.A., Dadgar, H., Arabi, H.: NSGA-II-DL: metaheuristic optimal feature selection with deep learning framework for HER2 classification in breast cancer. IEEE Access
  * [17] Redmon, J., Divvala, S.K., Girshick, R.B., Farhadi, A.: You only look once: Unified, real-time object detection. In: CVPR 2016. pp. 779–788
  * [18] Reed, S.E., Akata, Z., Yan, X., Logeswaran, L., Schiele, B., Lee, H.: Generative adversarial text to image synthesis. In: ICML 2016. pp. 1060–1069
  * [19] Rombach, R., Blattmann, A., Lorenz, D., Esser, P., Ommer, B.: High-resolution image synthesis with latent diffusion models. In: CVPR. pp. 10674–10685 (2022)
  * [20] Sarro, F.: Search-based software engineering in the era of modern software systems. In: IEEE International Requirements Engineering Conference. pp. 3–5 (2023)
  * [21] Sarro, F.: Automated optimisation of modern software system properties. In: International Conference on Performance Engineering, ICPE ’23. pp. 3–4
  * [22] Yu, T., Yang, X., Jiang, Y., Zhang, H., Zhao, W., Li, P.: TIRA in Baidu image advertising. In: International Conference on Data Engineering, ICDE 2021


# A direct proof of Stahl’s theorem for a generic class of algebraic functions

Sergey P. Suetin  Steklov Mathematical Institute of the Russian Academy of
Sciences, Russia<EMAIL_ADDRESS>
(Date: July 1, 2021)

###### Abstract.

Under the assumption of the existence of Stahl’s $S$-compact set we give a
short proof of the limit zeros distribution of Padé polynomials and
convergence in capacity of diagonal Padé approximants for a generic class of
algebraic functions. The proof is direct but not from the opposite as Stahl’s
original proof is. The generic class means in particular that all branch
points of the multi-sheeted Riemann surface of the algebraic function are of
the first order (i.e., we assume the surface is such that all branch points
are of square root type).

We do not use the relations of orthogonality at all. The proof is based on the
maximum principle only.

Bibliography: [13] titles.

##  1\. Introduction

### 1.1.

The seminal Stahl’s Theory (see [12], [13], [1] and the bibliography therein)
on the convergence of diagonal Padé approximants for the multivalued analytic
functions consists of two parts. Namely, geometrical part and analytical part.
In the first part it is proven that for a multi-valued function there exists a
unique admissible compact set $S$ possesses Stahl’s symmetric property.
Traditionally it is refereed to as an $S$-compact set or briefly $S$-curve
(see [12] and [9] for details). In the original Stahl’s Theory it is supposed
that the set of singularities of a multivalued analytic function is of zero
(logarithmic) capacity. Here we restrict our investigation to the case of
finite number of singular points only. Note that a short proof of the
existence of an $S$-curve for a multivalued analytic function with a finite
number of singular points was proposed by E. Rakhmanov in 1994 in the
unpublished paper [8] (see also [6]). Rakhmanov’s proof is based on the
connection between capacity and potential of equilibrium measure of a compact
set.

In the second part of the Stahl’s Theory it is proven that there exists zeros
limit distribution of Padé polynomials and convergence in capacity of the
diagonal Padé approximants takes place as well. The original Stahl’s proof of
the existence of limit zeros distribution of Padé polynomials is based on the
method of proof from the opposite. In the current paper we give a short and
direct proof of the second part of Stahl’s Theory for a generic class of
algebraic functions and under the assumption that the first geometrical
component is valid. We do not use the relations of orthogonality at all. The
proof is based on the maximum principle only (cf. [7] and [11]).

Let introduce a generic class $\mathscr{F}$ of admissible multivalued
functions which was mentioned above.

We set that $f\in\mathscr{F}$ if the following conditions are satisfied:

(1) $f$ is an algebraic function with all the branch points of the first order
(i.e., we assume that all the branch points are of square root type);

(2) $S$-curve of $f$ consists of a finite number of non-intersected closed
analytic arcs each of which contains exactly two branch points of $f$ – the
ends of the arc.

Some discussion on this assumptions are given in Section 3.

### 1.2.

Let $f\in\mathscr{F}$, $f_{\infty}\in\mathscr{H}(\infty)$ and
$S=S(f_{\infty})$ be the corresponding Stahl’s compact set. Let $\lambda_{S}$
be the probability equilibrium measure supported on $S$ and
$V^{\lambda_{S}}(z)$ be the corresponding logarithmic potential of
$\lambda_{S}$:

$V^{\lambda_{S}}(z)=\gamma_{S}-g_{S}(z,\infty),\quad z\in
D:=\widehat{\mathbb{C}}\setminus S,$ (1)

$g_{S}(z,\infty)$ is the Green function for the domain $D$ with the
logarithmic singularity at the infinity point $z=\infty$ and $\gamma_{S}$ is
the Robin constant for $D$.

Set $\mathbb{P}_{n}:=\mathbb{C}_{n}[z]$ be the set of all algebraic
polynomials with complex coefficients of order $\leqslant{n}$. For arbitrary
polynomial $Q\in\mathbb{C}[z]$, $Q\not\equiv 0$, we denote by $\chi(Q)$ the
zero counting measure of $Q$:
$\chi(Q):=\sum\limits_{\zeta:Q(\zeta)=0}\delta_{\zeta}$, where each zero of
$Q$ is represented with respect to its multiplicity.

For $f_{\infty}\in\mathscr{H}(\infty)$ and arbitrary $n\in\mathbb{N}$ Padé
polynomials $P_{n},Q_{n}\in\mathbb{P}_{n}$, $Q_{n}\not\equiv 0$, are defined
(non-uniquely) from the following relation:

$R_{n}(z):=(Q_{n}f_{\infty}-P_{n})(z)=O\left(\frac{1}{z^{n+1}}\right),\quad
z\to\infty;$ (2)

$R_{n}(z)$ is the so-called error function.

The following result holds (see [12], [13]).

######  Theorem 1.

Let $f\in\mathscr{F}$ and $f_{\infty}\in\mathscr{H}(\infty)$. Then as
$n\to\infty$

$\frac{1}{n}\chi(Q_{n}),\frac{1}{n}\chi(P_{n})\overset{*}{\longrightarrow}\lambda_{S}.$
(3)

Set $Q_{n}(z)=z^{k_{n}}+\dotsb$, then as $n\to\infty$

$\displaystyle|R_{n}(z)|^{1/n}\overset{\operatorname{cap}}{\longrightarrow}\operatorname{cap}(S)e^{-g_{S}(z,\infty)}\quad\text{inside
$D$},$ (4)
$\displaystyle\bigl{|}f(z)-[n/n]_{f}(z)\bigr{|}^{1/n}\overset{\operatorname{cap}}{\longrightarrow}e^{-2g_{S}(z,\infty)}\quad\text{inside
$D$}.$ (5)

Recall that the existence of an $S$-compact set for a function
$f\in\mathscr{F}$ follows from [8].

##  2\. Proof of Theorem 1

### 2.1.

For two positive sequences $\\{\alpha_{n}\\}$ and $\\{\beta_{n}\\}$ the
relation $\alpha_{n}\asymp\beta_{n}$ means that
$0<C_{1}\leqslant\alpha_{n}/\beta_{n}\leqslant C_{2}<\infty$ for $n=1,2,\dots$
and some constants $C_{1},C_{2}$ which do not depend on $n$. For two sequences
$\\{\alpha_{n}(z)\\}$ and $\\{\beta_{n}(z)\\}$ of functions holomorphic in a
domain $\Omega$ the relation $\alpha_{n}\asymp\beta_{n}$ means that for each
compact set $K\subset\Omega$ and $n=1,2,\dots$
$0<C_{1}\leqslant|\alpha_{n}(z)/\beta_{n}(z)|\leqslant C_{2}<\infty$ for $z\in
K$ where the constants $C_{1},C_{2}$ depend on $K$ but do not depend on $n$
and $z\in K$. Evidently that for such pairs of sequences and functions we have
that $|\alpha_{n}/\beta_{n}|^{1/n}\to 1$ as $n\to\infty$.

Since $f\in\mathscr{F}$, we have that
$S=S(f)=\bigsqcup\limits_{j=1}^{p}S_{j}$, where
$S_{j}=\operatorname{arc}(a_{2j-1},a_{2j})$. Set
$w^{2}=\prod\limits_{j=1}^{p}(z-a_{2j-1})(z-a_{2j})$. Then the two-sheeted
hyperelliptic Riemann surface (RS) $\mathfrak{R}_{2}(w)$ of the function $w$
is the RS associated with $f_{\infty}\in\mathscr{H}(\infty)$,
$f\in\mathscr{F}$, in accordance with Stahl’s Theory. Point $\mathbf{z}$ on
$\mathfrak{R}_{2}(w)$ is given by $\mathbf{z}=(z,w)$. The RS
$\mathfrak{R}_{2}(w)$ may be considered as a two-sheeted covering of the
Riemann sphere $\widehat{\mathbb{C}}$ with the canonical projection $\pi$,
$\pi\colon\mathfrak{R}_{2}(w)\to\widehat{\mathbb{C}}$, $\pi(\mathbf{z})=z$.
Let $\boldsymbol{\Gamma}:=\pi^{-1}(S)$. Then $\Gamma$ shares
$\mathfrak{R}_{2}(w)$ into two domains, We shall call them the (open) sheets
of $\mathfrak{R}_{2}(w)$. The function $w$ is a single-valued function on this
RS and has opposite signs on the sheets. We denote by $\mathfrak{R}_{2}^{(0)}$
the sheet of $\mathfrak{R}_{2}(w)$ where $w(z)/z^{p}\to 1$ as $z\to\infty$ and
refereed to it as zero sheet. Another sheet will be denoted by
$\mathfrak{R}^{(1)}_{2}$ and refereed to as first sheet of
$\mathfrak{R}_{2}(w)$. Then we have
$\mathfrak{R}_{2}(w)=\mathfrak{R}_{2}^{(0)}\sqcup\Gamma\sqcup\mathfrak{R}_{2}^{(1)}$.
Points on the sheets will be denoted by $z^{(j)}$, $j=0,1$, respectively.
Evidently $\pi(\mathfrak{R}_{2}^{(j)})=D$. We shall identify
$\mathfrak{R}_{2}^{(0)}$ with the Stahl’s domain
$D=\widehat{\mathbb{C}}\setminus{S}$ and $\infty^{(0)}$ with $\infty$ and
consider the germ $f_{\infty}$ as the germ $f_{\infty^{(0)}}$. In general
$\mathfrak{R}_{2}(w)$ is not the Riemann surface of $f$ and thus $f$ is not a
single-valued on $\mathfrak{R}_{2}(w)$. But since $f\in\mathscr{F}$ the germ
$f_{\infty^{(0)}}$ can be extended from the infinity point $\infty^{(0)}$ to
the whole zero sheet $\mathfrak{R}^{(0)}_{2}$ and even more to a small enough
neighborhood $V^{(0,1)}$ of $\boldsymbol{\Gamma}$ ,
$V^{(0,1)}\cap\mathfrak{R}_{2}^{(1)}\neq\varnothing$. In accordance with
Stahl’s Theory (see also [8]) the Green function $g_{S}(z,\infty)$ of $D$ can
be lifted to RS $\mathfrak{R}_{2}(w)$ as $g(\mathbf{z})$ with the following
properties: $g(z^{(0)})=g(z,\infty)$, $g(z^{(1)})=-g(z^{(0})<0$. From now on
we shall suppose that $V^{(0,1)}$ is such that $\partial
V^{(0,1)}\cap\mathfrak{R}_{2}^{(1)}=\\{z^{(1)}:g(z,\infty)=\log{R}\\}$, $R>1$.
Set $\mathfrak{D}:=\mathfrak{R}_{2}^{(0)}\cup V^{(0,1)}$ be a domain on
$\mathfrak{R}_{2}(w)$ and $f_{\infty^{(0)}}$ continues in $\mathfrak{D}$ as a
meromorphic (analytic and single-valued) function,
$f\in\mathscr{M}(\mathfrak{D})$. The function $R_{n}(z)$ is also extended to
$\mathfrak{D}$ as a meromorphic function $R_{n}(\mathbf{z})$. Let a polynomial
$q_{m}(z)=z^{m}+\dotsb$ is such that the set of its zeros coincide with the
projection of poles of $f$ in $\mathfrak{D}$. Then $\widetilde{f}:=q_{n}f$ and
$q_{m}R_{n}$ are holomorphic functions in $\mathfrak{D}$.

### 2.2.

For each $\rho\in(1,R)$ we denote by $\Gamma^{(1)}_{\rho}$ the set of points
$z^{(1)}$ such that $g_{S}(z,\infty)=\log\rho$ as
$z^{(1)}\in\Gamma^{(1)}_{\rho}$. Clearly we have $g(z^{(1)})=-\log\rho$. The
set $\Gamma^{(0)}_{\rho}$ is defined similarly and we have on that set
$g(z^{(0)})=\log\rho$. For $\rho\in(1,R)$ let $D^{(1)}_{\rho}$ be a subdomain
of $\mathfrak{D}$ with $\partial D^{(1)}_{\rho}=\Gamma^{(1)}_{\rho}$,
$\infty^{(0)}\in D^{(1)}$. Similarly $D^{(0)}_{\rho}\subset\mathfrak{D}$,
$\partial D^{(0)}=\Gamma^{(0)}_{\rho}$, $\infty^{(0)}\in D^{(0)}$. Set

$u_{n}(\mathbf{z}):=\log|q_{m}(z)R_{n}(\mathbf{z})|+(n+1-m)g(\mathbf{z}),\quad\mathbf{z}\in\mathfrak{D}.$
(6)

Function $u_{n}$ is a subharmonic function in $\mathfrak{D}$. Thus for each
$\rho\in(1,R)$ we have that

$u_{n}(\mathbf{z})\leqslant\max_{\mathbf{\zeta}\in\Gamma^{(1)}_{\rho}}u_{n}(\zeta),\quad\mathbf{z}\in
D^{(1)}_{\rho}.$ (7)

From (7) it follows that

$\bigl{|}R_{n}(z^{(0)})q_{m}(z)\bigr{|}\leqslant\frac{1}{\rho^{2n+2-2m}}M_{n,1}(\rho),\qquad
z\in\Gamma_{\rho}.$ (8)

where we set
$M_{n,1}(\rho):=\max\limits_{z\in\Gamma_{\rho}}|R_{n}(z^{(1)})q_{m}(z)|$.
Relations (6) and (7) imply that for $1<\rho_{1}<\rho_{2}<R$ we have

$M_{n,1}(\rho_{1})\leqslant\left(\frac{\rho_{2}}{\rho_{1}}\right)^{n-m+1}M_{n,1}(\rho_{2}).$
(9)

The following identity holds true:

$\displaystyle R_{n}(z^{(0)})$
$\displaystyle=Q_{n}(z)f(z^{(0)})-P_{n}(z)=Q_{n}(z)f(z^{(1)})-P_{n}(z)+Q_{n}(z)[f(z^{(0)})-f(z^{(1)})]$
$\displaystyle=R_{n}(z^{(1)})+Q_{n}(z)[f(z^{(0)})-f(z^{(1)})],\quad
z\in\Gamma_{\rho}.$ (10)

From (8) and (9) it follows that

$\max_{z\in\Gamma_{\rho}}|Q_{n}(z)[f(z^{(0)})-f(z^{(1)})]q_{m}(z)|=M_{n,1}(\rho)(1+\varepsilon_{n}),\quad\varepsilon_{n}\to
0.$ (11)

From now on we shall consider only such $\rho\in(1,R)$ that
$|q_{m}(z)[f(z^{(0)})-f(z^{(1)})]|\geqslant C(\rho)>0$ as $z\in\Gamma_{\rho}$
(clearly, $f(z^{(0)})-f(z^{(1)})\not\equiv 0$). Set
$m_{n}(\rho):=\max\limits_{z\in\Gamma_{\rho}}|Q_{n}(z)|$. Then from (11) it
follows that

$m_{n}(\rho)\asymp M_{n,1}(\rho).$ (12)

Since $\operatorname{deg}{Q_{n}}\leqslant{n}$, then Bernstein–Walsh theorem
gives us the inequality:

$|Q_{n}(z)|\leqslant e^{ng_{\Gamma_{\rho_{1}}}(z,\infty)}m_{n}(\rho_{1}),\quad
z\in\Gamma_{\rho_{2}},\quad\rho_{2}>\rho_{1},$ (13)

where $g_{\Gamma_{\rho_{1}}}(z,\infty)$ is the Green function for the domain
$g_{S}(z,\infty)>\log\rho_{1}$. Clearly,
$g_{\Gamma_{\rho_{1}}}(z,\infty)=g_{S}(z,\infty)-\log\rho_{1}$. From (13) we
obtain the estimate

$m_{n}(\rho_{2})\leqslant\left(\frac{\rho_{2}}{\rho_{1}}\right)^{n}m_{n}(\rho_{1}).$
(14)

After combining the relations (9), (12) and (14) we obtain that

$m_{n}(\rho_{2})\asymp\left(\frac{\rho_{2}}{\rho_{1}}\right)^{n}m_{n}(\rho_{1})\quad\text{and}\quad
M_{n,1}(\rho_{2})\asymp\left(\frac{\rho_{2}}{\rho_{1}}\right)^{n}M_{n,1}(\rho_{1}).$
(15)

Let $Q_{n}(z)=z^{k_{n}}+\dotsb$,
$k_{n}=\operatorname{deg}{Q_{n}}\leqslant{n}$. Again Bernstein–Walsh theorem
gives us the inequality:

$|Q_{n}(z)|\leqslant
e^{k_{n}g_{\Gamma_{\rho_{1}}}(z,\infty)}m_{n}(\rho_{1}),\quad
z\in\Gamma_{\rho_{2}},\quad\rho_{2}>\rho_{1}.$ (16)

From this relation it follows that

$m_{n}(\rho_{2})\leqslant\left(\frac{\rho_{2}}{\rho_{1}}\right)^{k_{n}}m_{n}(\rho_{1}).$
(17)

But in accordance with (15)
$m_{n}(\rho_{2})\asymp(\rho_{2}/\rho_{1})^{n}m_{n}(\rho_{1})$. From here and
(17) we obtain the inequality

$\left(\frac{\rho_{2}}{\rho_{1}}\right)^{n}\leqslant
C\left(\frac{\rho_{2}}{\rho_{1}}\right)^{k_{n}},$ (18)

where $C=C(\rho_{1},\rho_{2})$, $k_{n}\leqslant{n}$, $1<\rho_{1}<\rho_{2}$. It
directly follows from (18) that

$\operatorname{deg}{Q_{n}}/n\to 1,\quad n\to\infty.$ (19)

### 2.3.

Let $D_{\rho}:=\\{z\in\widehat{\mathbb{C}}:g_{S}(z,)>\log\rho\\}$, $\rho>1$,
$g_{\Gamma_{\rho}}(z,\infty)$ be the Green function for $D_{\rho}$. Then
$g_{\Gamma_{\rho}}(z,\infty)=g_{S}(z,\infty)-\log\rho=\log{|z|}+\gamma_{\rho}+o(1)=\log|z|+\gamma_{S}-\log\rho+o(1)$.
Thus $\gamma_{\rho}=\gamma_{S}-\log\rho$.

Set

$u_{n}(z):=\frac{1}{k_{n}}\log|Q_{n}(z)|-g_{\Gamma_{\rho}}(z,\infty)-\frac{1}{k_{n}}\log
m_{n}(\rho).$ (20)

Since function $u_{n}$ is subharmonic in the domain $D_{\rho}$ and
$u_{n}\leqslant 0$ on $\Gamma_{\rho}$, then $u_{n}\leqslant 0$ in $D_{\rho}$
and $u_{n}(\infty)\leqslant 0$. Thus we have that
$\log\rho-\gamma_{S}\leqslant\log m_{n}(\rho)^{1/k_{n}}$ and finally obtain

$m_{n}(\rho)^{1/k_{n}}\geqslant\rho
e^{-\gamma_{S}}=\rho\operatorname{cap}(S).$ (21)

For $z\in K\Subset D\rho$ and $\zeta\in\Gamma_{\rho}$ we have by definition
$g_{\Gamma_{\rho}}(z,\zeta)=0$. Let now extend the function
$g_{\Gamma_{\rho}}(z,\zeta)$ inside $\Gamma_{\rho}$ by identity
$g_{\Gamma_{\rho}}(z,\zeta)\equiv 0$ when $z\in D_{\rho}$,
$\zeta\in\operatorname{int}\Gamma_{\rho}$.

Let $Q_{n}(z)=\prod\limits_{j=1}^{k_{n}}(z-\zeta_{j})$,

$v_{n}(z):=\frac{1}{k_{n}}\log|Q_{n}(z)|-g_{\Gamma_{\rho}}(z,\infty)+\frac{1}{k_{n}}\sum_{j=1}^{k_{n}}g_{\Gamma_{\rho}}(z,\zeta_{j})-\frac{1}{k_{n}}\log
m_{n}(\rho),$ (22)

$z\in D_{\rho}$. Then $v_{n}$ is a harmonic function in $D_{\rho}$ and
$v_{n}\leqslant 0$ on $\Gamma_{\rho}$. From this it follows that for
$z\in\Gamma_{\rho_{2}}$, $\rho<\rho_{2}<R$, we have

$|Q_{n}(z)|\exp\left\\{\sum_{j=1}^{k_{n}}g_{\Gamma_{\rho}}(z,\zeta_{j})\right\\}\leqslant
m_{n}(\rho)\exp\biggl{\\{}k_{n}g_{\Gamma_{\rho}}(z,\infty)\biggr{\\}}.$ (23)

Let $z_{n}^{*}\in\Gamma_{\rho_{2}}$ is such that
$|Q_{n}(z_{n}^{*})|=m_{n}(\rho_{2})$. Then from (23) we obtain that

$m_{n}(\rho_{2})\exp\biggl{\\{}\sum_{j=1}^{k_{n}}g_{\Gamma_{\rho}}(z_{n}^{*},\zeta_{j})\biggr{\\}}\leqslant
m_{n}(\rho)\left(\frac{\rho_{2}}{\rho}\right)^{k_{n}}.$ (24)

Ultimately from (24) and (15) we obtain that

$\exp\biggl{\\{}\frac{1}{k_{n}}\sum_{j=1}^{k_{n}}g_{\Gamma_{\rho}}(z_{n}^{*},\zeta_{j})\biggr{\\}}\leqslant
C(\rho,\rho_{2})^{1/k_{n}},\quad\varepsilon_{n}\to 0.$ (25)

Let now $\Lambda\subset\mathbb{N}$ is a subsequence such that $z_{n}^{*}\to
z^{*}\in\Gamma_{\rho_{2}}$ and $\frac{1}{k_{n}}\chi(Q_{n})\to\mu$ as
$n\to\infty$, $n\in\Lambda$, $\mu(1)=1$. Then according to the descendence
principle (see [5, Chapter I, § 3, Theorem 1.3], [10], [2] and [3]), we have
that

$\int g_{\Gamma_{\rho}}(z^{*},\zeta)\,d\mu(\zeta)\leqslant 0,\quad
z^{*}\in\Gamma_{\rho_{2}},\quad\rho_{2}>\rho.$ (26)

It directly follows from (26) that
$\operatorname{supp}{\mu}\subset\widehat{\mathbb{C}}\setminus D_{\rho}$. Since
it is true for every $\rho>1$ than we have that
$\operatorname{supp}{\mu}\subset S$.

### 2.4.

So we have got that $k_{n}/n\to 1$ and each limit point $\mu$ of the sequence
$\\{\frac{1}{k_{n}}\chi(Q_{n})\\}$ satisfies the condition
$\operatorname{supp}\mu\subset S$.

Since $\operatorname{supp}{\mu}\subset{S}$ we have that

$\varlimsup_{\begin{subarray}{c}n\to\infty\\\
n\in\Lambda\end{subarray}}m_{n}(\rho)^{1/k_{n}}\leqslant C_{2}<\infty.$

Also from (21) it follows that

$\varliminf_{\begin{subarray}{c}n\to\infty\\\
n\in\Lambda\end{subarray}}m_{n}(\rho)^{1/k_{n}}\geqslant C_{1}>0.$

Set

$u_{n}(z):=\frac{1}{k_{n}}\log\frac{1}{|Q_{n}(z)|}-\frac{1}{k_{n}}\sum_{j=1}^{k_{n}}g_{\Gamma_{\rho}}(z,\zeta_{j})+g_{\Gamma_{\rho}}(z,\infty),\quad
z\in D_{\rho}.$

Then $\\{u_{n}\\}$ is a sequence of harmonic functions in $D_{\rho}$. Let
$u(z)=\lim\limits_{n\to\infty}u_{n}(z)$. Then $u$ is a harmonic function with
the following properties (see (15)):

$\displaystyle u(z)=V^{\mu}(z)-V^{\lambda_{S}}(z)+\operatorname{const},$
$\displaystyle\min_{z\in\Gamma_{\rho_{1}}}u(z)=\min_{z\in\Gamma_{\rho_{2}}}u(z)\quad\text{for
each}\quad\rho_{1},\rho_{2}>\rho.$

From this it follows that $u(z)=\operatorname{const}$ and thus
$V^{\mu}(z)=V^{\lambda_{S}}(z)$ for $z\in D_{\rho}$. Since
$\operatorname{supp}\mu\subset S$, then $V^{\mu}(z)=V^{\lambda_{S}}$ for $z\in
D$. Finally $\mu=\lambda_{S}$ because $S$ has no inner points.

Eventually we have that for each $\rho>1$ there exist the limits

$\displaystyle\lim_{n\to\infty}m_{n}(\rho)^{1/n}=\lim_{n\to\infty}M_{n,1}(\rho)^{1/n}=\rho\operatorname{cap}{S},\quad\rho>1,$
(27) $\displaystyle\lim_{n\to\infty}\max_{z\in
S}|Q_{n}(z)|^{1/n}=\operatorname{cap}{S}=e^{-\gamma_{S}},\quad\lim_{n\to\infty}\max_{z\in\Gamma_{\rho}}|R_{n}(z^{(0)})|^{1/n}=\frac{1}{\rho}e^{-\gamma_{S}}.$
(28)

From the above it easy to prove that

$|R_{n}(z)|^{1/n}\overset{\operatorname{cap}}{\longrightarrow}\operatorname{cap}(S)e^{-g_{S}(z,\infty)},\quad
n\to\infty.$ (29)

Indeed, let

$v_{n}(z):=\frac{1}{n-m+1}\log|q_{m}(z)R_{n}(z)|+g_{S}(z,\infty)+\gamma_{S}.$
(30)

Then for each $\rho>1$ function $v_{n}$ is a subharmonic function in
$D_{\rho}$ and from (28) it follows that for $z\in\Gamma_{\rho}$ we have

$v_{n}(z)\leqslant C_{n},$ (31)

where $C_{n}\to 0$ as $n\to\infty$. From (31) we obtain that for $z\in
D_{\rho}$

$|q_{m}(z)R_{m}(z)|^{1/(n-m+1)}\leqslant\operatorname{cap}(S)e^{-g_{S}(z,\infty)}e^{C_{n}}.$
(32)

Thus

$\varlimsup_{n\to\infty}|R_{n}(z)|^{1/n}\leqslant\operatorname{cap}(S)e^{-g_{S}(z,\infty)}.$
(33)

Relation (29) follows from (28) and (33) by two-constants theorem (cf. [4, §
3, subsection 8, (31)–(36)]).

Since $\frac{1}{n}\chi(Q_{n})\to\lambda_{S}$, then inside $D$

$|Q_{n}(z)|^{1/n}\overset{\operatorname{cap}}{\longrightarrow}e^{-V^{\lambda_{S}}(z)},\quad
n\to\infty.$ (34)

From (29) and (34) the relation (5) follows.

Theorem 1 is proven.

##  3\. Appendix

In fact the admissible class of analytic functions is wider then it is
described in the items (1)–(2) of definition of $\mathscr{F}$. In particular
our approach is valid for the class of multivalued functions generated by the
inverse Zhoukovskii transform. More precisely, let
$\varphi(z):=z+(z^{2}-1)^{1/2}$, where
$z\in\widehat{\mathbb{C}}\setminus\Delta$, $\Delta=[-1,1]$ and such branch of
the function $(\cdot)^{1/2}$ is chosen that $\varphi(z)/z\to 2$ as
$z\to\infty$. Let $1<A<B<\infty$ and $a:=(A+1/A)/2$, $b:=(B+1/B)/2$. Then the
function

$\mathfrak{f}_{\Delta}(z):=\left[\left(A-\frac{1}{\varphi(z)}\right)\left(B-\frac{1}{\varphi(z)}\right)\right]^{1/2}$
(35)

is an algebraic function of forth order with the set of square root
singularities $\Sigma(\mathfrak{f})=\\{\pm 1,a,b\\}$. Under the above
conditions on $(\cdot)^{1/2}$ we have that
$\mathfrak{f}\in\mathscr{H}(\widehat{\mathbb{C}}\setminus\Delta)$ and Stahl’s
compact set $S(\mathfrak{f})=[-1,1]$. Now let $\varphi_{\Delta_{j}}(z)$ be the
inverse Zhoukovskii function for a segment
$\Delta_{j}:=[\alpha_{j},\beta_{j}]$, $j=1,\dots,m$,
$\Delta_{j}\cap\Delta_{k}=\varnothing$, $j\neq k$. Set

$\mathfrak{f}(z):=\prod_{j=1}^{m}{\mathfrak{f}}_{\Delta_{j}}(z),$ (36)

where each $\mathfrak{f}_{\Delta_{j}}(z)$ is defined by (35) with some
suitable $A_{j}$ and $B_{j}$.

When all $\Delta_{j}\subset\mathbb{R}$, $j=1,\dots,m$, then
$S(\mathfrak{f})=\bigsqcup\limits_{j=1}^{m}\Delta_{j}$, Since
$\mathbb{C}(z,\mathfrak{f})\subset\mathscr{F}$, our approach is valid for each
$f\in\mathbb{C}(z,\mathfrak{f})$.

Another admissible and non-trivial subclass of $\mathscr{F}$ is obtained when
at least one of the branch points $\alpha_{j},\beta_{j}$, $j=1,\dots,m$, of
$\mathfrak{f}$ does not belong to the real line.

We can generalize (35) in the following way. Set

${\mathfrak{f}}_{\Delta}(z):=\prod\left(A-\frac{1}{\varphi(z)}\right)^{\alpha}\left(B-\frac{1}{\varphi(z)}\right)^{\beta}\cdot\dotsc\cdot\left(C-\frac{1}{\varphi(z)}\right)^{\gamma},$
(37)

where $\alpha,\beta,\dots,\gamma\in\mathbb{C}\setminus\mathbb{Z}$,
$\alpha+\beta+\dots+\gamma\in\mathbb{Z}$, to obtain functions which are not
from $\mathscr{F}$ but for which the proof from Section 2 is also valid.

## References

  * [1] A. I. Aptekarev, V. I. Buslaev, A. Martínez-Finkelshtein, S. P. Suetin , ‘‘Padé approximants, continued fractions, and orthogonal polynomials ’’, Russian Math. Surveys , 2011 , 66 , 6 , 1049–1131.
  * [2] E. M. Chirka , ‘‘Potentials on a compact Riemann surface ’’, ‘‘Complex analysis, mathematical physics, and applications ’’, Collected papers , Tr. Mat. Inst. Steklova , 2018 , 301 , MAIK Nauka/Interperiodica , Moscow , 287–319.
  * [3] E. M. Chirka , ‘‘Capacities on a Compact Riemann Surface ’’, ‘‘Analysis and mathematical physics ’’, Collected papers. On the occasion of the 70th birthday of Professor Armen Glebovich Sergeev , Tr. Mat. Inst. Steklova , 2020 , 311 , Steklov Math. Inst. , Moscow , 41–83.
  * [4] A. A. Gonchar, E. A. Rakhmanov , ‘‘Equilibrium distributions and degree of rational approximation of analytic functions ’’, Mat. Sb. (N.S.) , 1987 , 134(176) , 3(11) , 306–352.
  * [5] N. S. Landkof , ‘‘Foundations of modern potential theory ’’, Springer-Verlag , Berlin-Heidelberg-New York , 1972 , .
  * [6] A. Martínez-Finkelshtein, E. A. Rakhmanov, S. P. Suetin , ‘‘Variation of the equilibrium energy and the $S$-property of stationary compact sets ’’, Sb. Math. , 2011 , 202 , 12 , 1831–1852.
  * [7] J. Nuttall , ‘‘Asymptotics of diagonal Hermite–Padé polynomials ’’, 1984 , J. Approx.Theory , 42 , 299–386.
  * [8] E. A. Perevoznikova, E. A. Rakhmanov, ‘‘The variation of the equilibrium energy and the $S$-property of compact sets of minimal capacity’’, Manuscript, In Russian. 1994,
  * [9] E. A. Rakhmanov , ‘‘Orthogonal polynomials and $S$-curves ’’, ‘‘Recent advances in orthogonal polynomials, special functions and their applications ’’, 11th International Symposium, , August 29-September 2, 2011 Universidad Carlos III de Madrid Leganes, Spain , Contemp. Math. , 578 , ed . J. Arvesu and G. Lopez Lagomasino , Amer. Math. Soc. , Providence, RI , 2012, 195–239.
  * [10] Edward B. Saff, Vilmos Totik , ‘‘Logarithmic potentials with external fields ’’, Appendix B by Thomas Bloom , Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] , 316 , Springer-Verlag , Berlin , 1997 , .
  * [11] Herbert Stahl , ‘‘Three different approaches to convergence problem of diagonal Padé approximants ’’, ‘‘Rational approximation and applications in mathematics and physics ’’, Lancut, 1985 , Lecture Notes in Math. , 1237 , Springer, Berlin, 1987, 79–124.
  * [12] Herbert Stahl , ‘‘The convergence of Padé approximants to functions with branch points ’’, J. Approx. Theory, 91, 1997, 2, 139–204.
  * [13] Herbert R. Stahl, ‘‘Sets of Minimal Capacity and Extremal Domains’’, 112 pp.. arXiv: 1205.3811