Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
$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
1  
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
add comment

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
1  
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
1  
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.