EINE KOMBINATORISCHE UNGLEICHUNG

Michael Drmota (Wien)

Abstract. Using the notion of s-discrepancy D_{s}(u) of a word u over a finite alphabet A = {a_{1}, …, a_{α}} (see [1,2]) the s-discrepancy of u = (a_{1} ⋯ a_{α})^{n} is explicitly calculated.

Sei A = {a_{1}, …, a_{α}}, α ≥ 2, ein endliches Alphabet und bezeichne A^{∗} die Menge aller endlichen Worte über A. Ein Wort v = v_{1} ⋯ v_{n} (v_{i} ∈ A) heißt Teilwort des Wortes u = u_{1} ⋯ u_{m} (u_{i} ∈ A), falls für jedes k (1 ≤ k ≤ n) ein j_{k} (j_{1} < ⋯ < j_{n}) mit v_{k} = u_{j_{k}} existiert. Weiters bezeichne (u; v) die Anzahl, wie oft v als Teilwort in u vorkommt und |v| die Länge des Wortes v. Damit kann die s-Diskrepanz eines Wortes u ∈ A^{∗} definiert werden:

D_{s}(u) = max_{|v|=s} |(u; v)\binom{|u|}{s}^{−1} − α^{−s}| (1 ≤ s ≤ |u|).

Es soll nun die s-Diskrepanz eines Wortes u = (a_{1} ⋯ a_{α})^{n} explizit berechnet werden. Der Spezialfall α = 2 wurde bereits in [1] behandelt. In [2] wird gezeigt, daß

((a_{1} ⋯ a_{α})^{n}; v) = \binom{n + d(v)}{s}

gilt, wobei d(v) die Anzahl der geschlossenen Zweierblöcke der Form a_{i}a_{i+k}, 1 ≤ i ≤ α, 1 ≤ k ≤ α − i, im Wort v ist. Daraus folgt

\binom{n}{s} ≤ ((a_{1} ⋯ a_{α})^{n}; v) ≤ \binom{n + s − 1 − [\frac{s−1}{α}]}{s},

wobei beide Extremfälle eintreten können. Kann man nun die Ungleichung

\binom{n + s − 1 − [\frac{s−1}{α}]}{s} + \binom{n}{s} ≥ 2\binom{αn}{s}α^{−s}  (1)

zeigen, erhält man für die s-Diskrepanz die explizite Formel:

SATZ.

D_{s} ((a_{1} ⋯ a_{α})^{n}) = \binom{n + s − 1 − [\frac{s−1}{α}]}{s}\binom{αn}{s}^{−1} − α^{−s}.  (2)

Typeset by AMS-TEX

Zum Beweis von (1) betrachte man zunächst den Fall n ≥ s. Schreibt man s − 1 in der Form s − 1 = αg + k, 0 ≤ k ≤ α − 1, dann ist (1) äquivalent zu

\begin{matrix}(n + αg + k − g) ⋯ (n + 1) + (n − g − 1) ⋯ (n − αg − k) \\ ≥ 2 (n − \frac{1}{α}) ⋯ (n − 1 + \frac{1}{α}) (n − 1 − \frac{1}{α}) ⋯ (n − g − \frac{k}{α}) , \end{matrix}  (3)

wenn die gemeinsamen Faktoren gekürzt werden. Mit dem für x ≥ 0 konvexen Polynom

f(x) = ∏_{j=1}^{(α−1)g+k} (n − g − j + x (j + \frac{g}{2}))

folgt aus der Jensenschen Ungleichung f(0) + f(2) ≥ 2f(1), das heißt

(n + αg + k − g) ⋯ (n + 1) + (n − g − 1) ⋯ (n − αg − k) ≥ 2 (n − \frac{g}{2})^{(α−1)g+k} . (4)

(3) folgt dann aus (4), aus

((α − 1)g + k) (n − \frac{g}{2}) ≥ (α − 1)g (n − \frac{g}{2}) + k (n − g − \frac{k + 1}{2α})

und aus der Ungleichung zwischem dem arithmetischen und geometrischen Mittel. Für den Fall n < s gilt (1) ebenfalls. Dies kann man mit der Ungleichung

∏_{i=1}^{j}(1 + x_{i}) ≥ 1 + ∑_{i=1}^{j} x_{i} (x_{i} ≥ 0)

und unmittelbarer Überprüfung des Falles s = 3 sofort nachweisen.

Literatur

[1] P. Kirschenhofer und R. F. Tichy, Gleichverteilung und Formale Sprachen, SB Österr. Akad. Wiss., Math.-naturw. Kl. II 189 (1980), 291–319.

[2] P. Kirschenhofer und R. F. Tichy, Gleichverteilte Folgen auf Diskreten Räumen, in: Séminaire Lotharingien de Combinatoire, 14^{éme} Session (V. Strehl ed.), Publication de l’I.R.M.A. Strasbourg (1986), 89–108.