The Situation at the NSF

The National Science Foundation is one of the agencies most affected by the various executive orders issued by the Trump administration. As a critical funder of research in theoretical computer science, and science and engineering more broadly, the NSF has effectively come to a standstill sending universities scrambling. Here's a little primer on what's going on in the foundation.

The NSF, like all parts of the federal government, has to follow the Executive Orders, and the first step is to determine which orders apply to NSF business, then how these orders can be addressed in a way that satisfies the White House and other supervisory agencies. This is a process that the NSF leadership works out and negotiates.

For the immediate NSF business, most influential is the order Ending Illegal Discrimination and Restoring Merit-Based Opportunity, which states, among other things, that some DEIA measures violate anti-discrimination laws. Since NSF cannot pay for activities that violate current law, all active awards are checked whether they might be affected by that. This is done with the highest priority, since it affects the cash flow of current awards. After that, awards that are in progress towards being made, as well as entire programs and solicitations, will be reviewed for compliance with the executive order. Until compliance is assured in a way acceptable to the supervisory agencies, no new awards or other financial commitments can be made. After that, normal business should resume, although probably with a huge backlog.

The Hiring Freeze Executive Order also has a huge influence on NSF. The hiring freeze applies to all federal agencies, but NSF has a large number of rotators, usually university researchers who serve as a program director for a one to four-year term. The rotators are essential to the programs and the hiring freeze prevents new rotators from starting their role at the NSF. The hiring freeze will last for 90 days; then a plan to reduce the size of the federal workforce will be presented, and NSF might, we hope, again start hiring. In the past, NSF hiring processes were excruciatingly slow, so we need to expect NSF to be understaffed for a significant period beyond the 90 days. The recent Fork in the Road letter of the Office of Personnel Management might lead further people to leave federal employment, and the strong stand on return to in-person work might make hiring Rotators even more difficult. So, although all this is in flow and changing, it currently looks like difficult times ahead for the NSF.

What does this all mean for the research community? Some current funding locked up, hopefully for a short time, and heavy delays on new grants given higher scrutiny and lower staffing, and funding in fairness or focused heavily on broadening participation might be killed all together. A lengthy delay will mean less funding for PhD students and postdocs next academic year. Given the reduced funding and the political atmosphere, we may lose America's ability to recruit the world's top talent to our universities. 

You can read official news on how the executive orders affect NSF and also see Scott's take. 

Update 2/2/2025: For now, the NSF is getting back to business due to a temporary restraining order.

Lautemann's Beautiful Proof

In writing the drunken theorem post, I realized I never wrote a post on Lautemann's amazing proof that BPP is contained in \(\Sigma^p_2\), the second level of the polynomial-time hierarchy.

Clemens Lautemann, who passed away in 2005 at the too young age of 53, wasn't the first to prove this theorem. That honor goes to Michael Sipser who proved that BPP is in the polynomial-time hierarchy using Kolmogorov complexity and Peter Gacs who puts it into the second level using hash function, both results in the same paper. 

Nisan and Wigderson, after Sipser, Gacs and Lautemann, note that BPP in \(\Sigma^p_2\) follows from their pseudorandom generators, simply guess a potentially hard function and use the universal quantifier to check that it's hard. Once you have a hard function you can use their generator to derandomize BPP.

But Lautemann's proof is incredibly beautiful because he just directly gives the \(\Sigma^p_2\) (\(\exists\forall)\) expression, and two simple probabilistic method arguments to show it works. QED. 

Let L be in BPP accepted by a probabilistic polynomial-time Turing machine M with error bounded by \(2^{-n}\). Let \(A(x,r)\) be true iff \(M(x)\) using random tape \(r\) accepts. \(A(x,r)\) is deterministically polynomial-time computable. We can assume \(|r|=|x|^k\) for some \(k\). 

Here is the \(\Sigma^p_2\) expression for input \(x\) of length \(n\). All quantification is over binary strings of length \(n^k\). Let \(\oplus\) be bitwise parity and \(\vee\) be logical OR.

\(\exists z_1,\ldots,z_{n^k} \forall y\ A(x,z_1\oplus y) \vee \ldots \vee A(x,z_{n^k}\oplus y)\)

That's it, the beautiful self-contained formula. We just need to show that this expression is true if and only if \(x\) is in L. 

Suppose \(x\) is in L and pick \(z_1,\ldots,z_{n^k}\) independently at random. For a string \(y\) the probability that \(A(x,z_i\oplus y)\) is false for all \(i\) is at most \((2^{-n})^{n^k}=2^{-n^{k+1}}\). So the probability that for some \(y\) this happens is at most \(2^{n^k}2^{-n^{k+1}}=2^{n^k-n^{k+1}}\ll 1\) so for some choice (even most choices) of the \(z_i\), the expression will be true.

Now suppose \(x\) is not in L. Fix  \(z_1,\ldots,z_{n^k}\) and now pick \(y\) at random. The probability that \(A(x,z_i\oplus y)\) is true for a fixed i is at most \(2^{-n}\), so the probability that one of them is true is at most \(n^k2^{-n}\ll 1\). 

MIC DROP

People who live through two square years

 44*44=1936.

45*45=2025. This year!

46*46= 2116.

Since my fake birthday is Oct 1, 1960 (I do not reveal my real birthday to try to prevent ID theft), which is past 1936, and I won't live to 2116 unless Quantum-AI finds a way to put my brain in a a vat, I will not see two square years in my life :-(

Since I keep a list of celebrities (defined as people I know who have some fame - so its subjective) who are over 80, I have a LIST of celebrities who were born in 1936 or earlier. I was going to list them in this post but there are to many. So I list those that I think my readers care about, and point to the full list.

Here are people who have lived through two squares who I think you care about. I leave out how old they are or what year they were born.  They are in alphabetical order by their first names. I put a * next to the people who, in 1936, were  AWARE that it was a square year. So the starred names are those who truly ENJOYED living through 2 square years.

NAME                  KNOWN TO US FOR

Andrzej Ehrenfeucht   Math. EF-games (he is the E)
Anil Nerode                   Math- Recursive Math
Aviezri Fraenkel           Math-Combinatorial Games

Buzz Aldrin             Walked on the moon

Charles Duke           Walked on the moon.

Dana Scott            Math-CS. Prog Langs. Turing Award
David Scott           Walked on the moon
Dirk Van Dalen     Math- Logic

Eric Hirsch Jr        American Educator *

Harrison Schmidt      Walked on the Moon.
Harry Furstenberg     Math-Ergodic methods in Ramsey Theory.
Heisuka Hironik        Math-Algebraic Geom-Fields Medal
Herman Chernoff      Math-Probability *

Jack Edmonds         CS. Theorist.
James Watson          Biologist-The Double Helix. Nobel Prize with Crick.*
Jane Goodall            Zoologist and Activist
Jean-Pierre Serre     Math. Algebraic X. Fields Medal.*
John Thompson       Math. Group Theory.  Fields Medal, Abel Prize

Micahel Rabin           CS/ Math. Theorsit. Turing Award.

Noam Chomsky          Linguistics. Did work on Grammars

Richard Friedberg     Physicist. Also invented Priority method in Rec Theory.
Richard Karp            CS. Theorist. Turing Award. .
Richard Stearns        CS. Theorist. Turing Award.

Stephen Smale         Math-Lots of Stuff

Tom Baker             Actor-Dr. Who.
Tom Lehrer            Math/Novelty songs..*
Tony Hoare            CS. PL. Turing Award.

Volker Strassen       Math-CS.

Walter Koenig         Actor. Star Trek
William Shatner      Actor- Star Trek

For my complete list see here

It is currently  impossible for someone to live through three square years (again, unless they get their brain in a vat, or some other not-yet-invented mechanism). In a much earlier era it was possible: 

20*20=400

21*21=441

22*22=484

So if you were born in 400 and lived to be 84 years old, three squares! While MOST people didn't live that long back then, SOME did.

10*10=100

11*11=121

12*12=144

Born in the year 100, live to be 44 years old. Was the calendar well established by then?

(ADDED LATER: a colleague emailed me about the calendar. Dionysius Exiguus is credited with inventing the AD/BC calendar (not to be confused with the band AC/DC). He was born in 470 so lets say that the modern calendar was in known from 500 on. (I am not dealing with the times its changed a bit.). SO

23*23=529

24*24=576

25*25=625

To live through three squares you would need to live to 96.

To be aware that you lived through three squares you would need to ive to 104.

To enjoy the 3-squareness you would need to be a healthy 104 year old.

Did someone who was born in 529 live to 625. I would doubt it. See here for an article about how long people lived in Middle Ages. Or, more accurately, how short they lived. 

)

Reminds me of a great line from A Funny Think Happened on the Way to the Forum, a musical that takes place in the early AD's. The character Pseudolus says: 

(Looking at a bottle of wine) Was 1 a good year?

The Fighting Temeraire

What does an 1838 painting tell us about technological change?

A colleague and I decided to see how well LLMs could teach us a topic we knew nothing about. We picked the Romanticism art movement. I asked ChatGPT to tutor me on the topic for an hour. Chatty picked four paintings. 

Top Left: Liberty Leading the People (Delacroix, 1830)
Top Right: Wanderer above the Sea of Fog (Friedrich, 1818)
Bottom Left: The Fighting Temeraire (Turner, 1838)
Bottom Right: The Third of May 1808 (Goya, 1814)

For each of these paintings, I put the painting up a one screen and used the voice feature to have ChatGPT give me an overview of each, and then we would have a discussion about it where I would ask about various features. Ended up spending about an hour on each. Was it successful? I now know significantly more about the Romantic art period and these paintings, though of course not an expert. It was certainly a better and more enjoyable experience than freshman seminar course on art history I took in college.

Let discuss one of these paintings in more detail, the 1938 painting The Fighting Temeraire, tugged to her last berth to be broken up by Joseph Mallord William Turner, on display at the National Gallery in London. 

The Fighting Temeraire by J.M.W. Turner (click on picture for more detail)

The 98-gun ship Temeraire featured on the left fought in the Battle of Trafalgar. This painting captures the ship being towed by a steam tug through the Thames to be broken up for scrap. 

Much to love in the painting: the reddish sunset, the reflections of the boats in the water, the detail of the Temeraire and the lack of detail of the tug.

But also note the nod to technological change, the tall sailboat being taken to its end by a coal-powered tugboat, marking the new era of shipping vessels, the industrial revolution in full swing, and the beauty we lose to progress. Now a bad metaphor for the AI revolution of today.

If you want to learn more about the painting, you can watch this lecture from the National Gallery, or you could ask your favorite LLM.

Presidential Quiz!

I made up a quiz about the American Presidents here.  

It has 40 questions. In the modern electronic age you can probably look up most or even all of the answers. So what to do about that?

1) The quiz is not for money or credits or anything, so if you ``cheat'' you only cheat yourself.

2) Be honest with yourself and take it in three hours.

3) USE the web and see how long it takes you to finish it. You can make up some way to measure how well you did by combining how many you got right with how long it took.

4) The answers, that I will post later in the week or next week, have lots of other information of interest. So  whichever of 1,2,3 you do or something else, read the solutions (even those you got right) and be enlightened. 

It is actually titled Prez Trivia Quiz. This might not be accurate.

What is trivia? I think it is knowledge that does not connect to other knowledge and hence is not important. Some of my questions are trivia, and some are not. I give examples of each:

What is the most common middle initial for a president? This is clearly trivia. I don't know the answer and its no on the quiz, but I might put it on the next time I do this, four years from now.

(ADDED LATER: A comment used an AI and gave the wrong answer. However, this encourgaged me t find out the right answer. The website I found is here. The answer is H: William HENRY Harrison, George HERBERT WALKER Bush, William HOWARD Taft, Barach HUSSEIN Obama. Second place is W with three: George WALKER Bush, Ronald WILSON Reagan, and, much to my surprise, President Woodrow Wilson was actually Thomas WOODROW Wilson. There are many initials that appeared twice. Does any of this enlighten me? About presidents no. Finding out why the AI got it wrong would be interesting but perhaps unknowable.) 

Five presidents ran again for president four or more years after leaving office. Name them and how thy did. This is not trivia (what word means the opposite of trivia? See later). Since Trump ran four years later and won it is of interest to see what circumstances in the past  lead to a former prez (a) running again, and (b) winning. 

If you are so inclined you can, for each question on the quiz, say if its trivia or not. YMMV.

I googled "opposite of trivia" and got this informative website (I am not being sarcastic) here.

"Our Days Are Numbered"

Slide in Lev Reyzin's JMM talk "Problems in AI and ML for Mathematicians" Reyzin is paraphrasing Telgarsky. Posted with permission.

Last week I attended the Joint Mathematics Meeting in Seattle with a theme of

We Decide Our Future: Mathematics in the Age of AI

With little computational complexity in the conference, I attended many of the AI talks. You could divide them into Math for AI and AI for Math. Mathematics of course plays critical roles in machine learning optimization, and several talks focused on provably good learning algorithms, though they overemphasized the importance of such. Do you get on a plane because you understand the physics or because air travel has a strong safety record?

But let's focus on AI for Math which generated the most discussion and angst. 

I started the conference sitting on a panel on the challenges of peer review in mathematics. Math doesn't have the replication crisis that dogs other scientific communities. But math does have papers with very specialized, long, detailed proofs and few qualified referees willing to check them over with care. 

We're not there yet, but in the "near future" we ought to have AI systems that can verify well-written proofs by compiling them using proof assistants like Lean. Referees could spend less time on checking proofs and more on deciding whether the model, theorem and/or techniques merit publication. We might get to the point that you couldn't even submit a paper to a journal until the proofs have been verified.

It's what comes next that really spooks mathematicians. While AI has made significant progress in solving competition problems with DeepMind's AlphaProof and Open AI's O3, it has only played minor roles in developing new ideas for theorems. Eventually AI systems will find critical steps for publishable theorems. Who do we give the credit to? When AI systems become stronger that typical PhD students, what kinds of problems to we give the students? 

We'll get plenty of AI slop, flooding journals with mathematical papers that technically prove new theorems but don't offer any particularly interesting or illuminating insights. But we'll also get mathematicians who can unleash an army of virtual grad students to find new connections between different subfields, or make significant progress on major open problems in the field. 

Some mathematicians don't want AI trained on their papers and using their techniques and theorems, even though they wouldn't have problems with other mathematicians doing so. In any case, they might not have much choice as many publishers are making deals with AI companies.

The future of mathematicians might follow that of artists and programmers. The best will do fine since they can find proofs beyond what an AI can do. Mathematicians who know how to ask the right questions can harness AI to make themselves far more productive. All mathematicians will have to navigate this brave new world.

"At least they'll still need us to teach the courses," one mathematician told me. Don't be so sure.

Random Thought on AI from someone in the REAL WORLD

Guest Post from Nick Sovich. 

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

Bill Gasarch recently blogged on RANDOM THOUGHTS ON AI here . He is in the realm of theory. I am in the realm of applications so I asked if I could do a post on AI from that background. He agreed, and here's the post:

1) Words Matter

Today you tell a foundation model who to be and how to behave by giving it a system prompt and a chat prompt. The system prompt is the AI analog of 

 I’m a CS professor, I’m an expert in Ramsay theory, and my goal is to help students learn. 

The chat prompt is the AI analog of

“Hi CS Professor, can you please help me write a blog post to formulate my thoughts on AI”?

Words comprise these system prompts and chat prompts. Getting the right words is very important, in the same way writing the right lines of code is important.

So if you have an AI that *can* be any 157-level IQ expert in any field, you still haveto tell it what kind of expert to be, what its worldview is, and how to communicate. Because it can’t have infinite world views and communication styles all at once.

Example System Prompt and Chat Prompt is here.

 
2) If English becomes the #1 programming language, then what’s the difference between a poet and a computer scientist?

There has been talk in the industry of English eventually becoming the number 1 programming language. What does that mean? A poet has mastery over the English language. A computer scientist has mastery over programming languages. A poet can create works of art.  A poet can be creative, but so can a computer scientist. A computer scientist can be pragmatic, but so can a poet. Will poets become better programmers than computer scientists?  Will computer scientists become better artists than poets? Does it matter?

3) What is code and what is poetry?

Bad code doesn’t compile, or it compiles but doesn’t run, or it runs but has bugs. Bad poetry doesn’t express the author’s intent, or it doesn’t evoke the reader’s emotion, or it doesn’t convey a message to society. Bad code is still code, bad poetry is still poetry. Humans can produce good and bad code and good and bad poetry. AI can produce good and bad code and bad poetry. Can AI produce good poetry?


4) AI is a tool, like auto-complete. 

This is both good and bad.

Under use the tool, and you waste a lot of time.

Over use the tool and you don't understand your own product.

5) Where should AI start and end in academia?

This is an important question worthy of a separate blog that I might do in the future.

6) AI can either replace people or empower people. 

We should look for ways that it empowers people. A nice 38 second clip about that here.

As an example:

Good: Giving the vet tech tools to record my intake questions through natural language instead of pen and paper.

Bad: Automating away all vet tech jobs and replacing them with humanoid robots that would scare my dog anyway. It’s traumatic already when a human pins her down to give her eye drops.

Example System Prompt and Chat Prompt here.

7) How many tokens and how much test-time computation would it take to fully capture my dog’s personality?

First of all, the real thing is better. To see what the latest models are capable of, I used the reasoning models to help generate prompts for the diffusion models, to see how closely I could replicate my dog’s appearance. The reasoning models capture the veterinary terminology very well, and increased specificity in prompting leads to better results from the diffusion models. The diffusion models get close, but don’t seem to have the level of expert veterinary knowledge that the reasoning models do (yet).

Example Prompt and Resulting Image here.

 
8) If spending an hour a day on social media can radicalize you politically, can spending an hour a day reasoning with an AI on technical topics make you more technical?

Spending an hour a day searching the internet for technical topics and reading them can certainly make you more technical. If AI helps you get that information more efficiently, and if the AI actually works (hallucinates less than doing a web search would lead you to incorrect technical information), then it follows that AI can be more efficient than a web search in making you more technical. AI needs to be “aligned”, just like the web search needs to be “unbiased”. And make sure that one of the topics you learn, either through web search or AI, is how to read a map if you lose internet access.

BILL's comment on point 8: While I agree that spending an hour a day (or more) reasoning with an AI on a technical topic is a good idea, make sure you don't fall into a rabbit hole.  For example, while using AI to help me with Ramsey Theory I, on a whim, asked it to write me a poem about Ramsey Theory. It wasn't that good but it was better than what I could do. I won't reproduce it for fear of sending my readers down a rabbit hole.

 

When DO Names Change? When SHOULD Names Change?

 BILL: Good news for Jimmy Carter! He won  The Betty White Award! (see here).

LANCE: That's not good news. He had to die to get it.

BILL: Call it a mixed bag. Good news for me, in that I have a famous person for The Betty White award. And I later found out that Manmohan Singh, a former prime minister of India passed away on Dec 26, 2024, so I have two famous people for The Betty White Award.

LANCE: You should change the name to The Jimmy Carter Award. Did Betty White start a Department of Education?

BILL: No can do. What if someone even more famous dies next year. I don't want to play musical chairs with the name. Past winners were Pele and The Pope Emeritus. Were they more famous than Betty White?

LANCE: YES!

BILL: And that's the problem. If I changed it to The Pele Award and later to The Jimmy Carter Award, that's three names in three years. Also,

If it was The Pele Award, people would think it has to do with Soccer.

If it was The Pope Benedict award people would think it has to do with the Catholic Church.

If it was The Jimmy Carter award, people would think it was about building houses.

If it was The Manmohan Singh award, people would think I am not an ignorant American who knows nothing about Indian Politics.

With Betty White there is nothing so striking about her to think its about something else. (Not quite true- she was involved with Animal Rights.)

LANCE: Yup, Carter got the Nobel prize for homebuilding. You over estimate how many people care about  The Betty White Award. But you named the award after Betty White only because she died shortly before you started the award. Hardly seems like a good criteria. 

BILL: Well, we do this all the time in computer science.

LANCE: Indeed. Some of them, like the Turing Award, survived the test of time. Others, which we shall not name, have not.

But anyway, all of this raises the question, should we change the name when we have more famous dead people? 

BILL: Rarely. Do you have examples of names being changed?

LANCE: Yes, though not replaced by other names.

The best student paper award at the Complexity Conference was named after Ronald Book from 1999 to 2104 and then quietly dropped when the conference left the IEEE. And of course when Rolf Nevanlinna got cancelled in 2019, changing his award to the Abacus Medal. Not a person named Abacus but the ancient computing device. Personally I'm holding out for the Slide Rule Statue.

BILL: So, we need more examples of name changes that are NOT because a person was cancelled or a conference changes organizations.

LANCE: It's hard to do because it's admitting you made a mistake to begin with. So instead we are getting gun shy on new award names. The ACM has made it harder to make a named award and the more recent SIGACT awards have been named after those who died long ago (Gödel) or still living (Knuth). An exception was made for the Danny Lewin Best Student Paper Award at STOC. Danny died fighting the terrorists on American Flight 11 on September 11, 2001 and the award was named for him starting in 2002.

BILL: So it's no longer worth dying early to get an award.

LANCE: I wouldn't recommend it.

The Betty White Award for 2024

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

AND three Honorable Mentions:

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

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

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

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

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

So she also gets an Honorable Mention. 

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

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

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

My Drunken Theorem

Bill's SIGACT Open Problems Column remembering Luca Trevisan is out. I chose the problem of whether Promise-ZPP in P implies Promise-BPP in P, an extension of an earlier theorem by Luca and his co-authors, which showed that Promise-RP in P implies Promise-BPP in P. But now, let me share a story that I didn’t include in print.

In the mid-1990s, I receive an email from Luca saying that Noam Nisan had told him I’d come up with an easier proof of one of his theorems. Luca asked if he could use it in his upcoming paper. I had no idea what he was talking about.

Then, I vaguely remembered…

I was in Dagstuhl, back when we’d hang out in a room meant for drinking beer and wine. I had, shall we say, more than one good German Pilsner, when Noam came by and asked if I knew how to show that Promise-RP in P implies P = BPP. I mumbled something about how it might follow from Lautemann's proof that BPP is in the second level of the polynomial-time hierarchy. Lautemann’s proof uses the probabilistic method in both directions, which I thought might fit nicely into Promise-RP.

Now to all you kids out there: you should never drink and derive. A theorem you prove after a couple of beers usually falls apart when you sober up. But this time it turns out I was right—and I totally forgot about it until I got Luca’s email.

I never admitted this to Luca but did give him permission to include it in his paper with Andreev, Clementi, and Rolim. And they did.

However, Lautemann’s proof doesn’t tell us anything about Promise-ZPP, so that problem remains open. Go ahead, read Bill’s column, and give it a try. If you drink a couple of Warsteiners along the way, it may not help you prove the theorem—but at least you’ll enjoy some good beer.

Complexity Year in Review

Back in the day (circa 1989) we studied locally random reductions which would lead to all those exciting interactive proof results. Somehow locally random reductions got rebranded as locally correctable codes and this year's result of the year settled a long-standing open question. 

An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes

Pravesh Kothari and Peter Manohar

Roughly if you want a code where each bit is a linear combination of three other appropriately-chosen random bits with constant error, you're going to need a very long code. More in Quanta. 

Things Bill wanted me to mention in this post: R(5), new Mersenne prime, Busy Beaver, Vazirani's delayed proof, formal verification of the sum-check protocol and AI song generation.

2024 was quite a year, we saw a computational complexity theorist, Avi Wigderson, win the Turing Award and computer scientists win Nobel Prizes in both chemistry and physics. Also some elections, wars and college protests. It's all a prelude to a perfect storm for US higher education with the oncoming trains of the new administration, artificial intelligence, fiscal challenges and the demographic cliff. Hang on tight, it's going to be a bumpy ride.

We remember Rance Cleaveland, Peter Higgs, Thomas Kurtz, Phil Lewis, Steven Rudich, Frank Ryan, Jim Simons, Luca Trevisan, Dominic Welsh and Niklaus Wirth.

We thank all our guest posters and collaborators Eric Allender, Martin Bullinger, Max Burkes, James De Santis, Mohammad Hajiaghayi, Neil Immerman, Valentine Kabanets, Harry Lewis and Larry Washington.

Enjoy the holidays and we'll see you in January. 

Information is Physical?

I've heard a few times recently the phrase "Information only exists in a physical state". It come from the quantum computing world where they claim quantum changes the game when it comes to representing information.

As one who has spent his career studying theoretical information that has never and never will exist in a physical state, how can we reckon with such a statement? For starters let's consider the set of all primes--how does that infinite set exist in our finite world? 

Information is physical but not directly, but rather as its description. We can discuss a computational process or more generally a mathematical model that captures the set of all primes and we can and have store that description physically.

Let's consider a single prime, the recently discovered Mersenne prime \(2^{136279841}-1\). Note how we must describe the number in a very compressed format, certainly not as a collection of \(2^{136279841}-1\) ping pong balls or even \(2^{136279841}-1\) atoms, far more than the roughly \(2^{365}\) atoms in the observable universe.

In a similar fashion, a large language model stores information through its weights--not a direct encoding of the sentences it can generate. 

Now let's think of quantum computing. The quantum algorithm is always classically defined. All the information in quantum states has a classical description. An entangled quantum state may require an exponentially large explicit description, but the algorithm generating it provides a short classical physical description. So if we allow information to only physically represented by its description then it's hard to argue that quantum is somehow special. There are differences to how quantum works but when we try to simplify the message, it can confuse people into thinking quantum is more powerful than it really is.

Random Thoughts on AI (Human Generated)

 (I wrote this post without any AI help. OH- maybe not- I used spellcheck. Does that count? Lance claims he proofread it and found some typos to correct without any AI help.)

Random Thought on AI

I saw a great talk on AI recently by Bill Regli, who works in the field. 

Announcement of the talk: here

Video of the talk:  here

-----------------------------------------------
1) One item Bill R mentioned was that AI requires lots of Energy so
3-mile Island is being reopened. See here.

Later I recalled the song

        The Girl from 3-Mile Island

to the tune of

        The Girl from Ipanema.

The song is in my audio tape collection but that is not useful so I looked for it on the web. The copy on YouTube doesn't work; however, this website of songs about 3-mile island here included it.

In the 1990's I was in charge of the Dept Holiday Entertainment since I have an immense knowledge of, and collection of, novelty songs- many in CS and Math.

Today- My talents are no longer needed as anyone can Google Search and find stuff. I did a blog on that here. I still have SOME advantage since I know what's out there, but not as much. Indeed, AI can even write and sing songs. I blogged about that and pointed to one such song here.

SO, some people's talents and knowledge are becoming obsolete.  On the level of novelty songs I am actually HAPPY that things change- I can access so much stuff I could not before. But humans becoming obsolete is a serious issue of employment and self worth. Far more serious then MACHINES TAKE OVER THE WORLD scenarios.

---------------------------------------------------------
2) When technology made farming jobs go away, manufacturing jobs took their place. That was true in the LONG run, but in the SHORT run there were starving ex-farmers. The same may happen now.

(ADDED LATER; someone emailed me that Machines taking over farming and other things has caused standards of living to go up. YES, I agree- in the LONG run very good, but in the short run people did lose their livelihoods.)

Truck Drivers and Nurses may do better than Accountants and Lawyers:

Self Driving trucks are 10 years away and always will be.
Nurses need to have a bedside manner that AI doesn't (for now?).

One ADVANTAGE of AI is that if it makes white collar workers lose jobs the government might get serious about

Guaranteed Basic Income, and

Univ. Health care

(ADDED LATER: someone emailed me that there GBI is not the way to go. Okay, then I should rephase as when white collar workers lose their jobs then the problem of a social saftey net will suddently become important.) 

Similar: If global warming makes the Cayman Island sink then suddenly Global Warming will be an important problem to solve.

------------------------------------------------
3) An example of AI taking away jobs is the Writers Strike.

OLD WAY: There were 10 people writing Murder She Wrote Scripts.

NEW WAY: AN AI generates a first draft and only needs 2 people to polish it.

KEY: In a murder mystery the guilty person is an innocuous character you saw in the first 10 minutes or a celebrity guest star. Sometimes the innocuous character is the celebrity guest star.

-------------------------------------------------
4) ChatGPT and school and cheating.

Calculator Scenario: We will allow students to use Chat GPT as we now allow calculators. Students are not as good at arithmetic, but we don't care.  Is Chat GPT similar?

Losing battle scenario: Ban Chat GPT

My solution which works--- for now: Ask questions that Chat GPT is not good at, allow chat GPT, insist the students understand their own work, and admit they used it. Works well in Grad courses and even senior courses. Might be hard in a Freshman courses.

Lance's Solution--- Stop giving out grades. See here

----------------------------------------------
5) Bill R said that we will always need humans who are better at judgment.

Maybe a computer has better judgment. I blogged on this here

 --------------------------------------------------
6) I asked two AI people at lunch if the AI revolution is just because of faster computers and hence is somewhat limited. They both said YES.

SO- could it be that we are worrying about nothing?

This also may be an issue with academia: if we hire lots of AI people because it's a hot area, it may cool off soon. Actually I thought the same thing about Quantum Computing, but I was wrong there.

----------------------------------------------
7) LLM's use LOTS of energy. If you get to ask one How do we solve global warming? they might say

First step: Turn me off!

----------------------------------------------
8) Scott did a great  blog post about the ways AI could go. See here.

--------------------------------
9) I recently emailed Lance a math question.

He emailed me the answer 5 minutes later.

I emailed that I was impressed

He emailed that he just asked  Chat GPT. He had not meant to fool me, he just assumed I would assume that. Like if you asked me what 13498*11991 was and I answered quickly you would assume I used a calculator. And if there is a complicated word in this post that is spelled correctly then you would assume I used spellcheck - and there is no embarrassment in that.

--------------------------------
10) If a painting is done with AI does any human get credit for it?

I always thought that people who forge paintings that look JUST LIKE (say) a van Gogh should be able to be honest about what they do and get good money since it LOOKS like a van Gogh who cares that it is NOT a van Gogh.  Same with AI- we should not care that a human was not involved.

IF an AI finds a cure for cancer, Great!

If an AI can write a TV series better than the human writers, Great!

--------------------------------------------------------
11) AI will force us to make moral choices. Here is a horrifying scenario:

Alice buys a self-driving car and is given some options, essentially the trolley problem:

If your car has to choose who to run over, what do you choose?

You have the option of picking by race, gender, age, who is better dressed, anything you want.

-------------------------------------------------------
12) Climate Change has become a political problem in that

Democrats think it IS a problem
Rep think it is NOT a problem

Which is a shame since free-market solutions that would normally appeal to Reps are not being done (e.g., a Carbon Tax). Indeed, we are doing the opposite- some states impose a tax on Hybrid cars

SO- how will AI go with politics? Scenarios

a) Dems are for regulation, Reps are against it. Elon Musk worries about AI and he is a powerful Rep so this might not happen.  Then again, he supports Reps, many of whom have made E-cars in their states harder to get or own.

(ADDED LATER: I originally said states had BANNED e-cars. A commenter inquired which states did this so I looked it up. NONE so I ammended the post. Some states are making it harder to have an E-car:

Extra fees for owning an E-car. See here. The reasonaing given is that E-Cars don't pay gas taxes. While that is true, I don't really buy that- republicans seem to be agains ALL taxes EXCEPT thoseon E-cars (and lately tarrifs).

Want to phasa out E-cars: see here

Right now it is illegal to sell cars directly to customers- must go to dealers. This has nothing to do with e-cars but is clearly an idiotic law. E-cars are trying to get around it, and there is pushback on that, see here.

)

 
b) AI-doomsayers want more regulation, AI-awesomers do not, and this cuts across party lines.

c) We will ignore the issue until it's too late.

If I was a betting man ...

----------------------------------------------------------
13) International cooperation on being careful with AI. Good luck with that.

My cynical view: International Treaties only work when there is nothing at stake

The Chem Weapons ban works because they are hard to use anyway.

The treaty on exploring Antarctica was working until people found stuff there they wanted. It is now falling apart

It's Time to Stop Using Grades

We use grades to evaluate students and motivate them to learn. That works as long as grades remain a reasonably good measure of how well the student understands the material in a class. But Goodhart's law, "When a measure becomes a target, it ceases to be a good measure," cannot escape even this most basic of academic measurements. Grades become irrelevant or even worse, counterproductive, as chasing grades may undermine a student's ability to master the material. So perhaps it is time to retire the measure.

Grading became a weaker measure due to grade inflation and academic dishonesty. Let's do a short dive into both of these areas.

The average grade has increased about a full grade level since I went to college in the '80s, and now more than half of all grades given are A's. As college tuition increased, students started thinking of college more transactionally, expecting more from their college experience while putting less effort into classes. Administrators put more weight on student course surveys for faculty evaluation, and the easiest way to improve scores is to give higher grades. And repeat.

If everyone gets an A, no one gets an A. It just becomes harder to distinguish the strong students from the merely good.

Academic dishonesty goes back to the beginning of academics but has advanced dramatically with technology. In my fraternity, we had filing cabinets full of old homework and exams ostensibly to use as study guides. However, if a professor reused questions from year to year, one could gain an unfair advantage.

With the growth of the Internet, Chegg, and more recently large-language models, those looking for an edge never had it so good. ChatGPT-4o1 can answer nearly any undergraduate exam question in any field—it even got an easy A when I tested it with one of my undergraduate theory of computing finals.

AI becomes like steroids: those who don't use it find themselves at a disadvantage. If a pretty good student sees their peers using LLMs, they'll start using them as well, initially just as a learning aid. But there's a very fine line between using AI as a study guide and using AI to give you the answers. Many fall down a slippery slope, and this starts to undermine the mastery that comes with tackling problems on your own.

We can try and counter all this by returning to harsher grading and more heavily weighting in-person, no-tech exams, but these approaches cause other problems. Already we see companies and graduate schools devalue grades and focus on projects and research instead.

So let's acknowledge this endgame and just eliminate grades, maybe keeping only Pass and Fail for those who don't even show up. The ones who want to master the material can focus on doing so. Others can concentrate on working on projects. Still others can earn their way to a degree with little effort but also with little reward.

My comments on Lance's Favorite Theorems

In Lance's last post (see here) he listed his favorite theorems from 1965 to 2024.
There are roughly 60 Theorems. I mostly agree with his choices and omissions. I will point out where I don't.

I could make a comment on every single entry; however, that would be madness! Madness I say!

Instead, here are some random thoughts.  (Is that Random as in Random Restriction or Random as in Random Access Machine?  I leave that an exercise for the reader.)

1) 1965-1974

MANY BASIC RESULT WITH EASY PROOFS.
EXAMPLE:
The Cook-Levin Theorem. P, NP, and SAT is NPC

ANSWERS A QUESTION:
Ladner: Answers a very important question: YES, if P NE NP there are
intermediary sets. The set is constructed for the sole point of not being in P or NPC. Graph Isom and Factoring are natural candidates for being intermediary.

SEEMS TO HAVE BEEN FORGOTTEN:
Blum: Abstract Complexity Theory. Seems to not be taught anymore. I give a corollary for our young readers who might not know it:

There is a decidable set A such that If A is in DTIME(T(n)) then A is in DTIME((log T(n)). Hence A cannot be assigned a complexity. (The set A is constructed for the sole point of having this property. There are no natural examples or even candidates for sets that have this behavior.)

I might disagree with putting this on the list. It has not stood the test of time; however, it still seems important. 

II) 1975-1984.

This may be my favorite decade on the list; however, its been said
that everyone thinks that the best music was when they were a teenager.

EXAMPLES:

INTERESTING THEOREMS WITH INTERESTING PROOFS:
Everything on the list is in this category but I pick out three:

Baker-Gill-Solovay Oracles: The basic paper for my thesis work.

Furst-Saxe-Sipser Parity is not in constant depth.  A meaningful lower bound on a natural problem! Motivated by an Oracle open question (Sep PH from PSPACE) however, circuit complexity quickly became a field onto itself.  What is more interesting the circuit lower bound or the oracle-corollary? I would vote for the circuit lower bound. The issue was discussed here.

Valiant-Permanent. Perm is #P-complete is a theorem I've learned and forgotten many times. Scott much later gave a proof that may be more intuitive for some people (I am not one of them) see here.  The only theorem I've learned-and-forgotten more is the Hales-Jewitt Theorem.

 
III) 1985-1994.

A Decade of Surprises!

Barrington: Branching programs more powerful than we thought!

Toda: #P is more powerful then we thought!

LFKN: IP is more powerful than we thought! Bonus: used non-rel methods! (This result was not on the list but would have been if anybody except L or F or K or N had written the list.)

Nisan: Randomization is less powerful than we thought!

Lance did not have Factoring in Quantum P on the list for 1985-1994. It came out in 1994 towards the end of the year so it ended up missing both the 1985-1994 list and the 1995-2004 list. Reminds me of the Betty White awards, see here.  I do not think we disagree on the importance and merit of the result, though we disagree about altering the past- I would have included it in the post he did recently and explain that it was a late add to an old list.

IV) 1995-2004.

In 1990 a theorist told me that he could teach EVERYTHING known in complexity theory in a year-long graduate course.  Even then, that was not quite right, and may have really meant he could teach everything he thought was important. By 1995 this was no longer true. The PCP result alone would take a few months.

Theory begins to get really hard. Most of the papers before 1992 I have read and understood. Most of the papers after 1992 I have not, though I know what's in them. Sometimes not even that!

PCP: Many problems are hard to approximate.  Good to know, bad that its true. Proofs are hard!

Raz's Parallel Repetition: Really useful in later non-approx results (my favorite: Set Cover Lower bounds, see this survey here) but also Really Hard to read.

Most of the other papers are also hard and important.

AKS- Primality in P- not that hard. Indeed, surprising that it was not proven until 2002.

Lance did not include the work on Natural Proofs by Razborov and Rudich. He says why in a blog post here. I disagree with him- I would have put it in a top theorems list.

VI) 2005-2014.

Some upper bounds and some lower bounds. By now it was hard to have a surprising result since our intuitions were not so firm as to be surprised. (There is one exception in the 2015-2024 list.)

Reingold-Undirected Connectivity in Log Space: great result! I wish the proof was easier. I think people thought this would be true.

Lots of interesting lower bounds: Nash Equilibrium, Unique Game Conj, new PCP proof. None of which was surprising, though perhaps that we could proof things about these concepts is surprising.

JJUW-QIP=PSPACE. Really! I was shocked to find out that was true. No, I wasn't. I didn't understand QIP well enough. Was this surprising or not? Was the fact that this could be proven surprising or not?

VII) 2015-2024.

No real theme here though they all have hard proofs. I discuss a few.

Babai-Graph Isomorphism is the only result in this decade that I can explain to Darling. And she has a Masters Degree in SE so she knows stuff. (I recently told her the result that for all 2-colorings of R^6 there is a mono unit square  (see here). She was unimpressed.)

BZ- Dichotomy: Excellent result and explains the lack of natural intermediary problems.

CZ-Extracting Ramsey Graphs: An example of TCS helping to prove a result in math, though it also shows that the border between the two is thin. Obviously a favorite of mine.

JNVWY- MIP* = RE. This surprised people, including me.

Favorite Theorems: The Complete List

Now in one place all of my sixty favorite theorems from the six decades of computational complexity (1965-2024).

2015-2024

• Graph Isomorphism (Babai)
• Sensitivity (Huang)
• Quantum Provers (Ji-Natarajan-Vidick-Wright-Yuen)
• Dichotomy (Bulatov, Zhuk)
• Algebraic Circuits (Limaye-Srinivasan-Tavenas)
• Extracting Ramsey Graphs (Chattopadhyay-Zuckerman)
• Random Oracles (Håstad-Rossman-Servedio-Tan)
• Parity Games (Calude-Jain-Khoussainov-Li-Stephan)
• Gradient Descent (Fearnley-Goldberg-Hollender-Savani)
• Learning from Natural Proofs (Carmosino-Impagliazzo-Kabanets-Kolokolova)

2005-2014

• Undirected Connectivity in Log Space (Reingold)
• Optimal Inapproximability for Max-Cut (Khot-Kindler-Mossel-O'Donnell, Mossel-O'Donnell-Oleszkiewicz)
• Limitations of linear programming (Fiorini-Massar-Pokutta-Tiwary-de Wolf, Rothvoß)
• Complexity of Nash Equilibrium (Daskalakis-Goldberg-Papadimitriou, Chen-Deng)
• Combinatorial Proof of PCP Theorem (Dinur)
• Constructive Proof of the Lovász Local Lemma (Moser)
• Polylogarithmic independence fools AC⁰ (Braverman)
• QIP = PSPACE (Jain-Ji-Upadhyay-Watrous)
• Lower Bounds on Multilinear Formulas (Raz)
• NEXP not in ACC⁰ (Williams)

1995-2004

• Derandomization (Impagliazzo-Wigderson)
• Primality (Agrawal-Kayal-Saxena)
• Probabilistically Checkable Proofs (Håstad)
• Connections (Trevisan)
• Superlinear Bounds on Branching Programs (Ajtai)
• Parallel Repetition (Raz)
• List Decoding (Sudan)
• Learning Circuits (Bshouty-Cleve-Gavaldà-Kannan-Tamon)
• Quantum Lower Bounds (Ambainis)
• Derandomizing Space (Saks-Zhou)

1985-1994

To mark my first decade in computational complexity during my pre-blog days, I chose my first set of favorite theorems from that time period for an invited talk and paper (PDF) at the 1994 Foundations of Software Technology and Theoretical Computer Science (FST&TCS) conference in Madras (now Chennai), India. The links below go to the papers directly, except for Szelepcsényi’s, which I can't find online.

• Branching Programs (Barrington)
• Bounded-Depth Circuits (Håstad)
• Monotone Circuits (Razborov)
• Nondeterministic Space (Immerman, Szelepcsényi)
• Cryptographic Assumptions (Impagliazzo-Levin-Luby)
• Isomorphism Conjecture (Ogihara-Watanabe)
• Simulating Randomness (Nisan)
• Counting Complexity (Toda)
• Counting Classes (Beigel-Reingold-Spielman)
• Interactive Proof Systems (Arora-Lund-Motwani-Sudan-Szegedy)

1975-1984 (From 2006)

• Alternation (Chandra-Kozen-Stockmeyer)
• Relativization (Baker-Gill-Solovay)
• Small Sets (Mahaney)
• Primality Algorithms (Solovay-Strassen, Miller, Rabin)
• Probabilistic Complexity (Gill, Sipser)
• The Permanent (Valiant)
• Unique Witnesses (Valiant-Vazirani)
• Parity (Furst-Saxe-Sipser, Ajtai)
• The Yao Principle (Yao)
• Nonuniform Complexity (Karp-Lipton)

1965-1974 (From 2005)

• The Seminal Paper (Hartmanis-Stearns)
• Efficient Computation (Cobham-Edmonds)
• NP-Completeness (Cook, Levin)
• Combinatorial NP-Complete Problems (Karp)
• The Polynomial-Time Hierarchy (Meyer-Stockmeyer)
• P = NP for Space (Savitch)
• Abstract Complexity (Blum)
• NP-Incomplete Sets (Ladner)
• Logical Characterization of NP (Fagin)
• Defining the Future (Cook-Reckhow)

Will I do this again in ten years when I'm 70? Come back in 2034 and find out.

Conway's Trick for Divisibility. Asking its complexity is an odd question.

 (I got this material from a nice article by Arthur Benjamin here.)

 Conway suggested the following trick to determine if a number is divisible by each of the following: 

2,3,5,7,11,17,19,31

Note that

\( 152=2^3\times 19\)

\(153 =3^2 \times 17\)

\(154=2  \times 7 \times 11\)

\(155=5 \times 31\)

\(156=2^2  \times 13 \)

Here is the Div trick:

a) Input N

b) Divide N by 150 and note the remainder. So

 N=150q+r

r=N-150q 

Subtract q from r a few times: 

Note that

r-q = N-150q-q = N-151q

r-2q=N-152q

AH HA!- if 19 divides r-2q then 19 divides N. So divide r-2q by 19. (Note that r-2q is much smaller than N. Smaller enough to make this technique feasible? That is the question!)

r-3q=N-153q.

AH HA!- if 17 divides r-3q then 17 divides N. So Divide r-3q by 17.

r-4q=N-154q

AH HA- if 11 divides r-4q then 7 divides N. So Divide r-4q by7.

r-5q=N-155q

AH HA- if 31 divides r-5q then 31 divides N. So Divide r-5q by 31.

r-6q=N-156q

AH HA- if 13 divides r-6q then 13 divides N. So Divide r-6q by 13. 

Complexity with 1 division, 6 subtractions and 6 divisions of small numbers (r\le 150 and q\le N/150)

you find out the divisibility by 7,13,17,19,31.  For 2,3,5,11 there are well known tricks to use. OR you can test those as well by doing (for example) dividing r-4q=r-154 by 11.

Some Points

1) Is this method faster than just dividing N by the numbers (and using tricks for 2,3,5,11)? You would need to get into addition being faster than division, and look at the size of the numbers.

2) Is this method practical? For hand calculation YES. For computers it would be easy to code up but the main question of this post: is it better than just dividing N by numbers.

3) Are there larger runs of numbers that pick up more divisors? Yes. We present one. The order will look funny but we explain it later.

\(2000=2^4 \times 5^3 \) (you could skip this one, though dividing by 2000 is easier than by 2001)

\(2001=23\times 29\times 3\) (would divide N-2q by both 23 and 29)

\(2002=7\times 11\times 13\times 2\)

\(1998=37\times 54\)

\(2006=17\times 29\times 2\)

\(2010=67\times 30\)

\(2014=19\times 53\times 2\)

\(2013=61\times 33\)

\(2015=31\times 65\)

\(2009=41\times 49\)

\(2021=43\times 47\)

The order was suggested by Conway so that algorithm at every step adds or subtracts one of q, 2q, 4q, 6q, 8q, 12q. So after you get q you can compute these values. 

I leave it to the reader to count the number of divisions, subtractions, and size of the numbers involved.

4) For cracking RSA this technique is useless since RSA uses numbers of the form pq where p and q are large primes. For factoring randomly generated numbers I would be curious if this method is better than just dividing by numbers.

5) Project: find other sequences like those above that cover more prime factors.

We Will All Write Like AI

Will our writing all converge to a generic AI style? 

Let's take a quick detour into LaTeX. Back in the late '80s, before LaTeX was the standard, there was TeX—a system with no default formatting, which meant everyone had their own unique style for papers. Then LaTeX arrived, and suddenly all our papers looked polished and professional. But the catch was, LaTeX only got you about 80% of the way there. The original manual even mentioned that you needed to add some extra TeX commands to really finish the job. Most of us didn’t bother, though, and soon all our papers had that same uniform look. It was efficient, and it was good enough. Microsoft Word ended up doing the same thing for everyone else—you could tweak it to be different, sure, but most people didn’t. It turns out most of us are just fine with "good enough."

I generally don't like to use large language models to write for me. But I do use them to refine my work, to catch errors or suggest improvements. The thing is, AI likes to take what I write and make it sound smoother, and I often think, "Wow, that really does sound better." But here’s the tricky part: it might be better, but it’s not mine. It’s the AI's voice. And still, if the stakes aren’t too high, sometimes I let the AI’s version slide. That’s the start of a slippery slope. Before you know it, we’re all letting AI make our writing a bit more generic, a bit more uniform. And eventually, we end up writing to match the AI’s preferred style.

For this blog post, I didn’t resist at all. Could you tell this is ChatGPT's style?

For what d is the following true: For all 2-colorings of \(R^d\) has a mono unit square (Answering(?) the Question)

 In my last post (see here) I invited you to work on the following question:

Find a \(d\) such that

--There is a 2-coloring of \(R^d\) with no mono unit square.

--For all 2-colorings of \(R^{d+1}\) there is a mono unit square. 

Actually I should have phrased my question as What do we know about d?  

Here is what we know

a) \(d \ge 2\).  There is a 2-coloring of  \(R^2\) with no mono unit square. This is easy and I leave to you. 

b) \(d\le 5\). For all 2-colorings of \(R^6\) there is a mono unit square. I will give pointers to the relevant papers and to my slides later in this post.

c) \(d\le 4\). For all 2-colorings of \(R^5\) there is a mono unit square. This is by an observation about the proof for \(R^6\). It will be in the slides about \(R^6\).

d) \(d\le 3\). This is in a paper that the reader Dom emailed me a pointer to. Dom is better at Google Search than I am. The link is here.

MY SLIDES:

\(K_6\) is the complete graph on 6 vertices. We will be looking at 2-colorings of its edges

\(C_4\) is the cycle on 4 vertices. A mono \(C_4\) has all four edges the same color.

We need a result by Chvtal and Harary in this paper here.

Lemma: For all 2-colorings of the edges of \(K_6\) there is a mono \(C_4\).

The proof appears both in their paper,  here, and on slides I wrote here. 

Stefan Burr used this to prove the following theorem.

Thm: For all 2-colorings of \(R^6\) there is a mono unit square. 

The proof was appears (with credit given to Stefan Burr) in a paper by Erdos, Graham, Montgomery, Rothchild, Spencer, Straus, here, and on slides I wrote here.

Random Points

1) It is open what happens in \(R^3\). 

2) The proof for \(R^6\) uses very little geometry. Dom had a proof for \(R^6\) in a comment on my last post that used geometry. The proof for \(R^4\) uses geometry. 

3) An ill-defined open question: Find a proof that every 2-coloring of \(R^4\) has a mono unit square that does not use that much geometry and so I can make slides about it more easily.

For what d is the following true: for all 2-colorings of \(R^d\) there is a mono unit square (Asking the Question)

 In this post I give a question for you to think about. 

My next post will have the answer and the proof. 

1) The following are known and I have a set of slides about it here

a) For all 2-colorings of \(R^2\) there exists two points an inch apart that are the same color. (You can do this one.)

b) For all 3-colorings of \(R^2\) there exists two points an inch apart that are the same color. (You can do this one.)

c) For all 4-colorings of  \(R^2\) there exists two points an inch apart that are the same color. (You cannot do this one.) 

2) SO, lets look at other shapes

A unit square is  square with all sides of length 1.

Given a coloring of \(R^d\) a mono unit square is a unit square with all four corners the same color. 

a) There is a 2-coloring of \(R^2\) with no mono unit square. (You can do this one.)

b) What is the value of d such that 

-- There is a 2-coloring of  \(R^d\) with no mono unit square.

-- For all 2-colorings of \(R^{d+1}\) there is a mono unit square. 

My next post will tell you what is known about this problem.

Until then, you are invited to think about it and see what you can find out. Perhaps you will get a better result then what is known since you are untainted by conventional thinking. Perhaps not. 

Feel free to leave comments. However, if you don't want any hints then do not read the comments.