# Integrality of the LMOV invariants for framed unknot

Wei Luo, Shengmao Zhu  Center of Mathematical Sciences, Zhejiang University,
Hangzhou, Zhejiang 310027, China<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

The Labastida-Marinõ-Ooguri-Vafa (LMOV) invariants are the open string BPS
invariants which are expected to be integers based on the string duality
conjecture from M-theory. Several explicit formulae of LMOV invariants for
framed unknot have been obtained in the literature. In this paper, we present
a unified method to deal with the integrality of such explicit formulae.
Furthermore, we also prove the integrality of certain LMOV invariants for
framed unknot in higher genera.

##  1\. Introduction

Topological string amplitude is the generating function of Gromov-Witten
invariants which are usually rational numbers according to their definitions
[12]. In 1998, Gopakumar and Vafa [9, 10] found that topological string
amplitude is also the generating function of a series of integer-valued
invariants related to BPS counting in M-theory. Later, Ooguri and Vafa [26]
extended the above result to open string case, the corresponding integer-
valued invariants are named as OV invariants. Furthermore, the OV invariants
are further refined by Labasitida, Mariño and Vafa in [20], then the resulted
invariants are called LMOV invariants [21]. An expanded physicist’s
reconsideration of the GV and LMOV can be found in [4]. We refer to [31] for a
brief review of the applications of these integrality structures of
topological strings in mathematics.

The open string LMOV invariants have been studied in many papers, such as [18,
19, 20, 21, 3, 8, 16, 22, 23, 24, 13, 14]. Based on the large $N$ duality of
topological string and Chern-Simons theory [27, 11, 26], the open string LMOV
invariants can be approached by investigating the colored HOMFLYPT invariants
of the dual knots. For a knot $\mathcal{K}$, we use the notation
$n_{\mu,g,Q}(\mathcal{K})$ to denote the LMOV invariants of genus $g$ with a
boundary type $\mu$ which is a partition of a positive integer, where $Q$ is a
parameter describing the dependence of the relative homology class of the dual
Calabi-Yau geometry of the knot $\mathcal{K}$. We refer to Section 2 for more
detailed definition of $n_{\mu,g,Q}(\mathcal{K})$.

In particular, when the knot $\mathcal{K}$ is a framed unknot $U_{\tau}$ with
framing $\tau\in\mathbb{Z}$, we have different ways to compute its LMOV
invariants according to string dualities which have been proved in this
situation [17, 28, 5]. Then one can obtain several explicit formulae [8, 22]
for the genus zero LMOV invariants $n_{\mu,0,Q}(U_{\tau})$ of framed unknot
$U_{\tau}$. It turns out that these explicit formulae are certain combinations
of the Möbius function and binomial numbers. Based on the integrality
conjecture for LMOV invariants, these formulae will give integers. However,
such an argument is not so obvious, a rigorous proof is required.

In this paper, we present a straightforward way to prove the integrality of
these formulae. We use the notation $n_{m,l}(\tau)$ to denote the LMOV
invariants $n_{(m),0,l-\frac{m}{2}}(U_{\tau})$ of the framed unknot $U_{\tau}$
of genus $0$, where $m\geq 1$ and $l\geq 0$ are two integers. We have the
following explicit formula [25, 22] for $n_{m,l}(\tau)$.

For $b\geq 0$ and $a\in\mathbb{Z}$, we introduce the notation $\binom{a}{b}$
which is defined as follows

$\displaystyle\binom{a}{b}=$ $\displaystyle 1,$ $b=0$,
$\displaystyle\binom{a}{b}=$ $\displaystyle\binom{a}{b},$ $b\geq 1$ and $a\geq
0$,  $\displaystyle\binom{a}{b}=$ $\displaystyle(-1)^{b}\binom{-a+b-1}{b},$
$b\geq 1$ and $a<0$.

We define

$\displaystyle
c_{m,l}(\tau)=-\frac{(-1)^{m\tau+m+l}}{m^{2}}\binom{m}{l}\binom{m\tau+l-1}{m-1},$

then

(2) $\displaystyle
n_{m,l}(\tau)=\sum_{d|m,d|l}\frac{\mu(d)}{d^{2}}c_{\frac{m}{d},\frac{l}{d}}(\tau),$

where $\mu(d)$ denotes the Möbius functions.

In Section 3, we prove that

######  Theorem 1.1.

For any $\tau\in\mathbb{Z}$, $m\geq 1,l\geq 0$, we have
$n_{m,l}(\tau)\in\mathbb{Z}$.

######  Remark 1.2.

In fact, such form of the formula (2) is very general. For example, if we take
some special values of $l$ or $\tau$, it will give the formulae in [8] (cf.
the formulae (1.4) and (1.5) in [8]):

(3) $b_{K_{p},r}^{-}=-\frac{1}{r^{2}}\sum_{d\mid
r}\mu(\frac{r}{d})\binom{3d-1}{d-1},\qquad
b_{K_{p},r}^{+}=\frac{1}{r^{2}}\sum_{d\mid
r}\mu(\frac{r}{d})\binom{(2|p|+1)d-1}{d-1}$

for $p\leq-1$ and

(4) $b_{K_{p},r}^{-}=-\frac{1}{r^{2}}\sum_{d\mid
r}\mu(\frac{r}{d})(-1)^{d+1}\binom{2d-1}{d-1},\qquad
b_{K_{p},r}^{+}=\frac{1}{r^{2}}\sum_{d\mid
r}\mu(\frac{r}{d})(-1)^{d}\binom{(2p+2)d-1}{d-1}$

for $p\geq 2$. The above formulae (3) and (4) are referred as the extremal BPS
invariants of twist knots in [8]. Therefore, Theorem 1.1 implies the
integrality of formulae (3) and (4) immediately. Moreover, the integrality of
another special case of the formula (2) was also proved in [30].

Then, denoted by $n_{(m_{1},m_{2})}(\tau)$ the LMOV invariants
$n_{(m_{1},m_{2}),0,\frac{m_{1}+m_{2}}{2}}(U_{\tau})$ of the framed unknot
$U_{\tau}$ with $\mu=(m_{1},m_{2})$, $g=0$ and $Q=\frac{m_{1}+m_{2}}{2}$,
where $m_{1}\geq m_{2}\geq 1$, we obtain the following formula

(5) $\displaystyle n_{(m_{1},m_{2})}(\tau)$
$\displaystyle=\frac{1}{m_{1}+m_{2}}\sum_{d\mid m_{1},d\mid
m_{2}}\mu(d)(-1)^{(m_{1}+m_{2})(\tau+1)/d}$
$\displaystyle\cdot\binom{(m_{1}\tau+m_{1})/d-1}{m_{1}/d}\binom{(m_{2}\tau+m_{2})/d}{m_{2}/d}.$

From this expression, we know that
$n_{(m_{1},m_{2})}(\tau)=n_{(m_{2},m_{1})}(\tau)$. With the similar method, in
Section 4, we prove that

######  Theorem 1.3.

For any $\tau\in\mathbb{Z}$ and $m_{1},m_{2}\geq 1$, then
$n_{(m_{1},m_{2})}(\tau)\in\mathbb{Z}$.

Next, let $n_{m,g,Q}(\tau)$ be the LMOV invariants $n_{(m),g,Q}(U_{\tau})$ of
higher genus $g$ with boundary condition $\mu=(m)$. We define the following
generating function

$\displaystyle g_{m}(q,a)=\sum_{g\geq
0}\sum_{Q\in\mathbb{Z}/2}n_{m,g,Q}(\tau)z^{2g-2}a^{Q}$

where $z=q^{\frac{1}{2}}-q^{-\frac{1}{2}}$.

Let

$\displaystyle\mathcal{Z}_{m}(q,a)=(-1)^{m\tau}\sum_{|\nu|=m}\frac{1}{\mathfrak{z}_{\nu}}\frac{\\{m\nu\tau\\}}{\\{m\\}\\{m\tau\\}}\frac{\\{\nu\\}_{a}}{\\{\nu\\}}$

where $\mathfrak{z}_{\nu}=|Aut(\nu)|\prod_{i=1}^{l(\nu)}\nu_{i}$ and $\\{m\\}$
denotes the quantum integer, see Section 2 for introduction of the above
notations.

By the definition of LMOV invariants in Section 2, we obtain the following
expression

$\displaystyle g_{m}(q,a)=\sum_{d|m}\mu(d)\mathcal{Z}_{m/d}(q^{d},a^{d}).$

In Section 5, we prove that

######  Theorem 1.4.

For any $m\geq 1$, we have $g_{m}(q,a)\in
z^{-2}\mathbb{Z}[z^{2},a^{\pm\frac{1}{2}}],$ where
$z=q^{\frac{1}{2}}-q^{-\frac{1}{2}}$.

Therefore, Theorem 1.4 implies that $n_{m,g,Q}(\tau)\in\mathbb{Z}$ and
moreover $n_{m,g,Q}(\tau)$ vanishes for large $g$ and $Q$.

Acknowledgements. The authors are grateful to the referees for careful reading
of the paper and valuable comments and suggestions which greatly improved the
presentation of the content.

##  2\. LMOV invariants

###  2.1. Basic notations

We first introduce some basic notations. A partition $\lambda$ is a finite
sequence of positive integers $(\lambda_{1},\lambda_{2},..)$ such that
$\lambda_{1}\geq\lambda_{2}\geq\cdots$. The length of $\lambda$ is the total
number of parts in $\lambda$ and denoted by $l(\lambda)$. The weight of
$\lambda$ is defined by $|\lambda|=\sum_{i=1}^{l(\lambda)}\lambda_{i}$. The
automorphism group of $\lambda$, denoted by Aut($\lambda$), contains all the
permutations that permute parts of $\lambda$ by keeping it as a partition.
Obviously, Aut($\lambda$) has the order
$|\text{Aut}(\lambda)|=\prod_{i=1}^{l(\lambda)}m_{i}(\lambda)!$ where
$m_{i}(\lambda)$ denotes the number of times that $i$ occurs in $\lambda$.
Define
$\mathfrak{z}_{\lambda}=|\text{Aut}(\lambda)|\prod_{i=1}^{\lambda}\lambda_{i}$.

In the following, we will use the notation $\mathcal{P}_{+}$ to denote the set
of all the partitions of positive integers. Let $0$ be the partition of $0$,
i.e. the empty partition. Define $\mathcal{P}=\mathcal{P}_{+}\cup\\{0\\}$.

The power sum symmetric function of infinite variables
$\mathbf{x}=(x_{1},..,x_{N},..)$ is defined by
$p_{n}(\mathbf{x})=\sum_{i}x_{i}^{n}.$ Given a partition $\lambda$, we define
$p_{\lambda}(\mathbf{x})=\prod_{j=1}^{l(\lambda)}p_{\lambda_{j}}(\mathbf{x}).$
The Schur function $s_{\lambda}(\mathbf{x})$ is determined by the Frobenius
formula

$\displaystyle
s_{\lambda}(\mathbf{x})=\sum_{\mu}\frac{\chi_{\lambda}(\mu)}{\mathfrak{z}_{\mu}}p_{\mu}(\mathbf{x}),$

where $\chi_{\lambda}$ is the character of the irreducible representation of
the symmetric group $S_{|\lambda|}$ corresponding to $\lambda$, we have
$\chi_{\lambda}(\mu)=0$ if $|\mu|\neq|\lambda|$. The orthogonality of
character formula gives

$\displaystyle\sum_{\lambda}\frac{\chi_{\lambda}(\mu)\chi_{\lambda}(\nu)}{\mathfrak{z}_{\mu}}=\delta_{\mu\nu}.$

Let $n\in\mathbb{Z}$ and $\lambda,\mu,\nu$ denote the partitions. We introduce
the following notations

$\displaystyle\\{n\\}_{x}=x^{\frac{n}{2}}-x^{-\frac{n}{2}},\
\\{\mu\\}_{x}=\prod_{i=1}^{l(\mu)}\\{\mu_{i}\\}_{x}.$

In particular, let $\\{n\\}=\\{n\\}_{q}$ and $\\{\mu\\}=\\{\mu\\}_{q}$.

###  2.2. LMOV invariants for framed knots

Although the LMOV invariants are determined by the integrality structure of
topological open string partition function. Based on the large $N$ duality of
topological string and Chern-Simons theory [11, 26], one can also introduce
the LMOV invariants through Chern-Simons theory of links/knots [18, 19, 20,
21].

Given a partition $\lambda$, we let
$\kappa_{\lambda}=\sum_{i=1}^{l(\lambda)}\lambda_{i}(\lambda_{i}-2i+1)$. Let
$\mathcal{K}_{\tau}$ be a knot with framing $\tau\in\mathbb{Z}$. The framed
colored HOMFLYPT invariant of $\mathcal{K}_{\tau}$ is defined as follows

$\displaystyle\mathcal{H}_{\lambda}(\mathcal{K}_{\tau};q,a)=(-1)^{|\lambda|\tau}q^{\frac{\kappa_{\lambda}\tau}{2}}W_{\lambda}(\mathcal{K}_{\tau};q,a),$

where $W_{\lambda}(\mathcal{K}_{\tau};q,a)$ is the ordinary (framing-
independent) colored HOMFLYPT invariant of $\mathcal{K}_{\tau}$, we refer to
[29] for the concrete definition of $W_{\lambda}(\mathcal{K}_{\tau};q,a)$.

Let
$\mathcal{Z}_{\mu}(\mathcal{K}_{\tau};q,a)=\sum_{\lambda}\chi_{\lambda}(\mu)\mathcal{H}_{\lambda}(\mathcal{K}_{\tau};q,a),$
the Chern-Simons partition function of $\mathcal{K}_{\tau}$ is defined by

(6) $\displaystyle
Z_{CS}^{(S^{3},\mathcal{K}_{\tau})}(q,a,\mathbf{x})=\sum_{\lambda\in\mathcal{P}}\mathcal{H}_{\lambda}(\mathcal{K}_{\tau};q,a)s_{\lambda}(\mathbf{x})=\sum_{\mu\in\mathcal{P}}\frac{\mathcal{Z}_{\mu}(\mathcal{K}_{\tau};q,a)}{\mathfrak{z}_{\mu}}p_{\mu}(\mathbf{x}).$

Then we define the functions $f_{\lambda}(\mathcal{K}_{\tau};q,a)$ by

$\displaystyle
Z_{CS}^{(S^{3},\mathcal{K}_{\tau})}(q,a,\mathbf{x})=\exp\left(\sum_{d=1}^{\infty}\frac{1}{d}\sum_{\lambda\in\mathcal{P}_{+}}f_{\lambda}(\mathcal{K}_{\tau};q^{d},a^{d})s_{\lambda}(\mathbf{x}^{d})\right).$

Let
$\hat{f}_{\mu}(\mathcal{K}_{\tau};q,a)=\sum_{\lambda}f_{\lambda}(\mathcal{K}_{\tau};q,a)M_{\lambda\mu}(q)^{-1},$
where

$\displaystyle
M_{\lambda\mu}(q)=\sum_{\mu}\frac{\chi_{\lambda}(C_{\nu})\chi_{\mu}(C_{\nu})}{\mathfrak{z}_{\nu}}\prod_{j=1}^{l(\nu)}(q^{\nu_{j}/2}-q^{-\nu_{j}/2}).$

Denote $z=q^{\frac{1}{2}}-q^{-\frac{1}{2}}$, then the LMOV conjecture for
framed knot $\mathcal{K}_{\tau}$ stated that [25], for any
$\mu\in\mathcal{P}_{+}$, there are integers $N_{\mu,g,Q}(\mathcal{K}_{\tau})$
such that

$\displaystyle\hat{f}_{\mu}(\mathcal{K}_{\tau};q,a)=\sum_{g\geq
0}\sum_{Q\in\mathbb{Z}/2}N_{\mu,g,Q}(\mathcal{K}_{\tau})z^{2g-2}a^{Q}\in
z^{-2}\mathbb{Z}[z^{2},a^{\pm\frac{1}{2}}].$

Therefore,

$\displaystyle g_{\mu}(\mathcal{K}_{\tau};q,a)$
$\displaystyle=\sum_{\nu}\chi_{\nu}(\mu)\hat{f}_{\nu}(\mathcal{K}_{\tau};q,a)$
$\displaystyle=\sum_{g\geq
0}\sum_{Q\in\mathbb{Z}/2}n_{\mu,g,Q}(\mathcal{K}_{\tau})z^{2g-2}a^{Q}\in
z^{-2}\mathbb{Z}[z^{2},a^{\pm\frac{1}{2}}].$

where
$n_{\mu,g,Q}(\mathcal{K}_{\tau})=\sum_{\nu}\chi_{\nu}(\mu)N_{\nu,g,Q}(\mathcal{K}_{\tau})$.
These conjectural integers $n_{\mu,g,Q}(\mathcal{K}_{\tau})$ ( and
$N_{\nu,g,Q}(\mathcal{K}_{\tau})$) are referred to as the LMOV invariants in
this paper. We refer to [8, 16, 13, 14] for another slightly different
introduction of LMOV invariants which are referred to as OV invariants in
[30]. The integrality of certain OV invariants for a large family of
knots/links have been proved in [13, 14] recently by using the knots-quivers
correspondence.

In order to get an explicit expression for $g_{\mu}(\mathcal{K}_{\tau};q,a)$,
we introduce $F_{\mu}(\mathcal{K}_{\tau};q,a)$ through the following expansion
formula

$\displaystyle\log(Z_{CS}^{(S^{3},\mathcal{K}_{\tau})}(q,a,\mathbf{x}))=\sum_{\mu\in\mathcal{P}_{+}}F_{\mu}(\mathcal{K}_{\tau};q,a)p_{\mu}(\mathbf{x}).$

Then, by formula (6), we have

$\displaystyle F_{\mu}(\mathcal{K}_{\tau};q,a)=\sum_{n\geq
1}\sum_{\cup_{i=1}^{n}\nu^{i}=\mu}\frac{(-1)^{n-1}}{n}\prod_{i=1}^{n}\frac{\mathcal{Z}_{\nu^{i}}(\mathcal{K}_{\tau};q,a)}{\mathfrak{z}_{\nu^{i}}}.$

######  Remark 2.1.

For two partitions $\nu^{1}$ and $\nu^{2}$, the notation $\nu^{1}\cup\nu^{2}$
denotes the new partition obtained by combining all the parts in
$\nu^{1},\nu^{2}$. For example, if $\mu=(2,2,1)$, then the list of all the
pairs $(\nu^{1},\nu^{2})$ such that $\nu^{1}\cup\nu^{2}=(2,2,1)$ is

$\displaystyle(\nu^{1}=(2),\nu^{2}=(2,1)),\ (\nu^{1}=(2,1),\nu^{2}=(2)),$
$\displaystyle\ (\nu^{1}=(1),\nu^{2}=(2,2)),\ (\nu^{1}=(2,2),\nu^{2}=(1)).\ $

Finally, by using the Möbius inversion formula, we obtain

(7) $\displaystyle
g_{\mu}(\mathcal{K}_{\tau};q,a)=\mathfrak{z}_{\mu}\frac{1}{\\{\mu\\}}\sum_{d|\mu}\frac{\mu(d)}{d}F_{\mu/d}(\mathcal{K}_{\tau};q^{d},a^{d}).$

######  Remark 2.2.

In the above discussion, for the sake of brevity, we only consider the case of
a framed knot, actually, the LMOV invariants can be defined for any framed
link.

###  2.3. LMOV invariants for framed unknot $U_{\tau}$

In the following, we only consider the case of a framed unknot $U_{\tau}$. In
this situation, the large $N$ duality of topological string and Chern-Simons
theory [25] has been proved in [17, 28]. Therefore, we can also compute the
LMOV invariants for framed unknot $U_{\tau}$ through the open topological
string theory.

We denote by $n_{m,l}(\tau)$ the LMOV invariants
$n_{(m),0,l-\frac{m}{2}}(U_{\tau})$ of the framed unknot $U_{\tau}$, where
$g=0$ and $m\geq 1$, $l\geq 0$. According to the computations shown in [25] (
or cf. pages 15-16 in [22]), the explicit closed formula for $n_{m,l}(\tau)$
is given by formula (2). The integrality of $n_{m,l}(\tau)$ is given by
Theorem 1.1.

Then, denoted by $n_{(m_{1},m_{2})}(\tau)$ the LMOV invariants
$n_{(m_{1},m_{2}),0,\frac{m_{1}+m_{2}}{2}}(U_{\tau})$ of the framed unknot
$U_{\tau}$ with $\mu=(m_{1},m_{2})$, $g=0$ and $Q=\frac{m_{1}+m_{2}}{2}$,
where $m_{1}\geq m_{2}\geq 1$. By using the computations in open topological
string theory (cf. pages 18-19 in [22]), we obtain the explicit closed formula
for $n_{(m_{1},m_{2})}(\tau)$ which is given by formula (5). The integrality
of $n_{(m_{1},m_{2})}(\tau)$ is given by Theorem 1.3.

Let $n_{m,g,Q}(\tau)$ be the LMOV invariants $n_{(m),g,Q}(U_{\tau})$ of the
framed unknot $U_{\tau}$. We consider the following generating function

$\displaystyle g_{m}(q,a)=\sum_{g\geq
0}\sum_{Q\in\mathbb{Z}/2}n_{m,g,Q}(\tau)z^{2g-2}a^{Q}$

which can be computed by using formula (7). Considering the following function

$\displaystyle\phi_{\mu,\nu}(x)=\sum_{\lambda}\chi_{\lambda}(\mu)\chi_{\lambda}(\nu)x^{\kappa_{\lambda}}.$

By Lemma 5.1 in [3], for $d\in\mathbb{Z}_{+}$, we have

(8)
$\displaystyle\phi_{(d),\nu}(x)=\frac{\\{d\nu\\}_{x^{2}}}{\\{d\\}_{x^{2}}}.$

By the expression of colored HOMFLYPT invariant for unknot (cf. formula (4.6)
in [21])

$\displaystyle
W_{\lambda}(U;q,a)=\sum_{\nu}\frac{\chi_{\lambda}(\nu)}{\mathfrak{z}_{\nu}}\frac{\\{\nu\\}_{a}}{\\{\nu\\}},$

we obtain

$\displaystyle\mathcal{Z}_{\mu}(U_{\tau};q,a)$
$\displaystyle=\sum_{\lambda}\chi_{\lambda}(\mu)\mathcal{H}_{\lambda}(U_{\tau};q,a)$
$\displaystyle=(-1)^{|\mu|\tau}\sum_{\lambda}\chi_{\lambda}(\mu)q^{\frac{\kappa_{\lambda}\tau}{2}}\sum_{\nu}\frac{\chi_{\lambda}(\nu)}{\mathfrak{z}_{\nu}}\frac{\\{\nu\\}_{a}}{\\{\nu\\}}$
$\displaystyle=(-1)^{|\mu|\tau}\sum_{\nu}\frac{1}{\mathfrak{z}_{\nu}}\phi_{\mu,\nu}(q^{\frac{\tau}{2}})\frac{\\{\nu\\}_{a}}{\\{\nu\\}}.$

In particular, for $\mu=(m)$ with $m\geq 1$, formula (8) implies that

$\displaystyle\mathcal{Z}_{(m)}(U_{\tau};q,a)=(-1)^{m\tau}\sum_{|\nu|=m}\frac{1}{\mathfrak{z}_{\nu}}\frac{\\{m\nu\tau\\}}{\\{m\tau\\}}\frac{\\{\nu\\}_{a}}{\\{\nu\\}}.$

For brevity, if we let

$\displaystyle\mathcal{Z}_{m}(q,a)=\frac{1}{\\{m\\}}\mathcal{Z}_{(m)}(U_{\tau};q,a)=(-1)^{m\tau}\sum_{|\nu|=m}\frac{1}{\mathfrak{z}_{\nu}}\frac{\\{m\nu\tau\\}}{\\{m\\}\\{m\tau\\}}\frac{\\{\nu\\}_{a}}{\\{\nu\\}},$

then formula (7) gives

(9) $\displaystyle g_{m}(q,a)=\sum_{d|m}\mu(d)\mathcal{Z}_{m/d}(q^{d},a^{d}).$

Theorem 1.4 shows that $g_{m}(q,a)\in
z^{-2}\mathbb{Z}[z^{2},a^{\pm\frac{1}{2}}]$ for any $m\geq 1$.

##  3\. Proof of the Theorem 1.1

For nonnegative integer $n$ and prime number $p$, we introduce the following
function

(10) $f_{p}(n)=\prod_{i=1,p\nmid i}^{n}i=\frac{n!}{p^{[n/p]}[n/p]!}.$

Given a positive integer $k$, throughout this paper, we use the notation
$p^{k}\mid\mid n$ to denote that $p^{k}$ divides $n$, but $p^{k+1}$ does not.

Before giving the proof of Theorem 1.1, we first establish several useful
lemmas.

######  Lemma 3.1.

For odd prime numbers $p$ and $\alpha\geq 1$ or for $p=2$, $\alpha\geq 2$, we
have $p^{2\alpha}\mid f_{p}(p^{\alpha}n)-f_{p}(p^{\alpha})^{n}$. For
$p=2,\alpha=1$, $f_{2}(2n)\equiv(-1)^{[n/2]}\pmod{4}$ .

###### Proof.

With $\alpha\geq 2$ or $p>2$, $p^{\alpha-1}(p-1)$ is even,

$\displaystyle f_{p}(p^{\alpha}n)-f_{p}(p^{\alpha}(n-1))f_{p}(p^{\alpha})$
$\displaystyle=f_{p}(p^{\alpha}(n-1))\left(\prod_{i=1,p\nmid
i}^{p^{\alpha}}(p^{\alpha}(n-1)+i)-f_{p}(p^{\alpha})\right)$
$\displaystyle\equiv
p^{\alpha}(n-1)f_{p}(p^{\alpha}(n-1))f_{p}(p^{\alpha})\left(\sum_{i=1,p\nmid
i}^{p^{\alpha}}\frac{1}{i}\right)\pmod{p^{2\alpha}}$ $\displaystyle\equiv
p^{\alpha}(n-1)f_{p}(p^{\alpha}(n-1))f_{p}(p^{\alpha})\left(\sum_{i=1,p\nmid
i}^{[p^{\alpha}/2]}(\frac{1}{i}+\frac{1}{p^{\alpha}-i})\right)\pmod{p^{2\alpha}}$
$\displaystyle\equiv
p^{\alpha}(n-1)f_{p}(p^{\alpha}(n-1))f_{p}(p^{\alpha})\left(\sum_{i=1,p\nmid
i}^{[p^{\alpha}/2]}\frac{p^{\alpha}}{i(p^{\alpha}-i)}\right)\equiv
0,\pmod{p^{2\alpha}}$

Thus the first part of the Lemma 3.1 is proved by induction. For
$p=2,\alpha=1$, the formula is straightforward. ∎

######  Lemma 3.2.

For odd prime number $p$ and $m=p^{\alpha}a,l=p^{\beta}b$, $p\nmid a,p\nmid
b$, $\alpha\geq 1,\beta\geq 0$, we have

$p^{2\alpha}\mid\binom{m}{l}\binom{m\tau+l-1}{m-1}-\binom{\frac{m}{p}}{\frac{l}{p}}\binom{\frac{m\tau+l}{p}-1}{\frac{m}{p}-1}$

where for $\beta=0$, the second term is defined to be zero.

###### Proof.

$\displaystyle\binom{m}{l}\binom{m\tau+l-1}{m-1}-\binom{\frac{m}{p}}{\frac{l}{p}}\binom{\frac{m\tau+l}{p}-1}{\frac{m}{p}-1}$
(11)
$\displaystyle=\binom{\frac{m}{p}}{\frac{l}{p}}\binom{\frac{m\tau+l}{p}-1}{\frac{m}{p}-1}\left(\frac{f_{p}(m)}{f_{p}(l)f_{p}(m-l)}\cdot\frac{f_{p}(m\tau+l)}{f_{p}(m)f_{p}(m(\tau-1)+l)}-1\right)$

Write
$\binom{\frac{m}{p}}{\frac{l}{p}}=\frac{m}{l}\binom{\frac{m}{p}-1}{\frac{l}{p}-1}$
and
$\binom{\frac{m\tau+l}{p}-1}{\frac{m}{p}-1}=\frac{m}{m\tau+l}\binom{\frac{m\tau+l}{p}}{\frac{m}{p}}$,
both are divisible by $p^{\max(\alpha-\beta,0)}$. Each element of
$\\{m,l,m-l,m\tau+l,m(\tau-1)+l\\}$ is divisible by $p^{\min(\alpha,\beta)}$,
so by Lemma 3.1,

(12)
$\frac{f_{p}(m)}{f_{p}(l)f_{p}(m-l)}\cdot\frac{f_{p}(m\tau+l)}{f_{p}(m)f_{p}(m(\tau-1)+l)}-1$

is divisible by $p^{2\min(\alpha,\beta)}$ (including the case $\beta=0$) in
$p$-adic number field. Thus (11) is divisible by
$p^{2\max(\alpha-\beta,0)+2\min(\alpha,\beta)}=p^{2\alpha}$. ∎

######  Lemma 3.3.

For $m=2^{\alpha}a,l=2^{\beta}b,\alpha\geq 1,\beta\geq 0$,

$2^{2\alpha}\mid(-1)^{m\tau+m+l}\binom{m}{l}\binom{m\tau+l-1}{m-1}-(-1)^{\frac{m\tau+m+l}{2}}\binom{\frac{m}{2}}{\frac{l}{2}}\binom{\frac{m\tau+l}{2}-1}{\frac{m}{2}-1},$

where the second term is set to zero for $\beta=0$.

###### Proof.

For the case $\alpha\geq 2,\beta\geq 2$, both $m\tau+m+l$ and $(m\tau+m+l)/2$
are even, the Lemma is proved as in Lemma 3.2. For the case $\beta=0$, both
$\binom{m}{l}$ and $\binom{m\tau+l-1}{m-1}$ are divisible by $2^{\alpha}$, and
the Lemma is also proved. For remaining cases $\alpha>\beta=1$ or
$\beta\geq\alpha=1$, we compute similarly as (11),

$\displaystyle(-1)^{m\tau+m+l}\binom{m}{l}\binom{m\tau+l-1}{m-1}-(-1)^{\frac{m\tau+m+l}{2}}\binom{\frac{m}{2}}{\frac{l}{2}}\binom{\frac{m\tau+l}{2}-1}{\frac{m}{2}-1}$
(13)
$\displaystyle=\binom{\frac{m}{2}}{\frac{l}{2}}\binom{\frac{m\tau+l}{2}-1}{\frac{m}{2}-1}\left(\frac{f_{2}(m)}{f_{2}(l)f_{2}(m-l)}\cdot\frac{f_{2}(m\tau+l)}{f_{2}(m(\tau-1)+l)f_{2}(m)}-(-1)^{\frac{m\tau+m+l}{2}}\right)$

Both $\binom{\frac{m}{2}}{\frac{l}{2}}$ and
$\binom{\frac{m\tau+l}{2}-1}{\frac{m}{2}-1}$ are divisible by $2^{\alpha-1}$,
it suffices to prove that the third factor is divisible by $4$, which is, by
Lemma 3.1,

$(-1)^{[\frac{l}{4}]+[\frac{m-l}{4}]+[\frac{m\tau+l}{4}]+[\frac{m(\tau-1)+l}{4}]}-(-1)^{\frac{m\tau+m+l}{2}}.\pmod{4}$

It is divisible by $4$ if

(14)
$[\frac{l}{4}]+[\frac{m-l}{4}]+[\frac{m\tau+l}{4}]+[\frac{m(\tau-1)+l}{4}]+\frac{m\tau+m+l}{2}$

is even. Parity of (14) depends only on $\tau\pmod{2}$. For $\tau=1$, (14)
reduces to $[l/4]+[(m-l)/4]+[(m+l)/4]+[l/4]+l/2$. For $\tau=0$, it reduces to
$[l/4]+[(m-l)/4]+[l/4]+[(l-m)/4]+(m+l)/2$. Both are obviously even.

∎

Now, we can finish the proof of Theorem 1.1.

###### Proof.

For a prime number $p\mid m$, write $m=p^{\alpha}a,p\nmid a$.

$\displaystyle n_{m,l}(\tau)$ $\displaystyle=\sum_{d\mid m,d\mid
l}\frac{\mu(d)}{d^{2}}c_{\frac{m}{d},\frac{l}{d}}(\tau)$
$\displaystyle=\frac{1}{m^{2}}\sum_{d\mid m,d\mid
l}\mu(d)(-1)^{\frac{m\tau+m+l}{d}}\binom{\frac{m}{d}}{\frac{l}{d}}\binom{\frac{m\tau+l}{d}-1}{\frac{m}{d}-1}$
(15) $\displaystyle=\frac{1}{m^{2}}\sum_{d\mid m,d\mid l,p\nmid
d}\mu(d)\left((-1)^{\frac{m\tau+m+l}{d}}\binom{\frac{m}{d}}{\frac{l}{d}}\binom{\frac{m\tau+l}{d}-1}{\frac{m}{d}-1}-(-1)^{\frac{m\tau+m+l}{dp}}\binom{\frac{m}{dp}}{\frac{l}{dp}}\binom{\frac{m\tau+l}{dp}-1}{\frac{m}{dp}-1}\right)$

where for $pd\nmid l$, the second term of (15) is understood to be zero. For
odd prime number $p$, $\frac{m\tau+m+l}{d}$ and $\frac{m\tau+m+l}{dp}$ have
the same parity. Since $p^{\alpha}\mid\mid\frac{m}{d}$, $p^{2\alpha}$ divides
the summand in (15) by Lemma 3.2. For $p=2$, it is divisible by $2^{2\alpha}$
by Lemma 3.3.

$p^{2\alpha}$ divides the sum in (15) for every $p^{\alpha}\mid\mid m$, thus
$n_{m,l}$ is an integer. ∎

##  4\. Proof of the Theorem 1.3

We introduce the following lemma first.

######  Lemma 4.1.

If $p^{\beta}\mid\mid(a,b),p^{\alpha}\mid a+b$, then $p^{\alpha-\beta}$
divides

$\binom{a\tau+a-1}{a}\binom{b\tau+b}{b}.$

###### Proof.

Power of prime $p$ in $n!$ is $\sum_{k=1}^{\infty}[\frac{n}{p^{k}}].$ Apply
this to the binomial coefficients to find that the power of $p$ in
$\binom{a\tau+a-1}{a}\binom{b\tau+b}{b}$ is

$\displaystyle\sum_{i=1}^{\infty}\left([\frac{a\tau+a-1}{p^{i}}]+[\frac{b\tau+b}{p^{i}}]\right)-\left([\frac{a\tau-1}{p^{i}}]+[\frac{b\tau}{p^{i}}]\right)-\left([\frac{a}{p^{i}}]+[\frac{b}{p^{i}}]\right)$
$\displaystyle\geq\sum_{i=1}^{\alpha}\left((\frac{(a+b)(\tau+1)}{p^{i}}-1)-(\frac{(a+b)\tau}{p^{i}}-1)\right)-\sum_{i=1}^{\beta}(\frac{a+b}{p^{i}})-\sum_{i=\beta+1}^{\alpha}(\frac{a+b}{p^{i}}-1)$
$\displaystyle=\alpha-\beta$

where we use the fact that for $k\mid m+n+1,k>1$, $[m/k]+[n/k]=(m+n+1)/k-1$
and for $k\mid m+n,k\nmid m$, $[m/k]+[n/k]=(m+n)/k-1$. ∎

Recall the definition of the function $f_{p}(n)$ given by formula (10). It is
obvious that

(16) $f_{p}(p^{\alpha}k)\equiv
f_{p}(p^{\alpha})^{k}\equiv(-1)^{k}\pmod{p^{\alpha}}$

Now, we can finish the proof of Theorem 1.3:

###### Proof.

By definition,

$\displaystyle n_{(m_{1},m_{2})}(\tau)$
$\displaystyle=\frac{1}{m_{1}+m_{2}}\sum_{d\mid m_{1},d\mid
m_{2}}\mu(d)(-1)^{(m_{1}+m_{2})(\tau+1)/d}$ (17)
$\displaystyle\cdot\binom{(m_{1}\tau+m_{1})/d-1}{m_{1}/d}\binom{(m_{2}\tau+m_{2})/d}{m_{2}/d}$

Let $p$ be any prime divisor of $m_{1}+m_{2}$, $p^{\alpha}\mid\mid
m_{1}+m_{2}$. We will prove $p^{\alpha}$ divides the summation in (17), thus
$m_{1}+m_{2}$ also divides and $n_{m_{1},m_{2}}$ are integers.

If $p\nmid m_{1}$, each summand in (17) corresponds to $p\nmid d$, so
$p^{\alpha}\mid(m_{1}+m_{2})/d$ and $p\nmid m_{1}/d$. By Lemma 4.1 applied to
$a=m_{1}/d,b=m_{2}/d$, $p^{\alpha}$ divides each summand and thus the
summation.

If $p^{\beta}\mid\mid m_{1},\beta\geq 1$, consider two summands in (17)
corresponding to $d$ and $pd$ such that $pd\mid(m_{1},m_{2}),\mu(pd)\neq 0$.
When $p$ is an odd prime or $\alpha\geq 2$, the sign
$(-1)^{(m_{1}+m_{2})(\tau+1)/d}$ and $(-1)^{(m_{1}+m_{2})(\tau+1)/(pd)}$ are
equal. When $p=2,\alpha=1$, modulo 2 the sign is irrelevant. Write
$a=m_{1}/d,b=m_{2}/d$, then $p^{\alpha}\mid a+b,p^{\beta}\mid\mid a$.

$\displaystyle\binom{a\tau+a-1}{a}\binom{b\tau+b}{b}-\binom{(a\tau+a)/p-1}{a/p}\binom{(b\tau+b)/p}{b/p}$
$\displaystyle=\binom{(a\tau+a)/p-1}{a/p}\binom{(b\tau+b)/p}{b/p}\left(\frac{f_{p}(a\tau+a)f_{p}(b\tau+b)}{f_{p}(a\tau)f_{p}(a)f_{p}(b\tau)f_{p}(b)}-1\right)$
(18)
$\displaystyle=\binom{(a\tau+a)/p-1}{a/p}\binom{(b\tau+b)/p}{b/p}\frac{f_{p}(a\tau+a)f_{p}(b\tau+b)-f_{p}(a\tau)f_{p}(a)f_{p}(b\tau)f_{p}(b)}{f_{p}(a\tau)f_{p}(a)f_{p}(b\tau)f_{p}(b)}$

The term $\binom{(a\tau+a)/p-1}{a/p}\binom{(b\tau+b)/p}{b/p}$ is divisible by
$p^{\alpha-\beta}$ by Lemma 4.1. The numerator of the fraction term in (18) is
divisible by $p^{\beta}$ by (16), and the denominator is not divisible by $p$.
We proved that $p^{\alpha}$ divides (18), take summation over $d$, we get that
$p^{\alpha}$ divides the summation in (17). This is true for any $p\mid
m_{1}+m_{2}$, thus $n_{(m_{1},m_{2})}(\tau)$ is an integer. ∎

##  5\. Proof of the Theorem 1.4

We establish several lemmas first.

######  Lemma 5.1.

Suppose $k$ is a positive integer, then the number

$c_{m}(k,y)=\sum_{|\lambda|=m}\frac{1}{\mathfrak{z}_{\lambda}}k^{l(\lambda)}\\{\lambda\\}_{y^{2}}$

is equal to the coefficient of $t^{m}$ in $(\frac{1-t/y}{1-ty})^{k}$.

###### Proof.

Suppose the number of $i$’s in the partition $\lambda$ is $a_{i},i=1,\cdots$.
Then

$\displaystyle c_{m}(k,y)$ $\displaystyle=\sum_{\sum
ia_{i}=m}\prod_{i}\frac{1}{a_{i}!i^{a_{i}}}k^{a_{i}}(y^{i}-y^{-i})^{a_{i}}$
$\displaystyle=\left[\prod_{i=1}^{\infty}\left(\sum_{j=0}^{\infty}t^{ij}\frac{1}{j!i^{j}}k^{j}(y^{i}-y^{-i})^{j}\right)\right]_{t^{m}}$
$\displaystyle=\left[\prod_{i=1}^{\infty}\exp(t^{i}k(y^{i}-y^{-i})/i)\right]_{t^{m}}$
$\displaystyle=\left[\exp(k\ln(1-ty)^{-1}+k\ln(1-t/y))\right]_{t^{m}}$
$\displaystyle=\left[(\frac{1-t/y}{1-ty})^{k}\right]_{t^{m}}$

∎

######  Lemma 5.2.

Let $R=\mathbb{Q}[q^{\pm 1/2},a^{\pm 1/2}]$. Then

(19) $\displaystyle\\{m\\}\\{m\tau\\}g_{m}(q,a)=\sum_{d\mid
m}\sum_{|\mu|=m/d}\frac{\mu(d)(-1)^{m\tau/d}}{\mathfrak{z}_{\mu}}\frac{\\{m\mu\tau\\}}{\\{d\mu\\}}\\{d\mu\\}_{a}$

is divisible by $\\{m\tau\\}\\{m\\}/\\{1\\}^{2}$ in $R$.

###### Proof.

By the definition (9) of $g_{m}(q,a)$, we have the formula (19). It is clear
that

$\\{m\\}\\{m\tau\\}g_{m}(q,a)\in R.$

Denote $\Phi_{n}(q)=\prod_{d\mid n}(q^{d}-1)^{\mu(n/d)}$ to be the $n$-th
cyclotomic polynomial, which is irreducible over $R$. Then
$q^{n}-1=\prod_{d\mid n}\Phi_{d}(q)$, and

(20) $\displaystyle\\{m\\}\\{m\tau\\}$
$\displaystyle=q^{-\frac{m+m\tau}{2}}\prod_{{m_{1}}\mid
m}\Phi_{m_{1}}(q)\prod_{{m_{1}}\mid m\tau}\Phi_{m_{1}}(q)$
$\displaystyle=q^{-\frac{m+m\tau}{2}}\prod_{{m_{1}}\mid
m}\Phi_{m_{1}}(q)^{2}\prod_{{m_{1}}\mid m\tau,{m_{1}}\nmid m}\Phi_{m_{1}}(q)$

(i) For $m_{1}\mid m\tau,m_{1}\nmid m$, and any $|\mu|=m/d$, at least one of
$d\mu_{i}$’s are not divisible by $m_{1}$, thus
$\\{m\mu_{i}\tau\\}/\\{d\mu_{i}\\}$ is divisible by $\Phi_{m_{1}}(q)$. So
$\Phi_{m_{1}}(q)$ divides $\\{m\\}\\{m\tau\\}g_{m}(q,a)$.

(ii) For $m_{1}\mid m$ and any $|\mu|=m/d$, if not all $d\mu_{i}$ are
divisible by $m_{1}$, then at least two of them are not divisible. Then two of
corresponding $\\{m\mu_{i}\tau\\}/\\{d\mu_{i}\\}$ are divisible by
$\Phi_{m_{1}}(q)$.

We consider modulo $\\{m_{1}\\}^{2}$ in the ring $R$. It is easy to see, for
$a,b\geq 1$,

$\displaystyle\frac{\\{abm_{1}\\}}{\\{bm_{1}\\}}\equiv
a\left(\frac{q^{m_{1}/2}+q^{-m_{1}/2}}{2}\right)^{(a-1)b}\pmod{\\{m_{1}\\}^{2}}$

We write $x=(q^{m_{1}/2}+q^{-m_{1}/2})/2$, then $x^{2}\equiv
1\pmod{\\{m_{1}\\}^{2}}$.

Then modulo $\Phi_{m_{1}}(q)^{2}$, we have

$\displaystyle\\{m\\}\\{m\tau\\}g_{m}(q,a)$ $\displaystyle\equiv\sum_{d\mid
m}\sum_{|\mu|=m/d,m_{1}\mid
d\mu}\frac{\mu(d)(-1)^{m\tau/d}}{\mathfrak{z}_{\mu}}\frac{\\{m\mu\tau\\}}{\\{d\mu\\}}\,\\{d\mu\\}_{a}$
$\displaystyle\equiv\sum_{d\mid m}\sum_{|\mu|=m/d,m_{1}\mid
d\mu}\frac{\mu(d)(-1)^{m\tau/d}}{\mathfrak{z}_{\mu}}\left(\frac{m\tau}{d}\right)^{l(\mu)}x^{(m|\mu|\tau-d|\mu|)/m_{1}}\\{d\mu\\}_{a}$
$\displaystyle\equiv\sum_{d\mid
m}\sum_{|\lambda|=m/\mathrm{lcm}(d,m_{1})}\mu(d)(-1)^{m\tau/d}x^{\frac{m}{m_{1}}(\frac{m\tau}{d}-1)}\cdot\frac{1}{\mathfrak{z}_{\lambda}}\left(\frac{m\tau}{\mathrm{lcm}(d,m_{1})}\right)^{l(\lambda)}\\{\lambda\\}_{a^{\mathrm{lcm}(d,m_{1})}}$
(21) $\displaystyle\equiv\sum_{d\mid
m}\mu(d)(-1)^{m\tau/d}x^{\frac{m}{m_{1}}(\frac{m\tau}{d}-1)}\left[\left(\frac{1-t^{\mathrm{lcm}(d,m_{1})}a^{-\mathrm{lcm}(d,m_{1})/2}}{1-t^{\mathrm{lcm}(d,m_{1})}a^{\mathrm{lcm}(d,m_{1})/2}}\right)^{m\tau/\mathrm{lcm}(d,m_{1})}\right]_{t^{m}}$

  * •

For the cases $m_{1}$ with an odd prime factor $p$, or $p=2$ divides $m_{1}$
and $4\mid m$, or $p=2$ divides $m_{1}$ and $2\mid\tau$: Consider those $d$
with $\mu(d)\neq 0$ and $p\nmid d$, we have
$\mathrm{lcm}(d,m_{1})=\mathrm{lcm}(pd,m_{1})$ and parity of $m\tau/d$ equals
parity of $m\tau/(pd)$, but $\mu(d)=-\mu(pd)$. Thus two terms in (21)
corresponding to $d$ and $pd$ cancelled.

  * •

For the remaining case $2\mid\mid m,m_{1}=2,2\nmid\tau$:
$\Phi_{m_{1}}(q)^{2}=(q^{1/2}+q^{-1/2})^{2}=2x+2$. Coefficients of $x$ in (21)
equals sum of terms corresponds to odd $d\mid m,\mu(d)\neq 0$, while constant
term coefficient equals to sum of terms corresponds to $2d\mid m,\mu(2d)\neq
0$. The coefficients of term for $d$ and $2d$ match, so (21) is divisible by
$x+1$.

In summary, we have proved that for $m_{1}\mid m\tau,m_{1}\nmid m$,
$\Phi_{m_{1}}(q)$ divides $\\{m\\}\\{m\tau\\}g_{m}(q,a)$; for $m_{1}\mid
m,m_{1}\neq 1$, $\Phi_{m_{1}}(q)^{2}$ divides $\\{m\\}\\{m\tau\\}g_{m}(q,a)$.
By (20), the lemma is proved. ∎

######  Lemma 5.3.

For any integer $m\geq 1$, we have

$\displaystyle g_{m}(q,a)\in z^{-2}\mathbb{Q}[z^{2},a^{\pm\frac{1}{2}}].$

###### Proof.

By Lemma 5.2, we have

$\displaystyle
f(q,a):=z^{2}g_{m}(q,a)=\frac{\\{1\\}^{2}}{\\{m\\}\\{m\tau\\}}\sum_{d\mid
m}\sum_{|\mu|=m/d}\frac{\mu(d)(-1)^{m\tau/d}}{\mathfrak{z}_{\mu}}\frac{\\{m\mu\tau\\}}{\\{d\mu\\}}\\{d\mu\\}_{a}\in\mathbb{Q}[q^{\pm\frac{1}{2}},a^{\pm
1}].$

As a function of $q$, it is clear $f(q,a)$ admits $f(q,a)=f(q^{-1},a).$
Furthermore, for any $d|m$ and $|\mu|=m/d$, we have

$\displaystyle m|\mu|\tau-d|\mu|-m\tau-m\equiv
m^{2}\tau/d-m\tau=m\tau(m/d-1)\equiv 0\pmod{2},$

which implies $f(q,a)=f(-q,a).$ Therefore,
$f(q,a)=z^{2}g_{m}(q,a)\in\mathbb{Q}[z^{2},a^{\pm\frac{1}{2}}]$. The lemma is
proved. ∎

######  Lemma 5.4.

For any $\tau\in\mathbb{Z}$, we have

(22)
$\displaystyle\\{m\\}\\{m\tau\\}\mathcal{Z}_{m}(q,a)\in\mathbb{Z}[q^{\pm\frac{1}{2}},a^{\pm\frac{1}{2}}].$

###### Proof.

Since

$\displaystyle(-1)^{m\tau}\\{m\\}\\{m\tau\\}\mathcal{Z}_{m}(q,a)$
$\displaystyle=\sum_{|\mu|=m}\frac{\\{m\tau\mu\\}}{\mathfrak{z}_{\mu}\\{\mu\\}}\\{\mu\\}_{a}$
$\displaystyle=\sum_{\sum_{j\geq 1}jk_{j}=m}\frac{\prod_{j\geq 1}(\\{m\tau
j\\}\\{j\\}_{a})^{k_{j}}}{\prod_{j\geq 1}j^{k_{j}}k_{j}!},$

we construct a generating function

(23) $\displaystyle f(x)$ $\displaystyle=\sum_{n\geq 0}x^{n}\sum_{\sum_{j\geq
1}jk_{j}=n}\frac{\prod_{j\geq 1}(\\{m\tau
j\\}\\{j\\}_{a})^{k_{j}}}{\prod_{j\geq 1}j^{k_{j}}k_{j}!}$
$\displaystyle=\sum_{n\geq 0}\sum_{\sum_{j\geq 1}jk_{j}=n}\frac{\prod_{j\geq
1}(\\{m\tau j\\}\\{j\\}_{a}x^{j})^{k_{j}}}{\prod_{j\geq 1}j^{k_{j}}k_{j}!}$
$\displaystyle=\exp\left(\sum_{j\geq 1}\frac{\\{m\tau
j\\}\\{j\\}_{a}x^{j}}{j\\{j\\}}\right),$

Then
$(-1)^{m\tau}\\{m\\}\\{m\tau\\}\mathcal{Z}_{m}(q,a)=\left[f(x)\right]_{x^{m}}.$

For $\tau=0$, it is the trivial case.

For $\tau\geq 1$, we use the expansion $\frac{\\{m\tau
j\\}}{\\{j\\}}=\sum_{k=0}^{m\tau-1}q^{\frac{j(m\tau-2k-1)}{2}}$, then

$\displaystyle f(x)$ $\displaystyle=\exp\left(\sum_{k\geq
0}^{m\tau-1}\sum_{j\geq
1}\left(\frac{(q^{\frac{m\tau-1-2k}{2}}a^{\frac{1}{2}}x)^{j}}{j}-\frac{(q^{\frac{m\tau-1-2k}{2}}a^{-\frac{1}{2}}x)^{j}}{j}\right)\right)$
$\displaystyle=\exp\left(\sum_{k\geq
0}^{m\tau-1}\log\frac{1+q^{\frac{m\tau-1-2k}{2}}a^{-\frac{1}{2}}x}{1+q^{\frac{m\tau-1-2k}{2}}a^{\frac{1}{2}}x}\right)$
$\displaystyle=\prod_{k=0}^{m\tau-1}\frac{1+q^{\frac{m\tau-1-2k}{2}}a^{-\frac{1}{2}}x}{1+q^{\frac{m\tau-1-2k}{2}}a^{\frac{1}{2}}x}.$

We introduce the $q$-binomial coefficients defined by

$\displaystyle\binom{m}{r}_{q}=\frac{(1-q^{m})(1-q^{m-1})\cdots(1-q^{m-r+1})}{(1-q)(1-q^{2})\cdots(1-q^{r})}$

for $r\leq m$, and in particular $\binom{m}{0}_{q}=1$. The $q$-binomial
coefficients $\binom{m}{r}_{q}\in\mathbb{Z}[q]$ (see Chapter 2 of [15] for
$q$-binomial coefficients). There are analogs of the binomial formula, and of
Newton’s generalized version of it for negative integer exponents,

$\displaystyle\prod_{k=0}^{n-1}(1+q^{k}t)$
$\displaystyle=\sum_{k=0}^{n}q^{\frac{k(k-1)}{2}}\binom{n}{k}_{q}t^{k}$
$\displaystyle\prod_{k=0}^{n-1}\frac{1}{(1-q^{k}t)}$
$\displaystyle=\sum_{k=0}^{\infty}\binom{n+k-1}{k}_{q}t^{k}.$

Therefore, the coefficient $\left[f(x)\right]_{x^{m}}$ of $x^{m}$ in $f(x)$ is
given by

$\displaystyle\sum_{j+k=m}(-1)^{k}q^{\frac{j(j-1)-(m\tau-1)m}{2}}a^{\frac{k-j}{2}}\binom{m\tau}{j}_{q}\binom{m\tau+k-1}{k}_{q},$

which lies in the ring $\mathbb{Z}[q^{\pm\frac{1}{2}},a^{\pm\frac{1}{2}}]$ by
the integrality of Gaussian binomial.

For the case $\tau\leq-1$, we write $\\{m\tau j\\}=-\\{-m\tau j\\}$ in the
formula (23), then the similar computations give the formula (22). ∎

Now, we can finish the proof of Theorem 1.4 as follow:

###### Proof.

Lemma 5.3 implies that there exist rational numbers $n_{m,g,Q}(\tau)$, such
that

$\displaystyle z^{2}g_{m}(q,a)=\sum_{g\geq
0}\sum_{Q}n_{m,g,Q}(\tau)z^{2g}a^{Q}\in\mathbb{Q}[z^{2},a^{\pm\frac{1}{2}}].$

So we only need to show $n_{m,g,Q}(\tau)$ are integers. By lemma 5.4 and the
formula (9) for $g_{m}(q,a)$, we have

$\displaystyle\\{m\\}\\{m\tau\\}z^{2}g_{m}(q,a)\in\mathbb{Z}[q^{\pm\frac{1}{2}},a^{\pm\frac{1}{2}}],$

which is equivalent to

$\displaystyle(q^{\frac{m}{2}}-q^{-\frac{m}{2}})(q^{\frac{m\tau}{2}}-q^{-\frac{m\tau}{2}})\sum_{g\geq
0}\sum_{Q}n_{m,g,Q}(\tau)(q^{1/2}-q^{-1/2})^{2g}a^{Q}\in\mathbb{Z}[q^{\pm\frac{1}{2}},a^{\pm\frac{1}{2}}].$

So it is easy to get the contradiction if we assume there exists
$n_{m,g,Q}(\tau)$ which is not an integer. ∎

## References

  * [1] A. Aganagic and C. Vafa, Mirror symmetry, D-branes and counting holomorphic discs. arXiv: hep-th/0012041.
  * [2] A. Aganagic and C. Vafa, Large N Duality, Mirror Symmetry, and a Q-deformed A-polynomial for Knots, arXiv: 1204.4709.
  * [3] Q. Chen, K. Liu, P. Peng and S. Zhu, Congruent skein relations for colored HOMFLY-PT invariants and colored Jones polynomials, arxiv:1402.3571v3.
  * [4] M. Dedushenko, E. Witten, Some Details On The Gopakumar-Vafa and Ooguri-Vafa Formulas, arXiv:1411.7108.
  * [5] E. Eynard and N. Orantin, Computation of open Gromov-Witten invariants for toric Calabi- Yau 3-folds by topological recursion, a proof of the BKMP conjecture, Comm. Math. Phys. 337 (2015), no. 2, 483-567.
  * [6] H. Fuji, S. Gukov, P. Sulkowski, H. Awata, Volume Conjecture: Refined and Categorified, Adv. Theor. Math. Phys. 16 (2012) 1669-1777.
  * [7] H. Fuji, S. Gukov, P. Sulkowski, Super-A-polynomial for knots and BPS states, Nucl.Phys. B867 (2013) 506-546.
  * [8] S. Garoufalidis, P. Kucharski and P. Sulkowski, Knots, BPS states, and algebraic curves, Commun. Math. Phys. 346 (2016) 75-113.
  * [9] R. Gopakumar, C. Vafa, M-Theory and Topological Strings-I, arXiv:hep-th/9809187.
  * [10] R. Gopakumar, C. Vafa, M-theory and topological strings-II, arXiv:hep-th/9812127.
  * [11] R. Gopakumar and C. Vafa, On the gauge theory/geometry correspondence, Adv. Theor. Math. Phys.3(5) (1999) 1415-1443.
  * [12] K. Hori, S. Katz, A. Klemm, R. Pandharipande, R. Thomas, C. Vafa, R. Vakil and E. Zaslow, Mirror symmetry,(Clay mathematics monographs. 1).
  * [13] P. Kucharski, M. Reineke, M. Stosic, P. Sulkowski, BPS states, knots and quivers, arXiv:1707.02991.
  * [14] P. Kucharski, M. Reineke, M. Stosic, P. Sulkowski, Knots-quivers correspondence, arXiv:1707.04017.
  * [15] A. Klimyk and K. Schmudgen, Quantum groups and their representation theory, Springer-Verlag, Berlin Heidelberg 1997\.
  * [16] P. Kucharski and P. Sulkowski, BPS counting for knots and combinatorics on words, arXiv:1608.06600.
  * [17] C.-C. Liu, K. Liu, J. Zhou, A proof of a conjecture of Mariño-Vafa on Hodge integrals, J. Differential Geom. 65(2003).
  * [18] J.M.F. Labastida and M. Mariño, Polynomial invariants for torus knots and topological strings Comm. Math. Phys. 217 (2001),no. 2, 423.
  * [19] J.M.F. Labastida and M. Mariño, A new point of view in the theory of knot and link invariants J. Knot Theory Ramif. 11 (2002), 173\.
  * [20] J.M.F. Labastida, M. Mariño and C. Vafa, Knots, links and branes at large N, J. High Energy Phys. 2000, no. 11, Paper 7.
  * [21] K. Liu and P. Peng, Proof of the Labastida-Mariño-Ooguri-Vafa conjecture. J. Differential Geom., 85(3):479-525, 2010.
  * [22] W. Luo and S. Zhu, Integrality structures in topological strings I: framed unknot, arXiv:1611.06506.
  * [23] A. Mironov, A. Morozov, An. Morozov, A. Sleptsov, Gaussian distribution of LMOV numbers, arXiv:1706.00761.
  * [24] A. Mironov, A. Morozov, An. Morozov, P. Ramadevi, Vivek Kumar Singh, A. Sleptsov, Checks of integrality properties in topological strings, arXiv:1702.06316.
  * [25] M. Mariño, C. Vafa, Framed knots at large N, in: Orbifolds Mathematics and Physics, Madison, WI, 2001, in: Contemp. Math., vol.310, Amer. Math. Soc., Providence, RI, 2002, pp.185-204.
  * [26] H. Ooguri, C. Vafa, Knot invariants and topological strings. Nucl. Phys. B 577(3), 419-438 (2000).
  * [27] E. Witten, Chern-Simons Gauge Theory As A String Theory, Prog. Math. 133, 637 (1995).
  * [28] J. Zhou, A proof of the full Mariño-Vafa conjecture. Math. Res. Lett. 17 (2010), no. 6, 1091-1099.
  * [29] S. Zhu, Colored HOMFLY polynomials via skein theory, J. High. Energy. Phys. 10(2013), 229
  * [30] S. Zhu, Topological strings, quiver representations and Rogers-Ramanujan identities, The Ramanujan Journal (2019) Vol 48(2), 399-421.
  * [31] S. Zhu, Topological Strings and Their Applications in Mathematics, Notices of The ICCM, Dec. 2017.


# On CAD Informed Adaptive Robotic Assembly

Yotto Koga1, Heather Kerrick2 and Sachin Chitta3 1Yotto Koga is with Autodesk
Research, San Francisco, CA<EMAIL_ADDRESS>Kerrick is with
Autodesk Fusion 360, San Francisco, CA<EMAIL_ADDRESS>Chitta is with Autodesk Research, San Francisco, CA<EMAIL_ADDRESS>
###### Abstract

We introduce a robotic assembly system that streamlines the design-to-make
workflow for going from a CAD model of a product assembly to a fully
programmed and adaptive assembly process. Our system captures (in the CAD
tool) the intent of the assembly process for a specific robotic workcell and
generates a recipe of task-level instructions. By integrating visual sensing
with deep-learned perception models, the robots infer the necessary actions to
assemble the design from the generated recipe. The perception models are
trained directly from simulation, allowing the system to identify various
parts based on CAD information. We demonstrate the system with a workcell of
two robots to assemble interlocking 3D part designs. We first build and tune
the assembly process in simulation, verifying the generated recipe. Finally,
the real robotic workcell assembles the design using the same behavior.

##  I INTRODUCTION

Traditionally, automated assembly processes are implemented using fixed
automation, requiring considerable effort for each product to ensure robust
and reliable execution. However, the needs of ever more demanding and
discerning customers are pressuring manufacturers to provide customizable
product offerings. As a result, product cycles are shortening, and
manufacturers must often retool and re-program their assembly lines to
automate production for _high-mix, low volume_ products. However, frequent
assembly workcell changes are cost-prohibitive because of the required time,
material, and programming. Simplifying the programming workflow for automated
assembly will lead to a new generation of easy-to-deploy and flexible
automation systems.

This paper describes our efforts toward simplifying the design-to-make
workflow using robots through a novel mix of planning, perception, and
interactive authoring tools. The interactive tools are designed to allow
automation designers to easily specify desired actions at a high level, using
their expertise to augment the automated capabilities of our system - e.g. the
designer can specify the assembly sequence order of parts while planning
techniques are used to find intermediate waypoints for the robot putting the
parts into the assembly.

Through the interactive tools, the designer further simplifies the assembly
problem into three separate robotic manipulations tasks, picking up the part,
re-grasping the part to obtain the required goal grasp for part insertion, and
finally inserting the part into its goal location in the assembly.

We use depth images from an RGBD camera capturing a collection of parts to
feed a fully convolutional DenseNet model to identify part classes and to
infer collision-free grasp locations on the parts. This provides automated
part picking and adaptation to variations in the part locations. We also feed
depth images of grasped parts and the assembly with another DenseNet model
(trained differently than the grasping model) to infer 6 DOF pose estimates.
Combined with a simple graph-based regrasp sequence planner, this provides
automated re-grasping of parts to the desired goal grasp. With pose estimates
of the grasped part and the assembly area, the robot can deliver the part
through its waypoints into the assembly. We demonstrate our approach by
automating a challenging assembly of a set of interlocking part designs with a
multi-robot workcell.

Finally, our system makes extensive use of CAD information: (1) In the
interaction tool to specify high-level input for the assembly process, (2) In
the perception pipeline to enable part manipulation based solely on CAD data
of the part for training DenseNet models, and (3) In the planning pipeline to
simulate and validate feasible grasps, assembly paths and re-grasping
behaviors. We believe a CAD to assembly pipeline of this form will improve the
accessibility of assembly automation systems to non-expert users.

In summary, the contributions in this paper are: (1) A novel end-to-end
design-to-adaptive-make workflow augmenting designer input with planning and
perception, (2) A system that can deal with uncertainties arising from part
presentation, from pickup to re-grasping to insertion, (3) A precise pose
estimator that allows the robots to assemble the parts of the design using
only positional control, and (4) A demonstration of the system on a
challenging assembly task with a dual-arm robotic workcell.

##  II RELATED WORK

Using CAD information for inferring the assembly sequence has been studied in
early work [4, 2] where the concept of assembly by disassembly was used. This
approach draws on the fact that part motions are significantly constrained in
the disassembly phase, reducing the complexity of finding a solution. Other
work inferred feasible assemblies using geometric descriptions and constraints
of the parts [7, 19]. Knepper et al. built on this approach in [10] to
coordinate a team of robots building furniture.

In [15], Michniewicza et al. outlined the development of a system that
combined task and functional primitives into a directed graph called an
Augmented Assembly Priority Plan. The plan can consider constraints (e.g.,
workspace, collision) and allocate resources (e.g., robots, conveyors,
grippers, etc.). Individual operations (called skills – e.g., fastening,
insertion, etc.) are sequenced appropriately to complete the assembly.

We rely on the designer to provide the assembly sequence order and allocation
of resources for assembly tasks.

In [13], Lozano-Pérez et al. described a robot manipulation system called
HANDEY. They integrated vision, path planning, grasp planning, regrasp
planning, and motion control to pick, regrasp, and place shapes using multiple
robot arms. Re-grasping of parts was done by placing them on a table. In [1],
Alami et al. presented a unified framework for planning manipulation tasks for
picking, re-grasping, and placing objects using a robot arm. In [11], Koga and
Latombe developed a manipulation planner for multi-arm robotic systems. They
demonstrated simulated results of multiple arm robotic systems with up to 24
degrees of freedom, grasping an object, transferring it to some goal location,
and initiating re-grasping motions as needed to complete the task. We are
similar in spirit to the HANDEY system and decompose the assembly problem into
separate tasks, in contrast to the unified and challenging task and
manipulation planning approach.

In [20], Wan et al. described a regrasp planning component for finding
sequences of robot poses and grasp configurations to reorient a part to some
goal pose. They construct the problem as a graph search problem. Our re-
grasping approach is very similar, except that we search the graph to find a
sequence to reach a goal grasp of the part.

Deep learning models to infer grasp location on parts from RGBD images is a
popular method for robotic part picking tasks [17, 14, 23]. In particular,
Redmon and Angelova [17] described a model to regress RGBD image data into 2D
grasp proposals represented by a grasp rectangle $(x,y,\theta,h,w)$. Our
grasping model is a simple extension of [17] to 3D grasp proposals. We replace
their model backbone with the DenseNet segmentation model [9] and use dense
prediction from a depth image of part collections (presented as a heightmap)
to grasp rectangle point clouds. The inferred grasp rectangle point cloud is
the 3D grasp proposal for the associated part.

For pose estimation of objects, there are several techniques to employ such as
registration using ICP [21], PointNetLK [10], or PVN3D [8]. Our pose
estimation task is for non-occluded single objects, so PointNetLK, PVN3D, and
similar pose estimation models are excessive for our needs. ICP has challenges
with local minima and slow running speeds. For our pose estimation needs, we
modified our training data pipeline for the DenseNet grasp proposal model to
produce a pose rectangle point cloud label associated with the view of the
part. Given the offset between the pose rectangle and the part frame, we
extract a reliable pose estimate of the part after PCA.

In [6], Gorjup et al. described the system they developed for the IROS 2019
Robotic Grasping and Manipulation Competition. The competition consisted of
four representative classes of assembly tasks, fastener threading, insertion,
wire routing, and belt threading and tensioning. A CAD file described the
tasks’ layout, ground truth pose, and goals. Their first place system
consisted of a CAD interface to extract the ground truth data, a specialized
gripper to handle multiple tasks, and compliance control to recover from
calibration errors. In [5], Drigalski et al. described the system they built
for the World Summit 2018 World Robot Challenge. The set of tasks for this
competition was similar to [6]. Likewise, we have created workflow and tools
to simplify the task of setting up automated adaptable robotic assembly of
designs. We incorporate many of the same components, although we tackle a more
unconstrained problem where parts are arbitrarily presented to the system,
which requires solutions for tilting the gripper fingers to pick up the parts
successfully, and re-grasping of parts. We also only require positional
control to assemble the design.

##  III APPROACH

For this work, the assembly tasks we consider require picking up parts, re-
grasping if necessary, and then inserting parts into the assembly without
fasteners like bolts or clips. We consider only parallel-jaw gripper fingers.
We assume there are at least two robots in the workcell with a common
workspace where they can pass the part between each other for re-grasping. We
demonstrate the system using two robot arms to assemble interlocking block
designs called Yinan blocks, named after their inventor [22].

In this section, we first describe the authoring steps to specify the high-
level instructions for the assembly process. We then describe our method of
using planning techniques and perception models to fill in the details for the
actual robots in the workcell to complete the assembly.

Figure 1: A digital twin of a physical robotic workcell with custom made
fingers and camera fixtures. The authored pickup area and camera and fingers
used to grasp the parts are highlighted in blue. Figure 2: A disassembly
sequence for a design made with Yinan blocks. Sequence goes for a) to f).

###  III-A Authoring Steps

Our approach starts with the designer specifying high-level steps for the
assembly process. We assume that the robotic workcell is modeled and available
to the designer as a digital twin (see Fig. 1). The authoring steps of this
workflow are the following:

  1. 1.

In the CAD tool, the designer specifies the disassembly sequence for the parts
and sub-assemblies using a simple point and click visual interface (see Fig.
2). The authoring tool hides the selected parts to facilitate the
specification of the disassembly sequence. Reversing this sequence yields the
assembly sequence.

  2. 2.

The designer authors a set of grasps for each part using the specific fingers
in the workcell. A grasp in this set can be a single position and orientation
of the fingers with respect to the part or a range between two endpoints. We
rely on the designer’s judgment to author stable grasps of the part with the
fingers of the gripper. We assume an authored grasp can be flipped by 180
degrees around the fingers’ z-axis (see Fig. 3) and still be valid, so each
authored grasp adds two entries into the set. An example of authored grasps in
a set is shown in Fig. 3.

  3. 3.

The designer can additionally specify locations for the parts (pickup area),
the cameras available in the workcell, the assembly location in the workcell,
a re-grasping area, and other workcell parameters, including choice of cameras
and robots for different parts of the assembly process (see Figs. 1 and 4).

  4. 4.

In the final step, the designer stitches the assembly behaviors together
following the sequential task-level goals. We provide task-level APIs to
simplify the scripting task.

Figure 3: Examples of authored grasps. The upper left cell shows the reference
frame for the fingers. The frame origin is at the midpoint between the two
fingertips.

The authored steps describe the high-level intent of the assembly process. At
each stage, a validation check is run to verify that the assembly sequence,
with the robot, their fingers, and cameras in the workcell can reach, insert
and view the parts in the specified areas in a collision-free manner. Upon
verification of all steps, a recipe of sequential task-level goals for
assembling the design is generated. For each part, the instructions include
its type, its general location in the workcell, which camera to use to locate
the part, the fingers that will grasp it, the camera which will be used to get
its pose estimate, the goal grasp to insert it into the assembly, and finally,
the intermediate waypoints to insert it into the assembly. Our system requires
the designer to reauthor steps due to failures in the validation stage.
Incorporating designer feedback in this manner allows our system to draw on
the skills and experience of the designer in the areas that they are most
skilled at while providing an additional checkpoint before executing the
behaviors in the robot workcell.

Figure 4: An example of the location and the specified cameras and fingers
used to drive regrasp actions of parts (highlighted in blue).

###  III-B Robot Steps

At each stage of the assembly process, parts need to move from the pickup area
to the assembly area and be inserted into the assembly. This is a manipulation
planning problem [1, 11] which aims to find the robot motions to grasp the
part and transfer it to the goal location in a collision-free manner. Reaching
the goal may require the re-grasping of the part using stable placement areas
or an extra gripper to hold the part. We simplify the problem by breaking this
end-to-end consideration into three separate tasks, 1) grasping and pickup of
the part, 2) insertion of the part into the assembly, and if necessary, 3) re-
grasping of the part to the required grasp for part insertion.

To pick up the part, we use a perception model to find the required part in
the pickup region and infer its collision-free grasp for the user-specified
robot. We then move the robot and gripper to this location to grasp and pick
up the part. For part insertion, we use a motion planner with grasp
constraints for the user-specified insertion robot to find the required grasp
of the part for insertion and its waypoints into the assembly. We then move
the robot and the grasped part (with the goal grasp) through the waypoints
into the assembly. If the goal grasp differs from the pickup grasp, we first
move the grasped part into the user-specified regrasping area. A regrasp
planner is used to find the sequence of re-grasping steps to achieve the
required goal grasp for the insertion robot. We then move the robots through
the re-grasping steps. We now describe the key components in more detail.

####  III-B1 Grasp Inference

We want our system to be able to pick up tilted parts from a pile using a
parallel-jaw gripper. This requires finding grasps that orient in 3D and
account for tilt to maximize the chance for successful grasps.

Figure 5: A part pile heightmap (blue points) and the associated 3D grasp
proposals (red points). The blue points are the input to the model, and the
red points are the output.

Our grasp perception model is a simple extension of the work from Redmon and
Angelova [17]. We replace their model backbone with the DenseNet segmentation
model [9] and use dense prediction from a depth image of piled parts
(presented to the model as a heightmap) to get 3D grasp proposals for the
parts. A 3D grasp proposal represents the stable and collision-free grasp
region of the associated part for the fingers of the robot. The model produces
the proposal as a rectangular point cloud (see Fig. 5). For each rectangular
point cloud, we use PCA to get its 3D center, 3D orientation, width, and
height of the grasp proposal. The center and normal vector for the rectangular
region are the proposal frame origin and z-axis direction, respectively. The
points in the proposal are located at the pixel coordinates of the dense
prediction. The height value at the output pixel is the height of that point
in the rectangular point cloud. Also, the part class id of the associated part
is concatenated by the model to each pixel height value.

The frame of the grasp proposal (see Fig. 6) defines the location of the
finger frame for grasping (see Fig. 3). From just the rectangular point cloud,
the direction for the fingers to close on the part is ambiguous. Is it along
the width or height of the proposal? A value gradient over the proposal gives
this direction and the model concatenates gradient samples to the pixels’
height and class id values (see Fig. 7). The x-axis direction for the grasp
proposal (the finger closing direction) is along the gradient going from
biggest to smallest value.

Figure 6: The grasp proposal frame associated with a heightmap of a part.
Figure 7: The grasp x-gradient.

The training data is generated synthetically by randomly placing and piling
the CAD model of the parts in the pickup area in different orientations. We
use a 3D OpenGL-based renderer to create the depth data of the parts from the
view of the perspective camera for a given sample. To facilitate the transfer
of the learned model to work with actual camera depth data, we add noise to
the rendered depth map by downsampling the resolution and adding Perlin noise
to its depth values. We convert the depth image into an orthographic heightmap
representing the parts’ structured 2.5D point cloud.

The associated grasp proposal label for the sample is computed in the
following manner. For each part in the pile, the CAD model of the grasping
fingers is positioned at each grasp in the set authored for that part. A grasp
is considered valid if the CAD model of the fingers grasping the part does not
collide with any other parts or the environment. When a grasp defines a range
between two endpoints of the fingers along the part, we discretize the range
into a few steps and check if each step is valid. Consecutive, valid tests for
a grasp are grouped to create the grasp proposal. The grasp proposal frame is
the fingers’ tip frame at the midpoint of the span. Since the finger frame can
be rotated by 180 degrees around its z-axis and be the same grasp, we avoid
ambiguity in the label by constraining the proposal frame to have its x-axis
direction always pointing towards the right half of the camera view. The
dimension of the proposal in its x-axis is the spacing between the fingers for
the grasp, and the dimension in its y-axis is the finger width plus the span
of consecutive, valid tests. For all valid proposals, we check for any overlap
between proposals from the camera view. If there is an overlap, we discard the
bottom proposal. We then render the remaining proposals into a heightmap that
matches the associated part heightmap sample (rendered from the same camera
viewpoint). We save the label in an image format. The height of the grasp
proposal pixels are encoded in the alpha channel of the rendered result. The
grasp proposal x-axis direction gradient is encoded in the red channel. And
finally, the part class associated with the proposal pixels are encoded in the
green channel.

For each set of parts in an assembly process, we synthesize roughly 600,000
samples of these parts and their associated labels. Our loss function used in
training the DenseNet model is the sum of the cross-entropy loss of the
height, class, and gradient value in the dense prediction. We scale the loss
by the number of points with non-zero height values in the label to account
for the sparseness of the proposals. Our data generation pipeline creates
training data at a fixed camera distance from the part pile and generates the
associated grasp region labels with a specified finger CAD model. The model
take about 12 hours to train on an Nvidia V100 GPU.

We make grasp inference by capturing a heightmap from the specified camera for
part pickup and then feeding it to the model. We use 2D clustering techniques
to isolate each grasp proposal in the result. We then use PCA on the points to
get the center and tilted orientation of the proposal in the camera frame. The
part class associated with the proposal is the max class value. The x-axis
direction for the frame comes from the gradient direction embedded in the
proposal and is updated accordingly.

To grasp a particular part by class, we look at the grasp proposals with the
desired part class and choose the one with its center closest to the camera.
The grasp pose is mapped to the workcell frame, the fingers open to the value
given by the grasp proposal (plus some extra padding), and the robot moves the
fingers into position to grasp and pick up the part.

####  III-B2 Motion Planning for Assembly

Figure 8: A part designed in a CAD tool where the primary motion directions
for insertion into the assembly are also the axes of its local frame (the red,
blue, and green arrows).

After the designer authors a disassembly sequence, we use a motion planner to
verify that the disassembly sequence is correct. We approximate the test by
running a best-first-search [12] with three translation degrees of freedom
along the axes of the part local frame (see Fig. 8). This requires that the
part axes are aligned with the directions in which the part comes out of the
assembly. This seems to be a reasonable requirement regarding how CAD models
are created in practice. This allows us to orient the part in its final pose
and discretize the translation search space around the tight thresholds of the
parts in the assembly and maximize the chance of finding collision-free paths
in the discretized configuration space. If a collision-free path to extract
the part (to some free space outside the assembly) cannot be found, then an
error is communicated to the designer that the sequence is incorrect. We
require the designer to re-author the disassembly sequence to correct the
failure. Parts that need twisting or tilting into the assembly will require a
more exhaustive search routine. In complicated cases, we would have the
designer author the waypoints. Despite this limitation, we were still able to
explore interesting assembly tasks.

We also add a grasping constraint to the motion planning problem. The grasp
constraint requires that the robot and gripper fingers maintain the grasp of
the part during the search. The part, robot, and fingers must also be
collision-free throughout the path. The disassembly sequence for the design is
verified if we can find a collision-free extraction motion and meet the grasp
constraint criteria for all parts, running the planner multiple times with the
entire design in different random starting poses in the assembly area. If
multiple grasps exist, we choose the grasp with the fingers’ x-axis aligned
with any insertion motion. This is the stable grasp to keep the part from
twisting between the fingers during contact with the insertion surfaces.

The grasp associated with the resulting collision-free path is the goal grasp.
The motion planning search is biased to find straight-line motions with the
minimum number of direction changes. The ends of the straight-line motion
become waypoints for the disassembly of a part. The reverse order of waypoints
becomes the robot’s insertion instructions to move the part into the assembly.
For example, the insertion waypoints for the block in Fig. 8 in the assembly
shown in Fig. 2, is a downward motion with the nub of the part moving through
the vertical slot and then sliding horizontally through the horizontal slot
embedded inside the assembly to its goal.

Note that we only use the motion planner to find the part’s goal grasp and
generate the waypoints to deliver the part to the assembly from just above the
assembly area. We use simpler straight-line motions of the fingers or cameras
for gross robot motion in the workcell. For uncluttered workcells, this seems
sufficient to generate collision-free trajectories. As such, gross motion
planning was not a focus of this work, but, in more cluttered workcells, we
aim to integrate standard motion planning techniques in the future (e.g.,
using open-source packages like MoveIt! [18]).

####  III-B3 Re-grasp Planning

The parts in the pickup area can have arbitrary positions and orientations.
The grasp chosen for pickup may differ from the required grasp for part
insertion necessitating a re-grasping step. To re-grasp the part, we use two
robots to move through a sequence of alternating grasps until the desired
grasp is achieved (see Fig. 9).

Figure 9: An example re-grasping sequence of a part with the two robot fingers
to achieve the goal grasp. Sequence goes from a) to i).

We cast the problem into a graph search to find the re-grasping steps. We
construct the graph by first specifying where re-grasping occurs in the
workcell. The part will be centered at this location but can have different
orientations. We require a finite set of varying part poses to seed the graph.
For re-grasping, one robot will always hold the part. We compute the
associated grasp pose for the given part pose for each grasp definition in the
grasp set. We test if this grasp pose for the fingers is achievable. We then
test if the robot and fingers are collision-free with the environment for
achievable grasps. If these conditions are met, this $(grasp,partpose,finger)$
tuple becomes a node in our graph. To manage grasp definitions that allow the
fingers to be in a range along an edge of a part, we break up the range into
three samples, the grasp at two endpoints along the part and the midpoint.

Two nodes of the graph are connected when they share the same part pose, the
fingers in the nodes are different (i.e. the robots in the nodes are
different), and the robots, fingers, and any attached peripherals to the
robots grasping the part simultaneously do not collide with each other (see
Fig. 4). This edge type is a re-grasp step. Nodes with the same grasp and
fingers are also connected if the fingers (and associated robot) can move the
part from the pose in the first node to the second node in a collision-free
and reachable manner. This edge type is a repose step.

Assuming we can determine the initial grasp definition of the part with the
fingers, we find the nodes in the graph with the same grasp, finger pair. For
each node in this set, we can traverse edges of the graph using best-first
search and find the minimal number of re-grasp steps to achieve the desired
goal grasp of the part if a path exists. The path with the minimum number of
re-grasp steps is chosen if multiple paths exist.

To get the initial grasp definition of the part after pickup, we first get its
pose estimate. This gives us an estimate of the offset between the grasping
fingers’ frame and the part. We then visit the nodes in the graph with the
free fingers (the fingers not grasping the part). For the associated part
pose, we determine if the grasping fingers can repose the part to that pose
and that the grasp for the free fingers will be clear of the current fingers.
For nodes that pass this test, we search the graph to find the node that
yields the shortest re-grasp sequence. We then re-grasp the part according to
that node. This gives us the initial grasp definition of the part.

For re-grasping the part, we first move the part into the shared part pose
associated with the edge using the fingers currently grasping the part. Next,
we move the free fingers in a linear motion to a hovering position just above
its grasp pose with the fingers opened slightly greater than its grasp
definition. Then, we move the fingers in a linear motion to the grasp pose and
close the fingers around the part. The other fingers release the part, and we
move it in a linear motion just above its last grasp. Finally, we move the
fingers to an area away from the part to give clearance for the reorienting
part. We repeat this process until the goal grasp is reached.

####  III-B4 Part Pose Estimation Model

We need a precise in-hand pose estimate of the grasped part for the robot to
accurately deliver the fingers to their re-grasp locations and the part to its
insertion location. Note that the pose estimate only needs to be precise since
we can rely on the precision of the robots and calibration to deliver the
fingers and the part accurately to their goal location.

We re-use the DenseNet grasp proposal model and change the training dataset to
have the model produce the part pose estimate. The basic idea is to feed the
model a point cloud of the part (presented as a heightmap) and have it produce
a rectangular point cloud attached to the part for the given view direction
(see Fig. 10). We call this rectangular point cloud a pose proposal. We
extract the part pose estimate from the pose proposal in the following manner.

Figure 10: The pose proposal (red points) associated with the heightmap of the
part (blue points). This pose proposal is for the viewing directions from the
top side of the part.

We partition any view directions of the part into a top, bottom, left, right,
front and back direction. These correspond to the six primary viewing
directions of the part along the frame axes of the part. A view direction of
the part that is within a 45-degree frustum of a primary direction is said to
have that primary view direction. For example, in Fig. 10, all views of the
part within 45 degrees of the top side direction are considered a top view
direction.

For each primary view direction, there is one associated pose proposal. The
model produces the pose proposal for the view direction of the input part
heightmap. Each pose proposal has a fixed offset from the part frame, so using
PCA to get the center and 3D orientation of the proposal (in the exact manner
as grasp proposals) and applying the offset, we can infer the pose estimate of
the part.

The synthetic training data is generated by sampling a heightmap of each part
randomly positioned in front of the camera. The distance between the parts and
the camera is controlled in a fixed interval that ensures all parts are fully
viewable by the camera and fills roughly a third of the view. The height map
samples are generated using the same renderer as the grasping dataset.

The associated pose proposal label for the sample is computed as follows. We
first create the pose proposal for each primary view direction for each part.
This is done by taking the bounding box of the part and making each face the
pose proposal for the associated view direction. For example, the bounding box
face on the top side is the pose proposal for the top view direction. The
frame for each pose proposal is centered on the face, with the x and y axes
aligned with the width and height directions and the z-axis along the face
normal. The width and height of the face are the width and height of the
associated pose proposal. We record the offset between the part frame and each
of the six pose proposal frames. We then determine the primary view direction
for the given heightmap sample of the part. For that view direction, we take
the associated pose proposal, position it with respect to the part frame and
then render the rectangular pose proposal into a heightmap that matches the
associated part heightmap sample. The height of the pose proposal pixels are
encoded in the alpha channel of the rendered result. The pose proposal x-axis
direction gradient is encoded in the red channel. And finally, the part class
and primary view id associated with the proposal pixels are encoded in the
green channel. The combined id is: $id=viewid+6*partid$.

Some view directions of the parts have rotational symmetry order greater than
1. For example, each view direction of a cube shape will have rotational
symmetry of 4. We handle this ambiguity by constraining the direction of the
x-axis of the pose proposal during data generation. For example, a view
direction with rotational symmetry of order 2, we constrain the x-axis
direction of the proposal to point towards the right half of the camera view.

For each set of parts in an assembly process, we synthesize roughly 400,000
samples and their associated labels. We use the same loss function from the
grasping model. The model take about 12 hours to train on an Nvidia V100 GPU.

We estimate the pose by capturing a heightmap of the part at roughly the same
camera distance as in the training set. We use PCA on the points of the
generated pose proposal to get the center and tilted orientation of the
proposal in the camera frame (the x-axis direction is determined from the
gradient values). The part class and view direction id associated with the
proposal is the max class value. The offset of the pose proposal to the part
frame is retrieved using the part and view direction id. The part pose is then
transformed into the camera frame.

##  IV EXPERIMENTS

We implemented the end-to-end workflow using an internal robotics research
platform. The authoring and simulation tools are integrated into Autodesk
Fusion 360.

For the assembly demonstration, we used two shapes which we call Yinan blocks
(see Figs. 4 and 8), and a fixed base to support the assembly (see Fig. 2f).
The design we assembled is shown in Fig. 2a. We calibrated the workcell shown
in Fig. 11 to create the digital twin shown in Fig. 1. We use a UR10 and a
XArm-6 robot, with the Robotiq Rq140 and Rq85 grippers attached to each robot,
respectively. The fingers are custom printed for grasping the blocks (see Fig.
3). We used the Intel RealSense SR-300 cameras for depth sensing. A camera is
attached to the end of each robot with a fixture. The Yinan blocks are small
(about one in.) and interface with each other along particular pairs of faces.
The parts are initially located in random piles in an input area, i.e., the
parts are not nicely presented to the robot.

Figure 11: The assembly workcell with two robot arms.

We authored the disassembly sequence for the design by selecting the parts in
the order shown in Fig. 2. The behavior script corresponding to the generated
recipe for this experiment is represented in Fig. 12.

$sequence$ = $recipe$.get_assembly_sequence()

$camera$ = $recipe$.assembly_camera

${}^{W}T^{B}$ = $camera$.get_pose($recipe$.assembly_area)

while $s$ in $sequence$ do

$s$.fingers.pickup_part($recipe$.pickup_area, $s$.camera, $s$.part_class)

${}^{P}T^{F}$ = $s$.fingers.regrasp($s$.goal_grasp,

$s$.camera,

$s$.other_fingers,

$s$.other_camera)

while ${}^{W}T^{F}$ in $s$.insertion_waypoints(${}^{W}T^{B},^{P}T^{F}$) do

$s$.goal_fingers.move_to(${}^{W}T^{F}$)

end while

$s$.goal_fingers.release()

end while

${}^{W}T^{B}$ \- fixed base transform in the workcell frame

${}^{P}T^{F}$ \- finger transform in the part frame

${}^{W}T^{F}$ \- finger transform in the workcell frame

Figure 12: Pseudo-code of the assembly behavior for the experiment.

We first ran the behavior in simulation using the digital twin of our workcell
to verify that the assembly process was correct. We randomly piled the blocks
in the pickup area and then successfully ran the behavior on the actual
workcell. To accurately re-grasp and insert the grasped parts into the fixed
base (tight tolerances), we had to add a correction map to compensate for the
cascading calibration errors between the various fingers, cameras, and robot
base offsets. It took 9 minutes for the robots to complete this assembly task
(Fig. 13). Inference time for grasp and pose estimation is roughly 50 ms on an
Nvidia V100. To capture a clean depth image from the cameras, though, we wait
for the robot to stop moving and settle, which adds an extra second to the
total inference time. See https://youtu.be/hoAJPZuMmJ0 to view the assembly
behavior in action.

The success rate data for the pickup, re-grasp, and insertion tasks are in
Table I. We ran six consecutive end-to-end assembly of the design. On failure,
we tried the task again by resuming the assembly sequence from the pickup
task. We count each individual re-grasp step. Note that this data was
collected with the Xarm replaced with another UR10.

Figure 13: Snapshots from the assembly process. The upper left cell is the first step where the fixed base pose is acquired. The lower right cell is the completed assembly. TABLE I: Task Success Rate Task | Success | Failure | Success Rate
---|---|---|---
Pick | 47 | 2 | 96%
Regrasp | 130 | 17 | 88%
Insertion | 30 | 0 | 100%

##  V Discussion

There are avenues for improvement and further work. The assembly process is
slow, and we’re working towards improving cycle times for the task. The system
is sensitive to the calibration of the robots, their cameras, and each other -
e.g., failures during re-grasping are when the part is rotated from its pose
estimate, and the re-grasping finger has to rotate accordingly. This rotation
accentuates calibration errors causing the re-grasping fingers to miss their
mark. We plan to use visual servoing to remove the need for the correction
maps and the dependency on accurate calibration. We are working towards
further automating parts of the workflow that may need input from the
designer. This includes determining grasp poses for different parts and motion
planning for gross robot motion. We’d also like to improve our grasping and
pose estimation models’ performance, accuracy, and generality. Currently, our
perception models do not generalize to unseen objects. Characterizing the
range of shapes our perception models can handle is another area of future
work. Our system relies on clean depth images, and we are working towards
identifying the right visual sensors for different materials and parts’
surface finishes. For insertion tasks that are highly occluded or require
tighter tolerances, we aim to explore F/T sensing and insertion policies that
could be learned using reinforcement learning techniques.

Assembly sequence planning is another area of interest for further automation.
CAD information for most assemblies is often incomplete and inaccurate.
Individual parts may not be annotated or labeled correctly, and constraints
between parts can often be represented in multiple ways. Furthermore, there is
often a mismatch between CAD and real models. We aim to explore these areas
using tools from simulation, control, and reinforcement learning. We also aim
to explore more complex assemblies in the industrial domain to highlight the
advantages of our approach over traditional fixed automation.

## References

  * [1] R. Alami, T. Siméon J.P. Laumond. A Geometrical Approach to Planning Manipulation Tasks: The Case of Discrete Placements and Grasps. in Robotics Research 5, H. Miura and S. Arimoto, eds., MIT Press, Cambridge, pp. 453-459, 1990.
  * [2] P. Ambler, R. J. Popplestone. Inferring the positions of bodies from specified spatial relationships. in Artificial Intelligence, 6:157–174, 1975.
  * [3] Y. Aoki, H. Goforth, et al. PointNetLK: Robust & Efficient Point Cloud Registration using PointNet. in Computer Vision and Pattern Recognition (CVPR), pp. 7163–7172, 2019.
  * [4] L. H. De Mello, A.C. Sanderson. A correct and complete algorithm for the generation of mechanical assembly sequences.in IEEE transactions on Robotics and Automation, Bol. 7, no. 2, pp. 228–240, 1991.
  * [5] F. Drigalski, C. Nakashima, et al. Team O2AS at the world robot summit 2018: an approach to robotic kitting and assembly tasks using general purpose grippers and tools. in Advanced Robotics, 2020.
  * [6] G. Gorjup, G. Gao, et al. Combining Compliance Control, CAD Based Localization, and a Multi- Modal Gripper for Rapid and Robust Programming of Assembly Tasks. in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2020.
  * [7] D. Halperin, J.C. Latombe, R. H. Wilson. A general framework for assembly planning: The motion space approach. in Algorithmica, Vol. 26, no. 3-4, pp. 577–601, 2000.
  * [8] Y. He, W. Sun, et al. PVN3D: A Deep Point-Wise 3D Keypoints Voting Network for 6DoF Pose Estimation. in IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
  * [9] S. Jegou, M. Drozdzal, et al. The one hundred layers tiramisu: Fully convolutional densenets for semantic segmentation. in Proc. IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), 2017
  * [10] R. A. Knepper, T. Layton, et al, Ikeabot: An autonomous multi-robot coordinated furniture assembly system. in International Conference on Robotics and Automation (ICRA), pp. 855–862, 2013.
  * [11] Y. Koga, J.C. Latombe. On multi-arm manipulation planning. in International Conference on Robotics and Automation (ICRA), 1994.
  * [12] J.C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, Boston, MA, 1991.
  * [13] T. Lozano-Pérez, J.L. Jones, et al. Handey: a robot task planner. Cambridge, MA, USA: MIT Press, 1992.
  * [14] J. Mahler, J. Liang, et al. Dex-Net 2.0: Deep Learning to Plan Robust Grasps with Synthetic Point Clouds and Analytic Grasp Metrics. in Proceedings of Robotics: Science and Systems (RSS), 2017.
  * [15] J. Michniewicza, G. Reinharta, S. Boschert. 2016. CAD-based automated assembly planning for variable products in modular production systems. in 6th CIRP Conference on Assembly Technologies and Systems (CATS).
  * [16] D. Morrison, P. Corke, J. Leitner. Closing the loop for robotic grasping: A real-time, generative grasp synthesis approach. in Proceedings of Robotics: Science and Systems (RSS), 2018
  * [17] J. Redmon, A. Angelova. Real-time grasp detection using convolutional neural networks. in International Conference on Robotics and Automation (ICRA), pp. 1316–1322, 2015.
  * [18] I. Sucan, S. Chitta. MoveIt!. at https://moveit.ros.org.
  * [19] F. Thomas, C. Torras. Inferring feasible assemblies from spatial constraints. in IEEE Transactions on Robotics and Automation, 8(2):228–239, 1992.
  * [20] W. Wan, H. Igawa, et al. A regrasp planning component for object reorientation. in Autonomous Robot 43, 2018.
  * [21] J. Yang, H. Li, and Y. Jia. Go-ICP: Solving 3d registration efficiently and globally optimally. In 2013 IEEE International Conference on Computer Vision (ICCV), pp. 2241–2254, 2013.
  * [22] Y. Zhang, Y. Koga, D. Balkcom. Interlocking Block Assembly With Robots. in IEEE Trans. on Automation Science and Eng., vol. 18, issue 3, 2021.
  * [23] B. Zhao, H. Zhang, et al. Regnet: Region-based grasp network for single-shot grasp detection in point clouds. in IEEE International Conference on Robotics and Automation (ICRA), 2021.


# Subdigraphs of prescribed size and outdegree

Raphael Steiner

###### Abstract.

In 2006, Noga Alon [1] raised the following open problem: Does there exist an
absolute constant $c>0$ such that every $2n$-vertex digraph with minimum out-
degree at least $s$ contains an $n$-vertex subdigraph with minimum out-degree
at least $\frac{s}{2}-c$ ?

In this note, we answer this natural question in the negative, by showing that
for arbitrarily large values of $n$ there exists a $2n$-vertex tournament with
minimum out-degree $s=n-1$, in which every $n$-vertex subdigraph contains a
vertex of out-degree at most
$\frac{s}{2}-\left(\frac{1}{2}+o(1)\right)\log_{3}(s)$.

Department of Computer Science, Institute of Theoretical Computer Science, ETH
Zürich, Switzerland<EMAIL_ADDRESS>The author was
supported by an ETH Zurich Postdoctoral Fellowship.

##  1\. Introduction

The following open problem was raised by Alon in 2006 in the article [1] on
digraph splitting.

######  Problem 1 (cf. [1], Problem 4.1).

Does there exist an absolute constant $c>0$ such that the following holds for
all pairs of natural numbers $(n,s)$?

Every $2n$-vertex digraph $D$ of minimum out-degree at least $s$ contains an
$n$-vertex subdigraph of minimum out-degree at least $\frac{s}{2}-c$.

Using an elegant probabilistic argument, Alon proved in [1] that a weaker
bound holds, as follows: Every $2n$-vertex digraph of minimum out-degree at
least $s$ contains an $n$-vertex subdigraph of minimum out-degree at least
$\frac{s}{2}-O(\sqrt{s}\sqrt{\log s})$.

In this short note, we resolve Problem 1 in the negative, by proving the
following result via an explicit construction.

######  Theorem 1.

For an infinite sequence of numbers $n\in\mathbb{N}$, there exists a
$2n$-vertex tournament whose minimum out-degree is $s=n-1$, while the minimum
out-degree of every $n$-vertex subdigraph is at most
$\frac{s}{2}-(\frac{1}{2}+o(1))\log_{3}(s)$.

Following the notation from [1], for every $s\in\mathbb{N}$ denote by $d(s)$
the largest integer such that every $2n$-vertex digraph of minimum out-degree
at least $s$ contains an $n$-vertex subdigraph of minimum out-degree at least
$d(s)$. Alon’s result in [1] and Theorem 1 yield

$\Omega(\log s)<\frac{s}{2}-d(s)<O(\sqrt{s}\sqrt{\log s}).$

It remains an interesting open problem to close the gap between the lower and
upper bounds.

### Terminology

All digraphs considered in this paper have no loops or parallel arcs. For a
digraph $D$ we denote by $V(D)$ its vertex set and by
$A(D)\subseteq\\{(u,v)\in V(D)^{2}|u\neq v\\}$ its arc set. For a subset
$X\subseteq V(D)$ of vertices we denote by $D[X]$ the subdigraph of $D$
induced by $X$, i.e., consisting of the vertex set $X$ and all arcs of $D$
going between vertices of $X$. By $\delta^{+}(D)$, we denote the _minimum out-
degree_ of $D$, which is the smallest out-degree occurring in $D$ if $D$ is
non-empty, and defined as $0$ when $D$ is the empty digraph.

##  2\. Proof of Theorem 1

Theorem 1 is an immediate consequence of the following result.

######  Theorem 2.

For every integer $k\geq 0$ there exists a tournament $T_{k}$ on $3^{k}$
vertices in which every vertex has out-degree $\frac{3^{k}-1}{2}$, and such
that the following holds: For every set $X\subseteq V(T_{k})$ of size
$|X|\leq\frac{3^{k}-1}{2}$ we have
$\delta^{+}(T_{k}[X])\leq\frac{\frac{3^{k}-1}{2}-k}{2}$.

To deduce Theorem 2 from Theorem 1, pick $k\geq 0$ arbitrarily, let
$n:=\frac{3^{k}-1}{2}$, and let $D_{k}$ be the $2n$-vertex tournament obtained
from $T_{k}$ by deleting an (arbitrarily selected) vertex. Since deleting a
vertex can lower the out-degree by at most $1$, we have that $D_{k}$ is of
minimum out-degree $s:=n-1=\frac{3^{k}-1}{2}-1$. Furthermore, for every
subdigraph $D^{\prime}\subseteq D_{k}$ on $n=\frac{3^{k}-1}{2}$ vertices,
denoting by $X$ the set of vertices in $D^{\prime}$, we have that
$\delta^{+}(D^{\prime})\leq\delta^{+}(D_{k}[X])=\delta^{+}(T_{k}[X])\leq\frac{\frac{3^{k}-1}{2}-k}{2}=\frac{s}{2}-(\frac{1}{2}+o(1))\log_{3}(s)$.
Thus, the statement of Theorem 1 follows from Theorem 2.

Let us now go about proving Theorem 2. The tournaments $(T_{k})_{k\geq 0}$
have the following simple recursive definition:

  * •

$T_{0}$ is the one-vertex-tournament.

  * •

For every integer $k\geq 0$, the tournament $T_{k+1}$ is obtained from the
disjoint union of $3$ isomorphic copies of $T_{k}$ on vertex sets
$A_{k},B_{k},C_{k}$ by adding all possible arcs from $A_{k}$ to $B_{k}$, from
$B_{k}$ to $C_{k}$ and from $C_{k}$ to $A_{k}$.

It is immediate from this definition that for every $k\geq 0$ the digraph
$T_{k}$ is a tournament on $3^{k}$ vertices and that every vertex has the same
in- and out-degree, hence, the out-degree of each vertex equals
$\frac{3^{k}-1}{2}$. We now prove the statement of Theorem 2 by induction on
$k$.

###### Proof of Theorem 2.

For $k=0$, every induced subdigraph of $T_{1}$ has minimum out-degree $0$ by
definition, which is equal to $\frac{\frac{3^{0}-1}{2}-0}{2}$, and thus the
induction basis holds. For the induction step, assume that for some integer
$k\geq 0$ we have established that
$\delta^{+}(T_{k}[X])\leq\frac{\frac{3^{k}-1}{2}-k}{2}$ for every $X\subseteq
V(T_{k})$ of size at most $\frac{3^{k}-1}{2}$, and let us show the
corresponding statement for $T_{k+1}$.

So let $X\subseteq V(T_{k+1})=A_{k}\cup B_{k}\cup C_{k}$ be given arbitrarily
such that $|X|\leq\frac{3^{k+1}-1}{2}$. W.l.o.g assume $X\neq\emptyset$.
Denote $X_{A}:=X\cap A_{k},X_{B}:=X\cap B_{k},X_{C}:=X\cap C_{k}$, and let
$x_{A}:=|X_{A}|,x_{B}:=|X_{B}|,x_{C}:=|X_{C}|$, so that
$x_{A}+x_{B}+x_{C}=|X|\leq\frac{3^{k+1}-1}{2}$.

Consider first the case that $\min\\{x_{A},x_{B},x_{C}\\}=0$. Then possibly
after relabeling, we may assume w.l.o.g. that $X_{B}=\emptyset$ and
$X_{A}\neq\emptyset$. Pick a vertex $x\in X_{A}$. Since all its out-neighbors
within $X$ are also contained in $A_{k}$, and since the copy of $T_{k}$
induced on $A_{k}$ is $\frac{3^{k}-1}{2}$-out-regular, this certifies that
$\delta^{+}(T_{k+1}[X])\leq\frac{3^{k}-1}{2}\leq\frac{\frac{3^{k+1}-1}{2}-(k+1)}{2}$,
as desired.

Next, suppose that $x_{A},x_{B},x_{C}>0$. We then have, by construction of
$T_{k+1}$, that

$\delta^{+}(T_{k+1}[X])=\min\\{\delta^{+}(T_{k+1}[X_{A}])+x_{B},\delta^{+}(T_{k+1}[X_{B}])+x_{C},\delta^{+}(T_{k+1}[X_{C}])+x_{A}\\}.$

Among the three numbers $x_{A},x_{B}$ and $x_{C}$, at least two are of size at
least $\frac{3^{k}+1}{2}$, or at least two are of size at most
$\frac{3^{k}-1}{2}$. Without loss of generality (possibly after relabeling),
we may assume that $x_{A}$ and $x_{B}$ have this property. We now proceed
according to the two possible cases.

###  Case 1. $x_{A},x_{B}\geq\frac{3^{k}+1}{2}$.

We want to estimate as follows:

$\delta^{+}(T_{k+1}[X])\leq\delta^{+}(T_{k+1}[X_{B}])+x_{C}.$

In order to estimate the minimum out-degree of $T_{k+1}[X_{B}]$, pick a proper
subset $S\subseteq X_{B}$ of size exactly $\frac{3^{k}-1}{2}$. By inductive
assumption (applicable since $T_{k+1}[B_{k}]$ is isomorphic to $T_{k}$), we
have $\delta^{+}(T_{k+1}[S])\leq\frac{\frac{3^{k}-1}{2}-k}{2}$. Since adding a
single vertex can increase the minimum out-degree by at most $1$, we conclude
that
$\delta^{+}(T_{k+1}[X_{B}])\leq\frac{\frac{3^{k}-1}{2}-k}{2}+\left(x_{B}-\frac{3^{k}-1}{2}\right)$.
Putting things together, we obtain:

$\delta^{+}(T_{k+1}[X])\leq\frac{\frac{3^{k}-1}{2}-k}{2}+\left(x_{B}-\frac{3^{k}-1}{2}\right)+x_{C}$
$=\underbrace{(x_{A}+x_{B}+x_{C})}_{\leq\frac{3^{k+1}-1}{2}}-\underbrace{x_{A}}_{\geq\frac{3^{k}+1}{2}}-\frac{\frac{3^{k}-1}{2}+k}{2}$
$\leq\frac{3^{k+1}-1}{2}-\frac{3^{k}+1}{2}-\frac{\frac{3^{k}-1}{2}+k}{2}$
$=\frac{\frac{3^{k+1}-1}{2}-(k+1)}{2},$

as desired, and this concludes the proof in the first case.

###  Case 2. $x_{A},x_{B}\leq\frac{3^{k}-1}{2}$.

In particular, $|X_{A}|\leq\frac{3^{k}-1}{2}$, so that we can apply the
inductive assumption to the set $X_{A}$ in the tournament $T_{k+1}[A_{k}]$,
which is isomorphic to $T_{k}$. We conclude that
$\delta^{+}(T_{k+1}[X_{A}])\leq\frac{\frac{3^{k}-1}{2}-k}{2}$. We can now
estimate the minimum out-degree in $X$ via

$\delta^{+}(T_{k+1}[X])\leq\delta^{+}(T_{k+1}[X_{A}])+x_{B}$
$\leq\frac{\frac{3^{k}-1}{2}-k}{2}+\frac{3^{k}-1}{2}$
$=\frac{\frac{3^{k+1}-1}{2}-(k+1)}{2},$

thus proving the desired bound on the minimum degree also in the second case.
This concludes the proof of the theorem. ∎

## References

  * [1] N. Alon. Splitting digraphs. _Combinatorics, Probability & Computing_, 15, 933–937 (2006). DOI
  * [2] N. Alon. A note on subdigraphs of digraphs with large outdegrees. _Discrete Mathematics_ , 49(3), 321–322 (1984). DOI