%mpm.tex: Marko Petkovsek, My A=B Mate
%%a Plain TeX file  Doron Zeilberger (x pages)

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\centerline
{\bf Marko Petkov${ {\bf \breve s}}$ek (1955-2023), My A=B Mate}
\bigskip
\centerline
{\it 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 ({\tt https://www.mathgenealogy.org/id.php?id=8024}). 
Herb Wilf invited  Marko to speak at UPenn's combinatorics seminar, about the amazing
{\it Petkov${{\it \breve s}}$ek algorithm}. Both Herb and I were very excited about Marko's
algorithm, since that was the {\it missing link} needed by us to solve the at-the-time
{\it wide open} {\bf decision problem} for the existence of a closed-form solution 
for {\bf definite hypergeometric summation}.

Recall that the famous Gosper algorithm [G] decides whether an {\it indefinite} sum
$$
F(n):=\sum_{k=1}^{n} f(k) \quad,
$$
where $f(k)$ is a {\it hypergeometric term} (i.e. $f(k+1)/f(k)$ is {\bf rational function} of $k$), is again hypergeometric.
But what about {\bf definite summation}, i.e.
$$
F(n):=\sum_{k=0}^{n} f(n,k) \quad,
$$
where $f(n,k)$ is (proper) hypergeometric in {\bf both} discrete variables $n$ and $k$? So-called {\bf Wilf-Zeilberger Algorithmic Proof Theory}, and the {\bf Zeilberger algorithm} (see [PWZ]) can
always find the next-best thing to a closed-form solution, a {\bf linear recurrence equation with polynomial coefficients}, of {\it some} {\bf order} $L$. In other words come up with
$L+1$ polynomials:  $p_0(n), p_1(n), \dots, p_L(n)$; such that
$$
\sum_{i=0}^{L} p_i(n) \, F(n+i) \, = \, 0 \quad .
$$
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 {\it some} recurrence of {\it some order}, but does {\bf not} always give you the {\bf minimal order}. In order to know for {\bf sure}
that there is no first-order recurrence, we need the amazing   {\bf Petkov${{\bf \breve s}}$ek algorithm Hyper} [P1] [P2] [P3] [PWZ] (Ch. 8).  That was exactly the
missing ingredient that we needed to settle this important {\bf decision problem}.

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

Marko then went on to become a leader in {\bf symbolic summation} and {\bf 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].

\bigskip

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.

{\tt
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
{\tt https://cargo.wlu.ca/W80/}. Marko gave a great talk on  {\it enumeration of structures with no forbidden substructures} that
clearly showed  that he had a very broad perspective of combinatorial enumeration.
In his own words  \hfill\break
(from  {\tt  https://sites.math.rutgers.edu/\~{}zeilberg/akherim/W80abstracts.pdf} \quad):

{\it 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 {\bf immortality}.


{\bf References}

[CGH] Fan Chung, Curtis Greene, and Joan Hutchinson [coordinating editors], {\it Herbert S. Wilf (1931-2012)},
Notices of the American Mathematical Society {\bf 62(4)} (April, 2015).
\hfill\break                                        
{\tt https://www.ams.org/notices/201504/rnoti-p346.pdf} \quad .


[G] Robert W. Gosper, Jr., {\it Decision procedure for indefinite hypergeometric summation}, Proc. Natl. Acad. Sci. USA, {\bf 75} (1978), 40-42. \hfill\break                                        
{\tt  https://sites.math.rutgers.edu/\~{}zeilberg/akherim/gosper1978.pdf} \quad .

[P1]  Marko Petkov${\breve s}$ek, {\it Finding closed-form solutions of difference equations by symbolic methods}, PhD. thesis, Carnegie-Mellon University, CMU0-CS-91-103, 1991. \hfill\break                                        
{\tt  https://sites.math.rutgers.edu/\~{}zeilberg/akherim/petkovsekPhD1991.pdf} \quad .

[P2]  Marko Petkov${\breve s}$ek, {\it  Hypergeometric solutions of linear recurrences with polynomial coefficients},  J. Symbolic Computation {\bf 14} (1992), 243-264.

[P3]  Marko Petkov${\breve s}$ek, {\it  A generalization of Gosper's algorithm},  Discrete Mathematics {\bf 134} (1994), 125-131.

[PW] Marko Petkov${\breve s}$ek and Herbert S. Wilf, {\it A high-tech proof of the Mills-Robbins-Rumsey determinant identity}, Electronic Journal of Combinatorics {\bf 3} (1996) no. 2, \#R19. \hfill \break
{\tt https://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i2r19/pdf} \quad.

[PWZ] Marko Petkov${\breve s}$ek, Herbert S. Wilf, and Doron Zeilberger, {\it `` A=B''}, A.K. Peters, 1996.\hfill\break
{\tt https://www2.math.upenn.edu/\~{}wilf/AeqB.pdf} \quad .

\bigskip
\hrule
\bigskip
Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill\break
Email: {\tt DoronZeil at gmail  dot com}   \quad .
\bigskip
April 14, 2023.

\end

