The Fractal Nature of Riem/Diff I

Alex Nabutovsky^{1} and Shmuel Weinberger^{2}

Preface.

In this paper we would like to expose some of the astonishing richness of the space of Riemannian metrics on a smooth manifold, up to reparametrization. We will denote this space as Met(M) = Riem(M)/Diff(M). Of course, in the small, this space is a nice infinite dimensional “orbifold” (if one extends the definition of orbifold to include compact groups, and not just finite ones), at generic points it’s a manifold (see [Bo]). But we shall show that at larger scales, this space has much in common with fractals.

In particular we will see that there are large “basins” that have topology, and are repeated infinitely often within the space (and even, in some sense, “all over the space”). On the other hand, the structure is rather more complicated than what is usually associated with fractals. There seem to be infinitely many different sorts of basins with different geometries from each other.

Most of our results concern manifolds of dimension at least five – although some are true for “sufficiently large” 4-manifolds and, conjecturally, for all 4-manifolds. They certainly fail for most (and assuming things much weaker than geometrization, for all) 3-manifolds. For surfaces, uniformization asserts that this quotient is naturally homotopy equivalent to moduli space and is known to have a rather nice geometry.

Let us be a little more precise and describe what we mean by “basins”: Choose some scale-invariant functional s on Met(M) that measures geometric complexity of a metric such as vol^{\frac{1}{n}} /inj, sup |K|diam^{2} or (− inf K)diam^{2}. Consider first a local minimum μ of the geometric complexity. If we would like to reach a point where the value of the geometric complexity is lower going along a continuous path or by a sequence of very short jumps, then we must first pass through a point where the value of the geometric complexity is greater then s(μ)+K for some K > 0. Consider the infimum K_{μ} of such K. The (“jump”) connected component of sublevel set s^{−1}((0, s(μ) + K_{μ})) is regarded as a basin containing μ at the bottom and K_{μ} as its depth. (If μ is the global minimum, then we can consider the whole space as the corresponding basin of infinite depth.) It is clear that this definition of basins can be extended to cover situations when s does not necessarily attain its local minimum at the bottom of a basin: One starts from an arbitrary μ and first tries to reach points where the value of s is as small as possible. Points where s is almost as small as possible can be regarded as being near the “bottom” of the basin. Then one proceeds as

1 Partially supported by an NSERC Grant.

2 Partially supported by an NSF Grant. in the situation when the “bottom” of the basin is just a local minimum of s. *

This paper is partially an elaboration and synthesis of results from a series of earlier papers. In [N0], the first author applied techniques from logic to give the first proof of the existence of infinitely many deep basins (and even local minima) for certain (“crumpledness”) functionals on spaces of hypersurfaces, diffeomorphic to the sphere, in the Euclidean space. In [N3] the methods of that paper were applied to the functional vol/inj^{n} on Met(M), and again infinitely many very deep basins were shown to exist. An immediate application of these basins is that they provide a venue in which to seek local minima for s: the minimum of s in a basin is a local minimum of s on Met(M). If the “controllable increase” in the definition of basins grows sufficiently fast then these local minima will be very deep. An informal but practically useful observation is that when the “controllable increase” grows sufficiently fast then the basins for sufficiently large x can be regarded as separate connected components of Met(M) and some of them behave somewhat like the spaces of Riemannian structures on manifolds with quite different from M properties. In [NW1] we took another step further: we proved that in many of these basins the elements of Met(M) look and behave like Riemannian structures on manifolds admitting Riemannian metrics of negative curvature. This shows that a significant part of topology of hyperbolic manifolds (especially the Gromov-Thurston theory of bounded cohomology) is highly relevant for geometry of every compact highly dimensional manifold M (even S^{n}) and has immediate consequences for variational problems on Met(M).Also, in view of results of [NW1] there exists a definite but now only slightly explored possibility that for any M one can find basins where M looks like it has some other interesting topological properties useful for solving variational problems.

The paper has several purposes. First it is a survey of the results and methods based on computability theory and developed in [N0], [N1], [N2], [N3], [N4], [NW2], [NW3],

[NW4] and especially [NW1] demonstrating the ruggedness of the Morse landscape of a wide class of functionals on spaces Met(M) and on many other similar spaces.

Secondly, we would like to emphasize computational-theoretic aspects of geometry of Met(M). For example, we observe that one can see in Met(M) the rich combinatorics of computably enumerable degrees of undecidability. In particular, one has infinite sequences of local minima of any of the functionals mentioned above with depths growing as a function in any prescribed computationally enumerable degree. We will also see that degrees can be used to measure densities of local minima of various sorts not just their depths.

Thirdly, we will be interested in the presence of “virtual cycles”, which are homotopy or homology classes defined in a region of our space, but which are nullhomologous, but only after moving very far away. (Like the difference between two close points on a snowflake.)

It is well-known that there are substantial technical difficulties in applying Morse theory to variational problems for Riemannian functionals. But after these difficulties are resolved, virtual cycles can be used as effectively as genuine cycles in the application of

* If desired, this definition can be modified in order to allow a certain controllable increase of geometric complexity while looking for a point with a low value of s for “free” (that is K will be the excess of this allowed increase). In this case one should start here from a local minimum of depth not less than the allowed increase of geometric complexity. All basins defined in this way will be automatically deep.

Morse theory. When one is lucky, the virtual cycles and their cobounding chains each give rise to critical points. While the height function on a connected manifold can have a unique local maximum and minimum, on a connected fractal there are typically infinitely many. Moreover, one of the main achievements of [NW1] is in the demonstration that the technical difficulties in application of the Morse theory to variational problems on Met(M) unsurmountable for genuine cycles can disappear for appropriately chosen virtual cycles!

It was this last remark that had spurred our initial investigations of Met in [N3], [NW1], [NW4]; we were interested in showing that various natural functionals defined on Met(M) have many critical points. A difficulty in achieving this is the lack of compactness (due to collapsing, infinite increase of diameter or loss of control over curvature of metric in a minimizing sequence). In [NW1], [NW4] we developed a logico-geometric technique that enables one to single out large domains in Met(M) where a collapsing of a minimizing sequence cannot occur. (This will be explained in §9.)

To prove the existence of “virtual cycles” we take a closer look at the geometry and the topology of individual basins. We demonstrate that one can see in the geometry of basins of Met(M) combinatorics of interactions of the fundamental groups with homology groups of the manifold in the form appearing in at least several branches of topology of manifolds including surgery, concordance theory, and Waldhausen topological A-theory. And we can see this combinatorics for various (classes of) fundamental groups at once and even in the case when M itself is simply-connected! To be more precise there are cycles in basins of Met(M) which can be filled only by enormously large chains in Met(M) passing through elements of Met(M) of very large geometric complexity. Some of these cycles correspond to a sequence of cycles in BDiff(M#Σ_{i}), where Σ_{i} is a sequence of appropriately constructed homology spheres. The amount of freedom we have in constructing these homology spheres Σ_{i} enables us to see an astounding variability of homological properties of the basins of Met(M) for any M. The Hρ-invariant constructed in [We 1] plays an important role in this part of our story. The Hρ-invariant is an invariant which can distinguish nonhomeomorphic but tangentially homotopy equivalent closed manifolds; moreover, it is the only known invariant which can do this in the situation when the fundamental group of the manifolds is torsion-free.

It should be noted that in high dimensions, at least in theory, one can get a great deal of information about the global homotopy type of Met(M) in the concordance stable range by a combination of surgery theory [Wal], [We0], algebraic K-theory of spaces [Wld2], and an analysis of all the smooth transformation groups on M. Needless to say, this is a very hard project for most specific manifolds (and is not even theoretically solved, even for the “concordance stable range”). For instance, it seems hard to tell when π_{1}(Met(S^{n})) = 0.^{3}

The initial idea behind our work is rather simple: Recall that there is no algorithm which distinguishes M from homology M with different fundamental groups. (A homology M is, by definition, a smooth manifold with the same homology groups as M.) This known result is the corollary of the Adyan-Rabin theorem establishing the algorithmic

3 It boils down to the question of which isotopy classes of diffeomorphisms (which are essentially the same thing as exotic smooth structures on the sphere of one dimension higher) are represented by smooth periodic maps. That π_{1}(Met(S^{n})) can sometimes be non-zero follows from the work of Schulz [Sch]. unsolvability of the triviality problem for finitely presented groups that in turn follows from the algorithmic unsolvability of the word problem (cf. [Mi]). Now assume that for a certain topological property P there is no algorithm which distinguishes M from a homology M with property P. Then at least some basins of Met(M) must look like basins of the spaces of Riemannian structures on manifolds with property P. (We exploited this idea in [NW1] where the property P was non-vanishing of the simplicial volume). Here we apply this idea as follows: We use the invariant Hρ constructed in [We 1] distinguishing non-homeomorphic but homotopy equivalent manifolds with a fixed fundamental group (which can be torsion-free). Somewhat oversimplifying one can say that the invariant lives in the direct sum of homology groups of the fundamental group. It also has good realizability properties. The property P now will be having the prescribed non-zero value of Hρ.

Here are informal statements of two of our results:

Theorem 0.1. (Informal) For every closed smooth manifold M of dimension n > 4 there are infinitely many local minima of the diameter functional on the subset Al(M) of Met(M) consisting of isometry classes of metrics with curvature bounded in absolute value by 1. The local minima are represented by Riemannian metrics of smoothness C^{1,α} for any α ∈ [0, 1). Moreover, for any c.e. degree of unsolvability β the local minima of depth at least β are β-dense in a path metric on Al(M), and the number of β-deep local minima where the diameter does not exceed d is not less than exp(c(n)d^{n}) for a universal constant c(n) > 0. *

Precise definitions will appear in the body of the paper. (See, in particular §§1,2,9.) Informally, each c.e. degree determines a scale, and there are many distinguished local minima of diameter, that are deep at that scale. Their density in a path metric in Al(M) is only somewhat less then their depth. At smaller scales, of course, there will smaller “basins” that “come off” this one. And smaller ones that come off those. (Think about the construction of Koch’s curve.)

This picture is fairly uniform and densely repeated (in the coarse sense). However, at a less schematic level, one looks at the geometry of these basins. For these one sees that one has different fine level geometry. That is what is measured by the virtual cycles.

Remark: It is of crucial importance to us that the results of the above theorem are not that particular to the space Al and the diameter functional. See §18 below for the discussion of this important point.

Theorem 0.2. (Vague) There are infinitely many virtual cycles (in Al(M)), whose filling diameters are very large. Moreover, we can make the cycle die at any specified rate at most as large as the depth of the basin in which it lies.

Here is a specific rigorous version of the first statement of Theorem 0.2. (See §17 for the discussion of the second statement.)

* More precisely, the meaning of the last statement is the following: For any c.e. degree β there are increasing functions f_{β} and g_{β} equicalculable with the stopping time function for some c.e. set S with degree β such that the f_{β}(d)-deep local minima with value of diameter at most d are g_{β}(d)-dense.

Theorem 0.2. For any k ≥ 1, any compact manifold M of dimension that is sufficiently large in comparison with k, and any (Turing) computable function ϕ for all sufficiently large x there exists a k-dimensional cycle in Al(M) formed by metrics with diameter < x which bounds in Al(M) but does not bound in the subset of Al(M) formed by metrics with diameter less than ϕ(x).

Note that this cycle has the diameter not greater than 2x (with respect to the Gromov-Hausdorff metric), but any filling of this cycle must be of diameter at least ϕ(x) − x. This observation follows from the obvious fact that any two Riemannian manifolds of diameter ≤ x are d-close to a point and, thus, 2x-close to each other in the Gromov-Hausdorff metric. Note also, that the dimension restriction is probably not necessary, and we conjecture that the theorem is true for any manifold of dimension ≥ 5. The dimension restriction in the theorem appeared in our proof in connection with so called concordance stable range that plays an important role in calculations of the homotopy groups of Diff(M); see [Ig1]. Basing on the estimate in [Ig 1] it is sufficient to require in Theorem 0.2 that dim M > 9, if k = 1, dim M > 10, if k = 2, and dim M > 3k + 3, if k > 2.

Although a good part of the theory applies to give information uniformly about all manifolds of a sufficiently high dimension, the techniques we develop can be used to prove the existence of large scale differences in the geometry of Al(M) for different classes of manifolds. For example, for all sufficiently large n the filling function that measures for any r how much larger is the ball where homologically trivial rational 5-cycles in the ball of radius r die will be non-computable for S^{2n} but will be computable for hyperbolic manifolds or products of Kummer surfaces (see Theorem 17.1 in §17). In this assertion we consider the balls with respect to the path metric in Al(M) and these balls are centered at the base point. We consider this fact as one of the most important results of the present paper.

In §19 we outline a number of directions for a further study of geometry of Met(M) in the spirit of the present paper. In particular, we present a conjecture giving a more detailed information about depths and densities of local minima. We plan to establish a weaker version of this conjecture in a subsequent paper.

We remark that everything we have said about diameter regarded as a functional on Al(M) (or equivalently about sup |K|diam^{2} regarded as a functional on Met(M)) applies equally to many other functionals on Met(M) (see the §18) and on other spaces. As an example, we mention crumpledness functionals on (connected) spaces of hyperspheres in Euclidean spaces Emb(S^{n}, lR^{n+1})/Diff(S^{n}) for n > 4 ([N0]), or on the space Emb(S^{n} ⊂ S^{n+2}). (The unknotted embeddings form a very interesting component of this space. It also is the only known to us example where it is not necessary to take quotient with respect to the action of the diffeomorphism group. The arguments are the natural adaptation of [NW3] to the current context.)

It seems plausible that spaces of almost complex and maybe even symplectic structures have similar fractal features (but we do not yet have any specific results in this direction).

One of the purposes of the present paper is to give an introduction to all these ideas in a fashion that is as accessible to a non-specialist as possible. We organized this paper into a number of very brief sections most of which either sketches one idea or combines several that have arisen earlier. We also tried to make this paper as non-technical as possible omitting virtually all technical details. Several of the sections have appendices that contain discussions of especially interesting or important technical aspects of our story. These appendices (§3A, §4A, etc.) can be skipped if desired.

Finally note that this paper represents an exploration of Met(M). In our travels we are uncovering many rich regions, but what is accomplished is precisely that: a kind of rough overview of an open subset of this space. There are, no doubt, many features, and chunks of the space that we have not yet begun to think about.

1. [NW1]

Let us set the stage by recalling a part of the main result of [NW1].

Theorem 1.1. Let M^{n} be a closed smooth n-dimensional manifold, n > 4 and let Al(M) be the Gromov-Hausdorff closure of the subset of Met(M) consisting of metrics where the absolute value of the sectional curvature is bounded by 1. Then the diameter functional D : Al(M) → R has infinitely many deep local minima represented by C^{1,α} metrics on M for any α ∈ (0, 1). The number of local minima with Diam < d that are deep is bounded from below by exp(c(n)d^{n}) for some constant c(n) > 0.

The elements of Al(M) belong to the class of smoothness C^{1,α} for any α < 1 ([GW],[Pet]). For any element of Al(M) the sectional curvature is defined at almost any point of M and its absolute value does not exceed 1. Moreover, elements of Al(M) are Alexandrov spaces of curvature bounded from both sides, and have virtually the same nice geometric properties as Riemannian manifolds with sectional curvature between -1 and 1 (see the survey paper [BN]). We do not know much more about the set of local minima of D on Al(M), and whether these are smoother than a general metric in Al(M).

To make sense of the theorem, we must define what we mean by a “deep” local minimum. Definition. A local minimum p for ϕ : X → lR is K-deep if for any path f : [0, 1] → X with f(0) = p and ϕ(f(1)) < ϕ(p), there is some t for which ϕ(f(t)) = ϕ(p) + K.

Since D is unbounded, any global minimum is infinitely deep, but no local minimum which is not a global minimum is infinitely deep since Riem(M) is connected.

Remark. One can coarsen the notion of depth by allowing “coarse paths” which are sequences of jumps of uniformly bounded distance. While the depth measure will change, the theorem remains valid.

While local minima always exist, it is worth remarking that global minima do not. For instance, if M = T^{n}, then by rescaling a fixed flat metric one gets a sequence of flat metrics on T^{n} with diameters tending to zero but, of course, there is no metric of diameter 0. This is a typical example of a nonconvergent minimizing sequence. One of the key issues is to find locally minimizing sequences which cannot “fall off the space”.

Another feature of the theorem is that it is constructing more local minima than variational methods, even when they work, provide for. A hint is given by the depth. Local minima with varying value of D but of large depth force the sublevel sets of a functional to be disconnected.

2. How deep is “deep”?

We did not say how deep the local minima are in the previous section. The answer is that they grow faster than exp ( exp ( … ( exp(d^{d}) …))) where we exponentiate [exp(d^{d})] times. (Here d is the value of D at the local minimum p.)

OK. No one really proves an estimate like that. The answer we gave in [NW1] is the following. For any recursive function f of d, the theorem is correct for f(d)-deep critical points.

Recall that the class of recursive computable functions coincides with the class of Turing computable functions which in turn coincides with the class of functions computable by a computer program written in one of the programming languages, such as, BASIC, FORTRAN, PASCAL or C (using only the integer type of data). To deal with real values of d we can require that that f(d) = f([d]) is determined by the integer part of d. (Any introductory recursion theory book can serve as a reference, see e.g. [DSW].) Thus the notions of recursive and computable functions coincide. In this paper we prefer to use terms “computable” and “computably enumerable” (or “c.e.”) instead of the more classical terms “recursive” and “recursively enumerable” (or “r.e.”).

The function mentioned above is certainly, from the point of view of most conventional analysis, a rapidly growing function, but from the point of view of logic it’s pretty low on the ladder: it is primitive recursive.

In any case, a quite simple diagonal argument (see [DSW]) shows that there are functions that grow faster than any computable function. An example is the “busy beaver function” β(n) which is the maximum number of steps that it takes any of the first n Turing machines (encoded in some fashion) to complete any calculation performed on inputs of at most n bits. (One maximizes over calculations that actually halt; this is the sup over a finite set. The rub is that since the Halting problem is unsolvable, one does not know when one has actually computed β(n) or just a large lower bound – maybe one of the programs will yet halt on some input somewhere down the line.)

In a precise sense, the depth function for the local minima is of the same order as β(n). This is a much stronger statement than merely that it grows faster than any computable function. In particular, it means that it grows faster than an infinite number of other nonrecursively bounded noncomputable functions.

Finally, for reference, in addition to Turing machines being useful as a measure of rates of growth, we also find them useful in the description of types of subsets of the integers (or, words in a group, or …): A set is computably enumerable (c.e.) if there is a Turing machine whose output is exactly that set (or equivalently, there is a Turing machine which eventually stops its work (halts) iff the input lies in that set). It is computable if both it and its complement are c.e. or equivalent, iff its characteristic function is computable. The basic example of an c.e. noncomputable set is ((n, m)|f_{n}(m) halts) where f_{n} is the n-th Turing machine in some Gödel ordering. A reader not familiar with the notion of Turing machines can think about computer programs written in his favourite programming language using only the integer data type as above. Computable sets are sets such that the membership there can be checked by means of an algorithm (= a computer program). A set A is computably enumerable if there exists a computer program always confirming that x is in A if this is, indeed, so but possibly running an infinite time if x is not in A.

3. How close are these minima?

One should not think that these deep basins are steep. The functional we have chosen to investigate (that is, diameter D) is clearly Lipschitz with constant 2 in the Gromov-Hausdorff metric (cf. [Pe 1], [Pe 2] for the definition and properties of the Gromov-Hausdorff distance on the space of isometry classes of all compact metric spaces and therefore on M). We prefer however to endow Al(M) with the path metric discusssed in §3A. Define the width of a basin as the maximal radius of a metric ball contained in the basin. The distance in the path metric is obviously not less than the Gromov-Hausdorff distance. Thus, the width of the basins is not less than half of their depth.

Another of our goals is then to show that there are other local minima which lie within these basins, i.e. which are at the bottom of their own basins; these subbasins are also very deep: deeper than any computable function. But they are incomparably^{4} shallower than the β-deep local minima referred to in the previous section. (See §11 for more details.)

Note: The Lipschitzness of D gives a lower bound in terms of depth of how dense these local minima are. On the other hand, in some sense it gives the almost optimal lower bound: The methods of [NW1] can be easily adapted to prove the existence of local minima with a prescribed lower c.e. bound for their depth which will be dense with the density in the path metric only somewhat quicker growing that the lower bound for the depth (see below).

This is essentially a consequence of the fact that the theorem is true for all manifolds, simultaneously! Since the points of Met(M) are manifolds, the theorem which produces even a single local minimum, must produce one, not too far from the manifold (in the path metric)! A proof can be provided by reexamining the constructions from [NW1] (and is quite straightforward).

3A. Path metric on Al(M)

Along with the Gromov-Hausdorff metric one can consider a path or a “jump” metric on Al(M): The distance between two metrics on μ_{1}, μ_{2} on M is defined as the length of the shortest path connecting these metrics in Al(M). More formally, we can define this distance as lim_{ϵ⟶0} inf Σ_{i}d_{GH}(ν_{i}, ν_{i+1}), where μ_{1} = ν_{1}, …, ν_{k} = μ_{2} is a sequence of metrics in Al(M) such that for any i d_{GH}(ν_{1}, ν_{2}) ≤ ϵ, and the infimum is taken over all such finite sequences. We will call this metric the path metric on Al(M). (There are other ways to define this distance. For example, it can be defined as the infimum of lengths of all piecewise smooth liftings to Riem(M) of paths between μ_{1}, μ_{2} in Al(M) ⊂ Riem(M)/Diff(M). Here the infimum is taken over all continuous paths between μ_{1} and μ_{2} that admit a piecewise smooth lifting to Riem(M) and over all such liftings. All qualitative results of the present paper will remain valid for this definition of the path metric.)

4 In the poetic, nonmathematical sense. Mathematically, they are very definitely shallower!

Another reasonable choice of the path (or rather “jump”) metric is to replace taking the limit as ϵ ⟶ 0 by fixing a specific positive function ϵ(μ, ν), (μ, ν ∈ Al(M)), and considering the infimum over all sequences of elements of Al(M) {ν_{i}}_{i} such that μ_{1} = ν_{1}, ν_{k} = μ_{2} and d_{GH}(ν_{i}, ν_{i+1}) does not exceed ϵ(ν_{i}, ν_{i+1}). For example, choose ϵ(ν_{1}, ν_{2}) = ϵ(n, min{vol(ν_{1}), vol(ν_{2})}, max{diam(ν_{1}), diam(ν_{2})}) > 0 to be some specific sufficiently small number such that the distance between any two elements of Al(M_{1}) and Al(M_{2}) of diameter ≤ D and volume ≥ v is greater than ϵ(n, v, D) if M_{1} and M_{2} are not diffeomorphic. (The existence of such ϵ is well-known and a specific lower bound can be found, for example, in [Cha]. The continuity of volume and diameter on Al(M) implies the finiteness of so defined distance.) Such choice of metric enables one to disregard the effects of potentially bad local geometry of Al(M) and to concentrate only on large scale phenomena. This choice is especially appropriate when instead of the curvature restriction |K| ≤ 1 that we are focusing on in this paper one considers weaker curvature restrictions and it becomes difficult to estimate the limit when ϵ ⟶ 0 in the definition of the path metric.

4. Review of some results from global differential geometry

1. A key to our existence theorem is the remarkable compactness theorem of Cheeger and Gromov, together with some later refinements by Peters, Greene and Wu, Berestovskii and Nikolaev.

Theorem 4.1. The space of isometry classes of compact closed n-dimensional Riemannian manifolds with two sided bounds on the sectional curvature, an upper bound on diameter and a lower bound on volume is totally bounded and its limit points in the space of isometry classes of all compact metric spaces are isometry classes of C^{1,α}-smooth n-dimensional Riemannian manifolds.

One can regard this result as a geometric version of the Ascoli-Arzela theorem, where the curvature bound plays the role of the derivative bound, the diameter bound plays the role of the uniform boundedness, and the volume bound is a new geometric feature without an analog. In fact, the classical result of Gromov implies that the precompactness result will hold even under only a lower bound for the Ricci curvature and an upper bound of diameter. Alternatively, one can get the precompactness assuming an upper bound for the volume and a (positive) lower bound for the injectivity radius (cf. [Pe 1]).

2. Another class of geometric results important for our program are theorems establishing that two sufficiently close Riemannian manifolds satisfying some common restrictions on their curvature, volume, etc. are diffeomorphic (or homotopy equivalent, or at least have isomorphic fundamental groups) ([Pet], [GP], [F], [An], [Gr4], [CC2]). Such existence results are available in the case of sectional curvature bounded from both sides (diffeomorphism, cf. [Pet]), sectional curvature bounded from below (homeomorphism; cf. [GP], [F], [Pe 1], [Gr 4]), Ricci curvature bounded from below (isomorphism of fundamental groups assuming that they are torsion-free proven by Anderson [An]), volume bounded above and injectivity bounded from below and some other cases ([F], [CC2], Theorem A.1.4).

3. The last major geometric input are some results of Gromov [Gr 1],[Gr 2, section 6.6] where it was established that for some homotopy types of manifolds a lower bound for the Ricci curvature automatically implies a (positive) lower bound for the volume. To understand this phenomenon consider first the two-dimensional case. If M is a surface of genus > 1 and therefore of Euler characteristic ≤ −2, then the Gauss-Bonnet theorem implies that for any metric of curvature K ≥ −1 −vol(M) ≤ ∫ Kdμ = 2πχ(M) ≤ −4π. Hence vol(M) ≥ 4π. Thurston observed that a similar phenomenon generalizes for higher-dimensional manifolds admitting hyperbolic metrics. Gromov systematically analyzed the phenomenon giving sufficient conditions in terms of the fundamental group of the manifold and the image of its fundamental homology class in H_{n}(π_{1}(M)) under the classifying map. One of these two independent sufficient conditions is non-vanishing of simplicial volume (cf. [BP] for the definition and an accessible proof as well as the original paper [Gr1]). Another condition was stated in section 6.6 of [Gr 2] in terms of a classifying space of almost nilpotent subgroups.

Note that for such manifolds one does not need a lower bound for the volume in the text of Theorem 4.1 since it automatically follows from the lower curvature bound. Thus, for such manifolds the sublevel sets of diameter on Al(M) are compact and the existence of at least one local minimum of diameter in Theorem 0.1 is obvious.

A reader who would like to learn more systematically about the Riemannian geometry relevant here is referred to [Cha], [Pe 2], [Fu], [Ch], [Be] and especially [Gr4] in addition to the references cited above.

4A. More results from global differential geometry.

1. The structure of Gromov-Hausdorff limits of manifolds with a uniform lower bound for the Ricci curvature (with and without uniform lower volume bound) was investigated in the series of papers of Cheeger and Colding (cf. [CC1,2]). Note that even in the non-collapsed case the limit point can have a different topology from the topology of the converging manifolds and can have topological singularities. Even earlier the structure of the limit points of sequences of Riemannian manifolds with uniform lower bound for the sectional curvature was investigated by Yu. Burago, Gromov and Perelman ([BGP]). The limit objects in this case are Alexandrov spaces of curvature bounded below. In the important (for us) non-collapsing case (when a uniform lower volume bound is available) the limit will be a manifold homeomorphic to any manifold in the sequence with a sufficiently large number. However metric singularities (studied by Perelman, [P]) can occur. (Think about a sequence of smooth convex surfaces in lR^{3} converging to a convex polytope, or more generally, to a non-smooth convex singular surface with infinitely many “corners”.) Note that volume can be extended to a continuous (!) functional on the closure of the space of isometry classes of Riemannian metrics of curvature bounded from below. In the case of sectional curvature this highly non-trivial fact was proven in [BGP]; in the case of Ricci curvature this fact is due to Colding ([C]).

2. One can combine results about the stability of topology under small perturbation in the Gromov-Hausdorff metric with the precompactness. As the result we see that for any d there exists a finite net N_{n}(d) in the the space of isometry classes of all ndimensional Riemannian manifolds with diameter less than d and |K| ≤ 1 such that any point of this space and all sufficiently close points of the net (including the closest) represent diffeomorphic manifolds. Similar nets exist in the case, when the condition |K| ≤ 1 is replaced by a weaker condition K ≥ −1 if we require only homotopy equivalence (or even homeomorphism) of manifolds corresponding to close points. Under some mild restrictions on the fundamental groups of considered manifolds there exist similar nets in space of metrics satisfying Ric ≥ −(n − 1) and diameter ≤ d, but here we can demand only the isomorphism of the fundamental groups and equality of simplicial volumes of manifolds corresponding to a point and to all sufficiently close points of the net ([NW4]). However, it is surprisingly difficult to find an algorithm constructing such nets as a function of d despite the fact that one can give an explicit upper bound for the number of points in such nets as well as an explicit lower bound for a sufficient density. In [NW1] we constructed such nets in the situation when the sectional curvature is bounded from both sides. We smoothed out Riemannian manifolds using the Ricci flow (as in [Ba], [BMR], [Ha]) to do this (see the last section of [NW1]). In cases when K ≥ −1 or Ric ≥ −(n − 1) one can effectively construct required nets in larger spaces of isometry classes of metric spaces satisfying certain conditions making them similar to manifolds with Ricci curvature bounded from below ([NW4]). In this construction we used the work of Cheeger and Colding ([CC1], [CC2]) as well as effective versions of some results from [CC1], [CC2] proved by Yu Ding [Dg].

5. A Toy Problem

We follow [N4] in exposing a result asserted by Gromov.

Theorem 5.1. ([Gr 0]). If M is a closed manifold whose fundamental group has unsolvable word problem, then M has infinitely many contractible closed geodesics.

Theorem 5.2. ([We3]) The same is true if the Dehn function is superexponential.

Theorem 5.3. ([N4]) The number of closed contractible geodesics necessarily grows exponentially in length if the time bounded Kolmogorov complexity of the word problem for a certain computable time bound is exponential.

Remark: The time-bounded Kolmogorov complexity in the Theorem 5.3 can be exponential even if the word problem is solvable. As it was observed in [N4] this implies the existence of the groups with solvable word problems such that the number of contractible geodesics on any closed Riemannian manifold with that fundamental group grows exponentially. The other author ([We5]) observed that this class of manifolds contains K(π, 1) manifolds (using constructions described below, together with the method of M. Davis [Da]). For these manifolds, the free loop space of the universal covering is contractible, so the usual variational method of Lusternick-Fet, Morse, etc … does not lead to any contractible geodesics^{5}.

The idea behind Gromov’s theorem is this. Suppose M is a Riemannian manifold with fundamental group π and no contractible geodesics. Then we can solve the word

5 Indeed, there are aspherical manifolds with no nullhomotopic closed geodesics: namely, any nonpositively curved manifold. problem as follows: For any word in the generators of π, construct a simple closed curve representing that word in the fundamental group, and apply curve shortening. If one asymptotes to a closed curve that has positive length, then it must be nontrivial, but if it continually shortens to small length, then it is contractible. If there were finitely many closed geodesics, we could still incorporate them into an algorithm, which would contradict our hypothesis: One just should check if the final curve is one of the contractible closed geodesics.

There are some difficulties with implementing this. How algorithmically can one give a manifold and compute the gradient flow for energy? Also, and more seriously, how does one recognize that one is near a geodesic; perhaps one has very small gradient, and therefore it’s been years since the curve perceptibly shortened, but one has no idea whether that’s because one’s near a geodesic, or just going through some almost geodesic type curves.

A way around this is to take a very fine cover of the space of simple closed curves, so that any two points in the same element of the cover are homotopic. (The number of balls one needs to do this is exponential in the length. An easy way to accomplish this is to use a fine triangulation of the original manifold and use fine simplicial loops as centers of balls in the free loop space.) Then consider the adjacency graph of this cover, that is clearly effectively computable.

If the gradient flow would shorten one ultimately down to a point than one could look at the shadow of this trajectory in the net, and one would see a path through curves of length at most, say 5L, where L is the length of the curve, to a curve of length at most injectivity radius of the manifold/10. This can be tested for, and would lead to an algorithm to solve the word problem. (Indeed, it would lead to a bounding disk of at most exponential area, since the graph has only exponentially many vertices.)

Note that one does not really need to have any kind of geodesic flow for this argument. Any path can be shadowed in the nerve of the cover and therefore in the adjacency graph. Thus, the use of effective coverings to get solutions to algorithmic problems can well be applied to nonsmooth functionals.

6. Why Exponentially Many ([N4])?

Certainly one does not expect more than exponentially many closed geodesics, for entropy reasons. (The generic metric has only that many closed geodesics.) To get that many, one invokes the theory of Kolmogorov complexity.

Kolmogorov complexity measures how many bits of oracle information one needs to solve a decision problem for all instances of complexity (e.g. of length) less than N as a function of N. Time-bounded Kolmogorov complexity measures the number of bits of oracle information required to solve a decision problem in a time that does not exceed a given function and is actually more appropriate for our needs.* It is clear from the definitions that time-bounded Kolmogorov complexity always majorizes Kolmogorov complexity.

* Both Kolmogorov complexity and time-bounded Kolmogorov complexity are defined within to a constant summand ambiguity due to the choice of the model of computations. (For example, one can always include several bits of oracle information into a program and to regard them as a part of the algorithm and not of the oracle information.)

Sometimes it can be substantially larger than the Kolmogorov complexity: According to a fundamental result of Barzdin ([B]) there exists a computably enumerable set such that its membership problem for all numbers ≤ n has time-bounded Kolmogorov complexity ≥ n/const(λ) − const for any computable time bound λ whereas the usual Kolmogorov complexity is always ≤ ln n + const. (One can ask the oracle how many elements are there ≤ n, and the complete answer of this question can then be algorithmically applied to solve the membership problem for our set.) We refer the reader to [ZL], [LV], [D], [N2], [N4] concerning the exact definition and properties of Kolmogorov complexity and time-bounded Kolmogorov complexity.

The algorithm described in the previous section to solve the word problem in the situation when there are finitely many contractible closed geodesics can be turned into an algorithm using oracle information when the number of contractible closed geodesics of length ≤ x can grow to infinity with x. One encodes all of the closed contractible geodesics of a length less than x and includes them in an the algorithm as additional oracular information.

Thus, if the time-bounded Kolmogorov complexity of the word problem for the fundamental group of a Riemannian manifold for an appropriate computable time bound is exponential, there must be an exponentally growing number of closed contractible geodesics. Barzdin’s theorem together with the standard machinery for embedding computable set theory into the group theory implies the existence of such finitely presented groups.

7. Witness Constructions.

In section 5, we used groups with complicated logical structure to ensure some complexity of the geometric structure of manifolds with the given fundamental group. The theorems we are shooting for apply to arbitrary manifolds with even trivial fundamental group.

The relevant group theoretic idea comes from classic work of Adian and Rabin who showed that many properties of groups cannot be algorithmically decided. The most obvious (and important) of these is triviality.

We will not state their theorem in generality, see e.g. the survey [Mi]. The idea behind the theorem is this. Consider a torsion free group G with unsolvable word problem, with, say two generators g and h. Then consider the HNN extension <g,h,t,s∥tgt^{−1} = γ and shs^{−1} = γ >, where γ is a word in G. The group G embeds in this group iff γ is nontrivial. If γ is trivial, then this group is actually the free group F_{2} = ⟨t, s⟩. Already we see that freeness cannot be algorithmically decided.

In general, one does a more complicated series of amalgamated free products and HNN extensions to produce from an arbitrary element in any group a witness group, which will have a given property (say, be trivial) if the element if trivial, but will contain the given group as a subgroup if the element if nontrivial.

8. Geometric witness constructions.

The prototypes for this kind of theorem are to be found in the proofs of the theorems of Markov who showed that, in general, the homeomorphism problem for four dimensional manifolds is undecidable, and of Novikov, who showed that no manifold of dimension at least five is algorithmically detectable. We refer the reader to [BHP] for an excellent introduction to ideas of Markov. A detailed proof of S.P. Novikov’s theorem on the algorithmic unrecognizability of the standard sphere of dimension n ≥ 5 can be found in the Appendix of [Na 4]. The idea is to produce algorithmically manifolds M_{γ} that will be homology spheres and which have fundamental group the witness group for the element γ of G. By the generalized Poincare conjecture (Smale’s theorem) M is homeomorphic to the sphere, and, better yet, M# − M is diffeomorphic to the sphere iff γ = e; for if γ ≠ e, then M is not simply connected. For any N, then, one cannot distinguish N from N#M# − M, for to do so, one would be able to solve the word problem for G.

The construction of homology spheres with the right fundamental group is not hard by explicit handle construction. (See [Ke].) Although the witness groups need not actually be fundamental groups of homology spheres, their universal central extensions can be algorithmically constructed, and those are automatically fundamental groups of homology spheres.

In the course of proving our theorems we will build witnesses to the triviality of words in a fixed finitely presented group G which are smooth n-dimensional manifolds with the same homology groups as the considered manifold M such that these witnesses (1) have “good” geometric properties, if they are nontrivial. (These properties ensure the amount of compactness required for the existence of critical points of various interesting functionals on the space of Riemannian structures on the witness. One of these properties is non-vanishing of the simplicial volume; see section 4 above); and (2) whose fundamental group will have appropriate homological properties (in order to get desired properties of the virtual cycles). In order to space our critical points suitably around Met(M), we can also vary the “seed” group in terms of the degree of unsolvability and other measures of complexity.

In the next several sections we will explain how this can be done.

Remark: The witnesses corresponding to trivial elements play especially important role in our story since they appear in the construction of local minima and non-trivial basins. In order to get a feeling for what is going on it is worth considering the geometry of witnesses of triviality in the case when M is S^{n}. In this case witnesses corresponding to trivial elements will be Riemannian manifolds diffeomorphic to the sphere (using Smale’s proof of the Poincare conjecture) which are hard to recognize as being the sphere. Infinitely many of them will have short closed geodesics that cannot be contracted to a point without vastly increasing the lengths of these curves (see [N3] for more details). Moreover, any path (in Al(M)) from infinitely many of these metrics to a metric of a sufficiently small volume must be enormously long and must pass through metrics of enormously large diameter. (The length of the path depends on the degree of unsolvability of the Turing machine used to construct the group.) These properties will be preserved under appropriate Riemannian connected sums of arbitrary Riemannian manifolds with the trivial witnesses. (Of course, the diffeomorphism type of the manifolds does not change under such connected sums.)

8A. Geometric witness construction starting from a Turing machine and its input.

One can combine the geometric witness construction with the construction of a finitely presented group such that the halting problem for a given Turing machine reduces to its word problem: For any Turing machine T and its input ω one constructs a Riemannian homology sphere Σ^{n}(T, ω) of a presecribed dimension n ≥ 5 such that this homology sphere is diffeomorphic to S^{n} if and only if T halts with ω. Now it is natural 1) to try to make the geometric complexity of Σ^{n}(T, ω) to be closely related to the length of the description of T + the length of ω; 2) to try to ensure that if T halts with ω then the length of the shortest path in Al(S^{n}) connecting Σ^{n}(T, ω) with the standard metric on S^{n} is closely related with the time of work of T with ω. The problem 1) was completely solved in [N2] and [NW 1]. It is quite crucial for us here that the halting time and the length of the shortest path are in the same computable equivalence class. But, of course, one can establish a much stronger connection between these two functions. We plan to do this in a subsequent paper. As a result we will obtain much stronger results about depths and densities of local minima than the results presented here. (See §19 for more details.)

9. Designer Homology Spheres.

Our approach to the problem of non-Gromov-Hausdorff-convergent minimizing sequences is through the compactness theorems of §4. Our main problem is that we need a way to obtain a priori lower bounds on volume. A way to get such a lower bound for volume out of nothing was found in [NW1].

Some of the ideas from this section will be used again in §16 to show that at each scale, there are infinitely many different geometries present among the basins. The scales correspond to the halting time of the “seed” Turing machine (corresponding to the group with the unsolvable word problem) and the denseness of basins as well as the infiniteness of their number follow from the possibility to add the “trivial witnesses” to any metric on M.

We will sketch here one of the methods used in [NW1], based on the idea of simplicial norm [Gr1]. (There is another method based on a result of [Gr3], section 6.6 that also provides a positive lower bound for the volume of a Riemannian manifold with Ric ≥ −(n− 1) providing that this manifold represents a non-vanishing cycle in a suitable classifying space.)

Theorem 9.1. ([Gr 1]) If M^{n} is any closed smooth n-manifold with Ric(M) ≥ −(n − 1), then vol(M) > c_{n}∥[M]∥, where c_{n} > 0 is a universal constant just depending on the dimension, and ∥[M]∥ denotes the simplicial norm.

We prove the following:

Theorem 9.2. ([NW1]) For every n > 4, there is a Turing machine which produces on any input k an output which is a homology sphere Σ_{k} such that for each k, either

(a) Σ_{k} is diffeomorphic to S^{n}, or

(b) ∥[Σ_{k}]∥ > 1.

Furthermore, {k| case (b) holds} is not computably enumerable.

Note: 1) {k| case (a) holds} is c.e. 2) If case (b) holds then for any Riemannian metric on Σ_{k} with Ric ≥ −(n − 1) the volume of Σ_{k} will be greater than c_{n}.

This theorem is proven by a geometric witness construction that melds a fixed homology sphere with non-zero simplicial norm with homology spheres obtained from a group with unsolvable word problem by the more elementary witness construction explained in sections 8, 8A.

Where does even one homology sphere with nonzero simplical norm come from? It is a combination of three beautiful (even astounding) results. The first is due to Gromov and Thurston [Gr1] and is proven by the method of “straightening simplices”.

Theorem 9.3. If V is a negatively curved manifold, and f : M^{n} → V is any map such that n > 1 and f_{∗}[M] ≠ 0, then ∥[M]∥ ≠ 0.

Thus we must try to produce homology spheres that represent cycles in a negatively curved manifold. Our search is abetted by the following theorem of Hausmann and Vogel [H], [V] that is proven by a clever application of Cappell-Shaneson’s homology surgery theory [CS]. Before stating this theorem recall that the + construction is the neutron bomb of homotopy theory; it takes a space and kills its fundamental group (to the extent possible) while leaving its homology intact. For spaces with perfect fundamental group it can be defined as follows: first kill the fundamental group by adding 2-cells killing its generators, then restore the second homology group by adding 3-cells killing the new two-dimensional homology classes that appeared as the result of addition of 2-cells. In the general case when the fundamental group is not necessarily perfect we can perform this construction for any perfect subgroup of the fundamental group. The perfectness guarantees that all homology groups of the resulting space will be isomorphic to the homology groups of the original space.

Theorem 9.4. Suppose Γ is a finitely presented super-perfect group (i.e. H_{1}(Γ) = H_{2}(Γ) = 0) and n > 4. Then {Σ^{n}|π_{1}(Σ^{n}) = Γ; H_{∗}(Σ^{n}) = H_{∗}(S^{n})} up to concordance through homology cylinders with fundamental group Γ is in a natural 1 − 1 correspondence with θ^{n} ⊕ π_{n}(BΓ^{+}), where θ^{n} is the Kervaire-Milnor group of smooth structures on the n-sphere ([KM]) and BΓ^{+} is the result of performing the Quillen + construction to the classifying space of the group Γ.

The class represented by Σ^{n} produced by the Hausmann-Vogel theorem in the group homology H_{n}(BΓ) is just the image of the element of π_{n}(BΓ^{+}) under the composition of the Hurewicz homomorphism and the inverse of the inclusion isomorphism H_{∗}(BΓ) ⟶ H_{∗}(BΓ^{+}).

In particular, if h ∈ H_{n}(BΓ) is a class such that its image in H_{n}(BΓ^{+}) under the inclusion isomorphism is spherical, then there exists a homology sphere Σ^{n} with the superperfect fundamental group Γ such that the image of the fundamental homology class of Σ^{n} in BΓ under the homomorphism induced by the classifying map Σ^{n} ⟶ BΓ is h. See §9A for a further discussion of the Hausmann-Vogel theorem.

By combining the previous two theorems we need to find negatively curved manifolds whose homology and “homotopy” (i.e. the homotopy of the + construction) is under good control. The main input for this is a deep theorem of Clozel [Cl 2], (proven by Weil conjecture methods together with hard results within the Langlands program on eigenvalues of Hecke operators, etc.) We will phrase this result somewhat imprecisely, referring the reader to the original paper.

Theorem 9.5. There are uniform lattices in U(n, 1) whose only real values cohomology are, aside from powers of the Kahler class, in dimensions n+1−a, n+1−a+2, …, n+1+a, for each divisor a of n + 1.

Remarks:

(1) The application below uses both the existence of homology in these dimensions, and the nonexistence in any other dimensions.

(2) These results are rather stronger than what is predicted by the usual representation theoretic Matsushima method in the cohomology of groups. The above theorem can be interpreted as asserting that certain representations in the formula arise with multiplicity 0.

The lattice corresponding to U(2n − 1, 1) has a class in dimension n that turns out to be (after +) spherical. These cannot, however, be fundamental groups of homology spheres because they are not superperfect: they could well have nontrivial finite H_{1} and, because of the Kahler class, they certainly have nontrivial H_{2}. These trifles can be fixed with the aid of some amalgamated free products and universal central extensions. (The relevant theorems about simplicial norm and amalgamated free products and extensions along and by amenable groups can be found in [Gr1]). When one is done, one still has to check that the relevant classes in homology that we get from Clozel’s theorem are in the image of Hurewicz. This isn’t obvious, but a calculation using rational homotopy theory shows that some finite multiple of such a class is spherical – which gives the nonzero-simplicial norm homology sphere, by Hausmann-Vogel, and, ultimately, as we said before, the Turing machine with output of our desired type by a witness construction.

The work of Clozel is extremely deep and complicated. So, it might be worthwhile to explain another approach. We found another way to construct homology spheres based on the work of Gromov [Gr 2] instead of [Gr 1] (and on the Hausmann-Vogel theorem). One of the results in section 6.6 of [Gr 2] gives a positive lower bound depending only on n for the volume of any Riemannian manifold with Ric ≥ −(n − 1) providing that this manifold satisfies a certain property which is related to the non-vanishing of simplicial volume but is much easier to check. The problem of constructing homology spheres with this property also boils down to the construction of arithmetic or S-arithmetic groups with certain homology properties. But the examples of such S-arithmetic groups that we found turn out to be much simpler: One starts from the most well-known example of the fundamental group of a manifold of dimension ≥ 3 of constant negative curvature, namely, a torsion-free congruentz subgroup of SO_{F} (n+1, ZZ[\sqrt{2}]), where F (x_{1}, …, x_{n+1}) = x_{1}^{2} + … + x_{n}^{2} − \sqrt{2}x_{n+1}^{2}. To produce a group that we need, it is sufficient to replace here the ring ZZ[\sqrt{2}] by ZZ[\sqrt{2}, \frac{1}{5}]. Instead of \frac{1}{5} one can take here \frac{1}{p} for any prime p = 4k + 1. The idea is that for such p the equation x^{2} + 1 = 0 has a solution in the p-adic numbers and, thus the rank of the corresponding adelic group is large. The proof that these groups have required properties is quite non-trivial but uses much less of mathematics related to the Langlands program: namely, [BorWal] versus the work of Clozel [Cl1], [Cl2] plus the work of Kottwitz, Moeglin-Waldspurger and others used by Clozel.

Remark: In dimension 4, not every superperfect group is the fundamental group of a homology sphere (see [HWe]); we thus don’t know whether the triviality problem is decidable for fundamental groups of homology 4-spheres, nor do we know whether there’s an example of a 4-dimensional homology sphere with nonzero simplicial norm.

9A. Sketch of the proof of the Hausmann-Vogel theorem

The part of Theorem 9.4 that is most important for us is that for every class h ∈ H_{n}(BΓ) that becomes spherical in H_{n}(BΓ^{+}) there exists a n-dimensional homology sphere Σ^{n} with the fundamental group Γ such that h is the image of the fundamental homology class of Σ^{n} under the homomorphism into H_{n}(BΓ) induced by the classifying map F : Σ^{n} ⟶ BΓ. But first observe that if, conversely, h ∈ H_{n}(BΓ) is the image of [Σ^{n}], (π_{1}(Σ^{n}) = Γ), under the homomorphism induced by the classifying map, then applying the + construction to F we obtain a map F^{+} of S^{n} = (Σ^{n})^{+} into BΓ^{+} such that F_{∗}^{+}([S^{n}]) = h^{+}. Therefore h^{+} is spherical.

Now let us explain how to construct the required homology sphere Σ^{n} if h^{+} ∈ H_{n}(BΓ^{+}) is spherical. Let f represent a map S^{n} to BΓ^{+} such that h^{+} is the image of [f] under the Hurewicz homomorphism. Consider the homotopy pullback of the maps f, incl : S^{n}, BΓ ⟶ BΓ^{+}. This space has fundamental group Γ, and is an integral homology sphere. The homology sphere we are interested is a manifold which maps degree one to it. (Degree makes sense since it is a homology sphere!)

There is some manifold that has a degree one map to it, even a hypersurface, since its suspension has the homotopy type of the sphere. The transverse inverse image of this homology sphere under the homotopy equivalence is a manifold with a degree one (normal) map to the homology sphere. At this point one wants to do homology surgery to make the map an isomorphism on the fundamental group and a homology equivalence. This can be achieved using the Cappell-Shaneson theory. It turns out that the obstruction groups for this case vanish (or, more precisely are the same as the surgery obstruction groups for simply connected surgery – and therefore contribute nothing because we’ve arrange for our degree one normal map to bound a ”hemisphere”). That’s a theorem from Hausmann’s thesis. For odd dimensions, vanishing is in the original paper of Cappell and Shaneson [CS]– odd homology surgery obstruction groups inject into odd L-groups, which here vanish.

10. Existence of some local minima

We can now assemble all of our ingredients to prove the existence of local minima for D.

Let f be any computable function. We will first show that for some d, D^{−1}((0, d]) ⊂ Al(M) must be disconnected, and that there must be components that don’t connect within D^{−1}((0, d + f(d)]).

Then we’ll show that there are such components for which volume is bounded from below and inf(D) on such a component is the desired local minimum.

After that, we’ll worry about how many of these there are.

Why must there be many components? If not, we will solve the word problem for a suitable unsolvable word problem group. More precisely, consider M with any fixed Riemannian metric and consider the output of the Turing machine of the previous section, and consider the Riemannian manifolds M#Σ_{k}. Rescale to have sup |K| ≤ 1. View these as lying within a chunk of the space of isometry classes of all compact n-dimensional Riemannian manifolds with |K| ≤ 1 where one has a lower bound on volume and upper bound on diameter d_{k} as well as in a larger space where diameter is bounded by (d_{k}+f(d_{k})) instead of d_{k}. Find an effective ε-net for this larger space, where ε is so small that any two manifolds in this space that are 10ε-close are homotopy equivalent. (This ε can be found effectively as well.) Consider the graph G such that its vertices are points of the net and two vertices are connected by an edge if and only if the distance between the corresponding points is at most 5ϵ.

Now, if any two components of D^{−1}((0, d]) are connected up in D^{−1}((0, d + f(d)]), then one can try to use this to make an algorithm to understand when Σ_{k} is the standard sphere as follows. Look to see if there is a path in this graph connecting a vertex that is the closest to M#Σ_{k} to M. Of course, if there is, then Σ_{k} is standard. Suppose that we have the connectedness result, then whenever Σ_{k} is standard, M#Σ_{k} is diffeomorphic to M, and there would be a path from M#Σ_{k} to M in Al(M), which stays within the space of metrics of diameter ≤ d_{k} + f(d_{k}) and (1) either stays within the space of metrics of large volume, and thus would already be considered, or (2) would leave it, and go to a metric of very small volume. However, if there’s a path from M#Σ_{k} to a manifold of smaller volume than c_{n} then our a priori inequality tells us that Σ_{k} is the standard sphere – so we obtain an algorithm by seeing whether M#Σ_{k} can be connected to any metric of too small volume or to M.

This argument demonstrates the existence of more than one component of sublevel sets of diameter regarded as a functional on Al(M) for an infinite unbounded set of values of d. In order to see that sublevel sets of diameter are disconnected for all sufficiently large values of d one can either use an argument similar to the argument in [N3] that involves the notion of the Rado busy beaver function or to prove an exponential lower bound for the number of such components (see below).

Note now, that there must be some components with a positive lower bound on volume, because if there weren’t we could use the test of seeing whether there’s a path away from M#Σ_{k} which lowers the volume below c_{n}. Since there’s no such algorithm Al(M) must contain such volume bounded from below components, and therefore, by the Cheeger-Gromov theorem, there is a C^{1,α} metric at the bottom of that basin.

The exponential lower bound for the distribution function of local minima of D follows from an argument similar to the argument in §6 and involving the notion of the timebounded Kolmogorov complexity. Note that in order to use this line of reasoning one must ensure that the homology spheres constructed using the geometric witness construction have sufficiently low geometric complexity as a function of the length of the word in the seed group. (See Theorem 1 in [NW1] for the exact statement.) Surprisingly, this turned out to be not quite trivial due a certain amount of non-constructiveness in the proof of S.P. Novikov’s theorem, but the difficulty was essentially resolved in [N2].*

* Roughly speaking, one needed here a quantitative version of the well-known theo-

Remark: A similar approach can be used to prove the analogue of the main theorem of [NW1] when the sectional curvature is bounded from below instead of being bounded from both sides ([NW4]). The main new technical difficulty is the absence of a known to us way to construct by means of an algorithm the ε-nets in the spaces of Riemannian structures of curvature bounded from below. The local minima of diameter in this situation are known to be only the Alexandrov spaces of curvature ≥ −1 homeomorphic to M. Further, one can prove the analogue of the main results of [NW1] for the case when the Ricci curvature is bounded from both sides or from below ([NW4]). But in this case the limits of minimizing sequences can have singularities in codimension 2 (conjecturally, only in codimension 4) and while they are still n-dimensional they need not be homeomorphic to M.

10A. How to construct local minima of D on Al(M)?

The described proof of the existence of local minima of D on Al(M) is formally speaking non-constructive. However, it is not very difficult to turn it into an explicit (albeit very awkward) construction of representatives from non-trivial basins of D on Al(M) where the volume is uniformly bounded from below by a positive constant. (Recall that D attains its local minimum in such basins.) Here is an informal description of such a construction: One uses homology spheres produced using the geometric witness construction described in §8 and corresponding to certain trivial elements of the group with unsolvable word problem. (Recall that these homology spheres are Riemannian manifolds diffeomorphic to the standard sphere, but this fact is quite difficult to see from their geometry. At first glance they seem nonsimply-connected.) One should choose here trivial elements that correspond to the inputs ω of the Turing machine T used in the construction of the group with unsolvable word problem such that the halting time of T with ω is very large. In principle, one can construct a required homology sphere Σ^{n}(T, ω) explicitly. Then one takes a designer n-dimensional homology sphere Σ such that for any Riemannian metric on Σ with Ric ≥ −(n−1) the volume of Σ is ≥ 1. The construction of such homology spheres was partially explained in §9. One chooses any Riemannian metric with |K| ≤ 1 on Σ. Now one uses several copies of Σ^{n}(T, ω) in order to kill all generators of the fundamental group of Σ using a melding procedure described in [NW1]. As a result one gets a Riemannian manifold S^{n}(T, ω) which is diffeomorphic to the standard sphere but at first glance seems to be nonsimply-connected and even having non-zero simplicial volume. Now one can choose any Riemannian metric on M with |K| ≤ 1 and take a Riemannian conected sum with S^{n}(T, ω). Then one needs to rescale the resulting manifold (by a not very large factor) in order to ensure that |K| ≤ 1. If the halting time of T on ω is sufficiently large the resulting Riemannian manifold will be in a non-trivial basin of D where the volume is uniformaly bounded from below by a positive constant.

11. The lattice of C.E. Degrees

rem in homological algebra asserting that the universal extension of a perfect group is superperfect.

Our first extension of the results of [NW1] to a more “fractal” type assertion is a quite simple application of known results on Post’s problem, and more generally, on the semilattice of c.e. degrees combined with the argument sketched in the previous five sections.

Let A and B be sets of natural numbers. A is said to be Turing reducible to B, written A ≤ B, if there is an algorithm that computes the characteristic function of A from the characteristic function of B. (This is modelled by a 2 tape Turing machine, where one writes B on the second tape, so that all its elements are accessible in the course of a calculation of A.)

A and B have the same degree if A ≤ B and B ≤ A.

Note that A and the complement of A have the same degree, so being computably enumerable is not an invariant of the Turing degree. However, we will only be most concerned with the degrees of c.e. sets.

This is a semilattice: A ∧ B = {n|n/2 lies in A if n is even, or (n − 1)/2 lies in B if n is odd}. It is the least upper bound for A and B.

There is a highest c.e. degree. It is the degree of H = {2^{n}3^{m}|f_{n}(m)halts}. If S is any c.e. set, then it is recognized by some function f_{k}. Now to decide if m is in S, one just has to see whether f_{k}(m) = 0, so first one checks whether 2^{k}3^{m} is in H (asking the oracle), and if it is, then computing f_{k}(m) and seeing if it’s 0.

Obviously noncomputable c.e. degrees (like H) are different from 0 = degree(of any computable set). Post’s problem was whether there are any other c.e. degrees.

A landmark theorem of Friedberg and Muchnik provided the affirmative answer to Post’s problem, and lead to a great deal of work on the structure of this semilattice. We’ll just mention some results of Sacks.

Theorem 11.1. ([Sa], see also [So]). Between any two c.e. degrees there is another one. Any c.e. degree is l.u.b. of two incomparable c.e. degrees. Moreover, any countable p.o. set can be embedded into the c.e. degrees.

C.e. degrees have a lot to do with rates of growth of (total, i.e. everywhere defined) functions on the integers. Let f_{k} be a computable partial function that is defined exactly on S. (We denote the set of places where f_{r} halts as W_{r}; so S = W_{k}.) Then we can consider the function: T_{k}(n) = sup_{m≤n;m∈S} The number of steps it takes for f_{k} to accept m, where T_{k}(n) = 0 by definition if n is smaller than the least elements of S.

T_{k} is computably equivalent to S. For if one knows S, one knows how to compute T_{k}. Keep computing f_{k} until one sees all elements of S that should actually arise. Similarly, from T_{k} one can get S, by computing f_{k} and giving up when the calculation takes longer than T_{k} suggests.

Note that in this formulation, if there is any computable function g such that g(T_{k}) > T_{l} (here we mean pointwise larger!) then the set determined by f_{k} ≥ that determined by f_{l}. (Indeed g need not be computable, but can be “computable relative a lower degree than these sets”.) ^{6}

6 Moreover if W_{l} does not reduce to W_{k}, then there is no infinite computable set of integers on which the inequality g(T_{k}) > T_{l} can hold. This inequality cannot hold on an infinite strictly increasing sequence {n_{k}} majorizable by a computable or even a lower in

That H is the maximal element of the set of c.e. degrees is reflected in the fact that its halting function is essentially the busy beaver function, and grows more rapidly than the halting function of any other c.e. degree. However, the work cited above asserts that there are many “halting functions” i.e. T_{k}’s, which grow incomparably slow than the busy beaver, but much faster than any computable function.

Remark. It is desirable here not only to have T_{l} of a bigger c.e. degree majorize every computable function of the halting function of a smaller degree for infinitely many values but to majorize every computable function g of T_{k} for a smaller degree for all sufficiently large values of n exactly as the Rado busy beaver function eventually majorizes every computable function. Whenever this will not hold for any two c.e. degrees β and γ such that β < γ we learned from Bob Soare ([So 2]) that there exists an infinite sequence of c.e. sets β_{i} such that the halting function for β_{i+1} eventually majorizes every computable function of the halting function for β_{i}. A more refined analysis of our argument show that what is most relevant is not the general undecidability and irreducibility techniques but the stopping time of c.e. sets used in our construction. When we use sets β_{i} constructed by Soare as the seeds for our construction we discover, as we will see in the next section the following beautiful picture in Al(M): There are “pits” or “basins” in the graph in the graph of diameter with depth of the magnitude roughly equal to the “halting function” for β_{1} and spaced at intervals growing slightly faster that their depth. These are merely bumps in the basins of (the spaced much farther apart) much deeper basins that correspond to β_{2}. And even these huge basins are merely bumps in the basins corresponding to β_{3}. And so on.

The intuition of this picture is the source of the title of the paper.

12. First fractal properties of Met.

A natural refinement of the negative solution to the word problem, first given by A.A. Fridman, gives groups whose word problem is unsolvable in any given c.e. degree. There are a number of approaches in the literature. We will cite one of the earliest and the most recent: [Co] and [BRS]. [BRS] accomplishes a great deal more than merely encoding degrees. (Indeed, degrees are not even mentioned in this paper!) For more precise results than those we are proving here, and in particular, to make use of Soare’s sequence of sets, this added refinement is very convenient.

For later purpose we mention that these groups are accessible from the trivial group by a series of amalgamated free products and HNN extensions.

At this point, all one does is redo all the earlier arguments using a machine which melds the Clozel-Hausmann-Vogel homology sphere with one whose word problem has given c.e. degree. ^{∗}

the Turing hierarchy function of k.

∗ Note that although groups whose word problem has given c.e. degree are very convenient, they are not really necessary for our purposes. Instead we can start our geometric witness construction from an arbitrary Turing machine T and its arbitrary input ω as described in section 8A, and observe that the standard proof of the unsolvability of the word problem for f.p. groups (cf. [R]) yields a f.p. group G(T) and a word w(ω, T) ∈ G

The density of these critical points (and the values of D for them) is clearly as advertised by the proof of their existence. Their depth can be easily majorized and minorized in terms of the halting time of the Turing machines used in the construction of the group with the unsolvable word problem. Our remarks about growth of halting functions give the result about how fast the depths of such critical points must be growing.

Combining these statements gives the view described in §3. The busy beaver function describes the deepest basins, however, these basins have other local minima which are deep to a level measured by another c.e. degree. There are many of these, lots that are quite incomparable (in the technical sense!) in size (as we look at the sequences of these critical points arising for different d), and of each of these smaller basins, one finds yet smaller basins, that are also terrifically deep from the point of view of computable functions, but are tiny in comparison to the basins that they open up into.

13. Homology of Groups

Our attention now turns to the topology of basins but before we can understand what these look like we must study the properties of group homology for classes of finitely presented groups. The remarkable pair of papers [BDH] and [BDM] shed a great deal of light on the possible sequence of homology groups of a group. Among other results they prove that any recursively presented abelian group can be realized as H_{i}(G) for any i ≥ 3 for an appropriate finitely presented group G. For example, for any computably enumerable set K of positive integer numbers one can construct a finitely presented group G such that its i-th homology group is the abelian group generated by x_{1}, x_{2}, x_{3}, … with relations x_{j} = 0 for all j ∈ K. While their work is extremely valuable for us, unfortunately, given the unsettled nature of the Novikov conjecture and some of its analogues, one cannot use arbitrary groups, and we will have to be a bit careful in applying their work. (We will discuss the Novikov conjecture in the next section. For our purposes we need groups that are known to satisfy the Novikov conjecture.)

For general mathematical interest (and useless to us), we make the following:

Conjecture 13.1. A space X is of the form Bπ^{+} for some finitely presented group π iff (1) it has finite 2 skeleton and (2) it has a computable cell structure.

Here π is not assumed to be perfect and the +-construction can be performed with respect to any perfect subgroup of π. “Computable cell structure” means that one can make a Turing machine that lists all the cells of the space in some order. (But not necessarily all the 5 cells before you move on to 6 cells.) Recall that H_{∗}(Bπ) = H_{∗}(Bπ^{+}) so this conjecture, if true, extends results of [BDH] and [BDM] on homology of groups. Here is a partial result:

Theorem 13.2. If X is any simplicial complex with recursive cell structure, then Σ^{2}X = Bπ^{+} for a finitely presented group π that satisfies the Novikov conjecture.

such that 1) w = e if and only if T halts with ω; 2) If w = e then the minimal number of times one needs to apply relations of G to see that w = e differs from the halting time of T with ω by not more than a constant factor.

Theorem 13.2 implies that one can control things like Steenrod squares, which weren’t explicitly dealt with in the above papers.

The proof is a concatenation of the techniques of the two papers. In [BDH], the authors, presaging “hyperbolization” ideas, give n-simplices of acyclic groups, which all map into one another injectively. Then replace each simplex of the simplicial complex by the appropriate simplex of groups.

This gives a finitely presented group where Bπ^{+} is an arbitrary finite complex. We remark that the simplex of groups only involves finite Bπ complexes and that moreover these are accessible from the trivial group by amalgamated free product and HNN extension. Thus all of these groups satisfy the Novikov conjecture (even the Borel conjecture, away from 2) by [Ca].

It would be nice for some applications to know that the (higher and lower) Whitehead groups of these groups vanish. But unfortunately [Wld1] doesn’t directly apply, because of Nils.

To complete the proof of the theorem, we apply the fact that [BDM] produced a universal acyclic group A such that any recursively presented group embeds in. (Actually,

[BDM] doesn’t fuss over recursive presentation; the key point is that the celebrated Higman embedding theorem puts any recursively presented group within a finitely presented one.)

This is, for us, a fairly bad step, because the group A is pretty crummy: it’s a universal group and constructed from Higman’s universal group! Our group is A ∗_{(A∗_{π}A)} A.

Although we do not know the Borel conjecture for this group *, since A is acyclic, we certainly have the Novikov conjecture holding for this group, again by application of [Ca] (with the slight modifications or infinite generation commented on in [NW2]). Indeed, one even has a canonical splitting of the assembly map:

H_{n}(B(A ∗_{(A∗_{π}A)} A); L) ⟶ L_{n}(B(A ∗_{(A∗_{π}A)} A))
↓  ↓
H_{n−2}(Bπ; L)  ⟶  L_{n−2}(π)

where the bottom horizontal line and the left vertical lines are isomorphisms. (The right vertical arrow comes from two applications of Cappell’s splitting theorem.)

14. Higher ρ-invariants

The ρ-invariant was invented by Wall [Wal] for the classification of manifolds with the homotopy type of lens spaces: it is a natural extension of the method that Atiyah and Bott [AB] used for showing that lens spaces are never h-cobordant. (It is thus intimately connected to η-invariants as well.) It is defined for odd dimensional manifolds with finite fundamental group. Briefly, one multiplies M (with π_{1} ≅ G) by some number k to make it bound some W with fundamental group G, kM ≅ bW. Then one considers 1/k ∗ G-sign (W) modulo the regular representation.

* In fact the assembly map for A cannot be an isomorphism by unpublished work of Stanley Chang and the second author.

This is well defined, because the difference between any two such W ’s is a closed manifold, and since by the Atiyah-Singer G-signature theorem or simple bordism theory, the G-signature of a closed (free G-) manifold is a multiple of the regular representation.

Thus, the ρ-invariant is a “peripheral” invariant that is secondarily related to the signature. (Note, though, that while the signature or G-signature are homotopy invariant, the ρ-invariant is certainly not!) The question then arises, what are the invariants associated in the same way to Novikov’s higher signatures?

Let us first recall what the Novikov higher signatures are. Consider a manifold M^{m} with free abelian fundamental group ZZ^{n}. Its fundamental group is classified by a map φ : M → T^{n}. Now, whenever m − c is a multiple of 4, one can consider the submanifold φ^{−1}(T^{n−c}) of M. (Of course there are n!/(n−c)!c! possible choices here, parameterized by H^{c}(T^{n}).) While the submanifold is not well defined, it’s signature is, and these signatures are called Novikov’s higher signatures. (For a general group π, the higher signatures are parametrised by H^{∗}(Bπ)). Novikov’s conjecture is that these are homotopy invariants.

The problem with trying to directly mimic with ρ-invariant the above procedure for signatures, is that ρ-invariants are not bordism invariant so the value will depend on how one take the transverse inverse image of the submanifold. Another issue is this: if one considers two three dimensional lens spaces L and L′, which are homotopy equivalent but not diffeomorphic, their products S^{1} × L ≠ S^{1} × L′ with a circle remain distinct. However, after taking connect sums with a number of S^{2} × S^{2}’s, they become diffeomorphic. So, something must go wrong with defining such a secondary invariant in full generality.

In [We1] an approach to this was given for a class manifolds which are called “antisimple”. (Antisimple manifolds were first studied by J.Cl. Hausmann in an unpublished paper twenty years ago.) This condition is that they don’t have handles around the middle dimension. One can even work with a wider class of manifolds that satisfy a similar condition algebraically on their Q-cellular chain complex. Antisimplicity is thus a homotopy invariant property.

Everything we say has a suitable integral version. However, we will be content in writing our formulae only correctly in the case of ⊗Q. More precisely:

Theorem 14.1. ([We1]) Let M^{n}, n > 4, be a compact antisimple manifold with fundamental group Γ. Assume that the Novikov conjecture holds for Γ. Then, one can define an invariant Hρ(M) in L_{n+1}(Γ)/ ⊕_{i} H_{n+1−4i}(Γ) (which has a surjection to H_{n+4i+1}(Γ)). Moreover, a lattice in this group can be realized as Hρ(M′) − Hρ(M) as M′ ranges over manifolds tangentially (simple) homotopy equivalent to M.

We will give the applications of Hρ below. Its construction is explained in §14A.

14A. Construction of Hρ ([We 1]).

The main idea of the construction in [We1] is this: If M is antisimple, then its chain complex is algebraically nullcobordant (as a symmetric algebraic Poincare complex, in the sense of [Rn]). This is fairly trivial: it’s like saying that the signature of a manifold with no middle dimensional cohomology vanishes.

The next point, though, is to assume that the Novikov conjecture (see [Wa 1], [We 4], [FRR]) holds for π. Under this hypothesis, the vanishing of the symmetric signature implies that the higher signature vanishes as well. More precisely, Poincare dualizing, one has

φ_{∗}(L(M) ∩ [M]) ∈ H_{∗}(Bπ; L) ⟶ L^{∗}(π) .

Here L(M) is the Hirzebruch L-class. The push-forward homology class simulataneously captures all the higher signatures. The arrow is called the assembly map, and the symmetric signature is the image of the higher signature under assembly.

It is well-known that Novikov conjecture is equivalent to the rational injectivity of the assembly map, so for an antisimple manifold, all the higher signatures vanish, assuming the conjecture.

Vanishing of the higher signatures is not enough to guarantee that the manifold M geometrically bounds: in the simply connected case there’s more to bordism than just signature, but if one widens one scope to allow certain singularities [Si] (Witt spaces) one can make M a boundary of an object good enough to have L-classes, higher signatures, etc.

Now one can combine the algebraic and geometric coboundaries of M into one symmetric algebraic Poincare complex and consider its cobordism class. As the result one gets an invariant of antisimple n-manifolds that lives in L_{n+1}(π)/⊕H_{n+1−4i}(π; L). The bottom is, of course, the indeterminacy. It represents the possible higher signatures of closed n + 1 manifolds.

Remark. For π torsion free, conjecturally, the quotient is essentially ⊕H_{n+5+4i}(π; L). For π with torsion there are contributions from ⊕H_{n+1±2i}(C(g); L) as one runs over conjugacy classes of centralizers of elements of finite order in π.^{7}

In any case, Hρ(M) can be algorithmically recognized (when the Novikov conjecture is correct) in the sense that one can find by means of an algorithm the appropriate element of the L-group, etc. In other words one can produce a cycle representative for Hρ in the relevant group homology.

Surgery easily provides one with a realization theorem for Hρ among the manifolds simply (and tangentially) homotopy equivalent to the antisimple manifold M. One just uses the Wall realization theorem (see [Wa 1], [We 1]) to obtain a new manifold M′ normally cobordant to M where the normal cobordism between them is any preassigned element of the Wall group L_{n+1}(π_{1}(M)). The algebraic nullcobordism for M′ is the same as that for M, but the geometric nullcobordism is designed to be different.

Using this, one easily obtains by combining Hρ for an antisimple M constructed as the boundary of a finite complex in a high dimensional Euclidean space, with the fundamental group with “nonalgorithmic” homology, manifolds which cannot be recognized even among manifolds homotopy equivalent to them. “Non-algorithmic” means here that the triviality problem in the relevant for us homology group of the fundamental group is algorithmically unsolvable. (This homology group can be, for example, the infinitely generated abelian group with generators x_{i}, i = 1, 2, … and relations x_{i} = 0 for any i ∈ I where I is any recursively enumerable but non-recursive set.) See [NW2] for more details.

7 Regarding this, we’re making more than our usual Q inaccuracy. The formula we’ve written down is what would be correct for a complex analogue of what is a real situation. So actually, one has to look at involution invariant elements in this sum, where the involution sends g to g^{−1}.

The key point to make here is that this invariant is an absolute invariant, i.e. it’s an invariant of a single manifold, not of pairs. Consequently, it really detects whether manifolds are different from one another as opposed to whether some map is homotopic to a diffeomorphism.

15. BDiff

There is a simple and close connection between Riem/Diff and BDiff, which is the closest on manifolds which admit no symmetry (i.e. no smooth effective actions of any compact group), and is still quite close when there are only finite symmetries.* In the first case, life is simplest : As Riem is contractible, its quotient under the free action of Diff is, by definition, BDiff. For any G action on any X, one has a natural map from the Borel construction (X × EG)/G ⟶ X/G, the fiber over an individual point x is BG_{x}. In the case X = Riem(M), one thus always has a map BDiff(M) ⟶ Riem/Diff(M). If all the isotropy groups are finite (i.e. no metric on M has an infinite group of isometries), then all the BG_{x} are rationally acyclic and the map is an isomorphism in rational homology.

Differences in the rational homology between these spaces arise when there are positive dimensional Lie group actions on the manifold M. For instance if M admits no two dimensional actions, then H_{∗}(Riem/Diff, BDiff; Q) is then a sum over conjugacy classes of circle actions of the contributions that can be calculated using the Serre spectral sequence for a fibration. The relevant fibration has fiber BS^{1} = CP^{∞} and base that is the classifying space of the quotient of the normalizer of the S^{1} in the diffeomorphism group by S^{1}. (The latter are what the strata themselves look like.)

Unfortunately equivariant diffeomorphism groups have not received the attention they deserve and our knowledge of them is merely anecdotal. Therefore, we will not discuss the equivariant diffeomorphism contribution at all here. But Theorem 16.2 asserts that this stratification, when non-trivial, is almost always extremely rich. This means that there are infinitely many contributions to that relative homology, and these almost always come from the homology of Met rather than contribute to the homology of BDiff (although such assertions require calculations in general).

In this section we will discuss the topology of BDiff. We will only discuss π_{1} here. There is a similar story true, after a great deal more work, for the higher homotopy. (The algebraic K-theory relevant, though, is the algebraic K-theory of spaces cf. [Wld2].)

Of course, π_{1}(BDiff(M)) ≅ π_{0}(Diff(M)). This is the group of “obstructions to isotoping a diffeomorphism to the identity”. From this point of view, one tries to accomplish this in three steps:

(1) Is f homotopic to the identity? (2) Assuming f is homotopic to the identity, let

* Also, note that Riem(M)/Diff(M) and Al(M) are weakly homotopy equivalent. Indeed, the space of smooth Riemannian metrics on M satisfying |K| ≤ 1 is the deformation retract of Riem/Diff(M). And this space is weakly homotopy equivalent to its closure Al(M). The last statement follows from the possibility to push out small simplices in Al(M) into the space of smooth metrics on M satisfying |K| ≤ 1 using the de Rham smoothing operator ([Nik]).

H be a homotopy. Is H homotopic relf ∪ id to a homeomorphism, i.e. to a pseudoisotopy?

(3) If F : M × I ⟶ M × I is a pseudoisotopy, is it isotopic to an isotopy?

The first step is pure homotopy theory. The second step is surgery theoretic. And the final one is the subject of concordance space theory, which is the parameterized version of h-cobordism theory.

In the simply connected case there are general things one can say. Autohomotopy equivalences form an arithmetic group. Surgery can be described entirely in terms of characteristic classes. And pseudoisotopies are always isotopic to isotopies.

Note the obvious troubles in combining these machines. In (2) so much can depend on the choice of the homotopy – and in the general nonsimply connected case, this indeterminacy is uncontrolled. In (3), the pseudoisotopy isn’t quite well defined, either, but it is quite easy to quantify its indeterminacy. (It’s like doubling h-cobordisms to get self-h-cobordisms with nontrivial torsion.)

In the antisimple case, at least, one can circumvent, to some extent, the first of these issues. The homotopy is irrelevant if the obstruction to pseudoisotopy is detected by Hρ of the mapping tori. (Two diffeomorphisms can’t be pseudoisotopic if their mapping tori aren’t diffeomorphic: use their pseudoisotopy in a neighborhood of the glueing to produce the diffeomorphism between the mapping tori.)

The pseudoisotopy theory is also very interesting. For this π_{0} situation there are two obstructions, studied by Hatcher and Wagoner [HaW] (but see [Ig] for an important correction) One lies in W h_{2}(π_{1}) and the other lies in a relative group that is always at least as large as ZZ_{2} [nontrivial conjugacy classes on π_{1}] (although it actually depends on π_{2} as well).

In short, it is quite easy to guarantee, for antisimple situations anyway, large π_{0}(Diff) using Hρ and tons of 2-torsion based on the conjugacy classes in the fundamental group. One can’t make it too small, ever (because of the conjugacy class issue), but this is hard to quantify.

Problem 15.1. Is there a nontrivial torsion free finitely presented group all of whose nontrivial elements are conjugate?

And, pinning down the homotopy equivalences is pretty heard, too. But, just as a concrete corollary of the Hρ theory and surgery theory:

Corollary 15.2. If M^{n} is an antisimple manifold then there is a surjection of the kernel of the homomorphism π_{0}(Diff(M)) → Out(π) onto L_{n+2}(π)/ ⊕_{i} H_{n+2−i}(π, L_{i}(ZZ)). (Here π = π_{1}(M).)

One uses Hρ applied to the mapping torus. (In terms of applying this to our situation one needs antisimple homology spheres with such group homology. However, the original Kervaire construction of homology spheres with prescribed superperfect fundamental group produces antisimple ones (at least in dimensions greater than six). The condition here is only on the group homology, not on the image of the fundamental class under the homomorphism induced by the classifying map.) In particular, choosing π carefully, we can easily guarantee that the kernel of the homomorphism considered in Corollary 15.2 always contains an infinite rank vector space over any prime field^{8}.

16. A note on symmetries

The isotropy groups of Diff acting on Riem(M) are the compact groups that can act smoothly. Each Diff conjugacy class of action gives rise to a stratum in the quotient. (The set of Riemannian metrics actually preserved by a given action (pointwise) is an affine space.)

Having an S^{1} action is quite rare among manifolds.

Theorem 16.1. (See [BH]^{9}). If π_{1}(M) is centerless, and [M] ≠ 0 ∈ H_{n}(Bπ), then M does not admit an S^{1} action.

This is quite important for our approach. As a result of this, the basins produced in §§9-10 consist entirely of ordinary orbifold points, i.e. no positive dimension isotropy.

A second very useful fact is the following (see e.g. [Da 1]):

Theorem 16.2. If M admits a G action whose singular set has quotient which is more than two dimensional, then it admits infinitely many nonconjugate G actions, distinguished by their singular set. Indeed the fundamental group of a stratum of the singular set changes, although, its homology can be preserved.

For simplicity we’ll give the argument for G = ZZ_{2}. Let F = fixed set, and let Σ be a homology sphere of the same dimension of F, such that F bounds a contractible manifold K, with K × I a disk. (Above dimension three, all homology spheres have this property, aside from perhaps requiring a change of smooth structure near a point. A proof of the fact that all homology spheres bound a contractible manifold K can be found in [Ke]. Now the fact that K × I is homeomorphic to a disk easily follows from the Smale h-cobordism theorem.) By crossing with an appropriate disk, one can find a sphere of the dimension of M with an involution fixing Σ. Take the connect sum of M with that sphere, equivariantly, to produce a new involution on M with fixed set F #Σ.

There are infinitely many choices of Σ (and we can make these “designer homology spheres” if we ever have reason to).

17. Riem/Diff

It is clear now how to prove several versions of the second theorem in the introduction. The simplest way, given the build-up so far, is to take a group built as in §13 and build an antisimple homology sphere with that fundamental group.

One can make this group have whatever elements one want in π_{0}(Diff) (at least through some range depending on the dimension) as in the discussion in §15. Moreover, these

8 Although this involves some integrality statement that we have not made explicit in this paper, if you don’t choose characteristic 0.

9 Other versions are due to Gromov, Schoen-Yau, Schultz, the second author, and doubtlessly others. elements will be detected by cohomology classes (higher rho cocycles). Now modify the homology sphere, by performing witness constructions to it. (The witness construction will not affect Hρ if the chosen element of the group was non-trivial.) *

We remark that these modifications to the homology spheres are done near low skeleta, so general position allows these to be done in a parametrised fashion, if the number of parameters is not too large.

Finally connect sum to M.

Now one can juxtapose the non-existence of an algorithm solving the word problem for the seed group and the possibility to check whether or not the constructed cycle in Al can be easily filled (in the spirit of the proof described in §10). As the result one can conclude the existence of basins in Al(M) that will seemingly have tons of homology, until they die out on finally discovering that this connected sum manifold is really M.

Remark. As we pointed out earlier in our discussion of what points in a basin “look like” (see §10A), here, too, there is a simple description of the “virtual π_{1}” that arises: If (Σ, g) is a manifold with metric, and ϕ : Σ ⟶ Σ is a diffeomorphism, then tϕ^{∗}(g) + (1 − t)g, t ∈ [0, 1] describes a circle in Riem(Σ)/Diff(Σ). If ϕ is isotopic to an isometry, one can easily produce a nullhomotopy of this circle. As always, we can arrange for this step to be very hard and get our basins to have non-trivial fundamental group. As in §10A one can, in principle, construct a basin in Riem(M)Diff(M) with lots of homology explicitly.

Now, one can do more devious things, like arrange for the space X involved in building π to have some tricks up its sleave: like having H_{n} ≅ ZZ[ZZ]/S_{n} = 0, by which we mean that in dimension n the homology has generators parametrised by the integers, but we kill many of these generators, in each dimension according to a different c.e. set S_{n} (although the whole combination of these has to be an c.e. sequence of c.e. degrees).

One then produces cycles which will naturally fill at the rates given by the functions associated to the various S_{n}’s.

Clearly, there’s a lot more one can do.

As a final example, we point out that for S^{n} because one does have positive dimensional symmetry, there’s another (simpler?) source of noncomputable filling functions for 5-cycles.

Consider the S^{1} action on S^{n} with fixed set S^{n−2}. This action, of course extends to an SO(n + 1) action. But when we replace S^{n−2} by Σ^{n−2} (as in Theorem 16.2) it no longer extends to even a two dimensional group (if Σ^{n−2} is picked to carry a homology class). The link of each of these Σ^{n−2} strata in Met(S^{n}) contains CP^{∞}. These maps of CP^{∞} to Met(S^{n}) are homotopic, at least when restricted to a skeleton determined by the concordance stable range. Indeed, these actions of S^{1} extend to actions on D^{n+1}. Those actions can be verified to be differentiably conjugate after crossing with [0, 1]. Thus the maps CP^{∞} to BDiff(D^{n+2}) are homotopic, so the ones into BDiff(D^{n+1}) are, and the by restriction into BDiff(S^{n}) are.

For simplicity, just restrict to the 4-skeleton (= CP^{2}). If n > 18 we will be in the concordance stable range. The homotopy gives us a suspension over CP^{2} in Met(S^{n}) for

* Of course, the basins in Riem(M)/Diff(M) of interest for us will appear as the result of performing the witness construction on trivial words of the seed group (as usual). each pair of circle actions. (Glue cones over CP^{2} onto the homotopy cylinder at each end using symmetric metrics as vertices of the cones.) A Mayer-Vietoris argument shows that this is a non-trivial 5-cycle in Met(S^{n}) (rationally) whenever the circle actions are not conjugate i.e. correspond to different strata. (If we would take the 2-skeleta instead of 4-skeleta, then the resulting 3-cycle could be trivial.)

Now we can perform the following geometric witness construction: First one constructs a S^{1}-symmetric Riemannian metric on S^{n} with the fixed point set Σ^{n−2}, where Σ^{n−2} is a homology sphere that is standard if and only if a chosen word w in the seed group G is trivial. Then one produces the 5-cycle as described above starting from this metric and the standard metric on S^{n} using CP^{4} ⊂ CP^{∞} linked with the corresponding strata of S^{1}-symmetric metrics. This 5-cycle will be trivial if and only if w = e in G. Observe that if n is even then the existence of a computable upper bound for the rational homology filling function f_{5}(r) for Al(S^{n}) endowed with the path metric would imply the existence of an algorithm deciding if this cycle is trivial thereby solving the word problem for G and obtaining a contradiction. (The rational homology filling function f_{k}(r) for Al(M^{n}) endowed with the path metric is, by definition, the infimum of s such that rational k-cycles in the ball of radius r for the path metric on Al(M^{n}) centered at the base point which ultimately die, die within the ball of radius s from the base point. Of course, the metric on Al(M^{n}) is used here to define the metric balls in the definition of the filling function. So, these homology filling functions can be entirely different for the path metric and for the Gromov-Hausdorff metric on Al(M^{n}).) The assumption that n is even is made here in order to have a positive lower volume bound for every element of Al(S^{n}) and to avoid using a more complicated geometric witness construction involving homology spheres with non-zero simplicial volume. Thus, f_{5} for Al(S^{n}) with the path metric grows faster than any computable function (and, in fact as fast as the busy beaver function) at least for even n > 18.

This shows a feature that S^{n} does not share with certain other simply connected manifolds. The noncomputability of the rational homology filling function f_{k}(r) for Al(S^{n}) appears already for the path metric on Al(S^{n}). In other words, cycles that can be filled only by very large chains are close to the base point (i.e. the standard metric on S^{n}) in the path metric. On many other manifolds, as one increases r, to get the weird phenomena one has to go very far away in Al(M^{n}) with the path metric to find a cycle of diameter r which required all that extra room to fill in. This class of manifolds includes hyperbolic manifolds as well as some simply connected manifolds (e.g. products of Kummer surfaces) that do not admit a non-trivial S^{1}-action. In this case homology of Met(M^{n}) with rational coefficients coincide with homology of BDiff(M^{n}) and can be computed in the stable concordance range. As the result one can decide for an appropriate finite multiple of any cycle what is the linear combination of the generators of Met(M^{n}) rationally homologous to the cycle and to find a filling by a trial and error procedure. So, the 5-dimensional rational homology filling function for Al(M^{n}) endowed with the path metric for such manifolds M^{n} turns out to be computable in the stable concordance range (e.g. for dimensions ≥ 19), unlike this function for S^{n}. (But, of course, one can easily adapt the proof of Theorem 0.2 to show that f_{5}(r) grows faster than any computable function for any compact manifold M^{n} of dimension ≥ 19 if Al(M^{n}) is endowed with the Gromov-Hausdorff metric instead of the path metric.) The preceding discussion can be summarized by the following theorem:

Theorem 17.1. Let n be greater than 18.

(1) If n is even then the rational homology filling function for 5-cycles in Al(S^{n}) endowed with the path metric grows faster than any computable function.*

(2) For any compact n-dimensional simply connected manifold M^{n} not admitting a nontrivial S^{1}-action or for any compact manifold M^{n} that admits a negatively curved Riemannian metric this function for Al(M^{n}) is computable.

Similar theorems will be true for the filling functions f_{4i+1}(r) for any i ≥ 1 providing that n ≥ 12i + 7.

18. What are the functionals on Met(M) for which our technique works?

It is very important to realize that the fractal behaviour described above is by no means specific to the diameter functional D on Al(M), or, equivalently, sup |K| diam^{2} on Met(M).

First, note that the proofs given in [NW1] and here immediately imply almost all results of [NW1] and the present paper for any non-negative lower semicontinuous Riemannian functional r on Al(M) that can be approximately evaluated with any accuracy for any given element and such that the diameter can be majorized by a computable function of r. The only statement that needs to be modified is the statement about the growth of the number of local minima, but the adjustment is easy (cf. Theorem 1.5 of [N2]). For example, these results will be true for D + 7 exp(volume) or for the sum of D and total scalar curvature. (Total scalar curvature is a continuous functional on the space of metrics with sectional curvature bounded below according to the unpublished result of Perelman.) (Compare with the similar discussion at the end of [N0].) In fact, one can demand even that D can be majorized by a computable function of r and a positive lower bound on the volume. So, all results of [NW1] and the present paper will be true, say, for the product of diameter and volume regarded as a functional on Al(M).

Secondly, the results of [NW1] as well as Theorem 0.1 of the present paper were generalized in [NW4] for the case when diameter is regarded as a functional on the closure in Met(M) of the space of Riemannian metrics on M with K ≥ −1 (instead of |K| ≤ 1). The only change is the smoothness class of the local minima: We know only that they are Alexandrov spaces of curvature −1 homeomorphic to M. (See [BGP], [P] for the definition and properties of Alexandrov spaces of curvature bounded below.) Further, one can generalize these results for D regarded as a functional on the closure of the space of Riemannian metrics on M satsfying Ricci ≥ −(n − 1) (or |Ricci| ≤ n − 1) in the space of isometry classes of all n-dimensional metric spaces. The local minima in this case can develop singularities and be non-homeomorphic to M (although they are still n-dimensional). Let us emphasize however that the described fractal picture of basins (or connected or “jump” components of sublevel sets of diameter) will be completely the same

* It seems that this result holds also for odd dimensional spheres, but we had not checked the details. as in the present paper. Also, the generalizations described in the preceding remark will be similarly true.

Third, we proved in [N3] that sublevel sets of the volume regarded as a functional on the subset of Met(M) formed by metrics of injectivity radius ≥ 1 have infinitely many nontrivial connected or “jump” components and hence basins with depths that are not bounded by any computable function. Using results on [N2] it is easy to prove the exponential lower bound for the number of connected or “jump” components of sublevel sets of vol/inj^{n} on Met(M) as well as the results of the present paper about depth and density of basins. However, in order to get a meaningful result about local minima one must first study the Gromov-Hausdorff limits of manifolds with injectivity radii uniformly bounded from below (by a positive number) and volumes uniformly bounded from above. To the best of our knowledge this interesting question remains largely unexplored. Note, that the results of [N3] can also be immediately generalized for functionals r such that vol/inj^{n} can be majorized by a computable function of r. One example of such a functional is vol/conv^{n}, where conv is the convexity radius.

We conjecture that a fractal picture similar to that described in the present paper will be valid for all positive functionals ϕ on the spaces Met(M) of isometry classes of Riemannian metrics on closed n-dimensional manifolds, (n ≥ 4), or on subspaces of Met(M) “made” of volume, diameter, various norms of sectional, Ricci or scalar curvature, injectivity radius, convexity radius, etc. providing that ϕ constraints the fundamental group of manifolds or at least some invariants measuring interactions of the fundamental group with homology (e.g. simplicial volume) and that ϕ is computable within to any prescribed accuracy. (The second condition is practically vacuous from the differential-geometric point of view since all interesting for Riemannian geometry functionals made of various norms of various curvatures, volume, diameter, injectivity radius, convexity radius, etc. satisfy this requirement.)

In particular, we conjecture that for all sufficiently large x the sublevel sets ϕ^{−1}((0, x]) ∈ Met(M) will be disconnected. Moreover, the number of path components of ϕ^{−1}((0, x]) will be bounded from below by an unbounded increasing functions. Further, we conjecture that this assertion will remain true if we allow “jumps” (instead of continuous paths) not exceeding a certain ϵ_{ϕ}(x, M) > 0 or a controllable (=computable) increase of ϕ along paths in the definition of paths components of ϕ^{−1}((0, x]). A stronger version of this conjecture is the statement that many of these basins will contain local minima of ϕ, which can be singular but still must be n-dimensional metric spaces providing that ϕ is (lower semi-) continuous on the considered subset of the space of Riemannian structures. (The exact type of the singularity will depend on ϕ.) The most far-reaching conjecture in this direction might involve volume regarded as a functional on the space of isometry classes of Riemannian metrics on M with constant scalar curvature −1. (It is well-known that this space is not empty for any M of dimension ≥ 3.) According to a conjecture of Gromov ([Gr 3]) the volume can be minorized by a constant multiple of the simplicial volume of M on this space. If the Gromov conjecture is true, then for any x manifolds of sufficiently large simplicial volume do not admit metrics of volume ≤ x and the conditions of the weaker version of our conjecture are satisfied. But we can make the stronger conjecture that the volume regarded as a functional on the considered space has infinitely many deep local minima if one allows the limit of a minimizing sequence to have (topological) singularities and that the graph of volume has the same fractal properties as the functionals considered in this paper. In particular, we conjecture the existence of singular Einstein metrics of scalar curvature −1 on all closed manifolds of dimension ≥ 4. The well-known non-existence of Einstein metrics on many closed four-dimensional manifolds ([Be], [Lb2]) and the uniqueness of Einstein metrics on some others ([BCG], [Lb 1]) show that topological singularities are unavoidable here. But we optimistically conjecture that the singularities that must occur are not worse than singularities of limits for sequences of metrics with Ricci curvature and volume bounded below studied by Cheeger and Colding. Following on a conjecture of Cheeger and Colding, we hope that topological singularities will be of codimension four or more. (Note that if one allows isolated singularitues of the limit spaces then all known obstructions to the existence of one or even infinitely many Einstein metrics on four-dimensional manifolds seem to disappear.)

19. Final remarks

There are several final comments or further directions worth exploring:

1. The first is that while in this paper we have mainly been explaining our results using the Turing hierarchy we have seen the benefit of careful examination of stopping time of Turing machines which opens the possibility of much more delicate hierarchies being applicable to this type of geometry. Here is what we think is true in this direction:

Conjecture 19.1. Let M be a closed manifold of dimension ≥ 4. For any Riemannian metric μ on M with |K| ≤ 1 denote the diameter of μ by x and denote by S_{F} (z) the set of integer numbers of Kolmogorov complexity ≤ [z] (with respect to any fixed optimal family F). For any N ∈ S_{F} (const(M)(x^{n} + 1)) there exist more than exp(c(n)x^{n}) local minima of diameter on Al(M) of depth between N/c_{1}(M) and exp exp(c_{2}(M)(N + x)) that are exp exp(c_{2}(M)(N + x))-close to μ in the path metric. (All constants here are positive.)

(It is even possible that one can replace the double exponent by the single exponent here.) We plan to make this conjecture the subject of a forthcoming paper. It may seem strange on the first glance that exponentially many depths of local minima of diameter are comparatively close to very large numbers of comparatively small Kolmogorov complexity, but it is easy to see ALL depths of local minima are close to integers with comparatively small Kolmogorov complexity! This follows from the fact that one can find near every element of Al(M) a Riemannian manifold that can be coded by a comparatively short bit sequence (see the last section of [NW1]). But then one can find the approximate depth of the minimum by means of an almost obvious search algorithm. This conjecture is motivated by the fact that integer numbers of not very high Kolmogorov complexity can be realized as halting times of Turing machines with not very high number of states. (Of course, this statement can be made very precise.) Then these machines can be used in our geometric witness construction described in §8 that eventually leads to the construction of local minima.

2. The second comment regards low dimensional manifolds. If one believes in geometrization then presumably Riem/Diff for 3-manifolds looks very simple. The key question is whether there’s room for interesting phenomena at the level of quick algorithmic solvability (as in the previous remark.) It seems likely that deciding whether two 3-manifolds are diffeomorphic can be done quickly (see [Wld2], [Th]).

For knots in S^{3} there is the very nice paper of [HLP] that gives an upper bound on how many Reidemeister moves are necessary to unknot a knot.

In dimension four, the fundamental unresolved issue is whether S^{4} is recognizable. It seems unlikely, but if it were, it would imply, for instance, that one can solve the word problem for perfect groups with equal numbers of generators and relations!

Irrespective, for many 4-manifolds one has the whole panoply of critical points and basins, etc. produced here. We will refrain from discussing any connections to Physics here.

3. A third point for future development is this: we constructed a great many cycles that only persist to particular ranges. One can use other coarse measures of the shape of a space. (See e.g. [BW].) For getting information about these, it might be interesting to vary the amount of geometry of the seed X in §13, rather than just fixate on its homology type as we’ve been doing.

4. Fourthly, the cycles that we’ve constructed seem to come in many flavors, and come associated to many different discrete groups, etc. This suggests an anti-fractal side of the story: the many basins that arise include infinitely many different sorts; each of these repeats, but nothing like “self-similarity” could be descriptive.

5. There is an obvious homomorphism of π_{0}(Diff(M)) to the group of outer automorphisms of π_{1}(M). Let H be an arbitrary finitely presented group and G will be a group with the unsolvable word problem used in the present paper. One can hope to get the group with the automorphism group including Out(H) by performing an appropriate version of the witness construction on G ∗ H for non-trivial words w ∈ G. Further, one can hope to get homology spheres with the diffeomorphism group containing (a part of) Out(H) as the result of an appropriate geometric witness construction. In the case of success one will be able to construct virtual cycles in Met(M) corresponding to elements of Out(H) for various finitely presented groups H.

6. We noted in §4B that the techniques of the present paper are applicable to many Riemannian functionals as well as to functionals on other geometric moduli spaces. Yet we do not know how to extend out techniques to many situations where it should be applicable. The most immediate problem is to prove an analog of the results of [NW1], [NW4] and main theorems in the present paper for volume instead of diameter. We believe that such a generalization is possible (and perhaps is not so difficult) but there are some serious difficulties caused by the fact that sublevel sets of volume on Al(M) are not precompact.

7. We do not know almost anything about local properties of sublevel sets of Riemannian functionals. For example, are sublevel sets of the functional sup |K|diam^{2} on Met(M) locally connected (or locally path connected)? We do not see any reason to suspect a negative answer but we also do not see any means that could help to establish the local connectedness properties.

8. We know very little about the global geometry of connected components of sublevel sets of Riemannian functionals on Met(M) considered in this paper, in particular about their diameters in the path metric (or the “jump” metric) or their entropies. The fundamental question that should be investigated is the question about the “size” of the set of metrics in Al(M) of injectivity radius ≥ 1 and volume ≤ V as a function of V. Let us measure the “size” as the number of points in a minimal net in this set with the following property: Every other element from this set is bi-Lipschitz homeomorphic to one of the points of the net with the Lipschitz constant not exceeding 1000 (or any other constant of the readers choice). Does the number of elements of the net grow exponentially (i.e. ≤ exp(c(n)V)) or superexponentially? This question posed by Gromov is very closely related with the following question well-known to physicists working in Quantum Gravity: Let M is any closed manifold. Is it true that the number s_{M}(N) of simplicial isomorphism types of triangulations of M with not more than N simplices has an exponential upper bound? (It is very easy to prove an upper bound of the form N^{cN}.) Physicists beleive that the answer is positive. Even if the answer is negative, one can ask if the number of simplicial isomorphism of triangulations of M with ≤ N simplices such that number of simplices meeting at every vertex is bounded by a constant grows with N not faster than exponentially. A (slightly more probable) positive answer for this question can also have the implications for an important problem discussed below.

It is well-known that in dimension 2 the number s_{M}(N) of simplicial isomorphism classes of triangulations grows exponentially with N. In dimensions greater than four and for many four-dimensional manifolds M (and possibly for all of them) this function is non-computable ([NBA]) despite the fact that it does not exceed N^{cN} for an appropriate c!

9. Is the space of isometry classes of Riemannian metrics on M of bounded geometric complexity truly fractal? A more precise version of this question posed by Gromov is the following. For any x consider the space of metrics M(x) ⊂ Al(M) of the injectivity radius greater than one and volume ≤ x. (Alternatively one can impose other restrictions on the geometry, say diameter ≤ x and volume greater than one or replace Al(M) by the space of metrics of bounded Ricci curvature...). Is it possible to find a function ϕ(x) and an increasing unbounded sequence x_{i} of real numbers such that spaces M(x_{i}) endowed with the Gromov-Hausdorff topology and rescaled by the factor ϕ(x_{i}) converge to a metric space? (One might need something more complicated than mere rescalings.) If “yes” then obvious questions about uniqueness and properties of the corresponding space(s) arise. This question is closely related to questions about the distribution of “sizes” of connected components of sublevel sets of Riemannian functionals. For instance, are the “components” of great logical complexity negligible from some suitable probabilistic view? Acknowledment: We would like to thank Bob Soare for his attention to our work, for numerous useful discussions and, especially for answering an important question for us ([So 2]). A part of this work was done while one of the authors (A.N.) was visiting the Max-Planck-Institut für Mathematik at Bonn in 1999 and the other author (S.W.) was visiting Tel-Aviv University. The authors would like to thank the Max-Planck-Institut für Mathematik and Tel-Aviv University for their kind hospitality.

References.

[A] M.T. Anderson, “Short geodesics and gravitational instantons”, Journal of Differential Geom. 31(1990), 265-275.

[AB] M. Atyah, R. Bott, “A Lefshetz fixed point formula for elliptic complexes: II aplications”, Ann. Math. 88(1968), 451-491.

[Ba] S. Bando, “Real Analyticity of solutions of Hamilton’s equation”, Math. Z., 195(1987), 93-97.

[B] J.M. Barzdin, “Complexity of programs to determine whether natural numbers not greater than n belong to a recursively enumerable set”, Soviet Math. Dokl. 9(1968), 1251-1254.

[BDH] G. Baumslag, E. Dyer, and Heller, “The topology of discrete groups”, J. Pure Appl. Algebra, 16(1980), 1-47.

[BDM] G. Baumslag, E. Dyer, and C. Miller,“On the integral homology of finitely presented groups”, Topology 23(1983), 27-46.

[BMR] J. Bemelmans, M. Min-Oo, E. Ruh, “Smoothing Riemannian metrics”, Math. Z., 188(1984), 69-74.

[BP] R. Benedetti, C. Petronio, “Lectures on hyperbolic geometry”, Springer, 1992.

[BN] V.N. Berestovskij, I.G. Nikolaev, “Multidimensional generalized Riemannian spaces”, in “Geometry IV”, ed. Yu. G. Reshetnyak, Encyclopaedia of Mathematical Sciences, vol. 70, Springer, 1993.

[Be] A. Besse, “Einstein manifolds”, Springer, 1987.

[BCG] G. Besson, G. Courtois, S. Gallot, “Enthropies et rigidités des espaces locallement symétriques de courbure strictement négative ”, Geom. Funct. Anal., 5(1995), 731-799.

[BRS] J. Birget, E. Rips, and M. Sapir, to appear.

[BW] J. Block, S. Weinberger, “Large scale homology theories and geometry”, in “Geometric topology, Athens, 1997”, 522-569, Amer. Math.Soc., Providence, R.I., 1997.

[BHP] W. Boone, W. Haken, V . Poenaru, “On recursively unsolvable problems in topology and their classification”, in “Contributions to mathematical logic” (H. Arnold Schmidt, K. Schutte, H.-J. Thiele, eds.), Noth-Holland, 1968.

[BorWal] A. Borel, N. Wallach, “Continuous cohomology, discrete subgroups and representations of reductive groups”, Ann. of Math. Studies 94, Princeton Univ. Press, 1980.

[Bo] J.P. Bourguignon, “Une stratification de l’espace des structures Riemanniennes”, Comp. Math., 30(1975), 1-41.

[BH] W. Browder, W.-C. Hsiang, “G-actions and the fundamental group”, Invent. Math., 65(1981/82), 411-424.

[BGP] Yu. Burago, M. Gromov, G. Perelman, “A.D. Alexandrov spaces with curvature bounded from below”, Russ. Math. Surv. 47(1992), 1-58.

[Ca] S. Cappell, “On the homotopy invariance of higher signatures”, Invent. Math. 33(1976), 171-179.

[CS] S. Cappell, J. Shaneson, “The codimension two placement problem and the homology equivalent manifolds”, Ann. Math. 99(1974), 277-348.

[Cha] I. Chavel, “Riemannian geometry: a modern introduction”, Cambridge University Press, 1995.

[Ch1] J. Cheeger, “Finiteness theorems for Riemannian manifolds”, Amer. J. Math. 92(1970), 61-74. [Ch 2] J. Cheeger, “Critical points of distance function and their applications”, in “Geometric topology: recent developments”, 1-38, Lecture Notes in Mathematics, 1504, Springer, 1991.

[CC1] J. Cheeger, T. Colding, “Lower bound on Ricci curvature and the almost rigidity of warped products”, Ann. Math. 144(1996), 189-237.

[CC2] J. Cheeger, T. Colding, “On the structure of spaces with Ricci curvature bounded from below I”, J. Differential Geom., 46(1997),3, 406-480.

[Cl1] L. Clozel, “Représentations galoisiennes associées aux représentations automorphes autoduales de GL(n)”, Publications IHES, 73(1991), 97-145.

[Cl2] L. Clozel,“On the cohomology of Kottwitz’s arithmetic varieties”, Duke Math. J., 72(1993),757-795.

[C] T. Colding, “Ricci curvature and volume convergence”, Ann. of Math. 145 (1997), 477-501.

[Co] D. Collins, “Truth-table degrees and the Boone group”, Ann. of Math. 94(1971), 392-396.

[D] R.D. Daley “Minimal-program complexity of sequences with restricted resources”, Inf. and Control 23(1973), 301-312.

[Da] M. Davis, “Groups generated by reflections and aspherical manifolds not covered by Euclidean space”, Ann of Math.,117(1983), 293-324. [Da 1] M. Davis, “Multiaxial actions on manifolds”, Springer Lecture Notes in Mathematics 643, Springer, Berlin, 1978.

[DSW] M. Davis, R. Sigal, and E. Weyuker, “Computability, Complexity, and Languages”, Academic Press, 1994.

[Dg] Yu Ding, “On a theorem of Cheeger and Colding”, preprint, 1999.

[F] S. Ferry, “Topological finiteness theorems in Gromov-Hausdorff space”, Duke Math. J., 74(1994), 95-106.

[FRR] “Novikov conjecture, index theorems and rigidity”, vol. 1-2, S. Ferry, A. Ranicky, J. Rosenberg eds., Cambridge University Press.

[Fu] K. Fukaya, “Hausdorff convergence of Riemannian manifolds and its applications”, in “Recent Topics in Differential and Analytic Geometry”, ed. T. Ochiai, Adv. Stud. Pure Math. 18-I, Academic Press, Boston, 1990.

[GW] R. Greene, H. Wu, “Lipschitz convergence of Riemannian manifolds”, Pac. J. Math., 131(1988), 119-141. [Gr 0] M. Gromov, “Hyperbolic manifolds, groups and actions”, in “Riemannian surfaces and related topics”, Ann. of Math. Studies 97(1981), 183-215. [Gr 1] M. Gromov, “Volume and bounded cohomology”, Publications Math. de l’IHÉS 56 (1982), 5-99. [Gr 2] M. Gromov, “Filling of Riemannian manifolds”, J. Differential Geom., 18(1983),1-148. [Gr 3] M. Gromov “Large Riemannian manifolds”,in “Curvature and topology of Riemannian manifolds”, 108-121, Springer LNM 1201, Springer, 1986. [Gr 4] M. Gromov, “Metric structures for Riemannian and Non-riemannian Spaces”, Birkhauser Verlag, Basel, 1998.

[GL] M. Gromov, H.B. Lawson, “Positive scalar curvature and the Dirac operator on complete Riemannian manifolds”, Publications IHES, 58(1983), 295-408.

[GP] K. Grove, P. Petersen V, “Bounding homotopy type by geometry”, Ann. Math. 128(1988), 195-206.

[Ha] R.S. Hamilton, “Three-manifolds with positive Ricci curvature”, J. Differential Geom. 17(1982), 255-306.

[HLP] J. Hass, J. Lagarias, N. Pippenger, “The computational complexity of knot and link problems”, JACM 46(1999), 185-211.

[HaW] A. Hatcher and J. Wagoner, “Pseudo-isotopies of compact manifolds”, Asterisque, 6, 1973.

[Haus] J.-P. Hausmann, “Manifolds with a given homology and fundamental group”, Commun. Math. Helv. 53(1978), 113-134.

[HWe] J.-P. Hausmann, S. Weinberger, “ Caractéristiques d’Euler et groupes fondamentaux des variétes de dimension 4”, Comment. Math. Helv., 60(1985), 139-144.

[Ig] K. Igusa, “What happens to Hatcher and Wagoner’s formulas for π_{0}(C(M)) when the first Postnikov invariant of M is non-trivial?”, in “Algebraic K-theory, number theory, geometry and analysis”, 104-172, Springer LNM 1046, Springer 1984. [Ig 1] K. Igusa, “The stability theorem for smooth pseudoisotopies”, K-theory, 2(1988), 1-355.

[JK] J. Jost, H. Karcher, “Geometrische Methoden zur Gewinnung von A-Priori-Schranken für harmonische Abbildungen”, Manuscripta Math., 40(1982), 27-78.

[Ke] M. Kervaire, “Smooth homology spheres and their fundamental groups”, Trans. Amer. Math. Soc. 144(1969), 67-72.

[KM] M. Kervaire, J. Milnor, “Groups of homotopy spheres I”, Ann. Math., 77(1963), 504-537.

[Lb1] C. LeBrun, “Einstein metrics and Mostow rigidity””, Math. Res. Lett., 2(1995), 1-8.

[Lb2] C. LeBrun, “Four-manifolds without Einstein metrics”, Math.Res. Lett., 3(1996), 133-147.

[LV] M. Li, P.M.B. Vitanyi, “Kolmogorov complexity and its applications”, in “Handbook of theoretical computer science”, ed. by Jan van Leeuwen, Elsevier, 1990, 187-254.

[Ma] Yu.I. Manin, “A course in Mathematical Logic”, Springer, 1977.

[Mi] C. Miller, “Decision problems for groups-survey and reflections”, in “Combinatorial group theory” (G. Baumslag, C. Miller, eds.), Springer 1989, 1-59.

[N0] A. Nabutovsky, “Non-recursive functions, knots “with thick ropes” and self-clenching “thick” hyperspheres”, Comm. in Pure and Applied Math., 48(1995), 381-428.

[N1] A. Nabutovsky, “Einstein structures: existence versus uniqueness”, Geom. Funct. Anal. 5(1995), 76-91.

[N2] A. Nabutovsky, “Geometry of the space of triangulations of a compact manifold”, Commun.Math.Phys., 181(1996), 303-330.

[N3] A. Nabutovsky, “Disconnectedness of sublevel sets of some Riemannian functionals”, Geom.Funct.Anal. 6(1996), 703-725.

[N4] A. Nabutovsky, “Fundamental group and contractible closed geodesics”, Comm. on Pure and Appl. Math. 49(12)(1996), 1257-1270.

[NBA] A. Nabutovsky, R. Ben-Av, “Non-computability arising in dynamical triangulation model of four-dimensional Quantum Gravity”, Comm. Math. Phys. 157(1993), 93-98. [NW 1] A. Nabutovsky, S. Weinberger, “Variational problems for Riemannian functionals and arithmetic groups”, to appear in Publications Math. de l’IHÉS.

[NW 2] A. Nabutovsky, S. Weinberger, “Algorithmic aspects of homeomorphism problems”, in “Rothenberg Festschrift”, Contemp. Math., 231(1999), 245-250. [NW 3] A. Nabutovsky, S. Weinberger, “Algorithmic unsolvability of the triviality problem for multidimensional knots”, Comment. Math. Helv., 71(1996), 426-434. [NW 4] A. Nabutovsky, S. Weinberger, “Variational problems for functionals on spaces of Riemannian metrics of curvature bounded below”, preprint.

[Nik] I. Nikolaev, “Bounded curvature closure of the set of compact Riemannian manifolds”, Bull.Amer.Math.Soc., 24(1991), 171-177.

[P] G. Perelman, “Spaces with curvature bounded below”, in Proc. ICM-94, S. Chatterji, ed., Birkhauser-Verlag, Basel, 1995, pp. 517-525.

[Pet] S. Peters, “Convergence of riemannian manifolds”, Compos. Math., 62(1987), 3-16. [Pe 1] P. Petersen V, “Gromov-Hausdorff convergence of metric spaces”, in “Differential Geometry: Riemannian Geometry” , ed. by R. Greene, S.T. Yau, Proceedings of AMS Symposia in Pure Mathematics, 54:3(1993), 489-504. [Pe 2] P. Petersen V, “Riemannian Geometry”, Springer, 1997.

[Q] F. Quinn, “A geometric formulation of surgery”, PH. D. Thesis, Princeton University, 1969.

[Rn] A. Ranicki, “Algebraic L-theory and topological manifolds”, London Math. Society, 1993.

[R] J.J. Rotman, An introduction to the theory of groups”, Springer, 1995.

[Sa] G.E. Sacks, “Degrees of unsolvability”, Princeton University Press, Princeton, 1963.

[Sch] R. Schulz, “Isotopy classes of periodic diffeomorphisms on spheres”, in “Algebraic Topology, Waterloo 1978”, 334-354, Springer Lecture Notes in Mathematics 741, Springer, Berlin 1978.

[Si] P. Siegel, “Witt spaces: a cycle theory for KO-homology at odd primes”, Amer. J. Math., 1983, 1067-1105.

[So] R. Soare, “Recursively-enumerable sets and degrees. A study of computable functions and computably generated sets”, Springer, 1987. [So 2] R. Soare, private communication.

[TW] L. Taylor and B. Williams, “Surgery spaces: formulas and structures”, 170-195, in “Algebraic Topology, Waterloo, 1978”, Springer LNM 741, 1979.

[Th] A. Thompson, “Thin position and the recognition problem for S^{3}”, Math. Res. Lett. 1(1994), 613-630.

[V] P. Vogel, “Un theoreme d’Hurewicz homologique”, Commun. Math. Helv. 52(1977), 393-413.

[Wld1] F. Waldhausen, “Algebraic K-theory of amalgamated free products”, Ann. of Math. 108(1978), 135-256.

[Wld2] F. Waldhausen, “Algebraic K-theory of spaces”, Proc. Symp. Pure Math. 17(1978), 35-65.

[Wld3] F. Waldhausen, “On irreducible 3-manifolds which are sufficiently large”, Ann. of Math., 87(1968), 56-88.

[Wal] C.T.C Wall, “Surgery on compact manifolds”, Academic Press, 1971. [We 0] S. Weinberger, “The topological classification of stratified spaces”, University of Chicago Press, 1994.

[We 1] S. Weinberger, “Higher ρ-invariant”, in “Rothenberg Festschrift”, Contemp. Math., 231(1999), 315-320. [We 2] S. Weinberger, “Class numbers, the Novikov conjecture, and transformation groups”, Topology, 27(1988), 353-365. [We 3] S. Weinberger, “Dehn functions and contractible closed geodesics”, preprint. [We 4] S. Weinberger, “Aspects of the Novikov conjecture”, Contemp. Math. 105(1990), 281-297.

[ZL] A.K. Zvonkin, L.A. Levin, “The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms”, Russ.Math.Surv. 25(6)(1970), 83-129.

[Y] S.T. Yau, “Open problems in geometry”, in “Differential Geometry: Riemannian Geometry”, ed. by R. Greene and S.T. Yau, Proceedings of AMS Symposia in Pure Mathematics, 54:1(1993), 1-28.

A.N.: Department of Mathematics, University of Toronto, Toronto, Ontario, M5S 3G3, Canada; e-mail address: alex@math.toronto.edu S.W.: Department of Mathematics, University of Chicago, Chicago, Illinois, 60637-1538, USA; e-mail address: shmuel@math.uchicago.edu