(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.

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).

*Divisor Graph*

*graphe divisoriel*

The finite case is indeed a fun coding problem. Suitable for integer programming (at least up to n=600). https://github.com/AustinLBuchanan/divisor_graph_path_problem

ReplyDeleteI wonder about the complexity of the following problem: Given a list of distinct positive integers, is there a permutation of that list that is a Roeder sequence. Equivalently does the divisor graph for those integers have a Hamiltonian path?

ReplyDelete