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)**- .

**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 *n*th 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 .

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.