A Restless Soul

When I first became a professor I had it all planned out, I would do research, teach and supervise students, get tenure and do more research, teach more courses, and supervise more students for the rest of my life. But once I got tenure, instead of feeling very excited, I felt kind of depressed. I achieved the main goal I put out for myself. Would I really just do the same stuff for the rest of my career?

I even went to a career counselor who gave me a personality test. I'm a classic INTJ, a perfect fit for a scientific researcher. But I just couldn't keep doing the same and tried to mix it up in different ways. I had children, did a sabbatical in Amsterdam, changed jobs multiple times. A colleague called me "a restless soul."

I took service roles in the field, started this blog, wrote survey articles and a popular science book. In my research for a while I kept doing complexity though trying to focus on applying it to other disciplines such as economics. But I found myself often working on problems that few others cared about.

Eventually I became a department chair and a dean, during an incredible transformation in computing as we moved towards the data-driven future we now inhabit. Now that I've returned to the professoriate I lack the excitement and probably the skills to go back to complexity, which has become more of a mathematical field mostly ignoring the changes we've seen in computing.

In an interview for an administrative job I did not get, I gave a vision talk emphasizing growth and impact. Afterwards when I met with the faculty in small groups, one of them, a CS theorist whom I’ve known for decades, looks at me and says “You’ve changed". Yes. And they hadn't. Two responses to the same restlessness, perhaps. Or maybe they were never restless at all.

Guest Post on Why Coding Style is Important

Coding Style Is Important

Does coding style matter? We teach students how to write code and about algorithms. But, do we discuss coding style? Some people may say that style is just personal preference. But, there is undoubtedly good style and bad style, both for prose and for code. Following is a guest post by David Marcus that is a book review of a book that focuses on coding style.

====

This is a review of the book "Professional Pascal: Essays on the Practice of Programming" by Henry Ledgard. This book changed my life: After reading it, I rewrote all my code.

"Professional Pascal" is not about algorithms. It is about writing code. I consider it to be the Strunk & White for programmers.

While programs must be understood by the computer, they must also be understood by people: We need to read the code to determine that the program is correct (testing can only show that it is incorrect, not that it is correct). We need to read the code to maintain/improve/extend/debug/fix it. This applies even if you are the only person who will ever read or use your code. You probably spend more time reading your code than writing it. If you need to do something with code that you wrote long ago, you will be grateful if the style makes it easy to understand.

If you don't use Pascal (or Delphi), don't be put off by the "Pascal" in the title. Almost all of the advice can be applied to any programming language.

I won't try to summarize what Professor Ledgard has written in his book: He explains it much better than I can. But, I will mention a few of the topics that he covers and some things that I found notable.

One of the essays in the book is "The Naming Thicket". Names are important. Variables should be nouns, procedures should be verbs, booleans should be adjectives.

I was once reading some code in a commercial product, and I saw several methods that had a variable named "Ary". I eventually figured out that this was an abbreviation for "Array". Of course, this was a terrible name: "Array" didn't tell me what the contents of the array was, plus the unnecessary abbreviation turned it into a puzzle.

Another time I was reading a method in a commercial product and the method had a two-letter name. It wasn't clear to me what the two letters meant. I eventually guessed that they were the initials of the developer. I confirmed this with another developer who worked on the same team.

Another essay in the book is "Comments: The Reader's Bridge".

Following Professor Ledgard's advice, in my code I put a comment at the beginning of every procedure, function, method, unit, group of constants/types, and every class, but I never put comments mixed in with the code. If I'm tempted to put a comment in the code, I just make it a method name and call the method at that point in the code.

I own a commercial database library that comes with source code. There are some comments in the source, but most of them appear to be there so that they can be extracted into the Help. I know someone who works for the company. I asked them whether the source code that they ship is the same as their internal copy. I thought maybe they strip out some of the comments in the shipped version. Nope. It is the same as their internal version.

Another essay in the book is "Program Layout". To differ slightly from Professor Ledgard, I would say the layout should make the syntax clear (not the semantics). In case you haven't figured it out, the correct indentation for blocks is three spaces (I don't think Professor Ledgard says this, but he indents three spaces in his examples).

Another essay in the book is "A Purist's View of Structured Programming". Only use one-in, one-out control structures. Never exit a method or block in the middle. If you know the code is written to adhere to this rule, it is much easier to understand: You don't have to scan the whole method looking for quit/exit/return statements.

Another essay in the book is "The Persistence of Global Variables". I once had a bug in one of my programs. I spent a lot of time trying to figure out what was wrong. The problem was in a method that called several other methods of the same class, something like

   DoThis( X, Y );
   DoThat( X, Y );

After much confusion, a light bulb went off in my head when I remembered that DoThis was changing the value of the object's fields. The object is global to the method calls because the compiler passes it in, but it isn't explicitly listed in the parameters/arguments of the methods. After that experience, I always include the object when calling a method, e.g.,

   self.DoThis( X, Y );
   self.DoThat( X, Y );

Another essay in the book is "It Worked Right the Third Time". When I write code, I compile it to catch syntax errors (like a spell checker). I then proofread it to make sure that it is correct (just like reading a math proof to check it). (Ideally, I will print the code out, but if the changes are scattered in multiple files, then viewing a diff onscreen works better.) Only then will I try it. The emphasis should be on writing good code. No amount of testing can make poor code good.

This book was published in 1986, and that is when I first read it. So, why am I writing a book review now? I read a lot of code written by people who make their living writing code. And, all of these people would benefit from reading this book.

Professor Ledgard has also written the books "Software Engineering Concepts (Professional Software, Vol 1)" and "Programming Practice (Professional Software, Vol 2)" (both written with John Tauer) . Much of the material in "Professional Pascal" is also in these books. "Professional Pascal" is shorter, so if you are only going to read one of these books, read it. If a book is too long, here is an article: "Coding Guidelines: Finding the Art in the Science: What separates good code from great code?" by Robert Green and Henry Ledgard, ACM Queue, vol. 9, No. 11, 2011-11-02. The link is here

 

 

The Logical Argument

This will be one of a series of posts that I've always wanted to write but I needed to wait until I was no longer an academic administrator.

Logic is critical to proving theorems but it's the wrong way to argue for resources.

When I was such an administrator, faculty would come and argue, generally for more salary, more office space, more hiring in their specialty or less teaching. Since I had many mathematicians and computer scientists, I'd often get these logical arguments. These arguments were typically fitted to generate the conclusion. How? By choosing the right assumptions, or putting in certain facts, or a certain interpretation of the facts. I've never seen a faculty member give a logical argument on why they should be paid less.

I could point out the faulty assumptions or sometime faculty logic but you can never convince someone they are wrong, especially if it means they won't get what they want. So I generally just agree with them, try to to help out if I can but generally say limited resources tie my hands, which usually is true. 

What's the right way to argue? Show why helping you would strengthen the department/college/university, how you don't need that many resources and how you can generate more resources (say through grants). Arguing to grow the pie always wins over arguing for a bigger slice. I was also more receptive for requests that helped students rather than the faculty themselves.

Was the George Foreman Grill The Best Invention of the last 50 Years?

(This post was inspired by  George Foreman, who passed away March 21, 2025, at the age of 76.)

About 10 years ago I asked my class

What is the best invention or tech advance of the last 50 years?

Here are the answers I got NOT ranked.

1) The internet. We can look things up so easily! (see my post on one aspect of this here). Young people reading this blog have no idea what the world was like before the internet. Here is a short story that shows how much has changed.

At MIT in 1982 I saw Anil Nerode give a great talk about Recursive Mathematics: using recursion theory to show that some theorems whose proofs were not effective could not be made effective (e.g., there is a computable 2-coloring of pairs of naturals with no decidable infinite homogeneous set, so the proof of Ramsey theory on \(K_N\) has to be non-effective). The talk got me interested in the topic, so that day I went to the math library (ask your grandparents what a library is) and found the paper journals that had some of the articles he talked about (Journals used to be on paper? See my post here about that.) I then copied the articles on the copy machine (ask your grandparents what a copy machine is) and read them. A few years later Anil Nerode asked me to write a survey of recursive combinatorics for a collection of articles in recursive mathematics. He was one of the editors of a joint America/USSR project (ask your parents what the USSR was) which I was happy to do. The book was delayed when the USSR fell apart (ask your parents about that important historical era), but was eventually published. The survey is 131 pages and is here. The book, Handbook of Recursive Mathematics, is in two volumes. Its available on Amazon Volume 1 and Volume 2. I've also sometimes seen it available for free download though I don't know if it really is or if thats some kind of scam (if your grandparents try to download it warn them that it might be a scam).

2) Advances in medicine. You can have an operation and be home that night (this is partially medical advances and partially the insurance companies forcing you to have short stays). I asked the question pre-COVID. If I asked it again, I may have some people saying vaccines. 

3) VCR/DVD/DVR/Streaming so we have a lot more control over our entertainment (Is this really on a par with medical advances? Yes- you can watch TV of your choice while you recover.)

4) Easy Pass for Toll Booths. The students said that it was always a pain having to bring change to toss into a basket at the toll booth. And sometimes they missed. 

5) The George Foreman Lean Mean Fat-Reducing Grilling Machine. The student really liked using it and said that burgers were tastier and healthier. I asked him if he really thought George Foreman got to be the heavyweight champion of the world (twice!) because of the grill. He didn't know George Foreman had been a boxer, he thought that George Foreman was a pitchman.  Which is true but inomplete. Whether he is a pitchman or a boxer or an ex-boxer, does he really know enough about  healthy eating so that you should  take his advice? Note also that he has a financial incentive to  believe that the grill  produces tasty and healthy food.  See here for a blog post on the illogic of advertising. 

6) The Cell phone. It would be rude to, at a party, go into a corner and read a newspaper. But it is socially acceptable to go into a corner and read the news (or anything else) on your phone. I discussed this, though about laptops, as part of a post here. On the one hand, maybe it was good to be forced to talk to people. On the other hand, I can check my mail without being at home or the office!

7) THE CELL PHONE!!!!!! See Lance's post here.

8) Caller ID. The Cell Phone makes it possible to call anyone, anytime. Caller ID makes it possible to avoid talking to anyone, anytime. Symmetry!

9) ChatGPT was not on the list 10 years ago but might be now. And other AI things will be also.

But for now I ask: What do YOU think were the greatest tech advances of the last 50 years? If you prefer thinking on a full stomach then grill some burgers and eat them before answering. 

BILL to LANCE: Anything you want to add?

LANCE:

9) GPS - First launched in 1978 and now you never get lost, even at sea.

BILL: Some people trust their GPS to much, see here, though I think these stories happen less and less over time. 

10) CNN - Watching wars play out in real time was a game changer.

 BILL comment on CNN: In 1991 I was on a cruise. In the time I was gone there was an attempted coup against Gorbachev. I didn't hear anything about it until the cruise was over. CNN existed but it was not-a-thing to have it wherever you go. The next time I went on a cruise was 2022. While on that cruise, Gorbachev died and I heard about it right away. Two points here:(a) How fast we got news anytime-anywhere has changed a lot, and (b) For the sake of the Gorbachev family I should stop going on cruises. 

11) Cloud Computing - Enabled small startups to do big things.

BILL Sometimes very small, like one person. New word: Solopreneur

The Phone

I've heard this story from a few places. A father watches Back to the Future II with his kid. The 1989 movie view of 2015 looks entirely different when in fact not much has changed except for the fashion and the lack of mobile phones. This is supposed to be a parable about the lack of technological progress.

I disagree. It's about a lack of imagination of the future because of those phones. Phones that are hidden from sight, and have become so ubiquitous we take them for granted.

The phone in your pocket is more powerful than the most powerful computer of 1985 and it's not even close. But that's the least interesting thing about the phone.

You no longer need a printed newspaper, encyclopedia, atlas, almanac, dictionary, thesaurus, dining guides, programming manual or any other reference book. The printed sports almanac at the center of the plot of the movie doesn't exist anymore. 

You can read virtually any book ever published, listen to any song ever recorded, watch any movie ever filmed. You have access to nearly all publicly available information. You can watch major sporting events live. On that phone.

You can buy tickets to any event and save and use them on your phone. You can pay for just about anything with your phone, and if you wish ship it anywhere.

You no longer have to fold a map or ask for directions. The phone will give you directions, taking account traffic and transit delays, and guide you along the way.

When visiting a foreign country you can point your phone at a sign in Japanese and have the words magically replaced by English. Take a picture of a menu in German and have it describe the dishes in English. Instantly translate voice as well.

You can have a conversation with your phone about anything. It will understand your voice and respond likewise. 

You can take photos and videos on your phone and share them instantly with your friends or with everyone around the world. The quality is far superior to any consumer-level camera from 1985. Or you can have the phone create its own photos and videos based on your descriptions. 

It's also, of course, a phone. You can speak to anyone anywhere, with video if desired, for zero marginal cost. Back in 1985 it cost about a dollar a minute to call someone in a different state, and much more internationally, on a landline. You can have impromptu video meetings and you can send messages to anyone and share them with everyone. 

And I'm just scratching the surface. 

So between the phone and the flying hoverboards, I'll take the phone any day.

A few more notes about Tom L

Tom Lehrer passed away on July 26, 2025, at the age of 97. I wrote a blog-obit here. One of my readers read the post and went down a rabbit hole (or did he?), which lead to a blog post about rabbit holes here. 

A few more notes about Tom L.

1) When someone of interest to our readers dies, Lance calls me (he seems to always know before I do) to discuss who should do the obit (me, him, someone else, or perhaps no obit needed). This was a case where there was no need for a discussion.  To say I am a fan of novelty songs would be an understatement---I've been a fan of novelty songs before I was a fan of mathematics. A link to my website of novelty songs by topic, including Math, is here

2) Whenever Lance calls I answer with Who Died? 

3) Who was the oldest novelty song singer to die in the Summer of 2025? The summer is not over yet but I think the answer is known. And it's NOT Tom L!

Jane Morgan, a singer, died on August 4, 2025, at the age of 101.  She recorded a parody of  Johnny Cash's A Boy Named Sue titled A Girl Named Johnny Cash 

A boy named sue:  here

A girl named Johnny Cash: here

Wikipedia Page for Jane Morgan: here

To my knowledge, Jane Morgan only had one novelty song  (she had many non-novelty songs) so calling her a novelty singer is a stretch, but its a great song, so I will call her a novelty singer.  (I checked if the flipside of that song was a novely song. It was Charley, a love song, not a novelty song. Ask your grandparents what a flipside is.) 

4) Tom Lehrer and Jim Lehrer (news anchor on PBS, deceased) are not related.

I googled how many people have last name Lehrer

Google-AI:  FamilySearch.org estimates there are 211,503 records for the surname.

But this website says approximately 5982 bear this surname.

I'm surprised by the large gap there.

5) There have been more elements found since Tom L did The Elements. I wondered whether someone updated it. Of course they did:

The Original by Tom L: here

Updated version by Leonard  Lehrman that has the latest element, Number 118, Oganesson: here

I've heard that 118 is natural barrier- we probably won't create 119 or higher. Elements that high are created, not discovered. They also don't last long. 

6) There are many elements, so a list-song made sense. There are a lot of complexity classes, so a list-song makes sense for those as well. 

Dave Barrington sings Song of the Complexity Classes: here

7) How many people emailed me to tell me that Tom L passed away? R(5).

8) One of my favorite and less known Tom L songs, whose advice he did not take: Selling Out

9) Tom L wrote a paper with R.E. Fagen (Not Ronald Fagin) for the NSA. It's a real math paper, but note the third reference in the bibliography, the paper is here.

Total Pixel Space

Last month the New York Times highlighted some AI generated short movies, including Total Pixel Space, by Jacob Adler that gets philosophical about information, à la infinite monkeys. It imagines the finite number of images and video that contain all human history, both real and fake, along with all possible creatures, and even the rise and fall of alien civilizations.

Let's talk about the math. According to the video there are roughly 7.8 x 10^7,575,667 possible 1024x1024 images, and 9.3 x 10^{1,309,075,411,322} possible two hour films, incomprehensibly large numbers. The narrator acknowledges that most of the images are random noise.

But within this ocean of pixel possibility, natural images are but a drop. Recognizable scenes, faces and objects are extremely rare islands in a vast sea of noise.

So how do we capture which images actually matter? Let's visit our friend Kolmogorov Complexity, which measures information by the amount we can compress. A JPEG image typically compresses (lossily) to about 200 KB, which reduces the number of images to 8.7 x 10^1,061,650. Still enormous.

All the images and videos were generated by short prompts. JPEG compression reduces raw pixel space by discarding details our eyes don’t notice. Prompts do something similar at a higher level: they compress ideas, not pixels.

Consider prompts of length 100 over a 10,000 word alphabet typically used in prompting and we're down to 10⁴⁰⁰ possibilities, a mere quintic of the number of atoms in the universe. And you could cut that down by considering grammatical structure.

Now from a prompt you won't get the same image each time, based on the randomness of machine learning. But that's the whole power of AI, the randomness just gives us examples of the structure embedded in the prompt. It's the structure that matters.

And perhaps those monkeys would be more efficient if they entered prompts into AI, instead of generating random text. What images they could produce!

My Tom L post inspired a mathematical definition of Rabbithole

NICK: I read and enjoyed your blog post on Tom L (see here). I then spent 40 minutes down a rabbithole listening to his music on YouTube.

BILL: You call that a rabbit hole?!  A while back I spent 3 hours reading questions and answers on quora ranging from is Michelle Obama actually a man? to Is Donald Trump the Anti-Christ? (The answer to both is no.) THATS a rabbithole. Listening to Tom L is not.

NICK: SO... what is and isn't a rabbit hole? Also, is it rabbithole or rabbit hole?

BILL: Spellcheck is happy with rabbithole, hence so am I. As to your question,  we need a function \(f\) and a threshold \(T\) such that

if you spend \(x\) minutes on A, and 

you get y enjoyment out of it, where \(0\le y\le 10\), and

 \(f(x,y)\ge T\)  

then A is a  rabbithole.

(Note- I was kidding. There can't possibly be a function f that works.)

ONE DAY LATER

NICK: I asked Gemini  what \(f\) and \(T\) are  and it told me:

 \(f(x,y) = \frac{x}{y+1} \) and  

\(T=20\).

  It also gave me some examples:

1) The Tom L. Example: 40 mins, 8/10 enjoyment. Score 4.44. NOT a Rabbit Hole!

2) Doomscrolling: 90 mins, 1/10 enjoyment. Score  45. Rabbit Hole!

3) Binge-Watching Mediocre TV: 3 hours (180 mins), 4/10 enjoyment. Score = 36. Rabbit Hole!

4) Incredible Documentary: 3 hours (180 mins), 9/10 enjoyment.  18. Worthwhile but its close.

Gemini also output a heatmap, see here.

BILL: Uh- I was only kidding.

NICK: Well, the jokes on you. 

AI and ...

AI and Vacation

I'm back from my German vacation. This was my first AI vacation, by which I mean how I used AI to navigate a foreign country. Taking a picture of a hand-written menu board, not just to translate the dishes, but to get a description of each. Visiting a palace with a German-speaking tour guide and translating in real time. Even the more mundane taking pictures of buildings to learn about them.

On the TV I saw something about Künstliche Intelligenz, and Chatty told me it was German for Artificial Intelligence. The Germans use KI instead of AI partly because AI can be confused with Ei (egg). At least that's what AI tells me, so it must be true.

AI and Math

At the beginning of my vacation, Google announced that they achieved gold medal status in the International Mathematical Olympiad. An impressive achievement though Terry Tao makes a good point that comparing an AI system to a time-constrained high-school students is not an apples-to-apples comparison.

I already find talking to AI about math topics quite useful, though it's like talking to an early PhD student. Sometimes they just say things that aren't correct, but usually they are. The reasoning models are particularly good at finding holes in P v NP proofs. For example here's the conclusion of ChatGPT o3-pro's review of the paper from Eric's guest post.

The paper is a reminder that lower‑bound proofs live or die on the exact breadth of the algorithmic model they exclude—too narrow and the result is unsurprising, too broad and the proof tends to break. At present this work sits in the first category.

What I want to see is AI come up with a solution to an open math problem, a true new insight beyond just some optimized search. I'm not looking for P ≠ NP, just some result that would be publishable in a respectable conference or journal, even just a new completeness result. We haven't really seen that yet, but I suspect we will soon and then we can figure out where math goes from there.

AI and Bill

In his presidents question and solution, Bill states that AI had failed to find the right answer to his problem. Back in June, I saw Bill's draft post and tried AI to solve it.

AI initially failed the test but for a good reason. Bill's initial draft post had Ford and Dole in Group Two because they received LLBs instead of JDs. In the past the LLB was the professional law degree. Yale didn't change to JD until 1971. Ford got his LLB from Yale in 1941.

When I removed Ford and Dole, ChatGPT o3-pro correctly gave the reason for the partition, though it did take over 13 minutes.

Every name in Group One spent time in a law school—most completed a J.D. or LL.B., and the two exceptions (Al Gore and, in some accounts, Lloyd Bentsen) still enrolled in law studies.

• examples – Walter Mondale (University of Minnesota Law) en.wikipedia.org,
  JD Vance (Yale Law) en.wikipedia.org,
  Al Gore (attended Vanderbilt Law) en.wikipedia.org.

No one in Group Two ever attended a law school; their highest formal education is in fields such as engineering (Jimmy Carter), economics (George H. W. Bush), business (Donald Trump), political science (Paul Ryan), or acting (Ronald Reagan) en.wikipedia.orgen.wikipedia.org.

So the distinguishing property is legal education: every Group One figure went to law school, while none in Group Two did.

Another commentor got a similar result for ChatGPT o4-mini-high. I just tried it on Gemini 2.5-Pro and it also gave the correct response, this time in seconds.

On the other hand, E tried several base models and none of them succeeded. The lesson: You want to solve a tricky problem, pony up the $20/month and use a reasoning model.

Some thoughts on journals, refereeing, and the P vs NP problem

A guest post by Eric Allender prompted by an (incorrect) P ≠ NP proof recently published in Springer Nature's Frontiers of Computer Science.

For a time, I served as Editor-in-Chief of ACM Transactions on Computation Theory, and in this role I had to deal regularly with submissions that claimed to resolve the P vs NP problem. Finding referees for these papers was sometimes challenging, so I frequently ended up reviewing them myself.  Dealing with such submissions involves enough overhead that ToCT, J.ACM and ACM Transactions on Algorithms limit the frequency with which authors can submit work of this sort.  But for every submission, on any topic, the overall process was the same: Find someone on the Editorial Board who has sufficient expertise to find referees and make knowledgeable use of their recommendations.  If there was no such person on the Editorial Board, then it was always the case that the submission was out of scope for the journal.

These thoughts are brought to mind by a recent case, where it seems to me that the editorial process broke down.

Springer publishes several high-quality academic journals that deal with Theoretical Computer Science.  One Springer journal, Frontiers of Computer Science, recently published an article entitled SAT Requires Exhaustive Search, where one of the authors is a Deputy Editor-in-Chief of the journal.  The abstract of the article states that it proves a result that is stronger than P not equal to NP.  The Editorial Board of the journal has some members who are expert in computational complexity theory.  However, all the ones whom I know personally have asserted that they had no knowledge of this paper, and that they were not involved at all in handling the paper.

When Ryan Williams and I learned about the publication of this article, we drafted a comment, which we sent to the Editor-in-Chief.  We recommended that the paper be retracted, in which case there would be no need to publish our comment.  However, the Editor-in-Chief declined to retract the article, saying that he could find no evidence of misconduct, and thus we have been assured that an edited version of our comment will appear in the journal.

Our comment calls attention to some shortcomings in the proof of the main theorem (similar to shortcomings in several other failed attempts to separate P from NP).  But we were able to say more.  Often, when one is looking for bugs in a purported proof, one has to deal with the situation where the claimed theorem is probably true, and the only problem is that the proof is not convincing.  However, the main theorem in their paper (Theorem 3.2) states that a particular constraint satisfaction problem requires time more than \(d^{cn}\) for any constant \(c<1\) (where \(d\) is the domain size, and \(n\) is the number of variables).  In particular, their purported proof claims that this holds even when \(k=2\) (meaning that each constraint has at most 2 variables).  However, Ryan Williams presented an algorithm more than two decades ago that runs in time \(O(d^{(0.8)n})\) in this special case, contradicting the lower bound claimed in the article.

The article contains an appendix, with glowing testimonies from various researchers; the lead-in to the appendix also contains enthusiastic comments from Gregory Chaitin.  I contacted Gregory Chaitin, and he asserts that he did not read the paper, and that he was quoted out of context.

The edited version of the comment that Ryan Williams and I wrote, which will supposedly appear in Frontiers of Computer Science soon, differs from the version linked here (our original submission) primarily in one respect:  Our closing paragraph was removed.  Here is that paragraph:

Finally, it is our opinion that the publication of this article is a complete embarrassment to this journal and its publisher. We believe that, at the very least, the paper should be withdrawn, and Springer should conduct an investigation to understand how such a paper could have made it through the peer review process.

Update (Lance, 8/5/25): The authors of the paper in question have asked me to link to their reply to the Allender-Williams comment. I do so with no endorsement. 

Eric Allender asked me to note that their claim about Ryan’s algorithm requiring exponential space is misleading; the amount of space is not more than the runtime of the algorithm, which is less than the lower bound that they claim. (Their theorem does not state that \(d^{cn}\) time is required under the additional assumption that the algorithm use only \(n^{O(1)}\) space.)

Tom Lehrer Passed Away at the Age of 97

Tom Lehrer passed away on Saturday July 26 at the age of 97. (For other obits see this collection of ten obits here.)

He worked in both of my fields of interest: Parody Songs and Mathematics. 

1)  He got a BA in Mathematics from Harvard, magna cum laude, in 1946. (Spell check thinks magna  and laude are not words). 

2) While he was an undergraduate he wrote and performed the song Fight Fiercely Harvard which was a gentle football fight song. IDEA: Use the melody to write a song about Harvard's current fight with the Trump Administration.

3) He wrote some political songs. Some were performed by Nancy Ames on the British satirical Show That was the week That Was. Tom L didn't like that probably because they cut some of the more controversial lyrics. He later wrote and performed songs for another political satire show, The Frost Report. Here are some of his political songs and comments on them:

 Who's Next -- about which countries have or will have nuclear weapons. IDEA: Update it.

Vatican Rag--About the Catholic Church- controversial then, rather tame now. If you heard it now you won't understand why it was ever controversial. Such is the nature of biting satire. I noticed this in my blog-obit for Tommy Smothers  here.  As such, I view old political novelty songs as entertaining history. 

4) He went to graduate school for Math at Harvard. He worked on it on-and-off and had other jobs but left Harvard in 1965 (see his Wikipedia entry here for the full story).

5) One of the things he was doing while he was at Harvard was compose, sing, and record songs. Here are the some of particular interest to my readers:

New Math - -I was actually a victim or beneficiary of the new math. 

Lobachevsky-- Historically inaccurate but funny.

The Elements-- This might be Tom L's best known song. It's to the tune of  I am the very model of a  Modern Major General; however, some of the songs that use that Tune seem to be parodies of The Elements. I have a website of parodies of Modern Major General here. Unfortunately the song that is most clearly a parody of  The Elements, Dr Jane's The Muscles of the Kitty Cat, seems to have disappeared from YouTube. It is not on Spotify. (Spellcheck thinks that YouTube is a word but that Spotify is not a word.) I can't find it anywhere on the web. I DO have it on CD.

 The Decimal Song--About using base 10. This was on The Frost Report. Not on any album so you might not know this one, though it is on YouTube.

 That's Mathematics--Originally written to be the theme song for a PBS math show now titled Square One Television. They did not use it. He later added a lyric about Andrew Wiles. Square One Television often features math songs. Here are my favorites: The Mathematics of Love,  8% of my love,That's Combinatorics, Polka Patterns (by Weird Al).

 That's Mathematics sung by Mathematicians-- A nice tribute to him. It was done a few years ago. Tom L knew about it and was delighted. 

Derivative song (indexed to where it is within a longer segment)

 6) A few years ago Tom L put his songs in the public domain, see here. That website also includes lyrics for songs that were never recorded. IDEA: Record them! ADED LATER- a few have been recorded, though by other people. I found a website of that has lots of science novelty songs including some by him here. Much of it is not available on any record and not even on YouTube.

7) Tom L claims to have invented Jello Shots as a way to get around alcohol-free requirements. The Great Luke Ski wrote a song about Tom L in the style of Tom L. It's not on YouTube but it is at FUMP (FUnny Music project) here (click on play on second song) 

8)  His singing career was fairly short. Three albums, a few tours, a few other songs. Weird Al has 14 albums. Alan Sherman has 10 albums (Alan Sherman was born four years earlier than Tom L but died in 1973). However, the percent of great song on Tom L's albums is around 90%, whereas for Weird Al and Alan Sherman it's around 60% (this is just my opinion).  Also, Tom L had a day job. He has said he never really retired from singing, he wrote when he felt like it, and over time didn't feel like it. For what he said about retiring from singing, see his Wikipedia page here.

9)  There are two  stories about Tom L I bring up - one seems to be TRUE though I thought it was FALSE, and the other IS FALSE.

a) He stopped political satire because:

Political satire became obsolete when Henry Kissinger won the Nobel Peace Prize. 

I have the following (possibly false) memory: 

Tom L has denied this and points out that he had pretty much stopped many years earlier. And I'll point out that he wrote non-political novelty songs as well (that is Tom L did, not Henry K). 

BUT- Wikipedia and other sources say that it's true. Who am to  disagree with the Google Gods?

b) He was sued by Wernher von Braun's family for his song about Wernher. This is false and the web says that it is false. Tom L denied it in a 2003 interview. I have a (possibly false) memory of reading that he wished it was true because it would mean people are still listening to his music. 

9) On Jan 1, 2025 he became one of the rare people who:

-- Lived during two square years (1936 and 2025).

-- Was of age and mental ability to appreciate that they had done this

I had a blog on people who lived through two square years here.

10) I end with what might have been his last song

 I'm spending Hanukkah in Santa Monica 

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?

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

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 comments pointed out that I a wrong. See the comments 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

UT Austin: Anna Hiss Gym. 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.