Skip to content

More on Mathematical Diseases

November 12, 2009


A summary of some your ideas on mathematical diseases

images

John Conway is a world renowned mathematician, who defies a simple description. He has worked on countless games, puzzles, and easy to state, but often hard—if not impossible—to solve problems. These range from his classic game of Life, to his work on Surreal numbers; from his work on polyhedra, to his special notation for huge numbers. At the same time he has made deep contributions to many, if not most areas, of modern mathematics: from group theory, to number theory; from algebra, to geometric theory. There is only one John Horton Conway.

Today I want to talk about some of the mathematical diseases that were raised by those who were kind enough to comment on my previous discussion.

The response was so strong that I thought I would collect some of your comments in one place. I hope that this either helps someone to make progress on one of these diseases or to help spread them to others.

Conway was the source many of the popular MD’s, which is probably not too surprising given his wide range of results, that includes many unusual problems.

He once gave the keynote address at SODA. This conference, the Symposium on Discrete Algorithms, is theoretical, but a bit more down to earth than FOCS, for example. Conway’s presentation was a strange and wonderful one—at many levels. The main part of the talk was an impressive demonstration of his Doomsday algorithm. This algorithm allows one to calculate the day of the week from any date by a “simple” rule—Conway himself can do this in realtime. Thus,

\displaystyle  10 \text{ Nov, } 2009 \rightarrow \text{ Tuesday}.

The funniest part of his demonstration was that people would ask dates and get back days of the week, but for many of them we had no idea if Conway was really correct or not. Oh well.

Personally, of his many theorems, his 15-Theorem is one of the neatest:

Theorem: If a positive definite integral quadratic form represents all positive integers up to 15, then it represents all positive integers.

Conway proved this with William Schneeberger in 1993: see this for a overview of the result. Forget how one proves such a theorem, my question is more basic: where do you get the intuition that such a theorem might even be true?

Let’s turn now to the previous comments, with some extra annotation, here and there.

Some Mathematical Diseases (MD)

{ \bullet } Conway’s Thrackle Conjecture: Joseph O’Rourke suggests this one: which he says “ bites me about once every two years{\dots}

I did not know this conjecture. See this for a description of this amazing simple sounding problem. László Lovász has worked on the problem so this disease can affect even one of the best mathematicians in the world.

{ \bullet } Conway’s Game of Life: John Sidles suggest this one and, adds “What a great subject!” He says, To lead off, a wholly benign, utterly useless, and wonderfully enjoyable MD is the study of self-replicating structures in Conway’s Game of Life. The accomplishments of the Life community over the last 39 years are so amazing, that all one can say is {\dots} Golly!

The Game of Life is played on an infinite grid of squares. It is not really a game, it is a zero player game, one starts off by providing the seed — by marking some finite set of squares in the grid. Then the game is entirely deterministic, at each time instance, it evolves using 4 simple rules. Conway’s original question was : Is there a seed which can grow indefinitely? For the answer to this, and a beautiful exposition on the game itself, please see the this article on the game.

{ \bullet } Collatz Problem: Akash Kumar suggests the famous {3x+1} conjecture, which is also called the Collatz Conjecture. He says, “This `seemingly’ toy problem has much to offer as shown by its resistance to attempts at solving it.”

I was introduced to this famous problem, while I was a graduate student, by Albert Meyer. I tried to show that the mapping had no cycles by a modular argument. It failed. Somehow the problem never has appealed to me again. Definitely, a simple to state, but very hard problem.

{ \bullet } Palindromic Number Conjecture: Ted Carroll suggests this one. He says, “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.”

Start with a number and reverse it, then add the two together. Repeat until a palindrome is reached. Does this always happen? See this for an example and more:

  1. {97+79=176}
  2. {176+671=847}
  3. {847+748=1595}
  4. {1595+5951=7546}
  5. {7546+6457=14003}
  6. {14003+30041=44044} which is a palindrome.

Specifically, the number {196} has attracted lots of attention. Starting with {196}, after being iterated to {300} million digits a palindrome is yet to be found. Curiously, in the binary case, there is a very short counterexample that can be shown to never reach a palindrome.

{ \bullet } Goldbach Conjecture: Akash Kumar and Tom both suggest this one. Akash says, “I mean, I find it really amazing that this problem is accessible to people like me with a modest mathematical background and is so profound that it has avoided attacks by best brains.”

Tom says that “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.”

The book titled, “Uncle Petros and Goldbach’s Conjecture” by Apostolos Doxiadis is well written and fun. I would definitely recommend it to you. See this for other examples of Goldbach’s Conjecture appearing in popular culture.

The best known results about the Goldbach Conjecture are:

  1. Every sufficiently large odd number is the sum of three primes. This result is due to Matveevich Vinogradov.
  2. Every sufficiently large even number is the sum of a prime and the product of at most two primes. This result is due to Chen Jingrun. He proved it during the “culture revolution” in 1966, and at first the western mathematicians did not believe that he had achieved this great result. He had.

{ \bullet } Splay Conjecture: Mihai Pătraşcu suggests this one. This conjecture concerns the behavior of certain tree data structures. See this for an introduction to the question. A real computer science question.

{ \bullet } Graceful Tree Conjecture Ibrahim Cahit and Shiva Kintali suggested this one. Cahit explains, Let me give short explanation why GTC is a mathematical disease. Alexander Rosa has identified 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.

Despite of huge efforts very little known for about graceful trees e.g., any tree with {<34} vertices has a graceful labeling and all trees of diameter up to {5} are graceful.

{ \bullet } Riemann Hypothesis: Subrahmanyam Kalyanasundaram suggests this one. He says, “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.”

Two mathematicians from Purdue recently made independent claims, incorrectly, that they have proved the famous theorem. The Riemann has been claimed many times previously by both amateurs and professionals. I asked some experts the other day what is up with this great problem. The answer was there seems to be no progress; the conjecture is still as unreachable as ever.

{ \bullet } 4-Color Theorem: Gilbert Bernstein and Gil Kalai both suggest this one. Gilbert says that “633 configurations is still too many!”

Kalai adds, 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 Lovász 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.

I have outlined an approach that we have suggested for a “human” proof in a previous discussion. Roughly, we show that even proving that every planar cubic graph is approximately {3}-edge colorable, is enough to prove 4CT. Still we are unable to prove that this is true.

{ \bullet } Reconstruction Conjecture: Harrison and Ryan Williams suggest this one. Harrison explains why the conjecture is related to the GI conjecture:

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 Béla Bollobás that almost all graphs are reconstructible, since random graphs don’t allow us to embed large subgraphs into them in more than one way.)

Ryan Williams adds, Allow me to get a little bit infected {\dots} 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?

I have to say that I love this conjecture, but have some immunity—I have never thought about it all.

{ \bullet } The Status of {\zeta(3)}: This was suggested by Ninguem. He says:

Roger Apéry 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. He showed that {\zeta(3)} is not rational. We still don’t know whether {\zeta(3)} is transcendental.

An anonymous commenter adds, The reason people were initially skeptical was that Apéry 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 Apéry’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).

I heard that when Apéry wrote on the board the key identity he needed,

\displaystyle  \zeta(3) = \frac{5}{2} \sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{n^{3} {2n \choose n}}

he gave a very strange answer to “where did this identity come from?” He is alleged to have answered, “they grow in my garden.” Obviously, this did not help make people feel comfortable. The identity is wonderful, the proof is correct, and the values of the zeta function at other odd integers is still a mystery.

{ \bullet } Finding New Crypto-Systems: Chris Peikert suggests this one. He says: 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 {\dots}

  1. What if you don’t believe that these problems are truly hard?
  2. What if someone builds a quantum computer? (What if it happens sooner rather than later?)
  3. What if your device is constrained and can’t handle 2048-bit exponentiations?
  4. What if you need “extra features,” like delegation, revocation, or homomorphisms?
  5. What if you want to be guaranteed security even if some/most of your secret key leaks out via a side channel?
  6. Your standard-issue cryptosystems don’t admit very satisfactory answers to these questions. That’s why we need to look for more {\dots}

I agree with all he says, but I still think the search for new systems has a bit of an MD flavor, however.

{ \bullet } Rudrata Problem: Proaonuiq suggested this one. He says, 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!

I was puzzled by the reference to the “Rudrata disease,” since I had not heard of it before. I found out that it is another name for the Hamilton cycle problem, which is of course NP-complete. A special case of the Hamilton cycle problem is the famous knights tour problem on a chessboard. The pattern of moving a knight on a half-chessboard was presented back in the {9^{th}} century by the Kashmiri poet Rudrata in a Sanskrit poem. Hence the name “Rudrata disease.”

Thus, this open question is about understanding the structure of Hamiltonian cycles on special graphs that arise from groups—Cayley Digraphs. I can see why this could be an MD.

I have to add a comment on a related but completely different topic: how good are you at chess? Moving knights on a chessboard can be used to rate your chess ability. There is a simple test: One places four pawns on the chessboard at certain locations. Your job is to move the knight from one corner of the board to the other as fast as possible. You must visit all squares in a certain order, and can never visit the squares that are occupied by the pawns. You can have the knight visit a square more than once. The time that you take to do this task apparently correlates very well with your chess ability. I was given the test by a friend, and did not do very well.

{ \bullet } Long List of Problems: These were all suggested by Gil Kalai. He says the following: (I have made some minor edits—I hope that I have not changed any content by mistake.)

Let me adopt the MD term under a slight protest and mention some of my favorites MD’s that I spent most time studying.

  1. The rate of error-correcting binary codes (and spherical codes).

    (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 Erdös-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 {(\mathbb{Z}_3)^n} not having three elements that sum to zero. Closely related to Roth’s and Szemerédi’s theorems.

  6. Borsuk’s conjecture.

    I don’t 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 Erdös-Faber-Lovász conjecture. (Jeff settled the EFL conjecture skepticism 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 90′s. At the end I was a coauthor of a 4-author 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, Learnability, even philosophy of science.

  8. Learnability vs rationality

    One tempting “cure” for various diseases, 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.

  10. P{\neq}NP 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 bearing on P{\neq}NP 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.

  11. A little flirt with Poincaré

    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 three, I proved that such a simply connected manifold is a sphere. For dimension three, I could not prove it and it is a very very very special case of the Poincaré 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.

Open Problems

Solve some of these MD’s. Or suggest some others. One of my favorites that is missing is the power of polynomials over composite moduli.

About these ads
49 Comments leave one →
  1. eqnets permalink
    November 12, 2009 4:57 pm

    There is a claimed human proof of 4CT from a few days ago: http://arxiv.org/abs/0911.1587

    I haven’t looked at anything past the abstract though.

    • rjlipton permalink*
      November 12, 2009 5:27 pm

      I just looked at the paper. I am in dark on whether or not true. But the paper is well written and seems to be interesting. I have asked a world expert what’s up and will report back if I learn anything.

    • November 13, 2009 9:18 am

      Yes it is true that the paper is well written and seems to be interesting. I wonder how Bill Tutte could be missed such a straight forward proof from the chromatic polynomial. I don’t know whether the new results on the uniquely 4-colorable (U4C) planar graphs is enough to complete the proof. In all know proofs for the 4CT degree 3 vertices in the maximal planar graph have been discarded. On the other hand any U4C planar graph has at least two vertices with degree three (see Thm 5.10). The proof of the main theorem (Theorem 6.1) is based on the results on the U4C planar graphs and Figure 6.1. Since there are many maximal planar graphs which are not U4C, a possible problem, if the proof is not correct, it would be on characterization of all maximal planar graphs by the Figure 6.1.

      • November 15, 2009 3:32 pm

        Theorem 5.18. Let G be a 4-colorable maximal planar graph with minimum
        degree delta (G)>=  4, then G is not uniquely 4-colorable.

        The maximal 4-colorable planar graph with the minimum number of vertices which is not uniquely 4-colorable graph is not the regular octahedron (Fig. 5.11(a)) but it is the maximal planar graph shown at

        http://www.flickr.com/photos/49058045@N00/2372086534/

        It has been shown that it is not uniquely 4-colorable maximal planar graph in [1].

        [1] I. Cahit, “On unique coloring of planar graphs”, Bulletin of the Institute of Combinatorics and its Applications , to appear.

      • Sniffnoy permalink
        November 15, 2009 4:49 pm

        But, that has three more vertices than the octahedron…

      • Sniffnoy permalink
        November 15, 2009 9:02 pm

        Why is the 3-colorability of the octahedron relevant? Nothing in the proof of Theorem 5.18 seems to rely on non-3-colorability.

      • December 1, 2009 10:08 am

        Theorem 5.18 should be re-written as follows:

        Theorem 5.18′. Let G be a maximal planar graph with minimum
        degree delta (G)>=  4, then G is not uniquely 4-colorable.

        Then, I think the author would be in trouble. Furthermore the proof of the Theorem 5.18 is not working for the maximal planar graph with delta=4 given in my previous post.

      • Sniffnoy permalink
        December 2, 2009 1:18 pm

        But that statement is equivalent; any uniquely 4-colorable graph is 4-colorable, so to say that no 4-colorable maximal planar graph with minimum degree at least 4 is uniquely 4-colorable, is to say that no maximal planar graph with minimum degree at least 4 is uniquely 4 colorable.

        And, so far as I can tell, the proof works fine for that stargate. It has minimum degree 4, so pick a vertex of degree 4 – up to automorphisms of the graph they’re all the same so yay – do the operation to make G_1; G_2 is isomorphic as flipping the graph is an automorphism that takes which vertices are going to be deleted/identified; and G_1 (and hence G_2) is indeed 4-colorable, so this falls under subcase 1.1; and if you actually 4-color it and pull it back to a 4-coloring of G, you’ll see it works; and if you just flip the graph corresponding to if you used G_2 instead, you’ll get the other coloring class. It works perfectly. Subcase 1.1 doesn’t even use the inductive hypothesis at all, so the base case of the induction is irrelevant here!

    • Sniffnoy permalink
      November 14, 2009 1:40 am

      OK, the inductive step of Theorem 4.5 doesn’t make any sense to me. OK, fine, you can make the graph G_1 and all’s well… and you can make G_2, and it’ll be k-colorable… but, it is not at all obvious that the color axes don’t expand at this step! We can connect u to V’_{m+1} while maintaining k-colorability, because the fact that u is in V^c means that there’s some k-coloring that doesn’t color it m+1… but it’s not at all clear that it’s impossible that, say, every k-coloring colors it m+1 or m+2. In which case, once you make that connection, u is not in the new graph’s V^c, and you’ve got a problem on your hands. I thought maybe the proof would basically go through anyway, but once he got to the part with k+1-colorings, it seemed to just stop making any sense – because, well, a k+1-coloring isn’t a k-coloring, so why would it obey any of the stuff we’ve said about k-colorings? And why would u be an axis by itself? Etc… the proof really seems to use that the color axes don’t expand… do you suppose it could work with some sort of strong induction? Or is there something big I’m missing here?

      • November 15, 2009 6:50 pm

        The octahedron is 3-colorable.

      • December 2, 2009 3:14 pm

        1. By letting the maximal planar graph as 4-colorable you implicitly assume that four color theorem is true right from the beginning.

        2. In my example you can obtain only different color classes of G ;
        (a) by shifting cyclically colors of the external triangle vertices e.g., (B,R,G) one step counter clock-wise direction or
        (b) by shifting cyclically colors of the internal triangle vertices e.g., (R,G,B) one step clock-wise direction.

        In the proof color classes have been obtained from one W_4 only.

      • Sniffnoy permalink
        December 2, 2009 8:01 pm

        1. No, you’re not. Either it’s not 4-colorable, in which case it’s not uniquely 4-colorable; or it is 4-colorable, in which case the theorem proves it’s not uniquely 4-colorable. No assumption of 4CT is made anywhere in there.

        2. Yes, and if you compute it out, according to subcase 1.1, which is the only subcase that applies, you’ll see you end up getting both color classes. You can just do the computation, it doesn’t take very long.

      • December 3, 2009 1:17 am

        Thank you. Is the vertex v selected in the maximal planar graph G_(n+1) is the (n+1)th vertex?

      • December 5, 2009 12:43 am

        No, you’re not. Either it’s not 4-colorable , in which case it’s not uniquely 4-colorable; or it is 4-colorable, in which case the theorem proves it’s not uniquely 4-colorable. No assumption of 4CT is made anywhere in there.

        I know the logic is correct but “either it’s not 4-colorable also means there exists an counter-example to the 4CT if it is not 3-colorable”.

  2. November 12, 2009 5:38 pm

    Two of the earliest mathematical (and scientific) diseases are still infecting people today, more than four hundred years later: (1) How hard is to simulate physical systems? (Newton, Leibniz, Lagrange, Hamilton, Feynman …); (2) How hard is it to observe physical systems? (Galileo, Hooke, Leeuwenhoek, von Neumann …)

    Both questions are still unanswered, and the pendulum of opinion swings back and forth between optimism and pessimism—tending mainly toward optimism, yet with many setbacks along the way. The 1990s, for example, were a decade of relative pessimism, with microscopists daunted by problems of radiation damage, and the physicists daunted by the huge dimensionality of Hilbert space.

    Dring 2009 I was privileged to attend five conference that were attended by hundreds of researchers infected by these two passions, and it was very interesting to see that nowadays the pendulum is now swinging decidedly toward optimism.

    At SQuInT and FOMMS, a new generation of simulationists was gaining fresh insights into the structure of both classical and quantum state-spaces, and it was striking that the mathematical language of symplectic and metric geometry was spoken at both conferences. At the 50th ENC and the ACS, there was seemingly no limit to the aspirations of researchers in observing the atomic-scale structures and conformational dynamics of living organisms, via every form of spectroscopy and microscopy. As for the Kavli/Cornell Conference on Molecular Imaging, pretty much everyone attending (including me) was acutely infected by both viruses.

    Upon my return, I put together some hyperlinked seminar notes that attempted to tie together the themes of these five conferences, using mathematical language and expository methods that have been adapted from … where else … math/physics blogs like those of Bob Lipton (thanks!), Bill GASARCH and Lance Fortnow, Terry Tao, Igor Carron, Dave Bacon, Scott Aaronson, Gil Kalai (and many more).

    The point being, that if *anything* is going to unite the goals and methods of these five conferences together, it will be language of modern mathematics. And for spreading this language far and wide, my appreciation and thanks go to all of our planet’s many wonderful mathematical bloggers. IMHO you folks are a great treasure and delight of our modern culture.

    As for those two mathematical diseases … perhaps we can paraphrase both Richard Feynman and Brave Sir Robin (of Monty Python) in foreseeing (or hoping): “We are very lucky to live in an age that discovers the answer to both questions is ‘THAT’S EASY!’” :)

  3. November 12, 2009 5:56 pm

    Mathematicians are somehow nutcases, let’s say I would have a hunch about solving a famous conjecture like Goldbach’s, why the heck would I want to engage in the work needed to solve it (or fail…)?
    What’s the point of answering such a silly question?
    Don’t tell me about publishing!
    You better buy a lottery ticket.
    Could any of you explain the motivations behind those “diseases”?

    • rjlipton permalink*
      November 12, 2009 7:48 pm

      That is a cool question. Perhaps others will answer first, then later I will add my thoughts.

    • November 13, 2009 5:37 pm

      The question about `why answer’ those silly questions is, indeed, a good question! The classic answer to climbing a mountain, for example, is, of course, “Because it’s there.” Which raises the further question about how far mathematicians create this world by acting in it when the world in-which-we-live naturally raises a basic question that, “If a tree falls in a forest with no one around to hear… ” In any case, Polanyi would say insight comes from an exciting intimation of the actually intelligible. Lonergan would add that if we had to reflect on all our insights then we would need two lives; one life to live, and another, longer life to reflect on the life that is lived.

  4. Ashley permalink
    November 12, 2009 6:23 pm

    Here’s one of my favourites, which doesn’t seem to have been mentioned yet: the Hadamard conjecture that there exists a Hadamard matrix in every dimension that’s a multiple of 4. Easy to state, provable by computer for small dimensions, and as yet unsolved: all the hallmarks of a mathematical disease.

  5. Anonymous permalink
    November 12, 2009 7:54 pm

    What’s the point of answering such a silly question?

    Sometimes it’s a matter of technique: nobody cares about the statement of the Goldbach conjecture, but it would be great to understand the distribution of primes well enough to prove it. There are a lot of primes, enough that if they were distributed at random Goldbach would surely be true (it would take a real conspiracy for 2n-p to fail to be prime for each prime p < 2n when n is large). Of course the primes aren't random, but they seem to be pseudo-random in some fairly strong senses. It would be great if we could understand this, and the Goldbach conjecture is a nice benchmark for progress (for example in understanding sieve theory), even though it's admittedly of little importance.

    Sometimes people get interested in problems just because they can't believe something so simple to state could be so hard to resolve. This may be silly, but it's awfully hard to predict how deep something will get. For example, the statement of Fermat's last theorem is pretty pointless, but it turns out to involve far more beautiful mathematics than it deserves. So, for example, even though I see little interest in the thrackle conjecture, I wouldn't rule out the possibility that it's deeper and more interesting than it seems to me.

    Finally, some problems are just interesting to work on, regardless of their consequences or lack thereof. Fun is a perfectly good motivation (and better than most).

    • November 13, 2009 2:59 pm

      Of course the primes aren’t random, but they seem to be pseudo-random in some fairly strong senses. It would be great if we could understand this, and the Goldbach conjecture is a nice benchmark for progress (for example in understanding sieve theory)

      That still feels weird to me, kind of “glorified crosswords” which is (sometimes) justified after the fact by practical uses.

      For example, the statement of Fermat’s last theorem is pretty pointless, but it turns out to involve far more beautiful mathematics than it deserves.

      Ha! ha!
      This raises another nasty question: what are beautiful mathematics?
      I’ll be curious about a formalization of “beauty in mathematics”.

      • Anonymous permalink
        November 14, 2009 1:38 am

        That still feels weird to me, kind of “glorified crosswords” which is (sometimes) justified after the fact by practical uses.

        You’re right that a lot of it is just not practically useful (although of course it’s hard to predict what will someday be essential – the usual example is number theory and its cryptographic applications). Pure mathematics is part art, with a goal of beauty, and part science, with a goal of understanding. It sounds like applied mathematics is more to your taste.

        I’ll be curious about a formalization of “beauty in mathematics”.

        That’s a good question. The Wikipedia article on “Mathematical beauty” is actually a pretty decent start at a description, although it gets a little silly when it starts talking about information theory. I don’t know of a really great account – does anyone else know one?

      • Ian permalink
        November 17, 2009 2:11 am

        There’s actually a mathematical formalization of beauty that can be found in volume 4 of James Newman’s “The World of Mathematics”

        PART XXI: A Mathematical Theory of Art
        Mathematics of Aesthetics
        by GEORGE DAVID BIRKHOFF
        On page 2185

      • rjlipton permalink*
        November 17, 2009 10:13 am

        The whole series is wonderful. I believe it has a great story about the “law” of averages.

  6. adam o permalink
    November 13, 2009 1:11 am

    i didn’t know about the partial results on goldbach’s conjecture. what kind of techniques does Vinogradov’s result use? it’s astonishing that primes could serve as “additive” building blocks for integers in this way.

    • rjlipton permalink*
      November 13, 2009 8:26 am

      I am not an expert on Vinogradov’s work, but here is a very high level view. Consider the primes in the interval [1,N]. He uses exponential sums over primes to count the number of solutions to the equation p+q+r = x where p,q,r are primes. Exponential sums over primes are hard to estimate, and that is part of the brilliance of the method.

      See this for much more details. http://tinyurl.com/ybpvofy

  7. adam o permalink
    November 13, 2009 1:30 am

    re: anonymous above, primes begin “randomly” distributed would suggest that such a condition is unlikely to fail, not that it *never* fails, right?

    • Anonymous permalink
      November 13, 2009 11:50 am

      re: anonymous above, primes begin “randomly” distributed would suggest that such a condition is unlikely to fail, not that it *never* fails, right?

      Yes and no. There’s probably no good reason why it never fails: the history of similar problems suggests that a proof will probably give a conceptual reason why it works for all sufficiently large numbers and then check the small cases by ad hoc or computational arguments.

      However, probabilistic arguments do suggest that there should be no counterexamples, given that there are no small counterexamples. Here’s a very crude version. There are about 2n/log(n) primes up to 2n, and for each such prime p, let’s say 2n-p has a 1/log(n) chance of being prime. Assuming independence (which is a decent approximation) means that there is only a (1-1/log(n))^(2n/log(n)) chance that 2n will be a counterexample. This is less than exp(-2n/log(n)^2), which is tiny. Given that there are no counterexamples up to a million, the expected number of counterexamples is at most the sum of exp(-2n/log(n)^2) over n >= 10^6, which is also tiny. That means the probability that there is even one large counterexample is negligible. Of course, this is nothing like a proof, but it suggests that counterexamples will be not just rare but non-existent.

      • adam o permalink
        November 15, 2009 1:02 am

        thanks!

  8. November 13, 2009 2:11 pm

    Another code/pattern–never before discovered (as far as I can tell)…

    I am not a scientist and have always desired for mathematicians supporting the Bible to be aware of what I’ve stumbled across—that’s why I’m passing along this note…

    The numbered Bible…I’ve made a discovery you will first imagine to be impossible because based on our human understanding it simply cannot be. There’s hundreds of reasons against this but mathematics and numbers don’t lie. As he promised, God has inspired and preserved his word perfectly–nothing has been left to chance.

    THE DISCOVERY: The Bible’s book, chapter and verse numbers in addition to the numbers in the text form a DNA like authentication code that not only proves the Bible is correct but when understood also guides interpretation. Every number in the Bible has themes or meanings behind it and the numbers found associated with book, chapter and verses have themes that not only validate the text is in the right location– but it appears that if you could understand this DNA like structure we might find it translates to totally confirm the original text. There’s more than book chapter and verse numbers to be considered in this authentication code–there are also; cross bible verse numbers; cross book verse numbers; cross bible chapter numbers; like referenced verse numbers and more. Lastly, the numbers 1-10 spell out God’s plan of redemption and every verse reflects different aspects of these plans.

    Sorry, there’s no way to explain this well in a couple of sentences. I’ve studied this more than ten years but understandably people can’t take it in. Consider if you believe these below evidences are coincidence or lead you to want to know more. This is very real and easily provable. How could this be….Jer 32:27 “Behold, I am the LORD, the God of all flesh; is anything too difficult for Me?” (777th chapter)

    EVIDENCE #1 595th and Exact Middle Bible chapter is Ps 117—“Praise the LORD, all nations; Laud Him, all peoples!” shortest and only two verse chapter in the Bible – How did it get at this very unique location? In addition to their center position, these two verses in the Bible’s middle chapter are the 1929 and 1930 verses of Psalms and point by these numbers to another critical Bible separation–that of Old and New Testaments. The last chapter of the OT is #929 and Matthew 1 the first chapter of the NT is the 930th chapter. Note that there are 39 books in the OT so it also relates there. The middle chapter of the Bible is one of hundreds of evidences that tightly tie together the OT and the NT as one God written Bible.

    EVIDENCE #2 John 3, home of John 3:16 in the 1000th chapter – 1000 is said by Josephus to be God’s number of perfection—The most important chapter at the perfect position—How?

    EVIDENCE #3 Psalms 22, Jesus on the cross –the 500th chapter – one of most important chapters with very unique chapter number to be coincidence. 50 is a number for Jubilee and 500 is a factor of 50. Jesus death on the cross is the act of freedom from sins (Jubilee) for all those who believe in him.

    EVIDENCE #4 The 24,000th verse at intersections of 5 references to number 24 about the Day of the Lord — Matthew 24:42 about the Day of the Lord — Mathematically shows is statistically impossible occurrence

    EVIDENCE #5 Revelation 14:4 the Bible’s description of the 144,000 in a verse ref 144 –could be coincidence if there were not such a multitude of other evidences of the Bible’s intelligent designer.

    Discovery at AmazingWord.com

    Norm Patriquin
    Riverside, CA

  9. November 13, 2009 4:24 pm

    Anyone afflicted with the search for an odd perfect number (or a proof that none exist)?

    • November 14, 2009 8:47 pm

      I was also thinking of bringing up the odd perfect number problem. In fact, in my opinion it is probably the oldest famous open problem in number theory if not in whole of number theory.

      I wonder if this problem has not been given the due chase it deserves. I mean being the oldest one should earn it a lot of ‘respect’ even though it might seem useless from point of view of having applications.

  10. proaonuiq permalink
    November 15, 2009 6:39 pm

    I´ve seen the Hamiltonian problem called Rudrata problem first in a paper or lecture notes from Avi Wigderson. After Rudrata, british campanologists where the second i know to have studied the hamiltonian problem in history, from the XVII century to today (this time the Cayley Digraph restricted version, see Knuth´s 4th). Then Hamilton´s with his Icosian Game gave the definite graph theoretic look it has today.

    It could be interesting to comment that besides its historical roots in poetry, “sacred music”, puzzles or mathematical diseases this Hamilton-Rudrata problem restricted to Cayley´s is intensivelly studied today because of its applications to interconnection networks.

  11. Torsten Palm permalink
    November 16, 2009 2:31 pm

    I’m afraid you yourself may be suffering from the MD P = NP.
    Fortunately, this disease has a cure. There is a proof of: P is not equal to NP,
    http://arxiv.org/abs/0810.5056, as I have pointed out before on your blog
    Torsten Palm PERMALINK.
    I wish you a quick and full recovery.

  12. sarcasticus permalink
    November 16, 2009 9:15 pm

    The twin prime conjecture is my mathematical disease.

  13. proaonuiq permalink
    November 17, 2009 10:54 am

    I correct my previous comment. It is not Wigderson but Vazirani the first i´ve seen to give the name of Rudrata problem to the Hamiltonian problem. Sorry for this.

    Also related with this comment and for those interested in HPC the last issue of Top500 is out there. The current Top 1 uses as interconnect topology a 3d-torus (wich is a Cayley graph) with…181000 nodes!!.

    I ignore if the Rudrata problem is used in any way on this engineering system (maybe in some algorithm for collective node communication), but it is my opinion that as well as the bandwidth provided by bus topologies was saturated for networks of more than 30-40 nodes, the one provided by toruses of any dimension will be saturated soon.

  14. DirgeBurble permalink
    November 18, 2009 9:49 am

    Great, love this post and the first MD post too.

    I’ve decided it’s time to come clean about my lost years of chronic 4CT addiction that I’ve been hiding from my family and friends.

    But then… if I ever do find that proper proof maybe I’d just move on to Fermat’s Last Theorem, just for a while – I suspect there’s a stronger link between 4CT and number theory just waiting for us if we can understand it, and not just prove it – and then on to Kepler’s sphere stacking…
    But where was I?
    Oh yes. My wasted years of 4CT addiction…

    One serious question though: how could an amateur like myself (OK I do have a math degree but that doesn’t count) really get validation and acceptance of a genuine proof of one of these MD problems without just being ignored as a crank?
    Not sure there’s an easy or practical answer, but still worth asking.

    Thanks again for this and the other posts, very much appreciated by a hopeless MD sufferer :)

  15. orange juice permalink
    November 18, 2009 1:08 pm

    My favourite MD is “are there are only finitely many Fermat primes ?” .

    Is there a fast (not necessary in P) algorithm for calculating n! mod u ?
    For integers n and u

    Or even: Is n! mod u in NP ?

    • orange juice permalink
      November 18, 2009 8:52 pm

      I’m sorry in case i got it completly wrong, but i just found this blog entry:

      https://rjlipton.wordpress.com/2009/06/09/computing-very-large-sums/

      including the theorem:

      ” Theorem: Given an integer N, the following question is NP-complete: Is there a factor of N in the range [a,b]? ”

      As i understand [a,b] to be static, doesn’t that mean , one could reduce the question to the following question :

      for an integer x > log(b)

      ” does gcd( a! mod N^x , N^x) not equal gcd( b! mod N^x , N^x ) ? ”

      and therefore reduce it in polynomial-time to calculating ( a! mod N^x )
      and ( b! mod N^x ) ?
      Wouldn’t make that calculating ( n! mod u ) np-hard ?

      Again sorry if i got it all wrong as i’m quite the opposite of an expert,
      but the “necessary” in “( not necessary in P ) ” above could possibly be deleted :-)

  16. November 19, 2009 3:12 pm

    Interested in the observation about chess playing ability linked to knight and 4 pawns problem. Could not find anything online re this. Can you point me to some info on using this test?

    Thx!

  17. November 27, 2009 8:29 am

    hey, i just love it to do mathemetics, anything you add in 9 you will get same number and after adding 1 to it and multiplying by 9 and then subtracting 1 again you will get the same number…try this ;)

  18. Craig permalink
    July 22, 2012 12:08 pm

    The Cycle Double Cover Conjecture is a mathematical disease. It’s ranked 4 stars here: http://garden.irmacs.sfu.ca/?q=op/cycle_double_cover_conjecture

    It should be true and there should be an easy proof, yet nobody has presented one so far, as far as I know. Why? What makes it so difficult? (I tried to prove it, but quickly ran into difficulties. So I’m going to give up, as I don’t want to catch this disease.)

Trackbacks

  1. Quick one from Godel’s Lost Letters and P = NP blog « I Study Things
  2. More on Mathematical Diseases « GöDel’s Lost Letter and P=Np « Homemade Halloween Props
  3. Apery for a Third Time « OU Math Club
  4. The Lonely Runner Conjecture « Gödel’s Lost Letter and P=NP
  5. Isomorphism Is Where It’s At | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,244 other followers