# Generating Function for Pinsky’s Combinatorial Second Moment Formula for the
Generalized Ulam Problem

Samen Hossein
The Bronx High School of Science
75 Bronx Science Bvd
Bronx, NY 10468
Shannon Starr111 Partially funded by Simons Collaboration Grant
Department of Mathematics
University of Alabama at Birmingham
University Hall, Room 4005
1402 Tenth Avenue South
Birmingham, AL 35294-1241
<EMAIL_ADDRESS>
(January 7, 2023)

###### Abstract

In two papers, Ross Pinsky considered the generalized Ulam’s problem for the
distribution of the number of increasing subsequences of length $k$ in a
random permutation of $\\{1,\dots,n\\}$. The probability that there is at
least one increasing subsequence of length $k$ equals $1-F(k)$, where $F$ is
the cdf of the length of the longest increasing subsequence. Hence we call it
the “generalized Ulam problem.” Pinsky found various interesting results, but
we consider just his combinatorial formula for the second moment, which is the
first step towards calculating all higher moments. Pinsky obtained rigorous
general bounds sufficient to determine applicability of the Paley-Zygmund
second moment method. Spin glass theorists would still like the precise
asymptotics. We formulate the generating function for his $A(N,j)$ sequence
using the complex analysis approach as in the monograph of Pemantle and
Wilson.

##  1 Introduction

Ulam’s problem is a problem that involves a combination of tools and
techniques from the intersection of various subfields and specialities in
mathematics, statistics and physics. It has been studied by many top
researchers. The main results are beautiful, but diffficult.

The depth of the results related to Ulam’s problem is well-known. There are
good reviews. See, for example, the review article of Aldous and Diaconis [2].
Many new and important results have been discovered since the publication of
that particular paper. One notable recent development is the directed
landscape perspective [5].

We will state the actual problem known as Ulam’s problem. Let $\pi$ be a
random permutation in $S_{n}$, chosen according to the uniform measure. So for
any permutation in $S_{n}$, the probability for $\pi$ to equal that one
permutation is $1/n!$. Ulam’s problem involves increasing subsequences for
$\pi$. Given a cardinality $k$ subset of $\\{1,\dots,n\\}$, we may write the
set as $\\{i_{1},\dots,i_{k}\\}$ for

$1\leq i_{1}<\dots<i_{k}\leq n\,.$ (1)

Then we say that $(i_{1},\dots,i_{k})$ is an increasing subsequence for $\pi$
if

$\pi_{i_{1}}\,<\,\dots\,<\,\pi_{i_{k}}\,.$ (2)

If we fix $(i_{1},\dots,i_{k})$ and vary over $\pi$, then the probability of
the event, “$(i_{1},\dots,i_{k})$ is an increasing subsequence for $\pi$,” is
equal to $1/k!$. This is because if we are given $k$ numbers
$\\{j_{1},\dots,j_{k}\\}$ satisfying

$1\,\leq\,j_{1}\,<\,\dots\,<\,j_{k}\,\leq\,n\,,$ (3)

and we are told that we have equality of the sets

$\\{\pi_{i_{1}},\dots,\pi_{i_{k}}\\}\,=\,\\{j_{1},\dots,j_{k}\\}\,,$ (4)

then there are still $k!$ possible permutations
$\sigma=(\sigma_{1},\dots,\sigma_{k})\in S_{k}$ such that

$\forall r\in\\{1,\dots,k\\}\,,\ \text{ we have }\
\pi_{i_{r}}=j_{\sigma_{r}}\,.$ (5)

But for $(i_{1},\dots,i_{r})$ to be an increasing subsequence for $\pi$, then
we want $\pi_{i_{r}}=j_{r}$ for all $r$. That means $\sigma=(1,2,\dots,k)$,
the identity element of $S_{k}$, which is just one of the $k!$ possible
permutations.

Ulam’s problem is to determine the distribution of $L(n)$, the length of the
longest increasing subsequence for $\pi$: the largest $k$ such that there is
at least one subsequence $(i_{1},\dots,i_{k})$ which is increasing for $\pi$.
Hammersley used Markov’s bound and Kingman’s subadditive theorem to garner
information about $L(n)$ in the large $n$ limit. Let $Z(n,k)$ denote the
number of subsequences of cardinality $k$ which are increasing for $\pi$:

$Z(n,k)\,=\,\sum_{i_{1},\dots,i_{k}=1}^{n}\prod_{r=1}^{n-1}\left(\mathbf{1}_{(0,\infty)}(i_{r+1}-i_{r})\cdot\mathbf{1}_{(0,\infty)}(\pi_{i_{r+1}}-\pi_{i_{r}})\right)\,.$
(6)

Then
$\sum_{i_{1},\dots,i_{k}=1}^{n}\prod_{r=1}^{n-1}\mathbf{1}_{(0,\infty)}(i_{r+1}-i_{r})$
is equal to $n$-choose-$k$, and for each $(i_{1},\dots,i_{k})$ we know

$\mathbf{P}(\pi_{i_{1}}<\dots<\pi_{i_{k}})\,=\,\frac{1}{k!}\,.$ (7)

Therefore,

$\mathbf{E}[Z(n,k)]\,=\,\binom{n}{k}\cdot\frac{1}{k!}\,.$ (8)

Then, using Markov’s inequality, it is easily seen that

$\mathbf{P}(Z(n,k)>0)\,=\,\mathbf{P}(L(n)\geq k)\,\leq\,\mathbf{E}[Z(n,k)]\,.$
(9)

Then, by Stirling’s formula, writing $x$ for $k/\sqrt{n}$,

$\binom{n}{k}\cdot\frac{1}{k!}\,\sim\,\frac{\exp\left(-2xn^{1/2}\,\ln\left(x/e\right)-\frac{1}{2}\,x^{2}+\delta_{n}(x)\right)}{2\pi
xn^{1/2}(1-xn^{-1/2})^{1/2}}\,,$ (10)

in the limit $k\to\infty$, $n-k\to\infty$, where

$\delta_{n}(x)\,=\,xn^{1/2}\ln\left(1-xn^{-1/2}\right)-n\,\ln\left(e^{xn^{-1/2}}\left(1-xn^{-1/2}\right)\right)+\frac{x^{2}}{2}\,,$
(11)

which would be $o(1)$ as long as $xn^{-1/2}=o(1)$. In [9], Hammersley used the
subadditive ergodic theorem to prove that

$\liminf_{n\to\infty}n^{1/2}\mathbf{E}[L_{n}]\,=\,\limsup_{n\to\infty}n^{1/2}\mathbf{E}[L_{n}]\,=\,c\,,$
(12)

for some number $c$ which a priori could have been in $(0,\infty]$. But by
equation (10), he noted $c\leq e$. In fact, an equally simple argument using
the Erdös-Szekeres theorem gives $c\geq 1/2$. See, for example, Section 1.4 of
Steele’s monograph [15].

The actual mean is approximately $2\sqrt{n}$ by a result of Vershik and Kerov
[17], and a partial result of Logan and Shepp [10]. Moreover, there is a
complete characterization of the fluctuations for large $n$, according to the
Baik-Deift-Johannson theorem [3]. And new results are being continually
discovered for the fluctuations, such as the more recent “directed landscape”
picture [5].

Suppose that instead one asks for the distribution of $Z(n,k)$. The event that
$Z(n,k)>0$ is equal to the event that $L\geq k$. Thus, finding the
distribution of $Z(n,k)$ generalizes Ulam’s problem, so it can be called the
“generalized Ulam problem.” The easy bounds above for the event $Z(n,k)>0$
follows from Markov’s bounds. But more precise bounds could in principle be
obtained if we knew higher moments of $Z(n,k)$. In principle, the Bonferroni
inequalities would give sharp bounds if one had sufficient information on the
moments. A good reference for this combinatorial topic is the combinatorics
textbook of Charalambides [4]. In Appendix A we will review this. (We have an
earlier unpublished article reviewing this topic at more length, which we will
summarize.) Because of all this, it is interesting to know the distribution of
$Z_{n,k}$, beyond just its mean.

In [13], Pinsky investigated the second moment. He obtained an exact
combinatorial formula, albeit a difficult one. He then rigorously analyzed the
formula obtaining upper and lower bounds of matching growth rates (at the most
important, leading term, the exponential term) although with different
constant multipliers. Using this, he could determine exactly the criteria for
the Paley-Zygmund second moment method to guarantee that $Z_{n,k}$ satisfies a
weak law of large numbers type result. Note that just because the Paley-
Zygmund method does not imply a weak law, that does not mean that a weak law
may not still be true (since it does not necessarily require vanishing of the
variance of the rescaled quantity). So in [14], Pinsky proved a threshold to
be able to disprove a weak law for $Z_{n,k}$. He also has stated interesting
equivalent formulations of his questions, and he has interesting conjectures
which remain as open problems. The pair of papers is fascinating.

In theoretical physics and in the mathematical physics of spin glasses, even
though the second moment of $Z_{n,k}$ may be too large to prove a weak law,
one is still interested in the precise form of the second moment, and indeed
of all higher moments. In principle, spin glass physicists have methods which
sometimes allow one to go from formulas for the moments, asymptotically, to
information about the actual distribution. This is in cases where the usual
mathematical tools do not apply, such as where the moment problem is
indeterminate or in certain types of limits in asymptotics where finite $n$
methods may not apply. An excellent reference for the limitations of classical
mathematical tools when trying to apply them to spin glass techniques was
written by van Hemmen and Palmer [18]. However, the spin glass techniques have
proved effective in illuminating the Sherrington-Kirkpatrick mean field spin
glass problem, and may be useful beyond that. See for example, the classical
physics textbook [11]. The first rigorous proof of Parisi’s ansatz for the SK
model, given by Talagrand, seemed to proceed by very different techniques
[16], with a starting point the beautiful approach of Guerra [7] and Guerra
and Toninelli [8].

So we are interested in the more general moments of $Z_{n,k}$, starting with
the second moment. We call this the generalize Ulam problem. Technically, the
generalized Ulam problem should be the problem of stating as much as possible
about the distribution of $Z_{n,k}$ for the doubly-indexed sequence of numbers
for $n$ and $k$. But we are most hopeful to be able to calculate the positive
integer moments, in some asymptotic sense. So far as we know, this has not
been done, except by Pinsky. We begin, in the next section, by stating
Pinsky’s precise combinatorial formula for the second moment. Then we
calculate a generating function for the quantities that appear in Pinsky’s
decomposition, with hopes of returning later and extracting the precise
asymptotics from the generating function. For us, the calculation of the
generating function was already difficult.

##  2 Pinsky’s combinatorial second moment formula

In his paper [13], Pinsky calculated

$\mathbf{E}\left[Z_{n,k}^{2}\right]\,=\,\sum_{j=0}^{k}\binom{n}{2k-j}\frac{1}{(2k-j)!}\,A(k-j,j)\,,$
(13)

where

$A(N,j)\,=\,\sum_{\begin{subarray}{c}\ell_{0},\dots,\ell_{j}\in\\{0,1,\dots\\}\\\
\ell_{0}+\dots+\ell_{j}=N\end{subarray}}\
\sum_{\begin{subarray}{c}m_{0},\dots,m_{j}\in\\{0,1,\dots\\}\\\
m_{0}+\dots+m_{j}=N\end{subarray}}\
\prod_{r=0}^{j}\left(\binom{\ell_{r}+m_{r}}{\ell_{r},m_{r}}\right)^{2}\,.$
(14)

See Pinsky’s Proposition 2. We will not reproduce his proof, but we mention
that his argument is elegant.

Defining the new quantity

$B(L,M,j)\,=\,\sum_{\begin{subarray}{c}\ell_{0},\dots,\ell_{j}\in\\{0,1,\dots\\}\\\
\ell_{0}+\dots+\ell_{j}=L\end{subarray}}\
\sum_{\begin{subarray}{c}m_{0},\dots,m_{j}\in\\{0,1,\dots\\}\\\
m_{0}+\dots+m_{j}=M\end{subarray}}\
\prod_{r=0}^{j}\left(\binom{\ell_{r}+m_{r}}{\ell_{r},m_{r}}\right)^{2}\,,$
(15)

we have $A(N,j)=B(N,N,j)$. Defining the generating function

$\beta(w,x,y)\,=\,\sum_{j=0}^{\infty}\sum_{L=0}^{\infty}\sum_{M=0}^{\infty}w^{j}x^{L}y^{M}B(L,M,j)\,,$
(16)

for $x,y,w\in\mathbb{C}$, we have

$\beta(w,x,y)\,=\,\sum_{j=0}^{\infty}w^{j}\left(\sum_{\ell=0}^{\infty}\
\sum_{m=0}^{\infty}x^{\ell}y^{m}\left(\binom{\ell+m}{\ell,m}\right)^{2}\right)^{j+1}\,,$
(17)

by the Tonelli theorem when $x,y,w$ are in $[0,\infty)$ since all the
coefficients are nonnegative. (See for example, Section 2.5 of Folland [6].)
So the left-hand-side diverges if and only if the right-hand-side diverges. If
neither diverges, the equality is true. Also, if neither diverges for a choice
of $x=x_{1}$, $y=y_{1}$, $w=w_{1}$ for $x_{1},y_{1},w_{1}\in[0,\infty)$, then
for any complex numbers $x,y,w\in\mathbb{C}$ such that $|x|\leq x_{1}$,
$|y|\leq y_{1}$ and $|z|\leq z_{1}$, the two sides of (17) are convergent and
there is equality of the two sides by Fubini’s theorem.

$z=re^{i\theta}$$r>0$
and$-\pi<\theta<\pi$$\sqrt{z}=\sqrt{r}\,e^{i\theta/2}$$=\exp((1/2)\log(z))$
Figure 1: Schematic for the standard square-root function on the open domain
of $\mathbb{C}$ with branch cut along the non-positive real axis:
$\mathcal{D}_{1}=\\{re^{i\theta}\,:\,r>0\,,\ -\pi<\theta<\pi\\}$. For
$z\in\mathcal{D}_{1}$ we use the formula
$\sqrt{z}=\exp((1/2)\int_{0}^{1}(z-1)(1+t(z-1))^{-1}\,dt)$.

Given $|x|,|y|\in[0,1/4)$, let us define

$\gamma^{(2)}(x,y)\,=\,\sum_{\ell=0}^{\infty}\sum_{m=0}^{\infty}x^{\ell}y^{m}\left(\binom{\ell+m}{\ell,m}\right)^{2}\,,$
(18)

so that, according to (17),

$\beta(w,x,y)\,=\,\sum_{j=0}^{\infty}w^{j}\left(\gamma^{(2)}(x,y)\right)^{j+1}\,.$
(19)

The reason we have denoted the function in (18) as $\gamma^{(2)}$, is that it
bears a relation to a more famous generating function, which we call $\gamma$:

$\forall x,y\in\left[0\,,\ \frac{1}{2}\right)\,,\ \text{ we define }\
\gamma(x,y)\,=\,\sum_{\ell,m=0}^{\infty}\binom{\ell+m}{\ell,m}x^{\ell}y^{m}\,,$
(20)

using the multinomial notation for the binomial coefficient
$\binom{\ell+m}{\ell,m}=\frac{(\ell+m)!}{\ell!\,m!}$, we have

$\gamma(x,y)\,=\,\sum_{n=0}^{\infty}(x+y)^{n}\,=\,\frac{1}{1-(x+y)}\,.$ (21)

This is a first example in many textbooks: see for example Pemantle and
Wilson, Example 2.2.2 [12].

The relation between $\gamma$ and $\gamma^{(2)}$ is as follows. Taking the
product of $\gamma(x,y)$ and $\gamma(u,v)$ and then multiplying $x$ by $\xi$
and $u$ by $\xi^{-1}$, and multiplying $y$ by $\zeta$ and $v$ by $\zeta^{-1}$,
we have

$\gamma(x\xi,y\zeta)\gamma\left(\frac{u}{\xi}\,,\
\frac{v}{\zeta}\right)\,=\,\sum_{\ell,m,k,n=0}^{\infty}\binom{\ell+m}{\ell,m}\binom{k+n}{k,n}x^{\ell}y^{m}u^{k}v^{n}\xi^{\ell-k}\zeta^{m-n}\,.$
(22)

Therefore, integrating over unit circles, and using the residue method:

$\gamma^{(2)}(xu,yv)\,=\,\oint_{\mathcal{C}(0;1)}\oint_{\mathcal{C}(0;1)}\gamma(x\xi,y\zeta)\gamma\left(\frac{u}{\xi}\,,\
\frac{v}{\zeta}\right)\,\frac{d\xi}{2\pi i\xi}\,\cdot\frac{d\zeta}{2\pi
i\zeta}\,.$ (23)

One can perform the integral to calculate the following.

###### Lemma 2.1

Given $|x|,|y|\in[0,1/4)$, defining

$\gamma^{(2)}(x,y)\,=\,\sum_{\ell,m=0}^{\infty}x^{\ell}y^{m}\left(\binom{\ell+m}{\ell,m}\right)^{2}\,,$
(24)

the series converges and

$\gamma^{(2)}(x,y)\,=\,\left(\sqrt{\left(1-\left(x+y\right)\right)^{2}-4xy}\right)^{-1}\,.$
(25)

###### Remark 2.2

In our paper, we use the standard branch cut for the natural logarithm along
the non-positive real axis. So the domain is
$\mathcal{D}_{1}=\\{re^{i\theta}\,:\,r>0\,,\ -\pi<\theta<\pi\\}$ and for each
$z\in\mathcal{D}_{1}$, the formula is
$\log(z)=\int_{0}^{1}(z-1)(1+(z-1)t)^{-1}\,dt$. Then, for each
$z\in\mathcal{D}_{1}$, we use $\sqrt{z}=\exp((1/2)\log(z))$. See Figure 1 for
the schematic. In the decomposition of $x=re^{i\theta}$, we refer to the term
$e^{i\theta}$ as the “phase.” Some complex analysis textbooks call this the
argument as in Section 3.4 of [1]. But we reserve the term “argument” for the
input of other functions. For example, given a term of the form $\sqrt{f(x)}$
we will refer to $f(x)$ as the “argument of the square-root function.”

The result of the calculation in the lemma is an instance related to the fact
that the diagonal of a rational bivariate generating function is an algebraic
univariate generating function. This is proved in Section 2.4 of Pemantle and
Wilson, credited to Furstenberg and to Hautus and Klarner.

The residue method may be used to derive formulas such as this, when they are
unknown. This is opposed to proof methods for conjectural formulas, which are
sometimes more automatic, such as induction. For this example, we do the
contour integral as an exercise in Appendix B. But once the formula is
“known,” whether or not it is proved, there are often simpler combinatorial
methods that bypass contour integrals. Here we present such an alternative
proof.

Proof of Lemma 2.1: Let the right-hand-side of equation (25) be denoted by
$g^{(2)}(x,y)$. Then we may rewrite

$g^{(2)}(x,y)\,=\,\frac{1}{1-(x+y)}\,\left(1-\frac{4xy}{\left(1-(x+y)\right)^{2}}\right)^{-1/2}\,.$
(26)

Therefore, by Newton’s version of the binomial theorem, this gives

$\displaystyle g^{(2)}(x,y)\,$
$\displaystyle=\,\frac{1}{1-(x+y)}\,\sum_{n=0}^{\infty}\frac{(-1/2)_{n}}{n!}\frac{(-1)^{n}4^{n}x^{n}y^{n}}{\left(1-(x+y)\right)^{2n}}$
(27)
$\displaystyle=\,\sum_{n,k=0}^{\infty}\frac{(-1/2)_{n}}{n!}\cdot\frac{(-2n-1)_{k}}{k!}(-1)^{n+k}4^{n}x^{n}y^{n}(x+y)^{k}\,,$
(28)

where the Pochhammer symbol, falling factorial, is

$(z)_{n}\,=\,z(z-1)(z-2)\cdots(z-n+1)\,=\,\prod_{k=0}^{n-1}(z-k)\,.$ (29)

Then, by the regular binomial formula, we have

$g^{(2)}(x,y)\,=\,\sum_{n,k=0}^{\infty}\sum_{j=0}^{k}\frac{(-1/2)_{n}}{n!}\cdot\frac{(-2n-1)_{k}}{k!}\binom{k}{j}(-1)^{n+k}4^{n}x^{n+j}y^{n+k-j}\,.$
(30)

Therefore, the lemma will be proved if we check that

$\sum_{n=0}^{\infty}\frac{(-1/2)_{n}}{n!}\cdot\frac{(-2n-1)_{k}}{k!}\binom{k}{j}(-1)^{n+k}4^{n}\Bigg{|}_{\begin{subarray}{c}j=\ell-n\\\
k-j=m-n\end{subarray}}\,=\,\left(\binom{\ell+m}{\ell,m}\right)^{2}\,,$ (31)

for each $\ell,m\in\\{0,1,\dots\\}$. But using well-known combinatorial
formulas for the Pochhammer symbols of $-1/2$ and of negative integers, which
we review in Appendix C, this is equivalent to checking the multinomial
identity:

$\sum_{n=0}^{\infty}\binom{\ell+m}{n,n,\ell-n,m-n}\,=\,\left(\binom{\ell+m}{\ell,m}\right)^{2}\,.$
(32)

(We use the standard convention that if one of the indices in the subscript of
a binomial or multinomial coefficient is outside the range of $0$ to the
superscript index, then that coefficient equals 0 by definition.) Equation
(32) may be proved as follows.

Draw $\ell+m$ black dots on the number line from $1$ to $\ell+m$. Above each
dot place a circle with either the top or bottom shaded in, such that if
$\mathcal{A}$ is the subset of those $r\in\\{1,\dots,\ell+m\\}$ whose circle
above it has the top half shaded, then $|\mathcal{A}|=\ell$ and
$|\mathcal{A}^{\complement}|=m$. Below each black dot, place a circle with
either the left or right shaded in, such that if $\mathcal{B}$ is the set of
those $r\in\\{1,\dots,\ell+m\\}$ whose circle below it has the left half
shaded, then $|\mathcal{B}|=m$ and $|\mathcal{B}^{\complement}|=\ell$.

Then, if we let $n=|\mathcal{A}\cap\mathcal{B}|$ we have
$|\mathcal{A}\cap\mathcal{B}^{\complement}|=\ell-n$ and
$|\mathcal{A}^{\complement}\cap\mathcal{B}|=m-n$, as well. Therefore,
$|\mathcal{A}^{\complement}\cap\mathcal{B}^{\complement}|$ is equal to
$\ell+m-|\mathcal{A}\cap\mathcal{B}|-|\mathcal{A}\cap\mathcal{B}^{\complement}|-|\mathcal{A}^{\complement}\cap\mathcal{B}|$,
which is $n$. The number of ways of choosing one quadrant to shade in –
(top,left), (top,right), (bottom,left), (bottom,right) – with a prescribed
number of each $n$, $\ell-n$, $m-n$, $n$ is the multinomial coefficient
$\binom{\ell+m}{n,\ell-n,m-n,n}$. Summing over all choices of $n$ gives all
possibilities for choosing the two sets $\mathcal{A}$ and $\mathcal{B}$. Since
they are chosen independently, that is
$\left(\binom{\ell+m}{\ell,m}\right)^{2}$. This proves equation (32).
$\square$

Because of Lemma 2.1 and equation (17), we have

$\beta(w,x,y)\,=\,\frac{\gamma^{(2)}(x,y)}{1-w\gamma^{(2)}(x,y)}\,=\,\frac{1}{\left(\left(1-\left(x+y\right)\right)^{2}-4xy\right)^{1/2}-w}\,.$
(33)

Now define another generating function

$\alpha(w,z)\,=\,\sum_{j,N=0}^{\infty}w^{j}z^{N}A(N,j)\,=\,\sum_{j,N=0}^{\infty}w^{j}z^{N}B(N,N,j)\,,$
(34)

which is the generating function for the combinatorial numbers we want,
$A(N,j)$ for $N,j\in\\{0,1,\dots\\}$. Then, by applying the diagonal method,
we obtain

$\oint_{\mathcal{C}(0;1)}\beta\left(w\,,\ x\xi\,,\
\frac{y}{\xi}\right)\,\frac{d\xi}{2\pi i\xi}\,=\,\alpha(w,xy)\,,$ (35)

for sufficiently small $x$, $y$ and $w$.

Because of equation (44) we will assign variable names to some of the terms
such as $\sqrt{k-2}$ or $\sqrt{k+2}$ or related algebraic functions that
arise. The extra variable names have helped us to organize our calculations,
and we hope they are not too much of a distraction for an interested reader.

###### Theorem 2.3

Suppose we have numbers $t,u\in\mathbb{R}$, such that $0\leq t<1/4$ and $0\leq
u<1$. Then

$\begin{split}\alpha\left(2t\,\sqrt{1-u^{2}}\,,\
t^{2}u^{2}\right)\,&=\,\frac{1}{\pi}\int_{c_{1}}^{c_{2}}\frac{\sqrt{-\mathcal{Q}_{1}(r)}}{-\mathcal{Q}_{2}(r)}\,dr\\\\[5.0pt]
&+\frac{2t\sqrt{1-u^{2}}\,\left(\sqrt{1-(2t+2tu)^{2}}+\sqrt{1-(2t-2tu)^{2}}\right)\left(\sqrt{(1+2tu)^{2}-4t^{2}}+\sqrt{(1-2tu)^{2}-4t^{2}}\right)}{\left(1-(1+u^{2})t^{2}+\sqrt{1-8(1+u^{2})t^{2}+16(1-u^{2})^{2}t^{4}}\right)\sqrt{1-8(1+u^{2})t^{2}+16(1-u^{2})^{2}t^{4}}}\,.\end{split}$
(36)

where

$\displaystyle\mathcal{Q}_{1}(r)\,$
$\displaystyle=\,\big{(}(r^{2}+1)tu-(1-2tu)r\big{)}\big{(}(r^{2}+1)tu-(1+2tu)r\big{)}\,,$
(37) $\displaystyle\mathcal{Q}_{2}(r)\,$
$\displaystyle=\,\big{(}(r^{2}+1)tu-(1-2t)r\big{)}\big{(}(r^{2}+1)tu-(1+2t)r\big{)}\,,$
(38)

are two quartic polynomals, and where

$c_{1}\,=\,\frac{1+2tu-\sqrt{1+4tu}}{2tu}\ \text{ and }\
c_{2}\,=\,\frac{1-2tu-\sqrt{1-4tu}}{2tu}$ (39)

are the two roots of $\mathcal{Q}_{1}$ in $(0,1)$. Both $\mathcal{Q}_{1}(r)$
and $\mathcal{Q}_{2}(r)$ are negative on $(c_{1},c_{2})$.

$c_{1}$$c_{2}$$a_{1}$$a_{2}$$d_{1}$$d_{2}$$b_{1}$$b_{2}$$\boldsymbol{>}$
Figure 2: A schematic picture – it is not to scale but it does accurately
depict the order of points – for the branch cuts and poles of the integral in
(52). The configuration of points and branch cuts is shown assuming
$u,t\in(0,1)$ are sufficiently small. The poles are at $a_{1}$, $a_{2}$,
$b_{1}$ and $b_{2}$. The branch cuts are the intervals $[c_{1},c_{2}]$ and
$[d_{1},d_{2}]$. In other words, $c_{1},c_{2},d_{1},d_{2}$ are roots of
$\mathcal{Q}_{1}$ and $a_{1},a_{2},b_{1},b_{2}$ are roots of $\mathcal{Q}_{2}$
for the quartic polynomials $\mathcal{Q}_{1}$ and $\mathcal{Q}_{2}$ from
Theorem 2.3.

We will prove the theorem in the next section. For now let us note that this
is a potentially useful representation for the sequence $A(N,j)$. We note that
for $x>0$ and $w>0$ we can find $t$ and $u$ to match them. If we did have
$x=t^{2}u^{2}$ and $w=2t\sqrt{1-u^{2}}$, then we would have

$w^{2}+4x\,=\,\left(2t\,\sqrt{1-u^{2}}\right)^{2}+4t^{2}u^{2}\,=\,4t^{2}\,.$
(40)

Therefore, we may take

$t\,=\,\frac{1}{2}\sqrt{w^{2}+4x}\,.$ (41)

So $|t|<1$ as long as $4x+w^{2}<\frac{1}{4}$. We can then take
$u=t^{-1}\sqrt{x}=\sqrt{4x}/\sqrt{w^{2}+4x}$. (If $x$ and $w$ are both $0$
then $t=0$ and the value of $u$ is irrelevant.) So $u$ is in $[0,1]$ as long
as $x,w$ are both nonnegative.

In principle, calculating the generating function for all $x$ and $w$ in say
$[0,1/32]$ does determine all the coefficients. Note that all the coefficients
are nonnegative, since they are combinatorial (either 0 or positive integers).
So if the series is convergent for $0\leq x<1/32$ and $0\leq w<1/32$ then the
complex series is absolutely convergent for $|x|<1/32$ and $|w|<1/32$. This is
the same, usual fact that lies behind the Fubini-Tonelli theorem (see for
example [6]). Perhaps more importantly, if we want to obtain asymptotics for
$A(N,j)$, then one often uses techniques related to positivity such as
Chebyshev’s inequality. Certainly Chebyshev’s inequality gives one-sided
bounds. Those could potentially be turned into asymptotics if the correct
Tauberian-type theorem is found and used.

The integral appearing in equation (36) is an example of an elliptic integral,
although we do not know anything beyond that about a more precise
characterization of this integral.

###  2.1 Roots of a class of quadratic equations

Let us digress briefly to consider the type of equation which appears in the
square-root in the denominator in the expression of $\beta$ from (33). For a
quadratic equation of the form

$\xi^{2}+1-k\xi\,=\,0\,,$ (42)

the quadratic formula for the roots gives

$\xi_{\pm}\,=\,\frac{k\pm\sqrt{k^{2}-4}}{2}\,,$ (43)

which in turn can be written as

$\xi_{\pm}\,=\,\frac{1}{4}\left(\sqrt{k-2}\pm\sqrt{k+2}\right)^{2}\,,$ (44)

if we know that $k-2$ and $k+2$ are in the domain $\mathcal{D}_{1}$ for the
square-root function from Remark 2.2. The reason this type of quantity appears
for us is that we are considering $\beta(w,x\xi,y/\xi)$, and we may also
simplify by taking $y=x$. This is because in (35) we get a formula for
$\alpha(w,xy)$ which we may specialize to a formula for $\alpha(w,x^{2})$,
taking $y=x$, with no loss of utility. Then we see that

$\begin{split}\beta(w,x\xi,y/\xi)\,&=\,\frac{1}{\left(\big{(}1-x(\xi+\xi^{-1})\big{)}^{2}-4x^{2}\right)^{1/2}-w}\\\
&=\,\frac{1}{\left((x^{2}/\xi^{2})\,\left((\xi^{2}+1)-\left(x^{-1}+2\right)\xi\right)\left((\xi^{2}+1)-\left(x^{-1}-2\right)\xi\right)\right)^{1/2}-w}\,,\end{split}$
(45)

containing several terms of the form of the left-hand-side of (42) for
different choices of $k$. For the purpose of doing contour deformation, we
will need to factorize these terms.

In fact, they arise twice, in two rounds, because we rationalize the
denominator in order to more easily calculate the residues and the
contribution due to the branch-cut in (35). That means we must consider the
argument of the square-root function in order to handle the branch-cut
contribution. But we must also consider the poles of the denominator, after we
have rationalized it, which is a slightly different quartic.

##  3 Proof of Theorem 2.3: generating function formula

If we take $x,y,z\in\mathbb{C}$ such that

$2|x|+2|y|+|w|^{2}\,<\,1\,,$ (46)

then we have

$\alpha(w,xy)\,=\,\frac{1}{2\pi
i}\oint_{\mathcal{C}(0;1)}\frac{1}{\xi\,\cdot\left(\left(1-(x\xi+y\xi^{-1})\right)^{2}-4xy\right)^{1/2}-w\xi}\,d\xi\,,$
(47)

where we have used equation (33). The argument of the square-root function in
the denominator is contained in the open disk $\mathbb{C}$ centered at $1$
with radius $1$, since $2|x|+2|y|<1$. So the square-root is unambiguously
defined in the sense of Remark 2.2. Then the entire denominator may be written
as $\xi$ times a quantity which is within the open disk $\mathbb{C}$ centered
at $1$ with radius $1$, since $2|x|+2|y|+|w|^{2}<1$ by equation (46).

Next we rationalize the denominator, in order to simplify the calculation of
the residues. So equation (47) can be rewritten as

$\alpha(w,xy)\,=\,\frac{1}{2\pi
i}\oint_{\mathcal{C}(0;1)}\frac{\xi\,\cdot\left(\left(1-(x\xi+y\xi^{-1})\right)^{2}-4xy\right)^{1/2}+w\xi}{\left(\left(\xi-(x\xi^{2}+y)\right)^{2}-4xy\xi^{2}\right)-w^{2}\xi^{2}}\,d\xi\,.$
(48)

Now, we will specialize to simplify the calculations going forward. Firstly,
let us take $y=x$.

$\alpha(w,x^{2})\,=\,\frac{1}{2\pi
i}\oint_{\mathcal{C}(0;1)}\frac{\xi\,\cdot\left(\left(1-x(\xi+\xi^{-1})\right)^{2}-4x^{2}\right)^{1/2}+w\xi}{\left(\left(\xi-x(\xi^{2}+1)\right)^{2}-4x^{2}\xi^{2}\right)-w^{2}\xi^{2}}\,d\xi\,,$
(49)

Next, let us assume that $x$ and $w$ are real variables for the remainder of
the proof.

In fact, we change variables. Let us assume that we have real numbers
$t,u\in\mathbb{R}$ which are sufficiently small, which effectively amounts to
$-1/4<t<1/4$ and $-1<u<1$, and let us take $w=2t\,\sqrt{1-u^{2}}$ and $x=tu$.
Then we have

$\alpha\left(2t\,\sqrt{1-u^{2}}\,,\ t^{2}u^{2}\right)\,=\,\frac{1}{2\pi
i}\oint_{\mathcal{C}(0;1)}\frac{\xi\cdot\left(\left(1-(\xi+\xi^{-1})tu\right)^{2}-4t^{2}u^{2}\right)^{1/2}+2t\xi\,\sqrt{1-u^{2}}}{\left(\left(\xi-(\xi^{2}+1)tu\right)^{2}-4t^{2}u^{2}\xi^{2}\right)-4(t^{2}-t^{2}u^{2})\xi^{2}}\,d\xi\,.$
(50)

Collecting terms in the denominator, this may be simplified to give

$\alpha\left(2t\,\sqrt{1-u^{2}}\,,\ t^{2}u^{2}\right)\,=\,\frac{1}{2\pi
i}\oint_{\mathcal{C}(0;1)}\frac{\xi\cdot\left(\left(1-(\xi+\xi^{-1})tu\right)^{2}-4t^{2}u^{2}\right)^{1/2}+2t\xi\,\sqrt{1-u^{2}}}{\left(\xi-(\xi^{2}+1)tu\right)^{2}-4t^{2}\xi^{2}}\,d\xi\,.$
(51)

Now we factorize the denominator to obtain

$\alpha\left(2t\,\sqrt{1-u^{2}}\,,\ t^{2}u^{2}\right)\,=\,\frac{1}{2\pi
i}\oint_{\mathcal{C}(0;1)}\frac{\xi\cdot\left(\left(1-(\xi+\xi^{-1})tu\right)^{2}-4t^{2}u^{2}\right)^{1/2}+2t\xi\,\sqrt{1-u^{2}}}{\left((1-2t)\xi-(\xi^{2}+1)tu\right)\left((1+2t)\xi-(\xi^{2}+1)tu\right)}\,d\xi\,.$
(52)

The two factors of the denominator are quadratic polynomials, and they may
each be further factorized as (multiplying each one by $-1$ first)

$\displaystyle\left((\xi^{2}+1)tu-(1-2t)\xi\right)\,$
$\displaystyle=\,tu\cdot(\xi-a_{2})(\xi-b_{1})\,,$ (53)
$\displaystyle\left((\xi^{2}+1)tu-(1+2t)\xi\right)\,$
$\displaystyle=\,tu\cdot(\xi-a_{1})(\xi-b_{2})\,,$ (54)

by direct appeal to the quadratic formula, where

$\displaystyle a_{1}\,=\,\frac{1+2t-\sqrt{(1+2t-2tu)(1+2t+2tu)}}{2tu}\,,$ (55)
$\displaystyle a_{2}\,=\,\frac{1-2t-\sqrt{(1-2t-2tu)(1-2t+2tu)}}{2tu}\,,$ (56)
$\displaystyle b_{1}\,=\,\frac{1-2t+\sqrt{(1-2t-2tu)(1-2t+2tu)}}{2tu}\,,$ (57)
$\displaystyle b_{2}\,=\,\frac{1+2t+\sqrt{(1+2t-2tu)(1+2t+2tu)}}{2tu}\,.$ (58)

A power series expansion in the small parameter gives

$\displaystyle a_{1}\,$ $\displaystyle=\,tu-2t^{2}u+O(t^{3})\,,\qquad$
$\displaystyle\qquad a_{2}\,$ $\displaystyle=\,tu+2t^{2}u+O(t^{3})\,,$ (59)
$\displaystyle b_{1}\,$
$\displaystyle=\,\frac{1}{tu}-\frac{2}{u}+O(t)\,,\qquad$ $\displaystyle\qquad
b_{2}\,$ $\displaystyle=\,\frac{1}{tu}+\frac{2}{u}+O(t)\,.$ (60)

This means that $0<a_{1}<a_{2}<1<b_{1}<b_{2}$, when $t\in(0,1)$ is
sufficiently small. For future reference, we note that

$\begin{split}\mathcal{Q}_{2}(\xi)\,&=\,\big{(}(1-2t)\xi-(\xi^{2}+1)tu\big{)}\cdot\big{(}(1+2t)\xi-(\xi^{2}+1)tu\big{)}\\\\[3.0pt]
&=\,t^{2}u^{2}\cdot(\xi-a_{1})(\xi-a_{2})(\xi-b_{1})(\xi-b_{2})\,.\end{split}$
(61)

Now let us introduce some extra notation that helps to organize the
calculations to come. Let us define, for each
$\sigma_{1},\sigma_{2}\in\\{1,-1\\}$ the quantity

$\rho(\sigma_{1},\sigma_{2})\,=\,\sqrt{1+2\sigma_{1}t+2\sigma_{2}tu}\,.$ (62)

Since we assumed that $-1/4<t<1/4$ and $-1<u<1$ we know that the argument of
the square-root function is in the open disk in $\mathbb{C}$, centered at $1$
with radius $1$. So the standard square-root function may be applied (as in
Remark 2.2). Let us abbreviate the notation to

$\rho^{(+)}_{+}\,=\,\rho(1,1)\,,\qquad\rho^{(+)}_{-}\,=\,\rho(1,-1)\,,\qquad\rho^{(-)}_{+}\,=\,\rho(-1,1)\,,\qquad\rho^{(-)}_{-}\,=\,\rho(-1,-1)\,.$
(63)

Then we may write

$\displaystyle a_{1}\,$
$\displaystyle=\,\frac{1}{4tu}\,\left(\rho^{(+)}_{+}-\rho^{(+)}_{-}\right)^{2}\,,\qquad$
$\displaystyle\qquad a_{2}\,$
$\displaystyle=\,\frac{1}{4tu}\,\left(\rho^{(-)}_{+}-\rho^{(-)}_{-}\right)^{2}\,,$
(64) $\displaystyle b_{1}\,$
$\displaystyle=\,\frac{1}{4tu}\,\left(\rho^{(-)}_{+}+\rho^{(-)}_{-}\right)^{2}\,,\qquad$
$\displaystyle\qquad b_{2}\,$
$\displaystyle=\,\frac{1}{4tu}\,\left(\rho^{(+)}_{+}+\rho^{(+)}_{-}\right)^{2}\,.$
(65)

This is a rewriting of the roots of these particular quadratic equations
similar to what we described in equation (44). We will return to further
calculations involving these quantities, briefly.

First, let us perform a similar algebraic simplification for the polynomial in
the argument of the numerator in equation (52). This may be factorized as

$\left(1-(\xi+\xi^{-1})tu\right)^{2}-4t^{2}u^{2}\,=\,\left(1-2tu-(\xi+\xi^{-1})tu\right)\left(1+2tu-(\xi+\xi^{-1})tu\right)\,.$
(66)

Applying the quadratic formula, we have

$\displaystyle\left(1-2tu-(\xi+\xi^{-1})tu\right)\,$
$\displaystyle=\,tu\xi^{-1}\cdot(\xi-c_{2})(\xi-d_{1})\,,$ (67)
$\displaystyle\left(1+2tu-(\xi+\xi^{-1})tu\right)\,$
$\displaystyle=\,tu\xi^{-1}\cdot(\xi-c_{1})(\xi-d_{2})\,,$ (68)

where

$\displaystyle c_{1}\,$
$\displaystyle=\,\frac{1+2tu-\sqrt{1+4tu}}{2tu}\,,\qquad$ $\displaystyle\qquad
c_{2}\,$ $\displaystyle=\,\frac{1-2tu-\sqrt{1-4tu}}{2tu}\,,$ (69)
$\displaystyle d_{1}\,$
$\displaystyle=\,\frac{1-2tu+\sqrt{1-4tu}}{2tu}\,,\qquad$ $\displaystyle\qquad
d_{2}\,$ $\displaystyle=\,\frac{1+2tu+\sqrt{1+4tu}}{2tu}\,.$ (70)

A power series expansion in the small parameter gives

$\displaystyle c_{1}\,$ $\displaystyle=\,tu-2t^{2}u^{2}+O(t^{3})\,,\qquad$
$\displaystyle\qquad c_{2}\,$ $\displaystyle=\,tu+2t^{2}u^{2}+O(t^{3})\,,$
(71) $\displaystyle d_{1}\,$ $\displaystyle=\,\frac{1}{tu}-2+O(t)\,,\qquad$
$\displaystyle\qquad d_{2}\,$ $\displaystyle=\,\frac{1}{tu}+2+O(t)\,.$ (72)

This means that $0<a_{1}<c_{1}<c_{2}<a_{2}<1<b_{1}<d_{1}<d_{2}<b_{2}$, when
$t\in(0,1)$ and $u\in(0,1)$ are sufficiently small. In other words, the
ordering of the poles and branch cut endpoints are as depicted in Figure 2.
For future reference, we note that

$\begin{split}\mathcal{Q}_{1}(\xi)\,&=\,\big{(}(1-2tu)\xi-(\xi^{2}+1)tu\big{)}\cdot\big{(}(1+2tu)\xi-(\xi^{2}+1)tu\big{)}\\\\[3.0pt]
&=\,t^{2}u^{2}\cdot(\xi-c_{1})(\xi-c_{2})(\xi-d_{1})(\xi-d_{2})\,,\end{split}$
(73)

although now we will be more concerned with the interpretation of
$\sqrt{\mathcal{Q}_{1}(\xi)}$ or $\xi\sqrt{\mathcal{Q}_{1}(\xi)/\xi^{2}}$ as
analytic functions in prescribed domains.

$c_{1}$$\boldsymbol{>}$$c_{2}$$\boldsymbol{<}$$a_{1}$$\Gamma_{1}(\delta)$$\boldsymbol{>}$$a_{2}$$\Gamma_{2}(\delta)$$\boldsymbol{>}$$\Gamma_{3}(\delta)$
Figure 3: A schematic of the contours after deformation. The two positively
oriented circular contours – of radius $\delta$ for $0<\delta\ll 1$ – are
centered at the poles $a_{1}$ and $a_{2}$. They are $\Gamma_{1}(\delta)$ and
$\Gamma_{2}(\delta)$. The branch cut along the real axis interval from $c_{1}$
to $c_{2}$ is enclosed by the contour $\Gamma_{3}(\delta)$ which is the
rectangle joining $c_{1}-i\delta$, $c_{2}-i\delta$, $c_{2}+i\delta$ and
$c_{1}+i\delta$, traversed in the counter-clockwise orientation.

Now we deform the unit circle contour $\mathcal{C}(0;1)$ into the unit disk,
but avoiding cutting through the poles $a_{1}$, $a_{2}$ or the branch cut
interval $[c_{1},c_{2}]$ inside the unit disk. See Figure 3.

Just before doing that, let us make a precise declaration of how we consider
$\sqrt{\mathcal{Q}_{1}(\xi)}$ in the domain that we deform the contours
through.

###  3.1 Analytic extension of $\sqrt{\mathcal{Q}_{1}(\xi)}$ outside
$[c_{1},c_{2}]$ and $[d_{1},d_{2}]$

Let us define that domain

$\mathcal{D}_{2}\,=\,\mathbb{C}\setminus\big{(}[c_{1},c_{2}]\cup[d_{1},d_{2}]\big{)}\,.$
(74)

Note that for $\xi\in\mathbb{C}$ with $|\xi|$ close to $1$, the usual power
series expansion of $\sqrt{\mathcal{Q}_{1}(\xi)/\xi^{2}}$, expanding in $t$,
may be written

$\left(\big{(}1-(\xi+\xi^{-1})tu\big{)}^{2}-4t^{2}u^{2}\right)^{1/2}\,=\,\sum_{n=0}^{\infty}\frac{(1/2)_{n}}{n!}\cdot\left(-2\big{(}\xi+\xi^{-1}\big{)}tu+\big{(}\xi-\xi^{-1}\big{)}^{2}t^{2}u^{2}\right)^{n}\,.$
(75)

It is convergent if $(1+2\max(|\xi|,|\xi|^{-1})|tu|)^{2}-1<1$. We may then say
that, as long $|\xi|$ and $|\xi|^{-1}$ are both contained in a compact set, we
have

$\sqrt{\mathcal{Q}_{1}(\xi)/\xi^{2}}\,=\,1+O(|t|)\,,\ \text{ as }\ t\to 0\,.$
(76)

Let $\mathcal{U}(z_{0};\rho)$ denotes the open disk in $\mathbb{C}$ centered
at $z_{0}$, with radius $\rho$, and let $\overline{\mathcal{U}}(z_{0};\rho)$
denote the closure, the closed disk. Then, for each $\epsilon\in(0,1)$, if
$\xi$ is in
$\mathcal{U}(0;1+\epsilon)\setminus\overline{\mathcal{U}}(0;1-\epsilon)$ then
the power series defined by the right-hand-side of equation (75) is what we
mean by $\sqrt{\mathcal{Q}_{1}(\xi)/\xi^{2}}$.

We now describe a second version of the same function on $\mathcal{D}_{2}$.
Initially, consider another domain $\mathcal{D}_{3}$ equal to
$\mathbb{C}\setminus\big{(}(-\infty,c_{2}]\cup[d_{1},\infty)\big{)}$, which is
the domain depicted on the right-hand-side of Figure 5, the complex plane
minus any point in any of the branch cuts for $\sqrt{\xi-c_{1}}$, $\sqrt{\xi-
c_{2}}$, $\sqrt{d_{1}-\xi}$ and $\sqrt{d_{2}-\xi}$. We note that $1$ is in
$\mathcal{D}_{2}$ and with the standard definition of the square-root (from
Remark 2.2) we have

$\sqrt{1-c_{1}}\,,\ \sqrt{1-c_{2}}\,,\ \sqrt{d_{1}-1}\,,\
\sqrt{d_{2}-1}\,>\,0\,.$ (77)

Therefore, for some $\epsilon>0$, and for $\xi\in\mathcal{U}(1,\epsilon)$, we
have

$\xi\sqrt{\mathcal{Q}_{1}(\xi)/\xi^{2}}\,=\,t^{2}u^{2}\,\sqrt{\xi-
c_{1}}\,\sqrt{\xi-c_{2}}\,\sqrt{d_{1}-\xi}\,\sqrt{d_{2}-\xi}\,.$ (78)

Note that both sides have the property that their square equals
$\mathcal{Q}_{1}(\xi)$. A priori the right-hand-side of (78) is defined on all
of $\mathcal{D}_{3}$ including the subset of
$\mathcal{U}(0;1+\epsilon)\setminus\overline{\mathcal{U}}(0;1-\epsilon)$ equal
to all points except a neighborhood of $-1$, say
$\overline{\mathcal{U}}(-1;\epsilon)$. But in fact, we may see that it is
defined on all of
$\mathbb{C}\setminus\big{(}[c_{1},c_{2}]\cup[d_{1},d_{2}]\big{)}$.

Given a number $r\in\mathbb{R}\setminus\\{c_{1},c_{2},d_{1},d_{2}\\}$ we may
define two limits $\zeta_{+}(r)$ and $\zeta_{-}(r)$ as

$\zeta_{\pm}(r)\,=\,\lim_{\epsilon\to 0^{\pm}}\frac{\sqrt{r+i\epsilon-
c_{1}}\sqrt{r+i\epsilon-
c_{d}}\sqrt{d_{1}-(r+i\epsilon)}\sqrt{d_{2}-(r+i\epsilon-)}}{\left|\sqrt{r+i\epsilon-
c_{1}}\sqrt{r+i\epsilon-
c_{d}}\sqrt{d_{1}-(r+i\epsilon)}\sqrt{d_{2}-(r+i\epsilon-)}\right|}\,.$ (79)

This is the phase which is also the source of the discontinuities if we try to
define $\sqrt{\mathcal{Q}_{1}(\xi)}$ everywhere in $\mathbb{C}$ as a single-
valued function. Or in other words, if we analytically continued
$\sqrt{\mathcal{Q}_{1}(\xi)}$ to a holomorphic (single-valued) function on a
Riemann surface projecting down to $\mathbb{C}$, then the phases could be used
to denote the sheets of the Riemann surface. We may easily calculate

$\zeta_{\pm}(r)\,=\,\begin{cases}1&\text{ for $r\in(c_{2},d_{1})$,}\\\ \pm
i&\text{ for $r\in(c_{1},c_{2})$,}\\\ -1&\text{ for
$r\in(-\infty,c_{1})\cup(d_{2},\infty)$,}\\\ \mp i&\text{ for
$r\in(d_{1},d_{2})$.}\end{cases}$ (80)

Let us consider one example case: $r\in(c_{1},c_{2})$ and $\epsilon>0$. We may
refer to Figure 5 to determine the phase of $\sqrt{\mathcal{Q}_{1}(\xi)}$ for
$\xi=r+i\epsilon$. In this example case, we have

$\xi-c_{1}\,=\,\sqrt{(r-c_{1})^{2}+\epsilon^{2}}e^{i\theta_{1}}\ \text{ and }\
\xi-c_{2}\,=\,\sqrt{(c_{2}-r)^{2}+\epsilon^{2}}e^{i\theta_{2}}\,,$ (81)

where $\theta_{1}\in(0,\pi/2)$ and $\theta_{1}\in(\pi/2,\pi)$. But as
$\epsilon$ approaches $0$ from the positive side, we have $\theta_{1}\to 0$
while $\theta_{2}\to\pi$. So we have

$\lim_{\epsilon\to 0^{+}}\frac{\xi-c_{1}}{|\xi-c_{1}|}\,=\,1\ \text{ and
}\lim_{\epsilon\to 0^{+}}\frac{\xi-c_{2}}{|\xi-c_{2}|}\,=\,-1\,.$ (82)

But then taking the square-root, we have $e^{i\theta_{1}/2}$ converges to $1$
while $e^{i\theta_{2}/2}$ converges to $i$. Multiplying these together, we get
$\zeta_{+}(r)=i$. Note that $d_{1}-r>0$ and $d_{2}-r>0$ for $r$ throughout
$[-1,1]$, which is why we did not consider those factors. Of course if we
replace $\epsilon$ by $-\epsilon$ then the angles are reflected:
$\theta_{1}\leftarrow-\theta_{1}$ and $\theta_{2}\leftarrow-\theta_{2}$ using
replacement notation (as in APL). So the phase changes from $\zeta_{+}(r)=i$
to its reciprocal $1/i=-i$.

$c_{1}$$c_{2}$$d_{1}$$d_{2}$$c_{1}$$c_{2}$$d_{2}$$d_{1}$ Figure 4: The branch
cuts for the function $\sqrt{\mathcal{Q}_{1}(\xi)}$ are shown on the left. In
the figure on the right we show the a priori overlapping branch-cuts if we
take $(d_{1}-\xi)^{1/2}(d_{2}-\xi)^{1/2}(\xi-c_{1})^{1/2}(\xi-c_{2})^{1/2}$ as
a proposal to extend the “power series formula” of
$\xi\sqrt{\mathcal{Q}_{1}(\xi)/\xi^{2}}$ when $\xi$ is in the vicinity of the
unit circle $\mathcal{C}(0;1)$, meaning the power series in the variable $t$.
For the picture on the right, wherever two branch cuts overlap (or for more
general problems wherever an even number overlap) the branch cuts may be
removed because each branch cut is a square-root branch cut. So they are
counted modulo 2. If we check the limits from the upper half-plane $\xi=x+iy$,
$y>0$, they match the limits from the lower half-plane at points where 2
branch cuts overlap.

The point is that for $r\in(-\infty,c_{1})$ and $r\in(d_{2},\infty)$, the
limit from the upper half-plane and the limit from the lower half-plane
coincide. They are both $-1$. Therefore, the analytic function,

$z\in\mathbb{C}\setminus\big{(}(-\infty,c_{2}]\cup[d_{1},\infty)\big{)}\mapsto
t^{2}u^{2}\,\sqrt{\xi-c_{1}}\,\sqrt{\xi-
c_{2}}\,\sqrt{d_{1}-\xi}\,\sqrt{d_{2}-\xi}\,,$ (83)

may be extended to
$z\in\mathbb{C}\setminus\big{(}[c_{1},c_{2}]\cup[d_{1},d_{2}]\big{)}$ just by
taking limits from the upper half-plane and lower half-plane since the two
limits agree.

In particular, note that this formula is negative in $[-1,c_{1}]$. Reconsider
$\sqrt{\mathcal{Q}_{1}(\xi)/\xi^{2}}$, defined by the power series in $t$ for
small $t$ and for $|\xi|$ near to $1$. For that quantity, we know
$\sqrt{\mathcal{Q}_{1}(\xi)/\xi^{2}}=1+O(t)$ as $t\to 0$. But then that means
that $\xi\,\sqrt{\mathcal{Q}_{1}(\xi)/\xi^{2}}=\xi+O(t)$ as $t\to 0$. In
particular, near $\xi=-1$ the phase is approximated by $-1$. That matches the
behavior determined by $\sqrt{\mathcal{Q}_{1}(\xi)}$ on $\mathcal{D}_{2}$ in a
neighborhood of $-1$.

$c_{1}$$c_{2}$$\bullet$$<$$<$$\xi=r+i\epsilon$$\theta_{1}$$\theta_{2}$ Figure
5: Consideration of the phase of $\sqrt{\mathcal{Q_{1}}(\xi)}$, in the
vicinity of $[-1,1]$. If we write the output of the square root as
$e^{i\varphi}R$ for $R\geq 0$ and $\varphi\in\mathbb{R}$ then by “phase” we
mean $e^{i\varphi}$. Near the real axis, except in neighborhoods of
$\\{c_{1},c_{2},d_{1},d_{2}\\}$, in the upper half-plane and lower half-plane,
the phase $e^{i\varphi}$ is well approximated by one of the numbers in
$\\{1,i,-1,-i\\}$.

###  3.2 Resumption of the proof

First, let us quickly rewrite the formulas for the roots, as we did for the
denominator. Let us define, for each $\sigma_{1},\sigma_{2}\in\\{1,-1\\}$ the
quantity

$\widetilde{\rho}(\sigma_{1},\sigma_{2})\,=\,\sqrt{1+2\sigma_{1}tu+2\sigma_{2}tu}\,,$
(84)

for $\sigma_{1},\sigma_{2}\in\\{1,-1\\}$ and let us abbreviate the notation to

$\widetilde{\rho}^{(+)}_{+}\,=\,\widetilde{\rho}(1,1)\,,\qquad\widetilde{\rho}^{(+)}_{-}\,=\,\widetilde{\rho}(1,-1)\,,\qquad\widetilde{\rho}^{(-)}_{+}\,=\,\widetilde{\rho}(-1,1)\,,\qquad\widetilde{\rho}^{(-)}_{-}\,=\,\widetilde{\rho}(-1,-1)\,.$
(85)

Of course, two of these quantities $\widetilde{\rho}^{(+)}_{-}$ and
$\widetilde{\rho}^{(-)}_{+}$ are each equal to just $1$, and the formulas in
(69) and (70) are not terribly complex as compared to the equationsfor
$a_{1},a_{2},b_{1},b_{2}$, which did get simpler in (64) and (65). But using
all of these, we may write

$\displaystyle c_{1}\,$
$\displaystyle=\,\frac{1}{4tu}\,\left(\widetilde{\rho}^{(+)}_{+}-\widetilde{\rho}^{(+)}_{-}\right)^{2}\,,\qquad$
$\displaystyle\qquad c_{2}\,$
$\displaystyle=\,\frac{1}{4tu}\,\left(\widetilde{\rho}^{(-)}_{+}-\widetilde{\rho}^{(-)}_{-}\right)^{2}\,,$
(86) $\displaystyle d_{1}\,$
$\displaystyle=\,\frac{1}{4tu}\,\left(\widetilde{\rho}^{(-)}_{+}+\widetilde{\rho}^{(-)}_{-}\right)^{2}\,,\qquad$
$\displaystyle\qquad d_{2}\,$
$\displaystyle=\,\frac{1}{4tu}\,\left(\widetilde{\rho}^{(+)}_{+}+\widetilde{\rho}^{(+)}_{-}\right)^{2}\,.$
(87)

Now let us finally consider the contour deformation. We note that we may
rewrite the integral in (52) as

$\alpha\left(2t\,\sqrt{1-u^{2}}\,,\ t^{2}u^{2}\right)\,=\,\frac{1}{2\pi
i}\oint_{\mathcal{C}(0;1)}\frac{\xi\cdot\left(\mathcal{Q}_{1}(\xi)/\xi^{2}\right)^{1/2}+2t\xi\,\sqrt{1-u^{2}}}{\mathcal{Q}_{2}(\xi)}\,d\xi\,,$
(88)

using the notation for the quartic polynomials of (37) and (38). Referring to
the three contours shown in Figure 3, this means

$\alpha\left(2t\,\sqrt{1-u^{2}}\,,\ t^{2}u^{2}\right)\,=\,\frac{1}{2\pi
i}\sum_{j\in\\{1,2,3\\}}\oint_{\Gamma_{j}(\delta)}\frac{\xi\cdot\left(\mathcal{Q}_{1}(\xi)/\xi^{2}\right)^{1/2}+2t\xi\,\sqrt{1-u^{2}}}{\mathcal{Q}_{2}(\xi)}\,d\xi\,,$
(89)

but where we know the contour integrals along the contours
$\Gamma_{1}(\delta)$ and $\Gamma_{2}(\delta)$, for $\delta$ sufficiently
small, gives the residues at $a_{1}$ and $a_{2}$, respectively. We will state
what the $\delta\to 0^{+}$ limit of the $\Gamma_{2}(\delta)$ contour gives,
later. We know that the branch cut is along $[c_{1},c_{2}]$, and the poles are
at $a_{1}$ and $a_{2}$. But we must calculate the residues at $a_{1}$ and
$a_{2}$, including the numerator which includes the algebraic term. We may
also simplify the integral a bit for the portion of the contour that comes
from the two sides of the branch cut.

Let us first consider the residues at $\xi=a_{1}$ and $\xi=a_{2}$. When taking
the square-root of $\mathcal{Q}(\xi)/\xi^{2}$ for
$\xi\in\\{a_{1},a_{2}\\}\subset\mathbb{R}$ we need to check the sign of the
square-root output. Note that we wrote $\sqrt{\mathcal{Q}_{1}(\xi)/\xi^{2}}$
because if $|\xi|\in(1-\epsilon,1+\epsilon)$ for $\epsilon\in[0,1)$ fixed,
then we have

$\mathcal{Q}_{1}(\xi)/\xi^{2}\,=\,1+O(t^{2})\,,$ (90)

as $t\to 0$. Therefore, it is in the domain $\mathcal{D}_{1}$. The algebraic
function $\xi\sqrt{\mathcal{Q}_{1}(\xi)/\xi^{2}}$ is analytic for
$\xi\in\mathbb{C}$ satisfying $|\xi|<1$ and $\xi\not\in[c_{1},c_{2}]$.
Moreover for $\xi\in(-1,-1+\epsilon)$ the function is negative, while for
$\xi\in(1-\epsilon,1)$ the function is positive. But then, by inspection, we
see that for $r\in(-1,1)\setminus[c_{1},c_{2}]$, the function
$r\sqrt{\mathcal{Q}_{1}(r)/r^{2}}$, specializing the analytic function,
changes sign at $r=0$. So it is positive for $r\in(0,c_{1})\cup(c_{2},1)$. At
$r=a_{1}$ and $r=a_{2}$ we have

$\mathcal{Q}_{2}(r)\,=\,\mathcal{Q}_{1}(r)-4t^{2}(1-u^{2})r^{2}\,=\,0\,.$ (91)

Therefore, since $0<a_{1}<c_{1}<c_{2}<a_{2}<1$, we do have

$\forall r\in\\{a_{1},a_{2}\\}\,,\ \text{ we have }\
r\cdot(\mathcal{Q}_{1}(r)/r^{2})^{1/2}\,=\,2tr\,.$ (92)

This can also be seen to be consistent with the analysis in Subsection 3.1.
Therefore, for the integrand of (88) at the poles we have the value of the
numerator being as follows:

$\forall r\in\\{a_{1},a_{2}\\}\,,\ \text{ we have }\
r\cdot(\mathcal{Q}_{1}(r)/r^{2})^{1/2}+2tr\,\sqrt{1-u^{2}}\,=\,4tr\,\sqrt{1-u^{2}}\,.$
(93)

Therefore, since

$\mathcal{Q}_{2}(\xi)\,=\,t^{2}u^{2}(\xi-a_{1})(\xi-a_{2})(\xi-b_{1})(\xi-
b_{2})\,,$ (94)

we have the residues for the two contours

$\displaystyle\frac{1}{2\pi
i}\oint_{\Gamma_{1}(\delta)}\frac{\xi\cdot\left(\mathcal{Q}_{1}(\xi)/\xi^{2}\right)^{1/2}+2t\xi\,\sqrt{1-u^{2}}}{t^{2}u^{2}(\xi-
a_{1})(\xi-a_{2})(\xi-b_{1})(\xi-b_{2})}\,d\xi\,$
$\displaystyle=\,\frac{4ta_{1}\sqrt{1-u^{2}}}{t^{2}u^{2}(a_{1}-a_{2})(a_{1}-b_{1})(a_{1}-b_{2})}\,,$
(95) $\displaystyle\frac{1}{2\pi
i}\oint_{\Gamma_{2}(\delta)}\frac{\xi\cdot\left(\mathcal{Q}_{1}(\xi)/\xi^{2}\right)^{1/2}+2t\xi\,\sqrt{1-u^{2}}}{t^{2}u^{2}(\xi-
a_{1})(\xi-a_{2})(\xi-b_{1})(\xi-b_{2})}\,d\xi\,$
$\displaystyle=\,\frac{4ta_{2}\sqrt{1-u^{2}}}{t^{2}u^{2}(a_{2}-a_{1})(a_{2}-b_{1})(a_{2}-b_{2})}\,,$
(96)

if $\delta>0$ is small enough. Combining these two residue integrals, and
performing some simple algebra, we have (for sufficiently small $\delta>0$)

$\begin{split}\frac{1}{2\pi
i}\sum_{j\in\\{1,2\\}}\oint_{\Gamma_{j}(\delta)}\frac{\xi\cdot\left(\mathcal{Q}_{1}(\xi)/\xi^{2}\right)^{1/2}+2t\xi\,\sqrt{1-u^{2}}}{t^{2}u^{2}(\xi-
a_{1})(\xi-a_{2})(\xi-b_{1})(\xi-b_{2})}\,d\xi\,&\\\\[5.0pt]
&=\,\frac{4t\sqrt{1-u^{2}}}{t^{2}u^{2}}\left(-\frac{a_{1}}{(a_{2}-a_{1})(b_{1}-a_{1})(b_{2}-a_{1})}+\frac{a_{2}}{(a_{2}-a_{1})(b_{1}-a_{2})(b_{2}-a_{2})}\right)\\\\[5.0pt]
&=\,\frac{4\sqrt{1-u^{2}}}{tu^{2}}\cdot\frac{\big{(}-a_{1}(b_{1}-a_{2})(b_{2}-a_{2})+a_{2}(b_{1}-a_{1})(b_{2}-a_{1})\big{)}}{(a_{2}-a_{1})(b_{1}-a_{1})(b_{2}-a_{1})(b_{1}-a_{2})(b_{2}-a_{2})}\\\\[5.0pt]
&=\,\frac{4\sqrt{1-u^{2}}}{tu^{2}}\cdot\frac{\big{(}-a_{1}b_{1}b_{2}+a_{1}a_{2}(b_{1}+b_{2})-a_{1}a_{2}^{2}+a_{2}b_{1}b_{2}-a_{2}a_{1}(b_{1}+b_{2})+a_{1}^{2}a_{2}\big{)}}{(a_{2}-a_{1})(b_{1}-a_{1})(b_{2}-a_{1})(b_{1}-a_{2})(b_{2}-a_{2})}\\\\[5.0pt]
&=\,\frac{4\sqrt{1-u^{2}}}{tu^{2}}\cdot\frac{(-a_{1}+a_{2})(b_{1}b_{2}-a_{1}a_{2})}{(a_{2}-a_{1})(b_{1}-a_{1})(b_{2}-a_{1})(b_{1}-a_{2})(b_{2}-a_{2})}\\\\[5.0pt]
&=\,\frac{4\sqrt{1-u^{2}}}{tu^{2}}\cdot\frac{(b_{1}b_{2}-a_{1}a_{2})}{(b_{1}-a_{1})(b_{2}-a_{1})(b_{1}-a_{2})(b_{2}-a_{2})}\,.\end{split}$
(97)

Now let us use the formulas from (64) and (65). We have

$\displaystyle\begin{split}b_{1}-a_{1}\,&=\,\frac{1}{4tu}\left(\left(\rho^{(-)}_{+}+\rho^{(-)}_{-}\right)^{2}-\left(\rho^{(+)}_{+}-\rho^{(+)}_{-}\right)^{2}\right)\\\
&=\,\frac{1}{4tu}\left(\rho^{(+)}_{+}-\rho^{(+)}_{-}+\rho^{(-)}_{+}+\rho^{(-)}_{-}\right)\left(\rho^{(+)}_{-}-\rho^{(+)}_{+}+\rho^{(-)}_{+}+\rho^{(-)}_{-}\right)\,,\end{split}$
(98)
$\displaystyle\begin{split}b_{2}-a_{1}\,&=\,\frac{1}{4tu}\left(\left(\rho^{(+)}_{+}+\rho^{(+)}_{-}\right)^{2}-\left(\rho^{(+)}_{+}-\rho^{(+)}_{-}\right)^{2}\right)\\\
&=\,\frac{1}{4tu}\left(2\rho^{(+)}_{+}\right)\left(2\rho^{(+)}_{-}\right)\,,\end{split}$
(99)
$\displaystyle\begin{split}b_{1}-a_{2}\,&=\,\frac{1}{4tu}\left(\left(\rho^{(-)}_{+}+\rho^{(-)}_{-}\right)^{2}-\left(\rho^{(-)}_{+}-\rho^{(-)}_{-}\right)^{2}\right)\\\
&=\,\frac{1}{4tu}\left(2\rho^{(-)}_{+}\right)\left(2\rho^{(-)}_{-}\right)\,,\end{split}$
(100)
$\displaystyle\begin{split}b_{2}-a_{2}\,&=\,\frac{1}{4tu}\left(\left(\rho^{(+)}_{+}+\rho^{(+)}_{-}\right)^{2}-\left(\rho^{(-)}_{+}-\rho^{(-)}_{-}\right)^{2}\right)\\\
&=\,\frac{1}{4tu}\left(\rho^{(+)}_{+}+\rho^{(+)}_{-}+\rho^{(-)}_{+}-\rho^{(-)}_{-}\right)\left(\rho^{(+)}_{+}+\rho^{(+)}_{-}+\rho^{(-)}_{-}-\rho^{(-)}_{+}\right)\,,\end{split}$
(101)

and finally

$\begin{split}b_{1}b_{2}-a_{1}a_{2}\,&=\,\frac{1}{16t^{2}u^{2}}\left(\left(\rho^{(+)}_{+}+\rho^{(+)}_{-}\right)^{2}\left(\rho^{(-)}_{+}+\rho^{(-)}_{-}\right)^{2}-\left(\rho^{(+)}_{+}-\rho^{(+)}_{-}\right)^{2}\left(\rho^{(-)}_{+}-\rho^{(-)}_{-}\right)^{2}\right)\\\\[5.0pt]
&=\,\frac{1}{16t^{2}u^{2}}\left(\left(\rho^{(+)}_{+}+\rho^{(+)}_{-}\right)\left(\rho^{(-)}_{+}+\rho^{(-)}_{-}\right)-\left(\rho^{(+)}_{+}-\rho^{(+)}_{-}\right)\left(\rho^{(-)}_{+}-\rho^{(-)}_{-}\right)\right)\\\
&\qquad\cdot\left(\left(\rho^{(+)}_{+}+\rho^{(+)}_{-}\right)\left(\rho^{(-)}_{+}+\rho^{(-)}_{-}\right)+\left(\rho^{(+)}_{+}-\rho^{(+)}_{-}\right)\left(\rho^{(-)}_{+}-\rho^{(-)}_{-}\right)\right)\\\\[5.0pt]
&=\,\frac{1}{16t^{2}u^{2}}\left(2\rho^{(+)}_{+}\rho^{(-)}_{-}+2\rho^{(+)}_{-}\rho^{(-)}_{+}\right)\left(2\rho^{(+)}_{+}\rho^{(-)}_{+}+2\rho^{(+)}_{-}\rho^{(-)}_{-}\right)\,.\end{split}$
(102)

We will simplify this a bit more. But first, let us state the small algebraic
simplifications available for the contour integral

$\frac{1}{2\pi
i}\oint_{\Gamma_{3}(\delta)}\frac{\xi\cdot\left(\mathcal{Q}_{1}(\xi)/\xi^{2}\right)^{1/2}+2t\xi\,\sqrt{1-u^{2}}}{\mathcal{Q}_{2}(\xi)}\,d\xi\,,$
(103)

from (89).

###  3.3 Simplifying the integral around the contour $\Gamma_{3}(\delta)$

We may rewrite the contour integral as

$\frac{1}{2\pi i}\oint_{\Gamma_{3}(\delta)}\frac{tu\,\sqrt{\xi-
c_{1}}\,\sqrt{\xi-
c_{2}}\,\sqrt{d_{1}-\xi}\,\sqrt{d_{2}-\xi}+2t\xi\,\sqrt{1-u^{2}}}{\mathcal{Q}_{2}(\xi)}\,d\xi\,,$
(104)

by rewriting $\xi\cdot\left(\mathcal{Q}_{1}(\xi)/\xi^{2}\right)^{1/2}$ as in
Subsection 3.1. We know that for $r\in(c_{1},c_{2})$ we have

$\sqrt{\xi-c_{1}}\,\sqrt{\xi-c_{2}}\,\approx\,i\,\sqrt{(r-c_{1})(c_{2}-r)}\
\text{ for $\xi=r+i\delta$, as $\delta\to 0^{+}$.}$ (105)

Again, we refer to the analysis of Subsection 3.1. But for
$r\in(c_{1},c_{2})$, we have

$\sqrt{\xi-c_{1}}\,\sqrt{\xi-c_{2}}\,\approx\,-i\,\sqrt{(r-c_{1})(c_{2}-r)}\
\text{ for $\xi=r-i\delta$, as $\delta\to 0^{+}$.}$ (106)

Also, by analyticity, we know

$\frac{1}{2\pi
i}\oint_{\Gamma_{3}(\delta)}\frac{2t\xi\,\sqrt{1-u^{2}}}{\mathcal{Q}_{2}(\xi)}\,d\xi\,=\,0\,.$
(107)

It is also easily seen that the vertical edge contributions to the contour
integral may be bounded by terms which are vanishingly small when $\delta\to
0$. So

$\lim_{\delta\to 0}\frac{1}{2\pi
i}\oint_{\Gamma_{3}(\delta)}\frac{\xi\cdot\left(\mathcal{Q}_{1}(\xi)/\xi^{2}\right)^{1/2}}{\mathcal{Q}_{2}(\xi)}\,d\xi\,=\,\frac{-2i}{2\pi
i}\int_{c_{1}}^{c_{2}}\frac{tu\,\sqrt{(r-c_{1})(c_{2}-r)(d_{1}-r)(d_{2}-r)}}{\mathcal{Q}_{2}(r)}\,dr\,,$
(108)

which we obtained also by using the fact that for the top edge face of the
rectangle $\Gamma_{3}$, the contribution to the contour integral has the
opposite orientation as a typical real integral, while for the bottom edge
face it has the positive orientation. But, of course, $\mathcal{Q}_{2}(r)$ is
also negative on the whole interval $[c_{1},c_{2}]$. This is how we obtain a
positive integral contribution from the third contour integral around the
branch cut:

$\lim_{\delta\to 0}\frac{1}{2\pi
i}\oint_{\Gamma_{3}(\delta)}\frac{\xi\cdot\left(\mathcal{Q}_{1}(\xi)/\xi^{2}\right)^{1/2}}{\mathcal{Q}_{2}(\xi)}\,d\xi\,=\,\frac{1}{2\pi}\int_{c_{1}}^{c_{2}}\frac{\sqrt{-\mathcal{Q}_{1}(r)}}{-\mathcal{Q}_{2}(r)}\,dr\,.$
(109)

###  3.4 Resumption of simplification of residues

Based on equations (97) and (98), (99), (100), (101) and (102), the sum of the
two residues is given by

$\begin{split}\frac{4\sqrt{1-u^{2}}}{tu^{2}}\,\cdot\frac{(b_{1}b_{2}-a_{1}a_{2})}{(b_{1}-a_{1})(b_{2}-a_{1})(b_{1}-a_{2})(b_{2}-a_{2})}\,&=16t\,\sqrt{1-u^{2}}\\\
&\cdot\frac{\left(\rho^{(+)}_{+}\rho^{(-)}_{-}+\rho^{(+)}_{-}\rho^{(-)}_{+}\right)\left(\rho^{(+)}_{+}\rho^{(-)}_{+}+\rho^{(+)}_{-}\rho^{(-)}_{-}\right)}{1}\\\
&\cdot\frac{1}{\left(\rho^{(+)}_{+}-\rho^{(+)}_{-}+\rho^{(-)}_{+}+\rho^{(-)}_{-}\right)\left(\rho^{(+)}_{-}-\rho^{(+)}_{+}+\rho^{(-)}_{+}+\rho^{(-)}_{-}\right)}\\\
&\cdot\frac{1}{\rho^{(+)}_{+}\rho^{(+)}_{-}\rho^{(-)}_{+}\rho^{(-)}_{-}}\\\
&\cdot\frac{1}{\left(\rho^{(+)}_{+}+\rho^{(+)}_{-}+\rho^{(-)}_{+}-\rho^{(-)}_{-}\right)\left(\rho^{(+)}_{+}+\rho^{(+)}_{-}+\rho^{(-)}_{-}-\rho^{(-)}_{+}\right)}\end{split}$
(110)

We note that, since

$\begin{split}\rho^{(+)}_{+}\,=\,\sqrt{1+2t+2tu}\,,\qquad\rho^{(+)}_{-}\,=\,\sqrt{1+2t-2tu}\,,\\\\[3.0pt]
\rho^{(-)}_{+}\,=\,\sqrt{1-2t+2tu}\,,\qquad\rho^{(-)}_{-}\,=\,\sqrt{1-2t-2tu}\,,\end{split}$
(111)

we may more easily express

$\displaystyle\rho^{(+)}_{+}\rho^{(-)}_{-}\,=\,\sqrt{1+2t+2tu}\,\sqrt{1-2t-2tu}\,=\,\sqrt{1-(2t+2tu)^{2}}\,,$
(112)
$\displaystyle\rho^{(+)}_{-}\rho^{(-)}_{+}\,=\,\sqrt{1+2t-2tu}\,\sqrt{1-2t+2tu}\,=\,\sqrt{1-(2t-2tu)^{2}}\,,$
(113)
$\displaystyle\rho^{(+)}_{+}\rho^{(-)}_{+}\,=\,\sqrt{1+2t+2tu}\,\sqrt{1-2t+2tu}\,=\,\sqrt{(1+2tu)^{2}-4t^{2}}\,,$
(114)
$\displaystyle\rho^{(+)}_{-}\rho^{(-)}_{-}\,=\,\sqrt{1+2t-2tu}\,\sqrt{1-2t-2tu}\,=\,\sqrt{(1-2tu)^{2}-4t^{2}}\,.$
(115)

Hence, we may rewrite (110) as

$\begin{split}\frac{4\sqrt{1-u^{2}}}{tu^{2}}\,\cdot\frac{(b_{1}b_{2}-a_{1}a_{2})}{(b_{1}-a_{1})(b_{2}-a_{1})(b_{1}-a_{2})(b_{2}-a_{2})}\,&=16t\,\sqrt{1-u^{2}}\\\
&\cdot\frac{\left(\sqrt{1-(2t+2tu)^{2}}+\sqrt{1-(2t-2tu)^{2}}\right)\left(\sqrt{(1+2tu)^{2}-4t^{2}}+\sqrt{(1-2tu)^{2}-4t^{2}}\right)}{1}\\\
&\cdot\frac{1}{\left(\rho^{(+)}_{+}-\rho^{(+)}_{-}+\rho^{(-)}_{+}+\rho^{(-)}_{-}\right)\left(\rho^{(+)}_{-}-\rho^{(+)}_{+}+\rho^{(-)}_{+}+\rho^{(-)}_{-}\right)}\\\
&\cdot\frac{1}{\sqrt{(1+2t+2tu)(1+2t-2tu)(1-2t+2tu)(1-2t-2tu)}}\\\
&\cdot\frac{1}{\left(\rho^{(+)}_{+}+\rho^{(+)}_{-}+\rho^{(-)}_{+}-\rho^{(-)}_{-}\right)\left(\rho^{(+)}_{+}+\rho^{(+)}_{-}+\rho^{(-)}_{-}-\rho^{(-)}_{+}\right)}\end{split}$
(116)

For the remaining factors involving $\rho^{(+)}_{+}$, $\rho^{(+)}_{-}$,
$\rho^{(-)}_{+}$ and $\rho^{(-)}_{-}$, we note that collecting the terms the
denominator is of the form

$(a+b+c-d)(a+b-c+d)(a-b+c+d)(-a+b+c+d)\,,\ \text{ for
$\\{a,b,c,d\\}=\left\\{\rho^{(+)}_{+},\rho^{(+)}_{-},\rho^{(-)}_{+},\rho^{(-)}_{-}\right\\}$.}$
(117)

That can be seen to equal
$(a^{2}+b^{2}+c^{2}+d^{2})^{2}-2(a^{4}+b^{4}+c^{4}+d^{4})+8abcd$. But we may
see that

$\left(\rho^{(+)}_{+}\right)^{2}+\left(\rho^{(+)}_{-}\right)^{2}+\left(\rho^{(-)}_{+}\right)^{2}+\left(\rho^{(-)}_{-}\right)^{2}\,=\,4\,,$
(118)

while

$\left(\rho^{(+)}_{+}\right)^{4}+\left(\rho^{(+)}_{-}\right)^{4}+\left(\rho^{(-)}_{+}\right)^{4}+\left(\rho^{(-)}_{-}\right)^{4}\,=\,4+4t^{2}+4t^{2}u^{2}\,.$
(119)

So, we obtain that the product of the remaining unsimplified denominators
(meaning still expressed in terms of $\rho^{(+)}_{+}$, $\rho^{(+)}_{-}$,
$\rho^{(-)}_{+}$ and $\rho^{(-)}_{-}$) as

$16-2\left(4+4t^{2}+4t^{2}u^{2}\right)+8\sqrt{(1+2t+2tu)(1+2t-2tu)(1-2t+2tu)(1-2t-2tu)}\,.$
(120)

We may also notice that

$(1+2t+2tu)(1+2t-2tu)(1-2t+2tu)(1-2t-2tu)\,=\,1-8(1+u^{2})t^{2}+16(1-u^{2})^{2}t^{4}\,.$
(121)

So the expression in (120) may be rewritten as

$8-8(1+u^{2})t^{2}+8\sqrt{1-8(1+u^{2})t^{2}+16(1-u^{2})^{2}t^{4}}\,.$ (122)

##  Appendix A Bonferroni inequalities and Bell polynomials

The principle of inclusion-exclusion (PIE) and the associated inequalities
related to the PIE are a well-known topic at the intersection of combinatorics
and probability theory. We will follow the exposition from the textbook of
Charalambides [4] which we appreciate, greatly. The descriptions there are
clear, and also sufficiently complete to be useful to newcomers. For us, it is
nice that he discusses the Bonferroni inequalities and the Bell polynomials in
some detail.

Recall that we are interested in the number of cardinality $k$ subsequences of
$\\{1,\dots,n\\}$ which are increasing for a uniform random permutation
$\pi\in S_{n}$. Let us denote by $C_{n,k}$ the collection of $k$-tuples
$\boldsymbol{i}=(i_{1},\dots,i_{k})\in{\mathbb{Z}}^{k}$ such that

$1\,\leq\,i_{1}\,<\,i_{2}\,<\,\dots\,<\,i_{k}\,\leq\,n\,.$ (123)

So, for instance, the cardinality of this set is

$|C_{n,k}|\,=\,\binom{n}{k}\,.$ (124)

Given a permutation $\pi\in S_{n}$ and $(i_{1},\dots,i_{k})\in C_{n,k}$, let
us denote the indicator for $(i_{1},\dots,i_{k})$ being an increasing
subsequence of $\pi$:

$\mathcal{P}_{n,k}(\pi;(i_{1},\dots,i_{k}))\,=\,\prod_{a=1}^{k-1}\mathbf{1}_{(0,\infty)}(\pi_{i_{a+1}}-\pi_{i_{a}})\,.$
(125)

So, for example, we know that

$\forall(i_{1},\dots,i_{k})\in C_{n,k}\,,\ \text{ we have }\ \sum_{\pi\in
S_{n}}\mathcal{P}_{n,k}(\pi;(i_{1},\dots,i_{k}))\,=\,\frac{n!}{k!}\,,$ (126)

by the discussion around equations (3), (4) and (5). Now let
$\widetilde{C}^{(r)}_{n,k}$ denote the collection of all sets

$\left\\{\boldsymbol{i}^{(1)},\dots,\boldsymbol{i}^{(r)}\right\\}\,,$ (127)

satisfying

  * $\bullet$

for each $s\in\\{1,\dots,r\\}$ we have
$\boldsymbol{i}^{(s)}=(i^{(s)}_{1},\dots,i^{(s)}_{k})\in C_{n,k}$,

  * $\bullet$

for each $s,t\in\\{1,\dots,r\\}$, if $s\neq t$ then there is some
$a\in\\{1,\dots,k\\}$ such that $i^{(s)}_{a}\neq i^{(t)}_{a}$.

Therefore, we have, for instance, that the cardinality is equal to

$\left|\widetilde{C}^{(r)}_{n,k}\right|\,=\,\binom{\binom{n}{k}}{r}\,=\,\frac{N(N-1)\cdots(N-r+1)}{r!}\Bigg{|}_{N=\binom{n}{k}}\,.$
(128)

Now, following the notation from Chapter 4 of Charalambides, let us define

$\mathcal{S}_{n,k}^{(r)}\,=\,\sum_{\pi\in
S_{n}}\,\sum_{\\{\boldsymbol{i}^{(1)},\dots,\boldsymbol{i}^{(r)}\\}\in\widetilde{C}^{(r)}_{n,k}}\,\prod_{s=1}^{r}\mathcal{P}_{n,k}(\pi;\boldsymbol{i}^{(s)})\,.$
(129)

This is equal to the sum over all
$(\boldsymbol{i}^{(1)},\dots,\boldsymbol{i}^{(r)})\in\widetilde{C}^{(r)}_{n,k}$
of the number of permutations in $S_{n}$ such that each of
$\boldsymbol{i}^{(1)}$, …, $\boldsymbol{i}^{(r)}$ is an increasing subsequence
for $\pi$. So, for example,

$\frac{1}{n!}\,\mathcal{S}_{n,k}^{(1)}\,=\,\binom{n}{k}\cdot\frac{1}{k!}\,,$
(130)

as in equation (8). Note that we are following the notation of the
combinatorics textbook of Charalambides, so that we focus on cardinalities,
instead of expectations and probabilities. (That is what we needed to
noramlize by $1/n!$ on the left-hand-side of the equation above.) Now,
following the notation from Charalambides, let us define

$\mathcal{L}^{(r)}_{n,k}\,=\,\left|\left\\{\pi\in
S_{n}\,:\,\exists\\{\boldsymbol{i}^{(1)},\dots,\boldsymbol{i}^{(r)}\\}\in\widetilde{C}^{(r)}_{n,k}\,,\
\text{ s.t. }\
\prod_{s=1}^{r}\mathcal{P}_{n,k}(\pi,\boldsymbol{i}^{(s)})=1\right\\}\right|\,.$
(131)

This is equal to the number of permutations $\pi\in S_{n}$ such that there are
at least $r$ distinct subsequences
$\boldsymbol{i}^{(1)},\dots,\boldsymbol{i}^{(r)}\in C_{n,k}$, each of
cardinality $k$, such that all of the $r$ subsequences are increasing for
$\pi$. Then note that we have

$\frac{1}{n!}\,\mathcal{L}^{(r)}_{n,k}\,=\,\mathbf{P}(\\{\pi\in
S_{n}\,:\,Z_{n,k}(\pi)\geq r\\})\,.$ (132)

In principle, we are most interested in $\mathcal{L}^{(1)}_{n,k}$ because this
is the cardinality which arises in the formula for the length of the longest
increasing subsequence:

$\frac{1}{n!}\,\mathcal{L}^{(1)}_{n,k}\,=\,\mathbf{P}(\\{\pi\in
S_{n}\,:\,Z_{n,k}(\pi)\geq 1\\})\,=\,\mathbb{P}(\\{\pi\in
S_{n}\,:\,L_{n}(\pi)\geq k\\})\,.$ (133)

But Charalambides states the Bonferroni inequalities for general $r$.
Therefore, we defined the terms for general $r$, in order to most closely
match his notation. (Note that that variable which he calls $k$ is what we
call $r$, and there are other minor changes mutatis mutandis.)

######  Proposition A.1 (Version of the Bonferroni inequalities)

Suppose we have $n\in\mathbb{N}$ and we have chosen $k\in\\{1,\dots,n\\}$.
Then, for each $r\in\\{1,\dots,\binom{n}{k}\\}$ and for each
$R\in\\{0,1,\dots,|\widetilde{C}^{(r)}_{n,k}|\\}$ we have

$(-1)^{R-r+1}\left(\mathcal{L}_{n,k}^{(r)}-\sum_{s=r}^{R}(-1)^{s-r}\binom{s-1}{r-1}\mathcal{S}_{n,k}^{(s)}\right)\,\geq\,0\,.$
(134)

We will not provide the proof of this proposition, since we have copied it
from [4] where it is Theorem 4.5, equation (4.23). Our main interest is in the
case of $r=1$. So, summarizing that case, the proposition implies that for
each $R\in\\{1,\dots,\binom{n}{k}\\}$, we have:

  * $\bullet$

if $R$ is even then

$\mathcal{L}_{n,k}^{(1)}\,\geq\,\sum_{s=1}^{R}(-1)^{s-1}\mathcal{S}_{n,k}^{(s)}\,;$
(135)

  * $\bullet$

whereas, if $R$ is odd then

$\mathcal{L}_{n,k}^{(1)}\,\leq\,\sum_{s=1}^{R}(-1)^{s-1}\mathcal{S}_{n,k}^{(s)}\,.$
(136)

Of course, PIE also gives (as in Theorem 4.2 of Charalambides for example)

$\mathcal{L}_{n,k}^{(1)}\,=\,\sum_{s=1}^{|C_{n,k}|}(-1)^{s-1}\mathcal{S}_{n,k}^{(s)}\,.$
(137)

So, if one could calculate $\mathcal{S}_{n,k}^{(s)}$ for all $s$ up to
$|C_{n,k}|=\binom{n}{k}$, then this gives a method of calculating
$\mathcal{L}_{n,k}^{(1)}$ from them, in principle. But the goal of the
Bonferroni inequalities is to hopefully obtain inequalities that are useful
without requiring all $\mathcal{S}_{n,k}^{(s)}$ for $s$ going up to
$\binom{n}{k}$, but merely those for $s\in\\{1,\dots,R\\}$. It is hoped that
for some $R\leq\binom{n}{k}$ this gives an easier method of bracketing
$\mathcal{L}_{n,k}^{(1)}$ in order to calculate $\mathbb{P}(L_{n}\geq k)$.

The next step is to simplify the calculation of the quantities
$\mathcal{S}_{n,k}^{(r)}$. What Pinsky’s method allow us to calculate is
moments of $Z_{n,k}$. One may note that $Z_{n,k}(\pi)$ is the total number of
cardinality $k$ subsequences, $\boldsymbol{i}\in C_{n,k}$ such that
$\boldsymbol{i}$ is increasing for $\pi$. Then it is easy to see that

$\sum_{\\{\boldsymbol{i}^{(1)},\dots,\boldsymbol{i}^{(r)}\\}\in\widetilde{C}^{(r)}_{n,k}}\,\prod_{s=1}^{r}\mathcal{P}_{n,k}(\pi;\boldsymbol{i}^{(s)})\,=\,\binom{Z_{n,k}(\pi)}{r}\,=\,\frac{1}{r!}\,Z_{n,k}(\pi)\big{(}Z_{n,k}(\pi)-1\big{)}\cdots\big{(}Z_{n,k}-r+1\big{)}\,.$
(138)

In other words, combining the earlier calculations, we have for
$r\in\\{1,\dots,\binom{n}{r}\\}$:

  * •

if $r$ is even, then

$\mathbf{P}(L_{n}\geq k)\,=\,\mathbf{P}(Z_{n,k}\geq
1)\,\geq\,\sum_{s=1}^{R}(-1)^{s-1}\mathbf{E}\left[\binom{Z_{n,k}}{r}\right]\,;$
(139)

  * •

while if $r$ is odd, then

$\mathbf{P}(L_{n}\geq k)\,=\,\mathbf{P}(Z_{n,k}\geq
1)\,\leq\,\sum_{s=1}^{R}(-1)^{s-1}\mathbf{E}\left[\binom{Z_{n,k}}{r}\right]\,.$
(140)

###### Remark A.2

In an earlier version of this article, we promoted the idea of the Bell
polynomials, not realizing the simple connection to the factorial moments.

Precisely, the important fact is that, defining exponential Bell partition
polynomials as $B_{0}\equiv 0$ and for $r\in\mathbb{N}=\\{1,2,\dots\\}$

$B_{r}(x_{1},\dots,x_{r})\,=\,\sum_{s=0}^{r-1}\binom{r+1}{s}x_{s+1}B_{r-1-s}(x_{1},\dots,x_{r-1-s})\,,$
(141)

we have that the following 1-variable specialization gives the identity

$\forall r\in\\{0,1,\dots\\}\,,\ \text{ we have }\
B_{r}(-0!z,-1!z,\dots,-(r-1)!z)\,=\,\frac{1}{r!}\,(z)_{r}\,,$ (142)

where $(z)_{r}$ is the Pochhammer symbol, falling factorial from (29). A
reference for the Bell polynomials is Charalambides, Theorem 11.2 [4].

Even though the necessity is now bypassed, let us describe our old
observations that we largely transcribed from Charalambides. The reason that
the Bell polynomials are relevant is that according to Newton’s identity

https://en.wikipedia.org/wiki/Newton’s_identities

we have the following relation between symmetric functions

$r\cdot
e_{r}(x_{1},\dots,x_{N})\,=\,\sum_{s=1}^{r}(-1)^{s-1}e_{r-s}(x_{1},\dots,x_{N})p_{s}(x_{1},\dots,x_{N})\,,$
(143)

where the power sum symmetric functions are

$p_{r}(x_{1},\dots,x_{N})\,=\,\sum_{\kappa=1}^{N}x_{\kappa}^{r}\,,$ (144)

and the elementary symmetric functions are

$e_{r}(x_{1},\dots,x_{N})\,=\,\sum_{i_{1},\dots,i_{r}\in\\{1,\dots,N\\}}\left(\prod_{s=1}^{r-1}\mathbf{1}_{(0,\infty)}(i_{s+1}-i_{s})\right)x_{i_{1}}x_{i_{2}}\cdots
x_{i_{r}}\,.$ (145)

Relatedly, there are identities for certain types of generating functions of
these symmetric functions:

$1+\sum_{r=1}^{N}(-t)^{k}e_{r}(x_{1},\dots,x_{N})\,=\,\exp\left(-\sum_{r=1}^{\infty}\frac{t^{r}}{r}p_{r}(x_{1},\dots,x_{N})\right)\,.$
(146)

This is relevant because according to (129)

$\mathcal{S}_{n,k}^{(r)}\,=\,\sum_{\pi\in
S_{n}}e_{r}(\mathfrak{X}_{1}(\pi),\dots,\mathfrak{X}_{N}(\pi))\,,$ (147)

where we enumerate the elements of $C_{n,k}$ as

$C_{n,k}\,=\,\left\\{\boldsymbol{i}^{(1)},\dots,\boldsymbol{i}^{(N)}\right\\}\,,$
(148)

and, for each $\kappa\in\\{1,\dots,N\\}$, we define

$\mathfrak{X}_{\kappa}:S_{n}\to\\{0,1\\}\,,\ \text{ defined by the formula }\
\mathfrak{X}_{\kappa}(\pi)\,=\,\mathcal{P}_{n,k}\left(\pi;\boldsymbol{i}^{(\kappa)}\right)\,.$
(149)

But then, since each $\mathfrak{X}_{\kappa}$ is an indicator function, we have

$\forall r\in\mathbb{N}=\\{1,2,\dots\\}\,,\ \text{ we have }\
p_{r}(\mathfrak{X}_{1},\dots,\mathfrak{X}_{N})\,=\,Z_{n,k}\,=\,\sum_{s=1}^{N}\mathfrak{X}_{\kappa}\,.$
(150)

If we did not have this simple formula, then a formula for each
$r\in\mathbb{N}$ would be useful more generally:

$e_{r}(x_{1},\dots,x_{N})\,=\,\frac{(-1)^{r}}{r!}\,B_{r}(-0!p_{1}(x_{1},\dots,x_{N}),\dots,-(r-1)!p_{r}(x_{1},\dots,x_{r}))\,,$
(151)

which essentially restates (146) via (141) (which is equivalent to the
generating function identity stating that
$\sum_{r=1}^{\infty}B_{n}(x_{1},\dots,x_{n})t^{n}/n!$ is equal to
$\exp\left(\sum_{r=1}^{\infty}x_{r}t^{r}/r!\right)$ as in Charalambides
Corollary 11.1). See, for example, Example 11.5 on page 427 in [4].

##  Appendix B Contour integral alternative derivation of Lemma 2.1

By the equation (23) we may write

$\gamma^{(2)}(x^{2},y^{2})\,=\,\oint_{\mathcal{C}(0;1)}\oint_{\mathcal{C}(0;1)}\gamma(x\xi,y\zeta)\gamma\left(\frac{x}{\xi}\,,\
\frac{y}{\zeta}\right)\,\frac{d\xi}{2\pi i\xi}\,\cdot\frac{d\zeta}{2\pi
i\zeta}\,,$ (152)

which may be rewritten as

$\gamma^{(2)}(x^{2},y^{2})\,=\,\oint_{\mathcal{C}(0;1)}\oint_{\mathcal{C}(0;1)}\frac{1}{1-(x\xi+y\zeta)}\,\cdot\frac{1}{1-(x\xi^{-1}+y\zeta^{-1})}\,\cdot\frac{d\xi}{2\pi
i\xi}\,\cdot\frac{d\zeta}{2\pi i\zeta}\,.$ (153)

This may be rewritten as

$\gamma^{(2)}(x^{2},y^{2})\,=\,-\frac{1}{4\pi^{2}}\,\oint_{\mathcal{C}(0;1)}\oint_{\mathcal{C}(0;1)}\frac{1}{1-(x\xi+y\zeta)}\,\cdot\frac{1}{\xi\zeta-(x\zeta+y\xi)}\,d\xi\,d\zeta\,.$
(154)

Let us first integrate over $\zeta$. Therefore, we use the partial fraction
expansion for $\zeta$:

$\begin{split}\frac{1}{1-(x\xi+y\zeta)}\,\cdot\frac{1}{\xi\zeta-(x\zeta+y\xi)}\,&=\,\frac{1}{1-x\xi-y\zeta}\,\cdot\frac{1}{(\xi-x)\zeta-y\xi}\\\
&=\,\frac{1}{(\xi-x)(1-x\xi)-y^{2}\xi}\left(\frac{y}{1-x\xi-y\zeta}+\frac{\xi-x}{(\xi-x)\zeta-y\xi}\right)\end{split}$
(155)

Therefore, considering the integrand of (154) as a function of $\zeta$, the
poles are at

$\alpha\,=\,\frac{1-x\xi}{y}\,,\ \text{ and }\
\beta\,=\,\frac{y\xi}{\xi-x}\,.$ (156)

For $|x|$ and $|y|$ sufficiently small, and for $|\xi|=1$, we see that
$|\alpha|>1$ and $|\beta|<1$. Therefore, from the residue theorem (see for
example Theorem 17 in Section 4.5 of Ahlfors [1])

$\gamma^{(2)}(x^{2},y^{2})\,=\,\frac{1}{2\pi
i}\,\oint_{\mathcal{C}(0;1)}\frac{1}{(\xi-x)(1-x\xi)-y^{2}\xi}\,d\xi\,.$ (157)

Now we may factorize the denominator in the integrand of this integral, as a
polynomial in $\xi$ in order to find the locations of the poles and calculate
the residues. Note that if we had $x=0$ the integral $(2\pi
i)^{-1}\oint_{\mathcal{C}(0;1)}(\xi-y^{2}\xi)^{-1}\,d\xi$ would give
$(1-y^{2})^{-1}$ by the residue theorem. Let us assume $x\neq 0$, and then
note

$\begin{split}(\xi-x)(1-x\xi)-y^{2}\xi&=\,\xi-x-x\xi^{2}+x^{2}\xi-y^{2}\xi\\\
&=\,-x\left(\xi^{2}-\frac{1+x^{2}-y^{2}}{x}\,\xi+1\right)\end{split}$ (158)

By the formulas from Section 2.1 we have for $k=(1+x^{2}-y^{2})/x$, the roots
are at

$\xi_{\pm}\,=\,\frac{1}{4}\left(\sqrt{k+2}\pm\sqrt{k-2}\right)^{2}\,=\,\frac{1}{4}\left(\sqrt{\frac{1+x^{2}-y^{2}+2x}{x}}\pm\sqrt{\frac{1+x^{2}-y^{2}-2x}{x}}\right)^{2}\,,$
(159)

as long as we assume

$k\,=\,\frac{1+x^{2}-y^{2}}{x}\in\mathbb{C}\setminus(-2,2)\,.$ (160)

Note that we are justified in assuming that $x,y\in[0,\infty)$ and are small,
since determining the power series for $x$ and $y$ in that regime determines
it elsewhere by the identity theorem of complex analysis and the discussion of
the Fubini-Tonelli theorem before, between equations (17) and (18) Note that
for $x>0$ sufficiently small, we know that $\xi_{+}>1$ and $\xi_{-}<1$. (Note
that $\xi_{+}\xi_{-}=1$.) Therefore, by the residue theorem, we have

$\gamma^{(2)}(x^{2},y^{2})\,=\,-\frac{1}{x}\cdot\frac{1}{\xi_{-}-\xi_{+}}\,=\,\frac{1}{x}\cdot\frac{1}{\xi_{+}-\xi_{-}}\,.$
(161)

But it is easy to see the algebraic simplification

$\begin{split}x\cdot(\xi_{+}-\xi_{-})\,&=\,\frac{x}{4}\,\left(\left(\sqrt{k+2}+\sqrt{k-2}\right)^{2}-\left(\sqrt{k+2}-\sqrt{k-2}\right)^{2}\right)\\\
&=\,\frac{x}{4}\,\left(2\,\sqrt{k+2}\right)\left(2\,\sqrt{k-2}\right)\,.\end{split}$
(162)

Therefore, this may be further simplified as

$\begin{split}x\cdot(\xi_{+}-\xi_{-})\,&=\,\sqrt{\big{(}(1+x)^{2}-y^{2}\big{)}\big{(}(1-x)^{2}-y^{2}\big{)}}\\\
&=\,\sqrt{\big{(}(1+x^{2}-y^{2})+2x\big{)}\big{(}(1+x^{2}-y^{2})-2x\big{)}}\\\
&=\,\sqrt{(1+x^{2}-y^{2})^{2}-4x^{2}}\end{split}$ (163)

Then we expand

$\begin{split}(1+x^{2}-y^{2})^{2}-4x^{2}\,&=\,1+2(x^{2}-y^{2})+(x^{2}-y^{2})^{2}-4x^{2}\\\
&=\,1+(2x^{2}-2y^{2})+(x^{4}-2x^{2}y^{2}+y^{4})-4x^{2}\\\
&=\,1-2x^{2}-2y^{2}+x^{4}+2x^{2}y^{2}+y^{4}-4x^{2}y^{2}\\\
&=\,1-2(x^{2}+y^{2})+(x^{2}+y^{2})^{2}-4x^{2}y^{2}\\\
&=\,(1-(x^{2}+y^{2}))^{2}-4x^{2}y^{2}\,.\end{split}$ (164)

Therefore, we have,

$\gamma^{(2)}(x^{2},y^{2})\,=\,\frac{1}{\sqrt{\big{(}1-\left(x^{2}+y^{2}\right)\big{)}^{2}-4x^{2}y^{2}}}\,.$
(165)

Recall that it suffices to assume that we have $x,y\in[0,\infty)$ both
sufficiently small to specify the actual power series in complex $x$ and $y$.
Therefore, we obtain the desired result by replacing $x\geq 0$ by
$\sqrt{x}\geq 0$ and replacing $y\geq 0$ by $\sqrt{y}\geq 0$.

##  Appendix C Pochhamer identities for $-1/2$ and negative integers

Here we state what needs to be used to derive the equivalence of (31) and
(32). Note that

$(-1/2)_{n}\,=\,\left(-\frac{1}{2}\right)\left(-\frac{3}{2}\right)\cdots\left(-\frac{1+2(n-1)}{2}\right)\,,$
(166)

which equals

$(-1/2)_{n}\,=\,\frac{(-1)^{n}}{2^{n}}\left(1\right)\left(3\right)\cdots\left(2n-1\right)\,,$
(167)

which in turn may be rewritten as

$(-1/2)_{n}\,=\,\frac{(-1)^{n}}{2^{n}}\cdot\frac{(2n)!}{(2)(4)\cdots(2n)}\,=\,\frac{(-1)^{n}}{2^{2n}}\cdot\frac{(2n)!}{n!}\,.$
(168)

This well-known fact is easily found, for example on Wikipedia it can be
deduced from the formula $\Gamma(1/2)=\sqrt{\pi}$ and
$\Gamma(\frac{1}{2}-n)=(-1)^{n}2^{2n}n!\sqrt{\pi}/(2n)!$.

We also know that for the Pochhammer symbol at a negative integer we have

$(-n)_{k}\,=\,(-n)(-n-1)\cdots(-n-k+1)\,=\,(-1)^{k}(n)(n+1)(n+k-1)\,=\,(-1)^{k}\,\frac{(n+k-1)!}{(n-1)!}\,.$
(169)

Hence, in particular replacing $n$ by $2n+1$ we have

$(-2n-1)_{k}\,=\,(-1)^{k}\,\frac{(2n+k)!}{(2n)!}\,.$ (170)

Therefore, putting these two together, we see that the summands in (31) are
simplified by using the formula

$\frac{(-1/2)_{n}}{n!}\cdot\frac{(-2n-1)_{k}}{k!}\,=\,\frac{(-1)^{n}}{2^{2n}}\cdot\frac{(2n)!}{\left(n!\right)^{2}}\,\cdot\frac{(2n+k)!}{(2n)!\,k!}\,=\,\frac{(-1)^{n+k}}{2^{2n}}\binom{2n+k}{n,n,k}\,.$
(171)

Hence, the left-hand-side of equals (31)

$\sum_{n=0}^{\infty}\frac{(-1/2)_{n}}{n!}\cdot\frac{(-2n-1)_{k}}{k!}\binom{k}{j}(-1)^{n+k}4^{n}=\,\sum_{n=0}^{\infty}\frac{(-1)^{n+k}}{2^{2n}}\binom{2n+k}{n,n,k}\,\binom{k}{j}(-1)^{n+k}4^{n}\,,$
(172)

which may be further simplified using

$\binom{2n+k}{n,n,k}\,\binom{k}{j}\,=\,\binom{2n+k}{n,n,j,k-j}\,.$ (173)

So, the left-hand-side of equals (31) may be rewritten as

$\sum_{n=0}^{\infty}\frac{(-1/2)_{n}}{n!}\cdot\frac{(-2n-1)_{k}}{k!}\binom{k}{j}(-1)^{n+k}4^{n}=\,\sum_{n=0}^{\infty}\binom{2n+k}{n,n,j,k-j}\,.$
(174)

In (31) we wanted to verify that, when we replace $j\leftarrow\ell-n$ and
$k-j\leftarrow m-n$ (using replacement notation as in APL) then we get
$\binom{\ell+m}{\ell,m}\binom{\ell+m}{\ell,m}$. So this equation may be
rewritten as

$\sum_{n=0}^{\infty}\binom{2n+\ell+m}{n,n,\ell-n,m-n}\,=\,\binom{\ell+m}{\ell,m}\binom{\ell+m}{\ell,m}\,.$
(175)

We then take account of the fact that in the multinomial coefficient notation,
the multinomial coefficient equals $0$ unless all the terms in the bottom are
nonnegative integers. So we require $\ell-n\geq 0$ and $m-n\geq 0$. Then the
infinite sum for $n\in\\{0,1,\dots\\}$ may be restricted to
$n\in\\{0,\dots,\min(\ell,m)\\}$. That is how we reduce equation (31) to (32)
or its even more direct version

$\sum_{n=0}^{\min(m,n)}\binom{2n+\ell+m}{n,n,\ell-n,m-n}\,=\,\binom{\ell+m}{\ell,m}\binom{\ell+m}{\ell,m}\,.$
(176)

## References

  * [1] Lars V. Ahlfors.  Complex Analysis. McGraw-Hill Inc., New York, USA, 1979.
  * [2] David Aldous and Persi Diaconis.  Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem.  Bull Amer. Math. Soc. 36, no. 4, 413–432 (1999).
  * [3] Jinho Baik, Percy Deift and Kurt Johansson.  On the distribution of the length of the longest increasing subsequence of random permutations.  J. Amer. Math. Soc. 12, no. 4, 1119–1178 (1999).
  * [4] Charalambos A. Charalambides.  Enumerative Combinatorics.  CRC Press, Taylor & Francis group, Boca Raton, FL, 2002.
  * [5] Duncan Dauvergne, Janosch Ortmann, and Bálint Virág.  The directed landscape.  Preprint, https://arxiv.org/abs/1812.00309
  * [6] Gerald B. Folland.  Real Analysis: Modern Techniques and Their Applications. 2nd Ed. John Wiley & Sons, Inc., New York, USA, 1999.
  * [7] Francesco Guerra.  Broken replica symmetry bounds in the mean field spin glass model.  Commun. Math. Phys. 233 1–12 (2003).
  * [8] Francesco Guerra and Fabio-Lucio Toninelli.  Quadratic replica coupling in the SherringtonKirkpatrick mean field spin glass model.  J. Math. Phys. 43, 3704–3716 (2002).
  * [9] H, M. Hammersley.  A fee seedlings of research.  In: Proc. 6th Berkeley symp. math. statist. and probability, vol.1, pp. 345–394.  University of California Press, California 1972.
  * [10] B. F. Logan and L. A. Shepp.  A variational problem for random Young tableaux.  Advances in Math. 26 206–222 (1977).
  * [11] Marc Mezard, Giorgio Parisi and Miguel-Angel Virasoro.  Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications. World Scientific Publishing Company, Singapore, 1987.
  * [12] Robin Pemantle and Mark C. Wilson.  Analytic Combinatorics in Several Variables. Cambridge University Press, New York, USA, 2013.
  * [13] Ross G. Pinsky.  Law of large numbers for increasing subsequences of random permutations.  Random Structures Algorithms 29, no. 3, 277–295 (2006).
  * [14] Ross G. Pinsky.  When the law of large numbers fails for increasing subsequences of random permutations.  Ann. Probab. 35, no. 2, 758–772 (2007).
  * [15] J. Michael Steele.  Probability theory and combinatorial optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997.
  * [16] Michel Talagrand.  The Parisi formula.  Ann. Math. 163, 221–263 (2006).
  * [17] A. M. Vershik and S. V. Kerov.  Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tables.  Soviet Math. Dokl., 18, 527–531 (1977).
  * [18] J. L. van Hemmen and R. G. Palmer.  J. Phys. A: Math. Gen. 12 563–580 (1979).