- Fermat's last theorem should have been called a conjecture. It was proven. I don't think any serious mathematician ever thought it was false.
- Baudet's' Conjecture is now VDW's Theorem.
- The Modell Conjecture is now Faltings Theorem.
- I could list more, so could you.
- Hilbert's 10th problem asked for an algorithm that would, given a poly in many variables over Z, determine if it has a Diophantine solution. We now know this cannot be done. While this may have surprised Hilbert, he was aware of this sort of thing happening. See the preface to his problems, or better see his entire address here.
- Same with the Ind of CH from ZFC. Hilbert thought it was true. More to the point, Hilbert certainly thought it had an answer. Now we know that it does not. Or at least that its ind of ZFC.
- NL=coNL surprised alot of people.
- In 1986 most people thought that P\ne BPP (hard to believe!). One notable exception was Mike Sipser. Now most people think that P=BPP. Of course, not resolved yet.
I doubt that any of the Clay problems will end up being false. I doubt that any serious mathematician thinks that any will end up being false. That might be self-correcting: if someone did we would label him (perhaps unfairly) non-serious.
There are some examples, although not nearly as dramatic as the Clay problems would be. The longest-standing one is probably Euler's generalization of Fermat's last theorem (that a_1^n+a_2^n+...+a_(n-1)^n = b^n has no positive integer solutions.) Another one is the Mertens conjecture that implies the Riemann hypothesis. A metamathematical example: the elementary proof of the prime number theorem.
ReplyDeleteKeller's Cube-Tiling Conjecture Is False In High Dimensions (1992)
ReplyDeleteby Jeffrey C. Lagarias, Peter W. Shor
Bull. Amer. Math. Soc
http://www.research.att.com/~shor/papers/Keller.ps
Not many complexity theorists now believe the Berman-Hartmanis isomorphism conjecture, thanks to developments in cryptography.
The other one, of course, is the conjecture that the polynomial-time hierarchy is infinite... just waiting to be disproved :-)
Well, at least many famous conjectures had to be amended for them to stand a chance of being true. For instance, there is Grothendieck's famous (short) paper on why "Hodge's general conjecture is false for trivial reasons".
ReplyDeleteFor conjectures closer to TCS,
I know of at least one well-known and very believable conjecture in discrete geometry (the isotopy conjecture for order types (Arnold ?)) which turned out to be wildly false. It said that for every n, given two labelled configurations of n points in the plane, such that the orientations of every triplet is the same for both, it is possible to move continuously the first configuration to the second maintaining the orientation of every triplet on the way.
Euclid conjectured that the parallel postulate could be proven from the other axioms of geometry. People tried to prove it for literally thousands of years until it was shown to be independent.
ReplyDeleteAlthough the result here is the same as for the Continuum Hypothesis, this is definitely a "clean" story, since the original question was about independence.
Kahn and Kalai disproving the Borsuk's Conjecture seems to fit the bill.
ReplyDeletePerhaps the Khot-Vishnoi(-Devanur-Saket) disproof of the Goemans-Linial conjecture, though I don't know how strongly that was believed.
Euler's disproof of Fermat's Conjecture that 2^2^n+1 is always prime?
To contribute another example, Hardy and Littlewood made two conjectures about the distribution of primes: (1) the number of primes in an interval of length n is maximized by [0,n] and (2) any prime pattern that isn't impossible for modular reasons actually occurs and with a specific asymptotic density. Turns out they are contradictory.
ReplyDeleteRegarding the Clay problems: Selberg was said to have doubted the Riemann hypothesis. I know high-profile number theorists that doubt the generalized Riemann hypothesis.
NL=coNL surprised alot of people
ReplyDeleteNL=coNL was a surprise but not quite the surprise it would have been a year earlier. The first surprise was the earlier paper by Lange, Jenner, and Kirsig that the logspace hierarchy collapsed at the second level. That paper certainly heavily influenced Immerman's proof. Lange, Jenner, and Kirsig do not always get their due credit in the story.
I'd say conjectures in Fourier analysis go about 50-50.
ReplyDeleteThe disc multiplier conjecture turned was proved false by C. Fefferman in the early 70's.
Most analysts thought L^2 pointwise convergence was false, until proved by Carleson in 1966.
The Maximal Bochner-Reisz Conjecture was proved false by Tao in the mid 90's.
Google turns up:
ReplyDeletehttp://mathworld.wolfram.com/MertensConjecture.html
A more controversial one:
http://en.wikipedia.org/wiki/Skewes'_number
Another one, even if the conjecture was disproven a short time after being stated, is the Wang's conjecture (which states that any set of Wang tiles which can tile the plane can tile it periodically).
ReplyDeleteI think it was a kind of surprise. But OK, it was disproven just 5 years after Wang's paper.
The existence of continuous functions that are not differentable in any point. Probably, at the time most people believed that any continuous function is differentable almost everywhere, if we throw away some small set of points. This point of view prevailed for a long period of time until "frustrating" example due to Weierstrass. But, of course, this was not an explicitly stated conjecture...
ReplyDeleteDoes Barrington's theorem about 5-way branching programs count? Bob Lipton blogged about it fairly recently.
ReplyDeleteWas it explicitely conjectured
ReplyDeletethat IP does not contain co-NP
(and higher classes)? It was
definitely surprising.
Oh! here is a famous one in model theory:
ReplyDeleteHrushovski's construction refuting Lachlan and Zilber's conjectures.
http://en.wikipedia.org/wiki/Hrushovski_construction
There plenty of examples in which practical engineering problems proved considerably easier than the consensus option.
ReplyDeleteFast algorithms for discrete Fourier transforms came as a surprise to many, as did Dantzig's simplex algorithm.
In recent years, compressive sampling methods have confounded conventional wisdom ... this story is well-told in essays by Candes and Tao, and by Donoho, in the December 2008 IEEE Information Theory Society Newsletter.
Emerging surprises: classical methods for simulating large-scale quantum system dynamics already perform much better than (say) Feynman's generation foresaw, and the pace of improvement is itself accelerating.
Future surprises: efficient integer factoring would surprise many people, but by no means everyone.
The adjacency of GASARCH's post about widely embraced conjectures, with Lance's post about taking his daughter miniature golfing, points out one more widely embraced conjecture that perhaps many parents contemplate: "Our shared global civilization and planetary ecology will endure."
ReplyDeleteCarlton Caves' preprint (http://arxiv.org/abs/0806.3538v1) gives a readable summary of the purely probabilistic arguments for this conjecture, both pro and con.
From a historical point of view, I think many readers of this column will be familiar with Jared Diamond's writings on this conjecture.
Obviously, this particular conjecture is not likely to be resolved by reasoning from mathematical axioms ... still it undeniably has a very substantial mathematical component.
Just for the record, what is the status of the unique games conjecture? Is it currently widely-believed to be true? False? no general agreement?
ReplyDeleteSuch a dramatic result was last year's counterexample [Nature Physics, March 09] by Hastings showing that "the additivity conjectures" from quantum information theory were all false. A huge community of people, including operator theorists, physicists, information theorists and computer scientists, had been working on the problem. However,his counterexamples were by random selection and led to very tiny violations of additivity for extremely large channels and important questions still remain. How big can the violations be? Can a general formula for the classical capacity of quantum channels be given? Is the classical capacity itself additive?
ReplyDeleteAn analogous questions to the latter about quantum channels was shown to be false a few months before Hastings's counterexample appeared, when the quantum capacity was shown to not be additive by Smith and Yard [Science, Sept. 08]. Some time later, nonadditivity of the private capacity was then demonstrated by Li, Winter, Zou and Guo.
Of the above, the work by Hastings was the most high-profile, since the greatest number of people had been working on / were aware of the problem. The community seemed largely split on it, in part because Hastings completed a program initiated by Hayden and Winter to provide counterexamples. Their approach came close to generating counterexamples, but fell short, which some saw as a sign that additivity was "trying" really hard to be true, while others (correctly) believed that their methods just needed strengthening (as Hastings did).
A very good and thoroughly documented example of "a longstanding conjecture that ended up being false" can be found on the American Institute of Physics' web site on global warming:
ReplyDeletehttp://www.aip.org/history/climate/co2.htm
The conjecture was an important one: Anthropogenic increases in CO2 concentration exert minimal effect on Earth's climate.
The evidence was (too-simple) radiation transport experiments supported by (too-simple) mathematical models. The AIP web site thoroughly documents these errors.
The error was embraced by the the scientific community (roughly) from Knut Ångström's CO2 absorption experiments of 1900, to Lewis Kaplan layer-based modeling of 1952.
It is interesting that these errors are still publicly embraced today, mainly by ideology-driven far-right web sites, and also by organizations funded by the carbon industry.
Maybe not "dramatic" (but at least as dramatic as some of the other examples here).
ReplyDeleteBarry Cooper is a recursion-theorist from Leeds University who has solved not one but at least two relevant, long-standing conjectures related to the semilattice of Turing degrees. In both cases, in the surprising direction.
One was already asked by Post, if I remember correctly: prove that the first-order theory of the comparison of the Turing degrees is insufficient to define the jump; of course, anyone can "see" that if your expression language is just the T-reduction you cannot speak about halting machines. However, Barry proved in the late 80's that it IS possible to define the jump in such a limited language.
Also, it was widely expected that the semilattice of the Turing degrees was rigid; but Barry found in the mid or late 90's a nontrivial automorphism.
(I would welcome that someone more knowledgeable confirms or corrects my descriptions.)
José L Balcázar
While Cooper announced a sketch of the proof of the definability of the jump there were some holes that weren't filled in really satisfactorily until Slaman and Shore's proof.
ReplyDeleteTo my knowledge the existence of a nontrivial automorphism of the Turing degrees is still regarded as an open question with the best widely accepted result last time I looked being (by Slaman and Woodin I believe) that any such automorphism must be the identity above...0'' I believe. I think Cooper made a significant advance (showing it had to be the identity above 0'''??) but didn't settle the whole question. He may have claimed the existence of an automorphism but until there is a detailed proof it's not really settled.
In any case while people surely had intuitions one way or another about these problems they never rose to the level of 'the community would be stunned if the Turing degrees weren't rigid'
...we must know, we will know!
ReplyDelete