Sunday, April 24, 2022

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. 

Monday, April 18, 2022

1-week long Summer School for Ugrads Interested in Theory, and my comments on it

Recently a grad student in CS at UMCP emailed me the following email he got,  thinking (correctly) that I should forward it to interested ugrads. 

-------------------------------------------------------

Are you interested in theoretical computer science including topics like algorithms, cryptography, machine learning, and others? If so, please consider applying to the New Horizons in Theoretical Computer Science week-long online summer school! The school will contain several mini-courses from top researchers in the field. The course is free of charge,and we welcome applications from undergraduates majoring in computer science or related fields. We particularly encourage applications from students that are members of groups that are currently under-represented in theoretical computer science.

Students from previous years have shared with us that the mini-lectures, online group activities, and interactions with other students and the friendly TAs were extraordinarily engaging and fun.

For full consideration, please complete the application (it’s short and easy!) by April 25, 2022. The summer school will take place online from June 6 to June 10.

Please see our website for details: see here 

Any questions can be directed to summer-school-admin-2022@ttic.edu.

--------------------------------------------------------------------------

A few points about this

1) I emailed them asking `why do people need to apply if its online and free?'

I had one answer in mind, but they gave me another one

Their Answer: They want to have SMALL online activities in groups. If they had X students and want groups of size g then if X is large, X/g may be too large. 

My Answer: If people REGISTER for something they are more likely to actually show up. (I know of a conference that got MORE people going once they had registation, and even MORE when they began charging for it.) 

2) I emailed them asking if the talks will, at some later point, be on line. They will be. I then realized that there are already LOTS of theory talks online that I have not gotten around to watching, and perhaps never will. Even so, the talks on line may well benefit people who goto the summer school if they want to look back and something. 

3) Online conferences PROS and CONS:

PROS: Free (or very low cost), no hassle getting airfare and hotel, and if talks are recorded then you can see them later (that applies to in-person as well). 

CONS: Less committed to going to it. Can go in a half-ass way. For example, you can go and then in the middle of a talk go do your laundry. Being FORCED to be in a ROOM with the SPEAKER may be good. Also, of course, no informal conversations in the hallways.  Also, less serendipity. 

I want to say It would to be good to see talks outside of my area however, this may only be true for easy talks, perhaps talks in a new field, OR talks that are just barely outside my area so I have some context. 

4) I was surprised I didn't get the email directly since I have more contact with ugrads (and I have this blog) then the grad student who alerted me to it. However, I have learned that information gets to people in random ways so perhaps not to surprising. 

Monday, April 11, 2022

The Roeder Seq Problems was Solved Before I Posed it (Math)

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

Tuesday, April 05, 2022

Masks

Illinois Tech removed the last of their mandatory masking restrictions yesterday. Chicago had zero Covid deaths. Yet I still get messages like this in my twitter feed.

The science is unequivocal for vaccines, which do a good job preventing infection and a strong job saving lives. I just got my second booster on Sunday.

Masks give you some protection but nothing like the vaccines. It's impossible to completely remove the risk of Covid so people need to make their own choices and tradeoffs. If you are vaccinated your chance of serious illness is tiny, whether or not your wear a mask. And mask wearing is not cost-free.

I just don't like wearing masks. Wearing a mask bends my ears and is mildly painful. People can't always understand me when I talk through a mask, and they can't read my facial expressions. People and computers don't recognize me in a mask. Masks fog up my glasses. I can't exercise with a mask, it gets wet with sweat and hard to breath. You can't eat or drink wearing a mask.

Now everyone has their own tolerance and I respect that. I'll wear a mask if someone asks nicely or if it is required, like on public transit and many theaters. If I have a meeting with someone wearing a mask, I'll ask if they would like me to put mine on. In most cases they remove theirs.

On the other hand, the Chicago Symphony concert I planned to attend tonight was cancelled because the conductor, Riccardo Muti, tested positive for Covid (with minor symptoms). For my own selfish reasons, I wish he had worn a mask.



Friday, April 01, 2022

A Ramsey Theory Podcast: No Strangers at this Party

 BILL: Lance, I am going to blog about the Ramsey Theory Podcast called 

                            No strangers at this party

LANCE: Oh, so that will be your April Fools Day post? That is too unbelievable so it won't work as a joke.

BILL: Okay, you got me. But it will work if I get 14 Ramsey Theorists to do Podcasts on Ramsey Theory and pretend its coming from... where should it come from. 

LANCE: A Hungarian Middle School. 

BILL: That's  too realistic. How about Simon Fraser University in Canada?

LANCE: Why there?

BILL: Why not there?

LANCE: Knock yourself out.

---------------------------------------------------------------------------

At Simon Fraser University they have a podcast on Ramsey Theory. They had 14 episodes, each one was an interview with someone who is interested in Ramsey Theory. I don't like the term `Ramsey Theorist' since I doubt anyone does JUST Ramsey Theory (e.g., I do Muffins to!).

Here is the list of people they interviewed. You can find the podcasts at SpotifyAnchorApple Podcasts, and Google Podcasts.

Julian Sahasarabudhe, 

Jaroslav Nesetril

Joel Spencer 

Donald Robertson

Fan Chung

Steve Butler

Tomas Kaiser

David Conlon

Bruce Landman 

William Gasarch

Bryna Kra

Neil Hindman

Adriana Hansberg

Amanda Montejano