There are some theorems that seem less interesting once you generalize them. I am not sure they are less interesting, but they seem that way. Here are some.
- In 1978 I told my number theory professor that there is a polynomial in many variables with integer coefficients such that the positive numbers in the image are exactly the primes. He thought that was interesting! Maybe it uses algebraic number theory! or cyclotomic fields! or some deep number theory! I then told him that for any r.e. set A there is a polynomial in many variables with integer coefficients such that the positive numbers in that set is exactly A. You prove this by coding Turing Machines into polynomials. No hard number theory needed. It uses some easy number theory and many tricks. He was much less interested. (The result comes from the machinery used to prove Hilbert's Tenth Problem.) Jones came up with the actual polynomial. See here.)
- It easy to show that if L is regular (CFL, c.e.) then SUBSEQ(L) is regular (CFL, c.e.). What about if L is decidable? The good news: if L is decidable then SUBSEQ(L) is decidable. That sounds surprising and interesting. It is not. Actually if L is any language whatsoever then SUBSEQ(L) is regular. (High Level Proof: subsequence is a well quasi ordering, hence any downwardly closed subset of Σ*, such as SUBSEQ(L), has a finite obstruction set. This finite obstruction set can be used to give a DFA for SUBSEQ(L).) What I really want to see is a proof of L decidable implies SUBSEQ(L) is decidable that comes from recursion theory. I don't have one. I'm not even sure what that would mean. Show that SUBSEQ(L) is both c.e. and co-c.e.? (For more information see this post of mine.)
this blog talks about complexity.
ReplyDeletethis blog talks about everything.
pardon my ignorance. what means 'c.e.' ?
ReplyDeletec.e. means computably enumerable, which is the same as r.e. or recursively enumerable.
ReplyDelete> If you know theorems that are less
ReplyDelete> interesting because they are more
> interesting, then please comment.
I don't know if that counts, but...
Merge sort can be easily modified to sort in n(1+\lg\rho) comparisons where \rho is the number of maximal ascending runs in the input. This is optimal in the worst case over all instances of fixed n and \rho. Insertion sort can be similarly modified (into "local insertion sort", using a (2,4) finger search tree) to sort in n(1+\lg(\inv/n)) comparisons, where $\inv$ is the number of inversions in the input. This is also optimal in the worst case over instances of fixed n and \inv.
Step 1: interest.
I found all this quite interesting when I learned it, a long time ago, and even more the fact that no known sorting algorithm was known to be optimal in the worst case over all instances of fixed n, \rho and \inv (and that some people had been working on it).
Step 2: disappointment
I lost a bit of my interest when I realized that, asymptotically, the algorithm simulating both algorithms in parallel is obviously optimal for both \rho and \inv.
Step 3: regain of interest
I regained interest in the theme when I realized that all those results could be generalized to encodings of permutations, where multiplicative constants do count.
Generalization goes both ways?
"Theorems that seem less interesting once you generalize them" have a beauty all their own ... when they are instantiated as Mathematical Magic Tricks.
ReplyDeleteBecause if we think about it ... we see that the best mathematical magic tricks are wonderfully amazing when seen as particular instantiations, and yet utterly simple when the general mathematical principle is revealed.
As just one example (of many), see Colm Mulcahy's column A Little Erdös/Szekeres Magic.
This occurs in quantum information theory too ... results that seem mysterious and even paradoxical in coarse-grained projective descriptions, become natural and even trivial in fine-grained symplectic descriptions.
Indeed, the entire point of math & physics (arguably) is to discover the simple-yet-illuminating general theorems ... without losing sight of the fun and wonder that is associated to the mysterious-seeming special cases.
Suppose someone proves P=NP. How interesting will results of the form "either P=NP or ..." be? This is about 90% of complexity theory, right?
ReplyDeleteboring posts are boring
ReplyDeleteHere's an example that's not an example. Probably the Green-Tao theorem can be vastly generalized, to the statement that every set of integers with density at least that of the primes (and indeed considerably smaller) contains arbitrarily long arithmetic progressions. But that wouldn't show that the Green-Tao theorem "has nothing to do with the primes", partly because they make genuine, and very interesting, use of the primes in the proof, and partly because the proof of the general result is likely to be harder rather than easier.
ReplyDeletePerhaps the point is that often (paraphrasing Hamming) we want insight, not only a proof. In a simpler context the insight may be easier to grasp.
ReplyDeletei see.
ReplyDeleteBonjour,
ReplyDeleteVous trouverez ci-joint mon Blog (fermaton.over-blog.com)présentant ma nouvelle théorie mathématique de la conscience.
Par la présente, j'aimerais si vous le voulez bien que les scientifiques de votre communauté me fassent parvenir leur commentaire.
Cordialement
Dr Clovis Simard,phD
Well, general theory plus special considerations within a restricted domain can equal interesting result, no?
ReplyDelete