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 describes the output of such an algorithm.

Let T be a generally convergent algorithm with output . Assume for simplicity that W is irreducible, and let be the corresponding field extension. Then elements of describe all possible outputs which are computed rationally from the output of T and the original input data. We refer to 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 denote the group of Möbius transformations commuting with f. If is a group acting on a set, 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)

A rational map f(z) and a finite set such that converges to a point of A for all z in an open dense set; and

(b)

A finite Galois extension k'/k with Galois group G, an isomorphism and an element in ; such that

(c)

for all g in G; and

(d)

.

The output fields of T are the fixed fields of , as a ranges over the points of A. If 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 and fields such that is an element of , and is one of the output fields of . The field 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 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' 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. and will denote the symmetric and alternating groups on d symbols. Let be a finite group of Möbius transformations. As an abstract group, is either a cyclic group, a dihedral group, the tetrahedral group , the octahedral group , or the icosahedral group . 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 is solvable.

Near Solvability. Suppose a group G admits a subnormal series

such that each is a Möbius group. By (2) the series may be refined so that successive quotients are either abelian or . 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 is nearly solvable if and only if , 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 .

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

be the corresponding subnormal series for . is the same as the Galois group of , which faithfully restricts to a subgroup of the Galois group of the splitting field of over . 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, for some element such that 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 .

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

This will be established in the following section.

L 4.6. If k'/k is a Galois extension with Galois group , 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 be any isomorphism between G and . As shown in [15], there is a degree 2 cyclic extension of k in which the cohomology class becomes trivial. Since cyclic extensions are computable, we may assume this is true in our original field k. Thus there is an element such that , and is a generally convergent algorithm over k.

Since the stabilizer of a point in A is an subgroup of , the output field of T is the fixed field of . 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 generating the fixed field of satisfies a quintic polynomial p(z) in k(z). Since 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 and are both equal to zero, where 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 . By the preceding lemmas, each such extension is computable, so k' is computable as well.

Remark on the quartic. Let , 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 , Theorem 4.2 guarantees this is possible by a tower of algorithms.

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 from the space of roots to the space of polynomials. Let be an isomorphism between the Galois group G of k'/k and the octahedral group .

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

Now is a flat bundle outside of the branch locus of the map , which is the subvariety of polynomials with vanishing discriminant. The fundamental group is naturally identified with , 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 which records how the roots of p are permuted by the braid. Under the identification , this map records how the fiber of is twisted by monodromy along a loop.

If 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 to , a two-fold cover of .

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

  
Figure 3: Commuting braids.

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