The Roeder Problem was Solved Before I Posed it (how we missed it)

(This is a joint post with David and Tomas Harris.)

In my an earlier post (see here) I discussed the MATH behind a problem that I worked on, with David and Tomas Harris, that we later found out had already been solved. In this post we discuss HOW this happened. 

Recall that Bill Gasarch read a column of Oliver Roeder (see here) on Nate Silvers' blog where he challenged his readers to the following:

Find the longest sequence using numbers from {1,...,100} such that every number is either a factor or multiple of the previous number. (A later column (see here ) revealed the answer to be 77 via a computer search, which we note is not a human-readable proof.)

Bill wrote a blog post (see here) and an open problems column (see here ) asking about the general case of {1,...,n}. Before doing this Bill DID try to check the literature to see what was known, but he didn't check very hard since this was not going to be a published paper. Also, he vaguely thought that if it was a known problem then one of his readers would tell him.

QUESTION: Is it appropriate to blog on things that you have not done a search of the literature on?

ANSWER: Yes, but you should SAY SO in the blog post.

As measured by comments, the post did not generate much interest- 10 comments. 2 were me (Gasarch) responding to comments.

David (who has a PhD from UMCP under Aravind Srinivasan) asked Bill to find a HS project for his son Tomas. Bill gave Tomas the sequence problem (as he called it) to look at- perhaps write a program to find what happens for {1,...,n} for small n, perhaps find human-readable proofs of weaker bound, for small n or for n=100.

David got interested in the MATH behind the problem so the project became three projects: Tomas would look at the programing aspects and the human-readable aspects, David would look at the Math, and Bill would...  hmmm, not clear what Bill would do, but he did write up a great deal of it and cleaned up some of the proofs.

David showed

Omega( n/( (log n)^{1.68} )  LE  L(n)  LE  O( n/( (log n)^{0.79} ). 

Tomas and Bill obtained a human-readable proof that L(100) LE 83. (Comments on my blog sketched a proof that L(100) LE 83, and someone else that L(100) LE 80). See my previous post (here) for more on the known numbers for L. 

At that point David did a brief literature search; however, he didn't know what to look for.

BILL still thought of this as a HS project so he didn't think much about a paper coming out of it, or if it was original. So he didn't do the due diligence of seeing what was already known.

David and Tomas were busy working on it, so they only did a few cursory checks of the literature.

With the two results above,  we had a paper! David then looked much more carefully at the literature. He DID find some earlier papers -- he did a Google search for Roeder's puzzle, which mentioned another mathematician, who was quoted in a blog by another mathematician, who eventually mentioned Pomerance's old paper on the topic. Once he found a reference to an actual math paper it was easy to use Google Scholar to find forward/backward citations and find the current state of the art.

His email had subject title

                        SHUT IT ALL DOWN!!!

Which made Bill think it involved a nuclear reactor undergoing The China Syndrome rather than just telling us that other people did had better and earlier results. 

In 1995 Gerald Tenenbaum showed, in a paper written in French,  that there exists a,b such that 

                               n/(log n)^a LE L(n) LE n/(log n)^b (see here). 

More recently, in 2021, Saias showed, in a paper written in French, that 

                                      L(n) GE (0.3 - o(1)) n/log n (see here). 

SO, why didn't Bill, David, Tomas find that it was already known until late in the process:

1) They didn't know the right search term: Divisor Graph

2) The literature was in French so the right search term is graphe divisoriel

3) The transition from FUN HS PROJECT to SERIOUS MATH PAPER was somewhat abrupt and caught Bill by surprise.

Was this a disappointment?

1) We all learned some math from it, so that was nice.

2) We were in a position to read and understand the paper since we knew all of the difficulties --- however, it was in French which I do not read. David reads some, Tomas does not read French.  I prefer to be scooped in English, but even then  I might not be able to read up on the problem since  math is... hard. When did math get so hard? see my blog on that here. When did CS theory get so hard? See my blog on that here.)

Could this happen again?

1) Yes. Language barriers are hard to overcome. Though this is rare nowadays--- not much serious mathematics seems to be done outside English. French mathematicians seem to like to keep their language alive, although they probably know English as well. There may be a few other countries (China, perhaps), where English language skills are not advanced and researchers are cut off from the English literature.

2) Yes. I've heard of cases where many people discovered the same theorem but were unaware of each others results since they were in different fields.

3) Is it easier or harder to reprove a theorem now then it was X years ago?

We have better search tools, but we also have more to search.