3.3.4 THE SPECTRAL TEST 111 what happens when t = l?) 2. [Hi%?0] Let VI, , Vt be linearly independent vectors in t-space, let LO be the lattice of points defined by (lo), and let Vi, . . . , Ut be defined by (19). Prove that the maximum distance between (t -1)-dimensional hyperplanes, over all families of parallel hyperplanes that cover LO, is l/min{ f(zi, . . , Q) 1 (xi,. . , Q) # (0,. . . ,O)}, where f is defined in (17). 3. [M24] Determine ~3 and ~4 for all linear congruential generators of potency 2 and period length m. b 4. [ME?] Let ~11, ~12, usi, ~2s be elements of a 2 X 2 integer matrix such that ~11 $ a~12 = ~21 + ~2~22 E 0 (modulo m) and ~112122 -~21~12 = m. (a) Prove that all integer solutions (yi, 92) to the congruence y1 + ay2 E 0 (modulo m) have the form (~1,~s) = (51~11+222~21,51 (~12+222~22) for integer xl, 22. (b) If, in addition, 2~~11~214-~121122) 5 u~,+u& 5 u;,+&, prove that (yi, ys) = (~11, ~12) minimizes y: + yi over all nonzero solutions to the congruence. 5. [A4301 Prove that steps Sl through S3 of Algorithm S correctly perform the spectral test in two dimensions. [Hint: See exercise 4, and prove that (h + h)2 + (p + p) 2 h2 + p2 at the beginning of step S2.1 6. [A&N] Let ac, al, . . , at-1 be the partial quotients of a/m as defined in Section 3.3.3, and let A = rnaxc13 27r/(A + 1 + l/A). 7. [HiME??] Prove that question (a) and question (b) of the text have the same solution for real values of 41, . . . , q3-r, q3fl, . . , qt (cf. (24), (26)). 8. [AR61 Line 18 of Table 1 has a very low value of ~2, yet ~3 is quite satisfactory. What is the highest possible value of ~3 when ~2 = lo@ and m = lOlo? 9. [Hi!&%] (C. Hermite, 1846.) Let f(zi,. , xt) be a positive definite quadratic form, defined by the matrix U as in (17), and let 0 be the minimum value of f at nonzero integer points. Prove that ~9 5 ( $)(t-1)/2 1 det U12/t. [Hints: If W is any integer matrix of determinant 1, the matrix WU defines a form equivalent to f; and if S is any orthogonal matrix (i.e., S- = ST ), t he matrix US defines a form identically equal to f. Show that there is an equivalent form g whose minimum 9 occurs at (l,O, . ,O). Then prove the general result by induction on t, writing g(xi, . , xt) = B(XlfP2~2 +. . . + Ptxt) + h(x2,. . . , xt) where h is a positive definite quadratic form in t -1 variables.] 10. [M.28] Let (yi, ~2) be relatively prime integers such that yl +ay2 E 0 (modulo m) and Y: -I-Y; < m m. Show that there exist integers (Us, ~2) such that u1 +au2 F 0 (module m), 211~2-212~1 = m, 21~1~1 +UZYZ~ 5 min(zl:-t&, y:-l-&, and (UT + U$X (Y: + ~2) 2 m2. (Hence by exercise 4, V; = min(uf +u;, y:+yi).) b 11. [HM30] (Alan G. Waterman, 1974.) Invent a reasonably efficient procedure that computes multipliers a E 1 (modulo 4) for which there exists a relatively prime solution to the congruence yl + ay2 E 0 (modulo m) with y: + yz = mm-e, where E > 0 is as small as possible, given m = 2 . (By exercise 10, this choice of a will guarantee that ~2 2 m /(y: + yi) > m m, and there is a chance that ui will be near its optimum value mm. In practice we will compute several such multipliers having small c, choosing the one with best spectral values ~2, ~3, . . . .) 12. [HM.ZS] Prove, without geometrical handwaving, that any solution to the text s question (b) must also satisfy the set of equations (26).
This entry was posted
on Tuesday, February 26th, 2008 at 10:11 pm and is filed under Coldfusion.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.