DIVISIBILITY PROPERTIES OF GENERALIZED LAGUERRE POLYNOMIALS

CLEMENS FUCHS^{†} AND T.N. SHOREY

Abstract. In this paper we give effective upper bounds for the degree k of divisors (over ℚ) of generalized Laguerre polynomials L_{n}^{(α)}(x), i.e. of

L_{n}^{(α)}(x) = ∑_{j=0}^{n} \binom{n + α}{n − j} \frac{(−x)^{j}}{j!} ,

for α = −tn − s − 1 and α = tn + s with t, s ∈ ℕ, t = O(log k), s = O(k log k) and k sufficiently large.

2000 Mathematics Subject Classification: 11C08, 33C45, 11N05. Keywords: Laguerre polynomials, irreducibility, p-adic Newton polygons, gaps between primes.

1. Introduction and results

The generalized Laguerre polynomials L_{n}^{(α)}(x) are well-known and extensively studied objects in different areas of mathematics, e.g. in analysis, combinatorics and mathematical physics. We define

L_{n}^{(α)}(x) = ∑_{j=0}^{n} \binom{n + α}{n − j}\frac{(−x)^{j}}{j!} = ∑_{j=0}^{n} \frac{(n + α)(n − 1 + α) ⋯ (j + 1 + α)}{(n − j)!j!}(−x)^{j}

for α ∈ ℝ, n ∈ ℕ. An important instance is given by the case α = −2n − 1, since there we have the relation

(−1)^{n}n!L_{n}^{(−2n−1)}(x) = x^{n}B_{n}(2/x)

and B_{n}(x) are the Bessel polynomials. The leading coefficient is given by (−1)^{n}/n!.

In this paper we are concerned with questions on the divisors of L_{n}^{(α)}(x) over ℚ. In 1929 I. Schur proved that L_{n}^{(0)}(x) and L_{n}^{(−n−1)}(x) are irreducible (over ℚ) and in 1931 he proved the same for L_{n}^{(1)}(x) (cf. [14, 15]). A new proof for the case α = −n − 1 was given by R.F. Coleman [1] in 1987 by using the Newton polygon. In fact Coleman and M. Filaseta developed a new method for attacking these kind of problems. An overview of the results can be found in [4]. Filaseta [3] proved in 1995 that L_{n}^{(−2n−1)}(x) is irreducible for all but finitely many n, and in turn he immediately obtained the same result for the Bessel polynomials (by the connection given above). Later in 2002 Filaseta and O. Trifonov [6] extended this result to all integers n. In the same year, Filaseta and T.-Y. Lam [5] proved that L_{n}^{(α)}(x) is irreducible for all but finitely n for a fixed α ∈ ℚ\ℤ^{−}. We point out that the exclusion of the negative integers is really necessary, since for α = −r with r ∈ ℕ an easy computation shows that L_{n}^{(α)}(x) is reducible for n ≥ r. The irreducibility for α = −n − r and r = 2, …, 9 was shown by F. Hajir [9, 10] (the case r = 3 is by E.A. Sell [16]). Hajir also proved that for a fixed positive integer r the polynomial L_{n}^{(−n−r)}(x) is irreducible for all but finitely many n. We mention that the statements on all but finitely many n are effective in the sense that an explicit lower bound for the n from which onward the statement is true can be given. Hajir conjectured in [10] that for all non-negative integers n, s the generalized Laguerre polynomial L_{n}^{(−n−s−1)}(x) is irreducible. Another instance of this problem was recently considered by Filseta, T. Kidd and Trifonov in [7]. They showed that L_{n}^{(n)}(x) is irreducible for every n with n ≡ 2 (mod 4) with the exception n = 2, where this is false, and for all other n the polynomial L_{n}^{(n)}(x) is either irreducible or it is a linear polynomial times an irreducible polynomial of degree n − 1.

†Corresponding author.

Instead of proving that L_{n}^{(−n−s−1)}(x) is irreducible one can try to exclude divisors of large degree for many values of s. Recently, R. Tijdeman and the second author [13] proved that for every 0 ≤ α ≤ 30, α ∈ ℤ and 4 < k ≤ \frac{n}{2}, the polynomial L_{n}^{(α)}(x) has no factor of degree k. Moreover, they proved that if 2 ≤ k ≤ \frac{n}{2} and s is an integer with 0 ≤ s ≤ 0.8k, then L_{n}^{(−n−s−1)}(x) does not have a factor of degree k. In their paper they study in fact a more general situation than the case of Laguerre polynomials, where the above results are just some special cases. In this paper we shall consider an analogous problem for L_{n}^{(t′n+s′)} where s′ and |t′| ≥ 1 are integers.

Now we fix some notation which we shall always follow in this paper without reference. Let n, s, t be integers with n ≥ 2, 0 ≤ s ≤ n and let α be given by either

(1)  α = −tn − s − 1 with t ≥ 2

DIVISIBILITY PROPERTIES OF LAGUERRE POLYNOMIALS 3

or

(2)  α = tn + s with t ≥ 1.

First let α satisfy (1). We have

L_{n}^{(α)}(x) = ∑_{j=0}^{n} \frac{(n − tn − s − 1) ⋯ (j + 1 − tn − s − 1)}{(n − j)!j!}(−x)^{j}
= ∑_{j=0}^{n} \frac{(−(t − 1)n − s − 1) ⋯ (j − tn − s)}{(n − j)!j!}(−x)^{j}
= (−1)^{n} ∑_{j=0}^{n} \frac{((t − 1)n + s + 1) ⋯ ((t − 1)n + s + j)}{(n − j)!j!}x^{n−j}

and therefore

(−1)^{n}n!L_{n}^{(α)}(x) =: ∑_{j=0}^{n} c_{j}x^{n−j}

where

(3)  c_{j} = \binom{n}{j}((t − 1)n + s + 1) ⋯ ((t − 1)n + s + j)
= \binom{(t − 1)n + s + j}{j}(n − j + 1) ⋯ n.

Observe that for every m ∈ {0, …, n} we thus have

(4)  \frac{c_{n}}{c_{n−m}} = \frac{(tn + s)!}{(tn + s − m)!} · \frac{(n − m)!}{n!} · m!.

Let α satisfy (2). Then

(−1)^{n}n!L_{n}^{(α)}(x) = (−1)^{n}n! ∑_{j=0}^{n} \binom{(t + 1)n + s}{n − j}\frac{(−x)^{j}}{j!} =: ∑_{j=0}^{n} c′_{j}x^{n−j},

where

(5)  c′_{j} = (−1)^{j}\binom{n}{j}((t + 1)n + s − j + 1) ⋯ ((t + 1)n + s).

Thus

(6)  \frac{c′_{n}}{c′_{n−m}} = (−1)^{m} \frac{(tn + s + m)!}{(tn + s)!} · \frac{(n − m)!}{n!} · m!

for every m ∈ {0, 1, …, n}. The relations (4) and (6) will be of importance later on. For 0 ≤ j ≤ n, we write d_{j} = c_{j} or c′_{j} according as α satisfies (1) or (2), respectively. Moreover, we set

f(x) := ∑_{j=0}^{n} d_{j}x^{n−j}

and

F (x) := ∑_{j=0}^{n} a_{j}d_{j}x^{n−j}

for integers a_{0}, a_{1}, …, a_{n}. In the sequel we will denote by η_{1}, η_{2}, … effectively computable absolute positive real constants. We have the following result.

Theorem 1. Let ε = 1/5 if α < 0 and ε = 1/112 if α > 0. Let a_{0}, a_{1}, …, a_{n} be any integers with |a_{0}| = |a_{n}| = 1. Then there exists a constant η_{1} such that for all k with

η_{1} < k ≤ \frac{n}{2}

and for all α satisfying (1) or (2) with

t < ε log k, s < εk log k,

the polynomial F (x) does not have a factor of degree k.

Concerning the role of F (x) compared to f(x) we mention that many of the results from the introduction are also of such a general shape. As a special case we immediately get the following result for generalized Laguerre polynomials, which we state separately.

Theorem 2. Let ε be as in Theorem 1. There exists a constant η_{2} such that for all k with

η_{2} < k ≤ \frac{n}{2}

and all α satisfying (1) or (2) with

t < ε log k, s < εk log k,

the polynomial L_{n}^{(α)}(x) has no factor of degree k.

In the proof we will see that if n ≤ k^{42/23}, then Theorem 1 is also valid with t < ε log n, s < εk log n. The assumption n ≤ k^{42/23} is relaxed as follows in the case of negative integers, i.e. in case α satisfies (1).

Theorem 3. Let ε = 1/7 and a_{0}, a_{1}, …, a_{n} be any integers with |a_{0}| = |a_{n}| = 1. There is a constant η_{3} such that for all n > η_{3} and all α satisfying (1) with

exp ((log n)^{\frac{2}{3} (1+ε)}) ≤ k ≤ \frac{n}{2}

and

t < ε log n, s < εk log n,

the polynomial F (x) does not have a factor of degree k.

The proofs of Theorems 1 and 3 split in two parts. First by using p-adic arguments, especially the p-adic Newton polygon, we reduce the problem to finding a prime p having certain properties. By considering several cases depending on k the proof will be finished.

In the next section we introduce the Newton polygon with respect to a prime p and give some auxiliary results on this polygon, as well as on primes in certain intervals. Afterwards, we will give the proofs of Theorem 1 and 3, respectively.

2. Newton polygons and preliminaries on primes

For a prime p let v_{p} be a p-adic valuation, i.e. for a positive integer n we have that v_{p}(n) is the largest integer such that p^{v_{p}(n)}|n (we will also use the notation p^{v_{p}(n)}∥n, for short) and v_{p}(0) = ∞. We shall also write v for v_{p} when it will be clear from the context which p we are taking. Let g(x) = ∑_{j=0}^{n} b_{j}x^{n−j} ∈ ℤ[x] with b_{0}b_{n} ≠ 0. The p-adic Newton polygon (or just Newton polygon) for g(x) with respect to the prime p is now defined as the polygonal path formed by the lower edges of the convex hull of the points

(0, v(b_{0})), (1, v(b_{1})), (2, v(b_{2})), …, (n − 1, v(b_{n−1})), (n, v(b_{n})).

The left-most endpoint is (0, v(b_{0})) and the right-most endpoint is (n, v(b_{n})). Moreover, the endpoints of each edge belong to the above set and the slopes of the edges strictly increase from left to right.

Then Filaseta [3, Lemma 2] proved the following result.

Lemma 1. Let k and ℓ be integers with k > ℓ ≥ 0 and k ≤ n/2. Suppose that

g(x) = ∑_{j=0}^{n} b_{j}x^{n−j} ∈ ℤ[x]

and p is a prime such that p ∤ b_{0}, p|b_{j} for all j ∈ {ℓ + 1, …, n} and the rightmost 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

G(x) = ∑_{j=0}^{n} a_{j}b_{j}x^{n−j}

cannot have a factor with degree in the interval [ℓ + 1, k].

We apply this lemma in the case L_{n}^{(α)}(x), in fact we will use g(x) = f(x) and G(x) = F (x).

The next result is an estimate on the difference between consecutive primes and it will be used in the proof of Theorem 1.

Lemma 2 (S.T. Lou and Q. Yao, [12]). Denote by p_{n} the n-th prime number and let ε > 0. There exists a constant η_{4} such that

p_{n+1} − p_{n} ≤ η_{4} p_{n}^{6/11+ε}.

We remark that the upper bound is already quite good, since under the Riemann hypothesis the ideal bound would be ≪ p_{n}^{1/2} log p_{n} ≪ p_{n}^{1/2+ε} (with the usual meaning of ≪). Furthermore, observe that the lemma implies that there is η_{5} such that for any x > η_{5} there exists a prime in the interval [x, x+x^{1/2+1/21}] as well as in the interval [x−x^{1/2+1/21.5}, x] ⊇ [x−x^{47/86}, x].

For Theorem 3 we need a result on the largest prime factor in a product of consecutive integers.

Lemma 3 (M. Jutila, [11]). Let u and k be positive integers and let P (u, k) be the largest prime factor of (u + 1) ⋯ (u + k). Then there are constants η_{6}, η_{7} and η_{8} such that for

k^{3/2} ≤ u ≤ k^{η_{6}(log k)^{1/2}/ log log k}

we have

P (u, k) ≥ η_{8}k^{1+η_{7}Λ(k,u)},

where Λ(k, u) = (log k/ log u)^{2}.

Now we are ready to prove our assertions. This will be done in the next two sections.

3. Proof of Theorem 1

Let ε = 1/5 if α < 0 and ε = 1/112 if α > 0 and set δ = 1/16. Let η_{1} be sufficiently large. Assume that F (x) has a factor of degree k such that η_{1} < k ≤ \frac{n}{2} and ε log k > t, εk log k > s. Observe that n ≥ 2k and therefore n exceeds a sufficiently large effectively computable absolute constant. We divide the proof of Theorem 1 in two parts according to (1) or (2).

3.1. The case of negative indices, i.e. the case (1). First by Lemma 2 (see also the remark made afterwards) it follows that there is a prime p of the form p = (t − 1)n + s + ℓ with

(7)  0 < ℓ ≤ ((t − 1)n + s)^{1/2+1/21} ≤ (tn)^{23/42} < (n log n)^{23/42}.

From the definition of the c_{j} (cf. (3)) it follows at once that p∥c_{j} for j ∈ {ℓ, …, n} and p ∤ c_{0} = 1. Thus the right-most edge of the Newton polygon for f(x) with respect to p has endpoints (ℓ − 1, 0), (n, 1) and therefore, by (7), its slope is 1/(n − ℓ + 1) < 2/n ≤ 1/k. By Lemma 1 we get a contradiction unless k ≤ ℓ. Hence we can assume k ≤ ℓ ≤ (tn)^{23/42}.

Now we consider two different cases depending on the size of k, namely n^{11/21} ≤ k and k < n^{11/21}:

Assume that n^{11/21} ≤ k. Then since k ≤ (tn)^{23/42} and 1/2 < 11/21, we have n^{1/2} < n^{11/21} ≤ k ≤ (tn)^{23/42}. We start by proving the following lemma which extends Filaseta [3, Lemma 4] with t = 2, s = 0.

Lemma 4. Let n, r and k ≤ n/2 be positive integers, ℓ ∈ {0, 1, …, k − 1} and let p ≥ tk + s + 1 be a prime number satisfying p^{r}∥n − ℓ and

(8)  \frac{log(tn + s)}{p^{r} log p} + \frac{1}{p − 1} ≤ \frac{1}{k} .

Then F (x) does not have a factor with degree ∈ [ℓ + 1, k].

Proof. We start by introducing the function

a(n, j) := ⌊\frac{n}{p^{j}} ⌋ − ⌊\frac{n − m}{p^{j}}⌋

(obviously a(n, j) also depends on m and p), which is equal to the number of multiples of p^{j} in (n − m, n] and where ⌊x⌋ is defined to be the largest integer ≤ x. Since

v(m!) = ∑_{j=1}^{∞} ⌊\frac{m}{p^{j}}⌋ < ∑_{j=1}^{∞} \frac{m}{p^{j}} = \frac{m}{p − 1},

we show that it suffices to prove that

(9)  a(tn + s, j) − a(n, j) ≤ \frac{m}{p^{r}}

for all

j ≤ J := ⌊\frac{log(tn + s)}{log p}⌋ .

Because of (4) we now have

\frac{v(c_{n}) − v(c_{n−m})}{m} = \frac{v(m!)}{m} + \frac{1}{m} [v (\frac{(tn + s)!}{(tn + s − m)!}) − v (\frac{n!}{(n − m)!})]
= \frac{v(m!)}{m} + ∑_{j=1}^{∞} \frac{a(tn + s, j) − a(n, j)}{m},

where the sum in fact just runs over j ≤ J, since for j > J we have p^{j} > tn+s, which implies a(tn+s, j) = a(n, j) = 0. Thus, by using the inequalities obtained so far together with the hypothesis in (8), the slope of the rightmost edge of the Newton polygon for f(x) is bounded by

max_{1≤m≤n} \{\frac{v(c_{n}) − v(c_{n−m})}{m}\} < \frac{1}{p − 1} + \frac{log(tn + s)}{p^{r} log p} ≤ \frac{1}{k} .

Since p|n(n − 1) ⋯ (n − ℓ) and p > k ≥ j it follows that p|c_{j} for j ∈ {ℓ + 1, …, n} and p ∤ c_{0} = 1 (cf. equation (3)). Therefore, we get by Lemma 1 that F (x) does not have a factor with degree ∈ [ℓ + 1, k]. This proves the assertion.

We have to prove (9) and we do it by considering three cases depending on the size of j and m.

Case 1. Assume that 1 ≤ j ≤ r: We will use that p^{r}∥n − ℓ, which implies that there is an integer u with n = p^{r}u + ℓ. It follows that

a(tn + s, j) = ⌊\frac{tn + s}{p^{j}}⌋ − ⌊\frac{tn + s − m}{p^{j}}⌋
= ⌊tp^{r−j}u + \frac{tℓ + s}{p^{j}}⌋ − ⌊tp^{r−j}u + \frac{tℓ + s − m}{p^{j}}⌋
= ⌊\frac{tℓ + s}{p^{j}}⌋ − ⌊\frac{tℓ + s − m}{p^{j}}⌋ = − ⌊\frac{tℓ + s − m}{p^{j}}⌋
a(n, j) = ⌊\frac{n}{p^{j}} ⌋ − ⌊\frac{n − m}{p^{j}}⌋ = ⌊p^{r−j}u + \frac{ℓ}{p^{j}} ⌋ − ⌊p^{r−j}u + \frac{ℓ − m}{p^{j}}⌋
= ⌊\frac{ℓ}{p^{j}} ⌋ − ⌊\frac{ℓ − m}{p^{j}}⌋ = − ⌊\frac{ℓ − m}{p^{j}}⌋ ,

where we have used that our prime p satisfies p^{j} ≥ p > tℓ + s. Therefore we get

a(tn + s, j) − a(n, j) = − ⌊\frac{tℓ + s − m}{p^{j}}⌋ + ⌊\frac{ℓ − m}{p^{j}}⌋ ≤ 0.

It follows that (9) is trivially true.

Case 2. Assume now m ≤ tℓ + s: It first follows that (tn + s − m, tn + s] ⊆ (tn + s − tℓ − s, tn + s] = (tn − tℓ, tn + s]. Since p|n − ℓ we get p|tn−tℓ. Together with p > tℓ+s this implies that there is no multiple of p^{j} in (tn+s−m, tn+s] at all, which gives a(tn+s, j) = 0. Thus (9) again holds.

Case 3. Finally assume j > r, m > tℓ + s: We observe that the number of multiples of p^{r} in (tn + s − m, tn + s] ⊃ [tn − tℓ, tn + s] is bounded by ⌊m/p^{r}⌋+1. Since p ≥ tk +s+1 > t, the multiple tn−tℓ of p^{r} is not divisible by p^{j}. Therefore

a(tn + s, j) ≤ a(tn + s, r) − 1 ≤ ⌊\frac{m}{p^{r}} ⌋ .

So in this case the inequality (9) holds too.

Altogether, we have covered all cases and this completes the proof of Lemma 4. □

Thus we just have to prove that there is a prime p > 2εk log k, which implies p > (t + 1)k > (t + 1)n^{1/2} and p ≥ tk + s + 1, that divides n(n − 1) ⋯ (n − k + 1). Then

\frac{log(tn + s)}{p^{r} log p} + \frac{1}{p − 1} ≤ \frac{log((t + 1)n)}{(t + 1)k log((t + 1)n^{1/2})} + \frac{1}{(t + 1)k} ≤ \frac{1}{k} ,

since log((t + 1)n)/ log((t + 1)n^{1/2}) ≤ 2 ≤ t and then the contradiction follows by Lemma 4. To show that such a prime exists we use the following lemma, which is based on an argument first given by Erdős in [2]. We take the following version that can be found in [7, Lemma 6].

Lemma 5. Let z be a positive real number. For each prime p ≤ z, let d_{p} ∈ {n, n − 1, …, n − k + 1} with v_{p}(d_{p}) maximal. Define

Q_{z} = Q_{z}(n, k) = ∏_{p>z} p^{v_{p}(A)}

with A = n(n − 1) ⋯ (n − k + 1). Then

Q_{z} ≥ \frac{n(n − 1) ⋯ (n − k + 1)}{(k − 1)! ∏_{p≤z} p^{v_{p}(d_{p})}} ≥ \frac{(n − k + 1)^{k−π(z)}}{(k − 1)!} ,

where π(z) denotes the number of primes ≤ z.

We write z = 2εk log k in this case. By the prime number theorem we have

π(z) ≤ \frac{(1 + δ)2εk log k}{log(2εk log k)} .

We get

Q_{z} ≥ (\frac{1}{2}n)^{k−(1+δ)2εk log k/ log(2εk log k)} (εn log k)^{−23k/42}
(10) ≥ (n^{19/42−(1+δ)2ε log k/ log(2εk)}(ε log k)^{−23/42}2^{(1+δ)2ε log k/ log(2εk)−1})^{k} ,

where we have used that n − k + 1 ≥ \frac{1}{2}n and (k − 1)! ≤ k^{k} ≤ (tn)^{23k/42} < (εn log k)^{23k/42}. By definition of Q_{z} we now just have to guarantee that the exponent of n in the right hand side of (10) is > 0, then the existence of a prime p with the required properties follows. The exponent of n is 19/42 − (1 + δ)2ε log k/ log(2εk) ≥ 19/42 − 2ε(1 + δ)^{2} > 0, since log k/ log(2εk) ≤ 1 + δ, ε = 1/5 and δ = 1/16, implying Q_{z} > 1. This completes the proof in the first case.

Now we turn to the second case and assume that k < n^{11/21}. In this case we can immediately improve the lower bound for Q_{z} in the arguments above to

(11) Q_{z} ≥ (\frac{1}{2}n)^{k−(1+δ)2εk log k/ log(2εk)} n^{−11k/21} ≥ n^{k/41}2^{−k} ≥ n^{k/42},

since 10/21 − (1 + δ)2ε log k/ log(2εk log k) ≥ 10/21 − 2ε(1 + δ)^{2} ≥ 1/41. Now let p > z be a prime with p|n(n − 1) ⋯ (n − k + 1). Note that since p ≥ tk+s+1 > k it follows that p divides exactly one of n, n−1, …, n−k+1. Assume that p|n−ℓ with ℓ ∈ {0, …, k−1} and let r > 0 be such that p^{r}∥n−ℓ. Moreover, observe that (with the notation of Lemma 5) we have r = v_{p}(A). Since we are assuming that F (x) has a factor of degree k it follows by Lemma 4 applied with this prime p that we must have

\frac{log(tn + s)}{p^{v_{p}(A)} log p} + \frac{1}{p − 1} = \frac{log(tn + s)}{p^{r} log p} + \frac{1}{p − 1} > \frac{1}{k} .

Since p > (t+1)k ≥ 3k, we have 1/(p−1) ≤ 1/(3k) and therefore we deduce from the last formula that

p^{v_{p}(A)} < \frac{3k log((t + 1)n)}{2 log p} ≤ \frac{3 (1 + \frac{log(t+1)}{log n})}{2 log((t + 1)k)}k log n < \frac{1}{43}k log n;

this is true since (129/2)(log(t + 1) + log n) < log n log(t + 1) + log n log k. Therefore, we get

p < \frac{1}{43}k log n and v_{p}(A) < \frac{log k + log log n − log 43}{log p}

and hence

∑_{p>z} v_{p}(A) log p < ∑_{z<p≤ \frac{1}{43} k log n}(log k + log log n − log 43) ≤ \frac{1}{42}k log n.

By comparing this upper bound for log Q_{z} with the lower bound from (11) we immediately end up with a contradiction. This proves the assertion in the second case.

3.2. The case of positive indices, i.e. the case (2). Assume first that n^{23/42} ≤ k ≤ \frac{n}{2}. By Lemma 2 we get that there is a prime p of the form p = (t + 1)n + s − ℓ with

ℓ ≤ ((t + 1)n + s)^{47/86} ≤ (3n log n)^{47/86} < n^{23/42} ≤ k.

By the definition of the c′_{j} (see (5)) it follows that p divides c′_{ℓ+1}, …, c′_{n}, and clearly it does not divide c′_{0} = 1. Therefore v_{p}(c′_{j}) ≥ 1 for j ∈ {ℓ + 1, …, n} and v_{p}(c′_{0}) = 0. Since p > tn + s and therefore 2p > 2tn + 2s ≥ (t + 1)n + s , we see that (t + 1)n + s − ℓ = p is the only multiple of p among the numbers (t + 1)n + s − j with 0 ≤ j < n. Finally, from c′_{n} = (−1)^{n}(tn + s + 1) ⋯ ((t + 1)n + s) we get that v_{p}(c′_{n}) = 1. Therefore, the right-most edge of the Newton polygon of f(x) has slope < 1/(n − k) ≤ 1/k. This is not possible by Lemma 1 and therefore there is no factor of degree k in the range.

Now we can assume that k < n^{23/42}. We write z = 6εk log k in this case. By observing that (t + 1)n + s − k + 1 ≥ tn + s ≥ n, we get from Lemma 5

Q_{z}((t + 1)n + s, k) ≥ n^{k−π(z)}n^{−23/42k} ≥ (n^{19/42−(1+δ)6ε log k/ log(6εk)})^{k} > 1,

since 19/42 − 6ε(1 + δ)^{2} > 0. It follows that there is a prime p > z ≥ 2k dividing (t + 1)n + s − ℓ with 0 ≤ ℓ ≤ k − 1. For such a prime it follows that p|c′_{j} for j ∈ {ℓ + 1, …, n} and we define m = m(p) ∈ {1, …, n} such that

\frac{v_{p}(c′_{n}) − v_{p}(c′_{n−m})}{m}

is the slope of the right most edge of the Newton polygon for f(x) with respect to p. Then we have by Lemma 1 and (6) that

\frac{1}{k} ≤ \frac{v_{p}(c′_{n}) − v_{p}(c′_{n−m})}{m} ≤ \frac{1}{m} [v_{p} (\frac{(tn + s + m)!}{(tn + s)!}) − v_{p} \begin{matrix}( \\ ( & {n \atop m} & ) \\ ) \end{matrix}]
≤ \frac{1}{m}v_{p}((tn + s + 1) ⋯ (tn + s + m))
≤ \frac{1}{m} ∑_{j=1}^{∞} (⌊\frac{tn + s + m}{p^{j}}⌋ − ⌊\frac{tn + s}{p^{j}}⌋)

≤ \frac{1}{m} ∑_{j=1}^{J} (\frac{m}{p^{j}} + 1) ≤ \frac{1}{p − 1} + \frac{J}{m} ≤ \frac{1}{2k} + \frac{J}{m},

where

J := ⌊\frac{log((t + 1)n + s)}{log p}⌋ .

It follows that m ≤ 2kJ and thus

(12)  m ≤ \frac{2k log((t + 1)n + s)}{log p} < \frac{4k log n}{log k} =: m_{0}.

So this inequality is true for all primes p > z dividing (t + 1)n + s − ℓ with 0 ≤ ℓ ≤ k − 1.

Let U := {(t + 1)n + s, …, (t + 1)n + s − k + 1}\{b_{q} : q ≤ z}, where for all primes q ≤ z we have removed those numbers b_{q} ∈ {(t + 1)n + s, …, (t + 1)n + s − k + 1} with v_{q}(b_{q}) maximal. We mention, as we have already seen, that all elements of U are ≥ n. Now let Ω be the set of all primes q > z with v_{q}(u) > 0 from some u ∈ U and q^{v_{q}(u)} ≤ 2ε(m + k) log k for all u ∈ U. Here we recall that m = m(q) satisfies (12), since q > z and divides some u ∈ U. Observe that such a q divides exactly one u ∈ U, since q > z ≥ k. Thus we have

log ( ∏_{u∈U} ∏_{q∈Ω} q^{v_{q}(u)}) ≤ log (  ∏_{z<q≤2ε(m_{0}+k) log k} 2ε(m_{0} + k) log k)
≤ π(2ε(m_{0} + k) log k) log(2ε(m_{0} + k) log k)
≤ (1 + δ)2ε(m_{0} + k) log k
≤ 12(1 + δ)εk log n,

by using (12). It follows that

log ( ∏_{u∈U} ∏_{q≤z} q^{v_{q}(u)} ∏_{q∈Ω} q^{v_{q}(u)}) ≤ k log k + 12(1 + δ)εk log n ≤ \frac{2}{3}k log n,

since k < n^{23/42}. On the other hand we have

log ( ∏_{u∈U} u) ≥ (k − π(z)) log n ≥ (1 − \frac{(1 + δ)6ε log k}{log(6εk)} ) k log n > \frac{2}{3}k log n,

since log k/ log(6εk) ≤ 1+δ. By putting the last two statements together we conclude that there is a prime q > z that divides some element u ∈ U with the additional property that q^{v_{q}(u)} > 2ε(m+k) log k. Let u = (t+1)n+s−ℓ with 0 ≤ ℓ ≤ k − 1 and let r be defined by q^{r} > 2ε(m + k) log k ≥ q^{r−1} and such that q^{r} divides u. Again, by (5), it follows that this prime divides c′_{j} for j ∈ {ℓ + 1, …, n}. If q^{r} divides tn + s + j for some 1 ≤ j ≤ m, then it also divides (t + 1)(tn + s + j) − t((t + 1)n + s − ℓ) = s + tj + tℓ + j and therefore q^{r} ≤ s + (t + 1)m + t(k − 1) ≤ 2ε(m + k) log k, which is a contradiction. Therefore, q^{r} does not divide tn + s + j for all 1 ≤ j ≤ m. Hence, we now have

\frac{1}{k} ≤ \frac{v_{q}(c′_{n}) − v_{q}(c′_{n−m})}{m} ≤ \frac{1}{m}v_{q}((tn + s + 1) ⋯ (tn + s + m))

≤ \frac{1}{m} ∑_{j=1}^{r−1} (\frac{m}{q^{j}} + 1) ≤ \frac{1}{q − 1} + \frac{r − 1}{m} < \frac{1}{3k} + \frac{r − 1}{m},

since q > z ≥ 3k. For r ≥ 2 we have

2(2ε(m + k) log k) ≥ 2q^{r−1} > 2(6εk log k)^{r−1} ≥ (6εk log k)^{r−1} + 4εk log k

and therefore

4εm log k > (6εk log k)^{r−1} ≥ (r − 1)6εk log k.

Finally we conclude

m > \frac{3}{2}k(r − 1)

and

\frac{1}{k} ≤ \frac{v_{q}(c′_{n}) − v_{q}(c′_{n−m})}{m} < \frac{1}{3k} + \frac{2}{3k} = \frac{1}{k} ,

which is a contradiction. This completes the proof of Theorem 1.

4. Proof of Theorem 3

We take ε = 1/7 and δ = 1/40 in the proof of Theorem 3. Further, let η_{3} be sufficiently large. Assume that F (x) has a factor of degree k ≤ \frac{1}{2}n such that t < ε log n, s < εk log n with n > η_{3}.

We can start as in the proof of Theorem 1 and conclude that, actually, we may assume that k ≤ (tn)^{23/42}. Moreover, we can follow the arguments given there afterwards, but for k in the range k ≥ (n/2)^{2/3}. Namely, by applying Lemma 5 and the prime number theorem we get that for z = 2εk log n we have

Q_{z} ≥ (\frac{1}{2}n)^{k−π(z)} (tn)^{−23k/42}
≥ (n^{\frac{19}{42} − \frac{(1+δ)2ε log n}{log(2ε(n/2)^{2/3} log n)}} (ε log n)^{− \frac{23}{42}} 2^{−1+ \frac{(1+δ)2ε log n}{log(2ε(n/2)^{2/3} log n)}} )^{k} ,

which shows, since ε = 1/7 and log n/ log(2ε(n/2)^{2/3} log n) ≤ 3/2, that there is a prime p > 2εk log n > εn^{2/3} and p ≥ tk + s + 1 that divides n(n − 1) ⋯ (n − k + 1). For this prime we have tn + s < εn log n + εk log n ≤ 2εn log n and

\frac{log(tn + s)}{p log p} + \frac{1}{p − 1} ≤ \frac{log(2εn log n)}{2εk log n log (εn^{2/3})} + \frac{1}{εk log n} ≤ \frac{1}{k}

and therefore it follows by Lemma 4 that F (x) cannot have a factor of degree k.

Let η_{6}, η_{7} and η_{8} be the constants appearing in Lemma 3. We are left with k ≤ (n/2)^{2/3}, i.e. with 2k^{3/2} ≤ n. Since we are assuming that log n ≤ (log k)^{3/2(1+ε)^{−1}} ≤ (log k)^{3/2(1−ε/2)} it follows that

log n ≤ η_{6} \frac{(log k)^{3/2}}{log log k}

and therefore that

(13)  k^{3/2} ≤ \frac{n}{2} ≤ u := n − k ≤ n ≤ k^{η_{6}(log k)^{1/2}/ log log k}.

Hence, by the same lemma we get that the largest prime factor p = P (u, k) of n(n − 1) ⋯ (n − k + 1) = (u + 1)(u + 2) ⋯ (u + k) satisfies

p ≥ η_{8}k^{1+η_{7}Λ(k,u)}.

We observe

Λ(k, u) ≥ (\frac{log k}{log n})^{2} ≥ η_{6}^{−2} (\frac{log log k}{(log k)^{1/2}} )^{2} ≥ η_{9} \frac{(log log n)^{2}}{log k}

where we have used the last inequality in (13) again. Thus, p ≥ η_{10}k(log n)^{2} > k log n and p > 2εk log n > tk + s. But since

\frac{log(tn + s)}{p log p} + \frac{1}{p − 1} ≤ \frac{log(2εn log n)}{k log n log(log n)} + \frac{1}{p − 1} ≤ \frac{1}{k}

it follows again by Lemma 4 that F (x) cannot have a factor of degree k. This is a contradiction.

This completes the proof of Theorem 3.

5. Acknowledgments

This work was initiated when the second author was visiting ETH in April 2008 and he would like to thank ETH for the invitation and hospitality. The authors are most grateful to an anonymous referee for very careful reading of the paper and for useful and important advice in preparing the revised version.

References

[1] R.F. Coleman, On the Galois groups of the exponential Taylor polynomials, L’Enseignement Math. 33 (1987), 183-189.

[2] P. Erdős, On consecutive integers, Nieuw Archief voor Wiskunde (3) 3 (1955), 124-128.

[3] M. Filaseta, The irreducibility of all but finitely many Bessel polynomials, Acta Math. 174 (1995), 383-397.

[4] M. Filaseta, C. Finch, and J.R. Leidy, T.N. Shorey’s influence in the theory of irreducible polynomials, In: Diophantine Equations (N. Saradha, ed.), Narosa (2008), 77-102.

[5] M. Filaseta and T.-Y. Lam, On the irreducibility of the generalized Laguerre polynomials, Acta Arith. 105 (2002) 177-182.

[6] M. Filaseta and O. Trifonov, The irreducibility of the Bessel polynomials, J. Reine Angew. Math. 550 (2002), 125-140.

[7] M. Filaseta, T. Kidd, and O. Trifonov, Laguerre polynomials with Galois group A_{m} for each m, Preprint, 2008.

[8] M. Filaseta and R.L. Williams Jr., On the irreducibility of a certain class of Laguerre polynomials, J. Number Theory 100 (2003), 229-250.

[9] F. Hajir, Some A_{n}-extensions obtained from generalized Laguerre polynomials, J. Number Theory 50 (1995), 206-212.

[10] F. Hajir, Algebraic properties of a family of generalized Laguerre polynomials, Preprint, 2008.

[11] M. Jutila, On numbers with a large prime factor. II, J. Indian Math. Soc. (N.S.) 38 (1974), no. 1,2,3,4, 125-130 (1975).

[12] S.T. Lou and Q. Yao, A Chebychev’s type of prime number theorem in a short interval. II, Hardy-Ramanujan J. 15 (1992), 1-33.

[13] T.N. Shorey and R. Tijdeman, Generalizations of some irreducibility results by Schur, Preprint, 2008.

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

[15] I. Schur, Affektlose Gleichungen in der Theorie der Lagurreschen und Hermiteschen Polynome, J. Reine Angew. Math. 165 (1931), 52-58.

[16] E. A. Sell, On a certain family of generalized Laguerre polynomials, J. Number Theory 107 (2004), 266-281.

Clemens Fuchs Department of Mathematics, ETH Zurich Rämistrasse 101, 8092 Zürich, Switzerland Email: clemens.fuchs@math.ethz.ch

T.N. Shorey School of Mathematics, Tata Institute of Fundamental Research Homi Bhabha Road, 400005 Mumbai, India Email: shorey@math.tifr.res.in