\documentstyle[12pt,amssymbols]{report} \begin{document} \newcommand{\0}{\mbox{$\cal O$}} \newcommand{\C}{\mbox{$\cal C$}} \newcommand{\Cns}{\mbox{${\cal C}_{ns}$}} \newcommand{\nl}{\vspace{4 mm}} \newcommand{\CC}{\mathord{\Bbb C}} \newcommand{\N}{\mathord{\Bbb N}} \newcommand{\Z}{\mathord{\Bbb Z}} \newcommand{\Q}{\mathord{\Bbb Q}} \newcommand{\R}{\mathord{\Bbb R}} \newcommand{\la}{\mbox{$\rightarrow$}} \newcommand{\implies}{\mbox{$\rightarrow$}} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \title{\bf {\it Denesting Radical Expressions \\ Through Galois Theory}} \author{ Thomas Colthurst \\ Math 154: Abstract Algebra \\ Professor Randy McCarthy } \date{\today} \maketitle \section*{ Background } This is an expanded summary of Susan Landau's article {\em Simplification of Nested Radicals}, to appear in the SIAM Journal of Computation. All definitions, theorems, algorithms, and results, unless explicitly noted, are hers. I would like to thank Susan Landau for sending me a preprint of her article, and for answering my questions via e-mail. The motivation for this work are identities like the following (which was discovered by Ramanujan): \[ \sqrt[3]{\sqrt[3]{2}-1} = \sqrt[3]{1/9} - \sqrt[3]{2/9} + \sqrt[3]{4/9} \] We would like to have some way of converting nested radicals to the simplest possible form. Susan Landau has found an algorithm for doing this based upon Galois theory. \section*{ Definitions } We limit ourselves to fields with characteristic 0. A {\em formula\/} (or equivalently a {\em nested radical\/}) over a field k and its {\em depth of nesting\/} are defined as follows: \begin{enumerate} \item an element of k is a formula of depth 0 over k, \item an arithmetic combination ( A+B, A-B, AB, A/B ) of formulas A and B is a formula whose depth over k is max( depth(A), depth(B) ), and \item a root \( \sqrt[n]{A} \) of a formula A is a formula whose depth over k is 1 + depth \item a nth root of unity (denoted $\zeta_{n}$ ) has depth 1 over any field which does not contain it \end{enumerate} Please note that this is a symbolic, and not numeric or mathematical, definition. We are merely defining what combinations of symbols make up formulas, and associating with each valid formula a natural number called the depth of nesting. A given number will have an infinite number of formulas which have its value (evaluation of formulas should be obvious): \( 2 = 1 + 1 \), \( \sqrt[4]{2} = \sqrt{ \sqrt{2} } \), etc. This definition has both computational and algebraic motivation. We will soon see that depth of nesting corresponds to the length of the normal subgroup tower in a Galois group. Also, it approximately corresponds to the amount of computation it takes to handle a formula by a symbolic calculating program. I say approximately because the above definition only measures the length of the longest nesting path in what is actually a tree of nested radicals, which is to say that you can have a lot of radicals in an expression, but the depth of nesting only measures the extent to which they are nested. Still, for symbolic algebra programs, heavily nested radicals are significantly harder to deal with. \nl Further, we say that a formula A can be denested over the field k if there is a formula B of lower nesting depth than A such that A=B and that A can be denested in the field L if there is a formula B=A of lower nesting depth than A with all of the terms (subformulas) of B lying in L. \nl Of course, this is all slightly ambigious since $ \sqrt[n]{A} $ is a multivalued function. Landau chooses to define it as having the value which minimizes the degree of the field extension. This simplifies that math considerably, but is unfortunate from a computational standpoint since the standard choice is the root with minimum argument. The choice of assigning a nth root of unity ($\zeta_{n}$) a nesting depth of 1 also is motivated mathematically, since $\zeta_{n}$ can be added to any field in a simple extension. Computationally, however, this hides up to a log n nesting depth, since otherwise to get a primitve nth root of unity would we of had to adjoin something like \( ( -1 + \sqrt{-3} ) / 2 \). For instance, we can obtain a nesting of \( \sqrt{ \sqrt{5} - 5/2 } \) by adjoining the 5th root of unity $ \zeta_{5} $ and writting \( \zeta_{5} - 1 / \zeta_{5} \). To quote Landau, ``It is not clear that we have really simplified things. This problem seems unavoidable in the current approach.'' \section*{Theorems and Results} We assume the reader is familiar with the fundamentals of Galois theory. In particular, we require the following theorems: \begin{theorem} Let k be a field. The following are equivalent: 1. $\alpha$ is a nested radical over k. 2. There exists a solvable Galois extension L over k with $\alpha$ in L. 3. The spliting field of $k(\alpha)$ over k has solvable Galois group. \end{theorem} \begin{theorem} Let k be a field, with K a cyclic extension of k of degree n, and suppose $\zeta_{n}$ is in k. Then there is a $\beta$ in K such that \( K = k(\beta) \), and $\beta$ satisfies \( x^{n} - b \) for some b in k. \end{theorem} The following lemma puts forth the correspondence between Galois theory and nested radicals, namely that nested radicals correspond to nested subgroups. \begin{lemma} Let $\alpha$ be a nested radical, and suppose $\alpha$ can be denested in a field $ L \supseteq k $. Suppose that the denested expression has nesting depth l. Let $ \tilde{L} $ be the splitting field of L over k, with Galois group G, and assume that all roots of unity of $\tilde{L}$ appear in k. Then there are subgroups \( H_{1}, \ldots, H_{l} \) of G, with \( G = H_{0} \rhd H_{1} \rhd \cdots \rhd H_{l} \) and $ H_{i} / H_{i+1} $ abelian for \( i = 0, \ldots l-1 \), with \( H \supseteq H_{l} \), where H is the subgroup of G associated with $ k(\alpha) $ . Conversely, if there is such a sequence of subgroups, then $\alpha$ has nesting depth of at most l. \end{lemma} {\bf Proof} This proof does not use the notation of [1], but instead uses a more informal and I hope clearer approach. A nested radical formula can be expressed as a tree where each branch is a radical and the depth of nesting corresponds to the height of the tree. Since all the leaves are radicals over the field $ k = k_{l} $, and thus cyclic extensions (since we have all necessary roots of unity) which can be combined into a normal abelian extension $ H_{l-1} / H_{l} $ (which is well defined since we are dealing with Galois extensions). All the leaves are now elements of a new field $ k_{l-1} $ and can be pruned to produce a tree of hieght l-1, and the abelian subgroup chain follows by induction. To see that \( H \supseteq H_{l} \), note that \( k( \alpha ) \subseteq k_{l} \). The converse follows immediately from Theorems 1 and 2 and the fact that the needed roots of unity lie in k. \nl This next theorem fills in the assumption in the above theorem that $\alpha$ can be denested in the splitting field L. \begin{theorem} Suppose $\alpha$ is a nested radical over k, a field of characteristic 0 which contains all roots of unity. Then there is a minimum depth nesting of $\alpha$ with each of its terms lying in the splitting field of the minimal polynomial of $\alpha$ over k. \end{theorem} {\bf Proof} See Landau [1]. \nl We now know how to go, theoretically at least, from nested radicals and nested subgroups. The next step is to obtain a minimal nesting of radicals, which corresponds to a minimal nesting of subgroups. This we obtain using commutator subgroups. \begin{lemma} Let \( G = H_{0} \supset H_{1} \supset \cdots \supset H_{t} \) be a sequence of groups such that \( H_{i} \lhd H_{i-1} \) and \( H_{i-1} / H_{i} \) is abelian. Then \( H_{i} \supset D^{i}G \). \end{lemma} {\bf Proof} See Herstein [2], pg. 253. \begin{theorem} Suppose \( k \subset k_{1} \subset \cdots \subset k_{t} \) is a series of abelian extensions ($k_{i+1}$ an abelian extension of $k_{i}$), with \( K = k(\alpha) \subset k_{t} \). Let L be the splitting field of K over k, and $L_{1}$ be the splitting field of $k_{t}$ over k, with Galois group G. Then \( L \subset L_{1} \), and let \( N = Gal(L_{1}/L) \) and s the smallest natural number such that. $ D^{s}G \subset N $. Then $ s \leq t $ and s is the length of the derived series for $G/N = Gal(L/k)$. \end{theorem} {\bf Proof} Let G = $Gal(L_{1}/k)$. By the above lemma, \( Gal(L_{i}/k_{i}) \supset D^{i}G \), since \( Gal(L_{i-1}/k_{i-1}) / Gal(L_{i}/k_{i}) \) is abelian. We know that \( \bigcap_{\sigma \in G} \sigma Gal(L_{1}/k_{t}) \sigma^{-1} = (e) \), since $L_{1}$ is the smallest normal extension of $k_{t}$ over k and likewise \( \bigcap_{\sigma \in G} \sigma Gal(L_{1}/K) \sigma^{-1} = N = Gal(L_{1}/L)\), since L is the smallest normal extension of K over k. Note that $ N \lhd G $. Now, \( (e) = \bigcap_{\sigma \in G} \sigma Gal(L_{1}/k_{t}) \sigma^{-1} \supset \bigcap_{\sigma \in G} \sigma D^{t}G \sigma^{-1} = \bigcap D^{t}G = D^{t}G \), and thus \( D^{t}G = (e) \). This implies \( D^{t}G \subset D^{s}G \), or $ s \leq t$. Further, \( D^{i}(G/N) \simeq D^{i}(G)N/N \) implies \( D^{s}(G/N) = (e) \) implies s is the length of the derived sequence of G/N = Gal(L/k). \section*{Roots of Unity} All of the above theorems, you may have noticed, assume that all the roots of unity are in the base field k. This assumption allows us to translate between cyclic extensions and radical extensions. This assumption, however, is quite false for the majority of fields we would like to consider, in particular, for $\Q$. To deal with these, we must adjoin roots of unity in our algorithm. The question then is, which ones? Landau presents two strategies: try to determine them from the commutator subgroup tower or use the input formula. The first strategy has the disadvantage that it sometimes does not produce a minimal denesting, and the second that the output is dependent on the presentation of the input radical. The following two theorems formalize the situation. \begin{theorem} Suppose $\alpha$ is a nested radical over k, where k is a field of characteristic 0. Let L be the splitting field of $k(\alpha)$ over k, with Galois Group G. Let l be the lcm of the exponents of the derived series of G. If there is a denesting of $\alpha$ such that each of the terms has depth no more than t, then there is a denesting of $\alpha$ over $k(\zeta_{l})$ with each of the terms having depth no more than t+1, and lying in $L(\zeta_{l})$. \end{theorem} {\bf Proof } Let s be the length of the derived series of G. By Theorem 4, \( s \leq t + 1 \) -- taking the lcm of the exponents of the derived series guarantees us that each extension has the root of unity it needs, and the bound is \( \leq t + 1 \) since the derived series tower begins at k instead of $k(\zeta_{l})$. Let \( L_{i} = L^{D^{i}G} \). \( L_{0} \subset \cdots \subset L_{s} \) forms an abelian extension tower. Each \( D^{i-1}G / D^{i}G \) is an abelian group, and can thus be broken down into the product of cyclic groups, \( J_{i1} \times \cdots \times J_{it_{i}} \). Let \( \tilde{J}_{ij} = (e) \times \cdots \times J_{ij} \times (e) \cdots \times (e) \subseteq D^{i-1}G / D^{i}G \). Then $L_{ij}$ is a cyclic extension of $L_{i-1}$, where $L_{i}$ is the composite of cyclic extensions \( L_{i}^{\tilde{J}_{i1}} L_{i}^{\tilde{J}_{i2}} \ldots L_{i}^{\tilde{J}_{it_{i}}} \). Let \( K_{i} = L_{i}(\zeta_{l}) \). By Theorem 2, the extension $K_{i}$ over $K_{i-1}$ is abelian, and $K_{ij}$ over $K_{i}$ is a radical extension $ \forall $ i,j. Thus the maximal depth of nesting for any expression in $K_{s}$ over k is s. \begin{theorem} Let k,$\alpha$,L,G,l, and t be as in the above theorem. Let m be the lcm of $(m_{ij})$, where $m_{ij}$ runs over all the roots appearing in the given depth t nested expression for $\alpha$. Let r be the lcm of (m,l). Then there is a minimal depth nesting of $\alpha$ over $k(\zeta_{r})$ with each of its terms lying in $L(\zeta_{r})$. \end{theorem} {\bf Proof } See Landau [1]. \section*{The Algorithm} The algorithm for denesting a nested radical $\alpha$ over a field k has the following steps: \begin{enumerate} \item Compute f(x), the minimal polynomial of $\alpha$ over k. \item Compute L, the splitting field of f(x) over k. \item Compute G, the Galois group of L over k. \item Compute $ G = D^{0}G \ldots D^{s}G $, the commutator subgroups of G. \item Let l be the least common multiple of the exponents (the maximum orders of) the commutator subgroups and the indices of the roots in $\alpha$. Let $K_{0}$ be k adjoin the lth root of unity, or ( \( K_{0} = k( \zeta_{l} ) \). \item Break each commutator subgroup into cyclic groups, \( D^{i-1}G / D^{i}G = J_{i1} \times \cdots \times J_{it_{i}} \) and let \( \tilde{J}_{ij} = (e) \times \cdots \times J_{ij} \times (e) \cdots \times (e) \subseteq D^{i-1}G / D^{i}G \). \item For each cyclic group, determine its fixed field \( K_{ij} = \tilde{K}_{i}^{\tilde{J}_{ij}}(\zeta_{l}) \), where \( \tilde{K} = K_{i} = L^{D^{i}G}(\zeta_{l}) \). Let \( l_{ij} = [ K_{ij} : K_{i-1} ] \) be the degree of its extension. Compute a normal basis \( \theta_{ij_{1}} \ldots \theta_{ij_{l_{ij}}} \) over this extension. Let $ B_{ij} $ be the Lagrange resolvent for this extension. \item Let \( K_{i} = K_{i-1}( B_{i1}, \ldots, B_{it_{i}} ) \) \item Express $\alpha$ over $K_{s}$, by computing its minimal polynomial over k and factoring this polynomial over $K_{s}$. One of the linear factors will yield the denested radical, which by Theorem 6 is within one of minimal nesting depth over $k(\zeta_{l})$. \end{enumerate} The only things left to explain are the last three steps which translate the cyclic extensions into radical extensions for a denested radical (given, of course, the proper root of unity). For this we use Lagrange resolvents. Let \( (\zeta_{l},\tau) = \tau + \zeta_{l} \sigma \tau + \cdots + \zeta^{l-1}_{l} \sigma^{l-1} \tau \), where $\sigma$ is the generator of the Galois group of a cyclic extension of degree l, and $\tau$ is any element in the extension. Since the $\sigma$'s are linearly independent, there exists a $\tau$ such that \( (\zeta_{l},\tau) \) is non-zero. This $\tau$ will generate L over k, and will satsify an irreducible polynomial $x^{l} - b$ over k for some b in k. The algorithm uses an element of the normal basis for $\tau$, since this will make \( (\zeta_{l},\tau) \) non-zero. To find the normal basis, we use an algorithm developed by Artin [3]. \nl The above algorithm is based upon Theorem 6. There is an analogous algorithm based upon Theorem 5 which is within one of nesting depth and does not depend on the presentation of the radical, the only difference being in the calculation of l and the manner in which the roots of unity are adjoined. \nl If you are at all interested in the running time analysis, the gist of it is this: the running time is dominated by computing the Galois group and computing the normal basis for each $K_{ij}$. These both take time polynomial to the degree of the splitting field L over k (around \( O( [L:k]^{12} ) \) actually, but still polynomial). \section*{An Example} To show how the algorithm works in practice, we end with an example, the reduction of \( \sqrt{ 5 + 2 \sqrt{ 6 } } \) to \( \sqrt{2} + \sqrt{3} \). \begin{enumerate} \item f(x), the minimal polynomial of \( \sqrt{ 5 + 2 \sqrt{ 6 } } \) over $k = \Q$ is \( x^{4} - 10 x^{2} + 1 = ( x \pm \sqrt{ 5 + 2\sqrt{6}} ) ( x \pm \sqrt{ 5 - 2\sqrt{6}} ) \). (Checking mod 3 quickly shows this is irreducible.) \item L, the splitting field of f(x) over \( \Q \), is $k(\sqrt{ 5 + 2 \sqrt{ 6 } })$. \item G, the Galois group of L over k, is \( \Z_{2} \times \Z_{2} \). \item The commutator subgroups of G are \( D^{0}G = G = \Z_{2} \times \Z_{2} \) and \( D^{1}G = (e) \). (s=1). \item l = lcm( exponent of $D^{0}$, lcm( indices of roots in \( \sqrt{ 5 + 2 \sqrt{ 6 } } \) ) ) = lcm( 2, lcm( 2, 2) ) = 2. \( \zeta_{2} = -1 \in \Q \), so \( K_{0} = \Q(\zeta_{2}) = \Q \). \item \( D^{0}G / D^{1}G = \Z_{2} \times \Z_{2} = J_{11} \times \cdots \times J_{1t_{1}} \), so \( J_{11} = \Z_{2} \), \( J_{12} = \Z_{2} \), and $ t_{1} = 2 $. \item The fixed field of $J_{11}$ is \( K_{11} = K_{1}^{J_{11}}(\zeta_{2}) = \Q^{\Z_{2} \times (e) } = \Q(\sqrt{6}) \), an extension of degree 2 and the fixed field of $J_{12}$ is \( K_{12} = K_{1}^{J_{12}}(\zeta_{2}) = (e) \times Q^{\Z_{2} } = \Q(\sqrt{2}) \), also an extension of degree 2. The normal basis over $K_{11}$ is \( \theta_{11_{1}}, \theta_{11_{2}} = 1, \sqrt{6} \) and the normal basis over $K_{12}$ is \( \theta_{12_{1}}, \theta_{12_{2}} = 1, \sqrt{2} \). The Lagrange resolvent for these extensions are \( B_{11} = \sqrt{6} \) and \( B_{12} = \sqrt{2} \). \item \( K_{1} = K_{0}( B_{11}, B_{12} ) = \Q(\sqrt{2},\sqrt{6}) \). \item \( \sqrt{ 5 + 2 \sqrt{ 6 } } = \sqrt{2} + \sqrt{6}\sqrt{2}/2 \), because \( x^{4} - 10 x^{2} + 1 \) factors into \( (x - \sqrt{2} - \sqrt{6}\sqrt{2}/2 ) ( \ldots ) \) over \( K_{1} = \Q(\sqrt{2},\sqrt{6}) \). \end{enumerate} Voila! \( \sqrt{ 5 + 2 \sqrt{ 6 } } = \sqrt{2} + \sqrt{6}\sqrt{2}/2 = \sqrt{2} + \sqrt{3} \). \begin{thebibliography}{99} \bibitem{sl:nest} Landau, Susan. {\em Simplification of Nested Radicals.} Preprint, COINS Technical Report 90-113. To appear in the SIAM Journal of Computation. \bibitem{sl:hers} Herstein, I. N. {\em Topics in Algebra, 2nd Edition.} New York: John Wiley \& Sons, 1975. \bibitem{sl:artin} E. Artin, {\em Galois Theory}, University of Notre Dame Press, 1942. \end{thebibliography} \end{document}