I thought this recent article was a great demonstration that the creativity, diligence and playfulness that are encouraged in Math Circle can also be a part of a rewarding career.
UT Dallas Team’s Approach to an Old Problem is Praised as ‘Elegant’
Two UT Dallas computer scientists have made progress on a nearly 4-decade-old mathematical puzzle, producing a proof that renowned Stanford computer scientist Don Knuth called “amazing” in his communication back to them.
Created by the mathematician John Conway and known as Topswops, the puzzle starts like this: Begin with a randomly ordered deck of cards numbered 1 to n, with n being however high a number you choose. Now count out the number of cards represented by whatever card is the top card, and turn that block of card
s over on top of the remaining cards. Then count out the number of cards represented by the new top card and turn this whole block over on top of the remaining cards. Repeat until the card numbered 1 comes to the top (realizing that we know the card numbered 1 will always eventually come to the top).
Now here’s what needs to be done: Calculate the maximum and minimum number of steps required with n number of cards.
Knuth had previously proved an exponential upper bound on the number of Topswops steps, and conjectured that one might also prove a matching lower bound. What Dr. Hal Sudborough and Dr. Linda Morales did, however, was to prove a lower bound that is much better than that proposed in Knuth’s conjecture, and Knuth declared their proof technique both “elegant” and “amazing.”
“What I find fascinating about a problem such as bounding the Topswops function is connected to its simplicity, to its fundamental nature, and to the complexity and difficulty of finding an answer,” said Sudborough, the Founders Professor at the Erik Jonsson School of Engineering and Computer Science. “An easily described, easily communicated problem is invaluable for engaging a wide array of participants, from high school students to the most eminent mathematicians.”
He also cited Martin Gardner, a longtime columnist for Scientific American, who wrote of problems such as Topswops, “Let it not be supposed that those Conway card games are trivial. They deal with the theory of set permutations and not only may provide deep theorems but also may have a bearing on practical problems that arise in seemingly unrelated fields.”
And then there’s the sheer mathematical beauty that the problem reveals.
“The Topswops process is a simple one,” said Morales, a senior lecturer in computer science. “The basic algorithm is easily understood by almost anyone, regardless of their training or interests. But the simplicity is deceptive. Hiding behind it is a mathematical world of unexpected richness and beauty. Our research uncovered permutations whose iterate sequences have a fascinating structure, which upon analysis have revealed hitherto unknown lower bounds for the problem. There is much more to learn from the problem. We have tantalizing hints of more revelations just waiting to be uncovered.”
Metroplex Math Circle 
UT Dallas Researchers Continue
Related Work on Topswops Problem
In a related issue, Sudborough, Morales and their graduate students have also computed the maximum number of Topswops steps over all permutations of length n for small integers n.
Because there are more than 355 trillion different permutations of length 17, a brute force approach of trying all such permutations, one after the other, would require months of computation time. Knuth, who had previously computed the exact number for n=16, used a new, innovative approach, which allowed much shorter computation times. The UT Dallas group made several additional improvements and was able to determine that permutations of length 17 require at most 159 Topswops steps.
And their new technique required only a few days of computation. They have continued by also showing there is a permutation of length 18 that terminates with all cards in sorted order in 191 Topswops steps and that no such permutation of length 18 takes more than 191 steps. Why is that a noteworthy achievement of computational performance? Because there are more than 6 quadrillion permutations of length 18.
I agree that this is great stuff, but “What Dr. Hal Sudborough and Dr. Linda Morales did, however, was to prove a lower bound that is much better than that proposed in Knuth’s conjecture” seems totally wrong to me. Knuth’s conjecture is that there is an exponential lower bound to match the exponential (Fibonacci) upper bound. Sudborough and Morales found a quadratic lower bound, and their method is ingenious, but practically there seem to be known permutations that are much better than the lower bound they’ve proved, and quadratic is a long way from exponential. They have a great breakthrough here but the question of whether an exponential lower bound exists is still open. Their lower bound is much weaker than the one that Knuth conjectures to exist, but of course they have a theorem and Knuth only a conjecture!
Oops, my comment just previously was based on some ignorance on my part.
The article posted here said Knuth had conjectured a “matching lower bound”, which I took to mean also exponential like the upper bound.
However I read elsewhere that Knuth had conjectured not a lower bound but that in fact that the maximum length grows only linearly, in which case the discovery of the quadratic is a disproof of his conjectured *upper* bound.