Structure and Arithmetic in Sets by Karsten Chipeniuk B. Science, University of Victoria, 2005 M. Science, University of British Columbia, 2007 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Doctor of Philosophy in THE FACULTY OF GRADUATE STUDIES (Mathematics) The University Of British Columbia (Vancouver) April 2011 c Karsten Chipeniuk, 2011 Abstract We prove results in arithmetic combinatorics involving sums of prime numbers and also some variants of the Erd˝os-Szemer´edi sum-product phenomenon. In particular, we prove nontrivial lower bounds on the density in the integers of the sumset of a positive relative density subset of the primes. The proof of this result uses Green and Green-Tao pseudorandomness arguments to reduce the problem to an analogous statement for relatively dense subsets of the multiplicative subgroup of integers modulo a large integer N. The latter statement is resolved with a combinatorial argument which bounds high moments of a representation function. We also show that if two distinct sets A and B of complex numbers have very small productset, then they produce maximally large iterated sumsets. This uses an algebraic concept of the multiplicative dimension of a finite set. As an application of the case A = B, we obtain a quantitative version of a result of Chang on sums and products of distinct complex elements. ii Preface Two of the chapters of this thesis were produced from manuscripts accepted for publication: Chapter 2: K. Chipeniuk and M. Hamel, On sums of sets of primes with positive relative density. Accepted for publication in J. London Math. Soc. Chapter 3: K. Chipeniuk, Sums and products of distinct sets and distinct elements in C. Integers 10, 639- 667 (2010). The identification of the research program leading to the material in Chapter 2 was made by Izabella Łaba. Research activities were conducted equally by both authors with assistance provided by Ernie Croot (in particular with regards to the proof of Theorem 1.2.2) and Izabella Łaba. Both authors contributed equally to writing the manuscript, and we obtained proofreading and editing assistance from Izabella Łaba, Neil Lyall, and Akos Magyar. The author was aided by Izabella Łaba and J´ozsef Solymosi with the indentification and design of the research program leading to the material in Chapter 3, as well as with the initial investigations. Later research activities and the writing of the manuscript were conducted largely independently by the author, with feedback given by Izabella Łaba, Boris Bukh, and Mariah Hamel. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Set arithmetic and the structure of sets . . . . . . . . . . . . . . . 7 1.3.1 Basic notions of arithmetic combinatorics . . . . . . . . . 7 1.3.2 Additive tuples, the Balog-Szemer´edi-Gowers theorem, and the subspace theorem . . . . . . . . . . . . . . . . . . . . 10 1.3.3 Freiman’s theorem and the Pl¨unnecke-Ruzsa inequality . . 14 1.3.4 A version of Freiman’s theorem for distinct sets in real finite dimensional vector spaces . . . . . . . . . . . . . . . 15 Variants of the sum-product problem . . . . . . . . . . . . 23 Harmonic analysis on the group ZN and uniform sets . . . . . . . 28 1.4.1 28 1.3.5 1.4 Harmonic analysis preliminaries . . . . . . . . . . . . . . iv 1.4.2 Pseudorandomness and uniformity . . . . . . . . . . . . . 30 Number theoretic preliminaries . . . . . . . . . . . . . . . . . . . 33 1.5.1 Tools from analytic number theory . . . . . . . . . . . . . 33 1.5.2 Transference properties of the primes . . . . . . . . . . . 36 On sums of sets of primes with positive relative density . . . . . . . 43 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.2 Preliminaries and an outline of the argument . . . . . . . . . . . . 47 2.3 Sumsets and uniformity of the primes in residue classes . . . . . . 49 1.5 2 3 2.4 Sumsets of positive density subsets of . . . . . . . . . . . . . 57 2.5 Completion of the proof of Theorem 2.3.1 . . . . . . . . . . . . . 67 Sums and products of distinct sets and distinct elements in C . . . . 70 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.2 Sums and products of a single set . . . . . . . . . . . . . . . . . . 75 3.2.1 Multiplicative dimension and bounding the doubling constant 75 3.2.2 Bounding additive 2h-tuples . . . . . . . . . . . . . . . . 81 3.3 Simple sums and simple products . . . . . . . . . . . . . . . . . . 86 3.4 Sums of distinct sets with small productset . . . . . . . . . . . . . 91 3.4.1 3.4.2 4 Z∗m Bounding the multiplicative dimension in terms of the relative size of the productset . . . . . . . . . . . . . . . . . 91 Conclusion of the proof of Theorem 3.1.3 . . . . . . . . . 96 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.1 4.2 Overview of the results in the context of current research . . . . . 103 4.1.1 Uniformity of primes . . . . . . . . . . . . . . . . . . . . 103 4.1.2 Sums and products . . . . . . . . . . . . . . . . . . . . . 105 Possible future directions . . . . . . . . . . . . . . . . . . . . . . 106 4.2.1 A sharp bound in Theorems 1.2.1 and 2.1.3 . . . . . . . . 106 4.2.2 Weaker conditions in Theorem 3.1.3 . . . . . . . . . . . . 107 4.2.3 Sharp bounds for simple sums and products, and minimising examples for sum-product variants . . . . . . . . . . . 108 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 v List of Tables Table 1.1 Bounds on δ in the sum product problem. . . . . . . . . . . . . 24 Table 1.2 Variants of the sum product problem. . . . . . . . . . . . . . . 24 vi List of Symbols Notation Interpretation Z N N0 C C∗ R T ZN Z∗N P An A×B Ak ∏ni=1 Ai A(k) kA O(g(x)) o(g(x)) f εg f ≈g Integers Positive integers Nonnegative integers Complex numbers Multiplicative subgroup of complex numbers Real numbers One dimensional torus Integers modulo N Multiplicative subgroup of integers modulo N Prime numbers A ∩ [1, n] Cartesian product of A with B k-fold Cartesian product of A Cartesian product of A1 , ..., An k-fold iterated productset of A k-fold iterated sumset of A A function f satisfying f (x) ≤ Cg(x) for some constant C A function f satisfying f (x)/g(x) → 0 as x → ∞ There is a constant C(ε) such that f ≤ C(ε)g There are constants C1 , C2 such that C1 g ≤ f ≤ C2 g vii Acknowledgments I would like to thank my advisor, Izabella Łaba, for her constant support and assistance throughout the past six years. This work has only been possible through the insight, advice, and encouragement that she has always provided. I wish to thank the members of my examining committee: Mei-Chu Chang, Alexander MacKay, Akos Magyar, William Evans, Izabella Łaba, and Malabika Pramanik. I am grateful to Malabika Pramanik and J´ozsef Solymosi for also being a part of my supervisory committee. I am further grateful to them, along with Izabella Łaba and Akos Magyar, for providing a wide variety of interesting graduate courses, as well as for their support and advice. I would like to express my gratitude to Ernie Croot and Neil Lyall for their valuable assistance and contributions. I am thankful for having had the support and friendship of Mariah Hamel, as well as that of several of my fellow graduate students, including Simon Rose, Alex Duncan, Kelly Paton, Josh Zukewich, David Kohler, and Kelan Zhai. I would have been forever at a loss without the frequent assistance of the wonderful staff of the UBC Mathematics Department, and would like to thank all of them for their tireless efforts. I also wish to acknowledge the many opportunities provided to me by the University of British Columbia Department of Mathematics, which maintains its commitment to improving graduate student life. I am thankful to the National Sciences and Engineering Research Council for its financial support through a PGS-D scholarship, and to the University of British Columbia for its support through a Four Year Fellowship. Finally, I am deeply grateful to my family for their neverending love and support, and to Maria Khomenko for always being there to make the bad times good and the good times better. viii To my mom, for introducing me to coffee, and to those who have brought me coffee. For those who laugh with me. ix Chapter 1 Introduction 1.1 History Arithmetic combinatorics is a branch of mathematics which concerns the structure of sets whose elements we can add or multiply, and how this structure relates to these underlying operations. It has grown out of questions concerning the integers in Ramsey theory from the first half of the twentieth century, some of which were answered by mathematicians such as van der Waerden and Schur. Later, it began to achieve a firm theoretical framework from contributions due to Behrend, Roth, and Varnavides in the 1950s as well as Freiman, Furstenberg, and Szemer´edi in the 1970s, many of which used ingenious combinatorial arguments. In the first decade of the twentieth century, arithmetic combinatorics has seen a great deal of activity, fueled by work by Gowers, Green, and Tao which exploited harmonic analytic techniques in conjunction with ideas from analytic number theory. It now addresses questions in general group, ring, and field structures, demonstrating that the idea that a set’s geometry is related to its additive or multiplicative structure is a deep and intrinsic phenomenon. We begin by reviewing briefly some of the results which have led us to this point, in the hope of motivating what is to come after. In 1927, van der Waerden [47] proved the following theorem. Theorem 1.1.1. If the integers are coloured with finitely many colours, then there must exist a monochromatic arithmetic progression of arbitrary finite length. 1 This statement is typical of some results in additive combinatorics: sets that are not too small must contain at least some arithmetic-geometric structure, in this case an arithmetic progression. An outstanding conjecture in this spirit was provided by Erd˝os and Tur´an [18]. Conjecture 1.1.1. Let A ⊂ N, and suppose that 1 ∑ a = ∞. a∈A Then A contains an arithmetic progression of arbitrary finite length. Notice that the Erd˝os-Tur´an conjecture implies van der Waerden’s theorem; moreover, it would imply that the primes contain arbitrary length arithmetic progressions. It is clear that if the colouring in van der Waerden’s theorem has k colours, then one of the colour classes will contain a proportion of the integers that is at least 1/k. That is, if we define the upper density δ of a set A to be |A ∩ {1, ..., N}| , N N→∞ δ = lim sup then at least one colour class will have δ ≥ 1/k. This leads naturally to asking whether Ramsey theoretic statements such as van der Waerden’s theorem have stronger, density formulations. In 1953, Roth [36] proved the existence of three term progressions in subsets of the integers with positive upper density δ. In 1959, Varnavides [48] counted the number of three term progressions in such a set which occur with all elements smaller than a large integer N, giving a lower bound in terms of δ and N. In 1969, Szemer´edi [41] proved the existence of four term progressions in positive density sumsets. Then, in 1975, the arbitrary length case was finally resolved, also by Szemer´edi [42]. Theorem 1.1.2. If A is a set of integers of positive upper density, then A contains an arithmetic progression of arbitrary length. Once one has this result, Varnavides’s averaging argument can once again be 2 applied to gain a lower bound on the number of k term progressions, but now the bound has an additional dependence on k. Szemer´edi’s proof of his theorem was a combinatorial tour de force, and people had a continued interest in approaching it from different disciplines. Shortly after Szemer´edi’s original argument, in 1977, Furstenberg [22] was successful in giving a new proof using ergodic theory. Meanwhile, still in the 1970s, individuals including Freiman, Ruzsa, Pl¨unnecke, and Szemer´edi investigated phenomena surrounding the sumset of a set A. That is, for a finite set A of integers, we construct its sumset A + A = {a + a : a, a ∈ A}. A fundamental result of Freiman [21] connected in a very direct way additive and geometric structure in such a set. This theorem says, roughly speaking, that if A + A is small, then A must be contained efficiently in a set with very rigid geometric structure. The precise statement is given below, as Theorem 3.1.5. In 1983, Erd˝os and Szemer´edi [17] investigated the relationship between sums and products in the integers. To do this, they considered the productset A · A = {aa : a, a ∈ A} of a set A, thereby making the transition from additive to arithmetic combinatorics. They then pioneered an elegant conjecture, which claims that a set cannot be both additively and multiplicatively structured. Conjecture 1.1.2. Let ε > 0, and let A ⊂ Z. Then |A + A| + |A · A| ε |A|2−ε . This conjecture remains unresolved, although it has been supported through many variants on the same theme. We will elaborate on some of these variants in Section 1.3.5. More recently, problems in the spirit of van der Waerden’s instigating result have experienced a resurgence, following Gowers’s [24] proof of Szemer´edi’s theorem using a harmonic analytic method in 2001. In 2005, Green [27] succeeded in transferring this proof to apply it to finding arithmetic progressions in relatively dense subsets of the prime numbers. Shortly thereafter, in 2008, he and Tao [29] finally resolved a long standing conjecture: Theorem 1.1.3. The primes contain arbitrarily long arithmetic progressions. 3 In fact, this result also holds for subsets of the primes with positive upper relative density; however, the proof requires the exploitation of certain uniformity properties of the primes. We have yet to see if it is true on density grounds alone. Following the proof of their theorem, Green and Tao set out a program for proving the existence of a general class of structures in the prime numbers, leading to the Gowers inverse conjecture [30], which was recently resolved [25], [26]. However, two deep conjectures about the additive structure of the primes remain unsolved. One is the twin primes conjecture, which concerns primes which are very near to each other: Conjecture 1.1.3. There are infinitely many primes p such that p + 2 is also prime. The other is the Goldbach conjecture, which asks for the sumset of the prime numbers: Conjecture 1.1.4. Every even integer larger than 2 is the sum of two primes. 1.2 Main results This section is a summary of the main theorems proved in this thesis. While the statements are all rigorous, this treatment is intended to have an informal tone, so technical definitions underlying some of the statements have been left to Section 1.3, Section 1.4, and Section 1.5. The proofs of Theorem 1.2.1 and Theorem 1.2.2 are left to Chapter 2, and the proofs of Theorem 1.2.3 and Theorem 1.2.4 are left to Chapter 3. In [27], Green gave a formal translation of the idea that the primes are somewhat uniformly distributed. Meanwhile, in [31] Hamel and Łaba showed that a randomly constructed set will produce a large sumset with high probability (see Theorem 1.4.2). Combining these two ideas, it is natural to ask whether a subset of the primes should have large sumset. That is, we denote the set of primes by P and define A to be a subset of P with positive upper relative density δ. The problem is then to determine bounds on the upper density of A + A in N. It is well-known that P + P has density 1/2 in N; this is a special incidence of the case δ = 1. The Goldbach conjecture is a stronger statement, asserting that 4 every even integer greater than two should be expressible as a sum of two primes. On the other hand, for general values of δ, a short computation shows that A + A will have density at least δ2 . In joint work with Mariah Hamel, we proved the following stronger result for general values of δ: Theorem 1.2.1. If A is a subset of primes with positive relative upper density 0 < δ < 1, then A + A has has positive upper density 2/3 (log log(1/δ))1/3 C1 δe−C2 (log(1/δ)) in the natural numbers, where C1 and C2 are absolute constants. In the above theorem, the exponential factor goes to 0 as δ → 0, faster than 1/ log(1/δ) but slower than any power of δ. As suggested, this was an improvement over the δ2 bound, and it was natural to question what a sharp estimate would look like. Perhaps surprisingly, the density of A + A (in N) need not in general remain bounded from below by cδ for any constant c as δ → 0. To see this, we found an example which exploited the well-known obstructions to uniformity in the primes: for example, there is only one even prime, there is only one prime congruent to 0 modulo 3, there is only one prime congruent to 0 modulo 5, and so on. A full description of the construction is given in Chapter 4. A critical tool in the proof of Theorem 1.2.1 is the following theorem, which addresses similar phenomena in the multiplicative subgroup of the integers modulo m, for large natural numbers m. Theorem 1.2.2. Let 0 < α < 1. Assume that m ∈ Z+ is sufficiently large depending on α. If B ⊂ Z∗m satisfies |B| ≥ αϕ(m) then there are absolute constants C1 and C2 such that 2/3 (log log(1/α))1/3 |B + B| ≥ C1 αe−C2 (log(1/α)) m. The fact that the same exponential factor appears in both Theorem 1.2.1 and Theorem 1.2.2 is not a coincidence - the loss in Theorem 1.2.1 is entirely due to the geometry of Theorem 1.2.2. 5 Next, we discuss the results in Chapter 3. There are a number of variants of the sum-product phenomena ([2], [10], [15], [1]) including a paper of Chang [8]. In one of her theorems, Chang considered iterated sumsets: beginning with the sumset A + A, the kth iterated sumset is kA = A + (k − 1)A. The theorem says that if A ⊆ N and |A · A| is small enough, then kA must have approximate size |A|k . The main result of Chapter 3 is that this behaviour can be extended to distinct sets A and B of complex numbers whose productset is small. Theorem 1.2.3. Let A, B ⊂ C with |B| = C|A| for some C ≥ 1, and suppose that |AB| < α|A|. If α log |A| then there is an absolute constant c1 such that |kA + lB| ≥ c1 |A|k |B|l − Ok,l,α (|B|k+l−1 ) (k + l)4(k+l) 15(k+l) α where the implicit constant in the O term can be taken as c2 e4(k+l) for an absolute constant c2 . From the special case A = B, it is possible to obtain the following result on simple sums and simple products. Theorem 1.2.4. Let ε > 0 and let n0 = n0 (ε) be sufficiently large in terms of ε. Let A+ denote the set of complex numbers which can be expressed as a sum of elements of A with no two summands equal, and let A× denote the analogous set defined with products. Then for any n ≥ n0 we have min (1/200−ε) loglogloglog(n) log(n) |A+ | + |A× | ≥ n . (1.2.1) A⊂C,|A|=n These results are structured on a large technical framework which has been built in the literature of arithmetic combinatorics. The remainder of the introduction will provide some exposition of the tools to be used in the proofs of the above results: first, in Section 1.3, we describe some of the basic definitions and theorems of arithmetic combinatorics, which illustrate the relationship between set structure and arithmetic. In Section 1.4, we discuss tools which have come from harmonic analysis and have proven to be of great use in describing additive properties of 6 unstructured sets. The last section of the introduction, Section 1.5, brings forth some of the theory of the primes from analytic number theory; it concludes with a description of some of the ideas which came out of Green’s 2005 work. Following the introduction are our main research chapters. Chapter 2 is by and large taken from the author’s joint paper with Hamel, [14]. It contains the proofs of Theorem 1.2.1 and Theorem 1.2.2. Lastly, Chapter 3 is taken from [13], and in it we prove Theorem 1.2.3 and Theorem 1.2.4. Finally, we conclude with Chapter 4, where we discuss our main results in context, to gain an understanding of their overall significance amidst the history described above. We also discuss possible future research directions. 1.3 1.3.1 Set arithmetic and the structure of sets Basic notions of arithmetic combinatorics In this section we introduce the notions of sumsets and productsets, and prove the so-called trivial estimates on the sizes of these sum and productsets. This begins to make precise the intuition that a set has small sumset if and only if it is also geometrically structured. Let A and B be subsets of a group G. Often, but not always, G is taken to be abelian. In much of what follows, G will be the integers, denoted by Z, the real numbers, denoted by R, the complex numbers, denoted by C, or the integers modulo some natural number N, denoted by ZN . We can construct the sumset of A with B, A + B = {a + b : a ∈ A, b ∈ B}. When A = B, we obtain the sumset of A, given by 2A = A + A. For k ∈ N, k ≥ 2, we can then construct the kth iterated sumset of A from the (k − 1)th iterate, by kA = (k − 1)A + A. By A − B, we mean A + (−B), where −B = {−b : b ∈ B}. In the case in which G is replaced by a ring R, we can construct the productset of A with B, A · B = {ab : a ∈ A, b ∈ B}, as well as the productset of A, A(2) = A · A, and the kth iterated productset of A, 7 A(k) = A(k−1) · A. It is then natural to ask how large these constructions can be, in terms of the sizes of A and B. We have the following trivial estimates, which were taken from [44]: Lemma 1.3.1. Let A, B be finite, nonempty subsets of a (not necessarily abelian) group G. Then max (|A|, |B|) ≤ |A + B| ≤ |A||B| and |A| ≤ |A + A| ≤ |A|2 . Proof. The left hand inequality for |A + B| follows from considering A + {b} ⊂ A + B for an element b ∈ B and {a} + B ⊂ A + B for a ∈ A. The left hand inequality for |A + A| follows immediately. Let A = {a1 , ..., an } and let B = {b1 , ..., bm } where n = |A|, m = |B|. Then the right hand inequality is seen by noting that there are nm = |A||B| possible expressions ai + b j with 1 ≤ i ≤ n and 1 ≤ j ≤ m. Finally, the right hand inequality for |A + A| follows immediately from that for |A + B| on taking B = A. In the case G = R, we can use commutativity and the total ordering of the reals to refine the bounds as follows. Lemma 1.3.2. Let A, B be finite subsets of R. Then |A + A| ≤ |A|(|A| + 1)/2. and |A + B| ≥ |A| + |B| − 1. Moreover, the bound on |A + B| holds with equality if and only if A and B are arithmetic progressions with the same common difference. Proof. Let n and m be integers such that |A| = n and |B| = m respectively, and denote the elements of A in increasing order by a1 < ... < an and those of B by b1 < ... < bm . 8 Then the inequality containing |A + A| follows from applying commutativity of R to the expressions ai + a j and a j + ai , 1 ≤ i, j ≤ n. We therefore have the upper bound |A| + 1 2 |A + A| ≤ which evaluates to the one we seek. For the bound on |A + B|, we note that a1 + b1 < a1 + b2 < ... < a1 + bm < a2 + bm < a3 + bm < ... < an + bm . (1.3.1) There are m sums in this expression containing a1 , and n containing bm , and both a1 and bm appear in a single sum, that is a1 + bm . It therefore follows that |A + B| ≥ n + m − 1 which is the desired inequality. Next we prove the statement about arithmetic progressions. [=⇒]: Suppose that A and B are sets of real numbers such that |A + B| = |A| + |B| − 1. Denoting the sizes of A and B and their elements as above, we recall that each of the sums in Equation 1.3.1 is distinct, and that there are |A + B| of them. It follows that each sum of an element of A with an element of B must be equal to one of the expressions in Equation 1.3.1. In particular, we have a1 + b1 < a2 + b1 < a2 + b2 < ... < a2 + bm−1 < a2 + bm . Referring to Equation 1.3.1, we therefore see that a2 + b1 = a1 + b2 a2 + b2 = a1 + b3 .. . . = .. a2 + bm−1 = a1 + bm . Rearranging these, one finds that bi −bi−1 = a2 −a1 for i = 2, ..., m. In other words, 9 B is an arithmetic progression of step size d = a2 − a1 . By exchanging the roles of A and B, we find that A is as well. [⇐=]: Suppose that A and B are arithmetic progressions with the same common difference d, and let the sizes and elements of A and B be denoted as above. Then we have A = {a1 , a1 + d, ..., a1 + (n − 1)d} B = {b1 , b1 + d, ..., b1 + (m − 1)d} A + B = {a1 + b1 , (a1 + b1 ) + d, (a1 + b1 ) + 2d, ..., (a1 + b1 ) + (n + m − 2)d}. From this we see that the sumset has size (n + m − 2) + 1 = n + m − 1. The above lemmas are interesting largely in that they are the best that we can do in general: there are sets which satisfy the bounds with equality. We will often refer to sumsets as being ‘large’ or ‘small’; the exact meaning of these terms varies with context, but it is typically in reference to the extreme bounds above. A set A with large sumset will, short of contextual restrictions, satisfy |A + A| ≥ C|A|2−ε for some constant C, whereas one with small sumset will satisfy something more like |A + A| ≤ C|A| for some constant C. Of course, depending on the situation these meanings might vary. Lastly, it is worth noting that a result involving general sumsets in an arbitrary abelian group G will also hold for productsets, provided that the notion of multiplication one has is itself commutative, and also that the setting one is working in contains multiplicative inverses. The geometric structure changes appropriately: for example, in Lemma 1.3.2, the arithmetic progressions are replaced by geometric progressions. As a particular illustration, the sum-product conjecture (Conjecture 1.1.2) pursues the trivial upper bound for one of the sets A + A, A · A. 1.3.2 Additive tuples, the Balog-Szemer´edi-Gowers theorem, and the subspace theorem In this section, we describe how the conditions of a set having a large or small (iterated) sumset can be rephrased in terms of its intersection with certain linear surfaces, as described by particular linear equations. For a complete treatment of 10 this idea, we recall the Balog-Szemer´edi-Gowers Theorem, although it will not be applied in the sequel. Lastly, we connect these ideas with a powerful tool from algebraic number theory, the Subspace Theorem (Theorem 1.3.2), which will be used in the proofs of Theorem 1.2.3 and Theorem 1.2.4. If A is a set with a large sumset, then it must follow that few sums coincide: we expect that for a randomly chosen quadruple a1 , a2 , a3 , a4 ∈ A, the probability that a1 + a2 = a3 + a4 (1.3.2) should be very small. In particular, in the extreme case that |A + A| = |A|2 , the only way this equation holds is if a1 = a3 and a2 = a4 . Note that it automatically follows that no pair of elements in A can commute if we are to obtain the maximal sumset size - this structure immediately negates the maximal upper bound on the sumset. Definition 1.3.1. For a set A in a (not necessarily abelian) group G, a quadruple (a1 , a2 , a3 , a4 ) ∈ A4 satisfying Equation 1.3.2 is called an additive quadruple. Similarly, a 2k-tuple (a1 , ..., ak , a1 , ..., ak ) ∈ A2k is called an additive 2k-tuple if a1 + ... + ak = a1 + ... + ak . Just as additive quadruples will relate to the sumset, additive 2k-tuples will clearly have a relationship to the kth iterated sumset. In a similar way, we can also define additive 2k + 2l-tuples in Ak × Bl when we wish to consider iterated sumsets of two distinct sets. In relating sumset size and number of additive tuples, we will make extensive use of the next definition; for simplicity, we will now restrict our attention to abelian groups. Definition 1.3.2. Let A be a finite set in a group G with commuting operation +, and let k ≥ 2. Then we define the representation function rkA : kA → N by rkA (x) = |{(a1 , ..., ak ) ∈ Ak : a1 + ... + ak = x}|. Once again, this extends to representation functions rkA+lB : kA + lB → N defined on iterated sumsets of two distinct sets. We can now gain a precise idea of the relationship between sumset size and 11 additive quadruples as follows: Let A be a finite set in a group G with commuting operation +. Then we have |A|2 = ∑ r2A (x) x∈A+A since every pair (a1 , a2 ) ∈ A × A sums to some element in A + A. Next, note that if we denote the number of additive quadruples in A4 by Q, we have ∑ 2 r2A (x) = Q. x∈A+A Hence, applying the Cauchy-Schwartz inequality, we have 1/2 1/2 2 |A| ≤ ∑ 2 r2A ∑ 1 x∈A+A x∈A+A = Q1/2 |A + A|1/2 Rearranging, |A + A| ≥ |A|4 /Q. (1.3.3) In other words, if we have few additive quadruples, say on the order of |A|2 , then A + A will be large, whereas if A + A is small, then there will be many additive quadruples. We can obtain an analogous relationship for iterated sumsets in the same manner. Now, we would also expect that a large number of additive quadruples would imply a small sumset; however, since Equation 1.3.3 only gives lower bounds on |A + A| and Q, we cannot automatically conclude this. However, we do have the following partial converse, known as the Balog-Szemer´edi-Gowers Theorem [23], which says that a set with many additive quadruples will contain a large subset which behaves as we would expect. Theorem 1.3.1. Let A be a finite subset of an abelian group G, and let K > 0. If Q≥ |A|3 K , then there is a subset A ⊂ A such that (i) |A | ≥ cK −C |A|, (ii) |A + A | ≤ CKC |A |. 12 To describe the next result, we must introduce some notation and terminology. Let K be an algebraically closed field with characteristic 0, and let K ∗ be the multiplicative subgroup of K (so K ∗ = K \ {0}). We consider (K ∗ )n to be a group under componentwise multiplication via the multplication operation on K. We will be considering subgroups Γ of (K ∗ )n , and will have need of the following property. Definition 1.3.3. A subgroup Γ of (K ∗ )n is said to have finite rank r if Γ contains a subgroup Γ0 , which is finitely generated by r elements, such that Γ/Γ0 is a torsion group. In particular, groups which are finitely generated by r elements have rank r; in our use of the subspace theorem we will be exclusively interested in this case. The subspace theorem concerns certain solutions of linear equations with coefficients in K ∗ . These solutions will be nondegenerate, in the following sense. Definition 1.3.4. Let a1 , ..., an ∈ K ∗ . Then a solution (x1 , ..., xn ) ∈ (K ∗ )n to the equation a1 x1 + ... + an xn = 1 (1.3.4) is called nondegenerate if no proper subsum of the left hand side vanishes. Let A(a1 , ..., an ; Γ) denote the number of nondegenerate solutions to Equation 1.3.4 which are contained in Γ. The subspace theorem then tells us that A(a1 , ..., an ; Γ) is finite, even though Γ is in all likelyhood infinite. Moreover, it gives us a quantitative upper bound on A(a1 , ..., an ; Γ). In fact this bound depends only on the rank r of Γ, requiring no further structural information. In addition, the bound depends not on the exact coefficients a1 , ..., an , but rather on the number n of them. In other words, we will have A(a1 , ..., an ; Γ) ≤ A(n, r). The precise statement is the following. Theorem 1.3.2. Let Γ ⊂ (K ∗ )n be a subgroup of rank r. Then for any a1 , ..., an ∈ K ∗ we have A(a1 , ..., an ; Γ) ≤ exp (6n)3n (r + 1) . 13 (1.3.5) This theorem was previously applied by Chang [10] and Chang-Solymosi [12] in an arithmetic combinatorics context, however it has not achieved widespread use in the subject. This is perhaps surprising, on account of the discussion in this section: we have seen how the size of a sumset depends on solutions of equations which can be easily put into the form Equation 1.3.4. On the other hand, the subspace theorem does lead to quantitatively weak bounds in problems of an arithmetic combinatorial nature. Indeed, the bound in Theorem 1.3.2 is believed to quite possibly be far from best possible. 1.3.3 ¨ Freiman’s theorem and the Plunnecke-Ruzsa inequality We now recall two of the foundational results in arithmetic combinatorics. The first, the Pl¨unnecke-Ruzsa inequality, shows that control of A + A gives us control over all subsequent iterated sumsets. The second, Freiman’s theorem, is an example of an inverse theorem in arithmetic combinatorics. Rather than using the structure of a set to compute the sumset, it uses bounds on the sumset to conclude something about the structure of the underlying set. Both results will be used in Chapter 3. We will begin by stating the Pl¨unnecke-Ruzsa inequality [38]. Theorem 1.3.3. Let Z be an abelian group and let A and B be subsets of Z with |A + B| ≤ K|A|. Then for every n, m ∈ N we have |nB − mB| ≤ K n+m |A|. The proof of Theorem 1.3.3 is an elegant graph-theoretic argument. In fact, the statement above is a corollary of a statement about how fast certain sequences of bipartite graphs can “magnify”. For details, see [44]. Theorem 1.3.3 suggests that it may at times be helpful to measure the size of a sumset A + A relative to the size of the initial set A. This motivates the following definition. Definition 1.3.5. Let A be a subset of a finite abelian group G. Then the doubling constant of A, denoted σ(A), is given by σ(A) = |A + A| . |A| 14 A logical question is to ask what happens when σ(A) is bounded above by some number K, which may or may not depend on the size of A. The statements that one looks for are often structural results about the set A, the archetypal result being what is now known as Freiman’s theorem. Before giving the statement of Freiman’s theorem, we need the following definition, which gives us the structure that we are looking for. Definition 1.3.6. A subset P of an abelian group G is a generalized arithmetic progression of dimension d if there are group elements a0 , a1 , ..., ad and integers L1 , ..., Ld such that it can be written in the form d P= a0 + ∑ ki ai : 0 ≤ ki ≤ Li − 1 . i=1 In this case, P is called a proper generalized arithmetic progression of dimension d if |P| = L1 · ... · Ld . The original version of Freiman’s theorem is the following. Theorem 1.3.4. Let A ⊂ Z satisfy |A + A| ≤ K|A| for some K ∈ R. Then there is a generalized arithmetic progression of P of dimension at most K O(1) and size eK |P| O(1) |A| which contains A. If we are willing to worsen the size of P, we can gain better bounds on the dimension of P. The following refinement of Freiman’s theorem is due to Chang [7]. It is the one we will use in Chapter 3. Theorem 1.3.5. Let Z be a torsion-free abelian group, and let A ⊂ Z with |A+A| ≤ K|A| for some K ∈ R. Then there exists a proper generalized arithmetic progression P of dimension at most K − 1 and size |P| ≤ C(K)|A| which contains A. Here C(K) depends only on K. 1.3.4 A version of Freiman’s theorem for distinct sets in real finite dimensional vector spaces We will now prove a variant of Freiman’s theorem due to Ruzsa [37], which will be useful for deriving Theorem 3.1.3. The proof of this variant is self-contained, 15 whereas the original theorem of Freiman and Chang’s refinement of it rely on the Pl¨unnecke-Ruzsa inequality as well as some machinery that we will not cover in this thesis (for details, see [44]). We begin with a definition. Definition 1.3.7. For A ⊂ Rd , we define the dimension of A, denoted dim A to be the minimal dimension of an affine subspace which contains A. For sets A, B ⊂ Rd , we have: |A| ≥ dim A + 1 (1.3.6) dim(A + B) ≤ dim A + dim B (1.3.7) dim(A ∪ B) ≥ dim(A + B). (1.3.8) These properties can be proved by considering a set of dim A linearly independent differences in A, and likewise for B. The statement we would like to show is the following. Theorem 1.3.6. Let d ∈ N, and let A, B ⊂ Rd be finite with |A| ≤ |B|. Suppose dim(A + B) = d. Then we have |A + B| ≥ |B| + d|A| − d(d + 1) . 2 (1.3.9) We will follow Ruzsa’s original proof; another treatment may be found in [44]. Since we wish to investigate the size of A + B when dim(A + B) = d, it makes sense to define the following function Fd : N2 → N: Fd (m, n) = min{|A + B| : A, B ∈ Rd , |A| = m, |B| = n, dim(A + B) = d}. Lemma 1.3.3. We have the following properties: (i) Fd (m, n) is defined if and only if m + n ≥ d + 2. (ii) Fd (m, n) = Fd (n, m). Proof. The second property is clear by definition. The first property follows from Equation 1.3.6 and Equation 1.3.7. 16 The proof will bound Fd by a second function Gd , which we define by m−1 Gd (m, n) = n + ∑ min(d, n − j), n≥m≥1 j=1 and Gd (m, n) = Gd (n, m) if m > n. Lemma 1.3.4. We have the following properties of Gd (m, n): (i) Gd (m, n) is increasing with n. (ii) Gd (m, n) = Gd (n, m). (iii) We have n + d(m − 1), if n − m ≥ d Gd (m, n) = , if 0 ≤ t = n − m < d and n > d n + d(m − 1) − (d−t)(d−t−1) 2 (m−1)(2n−m) n+ , if n ≤ d 2 Proof. Once again, (ii) follows by definition. To see (i), we observe that (in the definition) Gd (m, n) is a sum of an increasing function of n with m − 1 nondecreasing functions of n. Property (iii) can be derived by a direct computation using the definition of Gd (m, n). We will show that Fd (m, n) ≥ Gd (m, n). (1.3.10) This will imply Theorem 1.3.6 as follows. Proof of Theorem 1.3.6 from Equation 1.3.10. We proceed from part (iii) of Lemma 1.3.4. It is clear that we obtain Theorem 1.3.6 in the cases |B| − |A| ≥ d and 0 ≤ |B| − |A| < d, n > d upon adding d to the second term and subtracting it at the end. We must therefore derive it in the case |B| ≤ d. In this case, we use the definition of Gd (m, n) directly; let d, m, n ∈ N be such that 0 < m ≤ n ≤ d. Let k be a nonnegative integer such that n = d − k. Observing 17 the n − j < d for j ≥ 1, we have m−1 Gd (m, n) = n + ∑ (n − j) j=1 (m − 1)m 2 (m − 1)m = n + (m − 1)(d − k) − 2 (m − 1)m = n + md − − mk − (d − k). 2 = n + (m − 1)n − Now, by the conditions on m and n we have m ≤ d − k, so we have (m − 1)m + mk + (d − k) ≤ 2 (d − k − 1)(d − k) + mk + (d − k) 2 d−k−1 = ∑ j + mk + (d − k) j=1 d−k ≤ ∑j + k(d − k) j=1 d−k < ∑j + (d − k + 1) + (d − k + 2) + ... + d j=1 = d(d + 1) . 2 Hence Gd (m, n) ≥ n + md − d(d + 1) . 2 Applying this with m = |A|, n = |B|, we have the result. The proof of Equation 1.3.10 will follow from a double induction on d and m + n. We will have use of the following lemma which relates Fd (m, n) to the case in which at least one of the parameters is decreased. Lemma 1.3.5. Let m, n ≥ 2 be such that m + n ≥ d + 2, and suppose that d ≥ 2. Then at least one of the following is true: (i) Fd (m, n) ≥ d + 1 + Fd (m − 1, n − 1), (ii) Fd (m, n) ≥ n + Fd−1 (m − 1, n − 1), 18 (iii) Fd (m, n) ≥ n + Fd−1 (m − 1, n), (iv) Fd (m, n) ≥ m + Fd−1 (m, n − 1). Proof. We will denote vectors in Rd by boldface letters. Let A, B ⊂ Rd satisfy |A| = m, |B| = n, and |A + B| = Fd (m, n). Let e be a vector such that all of the scalar products e · x are distinct as x ranges over A ∪ B. Define a0 to be an element of A which minimises (e, a) over all elements of A, and similarly define b0 . Without loss of generality, we may translate A and B and assume that a0 = b0 = 0. Next, let A = A \ {0} and let B = B \ {0}. By definition of the translations mentioned above, we have (e, x) > 0 for all x ∈ A ∪ B . (1.3.11) The proof now splits into two cases, based on the dimension of A + B . Case 1: dim(A +B ) = d. In this case we will show that (i) holds. In particular, we let C := (A + B) \ (A + B ) ∪ {0} = (A ∪ B ) \ (A + B ) so that |A + B| = |A + B | + |C| + 1. Now, from the last line we already have |A + B| ≥ |C| + 1 + Fd (m − 1, n − 1), so it is enough to prove that |C| ≥ d. We will do so by showing that C spans A + B. Let s ∈ A + B, and consider all representation of s as a sum s = x1 + ... + xk where xi ∈ (A + B) \ {0} for all i. By Equation 1.3.11, we must have k ≤ N, where N = (e, s)/ min{(e, x) : x ∈ (A + B) \ {0}}. For each such representation of s, each xi is either in A + B or else it is in C. But 19 if we choose a representation with maximal k, every xi must in fact be in C, since otherwise we could write xi = a + b for some a ∈ A , b ∈ B , giving a longer representation. It follows that we can write every element of A + B as a sum of elements in C. Hence C spans A + B, so that |C| ≥ d. Case 2: dim(A + B ) < d. In this case, we can conclude that A + B is contained in a proper affine subspace of Rd ; in other words, there is a vector subspace V of Rd such that A + B is contained in a translate V + p. From this we conclude the existence of vectors pA , pB such that A ⊂ V + pA B ⊂ V + pB . Moreover, these vectors may be chosen orthogonal to V , since A + B ⊂ V . We will assume that V also has minimal dimension out of all subspaces containing A + B , in which case dimV < d. Furthermore, by definition of A and B , we see that dimV > d − 2 as follows: if all elements of A + B are in V = x0 + span(x1 , ..., xD ), then A − A ⊂ span(x1 , ..., xD ). Hence A ⊂ span(x1 , ..., xD , a) for any a ∈ A, and arguing similarly for B we see that A + B ⊂ span(x1 , ..., xD , a, b), which requires D ≥ d − 2. The proof now decomposes further based on the dimension of V , and whether or not pA = 0. Subcase (2a): dimV = d − 2. In this case, observe that B ⊂ V ∪ (V + pb ). Furthermore, using v, v , v to denote elements of V (which may change from expression to expression), each element of A is of the form v + pA and each element of B is of the form v or v + pb . Hence each element of A + B is of the form v + pA + v = v + pA or v + pA + v + pB = v + pA + pB . In other words, A + B ⊂ (V + pA ) ∪ (V + pA + pB ). It follows that A + B = B ∪ (A + B) (1.3.12) is a disjoint union. From this we have Fd (m, n) ≥ n + |A + B|, and we will have concluded that (iii) holds if we can determine that A + B has dimension d − 1. But B ∪ (A + B) can have dimension at most 1 more that A + B, so by Equation 1.3.12 this last assertion 20 holds. Subcase (2b): dimV = d − 1, pA = 0. In this case, observe that B ⊂ V + pB and A + B ⊂ V + pA + pB implies that A + B ⊃ {0} ∪ B ∪ (A + B ) (1.3.13) is a disjoint union. We therefore obtain Fd (m, n) ≥ 1+(m−1)+Fd−1 (m−1, n−1), which is (ii). Subcase (2c): dimV = d − 1, pA = 0. Then pB = 0, since otherwise we would have A + B ⊂ V ; the dimension of V is too small for this to be true. In this case, A ⊂ V and A + B ⊂ V + pB , so A + B = A ∪ (A + B ) (1.3.14) is a disjoint union. We therefore obtain Fd (m, n) ≥ m + Fd−1 (m, n − 1), which is (iv). We are now ready to conduct the double induction needed to prove Equation 1.3.10. Base Case: d = 1. In this case, Equation 1.3.10 reduces to the inequality |A + B| ≥ m + n − 1 which we know is true from the discussion in Section 1.3.1. Induction: Let d ≥ 2, and let m, n ∈ N satisfy m + n ≥ d + 2. Suppose that Equation 1.3.10 holds for d − 1 with all pairs m , n and for d with all pairs m , n satisfying m + n < m + n. We will show that this implies that it holds for d and the pair m, n. Combining the induction hypothesis with Lemma 1.3.5 we have the following four new inequalities: (i’) Fd (m, n) ≥ d + 1 + Gd (m − 1, n − 1). (ii’) Fd (m, n) ≥ n + Gd−1 (m − 1, n − 1), (iii’) Fd (m, n) ≥ n + Gd−1 (m − 1, n), 21 (iv’) Fd (m, n) ≥ m + Gd−1 (m, n − 1). The strategy now will be to show that each of the right hand sides is larger than Gd (m, n). (i’) From the definition, we have m−1 Gd (m, n) = n + ∑ min(d, n − j) j=1 m−2 = n + min(d, n − 1) + ∑ min(d, n − j). j=1 Since we would like to express this in terms of Gd (m − 1, n − 1), we shift the parameters m and n in by 1, giving m−2 Gd (m, n) = ((n − 1) + min(d + 1, n − 1)) + ∑ min(d, (n − 1) − j) j=1 m−2 = (n − 1) + ∑ min(d, (n − 1) − j) + min(d + 1, n − 1) j=1 = Gd (m − 1, n − 1) + min(d + 1, n − 1) ≤ Gd (m − 1, n − 1) + d + 1 which is the result desired. (ii’) In this case, we will show that Gd (m, n) − Gd−1 (m − 1, n − 1) ≤ n, from which the required estimate will follow. Writing out the definitions, the left hand side is m−1 = n+ ∑ m−2 min(d, n − j) − n − 1 + j=1 ∑ min(d − 1, n − 1 − j) j=1 m−2 = 1+ ∑ (min(d, n − j) − min(d − 1, n − 1 − j) + min(d, n − m + 1) j=1 = 1 + (m − 2) + min(d, n − m + 1) ≤ m − 1 + n − m + 1 = n. (iii’) This follows from the previous case, on noting that Gd−1 (m − 1, n) ≥ 22 Gd−1 (m − 1, n − 1) by Lemma 1.3.4. (iv’) In this case, we must consider the possibilities m = n and m < n separately. For m = n, n − 1 < m, so we must use the symmetry of Gd (m, n) to write Gd (m, n) − Gd−1 (m, n − 1) = Gd (n, n) − Gd−1 (n, n − 1) = Gd (n, n) − Gd−1 (n − 1, n) n−2 = ∑ (min(d, n − j) − min(d − 1, n − j)) + min(d, 1) j=1 ≤ n − 2 + 1 < m. For m < n, we have m−1 Gd (m, n) − Gd−1 (m, n − 1) = 1 + ∑ (min(d, n − j) − min(d − 1, n − 1 − j)) j=1 ≤ 1 + (m − 1) = m. This concludes the proof. 1.3.5 Variants of the sum-product problem When we replace the underlying group G with a ring R, it is natural to ask how the corresponding notions of addition and multiplication interact. We recall the following inaugural conjecture of Erd˝os and Szemer´edi. Conjecture 1.3.1. Let A ⊂ Z be finite with |A| = N. Let ε > 0. If N ≥ N0 = N0 (ε) then max(|A + A|, |A · A|) N 2−ε . This conjecture remains open. However, Erd˝os and Szemer´edi did prove a weaker version of the same principle. Theorem 1.3.7. Let A ⊂ Z be finite with |A| = N. Then there is some δ > 0 such that if N ≥ N0 we have max(|A + A|, |A · A|) ≥ N 1+δ . 23 This led to a search for the best numerical lower bounds on δ. The sequence of world records for δ is contained in Table 1.1. The latter three bounds in fact hold for any A ⊂ R. δ 1/31 1/15 1/4 3/14 1/3-ε Discovered Nathanson 1997 Ford 1998 Elekes 1997 Solymosi, 2005 Solymosi, 2008 Reference [35] [20] [16] [39] [40] Table 1.1: Bounds on δ in the sum product problem. Amid the progress on the original sum-product conjecture, several variants emerged. We have already mentioned that some of the results above apply to the real numbers. Some of the other variants include those summarized in Table 1.2. Variant Type Exotic Rings Small productset implies large sumset Small sumset implies large productset Iterated sumset or productset Simple sums and products Distinct sets Perturbed set References [3],[4],[5],[11],[13],[32],[43] [8],[13] [7] [2],[15] [8],[13] [10], [13] [1] Table 1.2: Variants of the sum product problem. In addition, some results combine two or more of these variants. For example, Theorem 1.2.3 is a combination of the first, second, fourth, and sixth variants in Table 1.2, while Theorem 1.2.4 is a combination of the first and fifth. We will now give precise statements for some examples typical of each of the above. 1) Exotic rings. While the sum-product theorem in the sense of Conjecture 1.3.1 cannot hold in the general setting due to the possible existence of subrings or other degenerate cases, by diligently avoiding such occurences Tao obtained a result which holds in 24 completely arbitrary rings [43]. There are also numerous sum-product estimates in specific settings aside from the integers, including the reals and complex numbers, and more exotic settings such as rings of matrices [11] and finite fields [4]. The precise statement of a pioneering result in the latter setting, due to Bourgain, Katz, and Tao [4] is as follows. Theorem 1.3.8. Let F = Zq for q prime, and let δ > 0. Then there is some ε(δ) > 0 such that if A ⊂ F satisfies |F|δ < |A| < |F|1−δ then we have max(|A + A|, |A · A|) δ |A|1+ε . This result was followed by several variants in a similar spirit, notably those in [2] (partially extending Theorem 1.3.8 to Zq with q composite), [5] (dealing with the case δ > 1/2), and [32] (giving an explicit bound on ε for a particular range for δ). 2) Small productset implies large sumset. If the sum-product conjecture is true, then a set of integers with a relatively small productset should have a large sumset. Chang [8] proved the following. Theorem 1.3.9. Let A ⊂ Z be finite, and suppose that |A · A| ≤ α|A| for some α. Then for every k ≥ 2 we have |kA| ≥ |A|k . (2k2 − k)kα Note that this actually addresses iterated sumsets, and proves an optimally strong dependence on |A| for fixed k. 3) Small sumset implies large productset. We can also prove results as above, with the products and sums reversed. For example, Chang [7] proved: 25 Theorem 1.3.10. Let A ⊂ C be finite, and suppose that |A + A| ≤ α|A| for some α. Then for every k ≥ 2 and ε > 0 we have |A(k) | k,α,ε |A|k−ε . 4) Iterated sumset or productset. The most basic question we can ask in this context is a version of the original sumproduct conjecture which applies to iterated set operations. Erd˝os and Szemer´edi in fact made the following conjecture. Conjecture 1.3.2. Let A ⊂ Z be finite with |A| = N. Let ε > 0 and let k ∈ N. If N ≥ N0 = N0 (ε) then max(|kA|, |A(k) |) k,ε N k−ε . This of course remains open (the case h = 2 corresponds to the standard sumproduct question). However, many of the other variants incorporate iterated sum and product sets. In addition, Bourgain and Chang have the following impressive result in the integers [2]: Theorem 1.3.11. For every b > 1 there is k ∈ N such that if A ⊂ Z then |kA| + |A(k) | > |A|b . The proof of this theorem uses prime factorisation, so it does not generalise to abitrary sets of real numbers. Recently, Croot and Hart made progress towards extending the result [15]: Theorem 1.3.12. For every k ≥ 2 and 0 < ε < ε0 (k) there is an integer n0 (ε) such that if A is a set of real numbers with |A| ≥ n0 (ε) and |A · A| ≤ |A|1+ε then |kA| ≥ |A| log(k/2) 1 2 log 2 + 2 − f h (ε) where fh (ε) → 0 as ε → 0. 26 5) Simple sums and products. Instead of considering the sumset and productset, we can consider all elements which may be expressed as a sum elements of A with all summands distinct, and similarly for products. More specifically, we denote the elements of A by a1 , ..., an , where |A| = n, and define n A+ = ∑ εi ai : εi ∈ {0, 1} i=1 A× = n ∏ aεi : εi ∈ {0, 1} . i i=1 These constructions also obey sum-product phenomena, as the following result, due to Chang [8], shows. Theorem 1.3.13. Let A ⊂ N, and denote |A| = n. Then (1/8−ε) loglog(n) log(n) |A+ | + |A× | ≥ n . 6) Distinct sets. More recently, there have been questions about sums and products of a pair of distinct sets A, B, A = B. The following three results are also due to Chang [10]: Theorem 1.3.14. Let A ⊂ Z be finite, and suppose that for some ε > 0 we have |A · A| < |A|1+ε . Then for every B ⊂ Z and for every h ∈ N we have |kA + B| > |A|k |B|(|A| + |B|)−δ(k,ε) where δ(k, ε) → 0 as ε → 0. Theorem 1.3.15. Let A ⊂ R be finite, and let ε > 0 and k ∈ N. Suppose that |A · A| < α|A| for some α = oε,k (log |A|). Then for every B ⊂ R we have |kA + B| > |A|k |B|(|A| + |B|)−ε . Theorem 1.3.16. Let A ⊂ R+ , and let ε > 0 and k ∈ N. Suppose that |A+A| ≤ α|A| 27 for some α < α(ε, k, |A|) → ∞ as |A| → ∞. Then for every B ⊂ R+ we have |Ah B| h,α,ε |A|h |B|(|A| + |B|)−ε . 7) Perturbed sets. A recently described variant of the sum product phenomenon is due to Backman, Croot, Hamel and Hart [1]. It addresses the extent to which we can nudge the products in the productset AB of two sets A and B while still being able to guarantee that a sum-product estimate will hold. We first define the perturbed productset: Definition 1.3.8. Let A ⊂ R+ , and suppose that each pair of elements of A are separated by a distance of at least 1. For each pair (a, b) ∈ A × A, let δa,b and δa,b be real numbers such that |δa,b | < |A|1−ε a |δa,b | < |A|1−ε . b Then the perturbed productset of A is the set P defined by P := {(a + δa,b )(b + δa,b ) : a, b ∈ A} With this definition, one can obtain the desired type of estimate. Theorem 1.3.17. Let 0 < ε ≤ 1, and let n0 (ε) be sufficiently large in terms of ε. Let A ⊂ R+ satisfy |A| ≥ n0 (ε), and let P be a perturbed productset of A. Then we have |P| + |A + A| 1.4 1.4.1 n1+ε/9 . log n Harmonic analysis on the group ZN and uniform sets Harmonic analysis preliminaries In this section we collect the basic definitions and identities of discrete harmonic analysis for use later in the text. 28 We will use the notation 1A to denote the characteristic function of a set A, and we will use the definition e(θ) := exp(2πiθ). When borrowing themes from probability theory, we may also use the notation E f := 1 ∑ f (x) N x∈Z N for the expected value of a function f : ZN → C, from which we obtain the expression P(A) := |A|/N = E1A (x). We will have cause to recall the following pair of definitions. Definition 1.4.1. Let f : ZN → C. Then we define the Fourier transform of f to be the function f : ZN → C given by f (ξ) := 1 ∑ f (x)e(−xξ/N). N x∈Z N Definition 1.4.2. Let f , g : ZN → C. Then we define the convolution of f and g to be the function f ∗ g : ZN → C given by f ∗ g(x) := ∑ f (y)g(x − y). y∈ZN We will frequently refer to the Fourier transform of a set A, which simply means the transform of its characteristic function, 1A . The usefulness of these definitions in the present discussion is that the Fourier transform of a set A ⊂ ZN provides a measure of the degree of structure of A; this relationship will be discussed further in Section 1.4.2. On the other hand, the convolution 1A ∗ 1B for A, B ⊂ ZN , is supported on the sumset A + B, and in fact counts representations of elements of the sumset: Lemma 1.4.1. Let A, B ⊂ ZN . Then for every x ∈ ZN we have 1A ∗ 1B (x) = #{(a, b) ∈ A × B : a + b = x} Much of the versatility of the Fourier transform is given by the following three 29 key properties. Lemma 1.4.2. Let f , g : ZN → C. Then the following identities hold: (i) Fourier Inversion: f (x) = ∑ f (ξ)e(xξ/N) ξ∈ZN (ii) Convolution Identity: f ∗ g(ξ) = N f (ξ)g(ξ) (iii) Parseval’s Identity: ∑ f (ξ) g(ξ) = N −1 ∑ f (x)g(x). x∈ZN ξ∈ZN In what follows, we will also be considering the L p -norms of a bounded function f : ZN → C, given by 1/p f p := ∑ | f (x)| p when 0 < p < ∞, x∈ZN f ∞ := sup | f (x)|. x∈ZN When attempting to determine bounds in terms of these norms, we will make use of H¨older’s inequality: for f , g : ZN → C and all 1 ≤ p, q ≤ ∞ such that 1p + q1 = 1, we have fg 1.4.2 1 ≤ f p g q. Pseudorandomness and uniformity A motivating theme in the proof of Theorem 1.2.1 is that the primes are in some sense randomly distributed. In this section, we discuss what it means for a set to be random, and then address how one might measure the degree of randomness, or uniformity, of a set which is in actuality entirely determined. It has been a recurring theme in harmonic analysis that some deterministic sets are uniform: in other words, they are structured similarly to the expected shape of a set constructed through the following probabilistic procedure. 30 Definition 1.4.3. Let B ⊂ ZN . A random subset A ⊂ B is an element of a discrete sample space Ω = 2B , where the probability measure on this sample space is a Bernoulli distribution with probability 0 < p < 1; that is, P(A) = p|A| (1 − p)|B|−|A| . One can visualize this definition by imagining that A is constructed through |B| flips of a biased coin which lands with heads up with probability p. That is, we add the element n to A if and only if the result of the nth flip is heads. This agrees with our intuition that a random set should be a set whose elements are chosen randomly. Observe that the event x ∈ A occurs with probability p for each x ∈ ZN . Moreover, note that the random variable |A| has a binomial distribution: P(|A| = k) = |B| k p (1 − p)|B|−k . k This allows us to conclude that the expected size of a random set A is E(|A|) = pN with variance Var(|A|) = N p(1 − p). The importance of random sets in arithmetic combinatorics is that they will, with high probability, have minimal structure, either arithmetic or geometric. As an expression of this idea, we might expect a random set to contain many different point configurations, for example arithmetic progressions of arbitrary length. Kohayakawa, Łuczak, and R¨odl [33] proved the following version of this statement. Theorem 1.4.1. Let 0 < α ≤ 1 and let n ∈ N. There is a constant C = C(α) such that if S is a random subset of [n] whose elements are selected with probability √ p ≥ C/ n, then the statement every set A ⊂ S with |A| ≥ α|S| contains an arithmetic progression occurs with probability which tends to 1 as n → ∞. 31 A version of this theorem in the setting of groups Z p for p a prime was given by Tao and Vu [44], using a proof modified from the techniques they used to find arithmetic progressions in the primes [27], [29]. Another example of random sets having minimal structure was recently given by Hamel and Łaba, who proved the following: Theorem 1.4.2. Suppose that S is a random subset of ZN such that the events x ∈ S, where x ranges over ZN , are independent and have probability p = p(N) ∈ (CN −θ , 1], where 0 < θ < 1/140. Then for every β < α, the statement for every set A ⊂ S with |A| ≥ α|S|, we have |A + A| ≥ βN is true with probability 1 − oα,β (1) as N → ∞. In order to apply our heuristic that random sets tend to be unstructured to uniform deterministic sets, we need to somehow quantify the “randomness” of a set. Our mechanism for doing this will be the object of the following definition, which can be found, for example, in [44]. Definition 1.4.4. Let f : ZN → C. Then the linear bias of f , denoted f u2 , is given by f u2 := sup | f (ξ)| = f ∞. ξ We can now state what we mean for a deterministic set to be uniform, or, synonymously, pseudorandom. Roughly speaking, such sets are exactly those which have no large Fourier coefficients except perhaps when the frequency variable vanishes. Definition 1.4.5. Let A ⊂ ZN , and let 0 < η ≤ 1. Then A is η-pseudorandom (or just pseudorandom, for short) if 1A − P(A) u2 ≤ η. Of course, we can apply the above definition to any function f : ZN → C to define what it means for a function to be pseudorandom, by replacing 1A by f and P(A) by E f . Note that, when f is normalized to have mean 1, we can also rewrite the definition as | f (ξ) − 1ξ=0 | ≤ η ∀ξ ∈ ZN . 32 A discussion of how this definition is applied to the case of prime numbers is offered in Section 1.5.2. 1.5 1.5.1 Number theoretic preliminaries Tools from analytic number theory In this section, we introduce some basic notions and results from analytic number theory which will aid in the proof of Theorem 1.2.1. For integers m and n, we use the notation m|n to denote the statement that m divides n, that is that there is an integer k such that n = km. We will use the notation n ≡ k (mod m) to denote the property that n is congruent to k modulo m, or in other words the property that m|(n − k). Lastly, we will use (m, n) to denote the greatest common divisor of m and n. Throughout this thesis, we will use P to denote the prime numbers, that is, those natural numbers p which satisfy the property that whenever p|mn for integers m and n, p must divide one of m or n. The Fundamental Theorem of Arithmetic then states that each integer admits a unique factorisation into primes, up to order of the factors. There are many questions, solved and unsolved, with regards to the distribution of primes; for example we have the following basic properties. Theorem 1.5.1. There are infinitely many primes. Theorem 1.5.2. For every integer N, there are consecutive primes p and q with the property that |p − q| > N. The proofs of both of the above results are straightforward, and can be found in texts on elementary number theory. A fundamental distributional result in analytic number theory is the Prime Number Theorem, which counts the number of primes up to each real number x; this number is denoted by π(x). 33 Theorem 1.5.3. For every x ≥ 2, we have π(x) = x x +O . log(x) log2 (x) If we believe that the primes are uniformly distributed, then we should expect that they would not prefer any particular residue class modulo m, for any natural number m. This is quickly seen to not be the case, as we cannot have p ≡ k (mod m) for any prime p and any integer k such that (k, m) > 1, aside from the trivial case p = m, k ≡ 0. As a particular instance of this fact, we see that there are no even primes other than 2. However, if we focus only on those residue classes whose representatives k satisfy (k, m) = 1, it is possible to see that the primes are in fact uniformly distributed throughout them. We must first introduce some notation. Definition 1.5.1. The Euler totient function ϕ : N → N is the function given by ϕ(n) = #{x < n : (x, n) = 1}. That is, ϕ(n) counts the number of residue classes less than n whose elements are all relatively prime to n. We denote by π(x; q, a) the number of primes less than or equal to x which are congruent to a modulo q. The Prime Number Theorem for Arithmetic Progressions is then as follows. Theorem 1.5.4. For every x ≥ 2, q ∈ N, and a ∈ N such that (a, q) = 1, we have π(x; q, a) = x x +O . ϕ(q) log(x) log2 (x) Note that we can rewrite the estimate above as π(x; q, a) = π(x) 1 1 +O ϕ(q) log(x) , which is an expression of the uniform distribution of the primes among the reduced residue classes modulo q. 34 It will be useful to know some of the properties of ϕ. To begin with, we have the following useful formula. Lemma 1.5.1. For any natural number n we have ϕ(n) = n ∏ 1 − p|n 1 . p Proof. We begin by noting that ϕ is a multiplicative function: if (m, n) = 1, the natural numbers smaller than and relatively prime to mn are exactly the integers kl where k < m, (k, m) = 1, l < n, and (l, n) = 1. It follows that if n has prime power decomposition n = pa11 ...pas s then ϕ(n) = ϕ(pa11 )...ϕ(pas s ). (1.5.1) Now, if p is a prime and a is natural, the natural numbers smaller than or equal to pa which share a factor with pa are exactly those which have p as a divisor. That is, p, 2p, 3p, ..., (pa−1 − 1)p, pa−1 p. We therefore compute that φ(pa ) = pa − pa−1 = pa 1 − 1 . p The result now follows by combining this with Equation 1.5.1. It is clear from the above argument and the definition that ϕ(n)/n ≤ 1 − 1/n, and that these “world records” are obtained at the primes p. A lower bound is more difficult to obtain, and it is the object of the next lemma. 35 Lemma 1.5.2. Let n ≥ 3. Then 1 ϕ(n) ≥ e−γ + O(1/ log log(n)) . n log log(n) where γ ≈ 0.577215665 is Euler’s constant. This holds with equality for integers of the form ∏ p≤x p for any positive real number x. The proof of the above bound is surprisingly lengthy, and relies on estimates of Chebyshev and Mertens. It can be found in, for example, [34]. Lastly, in Section 1.5.2 we shall briefly need the notation µ for the M¨obius function, that is 1, if x = 1, µ(x) = (−1)r , if x is the product of r distinct primes, 0, if x is divisible by a perfect square larger that 1. 1.5.2 Transference properties of the primes This, the last of the introductory sections, will discuss a sequence of results, due to Green, which will be needed in Chapter 2. These results form the precise manner in which we consider the primes to be uniform. We will try to convey the main ideas of the proofs, while omitting the (rather technical) details. The interested reader may find the full discussion in [27]. We will let A be a subset of the primes P , and we will suppose that A has positive upper relative density. That is, |A ∩ [1, n]| ≥δ>0 | n→∞ P ∩ [1, n]| lim sup Throughout the remainder of this section, we will use the notation An = A ∩ [1, n], and similarly for other sets. Our first step will be to remove some of the structure of the primes by applying the W -trick of Green [27] and Green-Tao [29]. We will follow Green’s original formulation of this method. 36 We will now consider n ∈ N to be fixed such that |An |/|Pn | ≥ δ/2, and let m= ∏p p≤W for some number W = W (n) satisfying W → ∞ as n → ∞. To simplify the discussion, we will assume that W ≈ log log(n). We now have the following definition. Definition 1.5.2. Let n, W , and m be as above, and let b be a reduced residue class modulo m. Then the W -tricked primes (up to N in the residue class b modulo m) are the set Pb,m,N given by Pb,m,N = {x ≤ N : mx + b is prime}. Remark 1.5.1. It is common to use the notation W for m and a lower case w in the place of what we have labelled W . We will maintain Green’s original convention for consistency with Chapter 2. The key property of Pb,m,N is that its elements need not be odd, and in fact need not be restricted to any particular residue classes modulo k, for any integer k whose prime factors all divide m. In other words, Pb,m,N is a rescaled copy of the primes congruent to b modulo m, with some of the structure removed. We continue by introducing a function λb,m,N : Pb,m,N → R, also from [27]. Definition 1.5.3. Let n, W , m, and b be as above. The modified von Mangoldt function is the function λb,m,N : Pb,m,N → R by λb,m,N (x) = ϕ(m) mN log(mx + b) if x ≤ N and mx + b is prime, 0 otherwise. We prefer to think of An as a subset of ZN ; the following lemma, proved in Section 2.3, allows us to do so, after restricting to those elements of A congruent to b modulo m. We denote this set by A(b) , and the set of primes congruent to b 37 modulo m by P (b) . Lemma 1.5.3. Let N ∈ (2n/m, 4n/m], and let AN = m−1 (An − b) ∩ {1, . . . , N} for b ∈ G. Then ∑ λb,m,N (x) ≥ x∈AN (b) δb , 16 (b) where δb = |An |/|Pn |. We now interpret ν := Nλb,m,N as a measure on ZN , and we let f := N1AN ν be the restriction of ν to AN . Working in ZN allows us to use the Fourier analytic techniques of Section 1.4. In particular, we would like to use f in place of the characteristic function in the definition of pseudorandomness, Definition 1.4.5. However, knowing nothing about the set A other than that it is relatively dense in the primes, it is not clear that we can do this directly. On the other hand, motivated by Theorem 2.1.1, we might hope to be able to use pseudorandomness majorizing measure λb,m,N instead. In order to do so, we need to show that λb,m,N itself is pseudorandom. In other words, we need to compute an upper bound on |λb,m,N |. Doing so encompasses a large portion of [27]. We will now summarise the argument. This requires that we introduce an alternative definition of the Fourier transform, this time on the group Z. 1 (Z). Definition 1.5.4. Let f : Z → C, f ∈ function f˜ : T → C given by f˜(θ) = Then the Fourier transform of f is the ∑ f (n)e(nθ). n∈Z Fourier inversion takes on the form Z f (n) = f˜(θ)e(−nθ)d θ. T ˜ b,m,N . The pseudorandomness properties of ν will follow from asymptotics for λ For k satisfying (k, q) = 1, we denote the multiplicative inverse of k modulo q by k. In the following formula, we suppose for technical reasons that we have fixed 38 constants s > 2, A = 4/(s − 2), and B = 2A + 20. We also employ the notation τ(θ) for the exponential sum τ(θ) = Lemma 1.5.4. If |θ − a/q| ≤ (log N)B qN 1 ∑ e(nθ). N n≤N for some q ≤ (log N)−B and (m, q) = 1, ˜ b,m,N (θ) = µ(q) e(− abm )τ θ − a + O((log N)−A ). λ ϕ(q) q q Otherwise, we have ˜ b,m,N (θ) = O((log N)−A ). λ The proof of Lemma 1.5.4 uses the Hardy-Littlewood circle method. The unit circle T is divided into two disjoint sets, the major arcs and minor arcs. Specifically, for a, q ∈ N such that (a, q) = 1 and a/q is in lowest terms with q ≤ (log(N))−B , we define the major arc Ma,q by Ma,q = θ ∈ T : θ − (log N)B a ≤ q qN . The minor arcs are the complement of the major arcs, m = T\ [ Ma,q , where the (disjoint) union is over all a, q for which the major arcs are defined. ˜ b,m,N (θ) splits into cases depending on whether From here, the computation of λ θ lies in the major arcs or the minor arcs; in fact, Green initially computes the (Q) asymptotics for functions λb,m,N , where Q is an integer parameter, whose Fourier transforms are near to λb,m,N in L∞ . (Q) On the major arcs, one is able to use the uniform distribution of λb,m,N along long arithmetic progressions with small common difference to obtain the main term of the asymptotic, to within a small error. On the minor arcs, it is shown that the transform has small magnitude. Once these estimates are in hand, it is possible to employ arguments from harmonic analysis to prove the following, which we refer to as the restriction theorem for primes. 39 Theorem 1.5.5. Let p > 2. Then for every g : Pb,m,N → C we have gλb,m,N p p N −1/p g 2 . Theorem 1.5.5 is in the same theme as the restriction phenomena in harmonic analysis. It says that the operation of taking the Fourier transform of a measure supported on the (W -tricked) primes is bounded from L2 (Z) to L p (T). From Lemma 1.5.4 and Theorem 1.5.5, it is possible to produce the following transference properties of the primes, which we will require in Chapter 2. Lemma 1.5.5. For N and W sufficiently large there is some D > 0 such that ν u1 ≤ 2 log logW /W and ν(0) ≤ 1 + O((log N)−D ). In other words, the first bound above says that λb,m,N is 2 log logW /W -pseudorandom, provided N and W are sufficiently large. This follows by writing out the asymptotic ˜ b,m,N (r/N) from Lemma 1.5.4. for λb,m,N (r) = λ In addition to the pointwise bound on the Fourier transform in Lemma 2.3.2, it is helpful to have to bound the s s bounds on f . Using a result of Marcinkiewicz and Zygmund ˜ b,m,N and applying the norm of λb,m,N in terms of the Ls norm of λ Restriction Theorem for Primes to N1A we have: Lemma 1.5.6. Let s > 2. Then there is a constant C(s) such that f s ≤ C(s). (1.5.2) To conclude this section, we complete the proof of the Green-Tao transference principle (Lemma 2.3.4), which allows us to decompose our restricted measures f = N1A λb,m,N into two parts, one bounded, and one uniform. Part (i) of the following theorem is proved in Chapter 2; we will focus our current efforts on parts (ii), (iii), and (iv). 40 Lemma 1.5.7. Suppose that f = f (b) and ν = ν(b) are as above. Let s > 2 and let ε0 > 0. Define f1 (x) := E( f (x + y1 − y2 ) : y1 , y2 ∈ B0 ), where B0 := {x : |e−2πixξ/N − 1| ≤ ε0 for all ξ ∈ Λ0 }, Λ0 := {ξ : | f (ξ)| ≥ ε0 }. Define f2 (x) := f (x) − f1 (x). Then for every σ > 0, assuming that N is sufficiently large, and W is sufficiently large depending on ε0 , we have (i) 0 ≤ f1 ≤ 1 + σ, (ii) E f1 = E f , (iii) f2 (iv) fi ∞ s ≤ ε0 /16 and f1 ∞ 1, 1 for i = 1, 2. Proof. (ii): We have E f1 = = 1 1 f (x + y1 − y2 ) ∑ N x∈ZN |B0 |2 y1 ,y∑ 2 ∈B0 1 NE f N|B0 |2 y1 ,y∑ 2 ∈B0 = Ef. (1.5.3) (iii): We compute the Fourier transform of f1 to be f1 (ξ) = 1 ∑ Ey1 ,y2 ∈B0 f (x + y1 − y2 )e(−xξ/N) N x∈Z N = 1 ∑ Ey1 ,y2 ∈B0 f (x + y1 − y2 )e(−ξ(x + y1 − y2 )/N)e(ξy1 /N)e(−ξy2 /N) N x∈Z N = f (ξ)|Ey∈B0 e(−ξy/N)|2 . (1.5.4) It then follows that we also have f2 (ξ) = f (ξ) 1 − |Ey∈B0 e(−ξy/N)|2 . 41 (1.5.5) From Equation 1.5.4 and Lemma 1.5.6, we have immediately that f1 ∞ ≤ f ∞ s 1. Meanwhile, for ξ ∈ / Λ0 , we have | f2 | ≤ | f (ξ)| < ε0 . (1.5.6) For ξ ∈ Λ0 , we use Equation 1.5.5, the observation that |1 − e(−ξy/N)| ≤ ε for every y ∈ B0 , and Lemma 2.3.2 to obtain | f2 (ξ)| ≤ | f (ξ)| 1 − |Ey∈B0 e(−ξy/N)|2 ≤ | f (ξ)|(2ε − ε2 ) ≤ 2ε0 |E f | ≤ 2ε0 |Eν| ≤ 2ε0 |ν(0)| ε0 . (1.5.7) Combining Equation 1.5.6 and Equation 1.5.7 we obtain the ∞ bound on f2 . (iv): These bounds follow automatically from the fact that for i = 1, 2 we can apply Equation 1.5.4 and Equation 1.5.5 (respectively) to get fi s ≤ f from Lemma 1.5.6. 42 s s 1 Chapter 2 On sums of sets of primes with positive relative density In this, the first of the research chapters, our main goal will be to prove Theorem 1.2.1 and Theorem 1.2.2 (restated below as Theorem 2.1.2 and Theorem 2.1.3, respectively). We begin with a short introduction, which reviews and expands on some of the points from Chapter 1 which are most pertinent to the present discussion. In particular, we will briefly describe a pair of examples which suggests that the bounds in the main theorems may not be optimal. This is followed by the reduction of a finite version of Theorem 1.2.1 to a problem in Z∗N using the transference properties of the primes. In the process of solving this new problem, the proof of Theorem 1.2.2 is given. The content of this chapter is taken from [14], and is joint work with Mariah Hamel. Acknowledgements: We are extremely grateful to Ernie Croot for suggestions in proving Theorem 2.1.3. We thank Izabella Łaba, Neil Lyall and Akos Magyar for their support and advice. 2.1 Introduction In recent years there has been much progress made toward understanding additive properties of the primes. One of the first important structural results on the primes is due to Van der Corput [46], who showed that the primes contain infinitely many 43 three term arithmetic progressions. More recently, Green [27] proved a version of Roth’s theorem, by showing the existence of three term arithmetic progressions in subsets of the primes which have positive relative density. In 2004 Green and Tao [29] proved the celebrated theorem that the primes contain arbitrarily long arithmetic progressions. The strategy developed by Green and Green-Tao is to embed the primes in a ‘random’ set where they have positive relative density and to apply a relative version of Szemeredi’s theorem which holds in this setting. Extending results from additive number theory to the setting of random sets with asymptotic density 0 was first considered by Kohayakawa-Łuczak-R¨odl [33] who proved a variant of Roth’s theorem. An alternate proof of this version of Roth’s theorem is proved in Tao-Vu [44] and lends itself to adaptation in the primes (similar to Green’s proof of Roth’s theorem in the primes and used recently in [45]). This method of embedding the primes in a ‘random’ set suggests that one should be able to prove other results which are known in a random setting to that of the primes. A result of Hamel and Łaba [31] says that if A is a subset of a random set in ZN := Z/NZ with positive relative density, then A + A must have positive density in ZN . Theorem 2.1.1. Suppose that S is a random subset of ZN such that the events x ∈ S, where x ranges over ZN , are independent and have probability p = p(N) ∈ (CN −θ , 1], where 0 < θ < 1/140. Then for every β < α, the statement for every set A ⊂ S with |A| ≥ α|S|, we have |A + A| ≥ βN is true with probability 1 − oα,β (1) as N → ∞. The main result of this chapter is a version of Theorem 2.1.1 where A is replaced by a relatively dense subset of the primes, which take the role of the random set S. We should note that it is known that if P is the set of primes then the density of P + P in the natural numbers is 1/2 (see, for example, [49]). Theorem 2.1.2. Let A be a subset of the primes with positive relative density 0 < δ0 < 1. Then there exist absolute constants C1 and C2 such that A + A has positive upper density at least 2/3 (log log(1/δ ))1/3 0 C1 δ0 e−C2 (log(1/δ0 )) 44 (2.1.1) in the natural numbers. Remark 2.1.1. For δ0 = 1, a modification of our argument can be used to show that A + A has upper density 1/2 (in particular, one can use the Chinese remainder theorem to prove a corresponding version of Theorem 2.1.3 below). For sufficiently small values of δ0 , the constant C1 can be absorbed into the exponential term. For larger values of δ0 we can use the boundedness of the argument of the exponential near δ0 = 1 to rewrite the density as C1 δ0 for a new value of C1 . While it is not expected that this bound is best possible, the following example shows that it is not possible to extend Theorem 2.1.2 to the the analogous conclusion of Theorem 2.1.1. Let ϕ denote the Euler totient function, that is, for an integer n, ϕ(n) is the number of integers less than n which are relatively prime to n. Let m be the product of the first t primes and define A := {p ∈ P : p ≡ 1(mod m)}. Let An denote the set of elements of A which are less than or equal to n. The prime number theorem for arithmetic progressions implies that |An | = n n . +O ϕ(m) log n log2 n Hence, if n is sufficiently large, we have |An | ≥ n . 2ϕ(m) log n It follows by the prime number theorem that the relative density of A in the set of primes is at least δ := 1/2ϕ(m). On the other hand, the definition of A implies that An + An ⊂ {s ∈ N : s ≡ 2(mod m)}. Using estimates of Chebyshev and Mertens (for example, see Theorem 8.2 and 45 Theorem 8.8 in [34]) we see that m ∼ ϕ(m) log log ϕ(m), and hence |An + An | ≤ 2n δ ∼ n. m log log(1/δ) We also remark that it is possible to replace the bound in Equation 2.1.1 with the weaker bound of δ2 using a much simpler argument which uses Cauchy-Schwarz and the Brun sieve. One important difference between proving Theorem 2.1.1 and Theorem 2.1.2 is that while S is defined to be a random set in Theorem 2.1.1, the set of primes is not randomly distributed. For example, there is only one prime which is divisible by 2, and if x = 2 is prime then the probability that x + 1 is prime is zero. The strategy employed by Green and Green-Tao to handle this difficulty is to consider the primes modulo m where m is the product of small primes. They then pick one residue class where A ⊂ P has large density and find an arithmetic progression contained in that residue class. In order to bound the density of A + A we are not able to restrict the arguments to one residue class. To prove Theorem 2.1.2 we will need a way to consider all residue classes for which A has large relative density. The relevant residue classes are contained in the multiplicative subgroup of the integers modulo N, which we will denote by Z∗N . The result that we need is contained in the proof of the following theorem. Theorem 2.1.3. Let 0 < α < 1. Assume that m ∈ Z+ is sufficiently large depending on α. If B ⊂ Z∗m satisfies |B| ≥ αϕ(m) then there are absolute constants C1 and C2 such that 2/3 (log log(1/α))1/3 |B + B| ≥ C1 αe−C2 (log(1/α)) m. It is not a coincidence that the conclusions of Theorem 2.1.2 and Theorem 2.1.3 contain the same exponential factor. In fact, it will be evident in the proof of Theorem 2.1.2 that this factor comes about entirely from the structure of Z∗m for a suitable modulus m. Furthermore, the following example, in conjunction with Freiman’s theorem (see, for example, Theorem 5.33 in [44]), suggests that the 1/ log log(1/δ) factor obtained in the previous construction may in fact be sharp: Suppose m = p1 · · · ps , where p1 < · · · < ps are the first s primes. Then Zm ∼ = 46 Z p1 × · · · × Z ps . Let B ⊂ Zm be given in this representation by B := {1} × · · · × {1} × (Z pt+1 \ {0}) × · · · × (Z ps \ {0}). Here B is a low dimensional generalized arithmetic progression. Then, using the notation of Theorem 2.1.3, we can directly compute α = 1/ϕ(p1 . . . pt ) from the fact that ϕ(p) = p − 1 for a prime p and the fact that ϕ is multiplicative. In addition, computing B+B and using the same estimates as in the previous example, we obtain |B + B| = 2.2 m α ∼ m. p1 . . . pt log log(1/α) Preliminaries and an outline of the argument Throughout this chapter A will be a subset of the primes, An will be a subset of (b) the primes which are less than or equal to n and An will be those elements of An which are congruent to b modulo m, where m is the product of the primes less than or equal to some sufficiently large parameter W . We use |A| to denote the cardinality of the set A and define A + A := {a + a : a, a ∈ A}. We write C, C1 , or C2 to denote an absolute constant, although the exact value of any of these may differ between any two different expressions. For real-valued functions f and g, we write f g to mean | f | ≤ C|g|. As previously noted, we write ZN to denote the cyclic group Z/NZ and Z∗N := {x ∈ ZN : (x, N) = 1} to denote the multiplicative subgroup of integers modulo N. If f : ZN → C then we define the expectation of f to be E( f ) := 1 ∑ f (x). N x∈Z N We define the normalized Fourier transform f (ξ) := 1 ∑ f (x)e(−xξ/N) N x∈Z N 47 where e(α) := exp(2πiα). For two functions f , g : ZN → C we define the convolution f ∗ g(x) := ∑ f (y)g(x − y). y∈ZN We also define the L p norm f p := ∑ | f (x)| p 1/p x∈ZN and the L∞ norm f ∞ := sup | f (x)|. x∈ZN We will use Plancherel’s identity which says that ∑ f (ξ) g(ξ) = N −1 ∑ f (x)g(x), x∈ZN ξ∈ZN an identity for convolution f ∗ g(ξ) = N f (ξ)g(ξ) and the Fourier inversion formula f (x) = f (ξ)e(xξ/N). ∑ ξ∈ZN We will say that a function f : ZN → R≥0 is pseudorandom if f (ξ) − 1ξ=0 ∞ ≤η for some 0 < η ≤ 1. An outline of the argument is as follows: In Section 3, we begin by partitioning A into residue classes modulo m, where m is the product of small primes. We then use techniques introduced in [27] to embed each residue class on which A is concentrated into ZN for N ∼ n/m. In this setting, we are able to utilize the concept of pseudorandomness to decompose a modified characteristic function of 48 A on each partition (simultaneously) into a bounded part and a linearly uniform part. Modifying the arguments used to prove Theorem 2.1.1, we show that the sumset of the images of any two congruence classes of A has comparably large density in ZN . In Section 4, we develop a moment estimate needed to prove Theorem 2.1.3. In particular, in Proposition 2.4.1, we prove a kth moment estimate of the representation function which bounds the number of ways to write an element of Zm as the sum of two elements in B. An application of H¨older’s inequality allows us to use the kth moment estimate to prove Theorem 2.1.3. In Section 5, we combine the results of Sections 3 and 4 with an application of H¨older’s inequality to complete the proof of a finite version of Theorem 2.1.2. 2.3 Sumsets and uniformity of the primes in residue classes The main goal of this section will be to prove Proposition 2.3.1 below. Before stating Proposition 2.3.1 we will state a finite version of Theorem 2.1.2 which will allow us to introduce necessary notation. Let 0 < δ0 < 1. Let A be a subset of the primes with positive relative density δ0 . This means that lim sup n→∞ |A ∩ Pn | = δ0 , |Pn | |A∩Pn | |Pn | and hence there exist infinitely many n so that ≥ δ0 /2. Theorem 2.1.2 will then follow from a finite version, where δ := δ0 /2: Theorem 2.3.1. Let An ⊂ Pn satisfy |An | ≥ δ|Pn |. Then there exist absolute constants C1 and C2 such that if n ≥ n0 (δ) then 2/3 (log log(1/δ))1/3 |An + An | ≥ C1 δe−C2 (log(1/δ)) n. Let ε > 0 be a small parameter and let W be sufficiently large depending on δ and ε, and satisfying W log log n. Set m= ∏ p. p≤W 49 We begin by partitioning An into congruence classes modulo m. More specifically, let (b) An = {a ∈ An : a ≡ b (mod m)} , and Pn(b) = {p ∈ Pn : p ≡ b (mod m)} . Define (b) δb = |An | (b) |Pn | . (b) For those sets An for which we have a large relative density in Pn , we say that b is good, and we define the set of good residue classes to be G = {b ∈ Z∗m : δb ≥ δ/2}. Combining the methods of Green [27] on three term arithmetic progressions in subsets of the primes with the methods used to prove Theorem 2.1.1 we are able (b ) (b ) to show that for any pair of good residue classes b1 and b2 the sumset An 1 + An 2 is dense in the progression {0 ≤ x ≤ 2n : x ≡ b1 + b2 (mod m)}. Summing over pairs of residue classes and being careful not to count multiplicities, we have the following: Proposition 2.3.1. For every x ∈ G + G, let ∆x = max (b,b )∈G×G b+b =x δb + δb 2 ≥ δ/2. Then for every ε > 0 |An + An | ≥ ∑ x∈G+G (∆x − ε) n . m (2.3.1) Remark 2.3.1. As we will see in the proof of Lemma 2.3.4, we will require m to be a rapidly increasing function as δ and ε go to 0. This is the reason that we must gain control on |G + G| in order to prove Theorem 2.3.1. In the remainder of this section, we will prove Proposition 2.3.1. This requires 50 several lemmas. The first lemma, which was proved by Green ([27], Lemma 6.1), allows us to (b) consider An as a subset of ZN for N ∼ n/m. For those b for which the density δb is large, we will then construct a collection of simultaneously pseudorandom measures which majorize modified characteristic functions of the images in ZN (b) of the sets An . Working in ZN we then use Fourier analytic techniques. As our notation differs slightly from that used by Green in [27], we include a proof for completeness. We recall Green’s modified von Mangoldt function λb,m,N : Z+ → R, defined as ϕ(m) mN λb,m,N (x) = log(mx + b) if x ≤ N and mx + b is prime, 0 otherwise. (b) Lemma 2.3.1. Let N ∈ (2n/m, 4n/m], and let AN = m−1 (An − b) ∩ {1, . . . , N} for b ∈ G. Then λb,m,N (x) ≥ ∑ (b) x∈AN δb . 16 Proof. By the prime number theorem we have log x ≥ ∑ ∑ (b) x∈An x≥n3/4 1A(b) (x) log x n δb n − n3/4 log(n3/4 ) ϕ(m) log n 3 δb n 3 − n3/4 log n 4 ϕ(m) 4 δb n 4ϕ(m) ≥ = ≥ for n sufficiently large. Performing a change of variables x → mx + b we obtain ∑ x≤N mx+b prime 1A (b) (x) log(mx + b) ≥ N 51 δb n . 4ϕ(m) By definition of N, λb,m,N (x) ≥ δb n/4mN ≥ δb /16. ∑ (b) x∈AN (b) (b) (b) Taking AN ⊂ ZN we notice that |AN | = |An | and (b ) (b ) (b ) (b ) |An 1 + An 2 | ≥ |AN 1 + AN 2 | (2.3.2) for any b1 , b2 ∈ G. We now define f (b) (x) := N1A (b) (x)λb,m,N (x), N and ν(b) (x) := Nλb,m,N (x). From the above lemma, we note that E f (b) ≥ δb /16. Such functions were first defined by Green in [27] where a three term arithmetic progression was located (b) in a fixed residue class b where An had large relative density. The function f is defined so that it has large expectation and ν is pseudorandom. We require the following two lemmas of Green ([27], Lemma 6.2 and Lemma 6.6) which express the pseudorandom properties of primes: Lemma 2.3.2. For N and W sufficiently large there is some D > 0 such that ν(b) (0) ≤ 1 + O((log N)−D ) and sup |ν(b) (ξ)| ≤ 2 log logW /W. ξ=0 Lemma 2.3.3. Let s > 2. Then there is a constant C(s) such that f (b) s ≤ C(s). 52 (2.3.3) In order to prove Proposition 2.3.1 we will show that if b1 , b2 ∈ G then |{x ∈ ZN : ( f (b1 ) ∗ f (b2 ) )(x) > 0}| ≥ δb1 + δb2 − ε N. 2 (2.3.4) (b ) (b ) Since f (b1 ) ∗ f (b2 ) is supported on AN 1 + AN 2 , assuming Equation 2.3.4 implies that the size of this sumset must be large. In this case, by Equation 2.3.2, we must have (b ) δb1 + δb2 −ε N 2 δb1 + δb2 n −ε . 2 m (b ) |An 1 + An 2 | ≥ ≥ (b ) (b ) (b ) (b ) Noticing that An 1 + An 2 is disjoint from An 3 + An 4 provided b1 + b2 = b3 + b4 proves Proposition 2.3.1. It is therefore sufficient to prove Equation 2.3.4. Equation Equation 2.3.4 follows, with modifications, from the arguments in [31]. These arguments rely on a Fourier-analytic decomposition of Green [27] and Green-Tao [29], which as stated, appears in [28] [see Proposition 5.1] and is also contained in [44] [see Theorem 10.20]. In particular the functions f (b) (b) (b) are decomposed as f1 + f2 (b) where f1 (b) is bounded and f2 is unbounded but ‘uniform’. Lemma 2.3.4. Suppose that f = f (b) and ν = ν(b) are as above. Let s > 2 and let ε0 > 0. Define f1 (x) := E( f (x + y1 − y2 ) : y1 , y2 ∈ B0 ), where B0 := {x : |e−2πixξ/N − 1| ≤ ε0 for all ξ ∈ Λ0 }, Λ0 := {ξ : | f (ξ)| ≥ ε0 }. Define f2 (x) := f (x) − f1 (x). Then for every σ > 0, assuming that N is sufficiently large, and W is sufficiently large depending on ε0 , we have (i) 0 ≤ f1 ≤ 1 + σ, (ii) E f1 = E f , (iii) f2 (iv) fi ∞ s ≤ ε0 /16 and f1 ∞ 1, 1 for i = 1, 2. 53 Proof. The proofs of (ii), (iii) and (iv) follow as in [28], while we reiterate the proof of (i) here. In order to bound f1 we begin by using Fourier inversion to show that 0 ≤ f1 (x) = 1 f (x + y1 − y2 ) |B0 |2 y1 ,y∑ 2 ∈B0 ≤ 1 ν(x + y1 − y2 ) |B0 |2 y1 ,y∑ 2 ∈B0 = 1 ξ(x + y1 − y2 ) ν(ξ)e ∑ ∑ 2 |B0 | y1 ,y2 ∈B0 ξ∈Z N N = ∑ ξ∈ZN ≤ ∑ ξ∈ZN 1 ν(ξ)e (ξx/N) |B0 |2 1 |ν(ξ)| |B0 |2 2 ∑ e (−ξy/N) y∈B0 2 ∑ e (−ξy/N) . y∈B0 We continue by applying Lemma 2.3.2 and Plancherel’s identity to show that is ≤ |ν(0)| + ∑ ξ∈ZN 2 log logW 1 W |B0 |2 ≤ 1 + O (log N)−D + 2 ∑ e (−ξy/N) y∈B0 2 log logW N 2 ∑ 1B0 (ξ) W |B0 |2 ξ∈Z N 2 log logW N = 1 + O (log N)−D + W |B0 | 2 log logW N = 1+O . W |B0 | Using the pigeonhole principle, there is a constant c > 0 so that |B0 | ≥ (cε0 )|Λ0 | N. Also, ∑ | f (ξ)|s + εs0 |Λ0 | ≤ C(s)s ξ∈Λ0 54 2 where C(s) is given by Lemma 2.3.3, so |Λ0 | ≤ (C(s)/ε0 )s . Therefore 0 ≤ f1 (s) ≤ 1 + O log logW s W (cε0 )(C(s)/ε0 ) . The bound now follows since W is sufficiently large in terms of ε0 . Remark 2.3.2. In the following we will see that we must take ε0 to be smaller than δ4 ε6 . Combining this with the fact that we need the error term in the final equation of the above proof to be bounded, we see that m must increase rapidly as δ and ε approach 0, as mentioned in the remark following Proposition 2.3.1. Lemma 2.3.5. Suppose that f , g : ZN → C are functions so that E( f ) = α, E(g) = β and which have the property that they are majorized (respectively) by pseudorandom functions ν, µ : ZN → C, that is, 0 ≤ f (x) ≤ ν(x) and 0 ≤ g(x) ≤ µ(x) for every x ∈ ZN . Then for every ε > 0 |{x ∈ ZN : ( f ∗ g)(x) > 0}| ≥ α+β − ε N. 2 (2.3.5) Proof. Without loss of generality, assume that 0 < α ≤ β and let σ be a parameter which satisfies 0 < σ < ε/10. We decompose f = f1 + f2 and g = g1 + g2 as in Lemma 2.3.4, with ε0 depending on α and σ to be chosen later. 55 In order to establish Equation 2.3.5, it suffices to prove a main term estimate |{x ∈ ZN : f1 ∗ g1 (x) > σαN}| ≥ α+β − 3σ N 2 (2.3.6) and three error terms of the form |{x ∈ ZN : | fi ∗ g j (x)| > σα N}| ≤ σN, 10 (2.3.7) where (i, j) = (1, 1). For the main term, we first notice that since f and g are both nonnegative f1 ∗ g1 1 = f1 1 g1 1 = αβN 2 . (2.3.8) If Equation 2.3.6 were false, then we would have f 1 ∗ g1 1 ≤ σαN 2 + α(1 + σ)( α+β − 3σ)N 2 ≤ αβN 2 − ασN 2 2 which contradicts Equation 2.3.8. For the error terms, we will show the argument for j = 2 (the other estimate follows similarly). It is sufficient to show that f i ∗ g2 2 2 ≤ σN σ2 α2 2 N . 200 (2.3.9) Using the convolution identity for Fourier transforms and the Cauchy-Schwarz in- 56 equality, we have f i ∗ g2 2 2 = |( fi ∗ g2 )(x)|2 ∑ x∈ZN =N ∑ | fi ∗ g2 (ξ)|2 ξ∈ZN =N 3 | fi (ξ)|2 |g2 (ξ)|2 ∑ ξ∈ZN ≤ N 3 fi 1/2 ∞ g2 1/2 ∞ | fi (ξ)|3/2 |g2 (ξ)|3/2 ∑ ξ∈ZN = N 3 fi 1/2 ∞ g2 1/2 ∞ fi 3/2 3 g2 3/2 3 1/2 N 3 ε0 . 1/2 Hence, to ensure Equation 2.3.9 we simply require ε0 ≤ σ3 α2 /200, or equivalently ε0 ≤ 2.4 σ6 α4 . 24 52 Sumsets of positive density subsets of Z∗m Let m ∈ Z+ . For B ⊂ Zm and x ∈ Zm , denote rB (x) = |{(b, b ) ∈ B × B : b + b = x}|. In this section our main objective is to prove the following: Proposition 2.4.1. Let α > 0. Suppose m ∈ Z+ is squarefree, and let B ⊂ Z∗m satisfy |B| ≥ αϕ(m). Then there exists an absolute constant C such that if m ≥ m0 = m0 (α) and k ∈ Z+ then ∑ x∈Zm k rB (x) ≤ eCk 3 log(k) α2 |B|k ϕ(m)k . mk−1 As a corollary, we obtain Theorem 2.1.3 using H¨older’s inequality. Proof of Theorem 2.1.3: Assume that B is a set which satisfies the hypotheses of Theorem 2.1.3. We first assume that m is square free and at the end of the proof, we reduce the general case to the square free one. 57 Using H¨older’s inequality, for any k ∈ Z+ , we have (k−1)/k 1/k ∑ rB (x) = ∑ rB (x) ≤ rB (x) ∑ x∈B+B x∈Zm k ∑ . 1 x∈B+B x∈Zm The sum on the left is just |B|2 . Hence, Proposition 2.4.1 implies that |B|2k/(k−1) |B + B| ≥ ∑x∈Zm rB (x)k ≥ 2 |B|2k/(k−1) α2/(k−1) e−2C(k−1) log(k−1) m k/(k−1) (|B|ϕ(m)) 3 = α1+ k−1 e−2Ck = α for k > 2. Taking k = 1/(k−1) 1+ 6k e 3 log(k)/(k−1) −2Ck2 log(k) log(1/α) 1/3 log log(1/α) m m we find 2/3 (log log(1/α))1/3 |B + B| ≥ αe−C2 (log(1/α)) m for α sufficiently small. To deal with the case when α is not small, suppose α0 is the largest density for which we know the theorem is true. Partition B into B1 , . . . , B α/α0 sets each of which contains exactly α0 ϕ(m) consecutive elements of B. We apply the known result to each set B j for 1 ≤ j ≤ α/α0 to obtain 2/3 (log log(1/α ))1/3 0 |B j + B j | ≥ α0 e−C2 (log(1/α0 )) m. Summing over all j, we have α/α0 |B + B| ≥ ∑ |B j + B j | j=1 α/α0 ≥ ∑ 2/3 (log log(1/α ))1/3 0 α0 e−C2 (log(1/α0 )) j=1 2/3 (log log(1/α))1/3 ≥ C1 αe−C2 (log(1/α)) 58 m m 2/3 (log log(1/α ))1/3 0 as desired. Note that the constant C1 = e−C2 (log(1/α0 )) where α0 is the largest α for which we know the result is true. This completes the proof when m is squarefree. We reduce the general case to the squarefree one by letting m1 = ∏ p, p|m and considering the intervals I j = [ jm1 , ( j + 1)m1 ) for j = 0, . . . , m/m1 − 1. Let B j = B ∩ I j , denote α j = |B j | m1 , and let J = { j : α j > α/2}. Notice that m/m1 −1 ∑ αj = α j=1 and so m m1 α m ∑ α j ≥ 2 m1 . j∈J Considering I j and B j as subsets of integers, we note that (B j + B j ) ∩ (Bi + Bi ) = 0/ for i = j. For each j ∈ J we apply the theorem to the translate B j − jm1 to get 2/3 (log log(1/α |B j + B j | ≥ C1 α j e−C2 (log(1/α j )) 1/3 j )) m. Therefore, as subsets of integers, |B + B| ≥ ∑ |B j + B j | j∈J 2/3 (log log(1/α ≥ ∑ C1 α j e−C2 (log(1/α j )) 1/3 j )) m1 j∈J 2/3 (log log(1/α))1/3 ≥ C1 e−C2 (log(1/α)) m1 ∑ α j j∈J ≥ C1 αe −C2 (log(1/α))2/3 (log log(1/α))1/3 m as desired. Proof of Proposition 2.4.1:. Let B be a set satisfying the hypotheses of the 59 lemma, and suppose that the prime factorization of m is m = p1 . . . pt . Define R(x) :=|{(b, r) ∈ B × Z∗m : b + r = x}| =|{b ∈ B : b ≡ x (mod p1 ), . . . , b ≡ x (mod pt )}|. Then R(x) is simply counting the representations of x as a sum involving an element in B and an element taken from the whole of Z∗m , and in particular R(x) ≥ rB (x). Although R(x) is larger than the function rB (x), it is easier to control. Our goal is to produce a good upper bound on the kth moment of R(x). Define S := ∑ R(x)k . x∈Zm We begin by separating the values of x into partitions based on the value of (x, m). More specifically, for d|m let Xd :={x ∈ [0, m − 1] : (x, m) = d} ={x ∈ [0, m − 1] : x = dl for some l ∈ [0, m/d − 1] with (l, m/d) = 1}. Then we have S=∑ ∑ R(x)k = ∑ ∑ |{b ∈ B : b ≡ x d|m x∈Xd (mod p) for all p|m/d}|k d|m x∈Xd since the conditions b ≡ x (mod p) for p|d are certainly satisfied by every b ∈ B by the condition (b, m) = 1. Now, we denote the inner sum by Sd , so that S ≤ ∑ Sd . d|m Expanding the kth power in Sd and rearranging the order of summation gives Sd ≤ ∑ b1 ,...,bk ∈B ∑ 1. x∈Xd b1 ,...,bk ≡x (mod p) for all p|m/d Now, fix a k-tuple b1 , . . . , bk ∈ B. For this k-tuple, the contribution of the inner sum 60 above is |Xd ∩ {x ∈ [0, m − 1] : x ≡ b1 , . . . , bk (mod p) for all p|m/d}| (2.4.1) which is the same as |{l ∈ [0, m/d − 1] : (l, m/d) = 1 and l ≡ b1 , . . . , bk (mod p) for all p|m/d}| = |{l ∈ [0, m/d − 1] : l ≡ 0, b1 , . . . , bk (mod p) for all p|m/d}|. Defining r p (b1 , . . . , bk ) := |{s ∈ [0, p − 1] : bi ≡ s (mod p) for some i = 1, . . . , k}| we see that estimating Equation 2.4.1 is equivalent to estimating m ∏ (p − r p (b1 , . . . , bk ) − 1) = d ∏ p|m/d 1− p|m/d r p (b1 , . . . , bk ) + 1 . p Hence, we have shown that Sd ≤ r p (b1 , . . . , bk ) + 1 m 1− . ∏ p b1 ,...,bk ∈B d p|m/d ∑ (2.4.2) In order to bound this sum from above we need to understand the function r p (b1 , . . . , bk ). We notice that if p is much larger than k, then a random k-tuple will intersect k distinct residue classes (mod p) with high probability, and so r p (b1 , . . . , bk ) is typically of size k. The following lemma quantifies this fact. Lemma 2.4.1. For b1 , . . . , bk ∈ B let f (b1 , . . . , bk ) = ∑ p|m r p (b1 ,...,bk )≤k−1 1 . p Then there is an absolute constant c > 0 such that for every β ∈ R+ we have 2 |{b1 , . . . , bk ∈ B : f (b1 , . . . , bk ) ≥ β}| ≤ k2 2− exp(β/ck ) |B|k−2 ϕ(m)2 . 61 Proof. The result will follow from optimizing a double-counting argument on the quantity l ∑ bi ,b j ∈B ∑ p|bi −b j p|m 1 p over positive integer values of l. Upper Bound: We expand out the exponent and rearrange summation to get 1 p · · · pl ,...,p |m 1 ∑ p1 l 1. ∑ bi ,b j ∈B bi ≡b j (mod lcm(p1 , . . . , pl )) Now, fixing the l-tuple p1 , . . . , pl , we suppose that the distinct primes among this l-tuple are p1 , . . . , pu . Then the inner sum above is bounded above by 1= ∑ x,y∈Z∗ m x≡y (mod lcm(p1 , . . . , pl )) ϕ(m)2 . ϕ(lcm(p1 , . . . , pl )) It follows that the original quantity is bounded from above by 2 ϕ(m) p1 1 ∑ p1 . . . pl ϕ(lcm(p1 , . . . , pl )) ,··· ,p |m 2 ≤ ϕ(m) l 1 ∑ p(p − 1)1/l p|m l . Splitting the remaining sum based on whether p is greater than or less than l l and analyzing appropriately we see that the inner sum over p|m is smaller than ∑ 2≤p≤l l 1 1 + ∑ 1+1/l p n≥l l n log(l) + Z ∞ dx ll x1+1/l log(l). It follows that l ∑ bi ,b j ∈B ∑ p|bi −b j p|m 1 2 l ≤ ϕ(m) (c log(l)) , p where c > 0 is some constant. 62 (2.4.3) Lower Bound: Let K = K(β) = b1 , . . . , bk ∈ B : ∑ p|m r p (b1 ,...,bk )≤k−1 1 ≥ β . p Given b1 , . . . , bk ∈ K, we have ∑ ∑ i, j=1,...,k p|m i= j p|bi −b j 1 ≥ p ∑ p|m p|bi −b j for some i= j 1 = p 1 ≥ β p ∑ p|m r p (b1 ,...,bk )≤k−1 so there must be some pair, bi , b j , such that ∑ p|m p|bi −b j 1 β ≥ k . p 2 At least one such pair comes from each k-tuple b1 , . . . , bk ∈ K, and a given pair bi , b j can appear in at most k2 |B|k−2 k-tuples. We therefore have l ∑ bi ,b j ∈B ∑ p|bi −b j p|m |K| 1 l k ≥ 2 k−2 β p k |B| 2 −l . Combining the upper and lower bounds gives −l |K| k βl 2 k−2 k |B| 2 It follows that |K| ≤ β−l k 2 ≤ cl (log l)l ϕ(m)2 . l k2 cl (log l)l |B|k−2 ϕ(m)2 . Taking l = exp(β/ck2 ) we find that |K| ≤ k2 2−l |B|k−2 ϕ(m)2 . 63 We are now ready to proceed with the proof of Proposition 2.4.1. We would like to break the sum Sd into pieces defined by the behavior of the function r p (b1 , . . . , bk ). For technical reasons, we must first define some additional notation. Define m1 := m2 := ∏p p|m p≤3k ∏ p, p|m p>3k and for any d|m define d1 := d2 := ∏p p|d p≤3k ∏ p. p|d p>3k Then we can rewrite Equation 2.4.2 to have Sd ≤ m1 b1 ,...,bk ∈B d1 ∑ = ϕ(m1 /d1 ) ∏ 1− p|m1 /d1 m2 b1 ,...,bk ∈B d2 ∑ 1 p m2 d2 p|m2 /d2 1− ∏ 1− ∏ p|m2 /d2 r p (b1 , . . . , bk ) + 1 p r p (b1 , . . . , bk ) + 1 . p For a fixed d and a b1 , . . . , bk ∈ B, let P = {p|m2 /d2 : r p (b1 , . . . , bk ) ≤ k − 1}. Expanding Sd as a sum over geometric intervals we have ∞ Sd ≤ ϕ(m1 /d1 ) ∑ j=−∞ ∑ b1 ,...,bk ∈B f (b1 ,...,bk )∈[2 j ,2 j+1 ) ∞ ≤ ϕ(m1 /d1 ) ∑ j=−∞ ∑ b1 ,...,bk ∈B f (b1 ,...,bk )∈[2 j ,2 j+1 ) m2 d2 m2 d2 ∏ 1− r p (b1 , . . . , bk ) + 1 p 1− k+1 p p|m2 /d2 ∏ p|m2 /d2 64 ∏ p∈P 1− k+1 p −1 . Now, for fixed j and b1 , . . . , bk ∈ B we have log ∏ p∈P 1− −1 k+1 p = − ∑ log 1 − p∈P = k+1 ∑ p p∈P 1+ k+1 p k+1 1 + p 3 1 2 k+1 p ≤ (k + 1)2 j+1 , 2 +... (2.4.4) where the second to last line follows from the fact that all primes in P are larger than 3k. Applying Lemma 2.4.1 we now have Sd ≤ ϕ(m1 /d1 ) m2 d2 ≤ k2 ϕ(m1 /d1 ) ∏ 1− p|m2 /d2 ∞ k+1 p ∑ j=−∞ ∞ j ∞ Ck = j j j 2 ∑ e2(k+1)2 2− exp(2 /ck ) j=0 m2 k−2 k+1 |B| ϕ(m)2 ∏ 1− d2 p p|m2 /d2 where j b1 ,...,bk ∈B f (b1 ,...,bk )∈[2 j ,2 j+1 ) m2 k−2 k+1 |B| ϕ(m)2 ∏ 1− d2 p p|m2 /d2 = k2Ck ϕ(m1 /d1 ) e2(k+1)2 ∑ (2.4.5) 2 ∑ e2(k+1)2 2− exp(2 /ck ) . (2.4.6) j=0 Note that the lower bound on the range of summation in j comes from the fact that for every k-tuple b1 , . . . , bk ∈ B we have f (b1 , . . . , bk ) ≥ ∑ p≤k 1/p log log k > 2 provided k is large enough. Note also that the sum is clearly convergent to some constant dependent only on k. We also note that since we will see that Ck has size eCk 3 log k , in the argument below we have absorbed several smaller functions of k into Ck . The remainder of the proof follows in two steps. We first find a bound for S in terms of Ck by summing ∑d|m Sd and then we compute an upper bound for Ck . In particular, we will show S≤ Ck3 |B|k ϕ(m)k α2 mk−1 65 (2.4.7) and Ck ≤ eCk 3 log(k) . (2.4.8) We start by proving Equation 2.4.7. Summing Equation 2.4.5 over all d|m, we have S ≤ k2Ck |B|k−2 ϕ(m)2 ∑ ϕ(m1 /d1 ) d|m m2 d2 1− ∏ p|m2 /d2 k+1 . p Noticing that ϕ(m1 /d1 ) ≤ m1 we have ϕ(m1 /d1 )m2 ≤ m. Further, we observe that the number of divisors d of m which will give the same d2 is the number of ways of choosing which primes p ≤ 3k will be factors of d. In other words, there are fewer than 3k ∑ t=0 3k = 23k t such values of d. We can now rewrite the bound on S as S ≤ Ck2 |B|k−2 ϕ(m)2 m ∑ d2 |m2 = Ck2 α−2 |B|k m ∏ 1 − p|m2 = Ck2 α−2 |B|k m ∏ 1 − p|m2 ≤ Ck2 α−2 |B|k m ∏ 1 − p|m2 1 d2 1− ∏ p|m2 /d2 k+1 p k+1 p ∑ d2 |m2 k+1 p 1 d2 ∏ p|d2 (1 − (k + 1)/p) 1+ 1 p−k−1 k 1 p (2.4.9) where the last step follows by recalling that primes dividing m2 are larger than k. Using the fact that |B| = αϕ(m) and the fact that ϕ(m) = m ∏ p|m (1 − 1/p), the bound becomes S≤ Ck2 |B|k ϕ(m)k α2 mk−1 ∏ p|m1 1− 1 p −k . The remaining product is less than (3k)k , which is smaller than Ck . 66 It remains to prove Equation 2.4.8. Recall that ∞ Ck = ∑ e(k+1)2 j+1 −exp(2 j /ck2 ) log(2) (2.4.10) j=0 Expanding out the exponential function in the exponent, we see that the entire exponent is smaller than 2(k + 1)2 j+1 − log(2) − 2j 22 j − . ck2 2c2 k4 We notice that if j is larger than log2 (c2 k4 (k + 1)), then 22 j ≥ (k + 1)2 j+1 . 2c2 k4 Hence for j ≥ log2 (4c2 k4 (k + 1)), the exponent is smaller than log(2) − 2 j /ck2 and 2 so the tail of the sum is bounded by e1/(ck ) . Furthermore, we find that for small j, the exponent is maximized when 2 j = ck3 log(4ck2 (k + 1)/ log 2). Hence, splitting the sum in Equation 2.4.10, we have Ck ≤ log2 (4c2 k4 (k + 1))eck 3 log(4ck2 (k+1)/ log 2) 2 + e1/ck . Inequality Equation 2.4.8 follows. Combining Equation 2.4.7 and Equation 2.4.8, we have S≤ eCk 3 log(k) α2 |B|k ϕ(m)k mk−1 as desired. 2.5 Completion of the proof of Theorem 2.3.1 In this section we complete the proof of Theorem 2.3.1, which implies Theorem 2.1.2, the main result of this chapter. 67 Let n be sufficiently large, let An ⊂ Pn satisfy |An | ≥ δ|Pn |, and let ε > 0. Suppose that G is as in Section 3, and let α be such that |G| = αϕ(m) (in particular, α ≥ δ/2). Then, by Proposition 2.3.1, for every W sufficiently large in terms of δ and ε we have |An + An | ≥ (∆x − ε) ∑ x∈G+G n m (2.5.1) where m = ∏ p≤W p. Since ∑ δb ≥ δϕ(m), b∈Z∗m we can show that δ ∑ δb ≥ 2 ϕ(m). b∈G Hence, we also see that ∑ (b,b )∈G×G δb + δb 2 ≥ δ |G|2 . 2α Setting r(x) = |{(b, b ) ∈ G × G : b + b = x}| we can see that Equation 2.5.2 is equivalent to ∑ r(x)γx ≥ x∈G+G where γx = δ |G|2 2α δb + δb 1 ∑ r(x) (b,b ): b+b =x 2 ≤ ∆x . Using H¨older’s inequality, we have 1 k ∑ x∈G+G r(x)k ∑ x∈G+G 68 k k−1 ∆x k−1 k ≥ δ |G|2 . 2α (2.5.2) Applying Proposition 2.4.1 we find ∑ k k−1 k−1 k ≥ ∆x x∈G+G δ 2 α2/k eCk 2 log(k) m(k−1)/k . Because k/(k − 1) > 1 and ∆x ≤ 1, we have ∑ x∈G+G ∆x ≥ δ 2 k/(k−1) α2/(k−1) e−C k3 log(k) k−1 m. Proceeding as in the proof of Theorem 2.1.3 and then returning to Equation 2.5.1, we have 2/3 (log log(1/δ))1/3 |An + An | ≥ C1 δe−C2 (log(1/δ)) for every ε > 0. 69 −ε n Chapter 3 Sums and products of distinct sets and distinct elements in C In the final research chapter, we will give the proofs of Theorem 1.2.3 and Theorem 1.2.4 (restated below as Theorem 3.1.3 and Theorem 3.1.1, respectively). Once again, a short introduction reviews the most vital points of background knowledge. We then prove a special case of Theorem 1.2.3, corresponding to the case B = A; the proof of this case is more straightforward than that of the general case. It also allows us to follow up by immediately proving Theorem 1.2.4. We then give the proof of Theorem 1.2.3 in full generality. The content of this chapter is taken from [13]. Acknowledgements: I would like to thank J´ozsef Solymosi for pointing out and providing the reference [19] and for his suggestions for improving the argument, and Izabella Łaba for her constant support throughout the production of this work. I would also like to thank Mariah Hamel for her help, and Boris Bukh for his suggestions. 3.1 Introduction Let A and B be finite subsets of a commutative ring R. Then we can form the sumset A + B = {a + b : a ∈ A, b ∈ B} and the productset AB = {a · b : a ∈ A, b ∈ B}. In the case A = B, we denote the sumset by 2A and the productset by A(2) , and we may 70 also consider the variants kA = {a1 + ... + ak : a1 , ..., ak ∈ A} and A(k) = {a1 · ... · ak : a1 , ..., ak ∈ A}, for k ∈ Z+ , k ≥ 2. The sum product phenomenon, roughly, is the observation that |kA| and |A(k) | cannot both be small (except in degenerate cases; for example, when A is a subring of R). The most general result, which holds in arbitrary rings, is due to Tao [43]. On the other hand, the classical conjecture, due to Erd¨os and Szemer´edi, relates to the specific case when R = Z: Conjecture 3.1.1 (Erd˝os-Szemer´edi). Let A ⊂ Z be finite with |A| = N. Let ε > 0. Then if N ≥ N0 = N0 (ε) we have max(|A + A|, |A · A|) ≥ N 2−ε . While this remains open, Erd˝os and Szemer´edi did prove that on the right hand side we must have at least N 1+δ for some δ > 0. We then have the following numerical lower bounds for δ: 1/31 (Nathanson 1997), 1/15 (Ford 1998), 1/4 (Elekes 1997), 3/14 (Solymosi, 2005), and 1/3 − ε for any ε > 0 (Solymosi 2008). The latter three in fact hold for subsets of R. There is also an extension of Conjecture 3.1.1 to k-fold sums and products: if A is a finite set of integers then it is conjectured that for any ε > 0 |kA| + |A(k) | ε |A|k−ε . There are also analogues of the sum-product phenomena which apply to sums and products of distinct elements from a finite set A ⊂ R. In particular, letting A = {a1 , . . . , an }, one can construct the set of simple sums of A and the set of simple products of A, respectively n A+ = ∑ εi ai : εi ∈ {0, 1} for each i = 1, . . . , n (3.1.1) i=1 and A× = n ∏ aεi i : εi ∈ {0, 1} for each i = 1, . . . , n . i=1 71 (3.1.2) It is then possible to consider gR (n) = min {|A+ | + |A× |}. A⊂R, |A|=n (3.1.3) Such expressions were investigated by Erd˝os and Szemer´edi in [17] in the integer setting. They showed that log n gZ (n) < nc log log n (3.1.4) for some absolute constant c > 0. Later, in addition to providing an upper bound on c, Chang proved ([8]) their conjecture that this provides the lower bound as well; more precisely, she showed that for large enough values of n log n gZ (n) > n(1/8−ε) log log n . (3.1.5) More recently, in [9], Chang addressed a question of Ruzsa, proving that gC (n) grows faster than any power of n, log(gC (n)) = ∞. n→∞ log n lim (3.1.6) In this chapter we will obtain an explicit lower bound for gC (n). In particular, since gR2 (n) ≤ gR1 (n) whenever R1 is a subring of R2 , this bound will hold for any subring of C. Our result in this direction is the following. Theorem 3.1.1. Let ε > 0 and let n0 = n0 (ε) be sufficiently large in terms of ε. Then for any n ≥ n0 we have gC (n) ≥ n (1/200−ε) loglogloglog(n) log(n) . (3.1.7) The proof largely follows that of [8]. This approach uses yet another manifestation of the sum-product phenomenon, the statement that a small productset requires a large iterated sumset. Chang proved that if A ⊂ Z is finite, and |A · A| ≤ α|A| for some α, then for every h ≥ 2 we have |hA| ≥ |A|h . (2h2 − h)hα 72 In [10], Chang also proved an analogous result in R, provided the multiplicative doubling constant α satisfies α log |A|. We will use a version which holds in C: Theorem 3.1.2. Let A ⊂ C be finite, and suppose that |A(2) | ≤ α|A|. Then there is an absolute constant c1 such that for any integer h ≥ 2 we have 49h α |hA| ≥ c1 e−h |A|h . We will prove this result by following Chang’s argument for the real case, making necessary alterations to deal with the possibility of torsion elements in C. Note the explicit dependence on h, which will be essential in our proof of Theorem 3.1.1. Using a result of Ruzsa ([37], Theorem 3.4.1 below), we have also extended Theorem 3.1.2 to distinct sets A and B. Theorem 3.1.3. Let A, B ⊂ C with |B| = C|A| for some C ≥ 1, and suppose that |AB| < α|A|. If α log |A| then there is an absolute constant c1 such that |kA + lB| ≥ c1 |A|k |B|l − Ok,l,α (|B|k+l−1 ) (k + l)4(k+l) 15(k+l) α where the implicit constant in the O term can be taken as c2 e4(k+l) for an absolute constant c2 . This builds on the theme of sum product phenomena for distinct sets; other results in a similar vein may also be found in [10]. The proofs of Theorem 3.1.2 and Theorem 3.1.3 rely on bounding the number of additive 2h-tuples in A2h (respectively, additive (2k + 2l)-tuples in Ak × Bl ); this is accomplished by using a result of Evertse, Schlickewei, and Schmidt [19] which we next describe. Let K be an algebraically closed field of characteristic 0. Let K ∗ = K \ {0} be the multiplicative subgroup of nonzero elements in K. For a positive integer d let Γ be a subgroup of (K ∗ )d with rank r (so the minimum number of elements from which we can generate Γ is r). For coefficients a1 , . . . , ad ∈ K, let A(d, r) denote the number of solutions (x1 , . . . , xd ) ∈ Γ to a1 x1 + a2 x2 + · · · + ad xd = 1 73 which are nondegenerate (namely, no proper subsum of the left side vanishes). It is crucial that in the following result, which we will refer to as the Subspace Theorem, the bound is finite and depends only on r and d, and not on the particular group Γ nor the particular coefficients of the objective equation. Theorem 3.1.4 (Evertse, Schlickewei, and Schmidt [19]). Let d, r, and A(d, r) be as defined above. Then A(d, r) ≤ exp (6d)3d (r + 1) . We will also use two other standard tools of additive combinatorics (see, for example, [44]). The first is Freiman’s theorem in torsion-free groups [6] (given for general torsion free groups in, for example, [44]). Theorem 3.1.5 (Freiman’s Theorem). Let Z be a torsion-free abelian group, and let A ⊂ Z with |A + A| ≤ K|A| for some K ∈ R. Then there exists a proper generalized arithmetic progression P of dimension at most K − 1 and size |P| ≤ C(K)|A| which contains A. Here C(K) depends only on K. The second is the Pl¨unnecke-Ruzsa Inequality, in a version due to Ruzsa [38]. Theorem 3.1.6 (Pl¨unnecke-Ruzsa Inequality [38]). Let Z be an abelian group and let A and B be subsets of Z with |A + B| ≤ K|A|. Then for every n, m ∈ N we have |nB − mB| ≤ K n+m |A|. In Section 2 we begin by extending Chang’s notion of multiplicative dimension of a set of integers to sets of complex numbers, and prove three key properties of it. The third of these is an application of Freiman’s Theorem, and allows us to bound the multiplicative dimension of a set from above by its multiplicative doubling constant |A(2) |/|A|. This allows us to work with sets of low multiplicative dimension without loss of generality in order to use Theorem 3.1.4 to prove Theorem 3.1.2. In Section 3 we carry out the argument which proves Theorem 3.1.1 on simple sums and products, using Theorem 3.1.2. In Section 4, we use a Theorem of Ruzsa in place of Freiman’s Theorem to show that if distinct sets A and B have a small productset, then we may once again 74 bound the multiplicative dimension of both of them by |AB|/|A|. We are then once again able to proceed using Theorem 3.1.4 to prove Theorem 3.1.3. Notation: We will use the notation f (x) g(x) or f (x) = O(g(x)) to denote that there is a constant C such that for every x, f (x) ≤ Cg(x). Similarly, f (x) is the same as g(x) g(x) f (x), and f (x) ≈ g(x) means that there are constants C1 ,C2 such that C1 g(x) ≤ f (x) ≤ C2 g(x) for every x. We will use N to denote the positive integers, N0 to denote the nonnegative integers, and Z to denote the set of all integers. For an integer L, ZL will denote the integers modulo L. 3.2 3.2.1 Sums and products of a single set Multiplicative dimension and bounding the doubling constant Throughout this section A will denote a finite subset of C and n will denote the cardinality of A. Let h ≥ 2 be an integer. Also, let A∗ := A \ {0}. Then A∗ consists of those elements of A contained in the multiplicative subgroup C∗ of complex numbers. Lastly, the multiplicative subgroup of C∗ generated by the elements z1 , . . . , zm ∈ C∗ will be denoted by z1 , . . . , zm . We begin by extending the definition of multiplicative dimension from [8]. Definition 3.2.1. Let A ⊂ C be finite. Then we define the multiplicative dimension of A, denoted dim× (A), by dim× (A) = min M : ∃ z, z1 , . . . , zM ∈ C∗ such that A∗ ⊂ z · z1 , . . . , zM . (3.2.1) In other words, the multiplicative dimension of A is the minimal number M such that A∗ is contained in a coset of subgroup of C∗ of rank M. For d ∈ Z+ and X ⊂ Rd we will say that X is r-dimensional if the affine subspace of Rd of smallest dimension in which X may be contained has dimension r. Note that if a set is r-dimensional it must contain at least r + 1 elements, and 75 must also contain r linearly independent differences. From this fact, observe that for X,Y ⊂ Rd , dim(X +Y ) ≤ dim(X) + dim(Y ) (3.2.2) dim(X ∪Y ) ≥ dim(X +Y ). (3.2.3) and also that We wish to relate the above two concepts of dimension to each other. To do so, we will need to transition between groups of the form z1 , ..., zm and the group Zm . The Fundamental Theorem of Finitely Generated Abelian Groups provides the necessary maps to do so, in the proof of Lemma 3.2.1 below. However, some preliminary examples will help to clarify the argument. Example 1: Let A = {2, 31 eiπ/4 , 19 eiπ/2 , eiπ equal to 3, since it is contained in 2, is just isomorphic to Z3 , √ 2 }. Then A has multiplicative dimension √ 1 iπ/4 iπ 2 ,e 3e which is torsion-free. But this and furthermore if the isomorphism is denoted ν then we √ 2) can take ν(2) = (1, 0, 0), ν( 31 eiπ/4 ) = (0, 1, 0), and ν(eiπ = (0, 0, 1). Then we will have ν(A) = {(1, 0, 0), (0, 1, 0), (0, 2, 0), (0, 0, 1)}. Note that dim(ν(A)) = 3. Example 2: The situation is slightly more complicated if A contains torsion elements. Let A = {2, 13 eiπ/4 , eiπ/2 , eiπ/3 }. Then A once again has multiplicative dimension equal to 3, since it is contained in 2, 13 eiπ/4 , eiπ/6 := G. This group is isomorphic to Z2 × Z6 . Denoting this isomorphism by η and proceeding as in the previous example, we have η(A) = {(1, 0, 0), (0, 1, 0), (0, 0, 2), (0, 0, 3)}. However, we can consider this to be a subset of Z3 of dimension 3 by considering the last component of each point to be in [0, 5] ⊂ Z. This provides a one-to-one mapping η between η(G) and Z3 , and so we have a one-to-one mapping ν = η ◦η between G and Z3 . By extending the above calculations to the general case, one obtains the following key properties of multiplicative dimension, which we will use extensively. 76 Lemma 3.2.1. Let A ⊂ C∗ be finite with dim× (A) = m. Let G = z1 , ..., zm for some z1 , ..., zm ∈ C∗ , and suppose that A ⊂ z · G for some z ∈ C∗ . Let h ∈ N, h ≥ 2. Then (a) There is an injection ν : zG → Zm mapping zG into the additive group of mtuples of integers such that for every B ⊂ A we have dim(ν(B)) ≥ dim× (B) where ν(B) is viewed as a subset of Rm . (b) If ν is the map from (a), then for sets B, B1 , ..., Bh ⊂ zG we have 1 |B1 · ... · Bh | ≥ |ν(B1 ) + ... + ν(Bh )|. h and |B× | ≥ 1 |ν(B)+ | |B| (3.2.4) (3.2.5) (c) m ≤ (2|(A)(2) |/|A|) − 1 Proof. (a) The map which takes za ∈ G to a is an isomorphism, so we may assume without loss of generality that A ⊂ z1 , ..., zm = G. By the fundamental theorem of finitely generated abelian groups applied to z1 , . . . , zm , there is such a mapping if G is torsion-free. Suppose that G is not torsion-free. We claim that, in this case, the fundamental theorem of finitely generated abelian groups guarantees an isomorphism η : G → Zm−1 × ZL for some integer L. It certainly guarantees an isomorphism η : G → Zm−t ×ZL1 ×...×ZLt for some integer t, 1 ≤ t ≤ m and some L1 , ..., Lt ∈ N. Then for 1 ≤ j ≤ m we let ξ j = η−1 ((0, ...0, 1, 0, ..., 0)) where the nonzero entry is in the jth component. For m − t + 1 ≤ j ≤ m, ξ j has finite order, so it must be a root of unity. Hence there are positive integers r j , s j such that ξ j = e2πir j /s j . 77 Then, letting s = sm−t+1 · ... · sm and ξ = e2πi/s we see that ξ j = ξr j (s/s j ) , where r j (s/s j ) ∈ Z. In other words, ξj ∈ ξ for each j, m − t + 1 ≤ j ≤ m. Therefore, A ⊂ ξ1 , ..., ξm−t , ξ implying that dim× A ≤ m − t + 1. This is only possible if t = 1, and the claim follows. Now, the map η : Zm−1 × ZL → Zm which takes (x1 , ..., xm ) ∈ Zm−1 × ZL to (x1 , ..., xm ), where xm is the residue in [0, L − 1] of the class xm ∈ ZL , is an injection. We take ν = η ◦ η. Note that ν maps G injectively onto Zm−1 × [0, L − 1], but that η−1 may be extended to a surjection defined on all of Zm by setting η−1 ((x1 , ..., xm )) = (x1 , ..., xm ). It remains to prove the claim that ν(B) has dimension dim× (B) for each B ⊂ A. This will follow from the definition of multiplicative dimension. If ν(B) is contained in an affine subspace S of Rm of dimension d, we let x(0) ∈ S. It follows that there are vectors x(1) , ..., x(d) ∈ S − {x(0) } such that ν(B) ⊂ span(x(1) , ..., x(d) ) + {x(0) }. In other words, if b ∈ B, we can represent ν(b) as d ν(b) = x(0) + ∑ ki x(i) i=1 for some integers ki , i = 1, ..., d. (i) (i) Next, suppose that x(i) = (x1 , ..., xm ) for i = 0, ..., d, and denote by x(i) the element of Zm−1 × ZL given by (i) (i) (i) x(i) = x1 , ..., xm−1 , xm (i) (i) , where once again xm ∈ ZL is the residue class of xm ∈ [0, L − 1]. It follows that d η(b) = x(0) + ∑ ki x(i) . i=1 78 Then d b = η−1 (η(b)) = η−1 x(0) + ∑ ki x(i) i=1 d = η−1 x(0) ∏ η−1 x(i) ki i=1 ∈ η−1 x(0) η−1 x(1) , ..., η−1 x(d) . By definition of multiplicative dimension, it follows that d ≥ dim× (B). (b) Equations Equation 3.2.4 and Equation 3.2.5 follow immediately in the case where G is torsion-free (and hence ν is an isomorphism). We may therefore assume that G contains roots of unity. Let η : G → Zm−1 × ZL be the isomorphism from (a). Then to prove Equation 3.2.4, it is sufficient to show |η(B1 ) + ... + η(Bh )| ≥ 1h |ν(B1 ) + ... + ν(Bh )|. Let x = (x1 , ..., xm ) ∈ ν(B1 ) + ... + ν(Bh ). (i) (i) Then there are elements x(i) = (x1 , ..., xm ) ∈ ν(Bi ) for each i, 1 ≤ i ≤ h such that h x = ∑ x(i) , i=1 so (x1 , ..., xm ) ∈ η(B1 ) + ... + η(Bh ). But ν(B1 ) + ... + ν(Bh ) ⊂ Zm−1 × [0, hL] and so there are at most h elements (x1 , ..., xm−1 , y) of the left side such that (x1 , ..., xm−1 , y) evaluates to (x1 , ..., xm ). Hence there are at least |ν(B1 ) + ... + ν(Bh )|/h elements in η(B1 ) + ... + η(Bh ) as required. The proof of Equation 3.2.5) is nearly identical to that of Equation 3.2.4. It is 79 sufficient to show |η(B)+ | ≥ 1 + |B| |ν(B) |. Denote ν(B) = {x(1) , ..., x(|B|) }, and let x = (x1 , ..., xm ) ∈ ν(B)+ . Then there are values εi ∈ {0, 1} for each i, 1 ≤ i ≤ |B| such that |B| x = ∑ εi x(i) , i=1 so (x1 , ..., xm ) ∈ η(B)+ . But ν(B)+ ⊂ Zm−1 × [0, |B|L] and so there are at most |B| elements (x1 , ..., xm−1 , y) of the left side such that (x1 , ..., xm−1 , y) evaluates to (x1 , ..., xm ). Hence there are at least |ν(B)+ |/|B| elements in η(B)+ as required. (c) Let β = |(A)(2) |/|A|. Then by the first claim in part (b), |ν(A) + ν(A)| ≤ 2|(A)(2) | ≤ 2β|ν(A)|. Now, Theorem 3.1.5 applies, and we may contain ν(A) in a progression in Zm of dimension 2β − 1 , say 2β−1 ν(A) ⊂ x(0) + ∑ ji x(i) : 0 ≤ ji ≤ ki − 1 . i=1 But then A ⊂ η−1 (x(0) ) η−1 (x(1) ), ..., η−1 (x ) , ✷ which demonstrates the desired bound. Note that if 0 ∈ A and α = 2β−1 |A(2) |/|A|, 80 then we may apply Lemma 3.2.1 to A∗ , noting that |(A∗ )(2) | = |A(2) \ {0}| = |A(2) | − 1 ≤ α|A| − 1 = α(|A∗ | + 1) − 1 ≤ 2α|A∗ |, so that we obtain the inequality m ≤ 4α − 1. 3.2.2 (3.2.6) Bounding additive 2h-tuples In light of Equation 3.2.6, we are free to work with sets of low multiplicative dimension. Theorem 3.1.2 will follow as a corollary of the following. Proposition 3.2.1. Let A ⊂ C be finite, and suppose that dim× (A) = m. Then for any h ∈ N, h ≥ 2 there is n sufficiently large such that if |A| ≥ n we have 49h m |hA| ≥ e−h |A|h We will say that a 2h-tuple (a1 , ..., a2h ) ∈ A2h is an additive 2h-tuple if a1 + ... + ah = ah+1 + ... + a2h . The above proposition is a consequence of the following lemma from [8]. Lemma 3.2.2. Let A ⊂ C be finite. Let M denote the number of additive 2h-tuples in A2h . Then |hA| ≥ |A|2h M To prove Proposition 3.2.1 we therefore seek to bound the number of solutions (a1 , ..., a2h ) in A2h to the equation x1 + · · · + xh = xh+1 + · · · + x2h . 81 (3.2.7) To do so, one finds a likely tool in Theorem 3.1.4. However, Theorem 3.1.4 gives a bound on the number of nondegenerate solutions, whereas we must also account for the possibility of degenerate solutions. The result is the following statement, similar to a lemma of Chang in [10]: Lemma 3.2.3. Suppose that A ⊂ C satisfies 0 ∈ / A, and let dim× (A) = m. For every k ≥ 1 there is n sufficiently large such that if |A| ≥ n and c1 , ..., ck ∈ C∗ then (a) The number of elements (y1 , . . . , yk ) ∈ Ak satisfying c1 y1 + · · · + ck yk = 1 is at most ek 12k m n k/2 if k is odd and ek 12k m nk/2−1 if k is even. (b) The number of elements (y1 , . . . , yk ) ∈ Ak satisfying c1 y1 + · · · + ck yk = 0 is at most ek 12k m n k/2 . Proof. For r, s ∈ N let Ds,r = exp(s12s r), and let γ1 (s) = s/2 , if s is odd s/2 − 1, if s is even , γ0 (s) = s/2 . (3.2.8) (3.2.9) Then the statement we need to prove is that the number of solutions (y1 , ..., yk ) in Ak to c1 y1 + · · · + ck yk = 1 is at most Dk,m nγ1 (k) and that the number of solutions to c1 y1 + · · · + ck yk = 0 is at most Dk,m nγ0 (k) . Since A has multiplicative dimension m, A ⊂ zH for some subgroup H of C∗ of rank m; hence G = zH is a group of rank at most m + 1 which contains A. The proof proceeds by induction on the number of variables k. Base Cases: The case k = 1 is immediate. When k = 2 we see directly that the number of solutions (y1 , y2 ) ∈ A × A to c1 y1 + c2 y2 = 0 is at most n (Each of |A| = n choices for y1 determines a value −c1 y1 /c2 for y2 ). Meanwhile the number of nondegenerate solutions (y1 , y2 ) ∈ A × A to c1 y1 + c2 y2 = 1 is at most exp((12)6 (2(m + 1) + 1)) by Theorem 3.1.4, and the only two possible degenerate solutions are (0, 1) and (1, 0). We have exp((12)6 (2m + 3)) + 2 ≤ exp(224 m). 82 Hence the bound holds for k = 2 and all pairs (c1 , c2 ) of coefficients. Induction: Let k > 2 be fixed, and suppose both parts of the theorem have been proved for t variables for each positive integer t < k and for all t-tuples of coefficients (c1 , ..., ct ). We begin with the equation c1 y1 + · · · + ck yk = 0, (3.2.10) which we rewrite as c1 y1 + ... + ck−1 yk−1 = −ck yk . There are at most n choices for yk in A, all of which are nonzero. Picking one of these (call it a) and dividing through by the value −ck a, the number of solutions (y1 , ..., yk−1 , a) ∈ Ak to Equation 3.2.10 is the number of solutions to the new equation c1 ck−1 y1 + · · · + yk−1 = 1 −ck a −ck a (3.2.11) in k − 1 variables. There are still n possibilities for each variable in this equation, and each still falls in A. First suppose k is even. Then k − 1 is odd, so by the inductive hypothesis there are at most Dk−1,m n(k−2)/2 solutions in Ak−1 to Equation 3.2.11. Since there are at most n possible values for a, we have at most Dk−1,m nk/2 solutions in Ak to Equation 3.2.10. Since k is even, this is the desired result. Next, if k is odd, k − 1 is even, and the equation Equation 3.2.11 has fewer than Dk−1,m n(k−1)/2−1 solutions in Ak−1 , whereby the Equation 3.2.10 has fewer than Dk−1,m n(k−1)/2 in Ak . This again gives the desired result. Hence the result for vanishing sums holds in k variables. To count solutions in Ak to c1 y1 + · · · + ck yk = 1, (3.2.12) we begin by applying Theorem 3.1.4. This tells us that the number of nondegenerate solutions in the entirety of the rank k(m + 1) group Gk is bounded by exp((6k)3k (k(m + 1) + 1)). We use the inductive hypothesis to count degenerate solutions. 83 For each such degenerate solution (y1 , ..., yk ) ∈ Ak of Equation 3.2.12 we have a nonempty proper subset of {c1 y1 , ..., ck yk } which sums to 0, and the complement of this proper subset sums to 1. From each degenerate solution, then, we obtain a corresponding solution of a system of the form t k ∑ ci j yi j = 0 ∑ j=1 ci j yi j = 1 (3.2.13) j=t+1 where 2 ≤ t ≤ k − 1, and i1 , . . . , ik is some permutation of 1, . . . , k with i1 < · · · < it and it+1 < · · · < ik . Furthermore, every other solution of Equation 3.2.12 in Ak from which we obtain the same solution of Equation 3.2.13 in this manner must have components which are a permutation of (y1 , ..., yk ). It follows that, since there are solutions in Ak k t choices for {i1 , . . . , it }, the total number of to Equation 3.2.12 is bounded via the inductive hypothesis by k−1 2(k!) ∑ t=2 k Dt,m Dk−t,m nγ0 (t)+γ1 (k−t) t (3.2.14) where we have used the extra factor of two to simply account for the small number nondegenerate solutions. We begin by computing the exponent on n. Arguing based on parity of k, for k even we have γ0 (t) + γ1 (k − t) = k/2 − 1 = γ1 (k), (3.2.15) independent of the parity of t. Similarly, for k odd, we get (k − 1)/2, if t is even γ0 (t) + γ1 (k − t) = (k − 3)/2, if t is odd ≤ γ1 (k). In both cases we see that we can bound Equation 3.2.14 by k−1 2(k!) ∑ t=2 k Dt,m Dk−t,m nγ1 (k) t and we need only compute the constant. 84 (3.2.16) Now, Dt,m Dk−t,m = exp (t 12t + (k − t)12(k−t) )m . (3.2.17) The exponent is maximized over all possible values of t for t = k − 1. The entire sum is therefore bounded above by k−1 2(k!) exp((1 + (k − 1)12(k−1) )m) ∑ t=2 k−1 using the fact that ∑t=2 k t k ≤ exp(k12k m) t < 2k . The result for unit sums therefore holds for k variables. The lemma now follows ✷ by induction. In order to prove Proposition 3.2.1 we must eliminate the hypothesis 0 ∈ /A from Lemma 3.2.3(b) for the case of equations of the form Equation 3.2.7. We continue to use the notation n = |A|. Then if 0 ∈ A, the number of solutions to Equation 3.2.7 we gain is bounded above by 2h−1 ∑ t=1 2h D2h−t,m n t (2h−t)/2 . Here we have set t variables in the equation Equation 3.2.7 equal to 0 and used Lemma 3.2.3 to count the number of solutions to the resulting equation, for each t, 1 ≤ t ≤ 2h − 1. We can further bound the above expression by D2h−1,m nh−1 · 22h . After a short calculation, we see that the total possible number of solutions in A2h to Equation 3.2.7 for arbitrary A is therefore ≤ exp(h49h m)nh if n is sufficiently large. We have therefore proved: Lemma 3.2.4. Let A ⊂ C be finite, and let dim× (A) = m. Then for every h ∈ N there exists n sufficiently large that if |A| ≥ n then the number of additive 2h-tuples 85 in A is bounded above by exp(h49h m)nh . Combining this with Lemma 3.2.2 we obtain Proposition 3.2.1. Ch (m+1)) Remark 3.2.1. The above lemma was proved with the bound e(−h nh for some undetermined constant C by Chang in [10]. In fact, Chang’s result is someCh (m+1)) what stronger, with a bound of the form Oh (nh + e(−h nh−1 ). Since using this form of the bound makes the following estimates more complicated with no quantitative gains in the final result, we will not use it here. 3.3 Simple sums and simple products We are now in a position to consider simple sums and simple products constructed from a finite set A ⊂ C. The proof of Theorem 3.1.1 is similar to that for the integer case, given in [8]. When working with subsets of the complex plane, however, we use our revised definition of multiplicative dimension Equation 3.2.1 and the bound in Lemma 3.2.4. For a finite set A ⊂ C let g(A) = |A+ | + |A× |. Then for each positive integer n, we have gC (n) = minA⊂C, |A|=n g(A), and it is sufficient to show that for any ε > 0 and an arbitrary set A of sufficiently large size n we necessarily have g(A) ≥ n (1/200−ε) loglogloglog(n) log(n) . We begin by showing that a large proportion of the iterated sumset hA is included in the set |hA ∩ A+ |. Lemma 3.3.1. Let A ⊂ C be finite with dim× (A) = m and such that |A| is sufficiently large. Then for any sufficiently large h ∈ N with h ≤ |A| we have |hA ∩ A+ | ≥ |A|h . exp(h50h m) Proof. This follows exactly as in [8]. First we observe that the left hand side is at least as large as the number of simple sums with exactly h summands. Letting rhA (x) = |{(a1 , . . . , ah ) ∈ Ah : a1 + · · · + ah = x}| 86 we have |A| ≤ ∑ rhA (x). h x∈hA∩A+ (3.3.1) Using Stirling’s formula in the form N! ≈ N N+1/2 e−N on the left side we have |A| |A|! |A||A| = ≥ C h+1/2 |A|−h = C(|A|/h1+1/2h )h . h h!(|A| − h)! h |A| for an absolute constant C. Combining the previous two relations and applying the Cauchy-Schwartz inequality followed by Lemma 3.2.4 to the right side of Equation 3.3.1 we have 1/2 C(|A|/h + 1/2 1+1/2h h ≤ |hA ∩ A | ) ∑ 2 (rhA (x)) x∈hA∩A+ 49h ≤ |hA ∩ A+ |1/2 (exp(h m)|A|h )1/2 . since the bracketed sum after the first inequality is at most the number of additive 2h tuples in A. It follows that |hA ∩ A+ | ≥ C2 |A|h , h2h+1 exp(h49h m) and absorbing the constant C2 and the factor h2h+1 into the exponential (recalling h is large) we have |hA ∩ A+ | ≥ |A|h . exp(h50h m) ✷ The next step is to show that a set with small multiplicative dimension must have a large simple sum. Lemma 3.3.2. Let B ⊂ C, and suppose that dim× (B) = m. Then for any ε1 with 0 < ε1 < 1/50, there exists n = n(ε1 ) ∈ N sufficiently large such that if |B| ≥ 87 √ n and 1 − ε1 50 m≤ log log(n) log log log(n) then ε1 g(B) ≥ n 3 log log(n) log log log(n) . (3.3.2) Proof. We have g(B) > |B+ | ≥ |hB ∩ B+ | for any h ∈ N. Applying Lemma 3.3.1 to the right side we therefore have g(B) > |B|h exp(h50h m) provided h is sufficiently large. We take h = 1 log log(n1/2 ) 50 log log log(n) . Then 50h log(h) ≤ log log(n1/2 ) so exp(h50h m) ≤ nm/2 . But then we have g(B) > |B|h ≥ nh/2−m/2 nm/2 Recalling our condition on m and our choice of h and using the fact that n is large ✷ in terms of ε1 , we have the result. We now use the previous two lemmas to prove Theorem 3.1.1. Let ε > 0 be sufficiently small. Also, let A ⊂ C be finite with dim× (A) = m, and let ε1 , ε2 < ε. Let n = n(ε) be sufficiently large in terms of ε, and suppose |A| = n. We may assume without loss of generality that 0 ∈ / A. By Lemma 3.3.2 we may also assume without loss of generality that every √ subset B ⊂ A with |B| ≥ n satisfies dim× (B) ≥ 1 − ε1 50 88 log log(n) . log log log(n) (3.3.3) We therefore divide A into sets B1 , . . . , B √ n , each with size |Bi | ≥ √ n, and denote As = ∪si=1 Bi , so A √ n = A. Taking B = A in equation Equation 3.3.3 we apply Lemma 3.2.1 to conclude the existence of a map ν : zG → Zm for some coset zG of a subgroup G of C∗ which contains A and for some m ≥ (1/50 − ε1 ) loglogloglog(n) log(n) . Applying Equation 3.2.5 we have g(A) > |A× | ≥ 1 |ν(A)+ |. |A| (3.3.4) It will therefore be sufficient to prove the bound of Theorem 3.1.1 for |ν(A)+ |. Let ρ = 1 + n−1/2+ε2 . The proof now splits into two cases: first the case in which the simple sums of the sets ν(As ) grow quickly with s, followed by a complementary case in which we are able to effectively use the large multiplicative dimension of Bs for some s. First, if |ν(As ∪ Bs+1 )+ | > ρ|ν(As )+ | for every s, we can begin with A1 = B1 and iterate, gaining a factor of ρ each time, to get |ν(A)+ | > ρ √ n −1 √ n−2 √ |ν(B1 )| > ρ n. Hence, using (for x small) log(1 + x) > x − x2 /2 > x/2 we have √ 1 |ν(A)+ | > exp ( n − 2) log(ρ) + log(n) 2 √ 1 > exp ( n − 2)(1/2)n−1/2+ε2 + log(n) 2 ε2 > exp((1/2)n ) The last bound is much better than what we are ultimately trying to prove. We are therefore reduced to the case where |ν(As ∪ Bs+1 )+ | ≤ ρ|ν(As )+ | for some s. Let m = dim× (Bs+1 ), so m ≥ 1 50 89 − ε1 log log(n) log log log(n) by Equation 3.3.3. Now, since the sets Bi are disjoint, the sets ν(Bi ) are as well, so that ν(As ∪ Bs+1 )+ = (ν(As ) ∪ ν(Bs+1 ))+ = ν(As )+ + ν(Bs+1 )+ . (3.3.5) We therefore have |ν(As )+ + ν(Bs+1 )+ | ≤ ρ|ν(As )+ |, (3.3.6) so by the Pl¨unnecke-Ruzsa Inequality (Theorem 3.1.6) for any h ∈ N we have |(h + 1)ν(Bs+1 )+ − ν(Bs+1 )+ | ≤ ρh+2 |ν(As )+ |. (3.3.7) Let ν(Bs+1 ) = {b1 , . . . , bk }, and define the h-fold simple sum of ν(Bs+1 ) by k ν(Bs+1 )+ [h] := ∑ εi bi : εi ∈ {0, 1, . . . , h}, i = 1, . . . , k . i=1 Then the left hand side of Equation 3.3.7 is larger than |hν(Bs+1 )+ | ≥ |ν(Bs+1 )+ [h]| ≥ hm . (3.3.8) The second inequality here comes from looking at the h-fold simple sum of a linearly independent set in Rm chosen from ν(Bs+1 ), since by Lemma 3.2.1 (a), ν(Bs+1 ) is at least m-dimensional. We now take h = n1/2−ε2 , so that 1/2−ε2 +2 ρh+2 ≤ (1 + n−1/2+ε2 )n < exp((n1/2−ε2 + 2) log(1 + n−1/2+ε2 )) < e2 . (3.3.9) Combining Equation 3.3.7, Equation 3.3.8, and Equation 3.3.9, we have 90 |ν(As )+ | > e−2 hm log log(n) 1 −ε > e−2 n1/2−ε2 ( 50 1 ) log log log(n) . This proves the theorem. 3.4 3.4.1 Sums of distinct sets with small productset Bounding the multiplicative dimension in terms of the relative size of the productset In this section we begin to prove Theorem 3.1.3. Let A, B ⊂ C be finite, with |B| = C|A|, and suppose that |AB| < α|A|. In analogy with the proof of Theorem 3.1.2, our strategy is to use the condition |AB| < α|A| to bound the multiplicative dimensions of |A| and |B| in terms of α. However, we no longer have Freiman’s theorem at our disposal. Instead, we substitute for it with the following result of Ruzsa [37]. Theorem 3.4.1. ([37]) Let n ∈ N, and let X,Y ⊂ Rn be finite with |X| ≤ |Y |. Suppose dim(X +Y ) = n. Then we have |X +Y | ≥ |Y | + n|X| − n(n + 1) . 2 (3.4.1) We begin by translating the problem to the setting of Ruzsa’s result. Suppose 0 ∈ / A ∪ B, and let D = dim× (A ∪ B). Let GA∪B be a multiplicative group in C∗ of rank D which has a coset zGA∪B that contains A ∪ B. Then by Lemma 3.2.1 there is an injective map ν : zGA∪B → (ZD , +) ⊂ (RD , +). We set d = dim(ν(A) + ν(B)) ≥ max(dim ν(A), dim ν(B)) ≥ max(dim× (A), dim× (B)) (3.4.2) where the first inequality holds because ν(A) + ν(B) contains translates of both ν(A) and ν(B) and the second inequality follows from Lemma 3.2.1(a). Now, we may have d < D, so we cannot immediately apply Theorem 3.4.1. However, as mentioned ν(A) + ν(B) contains translates ν(A) + β and α + ν(B) for 91 α ∈ ν(A), β ∈ ν(B). Let Ad be the real affine space containing ν(A) + ν(B), and let γ ∈ Ad . Then Ad − γ is a subspace of RD of dimension d, and so there is an isomorphism η : (Ad − γ) → Rd . Setting X = η(ν(A) + β − γ) and Y = η(ν(B) + α − γ) we find that |X +Y | = |η(ν(A) + ν(B) + α + β − 2γ)| = |ν(A) + ν(B) + α + β − 2γ| = |ν(A) + ν(B)| ≤ 2|AB| (3.4.3) where in the last step we applied Lemma 3.2.1(b). In addition, we have dim(X +Y ) = d. (3.4.4) Combining Equation 3.4.2, Equation 3.4.3, and Equation 3.4.4 we have now proven the following. Lemma 3.4.1. Let A, B ⊂ C\{0} be finite. Then there exists d ≥ max(dim× (A), dim× (B)) and sets X,Y ⊂ Rd with |X| = |A| and |Y | = |B| such that dim(X +Y ) = d and |X +Y | ≤ 2|AB|. Theorem 3.4.1 now applies to the sets X and Y . Rewriting the result in terms of A and B by using the above lemma, we get Corollary 3.4.1. Let A, B ⊂ C\{0} be finite. Then there exists d ≥ max(dim× (A), dim× (B)) such that 2|AB| ≥ |B| + d|A| − d(d + 1) . 2 (3.4.5) In order to bound the multiplicative dimensions of A and B in terms of α, we need to handle the trailing term of −d(d + 1)/2. Since, recalling Equation 3.2.2, 92 dim(X +Y ) ≤ dim(X) + dim(Y ), we have |A| + |B| = |X| + |Y | ≥ d + 2. Then if we let K = (|A| + |B|)/(d + 2) we therefore have K ≥ 1. (3.4.6) We can now rewrite Corollary 3.4.1 in terms of α, C, and K. Lemma 3.4.2. Let A, B ⊂ C \ {0} be finite, with |B| = C|A| for some C > 1 and |AB| < α|A|, and let m = max(dim× (A), dim× (B)). Then there exists d ≥ m such that if K = |A|+|B| d+2 then m< 2α −C . 1 − CK (3.4.7) Proof. Let d ≥ m be any value given by the conclusion of Corollary 3.4.1. It suffices to prove the bounds for d. By Corollary 3.4.1 we have 2α|A| > 2|AB| ≥ |B| + d|A| − d(d + 1) . 2 Rearranging, 2α ≥ C + d − d(d + 1) . 2|A| Now, we have 2C|A| = 2|B| > |A| + |B|, so this gives 2α −C ≥ d − Cd(d + 1) C ≥ d 1− K(d + 2) K . ✷ Dividing, we see the result. For our application of this lemma, we need to avoid the singular behavior when K = C. The following will allow us to bound C/K away from 1. Lemma 3.4.3. Let d ∈ N be a sufficiently large integer and suppose that X,Y ⊂ Rd are sufficiently large and satisfy |Y | = C|X|, 1≤C 93 log2 |X| and dim(X +Y ) = d. Set K = (|X| + |Y |)/(d + 2). Then if K ≤ log2 |X| we have |X||Y | . log4 |X| |X +Y | (3.4.8) Proof. We begin by recalling Equation 3.2.3 to assert that dim(X ∪ Y ) = d. Hence there are linearly independent vectors x1 , . . . , xr and y1 , . . . , yd−r for some 1 ≤ r ≤ d and a point x0 ∈ X such that x0 + xi ∈ X for 1 ≤ i ≤ r and x0 + y j ∈ Y for 1 ≤ j ≤ d − r. First, suppose that r ≥ d/2. Then let Y be any subset of Y with |Y | = |Y |/(8 log2 |X|) . Note that |Y | ≥ |X|, so |Y | = 0 since |Y | is taken to be sufficiently large, but that (from the definition of K) |Y | ≤ (d + 2)/8 = d/8 + 1/4 < d/4. Hence we may choose X ⊂ x0 + {x1 , . . . , xr } such that |X | = d/4 ≥ |Y | ≥ |X|/(16 log2 |X|) and such that the spans of X − x0 and Y − x0 do not intersect. Since x + y = x + y implies y − y = x − x, it follows that |X +Y | ≥ |X +Y | (|X|/(25 log2 |X|))(|Y |/(25 log2 |X|)). If r ≤ d/2, then d − r ≥ d/2, and the argument is the same with the sets ex✷ changed. The following summarizes the results of this section as they will apply in the proof of Theorem 3.1.3: Proposition 3.4.1. Let A, B ⊂ C \ {0} be finite with |A| sufficiently large, and suppose that |B| = C|A| for some 1 ≤ C α log2 |A| and |AB| < α|A|. Assume that log |A|. 94 and let m = max(dim× (A), dim× (B)). Then m < 4α Proof. By Lemma 3.4.1 there is d ≥ max(dim× (A), dim× (B)) and sets X,Y ⊂ Rd with |X| = |A| and |Y | = |B| such that |X +Y | ≤ 2|AB| ≤ 2α|A| 2|A| log |A|. Letting K = (|X| + |Y |)/(d + 2) = (|A| + |B|)/(d + 2), Lemma 3.4.3 therefore implies that K > log2 |X|. Now, by Lemma 3.4.2 we have m< 2α −C , 1 − CK and since C|A| = |B| ≤ |AB| ≤ α|A| we get C log |A|. Hence C/K ≤ 1/2 since |A| is sufficiently large and we get m< 2α −C < 4α. 1 − 12 ✷ With Propostion Proposition 3.4.1 proven, we could proceed by induction (albeit with more bookeeping) as in Section 2 (or [10]) to complete the proof of Theorem 3.1.3. However, the alternative proof in the next section leads to a better dependence on the numbers of iterates k and l. 95 3.4.2 Conclusion of the proof of Theorem 3.1.3 We have once again reduced our problem involving the relative productset size |AB|/|A| into one involving multiplicative dimension. Theorem 3.1.3 is now a corollary of the following lemma. Lemma 3.4.4. Let A, B ⊂ C be finite sets and suppose that |B| = C|A| for some C > 1. Let m = max(dim× (A), dim× (B)), and let k, l ∈ N0 . Assume that m such that |kA + lB| ≥ c1 log |A|. Then there is an absolute constant c1 |A|k |B|l − Ok,l,m (|B|k+l−1 ) (k + l)4(k+l) 15(k+l) m where the implicit constant in the O term can be taken as c2 e(k+l) for an absolute constant c2 . Lemma 3.4.4 will in turn follow from a lemma which places slightly stronger hypotheses on the sets A and B, with small losses in the k and l dependence when these hypotheses are removed. Lemma 3.4.5. Let A, B ⊂ C \ {0} be finite sets and suppose that |B| = C|A| for some C > 1. Let m = max(dim× (A), dim× (B)), and let k, l ∈ N0 . Assume that m log |A|. In addition, suppose that / A ∩ (−A) = B ∩ (−B) = A ∩ B = A ∩ (−B) = 0. Then |kA + lB| ≥ |A| k (3.4.9) |B| − Ok,l,m (|B|k+l−1 ) l 15(k+l) m where the implicit constant in the O term can be taken as ce(k+l) for an absolute constant c. Once we have Lemma 3.4.5 we can arrive at Lemma 3.4.4 as follows. Let A, B ⊂ C be finite, and suppose that they do not satisfy one or more of the hypothe96 ses in Equation 3.4.9. First, we let A and B be such that A ⊂A B ⊂B |A | ≥ |A|/4 |B | ≥ |B|/4 a ∈ A =⇒ −a ∈ /A b ∈ B =⇒ −b ∈ /B If |A ∩ B | < |B |/2, we let A =A, B = B \A . Next, if in addition |A ∩ (−B )| < |B |/2, we let A =A , B = B \ (−A ), k = k, l = l, and Lemma 3.4.5 applies with A in place of A, B in place of B, k in place of k, and l in place of l to give |kA + lB| ≥ ≥ |k A + l B | |A | |B | − Ok,l,m (|B|k+l−1 ) k l |A|k |B|l − Ok,l,m (|B|k+l−1 ) 16k+l kk l l which is better than the bound in Lemma 3.4.4. On the other hand, if in addition |A ∩ (−B )| ≥ |B |/2, we let A = A ∩ (−B ), k = k + l, l = 0. Then Lemma 3.4.5 applies with A in place of A, k in place of k, and l in place of l to give |kA + lB| ≥ ≥ |k A | |A | − Ok,l,m (|B|k+l−1 ) k+l |B|k+l − Ok,l,m (|B|k+l−1 ) 16k+l (k + l)(k+l) 97 Lastly, if |A ∩ B | ≥ |B |/2 then we let A = A ∩B , k = k + l, l = 0. Then Lemma 3.4.5 applies with A in place of A, k in place of k, and l in place of l to give |kA + lB| ≥ ≥ |k A | |A | − Ok,l,m (|B|k+l−1 ) k+l |B|k+l − Ok,l,m (|B|k+l−1 ) 8k+l (k + l)(k+l) In any of the above cases we have the bound in Lemma 3.4.4. Notice in particular that the above computations did not worsen the constant in the O term. It remains to prove Lemma 3.4.5. To proceed, we introduce some notation. Let Ak denote the k element subsets of A and let Bl denote the l element subsets of B. That is, Ak = {S ⊂ A : |S| = k} Bl = {T ⊂ B : |T | = l}. Next, for each x ∈ kA + lB, let Sx = (S, T ) ∈ Ak × Bl : ∑ a+ ∑ b = x a∈S . b∈T Observe that |kA + lB| ≥ |Ak ||Bl | − | ∪x∈kA+lB Ex |, (3.4.10) where Ex = (S, T ), (S , T ) ∈ Sx × Sx : (S, T ) = (S , T ) . Denote the union on the right side of Equation 3.4.10 by E. The first term in Equation 3.4.10 has size 98 |A| k |B| l , so we have only to estimate |E|. It is sufficient to prove the following bound: 15(k+l) m |E| ≤ ce(k+l) |B|k+l−1 . (3.4.11) We will have use of the following definition: Definition 3.4.1. Let M be an r by n complex matrix with at least one nonzero entry in every column. Denote the entry in the ith row and jth column of M by Mi j . Then for any b ∈ C we say that a = (a1 , ..., an ) ∈ Cn is a nondegenerate solution of Mx = b if it is a solution such that for each i, 1 ≤ i ≤ r there is no proper subset J of { j : 1 ≤ j ≤ n, Mi j = 0} such that ∑ j∈J Mi j a j = 0. We can use Theorem 3.1.4 to show that, within a finite subset of a low-rank multiplicative subgroup of (C∗ )n , there are not many solutions to a system of equations. Lemma 3.4.6. Let M be an r by n complex matrix, and let Y be a finite set contained in a subgroup of C∗ of rank s. Then there are at most exp((6n)3n (ns + 1))|Y | r nondegenerate solutions to Mx = 0 in Y n . Proof. Letting the component of M in the ith row and jth column be Mi j , we can rewrite Mx = 0 as n 1 ≤ i ≤ r. ∑ Mi j x j = 0, (3.4.12) j=1 Now, let J(i) = max{ j : Mi j = 0}. Then, fixing a value of xJ(i) for each i, say xJ(i) = Yi ∈ Y , we can rearrange Equation 3.4.12 to get n−1 Mi j ∑ −MiJ(i)Yi y j = 1, 1 ≤ i ≤ r. (3.4.13) j=1 For each nondegenerate solution (y1 , ..., yn ) of Equation 3.4.12 with yJ(i) = Yi for each i, there corresponds an r-tuple (z1 , ..., zr ) such that zi ∈ Y n−1 is a nondegenerate solution of the ith equation in Equation 3.4.13 with (zi ) j = 0 for all indices j 99 such that Mi j = 0 and (zi ) j = y j otherwise. As well, this correspondence is one-toone, so we need only count the number of such r-tuples. However, for a fixed i, the nonzero components of zi make up a nondegenerate solution of the equation ∑ 1≤ j≤n−1 Mi j =0 Mi j x j = 1. −MiJ(i)Yi 3n (ns+1) Now Theorem 3.1.4 applies, and we see that for a fixed i there are at most e(6n) possibilities for zi . Hence the number of r-tuples (z1 , ..., zr ) is this value raised to the rth power. Since there are |Y | choices for Yi , i = 1, ..., r, this gives the result of ✷ the lemma. To prove Equation 3.4.11, we would like to use the above lemma to count elements of E. To do so, we will first demonstrate a low-multiplicity correspondence between E and nondegenerate solutions of Mx = 0 for a small number of matrices M. Such will be the content of the next lemma. Lemma 3.4.7. Let A, B ⊂ C \ {0} satisfy the hypotheses of Lemma 3.4.5. Let M be the set of matrices with r ≤ k + l − 1 rows and 2k + 2l columns and with each column containing exactly one nonzero entry, which is one of the values ±1. Lastly, let Z = x ∈ (A ∪ B)2k+2l : x is a nondegenerate solution of Mx = 0 for some M ∈ M . Then with E as in Equation 3.4.10 we have |E| ≤ (2k)!(2l)!|Z|. Proof. By definition of E, for each element (S, T ), (S , T ) of E we have ∑ a+ ∑ b = ∑ a + ∑ a∈S b∈T a ∈S b. b ∈T Choose any ordering of the elements of each of the sets S, S , T, T , say S = {c1 , ...ck }, S = {ck+1 , ..., c2k }, T = {c2k+1 , ..., c2k+l }, and T = {c2k+l+1 , ..., c2k+2l }. This gives a one-to-one correspondence between E and a subset of the solutions in 100 (A ∪ B)2k+2l of the equation x1 + ... + xk − xk+1 − ... − x2k + x2k+1 + ... + x2k+l − x2k+l+1 − ... − x2k+2l = 0. (3.4.14) Let di denote the ith coefficient in the expression Equation 3.4.14; then for 1 ≤ i ≤ k and 2k + 1 ≤ i ≤ 2k + l we have di = 1, whereas for k + 1 ≤ i ≤ 2k and 2k + l + 1 ≤ i ≤ 2k + 2l we have di = −1. Now, there is a partition of {1, 2, ..., 2k + 2l} into sets J1 , ..., Jr such that ∑ d j c j = 0, 1≤t ≤r ∑ d j c j = 0, 1≤t ≤r (3.4.15) j∈Jt and j∈Jt / for each proper subset Jt ⊂ Jt with Jt = 0. Let M be the matrix of the system Equation 3.4.15 (so the entry in row t and column j is d j if j ∈ Jt and is 0 otherwise). Then (c1 , ..., c2k+2l ) is a nondegenerate solution of the system Mx = 0. Recalling that 0 ∈ / A ∪ B, we see that each of the equations in Equation 3.4.15 has at least two terms on the left. Furthermore, applying Equation 3.4.9 and the condition that (S, T ) = (S , T ) one equation must have at least three. It follows that M has at most k + l − 1 rows, and hence (c1 , ..., c2k+2l ) ∈ Z. The desired correspondence therefore takes (S, T ), (S , T ) to the constructed value of (c1 , ..., c2k+2l ). It remains only to show that this correspondence above has low multiplicity. But any particular (2k + 2l)-tuple (c1 , ..., c2k+2l ) ∈ Z is mapped to from at most (2k)!(2l)! elements of E, one for each possible rearrangement of the components ✷ c1 , ..., c2k+2l . This gives the result. Now, applying Lemma 3.4.6 and Lemma 3.4.7 to sets A and B satisfying the hypotheses of Lemma 3.4.5, we find that |E| ≤ (2k)!(2l)! 2 exp (12(k + l))6(k+l) ((2k + 2l)(m + 1) + 1) |B| k+l−1 |M |. (3.4.16) 101 But we certainly have 2 |M | ≤ 3(2k+2l) , (3.4.17) since each element of M is a matrix with three possible values for each entry and with fewer than 2k + 2l rows and 2k + 2l columns. Combining Equation 3.4.16 and Equation 3.4.17 and absorbing extraneous factors into a single dominating ✷ constant, we have Equation 3.4.11, and Lemma 3.4.5 follows. Now, let A, B ⊂ C be finite, with |B| = C|A|, and suppose that |AB| < α|A|. Fix integers k and l, and assume that α log |A|. By Lemma 3.4.4, there are absolute constants c1 and c2 such that we have |kA + lB| ≥ 15(k+l) m c1 |A|k |B|l − c2 e(k+l) |B|k+l−1 4(k+l) (k + l) where m = max (dim× (A), dim× (B)). By Proposition 3.4.1 we have m < 4α. Substituting this into Equation 3.4.18, we have proved Theorem 3.1.3. 102 (3.4.18) Chapter 4 Conclusion 4.1 Overview of the results in the context of current research The most prominent recurring theme in arithmetic combinatorics is that there can be arithmetic structure in a set if and only if there is geometric structure in it. The results described in this thesis and their proofs are distinctly reminiscent of this underlying concept. Indeed, while all of our main results, and the arguments used to prove them, fit the framework described above, they may be further divided into two finer classes of phenomena: first, the behaviour of the integer primes as a uniform set, and second, the fact that all sets are either approximately additive subgroups or else are approximately multiplicative subgroups. We will separately describe each of these classes of results and the manner in which the theorems of this thesis fit in. 4.1.1 Uniformity of primes In Section 1.4.2 we discussed the arithmetic behaviour of random sets. Later, in Section 1.5.2, we described the sense in which the primes may be considered to be somewhat randomly distributed. In fact, the interplay between these two heuristics has a long history of investigation through results on the distribution of primes, as was discussed in the introduction. 103 Theorem 1.2.1 is an interesting theoretical result on its own, insofar as it is a very basic statement about the additive structure of the primes, which have been studied intensely by mathematicians throughout the history of the subject. Moreover, there is a clear connection between our result and one of the oldest problems in number theory, the Goldbach conjecture (Conjecture 1.1.4). While we make no claim that our result constitutes direct progress towards proving the above statement, it is a valuable addition to a large body of other partial results on the topic (see, for example, the collection of papers in [50]. Our argument for reducing the primes problem to that in multiplicative subgroups of finitely generated abelian groups uses Green’s formal treatment of the primes as a uniform set. However, previous results which have used these methods have been primarily focused towards proving existence theorems for finite configurations of particular shapes within subsets of positive relative upper density. For these purposes, it is enough to consider a single residue class on which the subset has high density, and to locate the configuration in question within this residue class. In contrast, when trying to compute lower bounds on the sumset of a subset of primes, we were forced to consider several residue classes at once in order to even prove that the sumset would have positive density in the integers; looking at a single residue class, the best that one could hope to show with Green’s approach is that, for a subset A of primes of positive upper relative density δ, we will have An + An ≥ δn/m(n), where m(n) → ∞ arbitrarily slowly as n → ∞. Of course, this does not even rule out the possibility that A + A has density 0. This result appears to be the first which required this approach. However, it is clear that if one hopes to deal with problems involving configurations of primes such as that in the twin primes conjecture, then one will encounter multiple residue classes modulo large integers m of the form considered (although it remains to be seen if viewing the primes (mod m) will play a role in any proof). Indeed the strongest results on configurations in primes fall just short of proving this conjecture. Similarly, one cannot prove the Goldbach conjecture by restricting to single residue classes: there are arbitrarily large even integers N which are not in the residue class 2b (mod m) for any b (mod m), since 2|m. 104 In addition, the fact that we can reduce the problem to Theorem 1.2.2 without any loss in density indicates that it is the structure of Z∗N which underlies the nonuniformity of the primes, at the very least in the context of this problem. If this applies in a larger context, it would be an important theoretical result, and might also have wide reaching applications to the distribution of primes. Lastly, we do not believe that our bounds in Theorem 1.2.1 and Theorem 1.2.2 are actually sharp, and it seems that it will likely be difficult to improve the argument used to prove Theorem 1.2.2. Instead, an entirely new approach may more easily shed extra light on this problem. With our conjecture on the form that sharp bounds in our theorems might take, we have hopefully been successful in motivating further interest in this line of research. 4.1.2 Sums and products The idea that all finite subsets of complex numbers behave closely to either an arithmetic or a geometric progression is captured by the sum-product conjecture and its many proven variants. In terms of the variant types described in Section 1.3.5, Theorem 1.2.3 is seen to be a sum-product theorem for distinct sets in exotic rings (the complex numbers, which admittedly are less exotic than some other variants), which uses a small productset to show that the iterated sumsets must be large. It therefore combines four of the variants mentioned. Moreover, with the exception of the small productset implies large sumset theme, all of these variations contribute to the result applying in a more general setting than the original sum product conjecture. Meanwhile, Theorem 1.2.4 is seen to be a sum-product theorem for simple sums and simple products in the complex setting, and quantifies a result of Chang [9]. The most interesting thing about our new results may be how they transfer Chang’s strategy of applying unique factorisation in the integers to the complex numbers, through the use of elementary group theory. This is a reasonably general approach, as multiplicative dimension can be defined for finite subsets of arbitrary rings. In addition, one might speculate that it could be used in instances where unique factorisation has been used to investigate sum-product problems and perhaps provide generalisations of such results, most notably one of Bourgain and 105 Chang [2]. Neither of our new results is likely to be as strong as one might hope to prove; in Section 1.3.5, the condition |AB| ≤ |A| log(|A|) can likely be improved to one of the form |AB| ≤ |A|1+ε , in keeping with other results of the small productset implies large sumset flavour. On the other hand, there is no clear reason why we should not be able to prove a lower bound in Theorem 3.1.1 as strong as that in Chang’s analogous result in the integers. Both of our current quantitative results are weakened by the use of the Subspace theorem, and this theorem is similarly believed to fall short of the best possible. 4.2 Possible future directions In this section, we describe some of the immediate future directions of research which are suggested by the results of this thesis: sharp bounds in Theorem 1.2.1, weaker conditions in Theorem 1.2.3, and the sharp lower bound in Theorem 1.2.4. 4.2.1 A sharp bound in Theorems 1.2.1 and 2.1.3 We begin by recalling a pair of constructions from in Section 2.1 in further detail, and in a more organised fashion. We will then discuss what these constructions suggest in terms of sharp bounds for Theorem 1.2.1. Our first construction can be restated in terms of the following theorem. Theorem 4.2.1. For every ε > 0 there is A ⊂ P such that A has upper relative density δ < ε in P but A + A has density smaller than δ log log(1/δ) in the natural numbers. We recall that the set A mentioned in this theorem is {p ∈ P : p ≡ 1 (mod m)} for m a product of consecutive primes. Theorem 4.2.1 only tells us that we can not expect to do better than the given bound; it does not illustrate the intuition behind why we might expect this bound to be sharp. Rather, this is left to the next example. 106 Theorem 4.2.2. For every ε > 0 there is a set A ⊂ Z∗m with |A| = δϕ(m) for some δ < ε such that |A + A| ≤ (δ/ log log(1/δ))m Now, if we recall Freiman’s theorem (Theorem 3.1.5), if we want A ⊂ Z∗m to have minimal sumset, then we will need to efficiently place A within a low dimensional generalised arithmetic progression. Meanwhile, from the discussion in Section 2.1, the construction in Theorem 4.2.2 is in fact a generalised arithmetic progression within Z∗m , and moreover by choosing the first t coordinates to be the ones which remain fixed, we have minimised the dimension (subject to the constraint that A have density δ = 1/ϕ(p1 ...pt )). We are therefore led to ask the following. Question 4.2.1. Is it true that if A ⊂ Z∗m satisfies |A| ≥ δϕ(m), then we must have |A + A| ≥ (δ/ log log(1/δ))m In light of the connection between results of this type in P and those in Z∗m , we would then hope to answer the following. Question 4.2.2. Is it true that if A ⊂ P has positive upper relative density δ, then A + A must have positive upper density larger than δ/ log log(1/δ) in the natural numbers? 4.2.2 Weaker conditions in Theorem 3.1.3 The condition |AB| ≤ α|A| in Theorem 3.1.3 is seen in virtually all sum product theorems of the small productset implies large sumset type. However, the requirement that α log |A| 107 is more stringent than what appears in Chang’s result in the integer setting. Rather, she found that, to get near-optimal lower bounds on |kA| for A a subset of integers, she only needed β |A|ε , where β = |A · A|/|A|. It therefore appears likely that we should be able to give an affirmative answer to the following question. Question 4.2.3. Can we prove the result in Theorem 3.1.3 if we only require α |A|ε for some ε > 0? In this case, the right hand side of the inequality in Theorem 3.1.3 would almost certainly contain an additional dependence on ε. It is worth mentioning again that the logarithmic bound on α is a direct consequence of our reliance on the subspace theorem. It is expected that an improvement to that theorem would lead to improvement in Theorem 1.2.3. 4.2.3 Sharp bounds for simple sums and products, and minimising examples for sum-product variants In [8] Chang considered simple sums and simple products of subsets of integers; a construction of Erd˝os and Szemer´edi [17] shows that her bound on gZ (n) is approximately sharp. Theorem 4.2.3. For infinitely many integers n there is a set A ⊂ N of n elements such that log n |A+ | + |A× | ≤ 2n(1−ε) log log n Since A is a set of integers, it follows that it is also a subset of complex numbers. However, there remains a large gap between this example and the bound in Theorem 1.2.4. It is therefore natural to ask the following Question 4.2.4. What is the sharp lower bound on gC (n)? Are there sets An of n complex numbers such that log n |A+ | + |A× | = o(2n(1−ε) log log n ), 108 or does the integer example minimise gC ? Chang’s construction used her concept of multiplicative dimension in terms of unique prime factorisation to help define this set, by taking the dimension of A to not be too small; it seems plausible that we could impose a similar condition using the version of dimension defined in order to prove Theorem 3.1.1. However, Chang also used the ordering of the integers to place a bound on the number of simple sums, by pointing out that her set is contained in a sufficiently short interval. Any resolution of the above question will require a new approach which overcomes the fact that the complex numbers are not ordered in this manner. This may also shed light on such minimising constructions for alternative variants of the sum-product problem. 109 Bibliography [1] S. Backman, E. Croot, M. Hamel, and D. Hart. Sum-product inequalities with perturbation. Proceedings of the Integers Conference 2009 (to appear). [2] J. Bourgain and M.-C. Chang. On the size of k-fold sum and product sets of integers. J. Amer. Math. Soc., 17:473–497, 2004. [3] J. Bourgain and M.-C. Chang. Sum-product theorem and exponential sum estimates in residue classes with modulus involving few prime factors. C.R. Acad. Sci. Paris, Ser. I, 339:463–466, 2004. [4] J. Bourgain, N. Katz, and T. Tao. A sum-product estimate for finite fields, and applications. GAFA, 14:27–57, 2004. [5] J. Bourgain, A. Glibichuk, and S. Konyagin. Estimates for the number of sums and products and for exponential sums in fields of prime order. J. London Math. Soc., 2(73):380–398, 2006. [6] M.-C. Chang. A polynomial bound in Freiman’s theorem. Duke Math. J., 113:399–419, 2002. [7] M.-C. Chang. Factorization in generalized arithmetic progressions and applications to the Erd¨os-Szemer´edi sum-product problems. GAFA, 113: 399–419, 2002. [8] M.-C. Chang. Erd¨os-Szemer´edi problem on sum set and product set. Annals of Math., 157:939–957, 2003. [9] M.-C. Chang. On sums and products of distinct numbers. J. Combin. Theory Ser. A, 105(2):349–354, 2004. [10] M.-C. Chang. Sum and product of different sets. Contrib. Discrete Math., 1 (1):47–56, 2006. 110 [11] M.-C. Chang. Additive and multiplicative structure in matrix spaces. Comb. Prob., 16(2):219–238, 2007. [12] M.-C. Chang and J. Solymosi. Sum-product theorems and incidence geometry. J. Eur. Math. Soc., 9(3):545–560, 2007. [13] K. Chipeniuk. Sums and products of distinct sets and distinct elements in C. Integers, 10:639–667, 2010. [14] K. Chipeniuk and M. Hamel. On sums of sets of primes with positive relative density. J. London Math. Soc. (to appear). [15] E. Croot and D. Hart. k-fold sums from a set with few products. SIAM J. Discrete Math. (to appear). [16] G. Elekes. On the number of sums and products. Acta. Arith., 81:365–367, 1997. [17] P. Erd˝os and E. Szemer´edi. On sums and products of integers. In Studies in Pure Mathematics, pages 213–218. Birkh¨auser, Switzerland, 1983. [18] P. Erd˝os and P. Tur´an. On some sequences of integers. J. London Math. Soc., 11:261–264, 1936. [19] J.-H. Evertse, H. Schlickewei, and W. Schmidt. Linear equations in variables which lie in a multiplicative group. Annals of Math., 155(3):807–836, 2002. [20] K. Ford. Sums and products from a finite set of real numbers. Ramanujan J., 2:59–66, 1998. [21] G. Freiman. Foundations of a structural theory of set addition. Kazan Gos. Ped. Inst., Kazan, 1966 (Russian). English translation in Translations of Mathematical Monographs 37, American Mathematical Society, Providence, 1973. [22] H. Furstenberg. Ergodic behavior of diagonal measures and a theorem of Szemer´edi on arithmetic progressions. J. d’Analyse Math, 71:204–256, 1977. [23] T. Gowers. A new proof of Szemer´edi’s theorem for arithmetic progressions of length four. GAFA, 8:529–551, 1998. [24] T. Gowers. A new proof of Szemer´edi’s theorem. Geom. Funct. Anal., 11 (3):465–588, 2001. 111 [25] B. Green and T. Tao. An equivalence between inverse sumset theorems and inverse conjectures for the U 3 -norm. Math. Proc. Camb. Phil. Soc., 149(1): 1–19, 2010. [26] B. Green, T. Tao, and T. Ziegler. An inverse theorem for the Gowers us+1 [n]norm. Preprint, 2010. [27] B. J. Green. Roth’s theorem in the primes. Annals of Math., 161:1609–1636, 2005. [28] B. J. Green and T. Tao. Restriction theory of the Selberg sieve, with applications. Journal de Th´eorie des Nombres de Bordeaux, 18:147–182, 2006. [29] B. J. Green and T. Tao. The primes contain arbitrarily long arithmetic progressions. Annals of Math., 167:481–547, 2008. [30] B. J. Green and T. Tao. Linear equations in primes. Annals of Math., to appear. [31] M. Hamel and I. Laba. Arithmetic structures in random sets. Integers, 8: A04, 2008. [32] D. Hart, A. Iosevich, and J. Solymosi. Sum-product estimates in finite fields via Kloosterman sums. International Mathematics Research Notices, 2007: Article ID rnm007, 2007. [33] Y. Kohayakawa, T. Łuczak, and V. R¨odl. Arithmetic progressions of length three in subsets of a random set. Acta. Arith., 75:133–163, 1996. [34] H. Montgomery and R. Vaughan. Multiplicative number theory I. Classical theory. Cambridge University Press, Cambridge, UK, 2007. [35] M. Nathanson. On sums and products of integers. Proc. Amer. Math. Soc., 125:9–16, 1997. [36] K. Roth. On certain sets of integers. J. London Math. Soc., 28:245–252, 1953. [37] I. Z. Ruzsa. Sum of sets in several dimensions. Combinatorica, 14(4): 485–490, 1994. [38] I. Z. Ruzsa. Sums of finite sets. In Number Theory (New York, 1991-1995). Springer-Verlag, New York, 1996. 112 [39] J. Solymosi. On the number of sums and products. Bull. London Math. Soc., 37(4):491–494, 2005. [40] J. Solymosi. An upper bound on the multiplicative energy. Advances in Mathematics, 222(2):402–408, 2009. [41] E. Szemer´edi. On sets of integers containing no four elements in arithmetic progression. Acta. Math. Acad. Sci. Hung., 20:89–104, 1969. [42] E. Szemer´edi. On sets of integers containing no k elements in arithmetic progression. Acta. Arithmetica., 27:199–245, 1975. [43] T. Tao. The sum-product phenomenon in arbitrary rings. Contrib. Discrete Math., to appear. [44] T. Tao and V. Vu. Additive Combinatorics. Cambridge University Press, Cambridge, UK, 2006. [45] H. Thai. Intersective polynomials and the primes. Preprint, 2009. [46] J. van der Corput. Uber summen von primzahlen und primzahlquadraten. Math. Ann., 116:1–50, 1939. [47] B. van der Waerden. Bewels einer Baudetschen Vermutung. Nieuw. Arch. Wisk., 15:212–216, 1927. [48] P. Varnavides. On certain sets of positive density. J. London Math. Soc., 34: 358–360, 1959. [49] R. Vaughan. The Hardy-Littlewood method. Cambridge University Press, Cambridge, UK, 1997. [50] Y. Wang. The Goldbach conjecture. World Scientific Publishing Co. Pte. Ltd., Singapore, 2002. 113
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Structure and arithmetic in sets
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Structure and arithmetic in sets Chipeniuk, Karsten 2011
pdf
Page Metadata
Item Metadata
Title | Structure and arithmetic in sets |
Creator |
Chipeniuk, Karsten |
Publisher | University of British Columbia |
Date Issued | 2011 |
Description | We prove results in arithmetic combinatorics involving sums of prime numbers and also some variants of the Erdös-Szemerédi sum-product phenomenon. In particular, we prove nontrivial lower bounds on the density in the integers of the sumset of a positive relative density subset of the primes. The proof of this result uses Green and Green-Tao pseudorandomness arguments to reduce the problem to an analogous statement for relatively dense subsets of the multiplicative subgroup of integers modulo a large integer N. The latter statement is resolved with a combinatorial argument which bounds high moments of a representation function. We also show that if two distinct sets A and B of complex numbers have very small productset, then they produce maximally large iterated sumsets. This uses an algebraic concept of the multiplicative dimension of a finite set. As an application of the case A=B, we obtain a quantitative version of a result of Chang on sums and products of distinct complex elements. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-04-15 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0071705 |
URI | http://hdl.handle.net/2429/33674 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2011-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2011_spring_chipeniuk_karsten.pdf [ 595.22kB ]
- Metadata
- JSON: 24-1.0071705.json
- JSON-LD: 24-1.0071705-ld.json
- RDF/XML (Pretty): 24-1.0071705-rdf.xml
- RDF/JSON: 24-1.0071705-rdf.json
- Turtle: 24-1.0071705-turtle.txt
- N-Triples: 24-1.0071705-rdf-ntriples.txt
- Original Record: 24-1.0071705-source.json
- Full Text
- 24-1.0071705-fulltext.txt
- Citation
- 24-1.0071705.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-0071705/manifest