1 Introduction
For
$k$
and
$n$
positive integers and integers
$a_{0},a_{1},\ldots ,a_{n}$
, define
$b_{k}=(10^{k}-1)/9$
and
In this paper, we establish the following.
Theorem 1. There is an absolute constant
$N$
such that if
$n\geqslant N$
and if
$a_{0},a_{1},\ldots ,a_{n}$
are integers having no prime divisors
${>}n\exp (\log n/(105\log \log n))$
, then
$f_{n}(x)$
as given in (1) is irreducible over
$\mathbb{Q}$
.
As in the theorem, henceforth in this paper, irreducibility refers to irreducibility over the rationals.
Theorem 1 is meant only to illustrate a general approach we will describe for establishing irreducibility of polynomials
$f(x)$
in which there are a number of coefficients where each denominator of these coefficients has a prime factor that does not divide any other denominator of a coefficient of
$f(x)$
. In the case of Theorem 1, the presence of the factor
$\unicode[STIX]{x1D6F7}_{k}(10)$
in
$b_{k}$
will provide us with such a prime factor, where
$\unicode[STIX]{x1D6F7}_{k}(x)$
denotes the
$k$
th cyclotomic polynomial.
As an indication of generalizations and other applications of the approach, we mention the following. One can show that for a fixed positive integer
$m$
, for
$n$
sufficiently large (depending on
$m$
) and for
$a_{k}$
as in Theorem 1, the polynomial
$f_{n}^{(j)}(x)$
is irreducible for
$0\leqslant j\leqslant m$
. Thus, for example, the polynomial
$f_{n}(x)$
and the first
$100$
derivatives of
$f_{n}(x)$
are all irreducible provided only that
$n$
is sufficiently large. We can also apply the same approach to show that for
$n$
sufficiently large and for
$a_{k}$
as in Theorem 1, we have that
$$\begin{eqnarray}\mathop{\sum }_{k=0}^{n}\frac{a_{k}x^{k}}{2^{2k}+2^{k}+1},\qquad \mathop{\sum }_{k=0}^{n}\frac{a_{k}x^{k}}{2^{\lfloor \unicode[STIX]{x1D70B}k\rfloor }+(-1)^{k}}\quad \text{and}\quad \mathop{\sum }_{k=0}^{n}\frac{a_{k}x^{k}}{k(k+1)(k+2)\unicode[STIX]{x1D6F7}_{k}(7)}\end{eqnarray}$$
are all irreducible. Note that showing the irreducibility of the second example, say
$g(x)$
, above is not difficult if
$a_{j}=1$
for every
$j$
as then multiplying by the least common multiple of the denominators in
$x^{n}g(1/x)$
allows one to apply Eisenstein’s criterion with the prime
$2$
. If
$a_{0}=2$
, then establishing the irreducibility of
$g(x)$
requires more work. As a final example, let
$u$
and
$v$
be integers with
$uv\neq 0$
and
$v\neq \pm u$
. Then there is a
$B=B(u,v)$
such that if
$n\geqslant B$
and
$a_{k}$
is as above, then our methods imply that
$$\begin{eqnarray}\mathop{\sum }_{k=0}^{n}\frac{a_{k}x^{k}}{u^{k}+v^{k}}\end{eqnarray}$$
is irreducible. We will focus on the proof of Theorem 1 in this paper and leave it to the interested reader to verify that the irreducibility results for the other polynomials listed here follow from the same methods.
2 Preliminaries
In this section, we discuss some background results.
Lemma 1. There is a constant
$\unicode[STIX]{x1D6FE}\in (0,1/2]$
such that for
$n$
sufficiently large, there are
$\gg n/(\log ^{2}n)$
primes
$p\in (n/2,3n/4]$
such that every prime divisor of
$n-p$
is
${>}n^{\unicode[STIX]{x1D6FE}}$
.
This is a fairly direct application of sieve methods. For example, it would follow from Brun’s sieve [Reference Halberstam and Richert6, Theorem 2.1
$^{\prime }$
, p. 65]. We omit the details.
Lemma 2. Let
$k$
and
$\ell$
be distinct positive integers. Then there exist polynomials
$u(x)$
and
$v(x)$
in
$\mathbb{Z}[x]$
such that
$$\begin{eqnarray}\displaystyle & & \displaystyle \unicode[STIX]{x1D6F7}_{k}(x)u(x)+\unicode[STIX]{x1D6F7}_{\ell }(x)v(x)\nonumber\\ \displaystyle & & \displaystyle \quad =\left\{\begin{array}{@{}ll@{}}p\quad & \text{if }p\text{ is a prime such that }k/\ell \text{ is a power of }p,\\ 1\quad & \text{if there is no prime }p\text{such that }k/\ell \text{is a power of }p.\end{array}\right.\end{eqnarray}$$
To clarify,
$k/\ell$
being a power of
$p$
allows for the possibility here that
$k/\ell =p^{-e}$
for some positive integer
$e$
. To the author’s knowledge, (2) first appeared in [Reference Filaseta5]. However, the analogous result with the right-hand side of (2) replaced by the resultant of
$\unicode[STIX]{x1D6F7}_{k}(x)$
and
$\unicode[STIX]{x1D6F7}_{\ell }(x)$
, as obtained by Apostol [Reference Apostol1], would suffice for our purposes in this paper. Although this resultant does not divide the right-hand side of (2) in general, Schinzel has pointed out that in fact (2) follows from knowledge of this resultant (see [Reference Filaseta5]). Elementary arguments for the value of the resultant and for (2) have been given by Dresden [Reference Dresden3].
Our next result is a consequence of a more general result of Stewart [Reference Stewart7]. We define
$\unicode[STIX]{x1D6F7}_{n}(x,y)=y^{\unicode[STIX]{x1D719}(n)}\unicode[STIX]{x1D6F7}_{n}(x/y)$
, so that
$\unicode[STIX]{x1D6F7}_{n}(x,y)\in \mathbb{Z}[x,y]$
. Then we have the following.
Lemma 3. Let
$u$
and
$v$
be integers with
$uv\neq 0$
and
$u/v\neq \pm 1$
. Then there is a
$k_{0}=k_{0}(u,v)$
such that if
$k$
is an integer
${\geqslant}k_{0}$
, then the largest prime divisor of
$\unicode[STIX]{x1D6F7}_{k}(u,v)$
is greater than
$$\begin{eqnarray}\displaystyle k\exp \biggl(\frac{\log k}{104\log \log k}\biggr). & & \displaystyle\end{eqnarray}$$
Our interest in Lemma 3 will be in the case that
$v=1$
, so that
$\unicode[STIX]{x1D6F7}_{k}(u,v)=\unicode[STIX]{x1D6F7}_{k}(u)$
. For further historical information on the prime factors of cyclotomic polynomials, see [Reference Dickson2, Ch. XVI].
Lemma 4. Let
$n$
and
$k$
be integers with
$n$
sufficiently large and
$k\in (n/2,n]$
. Let
$k^{\ast }$
denote the expression in (3). Then there is a prime
$q>k^{\ast }$
such that
$q\mid \unicode[STIX]{x1D6F7}_{k}(10)$
and
$q\nmid \unicode[STIX]{x1D6F7}_{\ell }(10)$
for every integer
$\ell \in [1,n]$
with
$\ell \neq k$
.
The existence of
$q>k^{\ast }$
such that
$q\mid \unicode[STIX]{x1D6F7}_{k}(10)$
follows from Lemma 3 with
$u=10$
and
$v=1$
. To see that Lemma 4 holds, we want to show also that
$q$
does not divide
$\unicode[STIX]{x1D6F7}_{\ell }(10)$
for every integer
$\ell \in [1,n]$
. Fix such an
$\ell$
. The conditions that
$n$
is sufficiently large and
$k\in (n/2,n]$
imply that
$q>n\geqslant \max \{k,\ell \}$
. In particular,
$q\nmid k$
and
$q\nmid \ell$
. Thus,
$k/\ell$
cannot be a power of
$q$
. Setting
$x=10$
in (2), we see that
$q$
cannot divide both
$\unicode[STIX]{x1D6F7}_{k}(10)$
and
$\unicode[STIX]{x1D6F7}_{\ell }(10)$
. Hence,
$q\nmid \unicode[STIX]{x1D6F7}_{\ell }(10)$
, as required.
The last piece of background we will use is the notion of Newton polygons and a theorem of Dumas [Reference Dumas4]. Let
$f(x)=\sum _{j=0}^{n}c_{j}x^{j}\in \mathbb{Q}[x]$
with
$c_{0}c_{n}\neq 0$
. Let
$p$
be a prime. For a rational number
$r\neq 0$
, we set
$\unicode[STIX]{x1D708}_{p}(r)$
to be the integer
$e$
such that
$r=p^{e}u$
, where
$u$
, expressed as a reduced fraction, has numerator and denominator not divisible by
$p$
. We define
$\unicode[STIX]{x1D708}_{p}(0)=+\infty$
. Let
$S$
be the set of lattice points
$(j,\unicode[STIX]{x1D708}_{p}(c_{n-j}))$
, for
$0\leqslant j\leqslant n$
, in the extended plane. We consider the lower edges along the convex hull of these points. The left-most edge has an end point
$(0,\unicode[STIX]{x1D708}_{p}(c_{n}))$
and the right-most edge has
$(n,\unicode[STIX]{x1D708}_{p}(c_{0}))$
as an end point. The polygonal path along the lower edges of the convex hull from
$(0,\unicode[STIX]{x1D708}_{p}(c_{n}))$
to
$(n,\unicode[STIX]{x1D708}_{p}(c_{0}))$
is called the Newton polygon of
$f(x)$
with respect to the prime
$p$
. The end points of every edge belong to the set
$S$
and each edge has a distinct slope that increases as we move along the Newton polygon from left to right.
The following important result due to Dumas [Reference Dumas4] connects the Newton polygon of
$f(x)$
with respect to a prime
$p$
with the Newton polygon of its factors with respect to the same prime.
Lemma 5. Let
$g(x)$
and
$h(x)$
be in
$\mathbb{Q}[x]$
with
$g(0)h(0)\neq 0$
, and let
$p$
be a prime. Let
$k=\unicode[STIX]{x1D708}_{p}(\ell )$
, where
$\ell$
is the leading coefficient of
$g(x)h(x)$
. Then the edges of the Newton polygon for
$g(x)h(x)$
with respect to
$p$
can be formed by constructing a polygonal path beginning at
$(0,k)$
and using translates of the edges in the Newton polygons for
$g(x)$
and
$h(x)$
with respect to the prime
$p$
, using exactly one translate for each edge of the Newton polygons for
$g(x)$
and
$h(x)$
. Necessarily, the translated edges are translated in such a way as to form a polygonal path with the slopes of the edges increasing from left to right.
3 The proof of Theorem 1
Fix
$\unicode[STIX]{x1D6FE}\in (0,1/2]$
as in Lemma 1. Let
$N_{0}\geqslant 2000$
be sufficiently large so that by Lemma 1, if
$n$
is an integer
${\geqslant}N_{0}$
, then the number of primes
$p\in (n/2,3n/4]$
such that every prime divisor of
$n-p$
is
${>}n^{\unicode[STIX]{x1D6FE}}$
is
$\gg n/(\log ^{2}n)$
. We divide the interval
$(n/2,3n/4]$
into
$\ll n^{1-\unicode[STIX]{x1D6FE}}$
disjoint subintervals
$(u,v]$
with
$v-u\in (n^{\unicode[STIX]{x1D6FE}}/2,n^{\unicode[STIX]{x1D6FE}})$
. Let
$I_{n}=(u_{n},v_{n}]$
be an interval from these which maximizes the number of primes
$p\in I_{n}$
such that every prime divisor of
$n-p$
is
${>}n^{\unicode[STIX]{x1D6FE}}$
. By the pigeonhole principle, the number of such primes
$p$
in
$I_{n}$
is
$\gg n^{\unicode[STIX]{x1D6FE}}/(\log ^{2}n)$
. Let
$N_{1}$
be such that
$n\geqslant N_{1}$
implies that this number is
${>}\lfloor 1/\unicode[STIX]{x1D6FE}\rfloor$
. Thus, for
$n\geqslant \max \{N_{0},N_{1}\}$
, we have that there is an interval
$I_{n}=(u_{n},v_{n}]\subseteq (n/2,3n/4]$
, with
$v_{n}-u_{n}<n^{\unicode[STIX]{x1D6FE}}$
, such that there are more than
$1/\unicode[STIX]{x1D6FE}$
primes
$p\in I_{n}$
where every prime divisor of
$n-p$
is
${>}n^{\unicode[STIX]{x1D6FE}}$
.
Fix an integer
$n\geqslant \max \{N_{0},N_{1}\}$
and fix
$p\in I_{n}$
with
$n-p$
having every prime divisor
${>}n^{\unicode[STIX]{x1D6FE}}$
. Let
$p^{\ast }$
denote the expression in (3) with
$k$
replaced by
$p$
. Given that
$p\in I_{n}\subseteq (n/2,3n/4]$
, there is an
$N_{2}$
such that if
$n\geqslant N_{2}$
, then
$$\begin{eqnarray}p^{\ast }=p\exp \biggl(\frac{\log p}{104\log \log p}\biggr)>n\exp \biggl(\frac{\log n}{105\log \log n}\biggr).\end{eqnarray}$$
For the statement of Theorem 1, we take
$N\geqslant \max \{N_{0},N_{1},N_{2}\}$
and so that, by Lemma 4, there is a prime
$q$
dividing
$\unicode[STIX]{x1D6F7}_{p}(10)$
with
$$\begin{eqnarray}q>p^{\ast }>p>n/2\end{eqnarray}$$
and such that
$q\nmid \unicode[STIX]{x1D6F7}_{\ell }(10)$
for every integer
$\ell \in [1,n]$
with
$\ell \neq p$
. We consider the Newton polygon of
$f_{n}(x)$
with respect to the prime
$q$
. Since
$q>p^{\ast }$
, we have
$\unicode[STIX]{x1D708}_{q}(a_{k})=0$
for
$0\leqslant k\leqslant n$
. For
$1\leqslant k\leqslant n$
, we have
$$\begin{eqnarray}b_{k}=\frac{10^{k}-1}{9}=\mathop{\prod }_{\substack{ d\mid k \\ d\neq 1}}\unicode[STIX]{x1D6F7}_{d}(10).\end{eqnarray}$$
By our choice of
$q$
, we have
$\unicode[STIX]{x1D708}_{q}(b_{k})=0$
if
$k\neq p$
and
$\unicode[STIX]{x1D708}_{q}(b_{p})=t>0$
for some integer
$t$
. Thus, the Newton polygon of
$f_{n}(x)$
with respect to the prime
$q$
consists of two edges, one edge joining
$(0,0)$
to
$(p,-t)$
and one joining
$(p,-t)$
to
$(n,0)$
. Call the first of these
$E_{1}$
and the second
$E_{2}$
. The main difficulty in applying Lemma 5 is that we do not have a lot of knowledge on the value of
$t$
. However, the edge
$E_{1}$
has consecutive lattice points separated by a horizontal distance
$p/\text{gcd}(p,t)$
, and the edge
$E_{2}$
has consecutive lattice points separated by a horizontal distance
$(n-p)/\text{gcd}(n-p,t)$
. As a consequence of Lemma 5, if
$m$
is the degree of an irreducible factor of
$f_{n}(x)$
, then there are integers
$r$
and
$s$
such that
$$\begin{eqnarray}\displaystyle m=\frac{p}{\gcd (p,t)}\cdot r+\frac{n-p}{\gcd (n-p,t)}\cdot s, & & \displaystyle\end{eqnarray}$$
where
$0\leqslant r\leqslant \gcd (p,t)$
and
$0\leqslant s\leqslant \gcd (n-p,t)$
. Furthermore, assuming that
$f_{n}(x)$
is reducible, there is an irreducible factor of degree
$m\in [1,n/2]$
. We fix such an
$m$
and take advantage of (4) next.
First, we show that
$r=0$
in (4). From
$p>n/2\geqslant m$
and the primality of
$p$
, we see that if
$r>0$
, then
$\gcd (p,t)=p$
. In particular,
$\unicode[STIX]{x1D708}_{q}(b_{p})=t\geqslant p$
. We deduce that
$$\begin{eqnarray}q^{p}\leqslant q^{t}\leqslant b_{p}\leqslant 10^{p},\end{eqnarray}$$
contradicting that
$q>n/2\geqslant N/2\geqslant N_{0}/2\geqslant 1000$
. Thus,
$r=0$
in (4). Along similar lines, we cannot have
$\gcd (n-p,t)=n-p\geqslant n/4$
since this would lead to the contradiction
$$\begin{eqnarray}q^{n/4}\leqslant q^{t}\leqslant b_{p}\leqslant 10^{p}\leqslant 10^{3n/4}\;\Longrightarrow \;q\leqslant 1000.\end{eqnarray}$$
Thus,
$\gcd (n-p,t)<n-p$
. Hence,
$(n-p)/\text{gcd}(n-p,t)$
is a divisor of
$n-p$
which is
${>}1$
. Recall that every prime divisor of
$n-p$
is
${>}n^{\unicode[STIX]{x1D6FE}}$
. We set
$P_{p}$
to be a prime divisor of
$(n-p)/\text{gcd}(n-p,t)$
, so that
$P_{p}>n^{\unicode[STIX]{x1D6FE}}$
. From (4) with
$r=0$
, we deduce that
$P_{p}$
is a prime divisor of
$m$
.
The above argument holds for every
$p\in I_{n}$
with
$n-p$
having all its prime divisors
${>}n^{\unicode[STIX]{x1D6FE}}$
. Recall that there are more than
$1/\unicode[STIX]{x1D6FE}$
such
$p$
. Let
${\mathcal{P}}={\mathcal{P}}(n)$
denote the set of such
$p$
. For two distinct primes
$p_{1}$
and
$p_{2}$
in
${\mathcal{P}}$
, the primes
$P_{p_{1}}$
and
$P_{p_{2}}$
divide
$n-p_{1}$
and
$n-p_{2}$
, respectively. Note that two numbers in
$I_{n}$
differ by
${<}n^{\unicode[STIX]{x1D6FE}}$
. Therefore,
$P_{p_{1}}$
and
$P_{p_{2}}$
are
${>}n^{\unicode[STIX]{x1D6FE}}$
and
$0<|(n-p_{1})-(n-p_{2})|=|p_{2}-p_{1}|<n^{\unicode[STIX]{x1D6FE}}$
, so that
$P_{p_{1}}\neq P_{p_{2}}$
. In other words, the
${>}1/\unicode[STIX]{x1D6FE}$
primes
$P_{p}$
with
$p\in {\mathcal{P}}$
are distinct. As each such
$P_{p}$
is a prime divisor of
$m$
, we obtain that
$$\begin{eqnarray}m\geqslant \mathop{\prod }_{p\in {\mathcal{P}}}P_{p}>(n^{\unicode[STIX]{x1D6FE}})^{1/\unicode[STIX]{x1D6FE}}=n,\end{eqnarray}$$
contradicting that
$m\leqslant n/2$
. Therefore,
$f_{n}(x)$
has no irreducible factor with degree in
$[1,n/2]$
and we deduce then that
$f_{n}(x)$
is irreducible for all integers
$n\geqslant N$
.
