The Customers of the Academy

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

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

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

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

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

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

The New Lower Bound on Busy Beaver of 6.

 We denote the busy beaver function by BB.

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

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

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

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

What about BB(6)?

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

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

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

SO, what to make of all this?

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

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

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

4) Why the interest in BB? Some speculation:

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

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

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

d) Results generate interest, and interest generates results.

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

A Professor Again

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

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

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

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

The next chapter begins...

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

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

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

NEW

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

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

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

Kudos to them!

OLD:

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

My students would ask me

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

The Distribution of Prime Numbers: A Geometrical Perspective

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

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

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

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

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

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

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

Prime Walk

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

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

Observing the PW in action raises numerous questions.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ANYWAY back to Sarah and Wheel of Fortune: The statement

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

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

Who does not want to be a millionaire? 

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

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

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

Fulbright Memories

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

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

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

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

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

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

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

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

I doubt it 

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

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

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

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

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

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

a) The name of the team.

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