# Counting the parts divisible by $k$ in all the partitions of $n$ whose parts
have multiplicity less than $k$

Daniel Herden, Mark R. Sepanski, Jonathan Stanfill, Cordell C. Hammon, Joel
Henningsen, Henry Ickes, Jorge Marchena Menendez, Taylor Poe, Indalecio Ruiz,
Edward L. Smith<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Recent results by Andrews and Merca on the number of even parts in all
partitions of $n$ into distinct parts, $a(n)$, were derived via generating
functions. This paper extends these results to the number of parts divisible
by $k$ in all the partitions of $n$ for which the multiplicity of each part is
strictly less than $k$, $a_{k}(n)$. Moreover, a combinatorial proof is
provided using an extension of Glaisher’s bijection. Finally, we give the
generating functions for this new family of integer sequences and use it to
verify generalized pentagonal, triangular, and square power recurrence
relations.

###### Key words and phrases:

Partitions, combinatorial proofs, Glaisher’s bijection.

###### 2010 Mathematics Subject Classification:

Primary 11P83; Secondary 05A17, 05A19.

###### Contents

  1. 1 Introduction
  2. 2 Initial Definitions and Statement of Main Theorem
  3. 3 Combinatorial Identities
    1. 3.1 Combinatorial Definitions
    2. 3.2 Bijection between $B_{k,m}(n)$ and $C_{k,m}(n)$ for $m=0,1$
    3. 3.3 Bijection between $A_{k}(n)\,\dot{\cup}\,A^{\prime}_{k}(n)$ and $C_{k,0}(n)\,\dot{\cup}\,C_{k,1}(n)$
    4. 3.4 Proof of Main Result
  4. 4 Connections to Andrews, Merca
  5. 5 The Generating Function for $a_{k}(n)$
  6. 6 Recurrence Relations for $a_{k}(n)$
  7. 7 Concluding Remarks

##  1\. Introduction

Partitions of integers is a subject deeply intertwined with myriad subfields
of mathematics and has been studied by a host of great mathematicians,
Leibniz, Euler, Sylvester, Rogers, Hardy, MacMahon, Ramanujan, and Rademacher,
to name only a few [1].

The celebrated Euler Partition Identity [1, Corollary 1.2] says that the
number of partitions of $n$ into odd parts is equal to the number of
partitions of $n$ into distinct parts. Glaisher [8] found a beautiful
combinatorial proof and extension of this result. Namely, for any $k\geq 2$,
the number of partitions of $n$ with no part divisible by $k$ is equal to the
number of partitions of $n$ with each part repeated less than $k$ times.
Euler’s Identity is a special case of Glaisher’s result for $k=2$. Franklin
[6] also found an extension for which Euler’s Identity is a special case when
$j=0$.

######  Theorem 1.1 ([12]).

For any partition
$\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}})$,
denote by $\gamma_{\mathcal{O}}(\lambda)$ the number of even bases
$\lambda_{i}$, and by $\gamma_{\mathcal{D}}(\lambda)$ the number of repeated
bases $\lambda_{i}$. Then, for $j\geq 0$, the number of partitions of $n$ with
$\gamma_{\mathcal{O}}(\lambda)=j$ is equal to the number of partitions of $n$
with $\gamma_{\mathcal{D}}(\lambda)=j$.

There have been many related results that count partitions with particular
properties. Most notable among them may be the Rogers-Ramanujan Identity [1,
Corollary 7.6] that the number of partitions of $n$ in which the difference
between any two parts is at least $2$ equals the number of partitions of $n$
into parts $\equiv 1$ or $4$ mod $5$.

In this paper, we want to concentrate on Franklin’s result. Theorem 1.1 has
been rediscovered by Wilf [14] and, more recently, by Andrews [2] and Fu, Tang
[7]. In [2], Andrews used generating functions to prove a conjecture of Beck
that the number of partitions of $n$ with $\gamma_{\mathcal{O}}(\lambda)=1$
equals the difference between the number of parts in all odd partitions of $n$
and the number of parts in all distinct partitions of $n$. Later, Ballantine
and Bielak [4] gave a combinatorial proof of Beck’s conjecture, while Yang
[16] and Li, Wang [10] provided generalizations. Li and Wang also investigated
analogues of Beck’s conjecture for compositions [9]. In [3], Andrews and Merca
introduced new identities which link the number of even parts in the
partitions of $n$ into distinct parts, $a(n)$, to partitions of $n$ with
$\gamma_{\mathcal{O}}(\lambda)=1$.

In this note, we give a combinatorial proof of a generalization of the results
in [3]. In that paper, Andrews and Merca introduced four additional sequences:
the number of partitions of $n$ into an odd (even, respectively) number of
parts in which the set of even parts has only one element and the number of
partitions of $n$ in which exactly one part is repeated and this part is odd
(even, respectively).

Here, see §2, we let

$a_{k}(n)$

count the number of parts that are divisible by $k$ in all partitions of $n$
for which the multiplicity of each part is strictly less than $k$. We let

$b_{k,0}(n)\text{ and }b_{k,1}(n)$

count the partitions
$\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}})$
of $n$ satisfying (1) exactly one $\lambda_{i}$ is divisible by $k$ and (2)
the corresponding exponent $m_{i}$ is divisible by $k$ ($b_{k,0}(n)$) or not
divisible by $k$ ($b_{k,1}(n)$). Finally, we let

$c_{k,0}(n)\text{ and }c_{k,1}(n)$

count the partitions
$\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}})$
of $n$ satisfying (1) exactly one $\lambda_{i}^{m_{i}}$ has $m_{i}\geq k$ and
(2) the corresponding $\lambda_{i}$ is divisible by $k$ ($c_{k,0}(n)$) or not
divisible by $k$ ($c_{k,1}(n)$).

Our main result (Theorem 2.4), generalizing [3] for $k=2$, is

$b_{k,0}(n)=c_{k,0}(n),$ $b_{k,1}(n)=c_{k,1}(n),$
$a_{k}(n)=b_{k,1}(n)-(k-1)b_{k,0}(n)=c_{k,1}(n)-(k-1)c_{k,0}(n).$

Combinatorial proofs are given in §3. We recently discovered that Li, Wang,
[11, Theorems 1.11 and 1.13], already have a preprint that gives a very
different proof of this result.

The sequence $a(n)$ from Andrews and Merca [3] appears in the OEIS as A116680.
However, the family of integer sequences $a_{k}(n)$ appears to be new (for
$k>2$) and quite interesting. A table of small values may be found in §5. In
that same section, the generating function is also provided,

$a_{k}(n)=\prod_{n=1}^{\infty}\frac{1-q^{kn}}{1-q^{n}}\cdot\sum_{n=1}^{\infty}\frac{q^{kn}+2q^{2kn}+\dots+(k-1)q^{(k-1)kn}}{1+q^{kn}+q^{2kn}+\dots+q^{(k-1)kn}}.$

In §6, using the generating function, we show that the sequences $a_{k}(n)$
satisfy the generalized pentagonal number recurrence relation when $k\nmid n$
(Theorem 6.1),

$\displaystyle a_{k}(n)$
$\displaystyle=a_{k}(n-1)+a_{k}(n-2)-a_{k}(n-5)-a_{k}(n-7)$
$\displaystyle\quad\,+a_{k}(n-12)+a_{k}(n-15)-a_{k}(n-22)-a_{k}(n-26)+\cdots.$

They also satisfy the triangular number recurrence relation when $k$ is even
and $n$ is odd (Theorem 6.2),

$\displaystyle a_{k}(n)$
$\displaystyle=a_{k}(n-1)+a_{k}(n-3)-a_{k}(n-6)-a_{k}(n-10)$
$\displaystyle\quad\,+a_{k}(n-15)+a_{k}(n-21)-a_{k}(n-28)-a_{k}(n-36)+\cdots,$

and, still for $k$ even and $n$ odd, the square power recurrence relation
(Theorem 6.3),

$\displaystyle a_{k}(n)$
$\displaystyle=a_{k}(n-1)+a_{k}(n-2)-a_{k}(n-4)-a_{k}(n-8)$
$\displaystyle\quad\,+a_{k}(n-9)+a_{k}(n-18)-a_{k}(n-16)-a_{k}(n-32)+\cdots,$

while for $k$ and $n$ both even we have the square power identity (Theorem
6.4),

$\displaystyle a_{k}(n-1)-a_{k}(n-4)+a_{k}(n-9)-a_{k}(n-16)+\cdots$
$\displaystyle\qquad\,=a_{k}(n-2)-a_{k}(n-8)+a_{k}(n-18)-a_{k}(n-32)+\cdots.$

We also show that this identity is shared with the partition function (Theorem
6.5),

$\displaystyle p(n-1)-p(n-4)+p(n-9)-p(n-16)+\cdots$
$\displaystyle\qquad\,=p(n-2)-p(n-8)+p(n-18)-p(n-32)+\cdots=[p(n)-p_{\mathcal{DO}}(n)]/2,$

for $n$ even, where $p_{\mathcal{DO}}(n)$ is the number of partitions of $n$
into distinct odd parts.

In addition, we give some thoughts and conjectures on some intriguing new
possible recurrence relations.

##  2\. Initial Definitions and Statement of Main Theorem

For $n\in\mathbb{Z}^{\geq 0}$, let $\mathcal{P}(n)$ be the set of partitions
of $n$. In general, for $\lambda\in\mathcal{P}(n)$, we write

$\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}})$

with distinct $\lambda_{i}$, each $m_{i}\geq 1$, and
$n=\sum_{i=1}^{\ell}m_{i}\lambda_{i}$, and we consider partitions equivalent
up to reordering. We refer to $m_{i}$ as the _multiplicity_ of the part
$\lambda_{i}$. When concatenating such sequences, we combine terms with the
same base and add the corresponding exponents.

######  Definition 2.1.

Let $n,k\in\mathbb{Z}^{\geq 0}$ with $k\geq 2$. Let

$a_{k}(n)$

count the number of parts (with multiplicity) that are divisible by $k$ in all
partitions of $n$ for which the multiplicity of each part is strictly less
than $k$.

For example, the partitions of $n=9$ are

$\displaystyle(9),\,(8,1),\,(7,2),\,(7,1^{2}),\,(6,3),\,(6,2,1),\,(6,1^{3}),\,(5,4),\,(5,3,1),\,(5,2^{2}),\,$
$\displaystyle(5,2,1^{2}),\,(5,1^{4}),\,(4^{2},1),\,(4,3,2),\,(4,3,1^{2}),\,(4,2^{2},1),\,(4,2,1^{3}),\,(4,1^{5}),\,$
$\displaystyle(3^{3}),\,(3^{2},2,1),\,(3^{2},1^{3}),\,(3,2^{3}),\,(3,2^{2},1^{2}),\,(3,2,1^{4}),\,(3,1^{6}),\,(2^{4},1),\,$
$\displaystyle(2^{3},1^{3}),\,(2^{2},1^{5}),\,(2,1^{7}),\,(1^{9}).$

The partitions of $9$ with the multiplicity of each part less than $k=3$ are

$\displaystyle(9),\,(8,1),\,(7,2),\,(7,1^{2}),\,(6,3),\,(6,2,1),\,(5,4),\,(5,3,1),\,(5,2^{2}),\,$
$\displaystyle(5,2,1^{2}),\,(4^{2},1),\,(4,3,2),\,(4,3,1^{2}),\,(4,2^{2},1),\,(3^{2},2,1),\,(3,2^{2},1^{2}).$

Of these, the ones that have parts divisible by $3$ are

$\displaystyle(9),\,(6,3),\,(6,2,1),\,(5,3,1),\,(4,3,2),\,(4,3,1^{2}),\,(3^{2},2,1),\,(3,2^{2},1^{2}).$

As $a_{3}(9)$ counts the parts divisible by $3$ with multiplicity, we see that

$a_{3}(9)=10.$

######  Definition 2.2.

Let $n,k\in\mathbb{Z}^{\geq 0}$ with $k\geq 2$.

  * $(a)$

Let

$b_{k,0}(n)$

count all $\lambda\in\mathcal{P}(n)$,
$\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}})$,
satisfying

    * $(1)$

exactly one $\lambda_{i}$ is divisible by $k$, and

    * $(2)$

the corresponding exponent $m_{i}$ is divisible by $k$.

  * $(b)$

Let

$b_{k,1}(n)$

count all $\lambda\in\mathcal{P}(n)$,
$\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}})$,
satisfying

    * $(1)$

exactly one $\lambda_{i}$ is divisible by $k$, and

    * $(2)$

the corresponding exponent $m_{i}$ is not divisible by $k$.

For example, the partitions of $n=9$ with exactly one base $\lambda_{i}$
divisible by $k=3$ are

$\displaystyle(9),\,(6,2,1),\,(6,1^{3}),\,(5,3,1),\,(4,3,2),\,(4,3,1^{2}),\,(3^{3}),\,$
$\displaystyle(3^{2},2,1),\,(3^{2},1^{3}),\,(3,2^{3}),\,(3,2^{2},1^{2}),\,(3,2,1^{4}),\,(3,1^{6}).$

Of these, the only one whose corresponding exponent $m_{i}$ is divisible by
$3$ is

$(3^{3})$

so

$b_{3,0}(9)=1\qquad\mbox{and}\qquad b_{3,1}(9)=12.$

######  Definition 2.3.

Let $n,k\in\mathbb{Z}^{\geq 0}$ with $k\geq 2$.

  * $(a)$

Let

$c_{k,0}(n)$

count all $\lambda\in\mathcal{P}(n)$,
$\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}})$,
satisfying

    * $(1)$

exactly one $\lambda_{i}^{m_{i}}$ has $m_{i}\geq k$, and

    * $(2)$

the corresponding $\lambda_{i}$ is divisible by $k$.

  * $(b)$

Let

$c_{k,1}(n)$

count all $\lambda\in\mathcal{P}(n)$,
$\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}})$,
satisfying

    * $(1)$

exactly one $\lambda_{i}^{m_{i}}$ has $m_{i}\geq k$, and

    * $(2)$

the corresponding $\lambda_{i}$ is not divisible by $k$.

For example, the partitions of $n=9$ with exactly one $\lambda_{i}$ with
multiplicity $m_{i}$ at least $k=3$ are

$\displaystyle(6,1^{3}),\,(5,1^{4}),\,(4,2,1^{3}),\,(4,1^{5}),\,(3^{3}),\,(3^{2},1^{3}),\,(3,2^{3}),\,$
$\displaystyle(3,2,1^{4}),\,(3,1^{6}),\,(2^{4},1),\,(2^{2},1^{5}),\,(2,1^{7}),\,(1^{9}).$

Of these, the only one whose corresponding $\lambda_{i}$ is divisible by $3$
is

$(3^{3})$

so

$c_{3,0}(9)=1\qquad\mbox{and}\qquad c_{3,1}(9)=12.$

We will prove the following result in this paper. Li, Wang have a preprint,
[11, Theorems 1.11 and 1.13], that gives an alternate proof of this result.

######  Main Theorem 2.4.

For all $n,k\in\mathbb{Z}^{\geq 0}$ with $k\geq 2$, the following holds:

  * $(a)$

$b_{k,0}(n)=c_{k,0}(n)$ and $b_{k,1}(n)=c_{k,1}(n)$

  * $(b)$

$a_{k}(n)=b_{k,1}(n)-(k-1)b_{k,0}(n)=c_{k,1}(n)-(k-1)c_{k,0}(n).$

For $n=9$ and $k=3$, we have
$a_{3}(9)=10=b_{3,1}(9)-2b_{3,0}(9)=c_{3,1}(9)-2c_{3,0}(9).$

##  3\. Combinatorial Identities

###  3.1. Combinatorial Definitions

######  Definition 3.1.

Let

$\displaystyle A_{k}(n)$
$\displaystyle=\\{(\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}}),\lambda_{i_{0}},m)\mid$
$\displaystyle\qquad\quad\lambda\in\mathcal{P}(n),\,m_{i}<k\,\forall i,\,1\leq
i_{0}\leq\ell,\,k\mid\lambda_{i_{0}},\,0\leq m<m_{i_{0}}\\}.$

By construction,

$a_{k}(n)=|A_{k}(n)|.$

Let

$\displaystyle A_{k}^{\prime}(n)$
$\displaystyle=\\{(\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}}),\lambda_{i_{0}},m)\mid$
$\displaystyle\lambda\in\mathcal{P}(n),\,1\leq
i_{0}\leq\ell,\,m_{i}<k\,\forall i\not=i_{0},\,m_{i_{0}}\geq
k,\,k\mid\lambda_{i_{0}},\,0\leq m<k\\}.$

For example, continuing with $n=9$ and $k=3$,

$\displaystyle A_{3}(9)$
$\displaystyle=\\{((9),9,0),\,((6,3),6,0),\,((6,3),3,0),\,((6,2,1),6,0),$
$\displaystyle\quad\ ((5,3,1),3,0),\,((4,3,2),3,0),\,((4,3,1^{2}),3,0),$
$\displaystyle\quad\
((3^{2},2,1),3,0),\,((3^{2},2,1),3,1),\,((3,2^{2},1^{2}),3,0)\\}$

and

$\displaystyle A^{\prime}_{3}(9)=$
$\displaystyle\\{((3^{3}),3,0),((3^{3}),3,1),((3^{3}),3,2)\\}.$

######  Definition 3.2.

Let

$\displaystyle B_{k,0}(n)$
$\displaystyle=\\{\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}},a^{b})\in\mathcal{P}(n)\mid
k\nmid\lambda_{i}\,\forall i,\,k\mid a,\,k\mid b\\},$

and

$\displaystyle B_{k,1}(n)$
$\displaystyle=\\{\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}},a^{b})\in\mathcal{P}(n)\mid
k\nmid\lambda_{i}\,\forall i,\,k\mid a,\,k\nmid b\\}.$

Note that $\ell$ may be zero above and that $b\geq 1$. By construction, we
have for $m=0,1$,

$b_{k,m}(n)=|B_{k,m}(n)|.$

Continuing with $n=9$ and $k=3$, we see that

$B_{3,0}(9)=\\{(3^{3})\\}$

and

$\displaystyle B_{3,1}(9)$
$\displaystyle=\\{(9),\,(6,2,1),\,(6,1^{3}),\,(5,3,1),\,(4,3,2),\,(4,3,1^{2}),\,$
$\displaystyle\quad\
(3^{2},2,1),\,(3^{2},1^{3}),\,(3,2^{3}),\,(3,2^{2},1^{2}),\,(3,2,1^{4}),\,(3,1^{6})\\}.$

######  Definition 3.3.

Let

$\displaystyle C_{k,0}(n)$
$\displaystyle=\\{\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}},a^{b})\in\mathcal{P}(n)\mid
m_{i}<k\,\forall i,\,b\geq k,\,k\mid a\\},$

and

$\displaystyle C_{k,1}(n)$
$\displaystyle=\\{\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}},a^{b})\in\mathcal{P}(n)\mid
m_{i}<k\,\forall i,\,b\geq k,\,k\nmid a\\}.$

Note that $\ell$ may be zero above and that $b\geq 1$. By construction, we
have

$c_{k,m}(n)=|C_{k,m}(n)|$

for $m=0,1$, and

$|A^{\prime}_{k}(n)|=kc_{k,0}(n).$

Again with $n=9$ and $k=3$, we see that

$\displaystyle C_{3,0}(9)=$ $\displaystyle\\{(3^{3})\\}$

and

$\displaystyle C_{3,1}(9)$
$\displaystyle=\\{(6,1^{3}),\,(5,1^{4}),\,(4,2,1^{3}),\,(4,1^{5}),\,(3^{2},1^{3}),\,(3,2^{3}),$
$\displaystyle\quad\
(3,2,1^{4}),\,(3,1^{6}),\,(2^{4},1),\,(2^{2},1^{5}),\,(2,1^{7}),\,(1^{9})\\}.$

In the next sections, we will exhibit bijections between

$B_{k,m}(n)\text{ and }C_{k,m}(n)$

for $m=0,1$, and between

$A_{k}(n)\,\dot{\cup}\,A^{\prime}_{k}(n)\text{ and
}C_{k,0}(n)\,\dot{\cup}\,C_{k,1}(n).$

###  3.2. Bijection between $B_{k,m}(n)$ and $C_{k,m}(n)$ for $m=0,1$

The following bijection is an extension of Glaisher’s combinatorial proof [8]
of the Euler Partition Identity.

######  Theorem 3.4.

Let

$\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}},a^{b})\in
B_{k,m}(n).$

Expand each $m_{i}$ in base $k$ as

$m_{i}=\sum_{j\in S_{i}}c_{ij}k^{j}$

with $0<c_{ij}<k$ for $j$ in some index set $S_{i}$.

Write $\frown$ for sequence concatenation. The mapping

$\lambda\mapsto((k^{j}\lambda_{i})^{c_{ij}})_{1\leq i\leq\ell,\,j\in
S_{i}}\frown(b^{a})$

gives a bijection between

$B_{k,m}(n)\longleftrightarrow C_{k,m}(n),$

for $m=0,1$. (Note that $b$ may also appear once among the $k^{j}\lambda_{i}$.
In that case, combine those two terms with the same base by adding the
corresponding exponents.)

###### Proof.

For injectivity, first note that $b$ in the statement of the Theorem is
uniquely recovered from its image as the only part of the partition on the
right hand side with multiplicity at least $k$. The value of $a$ is then
uniquely recovered by writing the exponent of $b$ as $a+r$ with $0\leq r<k$
and $k\mid a$. The $\lambda_{i}^{m_{i}}$ are then uniquely recovered by
undoing the base $k$ expansion with the remaining terms (including $b^{r}$
when $r\not=0$), i.e., extracting the largest power of $k$ dividing each term,
moving it to the exponent, and combining terms with the same base.

Surjectivity is similar. Start with
$\nu=(\nu_{1}^{n_{1}},\nu_{2}^{n_{2}},\ldots,\nu_{\ell}^{n_{\ell}},b^{\alpha})\in
C_{k,m}(n)$. Write $\alpha$ as $a+r$ with $0\leq r<k$ and $k\mid a$. The
preimage of $\nu$ is constructed via $a$, $b$, and the $\lambda_{i}^{m_{i}}$
resulting from undoing the base $k$ expansion on the remaining terms
(including $b^{r}$ when $r\not=0$) as above. ∎

######  Remark 3.5.

Our bijection $B_{2,m}(n)\longleftrightarrow C_{2,m}(n)$ provides an
alternative proof of Theorem 1.1 for the case $j=1$. In particular, note that
this bijection extends canonically to a bijection
$B_{2,0}(n)\dot{\cup}B_{2,1}(n)\longleftrightarrow
C_{2,0}(n)\dot{\cup}C_{2,1}(n)$, where $B_{2,0}(n)\dot{\cup}B_{2,1}(n)$ is the
collection of all partitions $\lambda$ of $n$ with
$\gamma_{\mathcal{O}}(\lambda)=1$ and $C_{2,0}(n)\dot{\cup}C_{2,1}(n)$ is the
collection of all partitions $\lambda$ of $n$ with
$\gamma_{\mathcal{D}}(\lambda)=1$.

###  3.3. Bijection between $A_{k}(n)\,\dot{\cup}\,A^{\prime}_{k}(n)$ and
$C_{k,0}(n)\,\dot{\cup}\,C_{k,1}(n)$

######  Theorem 3.6.

Let

$\mu=(\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}}),\lambda_{i_{0}},m)\in
A_{k}(n)\,\dot{\cup}\,A^{\prime}_{k}(n).$

Write $\frown$ for sequence concatenation. The mapping

$\mu\mapsto(\lambda_{i}^{m_{i}})_{i\neq
i_{0}}\frown(\lambda_{i_{0}}^{m},(m_{i_{0}}-m)^{\lambda_{i_{0}}})$

gives a bijection between

$A_{k}(n)\,\dot{\cup}\,A^{\prime}_{k}(n)\longleftrightarrow
C_{k,0}(n)\,\dot{\cup}\,C_{k,1}(n).$

(Note that $(m_{i_{0}}-m)$ may also appear once among the $\lambda_{i}$,
$i\not=i_{0}$. In that case, combine those two terms with the same base by
adding the corresponding exponents.)

###### Proof.

For injectivity, first note that the $\lambda_{i_{0}}$ in the statement of the
theorem is uniquely recovered from its image by writing the unique exponent
that is at least $k$ as $\lambda_{i_{0}}+r$ where $0\leq r<k$ and
$k\mid\lambda_{i_{0}}$. Then $m$ is recovered uniquely as the exponent of
$\lambda_{i_{0}}$ (so as $0$ if $\lambda_{i_{0}}$ does not appear). From that,
$m_{i_{0}}$ is obtained from the base of the $\lambda_{i_{0}}+r$ exponent by
adding $m$. After that, removing $\lambda_{i_{0}}^{m}$ and
$(m_{i_{0}}-m)^{\lambda_{i_{0}}}$ from the partition determines the remaining
$\lambda_{i}^{m_{i}}$, $i\neq i_{0}$.

Surjectivity is similar. Start with
$\nu=(\nu_{1}^{n_{1}},\nu_{2}^{n_{2}},\ldots,\nu_{\ell}^{n_{\ell}},b^{a})\in
C_{k,0}(n)\,\dot{\cup}\,C_{k,1}(n)$. To construct its preimage, write $a$ as
$\lambda_{i_{0}}+r$ with $0\leq r<k$ and $k\mid\lambda_{i_{0}}$. Let $m$ be
the exponent of $\lambda_{i_{0}}$, and let $m_{i_{0}}$ be $b+m$. The rest of
the $\lambda_{i}^{m_{i}}$, $i\not=i_{0}$, are chosen to be the remaining terms
after removing $\lambda_{i_{0}}^{m}$ and $(m_{i_{0}}-m)^{\lambda_{i_{0}}}$
from the partition. ∎

###  3.4. Proof of Main Result

######  Combinatorial proof of Theorem 2.4.

This is immediate as we now have

$\displaystyle b_{k,m}(n)=|B_{k,m}(n)|=|C_{k,m}(n)|=c_{k,m}(n),$

while

$\displaystyle a_{k}(n)+kc_{k,0}(n)=\,\mid
A_{k}(n)\,\dot{\cup}\,A^{\prime}_{k}(n)\mid=\,\mid
C_{k,0}(n)\,\dot{\cup}\,C_{k,1}(n)\mid=c_{k,0}(n)+c_{k,1}(n),$

gives

$\displaystyle a_{k}(n)=c_{k,1}(n)-(k-1)c_{k,0}(n).\qed$

##  4\. Connections to Andrews, Merca

######  Theorem 4.1.

Comparing our notation to that of Andrews, Merca [3], we have the following
correlations.

  * $(a)$

$a(n)=a_{2}(n)$, $c_{e}(n)=c_{2,0}(n)$ and $c_{o}(n)=c_{2,1}(n)$.

  * $(b)$

$b_{e}(n)=\begin{cases}b_{2,0}(n)&\text{if $n$ is even,}\\\
b_{2,1}(n)&\text{if $n$ is odd,}\end{cases}$ and
$b_{o}(n)=\begin{cases}b_{2,1}(n)&\text{if $n$ is even,}\\\
b_{2,0}(n)&\text{if $n$ is odd.}\end{cases}$

###### Proof.

$(a)$ follows trivially from the definitions of $a_{k}(n)$ and $c_{k,m}(n)$.
For instance, by definition $a(n)$ and $a_{2}(n)$ both count the number of
even parts in all partitions of $n$ into distinct parts. For $(b)$, let
$\lambda=(\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\ldots,\lambda_{\ell}^{m_{\ell}},a^{b})$
be an element of $B_{k,0}(n)\,\dot{\cup}\,B_{k,1}(n)$. If we take $n$ to be
even, and if $2\mid b$, then there must be an even number of odd parts in
$\lambda$, and if $2\nmid b$, then there must be an odd number of odd parts in
$\lambda$. So, $b_{2,0}(n)=b_{e}(n)$ and $b_{2,1}=b_{o}(n)$. For $n$ odd, we
argue similarly. ∎

From this, [3, Theorem 1.4] and [3, Theorem 1.5] become special cases of
Theorem 2.4 for $k=2$.

##  5\. The Generating Function for $a_{k}(n)$

For $k\geq 2$, the following calculation of formal power series provides the
generating function of the sequence $a_{k}(n)$.

$\displaystyle\sum_{n=0}^{\infty}a_{k}(n)q^{n}$
$\displaystyle=\frac{d}{dz}\bigg{[}\prod_{\begin{subarray}{c}n=1\\\ k\nmid
n\end{subarray}}^{\infty}(1\\!+\\!q^{n}\\!+\\!(q^{n})^{2}\\!+\dots+\\!(q^{n})^{k-1})\prod_{\begin{subarray}{c}n=1\\\
k\mid
n\end{subarray}}^{\infty}(1\\!+\\!zq^{n}\\!+\\!(zq^{n})^{2}\\!+\dots+\\!(zq^{n})^{k-1})\bigg{]}_{\\!z=1}$
$\displaystyle=\prod_{\begin{subarray}{c}n=1\\\ k\nmid
n\end{subarray}}^{\infty}\frac{1-q^{kn}}{1-q^{n}}\cdot\frac{d}{dz}\bigg{[}\prod_{\begin{subarray}{c}n=1\\\
k\mid
n\end{subarray}}^{\infty}\frac{1-z^{k}q^{kn}}{1-zq^{n}}\bigg{]}_{\\!z=1}$
$\displaystyle=\prod_{\begin{subarray}{c}n=1\\\ k\nmid
n\end{subarray}}^{\infty}\frac{1-q^{kn}}{1-q^{n}}\cdot\bigg{[}\prod_{\begin{subarray}{c}n=1\\\
k\mid
n\end{subarray}}^{\infty}\frac{1-z^{k}q^{kn}}{1-zq^{n}}\cdot\sum_{\begin{subarray}{c}n=1\\\
k\mid
n\end{subarray}}^{\infty}\frac{q^{n}\\!+\\!2q^{n}(zq^{n})\\!+\dots+\\!(k-1)q^{n}(zq^{n})^{k-2}}{1\\!+\\!zq^{n}\\!+\\!(zq^{n})^{2}\\!+\dots+\\!(zq^{n})^{k-1}}\bigg{]}_{\\!z=1}$
$\displaystyle=\prod_{n=1}^{\infty}\frac{1-q^{kn}}{1-q^{n}}\cdot\sum_{n=1}^{\infty}\frac{q^{kn}+2q^{2kn}+\dots+(k-1)q^{(k-1)kn}}{1+q^{kn}+q^{2kn}+\dots+q^{(k-1)kn}}$

Table 1 lists $a_{k}(n)$ for some small values of $n$ and $k$. The sequence
$a_{2}(n)$ is documented on OEIS [13, A116680].

| $k=2$ | $k=3$ | $k=4$ | $k=5$ | $k=6$ | $k=7$ | $k=8$
---|---|---|---|---|---|---|---
$n=0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$
$n=1$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$
$n=2$ | $1$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$
$n=3$ | $1$ | $1$ | $0$ | $0$ | $0$ | $0$ | $0$
$n=4$ | $1$ | $1$ | $1$ | $0$ | $0$ | $0$ | $0$
$n=5$ | $2$ | $2$ | $1$ | $1$ | $0$ | $0$ | $0$
$n=6$ | $4$ | $4$ | $2$ | $1$ | $1$ | $0$ | $0$
$n=7$ | $5$ | $6$ | $3$ | $2$ | $1$ | $1$ | $0$
$n=8$ | $5$ | $9$ | $6$ | $3$ | $2$ | $1$ | $1$
$n=9$ | $8$ | $10$ | $8$ | $5$ | $3$ | $2$ | $1$
$n=10$ | $11$ | $16$ | $13$ | $8$ | $5$ | $3$ | $2$
$n=11$ | $14$ | $21$ | $18$ | $12$ | $7$ | $5$ | $3$
$n=12$ | $18$ | $31$ | $26$ | $17$ | $12$ | $7$ | $5$
$n=13$ | $23$ | $39$ | $36$ | $25$ | $16$ | $11$ | $7$
$n=14$ | $29$ | $54$ | $51$ | $35$ | $24$ | $16$ | $11$
$n=15$ | $37$ | $69$ | $68$ | $48$ | $33$ | $23$ | $15$

Table 1. Small Values of $a_{k}(n)$

######  Remark 5.1.

It can easily be verified from the definitions that

$a_{k}(n)=\begin{cases}0&\text{for $1\leq n<k$},\\\ p(n-k)&\mbox{for $k\leq
n<2k$},\\\ p(k)+1&\mbox{for $n=2k$}\end{cases}$

for all $k\geq 3$, where $p(n)$ denotes Euler’s partition function. These
patterns are manifest in Table 1.

##  6\. Recurrence Relations for $a_{k}(n)$

One deduces the following two recurrence relations for $a_{k}(n)$ from the
generating function, from which setting $k=2$ recovers those found in [3].
Note that these recurrence relations are also satisfied by $p(n)$.

######  Theorem 6.1.

For $k\nmid n$, the sequence $a_{k}(n)$ satisfies the generalized pentagonal
number recurrence relation

$\displaystyle a_{k}(n)$
$\displaystyle=a_{k}(n-1)+a_{k}(n-2)-a_{k}(n-5)-a_{k}(n-7)$
$\displaystyle\quad\,+a_{k}(n-12)+a_{k}(n-15)-a_{k}(n-22)-a_{k}(n-26)+\cdots.$

###### Proof.

From the generating function for $a_{k}(n)$, one can write

$\displaystyle(q;q)_{\infty}\sum_{n=0}^{\infty}a_{k}(n)q^{n}=(q^{k};q^{k})_{\infty}\sum_{n=1}^{\infty}\frac{q^{kn}+2q^{2kn}+\dots+(k-1)q^{(k-1)kn}}{1+q^{kn}+q^{2kn}+\dots+q^{(k-1)kn}},$

where $(a;q)_{\infty}$ represents the _$q$ -series_ or _$q$ -Pochhammer
symbol_

$\displaystyle(a;q)_{\infty}=\prod_{n=0}^{\infty}(1-aq^{n}).$

Substituting Euler’s pentagonal number theorem [1, Corollary 1.7] on the
l.h.s.,

$\displaystyle(q;q)_{\infty}=\sum_{n=-\infty}^{\infty}(-1)^{n}q^{n(3n-1)/2},$

and noting that the r.h.s. is a power series in $q^{k}$ leads to the
recurrence relation. Namely, the coefficients of all $q^{n},\ k\nmid n,$ are
equal to zero, hence it quickly follows that

$\displaystyle 0$
$\displaystyle=a_{k}(n)-a_{k}(n-1)-a_{k}(n-2)+a_{k}(n-5)+a_{k}(n-7)-\cdots.\qed$

######  Theorem 6.2.

For $k$ even, $n$ odd, the sequence $a_{k}(n)$ satisfies the triangular number
recurrence relation

$\displaystyle a_{k}(n)$
$\displaystyle=a_{k}(n-1)+a_{k}(n-3)-a_{k}(n-6)-a_{k}(n-10)$
$\displaystyle\quad\,+a_{k}(n-15)+a_{k}(n-21)-a_{k}(n-28)-a_{k}(n-36)+\cdots.$

###### Proof.

From the generating function for $a_{k}(n)$, one can further write

$\displaystyle(q;q)_{\infty}$
$\displaystyle(-q^{2};q^{2})_{\infty}\sum_{n=0}^{\infty}a_{k}(n)q^{n}$
$\displaystyle=(-q^{2};q^{2})_{\infty}(q^{k};q^{k})_{\infty}\sum_{n=1}^{\infty}\frac{q^{kn}+2q^{2kn}+\dots+(k-1)q^{(k-1)kn}}{1+q^{kn}+q^{2kn}+\dots+q^{(k-1)kn}}.$

Substituting on the l.h.s. the theta identity [1, Equation (2.2.13)],

$\displaystyle(q;q)_{\infty}(-q^{2};q^{2})_{\infty}=\dfrac{(q^{2};q^{2})_{\infty}}{(-q;q^{2})_{\infty}}=\sum_{n=0}^{\infty}(-q)^{n(n+1)/2},$

and noting that the r.h.s. is a power series in $q^{2}$ leads to the
recurrence relation. Namely, the coefficients of all $q^{n},$ $k$ even, $n$
odd, are equal to zero, hence it quickly follows that

$\displaystyle 0$
$\displaystyle=a_{k}(n)-a_{k}(n-1)-a_{k}(n-3)+a_{k}(n-6)+a_{k}(n-10)-\cdots.\qed$

We include another particularly nice set of recurrence relations for
$a_{k}(n)$ which involves square powers and their doubles. Once again, these
recurrence relations are shared by $p(n)$ (see [5, Theorem 1]).

######  Theorem 6.3.

For $k$ even, $n$ odd, the sequence $a_{k}(n)$ satisfies the square power
recurrence relation

$\displaystyle
a_{k}(n)=\sum_{m=1}^{\left\lfloor\sqrt{n}\right\rfloor}(-1)^{m-1}a_{k}(n-m^{2})+\sum_{m=1}^{\left\lfloor\sqrt{\frac{n}{2}}\right\rfloor}(-1)^{m-1}a_{k}(n-2m^{2}).$

Thus

$\displaystyle a_{k}(n)$
$\displaystyle=a_{k}(n-1)+a_{k}(n-2)-a_{k}(n-4)-a_{k}(n-8)$
$\displaystyle\quad\,+a_{k}(n-9)+a_{k}(n-18)-a_{k}(n-16)-a_{k}(n-32)+\cdots.$

###### Proof.

From the generating function for $a_{k}(n)$ we define the series

(6.1) $\displaystyle
f_{k}(q)=(q;q)_{\infty}(q;q^{2})_{\infty}\sum_{n=0}^{\infty}a_{k}(n)q^{n}$
$\displaystyle\qquad\
=(q;q^{2})_{\infty}(q^{k};q^{k})_{\infty}\sum_{n=1}^{\infty}\frac{q^{kn}+2q^{2kn}+\dots+(k-1)q^{(k-1)kn}}{1+q^{kn}+q^{2kn}+\dots+q^{(k-1)kn}}.$

Using Euler’s identity

$\displaystyle(-q;q)_{\infty}=\dfrac{1}{(q;q^{2})_{\infty}},$

one substitutes Gauss’s square power identity [1, Equation (2.2.12)] on the
l.h.s,

$\displaystyle(q;q)_{\infty}(q;q^{2})_{\infty}=\dfrac{(q;q)_{\infty}}{(-q;q)_{\infty}}=\sum_{m=-\infty}^{\infty}(-1)^{m}q^{m^{2}}.$

Thus, the coefficient of $q^{n}$ of the series $f_{k}(q)$ is given by

(6.2)
$\displaystyle\sum_{m=-\infty}^{\infty}(-1)^{m}a_{k}(n-m^{2})=a(n)-2\sum_{m=1}^{\left\lfloor\sqrt{n}\right\rfloor}(-1)^{m-1}a_{k}(n-m^{2}).$

Next we consider the series

(6.3) $\displaystyle
g_{k}(q)=(q;q)_{\infty}(-q;q^{2})_{\infty}\sum_{n=0}^{\infty}a_{k}(n)q^{n}$
$\displaystyle\qquad\
=(-q;q^{2})_{\infty}(q^{k};q^{k})_{\infty}\sum_{n=1}^{\infty}\frac{q^{kn}+2q^{2kn}+\dots+(k-1)q^{(k-1)kn}}{1+q^{kn}+q^{2kn}+\dots+q^{(k-1)kn}}.$

Using once more Gauss’s square power identity, on the l.h.s we can substitute

$\displaystyle(q;q)_{\infty}(-q;q^{2})_{\infty}=\dfrac{(q^{2};q^{2})_{\infty}}{(-q^{2};q^{2})_{\infty}}=\sum_{m=-\infty}^{\infty}(-1)^{m}(q^{2})^{m^{2}}=\sum_{m=-\infty}^{\infty}(-1)^{m}q^{2m^{2}},$

and the coefficient of $q^{n}$ of the series $g_{k}(q)$ is given by

(6.4)
$\displaystyle\sum_{m=-\infty}^{\infty}(-1)^{m}a_{k}(n-2m^{2})=a(n)-2\sum_{m=1}^{\left\lfloor\sqrt{\frac{n}{2}}\right\rfloor}(-1)^{m-1}a_{k}(n-2m^{2}).$

Comparing the r.h.s of Equations (6.1) and (6.3), we see $g_{k}(q)=f_{k}(-q)$.
Hence, as $n$ is odd, the expressions in Equations (6.2) and (6.4) differ only
by a sign. In particular, adding gives

$\displaystyle
2a(n)-2\sum_{m=1}^{\left\lfloor\sqrt{n}\right\rfloor}(-1)^{m-1}a_{k}(n-m^{2})-2\sum_{m=1}^{\left\lfloor\sqrt{\frac{n}{2}}\right\rfloor}(-1)^{m-1}a_{k}(n-2m^{2})=0,$

and the desired recurrence follows. ∎

Theorem 6.3 has the following surprising counterpart for the case $k$ and $n$
even.

######  Theorem 6.4.

For $k$ and $n$ both even, we have the identity

$\displaystyle\sum_{m=1}^{\left\lfloor\sqrt{n}\right\rfloor}(-1)^{m-1}a_{k}(n-m^{2})=\sum_{m=1}^{\left\lfloor\sqrt{\frac{n}{2}}\right\rfloor}(-1)^{m-1}a_{k}(n-2m^{2}).$

###### Proof.

We define the series $f_{k}(q)$ and $g_{k}(q)$ with $g_{k}(q)=f_{k}(-q)$ as in
the proof of Theorem 6.3. This time $n$ is even, and the expressions in
Equations (6.2) and (6.4) must be equal. In particular,

$\displaystyle
a(n)-2\sum_{m=1}^{\left\lfloor\sqrt{n}\right\rfloor}(-1)^{m-1}a_{k}(n-m^{2})=a(n)-2\sum_{m=1}^{\left\lfloor\sqrt{\frac{n}{2}}\right\rfloor}(-1)^{m-1}a_{k}(n-2m^{2}),$

and the desired identity follows. ∎

As would be expected, the identity of Theorem 6.4 is once again shared by
$p(n)$.

######  Theorem 6.5.

For $n$ even, we have the identity

$\displaystyle\sum_{m=1}^{\left\lfloor\sqrt{n}\right\rfloor}(-1)^{m-1}p(n-m^{2})=\sum_{m=1}^{\left\lfloor\sqrt{\frac{n}{2}}\right\rfloor}(-1)^{m-1}p(n-2m^{2})=\frac{p(n)-p_{\mathcal{DO}}(n)}{2},$

where $p_{\mathcal{DO}}(n)$ denotes the number of partitions of $n$ into
distinct odd parts.

###### Proof.

The proof of the first equality is similar to Theorems 6.3 and 6.4, using the
series

$\displaystyle(q;q)_{\infty}(q;q^{2})_{\infty}\sum_{n=0}^{\infty}p(n)q^{n}\\!=(q;q^{2})_{\infty}\mbox{
and
}(q;q)_{\infty}(-q;q^{2})_{\infty}\sum_{n=0}^{\infty}p(n)q^{n}\\!=(-q;q^{2})_{\infty}.$

The second equality then immediately follows from an identity in [5, Theorem
1] for $n$ even,

$p(n)-\sum_{m=1}^{\left\lfloor\sqrt{n}\right\rfloor}(-1)^{m-1}p(n-m^{2})-\sum_{m=1}^{\left\lfloor\sqrt{\frac{n}{2}}\right\rfloor}(-1)^{m-1}p(n-2m^{2})=p_{\mathcal{DO}}(n).\hfill\mbox{}\qed$

##  7\. Concluding Remarks

When considering the proof of Theorem 6.2, one notices that multiplying by
$(-q^{2};q^{2})_{\infty}$ leads directly to the triangular number recurrence
relation. This naturally raises the question of what recurrence relations
occur, if any, when one multiplies instead by $(-q^{m};q^{m})_{\infty},\ 3\leq
m\leq k.$ In particular, for $m\mid k$, one obtains

$\displaystyle(q;q)_{\infty}$
$\displaystyle(-q^{m};q^{m})_{\infty}\sum_{n=0}^{\infty}a_{k}(n)q^{n}$
$\displaystyle=(-q^{m};q^{m})_{\infty}(q^{k};q^{k})_{\infty}\sum_{n=1}^{\infty}\frac{q^{kn}+2q^{2kn}+\dots+(k-1)q^{(k-1)kn}}{1+q^{kn}+q^{2kn}+\dots+q^{(k-1)kn}},$

where the r.h.s. is now a power series in $q^{m}$, which implies resulting
recurrence relations for all $m\nmid n$. However, writing a closed expression
for these relations would require a closed power series representation for
$(q;q)_{\infty}(-q^{m};q^{m})_{\infty},\ m\geq 3$. While using _Mathematica_
[15] allows one to find these relations for specific values of $m,k,n,$ to the
best of our knowledge there does not appear to exist any closed form for the
recurrence relations for $m\geq 3$.

Similarly, Theorems 6.3 and 6.4 originally resulted from multiplying the
generating function for $a_{k}(n)$ by either $(q;q^{2})_{\infty}$ or
$(-q;q^{2})_{\infty}$ and investigating the resulting recurrence relations

$\displaystyle
a_{k}(n)=2\sum_{m=1}^{\left\lfloor\sqrt{n}\right\rfloor}(-1)^{m-1}a_{k}(n-m^{2}),\quad
a_{k}(n)=2\sum_{m=1}^{\left\lfloor\sqrt{\frac{n}{2}}\right\rfloor}(-1)^{m-1}a_{k}(n-2m^{2}).$

Neither of these is generally true, but it came as quite a surprise that for
even $k$ and arbitrary $n$ the one recurrence relation holds if and only if
the other holds, which is now an easy consequence of Theorems 6.3 and 6.4. It
is also interesting to note that both recurrence relations seem to hold quite
often when considering $k=2,4$. In particular, for $k=2$, both recurrences are
valid for the following list of values $n\leq 500$:

$\displaystyle
1,5,11,22,23,27,30,41,61,65,66,71,72,79,93,100,115,116,117,120,$
$\displaystyle 122,124,131,135,166,183,191,203,204,214,216,223,224,229,236,$
$\displaystyle
252,258,262,286,288,289,291,311,316,321,324,331,336,341,350,361,$
$\displaystyle 366,367,378,383,390,403,414,416,418,425,440,468,470,471,488.$

Note that these are precisely the values of $n$ for which the term $q^{n}$ is
missing in the power series

$\displaystyle(q;q^{2})_{\infty}(q^{2};q^{2})_{\infty}\sum_{n=1}^{\infty}\frac{q^{2n}}{1+q^{2n}}=(q;q)_{\infty}\sum_{n=1}^{\infty}\frac{q^{2n}}{1+q^{2n}}.$

For $k=4$, both recurrences are valid for the following list of values $n\leq
500$:

$\displaystyle
1,2,3,6,19,53,54,58,99,143,164,170,173,257,283,302,328,338,356,359,376,473.$

We do not currently observe a pattern appearing in either of these lists. This
leads to a few interesting questions:

  * (1)

Are the sets of valid $n$ values for $k=2,4$ finite or infinite?

  * (2)

Is there a way to characterize these sets in a closed form?

We conclude by remarking that it may be interesting to investigate analogies
for $a_{k}(n)$ of the other relations for $p(n)$ in [5] and that the
conjectured inequalities regarding $a(n)=a_{2}(n)$ in Andrews, Merca [3,
Conjecture 1.6] extend quite naturally to $a_{k}(n),\ k\geq 3$. Combinatorial
proofs for our results in §6 are very welcome.

## References

  * [1] G. Andrews, The Theory of Partitions, Cambridge University Press, Cambridge (1998).
  * [2] G. Andrews, Euler’s partition identity and two problems of George Beck, Math. Student 86, no. 1–2, 115–119 (2017).
  * [3] G. Andrews, M. Merca, On the number of even parts in all partitions of $n$ into distinct parts, Ann. Comb. 24, 47–54 (2020).
  * [4] C. Ballantine, R. Bielak, On the number of even parts in all partitions of $n$ into distinct parts, Ann. Comb. 23, 511–525 (2019).
  * [5] Y. Choliy, L.W. Kolitsch, A.V. Sills, Partition recurrences, Integers 18B, Paper A1, 15 pp. (2018).
  * [6] F. Franklin, On partitions, Johns Hopkins Univ. Circular 2(22), 72 (1883).
  * [7] S. Fu, D. Tang, Generalizing a partition theorem of Andrews, Math. Student 86, no. 3–4, 91–96 (2017).
  * [8] J.W.L. Glaisher, A theorem in partitions, Messenger of Math. 12, 158–170 (1883).
  * [9] R. Li, A.Y.Z. Wang, Composition analogues of Beck’s conjectures on partitions, European J. Combin. 81, 210–220 (2019).
  * [10] R. Li, A.Y.Z. Wang, Generalization of two problems of George Beck, Discrete Math. 343, 111805, 12 pp. (2020).
  * [11] R. Li, A.Y.Z. Wang, The dual form of Beck type identities, preprint.
  * [12] I. Pak, Partition bijections, a survey, Ramanujan J. 12, 5–75 (2006).
  * [13] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org
  * [14] H.S. Wilf, Identically distributed pairs of partition statistics, Sém. Lothar. Combin. 44, B44c, 3 pp. (2000).
  * [15] Wolfram Research, Inc., Mathematica Edition: Version 12.1 (2020),
http://www.wolfram.com/mathematica/

  * [16] J. Yang, Combinatorial proofs and generalizations of conjectures related to Euler’s partition theorem, European J. Combin. 76, 62–72 (2019).


$\beta$-optimality due to the multiplicative factor $1/\beta$. Building on the
unified analysis proposed in (Jourdan et al., 2022), we prove Theorem 2.3.

Our main technical contribution for this proof lies in the use of tracking
instead of sampling. Given that the cumulative probability of being sampled is
the expectation of the random empirical counts, it is not surprising that
tracking-based Top Two algorithms enjoy the same theoretical guarantees as
their sampling counterpart. As we will see, the analysis to obtain similar
result is even simpler (Lemmas F.6, F.8 and F.10). Apart from this technical
subtlety, the proof of Theorem 2.3 boils down to showing that the UCB leader
satisfies the two sufficient properties highlighted by previous work (Lemmas
F.4 and F.7).

Using the fact that $x\to\sqrt{2x}$ is increasing, it is direct to see that
the TC challenger (4) coincides with the definition used by (Shang et al.,
2020; Jourdan et al., 2022), i.e.

$C^{\text{TC}}_{n}=\operatorname*{arg\,min}_{i\neq
B_{n}}\frac{(\mu_{n,B_{n}}-\mu_{n,i})_{+}}{\sqrt{1/N_{n,B_{n}}+1/N_{n,i}}}=\operatorname*{arg\,min}_{i\neq
B_{n}}\mathds{1}\left(\mu_{n,B_{n}}>\mu_{n,i}\right)\frac{(\mu_{n,B_{n}}-\mu_{n,i})^{2}}{2(1/N_{n,B_{n}}+1/N_{n,i})}\>.$

###  F.1 Proof of Theorem 2.3

Let $\mu\in\mathcal{D}^{K}$ such that $\min_{i\neq j}|\mu_{i}-\mu_{j}|>0$, and
let $i^{\star}=i^{\star}(\mu)$ be the unique best arm. Let $\beta\in(0,1)$ and
$w^{\star}_{\beta}$ be the unique allocation $\beta$-optimal allocation
satisfying $w^{\star}_{\beta,i}>0$ for all $i\in[K]$ (Lemma C.2), i.e.
$w_{\beta}^{\star}(\mu)=\\{w^{\star}_{\beta}\\}$ where

$w_{\beta}^{\star}(\mu):=\operatorname*{arg\,max}_{w\in\triangle_{K}:w_{i^{\star}}=\beta}\min_{i\neq
i^{\star}}\frac{(\mu_{i^{\star}}-\mu_{i})^{2}}{2(1/\beta+1/w_{i})}=\operatorname*{arg\,max}_{w\in\triangle_{K}:w_{i^{\star}}=\beta}\min_{i\neq
i^{\star}}\frac{\mu_{i^{\star}}-\mu_{i}}{\sqrt{1/\beta+1/w_{i}}}\>.$

Let $\varepsilon>0$. Following (Qin et al., 2017; Shang et al., 2020; Jourdan
et al., 2022), we aim at upper bounding the expectation of the _convergence
time_ $T^{\varepsilon}_{\beta}$, which is a random variable quantifies the
number of samples required for the empirical allocations $N_{n}/(n-1)$ to be
$\varepsilon$-close to $w^{\star}_{\beta}$:

$T^{\varepsilon}_{\beta}:=\inf\left\\{T\geq 1\mid\forall n\geq
T,\>\left\|\frac{N_{n}}{n-1}-w^{\star}_{\beta}\right\|_{\infty}\leq\varepsilon\right\\}\>.$
(21)

Lemma F.1 shows that a sufficient condition for asymptotic $\beta$-optimality
is to show $\mathbb{E}_{\mu}[T^{\varepsilon}_{\beta}]<+\infty$ for all
$\varepsilon$ small enough.

######  Lemma F.1.

Let $(\delta,\beta)\in(0,1)^{2}$. Assume that there exists
$\varepsilon_{1}(\mu)>0$ such that for all
$\varepsilon\in(0,\varepsilon_{1}(\mu)]$,
$\mathbb{E}_{\mu}[T^{\varepsilon}_{\beta}]<+\infty$. Combining the stopping
rule (1) with threshold as in (2) yields an algorithm such that, for all
$\mu\in\mathbb{R}^{K}$ with $|i^{\star}(\mu)|=1$,

$\limsup_{\delta\to
0}\frac{\mathbb{E}_{\mu}[\tau_{\delta}]}{\log\left(1/\delta\right)}\leq
T_{\beta}^{\star}(\mu)\>.$

###### Proof.

While the first result in the spirit of Lemma F.1 was derived by Qin et al.
(2017) for Gaussian distributions, a proof holding for more general
distributions is given by Theorem 2 in Jourdan et al. (2022). The sole
criterion on the stopping threshold is to be asymptotically tight (Definition
F.2).

######  Definition F.2.

A threshold $c:\mathbb{N}\times(0,1]\to\mathbb{R}_{+}$ is said to be
asymptotically tight if there exists $\alpha\in[0,1)$, $\delta_{0}\in(0,1]$,
functions $f,\bar{T}:(0,1]\to\mathbb{R}_{+}$ and $C$ independent of $\delta$
satisfying: (1) for all $\delta\in(0,\delta_{0}]$ and $n\geq\bar{T}(\delta)$,
then $c(n,\delta)\leq f(\delta)+Cn^{\alpha}$, (2) $\limsup_{\delta\to
0}f(\delta)/\log(1/\delta)\leq 1$ and (3) $\limsup_{\delta\to
0}\bar{T}(\delta)/\log(1/\delta)=0$.

Since $\mathcal{C}_{G}$ defined in (17) satisfies $\mathcal{C}_{G}\approx
x+\log(x)$, it is direct to see that

$c(n,\delta)=2\mathcal{C}_{G}\left(\frac{1}{2}\log\left(\frac{K-1}{\delta}\right)\right)+4\log\left(4+\log\frac{n}{2}\right)$

is asymptotically tight, e.g. by taking $(\alpha,\delta_{0},C)=(1/2,1,4)$,
$f(\delta)=2\mathcal{C}_{G}\left(\frac{1}{2}\log\left(\frac{K-1}{\delta}\right)\right)$
and $\bar{T}(\delta)=1$. This concludes the proof. ∎

Throughout the proof, we will use a concentration result of the empirical mean
(Lemma F.3) Since this is a standard result for Gaussian observations (see
Lemma 5 of (Qin et al., 2017)), we omit the proof.

######  Lemma F.3.

There exists a sub-Gaussian random variable $W_{\mu}$ such that almost surely,
for all $i\in[K]$ and all $n$ such that $N_{n,i}\geq 1$,

$\displaystyle N_{n,i}|\mu_{n,i}-\mu_{i}|\leq W_{\mu}\log(e+N_{n,i})\>.$

In particular, any random variable which is polynomial in $W_{\mu}$ has a
finite expectation.

##### Sufficient Exploration

To upper bound the expected convergence time, as prior work we first establish
sufficient exploration. Given an arbitrary threshold $L\in\mathbb{R}_{+}^{*}$,
we define the sampled enough set and its arms with highest mean (when not
empty) as

$S_{n}^{L}:=\\{i\in[K]\mid N_{n,i}\geq
L\\}\quad\text{and}\quad\mathcal{I}_{n}^{\star}:=\operatorname*{arg\,max}_{i\in
S_{n}^{L}}\mu_{i}\>.$ (22)

Since $\min_{i\neq j}|\mu_{i}-\mu_{j}|>0$, $\mathcal{I}_{n}^{\star}$ is a
singleton. We define the highly and the mildly under-sampled sets

$U_{n}^{L}:=\\{i\in[K]\mid N_{n,i}<\sqrt{L}\\}\quad\text{and}\quad
V_{n}^{L}:=\\{i\in[K]\mid N_{n,i}<L^{3/4}\\}\>.$ (23)

Jourdan et al. (2022) identifies the properties that the leader and the
challenger should satisfy to ensure sufficient exploration. Lemma F.4 show
that the desired property for the UCB leader defined in (3) with bonus
$g_{u}(n)=2\alpha(1+s)\log n$ or

$g_{m}(n)=\overline{W}_{-1}\left(2s\alpha\log(n)+2\log(2+\alpha\log
n)+2\right)\>.$

######  Lemma F.4.

There exists $L_{0}$ with $\mathbb{E}_{\mu}[(L_{0})^{\alpha}]<+\infty$ for all
$\alpha>0$ such that if $L\geq L_{0}$, for all $n$ (at most polynomial in $L$)
such that $S_{n}^{L}\neq\emptyset$, $B_{n}^{\text{UCB}}\in S_{n}^{L}$ implies
$B_{n}^{\text{UCB}}\in\mathcal{I}_{n}^{\star}$ and
$B_{n}^{\text{UCB}}\in\operatorname*{arg\,max}_{i\in S_{n}^{L}}\mu_{n,i}$.

###### Proof.

Let $\varepsilon>0$ and $\Delta_{\min}=\min_{i\neq j}|\mu_{i}-\mu_{j}|$. Let
$g$ denote either $g_{u}$ or $g_{m}$. Let $L\geq L_{0}$, where $L_{0}$ will be
specified later, and $n$ (at most polynomial in $L$) such that
$S_{n}^{L}\neq\emptyset$. Then, there exists a polynomial function $P$ such
that $n\leq P(L)$. By considering arms that are sampled more than $L$, we can
show that for all $k\in S_{n}^{L}\setminus\mathcal{I}^{\star}_{n}$,

$\displaystyle\mu_{n,k}+\sqrt{\frac{g(n)}{N_{n,k}}}$
$\displaystyle\leq\mu_{k}+W_{\mu}\sqrt{\frac{\log(e+N_{n,k})}{1+N_{n,k}}}+\sqrt{\frac{g(P(L))}{L}}\leq\mu_{k}+W_{\mu}\sqrt{\frac{\log(e+L)}{1+L}}+\sqrt{\frac{g(P(L))}{L}}\leq\mu_{k}+2\varepsilon\>,$

where the last inequality is obtained for $L\geq L_{0}$ with

$L_{0}=1+\sup\left\\{L\in N^{\star}\mid
W_{\mu}\sqrt{\frac{\log(e+L)}{1+L}}>\varepsilon,\>\sqrt{\frac{g(P(L))}{L}}>\varepsilon\right\\}\>.$

Since $\overline{W}_{-1}(x)\approx x+\log(x)$, both $g_{u}$ and $g_{m}$ have a
logarithmic behavior, hence $g(P(L))=_{L\to+\infty}o(L)$. Since $L_{0}$ is
polynomial in $W_{\mu}$, Lemma F.3 yields
$\mathbb{E}_{\mu}[(L_{0})^{\alpha}]<+\infty$ for all $\alpha>0$.

Moreover, for all $k\in\mathcal{I}^{\star}_{n}$,

$\mu_{n,k}+\sqrt{\frac{g(n)}{N_{n,k}}}\geq\mu_{k}-W_{\mu}\sqrt{\frac{\log(e+N_{n,k})}{1+N_{n,k}}}\geq\mu_{k}-W_{\mu}\sqrt{\frac{\log(e+L)}{1+L}}\geq\mu_{k}-\varepsilon\>.$

Assume that $B_{n}^{\text{UCB}}\in S_{n}^{L}$ and that
$B_{n}^{\text{UCB}}\notin\mathcal{I}^{\star}_{n}$. Since
$B_{n}^{\text{UCB}}=\operatorname*{arg\,max}_{k\in[K]}\left\\{\mu_{n,k}+\sqrt{\frac{g(n)}{N_{n,k}}}\right\\}$,
taking $\varepsilon<\Delta_{\min}/3$ in the above yields a direct
contradiction. ∎

We can use the proof of Jourdan et al. (2022) to obtain Lemma F.5. While their
result accounts for the randomization of the sampling procedure, the argument
is direct for tracking since it removes the need for a concentration argument.

######  Lemma F.5 (Lemma 19 in Jourdan et al. (2022)).

Let
$\mathcal{J}_{n}^{\star}=\operatorname*{arg\,max}_{i\in\overline{V_{n}^{L}}}\mu_{i}$.
There exists $L_{1}$ with $\mathbb{E}_{\mu}[L_{1}]<+\infty$ such that if
$L\geq L_{1}$, for all $n$ (at most polynomial in $L$) such that
$U_{n}^{L}\neq\emptyset$, $B_{n}^{\text{UCB}}\notin V_{n}^{L}$ implies
$C_{n}^{\text{TC}}\in
V_{n}^{L}\cup\left(\mathcal{J}_{n}^{\star}\setminus\left\\{B_{n}^{\text{UCB}}\right\\}\right)$.

Lemma F.6 proves sufficient exploration for the TTUCB sampling rule. It builds
on the same reasoning than the one used in the proofs introduced by Shang et
al. (2020), and generalized by Jourdan et al. (2022).

######  Lemma F.6.

Assume $\min_{j\neq i}|\mu_{i}-\mu_{j}|>0$. Under the TTUCB sampling rule,
there exist $N_{0}$ with $\mathbb{E}_{\mu}[N_{0}]<+\infty$ such that for all
$n\geq N_{0}$ and all $i\in[K]$, $N_{n,i}\geq\sqrt{n/K}$.

###### Proof.

Let $L_{0}$ and $L_{1}$ as in Lemmas F.4 and F.5. Therefore, for $L\geq
L_{2}:=\max\\{L_{1},L_{0}^{4/3}\\}$, for all $n$ such that
$U_{n}^{L}\neq\emptyset$, $B_{n}^{\text{UCB}}\in V_{n}^{L}$ or
$C_{n}^{\text{TC}}\in V_{n}^{L}$ since $|\mathcal{J}_{n}^{\star}|=1$ is
implied by $\min_{j\neq i}|\mu_{i}-\mu_{j}|>0$. We have
$\mathbb{E}_{\mu}[L_{2}]<+\infty$. There exists a deterministic $L_{4}$ such
that for all $L\geq L_{4}$, $\lfloor L\rfloor\geq KL^{3/4}$. Let
$L\geq\max\\{L_{2},L_{4}\\}$.

Suppose towards contradiction that $U_{\lfloor KL\rfloor}^{L}$ is not empty.
Then, for any $1\leq t\leq\lfloor KL\rfloor$, $U_{t}^{L}$ and $V_{t}^{L}$ are
non empty as well. Using the pigeonhole principle, there exists some $i\in[K]$
such that $N_{\lfloor L\rfloor,i}\geq L^{3/4}$. Thus, we have
$\left|V_{\lfloor L\rfloor}^{L}\right|\leq K-1$. Our goal is to show that
$\left|V_{\lfloor 2L\rfloor}^{L}\right|\leq K-2$. A sufficient condition is
that one arm in $V_{\lfloor L\rfloor}^{L}$ is pulled at least $L^{3/4}$ times
between $\lfloor L\rfloor$ and $\lfloor 2L\rfloor-1$.

Case 1. Suppose there exists $i\in V_{\lfloor L\rfloor}^{L}$ such that
$L_{\lfloor 2L\rfloor,i}-L_{\lfloor
L\rfloor,i}\geq\frac{L^{3/4}}{\beta}+3/(2\beta)$. Using Lemma D.3, we obtain

$N^{i}_{\lfloor 2L\rfloor,i}-N^{i}_{\lfloor L\rfloor,i}\geq\beta(L_{\lfloor
2L\rfloor,i}-L_{\lfloor L\rfloor,i})-3/2\geq L^{3/4}\>,$

hence $i$ is sampled $L^{3/4}$ times between $\lfloor L\rfloor$ and $\lfloor
2L\rfloor-1$.

Case 2. Suppose that, for all $i\in V_{\lfloor L\rfloor}^{L}$, $L_{\lfloor
2L\rfloor,i}-L_{\lfloor L\rfloor,i}<\frac{L^{3/4}}{\beta}+3/(2\beta)$. Then,

$\sum_{i\notin V_{\lfloor L\rfloor}^{L}}(L_{\lfloor 2L\rfloor,i}-L_{\lfloor
L\rfloor,i})\geq(\lfloor 2L\rfloor-\lfloor
L\rfloor)-K\left(\frac{L^{3/4}}{\beta}+3/(2\beta)\right)$

Using Lemma D.3, we obtain

$\displaystyle\left|\sum_{i\notin V_{\lfloor L\rfloor}^{L}}(N^{i}_{\lfloor
2L\rfloor,i}-N^{i}_{\lfloor L\rfloor,i})-\beta\sum_{i\notin V_{\lfloor
L\rfloor}^{L}}(L_{\lfloor 2L\rfloor,i}-L_{\lfloor L\rfloor,i})\right|\leq
3(K-1)/2\>.$

Combining all the above, we obtain

$\displaystyle\sum_{i\notin V_{\lfloor L\rfloor}^{L}}(L_{\lfloor
2L\rfloor,i}-L_{\lfloor L\rfloor,i})-\sum_{i\notin V_{\lfloor
L\rfloor}^{L}}(N^{i}_{\lfloor 2L\rfloor,i}-N^{i}_{\lfloor L\rfloor,i})$
$\displaystyle\geq(1-\beta)\sum_{i\notin V_{\lfloor L\rfloor}^{L}}(L_{\lfloor
2L\rfloor,i}-L_{\lfloor L\rfloor,i})-3(K-1)/2$
$\displaystyle\geq(1-\beta)\left((\lfloor 2L\rfloor-\lfloor
L\rfloor)-K\left(\frac{L^{3/4}}{\beta}+3/(2\beta)\right)\right)-3(K-1)/2\geq
KL^{3/4}\>,$

where the last inequality is obtained for $L\geq L_{5}$ with

$L_{5}=\sup\left\\{L\in\mathbb{N}\mid(1-\beta)\left((\lfloor 2L\rfloor-\lfloor
L\rfloor)-K\left(\frac{L^{3/4}}{\beta}+3/(2\beta)\right)\right)-3(K-1)/2<KL^{3/4}\right\\}\>.$

The l.h.s. summation is exactly the number of times where an arm
$i\in\overline{V_{\lfloor L\rfloor}^{L}}$ was leader but wasn’t sampled, hence

$\sum_{t=\lfloor L\rfloor}^{\lfloor
2L\rfloor-1}\mathds{1}\left(B_{t}^{\text{UCB}}\in\overline{V_{\lfloor
L\rfloor}^{L}},\>I_{t}=C_{t}^{\text{TC}}\right)\geq KL^{3/4}$

For any $\lfloor L\rfloor\leq t\leq\lfloor 2L\rfloor-1$, $U_{t}^{L}$ is non-
empty, hence we have $B_{t}^{\text{UCB}}\in\overline{V_{\lfloor
L\rfloor}^{L}}\subseteq\overline{V_{t}^{L}}$ implies $C_{t}^{\text{TC}}\in
V_{t}^{L}\subseteq V_{\lfloor L\rfloor}^{L}$. Therefore, we have shown that

$\sum_{t=\lfloor L\rfloor}^{\lfloor 2L\rfloor-1}\mathds{1}\left(I_{t}\in
V_{\lfloor L\rfloor}^{L}\right)\geq\sum_{t=\lfloor L\rfloor}^{\lfloor
2L\rfloor-1}\mathds{1}\left(B_{t}^{\text{UCB}}\in\overline{V_{\lfloor
L\rfloor}^{L}},\>I_{t}=C_{t}^{\text{TC}}\right)\geq KL^{3/4}\>.$

Therefore, there is at least one arm in $V_{\lfloor L\rfloor}^{L}$ that is
sampled $L^{3/4}$ times between $\lfloor L\rfloor$ and $\lfloor 2L\rfloor-1$.

In summary, we have shown $\left|V_{\lfloor 2L\rfloor}^{L}\right|\leq K-2$. By
induction, for any $1\leq k\leq K$, we have $\left|V_{\lfloor
kL\rfloor}^{L}\right|\leq K-k$, and finally $U_{\lfloor
KL\rfloor}^{L}=\emptyset$ for all $L\geq L_{3}$. This concludes the proof. ∎

##### Convergence Towards $\beta$-Optimal Allocation

Provided sufficient exploration holds (Lemma F.6), Jourdan et al. (2022)
identifies the properties that the leader and the challenger should satisfy to
obtain convergence towards the $\beta$-optimal allocation $w^{\star}_{\beta}$.
Lemma F.7 show that the desired property for the UCB leader defined in (3)
with bonus $g_{u}(n)=2\alpha(1+s)\log n$ or

$g_{m}(n)=\overline{W}_{-1}\left(2s\alpha\log(n)+2\log(2+\alpha\log
n)+2\right)\>.$

######  Lemma F.7.

There exists $N_{1}$ with $\mathbb{E}_{\mu}[N_{1}]<+\infty$ such that for all
$n\geq N_{1}$, $B_{n}^{\text{UCB}}=i^{\star}(\mu)$.

###### Proof.

Let $\Delta=\min_{i\neq i^{\star}}|\mu_{i^{\star}}-\mu_{i}|$. Let $g$ denote
either $g_{u}$ or $g_{m}$. Let $N_{0}$ as in Lemma F.6. For all $n\geq N_{2}$
(to be specified later), we obtain for all $k\neq i^{\star}$,

$\displaystyle\mu_{n,k}+\sqrt{\frac{g(n)}{N_{n,k}}}$
$\displaystyle\leq\mu_{k}+W_{\mu}\sqrt{\frac{\log(e+N_{n,k})}{1+N_{n,k}}}+K^{1/4}\sqrt{\frac{g(n)}{\sqrt{n}}}\leq\mu_{k}+W_{\mu}\sqrt{\frac{\log(e+\sqrt{\frac{n}{K}})}{1+\sqrt{\frac{n}{K}}}}+K^{1/4}\sqrt{\frac{g(n)}{\sqrt{n}}}\leq\mu_{k}+2\varepsilon\>,$

where the last inequality is obtained for $n\geq N_{1}$ where

$N_{1}=1+\sup\left\\{n\in N^{\star}\mid
W_{\mu}\sqrt{\frac{\log(e+\sqrt{\frac{n}{K}})}{1+\sqrt{\frac{n}{K}}}}>\varepsilon,\>K^{1/4}\sqrt{\frac{g(n)}{\sqrt{n}}}>\varepsilon\right\\}\>.$

Since $\overline{W}_{-1}(x)\approx x+\log(x)$, both $g_{u}$ and $g_{m}$ have a
logarithmic behavior, hence $g(n)=_{n\to+\infty}o(\sqrt{n})$. Since $N_{1}$ is
polynomial in $W_{\mu}$, Lemma F.3 yields
$\mathbb{E}_{\mu}[(N_{1})^{\alpha}]<+\infty$ for all $\alpha>0$.

Moreover

$\mu_{n,i^{\star}}+\sqrt{\frac{g(n)}{N_{n,i^{\star}}}}\geq\mu_{i^{\star}}-W_{\mu}\sqrt{\frac{\log(e+N_{n,i^{\star}})}{1+N_{n,i^{\star}}}}\geq\mu_{i^{\star}}-W_{\mu}\sqrt{\frac{\log(e+\sqrt{\frac{n}{K}})}{1+\sqrt{\frac{n}{K}}}}\geq\mu_{i^{\star}}-\varepsilon\>.$

Therefore, taking $\varepsilon<\Delta/3$, yields the result that
$B_{n}^{\text{UCB}}=i^{\star}$. ∎

Combining Lemma F.7 with tracking properties (Lemma D.3), we obtain
convergence towards the $\beta$-optimal allocation for the best arm (Lemma
F.8).

######  Lemma F.8.

Let $\varepsilon>0$. Under the TTUCB sampling rule, there exists $N_{2}$ with
$\mathbb{E}_{\mu}[N_{2}]<+\infty$ such that for all $n\geq N_{2}$,

$\left|\frac{N_{n,i^{\star}(\mu)}}{n-1}-\beta\right|\leq\varepsilon\>.$

###### Proof.

Let $N_{0}$ as in Lemma F.6 and $C_{1}$ as in Lemma F.7. For all
$n\geq\max\\{N_{1},N_{0}\\}$, we have $B_{n}=i^{\star}$. Let
$M\geq\max\\{N_{1},N_{0}\\}$. Then, we have $L_{n,i^{\star}}\geq n-M$ and
$\sum_{k\neq i^{\star}}N^{k}_{n,i^{\star}}\leq M-1$ for all $n\geq M+1$. Using
Lemma D.3, we have

$\displaystyle\left|\frac{N_{n,i^{\star}}}{n-1}-\beta\right|$
$\displaystyle\leq\frac{|N^{i^{\star}}_{n,i^{\star}}-\beta
L_{n,i^{\star}}|}{n-1}+\beta\left|\frac{L_{n,i^{\star}}}{n-1}-1\right|+\frac{1}{n-1}\sum_{k\neq
i^{\star}}N^{k}_{n,i^{\star}}\leq\frac{1}{2(n-1)}+\beta\frac{2(M-1)}{n-1}\>.$

Taking $N_{2}=\max\\{N_{1},N_{0},\frac{1/2+2\beta(M-1)}{\varepsilon}+1\\}$
yields the result. ∎

We can use the proof of Jourdan et al. (2022) to obtain Lemma F.9. While their
result accounts for the randomization of the sampling procedure, the argument
is direct for tracking since it removes the need for a concentration argument.

######  Lemma F.9 (Lemma 20 in Jourdan et al. (2022)).

Let $\varepsilon>0$. Under the TTUCB sampling rule, there exists $N_{3}$ with
$\mathbb{E}_{\mu}[N_{3}]<+\infty$ such that for all $n\geq N_{3}$ and all
$i\neq i^{\star}(\mu)$,

$\frac{N_{n,i}}{n-1}\geq w^{\star}_{\beta,i}+\varepsilon\quad\implies\quad
C_{n}^{\text{TC}}\neq i\>.$

Combining Lemma F.9 with tracking properties (Lemma D.3), we obtain
convergence towards the $\beta$-optimal allocation for all arms (Lemma F.10).

######  Lemma F.10.

Let $\varepsilon>0$. Under the TTUCB sampling rule, there exists $N_{4}$ with
$\mathbb{E}_{\mu}[N_{4}]<+\infty$ such that for all $n\geq N_{4}$,

$\forall
i\in[K],\quad\left|\frac{N_{n,i}}{n-1}-w^{\star}_{\beta,i}\right|\leq\varepsilon\>.$

###### Proof.

Let $N_{0}$, $C_{1}$, $N_{2}$ and $N_{3}$ as in Lemmas F.6, F.7, F.8 and F.9.
For all $n\geq\max\\{N_{0},N_{1},N_{2},N_{3}\\}$, we have
$B_{n}^{\text{UCB}}=i^{\star}$,
$\left|\frac{N_{n,i^{\star}}}{n-1}-\beta\right|\leq\varepsilon$ and for all
$i\neq i^{\star}$,

$\frac{N_{n-1,i}}{n-1}\geq
w^{\star}_{\beta,i}+\varepsilon\>\implies\>C_{n}^{\text{TC}}\neq i\>.$

Let $M\geq\max\\{N_{0},N_{1},N_{2},N_{3}\\}$ and $n\geq
N_{5}=\max\\{\frac{M-1}{\varepsilon}+1,M\\}$. Let
$t_{n-1,i}(\varepsilon)=\max\left\\{t\leq n\mid\frac{N_{t,i}}{n-1}\leq
w^{\star}_{\beta,i}+\varepsilon\right\\}$. Since
$\frac{N_{t,i}}{n-1}\leq\frac{N_{t,i}}{t-1}$ for $t\leq n$, we have

$\displaystyle\frac{N_{n,i}}{n-1}$
$\displaystyle\leq\frac{M-1}{n-1}+\frac{1}{n-1}\sum_{t=M}^{n}\mathds{1}\left(B_{t}^{\text{UCB}}=i^{\star},C_{t}^{\text{TC}}=i,\>I_{t}=i\right)$
$\displaystyle\leq\varepsilon+\frac{1}{n-1}\sum_{t=M}^{n}\mathds{1}\left(\frac{N_{t,i}}{n-1}\leq
w^{\star}_{\beta,i}+\varepsilon\right)\mathds{1}\left(B_{t}^{\text{UCB}}=i^{\star},C_{t}^{\text{TC}}=i,\>I_{t}=i\right)$
$\displaystyle\leq\varepsilon+\frac{t_{n-1,i}(\varepsilon)}{n-1}\leq
w^{\star}_{\beta,i}+2\varepsilon\>.$

As a similar upper bound is shown in the proof of Lemma F.8, we obtain
$\frac{N_{n,i}}{n-1}\leq w^{\star}_{\beta,i}+2\varepsilon$ for all $i\in[K]$
and all $n\geq N_{4}:=\max\\{N_{0},N_{1},N_{2},N_{3},N_{5}\\}$. Since
$\frac{N_{n,i}}{n-1}$ and $w^{\star}_{\beta,i}$ sum to $1$, we obtain for all
$n\geq N_{4}$ and all $i\in[K]$,

$\displaystyle\frac{N_{n,i}}{n-1}$ $\displaystyle=1-\sum_{k\neq
i}\frac{N_{n,k}}{n-1}\geq 1-\sum_{k\neq
i}\left(w^{\star}_{\beta,k}+2\varepsilon\right)=w^{\star}_{\beta,i}-2(K-1)\varepsilon\>.$

Therefore, for all $n\geq N_{4}$ and all $i\in[K]$,
$\left|\frac{N_{n,i}}{n-1}-w^{\star}_{\beta,i}\right|\leq
2(K-1)\varepsilon\>.$ Since $\mathbb{E}_{\mu}[N_{4}]<+\infty$ and we showed
the result for all $\varepsilon$, this concludes the proof. ∎

Lemma F.11 shows that $\mathbb{E}_{\mu}[T_{\beta}^{\varepsilon}]<+\infty$, it
is a direct consequence of Lemma F.10.

######  Lemma F.11.

Let $\varepsilon>0$ and $T_{\beta}^{\varepsilon}$ as in (21). Under the TTUCB
sampling rule, we have $\mathbb{E}_{\mu}[T_{\beta}^{\varepsilon}]<+\infty$.

Theorem 2.3 is a direct consequence of Lemma F.1 and Lemma F.11.

##  Appendix G Implementation Details and Additional Experiments

The implementations details and supplementary experiments are detailed in
Appendix G.1 and Appendix G.2.

###  G.1 Implementation Details

##### Top Two Sampling Rules

Existing Top Two algorithms are based on a sampling procedure to choose
between the leader $B_{n}$ and the challenger $C_{n}$, namely sample $B_{n}$
with probability $\beta$, else sample $C_{n}$. The difference lies in the
choice of the leader and the challenger themselves.

TTTS (Russo, 2016) uses a TS (Thompson Sampling) leader and a RS (Re-Sampling)
challenger based on a sampler $\Pi_{n}$. For Gaussian bandits, the sampler
$\Pi_{n}$ is the posterior distribution
$\bigtimes_{i\in[K]}\mathcal{N}(\mu_{n,i},1/N_{n,i})$ given the improper prior
$\Pi_{1}=(\mathcal{N}(0,+\infty))^{K}$. The TS leader is
$B_{n}^{\text{TS}}\operatorname*{arg\,max}_{i\in[K]}\theta_{i}$ where
$\theta\sim\Pi_{n}$. The RS challenger samples vector of realizations
$\theta\in\Pi_{n}$ until
$B_{n}\notin\operatorname*{arg\,max}_{i\in[K]}\theta_{i}$, then it is defined
as $C_{n}^{\text{RS}}\operatorname*{arg\,max}_{i\in[K]}\theta_{i}$ for this
specific vector of realization. When the posterior $\Pi_{n}$ and the leader
$B_{n}$ have almost converged towards the Dirac distribution on $\mu$ and the
best arm $i^{\star}(\mu)$ respectively, the event
$B_{n}\notin\operatorname*{arg\,max}_{i\in[K]}\theta_{i}$ becomes very rare.
The experiments in Jourdan et al. (2022) reveals that computing the RS
challenger can require more than millions of re-sampling steps. Therefore, the
RS challenger can become computationally intractable even for Gaussian
distribution where sampling from $\Pi_{n}$ can be done more efficiently.

T3C (Shang et al., 2020) combines the TS leader and the TC challenger.
$\beta$-EB-TCI (Jourdan et al., 2022) combines the EB leader with the TCI
challenger defined as

$C^{\text{TCI}}_{n}=\operatorname*{arg\,min}_{i\neq
B_{n}}\mathds{1}\left(\mu_{n,B_{n}}>\mu_{n,i}\right)\frac{(\mu_{n,B_{n}}-\mu_{n,i})^{2}}{2(1/N_{n,B_{n}}+1/N_{n,i})}+\log(N_{n,i})\>.$

Since the TC and TCI challenger can re-use computations from the stopping
rule, those two challengers have no additional computational cost which makes
it very attractive for larger sets of arms.

Each tracking procedure has a computational and memory cost in
$\mathcal{O}(1)$, hence total cost of $\mathcal{O}(K)$ for the $K$ independent
procedures. Each UCB index has a computational and memory cost in
$\mathcal{O}(1)$, hence total cost of $\mathcal{O}(K)$ to compute
$B^{\text{UCB}}_{n}$ as in (3). Each TC index (or stopping rule index) has a
computational and memory cost in $\mathcal{O}(1)$, hence total cost of
$\mathcal{O}(K)$ to compute $C^{\text{TC}}_{n}$ as in (4). Therefore, the per-
round computational and memory cost of TTUCB is in $\mathcal{O}(K)$.

##### Other Sampling Rules

At each time $n$, Track-and-Stop (TaS) (Garivier & Kaufmann, 2016) computes
the optimal allocation for the current empirical mean,
$w_{n}=w^{\star}(\mu_{n})$. Given $w_{n}\in\triangle_{K}$, it uses a tracking
procedure to obtain an arm $I_{n}$ to sample. On top of this tracking a forced
exploration is used to enforce convergence towards the optimal allocation for
the true unknown parameters. The optimization problem defining
$w^{\star}(\mu)$ can be rewritten as solving an equation $\psi_{\mu}(r)=0$,
where

$\forall r\in(1/\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2},+\infty),\>\psi_{\mu}(r)=\sum_{i\neq
i^{\star}}\frac{1}{\left(r(\mu_{i^{\star}}-\mu_{i})^{2}-1\right)^{2}}-1$

The function $\psi_{\mu}$ is decreasing, and satisfies
$\lim_{r\to+\infty}\psi_{\mu}(r)=-1$ and $\lim_{y\to 1/\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}}F_{\mu}(y)=+\infty$. For the practical
implementation of the optimal allocation, we use the approach of Garivier &
Kaufmann (2016) and perform binary searches to compute the unique solution of
$\psi_{\mu}(r)=0$. A faster implementation based on Newton’s iterates was
proposed by Barrier et al. (2022) after proving that $\psi_{\mu}$ is convex.
While this improvement holds only for Gaussian distributions, the binary
searches can be used for more general distributions.

DKM (Degenne et al., 2019) view $T^{\star}(\mu)^{-1}$ as a min-max game
between the learner and the nature, and design saddle-point algorithms to
solve it sequentially. At each time $n$, a learner outputs an allocation
$w_{n}$, which is used by the nature to compute the worst alternative mean
parameter $\lambda_{n}$. Then, the learner is updated based on optimistic
gains based on $\lambda_{n}$.

FWS (Wang et al., 2021) alternates between forced exploration and Frank-Wolfe
(FW) updates.

LUCB (Kalyanakrishnan et al., 2012) samples and stops based on upper/lower
confidence indices for a bonus function $g$. For Gaussian distributions, it
rewrites for all $i\in[K]$ as

$\displaystyle
U_{n,i}=\mu_{n,i}+\sqrt{\frac{2c(n-1,\delta)}{N_{n,i}}}\quad\text{and}\quad
L_{n,i}=\mu_{n,i}-\sqrt{\frac{2c(n-1,\delta)}{N_{n,i}}}\>.$

At each time $n$, it samples $\hat{\imath}_{n}$ and
$\operatorname*{arg\,max}_{i\neq\hat{\imath}_{n}}U_{n,i}$ and stops when
$L_{n,\hat{\imath}_{n}}\geq\max_{i\neq\hat{\imath}_{n}}U_{n,i}$. The
$\beta$-LUCB algorithm samples $\hat{\imath}_{n}$ with probability $\beta$,
else it samples $\operatorname*{arg\,max}_{i\neq\hat{\imath}_{n}}U_{n,i}$. The
stopping time is the same as for LUCB.

##### Adaptive Proportions

(Wang et al., 2022) propose a heuristic update mechanism for $\beta$ based on
the optimality conditions for the problem underlying $T^{\star}(\mu)$. For
Gaussian with known homoscedastic variance, their update mechanism is

$\beta_{n}=\frac{N_{n,B_{n}}d_{\text{KL}}(\mu_{n,B_{n}},u_{n}(B_{n},C_{n}))}{N_{n,B_{n}}d_{\text{KL}}(\mu_{n,B_{n}},u_{n}(B_{n},C_{n}))+N_{n,C_{n}}d_{\text{KL}}(\mu_{n,C_{n}},u_{n}(B_{n},C_{n}))}=\frac{N_{n,C_{n}}}{N_{n,B_{n}}+N_{n,C_{n}}}\>,$

where the second equality is obtained by direct computations which uses that

$u_{n}(i,j)=\inf_{x\in\mathbb{R}}\left[N_{n,i}d_{\text{KL}}(\mu_{n,i},x)+N_{n,j}d_{\text{KL}}(\mu_{n,j},x)\right]=\frac{N_{n,i}\mu_{n,i}+N_{n,j}\mu_{n,j}}{N_{n,i}+N_{n,j}}\>.$

##### Reproducibility

Our code is implemented in Julia 1.7.2, and the plots are generated with the
StatsPlots.jl package. Other dependencies are listed in the Readme.md. The
Readme.md file also provides detailed julia instructions to reproduce our
experiments, as well as a script.sh to run them all at once. The general
structure of the code (and some functions) is taken from the tidnabbil
library.111This library was created by (Degenne et al., 2019), see
https://bitbucket.org/wmkoolen/tidnabbil. No license were available on the
repository, but we obtained the authorization from the authors.

Table 4: CPU running time in seconds on random Gaussian instances ($K=10$). | TTUCB | EB-TCI | T3C | TTTS | TaS | FWS | DKM | LUCB | Uniform
---|---|---|---|---|---|---|---|---|---
Average | $0.14$ | $0.10$ | $0.06$ | $0.82$ | $78.38$ | $7.10$ | $0.40$ | $0.06$ | $0.14$
Standard deviation | $0.11$ | $0.30$ | $0.05$ | $0.65$ | $50.34$ | $9.6$ | $0.30$ | $0.09$ | $0.10$
Figure 5: Empirical errors at time $n<\tau_{\delta}$ on random Gaussian
instances ($K=10$).

###  G.2 Supplementary Experiments

##### Running Time

The CPU running time corresponding to the experiment displayed in Figure 1 are
reported in Table 4. They match our discussion on computational cost detailed
in Appendix G.1. The slowest algorithm is TaS, followed closely by FWS and
TTTS. All remaining algorithms have similar computational cost: TTUCB,
$\beta$-EB-TCI, T3C, LUCB and uniform sampling. It is slightly higher for DKM.

We emphasize that this is a coarse empirical comparison of the CPU running
time in order to grasp the different orders of magnitude. More efficient
implementation could (and should) be used by practitioners. As an example, the
computational cost of TaS can be improved for Gaussian distributions by using
the algorithm from Barrier et al. (2022) based on Newton’s iterates. However,
we doubt that the faster implementation of TaS will match the computational
cost of DKM or FWS.

##### Empirical Errors Before Stopping

At the exception of LUCB, all the considered algorithms are anytime algorithms
(see Jun & Nowak (2016) for a definition) since they are not using $\delta$ in
their sampling rule. While all those algorithms are $\delta$-correct, none
enjoy theoretical guarantees on the probability of error before stopping, i.e.
upper bounds on $\mathbb{P}_{\mu}(\hat{\imath}_{n}\neq i^{\star}(\mu))$ for
$n<\tau_{\delta}$. In Figure 5, we display their averaged empirical errors at
time $n<\tau_{\delta}$ ( i.e. $\mathds{1}\left(\hat{\imath}_{n}\neq
i^{\star}\right)$) corresponding to the experiment displayed in Figure 1, with
their associated Wilson Score Intervals (Wilson, 1927). To avoid an unfair
comparison between algorithms having different stopping time, we restrict our
plots to the median of the observed empirical stopping time. Therefore, even
the fastest algorithm will average its empirical errors on at least $2500$
instances.

Based on Figure 5, we see that uniform sampling and DKM perform the worst in
terms of empirical error. At all times, the smallest empirical errors are
achieved by $\beta$-EB-TCI, TTTS and LUCB. While TTUCB is at first as bad as
FWS, its empirical error tends to match the one of the best algorithms for
larger time. For TaS and T3C, the trend is reversed.

Figure 6: Empirical stopping time on random Gaussian instances ($K=10$):
tracking (T-) versus sampling (S-).

##### Tracking Versus Sampling

The TTUCB sampling rule uses tracking instead of sampling. Since both
approaches aim at doing the same with either a deterministic or a randomized
approach, it is interesting to assess whether they lead to different empirical
performance. Therefore, we compare both approaches for four Top Two sampling
rules. Figure 6 reveals that the algorithmic choice of tracking or sampling
has a negligible impact on the empirical stopping time.

In light of this experiment, the choice of tracking or sampling is mostly a
question of theoretical analysis. Since the analysis of a randomized sampling
requires to control of the randomness of the allocation, we choose a
deterministic tracking for analytical simplicity. Moreover, this choice is
natural when both the leader and challenger are deterministic.

Figure 7: Influence of the dimension $K$ on the average empirical stopping
time ($\pm$ standard deviation) for the Gaussian benchmark (a) “$\alpha=0.3$”
and (b) “$\alpha=0.6$”.

##### Larger Sets of Arms

In addition to the results presented in Section 4, we also evaluate the
performance of our algorithm on the two other benchmarks used in Jamieson &
Nowak (2014). The “$\alpha=0.3$” scenarios consider
$\mu_{i}=1-\left(\frac{i-1}{K-1}\right)^{\alpha}$ for all $i\in[K]$, with
hardness $H(\mu)\approx 3K$. The “$\alpha=0.6$” scenarios consider
$\mu_{i}=1-\left(\frac{i-1}{K-1}\right)^{\alpha}$ for all $i\in[K]$, with
hardness $H(\mu)\approx 12K^{1.2}$. The observations from Figure 7 are
consistent with the ones in Figure 2. Overall, T3C performs the best for
larger sets of arms.

####  G.2.1 Adaptive Proportions

To complement experiments conducted on “equal means” instances (see Figure 3),
we compare Top Two algorithms using a fixed proportion $\beta=1/2$ with their
adaptive counterpart using $\beta_{n}=N_{n,C_{n}}/(N_{n,B_{n}}+N_{n,C_{n}})$
at time $n$ on random instances.

Figure 8: Empirical stopping time on random Gaussian instances ($K=10$):
constant $\beta=1/2$ and adaptive (A-).

Experiments are conducted on $5000$ random Gaussian instances with $K=10$ such
that $\mu_{1}=0.6$ and $\mu_{i}\sim\mathcal{U}([0.2,0.5])$ for all $i\neq 1$.
Figure 8 shows that their performances are highly similar, with a slim
advantage for adaptive algorithms. For instances with multiple close
competitors, the same phenomenon appears (see Figure 9 below).

Figure 9: Empirical stopping time on random Gaussian instances ($K=10$) with
multiple close competitors.

Then, we assess the performance on $5000$ random Gaussian instances with
$K=10$ such that $\mu_{1}=0.6$ and $\mu_{i}=\mu_{1}-\Delta_{i}$ for $i\neq 1$
where $\Delta_{i}=\frac{1}{20}\left(\frac{995}{1000}+\frac{u_{i}}{100}\right)$
for all $i\in\\{2,3,4,5,6\\}$ and
$\Delta_{i}=\frac{1}{10}\left(\frac{995}{1000}+\frac{u_{i}}{100}\right)$ for
all $i\in\\{7,8,9,10\\}$ with $u_{i}\sim U([0,1])$. Numerically, we observe
$w^{\star}(\mu)_{i^{\star}}\approx 0.28276\pm 0.0003$ (mean $\pm$ std). Both
plots in Figure 9 show the same phenomena than the ones observed in Figures 1
and 8.