%This is the AmS-TeX file for an 3 page paper.

\input amstex.tex
\input amsppt.sty

\loadbold

\magnification1200
\hsize12cm
\vsize18.7cm

\nologo
\def\N{\Bbb N}
\def\inv{\operatorname{inv}}
\def\card{\operatorname{card}}

\topmatter 
\title Zum $q$-Analogon der Kongruenz von LUCAS
\endtitle 
\author Volker Strehl
\endauthor 
\affil 
Department of Computer Science (Informatik 8)\\
Friedrich-Alexander-Uni\-ver\-si\-t\"at Erlangen-N\"urnberg\\
D-91058 Erlangen, Germany
\endaffil
\address Department of Computer Science (Informatik 8),
Friedrich-Alexander-Uni\-ver\-si\-t\"at Erlangen-N\"urnberg,
D-91058 Erlangen, Germany
\endaddress
%\email \endemail
%\dedicatory \enddedicatory
%\date \enddate
%\thanks \endthanks
%\subjclass Primary ;
% Secondary 
%\endsubjclass
%\keywords \endkeywords
%\abstract 
%\endabstract
\endtopmatter
\document

In seiner klassischen Untersuchung \"uber die Kongruenzen f\"ur
Euler--Zahlen verwendet LUCAS folgende, nach ihm benannte Kongruenz
f\"ur die Binomialkoeffizienten:
$$\binom {ap+b}{cp+d}\equiv \binom ab\binom bd\mod p$$
f\"ur nat\"urliche Zahlen $a,b,c,d$ mit $0\le b,d<p$ und $p$ prim.

In seiner Arbeit \"uber sogenannte Kummersche Kongruenzen f\"ur die
$q$-Ana\-lo\-ga der Euler--Zahlen macht J.~D\'ESARM\'ENIEN entscheidend
Gebrauch von einem $q$-Analogon dieser LUCAS-Kongruenz:
$$\bmatrix {ak+b}\\{ck+d}\endbmatrix _q\equiv \binom ab
\bmatrix  b\\d\endbmatrix _q\mod \Phi_k(q)\ ,$$
wobei $a,b,c,d,k$ nat\"urliche Zehlen mit $0\le b,d<k$ sind, und wo
$\Phi_k(q)$ das $k$-te Kreisteilungspolynom und $\big[\ \big]_q$ das
$q$-Analogon der Binomialkoeffizienten bezeichnet. Der von 
D\'esarm\'enien gegebene Beweis ist rein arithmetischer Natur, so
da{\ss} sich angesichts der bekannten kombinatorischen
Interpretationen
der $q$-Binomialkoeffizienten (Inversionsstatistik beziehungsweise
major-index von MacMahon, siehe zum Beispiel ANDREWS, FOATA, KNUTH)
die Frage stellt, ob man diese Kongruenz mit (weitgehend)
kombinatorischen Mitteln beweisen kann.

Die Kongruenz von LUCAS ist insofern etwas unbefriedigend, als man
imFall $b<d$ nur erf\"ahrt, da{\ss} ein Binomialkoeffizient $\equiv0$
mod $p$ ist; allgemeiner interessiert man sich jedoch f\"ur die
Restklasse mod $p^{e+1}$ eines Binomialkoeffizienten, wenn $p^e$ die
h\"ochste Potenz von $p$ ist, die diesen Binomialkoeffizienten teilt.
Fragen dieser Art sind nat\"urlich in der Literatur schon untersucht
worden, zum Beispiel von SINGMASTER, und es liegt nahe, diese Art der
Fragestellung auf den Fall der $q$-Kongruenzen auszudehnen. Die
Verallgemeinerung f\"ur $q$-Multinomialkoeffizienten kann in einen
solchen Ansatz nat\"urlich gleich mit einbezogen werden.

\smallskip
Um nun das allgemeine Resultat der gesuchten Art vorzustellen, bedarf
es einiger Notation:

$A$ bezeichne ein endliches, totalgeordnetes Alphabet, etwa
$A=\{1,2,\dots,m\}$  mit der \"ublichen Ordnung; $A^+$ sei das freie
Abelsche Monoid \"uber $A$, Elemente von $A^+$ werden geschrieben als
Vektoren $\boldsymbol\alpha=(\alpha_1,\alpha_2,\dots,\alpha_m)$ mit $\alpha_i\in\N$,
$\iota:A^+\to \N$ bezeichne den nat\"urlichen Morphismus, das hei\ss t
$\iota(\alpha_1,\alpha_2,\dots,\alpha_m)=\alpha_1+\alpha_2+\dots+\alpha_m$. $A^*$
bezeichne, wie \"ublich, das freie Monoid \"uber $A$, dessen Elemente als
W\"orter \"uber $A$ geschrieben werden. $\tau:A^*\to A^+$ bezeichne
den nat\"urlichen Morphismus, f\"ur $\boldsymbol\alpha\in A^+$ ist dann
$[\boldsymbol\alpha]:=\{\bold a\in A:\tau\bold a=\boldsymbol\alpha\}$ die
Menge aller W\"orter (Multipermutationen) vom Typ $\boldsymbol\alpha$. F\"ur
$\bold a=a_1a_2\dots a_n\in A^*$ sei
$$\inv(\bold a):=\card\{(i,j):1\le i<j\le n,\, a_i>a_j\}$$
die Anzahl der Inversionen von $\bold a$; f\"ur $\boldsymbol\alpha\in A^+$
stellt dann
$$[\boldsymbol\alpha]_q:=\sum _{} ^{}\left\{q^{\inv(\bold a)}:\bold a\in
[\boldsymbol\alpha]\right\}$$
den zum Typ $\boldsymbol\alpha=(\alpha_1,\alpha_2,\dots,\alpha_m)$ geh\"orenden
$q$-Multinomialkoeffizienten dar:
$$[\boldsymbol\alpha]_q=\bmatrix \iota\boldsymbol\alpha\\
\alpha_1,\alpha_2,\dots,\alpha_m\endbmatrix_q\ .$$

Sei nun eine ganze Zahl $k\ge1$ fixiert. F\"ur beliebige $n\in\N$ seien
$Qn\in\N$ und $Rn\in\{0,1,\dots,k-1\}$ mittels der \"ublichen Division
mit Rest definiert: $n=k\cdot Qn+Rn$. Dies gibt Anla{\ss} zur
Definition von zwei Abbildungen $Q^+:A^+\to A^+$ und $R^+:A^+\to A^+$
mit:
$$\align Q^+(\alpha_1,\alpha_2,\dots,\alpha_m)&:=(Q\alpha_1,Q\alpha_2,\dots,Q\alpha_m)\quad \quad \text
{und}\\
R^+(\alpha_1,\alpha_2,\dots,\alpha_m)&:=(R\alpha_1,R\alpha_2,\dots,R\alpha_m)\ .
\endalign$$
Offensichtlich gilt dann f\"ur $\boldsymbol\alpha\in A^+$
$$k\cdot (Q\cdot \iota-\iota\cdot Q^+)\boldsymbol\alpha=
(\iota\cdot R^+-R\cdot\iota)\boldsymbol\alpha$$
und
$$e\boldsymbol\alpha:=(Q\cdot \iota-\iota\cdot Q^+)\boldsymbol\alpha$$
ist eine nichtnegative ganze Zahl. Mit diesen Begriffen kann nun das
Resultat formuliert werden.
\proclaim{Theorem} F\"ur alle $\boldsymbol\alpha\in A^+$ gilt:
$$\alignat 2
[\boldsymbol\alpha]_q&\equiv0&&\mod
(\Phi_k(q))^{e\boldsymbol\alpha}\ ,\tag1\\
[\boldsymbol\alpha]_q&\equiv \binom {Q\iota\boldsymbol\alpha}{\iota Q^+
\boldsymbol\alpha}[Q^+\boldsymbol\alpha]_1\,[R^+\boldsymbol\alpha]_q&&\mod
(\Phi_k(q))^{1+e\boldsymbol\alpha}\ .\tag2
\endalignat$$
\endproclaim

Insbesondere erweist sich $e\boldsymbol\alpha$ als der (exakte) Exponent
von $\Phi_k(q)$ in $[\boldsymbol\alpha]_q$, so da{\ss} sich unter den
Folgerungen, die aus diesem Theorem gezogen werden k\"onnen, ganz
pr\"azise Informationen \"uber die Zerlegung von $[\boldsymbol\alpha]_q$ in
irreduzible Faktoren (in $\Bbb Z[q]$) befinden.

F\"ur $m=2$ beinhaltet (2) eine (im oben angedeuteten Sinne)
versch\"arfte Version der $q$-LUCAS-Kongruenz von D\'ESARM\'ENIEN. Als
weitere Folgerungen findet man beispielsweise Resultate von FRAY \"uber
die $p$-Bewertung von $q$-Binomialkoeffizienten f\"ur ganzzahliges $q$,
sowie --- nat\"urlich --- f\"ur $q=1$ die klassischen Resultate \"uber
Primfaktorzerlegung und Kongruenzen f\"ur Bi\-no\-mi\-al- und
Multinomialkoeffizienten.

Abschlie\ss end sei betont, da{\ss} das Theorem, dessen arithmetische
Konsequenzen nat\"urlich keine gro\ss en \"Uberraschungen beinhalten, und
die man auch mit anderen Methoden herleiten kann, ein im Grunde rein
kombinatorisches Resultat ist. Von arithmetischen Eigenschaften der
Kreisteilungspolynome, die \"uber die Definition und sich daran
unmittelbar anschlie\ss ende Folgerungen hinausgehen, wird kein
Gebrauch gemacht.

\Refs\nofrills{Literatur}
\ref\by ANDREWS\book The Theory of partitions\publ Addison--Wesley\publaddr \yr
1976, Ch.~3.4\endref
\ref\by D\'ESARM\'ENIEN\jour Europ\. J. Combin\.
\vol 3\yr 1982\pages 19--28\endref
\ref\by FOATA\jour Proc\. Amer\. Math\. Soc\.
\vol 19\yr 1968\pages 236--240\endref
\ref\by FRAY\jour Duke Math\. J.
\vol 34\yr 1967\pages 469--480\endref
\ref\by KNUTH\book The Art of Computer Programming\publ vol.~3\publaddr
Addison--Wesley\yr 1973, Ch.~5.1\endref
\ref\by LUCAS\jour Bull\. Soc\. Math\. France
\vol 6\yr 1878\pages 49--54\endref
\ref\by SINGMASTER\jour J. London Math\. Soc\. (2)
\vol 8\yr 1974\pages 545--548\endref

\endRefs

\enddocument