Comment

Comment by Vincent Granville on July 15, 2013 at 11:48am

@Chris: Complexity of computing q(n) is O(n!). The complexity here is entirely, 100% created by by the sheer number of permutations that need to be checked to compute q(n). Of course for one single of these permutations, computation is absolutely straightforward and fast - no need for FFT. 

To put it differently, q(n) is a maximum value computed on ALL n! permutations of order n - not a value computed on one single permutation of order n. But there must be extremely smart ways to skip most permutations and still get the right answer, I guess that's what Maxim Nazarov did in his comment below.

Comment by Vincent Granville on July 14, 2013 at 11:28pm

@Maxim: Great finding, very impressive! I'll mention it when I publish the list of great contributors, in October. Did you look at the chart below that represents your incredibly weird permutation (X axis are the numbers 0 to 20, Y axis are the values after permutation). This is a one-to-one mapping (between X and Y) that does not look like one at all, and my guess is that all permutations that achieve the maximum q(n) or overshoot it, will have a similar pattern. I'm sure there must be very very very very very few permutations of 21 elements that overshoot my (erroneous) q(n): probably 2 or 3 out of more than a trillion of quadrillion (factorial 21 to be precise) permutations. I actually checked permutations up to order 23, but not ALL of them, just a very very very tiny sample (about a few hundred million). I missed the most important ones in my sample, when n=21 or bigger. However, you probably sampled out of a very small but well chosen subset or subgroup that has special properties.

To make our math competition more attractive, I will offer the same award if instead of finding q(n) or proving no formula exists, a participant comes up with an non-singular asymptotic distribution for my correlation coefficient, after proper normalization. Thus there will be two possible awards: one for a formula about q(n), and one for an asymptotic distribution for the correlation. More on this pretty soon.  

Maxim's Permutation - The least "linear" permutation of (0, ... , 20)

Standard correlation between X and Y is 0.0458

Comment by Maxim Nazarov on July 13, 2013 at 12:26pm

Just a quick comment - the claim that 

• q(n) = (n-6)+(n^2)/3 if and only if n is a multiple of 3

is false. For n=3 it doesn't hold already - q(n)=2 and not 0 as the given formula suggests. For a few next values (6,9,12,15,18) it holds, but then does not hold again starting from 21...

For 21, for example, the permutation of {0,1,...,20} that gives 164 (>162 suggested by formula) is {12,15,7,11,16,3,5,2,19,20,4,0,18,1,17,14,8,10,6,13,9}.

Comment by Vincent Granville on July 12, 2013 at 2:11pm

Note to potential candidates

If you are not referred by a partner, we encourage you to enlist your company as a reverse sponsor. There is no cost for the reverse sponsor, and it comes will the following benefits:

• Participants mentioning an official reverse sponsor when submitting their solution, if winning, will have the amount of the award multiplied by 2. The difference is paid by us, on behalf of the partner.
• Reverse sponsors referred by great candidates will be featured when we release the final results later in October.

Have your company or organization contact us at [email protected], to be listed as an official partner (reverse sponsor).