# Minimal cardinality of a field where a polynomial has a root

Let $P(n)$ be the set of all monic polynomials of degree $n$ with integer coefficients, such that all coefficients have absolute value at most $2^n$.

Given a positive integer $n$ let us define $A(n)$ as the minimal number $m$ such that for any $f \in P(n)$ there exists a field $k$ with at most $m$ elements such that for some $x\in k$ we have $\bar f(x)=0$, where $\bar f$ is the reduction of $f$ modulo the characteristic of $k$.

Q: What is the asymptotic behaviour of $A(n)$? In particular is it true that $\liminf_{n} \frac{A(n)}{n} = 0$ ?

• Here's a heuristic that suggests not: a randomly chosen polynomial over $\Bbb F_q$ has some probability $c_q$ of not having a root, and that probability (probably) goes to $1/e$ as $q\to\infty$ by comparison with a Poisson process. Assuming independence, the probability of a randomly chosen polynomial not having a root modulo any prime up to $n$ is roughly $1/e^{n/\log n}$; since $e^{n/\log n} = o(n2^n)$, this suggests that there are still lots of polynomials in $P(n)$ without roots modulo any of those primes (or, by the same argument, in any finite field of size less than $n$). – Greg Martin Jan 16 '18 at 23:39
• Consider the polynomial $g(x)=x(x-1)(x-2)\cdots(x-n)+1$ and the number $N = {\rm lcm}(1,2,\cdots,n)$. Then $N$ is of size about $\exp(n)$ and one can take the remainder of the coefficients of $g$ modulo $N$ to obtain a monic polynomial $f$ with coefficients bounded by $\exp(n)$. This polynomial has no roots in prime fields for all $p\leq n$. Maybe there is a similar construction that takes also care of field extensions. – Andreas Thom Jan 17 '18 at 21:25

No to the final question, stealing an idea from Andreas Thom. For all primes $p$ and degrees $d$ with $p^d>m$, there is a degree $d$ monic polynomial over $\mathbb F_p$ that has no roots in any field of characteristic $p$ of order $\leq m$. Indeed, an irreducible polynomial of degree $d$ does the trick.
Applying this, for any degree $d$ with $2^d > m$, there is a degree $d$ monic polynomial over $\mathbb Z/ P_m \mathbb Z$ where $P_m= \prod_{p\textrm{ prime}, p \leq m} p$ which does not have any roots in any field of cardinality at most $m$.
We can now lift this to an integral polynomial, with coefficients $<P_m$. So any $n$ with $2^n \geq P_m$ and $2^n > m$ has $A(n)>m$. Obviously the first condition is the interesting one, so we have $$n \approx \log_2 P_m = \sum_{p \textrm{ prime}, p \leq m} \frac{\log p}{\log 2} \approx \frac{m}{\log 2}$$ by the prime number theorem.
So $A(n)$ is greater than, approximately, $n \log 2$