\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\def\\{\cr}
\def\({\left(}
\def\){\right)}
\def\cD{\mathcal D}
\def\cI{\mathcal I}
\def\cP{\mathcal P}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\def\mand{\qquad \mbox{and} \qquad}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
On the Number of Polynomials of Bounded \\
\vskip .12in
Height that Satisfy the Dumas Criterion
}
\vskip 1cm
\large
Randell Heyman\\
Department of Computing \\
Macquarie University \\
Sydney, NSW 2109 \\
Australia\\
\href{mailto:randell@unsw.edu.au}{\tt randell@unsw.edu.au}
\end{center}

\vskip .2 in


\begin{abstract}
We study integer coefficient polynomials of fixed degree and maximum height $H$ that are irreducible by the Dumas criterion. We call such polynomials \emph{Dumas polynomials}. We derive upper bounds on the number of Dumas polynomials as $H \rightarrow \infty$.
We also show that, for a fixed degree, the density of Dumas polynomials in the set of all irreducible integer coefficient polynomials is strictly less than 1.
\end{abstract}


\section{Introduction}
The two most well-known polynomial irreducibility criteria based on coefficient primality divisibility are probably the Eisenstein criterion and the Dumas criterion. In the last decade and a half, results regarding the density of polynomials that satisfy the Eisenstein criterion have been obtained (see, for example, Dobbs and Johnson \cite{DoJo}, Dubickas \cite{Dub}, and the author and
Shparlinski \cite{Hey,Hey2}). In this paper we explore densities of polynomials that satisfy the Dumas criterion.  This criterion is a sufficient condition for polynomial irreducibility over $\Z$ (and hence $\Q$). It can be thought of as a generalization of the Eisenstein criterion since the Eisenstein criterion is an easy consequence of the Dumas criterion.


We can now state the Dumas criterion. Let
\begin{align}\label{f(x)}
 f(x)=\sum_{i=0}^nA_ix^i \in \Z[x]
 \end{align}
  be such that $A_0A_n \neq 0$.

If the Newton polygon for $f$ with respect to any prime is a single segment and contains no points with integer coordinates except the end points, then $f$ is irreducible.
The proof of the Dumas criterion is often based on the Newton diagram for a polynomial. The Newton diagram is similar to, but lesser known than, the Newton polygon. Construction of the Newton diagram and the proof of the Dumas criterion can be found in the book of Prasolov \cite[Subsection~2.2.1]{Pra}. Interested readers can also consult the 1906 paper by Dumas \cite{Dum}.

By way of example, the polynomial $f(x)=x^4+8$ with respect to the prime number 2 has a Newton polygon without integer coordinates (other than endpoints). Therefore $f$ is irreducible by the Dumas criterion. By contrast, the reducible polynomial $f(x)=x^4+4$ cannot satisfy the Dumas criterion since the coordinate $(2,2)$ or $(2,0)$ will appear in any Newton polygon of $f$. So the determination of irreducibility using the Dumas criterion is not possible for $f(x)=x^4+4$.
For integers $n \ge 2$ and $H \ge 1$ let $\cD_n(H)$ be the number of Dumas polynomials of height at most $H$, that is, satisfying $\max\{|A_0|,\dots,|A_n|\}\le H$. Our main result is the following theorem.
\begin{theorem}\label{firstmain}
We have

$$\cD_n(H) \le (2H)^{n+1}\tau_n + \begin{cases}
O\(H^2 (\log H)^2\),&\quad \text{if $n=2$};\\
O\(H^n\),&\quad  \text{if $n\ge 3$},
\end{cases}$$
where

$$\tau_n=\begin{cases}
1-\prod_{p~\mathrm{prime}}\(1-\frac{1}{p}\)^2\(1+\frac{2}{p}\),&\quad \text{if $n=2$}; \\
1-\frac{1}{\zeta(n-1)},&\quad  \text{if $n \ge 3$}.
\end{cases}$$
\end{theorem}

We have already noted that the number of polynomials that satisfy the Eisenstein criterion, calculated by the author and Shparlinski~\cite{Hey}, provides a lower bound on $\cD_n(H)$. Specifically,
\begin{lemma}
\label{lem:eisenstein}
We have
$$
\cD_n(H)\ge\vartheta_d 2^d H^d+\left\{\begin{array}{ll}
O\(H^{d-1}\),&\quad \text{if $d>2$}, \\
O(H(\log H)^2),&
\quad  \text{if $d=2$},
\end{array}\right.
$$
where
$$
\vartheta_d =  1-\prod_{p~\mathrm{prime}}
\(1- \frac{p-1}{p^{d+1}}\).
$$
\end{lemma}
We note the appearance of values of the zeta function in the main term of the estimate in Theorem \ref{firstmain}. This arises from the fact that estimates of the probability of $k$-tuples of positive integers being relatively prime play a major role in the proof of Theorem \ref{firstmain}.

In Theorem \ref{firstmain} we also observe that the result for quadratics is quite different to the result for higher degree polynomials. For polynomials of degree greater than 2 we can use
gcd conditions about the coefficients of the non-leading and non-constant terms to enumerate the number of Dumas polynomials. This is clearly not possible for quadratics and we are forced to consider the coefficients of the leading and non-constant terms as well.

\section{Notation}
Let $f(x)$ be as in \eqref{f(x)}. We define the height of the polynomial $f$ as
\begin{equation*}
H(f) = \max_{0\leq i\leq n} |A_i|.
\end{equation*}
As usual the Riemann zeta function is given by
$$\zeta(s)=\sum_{k=1}^\infty \frac{1}{k^s},$$
for all complex numbers $s$ whose real part is greater than 1.
We also recall that the notation $U=O(V)$ is equivalent to the assertion that the inequality $|U| \le c|V|$ holds for some constant $c>0$.


\section{Preparations}
\begin{lemma}\label{gcdends}
Fix $n=2$. Suppose that $f(x)$ is as in \eqref{f(x)} with $H(f) \le H$ and $A_{1} \ne 0.$ If $f$ is a Dumas polynomial then
$\gcd(A_j,A_k) \ne 1$  for every $j,k \in \{0,1,2\}$.
\end{lemma}

\begin{proof}
Suppose there exists a polynomial with the property that $\gcd(A_j,A_k) = 1$ for some distinct $j,k \in \{0,1,2\}$. If for any prime $p$ we have $p\mid  A_{1}$ then clearly $p \nmid A_0$ and $p \nmid A_2$. So the Newton passes through the point $(1,0)$, since it lies on the segment from $(0,0)$ to $(2,0)$. Thus $f$ is not a Dumas polynomial. On the other hand, if for any prime $p$ we have $p \nmid A_{1}$ then the Newton polygon includes the point $(1,0)$. So again $f$ is not a Dumas polynomial, completing the proof.
\end{proof}

\begin{lemma}\label{gcdmiddle}
Fix $n \ge 2$. Suppose $f(x)$ is as shown in \eqref{f(x)} with $H(f) \le H$ and $A_{1}A_{2}\cdots A_{n-1} \ne 0.$ If $f$ is a Dumas polynomial then
$\gcd(A_1,A_2,\ldots,A_{n-1}) \ne 1$.
\end{lemma}

\begin{proof}
Suppose $f$ is as described above with $\gcd(A_1,A_2,\ldots,A_{n-1})=1$. For any prime $p$ we must have $p \nmid A_i$ for some $1 \le i \le n-1$. So the Newton diagram for $f$ with respect to $p$ includes the point $(A_i,0)$. Thus the Newton diagram with respect to any prime $p$ does not consist of a single segment. Therefore $f$ is not a Dumas polynomial.
\end{proof}


\section{Proof of Theorem \ref{firstmain}}
Let $f(x)$ be as in \eqref{f(x)} with $H(f) \le H$.
We prove Theorem \ref{firstmain} for $n=2$ and $n \ge 3$ separately.

We start with the $n=2 $ case. To ease notation we use $\gcd^*(A_0,A_{1},A_{2}) \ne 1$ to mean that $A_0,A_{1}$ and $A_{2}$ are not pairwise coprime,
that is, $\gcd(A_0,A_{1})\ne 1$ or $\gcd(A_0,A_{2})\ne 1$ or
$\gcd(A_{1},A_{2})\ne 1$. We also use $\gcd_*(A_0,A_{1},A_{2}) = 1$ to
mean that  $A_0,A_{1}$ and $A_{2}$ are pairwise coprime, that is, 
$\gcd(A_0,A_{1})=\gcd(A_0,A_{2})=\gcd(A_{1},A_{2})= 1$.

There are $O(H^{2})$ polynomials with $A_{0}A_{1}A_2=0.$ If we have $A_{0}A_{1}A_2 \ne 0$ then, by Lemma \ref{gcdends}, the polynomial $f$ can only be a Dumas polynomial if $\gcd^*(A_0,A_1,A_2) \ne 1$. Therefore,
\begin{align}\label{2}
\cD_{2}(H) -O(H^2)&\le \sum_{\substack{1\le |A_0|,|A_{1}|,|A_{2}| \le H \\\gcd^*(A_0,A_1,A_2) \ne 1}}1\notag\\
&= \sum_{\substack{1\le A_0,A_{1},A_{2} \le H \\\gcd^*(A_0,A_1,A_2) \ne 1}}8\notag\\
&= (2H)^3-\sum_{\substack{1\le A_0,A_{1},A_{2} \le H \\\gcd_*(A_0,A_1,A_2) = 1}}8.
\end{align}
From the paper of T$\acute{\textrm{o}}$th~\cite[Corollary~2]{Tot} we have
\begin{align*}
\sum_{\substack{1\le A_0,A_{1},A_{2} \le H \\\gcd_*(A_0,A_{1},A_{2})=1 }}1=H^3\prod_{p~\textrm{prime}} \(1-\frac{1}{p}\)^2\(1+\frac{2}{p}\)+O\(H^2(\log H)^2\),
\end{align*}
from which
\begin{align}\label{toth}
\sum_{\substack{1\le |A_0|,|A_{1}|,|A_{2}| \le H \\\gcd_*(A_0,A_{1},A_{2}) = 1}}1&=(2H)^3\prod_{p~\textrm{prime}} \(1-\frac{1}{p}\)^2\(1+\frac{2}{p}\)+O\(H^2(\log H)^2\).
\end{align}
Substituting \eqref{toth} into \eqref{2} completes the proof for the $n=2$ case.

Now fix $n\ge 3$. There are $O(H^{n})$ polynomials for which $A_1A_2\cdots A_{n-1}=0.$ If $A_1A_2\cdots A_{n-1}\ne 0$ then, by Lemma \ref{gcdmiddle}, the polynomial $f$ can only be a Dumas polynomial if $\gcd(A_1,A_2,\ldots,A_{n-1}) \ne 1$. Therefore,
\begin{align}\label{eventhm}
\cD_{n}(H)-O(H^n)&\le \sum_{\substack{1\le|A_1|,|A_2|,\ldots,|A_{n}| \le H\\\gcd(A_1,A_2,\ldots,A_{n-1}) \ne 1 }}1.
\end{align}
We infer from Nymann~\cite{Nym} that
\begin{align}\label{coprime}
\sum_{\substack{1\le |A_1|,|A_2|,\ldots,|A_{n}|\le H\\\gcd(A_1,A_2,\ldots,A_{n-1}) \ne 1 }}1&=(2H)^{n+1}\(1-\frac{1}{\zeta(n-1)}\)+O(H^{n}).
\end{align}
Substituting \eqref{coprime} into \eqref{eventhm} completes the proof for the $n \ge 3$ case. Thus Theorem \ref{firstmain} is proven.


\section{Comments}
Let $\cP_n(H)$ be the number of polynomials of degree $n$ and maximum height $H$. Let $\cI_n(H)$ be the number of irreducible polynomials of degree $n$ and maximum height $H$. Two results immediately follow from Theorem \ref{firstmain}.

Firstly, we note that $\cP_n(H)$ is precisely $(2H)(2H+1)^{n}$ and infer from
Cohen~\cite[Theorem~1]{Coh} that for $n \ge 2$
$$\lim_{H \to \infty} \frac{\cI_n(H)}{\cP_n(H)}=1.$$
Thus, for $n\ge 2$,
$$\limsup_{H \rightarrow \infty}\frac{\cD_n(H)}{\cP_n(H)}=\limsup_{H \rightarrow \infty}\frac{\cD_n(H)}{\cI_n(H)}\le\tau_n.$$

Secondly, $\tau_n<1$ for all $n\ge 2$ and so for $n \ge 2$
$$\limsup_{H \rightarrow \infty} \frac{\cD_n(H)}{\cP_n(H)} =\limsup_{H \rightarrow \infty} \frac{\cD_n(H)}{\cI_n(H)}<1.$$

Table 1 shows some calculated values of upper bounds on the limit superior of $\cD_n(H)/\cP_n(H)$ as $H$ goes to infinity. It also includes limit inferior calculations derived from a paper by the author and Shparlinski~\cite{Hey}. Specifically, for various values of $n$, lower bounds on the limit inferior of $\cD_n(H)/\cP_n(H)$ as $H$ goes to infinity. All summations are over all primes less than 100,000.

\begin{table}[h]
\begin{center}
    \caption{Some upper bounds on $\limsup\cD_nH/\cP_n(H)$ as $H \rightarrow \infty$ and lower bounds on $\liminf\cD_n(H)/\cP_n(H)$ as $H \rightarrow \infty$}
   \medskip
\medskip
    \begin{tabular}{ | c | c | c |}
    \hline
    \textrm{$n$} & Lower bound & Upper bound \\ \hline
    $2$ & 0.1677 &0.7133\\ \hline

    $3$ & 0.0556 & 0.3922 \\ \hline

    $4$&0.0224& 0.1681  \\ \hline

    $5$&0.0099& 0.0766 \\ \hline
   $6$& 0.0046 & 0.0357 \\ \hline
    $7$&0.0022 & 0.0181\\ \hline
    $8$&0.0010&0.0079 \\ \hline
    $9$&0.0005 & 0.0049 \\ \hline
    $10$&0.0003&0.0020 \\ \hline
    \end{tabular}
  \end{center}
 \end{table}
\newpage
This prompts the following question. Is it possible to obtain tighter bounds or the exact values of
$$\liminf_{H \to \infty} \frac{\cD_n(H)}{\cP_n(H)}
\mand \limsup_{H \to \infty} \frac{\cD_n(H)}{\cP_n(H)}$$
(they most likely coincide)?


We also note that it is possible to find upper bounds on $$\limsup_{H \rightarrow \infty} \cD_n(H)/\cP_n(H)$$ by directly calculating the number of Dumas polynomials for an arbitrary single segment Newton polygon that contains no points with integer coordinates other than endpoints, and then summing over all possible single segment Newton polygons that contain no points with integer coordinates other than endpoints. There are substantial problems using the inclusion exclusion principle with this approach; a Dumas polynomial with respect to more than one prime may exhibit a different Newton polygon for each of these primes. Whilst results for degree $n>3$ are obtainable without the inclusion exclusion principle, it has not been possible to find any results that are superior to Theorem \ref{firstmain}.

\section{Acknowledgment}
The author would like to thank Igor Shparlinski for numerous helpful
suggestions. The author would also like to thank the referee for
suggestions that have led to improvements in this paper.


\begin{thebibliography}{9}
%
\bibitem{Coh}
S.~D.~Cohen,
The distribution of the Galois groups of integral polynomials,
{\it Illinois J. of Math.\/} {\bf 23}~(1979), 135--152.
%
\bibitem{DoJo} D.~E.~Dobbs and L.~E.~Johnson,
On the probability that Eisenstein's criterion applies to an arbitrary irreducible polynomial, in
{\it Proc. of 3rd Intern. Conf. Advances in Commutative Ring Theory\/},
Lect. Notes in Pure and Appl. Math., Vol.~205, Dekker, 1991, pp.~241--256.
%
\bibitem{Dub}
A.~Dubickas,
Polynomials irreducible by Eisenstein's criterion,
{\it Appl. Algebra Engrg. Comm. Comput.\/} {\bf 14}~(2003), 127--132.
%
\bibitem{Dum}
G.~Dumas,
Sur quelques cas d'irr$\acute{\textrm{e}}$ductibilit$\acute{\textrm{e}}$ des polynomes $\grave{\textrm{a}}$ coefficients rationnels,
{\it J. Math. Pures Appl.\/}~{\bf(6)\/} {\bf 2}~(1906), 191--258.
%
\bibitem{Hey}
R.~Heyman and I.~E.~Shparlinski,
On the number of Eisenstein polynomials of bounded height,
{\it Appl. Algebra Engrg. Comm. Comput.\/} {\bf 24}~(2013), 149--156.
%
\bibitem{Hey2}
R.~Heyman and I.~E.~Shparlinski,
On shifted Eisenstein polynomials,
{\it Period. Math. Hungar.\/}, to appear.
%
\bibitem{Nym} J.~E.~Nymann,
On the probability that $k$ positive integers are relatively prime,
{\it J. Number Theory\/} {\bf4}~(1972), 469--473.
%
\bibitem{Pra} V.~V.~Prasolov, {\it Polynomials\/}, Springer, 2004.
%
\bibitem{Tot} L.~T$\acute{\textrm{o}}$th,
The probability that $k$ positive integers are pairwise relatively prime,
{\it Fibonacci Quart.\/} {\bf40}~(2002), 13--18.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11R09.

\noindent \emph{Keywords: } 
irreducible polynomial, Dumas criterion, coprimality.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 3 2013;
revised version received  December 12 2013.
Published in {\it Journal of Integer Sequences}, January 4 2014.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in

\end{document}