Heilbronn gave a sufficient condition for a number field with a totally ramified prime to fail to be norm-Euclidean. We say that Heilbronn’s criterion applies to a polynomial f if it applies to the number field $K=\mathbb {Q}[x]/(f)$
generated by f. Suppose $n\geq 3$
is odd and $p\geq 5$
is prime with $\gcd (p-1,n)=1$
. Let $\mathcal {F}_{p,n}$
denote the collection of monic polynomials $f\in \mathbb {Z}[x]$
of degree n that are Eisenstein at the prime p. Order the polynomials by the natural height $\operatorname {\mathrm {Ht}}(f)$
. Define $\delta _{p,n}(X)$
to be the proportion of polynomials $f\in \mathcal {F}_{p,n}$
with $\operatorname {\mathrm {Ht}}(f)\leq X$
for which Heilbronn’s criterion applies. Then, $$ \begin{align*} \liminf_{X\to\infty} \delta_{p,n}(X)\geq \max\{\tfrac{2}{27},\;1-\varepsilon(p)\}, \end{align*} $$
where $\varepsilon (p)\to 0$
and is effectively computable. In particular, the lower density tends to $1$
as $p\to \infty $
uniformly in n. We also give a version of this result where we weaken the condition on $\gcd (p-1,n)$
. As a corollary, we show that given an integer $n\geq 2$
, a positive proportion of Eisenstein polynomials of degree n fail to generate norm-Euclidean fields.