I'm not trying to be flippant, although it may come off that way: why does any of this matter?
(1) When lots of really smart people spend lots of time trying to solve something, and fail to do so, it becomes even more interesting for other smart people. A well-known example is the Collatz Conjecture[0] which, by most accounts is a meaningless problem, but endlessly fascinates many for its renowned difficulty.
(2) In mathematics, you often stumble upon problems that are equivalent to other problems. If X is difficult to solve so you give up and go work on Y, only to find out that Y as a problem is basically the same to X, or they have some other intimate relationship, and it makes X that much more tantalizing. A common example for computer scientists is the whole class of NP complete problems[1] for which we don't know if there exists a polytime algorithm to decide. Every time we discover a new problem that lives in the realm of NP-complete, the P vs NP problem gets a little more tantalizing.
> If the conjecture is false, it can only be because there is some starting number which gives rise to a sequence that does not contain 1. Such a sequence would either enter a repeating cycle that excludes 1, or increase without bound. No such sequence has been found.
There are lots of histograms and empirical data supporting the conjecture.
My question is, why is this empirical data not "good enough" for mathematicians? As something closer to a physicist, I do wonder what the fascination is with trying to prove conclusively that 3n+1 xor n/2 will eventually encounter 1. It seems a bit like trying to prove conclusively that the gravitational constant is so-and-so, when it seems the best you can do is to measure it as precisely as possible:
> Jeffrey Lagarias stated in 2010 that the Collatz conjecture "is an extraordinarily difficult problem, completely out of reach of present day mathematics."
As someone who loved mathematics but was never much good at it, what's the fascination here? (I'm only trying to understand the motivations of people smarter than I am.)
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.
> 𝑛^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.
- https://math.stackexchange.com/questions/514/conjectures-tha...
- https://math.stackexchange.com/questions/111440/examples-of-... (and maybe https://mathoverflow.net/questions/11517/computer-algebra-er... )
- https://mathoverflow.net/questions/15444/examples-of-eventua...
(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 .)
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.
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.)
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.
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.
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.
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.
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.
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?
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.
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.
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?
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.
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.
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.
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.
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
I think I can see why trying to solve this problem is popular. It almost feels like it should be easy to solve but it just quite isn’t!
Cantor, Hilbert and Gödel gave us Church who gave us Turing. Turing and Flowers gave us the machines as well as the theory. All of them put together gave us type systems and types are how you formally prove that your 747 software is free of, if not all bugs, then at least certain large classes of error.
There is a clear line of connections from Cantor (1890s) to jumbo jet fly-by-wire (1990s.)
Countability of sets and Cantor’s diagonal argument — the subject of the first part of this article — are some of the first topics teenagers learn about in high school CS (if you’re lucky and on a very modern course) or CS101 (if you’re at a University.) Types are sets.
Who knows what today’s mathematics will bring us in the year 2121?
It’s not a flippant question at all.
The answer is, it doesn’t matter. And that’s the joy of it.
It wasn’t until I got into ML that I learned the value of doing unimportant work. When you’re free to think about inconsequential matters very seriously, you end up discovering so many useful things. It was how I independently rediscovered what is apparently called the Discrete Hartley Transform.
You have a vague notion that what you’re doing might be important, but it’s not the focus. It matters because it’s fun in a way that nothing else can be.
Of course, the more serious folk won’t admit it’s fun. It’s serious work. And they’re not wrong; nobody’s fooling around. Our time is every bit as precious as an executive’s.
But their goal is to change the world. Ours — or mine, at least — is to know the truth of a thing that most people don’t know.
It doesn't matter yet. Applications of pure math happen downstream decades or centuries later. It's hard to predict the impact.
Isn’t history enough reason?
The core of the original comment that started this chain was:
> Applications of pure math happen downstream decades or centuries later.
My argument was that history shows that a surprising amount of mathematics does eventually trickle down into applications. I don't think anyone is arguing all of mathematics eventually sees an application.
Again, my point was that history does indeed seem to show that "applications of pure math happen downstream decades or centuries later". As the original commenter said, it's hard to predict what will be the next thing to be applied.
There are more mathematicians alive today than at any point in human history, and their work has become specialized to a tremendous degree. Gone are the days where one mathematician could do substantial new work in a dozen diverse areas.
So, in short, the fact that historically lots of pure math has not found use, the specialized nature of modern research math, the volume of work being out out, and an irreverence for applications(again, this is _pure_ math) leads me to be doubtful that even a moderate amount of modern pure math research will ever be useful in any practical sense.
At the bottom are all sorts of applications of linear algebra and optimization (calculus) are related to machine learning, deep learning (AI), physics, engineering etc.
One level up there are all sorts of ideas in algebra and mathematical analysis that are leading to new ideas in linear algebra and optimization (calculus)
Going one level higher, there are ideas in mathematical logic and set theory that are improving our understanding our algebra and analysis.
If you look at a specific result at the very top of the pyramid as ask why does it matter? It is difficult to give a good answer. Clearly we want to base of the pyramid, but do we need to keep building it up? Should we stop at a certain level?
Do I 'go home' - leave my home office - and think about it? No. Do I muse on how to solve a work-related issue when I'm showering? Also no. Will I forget almost everything about this job as or when I move onto the next? Definitely yes.
But academically, I'm interested, and actively publish albeit modest, low-impact research, in relational databases. I love the set-based approach to all matters SQL and after many years in the field still fool around trying to embellish, attack, improve and invent the core ideas.
Why bother? Even if I come up with some magical new improvement to RDBMSs, it doesn't matter. If I fork MySQL and try out my ideas, no one cares. I'll never get the traction or the FOSS community support, I'll spend more time playing politics and managing collaborators than I'd like (zero) and I enjoy the independent thought that my interests bring.
So my academic work is pointless. But it's meaningful to me. And I think that's what matters. I don't understand one-tenth of the ideas in this article, but that doesn't matter. What matters is that it's interesting to somebody.
All of this is nuanced but is important to mathematics and philosophy.
0 <-> sandwich
1 <-> 0
...
n+1 <-> n
By definition, if you can biject two sets, they have the same cardinality.
If we're ok with extending that to sets of infinite things (we can still pair elements of each set, we'd just never be able to finish listing all the pairs), then we can say that the natural numbers and "the set containing the natural numbers and a sandwich" are of equal size because we could pair 1 from the first set with the sandwich from the second set, pair 2 from the first set with 1 from the second set, 3 from the first set with 2 from the second set, etc etc.
There's no element of either set without a match in the other set, so they have the same cardinality as the natural numbers, with or without the sandwich.
Saying that two sets have the same cardinality is equivalent to them having a bijection between them.
So the claim is that the natural numbers and the natural numbers plus a sandwich have the same cardinality. This can be proved by the bijection:
0 -> sandwich
1 -> 0
2 -> 1
3 -> 2
.
.
.
n -> n-1
.
.
.
0 -> sandwich_0
1 -> 0
2 -> sandwich_1
3 -> 1
4 -> sandwich_2
5 -> 2
.
.
.
Still enough natural numbers to eat them all, one per.
But still not enough sandwiches to feed all the (so-called) real numbers one sandwich each!
But if sandwiches grew on trees, and we had an infinite branching tree with two branches at each branching point, and every branch has a (pair of) sub-branches, then natural numbers could not eat all the sandwiches, and the sandwiches could feel all the (so-called) real numbers.
As I understand it we can say the cardinality of the reals is 2^aleph_0. Why is it cheating to create a bijection thusly:
0 -> 0
1 -> 1/(2^aleph_0)
2 -> 2/(2^aleph_0)
Problem 2: There's no natural number that maps to (say) 1. Even if you do allow 1/(2^aleph_0), there's no finite number n that would make n/(2^aleph_0) = 1. With any reasonable definitions of the operations involved here, n/(2^aleph_0) would always be infinitesimal, so it would never equal a non-infinitesimal.
Problem 3: You're still skipping over infinitely many numbers. If 1/(2^aleph_0) is a number (and again, this requires going beyond the real numbers) and 1.5 is a number, then 1.5 * 1/(2^aleph_0) = 1.5/(2^aleph_0) is also a number, but no natural number gets mapped to that.
2^{\aleph_0} is a cardinal number, which isn’t really a number in the sense of “an element of a field” or something like that. Dividing by it isn’t a well defined thing.
And, you certainly can’t just multiply any real number (or, any real number between 0 and 1) by 2^{\aleph_0} and get a different integer as a result.
(Now, if you work in the surreal numbers, you can define things like n/(2^{\aleph_0}) (identifying cardinals with the first ordinal of that cardinality), but these would not be real numbers. They would all be infinitesimal , smaller than 1/k for all positive integers k, and yet bigger than 0. Similarly in the surreal numbers, you could multiply real numbers between 0 and 1 by 2^{\aleph_0}, but you would get surreal numbers which are larger than every integer (in fact, larger than any countable ordinal))
Summary: What you wrote doesn’t define a mapping from the integers to the real numbers . (It can be interpreted as defining a map from integers to something else though.)
It's even possible to add an infinite number of elements to an infinite set and retain the same cardinality (the Integers set has the same cardinality as the Naturals set).
At one point in my life I felt like the continuum hypothesis was the most important question in the world. Now I'm mostly concerned about finite material issues, e.g. my health. I think a good argument can be made why either of them matter much more than the other.
As far as we understand, the natural numbers are not sufficient for modeling physical phenomena. The reals/complex while immensely useful also occasionally turn out to be “too complicated” to give theoretical guarantees/proofs of models working well. On the practical side, that means that these models/algorithms can’t be guaranteed to not give junk results, while working on the domain of real numbers.
Now, purely speculatively, since the naturals/rationals are aleph0 in size and the reals are aleph2, that means there likely exists a set of numbers of size aleph1 sitting in between the two. What if we could use that set of numbers to construct our physical models? Could we somehow guarantee better behavior… Eg: in quantum mechanics, or field theory, or chaos, etc?! :-)
In a model of ZFC in which the set of reals has cardinality greater than aleph_1 , I wouldn’t be surprised if there is a subfield of the reals of cardinality aleph_1 , but I would be surprised if such a field was useful for things like that. Such a field would, of course, not be complete with respect to the usual metric on the rationals, so we wouldn’t have the desired convergence properties. We wouldn’t really be able to do infinite sums in it? (Well, perhaps some other sense of infinite summation could be done, but it wouldn’t be the usual sense.)
In addition, because such a subfield would only exist as an uncountable proper subfield in some models of ZFC, I find it hard to imagine that it would allow computations that wouldn’t otherwise work? I suppose it could motivate some computations which would then also work regardless of what model of ZFC is being used / is true ?
Most modern pure math is done completely independent of and without regard to applications(if it were, it would be ‘applied math’).