Sunday, May 29, 2016
New Ramsey Result that will be hard to verify but Ronald Graham thinks its right which is good enough for me.
If you finitely color the natural numbers there will be a monochromatic solution to
x+2y+3z - 5w = 0
There is a finite coloring of the natural numbers such that there is NO monochromatic solution to
x+2y+3z - 7w = 0
More generally:
An equation is REGULAR if any finite coloring of the naturals yields a mono solution.
RADO's THEOREM: A linear equation a1 x1 + ... + an xn = 0 is regular IFF some subset of the ai's sums to 0 (the ai's are all integers).
Rado's theorem is well known.
What about other equations? Ronald Graham has offered $100 to prove the following:
For all two colorings of the naturals there is a mono x,y,z such that
x2 + y2 = z2
I've seen this conjecture before and I thought (as I am sure did others) that first there would be a prove that gave an ENORMOUS bound on
f(c) = the least n such that for all c-colorings of {1,...,n} there is a mono (x,y,z) such that ...
and then there would be some efforts using SAT solvers and such to get better bounds on f(c).
This is NOT what has happened. Instead there is now a paper by Heule, Kullmann, Marek, where they show f(2)=7825.
(NOTE- ORIGINAL POST HAD f(2)-7285. Typo, was pointed out in one of the comments
below. Now fixed.)
It is a computer proof and is the longest math proof ever. They also have a program that checked that the proof was correct.
And what did they get for their efforts? A check from Ronald Graham for $100.00 and a blog entry about it!
While I am sure there proof is correct I wish there was a human-readable proof that f(2) existsed even if it gave worse bounds. For that matter I wish there was a proof tha,t for all c, f(c) exists. Maybe one day; however, I suspect that we are not ready for such problems.
Subscribe to:
Post Comments (Atom)
You should read your posts after you post them to catch typos.
ReplyDeleteIf there is a typo in the above post let me know and
DeleteI will correct it.
I went to build the graph of related triples so that I could see this in action, and in the triples dataset I was looking at there was only 1 pair (x,y) such that x^2 + y^2 = 7285. But if that is true either you gave wrote down the wrong value for f(2) or defined it wrong, or that's not it's value, or I'm just really confused by what you were trying to say. Because for 7285 to be least n, Then there most be a coloring of {1,...,7284} with no monochrome solution, but for which both of the related colorings of {1,...,7285} have a monochrome solution. But that would require 2 solutions to x^2 + y^2 = 7285. So there is something that is incorrect.
ReplyDeleteYou misread my definition of f(c), which had a ... in it so perhaps it was unclear on my part. Here is the full definition:
ReplyDeletef(c) is the least n such that for any c-coloring of {1,...n} there
exists x,y,z all the same color such that x^2 + y^2 = z^2.
x,y,z in {1,...,n} right? So if f( c) is 7285. Then there exists 2 coloring of {1,...,7284} in which there are not same colored (x,y,z), because 7285 is the least such n. Call that coloring C'. There are two colorings of {1,...,7285} that are identical to C' for {1,...,7284}. We can call those C'+black and C'+white. because f( c) = 7285 those colorings both contain monochromatic solutions. If either of them doesn't use 7285 as z then C' had a monochromatic solution. so it must be the case that there exist (x1, y1) white in C' and (x2, y2) black in C` such that x1^2 + y1^2 = 7285^2 = x2^2 + y2^2. Otherwise one of those colorings does not have a monochromatic (x,y,z). Now the table I looked at said that 7285 was only in one such triple of integers. So either the table I referenced is wrong. My understanding of f( c) is still wrong. You've transcribed the result incorrectly and it's some other number. or their result is wrong.
ReplyDeleteThis was this list I referenced. http://www.tsm-resources.com/alists/PythagTriples.txt
ReplyDeleteEgdiroh- I looked back at the paper and I had transposed
ReplyDeletedigits in the result. I have made the correction.
Thanks for catching the mistake!
Apologies.