My First Paper with Dr. Z. : Bijective and Automated Approaches to Abel Sums

Combinatorics and more 2024-05-15

My new (and first!) paper with Dr. Z.

Gil Kalai and Doron Zeilberger, Bijective and Automated Approaches to Abel Sums

Abstract: In this tribute to our guru, Dominique Foata, we return to one of our (and Foata’s) first loves, and revisit Abel sums and their identities, from two different viewpoints.

abelblog

From left to right: John Majewicz, Doron Zeilberger, and Dominique Foata

Our preface to the paper: In the very first issue of Crelle’s journal (the first mathematical periodical solely dedicated to mathematics), Niels Henrik Abel published a two-page paper [A], stating and proving his eponymous identity. This lead to an intensive study of general Abel Sums by many people, (see [R] [C] and their numerous references), and to beautiful bijective approaches pioneered by Dominique Foata and Aimé Fuchs [Fo][FoFu] that led to Francon’s elegant proof [Fr] (see [C], p. 129). This tribute consists of two independent parts. The first part is bijective, while the second part is automated, elaborating and extending John Majewicz’s 1997 PhD thesis [M1][M2], and more important, fully implementing it (and its extension) in a Maple package.

The papers’ webpage on Doron’s web page has various complementary materials.

Some background – Abel’s identity.

Abel’s identity is:

$\displaystyle \sum_{k=0}^n {{n} \choose {k}} (k+x)^{k-1} (n-k+y)^{n-k} =\frac {1}{n+x}(n+x+y)^n$

In his book John Riordan extended the left hand side to a more general expression

$A_n(x,y;p,q)=$ $\displaystyle \sum_{k=0}^n {{n}\choose{k}}(k+x)^{k+p}(n-k+y)^{n-k+q}.$

Riordan referred as Cauchy’s formula to the following evaluation for $p=0,q=0$ :

$\displaystyle \sum_{k=0}^n {{n} \choose {k}} (k+x)^k (n-k+y)^{n-k}=\sum_{k=0}^n {{n} \choose {k}}k!(x+y+k)^{n-k}$

In 1972 I found a formula for $A_n(x,y;p,q)$ which gives for the special case $q=0$ the following identity:

$\displaystyle \sum_{k=0}^n {{n} \choose {k}} (k+x)^{k+p} (n-k+y)^{n-k} = \sum_{k=0}^n {{n} \choose {k}}(n+x+y)^{n-k} \Delta^kx^{p+k}.$

Here the difference operator $\Delta$ is defined by $\Delta f(x)=f(x+1)-f(x)$ . My general formula was

$\displaystyle A_n(x,y;p,q)=\sum_{k=0}^n {{n} \choose {k}} (k+x)^{k+p} (n-k+y)^{n-k+q} =\\ \sum_{k=0}^n {{n} \choose {k}}(n+x+y)^{n-k} (\Delta_x-\Delta_y)^kx^{p+k}(y+n-k)^q.$

It is a legitimate question in what sense does the right hand side of this general formula simplify the left hand side and I tried to justify it in the paper. The story of Riordan’s referee reports to my paper is told in this post. Since the paper appeared in 1979, it was cited once in an unpublished manuscript from 2018 by Darij Grinberg about non-commutative Abel-type identities, and now, once again by our paper.

Meeting Doron at the Weizmann Institute

In 1978, my mother made the decision to purchase a car. My parents had never owned a car before, and neither of them held a driving license. However, my mother resolved to buy a car and concurrently take driving lessons. At the time, I was nearing the end of my army service, and after passing successfully my (fifth) driving test, I participated in acquiring our family’s first Subaru, and for some time I was the sole driver.

In fall 1980, I was newly married, and a year into my graduate studies. We still used the Subaru for trips outside Jerusalem and on a particular day, my mother, sister (Tami) and me had planned to travel together to the Rehovot area. I intended to meet Doron, who was a new faculty member in Weitzman Institute (and already a well-known combinatorialist), while my mother and sister wished to visit some family and friends. (Come to think about it I don’t remember how the connection with Doron was made and not even if he expected my visit or I just showed up.) Shortly after we entered Doron’s office, my mother began to display impatience and reminded me of our scheduled commitments.

“Madam Kalai (גברת קלעי)” said Doron. “Your son is a m-a-t-h-e-m-t-i-c-i-a-n and he came here especially to talk and work with me. I suggest that you and Tami take a leisurely stroll in the lovely gardens of the Weizmann Institute for an hour, and then return to continue your journey with Gil.”.

I was flattered by Doron’s words, but to my surprise, my mother was also flattered. Indeed, she and my sister left us for a significant amount of time to engage in conversation about mathematics. Doron shared various interesting insights and even showed me a draft of his paper on Sister Celine’s method. I believe that this draft marked one of the initial stages of the renowned WZ theory. When my mother and sister came back Doron showed Tami how to prepare certain types of origami, and then we continued in our trip plans.

Here is a nice combinatorial identity

I mentioned to Doron a special case of (Cauchy’s) Abel-type identity.

$\displaystyle \sum_{k=0}^n {{n} \choose {k}} k^k (n-k)^{n-k} = \sum_{k=0}^n {{n} \choose {k}} k! n^{n-k}$ ,

and wondered about a simple bijective proof. The two sides have a clear combinatorial interpretation: The left hand side is the number of pairs $(A, f)$ where $f:[n] \to [n]$ , $f(A) \subset A$ and $f(\bar A) \subset \bar A$ ; the right hand side is the number of pairs $(B, f)$ where $f:[n] \to [n]$ and $f(B) = B$ .

A few weeks later I got a postcard from Doron. He wrote me that for every function $f$ there is a bijection between the $A$ ‘s and the $B$ ‘s, given by

$B=f(f(f(\cdots f(A))))),$

and

$A=f^{-1}(f^{-1}(\cdots f^{-1} (B))))))$ .

This is very beautiful!

[Comment: the dots means apply until it stabilizes…]

Doron attributed the method to Dominique Foata and this bijection and an extension of it is the basis of the first part of our new paper. (After my first visit, I visited Doron a couple of other times at WI, once, still as a student, he invited me to give a colloquium there, and since then our paths met many times.)

The second part of our paper deals with automatic proofs for Abel-type identities following John Majewicz’s 1997 PhD thesis. Of course, automated proofs is a very large and very important topic, and Doron is one of its pioneers. A question that comes to mind is if the process of finding bijective proofs can also be automated. Timothy Chow raised this question over MathOverflow six years ago: Automated search for bijective proofs.

Top from left to right: Marko Petkovsek, Herbert Wilf, Doron and Donald Knuth, and the cover of the book A=B. Bottom: Sister Celine Fasenmyer, Exercise 1.2.6.23 in Knuth’s AoCP part I, and Knuth’s forward. The forward starts with: “Science is what we understand well enough to explain to a computer. Art is everything else we do.”

Here is a trivia question: There are two notable figures in the A=B story (both are mentioned in the book) whose names differ by a single vowel, who are they? 0-knowledge answers please!