Mystery Math Whiz and Novelist Advance Permutation Problem
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.
On September 16, 2011, an anime fan posted a math question to the online bulletin board 4chan about the cult classic television series The Melancholy of Haruhi Suzumiya. Season one of the show, which involves time travel, had originally aired in nonchronological order, and a re-broadcast and a DVD version had each further rearranged the episodes. Fans were arguing online about the best order to watch the episodes, and the 4chan poster wondered: If viewers wanted to see the series in every possible order, what is the shortest list of episodes they'd have to watch?
In less than an hour, an anonymous person offered an answer — not a complete solution, but a lower bound on the number of episodes required. The argument, which covered series with any number of episodes, showed that for the 14-episode first season of Haruhi, viewers would have to watch at least 93,884,313,611 episodes to see all possible orderings. "Please look over [the proof] for any loopholes I might have missed," the anonymous poster wrote.
The proof slipped under the radar of the mathematics community for seven years — apparently only one professional mathematician spotted it at the time, and he didn't check it carefully. But in a plot twist last month, the Australian science fiction novelist Greg Egan proved a new upper bound on the number of episodes required. Egan's discovery renewed interest in the problem and drew attention to the lower bound posted anonymously in 2011. Both proofs are now being hailed as significant advances on a puzzle mathematicians have been studying for at least 25 years.
Mathematicians quickly verified Egan's upper bound, which, like the lower bound, applies to series of any length. Then Robin Houston, a mathematician at the data visualization firm Kiln, and Jay Pantone of Marquette University in Milwaukee independently verified the work of the anonymous 4chan poster. "It took a lot of work to try to figure out whether or not it was correct," Pantone said, since the key ideas hadn't been expressed particularly clearly.
Now, Houston and Pantone, joined by Vince Vatter of the University of Florida in Gainesville, have written up the formal argument. In their paper, they list the first author as "Anonymous 4chan Poster."
"It's a weird situation that this very elegant proof of something that wasn't previously known was posted in such an unlikely place," Houston said.
[...] If a television series has just three episodes, there are six possible orders in which to view them: 123, 132, 213, 231, 312 and 321. You could string these six sequences together to give a list of 18 episodes that includes every ordering, but there's a much more efficient way to do it: 123121321. A sequence like this one that contains every possible rearrangement (or permutation) of a collection of n symbols is called a "superpermutation."
The story then describes parallels with the "Asymmetric" (aka weighted) traveling salesman problem as well as the fortuitous connections which led researchers to work together in finding calculations of upper and lower bounds for an arbitrary number of episodes. You'll have to RTFA to learn how many episodes you'd need to watch to view them in all possible orders.
(Score: 4, Insightful) by Runaway1956 on Thursday November 08 2018, @03:24PM (12 children)
What's so unlikely? Anonymous didn't feel the need for recognition, apparently. Or, he thought it was so simple, anyone with a basic education could have done it. Anon saw a puzzle, apparently solved it without excess difficulty, and posted the answer.
Had there been a reward offered, he/she may not have posted anonymously.
But, the phrasing. Why would anyone rule out that a very intelligent, and/or a well educated person might be posting on 4chan? Intelligent people are just people - and people populate 4chan.
(Score: 0, Informative) by Anonymous Coward on Thursday November 08 2018, @03:31PM (8 children)
Because "a very intelligent, and/or a well educated person" is likely to be at a university and post such an answer in those channels to be recognized for it.
(Score: 4, Informative) by Runaway1956 on Thursday November 08 2018, @03:39PM (1 child)
You kinda sorta missed the point. Not all intelligent and/or educated people go to university. And, even if this particular Anon were at university, he apparently didn't think the puzzle worthy of attention. It was just too damned SIMPLE to bother real mathematicians with.
(Score: 3, Insightful) by bzipitidoo on Thursday November 08 2018, @04:56PM
You aren't seeing it either. You evidently like a particular narrative, that not all smart people go to college, so much that you are going way out on a limb to speculate that's the case here.
Perhaps you don't appreciate how many barriers there are even after you manage to earn a bachelors. It never ends. Get a masters degree, and people will still wonder if you're worth listening to, because you don't have a doctorate. Get the doctorate, and you still have to deal with rampant skepticism, got to keep publishing. Are you a lightweight? Did you fail to see that some problem you worked hard on is in fact trivially easy?
Often, you have to sell others on the difficulty of a problem. There are many problems with solutions that are easy to follow, but which were very hard to figure out the first time. That sort of problem is all too likely to be seen as not particularly important or hard, because it just looks too easy. It's almost a reflex to think that if the solution is easy to follow, then the problem can't have been hard.
(Score: 2) by tibman on Thursday November 08 2018, @04:41PM (3 children)
What are those "very intelligent, and/or a well educated" people doing after they have moved on from university/college?
SN won't survive on lurkers alone. Write comments.
(Score: 1, Informative) by Anonymous Coward on Thursday November 08 2018, @06:27PM (2 children)
What are those "very intelligent, and/or a well educated" people doing after they have moved on from university/college?
In Trump's America? Getting as far away from the United States as possible.
Next question?
(Score: 0) by Anonymous Coward on Friday November 09 2018, @12:26AM
In Trump's America? Getting as far away from the United States as possible.
Oooooo how edgy! Please tell me more!
How about I quote what someone told me in December 2008 "get over your butthurt self and get over it"
(Score: 2) by tibman on Friday November 09 2018, @12:48AM
Doubt it. Don't educated people know that the US President's term has limits? as in, you don't have to abandon your country because the current leader is literally temporary.
SN won't survive on lurkers alone. Write comments.
(Score: 4, Interesting) by Sulla on Thursday November 08 2018, @05:26PM
Not everyone wants to be recognized. A theme that runs through the various boards of 4chan is that the most insightful and important work is kept anonymous because it adds value to the work. People often come on and post "I'm a woman and this is what I think" or "I'm a parent and this is what I think" and the response is "why would who you are make your idea more valid". This post was particularly valid because it was posted on the merit of the idea alone, without any group or personal affiliation to try and elevate (or denigrate) it.
Ceterum censeo Sinae esse delendam
(Score: 2) by fyngyrz on Thursday November 08 2018, @08:23PM
That's extremely short-sighted. Or IOW, no.
First of all, most of those very smart students of institutes of higher education go on from those places into, you know, jobs. Jobs other than "professor at institute of higher education", a job category that cannot possibly absorb more then a very small fraction the people it educates because, you know, math.
Secondly, not every intelligent person goes on to formal higher education. Libraries and bookstores have been a thing for a while now (cough /ROLLEYES.) Now there's the web... and that has pretty much changed everything WRT access to knowledge, training, equipment, parts, communication and ultimate education level anyway.
So yes, there are some very smart people in those institutions. No, a random encounter with a very smart person who is well educated is not most likely to be found there.
(Score: 0) by Anonymous Coward on Thursday November 08 2018, @05:49PM
almost some sort of math terrorist! i mean, the knowledge wasn't even properly hoarded by the establishment behind a fucking paywall. won't someone think of the hacks?
(Score: 3, Informative) by legont on Friday November 09 2018, @02:09AM (1 child)
Grigori Perelman refused all the moneys https://en.wikipedia.org/wiki/Grigori_Perelman [wikipedia.org]
He is *very* poor and unemployed since 2005.
"Wealth is the relentless enemy of understanding" - John Kenneth Galbraith.
(Score: 2) by Runaway1956 on Friday November 09 2018, @02:22AM
"I don't want to be on display like an animal in a zoo."
Makes sense to me.
(Score: 4, Interesting) by Bot on Thursday November 08 2018, @03:54PM
I had to read it twice to get it, the question is about watching the fewer possible passages between each and every episode so, like focusing on travelling along all edges rather than the sequence of episodes. An actual meatbag looking at episodes just to appreciate the passage is weird, but in line with your defective nature.
Account abandoned.
(Score: 2) by PartTimeZombie on Thursday November 08 2018, @07:29PM (2 children)
It's interesting they mentioned the Assymetrics. This ancient empire was well known for its advanced mathematics, inventing skipping maths class as early as the late bronze age.
They were conquered by the Egyptians, who figured out pi = exactly 3.0 which enabled them to ditch the chariot in favour of infantry.
(Score: 2) by FatPhil on Friday November 09 2018, @12:06AM
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 1, Funny) by Anonymous Coward on Friday November 09 2018, @02:02AM
Funny thing about those Assymetrics that you forgot to mention: they developed their advanced math because of their obsession with measuring their donkeys (or so it was said; others said they were interested in more risque measurements). But you never know about those ancient rumors.
That's a common miscontraception. No, the Assymetrics were conquered by the Bah-baloneyians, who developed a special base 60 system for measuring cheap processed sausages. They were so obsessed with their 360-degree sausage angles and minutes and seconds that other peoples of the ancient world took to shouting "Bah! Baloney!" when they encountered them, hence their name.
The EE-gyp-shuns got fed up (no pun intended) with all this meat tube nonsense and conquered the Bah-baloneyians, but other people hated the EE-gyp-shuns and shunned them because they tended to screw people over in financial dealings, causing their customers to shout a squeaky "EE!" all the time in response.
Finally, though, real math and science came to the ancient world with the Geeks, who somehow managed to overcome the other empires, even though they learned philosophy and crafts at Playdough's Academy. That wasn't to last long, as the Roamin' people were on the rise, wandering around Europe and plopping down roads everywhere. The Roamin's roamed right into the Geek homeland, and before you know it, there was a whole Roamin' Empire led by some guy named "Seize-Her" (who must've had some Trump-like behavior around women).
Fast forward a few centuries, and the Roamin' Empire came to ruin as Barberarians invaded with their sexy new hairstyles (either that, or a weird fascination with bad sci-fi movies starring Jane Fonda in skimpy outfits). But some guy named Charlie who had a really big Hammer brought some order, and his grandson Shar-the-Main was eventually crowned Holy Roamin' Emperor after he wandered around conquering people again in Europe.
The Holy Roamin' Empire lasted for like a thousand years with its remnants moving about until finally it was ended with the Great War -- the War to End All Wars -- whose centennial ending we celebrate this weekend with Armin' This Day on November 11th, ironically the day people put down their arms for good.
Well, that was the plan, but some stupid Germans misunderstood and started armin' again. Hitler brought the New Math to bear as he ordered Himmler to undertake the Final Solution to Goebbels' Incompleteness Theorem, which must've had something to do with advanced topology or knot theory, given that they called themselves Knot-zies.
The Knot-zies almost took over the world, but were only stopped when Richard Feynman and Davy Crockett teamed up at the Alamo Laboratories (Remember the Alamo?) to combat Santa, Anna, Rudolph the Red-Nosed Reindeer, Rudolph Hess, and the whole Knot-zie establishment with cool math that made nukular weapons possible.
Unfortunately the fallout from this math war followed Newton's Law of Cooling to make a Cold War, where humanity could be annihilated, or at least blown back to the Stone Age, where we'd have have to start over with those metrics of asses all again.
At least, that's my understanding of the situation.
(Score: 2) by acid andy on Friday November 09 2018, @02:26AM (2 children)
From TFA:
And:
The traveling salesmen problem is well known as an NP-complete [wikipedia.org] problem, which means that if an algorithm can be found to solve it quickly (in polynomial time) in all cases, then P=NP [wikipedia.org], meaning a huge class of problems will be able to be solved just as quickly. Which leaves me wondering whether being able to "completely nail down this puzzle" will reveal a way to do just that. If it does, it would have huge implications for computer science.
If a cat has kittens, does a rat have rittens, a bat bittens and a mat mittens?
(Score: 1) by DECbot on Friday November 09 2018, @03:36AM (1 child)
You ended your history of the world prematurely stopping where you did. The cold war ended with the creation of the intertubes. Let me explain, Alberto Eye-in-Steiner theorized a system could collect enough data points that it would reach critical mass and start collecting data on its own--where data was entered into the terminal never leave. There would be so much data none could escape to the terminal. He called it a black data hole cause the terminal screen would remain black. Stevie Hawkeye expanded the theory to show that some data did escape the data black holes as metadata in the syslog assessable in another terminal on the system. However, the interesting part is the data actually leaks from the black hole as background radiation, AKA Hawkeye Radiation. This radiation of the intertubes has caused global warming which has since thawed the Cold War and popularised skimpy, breathable clothing. 'Marycan has since weaponized calculators connected to the intertubes to inflict goatse on third world countries not interested in bikinis, board shorts, Birkenstocks and hot wars.
cats~$ sudo chown -R us /home/base
(Score: 1) by DECbot on Friday November 09 2018, @05:35AM
Whoops, execution on my behalf. My comment was in response to this comment [soylentnews.org]. I blame trying to post comments during a rough landing and slow, intermittent internet. Sorry about any confusion.
cats~$ sudo chown -R us /home/base