What is Closed Form? The Horse Numbers are an illustration

In the book Those Fascinating Numbers by Jean-Marie De Konick they find interesting (or `interesting') things to say about many numbers. I reviewed the book in a SIGACT News book review column here. The entry for 13 is odd: 13 is the third Horse Number.  The nth Horse number is the number of ways n horses can finish a race. You might think: OH, that's just n!. AH- horses can tie. So it's the number of ways to order n objects allowing ties. 

Is there a closed form for H(n)? We will come back to that later. 

0) The Wikipedia Entry on horse races that ended in a dead  heat is here. They list 78 dead heats (two horses tie for first place) and 10 triple dead heats (three horses tie for first place). For the horse numbers we care if (say) two horses tie for 4th place. In reality nobody cares about that. 

1) I have found nowhere else where these numbers are called The Horse Numbers. 

2) They are called the Ordered Bell Numbers. The Wikipedia entry here has some applications.

3) They are also called the Fubini Numbers according to the Ordered Bell Number Wikipedia page.

4) I had not thought about the Horse Numbers for a long time  when they came up while I was making slides for the proof that  (Q,<) is decidable (the slides are here).

5) There is an OEIS page for the Horse Numbers, though they are called the Ordered Bell Numbers and the Fubini Numbers. It is here. That page says H(n) is asymptotically \(\frac{1}{2}n!(\log_2(e))^{n+1}\) which is approx \(\frac{1}{2}n!(1.44)^{n+1}\).

6) There is a recurrence for the Horse Numbers:

H(0)=1

H(1)=1

H(2)=3

For all  \(n\ge 3\) we split H(n) into what happens  if i horses are tied for last place (choose i out of n) and if the rest are ordered H(n-i) ways. Hence

\( H(n) = \binom{n}{1}H(n-1) + \binom{n}{2}H(n-2) +  \cdots  + \binom{n}{n}H(0) \)

Using \(\binom{n}{i} = \binom{n}{n-i}\) we get

\( H(n) = \binom{n}{0}H(0) + \binom{n}{1}H(1) +  \cdots  + \binom{n}{n-1}H(n-1) \)

STUDENT: Is there a closed form for H(n)?

BILL: Yes. Its H(n).

STUDENT: That's not closed form.

BILL: Is there a closed form for the number of ways to choose i items out of n?

STUDENT: Yes, \(\binom{n}{i}\) or \( \frac{n!}{i!(n-i)!}\) 

BILL: Does that let you compute it easily? No. The way you compute \(\binom{n}{i}\) is with a recurrence. The way you compute H(n) is with a recurrence. Just having a nice notation for something does not mean you have a closed form for it. 

STUDENT: I disagree! We know what n! is!

BILL: Do not be seduced by the familiarity of  the notation. 

Favorite Theorems: Dichotomy

A constraint satisfaction problem has a group of constraints applied to a set of variables and we want to know if there is a setting of the variables that make all the constraints true. In CNF-Satisfiability the variables are Boolean and the constraints are ORs of variables and their negations. In graph coloring, the variables are the colors of the nodes and the constraints, corresponding to edges, are two variables must be different. These problems lie in NP, just guess the values of the variables and check the constraints. They are often NP-complete. They are sometimes in P, like 2-coloring graphs. But they are never in between--all such problems are either in P or NP-complete.

A Dichotomy Theorem for Nonuniform CSPs by Andrei Bulatov

A Proof of the CSP Dichotomy Conjecture by Dmitriy Zhuk

Ladner's Theorem states that if P \(\neq\) NP then there exists a set in NP that is not in P and not NP-complete. Ladner's proof works by blowing holes in Satisfiability, an unsatisfying construction as it gives us a set that is NP-complete on some input lengths and easy on others. One could hope that some version of a constraint satisfaction problem could lead to a more natural intermediate set but dichotomy theorems tell us we need to look elsewhere.

In 1978, Thomas Schaefer gave a dichotomy theorem for satisfiability problems, basically CSP problems over Boolean variables. In 1990, Pavol Hell and Jaroslav Nešetřil showed a dichotomy result for homomorphisms of undirected graphs as described in my 2017 blog post. In 1998 Tomás Feder and Moshe Vardi formalized the constraint satisfaction dichotomy conjecture and expressed it as homomorphisms of directed graphs. The blog post described a claimed but later retracted solution to the dichotomy conjecture. Bulatov and Zhuk announced independent and different correct proofs later that year. In 2020 Zhuk received the Presburger Award for his paper (Bulatov was too senior for the award). 

May the fourth be with you. Too many -days?

(This post was inspired by Rachel F, a prior REU-CAAR student, emailing me wishing me a happy Star Wars Day.) 

 I am writing this on May 4 which is Star Wars day. Off the top of my head I know of the following special days (I exclude official holidays, though the term official has no official meaning.)

Jan 25: Opposite Day Wikipedia Link

Feb 2: Groundhog Day Wikipedia Link

Feb 12: Darwin Day Wikipedia Link

March 14: Pi Day Wikipedia link

May 4: Star Wars Day Wikipedia Link

April 22: Earth Day Wikipedia link

April 25: Take your Child to Work Day Wikipedia Link

Sep 21: National Cleanup Day Wikipedia Link

Sept 22: Hobbit Day Wikipedia Link

Oct 1: International Coffee Day Wikipedia Link

Oct 8: Ada Lovelace Day Wikipedia Link

Oct 16: Boss's Day  Wikipedia Link

Oct 23: Mole Day Wikipedia Link

Nov 13: Sadie Hawkins Day Wikipedia Link

Sept 19: Talk like a Pirate Day Wikipedia Link

A few notes

1a) Oct 23 is also Weird Al's birthday.

1b) May 4 is also Edward Nelson's birthday (he invented the problem of  finding the chromatic number of the plan). See my post (actually a guest post by Alexander Soifer) on the problem here for more information on that.

1c) I left off St. Patrick's Day (March 17) and International LGBT + Pride day (June 28) and many others.  Those left off are so well known that they are official where as I was looking for unofficial holidays. But see next point.

2) The Wikipedia entry for Talk Like a Pirate Day says it's a parodic holiday. The entries on the others holidays use terms like unofficial. I prefer unofficial since ALL holidays are made up, so the only real question is which ones are recognized. But even that is problematic since one can ask recognized by who? Also, despite collecting parody music and videos for the last 50 years, I have never heard the term parodic. Therefore it is not a word. Spellcheck agrees!

3) Darwin Day should be Darwin-Lincoln day since they were both born on Feb 12. In fact,they were both born in 1809. Most famous same-birthday-and-year pair ever. Second place is Lenny Bruce and Margaret Thatcher (Oct 13, 1925). 

4) The page on Pi Day mentions Tau Day, but Tau day has no page of its own. Tau is \(2\pi\) which some say comes up more often then \(\pi\) and hence should be THE constant. Some say that \(2\pi i\) comes up so often that it should be THE constant. However, there can't really be a day to celebrate it.(I blogged about is-tau-better-than-pi here.)

5) In the future every day will be some kind of day. The Future Is NOW: Website of Fun Holidays

Are the holidays on the list real? Depends what you mean by real. Because of the web anyone can post a list of anything and its just one person's opinion. I do not know who controls that website but even if I did, it would be hard to say YES THOSE ARE REAL or NO THOSE ARE NOT. 

One could say that to be a real DAY, it has to be on Wikipedia. But there are two problems with this:

a) Goodhart's law. When a measure becomes a target it stops being a measure. If I want Jan 15 to be Bagel and Lox Day, I'll make a page for it.

b) I'm still waiting for Raegan Revord, who has played Missy on Young Sheldon for 7 years, to get a Wikipedia Page. So what hope does Polar Bear Plunge day (Jan 1) have for getting a Wikipedia Page? 

Our Obsession with Proofs

Bullinger's post on this blog last week focused on Vijay Vazirani's public obsession of finding a proof for the 1980 Micali-Vazirani matching algorithm. But why does Vijay, and theoretical computer science in general, obsess over proofs? 

You can't submit a paper to a theory conference without a claimed complete proof, often contained in an appendix dozens of pages long. Often we judge papers more on the complexity of the proof than the statement of the theorem itself, even though for a given theorem a simpler proof is always better.

A proof does not make a theorem true; it was always true. The Micali-Vazirani algorithm is no faster with the new proof. Would we have been better off if the algorithm didn't get published before there was a full proof?

We're theoretical computer scientists--doesn't that mean we need proofs? Theoretical economists and physicists don't put such an emphasis on proofs, they focus on models and theorems to justify them.

Once a senior CS theorist told economists that his group had given the first full proof of a famous economics theorem and wondered why the economists didn't care. The economists said they already knew the theorem was true, so the proof added little to their knowledge base.

More than one journalist has asked me about the importance of a proof that P \(\ne\) NP. A proof that P = NP would be both surprising and hopefully give an algorithm. While a proof that P \(\ne\) NP would be incredibly interesting and solve a major mathematical challenge, it wouldn't do much more than confirm what we already believe.

I'm not anti-proof, it is useful to be absolutely sure that a theorem is true. But does focusing on the proofs hold our field back from giving intuitively correct algorithms and theorems? Is working out the gory details of a lengthy proof, which no one will ever read, the best use of anyone's time? 

As computing enters a phase of machine learning and optimization where we have little formal proof of why these models and algorithms work as well as they do, does our continued focus on proofs make our field even less relevant to the computing world today?

Math Thoughts Inspired by the TV show Succession

I watched Succession one-episode-a-day on treadmill for 39 days. I'm glad I did this in 2023 since Season 2 aired its last show on Oct 19, 2019, and Season 3 had its first show on Oct 17, 2021, so I would have been in suspense (or at least as much suspense as corporate board meetings can generate) for about 2 years. 

The show inspired the following mathematical thoughts.

1) There was a scene which I paraphrase as follows:

Alice: I'll give you two billion dollars for your shares in the company.

Bob: Don't insult me. It's worth at least 2.5 billion. 

My thought: I would take the two billion. 

My Math Thought: Let's say the shares really were worth 2.5 billion. Is it worth haggling? I think not, since I can't imagine I will ever spend that much money in my life. (See the blog post here  on the St. Petersburg paradox which is about  how much money is enough.) To be fair, if I wanted to buy Tesla (note that I mean buying the company, not buying the car) or buy the Comedy Cable Station (I would run it so that it only airs funny commercials) then I might need the extra half a billion to even begin trying (Tesla is worth around 740 billion).  SO the question of is it worth the haggling depends on your situation. 

So let's assume you don't need the money for some large purchase. Would you haggle? One reason to haggle is that you don't want the person who is ripping you off by only offering 2 billion to get away with it and/or think you are a chump. Whether one cares about this might depend on the relationship you have with that person. Even so, I would just take the 2 billion. Perhaps that's why I am in academia instead of business.

MATH QUESTION: Can we quantify what amount of money its not worth haggling over? 

2) Alice wants to buy Bob's company. After months of negotiations they agree to x dollars (and there are many side issues as well). The next day 

Alice thinks: OH, if he was willing to sell for x, he would be willing to sell for x-1. 

Bob thinks:OH, if she was willing to buy for x, he would be willing to buy for x+1.

(In the show this scenario happened many times, but usually with only one party wanting to re-negotiate and its not just  +1 and -1, its things like seats-on-the-board, who-will-be-CEO.) 

MATH QUESTION:  If Alice and Bob behave as above is there any mechanism to make them actually come to an agreement? Might involve assuming they can't factor fast or can't solve NPC problems fast.

Is Persistence an Anachronism?

Guest post by Martin Bullinger

Very recently, Vijay Vazirani's paper A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length got accepted to Mathematics of Operations Research. For the first time, it gives a complete and correct proof that the Micali-Vazirani algorithm finds a maximum cardinality matching in time \(\mathcal O\left(m\sqrt{n}\right)\). I would like to give an account of the extraordinary story of this proof and how Vazirani's contribution inspires persistence.

My fascination for matching already started during my undergrad when I gave a talk on Edmonds' blossom algorithm. It was at this time that I first heard about the Micali-Vazirani (MV) algorithm. Naturally, I was quite excited when I got to know Vazirani personally years later. When I talked to him about the MV algorithm I was, however, shocked: Vazirani admitted that even to that day, there did not exist a complete proof of its correctness. How can a theoretical result be accepted to FOCS without a proof?

Now, 44 years after publication of the algorithm, a proof exists and has been peer-reviewed in great depth. But why did it take so long? Apparently, some results just need time. Sometimes a lot of time. Think of Fermat's Last Theorem, whose proof took 358 years! So what is the story behind the MV algorithm? It can without a doubt be seen as a lifework. Together with his fellow PhD student Silvio Micali, Vazirani discovered it in the first year of his PhD in 1979-80. Without even attempting a proof, it was published in the proceedings of FOCS 1980. The first proof attempt by Vazirani was published in 1994 in Combinatorica. Unfortunately, this proof turned out to be flawed. It took another 30 years until his current paper.

What kept Vazirani going for so long? In the acknowledgements of his paper, he thanks matching theory for its gloriously elegant structure. Vazirani was driven by his passion for the subject matter---but passion by itself can only go so far. Even more important was his belief in the correctness of the algorithm and the theory, which he had broadly outlined in his 1994 paper. Similar to Andrew Wiles' story, his perseverance led him to the idea which clinched the proof. In Vazirani's case, this was to use the new algorithmic idea of double depth-first search, which forms the core of the MV algorithm, and now, its proof as well. But Vazirani's result is also the story of an excellent research environment. Finding deep results requires colleagues or friends to discuss ideas with. Vazirani had these in the form of strong postdocs and PhD students. About ten years ago, he had been discussing ideas towards his proof with his former postdoc Ruta Mehta, and in the last three years, he discussed the final touches of his proof with his current PhD student Rohith Gangam. Needless to say, both of them gained a lot from these discussions.

So why should we care for the MV algorithm? I have several reasons. First, without doubt, it is a historic result within combinatorial optimization. Matching is one of the most fundamental objects in discrete mathematics and we keep finding new applications for it, for example, in health, labor markets, and modern day matching markets on the Internet, basically in every part of our lives. But there is more. Once again, one can look at Vazirani's paper where he describes the impact of matching to the development of the theory of algorithms: Matching theory has led to foundational concepts like the definition of the complexity classes \(\mathcal P\) (Edmonds, 1965a) and \(\# \mathcal P\) (Valiant, 1979), the primal-dual paradigm (Kuhn, 1955), and polyhedral combinatorics (Edmonds, 1965b). The impact of matching on complexity theory was an earlier topic of this blog.

Despite being around for decades, the MV algorithm is still the fastest known algorithm for computing a maximum cardinality matching. This is surprising, to put it mildly. Similar to many other fundamental problems in combinatorial optimization, I would have expected the discovery of better algorithms in the last four decades. Why has this not happened? Vazirani appears to have gotten to the essence of the problem: a profound theory that interleaves algorithmic invariants and graph-theoretic concepts. It seems to be the kind of theory which would play an active role in the field of combinatorial optimization.

However, Vazirani's result proves something else, possibly even more important: the massive gains to be made by single-minded persistence. In a world in which departments and promotion procedures focus on publishing large numbers of papers, it seems impossible to work on one result for more than a year, let alone for decades. Vazirani managed to achieve both: pursue his passion and get the unfinished job done, but not let it come in the way of the rest of his otherwise-active research career. As a young researcher, this inspires me! In the end, it is through such persistence that science will take big steps forward.

This blog post evolved from many enjoyable discussions, which I had with Vijay Vazirani during a research stay at UC Irvine in spring 2024. I am grateful to Ruta Mehta for feedback on the initial version of this post. Vazirani recently presented his paper in a mini series of two talks available online.

Intelligent Comments on Bill's G.H. Hardy/Avi W post that we did not post.

I posted (see here) about Avi Wigderson being a counterexample to two of G.H. Hardy's opinions:

1) Hardy thought Math was a young man's game. I got some good comments on this. Some agreed and some disagreed.

2) Hardy thought applied math is dull. I got no comments on this one. I assume everyone agreed with my assessment that Hardy was wrong about this.

AND I got the following comment: 

Avi Wigderson's brilliance shatters the false assumptions of  G.H. Hardy, proving that intelligence knows no limits. His groundbreaking ideas challenge the status quo and inspire a new generation of thinkers.

I agree! I was going to post it! Then I realized that 

a) There were two links below it. A bad sign

b) While Avi is a brilliant thinker, is he known for challenging the status quo? The NW result pointed to P=BPP which was not thought to be true at the time. (Micheal Sipser thought P=BPP, see here, but he was an outlier. If my memory is wrong then leave a polite comment.)  Aside from that result  I don't think Avi's  work challenges the status quo. If I am WRONG leave a polite comment correcting my error. 

c) As a side note- I think of challenging the status quo as being over-rated. Wiles proof of FLT did not challenge the status quo. Many great results do not challenge the status quo. If Avi shows P NE NP that would be awesome even though it is the prevailing opinion. 

d) Upon reading the comment carefully,  it looks like it was AI generated. 

e) It fooled me for about 5 minutes. It didn't fool Lance for a second. 

3) But this comment inspired Lance to use ChatGPT to generate comments to my post: one agreeing, and one disagreeing

BEGIN COMMENT THAT  AGREED

Avi Wigderson’s recent Turing Award is a compelling moment to reflect on the fluid nature of mathematical careers and the erroneous stereotypes surrounding them. G.H. Hardy’s assertion in *A Mathematician’s Apology* that mathematics is a young man's game is eloquently countered by Avi’s illustrious career and the achievements of others well beyond the supposed prime age. This challenges Hardy's notion and suggests it warrants reevaluation as a mere conjecture rather than a stated fact.

Moreover, Hardy’s dismissal of applied mathematics overlooks the dynamic interplay between various disciplines. Even in his era, the boundaries between pure and applied math, along with physics and computer science, were permeable and productive. Avi Wigderson’s work, though not strictly applied math, beautifully illustrates how applied considerations can drive significant theoretical advancements.

In this light, the recognition of Wigderson’s contributions is not just a celebration of his individual genius but also a testament to the evolving and interconnected landscape of mathematics, which continues to defy the narrow confines set by earlier academic opinions.

END OF COMMENT

This is an intelligent comment; however, it mostly reflects back what I said. Indeed, it is a more eloquent exposition of what I said. Fortunately I can't be fired from blogging and replaced with an AI since I don't get paid anyway. 

BEGIN COMMENT THAT DISAGREED

While Avi Wigderson's Turing Award certainly highlights his exceptional contributions to theoretical computer science, invoking this as a refutation of G.H. Hardy's views on mathematics as a young man's game might be an oversimplification. Hardy's assertion, though controversial, was not without merit when considering the context of his times and the examples he witnessed firsthand. It's important to remember that exceptions like Wigderson do not necessarily disprove the rule but rather highlight remarkable outliers.

Furthermore, Hardy's critique of applied mathematics as being dull must be understood in the philosophical context of his personal commitment to pure mathematics. While we may not agree with his perspective, dismissing it entirely fails to appreciate the depth of passion that fueled his work and the work of many pure mathematicians. The interplay between disciplines enriches mathematics, indeed, but Hardy’s emphasis on the beauty of pure theory has inspired generations and continues to hold significant value in the mathematical community. 

END OF COMMENT

 

This does not seem to be just reflecting back what I wrote. 

 

The argument about Avi is an outlier is reasonable. 

 

Here is my counterargument for defending Hardy's negative opinion of applied math:  just because the  notion that applied math is dull fueled passion does not make it correct. And one must also see what harm the notion caused.

 

 If I debated a human on this point they might change their mind, or give better counterarguments. Can ChatGP change its mind? Does that question even make sense? I suspect that ChatGPT could give better or at least different counterarguments.

Favorite Theorems: Quantum Provers

For our next favorite theorem, we look at the surprising power of provers who share entangled bits. If you can prove something to an arbitrarily computable verifier, then two entangled provers can convince a polynomial-time verifier.

MIP* = RE
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen

A quick tour:

• A powerful prover convincing a skeptical computable deterministic verifier is another way of capturing computably enumerable (traditionally called recursively enumerable or RE). You can convince a verifier that a program halts by giving the halting time, and the verifier can simulate the machine for that many steps.
• A powerful prover convincing a skeptical polytime deterministic verifier is another way of capturing the class NP, like giving a 3-coloring of a graph that can be easily checked.
• If you allow the verifier to ask random questions, you can convince the verifier with high confidence that a graph is not colorable, or more generally any PSPACE problem.
• If you add two separated provers that a skeptical probabilistic verifier can play off each other, the provers can convince the verifier that any problem in NEXP, non-deterministic exponential time.

One of many quantum variations of interactive proofs, MIP* has two provers that cannot communicate but have entangled quantum bits. This change could go either way: 

• The provers to coordinate their answers better and so they wouldn't convince the verifier for all the languages in NEXP
• The verifier could ask more complex questions to the provers which they could answer using the entanglement, allowing the provers to convince the verifier for even more complex languages.

Turns out it's the later in a very strong way.

Ito and Vidick showed that you can create a protocol that prevents the provers coordinating better, recovering all problems in NEXP. Natarajan and Wright showed you can ask more questions, showing that provers with entangled bits can convince a verifier of everything in NEEXP, non-deterministic double exponential time (\(2^{2^{n^c}}\)), already a proof too large for the verifier to even point into. The MIP* = RE paper takes that all the way to the computably enumerable sets, all the languages you would get with a classical prover convincing a deterministic verifier unrestricted by time.