Data Loading...
Sum-product inequalities with perturbation Flipbook PDF
Sum-product inequalities with perturbation Dedicated to Mel Nathanson and Carl Pomerance on the occasion of their 65th b
114 Views
67 Downloads
FLIP PDF 112.91KB
Sum-product inequalities with perturbation Dedicated to Mel Nathanson and Carl Pomerance on the occasion of their 65th birthdays Spencer Backman Ernie Croot Mariah Hamel Derrick Hart April 30, 2010
1
Introduction
The standard sum-product inequality, as developed by Erd˝os and Szemer´edi [4], and improved upon by Elekes [3], Ford [5], Nathanson [6], and Solymosi [8] [9], asserts that there exists some ε > 0 such that if A is a set of n real numbers (though Erd˝os and Szemer´edi originally proved their theorem for A ⊆ Z), then |A + A| + |A.A| ≥ n1+ε , whenever n > n0 .
(1)
There are various generalizations of this theorem to multiple sums and products, for example the following result of Bourgain and Chang [1]: Theorem 1 (Bourgain-Chang) For every c > 0 there exists k ≥ 1 such that if S is a set of n ≥ 2 rationals, then |kS| + |S (k) | > nc , where kS denote the k-fold sumset S + S + · · · + S, and S (k) denotes the k-fold product set S.S...S. 1
Though this is a truly marvelous theorem, it would be nice to have it hold for the reals, instead of just the rationals. One is tempted to try the following idea: Start with T as a set of n reals, and then approximate each element t ∈ T by a rational st , and then let S := {st : t ∈ T } Bourgain-Chang will then show that either the k-fold sum or product set of S exceeds nc (assuming all the st are distinct, which we will). But does that then mean the same must hold true for T , at least if one chooses the approximations carefully? Alas, the answer to this question is not obvious. This problem of how robust sum-product theorems are under perturbation was partly what motivated the present paper, and we were able to prove a theorem in the case of a single sumset and product set (instead of k-fold ones, as in the Bourgain-Chang theorem). Now, of course, since we have sum-product theorems for the reals (in fact, the complex numbers) when a single sum and product are used, there is no need to bother with “perturbing” to the rational case; however, the theorem we prove is much more general than that. In fact, our theorem is general enough so that we can easily deduce a “rounded sum-product theorem” as a corollary, which basically tells us that either the sumset A + A is “small”; or else not only must A.A be “large” (which we already get from previous sum-product theorems), but in fact the elements of the product set A.A cannot “clump together too often”. The following is one such corollary: Corollary 1 Fix 0 < ε ≤ 1, and suppose that A is a set of n real numbers, all at least a distance 1 apart from each other. Then, if one lets R denote the elements of the product set A.A rounded to the nearest multiple of n1−ε , then |A + A| + |R| ≫ n1+ε/9 / log n. To see what this is saying, suppose A is a subset of n numbers in [1, 2n], all at least 1 apart from each other. Then, the product set lies in [1, 4n2 ], and there are ∼ 4n1+ε multiples of the real number n1−ε in this interval. The corollary here is telling us that ≫ n1+ε/9 / log n of these multiples must be “near” to an element of A.A. The proof of this corollary is discussed after the remarks following Theorem 2 in the next section. 2
One wonders whether these types of ideas (sum-product inequalities with perturbation) can somehow be used to improve upon the results of Balog [2] on smooth numbers. Attempting such a feat with sum-product technology was another, hidden motivation behind the present paper, though the results we have developed so far are much too weak to say anything interesting on smooth numbers.
2
The Main Theorem
It is interesting to consider whether one can prove a finer version of (1), where one is allowed to “perturb” the products ab ∈ A.A a little bit: suppose that for each pair a, b ∈ A we get to choose “perturbation parameters” δa,b and ′ δa,b , where say ′ δa,b , δa,b ∈ [−1, 1]. Given these parameters, define the “perturbed product set” ′ P := {(a + δa,b )(b + δa,b ) : a, b ∈ A}. ′ Must it be the case that for all choices of δa,b , δa,b we get that
|A + A| + |P | ≥ n1+ε ? The answer is obviously ‘no’, since if the elements of A are close enough ′ together, and are in arithmetic progression, we can easily choose δa,b and δa,b so that |A + A| + |P | = 2n. But what if we add the condition that the elements of A are all spaced at least 1 apart? Can we show that |A + A| + |P | must always be large? Again the answer is ‘no’, but the natural example is a little more complicated. Basically, consider the arithmetic progression A := {x + 1, x + 2, ..., x + n}.
(2)
This set has the property that it is “close” to the geometric progression {x(1 + 1/x)j : j = 0, 1, ..., n − 1}. Indeed, x(1 + 1/x)j = x + j + O(j 2/x), 3
(3)
for x ≥ n. So, clearly, for x big enough relative to n we will have that if the ′ δa,b , δa,b are allowed to vary over [−1, 1], we can force P = A + A, thereby making |A + A| + |P | ≤ 4n − 2. ′ But we can give even better upper bounds on δa,b and δa,b that make ′ |P | + |A + A| small: first, set all δa,b = 0. Then suppose that a and b correspond to the numbers (3) using exponents j and k, respectively. Next, we choose δa,b ≪ n/x so that
(a + δa,b )b
= =
x2 (1 + j/x + O(j 2/x2 ) + δa,b )(1 + k/x + O(k 2 /x2 )) x2 (1 + (j + k)/x + δa,b + O(n2/x2 )).
So, if δa,b is the negative of this O(n2 /x2 ) < O(n/x), then the product will be just x2 (1 + (j + k)/x), meaning that we can make our perturbed product set into an arithmetic progression, making |P | + |A + A| ≪ n. So, to achieve a lower bound on |P | + |A + A| that is substantially better ′ than the trivial bound, we will need that δa,b , δa,b can only vary over intervals that are width O(n/x). Our main theorem below will show that this is ′ essentially best possible, as the intervals for δa,b and δa,b leading to non1−ε 1−ε trivial results will have lengths n /a and n /b, respectively. Actually, our theorem is even more general, since following Remark 2 at the end of our theorem, the sumset A + A can also be perturbed, and still we get a good lower bound on the resulting perturbed sum and product sets. Our main theorem is as follows: Theorem 2 Suppose 0 < ε ≤ 1 and let A be a set of n > n0 (ε) positive real numbers, all at least 1 apart. For each pair (a, b) ∈ A × A, suppose that δa,b ′ and δa,b are arbitrary real numbers satisfying n1−ε n1−ε ′ |δa,b | < , and |δa,b | < . a b Finally, define the perturbed product set ′ P := {(a + δa,b )(b + δa,b ) : a, b ∈ A}.
Then, we have that |P | + |A + A| ≫ 4
n1+ε/9 . log n
(4)
Remark 1. Obviously, if the elements of A are not at least 1 apart, we can rescale to make it true. Furthermore, all we really need is that the median of the gaps between consecutive elements of A is at least 1, since by deleting at most n/2 elements from A we get a set of elements that are all at least 1 apart. Remark 2. From the proof one can show that if we also perturb the sums A + A, we have the same quality lower bound on the sums and products; ′′ that is, suppose we define S to be the set of all perturbed sums a + b + δa,b , ′′ 1−ε where |δa,b | ≤ n /(a + b). Then, we can show |P | + |S| ≫
n1+ε/9 . log n
(5)
See remarks at the end of the proof of Theorem 2 for a discussion of how this is proved. ′ Proof of Corollary 1. Given a pair a, b ∈ A with a ≤ b, we let δa,b =0 and then we select δa,b so that ′ (a + δa,b )(b + δa,b ) = (a + δa,b )b
is the nearest multiple of n1−ε to ab. It is possible to choose such δa,b , since this only requires |δa,b | < n1−ε /b, which is smaller than the upper bound of n1−ε /a that we are allowed.
3 3.1
Proof of Theorem 2 Preliminaries
We will basically follow a variant of Elekes’s original argument used to prove that if A is a set of n reals, then |A + A| · |A.A| ≫ n5/2 , from which it follows that |A + A| + |A.A| ≫ n5/4 . 5
But our approach will differ in that the Szemer´edi-Trotter theorem [11] is not directly amenable to our particular approach. Instead, we apply a very minor generalization of the Szemer´edi-Trotter curve theorem of Sz´ekely [10] (hardly any generalization at all), which follows by the same proof as that of Sz´ekely. Theorem 3 Suppose that one has a collection of ℓ non-self-crossing curves and p points. Let C denote the collections of curves. Let m1 denote the maximum over all pairs of points p1 , p2 , of the number of curves that are incident to both p1 and p2 , that pass through any given pair of points p1 , p2 , and let m2 denote the “average intersection multiplicity”, defined as follows −1 X ℓ |c1 ∩ c2 |. m2 := 2 {c1 ,c2 }⊆C
Then, the number of incidences I, which is the number of point-curve pairs, where the point is on the curve, satisfies I ≪ (m1 m2 )1/3 (pℓ)2/3 + ℓ + m1 p. The way this differs from the Szemer´edi-Trotter curve theorem in [10] is that m2 is the average intersection multiplicity among the curves, not an absolute upper limit on the intersection multiplicity between pairs of curves. The proof of Sz´ekely begins with the following result on the crossing number cr(G) of a multigraph G, as appears in [10, Theorem 7]. Theorem 4 Suppose that G is a multigraph with p nodes, e edges and edge multiplicity m. Then, either e < 5pm or cr(G) ≥ ce3 /(p2 m). Proof of Theorem 3. Now to prove Theorem 3 we construct a graph as follows: fix one of our ℓ curves, and consider which of our p points happens to lie on it. By choosing a direction with which to traverse the curve, we create an ordering of these incident points. If there are x such points on the given curve, then we form x − 1 curve segments that adjoin consecutive pairs of points. We throw away the “infinite parts” of the curves as they will play no further role in our proof. Letting I denote our total number of incidences, and e the number of edges in our graph, we will have e = I − ℓ, 6
since the number of edges each curve contributes is one less than its number of incident points. Letting C denote our set of curves, we also have that X ℓ m2 . cr(G) ≤ |c1 ∩ c2 | = 2 {c1 ,c2 }⊂C
Finally, note that in our drawing of the graph m = m1 . Putting all this together, we either have that e < 5m1 p, which would imply I = e + ℓ < 5m1 p + ℓ, which implies our theorem, or else ℓ m2 . (I − ℓ) /(p m1 ) = e /(p m1 ) ≪ cr(G) ≤ 2 3
2
3
2
Theorem 3 is now proved.
3.2
Restricting to a dyadic interval
Later, we will require an upper bound on the number of curves passing through pairs of grid points, and to achieve such upper bounds it will be good to first pass to elements of A that lie in a dyadic interval. To this end we will require the following lemma. Lemma 1 Suppose that A is a set of n real numbers satisfying |A + A| ≤ n1+δ /3 log n, for some δ > 0. Then, there exists a dyadic interval [x, 2x) containing at least n1−δ elements of A. A version of this lemma can be proved without too much trouble using only very elementary ideas; however, we give a proof using the RuzsaPl¨ unnecke inequality, since it makes the proof short and transparent. First, let us state the Ruzsa-Pl¨ unnecke inequality [7]. Theorem 5 Suppose that A is a subset of an additive abelian group, such that |A + A| ≤ K|A|. Then, |kA − ℓA| = |A + A + · · · + A − A − A − · · · − A| ≤ K k+ℓ |A|. 7
Proof of Lemma 1. Suppose, for proof by contraposition, that every dyadic interval contains fewer than n1−δ elements of A. Then, it requires at least nδ disjoint dyadic intervals to contain all the elements of A, and therefore choosing one element from every other dyadic interval (if these disjoint dyadic intervals are put into increasing order), we get a sequence of at least nδ /2 elements A′ := {a1 , ..., ah } ⊆ A, h ≥ nδ /2, such that ai+1 /ai ≥ 2. It is a simple matter to show that all the k-fold sums of distinct elements of A′ are distinct (think about the usual proof that binary number representations are unique); and so, if we assume that |A + A| = K|A|, then from Theorem 5 δ n /2 δ k < |kA′ | ≤ |kA| ≤ K k n. (n /k) ≤ k It follows that K ≥ nδ−1/k /k. Choosing k ∼ log n we get that K > nδ /3 log n. But this means that |A + A| = Kn > n1+δ /3 log n, so the lemma is proved.
Now we choose the dyadic interval [x, 2x) containing the most elements of A. We may assume that this interval contains at least n1−κε elements of A, where we define the constant κ = 1/9, since otherwise Lemma 1, with δ = κε implies that |A + A| > n1+κε /3 log n, thereby proving Theorem 2.
8
Let B denote those ≥ n1−κε elements of A contained in [x, 2x). We note that if we consider the products ′ (a + δa,b )(b + δa,b ), a, b ∈ B, ′ then as we vary over all legal choices for δa,b and δa,b , since a and b lie in the same dyadic interval [x, 2x), we have that the possible values of this product must lie in an interval of width
≪ n1−ε + n2−2ε /x2 . Since the gap between elements of A is at least 1, we have x ≫ n, making our interval of width ≪ ∆ := n1−ε . So, the number of our “perturbed products” is at least a constant multiple of the set of distinct values < ab >, a, b ∈ B, where < t > denotes t rounded to the nearest multiple of ∆.
3.3
A family of polygonal curves
In order to apply Theorem 3, we need to define some points and curves that are relevant to our problem: we begin by letting X be the elements of B + B; and then we let Y be the elements of B.B rounded to the nearest multiple of ∆. Our set of points will then be X × Y ; so, there will be |X| · |Y | of them in total. Now we define the curves: we begin by considering, for each a, b ∈ B, the set of points on the line y = a(x − b), with x ∈ B + b. Then, we round the y coordinate to the nearest multiple of ∆. Sweeping from left-to-right across the grid, we connect consecutive points by line segments.
3.4
Perturbing the curves
At this point we could have that some pairs of curves intersect in a segment, and therefore have infinitely many points of intersection. But this is easily fixed by making a small perturbation to the curves, replacing the shared segments by closely drawn curves that are nearly parallel and only intersect 9
at grid points. We furthermore can assume that if a pair of points is common to two or more curves, then those points must be grid points (again, by perturbing the curves slightly, while still connecting the same grid points as before).
3.5
The average crossing number
Now we calculate the average intersection multiplicity of pairs of curves: first, we observe that the polygonal curves are at most a vertical distance ∆ from their corresponding straight lines. And therefore, two of these polygonal curves, corresponding, say, to the curves y = a(x − b) and y = c(x − d), can only cross if x is such that |c(x − d) − a(x − b)| < ∆. In other words, |(c − a)x + ab − cd| < n1−ε . We first consider the contribution to our count of the average intersection multiplicity of all those pairs of lines having the same slope: in order for the polygonal curves corresponding to lines of the same slope to intersect, they must have y-intercepts that come within ∆ of one another, and when this happens we will just assume that the lines intersect in |B| points, the maximum possible. Since there are |B|4 choices for (a, b, c, d) ∈ B 4 , the contribution to our average intersection multiplicity count of pairs of lines of the same slope is X 1 ≪ |B| ≤ 1. |B|4 a,b,b′ ∈B |b−b′ |≤∆
Note that we just used here the trivial bound – we didn’t even need to use the fact that |b − b′ | ≤ ∆. Next, we consider the contribution of pairs of lines that have different slope. We begin by observing that between any consecutive x-values of the set {b, d} + B, (6) there can be at most one crossing between the pair of polygonal curves. 10
Now, since in any three consecutive points of (6), two must either belong to b + B or to d + B, we have that every other point of (6) is at least 1 apart. It follows, therefore, that the number of crossings between the two polygonal curves is at most 1 + O(n1−ε /(c − a)). (The 1 here accounts for the “left-most point of intersection”, and once we are given this point, there can be at most O(n1−ε /(c − a)) other intersection points to the right of it.) Thus, the average intersection multiplicity, is easily seen to be bounded from above by 1+
O(n1−ε ) X 1 |B|2 a,c∈B c − a
≤
1+
≤
1+
O( n1+ε(1−κ) )
c>a
1 (j − i) 1≤i x1 + 1, are at most in number the set of lines of the form fi (x) = ai (x − bi ), where all the fi (x1 ) come within ∆ of one another, and the same should hold for fi (x2 ). But this implies that |(ai − aj )(x1 − x2 )| ≤ 2∆.
(8)
First, let us see that no two of these lines can have the same slope: if they did, say ai = aj , then just considering the contribution of the point with 11
x = x1 , we would have that ai (x1 − bi ) = aj (x1 − bj ), and therefore bi = bj . But this can only hold if the two lines are in fact the same, so we may assume the slopes are different. Assuming this, we find from (8) that |ai − aj | ≤ 2∆ = 2n1−ε . It is clear that, since the ai ∈ B are all at least 1 apart, there can be at most O(n1−ε ) choices for the slopes ai such that all pairwise differences |ai − aj | satisfy this bound. We have therefore proved that m1 ≪ n1−ε .
(9)
Here we are assuming that ε ≤ 1, because of course we know that m1 ≥ 1.
3.7
Conclusion of the proof
Putting everything together, since our |B|2 = n2−2κε lines hit the grid X × Y in |B| = n1−κε points each, we have that the number of incidences is n3−3κε . Yet, from Theorem 3, along with (7) and (9), we find that the number of incidences is ≪ (m1 m2 )1/3 (|X| · |Y | · n2−2κε )2/3 ≪ n1/3−ε/3 (|X| · |Y | · n2−2κε )2/3 . So, |X| · |Y | ≫ n2−ε(5κ/2−1/2) So, |X| + |Y | ≫ n1+ε(1/4−5κ/4) ≫ n1+ε/9 . Note that here is where we used the fact that ε is sufficiently small – it allowed us to ignore the contribution of the terms ℓ + m1 p. This completes the proof. We conclude this section by giving some remarks about how to prove (5): basically, the reason we can show this is that in the first parts of the proof of Theorem 2 above, we pass to a subset B ⊆ A, contained in a dyadic interval [x, 2x), whose set of perturbed products or sums B +B we show must contain 12
′′ at least n1+ε/9 /3 log n elements. This then means that |δa,b | < n1−ε /x; and, then we can bound |S| from below by a constant multiple of |C + C|, where C is the set of elements of B rounded to the nearest multiple of n1−ε /x. Rewriting the perturbed products for B in terms of perturbed products for C, it is easy to see that this implies (5).
References [1] J. Bourgain and M.-C. Chang, On the size of k-fold sum and product sets of integers, J. Amer. Math. Soc. 17 (2004), 473-497. [2] A. Balog, On the distribution of integers having no large prime factor, Journ´ees Arithm´etiques, Besan¸con, Ast´erisque 147/148 (1985), 27-31. [3] G. Elekes, On the number of sums and products, Acta Arith. 81 (1997), 365-367. [4] P. Erd˝os and E. Szemer´edi, On sums and products of integers, Studies in Pure Mathematics; To the memory of Paul Tur´an, P. Erd˝os, L. Alpar, and G. Halasz, editors. Akademiai Kiado-Birkhauser Verlag, Budapest-Basel-Boston, Mass. 1983, 213-218. [5] K. Ford, Sums and products from a finite set of real numbers, Ramanujan Jour. 2 (1998), 59-66. [6] M. Nathanson, On sums and products of integers, Proc. Amer. Math. Soc. 125 (1997), 9-16. [7] I. Z. Ruzsa, An application of graph theory to additive number theory, Scientia, Ser. A 3 (1989), 97-109. [8] J. Solymosi, On sum-sets and product sets of complex numbers, J. Th. Nomb. Bordeaux 17 (2005), 921-924. [9] ———–, An upper bound on the multiplicative energy, preprint on the ARXIVES. [10] A. Sz´ekely, Crossing numbers and hard Erd˝os problems in discrete geometry, Comb. Prob. and Comp. 6 (1997), 353-358.
13
[11] E. Szemer´edi and W. Trotter, Extremal problems in discrete geometry, Combinatorica 3 (1983), 381-392.
14