[FOM] Soare's article in the BSL
Stephen G Simpson
simpson at math.psu.edu
Tue Jan 25 10:43:34 EST 2005
Martin Davis writes:
> In the December issue of the Bulletin of the ASL, Bob Soare's
> article "Computability Theory and Differential Geometry" discusses
> some of the work of the topologists Nabutovsky and Weinberger to
> which he contributed. Has anyone on FOM studied the article? I'd
> love to post comments on it.
Below I append my comments on this topic, written July 11, 2000. The
main references are to Soare's FOM posting of July 11, 2000, available
An additional reference is to my FOM posting of August 4, 1999 on the
so-called Simpson's Thesis, available on-line at
A key technical reference in Soare's BSL article is Barbara Csima's
2003 Ph.D. thesis, "Applications of Computability Theory to Prime
Models and Differential Geometry," written under Soare's supervision.
Unfortunately, Csima's thesis is not available on Soare's web page or
Csima's web page, but it can be downloaded from the national
Ph.D. thesis archive at http://www.umi.com/.
From: Stephen G Simpson <simpson at math.psu.edu>
Date: Tue, 11 Jul 2000 18:01:13 -0400 (EDT)
I applaud Robert Soare's informative message (posted 11 July 2000 by
Martin Davis) concerning recursion-theoretic results and methods, as
related to the geometrical work of Nabutovsky and Weinberger.
I have some technical/methodological questions concerning the various
recursion-theoretic results that Soare mentioned. These particular
questions are motivated by the so-called "Simpson's Thesis".
Soare questions the interest of "Simpson's Thesis". But I still think
that my original statement and justification of "Simpson's Thesis"
(see e.g. my FOM posting of 4 Aug 1999) remains vital.
In any case, I see no reason why we cannot discuss these issues
piecemeal, apart of any general thesis. They are really fairly
standard methodological issues in recursion theory.
First, I thank Soare for precisely stating Theorems 1 and 2.
Unfortunately, I don't know the precise statement of Theorem 2', but I
can guess at it.
As Soare pointed out, Theorem 1 follows easily from the existence of
an infinite descending sequence of r.e. Turing degrees. And the
latter statement is standardly proved by a finite-injury priority
argument, of the type used by Friedberg and Muchnik in their solution
of Post's problem. And many experts (e.g., Sacks) have said that this
kind of result "requires a priority argument". (But one should also
pay attention to Kucera's interesting work on non-priority solutions
of Post problem.)
My first question for Soare is: does Theorem 1 require a priority
My second question is, what about Theorem 2? This seems particularly
interesting from the viewpoint of "Simpson's Thesis", because Theorem
2 seems to be the one that Nabutovsky and Weinberger found most useful
in their applications to differential geometry. But the proof of
Theorem 2 remains a mystery, at least to the general public. Soare
announced Theorem 2 more than a year ago, but he has not yet explained
the proof to anyone.
Is Soare willing to comment on whether Theorem 2 "requires a priority
argument", in the sense that Friedberg/Muchnik is widely believed to
"require a priority argument"? Does Soare's other remark, that
Theorem 2 "requires a different approach", mean that the answer to my
question is no?
Soare has already said that Theorem 2' requires a priority argument
and is much more difficult than Theorem 1. My question now concerns
Theorem 2, not Theorem 2'.
Regarding Gromov's theorem.
The correct statement of the theorem is: If M is a compact Riemannian
manifold whose fundamental group has unsolvable word problem, then M
has infinitely many contractible closed geodesics.
Matt Frank (FOM, 11 June 2000) quotes from Soare's ASL 2000 talk:
> Soare mentioned a theorem that a compact Riemannian manifold with
> an unsolvable word problem has only finitely many closed
> contractible geodesics, characterizing this as logic coming in and
> geometry coming out. ....
and this agrees with my notes taken at the talk. But this statement
of the theorem is incorrect: "only finitely many" needs to be replaced
by "infinitely many". This was the context of my comment (FOM, 16
> However, the statement seems to be running the wrong way.
> Shouldn't "only finitely many" be replaced by "infinitely many"?
> This way it seems to make a lot more sense.
To my comment, Soare replied:
> If we take the contrapositive as Matt Frank suggests, then
> "finitely many" is correct.
But Frank's statement is not the contrapositive of the statement
attributed to Soare. "B implies A" is not the contrapositive of
"non-A implies B". I just wanted to straighten out that
Anyway, I think by now we can all agree on how to state the theorem.
As to who gets credit for the theorem. My notes taken at Soare's ASL
2000 talk say that Soare credited the theorem to Nabutovsky. But my
notes could be wrong. It could be that Soare mentioned both Gromov
In any case, the actual facts (which I was aware of before ASL 2000)
are that Gromov stated the theorem without proof in a 1981 paper, and
Nabutovsky proved it in a 1996 paper.
Nabutovsky's paper starts as follows:
"In  Gromov noted that if the fundamental group of a compact
Riemannian manifold has an unsolvable word problem, then the
manifold has infinitely many contractible closed geodesics. His
paper does not contain a proof of this result, but it is not
difficult to prove this result by contradiction using, for example,
the following idea: ..."
Nabutovsky then goes on to give a fairly detailed sketch of the proof.
After that, Nabutovsky states and proves a series of more refined
results, giving bounds on the number of contractible closed geodesics
in M in terms of the Kolmogorov complexity of the word problem for the
fundamental group of M.
I don't know whether Gromov ever wrote up a proof of the theorem. I
only know that there is a widespread though perhaps not universal
practice of attributing a theorem to the person who first proves it,
rather than to the person who first states it.
Gromov's paper is "Hyperbolic manifolds, groups and actions", in
"Riemannian surfaces and related topics", I. Kra and B. Maskit, eds.,
Annals of Math Studies, vol 97, 1981, 183-215. Nabutovsky's paper is
"Fundamental group and contractible closed geodesics", Comm Pure Appl
Math, vol 49, 1996, 1257-1270.
More information about the FOM