User talk:Rybu

From Wikipedia, the free encyclopedia

Contents

[edit] My todo list

  • Fix up Cerf theory page with examples.

[edit] Classification of four-manifolds

Thank you for replying! There are still quite a few points that I am not sure about. I've copied the whole discussion here for convenience, but please, feel free revert if you object to this.

[edit] Higher dimensional classification

What is the following sentence trying to express?

The classification of n-manifolds for n greater than three is known to be impossible, even up to homotopy equivalence.

I thought that it's about impossibility of classifying the fundamental groups, and it appeared so from the next couple of sentences, but when I incorporated a manifest reference to the fundamental group there, it quickly got reverted with a note about 'misleading argument'. So now I am confused:

  • Given a finite presentation of a group, are there further algorithmic obstructions to classifying four manifolds with that fundamental group (choose your favorite way of interpreting 'classifying')?
I think the point was that the fundamental group is one obstruction. There are in general further complications such as the classification of higher-order forms such as cubic forms, things like intersection forms and torsion linking forms..Rybu 08:56, 21 April 2007 (UTC)
Ok, from your reply (here and below) I gather that the fundamental group is considered to be the obstruction to (algorithmic) 'classification' of four-manifolds (and of course, also n-manifolds with n larger than four). Then I think it should be mentioned straight up, as I tried to do, because the present version of the article is weasel on this point. Also, given some counter-inuitive properties of higher-dimensional manifolds, it would make sense to explicitly state what happens when n is larger than four.
I take classification to mean two things: a non-repeating list of all the objects 'classified' together with an effective procedure to determine, given some reasonably-flexible standard presentation of an object, which object in the list it is isomorphic to, together with a procedure to construct the isomorphism. In dealing with low-dimensional manifolds, you could consider the 'listing' problem to be solved by the 'isomorphism' solution (if you have one) in that there are standard ways of constructing manifolds via triangulations or Heegaard splittings or surgery, etc. In high dimensions this is more of problematic as you don't even have a procedure to decide if a simplicial complex is a triangulation of a manifold. Anyhow, I disagree that the fundamental group is the obstruction. It's a big obstruction that we know a lot about. Classification of simply-connected manifolds in high dimensions is still a hard problem where there's open computational complexity problems -- such as classification of cubic and higher-order forms over the integers. They come up from the cup product structure on cohomology / intersection form on homology. Rybu 10:58, 21 April 2007 (UTC)
  • How does the undecidability of the isomorphism problem imply the impossibility of classification? It does not seem obvious on the surface.
Say you had a classification of 4-manifolds up to homotopy-equivalence. Then there is a procedure to determine if \pi_1 of a manifold M is trivial: it is trivial iff the manifold is homotopy-equivalent to a simply-connected 4-manifold. But simply-connected 4-manifolds we have a homotopy-equivalence classification by the H_2 intersection form. So find the simply-connected 4-manifold with the same H_2 form as M and ask your 'classification' whether or not the two manifold are homotopy-equivalent. So now you have an algorithm to determine if pi_1 M is trivial. Here is how you construct a procedure to determine if any finitely-presented group is trivial: take a connect sum of copies of S^1xS^3, as many as you have generators in your finitely-generated group. Now \pi_1 of this connect sum is a free group. Every relator in your finitely presented group is a word in \pi_1 (your connect sum) so represent it by an embeded curve, and do surgery on that curve. If you do that for all relators, you get a 4-manifold whose fundamental group is your initial finitely-presented group (this pi_1 computation is where we're using the fact that we're in dimension 4). This is the contradiction we were looking for, because there are known finitely-presented groups for which the word problem is algorithmically undecidable. Rybu 08:56, 21 April 2007 (UTC)
This is an interesting point. In the discussion about classification of three-manifolds, you seemed to take the position that classification amounts to a non-repetating list of manifolds. But if I understand you correctly, here you are saying that classification is the same as a decision problem. From the general algorithmic point of view, these are two different problems: recursively enumerable sets are more general than decidable sets. Let us specify an encoding of (let's say PL) four-manifolds. The fact that the decision problem of isomorphism is unsolvable means that the naïve algorithm that attempts to create a non-repeating list from a full list is impossible. But I don't quite see how it rules out another algorithm producing the list. Am I missing something? (A rather separate issue is that the word problem may not be the right thing to use in your argument). By the way, I think that the fact that certain problems are algorithmically unsolvable deserves a bit more than the casual 'since there is no algorithm' clause in the article. At least, there should be a link! Arcfrk 07:38, 21 April 2007 (UTC)
For 3-manifolds you can generate repeating lists by enumerating all the 3-manifolds that can be constructed via a triangulation with n tetrahedra. So one constructs the non-repeating list by removing the duplicates using geometrization to do the job. This is horribly inefficient and effectively useless when you consider that most 3-manifolds people are interested in do not appear in the lists constructed so far. The state of the art computer programs have been able to do this up to 3-manifolds triangulable with 11 or less tetrahedra, then they start to choke.Rybu 10:58, 21 April 2007 (UTC)


If you look at the above definition of classification comments in talk, you'll see a conversation on this already. I've been thinking of putting up a 'classification (mathematics)' Wikipedia page where we talk about what such a word typically means and all the side issues that it brings up like algorithmic complexity ie: some classifications are effectively useless because it's impossible on a silicone-based computer to handle the simplest cases. I'll put in some comments to your questions above.Rybu 08:56, 21 April 2007 (UTC)
That would definitely be worthwhile! Questions of algorithmic solvability in particular tend to lead to situations where vigorous handwaving can create an impression that the opposite of what is being claimed is true! Also, it may be argued that if (which I know isn't the case here) the isomorphism class of a manifold were determined by its fundamental group, then the classification were indeed possible: the manifolds would then have been classified by their fundamental groups! I do not think anyone objects to Eilenberg-Maclane spaces being 'classified' in this sense. In other words, and this is a meta-mathematical question, we may be interested in relative algorithmic solvability of a problem by reduction to another ('hard') problem (I think that this can be expressed using the notion of 'oracle'), even if the 'hard' problem itself isn't algorithmically solvable. But I am a little out of my depth on these issues. Arcfrk 10:03, 21 April 2007 (UTC)


Ok, now I understand the primary source of confusion: the definition of classification is really different from what I thought it was. In my field (algebra) classification does not (usually) involve any decision problems, just lists. Here is a somewhat imperfect example. All compact groups or simple complex Lie algebras are classified by Dynkin diagrams. In representation theory, this statement just means that there is a list of simple Lie algebras up to isomorphism (we need to develop some general theory to derive the list, of course). It does not mean that given a Lie algebra g (for example, specify its structure constants in a basis) and a Dynkin graph Γ, there is an algorithm to determine whether g is a simple Lie algebra of type Γ. Such an algorithm probably exists, but metamathematically, it's not part of what 'classification' stands for. I guess the lesson is that one cannot be as casual about what constitutes 'classification' as the article attempts to be at the moment: if the description cannot be unambigously interpreted even by mathematicians (who rightly pride themselves on being able to exactly understand and reproduce the objective meanings, regardless of differences of opinions, techniques, etc), it's really bad! Another, somewhat secondary source of confusion is that there are (as I understand from your helpful comments) several rather different facets of why classification is impossible or hard, which are all lumped together in one paragraph in the article.

Conclusions:

  • It is really necessary to include an explanation like the one you gave of what constitutes classification (it doesn't have to be long or technical).
  • It would be good to separate the features which make classification of high-dimensional manifolds difficult from those that make it impossible. Make the explanation more structured.
  • This article is in such a pitiful state that it is almost surreal to discuss very fine points of classification (tertiary source of confusion). Maybe, it's worthwhile to keep the most basic part, and move out the rest of the description (plus your comments above concerning triangulations, higher invariants on homology, application of Freedman's theorem to reduction 'classification implies algorithm for fp groups being trivial, etc) to a separate article.
  • Take a look at Classification theorem, it seems to be the page exactly of the type that you wanted to write, but of course, still very incomplete.

Thanks again for the explanations! Arcfrk 13:27, 21 April 2007 (UTC)

I think you will find a definitive reference is:
W. Boone, W. Haken, and V. Poenaru. On recursively unsolvable problems in topology and their classification. In Contributions to mathematical logic, pages 37-74. North-Holland, 1968.
The problem is indeed related to the isomorphism problem for finitely presented groups, and (if I recall correctly) Helmut Kneser attempted to use its insolubility to prove the same thing for compact 4-manifolds (by taking regular neighborhoods of 2-complexes realizing presentations of groups). There was a fatal flaw in this which required some cleverness to overcome (even though the idea remained the same).
To illustrate the delicate nature of the questions involved, consider the homeomorphism problem for connected finite 2-dimensional simplicial (or regular cell-) complexes. Obviously every finitely presented group appears as the fundamental group of some such complex. It should be relatively clear that it is impossible to determine which complexes have isomorphic fundamental groups, or even which ones have trivial fundamental groups (it would be tatamount to solving the isomorphism problem or triviality problem for finitely presented groups). It is also then a delicate matter whether one can decide when two such complexes have the same homotopy type. Nevertheless, years ago, Emmett F. Whittlesey proved in his Princeton Ph.D. dissertation that the homeomorphism problem has an affirmative solution - and that solution is fairly straightforward (at least to one who has looked into the problem of classifying compact surfaces). -- Chuck 21:03, 9 July 2007 (UTC)

[edit] Mathematical problem and Computing π

There was nothing ridiculous about my statement regarding pi. Calculating the number was a historical problem studied by Archimedes, Isaac Newton and others. It wasn't until computers in 1949 and then supercomputers in 1980's calculated pi to 29 million decimal places that the problem was "solved". I have a reliable reference to backup my statement. Do you have one to support your claims and subsequent deletions? - Shiftchange 07:11, 1 November 2007 (UTC)

The computer did not produce the algorithm to compute the decimal expansion of pi. Archimedes, on the other hand, gave a concrete procedure to compute the decimal expansion of pi. It was: inscribe a regular n-gon in the unit circle. Compute n*(side length of one side of the n-gon), then take the limit as n goes to infinity, and divide by two. The point of all this is that the computer implements known algorithms that people had implemented "by hand" before computers were available. The algorithm is the solution to the "problem", and the algorithm, in this case, has existed almost as long as the problem. Rybu