Density of polynomials which are soluble with respect to a set of primes

Question

Suppose that $p$ is a prime, and $f(x)$ is a polynomial with integer coefficients and positive degree. Then there exists an integer $n_p$ such that $p | f(n_p)$ if and only if $f(x)$ has a linear factor mod $p$; that is, $f(x) \equiv (x - r_p) g(x) \pmod{p}$ for some polynomial $g(x) \in \mathbb{Z}[x]$ and some integer $r_p$. If this is the case, say $f$ is $p$-soluble.

Let $\mathcal{P}$ be a finite set of primes, say $\mathcal{P} = \{p_1, \cdots, p_t\}$. Say $f$ is $\mathcal{P}$-soluble if $f$ is $p_j$-soluble for $j = 1, \cdots, t$. Define the set

$$\displaystyle A_{\mathcal{P},n}(N) = \{f(x) = a_n x^n + \cdots + a_0 : f \text{ is } \mathcal{P}\text{-soluble}, |a_j| \leq N \forall 0 \leq j \leq n \}.$$

Is there an asymptotic formula known for $\# A_{\mathcal{P},n}$?

Answer 1

It should be quite possible to obtain an asymptotic formula for this using standard lattice point counting and sieve techniques.

First consider the following simpler problem: Let $p$ be a prime and let $r_p \in \mathbb{F}_p$. Then the collection of $a_i$ for which the associated polynomial $f(x) = a_n x^n + \cdots + a_0$ has a root at $r_p$ modulo $p$ is a sublattice of $\mathbb{Z}^{n+1}$. Hence one can count this number quite easily using standard lattice point counting techniques.

In your case, one would obtain various collections lattices given by the different choices of $r_p$ modulo $p$ for different primes. One can count the points in these lattices as above, but one would also need to combine this with an inclusion-exclusion argument to take care of possible double counting (e.g. you need to be careful that you don't count those polynomials which have a root at both $0$ and $1$ modulo $p$ twice). This gives an asymptotic formula for your problem of the shape $$\#A_{\mathcal{P},n} \sim c_{\mathcal{P},n}N^{n+1}, \quad c_{\mathcal{P},n} > 0.$$ You would need to write out the details carefully if you would like to know the exact form of the leading constant.

Answer 2

The probability that a polynomial has a linear factor mod p is roughly $1-1/e,$ so the probability that it has a linear factor mod $r$ different primes is $(1-1/e)^r.$

EDIT To follow up on @Lucia's comment: the above is asymptotic for $n\rightarrow \infty,$ in general, the $1-1/e$ should be replaced by "the probability that a permutation in $S_n$ has a fixed point".

ANOTHER EDIT As Lucia wisely points out, for fixed primes there is a finite probability that the polynomial is not square-free, so Dedekind's theorem (used in the analysis above) does not apply. The fraction of non-square-free polynomials is bounded above by $1/p$ (since they have the form $(x-t)^2 q(x),$ there are $p$ choices of $t,$ and $p^{n-2}$ choices for the $q.$ However, this is an upper bound only, since there is double counting of polynomials which are divisible by squares of higher degree polynomials, etc.