544 ANSWERS TO EXERCISES (Web hosting provider) 3.3.4 Without loss of
544 ANSWERS TO EXERCISES 3.3.4 Without loss of generality, assume that f = g. Tf now S is any orthogonal matrix, the matrix US defines the same form as U, since (XUS)(XUS)T = (XU)(XU)T. Choosing S so that its first column is a multiple of VI and its other columns are any suitable vectors, we have for some ~1, ~2, . . . , crt and some (t -1) X (t -1) matrix U . Hence f(zl, . . . , zt) = (~1×1 + . . + a,~,) + h(zz,. ,z,). It follows that cy1 = fi [in fact, QI~ = (VI . Uj)/Je for 1 5 j 5 t], and that h is a positive definite quadratic form defined by U , where det U = (det U)/&. By induction on t, there are integers (~2,. . . , Q) with h(xz,. . . , xt) 5 (4) - / I detU12/(t- )/e /(t-1), and for these integer values we can choose x1 so that 1×1 + (~2×2 + … + a~tzt)/a~11 5 4, i.e., ((~1~1 + … + a,~,) 5 46 . Hence 0 2 f(xl, . . . ,x,) 2 $0 + (j)( - )/ 1 det U12/(t- )/81/(t- ) and the desired inequality follows immediately. [Note: For t = 2 the result is best possible. For general t, Hermite s theorem implies that pUt < ,t 2(4/3)t(t-1) 4/(t/2)!. A fundamental theorem due to Minkowski - ( Every t-dimensional convex set symmetric about the origin with volume 2 2t contains a nonzero integer point ) gives pt 2 2t; this is stronger than Hermite s theorem for t 2 9. Even stronger results are known, cf. (41).] 10. Since yl and yz are relatively prime, we can solve zllyz - 1~2~1 = m; furthermore (2~1 + qyl)y~ -(~2 + 4yz)yl = m for all 4, so we can ensure that 212~1~1 + 2~2~21 2 yf + yi by choosing an appropriate integer 4. Now y~(u1 f ~212) = ~22~1 - yluz = 0 (modulo m), and yz must be relatively prime to m, hence ZL~ + au2 = 0. Finally let lulyl + UZYZ~ = cum, u: + ZL~ = pm, y: + yz = ym; we have 0 5 QI 2 $7, and it remains to be shown that Q 2 $p and ,@ 2 1. The identity (2~1~2 -212~1) + (%Yl + u2Y2)2 = (4 +,4(Y: + YE2 im Pl ies that 1 + ~1 = /3r. If QI > a/3, we have 2ay > 1+ cy2, i.e., y -dm < 0: 5 %r. But $7 < dm implies that y2 > 4, a contradiction. 11. Since a is odd, y1 +yz must be even. To avoid solutions with yl and y2 both even, let y1 = ~1 +x2, y2 = x1-22, and solve x:+x; = m/&–E, with (~1, x2) relatively prime and x1 even; the corresponding multiplier a will be the solution to (x2 -x,)a = 52 + x1 (modulo 2e). It is not difficult to prove that a = 1 (modulo 2k-t1) iff x1 = 0 (modulo 2k), so we get the best potency when x1 mod4 = 2. The problem reduces to finding relatively prime solutions to XT + xi = N where N is a large integer of the form 41c $1. By factoring N over the Gaussian integers, we can see that solutions exist if and only if each prime factor of N (over the usual integers) has the form 41c + 1. According to a famous theorem of Fermat, every prime p of the form 4k + 1 can be written p = u2 + 21 = (u + iv)(u -iv), v even, in a unique way except for the signs of u and V. The numbers u and v can be calculated efficiently by solving x2 = -1 (modulo p), then calculating u + iv = gcd(z + i, p) by Euclid s algorithm over the Gaussian integers. [We can take x = n(p-1)/4 modp for almost half of all integers n. This application of a Euclidean algorithm is essentially the same as finding the least nonzero u2 + 21 such that u * XV = 0 (modulo p).] If the prime factorization of N is p; . . . p: = (ul + it~~)~l(u~ -i~)~ . . . (u? + ~w~)~ (u~ -iw,)+, we get 2 - distinct solutions to xf + xi = N, gcd(xl, x2) = 1, x1 even, by letting ~XZ[ f ilxl = (u, + iwp(UZ &-i2rp.. (u, f iw7)ev; and all such solutions are obtained in this way.