Prime values of reducible polynomials, I.

Yong-Gao Chen* and Imre Z. Ruzsa**

Department of Mathematics, Nanjing Normal University Nanjing 210097, Jiangsu, P. R. China e-mail:ygchen@pine.njnu.edu.cn

Mathematical Institute of the Hungarian Academy of Sciences, Budapest, Pf. 127, H–1364 Hungary. e-mail: ruzsa@math-inst.hu

1. Introduction

It is a generally accepted conjecture that an irreducible integer-valued polynomial without a constant divisor assumes infinitely many prime values at integers. On the other hand it is easy to see that for a reducible f ∈ ℚ[x] there are only finitely many integers n for which f(n) is prime. It is, however, a nontrivial question to estimate the number of these integers. We shall be primarily interested in finding estimates in terms of the degree of f or of its factors.

In the sequel by “polynomial” we always mean a polynomial with rational coefficients, and reducibility is meant in ℚ[x]. We will write

P (f) = #{m ∈ ℤ : f(m) is prime}.

In this generality probably there is no estimate that depends on the degree alone.

* Supported by the National Natural Science Foundation of China and Fok Ying Tung Education Foundation. The work was done while first author was visiting the Mathematical Institute of the Hungarian Academy of Sciences. ** Supported by Hungarian National Foundation for Scientific Research, Grant No. T 025617

Conjecture 1.1. For every k there is a reducible f ∈ ℚ[x] of degree two such that P (f) ≥ k.

To support this conjecture we show that it follows from the following form of the prime k-tuple conjecture: if a_{1}, ..., a_{k} and b_{1}, ..., b_{k} are integers such that a_{i} ≠ 0 and the polynomial (a_{1}x + b_{1})...(a_{k}x + b_{k}) has no constant divisor, then there is an integer y such that all the a_{i}y + b_{i} are primes.

Consider now a polynomial

f(x) = \frac{x(x + s)}{m},

where m = q_{1}...q_{k} is the product of k distinct primes. We want to find an s such that all the numbers f(m/q_{j}) are prime. To achieve this we must have \frac{m}{q_{i}} + s = q_{i}p_{i} with primes p_{i}. This implies that

s ≡ −\frac{m}{q_{i}} (mod q_{i})

for all i, and these congruences together are equivalent to a single congruence s ≡ S (mod m). Write s = S + my; the numbers that should be prime are

\frac{1}{q_{i}} (\frac{m}{q_{i}} + s) = \frac{m}{q_{i}}y + \frac{1}{q_{i}} (\frac{m}{q_{i}} + S) = a_{i}y + b_{i},

say. Observe that (a_{i}, b_{i}) = 1, since the prime divisors of a_{i} are the primes q_{j}, j ≠ i and

\frac{m}{q_{i}} + S ≡ S ≡ −\frac{m}{q_{j}} ≢ 0 (mod q_{j}).

We have to exclude the possibility that a prime p always divides at least one of these linear forms. Now if p |̸ a_{i} then p|a_{i}y + b_{i} holds for integers y belonging to one residue class modulo p, and if p|a_{i} then it never holds. Thus a sufficient condition is that the number of those a_{i} that are not divisible by p is at most p − 1. This automatically holds if p > k, and it also holds if p = q_{j} for some j, since in this case p|a_{i} unless i = j. These two conditions together cover all primes if q_{1}, ..., q_{k} are selected so that all primes ≤ k are included among them. Thus for such choices of the q_{j} the prime tuple conjecture yields our conjecture above.

The situation changes if we restrict our attention to integer-valued polynomials, that is, such polynomials that f(n) is integral whenever so is n.

Theorem 1.

Let

P_{n} = sup{P (f) : deg f = n, f is integer-valued and reducible in ℂ}.

We have

exp(log 2 − o(1))\frac{n}{log n} < P_{n} < exp C \frac{n}{log n}

with an absolute constant C.

The second author conjectures that the lower estimate gives the proper order of magnitude. We will establish this under certain restrictions on the degree of the factors of f.

The situation changes considerably if we assume that the factors of f are also integer-valued. Indeed, if f = gh with integer-valued g and h, then f(x) can be a prime only if either g(x) = ±1 or h(x) = ±1, which immeditately gives 2n as an upper bound. The possibility to improve this bound will be the subject of Part II.

2. The upper estimate in Theorem 1

A polynomial of degree n is integer-valued if and only if it has the form

f(x) = a_{0} + a_{1}\binom{x}{1} + ... + a_{n}\binom{x}{n}

with integers a_{i}; thus in particular n!f(x) ∈ ℤ[x]. Hence n!f is reducible in ℤ[x], say n!f = gh. If f(m) is prime, then either g(m)|n! or h(m)|n!. The first possibility yields at most 2τ(n!) possible values for g(m) (where τ denotes the number of positive divisors), hence at most 2τ(n!) deg g values for m. We have an analogous estimate in the second case, and adding them we obtain

P (f) ≤ 2τ(n!)(deg g + deg h) = 2nτ(n!).  (2.1)

By Legendre’s formula we have

τ(n!) = ∏_{p} (1 + ∑_{j=1}^{∞} [\frac{n}{p^{j}} ]) ,

and this is easily calculated to be

= exp(C + o(1))\frac{n}{log n}, C = ∑_{k=2}^{∞} \frac{log k}{k(k − 1)}.

3. Further upper estimates

In the sequel we fix two integers 1 ≤ d < n, and try to estimate P (f) for those polynomials of degree n which have a divisor h of degree d. Our main result is the following.

Theorem 2.

Let 1 ≤ d ≤ n/2 be integers, and let f be an integral-valued polynomial of degree n which has a divisor of degree d.

(i) We have

P (f) ≤ 2n^{1+n/d}.  (3.1)

(ii) If d = 1 or 2, then

P (f) < exp(log 2 + o(1))\frac{n}{log n}.  (3.2)

Thus the conjecture after Theorem 1 is confirmed by (ii) for d = 1, 2 and by (i) for d > (log n)^{2}/ log 2.

We say that an integer k is a constant divisor of a polynomial g if g is integer-valued and k|g(m) for every integer m. We call a polynomial standard, if it is integer-valued and it has no constant divisor k > 1. Clearly any polynomial g ∈ ℚ[x] has a unique representation in the form g = (b/a)g_{1}, where g_{1} is standard, a, b are coprime integers and a ≥ 1.

We start with some preparation and then prove Theorem 2.

Lemma 3.1.

Let f ∈ ℤ[x] be a polynomial of degree n. The number of integers m for which |f(m)| ≤ M is at most 2nM^{1/n} + n .

Proof. Write

f(x) = a(x − x_{1})...(x − x_{n}), x_{i} ∈ ℂ.

Here |a| ≥ 1, thus if |f(m)| ≤ M, then |m − x_{j}| ≤ M^{1/n} for at least one j, altogether at most n(1 + 2M^{1/n}) possibilities.

For a fixed standard h, positive integer n and prime p, we define α_{p} as the largest integer α such that there exists a standard polynomial g of degree at most n − d such that p^{α} is a constant divisor of hg. Write

R(h, n) = ∏_{p} p^{α_{p}}.

Lemma 3.2.

Let f be an integer-valued polynomial, deg f ≤ n, and let h be a standard polynomial which divides f. Write f = (b/a)hg, where g is standard, a, b are coprime integers and a ≥ 1. Let G and H be the least common denominators of the coefficients of g and h, respectively. We have

(i) aGH|n! ; (ii) for any integer m, (h(m), f(m)) = 1 implies h(m)|a, h(m)|n!/H and h(m)|R(h, n).

Proof. (i) Let h_{1} = Hh, g_{1} = Gg; by the definition of G and H, h_{1}, g_{1} ∈ ℤ[x] are primitive polynomials. Since (a, b) = 1, b is a constant divisor of f. Hence

n!\frac{f}{b} = \frac{n!}{aGH} h_{1}g_{1} ∈ ℤ[x].

Since f_{1}, g_{1} are primitive, so is their product and we see that aGH|n!.

(ii) Since af(m) = bh(m)g(m), the coprimality assumption implies h(m)|a. Now a|n!/H by (i) and a|R(h, n) by definition (in fact, R(h, n) is the l.c.m. of all the possible values of a for fixed h and variable f of degree n).

Lemma 3.3.

Let h be a standard polynomial. For every integer n ≥ deg h we have R(h, n)|n!.

Proof. For each prime p we find the g occurring in the definition of α_{p}, and put f = (b/a)gh, where a, b are taken to make f standard. Then p^{α_{p}}|a, thus p^{α_{p}}|n! by (i) of the previous lemma. Since this holds for each p, we conclude R(h, n)|n!.

We define

N(h, n) = max #{m ∈ ℤ : (h(m), f(m)) = 1},  (3.3)

where f runs over all integer-valued polynomials of degree n which are multiples of h. This somewhat artificial quantity is closely related to P (f).

Statement 3.4.

Assume 1 ≤ d ≤ n/2. Let h be a standard polynomial of degree d, and f an integral-valued polynomial of degree n which is a multiple of h. We have

P (f) ≤ N(h, n) + 2n^{3} ≤ 2d ∏(1 + α_{p}) + n^{3}.  (3.4)

Proof. We preserve the notations of the previous lemmas. If f(m) = q is prime, then aq = af(m) = bh(m)g(m) shows that either g(m)|a or h(m)|a and (h(m), f(m)) = 1.

If g(m)|a, then by (i) of Lemma 3.2 we see that |g(m)| ≤ n!, and by Lemma 3.1 the number of such m does not exceed

2(n − d)n!^{1/(n−d)} + (n − d) ≤ n^{3}.

(We use d ≤ n/2 and n! ≤ n^{n}2^{1−n}, which follows from the inequality of arithmetical and geometrical means.) The number of values with ((h(m), f(m)) = 1 is at most N(h, n), which is at most

2dτ((R(h, n)) = 2d ∏(1 + α_{p})

by (ii) of Lemma 3.2

This immediately slightly improves the bound 2nτ(n!) of (2.1); a better understanding of R(h, n) could lead to further improvements.

Proof of Theorem 2, (i). By Lemma 3.2 (ii) and Lemma 3.1 we have

N(h, n) ≤ #{m ∈ ℤ : |h(m)| ≤ n!} ≤ d(1 + 2(n!)^{1/d}) ≤ n^{1+n/d}.

The claim follows from Statement 3.4.

Lemma 3.5.

Let g be an integral-valued polynomial. If there are deg g + 1 consecutive integers at which g(m) is divisible by a certain integer k, then k is a constant divisor of g.

Proof. After a division, this is reduced to the statement that if deg f +1 consecutive values are integral, then so are all the values at integers, which is well known and easily follows from Newton’s or Lagrange’s interpolation formula.

Lemma 3.6.

Let h, d, n denote as generally and let p > d be a prime. If the number of solutions of the congruence

d!h(x) ≡ 0 (mod p^{α+1})

does not exceed p^{α+1}/(n − d + 2), then α_{p} ≤ α.

Proof. By the condition we can find n − d + 1 consecutive integers for which p^{α+1} |̸ h(m). Thus if p^{α+1}|h(m)g(m), then p|g(m). Since this holds for n − d + 1 = deg g + 1 consecutive integers, by the previous lemma we conclude that p is a constant divisor of g, in contradiction with the assumptions.

Proof of Theorem 2, (ii). Let h be a standard polynomial of degree 1 or 2. Write

H(x) = 2h(x) = ax^{2} + bx + c, a, b, c ∈ ℤ

(a = 0 is permitted).

We show that for any prime p > 2 at least one of the following properties holds:

(a) the congruence H(x) ≡ 0 (mod p^{2}) has at most 2 solutions;

(b) the congruence H(x) ≡ 0 (mod p^{3}) has at most 2p solutions, and whenever p|H(m), then always p^{2}|H(m).

Indeed, if H(x) ≡ 0 (mod p^{2}) has no solution at all, we are ready. If it has, by a shift we can achieve that 0 is a solution, so we may assume p^{2}|c and the congruence becomes x(ax + b) ≡ 0 (mod p^{2}). If p |̸ b, then p cannot divide both factors, thus either x ≡ 0 (mod p^{2}) or ax + b ≡ 0 (mod p^{2}), at most two solutions altogether. If p|b, then p |̸ a, otherwise p would be a constant divisor of h, in contradiction with the assumption of standardness. In this case p^{2}|H(m) holds if and only if p|m, which shows the second claim in (b). To enumerate the solutions modulo p^{3}, we may assume that 0 is a solution and then we see that any solution satisfies either x ≡ 0 (mod p^{2}), or ax + b ≡ 0 (mod p^{2}), at most 2p possibilities modulo p^{3}.

Let now p be a prime, \sqrt{2n} < p ≤ n. In case (a), from Lemma 3.6 we obtain α_{p} ≤ 1. In case (b), from the same lemma we obtain α_{p} ≤ 2. In both cases whenever p|h(m), then p^{α_{p}}|h(m).

Consider now the integers for which h(m)|R(h, n). From the above argument, the possible exponents of a prime \sqrt{2n} < p ≤ n in h(m) are 0 and α_{p}. For p ≤ \sqrt{2n} the exponent is ≤ 1 + n by the divisibility R(h, n)|n! (Lemma 3.3). This yields at most

2(1 + n)^{π(\sqrt{2n})}2^{π(n)−π(\sqrt{2n})}

possible values of h(m). By virtue of Lemma 3.2 we have

N(h, m) ≤ 2d(1 + n)^{π(\sqrt{2n})}2^{π(n)−π(\sqrt{2n})},

and now (3.4) shows (3.2).

4. The lower estimate

We define

N′(h, n) = max_{f} min_{p} #{m ∈ ℤ : (h(m), f(m)) = 1, p |̸ h(m)},  (4.1)

where f runs over all integer-valued polynomials of degree n which are multiples of h and p runs over the primes.

Statement 4.1.

Let h be an integer-valued polynomial of degree d. For n > n_{0} (where n_{0} depends on d) there is an integer-valued polynomial f of degree n which is divisible by h and for which

P (f) ≥ \frac{N′(h, n)}{50(log n!)^{3}} .

Let π(x, k, l) denote the number of primes ≡ l (mod k) not exceeding x.

Lemma 4.2.

With certain positive absolute constants c, c_{1} we have

π(x, k, l) = \frac{li x}{ϕ(k)} + O(xe^{−c\sqrt{log x}})

uniformly for all k ≤ K, all x > exp c_{1}(log K)^{2} and all (l, k) = 1, except possibly certain values of k which are all multiples of some number k_{0} satisfying k_{0} > c(log K)^{2}(log log K)^{−8}.

See Karatsuba [1]. Proof of the Statement. Let f_{1} be a polynomial for which the expression in (4.1) assumes its maximum.

First we deduce bounds for the values of h(m) such that (h(m), f_{1}(m)) = 1.

Let H be the least common denominator of the coefficients of h. By Lemma 3.2 we know that Hh(m)|n! for all such m, in particular 1 ≤ |h(m)| ≤ n!/H. We have

Hh(x) = a ∏_{i=1}^{d}(x − x_{i})

with |a| ≥ 1. Hence these values of m satisfy either |m − x_{1}| ≤ n!, which we shall call typical, or |m − x_{j}| < 1 for some j ≥ 2, which we call exceptional. Clearly the number of exceptional m’s is less than 2d. In the sequel we shall use only the typical m. By a shift (by the integer closest to Re x_{1}) we can achieve that these satisfy |m| ≤ n!, so we shall assume this inequality.

Next we modify f_{1} to make it small at the above values. Write f_{1} = hg_{1}. Every polynomial of the form f_{2} = h(g_{1} + g^{∗}), where g^{∗} ∈ ℤ[x], satisfies the same coprimality assumptions. By choosing the coefficients of g^{∗} appropriately we can achieve that all coefficients of g_{2} = g_{1} + g^{∗} are in (0, 1]. This yields

|g_{2}(m)| ≤ n(n!)^{n−d}

for all typical m, hence

|f_{2}(m)| ≤ n!|g_{2}(m)| ≤ nn!^{n}.

We shall find an f with many prime values in the form f = f_{2} + th with an integer t. We will find this t by a statistical argument. We define T by log T = (log n!)^{3}. This implies

T |h(m)| ≥ |f_{2}(m)|  (4.1)

for all typical m. Then we have

#{t : |t| ≤ T, f_{2}(m) + th(m) is prime} ≥ π(T |h(m)|, |h(m)|, |r|).

By Lemma 4.2 we deduce that this is

≥ \frac{1}{2} \frac{1}{ϕ(|h(m)|)} \frac{T |h(m)|}{log T |h(m)|} ≥ \frac{1}{4} \frac{T}{log T}

if h(m) is not a multiple of the exceptional k_{0}. The number of integers m for which this argument works is at least

N′(h, n) − 2d.

Since the number of choices for t is ≤ 2T + 1, there must be a |t| ≤ T for which

P (f) ≥ \frac{1}{2T + 1} \frac{T}{4 log T} (N′(h, n) − 2d).

This implies the claim of the statement if N′(h, n) ≥ 6d. If 1 ≤ N′ < 6d, then the bound is less than 1 and we can find a prime value simply by applying Dirichlet’s theorem; for N′ = 0 the claim is empty.

Remark 4.3. The difference between N(h, n) and N′(h, n) is of a technical nature and would disappear if we knew that there are no Siegel roots. The denominator in Statement 4.1 is due to the averaging, and the prime-tuple conjecture would give stronger results.

Proof of Theorem 1, lower estimate.

We will use the above statement for h(x) = x. Write Q = ∏_{p≤n} p. We will set f = gh/Q with

g(x) = Qx^{n−1} + ∑_{p≤n} \frac{Q}{p}(x^{p−1} − 1).

Clearly g is an integral-valued polynomial of degree n − 1. Q is a constant divisor of xg(x) by Fermat’s theorem, thus indeed f is integral-valued.

Next we show that for every D|Q we have (D, f(D)) = 1. Indeed, take a prime q|D. All coefficients of g except those coming from the term p = q in the sum are multiples of q, thus

g(D) ≡ \frac{Q}{q}(D^{q−1} − 1) ≡ −\frac{Q}{q} ≢ 0 (mod q).

Hence

(D, f(D)) = (D, \frac{g(D)}{Q/D}) = 1.

This implies

N′(h, n) ≥ min_{p} #{m ∈ ℤ : (m, f(m)) = 1, p |̸ m} ≥ min_{p} #{m ∈ ℤ : m|Q, p |̸ m} = 2^{π(n)}.

Nence the lower estimate of Theorem 1 follows from Statement 4.1.

Reference

[1] Karatsuba, A. A., Basic analytic number theory, Springer–Verlag, New York–Berlin 1993. Printed 1999.2.28.