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
y
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
.
I
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
I
yy yy
II yyy y

 

 

 


 




Also by (5),

1
11
2
2
nn
nn
n
yy
II
y




I
.
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
x
eyyy
eyy x
x
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
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
I
e
r



Now
1
2
2
1
1d
.
1d
n
n
l
n
l
11
1
2
nn
nn
x
eyy
ey x
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
A
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
j
A
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
A
in . Hence
j
j
A
and
j
A
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
j
. To have a
picture of Aj’s consider
A
which is a prototype for
others. Then 0
1
n
n
0
A
may be considered as
A
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
A
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
A
is not . First note that
*

111ni nnn
:1 ,
y
yin
yyy
0

. Then the claim is
established by noting that by the above definition for
A
01
Ay1
,
nnn
yy


which implies 0
A
does not intersect


\0DY y

: 1
ij
y ij *1 and so it is not
.
The sets 1ik
F
’s and
j
A
’s are defined in such a way
that 1

1
j
j, for . To see this, suppose
x and y are two elements of
DA A
1jk
j
A
and
x
y
n. Then there
exists such that
1
1
1
1
2
22
j
nn
00 11
00 11
22 2
22
nn
j
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
j
y
y
by
 
by by by
yby by

  
where 1
,
j
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
j
x
yA
To complete the proof, it remains to show that for each
.
j
A
,

\0
1
j
aA a

kj
. We already have proved this fact
for A0 and we will prove that for Ak and since
A
A
01jkk
i
,
we are done. So consider
F
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
A
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
x
x
yy
yy


 




















1
11.
2k
y
Let k
A
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
A
S
01
0, 1
11
k
. This conclusion also holds
if we let with

2
, ,yyYy
y
eb
,

1
1
p
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