# sum with permutations

Let $a$ be vector in $R^{2m}$. And let $S_{2m}$ be group of all permutations on the set $\{1,\dots,2m\}$.

I would like to calculate $$\sup_{\pi\in S_{2m}}\sum_{d(\sigma, \pi)=2}\left(\left|\sum_{k=1}^ma_{\sigma(k)}-\sum_{k=m+1}^{2m}a_{\sigma(k)}\right|-\left|\sum_{k=1}^ma_{\pi(k)}-\sum_{k=m+1}^{2m}a_{\pi(k)}\right|\right)^2.$$

Here $\sigma(\cdot),\pi(\cdot)$ are a permutations on the set $\{1,...,2m\}$ with uniform distribution.

Of course, I can open square:

\begin{align} \sum_{d(\sigma, \pi)=2}\Big(\left|\sum_{k=1}^ma_{\sigma(k)}-\sum_{k=m+1}^{2m}a_{\sigma(k)}\right|^2&-2\left|\sum_{k=1}^ma_{\pi(k)}-\sum_{k=m+1}^{2m}a_{\pi(k)}\right|\left|\sum_{k=1}^ma_{\sigma(k)}-\sum_{k=m+1}^{2m}a_{\sigma(k)}\right|\\ &+\left|\sum_{k=1}^ma_{\pi(k)}-\sum_{k=m+1}^{2m}a_{\pi(k)}\right|^2\Big), \end{align} and now for the first and for the last terms $$\left|\sum_{k=1}^ma_{\pi(k)}-\sum_{k=m+1}^{2m}a_{\pi(k)}\right|^2=\sum_{i=1}^{2m}a^2_{\pi_(i)}+2\sum_{i=1}^{2m}\sum_{i\neq k}a_{\pi(i)}a_{\pi(k)}-2\sum_{i=1}^{2m}\sum_{k=1}^{2m}a_{\pi(i)}a_{\pi(k)}.$$

But I don't know what to do with the second term of the sum and how to sum everything over $d(\pi, \sigma)$. Note here, $d(\sigma, \pi)=2$ means $\sigma=\pi \tau$, where $\tau$ is a transposition. Thank you for the help.

-
I think the outer square shouldn't be there in the second equation. Since noone has asked yet, I suppose $d(\sigma,\pi)$ must be a well-known notation, but I've never encountered it -- what does it mean? Also, what does it mean to sum over $d(\sigma,\pi)=2$ when $\sigma$ and $\pi$ are random? – joriki Jul 26 '12 at 23:23
Thank you. Square in the second equation was typo. Also, I wanted to find the suprenum of this sum. I've edited it. As I understand, $d(\sigma, \pi)$ is a distance between two permutations. (If I understand correct, $d(\sigma, \pi)=2$, if $\sigma=\tau \pi$, for some transposition $\tau$) – Michael Jul 27 '12 at 0:02
Also, I think to sum over $d(\sigma, \pi)$ its the same as to find expected value... – Michael Jul 27 '12 at 0:11
Maybe I am mistaking, I think that the question redused now to find $max_{\pi \in S_{2m}}E\left(|\sum_{k=1}^ma_{\pi(k)}-\sum_{k=m+1}^{2m}a_{\pi(k)}|-|\sum_{k=1}^m‌​a_{\pi \tau(k)}-\sum_{k=m+1}^{2m}a_{\pi \tau(k)}|\right)^2$ – Michael Jul 27 '12 at 3:25
You're mixing things here. Either you sum over all $\sigma$, or you take the expectation value with respect to a uniform distribution. Not only do the results differ by a factor of the number of permutations; it simply makes no sense to write down a sum and then specify a distribution. The sum is (a factor times) the expectation value with respect to a particular distribution, it's not something that has a free distribution to be specified. Regarding the definition of $d$, please add it to the question; people shouldn't have to delve into the comments in order to understand the question. – joriki Jul 27 '12 at 13:00