SF Writer Greg Egan & Mystery Math Whiz Advance Permutation Problem
November 7, 2018 12:36 PM Subscribe
A new proof from the Australian science fiction writer Greg Egan and a 2011 proof anonymously posted online are now being hailed as significant advances on a puzzle mathematicians have been studying for at least 25 years. 1600 words from Erica Klarreich in Quanta Magazine.
I went through the mathematics department at the University of Western Australia a few years after Greg Egan. He was very much noticed and remembered by the lecturers there at the time.
posted by drnick at 1:01 PM on November 7, 2018
posted by drnick at 1:01 PM on November 7, 2018
The only author more likely to have a significant mathematical result than to have plausible three-dimensional protagonists.
I kid!
posted by leotrotsky at 1:22 PM on November 7, 2018 [4 favorites]
I kid!
posted by leotrotsky at 1:22 PM on November 7, 2018 [4 favorites]
I kid!
You say that, but his characters do seem to spend a lot of time in either higher-dimensional or lower-dimensional spaces.
posted by solarion at 1:49 PM on November 7, 2018 [2 favorites]
You say that, but his characters do seem to spend a lot of time in either higher-dimensional or lower-dimensional spaces.
posted by solarion at 1:49 PM on November 7, 2018 [2 favorites]
When I interviewed at Facebook, they seemed obsessed with permutation questions, even though it’s a thing that doesn’t come up much in actual work. Maybe they wanted to predict all possible ways they could fuck their users in all combinations. (OK I didn’t get the job.)
posted by w0mbat at 2:56 PM on November 7, 2018 [1 favorite]
posted by w0mbat at 2:56 PM on November 7, 2018 [1 favorite]
For n=5, the largest value for which the exact answer is known, it takes 153 episodes.
The general formulas for the current best-known lower and upper bound give 152 and 154 for n=5, respectively, which means the actual answer is not either the current best known upper or lower bound.
posted by DevilsAdvocate at 3:07 PM on November 7, 2018
The general formulas for the current best-known lower and upper bound give 152 and 154 for n=5, respectively, which means the actual answer is not either the current best known upper or lower bound.
posted by DevilsAdvocate at 3:07 PM on November 7, 2018
The only author more likely to have a significant mathematical result than to have plausible three-dimensional protagonists.
The only author more likely to have plausible four-dimensional protagonists than plausible three-dimensional protagonists.
posted by straight at 3:18 PM on November 7, 2018 [4 favorites]
The only author more likely to have plausible four-dimensional protagonists than plausible three-dimensional protagonists.
posted by straight at 3:18 PM on November 7, 2018 [4 favorites]
He was very much noticed and remembered by the lecturers there at the time.
So they say. But did you actually see him?
posted by tavella at 3:24 PM on November 7, 2018 [3 favorites]
So they say. But did you actually see him?
posted by tavella at 3:24 PM on November 7, 2018 [3 favorites]
I just think it's wild that there's been a novel contribution to mathematics from an anonymous coward from 4chan talking about Haruhi Suzumiya
posted by Merus at 4:41 PM on November 7, 2018 [5 favorites]
posted by Merus at 4:41 PM on November 7, 2018 [5 favorites]
I'm finding it rather annoying that there doesn't seem to be a link to or screenshot of the actual 4chan comment, or at least an obvious one, in that whole article. They linked a score of *other* stuff but not the base of the whole story?
posted by tavella at 7:03 PM on November 7, 2018
posted by tavella at 7:03 PM on November 7, 2018
The paper where Anon is listed as an author links to an archive
posted by save alive nothing that breatheth at 7:08 PM on November 7, 2018 [1 favorite]
posted by save alive nothing that breatheth at 7:08 PM on November 7, 2018 [1 favorite]
Weirdly enough, I was just reading the other day (thanks to some friendly person on twitter or mastodon, maybe a mefite, pointing me to it) about Cool-lex ordering, which is a sort of thematically related (but apparently simpler, or at least more solved) problem of packing together a sequence that captures all configurations of an n-bit binary string.
posted by cortex at 9:55 PM on November 7, 2018
posted by cortex at 9:55 PM on November 7, 2018
A sequence like this one that contains every possible rearrangement (or permutation) of a collection of n symbols is called a “superpermutation.”
Seems like it would be much more in the spirit of the thing to just call it a "supermutation."
where do I apply for my Fields Medal
posted by solotoro at 5:52 AM on November 8, 2018 [5 favorites]
Seems like it would be much more in the spirit of the thing to just call it a "supermutation."
where do I apply for my Fields Medal
posted by solotoro at 5:52 AM on November 8, 2018 [5 favorites]
If viewers wanted to see the series in every possible order, what is the shortest list of episodes they’d have to watch?
I don’t even understand this question. What do they mean by “shortest list of episodes”? Are they withdrawing certain episodes?
posted by gucci mane at 6:33 AM on November 8, 2018
I don’t even understand this question. What do they mean by “shortest list of episodes”? Are they withdrawing certain episodes?
posted by gucci mane at 6:33 AM on November 8, 2018
Well I should have read the rest of the article first. This is still above my head though.
posted by gucci mane at 6:40 AM on November 8, 2018
posted by gucci mane at 6:40 AM on November 8, 2018
If there were 3 episodes, there are 6 possible orderings. We can name them permutations A through F.
A: 1, 2, 3
B: 1, 3, 2
C: 2, 1, 3
D: 2, 3, 1
E: 3, 1, 2
F: 3, 2, 1
You might think in order to watch all the episodes in every order, you would need to watch each permutation sequentially, for a total of 18 episodes. But that's not true. If you optimized the order that you watched the permutations, the end of one permutation might match the beginning of the next one, so you can trim off one or two episodes in your watch list, or even skip some of the permutations entirely. It turns out you only need to watch 9 episodes; half as many as you might have expected.
A: 1, 2, 3
B: 1, 3, 2
C: 2, 1, 3
D: 2, 3, 1
E: 3, 1, 2
F: 3, 2, 1
You might think in order to watch all the episodes in every order, you would need to watch each permutation sequentially, for a total of 18 episodes. But that's not true. If you optimized the order that you watched the permutations, the end of one permutation might match the beginning of the next one, so you can trim off one or two episodes in your watch list, or even skip some of the permutations entirely. It turns out you only need to watch 9 episodes; half as many as you might have expected.
1, 2, 3, 1, 2, 1, 3, 2, 1
+--A--+ | | | | | |
| | | | +--B--+ |
| | | +--C--+ |
+--D--+ | | |
+--E--+ | |
+--F--+
posted by zixyer at 10:07 AM on November 8, 2018 [10 favorites] That's some solid ascii charting, zixyer.
posted by cortex at 10:37 AM on November 8, 2018 [1 favorite]
posted by cortex at 10:37 AM on November 8, 2018 [1 favorite]
If you optimized the order that you watched the permutations, the end of one permutation might match the beginning of the next one, so you can trim off one or two episodes in your watch list, or even skip some of the permutations entirely.
I found it easier to understand once I uncoupled from the TV-watching metaphor, because I don't get "watching the series in order" just from seeing the episodes in a particular order. You have to pause and consider the permutation of episodes that you just saw as an entire series unto itself, then restart with another permutation from the jump.
But that's not what this math is "really" about.
posted by Etrigan at 10:38 AM on November 8, 2018
I found it easier to understand once I uncoupled from the TV-watching metaphor, because I don't get "watching the series in order" just from seeing the episodes in a particular order. You have to pause and consider the permutation of episodes that you just saw as an entire series unto itself, then restart with another permutation from the jump.
But that's not what this math is "really" about.
posted by Etrigan at 10:38 AM on November 8, 2018
Yes, Etrigan. I too would disagree that someone who watched the episodes in the order 1, 2, 3, 1, 2, 1, 3, 2, 1 could be said to have tried watching them in the order 3, 1, 2 because they could not simultaneously experience episode 3 as "the final episode in a set of three" and "the first episode in a set of three."
posted by straight at 6:12 PM on November 8, 2018
posted by straight at 6:12 PM on November 8, 2018
It is not about e3 as the last in a set of three. It is about the clever ways that e1 can be followed by e2 as compared to e1 being followed by e3.
It is about a story that works as a very interconnected graph, but that we can only experience linearly. This is the best way to get a glimpse of the graph structure.
posted by Dr. Curare at 8:37 AM on November 9, 2018
It is about a story that works as a very interconnected graph, but that we can only experience linearly. This is the best way to get a glimpse of the graph structure.
posted by Dr. Curare at 8:37 AM on November 9, 2018
If that were the case, then there would be no need to consider them in groups of three. The sequence 1 2 3 1 3 2 1 would be sufficient to simply experience each possible transition between two episodes.
What the TV version of this seems to disregard that might not be the case in other examples you could use to illustrate the mathematical concept in question is that the 3 in the sequence 123 is not the same as the 3 in the sequence 312. They should be really be written
[episode 1 as first episode][episode 2 as second episode][episode 3 as third episode]
and
[episode 3 as first episode][episode 1 as second episode][episode 1 as third episode]
which makes it clear that you can't overlap the two sequences.
posted by straight at 6:08 PM on November 9, 2018
What the TV version of this seems to disregard that might not be the case in other examples you could use to illustrate the mathematical concept in question is that the 3 in the sequence 123 is not the same as the 3 in the sequence 312. They should be really be written
[episode 1 as first episode][episode 2 as second episode][episode 3 as third episode]
and
[episode 3 as first episode][episode 1 as second episode][episode 1 as third episode]
which makes it clear that you can't overlap the two sequences.
posted by straight at 6:08 PM on November 9, 2018
I am genuinely enjoying the divergence here from the question of superpermutations themselves into the more philosophical/narrative question of what the nature of the experience a sequence of discrete chunks of art is. Which seems like it's at the heart of the argument about whether the episodes-of-a-season example is incompatible with the mathematical answer provided.
Here's another framing: instead of 12 (let's make it 12) episodes of a TV show, call it 12 notes on the standard chromatic musical scale. A, A#, B, C, C#, ... , G#. Let's imagine a melody consisting of all twelve of those notes, each played exactly once. (I'm allowing here for the huge simplification here that there aren't other qualities like duration, rest, dynamics, etc involve in a melody).
Now, we create a superpermutation of those 12-note non-repeating melodies.
One argument is we've arranged a way to hear every twelve-note melody that never repeats a note. The contrasting argument would be that the nature of a melody includes the idea that it begins and ends and that by embedding any given twelve-note tune in a longer string of notes, we've change the nature of experiencing-a-melody so much that the substrings of that superpermutation aren't really experienced as melodies.
And the thing is, I think you can run with both of those arguments somewhat defensibly. Because the second argument has meat on it: there is a difference between a run of notes embedded in a larger run, and that run of notes in isolation bounded by rest on either side. Context changes the experience.
But, on the other hand, a melody can still retain its structure, its sense of what it is as an identifiable passage, in a surrounding context. Much musical arrangement does exactly that; motifs are embedded, repeated, restated, inverted and transformed and mutated within larger works and still jump out as thing specific things they are in those contexts. Slip the opening notes of Beethoven's fifth, or Despacito, into an unrelated song and it'll still make your brain go "hey, that's Beethoven/Daddy Yankee".
Obviously there's a huge scale difference between an individual musical note and a half hour television episode, or a twelve-note melody and a season-length sequence of episodes. The question in my mind is is there a fundamental difference there, or is it one of (in this case a very significant number of) degrees; and if it's the former, why, and if the latter, how many degrees and where along the spectrum from single note to half hour episode does the narrative impact of a unit and of a sequence of units change from being recognizable as an entity that exists in its own right even in surrounding context to something to not being so.
posted by cortex at 7:34 PM on November 9, 2018 [2 favorites]
Here's another framing: instead of 12 (let's make it 12) episodes of a TV show, call it 12 notes on the standard chromatic musical scale. A, A#, B, C, C#, ... , G#. Let's imagine a melody consisting of all twelve of those notes, each played exactly once. (I'm allowing here for the huge simplification here that there aren't other qualities like duration, rest, dynamics, etc involve in a melody).
Now, we create a superpermutation of those 12-note non-repeating melodies.
One argument is we've arranged a way to hear every twelve-note melody that never repeats a note. The contrasting argument would be that the nature of a melody includes the idea that it begins and ends and that by embedding any given twelve-note tune in a longer string of notes, we've change the nature of experiencing-a-melody so much that the substrings of that superpermutation aren't really experienced as melodies.
And the thing is, I think you can run with both of those arguments somewhat defensibly. Because the second argument has meat on it: there is a difference between a run of notes embedded in a larger run, and that run of notes in isolation bounded by rest on either side. Context changes the experience.
But, on the other hand, a melody can still retain its structure, its sense of what it is as an identifiable passage, in a surrounding context. Much musical arrangement does exactly that; motifs are embedded, repeated, restated, inverted and transformed and mutated within larger works and still jump out as thing specific things they are in those contexts. Slip the opening notes of Beethoven's fifth, or Despacito, into an unrelated song and it'll still make your brain go "hey, that's Beethoven/Daddy Yankee".
Obviously there's a huge scale difference between an individual musical note and a half hour television episode, or a twelve-note melody and a season-length sequence of episodes. The question in my mind is is there a fundamental difference there, or is it one of (in this case a very significant number of) degrees; and if it's the former, why, and if the latter, how many degrees and where along the spectrum from single note to half hour episode does the narrative impact of a unit and of a sequence of units change from being recognizable as an entity that exists in its own right even in surrounding context to something to not being so.
posted by cortex at 7:34 PM on November 9, 2018 [2 favorites]
An additional wrinkle to that, cortex, is what counts as "experiencing" a melody? Say you've got a melody that quotes both the opening motif of Beethoven's 5th and the first phrase of "Mary Had a Little Lamb" so that they overlap.
And then what if you hear the first phrase of Bach's Toccata and Fugue in D Minor, and you say, "Hey, those first three notes and the final note of the phrase are the same as the first phrase from The Final Countdown."
posted by straight at 10:20 AM on November 10, 2018 [1 favorite]
1 2 3 4 5 6 7 8 9
Ma ry had a lit- le lamb
Dah Dah Dah Dum
Is it really possible to simultaneously experience notes 6, 7, and 8 as part of "Mary" AND part of Beethoven's 5th AND part of the of that new 9-note melody? Or are you only really "hearing" the different roles of those notes retrospectively in memory? Or maybe by "hearing" it in your head (like you probably just did) beforehand you can be primed to notice everything the notes are doing when you "actually" hear it? And then what if you hear the first phrase of Bach's Toccata and Fugue in D Minor, and you say, "Hey, those first three notes and the final note of the phrase are the same as the first phrase from The Final Countdown."
1 2 3 4 5 6 7 8 9 Dah dee Dah doodley-do duh Dum (Bach) Dah dee Dah Dum (Final Countdown)Would that count as having "heard" The Final Countdown? It seems to me that if we are going to say a listener can distinctly perceive 2345678 (Mary) and 6789 (Beethoven5) when they hear 123456789, then we also ought to say that they can perceive 1239 (Final Countdown) when they hear 123456789.
posted by straight at 10:20 AM on November 10, 2018 [1 favorite]
The contrasting argument would be that the nature of a melody includes the idea that it begins and ends and that by embedding any given twelve-note tune in a longer string of notes, we've change the nature of experiencing-a-melody so much that the substrings of that superpermutation aren't really experienced as melodies.
In the mathematical/symbolic representation of the problem, though, what this does is add a 13th character in the alphabet denoting a silence --- and a melody is defined to begin and end with a silence . This version of the problem, while completely defensible from the motivating question, is mathematically trivial as it's obvious we have to listen to 12!*14 notes to hear all the melodies.
posted by PMdixon at 10:22 AM on November 11, 2018
In the mathematical/symbolic representation of the problem, though, what this does is add a 13th character in the alphabet denoting a silence --- and a melody is defined to begin and end with a silence . This version of the problem, while completely defensible from the motivating question, is mathematically trivial as it's obvious we have to listen to 12!*14 notes to hear all the melodies.
posted by PMdixon at 10:22 AM on November 11, 2018
PMdixon, I think the original point of this was not to find a mathematically interesting problem involving melodies or TV show episodes, but to point out why those aren't very good examples for illustrating what the mathematical puzzle is about. Our intuition about what would be "valid" sequences in these examples doesn't match the actual goal of the puzzle.
I think a better example would be Scrabble letters. Given the letters B C A T E, what is the shortest string of letters that would contain every possible combination of these letters? Because then it would be relatively easy to spot all the valid words even if some of them are embedded in other words.
posted by straight at 5:13 PM on November 11, 2018
I think a better example would be Scrabble letters. Given the letters B C A T E, what is the shortest string of letters that would contain every possible combination of these letters? Because then it would be relatively easy to spot all the valid words even if some of them are embedded in other words.
posted by straight at 5:13 PM on November 11, 2018
« Older Go into the hot bubbling oil, unaccompanied. Each... | National Jealousy Day, Finland's "annual orgy of... Newer »
This thread has been archived and is closed to new comments
posted by Etrigan at 12:54 PM on November 7, 2018 [24 favorites]