MySQL Web Server, Tomcat, Jsp, Struts Hosting Blog

4.6.3 ANSWERS TO EXERCISES 637 If we form Dirichlet generating functions g(z) = xnEA l/n , h(z) = xneB l/n*, then the product g(z)h(z) corresponds to the multiset product AB. 20. Type 3: (SO,. . . , S,) = (MOO,. . . , M,o) = ({0}, . . . , {A}, {A-l,A}, {A-l,A,A}, {A-l,A-l,A,A,A}, . . ., {A+C-3,A+C-3,A+C-2,A+C-2,A+C-2}). Type 5: (MOO,. , NO) = ({O), . , {A), {A -&A), . , {A + C -1,A + C}, {A+C-l,A+C-l,A+C}, . . . . {A+C+D-l,A+C+D-l,A+C+D}); (MOl,. ..,M,l) = (0, . . . . 0, 0, . ..f 0, {A + C -2}, . , {A + C + D -2}), S, = Mio u Mtl. 21. For example, let u. = 28qf5, x = (2(qf1)u -1)/(2 -1) = 24 + + 2 + 1, y = 2(qt ) + 1. Then zy = (22(qt1) -1)/(2 -1). If n = 24(qf1)u + xy, we have l(n) 5 4(q $ 1)~. f q + 2 by Theorem F, but l*(n) = 4(q + 1)~ + 2q + 2 by Theorem H. 22. Underline everything except the u -1 insertions used in the calculation of x. 23. Theorem G (everything underlined). 24. Use the numbers (B < -l)/(B -l), 0 5 i 5 r, underlined when a, is underlined; and c&- (B*3 -l)/(B -1) for 0 _< j < t, 0 < i 5 b3+1 -b3, 1 < k 5 1 (B), underlined when ck is underlined, where CO, cl, is a minimum length lbchain for B. To prove the second inequality, let B = 2m and use (3). (The second inequality is rarely, if ever, an improvement on Theorem G.) 25. We may assume that dk = 1. Use the rule R Ak--l . . . AI, where A3 = XR if d3 = 1, A3 = R otherwise, and where R means take the square root, x means multiply by Z. For example, if y = (.llOllOl)z, the rule is R R XR XR R XR XR. (There exist binary square-root extraction algorithms suitable for computer hardware, requiring an execution time comparable to that of division; computers with such hardware could therefore calculate more general fractional powers using the technique in this exercise.) 26. If we know the pair (Fk, Fk-l), then we have (Fk+i, Fk) = (Fk + Fk-i, Fk) and (Fzk,Fsk--1) = (F: + 2FkFk--l,F: + F:-1); so a binary method can be used to calculate (Fnr F,-I), using O(logn) arithmetic operations. Perhaps better is to use the pair of VdUeS (Fk, Lk), where Lk = Fk-i + Fk+l (cf. Section 4.5.4); then we have (Fk+l,Lk+l) = ($(Fk + Lk), #Fk + Lk)), (Fzk, Lzk) = (FkLk,Li -2(-l)k). For the general linear recurrence x n = alxn-l + . . . + adxn-d, we can compute xn in O(d3 log n) arithmetic operations by computing the nth power of an appropriate d x d matrix. [This observation is due to J. C. P. Miller and D. J. S. Brown, Comp. J. 9 (1966), 188-190.1 27. First form the 2m -m -1 products XI . . . x2, for all sequences of exponents such that 0 2 e3 _< 1 and el + . . . + e, 2 2. Let n3 = (d3x . . . djld30)2; to complete the calculation, take x$ . . x2>, then square and multiply by xf %. . . x&~~, for i = X - 1, 1, 0. [Straus showed in AMM 71 (1964), 807-808, that 2X(n) may be replaced by &)x( n )f or any E > 0, by generalizing this binary method to 2k-ary as in Theorem D. See exercise 39 for later developments.] 28. (a) x V y = x V y V (z + y), where V is logical or , cf. exercise 4.6.2-26; clearly v(x V y) 5 v(x V y) + Y(X A y) = V(X) + v(y). (b) Note first that A,-1/2dZ-1 c A,/2da for 1 2 i I: r. Secondly, note that d, = di-1 in a nondoubling; for otherwise at-l 2 2aj 2 a9 + ak = a,. Hence Aj C A,-1 and Ak c Ai-1/2~3-~~. (c) An easy induction on i, except that close steps need closer attention. Let us say that m has property P(o) if the l s in its binary representation all appear in consecutive

636 ANSWERS TO EXERCISES 4.6.3 18. Call f(m) a nice function if (logf(m))r & -+ 0 as m + 00. A polynomial in m is nice. The product of nice functions is nice. If g(m) -+ 0 and c is a positive constant, then Pgcrn) is nice; also ( m$m)) is nice, for by Stirling s approximation this is equivalent to saying that g(m)log(l/g(m)) + 0. Now replace each term of the summation by the maximum term that is attained for any s, t, V. The total number of terms is nice, and so are (T$), ( t ) 5 2t+ , and /3 , because (t -Jr- w)/m -+ 0. Finally, ((,zSja) 5 (2m)2t/t! < (4m2/t)tet, where (4e)t is nice; setting t to its maximum value (1 - f ~)m/X(m), we have the upper bound (myt) = (mx(m)/(l -+))t = 2m( -t 2) . f(m), where f(m) is nice. Hence the entire sum is less than cP for large m, if o = 21PV, 0 < 11 < 4~. 19. (a) A4 n N, A4 U N, M M N, respectively; see Eqs. 4.6.2-6, 4.5.2-7. (b) f(z)g(z), lcm(f(z),g(z)), gcd(f(z),g(z)). (For the same reasons as (a), be- cause the manic irreducible polynomials over the complex numbers are precisely the polynomials z -<.) (c) Commutative laws AHB = BuA, AIJB = BuA, AnB = BnA. Associative lawsA~(Bl&C) = (AuB)uC, Au(BuC) = (AuB)uC, An(BnC) = (AnB)nC. Distributive laws A u (I3 n C) = (A u B) n (A u C), An (B u C) = (An B) U (A n C), A u (B u C) = (A U B) U (A M C), A M (B n C) = (A M B) n (A l3 C). Idempotent lawsAUA=A,AnA=A. AbsorptionlawsAu(AnB)=A,An(AUB)=A, An(AwB)=A,Au(AkgB)=AkdB. Identityandzerolaws0~A=A,0UA=A, 0 n A = 0, where 0 is the empty multiset. Counting law A kb B = (A U B) kl (A fl B). Further properties analogous to those of sets come from the partial ordering defined bytheruleAcBiffAnB=A(iffAUB=B). Notes: Other common applications of multisets are zeros and poles of meromorphic functions, invariants of matrices in canonical form, invariants of finite Abelian groups, etc.; multisets can be useful in combinatorial counting arguments and in the develop- ment of measure theory. The terminal strings of a noncircular context-free grammar form a multiset that is a set if and only if the grammar is unambiguous. Although multisets appear frequently in mathematics, they often must be treated rather clum- sily because there is currently no standard way to treat sets with repeated elements. Several mathematicians have voiced their belief that the lack of adequate terminology and notation for this common concept has been a definite handicap to the development of mathematics. (A multiset is, of course, formally equivalent to a mapping from a set into the nonnegative integers, but this formal equivalence is of little or no practical value for creative mathematical reasoning.) The author has discussed this matter with many people in an attempt to find a good remedy. Some of the names suggested for the concept were list, bunch, bag, heap, sample, weighted set, collection; but these words either conflict with present terminology, have an improper connotation, or are too much of a mouthful to say and to write conveniently. It does not seem out of place to coin a new word for such an important concept, and multiset has been sug- gested by N. G. de Bruijn. The notation A u B has been selected by the author to avoid conflict with existing notations and to stress the analogy with set union. It would not be as desirable to use A + B for this purpose, since algebraists have found that A + B is a good notation for { cr + p 1 (^Y E A and p E B}. If A is a multiset of nonnegative integers, let G(z) = xnEA zn be a generating function corresponding to A. (Generating functions with nonnegative integer coefficients obviously correspond one-to-one with multisets of nonnegative integers.) If G(z) corresponds to A and H(z) to B, then G(z) + H(z) corresponds to A w B and G(z)H(z) corresponds to A + B.

4.6.3 ANSWERS TO EXERCISES 635 10. By using the FATHER representation discussed in Section 2.3.3: Make use of a table f[j], 1 5 j < 100, such that f[l] = 0 and f[j] is the number of the node just above j for j 2 2. (The fact that each node of this tree has degree at most two has no effect on the efficiency of this representation; it just makes the tree look prettier as an illustration.) 11. 1, 2, 3, 5, 10, 20, (23 or 40), 43; 1, 2, 4, 8, 9, 17, (26 or 34), 43; 1, 2, 4, 8, 9, 17, 34, (43 or 68), 77; 1, 2, 4, 5, 9, 18, 36, (41 or 72), 77. If either of the latter two paths were in the tree we would have no possibility for n = 43, since the tree must contain either 1, 2, 3, 5 or 1, 2, 4, 8, 9. 12. No such infinite tree can exist, since I(n) # 2*(n) for some n. 13. For Case 1, use a Type-l chain followed by ZAfC + 2B+C + 2A $ 2B; or use the factor method. For Case 2, use a Type-2 chain followed by 2AfC+1 + 2BfC + 2A + 2B. For Case 3, use a Type-5 chain followed by addition of 2A + 2A-1, or use the factor method. For Case 4, n = 135.2O, so we may use the factor method. 14. (a) It is easy to verify that steps r -1 and r -2 are not both small, so let us assume that step r-l is small and step r-2 is not. If c = 1, then x(a,-1) = X(a,-.k), so Ic = 2; and since 4 < ~(a,) = v(a?-l) + ~(a~-k) -1 5 ~(a,-1) + 1, we have ~(a,-~) 2 3, making T - 1 a star step (lest as, al, . . , ~~~-3, uTPl include only one small step). Then ~~-1 = u7-z + a +-4 for some q, and if we replace ~~-2, a,-~, a7 by a7--2, 2u7--2, 2a,-2 + ur-q = u7, we obtain another counterexample chain in which step r is small; but this is impossible. On the other hand, if c 2 2, then 4 5 ~(a,) 2 ~(a,-I) + v(u7-k) -2 5 ~(a,-I); hence v(u~-1) = 4, ~(a,+) = 2, and c = 2. This leads readily to an impossible situation by a consideration of the six types in the proof of Theorem B. (b) If X(u,-k) < m -1, we have c 2 3, so v(u?-k) + ~(a,-1) 2 7 by (22); therefore both v(u~-~) and ~(a,-1) are 2 3. AI1 small steps must be < r -k, and x(u,-,) = m -Ic + 1. If k 2 4, we must have c = 4, k = 4, v(u7.-r) = v(G-~) = 4; thus u,-~ 2 2m+2m-1+2m-2, and ~~-1 must equal 2 +2m- +2m-2+2 -3; but a7--4 2 $a,-1 now implies that ~~-1 = 8~~~4. Thus k = 3 and ~~~-1 > 2 +2 -l. Since u7–2 < 2 and ~~-3 < 2m-1, step r -1 must be a doubling; but step r -2 is a nondoubling, since u7-r # 4ur-s. Furthermore, since v(ur-s) 2 3, r -3 is a star step; and ur-2 = ur-s + a?-5 would imply that us-s = 27n-2, hence we must have aT-s = u7–3 + ~~~-4. As in a similar case treated in the text, the only possibility is now seen to be u7–4 = 2m-2 + 2m-3, ur–3 = 2m-2 + 2m-3 + 2df1 + 2d, ~~-1 = 2m + p–l+ 2d+2 + 2d+l, and even this possibility is impossible. 16. lB(n) = l(n) j- v(n) -1; so if n = 2k, I (n)/x(n) = 1, but if n = 2k+1 -1, l (n)/A(n) = 2. 17. Let ii < . < it. Delete any intervals I,+ that can be removed without affecting the union I1 U IJ It. (The interval (jk, ik] may be dropped out if either jk+l 5 jk or jl < j2 < . . . and jk+i 2 ik-1.) Now combine overlapping intervals (jl, ill, . , (j,, id] into an interval (j , i ] = (ji, id] and note that a,, < a,,(1 + 6)21-J1+ +zd-jd 5 u,,(l + 6)2@ + ), since each point of (j , i ] is covered at most twice in (j,, ii] u . . . u (jd, id].

634 ANSWERS TO EXERCISES 4.6.3 04 IH NUL X N-l rAXXmodw 05 SLAK5 N-l + rA. 06 2H DECI 1 N rI1 + rI1 -1. 07 JlP IB N Multiply again if rI1 > 0. 1 The running time for this program is 14N -7; it is faster than the previous program when n 5 7, slower when n 2 8. 3. The sequences of exponents are: (a) 1, 2, 3, 6, 7, 14, 15, 30, 60, 120, 121, 242, 243, 486, 487, 974, 975 [16 multiplications]; (b) 1, 2, 3, 4, 8, 12, 24, 36, 72, 108, 216, 324, 325, 650, 975 [14 multiplications]; (c) 1, 2, 3, 6, 12, 15, 30, 60, 120, 240, 243, 486, 972, 975 [13 multiplications]; (d) 1, 2, 3, 6, 12, 15, 30, 60, 75, 150, 300, 600, 900, 975 [13 multiplications]. [The smallest possible number of multiplications is 12; this is obtainable by combining the factor method with the binary method, since 975 = 15. (26 + l).] 4. (777777)s = 218 -1. 5. Tl. [Initialize.] Set LINKU[j] + 0 for 1 5 j 5 27, and set k + 0, LINKR[O] + 1, LINKR[l] t 0. T2. [Change level.] (Now level k of the tree has been linked together from left to right, starting at LINKR[O].) If k = r, the algorithm terminates. Otherwise set n + LINKR[O], m + 0. T3. [Prepare for n.] (Now n is a node on level Ic, and m points to the rightmost node currently on level k + 1.) Set o + 0, s + n. T4. [Already in tree?] (Now s is a node in the path from the root to n.) If LINKU[n + s] # 0, go to T6 (the value n + s is already in the tree). T5. [Insert below n.] If q = 0, set m + n + s. Then set LINKR[n + s] + q, LINKU[n + s] +- n, q + n + s. T6. [Move up.] Set s + LINKU[s]. If s # 0, return to T4. T7. [Attach group.] If q # 0, set LINKR[m] + q, m + m . T8. [Move n.] Set n + LINKR[n]. If n # 0, return to T3. T9. [End of level.] Set LINKR[m] + 0, k c k + 1, and return to T2. 1 6. Prove by induction that the path to the number 2e0 + 2e1 + + 2 t, if es > el > … > et 2 0, is 1, 2, 2 , . . . , 2e0, 2 +2 ,, . . , 2 +2e1+…+2et; furthermore, the sequences of exponents on each level are in decreasing lexicographic order. 7. The binary and factor methods require one more step to compute zzn than s ; the power tree method requires at most one more step. Hence (a) 15 . 2k; (b) 33 . 2k; (c) 23. 2k; k = 0, 1, 2, 3, . . . 8. The power tree always includes the node 2m at one level beloiv m, unless it occurs at the same level or an earlier level; and it always includes the node 2m + 1 at one level below 2m, unless it occurs at the same level or an earlier level. [It is not true that 2m is a son of m in the power tree for all m; the smallest example where this fails is m = 2138, which appears on level 15, while 4276 appears elsewhere on level 16. In fact, 2m sometimes occurs on the same level as m; the smallest example is m = 6029.1 9. Start with N + n, Z + x, and Yk +-1 for 1 2 k < m; in general we will have xn = YlYi.. YEZ, ZN. If N > 0, set k + N mod m, and if k # 0 set Yk + Yk . 2. Then set Z + Zm, N + [N/m], and repeat. Finally set Yk + Yk.Yk+r for k = m-2, m-3, . . . . 1; the answer is Yi Y,-1.

4.6.3 ANSWERS TO EXERCISES 633 field. The number of prime ideals of norm 5 2 is at most nzr/ different from the total number of linear factors of u modulo primes < x, since such linear factors correspond to ideals of norm p, while other prime ideals have norms >_ ps. Consequently if we let N(z) be the total number of linear factors of a given primitive polynomial u, modulo all primes < 2, then the GRH implies that there is an absolute constant AZ such that lN(z)/~(z)–rl < Asnz-l/ (ln z)(ln zA). A proof of GRH would yield a short proof of the number of irreducible factors of any primitive polynomial u over the integers, since we could evaluate N(z) for a value of 2 sufficiently large to make this error bound less than f . Unfortunately AZ is quite large. SECTION 4.6.3 1. xm, where m = ZXcn), the highest power of 2 less than or equal to n. 2. Assume that x is input in register A, and n in location NN; the output is in register X. 01 Al ENTX 1 1 Al. Initialize. 02 STX Y 1 Y +-1. 03 STA Z 1 z + 2. 04 LDA NN 1 N +- n. 05 JMP 2F 1 To A2. 06 5H SRB 1 L+ 1 -K 07 STA N L+l-K N t [N/21. 08 A5 LDA Z L A Square A5 2. 09 MULZ L 2 x Zmodw IO STX Z L –+ 2. II A2 LDA N L A2. Halve N. 12 2H JAE 5B LS1 To A5 if N is even. 13 SRB 1 K 14 A4 JAZ 4F K Jump if N = 1. 15 STA N K-l N t LN/ZJ. 16 A3 LDA Z K-l A3. Multiply Y by 2. 17 MULY K-l Z X Ymodw 18 STX Y K-l + Y. 19 JMP A5 K-l To A5. 20 4H LDA 2 1 21 MULY 1 Do the final multiplication. [It would be better programming practice to change the instruction in line 05 to “JAP”, followed by an error indication. The running time is 21L + 16K + 8, where L = x(n) is one less than the number of bits in the binary representation of n, and K = v(n) is the number of 1 bits in that representation.] For the serial program, we may assume that n is small enough to fit in an index register; otherwise serial exponentiation is out of the question. The following program leaves the output in register A: . 01 Sl LDl NN 1 rI1 + n. 0.2 STA X 1 x t 5. 03 JMP 2F 1

632 ANSWERS TO EXERCISES 4.6.2 36. Let V,(Z) be the value computed for uj(z) by the procedure of exercise 34. If deg(U1) + 2deg(Uz) +. . . = deg(u), then uj(s) = V,(Z) for all j. But in general we will havee

46.2 ANSWERS TO EXERCISES 631 g(x) # f(x) then both f(x) and g(z) are distinct factors of !&m(z), hence they are distinct factors of xn -1, hence they have no irreducible factors in common modulo p. However, cp is a root of f(sp), so gcd(g(z), f(zP)) # 1 over the integers, hence g(z) is a divisor of f(zP). By (5), g(z) is a divisor of f(~)~, modulo p, contradicting the assumption that f(x) and g(x) have no irreducible factors in common. Therefore f(x) = g(z). [The irreducibility of Q%(Z) was first proved for prime n by K. F. Gauss in Disquisitiones Arithmeticie (Leipzig, 1801), Art. 341, and for general n by L. Kronecker, J. de Math. Pures et Applique es 19 (1854), 177-192.1 (c) *I(Z) = z -1; and when p is prime, wp(x) = 1 + 5 + + xp- . If n > 1 is odd, it is not difficult to prove that @am = Q&-z). If p divides n, the second identity in (a) shows that Qpn(x) = kn(zp). If p does not divide n, we have Qppn(z) = Iln(~~)/Iln(~). For nonprime n 2 15 we have @a(z) = x2 f 1, Qs(s) = x2 -z + 1, S(x) = x4 + 1, %(3(x) = x6 + Z3 + 1, %0(Z) = x4 -x3 + x2 -Z + 1, &(x) = x4 -x2 + 1, I114(5) = xs -x5 + x4 -2s + x2 -Z + 1, @15(x) = 2s -x7 + x5 - x4 + x3 -z + 1. [The formula lag(x) = (1 f xp +. . . + x(~- )~)(z -1)/(x4 -1) can be used to show that kpq(z) has all coefficients +l or 0 when p and q are prime; but the coefficients of $, ppr(~) can be arbitrarily large.] 33. False; we lose all p, with ej divisible by p. True if p 2 deg(zl). [See exercise 36.1 34. [D. Y. Y. Yun, Proc. ACM Symp. Symbolic and Algebraic Comp. (1976), 26-35.1 Set (t(x), ~1 (xl, WI(X)) + GCD(u(x),d(x)). If t(x) = 1, set e + 1; otherwise set (udx), vt+1(x), m+1(x)) +-GCD(vi(x),wi(x) -w:(x)) for i = 1, 2, . . . , e -1, until finding we(x) -v:(x) = 0. Finally set U,(Z) t V,(Z). To prove the validity of this algorithm, we observe that it computes the polyno- mials t(x) = u2(x)us(x)2u4(x)3.. , vi(x) = ui(x)ui+l(x)ui+2(x). . . , and W%(X) = ul(s)u~+l(z)uz+2(x)~~~ + 2u~(x)ul+l(x)ui+2(x)~~~ + ~G(X)G+I(X)~+&). . + . . . . We have gcd(t(x), WI(X)) = 1, since an irreducible factor of U%(X) divides all but the ith term of WI(X), and it is relatively prime to that term. Furthermore gcd(u%(x), 21,+1(x)) is clearly 1. [Exercise 2(b) indicates that comparatively few polynomials are squarefree, but non-squarefree polynomials actually occur often in practice; hence this method turns out to be quite important. See Paul S. Wang and Barry M. Trager, SIAM .J. Computing 8 (1979), 300-305, for suggestions on how to improve the efficiency when the given polynomial is already squarefree.] 35. We have wj(x) = gcd(uj(x), V;(X)) . gcd($+l(x), w,(x)), where 21;(x) = uj(x)uj+l(x). . . and w,*(x) = wj(x)w,+l(x). . [Yun notes that the running time for squarefree factorization by the method of exercise 34 is at most about twice the running time to calculate gcd(u(x), U (X)). Furthermore if we are given an arbitrary method for discovering squarefree factorization, the method of this exercise leads to a gcd procedure. (When U(X) and w(x) are squarefree, their gcd is simply wz(x) where w(x) = U(X)W(X) = w~(x)wz(x)~; the polynomials Us, wJ(x), %F(x), and wj(x) are all squarefree.) Hence the problem of converting a primitive polynomial of degree n to its squarefree representation is computationally equivalent to the problem of calculating the gcd of two nth degree polynomials, in the sense of asymptotic worst-case running time.]

630 ANSWERS TO EXERCISES 46.2 trie with r lieves (cf. Section 6.3). The cost associated with an internal node of this trie, having m lieves as descendants, is O(m2(logp)); and the solution to the recurrence A, = (;)+2l-” c(;)Ak is A, = 2(T), by exercise 5.2.2-36. Hence the sum of costs in the given random trie-representing the expected time to factor g(s) completely- is O(r2(logp)3) under this plausible assumption. The plausible assumption becomes rigorously true if we choose t(z) at random of degree < rd instead of restricting it to degree < 2d. 30. Let T(z) = z+z~+…+z~~- and W(Z) = T(t(z))modq(z). Since tag = t(s) in the field of polynomial remainders modulo q(z), we have ~(5)~ = W(Z) in that field; in other words, W(Z) is one of the p roots of the equation yp - y = 0. Hence V(X) is an integer. It follows that &

4.6.2 ANSWERS TO EXERCISES 629 smallest prime that is not unlucky is at most O(n log Nn), if n = deg(u) and N bounds the coefficients of U(X).] 24. Multiply a manic polynomial with rational coefficients by a suitable nonzero integer, to get a primitive polynomial over the integers. Factor this polynomial over the integers, and then convert the factors back to manic. (No factorizations are lost in this way; see exercise 4.6.1-8.) 25. Consideration of the constant term shows there are no factors of degree 1, so if the polynomial is reducible, it must have one factor of degree 2 and one of degree 3. Modulo 2 the factors are ~(5 f 1) (x2 + x + 1); this is not much help. Modulo 3 the factors are (5 + 2)2(~3 + 2x f 2). Modulo 5 they are (x2 + x + 1)(z3 + 4x + 2). So we see that the answer is (x2 + x + 1)(x3 -x $2). 26. Begin with D + (0 . . . Ol), representing the set (0). Then for 1 5 j 5 r, set D + D V (D 7 dj), where V denotes logical or and D 7 d denotes D shifted left d bit positions. (Actually we need only work with a bit vector of length [(n + 1)/2], since n -m is in the set iff m is.) 27. Exercise 4 says that a random polynomial of degree n is irreducible modulo p with rather low probability, about l/n. But the Chinese remainder theorem implies that a random manic polynomial of degree n over the integers will be reducible with respect to each of Ic distinct primes with probability about (1 - l/n)k, and this approaches zero as k + co. Hence almost all polynomials over the integers are irreducible with respect to infinitely many primes; and almost all primitive polynomials over the integers are irreducible. [Another proof has been given by W. S. Brown, AMM 70 (1963), 965-969. See also the generalization cited in the answer to exercise 36.1 28. Cf. exercise 4; the probability is the coefficient of zn in (l+al,z/p)(l+a2,z2/p2) X (lfaa,z3/p3). . , which has the limiting value g(z) = (1 + z)(l + $z2)(1 $ 4~ ). . . . For 1 5 n 5 10 the answers are 1, 3, 8, A, $&, a, #, #&, H, $$i#. [Let f(y) = ln(1 + y) -y = O(y2). We have g(z) = exp(& 1 znln + En2 1 W/n)) = h(z)l(l -Zh and it can be shown that the limiting probability is h(1) = exp(xn,r f(l/n)) = e–1 M .56146 as n -+ co; cf. D. H. Lehmer, Acta Arith. 21 (1972) 3791388. Indeed, N. G. de Bruijn has established the asymptotic formula lim,,, anp = eer +e- /n+ O(nb2 log n).] 29. Let ql(z) and q2(x) be any two of the irreducible divisors of g(x). By the Chinese remainder theorem (exercise 3), choosing a random polynomial t(x) of degree < 2d is equivalent to choosing two random polynomials ti(z) and tz(x) of degrees < d, where ti(x) = t(x)modqi(x). The gcd will be a proper factor if ti(~)(~~-l)/~ modqi(x) = 1 and tz(~)(~~- )/~ modqr(x) # 1, or vice versa, and this condition holds for exactly 2((pd -1)/2)((# + 1)/2) = (p2d - 1)/2 choices of ti(x) and tz(x). Notes: We are considering here only the behavior with respect to two irreducible factors, but the true behavior is probably much better. Suppose that each irreducible factor q%(x) has probability f of dividing t(~)(~~- )/~ -1 for each t(x), independent of the behavior for other qj(x) and t(x); and assume that g(x) has r irreducible factors in all. Then if we encode each qi(x) by a sequence of O s and l s according as qi(x) does or doesn t divide t(x)(pd- )/2 -1 for the successive t s tried, we obtain a random binary

628 ANSWERS TO EXERCISES 4.6.2 is equivalent to $s)v(z) + O(Z)W(Z) = f(s) (modulo T), where f(z) satisfies u(z) E W(Z)WJ(Z) + qf(s) (modulo qr). We have (4xMx) + t(xMx))~(x) + @(XV(X) -t(xb(x)h(x) = f(x) (module ~1 for all t(z). Since e(w) has an inverse modulo r, we can find a quotient t(x) by Algorithm 4.6.1D such that deg(bf–tw) < deg(w); for this t(s), deg(af+tw) 5 deg(w), since we have deg(f) 5 deg(u) = deg(w) + deg(w). Thus the desired solution is V(z) = b(x)f(x) -t(z)w(z) = b(z)f(z)modw(z), ti(z) = a(x)f(x) + t(z)w(z). If (a(z), G(x)) is another solution, we have (a(s) -G(z))w(z) G (b(z) -V(~))W(X) (modulo r). Thus if r is prime, w(x) must divide a(z) -U(s); but deg(z -E) < deg(w), so a(z) = $2) and G(x) = e(x). For p = 2, the factorization proceeds as follows (writing only the coefficients, and using bars for negative digits): Exercise 10 says that WI(X) = (11 l), WI(X) = (TiiO Oii) in one-bit two s complement notation. Euclid s extended algorithm yields a(z) = (10 0 0 0 l), b(s) = (10). The factor w(x) = x2 + clz + CO must have /cl 1 5 11 + a1 = 11, IcoJ 5 10, by exercise 20. Three applications of Hensel s lemma yield wd(z) = (13i), WJ(Z) = (1354435). Thus cl G 3 and CO = -1 (modulo 16); the only possible quadratic factor of U(X) is x2 + 32 -1. Division fails, so U(X) is irreducible. (Since we have now proved the irreducibility of this beloved polynomial by four separate methods, it is unlikely that it has any factors.) Hans Zassenhaus has observed that we can often speed up such calculations by increasing p as well as q: In the above notation, we can find A(x), B(x) such that A(z)V(z)+B(s)W(cc) = 1 ( mo d u 1o p r ), namely by taking A(x) = a(x)+pT~(s), B(z) = b(s) + p6(x), where Z(x)V(z) + 6(x)W(x) G g(x) (modulo r), a(x)V(z) + b(x)W(x) = 1 -pg(x) (modulo pr). We can also find C with C(V)C = 1 (modulo pr). In this way we can lift a squarefree factorization U(X) = w(x)w(x) (modulo p) to its unique extensions modulo p2, p4, ps, p16, etc. However, this accelerated procedure reaches a point of diminishing returns in practice, as soon as we get to double-precision moduli, since the time for multiplying multiprecision numbers in practical ranges outweighs the advantage of squaring the modulus directly. From a computational standpoint it seems best to work with the successive moduli p, p2, p4, p , . , pE, pE+ , pE+2e, pE+3e, …, where E is the smallest power of 2 with p* greater than single precision and e is the largest integer such that p has single precision. Hensel s lemma, which K. Hensel introduced in order to demonstrate the fac- torization of polynomials over the field of p-adic numbers (see exercise 4.1-31) can be generalized in several ways. First, if there are more factors, say U(X) = wi(x)wz(x)ws(x) (modulo p), we can find al(x), as(z), as(z) such that a~(x)wz(~)ws(2)+a~(z)vi(x)ws(x)+ as(x)wr(s)w2(x) = 1 (modulo p) and deg(a,) < deg(w,). (In essence, l/u(z) is expanded in partial fractions as C ai(z)/w,(z).) An exactly analogous construction now allows us to lift the factorization without changing the leading coefficients of wi and ~2; we take al(x) = al(x)f(s) mod wl(x), &(x) = az(s)f(x) mod wz(x), etc. Another important generalization is to several simultaneous moduli, of the respective forms pe, (x2 –a~)~~, . . . . (xt -f&y, when performing multivariate gcds and factorizations. Cf. D. Y. Y. Yun, Ph.D. Thesis (M.I.T., 1974). 23. The discriminant of pp(u(x)) is a nonzero integer (cf. exercise 4.6.1-12), and there are multiple factors modulo p iff p divides the discriminant. [The factorization of (22) modulo 3 is (x + 1)(x -5 -1)2(x3 +x2 -z + 1); squared factors for this polynomial occur only for p = 3, 23, 233, and 121702457. It is not difficult to prove that the