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}$?


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.


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.

  • 1
    $\begingroup$ Some qualification of this answer seems needed. The question fixes the degree $n$. For example when $n=1$ or $n=2$ this answer is not correct. $\endgroup$ – Lucia Apr 26 '15 at 21:57
  • $\begingroup$ @Lucia You are right, this is asymptotic for large degree. The $1/e$ is the answer to "what fraction of permutations in $S_n$ is fixed-point free" - obviously this is not $1/e$ in $S_1$ or $S_2.$ $\endgroup$ – Igor Rivin Apr 26 '15 at 22:00
  • 1
    $\begingroup$ It's still a tiny bit tricky. What you're thinking of is that a random polynomial, which will have Galois group $S_n$ typically will have this feature as you vary over $p$. But for a fixed prime, there is a positive probability that the discriminant is a multiple of $p$, and this I think will affect some calculations. I didn't think this through fully, so maybe you're fully correct, but it's just not immediate why. $\endgroup$ – Lucia Apr 26 '15 at 22:07
  • $\begingroup$ @Lucia your point is well-taken. In fact, the probability that the polynomial is not-square-free mod $p$ is $O(1/p),$ so what I say is true asymptotically, but not quite true mod any fixed $p.$ $\endgroup$ – Igor Rivin Apr 26 '15 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.