% Format a4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\catcode'32=9
\magnification=1200

% particularite du pilote canon

\voffset=1cm
\hoffset=0cm

\font\tenpc=cmcsc10
%\font\eightpc=cmcsc8

% Charge des fontes de 8 et 6 points :
\font\eightrm=cmr8
\font\eighti=cmmi8
\font\eightsy=cmsy8
\font\eightbf=cmbx8
\font\eighttt=cmtt8
\font\eightit=cmti8
\font\eightsl=cmsl8
\font\sixrm=cmr6
\font\sixi=cmmi6
\font\sixsy=cmsy6
\font\sixbf=cmbx6

\skewchar\eighti='177 \skewchar\sixi='177
\skewchar\eightsy='60 \skewchar\sixsy='60

% Chargement des fontes AMS

\font\tengoth=eufm10
%\font\tenbboard=msym10
\font\eightgoth=eufm8
%\font\eightbboard=msym8
\font\sevengoth=eufm7
%\font\sevenbboard=msym7
\font\sixgoth=eufm6
\font\fivegoth=eufm5

\newfam\gothfam
%\newfam\bboardfam

\catcode`\@=11

\def\raggedbottom{\topskip 10pt plus 36pt
\r@ggedbottomtrue}
\def\pc#1#2|{{\bigf@ntpc #1\penalty
\@MM\hskip\z@skip\smallf@ntpc #2}}

\def\tenpoint{%
  \textfont0=\tenrm \scriptfont0=\sevenrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\tenrm}%
  \textfont1=\teni \scriptfont1=\seveni \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\teni}%
  \textfont2=\tensy \scriptfont2=\sevensy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\tengoth \scriptfont\gothfam=\sevengoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\tengoth}%
%  \textfont\bboardfam=\tenbboard \scriptfont\bboardfam=\sevenbboard
%  \scriptscriptfont\bboardfam=\sevenbboard
%  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\tenit
  \def\it{\fam\itfam\tenit}%
  \textfont\slfam=\tensl
  \def\sl{\fam\slfam\tensl}%
  \textfont\bffam=\tenbf \scriptfont\bffam=\sevenbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\tenbf}%
  \textfont\ttfam=\tentt
  \def\tt{\fam\ttfam\tentt}%
  \abovedisplayskip=12pt plus 3pt minus 9pt
  \abovedisplayshortskip=0pt plus 3pt
  \belowdisplayskip=12pt plus 3pt minus 9pt
  \belowdisplayshortskip=7pt plus 3pt minus 4pt
  \smallskipamount=3pt plus 1pt minus 1pt
  \medskipamount=6pt plus 2pt minus 2pt
  \bigskipamount=12pt plus 4pt minus 4pt
  \normalbaselineskip=12pt
  \setbox\strutbox=\hbox{\vrule height8.5pt depth3.5pt width0pt}%
  \let\bigf@ntpc=\tenrm \let\smallf@ntpc=\sevenrm
  \let\petcap=\tenpc
  \normalbaselines\rm}
\def\eightpoint{%
  \textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\eightrm}%
  \textfont1=\eighti \scriptfont1=\sixi \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\eighti}%
  \textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\eightgoth \scriptfont\gothfam=\sixgoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\eightgoth}%
%  \textfont\bboardfam=\eightbboard \scriptfont\bboardfam=\sevenbboard
%  \scriptscriptfont\bboardfam=\sevenbboard
%  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\eightit
  \def\it{\fam\itfam\eightit}%
  \textfont\slfam=\eightsl
  \def\sl{\fam\slfam\eightsl}%
  \textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\eightbf}%
  \textfont\ttfam=\eighttt
  \def\tt{\fam\ttfam\eighttt}%
  \abovedisplayskip=9pt plus 2pt minus 6pt
  \abovedisplayshortskip=0pt plus 2pt
  \belowdisplayskip=9pt plus 2pt minus 6pt
  \belowdisplayshortskip=5pt plus 2pt minus 3pt
  \smallskipamount=2pt plus 1pt minus 1pt
  \medskipamount=4pt plus 2pt minus 1pt
  \bigskipamount=9pt plus 3pt minus 3pt
  \normalbaselineskip=9pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \let\bigf@ntpc=\eightrm \let\smallf@ntpc=\sixrm
  \normalbaselines\rm}

\let\bboard=\bf

\tenpoint

%���������������������� dactylographie fran�aise �����������������
% Conflit avec fplain (redefinition ?)
\catcode`\;=\active
\def;{\relax\ifhmode\ifdim\lastskip>\z@\unskip\fi
\kern\fontdimen2 \font\kern -1.2 \fontdimen3 \font\fi\string;}

\catcode`\:=\active
\def:{\relax\ifhmode\ifdim\lastskip>\z@\unskip\fi\penalty\@M\
\fi\string:}

\catcode`\!=\active
\def!{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string!}

\catcode`\?=\active
\def?{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string?}

\def\^#1{\if#1i{\accent"5E\i}\else{\accent"5E #1}\fi}
\def\"#1{\if#1i{\accent"7F\i}\else{\accent"7F #1}\fi}

\frenchspacing

%���������������������� format de sortie �����������������

\newif\ifpagetitre
\newtoks\auteurcourant \auteurcourant={\hfil}
\newtoks\titrecourant \titrecourant={\hfil}

\def\appeln@te{}
\def\vfootnote#1{\def\@parameter{#1}\insert\footins\bgroup\eightpoint
  \interlinepenalty\interfootnotelinepenalty
  \splittopskip\ht\strutbox % top baseline for broken footnotes
  \splitmaxdepth\dp\strutbox \floatingpenalty\@MM
  \leftskip\z@skip \rightskip\z@skip
  \ifx\appeln@te\@parameter\indent \else{\noindent #1\ }\fi
  \footstrut\futurelet\next\fo@t}

\pretolerance=500 \tolerance=1000 \brokenpenalty=5000
\newdimen\hmargehaute \hmargehaute=0cm
\newdimen\lpage \lpage=13.3cm
\newdimen\hpage \hpage=20cm
\newdimen\lmargeext \lmargeext=1cm
\hsize=11.25cm
\vsize=18cm
\parskip 0pt
\parindent=12pt

\def\margehaute{\vbox to \hmargehaute{\vss}}%
\def\margebasse{\vss}

\output{\shipout\vbox to \hpage{\margehaute\nointerlineskip
  \corpsdepage\margebasse}
  \advancepageno \global\pagetitrefalse
  \ifnum\outputpenalty>-20000 \else\dosupereject\fi}

\def\corpsdepage{\hbox to \lpage{\hss\pagetexte\hskip\lmargeext}}
\def\pagetexte{\vbox{\makeheadline\pagebody\makefootline}}
\headline={\ifpagetitre\titleheadline \else
  \ifodd\pageno\rightheadline \else\leftheadline\fi\fi}
\def\leftheadline{\eightpoint\hfil\the\auteurcourant\hfil}
\def\rightheadline{\eightpoint\hfil\the\titrecourant\hfil}
\def\titleheadline{\hfill}
\pagetitretrue

\def\footnoterule{\kern-6\p@
  \hrule width 2truein \kern 5.6\p@} % the \hrule is .4pt high



\let\rmpc=\sevenrm
\def\pd#1#2 {\pc#1#2| }

\def\pointir{\discretionary{.}{}{.\kern.35em---\kern.7em}\nobreak
\hskip 0em plus .3em minus .4em }

\def\resume#1{\vbox{\eightpoint \pc R\'ESUM\'E|\pointir #1}}
\def\abstract#1{\vbox{\eightpoint \pc ABSTRACT|\pointir #1}}

\def\titre#1|{\message{#1}
              \par\vskip 30pt plus 24pt minus 3pt\penalty -1000
              \vskip 0pt plus -24pt minus 3pt\penalty -1000
              \centerline{\bf #1}
              \vskip 5pt
              \penalty 10000 }

\def\section#1|{\par\vskip .3cm
                {\bf #1}\pointir}

\def\ssection#1|{\par\vskip .2cm
                {\it #1}\pointir}

\long\def\th#1|#2\finth{\par\vskip 5pt
              {\petcap #1\pointir}{\it #2}\par\vskip 3pt}

\long\def\tha#1|#2\fintha{\par\vskip 5pt
                    {\petcap #1.}\par\nobreak{\it #2}\par\vskip 3pt}
\def\cf{{\it cf}}

\def\rem#1|{\par\vskip 5pt
            {{\it #1}\pointir}}

\def\rema#1|{\par\vskip 5pt
             {{\it #1.}\par\nobreak }}

%
\def\ieme{\raise 1ex\hbox{\pc{}i\`eme|}}
\def\omini{\raise 1ex\hbox{\pc{}o|}}
\def\emini{\raise 1ex\hbox{\pc{}e|}}
\def\ermini{\raise 1ex\hbox{\pc{}er|}}
\def\remini{\raise 1ex\hbox{\pc{}re|}}

%reference pour un article :
\def\article#1|#2|#3|#4|#5|#6|#7|
    {{\leftskip=7mm\noindent
     \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3, {\it #4}, vol.\nobreak\ {\bf #5}, {\oldstyle #6},
     p.\nobreak\ #7.\par}}
%reference pour un livre :
\def\livre#1|#2|#3|#4|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
    \llap{[#1]\hskip.35em}{#2}\pointir
    {\it #3}\pointir #4.\par}}
%reference complementaire :
\def\divers#1|#2|#3|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3.\par}}
%
\mathchardef\conj="0365
\def\dem{\par{\it D\'emonstration}\pointir}
\def\qed{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}}

\def\virg{\raise 2pt\hbox{,}}   % virgule apr�s une fraction

\def\cqfd{\penalty 500 \hbox{\qed}\par\vskip 3pt}
\long\def\entourer#1{\hbox{\vrule\vbox{\hrule\hbox{\kern15pt\vbox{\kern5pt
{#1}\kern5pt}\kern15pt}\hrule}\vrule}}
\def\\S {\vskip 5pt\hskip .5cm plus .1cm minus .1cm\relax}

%les differents retraits, voir aussi \item
\def\enonce#1|#2\finenonce{{\par\leftskip=36pt
\noindent\hbox to 0pt{\kern-\leftskip#1\hfill}{#2}\par}}

\def\senonce#1|#2\finsenonce{{\par\leftskip=36pt
\noindent\hbox to 0pt{\kern-24pt #1\hfill}{#2}\par}}

\def\ssenonce#1|#2\finssenonce{{\par\leftskip=48pt
\noindent\hbox to 0pt{\kern-24pt #1\hfill}{#2}\par}}

\def\decale#1|{\par\noindent\hskip 28pt\llap{#1}\kern 5pt}
\def\decaledecale#1|{\par\noindent\hskip 34pt\llap{#1}\kern 5pt}
% pour les titres en deux lignes et les sections sans point-tiret :
\def\titrea#1|#2|{\message{#1 #2}
  \par\vskip.5cm plus .1cm minus .1cm\penalty -1000
  \centerline{\bf #1}
  \centerline{\bf #2}
  \vskip 5pt
  \penalty 10000 }
\def\sectiona#1|{\par\vskip .3cm
  {\bf #1.}
  \par\nobreak\vskip 3pt }
\def\ssectiona#1|{\par\vskip .2cm
  {\it #1.}
  \par\nobreak\vskip 2pt }

\def\rest#1{\ifinner\setbox1=\hbox{$\textstyle{#1}$}
            \else\setbox1=\hbox{$\displaystyle{#1}$}\fi
            \dimen1=\ht1
            \advance\dimen1 by\dp1
            \divide\dimen1 by 2
            \box1\lower 2pt\hbox{$\left|\vbox to\dimen1{}\right.$}}

\def\displaylinesno#1{\displ@y\halign{
\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}&
\llap{$##$}\crcr#1\crcr}}

\def\ldisplaylinesno#1{\displ@y\halign{ 
\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}&
\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr#1\crcr}}

\def\Eqalign#1{\null\,\vcenter{\openup\jot\m@th\ialign{
\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
&&\quad\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
\crcr#1\crcr}}\,}


% matrice justifi\'ee \`a droite : \hfil coef dans chaque ligne

\def\matrixd#1{\null \,\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$&&\quad \hfil $##$\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}\,}

\def\pmatrixd#1{\left(\matrixd{#1}\right)}

% ���������������������  syst�me d'�quations  ���������������������
% copi\'e sur \eqalign, on s'en sert comme une matrice
% syntaxe : signe & coef & inconnue
% les coef sont justifi\'es \`a droite (\hfil coef)
% et les inconnues \`a gauche (inconnue\hfil)
% attention : double && avant le signe =
% pour justification correcte !
% Exemple : $$\system{
%             &2 &x &- &3 & y & = &&       -5 \cr
%            -&  &x &+ &  & y & = && \hfill 6 \cr
%           }$$

\def\system#1{\left\{\null\,\vcenter{\openup1\jot\m@th
\ialign{\strut$##$     &\hfil$##$&$##$\hfil&&
       \enskip$##$\enskip&\hfil$##$&$##$\hfil\crcr
        #1\crcr}}\right.}

\catcode`\@=12
% Fin du format %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\input /home/institut/desar/TeX/a4.tex

%\nopagenumbers
\auteurcourant={J. D\'esarm\'enien}
\titrecourant={Modulo-$n$ study of Mahonian statistics}
%\font\twelvebf=TimesB at 12pt

\overfullrule=0pt
\medmuskip=3.5mu plus 1mu minus 3.5mu
\thickmuskip=4mu plus 2mu

\let\Tenpoint=\tenpoint
\let \Eightpoint=\eightpoint

\def\imaj{\mathop{\rm imaj}\nolimits}
\def\rec{\mathop{\rm rec}\nolimits}
\def\des{\mathop{\rm des}\nolimits}

% \line{Combinatoire/{\it Combinatorics}\hfil\the\day/\the\month}
\vglue 0pt\bigskip\bigskip
\centerline{{\bf Modulo-$n$ study of Mahonian statistics}}
\bigskip
\centerline{Jacques \petcap D\'esarm\'enien\footnote{}{With the support of
P.R.C. Math.-Info.}}

\bigskip

[This is a translation of the
paper ``\'Etude modulo n des statistiques mahoniennes'' from French.
The paper was originally published in
{\it S\'eminaire Lotharingien de Combinatoire}, B22a (1989).
 The
translation was done by Darij Grinberg. The translation
occasionally veers away from the original wording and corrects
a few typos and minor oversights.

The author thanks Darij Grinberg for his careful reading of the original French
version, for his accurate and precise translation as well as for his most
valuable remarks.]

\titre Introduction|
Under the general notion of Mahonian statistics, one subsumes a certain
number of statistics defined on some sets of words of length $n$.
% [{\it Translator's note:} What does ``order statistic'' mean? Is there
% any difference to just a statistic?]
Examples of such statistics are the number of inversions of permutations,
their major index or their imajor index, and the same statistics
on the words over the alphabet $\{ 0,1\} $. One can furthermore impose
constraints on the form (``up-down sequence'', for example) of
permutations.
% [{\it Translator's note:} Does ``major-inverse index''
% mean the imajor index?]
A celebrated result by Foata and Sch\"utzenberger [F--S]
establishes in this case the equidistribution of the number of inversions
and the imajor index. Thus one needs only study the major index
of a Young tableau, which allows one to use the whole arsenal of classical
algebra.
Such an approach has been used, in particular, in
[D2, D--F1, D--F2, D--F3, D--F4].

The purpose of this paper is to establish an equidistribution property
of Young tableaux of a given form with respect to the modulo-$n$ value
of their major index. From this, we will then deduce the same property
for all the statistics on permutations, and many analogous results.

We will also obtain the explicit decomposition of the representation of
the symmetric group on the free Lie algebra associated to a partition
$n$. This result, due to Kraskiewicz and Weyman [K--W],
is cited by Reutenauer [R].

The tools we will use are, first, the relationship between certain
characters of the symmetric group and the major index of Young tableaux,
and second, a lemma of arithmetical nature.

\titre 1. The arithmetical lemma|
We shall use the notation $(a,b)$ for the greatest common
divisor of two integers $a$ and $b$.

Let $n$ be a positive integer. Denote by $\Phi _n(q)$ the $n$-th
cyclotomic polynomial (so that $\Phi _1(q)=1-q$, $\Phi _2(q)=1+q$, \dots).
We will need the {\it Ramanujan sums}
$c_n(m)=\sum _{(i,n)=1}\zeta ^{im}$, where $\zeta $ denotes a primitive
$n$-th root of unity ({\it cf.}~[H--W]).
One can easily find the explicit value of Ramanujan sums in terms of the
M\"obius function $\mu (n)$ and Euler's totient function $\varphi (n)$.
More precisely, the following result, due to H\"older, holds:

\th Lemma 1.1 {{\rm [H--W, p.~238}]}|Set $(m,n)=\delta $ and
$n=\delta N$; then
$$c_n(m)={\mu (N)\varphi (n)\over \varphi (N)}.$$
In particular, if $(n_1,m)=(n_2,m)$, then
$c_n(m_1)=c_n(m_2)$.
\finth

Let now $P(q)=\sum _{0\leq k\leq n-1}a_kq^k$ be a polynomial with integer
coefficients. Following the terminology of Cohen [C], we say that the
coefficients of $P(q)$, and, by abuse of notation, the polynomial $P(q)$
itself, are {\it even} modulo $n$ if, for every $k$ and $l$ from $0$ to
$n-1$, the equality $(k,n)=(l,n)$ implies the equality of coefficients
$a_k=a_l$.

The functions even modulo $n$ have been studied by Cohen, who has shown
that they coincide with the linear combinations of Ramanujan sums. The
latter have been utilized, in particular, by Nicol and Vandiver [N--V],
in enumerating certain combinatorial configurations.

\th Proposition 1.2|Let $P(q)$ be a polynomial with integer coefficients
and degree less than $n$. Then, the following two properties are
equivalent:

\indent\indent\llap{{\rm (i)\ }}
For every divisor $d$ of $n$, the residue $r_d$ of $P(q)$ modulo
$\Phi _d(q)$ is an integer.

\indent\indent\llap{{\rm (ii)\ }}
The polynomial $P(q)$ is even modulo $n$.

Moreover, if these two equivalent properties (i) and (ii) are satisfied,
one has
$$a_k={1\over n}\sum _{d|n}r_d c_d(k)\qquad {\rm and}\qquad
r_\delta =\sum _{d|n}a_{n/d}c_d(n/\delta ).$$
\finth

\ssection Proof of Proposition 1.2|
The polynomials satisfying (i) and those satisfying (ii) clearly form
${\bboard Z}$-modules of the same rank, and this rank is equal to the
number of divisors of $n$.
% Hence, in order to show the equivalence of these
% properties, it is enough to show that one implies the other.
% [{\it Translator's note:} I don't know what ``one implies the other" means
% here. If it means ``(i) implies (ii) and (ii) implies (i)", then this is
% a tautology, and there is no need to invoke the rank of
% ${\bboard Z}$-modules. If it means ``(i) implies (ii) or (ii) implies (i)",
% then this argument is incomplete, since two free ${\bboard Z}$-modules $A$
% and $B$ of the same finite rank don't necessarily have to be identical when
% one knows that $A = B$. One could salvage this argument by working with
% ${\bboard Q}$-vector spaces in lieu of ${\bboard Z}$-modules; this allows
% proving Proposition~1.2 with ``integer" replaced by ``rational" everywhere.
% Now, an additional argument (a standard one, using the fact that any
% algebraic integer which is rational must be an actual integer) allows to
% deduce the actual Proposition~1.2 from this.]

Assume that property (ii) holds; in other words, whenever $(k,n)=n/d$, we
have $a_k=a_{n/d}$. In order to prove the property (i), it suffices to see
that whenever $q$ is set to any primitive $\delta $-th root of unity, with
$\delta |n$, the value attained by $P(q)$ is a number $r_\delta $ depending
only on $\delta$ (but not on the choice of the primitive $\delta $-th root
of unity). The primitive $\delta $-th roots of unity are the
$\zeta ^i$ with $(i,n)=n/\delta $, and for these we have
$$\eqalign{P(\zeta ^i)
  &=\sum _{0\leq k\leq n-1}a_k\zeta ^{ik},\cr
  &=\sum _{d|n}a_{n/d}\sum _{(k,n)=n/d}\zeta ^{ik}.\cr}$$
One can write $k=k'{n\over d}$ where $(k',d)=1$; moreover, if
$\zeta $ is a primitive $n$-th root of unity, then $\zeta ^{n/d}$
is a primitive $d$-th root of unity. Thus,
$$\eqalign{P(\zeta ^i)
  &=\sum _{d|n}a_{n/d}\sum _{(k',d)=1}\zeta ^{ik'n/d},\cr
  &=\sum _{d|n}a_{n/d}c_d(i),\cr
  &=\sum _{d|n}a_{n/d}c_d(n/\delta ).\cr}$$
Hence, one obtains property (i) and the value for $r_\delta $ announced.

Conversely, let us show that (i) implies (ii), and prove the formulas
for the $a_k$ and $r_\delta$ in terms of each other.
In order to verify that the $a_k$ can be
expressed in terms of the $r_d$ as indicated, one can use an inversion
formula due to Cohen [C, Theorem~2]. In order for this paper to
remain self-contained, we are going to actually establish this inversion
formula directly in our particular case.

Assume that property (i) holds. Let $\zeta ^0, \zeta ^1,\ldots,
\zeta ^{n-1}$ be the $n$ distinct $n$-th roots of unity. The primitive
$d$-th roots of unity thus are the $\zeta ^k$ for $(k,n)=n/d$.
Since $P(q)\equiv r_d \pmod{\Phi _d(q)}$, we have, for every $k$ that
satisfies $(k,n)=n/d$, the equality $P(\zeta ^k)=r_d$. Since we now know
the value of $P(q)$ at $n$ distinct points, we can apply the Lagrange
interpolation formula:
$$\eqalign{P(q)
  &=\sum _{0\leq i\leq n-1}P(\zeta ^i)\prod _{j\not=i}{(q-\zeta ^j)\over (\zeta ^i-\zeta ^j)},\cr
  &=\sum _{0\leq i\leq n-1}P(\zeta ^i)\prod _{j\not=i}{(\zeta ^{n-i}q-\zeta ^{n-i+j})\over (1-\zeta ^{n-i+j})},\cr
  &=\sum _{0\leq i\leq n-1}P(\zeta ^i)\prod _{j\not=0}{(\zeta ^{n-i}q-\zeta ^j)\over (1-\zeta ^j)}.\cr}$$

Since the polynomial whose roots are $\zeta ^j$ for $j\not=0$ (each only
once) is $\sum _{0\leq k\leq n-1}q^k$, we thus have
$$P(q)={1\over n}\sum _{0\leq i\leq n-1}P(\zeta ^i)\sum _{0\leq k\leq n-1}\zeta ^{(n-i)k}q^k.$$
Now, regrouping the indices $i$ according to the value $n/d$
of $(i,n)$, and replacing $P(\zeta ^i)$ by $r_d$, we can rewrite
this as
$$\eqalign{P(q)
  &={1\over n}\sum _{d|n}r_d\sum _{(i,n)=n/d}\sum _{0\leq k\leq n-1}\zeta ^{(n-i)k}q^k,\cr
  &={1\over n}\sum _{0\leq k\leq n-1}q^k\sum _{d|n}r_d\sum _{(i,n)=n/d}\zeta ^{ik},\cr
  &={1\over n}\sum _{0\leq k\leq n-1}q^k\sum _{d|n}r_d c_d(k).\cr}$$
Thus one obtains the value announced for the coefficient $a_k$.

Now, property (ii) readily follows. Indeed, whenever
$(k,n)=(l,n)$, we have $(k,d)=(l,d)$ for every divisor $d$ of $n$, and
thus $a_k = a_l$ according to the formula we have shown for the
coefficients $a_k$.

This completes the proof of Proposition 1.2.

\titre 2. Characters and congruences|
Regarding the definitions and general properties of symmetric functions,
the reader is referred to [M]. The word ``shape'' shall in the following
refer to an arbitrary skew partition.
We know that the power-sum symmetric
functions $p_\lambda $, where $\lambda $ ranges over the partitions,
form a $\bboard Q$-basis of the vector space of symmetric functions.
Moreover, to each representation of a symmetric group, a symmetric
function is associated. In this way, the Schur functions $S_\lambda $
for partitions (or straight shapes) $\lambda $ are associated to the
irreducible representations.
The Schur functions form a $\bboard Z$-basis of the $\bboard Z$-module
of symmetric functions.
More precisely, if we denote by $\chi _\lambda (\mu )$ the value at
$\mu $ of the irreducible character of the symmetric group associated to
$\lambda $, then one has the decompositions
$$\displaylines{
  S_\lambda =\sum _\mu {1\over z_\mu }\chi _\lambda (\mu )p_\mu ,\cr
  p_\mu =\sum _\lambda \chi _\lambda (\mu )S_\lambda ,\cr}$$
where $z_\mu $ is the integer $1^{\mu _1}2^{\mu _2}\ldots
\mu _1!\,\mu _2!\ldots$, when $\mu $ is a partition consisting of
$\mu _1$ parts equal to $1$, of $\mu _2$ parts equal to $2$, \dots

Given a standard Young tableau $T$ of shape $\lambda $ and size $n$, let
us denote by $\rec T$ the set of all integers $i$ with $1\leq i\leq n-1$
such that $i+1$ lies farther to the left (in the wider sense, i. e.,
$i+1$ lies in the same column as $i$ or in a column to the left of $i$)
than $i$ in
$T$ (these integers $i$ are called the {\it recoils} of $T$),
and let us denote by $\imaj T$ the sum of the integers $i\in  \rec T$
(this is called the {\it imajor index} of $T$).
In particular, if the shape $\lambda $ is a {\it ribbon} ({\it cf.}~[D2]),
then the tableau $T$ can be considered as a permutation whose shape is
given by $\lambda $, and the statistic thus defined on $T$ coincides with
the imajor index of this permutation.
[Here, the ``shape'' of a permutation is
defined as the shape of a standard Young tableau of ribbon shape whose
reading word is the permutation. This is just another way to encode the
descent set of the permutation.]
Denote by $(q,q)_n=(1-q)(1-q^2)\cdots(1-q^n)$
the $q$-factorial.

The connection between Schur functions and Mahonian statistics is
essentially contained in the following lemma ({\it cf.} [D--F1]):

\th Lemma 2.1|The generating function of the statistic
{\rm imaj} on the standard tableaux of shape $\lambda$ is given by
$$\sum _{T}q^{\imaj T}=(q,q)_n S_\lambda  (1,q,q^2,\ldots),$$
where the sum ranges over all standard tableaux of shape $\lambda $.
\finth

Let $P_\lambda (q)=\sum _{0\leq k\leq n-1}a_k(\lambda )q^\lambda $ be the
polynomial whose coefficient $a_k(\lambda )$ is the number of tableaux $T$
of shape $\lambda $ such that $\imaj T\equiv k \pmod{n}$.
We can now state the main result of this article.

\th Theorem 2.2|For any given shape $\lambda $ of size $n$, the value of
$a_k(\lambda )$ depends only on the greatest common divisor $(k,n)$ (but
not on $k$). More precisely,
$$a_k(\lambda )={1\over n}\sum _{d|n} \chi _\lambda (d^{n/d})c_d(k).$$
\finth

\ssection Proof of Theorem 2.2|
Let $d|n$. Since $1-q^n$ is divisible by $\Phi _d(q)$,
the remainder modulo $\Phi _d(q)$ of $P_\lambda (q)$ and that of the
generating series of imaj on the tableaux of shape $\lambda $ are
equal. By virtue of Lemma~2.1, it equals the remainder of
$(q,q)_n S_\lambda (1,q,q^2,\ldots)$ modulo $\Phi _d(q)$.

We can thus use the expression of $S_\lambda $ as a
linear combination of power-sum symmetric functions. We thus obtain
$$(q,q)_n S_\lambda (1,q,q^2,\ldots)=\sum _\mu  {1\over z_\mu }\chi _\lambda (\mu )  T_\mu (q),$$
where
$$T_\mu (q)=(q ,q)_n p_\mu (1,q,q^2,\ldots).$$
One easily sees that
$$T_\mu (q)=
  {(1-q)(1-q^2)\cdots (1-q^n)\over
  (1-q)^{\mu _1}(1-q^2)^{\mu _2}\cdots (1-q^n)^{\mu _n}}.$$

The only factors appearing in the preceding expression are cyclotomic
polynomials. It is not hard to find the remainder modulo any cyclotomic
polynomial ({\it cf.}~[D1, D2, D--F4]). Here, we are only interested in
the remainder modulo $\Phi _d(q)$, for which we will rederive the result.
The multiplicity of the factor $\Phi _d(q)$ in $T_\mu (q)$ is
$${n\over d}-(\mu _d+\mu _{2d}+\cdots+\mu _n).$$
Since
$$n=\mu _1+2\mu _2+\cdots+n\mu _n\geq d(\mu _d+\mu _{2d}+\cdots+\mu _n),$$
it follows that $T_\mu (q)$ is divisible by $\Phi _d(q)$ unless
$\mu =d^{n/d}$. In the latter case,
$$T_{d^{n/d}}(q)={(1-q)\cdots(1-q^d)(1-q^{d+1})\cdots(1-q^{2d})
  \cdots (1-q^n)\over (1-q^d)^{n/d}},$$
and substituting for $q$ any primitive $d$-th root of unity in the
preceding expression gives
$$T_{d^{n/d}}(q)\equiv d^{n/d}(n/d)!=z_{d^{n/d}} \pmod{\Phi _d(q)}.$$

Consequently, one has the congruence
$$(q,q)_n S_\lambda (1,q,q^2,\ldots)\equiv \chi _\lambda (d^{n/d}) \pmod{\Phi _d(q)}.$$
The condition (i) of Proposition~1.2 is thus satisfied for the
polynomial $P_\lambda (q)$, and Theorem~2.2 is demonstrated.

\titre 3. Combinatorial consequences|%
Theorem~2.2 can be applied to all shapes $\lambda $, which
includes ribbons, as mentioned above.
The standard Young tableaux of a ribbon shape are exactly the permutations whose
shape is given by the ribbon.
By taking linear combinations of Schur functions of ribbon shape,
one obtains permutations whose shape is subject to certain conditions.
It is precisely on these sets of permutations that Foata and
Sch\"utzenberger [F--S] have proven the equidistribution of the number
of inversion and the imajor index. One can thus deduce from
Theorem~2.2 the following result.

\th Proposition 3.1|The number of permutations of $[1,n]$
subject to given conditions on their shape and whose number of inversions
is congruent to $k$ modulo $n$ depends only on the greatest common divisor
$(k,n)$ and on the conditions (but not on $k$).
\finth

One can deduce analogous results for all the sequences analogous to the
classical number sequences studied in [D2]: alternating permutations,
Eulerian permutations, desarrangements,~\dots

We have studied, following Gessel [D--W], the symmetric functions
associated to Lyndon words of a given type. In a fashion completely
analogous to our proof of Lemma~2.1, one can deduce the existence of
symmetric functions $L_\lambda $ of degree $n$ such that the generating
function of the statistic $\imaj$ ranging over the permutations whose
cycle type is $\lambda $ equals $(q,q)_n L_\lambda (1,q,q^2,\ldots)$.
By decomposing these functions $L_\lambda $ as sums of Schur functions,
and applying Theorem~2.2 to each of the Schur functions, one obtains the
following result.

\th Proposition 3.2|The number of permutations of $[1,n]$
whose cycle type is $\lambda $ and whose imajor index is congruent
to $k$ modulo $n$ depends only on the greatest common divisor of $k$ and
$n$ and on $\lambda$ (but not on $k$).
\finth

A case particularly worthy of interest is that where $\lambda $ is a
partition with only one part; this part must of course be $n$.
The permutations with this cycle type are thus the cyclic permutations.
In this case, the function $L_n$, a weighted sum of Lyndon words of
length $n$, can be evaluated by P\'olya's theorem:
$$L_n={1\over n}\sum _{d|n}\mu (d) p_d^{n/d}.$$
Now, let us write this weighted-sum decomposition as a sum of Schur
functions:
$$\eqalign{L_n
  &={1\over n}\sum _{d|n}\sum _\lambda  \mu (d) \chi _\lambda (d^{n/d}) S_\lambda ,\cr
  &=\sum _\lambda \bigl({1\over n}\sum _{d|n}\mu (d) \chi _\lambda
(d^{n/d})\bigr)S_\lambda,\cr
  &=\sum _\lambda a_1(\lambda) S_\lambda.\cr}$$
The latter expression of $L_n$ results from Theorem~2.2 and from the
corollary to Lemma~1.1 stating that $c_d(1)=\mu (d)$.
We can thus deduce the following decomposition, obtained by other means
by Kraskiewicz and Weyman [K--W].

\th Proposition 3.3|The multiplicity of $S_\lambda $ in $L_n$ equals the
number of standard Young tableaux of shape $\lambda $ whose imajor index
is congruent to $1$ modulo $n$.
\finth

This result, as Reutenauer [R] indicates, has further consequences.
Indeed, let us start at the identity of the preceding proposition:
$$L_n=\sum _\lambda  a_1(\lambda ) S_\lambda .$$
Using the techniques and the notations of [D--W], we can write
$$L_n=\sum _\lambda  a_1(\lambda ) \sum _T \sum _{s\perp \rec T} w(s),$$
where the second sum ranges over the standard tableaux $T$ of shape
$\lambda $. One can rewrite
$$L_n=\sum _{E\subset [1,n-1]}\sum _{s\perp E} w(s) A^E ,$$
where $A^E$ is the number of pairs of standard tableaux
$(U,V)$ of order $n$, of same shape, satisfying $\imaj U\equiv 1\pmod n$
and $\rec T=E$.

The Robin\-son-Schensted-Sch\"utzen\-berger construction establishes
precisely a bijection between the pairs $(U,V)$ of standard Young
tableaux of equal shape and the permutations $\sigma $.
Moreover, the set of recoils of $U$ equals the set of recoils of
$\sigma $ and the set of recoils of $V$ equals the set of descents of
$\sigma $. Consequently, $A^E$ is also the number of permutations
$\sigma $ of $[1,n]$ whose set of descents is $E$ and for which
$\imaj \sigma $ is congruent to $1$ modulo $n$.

On the other hand,
$$L_n=\sum _{E\subset [1,n-1]}\sum _{s\perp E} w(s) C^E,$$
where $C^E$ is the number of cyclic permutations of $[1,n]$ whose set
of descents is $E$ ({\it cf.}~[D--W]). By comparing the two equalities
for $L_n$ (and by solving a triangular system of equations), we thus
conclude the equality $A^E=C^E$. Using also the result of Foata and
Sch\"utzenberger, we thus have established the following proposition,
due to Reutenauer [R].

\th Proposition 3.4|Let $E\subset [1,n-1]$. The following sets have the
same cardinality:

\indent\indent\llap{{\rm (i)\ }}The cyclic permutations whose set
of descents is $E$;

\indent\indent\llap{{\rm (ii)\ }}The permutations whose set of descents
is $E$ and whose imajor index is congruent to $1$ modulo $n$;

\indent\indent\llap{{\rm (iii)\ }}The permutations whose set of descents
is $E$ and whose number of inversions is congruent to $1$ modulo $n$.
\finth

In another vein, let us mention that Proposition~1.2 can also be applied
to Gaussian, or $q$-binomial, polynomials. We have established in [D1] the
following congruence: If $n=ka+r$ and $m=kb+s$ are the divisions with
rest of two integers $n$ and $m$ by $k$, then
$${n\brack m}\equiv {a\choose b}{r\brack s}\pmod{\Phi _k}.$$
When $k$ divides $n$, the polynomial $r\brack s$
is $0$ or $1$ according to whether $k$ does not divide or divides $m$.
In either case, the right-hand side of the congruence is an integer.
Now, using the combinatorial interpretations of Gaussian polynomials, due
to MacMahon, we obtain the following result analogous to Theorem~2.2 for
Mahonian statistics on words.

\th Proposition 3.5|The number of $n$-letter words containing $m$ times
the letter $0$ and $n-m$ times the letter $1$ and whose number of
inversions (or, equivalently, whose major index) is congruent to $k$
modulo $n$ depends only on the greatest common divisor $(k,n)$ and $m$
(but not on $k$).
\finth

\bigskip
\eightpoint

\leftline{\pc REFERENCES|}

\nobreak\bigskip

\article C|\pd COHEN (E.)|A class of arithmetical functions|%
  Proc. Natl. Acad. Sci. U.S.A.|41|1955|939--944|

\article D1|\pd D\'ESARM\'ENIEN (J.)|Un analogue des congruences
  de Kummer pour les $q$-nombres d'Euler|Europ. J. Combin.|3|1982|19--28|

\article D2|\pd D\'ESARM\'ENIEN (J.)|Fonctions sym\'etriques
  associ\'ees \`a des suites classiques de nombres|Ann. Scient.
  \smash{\'e}cole Normale Sup\'erieure|16|1983|271--304|

\article D--F1|\pd D\'ESARM\'ENIEN (J.) and \pd FOATA (D.)|Fonctions
  sym\'etriques et s\'eries hyperg\'eom\'etriques basiques
  multivari\'ees|Bull. Soc. Math. France|113|1985|3--22|

\divers D--F2|\pd D\'ESARM\'ENIEN (J.) and \pd FOATA (D.)|Fonctions
  sym\'etriques et s\'eries hyperg\'eom\'etriques basiques
  multivari\'ees~II, {\it Combinatoire \'enum\'erative}, [Labelle (G.)
  and Leroux (P.), eds.; Montr\'eal, 28~May--1~June~1985],
  p.~68--90\pointir Heidelberg, Springer-Verlag (Lecture Notes
  in Mathematics, vol.~1234), {\oldstyle 1987}|

\article D--F3|\pd D\'ESARM\'ENIEN (J.) and \pd FOATA (D.)|Statistiques d'ordre
  sur les permutations color\'ees|Discrete Mathematics|87|1991|133-148|

\article D--F4|\pd D\'ESARM\'ENIEN (J.) and \pd FOATA (D.)|The signed Eulerian
  numbers|Discrete Mathematics|99|1992|49-58|

\divers D--W|\pd D\'ESARM\'ENIEN (J.) and \pd WACHS (M.)|Descentes
sur les d\'erangements et mots circulaires, {\it S\'eminaire lotharingien
de combinatoire}, 19\emini~session, [Strehl (V.), ed.;
Schlo\ss\ Schwanberg/Ufr. 22--25~mars 1988], p.~13--21\pointir
Strasbourg, Publ. I.R.M.A. 361/S--19, {\oldstyle 1988}|

\article F--S|\pd FOATA (D.) and \pd SCH\"UTZENBERGER (M.)|Major
  index and inversion number of permutations|Math. Nachr.|%
  83|1978|143--159|

\livre H--W|\pd HARDY (G.M.) and \pd WRIGHT (E.M.)| An introduction
  to the theory of numbers (5\emini~ed.)|Oxford, Clarendon
  Press, {\oldstyle 1979}|

\divers K--W|\pd KRASKIEWICZ (W.) and \pd WEYMAN (J.)|Algebra of
  invariants and the action of a Coxeter element, preprint,
  Institute of Mathematics of the University of Copernic, Toru\'n,
  Poland|

\livre M|\pd MACDONALD (I.G.)|Symmetric functions and Hall
  polynomials|Oxford, Clarendon Press, {\oldstyle 1979}|

\article N--V|\pd NICOL (C.A.) and \pd VANDIVER (H.S.)|A Von
  Sterneck arithmetical function and restricted partitions
  with respect to a modulus|Proc. Natl. Acad. Sci. U.S.A.|%
  40|1954|825--835|

\divers R|\pd REUTENAUER (C.)|Number of permutations with
  given descent set and cycle stucture,
  {\it S\'eminaire lotharingien de combinatoire},
  Actes 21\emini~session,
  Strasbourg, Publ. I.R.M.A. 413/S--21, {\oldstyle 1990}|

\rightline{\strut \vrule width 3cm height .4pt depth 0pt}
\rightline{\it D\'epartement d'informatique,}
\rightline{\it Institut universitaire de
  technologie de l'Universit\'e Robert-Schuman,}
\rightline{\it 72, route du Rhin, 67400 Illkirch-Graffenstaden.}

\bye
