General discrepancy estimates. III: The Erdös-Turán-Koksma inequality for the Haar function system (Q1895154): Difference between revisions

[For Parts I, II see Acta. Arith. 67, 209-218 (1994; Zbl 0805.11055); and ibid., 313-322 (1994; Zbl 0813.11046).] The inequality of Erdös-Turán-Koksma is a central quantitative result in the theory of uniform distribution of sequences modulo one. It gives an upper bound of the discrepancy of a sequence \(\omega= (x_n )_{n\geq 0}\) in the \(s\)-dimensional unit cube \([0, 1[^s\) in terms of Weyl sums \[ S_N (\chi_{\mathbf k}, \omega):= {\textstyle {1\over N}} \sum_{n=0}^{N-1} \chi_{\mathbf k} (x_n), \qquad {\mathbf k}\neq \mathbf{0}, \] relative to some function system \({\mathcal F}= \{\chi_{\mathbf k}\}\) on \([0, 1[^s\). If we choose for \({\mathcal F}\) the system of trigonometric functions, we obtain the classical inequality of Erdös- Turán-Koksma [see \textit{L. Kuipers} and \textit{H. Niederreiter}, Uniform distribution of sequences, Wiley and Sons, New York (1974; Zbl 0281.10001), p. 112, 114, 116]. Niederreiter has proved important variants of the Erdös-Turán-Koksma inequality for finite rational point sets, as they appear in pseudorandom number generation and quasi-Monte Carlo integration. Due to Niederreiter's results, theoretical analysis of the serial test has been feasible for most types of uniform pseudorandom number generators (see the comprehensive monograph of \textit{H. Niederreiter} [Random number generation and quasi-Monte Carlo methods, SIAM (1992; Zbl 0761.65002)] and the recent surveys by \textit{J. Eichenauer-Herrmann} [Int. Stat. Rev. 60, 167-176 (1992; Zbl 0766.65002); and Z. Angew. Math. Mech. 73, T 644-- T 647 (1993; Zbl 0796.11029)] and \textit{H. Niederreiter} [New methods for pseudorandom number and pseudorandom vector generation, in Proc. 1992 Winter Simulation Conf., Arlington, Va., 1992, 264-269, IEEE Press, Piscataway, N.J. (1992)). In this paper we continue the study of general discrepancy estimates begun by the author in Parts I--II (loc. cit.). We prove the inequality of Erdös-Turán-Koksma for generalized Haar function systems, for the extreme and the star discrepancy of arbitrary sequences in \([0, 1[^s\). This extends results of Part I (loc. cit.). Further, we show the existence of the inequality of Erdös-Turán-Koksma for the isotropic discrepancy, for generalized Haar and Walsh function systems. In the appendix, we indicate how to extend our results to more general systems of numeration. Finally, we survey interesting related results.