Given is a bag of natural numbers, e.g. {0, 0, 1, 1}. The goal is to generate, one by one, each permutation of this bag once, such that the next permutation differs from the preceding permutation by a neighbor swap, i.e., by transposing two adjacent numbers. For example, 0011 and 0101 (when the numbers are small, we juxtapose them in a permutation) differ by a neighbor swap, but 0011 and 1001 not. Since the early 1990s it has been known for which bags of numbers this is possible. For {0, 0, 1, 1} it is not possible. In 1965, Derrick H. Lehmer conjectured that when it is not possible, a small relaxation of the problem makes it possible, viz. by allowing a permutation to occur twice by undoing a neighbor swap in the next step. Such a side step he called a “spur”. For {0, 0, 1, 1}, we can then even create a cycle: 0110, 0101, 0011 (spur tip), 0101, 1001, 1010, 1100 (spur tip), 1010, 0110 (back). In 2016, I proved Lehmer’s conjecture for the binary case. Currently, master student Max Opperman is completing the proof for the general case.

In this colloquium, I will explain how I ran into this problem and highlight some of the proof techniques that we used.