ZUM q-ANALOGON DER KONGRUENZ VON LUCAS

Volker Strehl

Department of Computer Science (Informatik 8) Friedrich-Alexander-Universität Erlangen-Nürnberg D-91058 Erlangen, Germany

In seiner klassischen Untersuchung über die Kongruenzen für Euler–Zahlen verwendet LUCAS folgende, nach ihm benannte Kongruenz für die Binomialkoeffizienten:

\binom{ap + b}{cp + d} ≡ \binom{a}{b}\binom{b}{d} mod p

für natürliche Zahlen a, b, c, d mit 0 ≤ b, d < p und p prim.

In seiner Arbeit über sogenannte Kummersche Kongruenzen für die q-Ana-loga der Euler–Zahlen macht J. DÉSARMÉNIEN entscheidend Gebrauch von einem q-Analogon dieser LUCAS-Kongruenz:

[ \begin{matrix}ak + b \\ ck + d \end{matrix} ]_{q} ≡ \binom{a}{b} [ \begin{matrix}b \\ d \end{matrix} ]_{q} mod Φ_{k}(q) ,

wobei a, b, c, d, k natürliche Zehlen mit 0 ≤ b, d < k sind, und wo Φ_{k}(q) das k-te Kreisteilungspolynom und [ ]_{q} das q-Analogon der Binomialkoeffizienten bezeichnet. Der von Désarménien gegebene Beweis ist rein arithmetischer Natur, so daß 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 im-Fall b < d nur erfährt, daß ein Binomialkoeffizient ≡ 0 mod p ist; allgemeiner interessiert man sich jedoch für die Restklasse mod p^{e+1} eines Binomialkoeffizienten, wenn p^{e} die höchste Potenz von p ist, die diesen Binomialkoeffizienten teilt. Fragen dieser Art sind natürlich 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ür q-Multinomialkoeffizienten kann in einen solchen Ansatz natürlich gleich mit einbezogen werden.

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

A bezeichne ein endliches, totalgeordnetes Alphabet, etwa A = {1, 2, …, m} mit der üblichen Ordnung; A^{+} sei das freie Abelsche Monoid über A, Elemente von A^{+} werden geschrieben als Vektoren α = (α_{1}, α_{2}, …, α_{m}) mit α_{i} ∈ ℕ, ι : A^{+} → ℕ bezeichne den natürlichen Morphismus, das heißt ι(α_{1}, α_{2}, …, α_{m}) = α_{1} + α_{2} + ⋯ + α_{m}. A^{∗} bezeichne, wie üblich, das freie Monoid über A, dessen Elemente als Wörter über A geschrieben werden. τ : A^{∗} → A^{+} bezeichne den natürlichen Morphismus, für α ∈ A^{+} ist dann [α] := {a ∈ A : τa = α} die Menge aller Wörter (Multipermutationen) vom Typ α. Für a = a_{1}a_{2} … a_{n} ∈ A^{∗} sei

inv(a) := card{(i, j) : 1 ≤ i < j ≤ n, a_{i} > a_{j}}

die Anzahl der Inversionen von a; für α ∈ A^{+} stellt dann

[α]_{q} := ∑ {q^{inv(a)} : a ∈ [α]}

den zum Typ α = (α_{1}, α_{2}, …, α_{m}) gehörenden q-Multinomialkoeffizienten dar:

[α]_{q} = [ \begin{matrix}ια \\ α_{1}, α_{2}, …, α_{m} \end{matrix} ]_{q} .

Sei nun eine ganze Zahl k ≥ 1 fixiert. Für beliebige n ∈ ℕ seien Qn ∈ ℕ und Rn ∈ {0, 1, …, k − 1} mittels der üblichen Division mit Rest definiert: n = k · Qn + Rn. Dies gibt Anlaß zur Definition von zwei Abbildungen Q^{+} : A^{+} → A^{+} und R^{+} : A^{+} → A^{+} mit:

Q^{+}(α_{1}, α_{2}, …, α_{m}) := (Qα_{1}, Qα_{2}, …, Qα_{m})  und
R^{+}(α_{1}, α_{2}, …, α_{m}) := (Rα_{1}, Rα_{2}, …, Rα_{m}) .

Offensichtlich gilt dann für α ∈ A^{+}

k · (Q · ι − ι · Q^{+})α = (ι · R^{+} − R · ι)α

und

eα := (Q · ι − ι · Q^{+})α

ist eine nichtnegative ganze Zahl. Mit diesen Begriffen kann nun das Resultat formuliert werden.

Theorem. Für alle α ∈ A^{+} gilt:

(1)  [α]_{q} ≡ 0  mod (Φ_{k}(q))^{eα} ,
(2)  [α]_{q} ≡ \binom{Qια}{ιQ^{+}α}[Q^{+}α]_{1} [R^{+}α]_{q} mod (Φ_{k}(q))^{1+eα} .

Insbesondere erweist sich eα als der (exakte) Exponent von Φ_{k}(q) in [α]_{q}, so daß sich unter den Folgerungen, die aus diesem Theorem gezogen werden können, ganz präzise Informationen über die Zerlegung von [α]_{q} in irreduzible Faktoren (in ℤ[q]) befinden.

Für m = 2 beinhaltet (2) eine (im oben angedeuteten Sinne) verschärfte Version der q-LUCAS-Kongruenz von DÉSARMÉNIEN. Als weitere Folgerungen findet man beispielsweise Resultate von FRAY über die p-Bewertung von q-Binomialkoeffizienten für ganzzahliges q, sowie — natürlich — für q = 1 die klassischen Resultate über Primfaktorzerlegung und Kongruenzen für Binomial- und Multinomialkoeffizienten.

Abschließend sei betont, daß das Theorem, dessen arithmetische Konsequenzen natürlich keine großen Überraschungen beinhalten, und die man auch mit anderen Methoden herleiten kann, ein im Grunde rein kombinatorisches Resultat ist. Von arithmetischen Eigenschaften der Kreisteilungspolynome, die über die Definition und sich daran unmittelbar anschließende Folgerungen hinausgehen, wird kein Gebrauch gemacht.

Literatur

ANDREWS, The Theory of partitions, Addison–Wesley, 1976, Ch. 3.4. DÉSARMÉNIEN, Europ. J. Combin. 3 (1982), 19–28. FOATA, Proc. Amer. Math. Soc. 19 (1968), 236–240. FRAY, Duke Math. J. 34 (1967), 469–480. KNUTH, The Art of Computer Programming, vol. 3, Addison–Wesley, 1973, Ch. 5.1. LUCAS, Bull. Soc. Math. France 6 (1878), 49–54. SINGMASTER, J. London Math. Soc. (2) 8 (1974), 545–548.

Department of Computer Science (Informatik 8), Friedrich-Alexander-Uni-versität Erlangen-Nürnberg, D-91058 Erlangen, Germany