2
$\begingroup$

We can defined the descent set of a word $w\in\mathbb{N}^n$ to be the set $D(w)=\{i\in[n-1]:w(i)>w(i+1)\}.$ Also, we can take as definition for the major index of $w$ to be $\text{maj}(w)=\sum_{d\in D(w)}d$.

Now let $k_i$ be the number of instances of $i$ in $w$. If $w\in[r]^n$ and $w(n)=s$, why is it then that w'=(12\cdots r)^{r-s}\circ w has major index \text{maj}(w')=\text{maj}(w)-k_{s+1}+\cdots+k_r?

I assume theres some sort of shift going on, but I don't see the relationship between the $\text{maj}$s. Thank you.

1 Answers 1

4

First off, I think that you have a small error in the statement of the result. Suppose that $n=5$, $r=3$, and $w=12321$, so that $s=1$, $D(w)=\{3,4\}$, and $\operatorname{maj}(w)=7$. Then w\,'=31213, D(w\,')=\{1,3\}, and \operatorname{maj}(w\,')=4=7-(k_2+k_3). It appears that the conclusion should be that \operatorname{maj}(w\,')=\operatorname{maj}(w)-(k_{s+1}+\dots+k_r).

The transformation w\mapsto w\,' replaces each element $i$ of $w$ by

i\,'=\begin{cases} i+r-s,&\text{if }1\le i\le s\\\\ i-s,&\text{if }s

Suppose that $d\in D(w)$, and let $i=w(d)$. There are two cases.

If $i\le s$, then w\,'(d)=i+r-s, and $w(d+1), so w\,'(d+1)=w(d+1)+r-s, and d\in D(w\,').

Now suppose that $s, so that i\,'=i-s. If $w(d+1)>s$ as well, then $d$ remains a descent of w\,', just as in the first case. If $w(d+1)\le s$, then

w\,'(d+1)=w(d+1)+r-s>r-s\ge i-s=i\,'\;,

so d\notin D(w\,').

Putting the two cases together, we see that D(w)\setminus D(w\,')=\{d\in D(w):w(d+1)\le s

and we need now to identify the indices that belong to D(w\,')\setminus D(w).

Suppose that d\in D(w\,')\setminus D(w). It’s clear from $(1)$ that this happens iff $w(d)\le s and $w(d)+r-s>w(d+1)-s$, i.e., iff $w(d)\le s. The final inequality is automatic, so d\in D(w\,')\setminus D(w) iff $w(d)\le s.

Let m=\operatorname{maj}(w)-\operatorname{maj}(w\,'); clearly

\begin{align*}m&=\sum\{d:d\in D(w)\setminus D(w\,')\}-\sum\{d:d\in D(w\,')\setminus D(w)\}\\\\ &=\sum\{d:w(d+1)\le s

Say that an element of $w$ is small if it is at most $s$ and large otherwise. Let $\bar w$ be the $n$-bit string obtained from $w$ by replacing each small element of $w$ by $0$ and each large element by $1$. Let $D(\bar w)$ be the set of descents of $\bar w$, and let $A(\bar w)$ be the set of ascents of $\bar w$. It follows from $(2)$ that $m=\sum_{d\in D(\bar w)}d-\sum_{a\in A(\bar w)}a\;.\tag{3}$ Let $k$ be the number of $1$’s in $\bar w$; clearly $k=k_{s+1}+\dots+k_r$, so we’re done if we can show that $(3)$ counts the number of $1$’s in $\bar w$.

Note first that that the last bit of $\bar w$ is $0$. If every bit of $\bar w$ is $0$, then $m=0=k$. Otherwise let $t>0$ be the number of descents of $\bar w$, and let $d_1<\ldots be the descents. If the first bit of $\bar w$ is $0$, there must also be $t$ ascents, say $a_1<\ldots, and they must alternate with the descents: $a_1 $(4)$ also holds if the first bit of $\bar w$ is $1$, provided that in that case we set $a_1=0$. Thus, we can rewrite $(3)$ as $m=\sum_{i=1}^t(d_i-a_i)\;.\tag{5}$ But $d_i-a_i$ is just the number of $1$’s in the $i$-th maximal block of consecutive $1$’s, so the righthand side of $(5)$ is $k$, and we’re done.

(There may well be an easier way to do this; it’s new to me, and I was working it out as I went along.)

  • 0
    Wow, many thanks Brian, and you're right, I think I missed some parentheses. I appreciate the details of your answer.2012-02-17