text:
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 ${A}$ and ${B}$ and ${C}$ had really been co-linear it would have worked. Perhaps the author could move ${\dots}$

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!

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.

1. 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.
2. 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.
3. 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.

${\bullet }$ Graph Isomorphism: This is the classic question of whether or not there is a polynomial time algorithm that can tell if two graphs are isomorphic. The problem seems so easy, but it has resisted all attempts so far. I admit to being mildly infected by this MD: in the 1970’s I worked on GI for special classes of graphs using a method I called the beacon set method.

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.

${\bullet }$ Group Isomorphism: This problem is not as well known as the GI problem. The question is given two finite groups of size ${n}$ are they isomorphic? The key is that the groups are presented by their multiplication tables. The best known result is that isomorphism can be done in time ${n^{\log n +O(1)}}$. This result is due to Zeke Zalcstein and myself and independently Bob Tarjan. It is quite a simple observation based on the fact that groups always have generator sets of cardinality at most ${\log n}$.

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 ${p}$-groups. If you can make progress on such groups, I believe that the general case might yield. In any event ${p}$-groups seem to be quite hard.

${\bullet }$ Graph Reconstruction: This is a famous problem due to Stanislaw Ulam. The conjecture is that the vertex deleted subgraphs of a graph determine the graph up to isomorphism, provided it has at least ${3}$ vertices. It is one of the best known problems in graph theory, and is one of the original diseases that Harary discussed.

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.

${\bullet }$ Jacobian Conjecture: This is a famous problem about when a polynomial map has an inverse. Suppose that we consider the map that sends a pair of complex numbers ${(x,y)}$ to ${(p(x,y),q(x,y))}$ where ${p(x,y)}$ and ${q(x,y)}$ are both integer polynomials. The conjecture is that the mapping is 1-1 if and only if the mapping is locally 1-1. The reason it is called the Jacobian Conjecture is that the map is locally 1-1 if and only if the determinant of the matrix

$\displaystyle \left( {\begin{array}{cc} p_{x}(x,y) & q_{x}(x,y) \\ p_{y}(x,y) & q_{y}(x,y) \\ \end{array} } \right)$

is a non-zero constant. Note, ${p_{x}(x,y)}$ is the partial derivative of the polynomial with respect to ${x}$. The above matrix is called the Jacobian of the map.

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.

${\bullet }$ Crypto-Systems: This is the quest to create new public key crypto-systems. While factoring, discrete logarithm, and elliptic curves seem to be fine existing public key systems, there is a constant interest in creating new ones that are based on other assumptions.

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.

${\bullet }$ P=NP: You all know this problem. See this for a nice list of attempts over the years to resolve the problem. Thanks to Gerhard Woeginger for maintaining the list.

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.

1. November 4, 2009 7:40 pm

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! 🙂

2. November 4, 2009 9:02 pm

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.

3. November 4, 2009 11:59 pm

I think my favorite bug is the 4-color conjecture. 633 configurations is still too many!

November 5, 2009 1:32 am

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.

November 5, 2009 8:02 am

Yes. It also has been claimed a few times. One claim made the front page of the New York Times.

5. November 5, 2009 4:32 am

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

6. November 5, 2009 5:30 am

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

November 5, 2009 7:53 am

Your right. How can this be open? It seems so simple. Yet it is very hard. Thanks for the details.

• November 5, 2009 11:25 am

Graceful Tree Conjecture is my favorite too. Read my earlier post here.

• November 5, 2009 1:04 pm

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:

• November 7, 2009 12:41 am

If one day the graceful tree conjecture will be settled, there is even stronger one!

See a letter from Donald E. Knuth at:

7. November 5, 2009 8:47 am

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:

November 5, 2009 10:38 am

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 .

November 5, 2009 4:26 pm

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.

November 5, 2009 5:21 pm

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.

November 6, 2009 8:10 am

Never said was a crank. I did understand that he was in another area. Sorry if I got it wrong.

November 5, 2009 11:16 pm

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

November 5, 2009 10:55 am

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.

10. November 5, 2009 11:43 am

Conway’s Thrackle conjecture bites me about once every two years… 🙂

November 5, 2009 6:34 pm

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?

12. November 5, 2009 8:34 pm

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…

13. November 6, 2009 5:13 am

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.

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.

14. November 6, 2009 5:21 am

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.

• November 6, 2009 12:15 pm

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?

• November 7, 2009 11:05 am

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”. https://rjlipton.wordpress.com/2009/03/28/erds-and-the-quantum-method/)

• December 22, 2009 1:42 am

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.

November 6, 2009 12:12 pm

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.

16. November 6, 2009 1:51 pm

The Splay Conjecture and the Sunflower Lemma are major ones.

17. November 8, 2009 8:47 pm

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

November 10, 2009 3:12 am

“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.)

November 10, 2009 3:21 am

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?

20. November 10, 2009 7:46 pm

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

November 10, 2009 9:51 pm

Even if you are him, it is still a great book. Thanks for pointer to new name.

November 12, 2009 12:21 pm

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.

November 12, 2009 4:52 pm

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.

23. November 16, 2009 12:46 am

The Frey-Mazur conjecture is a personal MD (see conjecture 3 of this paper: http://www.springerlink.com/content/k251nu0703j75441/fulltext.pdf).

24. November 16, 2009 4:19 am

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.

November 16, 2009 9:01 am

Great example. What is the best known on this conjecture? Do you know?

• November 16, 2009 6:13 pm

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.

December 9, 2009 5:43 pm

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.

December 29, 2009 9:51 am

There’s one mathematical disease that I am missing here: (video) compression!
Just Google “Jan Sloot” to see what I mean.

November 2, 2010 10:02 pm

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

May 23, 2012 12:46 am

Have you seen a direct proof of n=4 or 5? Do you have a reference?

May 29, 2012 5:07 am

No I do not have seen proof, it seems doable by computer using brute force for n=4 ?

• November 28, 2013 1:59 am

This can’t be the correct formulation, since the rows are a basis iff the columns are a basis…

27. November 28, 2013 1:54 am

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.

28. July 16, 2014 6:51 pm

Collatz conjecture = cocaine

September 15, 2014 5:19 am

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?

30. February 28, 2016 11:58 am

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


text:
# I'm having trouble finding the integral using u-substitution.

by nerdy_hottie
Tags: calculus, integrals, inverse trig, mathematics, u-substitution
 P: 19 1. The problem statement, all variables and given/known data I have to integrate using u-substitution (probably). Ex. 1 Integrate (sin^4x)/(cos^6x)dx 2. Integrate (2x)/(sqrt(e^(2x^2)-1))dx 3. Integrate (cos^-1x)/(sqrt(1-x^2))dx Thank you ! 2. Relevant equations I do not want the solutions. I just need to be pointed in the right direction (i.e. I need you to help me start off) **It should be noted that I am doing a calculus II course (Integral Calc, mostly) in university, so it's not very advanced integrals that I'm doing. Basically what I know is how to integrate using u-substitution, and I know the integrals for the inverse trig functions (which is supposed to be relevant to examples 2 & 3), and that's what information I have to work with. **It should also be noted that I may just not know how to rewrite the equations before I can integrate them. I have trouble 'seeing through' the equation and automatically knowing which way I'm going to solve it. 3. The attempt at a solution Ex. 1 I tried rewriting the equation using trig identities, e.g. (1-cos(x))/(1-sin(x))^3. I found this got me nowhere. I also tried rewriting it is (sin^4)(x)/(cos^4)(x)*1/cos(x), and rewriting and rewriting until I ended up with a big mess, so that got me nowhere as well. 2. Here's my dilemma: -if I substitute e^2x for u, I end up needing an e to the power in my numerator, so that doesn't work out. -if I instead substitute 2x^2 for u, I end up with the e to the power of u on the bottom and I don't have a formula for that. 3. I have no ideas on this one.
Mentor
P: 19,753
 Quote by nerdy_hottie 1. The problem statement, all variables and given/known data I have to integrate using u-substitution (probably). Ex. 1 Integrate (sin^4x)/(cos^6x)dx 2. Integrate (2x)/(sqrt(e^(2x^2)-1))dx 3. Integrate (cos^-1x)/(sqrt(1-x^2))dx Thank you ! 2. Relevant equations I do not want the solutions. I just need to be pointed in the right direction (i.e. I need you to help me start off) **It should be noted that I am doing a calculus II course (Integral Calc, mostly) in university, so it's not very advanced integrals that I'm doing. Basically what I know is how to integrate using u-substitution, and I know the integrals for the inverse trig functions (which is supposed to be relevant to examples 2 & 3), and that's what information I have to work with. **It should also be noted that I may just not know how to rewrite the equations before I can integrate them. I have trouble 'seeing through' the equation and automatically knowing which way I'm going to solve it. 3. The attempt at a solution Ex. 1 I tried rewriting the equation using trig identities, e.g. (1-cos(x))/(1-sin(x))^3. I found this got me nowhere. I also tried rewriting it is (sin^4)(x)/(cos^4)(x)*1/cos(x), and rewriting and rewriting until I ended up with a big mess, so that got me nowhere as well.
This is the right approach, but you have an error. Your integrand is equal to tan4(x)sec2(x). That should suggest a pretty obvious substitution.
 Quote by nerdy_hottie 2. Here's my dilemma: -if I substitute e^2x for u, I end up needing an e to the power in my numerator, so that doesn't work out. -if I instead substitute 2x^2 for u, I end up with the e to the power of u on the bottom and I don't have a formula for that.
 Quote by nerdy_hottie 3. I have no ideas on this one.
If u = cos-1(x), what is du?

BTW, welcome to Physics Forums!
 HW Helper Thanks P: 4,303 For example 2, rewrite the integrand to remove the sqrt in the denominator, that is, express 1/sqrt(e^(2*x^2)-1) using the appropriate exponent. After doing this, see if the factor 2x would be useful in integration by parts.
HW Helper
Thanks
P: 4,303

## I'm having trouble finding the integral using u-substitution.

 Quote by SteamKing For example 2, rewrite the integrand to remove the sqrt in the denominator, that is, express 1/sqrt(e^(2*x^2)-1) using the appropriate exponent. After doing this, see if the factor 2x would be useful in integration by parts.
Check that last suggestion.

See if the factor 2x would be useful in a u-substitution integration.
 P: 19 Thanks all, but I still cannot find the solution to the second example. I let u=2x, so du=2dx Since the x is is still in the numerator, I say that also, x=u/2 So I fill this in and I get Integral of (u/2)(1/(sqrt((e^u)-1))du I have not yet learned to do integration by parts, by the way.
 PF Patron HW Helper Sci Advisor Thanks Emeritus P: 10,923 The argument of the exponential has an x2 in it, right? So try u=x2 to try simplify that a bit. That's where you find the factor of 2x comes in handy. Then you might try a substitution like v=eu and see where that gets you. A lot of this you figure out by trial and error. As you do more problems, you'll start to get a feel for what works and what doesn't.

 Related Discussions Calculus & Beyond Homework 2 Calculus & Beyond Homework 3 Calculus & Beyond Homework 1 Calculus & Beyond Homework 2 Introductory Physics Homework 4

format: plain


text:
# Why did the Twilight Zone not feature a more diverse cast?

Movies & TV Asked by user66823 on January 30, 2021

I’m watching re-runs of Twilight Zone and I was wondering why most of the cast the predominantly white?

Rod Serling liked to write episodes about social issues, so it’s surprising that Twilight Zone didn’t feature more non white actors. The only episodes I found that featured non white actors were I Am the Night—Color Me Black with Ivan Dixon and The Encounter with George Takei.

In a Library of Congress interview from 1968, (named, aptly, "A Conversation with Rod Serling"12), Rod Serling talks about addressing issues indirectly:

You may have to tell them a story of prejudice in parable form, in which they may step aside as third persons and cluck and say, "<tsk tsk tsk> How awful we treat our minority groups", but at least they know that it's an evil, and they will recognize it as such, and by osmosis or some incredible process, will somewhere along the line be faced with a situation in which they too may have to exorcise [exercise?] their prejudice, and be conscious of it as an evil. Now on "Twilight Zone", for example, done during just as timorous a time as any other time, we made a comment on prejudice, on conformity, on intolerance, on censorship, but it's easy to do it when you're talking about "Buck Rogers isn't allowed to write his memoirs in the way he wants to write them, so he puts on his backpack, his rocket-pack, and he zooms over to the publisher." And they applaud and laugh and think, "How exciting and interesting." Now, it may well be that the inner message may never get through, but I think peripherally it does get through.

While this approach wouldn't preclude hiring people of color to fill various (non-stereotypical) roles in an effort to combat stereotypes (as was done in "Star Trek"), some of Rod's other experiences in the television industry may have turned him away from doing this. The Library of Congress interviewer mentions Serling's teleplay "A Town Has Turned to Dust", which, along with "Noon on Doomsday" (both were inspired by the lynching of Emmett Till), had to be rewritten due to network censorship. "A Town Has Turned to Dust" was originally about the lynching of a black character, who was changed to a Mexican under pressure from the network. "Noon on Doomsday" (the first to be written and produced) was about the lynching of a Jewish man, but network censors wouldn't even allow that3, or for it to be set in the South.

If a story was perceived to be about racial injustice, it was going to be censored, and hiring people of color might lead to this perception. Even without the perception, there were groups who would boycott shows just for featuring a black actor in a non-subservient role. Admittedly, both the stories inspired by the Till case are primarily about racism (rather than just featuring people of color in non-stereotypical roles), but the network push-back, along with other encounters, may have taught Serling to self-censor at certain times, and to approach some matters obliquely. It was his battles with censorship that led Serling to turn to speculative fiction, directly resulting in "The Twilight Zone". Which actors got hired for which parts may have been a case of Serling picking his battles.

Another "Twilight Zone" episode with non-white actors to add to the list: "A Quality of Mercy", which had Dale Ishimoto and Jerry Fujikawa (born Hatsuo Fujikawa), both of Japanese descent4.

1 Serling was uncomfortable with the title.
2 The first mention of race issues starts at 10:15.
3 In an interview, Serling insinuated a connection to the Till case, and The White Citizens Council responded by threatening a boycott.
4 Both were also interned in camps during WWII, and subsequently volunteered for the army.

Answered by outis on January 30, 2021

You have to A) cater to your audience and B) the demographics were different then. A vast majority of the TV audience back then were while. You have to remember that TV's were rather expensive back in those days. The least expensive TV cost almost $200 and in those days$200 was almost a month salary and considering how tough blacks had it in those days one would guess that not a lot of black households had TV's. Hell, there were a lot of white households that didn't have TV's. Remember Back to the Future when Lorraine's family were excited to get their first TV? But there were black actors on Twilight Zone. 2 of whom ended up being prominent actors in the 60's; Ivan Dixon who starred on Hogan's Hero's and Greg Morris who starred on Mission Impossible.

Answered by Studa Baker on January 30, 2021

I'm not going to make this too political, but it took a lot of people a lot of effort to change these old perceptions, and not just in Hollywood, in all walks of life.

Twilight Zone was first broadcast in 1959.

The world was a significantly different place back then. Hollywood wasn't alone in excluding non-white actors [and technicians, writers, producers] from their domain.

The word 'diversity' was more usually applied to people who could 'sing and dance' and had nothing to do with ethnic diversity.

In 1959, racial stereotypes were the "norm", not the exception.
Black people rolled their eyes and said "Yesm".
Asians all had pigtails and did the laundry.
Irish all said "Top 'o the mornin'"
Jews were all bankers, jewellers or tailors.
[I could go on, but it's already making me itch]
This wasn't just a 'colour' thing, it was 'anybody who is not exactly like we are'. These days we find this all risible if not actually horrendous [depends on perspective, perhaps].

Non-white actors in leading roles were not completely unknown, but they were very rare.

The first black actor to win an Oscar for a leading role[1] was Sidney Poitier, in 1963, for his part as the itinerant worker Homer Smith in Lilies of the Field (though he was first nominated in 1958.) This was a big deal and wasn't to be repeated until Denzel Washington and Halle Berry both won in 2001

By the late 60's shows such as Star Trek were starting to push the boundaries. Star Trek did it by being "not of this time" and so could more easily portray a future where "things were different".

Though I don't know those specific Twilight Zone episodes, I think that they featured non-white actors in 1964 was actually a good first step on the way. Every journey begins with one step, no matter how small.

Rod Serling - though trying to push boundaries - also had to deal with the current networks and how they wanted to appeal to their current audiences, so was very possibly more restrained than a modern writer. From your Wikipedia link on The Encounter:

First broadcast on May 1, 1964, its racial overtones caused it to be withheld from syndication in the U.S.

One might imagine Charlie Brooker's Black Mirror may have fewer restrictions to his imagination in this day and age.

[1] I must also mention Hattie McDaniel, as the first ever black actor to be nominated - and to win - any Oscar; though the part she played to win that accolade for Best Supporting Actress was unfortunately also an eye-rolling 'yesm' part. Though potentially valid during the time the plot is set, not something anyone could be particularly proud of in this day and age (other than, of course, she did it, she won, she deserves the honour for doing it)*.
Contrast to the significantly more enlightened Django Unchained

*It's difficult to approve of the actress whilst disapproving of the portrayal that was 'of its time' and express that to a modern audience without sounding like a complete †[email protected]† etc!!

Answered by Tetsujin on January 30, 2021

## Related Questions

### Why did Nancy forgive Steve even after he called her a slut?

1  Asked on November 30, 2020 by dhanishtha-ghosh

### How was Ben Rickert able to secure an ISDA agreement?

1  Asked on November 25, 2020 by nipponese

### How were the video screens in Chaplin’s Modern Times filmed?

0  Asked on November 1, 2020 by vsz

### Switch in *The Matrix* – Two Actors?

2  Asked on October 22, 2020 by catija

### How do they record the voice track in heavy rain scenes?

1  Asked on October 7, 2020 by suckrates

### What does it mean, “on a three”?

1  Asked on August 21, 2020 by nelson-blake

### Why is Tom James consider VP-elect at the end of Veep Season 4

0  Asked on August 17, 2020 by dspyz

### What is the timeline of The Lorax? Why don’t the older townspeople remember the trees?

3  Asked on July 27, 2020 by alvaro-montoro


text:
P value and Adj. P value showing N/A
1
0
Entering edit mode
Yihan • 0
@8e03f28b
Last seen 20 days ago
United States

I was trying to identify the genes that are the most different between WT and KI mice based on log 2 fold change. I'm wondering why for some of them it shows NA for p value and p.adj value?

dds <- DESeq(ddsHTSeq_filtered)

# By genotype for med KI vs WT (9w)
res_9w_med_genotype <- results(dds, contrast=c("group","9wWTmed","9wKImed"))
res_9w_med_genotype[order(abs(res_9w_med_genotype\$log2FoldChange), decreasing = TRUE),]

DESeq2 • 162 views
2
Entering edit mode

http://bioconductor.org/packages/devel/bioc/vignettes/DESeq2/inst/doc/DESeq2.html#why-are-some-p-values-set-to-na

As Mike says, you can be almost certain that most DESeq2 question, unless it is some super special case, is explained in the FAQs.

2
Entering edit mode
@mikelove
Last seen 4 hours ago
United States

This is explained in the DESeq2 vignette.