Advances in Pure Mathematics, 2012, 2, 195-199 http://dx.doi.org/10.4236/apm.2012.23027 Published Online May 2012 (http://www.SciRP.org/journal/apm) Difference Sets of Null Density Subsets of ,,babB Dawoud Ahmadi Dastjerdi, Maryam Hosseini Department of Mathematics, University of Guilan, Rasht, Iran Email: ahmadi@guilan.ac.ir, maryamh2002@googlemail.com Received December 29, 2011; revised February 9, 2012; accepted February 16, 2012 ABSTRACT Let , and for any , B 1::DBBB aba 2k 11k DB kk DBDB . If 1, , lim supn Bn dB n is positive, then B is considered as a large set with 1 bB b . Its difference set has both high density and rich structure. The set with 1 DB A1 aA a is also relatively large and it is a long standing conjecture that like sets with positive upper density they have arithmetic progression of arbitrary length. Here we show their difference set may not be substantial; for any k there exists such that k A1 aA ka *1 0 k dD A * and . Keywords: Difference Set; Density; -Set 1. Introduction A subset B of has null density if 1, ,0. Bn n 0dB lim n dB Perhaps, the most prominent general result in this case is a theorem conjectured by Erdős and proved by Rusza [1]. It states that if then 1 lim1, n DB 1, , , n Bn :,,babB (1) where . 1:DBBB aba Our concern here is to consider the null density subsets in the family 1 aA a :na A A :A. These sets can be considered “large” sets among null density sets. To have a comparison with sets of higher densities, note that if and , and has Ramsey property, that is, if and A is partitioned into finitely many sets then at least one of the elements of the partition lies in . These two proper- ties, being invariant under translation and having Ramsey property, hold for AnAn a 1, ,0 An n B : lim supn Bd B 1 DB * then is a as well. However, if -set [2]. This means 1 DB is both large and structured set. For instance, it is syndetic: there exists a p such that 1 ,nnpD B * for any n in . By definition, a -set intersects the difference set of any infinite natural sequence and amongst many structures it is IP which means there is a sequence of natural numbers nn b such that all of its finite sums are in B [3]. From largeness point of view, may be considered next to for [4]. Note that there is also a family ** ,, :0 limsupmn Am n AdA mn which * dA B is called the upper Banach density of A. We have that * and * is invariant under trans- lation and satisfies Ramsey property [5]. Also, if * then 1 DB * is [5] and B has arithmetic progression of arbitrary length [6]. However, B may not be -large. * 2,21, ,2: nn n Bnn but For instance, 1 bB b . Erdös conjectured that elements of have arithme- tic progression of arbitrary length [7]. An important sub- set of natural numbers, which is the set of prime numbers lies in and the conjecture was proved positively by C opyright © 2012 SciRes. APM
D. A. DASTJERDI, M. HOSSEINI 196 Green-Tao [8]. In order to present a substantial contrast of sets in with those in , we will show that for any k A there is such that 1k D A * :ax b 0, ,,yy 2yy k DA D; the kth difference set of A even does not lie in . Throughout this note, unless otherwise stated, by an interval we mean an interval of integers. So for instance, . ,ab x 2. Reference Set Here we introduce and investigate the properties of a subset of non-negative integers suitably defined for our later use. Let 012 be a set of non-negative in- tegers with the property that n, 1nn for any . For any n let ln be the largest integer strictly Yy 1ny less than 1 2 n n y y 1,,1122 :2 22 n kk nn ckykyky 1, ,in 0 1 , nn n yy y , 11 herwise. nn kk n cyy . Set for all those , such that 0kl y ii 112 22k k22ky. Also set 11 1 ,, 1, ,, 1 ,if :,ot n kk kk n cy dy 0 ,, kkkn dyy 0 :, nnY Definition 1.1. Let Y be as above. The set of non- negative integers 12 11 12 ,,,, 1000 n nn n l ll Yk nkk k Rc is called the reference set associated to Y. The reference set can also be seen as follows. Set yR 111 1 2 222 2 3 20 ,, 20,, 20, nnn n n ky y ky y ky y : i x x \0 Y R , then 11 21 11 32 22 1 0, , 2 2 2 nn nn y ly ly ly where . 22 ii ii ky ky i Let us now examine when for a given Y be- longs to 1 aA a , ,yy y : A . Lemma 1.2. Suppose 012 with 1nn and let Y be its associated reference set. Suppose for sufficiently large n, 0,Yy yR2 2 21 1 , nn nn yy yy 0 (2) \0R . Then . for some Y Proof. First note that (2) implies 1 lim ; n nn y y (3) and also if we set 21 1 ln ln :2ln ln nn n nn yy yy lim inf1 n (4) then n Now let for , 1n . 1 : card, nnnY yy R . Then 1 1 1 1 1 1 2card 0, 2 card0, . 2 nn Ynn n nn Yn n yy Ry I y yy Ry y 0nn kl (5) , But for 12 card0,card2, 21 . Yn Ynnnn n Ry Rkyky II I So by estimating any 1 r 2,21 nn nn rkyky , with 1 21 nn ky , 1 0, 1 1 Ym m n rR yn e r (6) where 11 :11313. nnnnnn eIIyyy y 130 nn yy Note that by (3) for sufficiently large n we have . Now 111 1121 1 1 11121 1 1 11 1 33 11 1 33 11 1 33 1. 11 1 33 nnnnnn nn nnnn nnnnn n nnnn eIIyyyy eIIyyyy yy yy II yyy y Also by (5), 1 11 2 2 nn nn n yy II y . Therefore, Copyright © 2012 SciRes. APM
D. A. DASTJERDI, M. HOSSEINI 197 21 3 1d 21 1 1d 21 nn nn n yy 1 1 21 1 1 3 1 11 1 1 3 1 3 1 2 12 1d 121 . 21 1d 21 n nn n nn n yy y nnnn nnn y yy y yy y eyyy eyy x x x x x By considering (3) this implies 2 1 1 ln ln 1. n n n n y y y y 11 l iminfliminf2 lim inf n nn n n n e e 2b 2 2, . n b b im b (7) Now the proof is complete by the ratio test. Let , then an example for Y satisfying the above lemma is 2 0, 2,, b Yb For this example lim infl nn nn 0 Remark 1.3. Similar arguments as the proof of the above lemma shows that if either (3) does not hold or if (3) holds but there is some . such that for infinitely many n, 2 21 , nn nn yy yy 1 (8) then 1 Y rR r n . We give a sketch of proof for the latter. Suppose is defined as (4). Then by (8), we have lim sup1 nn . Let i be as above and set 1 11 :24 nn nn eI Iyy 1 2 nn ly . Using the left inequality in (5), we have 1 1 1. m n n 0, Ym rR y e r Now 1 2 2 1 1d . 1d n n l n l 11 1 2 nn nn eyy ey x x From (3), we have 2 1 n l x . This and the fact that 1 n n y y 0 implies 1 lim suplim sup1 nn nn n e e DAAA and we are done. 3. Main Result We will show that comparing to a set of positive upper Banach density, the difference set, of a set A with 1 aA a *0dA k and can be very sparse. The next theorem gives a class of examples with this property. Theorem 2.1. Let k A, then there exists with 1 k aAa 0 kk DA A0 and such that is not * . In particular, *1 0 kk dD A 2b00y . Proof. Let , , , 1 12k yb 1 1 1 n y n yy and ,, ,Yyyy 012 . Consider the following symmetric subsets of integers: 0 122 11 0, 1, ,1,0,1, ,1 22 j jii ijj ii F yy Fyy 0jk (9) 2i 01 01 0 : jj j nn and . Set for ja naF aFaF I 01 :,,n aa a where a01 ,,, n j aa a I and is the interval 1 00 111 1 00 111 22 2, 2 222 2 nn j nn j y ay ayay y ay ayay 1 in . Hence j A and is a union of subin- tervals of non-zero integers with the first subinterval of length 1 1 2j y and all others of length 1 2 y 0 . To have a picture of Aj’s consider which is a prototype for others. Then 0 1 n n 0 may be considered as in which 10 11 00 10 20 21 00 121 11 00 1 =1 0, 0,,, 222 ,,, 222 =,= , 22 . Y Y n nni nnYni y yy AAyR y y yy AA yyRy yy AAyy Ry Copyright © 2012 SciRes. APM
D. A. DASTJERDI, M. HOSSEINI 198 That is, 0 has as half elements as Y in R 1 0, n y which are shifted to the left appropriately. So 01 0,aA y 1 0, 11 2. nYn rR y ar By Lemma 1.2, one obtains that \0 1 Y rR r and hence 0\0 1 aA a . (Later we will prove that 1 k aAa . So divergence of 0\0 1 aA a 0 will be a consequence of that as well). Now we claim that is not . First note that * 111ni nnn :1 , yin yyy 0 . Then the claim is established by noting that by the above definition for 01 Ay1 , nnn yy which implies 0 does not intersect \0DY y : 1 ij y ij *1 and so it is not . The sets 1ik ’s and ’s are defined in such a way that 1 1 j, for . To see this, suppose x and y are two elements of DA A 1jk and y n. Then there exists such that 1 1 1 1 2 22 j nn 00 11 00 11 22 2 22 nn y y ay mn ay ay ay xay ay and also with 1 1 1 1 2 22 j mm 00 11 00 11 22 2 22 mm y y by by by by yby by where 1 , ii ab i F i ai . So and b are in 2 1, i j2 11 1 22 i j ii yy yy or equivalently, 11 11 22. 22 ii jj ii yy yy ii ab Therefore, 1 yA To complete the proof, it remains to show that for each . , \0 1 j aA a kj . We already have proved this fact for A0 and we will prove that for Ak and since A 01jkk i , we are done. So consider in (9) and let 00 11 21 1 :0 , :10,1,, 22 kk kkii ii kk ii FF yy FF yy Also set 2,1.i 00 00 0 1 00 :22, 22. 2 jk nn knn nbF bF nn k by by y by by Then 11 kk aA bA ab . Now using the same argu- ments as in Lemma 1.2, we prove that 1 k bAb is di- vergent. If we let 11 1 : card0,,, : card,,, k nnnk IyA IyyA then 11 1 11 1 1,, 2 2 12,. 2 2 k nn nn kn Iy yy III y n lY R Let be as in the definition of ; then \0 1 k n bA n e b where 1 1 1 11 1 :322 3 111 . 325 nn k nn nn nk nn nn eI I yy ly II yy yy So 21 1 1 11 1 1 121 1 5 2 2 15 2 1 21 11 11 11 lim inflim 11 25 11 25 1d 121 lim inf21 1d 21 1lim inf 2 nn kn nn kn nn nn nn k nnn k nnn yy y kyy ny nn knn n eII eII yyy yyy x x yy yy 1 11. 2k y Let k be the set defined in the proof of the above theorem and let be a syndetic set with the larg- S Copyright © 2012 SciRes. APM
D. A. DASTJERDI, M. HOSSEINI ciRes APM 199 k Copyri2 Sght © 201. est gap smaller than b. Then the conclusion of the above theorem applies for S 01 0, 1 11 k . This conclusion also holds if we let with 2 , ,yyYy eb , 1 1 n y nn yyb2 p , where e is an 1nn bb 1 b pn 11 0dB even integer and is an increasing integer valued function with . Also recall that the theorem of Rusza [1] for sets of null density states that the difference set is considerablely larger than the set itself, that is, if then (1) holds. However, in examples such as those in the above theorem, one tries to have a difference set which is as small as possible. Our approach was to have the arithme- tic progression of long possible lengths. Therefore, such examples not only do not contradict the Erdös conjecture, but strongly are in the favor of it. REFERENCES [1] I. Z. Rusza, “On Difference-Sequences,” Acta Arithme- tica, Vol. 25, 1974, pp. 151-157. [2] V. Bergelson and N. Hindman, “Additive and Multiplica- tive Ramsey Theorems in -Some Elementary Results,” Combinatorics, Probability and Computing, Vol. 2, 1993, pp. 221-241. doi:10.1017/S0963548300000638 [3] V. Bergelson, “Partition Regular Structures Contained in Large Sets Are Abundant,” Journal of Combinat orial The- ory, Series A, Vol. 93, No. 1, 2001, pp. 18-36. doi:10.1006/jcta.2000.3061 [4] T. C. Brown and A. R. Freedman, “Arithmetic Progres- sions in Lacunary Sets,” Rocky Mountain Journal of Mathe- matics, Vol. 17, No. 3, 1987, pp. 587-596. doi:10.1216/RMJ-1987-17-3-587 [5] V. Bergelson, N. Hindman and R. McCutchen, “Notions of Size and Combinatorial Properties of Quotient Sets in Semigroups,” Topology Proceedings, Vol. 23, 1998, pp. 23-60. [6] E. Szemerdi, “On Sets of Integers Containing No k Ele- ments in Arithmetic Progression,” Acta Arithmetica, Vol. 27, 1975, pp. 199-245. [7] P. Erdös, “Problems and Results in Combinatorial Num- ber Theory,” Astrisque, 1975, pp. 295-310. [8] B. Green and T. Tao, “The Primes Contain Arbitrarily Long Arithmetic Progressions,” Annals of Mathematics, Vol. 167, No. 2, 2004, pp. 481-547. doi:10.4007/annals.2008.167.481
|