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)

Now suppose that $ss$ 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 sw(d+1)-s$, i.e., 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$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