A method for exact calculation of the discrepancy of low-dimensional finite point sets. I (Q1313455)

The discrepancy of a point sequence \((u_ k)\), \(1 \leq k \leq n\) in \([0,1)^ d\) is defined by \[ D_ n=\sup_ J \bigl| {1\over n} \text{ card} \{k:u_ k \in J\}-\text{vol} J \bigr|, \] where the supremum is extended over all axis parallel intervals \(J\). For \(d=1\) an explicit formula is due to \textit{H. Niederreiter} [Appl. Number Theory Numer. Anal., Proc. Symp. Univ. Montreal 1971, 203-236 (1972; Zbl 0248.10025)]: \[ D_ n={1 \over 2n}+\max_{1 \leq i \leq n} \left( u_ i- \left| {2i-1 \over 2n} \right| \right). \] In the present paper the authors obtain an interesting generalization for \(d=2,3\). The expression for \(D_ n\) is a three-fold maximum only containing terms of the sequence. In a subsequent paper a generalization to arbitrary dimensions will be obtained.