Discussions I wish we were having

1) Democrats think the best way to avoid school shootings (and other problems with guns) is to have regulations on Guns. They have proposed legislation. The Republicans think its a mental health issue. They have proposed legislation for this. NO THEY HAVEN"T. I would respect the its a mental health issue argument if the people saying this  respected it. They do not. See here. Idea: Politico should leak a (false) memo  by Gov Abbott where he says 

We have a serious mental health crisis in Texas which caused the recent event. I am not just saying this to deflect from the gun issue. I have drawn up a bill to fund mental health care, providing more money, for care and for studies. I call on Republicans and Democrats to pass it ASAP.

I wonder- if this false memo was leaked, would he deny it and say 

I didn't write that. I am using mental health only as a way to deflect from the gun issue. How dare they say that I am reasonable and am proposing actual solutions. 

Or would he be forced to follow through?

2) Democrats think Biden won the election. Some Republicans think Trump won the election. One issue was Arizona. So some republicans organized a recount of Arizona. And when they found out that Biden really did win it they said, as the good Popperian scientists they are, we had a falsifiable hypothesis and it was shown to be false, so now we acknowledge the original hypothesis was wrong. NO THEY DIDN"T. They seem to point to the Arizona audit as proof that they were right, even though it proves the opposite. (Same for all the court cases they lost.)

3) At one time I read some books that challenged evolution (Darwin on Trial by Phillip Johnson was one of them). Some of them DID raise some good points about how science is done (I am NOT being sarcastic). Some of them DID raise some questions like the gap in the fossil record and Michael Behe's notion of irreducible complexity.  (In hindsight these were window dressing and not what they cared about.) MY thought at the time was its good to have people view a branch of science with a different viewpoint. Perhaps the scientists at the Discovery Institute will find something interesting. (The Discovery institute is a think tank and one of their interests is Int. Design.) Alas, the ID people seem to spend their time either challenging the teaching of Evolution in school OR doing really bad science. Could intelligent people who think Evolution is not correct look at it in a different way than scientists do, and do good science, or at least raise good questions,  and come up with something interesting? I used to think so. Now I am not so sure.

4) I wish the debate was what to do about global warming and not is global warming happening? Conjecture: there will come a time when environmentalists finally come around to nuclear power being part of the answer. At that point, Republicans will be against Nuclear power just because the Democrats are for it. 

5) I sometimes get email discussions like the following (I will call the emailer Mel for no good reason.)

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

MEL: Dr. Gasarch, I have shown that R(5)=45.

BILL: Great! Can you email me your 2-coloring of K_{44} that has no mono K_5?

MEL: You are just being stubborn. Look at my proof!

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

Clyde has asked me what if Mel had a nonconstructive proof?

FINE- then MEL can tell me that. But Mel doesn't know math well enough to make that

kind of argument. Here is the discussion I wish we had

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

MEL: Dr. Gasarch, I have shown that R(5)=45.

BILL: Great! Can you email me your coloring of K_{44} that has no mono K_5?

MEL: The proof is non-constructive.

BILL: Is it a probabilistic proof? If so then often the prob is not just nonzero but close to 1. Perhaps you could write a program that does the coin flipping and finds the coloring.

MEL: The proof uses the Local Lovasz Lemma so the probe is not close to 1.

BILL: Even so, that can be coded up.

MEL: Yes but... (AND THIS IS AN INTELLIGENT CONVERSATION)

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

Maybe Mel really did prove R(5)=44, or maybe not, but the above conversation would lead to

enlightenment. 

In the 1960's students protested the Vietnam war!/In 1830 students protested... Math?

 I was at SUNY Stonybrook for college 1976-1980. 

I remember one student protest about a change to the calendar that (I think) would have us go home for winter break and then come back for finals.  I don't recall how that turned out. 

However I had heard about the protests in the 1960's over the Vietnam war. Recall that there was a draft back then so college students were directly affected. 

I was reading a book `Everything you know is wrong' which noted that some people thought the first time there were student protests was in the 1960's but this is not true. (Not quite as startling as finding out that a ships captain cannot perform weddings.) 

It pointed to The 1830 Conic Section Rebellion. I quote Wikipedia (full entry is here)

Prior to the introduction of blackboards, Yale students had been allowed to consult diagrams in their textbooks when solving geometry problems pertaining to conic sections – even on exams. When the students were no longer allowed to consult the text, but were instead required to draw their own diagrams on the blackboard, they refused to take the final exam. As a result forty-three of the ninety-six students – among them, Alfred Stille, and Andrew Calhoun, the son of John C. Calhoun (Vice Pres a the time) – were summarily expelled, and Yale authorities warned neighboring universities against admitting them.

Random Thoughts

1) From my 21st century prospective I am on the students side. It seems analogous to allowing students to use calculators-- which I do allow. 

2) From my 21st century prospective the punishment seems unfair. 

3) The notion of a school telling other schools to not admit student- I do not think this would happen now, and might even be illegal (anti-trust).

4) I am assuming  the students wanted to be able to consult their text out of some principle: we want to learn concepts not busy work.  And again, from my prospective I agree that it was busy work. 

5) Since all of my thoughts are from a 21st century prospective, they may be incorrect, or at least not as transferable to the 1830 as I think. (Paradox: My ideas may not be as true as I think. But if I think that...) 

6) I try to avoid giving busy work. When I teach Decidability and Undecidability I NEVER have the students actually write a Turing Machine that does something. In other cases I also try to make sure they never have to do drudge work.  And I might not even be right in the 21st century- some of my colleagues tell me its good for the students to get their hands dirty (perhaps just a little) with real TM to get a feel for the fact that they can do anything. 

7) The only student protests I hear about nowadays are on political issues. Do you know of any student protests on issues of how they are tested or what the course requirements are, or something of that ilk? I can imagine my discrete math students marching with signs that say: 

DOWN WITH INDUCTION!

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

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. 

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. 

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. 

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. 

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. 

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. ADDED LATER: Antonio NG send me a scan. A  pointer to it: here.) 

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. 

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.

I don't care who you are. If I see you without a mask indoors when infections are rampant and there are many still at risk, I will see you as ignorant of science, narcissistic, and uncaring of the vulnerable around you. I will truly see you unmasked for what you are.

— Bill Comeau 🇨🇦🇺🇦 (@Billius27) April 3, 2022

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.

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 Spotify, Anchor, Apple 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

I don't care about Ketanji Brown Jackson's LSAT scores and she does not care about my GRE scores

Tucker Carlson has asked to see Ketanji Brown Jacksons's LSATs. 

When I applied to College they (not sure who they are) wanted to see my SAT scores. Putting aside the issue of whether the test means anything, they viewed the SATs (and my HS grades and letters from teachers) as a sign of my 

                                                       potential. 

When I applied to Grad school they (a different they) wanted to see my GRE scores. Putting aside the issue of whether the test means anything, they viewed the GREs (and my college grades and letters from professors) as a sign of my

                                                       potential. 

When I applied for jobs as a professor they (another they) wanted to see my resume (papers I wrote) and letters from my advisor and others (I think). They did not look at my grades (just as well- I got a B in both compiler design and operating systems. Darling is amazed I even took operating systems). This was probably the oddest of the application processes since they were looking for both

                                                    potential and achievement.

That is, the evidence that I could do research was that I had done some research. This was before the current  era where grad students had to have x papers in prestige conferences to get a job at a top y school. The letter from my advisor may well have spoken of my potential. 

When I went up for tenure ALL they cared about was PAPERS (and letters saying they were good papers), and some teaching and service. It was based just  on 

                                                          achievement.

A wise man named Lance Fortnow once told me:

The worst thing a letter of recommendation for a tenure case can say is `this person has great potential'

It would have been rather odd for Tucker Carlson to ask to see my SAT scores or GRE scores or by HS, College, or Grad School grades as a criteria for Tenure. Those tests and those grades are there to measure potential to DO something, whereas if you are going up for tenure or a Supreme Court seat, you've already DONE stuff. 

After I got into grad school one of my first thoughts was

Nobody will ever want to see my GRE's again. ( I was right.) 

After KBJ got into Law School she might have thought

Nobody will ever want to see my LSAT scores again. (She was wrong.)

Do you want to be the SIGACT NEWS book review editor?

I ran the SIGACT Book Review Column from 1997-2015 (18 years). You can find all of my columns, plus reviews I did for Fred, here.

When I handed it off to Fred Green I gave him this sage advice:

                   Nobody should do this kind of job for more than about 5 years.

He ran the SIGACT Book Review Column since the end of 2015. You can find some of his columns here.

Fred is taking my advice and looking for a successor.

SO, this blog is a call to ask

                 DO YOU WANT TO BE THE SIGACT NEWS BOOK REVIEW EDITOR?

If so then email

Fred: fgreen@clarku.edu

DO NOT BE SHY! I suspect he won't get many applicants, so if you want the job its probably yours.

PROS

1) You get to skim lots of books and read some of  them.

2) You get some free books.

3) You get plugged into the book community (this helped me when I wrote my two books).

4) You'll have two Veteran Book Review Editors happy to review for you.

5) You get to decide the direction the column goes in.

Both Fred and I did mostly CS theory books. However:

a) I did more combinatorics, educational, history, and Computers & Society books than usual.

b) Fred did more Number Theory and Physics than usual.

(Since I did the job 18 years and Fred for 6, its not clear what usual means.) 

CONS

1) You have to get out a book review column 4 times a year.

2) You have to find reviewers for books and then email them when the reviews are due.

(I think Fred is still waiting for me to review a Biography of Napier. Oh well. On the other hand, I was the one who liked having history books, which may explain why Fred never hassled me about it.) 

ADVICE

Prob should be done by someone who already has Tenure. While seeing and skimming thosebooks is GOOD for your research career, and good in the long-termsomeone pre-tenure really needs to get papers out in the short term. Also, when you get a book think about who might be good to review it--- don't take on to many yourself. 

PARTING GIFT OR WELCOME GIFT

In a recent column I had a review of a 5-book set from the LESS WRONG blog. I amcurrently working on a review of a 4-book set set from the LESS WRONG blog. This willeither be a parting gift for Fred or a Welcome gift to his successor.

The War and Math

During the early parts of the cold war of the 20th century, we saw two almost independent developments of computational complexity, in the west and in the then USSR. There was little communication between the two groups, and countless theorems proven twice, most notably the seminal NP-complete papers of Cook and Levin. To understand more, I recommend the two articles about the early days of complexity by Juris Hartmanis and by Boris Trakhtenbrot.

Russia's invasion and relentless bombing in Ukraine have quickly separated the east and the west again. 

Our first concern needs to be with Ukraine and its citizens. We hope for a quick end to this aggression and Ukraine remaining a free and democratic country. Ukrainian cities have undergone massive damage, and even in the best possible outcome it will take years if not decades to fully rebuild the country. 

Terry Tao has been collecting resources for displaced mathematicians due to the crisis.

We've cut off ties with Russia institutions. In our world, major events to be held in Russia, including the International Congress of Mathematics and the Computer Science in Russia conference are being moved online. I was invited to workshops in St Petersburg in 2020 and 2021, both cancelled due to Covid, and was looking forward to one in 2022, which if it happens, will now happen without me. 

The music world has has cancelled some stars, most notably Valery Gergiev and Anna Netrebko, due to their close ties to Putin. It's rare that we do the same to mathematicians for political reasons though not unheard of. I suspect most of our colleagues in Russia oppose the war in Ukraine, or would if they had accurate information of what was going on. I have several Russian friends and colleagues including two I travelled to Moscow in 2019 to honor and would hate to be disconnected from them.

It's way too early to know how this will all play out. Will we see a quick Russian retreat? Not likely. Will we see a situation that sees a mass migration of Ukranian and Russian mathematicians and computer scientists to Europe and North America, like in the 1990's? Possibly. We will see a repeat of the cold war, disconnected internets and science on both sides happening in isolation? I hope not but we can't rule it out.

Problem X won't be solved in MY lifetime- but what about...

1) In 1989 on the episde The Royale of Star Trek: The Next Generation (which takes place in the far future)  Captain Picard is working on Fermat's last theorem which he says quite explicitly is still open.

When I saw the episode I asked Larry Washington, a Number Theorist at Univ of MD, when he thought FLT would be solved. He said

                                      It will be solved within the next 10 years.

And indeed- Wiles solved it in 1993-sort of. There was a flaw in the proof which he fixed in 1994 with the help of his former student Richard Taylor. Wiles published the correction to the flaw in 1995, so we will date it as having been solved in 1995. Larry Washington was correct.  And in an episode of Star Trek: Deep Space Nine in 1995 (episode name:Facets) Dax says that a previous host, Tobin Dax, had done the most creative work on FLT since Wiles. Maybe Tobin wrote this limerick:

A challenge for many long ages

Had baffled the savants and sages

Yet at last came the light

Seems that Fermat was right

To the margin add 200 pages.

I asked Larry W when he thought Riemann would be solved. He said  

                    In your lifetime but not in mine.

He is about 10 years older than I am and I think we are both in good health. This seems like a rather precise prediction so I am skeptical. But he did get FLT right...

2) In class I sometimes say things like 

I do not think Quantum Computers will factor faster than classical in my lifetime. 

I do not think P vs NP will be solved in my lifetime.

I can imagine P=BPP will be proven in my lifetime. (I said that 10 years ago. I am less imaginative now.) 

I hope the muffin problem is solved in my lifetime (it was, see here).

I didn't quite think about the difference in my age and the students until recently when I was working with Ilya Hajiaghayi (Mohammd H's 9 year old son) on cryptography and he said 

In your recorded lecture you said you don't think quantum computers will be a threat to cryptography  in your lifetime. What about in my lifetime?

Indeed- his lifetime and mine are rather far apart. 

I am reminded that one of the answers to my P vs NP poll made the point that while we have some sense of what will happen in the next 10 years, maybe even 20, math and life can change so much that conjectures beyond that are guesswork. Any  prediction for x years from now you should have confidence < 1/ln(x) of it being true.

Random thoughts on the Russian Invasion of Ukraine

 1) My first thought was: Doesn't Putin know that his army (and his society) is corrupt and people are promoted on loyalty rather than talent, hence the invasion is not going to work? But then note

a) He invaded Georgia (the country not the state)

b) He annexed Crimea

c) NATO agreeing on sanctions? They can't even agree on what to have for lunch.  

d) The above question ASSUMES that he will lose. This is not clear yet.

2) The US and other countries are imposing sanctions. Visa, MC, and Netflix have withdrawn from Russia. Will these cause Putin to stop, or will they just impose hardships on the citizens without having an affect? I ask non-rhetorically. Foreign Policy is hard, though I suspect Biden has hired experts and is listening to them. Doesn't mean they are right. 

3) This seems like a case where its obvious that Putin is in the wrong so I was surprised to see some Pro-Putin arguments. To be fair, some were more that we should not get involved, which is not quite Pro Putin. Here are some and my thoughts on them.

a) Putin never called me a racist and never made my kids learn Critical Race Theory. This is meant as a GOTCHA comment. To take it seriously one would have to (1) examine what American's are learning in grade school, (2) examine what Russians are learning in grade school, (3) see which country is giving their students a more honest view of things (particularly history), and (4) decide that whichever school is teaching more honest material deserves are support. 

b) Putin is a strong leader and I admire strong leaders. Really? If  Biden was a strong leader who could push through the Build-Back-Better plan, would you admire that? You can't just admire strong leaders in the abstract, you have to see where they lead. (Same with admiring people who have principles.)

c) Putin stands for good Christian values. OH- so Putin likes to help the poor and does not approve of divorce or pre-marital sex. Oh, that NOT what you mean? Oh, you just mean that he does not like gay people or abortion. OH, thats not correct- Russia has the second most number of abortions of any country (see here) So the only issue where Russia shares your values is in not liking gay people. Is that enough  commonality is enough to justify invading a country? This does raise the serious question: who do you support in a war? The country that shrares your values? The country that didn't start it (sometimes hard to tell, though not in this case)? The country you have a treaty with? These are good and serious questions. 

d) How come the world does not like Putin's war based on lies and had no problem with W's war on Iraq that was based on lies? This is actually a good question. Being an academic by first impulse is to write a paper on it. There are differences between the invasion of Ukraine and Gulf War II, but still, lets assume that they really are somewhat equivalent. The person asking the question was probably AGAINST Gulf War II. Hence they should be against the invasion of Ukraine as well. So this is a good question about the America and NATO's Double standard and hypocrisy but is not a reason to be pro-Putin. (I was emailed that there are many conflicts that American and NATO do not care about that are as bad as Putin's invasion.) 

e) Russia had real concerns about security. The last time Russia was invaded was WW II (if I am wrong then please correct me in the comments). Even so, I've heard analogies made to America freaking out when Cuba had Nuclear missiles. There were no nukes in Ukraine. Ukraine was not going to join NATO anytime soon. I wonder if this was a pretense on Putin's part and not a real reason. 

f) See here. I give an excerpt (I am not making this up). 

But as its Covid mission has become less clear, the group’s channels have turned to Russia’s invasion of Ukraine, where conspiracy-minded thinking has flourished. While some group members have admonished Russian President Vladimir Putin for the invasion, QAnon and anti-vaccine contingents within the groups have seized on a false conspiracy theory that the war is a cover for a military operation backed by former President Donald Trump in Ukraine.

The conspiracy theory, which is baseless and has roots in QAnon mythology, alleges that Trump and Putin are secretly working together to stop bioweapons from being made by Dr. Anthony Fauci in Ukraine and that shelling in Ukraine has targeted the secret laboratories. Fauci, director of the National Institute of Allergy and Infectious Diseases, has emerged in the past year as a main target for far-right conspiracy theories.

3) I was somewhat surprised when Hungary came out against Putin. But Putin's arrangments with his allies are transactional- there is no real love there. I was much more surprised when Switzerland came out against Putin. Switzerland has been neutral since 1515 (I think I read that some place). 

REU programs in general, and two at Univ of MD this summer.

REU stands for Research Experience for Undergraduates. 

REU programs are funded by the NSF. The NSF website of REU programs is here. 

Univ if MD at College Park dept of Comp Sci is running two REU programs this summer:

I (William Gasarch) am running  REU-CAAR (Combinatorics and AI Applied to Real problems) whose theme is applying theory to practice. The website for it is here.

 Jacquelyn Michaelis and Mihai Pop are running REU-BRIDGe (Bioinformatics Research In Data science for Genomics) which, as you can probably tell from the name, is in bio-comp. The website for it is here.

Most REU programs have the following: 

1) There is an admissions period where many people apply (I had around 200 applicants last year) of which only about 10 get in. Some have money for a few extra students. This year both REU-CAAR and REU-BRIDGe have applications due March 22; however, in the past I have admitted students before then, so students who apply March 21 may be at a severe disadvantage. 

2) Students apply from across the United states and these programs are competitive, so good to apply to several that you would definitely goto. Students ask me how many- I'll say 10 though temper that with only applying to those you REALLY would goto, and if there are MORE THAN 10 that look awesome, you could apply to more. 

3) Students stay in the dorms (the last two years some programs cancelled, and some were virtual- mine was virtual) and get stipend of $6000, and a meal card. The program is 10 weeks.

4) Students work on projects in teams of 2-5. Some programs have the students pick what projects they would be happy to work on when they apply (mine does that) while others assign projects once students arrive (REU-BRIDGe will do that). The later makes sense if the program is very focused so the projects do not differ that much. 

5) These programs are excellent for giving ugrads a chance to do research (NSF wants at least half of the students to come from non-research schools) and a sense of what grad school is like. So I recommend students thinking of grad school, or just want to do research, to apply to these programs. 

6) Some students get papers out of the research. In these cases the research usually continues after the program is over. 

7) It is healthy for a student to go to an REU program that is at a DIFFERENT school then where they are an ugrad for broadening. There may be mitigating circumstances where this is not possible. 

I did an Instagram Live with Mohammad Hajiaghayi

 Today I did an Instagram Live with Mohammad H. He was the host, asking me questions. We discussed 

Our lives

Blogging (which I do but he does not)

Parenting (which he does but I do not)

P vs NP (which we both care about) 

Zero Knowledge and Zcash

and

How to inspire young minds (since I mentor many students, including Mohammad's 9 year old son)

The conversation is on you-tube here

Enjoy!

I will be on instagram/If you have two reals in a box- Answer (Guest Post by David Marcus)

I will be on instragram:

We,  Prof. Mohammad Hajiaghayi and Prof. William Gasarch plan to have an Instagram Live at @mhajiaghayi this SAT FEB 26, 1:30PM EDT (in English).

 We talk about our lives as well as blogging, research, and how to inspire young minds. Please join if you can.

#PvsNP #blogging #youngminds #instagram

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

This is the answer to the problem posted in the last post which was a guest post by David Marcus. This post is also a guest post by him. 

We restate the problem:

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

PICK THE LARGEST NUMBER:

There are two distinct reals in a box (how do they fit! aren't reals infinite!). They are called the first and second number. 

You want to pick the larger one. You can pick one of the numbers at random and look at it

before deciding which one you want. 

Is there a strategy that will win with probability > 1/2.

CLARIFICATIONS:

1) We do not want a strategy that does well on average or in the long run. Even if the games is played just once, we want the probability of winning to be > 1/2.

2) It must have prob of winning > 1/2 for EVERY pair of reals.

3) Here is an example of a strategy that does NOT work: Pick the first number with prob 1/2. If its positive then keep it, else dump it. If the numbers are{1,2} this only works half the time.

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

There is a strategy. In fact, we give two.

STRATEGY ONE

Before looking at any number, pick a number x on your own from the reals according to a distribution with full support (every open interval has prob greater than 0). Then pick a number from the box (prob 1/2-1/2), which we call y. If x<y then keep y. If y\le x then take the other number.

If x is between the two numbers, then the strategy works. If not then the strategy does not hurt, so the prob in that case is 1/2. Hence you do better than 1/2. 

STRATEGY TWO

Let f: R--> (0,1) be strictly increasing. Pick a number from the box, call it y. Keep it with prob f(y).

I will be on Instagram/If you have two reals in a box.... (Guest Post by David Marcus)

I will be on instragram:

We,  Prof. Mohammad Hajiaghayi and Prof. William Gasarch plan to have an Instagram Live at @mhajiaghayi this SAT FEB 26, 1:30PM EDT (in English).

 We talk about our lives as well as blogging, research, and how to inspire young minds. Please join if you can.

#PvsNP #blogging #youngminds #instagram

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

 (David Marcus emailed me this for a guest post, inspired by my posts on a similar problem where I gave the question here and the answer here.)

This is a well known problem, but I have learned over time that not everyone knows things that are well known.

PICK THE LARGEST NUMBER:

There are two distinct reals in a box (how do they fit! aren't reals infinite!). They are called the first and second number. 

You want to pick the larger one. You can pick one of the numbers at random and look at it

before deciding which one you want. 

Is there a strategy that will win with probability > 1/2.

CLARIFICATIONS:

1) We do not want a strategy that does well on average or in the long run. Even if the games is played just once, we want the probability of winning to be > 1/2.

2) It must have prob of winning > 1/2 for EVERY pair of reals.

3) Here is an example of a strategy that does NOT work: Pick the first number with prob 1/2. If its positive then keep it, else dump it. If the numbers are{1,2} this only works half the time.

(Warning: I will NOT block comments that give away the answer, so if you want to work on it without knowing the answer, do not look at comments.)