Sunday, May 15, 2022

Is Kamala Harris our first female PREZ? No. Do I have a theorem named after me. No. But in both cases...

On Nov 19, 2021 Joe Biden got a colonoscopy and hence the 25th amendment was used to make Kamala Harris the president temporarily (this source: here says 85 minutes, though I thought I heard a few hours from other sources). 

Does this make Kamala Harris our first female president?

I would say NO and I suspect you agree. A friend of mine suggested the phrasing Kamala Harris is the first women to assume the powers of the president under the 25th amendment.  True.  I don't think it means much. She tacked on the under the 25th amendment since Edith Wilson was essentially president when Woodrow Wilson had a stroke (see here).


A student asked me Is there a theorem that is referred to as Gasarch's Theorem or something like that?

I will answer YES and NO, but really the answer is NO.

YES: In 1999 Gasarch and Kruskal had a paper in Mathematics Magazine: 

When can one load of Dice so that the sum is uniformly distributed?

In that paper we have a theorem that gives an exact condition on

(n_1,...,n_k) for when there is a loaded n_1-sided dice, n_2-sided dice,...,n_k-sided dice so that 

the sums are all equally likely.

In 2018 Ian Morrison published a paper in the American Math Monthly:

Sacks of dice with fair totals

which used our work and referred to our main theorem as The Gasarch-Kruskal Theorem.

Hence there is a theorem with my name on it!

NO: The Gasarch-Kruskal paper has only 8 citations (according to Google Scholar). This is more than I would have thought, but its not a lot. The fact that ONE person calls the main theorem THE GASARCH-KRUSKAL THEOREM hardly makes it a named theorem. 

QUESTION: So what criteria can one use?

We could say that X has a theorem with their name on it if there is a Wikipedia entry about the theorem, using that name. That works to a point, but might fun afoul of Goodhart's law (if a measure becomes a target it stops being a measure) in that, for example, I could write a Wikipedia entry on The Gasarch-Kruskal Theorem. 

We could say that 10 people need to refer to the theorem by the name of its authors. Why 10? Any number seems arbitrary. 

CAVEAT: If someone asked Clyde Kruskal is there a theorem that bears your name that is trickier, since The Kruskal Tree Theorem bears his name.... but its not his theorem. Reminds me of the (fictional) scenario where a Alice steals  a Field's medal and tells Bob I have a Field's Medal! and Bob  thinks Alice is a world-class mathematician since she has a fields medal, rather than thinking Alice is a world class thief. See here for my post on that. 

(I originally had Kruskal Three Theorem instead of Tree Theorem. I have corrected this but I hope it inspires Clyde to prove a theorem about the number Three so he can have a named theorem. And if he is lucky, over time, people will confuse it with the Kruskal Tree Theorem!) 





Tuesday, May 10, 2022

Queen Elizabeth is the 3rd longest reigning monarch; The problem with definitions

 A few days ago Queen Elizabeth passed Johann II of Liechtenstein to be the third longest reigning monarch (see here). 

A summary of the top 4:


4) Johann II, Liechtenstein ruled from Nov 12 1858 until his death on Feb 11, 1929. When he became King he was 18. He was king for 70 years, 91 days. 

3) Queen Elizabeth II (thats a two, not an eleven) ruled from Feb 2, 1952 until now. When she became Queen she was  25. I am writing this on May 10 at which time she ruled 70 years, 94 days. 

2) Bhumibol Adulyadej (Thailand) ruled from June 9, 1946 until Oct 13, 2016. When he became King he was 19. He was king for 70 years, 126 days. 

1) Louis XIV ruled from May 14, 1643 until Sept 1, 1715. When he became King he was 4 years and 8 months. He was king for 72 years, 110 days. 


Johann, Elizabeth, and Bhumibol started their reigns a bit young (they would have to to have ruled so long) but their first day of their reign they knew what the job was, what they are supposed to do etc. 

Here is my complaint: Louis XIV being king at the age of 4 years 8 months should not count (someone who proofread this post wondered if 4 years 9 months would count. No.) Shouldn't we define the reign of a king as the point at which he can make real decisions as king? Or something like that. 

For the record of the longest marriage there is a similar problem. The three longest marriages are legit in that the people got married at a reasonable age (I think all were married after they were 17). The fourth longest marriage of all time involved two people that were married when they were 5. That should not count (see here).

Is there a way to define monarch's reigns and also marriage length so that it corresponds to our intuitions? 

In Math we can use rigorous definitions but in English its harder. 




Wednesday, May 04, 2022

The (R)evolution of Steve Jobs


I don't mention it that often in this blog, but I fell in love with opera in the 90's and watch as much as I can, often fitting opera into my travels or vice-versa. Rarely do the tech world and operas collide but they did so this weekend in visit to Atlanta, I saw the (R)evolution of Steve Jobs, yes an opera about the iconic Apple founder that was first performed in Santa Fe five years ago. This production played in Austin and Kansas City earlier this year.

The story focused on relationships, Steve Wozniak, his wife Laurene, his guru Kōbun Chino Otogawa and Chrisann Brennan, the mother of Job's daughter Lisa, and on Steve Jobs focus on perfection and his company, as he often shunned others and even his own health. The music worked and the singers were generally strong. There were about 20 large monitors on the set which were used to enhance the story in pretty clever ways. The opera bounced around in time from when Steve Jobs father bought him a worktable to his memorial service. 

100 minutes is short for an opera, especially one on a person as complicated as Jobs, and some of the story lines and characters could have benefited by a longer exposition, or perhaps a more focused story could have had a larger emotional punch.

Laurene had a message at the memorial service but really meant for the audience in the opera.
And after this is over,
The very second this is over,
For better or worse,
Everyone will
Reach in their pockets,
Or purses,
And — guess what? —
Look at their phones,
Their “one device.”
I’m not sure Version 2.0 of Steve
Would want that.
Version 2.0 might say:
“Look up, look out, look around.
Look at the stars,
Look at the sky,
Take in the light,
Take another sip,
Take another bite,
Steal another kiss,
Dance another dance,
Glance at the smile
Of the person right there next to you.”
The (R)evolution of Steve Jobs has a couple of more performances in Atlanta this weekend, including a livestream, and heads to Calgary and other venues in the future.

Next year, The Life and Death(s) of Alan Turing at Chicago Opera Theater. 

Sunday, May 01, 2022

Elon Musk To Buy Complexityblog

Elon Musk has offered to buy out Complexityblog. The money is too good to turn down. As part of the contract we can't say how much or in what cryptocurrency, but suffice to say it will be more than the royalties from our books. Or not.

Readers be aware of the following changes to the blog:

1) We can no longer send Donald's Trump comments into our spam folder.

2) All of our posts will be written by Tesla autopilot.

3) Complete free speech in the comments. Or not. Depends on Elon's mood that day

4) Purchases made through this blog can be in bitcoin or other cryptocurrencies. Or not. Depends on Elon's mood that day.

5) Switch the business model (Lance- we have a business model?) from advertisements to a subscription service. How much will people pay per year to access complexity blog? 

6) Lance and I have been invited to fly to orbit on a SpaceX rocket so we can post from space. Or was it posting from the backseat of a Tesla? Depends on how you read the contract.

7)  April Fools day posts will henceforth be on May 1. 

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.