Hacker News Reader

No amount of empirical data is ever "good enough" for the mathematical standard of proof. (It may be enough for mathematicians to "believe" something in some informal sense, but not enough to consider it "proved".) You can see some examples at the answers to these questions; maybe at least one of them will be interesting to you:

(There are over a hundred examples at those questions; I guess this counts as a lot of empirical data that empirical data is not enough! However, sometimes empirical data can be enough for a mathematical proof; for instance if you know somehow that a polynomial f is of degree less than n and you have shown that f(x)=g(x) at n distinct points, you can indeed conclude that f=g and so on — see the "Proofs by Example?" section of the first "Proof Machines" chapter of the book "A=B" available online https://www2.math.upenn.edu/~wilf/AeqB.html .)

That was another question in the back of my mind -- famously, the four color theorem was proved by computers through exhaustive analysis (checking every possibility). At the time, it was controversial as a "proof" since it didn't really take the usual form of a proof.

I've often wondered "Why can't we do something like that, but for all instances of things like the Collatz conjecture?" Of course, it's computationally infeasible. But that raises the question: Suppose the four-color theorem was only able to prove 95% of cases rather than 100%. Isn't it at least sort of valuable to do so? Or is that last 5% all the difference?

I suppose what bugs me about math is, physicists are proved wrong all the time. Mathematicians are rarely proved mistaken, because they construct assumptions that you can't disagree with. There's no chance for empirical data to falsify one's assertions.

But that's an odd kind of debate, and not too productive. I just can't help but wonder about stuff like this.

The four-color theorem had the preliminary challenge of creating a method to identify all the relevant cases. That also required a mathematical theory. (I don't actually understand how it was done!)

If you didn't have that, you would have an infinite search for possible maps that violate the conjecture, because you wouldn't be able to divide them into a finite number of equivalence classes, or enumerate a finite number of possible counterexamples, or whatever.

For Collatz, I don't think we have any lemma that gives a path to saying "a counterexample must be one of these 2¹⁰⁰ integers" or the like. So without such a thing, checking every possibility would mean checking every integer. (Well, there are definitely lemmas that make it unnecessary to check large numbers of integers, so I should say instead that checking every possibility would still mean checking an infinite number of cases.)

As an interesting example where we did have a finite bound that was still out of reach to computationally exhaust, see the Weak Goldbach Conjecture:

https://en.m.wikipedia.org/wiki/Goldbach%27s_weak_conjecture

It was known to have at most finitely many counter-examples by the 1930’s, and by the 1950’s it was known that the largest counter-example had to be < 3^3^15. In 2002 that was lowered to about 10^1346. Still well out of reach of any computer!

Only in 2012 was an unconditional proof given.

It can be valuable, but it's not as valuable as covering all cases.

If I could prove collatz for 99% of numbers it would be great.

If i could additionally prove which 99% converge, let's say all numbers not divisible by 100, it would be enormous because even showing this much is likely to be a stepping stone to a full proof (what property is it about the number 100 that excludes all non-divisors from diverging?)

> I suppose what bugs me about math is, physicists are proved wrong all the time. Mathematicians are rarely proved mistaken, because they construct assumptions that you can't disagree with. There's no chance for empirical data to falsify one's assertions.

Right, and that's the whole point and beauty of it.

You're adhering to certain misconceptions for no good reason. An exhaustive check of all the cases in the model that supports the four-color conjecture is the "empirical" (here, meaning experimental) data required to falsify conjectures. And even physicists don't deny the value of falsification in narrowing down models to truth. But I think they are much more loose in what they are willing to stipulate as true if it means advancing other conclusions.

Furthermore mathematicians do accept certain kinds of probabilistic arguments, but they need to take a form of proving that an object will be guaranteed to have a certain property as a parameter on the object approaches a statistical limit. So partial evidence can sometimes point to the possible truth of a mathematical conjecture, but you are still burdened with the requirement of deductive demonstration if you desire logical certainty.

The tautological notion you take of math is a half-truth. On the one hand, models in math seek to be sound over the objects they specify. This is opposed to physics where deliberate simplifications must be made to make your idealizations of a system manageable or relevant. At the same time, no mathematical system is complete. So there will be truths that require other axiomatizations to access via proof. This is one source of mathematical creativity requiring judgment beyond following tautologies.

Math is simply not a science, not in the sense of "natural science". Math research does not follow the scientific method, it is not an iterative effort to construct (wrong, but useful) models of some external universe like science does. Math is a thing of its own, and it's best just to not compare it to physics or biology or gender studies or whatever.

"famously, the four color theorem was proved by computers through exhaustive analysis (checking every possibility)"

This is impossible. The plane can be arbitrarily large with an arbitrary number of regions. It can be exhaustively checked for n number of regions up to a certain n. But not for arbitrary n.

Not every possible graph, just every "interesting" class of subgraph that can be extended or combined with others to obtain a coloring of any planar graph. These are a large but finite number; if a graph is planar it cannot have too many edges.

>My question is, why is this empirical data not "good enough" for mathematicians?

There are two reasons: firstly, because mathematics is not an empirical discipline (well, unless you're a number theorist...), so it is possible to be certain of mathematical truth, unlike the inherent uncertainty of physical truth; secondly, because every finite bound on the natural numbers may as well be 0 when compared to the numbers that remain.

There is simply no way to take any empirical measurements of the natural numbers (or the reals) that would let you estimate anything "for all numbers", since the proportion of numbers you failed to sample is infinite.

You may be interested in reading the answers to this question: https://math.stackexchange.com/questions/514/conjectures-tha... which describes some problems which seemed true "up to some large number", but later turned out to be false.

https://math.stackexchange.com/questions/514/conjectures-tha... was excellent. Thank you.

> 𝑛^17+9 and (𝑛+1)^17+9 are relatively prime

> The first counterexample is 𝑛=8424432925592889329288197322308900672459420460792433

I think this helped me appreciate the difficulty of being satisfied with the Collatz conjecture.

Well, firstly there are "important numbers" much bigger than the range we've empirically tested, so our empirical results aren't actually good enough. If there was some deep relationship with number theory, maybe it just happens that a number in this range is the first to break the pattern, which could be a deep and beautiful result.

But also, it's just the nature of mathematics, proving what is true is just as important (if not more so) than knowing what is true.

From a practical perspective, doing mathematics, you often don't really grok why something is true until you prove it.

From a philosophical perspective, there's not much in the universe we can know for sure (as you mention with the gravitational constant), but a mathematical proof we know for sure. That's the beauty of it.

if X is true and the implication (X => Y) is true, then it must be that Y is true. By definition of a logical implication.

Add in a whole bunch of axioms and suddenly you can take these simple logical atoms and build them into a field that spans the working tools of every engineer and beautiful arcane subjects like set theory. And every single thing we prove, we know to be true, as we build it from logical atoms that can be traced back to definitions and axioms.

It "could be" that for certain types of matter or at certain distances, the gravitational constant changes. It cannot be that there exists a bijection between the natural numbers and the real numbers under ZFC. Cantor's diagonalization argument *proves* it.

They've verified that the Collatz conjecture holds for all numbers up to ~2^68, but that's precisely 0% of all the numbers that need to be checked.

But more importantly, the goal of (pure) mathematics isn't to declare truths. If you had a machine from God himself that outputted True or False for theorems you put in, that wouldn't demotivate (pure) mathematicians from doing the work they're doing. Understanding the reason things are the way they are (and being able to share those understandings) is the purpose of math. I'd be willing to wager that almost every mathematician would rather have a proof that Collatz holds for all numbers divisible by 17 rather than a definitive yes/no answer to whether it's true or not, because the former would lend much more illumination to the secrets behind the problem, and would lead to new, more interesting mathematical methods and disciplines. The latter would be a fun fact to share at parties.

> They've verified that the Collatz conjecture holds for all numbers up to ~2^68, but that's precisely 0% of all the numbers that need to be checked.

This is the crux of what has me looking like a fool to every mathematician in the thread, but I don't mind: why is 2^68 0% of the "numbers that need to be checked"? From a physicist standpoint, you can do a lot with numbers from 0 to 2^68. After all, 64-bit floats are quite useful. Is there 0% value in proving the Collatz conjecture for all possible numbers one might want to use in a normal programming language without big number libraries?

I know the question must sound pretty crude, but it's also a source of mystery. Mathematicians are so obsessed with exactness. Is there no room for empirical analysis in number theory?

In other words, number theory relies on certain assumptions. What if one of your assumptions is "a number system from 0 to 2^64"? Why is there no value in that?

>Why is there no value in that?

Because it's uninteresting. The point of pure math is not to be "useful", it's to be interesting. The Collatz Conjecture is (as yet) a completely useless result. Like I said, if God himself came down and told the world "The Collatz Conjecture is true", all we'd get is a useless piece of trivia. "The Collatz Conjecture is true for the first 2^68 natural numbers" is even more worthless than that. Maybe it'd be useful if we had an application for it, but for context, many pure mathematicians are quite derisive at the idea that their work should have practical applications.

Here's a digression, a simple math problem. If you take a checkerboard and remove two opposite corner squares, can you tile the remaining 62 squares with 31 dominoes?

You can probably write a program that can exhaustively churn through all the possible arrangements of dominoes in a checkerboard, and it'll spit out the answer (it's "no"). But is that interesting? No. This is a boring fact, "if you take a checkerboard and remove the two opposite corners you can't tile the remaining squares with 31 dominoes". No one cares about that.

But, here's a proof that this is true. If you look at the colors of each square on a checkerboard, there are 32 black squares and 32 white squares. When you remove the two opposite corner squares, you're removing two squares of the same color. So you have 30 black squares and 32 white squares left (or the converse). Meanwhile, every domino takes up one black square and one white square. So no matter how you place 31 dominoes, they should cover 31 black squares and 31 white squares. Therefore, we've proven the tiling is impossible.

That's somewhat interesting. You have an easily understandable argument for why the fact is true, and you have an application of a method (here, invariants) for looking at other math problems. Plus, it's kinda fun and satisfying and "elegant" to solve a problem like this. The proof is much, much more interesting than knowing the answer to the problem. Hopefully this helps convey that.

> why is 2^68 0% of the "numbers that need to be checked"?

The vast majority of natural numbers are larger than 2^68. Only 2^68 of them are less than 2^68, but infinitely many of them are greater.

Though note that that True/False machine could also quickly lead to the discovery of actual proofs, for example by making it extremely efficient to search for counterexamples. "The Collatz conjecture is true for all n ≤ some_huge_number." Also perhaps by making it extremely efficient to search for correct proofs in a lexicographically ordered list of proofs. "The shortest valid proof of the Collatz conjecture in the list of all proofs in my formalism is before proof number some_huge_number."

Although I think the basic version of the machine is "just" the first Turing jump oracle

https://en.wikipedia.org/wiki/Turing_jump

-- it depends on how you formalize the inputs to the machine, right? -- so maybe mathematicians would still be busy afterward. :-) Maybe the machine is an oracle with infinite Turing degree?

This is true, a universal oracle would probably lead to some chaos in the world's computer science departments. I wonder how many mathematicians would switch over to help formalize and solve their fields, and how many would stick to their pencils and paper :P

I think others addressed the "why proof not empirical data" question well, but one additional point. A logical proof is only as solid as its weakest component. In mathematics any result that has been proven may be used in a component of another proof. If you have a result that is based on empirical evidence, then every result proven based on that also inherits that empirical evidence as part of its foundation. The reason we don't do this is that if, by some weird chance, the original result that used empirical data instead of proof is shown to be false, then every result built upon it is invalidated and needs to be revisited. That would be a mess. Sticking to requiring formal proofs at least reduces that possibility - although it is still entirely possible for a proof to have a subtle mistake as well, which would have a similar cascading effect on results built upon it.

Some theoretical physicist (Aaronson?) once quipped something like, "If physicists had discovered P vs. NP, then they'd have said P != NP and given a Nobel for it. And then if it turned out P = NP, then they'd give another Nobel."

Another, more important reason is that we know that the Collatz Conjecture is a single slice of a Turing-complete question about dynamical systems. Trying to find a complete proof expands our knowledge about the bridge between dynamical systems and the natural numbers. Such explorations were essential to founding modern physics in terms of dynamics and conservation laws.

I'll give a perspective, although my specific knowledge of math is not very deep at all, I've thought a lot about concepts and abstractions.

I think the difference here is that math is much more abstract than physics. The concepts backing math are built off of very low level abstractions about the world. For math, over a long period of time more and more relationships and rules were deduced from what had already been induced from reality. And if you CAN deduce, you should likely, as it provides a proof for some idea or concept that induction never could (but only if your previous inductions and deductions were accurate).

Physics on the other hand, cannot deduce as readily. It is primarily based in the realm of gathering more and more data from the world and observing physical relationships firsthand. This cannot be done in abstract math because abstract math does not exist in reality. There is nothing to observe, it is mostly abstractions based on lower level observations in reality. For example, you can measure the effects of gravity firsthand, but you cannot measure infinity, a mathematical abstraction. Infinity does not exist in reality. It is simply a useful abstraction for things that are too large or small for us to meaningfully measure.

> There are lots of histograms and empirical data supporting the conjecture.

There's a very interesting implicit question there: why should counterexamples be small? [1][2] Certainly, counterexamples to many conjectures about infinite sets can be found with a brute-force search, even if the problem is merely semidecidable. But isn't that simply an example of selection bias?

There is a certain subjective beauty in having counterexamples like 9 or 341 or even 23338590792. But is that just anthropocentrism? After all, no matter how many cases we check, we have made absolutely no progress in exhausting the whole set of natural numbers! We can never reach even reasonably easily constructable numbers like 3↑↑↑3 (using Knuth arrow notation [3]), and still almost all[4] natural numbers are bigger than that.

In physics, there's an (often implicitly made) assumption that more evidence in support of a hypothesis makes it more likely that the hypothesis is supported by any future evidence as well. But why should we be able to make that assumption? We do, because it seems to work, but why should it still work tomorrow? This is, of course, the famous philosophical problem of induction [5]. But math is basically what happens when you explicitly reject inductive reasoning and then start to explore the space of things that can still be reached, using purely deductive reasoning!

[1] https://math.stackexchange.com/questions/449886/the-largest-...

[2] https://math.stackexchange.com/questions/111440/examples-of-...

[3] https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation

[4] https://en.wikipedia.org/wiki/Almost_all

[5] https://en.wikipedia.org/wiki/Problem_of_induction

It is simple empirical data isn't proof. It is as if you were testing primes 2 yes, 3 yes, 4 no. Here is empirical data that only 2 primes exist. Should we believe it?

Sure for Collatz we have tested more than 3 numbers but we can't guaranty it is true until we test all infinity of them, or have a proof that doesn't rely on empirical data. To do otherwise would be to look like a fool when someone got around to testing N+1 and it no longer being true.