Web host 4 life - 3.3.4 THE SPECTRAL TEST 105 in dimensions 2
3.3.4 THE SPECTRAL TEST 105 in dimensions 2 through 5, partly because it is easy to remember. Line 27 uses a random primitive root, modulo the prime 231 - 1, as multiplier. Line 28 is for the sequence X, = (271828183X,-1 -314159269X,-z) mod (231 -I), (39) which can be shown to have period length (231 -1)2 -1; it has been analyzed with the generalized spectral test of exercise 24. Theoretical upper bounds on pt, which can never be transcended for any m, are shown just below Table 1; it is known that every lattice with m points per unit volume has vt i 7t milt, (40) where yt takes the respective values (4/3) , 2l 7 2114, 23 1o, (64/3)1 12, 23/7, 2112 (41) for t = 2, . . . , 8. (See exercise 9 and J. W. S. Cassels, Inntroduction to the Geometry of Numbers (Berlin: Springer, 1959), p. 332.) These bounds hold for lattices generated by vectors with arbitrary real coordinates. For example, the optimum lattice for t = 2 is hexagonal, and it is generated by vectors of length 2/G that form two sides of an equilateral triangle. In three dimensions the optimum lattice is generated by vectors VI, V,, V3 that can be rotated into the form (w, ZI, -v), (w, -v,v), (-w, w, w), where w = l/a. *F. Relation to the serial test. In a series of important papers published during the 19 7Os, Harald Niederreiter has shown how to analyze the distribution of the t-dimensional vectors (1) by means of exponential sums. One of the main consequences of his theory is that the serial test in several dimensions will be passed by any generator that passes the spectral test, even when we consider only a sufficiently large part of the period instead of the whole period. We shall now turn briefly to a study of his interesting methods, in the case of linear congruential sequences (X0, a, c, m) of period length m. The first idea we need is the notion of discrepancy in t dimensions, a quantity that we shall define as the difference between the expected number and the actual number of t-dimensional vectors (z,, z,+~, . . . , s,ttYl) falling into a hyper- rectangular region, maximized over all such regions. To be precise, let (z,) be a sequence of integers in the range 0 5 x, < m. We define number of (x,, . . . , x,+t-l) in R for 0 5 n < N volume of R Djj) = max R N mt (42) where R ranges over all sets of points of the form R = { (Yl, * * * , Yt) I QIl I Yl < Pl, . . . , Qt I Yt < Pt >; (43) here cyj and & are integers in the range 0 5 CZ~ < pj 5 m, for 1 5 j 5 t. The volume of R is clearly (pl -ol). . . (& -at). To get the discrepancy DE , we imagine looking at all these sets R and finding the one with the greatest excess or deficiency of points (x,, . . . , Z,+t–l).