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

I came across the following fact:

Let $m$ and $n$ be natural numbers such that $n\geqslant m$ and $m\equiv n \pmod 2$. Then, there exists an irreducible polynomial $f\in\mathbb{Q}\left[X\right]$ of degree $n$ such that $f$ has exactly $m$ real roots.

I guess it is well known for algebraists. Unfortunately, I cannot find the proof of this anywhere and I do not know how to prove it. Could you help me?

-
isn't this a consequence (or rather an equivalent statement) of the fundamental theorem of algebra? –  scibuff Apr 10 '12 at 15:16
@scibuff: Irreducible? –  Did Apr 10 '12 at 15:33
Just a comment, not an answer. Write $n=m+2k$. Then the assertion is equivalent to the existence of an algebraic field extension $\Bbb Q\subset F$ such that $F$ admits exactly $m$ different embeddings into $\Bbb R$ and $2k$ different embeddings into $\Bbb C$. The equivalence is realized by looking at the minimal polynomial of an element $\alpha\in F$ such that $F=\Bbb Q(\alpha)$. Such elements exists by general results on field extensions. –  Andrea Mori Apr 10 '12 at 16:14
Thanks @JyrkiLahtonen. You know, this is one of those examples where if you had bet me at the start of the day today that I had answered this question 3 years ago, I would've taken that bet. I don't remember writing this in the slightest. :) –  Cam McLeman Mar 19 at 16:08
LOL, @Cam! I remembered your answer when a related question came up (see the link in the right margin). –  Jyrki Lahtonen Mar 19 at 16:42

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.

-
I don't think it is so hard to make rigorous. Let $f(x) \in \mathbb{R}[x]$ have the right number of roots. Let $\epsilon$ be small enough that changing any of the coefficients by $<\epsilon$ doesn't change the number of real roots. Let $p$ be prime and let $g(x)$ be an irreducible polynomial of degree $n$ modulo $p$. Let $N$ be large enough that $p/N < \epsilon$. Take $N f(x)$ and change each coefficient to the closest integer which is congruent modulo $p$ to the corresponding coefficient of $g(x)$ modulo $p$. –  David Speyer Apr 10 '12 at 16:33
Ah, very nice. Kind of a baby Krasner's lemma. –  Cam McLeman Apr 10 '12 at 16:41
+1: Sooo nice! I need to remember this. It is easy to arrange your polynomial $h$ to have constant term zero. Consequently you can always make the constant term of $f$ equal to one. So by going reciprocal we can even arrange $f$ to be monic should we so desire. –  Jyrki Lahtonen Apr 10 '12 at 17:32
@Cam McLeman I bless you for your response:) You have written that the existence of g of an arbitrary degree which is irreducible over $\mathbb{F}_2$ is not obvious. I have found the proof of this: planetmath.org/encyclopedia/… –  dawid Apr 10 '12 at 19:41

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.

-
Thanks for your hint, however I think that irreducibility is the the main difficulty here... –  dawid Apr 10 '12 at 15:37
Thanks a lot! It didn't seem to me that this polynomial can be just given by some formula. –  dawid Apr 10 '12 at 16:26
Guaranteeing no rational roots is quite a bit shy of showing irreducibility! (e.g., $(x^2-2)(x^2-3)$) –  Cam McLeman Apr 10 '12 at 16:29
The fact that the rationals are dense in the reals (and that $\mathbb{Q}[x]$ is dense in $C^1[a,b]$ encourages us to construct examples. –  bgins Apr 10 '12 at 16:32
@CamMcLeman: good point! –  bgins Apr 10 '12 at 16:32

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.

-