# Existence of solution to these inequalities

They say that all mathematics problems eventually reduce to linear algebra or combinatorics. I have reduced mine to proving a solution exists for the following set of inequalities but have no idea how to proceed.

Question: For $$n \geq 2$$, fix once and for all, a permutation $$\tau \in S_n, \tau \neq (1,n)(2,n-1)\cdots$$, i.e., $$\tau$$ isn't the long element. Let $$\Delta(\tau) = \{ i \in \{1, 2, \cdots, n-1 \} : \tau(\{ 1, 2, \cdots, i \}) \neq \{ n, n-1, \cdots, n-i+1 \} \}$$

Do there exist real numbers $$b_1 > b_2 > \cdots > b_{n-1} > b_n = 0$$ such that the inequalities

$$\frac{b_1 + b_2 + \cdots + b_i + b_{\tau(1)} + \cdots + b_{\tau(i)}}{2i} > \frac{b_1 + b_2 + \cdots + b_n}{n} \quad \dots \text{Eq. }(i)$$ hold simultaneously for every $$i \in \Delta(\tau)$$?

Motiation: My original question is posted here and the above question is the case when $$G = SL(n)$$, after some simplifications and explicit computation with the Cartan matrix.

Remark: I have explicitly verified this holds for $$n \leq 8$$. These calculations suggest that the $$b_i$$'s cannot be independent of $$\tau$$.

MAJOR EDIT: I made a mistake while posing the question. The $$\tau$$ in Equation $$(i)$$ should actually be $$\tau^{-1}$$. The mistake came because $$\sum b_i \varpi_{\tau(i)}$$ was wrongly written as $$\sum b_{\tau(i)} \varpi_i$$ instead of $$\sum b_{\tau^{-1}(i)} \varpi_i$$. I will reward the bounty to the answer by @Pietro Majer but the question I really want answered is:

Do there exist real numbers $$b_1 > b_2 > \cdots > b_{n-1} > b_n = 0$$ such that the inequalities $$\frac{b_1 + b_2 + \cdots + b_i + b_{\tau^{-1}(1)} + \cdots + b_{\tau^{-1}(i)}}{2i} > \frac{b_1 + b_2 + \cdots + b_n}{n} \quad \dots \text{New Eq. }(i)$$hold simultaneously for every $$i \in \Delta(\tau)$$?

I can award some more bounty points for proving the new inequality.

• Of course this is possible when $\tau$ is the long element, since then $\Delta(\tau)$ is empty. – LSpice Jan 26 '17 at 22:03
• Why you can't take $b_i:=n-i$? The mean of the 2i numbers on the LHS of eq1 is larger than the mean of all n numbers for i in $\Delta$... what am I missing? – Pietro Majer Jan 29 '17 at 1:07
• The LHS varies according to the permutation $\tau$ so it's not clear why the LHS mean should overpower the RHS. As I said in the remark, the $b_i$'s cannot be independent of $\tau$. – Abhishek Parab Jan 29 '17 at 3:07
• I put it as an answer, to explain myself more clearly. – Pietro Majer Jan 29 '17 at 11:16

## 1 Answer

For a given $\tau\in S_n$ and for any $j\in[n]$ define the numbers $$a_j:=\chi_{\Delta}(j)-\chi_{\Delta}(j-1)-\chi_{\Delta }(n-j)+\chi_{\Delta}(n-j+1),$$ where $\chi_\Delta:\mathbb{Z}\to\{0,1\}$ denotes the characteristic function of the set $\Delta:=\Delta(\tau)\subset\mathbb{Z}$. Also, with $c:=5n-a_n$, define $$b_j:=a_j-5j+c.$$ We may note right away that since $|a_j|\le2$, the $b_j$ are strictly decreasing, and that $b_n=0$, by the choice of the constant $c$.

For any $E\subset[n]$, for simplicity of notation we put $$\alpha(E):=\sum_{j\in E} a_j,\qquad \beta(E):=\sum_{j\in E} b_j$$ (so we may think $\alpha$ and $\beta$ as discrete signed measures supported in $[n]$).

For $i\in[n]$, summing over $j=1,\dots i$ we have

$$\alpha([i])=\chi_\Delta(i)-\chi_\Delta(n-i).$$

Incidentally, for any $i\in[n]$ we have $i\in\Delta$ if and only if, by definition, $\tau([i])\neq[i]+n-i$ thus also, since $\tau$ is bijective, if and only if $\tau([i]^c)\neq([i]+n-i)^c$, that is $\tau([n-i]+i)\neq [n-i]$ or $\tau^{-1}([n-i])\neq [n-i]+i$, which means $n-i \in \Delta^{-1}:=\Delta(\tau^{-1})$. Hence the last formula also writes $$\alpha([i])=\chi_{\Delta}(i)-\chi_{\Delta^{-1}}(i).$$ Also note that, since $n\not\in\Delta$ $$\alpha([n])=0,$$ and $$\alpha([i]+n-i)=- \alpha([n-i]) =-\chi_\Delta(n-i)+\chi_\Delta(i)= \alpha([i]).$$

We proceed showing the inequalities on the arithmetic means.

Case I. Assume $i\in\Delta\setminus\Delta^{-1}$. Then by definition of $\Delta^{-1}$, $\tau^{-1}([i])=[i]+n-i$, so that

$${\alpha([i])+ \alpha(\tau^{-1}[i])\over 2i}= {\alpha([i])+ \alpha([i]+n-i)\over2i}={\chi_{\Delta}(i)-\chi_{\Delta^{-1}}(i)\over i}={1\over i}>0,$$ and summing the arithmetic means of $-5j+c$ on the same sets we have plainly $${\beta([i])+ \beta(\tau^{-1}[i])\over 2i}>{\beta([n])\over n}.$$

Case II. Assume $i\in\Delta\cap\Delta^{-1}$. Thus $\tau^{-1}([i])\neq[i]+n-i$ and, just because $b_j$ are strictly decreasing

$${\beta([i])+ \beta(\tau^{-1}[i])\over 2i}>{\beta([i])+ \beta([i]+n-i)\over2i}$$ and since we have $\alpha([i])=\alpha([i]+n-i)=\alpha([n])=0$ because $\chi_{\Delta}(i)=\chi_{\Delta^{-1}}(i)=1$, summing as before the arithmetic means of the affine part of $b_j$, $${\beta([i])+ \beta([i]+n-i)\over2i}={\beta([n])\over n},$$ concluding the proof.

• Thank you for the answer. I made a mistake (explained above). I will award your bounty after few days so that the question will get attention. I would really appreciate if you could try this inequality too. The $b_i$'s will depend on $\tau$ now. – Abhishek Parab Jan 30 '17 at 17:14
• of course, let me just write it down nicely ;) – Pietro Majer Jan 30 '17 at 21:48
• $\phantom{...}$...done! – Pietro Majer Jan 31 '17 at 14:07
• You're welcome! Actually, I don't think I understand it more than you (I was amazed by the regular structure revealed by what seemed just a technical question; to me this is a clear sign that it comes from beautiful and deep mathematics :) ) – Pietro Majer Jan 31 '17 at 20:28
• On the technical side, the idea for the construction is: if you have two or more solutions of the weak inequalities ($\ge$), maybe not decreasing, you can sum them, and if one of them verifies a strict inequality at $\bf i$, so does the sum. Also, any affine sequence is a trivial solution of the weak inequalities (with $=$), but it can make the sum monotone if its slope is large enough. This way the problem is somehow reduced to easier ones. – Pietro Majer Jan 31 '17 at 20:29