The existence of a polynomial of degree $n$ with $m$ real roots when $m\equiv n \pmod 2$.

There probably isn't an entirely elementary proof of this statement (e.g., explicit demonstration of such a polynomial for a given $m$ and $n$). Nevertheless, it's easy to process the heuristic proof of why the result is true, and then not all that much harder to give a procedure for writing one down explicitly.

The heuristic is pretty straight-forward: Choose any polynomial in $\mathbb{Q}[x]$ with the desired number of real and complex roots (which of course is trivial), and then perturb the coefficients by small rational amounts until you land on an irreducible polynomial. Since the roots of a polynomial depend continuously on its coefficients, there exists an $\varepsilon$ small enough such that if you perturb each coefficient by at most $\varepsilon$, the number of real and imaginary roots of the polynomial remain unchanged by such a perturbation.

David Speyer's comment fills in the details of the rest of the construction nicely: Given $m$ and $n$ as above, choose a polynomial $h$ with the right number of real and complex roots, and let $\varepsilon$ be as above. Choose an irreducible polynomial $g$ of degree $n$ over (say) $\mathbb{F}_2$ (the existence of such a $g$ is not hard, but not terribly obvious). The goal is to perturb the coefficients of $h$ by a small amount to get a new polynomial which reduces to $g$ mod 2, guaranteeing its irreducibility. We achieve this as follows: Let $N=\lceil\frac{2}{\varepsilon}\rceil$, and let $f$ be the polynomial obtained by rounding each coefficient of $Nh$ to the nearest integer which agrees mod 2 with the corresponding coefficient of $g$. Then $f$ (or $f/N$) is irreducible and has been perturbed by a small enough amount from $h$ to maintain the right number of real and complex roots.

As an example, take $n=7$ and $m=5$. We can choose $$ g=x^7+x+1 $$ and $$ h=x(x^2-1)(x^2-4)(x^2+1)=x^7-4x^5-x^3+4x. $$ To be safe and convenient, take $\varepsilon=.02$ and hence $N=100$. Now $$ 100h=100x^7-400x^5-100x^3+400x $$ still has $n=7$ and $m=5$, as does the very very close polynomial $$ \boxed{f:=101x^7-400x^5-100x^3+399x+1.} $$ Since $f$ reduces to $g$ mod 2, $f$ is irreducible and has the right values of $m$ and $n$, as desired.

The parity modulo $2$ comes from the fact that complex roots of polynomials with real coefficients occur in pairs. If we choose $m$ rational roots and $n-m$ complex (or real nonrational) roots, we should be able to construct such a polynomial. For example $f(x)\in\mathbb{Z}[x]$ $$ f(x)=\prod_{k=0}^{n-1}(x-a_k) \qquad \text{for} \qquad a_k = \left\{\matrix{ k & 0\le k<m \\\\ (-1)^k\bigg\lfloor1+\frac{k-m}{2}\bigg\rfloor \quad& m\le k<n }\right.$$ However, this is not irreducible. We need to play around a little more to get an irreducible $f$.

Here are some more examples: $$ \matrix{ f(x)&\text{degree }n&m~(n\text{ odd})&m~(n\text{ even})&\\ x^n-1&\quad n\quad&1&2&\text{reducible for }n>1!\\ x^n-2&\quad n\quad&1&2\\ \Phi_k(x)&\quad \phi(k)\quad&\delta_{1k}&\delta_{2k}&\\ x^2-x-1&2&-&2\\ x^n-x-1&n&1&2&\text{for }n>1\\ } $$

What about taking the Lagrange interpolating polynomial for a "zig-zag" set of data points such as $$ (x_k,~y_k)=\left(h(k),~(-1)^k\right) \qquad \text{for} \qquad 1\le k\le n $$ for some increasing rational function $h$ which guarantees no rational roots of $f$? This has $n$ real irrational roots.

Finally, here is a candidate for what you need: $$ f(x)=x^{n-m}\prod_{k=1}^{m}(x+k)-\frac1{(2n)!^n} $$ One could also perturb a Lagrange interpolating polynomial as above, but with $m+1$ data points (with $m$ crossings of the $x$-axis) and choose a perturbation that is not only small, as attempted above, but also perhaps utilizing a unique prime somewhere to guarantee irreducibility from Eisenstein's criterion. Another candidate: $$ f\left(x\right)=\frac1{N!}+(2x)^{n-m}\prod_{k=1}^{m}\left(1-\frac{4x^2}{p_k}\right) $$ where $p_k$ is the $k$th odd prime. This is irreducible for $N\in\mathbb{N}$ and has the desired properties for $N$ sufficiently large.

Suppose $f = \sum_{j=0}^n c_j X^j \in {\mathbb Z}[X]$ with degree $n$, having $m$ distinct real roots and $n-m$ distinct non-real complex roots. Let $C$ be a set consisting of disjoint small circles around each root of $f$. By the argument principle, if $g \in {\mathbb Q}[X]$ of degree $n$ and $\max_{z \in C} |g(z)| < \min_{z \in C} |f(z)|$, then $f+g$ has exactly one root in each of the circles, and in particular has exactly $m$ real roots. In particular, take $g = (X^n + p)/p^2$ where $p$ is a sufficiently large prime, and note that $f+g$ is irreducible in ${\mathbb Q}[X]$ by Eisenstein's criterion.

If you don't want a specific formula for the polynomial then it is easy to see that examples can be constructed. The basic principle is very simple:

• the roots (for irreducible $f$) are transversal intersections of the graph of $f(x)$ with the $x$ axis and are determined by what $f$ looks like in the real topology. One can draw (to any desired accuracy) a picture of $f$ including approximate location of roots, location of extrema, approximate slope and curvature on various intervals, or other desired geometric characteristics and this geometric picture is equivalent to inequalities defining an open set (in the real topology) in the space of coefficients.

• irreducibility is a number-theoretic phenomenon and can be enforced by $p$-adic conditions. The Eisenstein criterion at one prime will do, for example.

• the p-adic and real metrics are sufficiently independent of each other that both conditions can be satisfied. In the (real-number topology) open set of coefficients defining the geometric conditions, there will be infinitely many rational points satisying the p-adic conditions.