Topics in descriptive set theory related to number theory and analysis Citation Ki, Haseo (1995) Topics in descriptive set theory related to number theory and analysis. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/SQV8-S991. https://resolver.caltech.edu/CaltechETD:etd-10112007-111738 Abstract Based on the point of view of descriptive set theory, we have investigated several definable sets from number theory and analysis. In Chapter 1 we solve two problems due to Kechris about sets arising in number theory, provide an example of a somewhat natural D 2 Π 0 3 set, and exhibit an exact relationship between the Borel class of a nonempty subset X of the unit interval and the class of subsets of N whose densities lie in X. In Chapter 2 we study the A, S, T and U-sets from Mahler's classification of complex numbers. We are able to prove that U and T are Σ 0 3 -complete and Π 0 3 -complete respectively. In particular, U provides a rare example of a natural Σ 0 3 -complete set. In Chapter 3 we solve a question due to Kechris about UCF, the set of all continuous functions, on the unit circle, with Fourier series uniformly convergent. We further show that any Σ 0 3 set, which contains UCF, must contain a continuous function with Fourier series divergent. In Chapter 4 we use techniques from number theory and the theory of Borel equivalence relations to provide a class of complete Π 1 1 sets. Finally, in Chapter 5, we solve a problem due to Ajtai and Kechris. For each differentiable function f on the unit circle, the Kechris-Woodin rank measures the failure of continuity of the derivative function f', while the Zalcwasser rank measures how close the Fourier series of f is to being a uniformly convergent series. We show that the Kechris-Woodin rank is finer than the Zalcwasser rank. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: Mathematics ; Set theory Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Kechris, Alexander S. Thesis Committee: Unknown, Unknown Defense Date: 15 March 1995 Non-Caltech Author Email: haseo (AT) yonsei.ac.kr Funders: Funding Agency Grant Number NSF DMS- 9020153 NSF DMS-9317509 Record Number: CaltechETD:etd-10112007-111738 Persistent URL: https://resolver.caltech.edu/CaltechETD:etd-10112007-111738 DOI: 10.7907/SQV8-S991 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 4040 Collection: CaltechTHESIS Deposited By: Imported from ETD-db Deposited On: 12 Oct 2007 Last Modified: 21 Dec 2019 02:51 Thesis Files Preview PDF - Final Version See Usage Policy. 2MB Repository Staff Only: item control page

Topics In Descriptive Set Theory Related To Number Theory and Analysis Thesis by Haseo Ki In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Thecnology Pasadena, California 1995 (Submitted March 15, 1995) Acknowledgement I thank the many people who have made this dissertation possible. I extend heartfelt thanks to my advisor Alexander Kechris for his inspiration and guidance over the past several years. His continual help, encouragement, and vast supply of knowledge were indispensable to the completion of this work. I would like to thank Achim Ditzen, Greg Hjorth, Xuhua Li, and Slawomir Solecki whose encouragement, advice and friendship have continued to make my math career easier. A special thanks to my friend Tom Linton, who helped me in many ways and allowed me to include a joint work in my thesis. Finally, I would like to thank Caltech's Mathematics Department and the National Science Foundation (NSF Grants DMS9020153 and DMS-9317509) for the finacial support they provided. 11 Contents 0 Introduction 1 1 Normal numbers and subsets of N with given densities ............... .4 1.1 Introduction ............................................................... 4 1. 2 Notation and background information ...................................... 5 1.3 Subsets of N with given densities ........................................... 8 1.4 Two methods for producing subsets with nice densities ..................... 9 1.5 Some Il~-complete sets ................................................... 11 1.6 Normal numbers .......................................................... 12 1. 7 The Borel classes of D x .................................................. 13 2 The Borel classes of Mahler's A, S, T and U-numbers 23 2.1 Introduction .............................................................. 23 2.2 Definitions and background ............................................... 24 2.3 Results ................................................................... 25 3 On the set of all continuous functions with uniformly convergent Fourier series 32 3.1 Introduction .............................. ." ............................... 32 3.2 Definitions and background ............................................... 32 3.3 Results ................................................................... 34 41 4 Complete coanalytic sets 111 4.1 Introduction .............................................................. 41 4.2 Notations and background ................................................ 42 4.3 The set of all universal sequences of real numbers ......................... 43 4.4 The sets arising countable Borel equivalence relations ..................... 51 5 The Kechris-Woodin rank is finer than Zalcwasser rank 59 5.1 Introduction ........................................................ , ..... 59 5.2 Definitions and background ............................................... 60 5.3 The Kechris-Woodin rank ................................................. 61 5.4 The Zalcwasser rank ...................................................... 62 5.5 An equivalent definition of the Zalcwasser rank ............................ 64 5.6 The Kechris-Woodin rank is finer than the Zalcwasser rank ................ 66 5. 7 The Denjoy rank and remark ............................................. 68 70 References lV Abstract Based on the point of view of descriptive set theory, we have investigated several definable sets from number theory and analysis. In Chapter 1 we solve two problems due to Kechris about sets arising in number theory, provide an example of a somewhat natural 1'2 (11~) set, and exhibit an exact relationship between the Borel class of a nonempty subset X of the unit interval and the class of subsets of N whose densities lie in X. In Chapter 2 we study the A, S, T and U-sets from Mahler's classification of complex numbers. We are able to prove that U and T are :E~-complete and 11~-complete respectively. In particular, U provides a rare example of a natural :E~-complete set. In Chapter 3 we solve a question due to Kechris about UCF, the set of all continuous functions, on the unit circle, with Fourier series uniformly convergent. We further show that any :E~ set, which contains UCF, must contain a continuous function with Fourier series divergent. In Chapter 4 we use techniques from number theory and the theory of Borel equivalence relations to provide a class of complete II~ sets. Finally, in Chapter 5, we solve a problem due to Ajtai and Kechris. For each differentiable function f on the unit circle, the Kechris-Woodin rank measures the failure of continuity of the derivative function f', while the Zalcwasser rank measures how close the Fourier series off is to being a uniformly convergent series. We show that the Kechris-Woodin rank is finer than the Zalcwasser rank. v Chapter 0 Introduction The purpose of this chapter is to provide an introduction to the results proved in the rest of the thesis. One of the most interesting properties of a Borel set is its exact level in the Borel hierarchy. We can attempt to compute an upper bound and lower bound for the set. The upper bound is usually easier to find. It involves producing a calculation that witnesses a given level. On the other hand, since Borel complexities are preserved under continuous preimages, the notion of a continuous reduction yields a powerful technique for producing lower bounds. A. Kechris asked whether the set of real numbers that are normal in base two is II~-complete. In Chapter 1 we further study the relationship between the Borel class of X C [O, 1], and that of Dx C 2N, the collection of subsets of N whose densities lie in X. Given the exact location of X in the Borel or difference hierarchy, we exhibit the exact location of Dx. For a: ~ 3, Xis properly Ve(II~) iff Dx is properly Ve(Il~+aJ We also show that for every non-empty set X C [O, 1], D x is Il~-hard. For each non-empty Il~ set X c [O, 1], in particular for X = {x }, D x is II~-complete. For each n 2:: 2, the collection of real numbers x that are normal or simply normal to base n is Il~-complete. And DQ, the subsets of N with rational densities, is V2 (Il~)-complete. In particular D<Q provides one of few natural examples of a Borel set above the third level of the Borel hierarchy. Note that this chapter is a joint work with T. Linton. See [KL]. Mahler [Mah] divided complex numbers into classes A, S, T and U according to their properties of approximation by algebraic numbers. A consists of algebraic numbers, while S, T, and U provide a canonical partition of the transcendental numbers according to speed at which they are approached by a sequence of algebraic 1 numbers. We calculate the possible locations of these sets in the Borel hierarchy. A turns out to be E~·-complete, while U provides a rare example of a natural E~­ complete set. vVe produce an upperbound of E~ for S and show that T is II~ but not Eg. Our main result is based on a deep theorem of Schmidt [Sc2] which guarantees the existence of T numbers. These results are given in Chapter 2. See [Kil]. We denote by UC F the set of all continuous functions, on the unit circle, with uniformly convergent Fourier series. In Chapter 3 we answer a question from [Kel]. UCF is shown to be II~-complete. This suggests an interesting question related to UCF. Namely, is it true that any E~ set, which includes UCF, has a continuous function with Fourier series divergent? We show that it is true in the course of the proof that UC F is II~-complete. Let X be a Polish space. A subset A of X is called a IIi set if there exists a Borel function f from the Cantor space to X such that X - A is the image of f. Thus a IIi set is coanalytic. We say that a subset A of X is IIi-hard if for any IIi subset B of the Cantor space there exists a Borel function f from the Cantor space to X such that B = f- 1 (A). If, in addition, A is IIi, then A is IIi-complete. In Chapter 4 we provide new examples of complete IIi sets from number theory and Borel equivalence relations. A set of real numbers M is called a normal set if there exists a sequence (xn)nEN of reals such that for all y E IR, y E M if and only if (yxn)nEN is uniformly distributed mod 1. A sequence of real numbers (xn)nEN is called a universal sequence if for all nonzero reals y, (yxn)nEN is uniformly distributed mod 1. We see that US is IIi. A. Kechris suggested that we calculate the exact complexity of US, the set of universal sequences of reals. We show that US is IIi-complete. Our result of U is based on a theorem of Rauzy [Ra]. Let Ebe a countable Borel equivalence relation on the Cantor space. We denote by A(E) (F(E)) the set of all closed sets K such that En (K x K) is aperiodic (finite), i.e., for all x E K, the equivalence class of x is infinite (finite) in K. In many cases, we also show that A( E) and F( F) are IIi-complete. In Chapter 5 we consider IIi norms. A norm on a set P is any function r.p 2 taking Pinto the ordinals. We only consider a regular norm 1.p, i.e., 1.p maps P onto some ordinal A. Given a Polish space X and a IIi subset P of X, we say that a norm 1.p: P --+ Ordinals is a IIi-norm if there are IIi subsets R and Q of X x X such that y E P =='? [x E P & 1.p(x) ~ 1.p(y) {::=::} (x, y) rf. R {::=::} (x, y) E QJ. From the previous relation, we see that in a uniform manner for y E P, the set {x E P: 1.p(x)~ 1.p(y)} is IIi ( (x, y) E Q) and the complement of a IIi set ( (x, y) rf. R), hence a Borel set. In [Mo] it is shown that every IIi-norm is equivalent to one which takes values in w 1 , the first uncountable ordinal. One of the basic facts is IIi subset P admits a IIi-norm 1.p: P--+ w1 (See [Mo].) Hence it is very natural to look for a canonical norm on IIi sets that arise in analysis and topology. that every Zalcwasser [Za] and Gillespie-Hurwitz [GH] introduced a rank that measures the uniform convergence of sequences of continuous functions on the unit interval. We call it the Zalcwasser rank and apply the Zalcwasser rank to the Fourier series of a continuous function on the unit circle. The Zalcwasser rank is a IIi norm on the set of all continuous functions with convergent Fourier series. Kechris and Woodin [KeWJ defined a rank that measures the uniform continuity of the derivative of a differentiable function. We shall refer to this rank as the Kechris-Woodin rank. In fact, they have shown that on the set of all differentiable functions, the KechrisWoodin rank is a IIi-norm. Ajtai and Kechris [AK] conjectured that the KechrisWoodin rank is finer than the Zalcwasser rank, meaning that for any function f, the Zalcwasser rank is less than or equal to the Kechris-Woodin rank. In the last chapter, we provide an affirmative answer to this conjecture. 3 Chapter 1 Normal numbers and subsets of N with given densities 1.1 Introduction The collection of "naturally arising" or non "ad hoc" sets that are properly located in the Borel hierarchy (meaning for example non :Eg), is relatively small. In fact, only a small number of specific examples of any sort are known to be properly located above the third level of the Borel hierarchy. Recently, Kechris asked whether the set of real numbers that are normal in base two is II~-complete. Ditzen then conjectured that if this were true for each base n ~ 2 then the set of ng real numbers that are normal to at least one base n ~ 2, should be :E~-complete. Certainly this example is non ad-hoc. We found this set extremely difficult to manage, and hence we are inclined to agree with Ditzen's conjecture. There is some evidence supporting this conjecture; namely, results as in [Scl] which suggest that normality base two and normality base three have a weak form of independence. Unfortunately, such proofs are non-constructive and the conjecture appears to be more number theoretic than set theoretic. It seemed reasonable to replace the set in the conjecture with the easier to manage collection of subsets of N with density l/n, for some (varying) n E N. However, in this case, the limit one computes is the same for all n, and the set is too simple. We then looked at the subsets of N with rational densities, DIQ, and were able to show it was properly the difference of two II~ sets, i.e., V 2 (II~)-complete. As DQ is at least somewhat natural, this is rather surprising, since it lies above the third level of the Borel hierarchy. In co~tinuing the study of the relationship between the Borel class of X ~ [O, 1J and that of Dx ~ 2N, the collection of subsets of N whose densities lie in X, we were able to show that if X is properly II~ (:E~), then Dx is properly II~+ 1 (:E~+ 1 ) for n ~ 3. Furthermore, the relationship extended to the difference hierarchy of a~+ 1 sets. If X is properly Ve(II~), then Dx is properly Ve(II~+ 1 ), so long as 4 n ~ 2. However, on the dual side, at the finite levels of the difference hierarchy for n = 2, an interesting phenomenon arises. For m < w, if X is properly Dm(11g), then D x is properly '.Dm+l (11~). So the analogy of Q to DIQ extends to all finite levels of the difference hierarchy, and no Dx can be properly Dm(11~). If~ ~ w and x is properly De(l1g), then Dx is properly De(l1~). For Q ~ 3, if r = 11~, E~, '.De(II~), or De(11~), and f* is the class where the Qin r is replaced by 1 +a, then X is properly r iff D x is properly I'*. In particular we are able to show that for every non-empty set X ~ [O, 1], Dx is 11~-hard; for each nonempty 11g set X ~ [O, 1], Dx is 11~-complete; for each n ~ 2, the collection of real numbers x that are normal or simply normal to base n is 11~-complete; and as mentioned above, DQ, or Dx for any E~-complete set X, is '.D 2 (11~)-complete. 1.2 Notation and background information For sets A and B, I A I is the cardinality of A, A denotes the topological closure of A, and we denote the set of all functions from B into A by AB. If X ~ A, we denote the preimage under f of X by f'-(X). We sometimes identify E N = { 0, 1, 2, ... } with the set { 0, 1, ... , n - 1 }. Thus 2N is the collection of functions f: N ~ { 0, 1 }. We let A <N = LJ An, denote all finite sequences from A., n and A :5N = A <N u AN. 0 and nEN r denote the constant zero and constant one functions in 2N. If f E A.~N and n EN, fin= (!(O), ... ,J(n -1)), and for s, t E A<N, Is I denotes the length of s (the unique n for which s E An), s ~ t (t extends s) means tl1 s I = s, and s,,....t is the sequences followed by the sequence t. We use JR and Q to denote the reals and rationals, and IF denotes the irrationals between zero and one. We describe the Borel hierarchy using the standard modern terminology of Addison, and define the difference hierarchy, on the ambiguous classes of a~+i sets, based on decreasing sequences of 11~ sets. For Polish topological spaces X, let E~(X) denote the collection of open subsets of X, and 11~(X) denote the closed subsets of X. Inductively define for countable ordinals a ~ 2, E~(X) = {A ~ X I A= LJ An, where each An E 11~n (X) and /3n <a}. nEN 11~(X) = {A.~ x I A= n An, where each An E E~n (X) and /3n < Q }. nEN 5 ~~(X) = {A<;:;; X I A E II~(X) n E~(X) }. If X is known by context or irrelevant, we frequently drop it for notational convenience. Thus, E~ = Open, II~ = Closed, E~ = Fu, II~ = G 8, and so on. The difference hierarchy, which is a finer two sided hierarchy on the ~~ sets, extends the Borel hierarchy by including it as the first level ( = 1) for each countable ordinal a. For a co.untable ordinal and any sequence of subsets of X, (A,a),a<e, where A,a 2 A131 if /3 < /3' (so (A,a) is decreasing) and for limit,\< A,\= A,a (so e e n e, ,8<,\ the sequence is continuous), define a set A= Ve((A,a),a<e), by x E A ~ 3/3 < e (x E A,a), and the largest such /3 is even. A countable ordinal f3 is even, if when we write /3 = ,\ + n, with ,\ = 0 or a limit ordinal, n is even. Let 'De(II~) be the collection of sets of the form Ve( (A,a) .B<e ), where (A,a) .B<e is a decreasing, continuous sequence of II~ sets (for < w, the decreasing requirement is redundant). So 'D1(II~) = II~, 'D2(II~) = {A - B I A, B E II~, and A 2 B} (so in IR, [O, 2) is a typical 'D2(II~) set), and 'D3 (II~) is the collection of sets of the form e (A - B) UC where A, B, CE II~ and A 2 B 2 C. For any class of sets r, let the dual class, r, be the collection of complements of sets in r (so i\(II~) = E~), and say A is properly r, if A E r - f. We need the following elementary facts about the difference hierarchy classes. The 'De(II~) sets are closed under: (i) intersections with II~ sets; (ii) intersections with E~ sets, if is even; (iii) unions with II~ sets, if is odd; (iv) unions with E~ sets, if ~ w. e e e Each of these implies a dual property for the Ve(II~) sets. For example, (i) says that the Ve(II~) sets are closed under unions with E~ sets. By combining the above properties with the fact that if A is II~, and B is IIp (/3 < a), then both A - Band AU Bare II~, we also have (for a> /3, or a= /3 and ( v) e~ w): the Ve(II~) sets are closed under intersections with IIp sets. We will need this for /3 = 3 later. 6 In order to determine the exact location of a set in the above hierarchy, one must produce an upper bound, or prove membership in the class r, and then a lower bound, showing the set is not in r. In general the lower bounds are more difficult, but since these classes are closed under continuous preimages, the notion of a continuous or Wadge reduction yields a powerful technique for producing lower bounds. The idea is take a set C that is known to be a non r set, and find a continuous function f such that r-(A) = C. Then A cannot be in r either. The Cantor space 2N (with the usual product topology and 2 = {0, 1 } discrete) is known to contain sets that are proper, in all the classes above. A subset, A, of a Polish topological space, x, is called r-hard (for r = De(II~) or De(II~) ), if for every C E r(2N) there is a continuous function, f: 2N ---+ X, such that x E C ~ f (x) E A, that is p-(A) = C. Thus if A is r-hard, then A rJ. r. If in addition to being r-hard, A is also in r, we say A is r-complete. Wadge [Wa] (using Borel determinacy [Mar]), showed that in zero-dimensional Polish spaces, there is no difference between a set being r-complete or properly r. Let X and Y be Polish spaces, C ~ X, A and B disjoint subsets of Y; let C ~w (A; B) assert that there is a continuous function f: X---+ Y where x E C =} f( x) E A, and x rJ_ C =} f( x) E B. If B = •A = Y - A, we write C ~w A for C ~w (A; •A), and say C is Wadge reducible to A. Wadge's result mentioned above was that for all Borel subsets A and B of ~ere-dimensional Polish spaces, either A ~w B or •B ~w A. Louveau and Saint-Raymond [LS] later showed a similar result (which Wadge obtained using analytic determinacy) for C ~w (A; B), using closed games. It implies that for each class r O O N = De(Ila) or De(Ila) (a ~ 2), there is a r-complete set Hr ~ 2 , such that for all disjoint analytic A and B (in any Polish space), either Hr ~w (A; B) (by a one-to-one continuous function), or there is a r set S such that A~ Sand B n S = 0. For our classes (since we only work in Polish spaces), being r-hard, and being a non r set are the same thing. Hence a set will be properly r iff it is r-complete. Notice also that if C is r-hard, and C ~w B, then B is r-hard. And if C ~w (A; B), and D is any set containing A and disjoint from B, then C ~w D. 7 1.3 Subsets of N with given densities We describe here the basic facts and properties about the densities of subsets of the natural numbers that we need. This topic is covered in detail in [KN], for example. Definition 1.1 For A ~ N, let 8(A) = lim n--+oo IAn n[O, n) I, if the limit exists, and say 8(A) does not exist, otherwise. We call 8(A) the density of A. Thus, whenever it exists, 8(A) E IR n [O, 1], and is roughly the frequency of occurrences of A in N. For nonempty X ~ [O, 1] n IR, let Dx = {A~ N I 8(A) E X} (if X = { r} we write Dr for D{r} ). Let DE= D[o,I] denote the collection of subsets of N whose densities exist. If we identify A ~ N with its characteristic function { 1, . b X ( ) X A: n,,_r --+ 2 , given y A n = O, if n E A; if n ~ A, then Dx becomes a subset of the Cantor space 2N (with the usual product topology). For s E 2<N, let 11s11 = I { i E Dom( s): s( i) = 1} and let Is I denote the length of s. We can then define the density of s, as J 8(s) II s II =VIE Qn [0,1]. For a E 2N, the density of a exists iff the sequence { 8( afn)} nEN converges, in which case the limit of the sequence is the density of a. This shows that DE and D 0 are O . TI 3 , smce (that is the sequence of partial densities of a is Cauchy), <=?a E n LJ n nEN NEN C(n,N, k), kEN where C(n, N, k) is the collection of a E 2N such that I8(afN) - 8(afN+k) I < l/n, which is clopen (both closed and open). In the future we will not bother rewriting 8 number quantifiers as countable intersections or countable unions, nor will we verify that the sets similar to C( n, N, k) above are clopen, if it is clear that they are. Do . a 1so 11° smce . is 3 a E Do¢;> Vn ::IN Vk?: N(8(a:ik) < l/n). The sequence {8( a:ln)} nEN is very close to being a Cauchy sequence, meaning that if n is large, then 8( a:ln) and 8( a:ln+I) are very close. In fact, (1.1) This shows that if I= liminfn->oo { 8(a:ln) }, and S = limsupn->oo { 8(aln) }, then for every real number r E [I, SJ, r is a limit point or cluster value of the sequence { 8( a:ln)} nEN" 1.4 Two methods for producing subsets with nice densities We now give two methods for producing a E 2N so that the density of a is easy to compute. The first involves copying the values of a sequence { Xn } nEN with Xn E (0, 1). The idea is to define a as a union, a = LJ an, where for all n E N, nEN O:n+l is a finite proper extension of an, 8(an) ~ Xn, and 8(a:lk+1) is between 8(an) and 8(a:n+1), whenever k is between I O:n I and I O:n+1 j. Thus the density of a will exist iff the sequence { Xn } nEN converges, and the limit of this sequence will be the density of a. Given any sequence { Xn }nEN E (0, 1)1' 1' we define a, the result of running the canonical construction with input { Xn} nEN' inductively as follows: Let a:o = (0, 1). Given an, if 8(an) < Xn+1, fix the least k EN such that c( "'lk) - II Cl:n II + k > u Cl:n - I Cl:n I + k _ Xn+l (k exists since { 8(an"'lk) }kEN starts at 8(an) and increases to 1). Set O:n+l O:n"' I k. If 8(an)?: Xn+1, fix the least k EN - { 0} such that c( ..... k) II Cl:n II u Cl:n 0 = I Cl:n I + k ~ Xn+1, LJ On E 2N. Clearly, IOn+1I?:jOnI+1>n+1, nEN for all n EN. Using the minimality of k and (1.1), we see that and set On+1 =On "'Ok. Let a= 1 I Xn+I - 8(an+1) I< ICl:n I < l/n. 9 Since an+l is an followed k zeros or k ones, 8(alm+1) is between 8(an) and 8(an+1), whenever m is between I an I and I an+l I· So the density of a exists iff the sequence of partial densities of a is Cauchy iff the sequence of the densities of the O:n 's is Cauchy iff { Xn} nEN is Cauchy. More precisely, for any convergent subsequence { Xnk }kEN' lim Xnk = lim 8( O:nk ). k_,.oo k_,.oo This gives then a canonical way to produce o: with 8(0:) = r for any r E [O, l]. Notice also that if Xn happened to be zero or one, we could replace Xn with 1/n or 1-1/n respectively, and hence we can run this construction for sequences in [O, l]N. The second construction involves partitioning N into a finite or countably infinite collection of sets with positive densities, and placing a copy of some O:n E 2N on the nth set in the partition. Then even when the partition is infinite, one can basically add the densities. In general this is not true, since the union of the singletons has density one, where as each singleton has density zero. But when the pieces being combined are contained in disjoint sets with positive densities, everything works out fine. Let I ~ N and {An } nEJ be a family of pairwise disjoint subsets of N such that LJ An = N (i.e., a partition of N); for each n E I, the density nEI N of An exists and is positive; and lim I: 8(An) = 1. For each n E I, let O:n E 2N N_,.oo n=O be such that 8( an) exists. Define C ~ N, the set obtained by playing a copy of O:n on An, as follows: First, since 8(An) > 0, An is infinite. Let { af: hEN be a one-to-one increasing enumeration of An. Then for each m E N there is a unique n and k such that m = af:. We put m EC iff m = af: and o:n(k) = 1. It is straightforward to check that 8(C) = L8(An) · 8(o:n)· nEI Thus, whenever we say "let o: be the result of playing O:n on An," we mean that o: is the characteristic function of the set C defined above. Of course we can still make this definition even if 8( o:n) does not exist. If at least two of the O:n 's have divergent densities, the density of C may or may not exist. However, if exactly one of an 's has a divergent density, then the density of C does not exist. 10 1.5 Some II~-complete sets In this section we establish a strong reduction of a II~-complete set, to the set D 0 . Thus we have an affirmative answer to a question of Kechris, who asked if Do was II~-complete. Once this is done, we are able to show hardness for numerous other sets, including the collections of normal and simply normal numbers. It is known that the set C3 = { /3 E NN I Vn, /3._(n) is finite}= { /3 E NN I liminf /3(n) = oo} n_,.oo is II~:--complete (see for example (24) in [Mi] for a proof). Theorem 1.2 C3 ~w (Do; -.DE). complete. In particular, both Do and DE are IT~­ The second part of the theorem follows from the first, because Do ~ DE and DE n -.DE = 0. The idea is to take /3 E NN and define from it a sequence D { Xn} nEN' so that Xn depends only on a finite initial segment of (3. We then produce the canonical a with input { Xn} nEN' The function /3 1-+ a : NN ---+ 2N, will then be continuous since the first N values of a depend only on the first N values of { Xn} nEN' which depend only on a finite initial segment of (3. The sequence Xn = /3tn) almost works, but we must first fix /3 so that /3( n) 2: 2, and /3 is not eventually constant (so that lim /3(l ) exists iff it is zero). For /3 E NN, define n_,.oo n '( ) = { /3(n/2) + 2, if n is even; /3 n n + 1, if n is odd. Then /3 1-+ /3' is continuous and /3 E C3 ¢=> /3' E C3 . Given /3 E NN, let a E 2N he the result of running the canonical construction on input { 1 //3' (n) }nEN' Then the sequence { b( afn)} nEN always contains a subsequence which converges to zero, since /3'(2n + 1) = 2n + 2. Hence the density of a exists iff it is zero. Thus, /3 E C3 ¢=> /3' E C3 ¢=> n_,.oo lim /3 I (l) n = 0 ¢=> b(a) = 0 ¢=>a E Do¢=> a EDE. This shows C3 ~w (D 0 ; -.DE) and completes the proof. 11 0 Corollary 1.3 For any nonempty X C [O, l], Dx is II~-hard. In particular for each r E [O, l], Dr is II~-complete. D It is clear that Dr is II~ for each r E [O, 1], so it suffices to prove the first statement. Let J denote the continuous function from Theorem 1.2. If 0 E X, J shows C3 ~w Dx. If 1 E X let g(/3) = <P(J(/3)), where <Pis the bit switching homeomorphism of 2N, </J(a)(n) = { 0, 1, ~f a(n) = l; 1f a (n) = 0. Then g shows C3 ~w Dx. Finally if X ~ (0, 1), let x EX be arbitrary. Let A 0 ~ N have density x. Fix n E N such that x + l/n < 1. Let A 1 be disjoint from Ao and have density l/n. Given /3 E NN, let a be the characteristic function of C = A 0 U C1 , where C1 is the result of playing J(/3) on A 1 . Then /3 f-+ a is continuous, o( C) exists iff o(C1 ) exists, and 1 /3 E C3 ¢:? o(C1 ) exists ¢:? o(C1 ) = 0 ¢:? o(a) = x +- · 0 ¢:?a E Dx. n Hence C3 ~w (Dx; ·DE), so C3 ~w Dx, because x EX and Dx n ·DE= 0. D 1. 6 Normal numbers For x E [O, l] and n ~ 2, the base n expansion of xis the sequence {di }iEN E = 2'::~ 1 ~:, and di =f. n - 1 for infinitely many i. For x E [O, l] and n ~ 2, say x is simply normal base n, and write x E SNn, if for each k = nN suth that x 0, 1, ... , n - l, o( { i E N I di = k}) = l/n. Say x E [O, l] is normal to base n, and write x E Nn, if for each m E N and each sEnm+l, o( { i EN I di= s(O), di+l = s(l), ... 'di+m = s(m)}) = l/nm+l. Thus, x is normal to base n, if in the base n expansion of x, all the digits k < n appear with equal frequency, all the pairs (k,j) appear with equal frequency, etc. 12 It is known that the set of numbers in [O, 1], that are normal to all bases n ~ 2 simultaneously, has Lebesgue measure one (see for example 8.11 in [Ni]). It is straightforward to see that SNn and Nn are TI~, since Dr is TI~. One of the main questions that motivated this study was to try to show that NN = UnEN Nn was :E~-complete. We were unable to answer this, but we did manage to show that each Nn and SNn are TI~-complete. As Nn ~ SNn the following result shows both of these simultaneously. Theorem 1.4 For each n E N - { 0, 1 }, Do :'.Sw (Nn; -iSNn)· In particular, both SNn and Nn are TI~-complete. Let x = d· 2:: -I be any fixed number that is normal to base n. Let { ik hEN 00 D i=l n be an increasing enumeration of the set Io = { i E N I di = 0 } . Then Io has density l/n since x E Nn. Given a E 2N let x' E [O, l] be given by the base n expansion, d'·= {l, 1 di, That is x' = x + 2:: ~k kEa- (1) n • ifi=ik anda(k)=l; otherwise. The function a r-+ x' is continuous. If a E D 0 , then x' is the result of changing a subset of density zero of the O's in the base n expansion of x to ones, leaving the rest of the base n expansion of x unchanged. Hence, x' is still normal base n. And if a rf. Do, then x' rf. SNn, since 0 and 1 no longer occur with density l/n in the base n expansion of x'. D 1. 7 The Borel classes of D x We now turn to the problem of classifying the Borel class of D x in terms of the class of X. The fact that such an exact relationship exists is surprising. Basically, D x has one more quantifier and lies on the same side of the hierarchy as X. We start with the upper bounds. Proposition 1.5 For nonempty X C [O, l], if X is complete. 13 Tig, then Dx C 2N is TI~­ Let { Un }nEN be a countable basis of open sets for IR n [O, 1] (with the usual Gk be any nonempty II~ subset of [O, 1], where each Gk is topology). Let X = kEN open. A moments reflection shows that D n a E Dx 5=} a EDE and Vk 3n 3m Vp ~ m (8(afp) E Un~ Un~ Gk)· Since membership in N(k, n,p) = {a E 2N I 8(afp) E Un~ Un~ Gk} is completely determined by afp (and whether or not Un ~ Gk, which is independent of afp), N(k,n,p) is clopen for each (k,n,p) E f~r3. Thus Dx is II~, and by Corollary 1.3, D x is II~-complete. Furthermore, if we denote by P( X) the set of a E 2N such that Vk 3n 3m Vp ~ m (8(afp) E Un~ Un~ Gk), then P(X) is II~ and a E Dx ¢:?a E DE n P(X). D Corollary 1.6 Let X ~ [O, 1] be nonempty. (i) If Xis Eg, then Dx is 1' 2 (II~). (ii) If Xis II~ (E~) for a~ 3, then Dx is II~+a (E~+aJ. (iii) If Xis 'De(II~), for a and e~ 2, then Dx is Ve(II~+aJ (iv) If xis Ve(II~) for a~ 3, or a= 2 and ~ w, then Dx is Ve(II~+a)· (v) If Xis Dm(IIg), form< w, then Dx is 1'm+1(II~). e If Xis Eg, •Xis IIg and Dx = DE-D-.x E 1' 2 (II~) by Proposition 1.5, so (i) holds. More precisely, for each XE Eg([o, 1]), there is a E~ set P'(X) (namely •P( •X) from Proposition 1.5) such that a E Dx ¢:?a E DE n P'(X). Clearly, for D W=X-X',Y= LJXnandZ= nEN (1.2) nxn, nEN Dw = Dx -Dx,, Dy= LJ Dxn, and Dz= nDxn· nEN nEN An easy induction then shows, for n ~ 2, that for each II~ (E~) set X ~ [O, 1], there is a II~+l (E~+ 1 ) set P(X) ~ 2N, such that (1.3) a E Dx ¢:?a E DE n P(X). This then gives (ii) for a < w, since the classes II~ and E~, for k ~ 4, are closed under intersections with II~ sets. The function f: 2N ~ IR, given by f(a) = { 8(a), 2, 14 if 8(a) .exists; otherwise. is a Baire class 4 function by Proposition 1.5. As r-(X) = Dx, for all X ~ [O, 1], if X is II~ or E~, then Dx is II~+a or E~+a· Thus if a ~ w, 4 +a= 1 +a= a, so (ii) holds (also the levels of the projective hierarchy do not increase from X to Dx ). Using (1.2) and (1.3), one shows that for each De(II~) set X ~ [O, 1] (with a and ~ ~ 2), there is a De(II~+a) set P(X) ~ 2N, such that Dx =DE n P(X). Thus (iii) follows, since De(II~+a) sets are closed under intersections with II~ sets 0 (as long as a ~ 2). If X is De(IIa), for a and ~ ~ 2, then D x = DE n -,D,x which is the intersection of a II~ set with a De(II~+a) set. For a ~ 3, or a= 2 and ~ ~ w, the class Ve(II~+a) is closed under intersections with II~ sets, and hence (iv) follows. Finally, if Xis Dm(IIg), then Dx =DE n -iD,x, which by (iii) and the definition is a Dm+l (II~) set, so (v) holds. O The upper bound of D 2 (II~) for X = Q the rationals turns out to be a lower bound also. This is rather surprising, since very few sets are known to be properly located above the third level of the Borel hierarchy. We show now that DQ is E~ hard. It turns out that no D x is E~-complete (except of course for X = 0 in which case one might say Dx = -iDE, which is E~-complete by Theorem 1.2), and our proof of this fact will be the second half of the proof that DQ is D2 (II~)-complete. Our reduction here uses a non-standard E~-complete set, namely, S3 = {a E 2NxN I 3R \Ir~ R 3c, a(r, c) = 1}. If one views a as an N x N matrix of zeros and ones whose entry in row r and column c is a(r, c), then S 3 is the set of matrices where all but finitely many rows contain a one, or equivalently with finitely many "all zero" rows. To prove that -iC3 :::;w S 3 , /3 E NN ~a E 2NxN, one attempts to define afnxn so that it contains /3(n) partial "all zero" rows. With a little organization, this makes the number of rows in a without any ones equal to the liminf of /3, so /3 ¢:_ C3 ¢:> liminfn_,. 00 /3(n) is finite ¢:> a E S3. We define inductively, afnxn, from /3fn (so that /3 ~ a is continuous, and at stage n we must define a's entries in column n for the rows 0, 1, 2, ... , n - l, as well as row n, columns 0, 1, ... , n ), as follows: 15 Stage 0: If ,8(0) = 0, set a:(O, 0) = 1 and if ,8(0) > 0, set a:(O, 0) = 0. Thus Z 0 , the number of "all zero" rows in a:f1xl is either 0 = ,8(0) or 1 ~ ,8(0). Stage n: We are given a:fnxn and ,B(n), and must define the first n + 1 entries, in both column n and row n, of a:. Let Zn be the number of partial rows in a:fnxn that are all zeros. If ,B(n) ~Zn, extend the "first" ,B(n) many "all zero" rows of a:fnxn by adding a zero in column n; all the remaining rows (with index less than n) receive a one in column n; and define the first n + 1 entries in row n to be ones. Here, "first" is defined from the indices of the rows, so the first 5 rows refers to the 5 rows with lowest indices. If ,B(n) > Zn, extend every "all zero" row by adding a zero in column n; every row that already has a one gets a one in column n; and make row n begin with n + 1 zeros. Hence Zn+ 1, the number of "all zero" rows in a:f(n+1)x(n+1), is either ,B(n) or 1 +Zn~ ,B(n). More precisely, for r < n, let Zn(r) denote the number of rows in a:fnxn, with index r' < r, that are all zeros. Then (for r < n) we set a:(r, n) = { if Ve< n[a(r,c) = O] and Zn(r) < ,B(n); ~: otherwise. And for c ~ n set _ { 0, a: (n, c ) 1, if ,8 (n) > Zn; h . ot erw1se. One sees that if for all n ~ N, ,8( n) ~ k, then Zm ~ k for all m > N + k, and the first k many "all zero" rows in af(N+k+l)x(N+k+l) always receive a zero. Thus, lim inf ,8( n) ~ the number of "all zero" rows in a:. n_,.oo The reverse inequality is trivial if lim inf ,8 = oo, so assume lim inf ,8 = k < oo. Then ,8 takes the value k infinitely often. Let ni < n2 < ... < nk+l be any collection of k + 1 natural numbers. We show that for some i = 1 to k + 1, row ni of a: contains a one. Since ,B(n) = k infinitely often, fix n > nk+1 such that ,B(n) = k. Then Zn+l ~ k, so at least one of the rows with indices ni gets a one at stage n. Thus liminfn_. 00 ,B(n) =the number of "all zero" rows in a:, which directly translates to and ·C3 ~w S3. So S3 is E~-hard and it is straightforward to see that S3 E :E~. 16 Proposition 1.7 S3 :::;w (Doi; DTP), and hence Doi is ~~-hard. D Let {An} nEN be a partition of N with 8(An) = l/2n+l (for example one can take { 2n(2p + 1) - 1 }pEN for An)· Let { ak }kEN be an increasing enumeration of An. Let Bn ~ An be the set { ak·(n!) I k EN}, so that 8(Bn) = n!;n+l. Let LJ Bn, so that B* U { Bn} nEN is a partition of N suitable for our second nEN canonical construction. Given a E 2NxN, let B* = N - a*(c) = { 1, r 0, if for all c'::::; c, a(r, c') = O; otherwise. Then a r--+ {a; }rEN is continuous (from 2NxN to (2N)N) and a; is eventually zero (hence 8(a;) = 0) iff row r of a has a one, and a; is identically one (hence 8(a;) = 1) iff row r of a is identically zero. Let f (a) E 2N be the result of playing a; on Br, 00 ... 8(a*) for r EN, and 0 on B*. Then, 8(J(a)) = r~o r!. ;+ 1 (which always exists). Also, 2 00 8(a;) r~o r!. r+l is rational iff 8(a;) is non-zero finitely often (see for example 1.7 in 2 [Ni] or a proof that e is irrational). Thus, a E S 3 iff all but finitely many rows of a contain a 1 iff for all but finitely many r, 8(a;) = 0 iff 8(J(a)) E Q. Thus S 3 :::;w (Doi; DTP), and Doi is ~~-hard, provided f is continuous. Since J(a)rn is completely determined by afMxn, where M =max { m EN I Am n [O, n) =/= 0 }, f is continuous and we are done. D Lemma 1.8 For any set C, if C :::;w (D x; D...,x ), then C3 x C :::;w D x. D . Let f be continuous and witness C :::;w (Dx; D...,x ). Assume C ~ Y (some topological space), then 8(f(y)) exists for ally E Y. As in Theorem 1.2, we replace /3 E NN with /3', where /3' (2n) = /3( n) + 2, and /3' (2n + 1) = 2n + 2. So that /3 r--+ /3' is continuous and does not alter membership in C3. We show C3 x C :::;w Dx by defining </>(/3, y) to be the result of playing J(y) (whose density always exists) on A 0 , the evens, and a' on A 1 , the odds, where a' comes from the canonical construction with input { Xn} nEN' where Xn = (1 - 1//3'( n )) · ( 8(f (y )In)+ 1//3'( n )). This defines a continuous function, since f is continuous and a'fn depends only on /3ln and the neighborhood of y that determines f (y )In (which exists since f is continuous). If /3 E C3 , then lim Xn = lim ([1-1//3'(n)] · [8(J(y)ln) + 1//3'(n)l) = 8(J(y)). n-+oo n-+oo 17 Hence, when /3 E C3, 6( </>(/3, y)) = (l/2)6(J(y)) + (l/2)6(J(y)) = 6(J(y)) E X {:} y E C. When /3 ~ C3 the sequence { Xn } nEN diverges. So 6( a/) does not exist and the density of ¢>((3,y) does not exist. Thus </>(/3,y) E Dx {:} (/3,y) E C3 x C. D We now construct a sequence of complete sets for the differences of II~ sets. Let m ~ 1 be a finite integer. In the space, (NN) m, consider the sets Ao, Ai, ... , Am-i, where Ao = C3 x NN x NN x ... x NN Ai = C3 x C3 x NN x NN x ... x NN D~ = { (/3i)i<m E (NN) m I /30 E C3 and max { i < m: /30, ... , /3i E C3} 1s even } D~ = { (/3i)i<m E (NN)m I /30 ~ C3 or max{i < m:/3o, ... ,/3i E C3} is odd}. We show now that for any '.Dm(II~) set B ~ 2N, B ~w complete and n:n, so n:n is '.Dm(II~)- n:n is '.Dm(Il )-complete. Given such a B, fix Bo 2 Bi 2 ... 2 - - 0 3 Bm-i, II~ subsets of 2N with B = '.Dm( (Bi)i<m)· Since Bi E II~ and C3 is II~:­ complete, there is a continuous function, fi: 2N---+ NN, such that a E Bi{:} fi(a) E C3. Define f: 2N ---+ ( NN) m by f(a) = (fo(a),fi(a), ... ,fm-i(o)). Since the Bi's are decreasing, it is straightforward to check that a: E Bi {:} fi( a) E C3 {:} J(a) E Ai, which shows B ~w n:n. Notice that C x D~ = D~+i· 3 18 Theorem 1.9Forl ~ m < w, if Dx isDm(IIg)-hard, thenDx isVm+ 1 (IIg)-hard. Thus no Dx is Dm(IIg)-complete, and Dro. is V 2 (IIg)-complete. D By Lemma 1.8, it suffices to show D~ ~w (Dx; D....,x ). If this were not the case, then by the result of Louveau and Saint-Raymond [LS] mentioned earlier, there would be a Vm(IIg) set S such that Dx ~ S and Sn D....,x = 0. But then Dx = Sn DE, a Vm(II~) set, which is contrary to the assumption that Dx is 0 Vm(II 3 )-hard. D We shall now basically show that X ~w Dx. Literally this cannot be true because X lives in a connected space and Dx lives in a zero-dimensional space. However, for large enough~ and a, intersecting a Ve(II~) set X with IF, the irrationals in [O, 1], does not change the Borel class. Since IF is homeomorphic to NN, if X ~IF one can show X ~w Dx. The following material is well known (see [Ni] pp. 51-67 for example). Given /3 E NN, let /3*(n) = /3(n) + 1. For each n EN, let 1 rn(/3) = rn = - - - - - - - - - - - 1 /3*(0) + - - - - 1 - /3*(1) + - - - 1 - (1.4) .. + /3*(n) so rn E tQ n [O, l]. Then, </>(/3) = lim rn exists, is irrational, and </>is a homeomorn__.,oo phism onto IF. In a way, the next two results, as well as Lemma 1.8, show that our canonical construction can absorb continuous functions. We shall see later that it can actually absorb some Baire class one functions too. Lemma 1.10 For nonempty X ~ NN, X ~w (D</>(X); D</>(....,x))· D Given /3 E NN, let J(/3) E 2N be the result of running the canonical con- struction on input { Xn }nEN' where Xn is the rn(/3) in (1.4) (which only depends on /3rn+ 1 ). Then b(a) = lim rn = </>(/3). Hence, since f is continuous, for any X ~ NN, f shows nEN and we are done. D 19 Theorem 1.11 Let f be one of the classes Il~ or :E~ for a~ 3; Ve(Il~) for a~ 2; - 0 - 0 Ve(Il 0 ) for a~ 3; or Ve(Il 2 ) for~~ w. If X ~ [O, 1] is f-hard, then so is Dx. In particular, if a ~ w and X is f-complete, then so is D x. The last part follows from the first and Corollary 1.6, since in this case 1 +Qi = Qi. For each such r, let denote the dual class { .x I x E r }. Then r is 0 r closed under intersections with ng sets and r is closed under unions with :Eg sets. - - Since X ~ [O, 1] is f-hard, X is not in r. If X n IF Er, then x = (x n IF) u (x n Q) r, :Eg. r, is also in since X n Q is countable and thus So X n IF r/:. and hence X n IF 1 1 is f-hard. As ¢>- is a homeomorphism, ¢>- (X n IF) is f-hard. By Lemma 1.10, Thus </>- 1 (X n IF) ~w Dx, and Dx is f-hard. 0 Notice that if r is one of the projective hierarchy classes, then X is f-complete iff Dx is. We have already seen Dx is Il~-complete, for any nonempty Il~ subset X of [O, 1]. We shall now show that for a~ 3, if X ~ [O, 1] is Il~ (:E~)-complete, then Dx is II~+a (:E~+a)-complete. We need the complete sets, { Hn ~ 2N In EN}, from [LS], and some basic properties of their function p. For n and m E N, let (n, m) = (1/2)(n + m)(n + m + 1) + m. Thus ( , ) : N x N --+ N is one-to-one and onto. Define p: 2N --+ 2N, by p(a)(n) = 1 <=> Vm (a((n,m)) = 0). Again, thinking of a as an N x N matrix of zeros and ones, with the entry in row n and column m being a( (n, m) ), then 0, p( a)( n) = { 1, if row n of a contains a 1; if row n of a is identically 0. Thus, if <l'n is the binary sequence where an( m) = a( (n, m) ), then p( a)( n) X{ q(an)· One can extend p to 2:::;N, by defining for s E 2k, p(s) = s* E 2<N, where Dom(s*) = {n E NI (n, 0) < k} 20 (so that Dom(s*) is an initial segment of N), and for n E Dom(s*), s*(n) = 1 ¢:?for all (n,m) E Dom(s), s((n,m)) = 0. The properties of p that we need are the following; all appear in [LS]. (i) Va E 2N, Vn EN, ::lk Vm 2: k (p(arm)rn = p(a)rn). (ii) Let H1 = {O} ~ 2N and Hn+I = p--(Hn)· Then Hn is II~-complete. Thus (i) says that for each i EN, the approximations a~(i) = p(arn)(i) are eventually equal to p( a)( i). Lemma 1.12 For H ~ 2N and X ~ [O, l], if H ::;w X, then p--(H) ::;w (Dx; D..,x ). In particular, for n 2: 2, and X ~ [O, l], if Hn ::;w X, then Hn+1 ::;w Dx, and if •Hn ::;w X, then •Hn+I ::;w Dx. Let g: 2N ---+ [O, l] be a continuous function witnessing H ::;w X. Given a E 2N, apply p to arn, yielding say a~ E 2<N (this is a finitary process even though D pis Baire class one). Let O:n = a~,,...O E 2N, and set Xn = g(an) E [O, l]. We let J(a) be the canonical construction on input { Xn }neN· As usual, Xn depends only on arn, so f is continuous. Since g is continuous, Xn = g(an), and { O:n }nEN converges pointwise to p( a), we get that lim Xn = g(p( a)) (and b(J( a)) always n-oo exists). Hence, a E p--(H) ¢:? p(a) EH¢:? g(p(a)) = n_,.oo lim Xn = b(J(a)) EX¢:? J(a) E Dx. So p,_(H) ::;w (Dx; D..,x ). D Theorem 1.13 (i) If X ~ [O, l] is II~-complete (E~-complete), for a 2: 3, then Dx is II~+ 0 -complete (E~+ 0 -complete). (ii) If X ~ [O, l] is V~(II~)-complete, for a 2: 2, then Dx is Ve(II~+ 0 )-complete. (iii) If X ~ [O, l] is Ve(II 0 )-complete, for a 2: 3, or for a = 2 and Dx is - - 0 e2: w, then 0 Ve(II 1+ 0 )-complete. (iv) If X ~ [O, l] is Dm(II~)-complete, for m < w, then Dx is Vm+I (II~)­ complete. 21 Likewise all these hold with hard replacing complete and all implications reverse for a:~ 3. D The upper bounds for D x are from Proposition 1.5 and Corollary 1.6. They show the reverse implications hold for a: ~ 3. If a: ~ w, Theorem 1.11 gives the above statements. Hence we need only work with a: < w, which we will denote by n. Now, ( i) is just the second part of Lemma 1.12. For the remaining cases consider the sets, De= {(a:13)13<e E (2N)e I a:o E Hn and the least /3 such that a:13 ~ Hn is odd } i5~ =·De = { (a:13)f3<e E (2N)e I the least /3 such that a:13 ~ Hn is even } , where (Hn)e is included in De if eis odd, and included in De when eis even. Then De is 'De(Il )-complete, and De is 'De(Il )-complete. Furthermore, by ap0 - - 0 0 0 plying p coordinatewise to De+1, we obtain Dg-. That is, a= (0:13) /3<e E De+i {:::} (p(a:13))13<e E De· Thus, we simply mimic the proof of Lemma 1.12. Let r be any of the classes 'De(Il~) or £\(Il~), mentioned in the hypothesis, where X is f-complete or f-hard. Let f* be the class where the n in r is replaced by n + 1. Let Then the assumptions give a continuous function g witnessing Dr ~w X. Since ~ is countable, (2N)e is homeomorphic to 2N by some function ¢: (2N)e --+ 2N. In fact, !f we take ( , ) : ~ x N --+ N to be any bijection such that for each /3 < e, the sequence (/3,n)nEN is increasing, then we can take ¢(5.)((/3,n)) = a:13(n). Ifwe then let <iln = { a:13(k) I (/3, k) < n }, this will be a finite set containing an initial segment of each 0:13. We can then apply p to each initial segment, obtaining say (a:fi,n)f3<e· Let a~ be the extension of (a:fi,n)f3<e by setting all undefined values to zero. Then {a~ }nEN converges pointwise to (p(a:13))f3<e· Given a E (2N)e, let = g(ii~) E [O, 1] (where a~ is as above). Then Xn depends only on a finite piece of a. If we set f( a) to be the result of running the canonical construction on { Xn } nEN' Xn f is continuous and as in Lemma 1.12, f witnesses Dr· ~w (Dx; D....,x ). Hence 0 Dx is f*-hard. Thus we are done, except for the last case where f* = 'Dm(Il 3 ), which follows immediately by Theorem 1.9. 22 D Chapter 2 The Borel classes of Mahler's A, S, T and U-numbers 2.1 Introduction Mahler [Mah] divided complex numbers into classes A, S, T and U according to their properties of approximation by algebraic numbers. Some studies were done on the structural properties of these sets. For example Kasch and Volkmann [KaVJ verified that the T numbers have Hausdorff dimension zero. Also in harmonic analysis, W. Morgan, C. E. M. Pearce and A. D. Pollington [MorPP] have shown that the set of T and U numbers support a measure whose Fourier transform vanishes at infinity. In the present paper we study the A, S, T, and U-sets from the point of view of Descriptive Set Theory. Among the few sets whose exact Borel class is known, a large percentage turn out to be 11~-complete. For example, the collection of reals that are normal or simply normal to base n [KL], C 00 (1I'), the class of infinitely differentiable functions (viewed as a 27r-periodic function on IR), and UCx, the class of convergent sequences in a separable Banach space X, are 11~-complete [Kel]. Apparently, there are few known natural !:~-complete sets. Of course, the complement of a 11~-complete set is !:~-complete. But, the complement of a natural set need not be natural! Tom Linton [Li] has shown that the family of H-sets, a class of thin sets from harmonic analysis, is !:~-complete, and this is the only !:~-complete natural set we know of (whose complement is not also natural). A. Kechris proposed to find out what the Borel classes of the A, S, T and U-sets are. It turns out that A is rather simple, being :Eg-complete. On the other hand, T is 11~-hard, while U is !:~-complete. Our main results are based on a theorem of W. M. Schmidt (see [Ba], p. 85-94). The exact Borel classes of the S and T-sets are 23 unknown to us. 2.2 Definitions and background For spaces ·x and Y, Xy denotes the set of all functions f from Y to X, with the usual product topology, X and Y being endowed with their usual topologies (2={O,1} and N = {1, 2, 3, ... } being discrete). For sets U and V, if Sis a function from xn+i x yn+i to un+i x vn+i and n E N, then Sin is the function from xn+i x yn+l to un x vn such that if S((x1,···,Xn+1), (y1,···,Yn+1)) = ((u1,···,Un+1), (v1,···,vn+1)), Sln((x1,···,Xn+1), (y1,···,Yn+1)) = ((u1,···,un), (v1,···,vn)). IP = { x E JR : x > 1} and A denotes the class of all non-zero real algebraic numbers in C. We briefly describe the Borel hierarchy. Thus the multiplicative sets of level n are denoted by II~, while the additive class of level n is denoted by E~. In particular, E~ = Open, II~ = Closed, E~ = F~, II~ = G 0 . In addition, the countable union of II~ sets is E~+l; the countable intersection of II~ sets is a E~+l set; the complement of a II~ set is E~; the E~ sets are closed under finite intersection and countable union; while the II~ sets are closed under finite union and countable intersection. If the context demands it, we use II~(X) to denote the II~ subsets of a space X. Now we define the A, S, T and U sets, from Mahler's classification. For convenience we use Koksma's notation which is equivalent to that of Mahler. Given algebraic a E <C, let p(x) E Z[x] be its minimal polynomial. Fix d, h EN. Let Xd,h be the finite collection of polynomials with degree :::; d whose largest coefficient has absolute value :::; h. Let the height of a polynomial, ht(p ), be the maximum of the absolute values of the coefficients. Let Ad,h be the finite collection of algebraic numbers a such that for some p E Xd,h, p(a) is zero (recall that 0 ~ N). Thus, Ad,h is the finite collection of algebraic (complex) numbers whose minimal polynomial has degree:::; d and ht:::; h. Let ebe any complex number and let a belong to Ad,h such that le - al takes the smallest positive value; and define w,i(e, h) by 1 1e - al = hdw~(e,h)+l. 24 Set w;i(O = limsupw;L(e, h) and w*(O = limsupw;L(O. h->oo d-.oo So the values of w;i(O and w*(O measure how fast e is approximated by algebraic numbers. We define, according to the values of w,i(O and w*(e), the A, S, T and U-sets as follows: A= {e EC: w*(e) = O}, s = {e E c: 0 < w*(O < oo}, T = {e EC: w*(O = oo and Vd EN (w;i(e) < oo)}, U = {e EC: w*(e) = oo and :Jd EN (wd(e) = oo)}. Thus, the A numbers are slowly approximated by algebraic numbers. The S numbers are approximated a bit more quickly than A numbers. On the other hand, the T numbers and U numbers are very rapidly approximated, i.e., the value of w*(O is infinite. In particular, the approximation of the U numbers is so quick that for some d E N, wd(e) diverges. For these reasons, we claim that the set of complex numbers is naturally partitioned by the A, S, T and U numbers. 2.3 Results Lemma 2.1 eEA{=:::;. eis an algebraic number. (See [Ba], p. 85-94.) Proposition 2.2 (i) Tbe A numbers are Eg-complete, and the U numbers are E~. (ii) Tbe S numbers are E~, while the collection of T numbers are II~. Proof of Proposition 2.2(i) For each d E N, let Ud be the collection of 25 eE C such that w;i(O = 00. Then ud is n~, since e E Ud ¢=::;> wd(e) = oo ¢=::;>Va EN Vb EN :Jc EN (wd(e, b + c) >a) ¢=::;>Va EN Vb EN :Jc EN :la: E Ad b+c ' ¢=::;> eEn n LJ LJ (o < 1e - a:!< (b +ct1 d+l) V(a,b,c,a:), a EN bEN cEN aEAd,b+c where V(a, b, c, a:) is the collection of 1 e E C such that 0 < le - a:! < -(b + c)ad+I' which is open. Since it is easy to see that for each d, wd(e) = oo implies wd+i(O = oo, we have U = LJ:, Ud and U is :E~. It is well-known that if D is a countable 1 dense set in a perfect Polish space, then D is :E~-complete. Thus, by Lemma 2, A is :E~-complete. (ii) By definition, T is the collection of N (w:(e) < oo). Thus, T = NI e E C such that w*(0 = oo and Va E nN, where M = {e E C : w*(O = oo} and N = {e EC: Va EN (w:(e) < oo)}. Now Mis Il~, since e E M ¢=::;>Va E N Vb E N :Jc E N (wb'+c( e) >a) ¢=::;> Va E N Vb E N :Jc E N :Jd E N Ve E N :Jf E N ( Wb+c( e, e + !) > a + d ¢=::;> ! l) eE n nU U n U W(a, b,c,d, e, !), aENbENcENdENeEN/EN where W(a, b, c, d, e, !) is the collection of e EC such that wb'+c(e, e+ !) > a+-d l , which is open by the argument above. So N is Il~, since by (i), U is :E~ and +1 e EN¢=::;> Va EN (w;(e) < oo) ¢=::;> eE C - U. Hence Tis Il~, being the intersection of two Il~ sets. Since e E S ¢=::;> e rt. T, e rt. U and ert. A, S is :E~. D In 2N, Q is the collection of sequences which end in zeros. 26 Lemma 2.3 There exists a continuous function v from 2N to NN such that (i) for each d EN, a E 2N, v(a)(d):::; v(a)(d + 1); (ii) a E Q <¢=:::? limd_, 00 v( a)( d) < oo. Proof of Lemma 2.3 Let a E 2N. We produce /3 = v(a) recursively. First ,8(2.1) = a(2.l). Suppose that we have defined ,B(i) for all i :::; k. Put ,B(k + 1) = ,B(k) if a( k + 1) = 0 and ,8( k + 1) = ,8( k) + 1 otherwise. It is easy to see that the function v satisfies (i). As long as a ends in zeros, so does v(a) in constants. Otherwise, v( a)( d) goes to the infinity as d ---+ oo, because infinitely many d's, v(a)(d + 1) = v(a)(d) + 1. So (ii) is valid. For given d EN, a 1 , a 2 E 2N, such that a1(i) = a2(i) for all i :::; d, v(ai)(i) = v(a2)(i) for all i :::; d. So vis continuous. This completes Lemma 2.3. From Lemma 2.3, a O rt. Q <¢=:::? limd-oo v( a)( d) = oo. To prove our main theorem, we need a standard example of the II~-complete set. Lemma 2.4 The set P3 ={a= (ad) E (2N)N: Vd EN (ad E Q)} is II~-complete. (See [Kel].) The following theorem is the main result of the paper. Theorem 2.5 There is a continuous function f from (2N)N to <C such that a E P3 <¢=:::? f(a) ET and a rt. P3 {:=::? f(a) EU. In particular, Tis II~-hard and U is E~-complete. Roughly speaking, the original statment of a theorem of Schmidt is the following: Let a1, a2, · · · be any non zero algebraic numbers and let v 1 , v2, · · · be any real numbers exceeding 1. Then we may find and v 1 , v 2 , • • ·, eE <C such that according to a a 2, · · · 1, eis a U number or T number. By using v, which is constructed in Lemma 2.3, we shall effectively control !Ii 's so that we are able to prove Theorem 2.5. In order to make it work, we need to state the reformulated version of a theorem of Schmidt which will play a crucial role in the proof of Theorem 2.5. 27 Theorem S[Schmidt] There exists a sequence< Sn > such that for each n E N, (i) Sn is a function from An x JPm to An x (0, 1r and Sn+l In= Sn, (ii) Suppose that Sn((B1,···,Bn), (v1,···,vn))=((-r1,···,"fn), (>.1,···,An)). Then 1 for each j < n, 'Y1/B1 is rational, H1+ 1 > 2Hj and iH1- 1 < 'YJ+l - 'Yj < !H1- , where H1 = h1_? and h1 = ht( 'Y1 ), and furthermore, we have l"f1 - ,Bl > n- 1 for all 4 algebraic numbers ,B with degreed ::; j distinct from 'Yl, · · ·, 'Yj, where B = >.;t 1 b( 3 d) and b denotes the height of ,B. (See [Ba], p. 85-94.) Using Theorem S we define the function S* from AN x JPN to AN x (0, l)N as follows: S*((B1,B 2,···), (v1,v2,···)) = (('Y1,"(2,···), (>.1,>.2,···)), where for each n, Sn((B1,···,Bn), (v1,···,vn))=(('Y1,···,"fn), (>.1,···,>.n)). S* is well-defined by Theorem S (i). Proof of Theorem 2.5 Let a E (2Nr. Fix a bijection<,> from N x N to N. For each d, k E N, define V<d,k> = (v(ad)(k) + 1)(3d) 5 and B<d,k> = Bd,k, where the function vis constructed in Lemma 2.3. Put A= {Bd,k} and deg(Bd,k) = d. Say S*((B1,B2, · · ·), (v1, v2, · · ·))=(('Y1,"(2, · · ·), (>.1, >.2, ···)).Then by Theorem S (ii), 'Yl' "(2, ... tends to a limit (2.1) ewhich is a real number and satisfies 1e - ,Bl;::: n- 1 for all algebraic numbers ,B distinct from "(1,"(2, ... ' and also (2.2) Define f (a) = _lim 'Y j = e. 1-= Claim. f is continuous from (2N)N to C. 28 Proof of the Claim. Suppose (a~m)) -t (ad) as m -t oo, where for each m, (a~m)) E (2N)N and (ad) E (2N)N. Say for each m, J((a~m))) =em= lim 1km) and !((ad))= k-= where for each e= lim 1k, k->oo k EN, 1km) and 1k are defined by S*, according to (a~m)) and (ad)· Let 1: > 0. Choose ao such that 2 a~- 2 < Since (a~m)) goes to (a(d)) as m -too, €. by the definition of 1km) and 1k, we may find No E N such that 11~:) - 1ao I 0 for all m ;::::: N 0 • Then for all m ;::::: N 0 , we have the following inequality: lem - el ~ lem -1~:) I+ 11~:) -1ao I+ l"r'ao - el < 2 a:-2 < since from (2.2) and Theorem S (ii), lem -1~m)I ~ (H~m))- 1 < 1 d I 2a-l an function. 2 1:, a~l (Him))- 1 ~ 1 H-1 1 11 . . e-1a I ~ Ha-1 < 2a-l 1 ~ 2a-l for a a ;::::: 1. So f lS a contmuous 0 Now we show the main part of the theorem. Depending on the properties of v, Theorem S guarantees that we produce a T number or U number. So we divide the following two cases so that one can have more intuitive ideas. Fix such d, i.e., ad r;f:. Q. Then by Lemma 2.3, we have limk_... 00 (v(ad)(k)+l) = oo. It is clear that for all k, h = h<d,k>, where J(a) = (2.3) wd*( e. So dw;i(e, h<d,k>);::::: V<d,k> - 1, i.e., e, h<d,k>);::::: V<d 'dk> - 1 ;::::: (v(ad)(k) + 1)3 d - d1 for all k. 5 4 It is easy to see that lim supk_, 00 h<d,k> = oo, since the right side of (2.3) goes to infinity as k -t oo. This shows that we may choose {km} such that km -t oo and h<d,km> -t oo as m -t oo. From (2.3), we get the following inequality: w:t(e) = lim supw:t(e, h) ;::::: limsupw:t(e, h<d,km>) h-oo m-oo 29 Therefore, w;i(O = oo and J(o:) = eEU. So we derive o: rf_ P 3 ===} J(o:) = eEU. Case 2. o: = (o:a) E P3 i.e. Vd EN (o:a E Q). Fix d E N. Then for all h, k, m, we have > 1 h -(v(am)(k)+l)(3m) 5 t . , - '"'f<m,k> - 4 <m,k> (2.4) 1e- ,B\ ~ >.deg(,a)(ht(jJ))-(3deg(,a))4 for all algebraic numbers jJ distinct from 11, /2' ... from (2.1) and (2.2), where eis the image of f of o:. In fact, all nonzero algebraic numbers appear in these two inequalities. Let h be a given natural number. Then from (2.4) and the definition of w;i( e' h), we have the following inequality: h-dw~(~,h) ~ min{lh-Mo(3d)s' >.(d)h-(3d)4}, (2.5) where N/0 = sup{v(o:s)(k) + l:s ~ d and k < oo} and >.(d) =min{>. 8 :s ~ d}. Even if for s ~ d, there is no k such that h<s,k> = h, this inequality can be applied. The value >..( d) is positive and 1 ~ Nl0 < oo, since {>-s : s ~ d} is the finite set of positive values and by assumption and Lemma 2.3, Vd E N (limk---.cxi v( o:a )( k) < oo ). So from (2.5), we get * log4 5 4 log>Jd) wa(e, h) ~ max{logh + 3 Mod , dlogh 5 4 + 3 d } < oo and wj(e) = limsupwj(e,h) ~ max{3 5 Mod4 ,3 5 d4 } = 35 M 0 d4 < oo. h----= Hence we can see that the inequality wj(e) = limsupwj(e, h) < oo (2.6) h----= holds for all d. But for all d, k, we obtain * wa(e,h<d,k>)~ As in case 1, w;f(e) ~ 35 d4 Mi - (2.7) V<d k> - 1 'd 5 4 ~(v(o:a)(k)+l)3 d 1 --;r ~'where M1 = limk---.cxi v(o:s)(k)+l ~ 1. Therefore, w;i(O ~ (3d) 4 and w*(e) = limsupw;f(O = oo. d---. cxi 30 From (2.6) and (2.7), for all d EN, w,i(O < oo and w*(O = oo, i.e., l(a) = So we derive a E P3 ===? l(a) = eET. eET. By case 1 and case 2, we obtain a E P3 ===? l(a) ET and a~ P 3 ===? l(a) EU. By definition of T, U, it is easy to see that they are disjiont. So the continuous function l satisfies P3 = l- 1 (T) and C- P3 = l- 1 (U). This fact implies that T, U are II~-hard, :E~-complete, respectively, since by Lemma 2.4, P 3 is II~-complete. We complete the proof of Theorem 2.5. D Remark. We conjecture that S, T are :E~-complete, II~-complete, respectively. 31 Chapter 3 On the set of all continuous functions with uniformly convergent Fourier series 3.1 Introduction There are many criteria for uniform convergence of a Fourier series on the unit circle. One can find those tests in [Zy]. In the present paper, we study UCF from the point of view of Descriptive Set Theory. In [Kel], it was conjectured that UC Fis properly TI~ (TI~ non E~). Several natural properly TI~ sets have been found. For example, the collection of reals that are normal or simply normal to base n [KL]; C 00 ('f), the class of infinitely differentiable functions (viewed as 27r-periodic functions on JR), and UCx, the class of convergent sequences in a separable Banach space X, are properly TI~ [Kel]. It turns out that UCF is properly TI~. We give two different proofs for it. [AK] Ajtai and Kechris have shown that EC, the set of all continuous functions with everywhere Fourier series convergent, is properly CA, i.e., coanalytic . 0 non Borel. We show that there is no E 3 set A such that UCF ~A~ EC. Hence any E~ set, which includes UCF, must contain a continuous function with Fourier series divergent. 3.2 Definitions and background Let N = {1, 2, 3, · · ·} be the set of positive integers and NN the Polish space with the usual product topology taking N discrete. Let X be a Polish space. A subset A of X is CA if there is a Borel funtion from NN to X such that the image of 32 NN off is X -A, i.e., f(NN) = X -A. A CA(IIg) subset A of Xis called properly CA(IIg) if for any CA(IIg) subset B of NN, there is a Borel (continuous) function f from NN to X such that the preimage of A off is B, i.e., B = f- 1 (A). From the definition it is easy to see that no properly CA(IIg) set is Borel(Eg). In paticular, if rrg subset A. of a Polish space is properly rrg and the continuous preimage of a subset B of a Polish space, then so is B. Let JR be the set of real numbers. Let 11' denote the unit circle and I, the unit interval. Let E be 11' or I. We denote by C(E) the Polish space of continuous functions on E with the uniform metric d(f,g) = sup{lf(x) - g(x)J: x EE}. C('ll') can also be considered as the space of all continuous 2rr-periodic functions on JR, viewing 11' as JR/2rrZ. Let UC denote the set of all sequences of continuous functions on I that are uniformly convergent, i.e., UC= {(Jn) E C(I)N: Un) converges uniformly}. To each f E C('II'), we associate its Fourier series co n=-co ~ where f(n) = l 2 7r {2rr Jo . J(t)e-mtdt. Let n Sn(!, t) = I: f(n)eikt k=-n be that nth partial sum of the Fourier series of f. We say the Fourier series of f converges at a point t E 11' if the sequence (Sn(!, t)) converges. Similarly, we define the uniform convergence of the Fourier series of f. Let EC denote the set of all continuous functions with Fourier series convergent. According to a standard theorem [Kat}, the Fourier series off at t converges to f(t) if it converges. Hence we have EC ={f E C('ll') : 'Vt E [O, 2rr] ((Sn(f, t)) converges ) } ={f E C('II') : 'Vt E [O, 2rr] (f(t) = }i_.~ Sn(!, t)) }. 33 We define by NF the complement of EC. Let UC F denote the set all continuous functions with Fourier series uniformly convergent, i.e., UCF = {f E C(1r): the Fourier series off converges uniformly}. 3.3 Results Theorem [AK] EC is properly CA. (See [AK].) Proposition 3.1 UC F and UC are II~. Proof of Proposition 3.1. Let Q be the set of all rational numbers. We consider ']['as [0,211"] with identifying 0 = 271". By the definition of UCF, f E UC F {:=:::? S N(f) converges uniformly {:=:::? V a E N :3 b E N V c, d E N V e E Q (1sb+cU, e) - sb+dU, e)I :::; ~) {:=:::? f En LJ n n V(a,b,c,d,e), aEN bEN c,dEN eEIQin(0,27r] where V( a, b, c, d, e) is the collection off E C(1r) such that ISb+c(f, e )-Sb+d(f, e)I :::; 1 /a, which is closed, since the function J f---+- } ( n) is continuous. Hence U FC is II~. Similarly, so is UC, and we are done. D Lemma 3.2 The set C 3 ={a E NN: limn ...... 00 a(n) = oo} is properly II~. (See (Kel ]. ) This set will be used to prove our main theorem. Proposition 3.3 UC is properly II~. Proof. We define the function F from NN to C(J)N as follows: for each /3 E NN, F(/3) = (/3(~)). 34 Then it is easy to see that /3 E C 3 {=::? F(/3) converges {=::? F(/3) converges uniformly, since F(/3) is a sequence of constant functions. Clearly, F is continuous. Hence UC is the continuous preimage of C3 . By Proposition 3.1 and Lemma 3.2, UC is properly II~. D Theorem 3.4 There is a continuous function H from NN to C('IT') such that /3 E C3 implies H(/3) E UCF, and /3 r/:. C3 if and only ifH(/3) E NF. In particular, UC F is properly II~. By this theorem, we have the following corollary. Corollary 3.5 There is no E~ set A such that UCF ~A~ EC, 1.e., any E~ set, which includes UCF, must contain a continuous function with Fourier series divergent. Proof. Suppose a E~ set A satisfies UC F ~ A ~ EC. Then by Theorem 3.4 we obtain H- 1 (A) = C3 . Since A is E~, so is C3 . By Lemma 3.2, it contradicts our assumption. D From a basic fact of Descriptive Set Theory [Kel], any Borel set is coanalytic. So by Theorem [AK], since EC is properly CA, it is a very natural guess that the complement of C3 can be reducible to EC - UCF. In fact, we have the following theorem. Theorem 3.6 There is a continuous function ii from NN to C(1') such that /3 E C3 implies H(/3) E UCF, and /3 ¢:. C3 implies H(/3) E EC - UCF. In particular, UC F is properly II~. 35 In order to prove Theorem 3.4 and Theorem 3.6, we need the following criterion due to Dini-Lipschitz (Zy]. Let f be defined in a closed interval J, and let w(b) = w(b; f) = sup{lf(x) - f(y)I: x,y E J and Ix - YI~ b}. The function w( b) is called the modulus of continuity of f. The Dini-Lipschitz test. If f is continuous and its modulus of continuity w( b) satisE.es the condition w( b) log b --+ 0, then the Fourier series off converges uniformly. We introduce the Fejer polynomials, for given 0 < n < N E N and x E JR, . ~ sinkx Q(x,N,n) =2smNx L...i-kk=l ~ sinkx R(x, N,n) =2cosNx L...i-k-. k=l These two polynomials were used to prove that there exists a continuous function whose Fourier series diverges at a point. Lemma 3. 7 There are positive numbers C1 , C2 > 0 such that i.e., these polynomials are uniformly bounded in x, N, n. From Lemma 3. 7, we immediately have the following. Proposition 3.8 Let (Nk) and (nk) be any two sequences of positive integers, with nk < Nk and let O:k be such that 0:1 + 0:2 + 0:3 • • • < oo. Then the series converge to continuous functions. Proof of Theorem 3.4 Let a:k = 2-k, nk = l/2Nk = 22 k (k = 1, 2, 3, · · ·). We define H from NN to C(T) as follows: for all /3 E NN, 1 H(/3) = La:k /3(k)Q(x,Nkink)· 36 Claim 1 H is continuous and well-defined. Proof of Claim 1 By Proposition 3.8, His well-defined. By Lemma 3. 7, it is easy to see that H is continuous. D We divide the rest of proof in two parts. Case 1 limn---;.oo ,8( n) =J. oo. We want to show that H(,B) EN F. For each k E N, 2: ii(ii)(z) - /l/~Nk+nk (3.1) 2: ii(ii)(l) /1/~Nk -k 1 1 ( 1 1) 1 2k = O!k ,B(k) 1 + 2 + .. · + nk > O!k ,B(k) lognk = 2 ,B(k) log2 1 = ,B(k) log2 holds. Since limn---;.oo /3(n) =J. oo, there exists a p E N such that for infinitely many k's, ,B(k) = p. Hence the Fourier series of H(,B) does not converge, since in (3.1), we have l/plog 2 for infinitely many k's. Thus H(,B) EN F. Case 2 limn_, 00 ,B( n) = oo. We show that H(,B) E UCF. We will demonstrate that w(8;H(,B))log8--+ 0 as 8 --+ 0. Then by the Dini-Lipschitz test, this shows that the Fourier series of H(,B) converges uniformly. We take any 0 < 8 ~ 1/2 and define v = v( 8) as the largest integer k satifying 22 k ~ 1/8. By Lemma 5, we have the following inequality: 1 00 00 1 L ak,B(k)Q(x+8,Nk,nk)- L O!k,B(k)Q(x,Nkink) k=v+I (3.2) ~2C k=v+I 1 00 1 00 L O!k/3(k) ~2Csup{,B(k) :k>v} L O!k k=v+I k=v+I 1 } =4Csup { ,B(k) :k>v 2 -v-l 1 } log 2 =4Csup{,B(k) :k>v llogt5I' Now we calculate the rest of H(,B). We clearly have n Q'(x,N,n) = NR(x,N,n) + 2sinNx l:coskx, IQ'I ~NC +2n = nC', k=l 37 for N = 2n and C' = 2C + 2. By the mean value theorem, we have the following inequality: By (3.2) and (3.3), we have the following: (3.4) 1 I Iw(8;H(/3))log8 I ::; max{4Csup{/3(k): k > v},C 2 2-v ~ 2k-k L..-2 1 /3(k)}. k$v Now if 8-+ 0, then v -+ oo. So it suffices to show that the right part of (3.4) goes to 0 as v-+ oo. Since j3(v)-+ oo as v-+ oo, sup{l//3(k): k > v} goes to 0. We need to show that the rest goes to zero as v diverges to infinity. It requires the following easy fact. Claim 2 """' 22k -k < 22" -v+4 · L..,k<v Proof of Claim 2 Use induction on v. For v = 1, 22- 1 = 2 ::; 22-i+ 4 = 25 . 1 Suppose it is true for v. By the induction assumption, Lk<v 2 2k-k + 22"+ -(v+l) ::; 1 1 1 2 2"-v+ 4 + 2 2"+ -(v+l). It is enough to show that 22"-v+ 4 22"+ -(v+l)::; 22"+ + 4 . +. Letting f} = 22", one can verify this inequality. D Fix€. Take N 0 such that 1//3(k) < €for all k ~No. For this No, we choose N > No so that 2- 2"+v Lk$No 22k-k < € for all v ~ N. Then for all v ~ N, by claim 2, the following inequality is valid: 2c'2-2" 2v L 22k-k k<v < 2c'(2-2"+v L 22"-k_l_ + 2-2"+v L 22"-k_l_) k<N - 0 j3(k) = 34€. 38 No<k<v - j3(k) Hence the right side of (3.4) converges to zero as v goes to the infinity, i.e., as 8 --t 0. So we derive H(/3) E UCF. By cases, we obtain /3 rf_ C3 =? H(/3) E NF, and /3 E C3 =? H(/3) E UCF respectively. We have shown the first part. In particular, C 3 is the preimage of UCF. Hence by Lemma 3.2, the second assertion follows. We have thus completed the proof of Theorem 3.4. D Proof of Theorem 3.6 Instead of Q, we use R. As in the proof of Theorem 3.4, we define ii from NN to C(11") as follows: for each /3 E NN, The same proof as before will demonstrate that this function is continuous, welldefined and if limn--oo f3(n) = oo, then the Fourier series of H(/3) converges uniformly. So it suffices to show that if limn--oo /3( n) -=f. oo, then H(/3) E EC - UCF. Suppose limn--oo /3(n) -=f. oo. The representation of H(/3) as Fourier series is I: av sin vx. We see that I: av sin vx converges uniformly for 8 S !xi S 7r for any 8 > 0, since the partial sums of R( x, N k, n k) are uniformly bounded in k and x, 8 S !xi S 7r. The series I: av sin vx contains sines only, and hence it converges for x = 0, and so everywhere. Now we will show that I: av sin vx does not converge uniformly. It is easy to see that . 7r 3nk 2nk So if we let x = , then we have 4nk L av sin vx - L v=l v=l __ 2 _k __1_ L sin(2nk + v x > 2 _k __1_ sm. L _l av sin vx nk ) nk _7r /3(k)v=l 39 V - /3(k) 4 v=lv' since for all 1:::; v:::; nk, l11" ~ 3nk 2nk """" L.....t av sin vx - """" 1 sm . 411" vL."""" L.....t av sin vx ~ 2- k /3(k) . .t=l -;;1 v=l > 2-k 1 1 . 11" _ (3(k) ognksm4 I v=l (3.5) 4~k (2nk + v) ~%·So finally, ' nk log2 1 - J2 (3(k). Hence I: av sin vx does not converge uniformly, since in (3.5), the same value appears for infinitely many k's. Hence as in the proof of Theorem 3.4, we finish the proof of Theorem 3.6. D 40 Chapter 4 Complete coanalytic sets 4.1 Introduction The following are some examples of IIi-complete sets in Analysis and Topology. The set of all differentiable functions on the unit interval [Maz]; the set of all nowhere dense differentiable functions on the unit interval [Mau]; the set of all sequences Un)nEN of continuous functions on the unit interval such that Un)nEN converges pointwise; the set of all continuous functions f on the unit interval such that the Fourier series off converges everwhere [AK]; the set of all compact countable subsets of an uncountable Polish space [Hu]; the set of all compact subsets K of JR. 2 such that K is simply connected [Be]; the set of all compact subsets K of the unit interval such that K is a set of uniqueness [Kau] and Solovay (unpublished), are all IIi-complete. In this paper, we give some natural complete IIi sets occurring in Number Theory and in the study of countable Borel equivalence relations. A set of real numbers M is called a normal set if there exists a sequence (x n) n EN of real numbers such that for ally E JR, y EM if and only if (yxn)nEN is uniformly distributed mod 1. Rauzy (Raz] found a sufficient and necessary condition for a set to be normal. By a theorem of Hahn [Kel J, we can get a more exact necessary and sufficient condition. Namely, for a given subset M of real numbers, M is normal if and only if for all nonzero integer q, qB C B, 0 ~ B and B is Fuo· A sequence of real numbers is universal if and only if (xn)nEN, i.e., for all nonzero real numbers y, (yxn)nEN is uniformly distributed mod 1. Using results of [Rau] we show that the set US, of universal sequence of real numbers, is II~ -complete. A Borel equivalence relation on a Polish space X is countable if all its equivalence classes are countable. 41 For a given countable Borel equivalence relation Eon 2N, we denote by A(E) (F(E)) the set of all closed sets K such that En (K x K) is aperiodic (finite), i.e., for all x E K, the equivalence class of x is infinite (finite) in K. In many cases, we show that A( E) and F( E) are Iii-complete. We also prove that US is Iii-complete. 4.2 Notations and background We denote by N, Z, Q and JR the sets of natural numbers, integers, rational numbers and real numbers. For such a space X and a Y, XY denotes the set of all functions f from Y to X, with the usual product topology, X being endowed with its usual topologies (2={O,1} and N = {O, 1, 2, ... } being discrete). For given set X, xx is the subset of X without zero, i.e., xx = X -{O}. Let N- 1 = {O} U{ n~l }nEN· We consider the space N- 1 as the subspace of R We denote by N<N the set of all finite sequences of natural numbers. We consider the space 2N<N with the usual product topology with N<N being discrete. For s E N<N, lh( s) is the length of s. Lets, t E N<N. We say t Cs if there is k:::; lh(s) such that t = s I k. We denote by sAt the concatenation of sand t, i.e., lh(sAt) = lh(s) + lh(t) and sAt(i) = s(i) if i < lh(s), and sAt(j +lh(s)) = t(j) if j < lh(t). We put for each n EN ands E N<N, sA0 =sand sA(n) = sAn. For each n E N and s 0, s 1 , · · ·, sn+l E N<N, we inductively define s0As1 A··· Asn+I = (so As1 A··· Asnrsn+l· For infinitely many nonempty finite sequences s0, s 1, s 2 · · · E N<N, we may similarly consider so As 1 As2 A· · · as an element in NN. Let T C N<N. T is called a tree if T is nonempty and for all s E N<N, s ET=? Vt Cs (t ET). We denote by Tr the set of all trees on N. We may think that any tree Ton N is an element of 2N<N, i.e., Tr C 2N<N. Then we see that Tr is a closed subset of 2N<N, so a Polish space. T is called a wellfounded tree if for all a E NN there is n E N such that a I n <:J. T. We denote by W F the set of all wellfounded trees on N. Let X and Y be sets. Let x EX, BC Y and CCX x Y. Put Cx = {y E Y: (x, y) EC} and VBC = {x EX: Vy EB ((x, y) EC)}. Let X be a Polish space. Let A be a subset of X. A is called a Iii subset if there is a Borel set c of x x 2N such that A = V2 Nc. Equivalently, there exists 42 a Borel function from 2N to X such that l(2N) = X - A. Thus ITi is coanalytic. Note that for any Polish space Y, any Borel subset A of Y and any Borel subset B of X x Y, VA B is ITi. Hence any Borel set is ITi. A is called ITi-hard if for any Polish space Y and any ITi subset B of Y there exists a Borel function l from Y to X such that l- 1 (A) = B. If in addition to being ITi-hard, A is also ITi, then we say A is ITi-complete. Note that any ITi-hard set is non Borel. For a given set C ~ X, in order to calculate the exact complexity of C, one must first calculate an upper bound for C, by showing for example that C is IIi. And then prove a lower bound for C , for example by showing that C is IIihard. Usually, finding the upperbound is fairly easy. However, it can be difficult to prove the hardness of C. Since the IIi classes are closed under preimages of Borel functions, if B is IIi-hard (Di-complete) and B = l- 1 (C), where f is a Borel function, then C is Di-hard (Di-complete, if also C E Di). This remark is the basis of a common method for showing that a given set B is IIi-hard: Choose an already known Di-hard set B and show that there is a Borel function f such that B = 1- 1 (C). By a standard theorem in [Kel] or [Mos], WF is Di-complete. We will use W F to prove the last theorem. 4.3 The set of all universal sequences of real numbers We introduce a coanalytic set from Number Theory. Let (xn)neN be a given sequence of real numbers. For a positive integer N and a subset T of the unit interval, let the counting function A(T; N; (xn)neN) be defined as the number of terms Xn, 1 ~ n ~ N, for which the fractional part of Xn is in T. The sequence (xn)neN of real numbers is said to be uniformly .distributed modulo 1 if for every pair a, b of real numbers with 0 ~a< b ~ 1, we have . hm N-+oo A([a, b); N; (xn)neN) N = b-a. A set M of real numbers is called a normal set if there exists a sequence (,\n)neN in JR such that (xAn)neN is uniformly distributed modulo 1 if and only if x E M. 43 We denote by U the set of all pairs ( (,\n)nEN, x) of RN x IR such that (x,\n)nEN is uniformly distributed modulo 1, i.e., U = { ( (An)nEN, x) E RN X IR: (xAn)nEN is uniformly distributed mod 1 }. Thus for each (,\n)nEN E RN, Up,n)nEN is a normal set. Also for each normal set M, there exists (,\n)nEN E RN such that M = u(>.n)neN· We call (,\n)nEN a universal sequence if for every nonzero real x, (xAn)nEN is uniformly distributed mod 1. Hence for each (An)nEN E RN, (An)nEN is a universal sequence iff u(>.n)nEN = ]RX. We denote by US the set of all universal sequences, i.e. 1 US= { (,\n)nEN E RN: Vx E Rx ( (x,\n)nEN is uniformly distributed mod 1) }. Thus us= vRxu. Let X be a Polish space. Let (/n)nEN be a sequence of continuous functions from X to R We denote by C((Jn)nEN) the set of all real numbers x such that fn(x) converges to zero as n--+ oo, i.e., C ( (!n) nEN) = {X E IR : Jn (x) --+ 0 as n --+ 00}. A continuous function f : IR--+ C is said continuously ( c.d.p.) definited positive if for all finite sets A of real numbers and all functions c from A to C, we have the inequality L:(x,y)EAxA f(x-y)c(x)c(y) ~ 0. We recall .C the set of c.d.p. functions, .Co the set of c.d.p. functions such that f(O) = 1, and .Ct the set of f E .Co such that Vx E IR, J(x) ~ 0. Note that if f E .Co, we have f(x) = J(-x) and f(x) ~ 1; in particular if f E .ct, f is even and Vx E IR ,0 ~ f(x) ~ 1. Let v be a function from N to N. Let {Wi,j : i, j E N} be a family. Then (uk)kEN = (wn,o, · · ·, Wn,v(n))nEN means that for each j ~ v(O), Uj = wo,j and for each i ~ 1, j ~ v(i), Uv(o)+··+v(i-l)+j = Wi,j· We call by (uk)kEN the composition of ~Wn,01 · .. , Wn,v(n))nEN· Theorem H[Hahn] Let X be Polish. A subset A ~ X is F(f6 iff there exists Un)nEN a sequence of continuous functions from X to IR such that A = C( Un)nEN). 44 (See [Kel].) We recall now a famous theorem of Weyl [We]. Theorem W The sequence (xn) is uniformly distributed mod 1 iff 1 lim _ N_,.=N z= N . e2rrihxn =0 n=l for all integers h -=J 0. vVe use Theorem W to prove that US is IIi. By Theorem W, we obtain the following: ( (,\n)neN, x) EU {:::::} (x,\n)nEN is uniformly distributed mod 1 1 N . {:::::}Va E zx ( lim - ~ e2maXAn = N_,.= N ~ o) n=l {:::::}Va E zx Vb E N 3c E N Vd E N c+d _1_ ~ e2rriaXAn < _1_ c+d~ -b+l n=l {: : :} n n LJ n aezx Va,b,c,d, bEN cEN dEN where Va,b,c,d is the set of all elements ( (,\n), x) such that / c!d L:~!:~ e 2 rriaxAn / ~ Clearly Va,b,c,d is a closed subset of RN X JR. So U is a FtF6 set, i.e., a Borel set. Hence us is for us = vRX u and u is a Borel set. b!l. IIi' By a theorem of Hahn [Kel], we immediately obtain the following reformulation theorem of Rauzy [Raz]. Theorem R[Rauzy] For given B ~ JR, B is normal iff Vq E zx (qB ~ B), 0 r/: B and B is FtF6. Lemma 4.1 There exists FtF6 set B ~ JR x JR such that vRX B is Di-complete, (x, y) EB {:::::} (-x, y) EB for all (x, y) E JR x JR and Vx (Bx is normal). Proof of Lemma 4.1 We can choose a FtFo subset C of JR x JR such that Vx E JR ((x,O) r/: C), (x,y) EB {:::::} (-x,y) EB for all (x,y) E JR x JR and VRxC is 45 IIi-complete. Let B = {(x, y) EC: Vq E zx ((x, qy) EC)}. Then B is also a Fu8 set. Clearly for given x E JR, Bx is Fu8· Let (x, y) E B and q E zx. Then by the definition of B, (x, iqy) E C for all i E zx. Hence by the definition of B, we obtain (x, qy) E B. We thus have qBx C Bx for all q E zx. Since for all x E IR, Vq E zx (qBx ~Bx), Bx is Fu8 and 0 ~Bx, by Theorem R, Bx is normal. Clearly v'JRX B ~ v'JRX c. Suppose x E V'IRX C. Then Vy E ]RX ((x, y) EC). Thus Vy E ]Rx Vq E zx ((x, qy) EC), i.e., Vy E ]Rx ((x, y) EB). Sox E V'!Rx B. D Theorem 4.2 For Bas is in Lemma 4.1, there is a Borel function R from JR to IRN such that for all x, y E IR, (x, y) EB ~ (R(x), y) EU. By Theorem 4.2, we have x E V'IRx B iff Bx = JRX iff UR(x) = JRX iff R(x) E So we obtain V'!Rx B = R- 1 (US). Hence the function R witnesses that US is Di-hard, i.e., Di-complete, since US is Di. Thus we conclude: V'!RxU iff R(x) E US. Corollary 4.3 US is Iii-complete. Proof of Theorem 4.2 We fix B in Lemma 4.1. By Theorem H, we have a sequence (fn)neN of continuous functions from Rx IR to JR such that (x, y) EB ~ f n(x, y) --+ 0 as n --+ 00. Let x E R Then Bx = c( ((fn)x)neN). Replace Un)nEN by (gn)nEN where for each n EN and for all x, y E IR, 9n(x, y) = fn(lxl, IYI). Note that for all (x, y) E IR x IR, (x, y) E B iff (\x\, \y\) E B. Thus C( (gn)neN) = C( (fn)neN). We can suppose that for each n E N, 9n is even. We fix x E IR. Clearly, 9n(x, 0) does not tend to zero. So choose the least Nx E N such that for infinitely many n, l9n(x, O)j ~ 1/Nx. Lemma 4.4 Let 0 < 2r < J.,. Then in a Borel way, there exists a sequence of elements of£+ such that if Bx,r = C(U'k,xheN), we have (i) If for all enough large k, jgk(x, y)\ ~ r, then y E Bx,r, 46 (ii) If for infinitely many k, IYk(x, y)I > 2r, then y rJ. Bx,r· Proof of Lemma 4.4 Let F:;, = {y E IR : IYn(x, y)I ~ rand IYI ~ n~I }, and I<~= {y E [-n,n]: IYn(x,y)I ~ 2r}. Note that we can check in a Borel way whether or not F:;, and K~ are nonempty, since a continuous function on IR is totally determined on the domain Q. Hence without loss generality, we may assume that F:;, and K~ are nonempty. Then F:;,, J{~ are disjoint symetric to the origin and 0 rJ. F:;,. Take the least M(x,n) EN such that M(x,n) > M(x,i) for all i < n and 0 < 2 M(~,n) < infyEF: IYI and 0 < 2 M(~,n) < inf(y,z)EF:xK;; IY - zl. For each n EN, set Qn = [-n,n] n Q. We enumerate Qn = {q~n)}pEN· We define a sequence (M~,p) pEN as follows: Mxn,p = {z E Kxn : lq(n) inf lq(n) p - zl = yEK:; p - YI}. Then it is easy to see that for each p E N, M:;,,p is non empty and has at most two elements. We define a sequence (c~,p) as follows: x cn,p = sup z. zEM:;,p Claim 4.1 We can choose (c~,p)pEN in a Borel way so that {e~,p}pEN is a countable dense subset of J{~. Proof of Claim 4.1Since9n(x,·) can be determined on the domain Q, we can proceed in a Borel way to choose e~,p for each p E N. So the first assertion follows. We s~ow that {e;,p}pEN is dense in K~. Let k EK~. Then there exists a sequence (p1)1EN such that q~~) converges to k. It is enough to show that e;,p 1 converges to k. For all l E N, we obtain lexn,p1 - kl -<lexn,p1 - q(n)I + lq(n) - kl= yEK:; inf IY - q(n)I + lq(n) - kl Pl Pl Pl Pl ·~lk - qt>1 + lk - q~~>I-+ o, as l -+ oo. Hence e;,p 1 -+ k. So we have shown that {e;,p} is a countable dense subset of K~. 0 We let E = M(~,n). For each n E N, choose the least Nn E N such that C~c LJ (c~,i-~,e~,i+~)butC~~ LJ (c~,i-~,e~,i+~)· i5'Nn i<Nn 47 The least N n exists, since K~ is compact and C~ is dense in K~. Here we see that this procedure can be done in a Borel way, since C~ is countable. Since C~ is dense in K~, we then obtain the following: Say ,\o(x, n), ,\ 1(x, n), · · ·, ,\NJx, n) are the centers of corresponding intervals (c~, 0 - E, c~,o +t:), · · ·, (c~,Nn - E, c~,Nn + E). Then ,\i(x, n) E K~ for all i ~ Nn. Now let 1 - M(x,n)IYI </>~(y) = { 0 2 ' , for !YI ~ 2 M(lx,n); for !YI > 2 M(~,n). Then for all n E N and x E IR, ¢~ E £+. Let a~,Jy) = </>~(y) + ~ l<P~(y - ,\i(x, n)) + </>~(y + ,\i(x, n)) I· Then a~ i is c.d.p. Let ' ax. n,i f n,i,x - ax .(o)' n,1 r where i ~ Nn. Clearly f~,i,x E £+. We set ur,x) = (f[,1,x1 ... 'J[,Nn,x)nEN· We verify (i) and (ii). Suppose jgk(x, y)j ~ r for all enough large k. Then y E F{ for all sufficiently large k. We fix such k. Then ¢M(x,k)(Y) = 0. Since for all i ~ Nk, jy-,\i(x, k)I, jy+,\i(x, k)I > 2 M(~,k), ¢M(x,k) (y-,\i(x, k)) = ¢M(x,k) (y+,\i(x, k)) = 0. Hence Jr''i x(Y) = 0. Therefore, for sufficiently large k and for all i ~ Nk, fk,i,x(Y) = 0, i.e., for enough large k, hk(y) = 0. Soy E Bx,r· We have finished (i). Now suppose jgk(x, y)j > 2r for infinitely many k. If y = 0, then clearly y ~ Bx,r· So suppose y '/=- 0. Then for infinitely many k, y E K% and 2 M(~,k) < IYI· We fix such k. Then for some i ~ Nk, jy-,\i(x, k)I < M(~,k) holds. Hence by the definition of </> M(x,kb </> M(x,k) (y - ,\i( x, k)) is bigger than 1/2. Since 2 M(~,k) < jyj, we have ¢M(x,k)(Y) = 0. It is easy to see that a~,i 2: i· Since by the definition of ¢M(x,k), for ally E IR, ¢M(x,k)(Y) ~ 1, we obtain ~l¢M(x,k)(zi)+¢M(x,k)(z2)I ~ l. Hence we get Jr . ( ) < -1 -81 < - k,1,x Y - 4· 48 So we conclude y f/:. Bx,r· We have finished (ii). It is easy to check that our construction was carried out in the Borel way. D We will use Lemma 4.4 countably many times. It will be easy to see that we are constructing our function Rina Borel way. We let r(n) = 2 N.,(~+l). Then by Lemma 4.4, if Bx,r(n) = C( u;,~)hEN)' we have: (i) If for all enough large k, l9k(x, y)I :s; r(n), then y E Bx,r(n)' (ii) If for infinitely many k, l9k(x,y)I > 2r(n), then y f/:. Bx,r(n)· Clearly Bx= nnENBx,r(n)· We take for each k E N. Then (hf) is the sequence of c.d.p. functions with hk(O) = 1. It is easy to see that C( (h~)nEN) = nnEN Bx,r(n) = Bx. We need the following lemma [Raz]: Lemma 4.5 Let f be a c.d.p function with f(O) = 1, let Ka compact set of IR. and e > 0. Then there exists an integer N 2: 1 and a finite sequence u 0 , u 1 , · · ·, VN-l such that l N-1 L sup J(x) - N e(xuk) < e. xEK k=O We let K = [-n, n]. For each s, n E N ands 2: 1, we denote by Vs,n the set of all (wk)k~s-1 satisfying(*), i.e., 1 s-1 1 Vs,n = {(wk)k~s-1: sup h~(y) - Cke(ywk) < --}. yE[-n,n] S k=O n +1 L We. know that for each n E N, h~ is c.d.p. and h~(O) = 1. Lemma 4.5 thus implies that there exists a least v(n) 2: 1 such that Vv(n),n is a nonempty open set. Since we have the countable dense set UnEN Qn of UnEN Rn and for each s, n E N, Vs,n is open, we can calculate in the Borel way whether or not Vs,n is empty. We define a 49 well order -<v(n) in Nv(n) as follows: (ko, · · ·, kv(n)-1) -<v(n) (k~, · · ·, k~(n)-l) E Nv(n) ¢::==;> (ko < k~) or (ko = k~ and k1 < k~) or (Vi< v(n) (ki = kD and kv(n)-1 < k~(n)-1) for all (ko, · · ·, kv(n)-1),(k~, · · ·, k~(n)-l) E Nv(n)_ We take, in terms of -<v(n) 1 the least (l~n), · · ·, l~(~)-l) E Nv(n) such that (q 1(n), • • ·, q1(n) 0 ) E Vv(n),n 1 where Q = v(n)-1 {qm}mEN· We set q1(n) = Wn,i for each i ~ v(n) -1. Set • v(n)-1 l S~(y) = v(n) t; Then we evidently have c( (S~)nEN) e(ywn,k) for ally ER = C( ((h~)x)nEN) = c( ((fn)x )nEN). Make (u~)nEN the sequence composition corresponding to (wn,o · · ·, Wn,v(n)-l )nEN· For each n ~ 1, set 1 n L e(yu%) for ally ER n t~(y) = - k=l We require the following lemma [Raz]: Lemma 4.6 If (un)nEN is composed from the sequence (wn,o, · · ·, Wn,v(n)-1)nEN and if f is a function from JR to C, the sequence ( vln) L~~nJ-l J(wn,k)J converges to zero iff so does for (~I:~,:; f(wk)). By this lemma, we have C((S~)nEN) = C((t~)). We finally set R(x) = (u~)nEN· By Theorem W, for each y E JR, the sequence (yu~) is uniformly distributed mod 1 iff 1 n lim - Le( hyu~) = 0, n-+oo n k=O for all q E zx, i.e., y E U(u~) = UR(x) ifffor all q E zx (t~(qy)---+ 0 as n---+ oo). Hence for all x E JR, C(((fn)x)nEN) = U(u';.) = UR(x)- It is easy (but somewhat 50 complicated) to see that R is a Borel function from JR. to JR.N. So we complete Theorem 4.2. D 4.4 The sets arising countable Borel equivalence relations Let X be a Polish space. Let K(X) be the Polish space of all closed sets of X with the Hausdorff metric. Given Borel equivalence relation E on X, E is called countable if for all x E X, [x]E, the equivalence class of x, is countable. Let Ebe a countable equivalence relation on 2N. We denote by A( E) (F( E)) the set of all closed sets K such that En K x K is aperiodic (resp. finite), i.e., for all x EK, the equivalence class of xis infinite (resp. finite) in K. Hence A(E) ={KE K(2N): E I K is aperiodic} F(E) ={KE K(2N) : E I K is finite,} where E I K = E n K x K. We denote by F the countable Borel equivalence relation on 2N x N- 1 such that for all (x, a), (y, b) E 2N x N- 1 , (x, a)F(y, b) {::=::} x = y. We also introduce the basic equivalence relation E 0 on 2N as follows: for all x, y E 2N, xE0 y {::=::} there is am EN such that for all n ~ m, x(n) = y(n). Let Ebe a countable Borel equivalence relation on 2N. We calculate the upper bounds of complexities of A(E) and F(E). By definition, we have the following: K E A( E) {::=::} E I K is aperiodic {::=::} Vx E 2N (x r/:. Kor [x]E is infinite in K) {::=::} Vx E 2N (x r/:. Kor Vn EN ::3xo,x 1 ,·· · ,xn E [x]E (Vi,j:::; n (i =/. j =?Xi=/. x3) and Vi:::; n (xi EK)) {::=::} Vx E 2N(x r/:. Kor (x, K) EV); 51 K E F( E) ~ E I K is finite ~ Vx E 2N (x ~Kor [x]E is finite in K) ~ Vx E 2N ( x ~ K or 3n EN ::3xo,X1, · · · ,xn E [x]E (Vi~ n (xi EK)) and Vy E [x]E (Vi ~ n (y "I- xi) => y ~ K)) ~ Vx E 2N (x ~Kor (K, x) E W), where V is the set of all elements (K, x) such that Vn E N 3x 0 , x 1 , .. ·, Xn E [x]E (Vi,j ~ n (i -j. j => Xi -j. x1) and Vi ~ n (xi E K)) and W the set of all elements (K, x) such that ::Jn EN 3xo, x1, · · ·, Xn E [x]E (vi~ n (xi EK) and Vy E [x]E (Vi~ n (y -j. Xi)=> y ~ K). Let Xand Y be Polish spaces. Let A be a Borel subset of Y x X such that for all y E Y, Ay is countable. Then by a standard theorem in [Kel], {y E Y: 3x E Ay ((x,y) EA))} is Borel. The relation 'x EK', i.e., {(K, x) E K(2N) x 2N: x EK}, is a closed subset of K(2N) x 2N. Hence by the above two facts, it is easy to see that V and W are Borel. Finally, A(E) and F(E) are Ili. We need the following proposition to make the proofs of our theorems easy. Proposition 4. 7 Let E be a countable Borel equivalence relation on 2N. Assume vV = {x E 2N: [x]E n [x]e "I- 0} is uncountable. Then there is one-to-one continuous function f from 2N x N- 1 to 2N such that (x, a)F(y, b) ~ f(x, a)Ef(y, b) for all (x, a), (y, b) E 2N x N- 1 . Proof of Proposition 4. 7 We may find a Cantor subset C of W such that (i) For all x E C, x is a limit point in [x]E, (ii) For all x, y E C, xEy implies x = y. By a standard theorem of Feldman and Moore [FM], there exists a countable group G and a Borel action of G such that E =Ea. We enumerate G = {gm}meN· We define the function from C x N- 1 to 2N as follows: for all x E 2N and n E N, 52 T(x,O) = x, T(x, n~ 1 ) = 9m·X where mis the least m such that 0 < d(x,gm.x) < n~l and 9m·X is different from T(x, 0), · · ·, T(x, n~l ). Then T is an one-to-one Borel such that for all (x, a), (y, b) E 2N x N- 1 , (x, a)F(y, b) ¢:=? T(x, a)ET(y, b). So for each a E N- , there exists a dense G0 subset Sa of 2N such that T I Sa x {a} 1 is continuous. Let s = naEN-1 Sa. Thens is a dense Go subset in 2N. It is enough to show that Tis continuous on S x N- 1 . Suppose (xn, an) ~ (x, a) in S x N- 1 . If an 's end in the same value, it is obious. So an ~ 0 and for infinitely many n's an -/:- 0. Clearly we can assume an -/:- 0 for all n E N. Then we have d(T(xn, an), T(x, a)) ::; d(T(xn, an), T(xn, 0)) + d(T(xn, 0), T(x, 0)) + d(T(x, 0), T(x, an))+ d(T(x, an), T(x, a)) ::; an+ d(T(x, 0), T(x, an)) +an+ an = 3an + d(T(xn, 0), T(x, 0)) ~ 0, as n ~ oo. Hence T is continuous in S x N- 1 . We choose a Cantor subset K of S which is homeomorphic to 2N. We take f = T I K x N- 1 . Then f witnesses Propostion 7, since K is homeomorphic to 2N. So we are done. D Theorem 4.8 Under the same assumptions as Proposition 4. 7. A(E) and F(E) are IIi-complete. Recall now the following theorem: Theorem D[HKL] For any Borel equivalence relation Eon 2N, (a) either Eis smooth or, (b) there is an one-to-one continuous function h from 2N to 2N such that for all x, y E 2N, xEoy ¢:=? f(x)Ef(y) holds. Here E is called smooth if there is a countable Borel separates family. By Theorem D, for nonsmooth E, it is easy to see that A(E) and F(E) are IIi-hard using Theorem 4.8. In addition, if Eis a countable Borel equivalence relation, then A(E) and F(E) are IIi-complete. 53 Proof of Theorem 4.8 We have seen that A(E) and F(E) are IIi. We show the hardness of A(E) and F(E). By Proposition 4.7, it is enough to show for A(2N x N- 1 , F) and F(2N x N- 1 , F). We write A(2N x N- 1 , F) = A(F) and F(2N x N- 1 ,F) = F(F). We recall that WF is IIi-complete. We will somehow construct Borel functions .from Tr to K, ( 2N x N- 1 ) such that the preimages of A( F) and F( F) of these functions are precisely W F. This will prove that A( F) and F( F) are IIihard. First we show that A(F) is IIi-hard. We will construct a Borel fuction from Tr to K, ( 2N x N) which witnesses that A( F) is IIi-hard. Fix a bijection (, ) from N x N to N. Let TE Tr. We define (As,k)sEN<N,kEN as follows: for alls E N<N and k EN, Denote by As the set of all elements a of 2N such that for all k E N, (a )k E As,k, i.e., where for all k EN, (a)k(m) = a((k,m)). Inductively, we define (A;}sEN<N as follows: 2N· A T_ 0 ' for each n EN, A T(n) -_ { A(n)' 0, if (n} ET; o.w., for each s E N<N, m EN, if sAm ET; if 3t Cs (t =f. 0, t ET, Vn EN (rn rf. T) and sAm rf. T); if Vt C s (t =f. 0 and t E T =* 3n E N (tAn E T)), 3t C s( t =f. 0 and t E T) & sAm ~ T or Vt C s (t =f. 0 and t ~ T). We define (B'[) sEN<N as follows: for all s E N<N, ifs ET; o.w. 54 For each a E Nw, set C'!_ = nnEN A;;fn x B'£fn· We define the function H from Tr to K(2N x N- 1) as follows: for all TE Tr, LJ C'£. H(T) = aENN We should verify that the function H is well-defined, Borel and H- 1 (A( F)) = vV F. (i) H is Borel and well-defined. Proof of (i) Let TE Tr. Inductively, we define (T(n))nEN as follows: T(o) ={(mo) E N<N: (mo) ET}; T(n+l) = {(mo,···, mn+1) E N<N : (mo,···, mn+1) ET} LJ T(n). Note that for all TE Tr and n EN, Claim 4.2 H(T) = nnEN H (T(n)). Proof of Claim 4.2 Clearly H(T) c nnEwH(T(n)). Suppose (x,a) E H(T(n)) for all n E N. Then there exists {an} C NN such that (x, a) E C'!_~n), i.e., (x, a) E A.;~nf~ x B'£~~i for all k, n E N. We take an a from the closure set of {an}· Then there is a strictly increasing sequence (N n) of natural numbers such that aNn converges to a. We fix kin N. It is enough to show that x E A?:tk and a E n;fk' We let s = ak. Suppose s E T. Then for large enough n E N, s E T(Nn), i.e., by the definition, Af = A;(Nn) and BI= n;<Nn). We are done for this case. Supposes ti. T. Clearly a E B'['. We choose a sufficiently large n E N such that N n > lh( s) + 5. Since x E A;(Nnl and s ti. T(Nn), by the definition, there is t C s such that Clearly the previous relation is true for T instead of T(Nn). Hence Af = 2N, i.e., x EA;. So we obtain nnewH(TCn)) c H(T). This completes Claim 2. D Using Claim 2, we show (i). We refer to the fact that if X is metrizable and Kn E K(X), · · · C K1 C Ko, then limn_,. 00 Kn = nnEwKn· By Claim 2 and this 55 fact, we obtain H(T) = lim H(T(n)), n--><Xl since··· C H(T(l)) C H(T(O)). For each n EN, we define a function Hn from Tr to JC (2N x N- 1 ) as follows: for all T E Tr, Hn(T) = H (T(n)). We denote by Tr(n) the set of all trees T such that for alls ET, lh(s)::; n. Note that for any TE Tr(n), Hn(T) = UsETM A!' X BI, where TM= {s ET: Vn E N (s~n rf_ T)}. Then it is easy to see that for each n E N, Hn is well-defined. We need the following claim. Claim 4.3 Let n E N. Then H n is a Borel function. Proof of Claim 4.3 Since the function T 1-------+ T(n) is continuous, it is enough to show that Hn I Tr(n) is a Borel function. Set R = Hn I Tr(n)_ Let U be open in 2N x N- 1 . Then it suffices to show that R- 1 ({k E JC(X): KC U}) and R- 1 ( {k E JC(X): Kn U 'I= 0}) are Borel sets. We observe the following: KE R- 1 ({k E JC(X): Kc U}) {:=::} R(T) = u AY x B'f' {:=::}Vs E TM (A; x KE R- 1 ( {k E K(X) : Kc U}) {:=::} ( cu BI C U); LJ AY x B'f') nu 'I= 0 {:=::} :3s E TM (A; x B'f' nu 'I= 0). Hence we need only show that for given s E N<N with lh(s) ::; n, {T E Tr(n) A!' x B'[ C U} and {TE Tr(n) : A!' x BI n U '/= 0} are Borel sets. Let s E N<N. We define two functions P1,s anf P2,s from Tr(n) to JC(2N) and JC(N- 1 ) as follows: for each T E Tr(n), P1,s(T) = Af and P2,s(T) = B'f'. Clearly P1,s and P2,s are continuous. So is P1,s X P2,s· Hence {TE Tr(n) : Af X BI C U} and {TE Tr(n) : A!' x BI n U '/= 0} are Borel sets. We have finished the proof of Claim 4.3. 0 Since H = limn--= Hn, by Claim 2, H is the limit of Borel functions Hn. So H is a Borel function. This completes the proof of (i) 0 (ii) H- 1 (A(F)) = WF. Proof of (ii) It is enough to show that for all TE Tr, TE WF ~ H(T) E A(F) and T ~ WF ~ H(T) rf_ A(F). Suppose T E WF. For all a E 2N, A~ '/= 0 if 56 ::Jt ET (Vm EN (Cm r/:. T) and t ca), or 0 if o.w. Hence either C'[ = A;fn x n;fn for some n E N or C'[ = 0. So it is easy to see that H(T) E A(F). Suppose T r/:. W F. We take a E [T]. Note that for all a, /3 E NN, either C'[ = Cf or for all x E C'[ and y E Ch, x and y are not F-equivalent. Clearly C~ =/: 0 and c; c 2N x {O}, i.e., for all z E 2N x N- c; n [z]F contains at most one element. 1 , Hence H(T) r/:. A(F). D We have finished the first part of the theorem 4.8, i.e., A( F) is IIi-hard. We show that F(F) is IIi-hard. We slightly modify the proof of the first part. We construct ii from Tr to K(2N x N- 1 ) which proves that F(F) is IIi-hard. Let TE Tr. We define (D'[) sEN<N as follows: for alls E N<N, DT = s { {0} U { 0 k!l }k9h(s), ifs ET; o.w. For each a E NN, we define cr,o: and C!,o: as follows: cr,o: = nnENA;fn and C!,o: = UnENn;tn· We define ii from Tr to K(2N x N- 1 )) as follows: for each TE Tr, - H(T) = u T C 1T,o: x Cz,o:· o:ENN We define (iim) nEN and (Hm,n) nEN as follows: for each TE Tr and m, n EN, - u - ( = uC Hm,n Hm(T) = T T(m) C 1 ,o: x C2 ,o: o:ENN T) T(n) 1 ,o: y(m) x C2 ,o: . o:EN°N Then as in the first part, for each m, n E N, one can show that H m,n is Borel, iim = limn_,. 00 iim,n and for each T E Tr, iim(T) C iim+1(T). It is easy to see that H(T) = UmEN Hm(T) and as in the first part, ii is well-defined. Claim 4.4 Let X be a Polish space. Let Ko C K 1 C · · ·, Kn E K(X) for all n E N. Suppose K 00 = UnEN Kn E K(X). Then limn_,. 00 Kn = K 00 • Proof of Claim 4.4 Let U0 ,U1 ,··· ,Uk be open sets in X. We denote by B the basic open set related to Uo, U1 , ···,Uk, i.e., B ={KE K(X): Kc Uo & Kn U1 =/: 0 & ... & Kn Uk=/: 0}. 57 Suppose K 00 E B. It suffices to show that for large enough n E N, Kn E B. Since K 00 EB, we have As K 00 is the increasing union of Kn's, for sufficiently large n E N, the previous relation is true for Kn, i.e., Kn EB. Hence Kn converges to K 00 = UnENKn. So we are done. D We have seen that for each TE Tr, ii(T) is the increasing union of iim's. By Claim 4.4, we obtain that ii (T) = limm ..... 00 ii m(T). Hence ii is the limit of Borel functions Hm. So H is a Borel function. Similarly to the first part, we can show that ii- 1 (F(F)) = W F. We have finished the second part. Hence we completed the proof of Theorem 4.8. D 58 Chapter 5 The Kechris-Woodin rank is finer than the Zalcwasser rank 5.1 Introduction Zalcwasser [Za) introduced a rank that measures the uniform convergence of sequences of continuous functions on the unit interval. We apply the Zalcwasser rank to the Fourier series of a continuous function on the unit circle. Throughout this paper, we will only consider the Zalcwasser rank on the Fourier series of a continuous function. In [AK] it is shown that on EC (the set of all continuous functions, on the unit circle, with convergent Fourier series), the Zalcwasser rank is a Ili norm which is unbounded below w i.e., functions in EC are arbitrarily bad 1, in terms of this rank. Kechris and Woodin [KeW) defined a rank that measures the uniform continuity of the derivative of a differentiable function. We shall refer to this rank as the Kechris-Woodin rank. In fact, they have shown that on the set of all differentiable functions, the Kechris-Woodin rank is a Ili-norm which is unbounded below W1. Ajtai and Kechris [AK] conjectured that the Kechris-Woodin rank is finer than the Zalcwasser rank, meaning that for any function f, the Zalcwasser rank is less than or equal to the Kechris-Woodin rank. There is a fair amount of evidence supporting this conjecture. For example, the Zalcwasser rank is 1, i.e., the smallest possible number, for all differentiable functions f, whose derivative f' is bounded. On the other hand, on the set of all differentiable functions with bounded derivatives, the Kechris-Woodin rank is unbounded below w 1 (See [KeW]). Our main 59 result is an affirmative answer to this conjecture of Ajtai and Kechris. 5.2 Definitions and background Let JR be the set of real numbers. Let '1I' denote the unit circle and C('f) the Polish space of continuous functions on '1I' with the uniform metric d(f,g) = sup{lf(x) - g(x)I: x E '11'}. C('f) can also be considered as the space of all continuous 27r-periodic functions on JR, by viewing '1I' as JR/27rZ. We denote by D('f) the set of differentiable functions on '11'. Let N = {1, 2, 3, · · ·} be the set of positive integers and NN the Polish space with the usual product topology, where N is given the discrete topology. We briefly recall the definition of a complete Let A be a subset of X. A Di set. Let X be a Polish space. Di set A is called Di-hard if for any Polish space Y and IIi subset B of Y there exists a Borel function f from Y to X such that 1- 1 (A) = B. If also A is IIi it is called IIi-complete. Clearly any Di-hard set is non Borel. A norm on a set P is any function r.p taking P into the ordinals. For each such r.p, we associate the prewellordering Sep on P, x Sep y {:=::} r.p(x) S r.p(y). r.p is regular if r.p maps Ponto some ordinal,\, Two norms r.p and l/; on Pare equivalent if the two associated prewellorderings are the same (Sep=Stti), i.e., r.p(x) S r.p(y) {:=::} l/;( x) S lf;(y ). Every norm is equivalent to a unique regular norm. Given a Polish space X and a IIi subset P of X, we say that a norm r.p: P --+ Ordinals is a Di-norm if there are Di subsets R and Q of X x X such that (5.0) y E P =} [x E P & r.p(x) S r.p(y) {:=::} (x, y) t/: R {:=::} (x, y) E Q]. It is well known that if a subset A of a Polish space and its complement are both Di, then A is Borel (See [Mos]). In (5.0), we see that in a uniform manner for y E P, the set {x E P: r.p(x) S r.p(y)} is Di ((x, y) E Q) and the complement of a Di set ( (x, y) rt, R), hence a Borel set. In [Mos] it is shown that every Di-norm is equivalent to one which takes values in w 1 , the first uncountable ordinal. One of the basic facts is that every IIi subset P admits a Di-norm r.p: P --+ w 1 . (See 60 [Mos].) Hence it is very natural to look for a canonical norm on Iii sets that arise in analysis, topology, etc. We will introduce Iii-norms on the set of continuous functions with everywhere convergent Fourier series and the set of differentiable functions. From norm theory, we have the following fundamental theorem. (See Chapter 4, [Mos].) Boundedness Principle. Let X be a Polish space. Let P be a Iii subset of X and <p: P ---+ w 1 be a Iii-norm on P. Then P is Borel if and only if <p is bounded below w1 . With this basic principle, one can prove that a Iii set P is Iii non Borel by showing that some Iii-norm on P is unbounded below w1 . 5.3 The Kechris-Woodin rank We define a Di-norm on D(1'), which we refer to as the Kechris-Woodin rank [KW]. We consider 1' as [O, 27r] identifying 0 with 27T'. When we say U is an open neighborhood in 1', U is considered as the usual open set in R Let f be a function and I an interval with endpoints a and b. We define the following: ~J(I) = f(b) - f(a) b- a. Fix f E C(1') and€> 0. For each closed subset P of 1', we define the K-W derived set of P by af,:V (P) = { x E P :V open neighborhood U of x, 3 closed intervals I, J ~ U such that In Jn P # 0 and l~f(I) - ~f(J)I ~ €}. Bfew (P) consists of all€ badly behaved points of Pin terms of the derivative off. Clearly, ofew(P) is closed. We can then define the sequence (8few(P,a))a<wi by transfinite induction. Let ar,ew (P, o) = P. Bfew (P, a + 1) = 8few (8few (P, a)). For >. a limit ordinal, 8few (P, >.) = n 8few (P, a). a<..\ 61 Note that LJE> 0 8f€w(P,a) = UnEN8f,f(P,a). By transfinite induction, we define the sequence (8f w (P, a ))a<wi by setting 81KW (P,a) = ua nEN KW 1,; (P,a). Fact 5.lfED(1r) ¢=::? 3a<w 1 ,81KW (11',a)= 0. Using this fact, we can define the Kechris-Woodin rank on D(1r). For each f E D(1r), let lflKw =the least ordinal a for which 8fw(1r,a) = 0. We let b1 D(11') be the set of all functions whose derivatives are bounded in absolute value by 1. The following two facts appear in [KeW]. Fact 5.2 For each a < wi, there is a function f in b1 D(11') with lflKw =a. Fact 5.3 I· !Kw: D(1r)--+- w 1 is a Iii-norm. By these two facts and the Boundedness Principle, we have the following: Corollary[KeW] The sets D(11.") and b1 D(11') are Iii non Borel subsets of C(11."). 5.4 The Zalcwasser rank J~(n)einx We associate to each f E C(1r), its Fourier series S[f] ,...., ~oo L..tn=-oo ' ~ 1 1271" . where f(n) = J(t)e-mtdt. Let 271" 0 n Sn(!, t) = L f(n)eikt k=-n be the nth partial sum of the Fourier series of f. We say "the Fourier series of f converges at a point t E 11'" if the sequence (Sn(!, t))nEN converges. We will give a rank on EC, the collection of all continuous functions with everywhere convergent Fourier series. According to a standard theorem [Kat], if the Fourier series of f at t converges, then it must converge to f(t). Hence, EC ={f E C(1r) : Vt E (0, 211"], ( Sn(f, t) )nEN converges } ={f E C(1r) : Vt E [O, 271"], f(t) = lim Sn(!, t) }. n--oo 62 Let f E C(11'), P ~ 11' be a closed set, and let x E P. We define the value of the oscillation function off on P at x as follows. w(x, f, P) = inf inf sup{ISm(f, y) - Sn(!, y)I: m, n 2:: p & y E P & Ix - YI < 8}. 8>0pEN Thus the oscillation function of f on P measures how bad the uniform convergence of the Fourier series off, near x, is on P. For each f E C(11') and each E > 0, define the Z derived set of P by af,€(P) = {x E p: w(x, f, P) ;:::: E}. Fix f E C(11') and E > 0. We define (8f,€(P, a))Q<wi by transfinite induction as follows. Let 8f,€(P, 0) = P. 8f,€(P,a + 1) = 8f,€(8f,JP, a)). For limit ordinals.-\, 8j€(P, ,\) = ' n 8j€(P, a). Q<>. ' Note that u€>Oaf,€(P,a) = UnENaf,f;(P,a). Define the sequence (8j(P,a))Q<w1 by aj (P, a) = LJ 8f, f; ( P, a). nEN Fact 5.4 f EEC ¢:::=? ::la< w1, 8j(11', a)= 0. Using this fact, we define the Zalcwasser rank as follows. For each f E EC, let lflz =the least ordinal a for which 8j(11',a) = 0. Fact 5.5 I· lz: EC-+ w1 is a Ili-norm. Fact 5.6 For each a< w1, there is a differentiable function f such that lflz 2:: a. In particular, by these facts and the Boundedness Principle, D(11') is Borel. Also the following theorem is true. Theorem [Ajtai-Kechris] EC is ITi-complete. (See [AK].) For a reference to the previous three facts and theorem, see [AK]. 63 ITi non 5.5 An equivalent definition of the Zalcwasser rank As we have seen, the definition of the Zalcwasser rank is very natural. But when we compare the Zalcwasser rank to other ranks or attempt to calculate the Z derived set of ~ given closed subset and continuous function, the definition of the Zalcwasser rank is extremely difficult to work with. We give an equivalent definition of the Zalcwasser rank which is more practical. We need the following formula for Fourier series (See [Zy]). Proposition 5. 7 Let b be a fi.xed positive number less than 1r. Then (1) 21 Sn(!, X) - J(X) = - 8 0 7r sin nt <P x(t ) - dt + o( 1), t where <Px(t) = f(x + t) + f(x - t) - 2f(x). 2 In this formula, o( 1) tends to 0 for any x and the convergence to zero is uniform in every interval where f is bounded. Let f E C(11'), P ~ 11' be a closed set, and let x E P. We define f!(x, f, P) the analogous definition of the oscillation function as follows: 8 n(x, f, P) =inf inf.sup{ 6>0pEN 1 o • ¢y(t) smnt dt : n ~ p & y E p & Ix - YI< b}. t In order to calculate f!(x, f, P), we only need to know the local behavior off. But for w(x, J, P), we have to calculate the nth partial sum of the Fourier series off (which usually is not easy) before we can calculate w(x, f, P). From this point of view, f!(x, f, P) is more practical than w(x, f, P). For each f E C(11') and each E > 0, we define the K derived set of P by af,€(P) = {x E p: f!(x, f, P) ~ E}. As. in the definition of the Zalcwasser rank, we define (8f,€( P, a)) a<wi for each E > 0 and then (8f (P, a)) a<wi by transfinite induction. Theorem 5.8 Let f E C(11') and P ~ 11' be a closed set. For each a < w 1 , if f EEC, then af (P, a)= af (P, a) and if f ~EC, then af (P, a)=/= 0. 64 In particular, instead of Bf (P, a), we can use Bf (P, a) to define the Zalcwasser rank. Proof of Theorem 5.8 We fix f E EC. Let P be a closed subset of 'JI'. By transfinite induction on a, it is enough to show that for each E > 0, since ar (P) = Ue>O 8.f.E(P) and a; (P) = Ue>O at,E(P). Hence, it suffices to show that for x E P, 2 71" fl(x, J, P) ~ E ¢==:;. w(x, J, P) ~ -E. Let x E P. By the definition of w(x, J, P), for each 8 > O,p EN, (5.2) w(x,J,P) ~ ISn(f,y)- Sm(J,y)I for all n,m 2'. p & y E P & Ix - YI< 8. In (5.2) letting m-+ oo, by (5.1) we have (5.3) 2 [8 sin nt w(x,J,P) ~ ISn(f,y)- J(y)I ~; Jo </>y(t)-t-dt + o(l). Since f is continuous, in (5.3) o(l) tends to 0 uniformly on all of 'JI'. Hence by (5.3), we have (5.4) 2 71" w(x, J, P) ~ -fl(x, f, P). So w(x, J, P) > 271"- 1 € implies fl(x, J, P) ~ €. For the other direction, suppose w(x,f,P) < 271"- 1 €. Let Eo > 0 be such that w(x,f,P) < 27l"- 1 Eo < 271"- 1 €. Let E1 > 0. Then for some 8 > 0 and p E N, (5.5) for all n, m ~ p & y E P & Ix - YI < 8. Here we can take 8 ~ 71", since J is periodic. In (5.5) letting m-+ oo, we have (5.6) 2 71" ISn(f, Y) - f(y )I ~ -Eo + 2E1 65 for all n ~ p & y E P & Ix - YI < 8. Since (5.1) holds uniformly in 'f, by (5.1) and (5.6), we have the following for sufficiently large n and for all y E P & Ix - YI < 8. Hence we conclude n( x' f' P) ~ Eo + 3 /27!'-l €1. Since €1 is arbitrary, n( x' f' P) ~ Eo < €. It is not hard to see that of (P) -=/=- 0 if f </:. EC. It is easy to see then that the second part is a consequence of the first part. D 5.6 The Kechris-Woodin rank is finer than the Zalcwasser rank By Fact 5.2, the set b1D('f) has arbitrary Kechris-Woodin ranks below w1. But for any f E b1D('f), it is easy to see that the Fourier series off converges uniformly, i.e., the Zalcwasser rank of f is 1. Hence it is natural to guess that the Kechris-Woodin rank is finer than the Zalcwasser rank. We verify this now. Theorem 5.9 For given f E D('f), lflz ~ lflKw, i.e., the Kechris-Woodin rank is :finer than the Zalcwasser rank. In order to prove this, we need the following lemma. Lemma 5.10 Let f E D('f) and P be a closed set in 'f. Then for given E1, E2 > 0, Proof of Lemma 5.10 Suppose x E P-a1K€W (P). Then by the definition, 3 8 > 0 ' 2 such that V p < q,r <sin (-8 + x,8 + x) n [0,27l'] with [p,q] n [r,s] n P-=/=- 0 (5.7) l~f([p, q]) - ~J([r, s])I < E2. 66 We fix positive values 81, 82 such that 82 ::; 7r and x -8 < x -( 81 +82 ). In particular, by (5.7), 2 l</>yt(t)I = IL\f([y - t, y]) - L\f([y, y + t])I ::; E2 (.5.8) holds for all 0 < t < 82 and ally E P n [x - 81 ,x + 81 ]. Hence by the formula (5.1) and (5.8), we have the following: for ally E P n [x - 81 , x + 81 ], 21 ISn(f, Y) - J(y)I = - 82 0 1T sin nt <f>x(t)-dt + o(l) t 1182 ::; IL\f([y - t, y]) - L\f([y, y + t])l I sin ntldt + o(l) 1T 0 1182 ::; - 1T 0 1 e2 dt + o(l) = -82E2 + o(l). 1T Since our function f is differentiable, Proposition 5. 7 says that o( 1) tends to 0 uniformly in every interval, i.e., the value o(l) is dependent on n only. Hence for sufficiently large n and all y E [ x - 81 , x + 8i] n P, we have 1 ISn(f, y) - J(y)I ::; -82E2 + 82, 1T i.e., n(x, f, P) ::; 7r- 182E2 + 82 by the definition. Since 82 is arbitrary, we have n(x, f, P) = 0. Hence by Theorem 5.8, x r/:. af,f 1 (P). So we are done. D Proof of Theorem 5.9 Fix f E D(T). Suppose that for all ordinals a < w1 , of(JJ.,a) ~ arw(P,a). Since f is in D(T), by Fact 5.1, there is an Q'. < W1 such that 8fw ('.IT', a) = 0. Thus by our assumption, 8f ('.IT', a) must be the empty set, i.e., lflz is less than or equal to a. Hence Jflz ::; lflKW· It is enough to show that for any E > 0, 8f,f( P, Q'.) ~ ar,fw (P, Q'.) by transfinite induction on a. For Q'. = 0 or a, a limit ordinal, this is obvious. Suppose it is true for a. Then by Lemma 5.10, we have It is easy to see that for all closed subsets A and B of '.IT' with A ~ B, 8f,fw (A, a) ~ 8f,fw (B, a). Hence by the inductive asstunption, of,EW (of,E(".IT', a)) ~ of,EW (ar,;v ('.IT', a)) = of,EW ('.IT', a+ 1). 67 Thus 8f (P, a + 1) ~ arw (P, a + 1). Hence the theorem is established. o 5.7 The Denjoy rank and remark For each f E D(11'), there is a canonical rank, which is called the Denjoy rank, lflDJ, from D(11') to w1 which measures how long it takes to recover f from f' via the Denjoy process (See [Br]). We briefly introduce the Denjoy rank. Let g be a measurable function on 11' and P be a closed subset of 11'. We define the set of all singular points of g over P by S(g, P) = {x E P :g is not Lebesgue integrable on In P for any open interval I with x E I}. Let f E C(11'). Let ((an, bn)) be the sequence of open intervals complementing Pin 11'. We define the set of divergence points of f over P by D(J,P) = {x E P: L lf(bn)- f(an)I diverges for every I open interval I with x E I}. Here 2: 1 indicates that the sum is to be taken over all the intervals (an, bn) which are contained in I. For f E D(11') and each closed subset P of 11', we define the DJ derived set of P by 8f 1 (P) = S(J',P) U D(f,P). As before, we define the transfinite sequence (8f 1 (P,a))a<wi· For each f E D(11'), let If IDJ = the least ordinal CY. for which af J (11', CY.) = 0. For f E D(11'), it is known that lfiDJ = 1 if and only if f' is integrable. Hence IJIDJ = 1 implies that the Fourier series of f converges uniformly, i.e., lflz = 1. So we might guess that lflz ~ l!ID1· Conjecture For each f E D(11'), lflz ~ lflDI· T. Ramsamujh [Ra] has shown that lflDJ ~ lflKW· In fact he proved that for any € > 0 and CY. < W1' any Ei, €2 > 0 and CY. < W1' af J ( P, CY.) ~ ar,Ew (P, CY.). We have shown that for at,Et (P, CY.) ~ ar,Ei; (P, CY.). So it seems likely that 68 af,E(P, a) ~ af J(P, a) for any E > 0 and a, i.e., If lz ~ lflDJ· Recently, Ki [Ki3] has shown that this conjecure is not true. Namely for any ordinal a, any nonzero ordinal /3 and any countable ordinal"( with a, /3 < "(,one can construct a differentiable function f on the unit circle such that lflz =a+ 1, lflvJ = /3 + 1 and l!IKw = "f · 69 References [AK] M. Ajtai and A. S. Kechris, The set of continuous functions with everywhere convergent Fourier series, Trans. Amer. Soc. 302 (1987), 207-221. [Ba] A. Baker, Transcendental Number Theory, Cambridge Univerity Press, 1975. [Be] H. Becker, Path-connectedness, simply connected sets and the projective hierarchy, in preparation. [Br] A. M. Bruckner, Differentiation of real functions, Lecture Notes in Math., vol. 659, Springer-Verlag, Berlin and New York, 1978. [FM] J. Feldman and C. C. Moore, Ergodic equivalence relations and van Neumann algebras, I, Trans. Amer. Math. Soc. 234, 289-324. [GH] D. C. Gillespie and W. A. Hurwitz, On sequences of continuous functions having continuous limits, Trans. Amer. Math. Soc. 32, 527-543. [HKL] L. Harrington, A. Kechris and A. Louveau, A Glimm-Effros dichotomy for Borel equivalence relations, J. Amer. Math. Soc. 3(4) (1990), 903-928. [Hu] W. Hurewicz, Zur Theorie der analytischen Mengen, Fund. Math. 15 (1930), 4-17. [KasV] F. Kasch and B. Vollkmann, Zur Mahlerschen Vermutung uber S-Zahlen, Math. Annalen. 136 (1958), 442-453. [Kat] Y. Katznelson, An introduction to harmonic analysis, Dover, New York, 1976. [Kau] R. Kaufman, Fourier transforrns and descriptive set theory, Mathematika 31 (1984), 336-339. [Kel] A. Kechris, Classical Descriptive Set Theory, Springer Verlag, 1995. 70 [Ke2] A. Kechris, Lectures on definable group actions and equivalence relations, in preparation. [KeW] A. S. Kechris and Woodin, Ranks for Differentiable functions, Mathematika 33 (1986), 252-278. [Kil] H. Ki, Tbe Borel classes of Mabler's A, S, T and U-numbers, to appear in Proc. Amer. Math. Soc. [Ki2] H. Ki, Tbe Kecbis- Woodin rank is finer tban tbe Zalcwawsser rank to appear in Trans. Amer. Math. Soc. [Ki3] H. Ki, On tbe Denjoy rank, tbe Kecbris-Woodin rank and tbe Zalcwasser rank, preprint. [KL] H. Ki and T. Linton, Normal numbers and subsets of N witb given densities, Fundamenta Mathematica (2) 144 (1994), 163-179. [KN] L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences, John Wiley and Sons Inc., New York, NY, 1974. [Li] T. Linton, Tbe H sets in tbe unit circle are properly G 6rr, Real Analysis Exchage 19 (1993-94), 203-211. [LS] A. Louveau and J. Saint-Raymond, Borel classes and closed games: Wadgetype and Hurewicz-type results, Transactions of the American Mathematical Soci- ety, 304 (1987), 431-467. [Mah] K. Mahler, Zur Approximation der Exponential function un des Logaritbmus I, Journal Reine Angew. Math. 166 (1932), 118-136. [Mar] D. A. Martin, Borel determinacy, Annals of Mathematics, 102 (1975), 363371. [Mau] D. Mauldin, Tbe set of continuous nowbere differentiable functions, Pacific J. Math. 83 (1979), 199-205. [Maz] S. Mazurkiewicz, Uber die Menge der differenzierbaren Funktionen, Fund. Math. 27 (1936), 244-249. 71 [Mi] D.E. Miller, The invariant II~ separation principle, Transactions of the American Mathematical Society, 242 (1978), 185-204. [MorPP] vV. Morgan, C. E. M. Pearce and A. D. Pollington, T-Numbers From an l'v10 Set, Mathematika 39 (1992), 18-24. [Mos] Y. N. Moschovakis, Descriptive Set Theory, North-Holland, Amsterdam, 1980. [Ni] I. Niven, Irrational Numbers, The Carus Mathematical Monographs (Mathematical Association of America) no. 11, Quinn and Boden Co. Inc., Rahway, NJ, 1956. [Ram] T. I. Ramsamujh, Three Ordinal Ranks for the Set of Differentiable Func- tions, J. Math. Anal. and Appl. 158 (1991), 539-555. [Raz] G. Rauzy, Caracterisation des ensembles normaux, Bull. Soc. Math. France 98 (1970), 401-414. [Scl] W. Schmidt, On Normal Numbers, Pacific Journal of Mathematics, 10 1960, 661-672. [Sc2] W. Schmidt, T-numbers do exist, Symposia Math. IV, INDAM, Rome, 1968 (Academic Press, London, 1970), 3-26. [Wa] W. Wadge, Degrees of complexity of subsets of the Baire space, Notices of the American Mathematical Society, 19 (1972), pp A-714, A-715 (abstract 72T-E91). [We] ·H. Weyl, Uber die Gleichverteitung van Zahlen mod. Eins, Math. Ann. 77 (1916), 313-352. [Za] A. Zalcwasser, Sur une propriete du champes des fonctions continus, Sudia Math. 2 (1930), 63-67. [Zy] A. Zygmund, Trigonometric series, 2nd ed., Cambridge Uni. Press, 1959. 72