A 2-Coloring of [1,N] Can Have (1/22)N2+O(N) Monochromatic Schur Triples, But Not Less!

by Aaron Robertson and Doron Zeilberger


.pdf   .ps   .tex
Appears in Electronic Journal of Combinatorics, v. 5(1998), R19.

Written: Feb. 27, 1998.

Issai Schur proved the first Ramsey Theorem (way before Ramsey). He proved that if you color the integers from 1 to n by r-colors, you are GUARANTEED (if n is not too small) a monochromatic triple {x,y,x+y}. [By the way, his motivation was to prove Fermat's Last Theorem.]

If you hate Schur triples, you must learn to put up with them. Nevertheless, you may still want to 2-color in such a way as to MINIMIZE these buggers. If the number of colors is 2, Ron Graham, in SOCA 96' (Tianjin, June 1996), offered 100 dollars for the asymptotic minimal number of these Schur triples.

This is yet another example of an a posteriori trivial theorem. It is highly non-trivial to CONJECTURE the statements that lead to the solution, using the Maple package RON, but the difficulty is that of experimental math , not `rigorous' math. Once the right statements are conjectured, the formal proof is ROUTINE, and can be safely left to the obtuse reader.

Tomasz Schoen, a student of Tomasz Luczak, has independently solved this problem.


Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page