MIDPOINTS OF SEGMENTS INDUCED BY A POINT SET Janos Pah Courant Institute, NYU and Hungarian Aademy of Sienes Abstrat Applying some well known results in additive number theory, we partially answer two geometri questions due to V. Balint et al. and F. Hurtado. (1) Let m(n) be the largest integer m with the property that from every set of n points in the plane one an selet m elements so that none of two p of them is the midpoint 0 1 = log n m(n) n= log n: (2) Let others. It is shown that n (n) be the smallest number of distint midpoints of all segments indued by n points in the plane, no 3 of whih are ollinear. It 00 plog n is proved that limn!1 (n)=n = 1 and that (n) ne : Here ; 0 ; and 00 denote suitable positive onstants. 1 Introdution Many extremal problems in disrete geometry lead to questions in additive number theory [12℄. This is partly due to the fat that their solutions are known or onjetured to be lattie-like, i.e., aÆnely equivalent to the integer lattie. Here we present two planar examples. Balint et al. [1℄ (see also [10℄, p. 27.) investigated the following question. A set of points in the plane is said to be midpoint-free if it has no pair of elements whose midpoint also belongs to the set. Let m(n) Supported by NSF grant CCR-00-98246, PSC-CUNY Researh Award 64421- 0033 and OTKA-T-032452. 1 denote the largest number m suh that every set of n points in the plane has a midpoint-free subset of size m. It was proved in [1℄ that p 8n + 1 e m(n); 1 + d 2 and it was onjetured that the order of p magnitude of this bound annot be improved, i.e., we have m(n) = O( n). However, it follows from the existene of relatively dense sets of integers ontaining no 3-term arithmeti progression that this onjeture is wrong. Theorem 1. There are positive onstants , 0 suh that n1 p log n = m(n) n= log 0 n: F. Hurtado raised the following problem. For any point set P , let M (P ) denote the set of midpoints of all the segments spanned by point pairs in P . Determine (n) = minj j jM (P )j; where the minimum is taken over all sets of n points in the plane, no 3 of whih are ollinear. Hurtado and Urrutia showed that (n) = O(n ) O(n ), but no superlinear lower bound was known. Using an idea of Behrend and Freiman's theory of set addition, we prove n 2 P =n log2 3 Theorem 2. There is a positive onstant (n) ne p 1:585 suh that log n : lim !1 (n)=n = 1: In the next two setions, we establish Theorems 1 and 2, resp., while in the last setion some related questions are disussed. Furthermore, we have n 2 Proof of Theorem 1 Consider a set P of n points in the plane with no midpoint-free subset of size larger than m(n). First, hoose (e.g., randomly) a straight line ` so that the orthogonal projetion : P ! ` takes P into an n-element set P 0 satisfying the following ondition: for any p ; p ; p 2 P , the midpoint of the segment p p is p if and only if (p ); (p ); and (p ) (in this i i k j i 2 j k j k order) form an arithmeti progression of length 3. Using simultaneous approximation [8℄, for any positive integer q, we an replae eah point (p ) by a rational number r =q , suh that r = r (q ) is an integer and j(p ) r j 1 i i i i q i i q 1+1 =n holds for all 1 i n: There exists a suÆiently large q satisfying the following ondition: eah triple ((p ); (p ); (p )) forms an arithmeti progression (in this order) if and only if (r ; r ; r ) does. Indeed, we have i j k i j k j((p ) + (p ) 2(p ))q (r + r 2r ) j jq(p ) r j + jq(p ) r j + 2jq(p ) r j q 4 : i i k j i k i k k j j j 1=n Assuming that q > 4 , if (p )+ (p ) 2(p ) = 0 holds for some triple, we obtain that jr +r 2r j < 1 so that r +r 2r = 0 must also be true. In the reverse diretion, assume indiretly that (p ) + (p ) 2(p ) is not equal to zero, but r (q) + r (q) 2r (q) = 0 holds for innitely many values of q. For these values, we have j ( p ) + ( p ) 2 ( p ) j 4 ; n i i k k j j i k j i i k i k j j k q 1+1 j =n whih leads to a ontradition, as q tends to innity. Thus, we have redued the problem to the following: determine the largest positive integer m0 (n) suh that every set of n integers has a subset of size m0 (n) whih ontains no arithmeti progression of length 3. Let m (n) denote the largest number of elements that an be hosen from the rst n positive integers without ontaining a 3-term arithmeti progression. Clearly, we have m0 (n) m (n) for every n. It was proved by Komlos, Sulyok, and Szemeredi [11℄ in a more general setting that there exists a onstant > 0 suh that m0 (n) m (n). Thus, Theorem 2 immediately follows from well known estimates on m (n), due to Behrend [2℄, Heath-Brown [9℄, and Szemeredi [14℄. Note that the same argument an be applied in higher dimensions. 3 3 3 3 3 3 3 3 3 3 Proof of Theorem 2 First we establish the upper bound, by adaptingd d the arguments in [5℄. for some natural Assume, for the sake of simpliity, that n = b number d 4. Consider the set L of all lattie points (x ; : : : ; x ) 2 Rd with integer oordinates 0 x < 2 . The number of distint distanes determined by L is at most d(2 ) , beause there are at most that many numbers of the form (P (x x0 ) ) , where 0 x ; x0 < 2 . In partiular, there is a sphere around the origin whih ontains at least jLj = (2 ) b 2 =n d(2 ) d(2 ) d elements of L. Let P denote the set of these points. Let M (P ) denote the set of midpoints of all segments determined by P . Clearly, we have jM (P )j = jP + P j; where P + P = f p + p j p ; p 2 P g: Observe that every element of P + P is a vetor (x ; : : : ; x ) 2 Rd with integer oordinates 0 x < 2 , hene 2 ( 2) d 1 2 d 2 1=2 d i=1 i 2 i i d d d d i d(d d d d i 2) 2 1 1 d+1 i 2 jM (P )j = jP + P j (2 ) < n2 d+1 p 8 d log n 1 2 d : Fix a 2-dimensional plane in Rd, and for any p 2 P let p0 denote the orthogonal projetion of p into . Evidently, we an hoose so as to meet the following two onditions: (i) the projetions of no two elements of P oinide, (ii) no 3 elements of P 0 are ollinear. In view of the fat that p + p = p + p implies jp0 + p0 j = jp0 + p0 j, we have that the number of distint midpoints of all segments determined by P 0 satises p jM (P 0 )j = jP 0 + P 0 j jP + P j < n2 ; as required. This argument easily extends to the general ase when n an take any positive integer value. We prove the seond part of Theorem 2 by ontradition. Assume that for innitely many values of n there are n-element point sets P with no 3 ollinear points in the plane suh that the the number of midpoints of all segments spanned by P satises jM (P )j = jP + P j < Cn; for an absolute onstant C . We need the following well known result of Freiman [6℄: For any integer C , there exists C 0 with the property that any n-element set P 1 2 3 4 1 2 3 8 4 log n n n n n n n 4 in the plane with jP + P j < Cn an be overed by the projetion of a lattie of dimension C and size C 0 n. That is, n n fv + m v + + m v j 1 m n g ; for suitable vetors v 2 R2 and natural numbers n satisfying Q n P 0 n 1 1 C C i i C i C 0 n. i=1 i i (See Ruzsa [13℄ for a simple proof.) Without loss of generality assume that n n . Obviously, we an x some values m ; : : : ; m so that 1=C 1 2 C v0 + m1 v1 + m 2 v2 + + m v C for at least C 2P n n n 0 n n n C C0 n 2 3 1 1=C C dierent integers m . However, the orresponding points of P are all on a line, ontraditing our assumption. 1 n 4 Related problems It was notied by Cokayne and Hedetniemi [3℄ that the problem of plaing queens on the diagonal of an n n hessboard so as to over all squares is equivalent to the problem of nding a midpoint-free set of integers up to n=2, i.e., one ontaining no 3-term arithmeti progression. 4.2. Erd} os raised the following problem related to Theorem 1. Determine the largest integer (n) suh that every set of n points in the plane, no four on a line, has an (n)-element subset with no ollinear triples. The best known bounds, due to Furedi [7℄, leave plenty of room for improvement: q ( n log n) (n) o(n): 4.3. Erd} os, Fishburn, and Furedi [4℄ studied the following question, strongly related to Theorem 2. Given a set P of n points in onvex position in the plane, let M (P ) denote the set of midpoints of its sides and diagonals. How small an the ardinality (n) of M be for xed n? One might guess that the answer is (0:5 o(1))n . However, it 4.1. n 2 2 5 was shown in [4℄ that this minimum is somewhere between 0:40 n and 0:45 n . In fat, we have ! ! n 2n + 12 n n(n + 1)(1 e ) n b (n) ; b 2 4 20 2 for all n 3. The upper bound follows from the fat that the number of multiple midpoints an be as large as b(n 2n + 12)=20: Woodall [15℄ solved a similar problem of R. Hall, onerning the minimum number of midpoints indued by an n-element subset of the vertex set of a d-dimensional ube (n 2 ). 2 2 2 1=2 2 d Referenes [1℄ V. Balint, M. Branika, P. Gresak, I. Hrinko, P. Novotny, and M. Staho, Several remarks about midpoint-free subsets, Studies of University Transport and Communiation in Zilina, Math.-Phys. Series 10, 3-10. [2℄ F. A. Behrend: On sets of integers whih ontain no three terms in arithmetial progression, Pro. National Aademy of Sienes, USA 28 (1942), 561{563. [3℄ E. J. Cokayne and S. T. Hedetniemi, On the diagonal queens domination problem. J. Combin. Theory, Ser. A 42 (1986), 137{ 139. [4℄ P. Erd}os, P. Fishburn, and Z. Furedi, Midpoints of diagonals of onvex n-gons, SIAM J. Disrete Math. 4 (1991), 329{341. [5℄ P. Erd}os, Z. Furedi, J. Pah, I. Z. Ruzsa, The grid revisited, Disrete Math. 111 (1993), 189{196 [6℄ G. Freiman, Foundations of a Strutural Theory of Set Addition , Translations of Mathematial Monographs 37, Amerian Mathematial Soiety, Providene, 1973. [7℄ Z. Furedi, Maximal independent subsets in Steiner systems and in planar sets, SIAM J. Disrete Mathematis 4 (1991), 196{199. 6 [8℄ G. H. Hardy and E. M. Wright, An Introdution to the Theory of Numbers, 4th ed., Clarendon Press, Oxford, 1960. [9℄ D. R. Heath-Brown, Integer sets ontaining no arithmeti progressions, J. London Math. So. (2) 35 (1987), 385{394. [10℄ V. Klee and S. Wagon, Old and New Unsolved Problems in Plane Geometry and Number Theory, Doliani Mathematial Expositions 11, Mathematial Assoiation of Ameria, 1991. [11℄ J. Komlos, M. Sulyok, and E. Szemeredi, Linear problems in ombinatorial number theory, Ata Mathematia Aademiae Sientiarum Hungariae 26 (1975), 113{121. [12℄ J. Pah and P. K. Agarwal, Combinatorial Geometry, WileyIntersiene, New York, 1995. [13℄ I. Z. Ruzsa, Arithmetial progressions and the number of sums, Periodia Mathematia Hungaria 25 (1992), 105{111. [14℄ E. Szemeredi, Integer sets ontaining no arithmeti progression, Ata Math. Hungar. 56 (1990), 155{158. [15℄ D. R. Woodall, A theorem on ubes, Mathematika 24 (1977), 60{ 62. 7