An Empirical Method for Solving (rigorously!) Algebraic Functional Equations Of the Form F(P(x,t), P(x,1),x,t)=0
By
Ira M. Gessel and Doron Zeilberger
.pdf
.ps
.tex
First Posted: Dec. 28, 2014; Last update (of this page, not the article): Feb. 15, 2015.
[Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, Ira Gessel's website, and arxiv.org]
Added Jan. 2, 2019: Colin R. Defant, from Princeton University correctly pointed out that there is an issue with the
current version. There is a hidden assumption that the functional equation in question should be solvable
in the ring of formal power series. I believe that once this hidden assumption is made explicit, then
everything will work out.
CNRS Silver-medalist, Mireille Bousquet-Mélou, in a recent talk, lamented `Adieu l'élégance'.
The proofs produced by the Maple package described in this article are indeed far from `elegant', for most
humans, but the method sure is meta-elegant, since it is so simple!
This is a long overdue fullfilment of a promise made in 1991, where it was referenced in
this article, labeled "in planning".
But it was good that it took so long, since now computers are so much faster, and we are much better
programmers.
Added Feb. 13 and Feb. 15, 2015: Mireille Bousquet-Mélou beat us in our game! She sent us
a `one-line' maple code (that for some cases needs to be adjusted to a few more lines, to get
rid of extraneous factors) that finds algebraic equations without any guessing!
See her email messages.
While Mireille won this battle, and in this case, our guessing approach was not necessary, and human cleverness
won (of course, still with the assistance of computers!), the main point of our article was methodological,
and in the long run, we will win the "war", and our empirical and naive approach would rule.
Better still, both sides will be winners, and collaborate!
Maple Package
Some Input and Output files for the Maple package FunEq
-
If you want to see, the solution of the Functional Equation (derived by Doron Zeilberger) that
enumerates (when you set the catalytic variable, y, to be 1), the number of 2-stack-sortable permutations
the input yields
the output
-
If you want to see, the same as above but with a COMPLETELY RIGOROUS PROOF
the input yields
the output
-
If you want to see, a webbook that tries to find
algebraic equations satisfied by the generating functions enumerating Alpha(a,b) Description trees
with 0 ≤ a,b ≤ 6, that can be obtained by using 40 terms as "training data", and
the implied linear recurrence equation for the enumerating sequence itself, provided that
Degree of the coefficients plus the ORDER are ≤ 10, and then prints out the
first 30 terms, and the 100-th term
the input yields
the output
-
Same as above, but only for 0 ≤ a,b ≤ 3, but using 50 terms as training data, and
the Degree+Order ≤ 20. In other words,
if you want to see, a webbook that tries to find
algebraic equations satisfied by the generating functions enumerating Alpha(a,b) Description trees
with 0 ≤ a,b ≤ 3, that can be obtained by using 50 terms as "training data", and
the implied linear recurrence equation for the enumerating sequence itself, provided that
Degree of the coefficients plus the ORDER are ≤ w0, and then prints out the
first 30 terms, and the 100-th term
the input yields
the output
-
If you want to see, a webbook that tries to find
algebraic equations satisfied by the generating functions enumerating Beta(a,b) Description trees
with 0 ≤ a,b ≤ 6, that can be obtained by using 40 terms as "training data", and
the implied linear recurrence equation for the enumerating sequence itself, provided that
Degree of the coefficients plus the ORDER are ≤ 10, and then prints out the
first 30 terms, and the 100-th term
the input yields
the output
-
Same as above, but only for 0 ≤ a,b ≤ 3, but using 50 terms as training data, and
the Degree+Order ≤ 20. In other words,
if you want to see, a webbook that tries to find
algebraic equations satisfied by the generating functions enumerating Beta(a,b) Description trees
with 0 ≤ a,b ≤ 3, that can be obtained by using 50 terms as "training data", and
the implied linear recurrence equation for the enumerating sequence itself, provided that
Degree of the coefficients plus the ORDER are ≤ w0, and then prints out the
first 30 terms, and the 100-th term
the input yields
the output
-
If you want to see many examples of the Gessel-Zeilberger empirical-yet-rigorous method
described in the article, obtained by "perturbing" the functional equations for
Beta(a,b) description trees for a few choices of (a,b),
the input yields
the output
-
If you want to see many examples of the Gessel-Zeilberger empirical-yet-rigorous method
described in the article, obtained by "perturbing" the functional equations for
Alpha(a,b) description trees for a few choices of (a,b),
the input yields
the output
-
If you want to see many examples of the Gessel-Zeilberger empirical-yet-rigorous method
described in the article, obtained by "perturbing" the functional equation for
the functional equation that enuerates 2-stack-sortable permutations
the input yields
the output
-
If you want to see the algebraic equation and the first-order recurrence for
Tutte's famous generating function for counting maps
the input yields
the output
-
[Added, Feb. 13, 2015, after attending Jonathan Bloom's Feb. 12, 2015 fascinating
talk [part 1, part 2]
at the famous Rutgers University Experimental Mathematics Seminar].
To see a discovery, and PROOF, a solution of a Functional Equation that came up in
Jonathan Bloom and Alex Burstein's
article,"Egge triples and unbalanced Wilf-equivalence"
print(`Eq. (2.5), pages 6-7 `):
the input yields
the output
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page