On Mathematical Diseases
Mathematical diseases: symptoms and examples
Underwood Dudley is a number theorist, who is perhaps best known for his popular books on mathematics. The most famous one is A Budget of Trisections, which studies the many failed attempts at the ancient problem of trisecting an angle with only a ruler and a compass. This problem is impossible, yet that has not stopped some people from working day and night looking for a solution. Trying to find such a solution is an obsession for some; it’s almost like they have a malady that forces them to work on the problem.
Today I plan on talking about other mathematical obsessions. They are like diseases that affect some, and make them feel they have to work on certain mathematical problems. Perhaps P=NP is one?
Dudley’s book is quite funny, in my opinion, although it does border on being a little bit unkind. As the title suggests, in “A Budget of Trisections,” he presents one attempt after another at a general method for trisecting any angle. For most he points out that when the angle is equal to some value what the exact error is. For others he adds a comment like:
This construction almost worked, if only the points
and
and
had really been co-linear it would have worked. Perhaps the author could move
His book is about the kind of mathematical problems that I will discuss today: problems that act almost like a real disease.
I cannot resist a quote from Underwood that attacks bloggers. Note he uses “he” to refer to himself in this quote:
He has done quite a bit of editing in his time–the College Mathematics Journal for five years, the Pi Mu Epsilon Journal for three, the Dolciani Mathematical Expositions book series (six years), and the New Mathematical Library book series (three years). As a result he has a complete grasp of the distinction between “that” and “which” (very rare) and the conviction that no writing, including this, should appear before the public before passing through the hands, eyes, and brain of an editor. Take that, bloggers!
(Bold added by me.)
Oh well.
What Is a Mathematical Disease?
This is the flu season in Atlanta, and many are getting it. I hope you either miss the bug, or if you are unfortunate enough to get it, get a mild case.
There is another type of “bug” that affects mathematicians—the attempt to solve certain problems. These problems have been called “diseases,” which is a term coined by the great graph theorist Frank Harary. They include many famous problems from graph theory, some from algebra, some from number theory, some from complexity theory, and so on.
The symptoms of the flu are well known—I hope again you stay away from fever, chills, and the aches—but the symptoms for a mathematical disease (MD) are less well established. There are some signs however that a problem is a MD.
- A problem must be easy to state to be a MD. This is not sufficient, but is required. Thus, the Hodge-Conjecture will never be a disease. I have no clue what it is about.
- A problem must seem to be accessible, even to an amateur. This is a key requirement. When you first hear the problem your reaction should be: that is open? The problem must seem to be easy.
- A problem must also have been repeatedly “solved” to be a true MD. A good MD usually has been “proved” many times—often by the same person. If you see a paper in arXiv.org with many “updates” that’s a good sign that the problem is a MD.
Unlike real diseases, MD’s have no known cure. Even the solution of the problem will not stop attempts by some to continue working on it. If the proof shows that something is impossible—like the situation with angle trisection—those with the MD will often still work hard on trying to get around the proof. Even when there is a fine proof, those with the disease may continue trying to find a simple proof. For example, Andrew Wiles’ proof of Fermat’s Last Theorem has not stopped some from trying to find Pierre de Fermat’s “the truly marvellous proof.”
Some Mathematical Diseases
Here are some of the best known MD’s along with a couple of lesser known ones. I would like to hear from you with additional suggestions. As I stated earlier Harary was probably the first to call certain problems MD’s. His original list was restricted to graph problems, however.
There are some beautiful partial results: for example, the work of László Babai, Yu Grigoryev, and David Mount on the case where the graphs have bounded multiplicity of eigenvalues is one of my favorites. Also the solution by Eugene Luks of the bounded degree case is one of the major milestones.
I would like to raise one question that I believe is open: Is there a polynomial time algorithm for the GI problem for expander graphs? I asked several people at the recent Theory Day and no one seem to know the answer. Perhaps you do.
I have been affected with this MD for decades. Like some kind of real diseases I get “bouts” where I think that I have a new idea, and I then work hard on the problem. It seems so easy, but is also like GI—very elusive. I would be personally excited by any improvement over the above bound. Note, the hard case seems to be the problem of deciding isomorphism for 
I somehow have been immune to this disease—I have never thought about it at all. The problem does seem to be solvable; how can all the subgraphs not determine a graph? My only thought has been that this problem somehow seems to be related to GI. But, I have no idea why I believe that is true.
is a non-zero constant. Note, 
This is a perfect example of a MD. I have worked some on it with one of the experts in the area—we proved a small result about the problem. During the time we started to work together, within a few months the full result was claimed twice. One of the claims was by a faculty member of a well known mathematics department. They even went as far to schedule a series of “special” talks to present the great proof. Another expert in the area had looked at their proof and announced that it was “correct.” Eventually, the talks were cancelled, since the proof fell apart.
Some of this work is quite technical, but it seems a bit like an MD to me. There are amateurs and professionals who both seem to always want to create a new system. Many times these systems are broken quite quickly—it is really hard to design a crypto-system.
A recent example of this was the work of Sarah Flannery and David Flannery in creating a new system detailed in their book In Code. The book gives the story of her discovery of her system, and its eventual collapse.
Open Problems
What are other MD’s? What is your favorite? Why do some problems become diseases? While others do not?
I would love to see some progress made on group isomorphism—I guess I have a bad case of this disease. I promise that if you solve it I will stop thinking about it. Really.
Trackbacks
- Tweets that mention On Mathematical Diseases « Gödel’s Lost Letter and P=NP -- Topsy.com
- uberVU - social comments
- More on Mathematical Diseases « Gödel’s Lost Letter and P=NP
- Some of My Favorite Books « Gödel’s Lost Letter and P=NP
- Fun with the Lazy State Monad « Melding Monads
- My mathematical diseases « Mas que Combinatorics
- Improbable Research » Blog Archive » Mathematical Diseases
- The Collatz conjecture, Littlewood-Offord theory, and powers of 2 and 3 « What’s new
- The Lonely Runner Conjecture « Gödel’s Lost Letter and P=NP
- The Informatics Prize « Gödel’s Lost Letter and P=NP
- math monster | Turing Machine
- What I did in my summer holidays | Gowers's Weblog
- Isomorphism Is Where It’s At | Gödel's Lost Letter and P=NP
- Deterministic RIP matrices: a new cooperative online project | Relax and Conquer
- The More Variables, the Better? | Gödel's Lost Letter and P=NP
- Number Theory is the Cocaine of Mathematics | fractalcows
- Yan's Cube: Odd 4-Cycles | fractalcows
- Graphical Supersymmetry Algebras | fractalcows
- Enriching the Frankl Conjecture | Gödel's Lost Letter and P=NP
- leading authorities weigh in on P vs NP proofs | Turing Machine
- collatz deja vu | Turing Machine
- collatz histogram discrepancy | Turing Machine
- PSA: If you’re gifted, you’re going to have to do math or something everyday for the rest of your life to stay sane – Blunt Japanese Woman | INTP Marketer in Japan
What a great subject!
To lead off, a wholly benign, utterly useless, and wonderfully enjoyable MD is the study of self-replicating structures in Conway’s Life.
The accomplishments of the Life community over the last 39 years are so amazing, that all one can say is … Golly! 🙂
A nice list Professor!
The following 2 problems spring up to my head; they both have a number theoretic flavor though.
The first one is the Goldbach conjecture. I mean, I find it really amazing that this problem is accessible to people like me with a modest mathematical problem and is so profound that it has avoided attacks by best brains.
The next one is the 3x+1 problem. This “seemingly” toy problem has much to offer as shown by its resistance to attempts at solving it.
I think my favorite bug is the 4-color conjecture. 633 configurations is still too many!
Although not so easy to state, I think Riemann Hypothesis has attracted quite a lot of attention. See here for a list of attempted proofs.
Yes. It also has been claimed a few times. One claim made the front page of the New York Times.
As someone who’s been bitten by the reconstruction bug, I’ll tell you that it is indeed related to graph isomorphism on a fundamental level. Here’s a brief sketch of why:
If we label the vertices of a graph, then reconstruction is trivial — we just glue the induced subgraphs together so that the labels match up, and in fact we only need three induced subgraphs to reconstruct our original graph. The reconstruction conjecture is that, if we forget the labels, then this “gluing” process is still unique (up to graph isomorphism, of course). This feels like it should be intuitively true, but there’s a crucial problem: namely, if the graph has a large automorphism group, then its induced subgraphs can get “put into” the original graph in many different ways, and it’s not clear that the global properties of the graph don’t change.
So much of the work on graph reconstruction centers around understanding just how automorphism groups of graphs behave, and how they relate to combinatorial properties. (From the other direction, by the way, it’s an old result of Bollobas that almost all graphs are reconstructible, since random graphs don’t allow us to embed large subgraphs into them in more than one way.)
Here is my favourite mathematical disease.
In a recent talk entitled “A DISCOURSE ON THREE COMBINATORIAL DISEASES” Alexander Rosa has ranked number one the graceful tree conjecture (GTC) as a combinatorial disease [1]. Definitions of the three related conjectures have been listed below:
1. Ringel’s conjecture (RC,1963). The complete graph K2n+1 with 2n + 1
vertices can be decomposed into 2n + 1 subgraphs, each isomorphic to a
given tree with n edges.
2. Kotzig’s conjecture (KC,1967). The complete graph K2n+1 can be cyclically
decomposed into 2n + 1 subgraphs isomorphic to a given tree with n
edges.
3. Graceful tree conjecture (GTC,1967). Every tree has a graceful labelling.
Despite of huge efforts very little known for graceful trees e.g., any tree with <34 vertices has a graceful labeling [2] and all trees of diameter up to 5 are graceful [3].
There is even no a "zero-knowledge proof" for the graceful tree conjecture.
[1] http://www.math.ilstu.edu/cve/speakers/Rosa-CVE-Talk.pdf
[2] http://www.projectgtv.cn/index_en.html (Graceful Tree Verification Project)
[3] http://www.combinatorics.org/Surveys/ds6.pdf
Your right. How can this be open? It seems so simple. Yet it is very hard. Thanks for the details.
Graceful Tree Conjecture is my favorite too. Read my earlier post here.
Let me give short explanation why GTC is a mathematical disease. Rosa has identifi ed essentially three reasons why a graph fails to be graceful: (1) G has “too many vertices and not enough edges,” (2) G “has too many edges,” and (3) G “has the wrong parity.” If for any graceful tree an arbitrary vertex can be assigned the label 0 (rotatable tree) then the proof of the GTC would be piece of cake. Unfortunately not all trees are rotatable. Similarly if all trees are alpha-valuable (a kind of balanced labeling stronger than graceful (beta-valuable) labeling) then the proof of GTC follows easily. What remains is an algorithmic proof attempt based on the induction on the diameter d (the length of the longest path in a tree) of a tree. Unfortunately most of the trees with diameter greater than 4 have no alpha-labeling. In the past I have attempted twice (once in 1975, settled a class of symmetric trees and again 1980, settled all trees of diameter 4). I didn’t give up, it is a disease after all.
See a letter from Gerhard Ringel at:
http://www.flickr.com/photos/49058045@N00/3947426742/
Additional note:
If one day the graceful tree conjecture will be settled, there is even stronger one!
See a letter from Donald E. Knuth at:
http://www.flickr.com/photos/49058045@N00/2094508909/
There are also some really super simple problems that function like diseases such as the Goldbach Conjecture:
http://en.wikipedia.org/wiki/Goldbach%27s_conjecture
Everyone has dreamed about solving these at least a little bit at some stage in their life. There’s even a (fictional) book written about this problem about a man obsessed with solving it:
http://www.amazon.co.uk/Petros-Goldbachs-Conjecture-Apostolos-Doxiadis/dp/0571205119/
I think there is a confusion here between two different types of “diseases”.
There is the “disease” where an amateur mathematician tries to prove a big conjecture or problem. This indeed entails the problem to be formulated simple enough, so that the amateur can at least convince him/herself that he/she has the solution.
I claim that this “mathematical disease” is in many cases a symptom of a real mental problem — it usually appears in eccentric figures, with a tendency to obsessive and compulsive behavior.
These people are usually referred to as “cranks”. Most P vs NP papers fall into this category.
On the other hand, there are “healthy”, or fruitful, mathematical obsessions, that is, an obsession of a professional mathematician to solve certain important (and even not so important) problem. And in this case, it’s not necessary at all that the problem has a simple formulation .
For a long time the irrational/rational nature of zeta(3) was open. It was solved by a non-mathematician, Roger Apéry.
I believe that he was not a professional mathematician and was almost dismissed asa “crank”. But he had a proof.
http://en.wikipedia.org/wiki/Roger_Apéry
He was a professor at a small French university. He was past the age most mathematicians prove big theorems, he had a history of bad proofs, not a big research output and, I was told, also an alcoholic. But he was a professional mathematician and not a crank.
We still don’t know whether zeta(3) is transcendental.
Never said was a crank. I did understand that he was in another area. Sorry if I got it wrong.
Actually, Apery was a math professor at Caen with a fairly prestigious background (he was a prize-winning student at ENS) and a number of research publications; although he wasn’t a terribly high-profile researcher, he was by no means an outsider to the mathematical research community.
The reason people were initially skeptical was that he gave a very weird talk presenting the proof. In the talk, he stated some implausible-looking identities and recurrences, with no hint of how to prove them, and he showed that they implied the irrationality of zeta(3). He apparently didn’t respond well to questions, and this led people to wonder whether he actually had a proof of the identities. Maybe he had just conjectured them based on numerical experiments, and perhaps they weren’t even true. He eventually came out with a paper that proved everything, and he probably had the proofs at the time he gave the talk, but he certainly didn’t explain it at all clearly at that time. I think it wasn’t until Don Zagier came up with his own proofs of Apery’s assertions that everyone became convinced it definitely worked (although everyone got very excited even before that, once they checked everything numerically and found that it all seemed to work).
The Palendromic Number Conjecture. I suck non-mathematicians in with that one all the time — especially computer people because there’s a proof that the conjecture holds for binary.
Conway’s Thrackle conjecture bites me about once every two years… 🙂
Allow me to get a little bit infected…
If we assume the graph reconstruction conjecture, does this imply anything interesting about the complexity of graph isomorphism? If you want to tell whether two n-node graphs are isomorphic, and you know that this “reduces” to checking whether there is an “isomorphism matching” between two sets of n graphs on n-1 nodes each, can you get a recursive algorithm?
As one of the many who search for new cryptosystems, allow me to defend the affliction (before someone develops a vaccine)!
Sure, factoring- and discrete-log-based systems are great for Alice and Bob’s everyday secret messages, but…
What if you don’t believe that these problems are truly hard?
What if someone builds a quantum computer? (What if it happens sooner rather than later?)
What if your device is constrained and can’t handle 2048-bit exponentiations?
What if you need ‘extra features,’ like delegation, revocation, or homomorphisms?
What if you want to be guaranteed security even if some/most of your secret key leaks out via a side channel?
Your standard-issue cryptosystems don’t admit very satisfactory answers to these questions. That’s why we need to look for more…
Let me adopt the MD term under a slight protest and mention (in two installements, alas without serious editing,) some of my favourites MDs that I spent most time studying.
1) The rate of error-correcting binary codes (and spherical codes). Asymptotically.(Infected by Nati Linial)
A very easy to describe problem. You want an error correcting binary code on n bits with minimal distance delta n. What is the largest possible rate as a function of delta.(A closely related problem is about the densest sphere packing in high dimensional spaces.)
Is the Gilbert-Varshamov lower bound the correct one? Can the MRRW upper bound (the best known one) be (even slightly) improved?
A (somewhat) related (easier) problem: Can you find an elementary construction (not based on algebraic geometry) for large-alphabets codes with better rate than Gilbert-Varshamov. (The zig-zag success for expanders give some little hope.)
2) The g-conjecture for spheres;
This is probably the first problem on my list. I started working on it the earliest and probably spent more time on it than on any other. It is a little hard to explain and motivate. But there are quite a few people who thought about the problem. (There are a few posts about it on my blog).
3) The Hirsch conjecture (and strongly polynomial LP)
I wrote about it amply on my blog.
4) The Erdos-Rado Delta system-conjecture
This is on Gowers’s possible future polymath projects so let me not elaborate further here.
5) The Cap set conjecture
It is about the largest size of a subset A of (Z_3)^n not having three elements that sum to zero.Closely related to Roth’s and Szemeredi’s theorems.
6) Borsuk’s conjecture.
I dont think Jeff Kahn and I were “obsessed” about the problem while working on it for quite a few years. It is not clear if an obsession mode is a good sign.
Our approach to the problem is somewhat related to a famous open problem which is still open and is on Alexander Rosa’s list and was always high on Jeff’s list: The Erdos-Faber-Lovasz conjecture. (Jeff settled the EFL cnjecture asymprotically and Jeff and Paul Seymour solved it fractionally.)
7) Bible codes
This represents an applied topic that I intensively (and obsessively) spent much time in the late 90s. At the end I was a coauthor of a 4-authors paper containing a thorough refutation of the scientific evidence for the existence of bible codes.
It was a good (while strange) introduction for me on various issues regarding statistics, science, scepticism, even philosophy of science.
8) Learnability vs rationality
One tempting “cure” for various deseases, especially of conceptual nature, is “learnability” via VC-dimension. I was very optimistic at some time about the usefulness of replacing “rational” by “learnable” in the foundations of theoretical economics.
9) Infeasibility of quantum computers
This represents a current main research interest.
Let me mention some flirting with famous problems
10) 4CT
Once I had some idea about 4CT (which asserts that every planar cubic graph is 3-edge colorable) and relating it to Tverberg’s theorem, and I remember Laci Lovasz asked me: “Can you use your approach to prove that a bipartite cubic graph is 3-edge colorable?” (Which is an easy graph theory result.)
Dealing with bipartite cubic or even with bipartite planar cubic graphs looks like a good test-case for various hypothetical approaches.
11) NP ne P and related issues
It is probably a good instinct whenever you study some new notion about Boolean functions (or simplicial complexes which are just monotone Boolean functions) to spend a little (let me repeat: a little) time on thinking: does this new notion has baring on NP=!P or other questions in computational complexity?
Most often you can easily realize that the answer is no, and sometimes you realize that the answer is no after some more effort.
12) A little flirt with Poincare
I was interested in triangulation of manifolds for which the links of vertices are of the simplest possible kind: stacked spheres. (They are the boundaries of a set of simplices glued together along facets.)
For dimension greater than 3 I proved that such a simply connected manifold is a sphere. For dimension 3 I could not prove it and it is a very very very special case of the Poincare conjecture. (I still cannot prove this special case directly.)
If you drop the assumption that the manifolds are simply connected then for d>3 you are left with very simple handle body manifolds. I do not know (and am curious to know) which 3-manifolds have a triangulation where are links are stacked spheres.
Gil Kalai, would you mind commenting further (either here or on your own blog) about “infeasibility of quantum computers?” I have finally started learning some basic quantum techniques, because I think they might be useful to prove non-quantum statements that interest me, but I have serious reservations about the physical realization of quantum computers. Are you saying a research direction exists that attempts to prove their physical impossibility, for example through a better understanding of decoherence?
Hmm, probably I should have written: ” 9) feasibility of quantum comuters.” This is the area of understanding fault tolerant quantum computation, e.g. how to handle decoherence.
Since the concept of quantum computers is quite revolutionary it is natural to have some reservations like you have. Nevertheless, there are good responses to various concerns that were raised over the years, and it is fair to say that, at this stage, optimism is not only instrumental but also fairly justified. As you correctly understood my interests are in the negative direction.
Learning quantum information/computation is certainly a very good thing to do. And the idea that quantum techniques will have applications in other areas (similar to applications of probability) is a nice idea that was also discussed in this blog. (So far, there are handful of examples). In any case, even in the likely event that quantum tricks will not help the non quantum statements that interest you, you may certainly enjoy learning the quantum tricks.
(Here is the post on the “quantum method”. http://rjlipton.wordpress.com/2009/03/28/erds-and-the-quantum-method/)
I forgot one (that I took from Itai Benjamini, Yuval Peres and Oded Schramm). It is the “Dying prtcolation conjecture” which asserts that for three dimensional percolation at the critical probability p_c, the probability for an infinite open cluster is zero.
In the Harary paper they cite the Rudrata disease, an old and widespread one. I like specially the RCD-variant (Rudrata problem for Cayley Digraphs), also old and widespread. Be aware: the later infection is harder to cure than the more general Rudrata disease, since the problem seems simpler !
Afaik the complexity of this RCD-disease is still unkown even for very restricted cases and imo this problem is a good candidate for the class of intermediate problems (NPI ? PI ?). I ignore if some cases
of known polynomial sequential complexity (i.e. 2-circulants: Woeginger is co-author of a paper about this)can be parallelized efficiently.
The point is that to my knowledge the complexity of the GI problem for CD is also unknown even for general circulants. On the other hand it is known that CD are tools for describing groups succintly so i wonder how the Group isomorphism problem could be related to GI via CD isomorphism.
The Splay Conjecture and the Sunflower Lemma are major ones.
People have been seeking (and are still seeking) the Philosopher’s Stone for hundreds of years. Physics even gives hope that transformations of base metals into gold can be economically achieved. While not impossible, a cost-effective solution is likely improbable and success would undermine the cost of gold so much, that markets would make any gains from the innovation very short-lived.
People still have MD over Fermat’s Last Theorem. Proved or no, they are still seeking Fermat’s “elegant” proof.
Einstein went to his grave denying the Heisenberg Uncertainty Principle and people (even physicists) still confuse it with the Observer Effect.
Arrow’s Impossibility Theorem hasn’t halted popular faith in the institution of democracy, nor should it. In the absence of a first-best solution, second-best solutions are not only tolerable but desirable.
Time travel is axiomatically impossible, yet even Stephen Hawking has retreated in the face of popular zeal for this science fiction myth and justified it with pseudo-scientific conjecture.
Gamblers and mathematicians seek fool-proof winning systems consisting of linear combinations of wagers with negative expected value and still think they can succeed.
When climate scientists regard their theories as “settled”, it flies in the face of so many previous notions which were considered “settled” and subsequently disproven. “Settled science” is an oxymoron.
There is a converse to futile efforts toward discovery. We know, for example, that chess has either a winning strategy for White or a non-losing strategy for Black. The strategy is likely unimplementable by a human being. Yet the search for this difficult strategy continues and, if found, would hardly kill the game as an enjoyable past-time. After all, we still teach our children Tic-Tac-Toe.
The ultimate question which is both unprovable and undeniable is the existence of God. Mankind’s finite intellect and limited sensory capabilities make either pursuit entirely futile. An extradimensional entity is beyond anyone’s ability to comprehend or observe. Continued discussion, though, is fruitful but continued argument is a waste of time. Scientists never could reconcile matters of faith with the shortcomings of their profession. Indeed, they refuse to admit shortcomings of their profession.
The bottom line is that stubborn people, (the most stubborn of which are scientists) don’t like being told anything is impossible. There is value in people trying to attain that which is merely believed to be impossible (like heavier than air flight). Attempting to prove the known impossible is folly, but some useful insights might be gained in the attempt. Many an innovation was discovered by accident while searching for something else.
“There are more things in heaven and earth…than are dreamt of in your philosophy.”
“While factoring, discrete logarithm, and elliptic curves seem to be fine existing public key systems,…”
I can’t see how this is true. They are only fine if you are satisfied with very weak security guarantees. You have security until somebody builds a quantum computer. Maybe that won’t be for a while. However, there has been a lot of momentum building on several experimental implementations. (Also, at least as much work is now being done in secret as in public, so don’t count on someone telling you when your security blanket has been pulled away.)
Therefore, given how heavily reliant we currently are on public-key cryptography, finding new schemes has to be a pretty urgent problem. I can’t see how it can be called a “mathematical disease.” I can still see the other problems on your list afflicting computer scientists and mathematicians twenty years from now. If we don’t have better public-key cryptosystems twenty years from now, then we will be in trouble.
(On the other hand, maybe it is possible to run the modern Internet and other networks without public-key cryptosystems? Instead, perhaps some infrastructure could be deployed. Given the ubiquity of public-key crypto, I think this would be a challenge, but I don’t know enough about it.)
I wrote, “I can still see the other problems on your list afflicting computer scientists and mathematicians twenty years from now.” But what will happen to the P versus NP question when we have quantum computers? Will this question still be seen as important, or will the research just move on to BQP versus QMA?
Honest question: How important is P versus NP in a quantum world?
Just a note, Underwood Dudley’s “Budget of Trisections” has been reprinted by the MAA as “The Trisectors”, so if difficulty is encountered finding an old used edition you can just go over to the MAA (or wherever you buy books) and get it new.
If memory serves— I no longer have the older book, published by Springer— the new “Trisectors” includes expanded commentary about trisections, in the same vein as Dudley’s other books on cranks and numerology, before the material that is identical to what appeared in the original “Budget of Trisections.” It is a great book.
(I am not Underwood Dudley.)
Even if you are him, it is still a great book. Thanks for pointer to new name.
Just to complete my previous comment on Rudrata disease on this thread: as well as Rudrata problems on CD are good candidates for intermediate problems in P and NP, the undirected version, wich is a restricted version of a well known loved conjecture (wich will probably be solved positivelly, hopefully soon) is a good candidate for a problem similar to factoring.
Didn’t the Collatz conjecture cause a lot of overloading on many many mainframes when computer scientists first became aware of it in the 1970’s? Surely that counts as a disease.
The Frey-Mazur conjecture is a personal MD (see conjecture 3 of this paper: http://www.springerlink.com/content/k251nu0703j75441/fulltext.pdf).
Although it’s more recreational in flavour, I think the Collatz conjecture (aka the Hailstone conjecture) fits the first two criteria of an MD. I’m not sure how often it has been claimed that it has been solved but, as Charles notes, it would have certainly chewed up a lot of processing power creating visualisations of the hailstone function.
My favourite “surely that’s not open” problem is the Frankl conjecture (aka the Union-closed sets conjecture): “for any finite union-closed family of finite sets, other than the family consisting only of the empty set, there exists an element that belongs to at least half of the sets in the family.”
I’ve mentioned this to several people who have all said something along the lines of “that should be easy”, wrestled with it for several hours and given up, exasperated.
Great example. What is the best known on this conjecture? Do you know?
I’ve only really engaged with the Union-closed set conjecture recreationally. That is to say, I haven’t looked up any “serious” work that has been done on it.
The Wikipedia entry notes that the conjecture has been proven for several special cases.
When talking about the best known result(s), we should use the more abstract lattice theoretic formulation of the conjecture: Every nontrivial finite lattice L has a join-irreducible element that is at or below at most half the elements of L.
The conjecture is known to be true for lattices having some additional structures, e.g. for modular lattices. Furthermore there are various results for lattices fulfilling some bound-condition, e.g. for lattices having a limited number of elements or having a limited number of join-irreducible elements. Links can be found at Wikipedia and elsewhere.
None of these results gives any clue, how the prove the conjecture in general.
The “best” known result from my understanding is a tautology: For every integer n >= 2 the conjecture is true for more than half of the isomorphism classes of lattices having n elements. It is tautologic, since for any lattice not fulfilling the conjecture the conjecture is obviously fulfilled by the dual lattice – having the reverse partial ordering -, and since for any n there are lattices isomorphic with their dual lattice.
There’s one mathematical disease that I am missing here: (video) compression!
Just Google “Jan Sloot” to see what I mean.
Here is another MD : The Rota Basis conjecture : in a vector space of dimension at n. Given n basis : write one per line. Can you reorder each line ( in itself) so that in each of the n column you have a basis too? Case n = 3 is ok but messy . n = 4 too messy for me. There is also some matroid formulation with some partial reduction to equivalent conjecture ( Timothy Chow ..)
Have you seen a direct proof of n=4 or 5? Do you have a reference?
No I do not have seen proof, it seems doable by computer using brute force for n=4 ?
This can’t be the correct formulation, since the rows are a basis iff the columns are a basis…
It doesn’t really fit your definition, but the quest to define higher categories in a “correct” way is very similar to an MD.
Anyone who knows a bit of category theory has exactly the reactions you described when faced with the question of how to generalize a category to an n-category.
This is even worse than a regular MD because it has no real “solution”.
I think at last count there are probably about 5 different definitions of n-category and/or infinity category which people are working with.
This has also sprouted an industry of comparison between the different models, usually vis a vis model category structures. Kind of silly when you think of it since a model category structure is only defined on a usual category, so of course people are also trying to extend the notion of model category, and the complications are endless.
It seems that I said the same thing as
http://en.wikipedia.org/wiki/Rota%27s_basis_conjecture
Collatz conjecture = cocaine
Let c(n) be the number of steps to convert n to 1 using the Collatz rules. I just noticed that c(5) = 5. Are there any other number n such that c(n) = n? Or is there a simple explanation as to why only 5?
Hi,
My mathematical disease is Goldbach’s conjecture : you can see my symptoms here :
http://denise.vella.chemla.free.fr
with a hope of total remission here :
https://hal.archives-ouvertes.fr/hal-01109052
Good morning from France.
Denise Vella-Chemla
The fact that you write “a MD” proves Dudley’s point