112 RANDOM NUMBERS 3.3.4 13. [HM,%!] Lemma A (Free web host)
112 RANDOM NUMBERS 3.3.4 13. [HM,%!] Lemma A uses the fact that U is nonsingular to prove that a positive definite quadratic form attains a definite, nonzero minimum value at nonzero integer points. Show that this hypothesis is necessary, by exhibiting a quadratic form (19) whose matrix of coefficients is singular, and for which the values of f(z~, . . . , Q) get arbitrarily near zero (but never reach it) at nonzero integer points (~1,. . . , Q). 14. [24] Perform Algorithm S by hand, for m = 100, a = 41, T = 3. b 15. [MZO] Let U be an integer vector satisfying (15). How many of the (t -l)- dimensional hyperplanes defined by U intersect the unit hypercube { (~1,. . . ,z,) ] 0 2 xj < 1 for 1 2 j 5 t }? (This is approximately the number of hyperplanes in the family that will suffice to cover LO.) 16. [MAO] (U. Dieter.) Show how to modify Algorithm S in order to calculate the minimum number A$ of parallel hyperplanes intersecting the unit hypercube as in exercise 15, over all U satisfying (15). [Hint: What are appropriate analogs to positive definite quadratic forms and to Lemma A?] 17. [ZO] Modify Algorithm S so that, in addition to computing the quantities vt, it outputs all integer vectors (~1,. . . , it) satisfying (15) such that u: + + . e + ZL~ = Y:, for 2 5 t 5 T. 18. [M30] (a) Let m = 2e, where e is even. By considering combinatorial matrices, i.e., matrices whose elements have the form y + x&j (cf. exercise 1.2.3-39), find 3 X 3 matrices of integers U and V satisfying (29) such that the transformation of step S5 does nothing for any j, but the corresponding values of zk in (31) are so huge that exhaustive search is out of the question. (The matrix U need not satisfy (28), we are interested here in arbitrary positive definite quadratic forms of determinant m.) (b) Although transformation (23) is of no use for the matrices constructed in (a), find another transformation that does produce a substantial reduction. F 19. [HMZ5] Suppose step S5 were changed slightly, so that a transformation with q = 1 would be performed when 2V,. q = I$ e V,. (Thus, q = [(vi. I,$ / I$. V,) + $1 in all cases.) Would it be possible for Algorithm S to get into an infinite loop? 20. [M21] Discuss how to carry out an appropriate spectral test for linear congruential sequences having c = 0, X0 odd, m = 2e, a mod 8 = 5. 21. [M80] (R. W. Gosper.) A certain application uses random numbers in batches of four, but throws away the second of each set. How can we study the grid structure of {&(X4% X4n+2, Xdn+s)}, given a linear congruential generator of period m = 2e? 22. [M46] What is the best upper bound on ps, given that ~2 is very near its maxi- mum value &?T? What is the best upper bound on ~2, given that ~3 is very near its maximum value +rfi? 23. [M46] Let U,, Vj be vectors of real numbers with Vi . Vj = &j for 1 5 i,j 5 t, and such that Ui . Ui = 1, 2]Uz . Ujl 5 1, 21Vz +l.$ < Vj . Vj for i # j. HOW large can !JI . VI be? (This question relates to the bounds in step S8, if both (23) and the transformation of exercise 18(b) fail to make any reductions. The maximum value known to be achievable is (n + 2)/3, which occurs when VI = II, Uj = $11 + &&Ij, Vl = I1 -(12 + * * . + In)/& Vj = 2Ij/fi, for 2 2 j 5 n, where (II,. . . , In) is the identity matrix; this construction is due to B. V. Alekseev [Matematicheskie Zametki, to appear] .)