I helped the Pope's with his latest Encyclical (His Math Background Helped)

I blogged about Pope Leo XIV here. Pope Leo XIV has an undergraduate degree in mathematics. He saw my post and asked for my help with his latest encyclical. 

LEO: Let's have lunch together at Popeyes.

BILL: Why Popeyes?

LEO: The name is Pope-yes so I get a discount.

BILL: Your treat. [We met at Pope-yes and had the following discussion.]

LEO: I am working on an encyclical to resolve the tension between miracles in the Bible and modern science. 

BILL: What's the issue?

LEO: The Bible has miracles in it that seem to violate the laws of science. There are a few ways to resolve this cosmic conflict.

a) The miracles are allegorical. This is insulting to both God and Man. 

b) The miracles can be explained by natural phenomena. For example:

The Red Sea was split by  a big wind. This is acceptable. The timing of the big wind is the miracle.

BILL: Let me guess the problem: There are some miracles that cannot fit into modern science.

LEO: Exactly!  And I hope that Christians who are scientists (not to be confused with Christian Science, see here) will take up the study of miracles and see how they can fit into modern science.

BILL: Give me an example of a miracle that cannot be resolved with modern science and we'll see what we can do about that.

LEO:  Recall the miracle of loaves and fishes:

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

A crowd of 4000 came to hear Jesus preach. When he was done they were hungry. 

Jesus told his disciples: 

I have compassion for these people; they have already been with me three days and have nothing to eat.  I do not want to send them away hungry, or they may collapse on the way. What food do we have?

The disciples responded:

Seven loaves and a few small fish.

Jesus told the crowd to sit down on the ground. Then he took the seven loaves and the fish and when he had given thanks, he broke them and gave them to the disciples, and they in turn gave to the people. They all ate and were satisfied. There were even leftovers. 

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

So how could Jesus take seven loaves of bread and a few fish and feed thousands of people? How can this be explained with modern science?

BILL: I have a way to resolve it but you may not like it.

LEO: Let's hear it.

BILL: Jesus used the Banach-Tarski paradox  (see here) --- when he broke the bread,  he divided one loaf into 5 pieces, some of which were not measurable, and put them back together to get two loaves. Repeat until you can feed 5000 people. Same with the fishes.

LEO: Great! Why wouldn't I like that?

BILL: It only works if you're pro-(axiom of) choice. 

LEO: I'll have to run this by a subset of my advisors.

BILL: Which subset?

LEO: The Large Cardinals

Fun Little Problems

Occasionally I run into what I consider fun problems in complexity, that require just a little bit of out of the box thinking. They require some background in theory, but nothing too deep. Some of these problems have been mentioned before on my blog or social media.

1. A language \(L\) is commutative if for all \(u\),\(v\) in \(L\), \(uv=vu\). Show that \(L\) is commutative if and only if \(L\) is a subset of \(w^*\) for some string \(w\). The "only if" direction is surprisingly tricky.
2. Let an NP machine be sparse if for some \(k\), it has at most \(n^k\) accepting paths for every input of length \(n\). The class FewP is the set of languages accepted by sparse NP machines. Let \(\#N(x)\) be the number of accepting paths of \(N(x)\). Show that if P=FewP then \(\#N(x)\) is polynomial-time computable for any sparse NP machine \(N\). 
   Richard Beigel gave me this problem and told me the second thing I tried would work. He was right.
3. Let PERM(\(L\)) be the set of all permutations of the strings in \(L\). For example, PERM(\(\{000,010\}\)) is \(\{000,001,010,100\}\). Are regular languages closed under PERM? How about context-free languages?
4. Suppose you have a one-tape Turing machine where we allow the transition function to move the head left, right or stay put. Show there is an equivalent one-tape Turing machine that only moves the head left or right. Not hard, but now do it without increasing the size of the state space or tape alphabet.
   
5. Let E be the set of problem solvable in time \(2^{O(n)}\). Show unconditionally that E \(\ne\) NP.
6. Show there is a computable list of Turing machines \(M_1,M_2,\ldots\) such that \(\{L(M_1),L(M_2),\ldots\}\) is exactly the set of computable languages. A computable list means there is a computable function \(f\) such that \(f(i)\) is a description of \(M_i\). 

My Oxford Term

High table dinner at Magdalen

My time in Oxford has come to an end and I head back to Chicago this week. I was a visiting Fellow at Magdalen (pronounced "maudlin") College for the Hilary Term.

There's a six week break between the eight-week Hilary and Trinity terms. They work the fellows hard during the terms with teaching, tutoring, admissions, hiring and various other administrative functions. All the events, seminars, workshops, high-table dinners are scheduled during the term. Pretty much nothing between terms, and many domestic students are forced out of their housing, and many of the fellows/professors leave town as well. An interesting strategy when us Americans get just a week for spring break. 

I came here for research, working mostly with my former PhD student Rahul Santhanam, a tutorial fellow at Magdalen, and his students. More on the research in a future post.

I took full advantage of the Magdalen college life, working in the senior common room, having lunch in the winter common room, evensong in the chapel with an outstanding choir and organ, and high table dinner in the hall. I had the same experiences as Magdalen fellows have for centuries including CS Lewis, Oscar Wilde and Erwin Schrödinger. There's also a summer common room with a secret door to the old library, and by old it predates most American universities. Magdalen looks like such a traditional old college that some recent Oxford-set shows, including My Oxford Year and Young Sherlock, had extensive filming there. 

As I mentioned earlier, community focuses on the college not on the departments. I had an office in the CS building but didn't spend that much time there. Every day at Magdalen particularly at lunch and dinner, I had great conversations with lawyers, biologists, historians, archivists, literature, music historians, stained-glass restorers and the numismatist who manages the 300,000 coin collection of the Oxford Ashmolean museum.

One dinner I sat next to the COO of the new Ellison Institute of Technology, a ten billion dollar venture in Oxford but independent of the university, funded by the Oracle CEO. She talked considerably about the famous pub, the Eagle and the Child. The pub, nicknamed the Bird and the Baby, was famous as the meeting place of the Inklings, a group of writers including Lewis and Tolkien. It never reopened after Covid and was purchased by Ellison and currently being renovated. 

Another visiting fellow, Elaine Treharne, was giving a talk on Medieval poetry the same week I talked about complexity and machine learning. We went to each other's talk. Hers in the brand new Schwarzman Centre for the Humanities, the same Schwarzman from MIT's College of Computing and mine in a CS building that's a mish mash of other buildings. She outdrew me two to one.

A $100 gift card could be legit. A $1000 is obviously a Scam. What should scammers do?

 If I get an email offering me a $1000 for I DON"T KNOW SINCE  I ignore it and don't even bother looking for other signs it is a scam. 

If I get an email offering me $100  I may look more carefully and often they are legit (most common is to give a per-publication review of a math book---sometimes just questions, but more often a written report). 

Most offers I get are either $1000 or $100. Today I got one for $750 which inspired this post (I ignored the offer without checking). 

Which nets more people $100 or $1000?

1) If people are like me then $100 fools more people. But people like me will still CHECK CAREFULLY. I sometimes feed the email into ChatGPT for an opinion to see if it's a scam. (Spellcheck still things ChatGPT should be spelled catgut.) 

2) Are there people who would fill out the survey (or whatever) for $1000 but not for $100? I ask non rhetorically as always. Are such people more gullible?

Would scammers make more money if they offered $100 instead of $1000 ?

1) More people would fall for the $100 scam. Or maybe not---do some people not bother if it's only $100?

2) Depending on how they are scamming you, will they get less out of it if they only offer $100?

Here are types of scams:

1) They send you a check for $1000 + x and say WHOOPS- please email us a check for $x. I've heard of this in the Can you tutor our daughter in math? scam. For this one, offering $1000 nets the scammer more money since for $100+x, x will be smaller than $1000+x.

2) They want to harvest your personal information. For these I don't think they will gain more if they do 1000 vs 100. 

One more thought:

1) I said that for $100 I take it seriously but for $1000 I don't

2) I said that $750 I do not take it seriously.

3) What's the cutoff?  Obviously $289.

Bennett and Brassard Win the Turing Award

Gilles Brassard and Charlie Bennett

Charlie Bennett and Gilles Brassard will receive the 2025 ACM Turing Award for their work on the foundations of quantum information science, the first Turing award for quantum. Read all about it in The New York Times, Science and Quanta.

Bennett and Brassard famously met in the water off a beach during the 1979 FOCS conference in Puerto Rico. That led to years of collaboration, most notably for their quantum secure key distribution protocol. The basic idea is pretty simple and does not require quantum entanglement. Alice sends a series of random bits, either straightforward or rotated 45 degrees. Bob measures each of these bits in randomly chosen bases. They discard the bits where they used different bases and use some of the remaining bits to check for eavesdropping, which would collapse the state, and others to set the key.

Bennett and Brassard and four other authors showed how to teleport a quantum bit using entanglement and two classical bits. Bennett with Stephen Wiesner gave the dual superdense coding protocol of sending two classical bits using a single quantum bit. 

Bennett and Brassard, with Ethan Bernstein and Umesh Vazirani, showed that in black-box setting, quantum computers would require \(\Omega(\sqrt{n})\) queries to search \(n\) entries, matching Grover's algorithm. For some reason, the popular press rarely covers these results that limit the power of quantum computing. 

I've had the pleasure of knowing both Bennett and Brassard since the 1980s, both just full of enthusiasm and wonderful ideas. 

Let me end by saying I don't see this as a Turing award for quantum computing. Once (if?) we get large scale machines, we'll certainly see Turing awards, if not Nobel Prizes, for Peter Shor, Umesh Vazirani and others.

For \(R^3\) the problem is open. That's too bad. We live in \(R^3\)

(If you live in Montgomery County Maryland OR if you care about Education, you MUST read this guest blog by Daniel Gottesman on Scott Aaronson's blog HERE.) 

(This post is a sequel to a prior post on this topic that was here. However, this post is self-contained---you don't need to have read the prior post.)  

(Later in the post I point to my open problems column that does what is in this post rigorously. However , that link might be hard to find, so here it is:  HERE)

BILL: I have a nice problem to tell you about. First, the setup.

Say you have a finite coloring of \(R^n\).

A  mono unit square is a set of four points that are

(a) all the same color, and

(b) form a square of side 1. The square does not need to be parallel to any of the axes.

DARLING: Okay. What is the problem?

BILL:  It is known that for all  2-colorings of \(R^6\) there is a mono unit square.

DARLING: \(R^6\)? Really! That's hilarious! Surely, better is known.

BILL: Yes better is known. And stop calling me Shirley.

DARLING: Okay, so what else is known?

BILL: An observation about the \(R^6\) result gives us the result for \(R^5\). (The \(R^5\) result also follows from a different technique.) Then a much harder proof gives us the result for \(R^4\). It is easy to  construct  a coloring of \(R^2\) without a mono unit square. The problem for \(R^3\) is open.

DARLING: That's too bad. We live in \(R^3\).

DARLING: Someone should write an article about all this including proofs of all the known results, open problems,  and maybe a few new things.

BILL: By someone you mean Auguste Gezalyan (Got his  PhD in CS, topic Comp Geom, at  UMCP), Ryan Parker (ugrad working on Comp Geom at UMCP), and Bill Gasarch (that's me!)  Good idea!

A FEW WEEKS LATER

BILL: Done! See here. And I call the problem about \(R^3\) The Darling Problem.

DARLING: Great! Now that you have an in-depth knowledge of the problem---

BILL: Auguste and Ryan have an in depth knowledge. Frankly I'm out of my depth.

DARLING: Okay, then I'll ask them:  What do you think happens in \(R^3\) and when do think it will be proved?

AUGUSTE: I think there is a 2-coloring of \(R^3\) with no mono unit square.

RYAN: I think that for every 2-coloring of \(R^3\) there is a mono unit square.

BILL: I have no conjecture; however, I think this is the kind of problem that really could be solved. It has not been worked on that much and it might just be one key idea from being solved. It is my hope that this article and blog post inspires someone to work on it and solve it. 

OBLIGATORY AI COMMENT

Auguste asked ChatGPT (or some AI) about the problem. It replied that the problem is open and is known as The Darling's Problem. This is rather surprising---Auguste asked the AI about this before I had submitted the article (it has since appeared) and before this blog post. So how did AI know about it? It was on my website.  I conjecture that Auguste used some of the same language we used in the paper so the AI found our paper. The oddest thing about this is that I don't find this odd anymore. 

 COLOR COMMENTARY  

The article appeared as a SIGACT News Open Problems Column. Are you better off reading it there or on my website, which is pointed to above. The SIGACT News version is (a) behind a paywall, and (b) in black and white. The version on my website is (a) free access, and (b) uses color. You decide.

Tony Hoare (1934-2026)

Turing Award winner and former Oxford professor Tony Hoare passed away last Thursday at the age of 92. Hoare is famous for quicksort, ALGOL, Hoare logic and so much more. Jim Miles gives his personal reflections.

Jill Hoare, Tony Hoare, Jim Miles. Cambridge, 7 September 2021

Last Thursday (5th March 2026), Tony Hoare passed away, at the age of 92. He made many important contributions to Computer Science, which go well beyond just the one for which most Maths/CompSci undergraduates might know his name: the quicksort algorithm. His achievements in the field are covered comprehensively across easy-to-find books and articles, and I am sure will be addressed in detail as obituaries are published over the coming weeks. I was invited in this entry to remember the Tony that I knew, so here I will be writing about his personality from the occasions that I met him.

I visited Tony Hoare several times in the past 5 years, as we both live in Cambridge (UK) and it turned out that my family knew his. As a Mathematics graduate, I was very keen to meet and learn about his life from the great man himself. I was further prompted by a post on this blog which mentioned Tony a few times and summarised a relevant portion of his work. I took a print out of that entry the first time I visited him to help break the ice - it is the green sheet of paper in the picture above.

Tony read the entry and smiled, clearly recalling very well the material of his that it referenced, and then elaborating a bit, explaining how vastly programs had scaled up in a rather short space of time and how they typically require different methods than many of those he had been developing in the early days.

I was aware that Tony had studied Classics and Philosophy at university so I was keen to learn how one thing had led to another in the development of his career. He explained that after completing his degree he had been intensively trained in Russian on the Joint Services School for Linguists programme and was also personally very interested in statistics as well as the emerging and exciting world of computers. This meant that after his National Service (which was essentially the JSSL) he took on a job 'demonstrating' a type of early computer, in particular globally, and especially in the Soviet Union. He described the place of these demonstrations as 'fairs' but I suppose we might now call them 'expos'. In a sense, this seemed like a very modest description of his job, when in fact - reading up on Tony's career - he was also involved in the development of code for these devices, but perhaps that's a historical quirk of the period: being a demonstrator of these machines meant really knowing them inside and out to the point of acting on the dev team (AND, one might deduce, being fluent in Russian!).

Tony would tell these stories with a clarity and warmth that made it clear that certainly he was still entirely 'all there' mentally, and that his memory was pinpoint sharp, even if there were some physical health issues, typical for anyone who makes it so far into their 80s (and, as we now know, beyond!).

A story that I was determined to hear from the source was the legendary quicksort 'wager'. The story goes that Tony told his boss at Elliott Brothers Ltd that he knew a faster sorting algorithm than the one that he had just implemented for the company. He was told 'I bet you sixpence you don't!'. Lo and behold, quicksort WAS faster. I asked Tony to tell this story pretty much every time we met, because I enjoyed it so much and it always put a smile on both of our faces. To his credit, Tony never tired of telling me this story 'right from the top'. I had hoped to visit again in the past year and record him telling it so that there was a record, but unfortunately this did not happen. However, I discover that it is indeed recorded elsewhere. One detail I might be able to add is that I asked Tony if indeed the wager was paid out or if it had merely been a figure of speech. He confirmed that indeed he WAS paid the wager (!). A detail of this story that I find particularly reflective of Tony's humble personality is that he went ahead and implemented the slower algorithm he was asked to, while he believed quicksort to be faster, and before chiming in with this belief. It speaks to a professionalism that Tony always carried.

About 50% of our meetings were spent talking about these matters relating to his career, while the rest varied across a vast range of topics. In particular, I wanted to ask him about a story that I had heard from a relative, that Tony - whilst working at Microsoft in Cambridge - would like to slip out some afternoons and watch films at the local Arts Picturehouse. This had come about because on one occasion a current film in question was brought up in conversation and it transpired Tony had seen it, much to the bemusement of some present. The jig was up - Tony admitted that, yes, sometimes he would nip out on an afternoon and visit the cinema. When I met Tony and gently questioned him on this anecdote he confirmed that indeed this was one of his pleasures and his position at Microsoft more than accommodated it.

On the topic of films, I wanted to follow up with Tony a quote that I have seen online attributed to him about Hollywood portrayal of geniuses, often especially in relation to Good Will Hunting. A typical example is: "Hollywood's idea of genius is Good Will Hunting: someone who can solve any problem instantly. In reality, geniuses struggle with a single problem for years". Tony agreed with the idea that cinema often misrepresents how ability in abstract fields such as mathematics is learned over countless hours of thought, rather than - as the movies like to make out - imparted, unexplained, to people of 'genius'. However, he was unsure where exactly he had said this or how/why it had gotten onto the internet, and he agreed that online quotes on the subject, attributed to him, may well be erroneous.

One final note I would like to share from these meetings with Tony is perhaps the most intriguing of what he said, but also the one he delivered with the greatest outright confidence. In a discussion about the developments of computers in the future - whether we are reaching limits of Moore's Law, whether Quantum Computers will be required to reinvigorate progress, and other rather shallow and obvious hardware talking points raised by me in an effort to spark Tony's interest - he said 'Well, of course, nothing we have even comes close to what the government has access to. They will always be years ahead of what you can imagine'. When pressed on this, in particular whether he believed such technology to be on the scale of solving the large prime factorisation that the world's cryptographic protocols are based on, he was cagey and shrugged enigmatically. One wonders what he had seen, or perhaps he was engaging in a bit of knowing trolling; Tony had a fantastic sense of humour and was certainly capable of leading me down the garden path with irony and satire before I realised a joke was being made.

I will greatly miss this humour, patience, and sharpness of mind, as I miss everything else about Tony.

RIP Tony Hoare (11 January 1934 - 5 March 2026)

How does AI do on Baseball-Brothers-Pitchers

In my graduate Ramsey Theory class I taught Kruskal's tree theorem (KTT) which was proven by Joe Kruskal in his PhD thesis in 1960.  (Should that be in a graduate Ramsey Theory class? There are not enough people teaching such a course to get a debate going.) A simpler proof was discovered (invented?) by Nash-Williams in 1963.

The theorem is that the set of trees under the homeomorphism ordering is a well quasi order.

But this blog post is not about well quasi orderings. It's about baseball brothers and AI.

The Kruskals are one of the best math families of all time. See my post on math families.The Bernoullis are another great math family.  What makes both families so great is that they had at least THREE great math people. Most have two.

Having taught the KTT and talked briefly about math families, I was curious how ChatGPT would do on the better-defined question of largest number of wins by a pair of brothers in baseball.  So I asked my students to look that up and include which tools they used,  as a HW problem  (worth 0 points but they had to do it). 

I wrote up 9 pages on what the answer is (there are some issues) and what the students' answers were. See my write up.

In case those 9 pages are tl;dr, here are the main takeaways

1) 7 of the answers given were just WRONG no matter how you look at it.

2) 7 had either the Clarksons who played in the 1880's, so don't count as modern baseball, or there were three of them, or both.  Even so, one could argue these are correct

3) 1 got it right. (That's   one got it right  not  I, bill g, got it right. It can be hard to distinguish the numeral for one, the letter capital i, and the letter small L. I blogged about L vs I here in the context of Weird AI vs Weird AL).

4) There were 13 different answers, which I find amazing.

As usual, when I study some odd issue, I learn a few other things of interest, at least to me, which may also have life lessons, though YMMV. 

a) Around 85% of pitchers in the Hall of Fame have won over 200 games. Dizzy Dean (his brother was also a pitcher which is why I was looking at this) got into the Hall of Fame with only 150 wins. Why? For 6 years he was the most dominant pitcher in the game. In addition (1) there was some sympathy for him since his career was cut short by an injury he got in an All-star game, and (2) he had a colorful personality and people liked him. The four least-wins for a HOF are: Candy Cummings (W-L 145-94).  [he is said to have invented the curveball], Dizzy Dean (W-L 150-83) , Addie Joss (W-L 160-97 )[he only played 9 years, which is less than the 10 needed for eligibility in the HOF, but he died so he was given an exception], Sandy Koufax (W-L 165-87) [he was dominant, like Dean, for a short time]. Sandy is the only one who is still alive. (W-L means Win-Loss. For example, Candy won 145 games and lost 94.)

b) Modern baseball starts in 1900. But this is arbitrary. In 1904 Jack Chesbro won 40 games which would never happen in modern baseball. But you have to draw the line someplace.  History is hard because there are fuzzy boundaries.

c) I had not known about the Clarkson brothers. 

d) My interest in this subject goes back to 1973. In that year I heard the following during a baseball game and, ever since I began blogging, I wondered how I could fit it into a blog post:


An old baseball trick question is now gone!  Just last week [in 1973] if you asked

What pair of brothers in baseball won the most games?

the answer was Christy and Henry Mathewson. Christy played for 16 seasons and had a W-L record of 373-188, while his brother Henry played in 3 games and had a W-L record of 0-1. So their total number of wins is 373 which was the record.

But this last week [in 1973] the Perry brothers, Gaylord and Jim, got 374 wins between them.  Hence the question

What pair of brothers in baseball won the most games?

is no longer a trick question since both Perrys are fine pitchers [Gaylord made it into the Hall of Fame; Jim didn't, but Jim was still quite good.]

As you will see in my writeup, the Perrys' record was broken by the Niekros.

e) Christy and Henry are a trick answer because Henry wasn't much of a player with his 0-1 W-L record. Are there other pairs like that? Greg (355 wins) and Mike (39 wins) Maddux might seem that way but they are not. While Mike only had 39 wins he had a 14-year career as a relief pitcher. Such pitchers can be valuable to the team, but because of their role they do not get many wins.

SO the usual question: Why did AI get this one wrong? Lance will say that the paid version wouldn't have and he may be right. David in Tokyo might say that ChatGPT is a random word generator. Others tell me that ChatGPT does not understand the questions it is asked (my proofreader thinks this is obvious).  I'll add that the pitcher-brother  question has more ambiguity than I thought- do you count pitchers before 1900? Do you count a brother who won 0 games? What about 3 brothers (not the restaurant)?