How do you find a polynomial with integer coefficients with this sum of radicals as a root?

Let $$x=\sqrt{a + \sqrt{b}} + \sqrt{c + \sqrt{d}}$$

How do you find the polynomial with this value as a root? Where a, b, c, and d are integers.

-
Square things, carefully, several times. – Qiaochu Yuan Oct 7 '12 at 1:25
If my answer is not satisfying enough I can give you an idea of how to construct the polynomial who has the sum as a root. I just thought you might've wanted a hint first. – Patrick Da Silva Oct 7 '12 at 1:34
I wrote a blog article about how to do this that you might find helpful. It includes an example of how to do it for $\sqrt2+\sqrt3$. This example is simpler than yours, but the process is similar. – MJD Oct 7 '12 at 1:34
@MJD, +1 for interesting article, thanks for sharing. – NoChance Oct 7 '12 at 1:56
@Patrick: I have given (most of) the solution I was hinting at below. – Qiaochu Yuan Oct 7 '12 at 6:18

A hint would be to first find the polynomial for $\sqrt{a + \sqrt b}$ first (thus also giving you a formula for the second term), and then find the polynomial with $\alpha + \beta$ as a root given polynomials $f$ and $g$ such that $f(\alpha) = g(\beta) = 0$. I think that will make your search a little bit easier.

How about this one for the first term? $$(x^2 - a)^2 - b$$

EDIT : Since you asked for the proof, I will outline it here.

Note that for a polynomial $p(x) = a_0 + \dots + a_{n-1}x^{n-1} + x^n$, being a root of this polynomial is equivalent to being an eigenvalue of the following matrix called the companion matrix of $p$ : $$\begin{bmatrix} 0 & & & & - a_0 \\ 1 & 0 & & & \vdots \\ & 1 & \ddots & & \vdots \\ & & \ddots & 0 & -a_{n-2} \\ & & & 1 & -a_{n-1} \\ \end{bmatrix}$$ You can read it off Dummit & Foote's Abstract Algebra, chapter 12. It is a very beautiful theory I suggest you know if you study polynomials for a while.

So instead of looking for a polynomial with $\alpha + \beta$ as a root, we are looking for a matrix with $\alpha + \beta$ as its eigenvalue, because then the characteristic polynomial of that matrix will give us the desired polynomial.

To produce such a matrix, one will use the tensor product of matrices (Very pretty schemes there explain how to perform such an operation : http://en.wikipedia.org/wiki/Tensor_product#Kronecker_product_of_two_matrices) because they have very interesting properties. Say $\alpha$ is an eigenvalue of the $n \times n$ matrix $A$ with eigenvector $x$ and $\beta$ is an eigenvalue of the $m \times m$ matrix $B$ with eigenvector $y$. Denote by $I_n$ the $n\times n$ identity matrix. Then $$(A \otimes I_m + I_n \otimes B)(x \otimes y) = (Ax) \otimes y + x \otimes (By) = (\alpha x) \otimes y + x \otimes (\beta y) = (\alpha)(x \otimes y) + (\beta) (x \otimes y) = (\alpha + \beta) (x \otimes y)$$ so that $\alpha + \beta$ is an eigenvalue of the matrix $A \otimes I_m + I_n \otimes B$.

If we do the computations explicitly, the matrix associated to $(x^2 - a)^2 - b$ will be a $4 \times 4$ matrix, namely since the polynomial is $x^4 - 2ax^2 + a^2 - b$, the matrix will be $$\begin{bmatrix} 0 & 0 & 0 & -a^2 + b \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 2a \\ 0 & 0 & 1 & 0 \\ \end{bmatrix}$$ and similarly the matrix for $B$ will be $$\begin{bmatrix} 0 & 0 & 0 & -c^2 + d \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 2c \\ 0 & 0 & 1 & 0 \\ \end{bmatrix}.$$ Now computing the tensor products gives $$A \otimes I_4 + I_4 \otimes B = \begin{bmatrix} 0 & 0 & 0 & -c^2 + d & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -a^2 + b & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -a^2 + b & 0 & 0 \\ 0 & 1 & 0 & 2c & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -a^2 + b & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -a^2 + b \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & -c^2 + d & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 2c & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -c^2 + d & 2a & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 2a & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 2c & 0 & 0 & 2a & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 2a \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -c^2 + d \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 2c \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix}$$ So compute the characteristic polynomial of this guy and you're good to go. If you're interested, you could try to plug it into Mathematica and see if trivial factors come out. Degree $16$ feels too high for the degree of this guy, but maybe it just is, you know. =)

Hope that helps,

-
Let me ponder this hint for a day or so. Thanks! – No One in Particular Oct 7 '12 at 2:48
It'll help if you know how to find a polynomial with $\alpha + \beta$ as a root when you know polynomials for $\alpha$ and $\beta$. Have you ever heard of such a technique? – Patrick Da Silva Oct 7 '12 at 6:21
No, but it will be fun to think about. – No One in Particular Oct 7 '12 at 11:13
Outstanding answer. I really appreciate it. – No One in Particular Oct 8 '12 at 21:08
Still trying to get it right. (Doing it by hand.) I will post the result when I get it done. – No One in Particular Oct 14 '12 at 20:43

For the sake of defending my honor, here's most of the solution I alluded to involving squaring. It is somewhat messy, and the solution alluded to by Patrick Da Silva is nicer.

First square:

$$x^2 = a + \sqrt{b} + 2 \sqrt{(a + \sqrt{b})(c + \sqrt{d})} + c + \sqrt{d}.$$

Second square:

$$(x^2 - a - \sqrt{b} - c - \sqrt{d})^2 = 4 (a + \sqrt{b})(c + \sqrt{d}).$$

Expand:

$$x^4 - 2x^2 (a + \sqrt{b} + c + \sqrt{d}) + (a^2 + 2a \sqrt{b} + b) + 2(ac + c \sqrt{b} + a \sqrt{d} + \sqrt{bd}) + c^2 + 2c \sqrt{d} + d = 4(ac + c \sqrt{b} + a \sqrt{d} + \sqrt{bd})$$

Rearrange:

$$x^4 - 2x^2 (a + c) + (-2x^2 + 2a - 2c) \sqrt{b} + (a^2 + b - 2ac + c^2 + d) = (2x + 2a - 2c) \sqrt{d} + 2 \sqrt{bd}.$$

I won't write everything out from here (I've probably already made a mistake). Squaring a third time removes all of the radicals except those of the form $\sqrt{b}$. Rearranging and squaring a fourth time removes these.

This method does not generalize; putting too many additional square roots into the problem will cause squaring to keep giving you more terms regardless of how cleverly you rearrange.

-
Thanks. I was looking at keeping all of the radicals on the right. How did you decide which to move to the left. – No One in Particular Oct 7 '12 at 11:14
I'm flattered =) – Patrick Da Silva Oct 7 '12 at 16:36
@No One: experience. The first step is to get rid of the nested radicals by any means necessary. The second step is motivated by some knowledge of the theory of field extensions (the keyword here is "biquadratic extension"). – Qiaochu Yuan Oct 7 '12 at 19:37
@Qiaochu Yuan: "This method does not generalize; putting too many additional square roots ..." I think things can be organized in such a way so that, no matter how many radicals you start with, you can eventually remove all of them. The key is to observe that starting with $n$ many radicals, there is a fixed upper bound on the number "irrational terms" that can show up. For example, if $a,$, $b,$ $c,$ $d,$ and $e$ are each originally under a radical, then under radicals you'll only get these, and things like $ab,$ $ac,$ ..., and things like $abc,$ $abd,$ ... $abcd,$ etc. under radicals. – Dave L. Renfro Oct 8 '12 at 19:56
@Qiaochu Yuan: More specifically, at most $2^{n}- 1$ many different square root terms can show up, this being the number of different singleton to $n$-fold unordered products of the insides of the radicals, and this number of such distinct products is equal to $C(n,1) + C(n,2) + ... + C(n,n),$ where $C(n,k)$ is the binomial coefficient for the number of $k$-element subsets of a set with $n$ elements. – Dave L. Renfro Oct 8 '12 at 20:08