%This is an AmS-TeX file
%producing a 2 pages paper


\input amstex
\documentstyle{amsppt}

\TagsOnRight
\NoBlackBoxes

\topmatter
\title
EINE KOMBINATORISCHE UNGLEICHUNG
\endtitle
\author
Michael Drmota (Wien)
\endauthor
\abstract
Using the notion of $s$-discrepancy $D_s(u)$ of a word $u$ over a
finite alphabet $A=\{a_1,\ldots,a_\alpha\}$ (see \cite{1,2}) 
the $s$-discrepancy of $u= (a_1\cdots a_\alpha)^n$ is explicitly
calculated.
\endabstract
\endtopmatter    

\document

Sei $A=\{a_1,\ldots,a_\alpha\}$, $\alpha\ge 2$, ein endliches
Alphabet und bezeichne $A^*$ die Menge aller endlichen Worte
\"uber $A$. Ein Wort $v = v_1\cdots v_n$ $(v_i\in A)$ hei\ss t
Teilwort des Wortes $u = u_1\cdots u_m$ $(u_i\in A)$, falls f\"ur
jedes $k$ $(1\le k\le n)$ ein $j_k$ $(j_1<\cdots < 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\"ange des Wortes 
$v$. Damit kann die $s$-Diskrepanz eines Wortes $u\in A^*$ definiert
werden:
$$
D_s(u) = \max_{|v|=s} \left| (u;v) {\binom{|u|}{s}}^{-1} - \alpha^{-s}
\right|\qquad (1\le s\le |u|).
$$
Es soll nun die $s$-Diskrepanz eines Wortes $u = (a_1\cdots a_\alpha)^n$
explizit berechnet werden. Der Spezialfall $\alpha = 2$ wurde bereits
in \cite{1} behandelt. In \cite{2} wird gezeigt, da\ss\ 
$$
\left( (a_1\cdots a_\alpha)^n;v\right) = \binom {n+d(v)}s
$$
gilt, wobei $d(v)$ die Anzahl der geschlossenen Zweierbl\"ocke der
Form $a_ia_{i+k}$, $1\le i\le \alpha$, $1\le k\le \alpha-i$, im Wort
$v$ ist. Daraus folgt
$$
\binom ns \le \left( (a_1\cdots a_\alpha)^n;v\right) \le
\binom {n+s-1-\left[\frac{s-1}{\alpha}\right]}s,
$$
wobei beide Extremf\"alle eintreten k\"onnen. Kann man nun die 
Ungleichung
$$
\binom {n+s-1-\left[\frac{s-1}{\alpha}\right]}s + \binom ns \ge
2 \binom {\alpha n}s \alpha^{-s} 
\tag 1
$$
zeigen, erh\"alt man f\"ur die $s$-Diskrepanz die explizite Formel:
\proclaim{SATZ}
$$
D_s\left( (a_1\cdots a_\alpha)^n\right) = 
\binom {n+s-1-\left[\frac{s-1}{\alpha}\right]}s
{\binom {\alpha n}s}^{-1}- \alpha^{-s}. 
\tag 2
$$
\endproclaim

Zum Beweis von (1) betrachte man zun\"achst den Fall $n\ge s$. Schreibt 
man $s-1$ in der Form $s-1 = \alpha g + k$, $0\le k\le \alpha-1$, dann 
ist (1) \"aquivalent zu
$$
\aligned
&(n+\alpha g+k-g)\cdots (n+1) + (n-g-1)\cdots (n-\alpha g -k) \\
&\quad \ge 2\left(n-\frac 1\alpha\right)\cdots \left(n-1+\frac 1\alpha\right)
\left(n-1-\frac 1\alpha\right)\cdots\left(n-g-\frac k\alpha\right),
\endaligned
\tag 3     
$$
wenn die gemeinsamen Faktoren gek\"urzt werden. Mit dem f\"ur $x\ge 0$
konvexen Polynom
$$
f(x) = \prod_{j=1}^{(\alpha-1)g+k} \left( n-g-j+x\left(j+\frac g2\right)
\right)
$$
folgt aus der Jensenschen Ungleichung $f(0)+f(2)\ge 2f(1)$, das hei\ss t
$$
(n+\alpha g+k-g)\cdots (n+1) + (n-g-1)\cdots (n-\alpha g -k) \ge
2\left( n-\frac g2\right)^{(\alpha-1)g+k}.
\tag 4
$$
(3) folgt dann aus (4), aus
$$
((\alpha-1)g+k)\left( n-\frac g2\right) \ge (\alpha-1)g\left( n-\frac g2\right)
+k\left( n-g-\frac {k+1}{2\alpha}\right)
$$
und aus der Ungleichung zwischem dem arithmetischen und geometrischen
Mittel.

F\"ur den Fall $n<s$ gilt (1) ebenfalls. Dies kann man mit der Ungleichung
$$
\prod_{i=1}^j (1+x_i) \ge 1 + \sum_{i=1}^j x_i\qquad (x_i\ge 0)
$$
und unmittelbarer \"Uberpr\"ufung des Falles $s=3$ sofort nachweisen.




\Refs\nofrills{Literatur}

\widestnumber\key{9}

\ref \key  1
\by P.\ Kirschenhofer und R.\ F.\ Tichy
\paper Gleichverteilung und Formale Sprachen
\jour SB \"Osterr.\ Akad.\ Wiss., Math.-naturw.\ Kl.\ II \vol 189
\yr 1980
\pages  291--319
\endref

\ref \key  2
\by P.\ Kirschenhofer und R.\ F.\ Tichy
\paper Gleichverteilte Folgen auf Diskreten R\"aumen
\jour in: S\'eminaire Lotharingien de Combinatoire, 14$^{\text{\'eme}}$
Session (V.\ Strehl ed.), Publication de l'I.R.M.A.\ Strasbourg
\yr 1986 \pages 89--108
\endref

\endRefs
\enddocument
