How do mathematicians calculate extremely large sets of numbers to prove theorems? Both now and in the past?
A modern example is the Collatz Conjecture, 2\^68 numbers were checked, so what resources do mathematicians use for this? Supercomputers?
And in the past, the Polya Conjecture was disproven by C. Brian Haselgrove in 1956, he calculated more than 2\^361 values, so how was this done when computers weren’t as powerful?
In: 40
>And in the past, the Polya Conjecture was disproven by C. Brian Haselgrove in 1956, he calculated more than 2^361 values, so how was this done when computers weren’t as powerful?
Haselgrove didn’t actually do that calculation – he proved that there was an answer somewhere under 2×10^361, but he didn’t actually find the answer, he just proved that there was one.
Someone else did find one in 1960, at a MUCH lower level than that – 906,180,359. That’s just over 9×10^8 – you could multiply it by the number of atoms in the universe four times and it would STILL be lower than what Haselgrove proved.
But even they didn’t check every number – it wasn’t until 1980 that it was proven that the lowest counterexample was 906,150,257.
Proofs arent generally made by brute force. The only one I can think of where the proof was brute forced was the sudoku one (A sudoku must have atleast 17 clues to have no more than 1 answer). When brute force is used it is on supercomputing clusters.
For the collatz conjecture, there are a lot of tricks you can do to check numbers. You might think the best way is asking “does 10 follow the collatz conjecture? how about 11? 12?” but this is pretty inefficient, you know the collatz conjecture says “if n is even, half it” this chain eventually lands on an odd number, so you never have to even check an even number. If all odd numbers follow it, so will all even ones. Speaking of odd numbers, the formula for that is 3n+1 which will always be an even number, so you can shortcut it with (3n+1)/2 or 1.5n+.5, if this ever hits a number you know satisfies the collatz conjecture, or a perfect power of 2 (even all the way down to 2) you are done, no need to check further. and you can go the other way too, if n satisfies the collatz conjecture, so does (n-1)/3 and 2n. Using these tricks you can vastly reduce the number of numbers that need to be checked the hard way. But we cant prove it this way, there is a chance we will find a counter example and disprove it, but we can never prove it for sure using brute force.
As for strangely large historical numbers, you can prove (and especially disprove) things about numbers without knowing them. For example, say we make a theorem that says “There are 10000 prime numbers, and no more” we can disprove this by saying “but if you multiply all of them together and add 1, you get a number that isnt divisible by any prime number, and is thus a new prime number” You can do that without knowing all the first 10000 prime numbers, and you can even estimate its size. Since 2 is the smallest prime number, this new prime is larger than 2^10000 and also 2*3^9999, etc. we can also know since not every number is a prime number, it is larger than 10000! (factorial), and we also know it is smaller than n^10000 (where n is the 10000th prime). You can narrow this range more, this is just an example, but the same process happens with other proofs.
Calculations are rarely involved in proving a mathematical theorem.
Let’s look at the example you used. The Collatz conjecture makes a claim about every positive integer. We aren’t going to be able to prove the Collatz conjecture by brute force, because we can’t check every positive integer (there are infinitely many).
If a proof is found for/against the Collatz conjecture, it will not be found by “checking” a ton of numbers, but instead will be found by logic and clever reasoning.
Wouldn’t a proof by induction take away the need for a brute force approach?
Note that your question has a fatal misunderstanding. You ask how mathematicians calculate extremely large sets of numbers to *prove* *theorems*, and then give a conjecture as an example.
A conjecture is quite literally an unproven theorem. It means we have yet to logically prove with adequate reasoning that the conjecture is universally and generally true. All we can say is that it appears true and, when we test to see if it’s true, thus far it has always been true. It will stop being a conjecture when we either prove/disprove it, or we stumble upon a counter-example.
The Twin Prime Conjecture is another example.
Real proofs don’t calculate exhaustively because there are, usually, an infinite number of calculations that need to be performed and there will always be this lingering worry that perhaps there exists some example out there to dismantle the conjecture.
Imagine you wanted to prove that the sum of any two odd integers always results in an even integer. You could try checking literally every sum possible, or you could prove it! Look up a proof for this! It’s quite easy to follow and demonstrates perfectly what real mathematics is.
Latest Answers