advertisement

DISTANCE SETS OF WELL-DISTRIBUTED PLANAR POINT SETS A. Iosevich and I. Laba December 12, 2002 (revised version) Abstract. We prove that a well-distributed subset of R2 can have a distance set ∆ with #(∆ ∩ [0, N]) ≤ CN 3/2− only if the distance is induced by a polygon K. Furthermore, if the above estimate holds with = 1/2, then K can have only finitely many sides. Introduction Distance sets play an important role in combinatorics and its applications to analysis and other areas. See, for example, [PA95] and the references contained therein. Perhaps the most celebrated classical example is the Erdős Distance Problem, which asks for the smallest q 2 2 possible cardinality of ∆B2 (A) = (a1 − a01 ) + (a2 − a02 ) : a, a0 ∈ A if A ⊂ R2 has cardinality N < ∞ and B2 is the Euclidean unit disc. Erdős conjectured that #∆B2 (A) = p Ω(N/ log(N )). The best known result to date in two dimensions is due to Tardos, who proves in [Tardos02] that #∆B2 (A) = Ω(N .864 ), improving an earlier breakthrough by Solymosi and Tóth ([ST01]). For a survey of higher dimensional results see [PA95] and the references contained therein. For applications of distance sets in analysis see e.g. [IKP99], where distance sets are used to study the question of existence of orthogonal exponential bases. The situation changes drastically if the Euclidean disc B2 is replaced by a convex planar 2 set with a “flat” boundary. For example, let Q2 = [−1, 1] and define ∆Q2 (A) = {|a1 − 1 a01 | + |a2 − a02 | : a, a0 ∈ A}. Let A = {m ∈ Z2 : 0 ≤ mi ≤ N 2 }. Then #A ≈ N , and it 1 is easy to see that #∆K (A) ≈ N 2 , which is much less than what is known to be true for the Euclidean distance. In fact, it follows from an argument due to Erdős ([Erd46]; see also 1 [I01]) that the estimate #∆K (A) = Ω(N 2 ) holds for any K. Research of A. Iosevich supported in part by the NSF Grant DMS00-87339 Research of I. Laba supported in part by the NSERC Grant 22R80520 Typeset by AMS-TEX 1 The example in the previous paragraph shows that the properties of the distance set very much depend on the underlying distance. One way of bringing this idea into sharper focus is the following. Let S be a separated subset of R2 , α-dimensional in the sense that (0.1) 2 #(S ∩ [−N, N ] ) ≈ N α . √ 2 If Erdős’ conjecture holds, then #∆B2 (S ∩ [−N, N ] ) = Ω(N α / log N ); in particular, if α > 1 then ∆B2 (S) cannot be separated. This formulation expresses the Erdős Distance Conjecture in the language of the Falconer Distance Conjecture (see e.g. [Wolff02]) which says that if a compact set E ⊂ R2 has Hausdorff dimension α > 1, then ∆B2 (E) has positive Lebesgue measure. On the other hand, we have seen above that ∆Q2 (S) can be separated for a 2-dimensional set S (e.g. S = Z2 ). The purpose of this paper is to show that the example of ∆Q2 (Z2 ) is extremal in the sense that the distance set of a sufficiently “thick” discrete set can be separated only if the distance is measured with respect to a polygon. We shall also give quantitative results that hold under weaker assumptions. Our notion of thickness is well-distributivity. More precisely: Well-distributed sets. We say that S ⊂ R2 is well-distributed if there exists a C > 0 such that every cube of side-length C contains at least one element of S. K-well-distributed sets. We say that S ⊂ R2 is K-well-distributed if there is a constant CK such that every translate of CK K contains at least one element of S. Note that well-distributivity and K-well-distributivity are equivalent modulo the choice of constants. We now formally define the distance set with respect to a bounded convex set K: K-distance. Let K be a bounded convex set, symmetric with respect to the origin. Given x, y ∈ R2 , define the K-distance, ||x − y||K = inf{t : x − y ∈ tK}. K-distance sets. Let A ⊂ R2 . Define ∆K (A) = {||x − y||K : x, y ∈ A}, the K-distance set of A. Our main result is the following. Theorem 0.1. Let S be well-distributed subset of R2 , and let ∆K,N (S) = ∆K (S) ∩ [0, N ]. (i) Assume that limN→∞ #∆K,N (S) · N −3/2 = 0. Then K is a polygon (possibly with infinitely many sides). (ii) If moreover #∆K,N (S) = O(N 1+α ) for some 0 < α < 1/2, then the number of sides of K whose length is greater than δ is bounded 1 by Cδ −2α . (iii) If #∆K,N (S) = O(N ) (in particular, this holds if ∆K (S) is separated), then K is a polygon with finitely if ∂K contains a line segment parallel to a S many sides. Furthermore, 2 line L, then S ⊂ t∈T t + L for some T ⊂ R satisfying #(T ∩ [−N, N ]2 ) = O(N ). 1 The trivial estimate would be Cδ −1 . 2 The assumptions of Theorem 0.1 can be weakened slightly in a technical way, see Lemmas 1.1–1.2 below; this, however, does not improve the values of the exponents in the theorem. We do not know if the conclusion of our main result still holds if the well-distributivity assumption is weakened. However, it is clear that some sort of a “thickness” assumption is needed. For example, if S = {(m, 0) : m ∈ Z}, then the distance set with respect to any convex set is separated. Consider also the set S = {1, 2, . . . , N } × {100N, 200N, . . . , 100N 2 }, and let K be any convex set whose boundary contains the line segments [−1/2, 1/2] × {±1} and {±1} × [−1/2, 1/2]. Then #S = N 2 , but the corresponding distance set ∆K (S) = {0, 1, 2, . . . , N − 1} ∪ {100N, 200N, . . . , 100N (N − 1)} has cardinality 2N − 1. Essentially, we need some conditions on S to guarantee that the set of slopes of the lines joining pairs of points in S is dense: if there are no such pairs with slopes in some angular sector (θ1 , θ2 ), then the corresponding sector of K could be modified arbitrarily without affecting ∆K (S). It is interesting to contrast our point of view with a classical result, due to Erdős ([Erd45]), which says that if S is an infinite subset of the plane such that ∆B2 (S) ⊂ Z+ , then S is a subset of a line. An asymptotic version of this result and an extension to more general distance sets can be found in [IosRud02]. In short, these results say that if the distance set with respect to a “well-curved” metric is separated and very regular, then the set cannot be very thick. On the other hand, Theorem 0.1 below says that if the distance set of a “thick” set is separated, then the metric cannot be “well-curved” and must, in fact, be given by a polygon. Another interesting question is to characterize the polygons K and point sets S for which the assumption #∆K,N (S) = O(N ) of Theorem 0.1 (iii) holds. For example, if S ⊂ Z2 , then K can be any symmetric polygon with finitely many sides whose vertices have rational coordinates. Must S always have a lattice-like structure? For what convex polygons K can we find a well-distributed set S for which the above estimate holds? Suppose that such K and S are given; applying a linear transformation if necessary, we may assume that K contains line segments I1 , I2 parallel to the x1 , x2 -axes respectively (where (x1 , x2 ) are Cartesian coordinates in R2 ). The last conclusion of the theorem implies that S ⊂ A1 × A2 , where Ai ⊂ R, Ai ∩ [−N, N ] = O(N ). Our assumption on the density of ∆K (S) implies, roughly speaking, that a large part of each set {a − a0 : a, a0 ∈ Ai ∩ [−N, N ]}, i = 1, 2, is contained in a set of cardinality O(N ). If ∂K also contains another line segment, say parallel to the line αx1 + βx2 = 0, we obtain similar density estimates for the set {αa + βb : (a, b) ∈ S}. Thus there appears to be a link between polygonal distance sets and certain deep questions in additive number theory (such as Freiman’s theorem and the Balog-Szemerédi theorem). We hope to pursue this connection further in a future paper. Acknowledgement. We thank Jozsef Solymosi for helpful discussions and in particular for prompting us to consider the cases (i)-(ii) of Theorem 0.1, and the anonymous referee for many valuable comments. 3 Proof of Theorem 0.1 Let S ⊂ R2 be a well-distributed set. Rescaling if necessary, we may assume that S is K-well-distributed with CK < 1/2. We denote by Cθ1 ,θ2 the cone {(r, θ) : θ1 < θ < θ2 }, where (r, θ) are the polar coordinates in R2 . We also write Γ = ∂K. A line segment will always be assumed to have non-zero length. Theorem 0.1 is an immediate consequence of Lemmas 1.1–1.3: it suffices to observe that the assumptions of Theorem 0.1 (i), (ii), (iii) imply those of Lemma 1.1, Lemma 1.2(ii) and (i), respectively. Let λ(N ) = #(∆K (S) ∩ (N − 2, N + 2)), and let L(N ) = min{λ(n) : N ≤ n ≤ kN } for some k > 1 which will be fixed throughout the rest of the paper. Lemma 1.1. Let S be a K-well-distributed set in the plane with CK < 1/2. Assume that limN→∞ L(N )N −1/2 = 0. Then for any θ1 < θ2 the curve Γ∩Cθ1 ,θ2 contains a line segment. Lemma 1.2. Let S be a K-well-distributed set in the plane with CK < 1/2. (i) If L(N ) = O(1), then Γ may contain only a finite number of line segments such that no two of them are collinear. (ii) If L(N ) = O(N α ) for some 0 < α < 1/2, then the number of sides of K whose length is greater than δ is bounded by Cδ −2α . Lemma 1.3. Suppose that K and S satisfy the assumptions of Theorem 0.1(iii). Fix a Cartesian coordinate system (x1 , x2 ) in R2 so that Γ contains a line segment parallel to the x1 axis. Then #{b : S ∩ [−N, N ]2 ∩ (R × {b}) 6= ∅} = O(N ). We now prove Lemmas 1.1–1.3. The main geometrical observation is contained in the next lemma. Lemma 1.4. Let Γ = ∂B, where B ⊂ R2 is convex. Let α > 0, x ∈ R2 , x 6= 0. (i) If Γ ∩ (αΓ + x) contains three distinct points, at least one of these points must lie on a line segment contained in Γ. (ii) Γ ∩ (αΓ + x) cannot contain more than 2 line segments such that no two of them are collinear. We will first prove Lemmas 1.1 and 1.2, assuming Lemma 1.4; the proof uses a variation on an argument of Moser [Mo]. The proof of Lemma 1.4 will be given later in this section. Let (1.1) AN = {x ∈ R2 : kxkK ∈ (N − 1, N + 1)}. We will often use the following simple observation. Fix θ1 , θ2 with 0 < θ2 − θ1 ≤ π/2. Then for all N large enough (depending on θ1 , θ2 ) we have #(S ∩ AN ∩ Cθ1 ,θ2 ) = Ω(N (θ2 − θ1 )). 4 To see this, we first observe that there is a constant c0 > 0 such that c0 kx − ykB2 ≤ kx − ykK for all x, y ∈ R2 , where B2 is the Euclidean unit disc. Let θ10 = (2θ1 + θ2 )/3, θ20 = (θ1 + 2θ2 )/3, C = Cθ10 ,θ20 . The Euclidean distance between the endpoints of the curve N Γ ∩ C is Ω(N (θ2 − θ1 )). Hence we may pick Ω(N (θ2 − θ1 )) points P1 , . . . , Pm ∈ N Γ ∩ C 1 with kPi − Pj kB2 ≥ 2c−1 0 for all i 6= j. The sets Ki = Pi + 2 K, i = 1, . . . , m, are mutually disjoint, since kPi − Pj kK ≥ 2 for i 6= j. By the triangle inequality, they are all contained in AN . To see that they are also contained in Cθ1 ,θ2 , we fix j ∈ {1, . . . , m} and observe that the Euclidean distance from Pj to the lines θ = θ1 , θ = θ2 is at least cN (θ2 − θ1 ), where c depends only on K. Thus the K-distance from Pj to the complement of Cθ1 ,θ2 is at least cc0 N (θ2 − θ1 ), which is greater than 1/2 as required if N is sufficiently large. Fix 2 points P, Q ∈ S; translating S if necessary, we may assume that P = −Q and that kP kK < 1. Let Observe that all of the distances (1.2) ks − P kK , ks − QkK : s ∈ S ∩ AN lie in (N − 2, N + 2), hence the number of distinct distances in (1.2) is bounded by λ(N ). Proof of Lemma 1.1. We may assume that 0 < θ2 − θ1 < π/2. Fix θ10 , θ20 so that θ1 < θ10 < θ20 < θ2 , and let C = Cθ1 ,θ2 , C 0 = Cθ10 ,θ20 . Then for all N large enough we have (1.3) C 0 ∩ AN ⊂ (C + P ) ∩ (C + Q) and (1.4) #(S ∩ C 0 ∩ AN ) ≥ cN (θ20 − θ10 ). Let (1.5) {d1 , . . . , dl } = {ks − P kK : s ∈ S ∩ AN }, {d01 , . . . , d0l0 } = {ks − QkK : s ∈ S ∩ AN }. Then l, l0 ≤ λ(N ) (see (1.2)). We have (1.6) S ∩ C 0 ∩ AN ⊂ S ∩ C 0 ∩ [ Γi ∩ Γ0j , i,j where Γi = di Γ + P , Γ0j = d0j Γ + Q. By our assumption, we may choose N so that N ≥ 10λ2 (N )c−1 (θ20 − θ10 )−1 . Then there are i, j such that #(S ∩ C 0 ∩ Γi ∩ Γ0j ) ≥ 10. It follows from Lemma 1.4(i) that at least one of the points in S ∩ C 0 ∩ Γi lies on a line segment I contained in C 0 ∩ Γi . By (1.3), I is contained in di Γ ∩ C, hence Γ ∩ C contains the line segment d−1 i I. 5 Proof of Lemma 1.2. Suppose that L(N ) = O(N α ) for some 0 ≤ α < 1/2, and that Γ contains line segments I1 , . . . , IM of length at least δ > 0, all pointing in different directions. We will essentially continue to use the notation of the proof of Lemma 1.1. Choose P, Q 0 0 such that θm < θm , Γ ∩ Cm ⊂ Im , and as above, and let Cm denote cones Cm = Cθm ,θm 0 0 θm − θm ≥ cδ. Let also Cm ⊂ Cm be slightly smaller cones. Our assumption on L(N ) 0 implies that we may choose N ≈ δ −1 so that λ(N ) ≤ cN α , each sector Cm ∩ AN contains at least 10 points of S, and (1.7) 0 ⊂ (Cm + P ) ∩ (Cm + Q). AN ∩ Cm Let also di , d0j , Γi , Γ0j be as above. Then for each m (1.8) 0 ⊂ S ∩ AN ∩ Cm [ 0 Γi ∩ Γ0j ∩ Cm . i,j 0 0 If N is large enough, Γi ∩ Cm ⊂ Cm and Γ0j ∩ Cm ⊂ Cm , hence the set on the right is a union of line segments parallel to Im . It must contain at least one such segment, since the set on the left is assumed to be non-empty. Therefore the set [ (1.9) Γi ∩ Γ0j i,j contains at least M line segments pointing in different directions, one for each m. But on the other hand, by Lemma 1.4(ii) any Γi ∩ Γ0j can contain at most two line segments that do not lie on one line. It follows that the set in (1.9) contains at most 2λ2 (N ) ≤ c2 N 2α line segments in different directions, hence M ≤ 2c2 N 2α . Since Γ can contain at most two parallel line segments that do not lie on one line, the number of line segments along Γ is bounded by 4c2 N 2α as claimed. Proof of Lemma 1.4. We first prove part (i) of the lemma. Suppose that P1 , P2 , P3 are three distinct points in Γ ∩ (αΓ + x). We may assume that they are not collinear, since otherwise the conclusion of the lemma is obvious. We have P1 , P2 , P3 ∈ Γ and P10 , P20 , P30 ∈ Γ, where Pj0 = α−1 (Pj − x). Let T and T 0 denote the triangles P1 P2 P3 and P10 P20 P30 , and let K 0 be the convex hull of T ∪ T 0 . Since K 0 ⊂ K and the points P1 , P2 , P3 , P10 , P20 , P30 lie on Γ = ∂K, they must also lie on ∂K 0 . Observe that ∂K 0 consists of some number of the edges of the triangles T, T 0 and at most 2 additional line segments. Furthermore, the set of vertices of K 0 is a subset of {P1 , P2 , P3 , P10 , P20 , P30 }. If for each i 6= j ∂K 0 contains at most one of the line segments Pi Pj and Pi0 Pj0 , K 0 is a polygon with at most 5 edges, hence at most 5 vertices. Thus if all 6 points Pj , Pj0 , j = 1, 2, 3, lie on ∂K 0 , at least three of them must be collinear, and one of them must be Pj for some j (otherwise P10 , P20 , P30 would be collinear). If these three points are distinct, then Γ contains the line segment joining all of them, and we are done. Suppose therefore that they are not distinct. It suffices to consider the cases when P1 = P10 6 or P1 = P20 . If P1 = P10 , then we must have α 6= 1 and P1 , P2 , P20 are distinct and collinear; if P1 = P20 , then P10 , P1 , P2 are distinct and collinear. Thus at least three of the points Pj , Pj0 are distinct and collinear, and we argue as above. It remains to consider the case when ∂K 0 contains both Pi Pj and Pi0 Pj0 for some i 6= j. The outward unit normal vector to Pi Pj and Pi0 Pj0 is the same, hence all four points Pi , Pj , Pi0 , Pj0 are collinear, at least three of them are distinct, and Γ contains a line segment joining all of them. Part (ii) of the lemma is an immediate consequence of the following. Let (x1 , x2 ) denote the Cartesian coordinates in the plane. Lemma 1.5. Let I be a line segment contained in Γ ∩ (αΓ + u), where u = (c, 0). Assume that the interiors of K and αK + u are not disjoint. (i) If α = 1, then I is parallel to the x1 -axis. c , 0) lies on the straight line containing I. (ii) If α 6= 1, then the point ( 1−α Proof of Lemma 1.5. Part (i) is obvious; we prove (ii). If I lies on the line x2 = ax1 + b, then so does αI + u. But on the other hand αI + u lies on the line (1.10) x1 − c x2 = α a + b = ax1 − ac + αb. α c It follows that b = αb − ca, hence − ab = 1−α . But −b/a is the x1 -intercept of the line in question. Similarly, if I lies on the line x1 = b, then αI + u lies on the lines x1 = b and x1 = αb + c, c . hence b = 1−α To finish the proof of Lemma 1.4 (ii), it suffices to observe that in both of the cases (i), (ii) of Lemma 1.5 the boundary of a convex body cannot contain three such line segments if no two of them lie on one line, and that if the interiors of K and αK + x are disjoint then Γ ∩ (αΓ + x) is either a single point or a line segment. Proof of Lemma 1.3. Suppose that Γ contains a line segment I ⊂ {x2 = b}, parallel to the x1 axis, and let P be the center of I. Let Cθ1 ,θ2 be a cone such that P ∈ Cθ1 ,θ2 and that Γ ∩ Cθ1 ,θ2 ⊂ I. Let c1 be a constant such that [−1, 1]2 ⊂ c1 K. Denote also SN = S ∩ [−N, N ]2 . Fix M N so that #(∆K (S) ∩ [M − 1 − c1 N, M + 1 + c1 N ]) = O(N ). The K-welldistributivity of S implies that the polygon K +M P contains a point Q = (q1 , q2 ) ∈ S. If M was chosen sufficiently large, we have [−N, N ]2 ⊂ Q−Cθ1 ,θ2 , hence for any s = (s1 , s2 ) ∈ SN we have kQ − skK = |(q2 − s2 )/b|. On the other hand, for any s ∈ SN we have kQ − skK − kM P kK ≤ kQ − M P kK + kskK ≤ 1 + N c1 , hence kQ − skK ∈ [M − 1 − N c1 , M + 1 + N c1 ]. It follows that there are only O(N ) possible values of s2 as claimed. 7 References [Erd45] [Erd46] P. Erdős, Integral distances, Bull. Amer. Math. Soc. 51 (1956), 996. P. Erdős, On sets of distances of n points, Amer. Math. Monthly 53 (1946), 248-250. [I01] A. Iosevich, Curvature, combinatorics and the Fourier transform, Notices of the AMS 46 no. 6 (2001), 577-583. [IKP99] A. Iosevich, N. Katz, and S. Pedersen, Fourier basis and the Erdős distance problem, Math. Research Letters 6 (1999). [IosRud02] A. Iosevich and M. Rudnev, A combinatorial approach to orthogonal exponentials, Intern. Math. Res. Not. (submitted) (2002). [Mo52] L. Moser, On the different distances determined by n points, Amer. Math. Monthly 59 (1952), 85-91. [PA95] J. Pach and and P. Agarwal, Combinatorial Geometry, Wiley-Interscience Series (1995). [ST01] J. Solymosi and Cs. D. Tóth, Distinct distances in the plane, Discrete Comput. Geom. 25 (2001), 629-634. [Tardos02] G. Tardos, On distinct sums and distinct distances, Adv. in Math. (to appear) (2002). [Wolff02] T. Wolff, Lecture notes in harmonic analysis (revised) (2002). A. Iosevich, University of Missouri email: iosevich @ wolff.math.missouri.edu I. Laba, University of British Columbia email: ilaba @math.ubc.ca 8