An Uncitable Result?

My colleague Pablo Soberon just showed me an unusually problematic result to cite, and I wanted to share this weird story. If you have other weird citation stories, do tell!

Yes, this is a second silly post in a row. Lately I’m not finding the time to write more serious ones. And the silly stories need to be documented somewhere…

This story begins with a Japanese anime show called The Melancholy of Haruhi Suzumiya. I don’t know much about this show, but apparently there are several different orders in which one can watch the episodes. This led a fan of the show to ask for the minimum number of episodes one needs to watch, so that you saw all the episodes in every possible order. In other words, the minimum sequence of the numbers from \{1,\ldots,n\}  that contains every possible permutation of the numbers. (if I understand correctly, each order has to appear consecutively, with no additional numbers in between). This was on 4chan in 2011. A solution was then offered by an anonymous user, and this disappeared among the other weird anime discussions around the web.

show

It turns out that some people have been studying the above question as a serious math problem, prior to the show and not aware of it. The sequence containing all of the possible permutations is referred to as a superpermutation. See for example here and here. One paper about this was even published in the journal “Discrete Mathematics” in 2013.

Now the people coming from the mathematical angle discovered the original 4chan discussion, and in it the solution to the problem. So can they cite this result? It is by an anonymous person and appeared on an anime fans website. If this is not complicated enough, the relevant website no longer exists. Instead, the original discussion was discovered on a site that archives old online discussions. And it’s unclear how stable this archive site is. Luckily, this is not my problem!

Advertisements

Mathematical Energy: Etymology

This might be the silliest post I’ve written so far (yes – worse than “Was Disney trying to kill mathematicians?”). I urge you to stop reading now unless (i) you are quite familiar with the mathematical notion of energy (e.g., additive energy), and (ii) you have a horrible sense of humor.

The term energy was coined by Tao and Vu. I like “energy” as a name for this object, but I never had a good answer when asked why this is how it’s called. That is, until a referee report provided me with an answer. And this wonderful referee probably didn’t even know it.

In a recent paper, Cosmin Pohoata and I used “color energy”. We have a graph G=(V,E)  with colored edges. Denote the color of an edge (v_1,v_2)  as \chi(v_1,v_2)  . The color energy of G  is

E(G) = \left|\left\{(v_1,v_2,v_3,v_4)\in V^4 :\ \chi(v_1,v_2) = \chi(v_3,v_4) \right\}\right|.

The referee complained about our notation for the multiplicity of a color c  (the number of edge of color c  ), and asked to change it to m_c  . After this change of notation, the energy is defined by the standard formula

E = \sum m_c^2.

Research and Willpower and Fools

Martin Hellman is one of the inventors of assymetric encryption – probably the biggest paradigm shift in the history of cryptography. I just stumbled upon a quote by him which goes well with my recent post about research and willpower:

“The way to get to the top of the heap in terms of developing original research is to be a fool, because only fools keep trying. You have idea number 1, you get excited, and it flops. Then you have idea number 2, you get excited, and it flops. Then you have idea number 99, you get excited, and it flops. Only a fool would be excited by the 100th idea, but it might take 100 ideas before one really pays off. Unless you’re foolish enough to be continually excited, you won’t have the motivation, you won’t have the energy to carry it through. God rewards fools.”

I wish I was more of a fool…

Martin-Hellman
Martin Hellman

A Prisoners Riddle

I just heard a nice riddle and wanted to share.

prisoners

Prisoner A and prisoner B are given an integer between 1 and 100. Each prisoner only knows his own number, but also that the two numbers are consecutive. For example, if prisoner A got the number 60, he knows that prisoner B got either 59 or 61. At the end of every hour each prisoner can choose to guess the number of the other. If either prisoner guesses correctly, they both go free. However, if either prisoner guesses wrong, they both get executed (even if at the same time the other guessed correctly). Both prisoners can choose not to guess for as many hours as they like.

The two prisoners are in different cells and cannot communicate in any way. Also, they did not have time to coordinate a strategy in advance. Each can only assume that the other prisoner is intelligent. Can they always guess correctly? After how many hours?

I think it would be nice not to post solutions in the comments. Although you can just write the number of hours you got.

A Boxes Riddle

I just recalled a nice mathematical riddle. I can’t remember where I originally read it, but it was likely in one of the blogs that are in the blogroll to the right.

Riddle. A game takes place where person A and person B are on the same team while person Z is their adversary. There are 100 boxes and 100 notes containing the numbers 1 to 100 (that is, each number is on exactly one note). The game goes as follows:

  • First, only Z and A are in the room. Z places one note in each box.
  • A sees the actions of Z and may afterwards pick two boxes and switch the notes in them (with each other). He may only perform one such switch.
  • Z sees the actions of A and then chooses a number N between 1 and 100.
  • A leaves the room while B enters it (they cannot exchange information during this process). Z tells B the number N.
  • Finally, B needs to find the box that contains the note with the number N. For this purpose, B may open up to 50 boxes.
If A chooses the 50 boxes at random, his probability of success is obviously 0.5. Do A and B have a strategy for increasing their chances? Or does Z have a strategy for which 0.5 is the best possible?

phd032108s

Feel free to write the answer as a comment. However, I think that it would be nice not to provide a full explanation here (that is, only to write whether it’s 0.5 or what better probability you can get).

(Later edit: I seem to be getting senile! I just noticed that I wrote the same riddle in a post two years ago…)

Quoting Rota

“What can you prove with exterior algebra that you cannot prove without it”? Whenever you hear this question raised about some new piece of mathematics, be assured that you are likely to be in the presence of something important. In my time, I have heard it repeated for random variables, Laurent Schwartz’ theory of distributions, idèles and Grothendieck’s schemes, to mention only a few. A proper retort might be: “You are right. There is nothing in yesterday’s mathematics that could not also be proved without it. Exterior algebra is not meant to prove old facts, it is meant to disclose a new world. Disclosing new worlds is as worthwhile a mathematical enterprise as proving old conjectures.”

This paragraph is taken from Indiscrete Thoughts by Gian-Carlo Rota, in a section discussing how Grassmann‘s work was ignored for decades. And yes, I am quoting other people because I have no time for more serious posts. Hopefully these will return in about six weeks. In the meantime, another Rota from the same book:

One day, in my first year as an assistant professor at MIT, while walking down one of the long corridors, I met professor Z, a respected senior mathematician with a solid international reputation. He stared at me and shouted “Admit it! All lattice theory is trivial!”

Being a group theorist can be dangerous!

The Maoist movement decided that group theory was a reactionary subject of the old regime, and started protesting at the increasing number of professors in the subject being appointed. Demonstrations erupted outside of the maths department with protesters holding placards demanding ‘No more group theory’. One new appointee in group theory was frightened off and took a job elsewhere. During one demonstration, the students scaled the outside of the building and scrawled `Group Theory Department’ on the wall.

This paragraph is taken from the non-fiction book Finding Moonshine by Marcus du Sautoy. These events took place in Germany in the early 70’s.