Primes and Perfect Powers in the Catalan Triangle

Nathaniel Benjamin Department of Mathematics

Iowa State University Carver Hall, 411 Morrill Road

Ames, IA 50011 USA

  nbenj582@iastate.edu

Eugene Fiorini Department of Mathematics

Muhlenberg College 2400 Chew Street Allentown, PA 18104

USA

eugenefiorini@muhlenberg.edu

Eric Jovinelly Department of Mathematics

Notre Dame University

255 Hurley Notre Dame, IN 46556

USA

    ejovinel@nd.edu

Grant Fickes Department of Mathematics Kutztown University of Pennsylvania 15200 Kutztown Road Kutztown, PA 19530 USA

                                gfick710@live.kutztown.edu

Edgar Jaramillo Rodriguez Department of Mathematics University of California, Davis 1 Shields Avenue Davis, CA 95616 USA

                                 edgarjr@math.ucdavis.edu

Tony W. H. Wong Department of Mathematics Kutztown University of Pennsylvania 15200 Kutztown Road Kutztown, PA 19530 USA

                                    wong@kutztown.edu

Abstract

The Catalan triangle is an infinite lower-triangular matrix that generalizes the Catalan numbers. The entries of the Catalan triangle, denoted by c_{n,k}, count the number of shortest lattice paths from (0, 0) to (n, k) that do not go above the main diagonal. This paper studies the occurrence of primes and perfect powers in the Catalan triangle. We prove that no prime powers except 2, 5, 9, and 27 appear in the Catalan triangle when k ≥ 2. We further prove that c_{n,k} are not perfect semiprime powers when k ≥ 3. Finally, by assuming the abc conjecture, we prove that aside from perfect squares when k = 2, there are at most finitely many perfect powers among c_{n,k} when k ≥ 2.

1 Introduction

A well-known theorem, first proved by Sylvester [15] and again by Erdős [2], states that for all n, k ∈ ℕ satisfying 2 ≤ k ≤ n, there is a prime p > k such that p divides

(n + k)(n + k − 1)(n + k − 2) ⋯ (n + 1).

Erdős [3] later applied Sylvester’s theorem to prove that if 4 ≤ k ≤ n, then \binom{n+k}{k} is never a perfect power. In other words, the Diophantine equation

\binom{n + k}{k} = x^{ℓ} with x ≥ 1, ℓ ≥ 2, and k ≤ n  (1)

has no positive integer solutions for k ≥ 4. Győry [6] extended Erdős’s result to k ≥ 2, proving the only positive integer solutions to equation (1) occur at \binom{50}{3} = 140^{2} or when k = ℓ = 2. These results motivate us to ask the same questions about the Catalan numbers and the Catalan triangle.

Let n ∈ ℕ ∪ {0}. The Catalan numbers, defined as

C_{n} = \frac{1}{n + 1}\binom{2n}{n},

form an integer sequence with rich combinatorial implications. They count the number of Dyck paths, the number of non-crossing partitions, the number of full binary trees, and the number of ways to insert parentheses, to name only a few examples. The number theoretic aspect of Catalan numbers is equally interesting, and numerous researches have been conducted on various divisibility and modulo properties of the Catalan numbers and their derivatives [8, 9, 10, 16].

The question of whether Catalan numbers can be perfect powers was answered negatively by Checcoli and D’Adderio [1]. Their proof was a simple application of a strong version of Bertrand’s postulate by Ramanujan [12], and it is included here for completeness.

Theorem 1 ([1]). For all n ∈ ℕ such that n ≥ 2, the n-th Catalan number C_{n} is never a perfect power.

Proof. First, note that C_{2} = 2, C_{3} = 5, C_{4} = 14, and C_{5} = 42, so none of these are perfect powers. When n ≥ 6, by Ramanujan’s theorem [12], there are at least two primes in the open interval (n, 2n). As a result, there is a least one prime p in the interval [n + 2, 2n). Therefore,

p || C_{n} = \frac{2n(2n − 1)(2n − 2) ⋯ (n + 2)}{n!},

i.e., p | C_{n} but p^{2} ∤ C_{n}. Hence, C_{n} cannot be a perfect power.

The Catalan numbers can be generalized to the Catalan triangle. For all n, k ∈ ℕ ∪ {0} satisfying n ≥ k, the entry c_{n,k} in the Catalan triangle is given by the number of Dyck paths starting from the upper-left vertex (0, 0) to the vertex (n, k) on the n-th row and the k-th column. Here, a Dyck path is a lattice path consisting of downward or rightward steps without visiting the region above the diagonal n = k. The first few rows in the Catalan triangle are depicted below.

1 1 1 1 2 2 1 3 5 5 1 4 9 14 14 1 5 14 28 42 42 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ...  (2)

Note that the rows and columns are indexed by ℕ ∪ {0}, so the topmost row and the leftmost column are referred to as the zeroth row and the zeroth column respectively. The entry on the n-th row and the k-th column is c_{n,k}. In particular, the diagonal entries are c_{n,n} = C_{n}. The general formula for the entries of the Catalan triangle is given by

c_{n,k} = \frac{n − k + 1}{n + 1}\binom{n + k}{k} = \frac{(n + k)(n + k − 1)(n + k − 2) ⋯ (n + 2)(n − k + 1)}{k!}, (3)

and for all 1 ≤ k < n, they satisfy the recursion relation

c_{n,k} = c_{n−1,k} + c_{n,k−1}.  (4)

Observe that the first column of the Catalan triangle in (2) is the sequence (c_{n,1})_{n≥1}, where c_{n,1} = \frac{n−1+1}{n+1} \binom{n+1}{1} = n for all n ∈ ℕ. As a result, every positive integer appears at least once in the Catalan triangle. Nevertheless, not all positive integers appear more than once in the Catalan triangle. The sequence of positive integers that appear uniquely in the Catalan triangle was added by the authors to the On-Line Encyclopedia of Integer Sequences (OEIS), listed as \underline{A275481} [14], and its complement is listed as \underline{A275586} [14].

The algorithm to search for positive integers that appear uniquely in the Catalan triangle is given in the aforementioned OEIS entries, and it relies on the following lemma.

Lemma 2. For all n, k ∈ ℕ such that n ≥ k, the following statements hold.

• For all n′ ∈ ℕ such that n < n′, c_{n,k} < c_{n′,k}.

• For all k′ ∈ ℕ such that k < k′ ≤ n, c_{n,k} ≤ c_{n,k′}, where equality holds if and only if n = k + 1.

• c_{n,k} < c_{n+1,k+1}.

Proof. Since every entry in the Catalan triangle is positive by definition, from the recursion relation in equation (4), we have

c_{n,k} < c_{n,k} + c_{n+1,k−1} = c_{n+1,k}.

Hence, for any fixed k ∈ ℕ, c_{n,k} strictly increases with n ≥ k. This proves the first statement. Also, when n > k + 1,

c_{n,k} < c_{n−1,k+1} + c_{n,k} = c_{n,k+1}.

Together with the observation that

c_{k+1,k} = \frac{2}{k + 2}\binom{2k + 1}{k} = \frac{2k + 2}{(k + 2)(k + 1)} · \frac{(2k + 1)!}{k!(k + 1)!} = \frac{1}{k + 2}\binom{2k + 2}{k + 1} = c_{k+1,k+1},

the second statement follows. Finally, the third statement is an immediate consequence of the prior two.

By algorithmically computing the sequence \underline{A275481}, we observe that most perfect powers appear uniquely in the Catalan triangle. In other words, c_{n,k} are rarely perfect powers when 2 ≤ k ≤ n. We prove in Section 2 that for 2 ≤ k ≤ n, c_{n,k} cannot be prime nor a perfect prime power except when c_{n,k} = 2, 5, 9, or 27. Furthermore, we prove that for 3 ≤ k ≤ n, c_{n,k} cannot be a perfect power of semiprimes. We prove in Section 3 there are infinitely many perfect squares in the Catalan triangle when k = 2. By assuming the abc conjecture, we then show the scarcity of squarefull numbers among c_{n,k} when k ≥ 4, thus proving that, other than those c_{n,2} that are perfect squares, there are at most finitely many perfect powers when k ≥ 2. A positive integer m is squarefull if for all primes p | m, we also have p^{2} | m. In other words, no exponent in the prime power factorization of m is 1. A squarefull number is also called powerful in the literature. Our proof utilizes a strong result of Granville [5] related to the abc conjecture.

2 Prime powers and perfect semiprime powers in the Catalan triangle

We begin with a simple result on the occurrence of primes in the Catalan triangle.

Lemma 3. For all n, k ∈ ℕ such that 2 ≤ k ≤ n, if c_{n,k} is a prime, then c_{n,k} = 2 or 5.

Proof. From the Catalan triangle (2), we observe that the statement is true for n ≤ 4. Hence, it suffices to prove that c_{n,k} is composite when k ≥ 2 and n ≥ max{k, 5}.

We will proceed by induction on k. When k = 2, by equation (3), c_{n,2} = \frac{(n+2)(n−1)}{2}, which is composite since both n + 2 and n − 1 are greater than 2.

Suppose that for some k ≥ 2, c_{n,k} is composite for all n ≥ max{k, 5}. For all n ≥ k + 1,

c_{n,k+1} = \frac{n − (k + 1) + 1}{n + 1}\binom{n + k + 1}{k + 1}

= \frac{(n − k)(n + k + 1)}{(n + 1)(k + 1)}\binom{n + k}{k}

= \frac{(n − k)(n + k + 1)}{(k + 1)(n − k + 1)}c_{n,k}.

Let \frac{(n−k)(n+k+1)}{(k+1)(n−k+1)} = \frac{a}{b}, where a, b ∈ ℕ such that gcd(a, b) = 1. Since c_{n,k+1} is an integer, we have b | c_{n,k}. In other words, c_{n,k+1} is the product of two integers a and \frac{c_{n,k}}{b}. If b = 1, then c_{n,k+1} = a · c_{n,k} is composite by the induction hypothesis. If b > 1, then a > 1 since a ≥ b by Lemma 2. Also, \frac{c_{n,k}}{b} > 1; otherwise, c_{n,k} = b ≤ (k + 1)(n − k + 1), which implies

k + 1 ≥ \frac{(n + k)(n + k − 1)(n + k − 2) ⋯ (n + 2)}{k!}
(k + 1)! ≥ (n + k)(n + k − 1)(n + k − 2) ⋯ (n + 2)
≥ (k + 5)(k + 4)(k + 3) ⋯ 7
≥ 7 · 6 · 5 · 4 · (k + 1)k(k − 1) ⋯ 7
> (k + 1)k(k − 1) ⋯ 7 · 6 · 5 · 4 · (3 · 2 · 1) = (k + 1)!,

a contradiction. Therefore, c_{n,k+1} is composite.

To prove the uniqueness of prime powers in the Catalan triangle, we will use the following lemma, which is a moderate strengthening of Sylvester’s theorem [15] based on Faulkner’s results [4].

Lemma 4. For all n, k ∈ ℕ such that 2 ≤ k ≤ n, (n + k)(n + k − 1) ⋯ (n + 2) has a prime factor q ≥ k + 1 except when (n, k) = (6, 3) or (2^{α} − 2, 2), where α ≥ 2 is an integer.

Proof. For convenience, let N = n + k, so that it suffices to prove the following statement.

If k ≥ 2 and N ≥ 2k, then N(N − 1) ⋯ (N − k + 2) has a prime factor q ≥ k + 1 except when (N, k) = (9, 3) or (2^{α}, 2), where α ≥ 2 is an integer.

By Faulkner’s result [4], if N ≥ 2K, then \binom{N}{K}, or equivalently, N(N − 1) ⋯ (N − K + 1), has a prime factor q ≥ \frac{7}{5}K. Substituting K = k − 1, if N ≥ 2(k − 1), then

N(N − 1) ⋯ (N − k + 2)

has a prime factor q ≥ \frac{7}{5}(k − 1). Note that \frac{7}{5}(k − 1) ≥ k + 1 if and only if k ≥ 6, so our lemma is proved for k ≥ 6.

When k = 2, then N does not have a prime factor q ≥ 3 if and only if N = 2^{α} for some integer α ≥ 2.

When k = 3, if N(N − 1) does not have a prime factor q ≥ 4, then N(N − 1) only has factors 2 and 3, which happens only when one of N and N − 1 is a power of 2 and the other is a power of 3. Also, as N ≥ 2k, both numbers are at least 5. Mihăilescu’s theorem [11] implies that the only pair of consecutive integers (N, N − 1) that satisfies these conditions is (9, 8), meaning (N, k) = (9, 3).

When k = 4, it follows directly from the case when k = 3, since any prime factor q ≥ 4 is at least 5.

When k = 5, if ∏_{i=0}^{3}(N − i) does not have a prime factor q ≥ 6, then its only prime factors are 2, 3, and 5. Let the prime factorization of N − i be 2^{α_{i}}3^{β_{i}}5^{γ_{i}}, where i = 0, 1, 2, 3. Note that exactly two α_{i}’s are positive, with one of them equal to 1. Note also that at most two β_{i}’s are positive, and if two are positive, then one of them is 1. Finally, at most one γ_{i} is positive. As N ≥ 2k, all four numbers N, N − 1, N − 2, and N − 3 are at least 7. Since there are at most 5 indices that are positive, we must have three of those four numbers being divisible by a power of 2, a power of 3, and a power of 5 respectively. Finally, the remaining number is at most 2 × 3 = 6, which is a contradiction.

We are now ready to prove the following two theorems, which are the main results of this section on the occurrence of prime powers and semiprime powers in the Catalan triangle.

Theorem 5. The only positive integer solutions to the Diophantine equation

c_{n,k} = p^{ℓ}

with 2 ≤ k ≤ n, ℓ ≥ 1, and prime p are

(n, k, p^{ℓ}) = (2, 2, 2), (3, 2, 5), (3, 3, 5), (4, 2, 9), or (7, 2, 27).

Proof. First, consider the case k = 2. Suppose that

c_{n,2} = \frac{(n + 2)(n − 1)}{2} = p^{ℓ}

for some n, p, ℓ ∈ ℕ such that n ≥ 2 and p is a prime. If n − 1 = 1 or 2, then

(n, k, p^{ℓ}) = (2, 2, 2) or (3, 2, 5)

respectively. If n−1 > 2, then p divides n−1 and n+2, implying that p | (n+2)−(n−1) = 3, i.e., p = 3.

Let n − 1 = 3m for some m ∈ ℕ. Then

3^{ℓ} = \frac{(3m + 3)(3m)}{2} = 9 · \frac{(m + 1)m}{2}.

If m > 2, then 3 divides both m and m + 1, which is impossible. Hence, m = 1 or 2, which gives (n, k, p^{ℓ}) = (4, 2, 9) or (7, 2, 27) respectively.

Next, consider the case k > 2. If c_{n,k} is a prime, by Lemma 3, c_{n,k} = 2 or 5. From the Catalan triangle (2), (n, k, p^{ℓ}) = (3, 3, 5) is a solution. Also, from Lemma 2, we know that (n, k, p^{ℓ}) = (3, 3, 5) is the only solution when k > 2. If c_{n,k} is a perfect prime power, by Theorem 1, we have n ≥ k + 1. Furthermore, we can assume that (n, k) ≠ (6, 3) since c_{6,3} = 48 is not a perfect prime power.

Let S = {n + k, n + k − 1, …, n + 2}. By Lemma 4, there exists a prime q ≥ k + 1 such that q | ∏_{s∈S} s. As q is relatively prime with k!, which is the denominator of equation (3), in order for c_{n,k} = p^{ℓ}, we have p = q. Also, since the difference between the largest and the smallest elements in S is k − 2 < p, there is a unique element s ∈ S such that p | s, and ∏_{s′∈S\{s}} s′ must divide k!. This implies that

k! ≥ ∏_{s′∈S\{s}} s′
≥ (n + k − 1)(n + k − 2)(n + k − 3) ⋯ (n + 2)
≥ 2k(2k − 1)(2k − 2) ⋯ (k + 3)
> 2k(k − 1)(k − 2) ⋯ (3) = k!,

which is a contradiction.

Theorem 6. There are no positive integer solutions to the Diophantine equation

c_{n,k} = (pq)^{ℓ}

with 3 ≤ k ≤ n, ℓ ≥ 2, and distinct primes p and q.

Proof. First, consider the case k = 3. Suppose that

c_{n,3} = \frac{(n + 3)(n + 2)(n − 2)}{6} = (pq)^{ℓ}

for some n, p, ℓ ∈ ℕ such that n ≥ 3, ℓ ≥ 2, and p and q are distinct primes. By computer exhaustion, we check that there are no integer solutions for n ≤ 122. Consider n > 122. Since n + 3 and n + 2 are greater than 6 and are relatively prime, assume without loss of generality that p | (n + 3) and q | (n + 2). As gcd(n + 3, n − 2) | 5 and gcd(n + 2, n − 2) | 4, we have

(n + 3, n + 2, n − 2) = (αp^{ℓ}, βq^{ℓ}, γ), (α5^{ℓ_{1}}, βq^{ℓ}, γ5^{ℓ−ℓ_{1}}),
(αp^{ℓ}, β2^{ℓ_{2}}, γ2^{ℓ−ℓ_{2}}), or (α5^{ℓ_{1}}, β2^{ℓ_{2}}, γ5^{ℓ−ℓ_{1}}2^{ℓ−ℓ_{2}}),

where α, β, γ ∈ ℕ, αβγ = 6, ℓ_{1} = 1 or ℓ − 1, and ℓ_{2} = 1, 2, ℓ − 2, or ℓ − 1. Note that

min{αp^{ℓ}, βq^{ℓ}, γ} ≤ 6,
min{α5^{ℓ_{1}}, βq^{ℓ}, γ5^{ℓ−ℓ_{1}}} ≤ 6 · 5 = 30,
min{αp^{ℓ}, β2^{ℓ_{2}}, γ2^{ℓ−ℓ_{2}}} ≤ 6 · 4 = 24, and
min{α5^{ℓ_{1}}, β2^{ℓ_{2}}, γ5^{ℓ−ℓ_{1}}2^{ℓ−ℓ_{2}}} ≤ 6 · 5 · 4 = 120.

All these violate the condition that n > 122. Hence, no positive integer solutions exist when k = 3.

Next, consider the case k > 3. Without loss of generality, let p > q. By Lemma 4, it follows that p > k. Let T = {n + k, n + k − 1, …, n + 2, n − k + 1}. If p^{ℓ} | t_{0} for some t_{0} ∈ T, then

(p^{ℓ} − 1)(p^{ℓ} − 2) ⋯ (p^{ℓ} − k + 2)(p^{ℓ} − 2k + 1) ≤ ∏_{t∈T \\{t_{0}\}} t = \frac{p^{ℓ}q^{ℓ}k!}{t_{0}} ≤ q^{ℓ} · k!.

Since q < p and k < p, we have q^{ℓ} ≤ (p − 1)^{ℓ} < p^{ℓ} − 2k + 1 and k^{2} ≤ (p − 1)^{2} < p^{ℓ} − 2k + 1. As a result,

k^{2k−4} < (p^{ℓ} − 1)(p^{ℓ} − 2) ⋯ (p^{ℓ} − k + 2) < k!,

which is a contradiction since k ≥ 4. Note that the difference between the largest and the smallest elements in T is 2k − 1 < 2p, and the difference between the largest and the second smallest elements in T is k − 2 < p. So we must have p^{ℓ_{1}} || (n − k + 1) and p^{ℓ−ℓ_{1}} || t_{1} for a unique t_{1} ∈ T \ {n − k + 1}, where ℓ_{1} = 1 or ℓ − 1.

When ℓ > 2, depending on ℓ_{1} = 1 or ℓ − 1, we have either

(p^{ℓ−1} − 1)(p^{ℓ−1} − 2) ⋯ (p^{ℓ−1} − k + 2)(p^{ℓ−1} − 2k + 1) ≤ ∏_{t∈T \\{t_{1}\}} t = \frac{p^{ℓ}q^{ℓ}k!}{t_{1}} ≤ pq^{ℓ} · k!

or

(p^{ℓ−1} + 2k − 1)(p^{ℓ−1} + 2k − 2) ⋯ (p^{ℓ−1} + k − 1) ≤ pq^{ℓ} · k!.

In either case, since q^{ℓ−1} ≤ p^{ℓ−1} − 2k + 1, we always have

(p^{ℓ−1} − 1)(p^{ℓ−1} − 2) ⋯ (p^{ℓ−1} − k + 2) ≤ pq · k!.

Furthermore, as pq < p(p − 1) < p^{ℓ−1} − k + 2, p^{ℓ−1} − 1 ≥ 5^{2} − 1 = 4!, and p^{ℓ−1} − 2 > k, we have

4! · k(k − 1) ⋯ 5 < 4! · (p^{ℓ−1} − 2)(p^{ℓ−1} − 3) ⋯ (p^{ℓ−1} − k + 3) < k!,

a contradiction. When ℓ = 2, note that n ≥ p + k − 1 and k < p < 2k since p || (n − k + 1) and p || t_{1}. Hence, if k ≥ 6, then

pq^{2} · k! ≥ (n + k)(n + k − 1) ⋯ (n + 2)

≥ (p + 2k − 1)(p + 2k − 2) ⋯ (p + k + 1)

> (p + 2k − 1)(p + 2k − 2) ⋯ (p + k + 4) (\frac{3p}{2})^{3}

> \frac{27}{8}(3k)(3k − 1) ⋯ (2k + 5) · pq^{2}

> \frac{27}{8}(3k)(3(k − 1))(k − 2)(k − 3) ⋯ 5 · pq^{2} > k! · pq^{2},

a contradiction. If k ≤ 5, then p ≤ 7, and q ≤ 5. As a result, c_{n,k} ≤ (7 · 5)^{2} = 1225. Since c_{12,4} = 1260 and c_{10,5} = 1638, by Lemma 2, we only need to consider n < 12 when k = 4 and n < 10 when k = 5. By computer exhaustion, c_{n,k} are never perfect squares for n < 12 when k = 4 and n < 10 when k = 53, which completes our proof.

3 Scarcity of perfect powers and squarefull numbers

The previous section showed that there are only two perfect prime powers in the Catalan triangle when k = 2, and no perfect prime powers nor perfect semiprime powers when k ≥ 3. This section addresses the general question of the occurrence of perfect powers in the Catalan triangle. One of the authors constructed an algorithm to search for perfect powers that appear nonuniquely in the Catalan triangle. The sequence, together with the algorithm, is listed on the OEIS as \underline{A317027} [14]. Note that \underline{A317027} is an infinite sequence since there are infinitely many perfect squares in the Catalan triangle when k = 2, due to the following theorem.

Theorem 7. The Diophantine equation

c_{n,k} = x^{ℓ}

has infinitely many integer solutions with x ≥ 1, 2 = k ≤ n, and ℓ = 2.

Proof. For any positive integer solution pair (X_{0}, Y_{0}) to Pell’s equation

X^{2} − 2Y^{2} = 1,

let n = 3X_{0}^{2} − 2. Note that n = 6Y_{0}^{2} + 1. Hence,

c_{n,2} = \frac{(n + 2)(n − 1)}{2} = \frac{3X_{0}^{2} · 6Y_{0}^{2}}{2} = (3X_{0}Y_{0})^{2}.

Since Pell’s equation has infinitely many integer solutions, the proof is complete.

The conditions that k = 2 and ℓ = 2 in Theorem 7 are both essential. If either condition is relaxed, then the results change drastically, as shown in Theorem 8 and Corollary 11.

Theorem 8. There are at most finitely many positive integer solutions to the Diophantine equation

c_{n,k} = x^{ℓ}

with

(a) x ≥ 1, 3 = k ≤ n and ℓ = 2; or

(b) x ≥ 1, 2 ≤ k ≤ 3, k ≤ n, and ℓ ≥ 3.

Proof. (a) When 3 = k ≤ n and ℓ = 2, the equation c_{n,k} = x^{ℓ} can be rewritten as

(n + 3)(n + 2)(n − 2) = 6x^{2}.

This equation defines a genus 1 curve, and hence by Siegel’s theorem on integral points [13], there are at most finitely many positive integer solutions for n on this elliptic curve.

(b) First, consider k = 2. Assume that c_{n,2} = x^{ℓ} for some positive integers n ≥ 2, x, and

ℓ ≥ 3. Then

(n + 2)(n − 1) = 2x^{ℓ}.  (5)

Let g = gcd(n + 2, n − 1). Then clearly g | 3. Equation (5) implies that \frac{n+2}{g} = aX^{ℓ} and \frac{n−1}{g} = bY^{ℓ} for some a, b, X, Y ∈ ℕ, where gcd(a, b) = 1 and ab = 2g^{ℓ−2}. Hence,

aX^{ℓ} − bY^{ℓ} = \frac{3}{g}.  (6)

Let 𝒮 = {s ∈ ℤ : p is a prime and p | s ⇒ p ∈ {2, 3}}, i.e., 𝒮 is the set of integers not divisible by primes outside \{2, 3\}. Since a, b, \frac{3}{g} ∈ 𝒮, Győry and Pintér [7] proved that there are at most finitely many integer solutions (X^{ℓ}, Y^{ℓ}) with ℓ ≥ 3 for the Thue equation (6). As a result, there are at most finitely many positive integer solutions for c_{n,2} = x^{ℓ}.

Next, consider k = 3. Assume that c_{n,3} = x^{ℓ} for some positive integers n ≥ 3, x, and ℓ ≥ 3. Then

(n + 3)(n + 2)(n − 2) = 6x^{ℓ}.  (7)

Let g_{1} = gcd(n+3, n−2) and g_{2} = gcd(n+2, n−2). Then clearly g_{1} | 5 and g_{2} | 4. Equation (7) implies that \frac{n+3}{g_{1}} = aX^{ℓ}, \frac{n+2}{g_{2}} = bY^{ℓ}, and \frac{n−2}{g_{1}g_{2}} = cZ^{ℓ} for some a, b, c, X, Y, Z ∈ ℕ, where a, b, c are pairwise relatively prime and abc | 6g_{1}^{ℓ−2}2^{ℓ−2}. Hence,

g_{1}aX^{ℓ} − g_{2}bY^{ℓ} = 1.  (8)

Let 𝒯 = {t ∈ ℤ : p is a prime and p | t ⇒ p ∈ {2, 3, 5}}, i.e., 𝒯 is the set of integers not divisible by primes outside {2, 3, 5}. Since g_{1}a, g_{2}b, 1 ∈ 𝒯 , again by Győry and Pintér’s results [7], there are at most finitely many integer solutions (X^{ℓ}, Y^{ℓ}) with ℓ ≥ 3 for the Thue equation (8). As a result, there are at most finitely many positive integer solutions for c_{n,3} = x^{ℓ}.

To prove that there are at most finitely many perfect powers in the Catalan triangle with k ≥ 4, we expand our consideration to squarefull numbers. Lemma 4 implies that when 4 ≤ k ≤ n < 2k, c_{n,k} is not squarefull, as c_{n,k} is divisible by a prime q ≥ k + 1 but not divisible by q^{2}. Assuming the abc conjecture, we can further show that there are at most finitely many perfect powers in the Catalan triangle with k ≥ 4.

The abc conjecture. For all ϵ > 0, there exists M > 0 such that for all relatively prime positive integers a, b, c that satisfy a + b = c,

c^{1−ϵ} ≤ M ∏_{\begin{matrix}p is prime \\ p|abc \end{matrix}} p.

Granville [5] applied the abc conjecture to prove the following theorem.

Theorem 9 ([5]). For all 3 ≤ k ≤ n, let a_{n,k} = ∏_{p||\binom{n+k}{k}} p. The abc conjecture implies that

a_{n,k} >>_{ϵ} \binom{n + k}{k}^{1−2/k−ϵ}.

In other words, for all ϵ > 0, there exist M, n_{0} > 0 such that for all n ≥ n_{0},

a_{n,k} ≥ M\binom{n + k}{k}^{1−2/k−ϵ}.

Note that the above theorem is uniform in k. Now, we use Granville’s result to prove the following theorem.

Theorem 10. The abc conjecture implies that there are at most finitely many squarefull c_{n,k} for 4 ≤ k ≤ n.

Proof. First, consider k = 4. The proof technique for the case k = 4 is similar to that in the proof of Proposition 3 in Granville’s paper [5]. Suppose that c_{n,4} is squarefull. Then for all primes p > 4 such that p | (n + 4)(n + 3)(n + 2)(n − 3), we also have

p^{2} | (n + 4)(n + 3)(n + 2)(n − 3).

Let n − 3 = τ_{1}η_{1}, and n + i = τ_{i}η_{i} for each i = 2, 3, 4, where τ_{i} is squarefree, η_{i} is squarefull, and gcd(τ_{i}, η_{i}) = 1 for all i = 1, 2, 3, 4. Since (n + 4) − (n − 3) = 7, by the assumptions, all prime factors of τ_{i} are at most 7. Hence,

∏_{\begin{matrix}p is prime \\ p|τ_{1}τ_{2}τ_{3}τ_{4} \end{matrix}} p ≤ 2 × 3 × 5 × 7 = 210.

Let ϵ = \frac{1}{5}. Applying the abc conjecture, there exists M > 0 such that if a = (n+4)(n+2), b = 1, and c = (n + 3)^{2}, then

(n + 3)^{2(1−ϵ)} ≤ M ∏_{\begin{matrix}p is prime \\ p|(n+4)(n+2)(n+3)^{2} \end{matrix}} p

= M (( ∏_{\begin{matrix}p is prime \\ p|τ_{2}τ_{3}τ_{4} \end{matrix}} p)^{\frac{1}{2}} ∏_{\begin{matrix}p is prime \\ p|η_{2}η_{3}η_{4} \end{matrix}} p) ( ∏_{\begin{matrix}p is prime \\ p|τ_{2}τ_{3}τ_{4} \end{matrix}} p)^{\frac{1}{2}}

≤ M((n + 4)(n + 3)(n + 2))^{\frac{1}{2}} \sqrt{210} < M\sqrt{210}(n + 4)^{\frac{3}{2}} , which is a contradiction for sufficiently large n.

Next, consider k ≥ 5. For all 5 ≤ k ≤ n, let b_{n,k} = ∏_{p||c_{n,k}} p. By Theorem 9, the abc conjecture implies that when ϵ = \frac{1}{10}, there exist M, n_{0} > 0 such that for all n ≥ n_{0},

a_{n,k} ≥ M\binom{n+k}{k}^{1−2/k−1/10}. Hence,

b_{n,k} ≥ \frac{a_{n,k}}{(n + 1)(n − k + 1)} ≥ \frac{M\binom{n+k}{k}^{1−2/5−1/10}}{(n + 1)(n − k + 1)} ≥ \frac{M\binom{n+5}{5}^{1/2}}{(n + 1)(n − k + 1)} > \frac{Mn^{5/2}}{5!n^{2}} = \frac{M}{120}n^{1/2}.

Thus b_{n,k} > 1 whenever n ≥ max\{n_{0}, (\frac{120}{M})^{2}\}, in which case c_{n,k} is not squarefull.

Since a perfect power is squarefull, we immediately have the following corollary.

Corollary 11. The abc conjecture implies that there are at most finitely many positive integer solutions to the Diophantine equation

c_{n,k} = x^{ℓ}

with x ≥ 1, 4 ≤ k ≤ n, and ℓ ≥ 2.

Theorem 7 showed that there are infinitely many perfect squares in the Catalan triangle when k = 2. Furthermore, we have shown through Theorem 8 and Corollary 11 that, other than those perfect squares given in Theorem 7, there are at most finitely many perfect powers when k ≥ 2, provided the abc conjecture holds. However, by observing the list of perfect powers in the sequence \underline{A275481}, we conclude our paper with the following conjecture.

Conjecture 12. Consider the Diophantine equation

c_{n,k} = x^{ℓ}.

(a) When x ≥ 1, 2 = k ≤ n, and ℓ ≥ 3, the only solutions are (n, x^{ℓ}) = (7, 27) and (126, 8000).

(b) When x ≥ 1, 3 ≤ k ≤ n and ℓ ≥ 2, there are no positive integer solutions.

These results are based upon work supported by the National Science Foundation under the grant number DMS-1560019, as well as the Kutztown University Bringing Experiences About Research in Summer (KU BEARS) and the Muhlenberg College Summer Research Program.

References

[1] S. Checcoli and M. D’Adderio, Perfect powers in Catalan and Narayana numbers,

    preprint, 2013. Available at https://arxiv.org/abs/1306.5929.

[2] P. Erdős, A theorem of Sylvester and Schur, J. London Math. Soc. 9 (1934), 282–288.

[3] P. Erdős, On a diophantine equation, J. London Math. Soc. 26 (1951), 176–178.

[4] M. Faulkner, On a theorem of Sylvester and Schur, J. London Math. Soc. 41 (1966), 107–110.

[5] A. Granville, On the scarcity of powerful binomial coefficients, Mathematika 46 (1999), 397–410.

[6] K. Győry, On the diophantine equation \binom{n}{k} = x^{l}, Acta Arith. 80 (1997), 289–295.

[7] K. Győry and Á. Pintér, Binomial Thue equations, ternary equations and power values of polynomials, J. Math. Sci. (N.Y.) 180 (2012), 569–580.

[8] M. Konvalinka, Divisibility of generalized Catalan numbers, J. Combin. Theory Ser. A 114 (2007), 1089–1100.

[9] T. Koshy and Z. Gao, Some divisibility properties of Catalan numbers, Math. Gaz. 95 (2011), 96–102.

[10] S. Liu, and J. C.-C. Yeh, Catalan numbers modulo 2^{k}, J. Integer Seq. 13 (2010), Article 10.5.4.

[11] P. Mihăilescu, Primary cyclotomic units and a proof of Catalan’s conjecture, J. Reine Angew. Math. 572 (2004), 167–195.

[12] S. Ramanujan, A proof of Bertrand’s postulate, J. Indian Math. Soc. 11 (1919), 181– 182.

[13] C. Siegel, Über einige Anwendungen diophantischer approximationen, Abh. Preuß, Akad. Wissen. Phys.-Math. Klasse (1929) = Ges. Abh. Bd. I, Springer-Verlag, 1966, pp. 209–266.

[14] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, https://oeis.org.

[15] J. J. Sylvester, On arithmetical series, Messenger Math. 21 (1892), 1–19, 87–120. Reprinted in Collected Mathematical Papers 4 (1912), 687–731.

[16] G. Xin and J.-F. Xu, A short approach to Catalan numbers modulo 2^{r}, Electron. J. Combin. 18 (2011), #P177.

2010 Mathematics Subject Classification: Primary 11D72; Secondary 11B65, 11A51. Keywords: Catalan triangle, squarefull number, prime power, semiprime power, perfect power, Sylvester’s theorem, Győry and Pintér’s theorem.

(Concerned with sequences \underline{A275481}, \underline{A275586}, and \underline{A317027}.) Received January 30 2019; revised versions received October 18 2019; October 31 2019. Published in Journal of Integer Sequences, November 8 2019. Return to Journal of Integer Sequences home page.