Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I just came back from my Number Theory course, and during the lecture there was mention of the Collatz Conjecture.

I'm sure that everyone here is familiar with it; it describes an operation on a natural number -- n/2 if it is even, 3n+1 if it is odd.

The conjecture states that if this operation is repeated, all numbers will eventually wind up at 1 (or rather, in an infinite loop of 1-4-2-1-4-2-1).

I fired up Python and ran a quick test on this for all numbers up to 5.76 × 10^18 (using the powers of cloud computing and dynamic programming magic). Which is millions of millions of millions. And all of them eventually ended up at 1.

Surely I am close to testing every natural number? How many natural numbers could there be? Surely not much more than millions of millions of millions. (I kid)

I explained this to my friend, who told me, "Why would numbers suddenly get different at a certain point? Wouldn't they all be expected to behave the same?"

To which I said, "No, you are wrong! In fact I am sure there are many conjectures which have been disproved by counterexamples that are extremely large!"

And he said, "It is my conjecture that there are none! (and if any, they are rare)"

Please help me, smart math people. Can you provide a counterexample to his conjecture? Perhaps, more convincingly, several? I've only managed to find one! (Polya's) One, out of the many thousands (I presume) of conjectures. It's also one that is hard to explain the finer points to the layman. Are there any more famous or accessible examples?

share|improve this question
33  
You can give your friend this 'conjecture': All integers are smaller than n. Counter example n. Here n = something extremely large. ;) –  Chao Xu Jul 22 '10 at 21:07
1  
Did you really test up to 5.76 × 10^18, or are you quoting someone else's result? I'm assuming you're joking about computing it yourself, but, if you did, I'd like to know how you did it. I've done some interesting things w/ cloud computing, but never THAT interesting. –  barrycarter Apr 3 '11 at 14:05
2  
@barrycarter heh, this question was posted during the site's beta phase as my attempt to seed the site with more questions, and I wasn't being too serious. –  Justin L. Apr 4 '11 at 2:56
1  
For Reference: mathoverflow.net/questions/15444/… –  JavaMan Aug 29 '11 at 22:07
3  
You may have been joking about doing though 10^18 via cloud computing; but an ongoing BOINC project has done an exhaustive search to 2.3*10^21. boinc.thesonntags.com/collatz/high_steppers.php –  Dan Neely Feb 21 '12 at 14:00
add comment

12 Answers

up vote 29 down vote accepted

Another example: Euler's sum of powers conjecture, a generalization of Fermat's Last Theorem. It states:
If the equation $\sum_{i=1}^kx_i^n=z^n$ has a solution in positive integers, then n ≤ k (unless k=1). Fermat's Last Theorem is the k=2 case of this conjecture.

A counterexample for n = 5 was found in 1966: it's
$$ 61917364224=27^5+84^5+110^5+133^5=144^5 $$ The smallest counterexample for n = 4 was found in 1988:
$$ 31858749840007945920321 = 95800^4+217519^4+414560^4=422481^4 $$ This example used to be even more useful in the days before FLT was proved, as an answer to the question "Why do we need to prove FLT if it has been verified for thousands of numbers?" :-)

share|improve this answer
    
This one I like a lot, and it's pretty simple to explain :) I also appreciate the historical background offered. –  Justin L. Jul 29 '10 at 5:20
    
On the other hand the numbers involved in the above examples are fairly small (compared to the millions of millions of millions). I find Justin's question interesting and I'm not sure I'm so convinced by those counterexamples which wouldn't take long to find using today's technology. –  David Kohler Mar 31 '11 at 16:47
1  
@David: 31858749840007945920321 is pretty large, and it took until 1988. Naïvely speaking, you have to try all triples of fourth powers, with the largest number going up to 414560. Finding this counterexample, even with today's technology, would take more than a year on a desktop computer. (Of course, there are presumably number-theoretic insights which make it faster to find counterexamples by computer, but as I saw it, the whole point of the question was that the "simply try as many numbers as you can on a computer" approach need not give the right answer.) –  ShreevatsaR May 10 '11 at 7:19
    
@ShreevatsaR: I edited as this question has just been bumped up anyway. –  George Lowther Aug 29 '11 at 23:03
    
@George: Thanks! I've deleted my old comment pointing out the error, since it's not needed now. –  ShreevatsaR Aug 30 '11 at 1:32
show 1 more comment

The wikipedia article on the Collatz conjecture gives these three examples of conjectures that were disproved with large numbers:

Polya conjecture.

Mertens conjecture.

Skewes number.

share|improve this answer
add comment

I heard this story from Professor Estie Arkin at Stony Brook (sorry, I don't know what conjecture she was talking about):

For weeks we tried to prove the conjecture (without success) while we left a computer running looking for counter-examples. One morning we came in to find the computer screen flashing: "Counter-example found". We all thought for sure that there must have been a bug in the algorithm, but sure enough, it was a valid counter-example.

I tell this story to my students to emphasize that "proof by lack of counter-example" is not a proof at all!


[Edit] Here was the response from Estie:

It is mentioned in our paper:
Hamiltonian Triangulations for Fast Rendering
E.M. Arkin, M. Held, J.S.B. Mitchell, S.S. Skiena (1994). Algorithms -- ESA'94, Springer-Verlag, LNCS 855, J. van Leeuwen (ed.), pp. 36-47; Utrecht, The Netherlands, Sep 26-28, 1994.

Specifically section 4 of the paper, that gives an example of a set of points that does not have a so-called "sequential triangulation".

The person who wrote the code I talked about is Martin Held.

share|improve this answer
5  
Please ask Estie Arkin to identify the conjecture. It's a great story, but would be more useful if we knew the precise counterexample. –  Joseph O'Rourke Aug 6 '10 at 18:44
2  
@Joseph: See edit –  BlueRaja - Danny Pflughoeft Mar 31 '11 at 16:33
5  
Thanks for asking the source! –  ShreevatsaR May 10 '11 at 7:21
add comment

The first example which came to my mind is the Skewes' number, that is the smallest natural number n for which π(n) > li(n). Wikipedia states that now the limit is near e727.952, but the first estimation was much higher.

share|improve this answer
add comment

For an old example, Mersenne made the following conjecture in 1644:

The Mersenne numbers, $M_n=2^n − 1$, are prime for n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257, and no others.

Euler observed that the Mersenne number at M_61 is prime, so refuting the conjecture.

M_61 is quite large by the standards of the day: 2 305 843 009 213 693 951.

According to Wikipedia, there are 47 known Mersenne primes.

share|improve this answer
2  
This one is the most accessible/easy to explain of them all...but 257 seems like an arbitrary place to stop the conjecture at so I'm not sure it's as pretty. –  Justin L. Jul 23 '10 at 19:21
    
@Justin: Well, Mersenne had an intuition. Sometimes intuitions are sound, and sometimes they're not. –  Charles Stewart Jul 23 '10 at 20:02
    
I doubt you mean Euclid, since he lived more than a thousand years before Mersenne. Euler, I presume? –  Pete L. Clark Jul 29 '10 at 7:07
    
@Pete: Quite so. –  Charles Stewart Aug 8 '10 at 7:59
add comment

Another class of examples arise from diophantine equations with huge minimal solutions. Thus the conjecture that such an equation is unsolvable in integers has only huge counterexamples. Well-known examples arise from Pell equations, e.g. the smallest solution to the classic Archimedes Cattle problem has 206545 decimal digits, namely 77602714 ... 55081800.

share|improve this answer
2  
I have a nice chuckle at "77602714 ... 55081800"! –  Willie Wong Jun 17 '11 at 0:27
add comment

A famous example that is not quite as large as these others is the prime race.

The conjecture states, roughly: Consider the first n primes, not counting 2 or 3. Divide them into two groups: A contains all of those primes congruent to 1 modulo 3 and B contains those primes congruent to 2 modulo 3. A will never contain more numbers than B. The smallest value of n for which this is false is 23338590792.

share|improve this answer
1  
There's a nice article about "prime number races" on the MAA Writing Awards website. –  ShreevatsaR Jul 29 '10 at 1:30
add comment

I don't know if I would consider this accessible or 'large', but the counterexample of Adyan to the famous General Burnside Problem in group theory requires an odd exponent greater than or equal to 665. The "shorter" counterexample (proof) due to Olshanskii requires an exponent greater than $10^{10}$. The reason for the large number in the latter proof is essentially due to 'large scale' consequences of Gauss-Bonnet theorem for certain planar graphs expressing relations in groups. It may be that a finer analysis can show that a counterexample can occur at exponent as low as 5, but this is still not known.

This is probably essentially different than what you are asking, since we aren't forced to consider 665 because the cases 1-664 are known to be true. I thought it may be fun to point out, here, though!

share|improve this answer
add comment

I was so pissed after testing one of my own conjectures that I remembered this question and wanted to post it here.

I conjectured after numerical observations that for every prime p, and integers $k \ge 1, n \ge 1$, that $$ p^k \, || 2^n-1 \quad \Longleftrightarrow \quad p^{k-1} \, || \, n \quad and \quad O(2,p) \, |\, n, $$ where $O(2,p)$ is the least integer $m$ such that $2^m \equiv 1 \pmod p$, and $||$ stands for exact division (i.e. $a^k \, | \, m$ but $a^{k+1} \, \nmid \, m$ is written $p^k \, || \, m$). This conjecture happens to be true for the first $180$ primes and the first $3000$ multiples of $O(2,p)$ (when $n$ is not a multiple of $O(2,p)$ we already know what happens). But it so happens that $1093$ is prime, that $O(2,1093) = 364$ and $2^{364} \equiv 1 \pmod {1093^2}$, so that the statement above is not true when $k=1$, $n = 364$ and $p=1093$ because the division on the LHS is not exact.

share|improve this answer
7  
+1 for discovering one of two Wieferich primes. –  draks ... Jul 31 '12 at 7:49
    
@draks : I didn't even know such primes existed. God I am damned. This was actually relevant to my research and I expected everything to work out nicely, and now I fall on some famous counter example. Gosh. –  Patrick Da Silva Jul 31 '12 at 7:57
3  
Maybe you can just exclud'em: Let $p$ not be a Wiefereich prime, then$\color{green}{.}\color{goldenrod}{.}\color{red}{.}$ –  draks ... Jul 31 '12 at 8:01
    
@draks : It's actually not that cool to exclude them given the context where I want to use them.. actually the reason for me to prove this statement is to establish a possible theorem/analogy between primes and irreducible polynomials over $\mathbb Z[x]$ (because there are lots, this one would be one more), so yeah, Wieferich primes... are not cool. –  Patrick Da Silva Jul 31 '12 at 8:05
1  
so you won't like Wolstenholme primes as well...anyway, good luck for research. –  draks ... Jul 31 '12 at 8:08
add comment

My favorite example, which I'm surprised hasn't been posted yet, is the conjecture:

$n^{17}+9 \text{ and } (n+1)^{17}+9 \text{ are relatively prime}$

The first counterexample is $n=8424432925592889329288197322308900672459420460792433$

share|improve this answer
4  
And $n^{19} + 6$ and $(n+1)^{16}+9$ are relatively prime until $n = 1578270389554680057141787800241971645032008710129107338825798$ (61 digits), where the two numbers have gcd equal to $5299875888670549565548724808121659894902032916925752559262837$. –  KCd Apr 18 '13 at 22:19
    
@KCd: These numbers (for that $n$) have $\gcd=2$. And the smallest value of $n$ with $\gcd>1$ is much much smaller. You intended $n^{19}+6$ and $(n+1)^{19}+6$. Do you know (or Joe K) any reference about this 'conjecture'? –  P.. Jun 5 '13 at 9:44
    
As another example $a=n^{29}+14$ and $b=(n+1)^{29}+14$ are relatively prime until $n=34525342211635505886236676687486891044156009698065465611040810544626869194123‌​9624255384457677726969174087561682040026593303628834116200365400$. Both $n$ and $\gcd(a,b)$ have 141 digits! –  P.. Jun 5 '13 at 9:46
    
This phenomenon is related to the resultant of the polynomials $x^{17}+9$ and $(x+1)^{17}+9$, or of $x^{19}+6$ and $(x+1)^{19}+6$, or of $x^{29}+14$ and $(x+1)^{29}+14$. Polynomials with even a moderately large degree, even if they have small coefficients, can have a truly gigantic resultant. –  KCd Jun 5 '13 at 13:59
add comment

It is well known that Goldbach's conjecture is one of the oldest unsolved problems in mathematics. A counterexample if it exists it will be a number greater than $4\cdot10^{18}$.

What is not well known is that Goldbach made another conjecture which turned out to be false. The conjecture was

All odd numbers are either prime, or can be expressed as the sum of a prime and twice a square.

The first counterexample is $5777$.
This number is not "extremely large" for today's data but surely it was on 1752 when Goldbach proposed this conjecture in a letter to Euler who failed to find the counterexample. It was found a century later in 1856 by Moritz Abraham Stern( see this). The prime numbers that cannot be written as a sum of a (smaller) prime and twice a square are called Stern primes. It is believed that there are only finitely many Stern primes.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.