Sunday, July 12, 2020

Ronald Graham: A summary of blog Posts We had about his work

To Honor Ronald Graham I summarize the blog posts we had about his work.

1) Blog post New Ramsey Result that will be hard to verify but Ronald Graham thinks its right which is good enough for me.

Wikipedia (see here) says that in the early 1980's (can't Wikipedia be more precise than that?) Ronald Graham conjectured the following:

For all 2-colorings of N, there exists x,y,z all the same color such that (x,y,z) form a Pythagorean triple.

I cannot imagine he did not also conjecture this to be true for all finite colorings.

I suspect that when he conjectured it, the outcomes thought to be likely were:

a) A purely combinatorial (my spell check says that combinatorial  is not a word. Really? It gets 14,000,000 hits) proof. Perhaps a difficult one. (I think Szemeredi's proof of his density theorem is a rather difficult but purely combinatorial proof).

b) A proof that uses advanced mathematics, like Roth's proof of the k=3 case of Sz-density, or Furstenberg's proof of Sz theorem.

c) The question stays open though with some progress over the years, like R(5).

What actually happened was

d) A SAT Solver solves it AND gets exact bounds:

For all 2-colorings of {1,...,7285} there is a mono Pythag triple.

There exists a 2-coloring of {1,...,7284} with no mono Pythag triple.

I wonder if this would have been guessed as the outcome back in the early 1980's.

-------------------------------------------------------------------------------
2) Blog Post Ronald Graham's Other Large Number- well it was large in 1964 anyway

Let

a(n) = a(n-1) + a(n-2)

I have not given a(0) and a(1). Does there exists rel prime values of a(0) and a(1) such that for all n, a(n) is composite.

In 1964 Ronald Graham showed yes, though the numbers he found (with the help of 1964-style computing) were

a(0) = 1786772701928802632268715130455793

a(1) = 2059683225053915111058164141686995

I suspect it is open to get smaller numbers, though I do not know.


------------------------------------------------------------------------------
3) Blog Post Solution to the reciprocals problem

Prove or disprove that there exists 10 natural numbers a,...,j such that

2011= a+ ... + j
1 = 1/a + ... + 1/j

I had pondered putting this on a HS math competition in 2011; however, the committee thought it was too hard. I blogged on the problem asking for solutions, seeing if there was one that a HS student could have gotten. The following post (this one) gave those solutions. My conclusion is that it could have been put on the competition, but its a close call.

All of the answers submitted had some number repeated.

So I wondered if there was a way to do this with distinct a,...,j.

 I was told about Ronald Grahams result:

For all n at least 78, n can be written as the sum of DISTINCT naturals, where the sum of
the reciprocals is 1.

This is tight: 77 cannot be so written.

Comment on that blog DID include solutions  to my original problem with all distinct numbers

----------------------------------------------------------------------
4) Blog Post A nice case of interdisplanary research tells the story of how the study of history lead to R(5) being determined (see here for the actual paper on the subject). One of the main players in the story is the mathematician

Alma Grand-Rho.

Note that this is an anagram of

Ronald Graham.

What is the probability that two mathematicians have names that are anagrams. I suspect very small. However, see this blog post to see why the probability is not as small as it might be.

-----------------------------------------------------------------------
5) Blog Post Winner of Ramsey Meme Contest This post didn't mention Ronald Graham; however I think he would have liked it.








2 comments:

  1. Comment to item 3):
    A variant of this result showed up as problem 3 on the USA mathematical olympiad in 1978 (USAMO 1978):

    An integer n will be called good if we can write
    n = a_1+a_2+...+a_k, where a_1,a_2,...,a_k are
    positive integers (not necessarily distinct) satisfying
    1/a_1 + 1/a_2 + ... + 1/a_k = 1.
    Given the information that the integers 33 through 73 are
    good, prove that every integer n>=33 is good.

    https://artofproblemsolving.com/wiki/index.php/1978_USAMO_Problems

    ReplyDelete
  2. Comment to item 2): This is still open, although the numbers are much smaller now.

    I believe the most recent pair was found in 2004: https://cs.uwaterloo.ca/journals/JIS/VOL7/Vsemirnov/vsem5.pdf

    ReplyDelete