Written: June 24, 2018
This is a tribute to George Andrews's forthcoming 80th birthday. Ch IV was especially inspired by his pioneering work in Computer Algebra, described in Chapter 10 of his classic "q-Series: Their Development and Applications in Analysis, Number Theory, Combinatorics, Physics, and Computer Algebra", CBMS series Number 66, American Mathematical Society, 1986.
In my plenary talk, delivered June 22, 2018, 9:20-10:10am, entitled
"Computer Algebra: from `Pencil with Power-Steering' to `Self-Driving Pencil'",
delivered at this historic conference, I sketched George Andrews' pioneering use of computer algebra, described in his masterpiece, where he solved a conjecture that occurred in "nature" in "high-brow" mathematics posed by famous mathematicians (Lusztig, Macdonald, and Wall).
In that conjecture, a sequence of polynomials in q, Xn(q) was given in terms of rather complicated recurrences, and one had to prove that the limit as n goes to infinity, is a certain q-series. Using the computer algebra system SCRATCHPAD, as a "pencil with power-steering", George Andrews described step-by-step, the discovery process that lead him to an explicit expression, in terms of the Gaussian polynomials (the `building blocks' of q-series, to use Andrews' words). Once the so-called q-binomial sum was conjectured, taking the limit was immediate. According to George, conjecturing the expression for Xn(q) was 90 percent of the battle, while the remaining 10 percent followed from "standard q-series methods". They may be standard for George, but not as `standard' to ordinary mortals. Today, however, one does not have to be a George Andrews to finish it up, one can use the amazing Maple package qEKHAD.txt (that uses a crucial "six-year-old-Gauss" `symmetrization trick' discovered by Peter Paule), or the powerful Mathematica package qZeil written by Axel Riese.
George's Andrews' solution of the L-M-W conjecture suggested the following fool-proof algorithm for getting tenure for young people. Suppose that Dr. Fresh PhD just got a tenure-track position and would be up for tenure in six years. He or she should use the q-Zeilberger algorithm (using, e.g., qEKHAD.txt), to figure out a complicated recurrence for some random complicated q-binomial sum, put it in safe place! Then email Abel-prize winner, Professor Fancy Famous, and ask him to pose a conjecture that the sequence defined by the recurrence has a certain explicit limit (similar to, but possibly more complicated than the L-M-W conjecture), and claim that this would entail important consequences in high-brow mathematics. Then six years later, when Dr. Fresh PhD is up for tenure, he would publish an earth-shattering article
"Proof of Fancy Famous' Conjecture"
and would not only get tenure in his or her current university, but at Princeton and Harvard.
This inspired this e-book, where it is easy to concoct very hard problems, to which you already know the answers beforehand. This lead to Chapter IV, directly mimicking the L-M-W conjecture. Unfortunately (to Dr. F. PhD), George Andrews' strategy may be used, and automated, so Fresh PhD may get scooped by other ambitious people, that would lead them to discover the sum, and hence getting the credit for proving Professor Famous' conjecture. So, on second thought, it is not such a safe strategy for getting tenure.
A safer way would be to use a problem in the style of Chapter III, using the ordinary Zeilberger algorithm, rather than the q-Zeilberger algorithm, for which it is much harder to do "reverse engineering" à la George.
The theme here is "One-Way functions", hence the title of this e-book. One- Way functions became famous thanks to the RSA algorithm, and this lead to Chapter I, and in a different context Chapter II (take several random multi-variable polynomials, add their squares, expand, and get a multi-variable polynomial that you know for sure is non-negative, and you can prove it (since you made it up), but for anyone else it would take years.).
At the end of my talk, George Andrews asked me, "you only talked about the first part, the power-steering part, what about the second part?, the `self-driving pencil'?". And indeed, since I don't use slides, and never prepare my talks, I ran out of time, so the second part would have to wait to AndrewsFest85.