THE DEFINITION OF RARE

(Guest Blog by Bill Gasarch has has a large collection 
of novelty songs, mostly funny songs.)

I) There was a satire on Saturday Night Life called
CONSPIRACY THEORY ROCK (which was in the style of
SCHOOLHOUSE ROCK) that was brilliant, and only aired
once.  (Too controversial, though this posting is not
about that.) I have this video clip in my collection,
and it was one of the rarest things in it.

NOW this clip is on YOU-TUBE!  Hence I can no longer
claim it is `rare'.  But the YOU-TUBE clip says
``rare video footage''

HOW RARE CAN A VIDEO CLIP BE IF
ANYONE IN THE WORLD CAN ACCESS IT !?

II) With the ability to make perfect copies of CD's,
and MP3's its hard to say what it means to have a
`rare recording'.  If you have the original Vinyl
record or reel-to-reel tapes, that may be rare, but
I'd RATHER have the version put on CD or MP3.

III) Some paintings sell for gobs of money.  Do we have
the tech to reproduce those exactly (in 3D)? I suspect
no, but one day we will (holographs?).  When that day
comes, will the prices drop?  Maybe not- its already
an artificial market; `originals' may still be valuable.

IV) What music or video or TV shows or whatever bring
produced now will be considered `rare' in the future?
Note that even really bad TV shows and movies are on DVD.
Some really bad movies even have `directors cuts'.

V) So, what is the rarest thing in my collection now?
In 1976 I audio taped off of TV a satire- a Chrismas
song as if done by Bob Dylan.  I did not know who did
it.  I still don't.  I have not found it anywhere else.
It does not seem to be on vinyl, audio, CD, or MP3.
Since I have the largest Bob Dylan Satire Collection
in the world, (www.cs.umd.edu/~gasarch/dylan/dylan.html)
and this is known by that community (How large is that
community? Larger than the Gen Multidim Poly VDW
community) the fact that I can't find it, and nobody
has emailed me about it, means ... its rare! However,
I would rather FIND it on CD or some other medium and
know who did it than preserve its rarity.

Tom Lehrer turns 9*9 today!

Today (April 9) Tom Lehrer turns 81=9². To celebrate I post some lesser known Tom L songs. I post all that did not appear on any of his CD's. Note that The remains of Tom Lehrer, his 3-CD boxed set, already had several songs that had not appeared on any of his prior available work. (I got it from Agnes, Thats Math (short version- long version is on Dr. Demento Basement tapes No. 4), Selling Out, I've spending Hannakuh in Santa Monica, L-Y, Silent E, O-U, S-N. L-Y and Silent E had appeared as extras on CD versions of his Vinyl records.) Hence to NOT even appear on the boxed-set makes it rather rare. Or is it? Its on You-Tube so how rare can it be? (I discussed this in an earlier blog here.)

Derivative Song. Likely did not appear on any CD because the audience for this is too small. Also might have been copyright problems as he used someone elses tune (See comment on THE PROFESSORS SONG later in this post.)

Decimal. GREAT song. Likely did not appear since its a bit dated and the context is now lost. The best of the rare songs. To the tune of his own New Math

The professor's song. GREAT song. Don't know why it's not in the boxed set--- no copyright problems since he used a Gilbert and Sullivan Tune which is public domain (Tom L always used his own tunes to avoid legal issues. The only exceptions are this song and The Elements which also used a Gilbert and Sullivan Tune.)



Subway Song. Not that good. However, note that 90% of Tom L's stuff is excellent. Weird Al has generated many more novelty songs, but only 50% are excellent. So who is better? It depends on how you measure. I, of course, like both of them. Incidentally, Weird Al did one math song for Square One TV: Polka Patterns. At one time that was a rare item in my collection. But now Its on you-tube so how rare can it be? @

The (il)logic of fandom

(UMCP is having an REU (Research Experience for Undergradutes) this summer on Combinatorial Algorithms Applied Research. If you are an ugrad, go to that site and see if you want to apply. If you are a faculty see if you want to recommend it to some students. Deadline to apply is Feb 15.)

The Sunday before the Superbowl I spotted this curious passage in THE WASHINGTON POST which I paraphrase.

Washington Redskins fans should root for the Baltimore Ravens in the Superbowl because the two teams share many fine qualities. Both have gritty defense, soft-spoken by shrewd head coaches, underrated quarterbacks craving validation on the big stage. Neither team is flashy or has big starts--- rather they are both greater than the sum of their parts.

I interpret this as assuming Sports fans pick who to root for in a logical manner. Something like I like quality X, this team has quality X, so I will root for them. Is that how sports fans act. If it was then sports fans would change who they root for often. They do not.

So what is the logic behind fandom? Why do people root for certain teams, likely for a lifetime. Is it rational?

1. Root root root for the home team, for it they don't win its a shame. Root for the team in the place you live NOW.
   
2. Root for your childhood team. I wonder if the Chicago Cubs has more fans across the country since one of the early cable channels WGN, is from Chicago and (I think) carries Cubs games--- so you can be a transplanted Chicagoan and still watch your team. As people move around alot loyalty to your home team may fade.
   
3. For College teams its common to root for the team that comes from the college you went to. This is less true for graduate school.
   
4. Fair weather fans root for the team that's winning. But it is more common to have a team (perhaps your home team) that you ignore unless they are winning. So you don't choose your team based on this, but you choose weather to care based on this.
   
5. The early NY Mets (early 1960's) were a terrible team but they had lots of fans. There was a loser-chic factor. The Chicago Cubs have also had that. This is rare or even nonexistent now. Everyone loves a winner.
   
6. Individual players may appeal to you. Tim Teabow got some attention because of his devout Christianity. But this is rare. Its more common to get attention for negative behavior. This is more a matter of rooting for a person rather than the team.
   
7. A while back some teams delayed getting any black players on them so they would still appeal to racist fans. This stopped once such teams just lost too much since they were not using that talent pool. Might someone root for or against a team because of the attitude or politics of the management? If some team took the profits and funded alternative energy for real would you root for them? What if they funded Ramsey Theory? What if they supported Same Sex marriage? I doubt a team would have a public opinion on an issue which may cause them to lose fans, though a player might.
   
8. A friend of yours is ON the team so you root for the team and your friend. This is rare. But if someone on the team is from your SCHOOL- you may have a certain affinity for that person and team even if you don't know them. Whenever I hear that some pro football player is from Harvard (where I went to graduate school) I at least notice this. Its rare.
   
9. In the Olympics one usually roots for their own country. What if (say) American offered the top Tennis player in the world (who was not an American) to become a citizen of the USA (and pay him for it) then he won the Gold Medal for American. (I think this is legal.) Would Americans be proud of that or feel that's not quite right? I suspect that this kind of thing will happen more often over time. While this may seem strange it already happens within a country. The NY Mets do not have more players from NY. Nor do the Baltimore Ravens have more players from Baltimore.
   
10. Jerry Seinfeld once commented that we LOVE this player if he's on OUR team but HATE him if he is on another team. What has changed? His uniform. So we are rooting for clothing.
    

Is there a logic to who a fan roots for or not? Is there a logic to being a sports fan?

Rules and Exceptions

As a mathematician nothing grates me more than the expression "The exception that proves the rule". Either we bake the exception into the rule (all primes are odd except two) or the exception in fact disproves the rule.

According to Wikipedia, "the exception that proves the rule" has a legitimate meaning, a sign that says "No parking 3-6 PM" suggests that parking is allowed at other times. Usually though I'm seeing the expression used when one tries to make a point and wants to dismiss evidence to the contrary. The argument says that if exceptions are rare that gives even more evidence that the rule is true. As in yesterday's New York Times

The illegal annexation of Crimea by Russian in 2014 might seem to prove us wrong. But the seizure of Crimea is the exception that proves the rule, precisely because of how rare conquests are today.

Another example might be the cold wave of 2014 which some say support the hypothesis of global warming because such cold waves are so rare these days.

How about the death of Joshua Brown, when his Tesla on autopilot crashed into a truck. Does this give evidence that self-driving cars are unsafe, or in fact they are quite safe because such deaths are quite rare? That's the main issue I have with "the exception that proves the rule", it allows two people to take the same fact to draw distinctly opposite conclusions.

The Betty White Award for 2023: Tommy Smothers

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

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

Past Winners:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

So I am puzzled that they were cancelled. 

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

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

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

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

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

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

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

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

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

 

 

Captain Einstein

If the president of the United States uses "complexity" in a tweet, I can't leave it alone.

Airplanes are becoming far too complex to fly. Pilots are no longer needed, but rather computer scientists from MIT. I see it all the time in many products. Always seeking to go one unnecessary step further, when often old and simpler is far better. Split second decisions are....

— Donald J. Trump (@realDonaldTrump) March 12, 2019

....needed, and the complexity creates danger. All of this for great cost yet very little gain. I don’t know about you, but I don’t want Albert Einstein to be my pilot. I want great flying professionals that are allowed to easily and quickly take control of a plane!

— Donald J. Trump (@realDonaldTrump) March 12, 2019

I got my MIT degree in Applied Mathematics so I don't count, but I know plenty of MIT computer scientists and the one undeniable truth is that I don't want any of them flying my plane.

I also agree with the Donald that a complex environment can often lead to confusion, especially in an emergency. HCI matters.

But that's where it stops. Better technology in the plane and on the ground, combined with better procedures have all but eliminated deadly major commercial airplane crashes in the US and quite rare in the world at large. I'll call that more than a "little gain". I remember the "old and simpler" days where we had deadly airline crashes every few months. No thanks.

I've had great discussions with some of the aerospace engineering professors at Georgia Tech. The amount of effort to get the "front-of-the-plane" software right via formal methods and rigorous testings has become harder to engineer than the plane itself. The "back-of-the-plane" software that controls the video screens and WiFi gets less attention. I can live with safety over movies.

When technology makes things much safer, whether it be planes or self-driving cars, the rare accidents become far more noticeable. while we should use these opportunities to learn and make things safer, the rare accidents help us realize just how much more safer technology can make us.

Regan Lipton celebrates my 1000th blog post and random thoughts this inspires

Ken Regan emailed me recently asking if our software could tell how many blogs I had done (not how many Lance+Bill had done). We didn't know how to do that but he managed it anyway. Apparently he was more interested in this question than either Lance or I was. 

But the answer was interesting: My1000th post of Complexityblog was about Betty White dying at just the wrong time to be in those those we say goodbye to articles that appear CLOSE to the end of the year. (I don't know why, but I think the fact that my 1000th post was on Betty White is just awesome!) The post is here. He was asking this because he thought (correctly) that I was around 1000 and wanted to do a tribute blog to me (actually it was done by Lipton and Regan- more on that later). And indeed they did do the post, its here.

RANDOM THOUGHT ONE

While preparing it Ken asked me about my papers.  This brings up the more general question: When looking at your old work what do you think? Common reactions are

1) Gee, I was smarter then. That was very clever. OH, now I remember, my co-author did it. 

2) Gee, I was dumber then. I could do that argument so much better now. 

3) Why did I care about Muffins so much to write a book about it? (Replace Muffins with whatever you worked on and book with the venue it appeared in.) 

Item 3 is probably the most common: As a graduate student one works on things without really have a vision of the field (though the advisor can mitigate this) so what you work on may seem odd later on. And ones tastes can change as well. 

RANDOM THOUGHT TWO

Ken and Dick write actual posts together. I find that amazing! By contrast, the extent of Lance and my interactions about the blog are: 

a) Someone died. Which of us should do the blog obit? or get a guest blogger.?(Whenever Lance phones me on the telephone I answer who died and usually someone did.) 

b) Which of us does the April Fools Day post this year (we usually alternate, or do we)?

c) I plan on doing 2 posts close together- a question and an answer, so when do you NOT plan on blogging so I can do that.

d) Someone proved X. Which of us should blog? Or should we get a guest blogger?

e) Establish a general rule for the year like Bill will post Sunday's, Lance Thursdays.

f) I ask Lance for technical help on the blog. How do you get rid of the white background when I cut and paste?

g) Sometimes one of us wants commentary on a blog we are working no- but that is rare. Though I asked Lance for this post and he added a few things to this list.

h) Sometimes I look at one of his posts before it goes out and offer commentary, or vice versa. Also rare.

i) Lance writes the end of year posts, but always with my input. We jointly choose the theorem of the year.

j) The very rare joint posts.

k) If we happen to be in the same place at the same time, like Dagsthul, we'll do a typecast capturing our conversations. In the past we've also had podcasts and vidcasts together.

Math, AI, and the Navier-Stokes Equations

On September 1, 2026:

LANCE:  I'm surprised you haven't blogged about OpenAI solving 10 open math problems.

BILL: If I post every time an open math problem is solved by AI I won't ever post about anything else.

I'll wait until AI does something really impressive.

LANCE: How impressive does the theorem have to be?

BILL: I'll post about AI doing math once AI solves a Millennium Prize Problem.

LANCE: That might not be for a while.

BILL: Agreed.

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

On September 8, OpenAI announced it had solved the Millennium Prize Problem on the Navier-Stokes equations. 

On September 9, Lance blogged about the result, see here.

So here, at last, is my long-awaited post on math and AI.

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

In my May 24, 2026 blog post about the Erdős Unit Distance problem being resolved by OpenAI ,  see here. I suggested two possible futures:

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

ONE: While this AI-generated (or AI-assisted) result is impressive, it will be a rare occurrence. This result was actually a counterexample. The needed math was known. The result was interesting. This is a perfect storm that we might not see again for a while.

TWO: Even before the AI revolution, when I came up with a math problem I wanted solved, I would seek help, perhaps too early. My curiosity far exceeds my ego.  Since AI makes it easy to get help, my fear is that eventually we will all be Bill Gasarch---scary.

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

Option ONE did not age well.

1) Rare occurrence? In August 2026, OpenAI solved ten math problems; see here. 

2) Only counterexamples?  The distinction between proving a conjecture and finding a counterexample may be an illusion. Even the disproof of the Erdos Distance Conjecture had to find an infinite number of counterexamples, which is close to a for-all statement.

3) The needed math was known?  To say that AI will only solve problems where the needed math is known seems odd. I suspect 99% of all theorems use math that is already known.

4) The result was interesting? All ten math problems OpenAI solved do all seem interesting.  Or, more rigorously, there exists N large (maybe around 100) such that, for all P, where P is one of the ten problems, there exists at least N people who care about P.

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

Other Points

1) On Aug 12 Terry Tao posted here  about Sendov's conjecture: Let \(n\ge 2\) and let \(p \colon C \rightarrow C \) be a degree \(n\) polynomial with zeros in the unit disk. Then for every zero a of \(p\), there exists a critical point \(\zeta\) with \( |\zeta - a | \le 1\)

a) The conjecture for \(n\le 8\) was known.

b) Terry Tao had shown that the conjecture was true for large \(n\).  No lower bound on \(n\) was known.

c) Lech Mazur was able to use an AI tool to resolve the conjecture. See here

d) The post by Terry Tao was a digestion of the proof.

Digestion is just the right term. I nominate it for word of the year for 2026.

2) This may be the future: AI assists us but we still need to digest the proofs.

3) Will we bother with the digestion? Or will we be like students who use ChatGPT to do the homework and then do not read it carefully enough to learn anything from it?

Perhaps future papers will be in two parts: the proof, and the proof that the author actually read the proof.

4) Might we all become embodiments of the Chinese Room? We ask AI a math question, it supplies the proof, and we rewrite the proof without really understanding it.

5) I hope we will all be Terry Tao: digest the proofs and maintain understanding.

6) The four color theorem: the basic idea was human-understandable, but a program was needed to check an enormous number of cases (even in the later proof).  Question: Are there any results where all we have is that a program said it was true and we lack the basic idea? Of course, many proofs in math were done by humans, but I do not understand the basic idea.

That is, has this SMBC cartoon happened yet: see here  

7) Riemann: I quote Wikipedia (see here)

In August 2026, an unreleased research version of the Anthropic's large language model Claude working interactively with human researchers, proved unconditionally that at least two-thirds (66.6%) of the non-trivial zeros of the Riemann zeta function lie on the critical line.[44] Using an optimized test family, this bound has been improved to

\(\frac{3}{2} - \frac{1}{\sqrt{2}}\cot(\frac{1}{\sqrt{2}})\sim 67.25\%\).

Is this progress towards a solution?  Is RH going to be solved soon? 

8) The Navier-Stokes equation problem. Very roughly, the question asks if a certain class of equations always has a smooth solution. OpenAI has announced that they found a counterexample. There are some issues with this. Here is a quote from the Wikipedia entry on the NS equations (see here)

The announcement [by OpenAI] was accompanied by a priority dispute with Levent Alpoge (employed at a rival AI company Anthropic) and Tristan Buckmaster, who derived a set of closely related results on the Euler equations. The method used to generate the claimed solution built upon a method developed by Diego Corboda and Luis Martinez Zoroa in 2023 to prove blowup phenomena in related fluid equations.

(ChatGPT wanted me to say Is the result AI-assisted or AI-generated rather than assert that it is AI-assisted.)

9) Could Alpoge and Buckmaster have solved the problem?

(The name Alpoge looked familiar to me so I searched the blog to see if I had mentioned him before. I had! He was the first person to prove that the primes are infinite using Ramsey theory. See that post here.)

10) Will people be scared to use AI when they are beginning to work on a proof for fear that AI will scoop them?

11) OpenAI has said it will not try to collect the money. This is the SECOND Millennium Prize Problem where the solver turned down the money, though for different reasons. I do wonder what will happen the next time AI solves a problem worth money---who gets the money?  Perhaps the prize should go to whoever can explain the proof to the prize committee.

12) Shortly after the story broke Terry Tao had a blog post on it. He later had some guest posts about Math and AI. I was going to point to Terry Tao's posts and guest posts, but you can all use Google to find those posts, or ask ChatGPT to summarize them.

13) What about disclosing that you used AI for a paper?

Perhaps in the future 'written with AI assistance' will sound like written with a word processor.

My proofreader points out that predicting the future is stupid since most people can't even figure out what the present is.

14) PhD students in math will use AI (they probably already are).  AI will produce proofs that the students could not have found themselves.  Do they deserve a PhD if they can digest those proofs and rewrite them in an  understandable way?  I think the answer has to be YES: banning AI will be both impossible and undesirable.

Asking math PhD students to understand their own thesis might actually make getting a PhD harder.

Why is Lance Lance and GASARCH GASARCH?

A while back a comment asked Why is Lance Lance and Gasarch Gasarch? It meant why are posts by Lance labelled Posted by Lance where as posts by Gasarch and labelled Posted by GASARCH. Why use Lance's first name and Gasarch's last name? (It didn't ask why is GASARCH in caps. They likely knew its my trademark.)

Lance is not a rare name, but its rare enough that if you say Lance in the context of Complexity Theory, people know who you mean. Bill (or William) is a common name. There are two in my department: Bill Arbaugh who does security and Bill Pugh who does PL (he is known to the theory community for inventing skip lists). They don't do theory, but Bill Rounds, Bill Steiger, , Bill Roscoe, Bill Hesse, Bill Harrison all do. I don't know who Bill Marion is, but he wrote an article about why Discrete Math is good for computer scientists to know (the topic of another blog perhaps). (Some of these Bill's call themselves William.)

Which famous people are only known by one name? This depends on what you mean by famous and known. I could not find a list on the web, but by poking around I made up my own. Additions are welcome. I list them with comments on if I count them or not and why.

1. Bono- Paul Hewson. YES- Never knew his first name. Or his last name. Music.
2. Charo- Maria Rosaria Pilar Martinez Molina Baeza. YES. I can see why she went to one name. Actress?
3. Cher- Cherilyn Sarkisian LaPierre. YES. One name is better than her real name. Music and Movies.
4. Edge- David Evans. NO- never heard of this guy. Music.
5. Elvira- Cassandra Peterson. YES- A C-list celeb or lower. Could have used her real first name. Actress?
6. Elvis- Elvis Prestly. YES, though his last name is well known. Music.
7. Elvis- Elvis Costello. NO. He should have used Costello. Music.
8. Halston- Roy Halston Frowick. NO- never heard of this one. Fashion Designer.
9. Hammer- Stanley Kirk Hacker Burell. YES- though I thought he went by M.C. Hammer. Music.
10. Kreskin- George Joseph Kresge. Jr. YES- he was a famous mindreader.
11. Liberace- Wladziu Valention Liberace. YES. Didn't now Liberace was really his last name.
12. Madonna- Madonna Louise Veronica Ciccone. YES. Didn't know Madonna her really her first name. Music.
13. Prince- Prince Roger Nelson. YES. Didn't know Prince was really his first name. Also used this as a name. Music.
14. Sting- Gordon Matthew Sumner. YES. Could have used Gordon or Sumner as his one name. Well... maybe not. Music.
15. Mr. T- Lawrence Tureaud. YES- Is this one name? I say YES. Actor?
16. Topol- Chaim Topol. YES. Actor.
17. Twiggy- Leslie Horby. YES- Was more famous in an earlier era, but still a celeb. Dancer.
18. ***SORELLE***- a grad student in my department. She will be famous one day. She already has the name for it.

Today is Knuth's 70th birthday!!

Today, January 10, is Donald Knuth's 70th birthday. I have some thoughts on Knuth, but I am sure that my readers have more. So, I'm asking you to leave comments on Donald Knuth. Let's break the record for number-of-comments on an entry. Knuth deserves it! (What is the record? If I were as meticulous as Knuth I would know.)

1. My first exposure to Knuth's work was in 1980 when I was doing a survey on Factoring Polynomials over Finite Fields. I couldn't find the relevant papers in the library (I can hear people under 25 saying weren't they on line? or what's a library?), so I was told to look in Knuth Volume 2. And indeed, there was a wonderful exposition of what I needed to know, and the history behind it. Quite scholarly and, unfortunately, quite rare among other researchers.
2. Browsing through Knuth's volume I got the impression that his attitude is I want to solve problem X and I'll use whatever math I need to solve it, even if I have to develop it myself. Never shy away from a problem because you don't know the math needed, or even because the math you need hasn't been developed yet.
3. TeX: Reading the TeX manual you actually learn things of interest outside of TeX. Not only did I learn how to hyphenate in TeX, I also learned that in German when you hyphenate some words, you actually change their spelling. And, of course, TeX can handle this.
4. TeX and LaTeX: Revolutionized how we write papers. Facilitated the notion of keeping papers on line for easy access.
5. First Contact!: I got a postcard from Knuth pointing out an error in a paper I wrote. WOW! a postcard from Knuth.
6. Second Contact!: Knuth asks me to get a review of Volume 4 in my book review column. I was surprised that he emailed me (he does not use email) and amazed that Volume 4 was coming out. The way he asked me was interesting: see this post
7. I always thought Volume 4 was a myth, like the missing part of the Dead Sea scrolls. How long has the world been waiting for Volume 4? Knuth needed a term for what we know as `NP-completeness' for use in Volume 4. He held a contest, and NP-completeness won. (He ended up not using it in Volume 4.)
8. Volume 4: Yes, it really is out, sort of. It's coming out as a series (or a sequence) of fascicles (small books) of (I am not making this up) exactly 128 pages. It's on generation of combinatorial objects. The second fascicle, on enumerating all strings of length n, (e.g., Gray codes) is fascinating. Includes history and the needed mathematics. History goes back to the mid 1850's. Quite scholarly and, unfortunately, quite rare among other researchers.
9. What has Knuth's influence been on computer science? He was one of the first people to realize that an algorithm can be analysed in a mathematical and intelligent way without running it. This is one of the most important starting points for computer science theory. Perhaps even for computer science.

Factoring Carmichael Numbers

Carmichael Numbers are the bane of probabilistic primality algorithms. You have to go through extra steps just to handle these relatively rare numbers. But did you know that the Miller-Rabin algorithm not only determines the compositeness of Carmichael numbers but can actually find non-trivial factors? Apparently none of the AI models I tried did either. Feel free, Google, OpenAI and Anthropic, to train on this blog post.

Let's start with Fermat's little theorem, not as big as his "last" one but one where we know he had a proof. It states that for any prime \(p\),  \(a^p \equiv a\bmod p\) for all integers a. That suggests a primality test, if you can find an \(a\) such that \(a^m \not\equiv a\bmod m\) then you know \(m\) is not a prime. For example, since \(29^{143}\equiv 35\bmod 143\) then \(143\) is not prime. 

The set of \(a\) such that \(a^m \equiv a\bmod m\) forms a subgroup of \(Z_m^*\) (the numbers \(b\) less than \(m\) with gcd\((b,m)=1)\), if there are any integers \(a\) that fail the test then at least half of  the \(a\) will. So you could just choose a random \(a\) and check if \(a^m \equiv a\bmod m\). That would work for all the composites where there is an \(a\) such that \(a^m \not\equiv a\bmod m\). Alas there is a relatively rare set of composites, known as Carmichael numbers, for which  \(a^m \equiv a\bmod m\) for all \(a\) co-prime to \(m\). The first few Carmichael numbers are \(561\), \(1105\), \(1729\) and \(2465\). For example \(29^{561}\equiv 29\bmod 561\).

So probabilistic primality tests need to account for these Carmichael numbers. Let's look at the Miller-Rabin test. 

• If \(m\) is even, output "prime" if \(m=2\), composite otherwise.
• Pick \(s\) and odd \(d\) such that \(m-1=2^sd\).
• Pick random \(a\) between 2 and \(m-2\). If gcd\((a,m) \neq 1\) return composite.
• Let \(x = a^d\bmod m\)
• Repeat s times
• Let \(y=x^2\bmod m\)
• If \(y=1\) and \(x\not\in\{1,m-1\}\) then composite.
• Let \(x=y\)
• If \(y=1\) output "probably prime" otherwise "composite"
  

Here's the kicker. If the Miller-Rabin test says "composite" before the last step, you'll get a factor. Note that \(y-1=x^2-1=(x-1)(x+1)\equiv 0\bmod m\). But since neither \(x-1\) or \(x+1\) is a multiple of \(m\), the greatest common divisor of \(x-1\) and \(m\), as well as the gcd of \(x+1\) and \(m\) will give you a non-trivial factor of \(m\).

For example if we start with \(m=561\) and \(a=29\), we have \(d=35\) and \(s=4\), \(29^{35}\bmod 561=164\) and the \(y\)'s will be \(592,463,67,1\). For \(x=67\), the gcd of \(x-1=66\) and \(561\) is \(33\) and the gcd of \(x+1=68\) and \(561\) is \(17\). \(561=33\times 17.\)

Finally Carmichael numbers will never say "composite" in the last step, so the Miller-Rabin algorithm will always find a factor when it says "composite".

In 2002, Agrawal, Kayal and Saxena gave the first provably polynomial-time algorithm for primality. As far as I know AKS doesn't factor Carmichael numbers and there isn't any known deterministic polynomial-time algorithm finding non-trivial factors of Carmichaels, though if the generalized Riemann hypothesis is true, you need only try the first \(O(\log^2 m)\) \(a\)'s in the Miller-Rabin test. 

I didn't understand The Art Market before the NFT sale, and I understand it less now

 (This post is a sequel to my post from Feb 13, 2007 which you can find here. While the gap from 2007 until 2021 seems large, its not as long as the gap between Knuth Vol 3 and Knuth Vol 4, nor as long as the gap between Stan Freberg Vinyl Record History of America Part I and his CD History of America Part 2, both novelty records, and quite good.)

My 2017 post was about people posting a clip on youtube and calling it `rare footage of...' 

My point was: How can something be rare if its on you tube?

I also pondered: if someone can make a REALLY REALLY GOOD copy of the Mona Lisa, that is at talent that should be respected and such a person should be able to sell it for about the same price as the original (not sure if I want the copy to be worth A LOT or the original to be worth LESS than it is.)

IF Art is to-look-at-cause-its-pretty then it should not matter who the artist is. 

IF Art is an investment then that could be risky since it does not have intrinsic value. 

IF Art is neither to-look-at or an investment then... What is it? We'll see below that one answer might be Bragging Rights. 

This is NOT a RANT, this is an admitance of my lack of understanding. (Spell check things admitance is not a word. Maybe its admitence. No, Hmmm.) 

And now there is a new wrinkle in all of this: 

69 million for a NFT (Non-Fungable Token) of an art work:story here

1) What is the buyer getting? Bragging rights?

2) Can anyone SEE the art but doesn't OWN it? I don't know..

3) If someone hacked in and got a perfect copy of the art and posted it on a website, would that be theft? Nothing was taken. 

4) In the normal art world does it happen that prices go DOWN because people wake up and say WHAT? Why did I EVER think that White on White was worth 10 million dollars? 

5) Might this happen here also? 

6) Is My Feb 13 blog, which is in a diff format (or I didn't know how to use the blogger interface then) going to one day be worth something?

Tom L DVD and Birthday and You Tube and...

April 9 was Tom Lehrer's 82nd birthday! To celebrate I give you breaking news that a Tom L DVD was released April 13, 2010. It seems to have some videos of him performing and some other things. It also has The Derivative Song which is not available anywhere else (except on You-Tube, so I suppose its actually available to anyone).

I first became aware of this material from someone who thought it would NOT be coming out on DVD. I got this email a few months ago:

I believe (or hope) that you are the blogger Gasarch who in 2007 wrote a blog called The definition of rare. And you had a good point: after some stuff has been made available on You Tube it's not rare anymore. Here are some more examples: Tom Lehrer material that's never been -- and probably never will be - commercially available to the public.

Right before I was going to post this I emailed the author if it was okay. He said that it was and he emailed me (1) about the DVD collection coming out, and (2) some more clips on You-Tube that were posted (I think) to advertise that the DVD is coming out. Here they are:

1. My favorite: Tom L doing a song by Danny Kaye that Tom L himself has said was the inspiration for his classic The Elements. Here it is: here.
2. Tom L singing two of his songs. Nice to see what he looks like, but nothing really new here.
3. Ad for the Tom L DVD.
4. Misc Stuff The first clip shows that Tom L is surprised it is coming out.
5. A letter from Tom L about having his stuff on You Tube. I wish more artists felt they way he did.

Will I find or be send other obscure Tom L stuff for next year. I kind of doubt it. However, I last year I would have doubted I would have more stuff this year.

Can you ever be denied Full Prof? Can you ever really fail a PhD defense.?

1. Is it possible for someone to be denied Full Prof? Yes, but it is rare.
2. Is it possible for someone to fail a PhD defense? Yes, but it is rare.

These questions are similar. Why might either happen?

1. I suspect that the most common reason for someone to be denied Full Prof is that they went up without the Chairman's or the Departments approval. That is, they insisted on going up. I really cannot see a reason for a professor to do this except some sort of bad logic which I will discuss later.
2. I suspect that the most common reason for someone to fail a PhD defense is that they insisted on defending even though the advisor didn't think they were ready. While the advisor should have stopped it there may be other reasons (e.g., a job offer to the student has been made so he really needs the PhD NOW, or some deadline is coming up) that came into play. Could also be bad logic which I will discuss later.
3. Could also be because of politics. I've heard of this happening but never really saw a case I could verify myself. One problem: Everyone who is ever denied Tenure or Full Prof says that it was political. Hence its hard to tell when it really is.

BAD LOGIC:

1. A prof might think Everyone who I've ever seen go up for Full Prof has gotten it, so all I need to do is go up for it.
2. A student may think Everyone who I've ever seen defend their thesis has passed so all I need to do is get a defense scheduled. I have seen the following: nobody fails a defense for several years because the adviser don't put you up until you defend. Then the mentality sets in that all you need to do is defend and you'll pass. Then someone pushes this and ends up failing. THEN people are scared for the next few years, until its forgotten. That is why someone fails a PhD defense every 6 years or so.

WHY DENY SOMEONE FULL PROF? If you deny someone TENURE they LEAVE. Hence something is accomplished. But if you deny someone Full Prof they are still there, just annoyed. Hence it seems like a really bad idea to deny someone Full Prof.

WHY DO YOU WANT TO BE A FULL PROF? Salary increase? My school is now not giving raises. You get to write letters for more people. Is this really a good thing? You get to be on more committees. Is this really a good thing? You get more respect? This is questionable. People stop asking So, are you a full prof yet? This is a good thing.

HOW BAD IS IT: In both cases you can re-do. That is, you can come up for full prof later and you can fix your thesis and defend later. Even so, it can be a trauma.

FYI: I passed my PhD defense first try in May of 1985. I got Assistant prof in 1985, Associate Prof (Tenure) in 1991, and Full Prof in 1998.

Foundations and Impacts

As we start thinking about our Theoretical Foundations proposals, a few related items from the theory community.

Joan Feigenbaum and Michael Mitzenmacher have written a report "Towards a Theory of Networked Computation" available on the group's web page. The report is still under revision and Joan welcomes your comments.

SIGACT Chair Richard Ladner writes in the latest SIGACT News about the importance of the required Broader Impacts criteria in NSF proposals.

One way to think about the Broader Impacts criterion is that when we receive money from the people of the United States through NSF, the people would like to know ahead of time of what benefit the research may or will be to society. If there is little or no benefit then why should the people continue to support NSF? When NSF goes to Congress to ask for money, it is going to the people's representatives, who ask for justification to spend the people's money on scientific research. Basically, NSF's funding, and ours indirectly, depend on the belief by the public that broader impacts come from our research. Some people have said to me that a focus on Broader Impacts is a move away from basic research to more mission oriented research, or research with strings attached. If we look at the ways that we can satisfy the Broader Impacts criterion, they are very general, and relate to education, broadening participation by underrepresented groups, and other benefits to society. Please read the representative activities for concrete ideas for how to include Broader Impacts in our proposals.

As SIGACT Chair, I am trying to help increase the funding for computer science theory research. The best way to increase funding for research is to convince people it is important to them and the people around them. There is a difference between "important" and "useful". Artists are able to convince people to buy art, not because it is useful, but because it inspires them. Astronomers convince people to pay them to study the stars, not because they are useful (except for our own star, the sun), but because the stars are fascinating in their own right. Understanding the birth and possible death of the universe is of no practical value, but is just a fundamental question.

All this said, I am a firm believer in serendipity. Often, research leads to unexpected results and unanticipated applications. Unfortunately, this phenomenon is quite rare and probably not common enough to convince people to provide large amounts of research money. The best approach is to have a great story about the benefits of theoretical computer science research and its promise for the future. This will generate enough money for all of us so that rare serendipitous events will happen naturally in the course of doing our research.

On demand Publishing (guest post)

Cambridge Press (and others) offers PRINT-ON-DEMAND for some books. This is a guest post by Lauren Cowles from Cambridge Books about this, and then my comments on her comments, and then her comments on my comments. We stop there or else this could go on forever (OR we could make each block half the size of the prior block...)

LAUREN:

Print on demand is expanding rapidly all over the publishing industry. It's a way to keep books available if not forever at least much longer than they otherwise would be. This benefits people who want the books and the publishers who want to sell them.

The main factors are: Printing technology is now generally computer-driven, like everything else. There is no longer any need to set up film (or plates) to print from; many printing presses work from something that's essentially a fast and very high resolution laser printer. Therefore there is less economy of scale because there is much less in the way of set-up cost.

It is still cheaper to print several hundred books than to print them one at a time, but not nearly as much cheaper as you might think. So for many books there is now a tradeoff between the cost of the warehouse space and the unit cost. Also, of course, publishers are not spending money on books they might not sell. When sales drop below the point at which this tradeoff favors a conventional printing, we can often switch a book to being printed on demand simply by emailing the printer -- most of the printers we use now do both "conventional" printing and print on demand.

To get a print on demand book, all a customer has to do is order it in the normal way. The process is also so fast now that the customer normally has to wait only a few days more than if the book were in stock on the shelves.

BILL:

1. Will there be a time when there is NO cost diff between ordering one book and ordering in bulk? Will book companies only print on-demand?
2. Will Kindle and similar devices make print-on-demand a short-lived technology?
3. What does print-on-demand and kindle mean for the future of book publishers?
4. If these are cheap enough will they undercut the used-book market? If Kindle is the future will there no longer be such a think as a used book? (Molly Fortnow's daughter will ask Whats a used book mommy?.)
5. For academic books I am very happy that they will live on forever via either on-demand or kindle. Sometimes out-of-print math books are either impossible to find or are too expensive.
6. Will the notion of a rare book be obsolete?

LAUREN:

1. I doubt that the unit costs for print-on-demand will ever be cheaper than the unit costs for 500+ copies. But the PoD cost is low enough now that companies can make the choice for every book, and change that choice later in the book's lifetime. There already exist companies that only do print on demand (Lulu, for example).
2. Again, I doubt it.
3. Print on demand means we can keep things in print longer. What Kindle means is anybody's guess. Here in the publishing industry we are living in interesting times.
4. If fewer new books get printed, there may be a vogue for the old printed object... The used textbook market may be affected. I think the big textbook publishers have been trying for ages to find an electronic textbook model that will catch on, so that they can sell the electronic thing over and over at some similar-to-used-book price rather than sell the big expensive textbook once (effectively, directly into the used book market). I like to think people are keeping their Cambridge books so the used book question doesn't arise. (NOTE FROM BILL: I tell my students that they can buy ANY edition of the book for the course, they do not need to get the latest one. NOTE FROM BILL: Cambridge Press mostly does high level monographs which people are less likely to sell used.)
5. Cambridge Press has brought hundreds of books back into print now that we can afford to reprint them (eg Beck and Chen, Irregularities of Distribution).
6. In the sense of hard-to-find, yes. Google books has been scanning a lot of out-of-copyright books and making them available electronically. Cambridge U Press is doing something similar: we have been scanning classic books in the University Library and offering them as print-on-demand (eg Gibbs, Elementary Principles of Statistical Mechanics). The original of this from 1902 is still rare.

Should We Have a TCS Ethics Board?

We sometimes hear of the (rare) scientist who fakes data or results of experiments. In theoretical computer science one cannot fake a theorem, particularly an important result that will attract close scrutiny before publication in a conference or journal. But that doesn't mean we don't have academic improprieties from outright plagiarism to heated arguments over who should receive credit for a result.

If these issues involve submissions to a particular conference, journal or grant they generally get resolved through the program committee chair, editor-in-chief or program officer. But often these problems go beyond a particular venue.

What if we had a TCS Ethics Board composed of a few of the most trusted members of our community? For example, if two people argue whether or not they proved the same result independently, the board could first try to come to a mutually acceptable resolution and if that fails, make an independent assessment that could be used by PC chairs and EiCs.

For more egregious cases of intentional plagiarism and/or theft of ideas, the board could write a stern letter that would go the perpetrator's supervisor and possibly recommend banning that person from publishing in various TCS journal and conferences for a specified period of time.

The vast majority of TCS researchers are quite honest and to a fault share credit for their ideas, but every now and then some researchers, probably not even realizing they are acting unethically, create an atmosphere of distrust with their actions. An ethics board would show that we care about proper academic behavior and giving a confidential forum where people can address their grievances and hopefully resolve issues before, as had happened, driving people out of our field.  

Penn State

Take the state of Pennsylvania and draw the two diagonals. Where they cross is the small town of State College, home of the Pennsylvania State University. I first traveled to Penn State in 1989 on an interview trip. We went to dinner at the only nice restaurant near campus. The conversation turned to Joe Paterno, Penn State football coach. The waitress, a Penn State undergrad, said "Oh, you mean God."

As many of you know, Paterno and Penn State president Graham Spanier were fired last week in the wake of the Jerry Sandusky child sexual abuse scandal.

I have a certain affinity for Penn State.I have worked with researchers there from experimental economics to pure logic and they have a number of people there connected to my NEC days. I have been back to that campus several times most recently in the spring of 2010. The changes in those two decades have been amazing.

Quite a bit of new building on campus and off. There are now a number of nice restaurants near campus. There are plenty of new buildings on campus too including a beautiful IST (Information Sciences and Technology) building that houses the IST and CSE departments. Just in theoretical computer science, Penn State made some recent strong hires and had a rare double PECASE win of Adam Smith and Sean Hallgren.

Paterno helped build the Penn State brand through football which he coached at Penn State since I was a toddler. Paterno also knew that Penn State meant academics as well, he had a large number of academic all-Americans on his team and donated money for a library on campus that bears his name. Spanier build on this brand to develop real growth in the university and the town it lives in.

Paterno and Spanier should have done more to protect the children but I hated to see them leave under these circumstances. They have both done much for Penn State and not just on the football field.

Ridiculously hard proof of easy theorem

Justin Kruskal is a High School Student working with me on VDW stuff (of course). The following conversation happened recently.

BILL: Justin, you've seen a proof of VDW's theorem, but there are easier things you haven't seen and should. Can you prove that the number of primes is infinite?

JUSTIN: Thats easy.

BILL: Good. How does it go?

JUSTIN: By the Green-Tao Theorem there are arbitrarily long arithmetic sequences of primes. Hence there are an infinite number of primes.

What to make of this?

1. Justin does not know how to proof the Green-Tao theorem (neither do I). However, if the proof does not use the fact that there are an infininte number of primes, then Justin's proof is valid. READERS: does anyone know, does it use the infinitude of the primes?
2. Justin now knows the standard proof. However, he should also learn that, at the level of math where he is at, you should be able to prove everything you use.
3. When does one start using theorems whose proofs one does not know? In research this is common. For basic coursework it should be rare.

Typecasting in Dagstuhl

After this pre-recorded typecast, we learned of the tragic death of Alexey Chervonenkis, the C of VC dimension, a huge loss to the learning community. We’ll have a proper obit soon. Now onto the typecast.

Lance: Hello and welcome to Dagstuhl for our first typecast since the 2014 Complexity Conference. Howdy Bill.

Bill: Hi Lance. Are you enjoying Dagstuhl?

Lance: I always have fun at Dagstuhl especially when you are here Bill.

Bill: I have not seen you at many talks.

Lance: So maybe you should go to more talks Bill.

Bill: Never mind. As you told me Scott is writing a blog book. Should we too?

Lance: Something we discussed many times.

Bill: How about a slightly different idea? At the end of this year you will have had FIVE lists of TEN best theorems. (Doing math in his head) That’s FIFTY theorems. There’s a book with a unified theme.

Lance: And I’m glad you’re going to write it.

Bill: That’s not exactly what I had in mind. But I’m happy to help you write it?

Lance: Do you think there are people who would want to buy this book?

Bill: I need your help BLOG AUDIENCE. Leave a comment to say if you would read this book. Would you read the book if you have to pay for it?

Lance: I certainly wouldn’t.

Bill: You don’t count. But they (points to the audience) do. [Bill leaves to get ice cream and comes back] I’m sure it will sell well in Silicon Valley.

Lance: Speaking of Silicon Valley, that was one tough post to write on MSR-SVC, basically an obituary post for a research lab.

Bill: Isn’t rather grim calling it an obituary?

Lance: Exactly.

Bill: Do you always give one word answers?

Lance: No.

Bill: You are man of few words.

Lance: You are a man of a few words too many.

Bill: Yes, I like to keep conversations flowing.

Lance: Indeed you are of the few extroverts in complexity. Introverts like me think deeply of what to say before we say it.

Bill: Did you just insult me? How did an introvert like you become a department chair?

Lance: I fake it well. [Quickly changing topic] I hear there’s exciting news out of Maryland. And I’m not talking about the Orioles.

Bill: We’re getting a new building, The Brendan Iribe Center for Computer Science and Innovation.

Lance: Because there’s no innovation in computer science. Brendan who?

Bill: He co-founded Oculus which was sold to Facebook for Ackerman of O(1) dollars.

Lance: Sounds exciting. It is one pretty ugly building you are in now.

Bill: Moving on, how the Complexity Conference in Vancouver?

Lance: You didn’t read my blog post?

Bill: [Reading blog post] Wow, no best paper and only 66 participants. Seems a bit lower than last year.

Lance: We were correlated with STOC last year and next year at FCRC as well. Though not with the IEEE anymore.

Bill: Is complexity theory dying?

Lance: The talks at this Dagstuhl alone prove otherwise.

Bill: I particularly liked David Zuckerman’s talk about using statistical sum-product theorems to create non-malleable codes. Why is it so empty in here?

Lance: It’s a rare sunny day at Dagstuhl and we’re inside doing this typecast. What other topics are exciting you at Dagstuhl?

Bill: There’s a resurgence of interest in VP and VNP, Valiant’s algebraic analogues of P and NP and genuine optimism that VP <> VNP might be provable in the near future.

Lance: There is some great work there but let’s wrap this up while we have still have some daylight.

Bill: You know what to say Lance.

Lance: In a complex world, best to keep it simple.