2023 Complexity Year in Review

Result of the year goes to 

Polynomial-Time Pseudodeterministic Construction of Primes
Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren and Rahul Santhanam

An impressive year for complexity and we wrote several theorem posts this year including the one above, new Ramsey bounds, exponential circuit bounds for \(\Sigma_2^E\), inverting compression functions and advances in group isomorphism. 

It's a year dominated by wars, Taylor Swift, ChatGPT and mathematicians Leaning in. The blog word of the year is meta-complexity.

We remember Jimmy Buffett, Martin Davis, Neil Jones, Abraham Lempel, Gordon Moore, Roger Schank, Vera Sós, William Wulf, Jacob Ziv and Dilbert. Happy to forget Ted Kaczynski. 

Thanks to our guest posters Eric Allender, Ravi Boppana, Josh Grochow, and Youming Qiao.

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

Archimedes, Pi, and Pickelball

I typed 

3,1,4,1,5,9 

into OEIS and,  as expected, I found that these are the first few digits of \(\pi\). See here.

I then read on the page:

\(\pi\) is sometimes refereed to a Archimedes constant, because the Greek mathematician computed lower and upper bounds of \(\pi\) by drawing regular polygons inside and outside a circle. 

In my 40 or so years being involved with math, I have never heard \(\pi\) called Archimedes constant. Whats going on here?

(a) The term is STILL in use I just happened to never hear it. I noted in a blog here that I didn't have a single book on trig in my house, so this is plausible.

(b) The term is NOT in use but the person who wrote that entry either is rather old or THOUGHT it was in use or heard it once when he was 10 years old or...

(c) Some weighted sum of (a) and (b) 

I suspect the term is NOT in use anymore. So when was it in use, and when did it fall out of favor? 

More random thoughts

1) I googled why is it called pi but it was auto filled to ask why is it called pickleball. I'll report on both:

pi: It was first called pi  in 1706 by [The Welsh Mathematician] William Jones because pi is the first letter in the Greek word perimitros which means perimeter. (ADDED LATER- the comments say that the question-and-answer are not as simple as this quote would imply. I am sure they are right.) 

Pickleball: This website here says the following. Joel Pritchard invented the game (the story is more complicated than that). With that in mind here is a direct quote:

Okay, now you know how it all started but the question we’re all thinking still remains: why do they call pickleball, well, pickleball? According the to U.S.A. Pickleball Association, the origins of the name differs between different accounts.

Joel Pritchard’s wife, Joan, started to call their game pickleball because “the combination of different sports reminded me of the pickle boat in crew where oarsmen were chosen from the leftovers of other boats.” But according to Barney McCallum, they named the game after Pritchard’s dog, who was (as you might’ve guessed) named Pickles! Despite the sour taste of actual pickles, their dog was sweet and known to run off with the ball while it was still being played!

Depending on who you ask, both accounts of the game’s name may actually be true. At the start, there wasn’t any name for pickleball until an official one was needed when the game started to gain traction. With the laid-back nature of pickleball, it’s only appropriate that it was named in a similar fashion.

Respect

I've generally avoided talking about all the events at college campuses in the last few months that came to a head at the congressional hearings last week that led to the resignation of Penn's president Liz Magill. It's not that I don't have any thoughts to share, rather I have too many that I'm still trying to process. 

I had planned to put them in writing this week but I can't. Not yet.

So one word for this season to hopefully recapture what we've seem to have lost: Respect.

Where do Journals go to Die?

In 2011 I had a post, here, about a real journal called The Antarctica Journal of Mathematics. Note that I put in the link in the last sentence; however, if you go there you will get to a page that IS labelled with the name of that journal, but all of the links on it are either broken or go to a place to sell domain names. I assume the journal is dead, but I can't find any evidence that it was ever alive. When I googled it I got the link above for the first hit and my 2011 blog post for the fourth hit.

On Wikipedia I found a debate about deleting the Wikipedia webpage for it, which I assume won since there is no webpage for it.  Here is that webpage: here.  That page also debates whether the journal was a joke, though they conclude that it was not a joke.

 

If you try to go to The Journal of Combinatorics and Number Theory using that link you will find

a) There is a page, but it says that the  journal is discontinued.

b)  You can click to see the table of contents from Vol 11, No 1 to Vol 12 No. 3.

c)  There is a mechanism to click on stuff and BUY articles from those issues but I do not know if it works, and I am not going to find out.

d) For issues before Vol 11, there is a place to click for prior issues. When you click on it you get to the NOVA publishers webpage but no indication of where to go for prior issues of this particular journal.

e) There is no Wikipedia site for the journal. That might not mean much, there is no Wikipedia site for  Raegan Revord either, and she deserves one (I linked to her IMDB page).

f) Why do I care? Actually, I don't care much. However, I DO have an article in that journal, co-authored with Larry Washington and Sam Zbarsky. It was refereed seriously and we were never asked for money, so (1) its probably not a scam, and (2)  there was some quality control  (or the referee didn't get the memo). It was in Volume 10, No. 1. There is  no way for me to verify that it was ever published. Fortunately I will never have to. Also, the paper does not need to be published to be known since (1) I blogged about it  here and (2)  its on arxiv's here. Someone read it (probably on arxiv) and wrote a followup paper, see here.

 

QUESTIONS

1) Why did The Antarctica Journal of Mathematics die?

2) Why did the Journal of Combinatorics and Number Theory die?

If an author publishes in a journal that dies, and the journal does not maintain a good website, how can the author prove that he published there, if they need to? For a paper journal they may have a paper version of the journal, but for an e-journal they may be SOL.

If the paper is not on arxiv (or a similar site) it may be lost forever. Note that even if you wanted to pay for an article in either of those journals, it might be impossible. 

3) I wonder- are journals losing money since people are using arxiv and hence not buying the journals?

I only use journals to get credit from my school for publishing, and to get a good proofread from the referee. NOT to get an article out there. Thats what arxiv is for! Also, in my case I can email my article to the few people who care. And I can blog about it. 

Do We Need to Formalize?

Back in the 1990s I explored the system Nuprl for formalizing mathematical proofs. We had a theoretical paper on quickly checking a proof and I wanted to see if we could code it up and make it work on some simple theorems. It never went anywhere.

Automated proof systems have come a long way. Yesterday Terry Tao announced that he has fully formalized his proof with Tim Gowers, Ben Green and Freddie Manners of the Polynomial Freiman-Ruzsa (PFR) conjecture over \({\mathbb F}_2\) in the Lean proof system. The process from paper to formalization took about three weeks.

It's an impressive feat--major new theorem to full formalization in weeks. There's a nice Quanta article from 2021 about the Lean system formalizing a different result.

Is this just a novelty or do we gain something from the formalization?

Mathematics has done quite well without full formalization of theorems--we trust papers that give enough details of a proof that we know a full formalization is possible but fully formalizing a proof just didn't seem an efficient use of a mathematician's time. Should we not trust the proof of the Green-Tao theorem that there are arbitrarily long arithmetic progressions in the primes if we don't have a full formalization?

It would be interesting if formalizing in Lean led to new theorems or found serious bugs in "proofs" of old theorems. 

Maybe AI combined with strong proof systems in the future will be able to take a well-written math paper and find a fully formalized proof or output a logical gap. That would be great--a reviewer can focus on the value of a result instead of its correctness. But we are a long way from unassisted formalization.

Concepts like Turing Machines are hard to fully formulate but somebody did it and there's a lengthy discussion of formalizing computational complexity. So perhaps we can require that anyone who claims a solution to P vs NP needs to formalize their proof before they get to post it to arXiv. For me, that would be the killer app for Lean.

Where do Non-Primitive Recursive Functions come up NATURALLY?

The following is a conversation between Clyde Kruskal and Bill Gasarch.

CLYDE:  Bill, a student, Ian Roberts,  asked me if there are any non-primitive recursive functions that people actually want to compute. (See here for a definition of Primitive Recursive. Also see here for Ackermann's function which is computable but not primitive recursive.) 

BILL: Off hand I would say no, but non-prim rec functions DO come up in natural ways.

CLYDE: That's not what he asked.

BILL: Even so, that's what I will blog about. OH, one more thing, why does he want to know?

CLYDE: Ask him directly. (BILL then emailed Ian)

BILL: Good question about NATURAL problems that are not prim-rec, but why do you want to know?

IAN:  Meyer and Richie proved (see here) that if you limit the control flow to IF statements, FOR loops with finite iterators then the class of functions you implement is  exactly the primitive recursive functions. So I was wondering if I could avoid ever using WHILE loops since they are harder to reason about. 

BILL: YES you COULD avoid ever using WHILE LOOPS; however, there are times when using them is the best way to go.

CLYDE: Bill, when is the last time you wrote a program? And LaTex does not count. 

BILL: Good point. Rather than take my word for it, let's ASK my readers. I'll add that to my list of RANDOM THOUGHTS ABOUT non-prim rec functions. 

SO, random thoughts on non-prim rec functions

0) Are there problems for which writing a WHILE loop is the way to go even though they are  not needed? 

1) HALT is not prim recursive and we want to compute it. Oh well. All future examples will be computable.

2) QUESTION: Are there simple programming languages so that HALT restricted to them is decidable but not primitive recursive? I suspect one could contrive such a language so I ask for both natural and contrived examples. 

3) The Paris-Harrington Numbers from Ramsey Theory are computable and  grow MUCH faster than prim rec. Indeed- they grow much faster than Ackermann's function. See Wikipedia Entry.

4) The Kanamori-McAloon Theorem from Ramsey theory is computable and grow MUCH faster than prim rec. Indeed- they grow much faster than Ackemann's function. See Wikipedia Entry. They are not as well known as the Paris-Harrington numbers. Hopefully this blog post will help that. 

5) Goodstein's Theorem yields numbers that are computable and grow MUCH faster than prim rec. Indeed, they grow much faster than Ackermann's function. See Wikipedia Entry and/or my blog post on them.

6) QUESTION: Of PH, KM, GOOD, which grows fastest? Second fastest? Third fastest? Perhaps some are tied.

6) QUESTION: We know that GO and CHESS have very high complexity, but are still prim recursive. We know that there are some math games (e.g., the Hydra game) that are not prim recursive. Are there any FUN  games whose complexity is NOT prim recursive?

7) Tarjan's UNION-FIND data structure has amortized complexity roughly O(n alpha(n)) where alpha(n) is the inverse of Ackermann's function. This is also a lower bound. See Wikipedia entry on disjoint-set data structure. QUESTION: Is Tarjan's UNION-FIND data structure actually used? It can be used to speed up Kruskal's MST algorithm, but that just takes the question back one step: Is MST a problem people really want to solve? I asked Lance and he asked chatty. For the results of that see here . The answer seems to be YES, though I wonder if the speedup that UNION-FIND gives is important. Union-Find is also used in the Hoshen-Kopelman Algorithm for (to quote Wikipedia) labeling clusters on a grid, where the grid is a regular network of  cells, with the cells being either occupied or unoccupied.  Other issues:  (a) is UNION-FIND hard to code up? Lance tells me that it is easy to code up.  (b) Is the constant reasonable?

8) Is the Ackerman Security Company called that since they claim that breaking their security is as hard as computing Ackerman's function? Unlikely- they spell it with only one n at the end. Even so, my class believed me when I told them that. 

9) The finite version of Kruskal's Tree Theorem YADA YADA YADA not prim rec. Wikipedia Entry

CLYDE: You can't YADA YADA YADA my Uncle Joe!

BILL: It's my party and you'll cry if you want to, cry if you want to, cry if you want to. (See here for Leslie Gore's song Its my party and I'll cry if I want to which is not about non primitive recursive functions. Also see her sequel Judy's turn to cry.  A much better song with a better message for teenagers is her You don't own me.)

CLYDE: Oh well. However, I'll make sure to tell that example to my class.

(ADDED LATER: Quanta had a nice article on non-primrec functions recently here. The problem they are talking about is discussed in the comments.)