The following algorithm suggests itself. Let $\alpha$ be an unknown root of a polynomial $f(x)$ of degree $n$, and $\beta$ be an unknown root of a polynomial $g(x)$ of degree $m$.
Using the equation $f(\alpha)=0$ allows us to rewrite any power $\alpha^k$ as
a linear combination of $1,\alpha,\alpha^2,\ldots,\alpha^{n-1}$. Similarly using the equation $g(\beta)=0$ allows us to rewrite any power $\beta^\ell$ as a linear
combination of $1,\beta,\beta^2,\ldots,\beta^{m-1}$. Putting these two pieces together shows that we can write any monomial $\alpha^k\beta^\ell$ as a linear combination of the $mn$ quantities $\alpha^i\beta^j, 0\le i<n, 0\le j<m.$
Denote $c_k=\alpha^i\beta^j$, where $k=mi+j$ ranges from $0$ to $mn-1$.
Next let us use the expansions of $(\alpha\beta)^t$, $0\le t\le mn$ in terms of the $c_k$:s. Let these be
$$
(\alpha\beta)^t=\sum_{k=0}^{mn-1}a_{kt}c_k.
$$
Here the coefficients $a_{tk}$ are integers. We seek to find integers $x_t,t=0,1,\ldots,mn$, such that
$$
\sum_{t=0}^{mn}x_t(\alpha\beta)^t=0.\qquad(*)
$$
Let us substitute our formula for the power $(\alpha\beta)^t$ above. The equation $(*)$ becomes
$$
0=\sum_t\sum_kx_ta_{tk}c_k=\sum_k\left(\sum_t x_ta_{kt}\right)c_k.
$$
This will be trivially true, if the coefficients of all $c_k$:s vanish, that is, is the equation
$$
\sum_{t=0}^{mn}a_{kt}x_t=0 \qquad(**)
$$
holds for all $k=0,1,2,\ldots,mn-1$. Here there are $mn$ linear homogeneous equations on the $mn+1$ unknowns $x_t$. Therefore linear algebra says that we are guaranteed to succeed in the sense that there exists a non-trivial vector
$(x_0,x_1,\ldots,x_{mn})$ of rational numbers that is a solution of $(**)$. Furthermore, by multiplying with the least common multiple of the denominators,
we can make all the $x_t$:s integers.
The polynomial
$$
F(x)=\sum_{t=0}^{mn}x_tx^t
$$
is then an answer.
Let's do your example of $f(x)=x^2-1$ and $g(x)=x^2+3x+2$. Here $f(\alpha)=0$
tells us that $\alpha^2=1$. Similarly $g(\beta)=0$ tells us that $\beta^2=-3\beta-2$. This is all we need from the polynomials. Here $c_0=1$, $c_1=\beta$,
$c_2=\alpha$ and $c_3=\alpha\beta$. Let us write the power $(\alpha\beta)^t$,
$t=0,1,2,3,4$ in terms of the $c_k$:s.
$$
(\alpha\beta)^0=1=c_0.
$$
$$
(\alpha\beta)^1=\alpha\beta=c_3.
$$
$$
(\alpha\beta)^2=\alpha^2\beta^2=1\cdot(-3\beta-2)=-2c_0-3c_1.
$$
$$
(\alpha\beta)^3=\alpha\beta(-3\beta-2)=\alpha(-3\beta^2-2\beta)=\alpha(9\beta+6-2\beta)=\alpha(7\beta+6)=6c_2+7c_3.
$$
$$
(\alpha\beta)^4=(-3\beta-2)^2=9\beta^2+12\beta+4=(-27\beta-18)+12\beta+4=-14-15\beta=-14c_0-15c_1.
$$
We are thus looking for solutions of the homogeneous linear system
$$
\left(\begin{array}{ccccc}
1&0&-2&0&-14\\
0&0&-3&0&-15\\
0&0&0&6&0\\
0&1&0&7&0
\end{array}\right)
\left(\begin{array}{c}x_0\\x_1\\x_2\\x_3\\x_4\end{array}\right)=0.
$$
Let us look for a solution with $x_4=1$ (if the polynomials you started with
are monic, then this always works AFAICT). The third equation tells us that we should have $x_3=0$. The second equation allows us to solve that $x_2=-5$. The last equation and our knowledge of $x_3$ tells that $x_1=0$. The first equation
then tells that $x_0=4.$ This gives us the output
$$
x^4-5x^2+4.
$$
The possibilities for $\alpha$ are $\pm1$ and the possibilities for $\beta$ are $-1$ and $-2$. We can easily check that all the possible four products $\pm1$ and $\pm2$ are zeros of this quartic polynomial.
My solution to the linear system was ad hoc, but there are known algorithms for that: elimination, an explicit solution in terms of minors,...
The discriminant of a monic, cubic polynomial
$$p(x) := x^3 + b x^2 + c x + d$$
is the invariant
$$\Delta := -4 b^3 d+b^2 c^2+18 bc d-4 c^3-27 d^2;$$
it has the useful property that $p$ has three distinct, real roots iff $\Delta > 0$. (If $p$ has a repeated real root, then $\Delta = 0$, but in this case the nonrepeated root is always rational.)
On the other hand, by the Rational Root Theorem, if a monic polynomial $x^n + \cdots + d$ has a rational root $r$, then $r$ is an integer that divides $d$. These facts together suggest a way of generating examples:
- Pick a triple $(b, c, d)$ of integers.
- Compute $\Delta$; if $\Delta \leq 0$, $p$ does not have three real roots, so start over and pick a new triple. Otherwise, $p$ has three real roots.
- For each of the factors $s$ of $d$. Computing $p(\pm s)$. If any of these is values is zero, then $p$ has a rational root, so start over and pick a new triple. Otherwise, if none of these is zero, none of the roots of $p$ are rational, that is, $p$ satisfies the condition.
A quick Maple script shows that $2922$ ($31.2\%$) of the $21^3 = 9261$ monic, cubic polynomials with integer coefficients in $-10, \ldots, 10$ satisfy the condition, so the above procedure is efficient in the sense that in practice, one needn't try too many triples $(b, c, d)$ to produce examples.
Best Answer
For $n\ge3,$ let $f(x)\in \mathbb Z[x]$ be monic of degree $n.$ The roots of $f(x)$ are $\alpha_1, \alpha_2, \ldots, \alpha_n.$ Let $$g(x) = \frac{x^n - \alpha_1^n}{x - \alpha_1} \cdots \frac{x^n - \alpha_n^n}{x - \alpha_n}$$
$$g(x)=\prod_{k=1}^n (x^{n-1}+\alpha_kx^{n-2}+\alpha_k^2x^{n-3}+\cdots +\alpha_k^{n-1} )\tag1$$ By (1), g(x) is unchanged whenever the roots are permuted. Thus, each coefficient of $g(x)$ is a symmetric function of the roots of $f(x)$ (with coefficients in $\mathbb Z$). By the well-known theorem, each coefficient of $g(x)$ is therefore a $\mathbb Z$-linear combination of elementary symmetric functions of the roots of $f(x)$. Since the latter are integers, $g(x)\in\mathbb Z[x].$