THE IRREDUCIBILITY OF THE BESSEL POLYNOMIALS

Michael Filaseta*and Ognian Trifonov

Dedicated to the memory of Emil Grosswald

1. Introduction

In 1951, Emil Grosswald [7] began investigating the irreducibility of the Bessel Polynomials

y_{n}(x) = ∑_{j=0}^{n} \frac{(n + j)!}{2^{j}(n − j)!j!}x^{j}.

He conjectured (cf. [8],[9]) that y_{n}(x) is irreducible over the rationals for all positive integers n. In this paper, we resolve this conjecture and establish the following generalization.

Theorem. Let n be a positive integer, and let a_{0}, a_{1}, …, a_{n} be arbitrary integers with |a_{0}| = |a_{n}| = 1. Then

∑_{j=0}^{n} a_{j} \frac{(n + j)!}{2^{j}(n − j)!j!}x^{j}

is irreducible over the rationals.

The above theorem was established in the case that n is sufficiently large, say n ≥ n_{0}, by the first author in [4]. He also conjectured there that the above general theorem holds. Although the method in [4] gives an effectively computable value for n_{0}, a direct application of the methods there does not allow one to establish even that n_{0} ≤ 10^{10^{1000}}. Nevertheless, our approach in this paper is quite similar to that given in [4] and is based on refining the estimates made there. Related work has been done by I. Schur [11], the first author [2,3,5], and S. Graham and the first author [6].

2. Preliminaries

As in previous approaches, we define

z_{n}(x) = x^{n}y_{n}(2/x) = ∑_{j=0}^{n} \frac{(2n − j)!}{j!(n − j)!}x^{j} = ∑_{j=0}^{n} \frac{(n + j)!}{j!(n − j)!}x^{n−j}.

Typeset by AMS-TEX

*The first author was supported by NSA Grant MDA904-97-1-0035.

The polynomial F (x) given in the theorem is easily seen to be irreducible if and only if

(1)  f(x) = x^{n}F (2/x) = ∑_{j=0}^{n} a_{n−j} \frac{(2n − j)!}{j!(n − j)!}x^{j}

is irreducible. We therefore concentrate our efforts on showing f(x) is irreducible (though with some modifications one can work directly with F (x)).

Given g(x) = ∑_{j=0}^{n} b_{j}x^{j} ∈ ℤ[x] and p a prime, we define the Newton polygon of g(x) with respect to p as the lower convex hull of the points (j, ν(b_{n−j})) where ν(m) = ν_{p}(m) is the nonnegative integer r for which p^{r}∥m (cf. [4], [8]; the points where b_{n−j} = 0 need not be considered). Our first lemma below is used to connect the degrees of possible factors of the general polynomial f(x) with information about the Newton polygons of z_{n}(x). The proof can be found in [4, see Lemma 2].

Lemma 1. Let k and ℓ be integers with k > ℓ ≥ 0. Suppose g(x) = ∑_{j=0}^{n} b_{j}x^{j} ∈ ℤ[x] and p is a prime such that p ∤ b_{n}, p|b_{j} for all j ∈ {0, 1, …, n − ℓ − 1}, and the right-most edge of the Newton polygon for g(x) with respect to p has slope < 1/k. Then for any integers a_{0}, a_{1}, …, a_{n} with |a_{0}| = |a_{n}| = 1, the polynomial f(x) = ∑_{j=0}^{n} a_{n−j}b_{j}x^{j} cannot have a factor with degree in the interval [ℓ + 1, k].

We take g(x) = z_{n}(x). Following the proofs of Lemmas 4 and 5 from [4], we note that the slope of the right-most edge of the Newton polygon of z_{n}(x) with respect to p is

max_{1≤u≤n} \{\frac{1}{u}(ν(u!) + ν(\frac{(2n)!}{(2n − u)!}) − ν(\frac{n!}{(n − u)!}))\}.

We will be interested in using this expression for the slope when applying Lemma 1 to obtain information about the degrees of the factors of f(x). First, we indicate the information obtained from Lemma 1 in [4] (cf. Lemmas 4 and 5 there).

Lemma 2. Let n be a positive integer. Suppose that p is a prime, that k and r are positive integers, and that ℓ is an integer in [0, k − 1] for which

(i) p^{r}||(n − ℓ),

(ii) p ≥ 2ℓ + 1, and

(iii) \frac{log(2n)}{p^{r} log p} + \frac{1}{p − 1} ≤ \frac{1}{k}.

Then f(x) cannot have a factor with degree ∈ [ℓ + 1, k].

Lemma 3. Let n be a positive integer. Suppose that p is a prime, that k and r are positive integers, and that ℓ is an integer in [−k, −1] for which

(i) p^{r}||(n − ℓ),

(ii) p ≥ 2|ℓ| + 1, and

(iii) max \{\frac{1}{p − 2|ℓ| + 1}, \frac{log(2n)}{(p^{r} − 2|ℓ| + 1) log p}\} + \frac{1}{p − 1} ≤ \frac{1}{k}.

Then f(x) cannot have a factor with degree ∈ [|ℓ|, k].

In [4], Lemma 3 was only used to show that for n large f(x) cannot have a factor of degree 1, 2, 3, or 4; furthermore, only the case ℓ = −1 was used. In this paper, we will take advantage of the full range of values of ℓ given in the above two lemmas. The condition given in Lemma 3 (iii) is somewhat awkward and can be improved when r = 1. The purpose of our next lemma is to obtain such an improvement and at the same time uniformize our use of Lemmas 2 and 3.

Lemma 4. Let n be a positive integer. Suppose that p is an odd prime, that k is an integer > 1, and that ℓ ∈ {−k, −(k − 1), …, −1, 0, 1, …, k − 2, k − 1}. Suppose further that

(i) p|(n − ℓ),

(ii) p ≥ 2k + 1, and

(iii) \frac{log(2n)}{(p − 2k + 1) log p} < \frac{1}{k}.

Then f(x) cannot have a factor of degree k.

Proof. In order to prove Lemma 4, we consider the cases ℓ ≥ 0 and ℓ < 0 separately. For ℓ ≥ 0, we show the above lemma is in fact a consequence of Lemma 2. To do this we need only show that the inequality in Lemma 4 (iii) implies the inequality in Lemma 2 (iii); more precisely, we establish

(2)  \frac{log(2n)}{(p − 2k + 1) log p} < \frac{1}{k} ⟹ \frac{log(2n)}{p log p} + \frac{1}{p − 1} < \frac{1}{k}

from which Lemma 2 (iii) is an easy consequence. By a direct computation, we have

\frac{1}{pk} (\frac{1}{k} − \frac{1}{p − 1})^{−1} = \frac{p − 1}{p(p − k − 1)} ≤ \frac{1}{p − 2k + 1}.

The inequality in Lemma 4 (iii) implies

\frac{1}{pk} (\frac{1}{k} − \frac{1}{p − 1})^{−1} \frac{log(2n)}{log p} ≤ \frac{log(2n)}{(p − 2k + 1) log p} < \frac{1}{k} ,

and the implication in (2) easily follows.

Now, consider the case ℓ < 0. We modify the argument given for Lemma 5 in [4] as follows. Observe that z_{n}(x) = ∑_{m=0}^{n} c_{m}x^{n−m} where c_{0} = 1 and

c_{m} = \binom{n}{m}(n + 1) ⋯ (n + m) for m ≥ 1.

Hence, p|c_{m} for m ∈ {|ℓ|, |ℓ|+1, …, n}. We apply Lemma 1 and make use of the description of the slope of the right-most edge of the Newton polygon of z_{n}(x) with respect to p. Thus, we want to show that for each u ∈ {1, 2, …, n},

(3)  \frac{1}{u}(ν(u!) + ν(\frac{(2n)!}{(2n − u)!}) − ν(\frac{n!}{(n − u)!})) < \frac{1}{k} .

Fix such a u, and define a(x, j) as the number of multiples of p^{j} in (x − u, x]. Then

ν(\frac{(2n)!}{(2n − u)!}) − ν(\frac{n!}{(n − u)!}) = ∑_{j=1}^{∞} (a(2n, j) − a(n, j)).

The upper limit in the summation may be replaced by [log(2n)/ log p] since a(2n, j) = a(n, j) = 0 when p^{j} > 2n. Furthermore,

a(x, j) = [\frac{x}{p^{j}} ] − [\frac{x − u}{p^{j}}] = \frac{u}{p^{j}} + θ(x, j)

where |θ(x, j)| < 1. It follows that a(2n, j) − a(n, j) is an integer with absolute value < 2. Therefore, |a(2n, j) − a(n, j)| ≤ 1. Hence,

ν(\frac{(2n)!}{(2n − u)!}) − ν(\frac{n!}{(n − u)!}) ≤ ∑_{1≤j≤[log(2n)/ log p]} |a(2n, j) − a(n, j)| ≤ \frac{log(2n)}{log p}.

Also,

ν(u!) = ∑_{j=1}^{∞} [\frac{u}{p^{j}} ] ≤ ∑_{j=1}^{∞} \frac{u}{p^{j}} = \frac{u}{p − 1}.

Suppose first that u ≥ p. Then

\frac{1}{u}(ν(u!) + ν(\frac{(2n)!}{(2n − u)!}) − ν(\frac{n!}{(n − u)!})) ≤ \frac{1}{p − 1} + \frac{log(2n)}{u log p} ≤ \frac{1}{p − 1} + \frac{log(2n)}{p log p}.

From (2), it follows that Lemma 4 (iii) implies this last expression is < 1/k. We show next that (3) holds when u < p so that we may deduce that the right-most edge of the Newton polygon of z_{n}(x) has slope < 1/k and apply Lemma 1.

Suppose u < p. Then ν(u!) = 0. If 1 ≤ u ≤ p + 2ℓ, then n − ℓ − p < n − u + 1 and 2n − 2ℓ − p < 2n − u + 1 so that there are no multiples of p in each of (n − u, n] and (2n − u, 2n]. In this case,

\frac{1}{u}(ν(u!) + ν(\frac{(2n)!}{(2n − u)!}) − ν(\frac{n!}{(n − u)!})) = 0.

If u ≥ p + 2ℓ + 1, then u ≥ p − 2k + 1 so that

\frac{1}{u}(ν(u!) + ν(\frac{(2n)!}{(2n − u)!}) − ν(\frac{n!}{(n − u)!})) ≤ \frac{1}{u} ∑_{1≤j≤[log(2n)/ log p]} |a(2n, j) − a(n, j)|

≤ \frac{log(2n)}{u log p} ≤ \frac{log(2n)}{(p − 2k + 1) log p}.

We deduce from Lemma 4 (iii) that this last expression is < 1/k.

Combining the above, we obtain that (3) holds for each u ∈ {1, 2, …, n} and, hence, the slope of the right-most edge of the Newton polygon of z_{n}(x) is < 1/k. Lemma 1 implies that f(x) cannot have a factor of degree k, completing the proof. ■

3. The Proof of the Theorem

In this section, we let f(x) denote the polynomial given in (1). We assume that f(x) has a factor of degree k ∈ [1, n/2] and establish the theorem by obtaining a contradiction. We break the argument up into different cases depending on the size of k. For these different cases, we will establish the theorem for n ≥ 2479. The final case we consider is the irreducibility of f(x) when n < 2479. Throughout our arguments we will make use of the following explicit analytic estimates of Rosser and Schoenfeld [10, formulas (3.6), (3.14), (3.15), and (3.16)].

Lemma 5. Let π(x) denote the number of primes p ≤ x, and let ϑ(x) = ∑_{p≤x} log p. Then

π(x) < 1.256\frac{x}{log x} for all x > 1,

ϑ(x) < x(1 + \frac{1}{2 log x}) for all x > 1, and ϑ(x) > \{ \begin{matrix}x(1 − \frac{1}{log x}) & for x ≥ 41 \\ x(1 − \frac{1}{2 log x}) & for x ≥ 563. \end{matrix}

CASE 1: \frac{n}{100} ≤ k ≤ \frac{n}{2} and n ≥ 2479.

Lemma 6. For x ≥ 2479, there is a prime in the interval (x, 1.01x].

Proof. Let ϑ(x) = ∑_{p≤x} log p. There is a prime in (x, 1.01x] provided ϑ(1.01x) > ϑ(x). We deduce from Lemma 5 that, for x ≥ 563, there is a prime in (x, 1.01x] provided

1.01x(1 − \frac{1}{2 log(1.01x)}) > x(1 + \frac{1}{2 log x}).

One easily checks that this holds if log x ≥ 101. Since e^{101} < 10^{44}, we are through if x > 10^{44}.

We are left with verifying the theorem for all x ∈ [2479, 10^{44}]. We define a sequence recursively as follows. Let x_{0} = 2479. For n ≥ 1, define x_{n} as the largest prime < 1.01x_{n−1}. Suppose that x_{n+1} > x_{n}. It follows that if x ∈ [x_{n}, x_{n+1}), then there is a prime p ∈ (x, 1.01x] (the prime x_{n+1} will be such a p). We computed x_{n} for 1 ≤ n ≤ 10^{4} using both MAPLE (Version V, Release 4) and PARI (Version 1.39.12). Each of these contains a subroutine called “isprime” which, in both cases, is a pseudo-primality test. We avoided use of this subroutine and instead used the factoring routines in these symbolic packages. We compared the values of x_{1000j} for 1 ≤ j ≤ 10. The results were identical with

x_{10000} = 30160992555276892299261579269275542298335694063 > 10^{47}.

This establishes the lemma. ■

By Lemma 6, there is a prime p = n + ℓ + 1 where 0 ≤ ℓ < n/100. As in the proof of Lemma 4, we use that z_{n}(x) = ∑_{m=0}^{n} c_{m}x^{n−m} where c_{0} = 1 and

c_{m} = \binom{n}{m}(n + 1)(n + 2) ⋯ (n + m) for m ≥ 1.

Thus, p|c_{m} for m ∈ {ℓ + 1, ℓ + 2, …, n}. The endpoints of the right-most edge of the Newton polygon of z_{n}(x) with respect to p are (ℓ, 0) and (n, 1). This edge, therefore, has slope 1/(n − ℓ). By Lemma 1, f(x) cannot have a factor with degree in (ℓ, n − ℓ). Hence, k cannot be in the range given for this case.

CASE 2: n^{1/2} ≤ k < \frac{n}{100}.

Observe that the conditions in this case imply n > 10^{4} and k > 100. To show no factor can be of degree k, we show that there is a prime p > 3k > (2n)^{1/2} that divides n(n − 1) ⋯ (n − k + 1). Once we have done this, Lemma 2 implies we are through since

\frac{log(2n)}{p^{r} log p} + \frac{1}{p − 1} < \frac{log(2n)}{p log((2n)^{1/2})} + \frac{1}{3k} < \frac{2}{3k} + \frac{1}{3k} = \frac{1}{k} .

Since k > 41, we deduce from Lemma 5 that

∏_{k<p≤3k} p = exp (ϑ(3k) − ϑ(k)) ≤ exp (2k + \frac{3k}{2 log(3k)} + \frac{k}{log k} ) ≤ exp (2k + \frac{2.5k}{log k} ).

We make use of an idea of Erdős [1] (also described by Tijdeman in [12]). For each prime p ≤ k, we consider a number among n, n − 1, …, n − k + 1 which is divisible by p^{e} where e = e(p) is as large as possible. We dispose of these, and let S denote the set of numbers that remain. For every prime p, let N_{p} denote the exponent in the largest power of p dividing ∏_{m∈S} p. For p ≤ k, we obtain N_{p} ≤ [k/p] + [k/p^{2}] + · · ·. For k < p ≤ 3k, we use that k ≥ n^{1/2} to deduce that N_{p} ≤ 1. Therefore,

∏_{p>3k} p^{N_{p}} = \frac{∏_{m∈S} m}{( ∏_{p≤k} p^{N_{p}})( ∏_{k<p≤3k} p^{N_{p}})} ≥ (n − k + 1)^{|S|}(k! exp (2k + \frac{2.5k}{log k} ))^{−1}.

To complete this case, it suffices to show this last expression is > 1. We use that n−k+1 > 99k, |S| > k − 1.256k/ log k (by Lemma 5), and k! < ((k + 1)/e)^{k+1} for k ≥ 6. Taking logarithms, we want

k log k +((log 99)−1.256)k −(log 99)(1.256)\frac{k}{log k} > (k +1) log(k +1)+(k −1)+2.5\frac{k}{log k} .

Since k > 100, we have log k ≥ log 100 > 4. Also, (log x)/x is decreasing for x > e so that log k < k(log 100)/100 < (0.05)k. Finally, we use that log(k + 1) ≤ (log k) + (1/k). A direct computation shows the above inequality holds.

CASE 3: 100 ≤ k < n^{\frac{1}{2}} .

We obtain a contradiction here by modifying the approach used in the previous case. In Cases 3, 4, and 5, we use one and the same construction. We give details here though not all aspects of our discussion will be needed for Case 3. Define p_{min} = p_{min}(k) as the least prime ≥ 2k + \sqrt{2k^{2} − 2k + 1}. Hence,

p ≥ p_{min} ⟹ \frac{1}{p − 2k + 1} + \frac{1}{p − 1} ≤ \frac{1}{k} .

For each prime p, define r = r(p) so that p^{r(p)}||(n + k)(n + k − 1) ⋯ (n − k + 1). Define P = P (k) = ∏_{p≥p_{min}} p^{r(p)}. We estimate P in two different ways. First we get a lower bound. Using the idea of Erdős [1], for each prime p < p_{min}, we consider a number among n + k, n + k − 1, …, n − k + 1 which is divisible by p^{e} where e = e(p) is as large as possible. We dispose of these, and let S be the set of numbers that remain. For every prime p, let N_{p} denote the exponent of the largest power of p dividing ∏_{m∈S} m. Obviously r(p) ≥ N_{p} for each prime p and ∏_{m∈S} m = ∏_{p} p^{N_{p}}. As before, for p < p_{min} we obtain N_{p} ≤ [2k/p] + [2k/p^{2}] + ⋯ so that ∏_{p<p_{min}} p^{N_{p}} ≤ (2k)!. Since P ≥ ∏_{p≥p_{min}} p^{N_{p}}, we get

(4)  P > \frac{(n − k)^{2k−π(p_{min}−1)}}{(2k)!} .

Next, we get an upper bound for P. Note that when p ≥ p_{min} > 2k at most one of the numbers n + k, n + k − 1, …, n − k + 1 is divisible by p. Let p_{0} be a prime ≥ p_{min}. We estimate P_{1}(p_{0}) = ∏_{p≥p_{0},r(p)>1} p^{r(p)} (where we define the product to be 1 if r(p) ≤ 1 for each p ≥ p_{0}). Define P_{1} = P_{1}(p_{min}). Let p, if it exists, be a prime ≥ p_{0} with r(p) > 1. From Lemma 2 and Lemma 3, we get

\frac{log(2n)}{(p^{r} − 2k + 1) log p} + \frac{1}{p − 1} > \frac{1}{k} .

Defining

α_{k} = α_{k}(p_{0}) = \frac{1}{k} − \frac{1}{p_{0} − 1} and β_{k} = β_{k}(p_{0}) = α_{k}(p_{0}^{2} − 2k + 1),

we deduce that

α_{k} < \frac{log(2n)}{(p^{r} − 2k + 1) log p} and β_{k} < \frac{log(2n)}{log p}.

These inequalities hold provided p ≥ p_{0} and r(p) > 1 as in the product defining P_{1}(p_{0}). If β_{k} ≥ log(2n)/ log p_{0}, then it follows that no such p exists. In other words,

(5)  n ≤ \frac{p_{0}^{β_{k}}}{2} ⟹ P_{1}(p_{0}) = 1.

The above inequalities also imply for r > 1 that

(6) 2k − 1 + \frac{log(2n)}{α_{k} log p} > p^{r} and \frac{γ_{k} log(2n)}{log p} > p^{r} where γ_{k} = γ_{k}(p_{0}) = \frac{1}{α_{k}} + \frac{2k − 1}{β_{k}}.

Observe that when k ≥ 4, we have 2k + \sqrt{2k^{2} − 2k + 1} ≥ 3k + 1. Also, p_{min}(3) = 11 and p_{min}(2) = 7. It follows that for k > 1, we have

p_{min} ≥ 3k + 1, α_{k} ≥ \frac{2}{3k} , β_{k} > 6k + \frac{8}{3}, and γ_{k} < \frac{3k}{2} + \frac{1}{3}.

Set z = z(k, p_{0}) = γ_{k} log(2n)/ log p_{0}. Then z > p^{r(p)} > 1 and \sqrt{z} > p for each p in the product. In particular, if such a p exists (that is if P_{1}(p_{0}) > 1), then π(\sqrt{z}) > π(p_{0} − 1) and P_{1}(p_{0}) ≤ z^{π(\sqrt{z})−π(p_{0}−1)}. Lemma 5 implies

z^{π(\sqrt{z})} < exp(2.512\sqrt{z}) = (2n)^{\frac{2.512\sqrt{z}}{log(2n)}} .

Since β_{k} < log(2n)/ log p_{0}, we have

\frac{\sqrt{z}}{log(2n)} < \frac{1}{log p_{0}} \sqrt{\frac{γ_{k}}{β_{k}}} .

It follows that if there is a prime p ≥ p_{0} for which r(p) > 1, then

(7)  P_{1}(p_{0}) ≤ (2n)^{δ_{k}}/z^{π(p_{0}−1)}  where δ_{k} = \frac{2.512}{log p_{0}} \sqrt{\frac{γ_{k}}{β_{k}}} .

Also, \sqrt{z} > p_{0} implies

z^{π(p_{0}−1)} ≥ z^{π(p_{min}−1)} ≥ p_{0}^{2π(p_{min}−1)}.

Define

B = max \{1, \frac{(2n)^{δ_{k}}}{p_{0}^{2π(p_{min}−1)}} \}.

Then we obtain

(8)  P_{1}(p_{0}) ≤ B.

Now, we estimate P_{2} = ∏_{p≥p_{min},r(p)=1} p (where we define the product to be 1 if r(p) ≠ 1 for each p ≥ p_{min}). If P ≠ 1, we let p_{max} denote the largest prime in the product P. Then P_{2} ≤ exp(ϑ(p_{max}) − ϑ(p_{min} − 1)). For k > 1, Lemma 4 implies

(9)  2k − 1 + \frac{k log(2n)}{log p} ≥ p

for each prime appearing in the product P. In particular, (9) holds with p = p_{max} (if P ≠ 1). Lemma 5 implies ϑ(p_{max}) ≤ c_{1}(k) + c_{2}(k) log n where

c_{1}(k) = (1 + \frac{1}{2 log p_{max}} ) (2k − 1 + \frac{k log 2}{log p_{max}} )

and

c_{2}(k) = (1 + \frac{1}{2 log p_{max}} ) \frac{k}{log p_{max}} .

Thus, if P ≠ 1, then

(10)  P_{2} ≤ \frac{e^{c_{1}(k)}n^{c_{2}(k)}}{∏_{p<p_{min}} p} .

Observe that if P = 1, then P_{2} = 1 so that in general P_{2} is bounded above by the maximum of 1 and the expression on the right of (10). Also, note that (4) through (10) hold true for all n > 2k > 2. Furthermore, (4) through (8) hold when k = 1.

Now, we use these estimates to complete Case 3. We have n − k > n(1 − \frac{1}{k}). Also, since (1 − \frac{1}{k})^{k} is increasing for k ≥ 1, we obtain (1 − \frac{1}{k})^{k} ≥ (0.99)^{100}. Lemma 5 implies

π(p_{min} − 1) ≤ π((2 + \sqrt{2})k) < 1.256\frac{(2 + \sqrt{2})k}{log((2 + \sqrt{2}) × 100)} < 0.74k.

We use that for m ≥ 50, the inequality m! < (m/e)^{m+1} holds. Since k > 25 and n > k^{2}, we deduce that (2k)! < (2k/e)(2/e)^{2k}n^{k}. Using (4) we obtain

P > \frac{1}{3k} (\frac{e}{2})^{2k}n^{0.26k} > \frac{n^{0.26k}}{3k} .

Recall that for k > 1, β_{k} > 6k + (8/3) and γ_{k} < (3k/2) + (1/3). Thus, γ_{k}/β_{k} < 1/4. Also, p_{min}(100) = 347 and π(346) = 68. From (8), we deduce that

P_{1} < n^{0.3}.

Using p_{max}(k) ≥ p_{min}(k) ≥ p_{min}(100) = 347 we get c_{1}(k) < 2.3k and c_{2}(k) < 0.2k. For k ≥ 100, we obtain from Lemma 5 that

log ( ∏_{p<p_{min}} p) = ϑ(p_{min} − 1) ≥ ϑ(3k) > (1 − \frac{1}{log 300})3k > 2.3k.

Therefore, (10) implies P_{2} ≤ n^{0.2k}.

Since P = P_{1}P_{2}, combining the above, we deduce

\frac{n^{0.26k}}{3k} < n^{0.3}n^{0.2k}.

In other words, n^{0.06k−0.3} < 3k. Since \sqrt{n} > k ≥ 100, we obtain n^{0.06k−0.3} ≥ n^{5} ≥ 3k. The previous inequality therefore cannot hold, and we obtain a contradiction. Thus, f(x) cannot have a factor of degree k in this case.

CASE 4: 3 ≤ k < 100 and n ≥ 1800.

We proceed in the same way as we did in the previous case, the only difference being that we compute the quantities depending on k but not on n instead of estimating them. Our computations were done with the use of MAPLE V, Release 4. In particular, we calculated p_{min} = p_{min}(k) and π(p_{min} −1) precisely for 3 ≤ k < 100 to determine that the right-hand side of (4) is > 1 when n = 805. It follows that P > 1 whenever n > 804 and 3 ≤ k < 100. Since in fact n ≥ 1800, we also have n − k = n(1 − k/n) ≥ n(1 − k/1800). From (4), we obtain

P > \frac{(1 − \frac{k}{1800})^{s}n^{s}}{(2k)!} where s = 2k − π(p_{min} − 1).

We consider first the possibility that P_{1} > 1 and take p_{0} = p_{min}. Then (8) implies

P_{1} ≤ \frac{(2n)^{δ_{k}}}{p_{min}^{2π(p_{min}−1)}} .

Using (10) and P = P_{1}P_{2}, we obtain

\frac{(1 − \frac{k}{1800})^{s}n^{s}}{(2k)!} < \frac{(2n)^{δ_{k}}}{p_{min}^{2π(p_{min}−1)}} × \frac{e^{c_{1}(k)}n^{c_{2}(k)}}{∏_{p<p_{min}} p} .

Taking logarithms, we deduce that e_{1}(k) log n + e_{2}(k) < 0 where

e_{1}(k) = s − c_{2}(k) − δ_{k}

and

e_{2}(k) = ϑ(p_{min}−1)+s log (1−\frac{k}{1800})+2π(p_{min}−1) log(p_{min})−log((2k)!)−δ_{k}(log 2)−c_{1}(k).

We find trivial upper bounds for c_{1}(k) and c_{2}(k) by using the estimate p_{max}(k) ≥ p_{min}(k). Observe that with this estimate for p_{max}(k), we obtain lower bounds for e_{1}(k) and e_{2}(k) that depend only on k. Direct computations show that e_{1}(k) > 0 and e_{2}(k) > 0 for each k ∈ [3, 100). Thus, in the case that P_{1} > 1, we deduce that f(x) has no factors of degree k ∈ [3, 100).

We now consider the possibility that P_{1} = 1. Since P = P_{2}, we obtain e′_{1}(k) log n + e′_{2}(k) < 0 where e′_{1}(k) = e_{1}(k)+δ_{k} > e_{1}(k) > 0 and e′_{2}(k) = e_{2}(k)−2π(p_{min}−1) log(p_{min})+ δ_{k}(log 2). Direct computations give here that

e′_{1}(k) log n + e′_{2}(k) ≥ e′_{1}(k) log(1800) + e′_{2}(k) > 7.4e′_{1}(k) + e′_{2}(k) > 0 for 8 ≤ k < 100.

Therefore, f(x) has no factors of degree k ∈ [8, 100). The cases k = 3, 4, 5, 6, and 7 require some additional work.

For 3 ≤ k ≤ 7, this same argument works provided n > N where N = N(k) = exp(−e′_{2}/e′_{1}) (since then e′_{1}(k) log n + e′_{2}(k) > 0). Further work is required to handle n ∈ [1800, N]. For such n, we use (9) to obtain

2k − 1 + \frac{k log(2N)}{log p} − p ≥ 0

for each prime p dividing P_{2}. As a function of p, the left-hand side of the above inequality is decreasing. We determine the least prime q = q(k) such that the inequality does not hold if p is replaced by q. Then p_{max} < q. Using the definition of p_{min}, we obtain

k = 7 ⟹ 29 = p_{min} ≤ p_{max} ≤ 31, k = 6 ⟹ 23 = p_{min} ≤ p_{max} ≤ 29,
k = 5 ⟹ 17 = p_{min} ≤ p_{max} ≤ 23, k = 4 ⟹ 13 = p_{min} ≤ p_{max} ≤ 19,

and

k = 3 ⟹ 11 = p_{min} ≤ p_{max} ≤ 19.

Since in this case P = P_{2} is at most the product of the primes from p_{min} to p_{max}, we obtain an upper bound on P = P (k) for each k ∈ [3, 7]. Specifically, we have

P (7) ≤ 29 × 31 = 899, P (6) ≤ 23 × 29 = 667, P (5) ≤ 17 × 19 × 23 = 7429,
P (4) ≤ 13 × 17 × 19 = 4199, and P (3) ≤ 11 × 13 × 17 × 19 = 46189.

On the other hand, using (4) with n ≥ 1800, we obtain the lower bounds

P (7) ≥ 212565, P (6) ≥ 21624, P (5) ≥ 2860847, P (4) ≥ 143680, and P (3) ≥ 4485.

For 4 ≤ k ≤ 7, the lower bounds on P (k) exceed the upper bounds and we deduce again that f(x) cannot have a factor of degree k. For k = 3, we iterate the above procedure a second time. Using (4), we obtain that P (3) ≥ 46192 if n ≥ 5770. Since we have already determined that P (3) ≤ 46189, we obtain n ≤ 5769. Replacing N(3) with 5769 above, we deduce that p_{max}(3) ≤ 13 so that P (3) ≤ 11 × 13 = 143. This contradicts our lower bound for P (3) and we conclude that f(x) cannot have a factor of degree 3.

CASE 5: k = 1 or 2 and n ≥ 1614.

First, assume that f(x) has a factor of degree 2 (i.e., k = 2). In this case, p_{min} = p_{min}(2) = 7. Since among any four consecutive integers there is exactly one divisible by 4, at most one divisible by 9, and at most one divisible 5, we have P = ∏_{p≥7} p^{r} ≥ (n − 1)/6. We need to refine somewhat our estimates for P_{1} and P_{2}.

We consider first the possibility that p_{max} ≥ 23, that is that the largest prime divisor of (n + 2)(n + 1)n(n − 1) is ≥ 23. Then Lemma 4 implies n ≥ (1/2)23^{10}. By using (10) and p_{max} ≥ 23 we obtain P_{2} ≤ 2 × n^{0.74}.

To estimate P_{1} we first show that r(p) ≤ 1 for all primes p ≥ 11. Assume otherwise so that r(p) > 1 for some prime p ≥ 11. From (6) (with p_{0} = p_{min} = 7) we obtain 7^{r(7)} < 2 log(2n). From (7), we see that P_{1}(11) < 2n^{0.245}/z^{4} where z = z(2, 11) = γ_{2}(11) log(2n)/ log(11) > log(2n). Recall also from the arguments there that \sqrt{z} > p. Hence, z ≥ 11^{2} = 121. We obtain

P_{1} = P_{1}(7) ≤ 7^{r(7)} × P_{1}(11) < 2n^{0.245} \frac{2 log(2n)}{log(2n) × 121^{3}} < 10^{−5}n^{0.245}.

We deduce that

n − 1 ≤ 6P = 6P_{1}P_{2} < 6 × 2 × 10^{−5}n^{0.985} < \frac{n^{0.985}}{10} .

By dividing through by n^{0.985}, it is easy to see that the above inequalities cannot hold for n ≥ 2. Since n ≥ (1/2)23^{10}, we obtain a contradiction.

Thus, we must have r(p) ≤ 1 for all primes p ≥ 11. But then we obtain

P_{1} ≤ 7^{r(7)} < 2 log(2n) ⟹ n − 1 ≤ 6P = 6P_{1}P_{2} < 24 log(2n)n^{0.74}.

By dividing through by n^{0.74} and rearranging, we obtain the function w(n) = n^{0.26} − n^{−0.74} − 24 log(2n). It is easy to deduce that w(n) is increasing for n > 10^{8} and that w(10^{11}) > 0. Since we are interested in n ≥ (1/2)23^{10} > 10^{11}, we obtain again a contradiction. We deduce that p_{max} ≤ 19.

Since p_{min} = 7 and p_{max} ≤ 19, there are at most five primes p in the product P for which r(p) > 0. From Lemma 2 and Lemma 3, we obtain p^{r} < 3 + (3 log(2n)/ log(7)) for any prime p ≥ 7 so that

(11)  n − 1 ≤ 6P = 6 ∏_{p≥7} p^{r} ≤ 6(3 + \frac{3 log(2n)}{log 7})^{5}.

Dividing through by n and substituting x = n^{1/5}, we are led to considering the function

w(x) = 1 − \frac{1}{x^{5}} − 6(\frac{3}{x} + \frac{15 log x + 3 log 2}{x log 7})^{5}.

It is easy to see that w(x) is increasing for x > e. Since w(50) > 0, we deduce that (11) cannot hold if n > 50^{5}. Therefore, f(x) has no factors of degree 2 for such values of n. Let n ≤ 50^{5}. Note that (5) implies P_{1} = 1 for n ≤ (1/2)7^{(46/3)}. In particular, P_{1} = 1 for n ≤ 50^{5}. Therefore, in this case,

n − 1 ≤ 6P = 6P_{2} ≤ 6 × 7 × 11 × 13 × 17 × 19 < 10^{7}.

Now, from (9) we deduce that p_{max} ≤ 13. Hence, n − 1 ≤ P ≤ 6 × 7 × 11 × 13 so that n ≤ 6007. One more application of (9) gives p_{max} ≤ 7 which implies n − 1 ≤ 6 × 7. Thus, f(x) has no irreducible factors of degree 2 when n > 43.

The case k = 1 is similar to the case k = 2. With k = 1, we have p_{min} = 3. At least one of n and n + 1 is odd so that the definition of P implies P = ∏_{p≥3} p^{r} ≥ n. We consider first the possibility that the largest prime divisor of n(n + 1) is ≥ 13 (in other words, p_{max} ≥ 13). Lemma 2 and Lemma 3 imply n ≥ (1/2)13^{11} > 10^{11}. We wish to apply (10) except our argument for (10) made use of (9) which holds only for k > 1. By using Lemma 2 and Lemma 3 again we obtain for each p > 2 that p < 2 + log(2n)/ log p, and we replace our use of (9) (to derive (10)) with this inequality. For k = 1 we deduce that (10) holds with

c_{1}(1) = (1 + \frac{1}{2 log p_{max}} ) (2 + \frac{log 2}{log p_{max}} )

and c_{2}(1) as defined earlier. Using p_{max} ≥ 13 in (10), we deduce that P_{2} < 8\sqrt{n}.

To estimate P_{1} we show first that r(p) ≤ 1 for all primes p ≥ 5. Assume r(p) > 1 for some prime p ≥ 5. From (6) we obtain 3^{r} < 2.5 log(2n). Using (7), we deduce that P_{1}(5) < 2 × n^{0.45}/z^{2} where z = z(1, 5) = γ_{1}(5) log(2n)/ log 5 ≥ 0.8 log(2n). Also, \sqrt{z} > p implies z ≥ 25. We obtain

P_{1} = P_{1}(3) = 3^{r(3)} × P_{1}(5) < 2 × n^{0.45} \frac{2.5 log(2n)}{0.8 log(2n) × 25} = \frac{n^{0.45}}{4} .

We deduce that n ≤ P = P_{1}P_{2} < 2 × n^{0.95}. This does not hold for n ≥ 2^{20}. Since n > 10^{11} > 2^{20}, we arrive at a contradiction. Therefore, r(p) ≤ 1 for all primes ≥ 5. Now, we obtain

P_{1} ≤ 3^{r} < 2.5 log(2n) and n ≤ P < 2.5 log(2n) × 8\sqrt{n} = 20 log(2n)\sqrt{n}.

The function w(x) = 20 log(2x)/\sqrt{x} is easily seen to be decreasing for x > 4. Also, w(10^{5}) < 1. It follows that the inequality on n above does not hold for n ≥ 10^{5}. Since n > 10^{11}, we deduce that the largest prime divisor of n(n + 1) is < 13.

It remains to consider the case when p_{max} ≤ 11. Lemma 2 and Lemma 3 imply

(12)  p^{r} < 1 + \frac{2 log(2n)}{log p} ≤ 1 + \frac{2 log(2n)}{log 3}  for each prime dividing P.

Therefore,

n ≤ P = ∏_{p≥3} p^{r} < (1 + \frac{2 log(2n)}{log 3})^{4}.

By considering w(x) = x^{−1/4} + (2 log(2x)/(x^{1/4} log(3)) in a manner similar to before, we deduce that the above inequality does not hold for n ≥ 500000. Using the inequality p < 2 + log(2n)/ log p mentioned above on primes p dividing P and n < 500000, we obtain p_{max} ≤ 7. From (12), we now see that

n ≤ P ≤ (1 + \frac{2 log(2n)}{log 3})(1 + \frac{2 log(2n)}{log 5})(1 + \frac{2 log(2n)}{log 7}).

For each p ≥ 2, the function w(x) = x^{−1/3} + (2 log(2x)/(x^{1/3} log(p)) is decreasing for x ≥ 21 > e^{3}. We deduce that the inequality above does not hold if n ≥ 1614. Thus, we conclude that f(x) does not have a linear factor for n ≥ 1614.

CASE 6: n ≤ 2479.

We suppose as we may that n ≥ 2. We verify that f(x) is irreducible whenever 2 ≤ n ≤ 2479 as follows. Fix such an n. We use Lemma 4 to prove that f(x) cannot have a factor of degree k ∈ [2, n/2], and then we address the possibility that f(x) has a linear factor. We make use of three primes p_{1}, p_{2}, and p_{3}. We define p_{1} as the smallest prime ≥ n. We define p_{2} as the largest prime divisor of (n − 1)n(n + 1)(n + 2). We let t be the least positive integer satisfying

(p_{2} − 2t + 1) log p_{2} ≤ t log(2n).

Define p_{3} as the largest prime divisor of ∏_{j=−t+1}^{t}(n+j). The prime p_{1} is used in a manner similar to Case 1. We deduce that f(x) cannot have a factor of degree k ∈ (α, n/2] where α = p_{1} − n. By the definition of t, for each k < t, we have (p_{2} − 2k + 1) log p_{2} > k log(2n). This implies p_{2} > 2k for each such k. Since also p_{2}|(n−1)n(n+1)(n+2), the conditions in Lemma 4 hold, and we deduce that f(x) cannot have a factor of degree k ∈ [2, t). If t > α, then we can conclude f(x) has no factor of degree k ∈ [2, n/2]. If t ≤ α, we make use of p_{3}. We checked computationally using MAPLE, and for each n ∈ [2, 2479] (and somewhat beyond) the inequalities

p_{3} > 2k and (p_{3} − 2k + 1) log p_{3} > k log(2n)

held for t ≤ k ≤ α; indeed, the computation was somewhat simple as the inequalities hold for all such k if the second inequality holds when k = α. It follows that for k ∈ [t, α], Lemma 4 again applies to show that f(x) has no factor of degree k.

We are left with considering the possibility of a linear factor (i.e, k = 1). We use Lemmas 2 and 3 for this purpose. The computation for n ≤ 2479 (and beyond) was a direct application of these lemmas. We take two primes p_{1} and p_{2}, p_{1} being the largest prime factor of n and p_{2} being the largest prime factor of n + 1. We check if Lemma 2 applies with k = 1, ℓ = 0, and p = p_{1}. If it does, we’re done as f(x) then cannot have a linear factor. Otherwise, we check if Lemma 3 applies with k = 1, ℓ = −1, and p = p_{2}. In every case except n = 2 and n = 3, one of these two lemmas applied to show that f(x) does not have a linear factor. For n = 2 and n = 3, one can apply Lemma 1 directly with p = 3 (in fact, f(x) is Eisenstein with respect to 3 in these cases). We deduce that f(x) cannot have a linear factor.

References

1. P. Erdős, On consecutive integers, Nieuw Arch. Wisk. (3) 3 (1955), 124–128.

2. M. Filaseta, The irreducibility of almost all Bessel Polynomials, J. Number Theory 27 (1987), 22–32.

3. M. Filaseta, On an irreducibility theorem of I. Schur, Acta Arith. 58 (1991), 251–272.

4. M. Filaseta, The irreducibility of all but finitely many Bessel Polynomials, Acta Math. 174 (1995), 383–397.

5. M. Filaseta, A generalization of an irreducibility theorem of I. Schur, Analytic Number Theory: Proceedings of a Conference in Honor of Heini Halberstam, Vol. 1 (edited by B. Berndt, H. Diamond, and A. Hildebrand), Birkhäuser, Boston (1996), 371–396.

6. M. Filaseta and S. W. Graham, An estimate for the number of reducible Bessel Polynomials of bounded degree, Colloq. Math. 65 (1993), 65–68.

7. E. Grosswald, On some algebraic properties of the Bessel Polynomials, Trans. Amer. Math. Soc. 71 (1951), 197–210.

8. E. Grosswald, Bessel Polynomials, Lecture Notes in Math., 698. Springer-Verlag, Berlin, 1978.

9. E. Grosswald, Math. Review #89a:11105 (of [2] above), Math. Reviews, Issue 89a (January, 1989), 84.

10. J.B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–89.

11. I. Schur, Einige Sätze über Primzahlen mit Anwendungen aug Irreduzibilitätsfragen, I, Sitzungsber. Preuss. Akad. Wiss. Berlin Phys.-Math. Kl. 14 (1929), 125–136.

12. R. Tijdeman, On the maximal distance of numbers with a large prime factor, J. London Math. Soc. (2) 5 (1972), 313–320.

Mathematics Department University of South Carolina Columbia, SC 29208