Marko Petkovs̆ek (1955-2023), My A=B Mate

Doron ZEILBERGER

I have only met Marko a few times in my life, but he was a constant presence.

The first time was in 1991, in Philadelphia, shortly after he defended his Carnegie-Mellon PhD

under the logical giant Dana Scott (https://www.mathgenealogy.org/id.php?id=8024). Herb

Wilf invited Marko to speak at UPenn’s combinatorics seminar, about the amazing Petkovs̆ek algorithm. Both Herb and I were very excited about Marko’s algorithm, since that was the missing link needed by us to solve the at-the-time wide open decision problem for the existence of a closed-form solution for definite hypergeometric summation.

Recall that the famous Gosper algorithm [G] decides whether an indefinite sum

F (n) := ∑_{k=1}^{n} f(k) ,

where f(k) is a hypergeometric term (i.e. f(k + 1)/f(k) is rational function of k), is again hypergeometric. But what about definite summation, i.e.

F (n) := ∑_{k=0}^{n} f(n, k) ,

where f(n, k) is (proper) hypergeometric in both discrete variables n and k? So-called Wilf-Zeilberger Algorithmic Proof Theory, and the Zeilberger algorithm (see [PWZ]) can always find the next-best thing to a closed-form solution, a linear recurrence equation with polynomial coefficients, of some order L. In other words come up with L + 1 polynomials: p_{0}(n), p_{1}(n), …, p_{L}(n); such that

∑_{i=0}^{L} p_{i}(n) F (n + i) = 0 .

If the order, L, happens to be 1, then we know right away that F (n) is closed form (in the sense of being hypergeometric), but what if L > 1?

Zeilberger’s algorithm guarantees to output some recurrence of some order, but does not always give you the minimal order. In order to know for sure that there is no first-order recurrence, we need the amazing Petkovs̆ek algorithm Hyper [P1] [P2] [P3] [PWZ] (Ch. 8). That was exactly the missing ingredient that we needed to settle this important decision problem.

As Marko describes so charmingly in his reminiscences about Herb Wilf [CGH], this connection lead to our collaboration A=B [PWZ], whose table of contents was drafted in the Moosewood vegetarian restaurant, in Itacha, New York.

Marko then went on to become a leader in symbolic summation and difference equations, with very deep work in collaboration with Sergei A. Abramov, and others. He also wrote a charming paper with Herb Wilf about a ‘high-tech’ proof of an important identity in enumerative combinatorics [PW].

When Bill Chen organized a conference in Tianjin to celebrate my 60^{th} birthday, in the summer of 2010, he asked me whom to invite, and of course I suggested Marko, whom Bill dully invited. Unfortunately, Marko was unable to come, but instead wrote me this nice email.

From Marko.Petkovsek@fmf.uni-lj.si Sun Aug 8 17:30:52 2010
Dear Doron,
I was looking forward very much to the Zeilberger-fest at Nankai.  Alas, as it turned
out, I will not be able to attend it.  Last week I had a small operation on my leg
(nothing serious - removal of a large carbuncle probably caused by an insect bite),
but the wound has not healed yet and my doctor advised against traveling.
So, I just wish you a very happy |A_{5}|-th birthday!
Best regards,
--Marko

Last time I met Marko in person was during Herb Wilf’s 80^{th} Birthday conference, held May 26-29, 2011, in Wilfrid Laurier University, Waterloo, Canada, and organized by Eugene Zima and Ilias Kotsireas https://cargo.wlu.ca/W80/. Marko gave a great talk on enumeration of structures with no forbidden substructures that clearly showed that he had a very broad perspective of combinatorial enumeration. In his own words

(from https://sites.math.rutgers.edu/~zeilberg/akherim/W80abstracts.pdf ):

Many interesting classes of combinatorial structures are defined by restricting some general class of structures to those structures that avoid certain forbidden substructures. Examples include words avoiding forbidden subwords or subsequences, permutations avoiding forbidden patterns, matrices avoiding forbidden submatrices, graphs avoiding forbidden subgraphs, induced subgraphs, minors, or topological minors. We will try to look at the abundance of enumeration problems (solved and unsolved) presented by such classes.

Marko will be sorely missed, but his mathematics and algorithms guarantee his immortality.

References

[CGH] Fan Chung, Curtis Greene, and Joan Hutchinson [coordinating editors], Herbert S. Wilf (1931-2012), Notices of the American Mathematical Society 62(4) (April, 2015).

https://www.ams.org/notices/201504/rnoti-p346.pdf .

[G] Robert W. Gosper, Jr., Decision procedure for indefinite hypergeometric summation, Proc. Natl. Acad. Sci. USA, 75 (1978), 40-42.

https://sites.math.rutgers.edu/~zeilberg/akherim/gosper1978.pdf .

[P1] Marko Petkovs̆ek, Finding closed-form solutions of difference equations by symbolic methods, PhD. thesis, Carnegie-Mellon University, CMU0-CS-91-103, 1991.

https://sites.math.rutgers.edu/~zeilberg/akherim/petkovsekPhD1991.pdf .

[P2] Marko Petkovs̆ek, Hypergeometric solutions of linear recurrences with polynomial coefficients, J. Symbolic Computation 14 (1992), 243-264.

[P3] Marko Petkovs̆ek, A generalization of Gosper’s algorithm, Discrete Mathematics 134 (1994), 125-131.

[PW] Marko Petkovs̆ek and Herbert S. Wilf, A high-tech proof of the Mills-Robbins-Rumsey determinant identity, Electronic Journal of Combinatorics 3 (1996) no. 2, #R19.

https://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i2r19/pdf .

[PWZ] Marko Petkovs̆ek, Herbert S. Wilf, and Doron Zeilberger, “ A=B”, A.K. Peters, 1996.

https://www2.math.upenn.edu/~wilf/AeqB.pdf .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .

April 14, 2023.