Having turned 18, I have now swapped out the impromptu school parties with their questionable music, eccentric concoctions which come about after a few drinks—Shloer, vodka and salad dressing, anyone?—and soon-to-be sticky carpets, to attend city centre institutions with equally interesting music, drinks and floor-al adhesion.
I and a group of close friends (who will be referred to as A, B, C, D throughout, leaving me as E) decided to paint the town red and celebrate the arrival of my newfound rights to drink, drive a forklift truck, and go bungee jumping (though not simultaneously). We decided unanimously on a venue whose name I will refrain from mentioning (as I am certain I saw the bouncer doing the Chalkdust prize crossnumber, and hence may be liable to read this article).
We approached the bar, and the bartender—thrilled for what must have been their first clientele of the night—took our orders with great gusto. Although the bartender was blessed with many things, short-term memory was not among them: each order was perfectly procured, but much like the pianist who could play all the right notes but not necessarily in the right order, the hapless bartender had no clue which order was whose. In fact, by some combinatorial miracle, he managed to give everyone the wrong drink: whereas it ought to have gone ABCDE, instead, he went DAECB.
“Just our luck,” said C, exasperatedly.
“A derangement no less.” said D.
“Who are you calling deranged?” responded B indignantly.
“No—a derangement—a kind of permutation,” I explained to defuse the situation.
“What’s a permutation?” pondered D thoughtfully.
“It’s simply a bijection $\pi: \{1, \dots, n\} \rightarrow \{1, \dots, n\}$: a map sending each element of $\{1, \dots, n\}$ to a different element,” I explained.
“Right-o. But a derangement?” enquired B.
“A derangement is a permutation without fixed points: so $\pi(i) \neq i$ for all $1 \leq i \leq n$.” I answered.
Deranged or otherwise, we needed to work out how to return the beverages to their rightful owners. Our attempt to slide them across, wild west style, was scuppered by one inadvertent collision and the stern eye of the bouncer (who was getting started on the across clues) so we decided to work it out rigorously. While most people would get off their seats and swap drinks, we mathematicians know that no night out is complete until it becomes a maths problem. We may make things difficult for ourselves—but at least we’ll get a paper out of a night out.
“Let’s set some ground rules,” said C, enjoying his newfound role as leader. “Rule one: we must return our drinks in some series of swaps. Rule two: people may only swap with their immediate neighbour to prevent any collisions. Rule three: people may not engage in two swaps at once or have more than one drink at once. That constitutes cheating, and will result in the aforementioned cheater being required to buy everyone a round of drinks. And rule four: we will carry this out with a minimal number of swaps to prevent anyone from ‘sampling’ someone else’s drink. I know who you are,” he said, eyeing A suspiciously.
With this, we took our seats and set to work, drawing frenzied diagrams on cocktail napkins with whatever we had to hand.
Ticket to ride
I stared quizzically at my sketches, resisting the urge to sip the Guinness which had been placed before me. “We can guarantee we will only need to do at most 10 swaps if we don’t need to swap each drink more than once.”
“Actually, only six pairs of drinks are in the wrong order,” added B.
“What do you mean, ‘the wrong order’?” I asked.
“I mean that for our permutation, there are only six pairs of people X and Y such that X sits to the left of Y but X’s drink is to the right of Y’s—like A and D. So, at some point, the drinks will have to cross past each other.”
As I struggled to make sense of this, A made a suggestion. “Let’s use some shorthand to make it slightly easier. How about we use $\sigma_i$ to denote the swap between the $i$th and $(i + 1)$th person, counting from A to E.”
“So a total of $n-1$ kinds of swap for $n$ people,” I added.
“Right,” replied A. “And when we do more than one swap, we work from left to right—because we’re indexing positions of drinks, not the drinks themselves.” We agreed this was a splendid idea.
“We can actually draw out an exact map of how to do this, and which exchanges to do… like a tube map!” said D, drawing the following diagram:
“All you need to do is draw lines between the drink and its destination. All the points at which the drinks should ‘collide’ give you the exact order in which we should exchange our drinks. So we can actually trace which drinks go where and when—like a tube map for cocktails!” said C, brimming with excitement.
“And lo and behold… only six exchanges, like you said!” chimed in B.
“Lower bound and upper bound: since the lines will only cross precisely when their drinks start on the wrong side, it’s optimal!” A surmised.
“And we can read off the orders of drinks as follows: DAECB, ADCEB, ADCBE, ADBCE, ABDCE, ABCDE. Hey presto—six swaps, like you said!” exclaimed C.
“Or, with our newfound notation, simply $\sigma_1 \sigma_3 \sigma_4 \sigma_3 \sigma_2 \sigma_3$.” B added.
We tried it, and lo and behold, our drinks were returned to the right order.
I continued: “So we can write a formula for the number of swaps in general: for any permutation $\sigma$, where the $i$th element is notated $\sigma(i)$, the number of exchanges we need to use is
\[|\{i < j: \sigma(i) > \sigma(j)\}|\text{.}\]
“And so for five drinks, we’ll never need more than 10 swaps—because we only have $\left(\begin{smallmatrix}5\\2\end{smallmatrix}\right) = 10$ pairs $\{i, j\}$ where $1 \leq i < j \leq 5$," parried B. "Which could happen if we started out with EDCBA,” added A.
They’re the same picture
While we supped our drinks, C opined the following.
“I think the diagram is rather splendid, because we can actually prove things with the diagrams themselves.”
“How so?” I asked.
“Well, say we wanted to multiply out two permutations. We can just stack them up like so:”
“But then how would you undo it?” asked A, unsatisfied.
“By reflecting the diagram, top-to-bottom,” C countered.
Yet D looked suspicious. “But surely your diagrams aren’t unique—you can change the diagram, but the permutation remains the same. How else could we have done this?”
“If you do a swap twice, it undoes itself: that checks out from the diagram!” said B, drawing the following:
“For some pairs of swaps, like you mentioned, it doesn’t matter which order we do them—they may as well have been in either order, or at the same time,” said A.
“So we could say $\sigma_i \sigma_j = \sigma_j \sigma_i$,” I surmised. “And that would look a little like this:” I added, displaying my proof:
“But that only happens if $i$ and $j$ are at least 2 apart. So what if they are next to each other?” A asked trenchantly.
“There’s an even cleverer one. If we have a permutation like $\sigma_i \sigma_{i + 1} \sigma_i$, we can ‘pick up’ the middle strand and place it over the other two without changing the result of the permutation, and get $\sigma_{i + 1} \sigma_i \sigma_{i + 1}$ back.” intoned C. “Like this:”
“Or equivalently, $(\sigma_i \sigma_{i + 1})^3$ should return everything to where it started, since both $\sigma_i \sigma_{i + 1} \sigma_i$ and $\sigma_{i + 1} \sigma_i \sigma_{i + 1}$ swap drinks $i$ and $i + 2$,” I added.
In the heat of excitement, C urged A and B to show him in order to demonstrate this. The drinks had returned like clockwork.
“So we now have a set of rules for our permutations: we have permutations $\sigma_i$ for $1 \leq i \leq n$ such that:
- $\sigma_i^2 = 1$ (where $1$ is just the identity permutation);
- $\sigma_i \sigma_j = \sigma_j \sigma_i$ if $|i-j| > 1$; and
- $\sigma_i \sigma_{i + 1} \sigma_i = \sigma_{i + 1} \sigma_i \sigma_{i + 1}$,”
summed up C. “Or, alternatively, $(\sigma_i \sigma_{i + 1})^3 = 1$ and $(\sigma_i \sigma_j)^2 = 1$ otherwise.”
“And we can get to any diagram of any permutation we want this way?” B enquired.
“Using C’s diagram idea.” I offered.
“So we’ve given a full description of the collection of permutations!” D said, eagerly awaiting their drink.
We sat in awe of our realisation.
You’ve really made the braid
Then C once again saw fit to throw the cat among the pigeons. “Hold on. Let’s go back to the original diagrams. What if they were actual pieces of string?”
“So the strands would go over and under each other?” asked D.
“Right. You’d multiply and take inverses just like we did earlier—so it’s as well-defined as our diagrams,” replied C.
“If you did a swap twice, you wouldn’t get the same thing back—it would be all tangled!” I said, drawing a version of our original map:
“Braided!” suggested C.
“Ah—but we’d still have our previous rules, that $\sigma_i \sigma_j = \sigma_j \sigma_i$ if $|i-j| > 1$, and $\sigma_i \sigma_{i + 1} \sigma_i = \sigma_{i + 1} \sigma_i \sigma_{i + 1}$.” A elicited.
“In fact, I don’t think we can say anything more—these are the only ways we can move any of the strands without tangling our strings. So that’s it—that’s our new algebra,” I concluded.
To be or knot to be
Then D picked up his bar napkin and made it into a loop: “What if we joined the ends together?” he asked.
“We get some kind of knot—or maybe a link if there happens to be more than one connected component,” said B:
“Could we get any kind of knot like that? And which braids give us the same thing?” I asked.
“Well, I suppose if you did braids $\sigma \tau$, it would be the same as doing $\tau \sigma$—we would just loop round and get the same thing back, because it doesn’t matter where you start,” said C:
“And if we add an extra strand, $\tau \sigma_n$ on $n + 1$ strands should look the same as $\tau$ on $n$ strands,” I added:
“Wait—this all feels an awful lot like physics.” D said. “Imagine we watch how our drinks proceed at some point in time. Your original diagram, C, shows us the worldlines of the individual drinks as they pass through time from top to bottom, like frames in a movie:”
“But originally, if we swapped them twice, we would get the same thing back.” A replied. “Now, if we swap them twice, the particles would remember what they were swapped with! In fact, you could make a computer with these—they would store the way in which they were exchanged!”
“No more—you’re giving me a headache!” implored B.
Hexagonator the almighty
“But how could we do this?” I asked.
“Say we have 5 particles, say, A, B, C, D and E. We denote their states by $|A\rangle$ and so on.” said C. “We’d write $|A\rangle \otimes |B\rangle$ for the superposition of two particles.”
“And this would be different from $|B\rangle \otimes |A\rangle$?” I enquired.
“Yes,” replied C, “but we’d need some kind of operator $b_{A, B}$. One which would do \[|A\rangle \otimes |B\rangle \rightarrow |B\rangle \otimes |A\rangle.\text{“}\]
“And if you did it twice with our braided particles, you wouldn’t get the same configuration back,” added A.
“What about if we have three particles? Wouldn’t \[(|A\rangle \otimes |B\rangle) \otimes |C\rangle\] give us the same thing as \[|A\rangle \otimes (|B\rangle \otimes |C\rangle)\text{?”}\] I asked.
“Ah, but they’re not—be careful,” said D, toyingly. “We’d need some kind of map, $a_{A, B, C}$ which would carry out \[(|A\rangle \otimes |B\rangle) \otimes |C\rangle \rightarrow |A\rangle \otimes (|B\rangle \otimes |C\rangle)\] for us.”
“Call it the associator! I like the sound of that—like a superhero,” I said.
“There’s another way of seeing this,” added A. “This all sounds an awful lot like a category—a collection of objects (like our particles) and maps, or morphisms (like our $a$ and $b$ maps) between them.
“And since this superposition malarkey is associative, we have a monoid.”
“So our particles form a braided monoidal category!” I surmised.
“I remember reading about this—there’s a couple of results it should always satisfy… Ah, here’s one:” said D, scrawling across two napkins and a beer mat (overleaf).
“A hexagon diagram!” I added.
“What about the three equivalences C found earlier?” raised B, gesturing to the discarded diagram. “Couldn’t we encode this in our new categorical form?”
“Just considering the strands, swapping the first pair and fixing the third is simply $b_{A, B} \otimes 1_C$. That’s like our $\sigma_1$,” said C.
“Right… and similarly if we swap the second two, we get $1_A \otimes b_{B, C}$ —like our $\sigma_2$,” returned B.
“So,” said D, “our relation looks a little like this, up to association:
\begin{align*}
(1_A\otimes b_{B, C})(b_{A, C} \otimes 1_B)(1_C \otimes b_{A, B}) \hspace{2cm} \\ \hspace{1.6cm} = (b_{A, B} \otimes 1_C)(1_B \otimes b_{A, C})(b_{B, C} \otimes 1_A)\text{.”}
\end{align*}
“And that’s just the Yang–Baxter relation from theoretical physics!” A added.
“But what does that mean?” B asked.
“Having this relation in 2 dimensions (1 spacelike plus 1 timelike) means that a system will have certain quantities fixed—such as the momentum remaining the same in each particle—which is called being integrable,” answered A.
“Moreover, if we have a system in which 3 or more particles are scattering we can always reduce it to an equivalent system of 2 particles,” added C. “In fact, one can do a similar trick in higher dimensions—but unfortunately this beer mat is too narrow to contain such an explanation.”
“Isn’t it just remarkable how many different ways there are of seeing the same thing, just from considering our drinks?” I remarked, satisfied with the night’s work.
“Isn’t it just,” said B. “Now, whose round is it next?”
* I was planning on naming this “Merry Twist-mas” after the oft-overlooked masterpiece by The Marcels, which is objectively the best Christmas song of all time. Alas, the timing was not to be.
More from Chalkdust
In conversation with Jens Marklof
Bethany Clarke and Enric Solé-Farré chat to the professor and new president of the London Mathematical Society about academia, access and awards
Markov unchained
Ashleigh Wilcox looks for integer solutions to the Markov equation
Significant figures: Sofya Kovalevskaya
Nora Koparan tells the story of the first female professor of mathematics
A daredevil’s disaster
Donovan Young goes round the bend exploring what happens when the loop-the-loop goes wrong
We don’t talk about the integers
Simone Ramello explores the hic sunt leones of the friendliest numbers we know...
A day in the life: teachers
We talk to three teachers, working in different countries