Zur Diskrepanz von 0,1-Folgen. (Discrepancy of 0,1-sequences) (Q1061165)

Let \(\mu\) be a probability measure on the finite set A and let \(\omega =(x_ n)\) be a sequence of elements of A. For integers \(s\geq 1\) and \(N\geq 1\) define the discrepancy \[ D_ N^{(s)}(\omega)=\max_{u\in A^ s}| \left( \begin{matrix} N\\ s\end{matrix} \right)^{-1}(\omega_ N;u)-\mu (u)|, \] where for \(u=(u_ 1,...,u_ s)\in A^ s\) we set \(\mu (u)=\mu (u_ 1)...\mu (u_ s)\) and \[ (\omega_ N;u)=\sum_{1\leq i_ 1<...<i_ s\leq N}\chi_{u_ 1}(x_{i_ 1})... \chi_{u_ s}(x_{i_ s}) \] with \(\chi_ a\) the characteristic function of \(\{\) \(a\}\). In the case \(card(A)=2\) it is shown that \[ \sup_{\mu}\inf_{\omega}\overline{\lim}_{N\to \infty}N D_ N^{(s)}(\omega)=s/2. \] Analogous results for \(s=1\) and card(A) arbitrary are due to \textit{H. G. Meijer} [Indagationes Math. 35, 9-17 (1973; Zbl 0249.10024)], \textit{H. G. Meijer} and the reviewer [Compos. Math. 25, 153-160 (1972; Zbl 0239.10020)], and \textit{R. Tijdeman} [J. Comb. Theory, Ser. A 15, 129-137 (1973; Zbl 0261.05001)]. If \(card(A)=2\) and \(\mu\) is the equiprobability measure on A, then the authors prove that \[ \inf_{\omega}\overline{\lim}_{N\to \infty}N D_ N^{(s)}(\omega)=s(s+1)/2^{s+1}. \] In this case the value of \(\inf_{\omega} N D_ N^{(2)}(\omega)\) for any fixed N is also determined. The proofs use clever combinatorial arguments. A list of open problems concludes the paper.