(Joint Post by Bill Gasarch, David Harris, and Tomas
Harris)
The divisor graph D(n) is an undirected graph with
vertex set V={1,...,n}$ and
edge set E={(a,b) : a divides b
or b divides a }
We denote the length of the longest simple path in D(n) by
L(n).
EXAMPLE: if n=10 then one long-ish sequence is
1,8,4,2,6,3,9
so L(10) GE 7. I leave it to the reader to do better OR to
show its optimal.
In 2017 Oliver Roeder asked for L(100) (see here)
In a later post Roeder reported that Anders Kaseorg claimed L(100)=77
(see here).
Anders gave a sequence and claimed that, by a computer search, this was
optimal. The column also claims that other people also claimed 77 and nobody
got a sequence of length 78, so the answer probably is 77 (it is now known that
it IS 77). Roeder also mentions the case of n=1000 for which Kaseorg
showed L(1000) GE 418. No nontrivial lower bounds are known.
In 2019 I (Gasarch) asked about asymptotic results for
L(n) (see my blog post here and
my open problems column here.)
I began working on it with David and Tomas Harris. David proved that
Omega( n/( (log n)^{1.68} ) LE L(n)
LE O( n/( (log n)^{0.79} ).
We also studied human-readable proofs that L(100) LE X for
some reasonable X, though getting a human-readable proof for X=77 seemed
impossible. We did get L(100) LE 83, in a human-readable proof. (Some
commenters on my post to sketched a proof that L(100) LE 83 and another
that L(100) LE 80 as well.)
But it turned out that this problem had already been
studied, predating Roeder's column. (This blog post is all about the math, bout
the math, no treble. My next post will be about how we didn't know the
literature until our paper was close to being finished.)
In 1982 Pomerance showed L(n) LE o(n) (see here).
Pollington had earlier shown
L(n) GE ne^{polylog(n)};
however, the paper is not online and hence is lost to
history forever. (If you can find an online copy please email me the pointer
and I will edit this post.)
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).
(ADDED LATER: I got a very angry email telling me that the paper was in English and that I am a moron. It turns out that the abstract is in English but the paper is in French, hence the person who send the letter only read the abstract which explains their mistake.)
He conjectures that L(n) SIM cn/log n where c is
likely in the interval [3,7]. (Apparently, no other information is known about
the relevant constant factors in the estimates.)
Interestingly, the work of Tenenbaum and Saias also
demonstrates why the study of L(n) is not an idle problem in recreational
mathematics. The upper bounds come from results on certain density conditions
for prime factorization of random integers. That is, given an integer x chosen
uniformly at random from the range {1,..., n} with prime factorization p1 GE p2
GE ... one wants to show that, with high probability, the primes pi are close
to each other in a certain sense. Most recent results on L(n) have been tied
closely with improved asymptotic estimates for deep number theory problems.
Determining the value of L(100) (i.e., Roeder's problem) was
mentioned in Saias's paper. He claims that L(100) = 77 was discovered by Arnaud
Chadozeau, who himself has written a number of papers on other properties of
D(n). Since this paper was in 2021 it was after Roeder's column; however, we
believe that the different discoveries of L(100) are independent. The recent
work around Roeder's column appears to be done independently from the extensive
French-language literature on the topic.
The following problems are likely still open:
a) Find L(n) exactly for as many n as you can. This
would clearly need a computer program.
A listing of L(n) for n = 1 ... 200, computed by Rob Pratt
and Nathan McNew,
appears as OEIS #A337125. This also includes additional
references.
b) Find human-readable proofs for upper bounds on L(n)
(likely not exact) for as many
n as you can.
ADDED LATER: Gaétan Berthe emailed me
-----------------------------------------------------------------
I'm the author of the last comment on your article about
Roeder Sequence , as your curious about the subject I can share what we've done
with my friend Paul Revenant those last few years for fun.
It all started with a competition between our classmates (see here though note that its in French) for the 100 and 1000 cases, after a few months Paul using a MIP solver gurobi
was able to found a solution of size 666, and last year by studying the
structure of the 666 solution we were able, with the help of gurobi again, to
prove that there was no 667 solution either.
Paul then achieve to find very probable value of the sequence for 1 to 1000 (we
didn't automatize the proof of 666 but it should be doable). On my side I tried
to look for good solutions for the 10000 case, again using gurobi and the structure
that appeared in the solution of size 666. The structure enable to cut the
problem in two subpart, so the search goes faster I was able to find a solution
of size 5505.
So I would say that the two mains reasons we're able to prove optimality for high
numbers as 1000 are:
- MIP solver such as gurobi are very powerful tools.
- The longest path in the divisor graph are highly structured.
I joined our informal proof of the 666 case (the solution at the end), what is
interesting is to understand how the solution is composed of different blocks
depending of the prime decomposition of the elements. I joined lower bound from
1 to 1000 computed by Paul, that are very likely to be optimal.
---------------------------------------------------------------------------------------------------------
He also emailed me
1) a list of the numbers I call L(n) for n=1 to 1000.
These have not been refereed though I think they are correct. The list is here
AND
2) a PROOF that L(1000)\le 666 (and they HAVE a
sequence of length 666, so L(1000)=666).
Again, not refereed, but you can read the proof
yourself here WARNING- the proof is in ENGLISH, so you cannot use it to improve your
mathematical French.
