close

Вход

Забыли?

вход по аккаунту

Мукосат - эффективное средство для лечения;pdf

код для вставкиСкачать
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
1/--страниц
Пожаловаться на содержимое документа