Proof. Let $\mathfrak {p}$ be a prime in K over p and set $e= v_{\mathfrak {p}}(p)$ . We aim to show $e=n$ . Of course, a priori, one has $e\leq n$ . Let $\alpha $ be a root of f in K. From $f(\alpha )=0$ , using the p-Eisenstein condition, we find $\mathfrak {p}$ divides $(\alpha )$ and, therefore, $v_{\mathfrak {p}}(\alpha ^n)\geq n$ . Moreover, $v_{\mathfrak {p}}(a_0)=e$ and $v_{\mathfrak {p}}(a_i\alpha ^i)\geq e+1$ for $i=1,\ldots ,n-1$ , which implies ${v_{\mathfrak {p}}(\alpha ^n)=e}$ . It follows that $n\leq e$ , which completes the proof.

Proof. Let $r_1\in \{1,2,\ldots , q_1-1\}$ and $r_2\in \{1,2,\ldots , q_2-1\}$ be fixed. Then, $p\ge q_1^2q_2^2$ implies

$$ \begin{align*}p-r_1q_1-r_2q_2 \ge q_1^2q_2^2 -(q_1-1)q_1-(q_2-1)q_2 \ge (q_1^2-1)(q_2^2-1).\end{align*} $$

By the Frobenius coin-exchange problem, since $q_1^2$ and $q_2^2$ are coprime, and

$$ \begin{align*}p-r_1q_1-r_2q_2\ge (q_1^2-1)(q_2^2-1),\end{align*} $$

there exist nonnegative integers $t_1, t_2$ such that

$$ \begin{align*}p-r_1q_1-r_2q_2 = q_1^2t_1+q_2^2t_2.\end{align*} $$

Then,

$$ \begin{align*}p = q_1(q_1t_1+r_1)+q_2(q_2t_2+r_2) = q_1u+q_2v,\end{align*} $$

where $u = q_1t_1 + r_1$ and $v = q_2t_2 + r_2$ with $q_1\nmid u$ and $q_2\nmid v$ .

Proof. Suppose q is a norm. Then, there is a prime $\mathfrak {q}$ in K such that $N(\mathfrak {q})=q$ . This means $|\mathcal {O}_K/\mathfrak {q}|=q$ and, hence, $\mathcal {O}_K/\mathfrak {q}\cong \mathbb {F}_q$ . Let $\alpha $ be a root of $f(x)$ in K and consider $\overline {\alpha }$ , the image of $\alpha $ under the reduction map $\mathcal {O}_K\to \mathcal {O}_K/\mathfrak {q}$ . Since $f(\alpha )=0$ , we must have $f(\overline {\alpha })=0$ in $\mathbb {F}_q$ , which proves the result.

Proof of Lemma 1.1

Suppose p is totally ramified and we can write $p=a+b$ as in the statement of the result. By way of contradiction, suppose K is norm-Euclidean. By hypothesis, $(p)=\mathfrak {p}^n$ , where $N(\mathfrak {p})=p$ . It follows that $p=u\pi ^n$ in K for some $u\in \mathcal {O}_K^\times $ and some $\pi \in \mathcal {O}_K$ irreducible with $N(\pi )=p$ . Since a is an nth power residue modulo n, there exists $x\in \mathbb {Z}$ such that $x^n\equiv a\pmod {p}$ . Using the norm-Euclidean condition, we find $x=\gamma \pi +\rho $ for some $\gamma ,\rho \in \mathcal {O}_K$ with $|N(\rho )|<|N(\pi )|=p$ . We have $x\equiv \rho \pmod {\pi }$ and, hence, $x\equiv \rho ^\sigma \pmod {\pi }$ for any embedding $\sigma :K\to \mathbb {C}$ . This leads to the congruence $a\equiv x^n\equiv N(\rho )\pmod {p}$ . We have $0<a<p$ and $-p<N(\rho )<p$ . Thus, either $N(\rho )=a$ or $N(\rho )+p=a$ . This implies one of $\{a,-b\}$ is a norm, which is a contradiction.

Proof. Let $\mathcal {A} := [-X,X]^n\cap \mathbb {Z}^n$ . Choose the maximal $k\in \mathbb {Z}^+$ such that

$$ \begin{align*} \mathcal{B} := (-km,km]^n\cap\mathbb{Z}^n\subseteq \mathcal{A}. \end{align*} $$

The set $\mathcal {B}$ is chosen so that

$$ \begin{align*} \#\{a\in\mathcal{B}\mid a\ \mod{m}\in S\} = |S|(2k)^n. \end{align*} $$

Using the binomial theorem,

$$ \begin{align*} \bigg(\frac{X}{m}\bigg)^n \ge k^n \ge \bigg(\frac{X}{m}-1\bigg)^n = \bigg(\frac{X}{m}\bigg)^n+O\bigg(n2^n\bigg(\frac{X}{m}\bigg)^{n-1}\bigg) \end{align*} $$

and, therefore,

$$ \begin{align*} \#\{a\in\mathcal{B}\mid a\ \mod{m}\in S\}= \frac{|S|}{m^n}(2X)^n+O(n 2^n m(2X)^{n-1}). \end{align*} $$

Next, one bounds

$$ \begin{align*} \#(\mathcal{A}\setminus\mathcal{B}) \leq (2X+1)^n-(2km)^n \ll n2^n m(2X)^{n-1}. \end{align*} $$

The result follows.

Proof. This is an application of Lemma 3.1 with the modulus $m=q_1\cdots q_t p^2$ . By Remark 3.2, we can determine the density $|S|/m^n$ for each prime power separately. The condition that f is p-Eisenstein corresponds to

$$ \begin{align*} &a_0\ \mod{p^2}\in\{p,2p,\ldots,(p-1)p\}, \\ &a_i\ \mod{p^2}\in\{0,p,\ldots,(p-1)p\},\;i=1,\ldots,p-1. \end{align*} $$

Therefore, the density mod $p^2$ equals $(p-1)p^{n-1}/p^{2n}$ in agreement with (3.1). The values of $C_q(n)$ are correct tautologically.

Proof. The count proceeds by inclusion–exclusion. We start with all polynomials, then remove the polynomials that are multiples of $(x-a)$ for $a\in \mathbb {F}_p$ . Therefore, the number of monic polynomials in $\mathbb {F}_p[x]$ of degree n with no roots equals

$$ \begin{align*} \sum_{k=0}^n (-1)^k{p\choose k}p^{n-k}. \end{align*} $$

Note that as ${p\choose k}=0$ whenever $k>p$ , we find that for $n\geq p$ ,

$$ \begin{align*} \sum_{k=0}^n (-1)^k{p\choose k}p^{n-k} =\sum_{k=0}^p (-1)^k{p\choose k}p^{n-k} = p^n \sum_{k=0}^p {p\choose k} \bigg(\frac{-1}{p}\bigg)^k = p^n\bigg(1-\frac{1}{p}\bigg)^p. \\[-46pt] \end{align*} $$

Proof. First, note that $f(k) = {p\choose k}/p^k$ is a decreasing function. Indeed, for $k\le p-1$ ,

$$ \begin{align*} \frac{f(k)}{f(k+1)} = \frac{(k+1)p}{p-k}> 1 \end{align*} $$

for all $k\le p-1$ . Since $f(k) = 0$ for $k> p$ and $f(k)> 0$ for $k\le p$ , it follows that $f(k)$ is decreasing. Since $f(k)$ is decreasing and $A_p(n)$ is an alternating sum of positive decreasing terms, for $n\ge 2$ ,

$$ \begin{align*} \frac{{p\choose 2}}{p^2} - \frac{{p\choose 3}}{p^3} \le \frac{A_p(n)}{p^n} \le \frac{{p\choose 2}}{p^2}. \\[-42pt] \end{align*} $$

Proof of Theorem 1.2

Adopt the notation from the statement of the theorem. Further, write $N_{p,n}(X)$ to denote the number of $f\in \mathcal {F}_{p,n}$ with $\operatorname {\mathrm {Ht}}(f)\leq X$ . We have $N_{p,n}(X)\sim E(p)(2X)^n$ , where $E(p)$ is given in (3.1). This follows from [Reference Dubickas5] or alternatively, from Proposition 3.3 with $t=0$ .

First, we will establish the lower bound $\liminf _{X\to \infty }\delta _{p,n}(X)\geq 2/27$ . Assume ${p\neq 7,11,19}$ . By Lemma 2.2, we can write $p=2u+3v$ with $(2,u)=1$ and $(3,v)=1$ for $p\ge 36$ . One can then manually check that the only examples of primes up to 36 that cannot be expressed in such a way are $p = 7, 11, 19$ . Therefore, provided $f(x)$ has no roots in $\mathbb {F}_2$ or $\mathbb {F}_3$ , Heilbronn’s criterion applies. (Recall Lemma 1.1 and the discussion in Section 2.) Write $N^*_{p,n}(X)$ to denote the counting function for this collection of polynomials. Using Proposition 3.3 with $q_1=2$ , $q_2=3$ ,

$$ \begin{align*} N^*_{p,n}(X)\sim E_p(n)C_2(n)C_3(n)(2X)^n , \end{align*} $$

and therefore, via Lemma 4.1 with $n\geq 3$ ,

$$ \begin{align*} \liminf_{X\to\infty} \delta_{n,p}(X)\geq C_2(n)C_3(n)= (1/4)(8/27)=2/27. \end{align*} $$

In the case where $p\in \{7,11,19\}$ , we can write $p=2u+5v$ with $(2,u)=1$ and $(5,v)=1$ . The same approach proves

$$ \begin{align*} \liminf_{X\to\infty}\delta_{n,p}(X)\geq C_2(n)C_5(n)\geq(1/4)(8/25)>2/27. \end{align*} $$

Indeed, by Lemma 4.2, as $n\geq 3$ is odd, one has $C_5(n)\geq 8/25$ .

It remains to establish a lower bound $\delta _{p,n}(X)\geq 1-\varepsilon (p)$ , where $\varepsilon (p)\to 0$ . We may assume that p is large. Choose Y maximal such that $Y^4<p$ . Let $q_1<\cdots <q_t\leq Y$ be all the primes less than Y. In particular, Lemma 2.2 applies to any pair of primes in $Q := \{q_1,\ldots ,q_t\}$ and we have $t=\pi (Y)\leq \pi (p^{1/4})$ . Before proceeding with the final estimate, observe that by Lemma 4.2,

$$ \begin{align*} D := \max_{j=1,\ldots,t}\bigg\{\frac{C(q_j)}{1-C(q_j)}\bigg\} \le 1. \end{align*} $$

We wish to bound from above the number of p-Eisenstein polynomials with $\operatorname {\mathrm {Ht}}(f)\leq X$ such that Heilbronn’s criterion does not apply for any pair of primes in Q. This means that f has no root modulo q for at most one $q\in Q$ . Using Proposition 3.3 in the situation where $\{q\in Q\mid f \text { has a root in }\mathbb {F}_q\}$ equals Q, $Q\setminus \{q_1\}$ , $Q\setminus \{q_2\}$ and so on, we obtain

(5.1) $$ \begin{align} 1-\liminf_{X\to\infty}\delta_{n,p}(X) & \leq \prod_{i=1}^t(1-C(q_i))+ \sum_{j=1}^tC(q_j)\bigg((1-C(q_j))^{-1}\prod_{i=1}^t(1-C(q_i))\bigg) \nonumber\\ & \leq (1+tD)\prod_{i=1}^t(1-C(q_i)) \nonumber\\ & \leq (1+\pi(p^{1/4}))\bigg(\frac{3}{4}\bigg)^{\pi(p^{1/4})}=:\varepsilon(p). \end{align} $$

In the last step, we have used the fact that $C_p(n)\ge 1/4$ for $p\geq 2$ , which follows from Lemma 4.2.

Proof of Theorem 1.3

Let $Y>0$ be a parameter to be chosen later. Let $\mathcal {F}^*_{p,n}$ denote the subset of $\mathcal {F}_{p,n}$ consisting of polynomials for which there exist primes $q_1<q_2\leq Y$ that are not norms in K. Applying the argument from the proof of Theorem 1.2 leading up to (5.1), we find that the lower density of $\mathcal {F}^*_{p,n}$ in $\mathcal {F}_{p,n}$ is bounded below by $1-\hat {\varepsilon }(p)$ , where

$$ \begin{align*} \hat{\varepsilon}(p) := (1+\pi(Y))(\tfrac{3}{4})^{\pi(Y)}. \end{align*} $$

Set $g := \gcd (n,p-1)$ . Next, we show that Heilbronn’s criterion applies when g is small enough compared with p. Let $f\in \mathcal {F}_{p,n}^*$ . Then, there exist primes $q_1<q_2\leq Y$ that are not norms in K. Let $\psi $ be a primitive Dirichlet character modulo p of order g, so that $\psi (u)=1$ if and only if u is an nth power residue modulo p. Note that there are $(p-1)/g$ elements of $(\mathbb {Z}/p\mathbb {Z})^\times $ that are nth power residues modulo p.

Set $X := p/q_1-2q_2$ . Assume $Y<p/4$ so that $X<p$ . For the moment, assume we can find a positive integer $u<X$ such that

(6.1) $$ \begin{align} (u,q_1)=1, \quad q_1 u\equiv p\pmod{q_2}, \quad \psi(uq_1)=1. \end{align} $$

Since $u<p/q_1$ , this implies we can write $p=uq_1+vq_2$ with $v>0$ . Observe that Heilbronn’s criterion applies, except possibly when $q_2\mid v$ . In the case where $q_2\mid v$ , we try $p=(u+q_2)q_1+(v-q_1)q_2$ , which works unless $q_1\mid u+q_2$ . If this is the case, we try $p=(u+2q_2)q_1+(v-2q_1)q_2$ which is forced to work. Note that $u<X$ implies $u<u+q_2<u+2q_2<p/q_1$ and, hence, the aforementioned expressions all involve positive integers.

Let us count the number of $u<X$ satisfying (6.1). Using standard techniques, this count equals

(6.2) $$ \begin{align} X\frac{q_1-1}{q_1}\cdot\frac{1}{q_2}\cdot\frac{1}{g}+O(m^{1/2}\log m), \end{align} $$

where the error term comes from an application of the Pólya–Vinogradov inequality to a Dirichlet character of modulus $m=p q_1 q_2$ . Indeed, one sums the product of the following indicator functions over $u < X$ :

$$ \begin{align*} \phi_0(u) &= \begin{cases} 1 & \text{if } \mathrm{gcd}(u,q_1)=1,\\ 0 & \text{if }\mathrm{gcd}(u,q_1)>1, \end{cases} \\ \frac{1}{\phi(q_2)}\sum_{\chi\text{ mod }q_2}\chi(uq_1)\chi(p)^{-1} &= \begin{cases} 1 & \text{if } q_1 u\equiv p\pmod{q_2},\\ 0 & \text{otherwise}, \end{cases} \\ \frac{1}{g}\sum_{k=1}^g\psi^k(uq_1) &= \begin{cases} 1 & \text{if } \psi(uq_1)=1, \\ 0 & \text{otherwise}. \end{cases} \end{align*} $$

In the above, $\phi _0$ is the principal character modulo $q_1$ , the sum $\sum _{\chi \text { mod }q_2}$ is taken over all Dirichlet characters modulo $q_2$ and $\psi $ is the character modulo p defined above.

To guarantee that $u<X$ satisfying (6.1) exists, we must have the main term of (6.2) strictly greater than the error term. Using $q_1\geq 2$ and the definition of X, the following condition suffices:

$$ \begin{align*} \frac{1}{2}\bigg(\frac{p}{q_1 q_2}-2\bigg)\frac{1}{g}>Cm^{1/2}\log m , \end{align*} $$

where C is the constant from Pólya–Vinogradov. Using $m=p q_1 q_2$ with $q_1,q_2\leq Y$ , and some simple manipulation, the sufficient condition becomes

$$ \begin{align*} g<\frac{p^{1/2}}{2C Y^3\log(pY^2)} -\frac{1}{C p^{1/2}\log{p}}. \end{align*} $$

It suffices to prove the theorem when p is sufficiently large, and the result follows for large p upon choosing $Y=(\log p)^{1/4}$ .

Proof of Corollary 1.4

First, suppose n is odd. From Theorem 1.2,

$$ \begin{align*} \liminf_{X\to\infty}\delta_{5,n}(X)\geq 2/27. \end{align*} $$

Since $\mathcal {F}_{5,n}$ is of positive density inside $\mathcal {F}_n$ , the set of all monic $f\in \mathbb {Z}[x]$ with ${\deg (f)=n}$ , the result follows.

Next, suppose n is even. We would like to invoke Theorem 1.3. We know there is a $p_0$ such that $\hat {\varepsilon }(p)<1$ and $2<\sqrt {p}/(\log {p})^2$ when $p\geq p_0$ . To invoke the theorem, we need a prime $p\geq p_0$ such that $\gcd (p-1,n)$ is small enough. We claim there exist infinitely many primes p satisfying the condition. Indeed, when $p\equiv -1\pmod {2n}$ , one finds $\gcd (p-1,n)=2$ . Choosing such a prime with $p\geq p_0$ allows us to conclude that

$$ \begin{align*} \liminf_{X\to\infty}\delta_{p,n}(X)>0, \end{align*} $$

which completes the proof.