6. Primzahlbänder in den Binomialkoeffizienten, II

Wir betrachten nun allgemeine Binomialkoeffizienten der Form

$( \binom{n}{k} )$ = $( \binom{n}{n - k} )$ mit 0 < k < n.

Seien also n ≥ 1 und 0 < k < n. Aufgrund der Symmetrie der Binomialkoeffizienten nehmen wir an, dass k ≤ n/2. Wir übernehmen die Bezeichnungen des vorangehenden Essays und betrachten

a = n − k, b = n, I = ] a, b ] = ] n − k, n ], ℓ = k.

Sei d ≥ 1 beliebig. Wegen k ≤ n/2 gilt ℓ/a = k/a = k/(n − k) ≤ 1, sodass genau ein oder genau zwei Lösungsintervalle in V(d) = ] a/d, a/(d − 1) [ existieren . Für die s-Funktion (mit s = s_a,b = s_{n − k, n}) gilt nun:

Satz (Eigenschaften der s-Funktion)

Sei d ≥ 1. Dann sind äquivalent:

(1)	s(d + 1) − s(d) = 2.

(2)	Der Rest der Division von bd durch a ist gleich 0 oder größer als a − k.

(3)	Es gibt ein r  ∈  { a − k + 1, …, a } mit kd ≡ r mod(a).

(4)	Es gibt ein r  ∈  { a − k + 1, …, a } mit nd ≡ r mod(a).

Beweis

Wegen b/a ≤ 2 gilt

s(d + 1) − s(d) = ⌈bd/a + b/a⌉ − ⌈bd/a⌉  ∈  { 1, 2 }.

Weiter ist b/a = 1 + k/a, sodass

⌈bd/a + b/a⌉ − ⌈bd/a⌉ = 1 + ⌈bd/a + k/a⌉ − ⌈bd/a⌉.

Hieraus (und aus kd ≡ nd mod(a)) lassen sich die Äquivalenzen ablesen.

Die rechten Grenzpunkte lassen sich leicht identifizieren:

Satz (Charakterisierung der rechten Grenzen)

Sei c ≥ 1. Dann ist n/c genau dann eine rechte Intervallgrenze eines Lösungsintervalls, wenn c kein Vielfaches von n* = n/ggT(k,n) ist.

Beweis

Es gilt (n, k) = (n − k, k). Also ist der Quotient ac/b = (n − k)c/n genau dann ganzzahlig, wenn c ein Vielfaches von n* ist. Damit folgt die Behauptung aus dem allgemeinen Satz über die ausgelassenen rechten Grenzen.

Der folgende Satz versammelt Aussagen, mit denen wir überprüfen können, ob in V(d) ein oder zwei Lösungsintervalle existieren.

Satz (zwei Lösungsintervalle)

Sei d ≥ 1. Dann sind äquivalent:

(1)	Es gibt zwei Lösungsintervalle in V(d).

(2)	u_r < u₀, wobei u_r = ⌊k(d − 1)/a⌋ und u₀ = ⌈kd/a⌉ − 1.

(3)	kd hat bei Division durch a einen Rest in { 1, …, k − 1 }.

(4)	] k(d − 1)/a, kd/a [ enthält (genau) eine natürliche Zahl c ≥ 1.

(5)	Es gibt eine natürliche Zahl c ≥ 1 mit d = ⌈ac/k⌉ und d ≠ ac/k.

Beweis

Da höchstens zwei Lösungsintervalle existieren, gibt es nach unserer allgemeinen Analyse genau dann ein zweites Lösungsintervall wenn u_r < u₀. Äquivalent hierzu ist

r = ⌈kd/a⌉ − 1 − ⌊k(d − 1)/a⌋ = 1, d. h. ⌈kd/a⌉ − ⌊kd/a − k/a⌋ = 2.

Hieraus ergibt sich die Äquivalenz der ersten drei Aussagen. Aussage (4) ist eine Umformulierung von (2) (das Intervall hat eine Länge kleinergleich 1, sodass c im Fall der Existenz eindeutig ist). Eine algebraische Umformung zeigt die Äquivalenz von (4) und (5).

Gibt es in V(d) = ] a/d, a/(d − 1) [ ein zweites Lösungsintervall, so hat dieses die Form ] k/c, f(k/(c − 1)) ] mit c wie in (4). Es gilt

f (k/(c −1)) = ^b_{d + c − 1} = ⁿ_{c + ⌈ac/k⌉ − 1} = ⁿ_{⌈nc/k⌉ − 1} = ⁿ_{s_k,n(c)}.

Damit haben die zweiten Lösungsintervalle also die Form

I_c, k, n = ] k/c, n/s_k,n(c) ],

d. h., sie sind erste Lösungsintervalle für das Grundintervall ] k, n ] anstelle von ] n − k, n ]. Umgekehrt taucht jedes Intervall I_c, k, n als erstes oder zweites Lösungsintervall für I = ] n − k, n ] auf. Sei hierzu c ≥ 1. Ist k ein Teiler von ac, so sei d ≥ 1 derart, dass kd = ac. Dann gilt

s_a,n(d) = ⌈nd/a⌉ − 1 = ⌈nc/k⌉ − 1 = s_k,n(c),

I_d,a,n = ] a/d, b/s_a,n(d) ] = ] k/c, s_k,n(c) ]  = I_c,k,n.

In diesem Fall fällt also I_c,k,n mit einem nach (5) eindeutigen Lösungsintervall I_d,a,n zusammen. Ist andernfalls k kein Teiler von ca, so gibt es ein eindeutiges d derart, dass Aussage (4) erfüllt ist. In diesem Fall ist, wie wir gesehen haben, I_c,k,n das zweite Lösungsintervall in V(d). Die Eigenschaft „k ist ein Teiler von ac“ ist äquivalent zu „c ist ein Vielfaches von k*“, wobei k* = k/(k,n) = k/(a,n).

Damit haben wir gezeigt:

Satz (Indikatorfunktion der I-Intervalle)

Sei I = ⋃_c ≥ 1 I_c, k, n ∪ ⋃_d ≥ 1 I_{d, n−k, n}. Dann gilt

⌊n/x⌋ − ⌊(n − k)/x⌋ − ⌊k/x⌋ = ind_I(x) für alle x  ∈  ℝ.

Hieraus erhalten wir erneut eine genaue Beschreibung der Primfaktorzerlegung des zugehörigen Binomialkoeffizienten:

Korollar (Primzahlbänder von Binomialkoeffizienten)

Sei p prim. Dann gilt:

ex_p( $( \binom{n}{k} )$ ) = |{ e ≥ 1 | p^e  ∈  I }|.

Ist p² > n, so gilt:

(a)	Ist p  ∈  I, so kommt p in $( \binom{n}{k} )$ genau einmal vor.

(b)	Ist p  ∉  I, so kommt p in $( \binom{n}{k} )$ nicht vor.

Unsere Berechnung der rechten Grenzen liefert:

Satz (Teilbarkeitseigenschaft der Binomialkoeffizienten)

Seien n ≥ 1, 0 ≤ k ≤ n und n* = n/ggT(k,n). Dann ist n* ein Teiler von $( \binom{n}{k} )$ .

Beweis

Die Aussage ist klar für k = 0 oder k = n. Sei also 1 < k < n. Sei p prim, und seien ν, μ die p-Exponenten von n bzw. n*. Dann sind die Zahlen

c₁ = n/p^ν, …, c_μ = n/p^{ν − μ + 1}

keine Vielfachen von n*, da ihre p-Exponenten die Zahlen 0, …, μ − 1 durchlaufen. Folglich sind

p^ν = n/c₁, …, p^{ν − μ + 1} = n/c_μ

rechte Intervallgrenzen von I. Damit ist der p-Exponent von $( \binom{n}{k} )$ größergleich μ. Hieraus folgt die Behauptung.

Speziell gilt:

Korollar (Teilbarkeitseigenschaft der Binomialkoeffizienten b_m,n)

Seien n, m ≥ 1. Dann ist m ein Teiler von b_m,n.

Beweis

Es gilt nm/(mn,n) = nm/n = m.

Die folgenden Diagramme visualisieren die beiden Intervall-Folgen (I_c, k, n)_c ≥ 1 und (I_{d, n−k, n})_d ≥ 1 für n = 1400, k = 400, a = n − k = 1000.

Die I-Intervalle für n = 1400 und k = 400. Die Intervalle sind die Primzahlbänder von $( \binom{1400}{400} )$ .

Um die Periodizität dieses Beispiels einzusehen, berechnen wir die Reste der Vielfachen von k modulo a. Dies ergibt die periodische Folge

400, 800, 200, 600, 0, 400, 800, 200, 600, 0, 400, 800, 200, 600, 0, …

Ein Rest von dk modulo a in { 1, …, a − 1 } = { 1, …, 399 } führt zu zwei disjunkten Intervallen in V(s) = ] a/d, a/(d − 1) ]. Die Folge der Anzahl der Lösungsintervalle in V(d) lautet also

1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, …

Ist der Rest 0, so finden wir V(s) genau ein Lösungsintervall, das von beiden Intervall-Folgen angenommen wird. Ein Rest in { 601, …, 999 } ∪ { 0 } entspricht einem Sprung der s-Funktion, d. h. s(d + 1) − s(d) = 2. Die s-Folge lautet

1, 2, 4, 5, 6, 8, 9, 11, 12, 13, 15, 16, 18, 19, 20, …

Die Folge der (s(d + 1) − s(d))_d ≥ 1 der Differenzen ist

1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, …

Die Primfaktorzerlegung des Binomialkoeffizienten lautet (mit durch Abstände verdeutlichten Intervallbereichen ab 100):

2³ · 3 · 5 · 7² · 11² · 13² · 17 · 23 · 29 · 31 · 37 · 41 · 53 · 59 · 67 · 73 ·

101 · 103 · 107 · 113 · 127 · 137 · 139 · 149 · 151 ·

167 · 173 · 211 · 223 · 227 · 229 · 233 · 251 · 257 · 263 · 269 · 271 · 277 ·

337 · 347 · 349 · 401 · 409 · 419 · … · 457 · 461 · 463 ·

503 · 509 · 521 · … · 677 · 683 · 691 ·

1009 · 1013 · 1019 · … · 1373 · 1381 · 1399

Für die Primzahl 11 gilt 11  ∈  I, 11² = 121  ∉  I, 11³ = 1331  ∈  I.

Schließlich halten wir noch fest:

Satz (Struktur der I-Intervalle)

In obiger Situation seien g = ggT(k,n), k* = k/g, n* = n/g und c* = (n − k)/g. Dann gilt

I_{k*d, k, n} = I_{c*d, n − k, n} = ] g/d, n/(n*d − 1) ] für alle d ≥ 1.

Ist speziell k ein Teiler von n (d. h. g = k), so ist (I_d, k, n)_d ≥ 1 eine Teilfolge von (I_{d, n − k, n})_d ≥ 1 und genauer gilt

I_d, k, n = I_{(n/k − 1)d, n − k, n} = ] k/d, nk/(nd − k)] für alle d ≥ 1.

Beweis

Sei d ≥ 1. Dann gilt

^k_k*d = ^g_d = ^n − k_c*d,

s_k,n(k*d) = ⌈^n k* d_k⌉ − 1 = n*d − 1 = ⌈^n c* d_n − k⌉ − 1 = s_n−k,n(c*d).

Also ist I_{k*d, k, n} = I_{c*d, n−k, n}.

Insbesondere ist (I_d, n, mn)_d ≥ 1 eine Teilfolge von (I_{d, (m−1)n, n})_d ≥ 1. In den Binomialkoeffizienten b_m,n ist also eine zweite Intervall-Folge vorhanden, sie wird aber vollständig durch die erste Intervall-Folge überdeckt.

Untersuchung der Binomialkoeffizienten mit Hilfe der ψ-Funktion

Wir diskutieren noch einen anderen Zugang zur Berechnung der Primfaktorzerlegung der Binomialkoeffizienten. Ist x ≥ 1, so gilt

ψ(x) = ∑_n ≤ x Λ(n) = ∑_p^k ≤ x log(p).

Wenden wir die Exponentialfunktion an, so erhalten wir

e^ψ(x) = ∏_p^k ≤ x p.

Ist I = ] y, x ] ein reelles Intervall mit 1 ≤ y < x, so gilt

ψ(y) − ψ(x) = ∑_{p^k  ∈  I} log(p)

und damit

e^{ψ(y) − ψ(x)} = ∏_{p^k  ∈  I} p.

Damit haben wir Produkte gefunden, wie sie in unserer Analyse der Primzahlbänder der Binomialkoeffizienten auftauchen. Mit Hilfe der Chebychev-Identität können wir nun Binomialkoeffizienten (in logarithmischer Form) berechnen. Die Chebychev-Identität lautet

ψ(x) + ψ(x/2) + ψ(x/3) + … = ∑_n ≤ x log(n),

wobei die Summe auf der linken Seite abbricht, sobald x/n < 1 gilt. Substituieren wir x/2 für x, so erhalten wir

ψ(x/2) + ψ(x/4) + ψ(x/6) + … = ∑_n ≤ x/2 log(n).

Ziehen wir nun das Doppelte der zweiten Identität von der ersten ab, so ergibt sich die alternierende Summe

ψ(x) − ψ(x/2) + ψ(x/3) − ψ(x/4) ± … = ∑_n ≤ x log(n) − 2 ∑_n ≤ x/2 log(n).

Wir fassen nun die Stellen x, x/2, x/3, x/4, … paarweise zusammen und definieren entsprechende reelle Intervalle durch

I_d = ] x/(2d), x/(2d − 1)] für alle d ≥ 1.

Nun können wir die alternierende Summe in der folgenden Form schreiben:

∑_d ≥ 1 ∑_{p^k  ∈  I_d} log(p) = ∑_n ≤ x log(n) − 2 ∑_n ≤ x/2 log(n).

Die Anwendung der Exponentialfunktion liefert

∏_d ≥ 1 ∏_{p^k  ∈  I_d} p = ^⌊x⌋ !_{⌊x/2⌋! ⌊x/2⌋!}

Ist x eine gerade natürliche Zahl, so gilt also

∏_d ≥ 1 ∏_{p^k  ∈  I_d} p = $( \binom{x}{x / 2} )$ .

Damit haben wir erneut die Primzahlbänder der mittleren Binomialkoeffizienten ans Licht gebracht. Die Primzahlbänder eines allgemeinen Binomialkoeffizienten $( \binom{n}{k} )$ ergeben sich analog durch die Berechnung der Summe

∑_d ≥ 1 ψ(ⁿ_d) − ∑_d ≥ 1 ψ(^k_d) − ∑_d ≥ 1 ψ(^n − k_d).

Mit etwas Mühe lässt sich diese Summe in eine alternierende Summe mit monoton fallenden Stellen umschreiben. Diese Summe entspricht genau der Intervall-Produktdarstellung des Binomialkoeffizienten $( \binom{n}{k} )$ . Da wir die Primzahlbänder der Binomialkoeffizienten bereits im Detail untersucht haben, begnügen wir uns an dieser Stelle mit einem einfachen Beispiel.

Beispiel

Für einen Binomialkoeffizienten der Form $( \binom{3 n}{2 n} )$ gilt

∑_d ≥ 1 ψ(³ⁿ_d) − ∑_d ≥ 1 ψ(²ⁿ_d) − ∑_d ≥ 1 ψ(ⁿ_d)

= ψ(3n) + ψ(3n/2) + ψ(3n/4) + ψ(3n/5) + ψ(3n/7) + ψ(3n/8) + …

− ψ(2n) − ψ(2n/2) − ψ(2n/3) − …

= ψ(3n) − ψ(2n) + ψ(3n/2) − ψ(2n/2) + ψ(3n/4) − ψ(2n/3) ± …

Im ersten Schritt verwenden wir, dass die dritte Summe eine Teilsumme der ersten ist. Anschließend fügen wir die zweite Summe alternierend ein. Die alternierende Summe entspricht nun genau unserem früheren Ergebnis (mit a = 2n und b = 3n): Als linke Intervallgrenzen tauchen alle Glieder der Folge (a/d)_d ≥ 1 auf, als rechte Intervallgrenzen alle Glieder der Folge (b/s(d))_d ≥ 1. Die s-Funktion springt alle drei Schritte um 1. Es gilt

(s(d))_d ≥ 1 = (1, 2, 4, 5, 7, 8, …).

Anhang: Ein direkter Beweis für den Wertebereich der s-Folgen

Wir zeigen ohne Rückgriff auf die allgemeine Analyse:

Satz (Wertebereich der s-Folgen)

rng(s_k,n) ∪ rng(s_{n − k,n}) = { c ≥ 1 | c ist kein Vielfaches von n* }.

Beweis

zu ⊆: Sei k* = k/(k, n), sodass k* n = k n*. Sei q  ∈  ℕ mit q ≥ 1. Wegen k/n < 1 gibt es kein natürliches d ≥ 1 mit

q k* < d ≤ q k* + k/n.

Folglich gibt es kein solches d mit

q n* k < nd ≤ q n* k + k.

Also gibt es kein d mit ⌈nd/k⌉ = qn* + 1. Dies zeigt, dass die Vielfachen von n* nicht im Wertebereich von s_k,n liegen. Analog liegen sie nicht im Wertebereich von s_a,n = s_{n − k,n} (da (k, n) = (a, n)).

zu ⊇: Sei nun c ≥ 1 mit c  ∉  rng(s), s = s_a,n. Dann gibt es ein d ≥ 1 mit s(d) = c − 1, s(d + 1) = c + 1 und ein r  ∈  { a − k, …, a }, sodass

c − 1 < ^nd_a ≤ c, c = ^nd_a + ^a − r_a.

Wir nehmen nun an, dass c kein Vielfaches von n* ist. Dann ist a kein Teiler von nd (denn sonst ist c = nd/a = n*d/a* mit a* = a/(k,n) = a/(a, n); da n* und a* teilerfremd sind, ist a* ein Teiler von d und damit c ein Vielfaches von n*, Widerspruch). Damit ist r ≠ a.

Wir setzen nun e = ⌈dk/a⌉ und zeigen, dass s_k,n(e) = c. Wir zeigen hierzu:

(+) c < ⌈^dk_a⌉ ⁿ_k ≤ c + 1.

Wegen dk ≡ dn mod(a) gilt ⌈dk/a⌉ = dk/a + (a − r)/a. Also ist

⌈^dk_a⌉ ⁿ_k = ^nd_a + ^a − r_aⁿ_k > c (da r ≠ 0 und n/k > 1).

Wegen r ≥ a − k und a − r ≤ k und somit

^a − r_aⁿ_k = ^a − r_a (1 + ^a_k) = ^a − r_a + ^a − r_k ≤ ^a − r_a + 1.

Folglich ist

⌈^dk_a⌉ ⁿ_k = ^nd_a + ^a − r_aⁿ_k ≤ ^nd_a + ^a − r_a + 1 = c + 1.

Satz (Eigenschaften der s-Funktion)

Beweis

Satz (Charakterisierung der rechten Grenzen)

Beweis

Satz (zwei Lösungsintervalle)

Beweis

Satz (Indikatorfunktion der I-Intervalle)

Korollar (Primzahlbänder von Binomialkoeffizienten)

Satz (Teilbarkeitseigenschaft der Binomialkoeffizienten)

Beweis

Korollar (Teilbarkeitseigenschaft der Binomialkoeffizienten bm,n)

Beweis

Satz (Struktur der I-Intervalle)

Beweis

Untersuchung der Binomialkoeffizienten mit Hilfe der ψ-Funktion

Beispiel

Anhang: Ein direkter Beweis für den Wertebereich der s-Folgen

Satz (Wertebereich der s-Folgen)

Beweis

Korollar (Teilbarkeitseigenschaft der Binomialkoeffizienten b_m,n)