#  $M$-ary partition polynomials

Błażej Żmija  Institute of Mathematics of the Polish Academy of Sciences, ul.
Śniadeckich 8, 00-656 Warszawa, Poland<EMAIL_ADDRESS>
###### Abstract.

Let $M=(m_{i})_{i=0}^{\infty}$ be a sequence of integers such that $m_{0}=1$
and $m_{i}\geq 2$ for $i\geq 1$. In this paper we study $M$-ary partition
polynomials $(p_{M}(n,t))_{n=0}^{\infty}$ defined as the coefficient in the
following power series expansion:

$\displaystyle\prod_{i=0}^{\infty}\frac{1}{1-tq^{M_{i}}}=\sum_{n=0}^{\infty}p_{M}(n,t)q^{n},$

where $M_{i}=\prod_{j=0}^{i}m_{j}$. In particular, we provide a detailed
description of their rational roots and show, that all their complex roots
have absolute values not greater than $2$. We also study arithmetic properties
of $M$-ary partition polynomials. One of our main results says that if
$n=a_{0}+a_{1}M_{1}+\cdots+a_{k}M_{k}$ is a (unique) representation such that
$a_{j}\in\\{0,\ldots,m_{j+1}-1\\}$ for every $j$, then

$\displaystyle p_{M}(n,t)\equiv t^{a_{0}}\prod
t^{a_{j}}f(a_{j}+1,t^{m_{j}-1})\pmod{g_{k}(t)},$

where $f(a,t):=\frac{t^{a}-1}{t-1}$ and
$g_{k}(t):=\gcd\big{(}t^{m_{1}+m_{2}-1}f(m_{2},t^{m_{1}-1}),\ldots,t^{m_{k}+m_{k+1}-1}f(m_{k+1},t^{m_{k}-1})\big{)}$.
This is a polynomial generalisation of the well-known characterisation modulo
$m$ of the sequence of $m$-ary partition.

###### Key words and phrases:

$M$-ary partitions, congruences, generating functions

###### 2020 Mathematics Subject Classification:

11P83, 11P81, 05A15, 05A17

##  1\. Introduction

If $m$ is a positive integer, then by an $m$-ary partition of $n$ we
understand any expression of the form

$\displaystyle n=m^{i_{1}}+m^{i_{2}}+\cdots+m^{i_{k}},$

where $i_{1}\leq i_{2}\leq\ldots\leq i_{k}$ are nonnegative integers. We will
denote the number of such partitions of $n$ by $b_{m}(n)$.

The first person to study $m$-ary partitions was probably Euler, who found the
generating function for the sequence of binary partitions, that is, the case
of $m=2$. Later, the sequence $(b_{m}(n))_{n=0}^{\infty}$ was studied by many
mathematicians, and for example Mahler [19], and then Pennington [20],
described its the asymptotic behaviour, Churchhouse started studying its
arithmetic properties in the case of $m=2$ in [8], and this was continued for
more general $m$ by Gupta [15], Rødseth [21], Rødseth and Sellers [22], and
many more.

The notion of $m$-ary partitions was generalised by many authors and many
directions, see for example [3, 5, 9, 13, 16, 18, 17, 24]. For us, the two
types of generalisations will be important. The first one, done by Folsom et
al. in [11] is the following. Let $M=(m_{n})_{n=0}^{\infty}$ be a fixed
sequence of natural numbers such that $m_{0}=1$ and $m_{j}\geq 2$ for $j\geq
1$. For every $i\geq 0$ let $M_{i}:=\prod_{j=0}^{i}m_{j}$. Then we will call
every representation of the form

$\displaystyle n=M_{i_{1}}+M_{i_{2}}+\cdots+M_{i_{k}}$

an $M$-ary partition of $n$. In the paper, we will denote by $b_{M}(n)$ the
number of $M$-ary partitions of $n$.

Note, that Folsom et al. called such representations $M$-sequence non-
squashing partitions and were focused on their asymptotic behaviour. They also
stated some conjectures concerning the divisibility of numbers $b_{M}(n)$ by
the terms in the sequence $M$. These conjectures were however not true as was
showed in [25].

On the other way Ulas and Żmija introduced in [23] a polynomial generalisation
of binary partitions, that is, binary partition polynomials, defined as the
coefficients in the following power series expansion:

$\displaystyle
F_{2}(q,t):=\prod_{j=0}^{\infty}\frac{1}{1-tq^{2^{j}}}=\sum_{n=0}^{\infty}p_{2}(n,t)q^{n}.$

They used the polynomials to obtain some non-trivial identities involving
binary partitions. For example, they proved that for every $n$, the number of
binary partitions of $8n+4$ with the number of parts $\equiv 2k\pmod{4}$ is
equal to the number of binary partitions of $8n+4$ with the number of parts
$\equiv 2k+1\pmod{4}$ for $k\in\\{0,1\\}$. They also used binary partition
polynomials to study the sequence of so-called $s$-partitions. These are
partitions into parts of the form $2^{k}-1$, $k\in\mathbb{N}_{0}$. Note here,
that $s$-partitions were introduced by Bhatt in [6], who showed their
application in cryptography.

In this paper, we study properties of (probably) the simplest non-trivial case
of polynomials related to partitions, that is, $M$-ary partition polynomials.
Here we are interested exclusively in the case of partitions with parts from
an infinite set. This corresponds to the case of $M$ being infinite. However,
many of the results from this chapter remains true also if $M$ is finite.

Let $M=(m_{n})_{n=0}^{\infty}$ be a fixed sequence of natural numbers such
that $m_{0}=1$ and $m_{j}\geq 2$ for $j\geq 1$. Let
$M_{n}:=\prod_{i=0}^{n}m_{i}$. For a number $n$ we define the $n$th $M$-ary
partition polynomial $p_{M}(n,t)$ as the $n$th coefficient in the following
power series expansion:

$\displaystyle
F_{M}(q,t):=\prod_{j=0}^{\infty}\frac{1}{1-tq^{M_{j}}}=\sum_{n=0}^{\infty}p_{M}(n,t)q^{n}.$

The coefficients of the polynomial $p_{M}(n,t)$ have the following
combinatorial interpretation. If

$\displaystyle p_{M}(n,t)=\sum_{j=0}^{n}a_{M}(j,n)t^{j},$

then $a_{M}(j,n)$ is equal to the number of representations of $n$ as a sum of
the numbers $M_{i}$ with exactly $j$ parts. In particular,
$p_{M}(n,1)=b_{M}(n)$. Note, that the case of binary partition polynomials is
obtained by putting $M=(1,2,2,\ldots)$.

Let us describe briefly the content of this paper. In the next section we will
describe the basic properties of $M$-ary partition polynomials and show some
examples. Then we will focus on their rational roots in Section 3 and complex
roots in Section 4. In these part we will mainly interested in the case of
$m$-ary partition polynomials, that is, the case of $M=(1,m,m,\ldots)$. In
particular, we will obtain a very precise description of all the possible
rational roots and that all the complex roots are in the circle of radius $2$
and the center in the origin. In Section 5 we will return to the general case
and prove a polynomial generalisation of the well-known characterisation of
the sequence $(b_{m}(n))_{n=0}^{\infty}$ modulo $m$. Moreover, our result
works for any sequence $M$, not only $M=(1,m,m,\ldots)$. In the last section
we will study two sequences of the coefficients of $M$-ary partition
polynomials. In particular, we will show that both these sequences are
bounded, and connect the values of one of them with the numbers of partitions
into parts of the form $M_{i}-1$.

In the paper, we will sometimes use the following notion of automaticity. Let
$k\in\mathbb{N}$ and $k\geq 2$. We say that a sequence
$\mathbf{a}=(a_{n})_{n=0}^{\infty}$ is $k$-automatic if the following set

$\displaystyle\mathcal{K}_{k}(\mathbf{a}):=\big{\\{}\
(a_{k^{i}n+j})_{n=0}^{\infty}\ \big{|}\ i\in\mathbb{N}_{0}\textrm{ and }0\leq
j<k^{i}\ \big{\\}},$

called the $k$-kernel of $\mathbf{a}$, is finite. This condition is equivalent
to the condition that there exists a $k$-automaton for the sequence
$\mathbf{a}$. Roughly speaking, $k$-automaton (or automaton for short if $k$
is fixed) is a procedure that allows us, for a given $n$, find the value of
$a_{n}$ using only the representation of $n$ in base $k$. For more precise
definition see [2].

One of the most important results in the theory of automatic sequences is the
following characterisation in the case of $k$ being a power of a prime.

######  Lemma 1.1 (Christol’s Theorem).

Let $q$ be a power of a prime. Let $\mathbf{a}=(a_{n})_{n=0}^{\infty}$ be a
sequence over $\mathbb{F}_{q}$. Then $\mathbf{a}$ is $q$-automatic if and only
if its generating function is algebraic over $\mathbb{F}_{q}(x)$.

###### Proof.

Can be found in [2]. ∎

##  2\. Basic properties

In this section we collect the most basic properties of the $M$-ary partition
polynomials. From the definition of the function $F_{M}(q,t)$ we have

$\displaystyle F_{M}(q,t)=\frac{1}{1-tq}F_{M^{\prime}}(q^{m_{1}},t),$

where $M^{\prime}=(1,m_{2},m_{3},\ldots)$. Therefore,

$\displaystyle\sum_{n=0}^{\infty}p_{M^{\prime}}(n,t)q^{m_{1}n}=(1-tq)\left(\sum_{n=0}^{\infty}p_{M}(n,t)q^{n}\right)=\sum_{n=0}^{\infty}\big{(}p_{M}(n,t)-tp_{M}(n-1,t)\big{)}q^{n}.$

By comparing the coefficients on both sides of the above power series we get

(3)
$\displaystyle\left\\{\begin{array}[]{ll}p_{M}(m_{1}n+j,t)=tp_{M}(m_{1}n+j-1,t),&\textrm{
if }j\in\\{1,\ldots,m_{1}-1\\},\\\
p_{M}(m_{1}n,t)=tp_{M}(m_{1}n-1,t)+p_{M^{\prime}}(n,t).&\end{array}\right.$

In particular, we can compute the first few $M$-ary partition polynomials.

######  Example 2.1.

If $n=km_{1}+j$ for some $j\in\\{0,\ldots,m_{1}-1\\}$ and
$k\in\\{0,\ldots,m_{2}-1\\}$, then

$\displaystyle
p_{M}(km_{1}+j,t)=t^{k+j}\frac{t^{(m_{1}-1)(k+1)}-1}{t^{m_{1}-1}-1}.$

###### Proof.

Because of the first equality in (3), it is enough to justify the formula in
the case of $j=0$. If $k=0$ it is trivial. Assume it works for some
$k-1\in\\{0,\ldots,m_{2}-2\\}$. We get for $k$:

$\displaystyle p_{M}(km_{1},t)$
$\displaystyle=t^{m_{1}}p_{M}((k-1)m_{1},t)+p_{M^{\prime}}(k,t)=t^{m_{1}}t^{k-1}\frac{t^{(m_{1}-1)k}-1}{t^{m_{1}-1}-1}+t^{k}$
$\displaystyle=t^{k}\frac{t^{m_{1}-1}t^{(m_{1}-1)k}-t^{m_{1}-1}+t^{m_{1}-1}-1}{t^{m_{1}-1}-1}=t^{k}\frac{t^{(m_{1}-1)(k+1)}-1}{t^{m_{1}-1}-1}.$

In the above computations we used the fact that $p_{M^{\prime}}(k,t)=t^{k}$
for $k\in\\{0,\ldots,m_{2}-1\\}$ which follows trivially from the first
equation in (3) used with the sequence $M^{\prime}$ instead of $M$. ∎

Relations (3) allow us to find the degree of the polynomial $p_{M}(n,t)$. The
formula in theorem below directly generalizes the result from [23] concerning
the case $m=2$.

######  Observation 2.2.

For every $M$ and $n$ we have $\deg p_{M}(n,t)=n$.

###### Proof.

We have $p_{M}(0,t)=1$ and $p_{M}(1,t)=t$. Assume that $\deg p_{M}(k,t)=k$ for
$k<n$. Thus if $m_{1}\nmid n$, then by the induction hypothesis and relations
(3) we obtain

$\displaystyle\deg p_{M}(n,t)=\deg\left(tp_{M}(n-1,t)\right)=1+\deg
p_{M}(n-1,t)=1+(n-1)=n.$

If $m_{1}\mid n$, then by the induction hypothesis we get

$\displaystyle\deg\left(tp_{M}(n-1,t)\right)=1+\deg
p_{M}(n-1,t)=n>\frac{n}{m_{1}}=\deg
p_{M^{\prime}}\left(\frac{n}{m_{1}},t\right).$

We finish the proof analogously as in the previous case. ∎

##  3\. Rational roots

The first objects that we want to study in the context of polynomials in
general, and the $M$-ary polynomials in particular, are their roots. For now,
we focus on the existence of rational roots. This will naturally lead us to
studying the sequence $(p_{M}(n,-1))_{n=0}^{\infty}$. Note that $p_{M}(n,-1)$
is equal to the difference between the number of $M$-ary partitions with even
number of parts and the number of $M$-ary partitions with odd number of parts.

In this section we narrow our considerations down to the case of $m$-ary
partition polynomials where $m\in\mathbb{N}$. This is a special case of
$M$-ary partition polynomials with $M=(1,m,m,m,\ldots)$. We will write
$p_{m}(n,t)$ instead of $p_{M}(n,t)$ in this case.

In this case we simply have $M^{\prime}=M$, so the recurrence relations (3)
simplify to

(7) $\displaystyle\left\\{\begin{array}[]{ll}p_{m}(0,t)=1,&\\\
p_{m}(mn+j,t)=tp_{m}(mn+j-1,t),&\textrm{ if }j\in\\{1,\ldots,m-1\\},\\\
p_{m}(mn,t)=tp_{m}(mn-1,t)+p_{m}(n,t).&\end{array}\right.$

Although the proof of the next lemma uses Theorem 3.2, we state the lemma
first to give the reader an insight about possible values of rational roots of
$p_{m}(n,t)$.

######  Lemma 3.1.

If $r$ is a rational root of $p_{m}(n,t)$ for some $n$ then $r\in\\{-1,0\\}$.

###### Proof.

A simple induction argument (together with Theorem 3.2 below) shows that for
every $n$, the leading coefficient and the initial coefficient in $p_{m}(n,t)$
are both equal to $1$. Hence, $r$ has to be an integer and divide $1$ or be
equal to $0$. Moreover, all nonzero coefficients in $p_{m}(n,t)$ are positive,
so $p_{m}(n,1)>0$. Therefore, $r\in\\{-1,0\\}$. ∎

In order to state the next result we need the following notation. If
$n=\sum_{j=0}^{k}n_{j}m^{j}$ is a unique $m$-ary representation of $n$, then
we define

$\displaystyle s_{m}(n):=\sum_{j=0}^{k}n_{j}.$

That is, $s_{m}(n)$ is the sum of digits in the $m$-ary representation of $n$.

The next theorem provides information about the order of $0$ as a root of the
polynomial $p_{m}(n,t)$.

######  Theorem 3.2.

For every natural number $n$ the following formula holds:

$\displaystyle{\rm ord}_{t=0}p_{m}(n,t)=s_{m}(n).$

###### Proof.

We proceed by induction. The statement is true for $n=0$ and $n=1$. Assume
that it is true for some $n=mn^{\prime}+a$, where $a\in\\{0,\ldots,m-2\\}$. By
the second equation in (7) we have

$\displaystyle{\rm ord}_{t=0}p_{m}(mn^{\prime}+a+1,t)=1+{\rm
ord}_{t=0}p_{m}(mn^{\prime}+a,t)=1+s_{m}(mn^{\prime}+a)=s_{m}(mn^{\prime}+a+1).$

Hence, we can assume that $n=mn^{\prime}+m-1$. Observe that
$s_{m}(mn^{\prime}-1)\geq s_{m}(n^{\prime})$. Indeed, if
$n^{\prime}=\sum_{j=h}^{k}a_{j}m^{j}$, where $a_{h}$ is the smallest non-zero
digit in the representation, then

$\displaystyle
mn^{\prime}-1=\sum_{j=h+1}^{k}a_{j}m^{j+1}+(a_{h}-1)m^{h+1}+\sum_{j=0}^{h}(m-1)m^{j}.$

Therefore,

$\displaystyle
s_{m}(mn^{\prime}-1)=\sum_{j=h}^{k}a_{j}+(h+1)(m-1)-1\geq\sum_{j=h}^{k}a_{j}=s_{m}(n^{\prime}).$

Hence,

$\displaystyle{\rm ord}_{t=0}p_{m}(mn^{\prime}+m,t)=$ $\displaystyle{\rm
ord}_{t=0}\big{(}tp_{m}(mn^{\prime}+m-1,t)+p_{m}(n^{\prime}+1,t)\big{)}$
$\displaystyle=$
$\displaystyle\min\big{\\{}1+s_{m}(mn^{\prime}+m-1),s_{m}(n^{\prime}+1)\big{\\}}$
$\displaystyle=$ $\displaystyle s_{m}(n^{\prime}+1)=s_{m}(mn^{\prime}+m),$

and this equality finishes the proof. ∎

Let us move to the problem when $-1$ is a root of some $m$-ary partition
polynomial. Interestingly, the behaviour of polynomials $p_{m}(n,t)$ at $-1$
highly depends on the parity of $m$. We begin by studying the case of even $m$
in which we can provide a very good description of the numbers $p_{m}(n,-1)$.

######  Theorem 3.3.

Let $n=a_{0}+a_{1}m+\cdots+a_{k}m^{k}$ be the base $m$ representation of $n$.
If $2\mid m$, then

$\displaystyle
p_{m}(n,-1)=(-1)^{a_{0}}\prod_{j=1}^{k}\frac{1+(-1)^{a_{j}}}{2}.$

In particular $p_{m}(n,-1)\in\\{-1,0,1\\}$ and

$\displaystyle p_{m}(n,-1)=0\hskip 28.45274pt\textrm{ if and only if }\hskip
28.45274pt2\nmid a_{j}\textrm{ for some }j\in\\{1,\ldots,k\\}.$

###### Proof.

Let $p_{n}:=p_{m}(n,-1)$. Relations (7) imply

$\displaystyle\left\\{\begin{array}[]{ll}p_{0}=1,&\\\
p_{mn+j}=-p_{mn+j-1},&\textrm{if }j\in\\{1,\ldots,m-1\\},\\\
p_{mn}=-p_{mn-1}+p_{m}.\end{array}\right.$

In particular, we have $p_{mn+j}=(-1)^{j}p_{mn}$ for $j\in\\{0,\ldots,m-1\\}$,
and hence

$\displaystyle
p_{mn}=-p_{mn-1}+p_{n}=(-1)^{m}p_{m(n-1)}+p_{n}=p_{m(n-1)}+p_{n},$

because $m$ is even by the assumption. Therefore, if we write
$n_{1}=mn_{2}+a_{1}$, then

$\displaystyle p_{mn_{1}}=$ $\displaystyle\
p_{m(n_{1}-1)}+p_{n_{1}}=p_{m(n_{1}-2)}+p_{n_{1}-1}+p_{n_{1}}=\cdots=\sum_{j=0}^{n_{1}}p_{j}$
$\displaystyle=$ $\displaystyle\
\sum_{l=0}^{n_{2}-1}\sum_{j=0}^{m-1}p_{ml+j}+\sum_{j=0}^{a_{1}}p_{mn_{2}+j}=\sum_{l=0}^{n_{2}-1}\sum_{j=0}^{m-1}(-1)^{j}p_{ml}+\sum_{j=0}^{a_{1}}(-1)^{j}p_{mn_{2}}$
$\displaystyle=$ $\displaystyle\
\sum_{l=0}^{n_{2}-1}\left(\sum_{j=0}^{m-1}(-1)^{j}\right)p_{ml}+\left(\sum_{j=0}^{a_{1}}(-1)^{j}\right)p_{mn_{2}}=0+\frac{1+(-1)^{a_{1}}}{2}p_{mn_{2}}=\frac{1+(-1)^{a_{1}}}{2}p_{mn_{2}}.$

We now use the induction argument on the number of digits in the $m$-ary
representation of $n$. If $n=a_{0}$ for some $a_{0}\in\\{0,\ldots,m-1\\}$ then
the result is true. Assume this is true for every natural number with at most
$k$ digits in the $m$-ary representation. Let
$n=a_{0}+a_{1}m+\cdots+a_{k}m^{k}$ (that is, $n$ has $k+1$ digits in its base
$m$ representation). By our previous computations and the induction hypothesis
we get

$\displaystyle
p_{mn_{1}}=\frac{1+(-1)^{a_{1}}}{2}p_{mn_{2}}=\frac{1+(-1)^{a_{1}}}{2}\prod_{j=2}^{k}\frac{1+(-1)^{a_{j}}}{2}=\prod_{j=1}^{k}\frac{1+(-1)^{a_{j}}}{2},$

and hence,

$\displaystyle
p_{n}=(-1)^{a_{0}}p_{mn_{1}}=(-1)^{a_{0}}\prod_{j=1}^{k}\frac{1+(-1)^{a_{j}}}{2},$

as desired. ∎

######  Corollary 3.4.

Let

$\displaystyle e_{m}(n):=$ $\displaystyle\ \\#\left\\{m-\textrm{ary partitions
with even number of parts}\right\\},$ $\displaystyle o_{m}(n):=$
$\displaystyle\ \\#\left\\{m-\textrm{ary partitions with odd number of
parts}\right\\}.$

If $2\mid m$ and $n=a_{0}+a_{1}m+\cdots+a_{k}m^{k}$ is the base $m$
representation of $n$, then

$\displaystyle
e_{m}(n)-o_{m}(n)=(-1)^{a_{0}}\prod_{j=1}^{k}\frac{1+(-1)^{a_{j}}}{2}.$

In particular, $|e_{m}(n)-o_{m}(n)|\leq 1$.

###### Proof.

The statement follows from the observation that
$p_{m}(n,-1)=e_{m}(n)-o_{m}(n)$, and Theorem 3.3. ∎

Now we show the automaticity of the sequence
$(e_{m}(n)-o_{m}(n))_{n=0}^{\infty}$ if $m$ is even. The required definitions
have been resented in the introduction.

######  Corollary 3.5.

If $2\mid m$, then the sequence $(e_{m}(n)-o_{m}(n))_{n=0}^{\infty}$ is
$m$-automatic.

###### Proof.

We will prove that the $m$-kernel of the considered sequence is finite. Recall
that $e_{m}(n)-o_{m}(n)=p_{m}(n,-1)=:p_{n}$ for all $n\in\mathbb{N}_{0}$.
Theorem 3.3 implies the following relations for all $n\in\mathbb{N}_{0}$ and
$0\leq a,b\leq m-1$:

$\displaystyle p_{m(mn+a)+b}=(-1)^{b}\frac{1+(-1)^{a}}{2}p_{mn}.$

Hence,

$\displaystyle p_{m^{2}n+b}=$ $\displaystyle\
(-1)^{b}p_{m^{2}n}=(-1)^{b}p_{mn}=\left\\{\begin{array}[]{ll}p_{mn},&2\mid
b,\\\ -p_{mn},&2\nmid b\end{array}\right.,$ $\displaystyle p_{m^{2}n+ma+b}=$
$\displaystyle\ \left\\{\begin{array}[]{ll}p_{m^{2}n+b},&2\mid a,\\\ 0,&2\nmid
a\end{array}\right.$

In particular, every sequence of the form $(p_{m^{j}n+k})_{n=0}^{\infty}$ is
equal to one of the sequences: $(p_{n})_{n=0}^{\infty}$,
$(p_{mn})_{n=0}^{\infty}$, $(-p_{mn})_{n=0}^{\infty}$ or the constant sequence
$(0)_{n=0}^{\infty}$. Thus

$\displaystyle\mathcal{K}_{m}\big{(}(p_{n})_{n=0}^{\infty}\big{)}=\big{\\{}\
(p_{n})_{n=0}^{\infty},\ (p_{mn})_{n=0}^{\infty},\ (-p_{mn})_{n=0}^{\infty},\
(0)_{n=0}^{\infty}\ \big{\\}}.$

is finite and the result follows. ∎

One can see that the sequence $(e_{m}(n)-o_{m}(n))_{n=0}^{\infty}$ is
generated by the following automaton (reading the input starts with the least
significant digit):

$1$$1$$-1$$0$evenoddevenoddevenoddall

where the term ’even’ means any even digit in the base $m$ representation, and
similarly ’odd’ means any odd digit.

One can also give an automaton generating the sequence
$(e_{m}(n)-o_{m}(n))_{n=0}^{\infty}$ where reading the input starts with the
most significant digit. It is the following:

$1$$-1$$0$evenoddall

We use the same convention using the terms ’even’ and ’odd’ as before.

The case of odd $m$ is completely different.

######  Theorem 3.6.

If $2\nmid m$, then for every $n$:

$\displaystyle p_{m}(n,-1)=(-1)^{n}p_{m}(n,1).$

In particular, $|p_{m}(n,-1)|\to\infty$ as $n\to\infty$, and $p_{m}(n,-1)\neq
0$ for all $n$’s.

###### Proof.

Let

$\displaystyle
F_{m}(q,t)=\sum_{n=0}^{\infty}p_{m}(n,t)q^{n}=\prod_{j=0}^{\infty}\frac{1}{1-tq^{m^{j}}}.$

Then

$\displaystyle\sum_{n=0}^{\infty}p_{m}(n,-1)q^{n}=$ $\displaystyle\
F_{m}(q,-1)=\prod_{j=0}^{\infty}\frac{1}{1+q^{m^{j}}}=\prod_{j=0}^{\infty}\frac{1}{1-(-q)^{m^{j}}}$
$\displaystyle=$ $\displaystyle\
F_{m}(-q,1)=\sum_{n=0}^{\infty}p_{m}(n,1)(-q)^{n}=\sum_{n=0}^{\infty}(-1)^{n}p_{m}(n,1)q^{n},$

because $m$ is odd. The result follows. ∎

The above theorem implies that if $m$ is odd, then the sequence
$\big{(}e_{n}(n)-o_{m}(n)\big{)}_{n=0}^{\infty}$ is unbounded and

$\displaystyle(-1)^{n}\big{(}e_{m}(n)-o_{m}(n)\big{)}>0$

for every $n$. This shows a striking difference with the case of even $m$, in
which $e_{m}(n)-o_{m}(n)\in\\{-1,0,1\\}$ for all $n$ and the sign of the
difference $e_{n}(n)-o_{m}(n)$ depends on the first non-zero digit in the
$m$-ary representation of $n$. However, this is exactly the behaviour that we
can expect. More precisely, if $2\nmid m$ then we need even number of powers
of $m$ to obtain any partition of any even number $n$, and odd number of such
powers to obtain a partition of odd $n$. In the case of even $m$, one can
guess, that $o_{m}(n)$ and $e_{m}(n)$ have similar size, and this is very
precisely described in Corollary 3.4.

##  4\. Complex roots

In the previous section we have considered the rational roots of the
polynomials $p_{M}(n,t)$. Hence, we can move to a more general problem of
studying the complex roots of these polynomials. This is much more difficult
task and we will not characterize all of the roots. Instead, our aim is to
prove that all the roots of $m$-ary partition polynomials lie in a small
region on a complex plane. In fact, we will prove in Theorem 4.3 that all such
roots are in the circle of radius $4^{1/m}$ centered at the origin. We start
this section by a heuristic argument explaining why we may expect such a
result.

Recall that Rouche’s theorem says that if $f$ and $g$ are two functions
holomorphic in a neighbourhood of the closure of a bounded region $K$ with
closed contour $\partial K$ without self-intersections, and
$|f(z)-g(z)|<|f(z)|$ for $z\in\partial K$, then $f$ and $g$ have the same
number of zeros inside $K$ (counting multiplicities). For more details see for
example [14].

In the case of $m$-ary partition polynomials, we have

$\displaystyle p_{m}(n,t)-tp_{m}(n-1,t)=p_{m}(n/m,t),$

where $p_{m}(n/m,t)=0$ for all $t$ if $m\nmid n$. It follows that the
difference $p_{m}(n,t)-tp_{m}(n-1,t)$ is a polynomial of much smaller degree
than both, $p_{m}(n,t)$ and $tp_{m}(n-1,t)$. Therefore, we may expect that if
$|t|$ is large enough, then $|p_{m}(n,t)-tp_{m}(n-1,t)|<|tp_{m}(n-1,t)|$.
Obviously, there might be some unexpected cancellations even if $|t|$ is very
large. However, assume for a while that we know that such cancellations do not
occur if $|t|\geq R$ for some $R$. Then if we knew somehow (for example from
some induction hypothesis) that all the zeroes of the polynomial
$p_{m}(n-1,t)$ lay inside the circle

$\displaystyle C(R):=\big{\\{}\ z\in\mathbb{C}\ \big{|}\ |z|=R\ \big{\\}},$

then we would get by Rouche’s theorem that all the zeroes of $p_{m}(n,t)$ are
inside $C(R)$ too. Therefore, we may expect, that all the zeroes of all
polynomials $p_{m}(n,t)$ are contained inside a circle $C(R)$ for some $R$
independent of $m$ and $n$.

The above heuristic argument agrees with computational data. Moreover, more
precise statement seems to be true. Ulas (in private communication) stated in
the case of $m=2$ the following problem, that we extend here to the general
case.

######  Conjecture 4.1.

Let $C(1)$ be the unit circle with the center in the origin. For all natural
numbers $m\geq 2$ and $n$ let

$\displaystyle Z_{m,n}:=\\{\ z\in\mathbb{C}\ |\ p_{m}(n,z)=0\
\\}\setminus\\{0\\}.$

Moreover, for $N\in\mathbb{N}$ let

$\displaystyle Z_{m}^{(N)}:=\bigcup_{n>N}Z_{m,n}.$

Then, for every $\varepsilon>0$ and for every $m$ there exists $N$ (possibly
depending on $\varepsilon$ and $m$) such that

$\displaystyle Z_{m}^{(N)}\subseteq\big{\\{}\ z\ \big{|}\
1-\varepsilon<|z|<1+\varepsilon\ \big{\\}}.$

Moreover, we believe that for every $m$:

$\displaystyle\\#\left(Z_{m}^{(0)}\cap\big{\\{}\ z\ \big{|}\ |z|>1\
\big{\\}}\right)=\\#\left(Z_{m}^{(0)}\cap\big{\\{}\ z\ \big{|}\ |z|<1\
\big{\\}}\right)=\infty.$

That is, we believe that there are infinitely many roots of $m$-ary partition
polynomials inside and outside the unit circle.

Let us show some computations to support Conjecture 4.1. We present all the
roots of the polynomials $p_{4}(n,t)$ for $1\leq n\leq 400$ in Figure 2 and
all the roots of the polynomials $p_{5}(n,t)$ for $1\leq n\leq 500$ in Figure
2.

Figure 1. All the roots of
the polynomials $p_{4}(n,t)$ for $1\leq n\leq 400$.

Figure 2. All the roots of
the polynomials $p_{5}(n,t)$ for $1\leq n\leq 500$.

In fact, we made pictures of the roots of many polynomials $p_{m}(n,t)$ with
small $m$ and large $n$ and all the pictures looked very similar to those that
we present here.

We move to the main part of this section. Lemma 4.2 below gives precise
description how and when the difference $|p_{m}(n,t)-tp_{m}(n-1,t)|$ is small
compared to $|tp_{m}(n,t)|$.

######  Lemma 4.2.

Let $\varepsilon\in(0,1)$. If
$|t|>\max\left\\{\varepsilon^{-\frac{1}{m-1}},\big{(}\varepsilon(1-\varepsilon)\big{)}^{-\frac{1}{m}}\right\\}$,
then

$\displaystyle|p_{m}(n,t)-tp_{m}(n-1,t)|<\varepsilon|tp_{m}(n-1,t)|.$

###### Proof.

If $m\nmid n$, then $|p_{m}(n,t)-tp_{m}(n-1,t)|=0$ and the statement is
clearly true. Therefore, it is enough to show that

(8) $\displaystyle|p_{m}(mn,t)-tp_{m}(mn-1,t)|<\varepsilon|tp_{m}(mn-1,t)|$

for every $n$. For $n=1$ and for every $t$ such that
$|t|>1/\varepsilon^{1/(m-1)}$ we have

$\displaystyle|p_{m}(m,t)-tp_{m}(m-1,t)|=|(t^{m}+t)-t\cdot
t^{m-1}|=|t|<\varepsilon|t|^{m}=\varepsilon|tp_{m}(m-1,t)|.$

Let us assume that (8) holds for all $k<n$. We want to prove it for $n$. Let
us observe that the induction hypothesis (that is, (8) with $k$ used instead
of $n$) implies

(9)
$\displaystyle|p_{m}(mk,t)|<\frac{1}{|t|^{m}(1-\varepsilon)}|p_{m}(m(k+1),t)|$

for all $k\leq n-2$. Indeed, (8) gives

$\displaystyle|p_{m}(m(k+1),t)|\geq$ $\displaystyle\
|tp_{m}(m(k+1)-1,t)|-|p_{m}(m(k+1),t)-tp_{m}(m(k+1)-1,t)|$ $\displaystyle>$
$\displaystyle\ (1-\varepsilon)|tp_{m}(m(k+1)-1,t)|,$

and hence,

$\displaystyle|p_{m}(mk,t)|=$ $\displaystyle\
\frac{1}{|t|^{m-1}}|p_{m}(m(k+1)-1,t)|$ $\displaystyle<$ $\displaystyle\
\frac{1}{|t|^{m-1}}\cdot\frac{1}{|t|(1-\varepsilon)}|p_{m}(m(k+1),t)|=\frac{1}{|t|^{m}(1-\varepsilon)}|tp_{m}(m(k+1),t)|.$

Let us now write $n=mn^{\prime}+r$ for some $r\in\\{0,\ldots,m-1\\}$. We apply
(9) $(n-1)-n^{\prime}$ times and get

$\displaystyle|p_{m}(mn^{\prime},t)|<\frac{1}{|t|^{m(n-n^{\prime}-1)}(1-\varepsilon)^{n-n^{\prime}-1}}|p_{m}(m(n-1),t)|.$

Finally, we have the following chain of (in)equalities:

$\displaystyle|p_{m}(mn,t)-tp_{m}(mn-1,t)|=$ $\displaystyle\
|p_{m}(n,t)|=|p_{m}(mn^{\prime}+r,t)|=|t|^{r}|p_{m}(mn^{\prime},t)|$
$\displaystyle<$ $\displaystyle\
\frac{|t|^{r}}{|t|^{m(n-n^{\prime}-1)}(1-\varepsilon)^{n-n^{\prime}-1}}|p_{m}(m(n-1),t)|$
$\displaystyle=$ $\displaystyle\
\frac{|t|^{r-(m-1)}}{|t|^{m(n-n^{\prime}-1)}(1-\varepsilon)^{n-n^{\prime}-1}}|p_{m}(m(n-1)+(m-1),t)|$
$\displaystyle\leq$ $\displaystyle\
\frac{1}{|t|^{m(n-n^{\prime}-1)}(1-\varepsilon)^{n-n^{\prime}-1}}|p_{m}(mn-1,t)|.$

In order to finish the proof, it is enough to check when the expression at the
end of the last chain of inequalities is less than or equal to
$\varepsilon|tp_{m}(mn-1,t)|$. This is equivalent to

$\displaystyle\frac{1}{|t|^{m(n-n^{\prime}-1)}(1-\varepsilon)^{n-n^{\prime}-1}}\leq\varepsilon|t|.$

Since $|t|>1$, it is enough to check whether

$\displaystyle\frac{1}{|t|^{m(n-n^{\prime}-1)}(1-\varepsilon)^{n-n^{\prime}-1}}\leq\varepsilon,$

that is,

$\displaystyle|t|\geq\frac{1}{\varepsilon^{1/(m(n-n^{\prime}-1))}(1-\varepsilon)^{1/m}}.$

We have $n-n^{\prime}-1\geq 1$ so it is enough to have

$\displaystyle|t|\geq\frac{1}{\varepsilon^{1/m}(1-\varepsilon)^{1/m}}.$

This finishes the proof. ∎

At this point, we can just conclude that the theorem below follows from
Rouche’s theorem, as we did in the heuristic argument at the beginning of this
section. However, the inequality from Lemma 4.2 used in more explicit way
provides the same information with an additional lower bound for $p_{m}(n,t)$
when $|t|\geq 4^{1/m}$.

######  Theorem 4.3.

If $t\in\mathbb{C}$ is such that $p_{m}(n,t)=0$, then $|t|<4^{1/m}$.

###### Proof.

From Lemma 4.2 with $\varepsilon=\frac{1}{2}$ we get that if
$|t|>\max\\{2^{1/(m-1)},4^{1/m}\\}=4^{1/m}$, then

$\displaystyle|p_{m}(n,t)|>\frac{1}{2}|tp_{m}(n-1,t)|$

for all $n$. In particular, if $|t|>4^{1/m}=2^{2/m}$ we have

$\displaystyle|p_{m}(n,t)|>\frac{|t|^{n}}{2^{n}}|p_{m}(0,t)|=\frac{|t|^{n}}{2^{n}}>2^{\left(\frac{2}{m}-1\right)n}.$

Thus $p_{m}(n,t)\neq 0$ if $|t|>4^{1/m}$. Moreover, each polynomial
$p_{m}(n,t)$ is a continuous function and we proved that the values of
$p_{m}(n,t)$ for $|t|>4^{1/m}$ are bounded away from $0$ by a constant
independent of $t$. Therefore, $p_{m}(n,t)\neq 0$ if $|t|=4^{1/m}$. The result
follows. ∎

Now we can prove the following fact that we predicted at the beginning of this
section.

######  Corollary 4.4.

For all $m\geq 2$, all roots of $m$-ary partition polynomials lay inside the
circle of radius $2$ centered in the origin.

###### Proof.

By Theorem 4.3 it is enough to observe, that $4^{1/m}\leq 4^{1/2}=2$ for
$m\geq 2$. ∎

We finish our study of complex roots of $m$-ary partition polynomials by the
following observation. The figures 2. and 2 show some symmetries. Especially,
some roots seem to lie on (rotated and scaled) $(m-1)$th roots of unity. We
will explain this phenomenon in the next result.

######  Theorem 4.5.

  1. (1)

Let $\widetilde{p_{m}}(n,t):=\frac{1}{t^{s_{m}(n)}}p_{m}(n,t)$. Then
$\widetilde{p_{m}}(n,t)\in\mathbb{N}_{0}\left[t^{m-1}\right]$.

  2. (2)

Let $P_{m}(n,q):=\widetilde{p_{m}}(mn,q^{1/(m-1)})$. Then
$P_{m}(n,q)\in\mathbb{N}_{0}[q]$. Moreover, we have the following recurrence:
$P_{m}(k)=\frac{q^{k+1}-1}{q-1}$ for $k\in\\{0,\ldots,m-1\\}$, and

$\displaystyle
P_{m}(n)=q^{1+\nu_{m}(n)}P(n-1,q)+P_{m}\left(\left\lfloor\frac{n}{m}\right\rfloor,q\right)$

for $n\geq 2$, where $\nu_{m}(n)$ denotes the highest power of $m$ that
divides $n$.

###### Proof.

From Example 2.1 we immediately get

$\displaystyle\widetilde{p_{m}}(km,t)=\frac{1}{t^{k}}p_{m}(km,t)=\frac{t^{(m-1)(k+1)}-1}{t^{m-1}-1},$

so indeed $P_{m}(k,q)=\frac{q^{k+1}-1}{q-1}$ for $k\in\\{0,\ldots,m-1\\}$.

Recurrence relations (7) imply

$\displaystyle\frac{1}{t^{s_{m}(mn)}}p_{m}(mn,t)=t^{s_{m}(n-1)-s_{m}(n)+1}t^{m-1}\left(\frac{1}{t^{s_{m}(n-1)}}p_{m}(m(n-1),t)\right)+\frac{1}{t^{s_{m}(n)}}p_{m}(n,t),$

or

$\displaystyle\widetilde{p_{m}}(mn,t)=t^{s_{m}(n-1)-s_{m}(n)+1}t^{m-1}\widetilde{p_{m}}(m(n-1),t)+\widetilde{p_{m}}(n,t).$

Let us study the quantity $s_{m}(n-1)-s_{m}(n)+1$. Let
$n=\sum_{j=h}^{r}a_{j}m^{j}$, where $a_{h}\geq 1$. Then $h=\nu_{m}(n)$ and

$\displaystyle n-1$
$\displaystyle=\sum_{j=h+1}^{r}a_{j}m^{j}+(a_{h}-1)m^{h}+(m-1)m^{h-1}+\cdots+(m-1)m+(m-1).$

Therefore,

$\displaystyle s_{m}(n-1)-s_{m}(n)+1$
$\displaystyle=\sum_{j=h+1}^{r}a_{j}+(a_{h}-1)+(m-1)h-\sum_{j=h}^{r}a_{j}+1$
$\displaystyle=(m-1)h=(m-1)\nu_{m}(n).$

Hence,

$\displaystyle\widetilde{p_{m}}(mn,t)=t^{(m-1)(\nu_{m}(n)+1)}\widetilde{p_{m}}(m(n-1),t)+\widetilde{p_{m}}(n,t),$

and we get by a simple induction argument, that indeed
$\widetilde{p_{m}}(mn,t)\in\mathbb{N}[t^{m-1}]$. By putting the definition of
$P_{m}(n,q)$ into above equality, we immediately get the second part of the
theorem. ∎

##  5\. Certain properties modulo another polynomials

The aim of this section is to provide a polynomial generalization of the known
characterisation of the number of $m$-ary partitions of $n$ modulo $m$ that
depends on the $m$-ary representation of $n$. Recall, that if
$n=a_{0}+a_{1}m+\cdots+a_{k}m^{k}$, then

(10) $\displaystyle p_{m}(n,1)\equiv\prod_{j=1}^{k}(a_{j}+1)\pmod{m}.$

The above result was independently proved by Alkauskas in [1], and Andrews,
Freankel and Sellers in [4]. Another proofs were found by Edgar in [10] and
Żmija in [26].

Very interestingly, we will prove analogous characterisation for a more
general class of $M$-ary partitions. Moreover, a polynomial version of this
characterisation can be provided. We will do it in Theorem 5.3.

Recall that $M=(m_{n})_{n=0}^{\infty}$ is a sequence of integers such that
$m_{0}=1$ and $m_{n}\geq 2$ for $n\geq 1$, and
$M^{\prime}=(1,m_{2},m_{3},\ldots)$. In other words, $M^{\prime}$ is the
sequence obtained from $M$ by omitting $m_{1}$.

We begin by the following technical lemma.

######  Lemma 5.1.

Let $n=km_{2}+r$, where $r\in\\{0,1,\ldots,m_{2}-1\\}$, and
$f(m,t):=\frac{t^{m}-1}{t-1}$ for an integer $m\geq 0$. Then

$\displaystyle p_{M}(m_{1}n,t)\equiv
t^{r}f(r+1,t^{m_{1}-1})p_{M^{\prime}}(km_{2},t)\pmod{t^{m_{1}+m_{2}-1}f(m_{2},t^{m_{1}-1})}.$

###### Proof.

At first, let us observe, that for every $k\leq n$ the following equality is
true:

(11) $\displaystyle
p_{M}(m_{1}n,t)=t^{km_{1}}p_{M}(m_{1}(n-k),t)+\sum_{j=0}^{k-1}t^{jm_{1}}p_{M^{\prime}}(n-j,t).$

Indeed, the case $k=1$ follows immediately from equations (3), and if it is
true for some $k$, then for $k+1$ we get:

$\displaystyle p_{M}(m_{1}n,t)=$ $\displaystyle\
t^{km_{1}}p_{M}(m_{1}(n-k),t)+\sum_{j=0}^{k-1}t^{jm_{1}}p_{M^{\prime}}(n-j,t)$
$\displaystyle=$ $\displaystyle\
t^{km_{1}}\big{(}t^{m_{1}}p_{M}(m_{1}(n-(k+1)),t)+p_{M^{\prime}}(n-k,t)\big{)}+\sum_{j=0}^{k-1}t^{jm_{1}}p_{M^{\prime}}(n-j,t)$
$\displaystyle=$ $\displaystyle\
t^{(k+1)m_{1}}p_{M}(m_{1}(n-(k+1)),t)+\sum_{j=0}^{k}t^{jm_{1}}p_{M^{\prime}}(n-j,t).$

In particular, for $k=n$ from (11) we get:

(12) $\displaystyle p_{M}(m_{1}n,t)=$ $\displaystyle\
t^{nm_{1}}p_{M}(0,t)+\sum_{j=0}^{n-1}t^{jm_{1}}p_{M^{\prime}}(n-j,t)$
$\displaystyle=$ $\displaystyle\
\sum_{j=0}^{n}t^{jm_{1}}p_{M^{\prime}}(n-j,t)=\sum_{j=0}^{n}t^{(n-j)m_{1}}p_{M^{\prime}}(j,t).$

If we use (3) for $M^{\prime}$ instead of $M$, we get
$p_{M^{\prime}}(m_{2}n+j,t)=t^{j}p_{M^{\prime}}(m_{2}n,t)$ for
$j\in\\{0,\ldots,m_{2}-1\\}$. Hence, for $l\in\\{0,\ldots,k-1\\}$ we have

$\displaystyle\sum_{j=lm_{2}}^{lm_{2}+m_{2}-1}t^{(n-j)m_{1}}p_{M^{\prime}}(j,t)=$
$\displaystyle\
\sum_{j=0}^{m_{2}-1}t^{(n-lm_{2}-j)m_{1}}p_{M^{\prime}}(lm_{2}+j,t)$
$\displaystyle=$ $\displaystyle\
\sum_{j=0}^{m_{2}-1}t^{(n-lm_{2}-j)m_{1}}\cdot t^{j}p_{M^{\prime}}(lm_{2},t)$
$\displaystyle=$ $\displaystyle\
t^{(n-lm_{2})m_{1}}p_{M^{\prime}}(lm_{2},t)\sum_{j=0}^{m_{2}-1}t^{(1-m_{1})j}$
$\displaystyle=$ $\displaystyle\
p_{M^{\prime}}(lm_{2},t)t^{(n-lm_{2})m_{1}}\frac{1-t^{(1-m_{1})m_{2}}}{1-t^{1-m_{1}}}$
$\displaystyle=$ $\displaystyle\
p_{M^{\prime}}(lm_{2},t)t^{(n-lm_{2})m_{1}}\cdot\frac{t^{(1-m_{1})m_{2}}}{t^{1-m_{1}}}\cdot\frac{t^{(m_{1}-1)m_{2}}-1}{t^{m_{1}-1}-1}$
$\displaystyle=$ $\displaystyle\
p_{M^{\prime}}(lm_{2},t)t^{(n-lm_{2})m_{1}+(1-m_{1})m_{2}-(1-m_{1})}\frac{t^{(m_{1}-1)m_{2}}-1}{t^{m_{1}-1}-1}.$

Observe that

$\displaystyle(n-lm_{2})m_{1}+(1-m_{1})m_{2}-(1-m_{1})\geq$ $\displaystyle\
(km_{2}-(k-1)m_{2})m_{1}-m_{1}m_{2}+m_{1}+m_{2}-1$ $\displaystyle=$
$\displaystyle\ m_{1}+m_{2}-1,$

and thus

(13)
$\displaystyle\sum_{j=lm_{2}}^{lm_{2}+m_{2}-1}t^{(n-j)m_{1}}p_{M^{\prime}}(j,t)\equiv
0\pmod{t^{m_{1}+m_{2}-1}f(m_{2},t^{m_{1}-1})}.$

We perform similar computation in the case of $l=k$ and obtain

$\displaystyle\sum_{j=km_{2}}^{km_{2}+r}t^{(n-j)m_{1}}p_{M^{\prime}}(j,t)=$
$\displaystyle\ \sum_{j=0}^{r}t^{(n-km_{2}-j)m_{1}}p_{M^{\prime}}(km_{2}+j,t)$
$\displaystyle=$ $\displaystyle\
t^{rm_{1}}p_{M^{\prime}}(km_{2},t)\sum_{j=0}^{r}t^{(1-m_{1})j}$
$\displaystyle=$ $\displaystyle
p_{M^{\prime}}(km_{2},t)t^{rm_{1}}\frac{1-t^{(1-m_{1})(r+1)}}{1-t^{1-m_{1}}}$
$\displaystyle=$ $\displaystyle\
p_{M^{\prime}}(km_{2})t^{rm_{1}+(1-m_{1})(r+1)-(1-m_{1})}\frac{t^{(m_{1}-1)(r+1)}-1}{t^{m_{1}-1}-1}$
$\displaystyle=$ $\displaystyle\
p_{M^{\prime}}(km_{2},t)t^{r}\frac{t^{(m_{1}-1)(r+1)}-1}{t^{m_{1}-1}-1}=t^{r}f(r+1,t^{m_{1}-1}).$

The statement of our lemma simply follows from (12), (13) and the above
equality. ∎

In order to state the main theorem of this section we need to introduce some
notation. For a positive integer $n$ let $(n_{0},\ldots,n_{k})$ and
$(a_{0},\ldots,a_{k})$ be sequences constructed in the following way:

$\displaystyle\left\\{\begin{array}[]{ll}n_{0}:=\left\lfloor\frac{n}{m_{1}}\right\rfloor,&\\\
n_{j}:=\left\lfloor\frac{n_{j-1}}{m_{j}}\right\rfloor,&\textrm{ for }j\geq
1\\\ a_{j-1}:=n_{j-1}-m_{j}n_{j},&\textrm{ for }j\geq 1.\end{array}\right.$

In other words, numbers $a_{j}$ can be seen as (unique) coefficients in the
expansion

$\displaystyle
n=a_{0}+m_{1}(a_{1}+m_{2}(a_{2}+\cdots)))=a_{0}+a_{1}M_{1}+a_{2}M_{2}+\cdots+a_{k}M_{k},$

where $a_{j}\in\\{0,\ldots,m_{j+1}-1\\}$. We call the above representation an
$M$-ary representation of $n$. Let us prove, that this representation is
indeed unique.

######  Proposition 5.2.

For every $M$ and $n$ the coefficients in the expansion

$\displaystyle n=a_{0}+a_{1}M_{1}+\cdots+a_{k}M_{k}$

are unique.

###### Proof.

We use induction on $n$. For every sequence $M$, if $0\leq n\leq m_{1}-1$,
then the representation is obviously unique. Let us assume, that the
representation is unique for all numbers less than some $n$ and all sequences
$M$, and suppose that

$\displaystyle
n=a_{0}+a_{1}M_{1}+\cdots+a_{k}M_{k}=b_{0}+b_{1}M_{1}+\cdots+b_{l}M_{l}.$

All numbers $M_{j}$ for $j\geq 1$ are divisible by $m_{1}$. Therefore, the
difference $a_{0}-b_{0}$ has to be divisible by $m_{1}$. But $-(m_{1}-1)\leq
a_{0}-b_{0}\leq m_{1}-1$ so $a_{0}=b_{0}$. Hence we get

$\displaystyle\frac{n-a_{0}}{m_{1}}=a_{1}M^{\prime}_{1}+\cdots+a_{k}M^{\prime}_{k}=b_{1}M^{\prime}_{1}+\cdots+b_{l}M^{\prime}_{l}.$

Now we can use the induction hypothesis to the number $(n-a_{0})/m_{1}$ and
get $k=l$ and $a_{j}=b_{j}$ for all positive $j$’s. Hence, both of the above
representations are equal. Therefore the number $n$ has only one
representation. The proof is finished. ∎

For two monic polynomials $f_{1},f_{2}\in\mathbb{Z}[x]$ let
$\gcd(f_{1},f_{2})$ be a polynomial of the highest possible degree that
divides both $f_{1}$ and $f_{2}$. For polynomials $f_{1},\ldots,f_{k}$ we
define their greatest common divisor inductively as

$\displaystyle\gcd(f_{1},\ldots,f_{k}):=\gcd(\gcd(f_{1},\ldots,f_{k-1}),f_{k}).$

We are ready to state the main theorem of this section of the paper.

######  Theorem 5.3.

For a positive integer $h$ let us define

$\displaystyle
g_{h}(t):=\gcd\big{(}t^{m_{1}+m_{2}-1}f(m_{2},t^{m_{1}-1}),\ldots,t^{m_{h}+m_{h+1}-1}f(m_{h+1},t^{m_{h}-1})\big{)}.$

Let $n\in\mathbb{N}$ and $n=a_{0}+a_{1}M_{1}+\cdots+a_{k}M_{k}$ be its $M$-ary
representation. Then

$\displaystyle p_{M}(n,t)\equiv
t^{a_{0}}\prod_{j=1}^{k}t^{a_{j}}f(a_{j}+1,t^{m_{j}-1})\pmod{g_{k}(t)}.$

###### Proof.

We use an induction on $k$. For $k=0$, that is, if $n=a_{0}$, the statement
follows from (3). Assume that it is true for all sequences $M$ and all natural
numbers with at most $k$ coefficients in their $M$-ary representations. Let
$n=a_{0}+a_{1}M_{1}+\cdots+a_{k}M_{k}$, that is, $n$ has $k+1$ coefficients.
Let $n_{1}$ and $n_{2}$ be such that $n=n_{1}m_{1}+a_{0}$ and
$n_{1}=n_{2}m_{2}+a_{1}$. Then Lemma 5.1 and the induction hypothesis (used
for $M^{\prime}$ instead of $M$ and $n_{1}$ instead of $n$) implies

$\displaystyle p_{M}(n,t)=$ $\displaystyle\
p_{M}(n_{1}m_{1}+a_{0},t)=t^{a_{0}}p_{M}(n_{1}m_{1},t)\equiv t^{a_{0}}\cdot
t^{a_{1}}f(a_{1}+1,t^{m_{1}-1})p_{M^{\prime}}(n_{2}m_{2},t)$
$\displaystyle\equiv$ $\displaystyle\ t^{a_{0}}\cdot
t^{a_{1}}f(a_{1}+1,t^{m_{1}-1})\cdot\prod_{j=2}^{k}t^{a_{j}}f(a_{j}+1,t^{m_{j}-1})\pmod{g_{k}(t)}.$

This finishes the proof. ∎

The above theorem has interesting consequences. We list some of them.

######  Corollary 5.4.

Let $n=n_{0}+n_{1}m+\cdots+n_{s}m^{s}$ be the representation of $n$ in base
$m$. For a natural number $k$ let us consider the polynomial

$\displaystyle f_{k}(t):=\frac{t^{(m-1)k}-1}{t^{m-1}-1}.$

Then

$\displaystyle p_{m}(n,t)\equiv
t^{n_{0}}\prod_{j=1}^{s}t^{n_{j}}f_{n_{j}+1}(t)\pmod{t^{2m-1}f_{m}(t)}.$

###### Proof.

Put $M=(1,m,m,\ldots)$ in Theorem 5.3. ∎

######  Corollary 5.5.

Let $n=a_{0}+a_{1}M_{1}+\cdots+a_{k}M_{k}$ be the representation of $n$ in
base $M$. Then

$\displaystyle
p_{M}(n)\equiv\prod_{j=1}^{k}(a_{j}+1)\pmod{\gcd(m_{1},\ldots,m_{k})}.$

###### Proof.

Put $t\to 1$ in Theorem 5.3. ∎

At the end note, that the statement of Corollary 5.4 looks especially elegant
if we use the polynomials $P_{m}(n,t)$ introduced in Theorem 4.5, and some
notation from so-called quantum calculus. Roughly speaking, quantum calculus
is a theory in which we replace classical definition of derivative of a
function $f(x)$ by its $q$-analogue:

$\displaystyle D_{q}f(x):=\frac{f(qx)-f(x)}{(q-1)x}.$

In quantum calculus, the role of positive integers $n$ is played by the
following polynomials in $q$:

$\displaystyle[n]_{q}:=\frac{q^{n}-1}{q-1}.$

Indeed, we have for example that then $D_{q}(x^{n})=[n]_{q}x^{n-1}$. For more
details see [7].

With the above notation in mind, we can rephrase Corollary 5.4 in the
following very elegant way.

######  Corollary 5.6.

Let $n=a_{1}+a_{2}m+\cdots+a_{k}m^{k-1}$. Then

$\displaystyle P_{m}(n,q)\equiv\prod_{j=1}^{k}[a_{j}+1]_{q}\pmod{[m]_{q}}.$

In other words, our result may be seen as a quantum generalisation of the
characterisation (10) of the sequence of $m$-ary partitions modulo $m$.

##  6\. Coefficients of $M$-ary partition polynomials

We devote the next part of this paper to study of the coefficients of
polynomials $p_{M}(n,t)$. Let us write

$\displaystyle p_{M}(n,t)=\sum_{j=0}^{n}a_{M}(j,n)t^{j}.$

Recall that then $a_{M}(j,n)$ is equal to the number of $M$-ary partitions of
$n$ with exactly $j$ parts.

From relations (3) we have

(14) $\displaystyle a_{M}(j,n)=a_{M}(j-1,n-1)+a_{M^{\prime}}(j,n/m_{1}),$

where we use a convention that $a_{M}(i,q)=0$ if $i>q$ or
$q\not\in\mathbb{N}$.

Our aim is to generalize results from [23], where the case of binary partition
polynomials (that is, $m=2$) was considered. We will study two types of
sequences. At first, we will narrow aour considerations down to the $m$-ary
case and focus on the sequence $(a_{M}(k,n))_{n=0}^{\infty}$. This is the
sequence of coefficients of $t^{k}$ of consecutive $m$-ary partition
polynomials, where $k$ is a fixed natural number. In particular, we will prove
that for each $k$ this sequence is bounded. It is important to note that in
[23] the following bound has been showed in the case of binary partition
polynomials: $a_{2}(j,n)\leq j!$ for all $n$. However, there was a mistake in
the proof. Fortunately, we use a bit different approach here and prove a
better bound in Theorem 6.3 below. More details in the case of $m=2$ are
provided in the remark after Theorem 6.3.

The second sequence that will be interesting for us is
$(a_{M}(n-k,n))_{n=0}^{\infty}$, that is, sequence of coefficients of
$t^{n-k}$ in polynomials $p_{M}(n,t)$, where $k$ is again a fixed positive
integer. We will prove that this sequence is eventually constant and relate
this constant value to another kind of partitions, that is, partitions with
parts of the form $M_{j}-1$. This relation was found in the special case when
$M_{j}=2^{j}$ for all $j\geq 1$ in [23]. The sequence counting partitions into
parts of the form $2^{j}-1$ is known as a sequence of $s$-partitions and was
introduced by Bhatt in [6]. He used some properties of this sequence in his
algorithm that computes expressions of the form $a^{n}\mod{m}$. Another
properties of the sequence of $s$-partitions were studied in [12].

Let us begin with two lemmas. Lemma 6.1 is especially interesting because it
implies that for every $j$, there are infinitely many zeroes in the sequence
$(a_{m}(j,n))_{n=0}^{\infty}$.

######  Lemma 6.1.

Let $j$, $r\geq 1$, and let $m\nmid n$. If $a_{m}(j,m^{r}n-1)\geq 1$, then
$j\geq(m-1)r$.

###### Proof.

Let us assume that there is a representation

$\displaystyle m^{r}n-1=m^{s_{1}}+\cdots+m^{s_{j}},$

for some non-negative integers $s_{1}\leq\ldots\leq s_{j}$. If we have
$s_{l}=\ldots=s_{l+m-1}$ for some $l$, we can replace these $m$ powers of $m$
by a single power $m^{s_{l}+1}$. We then get another representation with
possibly smaller number of parts. We can perform this procedure as many times
as possible and get representation of the form

$\displaystyle m^{r}n-1=m^{t_{1}}+\cdots+m^{t_{j^{\prime}}}$

with $t_{1}\geq\ldots\geq t_{j^{\prime}}$, where each power occurs at most
$m-1$ times, and $j^{\prime}\leq j$. Consider the above equality modulo
$m^{r}$, that is,

$\displaystyle-1\equiv m^{t_{1}}+\cdots+m^{t_{l}}\pmod{m^{r}},$

where $1\leq t_{1}\leq\ldots\leq t_{l}\leq r-1$ and $j^{\prime}\geq l$.
Observe, that

$\displaystyle
m^{t_{1}}+\cdots+m^{t_{l}}\leq(m-1)(1+\cdots+m^{r-1})=m^{r}-1<m^{r}.$

Hence,

$\displaystyle m^{r}-1=m^{t_{1}}+\cdots+m^{t_{l}},$

and because this is the largest possible value of the expression on the right-
hand side, we need to have $l=(m-1)r$. Thus $j\geq j^{\prime}\geq l=(m-1)r$,
and we are done. ∎

######  Lemma 6.2.

Let $n$, $r\geq 0$ be such that $m\nmid n$. Then the following equality holds:

$\displaystyle
a_{m}(k,m^{r}n)=\sum_{j=0}^{r-1}a_{m}(k-1,m^{r-j}n-1)+a_{m}(k,n).$

###### Proof.

We prove that for every $N\geq 0$ such that $N\in\\{0,\ldots,r-1\\}$ we have:

$\displaystyle
a_{m}(k,m^{r}n)=\sum_{j=0}^{N}a_{m}(k-1,m^{r-j}n-1)+a_{m}(k,m^{r-N-1}n).$

Indeed, for $N=0$ this is exactly (14), and if it is true for some $N$, then
for $N+1$, using (14), we get the following chain of equalities:

$\displaystyle a_{m}(k,m^{r}n)=$
$\displaystyle\sum_{j=0}^{N}a_{m}(k-1,m^{r-j}n-1)+a_{m}(k,m^{r-N-1}n)$
$\displaystyle=$
$\displaystyle\sum_{j=0}^{N}a_{m}(k-1,m^{r-j}n-1)+a_{m}(k-1,m^{r-N-1}n)+a_{m}(k,m^{r-N-1-1}n)$
$\displaystyle=$
$\displaystyle\sum_{j=0}^{N+1}a_{m}(k-1,m^{r-j}n-1)+a_{m}(k,m^{r-(N+1)-1}n).$

The result follows by putting $N=r-1$. ∎

######  Theorem 6.3.

Let $k\in\mathbb{N}$ and $n\equiv i\pmod{m}$ for some
$i\in\\{0,\ldots,m-1\\}$. Then the following inequality holds:

$\displaystyle
a_{m}(k,n)\leq\left(\frac{m}{m-1}\right)^{\lfloor(k-i)/m\rfloor}\ \
\prod_{j=0}^{\lfloor(k-i)/m\rfloor-1}\left(k-i-jm\right).$

In particular, the sequence $(a_{m}(k,n))_{n=0}^{\infty}$ is bounded.

###### Proof.

We want to find for $i\in\\{0,\ldots,m-1\\}$ sequences $c_{k}^{(i)}$ such that
for every $n$ if $n\equiv i\pmod{m}$ then $a_{m}(k,n)\leq c_{k}^{(i)}$. For
$k=0$ and $k=1$ we have $a_{m}(0,n)=1$ and

$\displaystyle a_{m}(1,n)=\left\\{\begin{array}[]{ll}1,&\textrm{if }n\textrm{
is a power of }m,\\\ 0,&\textrm{otherwise}.\end{array}\right.$

Hence $a_{m}(1,n)\leq 1$ and we can define $c_{1}^{(i)}=1$ for every $i$.

Now we want to express every $c_{k}^{(i)}$ in terms of the numbers
$c_{k-1}^{(j)}$. If $n=mn_{1}+a_{0}$ for some $a_{0}\in\\{1,\ldots,m-1\\}$,
then by (14) we get

$\displaystyle a_{m}(k,n)=a_{m}(k-1,n-1)\leq c_{k-1}^{(a_{0}-1)},$

so we can take $c_{k}^{(a_{0})}:=c_{k-1}^{(a_{0}-1)}$.

Let us now assume that $n=m^{r_{1}}n_{1}$ where $m\nmid n_{1}$. Observe, that
for some $r\leq\frac{k}{m-1}$ we have

$\displaystyle a_{m}(k,m^{r_{1}}n_{1})=a_{m}(k,m^{r}n_{1}).$

Indeed, if $r_{1}\leq\frac{k}{m-1}$, then we can take $r=r_{1}$. Otherwise, by
(14) and Lemma 6.1 (used with $j=k-1$) we have

$\displaystyle
a_{m}(k,m^{r_{1}}n_{1})=a_{m}(k-1,m^{r_{1}}n_{1}-1)+a_{m}(k,m^{r_{1}-1}n_{1})=a_{m}(k,m^{r_{1}-1}n_{1}).$

Now, if $r_{1}-1\leq k/(m-1)$ we take $r=r_{1}-1$. Otherwise, we repeat the
procedure.

We assume that $n_{1}\equiv i\pmod{m}$ for some $i\in\\{1,\ldots,m-1\\}$.
Finally, we use Lemma 6.2 to get

$\displaystyle a_{m}(k,m^{r_{1}}n_{1})$
$\displaystyle=a_{m}(k,m^{r}n_{1})=\sum_{j=0}^{r-1}a_{m}(k-1,m^{r-j}n_{1}-1)+a_{m}(k,n_{1})$
$\displaystyle\leq\sum_{j=0}^{r-1}c_{k-1}^{(m-1)}+c_{k}^{(i)}=rc_{k-1}^{(m-1)}+c_{k-1}^{(i-1)}\leq\left\lfloor\frac{k}{m-1}\right\rfloor
c_{k-1}^{(m-1)}+c_{k-1}^{(i-1)}.$

Suppose further that the numbers $c_{j}^{(i)}$ satisfy $c_{j}^{(i)}\leq
c_{j}^{(0)}$ for every $j$ and every $i\in\\{0,\ldots,m-1\\}$. Therefore, we
can define

$\displaystyle c_{k}^{(0)}:=\left\lfloor\frac{k}{m-1}\right\rfloor
c_{k-1}^{(m-1)}+c_{k-1}^{(0)}.$

Using the information obtained so far, we can conclude that if $n\equiv
i\pmod{m}$ then $a_{m}(k,n)\leq c_{k}^{(i)}=c_{k-i}^{(0)}$. Therefore, in
order to finish the proof, we need to find upper bounds for the terms in the
sequence $C_{k}:=c_{k}^{(0)}$, which satisfies the following recurrence
relation: $C_{j}=1$ for $j\in\\{0,\ldots,m-1\\}$, and
$C_{k}=C_{k-1}+\left\lfloor\frac{k}{m-1}\right\rfloor C_{k-m}$ for $k\geq m$.
Of course, the sequence $(C_{k})_{k=0}^{\infty}$ is then increasing, so

$\displaystyle C_{k}$
$\displaystyle=C_{k-1}+\left\lfloor\frac{k}{m-1}\right\rfloor
C_{k-m}=C_{k-2}+\left\lfloor\frac{k-1}{m-1}\right\rfloor
C_{k-1-m}+\left\lfloor\frac{k}{m-1}\right\rfloor C_{k-m}$ $\displaystyle\leq
C_{k-2}+\left(\left\lfloor\frac{k-1}{m-1}\right\rfloor+\left\lfloor\frac{k}{m-1}\right\rfloor\right)C_{k-m}$
$\displaystyle=C_{k-3}+\left\lfloor\frac{k-2}{m-1}\right\rfloor
C_{k-2-m}+\left(\left\lfloor\frac{k-1}{m-1}\right\rfloor+\left\lfloor\frac{k}{m-1}\right\rfloor\right)C_{k-m}$
$\displaystyle<C_{k-3}+\left(\left\lfloor\frac{k-2}{m-1}\right\rfloor+\left\lfloor\frac{k-1}{m-1}\right\rfloor+\left\lfloor\frac{k}{m-1}\right\rfloor\right)C_{k-m}$
$\displaystyle<C_{k-m}+\left(\left\lfloor\frac{k-m+1}{m-1}\right\rfloor+\cdots+\left\lfloor\frac{k}{m-1}\right\rfloor\right)C_{k-m}$
$\displaystyle=\left(1+\left\lfloor\frac{k}{m-1}\right\rfloor-1+\left\lfloor\frac{k-m+2}{m-1}\right\rfloor+\cdots+\left\lfloor\frac{k}{m-1}\right\rfloor\right)C_{k-m}$
$\displaystyle\leq m\left\lfloor\frac{k}{m-1}\right\rfloor
C_{k-m}\leq\frac{mk}{m-1}C_{k-m}.$

The above inequality implies, by a simple induction argument, that for every
$t\leq k/m$ we have

$\displaystyle C_{k}<\left(\frac{m}{m-1}\right)^{t}\ \
\prod_{j=0}^{t-1}\left(k-jm\right)C_{k-tm}.$

In particular, for $t=\lfloor k/m\rfloor$, we get

$\displaystyle C_{k}<\left(\frac{m}{m-1}\right)^{\lfloor k/m\rfloor}\ \
\prod_{j=0}^{\lfloor k/m\rfloor-1}\left(k-jm\right).$

The result follows. ∎

######  Remark 6.4.

Observe, that the expression from the bound from Theorem 6.3 is decreasing in
$m$, so we can find a bound which is uniform in $m$ and $n$:

$\displaystyle a_{m}(k,n)\leq 2^{\lfloor k/2\rfloor}\ \ \prod_{j=0}^{\lfloor
k/2\rfloor-1}(k-2j)=\left\\{\begin{array}[]{ll}2^{k}\left(\frac{k}{2}\right)!,&\textrm{if
}k\textrm{ is even},\\\ \frac{k!}{\left(\frac{k-1}{2}\right)!},&\textrm{if
}k\textrm{ is odd}.\end{array}\right.$

This significantly improves the bound $a_{2}(2k+i,n)\leq(2k+i)!$ for
$i\in\\{0,1\\}$ from [23].

In order to further study the sequence $(a_{M}(k,n))_{n=0}^{\infty}$, let us
define

$\displaystyle A_{M}(k,x):=\sum_{n=0}^{\infty}a_{M}(k,n)x^{n}.$

More precisely, we are now interested in the sequence of coefficients of
$x^{k}$ in consecutive polynomials $p_{m}(n,t)$, where $k$ is fixed and $n$
varies. Our aim is to generalize results from [23] related to the coefficients
of binary partition polynomials.

From (14) we get

$\displaystyle A_{M}(k,x)-xA_{M}(k-1,x)=A_{M^{\prime}}(k,x^{m_{1}}).$

We focus on the $m$-ary case, so in particular $M=M^{\prime}$. The above
relation simplifies to

(15) $\displaystyle A_{m}(k,x)-xA_{m}(k-1,x)=A_{m}(k,x^{m}),$

where we write $A_{m}(k,x)$ instead of $A_{M}(k,x)$ in this case.

Our aim is to show that for every $m$ and $k$, the function $A_{m}(k,x)$
satisfies a Mahler type functional equation, that is, an equation of the form

$\displaystyle\sum_{j=0}^{t}f_{j}(x)A_{m}\left(k,x^{m^{j}}\right)+g(x)=0$

for some polynomials $f_{j}(x)$ and $g(x)$, and a positive integer $t$.

######  Theorem 6.5.

Let $m\geq 2$ and $k\geq 1$ be fixed. The function $A_{m}(k,x)$ satisfies the
equation

$\displaystyle\sum_{j=0}^{k}P_{k,j}(x)A_{m}\left(k,x^{m^{j}}\right)+Q_{k}(x)=0.$

Here $P_{k,j}(x)$ and $Q_{k}(x)$ are polynomials with integer coefficients
satisfying the following recurrence relations:

$\displaystyle\left\\{\begin{array}[]{ll}P_{0,0}(x)=1,&\\\ Q_{0}(x)=-1,&\\\
P_{k,0}(x)=x^{m^{k-1}-1}P_{k-1,0}(x),&\textrm{for }k\geq 1,\\\
P_{k,j}(x)=x^{m^{k}-m^{j}}P_{k-1,j}(x)-x^{m^{k-1}-m^{j-1}}P_{k-1,j-1}(x),&\textrm{for
}k\geq 1\textrm{ and }j\in\\{1,\ldots,k-1\\},\\\
P_{k,k}(x)=-P_{k-1,k-1}(x),&\\\
Q_{k}(x)=x^{m^{k-1}}Q_{k-1}(x).\end{array}\right.$

###### Proof.

We use an induction argument. For $k=1$ we get, from (15) the following
equation:

$\displaystyle
0=A_{m}(1,x)-xA_{m}(0,x)-A_{m}(1,x^{m})=A_{m}(1,x)-A_{m}(1,x^{m})-x.$

Assume that the statement is true for some $k-1$. That is, we assume that

$\displaystyle\sum_{j=0}^{k-1}P_{k-1,j}(x)A_{m}(k-1,x^{j})+Q_{k-1}(x)=0,$

or equivalently,

(16) $\displaystyle
A_{m}(k-1,x)=-\frac{\sum_{j=1}^{k-1}P_{k-1,j}(x)A_{m}(k-1,x^{j})+Q_{k-1}(x)}{P_{k-1,0}(x)}.$

Relation (15) implies that for every $j\geq 0$ we have

(17) $\displaystyle
A_{m}(k-1,x^{m^{j}})=\frac{A_{m}(k,x^{m^{j}})-A_{m}(k,x^{m^{j+1}})}{x^{m^{j}}}.$

Using (15), (16) and (17), we get

$\displaystyle A_{m}(k,x)-A_{m}(k,x^{m})=$ $\displaystyle\ xA_{m}(k-1,x)$
$\displaystyle=$ $\displaystyle\
-\frac{x}{P_{k-1,0}(x)}\left(\sum_{j=1}^{k-1}P_{k-1,j}(x)A_{m}(k-1,x^{j})+Q_{k-1}(x)\right)$
$\displaystyle=$ $\displaystyle\
-\frac{x}{P_{k-1,0}(x)}\left(\sum_{j=1}^{k-1}P_{k-1,j}(x)\frac{A_{m}(k,x^{m^{j}})-A_{m}(k,x^{m^{j+1}})}{x^{m^{j}}}+Q_{k-1}(x)\right).$

Thus

$\displaystyle x^{m^{k-1}-1}P_{k-1,0}(x)A_{m}(k,x)+\sum_{j=0}^{k-1}$
$\displaystyle\left(x^{m^{k}-m^{j}}P_{k-1,j}(x)-x^{m^{k-1}-m^{j-1}}P_{k-1,j-1}(x)\right)A_{m}(k,x^{m^{j}})$
$\displaystyle-$ $\displaystyle
P_{k-1,k-1}(x)A_{m}(k,x^{m^{k}})+x^{m^{k-1}}Q_{k-1}(x)=0,$

and the result follows. ∎

######  Corollary 6.6.

Let $m=p$ be a prime number. For every $k$ the sequence $(a_{p}(k,n)\
\mathrm{mod}\ p)_{n=0}^{\infty}$ is $p$-automatic.

###### Proof.

Theorem 6.5 implies that the function $A_{p}(k,x)$ satisfies the equation

$\displaystyle\sum_{j=0}^{k}P_{k,j}(n)A_{p}(k,x)^{p^{j}}+Q_{k}(x)\equiv
0\pmod{p}.$

In other words, $A_{p}(k,x)$ is algebraic over $\mathbb{F}_{p}$. The result
follows from Christol’s Theorem (Lemma 1.1). ∎

In the case of $m$ not being a prime we cannot use Christol’s Theorem and get
the analogous result. Therefore, we only state the following question for
possible future work.

######  Question 6.7.

Is the sequence $(a_{m}(k,n)\ \mathrm{mod}\ m)_{n=0}^{\infty}$ $m$-automatic
for every $k$?

Let us move to study the coefficients of $t^{n-k}$ in the $n$th $M$-ary
polynomial, where $k$ is a fixed positive integer. Observe that the difference
between two consecutive $M$-ary partition polynomials, where the former one is
multiplied by t, is always a polynomial of much smaller degree. This suggests
that for every $k$ the value of $a_{M}(n-k,n)$ is constant for sufficiently
large values of $n$. We prove this statement in the next theorem.

######  Theorem 6.8.

Let $k\in\mathbb{N}$. Then for every $n\geq\frac{km_{1}}{m_{1}-1}$ we have

$\displaystyle a_{M}(n-k,n)=\sum_{k/m_{1}\leq j\leq
k/(m_{1}-1)}a_{M^{\prime}}(m_{1}j-k,j).$

In particular, if $n\geq km_{1}/(m_{1}-1)$ and $1\leq k\leq m_{1}-2$, then
$a_{M}(n-k,n)=0$.

###### Proof.

Let

$\displaystyle G_{k}(x)=\sum_{n=0}^{\infty}a_{M}(n-k,n)x^{n},$

and observe that (14) implies

$\displaystyle G_{k}(x)=$
$\displaystyle\sum_{n=0}^{\infty}\big{(}a_{M}(n-k-1,n-1)+a_{M^{\prime}}(n-k,n/m_{1})\big{)}x^{n}$
$\displaystyle=$ $\displaystyle
x\sum_{n=1}^{\infty}a_{M}((n-1)-k,n-1)x^{n-1}+\sum_{n=0}^{\infty}a_{M^{\prime}}(n-k,n/m_{1})x^{n}$
$\displaystyle=$ $\displaystyle xG_{k}(x)+\sum_{k\leq n\leq
km_{1}/(m_{1}-1)}a_{M^{\prime}}(n-k,n/m_{1})x^{n},$

because $a(n-k,n/m_{1})=0$ if $n-k>n/m_{1}$, that is, if $n>km_{1}/(m_{1}-1)$.
Therefore,

$\displaystyle G_{k}(x)=$ $\displaystyle\frac{1}{1-x}\sum_{k\leq n\leq
km_{1}/(m_{1}-1)}a_{M^{\prime}}(n-k,n/m_{1})x^{n}$ $\displaystyle=$
$\displaystyle\
\sum_{n=0}^{\infty}\left(\sum_{j=0}^{n}a_{M^{\prime}}(j-k,j/m_{1})\right)x^{n}$
$\displaystyle=$ $\displaystyle\sum_{k\leq
n<km_{1}/(m_{1}-1)}\left(\sum_{j=0}^{n}a_{M^{\prime}}(j-k,j/m_{1})\right)x^{n}$
$\displaystyle\ \hskip 56.9055pt+\sum_{n\geq
km_{1}/(m_{1}-1)}\left(\sum_{k\leq j\leq
km_{1}/(m_{1}-1)}a_{M^{\prime}}(j-k,j/m_{1})\right)x^{n}.$

Hence, if $n\geq km_{1}/(m_{1}-1)$, then

$\displaystyle a_{M}(n-k,n)=$ $\displaystyle\sum_{k\leq j\leq
km_{1}/(m_{1}-1)}a_{M^{\prime}}(j-k,j/m_{1})=\sum_{k/m_{1}\leq j\leq
k/(m_{1}-1)}a_{M^{\prime}}(m_{1}j-k,j).$

This finishes the first part of our theorem. For the second part, it is enough
to notice that if $k<m_{1}-1$, then

$\displaystyle 0<\frac{k}{m_{1}}<\frac{k}{m_{1}-1}<1,$

so the sum in the expression defining $a_{M}(n-k,n)$ is empty. The result
follows. ∎

It turns out that the constant value of $a_{M}(n-k,n)$ for $n\geq
km_{1}/(m_{1}-1)$ is equal to the number of some another kind of partitions of
$n$. More precisely, let

$\displaystyle
S_{M}(x):=\prod_{n=1}^{\infty}\frac{1}{1-x^{M_{n}-1}}=\sum_{n=0}^{\infty}s_{M}(n)x^{n}.$

That is, for every $n$ the number $s_{M}(n)$ is equal to the number of
partitions of $n$ into parts of the form $M_{j}-1$. Here we note that the
special case of $m_{i}=2$ for all $i\geq 1$ we get the sequence partitions
into parts of the form $2^{n}-1$, $n\in\mathbb{N}$. They are called
$s$-partitions and were introduced in [6] by Bhatt, who applied them to some
problem coming from computer science. The sequence of $s$-partitions was also
studied in [12, 23].

The following relation is true.

######  Corollary 6.9.

Let $k\in\mathbb{N}$. Then for every $n\geq\frac{km_{1}}{m_{1}-1}$ we have

$\displaystyle a_{M}(n-k,n)=s_{M^{\prime}}(n).$

###### Proof.

By Theorem 6.8 it is enough to show that the equality

$\displaystyle s_{M^{\prime}}(n)=\sum_{k/m_{1}\leq j\leq
k/(m_{1}-1)}a_{M^{\prime}}(m_{1}j-k,j)$

is true for every sequence $M$. We have

$\displaystyle S_{M^{\prime}}(x)=$ $\displaystyle\
F_{M^{\prime}}(1/x,x^{m_{1}})=\sum_{k=0}^{\infty}\left(\sum_{j=0}^{k}a_{M^{\prime}}(j,n)x^{-j}\right)x^{m_{1}k}$
$\displaystyle=$ $\displaystyle\
\sum_{k=0}^{\infty}\left(\sum_{m_{1}\beta-\alpha=k}a_{M^{\prime}}(\alpha,\beta)\right)x^{k}$
$\displaystyle=$ $\displaystyle\
\sum_{k=0}^{\infty}\left(\sum_{\beta=0}^{\infty}a_{M^{\prime}}(m_{1}\beta-k,\beta)\right)x^{k}$
$\displaystyle=$ $\displaystyle\
\sum_{k=0}^{\infty}\left(\sum_{k/m_{1}\leq\beta\leq
k/(m_{1}-1)}a_{M^{\prime}}(m_{1}\beta-k,\beta)\right)x^{k},$

because $a_{M^{\prime}}(m_{1}\beta-k,\beta)=0$ if $m_{1}\beta-k<0$ or
$m_{1}\beta-k>\beta$, that is, if $\beta<k/m_{1}$ or $\beta>k(m_{1}-1)$. The
proof is finished. ∎

## Acknowledgements

The author is very grateful to Maciej Ulas, Piotr Miska and Krystian Gajdzica
for helpful discussions and for many suggestions.

This paper was a part of the author’s PhD dissertation.

The research of the author was partially supported by the grant of the
National Science Centre (NCN), Poland, no. UMO-2019/34/E/ST1/00094.

## References

  * [1] G. Alkauskas, m–nariniai skaidiniai, DOI: 10.13140/RG.2.2.23219.12321.
  * [2] J.-P. Allouche, J. O. Shallit,Automatic Sequences: Theory Applications, Generalizations, Cambridge University Press, Cambridge, 2003.
  * [3] G. E. Andrews, E. Brietzke, Ø.J. Rødseth, J. A. Sellers, Arithmetic properties of $m$-ary partitions without gaps, Ann. Comb. 21(4) (2017), 495–506.
  * [4] G. E. Andrews, A. S. Fraenkel, J. A. Sellers, Characterizing the Number of $m$–ary Partitions Modulo $m$, Am. Math. Mon. 122(9) (2015), 880–885.
  * [5] G. E. Andrews, A. S. Fraenkel, J. A. Sellers, $m$–ary partitions with no gaps: A characterisation modulo $m$, Discrete Math. 339 (2016), 283–287.
  * [6] P. C. P. Bhatt, An interesting way to partition a number, Inform. Process. Lett. 71 (1999), 141–148.
  * [7] P. Cheung, V. Kac, Quantum calculus, New York: Springer, 2002.
  * [8] R. F. Churchhouse, Congruence properties of the binary partition function, Proc. Cambridge Philos. Soc. 66 (1969), 371–376.
  * [9] K. M. Courtright, J. A. Sellers, Arithmetic properties for hyper $m$-ary partition functions, Integers 4 (2004), A6.
  * [10] T. Edgar, The distribution of the number of parts of $m$-ary partitions modulo $m$, Rocky Mountain J. Math. 47(6) (2017), 1825–1838.
  * [11] A. Folsom, Y. Homma, J. H. Ryu, B. Tong, On a general class of non-squashing partitions, Discrete Math., 339(5) (2016), 1482–1506.
  * [12] W. Goh, P. Hitczenko, A. Shokoufandeh, $s$-partitions, Inform. process. lett. 82(6) (2002), 327–329.
  * [13] I. P. Goulden, P. Shuldiner, Characterizing the number of coloured m-ary partitions modulo m, with and without gaps, Discrete Math. 341(5) (2018), 1210–1214.
  * [14] R. E. Greene, S. G. Krantz, Function Theory of One Complex Variable: Third Edition, Graduate Studies in Mathematics, vol. 40, 2006.
  * [15] H. Gupta, On m-ary partitions, Math. Proc. Camb. Phil. Soc. 71 (1972), 343–345.
  * [16] Q. H. Hou, H. T. Jin, Y. P. Mu, L. Zhang, Congruences on the Number of Restricted m–ary Partitions, J. Number Theory 169 (2016), 79–85.
  * [17] Q. L. Lu, L. Ma, Congruences for Hyper m-ary Overpartition Functions, Integers 10.1 (2010), 1–11.
  * [18] Q. L. Lu, Z. K. Miao, Congruences for a Restricted $m$-ary Overpartition Function, J. Math. Research & Exposition (2010), 939–943.
  * [19] K. Mahler, On a special functional equation, J. Lond. Math. Soc. 15 (1940), 115–123.
  * [20] W. B. Pennington, On Mahler partition problem, Ann. of Math. 57 (1952), 531–546.
  * [21] Ø. J. Rødseth, Some arithmetical properties of m-ary partitions, Math. Proc. Camb. Phil. Soc. 68 (1970), 447–453.
  * [22] Ø. J. Rødseth, J. A. Sellers, On m-ary partition function congruences: a fresh look at a past problem, J. Number Theory 87 (2001), 270–281.
  * [23] M. Ulas, B. Żmija, On arithmetic properties of binary partition polynomials, Adv. Appl. Math. vol. 110 (2019), 153–179.
  * [24] M. Ulas, B. Żmija, On $p$-adic valuations of certain $m$ colored $p$-ary partition functions, Ramanujan J. 55(2) (2021), 623–660.
  * [25] B. Żmija, High order congruences for $M$-ary partitions, 9pp, to appear in: Periodica Mathematica Hungarica.
  * [26] B. Żmija, Recurrence sequences connected with the m–ary partition function and their divisibility properties, J. Number Theory 211 (2020), 322–370.


#  $p$-adic valuation of harmonic sums and their connections with Wolstenholme
primes

Leonardo Carofiglio, Luigi De Filpo, Alessandro Gambini

###### Abstract.

We explore a conjecture posed by Eswarathasan and Levine on the distribution
of $p$-adic valuations of harmonic numbers $H(n)=1+1/2+\cdots+1/n$ that states
that the set $J_{p}$ of the positive integers $n$ such that $p$ divides the
numerator of $H(n)$ is finite. We proved two results, using a modular-
arithmetic approach, one for non-Wolstenholme primes and the other for
Wolstenholme primes, on an anomalous asymptotic behaviour of the $p$-adic
valuation of $H(p^{m}n)$ when the $p$-adic valuation of $H(n)$ equals exactly
3.

###### Key words and phrases:

_Keywords_ : harmonic numbers; harmonic sums; Wolstenholme primes

##  1\. Introduction and general setting

The $n$-th harmonic number is defined as the partial sum of the well-known
harmonic series as follows:

$H(n):=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}.$

It has been known since the nineteenth century that by the Wolstenholme
Theorem [14], for any prime $p\geq 5$ the numerator of $H(p-1)$ is multiple of
$p^{2}$. Many researchers have investigated the arithmetic properties of
harmonic numbers and related problems; in the last century, Bleicher and Erdös
have studied the so-called harmonic subsums [2] while random harmonic sums and
harmonic series have been investigated in probabilistic terms (see, for
example, [1, 7, 12, 13]).

In 1991, Eswarathasan and Levine [6] introduced the set $J_{p}$ of the
positive integers $n$ whereby $H(n)$ is a multiple of $p$ and conjectured that
$J_{p}$ is finite for all primes $p$. Eswarathasan and Levine also introduced
an algorithm to count the elements of $J_{p}$ in the event that $J_{p}$ is
finite, which was improved by Boyd [3] in 1994. Boyd determined $J_{p}$ for
all $p\leq 547$, except 83, 127 and 397. It is easy to show that
$J_{2}=\emptyset$ and $J_{3}=\\{2,7,22\\}$, while for all $p\geq 5$,

$\\{p-1,\,p(p-1),\,p^{2}-1\\}\subseteq J_{p}.$

The primes for which $J_{p}$ contains only these three elements are called
“harmonic”: for instance $p=5$ is harmonic as $J_{5}=\\{4,20,24\\}$ (see [6]
for further details). The case $p=3$ was also treated individually in the
paper by Kamano [9].

Sanna [11] recently gave an upper bound for the number of elements of $J_{p}$
showing that

$\\#J_{p}(x)\leq 129p^{\frac{2}{3}}x^{0.765}$

where $J_{p}(x)=J_{p}\cap[1,x]$. This upper bound was improved by Chen and Wu
[15]:

$\\#J_{p}(x)\leq 3x^{\frac{2}{3}+\frac{1}{25\log p}}.$

They also tackled the alternating harmonic sum [16]. Recently Leonetti and
Sanna also studied the $p$-adic valuation of $H(n,k)$, for $n\geq k$, a kind
of generalized Harmonic numbers defined as:

$H(n,k):=\sum_{1\leq i_{1}<\cdots<i_{k}\leq n}\frac{1}{i_{1}\cdots i_{k}},$

which are closely linked to the Stirling numbers of the first kind.

An interesting connection between harmonic numbers and Bernoulli numbers was
discovered by Boyd [3, §4]. This connection concerns Wolstenholme primes that
are defined as the primes $p$ that divide the numerator of the Bernoulli
numbers $B_{p-3}$. The only two known Wolstenholme primes are 16843 and
2124679, but it is conjectured that infinitely many such primes exist. The
latest search for Wolstenholme primes in 2007 found that those were the only
two up to $10^{9}$ (see [10]). In this paper, we explored this connection by
identifying different behaviours of $J_{p}$ according to whether $p$ is or is
not a Wolstenholme prime.

We studied the $p$-adic valuation of the sequence of harmonic numbers
$H(p^{m}n)$ for fixed $(n,p)$ where $p\nmid n$, and we identified that it
follows one out of three patterns. These patterns differ according to whether
$p$ is a Wolstenholme prime or not. Interesting phenomena occur in pairs
$(n,p)$ such that $\nu_{p}(H(n))=3$, whose only known occurrences up to today
were $n=848,9338,10583,3546471722268916272$ for $p=11$, one $n\geq 10^{5}$ for
$p=83$, which were found by Boyd [3], $(n=16842,\,p=16843$) and
$(n=2124678,\,p=2124679)$, which are Wolstenholme primes and satisfy
$\nu_{16843}(H(16842))=3$ and $\nu_{2124678}(H(2124679))\geq 3$. Finally, Boyd
[3] conjectured that there are no pairs $(n,p)$ such that $\nu_{p}(H(n))\geq
4$.

##  2\. Results

In [3] and [6] the following Lemma has been proved:

###### Lemma 2.1.

For any prime $p\geq 5$, if $\nu_{p}(H(n))\leq 2$ then

$\nu_{p}(H(pn))=\nu_{p}(H(n))-1.$

Boyd [3] gives a stronger version of this lemma, which we have postponed to
Proposition 3.5. At this introductory stage, in fact, a weaker version is
sufficient to explains what we will call the “descent phenomenon” observed in
Table 1 of the $p$-adic valuations of harmonic numbers. Starting from that
point, we can see that the behaviour of harmonic numbers when
$\nu_{p}(H(n))\leq 2$ in terms of $p$-adic valuation is the following:
$\nu_{p}(H(p^{m}n))=\nu_{p}(H(n))-m$ for all $m\in\mathbb{N}$; here we give a
fragment for the table of $p=5$.

Table 1. Table for $p=5$: this shows the $5$-adic valuation of $H(5m+k)$,
where $m$ is the column index and $k$ is the row index. $\nu_{5}(H(5m+k))$
---
|  $k=0$ |  $k=1$ |  $k=2$ |  $k=3$ |  $k=4$
$m=0$ |  $\infty$ |  0 |  0 |  0 |  2
1 |  -1 |  -1 |  -1 |  -1 |  -1
2 |  -1 |  -1 |  -1 |  -1 |  -1
3 |  -1 |  -1 |  -1 |  -1 |  -1
4 |  1 |  0 |  0 |  0 |  1
5 |  -2 |  -2 |  -2 |  -2 |  -2
6 |  -2 |  -2 |  -2 |  -2 |  -2
$\vdots$ |  $\vdots$ |  $\vdots$ |  $\vdots$ |  $\vdots$ |  $\vdots$
19 |  -2 |  -2 |  -2 |  -2 |  -2
20 |  0 |  0 |  0 |  0 |  0
21 |  -1 |  -1 |  -1 |  -1 |  -1
22 |  -1 |  -1 |  -1 |  -1 |  -1
23 |  -1 |  -1 |  -1 |  -1 |  -1
24 |  0 |  0 |  0 |  0 |  0
25 |  -3 |  -3 |  -3 |  -3 |  -3
$\vdots$ |  $\vdots$ |  $\vdots$ |  $\vdots$ |  $\vdots$ |  $\vdots$
124 |  -1 |  -1 |  -1 |  -1 |  -1
125 |  -4 |  -4 |  -4 |  -4 |  -4
126 |  -4 |  -4 |  -4 |  -4 |  -4
$\vdots$ |  $\vdots$ |  $\vdots$ |  $\vdots$ |  $\vdots$ |  $\vdots$

However, Lemma 2.1 cannot be applied to the case $\nu_{p}(H(n))\geq 3$. We
provide formulas that can apply to this case as well.

###### Definition 2.2.

The Bernoulli numbers $B_{n}$ are defined using the generating function

$\frac{t}{1-e^{t}}=\sum\limits_{k=0}^{\infty}B_{k}\frac{t^{k}}{k!}.$

###### Definition 2.3.

A prime $p$ is a Wolstenholme prime if $p\mid B_{p-3}$.

###### Proposition 2.4.

$p$ is a Wolstenholme prime if and only if $p^{3}\mid H(p-1)$.

This result explains the fact that Wolstenholme primes give occurrences of
$\nu_{p}(H(n))=3$ for $n=p-1$ as in the introduction. It is important to
report this result (which comes from a paper submitted by Gardiner [8] in
1988), as it shows also other equivalent definitions of Wohstenholme primes,
that, however, we did not use in this article.

Below we present the main results of our research:

###### Theorem 2.5.

Let $p\geq 5$ be a non-Wolstenholme prime and $n\in\mathbb{N}$ such that
$p\nmid n$ and $\nu_{p}(H(n))\geq 3$. Then

  1. (1)

If $\nu_{p}(H(n))\geq 4$, then $\nu_{p}(H(pn))=2$ and then we perceive the
“descent phenomenon”,

  2. (2)

If $\nu_{p}(H(n))=3$ and there does not exists $m\in\mathbb{N}$ such that
$\nu_{p}(H(p^{m}n))\leq 2$, then $\nu_{p}(H(p^{m}n))=2m+3$ for all
$m\in\mathbb{N}$,

  3. (3)

If $\nu_{p}(H(n))=3$ and there exists $m\in\mathbb{N}$ such that
$\nu_{p}(H(p^{m}n))\leq 2$, then there exists $M\in\mathbb{N}$ such that
$\nu_{p}(H(p^{M}n))=0$ and

$\nu_{p}(H(p^{m}n))=\begin{cases}\begin{aligned} &2m+3&\quad\text{if
}m\leq\frac{M}{3}+1\\\ &M-m&\quad\text{if
}m>\frac{M}{3}+1\end{aligned}\end{cases}$

for all $m\in\mathbb{N}$.

###### Theorem 2.6.

Let $p\geq 5$ be a Wolstenholme prime, and $n\in\mathbb{N}$ such that $p\nmid
n$ and $\nu_{p}(H(n))\geq 3$. Then

  1. (1)

If $\nu_{p}(H(n))=3$, then $\nu_{p}(H(pn))=2$ and then we perceive the
“descent phenomenon”,

  2. (2)

If $\nu_{p}(H(n))\geq 4$ and there does not exists $m\in\mathbb{N}$ such that
$\nu_{p}(H(p^{m}n))\leq 3$, then $\nu_{p}(H(p^{m}n))\geq 2m+4$ for all
$m\in\mathbb{N}$,

  3. (3)

If $\nu_{p}(H(n))\geq 4$ and there exists $m\in\mathbb{N}$ such that
$\nu_{p}(H(p^{m}n))\leq 3$, then there exists $M\in\mathbb{N}$ such that
$\nu_{p}(H(p^{M}n))=0$ and

$\begin{cases}\begin{aligned} &\nu_{p}(H(p^{m}n))\geq 2m+4&\quad\text{if
}m\leq\frac{M+1}{3}+1\\\ &\nu_{p}(H(p^{m}n))=M-m&\quad\text{if
}m>\frac{M+1}{3}+1\end{aligned}\end{cases}$

for all $m\in\mathbb{N}$.

##  3\. Setting the problem

In this section we will use the Big-O notation,

$\nu_{p}(x-y)\geq k\quad\Longleftrightarrow\quad x-y=O(p^{k}).$

###### Proposition 3.1.

Let $a,b\in\mathbb{Z}$, $(b,p)=1$. Then

$\frac{a}{b}=\frac{a}{b+hp}+O(p)$

for all $h\in\mathbb{Z}$.

###### Proof.

We have

$\nu_{p}\left(\frac{a}{b}-\frac{a}{b+hp}\right)=\nu_{p}\left(\frac{ahp}{b(b+hp)}\right)\geq
1,$

∎

###### Proposition 3.2.

Let $q\in\mathbb{Q}$. Then $\nu_{p}(q)=k<1$ if and only if there exist
$a,b\in\mathbb{Z}$, $b\neq 0$ with $(a,p)=1$ and $(b,p)=1$ such that

$q=p^{k}\frac{a}{b}+O(p).$

###### Proof.

  * ($\Longrightarrow$)

Straightforward.

  * ($\Longleftarrow$)

We have

$\nu_{p}\left(q-p^{k}\frac{a}{b}\right)\geq 1,$

then

$\nu_{p}(q)=\min\left\\{\nu_{p}\left(p^{k}\frac{a}{b}\right),\nu_{p}\left(q-p^{k}\frac{a}{b}\right)\right\\}=k.$

∎

Now, in order to study the behaviour of $J(p)$, we must consider a very
important property:

###### Lemma 3.3.

If $n\in J(p)$, $\nu_{p}(H(pn))\geq 0$, we have

$H(pn+k)=\frac{H(n)}{p}+H(k)+O(p)$

for each $k=1,\dotsc p-1$.

###### Proof.

Using Lemma 2.1 and Proposition 3.1 we get

$H(pn+k)=H(pn)+\sum\limits_{i=1}^{k}\frac{1}{pn+i}=\frac{H(n)}{p}+\sum\limits_{i=1}^{k}\frac{1}{i}+O(p)=\frac{H(n)}{p}+H(k)+O(p),$

∎

From Lemma 3.3 follows immediately the following:

###### Corollary 3.4.

If $\nu_{p}(H(pn))\geq 1$, $H(pn+k)=H(k)+O(p)$.

It means that the set of indices $k=1,\dotsc p-1$ such that
$\nu_{p}(H(pn+k))=0$ coincides with the set of indices $k=1,\dotsc p-1$ as
before such that $\nu_{p}(H(k))=0$. This explains the repetition with the same
patterns of zeros observed in Table 1, however we cannot yet predict the
actual $p$-adic valuation, only whether it is null or not. If, on the other
hand, $\nu_{p}(H(pn))=0$, then given that

$H(pn+k)=\frac{H(n)}{p}+H(k)$

for each $k=1,\dotsc p-1$, the study of these $k$ with $H(pn+k)=0$ is reduced
to the study of the $p$-adic valuation in modulus $p$ of the initial terms of
a shifted sum. We now focus on harmonic numbers of the type $H(p^{m}n)$.

###  3.1. Formulas for $H(p^{m}n)$

We recall a stronger version of Lemma 2.1:

###### Proposition 3.5 (see [3], Lemma 3.1).

If $p\geq 5$ is prime and $n\geq 1$, we have

$H(pn)=\frac{H(n)}{p}+O(p^{2}).$

We could conclude that, if $\nu_{p}(H(n))\leq 2$, then

$\nu_{p}(H(pn))=\nu_{p}(H(n))-1.$

###### Lemma 3.6.

If $p\geq 5$ is prime and $n\geq 1$, we have

$H(p^{2}n)=\frac{H(n)}{p^{2}}+O(p),$

###### Proof.

Proposition 3.5 implies that there exists $\alpha\in\mathbb{Q}$ with
$\nu_{p}(\alpha)\geq 0$ such that

$H(pn)=\frac{H(n)}{p}+O(p^{2}),$

then

$H(p^{2}n)=\frac{H(pn)}{p}+O(p)=\frac{H(n)}{p^{2}}+O(p).$

∎

###### Lemma 3.7.

Let $a,b\in\mathbb{Z}$, then $(b,p)=1$ and $k\geq 0$ an integer. Then

$\frac{a}{p^{k}b}=\frac{ab^{-1}}{p^{k}}+O(p),$

where $b^{-1}$ denotes the inverse of $b$ modulo $p^{k+1}$.

###### Proof.

We have

$\nu_{p}\left(\frac{a}{p^{k}b}-\frac{ab^{-1}}{p^{k}}\right)=\nu_{p}\left(\frac{a(1-bb^{-1})}{p^{k}b}\right)\geq
1.$

∎

###### Lemma 3.8.

If $a,b\in\mathbb{Z}$ and $a=b+O(p^{k+1})$,

$\frac{a}{p^{k}}=\frac{b}{p^{k}}+O(p).$

###### Proof.

We have

$\nu_{p}\left(\frac{a}{p^{k}}-\frac{b}{p^{k}}\right)=\nu_{p}\left(\frac{a-b}{p^{k}}\right)=\nu_{p}(a-b)-k\geq
1.$

∎

We now recall the famous Clausen-Van Staudt Theorem:

###### Theorem 3.9 (Clausen-Van Staudt).

Let $n\in\mathbb{N}$ and $B_{i}$ be the $i$-th Bernoulli number, then

$B_{2n}+\\!\\!\sum\limits_{\begin{subarray}{c}{p\;\mathrm{prime}}\\\
{(p-1)\mid 2n}\end{subarray}}\frac{1}{p}$

is an integer.

See [4] for a proof of the theorem.

###### Corollary 3.10.

Let $n\in\mathbb{N}$ and $B_{i}$ be the $i$-th Bernoulli number, then

  * i)

$\nu_{p}(B_{2n})\geq-1,$

  * ii)

$\nu_{p}(B_{2n})=-1\quad\iff\quad p-1\mid 2n.$

The previous Propositions and Lemmas are used to investigate $H(p^{m}n)$ more
in detail:

###### Theorem 3.11.

Let $n,m$ be non-negative integers and $p\geq 5$ be a prime number, then the
following formula holds

$H(p^{m}n)=\frac{H(n)}{p^{m}}+\sum\limits_{h=2}^{m-1}\sum\limits_{k=1}^{h}\frac{B_{p^{h}(p-1)-2k}}{2kp^{h}}\binom{p^{h}(p-1)-1}{2k-1}p^{2k(m-h)}n^{2k}+O(p),$
(1)

where $B_{i}$ is the $i$-th Bernoulli number.

###### Proof.

In order to prove the statement:

Let us define

$a_{m}(n):=\sum\limits_{h=2}^{m-1}\sum\limits_{k=1}^{h}\frac{B_{p^{h}(p-1)-2k}}{2kp^{h}}\binom{p^{h}(p-1)-1}{2k-1}p^{2k(m-h)}n^{2k}.$

Hence the statement becomes:

$H(p^{m}n)=\dfrac{H(n)}{p^{m}}+a_{m}(n)+O(p).$

The proof follows by induction on $m$: our aim is to find functions
$\chi_{m}(n)$ such that the following congruences hold:

$H(p^{m+1}n)=\dfrac{H(pn)}{p^{m}}+a_{m}(n)+O(p)=\dfrac{H(n)}{p^{m+1}}+\chi_{m}(n)+a_{m}(n)+O(p)=\dfrac{H(n)}{p^{m+1}}+a_{m+1}(n)+O(p).$

  * Step 1.

Find $\chi_{m}(n)$ such that

$\dfrac{H(pn)}{p^{m}}=\dfrac{H(n)}{p^{m+1}}+\chi_{m}(n)+O(p).$

  * Step 2.

Prove that, for the $\chi_{m}(n)$ already found, it holds

$\chi_{m}(pn)+a_{m}(n)=a_{m+1}(n)+O(p).$

Proof of step 1. By Proposition 3.5 and noting that

$\displaystyle
H(pn)=\sum\limits_{k=1}^{n}\frac{1}{pk}+\sum\limits_{\ell=0}^{n-1}\sum\limits_{k=1}^{p-1}\frac{1}{\ell
p+k},$

we obtain

$\displaystyle\dfrac{H(pn)}{p^{m}}$
$\displaystyle=\dfrac{1}{p^{m}}\left(\sum\limits_{k=1}^{n}\frac{1}{pk}+\sum\limits_{\ell=0}^{n-1}\sum\limits_{k=1}^{p-1}\frac{1}{\ell
p+k}\right)+O(p)$
$\displaystyle=\dfrac{1}{p^{m}}\left(\dfrac{H(n)}{p}+\sum\limits_{\ell=0}^{n-1}\sum\limits_{k=1}^{p-1}\frac{1}{\ell
p+k}\right)+O(p)$
$\displaystyle=\dfrac{H(n)}{p^{m+1}}+\dfrac{1}{p^{m}}\sum\limits_{\ell=0}^{n-1}\sum\limits_{k=1}^{p-1}\frac{1}{\ell
p+k}+O(p).$

Hence, we found

$\chi_{m}(n)=\dfrac{1}{p^{m}}\sum\limits_{\ell=0}^{n-1}\sum\limits_{k=1}^{p-1}\frac{1}{\ell
p+k}.$

We focus on the inner sum of the RHS:

$\displaystyle\frac{1}{p^{m}}\sum_{k=1}^{p-1}\frac{1}{\ell p+k}$
$\displaystyle=\frac{1}{p^{m}}\sum_{k=1}^{p-1}(\ell p+k)^{p^{m}(p-1)-1}+O(p)$
$\displaystyle=\frac{1}{p^{m}}\left(\sum_{k=1}^{\ell
p+p-1}k^{p^{m}(p-1)-1}-\sum_{k=1}^{\ell p}k^{p^{m}(p-1)-1}\right)+O(p)$
$\displaystyle=\frac{1}{p^{m}}\left(\sum_{k=1}^{(\ell+1)p}k^{p^{m}(p-1)-1}-\sum_{k=1}^{\ell
p}k^{p^{m}(p-1)-1}\right)+O(p).$ (2)

We have taken advantage of the fact that, if $y$ has an inverse modulo $n$,
$y^{-1}\equiv y^{\varphi(n)-1}\text{(mod }n\text{)}$ by Euler’s Theorem, where
$\varphi$ denotes Euler’s totient function. This explains the choice of the
exponent $p^{m}(p-1)=\varphi(p^{m+1})$.

Now the recurring expression

$\frac{1}{p^{m}}\sum_{k=1}^{\ell p}k^{p^{m}(p-1)-1}$

can be simplified using Bernoulli’s formula for sums of powers (Faulhaber’s
formula, see [5, §4] pag. 106):

$\displaystyle\frac{1}{p^{m}}\sum\limits_{\begin{subarray}{c}k=1\end{subarray}}^{\ell
p}k^{p^{m}(p-1)-1}=\frac{1}{p^{2m}(p-1)}\\!\\!\\!\\!\\!\\!\\!\\!\sum_{k=0}^{p^{m}(p-1)-1}\\!\\!\\!\\!\\!\\!\\!(-1)^{k}B_{k}\binom{p^{m}(p-1)}{k}(\ell
p)^{p^{m}(p-1)-k}.$ (3)

In terms of congruence modulo $p$, the terms with $0\leq k<p^{m}(p-1)-2m$
vanish since they have positive $p$-adic valuation: by Corollary 3.10 we find
that $\nu_{p}(B_{k})\geq-1$. Moreover, the $p$-adic valuation of a binomial
coefficient is non-negative and by removing $B_{1}$ we do not need the factor
$(-1)^{k}$ because $B_{k}=0$ for all $k\geq 3$ odd. Then, the RHS of (3) is
equal to

$\frac{1}{p^{2m}(p-1)}\sum_{k=1}^{2m}B_{p^{m}(p-1)-k}\binom{p^{m}(p-1)}{k}(\ell
p)^{k}.$

Resuming from (3.1), we arrive at

$\displaystyle\frac{1}{p^{m}}\sum_{k=1}^{p-1}\frac{1}{\ell p+k}$
$\displaystyle=\frac{1}{p^{m}}\left(\sum\limits_{\begin{subarray}{c}k=1\end{subarray}}^{(\ell+1)p}k^{p^{m}(p-1)-1}-\sum\limits_{\begin{subarray}{c}k=1\end{subarray}}^{\ell
p}k^{p^{m}(p-1)-1}\right)+O(p)$
$\displaystyle=\frac{1}{p^{2m}(p-1)}\sum_{k=1}^{2m}B_{p^{m}(p-1)-k}\binom{p^{m}(p-1)}{k}\left(\left((\ell+1)p\right)^{k}-(\ell
p)^{k}\right)+O(p).$

Now we have a candidate $\chi_{m}(n)$, and by rearranging terms, developing
the telescopic sum and highlighting again that $B_{k}=0$ for all $k\geq 3$
odd, we arrive at the following

$\displaystyle\chi_{m}(n)$
$\displaystyle=\frac{1}{p^{2m}(p-1)}\sum_{\ell=0}^{n-1}\sum_{k=1}^{2m}B_{p^{m}(p-1)-k}\binom{p^{m}(p-1)}{k}\left(\left((\ell+1)p\right)^{k}-(\ell
p)^{k}\right)+O(p)$
$\displaystyle=\frac{1}{p^{2m}(p-1)}\sum_{k=1}^{2m}B_{p^{m}(p-1)-k}\binom{p^{m}(p-1)}{k}(np)^{k}+O(p)$
$\displaystyle=\frac{1}{p^{m}}\sum_{k=1}^{2m}\frac{B_{p^{m}(p-1)-k}}{k}\binom{p^{m}(p-1)-1}{k-1}(np)^{k}+O(p)$
$\displaystyle=\sum_{k=1}^{m}\frac{B_{p^{m}(p-1)-2k}}{2kp^{m}}\binom{p^{m}(p-1)-1}{2k-1}(np)^{2k}+O(p).$

Proof of step 2. In order to conclude the global proof we need to show that it
holds

$a_{m+1}(n)=\chi_{m}(pn)+a_{m}(n)+O(p),$

The identity is true for $m=3$ and, given the inductive hypothesis, the
identity is trivial since $\chi_{m}(n)$ just found is exactly the $m$-th term
of the sum of $a_{m}(n)$. ∎

##  4\. Proof of Theorem 2.5 and 2.6

We recall here this famous result from Kummer:

###### Theorem 4.1 (Kummer’s Congruence).

If $a,b\in\mathbb{N}$ are even, not divisible by $p-1$ and $a=b+O(p-1)$, then

$\frac{B_{a}}{a}=\frac{B_{b}}{b}+O(p).$

Now we are able to prove Theorem 2.5.

###  4.1. Proof of Theorem 2.5

###### Proof of Theorem 2.5.

  1. (1)

If we prove that $H(p^{3}n)=O(p)$ it follows from Lemma 3.6 that
$\frac{H(pn)}{p^{2}}=O(p)$ and this means that $\nu_{p}(H(pn))\geq 2$. We
consider then Theorem 3.11 for $m=3$:

$H(p^{3}n)=\frac{H(n)}{p^{3}}-B_{p^{2}(p-1)-2}\frac{n^{2}}{2}+O(p)=\frac{H(n)}{p^{3}}-\frac{B_{p-3}}{3}n^{2}+O(p)=-\frac{B_{p-3}}{3}n^{2}+O(p),$

as by hypothesis, $\nu_{p}(H(n))\geq 4$. The RHS has valuation zero if $p$ is
non-Wolstenholme: in fact, using Theorem 4.1 to justify the Bernoulli number
congruence,

$-\frac{B_{p^{2}(p-1)-2}}{2}=\frac{B_{p^{2}(p-1)-2}}{p^{2}(p-1)-2}+O(p)=\frac{B_{p-3}}{p-3}+O(p)=-\frac{B_{p-3}}{3}+O(p).$

  2. (2)

By hypothesis, for all $m\in\mathbb{N}$, $H(p^{m}n)=O(p)$, we then evaluate
formula (1) in $p^{j}n$: $\forall j\in\mathbb{N}$, where $p\nmid n$,

$\displaystyle H(p^{m+j}n)$ $\displaystyle=O(p)\quad\mbox{and}$ $\displaystyle
H(p^{m+j}n)$
$\displaystyle=\frac{H(p^{j}n)}{p^{m}}+\sum\limits_{h=2}^{m-1}\sum\limits_{k=1}^{h}\frac{B_{p^{h}(p-1)-2k}}{2kp^{h}}\binom{p^{h}(p-1)-1}{2k-1}p^{2k(m-h+j)}n^{2k}+O(p).$

We now aim to prove that the term with the lowest $p$-adic valuation in the
sum is obtained for $h=m-1,k=1$. This term has valuation

$\displaystyle v_{\min}=$
$\displaystyle\nu_{p}\left(\frac{B_{p^{m-1}(p-1)-2}}{2p^{m-1}}\binom{p^{m-1}(p-1)-1}{1}p^{2(j+1)}n^{2}\right)=$
$\displaystyle=\nu_{p}\left(B_{p^{m-1}(p-1)-2}\right)+2j+3-m=$
$\displaystyle=\nu_{p}\left(B_{p-3}\right)+2j+3-m=2j+3-m.$

Once again we used Theorem 4.1 and Proposition 3.2 to justify the Bernoulli
number congruence

$-\frac{B_{p^{m-1}(p-1)-2}}{2}=\frac{B_{p^{m-1}(p-1)-2}}{p^{m-1}(p-1)-2}+O(p)=\frac{B_{p-3}}{p-3}+O(p)=-\frac{B_{p-3}}{3}+O(p),$

from which follows the equivalence of valuations if $p$ is non-Wolstenholme.
Now we discuss the $p$-adic valuation term by term in the sum. Each summand
may be represented as a pair $(h,k)$ as coordinates in the two sums formula
with $2\leq h\leq m-1$ and $1\leq k\leq h$. Therefore each term falls into one
of these three groups:

     * $i)$

The term corresponding to $(h,k)=(m-1,1)$, discussed above,

     * $ii)$

Terms of the forms $(h,k)$ such that $(p-1)\mid 2k$ (except the summand in the
$(i)$ group),

     * $iii)$

The remaining terms.

For the general summand in (1) we have:

$\displaystyle\nu_{p}$
$\displaystyle\left(\frac{B_{p^{h}(p-1)-2k}}{2kp^{h}}\binom{p^{h}(p-1)-1}{2k-1}p^{2k(m-h+j)}n^{2k}\right)=$
$\displaystyle=\nu_{p}\left(B_{p^{h}(p-1)-2k}\right)+\nu_{p}\binom{p^{h}(p-1)-1}{2k-1}+2k(m-h+j)-h-\nu_{p}(k)$
$\displaystyle\geq\nu_{p}\left(B_{p^{h}(p-1)-2k}\right)+2k(m-h+j)-h-\nu_{p}(k)$
$\displaystyle\geq\nu_{p}\left(B_{p^{h}(p-1)-2k}\right)+2k(m-h+j)-h+(k-\nu_{p}(k)-1)-k+1$
$\displaystyle\geq\nu_{p}\left(B_{p^{h}(p-1)-2k}\right)+2k(m-h+j)-h-k+1$
$\displaystyle\geq\nu_{p}\left(B_{p^{h}(p-1)-2k}\right)+2k\Big{(}m-h+j-\frac{1}{2}\Big{)}-h+1,$
(4)

as $k>1+\nu_{p}(k)$ for $p\geq 5$, and $k\geq 2$. Now, we use Corollary 3.10:
$\nu_{p}\left(B_{p^{h}(p-1)-2k}\right)\geq-1$ and
$\nu_{p}\left(B_{p^{h}(p-1)-2k}\right)=-1$ if and only if $(p-1)\mid 2k$.

If the terms belong to group ($ii$), $(p-1)\mid 2k$, then (2) is greater than

$\displaystyle 2k\Big{(}m-h+j-\frac{1}{2}\Big{)}-h$ $\displaystyle\geq$
$\displaystyle(p-1)(m-h+j-\frac{1}{2})-m+1$ $\displaystyle\geq$
$\displaystyle(p-1)(1+j-\frac{1}{2})-m+1>v_{\min}.$

Otherwise, if the terms belong to group ($iii$), the inequality $h<m-1$ is
strict, bearing in mind that for group $(iii)$ we have $(h,k)\neq(m-1,1)$ and
$k\geq 2$. Then (2) is greater than

$\displaystyle 2k\Big{(}m-h+j-\frac{1}{2}\Big{)}-h+1$ $\displaystyle>$
$\displaystyle 2k\Big{(}\frac{1}{2}+j\Big{)}-m+2$ $\displaystyle>$
$\displaystyle 2(1+j)-m+1$ $\displaystyle=$ $\displaystyle 2j+3-m=v_{\min}.$

Therefore we find that the sum has valuation $v_{\min}$, which is negative for
sufficiently large $m$, thus

$\nu_{p}\left(H(p^{j}n)\right)-m=\nu_{p}\left(\frac{H(p^{j}n)}{p^{m}}\right)=v_{\min}=2j+3-m,$

that means

$\nu_{p}\left(H(p^{j}n)\right)=2j+3.$

  3. (3)

If instead there exists $m\in\mathbb{N}$ such that $\nu_{p}(H(p^{m}n))\leq 2$,
then by the descent phenomenon there exists $M\\!\in\mathbb{N}$ such that
$\nu_{p}(H(p^{M}n))=0$. Then again evaluating formula (1) in
$H(p^{M}\,p^{j}n)$ with $m=M$ in $p^{j}n$, where $p\nmid n$, we have

$H(p^{M}\,p^{j}n)=\frac{H(p^{j}n)}{p^{M}}+\sum\limits_{h=2}^{M-1}\sum\limits_{k=1}^{h}\frac{B_{p^{h}(p-1)-2k}}{2kp^{h}}\binom{p^{h}(p-1)-1}{2k-1}p^{2k(M-h+j)}n^{2k}+O(p),$

where the LHS has valuation $-j$, and by the same reasoning as in case $(2)$
the RHS is a sum of two terms of valuation respectively $\nu_{p}(H(p^{j}n))-M$
and $2j+3-M$. Now surely both valuation cannot exceed $-j$, since then the LHS
and RHS would then have different valuations. Thus, we have the following
cases:

     * •

If $3j+3>M$, then $\nu_{p}(H(p^{j}n))=M-j$.

     * •

If $\nu_{p}(H(p^{j}n))>M-j$, then $3j+3=M$.

     * •

If $3j+3\leq M$ and $\nu_{p}(H(p^{j}n))\leq M-j$, then
$\nu_{p}(H(p^{j}n))=2j+3$.

Therefore, by rearranging the results, we conclude the proof.

∎

###  4.2. Proof of Theorem 2.6

Using the same arguments we can prove the analogous theorem for Wolstenholme
primes.

###### Proof of Theorem 2.6.

  1. (1)

Again, using the same reasoning as in the previous Theorem, we evaluate
formula (1) in $m=3$:

$H(p^{3}n)=\frac{H(n)}{p^{3}}-B_{p^{2}(p-1)-2}\frac{n^{2}}{2}+O(p)=\frac{H(n)}{p^{3}}+\frac{B_{p-3}}{3}n^{2}+O(p)=\frac{H(n)}{p^{3}}+O(p),$

where the RHS has valuation zero. We note that this fact proves the descent
phenomenon in the case $m=3$ for Wolstenholme primes.

  2. (2)

As before, we evaluate formula (1) in $p^{j}n$, where $p\nmid n$:

$\displaystyle H(p^{m+j}n)$ $\displaystyle=O(p)\quad\mbox{and}$ $\displaystyle
H(p^{m+j}n)$
$\displaystyle=\frac{H(p^{j}n)}{p^{m}}+\sum\limits_{h=2}^{m-1}\sum\limits_{k=1}^{h}\frac{B_{p^{h}(p-1)-2k}}{2kp^{h}}\binom{p^{h}(p-1)-1}{2k-1}p^{2k(m-h+j)}n^{2k}+O(p).$

Differently from the proof of Theorem 2.5 the minimum valuation term in the
sum is not known, but the lowest valuation of each summand is $v_{\min}\geq
2j+4-m$ according to the same argument used in the previous proof. Thus, since
the LHS has positive valuation, we have

$\nu_{p}\left(\dfrac{H(p^{j}n)}{p^{m}}\right)\geq 2j+4-m,$

otherwise, thanks to ultrametric inequality, we would have

$\nu_{p}\left(H(p^{m}\,p^{j}n)\right)=2j+4-m$

that contradicts the hypothesis for sufficiently large $m$.

If, instead, there exists $m\in\mathbb{N}$ such that $\nu_{p}(H(p^{m}n))\leq
3$ then by descendent phenomenon there exists $M\in\mathbb{N}$ such that
$\nu_{p}(H(p^{M}n))=0$. Therefore, we have:

$\nu_{p}(H(p^{M+j}n))=-j.$

Then again, evaluating formula (1) for $m=M$ in $p^{j}n$, where $p\nmid n$, we
have the following congruence:

$\displaystyle H(p^{M}\,p^{j}n)=$
$\displaystyle\frac{H(p^{j}n)}{p^{M}}+\sum\limits_{h=2}^{M-1}\sum\limits_{k=1}^{h}\frac{B_{p^{h}(p-1)-2k}}{2kp^{h}}\binom{p^{h}(p-1)-1}{2k-1}p^{2k(M-h+j)}n^{2k}+O(p)$
$\displaystyle=$ $\displaystyle\dfrac{\Delta}{p^{M}}+\Sigma,$

say. In this formula the $p$-adic valuation of the three terms are:

     * $\bullet$

$\nu_{p}(H(p^{M}\,p^{j}n))=-j$,

     * $\bullet$

$\nu_{p}\left(\dfrac{\Delta}{p^{M}}\right)=\nu_{p}(\Delta)-M$,

     * $\bullet$

$\nu_{p}(\Sigma)\geq 2j+4-M$.

In order to complete the proof, we will use the $p$-adic valuation inequality
to find a bound for $\nu_{p}(\Delta)$. However, in contrast to the situation
in Theorem 2.5 case (3), there is not the exact valuation of
$\nu_{p}(\Sigma)$. Hence, the possibilities are:

$\displaystyle i)$ $\displaystyle\quad\nu_{p}(\Delta)-M=-j$
$\displaystyle\nu_{p}(\Sigma)>-j$ $\displaystyle ii)$
$\displaystyle\quad\nu_{p}(\Delta)-M>-j$ $\displaystyle\nu_{p}(\Sigma)=-j$
$\displaystyle iii)$
$\displaystyle\quad\nu_{p}(\Delta)-M=\nu_{p}(\Sigma)\leq-j$

We combine these results with the inequality for $\nu_{p}(\Sigma)$ in order to
estimate $\nu_{p}(\Delta)$. It is important to notice that the condition
$\nu_{p}(\Sigma)>-j$ does not provide information combined with the other
inequality concerning $\nu_{p}(\Sigma)$.

$\displaystyle i.a)$ $\displaystyle\quad\nu_{p}(\Delta)=M-j<2j+4$ if
$\displaystyle M<3j+4\text{ and $(i)$ holds,}$ $\displaystyle i.b)$
$\displaystyle\quad\nu_{p}(\Delta)=M-j\geq 2j+4$ if $\displaystyle M\geq
3j+4\text{ and $(i)$ holds,}$ $\displaystyle ii)$
$\displaystyle\quad\nu_{p}(\Delta)>M-j>2j+4$ if $\displaystyle M\geq
3j+4\text{ and $(ii)$ holds,}$ $\displaystyle iii)$
$\displaystyle\quad\nu_{p}(\Delta)=\nu_{p}(\Sigma)+M\geq 2j+4$ if
$\displaystyle M\geq 3j+4\text{ and $(iii)$ holds.}$

This yields the desired result.

∎

##  5\. Conclusions and further developments

We highlight the fact that the existences of pairs $(n,p)$ satisfying case
$(2)$ in Theorems 2.5 or 2.6 would disprove the conjecture of Eswarathasan and
Levine on the finiteness of $J_{p}$: to achieve this outcome in formula (1)
the sum should somehow vanish in valuation. We also point out that alas the
refutation of case $(2)$ unfortunately does not imply Eswarathasan and
Levine’s conjecture, or even Boyd’s conjecture on the impossibility of
$\nu_{p}(H(n))\geq 4$, which would require the cases $(1),(2)$ to be false,
and $M=3$ in case $(3)$.

One possible way to use the results achived could be that one undertaken by
Sanna [11] to “count” the number of elements of $J_{p}$ with $p$-adic
valuation greater than 1. One could try to count the number of elements with
$p$-adic valuation greater or equal to a positive integer $k$ in order to
refute case 2 of Theorem 2.5. The problem in this case is that Sanna’s Lemma
2.2 on short intervals works when looking for elements that cancel the
derivative in a field $\mathbb{Z}_{p}$ ($f^{\prime}_{d}\equiv 0\ \mod p$). As
this case concerns a ring $\mathbb{Z}_{p^{k}}$ the number of roots of a
polynomial cannot be bounded, in general, by $p$. Bounding it by
$(d-1)p^{k-1}$ leads to overestimating the roots and then to a choice of $z$
that is inadequate for our purpose.

According to the same arguments used in this paper it does not appear too
difficult to extend Theorems 2.5\- 2.6 for the generalized harmonic sum

$H_{\alpha}(n):=\sum\limits_{k=1}^{n}\frac{1}{k^{\alpha}}$

in the case $(p-1)\nmid\alpha$, the only difference being that the descent
phenomenon lowers the valuation by $\alpha$.

##  6\. Acknowledgments

This research is the result of a collaborative initiative among students of
the three-year degree programme in Mathematics who have actively participated
in the paths of excellence promoted by the Department of Mathematics “Guido
Castelnuovo” of Sapienza University of Rome.

We would also like to thank Domenico Marino, Daniele Saracino and Francesco
Vertucci for their fruitful suggestions that improved our paper.

We finally would like to thank the anonymous referees for their helpful
comments and suggestions.

## References

  * [1] S. Bettin, G. Molteni, C. Sanna, _Small values of signed harmonic sums_ , C. R. Math. Acad. Sci. Paris 356, no. 11-12 (2018), 1062–1074.
  * [2] M. N. Bleicher, P. Erdős, _The number of distinct subsums of $\sum_{1}^{N}1/i$_, Math. Comp. 29, (1975) 29–42.
  * [3] D. W. Boyd, _A $p$-adic study of the partial sums of the harmonic series,_ Experiment. Math. 3, no. 4 (1994), 287–302.
  * [4] L. Carlitz, _Bernoulli numbers_. Fib. Quart, 6(1) (1968), 968.
  * [5] J. H. Conway, R. K. Guy, _The Book of Numbers._ New York: Springer-Verlag, 1996.
  * [6] A. Eswarathasan, E. Levine, _$p$ -Integral harmonic sums_, Discrete mathematics, 91(3) (1991), 249–257.
  * [7] A. Gambini, R. Tonon, and A. Zaccagnini, _Signed harmonic sums of integers with $k$ distinct prime factor_, Rendiconti Sem. Mat. Univ. Pol. Torino, 78(1) (2020), 125–141.
  * [8] A. Gardiner, _Four problems on prime power divisibility._ The American Mathematical Monthly, 95(10) (1988), 926–931.
  * [9] K. Kamano, _On 3-adic valuations of generalized harmonic numbers_ , Integers no. 11 (2002).
  * [10] R. McIntosh, E. Roettger, _A search for Fibonacci-Wieferich and Wolstenholme primes_ , Mathematics of Computation, 76(260) (2007), 2087–2094.
  * [11] C. Sanna, _On the $p$-adic valuation of harmonic numbers._ Journal of Number Theory 166 (2016), 41–46.
  * [12] B. Schmuland, _Random harmonic series_ , Amer. Math. Monthly 110, no. 5 (2003), 407–416.
  * [13] R. T. Worley, _Signed sums of reciprocals. I_ , J. Austral. Math. Soc. Ser. A 21, no. 4 (1976), 410–413.
  * [14] J. Wolstenholme, _On certain properties of prime numbers_. QJ Math., 5 (1862), 35–39.
  * [15] B. L. Wu, Y. G. Chen, _On certain properties of harmonic numbers_ Journal of Number Theory 175 (2017), 66–86.
  * [16] B. L. Wu, Y. G. Chen, _On the denominators of harmonic numbers, II._ Journal of Number Theory 200 (2019), 397–406.