On p-adic valuations of colored p-ary partitions

Let \(\mathbb {N}\) denotes the set of nonnegative integers and \(\mathbb {P}\) be the set of prime numbers. Let \(m\in \mathbb {N}_{\ge 2}\) and consider the sequence \((a_{m}(n))_{n\in \mathbb {N}}\) defined by the power series expansion of the infinite product

From the general theory of partitions (see the first chapter in the book of Andrews [3]) we know that the sequence \((a_{m}(n))_{n\in \mathbb {N}}\) has a natural combinatorial interpretation. Indeed, we have \(a_{m}(0)=1\) and for \(n\in \mathbb {N}_{+}\), the number \(a_{m}(n)\) counts the number of so called m-ary representations of a non-negative integer n, i.e., representations of the form

where \(u\in \mathbb {N}\) and \(\varepsilon _i\in \mathbb {N}\) for \(i\in \{0,\ldots ,u\}\). Let us note that the m-ary representation is generalization of the (unique) representation of the integer n in the base m, i.e., the representation (1) with \(\varepsilon _{i}\in \{0,\ldots ,m-1\}\).

In the sequel we will need a notion of the p-adic valuation of an integer, where \(p\in \mathbb {P}\). The p-adic valuation of an integer n, denoted by \(\nu _{p}(n)\), is just the highest power of p dividing n, i.e., \(\nu _{p}(n):={\text {max}}\{k\in \mathbb {N}:\;p^{k}\mid n\}\). We also make standard convention that \(\nu _{p}(0)=+\infty \).

There are many papers devoted to the study of arithmetic properties of the sequence counting m-ary partitions. The case of \(m=2\) was investigated by Euler. However, it seems that the first non-trivial result concerning this case was proved by Churchhouse [5]. He proved that the sequence of the 2-adic valuations of \((b(n))_{n\in \mathbb {N}}\) is bounded by 2. More precisely, we have \(b(0)=1, b(1)=1\) and if \(n\ge 2\), we have \(\nu _{2}(b(n))=2\) if and only if n or \(n-1\) can be written in the form \(4^r(2u+1)\) for some \(r\in \mathbb {N}_{+}\) and \(u\in \mathbb {N}\). In the remaining cases the value of \(\nu _{2}(b(n))\) is equal to 1. Churchhouse also stated some conjectures concerning the 2-adic behaviour of the difference \(a_{2}(4n)-a_{2}(n)\). These conjectures were independently proved by Rødseth [11] and Gupta [7] (see also the presentation given in Chapter 10 in the Andrews book). These results motivated the study of the divisibility of the difference \(a_{m}(m^{r+1}n)-a_{m}(m^{r}n)\) by powers of m (in the case of odd m) or by powers of m / 2 (in the case of even m). See for example the papers of Gupta [8, 10], Andrews [2], Rødseth and Sellers [12, 13].

Another kind of generalizations appeared in a recent work of Gawron, Miska and the first author [6]. More precisely, for \(k\in \mathbb {N}_{+}\) one can define the sequence \((A_{m,k}(n))_{n\in \mathbb {N}}\), where

The sequence \((A_{m,k}(n))_{n\in \mathbb {N}}\), as the sequence \((a_{m}(n))_{n\in \mathbb {N}}\), can be interpreted in a natural combinatorial way. More precisely, the number \(A_{m,k}(n)\) counts the number of representations of n as sums of powers of m, where each summand has one among k colors. Equivalently, we are looking for the number of solutions in non-negative integers of the system \(\varepsilon _{i}=\sum _{j=1}^{k}\varepsilon _{i,j}\), where \(\varepsilon _{i}\) comes from the m-ary representation given by (1). In [6], the sequence of the 2-adic valuations of \(A_{2,k}(n)\) was investigated. The authors proved that the sequence \((\nu _{2}(A_{2,k}(n)))_{n\in \mathbb {N}}\) with \(k=2^{s}-1, s\in \mathbb {N}_{+}\), is bounded by 2. In fact the precise description whether \(\nu _{2}(A_{2,k}(n))=1\) or 2 is presented in the paper. Let \(m=p\), where p is a prime number. A question arises: is it possible to find a simple expression for an exponent k, such that the sequence \((\nu _{p}(A_{p,k}(n)))_{n\in \mathbb {N}}\) is bounded or even can be described in simple terms? This natural question was the main motivation for writing this paper. As we will see the required generalization can be given and is presented in Theorem 3.1.

Let us describe the content of the paper in some details. In Sect. 2 we present some preliminary result needed in the sequel and present the proof of the lemma which contains precise information on the p-adic valuation of certain sums which are closely related to the coefficients of the power series expansion of \(F_{p}(x)^{-r}\), where \(r\in \{1,\ldots ,p-1\}\).

In Sect. 3, among other things we present the computation of the exact value of the p-adic valuation of the number \(A_{p,(p-1)(p^s-1)}(n)\), where \(p\in \mathbb {P}_{\ge 3}\) and \(s\in \mathbb {N}_{+}\). More precisely, for \(n\ge p^s\), we prove the equality \(\nu _{p}(A_{p,(p-1)(p^s-1)}(n))=1\). Note that the number \(k=(p-1)(p^s-1)\) for \(p=2\) reduces to the exponent considered in [6]. However, in the mentioned paper the sequence of the 2-adic valuations of \((2^s-1)\)-colored partitions is not eventually constant (and it is not periodic). This shows striking difference between the case of \(p=2\) and \(p\ge 3\). Moreover, we obtain some result concerning the boundedness of the sequence \((\nu _{p}(A_{p,(p-1)(up^s-1)}(n)))_{n\in \mathbb {N}}\) for \(p\in \mathbb {P}_{\ge 3}, u\in \{2,\ldots ,p-1\}\) and \(s\in \mathbb {N}_{+}\).

Finally, in the last section we state some conjectures on the shape of exponents k which (according to numerical calculations) lead to bounded (but not-eventually constant) sequences \((\nu _{p}(A_{p,k}(n)))_{n\in \mathbb {N}}\).

Before we state our theorems we will need some notation and preliminary results concerning various objects related to unique representation of integer n in the base p.

For a given p (non-necessarily a prime), an integer n and \(i\in \{0,\ldots ,p-1\}\) we define

The above number counts the number of the digits equal to i in the base p representation of the integer n. From the definition, we immediately deduce the following equalities:

Lemma 2.1

Let \(r\in \{1,\ldots ,p-1\}\). We have

where

with the convention that \(\left( {\begin{array}{c}a\\ b\end{array}}\right) =0\) for \(b>a\) and \(0^0=1\). Moreover, for \(j\in \{0,\ldots ,p-1\}\) and \(n\in \mathbb {N}_{+}\) we have

Proof

The first equality is a simple consequence of the uniqueness of the base p representation of a given number n and the equality

Indeed, the number \(D_{p,r}(n)\) can be written as

and hence our compact formula.

In order to get the second part of our lemma we note that \(N_{p}(i,n)=1\) for \(n\in \{0,1\ldots ,r\}\) and \(N_{p}(i,n)=0\) for \(n\in \{r+1\ldots ,p-1\}\). With our convention we have that \(D_{p,r}(n)=(-1)^{n}\left( {\begin{array}{c}r\\ n\end{array}}\right) \) in this case. Writing now \(n=pn'+j\) for some \(j\in \{0,\ldots ,p-1\}\) we get

and our lemma follows. \(\square \)

The above results are true without the assumption \(p\in \mathbb {P}\). However, from now up to the end of the paper we assume that p is an odd prime. Moreover, in order to shorten the notation a bit we define the number \(D_{p}(n)\) as

In particular \(D_{p}(n)\ne 0\) for all \(n\in \mathbb {N}\).

Lemma 2.2

Let \(k\in \mathbb {N}_{+}\) and suppose that \(p-1|k\). Then

Proof

Let us recall that if the congruence \(a\equiv b\pmod {p}\) holds, then for any \(t\in \mathbb {N}_{+}\) we have \(a^{p^{t}}\equiv b^{p^{t}}\pmod {p^{t+1}}\).

From the definition of the function \(F_{p}(x)\) we get

and thus we immediately deduce that \(F_{p}(x)^{p-1}\equiv (1-x)\pmod {p}\). Invoking now the property mentioned above with \(t=\nu _{p}(k)\) we get

Write \(k=p^{\nu _{p}(k)}(p-1)\delta \). Raising the both sides of the last congruence to the power \(\delta \) we get the result. \(\square \)

We are ready to present the crucial lemma which will be the main tool in our study of the p-adic valuation of the number \(A_{p,(p-1)(up^s-1)}(n)\) in the sequel. More precisely, the lemma contains information about behaviour of the p-adic valuation of the expression

Lemma 2.3

Let \(p\ge 3\) be prime and \(u\in \{1,\ldots ,p-1\}\). Let \(n\ge p\) be of the form \(n=n''p^{s+1}+kp^{s}+j\) for some \(n''\in \mathbb {N}, k\in \{1, \ldots , p-1\}, s\in \mathbb {N}_{+}\) and \(j\in \{0,\ldots , p-1\}\). Then the following equality holds:

In particular:

1. (a)

   If \(u=1\), then

   $$\begin{aligned} \nu _{p}\left( \sum _{i=0}^{u}(-1)^{i}\left( {\begin{array}{c}u\\ i\end{array}}\right) D_{p}(n-i)\right) =\nu _{p}(D_{p}(n)-D_{p}(n-1))=1, \end{aligned}$$

   for any \(n\in \mathbb {N}_{+}\).

2. (b)

   If \(j\ge u\), then we have the equality

   $$\begin{aligned} \nu _{p}\left( \sum _{i=0}^{u}(-1)^{i}\left( {\begin{array}{c}u\\ i\end{array}}\right) D_{p}(n-i)\right) =1. \end{aligned}$$
3. (c)

   If \(u\ge 2\), then there exist \(j, k\in \{0,\ldots ,p-1\}, k\ne 0\), such that we have

   $$\begin{aligned} \nu _{p}\left( \sum _{i=0}^{u}(-1)^{i}\left( {\begin{array}{c}u\\ i\end{array}}\right) D_{p}(n-i)\right) \ge 2. \end{aligned}$$

Proof

Let us suppose that \(n\in \{u,\ldots ,p-1\}\). Then

Let \(n\ge p\) and write \(n=pn'+j\) for some \(j\in \{0,\ldots ,p-1\}\) and \(n'\in \mathbb {N}_{+}\). We have

Write \(n'=n''p+k\). If \(k\ge 1\), then

If \(k=0\), then

Hence if \(n'=p^{s}(ap+k)\) with \(k\ge 1\), then

If \(n'=kp^{s}\) with \(1<k\le p-1\), then

Finally, for \(n'=p^{s}\), we get

Thus, in any case we get that if \(n=n''p^{s+1}+kp^{s}+j\) for some \(n''\in \mathbb {N}\), \(k\in \{1,\ldots ,p-1\}\), \(s\in \mathbb {N}_{+}\) and \(j\in \{0,\ldots ,p-1\}\), then

The equality

implies

This finishes the proof of the main part of our lemma.

In order to get the part (a), it is enough to observe that for \(u=1\) we have

The result follows since \(1\le k\le p-1\).

If u is arbitrary and \(j\ge u\), then

Hence we get the part (b).

In order to prove the part (c) let us fix p and u. We want to find j and k such that

Let us write

Thus, we only need to find \(j\le u-1\) and \(k\in \{1,\ldots ,p-1\}\) such that

or equivalently,

In consequence, the sufficient condition for the inequality (4) to hold, is the condition

We prove that this is satisfied in at least one case \(j=0\) or \(j=1\). Let us observe that if \(j=0\), then

Similarly, for \(j=1\) we have

Thus, if \(p^{2}|\left( {\begin{array}{c}p+u-1\\ j\end{array}}\right) -\left( {\begin{array}{c}p+u-1\\ p+j\end{array}}\right) \) for \(j=0\) and \(j=1\), then \(p^{2}\) divides also the number

However,

and we get a contradiction. The result follows. \(\square \)

Now, we are ready to prove the following

Theorem 3.1

Let \(p\in \mathbb {P}_{\ge 3}\), \(u\in \{1,\ldots ,p-1\}\) and \(s\in \mathbb {N}_{+}\).

1. (a)

   If \(n>up^{s}\), then

   $$\begin{aligned} \nu _{p}(A_{p,(p-1)(up^s-1)}(n))\ge 1. \end{aligned}$$
2. (b)

   If \(n>p^{s}\), then

   $$\begin{aligned} \nu _{p}(A_{p,(p-1)(p^s-1)}(n))= 1. \end{aligned}$$
3. (c)

   If \(u\ge 2\), then

   $$\begin{aligned} \nu _{p}(A_{p,(p-1)(up^s-1)}(n))= 1 \end{aligned}$$

   for infinitely many n.

4. (d)

   If \(u\ge 2\), then

   $$\begin{aligned} \nu _{p}(A_{p,(p-1)(up^s-1)}(n))\ge 2 \end{aligned}$$

   for infinitely many n.

5. (e)

   If \(s\ge 2\) and \(n\ge p^{s+1}\) with the unique base p-representation \(n=\sum _{i=0}^{v}\varepsilon _{i}p^{i}\) and

   $$\begin{aligned} \nu _{p}(A_{p,(p-1)(up^s-1)}(n))\in \{1,2\}, \end{aligned}$$

   then the value of \(\nu _{p}(A_{p,(p-1)(up^s-1)}(n))\) depends only on the coefficient \(\varepsilon _{s}\) and the first non-zero coefficient \(\varepsilon _{t}\) with \(t>s\).

6. (f)

   If \(s\ge 2\) and

   $$\begin{aligned} \nu _{p}(A_{p,(p-1)(up^s-1)}(n))\le s \end{aligned}$$

   for \(n>up^{s}\), then also

   $$\begin{aligned} \nu _{p}(A_{p,(p-1)(up^s-1)}(pn))= & {} \nu _{p}(A_{p,(p-1)(up^s-1)}(pn+1))\\= & {} \ldots =\nu _{p}(A_{p,(p-1)(up^s-1)}(pn+(p-1))). \end{aligned}$$

Proof

Applying Lemma 2.2 with \(k=p^{s}(p-1)\) we get

Raising both sides to the power u we get

Multiplying both sides of the above congruence by \(F_{p}(x)^{1-p}\) we get

Equivalently, by using Lemma 2.1 and comparing coefficients on both sides of the above congruence, we get the congruence

Let us take \(n>up^{s}\) and write

for some \(t\ge s\). Let us define the numbers \(n_{0},\ldots ,n_{t}\) recursively in the following way

for \(i=0,1,\ldots ,t-1\). Let us observe that we have \(n_s \ge u\).

We start by proving the part (f). Let \(s\ge 2\). Observe, that the formula

implies that if \(p\not \mid k\), then \(p^{s}|\left( {\begin{array}{c}p^{s}\\ k\end{array}}\right) \). Hence, using Lemma 2.1, we get

Thus, if \(\nu _{p}(A_{p,(p-1)(up^s-1)}(n))\le s\), then

which does not depend on \(\varepsilon _{0}\). Hence we get (f).

In order to prove parts (a) to (e) it is enough to show that there exists a constant \(C_{1}\) not divisible by p, such that

and then apply Lemma 2.3.

From the formula (5) we see that the condition \(p^{s-1}\not \mid k\) implies \(p^{2}|\left( {\begin{array}{c}p^{s}\\ k\end{array}}\right) \). We proceed similarly as in the proof of the part (f). Indeed, we have

with

In the case of \(s=1\), the starting sum is of the same form with \(C_{2}=1\). It is clear that \(C_{2}\not \equiv 0\pmod p\). We need to investigate the expression in the brackets.

Observe that if p does not divide i, then \(p|\left( {\begin{array}{c}up^{s}\\ ip^{s-1}\end{array}}\right) \). We also have

and

The last equivalence is a consequence of Lucas theorem. Hence

Thus, we get the congruence

with

The result now follows from Lemma 2.2. \(\square \)

We have already proved a quite strong result concerning the behaviour of the p-adic valuation of \(A_{p,k}(n)\) for certain exponents k. The question arises: can we prove something in the opposite direction? More precisely: is it possible, given any \(s\in \mathbb {N}_{+}\), to construct an exponent \(k\in \mathbb {N}_{+}\) such that the congruence \(A_{p,k}(n)\equiv 0\pmod {p^{s}}\) has infinitely many solutions?

We are ready to investigate more closely the set

From Lemma 2.2 we immediately deduce that \(\mathcal {E}_{p}=\mathbb {N}\). However, for \(s\in \mathbb {N}_{+}\), the exponents k in this case are divisible by p. Can we produce exponents without this property? The answer to this question is contained in the following

Theorem 3.2

Let \(k\in \mathbb {N}_{+}, p\in \mathbb {P}_{\ge 3}\) and suppose that \(p^2(p-1)|k\) and \(r\in \{1,\ldots ,p-2\}\).

Then, there are infinitely many \(n\in \mathbb {N}_{+}\) such that

Proof

From the assumption \(p-1|k\) and the congruence \(F_{p}(x)^{p-1}\equiv 1-x\pmod {p}\) we get

Multiplying both sides of the above congruence by \(F(x)^{-r}\) we obtain

Write \(k/(p-1)=\delta p^{\nu }\) for some \(\delta \in \mathbb {N}_{+}\), where \(\nu =\nu _{p}(k)\ge 2\). Hence, comparing coefficients on both sides of the above congruence we get the congruence

Let \(n>\delta p^{\nu }\) and write \(n=pn'+j\) for some \(n'\in \mathbb {N}\) and \(j\in \{0,\ldots ,p-1\}\). Let us observe that if \(p\not \mid i\), then \(p^{\nu }|\left( {\begin{array}{c}\delta p^{\nu }\\ i\end{array}}\right) \). Thus

In consequence, \(A_{p,k-r}(n)\equiv 0\pmod {p^{\nu }}\) for any \(n>\delta p^{\nu }=k/(p-1)\) satisfying \(n\equiv j\pmod p\), where \(j\in \{r+1,\ldots ,p-1\}\) is arbitrarily chosen. The proof is complete. \(\square \)

Remark 3.3

The above result can be seen as a (weak) generalization of the result obtained by Rødseth and Sellers in [12], which says that for any odd m and \(s\in \mathbb {N}_{+}\), the congruence \(a_{m}(n)\equiv 0\pmod {m^{s}}\) has infinitely many solutions in n. The weakness of our result is in the dependence of the number of colors and the exponent s.

From Lemma 2.2 and the proof of our theorem we can easily deduce the following

Corollary 3.4

Let \(k\in \mathbb {N}_{+}\) and suppose that the sequence \((\nu _{p}(A_{p,k}(n)))_{n\in \mathbb {N}}\) is eventually constant and equal to 1.

1. (a)

   If \(p-1|k\), then \(p\not \mid k\).

2. (b)

   If \(p-1\not \mid k\), \(k=(p-1)k'+q\) for some \(q\in \{1,\ldots ,p-2\}\), and \(p|k'+1\), then \(p^{2}\not \mid k'+1\).

Our Theorem 3.1 implies boundedness of the sequence \((\nu _{p}(A_{p,k}(n)))_{n\in \mathbb {N}}\) with \(k=(p-1)(p^s-1)\) and \(s\in \mathbb {N}_{+}\). It is natural to ask whether the founded family of exponents is the only one with this property. In order to get some feelings about this question, we performed numerical search with primes \(p\in \{3,5,7,11\}\), the exponents \(k\le 100\) and \(n\le 10^4\). Our numerical search motivated the following

Conjecture 1

Let \(p\in \mathbb {P}_{\ge 3}, u\in \{2,\ldots ,p-1\}\) and \(s\in \mathbb {N}_{+}\). Then, for \(n\ge up^{s}\) we have

Moreover, for each \(n\in \mathbb {N}_{+}\) we have the equalities

The above conjecture was suggested by our numerical observations. Moreover, the form of the conjecture motivated the parts (c) to (f) in Theorem 3.1.

Let \(k\in \mathbb {N}_{\ge 2}\) be given. We say that the sequence \({\varepsilon }=(\varepsilon _{n})_{n\in \mathbb {N}}\) is k-automatic if and only if the following set

called the k-kernel of \({\varepsilon }\), is finite. In the case of \(p=2\) we know that the sequence \((\nu _{2}(A_{2,2^s-1}(n)))_{n\in \mathbb {N}}\) is 2-automatic (and it is not eventually periodic). In Theorem 3.1 we proved that the sequence \((\nu _{p}(A_{p,k}(n)))_{n\in \mathbb {N}}\) for \(k=(p-1)(p^s-1)\) with \(p\ge 3\), is eventually constant and hence k-automatic for any k.

We calculated the first \(10^5\) elements of the sequence \((\nu _{p}(A_{p,(p-1)(up^s-1)}(n)))_{n\in \mathbb {N}}\) for any \(p\in \{3, 5, 7\}, s\in \{1,2\}\) and \(u\in \{1,\ldots ,p-1\}\) and were not able to spot any general relations. Our numerical observations lead us to the following

Question 1

For which \(p\in \mathbb {P}_{\ge 5}, s\in \mathbb {N}\) and \(u\in \{2,\ldots , p-1\}\), the sequence \((\nu _{p}(A_{p,(p-1)(up^s-1)}(n)))_{n\in \mathbb {N}}\) is k-automatic for some \(k\in \mathbb {N}_{+}\)?

Finally, we formulate the following

Conjecture 2

Let \(k\in \mathbb {N}_{+}, p\in \mathbb {P}\) and suppose that k is not of the form \((p-1)(up^s-1)\) for \(s\in \mathbb {N}\) and \(u\in \{1,\ldots ,p-1\}\). Then, the sequence \((\nu _{p}(A_{p,k}(n)))_{n\in \mathbb {N}}\) is unbounded.