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 Bentson. 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, Bentson, 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 Bentson, 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 Bentson 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?

Trevisan Prize- Deadline July 31 for Notification Intent, Aug 31 for nomination.

A new prize:

The Trevisan Prize, in honor of Luca Trevisan, who died in 2024 (blog obit is here, open problems column in his honor is here), has been announced. 

 The link is  here.

 

The deadline for notification of intent is July 31 which is soon.

 The deadline for the nomination is Aug 31. 

 

 

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 Bentson

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, Bentson, 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.) 

Turing, Wagner, Ruth

Douglas Hofstadter first published Gödel, Escher, Bach: an Eternal Golden Braid in 1979 and my then high school self tried, and failed, to read though the entire book. It focused on the contradictions, with Kurt Gödel's incompleteness theorems, M. C. Escher's Drawing Hands and Johann Sebastian Bach's Canon a 2 per tonos, a piece that keeps rising until it ends a whole tone higher than it started.

I'd prefer to focus less on the paradoxes and self-reference to the true beauty and complexity of computation. So now having had a long career in the field, who would I call on to capture the power and beauty of computing?

It has to start with Alan Turing. His seminal paper On Computable Numbers, with an Application to the Entscheidungsproblem gives a clean model for computation and still the best argument (Section 9) for why this simple model captures everything computable. The Entscheidungsproblem, that you can't mechanize all of mathematics, comes as a consequence, not as a goal of the paper. In a much later paper, The Chemical Basis of Morphogenesis, he shows how the beauty of nature can emerge naturally from computation, which of course we now know much better arises from discrete DNA sequences.

For music, instead of Bach's abstract works, I prefer to focus on the emotional power of music that still arises from a musical score that is not unlike a computer program in the way it lays out the composition. Take for example Richard Wagner's Prelude and Liebestod (the beginning and the end of his opera Tristan and Isolde). It captures the tension of the two lovers from the very first notes and keeps that tension going until it resolves at the very end.

While soccer and basketball have mostly continuous play, I prefer that great American game of baseball that after each pitch has a very discrete state space that stadiums would capture with a few light bulbs (strikes, balls, outs), and yet could keep the excitement and tension on every one of those pitches. No one dominated the game more in his time than George Herman "Babe" Ruth, who I might have admittedly also chose to keep the same syllable cadence as Hofstadter.

So let's thank Turing, Wagner, Ruth, and the many others that showed we can show how incredible complexity and beauty can arise in the simplicity of computation. So many stories to tell. 

How much money did Francis Scott Key give to have a building named after him?

UMCP has a building named 

The Francis Scott Key Building

STUDENT: How much money did Francis Scott Key give to have a building named after him?

BILL: He didn't give money. He wrote The Star Spangled Banner.

STUDENT: I get it! He left the royalties! That would be a lot since Major League Baseball plays that song before every game!

BILL: The song is in the public domain.

STUDENT: That's too bad. Well, at least UMCP got some money out of it before it was in the public domain.

BILL: Francis Scott Key did not give UMCP the royalties from his song.

STUDENT: Well then what did he give UMCP?

BILL: He didn't give UMCP anything. He died in 1843 and UMCP was founded in 1856.

STUDENT: Oh. So his descendants gave money to have a building named after him.

BILL: No, that didn't happen either.

STUDENT: Then why is there a building named after him?

BILL: To honor him.

STUDENT: What does that mean? The only reason to name a building after someone is if they give money to the school. The notion of "honoring someone" sounds so odd--in fact I honestly don't know what it means. OH, I get it, they are just using that name as a placeholder until they find someone who gives the school money for a building.

BILL: I doubt that. Once a building is named to honor someone, it won't change the name for money. That's just too crass.

LANCE: Don't be so sure. When I started undergrad at Cornell in 1981, Benjamin Franklin hall, the site of the country's first Electrical Engineering Department, was just renamed to Olive Tjaden hall. One of my professors made fun of the change, "Why should we name it after Ben Franklin—he never donated to Cornell".

During an alumni weekend, we had a visit from a former alum and his wife, Olive Tjaden, to my fraternity, Kappa Delta Rho (Yes, I was a frat boy in college). She was not shy about bragging that the building was named after her. For some reason Mr. Franklin never showed up to defend the old name. 

Cornell still has a Lincoln Hall named after the former president. 

BILL: Does any campus name buildings to honor people anymore? 

LANCE: At this point I wouldn't be surprised if some university names a building "Donald J Trump Hall" as part of a settlement.

But really, these days, you need money to build buildings, so they get named after donors—or after someone the donor wants to honor. Even if a building is built on state funds, it's usually given a generic name to leave open a naming opportunity later. 

BILL: What happens if you name a building after someone because they gave money but later if they found out that they are an X (you can fill it in with some type of person you would not want to honor)? If you had named the building to honor them, you can change the name. If you named it because they gave money you may have a contractual obligation to keep the name. (This was almost a problem with Enron Field, see here).

LANCE: In 2017, Yale renamed Calhoun College, named for a white supremacist, to honor Grace Murray Hopper. 

BILL: I hope they got all the bugs out first.

I conjecture very few (any?) colleges name buildings anymore to honor people. It is purely transactional. 

1) Am I right? ADDED LATER: Some comment pointed out that I a wrong. See the comment and also these pointer:

Univ of MD at College Park: Pyon-Chen Hall here, 

Univ of MD at College Park: Johnson-Whittle Hall (same pointer as Pyon-Chen) here, 

Univ of MD at College Park: Thurgood Mashall Hall here.

Princeton: (Toni) Morrison Hall: here

Univ of CA at Irvine: (F. Shewood) Rowland Hall here

Univ of CA at Irvine: (Fredrick) Reines Hall here

 Readers- if you have other examples of BUILDINGS named after people do honor thos people, please leave a comment about it that provides enough information so I can get a pointer.

2) If so, is this a bad thing?

3) And when will Grace Murray Hopper College be renamed again after a donor?

The Customers of the Academy

I had an epiphany reading an article in the Trenton Times when I lived in New Jersey at the turn of the century. The article interviewed companies along a certain street lobbying for a new bus route so their employees could more easily get to work. The customers for mass transit are not its riders but the employers who need workers to get to them. Maybe that's why mass transit trains and buses offer a functional but not particularly comfortable ride.

So who are the customers for universities? Before I go there, let's look at newspapers. Until the early 2000s, newspapers were primarily driven by advertising revenue. Readers were the product. While newspapers needed readers to sell, they could get them by offering cheap subscriptions by focusing on quality coverage that focused on news and analysis from a broad range of views. But since then, the few newspapers that thrive now do so mostly on subscription revenue, print and digital, and the readers have become the customers. They also have more competition from other sources like social media. So newspapers now tailor their coverage and their brand for the paying subscriber, and while most still focus on accuracy, they'll stick to narrower views in their analysis which often overshadows the pure news.

Universities have a mission beyond just serving students, providing them with knowledge in exchange for tuition. They have a societal mission. The Morrill Land-Grant Act of 1862, which helped establish and grow a number of public universities, wanted to educate students to improve the productivity of American agriculture and industry. The GI Bill in 1944 brought the masses of returning soldiers into higher education. The Higher Education Act of 1965, brought in resources for students through Pell Grants and federally-guaranteed student Loans to further the competitiveness of America through the Cold War. Most universities have non-profit status because of their broader mission.

In other words, society as a whole was our customer. Our role is to educate and prepare students to help push our society forward. Many universities also have a research mission, also mostly government funded, both to recruit expert professors to educate our students, but also to produce important knowledge to manage the complexities of the world. Students participated willingly for future intellectual and financial gain and our role was to ensure the students got a strong education, for the betterment of not just themselves but the workforce and society they would later join.

Our viewpoint has changed as college costs increased and universities became more dependent on tuition and governmental financial aid. Institutions started treating the students as the customer, to ensure they came to the university and stayed there. More amenities, grade inflation, much more student support and tolerance. The relationship became transactional, a student comes, pays their tuition and their time, gets a degree and gets a job. The focus becomes more on degrees that prepare you for the workplace, a focus more on immediate skill and credential building than producing students who have the critical thinking skills to build a strong career. 

And now in a time of changing demographics, less government support and AI heading towards performing many of the skills universities teach, how does the story continue? How do universities focus back on producing students who can not just live in our society but improve it? How do they focus on the right customers while ensuring educational quality? Universities need to get it right, or they won't have customers at all. 

The New Lower Bound on Busy Beaver of 6.

 We denote the busy beaver function by BB.

BB(n) is the max time a Turing machine of size n takes to halt on the empty string.

(A particular model of TM and a notion of size has become standardized.)

BB(n) grows faster than any computable function. That is obviously interesting. What is less obvious (and  some of my co-bloggers disagree) the pursuit of actual values of BB is interesting. For an excellent overview of the BB numbers, written in 2020 (that is relevant) by Scott Aaronson, see here. (Computable and Aaronson are flagged by my spell check but I think they are spelled correctly.) 

When Scott's article appeared, BB(5) was not known. In June 2024 the value of BB(5) was discovered.  See Scott's blog on this, here. The value of BB(5) isn't even that big- its just 47,176,870. That's one of those numbers that is SMALL now but would have been LARGE in (say) 1964 (see my blog about a different number of that type here). 

What about BB(6)?

No, I am not going to announce that Scott announced it is now known. 

I am going to announced that Scott announced better lower bounds for BB(6) are now known. 

I won't restate the lower bounds since (a) Scott already has (see here) and (b) typesetting the bounds is hard (for me). 

SO, what to make of all this?

1) At the time of Scott's article it looked like BB(6) was large. How large was hard to say. Intuitions about how large BB(6) would be are hard to come by, so the new result is neither surprising nor unsurprising. 

2) We will never know BB(6). Shucky Darns!

3) Many of the results on BB are not published in refereed journals. However, the ones mentioned in the context of BB(5) and BB(6) were verified in Coq.  I doubt other parts of math could take this approach;  however, it is interesting that results can be verified via computer in this field. Indeed- I doubt a referee could verify the results without a computer aid. 

4) Why the interest in BB? Some speculation:

a) Computing power is such that one can actually get out some results (read Scott's blog on BB(5) for more on that).

b) The internet: there are not that many people working on BB but those that are can easily communicate with each other. 

c) Scott's article and his blog posts on it helped generate interest. Since I asked Scott to write the article for my open problems column, I get some credit here also (very little).

d) Results generate interest, and interest generates results.

e) Items a,b,c,d,e all help to reinforce each other. 

A Professor Again

A new dean has taken my place, and I have returned to the professoriate at Illinois Tech, ending thirteen years in administration, six as dean and seven as department chair at Georgia Tech. I won't rule out more administrative roles in the future, but only if the right role presents itself.

I'll teach intro theory in the fall, my first course since 2018, and take a sabbatical in the spring, mostly at Oxford. I plan to focus on writing, hoping to get out another book or books and other projects. It will be hard to go back to traditional computational complexity research, the field has changed considerably. I plan to spend some time understanding how AI changes the way we think about computation. Particularly why we see many of the benefits of P = NP while cryptography remains secure.

Also for the first time in 13 years I don't have a "boss". Technically I report to the department chair, who until a few days ago reported to me. But tenure protects my job, I choose my own research agenda, and teaching and service assignments are more of a negotiation than a top-down decision. Freedom!

For the blog, I have held back talking about the inner workings of universities while I had administrative roles. I'll now be more open in giving my thoughts, at least in general terms.

The next chapter begins...

Two high school students have a new proof of the Pythagorean Theorem / Pythag theorem older than thought

(I wrote this post a while back so its no longer NEW. More important--- if there has been a follow-up to the story that is not in my post, let me know.)  

 We have something NEW and something OLD about the Pythagorean Theorem. Now all we need is something BORROWED and something BLUE.

NEW

Two high school students have a new proof of the Pythagorean Theorem, see here. (An anonymous commenter provides a pointer to their published article in the American Math Monthly.)

They used trigonometry. Oh wait, that sounds circular since Trig is based on the Pythagorean Theorem. While this is a fair question to ask about the theorem, it has recently been accepted for publication and looked at carefully (those two are not equivalent) so it seems to be correct. 

The Pythagorean Theorem is an often-proved-theorem. Often an often-proved-theorem has proofs that use hard math (e.g., proofs that primes are infinite using Ramsey Theory, see my post on that here). However, the new proof of PT seems to be elementary. 

Kudos to them!

OLD:

Pythagorean theorem found on clay tablets 1000 years earlier than Pythagoras: see here.

My students would ask me

 How come Pythagoras didn't go to arXiv to see if someone already had the theorem? 

The Distribution of Prime Numbers: A Geometrical Perspective

Alberto Fraile and Daniel Fernández guest post on random walks generated by the distribution of prime numbers.

In our recent papers, we explored the sequence of prime numbers by defining "random walks" governed by simple algorithms applied to their sequence.

We introduced a prime number visualization called Jacob’s Ladder. The algorithm plots numbers on a 2D graph that oscillates up and down based on the presence of prime numbers, creating a ladder-like structure. The path ascends or descends based on the primality of subsequent numbers. When a prime number is encountered, the path alters direction, leading to a zig-zag pattern. Number 2 is prime, so it flips and goes down. Now 3 is prime, so the next step changes direction and goes up again, so we move up. But 4 is not a prime, so it continues up, and on it goes.

Jacob’s Ladder from 1 to 100,000 (Top) and from 1 to 1,000,000 (Bottom).
The blue line represents y=0, or sea level.

The x-axis can be imagined as sea level, the zig-zag above it as mountains, and those below as ocean chasms. Our intrepid navigator sails eastward, occasionally discovering new lands—sometimes tiny islands, other times vast continents.

As we chart this new world, it is natural to wonder about the location of the next continent (if any), the height of its highest mountain, or the depth of its deepest ocean. One thing we know for sure is that gaps between primes can become arbitrarily large. This suggests there may be no upper bound on the mountains’ heights or the chasms’ depths.

A natural question arises: if the voyage continues into infinity, would this world contain equal amounts of land and sea? Or, more formally, does the construction exhibit symmetry in the limit, with equal numbers of positive and negative points? The beauty of Jacob’s Ladder lies in its simplicity, yet it raises many questions that are surprisingly difficult to answer.

Prime Walk

In our second study, we examined the behavior of a 2D "random walk" determined by the sequence of prime numbers, known as the prime walk (PW), choosing a direction based on the last digit of the next prime (1 down, 3 up, 7 right, 9 left) ignoring the primes 2 and 5.

Graphical representation of three different PWs up to N=108. Color coding represents step progression.

Observing the PW in action raises numerous questions.

For instance, will this PW eventually cover the entire plane as N → ∞? Will the area explored continue expanding indefinitely, or will it reach a limit? Initially, we conjectured the area would be unbounded.

We thought this conjecture might remain unanswered indefinitely, so we challenged the community with a modest prize for anyone who could prove it within two years of publication. Surprisingly, we found the solution ourselves, detailed in our recent work.

Moreover, within the explored region, certain points remain unvisited—small regions or isolated spots. Could some points remain unreachable forever? These straightforward questions, intriguingly, remain remarkably difficult to answer.

If you do well in the UMCP HS Math Competition you may win $1,000,000

The Univ of  MD at College Park holds a HS Math Competition every year. At the reception for the winners Professor Larry Washington points to many past people who did well on the exam. Two stand out for different reasons:

1) Serge Brin did well on the UMCP HS competition and went on to be a Stanford Math Grad Student Drop Out. Oh well. (I originally had Standard instead of Stanford. That sentence will makes sense.) 

2) Sarah Manchester did well on the UMCP HS competition  and went on to win $1,000,000 on Wheel of Fortune. 

Is there a connection between doing well on the UMCP Math Competition and winning $1,000,000 on Wheel of  Fortune? 

Only 4 people have won the $1,000,000. Worse, if you don't win the $1,000,000 you will probably win less than $50,000. An article about those 4 is here. This is so few that while I am sure Sarah is good at Wheel of Fortune (a) she had to also be very lucky, and (b) I doubt being good at Math had much affect on her winning. 

While we are here, lets look at two other game shows.

14 people have won $1,000,000 or more on Who wants to be a Millionaire?, see here. That show has the advantage that even if you don't win $1,000,000 it's not so unusual to get over $100,000.

(What kind of people do not want to be millionaires? I give two answers later.) 

Deal or No Deal has different versions in different countries so it gets more complicated:

UK: 9 big winners, Turkey: 1 big winner, Australia: 4 big winners, America: 2 big winners. 

ANYWAY back to Sarah and Wheel of Fortune: The statement

Sarah did well on the UMCP HS Math Competition and went on to win $1,000,000 on Wheel of Fortune

is technically true but conveys a causality that is not true. 

Who does not want to be a millionaire? 

Would be a terrible name for a quiz show. However, taking it as a question the answer is with one caveat: I define Millionaire as someone who has AROUND $1,000,000. 

a) Billionaires. Actually, anyone who has much more than  $1,000,000 would not want to come down to only $1,000,000.

b) People who think it would change their life in ways they don't want. 

Fulbright Memories

As the entire Fulbright board resigned last week and as the program that promotes international visits for US researchers, and vice-versa, may not survive the Trump administration, I thought I would recount some memories from my Fulbright scholarship to the Netherlands in 1996-97.

The program had considerable paperwork for a relatively small stipend, but it went beyond the compensation. I went to a meeting in Amsterdam with the other fellows, mostly grad students and postdocs. I was the old one as a recently tenured associate professor. The others had strong reasons for being in the Netherlands: An historian who wanted to research the Dutch army, and a piano player with hands too small who came to study with the world's leading teacher on a specialized narrow-keyboard grand.

And so they asked me why I would go to the Netherlands from the US to study computer science. But I spent the sabbatical year at the Centrum Wiskunde & Informatica (Center for Mathematics and Computer Science) in Amsterdam working with Harry Buhrman, Leen Torenvliet, Paul Vitányi and others. I also made several trips to universities in Germany, England, France and Israel, and had one of my best research years.

My coolest Fulbright experience was having Thanksgiving dinner at the US ambassador's house in The Hague, perhaps the most American thing I did during the year.

I also participated in celebrations marking the fiftieth anniversary of the Fulbright program, established in 1946 to encourage international educational and research collaborations, alongside the Marshall Plan and NATO, to draw the US closer to Europe and later the rest of the world. Too bad we seem to be moving away from those ideals today. 

Lance never thought he would see a Pope who roots for the same team as him. And now...

 A year ago if I showed you a picture of The Pope wearing a Baseball cap for the Chicago White Sox  (or any Amercan team) you would assume it was computer-generated.  And you would likely be right. 

Are there any real pictures of any Pope before Pope Leo XIV with a baseball cap on? 

I doubt it 

A real picture of Pope Leo wearing a Chicago White Sox baseball cap is here.

1) Having an American Pope is so incongruent with how we think of Popes that pictures like Pope Leo XIV in a baseball cap look very odd.

2) Pope Francis was a soccer fan (see here).  Is there a real  pictures of him wearing a soccer jersey?

3) Before the web we didn't know much about the personal lives of leaders. I don't just mean we didn't know about (say) their affairs; we didn't even know about non-controversial things like what sports team they root for. 

4) Lance has tweeted that he never thought he would see the day where he and The Pope rooted for the same baseball team. I want to see a picture of The Pope and Lance together at a game, both wearing Chicago White Sox caps. A real picture may be hard to do, but I suspect that once The Pope  sees this post he will create such a picture. 

5) I hope the next Pope is a fan of the San Diego Padres for two reasons

a) The name of the team.

b) They have never won a World Series. They need all the help they can get.

Defending Theory

In the June CACM, Micah Beck writes an opinion piece Accept the Consequences where he is quite skeptical of the role of theory in real-world software development, concluding

It is important that we teach practical computer engineering as a field separate from formal computer science. The latter can help in the understanding and analysis of the former, but may never model it well enough to be predictive in the way the physical sciences are.

I certainly agree that theoretical results can't perfectly predict how algorithms work in practice, but neither does physics. The world is much more complex, both computationally and physically, to perfectly model. Physics gives us an approximation to reality that can help guide engineering decisions and theory can do the same for computation.

You need a basis to reason about computation, lest you are just flying blind. Theory gives you that basis.

Let's consider sorting. Beck complains that Quicksort runs in \(O(n^2)\) time in the worst case even though it is used commonly in practice, while the little-used Insertion sort runs in worst-case \(O(n\log n)\). Let's assume Beck meant an algorithm like heapsort that actually has \(O(n\log n)\) worst-case performance. But theorists do more than fixate on worst-case performance, Quicksort runs in \(O(n\log n)\) on average, and on worst-case if you use a random pivot, or a more complex deterministic pivoting algorithm. Introsort combines Quicksort efficiency and worst-case guarantees and is used in some standard libraries.

Beck worries about secondary storage and communication limitations but theorists have studied sorting in those regimes as well. 

The other example he talks about is about a theoretical result that one cannot use an unreliable network to implement one that is completely reliable while textbooks consider TCP to be reliable. But in fact TCP was designed to allow failure because it took account of the theoretical result, not in spite of it.

Beck ends the article talking about Generative AI where theory hasn't kept up with practice at all. Beck calls for using classical AI tools based on formal logic as guardrails for generative AI. However, the lack of theoretical understanding suggests that such guardrails may significantly weaken generative AI's expressive power. Without adequate theory, we must instead rely more heavily on extensive testing, particularly for critical systems.

There are stronger examples Beck could have used, such as algorithms that solve many NP-complete problems efficiently in practice despite their theoretical intractability. Even here, understanding the theoretical limitations helps us focus on developing better heuristics and recognizing when problems might be computationally difficult.

I agree with Beck that relying solely on the theoretical models can cause some challenges but rather than have the students "unlearn" the theory, encourage them to use the theory appropriately to help guide the design of new systems.

Beck's call to separate software development from theory only underscores how important we need to keep them intertwined. Students should know the theoretical foundations, for they shape problem solving, but they should also understand the limitations of these models.

The New Godel Prize Winner Tastes Great and is Less Filling

David Zuckerman

The 2025 Gödel Prize has been awarded to Eshan Chattopadhyay and David Zuckerman for their paper

Explicit two-source extractors and resilient functions

which was in STOC 2016 and in the Annals of Math in 2019. 

We (Bill and Lance) care about this result for two different reasons.

BILL: The result has applications to constructive Ramsey---

LANCE: Ramsey Theory? Really? This is a great result about

Eshan Chattopadhyay

pseudorandomness! In fact the only interesting thing to come out of Ramsey Theory is the Probabilistic Method (see our discussion of this here). 

BILL: Can't it be BOTH a great result in derandomization AND have an application to Ramsey Theory. Like Miller Lite: Less Filling AND Tastes Great (see here)

LANCE: But you don't drink!

BILL: Which means I can give a sober description of their application to Ramsey Theory.

All statements are asymptotic.

Let \(R(k)\) be the least \(n\) so that for all 2-colorings of \(K_n\) there is a homog set of size \(k\).

Known and easy: \(R(k)\le 2^{2k}/\sqrt{k} \)

Known and hard: \(R(k) \le 3.993^k \). How do I know this is true? Either I believe the survey papers on these kinds of results (see here) or a former student of mine emailed me a picture of a T-shirt that has the result (see here) from (of course) Hungary.

Known and Easy and Non-Constructive: \(R(k)\ge k2^{k/2}\)

Can we get a constructive proof? There were some over the years; however, the paper by Eshan Chattopadhyay and David Zuckerman improves the constructive bound to exponential in \(  2^{(\log k)^\epsilon}.\) 

SO Lance, why do you care?

LANCE: First of all when I chose this paper as one of my favorite theorems (a far bigger honor than the so-called Gödel Prize) I gave the post the clever title Extracting Ramsey Graphs that captures both the pseudorandomness and the Ramsey graphs. But of course the Ramsey result is just a minor corollary, the ability to get a near perfect random bit out of two independent sources of low min-entropy is the true beauty of this paper. 

BILL: You have no sense of good taste.

LANCE: Well at least I'm not less filling.

Rules vs Standards

You can write laws that are very specific, like the US tax code, or open to interpretation like the first amendment. In the literature these are known as rules and standards respectively. 

In computational complexity, we generally think of complexity as bad. We want to solve problems quickly and simply. Sometimes complexity is good, if you want to hide information, generate randomness or need some friction. But mostly we want simplicity. How does simplicity guide us in setting guidance, either through rules or standards?

 

Rules are like a computer program. Feed in the input and get an output. Predictable and easy to compute. So why not always have tight rules?

Nobody ever gets a computer program right the first time, and the same goes for rules. Rules can be overly restrictive or have loopholes, leading to feelings of unfairness. Rules can require hoops to jump through to get things done. Rules don't engender trust to the ones the rules apply to, like very tight requirements on how grant funds can be spent. We know that in general we can't predict anything about how a computer program behaves, so why do we trust the rules? 

A good example of a standard is that a PhD dissertation requires significant original research. Rules are things like the exact formatting requirements of a thesis, or statements like a CS thesis must contain three papers published in a specific given set of conferences. 

As an administrator I like to focus on making decisions based on what's best for my unit, as opposed to ensuring I followed every letter of every rule. Because if you live by the rules, you'll die by the rules.  People will try to use their interpretation of the rules to force your hand.

Sometimes we do need strict rules, like safety standards, especially for people unfamiliar with the equipment. Structured rules do give a complete clarity of when an action is allowed. But it also gives an excuse. Have you ever been satisfied by someone who did something you didn't like but said "I was just following the rules"?

Even strict rules tend to have an out, like a petition to take a set of courses that don't exactly match the requirements of a major. The petition is a standard, open to interpretation to capture what the rules don't. 

As a complexity theorist I know what programs can't achieve, and as an administrator I see the same with rules. I prefer standards, principles over policies. Set your expectations, live by example, and trust the people, faculty, staff and students, to do the right thing and push back when they don't. People don't want strict rules, but they mostly act properly when they believe they are trusted and have wide latitude in their work. 

Complexity theory of hand-calculations

 (Thanks to David Marcus who sent me the video I point to in point 4 of this post. Tip for young bloggers (if there are any) you can have a half-baked idea for a post and then someone sends you something OR you later have an idea to make it a full-baked idea for a post. That's what happened here. So keep track of your half-baked ideas.)

1) When I was 10 years old I wanted to find out how many seconds were in a century. I didn't have a calculator (I might not have known what they were). I spend a few hours doing it and I got AN ANSWER. Was it correct? I didn't account for leap years. Oh well.

(An astute reader pointed to a website that does the centuries-to-seconds conversion as well as many other conversions. It is here. If such was around when I was a kid, what affect would it have on my interest in math? Impossible to know.) 

2) Fast forward to 2024: I wanted to find the longest sequence of composites all \( \le 1000\). One long sequence I found by hand is the following (I also include the least prime factor):

114-2, 115-5, 116-2, 117-3, 118-2, 119-7, 120-2, 121-11, 122-2, 123-3, 124-2 , 125-5, 126-2

length 13.

I wanted to find the answer WITHOUT using a computer program or looking at list of primes online (though I do allow a calculator just for division and multiplication). 

Of more interest mathematically is trying to prove that there is no sequence of length 14. (If there is, then perhaps the attempt will lead us to it.) 

Assume there was a sequence of consecutive composites \(\le 1000\) of length 14.

Map each one to the least prime that divides it. 

At most 7 of them map to 2

At most 3 of them map to 3

At most 2 of them  map to 5

At most 1 of them  map to 7.

At most 1 maps to 11. (Can look at 11*p for all primes \(11\le p \le 89\) and see any of them are in a sequence of length 14.) 

I'll stop here. This is getting tedious and might be wrong. So I asked Claude. It gave me a  sequence of composites of length 19. Here it is (I include the least prime factor):

888-2, 889-7, 890-2, 891-3, 892-2, 893-19, 894-2, 895-5, 896-2, 897-3, 898-2, 899-29, 900-2, 901-17, 902-2, 903-3, 904-2, 905-5, 906-2.

Can one show by hand that there is no sequence of length 20? 

3) The more general question: what is the complexity of finding the longest string of composites all \( \le n\) . This is actually many questions:

a) By hand: by which I mean only allowing multiplication and division and only of numbers \(\le n.\)

b) Theoretically. Use whatever fancy algorithms you want.

c) Theoretically but can assume some Number theory Conjectures that are widely believed. The Wikipedia page on prime gaps is here. (ADDED LATER- an astude commenter pointed out that we want LARGE gaps between primes, but the wikipedia article is about SHORT gaps between primes.) 

d) Do a,b,c for the set version which is as follows:  Given \(n\) and\( L\) determine if there a sequence of consecutive composites of length L that are all \(\le n\).  

4) Does anyone else care about calculation-by-hand? Yes! There are people who want to compute\(\ pi\) to many places JUST BY HAND. Here is a video about them here. Spoiler alert: they did very well. 

The Hilltop Story

 

On Route 1 in Saugus, Massachusetts, about a twenty minute drive from Cambridge, stood the Hilltop Steak House. When I went to graduate school in the late 80's, Hilltop led all restaurants in the United States by sales (about $30 million in annual revenue) and volume (about 2.5 million customers).

I went there several times during graduate school. Despite the size, about 1500 seats, always a long wait but worth it to get a good steak at a price a grad student could afford. 

But in 1994, Hilltop was bought by an investment company from the original Giuffrida family. The cost of labor went up and to keep costs reasonable, the new owners cut the quality of the meat. No longer a place to get good steak at a good price and with changing tastes, they lost customers and would finally close in 2013.

Computer Science as an academic discipline has had its Hilltop moment with tremendous growth pretty consistently from 2010 through about 2023. But with the growth of AI and an uncertain job market, if we don't maintain quality and adjust to the new needs and interests of our students, CS may become just a road sign on Route 1.

Some are Mathematicians, some are Carpenters' Wives, Some are Popes.

 (Trivia: What song has the lyric Some are Mathematicians, some are Carpenters's wives ? It's not a parody song, though sometimes it's hard to tell a  parody song from a so-called real song.)

In my post about Pope Leo XIV I made the following comments in different parts of the post:

Pope Leo XIV has a degree in Mathematics.

Prevost [his pre-Pope name] has a degree in mathematics from Villanova. 

He is not the first Pope to know some mathematics.

I also wrote:

Since Pope Leo XIV was a mathematician, as Pope he won't only know about sin but also about cos.

Someone emailed me about this line, not to say it was a bad joke or even a good joke, but to say 

Since Pope Leo XIV was a mathematician: What qualifies one to be considered a mathematician?

A few thoughts on this question.

1) I blogged about this topic here. Hence today I will discuss issues I did not discuss then. 

2) Robert W  Prevost wrote a book that (just from the title) seems to use some math:

Probability and Theistic Explanations, see here.

that was published in print in 1990 and online in 2023.  I wonder if it will sell more copies now.  I am tempted to ask for a free copy to read and do a review of, but I'm not sure I really want to read it. 

One would think that if someone named Robert Prevost wrote a book that seems to use math and theology then it would be the Robert Prevost who is now called Pope Leo XIV. I thought that. A commenter on my blog thought that. But Lance read an earlier version of this post and pointed out that 

Robert W Prevost NE Robert  F Prevost AND

Robert F  Prevost = Pope Leo XIV.

Hence, alas, the author of the book is NOT Pope Leo XIV. It's striking how plausible it would be that Pope Leo IS the author.  The book STILL might sell more copies since people may think it's by the Pope. 

Robert W Prevost's Wikipedia page is here.

Robert F Prevost's Wikipedia page is here.

3) If someone keeps LEARNING math but doesn't DO math I WOULD consider them a mathematician.

4) If someone is a math crank then the question of are they a mathematician will depend on how cranky they are.

5) If one KNOWS a lot of math but is neither learning anymore or doing any more (perhaps myself when I retire) can you consider them a mathematician?

6) If someone gets a PhD from MIT in Pure math but then goes to industry and programs would you consider them to be a mathematician?

7) If X is NOT a math crank and X considers themselves a mathematician, are they a mathematician?

8) I WOULD consider applied math to be math. This should not need to be said but there may be some pure-math-snobs reading this post. Computer scientists, statisticians, are more of a borderline case that, without being a snob, I might not consider mathematicians.

9)  Someone posted on the blog where this came up Does Lance consider himself a mathematician? I asked Lance and he said:

For the next 37 days I consider myself a Dean. After that, who knows?

The Blog of Record

On Saturday, I had my last Illinois Tech graduation as dean before I step down at the end of June. The College of Computing had nearly 1600 graduates and I shook many, many hands that morning.

After graduation I caught a plane to Washington, DC to attend the wedding of my daughter's college friend. We were invited because we became good friends with the bride's parents when we lived in Atlanta. My last trip before Covid was to DC for an NSF panel and this was my first trip to Washington since. 

The out-of-town guests were housed at the Hyatt Regency Bethesda, coincidentally the same hotel that hosted STOC 2009. My favorite STOC talk of all time took place in that building. But I remembered nothing about the venue except for the jogging path near the hotel.

No trip to the DMV would be complete without seeing my co-blogger Bill Gasarch in person for the first time in years. We chatted about many things, most notably his last few posts where he joked about the new pope's undergraduate math thesis, taken seriously by both our readers and ChatGPT. I reminded Bill that we are the blog of record, often used by wikipedia as a primary source for much in and out of complexity. Later Bill took out the fake thesis titles.

With graduation behind me, not much more for me to do as dean before my term ends. On the plane ride home, I thought about the question everyone asks me: What's next? I have no idea, but it's going to be fun.

Is Satire Dangerous in the AI-Age?

There have been times when satire has been mistaken for reality. A list of Onion stories that were mistaken for reality (or was it a mistake?) is here. When I say mistaken for reality I mean that a large set of people were fooled.

My own Ramsey-History-Hoax (blog here, latest version of the paper here) has fooled some people; however the number of people is small since the number of people who know the underlying math is small. 

In my last blog (see here) I said that the Pope Leo XIV majored in math (that is true) and then I gave a false title for his thesis (I HAVE SINCE REMOVED THE ENTIRE PASSAGE). 

 Later in the post I said that his ugrad thesis was not on that topic, but  gave another false title (I HAVE RMEOVED THAT AS WELL.) 

I thought the reader would know that it was false, but one comment inquired about it so I left a comment admitting it was false.

This is all very minor: Not that many people read this blog and very few non-math people would care about what the topic of the  Pope's undergraduate thesis.

The last part of the last sentence is false. Its the POPE! People Do care about his background. 

But surely my blog post isn't so well read so as to make the fictional  title of his thesis a hoax that fools a lot of people. 

Even so, I left a comment wondering if LLM's might learn the incorrect title of the Pope's ugrad thesis. 

A reader named E posted the following:

 It might be too late. I did this search this evening:

E: Did Pope Leo XIV study Ramsey Theory?

Gemini: Pope Leo XIV, whose given name is Robert Francis Prevost,
earned a Bachelor of Science degree in mathematics from Villanova
University in 1977. His undergraduate thesis focused on Rado's Theorem
for Nonlinear Equations.

0) This may not be too bad- one would have to ask about The Pope and Ramsey Theory to get that answer. But in the future this answer might pop up on the question`What did the Pope Study as an Undergraduate' or similar questions.

1) Might future satires or April Fool's Day jokes be mistaken for reality in the future by AI and hence reach a much larger audience than this blog does?

2) If so, should we be careful with what we post (not sure how to do that)?

3) What about people who have a much larger following than complexityblog  (yes, there are such people)?

4) In the past one had to be a celebrity or similar to change peoples perception of reality (see Stephen Colbert and Wikipedia here). Now a complexity blogger may be able to change people's perception of reality. Hence I ask

Is Satire Dangerous in the AI-Age?

 

 

 

 

 

A Bittersweet Anniversary

The National Science Foundation was founded on May 10, 1950, 75 years ago last Saturday. No doubt the NSF has seen better days, but first let's take a look back.

At the end of World War II, Vannevar Bush, Director of the Office of Scientific Development, wrote Science, The Endless Frontier, where he laid out the importance of scientific research and the need for the US government to foster that research. 

A new agency should be established, therefore, by the Congress for the purpose. Such an agency, moreover, should be an independent agency devoted to the support of scientific research and advanced scientific education alone. Industry learned many years ago that basic research cannot often be fruitfully conducted as an adjunct to or a subdivision of an operating agency or department. Operating agencies have immediate operating goals and are under constant pressure to produce in a tangible way, for that is the test of their value. None of these conditions is favorable to basic research. Research is the exploration of the unknown and is necessarily speculative. It is inhibited by conventional approaches, traditions, and standards. It cannot be satisfactorily conducted in an atmosphere where it is gauged and tested by operating or production standards. Basic scientific research should not, therefore, be placed under an operating agency whose paramount concern is anything other than research. Research will always suffer when put in competition with operations.

The report laid out the National Research Foundation that would actually spread across three agencies, DARPA, NIH, and the NSF.

While Bush didn't significantly mention computing, given the time, Computing would become a central part of NSF's mission with the establishment of the Computing and Information Science and Engineering (CISE) directorate in 1986, placing Computing at the same level as the Math and Physical Sciences Directorate and the Engineering Directorate.

In 1999, the President’s Information Technology Advisory Committee (PITAC) issued a report that led to the NSF Information Technology Research (ITR) program, which became one of the largest NSF research initiatives of the early 2000s. The report helped reframe computing not just as infrastructure but as a scientific discipline in its own right, deserving of the same kind of basic science funding as physics or biology.

CISE has led many initiatives through the years, for example the TRIPODS program established several centers devoted to the theoretical study of data science.

In recent weeks, the NSF director stepped down, hundreds of grants were canceled, new grants were put indefinitely on hold, indirect costs on new grants will be capped at 15%, and many staff members were pushed out. Divisions below the directorates are slated for elimination, advisory committees have been disbanded, and Trump's proposed budget cuts NSF’s allocation by about half. The CISE AD (Assistant to the NSF Director, or head of CISE), Greg Hager, stepped down last week and through the CRA sent a message to the community.

Under these circumstances, my ability to carry out my vision, to provide a voice for computing research, and to provide authentic leadership to the community are diminished to the point that I can have more impact outside NSF than within it. Echoing Dr. Nelson’s powerful article, leaving “allows me to speak more clearly in my own language,” and, in doing so, even more effectively amplify the work of the incredible, dedicated CISE leadership and staff who continue to strive to fulfill NSF’s mission. 

As I move beyond NSF, I will continue to make the case for computing research. Computing is central to so much in today’s world and computing advances are now core assets to the Nation’s research enterprise. NSF’s support for the past 75 years has forcefully demonstrated the value of computing research for advancing national health, prosperity and welfare; enhancing national economic competitiveness; securing the national defense and helping promote all of science and engineering. NSF-funded work has continually catalyzed new innovations, created new industries, and made us the envy of the world.  

We all need to join Greg in continuing the fight to ensure that Vannevar Bush's vision continues to survive another 75 years and beyond.

Random Thought on the New Pope (the actual New Pope, not the TV series). He was a math major!

 The New Pope is Pope Leo XIV (pre-Pope name is Robert  Prevost). 

1) Pope names are one of the few places we still use Roman Numerals. I saw an article that was probably satirical that Americans prefer Roman Numerals (the numbers Jesus used) over Arabic Numerals. Also note that Pope Francis did not have a Roman Numeral- that is because he is the first Pope Francis. They could call him Pope Francis I now, rather than later, to avoid having to rewrite things. (John Paul I took the name John Paul I.)

2) Over the years I have  read the following and had the following thoughts (Spoiler- I was wrong on all of them)

a) The last non-Italian Pope was Pope Adrian VI who was Pope from Jan 9 1522 to Sept 14 1523. His Wikipedia entry: here. He was 80 years old when he became Pope and died of  a heart attack.

BILL THOUGHT: We will never see a non-Italian Pope again.

REALITY: John Paul II from Poland was Pope from 1978 until 2005. His Wikipedia page is here

MORE REALITY: Since then we've had Pope Benedict XVI (Germany), Pope Francis I (Argentina),and Pope Leo  XIV (America). I now wonder if we will ever have an Italian Pope again but I make no predictions. 

b) There will never be an American Pope because people think that America already has too much power and if there ever was an American Pope then people would think it was engineered by the CIA.

BILL THOUGHT: That sounded correct to me. Not that the election would be engineered by the CIA, but that people would think that. 

REALITY: Pope Leo XIV is American. Some MAGA people are calling Pope Leo a Woke Marxist Pope (see here). Not the type the CIA would install. 

QUESTION: How much power does the Pope really have? I ask non-rhetorically as always. 

c) The shortest Pope Reign was Pope Urban VII (1590) who reigned for 13 days. The tenth shortest was Pope Benedict V (964) who reigned for 33 days. I originally thought the short reigns were from assassinations, but I looked it up and there were two that may have been murdered, but the rest died of natural causes. Having looked it up I wrote it up here.

BILL THOUGHT: The 10th shortest reign was 33 days. With better health care and less skullduggery in the Papacy that won't happen again.

REALITY: Pope John-Paul I in 1978 died of a heart attack after being Pope for 33 days. 

d) The last Pope to resign was Pope Gregory XII in 1415 (his Wikipedia page is here). He resigned to heal a  schism in the church (its more complicated than that, see his Wikipedia page).

BILL THOUGHT: We will never see a Pope resign again.

REALITY: Pope Benedict XVI resigned (see here for the Wikipedia page on the resignation) in 2013. He said it was for health reasons.

BILL THOUGHT: Now that Pope Benedict has resigned it will be easier for later popes who feel they are not healthy enough for the job to resign. But I make no predictions. 

3) Pope Leo XIV has a degree in Mathematics. I emailed the following to my Ramsey Theory class which is an excerpt from his Wikipedia Page with one incorrect sentence.  (NOTE- I USED TO HAVE A TITLE OF THE POPE'S UGRAD MATH THESIS, WHICH WAS FAKE, BUT SINCE AI'S PICKED IT UP AS REAL I HAVE DELETED THAT, AND ALSO DELETED A LATER PART OF THIS POST WHERE I  GIVE THE REAL TITLE, WHICH IS ALSO FAKE.)

Prevost earned a Bachelor of Science (BS) degree in mathematics from Villanova University, an Augustinian college, in 1977.  He obtained a Master of Divinity (MDiv) from Catholic Theological Union in Chicago in 1982, also serving as a physics and math teacher at St. Rita of Cascia High School in Chicago during his studies. He earned a Licentiate of Canon Law in 1984, followed by a Doctor of Canon Law degree in 1987 from the Pontifical University of Saint Thomas Aquinas in Rome. His doctoral thesis was titled The Role of the Local Prior in the Order of Saint Augustine. Villanova University awarded him an honorary Doctor of Humanities degree in 2014

4) He is not the first Pope who knew some mathematics. In a general sense people used to be more well-rounded before fields got so specialized. So in that sense I am sure that some prior Popes knew some math. But more concretely Pope Sylvester II was, according to the article When the Pope was a Mathematician Europe's leading mathematician, (at the time a modest distinction) reigning as Pope Sylvester from  997 to1003. His Wikipedia page is here.

5) Since Pope Leo XIV was a mathematician, as Pope he won't only know about sin but also about cos.

6) The name Leo struck me since one of my TAs is named Leo. I asked him, if he became Pope, would he change his name. He said 

Hmm, after careful consideration, I think I would take another name. I like being Leo, but I think I would want to try out a different name. I looked up Papal names, and I would probably pick something cool like Boniface, Honorius, or Valentine. But I would do the name change after the semester ends so as not to screw up the payroll office. 

7) Popes did not always change their names. For a long article on that see here. For a short version here are some points:

a) The first Pope to change his name was born Mercurious, a Pagan God Name, and changed it to be Pope John II. That was in 533. 

b) The name-change did not become standard for a while. Before the year 1000 only 3 Popes changed their names, all to John. The other two had given name Peter and felt they should not take the name Peter since Peter was the first Pope and an apostle. Kind of like having a jersey number retired by a sports team.

c) After the year 1000 some changed,some didn't, but the last one to not change was Pope Marcellus II in 1555. His reign was 22 days, though I doubt that is related to not changing his name. 

8) Math question: What is the average length of a Papacy and what is the average length of a presidency (of America)?

The first Pope was Peter, began in 30AD.

The 266th Pope was Francis whose reign ended in 2025.

SO we have 266 Popes in 1995 years, so the average reign is 7.5 years.

The first president was George Washington whose presidency began in 1789.

The 46th president was Joe Biden and it ended in 2025.

SO we have 46 presidents (we ignore the Grover C thing) in 236 years, so the avg reign is 5.1 years.

The 7.5 and 5.1 are more different than they look since the length of presidents is usually 4 or 8 years,while the length of a Papal reign has had a min  of 13 days and a max of 31 years (Pope Pius IX).

I'l be curious what the standard deviation and deviance are for both Papal Reigns and Presidents. I suspect that it's much bigger for Papal reigns, and not just because the presidency is at most 8 years (with one exception-FDR was president for 12 years). 

9) There was betting and betting markets on the next Pope. This raises the question of how often someone NOT on the short list (so probably not bet on much) becomes Pope. Lets look at the last few:

Pope Leo XIV- not on the short list

Pope Francis- not on the short list

Pope Benedict XVI- a favorite

Pope John Paul II- not on the short list

Pope John Paul I- I don't know and I will stop here.

Upshot: it may be foolish to bet on the next Pope. Even more so than betting on the Vice Prez nominee which I commented on here.

10) Art imitates life: Some of the cardinals at the conclave watched the movie Conclave to get an idea of what a conclave is like. I suspect the real conclave was much less dramatic than the movie Conclave. 

11) Trump thinks that since the Pope is American, America should annex the Vatican. Or does he? See this article here.  

12) Pope Leo has an opinion about AI (I wonder if his math background helps); see here. This is a good example of the limits to the Pope's power-does anyone who can do anything care what Pope Leo XIV thinks? I ask non-rhetorically as always.

Using AI for Reviews

I reviewed a paper recently and I had to agree not to use AI in any aspect of the reviewing process. So I didn't but it felt strange, like I wouldn't be able to use a calculator to check calculations in a paper. Large language models aren't perfect but they've gotten very good and while we shouldn't trust them to find issues in a paper, they are certainly worth listening to. What we shouldn't do is have AI just write the review with little or no human oversight, and the journal wanted me to check the box probably to ensure I wouldn't just do that, though I'm sure some do and check the box anyway.

I've been playing with OpenAI's o3 model and color me impressed especially when it comes to complexity. It solves all my old homework problems and cuts through purported P v NP proofs like butter. I've tried it on some of my favorite open problems where it doesn't make new progress but it doesn't create fake proofs and does a good job giving the state of the art, some of which I didn't even know about beforehand.

We now have AI at the level of new graduate students. We should treat them as such. Sometimes we give grad students papers to review for conferences but we need to look over what they say afterwards, the same way we should treat these new AI systems. Just because o3 can't find a bug doesn't mean there isn't one. The analogy isn't perfect, we give students papers to review so they can learn the state of the art and become better critical thinkers, in addition to getting help in our reviews. 

We do have a privacy issue. Most papers under review are not for public consumption and if uploaded into a large-language model they could become training data and be revealed if someone asks a relevant question. Ideally we should use a system that doesn't train on our inputs if we use AI for reviewing but both the probability of leakage and amount of damage is low, so I wouldn't worry too much about it.

If you are an author, have AI review your paper before you submit it. Make sure you ask AI to give you a critical review and make suggestions. Maybe in the future we'd required all submitted papers to be AI-certified. It would make the conference reviewers jobs less onerous.

For now, humans alone or AI alone is just not the best way to do conference reviews. For now when you do a review, working with an AI system as an assistant will lead to a stronger review. I suspect in the future, perhaps not that far, AI alone might do a better job. We're not there yet, but we're further than you'd probably expect.

My response to Scott's least controversal post ever!

In a recent post by Scott (see here or just read my post which includes his post) he listed topis that he conjectured would NOT cause an outrage.

I was going to write a long comment in his comments section,  which would only be read by people who got to comment 100 or so. OR I could comment on it in my blog.

SO, here is his blog post and my comments on it.

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

A friend and I were discussing whether there’s anything I could possibly say, on this blog, in 2025, that wouldn’t provoke an outraged reaction from my commenters.  So I started jotting down ideas. Let’s see how I did.

1) Pancakes are a delicious breakfast, especially with blueberries and maple syrup.

BILL: Pancakes have a terrible ratio of health to enjoyment.

2) Since it’s now Passover, and no pancakes for me this week, let me add: I think matzoh has been somewhat unfairly maligned. Of course it tastes like cardboard if you eat it plain, but it’s pretty tasty with butter, fruit preserves, tuna salad, egg salad, or chopped liver.

BILL: UNFAIRLY MALIGNED. That's an interesting concept in itself since there are so many opinions on the internet there is not really a consensus on.... anything.  My 2 cents: I like the taste of cardboard and hence I like the taste of matzoh.

3) Central Texas is actually really nice in the springtime, with lush foliage and good weather for being outside.

BILL: I WILL DEFER to Scott, who is now a Texan, on this one.

4) Kittens are cute. So are puppies, although I’d go for kittens given the choice.

BILL: PETS are a waste of time and energy. My opinion shows something more important: Scott and I disagree on this but we are not OUTRAGED at each other.

5) Hamilton is a great musical—so much so that it’s become hard to think about the American Founding except as Lin-Manuel Miranda reimagined it, with rap battles in Washington’s cabinet and so forth. I’m glad I got to take my kids to see it last week, when it was in Austin (I hadn’t seen it since its pre-Broadway previews a decade ago). Two-hundred fifty years on, I hope America remembers its founding promise, and that Hamilton doesn’t turn out to be America’s eulogy.

BILL: Agree. Also lead to the best math novelty song of all time, See here.

6) The Simpsons and Futurama are hilarious.

BILL: The cliche The Simpsons was better in its first X seasons is true, but it can still crank out an excellent episode once in a while. The episode  Treehouse of Horrors: Simpsons Wicked This Way Comes  (from 2024--Wikipedia entry here)  is a microcosm of the series: Two okay satires of two okay stories by Ray Bradbury and then a BRILLIANT satire of Fahrenheit 451. (Spell check thinks Treehouse is not a word .I looked it up to see what the geat God Google would say.  The Treehouse of Horror episodes of the Simpsons use Treehouse. I googled Is Treehouse One word and got a YES. This is a rare time when spellcheck is just wrong.)

BILL: I think Futurama benefited from being on the air, then off, then on, then off, then on (is it on now?) since it came back with new stories. 

7) Young Sheldon and The Big Bang Theory are unjustly maligned. They were about as good as any sitcoms can possibly be.

BILL: AGREE though again, some malign, some praise, some just watch it and laugh.  I've had 5 blog posts inspired by these shows, and a few more that mention them in passing. I recently saw TBBT on a list of OVERRATED shows so someone must be liking it to cause it to be on that list.

BILL: In an earlier era it would be hard to watch every episode of a TV show since they were on once, and then maybe some reruns but maybe not.  I've seen every episode of both TBBT and YS without even trying to. 

BILL: (Added later inspired by a comment) For the entire run of the series YS the actress who played Missy, Raegan Revod did not have a Wikipedia page. I noted this in two prior blog posts. I am happy to say that she finally does, see here. It is a long overdue honor. (Is it an honor?) 

8) For the most part, people should be free to live lives of their choosing, as long as they’re not harming others.

BILL: TRICKY- the For the most part causes arguments and outrage. Example: Helmet laws for motorcyclists. Should they be free to get brain injuries that the rest of society must pay for?  I ask non-rhetorically as always.

9) The rapid progress of AI might be the most important thing that’s happened in my lifetime. There’s a huge range of plausible outcomes, from “merely another technological transformation like computing or the Internet” to “biggest thing since the appearance of multicellular life,” but in any case, we ought to proceed with caution and with the wider interests of humanity foremost in our minds.

BILL: I doubt it's the biggest thing since the appearance of multicellular life.  My blog on AI here. I agree that caution is needed, though in two ways:

a) Programs are written that we don't understand and might be wrong in serious ways. (You can replace programs with other things.)

b) The shift in the job market may be disruptive. People point to that farmers stopped farming and moved to factory work, but there was an awful transition time. And the AI-shift might be much faster. Fortunately for me, ChatGPT is terrible at solving problems in Ramsey Theory. For now.

10) Research into curing cancer is great and should continue to be supported.

BILL: This one seems obvious but one has to ask the broader question: Which medical things should be funded and why? More generally, what should the government fund and why? These require careful thought. 

11) The discoveries of NP-completeness, public-key encryption, zero-knowledge and probabilistically checkable proofs, and quantum computational speedups were milestones in the history of theoretical computer science, worthy of celebration.

BILL: Of course I agree. But the following questions haunt me:

a) What is a natural problem and do we spend too much time on unnatural ones. Even Graph Isom which seems like a natural problem does not have any applications (see my blog posts here and a ChatGPT  generated post on this topic here).

b) Darling has asked me IF WE PROVE P NE NP THEN HOW WILL THAT HELP SOCIETY? Good question.

12) Katalin Karikó, who pioneered mRNA vaccines, is a heroine of humanity. We should figure out how to create more Katalin Karikós.

BILL: Cloning?

BILL: This raises the general question of how much ONE PERSON is responsible for great scientific discoveries.

13) Scientists spend too much of their time writing grant proposals, and not enough doing actual science. We should experiment with new institutions to fix this.

BILL: Also writing up papers and waiting for referees reports. A paper I submitted with students 3 years ago was accepted (Yeah) with many helpful comments (Yeah) but way too late to help those students get into grad school (they did anyway- Yeah). We had forgotten what we wrote and why we cared.  (Boo) We did get the corrections done and resubmitted it. So I could say it will be out soon. But that's the weird thing-we posted it to arxivs three years ago so its been out for a while. 

14) I wish California could build high-speed rail from LA to San Francisco. If California’s Democrats could show they could do this, it would be an electoral boon to Democrats nationally.

BILL: This seems fine but seems like an arbitrary thing to want as opposed to other pairs of cities and other achievement.

15) I wish the US could build clean energy, including wind, solar, and nuclear. Actually, more generally, we should do everything recommended in Derek Thompson and Ezra Klein’s phenomenal new book Abundance, which I just finished.

BILL: You inspired me to recommend the book Abundance to my book club. This is the second time that's happened- I also had them read the Stephen Pinker Book Enlightenment Now based on your blogs recommendation.

BILL: Some of the problem is political and some is technical. I don't know how much of each.

16) The great questions of philosophy—why does the universe exist? how does consciousness relate to the physical world? what grounds morality?—are worthy of respect, as primary drivers of human curiosity for millennia. Scientists and engineers should never sneer at these questions. All the same, I personally couldn’t spend my life on such questions: I also need small problems, ones where I can make definite progress.

BILL: Indeed-I like well defined questions that have answers, even if they are hard to answer. The  questions you raise are above my pay grade. 

17) Quantum physics, which turns 100 this year, is arguably the most metaphysical of all empirical discoveries. It’s worthy of returning to again and again in life, asking: but how could the world be that way? Is there a different angle that we missed?

BILL: I can either have an opinion on this or defer to one of the worlds leading authorities  on the topic.

18) If I knew for sure that I could achieve Enlightenment, but only by meditating on a mountaintop for a decade, a further question would arise: is it worth it? Or would I rather spend that decade engaged with the world, with scientific problems and with other people?

BILL: If that enlightenment includes obtaining a proof that P NE NP then sign me up!

19) I, too, vote for political parties, and have sectarian allegiances. But I’m most moved by human creative effort, in science or literature or anything else, that transcends time and place and circumstance and speaks to the eternal.

BILL: I find myself less interested in politics and more interested in math. Non-partisan example: I read many articles about who Trump will pick for his VP. Then he picked one. I then read many articles about who Harris will pick for her VP.Then she picked one. I WISH I HAD SPENT THAT TIME ON THE POLYNOMIAL-HALES-JEWITT THEOREM INSTEAD!

20) As I was writing this post, a bird died by flying straight into the window of my home office. As little sense as it might make from a utilitarian standpoint, I am sad for that bird.

BILL: If we could ,without too much effort, make this not happen in the future,  that would be good. There were some suggestions for that in your blog comments.

P v NP Papers Galore

As someone who has literally written a book on the topic, I have had many people over the years send me their attempts at P v NP proofs. On average, I receive about one a month, but I've had seven in the last two weeks. And not just the usual email with a PDF attachment. A DM in X. A phone call with a baby in the background. Via Linkedin, in Spanish. One with forty-one follow up emails.

P v NP is still the most important problem in theoretical computer science and perhaps all of mathematics, and not that difficult to understand, at least on an intuitive level. I can see the fascination in wanting to solve it, much the way my teenage self dreamed of being the first to prove Fermat's last theorem (damn you Wiles).

But why the spate of "proofs" right now? Maybe it's an artifact of the crazy world we live in.

In one sense, I appreciate the continued interest in this great question, even though these papers rarely (really never) provide new insights into the P v NP problem. Most of my colleagues just ignore these emails, I usually try to respond once, but most authors will come back and I just don't have time for those continued conversations.

These papers come in three categories.

1. Claiming to prove P ≠ NP by arguing that a polynomial-time machine must search a large space of solutions. To truly prove P ≠ NP, one cannot make assumptions about how the machine might work.
2. Giving an algorithm for an NP-complete problem which works on some small test case. I'd usually ask for them to solve SAT competition problems, solve RSA challenge problems or mine themselves some bitcoin. 
3. Giving a new philosophical or physical spin on the P v NP problem and claiming that tells us about whether P = NP. But P v NP is at its heart a mathematical question, and no amount of philosophy or physics will help settle it.

I have a new suggestion for those who think they've settled P v NP: Run your paper through an AI system, preferably a reasoning model, using the prompt "Give me a critical review of this paper". If you can't convince AI, you're not likely to convince me.