Monatsh Math (2010) 161:193–222 DOI 10.1007/s00605-009-0150-y

Further discrepancy bounds and an Erdös–Turán–Koksma inequality for hybrid sequences Harald Niederreiter

Received: 3 February 2009 / Accepted: 25 August 2009 / Published online: 19 September 2009 © Springer-Verlag 2009

Abstract We consider hybrid sequences, that is, sequences in a multidimensional unit cube that are composed from lower-dimensional sequences of two different types. We establish nontrivial deterministic discrepancy bounds for five kinds of hybrid sequences as well as a new version of the Erdös–Turán–Koksma inequality which is suitable for hybrid sequences. Keywords Discrepancy · Hybrid sequence · Halton sequence · Kronecker sequence · Nonlinear congruential sequence · Inversive sequence · Quasi-Monte Carlo method Mathematics Subject Classification (2000) Secondary 65C05 · 65C10 · 65D30

Primary 11K38 · 11K45 · 11L07;

1 Introduction This paper continues the work initiated in [23] on deterministic discrepancy bounds for hybrid sequences. The motivation for this work, which is delineated in detail in [23], stems from applications of the theory of uniform distribution modulo 1 to Monte Carlo methods and quasi-Monte Carlo methods for multidimensional numerical integration. We mention here only the essential idea, first proposed by Spanier [30], of combining the advantages of Monte Carlo methods and quasi-Monte Carlo

Communicated by J. Schoissengeier. H. Niederreiter (B) RICAM, Austrian Academy of Sciences, Altenbergerstr. 69, 4040 Linz, Austria e-mail: [email protected]; [email protected] H. Niederreiter Department of Mathematics, University of Salzburg, Hellbrunnerstr. 34, 5020 Salzburg, Austria

123

194

H. Niederreiter

methods by using hybrid sequences. By a hybrid sequence we mean a sequence of points in a (usually high-dimensional) unit cube that is obtained by “mixing” a lowdiscrepancy sequence and a sequence of pseudorandom numbers (or vectors), in the sense that certain coordinates of the points stem from the low-discrepancy sequence and the remaining coordinates stem from the sequence of pseudorandom numbers (or vectors). A crucial issue in this context is that of obtaining discrepancy bounds for hybrid sequences. Prior to [23], only probabilistic results on the discrepancy of hybrid sequences were available (see [26,27]). A refinement of the result in [27] was recently shown in [7]. Nontrivial deterministic discrepancy bounds for five kinds of hybrid sequences were proved in [23]. In the present paper, we establish further deterministic discrepancy bounds for various hybrid sequences of practical interest. The sequences that we “mix” together are familiar in the area and their definitions are recalled in Sect. 2. A new version of the classical Erdös–Turán–Koksma inequality which is very convenient for certain types of hybrid sequences is shown in Sect. 3. The following five sections present discrepancy bounds for five more kinds of hybrid sequences. 2 Definitions For an arbitrary dimension m ≥ 1, let [0, 1)m be the m-dimensional half-open unit cube. We write c J for the characteristic function of a subinterval J of [0, 1)m . Given L points x0 , x1 , . . . , x L−1 ∈ [0, 1)m , we put A(J ; L) :=

L−1 

c J (xn ).

(1)

n=0

The discrepancy D L of these points is defined by    A(J ; L)   − λm (J ) , D L = sup  L J

(2)

where the supremum is extended over all half-open subintervals J of [0, 1)m and λm denotes the m-dimensional Lebesgue measure. Note that we always have L D L ≥ 1 (see [12, p. 93]) and D L ≤ 1. The star discrepancy D ∗L of x0 , x1 , . . . , x L−1 is obtained by letting the supremum in (2) run only over the half-open intervals J ⊆ [0, 1)m with one vertex at the origin. According to [20, Proposition 2.4] we have D L ≤ 2m D ∗L .

(3)

We now recall the definitions of the specific sequences which form the basic constituents of our hybrid sequences. These basic sequences fall into two categories: (i) low-discrepancy sequences; (ii) sequences of pseudorandom numbers. For (i) we use Halton sequences and Kronecker sequences, whereas for (ii) we use nonlinear

123

Further discrepancy bounds and an Erdös–Turán–Koksma inequality

195

congruential sequences, explicit inversive congruential sequences, and digital inversive sequences. We start with the Halton sequences (see [8], [20, Chapter 3]). Given an integer b ≥ 2, we write Zb := {0, 1, . . . , b − 1} for the least residue system modulo b. For an integer n ≥ 0, let n=

∞ 

al (n)bl

l=0

be the digit expansion of n in base b, where al (n) ∈ Zb for all l ≥ 0 and al (n) = 0 for all sufficiently large l. Then we define the radical-inverse function φb in base b by φb (n) =

∞ 

al (n)b−l−1 .

l=0

For a given dimension s ≥ 1, let b1 , . . . , bs be pairwise coprime integers ≥ 2. Then the Halton sequence (in the bases b1 , . . . , bs ) is given by xn = (φb1 (n), . . . , φbs (n)) ∈ [0, 1)s , n = 0, 1, . . . . It is a classical low-discrepancy sequence. Our second family of sequences is that of Kronecker sequences. Let s ≥ 1 be a given dimension and let α ∈ Rs . Then we consider the sequence ({nα}), n = 0, 1, . . . , of fractional parts. If α = (α1 , . . . , αs ), then this sequence is uniformly distributed if and only if 1, α1 , . . . , αs are linearly independent over Q (see [3, Theorem 1.76]). If α is badly approximable in the sense of diophantine approximations, then this sequence has a small discrepancy (see, e.g., [12, p. 132, Exercise 3.17]). Let p ≥ 3 be a prime which in practice will be large. We identify the finite field F p of order p with the set Z p = {0, 1, . . . , p − 1}. Choose a polynomial g ∈ F p [X ] with 2 ≤ deg(g) < p. Then we put yn := g(n) ∈ F p for n = 0, 1, . . . , p − 1. By extending with period p, we get a sequence y0 , y1 , . . . of elements of F p which is called a nonlinear congruential generator. It is obvious that this sequence has least period p. The nonlinear congruential sequence that we want to consider is the normalized sequence (yn / p), n = 0, 1, . . ., of numbers in [0, 1). Because of its periodicity, it is meaningful to study only the first N ≤ p terms of this sequence. For basic results on nonlinear congruential sequences, we refer to [4,19], and [20, Section 8.1]. Let p ≥ 5 be a prime which again will be large in practice. As above, we identify F p with Z p . For f ∈ F p we define f := f −1 ∈ F p (i.e., the multiplicative inverse of f modulo p) if f = 0 and f := 0 ∈ F p if f = 0. Now we choose a, d ∈ F p with a = 0 and we put

123

196

H. Niederreiter

en := an + d ∈ F p for n = 0, 1, . . . , p − 1. By extending with period p, we get a sequence e0 , e1 , . . . of elements of F p which is called an explicit inversive congruential generator. It is obvious that this sequence has least period p. The explicit inversive congruential sequence that we want to consider is the normalized sequence (en / p), n = 0, 1, . . ., of numbers in [0, 1). Because of its periodicity, it is meaningful to study only the first N ≤ p terms of this sequence. Explicit inversive congruential sequences were introduced by EichenauerHerrmann [5] and further studied in [21]; see also [22, Section 3.3] for a survey of results on these sequences. Our last family of sequences is obtained by the digital inversive method in the sense of Niederreiter and Rivat [25, Section 4]. Let p be a prime (which can be small in this case, e.g., p = 2 is a common choice) and let k ≥ 2 be an integer. Let Fq be the finite field of order q = p k . Fix α, δ ∈ Fq∗ and define the sequence R0 , R1 , . . . of rational functions over Fq by R0 (X ) = X,

Rn (X ) = Rn−1 (α X −1 + δ) for n = 1, 2, . . . .

The sequence R0 , R1 , . . . is purely periodic with least period T ≤ q + 1. For 1 ≤ n ≤ T − 1, each Rn has a unique pole εn ∈ Fq . Now choose γ0 ∈ Fq with γ02 = δγ0 + α. Then for 1 ≤ n ≤ T − 1 we put  γn :=

Rn (γ0 ) if γ0 = εn , δ − εn if γ0 = εn .

By extending with period T , we get a sequence γ0 , γ1 , . . . of elements of Fq which is called an inversive generator. This sequence has least period T according to [25, Lemma 2]. A simple sufficient condition for obtaining the maximum period T = q + 1 is given in [25, Theorem 1], and for any q there are always choices of α, δ ∈ Fq∗ such that this maximum period is attained (see [25, p. 255]). Now let {β1 , . . . , βk } be an ordered basis of Fq over F p . For n = 0, 1, . . ., we can write γn =

k 

cn,l βl

(4)

l=1

with all cn,l ∈ F p being unique. Then a digital inversive sequence is defined by zn =

k 

cn,l p −l ∈ [0, 1) for n = 0, 1, . . . .

(5)

l=1

The sequence z 0 , z 1 , . . . has least period T . Because of its periodicity, it is meaningful to study only the first N ≤ T terms of this sequence.

123

Further discrepancy bounds and an Erdös–Turán–Koksma inequality

197

3 An Erdös–Turán–Koksma inequality for hybrid sequences The Erdös–Turán–Koksma inequality is a fundamental tool for bounding the discrepancy of point sets in a unit cube in terms of exponential sums. The one-dimensional Erdös–Turán–Koksma inequality, also called the Erdös–Turán inequality, was shown by Erdös and Turán [6]. The constants in the Erdös–Turán inequality were improved by Niederreiter and Philipp [24], and their method applies also to all distribution functions satisfying a Lipschitz condition and not just to the uniform distribution. Vaaler [32, Section 8] devised a new approach to the Erdös–Turán inequality which yields even smaller constants; see also Montgomery [15, Section 1.2], Mauduit et al. [14, Lemma 1], and Rivat and Tenenbaum [28]. Lower bounds on the constants in the Erdös–Turán inequality were discussed by Niederreiter and Philipp [24, p. 640], Kuipers and Niederreiter [12, p. 117, Exercises 2.11 and 2.12], and Rivat and Tenenbaum [28]. The multidimensional Erdös–Turán–Koksma inequality was shown independently by Koksma [11] and Szüsz [31]. Niederreiter and Philipp [24] established a more general version for a wider family of distribution functions. The approach of Vaaler [32] was extended to the multidimensional case by Cochrane [2]. Let m ≥ 1 again be an arbitrary dimension. The following two functions on Zm will be used frequently. Definition 1 For any h = (h 1 , . . . , h m ) ∈ Zm , put m      M(h) = max h j  , r (h) = max(h j , 1). 1≤ j≤m

j=1

Now we recall the Erdös–Turán–Koksma inequality in its classical form (compare with [3, Theorem 1.21] and [12, p. 116]). In the following, we use · to denote the standard inner product in Rm . We write e(u) = e2πiu for u ∈ R. We also use the convention that the parameters on which the implied constant in a Landau symbol O depends are written in the subscript of O. A symbol O without a subscript indicates an absolute implied constant. Lemma 1 Let x0 , x1 , . . . , x L−1 be arbitrary points in [0, 1)m and let D L be their discrepancy. Then for any integer H ≥ 1 we have ⎛ ⎜1 1 D L = Om ⎜ ⎝H + L

 h∈Zm 0
⎞  L−1   ⎟   . r (h)−1  e(h · xn )⎟  ⎠ n=0

For point sets obtained by digital constructions (such as the digital inversive method described in Sect. 2 and many others), there are Erdös–Turán–Koksma inequalities involving exponential sums that depend explicitly on the digits of the coordinates of the points. Such an inequality was first proved in the one-dimensional case by Niederreiter [17]. A general multidimensional version which allows for different bases

123

198

H. Niederreiter

in different coordinates was shown in [18, Satz 2]. A special case of this inequality is given in [20, Theorem 3.12]. An approach to these inequalities in terms of Walsh functions is due to Hellekalek [9]; see also Hellekalek [10] for an Erdös–Turán–Koksma inequality in terms of Haar functions. We now establish a new version of the Erdös–Turán–Koksma inequality which can be viewed as a “hybrid” of the classical Erdös–Turán–Koksma inequality in Lemma 1 and of [20, Theorem 3.12]. This new inequality is a suitable tool for estimating the discrepancy of certain types of hybrid sequences (see Sect. 8). Before we can prove this result, we need further preparations. Let b ≥ 2 be an integer. Besides Zb , we use another complete residue system modulo b given by C(b) := (−b/2, b/2] ∩ Z. Fix also an integer k ≥ 1. For (h 1 , . . . , h k ) ∈ C(b)k , we put  Q b (h 1 , . . . , h k ) :=

if (h 1 , . . . , h k ) = 0,

1

b−d csc(π |h d | /b) if (h 1 , . . . , h k ) = 0,

(6)

where d = d(h 1 , . . . , h k ) is the largest l with h l = 0. Given a further integer m ≥ 1, we write C(b)m×k for the set of m × k matrices with entries from C(b). For H = (h j,l ) ∈ C(b)m×k , we define Wb (H) :=

m 

Q b (h j,1 , . . . , h j,k ).

(7)

j=1

We introduce also the following somewhat unusual

notation. Let but convenient H = (h j,l ) be an m × k matrix over Z and let z = z (1) , . . . , z (m) ∈ [0, 1)m be a point for which each coordinate is a rational number with denominator bk . For each j = 1, . . . , m, we have a unique representation z ( j) =

k 

( j) −l

wl

b

( j)

with all wl

∈ Zb .

l=1

Then we define H ⊗ z :=

m  k 

( j)

h j,l wl .

(8)

j=1 l=1

This operation depends of course on the base b, but for the sake of simplicity we suppress this dependence in the notation. The value of b will always be clear from the context. The following auxiliary result on trigonometric approximation is crucial.

123

Further discrepancy bounds and an Erdös–Turán–Koksma inequality

199

Lemma 2 Let I be a subinterval of [0, 1) and let c I be its characteristic function. Then for every integer H ≥ 1 there exists a trigonometric polynomial f I (x) =

H 

ψ I (h)e(hx),

(9)

h=−H

with complex coefficients ψ I (h) satisfying ψ I (0) = λ1 (I ) and |ψ I (h)| < |h|−1 for h = 0, such that |c I (x) − f I (x)| ≤

H  1 ω I (h)e(hx) for 0 ≤ x < 1, H +1

(10)

h=−H

where the complex coefficients ω I (h) satisfy |ω I (h)| ≤ 1 for all h and ω I (0) = 1. Proof This can be extracted from the work of Vaaler [32] and also from its exposition in Drmota and Tichy [3, Section 1.2.2]. Indeed, in the notation of [3, Section 1.2.2] we have ψ I (h) = cˆ I (h) JˆH +1 (h) (note that χ I there is the same as our c I ), and so ψ I (0) = λ1 (I ) follows immediately. (We have corrected an obvious misprint in [3, p. 22, line 1] where in its third occurrence x j needs to be replaced by h.) Furthermore, by the inequalities at the end of the proof of [3, Corollary 1.26] we get |ψ I (h)| < |h|−1 for h = 0. Next, by the first displayed inequality in the proof of [3, Corollary 1.26] we have (10) with ω I (h) = Kˆ H +1 (h)C h , where Kˆ H +1 (h) = 1 − |h| /(H + 1) and |C h | ≤ 1 for all h. This yields |ω I (h)| ≤ 1 for all h, and C0 = 1 implies that  ω I (0) = 1. Remark 1 The coefficients ψ I (h) and ω I (h) in (9) and (10), respectively, depend also on H , but we think of H as being fixed and for simplicity suppress the dependence on H in the notation. Now we are ready to state and prove the new version of the Erdös–Turán–Koksma inequality. For integers s ≥ 1 and t ≥ 1, we consider points x0 , x1 , . . . , x N −1 ∈ [0, 1)s+t which we write in the form xn = (yn , zn ) with yn ∈ [0, 1)s and zn ∈ [0, 1)t for 0 ≤ n ≤ N − 1. The points y0 , y1 , . . . , y N −1 are arbitrary. The points z0 , z1 , . . . , z N −1 are such that all their coordinates are rational numbers with denominator bk , where b ≥ 2 and k ≥ 1 are fixed integers. Theorem 1 Let b ≥ 2, k ≥ 1, s ≥ 1, and t ≥ 1 be integers. Let the points xn = (yn , zn ) ∈ [0, 1)s+t , n = 0, 1, . . . , N − 1, be as above and let D N be their discrepancy. Then for any integer H ≥ 1 we have ⎞ ⎛   N −1   ⎟ ∗ ⎜1 1 Wb (H)   1 1 ⎟ + H ⊗ z + e h · y + D N = Os,t ⎜ ⎠ ,  n n ⎝ bk   H N s r (h) b t×k h∈Z , H∈C(b)

n=0

M(h)≤H

where M(h) and r (h) are as in Definition 1 and Wb (H) is given by (6) and (7). The asterisk signifies that the pair (h, H) = (0, 0) is omitted from the range of summation.

123

200

H. Niederreiter

Proof We fix the integer H ≥ 1 throughout the proof. We use the standard convention that empty sums have the value 0 and empty products have the value 1. We first consider an interval J ⊆ [0, 1)s+t of the form J=

s+t 

Ii ,

(11)

i=1

where Ii is an arbitrary half-open subinterval of [0, 1) for 1 ≤ i ≤ s and where  v  i Ii = 0, k for s + 1 ≤ i ≤ s + t, b

(12)

with vi ∈ Z and 1 ≤ vi ≤ bk for s + 1 ≤ i ≤ s + t. We abbreviate the characteristic function c Ii of Ii by ci (1 ≤ i ≤ s +t) and the corresponding trigonometric polynomial f Ii in Lemma 2 by f i (1 ≤ i ≤ s). For 0 ≤ n ≤ N − 1, we write yn = (yn(1) , . . . , yn(s) ) ∈ [0, 1)s , zn = (z n(1) , . . . , z n(t) ) ∈ [0, 1)t . Then A(J ; N ) − N λs+t (J ) =

N −1 

c J (xn ) − N λs+t (J )

n=0

=

N −1 

c1 (yn(1) ) · · · cs (yn(s) )cs+1 (z n(1) ) · · · cs+t (z n(t) ) − N λs+t (J )

n=0

=

N −1  

 c1 (yn(1) ) · · · cs (yn(s) ) − f 1 (yn(1) ) · · · f s (yn(s) ) cs+1 (z n(1) ) · · · cs+t (z n(t) )

n=0

+

N −1  

f 1 (yn(1) ) · · · f s (yn(s) )cs+1 (z n(1) ) · · · cs+t (z n(t) ) − λs+t (J )



n=0

=: 1 + 2 .

For the first sum 1 , we have | 1 | ≤

N −1  

   c1 (yn(1) ) · · · cs (yn(s) ) − f 1 (yn(1) ) · · · f s (yn(s) ) .

(13)

n=0

The following inequality is shown by straightforward induction on s: if a1 , . . . , as , b1 , . . . , bs ∈ C with |bi | ≤ 1 for 1 ≤ i ≤ s, then |b1 · · · bs − a1 · · · as | ≤

s  i=1

123

(1 + |bi − ai |) − 1.

Further discrepancy bounds and an Erdös–Turán–Koksma inequality

201

By applying this inequality to (13), we obtain | 1 | ≤

  s     (i) (i)  1 + ci (yn ) − f i (yn ) − 1 .

N −1  n=0

i=1

Now we invoke (10) to get ⎛ | 1 | ≤

N −1  n=0

⎛

s 

⎜ ⎜ ⎝

i=1

⎞

⎜ ⎜1 + 1 + 1 ⎝ H +1 H +1

H  h i =−H

⎞

⎟ ⎟ ⎟ ω Ii (h i )e(h i yn(i) )⎟ ⎠ − 1⎠ .

h i  =0

s Next we expand the product i=1 above. We write h = (h 1 , . . . , h s ) and we let wt(h) be the Hamming weight of h, that is, the number of nonzero coordinates of h. Then we obtain s  1 −1 H +1 s−wt(h) s    1 1 1+ ω Ii (h i )e(h i yn(i) ) H +1 (H + 1)wt(h) s

 | 1 | ≤ N 1+ +

N −1  n=0

⎛

h∈Z

i=1

0
⎜N = Os ⎜ ⎝H +

 h∈Zs 0
1 (H + 1)wt(h)

⎞  s   N −1     ⎟    . e(h · yn )⎟  ω Ii (h i )    ⎠ n=0

i=1

  Since ω Ii (h i ) ≤ 1 by Lemma 2, this yields ⎛ 

⎜N | 1 | = Os ⎜ ⎝H +

h∈Zs

⎞  N −1  ⎟ 1    . e(h · yn )⎟  ⎠ r (h) 

(14)

n=0

0
Next we consider the characteristic function c I of an interval I of the form (12). Concretely, let  v I = 0, k b with v ∈ Z and 1 ≤ v ≤ bk . We can write v−1  = vl b−l with all vl ∈ Zb . bk k

l=1

123

202

H. Niederreiter

Take a rational number z of the form z = wb−k with w ∈ Z and 0 ≤ w < bk . We can write  w = wl b−l with all wl ∈ Zb . k b k

z=

l=1

We have z ∈ I if and only if k 

wl b

−l

≤

l=1

k 

vl b−l .

(15)

l=1

For d1 , d2 ∈ Zb put δ(d1 , d2 ) = 1 if d1 = d2 and δ(d1 , d2 ) = 0 if d1 = d2 . Furthermore, let  u l :=

for 1 ≤ l < k, vl vl + 1 for l = k.

Then it follows from (15) that

c I (z) =

k 

δ(u 1 , w1 ) · · · δ(u l−1 , wl−1 )

u l −1

δ(u, wl ).

u=0

l=1

Now   1  h δ(d1 , d2 ) = e (d1 − d2 ) , b b h∈C(b)

and so  u −1   l−1 l  1 hl (wl − u) b e h r (wr − u r ) e c I (z) = b b r =1 u=0 l=1 h 1 ,...,h l ∈C(b)  l  k   1 −l = b e h r (wr − u r ) Tb (h l , u l ) b k 

l=1

−l





r =1

h 1 ,...,h l ∈C(b)

with Tb (h, L) :=

  L  hu for L ≥ 0. e b u=1

123

Further discrepancy bounds and an Erdös–Turán–Koksma inequality

203

This can be rewritten as 

c I (z) =

H∈C(b)



 k 1 e h l (wl − u l ) Vb (H; I ), b k l=1

where H = (h 1 , . . . , h k ) and Vb (H; I ) :=

k 

b−l Tb (h l , u l ).

l=a(H)

Here a(0) = 1, and for H = 0 we let a(H) be the largest r with h r = 0. We note that Vb (0; I ) = λ1 (I ) since Tb (0, L) = L. If we put also 

 k 1 h l u l Vb (H; I ), b (H; I ) := e − b

(16)

l=1

then by using the notation in (8) with m = 1 we can write 



c I (z) =

H∈C(b)

1 b (H; I )e h l wl b k k



l=1

=



 b (H; I )e

H∈C(b)k

 1 H⊗z . b

(17)

Now we consider the sum 2 introduced earlier in the proof, namely

2 =

N −1  

 f 1 (yn(1) ) · · · f s (yn(s) )cs+1 (z n(1) ) · · · cs+t (z n(t) ) − λs+t (J ) .

n=0

For each individual term of this sum, we use (9) and (17) to obtain f 1 (yn(1) ) · · · f s (yn(s) )cs+1 (z n(1) ) · · · cs+t (z n(t) ) − λs+t (J ) ⎛ ⎞ ⎛ ⎞ H H   =⎝ ψ I1 (h 1 )e(h 1 yn(1) )⎠ · · · ⎝ ψ Is (h s )e(h s yn(s) )⎠ h 1 =−H

⎛

h s =−H

⎞  1 ·⎝ H1 ⊗ z n(1) ⎠ b (H1 ; Is+1 )e b H1 ∈C(b)k ⎛ ⎞    1 Ht ⊗ z n(t) ⎠ − λs+t (J ) b (Ht ; Is+t )e ···⎝ b k 



Ht ∈C(b)

123

204

H. Niederreiter





=

h∈Zs , H∈C(b)t×k M(h)≤H

s 

⎛ ψ Ii (h i ) ⎝

i=1

t 

⎞ b (H j ; Is+ j )⎠

j=1

  1 ×e h · yn + H ⊗ zn − λs+t (J ), b where we put again h = (h 1 , . . . , h s ) and where H1 , . . . , Ht are the row vectors of the t × k matrix H ∈ C(b)t×k . Note that the contribution of the pair (h, H) = (0, 0) to the above sum is equal to λs+t (J ). Thus, by summing over n = 0, 1, . . . , N − 1 and applying the triangle inequality, we get ∗

| 2 | ≤

h∈Zs , H∈C(b)

  s   t   N −1        1    b (H j ; Is+ j )  e h · yn + H ⊗ zn  .  ψ Ii (h i )      b   t×k i=1

n=0

j=1

M(h)≤H

It follows from Lemma 2 that  s    1   .  ψ Ii (h i ) ≤   r (h) i=1

Furthermore, by (16) and [20, eq. (3.21)] we have   ⎞ ⎛  t  t t        Vb (H j ; Is+ j ) = Ot ⎝ b (H j ; Is+ j ) = Q b (H j )⎠ = Ot (Wb (H)),   j=1  j=1 j=1 where Q b (H j ) is given by (6). Therefore ⎛ ∗

⎜ | 2 | = Ot ⎜ ⎝

h∈Zs , H∈C(b)t×k

⎞   N −1   ⎟ Wb (H)   1  . e h · yn + H ⊗ zn ⎟  ⎠  r (h) b

(18)

n=0

M(h)≤H

By combining (14) and (18) and noting that Wb (0) = 1, we conclude that    A(J ; N )  1  | 1 + 2 | − λs+t (J ) =  N N ⎛ ⎜1 1 = Os,t ⎜ ⎝H + N

∗

h∈Zs , H∈C(b)t×k

⎞   N −1   ⎟ Wb (H)   1  . e h · yn + H ⊗ zn ⎟  ⎠  r (h) b

(19)

n=0

M(h)≤H

We recall that the interval J is of the form (11) with Is+1 , . . . , Is+t of the special form (12). We also emphasize that the implied constant in the Landau symbol Os,t

123

Further discrepancy bounds and an Erdös–Turán–Koksma inequality

205

in (19) is independent of J . Now we consider an interval J ⊆ [0, 1)s+t of the form J=

s 

s+t 

Ii ×

i=1

[0, xi ),

(20)

i=s+1

where I1 , . . . , Is are again arbitrary half-open subintervals of [0, 1) and where 0 < (1) xi ≤ 1 for s + 1 ≤ i ≤ s + t. For s + 1 ≤ i ≤ s + t, let vi be the largest integer (1) (2) (2) such that vi b−k ≤ xi and let vi be the least integer such that xi ≤ vi b−k . Put J1 :=

s  i=1

s+t 

Ii ×

i=s+1



(1)

v 0, i k b

 J2 :=

,

s 

Ii ×

i=1

s+t  i=s+1



(2)

v 0, i k b

 .

Then trivially A(J1 ; N ) ≤ A(J ; N ) ≤ A(J2 ; N ), and so      A(J ; N )  A(J ; N )      − λs+t (J ) ≤ max  − λs+t (J ) + max |λs+t (J ) − λs+t (J )| .  =1,2 =1,2 N N The first maximum is bounded by (19). For the second maximum, we observe that  s+t  s+t   v ()     i max |λs+t (J ) − λs+t (J )| = λs Ii max  − x  i  =1,2 =1,2  bk i=1 i=s+1 i=s+1   s+t  ()   t  vi  ≤ max  k − xi  ≤ k . b  b =1,2 

s 



i=s+1

Hence we get    A(J ; N )   − λs+t (J )  N ⎛ ⎜1 1 1 = Os,t ⎜ ⎝ bk + H + N

∗

h∈Zs , H∈C(b)t×k

⎞  N −1    ⎟ Wb (H)   1  . e h · yn + H ⊗ zn ⎟  ⎠ r (h)  b n=0

M(h)≤H

Passing from an interval of the form (20) to an arbitrary half-open subinterval J of [0, 1)s+t involves exactly the same arguments as the proof of (3) (see [12, p. 93] and [20, Proposition 2.4]) and introduces an additional factor 2t which is absorbed into Os,t . Since the implied constant in this Landau symbol is still independent of J , we arrive at the desired result. 

123

206

H. Niederreiter

Remark 2 The method in the proof of Theorem 1 can be easily adapted to the more general situation where in each of the last t coordinates of the points x0 , x1 , . . . , x N −1 in Theorem 1 (or in other words, in the coordinates of z0 , z1 , . . . , z N −1 ) we may use a different base and a different length of the digit expansion. This yields a “hybrid” of the classical Erdös–Turán–Koksma inequality in Lemma 1 and of [18, Satz 2]. We have not enunciated this more general result since it is not of interest for the applications we have in mind. 4 Mixing Halton sequences and nonlinear congruential sequences Let s ≥ 1 and t ≥ 1 be given integers. Let b1 , . . . , bs be pairwise coprime integers ≥2. Let p ≥ 3 be a prime and choose polynomials g1 , . . . , gt ∈ F p [X ]. Then we define the hybrid sequence xn = (φb1 (n), . . . , φbs (n), g1 (n)/ p, . . . , gt (n)/ p) ∈ [0, 1)s+t , n = 0, 1, . . . . (21) Thus, we “mix” an s-dimensional Halton sequence and t nonlinear congruential sequences. We need the following lemma which is an easy consequence of the Weil bound (see [13, Theorem 5.38] for the Weil bound). The result of this lemma was shown also in the proof of [19, Theorem 2]. Lemma 3 Let p ≥ 3 be a prime, let χ be a nontrivial additive character of F p , and let g ∈ F p [X ] with 2 ≤ deg(g) < p. Then for any integer L with 1 ≤ L ≤ p we have  L−1        χ (g(k)) = O deg(g) p 1/2 log p .    k=0

Theorem 2 Let b1 , . . . , bs be pairwise coprime integers ≥ 2. Let p ≥ 3 be a prime and assume that gcd(bi , p) = 1 for 1 ≤ i ≤ s. Let g1 , . . . , gt ∈ F p [X ] with deg(g j ) < p for 1 ≤ j ≤ t and assume that the polynomials 1, X, g1 (X ), . . . , gt (X ) are linearly independent over F p . Then for 1 ≤ N ≤ p the discrepancy D N of the first N terms of the sequence (21) satisfies D N = Ob1 ,...,bs ,t



N −1 Gp 1/2 (log p)t+1

1/(s+1) 

,

where G = max(deg(g1 ), . . . , deg(gt )) and the implied constant depends only on b1 , . . . , bs , t. Proof The discrepancy bound is trivial if N ≤ Gp 1/2 (log p)t+1 , and so we can assume that Gp 1/2 (log p)t+1 < N ≤ p. We introduce the positive integers  f i :=

123

1 N log (s + 1) log bi Gp 1/2 (log p)t+1

 for 1 ≤ i ≤ s

Further discrepancy bounds and an Erdös–Turán–Koksma inequality

207

and f

f

B := b1 1 · · · bs s . We assume next that N ≥ B. Let A(J ; N ) be the counting function in (1) relative to the points x0 , x1 , . . . , x N −1 in (21). We first choose an interval J ⊆ [0, 1)s+t of the form   s t   vi vi + 1 J= , [0, w j ) × fi f bi i i=1 bi j=1 f

with v1 , . . . , vs ∈ Z, 0 ≤ vi < bi i for 1 ≤ i ≤ s, and 0 < w j ≤ 1 for 1 ≤ j ≤ t. By the construction of the Halton sequence, we have xn ∈ J if and only if n ≡ d (mod B) and (g1 (n)/ p, . . . , gt (n)/ p) ∈

t 

[0, w j ),

j=1

where d is an integer with 0 ≤ d < B which depends only on J . Thus, n = Bk + d for some integer k, and the condition 0 ≤ n ≤ N − 1 is equivalent to 0 ≤ k ≤ (N − d − 1)/B. Recall that N ≥ B ≥ d + 1. It follows that ⎧ ⎨



A(J ; N ) = # 0 ≤ k ≤ ⎩

N −d −1 B

 : (g1 (Bk + d)/ p, . . . , gt (Bk + d)/ p) ∈

t  j=1

⎫ ⎬ [0, w j ) , ⎭

and so 

N −d −1+ B A(J ; N ) = B (B)

where D L

 t

 wj + O

j=1

N −d −1+ B B



 ,

(B) D(N −d−1+B)/B

denotes the discrepancy of the L points

(g1 (Bk + d)/ p, . . . , gt (Bk + d)/ p) ∈ [0, 1)t , k = 0, 1, . . . , L − 1. Therefore  A(J ; N ) = N λs+t (J ) + O

N −d −1+ B B



(B) D(N −d−1+B)/B

 .

(22)

(B)

We now bound D L for 1 ≤ L ≤ p by using [20, Corollary 3.11] in the following form: if χ is the canonical additive character of F p and the real number R is such that  ⎛ ⎞   t    L−1  ⎝ ⎠ χ h j g j (Bk + d)  ≤ R    k=0 j=1

(23)

123

208

H. Niederreiter

for all h = (h 1 , . . . , h t ) ∈ Ftp with h = 0 ∈ Ftp , then

= Ot R(log p)t .

(B)

L DL

For fixed h = (h 1 , . . . , h t ) ∈ Ftp with h = 0 ∈ Ftp , we put g(X ) :=

t 

h j g j (B X + d) ∈ F p [X ].

j=1

We observe that gcd(B, p) = 1 since gcd(bi , p) = 1 for 1 ≤ i ≤ s. Therefore the conditions on g1 , . . . , gt in the theorem imply that 2 ≤ deg(g) ≤ G < p. Thus, it follows from Lemma 3 that we have (23) with a number R satisfying   R = O Gp 1/2 log p . Hence (B)

L DL

  for 1 ≤ L ≤ p, = Ot Gp 1/2 (log p)t+1

and so (22) yields   A(J ; N ) = N λs+t (J ) + Ot Gp 1/2 (log p)t+1 .

(24)

Next we consider an interval J ⊆ [0, 1)s+t of the form J=

s 



i=1

0,

vi f

bi i

 ×

t 

[0, w j )

j=1

f

with v1 , . . . , vs ∈ Z, 1 ≤ vi ≤ bi i for 1 ≤ i ≤ s, and 0 < w j ≤ 1 for 1 ≤ j ≤ t. By adding at most B identities of the form (24), we obtain   A(J ; N ) = N λs+t (J ) + Ot BGp 1/2 (log p)t+1 .

(25)

Finally, we consider an arbitrary half-open interval J ⊆ [0, 1)s+t with one vertex at the origin, i.e., J=

s t   [0, u i ) × [0, w j ) i=1

j=1

with 0 < u i ≤ 1 for 1 ≤ i ≤ s and 0 < w j ≤ 1 for 1 ≤ j ≤ t. By approximating f the u i from below and above by the nearest fractions of the form vi /bi i with vi ∈ Z

123

Further discrepancy bounds and an Erdös–Turán–Koksma inequality

209

and proceeding as in the part of the proof of Theorem 1 that follows (20), we deduce from (25) that D ∗N ≤

s 

  + Ot B N −1 Gp 1/2 (log p)t+1 ,

− fi

bi

(26)

i=1

where D ∗N is the star discrepancy of the points x0 , x1 , . . . , x N −1 . This bound is trivial for N < B, and so it holds for all integers N with Gp 1/2 (log p)t+1 < N ≤ p. By the definition of the f i we have 

N Gp 1/2 (log p)t+1

1/(s+1)

 f

≤ bi i ≤ bi

N Gp 1/2 (log p)t+1

1/(s+1) for 1 ≤ i ≤ s,

and so  B ≤ b1 · · · bs

N Gp 1/2 (log p)t+1

s/(s+1) .

In view of (26), this yields D ∗N

= Ob1 ,...,bs ,t

 N

−1

Gp

1/2

(log p)

t+1

1/(s+1) 

,

and an application of (3) completes the proof.



Remark 3 The conditions on g1 , . . . , gt ∈ F p [X ] in Theorem 2 are satisfied if 2 ≤ deg(g j ) < p for 1 ≤ j ≤ t and deg(g1 ), . . . , deg(gt ) are distinct. Remark 4 Fix the parameters b1 , . . . , bs , t as in Theorem 2. For each prime p ≥ 3, choose g1 , . . . , gt ∈ F p [X ] as in Theorem 2 and put G p = max(deg(g1 ), . . . , deg(gt )). Choose also positive integers N p ≤ p with lim

p→∞

G p p 1/2 (log p)t+1 = 0. Np

Then D N p → 0 as p → ∞ by Theorem 2, and so in this sense we get asymptotic uniform distribution. 5 Mixing Kronecker sequences and nonlinear congruential sequences Let α ∈ Rs for an arbitrary dimension s ≥ 1, let p be a prime, and for a given integer t ≥ 1 choose polynomials g1 , . . . , gt ∈ F p [X ]. Consider the hybrid sequence xn = ({nα}, g1 (n)/ p, . . . , gt (n)/ p) ∈ [0, 1)s+t , n = 0, 1, . . . .

(27)

123

210

H. Niederreiter

We first establish a bound for the following exponential sum. For h1 ∈ Zs , h2 = (h 1 , . . . , h t ) ∈ Zt , and an integer N ≥ 1, put E N (h1 , h2 ) :=

N −1 

⎛ e ⎝n(h1 · α) +

n=0

t 

⎞ h j g j (n)/ p ⎠.

(28)

j=1

Lemma 4 Let p ≥ 5 be a prime and let g1 , . . . , gt ∈ F p [X ] with 3 ≤ deg(g j ) < p for 1 ≤ j ≤ t and deg(g1 ), . . . , deg(gt ) distinct. Let α ∈ Rs , h1 ∈ Zs , and h2 = (h 1 , . . . , h t ) ∈ Zt with gcd(h 1 , . . . , h t , p) = 1. Then for the exponential sum E N (h1 , h2 ) in (28) we have   |E N (h1 , h2 )| = O N 1/2 G 1/2 p 1/4 (log p)1/2 for 1 ≤ N ≤ p, where G = max(deg(g1 ), . . . , deg(gt )). Proof We have |E N (h1 , h2 )|2 =

N −1 

⎛ e ⎝(k − n)(h1 · α) +

k,n=0

t 

⎞ h j (g j (k) − g j (n))/ p ⎠

j=1

   ⎛ ⎞  N  −1 t    ≤ N + 2  e ⎝(k − n)(h1 · α) + h j (g j (k) − g j (n))/ p ⎠ k,n=0  j=1  k>n   ⎛ ⎞  N  t −1−d   −1 N    ⎝ ⎠ = N +2 e d(h1 · α) + h j (g j (n + d) − g j (n))/ p   d=1 n=0  j=1   N −1  N  −1−d     ≤ N +2 χ ( f d (n)) ,    d=1

n=0

where χ denotes the canonical additive character of F p and f d (X ) :=

t 

h j (g j (X + d) − g j (X )) ∈ F p [X ].

j=1

Note that 1 ≤ N ≤ p, and so 1 ≤ d < p. For fixed d ∈ F∗p , the polynomial g j (X + d) − g j (X ) has degree deg(g j ) − 1 for 1 ≤ j ≤ t. It follows therefore from the conditions in the lemma that for each d ∈ F∗p we have 2 ≤ deg( f d ) < p. Thus, Lemma 3 yields  N −1−d         χ ( f d (n)) = O Gp 1/2 log p .    n=0

123

Further discrepancy bounds and an Erdös–Turán–Koksma inequality

211

Hence   |E N (h1 , h2 )|2 = O N Gp 1/2 log p , 

and we arrive at the desired result.

The following lemma was shown in [23]. We again use the notation in Definition 1. We write also u = min ({u}, 1 − {u}) for the distance from u ∈ R to the nearest integer. Note that if α = (α1 , . . . , αs ) ∈ Rs is such that 1, α1 , . . . , αs are linearly independent over Q, then h · α > 0 for all h ∈ Zs \{0}. Lemma 5 Let s be an arbitrary positive integer and let α ∈ Rs be such that there exist real numbers σ ≥ 1 and c > 0 with r (h)σ h · α ≥ c for all h ∈ Zs \{0}. Then for any integers H ≥ 1 and N ≥ 1 we have 

r (h)

h∈Zs

 N −1       for all ε > 0. e(n(h · α)) = Oα,ε H (σ −1)s+ε   

−1 

n=0

0
In order to get a reasonable discrepancy bound for the sequence (27), we assume that α ∈ Rs is of finite type according to the following standard definition (see, e.g., [16, Definition 6.1]). Definition 2 Let η be a real number. Then α ∈ Rs is of finite type η if η is the infimum of all real numbers σ for which there exists a positive constant c = c(σ, α) such that r (h)σ h · α ≥ c for all h ∈ Zs \{0}. Remark 5 As noted in [16, p. 164], it is an easy consequence of Minkowski’s linear forms theorem that we always have η ≥ 1. Well-known examples of points α ∈ Rs of finite type η = 1 are the following: (i) α = (α1 , . . . , αs ) with real algebraic numbers α1 , . . . , αs such that 1, α1 , . . . , αs are linearly independent over Q (see [29]); (ii) α = (er1 , . . . , ers ) with distinct nonzero rational numbers r1 , . . . , rs (see [1]). Theorem 3 Let p ≥ 5 be a prime and let g1 , . . . , gt ∈ F p [X ] with 3 ≤ deg(g j ) < p for 1 ≤ j ≤ t and deg(g1 ), . . . , deg(gt ) distinct. Let α ∈ Rs be of finite type η. Then for 1 ≤ N ≤ p the discrepancy D N of the first N terms of the sequence (27) satisfies    D N = Oα,t,ε max N −1/((η−1)s+1)+ε , N −1/2 G 1/2 p 1/4 (log p)1/2 (log N )s+t for all ε > 0, where G = max(deg(g1 ), . . . , deg(gt )) and the implied constant depends only on α, t, and ε.

123

212

H. Niederreiter

Proof Since the discrepancy bound is trivial for N = 1, we can assume that 2≤N ≤ p. We apply the Erdös–Turán–Koksma inequality (see Lemma 1) with H = min

"

#  N 1/((η−1)s+1) , p − 1 .

Then 2 ≤ H ≤ N and H < p. Furthermore, ⎞  N −1   ⎟   . r (h)−1  e(h · xn )⎟  ⎠

⎛ ⎜1 1 D N = Os,t ⎜ ⎝H + N

 h∈Zs+t

(29)

n=0

0
Write h = (h1 , h2 ) with h1 ∈ Zs , h2 ∈ Zt . We first consider the case where h1 = 0 and h2 = 0. Then N −1 

e(h · xn ) =

n=0

N −1 

e(n(h1 · α)).

n=0

Now fix an ε > 0. Then by Lemma 5 we get 

r (h)

 N −1       e(h · xn ) = Oα,ε H (η−1)s+ε   

−1 

h∈Zs+t , h2 =0

n=0

0
  = Oα,ε N (η−1)s/((η−1)s+1)+ε .

Moreover, for h ∈ Zs+t with M(h) ≤ H and h2 = 0, we can apply Lemma 4 to obtain  N −1        e(h · xn ) = |E N (h1 , h2 )| = O N 1/2 G 1/2 p 1/4 (log p)1/2 .    n=0

Therefore  h∈Zs+t , h2 =0

 N −1      r (h)−1  e(h · xn )   n=0

0
⎛

⎜ 1/2 1/2 1/4 1/2 = O⎜ ⎝ N G p (log p)

⎞  h∈Zs+t , h2 =0 0
123

⎟ r (h)−1 ⎟ ⎠

Further discrepancy bounds and an Erdös–Turán–Koksma inequality

213

  = Os,t N 1/2 G 1/2 p 1/4 (log p)1/2 (log H )s+t   = Os,t N 1/2 G 1/2 p 1/4 (log p)1/2 (log N )s+t . 

By combining the above bounds with (29), we arrive at the desired result.

Corollary 1 Let p ≥ 5 be a prime and let g1 , . . . , gt ∈ F p [X ] with 3 ≤ deg(g j ) < p for 1 ≤ j ≤ t and deg(g1 ), . . . , deg(gt ) distinct. Let α ∈ Rs be of finite type η = 1. Then for 2 ≤ N ≤ p the discrepancy D N of the first N terms of the sequence (27) satisfies   D N = Oα,t N −1/2 G 1/2 p 1/4 (log p)1/2 (log N )s+t , where G = max(deg(g1 ), . . . , deg(gt )) and the implied constant depends only on α and t. Remark 6 Fix an integer t ≥ 1 and α ∈ Rs of finite type. For each prime p ≥ 5, choose g1 , . . . , gt ∈ F p [X ] as in Theorem 3 and put G p = max(deg(g1 ), . . . , deg(gt )). Choose also positive integers N p ≤ p with lim

p→∞

G p p 1/2 (log p)(log N p )2(s+t) = 0. Np

Then D N p → 0 as p → ∞ by Theorem 3, and so in this sense we get asymptotic uniform distribution. 6 Mixing Halton sequences and explicit inversive congruential sequences Let s ≥ 1 and t ≥ 1 be given integers. Let b1 , . . . , bs be pairwise coprime integers ≥ 2. Let p ≥ 5 be a prime and choose a1 , . . . , at ∈ F∗p and d1 , . . . , dt ∈ F p . For 1 ≤ j ≤ t, put ( j)

en = a j n + d j , n = 0, 1, . . . , p − 1, and extend with period p. Then we define the hybrid sequence xn = (φb1 (n), . . . , φbs (n), en(1) / p, . . . , en(t) / p) ∈ [0, 1)s+t , n = 0, 1, . . . .

(30)

Thus, we “mix” an s-dimensional Halton sequence and t explicit inversive congruential sequences. The following result was shown in the proof of [21, Theorem 6]. Lemma 6 Let p ≥ 5 be a prime and let χ be a nontrivial additive character of F p . For an integer m ≥ 1, let a1 , . . . , am ∈ F∗p and d1 , . . . , dm ∈ F p be such that

123

214

H. Niederreiter

d1 a1 , . . . , dm am are distinct elements of F p . Let h = (h 1 , . . . , h m ) ∈ Fmp be such that h = 0 ∈ Fmp . Then for any integer N with 1 ≤ N ≤ p we have  ⎛ ⎞   N −1 m       ⎝ ⎠ χ h j a j n + d j  = Om p 1/2 log p .    n=0 j=1 Theorem 4 Let b1 , . . . , bs be pairwise coprime integers ≥ 2. Let p ≥ 5 be a prime and assume that gcd(bi , p) = 1 for 1 ≤ i ≤ s. Let a1 , . . . , at ∈ F∗p and d1 , . . . , dt ∈ F p be such that d1 a1 , . . . , dt at are distinct elements of F p . Then for 1 ≤ N ≤ p the discrepancy D N of the first N terms of the sequence (30) satisfies D N = Ob1 ,...,bs ,t



N −1 p 1/2 (log p)t+1

1/(s+1) 

with an implied constant depending only on b1 , . . . , bs , t. Proof We proceed by a method similar to that in the proof of Theorem 2. The discrepancy bound is trivial if N ≤ p 1/2 (log p)t+1 , and so we can assume that p 1/2 (log p)t+1 < N ≤ p. We introduce the positive integers  f i :=

1 N log 1/2 (s + 1) log bi p (log p)t+1

 for 1 ≤ i ≤ s

and f

f

B := b1 1 · · · bs s . (B)

We assume next that N ≥ B. Then we have (22), where D L is now the discrepancy of the L points (1)

(t)

(e Bk+d / p, . . . , e Bk+d / p) ∈ [0, 1)t , k = 0, 1, . . . , L − 1. Note that for 1 ≤ j ≤ t and k = 0, 1, . . ., we have ( j)

e Bk+d = a j (Bk + d) + d j = a j Bk + a j d + d j . This is again an explicit inversive generator with a j replaced by a j B and d j replaced by a j d + d j . We observe also that gcd(B, p) = 1 since gcd(bi , p) = 1 for 1 ≤ i ≤ s. Now (a j d + d j )a j B = d B + d j a j B for 1 ≤ j ≤ t. Since d1 a1 , . . . , dt at are distinct elements of F p by hypothesis, it follows that (a1 d+d1 )a1 B, . . . , (at d+dt )at B are also distinct elements of F p . Thus, Lemma 6 with

123

Further discrepancy bounds and an Erdös–Turán–Koksma inequality

215

m = t shows that if χ is the canonical additive character of F p and h = (h 1 , . . . , h t ) ∈ Ftp is such that h = 0 ∈ Ftp , then for 1 ≤ L ≤ p we have  ⎛ ⎞  L−1  t     ( j) ⎠ 1/2  ⎝ = O p χ h e log p . j t Bk+d    k=0  j=1 It follows therefore as in the proof of Theorem 2 that (B)

L DL

  for 1 ≤ L ≤ p. = Ot p 1/2 (log p)t+1

Hence the analog of (24) is   A(J ; N ) = N λs+t (J ) + Ot p 1/2 (log p)t+1 . The analog of (25) is   A(J ; N ) = N λs+t (J ) + Ot Bp 1/2 (log p)t+1 and the analog of (26) is D ∗N ≤

s 

− fi

bi

  + Ot B N −1 p 1/2 (log p)t+1 .

(31)

i=1

This bound is trivial for N < B, and so it holds for all integers N with p 1/2 (log p)t+1 < N ≤ p. By the definition of the f i we have 

N p 1/2 (log p)t+1

1/(s+1)

 f

≤ bi i ≤ bi

N p 1/2 (log p)t+1

1/(s+1) for 1 ≤ i ≤ s,

and so  B ≤ b1 · · · bs

N p 1/2 (log p)t+1

s/(s+1) .

In view of (31), this yields D ∗N = Ob1 ,...,bs ,t



N −1 p 1/2 (log p)t+1

and an application of (3) completes the proof.

1/(s+1) 

, 

123

216

H. Niederreiter

Remark 7 Fix the parameters b1 , . . . , bs , t as in Theorem 4. For each prime p ≥ 5, choose a1 , . . . , at , d1 , . . . , dt satisfying the hypotheses in Theorem 4. Choose also positive integers N p ≤ p with lim

p→∞

p 1/2 (log p)t+1 = 0. Np

Then D N p → 0 as p → ∞ by Theorem 4, and so in this sense we get asymptotic uniform distribution. 7 Mixing Kronecker sequences and explicit inversive congruential sequences Let α ∈ Rs for an arbitrary dimension s ≥ 1, let p ≥ 5 be a prime, and for an integer t ≥ 1 choose a1 , . . . , at ∈ F∗p and d1 , . . . , dt ∈ F p . For 1 ≤ j ≤ t, put ( j)

en = a j n + d j , n = 0, 1, . . . , p − 1, and extend with period p. Consider the hybrid sequence xn = ({nα}, en(1) / p, . . . , en(t) / p) ∈ [0, 1)s+t , n = 0, 1, . . . .

(32)

We first establish a bound for the following exponential sum. For h1 ∈ Zs , h2 = (h 1 , . . . , h t ) ∈ Zt , and an integer N ≥ 1, put C N (h1 , h2 ) :=

N −1 

⎛ e ⎝n(h1 · α) +

n=0

t 

⎞ ( j)

h j en / p ⎠ .

(33)

j=1

Lemma 7 Let p ≥ 5 be a prime and let a1 , . . . , at ∈ F∗p and d1 , . . . , dt ∈ F p be such that d1 a1 , . . . , dt at are distinct elements of F p . Let α ∈ Rs , h1 ∈ Zs , and h2 = (h 1 , . . . , h t ) ∈ Zt with gcd(h 1 , . . . , h t , p) = 1. Then for the exponential sum C N (h1 , h2 ) in (33) we have   |C N (h1 , h2 )| = Ot N 1/2 p 1/4 (log p)1/2 for 1 ≤ N ≤ p. Proof As in the proof of Lemma 4 we obtain    |C N (h1 , h2 )|2 ≤ N + 2  d=1 

N −1  N  −1−d  n=0

⎞   ⎝ ⎠ χ h j (a j n + a j d + d j − a j n + d j )  ,  j=1 ⎛

t 

where χ is again the canonical additive character of F p . Now we consider the character sum inside the last absolute value bars. Note that 1 ≤ N ≤ p, and so 1 ≤ d < p. Suppose that d ∈ F∗p is of the form d = d j a j − dl al for some 1 ≤ j, l ≤ t with

123

Further discrepancy bounds and an Erdös–Turán–Koksma inequality

217

j = l. Clearly, there are O(t 2 ) such values of d. For these values of d, we bound the absolute value of the character sum trivially by N . If d is not of the above form, then it is easily seen that we have a character sum satisfying the hypotheses of Lemma 6 with m = 2t. Therefore the absolute value of the character sum is Ot p 1/2 log p . Altogether, we obtain     |C N (h1 , h2 )|2 ≤ N + Ot (N ) + Ot N p 1/2 log p = Ot N p 1/2 log p , which yields the desired result.



Now we use again the notion of finite type introduced in Definition 2. Theorem 5 Let p ≥ 5 be a prime and let a1 , . . . , at ∈ F∗p and d1 , . . . , dt ∈ F p be such that d1 a1 , . . . , dt at are distinct elements of F p . Let α ∈ Rs be of finite type η. Then for 1 ≤ N ≤ p the discrepancy D N of the first N terms of the sequence (32) satisfies    for all ε > 0 D N =Oα,t,ε max N −1/((η−1)s+1)+ε , N −1/2 p 1/4 (log p)1/2 (log N )s+t with an implied constant depending only on α, t, and ε. Proof The proof proceeds in the same way as the proof of Theorem 3, but with Lemma 4 replaced by Lemma 7.  Corollary 2 Let p ≥ 5 be a prime and let a1 , . . . , at ∈ F∗p and d1 , . . . , dt ∈ F p be such that d1 a1 , . . . , dt at are distinct elements of F p . Let α ∈ Rs be of finite type η = 1. Then for 2 ≤ N ≤ p the discrepancy D N of the first N terms of the sequence (32) satisfies   D N = Oα,t N −1/2 p 1/4 (log p)1/2 (log N )s+t with an implied constant depending only on α and t. Remark 8 Fix an integer t ≥ 1 and α ∈ Rs of finite type. For each prime p ≥ 5, choose a1 , . . . , at , d1 , . . . , dt satisfying the hypotheses in Theorem 5. Choose also positive integers N p ≤ p with

lim

p→∞

p 1/2 (log p)(log N p )2(s+t) = 0. Np

Then D N p → 0 as p → ∞ by Theorem 5, and so in this sense we get asymptotic uniform distribution.

123

218

H. Niederreiter

8 Mixing Kronecker sequences and digital inversive sequences Let α ∈ Rs for an arbitrary dimension s ≥ 1. Let p be an arbitrary prime, let k ≥ 2 be an integer, and let Fq be the finite field of order q = p k . Let z 0 , z 1 , . . . be the digital inversive sequence defined by (5) and let T be its least period. Then we choose integers 0 ≤ i 1 < i 2 < · · · < i t < T and consider the hybrid sequence xn = ({nα}, z n+i1 , . . . , z n+it ) ∈ [0, 1)s+t , n = 0, 1, . . . .

(34)

A bound for the discrepancy of this sequence can be established by using the new version of the Erdös–Turán–Koksma inequality in Theorem 1. For this purpose, we employ the same notation as in Sect. 3. In particular, we put zn = (z n+i1 , . . . , z n+it ) ∈ [0, 1)t , n = 0, 1, . . . .

(35)

For h ∈ Zs , a t × k matrix H ∈ C( p)t×k , and an integer N ≥ 1, we introduce the exponential sum FN (h, H) :=

N −1  n=0

  1 e n(h · α) + H ⊗ zn . p

(36)

In order to estimate this exponential sum, we need the following result shown in [25, Theorem 2]. As in Sect. 2, we let γ0 , γ1 , . . . be the sequence of elements of Fq which is the inversive generator corresponding to the sequence z 0 , z 1 , . . . according to (4) and (5). Lemma 8 Let the sequence γ0 , γ1 , . . . of elements of Fq be an inversive generator with least period T . Let 0 ≤ f 1 < f 2 < · · · < f m < T be integers. Let χ be a nontrivial additive character of Fq and let μ1 , . . . , μm be elements of Fq that are not all 0. Then for any integer N with 1 ≤ N ≤ T we have  ⎛ ⎞   N −1 m       = Om N 1/2 q 1/4 .  ⎝ ⎠ χ μ γ j n+ f j     n=0 j=1 Lemma 9 Let α ∈ Rs , h ∈ Zs , and let the matrix H ∈ C( p)t×k be nonzero. Then for the exponential sum FN (h, H) in (36) we have   |FN (h, H)| = Ot N 3/4 q 1/8 for 1 ≤ N ≤ T, where q = p k . Proof Let {β1 , . . . , βk } be the ordered basis of Fq over F p as in Sect. 2 and let {ϑ1 , . . . , ϑk } be its dual basis. Then it is well known (see [13, p. 58]) that the coefficients cn,l in (4) can be represented as cn,l = Tr(ϑl γn ),

123

Further discrepancy bounds and an Erdös–Turán–Koksma inequality

219

where Tr denotes the trace function from Fq to F p . Now for a nonzero matrix H = (h j,l ) ∈ C( p)t×k and for a point zn in (35), we obtain by the F p -linearity of the trace that ⎛ ⎞   t  k  1 1 H ⊗ zn = e ⎝ e h j,l cn+i j ,l ⎠ p p j=1 l=1 ⎛ ⎞ t  k  1 = e⎝ h j,l Tr(ϑl γn+i j )⎠ p j=1 l=1 ⎛ ⎛ ⎞⎞ t  k  1 = e ⎝ Tr ⎝ h j,l ϑl γn+i j ⎠⎠ p j=1 l=1 ⎛ ⎞ t  =χ⎝ μ j γn+i j ⎠ , j=1

where χ is the canonical additive character of Fq and μj =

k 

h j,l ϑl ∈ Fq for 1 ≤ j ≤ t.

l=1

Since the matrix H is nonzero, the elements μ1 , . . . , μt are not all 0. By what we have already shown, we can write ⎛ ⎞ N −1 t   FN (h, H) = e(n(h · α))χ ⎝ μ j γn+i j ⎠ . n=0

j=1

Now we proceed as in the proof of Lemma 4 to obtain  ⎛ ⎞  N −1  N  −1−d t     2  ⎝ ⎠ |FN (h, H)| ≤ N + 2 χ μ j (γn+d+i j − γn+i j )  .   d=1  n=0 j=1 Next we consider the character sum inside the last absolute value bars. Note that 1 ≤ N ≤ T , and so 1 ≤ d < T . Suppose that d is such that d ≡ i j − i  (mod T ) for some 1 ≤ j,  ≤ t with j = . There are O(t 2 ) such values of d. For these values of d, we bound the absolute value of the character sum trivially by N . If d is not of the above form, then it is easily seen that we have a character sum satisfying the hypotheses of Lemma

8 with m = 2t. Therefore the absolute value of the character sum is Ot N 1/2 q 1/4 . Altogether, we obtain     |FN (h, H)|2 ≤ N + Ot (N ) + Ot N 3/2 q 1/4 = Ot N 3/2 q 1/4 , which yields the desired result.



123

220

H. Niederreiter

Now we use again the notion of finite type introduced in Definition 2. Theorem 6 Let α ∈ Rs be of finite type η. Then for 1 ≤ N ≤ T the discrepancy D N of the first N terms of the sequence (34) satisfies    for all ε > 0, D N = Oα,t,ε max N −1/((η−1)s+1)+ε , N −1/4 q 1/8 (log q)t (log N )s where q = p k and the implied constant depends only on α, t, and ε. Proof Since the discrepancy bound is trivial for N = 1, we can assume that 2 ≤ N ≤ T . We apply Theorem 1 with " # H = N 1/((η−1)s+1) . Then 2 ≤ H ≤ N ≤ q + 1 = p k + 1 and ⎛

⎞

⎜1 1 D N = Os,t ⎜ ⎝H + N

∗

h∈Zs , H∈C( p)t×k

⎟ W p (H) |FN (h, H)|⎟ ⎠. r (h)

(37)

M(h)≤H

We first consider the pairs (h, H) in the summation in (37) with h = 0, M(h) ≤ H , and H = 0. Then W p (H) = 1 by (6) and (7). Furthermore by (36), FN (h, H) =

N −1 

e(n(h · α)).

n=0

Now fix an ε > 0. Then the contribution of these pairs to the sum in (37) is  h∈Zs

r (h)

 N −1       e(n(h · α)) = Oα,ε H (η−1)s+ε   

−1 

n=0

0
  = Oα,ε N (η−1)s/((η−1)s+1)+ε

(38)

according to Lemma 5. The remaining pairs (h, H) in the summation in (37) satisfy M(h) ≤ H and H = 0. For these pairs we can apply Lemma 9 to obtain ⎞

⎛  h∈Zs , H∈C( p)t×k M(h)≤H, H =0

123

⎜ 3/4 1/8 W p (H) |FN (h, H)| = Ot ⎜ ⎝N q r (h)

 h∈Zs , H∈C( p)t×k M(h)≤H, H =0

W p (H) ⎟ ⎟. r (h) ⎠

Further discrepancy bounds and an Erdös–Turán–Koksma inequality

221

Now clearly 





r (h)−1 = Os (log H )s = Os (log N )s .

h∈Zs M(h)≤H

Moreover, by [20, Lemma 3.13] we have 



W p (H) = Ot (log q)t ,

H∈C( p)t×k H =0

and so  h∈Zs , H∈C( p)t×k

  W p (H) |FN (h, H)| = Os,t N 3/4 q 1/8 (log q)t (log N )s . r (h)

M(h)≤H, H =0

By combining this bound with (37) and (38), we complete the proof.



Corollary 3 Let α ∈ Rs be of finite type η = 1. Then for 2 ≤ N ≤ T the discrepancy D N of the first N terms of the sequence (34) satisfies   D N = Oα,t N −1/4 q 1/8 (log q)t (log N )s with an implied constant depending only on α and t. Remark 9 Fix an integer t ≥ 1 and α ∈ Rs of finite type. Consider infinitely many composite prime powers q. For each chosen q, take a digital inversive sequence with maximum period q + 1 and integers i 1 , . . . , i t as in (34). Choose also positive integers Nq ≤ q + 1 with q 1/2 (log q)4t (log Nq )4s → 0 as q → ∞. Nq Then D Nq → 0 as q → ∞ by Theorem 6, and so in this sense we get asymptotic uniform distribution. References 1. Baker, A.: On some diophantine inequalities involving the exponential function. Can. J. Math. 17, 616–626 (1965) 2. Cochrane, T.: Trigonometric approximation and uniform distribution modulo one. Proc. Am. Math. Soc. 103, 695–702 (1988) 3. Drmota, M., Tichy, R.F.: Sequences, Discrepancies and Applications. Lecture Notes in Mathematics, vol. 1651. Springer, Berlin (1997) 4. Eichenauer, J., Grothe, H., Lehn, J.: Marsaglia’s lattice test and non-linear congruential pseudo random number generators. Metrika 35, 241–250 (1988)

123

222

H. Niederreiter

5. Eichenauer-Herrmann, J.: Statistical independence of a new class of inversive congruential pseudorandom numbers. Math. Comp. 60, 375–384 (1993) 6. Erdös, P., Turán, P.: On a problem in the theory of uniform distribution, I, II. Indag. Math. 10, 370–378, 406–413 (1948) 7. Gnewuch, M.: On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence. J. Complexity 25, 312–317 (2009) 8. Halton, J.H.: On the efficiency of certain quasi-random sequences of points in evaluating multidimensional integrals. Numer. Math. 2, 84–90, 196 (1960) 9. Hellekalek, P.: General discrepancy estimates: the Walsh function system. Acta Arith. 67, 209–218 (1994) 10. Hellekalek, P.: General discrepancy estimates III: the Erdös–Turán–Koksma inequality for the Haar function system. Monatsh. Math. 120, 25–45 (1995) 11. Koksma, J.F.: Some Theorems on Diophantine Inequalities. Scriptum No 5. Math Centrum, Amsterdam (1950) 12. Kuipers, L., Niederreiter, H.: Uniform Distribution of Sequences. Wiley, New York (1974); reprint, Dover, Mineola (2006) 13. Lidl, R., Niederreiter, H.: Finite Fields. Cambridge University Press, Cambridge (1997) 14. Mauduit, Ch., Rivat, J., Sárközy, A.: On the pseudo-random properties of n c . Ill. J. Math. 46, 185–197 (2002) 15. Montgomery, H.L.: Ten Lectures on the Interface between Analytic Number Theory and Harmonic Analysis. American Mathematical Society, Providence (1994) 16. Niederreiter, H.: Application of diophantine approximations to numerical integration. In: Osgood, C.F. (ed.) Diophantine Approximation and its Applications, pp. 129–199. Academic Press, New York (1973) 17. Niederreiter, H.: The performance of k-step pseudorandom number generators under the uniformity test. SIAM J. Sci. Stat. Comput. 5, 798–810 (1984) 18. Niederreiter, H.: Pseudozufallszahlen und die Theorie der Gleichverteilung. Sitzungsber Österr Akad Wiss Math-Naturw Kl Abt II 195, 109–138 (1986) 19. Niederreiter, H.: Statistical independence of nonlinear congruential pseudorandom numbers. Monatsh. Math. 106, 149–159 (1988) 20. Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia (1992) 21. Niederreiter, H.: On a new class of pseudorandom numbers for simulation methods. J. Comp. Appl. Math. 56, 159–167 (1994) 22. Niederreiter, H.: New developments in uniform pseudorandom number and vector generation. In: Niederreiter, H., Shiue, P.J.-S. (eds.) Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing. Lecture Notes in Statistics, vol. 106, pp. 87–120. Springer, New York (1995) 23. Niederreiter, H.: On the discrepancy of some hybrid sequences. Acta Arith. (2009, in press) 24. Niederreiter, H., Philipp, W.: Berry–Esseen bounds and a theorem of Erdös and Turán on uniform distribution mod 1. Duke Math. J. 40, 633–649 (1973) 25. Niederreiter, H., Rivat, J.: On the correlation of pseudorandom numbers generated by inversive methods. Monatsh. Math. 153, 251–264 (2008) 26. Ökten, G.: A probabilistic result on the discrepancy of a hybrid-Monte Carlo sequence and applications. Monte Carlo Methods Appl. 2, 255–270 (1996) 27. Ökten, G., Tuffin, B., Burago, V.: A central limit theorem and improved error bounds for a hybrid-Monte Carlo sequence with applications in computational finance. J. Complexity 22, 435–458 (2006) 28. Rivat, J., Tenenbaum, G.: Constantes d’Erdös–Turán. Ramanujan J. 9, 111–121 (2005) 29. Schmidt, W.M.: Simultaneous approximation to algebraic numbers by rationals. Acta Math. 125, 189–201 (1970) 30. Spanier, J.: Quasi-Monte Carlo methods for particle transport problems. In: Niederreiter, H., Shiue, P.J.-S. (eds.) Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing. Lecture Notes in Statistics, vol. 106, pp. 121–148. Springer, New York (1995) 31. Szüsz, P.: On a problem in the theory of uniform distribution (Hungarian). In: Comptes Rendus du Premier Congrès des Mathématiciens Hongrois 1950, pp. 461–472. Akadémiai Kiadó, Budapest (1952) 32. Vaaler, J.D.: Some extremal functions in Fourier analysis. Bull. Am. Math. Soc. (N.S.) 12, 183–216 (1985)

123