Clarifications: 1) In the definition of Schur number, we are talking about the largest integer such that *there exists* a coloring with no monochromatic solutions to a+b=c. You can always do a stupid colorings like all one color, the question is how high can we get where we can find at least one possible coloring without any monochromatic triples. 2) A few of you noticed the distinction between demanding each number has AT LEAST one color and demanding each number has AT MOST one color (put together, each number gets exactly one color). In the video I only implemented the former. Partly, this was because the expressions were long and I wanted it brief for the video, but partly this is because when using SAT solvers, a technique called blocked clause elimination ends up eliminating the extra causes for the AT MOST direction. Some of the comment suggestions was just to use XOR instead of OR, but SAT solvers apply to things in something called "conjunctive normal form" which is just long series of and statements of or statements, so when encoding we break up the XOR statements into multiple OR statements. Check out the section on the paper on symmetry breaking for further reading here. 3) Just for fun. What the "longest" mathematical proof is depends a bit on interpretation. Another contender (and won the guiness record) is the classification of finite simple groups, involving hundreds of papers combined.
Quite many years ago, when commenting on another proof that similarly had a huge amount of computer-generated data attached to it, a mathematician said that (paraphrasing) "a good mathematical proof is like a poem. This proof is like a phonebook." He didn't like that proof much.
This is why mathematics- in a very general and abstract sense- scares me. What if some answers *could* be known, but they're simply too complicated for our minds to understand?
Mathematics is fundamentally incomplete or inconsistent anyway. And we cannot demonstrate its consistency. There is already a fundamental leap of faith when we do math and choose to believe our results to be correct.
@@2299momo If we cannot prove even results we know to be true or even be sure that things we believe to be "true" are actually true or if our formal system is inconsistent, what would even more complex results change? absolutely nothing
16:29 You say 2 terabytes here but 2000 terabytes at the beginning of the video. I assume the 2000 is correct since a "mere" 2TB is nothing these days.
Presumably you could simplify the statements slightly by fixing the colors of 1 and 2, since you know they must be different, and any successful coloring would be also be true with the colors permuted however you like.
There are just these "easy" proofs that depend on doing something in principle but doing that thing in practice is really hard. The proof of an infinite number of primes is an obvious example, producing a few thousand primes is easy enough but factorising their product + 1 is a really hard problem but in principle it generates a prime we haven't listed yet. Ramsey theory seems to be a rich source of these kinds of proof, if it's big enough there will be something but how big is left as an exercise for the reader!.
Ya Ramsey theory has all these theorems about how eventually some structure is guaranteed to occur eventually and some of the proofs are quite nice and elegant, but the computations sure get super long!
@DrTrefor Off topic Trefor can you PLEASE PLEASE SHARE HOW you don't get fed up and bored and tired doing math?? And how can I be a genius like Einstein or Ramanujan? Hope to hear from you PLEASE
Very cool! Given a computational proof like this, are we able to get interesting insights from the proof? The advances on algorithms is great to see though!
I don’t think it yields some interesting insight, although in other cases it can such as the computer finding a conjecture we didn’t think about before
Questions on mathematical proofs, but not really linked to the problem in the video: 1. One mathematical statement can have multiple ways to prove it right? If each proof has a different length, is there a way to determine the proof (step-by-step) with minimal length? 2. Generalizing the first question: since math deals with abstraction, can the proofs themselves be treated as mathematical objects with certain properties?
Certainly you can treat proofs as objects of some sort. For instance, in the theory of "propositions-as-types", a proof is a term of a particular type that represents the proposition. Depending on how this term is represented, you can even have a notion of length. I believe determining the minimal proof length is an undecidable problem, since we can search all proofs of that length for a proof of our statement in finite time. But we already know that the problem of proving statements is undecidable in general.
@@eclipse1353 Not quite, the majority of the first 300 pages are setting up the system, only some of which are needed to show that 1+1=succ(1)=2. I think the classification of finite simple groups is 2000 pages long
As a non matematitian i'm astonished by the fact that such a simple problem cannot be solved by understanding the underlying patterns and symmetries that certainly exist. For example, chosen a number c divide it by two, then a and b will every time equally distant from that result, giving the solution a certain predictability and order. It's very strange that brute force is the only possible way. This furthermore makes me wonder when you clearly created a very simple algorithm for the first easiest solution, an algorithm that apparently could lead in my eyes to some graph theory solution
With regards to the balance between breaking it up and "just work longer", I kinda wonder what the motivation for ever going with "just work longer" would be? I'm thinking it suggests something about the distribution of solution times that it's faster to do that then break up everything that doesn't solve quickly. On the other hand, you might be able to have you cake and eat it too if the SAT solver could take an intermediate state of a problem and on demand split it into halves that can be processed on concurrency. If a solver could be structured that way, then you just trigger that on the longest running shard any time you have unused compute. That said, I'm now wondering if that's what they did? (One interesting property of tree search algorithms is that they can be insanely sensitive to how you traverse things. Even very tiny improvements to the choice of how you proceed can make many order of magnitude changes in compute time. I first ran into this with alpha-beta pruning where just by changing the fixed order of traversal of sub trees I got a change in the "effective branching factor" from something like 3.07 to 3.01 for something like a 100x speedup.)
I was watching through this and though "wow this is a neat problem, I can't wait to see what genius insight makes this proof obvious" and then I remembered that the proof involves petabytes of brute force lmao
You lose me directly at the start. @1:15 you state that "you'll notice that we get a bunch of tripples". I see that. But why is that? What is the rule or premise to change from one color to another?
Hm... This seems very similar to the Three Color Problem in graph theory. I'm curious is you could represent this problem as a graph and solve it that way.
The explanation of S(k) is quite unambiguous, since we could assume a can or cannot be equal to b. so, 1 could be color 1, 2 cannot be formed with 1 1 so it can be color 1, 3=1+2 so it has to be color 2, etc. if a and b had to be distinct numbers, S(k) would be a lot larger. so, S(1)=2, S(2)>=7, S(3)>16 these results are just with a greedy algorithm. I´m quite sure S(4)>>44
2 PBs is huge. So is 13 years of compute (was it 13? can't remember). I wonder if cryptographic methods can play a useful role for the archival of verified machine generated proofs. Say a compact artifact that asserts the verifier successfully verified the output of the program -- a non-interactive zero knowledge proof, maybe. If in the future the math community is to generate such proofs at scale, it would be useful not to have to archive the proof itself but only program [that generates the proof] along with a cryptographic proof that its output was verified. Is the issue of the *archival* of computer generated proofs itself an area of research?
To a first approximation, the 2 petabyte file is just a "trace" (i.e., a complete transcript) of the SAT solver computation, so the verifying algorithm just retraces the steps of the original computation. That's not quite right, though, because they use some clever tricks to write down a correctness proof efficiently (something called a DRAT proof of unsatisfiability). But the time required to verify the proof is still on the same order of magnitude as generating the proof in the first place.
given even checking takes up so much computational power, do we need to then verify the verification of the proof, and then verify that, and then verify that etc.. 😂
there's a detail I didn't include in the video which is that you should as you suggest ALSO do something to eliminate the possibility one number gets multiple colours - the authors add separate regular or statements for that, but then do some symmetry breaking tricks to simplify again so I just glossed over all of this for the sake of (20 minutes?) brevity.
This is actually simple..If no a,b,c =same color then there must always be a variable that is a negation of the other states for each series possible. If that is not possible, then it has no solution.
Also idk why you are saying the solution isn't satisfied when 1 is yellow too, all you do is flip the other states around. This seems like a pretty trivial problem but I may be misunderstanding it
It is kind of like proving an infinite numbers of primes. Let 1+1=2. Then 2+2=4. Let half of a number exist, this is half of 2 and half of 4, which is 3. Then any number constructed must be a prime eventually since half of the numbers up to 4 are prime and all numbers mod 4 will be bounded by the initial construct of the number line then every number series must eventually generate a new prime since all other numbers can be generated by the recursive operation over the initial states. By induction, unless numbers are not number then there must be an infinite amount of primes due to the theorem of arithmetic so it is also trivial in a way.
It's a very unsatisfying proof though. The best proofs (imo) link the problem to some other area of mathematics and lead to new insight or methods. This is just brute forcing a load of CPU cycles and doesn't advance maths in any way.
I partly see this, but personally I still found HOW they computed it and the way they encoded and then simplified the encoding to be tractable still had some interest. That said, a lot of this is aesthetic so to each their own!
I think some problems are just more akin to engineering than maths. Some maths problems can easily be generalised and proofs for those may lead us to new and interesting ideas. But I think some problems, you just get the answer, yes or no, and that's it. I'm not sure any alternative proof to this would give us any new insights - is there some deeper truth to the lack of 5-colourability in a 161-node graph that's connected in a very particular way? I don't think so.
@@IOverlord It would be so cool if we meet aliens and exchange maths knowledge! Discovering what overlap, what theorems and proofs we've independently discovered and in what order, whether either of us have missed something 'obvious' and get that forehead-slap moment when we share it. Like, do aliens know about the fast fourier transform? :D
Probably not, as a solution where a number has multiple colors just proves that it can be either. This is because, as I understand it, aside from the expressions that check that every number has at least one color, all the other expressions depend on the negative, i.e a number not being a particular color, rather than having to be a particular color. Though it may speed up the SAT solver to add those statements as you might be able to eliminate the possibility of multiple colors more quickly.
mathematics proofs will all look like this eventually because the whole concept is so stupid but everyone in charge makes all their money with this circus.
Very nice video. Amazing how such proofs are possible wow. Humanity has come so far being able to use ~30 cpu years to proof such a (sry) random fact 😂
Question: What is the use of this problem? … it is not that far in the k of S(k; so, probably pretty useless for the energy it consumed to find a solution and prove it. (Isn’t climate change about energy consumption? … not to forget training LLMs and mining blockchain money.)
@@DrTrefor Not really. If I hear a problem that goes "here is the possible solution space and here are the constrants (that is efficently computable in polynomial time)" my first instinct is "use SAT". It's basically brute force but more efficient
Haven't watched the video, but the thumbnail is a list of primes, and up to what I remember the infinity of the amount of existent primes is super easy to prove Edit: 3:10 this is the proof my comments are legit, completely missed the topic of the video Secound edit: The thumbnail even shows non-primes...
Interesting, but... I don't consider something like this to be "proof". The only proof I would consider is proof about general S(n) formula. This is just calculation, a smart calculation, but calculation nevertheless.
"If I try to color numbers", color how, randomly? "You'll notice triplets" why would anyone notice that, why is it presented like it's a reasonable thing to think about Explanations are so rushed in this one while using vague language geez
