Web site management - 3.3.4 THE SPECTRAL TEST 113 b 24. [M.28]
3.3.4 THE SPECTRAL TEST 113 b 24. [M.28] Generalize the spectral test to second-order sequences of the form X, = (ax,-1 + bX,-z)modp, having period length p2 -1. (Cf. Eq. 3.2.2-8.) How should Algorithm S be modified? 25. [HA&24] Let d be a divisor of m and let 0 5 9 < d. Prove that c r(k), summed over all 0 5 k < m such that Icmodd = 9, is at most (2/dr)ln(m/d) + O(1). (Here r(k) is defined in Eq. (46) when t = 1.) 26. [A&?$ Explain why the derivation of (53) leads to a similar bound on N-l for 0 < 9 < m. Where does the derivation of (53) break down when m = l? 27. [HA4391 (E. Hlawka, H. Niederreiter.) Let r(ui, . , urn) be the function defined in (46). Prove that c T(u~, . . . , it), summed over all 0 5 ~1,. , it < m such that (~1,. . . ,~t) # (0,. . ,O) and (15) holds, is 0((27rlgm)t ~~~~~~ where rmax is the maximum term ~(2~1,. . . , it) in the sum. b 28. [M.28] (H. Niederreiter.) Find an analog of Theorem N for the case m = prime, c = 0, a = primitive root modulo m, X0 $ 0 (modulo m). [Hint: Your exponential sums should involve 5 = e2Ti (m-1) as well as w.] Prove that in this case the average primitive root has discrepancy 0:)-r = O(t(log m) /#(m -l)), hence good primitive roots exist for all m. 29. [A& 11 Prove that quantity rmax of exercise 27 is never larger than &?/ut, unless UT 5 2(t -1). 30. [A4331 (S. K. Zaremba.) Prove that in two dimensions, rmax 5 m/max(al,. . . , a,), whereal,…, a, are the partial quotients obtained when Euclid s algorithm is applied to m and a. [Hint: We have a/m = /al,. , a,/ in the notation of Section 4.5.3; apply ex- ercise 4.5.3-42.1 31. [HM47] (I. Borosh.) Prove that for all sufficiently large m there exists a number a relatively prime to m such that all partial quotients of u/m are 2 3. Furthermore the set of all m satisfying this condition but with all partial quotients 5 2 has positive density.