3.3.4 THE SPECTRAL TEST 109 In fact, the (Unable to start debugging on the web server)
3.3.4 THE SPECTRAL TEST 109 In fact, the upper bound gets even smaller when q has a factor in common with m, since s and m/G generally become smaller. (See exercise 26.) We have now proved that the g(ul, . . . , ut) part of our upper bound (44) on the discrepancy is small, if N is large enough and if (ul,. . . , Q) does not satisfy the spectral test congruence (15). Exercise 27 proves that the f(ul, . . . , ut) part of our upper bound is small, when summed over all the nonzero vectors CR,…, ut) satisfying (15), provided that all such vectors are far away from (0,. . . ,O). Putting these results together leads to the following theorem of Niederreiter: Theorem N. Let (Xn) be a linear congruential sequence (X0, a, c, m) of period length m, and let s be the least positive integer such that us = 1 (modulo m). Let ut be the t-dimensional accuracy of (XJ, as determined by the spectral test. Then the t-dimensional discrepancy DN(t) determined by the first N values of (Xn), as defined in (42)) satisfies D(t) = o d%k4hwV N N ) + O( mFJ)t) + O((logm)t rmax); (54) ( Dg = O((logm)t rmrtx), (55) Here rmax is the maximum value of the quantity T(u~, . . . , Ut) defined in (46), taken over all nonaero integer vectors (ul, . . . , Q) satisfying (15). Proof. The first two 0 terms in (54) come from vectors (ul, . . . , Ut) in (44) that do not satisfy (15), since exercise 25 proves that f(zll, . . . , Ut) summed over all (Ul,… , ut) is O(((~/YT) lnm)t) and exercise 26 bounds each g(ul, . . . , Ut). (These terms are missing from (55) since g(ul, . . . , ut) = 0 in that case.) The remaining 0 term in (54) and (55) comes from nonzero vectors (~1,. . . , ut) that do satisfy (15), using the bound derived in exercise 27. (By examining this proof carefully, we could replace each 0 in these formulas by an explicit function of t.) I Eq. (55) relates to the serial test in t dimensions over the entire period, while Eq. (54) gives us useful information about the distribution of the first N generated values when N is less than m, provided that N is not too small. Note that (54) will guarantee low discrepancy only when s is sufficiently large, otherwise the m/G term will dominate. If m = p: . . . pF7 and gcd(a - 1, m) = fl P, ***P, fr , then s equals ~Tl-~l. . . pFr–fr (cf. Lemma 3.2.1.2P); thus, the largest values of s correspond to high potency. In the common case m = 2e and a G 5 (modulo 
, we have s = am, so0:) is O(fi(logm)t+l/N)+O((logm)tr,,,). It is not difficult to prove that T,,, 2 a/z+ unless vt is very small (see exercise 29); therefore Eq. (54) says in particular that the discrepancy will be low in t dimensions if the spectral test is passed and if N is somewhat larger than Jm (log m)t+l. In a sense Theorem N is almost too strong, for the result in exercise 30 shows that linear congruential sequences like those in lines 8, 19, and 23 of Table 1 have a discrepancy of order (logm)2/m in two dimensions. The discrepancy