Relation between major indices of words?

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.

-

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<i\le r\;. \end{cases}\tag{1}$$

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)<w(d)$, so $w\,'(d+1)=w(d+1)+r-s$, and $d\in D(w\,')$.

Now suppose that $s<i\le r$, 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<w(d)\}\;,$$

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<w(d+1)$ and $w(d)+r-s>w(d+1)-s$, i.e., iff $w(d)\le s<w(d+1)<w(d)+r$. The final inequality is automatic, so $d\in D(w\,')\setminus D(w)$ iff $w(d)\le s<w(d+1)$.

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<w(d)\}-\sum\{d:w(d)\le s<w(d+1)\}\;.\tag{2} \end{align*}

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<d_t$ be the descents. If the first bit of $\bar w$ is $0$, there must also be $t$ ascents, say $a_1<\ldots<a_t$, and they must alternate with the descents: $$a_1<d_1<a_2<d_2<\ldots<a_t<d_t\;.\tag{4}$$ $(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.)

-
Wow, many thanks Brian, and you're right, I think I missed some parentheses. I appreciate the details of your answer. –  Nastassja Feb 17 '12 at 8:02