The Calculator Transition

There's a scene in Apollo 13 where Jim Lovell, played by Tom Hanks, asks Houston control to check his calculations, which they do using a slide rule. 

My father told me that when he was in college (1950s) that engineers measured their technical prowess in how many digits of accuracy they could get off a slide rule.

The actual Apollo 13 incident took place in 1970. A year later Bowmar/Ali released the 901B, nicknamed the Bowmar Brain, for about $240. 

The following year came the HP-35, the first successful handheld scientific calculator that put slide rules out to pasture.

A couple of years later I asked for a calculator for my birthday (the math nerd I was). I insisted on it having a memory button that could remember one number so I could do more complex calculations. The one I got even had a square root button!

By the time I got to high school at the end of the decade, we all had handheld calculators. My AP chemistry teacher still insisted on teaching us how to use a slide rule. For fun, I decided to use my father's slide rule on a chemistry exam. That was a mistake for two reasons.

1. I did not have the "technical prowess" to get many digits of accuracy. So especially after a few calculations, my numbers were way off. The teacher took pity on me and gave me credit because I had the formulas right.
2. I spent too much time doing the calculations where everyone else just punched numbers into their calculator and didn't finish all the problems. 

Maybe with more experience I could have handled both issues better, but that was the last time I used the slide rule for any important calculations. School children still learned how to add and multiply, but I'm not sure my kids can do long division. Certainly I was the last generation to learn how to do square roots by hand.

Is there an AI lesson in all this? We went from slide rules in mission control to calculators in high school in under a decade. No one suggests we go back to slide rules, and using a slide rule is now a lost art. Civilization survived.

But there's a bigger story. The slide rule and calculator took care of the routine math, but the teacher graded me on my knowing the Chemistry. AI Can now do the chemistry. And what's left after that?

Centaur Math

In the past, new PhD students would ask how they could succeed when they had to compete with the likes of say, Richard Karp or Avi Wigderson. I would say Karp and Wigderson have limited bandwidth and you can work on problems they don't work on, or think deeper about a problem than Karp or Wigderson has time to.

Now we get the same question but with names like Claude and ChatGPT and it's hard to make the same bandwidth argument. What do we tell them as we get closer to Math AGI?

What even is Math AGI? It's not that every math problem gets solved. I don't expect P vs NP to be solved anytime soon. It would require a completely new approach, and AI doesn't (yet) think outside the box, though it has a very large box.

Math AGI means that with rare exceptions, if AI can't solve a math problem then no human could either. If you need a proof, you'd have to pay for more cycles, or wait for the next new and improved model. Like the Turing test, we'll only truly realize we've reached Math AGI once we've gone well past it.

We haven't reached Math AGI yet and we may never fully get there. We have entered the world of Centaur Math. Mathematicians can still prove theorems AI can't, AI can prove some theorems mathematicians haven't yet proven, but the real strength comes with mathematicians and AI working together. Working with AI today is like having a pretty good PhD student, who has a huge broad base knowledge of mathematics, is a whiz at coding, but still needs direction, encouragement and verification.

Chess had a short centaur moment when humans and AI working together could beat the best human players and AI programs. Now, any human would play worse not following what AI says. Nevertheless, we still enjoy watching two sub-AI humans play chess against each other. I doubt the same would hold for sub-AI mathematicians.

So what do we tell the students? If you love math, do math. Embrace AI, use it to go further, not as a crutch. Challenge yourself and remain agile so you can find success whatever the future might hand us. And remember, math is not ultimately about the theorems we prove but how we understand the principles behind them, and that's a human endeavor not a machine one.

IIT is the canary in the coalmine (Do our younger readers know what that means? Do we have younger readers?)

Lance has posted about his, and around 160 others, being laid off from IIT here.(IIT stands for Illinois Institute of Technology which is where Lance was employed.)

Hence I looked into what is happening at IIT to see if there is a lesson for us all.

I) I wondered why IIT had declining enrollment. I wondered which of the two reasons below  was the issue (and of course there are other reasons). 

--The enrollment cliff.  (See here)

--International students have declined in number. Why? (1) Having getting student visas, (2)  They think they are not welcome here (3) Schools in their home country getting better. Note that I am just guessing.

Rather than speculate I asked ChatGPT for the data on both enrollment and on international enrollment from 2015 to 2025. Here is the data: here.

a) 2015 had an enrollment of 7792. It went down in 2020 (COVID?) but then came up again and it was 8838 in 2024.  In all the years for which there is data international students were about half of the students.

b) 2024: 8838 students, of which 4596-International (52%), 4242-Americans

   2025: 7502 students, of which 2141-International (42%), 5361-Americans

So it looks like the enrollment cliff was not a problem since more Americans came, but the decline in international students is a problem.

I think that international students pay more, so their decline creates more of a financial pinch.

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

II) I wondered if other schools had massive layoffs so  I asked Google AI what other schools had laid off more than 30 professors in the last two years. It had an issue with that since schools combine faculty and staff.  Even so, the main fact is that (a) it is happening at other schools, and (b) 160 is more than usual. 

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

III) Challenges facing Universities

a) The enrollment cliff. This will be a real problem for small schools.  For big schools it may be an opportunity to have smaller classes.  This issue cannot be stopped.

b) Less international students means less money. This may change since this or a later administration may change the rules. However, changing the rules might not help much since other countries have fine schools and international students may feel they are not welcome here.

c) Grants are drying up. Again, this may change.

d) AI and cheating. This may make us rethink the entire point of education.

e) Does college exist to create an educated public who can make decisions and vote intelligently, or are colleges vocational? It's getting harder to do both.

f) Fads: The hot topics in CS now are Quantum, ML, and Quantum ML. What will they be in 10 years?How do we adjust? Do other fields have this problem? ML (or more broadly AI) is hot in that students want to take it because it both sounds interesting and sounds employable. Quantum is hot for grant money and some students think its going to be cool. (In this context `Hot' and `Cool' are not opposites.) 

g) Tuition keeps going up. The business model may be broken.

h) A while back online education seemed like it might be an alternative for some students (MOOCS were hot). That hasn't happened yet but it might.

i) This is a far bigger subject than the points above. Maybe Lance can write a book on the topic now that he has some free time.

Unexpected Unemployment

Enjoying Idaho while ignoring Illinois

Today is the first day of my life that I am unemployed. And not by choice.

As I mentioned on LinkedIn last week, me and about 160 of my colleagues, staff and faculty, untenured and tenured, lost our positions at Illinois Tech after they declared "financial exigency" which allows them to eliminate tenured positions. I'll use this post to tell my story, but keep in mind there are 160 other ones.

The president announced that he would be asking the board to declare financial exigency in mid-July so we knew layoffs were coming but not when. On July 25th, we left for a planned 12-day vacation to Idaho. Why Idaho? It's my fiftieth state, so my wife and I decided to make a vacation of it. We saw Boise, canyons, craters, mountains, lakes. We were in Twin Falls three days before a mass shooting but that's a different story.

Usually I avoid reading work emails on vacation but decided I probably should this time. And on day four of vacation, I got an email invite to a meeting with the Vice-Provost of Faculty Affairs and an HR representative titled "Organizational Update" and I knew my fate was sealed. By the next day I was tired thinking about it and just decided to enjoy the rest of the vacation and deal with everything when I got back last Thursday. It might have been better if I simply didn't read email like usual.

It really hit me as I started to pack up my office Monday, for the first time with no office on the other side. Monday was also the first day of orientation week and a group of new students walked by as I was packing boxes into my car, though I don't think they noticed.

Illinois Tech got hit hard by a large drop in foreign graduate enrollment due to changing visa requirements, general anti-US sentiment, more opportunities in other countries and a weaker job market for graduating Masters students partly due to artificial intelligence. Universities face challenges beyond international students including Baumol's disease, administrative bloat to meet expanding regulations, the demographic cliff, reduced grant funding, and less support of universities by the public and both political parties, and AI changing how and why we teach. Illinois Tech is one of the first tech research schools to eliminate tenured roles, but it won't be the last.

I'll be okay but many of the other faculty could really use another position, in some cases so they can stay in the US. If you have opportunities for faculty in any discipline, let me know and I'll pass it along.

Math Concepts With Funny Names

(Some of this came from a Reddit post  I read, and some of  the comments on it.) 

Here are theorems with names that I think are funny or unusual. The names are also pointers to the Wikipedia entry on them or some other source.

The Chicken McNugget Theorem

The Ham Sandwich Theorem

The Hairy Ball Theorem

Freshman Dream

The law of the unconscious statistician

The Homicidal Chauffeur Problem

The Pigeonhole Principle (We are so used to this we no longer find it funny, but it is.) 

Eventown and Oddtown 

I am sure there are more and I invite you to comment BUT there are some issues

1) What is funny?

2) I want math concepts that are known. As a counterexample, if Lance proved a theorem and called it the Funkytown Theorem just to get on this list then I'd be surprised. It also would not count. 

3) The name has to be some relevance to the concept. 

And I now list two titles of papers that I find funny. Note that what I write IS the title, even though the first one is an odd title and the second one really does not look like a title.

A minus sign that used to annoy me but now I know why it is there (two constructions of the Jones polynomial)

Some title containing the words "homotopy" and "symplectic", e.g., this one

A problematic category on Jeopardy Raises a Good Question

I was watching a Jeopardy from 2004 (The Game Show Channel is rerunning Ken Jennings streak) and the following question raises a good question.

The contestants where Ken, Jerry, Jennifer.

In Double Jeopardy there was a category  Biblical Name The Same.

The clue was three last names (e.g., Driver, Sandler, West) and the correct response is a biblical name that is the first name of people with that last name (Adam: Adam Driver, Adam Sandler, Adam West).

What happened with Biblical Name The Same for 1200 shows an issue with the question.

Clue: Stewart, Graham, Grimes.

Jerry said  James. This was ruled incorrect.

Ken said Martha. This is correct.

Why is Martha Correct:

Martha Stewart is a well known TV personality focusing on home and hospitality.

Martha Graham was an American modern dancer, teacher, and choreographer (she died in 1991).

Martha Grimes is an American writer of detective fiction.

Frankly, the only one I had heard of was Martha Stewart.

But later they decided Jerry was right and gave him the points (Ken kept his points).  Here was Jerry's argument:

James Stewart was a well known  actor (died in 1997).

James Graham- the show said he was a British General in the 17th Century. I (Bill, not Jerry) looked up James Graham on Wikipedia- there are a lot of them. Four were under the category Military.  Of those, two were British. Neither was a General. One lived 1649-1730 so it may be him.

James Grimes-the show said he was a Senator involved with the impeachment of Andrew Johnson.  I (Bill) looked it up- Grimes was a Republican and it was his party that was trying to impeach, but he (and six other Republicans) broke rank and voted for acquittal. He and the others were bothered that the process had been manipulated. There were rumors they were bribed with patronage jobs or cash though I could not tell if this was true.

The category is problematic.

It is implicit that the three people have to be famous.

This raises two questions and a challenge

Two Questions: What is fame?  How do you measure it? 

Challenges: Let x,y \(\ge\) 2. 

 Find x  last names L1,...Lx  such that there are y first names F1,...,Fy

with F1-L1, F1-L2,...,F1-Lx famous AND

        F2-L1, F2-L2,..., F2-Lx famous AND

DOT DOT DOT

        Fy-L1, Fy-L2,...,Fy-Lx famous.

For the example above x=3 and y=2. You either try the easier case x=2, y=2, or a harder case like x=3, y=3. 

Would Erdos have been happy with the resolution of the Erdos Unit Distance Problem? How to find out?

Let's say there is a statement in math T that you wonder whether it's true or false.  You may even make a conjecture of which way it goes. Do you have a rooting interest?  I may think T is true, but if someone proves T or proves NOT(T) my main concerns are (1) can I understand the proof ? (2) is the proof interesting?

Paul Erdos posed the sum-product conjecture which was recently proven false (by humans!).  I blogged about it here.

I wondered whether Paul Erdos would be happy with how it turned out. So I did the obvious thing: I asked Google AI

       Would Erdos have liked the solution to the sum-product conjecture?

Here is what it said:

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

Paul Erdős would likely have had mixed feelings about the final resolution of the sum-product conjecture, but ultimately thrilled by the breakthroughs.

The original conjecture stated that for any finite set \(A\) of real numbers, either the sumset \(A+A\) or the product set \(AA\) must be large, meaning \(\max(\vert{}A+A\vert{}, \vert{}AA\vert{}) \approx \vert{}A\vert{}^{2-o(1)}\).

Here is how he would have reacted to the different aspects of the solution:

a) Shock and Disbelief at the Disproof: Erdős believed so strongly in his 1974 conjecture that he originally offered a \(\$500\) reward for its solution. He would likely be shocked to learn that it is actually false for real numbers.

BILL COMMENT: OFFERING $500 MIGHT BE BECAUSE HE THOUGHT IT WAS IMPORTANT, NOT THAT HE THOUGHT IT WAS TRUE. DID HE ALSO OFFER $500 TO SHOW IT'S FALSE?

b) Excitement Over the Methods: The disproof of the conjecture relies on sophisticated constructions using high-degree number fields. Erdős loved deep, elegant connections between combinatorics and number theory, and would have admired the clever ways algebraic integers were used to cheat both addition and multiplication.

c) Joy in the Breakthrough: Erdős famously loved to "solve problems" and advance mathematics above all else.  Because the disproof opens entirely new avenues in additive combinatorics and number theory, he would be thrilled with the mathematical progress it generated.

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

Some randomized points:

0) Has anyone ever been mad because their conjecture was PROVEN false? Or even proven true? 

One of the comments says that Pythagoras didn't like the sqrt(2) since it was not rational, but this is a myth. See the book The Cult of Pythagoras or my review of it here.

1) What Google AI says sounds right to me. Hence I believe it. However, dishonest fortune tellers (are there any honest ones?) will look at your clothes and how you talk and deduce things about you, and feed it back to you. Is Google AI similar?

2) What if I ask Google AI (or Chatty or Claude) a question and the answer does not sound right to me?

If it's a math question I can explore for myself and see what's up (ChatGPT has often been wrong when I ask it obscure things in Ramsey Theory).

If it's a question like How would Paul Erdos Feel About ... then there is no way to check the answer.

3) When I ask AI about history or literature I tend to believe it. Maybe I shouldn't.  It always respects my point of view which it might be wrong to do. For example, I asked Google AI

Why is My Mother the Car a better TV show than The Sopranos?

For a too-respectful response see here

Complexity Class of the Week: \(L_2^P\)

Back in the 90s when I was a young professor at the University of Chicago, we would have a Complexity Class of the Week where I would take some interesting complexity class, write down on a white board everything we knew about it with some open problems and students and faculty would muse over it. When I started the blog in 2002, I took the concept online. 

My first Complexity Class of the Week post covered the class \(S_2^P\). Recently Rahul Santhanam said to me "\(L_2^P\) is the new \(S_2^P\)". So for one week only, I'm bringing back the complexity class of the week to talk about \(L_2^P\), the set of problems reducible to the linear ordering principle. 

Recall the \(S_2^P\) courtroom: a polynomial-time judge, two lawyers submitting written arguments, one arguing the string is in the language, the other arguing it's out, and neither seeing the other's brief. For \(L_2^P\) we add one rule: the judge's rulings must be transitive. Each lawyer submits an argument that the judge can compare in polynomial time, where the judge in his mind ranks all the arguments in a linear order. The best argument wins.

The linear ordering principle states that any total linear order of a finite set has a unique minimum element. Oliver Korten and Toni Pitassi define the Linear Ordering Principle (LOP)  as a total search problem: given a circuit \(C(x,y)\) purporting to compute a linear ordering on \(\{0,1\}^n\), find either the minimum element or a witness that one of the order axioms fails (a violation of antisymmetry or transitivity). \(L_2^P\) is the class of languages polynomial-time Turing reducible to LOP. Korten and Pitassi show polynomial-time many-one, Turing and even \(\mathrm{P^{NP}}\) reductions to LOP all give the same class. Equivalently, \(L\in L_2^P\) if there is a polynomial-time relation \(R\) such that for every \(x\), \(R(x,\cdot,\cdot)\) defines a linear order on polynomially-long strings, and the minimum element begins with a 1 exactly when \(x\in L\). That last formulation makes clear that \(L_2^P\) is just \(S_2^P\) with a transitive referee, so \(L_2^P\subseteq S_2^P\).

Korten and Pitassi show \(\mathrm{P^{NP}}\subseteq L_2^P\subseteq S_2^P\) and \(\mathrm{MA}\subseteq L_2^P\). Edward Hirsch and Ilya Volkovich show  \(\mathrm{P^{prMA}}\subseteq L_2^P\), answering a 2011 question of Venkatesan Chakaravarthy and Sambuddha Roy on whether \(\mathrm{P^{prMA}}\subseteq S_2^P\). MA is the class of two-round interactive proofs where the prover goes first. Promise-MA (prMA) means you need to give the correct answer when the promise holds but can give an arbitrary response when it doesn't.

Since Jin-Yi Cai showed \(S_2^P\subseteq \mathrm{ZPP^{NP}}\), and under standard derandomization assumptions \(\mathrm{P^{NP}}=\mathrm{ZPP^{NP}}\), in the world most of us believe in, \(\mathrm{P^{NP}}= \mathrm{P^{prMA}}=L_2^P=S_2^P=\mathrm{ZPP^{NP}}.\)

Why define the class at all? It came out of the recent breakthroughs on circuit lower bounds. Lijie Chen, Shuichi Hirahara, Zeyong Li and Hanlin Ren showed that \(S_2^E\) requires circuits of near-maximum size \(2^n/n\), by giving a clever algorithm for the Range Avoidance problem: given a circuit mapping \(n\) bits to \(n+1\) bits, find a string outside its range. Korten and Pitassi sharpened their algorithm into the reduction from Range Avoidance to LOP and thus to \(L_2^P\). The payoff: \(L_2^E\) requires \(2^n/n\)-size circuits, and for every fixed \(k\) there is a language in \(L_2^P\) without \(n^k\)-size circuits. In my 2002 post I wrote that "\(S_2^P\) is the smallest class known to have these properties." That's where the quote from Rahul came from.

Karp–Lipton collapses have moved too. Korten and Pitassi asked whether NP in P/poly collapses PH to \(L_2^P\); Hirsch and Volkovich answered yes via \(\mathrm{PH}=\mathrm{P^{prMA}}\subseteq L_2^P\). 

Some of my old work on \(S_2^P\) now moves to \(L_2^P\). With Aduri Pavan and Samik Sengupta, we showed that if \(\mathrm{P}^{\mathrm{NP}[1]} = \mathrm{P}^{\mathrm{NP}[2]}\) then the polynomial-time hierarchy collapses to \(S_2^P\). Vyas Ram Selvam extended that collapse to \(\mathrm{P}_{||}^{\mathrm{NP}[1],\mathrm{MA}[1]}\subseteq \mathrm{P^{prMA}}\subseteq L_2^P\) under the same assumption.

Thirty years ago Yamakami and I constructed a language \(L(G)\in\Sigma_2^{P,G}\cap\Pi_2^{P,G}\) and used it to show generic oracles separate \(\Sigma_2^P\cap\Pi_2^P\) from \(\mathrm{P^{NP}}\). I later pushed \(L(G)\) into \(S_2^{P,G}\) and with a little effort can now show \(L(G)\in L_2^{P,G},\) showing that \(\mathrm{P^{NP}}\subsetneq L_2^P\) relative to generic oracles.

One thing that doesn't carry over: last fall I showed that the search version of \(S_2^P\) is equivalent to  \(\mathrm{TF}\Sigma_2\), a probably larger class, where the search version of \(L_2^P\) is just LOP, computationally equivalent to \(L_2^P\).

Whether  \(L_2^P=S_2^P\) or even \(L_2^P=\mathrm{ZPP^{NP}} \) remains open even in relativized worlds.

For more, read the well-written papers by Korten and Pitassi and Hirsch and Volkovich.