[FOM] Soare's article in the BSL

[Stephen G Simpson]

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
on-line at

  http://www.cs.nyu.edu/pipermail/fom/2000-July/004224.html

An additional reference is to my FOM posting of August 4, 1999 on the
so-called Simpson's Thesis, available on-line at

  http://www.cs.nyu.edu/pipermail/fom/1999-August/003348.html

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
 argument?

 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
 June 2000):

  > 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
 misunderstanding.

 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
 and Nabutovsky.

 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 [10] 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.

 -- Steve