Arithmetic Structures in Random Sets by Mariah Hamel M.Sc., B..A., Colby College, 2002 The University of British Columbia, 2004 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 T H E REQUIREMENTS FOR T H E D E G R E E OF Doctor of Philosophy m The Faculty of Graduate Studies (Mathematics) The University of British Columbia June 2008 © Mariah Hamel 2008 Abstract W e prove various results i n additive combinatorics for subsets of r a n d o m sets. In p a r t i c u l a r we extend Sarkozy's theorem a n d a theorem of G r e e n on long a r i t h m e t i c progressions i n sumsets to dense subsets of r a n d o m sets w i t h a s y m p t o t i c density 0. O u r proofs require a transference argument due to G r e e n a n d G r e e n - T a o w h i c h enables us to a p p l y k n o w n results for sets of positive upper density to subsets of r a n d o m sets w h i c h have positive relative density. W e also prove a density result w h i c h states that if a subset of a r a n d o m set has positive relative density, then the sumset of the subset must have positive upper density i n the integers. Table of Contents Abstract T a b l e of C o n t e n t s Acknowledgements Dedication S t a t e m e n t of C o - A u t h o r s h i p 1 Introduction 1.1 1.2 1.3 1.4 1.5 History 1.1.1 Statement of m a i n results Preliminaries and Notation B o h r Sets 1.3.1 A localized version of C h a n g ' s theorem A proof of Sârkôzy's T h e o r e m T h e transference p r i n c i p l e a n d pseudorandom sets ii iii v vi vii 1 1 3 5 6 8 10 14 Bibliography 18 2 20 A r i t h m e t i c structures i n r a n d o m sets 2.1 Introduction 20 2.2 2.3 2.4 Preliminaries A V a r n a v i d e s - t y p e theorem for square differences P r o o f of T h e o r e m 2.1.2 24 27 29 2.5 P o w e r differences 31 2.6 2.7 L o n g a r i t h m e t i c progressions i n sumsets T h e m a i n t e r m estimate 32 33 2.8 T h e restriction argument 2.9 P r o o f of P r o p o s i t i o n 2.1.3 2.10 Acknowledgements 39 41 42 Bibliography 43 3 Conclusion 3.1 A p o t e n t i a l a p p l i c a t i o n to primes 45 45 3.2 A n improvement to T h e o r e m 2.1.2 47 3.3 F u t u r e directions 47 Bibliography 50 Acknowledgements I want to t h a n k m y advisor Izabella L a b a for her continued support a n d g u i d ance throughout m y graduate work. I a m especially t h a n k f u l for our m a n y meetings filled w i t h m a t h e m a t i c a l insight, encouragement a n d thoughtful advice. I w o u l d like to t h a n k Jozsef S o l y m o s i , D a v i d B o y d a n d M a l a b i k a P r a m a n i k for m a n y useful discussions a n d for offering such an interesting array of graduate courses. I a m grateful to D a v i d B r y d g e s for always being so k i n d a n d for always i n q u i r i n g about m y progress as a graduate student. I w o u l d like to t h a n k G r e g M a r t i n a n d Stephen K w o k - K w o n g C h o i for being members of m y e x a m i n i n g committee a n d for thoughtful suggestions for this thesis. I have enjoyed discussions w i t h m a n y of m y fellow graduate students including K a r s t e n Chipeniuk, Chris Coulter, Chris Duarte, Zhai K e l a n and T e r r y Soo. I a m deeply grateful to have begun s t u d y i n g mathematics under the supervision of B e n M a t h e s , Leo L i v s h i t s a n d Fernando Gouvêa at C o l b y College. I w i l l forever remember their encouragenient a n d their love of mathematics. I a m indepted to m y parents, E d a n d M a r y H a m e l , for h a v i n g s u p p o r t e d me throughout m y education. F i n a l l y , I w o u l d like to t h a n k M a t h e w Rogers for his support, encouragement a n d love. Dedication For C a r i n a statement of Co-Authorship T h e manuscript which is contained i n this thesis is joint work w i t h Izabella Laba. It was suggested to us that Theorem 2.1.2 was feasible Ben Green. T h e statement of Theorem 2.1.4 was first considered by L a b a . The manuscript was researched and jointly written by M a r i a h Hamel and Izabella Laba. Chapter 1 Introduction 1.1 History A d d i t i v e combinatorics can be described as a s t u d y of the s t r u c t u r a l properties of sets of integers, or more generally, additive groups. W h i l e this area has long been of interest to m a t h e m a t i c i a n s , over the past few years there has been an abundance of c o l l a b o r a t i o n between those w h o study number theory, h a r m o n i c analysis, combinatorics a n d ergodic theory. I n this introd u c t i o n we w i l l provide m o t i v a t i o n to the work i n c l u d e d below t h r o u g h a discussion of the h i s t o r y of additive combinatorics as well as some (difficult) conjectures w h i c h r e m a i n open. O n e of the first results i n the subject w h i c h is today called additive combinatorics is a coloring result due to v a n der W a e r d e n proved i n 1927. He was able to show t h a t given integers r a n d k, if the set of integers is colored by r colors, t h e n there must be k integers i n a r i t h m e t i c progression w h i c h are m o n o c h r o m a t i c . A related result, due to Schur states that if the integers are r - c o l o r e d , t h e n there must be x, y a n d z, m o n o c h r o m a t i c , such that X + y — z. B o t h of these problems fall into the category of R a m s e y theory w h i c h is concerned w i t h e x t r e m a l results. W e c a n rephrase t h e m as follows: Suppose { 1 , n ] is colored w i t h r colors. H o w large must n be (as a function of r) to guarantee the desired m o n o c h r o m a t i c structure? In 1936 E r d o s a n d T u r a n formulated the following conjecture: C o n j e c t u r e 1.1.1. Suppose ^ C N such that > - = oo. aeA Then A must contain arithmetic progressions of arbitrary length. W e r e m a r k t h a t this can be seen as an extension of the theorem of van der W a e r d e n since if we color the integers w i t h finitely m a n y colors, then certainly one of the color classes w i l l satisfy the hypothesis of Conjecture 1.1.1. However, no such generalization of Schur's theorem exists since, for example, the set of o d d integers also satisfies the hypothesis of the Conjecture but there are no three o d d numbers w h i c h satisfy x + y = z. W h i l e C o n j e c t u r e 1.1.1 remains open, there have been m a n y interesting results i n t h a t direction. W e say that a subset A of the integers has positive upper density if limsupJ |^n{l,...,n}| „ ^ ' ' > 0. In 1953, R o t h [13] proved that any subset of the integers w i t h positive upper density must c o n t a i n a r i t h m e t i c progressions of length three. A few years later, b u i l d i n g on R o t h ' s result, V a r n a v i d e s [17] showed t h a t , i n fact, such a subset must contain m a n y three-term a r i t h m e t i c progressions. W h i l e we w i l l not elaborate on the details of proof here, we note that the reader can compare the proof of R o t h ' s theorem to that of Sarkozy's theorem on square differences i n c l u d e d i n Section 1.4. S i m i l a r l y the extension of S a r k o z y ' s theorem contained i n C h a p t e r 2 follows V a r n a v i d e s ' o r i g i n a l argument. I n 1975, Szemerédi extended R o t h ' s theorem for a r i t h m e t i c progressions of a r b i t r a r y length. Specifically, he proved the following: T h e o r e m 1.1.2. Szemerédi's T h e o r e m . Let k be a positive integer let Ô > 0. {1,...,N} Then there exists N = N{k,ô), such that \A\ > SN must contain and such that every subset A of an arithmetic of progression length k. M o t i v a t e d by Szemerédi's work, Purstenberg [4] provided an ergodic proof of the same theorem. M o r e recently, i n 2001, Cowers [5] approached the p r o b l e m w i t h a proof that can be seen as a generalization of R o t h ' s o r i g i n a l argument for three t e r m a r i t h m e t i c progressions. M a n y of the ideas developed b y Gowers were used by G r e e n a n d T a o [8] i n p r o v i n g that the primes c o n t a i n a r i t h m e t i c progressions of a r b i t r a r y length. Inverse problems form another i m p o r t a n t topic i n additive number theory. Suppose that A c { 1 , A ' ' } . size of the sumset A + A ~ F r e i m a n ' s theorem [3] states t h a t if the {ai + a2 : a i , a2 £ A} is s m a l l (relative to the size of A) t h e n A itself must be very s t r u c t u r e d . T o state F r e i m a n ' s theorem precisely, we require a the following definition: D e f i n i t i o n 1.1.3. Suppose that XQ, xi, ...,Xd are integers and are positive integers. A generalized arithmetic progression defined d XjXj : 0 < Aj < ruj - P := {xo + i=l 1}. mi,m2, of dimension d is If the size of the progression P is proper. is equal to the product of the ruis, we say that A n i l l u s t r a t i v e example of a generalized a r i t h m e t i c progression is defined by the set P := 6 + {0, 3,6,9} + { 0 , 1 0 0 , 2 0 0 , 3 0 0 } . P r e i m a n ' s theorem then states: T h e o r e m 1.1.4. (Preiman-Ruzsa-Chang) Suppose A C "L and \A\ = A'^ and \A-\- A\ < C\A\. Then there exists a proper d-dimensional arithmetic progression P such that A C P and \P\ < CiN where d < [C - I] and log(|P|/|A|)«C2(logC)3. Despite m a n y works on the above subjects there r e m a i n m a n y open problems. E v e n the case of three t e r m a r i t h m e t i c progressions has not been satisfactorily solved. I n terms of an upper b o u n d , the best k n o w n result is due to B o u r g a i n [2] i n w h i c h he shows a set of density ô » ^(°(fg^)2/3 (assum- ing N is sufficiently large) must contain three t e r m a r i t h m e t i c progressions. O n the other h a n d , the best lower b o u n d due to B e h r e n d [1] shows that there exists a subset o f { l , A ' ' } of size A'' viogAr TîSgW w h i c h contains no three t e r m a r i t h m e t i c progressions. In the case of R o t h ' s theorem, there have been some interesting results for sets w h i c h do not satisfy B o u r g a i n ' s bounds. I n 1996, K o h a y a k a w a , L u c z a k a n d R o d l [12] proved a version of R o t h ' s theorem for sets of a s y m p totic density zero w h i c h satisfy the a d d i t i o n a l hypothesis of positive relative density i n a r a n d o m set w h i c h has density zero i n the integers. In 2002, G r e e n [7] proved a version of R o t h ' s theorem for sets w h i c h have positive upper density i n the primes. 1.1.1 Statement of m a i n results T h e purpose of t h i s section is to state the m a i n results contained i n this thesis. Theorems 1.1.5 a n d 1.1.6 are contained i n C h a p t e r 2 a n d can be found as T h e o r e m 2.1.2 a n d T h e o r e m 2.1.4 respectively. T h e proof of T h e o r e m 1.1.5 can be found i n Section 2.4. T h e proof of T h e o r e m 2.1.4 can be found i n Sections 2.6, 2.7 a n d 2.8. T h e purpose of the remainder of this chapter is to provide an i n t r o d u c t i o n to the ideas used i n C h a p t e r 2 a n d to fill i n certain details t h a t were o m i t t e d from [11]. In 1978 Sârkôzy [15] proved a variant on R o t h ' s theorem showing that subsets of positive upper density must contain two elements whose diflFerence is a perfect square. T h e same result was proved independently by Furstenberg ([4]) u s i n g ergodic theory a r o u n d the same t i m e . In 1988, P i n t z , Steiger a n d Szemerédi, using a c o m b i n a t i o n of F o u r i e r a n a l y t i c a n d c o m b i n a t o r i a l arguments, showed t h a t any subset of {1,...,A'^} of size at least (logA^)-^'°g'°g'°g^°g^Ar must c o n t a i n a square difference. O n the other h a n d , a c o n s t r u c t i o n of R u z s a shows that there exists a set of size iv^^°-^^^ w h i c h contains no square difference. It is conjectured t h a t for a n y e > 0, a n d A'^ sufficiently large (depending on e), there exists a set of size A''^~^ w h i c h contains no square difference. I n a j o i n t paper w i t h Izabella L a b a we prove the following variant of S a r k o z y ' s theorem. T h e o r e m 1.1.5. Suppose that W is a random subset of ZN such that the events x G W, where x ranges over Z j v , are independent p = p{N) G {cN-^, 1] where 0<9 for every set A C W and have probability < 1/110. Let a > 0. Then the statement with \A\ > aW, there are x,y e A such that x ~ y is a non-zero perfect square is true with probability 1 — OQ;(1) as N OO. If A is a subset of the integers, it is k n o w n t h a t the sumset A + A {ai + a2 • ai,a2 G A} = contains 'more' a d d i t i v e s t r u c t u r e t h a n the original set. T h e case when ^ is a subset of positive u p p e r density has been s t u d i e d by B o u r g a i n , R u z s a , G r e e n a n d Sanders. F o r a more detailed discussion of the h i s t o r y of this p r o b l e m we direct the reader to the i n t r o d u c t i o n of [11] i n c l u d e d below. W e prove the following analogue for subsets of r a n d o m sets. T h e o r e m 1.1.6. Suppose that W is a random subset of events x G W, where x ranges over Z^r, are independent p = p(N) e {CN~^, 1], where 0 <$ k < exp where C\,C2 ^ ^ Then the progression 1 — O/C,Q(1) as N (1.1.2) - M o g ^) statement with \A\ > a\W\, the sumset A + A a k-term arithmetic IS true with probability large constants. OO. probability that a and k obey aMoglogA^ y C2 log ^ (log log log are sufficiently for every set AcW < 1/140. Assume such that the and have contains 1.2 Preliminaries and Notation T h r o u g h o u t t h i s paper, we w i l l be concerned w i t h subsets of the integers or subsets of t h e a d d i t i v e group •= Z/NZ. W e define e{9) := e-x.p{2m9). W e often use t h e n o t a t i o n A{x) t o denote the characteristic f u n c t i o n of the set A. Suppose t h a t / a n d g are real-valued functions w i t h / ( x ) > 0 for a l l X. W e w r i t e g{x) = 0{f{x)) If f(x) i f \g{x)\ < Cf{x) > 0 we w r i t e g{x) = o{f{x)) for some constant C > 0. i f Vixax-^oo g{x)/f {x) = 0. if there exists C i a n d C2 such t h a t C\f{x) < g{x) < C2f{x) Finally, we write g{x) = 0 ( / ( x ) ) . In this setting, we begin w i t h some p r e l i m i n a r y definitions a n d lemmas w h i c h w i l l be used t h r o u g h o u t . D e f i n i t i o n 1.2.1. Suppose that f : Z j y —* C . Then we define the discrete Fourier transform f(o ^= ^ E /(^)e(-xc/iv). D e f i n i t i o n 1.2.2. / / / and g are functions we define their such that f,g {f*g){x) := Yl fiy)9i^-y)- L e m m a 1.2.3. Suppose that f and g are functions Then the following identities (i) Parseval's (ii) Fourier such that f,g : Z^ —• C . hold: identity: inversion: m (iii) : ZN —» C , then convolution Convolution = E identity: me{-xi/N), W e w i l l denote the LP-norm of / by xex and if X = ZAT we w i l l write ||/||p. W e w i l l say that the probability A is F{A) W e define the related expectation := for a function / ; Zyv ^ C to be It w i l l also be useful to sometimes use the conditional ditional expectation, defined respectively, probability a n d con- : = I ^ , E ( / | X ) FiA\X) 1.3 of a set Bohr Sets In this section, we include some background relating to B o h r sets. In p a r t i c ular, we provide a detailed exposition of the results required i n [11], i n c l u d i n g a localized version of a theorem of C h a n g w h i c h is developed i n [14]. O n e of the first uses of B o h r sets i n additive number theory came i n a paper of B o u r g a i n [2] i n w h i c h he improved the upper b o u n d on r3{N) (the f u n c t i o n w h i c h denotes the size of the largest subset of { 1 , A ' ' } w h i c h contains no three t e r m a r i t h m e t i c progression). H i s proof relies on a density increment argument, however instead of i t e r a t i n g on a r i t h m e t i c progressions, he increases the relative density of a subset i n consecutive B o h r sets. A s we w i l l see, one can show that B o h r sets contain long arithmetic progressions. D e f i n i t i o n 1.3.1. A Bohr set is a set of the form B = 6 -h B{A,ô) 6 e Ziv, A C Ziv, € (0,2) and B{A, 6) := {XEZN : \e{x^/N) - 1\ < Ô for all ^ e where A}. We will say that the Bohr set B is of rank d := |A| and of radius Ô. In the following l e m m a , we state two basic facts about B o h r sets that we w i l l use t h r o u g h o u t . L e m m a 1.3.2. Suppose A C Z j v is a set of frequencies, Then the following and Ô, Ô-[,Ô2 € (0,2). are true, B ( A , 6i) + B ( A , ^2) C B ( A , ÔI + S2) (1.3.3) |S(A, (5)1 < C l ^ l | 5 ( A , 5/2)1 (1.3.4) for some absolute constant C > 1. D e f i n i t i o n 1.3.3. Let CQ € ( 0 , 1 / 2 ) be a small parameter. We will say that a Bohr set B{A, 5) is CQ-regular if P ( S ( A , (1 + cl)5) \ B{A, (1 - cl)ô)) < conm, S)). We will also say that B = b + B{A, ô) is regular i / - B ( A , 6) is regular. If J3 is a Co-regular B o h r set, t h e n we have the following size b o u n d . L e m m a 1.3.4. Let B{A,Ô) be a CQ-regular Bohr set. Then \BiA,ô)\>ic~'clS)\'^\. Proof. W e first notice t h a t B{A, 6) C B{A, (1 + cl)ô). Hence, b y regularity, we have \B{A, Ô)\B{A, (1 - çl)6)\ < \BiA, (1 + cl)ô)\B{A, (1 - cl)ô)\ <co\B{A,ô)\. Hence we m u s t have t h a t B{A, (l-cg)(5) is nonempty. Say b e B{A, Now {1-CQ)6). b y P r o p e r t y 1.3.3 we have BiA,clô) + B(A,{1 - cl)ô) c BiA,ô) and hence B{A,clS) + bcB{A,ô). F i n a l l y using P r o p e r t y 1.3.4 we have \B{A, c^5)| > {C^^CQÔ)^^^ as desired. L e m m a 1.3.5. Assume CQ is small enough. • Then for any A C Z/v with |A| < y/c^N and for any ÔQ > 0 there exists ô € ((^o/2, ^o) so that B{A, Ô) is Co-regular. Proof. W e pick r a d i i ÔQ > ôi > ... > ô^^i := ôo/2 where k = Q{N) t h a t ôi-i-i < (1 - cl)ôi < (1 -f cl)5i < 5i-i. such B y P r o p e r t y 1.3.4 we have |B(A,5o)|<Cl^l|i?(A,<5o/2)|. Hence, by the pigeonhole principle there exists 1 <i < k such that |5(A,5,_:)|<CW|B(A,5,+i)|. (1.3.5) U s i n g this, a n d the fact that S ( A , Jj+i) C S ( A , ( 5 j _ i ) , we have \BiA,il + cl)ôi)\<\B{A,ôi^,)\ <cW|B(A,(l-c2)<50|. Since B{A, (1 - cl)ôi) C B{A, (1 + cl)ôi), we must have \B{A, (1 + c2)<50\i?(A, (1 - cl)ô,)\ < \B{A, (1 + cl)5,)\- ^ ^ | B ( A , (1 + cl)5,)\ U s i n g the assumptions on |A| a n d k we have C^l^l/'^ = 1 + 0 { ^ ) gives the desired result. 1,3.1 A localized version of C h a n g ' s which • theorem In this section we w o u l d like to e x p l a i n a localized version of C h a n g ' s structure theorem due to Sanders. W e begin w i t h dissociated sets a n d the statement of C h a n g ' s theorem. W e also include a description of Sanders' result, its relation to the work of C h a n g a n d other ingredients of its proof. D e f i n i t i o n 1.3.6. We say that the set A := { A i , A ^ } is dissociated if k ^ C i A i = 0, 2=1 where Ci 6 {—1, 0,1}, implies Q = 0 for every 1 < i < k. D e f i n i t i o n 1.3.7. If A := {X\,X^} the set of the form we say that the cube spanned by A is 3 A := {Y,c^X^ : Ai G A , e {-1,0,1}}. T h e following t h e o r e m shows t h a t the set of large Fourier coefficients of a given subset of the integers must be s t r u c t u r e d . T h e o r e m 1.3,8. ( C h a n g ' s t h e o r e m ) Let p,a e (0,1], let A C ZN such that \A\ = aN and define R C Z / v by R:=^{^eZM:\Â{0\>pa}. Then there exists a maximal dissociated subset A C R so that R C A and |Â[<2p-2log(l/a). I n the remainder of t h i s section, we w i l l e x p l a i n the following p r o p o s i t i o n of Sanders w h i c h we require t o prove P r o p o s i t i o n 2.7.1. P r o p o s i t i o n 1.3.9. Suppose B := B{r,5) r] e (0,1]. Assume ACZN is a regular Bohr set and that e, f : ZN —^ R such that supp{f) C B. Then there exists and 5' € (0,1] such that |A|«e2|S|log(||/||£,%)||/||i.(3)), ""^d^lSllogdl/IJ-.^jll/lli.^^)) and {e6Z^:|/(0l>^ll/llLi(B)} C {e G ZTV : |1 - ei-x^/N)\ < r? V x € B ( r u A,(5')}. Sanders proves his theorem w i t h two lemmas w h i c h c a n be c o m p a r e d w i t h the t w o conclusions of T h e o r e m 1.3.8. T h e first step shows that the set of large Fourier coefficients of / must satisfy a s t r u c t u r a l i n c l u s i o n . T h e second step shows t h a t this inclusion is 'nice' i n a q u a n t i t a t i v e sense. Before we c a n state the t w o required lemmas, we must generalize the definition of dissociated sets i n the context of B o h r sets. D e f i n i t i o n 1.3.10. Suppose A := {X\,A^} Z. andm := ( m i ) f _ j wheremi e Define d mA := y ^ m i A ; i=i and d \m\ := ^ mi. i=l Let S be a non-empty S-dissociated symmetric neighborhood of 0. Then we say that A is if mA e S implies m j = 0 for every 1 < i < d. W i t h t h i s definition we use the following l e m m a to show that the set of large Fourier coefficients of a function / is contained i n a highly s t r u c t u r e d set. 1.3.11. Suppose B Lemma := B{T,ô) is a regular T] e (0,1]. Suppose / : ZAT —> K such that supp{f) I'M : \m\ dissociated > Bohr set and let e, C B and define 5 := If A IS a maximal e Z^ : € > subset of S then there exists '»^'^m^3d^ such that 5 C {e G Z i v : |1 - e{-x^/N)\ < T? V a; G S ( r U A , Ô')}. T h e proof of this l e m m a is straightforward a n d follows from basic facts about B o h r sets. Since the proof requires several steps, we recommend the reader consult [14] for a detailed proof. L e m m a 1.3.12. Suppose B, f, Further, e, rj and S are as in the previous assume that / ^ 0. Then there exists 5" » is regular and such that if A is a of S then lemma. such that B{T, 5") E Zjv : |B(OI ^ gj^}-dissociated subset |A|«6-2|B|log(||/||-,%)||/||i.(^)). W h i l e the proof of this l e m m a requires a localized version of R u d i n ' s inequality, several steps are similar to the proof of C h a n g ' s theorem. A g a i n we direct the reader to [14] for a complete proof. F i n a l l y , we w o u l d like to mention that P r o p o s i t i o n 1.3.9 can also be seen as a q u a n t i t a t i v e improvement of the d u a l version of a local Bessel inequality of G r e e n a n d T a o [10]. U s i n g the ideas from C h a n g ' s structure theorem, Sanders greatly improves the size on |A| w i t h a cost on the size of 6'. 1.4 A proof of Sarkozy's Theorem I n this section we include a proof of Sarkozy's theorem following G r e e n [6] w h i c h we require i n order to prove T h e o r e m 2.3.1. W e also remark t h a t as i n [6] we do not require the best k n o w n bounds, and so m i n i m i z e the technicalities w h i c h results i n a less t h a n o p t i m a l quantitative b o u n d . Theorem 1.4.1, (Sârkôzy's t h e o r e m ) Let 6 > {1,...,A''} so that \A\ > ON. Assume 0 and suppose A N is sufficiently large. exist elements x and y in A (x ^ y) so that x — y is a perfect C Then there square. W e begin w i t h some p r e l i m i n a r y lemmas a n d propositions. F o r the rem a i n d e r of this section, we assume S to be the set of non-zero squares less t h a n or equal to N/2. P r o p o s i t i o n 1.4.2. (Squares i n u n i f o r m sets) Let 5 > A C { 1 , A ' ' } such that \A\ = ôN. where a Assume 0. Suppose that \À{^)\ < a for every ^ ^0 2-30^13/2 _ j'hgn there exist x, y E A such that x — y is a perfect square. Proof. W e first note t h a t A must have density 5 on at least one of the intervals [0, A''/2] or [A''/2,A'']. W i t h o u t loss of generahty, assume B A n [0, A^/2] is such t h a t \B\ > ôN/2. If we t h e n consider ^ a n d 5 := as subsets of Zjv we c a n b o u n d the n u m b e r of integer square differences from below using the n u m b e r of square differences m o d u l o A^. T h e n u m b e r of square differences m o d u l o A'^ is larger t h a n S{x)B{y)A{y + x) =^ N^ SiOmM-O j;] (5)(05(o^(-o = N^mmÀ{Q)+N^ > N^/^S^/i -N'm^x]Â{0\'/' Y 1^(011^(011^(01'/' > A^3/2^V4-A^2j^ax|^(Op/'( Y ( E i^(on^/^( E 1^(01'')'^'"- iMOi'f' where we have used Parseval's i d e n t i t y a n d H o l d e r ' s inequality. U s i n g P a r seval again, we have the bounds [6] we have ||5||i2 < 21^/^2^-1/2 |-B(OP < ^ and | ^ ( 0 P ^ ^- F r o m p i t t i n g this a l l together, w i t h the as- s u m p t i o n of a - u n i f o r m i t y , we have Y S{x)B{y)A{y + x) > - cc"^ • 2''''^N'"H''''\ x,y T h i s q u a n t i t y is positive w i t h our choice of a as desired. • P r o p o s i t i o n 1.4.3. (Density increment) Suppose there exists ^ e Zyv such that > 2-30^13/21^1/^, r^^^^ j^g^g g^jg^^ a progression P with square difference such that and (ii) \P\ > W e require t h e following l e m m a cited i n [6] from [5]. T h e proof uses W e y l ' s inequality. L e m m a 1.4.4. Let a € Z j v and suppose 2^^^^ < t < N. some p <t Proof. Then there exists such that \p'^a\ < t'^/^^N. 1.4-3) B y L e m m a 1.4.4, we take t = N^/'^, a n d hence (Of proposition there exists p < A^^/^ such that \p'^^\ < A^63/64 difference progression P := {p'^,2p'^, ...,Lp^] y/^ t^gn define t h e square where L = •^N^^^'^. T h e n , we have the estimate L = N-'Yei-{jp^)aN) ; =1 L = N-'J2{l-{l-e{-{jp')aN))) L = L/N ~ N-'J2{l-e{-{jp')aN)). Hence, using t h e triangle inequality, we have > i 2A^ N o w we w o u l d like to show that A has increased density on some translate of P. W e begin by s u m m i n g the relative densities over a l l translates. I n the following c a l c u l a t i o n we use the definition of c o n v o l u t i o n as well as Parseval's identity a n d t h e c o n v o l u t i o n identity given i n L e m m a 1.2.3. J2\An{x-P)\' X = ^\J2 A{y){x X y = P)iy) J2\A*P{x) = N^\{A*Pm ^N'j2\^{o\'\pm' T h i s b o u n d shows t h a t we have the desired density increment for a given progression m o d u l o A'', however we require true Z progressions. Hence, we need to check t h a t our b o u n d holds for some square progression t h a t doesn't split. W e say t h a t a progression P is ' g o o d ' if i t is a genuine Z progression and we denote t h e set of such progressions b y G. < iV2/3 ^j^^i Lp^ < ^N^I^^N^/"^ O u r choice of L gives i ^ ^ Q ^ ^Yi3X the set of 'good' progressions must have size at least N^/^. Therefore, the c o n t r i b u t i o n to our estimate above from ' b a d ' progressions is given b y 5 ] |A n ( x - P ) p < 5 ^ L 2 < x^G L'N''l\ xiG Hence, we have xeG for large enough A''. O n the other h a n d , we have ^\An{x-P)f<ma^\Anix-P)\J2\An{x-P)\ xeG xeG < \A\Lma^\An{x- P)\. Hence, there exists XQ e G so t h a t \An{xoas desired. P)\>6{l + 2~^^Ô^^)\P\ • P r o o f of S a r k o z y ' s t h e o r e m : W e use the following iterative argument: S t e p 1: |j4o|/|Po|- Set PQ := {l,...,yVo} where NQ := If ^ 0 is such t h a t ^ o ( O I < N, AQ := A a n d So := for each ^ 7^ 0, we t e r m i n a t e . O t h e r w i s e , there must exist ^0 such t h a t |>l(^o)| > <^^^^^ • 2~^^. Hence by P r o p o s i t i o n 1.4.3 there exists a square difference progression P i such t h a t l-4onFi| — — — Kll > Ô0 + 2 63 rl2 00 and inl > i ^ o " " step 2: M a p the set AQ n P i to Ai C { 1 , [ 1 / 2 0 N Q ^ ^ ' ^ \ } =: P i . A n y square difference f o u n d i n Ai w i l l correspond to a square difference i n yloN o w a p p l y the same argument as i n Step 1. I t e r a t i n g t h i s argument, we w i l l reach a density of 2ÔQ after at most 2 6 3 j j - i i g^gpg a n d a density of 1 after less t h a n 2^^S~^^ steps. F i n a l l y , we check t h a t after our iterations we s t i l l have a set P^ w h i c h has at least two elements. W e c a n check t h a t t h i s happens as long as ciiV^^/^^'^')''^'' > 2 w h i c h we can guarantee as long as N > exp(exp(c(5~^^)). 1.5 The transference principle and pseudorandom sets T h e idea of transference enables us deduce results for sets w h i c h obey certain r a n d o m properties from results w h i c h are k n o w n for sets of positive upper density. T h e first such result of this t y p e is a version of R o t h ' s theorem i n r a n d o m sets due to K o h a y a k a w a , L u c z a k a n d R o d l [12] w h i c h we briefly described i n Section 1.1 a n d is stated precisely i n Section 2.1. a n a l y t i c proof of the same result is given b y Tao a n d V u i n [16]. A Fourier T h e first such a p p l i c a t i o n developed i n the Fourier a n a l y t i c setting was b y G r e e n [7] i n order t o prove his version of R o t h ' s theorem i n the primes. T h e o r e m 1.5.1. ( G r e e n ) Suppose that A C P, the set of primes, where P is defined to be such that h m sup ' n—>oo where Pn is the set of primes y, z E A such that x + z ~ 2y. ' = a > 0 jPnl less than or equal to n. Then there exists x, Green's theorem states t h a t if one considers a subset of the primes w i t h positive relative density, then R o t h ' s theorem s t i l l holds. I n his proof he exploits the fact t h a t t h e primes obey certain r a n d o m properties. L a t e r , G r e e n a n d T a o [9] reformulate the transference p r i n c i p l e i n a form we use below. T h e a p p l i c a t i o n i n their paper allows t h e m to deduce a version of R o t h ' s theorem for subsets of C h e n primes (those primes p such that p + 2 is t h e p r o d u c t of at most 2 primes) w i t h positive relative density. T h i s form of the transference p r i n c i p l e says t h a t if a set is m a j o r i z e d b y a 'pseudorandom' measure t h e n the set c a n be decomposed into a large bounded component plus a s m a l l u n i f o r m component. O n the b o u n d e d component we c a n a p p l y k n o w n results for sets of positive upper density, w h i l e the u n i f o r m component o n l y contributes a s m a l l error t e r m . L e m m a 1.5.2. Assume that f : ZN ^ [0, oo) satisfies E ( / ) > ô > 0 and 11/11, < M for some 2 < q <3. the pseudorandom (1.5.6) also that f < ly, where u : Zjv —>• [0,oo) obeys Assume condition (1-5.7) \\m~h=o\\oo<V for some 0 < r] <1. Let / i ( x ) = E ( / ( x + y i - Ï / 2 ) : 2/1,^2 6 ^ o ) , where Bo = {x: | e - 2 - « - / ^ _ i | < ^o, ^ € A Q } , AO = for some eo to be fixed later. Let also f2{x) — f{x) (t)o<f,<i (ii) E / i + =Ef>ô, 1/(01 > — fi{x). ^o} Then {i+nsor'H (Hi) l i / 2 ( O l l o o < 3 ( l + 77)eo, (iv) |7i(OI < 1 / ( 0 1 for all ^ e ZN and i = 1,2. holds with f replaced by f^- In particular, (L5.6) Proof, (i) T o verify t h a t | / i | < 1 + 77A'"/|J3o| we use the definition of f\, the fact that / is b o u n d e d b y the pseudorandom function v, a n d the F o u r i e r inversion f o r m u l a 1.2.3 ( i i ) . W e have, l / l | = \^yi,y2€Bo{f{x + < ^yuy2eBo{Hx + ^ = ^yim^Bo < Yl <l yi-y2)) yi-y2)) P(e)e(-(x + yi-y2)^/7V) V{Oe{-x^/N)\EyeBoe{-y^/N)(' mmyeBoe{~yaN)\' + r]N/\Bo\ w h i c h completes the proof of (i). (ii) T h e fact that E / i = Ef follows directly from the definition of / i . (iii) a n d (iv) W e begin w i t h the observation that | / i ( O I ^ 1 / ( 0 1 since = J2 ^yi,y2eBofix + yi - y2)e{-x^/N) xeZN w h i c h verifies (iv) i n the case that z = 1. U s i n g this equality, we have Î2{o = = m-m) m{i-W'yeBMyum?) w h i c h shows (iv) w i t h i = 2. N o w , if ^ e AQ then for each y e S o we must have \e{y^/NJ - 1| < eo by the definition of BQ. C o m b i n i n g this w i t h the identity for /2 above, we must have I/2I <3eoE(z^) < 3 ( l + r/)eo. O n the other h a n d , if ^ ^ AQ then by the definition of AQ we have | / ( 0 I < and hence, combining this w i t h our identity for /2 we have I/2I establishing (iii). < eo • T h e following l e m m a , from [16], is needed to deduce L e m m a 2.2.6 w h i c h allows us t o exploit t h e r a n d o m properties of v i n order to deduce a n l'^ estimate from a n P one. L e m m a 1.5.3. Suppose that f : ZN ^ [0, oo) satisfies Ef assume that f < v, where v satisfies the pseudorandom > ô > 0 and condition F(0-lç=0||oo</? for some 0 < 77 < 1. Define A := e ZAT : |/(^)| > a} for any a > 0. Then |A| < 4 / a 2 for all a > 2r?i/2. P r o o f of L e m m a 2.2.6: B y a s s u m p t i o n , we have ||/||2 < cr]~'^^^. Hence, we have - E E \m\'^'+ i--\m\<4r, i/(0P+^ e.|/(Ç)l>4r) <4ry^ E E E <cr^^/' + J2'^'('+'^\{^:\m\^2'^}\ k < cr;'/2 ^ ^ 2''(2+£) . 2-2fc+i k < M where we have used L e m m a 1.5.3 for the second to last step. Bibliography [1] F . B e h r e n d , On the sets of integers arithmetic progression. which contain no three terms in P r o c . N a t . A c a d . S c i . , 23 (1946), 331-332. [2] J . B o u r g a i n , On triples in arithmetic 9 (1999), 968-984. progressions, Geom. Punct. A n a l . [3] G . A . F r e i m a n , Foundation of a structural theory of set addition (translated from Russian), Translations of M a t h e m a t i c a l M o n o g r a p h s , 37, 1973. [4] H . Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J . d ' A n a l y s e M a t h , 71, 1977, 204-256. [5] T . Gowers, A new proof of Szemerédi's 12 (2001), 465-588. [6] B . J . G r e e n , On arithmetic structures M a t h . J o u r . , 114 (2002), 215-238. theorem, Geom. Funct. Anal., in dense sets of integers, Duke [7] B . J . G r e e n , Roth's Theorem in the primes, A n n a l s of M a t h . 161 (2005), 1609-1636. [8] B . J . G r e e n , T . T a o , The primes contain arbitrarily gressions. A n n a l s of M a t h . , to appear. long arithmetic pro- [9] B . J . G r e e n , T . T a o , Restriction theory of the Selberg Sieve, with applications. J o u r n a l de Théorie des N o m b e r s de B o r d e a u x , 18 (2006), 137-172. [10] B . J . G r e e n , T . T a o , An inverse theorem for the Gowers U^{G) P r o c . E d i n b u r g h M a t h . S o c , to appear. norm, [11] M . H a m e l a n d I. L a b a , Arithmetic structures in random sets, I N T E G E R S : E l e c t r o n i c J o u r n a l of C o m b i n a t o r i a l N u m b e r T h e o r y , 8, 2008. [12] Y . K o h a y a k a w a , T . L u c z a k , V . Rôdl, Arithmetic progressions of length three in subsets of a random set, A c t a A r i t h . 75 (1996), 133-163. [13] K . R o t h , On certain sets of integers, J . L o n d o n M a t h . Soc. 28 (1953), 245-252. [14] T . Sanders, Additive structures C a m b r i d g e P h i l o s . Soc. [15] A . Sarkozy, On difference H u n g a r , 31:125-149, 1978. [16] T . Tao, V . V u , Additive in sumsets, to appear i n M a t h . P r o c . sets of integers combinatorics, i. A c t a M a t h . A c a d . S c i . C a m b r i d g e U n i v . Press, 2006. [17] P . Varnavides, On certain sets of positive M a t h . S o c , 34 (1959), 358-360 density, DEPARTMENT OF BRITISH VANCOUVER, mehamel@math. OF MATHEMATICS, B.C. V6T ubc. ca 1Z2, UNIVERSITY CANADA Journal London COLUMBIA, Chapter 2 Arithmetic structures in random sets A r i t h m e t i c structures i n r a n d o m sets^ M a r i a h H a m e l a n d Izabella L a b a Abstract W e extend two w e l l - k n o w n results i n additive number theory, Sarkozy's theorem on square differences i n dense sets a n d a theorem of G r e e n on long a r i t h m e t i c progressions i n sumsets, to subsets of r a n d o m sets of a s y m p t o t i c density 0. O u r proofs rely on a restriction-type Fourier a n a l y t i c argument of G r e e n a n d G r e e n - T a o . 2.1 Introduction T h e purpose of this paper is to extend several basic results i n additive n u m ber theory, k n o w n for sets of positive density i n Z^v, to the setting of r a n d o m sets of a s y m p t o t i c density 0. T h i s Une of work originated i n the paper of Kohayakawa-Luczak-Rôdl [29], who proved a random-set analogue of R o t h ' s theorem on 3-term a r i t h m e t i c progressions. R o t h ' s theorem [32] asserts that for any fixed 6 > 0 there is a large integer NQ such that iî N > No a n d if A is a subset of { 1 , . . . , AT} w i t h |^| > ON, t h e n A contains a n o n - t r i v i a l 3-term a r i t h m e t i c progression a,a + r,a + 2r w i t h r ^ 0. T h e article [29] raises the following question: are there any sets W, sparse i n { 1 , . . . , N}, w i t h the p r o p e r t y t h a t any set A c o n t a i n i n g a positive p r o p o r t i o n of the elements of W must c o n t a i n a 3-term a r i t h m e t i c progression? T h e authors proceed to answer it i n the affirmative for r a n d o m sets: * A version of this paper is published. M . H a m e l and I. L a b a , A d d i t i v e structures in random sets, I N T E G E R S : Electronic Journal of Combinatorial Number Theory, 8 2008. T h e o r e m 2.1.1. [291 Suppose that W is a random subset ofZ^ such that the events x G W, where x ranges over ZN, are independent and have probability p = p{N) G {CN~'^/'^, 1]. Fix a > 0. Then the statement every set A CW progression is true with probability with \A\ > a\W\ contains a 3-term arithmetic 1 — O Q ( 1 ) as N ^ OO. T h e current interest i n questions of this type is motivated by the work of G r e e n [25] a n d G r e e n - T a o [26], [27] on a r i t h m e t i c progressions i n the primes, where the "pseudorandomness" of the almost-primes plays a key role. F o r example, T a o - V u [39, Section 10.2] give an alternative (and simpler) proof of T h e o r e m 2.1.1 under the stronger assumption that p > C N ~ ^ w i t h 9 small enough. W h i l e the argument i n [29] is c o m b i n a t o r i a l a n d uses Szemerédi's regularity l e m m a , the proof i n [39] is F o u r i e r - a n a l y t i c a n d reUes i n p a r t i c u l a r on a restriction-type estimate from [25], [27]. It is n a t u r a l to ask w h i c h other results from additive number theory can be extended to the r a n d o m set setting. W h i l e the methods of [29] do not seem to e x t e n d to other questions, the decomposition technique i n [27] turns out to be more robust. W e are able to use i t to prove r a n d o m set analogues of two w e l l - k n o w n results: Sârkôzy's theorem on square differences, a n d a theorem of G r e e n on long a r i t h m e t i c progressions i n sumsets. W e note t h a t the concept of pseudorandomness has played a m a j o r role i n m a n y of the basic e x t r e m a l results i n additive number theory, such as Szemerédi's t h e o r e m on a r i t h m e t i c progressions. Specifically, i n order to find a certain t y p e of an a r i t h m e t i c structure (such as an a r i t h m e t i c progression) i n sets of positive density, one often begins by showing that such structures are c o m m o n i n a p p r o p r i a t e l y defined pseudorandom sets. It is not clear whether our results w i l l have applications of this type, as the corresponding e x t r e m a l results for sets of positive density are already k n o w n . O n the other h a n d , we expect t h a t the methods developed here w i l l be useful i n p r o v i n g similar results i n settings where the background set 14^ is a given set of density zero w i t h sufficiently good pseudorandom properties (e.g. the primes, the C h e n primes). F o r example, one could inquire about the a r i t h m e t i c properties of sets of the form A-\- B, where A a n d B are subsets of the primes w i t h relative positive density. W e now give the precise statement of our results. T h r o u g h o u t the paper, VF is a r a n d o m subset of ZAT, w i t h each x e ZAT belonging to W independently w i t h p r o b a b i l i t y p € (0,1]. W e w i l l assume that p > A''""^, where 6 is a sufficiently s m a l l positive number. In p a r t i c u l a r , we allow p to go to 0 as AT oo. W e also fix J > 0 a n d let AcW, \A\ = S\W\. Sarkozy's theorem (proved also independently b y Purstenberg) states that for any fixed positive number ô there is a large integer A^o such that if N > NQ a n d if is a subset of { 1 , . . . , iV} w i t h |A| > ON, then A contains two distinct elements x, y such that x — y is a perfect square. T h e best k n o w n q u a n t i t a t i v e b o u n d , due to P i n t z , Steiger a n d Szemerédi [31], is that one m a y take NQ = (log A'') '°s log AT ^j^g converse d i r e c t i o n , R u z s a [33] constructed a set of size A^i-0-26V -^^hich contains no square difference. W e are able to prove the following. T h e o r e m 2.1.2. Suppose that W is a random subset of ZN such that the events x 6 W, where x ranges overZ^, are independent and have probability p = p{N) e {cN~^, 1] where 0 < 6» < 1/110. Let a > 0. Then the statement for every set A C W with \A\ > aW, there are x,y that X — y is a non-zero perfect square is true with probability 1 — Oa(l) as N e A such oo. W e also have an analogous result for higher power differences, see Section 2.5. If A, B are two sets of integers, we w i l l write A + B = {a + h : a € A,b e B}. L e t W he a r a n d o m set as described above, but w i t h 6 e (0,1/2]. O n e can show using a p r o b a b i l i s t i c argument t h a t i t holds w i t h p r o b a b i l i t y 1 - o ( l ) that the sumset A-\- Aot every subset A CW w i t h |A| > a\W\ has density at least i n Zjv ^. If 6* is close enough to 0, then we can prove the following stronger result using F o u r i e r - a n a l y t i c methods. P r o p o s i t i o n 2.1.3. Suppose that W is a random subset o / Z j v such that the events x G W, where x ranges overZ^, are independent and have probability p = p{N) e {CN-\ I], where 0 < 9 < 1/140, Then for every (3 < a, the statement for every set A C W with \A\ > a\W\, we have \A-\- A\ > f3N is true with probability 1 — OQ,^(1) as A" —> G O . It is easy to see that one can have ]yl -f A | proposition: let A^ = W D{P Z/v of step about t h a t \A^\ » aN i n the setting of the + x), where P is an a r i t h m e t i c progression i n a n d length about aN. a\W\ for some x, while [A^c + A n averaging argument shows < 2|P| ^ aN. ^ We are grateful to Mihalis Kolountzakis for pointing this out to us and communicating a short proof. O u r second m a i n result concerns the existence of long a r i t h m e t i c progressions i n sumsets. B o u r g a i n [18] proved t h a t if A, B are sumsets of { 1 , . . . , A?^} w i t h 1^1 > aN, \B\ > (3N, t h e n A + B contains a A;-term a r i t h m e t i c pro- gression w i t h k > exp(c(a/31og A^)i/3 _ l o g l o g i V ) . (2.1.1) T h e p o i n t here is t h a t a sumset has m u c h more a r i t h m e t i c structure, and therefore contains m u c h longer a r i t h m e t i c progressions, t h a n w o u l d be norm a l l y expected i n a set of a s i m i l a r size (based on Szemerédi's theorem, for example). B o u r g a i n ' s b o u n d was i m p r o v e d by G r e e n [23] to k > exp(c(a/31ogAr)V2 _ i o g i o g A r ) , (2.1.2) w h i c h is the best k n o w n result i n this d i r e c t i o n so far. A n alternative proof of essentially the same b o u n d was given more recently by Sanders [35]. O n the other h a n d , R u z s a [34] gave a c o n s t r u c t i o n showing that the exponent 1/2 i n (2.1.2) cannot be i m p r o v e d beyond 2 / 3 . N o t e that ii A = B, the estimate (2.1.2) gives a n o n - t r i v i a l result o n l y w h e n a > {\ogN)~^/'^, and i n p a r t i c u l a r sets w i t h d e n s i t y N~^ are not allowed. T h e case of sparse sets was considered more recently by C r o o t - R u z s a Schoen [21]. T h e authors proved t h a t iîA,B C ZN obey \A\\B\ > {6N)2 then A + B contains a k-term a r i t h m e t i c progression. T h e y also gave a cons t r u c t i o n of sets A cZi\f w i t h \A\ > N^"^, where 9 is s m a l l enough depending o n e > 0, such t h a t A + A does not c o n t a i n a n a r i t h m e t i c progression longer t h a n ex.p{c9~3~^). O u r result is the following. T h e o r e m 2.1.4. Suppose that W is a random events x G W, where x ranges overZ^, p = p{N) e (CN~^, are independent 1], where 0 < 9 < 1/140. Assume k < exp where C\,C2 subset o / Z ^ r such that the ^ log log AT and have ^ large constants. Then the statement for every set Ad W with \A\ > a|H^|, the sumset A + A a k-term arithmetic progression is true with probability 1 (2.1.4) y C2 log ^ (log log log i V + log ^ ) y are sufficiently — Ok,a(^) as N ^ oo. probability that a and k obey contains A n o n - q u a n t i t a t i v e version of the result, n a m e l y that the displayed statement i n the theorem is true w i t h p r o b a b i l i t y 1 — o ( l ) as A'' -> oc if a and k are fixed, can be obtained by a p p l y i n g Szemerédi's theorem to the positive density set A-\-A. O u r point, as i n [18] or [23], is that the a r i t h m e t i c progressions i n d i c a t e d by T h e o r e m 2.1.4 are m u c h longer t h a n those i n Szemerédi's theorem, a n d that t h e y can be found using a much easier argument. For comparison, the current best bounds i n Szemerédi's theorem [22] i m p l y that a set of relative density a in ZN should c o n t a i n fc-term a r i t h m e t i c progressions w i t h k < log log ^ log log A^^ w h i c h is m u c h weaker t h a n (2.1.4). T h e bounds on 9 i n Theorems 2.1.2 a n d 2.1.4 are due to our choices of exponents i n the proofs a n d are probably not o p t i m a l . T h e n a t u r a l threshold w o u l d be 1/2, as i n [29]. However, it does not seem possible to extend our results to a l l ^ < 1/2 using the same t y p e of arguments as i n this paper. T h e article is organized as follows. In the next section we e x p l a i n the n o t a t i o n a n d s u m m a r i z e the k n o w n results that w i l l be used repeatedly. T h e o r e m 2.1.2 is proved i n Sections 2.3 a n d 2.4. Its analogue for higher power differences. T h e o r e m 2.5.1, is stated a n d proved i n Section 2.5. T h e proof of T h e o r e m 2.1.4 is given i n Section 2.6, w i t h the proofs of the m a i n estimates postponed to Sections 2.7 and 2.8. T h e proof of P r o p o s i t i o n 2.1.3, w h i c h involves a simplified version of the argument i n the proof of T h e o r e m 2.1.4, concludes the paper. 2.2 Preliminaries W e first e x p l a i n the n o t a t i o n . W e use |A| to denote the c a r d i n a h t y of a set A C Z j v . T h e probability of a set A is P ( ^ ) = N~^\A\, a n d the expectation of a f u n c t i o n / : ZAT ^ C is defined as Ef = E,f = N-' Y2 /(^)- XGZJV W e w i l l also sometimes use c o n d i t i o n a l p r o b a b i l i t y and expectation m\X) = l ^ i ^ , Eif\X) = E^^xfix) = j^^Yl fi^)- Whenever the range of a variable (in a s u m , expectation, etc.) i n d i c a t e d , i t is assumed to be a l l of Z j y . is not We w i l l also use the n o t a t i o n l l / l l p = ( E x 1 / ( ^ ) 1 " ) ' / " a n d Wfhrçx) = (E.exl/(^)r)'/"throughout t h e paper w i l l be independent of A'^, a, a n d A;. T h e discrete F o u r i e r t r a n s f o r m of / is defined b y A l l constants /(0=E,/(a:)e-2--«/^. W e have t h e u s u a l P l a n c h e r e l i d e n t i t y E / ? = f o r m u l a f{x) = E ç . z . / ( O e - ^ ^ ^ ^ / ^ . W e define t h e convolution of two functions f, g : ZN (/*5)(x) = E / ( 2 ; M x - y ) = y inversion E fd C hy the formula f^^)9{s). E t,s:t+s=:x W e have t h e i d e n t i t y Nfg = f * g. W e r e c a l l a few basic results about B o h r sets, a l l of w h i c h are s t a n d a r d i n t h e l i t e r a t u r e a n d c a n be found e.g. i n [28], [39], or i n [19] where regular B o h r sets were first i n t r o d u c e d . D e f i n i t i o n 2.2.1. A B o h r set is a set of the form B = b + B{A, 6), where beZN, ACZN, ôe (0,2), B{A, ô) = {xeZN: and je^'^*^?/^ - 1| < <5 for all ^ € A } . We will often refer to |A| and 5 as the rank and radius of B, respectively. D e f i n i t i o n 2.2.2. Letco be a small positive constant which will remain fixed throughout the paper. ¥{B{A, We will say that a Bohr set B{A, 6) is regular if (1 + cl)ô) \ B{A, (1 - elm < c o P ( B ( A , Ô)). We will also say that B = b + B{A, ô) is regular if B{A, ô) is regular. L e m m a 2.2.3. If B = B{A,Ô) L e m m a 2.2.4. Assume with \A\ < ^JCQN is a regular Bohr set, then F(B) > (ccg(^)l^l. that co is small enough. Then for any A C Z^ and any ÔQ> Q there is a ô E {^,ôo) such that B{A,ô) is regular. W e w i l l need a F o u r i e r - a n a l y t i c argument w h i c h first appeared i n [25] i n a sHghtly different f o r m u l a t i o n and i n [27] as stated, a n d was a d a p t e d i n [39] to a r a n d o m set setting. Specifically, [25] a n d [27] i n t r o d u c e d the decomposition f = f\ + f2 defined below, where / i is t h e " s t r u c t u r e d " b o u n d e d p a r t , a n d /2 is u n b o u n d e d b u t r a n d o m . W e w i l l need several results concerning the properties of f\ a n d / 2 , w h i c h we collect i n t h e next t w o lemmas. T h e first one is contained i n the proofs of [27, P r o p o s i t i o n 5.1] or [39, T h e o r e m 10.20]. that f : ZN L e m m a 2.2.5. Assume [0, oo) satisfies Wfh for some 2 < q < 3. Assume the pseudorandom E(f) > ô > 0 and (2.2.1) < M also that f < u, where u : Z^r —> [0, oo) obeys condition MO (2.2.2) - h=o\\oo < V for some 0 < r/ < 1. Let fi{x) = E{f{x + yi-y2): yi,y2 € ^o), where Bo = {x: | e - 2 - « - / ^ _ i | < ^o, ^ € A o } , AQ - for some eg to be fixed later. Let also f2{x) = f{x) (i)0<fi<l (il) E / i = (iii) + il + : |7(C)| > eo} — f\{x). Then nBor')ri, Ef, li/2lloo < 3 X l + 7?)eo, M |7i(OI < 1/(01 for all ^ e ZN and i = 1,2. In particular, holds with f replaced by / a . (2.2.1) I n order t o be able to a p p l y L e m m a 2.2.5, we need t o have the estimate (2.2.1) for some 2 < q < 3. T o this end we have t h e following result, based on t h e S t e i n - T o m a s argument as used i n [25], [27], a n d contained i n t h e form we need i n [39, L e m m a 10.22 a n d proof of T h e o r e m 10.18]. L e m m a 2.2.6. Let f and v be as in Lemma (2.2.1) 2.2.5, except that instead of we assume that II/II2 < C r ? - / 4 for some e > 0. Then (2.2.1) holds with g = 2 -I- e. W e a d a p t t h i s argument t o t h e r a n d o m setting as i n [39, Section 10.2]. Suppose t h a t I ^ is a r a n d o m subset of ZN such t h a t each x EZM belongs to W i n d e p e n d e n t l y w i t h p r o b a b i l i t y p 6 (0,1). W e w i l l assume t h a t p > where 0 < ^ < 1/100. W e also fix (5 > 0 a n d let AcW, y{x) = p-^Wix), fix) L e m m a 2.2.7. Let v and f be the random (i) WHO - lç=o||oo = 0 ( A - ^ / ^ ) (ii) Wfg = N-^lfg = 0{p'^) = p-^A{x). variables with probability < , \A\ = Ô\W\. W e let defined above. 1 - o(l), with probability 1 - o(l). Then P a r t (i) of tlie l e m m a follows from w e l l - k n o w n p r o b a b i l i s t i c arguments. It c a n be found e.g. i n [39, C o r o l l a r y 1.9 a n d L e m m a 4.15], or extracted from t h e proof of L e m m a 14 i n [23]. Observe i n p a r t i c u l a r t h a t (i) w i t h Ç = 0 says t h a t F{W) = p ( l + OiN''^^^)) w i t h p r o b a b i l i t y 1 - o ( l ) . P a r t (ii) follows from this a n d the P l a n c h e r e l identity. 2.3 A Varnavides-type theorem for square differences T h e purpose of this section is to prove the following theorem. T h e o r e m 2.3.1. Let 0 < ô < 1 and N > 1 be a prime ZAT —» [0,1] be a bounded function such that integer. Let f : Ef > Ô. Then we have E{f{n)f{n + r^)\n,reZN, 1 < r < [y/WJÎ]) > c{ô) - os{l). T h e o r e m 2.3.1 strengthens Sârkôzy's theorem (stated i n the i n t r o d u c tion) i n t h e same w a y i n w h i c h a theorem of V a r n a v i d e s [40] strengthens R o t h ' s theorem o n 3-term a r i t h m e t i c progressions. It guarantees t h e existence of " m a n y " square differences i n a set of positive density, instead of just one. Proof. T h e proof combines Sârkôzy's theorem w i t h a m o d i f i c a t i o n of V a r navides's c o m b i n a t o r i a l argument [40]. W e first note that i t suffices t o prove the result for characteristic functions. T o see this, let / be as i n the theorem, and define A := {n e ZN •• f{n) > 5/2}. T h e n \A] > 6N/2 a n d / > f o n A. Hence, assuming the result for characteristic functions, we have E ( / ( n ) / ( n + r2)) > jE{A{n)A{n + r^)) > jc{S/2). W e now t u r n to the proof of the result for characteristic functions. L e t ^ C Z i v such t h a t \A\ > ON a n d N is sufficiently large. W e w i l l consider a r i t h m e t i c progressions Px,r = {x,x + r^,...,x + {k~ l)r^}, l<x<x + {k- l)r^ < N (2.3.1) where x , r e Zyv, r < \/3N, and where € N is chosen so that the conclusion of Sârkôzy's theorem holds for subsets of { 1 , f c } w h i c h have size at least ijfc. Suppose that < f . (2.3.2) W e say t h a t a progression Px^r as i n (2.3.1) is good i f \Px,rnA\>^ôk. (2.3.3) L e t Gr{N) denote t h e set of g o o d progressions Px,r{N) claim that for a fixed r. W e |G,(iV)| > ^SN. (2.3.4) Indeed, we have \A n (kr^, N - kr^)\ > \A\ - 2kr'^ > 5N - 2kr^ > 0(1 - k ^N, where at the last step we use (2.3.2). E a c h a € An(fcr^, N—kr'^) is contained i n e x a c t l y k progressions Px^r- Hence \AnPx,r\>kô{\-^)N>^ôkN (fe>8). x:l<i<a;-t-(fc-l)r2<iV O n t h e other h a n d , the number of progressions P^.r for a fixed r is clearly b o u n d e d by A'', hence we have a n upper b o u n d \AnPx,r\<N-^ôk E + GriN)k. x:l<x<x+{k-l)r^<N C o m b i n i n g these bounds yields (2.3.4) as c l a i m e d . L e t G{N) := T.r:r^<^J^ Gr{N). G{N) Then > ^ ' - f = c,m^/\ (2.3.5) since k depends o n l y o n 6. B y S a r k o z y ' s theorem, each g o o d progression Px^r contains a square difference. W e n o w count the n u m b e r of good progressions w h i c h m a y contain a fixed square difference pair x,x + . Clearly, a:,x - f c a n be contained i n at most k — \ progressions w i t h step size a n d at most \k{k — 1) progressions w i t h step size r'^jt for integers t> \. Since k depends only o n J , the t o t a l number of progressions containing x,x + r^ is bounded b y C2{ô). T h u s the t o t a l number of square differences i n A must be at least 4 K i V ' / ' = c(<J)iV3/2. C2{à) S u b t r a c t i n g off the t r i v i a l progressions ( w i t h = 0) gives the desired result. • 2.4 Proof of Theorem 2.1.2 Let W, A be as i n T h e o r e m 2.1.2. A t least one of the sets Ai = An [0, A^/3), A2 = An [N/3,2N/3), ^ 3 = ^ n [2A^/3, A^), say Ai (the other two cases are identical), has size at least \A\/3. Define v,/ as in L e m m a 2.2.7, b u t w i t h A replaced b y Ai. B y L e m m a 2.2.7, the assumptions of L e m m a 2.2.6 w i t h rj = A ^ - V 5 a n d e = 1/11 are satisfied w i t h p r o b a b i l i t y 1 - o ( l ) , thus (2.2.1) holds w i t h q = 23/11. W e w i l l henceforth c o n d i t i o n o n these events. L e t / = / i + /2 as i n L e m m a 2.2.5, w i t h eo = eo(a) s m a l l enough t o be fixed later. W e w o u l d like to ensure t h a t ||/i||oo<2. (2.4.1) B y L e m m a 2.2.5, this w i l l follow if A r - i / 5 ( l + P ( 5 o ) - i ) < 1. (2.4.2) B y L e m m a 2.2.3, we can estimate ¥{Bo) » (ceo)''^°l, while b y (2.2.1) a n d C h e b y s h e v ' s inequality we have |Ao| < {M/CQ)'^^/^^ . N o w a short calculation shows t h a t i f log — < c i log log A^ eo (2.4.3) w i t h c i s m a l l enough, w h i c h we w i l l assume henceforth, then (2.4.2) a n d (2.4.1) h o l d . It suffices to prove that E ( / ( x ) / ( x + r^)\x, r 6 ZAT, 1 < r < ^/N/3) > c{5) - 05(1). (2.4.4) Indeed, since Ai C [0, A ' / 3 ) , any square difference a — a'^^r"^ w i t h a, a' G Ai and 1 < r-2 < A^/3 must be a n actual square difference i n Z , not just a square difference m o d A''. W e w r i t e f{x)f{x + r^) = Yl'i,j=i fi{x)fj{x + r ^ ) , a n d estimate the exp e c t a t i o n of each t e r m . A p p l y i n g T h e o r e m 2.3.1 to / i , we get a lower b o u n d on the m a i n t e r m E ( / i ( x ) / i ( x + r2)|x,r € Z ^ , 1 < r < v W s ) > ci((5) - 05(1), (2.4.5) if N is large enough so that (2.4.3) holds. W e now t u r n to the error estimates. We write E ( / 2 ( x ) / 2 ( x + r2)|x,r € Z i v , 1 < r < / Â / S ) - %/3ÎVE(/2(x)/2(x + t)S{t)\x, t e Z N ) , (2,4,6) where S{-) denotes the characteristic function of the squares less t h a n A ' / 3 , F r o m G r e e n [24] we have the estimate 11^1112 < 2''/''N-y\ based o n a number theoretic b o u n d on the number of representations of an integer as the s u m of s i x squares. U s i n g also Parseval's identity a n d Holder's inequality, we have Eif2{x)f2{x + t)S{t)\x,teZN) <2i9/i2^r-i/2||/,fJ/;2|,;^||i/i2 P l u g g i n g this into (2.4.6), we see that E ( / 2 ( x ) / 2 ( x + r 2 ) | x , r G ZJV, 1 < r < x/ÎV/S) < c i ( 5 ) / 4 if eo was chosen sufficiently s m a l l depending on 5. T h e " m i x e d " error terms are estimated similarly. C o m b i n i n g the error estimates w i t h (2.4.5) yields (2.4.4) as desired. 2.5 Power differences In this section we show that a modification of the proof of T h e o r e m 2.1.2 yields a n analogous result for higher power differences. T h e o r e m 2.5.1. Suppose that W is a random subset of Zpj such that the events x G W, where x ranges overZ^, are independent and have probability p = p{N) € {cN'^, 1] with 0 < 6 < 6k, where 6k is small enough depending on fc G N . Let a > 0. Then the statement for every set A C W with \A\ > aW, x — y — n^ for some n G N is true with probability Ok^aiX) as N 3 x,y e A such that oo. Since the proof is very similar to that of T h e o r e m 2.1.2, we o n l y sketch the m a i n steps. Instead of T h e o r e m 2.3.1, we w i l l need a similar result for higher powers, w h i c h c a n be proved by exactly the same argument. T h e o r e m 2.5.2. Let 0 < 5 < 1, and let N > 1 be a prime integer. / : Z^r —> [0,1] be a bounded function such that Ef > Ô. Then we have Eifin)fin + r'')\n,reZN, 1 < r < [^N/Sl) > c{6) - Let os{l). W e now follow the argument i n Section 2.4. Define u, f, fi, /2 as i n the proof of T h e o r e m 2.1.2. A p p l y i n g T h e o r e m 2.5.2 to fi, we see that E(/i(x)/i(x + r'^)|x,rGZ;v,l <r-< !^/N/3) > c{5) - oe^,,^M{r]). T o estimate the error terms, we invoke the a s y m p t o t i c formula for W a r i n g ' s p r o b l e m (see e.g. [30]), w h i c h implies that RkM^) € Z ^ | 4 + - + 4k = ••= \{iai,agfc) m o d Ar)}| < cN^. B y c o n v o l u t i o n and P a r s e v a l identities, this translates to \\Pk\\6k < where Pk denotes the characteristic function of the set of fc-th powers smaller t h a n N/3, a n d c, c i are constants depending on fc. N o w we are able to estimate t h e error terms as i n Section 2.4, for example we have E(f2ix)f2{x + r)Pk{r)) < \\Pkhk\\h\\\\lt^^^^^^^ < ciCN'I'^-hl"'. A t the last step we used that (2.2.1) holds w i t h q = enough. T h e proof is finished as i n Section 2.4, if 6k is small 2.6 Long arithmetic progressions in sumsets W e now t u r n t o T h e o r e m 2.1.4. I n this section we prove the theorem, m o d u l o the two m a i n estimates (2.6.1), (2.6.7) w h i c h w i l l be proved i n t h e next two sections. Our proof w i l l combine the arguments of Sanders [35] w i t h those of Green-Tao [27]. L e t W,A be as i n T h e o r e m 2.1.4, a n d define i/, f as i n L e m m a 2.2.7. W e w i l l show t h a t , w i t h high probability, there is a reasonably large B o h r set B o n w h i c h we have f * f{x) > 0 for a l l b u t a few values of X. B u t / * / is s u p p o r t e d on A + A, hence a l l b u t a s m a l l fraction of B is contained i n A + A. T h e proof is concluded b y i n v o k i n g a pigeonholing argument from [35], w h i c h says t h a t t h e p o r t i o n of B contained in A + A contains a long a r i t h m e t i c progression. T h e details are as follows. F i x k (the length of t h e progression), a n d let cr = {16k)~^. W e w i l l also assume t h a t k > ko a n d a < ao , where ko eN is a sufficiently large absolute constant a n d ao > 0 is a sufficiently s m a l l absolute constant. B y L e m m a 2.2.7, the assumptions of L e m m a 2.2.6 w i t h rj = N~'^^^ a n d e = 1/9 are satisfied w i t h p r o b a b i l i t y 1 — o ( l ) , thus (2.2.1) holds w i t h q = 19/9. L e t / = / i -f /2 as i n L e m m a 2.2.5, w i t h eo = eo(a, cr) s m a l l enough to be fixed later. W e w i l l assume that (2.4.3) holds w i t h c i sufficiently s m a l l ; as i n Section 2.4, i t follows that ||/i||oo < 2. W e need a n extension of a result of Sanders [35]: there are regular B o h r sets B := b -h B ( r , 6) a n d B' :=b + B{r, 5') such t h a t {xeB': ( / i * f,){x) > ^\B\}\ > (1 - a)\B'\, (2.6.1) and i' » ^ , |r| « a - 2 l o g ( a - i ) . (2.6.2) (2.6.4) W e establish this i n P r o p o s i t i o n 2.7.2. W e t h e n verify i n Section 2.8, v i a a restriction-type argument, t h a t i f log - » eo a-2(iogi)(log/c)(loglogfc + l o g - ) , o; a (2.6.5) w i t h a large enough i m p l i c i t constant, then |/2*/.(a:)|>^|B|} {xeB': < a\B'\, i = l , 2 . (2.6.6) It follows t h a t (/*/)(x)>^|S|} {xeB': >(l-4a)|5'|, (2.6.7) provided that b o t h (2.4.3) a n d (2.6.5) h o l d . A somewhat cumbersome calc u l a t i o n shows that eo can be chosen so as to satisfy b o t h (2.4.3) a n d (2.6.5), provided t h a t ^ log^(logloglogA^ + l o g i ) ' ^ ' w h i c h is equivalent t o (2.1.4). W e n o w invoke L e m m a 6.5 i n [35], w h i c h says that if (4a)-i « |r|-i5'Ari/|r|^ (2.6.9) then the set o n the left side of (2.6.7) contains a n a r i t h m e t i c progression of length (16cr)~i = k. P l u g g i n g i n (2.6.2)-(2.6.4) a n d solving for N, we see t h a t (2.6.9) holds i f logA^ > a"^(log''A; + l o g ^ ( - ) - h l o g - l o g l o g f c ) . a a (2.6.10) A n o t h e r cumbersome c a l c u l a t i o n shows t h a t if we assume (2.6.8), then the a d d i t i o n a l c o n d i t i o n (2.1.3) suffices to guarantee that (2.6.10) holds. T h u s , assuming b o t h (2.1.3) a n d (2.1.4), t h e set o n the left side of (2.6.7) contains a fc-term a r i t h m e t i c progression. Since t h a t set is contained in A + A, the conclusion of t h e theorem follows. In the next two sections we complete the proof by verifying the i n e q u a l ities (2.6.1), (2.6.6). 2.7 T h e main term estimate P r o p o s i t i o n 2.7.1. Let B = b + BÇT^ô) Z i v —> R be a function such that supp{f) be a regular Bohr Let f : C B, 0 < f < 1 and E j g / = a > 0. Fix a 6 (0,1] and let d = j F j . Then one of the following (i) There is a S' :^ ^ set. must be true: such that B' = b + BÇT^Ô') is regular and {xeB':if*f){x)>^\B\} >il-a)\B'\, (2.7.1) or (ii) There is a regular Bohr set B" = b" + B(r E{f\B")>a{l where |A| < a - ^ l o g a - ^ and Ô" > U A , ô") such that (2.7.2) + 2-^), ^ r g ^ . Proof: W e essentially follow the argument of Sanders [35]; however, some care must be taken to get the right quantitative version. R e p l a c i n g / by /(• + &) if necessary, we m a y assume that 6 = 0. L e t CQ be a s m a l l enough constant w h i c h w i l l be fixed later. B y [28], L e m m a 8.2, we can find Ô' such that (2.7.3) Ô' e icoa^ôd-\2coa'^ôd-^) and t h a t the set B' defined i n (i) is regular. Suppose that (2.7.1) fails for this choice of Ô'; we have to prove that this implies (ii). T h e failure of (2.7.1) means t h a t we can find a set S C JB' Pi {x : (/ * f){x) < ^\B\} such that |5| = a\B'\. Let g = f - aB be the "balanced f u n c t i o n " of / , W e first c l a i m that l^ij^ + Oidô'ô-'a). * ^(^) ^ {2.7A) T o prove this, we write ' " ' xes xeS XGS T h e first t e r m obeys ^ E ( / . / ) W < 5 f ^ | S l = ^ . by the choice of S. T h e second t e r m is estimated as i n [35]. C o r o l l a r y 3.4, we have for x € B' / * ^ ( ^ ) - / * ^ ( 0 ) <^dô'ô-\ (2.7.5) By [35], B u t / * ^ ( 0 ) = a , so that / * ^(x) in^Wl*\B\ \B'\ - ^ = JW^^ \B' + 0{dô'ô-')) F i n a l l y , we t r i v i a l l y have B * B{x) —|— = a + 0{d5'ô-^) for x G B'. Hence = aa + 0{dô'ô~'a). (2.7.6) < \B\ for a l l x, hence 5 ^ 5 * B{x) < a + 0(d<5'r V ) . (2.7.7) C o m b i n i n g (2.7.5), (2.7.6), (2.7.7), we get (2.7.4). W e now convert this to a F o u r i e r a n a l y t i c statement. W e have Y9*9{x)= E xes xeÎN 9*9{x)S{x) = N'Y1 \9iO\'S{0- (.eZN Hence, b y the triangle inequality, (2.7.4) implies t h a t p i ^ E l ^ ( O l ' l ^ ( O I >%f + 0{dô'5-'a). (2.7.8) Define £:= { e 6 Z ^ : | 5 ( 0 l > ^ ^ } . W e c l a i m t h a t the m a i n c o n t r i b u t i o n to the s u m i n (2.7.8) comes from C In fact I II U^/: I I ^^c aaN aa N aa J2 4|J5| + a^a 4151 ' < a^o \f{x)-aB{x) |2 2 ' X&N 2a^a - 4 4 aa 2N = ^ ( a - a ) a'^a 1 a^a 4 < Hence "'7TEl»«)l'l^«)l>4^ + Since 0(<H'i-'). 1 5 ( 0 1 is t r i v i a l l y bounded by a, we have Y,\9{0\'>^ + 0idô'ô~'a). (2.7.9) 1^1 W e now a p p l y the localized version of C h a n g ' s theorem proved i n [35] ( P r o p o s i t i o n 4.2) to S C B', w i t h e = a / 4 and r/ = 1/2. W e conclude that there is a set A C Zjv and a SQ > 0 such t h a t |A| < 24 ^loga-\ a2 (?^a^4 d2 l o g ( j - i ' and £ C {Ç € Z;v : |1 - e-^'^^^^/^l < 1/2 V x G B{T U A , 5'^)}. Choose 6" G (5o,25()') such that B" is regular. N o t e that := B{TuA,ô") this together w i t h (2.7.3) implies t h a t 5" obeys the c o n d i t i o n i n (ii). m a y also assume that Ô" < 6'. O u r goal is to get the We density increment as i n (2.7.2) on a translate of B " . B y the definition of C, we have J§T^\B''{^)\ > 1/2 for a l l ^ € £ . Hence A g a i n using Plancherel's identity a n d the convolution identity we have a^(i+o(a-^rf5'ri)) < '16 ^ - \B\\B'' Y \m\'mo\' iV3 W e now a p p l y L e m m a 5.2 from [35] a n d conclude t h a t sup 1/ * B"ix)\ > a{l + 2-4 + 0 ( a - 2 d 5 ' r i ) ) - >a(l + 2-4) + 0 ( d a - M ' J - i ) . W e now let the constant CQ i n (2.7.3) be s m a l l enough, so that the error t e r m is b o u n d e d by a2'~^. T h e conclusion (ii) follows if we choose b" to m a x i m i z e 1/ * B"{b")\. T h i s proves P r o p o s i t i o n 2.7.1. P r o p o s i t i o n 2.7.2. Let / : ZAT -> [0,1] be defined such that ]Exez^/(x) = Let a G (0,1]. Then there exist Bohr b + B(T,Ô') such that {xEB': Q>0. sets B := b + B{r,ô) (/*/)(x)>^|5|}|>(l-a)|5'|. and B' := and Mog(a and \T\ « a - 2 l o g ( a - i ) . Proof of Proposition 2.7.2: W e construct the B o h r sets B a n d B' by i t e r a t i n g P r o p o s i t i o n 2.7.1. L e t PQ := {0}, a n d pick (5o 1 so that BÇTOTSQ) is regular. Define ao := a . A v e r a g i n g over translates of B(ro,ôo), we see t h a t there is a bo such that E{f\Bo) > ao for Bo = bo + B{To,ôo). By P r o p o s i t i o n 2.7.1, one of the following must h o l d : (i) T h e r e is a (5Q » such that BQ := bo + B{TQ, Ô'Q) is regular a n d ^0 {xeB'o-.if* > ^\Bo\}\ > (1 - a)\B'o\, f){x) (2.7.10) (ii) T h e r e is a regular B o h r set Bi := bi + B{To U A o , ôi) such that E ( / | 5 i ) > a o ( l + 2-^), where |ro| < aô^\og{o-') a n d 6i » (2.7.11) jf^^^^y If (i) holds, we let B' — BQ a n d we are done. If o n the other h a n d (ii) holds, we repeat the procedure w i t h BQ replaced b y Bi, a n d continue b y i n d u c t i o n . If we have not satisfied (i) b y t h e e n d of the kth step, we have found a regular B o h r set B^ := bk + B{Tk, ok) such t h a t Eif\Bk) = ak\Bk\, where «fc>«fe-i(l + 2-'), 4 » ,p i s f ' ; ' IV (2.7.12) (2.7.13) |rfc_iPlog(cr 1) and iFfcl - IPfc-il « afc_i l o g ( a - i ) . (2.7.14) T h e i t e r a t i o n must t e r m i n a t e (upon reaching density 1 on a large enough B o h r set) after at most k < log(a~^) steps, since from (2.7.12) we liave B y (2.7.14) we have iFfcl < «fc^i l o g ( a - l ) + a^^2 l o g ( a - i ) + • • • + a^^ < a'^ l o g ( a - i ) 5^(1 j=o ^ogia'^) + 2-^)-^' < a - 2 l o g ( a - i ) . F i n a l l y , using our bounds for ak a n d IF^I, we have Mog(<7-i)^ for some absolute constant C > 0. T h i s proves P r o p o s i t i o n 2.7.2. 2.8 The restriction argument A s s u m e that the hypotheses of T h e o r e m 2.1.4 h o l d . W e need to show that if h, J2 are as i n L e m m a 2.2.5 a n d B' are the B o h r sets chosen i n P r o p o - sition 2.7.2, t h e n (2.6.6) holds, i.e. {xEB': |/2*/,(x)|>^|i?|} <a\B'li = 1,2. (2.8.15) It suffices to prove that or \\fi*h\\UB')<^<y\B?\B'\. 200 (2.8.16) W e have xeB' y z x,y,z,u,v Ç V = N'^(B^ i *fM-0fi(0f2{0• B y H o l d e r ' s inequality, ||/^ * /2|li2(s,) < iV^IIB^ * 7/2II10 ||7J2||io/9- (2.8.17) A p p l y i n g Y o u n g ' s inequality, we get (2.8.18) ||P^*7i/2||lO<||B^||5||7i/2||lO/9. Furthermore, l l 7 7 2 i i ; s ; 9 < i i 7 2 i i ^ ^ E 1/2(01 i 7 ( 0 P " / ' <ll72||^'ll72||l9/9ll7(e)li;9^9, where at the last step we used H o l d e r ' s inequality again. P l u g g i n g this together w i t h (2.8.18) i n (2.8.17), we see t h a t ||/i*/2|li2(B')<^'m5ll772||?o/9 <A^3||S^||5(||72|lL/'||72||l9/9ll7li;S;9)'^' <A^'ll^ll5||72||^'ll72|i;g9 ll7ll?9/9- B y P l a n c h e r e l ' s theorem a n d L e m m a 2.2.5(iv), we have AII2 < l l / l l i = N-'Wfg « ap-' = aN'. Since 0 < 1/20, i t follows from L e m m a 2,2.6 that II/II19/9 = 0 ( 1 ) a n d ||7i||i9/9 = 0 ( 1 ) , z = 1,2. B y L e m m a 2.2.5(iii), we have II/2II0C < Ceo. Finally, P ' l l5i <: iP ' l l lloo Ll| 5 ' 1l12l ^ ' < -^-^yl-II-S'il2 ^ll^'llo = = -^^l"' 11-^ C o m b i n i n g these estimates, we get W e need t h e right side of this to be smaller t h a n ^cr|i?|2|i?'|, i.e. we need to have • e f < caV^i^D^ = ca'aF{B)MB'Y^'. (2.8.20) B u t b y L e m m a 2.2.3 a n d (2.6.2)^(2.6.4), F{B) a n d F{B') are b o u n d e d from below b y F{B) > F(B') » ic6"p » (-^) \V log loefc fc// ca ^ log - log k where we plugged i n cr = (16fc)-^ Hence (2.8.20) holds if 98, 0 / CQ log i log fc A short c a l c u l a t i o n shows t h a t (2.6.5) is sufficient to guarantee t h a t (2.8.21) is satisfied. 2.9 Proof of Proposition 2.1.3 L e t 0 < (T < ( a - /3)/10. Define i^,f,f\,f2 instead of (2.4.1) we w i l l require as i n Section 2.6, except t h a t ll/i||oo<l + a, (2.9.1) w h i c h holds for large enough A'' (depending o n a a n d o n the eo i n the defin i t i o n of fi) by the same argument as i n Section 2.4. It clearly suffices to prove t h a t {XEZN •• / * fix) > 0} > (Q - lQa)N. (2.9.2) Indeed, (2.9.2) shows t h a t the sumset A + A in ZN has size at least hence so does the sumset A + A inZ. W e first c l a i m t h a t if N is large enough, t h e n {x € ZN : fi * / i ( x ) > aaN] > ( a - 3a)iV. (2.9.3) T o see this, we first note t h a t l l / i * M i l = ll/ill? = « ' ^ ' ( 1 +o(iv-'/'))- (2.9.4) O n the other h a n d , i f (2.9.3) failed, we w o u l d have l l / i * / i 111 < cyc^N • N + a A ^ ( l + a + 0{N-'^'^)) • {a - 3a)N = a^N^l + 0{N-^^^)) - aaN^, w h i c h contradicts (2.9.4). T h i s proves (2.9.3). T h e proof of (2.9.2) w i l l be complete if we c a n show t h a t {x€Zjv:|/i*/2(x)|>—iV} < aN. (2.9.5) T o this e n d , we repeat the argument i n Section 2.8. It suffices t o prove t h a t l|/^*/2||i< 200 aN^. (2.9.6) A s i n Section 2.8 ( w i t h B ^ B' = ZN), we have ll/i*/2||i«4^'A^', (2.9.7) and the right side is smaller t h a n the right side of (2.9.6) if eo <§C a'^'^a^^, w i t h a s m a l l enough i m p l i c i t constant. T h u s (2.9.5) holds for large enough A'' if eo was chosen s m a l l enough. T h i s proves P r o p o s i t i o n 2.1.3 2.10 The Acknowledgements authors were s u p p o r t e d i n part by a n N S E R C Discovery G r a n t . We are grateful to B e n G r e e n for suggesting the feasibihty of T h e o r e m 2.1.2, and to E r n i e C r o o t a n d M i h a l i s K o l o u n t z a k i s for helpful discussions a n d suggestions. Bibliography [18] J . B o u r g a i n , On arithmetic progressions in sums of sets of integers, i n A tribute to Paul Erdos, p p . 105-109, C a m b r i d g e U n i v e r s i t y Press, 1990. [19] J . B o u r g a i n , On triples in arithmetic progressions, 9 (1999), 968-984. [20] M . - C . C h a n g , A polynomial J . 113 (2002), 399-419. bound in Freiman's Geom. Punct. A n a l . theorem, D u k e M a t h . [21] E . C r o o t , I . R u z s a , T . Schoen, Long arithmetic progressions in sparse sumsets, Integers: T h e E l e c t r o n i c J o u r n a l of C o m b i n a t o r i a l N u m b e r Theory, 7(2) (2007), # A 1 0 . [22] W . T . Gowers, A new proof of Szemerédi's 11 (2001), 465-588. [23] B . J . G r e e n , Arithmetic (2002), 584-597. progressions theorem, G e o m . F u n c t . A n a l . in sumsets, G e o m . F u n c t . A n a l . 12 [24] B . J . G r e e n , On arithmetic structures M a t h . J o u r . , 114 (2002), 215-238. in dense sets of integers, Duke [25] B . J . G r e e n , Roth's Theorem in the primes. A n n a l s of M a t h . 161 (2005), 1609-1636. [26] B . J . G r e e n , T . T a o , The primes contain arbitrarily gressions. A n n a l s of M a t h . , to appear. long arithmetic pro- [27] B . J . G r e e n , T . T a o , Restriction theory of the Selberg Sieve, with applications. J o u r n a l de Théorie des N o m b e r s de B o r d e a u x , 18 (2006), 137-172. [28] B . J . G r e e n , T . T a o , An inverse theorem for the Gowers U^{G) P r o c . E d i n b u r g h M a t h . S o c , to appear. norm, [29] Y . K o h a y a k a w a , T . L u c z a k , V . Rôdl, Arithmetic progressions of length three in subsets of a random set, A c t a A r i t h . 75 (1996), 133-163. [30] M . B . N a t h a n s o n , Additive Springer, N e w Y o r k , 1996. Number Theory: The Classical Bases, [31] J . P i n t z , W . L . Steiger, E . Szemerédi, On sets of natural numbers whose difference set contains no squares, J . L o n d o n M a t h . Soc. 37 (1988), 219-231. [32] K . R o t h , On certain sets of integers, J . L o n d o n M a t h . Soc. 28 (1953), 245-252. [33] L R u z s a , Difference sets without squares. P e r i o d . M a t h . H u n g a r . 15 (1984), no. 3, 205-209. [34] I. R u z s a , Arithmetic 191-202. progressions [35] T . Sanders, Additive structures C a m b r i d g e P h i l o s . Soc. A c t a A r i t h . 60 (1991), in sumsets. in sumsets, to appear i n M a t h . P r o c . [36] E . Szemerédi, On sets of integers containing no four elements in arith- metic progression. A c t a M a t h . A c a d . S c i . H u n g a r . 20 (1969), 89-104. [37] E . Szemerédi, On sets of integers containing no k elements in arithmetic progression, A c t a A r i t h . 27 (1975), 299-345. [38] T . T a o , Arithmetic progressions V o l . E x t r a , 37-88. [39] T . T a o , V . V u , Additive and the primes, combinatorics, Collect. M a t h . (2006), C a m b r i d g e U n i v . Press, 2006. [40] P . V a r n a v i d e s , On certain sets of positive M a t h . S o c , 34 (1959), 358-360 density. DEPARTMENT OF BRITISH VANCOUVER, mehameWmath. OF MATHEMATICS, B.C. V6T 1Z2, UNIVERSITY CANADA ubc. ca, ilaba@math. ubc. ca Journal London COLUMBIA, Chapter 3 Conclusion 3.1 A potential application to primes O n e a p p l i c a t i o n of the methods used i n this paper involves t r a n s l a t i n g results from the r a n d o m setting into t h a t of the primes. A theorem of G r e e n [47] states t h a t if is a subset of the primes w i t h positive relative density, then A must c o n t a i n three terms i n a r i t h m e t i c progression. T h e strategy developed by G r e e n i n [47] is essentially to exploit certain ' r a n d o m ' properties of the primes (in a Fourier a n a l y t i c sense). O n e of the first hurdles to overcome is t h a t the primes aren't a c t u a l l y r a n d o m . F o r example, the set of primes isn't r a n d o m l y d i s t r i b u t e d m o d u l o a s m a l l prime. To deal w i t h this, one employs what is t o d a y referred to as the W — trick (a nice e x p l a n a t i o n of this can be found i n [49]). T h i s entails defining a number m w h i c h is the product of s m a l l primes. T h e next step is to consider the residue classes m o d u l o m. T h e set of primes contained i n a given residue class w i l l then behave i n a satisfactorily r a n d o m manner. T h e proof t h e n restricts itself to the p o r t i o n of the set A w h i c h falls i n one p a r t i c u l a r residue class (pick the residue class o n w h i c h A has largest relative density). W o r k i n g w i t h this chosen p o r t i o n of A one applies R o t h ' s theorem i n a manner similar to the a p p l i c a t i o n of Sârkôzy's theorem i n the proof of T h e o r e m 2.1.2. W i t h o u t p r o v i d i n g details, we note t h a t the appropriate choice for J / is a modified version of the von M a n g o l d t f u n c t i o n s u p p o r t e d o n the chosen residue class. C o m b i n i n g the results from the manuscript [51] contained i n this dissertation, a n d the framework for the primes of G r e e n [47] or G r e e n and T a o [49] we can prove a version of Sârkôzy's theorem i n the primes (and a s i m i l a r extension for long a r i t h m e t i c progressions i n sumsets). Specifically, it is possible to show t h a t if A is a subset of the primes w i t h positive relative density, then A must contain a square difference. However, we should m e n t i o n , that i n the case of Sârkôzy's theorem such a variation holds i n the primes for density reasons alone. P i n t z , Steiger a n d Szemerédi [55] show t h a t if a subset A C {1, .•.,N} contains no square difference, the \A\/N < (log A ^ ) - c l o g log log log iv_ P Q J . comparison, the p r i m e number theor e m states t h a t the number of primes less t h a n an integer A'^ is asymptotic to N/ log A^. I n joint work w i t h K a r s t e n C h i p e n i u k , we are a t t e m p t i n g to prove a n analogue of T h e o r e m 2.1.3 i n t h e setting of t h e primes. W e begin w i t h a m o t i v a t i n g example. L e t P be t h e set of a l l primes a n d define A := {p € P : p = 1 m o d n} a n d consider AAT •= {p & A : p < N}. T h e n , the p r i m e number theorem for a r i t h m e t i c progressions gives us q u a n t i t a t i v e i n f o r m a t i o n o n the size of A j y . N a m e l y , we have Set 6 :— T h e n , assuming N is sufficiently large, we have \AN\ » S-^^jj. O n t h e other h a n d . A N + A N C { m = 2 m o d n } a n d hence, \AN + A N \ < ~ ^ ^ N. log log n n T h e previous example leads us to the following question: Q u e s t i o n 3.1.1. Suppose A cP h m sup N->oo where PN •= {p < N : p EP}. IAN + such that — —— = 5 \PN\ IS it true that ANI^T—T^J^-N? log log(1/5) T h e question above differs from other applications i n t h e primes since for a density result, we are not able to consider only one residue class m o d u l o m. If p is a p r i m e number, then the residue class i n w h i c h p lies must be contained i n the m u l t i p l i c a t i v e subgroup Zj|^ c Z m - W h i l e we are able to a p p l y a modified version of the convolution l e m m a from [51] to a given residue class o n w h i c h a subset of the primes has large enough relative density, we must also ensure that the sumset determined b y these residue classes covers enough of Z j „ . I n p a r t i c u l a r we must answer t h e following question: Q u e s t i o n 3.1.2. Suppose 5 C Z ^ such that \S\ > ôc/){m). Is it then true W e i n t e n d to answer these questions i n an u p c o m i n g paper. 3.2 A n improvement to Theorem 2.1.2 R e c a l l that i n the statement of T h e o r e m 2.1.2 we define the r a n d o m set W CZM w i t h each element chosen w i t h p r o b a b i l i t y p(A'') e {cN~^, 1] where we require 0 < ^ < 1/110. A s we noted i n Section 2.1, while we expect that the range should be extended to a l l ^ < 1/2 the methods of our paper do not seem sufficient to establish such a result. I n a work [54] that is currently i n p r e p a r a t i o n , H . N g u y e n a n d V . V u have proved: T h e o r e m 3.2.1. Suppose that W is a random subset of such that the events x € W, where x ranges overZ^, are independent and have probability p = p{N) e icN~^, 1] where 0 < 6» < 1/2. Leta>0. Then the statement for every set A C W with \A\ > aW, there are x,y that x — y is a non-zero perfect square is true with probability € A such 1 — O Q ( 1) as A ' —> oo. T h e y are also able to prove similar results for fc-th powers w i t h the 6 < 1/2 replaced by 9 < 1/fc. T h e i r proof uses methods from g r a p h theory relating to the cited work of K o h a y a k a w a , L u c z a k , a n d R o d l a n d i n p a r t i c u l a r they use Szemerédi's regularity l e m m a . 3.3 Future directions A famous result of Bergelson and L e i b m a n [42] is a p o l y n o m i a l version of Szemerédi's theorem. T h e o r e m 3.3.1. B e r g e l s o n - L e i b m a n Let 6 > 0 and let P i , b e polynomials in Z[d] such that Pj(0) = 0 for every i = 1, ...,fc. Suppose that N is sufficiently large depending on 5 and P i , ...,Pfc. Then, there exist integers m and d so that m Pi{d) E A for all i = 1,fc. Bergelson a n d L e i b m a n ' s proof uses ergodic theory a n d is currently the o n l y k n o w n proof of a p o l y n o m i a l version of Szemerédi's theorem. Recently, Tao a n d Ziegler [59] proved that the primes c o n t a i n a r b i t r a r i l y long p o l y n o m i a l progressions, r e l y i n g on a certain q u a n t i t a t i v e version of T h e o r e m 3.3.1. T h e i r proof, s i m i l a r l y to the proof of the G r e e n - T a o theorem on primes in a r i t h m e t i c progression, can be d i v i d e d into three m a i n steps: a p o l y n o m i a l version of Szemerédi's theorem, a transference p r i n c i p l e a n d a m e t h o d to treat the primes as ' r a n d o m ' . W e should note that despite the similarities i n tiie o u t l i n e , tlie p o l y n o m i a l version requires several arguments w h i c h are not needed i n t h e case of finding a r i t h m e t i c progressions i n the primes. T h e r e have been certain results using Fourier analysis r e l a t i n g to the p o l y n o m i a l version of Szemerédi's theorem. O n e reason t h a t this is of interest is t h a t the ergodic proof, r e l y i n g o n the a x i o m of choice, does not provide any i n f o r m a t i o n o n when the first occurrence of a given p o l y n o m i a l p a t t e r n must occur i n a subset of positive upper density. T h e first q u a n t i t a t i v e result i n t h i s d i r e c t i o n is due to G r e e n [46]: T h e o r e m 3.3.2. Suppose that A C {1,..., A ' } so that\A\/N Then there exists x, x + y,x + 2yEA > (log log A f ) - ^ such that y = a'^ + b'^. H i s proof requires q u a d r a t i c F o u r i e r analysis. W e notice, t h a t using these methods. G r e e n is able to deduce q u a n t i t a t i v e bounds o n the required density for a subset of the integers to contain this p a r t i c u l a r a r i t h m e t i c progression. Since G r e e n ' s current b o u n d is not sufficient for h a n d h n g subsets of t h e primes, we believe t h a t i t w o u l d be of interest to consider this p r o b l e m i n t h e r a n d o m setting. W e expect t h a t the m e t h o d of G r e e n - T a o for h a n d i n g f o u r - t e r m a r i t h m e t i c progressions i n the primes should provide the necessary framework for such a n a p p l i c a t i o n . M o r e specifically, i f we assume t h a t W is a r a n d o m subset of ZAT a n d A C W has positive relative density t h e n we w o u l d Hke t o construct / a n d u as i n Section 2.2. F o r such a n a r gument, we expect t h a t i t w o u l d be necessary to replace the pseudorandom c o n d i t i o n ||?(0 ~ lç=o||oo < V w i t h an appropriate q u a d r a t i c c o n d i t i o n . A result of L y a l l a n d M a g y a r [53] c a n be seen as a special case of the p o l y n o m i a l version of Szemerédi's theorem or as a generalization of S a r k o z y ' s theorem. Theorem polynomials 3.3.3. Assume independent so that Pi{0) = 0 for each i = I, .-.,1 and assume the largest degree of the polynomials \A\/N 6 Z[d] are linearly that Pi,...,Pi Pi is k. > ((loglogAr)2/logAf)^'''^^'"^\ that Pi{d) Ci A - A for every i = Suppose that A C {!,..., A ' } so that Then there exists an integer d such 1,k. T h e i r proof is Fourier a n a l y t i c a n d again provides q u a n t i t a t i v e bounds t h a t t h e ergodic proof does n o t . W e expect that using s i m i l a r methods to those i n t h i s m a n u s c r i p t we could extend T h e o r e m 3.3.3 to subsets of r a n d o m sets. W e should remark t h a t L y a l l a n d M a g y a r are o p t i m i s t i c t h a t c o m b i n i n g their proof w i t h t h e methods of P i n t z , Steiger a n d Szemerédi w o u l d result i n a s i m i l a r b o u n d to t h a t k n o w n for S a r k o z y ' s theorem. T h i s m e t h o d w o u l d have the advantage of i n c l u d i n g a l l sets of such density, rather t h a n subsets of r a n d o m sets or subsets of the primes. F i n a l l y , we believe t h a t it w o u l d be of interest to find a Fourier a n a l y t i c proof of the following special case of the B e r g e l s o n - L e i b m a n theorem w h i c h can be compared w i t h b o t h T h e o r e m 3.3.2 a n d T h e o r e m 3.3.3: T h e o r e m 3.3.4. Suppose that ô > 0 and assume A is a subset of the integers with positive upper density. Then there must exist integers x and y such that X, X + y'^, x + y^ e A. W e expect t h a t such a result w o u l d require q u a d r a t i c Fourier analysis, w h i c h w o u l d enable us to determine a b o u n d on how soon we could find three elements of the form x, x + y'^ and x + y^ i n A. If we are t h e n able to extend t h i s to show t h a t , i n fact, A must contain ' m a n y ' triples of the desired form, then we w o u l d hope to be able to prove a version of T h e o r e m 3.3.4 i n the r a n d o m setting or i n the primes. Such a result w o u l d provide new q u a n t i t a t i v e i n f o r m a t i o n for a special case of the T h e o r e m of Tao-Ziegler on p o l y n o m i a l progressions i n the primes. Bibliography [41] F . B e h r e n d , On the sets of integers arithmetic progression. which contain no three terms in P r o c . N a t . A c a d . S c i . , 23:331-332, 1946. [42] V . Bergelson a n d A . L e i b m a n , Polynomial extensions of van der Waerden's and Szemerédi's theorems, J . A m e r . M a t h . Soc. 9 (1996), no. 3, 725-753. [43] J . B o u r g a i n , On triples in arithmetic 9 (1999), 968-984. progressions, Geom. Funct. A n a l . [44] G . A . F r e i m a n , Foundation of a structural theory of set addition (translated from Russian), T r a n s l a t i o n s of M a t h e m a t i c a l M o n o g r a p h s , 37, 1973. [45] T . Gowers, A new proof of Szemerédi's 12:465-588, 2001. [46] B . J . G r e e n , On arithmetic structures M a t h . J o u r . , 114 (2002), 215-238. theorem, G e o m . F u n c t . A n a l , in dense sets of integers, Duke [47] B . J . G r e e n , Roth's Theorem in the primes, A n n a l s of M a t h . 161 (2005), 1609-1636. [48] B . J . G r e e n , T . T a o , The primes contain arbitrarily gressions. A n n a l s of M a t h . , to appear. long arithmetic pro- [49] B . J . G r e e n , T . T a o , Restriction theory of the Selberg Sieve, with applications, J o u r n a l de Théorie des N o m b e r s de B o r d e a u x , 18 (2006), 137-172. [50] B . J . G r e e n , T . T a o , An inverse theorem for the Gowers U^{G) P r o c . E d i n b u r g h M a t h . S o c , to appear. norm, [51] M . H a m e l a n d L L a b a , Arithmetic structures in random sets, I N T E G E R S : E l e c t r o n i c J o u r n a l of C o m b i n a t o r i a l N u m b e r T h e o r y , 8, 2008. [52] Y . K o h a y a k a w a , T . L u c z a k , V . R o d l , Arithmetic progressions of length three in subsets of a random set, A c t a A r i t h . 75 (1996), 133-163. [53] N . L y a l l a n d A . M a g y a r , Polynomial preprint. configurations in difference sets, [54] H . N g u y e n a n d V . V u , i n preparation. [55] J . P i n t z , W . L . Steiger, E . Szemerédi, On sets of natural difference set contains numbers whose no squares, J . L o n d o n M a t h . Soc. 37 (1988), 219-231. [56] K . R o t h , On certain sets of integers, J . L o n d o n M a t h . Soc. 28 (1953), 245-252. [57] T . Sanders, Additive structures C a m b r i d g e P h i l o s . Soc. [58] A . Sarkozy, On difference in sumsets, to appear i n M a t h . P r o c . sets of integers I, A c t a M a t h . A c a d . S c i . H u n g a r , 31:125-149, 1978. [59] T . T a o a n d T . Ziegler, The primes progressions, contain arbitrarily long polynomial to appear i n A c t a . M a t h . [60] T . T a o , V . V u , Additive [61] P . V a r n a v i d e s , combinatorics, On certain C a m b r i d g e U n i v . Press, 2006. sets of positive density, Journal London M a t h . S o c , 34 (1959), 358-360 DEPARTMENT VANCOUVER, OF MATHEMATICS, B.C. V6T mehamel@math. ubc. ca 1Z2, UNIVERSITY CANADA OF BRITISH COLUMBIA,
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Arithmetic structures in random sets
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Arithmetic structures in random sets Hamel, Mariah 2008
pdf
Page Metadata
Item Metadata
Title | Arithmetic structures in random sets |
Creator |
Hamel, Mariah |
Publisher | University of British Columbia |
Date Issued | 2008 |
Description | We prove various results in additive combinatorics for subsets of random sets. In particular we extend Sarkozy's theorem and a theorem of Green on long arithmetic progressions in sumsets to dense subsets of random sets with asymptotic density 0. Our proofs require a transference argument due to Green and Green-Tao which enables us to apply known results for sets of positive upper density to subsets of random sets which have positive relative density. We also prove a density result which states that if a subset of a random set has positive relative density, then the sumset of the subset must have positive upper density in the integers. |
Extent | 2205235 bytes |
Subject |
Additive combinatorics |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2008-12-04 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0066823 |
URI | http://hdl.handle.net/2429/2838 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2008-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2008_fall_hamel_mariah.pdf [ 2.1MB ]
- Metadata
- JSON: 24-1.0066823.json
- JSON-LD: 24-1.0066823-ld.json
- RDF/XML (Pretty): 24-1.0066823-rdf.xml
- RDF/JSON: 24-1.0066823-rdf.json
- Turtle: 24-1.0066823-turtle.txt
- N-Triples: 24-1.0066823-rdf-ntriples.txt
- Original Record: 24-1.0066823-source.json
- Full Text
- 24-1.0066823-fulltext.txt
- Citation
- 24-1.0066823.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.24.1-0066823/manifest