Greg Egan and the Permutation Problem

“Then on September 26 of this year, the mathematician John Baez of the University of California, Riverside, posted on Twitter about Houston’s 2014 finding, as part of a series of tweets about apparent mathematical patterns that fail. His tweet caught the eye of Egan, who was a mathematics major decades ago, before he launched an award-winning career as a science fiction novelist (his breakthrough 1994 novel, in a happy coincidence, was called Permutation City). “I’ve never stopped being interested in ,” Egan wrote by email.

Egan wondered if it was possible to construct superpermutations even shorter than Houston’s. He scoured the literature for papers on how to construct short paths through permutation networks, and after a few weeks found exactly what he needed. Within a day or two, he had come up with a new upper bound on the length of the shortest superpermutation for n symbols: n! + (n-1)! + (n-2)! + (n-3)! + n-3. It’s similar to the old factorial formula, but with many terms removed.”

—Erica Klarreich. “Mystery Math Whiz and Novelist Advance Permutation Problem.” Quanta. November 5, 2018.

Greg Egan’s hard sci-fi novels are amazing. Axiomatic is a collection of short stories that can give you a sense of what to expect. Read Diaspora if you want to jump right into the deep end. Read Quarantine if you want to take on a series.