Arithmetic Structures in Random Sets by Mariah Hamel B..A., Colby College, 2002 M.Sc., The University of Brit ish Columbia, 2004 A T H E S I S 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 R E Q U I R E M E N T S F O R T H E D E G R E E O F Doctor of Philosophy m The Faculty of Graduate Studies (Mathematics) The University of Brit ish Columbia June 2008 © Mariah Hamel 2008 Abstract We prove various results in additive combinatorics for subsets of random sets. In part icular we extend Sarkozy's theorem and a theorem of Green on long ar i thmetic progressions in sumsets to dense subsets of random sets w i t h asymptotic density 0. O u r 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 i n the integers. Table of Contents Abstract i i Table of Contents i i i Acknowledgements v Dedicat ion v i Statement of C o - A u t h o r s h i p v i i 1 Introduction 1 1.1 His tory 1 1.1.1 Statement of m a i n results 3 1.2 Prel iminaries and Notat i on 5 1.3 B o h r Sets 6 1.3.1 A localized version of Chang's theorem 8 1.4 A proof of Sârkôzy's Theorem 10 1.5 T h e transference principle and pseudorandom sets 14 Bibl iography 18 2 A r i t h m e t i c structures in random sets 20 2.1 Introduct ion 20 2.2 Pre l iminaries 24 2.3 A Varnavides-type theorem for square differences 27 2.4 Proo f of Theorem 2.1.2 29 2.5 Power differences 31 2.6 L o n g arithmetic progressions i n sumsets 32 2.7 T h e main term estimate 33 2.8 T h e restriction argument 39 2.9 Proo f of Propos i t ion 2.1.3 41 2.10 Acknowledgements 42 Bibl iography 43 3 Conclusion 45 3.1 A potent ia l application to primes 45 3.2 A n improvement to Theorem 2.1.2 47 3.3 Future directions 47 Bibl iography 50 Acknowledgements I want to thank my advisor Izabella L a b a for her continued support and guid - ance throughout my graduate work. I am especially thankful for our many meetings filled w i t h mathematical insight, encouragement and thoughtful advice. I would like to thank Jozsef Solymosi , D a v i d B o y d and M a l a b i k a P r a - manik for many useful discussions and for offering such an interesting array of graduate courses. I am grateful to D a v i d Brydges for always being so k i n d and for always inquir ing about my progress as a graduate student. I would like to thank Greg M a r t i n and Stephen K w o k - K w o n g C h o i for being members of m y examining committee and for thoughtful suggestions for this thesis. I have enjoyed discussions w i t h many of my fellow graduate students inc luding K a r s t e n Chipeniuk , Chr i s Coulter , Chr i s Duarte , Zha i K e l a n and Terry Soo. I am deeply grateful to have begun studying mathematics under the supervision of B e n Mathes , Leo L ivsh i t s and Fernando Gouvêa at Co lby College. I w i l l forever remember their encouragenient and their love of mathematics . I am indepted to my parents, E d and M a r y Hamel , for having supported me throughout my education. F ina l ly , I would like to thank M a t h e w Rogers for his support, encour- agement and love. Dedication For C a r i n a statement of Co-Authorship The manuscript which is contained in this thesis is joint work with Iz- abella Laba. It was suggested to us that Theorem 2.1.2 was feasible Ben Green. The statement of Theorem 2.1.4 was first considered by Laba. The manuscript was researched and jointly written by Mariah Hamel and Izabella Laba. Chapter 1 Introduction 1.1 History A d d i t i v e combinatorics can be described as a study of the structural prop- erties of sets of integers, or more generally, additive groups. W h i l e this area has long been of interest to mathematicians, over the past few years there has been an abundance of col laboration between those who study number theory, harmonic analysis, combinatorics and ergodic theory. In this intro- duct ion we w i l l provide motivat ion to the work included below through a discussion of the history of additive combinatorics as well as some (difficult) conjectures which remain open. One of the first results i n the subject which is today called additive combinatorics is a coloring result due to van der Waerden proved in 1927. He was able to show that given integers r and k, if the set of integers is colored by r colors, then there must be k integers i n arithmetic progression which are monochromatic . A related result, due to Schur states that if the integers are r-colored, then there must be x, y and z, monochromatic , such that X + y — z. B o t h of these problems fal l into the category of Ramsey theory which is concerned w i t h extremal results. We can rephrase them as follows: Suppose { 1 , n ] is colored w i t h r colors. How large must n be (as a function of r) to guarantee the desired monochromatic structure? In 1936 Erdos and Turan formulated the following conjecture: Conjecture 1.1.1. Suppose ^ C N such that > - = oo. aeA Then A must contain arithmetic progressions of arbitrary length. We remark that this can be seen as an extension of the theorem of van der Waerden since if we color the integers w i t h f initely many 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 odd integers also satisfies the hypothesis of the Conjec- ture but there are no three odd numbers which satisfy x + y = z. W h i l e Conjecture 1.1.1 remains open, there have been many interesting results i n that direction. We say that a subset A of the integers has positive upper density if | ^ n { l , . . . , n } | „ l i m s u p J ^ ' ' > 0. In 1953, R o t h [13] proved that any subset of the integers w i t h positive upper density must contain arithmetic progressions of length three. A few years later, bu i ld ing on Roth ' s result, Varnavides [17] showed that , in fact, such a subset must contain many three-term arithmetic 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 Roth ' s theorem to that of Sarkozy's theorem on square differences included i n Section 1.4. S imi lar ly the extension of Sarkozy's theorem contained in Chapter 2 follows Varnavides ' original argument. In 1975, Szemerédi extended Roth ' s theorem for arithmetic progressions of arb i t rary 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 and let Ô > 0. Then there exists N = N{k,ô), such that every subset A of {1,...,N} such that \A\ > SN must contain an arithmetic progression of 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 problem w i t h a proof that can be seen as a generalization of Roth ' s or iginal argument for three term arithmetic progressions. M a n y of the ideas developed by Gowers were used by Green and Tao [8] i n proving that the primes contain arithmetic progressions of arb i trary length. Inverse problems form another important topic in additive number the- ory. Suppose that A c { 1 , A ' ' } . Freiman's theorem [3] states that if the size of the sumset A + A ~ {ai + a2 : a i , a2 £ A} is small (relative to the size of A) then A itself must be very structured. To state Freiman's theorem precisely, we require a the following definition: Definit ion 1.1.3. Suppose that XQ, xi, ...,Xd are integers and mi,m2, are positive integers. A generalized arithmetic progression of dimension d is defined d P := {xo + XjXj : 0 < Aj < ruj - 1}. i=l If the size of the progression is equal to the product of the ruis, we say that P is proper. A n i l lustrat ive example of a generalized ar i thmetic progression is defined by the set P := 6 + {0, 3,6,9} + {0,100,200,300}. Preiman'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 l o g ( | P | / | A | ) « C 2 ( l o g C ) 3 . Despite many works on the above subjects there remain many open problems. E v e n the case of three term arithmetic progressions has not been satisfactorily solved. In terms of an upper bound, the best known result is due to Bourga in [2] i n which he shows a set of density ô » (̂°(fg )̂2/3 (assum- ing N is sufficiently large) must contain three term arithmetic progressions. O n the other hand, the best lower bound due to Behrend [1] shows that there exists a subset o f { l , A ' ' } of size A'' viogAr TîSgW which contains no three term ar i thmetic progressions. In the case of R o t h ' s theorem, there have been some interesting results for sets which do not satisfy Bourgain 's bounds. In 1996, Kohayakawa, Luczak and R o d l [12] proved a version of Roth ' s theorem for sets of asymp- totic density zero which satisfy the addit ional hypothesis of positive relative density in a random set which has density zero in the integers. In 2002, Green [7] proved a version of Roth ' s theorem for sets which have positive upper density i n the primes. 1.1.1 S t a t e m e n t of m a i n results The purpose of this section is to state the m a i n results contained i n this thesis. Theorems 1.1.5 and 1.1.6 are contained i n Chapter 2 and can be found as Theorem 2.1.2 and Theorem 2.1.4 respectively. T h e proof of Theorem 1.1.5 can be found i n Section 2.4. T h e proof of Theorem 2.1.4 can be found i n Sections 2.6, 2.7 and 2.8. T h e purpose of the remainder of this chapter is to provide an introduct ion to the ideas used in Chapter 2 and to f i l l i n certain details that were omitted from [11]. In 1978 Sârkôzy [15] proved a variant on Roth ' s theorem showing that subsets of positive upper density must contain two elements whose diflFer- ence is a perfect square. T h e same result was proved independently by Furstenberg ([4]) using ergodic theory around the same t ime. In 1988, P i n t z , Steiger and Szemerédi, using a combination of Fourier analytic and combi- nator ia l arguments, showed that any subset of {1,...,A'^} of size at least (logA^)-^'°g'°g'°g^°g^Ar must contain a square difference. O n the other hand, a construction of Ruzsa shows that there exists a set of size iv^^°-^^^ which contains no square difference. It is conjectured that for any e > 0, and A'̂ sufficiently large (depending on e), there exists a set of size A''^~^ which contains no square difference. In a joint paper w i t h Izabella L a b a we prove the following variant of Sarkozy '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 Zjv, are independent and have probability p = p{N) G {cN-^, 1] where 0<9 < 1/110. Let a > 0. Then the statement for every set A C W 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 known that the sumset A + A = {ai + a2 • ai,a2 G A} contains 'more' additive structure than the original set. T h e case when ^ is a subset of positive upper density has been studied by Bourga in , Ruzsa , Green and Sanders. For a more detailed discussion of the history of this problem we direct the reader to the introduct ion of [11] included below. We prove the following analogue for subsets of random sets. T h e o r e m 1.1.6. Suppose that W is a random subset of such that the events x G W, where x ranges over Z^r, are independent and have probability p = p(N) e {CN~^, 1], where 0 <$ < 1/140. Assume that a and k obey k < exp ^ a M o g l o g A ^ ^ y C2 log ^ (log log log - M o g ^) where C\,C2 are sufficiently large constants. Then the statement (1.1.2) for every set AcW with \A\ > a\W\, the sumset A + A contains a k-term arithmetic progression IS true with probability 1 — O/C,Q(1) as N OO. 1.2 Preliminaries and Notation Throughout this paper, we w i l l be concerned w i t h subsets of the integers or subsets of the additive group •= Z/NZ. We define e{9) := e-x.p{2m9). We often use the notat ion A{x) to denote the characteristic function of the set A. Suppose that / and g are real-valued functions w i t h / ( x ) > 0 for al l X. We write g{x) = 0{f{x)) if \g{x)\ < Cf{x) for some constant C > 0. If f(x) > 0 we write g{x) = o{f{x)) if Vixax-^oo g{x)/f {x) = 0. F ina l ly , i f there exists C i and C2 such that C\f{x) < g{x) < C2f{x) we write g{x) = 0 ( / ( x ) ) . In this setting, we begin w i t h some prel iminary definitions and lemmas which w i l l be used throughout. Definition 1.2.1. Suppose that f : Zjy —* C . Then we define the discrete Fourier transform f(o =̂ ^ E / ( ^ ) e ( - x c / i v ) . Definition 1.2.2. / / / and g are functions such that f,g : ZN —» C , then we define their convolution {f*g){x) := Yl fiy)9i^-y)- L e m m a 1.2.3. Suppose that f and g are functions such that f,g : Z^ —• C . Then the following identities hold: (i) Parseval's identity: (ii) Fourier inversion: m = E me{-xi/N), (iii) Convolution identity: We w i l l denote the LP-norm of / by xex and if X = ZAT we w i l l write ||/||p. We w i l l say that the probability of a set A is F{A) := We define the related expectation for a function / ; Zyv ^ C to be It w i l l also be useful to sometimes use the conditional probability and con- ditional expectation, defined respectively, FiA\X) : = I ^ , E ( / | X ) 1.3 Bohr Sets In this section, we include some background relating to Bohr sets. In part ic - ular, we provide a detailed exposition of the results required in [11], inc luding a localized version of a theorem of C h a n g which is developed in [14]. One of the first uses of B o h r sets i n additive number theory came i n a paper of Bourga in [2] in which he improved the upper bound on r3{N) (the function which denotes the size of the largest subset of { 1 , A ' ' } which contains no three term arithmetic progression). His proof relies on a density increment argument, however instead of i terating on arithmetic progressions, he increases the relative density of a subset i n consecutive Bohr sets. A s we wi l l see, one can show that B o h r sets contain long arithmetic progressions. Definition 1.3.1. A Bohr set is a set of the form B = 6 -h B{A,ô) where 6 e Z iv , A C Z iv , € (0,2) and B{A, 6) := {XEZN : \e{x^/N) - 1\ < Ô for all ^ e A } . We will say that the Bohr set B is of rank d := |A| and of radius Ô. In the following lemma, we state two basic facts about B o h r sets that we w i l l use throughout. L e m m a 1.3.2. Suppose A C Zjv is a set of frequencies, and Ô, Ô-[,Ô2 € (0,2). Then the following 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. Definition 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, then we have the following size bound. L e m m a 1.3.4. Let B{A,Ô) be a CQ-regular Bohr set. Then \BiA,ô)\>ic~'clS)\'^\. Proof. We first notice that B{A, 6) C B{A, (1 + cl)ô). Hence, by regularity, we have \B{A, Ô)\B{A, (1 - çl)6)\ < \BiA, (1 + cl)ô)\B{A, (1 - cl)ô)\ <co\B{A,ô)\. Hence we must have that B{A, (l-cg)(5) is nonempty. Say b e B{A, {1-CQ)6). Now by Proper ty 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 Proper ty 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. We pick rad i i ÔQ > ôi > ... > ô^^i := ôo/2 where k = Q{N) such that ôi-i-i < (1 - cl)ôi < (1 -f cl)5i < 5i-i. B y Property 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 , _ : ) | < C W | B ( A , 5 , + i ) | . (1.3.5) Us ing this, and the fact that S ( A , Jj+i) C S (A , (5 j _ i ) , we have \BiA,il + cl)ôi)\<\B{A,ôi^,)\ < c W | B ( A , ( l - c 2 ) < 5 0 | . 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,)\ Using the assumptions on |A| and k we have C^l^l / '^ = 1 + 0 { ^ ) which gives the desired result. • 1,3.1 A l o c a l i z e d v e r s i o n of C h a n g ' s t h e o r e m In this section we would like to explain a localized version of Chang 's struc- ture theorem due to Sanders. We begin w i t h dissociated sets and the state- ment of Chang 's theorem. We also include a description of Sanders' result, its relation to the work of C h a n g and other ingredients of its proof. Definition 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. Definition 1.3.7. If A := {X\,X^} we say that the cube spanned by A is the set of the form 3 A := {Y,c^X^ : Ai G A , e { -1 ,0 ,1 } } . T h e following theorem shows that the set of large Fourier coefficients of a given subset of the integers must be structured. T h e o r e m 1.3,8. (Chang's theorem) 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 | Â [ < 2 p - 2 l o g ( l / a ) . In the remainder of this section, we w i l l explain the following proposition of Sanders which we require to prove Propos i t i on 2.7.1. Proposit ion 1.3.9. Suppose B := B{r,5) is a regular Bohr set and that e, r] e (0,1]. Assume f : ZN —̂ R such that supp{f) C B. Then there exists ACZN and 5' € (0,1] such that |A|«e2|S|log(||/||£,%)||/||i.(3)), " " ^ d ^ l S l l o g d l / I J - . ^ j l l / l l i . ^ ^ ) ) and { e 6 Z ^ : | / ( 0 l > ^ l l / l l L i ( B ) } C {e G ZTV : |1 - ei-x^/N)\ < r? V x € B ( r u A,(5')}. Sanders proves his theorem wi th two lemmas which can be compared w i t h the two conclusions of Theorem 1.3.8. T h e first step shows that the set of large Fourier coefficients of / must satisfy a structural inclusion. The second step shows that this inclusion is 'nice' in a quantitative sense. Before we can state the two required lemmas, we must generalize the definition of dissociated sets i n the context of Bohr sets. Definition 1.3.10. Suppose A := {X\,A^} andm := (mi) f_ j wheremi e Z. Define d mA := y ^ m i A ; i=i and d \m\ := ^ mi. i=l Let S be a non-empty symmetric neighborhood of 0. Then we say that A is S-dissociated if mA e S implies mj = 0 for every 1 < i < d. W i t h this definition we use the following lemma to show that the set of large Fourier coefficients of a function / is contained in a highly structured set. L e m m a 1.3.11. Suppose B := B{T,ô) is a regular Bohr set and let e, T] e (0,1]. Suppose / : ZAT —> K such that supp{f) C B and define 5 := € I'M : \m\ > If A IS a maximal e Z ^ : > dissociated subset of S then there exists '»^'^m^3d^ such that 5 C {e G Z iv : |1 - e{-x^/N)\ < T? V a; G S ( r U A , Ô')}. T h e proof of this l emma is straightforward and 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, e, rj and S are as in the previous lemma. Further, assume that / ^ 0. Then there exists 5" » such that B{T, 5") is regular and such that if A is a E Zjv : |B(OI ^ gj^}-dissociated subset of S then |A|«6-2|B|log(||/||-,%)||/||i.(^)). W h i l e the proof of this lemma requires a localized version of R u d i n ' s inequality, several steps are similar to the proof of Chang's theorem. A g a i n we direct the reader to [14] for a complete proof. F ina l ly , we would like to mention that Propos i t ion 1.3.9 can also be seen as a quantitative improvement of the dual version of a local Bessel inequality of Green and Tao [10]. Us ing the ideas from Chang'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 In this section we include a proof of Sarkozy's theorem following Green [6] which we require in order to prove Theorem 2.3.1. We also remark that as in [6] we do not require the best known bounds, and so minimize the technicalities which results in a less than opt imal quantitative bound. T h e o r e m 1.4.1, (Sârkôzy's theorem) Let 6 > 0 and suppose A C {1,...,A''} so that \A\ > ON. Assume N is sufficiently large. Then there exist elements x and y in A (x ^ y) so that x — y is a perfect square. We begin w i t h some pre l iminary lemmas and propositions. For the re- mainder of this section, we assume S to be the set of non-zero squares less than or equal to N/2. Proposi t ion 1.4.2. (Squares in uniform sets) Let 5 > 0. Suppose A C { 1 , A ' ' } such that \A\ = ôN. Assume that \À{^)\ < a for every ^ ^0 where a 2-30^13/2 _ j'hgn there exist x, y E A such that x — y is a perfect square. Proof. We first note that 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 that \B\ > ôN/2. If we then consider ^ and 5 as subsets of Zjv we can bound the number of integer square differences from below using the number of square differences modulo A^. T h e number of square differences modulo A'̂ is larger than S{x)B{y)A{y + x) =^ N^ SiOmM-O = N^mmÀ{Q)+N^ j;] (5)(05(o^(-o > N^/^S^/i -N'm^x]Â{0\'/' Y 1 ^ ( 0 1 1 ^ ( 0 1 1 ^ ( 0 1 ' / ' > A ^ 3 / 2 ^ V 4 - A ^ 2 j ^ a x | ^ ( O p / ' ( Y 1 ^ ( 0 1 ' ' ) ' ^ ' " - ( E i ^ ( o n ^ / ^ ( E iMOi'f' where we have used Parseval 's identity and Holder 's inequality. U s i n g P a r - seval again, we have the bounds | - B ( O P < ^ and | ^ ( 0 P ^ ^- F r o m [6] we have ||5||i2 < 21^/^2^-1/2 p i t t i n g this a l l together, w i t h the as- sumption of a-uniformity, we have Y S{x)B{y)A{y + x) > - cc"^ • 2''''^N'"H''''\ x,y T h i s quantity is positive w i t h our choice of a as desired. • Proposi t ion 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\ > We require the following lemma cited in [6] from [5]. T h e proof uses Weyl ' s inequality. L e m m a 1.4.4. Let a € Zjv and suppose 2̂ ^̂ ^ < t < N. Then there exists some p <t such that \p'^a\ < t'^/^^N. Proof. (Of proposition 1.4-3) B y L e m m a 1.4.4, we take t = N^/'^, and hence there exists p < A^^/^ such that \p'^^\ < A^63/64 y/^ t^gn define the square difference progression P := {p'^,2p'^, ...,Lp^] 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 the triangle inequality, we have > i 2A^ N o w we would like to show that A has increased density on some translate of P. We begin by summing the relative densities over al l translates. In the following calculat ion we use the definition of convolution as well as Parseval 's identity and the convolution identity given i n L e m m a 1.2.3. J2\An{x-P)\' = ^\J2 A{y){x - P)iy) X X y = J2\A*P{x) = N^\{A*Pm ^N'j2\^{o\'\pm' T h i s bound shows that we have the desired density increment for a given progression modulo A'', however we require true Z progressions. Hence, we need to check that our bound holds for some square progression that doesn't split . We say that a progression P is 'good' if it is a genuine Z progression and we denote the set of such progressions by G. O u r choice of L gives Lp^ < ^N^I^^N^/"^ < iV2/3 ^j^^i i ^ ^ Q ^ ^Yi3X the set of 'good' progressions must have size at least N^/^. Therefore, the contribution to our estimate above from 'bad ' progressions is given by 5 ] |A n (x - P ) p < 5 ^ L 2 < L'N''l\ x^G xiG Hence, we have xeG for large enough A''. O n the other hand, 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 that \An{xo- P)\>6{l + 2~^^Ô^^)\P\ as desired. • P r o o f of Sarkozy's theorem: We use the following iterative argument: Step 1: Set PQ := {l,...,yVo} where NQ := N, AQ := A and So := |j4o|/|Po|- If ^ 0 is such that ^ o ( O I < for each ^ 7̂ 0, we terminate. Otherwise, there must exist ^0 such that |>l(̂ o)| > <̂ ^̂ ^̂ • 2~^^. Hence by Propos i t ion 1.4.3 there exists a square difference progression P i such that l - 4onFi| 63 r l2 — — — > Ô0 + 2 00 K l l and i n l > i ^ o " " step 2: M a p the set AQ n Pi to Ai C {1 , [1/20NQ^^'^\} =: P i . A n y square difference found i n Ai w i l l correspond to a square difference i n ylo- Now apply the same argument as i n Step 1. Iterating this argument, we w i l l reach a density of 2ÔQ after at most 263j j - i i g^gpg and a density of 1 after less than 2^^S~^^ steps. F ina l ly , we check that after our iterations we s t i l l have a set P^ which has at least two elements. W e can check that this happens as long as ciiV^^/^^'^')''^'' > 2 which we can guarantee as long as N > exp(exp(c(5~^^)). 1.5 The transference principle and pseudorandom sets The idea of transference enables us deduce results for sets which obey certain random properties from results which are known for sets of positive upper density. T h e first such result of this type is a version of Roth ' s theorem i n random sets due to Kohayakawa, Luczak and R o d l [12] which we briefly described in Section 1.1 and is stated precisely in Section 2.1. A Fourier analyt ic proof of the same result is given by Tao and V u in [16]. The first such appl icat ion developed i n the Fourier analytic setting was by Green [7] i n order to prove his version of Roth ' s theorem i n the primes. T h e o r e m 1.5.1. (Green) Suppose that A C P, where P is defined to be the set of primes, such that h m sup ' ' = a > 0 n—>oo jPnl where Pn is the set of primes less than or equal to n. Then there exists x, y, z E A such that x + z ~ 2y. Green's theorem states that if one considers a subset of the primes w i t h positive relative density, then Roth ' s theorem st i l l holds. In his proof he exploits the fact that the primes obey certain random properties. Later , Green and Tao [9] reformulate the transference principle in a form we use below. T h e appl icat ion in their paper allows them to deduce a version of Roth ' s theorem for subsets of Chen primes (those primes p such that p + 2 is the product of at most 2 primes) w i t h positive relative density. T h i s form of the transference principle says that if a set is majorized by a 'pseudorandom' measure then the set can be decomposed into a large bounded component plus a smal l uni form component. O n the bounded component we can apply known results for sets of positive upper density, while the uni form component only contributes a smal l error term. L e m m a 1.5.2. Assume that f : ZN ^ [0, oo) satisfies E ( / ) > ô > 0 and 11/11, < M (1.5.6) for some 2 < q <3. Assume also that f < ly, where u : Zjv —>• [0,oo) obeys the pseudorandom condition \\m~h=o\\oo<V (1-5.7) 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, ^ € AQ}, AO = 1 / (01 > ^o} for some eo to be fixed later. Let also f2{x) — f{x) — fi{x). Then (t)o<f,<i + {i+nsor'H (ii) E / i =Ef>ô, (Hi) l i / 2 ( O l l o o < 3 ( l + 77)eo, (iv) |7i(OI < 1 / ( 01 for all ^ e ZN and i = 1,2. In particular, (L5.6) holds with f replaced by f^- Proof, (i) To verify that | / i | < 1 + 77A'"/|J3o| we use the definition of f\, the fact that / is bounded by the pseudorandom function v, and the Fourier inversion formula 1.2.3 (ii). We have, l / l | = \^yi,y2€Bo{f{x + yi-y2)) < ^yuy2eBo{Hx + yi-y2)) ^ P ( e ) e ( - ( x + y i - y 2 ) ^ / 7 V ) = ^yim^Bo V{Oe{-x^/N)\EyeBoe{-y^/N)(' < Yl mmyeBoe{~yaN)\' <l + r]N/\Bo\ which completes the proof of (i). (ii) The fact that E / i = Ef follows directly from the definition of / i . (iii) and (iv) We begin w i t h the observation that | / i (OI ^ 1 / (01 since = J2 ^yi,y2eBofix + yi - y2)e{-x^/N) xeZN which verifies (iv) i n the case that z = 1. Us ing this equality, we have Î2{o = m-m) = m{i-W'yeBMyum?) which shows (iv) w i t h i = 2. Now, if ^ e AQ then for each y e So we must have \e{y^/NJ - 1| < eo by the definition of BQ. Combin ing 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 hand, 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 < eo establishing ( i i i ) . • T h e following l emma, from [16], is needed to deduce L e m m a 2.2.6 which allows us to exploit the random properties of v in order to deduce an l'^ estimate from an P one. L e m m a 1.5.3. Suppose that f : ZN ^ [0, oo) satisfies Ef > ô > 0 and assume that f < v, where v satisfies the pseudorandom condition F ( 0 - l ç = 0 | | o o < / ? for some 0 < 77 < 1. Define A := e ZAT : |/(^)| > a} for any a > 0. Then |A| < 4/a2 for all a > 2r?i/2. P r o o f of L e m m a 2.2.6: B y assumption, we have ||/||2 < cr]~'^^^. Hence, we have - E \m\'^'+ E i / ( 0 P + ^ i--\m\<4r, 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 . Behrend , On the sets of integers which contain no three terms in arithmetic progression. Proc . N a t . A c a d . Sc i . , 23 (1946), 331-332. [2] J . Bourga in , On triples in arithmetic progressions, Geom. Punct . A n a l . 9 (1999), 968-984. [3] G . A . Fre iman , Foundation of a structural theory of set addition (trans- lated from Russian), Translations of Mathemat i ca l Monographs, 37, 1973. [4] H . Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J . d 'Analyse M a t h , 71, 1977, 204-256. [5] T . Gowers, A new proof of Szemerédi's theorem, Geom. Funct . A n a l . , 12 (2001), 465-588. [6] B . J . Green, On arithmetic structures in dense sets of integers, Duke M a t h . Jour . , 114 (2002), 215-238. [7] B . J . Green, Roth's Theorem in the primes, A n n a l s of M a t h . 161 (2005), 1609-1636. [8] B . J . Green, T . Tao, The primes contain arbitrarily long arithmetic pro- gressions. Anna l s of M a t h . , to appear. [9] B . J . Green , T . Tao, Restriction theory of the Selberg Sieve, with ap- plications. Journa l de Théorie des Nombers de Bordeaux, 18 (2006), 137-172. [10] B . J . Green , T . Tao, An inverse theorem for the Gowers U^{G) norm, Proc . E d i n b u r g h M a t h . S o c , to appear. [11] M . H a m e l and 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 Journal of Combinator ia l Number Theory, 8, 2008. [12] Y . Kohayakawa, T . Luczak , 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 . London M a t h . Soc. 28 (1953), 245-252. [14] T . Sanders, Additive structures in sumsets, to appear i n M a t h . Proc . Cambridge Phi los . Soc. [15] A . Sarkozy, On difference sets of integers i. A c t a M a t h . A c a d . Sci . Hungar , 31:125-149, 1978. [16] T . Tao, V . V u , Additive combinatorics, Cambridge U n i v . Press, 2006. [17] P . Varnavides, On certain sets of positive density, Journa l London M a t h . S o c , 34 (1959), 358-360 D E P A R T M E N T O F M A T H E M A T I C S , U N I V E R S I T Y O F B R I T I S H C O L U M B I A , V A N C O U V E R , B . C . V 6 T 1 Z 2 , C A N A D A mehamel@math. ubc. ca Chapter 2 Arithmetic structures in random sets A r i t h m e t i c structures in random sets^ M a r i a h Hamel and Izabella L a b a Abstract We extend two wel l -known results i n additive number theory, Sarkozy's theorem on square differences in dense sets and a theorem of Green on long arithmetic progressions in sumsets, to subsets of random sets of asymptotic density 0. O u r proofs rely on a restriction-type Fourier analyt ic argument of Green and Green-Tao. 2.1 Introduction T h e purpose of this paper is to extend several basic results in additive num- ber theory, known for sets of positive density in Z^v, to the setting of random sets of asymptotic density 0. T h i s Une of work originated in the paper of Kohayakawa-Luczak-Rôdl [29], who proved a random-set analogue of Roth ' s theorem on 3-term arithmetic progressions. Roth ' s theorem [32] asserts that for any fixed 6 > 0 there is a large integer NQ such that iî N > No and if A is a subset of {1 , . . . , AT} w i t h |^| > ON, then A contains a non - t r iv ia l 3-term arithmetic 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 in { 1 , . . . , N}, w i t h the property that any set A containing a positive proport ion of the elements of W must contain a 3-term arithmetic progression? T h e authors proceed to answer it i n the affirmative for random sets: * A version of this paper is published. M . Hamel and I. Laba, Addit ive 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 prob- ability p = p{N) G {CN~'^/'^, 1]. Fix a > 0. Then the statement every set A CW with \A\ > a\W\ contains a 3-term arithmetic progression is true with probability 1 — OQ(1 ) as N ^ OO. T h e current interest i n questions of this type is motivated by the work of Green [25] and Green-Tao [26], [27] on arithmetic progressions in the primes, where the "pseudorandomness" of the almost-primes plays a key role. For example, T a o - V u [39, Section 10.2] give an alternative (and simpler) proof of Theorem 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 in [29] is combinatorial and uses Szemerédi's regularity lemma, the proof i n [39] is Fourier-analytic and reUes i n particular on a restrict ion-type estimate from [25], [27]. It is natura l to ask which other results from additive number theory can be extended to the random set setting. W h i l e the methods of [29] do not seem to extend to other questions, the decomposition technique in [27] turns out to be more robust. We are able to use i t to prove random set analogues of two wel l -known results: Sârkôzy's theorem on square differences, and a theorem of Green on long arithmetic progressions in sumsets. We note that the concept of pseudorandomness has played a major role in many of the basic extremal results in additive number theory, such as Sze- merédi's theorem on ari thmetic progressions. Specifically, in order to find a certain type of an ar i thmetic structure (such as an arithmetic progression) i n sets of positive density, one often begins by showing that such structures are common i n appropriately defined pseudorandom sets. It is not clear whether our results w i l l have applications of this type, as the corresponding extremal results for sets of positive density are already known. O n the other hand, we expect that the methods developed here w i l l be useful in proving 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). For example, one could inquire about the arithmetic properties of sets of the form A-\- B, where A and B are subsets of the primes w i t h relative positive density. W e now give the precise statement of our results. Throughout the paper, VF is a random subset of ZAT , w i t h each x e ZAT belonging to W indepen- dently w i t h probabi l i ty p € (0,1]. We w i l l assume that p > A''""^, where 6 is a sufficiently smal l positive number. In part icular , we allow p to go to 0 as AT oo. We also fix J > 0 and let AcW, \A\ = S\W\. Sarkozy's theorem (proved also independently by Purstenberg) states that for any fixed positive number ô there is a large integer A ô such that if N > NQ and 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. The best known quantitative bound, due to P i n t z , Steiger and Szemerédi [31], is that one may take NQ = (log A'') '°s log AT ĵ̂ g converse direction, Ruzsa [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 e A such that X — y is a non-zero perfect square is true with probability 1 — Oa(l) as N oo. We 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}. Le t W he a random set as described above, but w i t h 6 e (0,1/2] . One can show using a probabil ist ic argument that i t holds w i t h probabi l i ty 1 - o ( l ) that the sumset A-\- Aot every subset A CW w i t h |A| > a\W\ has density at least in Zjv .̂ If 6* is close enough to 0, then we can prove the following stronger result using Fourier-analytic methods. Proposit ion 2.1.3. Suppose that W is a random subset o /Z jv 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| aN in the setting of the proposit ion: let A^ = W D{P + x), where P is an arithmetic progression i n Z/v of step about and length about aN. A n averaging argument shows that \A^\ » a\W\ for some x, while [A^c + < 2|P| ̂ aN. ^ We are grateful to Mihalis Kolountzakis for pointing this out to us and communicating a short proof. O u r second main result concerns the existence of long arithmetic progres- sions i n sumsets. Bourga in [18] proved that if A, B are sumsets of { 1 , . . . , A?̂ } w i t h 1^1 > aN, \B\ > (3N, then A + B contains a A;-term arithmetic 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 point here is that a sumset has much more arithmetic structure, and therefore contains much longer arithmetic progressions, than would be nor- mal ly expected in a set of a s imilar size (based on Szemerédi's theorem, for example). Bourgain 's bound was improved by Green [23] to k > exp(c(a/31ogAr)V2 _ i o g i o g A r ) , (2.1.2) which is the best known result in this direction so far. A n alternative proof of essentially the same bound was given more recently by Sanders [35]. O n the other hand, R u z s a [34] gave a construction showing that the exponent 1/2 i n (2.1.2) cannot be improved beyond 2 /3 . Note that ii A = B, the estimate (2.1.2) gives a non - t r iv ia l result only when a > {\ogN)~^/'^, and in part icular sets w i t h density 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 - 2 -Schoen [21]. The authors proved that iîA,B C ZN obey \A\\B\ > {6N) then A + B contains a k-term ar ithmetic progression. T h e y also gave a con- struct ion of sets A cZi\f w i t h \A\ > N^"^, where 9 is small enough depend- ing on e > 0, such that A + A does not contain an arithmetic progression longer than 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 subset o /Z^r such that the events x G W, where x ranges overZ^, are independent and have probability p = p{N) e (CN~^, 1], where 0 < 9 < 1/140. Assume that a and k obey k < exp ^ log log AT ^ y C2 log ^ (log log log iV + log ^ ) y where C\,C2 are sufficiently large constants. Then the statement (2.1.4) for every set Ad W with \A\ > a|H^|, the sumset A + A contains a k-term arithmetic progression is true with probability 1 — Ok,a(^) as N ^ oo. A non-quantitative version of the result, namely that the displayed state- ment in the theorem is true w i t h probabi l i ty 1 — o( l ) as A'' -> oc if a and k are fixed, can be obtained by apply ing Szemerédi's theorem to the positive density set A-\-A. O u r point, as in [18] or [23], is that the ar i thmetic progres- sions indicated by Theorem 2.1.4 are much longer than those i n Szemerédi's theorem, and that they can be found using a much easier argument. For comparison, the current best bounds in Szemerédi's theorem [22] imp ly that a set of relative density a in ZN should contain fc-term arithmetic progres- sions w i t h k < log log ^ log log A^^ which is much weaker than (2.1.4). T h e bounds on 9 in Theorems 2.1.2 and 2.1.4 are due to our choices of exponents i n the proofs and are probably not opt imal . T h e natural threshold would be 1/2, as in [29]. However, it does not seem possible to extend our results to a l l ^ < 1/2 using the same type of arguments as in this paper. T h e article is organized as follows. In the next section we explain the notat ion and summarize the known results that wi l l be used repeatedly. Theorem 2.1.2 is proved i n Sections 2.3 and 2.4. Its analogue for higher power differences. Theorem 2.5.1, is stated and proved in Section 2.5. The proof of Theorem 2.1.4 is given in Section 2.6, w i t h the proofs of the main estimates postponed to Sections 2.7 and 2.8. T h e proof of Propos i t ion 2.1.3, which involves a simplif ied version of the argument in the proof of Theorem 2.1.4, concludes the paper. 2.2 Preliminaries We first explain the notation. We use |A| to denote the cardinahty of a set A C Zjv. T h e probability of a set A is P ( ^ ) = N~^\A\, and the expectation of a function / : ZAT ^ C is defined as Ef = E,f = N-' Y2 /(^)- X G Z J V We w i l l also sometimes use conditional probabi l i ty and expectation m\X) = l ^ i ^ , Eif\X) = E^^xfix) = j^^Yl fi^)- Whenever the range of a variable (in a sum, expectation, etc.) is not indicated, i t is assumed to be a l l of Zjy. We wi l l also use the notation l l / l lp = ( E x 1 / (^)1" ) ' / " and Wfhrçx) = ( E . e x l / ( ^ ) r ) ' / " - A l l constants throughout the paper w i l l be independent of A'̂ , a, and A;. T h e discrete Fourier transform of / is defined by / ( 0 = E , / ( a : ) e - 2 - - « / ^ . We have the usual Plancherel identity E / ? = E fd inversion formula f{x) = E ç . z . / ( O e - ^ ^ ^ ^ / ^ . We define the convolution of two functions f, g : ZN C hy the formula ( /*5)(x) = E / ( 2 ; M x - y ) = E f^^)9{s). y t,s:t+s=:x We have the identity Nfg = f * g. We recall a few basic results about B o h r sets, a l l of which are standard in the l iterature and can be found e.g. i n [28], [39], or i n [19] where regular B o h r sets were first introduced. Definition 2.2.1. A Bohr set is a set of the form B = b + B{A, 6), where beZN, ACZN, ô e (0,2), and B{A, ô) = {xeZN: je^'^*^?/^ - 1| < <5 for all ^ € A } . We will often refer to |A| and 5 as the rank and radius of B, respectively. Definition 2.2.2. Letco be a small positive constant which will remain fixed throughout the paper. We will say that a Bohr set B{A, 6) is regular if ¥{B{A, (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,Ô) is a regular Bohr set, then F(B) > (ccg(^)l^l. L e m m a 2.2.4. Assume that co is small enough. Then for any A C Z^ with \A\ < ^JCQN and any ÔQ> Q there is a ô E {^,ôo) such that B{A,ô) is regular. We w i l l need a Fourier-analyt ic argument which first appeared i n [25] i n a sHghtly different formulation and in [27] as stated, and was adapted i n [39] to a random set setting. Specifically, [25] and [27] introduced the decomposition f = f\ + f2 defined below, where / i is the "structured" bounded part , and /2 is unbounded but random. We w i l l need several results concerning the properties of f\ and /2 , which we collect i n the next two lemmas. T h e first one is contained i n the proofs of [27, Propos i t ion 5.1] or [39, Theorem 10.20]. L e m m a 2.2.5. Assume that f : ZN [0, oo) satisfies E(f) > ô > 0 and Wfh < M (2.2.1) for some 2 < q < 3. Assume also that f < u, where u : Z^r —> [0, oo) obeys the pseudorandom condition MO - h=o\\oo < V (2.2.2) for some 0 < r/ < 1. Let fi{x) = E{f{x + yi-y2): yi,y2 € ^o), where Bo = {x: | e - 2 - « - / ^ _ i | < ^o, ^ € Ao}, AQ - : |7(C)| > eo} for some eg to be fixed later. Let also f2{x) = f{x) — f\{x). Then (i)0<fi<l + il + nBor')ri, (il) E / i = Ef, (iii) li/2lloo < 3 X l + 7?)eo, M |7i(OI < 1/(01 for all ^ e ZN and i = 1,2. In particular, (2.2.1) holds with f replaced by / a . In order to be able to apply L e m m a 2.2.5, we need to have the estimate (2.2.1) for some 2 < q < 3. To this end we have the following result, based on the Stein-Tomas argument as used in [25], [27], and contained i n the form we need i n [39, L e m m a 10.22 and proof of Theorem 10.18]. L e m m a 2.2.6. Let f and v be as in Lemma 2.2.5, except that instead of (2.2.1) we assume that II/II2 < C r ? - / 4 for some e > 0. Then (2.2.1) holds with g = 2 -I- e. W e adapt this argument to the random setting as in [39, Section 10.2]. Suppose that I ^ is a random subset of ZN such that each x EZM belongs to W independently w i t h probabi l i ty p 6 (0,1). We w i l l assume that p > , where 0 < ^ < 1/100. We also fix (5 > 0 and let AcW, \A\ = Ô\W\. We let y{x) = p-^Wix), fix) = p-^A{x). L e m m a 2.2.7. Let v and f be the random variables defined above. Then (i) WHO - lç=o||oo = 0 ( A - ^ / ^ ) with probability 1 - o ( l ) , (ii) Wfg = N-^lfg = 0{p'^) < with probability 1 - o ( l ) . P a r t (i) of tl ie l emma follows from well -known probabil ist ic arguments. It can be found e.g. i n [39, Coro l lary 1.9 and L e m m a 4.15], or extracted from the proof of L e m m a 14 i n [23]. Observe i n part icular that (i) w i t h Ç = 0 says that F{W) = p ( l + OiN''^^^)) w i t h probabi l i ty 1 - o ( l ) . P a r t (ii) follows from this and the Plancherel 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 integer. Let f : ZAT —» [0,1] be a bounded function such that Ef > Ô. Then we have E{f{n)f{n + r^)\n,reZN, 1 < r < [y/WJÎ]) > c{ô) - os{l). Theorem 2.3.1 strengthens Sârkôzy's theorem (stated in the introduc- tion) i n the same way i n which a theorem of Varnavides [40] strengthens Roth ' s theorem on 3-term arithmetic progressions. It guarantees the exis- tence of "many" square differences in 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 modif ication of V a r - navides's combinatorial argument [40]. We first note that it suffices to prove the result for characteristic functions. To 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 and / > f on A. Hence, assuming the result for characteristic functions, we have E ( / ( n ) / ( n + r2)) > jE{A{n)A{n + r^)) > jc{S/2). We now t u r n to the proof of the result for characteristic functions. Let ^ C Ziv such that \A\ > ON and N is sufficiently large. We w i l l consider ar i thmetic 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 } which have size at least i j f c . Suppose that < f . (2.3.2) We say that a progression Px^r as i n (2.3.1) is good i f \Px,rnA\>^ôk. (2.3.3) Let Gr{N) denote the set of good progressions Px,r{N) for a fixed r. We c la im that |G,(iV)| > ^SN. (2.3.4) Indeed, we have \A n (kr^, N - kr^)\ > \A\ - 2kr'^ > 5N - 2kr^ > 0(1 - ^N, k where at the last step we use (2.3.2). E a c h a € An(fcr^, N—kr'^) is contained i n exact ly k progressions Px^r- Hence \AnPx,r\>kô{\-^)N>^ôkN (fe>8). x : l< i<a ; - t - ( f c - l ) r2< iV O n the other hand, the number of progressions P^.r for a fixed r is clearly bounded by A'', hence we have an upper bound E \AnPx,r\<N-^ôk + GriN)k. x:l<x<x+{k-l)r^<N Combin ing these bounds yields (2.3.4) as claimed. Let G{N) := T.r:r^<^J^ Gr{N). T h e n G{N) > ^ ' - f = c,m^/\ (2.3.5) since k depends only on 6. B y Sarkozy 's theorem, each good progression Px^r contains a square dif- ference. We now count the number of good progressions which may contain a fixed square difference pair x,x + . Clearly, a:,x -f can be contained i n at most k — \ progressions w i t h step size and at most \k{k — 1) pro- gressions w i t h step size r'^jt for integers t> \. Since k depends only on J , the tota l number of progressions containing x,x + r^ is bounded by C2{ô). T h u s the tota l number of square differences in A must be at least 4 K i V ' / ' = c(<J)iV3/2. C2{à) Subtract ing off the t r i v i a l progressions (with = 0) gives the desired result. • 2.4 Proof of Theorem 2.1.2 Let W, A be as i n Theorem 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, but w i t h A replaced by 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 and e = 1/11 are satisfied w i t h probabi l i ty 1 - o ( l ) , thus (2.2.1) holds w i t h q = 23/11. We w i l l henceforth condit ion on these events. Let / = / i + /2 as in L e m m a 2.2.5, w i t h eo = eo(a) smal l enough to be fixed later. W e would like to ensure that ||/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 by (2.2.1) and Chebyshev's inequality we have |Ao| < {M/CQ)'^^/^^ . Now a short calculation shows that i f log — < c i log log A^ (2.4.3) eo w i t h c i smal l enough, which we w i l l assume henceforth, then (2.4.2) and (2.4.1) ho ld . 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 an actual square difference in Z , not just a square difference mod A''. We write f{x)f{x + r^) = Yl'i,j=i fi{x)fj{x + r^) , and estimate the ex- pectation of each term. A p p l y i n g Theorem 2.3.1 to / i , we get a lower bound on the m a i n term 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. We now t u r n to the error estimates. We write E (/2 (x )/2 (x + r2 )|x,r € Z iv , 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 than A ' / 3 , F r o m Green [24] we have the estimate 11̂ 1112 < 2''/''N-y\ based on a number theoretic bound on the number of representations of an integer as the sum of six squares. Us ing also Parseval 's identity and Holder 's inequality, we have Eif2{x)f2{x + t)S{t)\x,teZN) <2i9/i2^r-i/2||/, fJ/;2|,;^||i/i2 Plugg ing this into (2.4.6), we see that E ( / 2 ( x ) / 2 ( x + r2)|x,r G ZJV, 1 < r < x/ÎV/S) < c i (5 ) /4 if eo was chosen sufficiently smal l depending on 5. T h e "mixed" error terms are estimated similarly. Combin ing the error estimates wi th (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 Theorem 2.1.2 yields an 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, 3 x,y e A such that x — y — n^ for some n G N is true with probability Ok^aiX) as N oo. Since the proof is very similar to that of Theorem 2.1.2, we only sketch the m a i n steps. Instead of Theorem 2.3.1, we w i l l need a s imilar result for higher powers, which can 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. Let / : 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) - os{l). W e now follow the argument in Section 2.4. Define u, f, fi, /2 as in the proof of Theorem 2.1.2. A p p l y i n g Theorem 2.5.2 to fi, we see that E ( / i ( x ) / i ( x + r ' ^ ) | x , r G Z ; v , l < r - < !^/N/3) > c{5) - oe^,,^M{r]). To estimate the error terms, we invoke the asymptotic formula for Waring 's problem (see e.g. [30]), which implies that RkM^) ••= \{iai,agfc) € Z ^ | 4 + - + 4k = mod Ar)}| < cN^. B y convolution and Parseval identities, this translates to \\Pk\\6k < where Pk denotes the characteristic function of the set of fc-th powers smaller than N/3, and c, c i are constants depending on fc. Now we are able to estimate the 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 = if 6k is small enough. T h e proof is finished as in Section 2.4, 2.6 Long arithmetic progressions in sumsets We now t u r n to Theorem 2.1.4. In this section we prove the theorem, modulo the two m a i n estimates (2.6.1), (2.6.7) which w i l l be proved in the next two sections. O u r proof w i l l combine the arguments of Sanders [35] w i t h those of Green-Tao [27]. Let W,A be as in Theorem 2.1.4, and define i/, f as in L e m m a 2.2.7. We w i l l show that , w i t h high probabil ity, there is a reasonably large B o h r set B on which we have f * f{x) > 0 for a l l but a few values of X. B u t / * / is supported on A + A, hence a l l but a smal l fraction of B is contained in A + A. T h e proof is concluded by invoking a pigeonholing argument from [35], which says that the port ion of B contained in A + A contains a long arithmetic progression. T h e details are as follows. F i x k (the length of the progression), and let cr = {16k)~^. We w i l l also assume that k > ko and a < ao , where ko eN is a sufficiently large absolute constant and ao > 0 is a sufficiently small 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~'^^^ and e = 1/9 are satisfied w i t h probabi l i ty 1 — o ( l ) , thus (2.2.1) holds w i t h q = 19/9. Let / = / i -f /2 as in L e m m a 2.2.5, w i t h eo = eo(a, cr) smal l enough to be fixed later. We w i l l assume that (2.4.3) holds w i t h c i sufficiently smal l ; as in Section 2.4, it follows that ||/i||oo < 2. We need an extension of a result of Sanders [35]: there are regular Bohr sets B := b -h B ( r , 6) and B' :=b + B{r, 5') such that {xeB': ( / i * f,){x) > ^\B\}\ > (1 - a)\B'\, (2.6.1) and i' » ^ , (2.6.2) |r| « a - 2 l o g ( a - i ) . (2.6.4) We establish this i n Propos i t ion 2.7.2. We then verify in Section 2.8, v ia a restriction-type argument, that i f log - » a - 2 ( i og i ) ( l og / c ) ( l og l og f c + l o g - ) , (2.6.5) eo o; a w i t h a large enough impl ic i t constant, then {xeB': | /2* / . ( a : )|>^|B|} < a\B'\, i = l , 2 . It follows that {xeB': ( / * / ) ( x ) > ^ | S | } > ( l - 4 a ) | 5 ' | , (2.6.6) (2.6.7) provided that bo th (2.4.3) and (2.6.5) hold. A somewhat cumbersome cal- culat ion shows that eo can be chosen so as to satisfy both (2.4.3) and (2.6.5), provided that ^ l og^ ( l og l og logA^ + l o g i ) ' ^ ' which is equivalent to (2.1.4). W e now invoke L e m m a 6.5 i n [35], which says that if ( 4 a ) - i « |r|-i5'Ari/|r|^ (2.6.9) then the set on the left side of (2.6.7) contains an arithmetic progression of length (16cr)~i = k. P lugg ing i n (2.6.2)-(2.6.4) and solving for N, we see that (2.6.9) holds i f logA^ > a"^(log' 'A; + log^( - ) - h l o g - l o g l o g f c ) . a a (2.6.10) Another cumbersome calculation shows that if we assume (2.6.8), then the addit ional condit ion (2.1.3) suffices to guarantee that (2.6.10) holds. Thus , assuming bo th (2.1.3) and (2.1.4), the set on the left side of (2.6.7) contains a fc-term ar i thmetic progression. Since that set is contained in A + A, the conclusion of the theorem follows. In the next two sections we complete the proof by verifying the inequal- ities (2.6.1), (2.6.6). 2.7 The main term estimate Proposi t ion 2.7.1. Let B = b + BÇT^ô) be a regular Bohr set. Let f : Ziv —> R be a function such that supp{f) C B, 0 < f < 1 and E j g / = a > 0. Fix a 6 (0,1] and let d = jFj . Then one of the following must be true: (i) There is a S' :^ ^ 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 U A , ô") such that E{f\B")>a{l + 2-^), (2.7.2) where |A| < a - ^ l o g a - ^ and Ô" > ^ r g ^ . Proof: W e essentially follow the argument of Sanders [35]; however, some care must be taken to get the right quantitative version. Replac ing / by /(• + &) if necessary, we may assume that 6 = 0. Let CQ be a smal l enough constant which w i l l be fixed later. B y [28], L e m m a 8.2, we can find Ô' such that Ô' e icoa^ôd-\2coa'^ôd-^) (2.7.3) and that 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 that 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 funct ion" of / , We first c la im that l ^ i j ^ * ^(^) ^ + Oidô'ô-'a). {2.7A) To prove this , we write T h e first t e rm obeys ' " ' xes xeS XGS ^ E ( / . / ) W < 5 f ^ | S l = ^ . (2.7.5) by the choice of S. T h e second term is estimated as i n [35]. B y [35], Coro l lary 3.4, we have for x € B' / * ^ ( ^ ) - / * ^ ( 0 ) <^dô'ô-\ B u t / * ^ ( 0 ) = a , so that / * ^(x) = a + 0{d5'ô-^) for x G B'. Hence in^Wl* = JW^^ + 0{dô'ô-')) = aa + 0{dô'ô~'a). (2.7.6) \B'\ \B\ - ^ \B' F i n a l l y , we t r iv ia l l y have B * B{x) < \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). We now convert this to a Fourier analyt ic statement. We have Y9*9{x)= E 9*9{x)S{x) xes xeÎN = N'Y1 \9iO\'S{0- (.eZN Hence, by the triangle inequality, (2.7.4) implies that p i ^ E l ^ ( O l ' l ^ ( O I >%f + 0{dô'5-'a). (2.7.8) Define £ : = { e 6 Z ^ : | 5 ( 0 l > ^ ^ } . We c la im that the m a i n contr ibut ion to the sum in (2.7.8) comes from C In fact I II U ^ / : I I ^^c aaN aa N aa 4|J5| J2 \f{x)-aB{x) |2 + a^a 4151 ' ' X&N 2 a^o 2a^a a^a < 1 - 4 4 4 aa 2N = ^ ( a - a ) < a'^a Hence " ' 7 T E l » « ) l ' l ^ « ) l > 4 ^ + 0 (<H'i - ' ) . Since 15 (01 is t r i v ia l l y bounded by a, we have Y,\9{0\'>^ + 0idô'ô~'a). (2.7.9) 1^1 W e now apply the localized version of Chang's theorem proved in [35] (Proposit ion 4.2) to S C B', w i t h e = a / 4 and r/ = 1/2. We conclude that there is a set A C Zjv and a SQ > 0 such that 24 a2 (?̂ a^4 d2 l o g ( j - i ' |A| < ^ l o g a - \ 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" := B{TuA,ô") is regular. Note that this together w i t h (2.7.3) implies that 5" obeys the condit ion i n (ii). We may also assume that Ô" < 6'. O u r goal is to get the density increment as in (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 and the convolution identity we have a ^ ( i + o ( a - ^ r f 5 ' r i ) ) < Y \m\'mo\' iV3 '16 ^ - \B\\B'' We now apply L e m m a 5.2 from [35] and conclude that 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 ) . We now let the constant CQ in (2.7.3) be smal l enough, so that the error term is bounded by a2'~^. T h e conclusion (ii) follows if we choose b" to maximize 1/ * B"{b")\. T h i s proves Propos i t ion 2.7.1. Proposi t ion 2.7.2. Let / : ZAT -> [0,1] be defined such that ]Exez^/ (x ) = Q > 0 . Let a G (0,1]. Then there exist Bohr sets B := b + B{r,ô) and B' := b + B(T,Ô') such that {xEB': ( / * / ) ( x ) > ^ | 5 | } | > ( l - a ) | 5 ' | . and Mog(a and \T\ « a - 2 l o g ( a - i ) . Proof of Proposition 2.7.2: We construct the Bohr sets B and B' by i terat ing Propos i t i on 2.7.1. Let PQ := {0}, and pick (5o 1 so that BÇTOTSQ) is regular. Define ao := a . Averaging over translates of B(ro,ôo), we see that there is a bo such that E{f\Bo) > ao for Bo = bo + B{To,ôo). B y Propos i t i on 2.7.1, one of the following must hold : (i) There is a (5Q » ^0 such that BQ := bo + B{TQ, Ô'Q) is regular and {xeB'o-.if* f){x) > ^\Bo\}\ > (1 - a)\B'o\, (2.7.10) (ii) There is a regular Bohr set Bi := bi + B{To U Ao, ôi) such that E ( / | 5 i ) > a o ( l + 2-^), (2.7.11) where |ro| < aô^\og{o-') and 6i » jf^^^^y If (i) holds, we let B' — BQ and we are done. If on the other hand (ii) holds, we repeat the procedure w i t h BQ replaced by Bi, and continue by induct ion. If we have not satisfied (i) by the end of the kth step, we have found a regular B o h r set B^ := bk + B{Tk, ok) such that Eif\Bk) = ak\Bk\, where « f c > « f e - i ( l + 2 - ' ) , (2.7.12) 4 » ,p i s f ' ; ' I V (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 terat ion must terminate (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^^ ^ogia'^) < a'^ l o g ( a - i ) 5̂ (1 + 2-^)-^' < a - 2 l o g ( a - i ) . j=o Fina l ly , using our bounds for ak and IF^I, we have Mog(<7-i)^ for some absolute constant C > 0. T h i s proves Propos i t ion 2.7.2. 2.8 The restriction argument Assume that the hypotheses of Theorem 2.1.4 hold. We need to show that if h, J2 are as in L e m m a 2.2.5 and B' are the B o h r sets chosen in Propo - sit ion 2.7.2, then (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) We have xeB' y z x,y,z,u,v Ç V = N'^(B^ *fM-0fi(0f2{0• i B y Holder 's inequality, ||/̂ * /2|li2(s,) < iV^IIB^ * 7/2II10 ||7J2||io/9- (2.8.17) A p p l y i n g Young 's inequality, we get ||P^*7i/2||lO<||B^||5||7i/2||lO/9. (2.8.18) 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 Holder 's inequality again. P lugging this together w i t h (2.8.18) in (2.8.17), we see that | | / i * / 2 | l i 2 ( B ' ) < ^ ' m 5 l l 7 7 2 | | ? 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 Plancherel 's theorem and 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 ) and ||7i||i9/9 = 0 (1 ) , z = 1,2. B y L e m m a 2.2.5(iii), we have II/2II0C < Ceo. F i n a l l y , 5 : i lloo 11-̂ 112 ^ -^-^yl-II-S'il2 = - ^ ^ l " ' P ' l l i < P ' l l L l | 5 ' l l ' < ^ l l ^ ' l l o C o m b i n i n g these estimates, we get We need the right side of this to be smaller than ^cr|i?|2|i?'|, i.e. we need to have • e f < c a V ^ i ^ D ^ = ca'aF{B)MB'Y^'. (2.8.20) B u t by L e m m a 2.2.3 and (2.6.2)^(2.6.4), F{B) and F{B') are bounded from below by F{B) > F ( B ' ) » ic6"p » ( - ^ ) \ loe fc / ca ^ log - log k V log fc / where we plugged in cr = (16fc)-^ Hence (2.8.20) holds if 98, 0 / CQ log i log fc A short calculation shows that (2.6.5) is sufficient to guarantee that (2.8.21) is satisfied. 2.9 Proof of Proposition 2.1.3 Let 0 < (T < (a - /3)/10. Define i^,f,f\,f2 as in Section 2.6, except that instead of (2.4.1) we w i l l require l l / i | | o o < l + a, (2.9.1) which holds for large enough A'' (depending on a and on the eo in the defi- n i t ion of fi) by the same argument as in Section 2.4. It clearly suffices to prove that {XEZN •• / * fix) > 0} > ( Q - lQa)N. (2.9.2) Indeed, (2.9.2) shows that the sumset A + A in ZN has size at least hence so does the sumset A + A inZ. We first c la im that if N is large enough, then {x € ZN : fi * / i ( x ) > aaN] > ( a - 3a)iV. To see this, we first note that l l / i * M i l = l l / i l l ? = « ' ^ ' ( 1 + o ( i v - ' / ' ) ) - O n the other hand, i f (2.9.3) failed, we would have l l / i * / i 111 < cyc^N • N + aA^( l + a + 0{N-'^'^)) • {a - 3a)N = a^N^l + 0{N-^^^)) - aaN^, which contradicts (2.9.4). Th i s proves (2.9.3). T h e proof of (2.9.2) w i l l be complete if we can show that (2.9.3) (2.9.4) { x € Z j v : | / i * / 2 ( x ) | > — i V } < aN. (2.9.5) To this end, we repeat the argument in Section 2.8. It suffices to prove that l| /^* /2||i< 200 aN^. (2.9.6) A s i n Section 2.8 (with B ^ B' = ZN), we have l l / i * / 2 | | i « 4 ^ ' A ^ ' , (2.9.7) and the right side is smaller than the right side of (2.9.6) if eo <§C a'^'^a^^, w i t h a smal l enough impl i c i t constant. T h u s (2.9.5) holds for large enough A'' if eo was chosen smal l enough. T h i s proves Propos i t i on 2.1.3 2.10 Acknowledgements The authors were supported in part by an N S E R C Discovery G r a n t . We are grateful to B e n Green for suggesting the feasibihty of Theorem 2.1.2, and to Ern ie Croot and M i h a l i s Kolountzakis for helpful discussions and suggestions. Bibliography [18] J . Bourga in , On arithmetic progressions in sums of sets of integers, in A tribute to Paul Erdos, pp. 105-109, Cambridge Univers i ty Press, 1990. [19] J . Bourga in , On triples in arithmetic progressions, Geom. Punct . A n a l . 9 (1999), 968-984. [20] M . - C . Chang , A polynomial bound in Freiman's theorem, Duke M a t h . J . 113 (2002), 399-419. [21] E . Croot , I .Ruzsa, T . Schoen, Long arithmetic progressions in sparse sumsets, Integers: T h e Electronic Journal of Combinator ia l Number Theory, 7(2) (2007), # A 1 0 . [22] W . T . Gowers, A new proof of Szemerédi's theorem, Geom. Funct . A n a l . 11 (2001), 465-588. [23] B . J . Green, Arithmetic progressions in sumsets, Geom. Funct . A n a l . 12 (2002), 584-597. [24] B . J . Green, On arithmetic structures in dense sets of integers, Duke M a t h . Jour . , 114 (2002), 215-238. [25] B . J . Green , Roth's Theorem in the primes. Annals of M a t h . 161 (2005), 1609-1636. [26] B . J . Green, T . Tao, The primes contain arbitrarily long arithmetic pro- gressions. A n n a l s of M a t h . , to appear. [27] B . J . Green , T . Tao, Restriction theory of the Selberg Sieve, with ap- plications. Journa l de Théorie des Nombers de Bordeaux, 18 (2006), 137-172. [28] B . J . Green, T . Tao, An inverse theorem for the Gowers U^{G) norm, Proc . E d i n b u r g h M a t h . S o c , to appear. [29] Y . Kohayakawa, T . Luczak , 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 . Nathanson, Additive Number Theory: The Classical Bases, Springer, New Y o r k , 1996. [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 . London M a t h . Soc. 37 (1988), 219-231. [32] K . R o t h , On certain sets of integers, J . London M a t h . Soc. 28 (1953), 245-252. [33] L R u z s a , Difference sets without squares. Per iod . M a t h . Hungar . 15 (1984), no. 3, 205-209. [34] I. R u z s a , Arithmetic progressions in sumsets. A c t a A r i t h . 60 (1991), 191-202. [35] T . Sanders, Additive structures in sumsets, to appear in M a t h . Proc . Cambridge Phi los . Soc. [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 . Sc i . Hungar . 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 . Tao, Arithmetic progressions and the primes, Collect . M a t h . (2006), V o l . E x t r a , 37-88. [39] T . Tao, V . V u , Additive combinatorics, Cambridge U n i v . Press, 2006. [40] P . Varnavides, On certain sets of positive density. Journa l L o n d o n M a t h . S o c , 34 (1959), 358-360 D E P A R T M E N T O F M A T H E M A T I C S , U N I V E R S I T Y O F B R I T I S H C O L U M B I A , V A N C O U V E R , B . C . V 6 T 1Z2 , C A N A D A mehameWmath. ubc. ca, ilaba@math. ubc. ca Chapter 3 Conclusion 3.1 A potential application to primes One appl icat ion of the methods used in this paper involves translat ing results from the random setting into that of the primes. A theorem of Green [47] states that if is a subset of the primes w i t h positive relative density, then A must contain three terms i n arithmetic progression. T h e strategy developed by Green i n [47] is essentially to exploit certain ' random' properties of the primes ( in a Fourier analyt ic sense). One of the first hurdles to overcome is that the primes aren't actual ly random. For example, the set of primes isn't randomly d istr ibuted modulo a small prime. To deal w i t h this, one employs what is today referred to as the W — trick (a nice explanation of this can be found i n [49]). T h i s entails defining a number m which is the product of smal l primes. T h e next step is to consider the residue classes modulo m. The set of primes contained i n a given residue class w i l l then behave in a satisfactorily random manner. The proof then restricts itself to the port ion of the set A which falls in one part icular residue class (pick the residue class on which A has largest relative density). W o r k i n g w i t h this chosen port ion of A one applies Roth ' s theorem in a manner s imilar to the application of Sârkôzy's theorem in the proof of Theorem 2.1.2. W i t h o u t providing details, we note that the appropriate choice for J / is a modified version of the von Mango ldt function supported on the chosen residue class. C o m b i n i n g the results from the manuscript [51] contained in this dis- sertation, and the framework for the primes of Green [47] or Green and Tao [49] we can prove a version of Sârkôzy's theorem in the primes (and a s imi lar extension for long arithmetic progressions i n sumsets). Specifi- cally, it is possible to show that if A is a subset of the primes wi th pos- itive relative density, then A must contain a square difference. However, we should mention, that in the case of Sârkôzy's theorem such a variation holds in the primes for density reasons alone. P i n t z , Steiger and Szemerédi [55] show that 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 prime number theo- rem states that the number of primes less than an integer A ' ^ is asymptotic to N/ log A^. In joint work w i t h K a r s t e n Chipeniuk , we are attempting to prove an analogue of Theorem 2.1.3 i n the setting of the primes. We begin w i t h a mot ivat ing example. Let P be the set of a l l primes and define A := {p € P : p = 1 mod n} and consider AAT •= {p & A : p < N}. T h e n , the prime number theorem for arithmetic progressions gives us quantitative information on the size of Ajy . Namely , we have Set 6 :— T h e n , assuming N is sufficiently large, we have \AN\ » S-^^jj. O n the other hand. A N + A N C {m = 2 mod n} and hence, \AN + A N \ < ~ ^ ^ N. n log log n T h e previous example leads us to the following question: Question 3.1.1. Suppose A cP such that h m sup —— — = 5 N->oo \PN\ where PN •= {p < N : p EP}. IS it true that IAN + ANI^T—T^J^-N? log log(1/5) The question above differs from other applications i n the primes since for a density result, we are not able to consider only one residue class modulo m. If p is a prime number, then the residue class in which p lies must be contained in the mult ipl icat ive subgroup Zj|^ c Zm- W h i l e we are able to apply a modified version of the convolution lemma from [51] to a given residue class on which a subset of the primes has large enough relative density, we must also ensure that the sumset determined by these residue classes covers enough of Z j „ . In particular we must answer the following question: Question 3.1.2. Suppose 5 C Z ^ such that \S\ > ôc/){m). Is it then true We intend to answer these questions in an upcoming paper. 3.2 A n improvement to Theorem 2.1.2 Reca l l that i n the statement of Theorem 2.1.2 we define the random set W CZM w i t h each element chosen w i t h probabi l i ty p(A'') e {cN~^, 1] where we require 0 < ^ < 1/110. A s we noted in 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. In a work [54] that is currently in preparation, H . Nguyen and 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 € A such that x — y is a non-zero perfect square is true with probability 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. The ir proof uses methods from graph theory relating to the cited work of Kohayakawa, Luczak , and R o d l and in particular they use Szemerédi's regularity lemma. 3.3 Future directions A famous result of Bergelson and L e i b m a n [42] is a po lynomial version of Szemerédi's theorem. T h e o r e m 3.3.1. Bergelson-Leibman Let 6 > 0 and let P i , b e poly- nomials 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 and Le ibman 's proof uses ergodic theory and is currently the only known proof of a po lynomial version of Szemerédi's theorem. Recently, Tao and Ziegler [59] proved that the primes contain arb i t rar i ly long polyno- mia l progressions, relying on a certain quantitative version of Theorem 3.3.1. T h e i r proof, s imi lar ly to the proof of the Green-Tao theorem on primes in arithmetic progression, can be divided into three m a i n steps: a po lynomial version of Szemerédi's theorem, a transference principle and a method to treat the primes as ' random' . We should note that despite the similarities i n t i ie outl ine, t l ie po lynomial version requires several arguments which are not needed in the case of f inding arithmetic progressions in the primes. There have been certain results using Fourier analysis relating to the po lynomial version of Szemerédi's theorem. One reason that this is of inter- est is that the ergodic proof, relying on the axiom of choice, does not provide any information on when the first occurrence of a given po lynomial pattern must occur i n a subset of positive upper density. The first quantitative result i n this direct ion is due to Green [46]: T h e o r e m 3.3.2. Suppose that A C {1,..., A'} so that\A\/N > (log log A f ) -^ Then there exists x, x + y,x + 2yEA such that y = a'^ + b'^. His proof requires quadratic Fourier analysis. We notice, that using these methods. Green is able to deduce quantitative bounds on the required density for a subset of the integers to contain this part icular ar i thmetic pro- gression. Since Green's current bound is not sufficient for handhng subsets of the primes, we believe that it would be of interest to consider this prob- lem i n the random setting. We expect that the method of Green-Tao for handing four-term arithmetic progressions in the primes should provide the necessary framework for such an application. M o r e specifically, i f we assume that W is a random subset of ZAT and A C W has positive relative density then we would Hke to construct / and u as i n Section 2.2. For such an ar- gument, we expect that it would be necessary to replace the pseudorandom condit ion ||?(0 ~ lç=o||oo < V w i t h an appropriate quadratic condit ion. A result of L y a l l and M a g y a r [53] can be seen as a special case of the po lynomial version of Szemerédi's theorem or as a generalization of Sarkozy's theorem. T h e o r e m 3.3.3. Assume that Pi,...,Pi 6 Z[d] are linearly independent polynomials so that Pi{0) = 0 for each i = I, .-.,1 and assume the largest degree of the polynomials Pi is k. Suppose that A C {!,..., A'} so that \A\/N > ( ( loglogAr)2/logAf)^' ' '^^'"^\ Then there exists an integer d such that Pi{d) Ci A - A for every i = 1 , k . T h e i r proof is Fourier analytic and again provides quantitative bounds that the ergodic proof does not. We expect that using s imilar methods to those in this manuscript we could extend Theorem 3.3.3 to subsets of random sets. We should remark that L y a l l and Magyar are optimist ic that combining their proof w i t h the methods of P i n t z , Steiger and Szemerédi would result in a similar bound to that known for Sarkozy 's theorem. T h i s method would have the advantage of including al l sets of such density, rather than subsets of random sets or subsets of the primes. F i n a l l y , we believe that it wou ld be of interest to find a Fourier analytic proof of the following special case of the Bergelson-Leibman theorem which can be compared w i t h both Theorem 3.3.2 and Theorem 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 that such a result would require quadratic Fourier analysis, which would enable us to determine a bound on how soon we could find three elements of the form x, x + y'^ and x + y^ i n A. If we are then able to extend this to show that , in fact, A must contain 'many ' triples of the desired form, then we would hope to be able to prove a version of Theorem 3.3.4 i n the random setting or i n the primes. Such a result would provide new quantitat ive information for a special case of the Theorem of Tao-Ziegler on po lynomia l progressions in the primes. Bibliography [41] F . Behrend , On the sets of integers which contain no three terms in arithmetic progression. P roc . N a t . A c a d . Sc i . , 23:331-332, 1946. [42] V . Bergelson and A . L e i b m a n , Polynomial extensions of van der Waer- den's and Szemerédi's theorems, J . Amer . M a t h . Soc. 9 (1996), no. 3, 725-753. [43] J . Bourga in , On triples in arithmetic progressions, Geom. Funct . A n a l . 9 (1999), 968-984. [44] G . A . Fre iman, Foundation of a structural theory of set addition (trans- lated from Russian), Translations of Mathemat i ca l Monographs, 37, 1973. [45] T . Gowers, A new proof of Szemerédi's theorem, Geom. Funct . A n a l , 12:465-588, 2001. [46] B . J . Green, On arithmetic structures in dense sets of integers, Duke M a t h . Jour . , 114 (2002), 215-238. [47] B . J . Green, Roth's Theorem in the primes, Anna l s of M a t h . 161 (2005), 1609-1636. [48] B . J . Green, T . Tao, The primes contain arbitrarily long arithmetic pro- gressions. A n n a l s of M a t h . , to appear. [49] B . J . Green, T . Tao, Restriction theory of the Selberg Sieve, with ap- plications, Journa l de Théorie des Nombers de Bordeaux, 18 (2006), 137-172. [50] B . J . Green, T . Tao , An inverse theorem for the Gowers U^{G) norm, Proc . E d i n b u r g h M a t h . S o c , to appear. [51] M . H a m e l and L L a b a , Arithmetic structures in random sets, I N T E - G E R S : Electronic Journa l of Combinator ia l Number Theory, 8, 2008. [52] Y . Kohayakawa, T . Luczak , 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 and A . Magyar , Polynomial configurations in difference sets, preprint. [54] H . Nguyen and V . V u , i n preparation. [55] J . P i n t z , W . L . Steiger, E . Szemerédi, On sets of natural numbers whose difference set contains no squares, J . London M a t h . Soc. 37 (1988), 219-231. [56] K . R o t h , On certain sets of integers, J . London M a t h . Soc. 28 (1953), 245-252. [57] T . Sanders, Additive structures in sumsets, to appear in M a t h . Proc . Cambridge Phi los . Soc. [58] A . Sarkozy, On difference sets of integers I, A c t a M a t h . A c a d . Sci . Hungar , 31:125-149, 1978. [59] T . Tao and T . Ziegler, The primes contain arbitrarily long polynomial progressions, to appear in A c t a . M a t h . [60] T . Tao, V . V u , Additive combinatorics, Cambridge U n i v . Press, 2006. [61] P . Varnavides, On certain sets of positive density, J o u r n a l London M a t h . S o c , 34 (1959), 358-360 D E P A R T M E N T O F M A T H E M A T I C S , U N I V E R S I T Y O F B R I T I S H C O L U M B I A , V A N C O U V E R , B . C . V 6 T 1Z2 , C A N A D A mehamel@math. ubc. ca
- 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
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
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 |
FileFormat | 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 |
GraduationDate | 2008-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | 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}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0066823/manifest