SOME DIVISIBILITY PROPERTIES OF BINOMIAL AND q-BINOMIAL COEFFICIENTS

Victor J. W. Guo^{1} and C. Krattenthaler^{2†}

1Department of Mathematics, East China Normal University Shanghai 200062, People’s Republic of China

                 Email: jwguo@math.ecnu.edu.cn
                 WWW: http://math.ecnu.edu.cn/~jwguo

2Fakultät für Mathematik, Universität Wien Oskar-Morgenstern-Platz 1, A-1090 Vienna, Austria.

               WWW: http://www.mat.univie.ac.at/~kratt.

Abstract. We first prove that if a has a prime factor not dividing b then there are infinitely many positive integers n such that \binom{an+bn}{an} is not divisible by bn + 1. This confirms a recent conjecture of Z.-W. Sun. Moreover, we provide some new divisibility properties of binomial coefficients: for example, we prove that \binom{12n}{3n} and \binom{12n}{4n} are divisible by 6n − 1, and that \binom{330n}{88n} is divisible by 66n − 1, for all positive integers n. As we show, the latter results are in fact consequences of divisibility and positivity results for quotients of q-binomial coefficients by q-integers, generalising the positivity of q-Catalan numbers. We also put forward several related conjectures.

1. Introduction

The study of arithmetic properties of binomial coefficients has a long history. In 1819, Babbage [6] proved the congruence

\binom{2p − 1}{p − 1} ≡ 1 (mod p^{2})

for primes p ⩾ 3. In 1862, Wolstenholme [28] showed that the above congruence holds modulo p^{3} for any prime p ⩾ 5. See [20] for a historical survey on Wolstenholme’s theorem. Another famous congruence is

\binom{2n}{n} ≡ 0 (mod n + 1).

2010 Mathematics Subject Classification. Primary 11B65; Secondary 05A10, 05A30. Key words and phrases. binomial coefficients, Lucas’ theorem, Euler’s totient theorem, q-binomial

coefficients, Gaußian polynomials, Catalan numbers, q-Catalan numbers, positive polynomials.

†Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S50-N15, the latter in the framework of the Special Research Program “Algorithmic and Enumerative Combinatorics”.

The corresponding quotients, the numbers C_{n} := \frac{1}{n+1} \binom{2n}{n}, are called Catalan numbers, and they have many interesting combinatorial interpretations; see, for example, [12] and [24, pp. 219–229]. Recently, Ulas and Schinzel [27] studied divisibility problems of Erdős and Straus, and of Erdős and Graham. In [25, 26], Sun gave some new divisibility properties of binomial coefficients and their products. For example, Sun proved the following result.

Theorem 1.1. [26, Theorem 1.1] Let a, b, and n be positive integers. Then

\binom{an + bn}{an} ≡ 0 mod \frac{bn + 1}{gcd(a, bn + 1)}.  (1.1)

Sun also proposed the following conjecture.

Conjecture 1.2. [26, Conjecture 1.1] Let a and b be positive integers. If (bn + 1) |\binom{an+bn}{an} for all sufficiently large positive integers n, then each prime factor of a divides b. In other words, if a has a prime factor not dividing b, then there are infinitely many positive integers n such that (bn + 1) ∤ \binom{an+bn}{an}.

Inspired by Conjecture 1.2, Sun [26] introduced a new function f: ℤ^{+} × ℤ^{+} → ℕ. Namely, for positive integers a and b, if \binom{an+bn}{an} is divisible by bn + 1 for all n ∈ ℤ^{+}, then he defined f(a, b) = 0; otherwise, he let f(a, b) be the smallest positive integer n such that \binom{an+bn}{an} is not divisible by bn + 1. Using Mathematica, Sun [26] computed some values of the function f:

f(7, 36) = 279, f(10, 192) = 362, f(11, 100) = 1187, f(22, 200) = 6462, ….

The present paper serves several purposes: first of all, we give a proof of Conjecture 1.2 (see Theorem 2.1 below); second, we provide congruences and divisibility results similar to the ones addressed in Theorem 1.1 and Conjecture 1.2 (see Theorems 2.2–2.3 in Section 2); third, we show in Section 3 that among these results there is a significant number which can be “lifted to the q-world;” in other words, there are several such results which follow directly from stronger divisibility results for q-polynomials. In particular, Theorem 1.1 is an easy consequence of Theorem 3.3, and Theorem 2.3 is an easy consequence of Theorem 3.1. On the other hand, Theorem 2.4 hints at the limitations of occurrence of these divisibility phenomena. Sections 4–6 are devoted to the proofs of our results in Sections 2 and 3. We close our paper with Section 7 by posing several open problems.

2. Results, I

Our first result is a more precise version of Conjecture 1.2.

Theorem 2.1. Conjecture 1.2 is true. Moreover, if p is a prime such that p | a but p ∤ b, then

f(a, b) ⩽ \frac{p^{φ(a+b)} − 1}{a + b},

where φ(n) is Euler’s totient function.

For the proof of the above result, we need the following theorem.

Theorem 2.2. Let a and b be positive integers with a > b, and β an integer. Let p be a prime not dividing a. Then there are infinitely many positive integers n such that

\binom{an}{bn + β} ≡ ±1 (mod p).

Our proofs of Theorems 2.1 and 2.2 are based on Euler’s totient theorem and Lucas’ classical theorem on the congruence behaviour of binomial coefficients modulo prime numbers, see Section 4.

In [14, Corollary 2.3], the first author proved that

\binom{6n}{3n} ≡ 0 (mod 2n − 1).  (2.1)

It is easy to see that

\binom{2n}{n} = 2\binom{2n − 1}{n} = \frac{4n − 2}{n}\binom{2n − 2}{n − 1} ≡ 0 (mod 2n − 1).  (2.2)

The next theorem gives congruences similar to (2.1) and (2.2).

Theorem 2.3. Let n be a positive integer. Then

\binom{12n}{3n} ≡ \binom{12n}{4n} ≡ 0 (mod 6n − 1),  (2.3)

\binom{30n}{5n} ≡ 0 (mod (10n − 1)(15n − 1)),  (2.4)

\binom{60n}{6n} ≡ \binom{120n}{40n} ≡ \binom{120n}{45n} ≡ 0 (mod 30n − 1),  (2.5)

\binom{330n}{88n} ≡ 0 (mod 66n − 1).  (2.6)

We shall see that this theorem is the consequence of a stronger result for q-binomial coefficients, cf. Theorem 3.1 in the next section.

It seems that there should exist many more congruences like (2.1)–(2.6). (In this direction, see Conjecture 7.3.) On the other hand, we have the following negative result.

Theorem 2.4. There are no positive integers a and b such that

\binom{an + bn}{an} ≡ 0 (mod 3n − 1)

for all n ⩾ 1.

For a possible generalisation of this theorem see Conjecture 7.2 in the last section.

3. Results, II: q-divisibility properties

Recall that the q-binomial coefficients (also called Gaußian polynomials) are defined by

[\begin{matrix}n \\ k \end{matrix}]_{q} = \begin{cases}\frac{(1 − q^{n})(1 − q^{n−1}) ⋯ (1 − q)}{(1 − q^{k})(1 − q^{k−1}) ⋯ (1 − q)(1 − q^{n−k})(1 − q^{n−k−1}) ⋯ (1 − q)}, & if 0 ⩽ k ⩽ n, \\ 0, & otherwise. \end{cases}

We begin with the announced strengthening of Theorem 2.3.

Theorem 3.1. Let n be a positive integer. Then all of

\frac{1 − q}{1 − q^{6n−1}} [\begin{matrix}12n \\ 3n \end{matrix}]_{q} , \frac{1 − q}{1 − q^{6n−1}} [\begin{matrix}12n \\ 4n \end{matrix}]_{q} , \frac{1 − q}{1 − q^{30n−1}} [\begin{matrix}60n \\ 6n \end{matrix}]_{q} ,

\frac{1 − q}{1 − q^{30n−1}} [\begin{matrix}120n \\ 40n \end{matrix}]_{q} , \frac{1 − q}{1 − q^{30n−1}} [\begin{matrix}120n \\ 45n \end{matrix}]_{q} , \frac{1 − q}{1 − q^{66n−1}} [\begin{matrix}330n \\ 88n \end{matrix}]_{q} (3.1)

are polynomials in q with non-negative integer coefficients. Furthermore,

\frac{(1 − q)^{2}}{(1 − q^{10n−1})(1 − q^{15n−1})} [\begin{matrix}30n \\ 5n \end{matrix}]_{q}  (3.2)

is a polynomial in q.

For a conjectural stronger form of the last assertion in the above theorem see Conjecture 7.4 at the end of the paper.

It is obvious that, when a = b = 1, the numbers \binom{an+bn}{an}/(bn + 1) (featured implicitly in Conjecture 1.2 and in Theorem 2.1) reduce to the Catalan numbers C_{n}. There are various q-analogues of the Catalan numbers. See Fürlinger and Hofbauer [10] for a survey, and see [11, 17, 16] for the so-called q, t-Catalan numbers.

A natural q-analogue of C_{n} is

C_{n}(q) = \frac{1 − q}{1 − q^{n+1}} [\begin{matrix}2n \\ n \end{matrix}]_{q} .

It is well known that the q-Catalan numbers C_{n}(q) are polynomials with non-negative integer coefficients (see [1, 2, 4, 10]). Furthermore, Haiman [17, (1.7)] proved (and it follows from Lemma 5.2 below) that the polynomial

\frac{1 − q}{1 − q^{bn+1}} [\begin{matrix}bn + n \\ n \end{matrix}]_{q}

has non-negative coefficients for all b, n ⩾ 1. Another generalisation of C_{n}(q) was introduced by the first author and Zeng [15]:

B_{n,k}(q) := \frac{1 − q^{k}}{1 − q^{n}} [\begin{matrix}2n \\ n − k \end{matrix}]_{q} = [\begin{matrix}2n − 1 \\ n − k \end{matrix}]_{q} − [\begin{matrix}2n − 1 \\ n − k − 1 \end{matrix}]_{q} q^{k}, 1 ⩽ k ⩽ n.

They noted that the B_{n,k}(q)’s are polynomials in q, but did not address the question whether they are polynomials with non-negative coefficients. As the next theorem shows, this turns out to be the case. The theorem establishes in fact a stronger non-negativity property.

Theorem 3.2. Let n and k be non-negative integers with 0 ⩽ k ⩽ n. Then

\frac{1 − q^{gcd(k,n)}}{1 − q^{n}} [\begin{matrix}2n \\ n − k \end{matrix}]_{q}  (3.3)

is a polynomial in q with non-negative integer coefficients. Consequently, also B_{n,k}(q) = \frac{1−q^{k}}{1−q^{n}} [ \begin{matrix}2n \\ n−k \end{matrix}]_{q} is a polynomial with non-negative coefficients.

Applying the inequality [26, (2.1)], we can also easily deduce that

C_{a,b,n}(q) := \frac{1 − q^{a}}{1 − q^{bn+1}} [\begin{matrix}an + bn \\ an \end{matrix}]_{q}

is a product of certain cyclotomic polynomials, and therefore a polynomial in q. Again, as it turns out, all coefficients in these polynomials are non-negative. Also here, we have actually a stronger result, given in the theorem below. It should be noted that it generalises Theorem 1.1, the latter being obtained upon letting q → 1.

Theorem 3.3. Let a, b, and n be positive integers. Then

\frac{1 − q^{gcd(an,bn+1)}}{1 − q^{bn+1}} [\begin{matrix}an + bn \\ an \end{matrix}]_{q} = \frac{1 − q^{gcd(an,bn+1)}}{1 − q^{an+bn+1}} [\begin{matrix}an + bn + 1 \\ an \end{matrix}]_{q}

is a polynomial in q with non-negative coefficients.

Corollary 3.4. Let a, b, and n be positive integers. Then

\frac{1 − q^{a}}{1 − q^{bn+1}} [\begin{matrix}an + bn \\ an \end{matrix}]_{q}

is a polynomial in q with non-negative coefficients.

The proofs of the results in this section are given in Section 5.

4. Proofs of Theorems 2.1 and 2.2

The proof of Theorem 2.2 (from which subsequently Theorem 2.1 is derived) makes essential use of Lucas’ classical theorem on binomial coefficient congruences (see, for example, [7, 9, 13, 21]). For the convenience of the reader, we recall the theorem below.

Theorem 4.1 (Lucas’ theorem). Let p be a prime, and let a_{0}, b_{0}, …, a_{m}, b_{m} ∈ {0, 1, …, p − 1}. Then

\binom{a_{0} + a_{1}p + ⋯ + a_{m}p^{m}}{b_{0} + b_{1}p + ⋯ + b_{m}p^{m}} ≡ ∏_{i=0}^{m} \binom{a_{i}}{b_{i}} (mod p).

Proof of Theorem 2.2. Note that gcd(p, a) = 1. By Euler’s totient theorem (see [23]), we have

p^{φ(a)} − 1 ≡ 0 (mod a).

Since a > b > 0, there exists a positive integer N such that an > bn + β > 0 holds for all n > N. Let r be a positive integer such that p^{rφ(a)} − 1 > aN, and let n = (p^{rφ(a)} − 1)/a. Then, by Lucas’ theorem, we have

\binom{an}{bn + β} = \binom{p^{rφ(a)} − 1}{bn + β} ≡ ∏_{i=0}^{m} \binom{p − 1}{b_{i}} ≡ (−1)^{b_{0}+···+b_{m}} (mod p),

where bn + β = b_{0} + b_{1}p + ⋯ b_{m}p^{m} with 0 ⩽ b_{0}, …, b_{m} ⩽ p − 1. It is clear that there are infinitely many such r and n. This completes the proof. □

Proof of Theorem 2.1. Suppose that a and b are positive integers and p a prime such that p | a but p ∤ b. We have the decomposition

\frac{1}{bn + 1}\binom{an + bn}{an} = \binom{an + bn}{an − 1} − \frac{a + b}{a}\binom{an + bn − 1}{an − 2}.  (4.1)

It is clear that p ∤ (a+b). By the proof of Theorem 2.2, if we take n = (p^{rφ(a+b)}−1)/(a+b) (r ⩾ 1), then

\binom{an + bn}{an − 1} ≡ ±1 (mod p),

and thus

(a + b)\binom{an + bn − 1}{an − 2} = \frac{an − 1}{n}\binom{an + bn}{an − 1} ≡ ±(a + b) ≢ 0 (mod p).  (4.2)

Combining (4.1) and (4.2) gives

\frac{1}{bn + 1}\binom{an + bn}{an} ∉ ℤ

for all n = (p^{rφ(a+b)} − 1)/(a + b) (r = 1, 2, …). Namely, Conjecture 1.2 holds and

f(a, b) ⩽ \frac{p^{φ(a+b)} − 1}{a + b},

as desired. □

5. Proofs of Theorems 3.1–3.3 and of Corollary 3.4

All the proofs in this section are similar in spirit. They all draw on a lemma from [22, Proposition 10.1.(iii)], which extracts the essentials out of an argument of Andrews [3, Proof of Theorem 2]. (To be precise, Lemma 5.1 below is a slight generalisation of [22, Proposition 10.1.(iii)]. However, the proof from [22] works also for this generalisation. We provide it here for the sake of completeness.) Recall that a polynomial P (q) = ∑_{i=0}^{d} p_{i}q^{i} in q of degree d is called reciprocal if p_{i} = p_{d−i} for all i, and that it is called unimodal if there is an integer r with 0 ⩽ r ⩽ d and 0 ⩽ p_{0} ⩽ … ⩽ p_{r} ⩾ … ⩾ p_{d} ⩾ 0.

Lemma 5.1. Let P (q) be a reciprocal and unimodal polynomial and m and n positive integers with m ⩽ n. Furthermore, assume that A(q) = \frac{1−q^{m}}{1−q^{n}} P (q) is a polynomial in q. Then A(q) has non-negative coefficients.

Proof. Since P (q) is unimodal, the coefficient of q^{k} in (1 − q^{m})P (q) is non-negative for 0 ⩽ k ⩽ deg(P)/2. Consequently, the same must be true for A(q) = \frac{1−q^{m}}{1−q^{n}} P (q), considered as a formal power series in q. However, also A(q) is reciprocal, and its degree is at most the degree of P (q). Therefore the remaining coefficients of A(q) must also be non-negative. □

Proof of Theorem 3.1. In view of Lemma 5.1 and the well-known reciprocality and unimodality of q-binomial coefficients (cf. [24, Ex. 7.75.d]), for proving Theorem 3.1 it suffices to show that the expressions in (3.1) and (3.2) are polynomials in q. We are going to accomplish this by a count of the cyclotomic polynomials which divide numerators and denominators of these expressions, respectively.

We begin by showing that \frac{1−q}{1−q^{6n−1}} [ \begin{matrix}12n \\ 3n \end{matrix}]_{q} is a polynomial in q. We recall the well-known fact that

q^{n} − 1 = ∏_{d|n} Φ_{d}(q),

where Φ_{d}(q) denotes the d-th cyclotomic polynomial in q. Consequently,

\frac{1 − q}{1 − q^{6n−1}} [\begin{matrix}12n \\ 3n \end{matrix}]_{q} = ∏_{d=2}^{12n} Φ_{d}(q)^{e_{d}},

with

e_{d} = −χ(d | (6n − 1)) + ⌊\frac{12n}{d}⌋ − ⌊\frac{3n}{d}⌋ − ⌊\frac{9n}{d}⌋ ,  (5.1)

where χ(S) = 1 if S is true and χ(S) = 0 otherwise. This is clearly non-negative, unless d | (6n − 1).

So, let us assume that d | (6n − 1), which in particular means that d ⩾ 5. Let us write X = {3n/d}, where {α} := α − ⌊α⌋ denotes the fractional part of α. Using this notation, Equation (5.1) becomes

e_{d} = −χ(d | (2dX − 1)) + ⌊4X⌋ − ⌊3X⌋ .

Since 0 ⩽ X < 1, we have −1 ⩽ 2dX − 1 < 2d. The only integers which are divisible by d in the range −1, 0, …, 2d − 1 are 0 and d. Hence, we must have X = 1/(2d) or X = (d + 1)/(2d). The former is impossible since X is a rational number which can be written with denominator d. Thus, the only possibility left is X = (d + 1)/(2d). For this choice, it follows that ⌊4X⌋ − ⌊3X⌋ = 2 − 1 = 1. (Here we used that d ⩾ 5.) This proves that e_{d} is non-negative also in this case, and completes the proof of polynomiality

of \frac{1−q}{1−q^{6n−1}} [ \begin{matrix}12n \\ 3n \end{matrix}]_{q}.

The proof of polynomiality of \frac{1−q}{1−q^{6n−1}} [ \begin{matrix}12n \\ 4n \end{matrix}]_{q} is completely analogous and therefore left to the reader.

We next turn our attention to \frac{1−q}{1−q^{30n−1}} [ \begin{matrix}60n \\ 6n \end{matrix}]_{q}. Again, we write

\frac{1 − q}{1 − q^{30n−1}} [\begin{matrix}60n \\ 6n \end{matrix}]_{q} = ∏_{d=2}^{60n} Φ_{d}(q)^{e_{d}},

with

e_{d} = −χ(d | (30n − 1)) + ⌊\frac{60n}{d}⌋ − ⌊\frac{6n}{d}⌋ − ⌊\frac{54n}{d}⌋ .  (5.2)

This is clearly non-negative, unless d | (30n − 1).

We assume d | (30n − 1) and note that this implies d = 7 or d ⩾ 11. Here, we write X = {6n/d}. Using this notation, Equation (5.2) becomes

e_{d} = −χ(d | (5dX − 1)) + ⌊10X⌋ − ⌊9X⌋ .

Since 0 ⩽ X < 1, we have d | (5dX − 1) if and only if X is one of

\frac{1}{5d}, \frac{1}{5} + \frac{1}{5d}, \frac{2}{5} + \frac{1}{5d}, \frac{3}{5} + \frac{1}{5d}, \frac{4}{5} + \frac{1}{5d}.

For the same reason as before, the option X = 1/(5d) is impossible. For the other options, the corresponding value of ⌊10X⌋ − ⌊9X⌋ is always 1, except if X = \frac{1}{5} + \frac{1}{5d} and d = 7. However, in that case, we have X = \frac{8}{35}, which cannot be written with denominator d = 7. Therefore this case can actually not occur. This completes the proof that e_{d} is non-negative for all d ⩾ 2, and, hence, that \frac{1−q}{1−q^{30n−1}} [ \begin{matrix}60n \\ 6n \end{matrix}]_{q} is a polynomial in q.

Proceeding in the same style, for the proof of polynomiality of \frac{1−q}{1−q^{30n−1}} [ \begin{matrix}120n \\ 40n \end{matrix}]_{q} we have to show that

e_{d} = −χ(d | (3dX − 1)) + ⌊12X⌋ − ⌊4X⌋ − ⌊8X⌋  (5.3)

is non-negative for all X of the form X = x/d with 0 ⩽ x < d, x being integral, and d ⩾ 2. Clearly, the expression in (5.3) is non-negative, except possibly if d | (3dX − 1). With the same reasoning as before, we see that the only cases to be examined are X = (d + 1)/(3d) and X = (2d + 1)/(3d), where d = 7 or d ⩾ 11. If X = (d + 1)/(3d), we have

⌊12X⌋ − ⌊4X⌋ − ⌊8X⌋ = 4 − 1 − ⌊\frac{8}{3} + \frac{8}{3d}⌋ .

So, this will be equal to 1, except if d = 7. However, in that case we have X = \frac{8}{21}, which cannot be written with denominator d = 7, a contradiction. Similarly, if X = (2d + 1)/(3d), we have

⌊12X⌋ − ⌊4X⌋ − ⌊8X⌋ = 8 − 2 − 5 = 1.

So, again, the exponent e_{d} in (5.3) is non-negative, which establishes that \frac{1−q}{1−q^{30n−1}} [ \begin{matrix}120n \\ 40n \end{matrix}]_{q} is a polynomial in q.

For the proof of polynomiality of \frac{1−q}{1−q^{66n−1}} [ \begin{matrix}330n \\ 88n \end{matrix}]_{q} we have to show that

e_{d} = −χ(d | (3dX − 1)) + ⌊15X⌋ − ⌊4X⌋ − ⌊11X⌋  (5.4)

is non-negative for all X of the form X = x/d with 0 ⩽ x < d, x being integral, and d ⩾ 2. Clearly, the expression in (5.4) is non-negative, except possibly if d | (3dX − 1). With the same reasoning as before, we see that the only cases to be examined are X = (d + 1)/(3d) and X = (2d + 1)/(3d), where d = 5, d = 7, or d ⩾ 13. If X = (d + 1)/(3d), we have

⌊15X⌋ − ⌊4X⌋ − ⌊11X⌋ = 5 + ⌊\frac{5}{d}⌋ − 1 − ⌊\frac{11}{3} + \frac{11}{3d}⌋ .

So, this will be equal to 1, except if d = 7. However, again, this is an impossible case. Similarly, if X = (2d + 1)/(3d), we have

⌊15X⌋ − ⌊4X⌋ − ⌊11X⌋ = 10 + ⌊\frac{5}{d}⌋ − 2 − ⌊\frac{22}{3} + \frac{11}{3d}⌋ = 1.

So, again, the exponent e_{d} in (5.4) is non-negative, which establishes that \frac{1−q}{1−q^{66n−1}} [ \begin{matrix}330n \\ 88n \end{matrix}]_{q} is a polynomial in q.

Turning to (3.2), to prove that \frac{(1−q)^{2}}{(1−q^{10n−1})(1−q^{15n−1})} [ \begin{matrix}30n \\ 5n \end{matrix}]_{q} is a polynomial in q, we must show that

e_{d} = −χ(d | (2dX − 1)) − χ(d | (3dX − 1)) + ⌊6X⌋ − ⌊5X⌋  (5.5)

is non-negative for all X of the form X = x/d with 0 ⩽ x < d, x being integral, and d ≠ 5.

First of all, we should observe that gcd(10n − 1, 15n − 1) = 1, whence the two truth functions in (5.5) cannot equal 1 simultaneously. Therefore, the expression in (5.5) is nonnegative, except possibly if d | (2dX − 1) or if d | (3dX − 1). With the same reasoning as before, we see that the only cases to be examined are X = (d+1)/(2d), X = (d+1)/(3d), and X = (2d + 1)/(3d), where, in the latter two cases, the choice of d = 3 is excluded. If X = (d + 1)/(2d), then

⌊6X⌋ − ⌊5X⌋ = 3 + ⌊\frac{3}{d}⌋ − ⌊\frac{5}{2} + \frac{5}{2d}⌋ ,

which always equals 1 for d ⩾ 2. If X = (d + 1)/(3d), then

⌊6X⌋ − ⌊5X⌋ = 2 + ⌊\frac{2}{d}⌋ − ⌊\frac{5}{3} + \frac{5}{3d}⌋ ,

which always equals 1 for d = 2, 6, 7, … (sic!). Because of our assumptions, we do not need to consider the cases d = 3 and d = 5, so the only remaining case is d = 4. However, in that case X = \frac{5}{12}, which cannot be written with denominator d = 4, a contradiction. Finally, if X = (2d + 1)/(3d), then

⌊6X⌋ − ⌊5X⌋ = 4 + ⌊\frac{2}{d}⌋ − ⌊\frac{10}{3} + \frac{5}{3d}⌋ ,

which always equals 1 for d ⩾ 2.

So, again, the exponent e_{d} in (5.5) is non-negative in all cases, which establishes that

\frac{(1−q)^{2}}{(1−q^{10n−1})(1−q^{15n−1})} [ \begin{matrix}30n \\ 15n \end{matrix}]_{q} is a polynomial in q. □

Proof of Theorem 3.2. By Lemma 5.1, it suffices to establish polynomiality of (3.3). When written in terms of cyclotomic polynomials, Expression (3.3) reads

\frac{1 − q^{gcd(k,n)}}{1 − q^{n}} [\begin{matrix}2n \\ n − k \end{matrix}]_{q} = ∏_{d=2}^{2n} Φ_{d}(q)^{e_{d}},

with

e_{d} = χ(d | gcd(k, n)) − χ(d | n) + ⌊\frac{2n}{d}⌋ − ⌊\frac{n − k}{d} ⌋ − ⌊\frac{n + k}{d} ⌋ .  (5.6)

Similarly as before, let us write N = {n/d} and K = {k/d}. Using this notation, Equation (5.6) becomes

e_{d} = χ(d | gcd(k, n)) − χ(d | n) + ⌊2N⌋ − ⌊N − K⌋ − ⌊N + K⌋ .  (5.7)

We have to distinguish several cases. If d | n, then N = 0, and (5.7) becomes

e_{d} = χ(d | k) − 1 − ⌊−K⌋ .

We see that this is zero (and, hence, non-negative) regardless whether d | k or not. On the other hand, if we assume that d ∤ n, then (5.7) becomes

e_{d} = ⌊2N⌋ − ⌊N − K⌋ − ⌊N + K⌋ ,

and this is always non-negative. We have proven that (3.3) is indeed a polynomial in q.

The statement on B_{n,k}(q) follows immediately from the previous result and the fact that gcd(k, n) | k. □

Finally, Theorem 3.3 will follow immediately from the following strengthening of a non-negativity result of Andrews [3, Theorem 2].

Lemma 5.2. Let a and b be positive integers. Then

\frac{1 − q^{gcd(a,b)}}{1 − q^{a+b}} [\begin{matrix}a + b \\ a \end{matrix}]_{q}  (5.8)

is a polynomial in q with non-negative integer coefficients.

Proof. In view of Lemma 5.1, it suffices to show that the expression in (5.8) is a polynomial in q. Again, we start with the factorisation

\frac{1 − q^{gcd(a,b)}}{1 − q^{a+b}} [\begin{matrix}a + b \\ a \end{matrix}]_{q} = ∏_{d=2}^{a+b−1} Φ_{d}(q)^{e_{d}},

with

e_{d} = χ(d | gcd(a, b)) + ⌊\frac{a + b − 1}{d}⌋ − ⌊\frac{a}{d}⌋ − ⌊\frac{b}{d}⌋ .  (5.9)

Next we write A = {a/d} and B = {b/d}. Using this notation, Equation (5.9) becomes

e_{d} = χ(d | gcd(a, b)) + ⌊A + B − \frac{1}{d}⌋ .

This is clearly non-negative, unless A = B = 0. However, in that case we have d | a and d | b, that is, d | gcd(a, b), so that e_{d} is non-negative also in this case. □

Proof of Theorem 3.3. Replace a by an and b by bn + 1 in Lemma 5.2. □

Proof of Corollary 3.4. This follows immediately from Theorem 3.3 and the fact that a | gcd(a, bn + 1) = gcd(an, bn + 1). □

6. Proof of Theorem 2.4

The following auxiliary result on the occurrence of prime numbers congruent to 2 modulo 3 in “small” intervals will be crucial.

Lemma 6.1. If x ⩾ 530, there is always at least one prime number congruent to 2 modulo 3 contained in the interval (x, \frac{20}{19}x).

Proof. Let θ(x; 3, 2) denote the classical Chebyshev function, defined by

θ(x; 3, 2) = _{∑_{p prime, p⩽x} p≡2 (mod 3)} log p.

McCurley proved the following estimates for this function (see [19, Theorems 5.1 and 5.3]):

θ(y; 3, 2) < 0.51 y, y > 0,
θ(y; 3, 2) > 0.49 y, y ⩾ 3761.

This implies that, for x > 3761, we have

θ (\frac{20}{19}x; 3, 2) − θ(x; 3, 2) > 0.49 · \frac{20}{19}x − 0.51 x > 0.0057 x > 1.

This means that, if x > 3761, there must be a prime number congruent to 2 modulo 3 strictly between x and \frac{20}{19}x. (To be completely accurate: the above argument only shows that such a prime number exists in the half-open interval (x, \frac{20}{19}x]. However, existence in the open interval (x, \frac{20}{19}x) can be easily established in the same manner, by slightly lowering the value of \frac{20}{19} in the above argument.)

For the remaining range 530 ⩽ x ⩽ 3761, one can verify the claim directly using a computer. □

Proof of Theorem 2.4. Given a and b, our strategy consists in finding a prime p and a positive integer n such that the p-adic valuation of \binom{an+bn}{an}/(3n − 1) is negative, so that 3n − 1 cannot divide . \binom{an+bn}{an}. We first verified the possibility of finding such p and n for a, b ⩽ 1850 using a computer.

To establish the claim for the remaining values of a and b, we have to distinguish several cases, depending on the congruence classes of a and b modulo 3 and the relative sizes of a and b.

First let (a, b) ∈ {(0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0)} + (3ℤ)^{2}. By Dirichlet’s theorem [8] (see [5]), we know that there are infinitely many primes congruent to 2 modulo 3. Let us take such a prime p with p > a + b, and let 3n − 1 = p, that is, n = (p + 1)/3. Furthermore, let v_{p}(α) denote the p-adic valuation of α, that is, the maximal exponent e such that p^{e} divides α. Writing a = 3a_{1} + a_{2} and b = 3b_{1} + b_{2} with 0 ⩽ a_{2}, b_{2} ⩽ 2, by the well-known formula of Legendre [18, p. 10] for the p-adic valuation of factorials, we then have

v_{p} (\frac{1}{3n − 1}\binom{an + bn}{an}) = −1 + ∑_{ℓ⩾1} (⌊\frac{(a + b)n}{p^{ℓ}}⌋ − ⌊\frac{an}{p^{ℓ}}⌋ − ⌊\frac{bn}{p^{ℓ}}⌋)

= −1 + ⌊\frac{a_{2} + b_{2}}{3} + \frac{a + b}{3p}⌋ − ⌊\frac{a_{2}}{3} + \frac{a}{3p}⌋ − ⌊\frac{b_{2}}{3} + \frac{b}{3p}⌋ . (6.1)

Since, in the current case, we have 0 ⩽ a_{2} + b_{2} ⩽ 2 and \frac{a+b}{3p} < \frac{1}{3}, all the values of the floor functions on the right-hand side of the above equation are zero. Consequently, the p-adic valuation of \frac{1}{3n−1} \binom{an+bn}{an} equals −1 for our choice of p and n, which in particular means that \frac{1}{3n−1} \binom{an+bn}{an} is not an integer.

For the next case, consider a pair (a, b) ∈ {(2, 1), (2, 2)} + (3ℤ)^{2}. Let us first assume that b ⩽ \frac{9}{10}a. Since we have already verified the claim for a, b ⩽ 1850, we may assume a ⩾ 1850. We now choose a prime p ≡ 2 (mod 3) strictly between \frac{19}{20}a and a. Such a prime is guaranteed to exist by Lemma 6.1, because, due to our assumption, we have \frac{19}{20}a ⩾ 1757.5 > 530. Furthermore, we choose n = (p + 1)/3. We have

(a + b)n ⩽ \frac{19}{10}a\frac{p + 1}{3} < \frac{2}{3}p(p + 1) < p^{2},

and hence, with the same notation as above, Equation (6.1) holds also in the current case. We have 3 ⩽ a_{2} + b_{2} ⩽ 4, a + b ⩽ \frac{19}{10}a < 2p, \frac{a_{2}}{3} = \frac{2}{3}, \frac{1}{3} < \frac{a}{3p} ⩽ \frac{20}{57} < \frac{2}{3}, hence

⌊\frac{a_{2} + b_{2}}{3} + \frac{a + b}{3p}⌋ − ⌊\frac{a_{2}}{3} + \frac{a}{3p}⌋ − ⌊\frac{b_{2}}{3} + \frac{b}{3p}⌋ = 1 − 1 − 0 = 0.

Consequently, again, the p-adic valuation of \frac{1}{3n−1} \binom{an+bn}{an} equals −1 for our choice of p and n, which in particular means that \frac{1}{3n−1} \binom{an+bn}{an} is not an integer.

Next let again (a, b) ∈ \{(2, 1), (2, 2)\} + (3ℤ)^{2}, but \frac{9}{10}a < b ⩽ \frac{7}{5}a. Since we have already verified the claim for a, b ⩽ 1850, we may assume a ⩾ 1300. (If a < 1300, then the above restriction imposes the bound b ⩽ \frac{7}{5}1300 = 1820 < 1850.) Here, we choose a prime p ≡ 2 (mod 3) strictly between \frac{4}{5}a and \frac{9}{10}a. Such a prime is guaranteed to exist by Lemma 6.1, because, due to our assumption, we have \frac{4}{5}a = 1040 > 530. Furthermore, we choose n = (p + 1)/3. We have still 3 ⩽ a_{2} + b_{2} ⩽ 4, moreover 2p < \frac{19}{9}p < \frac{19}{10}a ⩽ a + b ⩽ \frac{12}{5}a < 3p, \frac{a_{2}}{3} = \frac{2}{3}, \frac{1}{3} < \frac{a}{3p} ⩽ \frac{5}{12} < \frac{2}{3}, \frac{1}{3} < \frac{3a}{10p} ⩽ \frac{b}{3p} ⩽ \frac{7a}{15p} ⩽ \frac{7}{12} < \frac{2}{3}, hence

⌊\frac{a_{2} + b_{2}}{3} + \frac{a + b}{3p}⌋ − ⌊\frac{a_{2}}{3} + \frac{a}{3p}⌋ − ⌊\frac{b_{2}}{3} + \frac{b}{3p}⌋ = 1 + χ(b_{2} = 2) − 1 − χ(b_{2} = 2) = 0,

implying again that the p-adic valuation of \frac{1}{3n−1} \binom{an+bn}{an} equals −1 for our choice of p and n, as desired.

The next case we discuss is (a, b) ∈ \{(2, 1)\} + (3ℤ)^{2} and \frac{7}{5}a < b ⩽ 3a. Since we have already verified the claim for a, b ⩽ 1850, we may assume b ⩾ 1850. Here, we choose a prime p ≡ 2 (mod 3) strictly between \frac{3}{10}b and \frac{1}{3}b. Such a prime is guaranteed to exist by Lemma 6.1, because, due to our assumption, we have \frac{3}{10}b = 555 > 530. Furthermore, we choose n = (p + 1)/3. Here we have

v_{p} (\frac{1}{3n − 1}\binom{an + bn}{an}) = −1 + ∑_{ℓ⩾1} (⌊\frac{(a + b)n}{p^{ℓ}}⌋ − ⌊\frac{an}{p^{ℓ}}⌋ − ⌊\frac{bn}{p^{ℓ}}⌋)

= −1 + ⌊\frac{(a + b)n}{p^{2}}⌋ − ⌊\frac{an}{p^{2}}⌋ − ⌊\frac{bn}{p^{2}}⌋

+ ⌊\frac{a_{2} + b_{2}}{3} + \frac{a + b}{3p}⌋ − ⌊\frac{a_{2}}{3} + \frac{a}{3p}⌋ − ⌊\frac{b_{2}}{3} + \frac{b}{3p}⌋ .

In this case, due to the estimations

p^{2} < b\frac{p}{3} < (a + b)n = (a + b)\frac{p + 1}{3} < \frac{12}{7}b\frac{p + 1}{3} < \frac{40}{21}p(p + 1) < 2p^{2}, for p > 20,

and

p^{2} < b\frac{p}{3} < bn < (a + b)n < 2p^{2}, for p > 20,

we have

⌊\frac{(a + b)n}{p^{2}}⌋ − ⌊\frac{an}{p^{2}}⌋ − ⌊\frac{bn}{p^{2}}⌋ = 1 − 0 − 1 = 0.

Moreover, we have a_{2} + b_{2} = 3, 3p < b < a + b ⩽ \frac{12}{7}b < \frac{120}{21}p < 6p, \frac{a_{2}}{3} = \frac{2}{3}, \frac{1}{3} < \frac{b}{9p} ⩽ \frac{a}{3p} ⩽ \frac{5b}{21p} < \frac{50}{63}, \frac{b_{2}}{3} = \frac{1}{3}, 1 < \frac{b}{3p} ⩽ \frac{10}{9}, so that

⌊\frac{a_{2} + b_{2}}{3} + \frac{a + b}{3p}⌋ − ⌊\frac{a_{2}}{3} + \frac{a}{3p}⌋ − ⌊\frac{b_{2}}{3} + \frac{b}{3p}⌋ = 2 − 1 − 1 = 0,

implying again that the p-adic valuation of \frac{1}{3n−1} \binom{an+bn}{an} equals −1 for our choice of p and n, as desired.

The last case to be discussed is (a, b) ∈ {(2, 1)} + (3ℤ)^{2} and 3a < b. Again, since we have already verified the claim for a, b ⩽ 1850, we may assume b ⩾ 1850. Here, we choose a prime p ≡ 2 (mod 3) strictly between \frac{5}{11}b and \frac{1}{2}b. Such a prime is guaranteed to exist by Lemma 6.1, because, due to our assumption, we have \frac{5}{11}b > 530. Furthermore, we choose n = (p + 1)/3. Since

(a + b)n < \frac{4}{3}b\frac{p + 1}{3} < \frac{44}{45}p(p + 1) < p^{2}, for p > 44,

for the p-adic valuation of \frac{1}{3n−1} \binom{an+bn}{an} there holds again (6.1). In the current case, we have furthermore a_{2} + b_{2} = 3, a + b ⩽ \frac{4}{3}b < \frac{44}{15}p < 3p, \frac{a_{2}}{3} = \frac{2}{3}, \frac{a}{3p} < \frac{b}{9p} < \frac{11}{45} < \frac{1}{3}, \frac{b_{2}}{3} = \frac{1}{3}, \frac{2}{3} < \frac{b}{3p} ⩽ \frac{11}{15}, and hence

⌊\frac{a_{2} + b_{2}}{3} + \frac{a + b}{3p}⌋ − ⌊\frac{a_{2}}{3} + \frac{a}{3p}⌋ − ⌊\frac{b_{2}}{3} + \frac{b}{3p}⌋ = 1 − 0 − 1 = 0,

implying also here that the p-adic valuation of \frac{1}{3n−1} \binom{an+bn}{an} equals −1 for our choice of p and n, as desired.

We have now covered all possible cases (in particular, by symmetry in a and b, we also covered the case (a, b) ∈ {(1, 2)} + (3ℤ)^{2}), and hence this concludes the proof of the theorem. □

7. Concluding remarks and open problems

In the proof of Theorem 2.1, assume that s is the smallest positive integer such that (a + b) | (p^{s} − 1). Then we obtain the stronger inequality

f(a, b) ⩽ \frac{p^{s} − 1}{a + b}.  (7.1)

It is easily seen that s | φ(a + b). However, such an upper bound is still likely much larger than the exact value of f(a, b) given by Sun [26]. For example, the inequality (7.1) gives

f(7, 36) ⩽ \frac{7^{6} − 1}{43} = 2736,

f(10, 192) ⩽ \frac{5^{25} − 1}{202} = 1475362494440362,

f(11, 100) ⩽ \frac{11^{6} − 1}{111} = 15960,

f(22, 200) ⩽ \frac{11^{6} − 1}{222} = 7980,
f(1999, 2011) ⩽ \frac{1999^{400} − 1}{4010} ≈ 5.272 × 10^{1316}.

It seems that Theorem 2.2 can be further generalised in the following way.

Conjecture 7.1. Let a and b be positive integers with a > b, and let α and β be integers. Furthermore, let p be a prime such that gcd(p, a) = 1. Then for each r = 0, 1, …, p − 1, there are infinitely many positive integers n such that

\binom{an + α}{bn + β} ≡ r (mod p).

In relation to Theorem 2.3, we propose the following two conjectures, the first one generalising Theorem 2.4.

Conjecture 7.2. For any odd prime p, there are no positive integers a > b such that

\binom{an}{bn} ≡ 0 (mod pn − 1)

for all n ⩾ 1.

Conjecture 7.3. For any positive integer m, there are positive integers a and b such that am > b and

\binom{amn}{bn} ≡ 0 (mod an − 1)

for all n ⩾ 1.

Note that the congruences (2.1)–(2.6) imply that Conjecture 7.3 is true for 1 ⩽ m ⩽ 5. It seems clear that, for each specific prime p, a proof of Conjecture 7.2 in the style

of the proof of Theorem 2.4 in Section 6 can be given. On the other hand, a proof for arbitrary p will likely require a new idea.

We end the paper with the following conjecture, strengthening the last part of Theorem 3.1.

Conjecture 7.4. For all positive integers n and non-negative integers k with 0 ⩽ k ⩽ 125n^{2} − 25n + 4, the coefficient of q^{k} of the polynomial

\frac{(1 − q)^{2}}{(1 − q^{10n−1})(1 − q^{15n−1})} [\begin{matrix}30n \\ 5n \end{matrix}]_{q}

is non-negative, except for k = 1 and k = 125n^{2} −25n+3, in which case the corresponding coefficient equals −1.

Note

Conjecture 7.2 was proved by Madjid Mirzavaziri and the second author. Conjecture 7.3 was proved by Madjid Mirzavaziri.

Acknowledgement

We thank Pierre Dusart for very helpful discussion concerning Lemma 6.1.

References

[1] G.E. Andrews, Catalan numbers, q-Catalan numbers and hypergeometric series, J. Combin. Theory Ser. A 44 (1987), 267–273.

[2] G.E. Andrews, On the difference of successive Gaussian polynomials, J. Statist. Plann. Inference 34 (1993), 19–22.

[3] G.E. Andrews, The Friedman–Joichi–Stanton monotonicity conjecture at primes, Unusual Applications of Number Theory (M. Nathanson, ed.), DIMACS Ser. Discrete Math. Theor. Comp. Sci., vol. 64, Amer. Math. Soc., Providence, R.I., 2004, pp. 9–15.

[4] G.E. Andrews, q-Catalan identities, in: The Legacy of Alladi Ramakrishnan in the Mathematical Sciences, Springer, New York, 2010, pp. 183–190.

[5] T.W. Apostol, Introduction to Analytic Number Theory, Undergraduate Texts in Mathematics, Springer-Verlag, New York–Heidelberg, 1976.

[6] C. Babbage, Demonstration of a theorem relating to prime numbers, Edinburgh Philos. J. 1 (1819), 46–49.

[7] K. S. Davis and W. A. Webb, Lucas’ theorem for prime powers, Europ. J. Combin. 11 (1990), 229–233.

[8] P.G.L. Dirichlet, Beweis des Satzes, daß jede unbegrenzte arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Factor sind, unendlich viele Primzahlen enthält, Abhand. Akad. Wiss. Berlin 48 (1837), 45–81.

[9] N. Fine, Binomial coefficients modulo a prime, Amer. Math. Monthly 54 (1947), 589–592.

[10] J. Fürlinger and J. Hofbauer, q-Catalan numbers, J. Combin. Theory Ser. A 40 (1985), 248–264.

[11] A.M. Garsia and J. Haglund, A proof of the q, t-Catalan positivity conjecture, Discrete Math. 256 (2002), 677–717.

[12] H.W. Gould, Bell and Catalan Numbers: Research Bibliography of Two Special Number Sequences, Combinatorial Research Institute, Morgantown, WV, 1978.

[13] A. Granville, Arithmetic properties of binomial coefficients, I, Binomial coefficients modulo prime powers, in: Organic Mathematics (Burnaby, BC, 1995), 253–276, CMS Conf. Proc., vol. 20, Amer. Math. Soc., Providence, RI, 1997, pp. 253–276.

[14] V.J.W. Guo, Proof of Sun’s conjecture on the divisibility of certain binomial sums, preprint,

    arχiv:1301.4877.

[15] V.J.W. Guo and J. Zeng, Factors of binomial sums from the Catalan triangle, J. Number Theory 130 (2010), 172–186.

[16] J. Haglund, Conjectured statistics for the q, t-Catalan numbers, Adv. Math. 175 (2003) 319–334.

[17] M. Haiman, t, q-Catalan numbers and the Hilbert scheme, Discrete Math. 193 (1998), 201–224.

[18] A. M. Legendre, Essai sur la théorie des nombres, 2^{e} ed., Courcier, Paris, 1808.

[19] K.S. McCurley, Explicit estimates for θ(x; 3, l) and ψ(x; 3, l), Math. Comp. 42 (1984), 287–296.

[20] R. Městrović, Wolstenholme’s theorem: its generalizations and extensions in the last hundred and fifty years (1862–2012), preprint, arχiv:1111.3057.

[21] M. Razpet, On divisibility of binomial coefficients, Discrete Math. 135 (1994), 377–379.

[22] V. Reiner, D. Stanton and D. White, The cyclic sieving phenomenon, J. Combin. Theory Ser. A 108 (2004), 17–50.

[23] D. Shanks, Solved and Unsolved Problems in Number Theory, 4th ed., New York, Chelsea, 1993, pp. 21 and 23–25.

[24] R.P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.

[25] Z.-W. Sun, Products and sums divisible by central binomial coefficients, Electron. J. Combin. 20(1) (2013), Article #P9, 14 pp.

[26] Z.-W. Sun, On divisibility of binomial coefficients, J. Austral. Math. Soc. 93 (2012), 189–201.

[27] M. Ulas and A. Schinzel, A note on Erdős–Straus and Erdős–Graham divisibility problems, (with an appendix by Andrzej Schinzel), Int J. Number Theory 9 (2013), 583–599.

[28] J. Wolstenholme, On certain properties of prime numbers, Quart. J. Pure Appl. Math. 5 (1862), 35–39.