Estimating reducible monic polynomials of degree n with integer coefficients of height of atmost N

Question

This question is from my assignment in Sieve Theory and I am struck on it. I am following following notes on Sieve Theory: http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html

Question: For a monic integer polynomial $f(t)= t^n + a_{n-1} t +...+ a_0$ we define the height as $Ht(f)= max_j |a_j|$ . We define $R_n(N)=$ { $f(t) = t^n +a_{n-1} t +...+a_0: Ht(f) \leq N ;$ reducible over $\mathbb{Q}$} to be the set of reducible monic polynomial of degree n with integer coefficients , of height at most N. Show that for n>2, #$R_n(N) \ll_n N^{n-1/2} logN $.

Lecture 16( An application of the larger sieve: Counting Reducible Polynomials) of the above notes gives a method to estimate the $R_2(N)$. In proposition 0.2 it is proved that #$R_2(N) \ll N^{3/2} Log N.$

Attempt to generalize it for $R_n(N)$: We are given a set $A\subset \mathbb{Z}^n$ of integer vectors , contained in a box of size X: $diam A\leq X$.

We a given a set P of primes all satisfying $p\leq z$.

For all $p\in P$, we are given a set $\Omega(p) \subseteq \mathbb{Z}^n / p \mathbb{Z}^n$ of excluded residue classes mod p. Set $\omega(p) =$ # $\Omega(p)$.

First I have to find a condition when $f(t)=t^n +a_{n-1} t+ ...+a_0$ is reducible. But I am unable to do so and need help.

Then I have to find # $\Omega(p)$

Do in this I also need to prove that #$R_n(N)\leq $# $S(A,P,\Omega)$? as was proved on 3rd page of Lecture 16. Why or why not?

I hope only these 3 things are necessary to complete the proof ? Am I right?

Kindly help me with these questions.

Answer 1

Here is a sketch of a proof:

1. If a polynomial is reducible, then it must be reducible mod $p$ for every prime $p$.

2. The number of degree $n$ polynomial mod $p$ that is irreducible is (Estimating reducible monic polynomials of degree n with integer coefficients of height of atmost N) $$M_n(p) = \frac{1}{n}\sum_{d | n} \mu(d)p^{n/d}.$$

3. Note that $M_n(p) \geq \frac{1}{2n}p^n$ for large $p$.

4. So take $\Omega(p)$ to be the coefficients mod $p$ such that the polynomial is irreducible mod $p$, and apply the large sieve inequality.