Solving Cyclotomic Polynomials by Radical Expressions
Andreas Weber, Michael Keckeisen, Essam Abdel-Rahman
E-mail: weber@cs.uni-bonn.de
Introduction
Niels Henrik Abel and Evariste Galois showed that polynomial equations of degree higher than four cannot be solved by radical expressions in general. As Galois stated in his work, radical solutions exist if and only if the Galois group of the polynomial is solvable.
Since the the Galois group of a cyclotomic polynomial is Abelian, its Galois group is solvable, and so its solutions can be expressed by radical expressions.
Example: the 5th cyclotomic polynomial and it's solutions:
In the last years algorithmic methods to compute solutions by radicals for the cases in which the Galois group of the polynomial is solvable have obtained renewed attention [HM01]. However, for the special case of cyclotomic polynomials a very good algorithm was already published in the year 1801, when the masterwork Disquisitiones Arithmeticae ([Gau86]) of Carl Friedrich Gauss appeared. In this book Gauss described an algorithm to compute radical expressions for primitive roots of unity. This work in some sense is a generalization of the famous result of Gauss already obtained in 1797 showing that the regular 17gon can be constructed by compass and ruler.
We implemented this algorithm of Gauss for computing radical expressions for roots of unity in MAPLE with an improved time complexity compared to Gauss' original proposition [Web96]. The command radsolve serves as an extension to the solve command, that returns radical solutions for all cyclotomic factors of a polynomial with integer coefficients and calls solve for the others.
The hard part of the proof and of the algorithm is to compute a radical expression for a primitive -th root of unity, where is a prime number. The improvement in our algorithm reduces the asymptotic time complexity in this case from
Ο((
to
Ο(,
where is the largest prime factor of -1. An analysis of the algorithm and the statement and proof of the proposition on which the improvement is based can be found in [Web96]. We also refer to this paper for a description of the underlying ideas of Gauss' algorithm and the statement of the theorems that yield its correctness.
For an overview see The Algorithm.
Compared to the MAPLE-code given in [Web96], we managed to improve the practical speed of the algorithm to a great extend, reducing the needed amount of memory at the same time. For instance, the computations of radical expressions for the 47th, 59th, or 83rd root of unity failed with the previous implementation, but can now be accomplished within a few hours.
The Algorithm
First, we will show how the task of computing radical solutions for cyclotomic polynomials can be reduced to the one of calculating radical expressions for roots of unity. Second, we will sketch the algorithm for the latter task, which mainly is the one given in [Web96].
Radical solutions for cyclotomic polynomials
The n-th cyclotomic Polynomial over the rational numbers is of the form
(x) =
and its degree is
φ(n) =
where n = and φ is the Eulerian φ -Function, as can be seen in [Nar90, p. 13 and 169]. From the difining formula of φ it can be seen that the inverse image of φ is finite. Thus, to determine whether or not an irreducible factor of a polynomial is cyclotomic, it suffices to compare the j-th cyclotomic polynomial with q for all j in . MAPLE provides the function numtheory[invphi] to calculate ; the computational costs of this functions is neglegible for the range of arguments which are feasible for computing radical expressions.
Given the n-th cyclotomic polynomial (x) , the task of computing φ(n) radical solutions can be reduced to finding a radical expression for one root of unity, because this root will be primitive, e.g. a multiplicative generator for the others. Further, it suffices to find a primitive n-th root of unity to compute primitive roots of unity for all prime factors of n by applying some relatively simple recursion formulas, see e.g. [Gaa88].
Radical expressions for primitive r-th roots of unity
The hard part of the algorithm is to find a radical expression for a primitive -th root of unity, where is a prime number. This part involves the computation of Gaussian periods, cf. [Gau86, Sec.343]. If denotes a primitive -th root of unity the period (f , k) for two integers f and k is defined by
(f , k) =
where e = and ℊ is a primitive -th root. In Maple a primitive -th root can be computed by the function primroot in the package numtheory. The Gaussian periods are generators of intermediate fields of the number field Q( ), which is a number field of degree -1 over the rationals. Using the modern terminlogy of intermediate fields the algorithm of Gauss works roughly as follows. Starting with the rationals, compute a radical expression for a generator of an intermediate field of prime degree, i.e. an appropriate Gaussian period. After this task has been accomplished compute a radical expressions for a generator of another intermediate field (i.e. another Gaussian period) whose relative degree over the other intermediate field is of prime order. Continue this task until a radical expression for a generator of Q( ), i.e. has been computed.
The difficult part of Gauss algorithm is the lifting of radical expressions from one intermediate field to another one. We will not give the details of this lifting here but we refer to [Web96].
The algorithm described above works for several sequences of intermediate fields to be constructed. All permutations on the list of prime factors of -1 give a possible sequence in the construction of the intermediate fields. Different permutations give different results in general, and also the computational costs are greatly affected by the choice of an appropriate sequence of intermediate fields. Our default strategy in the choice of the intermediate fields is as follows: first take the largest prime factor, then the second largest and so on, until we just get the final field Q( ) as a relative extension of degree 2 of the last intermediate field. Note that we have to count multiplicities as seperate factors. This strategy seems to be preferable over others, because bigger relative extensions --- which cause more computations --- occurr in smaller intermediate fields. However, as a tool for experimental mathematics we provide another strategy, too. The second strategy is simply to reverse the ordering; this can be done by setting SwapPrimeOrder := true. As had to be expected in all our experiments the obtained computation times were far worse than with our default setting and the computed radical expressions were also larger; some examples are given below.
How to use radsolve
The library is included in the file ?radsolvelib.mpl?.
All functionality is available via the function radsolve.
The command radsolve serves as an extension to the Maple solve command. It returns radical solutions for all cyclotomic factors of a polynomial with integer coefficients and calls solve for the others.
Description:
radsolve(poly) is based on an algorithm given by Carl Friedrich Gauss in his Disquisitiones Arithmeticae, 1797, with an improved time complexity, as described in Weber, A.: Computing radical expressions for roots of unity, SIGSAM Bulletin 30, 117 (Sept. 1996), p.11-20.
Examples:
The Maple solve command does not express the solutions of a cyclotomic factor of a polynomial of degree higher than 4 in radicals, but uses sin and cos functions instead.
In the following, we set AllSolutions to false. Thus we get only one solution for any irreducible factor of the polynomial.
See Also: solve , RootOf , allvalues , dsolve , fsolve , isolve , msolve , rsolve , assign , invfunc , isolate , match , linalg[linsolve] , simplex , grobner
To verify the results, use radnormal . You might have to use numeric evaluation for large results:
Gauss computed the value of cos(2*pi/17) up to 30 digits in 1801, see [BH08]. We will compute the numeric value of the our radical expression for a 17th root of unity as a test.
Note that radsolve uses remember tables. So, if you compute the same solution twice, the second will be taken from memory and changes to global variables will not affect the result. Try restart in this case.
Practical Limitations of the Algorithm
Compared to [Web96] the implementation of the algorithm has been optimized. For the table below we apply radsolve on all cyclotomic polynomials of (prime) degree up to 257. It can be seen that the computing time depends on the size of the largest prime factor of to a great extend, as had to be expected from the theoretical complexity analysis given in [Web96]. We also summarized sizes of normal and dag representation, f meaning rational, r radical operations and a the number of dag variables used. Moreover, we save the computed radical expressions in files with the name radprimroot###.m. We also test numerically that the computed expressions are roots of unity (of the right order).
It is interesting to see the results you obtain by setting SwapPrimeOrder := true. You get different radical expressions and it takes more time and memory. The reason for this is explained above. We will only give the dag representation. Notice that you must not use a simply evalf for the numerical test, as this would generate a tree representation of the expression instead of a dag.
We will also compute the fully recursively evaluated radical expressions for the prime roots of unity. Here we will only give the count on the dag representation. Notice that we must not use evalf directly, as this will cause a possible explosion on memory due to an intermediate tree representation of the expression. We save the results in files of the name radicalprimroot###.m.
Comparison to Related Work
In the book of Gaal [Gaa88] a radical expression for a 7th root of unity is derived by some special reasoning that does not generalize to higher orders. The derived expression is the following:
Our function radsolve computes:
radsolve computed the 7th root of unity that is equal to :
Except for an implementation by ourselves of a much more inefficient method for the same task described in [Edw84], we do not know of implementations of other general methods by which radical expressions for higher roots of unity can be computed. Without being aware of an implemetation, we know of an algorithm developped by B. Trager, which computes radical expressions for a -th root of unity [Zip94]. This algorithm is entirely different from the one of Gauss. The major computational task consists of inverting a matrix of size Ο() over Q( ) , where q is a divisor of -1. Thus if -1 is smooth, i.e. if -1 contains only small prime factors, the asymptotic time complexity of our improvement of the algorithm of Gauss is much better. But in special cases, such that is prime, the algorithm of Trager might be an interesting alternative. It would be interesting to have a careful implementation of the hard cases, such as p = 47 , 59, 83, 107, 167, 179, 227 etc.
Bibliography
[BH08] Bauer, F. L. and Haenel, C.: Carl Friedrich Gau?, das 17-Eck und MATHEMATICA. Informatik Spektrum 31,5 (2008), p. 492-498
[Edw84] Edwards, H. M.: Galois Theory, vol. 101 of Graduate Texts in Mathematics, Springer, New York, 1984
[Gaa88] Gaal, L.: Classical Galois Theory, 4th ed., Chelsea Publishing Company, New York, 1988
[Gau86] Gauss, C. F.: Disquisitiones Arithmeticae - English Edition, Springer, Berlin, 1986
[HM01] Hanrot, G. and Morain, F.: Solvability of radicals from an algorithmic point of view. Proc. ISSAC 2001, p. 175-182. ACM.
[Nar90] Narkiewicz, W.: Elementary and Analytic Theory of Numbers, Springer, 1990.
[Web96] Weber, A.: Computing radical expressions for roots of unity, SIGSAM Bulletin 30, 117 (Sept. 1996), p. 11-20
[Zip94] Zippel, R.: Computer Algebra. Unpublished Lecture Notes, 1994.
