# Constructive proof of algebraic elements forming a subfield

Let $F \leqslant E$ be a field extension.

If $a, b \in E$ are algebraic over $F$ then $a+b$ and $ab$ are algebraic as well. There is an short proof of this using the extension $E(a,b)$:

$[E(a,b):E]$ is finite so all elements are algebraic otherwise powers non-algebraic would form an infinite linearly independent set. In particular $a+b \in E(a,b)$ and $ab \in E(a,b)$ are algebraic.

But this proof doesn't construct the actual polynomial. Is there a constructive proof or any reason for such a proof not to exist?

-
All the classical proofs used resultants. It was Dedekind who came up with the short existence proof. I would be surprised if you couldn't find these things in Cohen's books on computational algebraic number theory. – Franz Lemmermeyer Nov 22 '11 at 19:24
$ab$ and $a+b$ both act on $F[a]/p(a) \otimes F[b]/q(b)$ where $p, q$ are the minimal polynomials of $a, b$. This vector space has basis $a^i \otimes b^j$ for $i, j$ in the appropriate range. One can explicitly write down the matrices of both $ab$ and $a+b$ (they are in fact the matrices described in Igor Rivin's answer) acting on this basis and then take the characteristic polynomial. – Qiaochu Yuan Nov 22 '11 at 19:52
Take the product of all polynomials $X-a'b'$ where $a'$ and $b'$ range over the conjugates of a and b, and use the symmetric function theorem to show that its coefficient lie in $E$. – anon Nov 22 '11 at 21:39

Let me see if I remember this right. Let $f$ be the minimal polynomial of $a$ and $g$ the minimal polynomial of $b$ over $F$. Consider the polynomial $h(x)$ obtained as the resultant with respect to the variable $y$ of the polynomials $f((x+y)/2),g((x-y)/2)$. A root $c$ of $h$ is therefore an element of the algebraic closure of $F$ for which $f((c+y)/2),g((c-y)/2)$ have a common root $d$, so (up to conjugates) $(c+d)/2=a,(c-d)/2=b$, so $c=a+b$. The correct statement is probably that $h$ has $a+b$ as one of its roots, but may not be irreducible.

There is a similar trick for $ab$ that I don't remember. Also, what I did doesn't work in characteristic two but a variant does, but I don't remember that either.

-
You are thinking too symmetrically. Take the resultant of $f\left(y\right)$ and $g\left(x-y\right)$, and you won't have to struggle with characteristic $2$. – darij grinberg Nov 22 '11 at 19:34
According to Wikipedia on Resultants: "If x and y are algebraic numbers such that P(x) = Q(y) = 0 (with degree of Q=n), we see that z = x + y is a root of the resultant (in x) of P(x) and Q(z − x) and that t = xy is a root of the resultant of P(x) and xnQ(t / x) ; combined with the fact that 1 / y is a root of ynQ(1 / y), this shows that the set of algebraic numbers is a field." – Kris Joanidis Nov 22 '11 at 19:37

This question keeps getting asked on forums, e.g.: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=61&t=202382 and www.artofproblemsolving.com/Forum/viewtopic.php?f=61&t=180471 .

This fact is a particular case of a more general fact, which claims that if $A$ is a subring of a commutative ring $B$, and if $a$ and $b$ are two elements of $B$ integral over $A$, then $a+b$ and $ab$ are integral over $A$, too. This is a standard result in commutative algebra, and usually proven constructively: e.g. Corollary 2.1.11 in Swanson-Huneke yields it.

PS. This might be clear to you, but there is no chance to get the minimal polynomial of either $a+b$ or $ab$ by any algorithm. What you can get are polynomials, both of degree $\left[E\left(a\right):E\right]\cdot\left[E\left(b\right):E\right]$, that have $a+b$ resp. $ab$ as roots. These can be obtained as resultants in a way similar to Felipe's, or by executing any of the above-mentioned constructive proofs as programs.

-

There is a different (on some level) very cute constructive proof:

We need:

Lemma 1 The eigenvalues of $A\otimes B$ are the products of eigenvalues of $A$ and $B.$

and

Lemma 2 The eigenvalues of $A \otimes I + I \otimes B$ are the sums of the eigenvalues of $A$ and $B.$

Proofs of these are left to the interested reader. In any case, now apply Lemmas 1, 2 to the companion matrices of your favorite algebraic numbers.

-
Thing is that Lemmas 1 and 2 are rather annoying to prove. They are both very clear when all eigenvalues exist and are pairwise distinct; proving them in the general case requires showing that this case is Zariski-dense (easy) and that the assertions of the lemmata are polynomial identities (relatively easy, but nauseating to formalize). – darij grinberg Nov 22 '11 at 19:52