10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Of course this is possible when $\tau$ is the long element, since then $\Delta(\tau)$ is empty. $\endgroup$ – LSpice Jan 26 '17 at 22:03
  • $\begingroup$ 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? $\endgroup$ – Pietro Majer Jan 29 '17 at 1:07
  • $\begingroup$ 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$. $\endgroup$ – Abhishek Parab Jan 29 '17 at 3:07
  • $\begingroup$ I put it as an answer, to explain myself more clearly. $\endgroup$ – Pietro Majer Jan 29 '17 at 11:16
8
+300
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Abhishek Parab Jan 30 '17 at 17:14
  • $\begingroup$ of course, let me just write it down nicely ;) $\endgroup$ – Pietro Majer Jan 30 '17 at 21:48
  • $\begingroup$ $\phantom{...}$...done! $\endgroup$ – Pietro Majer Jan 31 '17 at 14:07
  • 1
    $\begingroup$ 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 :) ) $\endgroup$ – Pietro Majer Jan 31 '17 at 20:28
  • 1
    $\begingroup$ 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. $\endgroup$ – Pietro Majer Jan 31 '17 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.