Pairs of Celebrities died/born the same day

Farrah Fawcett and Michael Jackson died the same day (June 25, 2009).

1. Who is the most famous pair of people that died the same day? While its hard to measure fame objectively, there are two candidates that come to mind. (1) If you give a bonus for being in very different fields then the answer could be Orville Wright and Gandhi (Jan 30, 1948). (2) If you have an American bias then perhaps John Adams and Thomas Jefferson (July 4, 1826). Possible Bonus for July 4 being the day. (James Monroe also died on July 4, though in 1831. What is the probability that three of the US presidens died the same day? Prob=1 since they did.)
2. If you are famous and want people to notice your death there here are some tips:
   1. DO NOT die the same day as a someone more famous. Example: Farrah Fawcett overshadowed by Michael Jackson.
   2. DO NOT die close to the day someone more famous dies. Examples: (1) Ed McMahon died the day before Michael Jackson. (2) Mother Theresa died a few days after Princess Di (It is likely that Mother Theresa wanted to not have a big deal made of her death, so perhaps this was a win for her.)
   3. DO NOT die the last week of the year. James Brown and Gerald Ford both died the last week in 2006. By that time all the lists of famous people who died in 2006 were already made. So James Brown and Gerald Ford never made those lists.
3. Who were the most famous pair of people that were born the same day? While its hard to measure fame objectively a good candidate pair is Abe Lincoln and Charles Darwin (Feb 12, 1809). Others of interest (from this website): George W. Bush and Sylvester Stallone (July 6, 1946), (One is a pretend war hero, the other starred in the ROCKY movies.) Sigmund Freud and Robert Peary (May 6, 1856), Winston Churchill and Lucy Maud Montgomery (Nov 30, 1874), (I didn't know who Montgomery was. Either fame is fleeting or I am not up on my writers of books for young girls-- she wrote Anne of Green Gables.) Ariel Sharon and Fats Domino (Feb 26, 1928).

George HW Bush passed away- some non-partisan math comments

George HW Bush passed away recently. When he was alive there were 5 living ex presidents. Now there are 4. What is the max and min number of ex presidents? This we will answer. What is the prob of having many living ex-presidents?

What is the max number of ex-presidents alive at the same time? List the times this has happened. Your answer should be a list of statements of the following form:

 Shortly after X took office there were Y ex-presidents: Z(1), Z(2), ... , Z(Y).

I leave a little white space in case you want to try to figure it out, though the point of this post is not to quiz you.
















ANSWER: The max number of ex-presidents alive at the
same time is five. This has happened four times.

--------------------------------------------
ONE: In 1861 just after Lincoln took office there were five living ex-presidents:
Martin van Buren (died in 1862), John Tyler (died in 1862), Millard Fillmore (died in 1874), Franklin Pierce (died in 1869), James Buchanan (died in 1868).

Key factors: (1) Between 1836 and 1860 there were no 2-term presidents, (2) Martin van Buren lived a long time after being president.

TWO: In 1993 just after Clinton took office there were five living ex-presidents:
Richard M. Nixon (died in 1994), Gerald Ford (died in 2006), Jimmy Carter (still alive as of Dec 2018), Ronald Reagan (died in 2004), George HW Bush (died in 2018).

Key factors: (1) Nixon, Ford, Carter, Bush Sr were the equivalent of 4 one-terms, and (2) Reagan lived a long time after being president.

THREE: In 2001 just after George W. Bush took office there were five living ex-presidents:
Gerald Ford (died in 2006), Jimmy Carter (still alive as of Dec 2018), Ronald Reagan (died in 2004), George Bush (died in 2018).  Bill Clinton (still alive as of Dec 2018).

Key factors: (1) Ford, Carter, Bush Sr. were effectively 3 one-terms, and (2) Reagan lived a long time after being president.

FOUR: In 2017 just after Donald Trump took office there were five living ex-presidents:
Jimmy Carter (still alive as of Dec 2018), George  HW Bush (died in 2018).  Bill Clinton (still alive as of Dec 2018).  George W Bush (still alive as of Dec 2018).  Barack Obama (still alive as of Dec 2018).

Key factors: (1) Carter, Bush were both one-termers,  (2) Clinton and W are relatively young for presidents and in good health, and  (3) Carter and Bush Sr. lived  a long time (Carter is still living!)

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

I want to see this record broken! I want to see 6 living ex presidents! (Darling asks why I want to see that. Its a good question which I will partially address later.) Hence I want to see Donald Trump impeached or resign or leave office!  I was hoping it would would happen before one of Carter, Bush Sr, Clinton, W, Obama died. Oh well.

So now what? Is it possible that we will see 6 living ex-presidents in our lifetime. Factors: prez longevity, prez age, one-term vs two-term, and since I am asking about in OUR lifetime, our longevity.

Lets assume that neither The Donald nor any other president resigns or gets impeached or leaves office before their term is up. We assume that the presidents after Trump are  Alice, Bob, Carol.

Scenarios:

ONE: Donald Trump loses to Alice in 2020, Alice loses to Bob in 2024. None of the ex presidents dies before 2025. Then we would have, in the first day of the Bob presidency, which would be  in  2025,  6 living ex presidents:  Carter, Clinton, W, Obama, Trump, Alice.

This needs Carter to live to be about 100 (the others are much younger). Possible!

TWO: Donald Trump loses  to Alice in 2020, Alice loses to Bob in 2024 . Bob loses to Carol in 2028. Carter passes away before 2025 but the other ex presidents are alive in 2029. Then we would have, in the first day of the Carol presidency, which would be in 2029, 6 living ex presidents:Clinton, W, Obama, Trump, Alice, Bob.

This needs W, Clinton, Trump  to live to be about 83 and Obama to live to be 72.  Possible!

I'll stop here, but you can make up your own SCENARIO THREE which requires some people to live to 87.

Scenario ONE seems unlikely. TWO and THREE are plausible; however, there is another factor. I am assuming a long string of one-termers (that was flagged as not-a-word. Oh well.)  Lately incumbency has a big advantage: Clinton, W, Obama were all two-termers. Incumbency is powerful for two reasons that reinforce each other:

The incumbent can DO things, can LOOK presidential.

Since the incumbent has these advantages people are scared to run against him or her.

--------------------------------------
Math problem: What is the probability that we will see 6 living ex presidents by 2029? To solve this you would need to know

Longevity statistics. But of what group? by Age? by profession? of ex-presidents? That seems to narrow for good statistics.

Incumency statistics. How likely is it for a Prez to be re-elected? Again, too small a sample size. And Trump seems like an outlier. I suspect that if Jeb or Hillary were president they would get re-elected because of the incumbency advantage. But Trump is so unusual that it might not hold. One thing in his favor: it is unlikely there will be a challenge from his own party. One thing in his disfavor would be a third party challenge. But ENOUGH. My point is that it would be hard to do good stats here.

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


So why do I care about seeing 6 living ex-presidents in my lifetime? I have a reason but its not a good reason.

Early in the Nixon Presidency LBJ died. I noticed that there were ZERO living ex-presidents. I knew that LBJ was dead, and JFK was dead, and I suspected (correctly) that Eisenhower and Truman were dead, and I knew FDR was dead. Before that we have Hoover and others who were of course dead. I was SO PROUD of myself for KNOWING this (to be fair I was 12 years old). This sparked my interest in presidents and especially in the question of most/least living ex-prez.

Now for the obvious question on the other end of the spectrum:

What is the min number of ex-presidents alive at the same time? And when did it occur (list all times)

White space for those who want to try to figure it out or look it up.
























ANSWER: Zero. This happened six times.

ONE: When George Washington was president there obviously were zero living ex-presidents.

TWO: Shortly after John Adams became president George Washington died. At that time there were zero ex-presidents.

THREE: During Ulysses S Grant's term Andrew Johnson, the prior president died. Lincoln was dead by assassination and all prior presidents were dead of old age  or similar (e.g., James Buchanan died at the age of 77, Franklin Pierce (an ancestor of Barbara Bush (nee Pierce) was 65 and died of cirrhosis of the liver, from alcoholism.)

FOUR: During Theodore Roosevelt's term Grover Cleveland died, and all other ex-presidents were dead.  Recall that the prior prez, McKinley, had been assassinated.

FIVE: During Herbert Hoover's term, following Calvin Coolidge's death (Hoover's predecessor), there were no ex-presidents.  This partially explains why Coolidge didn't run- he had health problems.  Note that Harding died in office.

SIX: During Nixon's term, in 1973, Lyndon Johnson died. At that time there were zero ex-presidents.  This was because Lyndon Johnson died young (65), Kennedy was assassinated, Eisenhower was old while president.


NOTE: I would have thought that since FDR served so long and died in office either during FDR's term or Harry Truman's term there would be a time with no living ex-presidents.  Early in FDR's term there was only one living ex-president: Hebert Hoover. However, he didn't die until 1964. Hence he lived through the presidencies of FDR, Truman, Eisenhower, Kennedy, and part of Johnson's.  This is NOT the most presidents an ex-president has lived through after they step down. That honor might go to Carter who has lived through the presidencies of Reagan, Bush Sr, Clinton, W, Obama, and, as of this writing, a few years of Trump.  I have not checked if this is a record but I will once Carter passes away.

NOTE: In most of the cases above a recent president had died prematurely. Grant- Lincoln, Roosevelt- McKinley, Hoover- Coolidge, Nixon- Johnson and Kennedy.)

NOT: Since Obama, W, and Clinton are all relatively young, and presidents dying in office is now very rare (the last one was JFK in 1963)   I doubt this will happen again. But politics and history can surprise you.

Presidents Day Poll- what does the youth of american think about....

(In honor of President's day which was two days ago.)

On Presidents Day last year I had my classes fill out a form saying who they thought was the best, second best, third best, and worst president. I gave them a list and asked them to just mark 1,2,3 (for best, second best, third best) , BAD (for worst) on it. I omitted Obama, Bush Jr, Clinton from the list since they are too recent. So, what does the youth of America think? Or at least the youth taking Honors Discrete Math or Automata theory?

Here is the list or presidents ranked by roughly how well they did. (Some are not included since they did not get any voters pos or neg.) I (somewhat arbitrarily) gave 3 points for each ONE, 2 points for each TWO, 1 point for each THREE and -3 points for each BAD. Are these the best weights to use? Is there a way of arguing which weights are best? This is a variant of a standard voting problem. The standard problem does not include the option of BAD for negative points. I don't think there is an optimal answer. Weights that would NOT be good to use would make the ONES's get a lot more than the TWO's since I suspect this gap was not so large in peoples minds. Or I could have had THEM give point values between (say) 1 to 100 for the ONE, TWO, THREE and between -1 and -100 for the BAD. Maybe I'll do that next year.

1. Abraham Lincoln: 15 ones, 10 twos, 10 threes: 75 points.
2. Theodore Roosevelt: 8 ones, 8 twos, 4 three: 44 points.
3. Franklin D. Roosevelt: 11 ones, 7 twos, 7 threes, one B: 51 points.
4. George Washington: 7 ones, 4 twos, 8 threes, one B: 34 points.
5. Thomas Jefferson: 6 ones, 5 twos, 5 threes: 33 points
6. Dwight Eisenhower: 1 one, 3 twos, 5 threes: 14 points.
7. John F Kennedy: 2 ones, 5 twos, 6 ones, 1 B: 14 points.
8. Woodrow Wilson: 1 one, 1 two, 3 threes: 10 points.
9. Harry S Truman: 2 twos. 6 points.
10. James Polk: 1 one, 1 two: 5 points.
11. John Adams: one 1, one 2, one B: 4 points.
12. William Henry Harrison: one 1: 3 points.
13. Lyndon B. Johnson: one 2, one 3, one B: 2 points.
14. Andrew Jackson: 2 ones, 1 two, 2 B's: 2 points.
15. Ulysses S. Grant: 1 two, 2 B's: -4 points.
16. Zachery Taylor, Rutherford B Hayes, Chester Arthur, Millard Fillmore, Warren Harding, Gerald Ford: 1 B: -3 points.
17. Jimmy Carter: 1 one, 1 two, 4 B's: -5 points. CORRECTION ADDED LATER: SHOULD BE -7. ARITHMETIC MISTAKE. MAKES HIM RANK BELOW BUCHANAN AND TAFT!
18. James Buchanan, William Taft: 2 B's: -6 points.
19. Ronald Reagan: 1 one, 3 twos, one 3, 8 B's: -12 points. CORRECTOIN ADDED LATER: SHOULD BE -14. ARITHMETIC MISTAKE. RELATIVE ORDER UNCHANGED.
20. Herbert Hoover: 5 B's: -15 points.
21. George Bush: 6 B's: -18 points.
22. Richard Nixon: 1 one, 1 two, 10 B's: -25 points.

My thoughts

1. I thought George Washington would do better.
2. I'm surprised that Theodore Roosevelt did so well. Bart Simpsons likes him, though Lisa Simpson prefers FDR (From the episode Bart stops and smells the Roosevelt's.
3. The person who ranked Hayes as the worst president of all time either knows much more about the Hayes administration then I do or was just putting things down at random.
4. The vote for William Henry Harrison was a joke- the guy who voted for WHH is named Henry and liked that his first name was WHH's middle name.
5. Dwight Eisenhower did better than I thought he would.
6. Richard Nixon did worse than I thought he would. I thought today's youth didn't know about Watergate. George McGovern (who Nixon beat in 1972 and is still alive) recently said that if he had won in 1972 then Nixon's legacy would be much better (going to China, Detente with Russia, EPA, Okay on Civil Rights.) Nixon would be considered a left wing democrat today.
7. George Bush did so bad that I think people may have confused him with his son W.
8. Some of my opinion: (1) I rank George Washington first since the very act of STEPPING DOWN after two terms set the tone for peaceful transitions of power. Note that young democracies today the most important election is the one where the person in power has to voluntarily step down. (2) For worst prez I wouldn't call someone BAD just because I happen to disagree with their policies. It has to be someone who (in contrast to Washington) did things that undermine our democracy. Two that come to mind are Nixon (Watergate) and John Adams. (Alien and Sedition Acts). George W Bush (Patriot Act) might also qualify but its too early to tell. Other wartime restrictions on freedom (happened in many wars) might also qualify. The corruption of the Grant and Harding's administration were deplorable but I don't think they rise to the level of undermining our democracy. There are probably other presidents who qualify for this honor but not being an expert on Presidents, I don't know who they are.
9. In the book Hail to the Chiefs (a humorous though mostly accurate look at the presidents) in the first edition she said that Buchanan and Andrew Johnson were not looked upon kindly by historians, which is true. In the second edition she made the points many times with many presidents (including those two) that how well you do is VERY MUCH a matter of timing, luck, and History. To paraphrase Buchanan couldn't stop the Civil War. By that point nobody could. Andrew Johnson had to reunite the country and deal with the South after the Civil War. That's pretty hard too. I agree that there are many thing outside a presidents control, and they some blame or praise may be unwarranted.

The Betty White Award for 2024

In Jan of 2023 I estabalished the Betty White Award, see here which is given to people who died late in the prior year and hence won't be in the  those who we lost in year X articles. I also gave out a few from prior years. Here are past winners, some in retrospect.

2006: James Brown and Gerald Ford. See my post here. The post was not on the Betty White award since Betty White had not died yet. But the idea is there.

2021: Betty White and Bishop Tutu. See my post here. I didn't have the award yet but I do now. Can person X win the X award? I say yes. Its rare since usually the person an award is named after is dead, but in this case that's kind of the point.

2022: Pele (Soccor player), Barbara Walters (broadcast journalist), Pope Emeritus Benedict. See my post here. Three famous people! To quote my post: One was prominent in one of the worlds largest religions. The others were a broadcast journalist and a former Pope. 

2023: Tommy Smothers (Singer and Comedian). See my post here. Since I collect novelty songs I knew who he was, but I think most people did not. 

2024: I began writing this post on Dec 28. Bad idea- the whole point of the award is that we should WAIT until the year is OVER before doing retrospectives. In fact, the award was going to go to Ricky Henderson (famous baseball player), Greg Gumbel (sportscaster), and Olivia Hussey (Actress). The last two I had never head of until they died, but I didn't want to just give it to one person.

Then on Dec 29 Jimmy Carter died. Okay then. Greg and Olivia will still get Honorable Mention.  After that but before Jan 1, Linda Lavin died who will also get Honorable Mention. 

ADDED LATER: An alert commented that Manmohan Singh, who was prime minister of India 200 4-2014 (analogous to being president of America) passed away on Dec 26, 2024. Hence I have added him as well.

Here are the WINNERS of the Betty White Award for 2024:

Ricky Henderson A hall-of-fame baseball player who was truly a superstar. He died on Dec 20, 2024, at the age of 65. See his Wikipedia entry here. There are two criteria for the Betty White Award. 

a) Being famous enough so IF he had died earlier, he WOULD be in the those we lost in 2024 articles. On this criteria, Ricky Henderson is solid. Note that he holds the record for most stolen bases in a career by A LOT: RH has 1406, Lou Brock is second with  938.

b) Dying to late in the year to be on those lists. I checked- he is on some lists but not others. To NOT get the Betty White award because he died late but not late enough would be really sad. SO, even though on this criteria he is borderline, the judges have decided to give it to him.

Jimmy Carter A former president of the United States; however, he may be more known for his post-presidency work on charities. He won a Nobel Peace Prize in 2002. He died on Dec 29, 2024 at the age of 100. Providing a Wikipedia link sounds silly- you all know who he is. Here are some miscellany:

a) I was hoping he would last until Biden stepped down so there would be six living ex-presidents:

Carter, Clinton, Bush Jr, Obama, Trump, Biden.  I blogged about this here.

b) Carter is the prez who lived the longest. He also  had the longest marriage. Jimmy and Rosalyn Carter were married for 77 years. George and Barbara Bush were second with 73 years of marriage. 

c) Carter is the only president sworn into office by his nickname Jimmy (his `real' name is James). It annoyed me when BILL Clinton was sworn in as WILLIAM and when JOE Biden was sworn in as JOSEPH. If Jeb Bush had become prez he probably would have been sworn in by his nickname Jeb (his `real' name is John). Oh Well. 

Jimmy is Clearly famous enough and Clearly died late enough in the year. 

Manmohan Singh A former prime minister of India; however, some of my American readers may not know that (indeed- I did not). He served as prime minister from 2004 to 2014, serving two 5-year terms. He was the first Sikh prime minister of India. See his Wikipedia entry here. 

Manmohan is not famous in America but he is very famous in India and in countries that pay more attention to world events than Americans do. And he died late enough in the year.

AND three Honorable Mentions:

Greg Gumbel A sportscaster, died on December 27, 2024 at the age of 78. See his Wikipedia entry here. SO, does he deserve it? 

a) Being famous. I've read that he is famous but frankly, I had never heard of him until I saw the obit and said  Betty White Award Contender.? That he had an obit on some news site IS an indicator of fame. And more to the point of the award, had he died a a few days later, in 2025, he would have been on the those who we lost in 2025 lists. If Jimmy Carter hadn't died he would have won the award (with Ricky Henderson and Olivia Hussey and Linda Lavin) so I decided to give him Honorable Mention.  My award, My rules. 

b) Dying late. OH YEAH! Dec 27 is very late. 

Olivia Hussey An actress, died December 27, 2024 at the age of 73. See her Wikipedia entry here. SO, does she deserve the award? 

The Being Famous and Dying late comments are identical to those for Greg Gumbel. 

So she also gets an Honorable Mention. 

Linda Lavin An actress, died December 29, 2024 at the age of 87. See her Wikipedia entry here. SO does she deserve the award? 

The Being Famous and Dying late comments are identical to those for Greg Gumbel. 

So she also gets an Honorable Mention. Also she gets credit for dying really late in the year.

A Prez Question: Can AI do it? Can you? Can I?

 I am curious how AI or humans can do on the following question.

I have listed out the nominees for Prez and VP (Vice Prez) since 1976 and put them in two categories.

What criteria did I use?

The criteria is about their lives. So it's not going to be something like

The ones in GROUP ONE have last names with at most 3 vowels.

A few notes before the lists:

1) You may come up with  criteria I didn't come up with.  It may even be outside of my rules- for example about vowels. Fine- I will be curious if some criteria like that happen to be equivalent to my criteria.

2) You can use whatever you want- Wikipedia, ChatGPT, your friend who knows a lot about presidents.

3) Leave comments with your proposed answer AND HOW YOU GOT IT, though be warned to NOT go to the comments if you want to work on it yourself, since the right answer might be there.

4) There are people who were the nominees for Prez or VP several times.
I want the list to be in chronological order. I list everyone only once.
What to do about (say) the fact
that Bob Dole ran for VP in 1976 and for Prez in 1996?
I list people in order of the FIRST time they were the nominee.
So I have:

VP 1976. Prez-1996
Bob Dole

5) I added some misc information for fun. That information is NOT relevant to the solution. 

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

GROUP ONE:

VP-1976 and 1980. Prez-1984
Walter Mondale

Prez-1976
Gerald Ford

VP-1976. Prez-1996
Bob Dole

VP-1984
Geraldine Ferraro

Prez-1988
Michael Dukakis

VP-1988
Lloyd Bentsen

VP-1988 and 1992
Dan Quayle

Prez-1992 and 1996
Bill Clinton

VP-1992 and  1996. Prez-2000
Al Gore

VP-2000
Joe Lieberman

Prez-2004
John Kerry

VP-2004
John Edwards

Prez-2008 and 2012
Barack Obama

Prez-2012
Mitt Romney

VP-2008 and 2012. Prez-2020
Joe Biden

Prez-2016
Hillary Clinton

VP-2016
Tim Kaine

VP-2016 and 2020
Mike Pence

VP-2020. Prez-2024
Kamala Harris

VP-2024
J.D Vance

(The only names that were flagged for being misspelled are Dukakis, Bentsen, Kamala.)

--------------------------------------
GROUP TWO

Prez-1976 and 1980
Jimmy Carter

Prez-1980 and 1984
Ronald Reagan

VP-1980 and 1984, Prez-1988 and 1992.
George H.W. Bush
(Not counting the early elections which had different rules,
I think the only other person who got the nomination twice for VP
and twice for president is Richard Nixon. If I am wrong, let me know.)

VP-1996
Jack Kemp

Prez-2000 and 2004
George W Bush

VP-2000 and 2004
Dick Cheney

Prez-2008
John McCain

VP-2008
Sarah Palin

VP-2012
Paul Ryan

Prez-2016 and 2020 and 2024
Donald Trump

VP-2024
Tim Walz

(The only name that was flagged for being misspelled was Walz.) 

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. 

An odd way to find good employees- it might work

I recently got the following email. It is not spam in that it is a legitimate company asking a fair question and it has only gone to a select group of people. However, a very similar email may have gone to other select groups of people, perhaps millions of select groups of people. Italics are mine.

I found your name while researching scholars who have served as teaching fellows under Professor Harry Lewis at Harvard. The D. E. Shaw group is currently looking to hire a small number of truly gifted individuals with outstanding backgrounds in math, physics, computer science, and other technical fields. As an organization, the D. E. Shaw group goes to extraordinary lengths to identify such candidates and introduce them to the firm. Based on your work as a teaching fellow in one of the most challenging CS courses at Harvard, you seem to be especially well-placed to help us find people with strong academic backgrounds whose areas of specialization might be particularly relevant to the work we do. Do you have any students or colleagues who stand out in your mind as possessing unusual raw ability even among a relatively gifted population of peers? If so, we would be enormously grateful if you'd bring them to our attention. If you yourself might be inclined to explore opportunities with us, I encourage you to send us a copy of your resume.

So, this person researches scholars who have served as teaching fellows under Professor Harry Lewis. How many people do research on that? Do they have their own Journal?

The sender did get one thing right and one thing weird. RIGHT: I was Harry Lewis's TA for Automata Theory in Fall 1981 and Fall 1984. WEIRD: The course was challenging for the students, but I doubt it was one of the most challenging CS courses at Harvard. Actually, I doubt that phrase even makes sense- for me Automata Theory was easy and programming courses were hard, and others felt the opposite.
Harry Lewis has on his website a list of all the people who ever TAed for him, which is where the sender got my name (other TAs of Harry Lewis, some further back than myself, have gotten the same email).
So, why did D.E. Shaw choose this group of people to send the email to? Harry Lewis has no connection to the company, so thats not it.

1. They believe, rightly or wrongly, that ugrads at Harvard who get to TA courses must be pretty good, and grad students who go to Harvard must be pretty good. But see next item.
2. They did not say that they want me to apply. They think I might know people that should apply. At the end of the letter they have an after-thought-type-statement saying essentially, `oh, and you too, I guess'
3. The list of Harry Lewis TA's is available! I also TAed for Michael Rabin, Gerald Sacks, and Leslie Valiant, but they don't have lists of their TAs on their websites. Hence people who do research on (say) scholars who have served as teaching fellows under Michael Rabin or the others have a much harder time.

Oh, I remember/recorded/DVRed it well

You can now wear a device, Memoto that will take a picture every 30 seconds. Do you really have a Kodak Moment every 30 seconds? No, but this way when you do have one it will be captured (unless it happens at just the wrong time.) There is another one called Autographer which claims to be a "smart" camera that will take tons of pictures of your day. A photographer wore one and had his team all wearing them during a photo shoot.

Current historians who study ancient civilizations have the problem of very little being preserved. They go on whatever, perhaps by chance, happened to survive. King Tut is studied NOT because he was an important king, but because we have LOTS of his stuff. (What if America is destroyed and all that is left is the Gerald Ford Library?}

Future Historians may have the problem of having too much written down, recorded, emailed, blogged, tweeted. Or they may have the problem current historians have if some of these technologies go out-of-date so a lot is lost. Floppy's are already unreadable, Video Tapes and VCR's are degrading, beta-tapes--- as your grandparents what they were. They may also have the Galaxy Quest problem of mistaking our TV shows for historical documents (oh that poor Gilligan!).

What do we and don't we preserve?

1. Almost every TV show and Movie produced since DVDs came out, no matter how bad, is on DVD. Is there a directors cuts of Dude, where's my car?? Will future generations need that?
   
2. News shows are not preserved. Too bad- I might want a complete set of THE DAILY SHOW and THE COLBERT REPORT. Future historians may have the problem of mistaking these shows for satire.
   
3. Quiz shows are not preserved. Too bad- I liked BEAT THE GEEKS but all I have are some video tapes I recorded when it was on.
   
4. Sporting events- This is borderline since there are DVDs of past Superbowl's, World Series, etc, but not of ordinary games.
   
5. Many TV movies don't make it to DVD. Is that a loss?
   
6. Much TV from before the video tape age is lost. Some survives. It is somewhat arbitrary. I Love Lucy was done on some sort of medium that survived, others did not.
   
7. A very odd case: Dr. Who. There are rumors that some fans audiotaped the early episodes and that the only form in which they are preserved. See here, here.
   
8. Commercials. Aside from arbitrary things people happen to have taped, most commercials will not survive! What will future generations do without all of those insurance companies claiming that they are cheaper than the other ones?
   
9. What if the only knowledge of complexity theory that survives is Lance's book. That would be okay!
   
10. What if the only knowledge of complexity theory that survives are the Bill/Lance Podcasts. Hmm...
    

Quasi related to the theme of today's post (today's post has a theme?) is the question Who was the first married sitcom couple to be shown sleeping in the same bed? The funny answers are The Flintstones and The Munsters, indicating that America was so prudish they couldn't show real humans in bed. The first real-human couple is then said to be the Brady Bunch. But actually a couple named Mary Kay and Johnny from a sitcom in 1947 are said to be the first. The networks were less prudish because the couple really was married (also, TV was SO new back then). But here is my point- The show DOES NOT EXIST ON VIDEO TAPE OR DVD OR ANY MEDIUM. So the answer is only people's memories which could be faulty. We are already losing access to some TV trivia! Incidentally, are there any happily married couples on TV anymore? (The FBI agent on White Collar comes to mine, but nobody else.) (Added later: Our knowledge of TV trivia is actually increasing! see here.


What about journal articles? Do we do the future a DISservice by publishing too much and making it harder to find stuff? Or will they have the tools to find what they want? Today we have Google Scholar and some other tools- but are we putting all of our eggs in one basket? Will all of our papers survive or only the good ones? Or is every paper a gem worthy of preserving for future generations? While I doubt this is true, you never know when someone is going to need the Canonical a-ary Ramsey Theorem to prove something in geometry.

Do Senators have an Advantage for being Dem VP Nominee?

This is a non-partisan post. Even so:  I plan to vote for Joe Biden.

(Lance says that whenever I write `this is a non-partisan post'  its partisan anyway.)

I've had posts on predicting VPs before:

In this post I looked at a Nate Silver column a few months ago where they were trying to predict the democratic VP nomination before the Prez nominee was known. Some of what they said seems relevant.

In this post I PREDICTED that bets on INTRADE would not do well on picking VPs since VP picks are hard to predict and often are not from anyone's short list. I DID NOT PREDICT that INTRADE would go out of business.

I came across a statistic recently that seems relevant and inspired this post. Actually this post asks IS this statistic relevant?

From Prez candidate  Harry Truman to Prez candidate Hillary Clinton there have been 15 Dem VP nominees (not  counting incumbents) of which 13 have been Senators:

Harry Truman(Prez)-Alben Barkely. Sen from Kentucky

Adlai Stevenson(Gov-Illinois) -John Sparkman. Sen from Alabama

Adlai Stevenson(Gov-Illinois)-Estes Kefauver, Sen from Tennessee 

John F Kennedy(Sen-Mass)-Lyndon B Johnson, Sen from Texas

Lyndon B Johnson(Prez)-Hubert Humphrey,Sen from Minnesoda

Hubert Humphrey(VP)-Ed Muskie, Sen from Maine

George McGovern Sen-South Dakota)-Sgt Shriver Amb to France, Office of Econ Activity

Jimmy Carter(Gov Georgia)-Walter Mondale- Senator from Minnesota

Walter Mondale(Senator Minnesota)-Geraldine Ferraro Congressperson- NY

Mike Dukakis (Gov Mass), Lloyd Benson-Sen Texas

Bill Clinton(Gov Arkansas), Al Gore Sen from Tennesee

Al Gore (VP), Joe Lieberman Senator from Conn

John Kerry (Sen-Mass), John Edwards Sen from NC

Barack Obama (Sen-Illinois), Joe Biden Sen from Del

Hillary Clinton (Sen-NY), Tim Kaine- Sen Virginia

Of the 15 Dem VP nominees, 13 are Senators

Of the 13 Rep VP nominees, 4 are Senators  see here

My Speculations: 

1)  When a gov runs he wants someone with fed experience. That explains 5 of the cases above.

2) Senators tend to be better known than other politicians, so perhaps being well known is what you need. Note on the Republican Side Paul Ryan was a House member but was well known.

3) Why do the Reps and Dems differ on this? Is the sample size too small to make this question interesting? 

So here is the question: When trying to predict who the Dem VP will be (this year or any year) should being a Senator give someone a plus? A higher weight in a Neural Net? 

Kamala Harris is the favorite on the betting markets.  Is this because she is a Senator?

She has a national profile and has already been vetted since she rana serious campaign  for Prez in the primaries. So I would say that THATS the reason (and other reasons), not that she is a Senator. But would she have been able to run a serious campaign  in the primaries if she wasn't already a Senator? I ask non rhetorically.

ADDED LATER- one of the comments inspired me to also include who the Republicans picked for VP since Truman. Much more variety in the jobs they held prior. This is neither good or bad.

Thomas Dewey (Gov-NY), Earl Warren (Gov-California)

Dwight Eisenhower (General), Richard Nixon (Sen-California)

Richard Nixon (VP), Henry Cabot Lodge (Sen-Mass, Amb-UN)

Barry Goldwater (Sen-Arizona), William Miller (Representive-NY)

Richard Nixon (VP), Spiro Agnew (Gov-MD)

Gerald Ford (Prez, Senator-Michigan), Bob Dole (Senator-Kansas)

Ronald Reagan (Gov California), George Bush (Dir of CIA)

George Bush (VP), Dan Quayle (Sen-Indiana)

Bob Dole (Sen-Kansas), Jack Kemp (Representiative-NY)

George W Bush (Gov-Texas), Dick Cheney (Cabinet)

John McCain (Sen-Arizona), Sarah Palin (Gov-Alaska)

Mitt Romney (Gov-Mass), Paul Ryan (Represenative-NY)

Donald Trump (Businessman-NY), Mike Pence (Gov-Indiana)

Answer to my GROUP ONE/GROUP TWO Prez question

In a prior post I asked what criteria I used to place Prez and VP nominees since 1976 into two groups. 

In the book Abundance I read that since 1984 all of the Democratic nominees for Prez and VP except Tim Walz had gone to law school.  I decided to get data on that, along with Republicans, and also go back to 1976 since leaving out 1980 (Jimmy Carter did not go to law school) seemed like a cheat. So GROUP ONE all went to law school, and GROUP TWO did not. I restate the groups and note which law school and a few other fun facts. There are a few glitches along the way. And then I have comments on the problem and AI (when was the last time there was a blog post that did not mention AI?) 

GROUP ONE:

VP-1976 and 1980. Prez-1984
Walter Mondale. University of Minnesota Law School. 1956.

Prez-1976
Gerald Ford. Has an LLB from Yale. 1941. What is an LLB? Some law degrees were called LLBs in an earlier time. This is a glitch. Some places on the web call it an undergraduate degree in Law (the B stands  for Bachelors) but some say it's equivalent to a JD. Fords's seems to be equivalent to a JD. 

VP-1976. Prez-1996
Bob Dole. Has an LLB from Washburn University in Topeka Kansas in 1952 . See entry on Ford for what an LLB is. From the Wikipedia entry on Bob Dole it seems like the LLB was an undergraduate degree, but its hard to tell. 

VP-1984
Geraldine Ferraro. Fordham University School of Law. 1960.

Prez-1988
Michael Dukakis. Harvard Law School. 1960.

VP-1988
Lloyd Bentsen. LLB from the  University of Texas Law School. 1942. See Entry on Ford for what an LLB is. From the Wikipedia entry I cannot tell if it was the equivalent of a JD. 

VP-1988 and 1992
Dan Quayle. Indiana University Robert H. McKinney School of Law. 1974.

Prez-1992 and 1996
Bill Clinton. Yale Law. 1973.

VP-1992 and  1996. Prez-2000
Al Gore.  Vanderbilt University Law School. He quit to run for the House of Representatives. I still count this but it's a glitch. 

VP-2000
Joe Lieberman.  Yale Law School. 1967.

Prez-2004
John Kerry.  Boston College 1976.

VP-2004
John Edwards.  University of North Carolina School of Law. 1977.

Prez-2008 and 2012
Barack Obama.  Harvard Law School. 1991.

Prez-2012
Mitt Romney.  MBA/JD (a joint program) from Harvard. 1975. (This surprised me.)

VP-2008 and 2012. Prez-2020
Joe Biden.  Syracuse University College of Law. 1968.

Prez-2016
Hillary Clinton.  Yale Law School. 1973.

VP-2016
Tim Kaine. Harvard Law School. 1983.

VP-2016 and 2020
Mike Pence. Indiana University Robert H. McKinney School of Law. 1986.

VP-2020. Prez-2024
Kamala Harris. University of California, Hastings College of the Law. 1989.

VP-2024
J.D Vance. Yale Law School. 2013.

The only names that were flagged for being misspelled are Dukakis, Bentsen, and Kamala.) 

--------------------------------------
GROUP TWO

Prez-1976 and 1980
Jimmy Carter

Prez-1980 and 1984
Ronald Reagan

VP-1980 and 1984, Prez-1988 and 1992.
George H.W. Bush 

(The only people who were nominated for VP twice and Prez twice are John Adams and George H.W. Bush. Richard Nixon was nominated for VP twice and for Prez three times.) 

VP-1996
Jack Kemp

Prez-2000 and 2004
George W. Bush

VP-2000 and 2004
Dick Cheney

Prez-2008
John McCain

VP-2008
Sarah Palin

VP-2012
Paul Ryan (This surprised me.) 

Prez-2016 and 2020 and 2024
Donald Trump

VP-2024
Tim Walz

(The only name flagged for being misspelled was Walz.) 

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

Some notes

In these notes I treat Bentsen, Dole, Ford, who all got LLB's,  as having gone to law school and finished it.

1) Of the 16 Democrats, 14 went to law school and 13 finished law school.

2) Of the 14 Republicans, 6 went to law school (all finished).

3) The LLB's and the fact that Al Gore started but did not finish law school are examples of edge cases which are cases that are odd outliers which an AI might not have been trained on or know to look for. Over time will these diminish or will we always need humans to help with that? 

4) I was surprised that Mitt Romney had a double-degree MBA/JD since (a) I didn't know there were such things and (b) since he worked at Bain Capital I thought of him as a business person--- MBA--- which is correct but incomplete. 

5) I was surprised that Ford, Dole, and Bentsen had LLBs since I never heard of that before.

6) I was surprised that Paul Ryan does not have a law degree. Seems like the type that would have one. 

7) Let LL mean Prez and VP both went to law school. Let LN mean prez went, VP didn't go. NL and NN are obvious. We considered 13 elections. Dems: 10 LL, 2 NL, 1 LN. Reps: 5 NN, 5 NL, 2 LN, 1 LL. Since I was surprised that Romeny went to law school AND I was surprised that Ryan did not, I would have thought 2012 for Reps was NL but it was really LN. 

8) One of the commenters used several AI programs on the question and NONE solved it. Some humans DID solve it. 

a) Some comments suggested that an AI should be able to list several ways the lists differ, and have probabilities of which ones are sensible.  My take: maybe in the future but not now.

b) Is this kind of question fair to ask an AI (or for that matter a person). They have to guess what I have in mind. Be that as it may, the AIs tried on the program.

DID NOT list out a different criteria that was right

but

INSTEAD gave criteria that were just wrong. 

 c) A commenter wrote  that the study was not rigorous. That's correct. So view this blog post as the starting point: study how AI's do on this question and others like it, keeping track of which AI and how the question is posed. Then we will have a better sense. 

9) Is this a sign that AI is not as good as people think OR is it just a hiccup?

President Regan (not Reagan)

Whose name (in firstname lastname form) appeared most often in the pages of Newsweek in the 1970's? Is it---?

1. Richard Nixon
2. Gerald Ford
3. Jimmy Carter
4. Ken Regan.

The answer could well be... Ken Regan. Ken Regan is a photographer. Many pictures in Newsweek had Photo credit Ken Regan in tiny letters up the side.

I was emailed an invitation to an event titled Ken Regan Presents Bob Dylan, and I wondered if I was emailed this because

1. I have the largest collection of Bob Dylan satires in the world .
2. I am friends with Ken Regan who, for all I know, in addition to being a computer scientist, chess player, language expert, blogger, choir singer, and would-be composer and writer, could also be a photographer.
3. This email went to EVERYONE,
4. This email was spam (not clear how this differs from the last choice).

I emailed Complexity-Ken who told me (1) there is a photographer Ken Regan, and (2) Complexity-Ken-Regan does not equal Photographer-Ken-Regan. Sharing a name with a photographer seems okay. Its better than sharing a name with a vicious murderer, or worse, a Congressman.

Photographer-Ken has one thing going for him: he registered the domain www.kenregan.com. Thus Complexity-Ken has forever lost the chance to emulate www.fortnow.com or www.scottaaronson.com. Still, Complexity-Ken often pushes the domain into second place in Google searches, and simply Google Regan without any firstname at all turns him up on the first page of hits. Why is that? It may be a prerogative of being both a computer scientist and a blogger who tends to make a lot of comments under his real name, with his name (or handle KWRegan) linking back to his site. Perhaps Google regards this as legitimate self-citation, ticking up his page's "authority" score for each one?

Complexity-Ken's wife Debbie Howe is shares a name with the originator of the popular children's book series Bunnicula. However, Complexity-Ken-Wife-Debbie took Complexty-Ken's surname as her middle name and has used the resulting full name in some publications, which Google Deborah Regan Howe finds. More generally, preserving the Google trail has become a factor in wives' keeping their maiden names after marriage. I suspect its a bigger factor than feminism or being-your-own-person or other very good reasons. (I posted on this already here.)

The Betty White Award for 2023: Tommy Smothers

Betty White died on December 31, 2021. When I mention that, even now, some people are surprised that they didn't hear about it. Why? Because she died AFTER all of the who we said goodbye to this year articles have come out. I think its idiotic to have these things come out in DECEMBER instead of early January.  Same with Time Magazine's Person of the Year. If Joe Biden had managed to create peace between Israel and the Palestinians AND between Russia and Ukraine on Dec 31, then he might, just might, have been a better choice than Taylor Swift for Person of the Year.

BUT, rather than complain, I created The Betty White Award for famous people who die towards the end of December. 

Past Winners:

2006: James Brown and Gerald Ford. I didn't have the award then but I noticed their deaths coming to late in the year to be noticed, see my post  here.

2021: Betty White and Bishop Tutu. See my post here. I didn't quite have the award then, but its implied.

2022: Pele, Barbara Walters, Pope Emeritus Benedict. See my post here.

I thought based on these three data points that I would often have 2 or more winners. But no. For 2023 there is one winner:

Tommy Smothers who died on  Dec 26, 2023 at the age of 86.

Tommy and Dickie Smothers (his brother is still alive at the age of 85)  were known as The Smothers Brothers. They did Comedy and Music together. They are more known for their comedy. A few notes

0) I wrote this post on Dec 31. I was going to post it on Dec 31 at 11:00PM but then thought What if someone famous dies in the next hour? Then I'll need to redo the post, probably giving both that person and Tommy Smothers the award!  I waited until Jan 2 since its possible that someone famous dies and I don't hear about for a few days.

1) They had a comedy-variety show The Smothers Brothers Comedy Hour from Feb 1967 to June 1968. It was controversial at the time for some of its political comments though, frankly, if you saw it now I really don't see why they were controversial.  They had very high ratings but were cancelled because of the controversy. I don't understand that either- if its making the network money, then why cancel it? Possibilities:

a) They were losing sponsors. I have not read that this was the case. And I would think they could get new ones.

b) Some local stations refused to air it. This seems to be true.

c) The suits themselves were offended and put their principles above profits. 

d) They were scared that the FCC would crack down on them.

e) They got angry letters (this is true though I don't see why this means you cancel).

What controversy? They made fun of the president! They were against the war in Vietnam!

So I am puzzled that they were cancelled. 

I was young at the time  and didn't really understand it (I still don't) but I recalled a great Mad Magazine piece about it (in 1968).  And thanks to the wonder of the internet, I found it in about 5 seconds. Here it is: here.  I suspect that my young readers are not at all surprised that an article I read over 50  years ago I can find easily. This still surprises me. And I note that its not always so easy.

2) The show was one of the first to do political humor about real living politicians (Another one was That was the week that was which had Tim Lehrer on it, among others.) Comedy featuring a generic politician being, say, dishonest, was certainly allowed, but not an actual one with current issues. As such it lead the way for SNL, The Daily Show, and other shows. 

3) While Smothers Brothers sounds like a made up name, their last name really was Smothers. Reminds me of Clint Eastwood and Dolly Parton having great stage names for their real names.

4) One of their types of comedy was to start singing a real song (they were good singers- folk singers) and then in the middle of it get into an argument or discussion about it. Here is an example: here. (warning- this is NOT controversial or political)

5) There was one episode that never aired because of its controversy.  Here it is: here. I watched it. I cannot see what is controversial in it. There is also some commentary after it that explains why it was controversial.

More odd- I didn't find it that funny. And note that this is the kind of thing I usually DO find funny. But this is not a criticism- its just evidence that some shows (or art in general) has a short shelf live.

6) That one episode being on you tube reminds me of the ONE picture of FDR in a wheelchair is ALL OVER the web. Here is one place: here. Not just the web--- it was in my High School History Text with the caption a rare photo of FDR in a wheelchair. Even then I doubt it was rare since it was in many textbooks. And now being on the web makes it even harder to say its rare. I did a post a long time ago (I was a guest blogger) on how things on the web can't really be considered rare. Its here.

7) The fact that they were controversial then but would not be now reminds me of the TV show Tanner 88, which was on HBO in 1988 (one of their first original series) which followed the fictional presidential campaign of Jack Tanner. At the time it was considered biting political satire. I bought the DVD and watched it in 2008. A typical episode of West Wing (a good show, but hardly a biting political satire) had more bite. But again, much like The Smothers Brothers, it paved the way.Which brings up back to our original point:

 Tommy and Dickie Smothers: We THANK YOU for paving the way for political satire and commentary.  

 

 

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. 

ACM Awards

The 2005 ACM Awards have been announced. Omer Reingold received the Grace Hopper Award given to the best "outstanding young computer professional of the year, selected on the basis of a single recent major technical or service contribution" in this case for his log-space algorithm for undirected connectivity. The previous theoretician to receive the award was Shafi Goldwasser in 1996 and before that Donald Knuth in 1971. Congratulations Omer!

Peter Naur won the Turing Award (the closest CS has to a Nobel Prize) for his work on Algol 60.

Gerald Holzmann, Robert Kurshan, Moshe Vardi and Pierre Wolper won the Paris Kanellakis Theory and Practice Award for their use of automata theory in program verification.

Thanks to Moni Naor for the pointer.