next up previous
Next: Rational Maps with Symmetry. Up: Solving the quintic by Previous: Purely Iterative Algorithms.

Towers of Algorithms.

Let V be a variety, k its function field. From a computational point of view, k is the set of all possible outputs of decision-free algorithms which perform a finite number of arithmetic operations on their input data. The graph of an element of k in tex2html_wrap_inline2109 describes the output of such an algorithm.

Let T be a generally convergent algorithm with output tex2html_wrap_inline2113 . Assume for simplicity that W is irreducible, and let tex2html_wrap_inline2117 be the corresponding field extension. Then elements of tex2html_wrap_inline2119 describe all possible outputs which are computed rationally from the output of T and the original input data. We refer to tex2html_wrap_inline2123 as the output field of T.

If W is reducible then T has an output field for each component of W. All algorithms which we consider explicitly will have irreducible output.

If f(z) is a rational map, let tex2html_wrap_inline2135 denote the group of Möbius transformations commuting with f. If tex2html_wrap_inline2139 is a group acting on a set, tex2html_wrap_inline2141 will denote the subgroup stabilizing the point a.

T 4.1. Every generally convergent algorithm T in k(z) can be described by the following data:

A rational map f(z) and a finite set tex2html_wrap_inline2151 such that tex2html_wrap_inline2153 converges to a point of A for all z in an open dense set; and
A finite Galois extension k'/k with Galois group G, an isomorphism tex2html_wrap_inline2163 and an element tex2html_wrap_inline2165 in tex2html_wrap_inline2167 ; such that
tex2html_wrap_inline2169 for all g in G; and
tex2html_wrap_inline2175 .

The output fields of T are the fixed fields of tex2html_wrap_inline2179 , as a ranges over the points of A. If tex2html_wrap_inline2185 acts transitively on A then the output of T is irreducible and the output field is unique up to isomorphism over k.

Proof. Given the rigidity of generally convergent algorithms, the proof follows the same lines as Theorem 2.1.

A tower of algorithms is a finite sequence of generally convergent algorithms, linked together serially, so the output of one or more can be used to compute the input to the next. The final output of the tower is a single number, computed rationally from the original input and the outputs of the intermediate generally convergent algorithms.

A tower is described by rational maps tex2html_wrap_inline2193 and fields tex2html_wrap_inline2195 such that tex2html_wrap_inline2197 is an element of tex2html_wrap_inline2199 , and tex2html_wrap_inline2201 is one of the output fields of tex2html_wrap_inline2203 . The field tex2html_wrap_inline2205 is the final output field of the tower. The field extension k'/k is computable if it is isomorphic over k to a subfield of tex2html_wrap_inline2211 for some tower of algorithms.

If we require that every algorithm employed has irreducible output, then there is a one-to-one correspondence between the elements of all computable fields over k, and the `graphs' tex2html_wrap_inline2215 of the final output of all towers of algorithms. In general, if W is reducible, then each component of W corresponds to an element of a computable field.

Our main goal is to characterize computable field extensions.

Möbius groups. tex2html_wrap_inline2221 and tex2html_wrap_inline2223 will denote the symmetric and alternating groups on d symbols. Let tex2html_wrap_inline2227 be a finite group of Möbius transformations. As an abstract group, tex2html_wrap_inline2229 is either a cyclic group, a dihedral group, the tetrahedral group tex2html_wrap_inline2231 , the octahedral group tex2html_wrap_inline2233 , or the icosahedral group tex2html_wrap_inline2235 . We refer to such groups as Möbius groups. Note that

(1) Any subgroup or quotient of a Möbius group is again a Möbius group; and

(2) every Möbius group other than tex2html_wrap_inline2237 is solvable.

Near Solvability. Suppose a group G admits a subnormal series


such that each tex2html_wrap_inline2241 is a Möbius group. By (2) the series may be refined so that successive quotients are either abelian or tex2html_wrap_inline2243 . We will say such a group is nearly solvable. By (1) any quotient or subgroup of a nearly solvable group is also nearly solvable.

T 4.2. A field extension k'/k is computable if and only if the Galois group of its splitting field is nearly solvable.

Since tex2html_wrap_inline2247 is nearly solvable if and only if tex2html_wrap_inline2249 , we have the immediate:

C 4.3. Roots of polynomials of degree d can be computed by a tower of algorithms if and only if tex2html_wrap_inline2253 .

Proof of 4.2: one direction. Suppose k' is computable. Let tex2html_wrap_inline2257 be a tower of output fields such that k' is isomorphic over k to a subfield of tex2html_wrap_inline2263 . Define inductively tex2html_wrap_inline2265 to be the splitting field of tex2html_wrap_inline2267 over tex2html_wrap_inline2269 , and let


be the corresponding subnormal series for tex2html_wrap_inline2271 . tex2html_wrap_inline2273 is the same as the Galois group of tex2html_wrap_inline2275 , which faithfully restricts to a subgroup of the Galois group of the splitting field of tex2html_wrap_inline2277 over tex2html_wrap_inline2279 . By Theorem 4.1, the latter group is isomorphic to a finite group of Möbius transformations, so G is nearly solvable.

To complete the proof we must exhibit algorithms for producing field extensions. It turns out that, in addition to the basic tool of Newton's method for radicals, only one other generally convergent algorithm is required.

L 4.4. If k'/k is a cyclic Galois extension, then k' is computable.

Proof. Since k contains all roots of unity, tex2html_wrap_inline2287 for some element tex2html_wrap_inline2289 such that tex2html_wrap_inline2291 is in k. As we have seen, Newton's method is generally convergent when applied to extract nth roots. Thus k ' is the output field of T in k(z) where T is Newton's method applied to the polynomial tex2html_wrap_inline2305 .

L 4.5 (Existence of an Icosahedral Algorithm). There is a critically finite rational map f(z) with tex2html_wrap_inline2309 isomorphic to tex2html_wrap_inline2311 , whose superattracting fixed points A comprise a single orbit under tex2html_wrap_inline2313 with stabilizer tex2html_wrap_inline2315 .

This will be established in the following section.

L 4.6. If k'/k is a Galois extension with Galois group tex2html_wrap_inline2319 , then k' is computable.

Proof. To construct an algorithm to compute k', we need only provide data as in (a) and (b) of Theorem 4.1. For f(z), we take the rational map given by the preceding lemma, and A its superattracting fixed points. Since f is critically finite, Theorem 3.3 guarantees an open, full measure set of z converge to A.

Let tex2html_wrap_inline2333 be any isomorphism between G and tex2html_wrap_inline2337 . As shown in [15], there is a degree 2 cyclic extension of k in which the cohomology class tex2html_wrap_inline2341 becomes trivial. Since cyclic extensions are computable, we may assume this is true in our original field k. Thus there is an element tex2html_wrap_inline2345 such that tex2html_wrap_inline2347 , and tex2html_wrap_inline2349 is a generally convergent algorithm over k.

Since the stabilizer of a point in A is an tex2html_wrap_inline2355 subgroup of tex2html_wrap_inline2357 , the output field of T is the fixed field of tex2html_wrap_inline2359 . As k' is a cyclic extension of this fixed field, it is computable.

The result of Serre's quoted above has been generalized by Merkurev and Suslin to show that any Severi-Brauer variety has a solvable splitting field [13]. (This reference was supplied by P. Deligne.)

The lemma can also be established somewhat less conceptually without appeal to [15]. Any element tex2html_wrap_inline2363 generating the fixed field of tex2html_wrap_inline2365 satisfies a quintic polynomial p(z) in k(z). Since tex2html_wrap_inline2371 is solvable, to compute the extension k' it suffices to compute a root of p.

In the Appendix we will give an explicit algorithm for solving quintic polynomials. To carry out the solution, the quintic must be normalized so that tex2html_wrap_inline2377 and tex2html_wrap_inline2379 are both equal to zero, where tex2html_wrap_inline2381 denote the roots of p. This normalization is easily carried out by a Tschirnhaus transformation, but it requires the computation of a square root. The square root, which Klein calls the `accessory irrationality', furnishes the predicted degree 2 extension.

Completion of the Proof of 4.2. Replacing k' by its splitting field, we may assume k' / k is Galois with nearly solvable Galois group. Then k' is obtained from k by a sequence of Galois extensions, each of which is cyclic or tex2html_wrap_inline2393 . By the preceding lemmas, each such extension is computable, so k' is computable as well.

Remark on the quartic. Let tex2html_wrap_inline2397 , and let k be the subfield of symmetric functions. Then the problem of computing k'/k is the same as that of finding the roots of a general fourth degree polynomial. Since the Galois group G here is tex2html_wrap_inline2405 , Theorem 4.2 guarantees this is possible by a tower of algorithms.

tex2html_wrap_inline2407 is actually isomorphic to a Möbius group, namely the symmetries of an octahedron, or its dual, a cube. Is k' the output field of a generally convergent algorithm? If so, the roots of quartic polynomials would be computable as rational functions of the output of a single purely iterative algorithm (we have already seen the roots cannot actually be the output of such an algorithm).

Unfortunately, this is impossible; although the Galois group is isomorphic to a Möbius group, the potential obstruction in Galois cohomology is nonzero, and k'/k is not a rigid extension.

The analogous case of polynomials of degree 5 is discussed in [15]. Here we will sketch a picture of the obstruction from a topological point of view.

The field extension k'/k corresponds to the rational map tex2html_wrap_inline2415 from the space of roots to the space of polynomials. Let tex2html_wrap_inline2417 be an isomorphism between the Galois group G of k'/k and the octahedral group tex2html_wrap_inline2423 .

If k'/k is rigid, then the Severi-Brauer variety tex2html_wrap_inline2427 associated to tex2html_wrap_inline2429 is birational to the product tex2html_wrap_inline2431 .

Now tex2html_wrap_inline2433 is a flat tex2html_wrap_inline2435 bundle outside of the branch locus of the map tex2html_wrap_inline2437 , which is the subvariety tex2html_wrap_inline2439 of polynomials with vanishing discriminant. The fundamental group tex2html_wrap_inline2441 is naturally identified with tex2html_wrap_inline2443 , the braid group of four points in the plane: Over a loop based at p, the roots of p(z) move without collision and return to their original positions, describing a braid.

There is a natural map tex2html_wrap_inline2449 which records how the roots of p are permuted by the braid. Under the identification tex2html_wrap_inline2453 , this map records how the fiber of tex2html_wrap_inline2455 is twisted by monodromy along a loop.

If tex2html_wrap_inline2457 is birational to the trivial bundle, then its restriction to some Zariski open subset U is topologically trivial. If that subset were as large as possible--i.e., if U were equal to the complement of the discriminant locus--then it would be possible to lift the map tex2html_wrap_inline2463 to tex2html_wrap_inline2465 , a two-fold cover of tex2html_wrap_inline2467 .

But this is impossible: There are two commuting elements tex2html_wrap_inline2469 and tex2html_wrap_inline2471 in the braid group (see Figure 3), whose images in tex2html_wrap_inline2473 (thought of as Euclidean symmetries of a cube) are tex2html_wrap_inline2475 rotations about perpendicular axes. Such rotations cannot be lifted to commuting elements of tex2html_wrap_inline2477 .

Figure 3: Commuting braids.

There is a torus in the complement of tex2html_wrap_inline2479 whose fundamental group is generated by tex2html_wrap_inline2481 and tex2html_wrap_inline2483 . One can show that this torus can be moved slightly to avoid any finite set of other hypersurfaces in tex2html_wrap_inline2485 . Thus the obstruction persists on any Zariski open set, and tex2html_wrap_inline2487 is not birationally trivial.

next up previous
Next: Rational Maps with Symmetry. Up: Solving the quintic by Previous: Purely Iterative Algorithms.

Peter Doyle