Fourier Analytic Applications to Number Theory . by Mariah Hamel B.A., Colby College, 2002 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L M E N T O F THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE. in The Faculty of Graduate Studies (Department of Mathematics) We accept this thesis as conforming to the required standard T H E U N I V E R S I T Y O F BRITISH C O L U M B I A October 5, 2004 © Mariah Hamel, 2004 ...... JUBCl THE UNIVERSITY OF BRITISH COLUMBIA L i b r a r y FACULTY OF GRADUATE STUDIES A u t h o r i z a t i o n In presenting this thesis in partial fulfillment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. 0^1 Name of Author (please print) Title of Thesis: "£pjA*r Date (dd/mm/yyyy) f V A ^ \ \ i koo\U/cVi',,ra Degree: Department of ^ooH \o( A p AJ0w>V»w r X V ^ Year: M C ^ V M . w^\\i.<, The University of British Columbia Vancouver, BC Canada g'rad.ubc.ca/forms/?formlD=THS p a g e 1 of 1 last updated: 5-Oct-04 11 Abstract In this paper we give expositions of Roth's theorem, Weyl's inequality and Vinogradov's three-primes theorem. In the proofs, we will frequently use exponential sums and more specifically the discrete Fourier transform. In the proof of Vinogradov's three-primes theorem we will use Hardy and Littlewood's circle method. This paper is intended to be self-contained and will hopefully be readable to someone with little background in the area. iii Contents Abstract ii Contents iii Preface v Acknowledgements 1 vi Introduction 1 1.1 2 Notation 2 T h e discrete F o u r i e r t r a n s f o r m . 4 3 Roth's Theorem 7 4 3.1 History 3.2 Roth's Theorem 3.3 Szemeredi's Theorem Weyl's inequality 4.1 History 4.2 Weyl's inequality 4.3 Applications to Uniform Distribution 5 V i n o g r a d o v ' s three-primes t h e o r e m 5.1 History, outline and setup 5.2 Minor Arcs 5.3 Major Arcs 5.4 Final calculations A A Minor Arcs Lemma. 7 8 15 21 21 22 27 '. . 31 31 35 , 44 49 55 Contents B T h e o r e m s from A n a l y t i c N u m b e r T h e o r y Bibliography iv 58 60 Preface When I first read about Vinogradov's three-primes theorem, I was overwhelmed. After examining a few sources, I came across Gowers' lecture notes [3] on the internet. His notes were much more readable and intuitive than any of the other sources I had seen. This paper originates with those notes. M y goal in this paper is to provide a gentle introduction to the applications of Fourier analysis in Number Theory. At the suggestion of my advisor, Izabella Laba, I began studying this area of Number Theory with Roth's theorem. Besides the applications to Szemeredi's theorem [4], the proof of Roth's theorem provided me with a nice way to become more comfortable with the discrete Fourier transform. Therefore, I have included a proof of this theorem here. Weyl's inequality is typically used in minor arcs estimates in applications of the circle method. I have included a proof of Weyl's inequality for quadratic polynomials as well as the related lemma A.0.5 which we will use in the minor arcs estimates for Vinogradov's three-primes theorem. The inclusion of Weyl's inequality provides for a fairly self contained proof of the three-primes theorem and also gives the reader important background material for other problems in this field. In the proof of Vinogradov's three-primes theorem my primary goal was to clarify Gowers' notes and "to fill in the gaps that may have resulted from the notes being written as a supplement to class lectures. I have chosen to omit constants since they originally distracted me from overlying ideas. Throughout this paper, I have tried to combine available sources and to to take the best elements from each of them. I have tried to provide the reader with a foresight in the form of outlines of proofs, where a lemma or theorem may be used, etc. I have attempted to clarify portions of the proofs that I found difficult upon first reading. And, finally, I have used the opportunity to write this thesis to become familiar with this area of mathematics. 3 VI Acknowledgements I would like to thank Izabella Laba for all of her help and encouragement with this project. I would like to thank David Boyd for agreeing to be the second reader. I would also like to thank Ben Green for discussions of material relating to this thesis and for suggestions and open problems in this area. i Chapter 1 Introduction The purpose of this paper is to provide an introduction to the application of Fourier analytic techniques in number theory. The theorems presented below combine methods from additive, combinatorial and analytic number theory. Specifically, we will prove Roth's theorem, Weyl's inequality and Vinogradov's three-primes theorem. In an effort to keep this paper fairly self-contained, we include an introductory section to the discrete Fourier transform. We also briefly describe the history of each theorem and summarize recent related results. The theorems presented all concern the structure of subsets of the integers. The following are natural questions: Does a subset contain an arithmetic or geometric progression? Does a given subset form a base of the integers? When is the distribution of a subset of integers 'random' ? What can we extrapolate about a subset from its sumset? The theorems in this paper formulate and provide answers to some of these questions. We say that a subset of nonnegative integers, A, is a basis of finite order k if N C A + A + ... + A = {ai + ... + a : a; e ^4}. For example, it is clear that A = {0,1,3,5,...} is a basis of order 2. In 1770, Waring stated without proof that every natural number is the sum of at most four squares, nine cubes, nineteen fourth powers, etc. Stated precisely he claimed that A — {0,1", 2 , 3 ,...} is a basis of finite order for each n. The Goldbach conjecture states that every even integer greater than or equal to six is the sum of exactly two prime numbers. This general type of problem can be characterized as an attempt to show that the natural numbers can be represented as solutions to arithmetic equations over a restricted domain. A n arithmetic progression of length k is a set of the form P = {a, a + s,a + 2s, ...,a + (k — l)s}. Szemeredi's theorem proves that an arithmetic progression of arbitrary length can be found in every sufficiently dense subset of the integers. A n example of a set which is not sufficiently dense, and hence does not satisfy the hypothesis of Szemeredi's theorem, is the prime numbers. Despite this, Green and Tao recently (May 2004) proved that the primes k n n Chapter 1. Introduction 2 also contain arithmetic progressions of arbitrary length. Another interesting result i n this area is that any sufficiently dense subset of the integers must contain two elements which differ by a perfect square. This result was first proved by Sarkozy and separately by Furstenberg, who came by the result as a corollary to his proof of Szemeredi's theorem. A third topic in this area is called inverse additive number theory. While we will not address this in detail the area may be of interest to the reader. Problems from this area involve the study of sumsets or difference sets. Let A be a subset of the positive integers. We define a sumset to be the set A + A = {ai + a<i : a i , G ^4} and similarly the difference set A — A. A n important result is Freiman's theorem which states that if the sumset A + A is small, then A must be contained in a generalized arithmetic progression. Freiman's theorem is related to the Balog-Szemeredi theorem which Gowers uses in his proof of Szemeredi's theorem. Many different methods can be applied to the above problems. A good illustration is Szemeredi's theorem which can be proved using combinatorial or ergodic or analytic methods. Each approach has its own advantage, and in this paper we will focus, on Fourier analytic techniques. Although this approach gives quantitative bounds (which ergodic methods do not give), we will not always provide them in an effort to keep the proofs as readable as possible. 1.1 N o t a t i o n Throughout this paper we will use the following notation: We will be estimating many exponential sums and therefore the following will be very useful. e(x) = e ™ 2 exp(x) = e x At times, we will find that it is easier not to keep track of certain constants and so if / and g are functions, g(x) > 0forall x and there exists a constant M such that \f(x)\ < Mg(x) for all x, then we will write /(*) = 0(g(x)) Chapter 1. Introduction or 3 « fix) g{x). The standard floor and ceiling functions are defined to be [a\ — max{n e Z : a > n} and [a] = min{n £ Z : a < n}. We define the fractional part of the real number a to be {a} = a — [a\. We will denote the distance from a real number a to the closest integer by 11or11 = min(|n — a\ : n G Z). We will also use some functions typically used in Number Theory: We define the Mobius function to be { 1 if n = 1, 0 if n is divisible by the square of a prime (—l) if n is the product of r distinct primes. The Euler ^-function is defined to be the number of positive integers less than n which are relatively prime to n. We can count the number of primes less than any real number x which we denote by 7r(a;). /Finally,, we define the von Mangoldt function to be I l°gP if P f ° some prime p and some m > 1, A[n) = < 10 otherwise . r ; n = m r We refer the reader to appendix B for some interesting results relating to these functions. 4 Chapter 2 The discrete Fourier transform In this section we will introduce the discrete Fourier transform and prove several related identities. We take / to be a function which maps the group Z J V , the set { 0 , 1 , N — 1} under modular addition, to the complex numbers. The Fourier transform f oi f preserves certain important properties and is often easier to study. The Fourier inversion formula will provide a way to recover the original function / . Although this necessary background comes ahead of where we must use it, we will attempt to provide some motivation. Roth's theorem states that any subset A of the numbers { 0 , 1 , N —. 1} of size. 5N must contain an arithmetic progression of length-three for any 5 > 0 assuming that N is sufficiently large. To prove Roth's theorem, we will cover the two cases defined by the size of the Fourier transform of the characteristic function of the set A. D e f i n i t i o n 2.0.1. Let f : Z/v —> C. Then for any r e C define the discrete F o u r i e r t r a n s f o r m of f to be N-l /(r) = £/(s)e(-rs/iV). In the case of Roth's theorem, we define A(x) to be the characteristic function of A. Then by definition 2.0.1 A(r) = J2x^o A(x)e(-rx/N) = YlaeA (~ /N)Therefore, the magnitude of the Fourier transform A is dependent on the distribution of points e(—ra/N) on the unit circle. We will see that small Fourier transforms, which means these points have a fairly even density on the entire circle, coincides with the set A being "random". For the remainder of this section, where the limits of summation are clear we will omit the bounds. e ra D e f i n i t i o n 2.0.2. Let f,g : Z N -> C. Then f*9(s) = ^f(t)g(t-s) t Chapter 2. The discrete Fourier transform 5 is defined to be the convolution of f and g. The next identity provides a relation between the discrete Fourier transforms of / and g and their convolution. Lemma 2.0.3. (JXg) = f(r)g(r). Proof: B y definition 2.0.1 and definition 2.0.2 we have = (f^9) J2^*9)(s)e(-rs/N) s s t = ]T f(t)W^)e(-rt/N)e(-r(t - s)/N) s,t = J^/(t)e(-rt/iV)p( )e(-rw/JV) U = f(r)W). a We will use the following identity in the proof of Parseval's identity, Plancherel's formula, the Fourier inversion formula and Roth's theorem. E«(-™/ao={ 7,7o 0 0 s=0 ' v Lemma 2.0.4. Parseval's identity. s r Proof: Using lemma 2.0.3 and equation 2.0.1 we have r r s = £(/*</)(*) s = = £<K-™/w) r N((f*g)(0)) Nj2f(t)W)-^ p- - ) 0 1 Chapter 2. The discrete Fourier transform Plancherel's f o r m u l a says t h a t t h e L 6 n o r m of the discrete Fourier trans- 2 f o r m o f ' / is p r o p o r t i o n a l t o t h e I? n o r m of /. Lemma 2.0.5. Plancherel's formula. Ei/( )i r 2 = i V r Ei/( )i s 2 s P r o o f : U s i n g lemma'2.0.4 let g(r) = f( )r T h e n f(r)f(r) = |/(r)| . 2 F i n a l l y , we are r e a d y t o p r o v e t h e F o u r i e r i n v e r s i o n f o r m u l a . Lemma 2.0.6. Fourier inversion formula. f(s) = N- J2f(r)e(rt/N). ' 1 r Proof: ' • - - ' . /V--' £ / ( r ) e ( r * / A ) r ^ " l E E / W ^ ^ ) ) ^ ^ ) - = N- Yl^2f{t)e{r{ -i)/N) l 8 r t t = N- (f(s)N) = f(s) b y e q u a t i o n 2.0.1. • l r ' • 7 C h a p t e r R o t h ' s 3.1 3 T h e o r e m H i s t o r y In this section we prove Roth's theorem on arithmetic progressions of length three. One of the first developments in the study of arithmetic progressions in sets of integers was given by van der Waerden in 1927 when he proved the following theorem: Theorem 3.1.1. Let k and r 6 N . Then there exist M £ N which depends on k and r such that if { 1 , M } is partitioned into any r subsets, then one of these subsets must contain an arithmetic progression of length k. In 1936, Erdos and Turan attempted to strengthen van der Waerden's result with their conjecture that an arithmetic progression of length k could be found in any sufficiently dense subset of the integers. In 1953, Roth made the first progress toward this conjecture by proving the case with k = 3. Szemeredi proved the conjecture for k = 4 in 1969 and generalized for all k in 1974. Later, Furstenberg was able to prove the theorem using ergodic theory. A third proof is due to Gowers in 2001 in which the methods of Roth are generalized. • " Theorem 3.1.2. Szemeredi's Theorem. Let k be a positive integer and let 5 > 0. Then there exists N = N(k, 5), such that every subset A of { 1 , N } such that \A\ > 5N must contain an arithmetic progression of length k. Roth's proof of the case k — 3 also provided a quantitative bound on the size of iV in relation to the density 5 of the subset A. We define N(5, k) to be how large N must be to guarantee that any subset A C { 0 , 1 , N — 1} with density 6 contains an arithmetic progression of length k. In Roth's proof, he was able to show that N(5,3) = Cexp(exp(c5 )). Szemeredi's proof gave the bound N(S,3) = C i e x p ( > - ) . In 1999, Bourgain gave the best bound known with N(5,3) < Cexp(5~ log (S' )). -1 C2 2 2 1 Chapter 3. Roth's Theorem 8 Szemeredi's proof of progression of length k also contained a quantitative bound on N(8, k), although it is extremely difficult to write down. Furstenberg's methods gave no bounds at all. Gowers' proof did significantly improve Szemeredi's bound. Gowers showed that N(S, k) — 2 * The next natural question is to find a lower bound for N(5, 3). The best bound known to date was given by Behrend [2] in 1946. In his argument 2 1 y/2 log 2 , £ he constructed a subset of {0, l , . . . , i V — 1} of size N v i o g w " ^ without arithmetic progression of length three. In other words, he showed that N(5,3) > Ci exp(c2 log (<5 )). His construction is based on the fact that higher dimensional spheres are convex, and so any line which passes through the sphere can intersect the sphere at most twice. There is also a result for longer arithmetic progressions due to Rankin [12]. He showed that for k > 1, there are subsets of { 1 , N } of cardinality at least iVexp(—C(logN) ^ ^) that do not contain arithmetic progressions of length 1 + 2 . The remainder of this chapter follows Gowers' paper " A New Proof of Szemeredi's Theorem" [4]. 1 2 -1 l k+1 fc 3.2 R o t h ' s T h e o r e m Before presenting the details of Roth's theorem, it is useful to give an outline of the proof. We begin with A C {0,1, 1} with | A | = '8N. If A is "random", then we will be able to show that A contains many arithmetic progressions of length three. On the other hand, if A is not "random", then we are able to choose a subset A' C A which has higher density in some subprogression of the integers. We must then determine if A' is "random" or not, and we iterate the argument until the theorem is proved. For this argument to work, we must count the number of necessary steps to ensure that we do not eliminate too many elements for the number of steps needed. Eventually we will have a set contained in an arithmetic progression with density one and at least three elements. We recall that for any set A G Z^r we can define its characteristic function To the characteristic function, we associate the balanced f u n c t i o n / of A defined to be f(x) = A(x) — 5. Chapter 3. Roth's Theorem 9 As a final note before we begin the details of the proof, we will need to distinguish between an arithmetic progression in the integers (an arithmetic Z-progression) and a progression modulo N (an arithmetic Z;v-progression). We will say that a set A is random if the Fourier coefficients of the balanced function are small. D e f i n i t i o n 3.2.1. We^say that the mapping f o/Zjv to the closed unit disk in C is a-uniform if \f(r)\ < ®N for all r ^ 0. If f is the balanced function of A(x) then we will say that A is a-uniform or random. We will now state and prove results which will be useful when a Fourier coefficient is large, in other words, when A is not random. L e m m a 3.2.2. Assume N is a sufficiently large prime. Pick integers r and s such thatO < r < N and 0 < s < N - 1 . Then the set { 0 , 1 , J V - 1 } can be partitioned into arithmetic Z-progressions Pj such that (1) y/s/2 < \Pj\ < y/s and (2) if x\,x% € Pj, then \x\r — X2r\ < 2s in ZjvProof: Partition the interval [0, N — 1] into N/2y/s intervals of equal length. Consider the set S- = {0, r, 2r,[N/y/2s] } modulo N. Then, by the pigeonhole principle, there must be two elements from S, kr and Ir, which lie in the same interval. Assume that k > I. Then \kr — lr\ < \/4s. Set u = k — l. Now we consider the set { 0 , 1 , — 1} modulo u. Each residue class will have [N/u\ or \N/u] elements. Now, \N/u] > [N/u\ > iV/(/V/V2s) = \/2s. Now will simply divide each residue class into subprogressions, Pj of sequential elements with the desired length; y/s/2 < \Pj\ < y/s. Then given £ i , x € Pj we have \x\_r — x%r\ < y/s • ru < y/s - V i s = 2s as desired. • 2 L e m m a 3.2.3. Let N be a sufficiently large odd integer and let f be a function such that f : {0,1,..., iV — 1} —> {z : \z\ < 1}. Assume that 1/(01 ^ N for some r ^ 0. Then the set {0,1,...,7V — 1} can be partitioned into arithmetic Z-progressions Pj such that \Pj\ > y/aN/327r and a Proof: Set s = aN/Sir and apply lemma 3.2.2 in order to partition { 0 , 1 , i V — 1} into arithmetic progressions Pj such that y/aN/327T < \Pj\ and given x\ and x<i € Pj we have \x\r — x%r\ < 2s = aN/iir in Zj^. Chapter 3. Roth's Theorem 10 B y a s s u m p t i o n a n d d e f i n i t i o n o f t h e F o u r i e r t r a n s f o r m , we h a v e „ AT-l aN <\f(r)\ = \^f(x)e(-xr/N)\ x=l j j xePj xePj T o see t h i s , we e s t i m a t e t h e i n s i d e s u m for f i x e d j as f o l l o w s . \J2f(^(-rx/N)\ i E / w ( _ e • ~ ( - -Xjr/N) + e(-xr/N) - e(- r/N))\ Xj xePj < iE / ( * m - ^ / A 0 | + l E / ( * ) ( e ( - xr'/N) - e ( - xGP, < i £ / ( * ) i + \Pj\ • max • max\e{-xr/N) - e( xePj < f £ / ( * ) i + IPjl-a/2 |xr — Xj-r| < aN/Aix b y l e m m a 3 . 2 . 2 t o s h o w < a/2. H e r e we use t h e fact t h a t \e(-xr/N) - e{- r/N)\ Xj T h e r e f o r e w e have p r o v e d aN — aN/2 desired. • = aN/2 < ]T). | Ylxep f( )\ x a s Let A c { 0 , 1 , N - 1 } swc/i tfiai |A| = <5JV. Assume that \A(r)\ > aN for some r ^ O and a = <5 /10. Then there exists an arithmetic X-progression P = {a,a + u, ...,a + mu) of length at least \/6 N/2>207r such that -^>6 + 8 /40. C o r o l l a r y 3.2.4. 2 2 l 2 P r o o f : A s s u m e r ^ 0 . C o n s i d e r t h e b a l a n c e d f u n c t i o n f(x) = A(x) — 5. W e first n o t e t h a t f(r) a n d A(r) are e q u a l sin c e Chapter 3. Roth's Theorem 11 N-l N-l JV-1 = ^TA(x)e{-xrlN)-5Y^<-xrlN) = Mr) W e apply l e m m a 3.2.3 t o p a r t i t i o n { 0 , 1 , N — l } into arithmetic progressions Pj s u c h t h a t \Pj\ > y/oN/32n = ^5 N/320*K 2 J2j I £ * p , f( )\ x and e ^ = <5 JV/20. S i n c e 2 n-l 7V-1 £/(*) = ]£>(*)-*) x=0 x=Q N-l = N-l E ^ ) - E 5 = |A| - 5N = °> we have E j iE xePj + E /(*)-= E x=o j (i E +E xePj- xePj /(*)> > 5 iV/20 2 T h e r e f o r e , t h e r e m u s t b e a t least one j s u c h t h a t | £ S \Pj\/20. T h i s i m p l i e s t h a t J2xePj f( ) ^ I : / I / 2 x 5 2 P 4 0 a > 6/2. T h u s , f o r t h i s c h o s e n j, w e have |AnP,| = E ^ ) = E(/(*)+s) xePj = j2m+s\p \ XtPj j •> ^ - 1 / 4 0 + ^ 1 s x i 6 p . /(^OI+ExeP- n c e H + a >' 6 > 0 f( ) x Chapter 3. Roth's Theorem as desired. 12 • L e m m a 3.2.5. Bertrand's Postulate: If n > 1 then there is a prime p such that n < p < 2n. We are now ready to prove Roth's theorem. T h e o r e m 3.2.6. Let S > 0, let N > e x p e x p ( C J ) (where C is an absolute constant) and let A C { 1 , 2 , N } be a set of size at least 5N. Then A contains an arithmetic progression of length three. _1 Proof: As previously outlined, we will prove Roth's theorem by considering the distribution of the set A . We recall that we will show that if A is uniform, then we can find a progression of length three. If A is not uniform, then we are able to find a subprogression of N where the density of A is higher. We iterate this argument, until we have a density of one. Finally, we will show that N is large enough to perform the number of iterations necessary to reach a density of one and to have at least 3 elements remaining in our set. Assume AT is a large postive integer and let c5 > 0. Assume A C { 0 , 1 , N Q — 1} such that | A | > <5 Ao. We will need N to be prime and since our argument is iterative, this argument allows us to choose A^ prime in each step. Applying lemma 3.2.5, we choose a prime N € [An/3, 2Ao/3]. 0 Let A = A n { 0 , 1 , N 0 C a s e 0: If 0 0 0 \A\ < 5 [1 0 0 - 1}. - 5 /lW)N, then we have 0 b4 n{A,...,A -l}| > 0 \A \-\A\ 0 0 >5 (N -(1-6Q/160)N) 0 = 0 S ((N Q 0 - N ) + c5 A/160) 0 >r5 (l + <y320)(A/o-A0 o Set 5 = 5 (l-c5o/160). 0 Case 1: Assume \A\ = S N . Let B = A n [N/3,2N/3] and assume \B\ < 6N/5. In this case, we have a small density in the middle third of the set { 0 , 1 , — 1} which must mean that A has a higher density in at least of of the other intervals [0, N/3) or [2A/3, N — 1]. In this case, without loss of generality, \A n [0, JV/3)| > 2(WV/5 = 65/5 • N/3. Chapter 3. Roth's Theorem 13 Case 2: Let a — 5 /10. Assume that A is not a-uniform.. Then there exists r ^ 0 such that \A{r)\ > aN. Here we have satisfied the hypothesis of corollary 3.2.4 and we know that there is an arithmetic progression such that A has higher density in this progression than in our original set. Specifically, the progression will have length at least y/PNffiOn and \A n P\/\P\ > <5 + 5 /40. This will be the basis for our iteration argument. We will consider (AnP) c P. 2 2 Case 3: Assume that none of the previous cases holds. In this case we are able to show that A contains an arithmetic progression of length three. By assumption, we know that |A(r)| < aN for each nonzero r G C . We would like to put a lower bound on the number of progressions of length three. We first note that an arithmetic progression modulo N is not necessarily an arithmetic Z-progression (consider 10,12,1 modulo 13 for example). However, the number of arithmetic Z-progressions (x,y,z) G Z must be greater than or equal to the number of arithmetic progressions restricted to (x, y, z) G A x B x B where B = A n [N/3,2N/3] as defined above. The triple (x,y,z) G A x B x B is an arithmetic progression modulo N if and only if x + z = 2y modulo N. We will now estimate the number of such triples. 3 E 1 = E E E 1 (x,y,z)£AxB' ,x+z=2y E xeA y€B z£B 2 e « y 2 x - )i ) z N r=0 N-l = iV" E 1 A(r)B(-2r)B(r) r=0 - i V " max | A ( r ) | ( E l ^ ( - 2 r ) | ) / ( E 1 2 r=l > 6\B\ 2 1 2 \B(r)\ ) 2 1/2 r=l a\B\N. Since our technique has counted trivial progressions (x = y = z), and there are \B\ such progressions, we want to show that 5\B\ —a\B\N > \B\+l. Now we use the fact that |J3| is at most and \B\ is at least 5N/5. Therefore, we can conclude that iV > (50 + V2500 + AP)/25 . In Case 3, we are able to produce an arithmetic progression of length three. Now we will begin our iteration argument for the other three cases. 2 3 Chapter 3. Roth's Theorem 14 First we must establish a method for finding subprogressions P such that AC) P has a higher density in P. The result of corollary 3.2.4 tells us that in Case 2, there exists an arithmetic progression P of { 0 , 1 , N — 1} of cardinality at least ^5 N/320n and | A n P | / | P | > 5 + 5 /40. We now apply this to our original progression { 0 , 1 , N — 1} by noting that 5(1 + 5/40) > 5n(l + 5n/320). Now since 7V is at most three times N, we know that this subprogression P must be at least of cardinality aNo/96n and \Arj fl P\ > 5 (1 + <W320|P|). In case 0 we can take A D {N + 1 , N - 1} such that \A n{N + l , N - 1}\/\{N,iVo - 1}| > 5 + 51/320. In case 1, we assume without loss of generality that \A D [0, N/3)\/(N/3) > 65/5. We now begin our iteration argument. We need to be sure of two conclusions: that it is possible to reach a density for which an arithmetic progression is guaranteed (in our case we will actually reach density one, and that our N is large enough so that we do not run out of possible subprogressions. Beginning with our first step, we start with a density of <5n. Then, in each subsequent iteration, we have the density increasing by at least 5g/320. Then we will reach a density of 25Q after at most 320<5Q steps. Now, at any point where we satisfy case 3, we can stop. However, there is no way to guarantee this. Instead we will reach density one. Reaching a density of 25Q after at most 320<5 steps, we can then see that we will reach a density of 45Q after at most 320(25 y ) further steps. In general, at step m where the density is 5 , we will reach a density 25 after at most 3205" further steps. We now calculate the maximum number of steps required to reach a density of one: 320(1/<S + l/25 + l/45 + ...) = 640/V Now, we ask what bound we must put on iV in order that this number of steps makes sense. First observe that at each step of the iteration the size of the subprogression chosen is about the square root of the progression of the previous step. Therefore after the first step we go from a progression of length JV to a progression of at least length (ciiVo) / . Then after 6405 steps we will have a length of at least 2 2 0 0 0 0 0 0 0 0 1 _1 0 1 r 1 m m 0 0 0 0 1 cN n 0 2 -1 '. Now, if we are still to have a progression of length three, then we must have cN^ ° ^ > 3. This is equivalent to showing NQ^ ° ^ > 3/c. Taking the log of both sides, we have logTVo > 2 o • 3/c. Therefore, we 2 2 6m it. AT \ c 6 4 0 must have iVn > e i c ^ 1 - >e log c-640,5- 1 x e . • Chapter 3. Roth's Theorem 3.3 15 Szemeredi's Theorem Now that we have proved Roth's theorem, we will be able to discuss Gowers' generalization of the proof used to prove Szemeredi's theorem. The outline of Gowers' proof mirrors that of Roth's theorem. If a subset A of { 0 , 1 , N — 1} is 'random', then one can show that A must contain a progression of length k. Otherwise, there is a subprogression, P C {0,1,...,N — 1} such that \A fl > S. The argument can then be iterated as in Roth's theorem. The most obvious way to generalize would be to use oj-uniformity to show that A contains an arithmetic progression of length k. Unfortunately the information given by a-uniformity does not seem to be sufficient to find progressions of length greater than three using known methods of estimation. Gowers' idea is to use a stricter definition of 'randomness' which lends itself to finding progressions of arbitrary length. However, this definition will of course complicate the iteration argument in the non-random case since fewer subsets of { 0 , 1 , i V — 1} will satisfy the new definition of random. We give here the definition of higher degree uniformity for all k, however, we will focus on the case with k = 4 in Szemeredi's theorem. D e f i n i t i o n 3.3.1. Assume f : Zjv —> [—1,1] and let x G Zpj. Then we define the difference function A ( / ; x) to be A(f;x)(s) = f(s)f(s-x). Given a set { ,x ,xj} one can iterate the difference function. In the case d — 2 (which we will need for progressions of length four) this iteration is straightforward: Xi 2 A ( / ; xi, x )(s) = A ( A ( / ; ii)-; x )(s) = f(s)f(s - x i ) / ( s ~x )f(s2 2 2 Xi - x) (3.3.1) 2 In general we have A ( / ; x i , ...,x ) = A ( A • • • ( A ( / ; x i ) • • • ;x ). d d D e f i n i t i o n 3.3.2. Let f be a function which maps Zjv to [—1,1]. Then we say that f is a-uniform of degree d if £ |£A(/;x ... a l j > ; c I )( )| <aJV*»- . S 2 2 In the case where d — 2 we say that f is quadratically a-uniform. Chapter 3. Roth's Theorem 16 Given d = 1 this definition means E iE X A (/; *)i = E i 2 s x E /(*)/(* - * ) i 2 < a N Z - s One can see that this definition implies a-uniformity as defined for Roth's theorem since E i E / ( x s ) / ( s - * ) i s 2 = E /(«)/ww/(^) = a—b=c—d iv- Ei/( )i 1 r 4 r which is easy to verify and follows from Chapter 2. We will give a more detailed outline of the proof that the set A C { 0 , 1 , N — 1} which is a-uniform of degree 2 and satisfies the hypotheses of Szemeredi's theorem must contain an arithmetic progression of length four. Before this outline, we would like to make a few comments regarding the non-uniform case. Here we assume that the subset A C { 0 , 1 , N — 1} is not quadratically a-uniform. Precisely, this definition states that there are at least aN integers k such that there exists r e ZN such that \J2 (x)A{x A - k)e(-rx/N)\ > aN. (3.3.2) X Denote the set of such k by B and define the function (f> : B —> Zyv by db(k) — r (if more than one r satisfies equation 3.3.2 we can just pick one such r for a given k). One would then like to show that the function <fi satisfies some sort of linear properties. To do this, one shows that there exist a N "additive quadruples" (a, 6, c, d) 6 B such that a + b = c + d and 4>{a) + 4>(b) = 4>(c) + (j)(d). One then uses Gowers' quantitative version of the Balog-Szemeredi theorem to show that there exists an long arithmetic progression modulo N on which <f)(s) = Xs+fi for many s e B. B y restricting cp to this large arithmetic progression, one is able to iterate the argument in a similar manner to the proof of Roth's theorem. Now we return to the a-uniform case. As before, we denote the characteristic function of the set A by A(x) and the balanced function associated with A by f(x). We say that A is quadratically a-uniform if / is quadratically a-uniform. Now we will use the characteristic function of A to count arithmetic progressions. If A(x)A(x — y)A(x — 2y)A(x — 3y) is one for some x and y then we clearly have an arithmetic progression. We will sum over all x and y modulo 4 2 4 Chapter 3. Roth's Theorem 17 iV to count the total number of progressions. Here we will assume, that N is prime. . ==• The number of Z ^ progressions contained in A is given by 1 £ £ x A(x)A{x - y)A{x - 2y)A(x - 3y) y = £ £ ( / ( * ) + W ( * - !/) + W ( * x 2y) + 8)(f(x - 3») + 5) y = N5 2 4 + ( £ £ S x - £ - y)f( - fWf( x 2 x y + £ £ / ( * ) / ( * x ^ (3-3.3) zy) (3.3.4) -3j/) (3.3.5) j/ + ££/(*x 2 3/ x + £ /(*)/(* - ^ - y)H 2 x - 2/)) (3-3-6) 3 y + ££/(*)/(*-y)/(*-2y)/(*-3?/), x (3-3.7) J/ where we use the fact that J2 f{ )~®Using this method we count progressions modulo N as well as the trivial progressions. This is a technicality similar to the one in the proof of Roth's theorem. What we have in the above sum is the expected number of progression, N 8 , plus an error term which we would like to show is small. Ignoring the modulo N technicality, we will show that the magnitude of each of the terms, (3.3.3), (3.3.4), (3.3.5), (3.3.6) and (3.3.7), is small, therefore forcing a positive number of progressions. This will give a rough outline of Gowers' method to show that higher degree a-uniformity guarantees progressions of length four. This problem can be generalized for progressions of arbitrary length using the same techniques. x X 2 4 L e m m a 3.3.3. Assume f : Z —» [—1,1] and f is a-uniform of degree d. Then there exists a function (3 : Zjv —• [0,1] such that Yl ez @( ) ^ and A ( / ; x) is (3 {x)-uniform of degree d—1. N x x N = a Chapter 3. Roth's Theorem 18 Proof: We prove this for the case when / is quadratically a-uniform. For A ( / ; x ) to be /3(x)-uniform of degree 1, we would like to show that £(£A(A(/;x); )) 2 5 s a = £ ( £ f( V( a s - ^( s x - )/( s a - s - )) x a 2 s < P{x)N 3 where YL P( ) x ^• But we know that = a X E E (E /(«)/(* x a - )f( a s s ~ ~ )) x a ^ 2 a N " since / is quadratically a-uniform. Therefore, we could take 3 ( x , \ A -- E (E.A(/:; ^)) ifx^() ? ' : 2 u ^ 1 : i ( \<*N- N~* E ^ o E ( A ( / ; x, ) ) a 5 2 < otherwise, to prove the lemma. • .::•-•-.-„,. • •• . We present the following theorem exactly as it appears in Gowers paper [4]. There does not appear to be an advantage to treating the theorem separately for the case k = 4. T h e o r e m 3.3.4. Let k>2 and let / i , f k be functions from ZA/ —* [—1,1] such that fk is a-uniform of degree k — 2. Then E/iW/2(«-y)-/fc(x-(fe-l)y) < a ^ N E 2 . We can see that using this lemma, we will be able to bound each of the terms (3.3.3), (3.3.4), (3.3.5) and (3.3.6) using linear uniformity (ie. auniformity of degree 1). For example, the sum (3.3.4) can be estimated using g(x) = f(x - y) to give E E tt )^ x x y x - y)tt 2 x -%)=£ x £ f( )9(x - vM* - %)> x y which we can estimate using theorem 3.3.4. The other term, (3.3.7), we estimate directly from theorem 3.3.4 using quadratic a-uniformity. Chapter 3. Roth's Theorem 19 Proof of theorem 3.3.4: We will prove this theorem by induction. For the casefc— 2 we have £/>(*)) (z ££/i(a0/2(*-l/) x y < a^ N . 2 2 since I X ^ / i t ^ ) ! is trivially bounded by N and lX)u/2( )l ^ a l N using a-uniformity of degree zero. For fc > 2 we assume that the inequality holds for k — 1. Since we assume that fk is a-uniform of degree k — 2, by lemma 3.3.3 we know that there exists a function (3 : Zjy —> [0,1] such that ^2 P(x) — aN and A ( / ; x ) is /3(x)-uniform of degree A; — 3. Now we would like to have a form to which we can apply this inductive hypothesis. w l 2 x E E fi(*)Mx-y)-fk(x-(k-i)y) ^fi(x)f2(x-y)...f (x-(k-l)y) k X X > 0 » - v)h(x - iy)..Mx x = E E E h( N - y)f^ x x = m y (ki) ) k U u X x. - «)••••'/*(* - ( - i)y)fk(x - x E E E M )M N - (k - y y v X - )-fk{x - (fc - 2)y)f (x - (fc - 2)y - (fc - l)v) v k -J ' . "•' = ' E E E A(/ ;*)(a)A(/ ; 2^)(x - y)...A(/ ; (fc - l)v)(x - (fc - 2)y) N a a; y 3 fc v <Nj2P((k-l)v) ~ N . 1/2k 2 2 V Therefore, E xei M )f2(x-y)...f ( -(k-l)y) < E N x x k yez N using the induction hypothesis. • a ^ N 2 Chapter 3. Roth's Theorem 20 This shows that each of the terms must be small as desired. We hope that this brief introduction to Gowers' proof will entice the reader to read his paper [4]. 21 Chapter 4 Weyl's inequality 4.1 History In this chapter we will state Weyl's inequality, prove a special case of the theorem and also give a simple application. Although Weyl's inequality has many applications, our primary reason for including it here is for its importance in applying the circle method, which we will use to prove Vinogradov's three-primes theorem. We will briefly describe the circle method here, however we leave the details for the next chapter. Hardy and Littlewood first developed the circle method in the early 1920s. They used it to prove Waring's problem, described in the introduction. It was soon realized that their method would have many applications, and the technique was refined most notably by Vinogradov, Vaughan and Wooley. Vinogradov's refinement enabled integration over the interval [0,1] rather than the original circle of integration used by Hardy and Littlewood. In the case of Waring's problem, we denote the number of representations of N as a sum of s positive k powers (ie N = x\ + ... + x ) by r (N). The first step in the circle method is to write r , (N) as an integral, which one then estimates. In this case, the goal is to show that the integral must be positive. In estimating the integral, one divides the bounds of integration into two disjoint sets called the major arcs and the minor arcs. One then shows that the integral over the major arcs is positive and is the main contribution to the entire estimate. The integral over the minor arcs is shown to contribute a small error term. It is in the estimate of the integral over the minor arcs that one is able to apply Weyl's inequality. th k s kiS k s We will also use Weyl's inequality to prove that the set S = {{P(n)} : n = 1,2,...} defined by the polynomial P{n) = an + fin 4- 7 is uniformly distributed in the unit interval whenever a is irrational. Weyl's inequality is a useful tool for proving a set is uniformly distributed because Weyl's criterion gives a set of equivalent conditions for a set to be uniformly distributed. The primary source used in this section is Montgomery's Ten Lectures 2 Chapter 4. Weyl's inequality 22 on the Interface Between Analytic Number Theory and Harmonic Analysis [9]. We also consulted Nathanson [10] and took examples in the applications section 4.3 from a course at the University of British Columbia taught by Izabella Laba in the spring of 2004. 4.2 Weyl's inequality T h e o r e m 4.2.1. Weyl's inequality Let P(x) = Y^=o j ^ where a ; G 8 for each i and \ak — a/q\ < q~ for some a, q G Z and (a,q) = 1. Then a x 2 N e ( P H ) < C^N^iq- 1 + N' 1 + qN~ ) k n=l We lemma primes qi,q2, lemma will prove Weyl's inequality for P(x). = a + fix + 7 . The following will be used for Weyl's inequality and in proving Vinogradov's three theorem. We will also prove that given a Q there exists a sequence ••• such that lim _ <7jv and q^ < N such that \ot — QJV/^ATI < q^ in 4.3:4 which allows "us to make use of Weyl's inequality^ •>+ 2 2 n >00 k L e m m a 4.2.2. Let a, fi eR and let.M, N £ N . Then Proof: The sum is trivially bounded by N since £ e{an + fi)\<Y^ \( e an + fi)\<N. Since e(an + fi) = e(an)e(fi) we can take fi = 0. To show the other bound, we have Chapter 4. Weyl's inequality E l ( OI m<u<n e ai 23 |e(am) E e(au)\ 0<u<n—m _ e(a(n — m + 1)) — 1 e(a) - 1 2 = < |e(a) - 1| 2 |e(a/2)-e(-a/2)| 2 |2zsin 7ra| = | sin7TQ;| _1 <(2\\a\\)-\n T h e o r e m 4.2.3. Weyl's inequality for quadratic polynomials Let P(x) = o? + (5x + 7 w/tere a € R. Assume \a - a/q\ < q~ , a, q G Z and (a, g) = 1. £>e/me 5 = £ n = i e(P(n)). T^en 2 \S\ < {N/^q-+ y/Nlogq + ^/qlogq) Proof: To prove Weyl's inequality, we will estimate \S\ as follows. B y definition, 2 Chapter 4. Weyl's inequality |S| = | f > ( P ( n ) ) | a 24 2 n=l N = E e(P(m) - P(n)) n,m=l AT JV-n = E E ra=l = e(P(n + / i ) - P ( n ) ) h=l—n E E h=l-N l<n<N,l-n<h<N-h N-l N-h E ( = N+E /i=l ( p n + h ) - w ) p + e ( p ( ) n _ p ( n + h ) ) - E h-:\ r ( N-h = N + E A e n=l N-l < e^n-f^-P^)) 2Re(e(P(n + fc) - P(n))) I) • 1 , + E i E ( ( 2 e h=l p n + ^ ) - ( ) ) i p n : . .... : n=l Noticing that P ( n -(- /i) — P(n) = 2ahn + ah + /3h = o/n + (3' where we take a! = 2a/i and /?' = ah + /3h, we can apply lemma 4.2.2 which gives us the bound 2 2 JV-l |S| < N + 2 j 2 2 m i n i N (2||2a/i||) } -1 /i=i 2N < N + 2E min{iV,|\ha\ /i=i We will consider the case when a is rational and the case when a is not rational. Case 1: If a = a/q where (a, q) = 1 and a, q £ Z, then we have Emin{ATj|^|r } = E^{iV,||Ma/g)||- } 1 71=1 1 /l=l Chapter 4. Weyl's inequality 25 1-1 • . . /i=l. • 9-1 ' - v - '• < N+ J2\\h(a/q)\\- 1 '' ' >* ' = N+ ^2\\h/q\\- 1 h=l 9-1 h=l < N + Cq log q The fourth step in the above estimates holds since {a, 2a,(q — l)a} give a complete list of residues modulo We also note that the same bound works when we consider any sum Ylh=kq+i We partition 1 , 2 N into blocks of length q. We will have less than or equal to 2Njq + 1 such blocks. Therefore, we have n o w |5| < N + (2N/q + 1){N + Cqlogq) 2 < N /q + N\ogq + qlogq. 2 Finally, taking the square root, we have l ^ l <^N/^+y N\ogq+ / x/qhgq. Case 2: We assume \a — a/q\ < q~ , a, q e Z and (a, q) = 1. As in case 1, it will be useful to split the sum we wish to estimate into separate sums. In this case, we fix a block of q integers, M < n < M + q. Write ct = a/q + r where r < l/q . Then for every u there are at most 3 choices of n in the specified interval such that \\na — u\\ < l/2q. To see this, we will assume \\na — u\\ < l/2q and prove that there are at most three possibilities. Let n = M + m, v = u — Ma and 1 < m < q. Then 2 2 \\ma — v\ \ = \\Ma + ma — v — Ma\\ = .||(M + m)a -v + v - u\\ = \\na — u\\ < l/2q Chapter 4. Weyl's inequality 26 by assumption. Further, \\mr\\ < q\r\ < 1/q. Therefore, \\ma/q — v\\ = \\majq + mr — mr — v\\ — \\ma — v — mr\\ < \\ma — v\\ + \\mr\\ <l/2q + l/q = 3/2q. Therefore, there are at most three distinct choices of m and hence at most three distinct choices of n for which \\na — u\\ < l/2q. LetS={l/q,2/q,...,(q/2)/q} Then M+q E M=q min(AM|Hn = (2/g)E h=M+l u€S E 9 ueS + - E i M r h:\\ha-u\\<l/2q (2/g)E ue5 • . 1 h=M+l < (2/ ) E ( 3 i v + <3iV m^Wl'lM!' ) 1 ) ' ((IHI-i/Sg))- E ' 1 fc||/ia-u||<l/29 <3iy + 2 E a / ( I N I - i / 2 ) g ui-S • q/2 < 3N + 2 E l/(m/q - l/2q) <3N + 2qlogq. (4.2.1) Now using the same argument as case 1 we have 2N E n u n ( J V " , l / | | / i a | | ) < 10(N /q + Nlogq + qlogq). 2 h=l Therefore, we have \S\ < N + (N /q + Nlogq + q\ogq). 2 2 Taking the square root of both sides, we have the desired result. • Chapter 4. Weyl's inequality 4.3 27 Applications to U n i f o r m Distribution D e f i n i t i o n 4.3.1. We say that a sequence ai,a2,... G [0,1] is u n i f o r m l y d i s t r i b u t e d if for every a € [0,1] lim -^[{n : 0 < a < a,n < N}\ = a. n We will now state and prove Weyl's criterion. T h e o r e m 4.3.2. Weyl's criterion The following are equivalent: (1) The sequence { a } ^ is uniformly distributed in the interval [0,1] (2) For each k G Z and k ^ 0, J2%=i e(-ka ) = o{N) (3) If F{x) is a bounded and Riemann integrable function on [0,1], then limiv^oo £ £ L i F{a ) = F{x)dx n = 1 n n Before proving Weyl's criterion, we give the immediate consequence that the set {an} where a is irrational is uniformly distributed. By Weyl's criterion, condition (2), we can consider the exponential sum N-l jE e ( - f e ( a n ) ) < min(JV, ( 2 | | H I ) _ 1 ) n=l < i/(2||HI) = o(N\ ... since ||fca|| 0 since a is irrational. P r o o f o f W e y l ' s c r i t e r i o n : (1) (3) Since we assume F Riemann integrable, we can compute the left hand side of (3) using Riemann sums. Let € > 0. Then there exists n such that if we partition [0,1] into n intervals, 0 = XQ < X\ < ... < x — 1 and let Mj = max .< < . F(x) we have Y ]ZlM Ax -^F{x)dx<e. n J j j 1 1 1 +1 Chapter 4. Weyl's inequality 28 For right hand side of (3) we have iV" f > ( a O = E A T 1 £ 1 Fiat) j=0 l:ai€[xj,Xj+l) n-l k=l [x^Xj+Ml-Mj < ^l/JV|{*:a,e 3=0 n-l j=0 < [ Jo F(x)d.x + 2e as N —* oo since l m i A r ^ o o 1/N\{k : a G [x_,-,Xj i)}| = x — definition of uniformly distributed. Using lower Riemann sums in the same way, we get limjv—oo k Jo F(x)dx — 2e. J + 1 + Xj = Ax.,- by- Y2k=i F( k) a Therefore, we can conclude limyv^oo l/N ^2 k=1 JQ F(x)dx as desired. (3) F(a ) k = (2) Set F(x) = e(-kx) with Ac 7^ 0. Then by assumption; w ,-1 lim 7 e(—ka ) = / ^t^i ° e(—kx)dx n N J = —Jfc- e(—fca;)|J 1 =0 (3) Then (1) Set F(x) = X[o,a)( ) where x is the characteristic function. x iV lim |{n < N : 0 < a < a}\ = lim i V " N—>oo n TV—>oo = / Jo 1 VX[o,a)M ^—' n=l X[o,a)(z)dx = OJ (2) (3) Here we give an outline of the proof. We can approximate Riemann integrable functions with step functions, step functions with continuous functions and continuous functions by trigonometric polynomials. Chapter 4. Weyl's inequality 29 Since lim N' 1 7V-*oo n=l . \x ' Jo by assumption and N lim N' 1 = 1 n=l I ldx, the equality must hold for trigonometric polynomials and therefore, must hold for all functions by approximation. • Now we will prove that the set defined by {P(n)} given by the polynomial P{x) = ax + fix + 7 is uniformly distributed if a is irrational. 2 L e m m a 4.3.3. Given a £ R and N £ N, there exists 0 < q < N such that \\aq\\ < 1/JV. Proof: Consider the set S = {0,1, {a}, { 2 a } , { ( J V - l ) a } } . Partition [0,1] into intervals [i/N,(i + l)/N}. Then we have N — 1 intervals and N + 1 elements of S. Hence, by the pigeonhole principle, there must be two elements of 5 contained in the same interval. Assume those two elements are {axi} = \axi — y i | and {0:2:2} = |OJ£2—2/21 - Without loss of generality, assume that xi > x . Then \{ a-yi) - (x a-y )\ = \(xi~ x )a-(y!-y )\ < 1/N. Thus, \\(xi — x )a\\ < 1/N as desired. • 2 Xl 2 2 2 2 2 L e m m a 4.3.4. If a fi Q then there exists qi, q ,... such that l i m ^ o o q = qN < N and \a — a^/qN] < l/<7Jv f some a^. 2 n 00, or Proof: Consider min |a — a/q^\ = l/qNmm \aqx — a\ = 1/q^\\aq^\\. B y lemma 4.3.3, for each N, there exists qN such that ||C«/JV|| < 1/AT < 1/qNSince we require a to be irrational, ||a<7jv|| 7^ 0 for any q. • Now the desired result is a simple corollary. a a C o r o l l a r y 4.3.5. The set {{P(n)} : n = 1,...,N} is uniformly distributed in [0,1]. Proof: By Weyl's criterion, it suffices to prove N Y^e(kP(n)) = o(N). n=l Chapter 4. Weyl's inequality 30 For each N, choose and such that \a — a /q \ < l/q as given by lemma 4.3.4. Then, applying Weyl's inequality to kP(n), we have n | J2 n N N-l e(kP(n))\ < C(N/q N n=l = o(N).a + y/N\ogq N + vWogflv) 31 Chapter 5 Vinogradov's three-primes theorem 5.1 History, outline and setup In 1742, Goldbach wrote a letter to Euler conjecturing two statements that would remain open problems for years to come. The first statement was what is today the Goldbach conjecture- namely that any even integer, greater than or equal to six, can be written as the sum of two odd primes. The second statement asserted that every odd integer, greater than or equal to nine, can be written as the sum of three odd primes. It is clear that proving the first statement would guarantee the second. Although the Goldbach conjecture remains open, Goldbach's second conjecture has been proven for sufficiently large N. The first progress was due to Hardy and Littlewood [5] with an application of their circle method in 1923. They proved that if N was sufficiently large, then the conjecture holds assuming the weak generalized Riemann hypothesis. In 1934, using a refinement of the circle method, Vinogradov [15] was able to remove the dependence on the generalized Riemann hypothesis. In 1946 Linnik [8] proved the theorem for large N using Riemann-Hadamard's method of L-series and contour integration. More recently,, in 1997, Deshouillers, Effinger, te. Riele and Zinoviev [6] proved the complete conjecture that every odd number greater than six can be written as the sum of three prime numbers where they assume the generalized Riemann hypothesis. Their proof is divided into two parts. First, they proved the theorem for N > 10 . Second, a computational result (independently due to Saouter [13] and Deshouillers- te Riele) shows that the theorem must be true for primes greater than or equal to seven. The proof of Vinogradov's three primes theorem that is given here follows the lecture notes of Gowers [3] and gives neither a bound on how large N must be nor an asymptotic formula for the number of ways which we can write a large number N as the sum of three prime numbers. We would also 4 20 Chapter 5. Vinogradov's three-primes theorem 32 like to cite here Nathanson's text [10] and Vaughan's text [14] which were very useful in writing up this material. The current bound given for the size of N is 1 0 < N and was proved by Chen and Wang [7]. We define 43000 r(N) = £ 1 to be the number of ways to write ./V as the sum of three primes. T h e o r e m 5.1.1. If N is odd and sufficiently large, then where Q(N) is the singular series for the three-primes theorem defined by where c (N) = q [10]. J2 e(aN/q) , - ' o=l,(d',g)=l Our goal will be to show that r(N) > 0 for large enough N. Since we are not attempting to show how large TV must be, or to give an asymptotic formula for r(N) this will be adequate for our purposes. Let Then showing R(N) > 0 is equivalent to showing that r(N) is positive. Letting F(®) = ^2(^ogp)e(pa) p<N Chapter 5. Vinogradov's three-primes theorem we have R 33 - ( ) = N 1 ogPilogp logp 2 3 Pl+P2+P3=N ^ logpilogp logp / 2 2 = / e((pi+p +P3)a)e{-Na)da 3 Pi<N,p <N,p <N 2 ^° 3 logpilogp hgp e((p +p +P3)a)e(-Na)da E 2 3 2 1 Pi<N,p2<N,p <N 3 = [ Jo F{afe(-Na)da. Our goal is now is to prove that F(a) e(—Na)da > 0. To do this, we must be able to estimate F(a), which is difficult. Therefore, we will simplify the problem by considering the set of "almost primes" which behaves similarly to the weighted primes. Since the primes have few divisors, we must make sure that integers in our new set have few divisors. 3 D e f i n i t i o n 5.1.2. Let i,p , ...,p to be the primes less than or equal to (\ogN) where A is an absolute constant. Then let Q = {x < N : p \ x, 1 < i < k}. P 2 k A t We will rely on the following functions in our estimates: h(a) i® ) e x xeQ and hi(a) = K E e(ax) where fc 1=1 where k is as in definition 5.1.2. It is clear that JQ /i(ct) e(—Na) counts the number of ways which we can write iV as the sum of three elements in Q. Our choice of K has the identity 3 fc K = U(1- 1/ y l Pi = ^log((log 7V) ) + 0(1) A (5.1.1) Chapter 5. Vinogradov's three-primes theorem 34 which is Mertens' formula B.0.10. We will prove that the difference | f F(afe(-Na)da~ Jo [ Jo h {afe(-Na)da\ x is small in relation to the size of fi hi(a) e(—Na) and hence fi F{a) e(—Na)da must be positive. The key to proving this will be to show that F(a) and hi{a) are close to each other. Now we are ready to begin our application of the circle method. In showing that \F(a) — hi(a)\ is small, we must consider the case when a is contained in the minor arcs and when a is contained in the major arcs. We will find that if a € [0,1] is close to a rational with a small denominator, then F(a) is large. If not, then F(a) is small. We now make precise what it means for a to be close to a rational with small denominator. We will first define the major arcs and then the minor arcs will be everything leftover. Let B = 16. Then given a/q € [0,1], a rational with small denominator means that 1 < q < (\ogN) . We also have the condition that 0 < a < q. Now for a & [0,1] to be close to such a rational means that 3 3 B \a-a/q\ < (log N) /N-. ' B Therefore, we define the major arcs, M(q, a) to be an interval of all a 6 [0,1] such that a is close to a/q.-' Precisely, M(g, a) = {a: \a — a/q\ < (log N) /N}. • Since we will be using the major and minor arcs to estimate an integral representation of R(N), we must assure that the major arcs M(q,a) are disjoint in order to integrate. We will show this by contradiction. Assume that for different qi, a and q , a we have \a\q — a q\\ > 1 and M(qi, a ) Pi M(q ,a ) is nonempty. Take «o £ M(qi,ai) (~) M(q ,a ). Then B x 2 2 2 2 2 x 2 2 j^WS < (logA) qiq < 71 2 a 2 = qq x <,^_ | ~ qi a 2 + = qq qq _^,< q2 N x | a 2 2 x 2 q x a+a- — q 2 Rearranging the inequality, we have N < 2(logN) . If we choose N to be large, then this inequality is certainly false. This proves our claim that the major arcs are disjoint. Explicitly we have: 3B Chapter 5. Vinogradov's three-primes theorem [(logiV)Sj M= 35 „ | J (J M( ,o)c[0,l]. 9 (a,q) = l We can now define the m i n o r arcs m to be the complement of M in [0,1]. Using this new notation we rewrite the integral for R(N): R(N)= f F{afe(-Na)da+ JM f F(afe(-Na)da. J m In estimating the above integral, we will show that F(a) is small when ex. is not close to a rational with small denominator and we will estimate F(ot) when a G M(q, a) for some rational number a/q. 5.2 Minor Arcs The goal of this section is to show that both F(a) and hi(a) are small when a G m. For each of the following lemmas we use the same hypothesis as when defining the major and minor arcs. We will denote the distance to the closest integer to a by Now we are ready to begin our estimate. Instead of estimating F(a) directly, we will use the function x<N which is easier to estimate, and which we can show-is close..to F(a): Recall the von Mangoldt function . { log p if n = p where p is prime and k > 1 k 0 otherwise The next lemma proves that g(a) is in fact a good approximation for F(a). L e m m a 5.2.1. For every a G [0,1], \F(ct) — g{a)\ < CV~N where C is an absolute constant. Chapter 5. Vinogradov's three-primes theorem 36 Proof: |0(a) - F ( a ) | = I E A(a)e(ax) - Y logpe(ap)| x<Ar p<iv = 1 Y i °gp ( p ) - £ e a A : Y = I °gp ( p)\ l e a p<N p <N,k>l k logpe(ap )| fc p <N,k>2 K <(logy/N) £ 1 P<VN < C^N. where the last line is shown using Chebyshev's theorem B.0.8. • We now turn to the estimation of the minor arcs. Here we will use results due to Vaughan. In the following lemma, we write g(ot) as the sum of three terms plus an error.term. We'wilf then show that each of the terms is bounded and hence we will be able to bound g(a). Our goal is to show that g(a) is small when a is not close to a rational with small denominator. We will use two methods to show this. First, we will be able to consider the cancelation in the exponential sum as in lemma 4.2.2. Second, we can relate g(ct) to Y2,d\x log ^ discussed above, which should be easier to estimate. We will, in fact, use both ideas to show that g(a) must be small with these conditions. = 3 Then g(a) = Y, <NA(x)e(ax) L e m m a 5.2.2. Let X = A / . U + 0{N / ) where 2 2 5 X 5 Y, Y/ S=Y^ii(d) d<X T =Y ^ d<X A(x)e(adxz), z<N/dx<N/zd Y z<N/d Y A(x)e(aGfez), x<X,x<N/zd and U= Y Y X<u<N d\u,d<X ^(d) Y X<x<N/u Hx)e(axu). = S-T- Chapter 5. Vinogradov's three-primes theorem 37 Our proof of lemma 5.2.2 incorporates Vaughan's identity which we will use specifically for g(ot), but can also be proved in general for any arithmetic function of two variables. We will begin with g(a) and work towards a form that we hope to understand. Proof of lemma 5.2.2: Using Chebyshev's theorem B.0.8, we cari bound the sum A(x)e(ax) = | ^ \ogpe(ap )\ k x<X pk<x < E logp p*=<X = 0{X) Therefore, by definition, x<N = E A(x)e(ax) + ^ K(x)e(ax) X<x<N = x<X A(x)e(ax) + 0(N ^) 2 X<x<N Recall that Then 9(«) = EEM ) E H )e(^xu) + O(N^) rf x u<X = E d\u X<x<N/u E E u<N d\u,d<X = E E d<X zd<N = d<X ^ K )<0ixu)-U x + 0{N ' ) 2 5 X<x<N/u E Hx)e(axzd) -U + 0{N ' ) 2 5 X<x<N/dz M<0 E E M Waxzd) ' z<N/dX<x<N/dz x = S -T -U + 0{N ). 2/b -U + 0(N ) 2/5 Chapter 5. Vinogradov's three-primes theorem 38 Note here that in step one, we use the fact that d\u and u < X which implies that d < X. In step two, we let u = dz. • We now show that S, T and U are small under the prescribed conditions. L e m m a 5.2.3. | 5 | < (logN) (q + X + N/q). 2 Proof: By definition |S| = | £/*(<*) £ d<X £ Hx)e(adxz)\. z<N/dx<N/zd In the next sequence of inequalities we will split the sum into pieces of the form Yl <n/dJ2x\u A(x)e(au) and then apply lemma B.0.6. Now letting u = xz, we have u |S| = l £ / 4 * ) £ d<X £A(s)e(adu)| u<N/d x\u - 1 £ E ^)E ^i . A _ . - ' ' u<N/d <*<X = i E M(O E d<X < IE =E d<X x\u e u<N/d 1 ( a r f t x e i E i o s i w ... ( ) E ) a(lu 1(> S' I U e(adw)log«|. u<N/d Now we notice that u e(adu)di/t\ / N/d / E e(adu)dt/t\ t<u<N/d t-N/d < j E J l e{adu)\dt/t. t<u<N/d Chapter 5. Vinogradov's three-primes theorem 39 And thus, by lemma 4.2.2 N/d min{||ad||~\ A y ^ i / i / < logNmm{\\ad\\-\N/d} Now apply lemma A.0.5 and we have I' 5 - E ' d<X e(aw)logw| < Elog/VminllMI- 1 ,^/^} E u<N/d . d<X (log N) {q + X + N/q) 2 as desired. • L e m m a 5.2.4. \T\ <^ (log N) (q + X + N/q) 2 2 Proof: l l =l E ^ ) E E T d<X H E ^ ) E d<X d<X :• E x ) E ( A E ) i x A < a d x z ) \ z<N/dx d<X < a d x z ) \ z<N/dx ^ ) i " E - d<Xd<X - ( A x<X,x<N/d < E ^ ) E < E E Mx)e(adxz)\ z<N/dx<X,x<N/zd ' ( e t t ^ ) i z<N/dx E A (*)i E V<X x<X,x\y ' 2 < y*)\ a ~-z<N/y • , " when we let y = dx. Now we know that ^2 x \ M ) ^ 1°'S2/ 5: log AT by lemma B.0.6 and | Y^z<N/y ( V )\ ^ { | | y i r > N/y} by lemma 4.2.2. Therefore, as in the previous lemma, we can apply lemma A.0.5 to achieve the desired bound. Note that here we have X = N / . • x x< e a z m i n Q ; A l 2 1 2 y 1 2 L e m m a 5.2.5. \U\ < (logN) (N l q l x 4 + N/X ' 1 2 5 + Nq- ' ) 1 2 Chapter 5. Vinogradov's three-primes theorem 40 Proof: We know that M = l £ £ X<u<N < £ M d ) d\u,d<X I X<u<N £ A C r M o s u ) ! X<x<N/u M(*0I -1 £ d\u,d<X £ A(x) ( e axu) X<x<N/u We will split the sum into pieces, each of which we will be able to bound. For each positive integer'i, let 2 -l l Ui £ £ £^ Md) d\u,d<X A(x)e(axu) X<x<AT/u The first important observation is that we will be summing over a finite number of pieces since Ui must be zero when 2 > N/X since then for the last part of the sum we would have X < x < N/(N/X) = X. Therefore, we will have log N pieces since we are summing from 2 > X and 2 ~ < N/X. Now for each Ui we can apply the Cauchy Schwarz inequality to Uf. Thus i _ 1 i i 1 : ^ 2*-l £ •2*-l £ . E M<*) n=2 - =2*-! i " A(x)e(a:x«) 1 X<x<N/u (5.2.2) We now wish to bound each term of this product. Since u(d) is at most 1 we know that | J2d\u,d<x (d)\ < d(u) where d(u) denotes the number of divisors of u. Therefore, we are able to bound the first term of the product (5.2.2) as a 2 2 -1 J E u=2*-i £ Kd) 2'-l < / £ £ d\u,d<X <£« 2 i=l «(logA) , 3 using lemma B.0.7. \ 2 / ««) Chapter 5. Vinogradov's three-primes theorem 41 Now consider the second term in the product and expand. Thus 2 -l l A(x)e(axu) X<x<n/u- 2 -l l = £ £ u=2 ^ i = £ X<x<N/u 1 £ E X<x<N/2 ~ i < A(x)A(y)e(a(a; - y)u) X<y<N/u A(x)A(y) X^y^N^*- 1 1 £ E X^xKN^- £ e(a(x-y)u) 2 ~ <u<2 ,u<min{N/x,N/y} i l i AWA^mindl^x-y)!!- },^- } 1 1 X<y<N/2 - 1 i 1 £ < (logN) (N/T) 2 mindlHr ^' } 1 -1 N/2 - <z<N/2 ~ i <(logA0 (A/2*) 2 i E 2 1 minlllazll- ,^/^} 1 z<N/2 ~ i 1 <^N(logNf(N/q + X + q) where we use lemma 4.2.2 for step three and lemma A.0.5 for step five. Therefore, putting both estimates together and using the facts that N/2 < N/X and 2*" < N/X , we have 1 1 U < (log A ) • N • (log Nf-N2 3 (log Nf(q + N/?- 1 + N/q) < AT(log Nf(q + N/X + N/q), where we use the fact that we have A/2* < N/X. Now taking square roots of both sides, we have Ui « (log N) (q N ' z ll2 1 2 + AX" / 1 2 + Nq-V ). 2 Finally, as mentioned above, we have at most log N possible i, hence we have U « (log Nf(q ' N l l 2 as desired. • x 2 + NX' ' 1 2 + Nq- ? ) 1 2 Chapter 5. Vinogradov's three-primes theorem 42 L e m m a 5.2.6. Let a and q be positive integers with (a, q) — 1 and let a E R such that \a — a/q\ < q~ . Then, given N sufficiently large, F(a) and g(a) are both at most C'(log N)\N l q / + TV / + Nq~ ' ). 2 l 2 1 2 4 5 1 2 Proof: This result combines the results from lemma 5.2.1, lemma 5.2.2 and the lemmas bounding S, T and U. • We will now use definition 5.1.2 and put a bound on the function h(a) = E z e Q e(ax) defined in the introduction. This bound will be used later to show that distance between F(a) and hi(a) = K • h(et) is small when we are considering a in a minor arc. This will be our last estimate needed for the minor arcs. We will do the same for a in a major arc, but we must estimate separately. L e m m a 5.2.7. Let a and q be positive integers with (a, q) = 1 and let a EM. such that \a — a/q\ < q~ . Then 2 \h(a)\ < (logiV) (/V 2 1/2 + q + Nq' + N ' ^). 1 1 1 Proof: We want to write h(a) in some form that we can estimate. Therefore, we notice that fc h(o) - E t - ) 1 , . E 3 '.. s=0- .. X <<m•••!>,<!/)• .\ •„ ; (5.2.3) : • l<ii<'...<is<ky<N/p ...p il is Since, if x E Q, then e(ax) is added if and only if s = 0. On the other hand, if a; ^ Q, then we can write x = p!* • • -p^w where w E Q. In this case, we add (—l)^e(ax) for each subset B C { j i , j } using the inclusionexclusion formula. We apply lemma 4.2.2 to the inner sum of (5.2.3) and note the bound 1 r e(ap ... y) h Pis <mm{\\ap ...p \\- ,N/p ...p }. l il is il is Now we will split the outer sum of 5.2.3 into two parts where we define t = log N/2A log log N. Then t \9(*)\ < \Y,(-l) a s=0 E E e(«p ...p y)\ h l<ii<--<i <ky<N/pi ...p s 1 i$ is + Chapter 5. Vinogradov's three-primes theorem I E E E s=t+l 43 ( Pii-PisV)\- e a l<h<-<is<ky<N./p ..p iv is We estimate each term separately. For the first sum we observe thatforany combination of the primes p i , ...,p , we have p^.-.p^ < ((log JV) )* = </N. Thus A k E ( _ 1 ) E S E ' («Pii-Pi.2/)l e l<ii<...<i <fc /<N/p ...p 0 s ^ IE^- ) 1 2 il E 8 s=0 is min{||ap ...p J|- ,^/p ...p J| 1 il i il i l<ii<---<is<fc < 5^ min{||a!:r|| , N/x} -1 X<VN < (log /V) (N ' 2 1 2 + q + Nq' ) 1 using lemma A.0.5 for the last step. For our second estimate, we have k E t - ) 1 E 5 s=t+l E e (a P i l ... )i M i<h<--<i <ky<N/ ...p s Pil is k - E E s=t+l {\\ Ph-Pis\\~\N/p ...p ,} m[n a il l<ii<...<i <k s £ "tlx, ±t 1 s=t+l l<i <...<i <fc. 1 s j=l fc fc <^ E( ) (EP-) S! _1 s=4+l S m=l fc <CN E( /e)- (loglog(logiV) )^ s A 5 s=t+l fc < CiV ^ s=t+l (e/s • 2 log log log N) s i Chapter 5. Vinogradov's three-primes theorem 44 where we use Mertens' theorem B.0.9 and Stirling's formula in step four. The function (2es log log log N) is decreasing when s > 2e log log log N and so to estimate our inequality, we can substitute s = t = log N/2A log log N > 4e log log log N, so we can conclude, _1 s fc £ (2es- logloglogiV) < 1 fc(2er logloglogA^) . s 1 t s=t+l We want to prove that this last quantity is less than or equal to C(N~ ' ). We know that k = n((logN) ) < C < CN' for any e > 0 and N' sufficiently large. Then l iA A log(2e£~ log log log Nf = t log(2er log log log N) 1 1 - 2 + 26, 4A ^ < (-l/4^-€o)logJV. = Therefore, we have ' ' (2et log log log Nf < CAT-i/4A-e _ _1 0 Using this and our upper bound for k, we can conclude that lEt- )* 1 s=t+l E E e(a ...p y)\<N- , l/4A Pil ls l<h<---<is<ky<N/pi ...p l is which we combine with our estimate for the first part of the sum to have our desired conclusion. • 5.3 M a j o r Arcs Now we move on to estimates for the major arcs. Our goal will be to estimate F(a) and h(a) when a is close to a rational with small denominator. Chapter 5. Vinogradov's three-primes theorem 45 In the next section, along with the results we have proved for the minor arcs, we will show that F(a) — h\(a) is small regardless of our choice of a. Before continuing with the estimates, we will provide some motivation for the following lemmas. Let X be an arithmetic progression of the form {a, a , 4 - 1 , a + (m — l)q} where a and q are relatively prime and 1 < a ,< n • —(m — l)q. Define a function log a: — KQ(x)ii x is prime (5.3.4) —KQ(x) otherwise { where Q(x) is the characteristic function of Q. Then it is clear that ^2G(x)e(ax) = F(a)-h {a). y 1 x<N We will relate G to arithmetic progressions of the above form and therefore estimate the difference between F(a) and hi(a) by estimating J2 ^°SP and \X n Q\. The following version of the Siegel-Walfisz theorem is taken from Nathanson [10]. peX T h e o r e m 5.3.1. (Siegel-Walfisz) If q > 1 and (a,q) = 1, then for any C>0, £ 1 O E P= p<x,p=a{mod q) ^ r + W 0 ((I^F)\ V 6 / ( 5 / - 3 5 ) for all x > 2 and where the implied constant depends only on C and (j) is defined to be the Euler ^-function. The modular condition given to the sum of (5.3.5) provides an estimate for the arithmetic progressions X described above. Since we chose 1 < a < N — (m — l)q then we have £ logp = ^ + 0(iV/(log N) ). c (5.3.6) Here we want the estimate for the major arcs and hence we take q < (log N) which allows us to conclude that the implied constant must only depend on B and C. B Chapter 5. Vinogradov's three-primes theorem L e m m a 5.3.2. Let q < (log N) , let X = {a, a + q , a {1,N}, m > N and let (a, q) = 1. Then 46 + (m - l)q} C B l/2 k I* Q\ = ^ N IK - + OMT /"). 1 1 Proof: The proof relies on the Brun Sieve for arithmetic progresions. First note that X n Q = {x € X : p* \ x i = 1 , f c } . Let x G X be chosen uniformly at random. Define the Xi to be the event Pi\x. We let P(Y) be the probability of the event Y . Then ( pT' + Oim- ) if \q 1 Pi I 0 if |<7 Pi Then k |XnQ| = m(l-P((J*i)) i=l r = m(l-P(|JX )), i 1=1 .-,. where P{Xi) ^ 0 for 1 < i < r. In order to compute - P ( U ; = i Xi) we will use the inclusion-exclusion formula. Given a set of events Xi ,...,Xi with 1 < ii < ••• < i < k we can compute the probability that a combination of the events happens as x s s s P(x n . . . n x j = n i/ . + 0{m- ), 1 h Pi 3=1 if p^, ...pj. { g and 0 otherwise. Therefore, for any t, we have t i - n y ^ - D - D 1 s = n v * , E o + ( n , - ) l<ii<-<i,<fc -=i 0 s = i<«-i<...<i.<*j=i 0 + E s = t + 1 n > / , l<ii<...<t,<*j=i E r . ^ 7 ^ + o ( m - ' ) j , ^ s— J. Chapter 5. Vinogradov's three-primes theorem 47 For the first sum, we have 9 B - 1 ) 5 s=0 £ I I vw, = I B l<ii<...<i <k - VP*) i=l j=l s 1 A; =n(-/ft)ii(-/Pir i i i i i =n(-./ft)n(-/Pi)i i i i 1 using theorem B.0.12 in the last step. The second sum, we can estimate as in lemma 5.2.7 £ s=t+l I I V f t , < (4c*- log log log)' E 1 l<h<-<is<k j - l where t > 8e log log log N. Putting this all together, we have 1 - P ( U f X i ) = f[(l - 11 ) + 0((logN) At =1 Pi + (4elogloglog iV/i)') i=l k ^n(i-i/ft)+"OfArV") where we take t = log-N/2A loglog:,AT.and estimate as in lemma 5.2.7. Multiplying everything by m weget the desired result. • C o r o l l a r y 5.3.3. Let q < (log N) , let X = {a, a + <?,..., a + (m - 1)<?}. Assume £/ia£ C is any positive constant. Then A K\XnQ\-Y °&P l p<=X = 0(N(\ogN)- ). c Chapter 5. Vinogradov's three-primes theorem 48 Proof: Recall that K = Ui=i( ~ PJ )( >?) = follows directly from lemma 5.3.2 and from equation 5.3.6. If (a, q) ^ 1 then the arithmetic progression X contains at most one prime, which must be a, and the bound holds trivially. • 1 l W h e n a t h i s L e m m a 5.3.4. Let q < (\ogN) , let (b,q) = 1 and assume a G K such that \a - b/q\ < {\ogN) /qN. Define G : {1, 2,.... TV} —• M such that \G(x)\ < log iV for every x and A A |£G(x)|«iV(logiV)xex A for every arithmetic progression X defined as above where B > 4A + 2. Then | G{x)e(ax)\ = 0{N{\ogN)' ) A x<N Proof: The idea of this proof is to split J2J2 k £ x<N G(x)e(ax) = i=l G(x)e(ax) x£Xi where the progressions X j partition { 1 , 2 , N } into 2N/rriQ sets with m < o — N(\og N)~ / . We can estimate the magnitude of J2xeX G(x)e{ax) using the following fact and lemma 5.3.3. If x, y G X and j3 = a — b/q then, m B 2 \e((3x) - e(Py)\ = \e(J3x)(l - e(/% - x))) = \(1 - e(P(y - x))\ <2ir\y-x\\p\ < 2ixm{\ogN) /N. A Chapter 5. Vinogradov's three-primes theorem 49 Let xo € X be fixed. Then for each progression we have | £G(x)e(axj| = |£ xex G(x)e((/3 + b/q)x)\ xex = \Y,G(x)e(bx/ )e{(3x)\ q • •' . ; •x&x-t • • < | e ( a f e ^ ) £ G ( x ) [ e ( ) 0 x ) + e(^o)-e(/3xo)]| xex < |e(atyg) ^ G ( i ) ( e ( | 3 x ) - e((3x ))\ 0 xex + \e(ab/q)e((3x )Y ( )\ 0 G x xex < £ \G(x)(e(Px) -e((3x ))\ + | £ G ( x ) | 0 xex < £ xex log TV • 27rm(log A ) / i V + A^(log A ' ) A < (logA)^^ ^ 2 1 7 - 5 + A^(logA)- . B Since we have split the sum into 2N/m partitions, we can conclude 0 |£ G(x)e{ax)\ < 2AT/mo((log A ' ) / j4+1 m A " ~ + AT(logN)~ ) 2 / 1 B x<N which gives the desired result. • 5.4 Final calculations We now have everything that we need to show that F(a) and h\(a) are close. In these final calculations, we will show that fi h\(ot)e(—Na) > N /\ogN, that the difference j fi F{a)e{-Na) - fi ^ ( a ) e ( - J V a ) | = 0 ( A ( l o g N)' ) and hence that fi F(a)e(—Na) > 0. 2 2 3 L e m m a 5.4.1. Let A = 16. Then for every a G R , F(a) — h (a) = 0(N(\ogN)- ). x 4 Proof: Fix a. Then there exist b and q with (6, 9) = 1 such that q < N{\ogN)- and \a - b/q\ < (log N) /Nq (in particular, \a - b/q\ < q' ). A A 2 Chapter 5. Vinogradov's three-primes theorem 50 For the case of a in the minor arcs, we consider q > (\ogN) . Applying lemma 5.2.6 and using the upper bound and lower bound for q we have A F(a) « (log N)\N l\ ' l + AT / + Nq' ' ) 1 2 4 5 1 2 « (log A ) ( A ( l o g N)~ / + A / + A (log N)- ' ) 4 A 2 4 5 A 2 and for large enough N, we have < A(log Nf~ ' A = A(log N)~\ 2 We now estimate h\(a) using lemma 5.2.7 and (5.1.1). We have . \hi{a)\ <ZiK{\ogN) (N l + 2 l q + Nq~ + 2 N-' ) l l l 4A < K'{log A ) A'(log N)~ 2 < A log(logA)A(logA) 2 = A(log A ) - A 1 3 Since we have show that both F(a) and hi(a) are smaller than the desired bound, it is clear that their difference is bounded as desired. • For the major arcs, we have q < (log A ) : Let Q(x)-be the characteristic function for Q. Recall that X is the progression X = {a, a+q,a+(m—l)q}. Then we have A ' |£A0(rr)-£logp! xex pex !£G(.7;)|,= xex . \ . = K\xnQ\-J2 °sP l P<EX = 0(A(logA)- ) c by corollary 5.3.3. We can relate G to F and h\ as follows: £ x<N G(x)e(ax) = £ ( l o g p - K Q(p))e(ax) - K p<N £ Q(x)e(ax) x<N,x^p = £(l°gp)e(ap) ~ Y 1 K p<N Q( ) i ) x e ax x<N = F(a) - h (a). x Applying lemma 5.3.4 we have F(a) - hi(a) = 0(A(logN)' ). A • Chapter 5. Vinogradov's three-primes theorem 51 Now we are ready to prove Vinogradov's theorem. We begin by estimating the number of ways of writing an integer m as the sum of two elements of Q and we obtain an estimate for the number of ways to write m as the sum of three elements of Q as a corollary. Since we have found that Q behaves like the weighted primes, we will use these two results to prove that every large N can be written as the sum of three primes. L e m m a 5.4.2. Let m e Z , Then the number of ways of writing m = x + y where x, y £ Q is at least k m]J(l "'/P*) + 0{m- N ' i=l l r where r • 1 1 2 + mN-^ ) A s ^ \ 2 otherwise Proof: Choose x £ {1,2, ...,m}. For each 1 < i < k, let Xi be the event that pi\x or Pi\(m — x). Note that if Pi\m then we have Pi\x if and only if i\{m — x). If Pi \ m then pi\x and Pi\(m — x) are mutually exclusive. Therefore we have P(Xi)=n/p + 0(m- ) P 1 i and s P(X h n • • • nX*,) = \\rijpi, + 0(m~ ). l 3=1 The proof then follows directly as in lemma 5.3.2 so we have ' k • 1- P(utiXi) = . - -rjpi) + O ^ - (log N) 1 At + (Set' log log log Nf) 1 i=l for t > 16e log log log N. Taking t =..'log N/2A\og\og N the lemma follows. • As we approach the final result, we first prove a bound on the number of ways which we can write a sufficiently large odd integer, N, as the sum of three elements of Q. Then, using this set, which shares properties with the primes, we will be able to prove Vinogradov's theorem. Chapter 5. Vinogradov's three-primes theorem 52 C o r o l l a r y 5.4.3. Let N be a large odd integer. Then, k £ f[(l - 2/pO 1 » (N /16)K2 1 N=q +q +q3,qi£Q 1 i=2 2 > Ar /logA 2 Proof: If z is odd and z < N/2, then we can apply lemma 5.4.2 to N — z. Then k J2 ^ 1 A r / I1( 4 N—z=x+y,x,yeQ 1 - M ) + OC/V " /").. 1 2 1 i=2 The number of possible 2 < A / 2 and 2 € 0; is given by lemma 5.3.2. Letting X = {1,2,..., [N/2\}, we have fc i x n Q i ^ L A V ^ n a - p r ) 1 i=i > {N/4)K~ L Therefore, • £ 1 > 0V/4)A-' E N=qi+q2+q3,qieQ 1' ' N-z=x+y,x,yeQ fc - 2/ ) >> N K~ 2 L Pi i-i fc k n a - p - ^ n a - p - »N K-' 2 1 ) 1=9 i=10 » _. , . N K~ 2 3 > A ( l o g log A O " 2 3 » A /log A, 2 when N is sufficiently large, we use identity (5.1.1) and the fact that since Pi ~ 1 > Pi-i, l-2/ P l = (l-l/p )( 1 _ 2 / P J = d-iM)(^) >(1-1/ )(l-1/ ^)n Pi Pi ^ Chapter 5. Vinogradov's three-primes theorem 53 Finally we are able to prove Vinogradov's three primes theorem by relating F(a) and hi(a). T h e o r e m 5.4.4. If N is^a large odd integer, then N can be written as the sum of three primes. Proof: As we noted previously, and using lemma 5.4.3 we have /ii(a) e(-Aa)A > f Jo 3 3 = * h{afe{-Na)da £ 3 i N=qi+q2+q3,qi€Q > A /log A. 2 Set A = 4. Recall that in lemma 5.4.1 we proved that for every real number a, F(a) - /n(a) = 0 ( A ( l o g A ) " ) . 4 Therefore, we are able to prove the desired result given in the introduction. Namely, l r F{afe{-Na)da= | / {F{af Jo i / /\ (a) e(-Aa)da| Jo 3 1 -/ii(a) )e(-Aa)ria| 3 Chapter 5. Vinogradov's three-primes theorem 54 < f \F{af - /ii(a) ||e(-A^a)|da 3 Jo < ! \F{a) - h {a)\\F(a) + F{a)h {a) + h{a) \da Jo 2 2 1 x = 0{N{logN)~ ) [ \F{a) + h^atfda Jo A/4 = 0{N(logN)~ ^) [ \F(a)\ + \h {a)\ da Jo A 2 2 x = 0(N{logN)- ^)( f \J]logpe{ap)\ da+ f \Kh(a)\ da) Jo < Jo A 2 p N = 0(iV(logiV)- )( f V o < \logpe{ap)\ da + f \K\ \h{a)\ da) Jo A/4 2 J P = N 0(N(logN)- ^)(J2^ogp) 2 A 2 2 2 + K \Q\) 2 p<N = 0{N log N {log N)~ ) 2 4 where we use the estimate.from B.0.11 for Y1 <NQ°&P) 2 P Hence : l F{afe{-Na)da > TV / log N - 0{N {log N)~ ) 2 2 3 o '. '• '--> y (): ' . : -- • Finally, we have proved Vinogradov's three-primes theorem . 55 Appendix A A Minor Arcs Lemma This lemma is in the same spirit as Weyl's inequality, and to prove it, we use elements from the proof of Weyl's inequality. We use this variation in our estimates of the minor arcs in Vinogradov's three-primes thoerem. L e m m a A . 0 . 5 . Let a, q, N £ N . Assume a £ [0,1], (a, q) = 1 such that \a - a/q\ < q~ q < X and X = A " / . Then 2 2 Y,™™{\\ad\\-\N/d} 5 < (\og2qX)(N/q + X + q). d<X Proof: The first observation that we make is that one can write d uniquely as d = kq + r where 1 < r < q and 0 < k < X/q. Therefore we can bound the sum we wish to estimate as Emin{IM|r\A7d}< d<X £ £ m i n { | | a ( / c + r)\\~\ N/(kq + r)} g 0<k<X/q r = l (A.0.1) We will estimate the right hand side of equation in two steps. In the first case, we assume k — 0 and r < q/2. Then we would like to bound E^mindlarH^^/r} We have a = - + 4 where —1 < u < 1 since la — -I < q~ . Thus or = — + . Note that we can bound the magnitude of the second term 1^1 < ^ < ^ 2 = 2^- Also, since ar £ 1< we can write av = jq + s for 0 < s < q and s unique for each r. Therefore, we have the following estimate 2 Appendix A. A Minor Arcs Lemma 56 for llarll. ar ur,. — q + q— \ctr 2 s ur, J + -q + — q s ur.. 2 • > f l l - l l ^ l l £ 1 2q Q Therefore, we are able to pair each number ||ar|| with a unique number || — ^ = | — ^ since s < q/2 implies that s/q < 1/2. Therefore, we have £ m i n l l K H ^ i V r - } ^ ]T \or\\1 1 r<q/2 r<q/2 1 v-. s<q/2 = , <? 2<j 2qY ^ 2s - . 1 , s<q/2 < 2 , £ 1 s<q/2 <glogg. Now we will estimate the sum for 1 <fcorfc= 0 and g/2 <r<q. Then we have < since if 1 <fcthen kq + r > kq> ( ^ and otherwise k+ Q kq + r = r > q/2 = We would like to bound J2l=i {IK 9 + r ) | | , (fcj^^}- Although our summation runs from r = ltor = q, the (kq+r) translates the sum and places us in the case of Weyl's inequality (4.2.1). Therefore, we have E r = i min{||a(fcg + r ) | | , ^ jj^fi +q\ogq. m i n _ 1 _ 1 fk 1)q f c Appendix A. A Minor Arcs Lemma 57 Hence, £min{.||«d||- ,iVM<<9log + ^ m H I I ^ + r)!!- ^—} 1 1 g d<X K 0<k<X/qr=l «glogg+ ((k + l ) a 0<k<X/q ^ = qlogq + ^ £ : — 0<fc<X/q AT ,H + JH + q l O S q ) ' , ,. ; - •: ^ 0</e<X/ glogq 9 < g log g + — \og{X/q + 1) + X log <? + q log 9 < (log2gX)(AT/g + X + g) since X / g + 1 < X + 9 < 2 max(o, X ) < 2qX. • 58 Appendix B Theorems from Analytic Number Theory Here we list a few estimates that we have used in the above proofs. I have found Nathanson's "Elementary Methods in Number Theory" [11] and Apostol's "Introduction to Analytic Number Theory"[1] to be good sources for the following material. L e m m a B.0.6. A(d) = log x d\x Proof: Write x — p" • • • p . Then we have the sum of logpi, a times, logp2i 2 times and so on. • • . 1 a k k x a L e m m a B . 0 . 7 . Let d(n) denote the number of divisors of n € N . Then ^d{xf <2n{\ognf T h e o r e m B . 0 . 8 . C h e b y s h e v : [11] Let n(x) = J2 < h = E <x S P and ip(x) — Y^ k< \°E,P- Then there exist positive constants A and B such that P p X P l o x Ax < i!}(x) < ip{x) < TT(X)logx < Bx. The following two theorems are due to Mertens. The proofs can be found in Nathanson [11]. T h e o r e m B . 0 . 9 . There exists a constant b such that x V p<x for x > 2. 1/p = log log x + 6 + 0 ( ^ — ) logx : Appendix B. Theorems from Analytic Number Theory 59 T h e o r e m B.0.10. M e r t e n s ' formula: There exists a constant 7 such that for x > 2, Ylil-p- )1 = enogx + 1 0(l). p<x Here 7 is Euler's constant which is defined by 7 = l i m ^ o o ( E ^ 1 / k — log A O n = 1 L e m m a B.0.11. £(logp) 2 < NlogN p<N Proof: Define £(x) to be log a; if x is prime and 0 otherwise. Then Y ( ) °S £(logp) = 2 p<N £ x l x J N x<N = ${N) log A" — ^-dt <iVlogJV, where we use Chebyshev's theorem B.0.8 and partial summation. T h e o r e m B.0.12. The Euler (^-function has the identity <\>(n)=n\\iA- - ). 1 V p\n • 60 Bibliography [1] T. M . Apostol. Introduction to Analytic Number Theory. Springer, New York, 1976. [2] F . A . Behrend. O n sets of integers which contain no three terms in arithmetical progression. Proc. Nat. Acad. Sci. U.S.A, 32:331-332, 1946. [3] T. Gowers. Vinogradov's three-primes theorem, notes available at http://www.dpmms.cam.ac.uk/ wtgl0/3primes.dvi. [4] T. Gowers. A new proof of Szemeredi's theorem. Geom. Fund. Anal, ll(3):465-588, 2001. Preprint available at http://www.dpmms.cam.ac.uk/ wtglO/papers.html. [5] G . H . Hardy and J. E . Littlewood. Some problems of "partitio numerorum"; iii: On the expression of a number as a sum of primes. Acta Math, 44:1-70, 1923. [6] H . te Riele D. Zinoviev J . - M . Deshouillers, G . Effinger. A complete Vinogradov 3-primes theorem under the Riemann hypothesis. Electronic Research Announcements of the American Mathematical Society, 3:99104, 1997. [7] Chen J.R. and Wang T.Z. On odd Goldbach problem! Acta Math. Simca, 32:702-718, 1989. [8] J. V . Linnik. A new proof of the Vinogradov-Goldbach theorem. Mat Sbornik, 19:3-8, 1946. [9] H . L . Montgomery. Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis. American Mathematical Society, Providence, Rhode Island, 1994. [10] M . B . Nathanson. Additive Number Theory: The Classical Bases. Springer, New York, 1996. Bibliography 61 [11] M . B . Nathanson. Elementary Methods in Number Theory. Springer, New York, 2000. [12] R. Rankin. Sets of integers containing not more than a given number of terms in arithmetical progression. Proc. Roy. Soc. Edinburgh, Sect. A, 65:332-344, 1960/1961. [13] Y . Saouter. Checking the odd Goldbach conjecture up to 10 . Math. Comp., 67(222):863-866, 1998.' . 20 [14] R. C. Vaughan. The Hardy-Littlewood Method. Cambridge University Press, Cambridge; New York; Melbourne, second edition, 1997, 1981. [15] I. M . Vinogradov. Representation of an odd number as a sum of three primes. Comptes Rendus (Doklady) de VAcademi des Sciences de I'URSS, XV(3):291-294, 1937.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Fourier analytic applications to number theory
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Fourier analytic applications to number theory Hamel, Mariah 2004
pdf
Page Metadata
Item Metadata
Title | Fourier analytic applications to number theory |
Creator |
Hamel, Mariah |
Date Issued | 2004 |
Description | In this paper we give expositions of Roth's theorem, Weyl's inequality and Vinogradov's three-primes theorem. In the proofs, we will frequently use exponential sums and more specifically the discrete Fourier transform. In the proof of Vinogradov's three-primes theorem we will use Hardy and Littlewood's circle method. This paper is intended to be self-contained and will hopefully be readable to someone with little background in the area. |
Extent | 2682321 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-11-27 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080078 |
URI | http://hdl.handle.net/2429/15908 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2004-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_2004-0713a.pdf [ 2.56MB ]
- Metadata
- JSON: 831-1.0080078.json
- JSON-LD: 831-1.0080078-ld.json
- RDF/XML (Pretty): 831-1.0080078-rdf.xml
- RDF/JSON: 831-1.0080078-rdf.json
- Turtle: 831-1.0080078-turtle.txt
- N-Triples: 831-1.0080078-rdf-ntriples.txt
- Original Record: 831-1.0080078-source.json
- Full Text
- 831-1.0080078-fulltext.txt
- Citation
- 831-1.0080078.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080078/manifest