# Bijection with constraints between sets of polynomial

How can I show the existence (or even better: construct explicitly) of a bijection (if one exists) between the set of all polynomial that have integer coefficients and a integer root and the set of all polynomials that have positive integer coefficients and positive integer roots ?

If I drop the additional "root" constraint, the problem is very simple to solve. But with the root constraint I have no idea how to solve it, since my knowledge of algebra is rather limited. For example if I use the function $h:\mathbb{Z} \rightarrow \mathbb{N}, \ h:=\begin{cases} 2t & ,t\geqslant0\\ -2t-1 & ,t<0\end{cases}$ to map the integer coefficients bijectively to positive integer coefficients, I can find counterexample that have no integer roots whatsoever.

-

A polynomial with positive coefficients can't have a positive root - just think about what happens when you plug a positive number into such a polynomial.

-
of course...I didn't think the question through... –  temo May 14 '11 at 14:33

As has been pointed out, with the way you have worded things, there is no bijection, since one of your collections of polynomials is infinite, while the other collection is empty.

Let us look at a generalization of the problem. Suppose you have an explicit listing of two types of polynomials with integer coefficients, Type $1$ and Type $2$ (in your case, Type $1$ is all polynomials with integer coefficients, Type $2$ is positive integer coefficients).

Now suppose that you want to exhibit a bijection between Type $1$ polynomials that satisfy a certain additional condition $A$, and Type $2$ polynomials that satisfy an additional condition $B$. This will not be possible if the cardinalities of the two collections are different. So suppose for example that there are infinitely many Type $1$ polynomials that satisfy condition $A$, and infinitely many Type $2$ polynomials that satisfy condition $B$.

We can list the Type $1$ polynomials that satisfy condition $A$ as $P_1$, $P_2$, $P_3$, and so on, by letting $P_1$ be the first polynomial in the listing of Type $1$ polynomials that satisfies $A$, letting $P_2$ be the second one, and so on.

Similarly, we can list the Type $2$ polynomials that satisfy condition $B$ as $Q_1$, $Q_2$, $Q_3$, and so on by using the same strategy.

Now we get an explicit bijection between Type $1$ polynomials that satisfy $A$ and Type $2$ polynomials that satisfy $B$ by mapping $P_k$ to $Q_k$ for all $k$.

Is this bijection really explicit? Suppose we have a computer program for listing Type $1$ polynomials, and a computer program that can recognize whether a polynomial satisfies condition $A$. Suppose also that we have similar programs for Type $2$ polynomials and for recognizing condition $B$. Then we can write an explicit computer program that will produce the bijection.

In general, one cannot expect that the bijection will be given by a simple short formula. But what I have outlined is more than an existence proof, it is, under appropriate conditions, a recipe.

-