On the lower bound of the discrepancy of (t,s)-sequences: II

Abstract

Let \((x(n))_{n \geq 1}\) be an \(s\)-dimensional Niederreiter-Xing sequence in base \(b\). Let \(D((x(n))_{n=1}^N)\) be the discrepancy of the sequence \((x(n))_{n=1}^N\). It is known that \(ND((x(n))_{n=1}^N) = O(\ln^s N)\) as \(N \to \infty\). In this paper, we prove that this estimate is exact. Namely, there exists a constant \(K > 0\), such that
\[
\inf_{w \in [0,1]^s} \sup_{1 \leq N \leq b^m} ND((x(n) \oplus w)_{n=1}^N) \geq K \ln^s \quad \text{ for } m = 1, 2, \ldots.
\]

We also get similar results for other explicit constructions of \((t,s)\)-sequences.

Keywords: low discrepancy sequences, \((t,s)\)-sequences, \((t,m,s)\)-nets.