Upper-bounding a sum over non-identity permutations

Question

EDIT: Question 1 has been settled (below). The bounty is for question 2.

Let $n\geq 3$ and consider the following function $f:S_n\backslash\{e\}\rightarrow \mathbb{R}$

$$f(\sigma)=\sum_{i=1}^n\frac{1}{\sqrt{n^{i+\sigma(i)}}}$$

where $\sigma\in S_n$ is considered a function $\sigma:\{1,\dots,n\}\rightarrow \{1,\dots,n\}.$

I believe $f$ is maximised at $\sigma=(n-1\quad n)$ where it takes on the value

$$f(\sigma)=\frac{1}{n^{3n-1}}\frac{n^n-1}{n-1}.$$

1. Prove this assertion.

Secondly I am interested in upper-bounding the sum for $k\in \mathbb{N}$:

$$\frac{1}{4n^{2k(n-2)}}\sum_{\sigma\in S_n\backslash{e}}f(\sigma)^{2k},$$

particularly in the asymptotic case $n\rightarrow \infty$ and $k=k(n)\rightarrow \infty$.

2. Any bounds that are "significantly" better than using the trivial $$\sum_{j=1}^N|a_j|\leq N\cdot \max_j|a_j|.$$

Context:

These sums are related to bounding the distance to random of the random walk on the quantum group $\widehat{S_n}$ (given by $F(\widehat{S_n})=\mathbb{C}S_n$) driven by a state (positive definite function on $G$) $u\in M_p(\widehat{S_n})$ given by the permutation representation together with the unit vector $\alpha=(\alpha_i)$ where $$\alpha_i=\sqrt{n^{n-i}\frac{n-1}{n^n-1}}.$$

Answer 1

Regarding question 2, one can improve on the trivial bound a bit, but I'm not sure this counts as "significant".

Let $f_0 = \max_{\sigma \neq e} f(\sigma)$. As you noted, $\frac{n! - 1}{4n^{2k(n-2)}} f_0^{2k}$ is a trivial upper bound. For the sake of later comparison, let us call this trivial bound $M_0$.

Now observe that $f_0 \approx \frac{1}{n}$. Moreover, $f(\sigma) \approx \frac{1}{n}$ if and only if $\sigma(1) = 1$, and $f(\sigma) = O \left( n^{-\frac32} \right)$ otherwise (this order of magnitude is attained if either $\sigma(1) = 2$ or $\sigma(2) = 1$).

That is to say, only $(n-1)! - 1$ non-identity permutations come close to the maximum value, and for the remaining permutations, $f(\sigma)$ is smaller by a factor of $n^{\frac12}$. Using the trivial bound on these two sets of permutations separately, we have $$ \frac{1}{4n^{2k(n-2)}} \sum_{\sigma \in S_n \setminus \{e \}} f(\sigma)^{2k} \lessapprox \frac{(n-1)!-1}{4n^{2k(n-2)}} f_0^{2k} + \frac{n! - (n-1)!}{4n^{2k(n-2)}} \left( f_0 n^{-\frac12} \right)^{2k} \sim \left( n^{-1} + n^{-k} \right) M_0.$$

Hence this new upper bound is only a factor $n$ smaller than the trivial one. However, we cannot hope to do much better*: $$ \frac{1}{4n^{2k(n-2)}} \sum_{\sigma \in S_n \setminus \{e \}} f(\sigma)^{2k} \ge \frac{1}{4n^{2k(n-2)}} \sum_{\substack{\sigma \in S_n \setminus \{ e \} \\ \sigma(1) = 1}} f(\sigma)^{2k} \ge \frac{(n-1)! - 1}{4n^{2k(n-2)}} \cdot \frac{1}{n^{2k}} \gtrapprox \frac{(n-1)! - 1}{4n^{2k(n-2)}} f_0^{2k} \sim \frac{1}{n} M_0.$$

[*The approximation in the second line (the $\gtrapprox$) is only valid when $k$ does not grow too quickly with $n$. $f_0 = \frac{1}{n} + O(n^{-2})$, and if $k$ is linear in $n$, then $f_0^{2k}$ can be much larger than $\frac{1}{n^{2k}}$.]

I've used asymptotic approximations here just to avoid having to be too careful and fiddling around with constants. However, it shouldn't be too hard to turn these into bona fide bounds: $f_0$ is essentially a rapidly converging geometric series.

Answer 2

Here is a proof of the first assertion.

Let $a_i$ be an increasing or decreasing sequence. For a permutation $\sigma\in S_n$, consider the sum

$$S(\sigma)=\sum_{i=1}^na_ia_{\sigma(i)}.$$

An inversion is a pair $(j,k)\subset\{1,\dots,n\}$ with $j<k$ and $\sigma(j)>\sigma(k)$. All non-identity permutations have at least one inversion. Take the minimum inversion $(j^*,k^*)$ (with respect to the lexicographic order) $(j,k)$ and define a new permutation by

$$\tau_1(i):=(j^*\quad k^*)\sigma(i)=\begin{cases}\sigma(i)&\text{ if }i\neq j,k\\ \sigma(j)&\text{ if } i=k\\ \sigma(k)&\text{ if }i=j\end{cases}.$$

The calculation on page 79 shows that

$$S(\sigma)\leq S(\tau_1).$$

This process of multiplying by suitably chosen transpositions strictly reduces the number of inversions and can always be done until $\tau_r=e$. Furthermore each multiplication increases the sum.

Therefore, no matter what the starting permutation $\sigma$, $\displaystyle\tau_{r-1}$ is a transposition and therefore to maximise $S$ on $S_n\backslash\{e\}$ one just maximises over transpositions.

Now consider the decreasing sequence $\displaystyle a_i=\frac{1}{\sqrt{n^i}}$. Define $$f(x)=\frac{1}{\sqrt{n^x}}-\frac{1}{\sqrt{n^{x+1}}}.$$ Note $f(x)$ is positive for $x\geq 1$. Furthermore $$f'(x)=-\frac{1}{2}\ln n\cdot f(x),$$ and so $f(x)$ --- the one-step differences between the $a_i$ --- is decreasing and so the smallest one-step difference is between $a_{n-1}$ and $a_n$.

Let $(j\quad k)$ be a permutation with $j<k$. Note from the result about the one-step difference and $a_k\leq a_{j+1}$

$$ \begin{align*} a_{n-1}-a_n&\leq a_{j}-a_{j+1}\leq a_{j}-a_k \\ \Rightarrow (a_{n-1}-a_n)^2&\leq (a_j-a_k)^2 \\ \Rightarrow a_ja_k+a_ka_j+a_{n-1}^2+a_n^2&\leq a_j^2+a_k^2+a_na_{n-1}+a_{n-1}a_n \\\Rightarrow S((j \quad k))&\leq S((n-1\quad n))\,\,\bullet \end{align*}$$

This proof can be generalised to:

Suppose that $\{a_i\}_{i=1}^n$ is a decreasing sequence such that the one-step difference is minimised for $a_{j+1}-a_j$. Then $S:S_n\backslash \{e\}\rightarrow \mathbb{R}$ is maximised at $(j\quad j+1)$.

It might be possible to generalise it to two sequences a lá the Rearrangement Inequality.