Department of Mathematics College of Charleston Charleston, SC 29424 jinr@cofc.edu
Characterizing the structure of
when the ratio
is bounded by
Renling Jin
November 27, 2006
-
Abstract Let
be the set all of non-negative integers, let
be a finite set, and let
be the set of all numbers of form
for each
and
in
. In [Fr1] the arithmetic structure of
was accurately characterized when (i)
, (ii)
, or (iii)
. It is also suggested in [Fr1] that for characterizing the arithmetic structure of
when
, analytic methods need to be used. However, the interesting and more general results in [Fr1] , which use analytic methods, no longer give the arithmetic structure of
as precise as the results mentioned above. In this paper we characterize, with the help of nonstandard analysis, the arithmetic structure of
along the same lines as Freiman's results mentioned above when
, where
is positive but not too large. Precisely, we prove that there is a real number
and there is a
such that if
and
for
, then
is either a subset of an arithmetic progression of length at most
or a subset of a bi-arithmetic progression
of length at most
.
1 Introduction
Inverse problems study the structural properties of the sets
when the sum of the sets
satisfies certain conditions. When
for every
, we write
for
. Note that the term
should not be confused with the term
, which will also be used later in this paper. For a number
we write
for the set
and write
for the set
. G. A. Freiman and many others have studied inverse problems for the addition of finite sets and have obtained many results showing that if
is small relative to the size of
and the size of
, then
and
must have some arithmetic structure (cf. [Na, DLY] ). In this paper we consider the addition of two copies of the same finite set
of natural numbers. Let
with
.
A set of the form
is called an arithmetic progression of length
with difference
. A set of the form
is called a bi-arithmetic progression of length
with difference
if both
and
are arithmetic progressions of difference
,
, and
,
,
are pairwise disjoint. We will write a.p. and b.p. as an abbreviation for “arithmetic progression” and “bi-arithmetic progression”, respectively.
For two integers
the term
represents exclusively the interval of integers. For a set of integers
, we write
for the set
and
for the number
. The reader needs to be able to distinguish
, which is
times the number
, from
, which is the number of elements in the set
.
Suppose
. It is well known that if
, then
must be an a.p.
Note that it is always true that
. In [Fr1] Freiman obtained the interesting generalizations of these facts by showing that (1) if
and
, then
is a subset of an a.p. of length at most
; (2) if
and
, then either
is a subset of an a.p. of length at most
or
is a b.p.
In [Fr1] the structure of
was also characterized when
and
.
The proof of the
theorem above in [Fr1] was not short while the proof of the
theorem was omitted there because, commented by Freiman, it was too tedious
. There has been no further accurate characterization, until now, of the structure of
when, for example,
. In fact, Freiman made the following conjecture a few years ago in [Fr2] .
Conjecture 1.1 (G. A. Freiman)
There exists a natural number
such that for any finite set of natural numbers
with
and
for
,
is either a subset of an a.p. of length at most
or a subset of a b.p. of length at most
.
Note that Conjecture 1.1 is clearly false if
as shown in the following easy example.
Example 1.2
Suppose
and
. Let
. Then
and
. But
is neither a subset of an a.p. of length
nor a subset of a b.p. of length
.
It is easy to prove Freiman's conjecture if one adds an extra condition that the set
is a subset of a b.p. We prove this in Theorem 1.3 as a simple consequence of Theorem A.3 .
Let
and
be two subsets of two torsion–free groups, respectively. A bijection
is called a
-isomorphism
if for all
,
if and only if
. A set
with
is called a
-progression if the map
with
is a
-isomorphism.
is called to have rank 2 if
and rank 1 if
.
Theorem 1.3
Suppose
is a subset of a b.p.
such that
and both
and
are non-empty. If
for
, then
and
can be chosen so that
.
Proof: Without loss of generality we can assume that
has the shortest length.
Clearly,
is
-isomorphic to the set
|
(I)
|
in
where
is the length of
and
is the length of
. Let
be the
-isomorphism from
to
. Then
and
. By Theorem A.3 we have that
. Hence
is a subset of a b.p. of length at most
.
(Theorem 1.3 ) It is worth to mention another interesting generalization of Freiman's
Theorem in [HP] , where the condition
is replaced by
for an integer
. The most interesting case of this generalization is when
. However, this generalization does not concern the case when
with
. Recently, we developed some ideas with the help of nonstandard analysis in the research of the inverse problem for upper asymptotic density [Ji2] and found that these ideas can be applied to the case when
with some relatively small
. The following is the main result of this paper.
Theorem 1.4
There exists a positive real number
and a natural number
such that for every finite set of natural numbers
with
, if
and
for
, then
is either a subset of an a.p. of length at most
or a subset of a b.p. of length at most
.
Theorem 1.4 gives an affirmative answer to Conjecture 1.1 when
. Note that we have a new result even when
. Note also that the upper bound
of the length of the a.p. and the upper bound
of the length of the b.p. in Theorem 1.4 are optimal as shown in the following two easy examples.
Example 1.5
For
let
. Then
and
.
The shortest a.p. containing
has length
and
is not a subset of a b.p. of length
.
Example 1.6
For
let
. Then
and
.
The shortest b.p. containing
has length
and
is not a subset of an a.p. of length
.
The proofs in this paper use methods from nonstandard analysis. The reader is assumed to have some basic knowledge of nonstandard analysis such as the existence of infinitesimals, differences among standard sets, internal sets, and external sets, the transfer principle, countable saturation, etc. For details we recommend the reader to consult [Li] , [He] , [Ji1] , or other introductory nonstandard analysis textbooks.
Notations involved in nonstandard methods need to be introduced. Some of these notations may not be common in other literature. We work within a fixed countably saturated nonstandard universe
. For each standard set
, we write
for the nonstandard version of
in
. For example,
is the set of all natural numbers in
, and if
is the set of all even numbers in
, then
is the set of all even numbers in
.
If we do not specify that
are sets of standard natural numbers, then they are always assumed to be internal subsets of
. The lower case letters are used for integers.
The integers in
are called hyperfinite integers. From now on, the letters
and
are exclusively reserved for hyperfinite integers. The Greek letters
,
,
,
, and
are reserved exclusively for standard real numbers.
For the convenience of handling nonstandard arguments, we introduce some notations of comparison (quasi-order). For real numbers
in
, by
we mean that
is an infinitesimal, i.e. the absolute value of
is less than any standard positive real numbers; by
(
) we mean
(
) and
; by
(
) we mean
(
) or
. Given a hyperfinite integer
and two real numbers
, by
we mean
; by
(
) we mean
(
) and
; by
(
) we mean
(
) or
. It is often said that a quantity
is insignificant with respect to
if
. When using
,
,
, etc. insignificant quantities can often be neglected. For example, instead of writing
, we can write its equivalent form
. For another example, when
, we often write
instead of
. We will omit the subscript
when it is clearly given. For a real number
bounded by a standard real number, let
, the standard part of
, be the unique standard real number
such that
. Note that
,
,
,
,
, and
are external relations. If
is a hyperfinite set with
and
, then
is said to be full (in
) if
is a subset of an a.p.
such that
. We say that
is full in a b.p.
if
and
where
and
for
. Note that if
be a subset of an a.p.
and
, then
is always full. We always assume that
and
are non-empty when we say that
is a subset of the b.p.
.
In order to apply nonstandard methods, we need to translate Theorem 1.4 into the following nonstandard version of it. Then we proof the nonstandard version in the rest of the paper.
Theorem 1.7
Let
be a hyperfinite integer and
be an internal set. Suppose
,
,
,
, and
for
. Then either
or
is a subset of a b.p. of length at most
.
Proof of Theorem 1.4 from Theorem 1.7 : Suppose Theorem 1.4 is not true. Then for
and
for each
, there is a finite set
satisfying the following:
,
,
,
,
for
,
, and
is not a subset of a b.p. of length at most
.
Let
be a hyperfinite integer and let
be the term in the internal sequence
. Then we have the following:
,
,
,
,
for some
with
,
, and
is not a subset of a b.p. of length at most
. If in addition we have
, then the set
contradicts Theorem 1.7 . Hence it suffices to prove
or equivalently
.
Suppose
. By Theorem A.5 the set
is a subset of a
-sequence
such that
. If
has rank 1, then
is an a.p. Since
, then
. This contradicts
. Hence we can assume that
has rank 2. Let
be a
-isomorphism and
. Then
is not a subset of a straight line. Since
is a
-isomorphic image of
, we have
. Hence by Theorem A.3 ,
is
-isomorphic to a subset of
in ( I ) such that
. This shows that
is a subset of a b.p. of length at most
, which contradicts the assumption that
is not a subset of a b.p. of length at most
.
(Theorem 1.4 ) The approach of eliminating the possibility of
in the proof above is from [Bo] . In fact the same approach can be used to prove that there exists a small positive number
such that Conjecture 1.1 is true when an extra condition
is added.
It is possible but much more tedious to prove
in the proof above directly without citing Theorem A.5 .
We prove Theorem 1.7 in the next several sections. The proof is done in two steps. In the first step we deal with the case when
contains significantly less than half of the elements in
. In the second step we deal with the case when
contains roughly half of the elements in
. The main theorem in each step is preceded by a list of lemmas, which prove the theorem under various circumstances. Before these two steps we present a list of general lemmas. For convenience we include some existing theorems in Appendix for quick references. In this paper, theorems, lemmas, cases, and claims are numbered in such a way that the reader should be able to see how they are nested.
2 General Lemmas
In this section we state some lemmas from the author's previous papers without proof and state some other new lemmas with proof. The first lemma in this section will play an important role in the proof of Theorem 1.7 . It uses a concept called cut from nonstandard analysis.
An infinite initial segment
of
is called a cut if
. Clearly
and
are cuts. A cut
is external because it has no maximum element. For example,
is external. For a hyperfinite integer
, the set
|
(II)
|
is an external cut. We often write
for
and write
for
. Note that if
and
, then
.
Let
be a cut. A b.p.
is called a
–unbounded b.p. if both
and
are upper unbounded in
. Note that a
–unbounded b.p. always has the difference greater than
.
Suppose
is a cut. Given a function
(not necessarily internal) bounded by a standard real number, the lower
–density of
is defined by
Given a set
, let
for each
. The lower
–density of
is defined by
For any
, we define the lower
–density and lower
–density of
by
and
From now on, the only cut we need is
defined by ( II ) for a given
. Hence when
is clearly given, the letter
always represents the cut
. Note that with
fixed we have that
iff
or equivalently
iff
.
The first lemma of this section bellow is [Ji2,Lemma2.12] .
Lemma 2.2
Let
be hyperfinite,
, and
be such that
. If
is neither a subset of an a.p. of difference greater than
nor a subset of a
–unbounded b.p., then there is a
such that for every
, there is a
with
such that
|
(III)
|
The following is [Ji2,Lemma2.4] .
Lemma 2.3
Let
. Suppose
. If
satisfy the following (1)
, (2) if
, then
and
for some
in
, (3) if
, then
and
for some
in
, then
.
Lemma 2.4
Let
. Suppose
,
,
, there is an
in
such that
, and for every
there is a
with
such that ( III ) is true. Then
.
Proof: Let
be such that for any
there is a
with
such that
Let
be such that
and let
be such that
,
,
, and
.
If
, then the lemma follows from Lemma 2.3 and Theorem A.1 .
So we can assume
. By Theorem A.4 we have
. Hence
| |
| |
| |
| |
| |
| |
| |
(Lemma 2.4 ) It is worth to mention here that Lemma 2.2 , Lemma 2.3 , and Lemma 2.4 , combined together, will frequently be used to show
in various situations. For example, if
and
does not have “nice arithmetic structures”, then one can find an arbitrarily small
in
such that
. By Lemma 2.3 or Lemma 2.4 one needs only to make sure that
is not a subset of an a.p. of difference
for some
in order to conclude that
.
The next lemma is trivial and will be frequently referred as the pigeonhole principle.
Lemma 2.5
Let
. Suppose
,
,
,
,
, and
. If
, then
.
For convenience we give a name for each of the following two sets with special structural properties. Let
in
. A set
is called a forward triangle from
to
if
and for every
with
,
. A set
is called a backward triangle from
to
if the set
is a forward triangle from
to
. By the symmetry of the forward triangle and the backward triangle, we often prove a result about forward (backward) triangle and assume the symmetric result about backward (forward) triangle without proof.
Note that if
is a forward triangle from
to
, then there is a
such that
and
. The number
can be obtained by letting
be the greatest number in
such that
.
Lemma 2.6
Let
be such that
and
. Let
and
.
(1) If
and
, then there exists a
such that
and either
or for any
in
,
.
(2) If
, then there are
such that
and
is a forward triangle.
(3) If
, then there is a
such that
is a forward triangle.
(4) If
and
, then there are
such that
and
is a backward triangle.
Proof: (1) Let
where
is the standard part map. By the completeness of the standard real line,
is well defined. Let
be such that
. Clearly
.
It is easy to see that if
, then
for any
by the supremality of
. It is also easy to see that both
and
are impossible by the fact that
is the least upper bound.
(2) By the same idea as in (1) we can find
such that
and
for any
. Let
be such that
and
for any
. It is easy to see that
is a forward triangle.
(3) By the definition of
and (1) above there exists
such that
and
for every
. Clearly
is a forward triangle.
(4) Choose a
such that
. Hence
. Now the conclusion follows from (2) above with the order of
reversed.
(Lemma 2.6 ) The following lemma in nonstandard analysis, which is already used in (3) of Remark 2.1 , will be frequently– sometimes implicitly–used.
Lemma 2.7
Let
be a proper external initial segment of non-negative integers and let
be an internal set. (a) If
is upper unbounded in
, then
. (b) If
is lower unbounded in
, then
.
Proof: If (a) of the lemma is not true, then
which means that
is internal. The proof of (b) is similar.
(Lemma 2.7 )
Lemma 2.8
Suppose
in
.
(1) If
is a forward triangle from
to
, then
for some
and
.
(2) If
is a backward triangle from
to
, then
for some
and
.
Proof: Given each
with
, since
, then by the pigeonhole principle,
. This implies
. Since
is an internal set, then by Lemma 2.7 there are
and
such that
. The proof of the second part follows from the symmetry.
(Lemma 2.8 ) The following is [Ji2,Lemma2.5]
Lemma 2.9
Let
for a hyperfinite integer
. If
is a forward triangle from
to
and
for some
, then there is a
such that
.
The following is a technical lemma, which will be used in the next two sections.
Lemma 2.10
Suppose
,
,
,
is a subset of a b.p.
of difference
,
is not a subset of a b.p. of difference
,
, and
. Then
is full in
and
.
Proof: Let
,
,
, and
for
.
Since
| |
| |
then
implies that
for
. Hence by Theorem A.1 we have that
is full in
and
is full in
.
Without loss of generality we assume
. If
, then
If
and
, then
because
. Hence we have
for
.
(Lemma 2.10 )
3 First Step: When
is significantly less than
.
In this section we always assume that
is a hyperfinite integer,
,
, and
. We will prove Theorem 1.7 under one extra condition
We will prove that if
and ( IV ) is true, then
must be a subset of a b.p., which, by Theorem 1.3 , implies Theorem 1.7 . In this section the condition
is not explicitly used. Hence the letter
is not reserved. In order to make the lemmas in this section available for the other sections, we will not automatically assume ( IV ). The condition ( IV ) will be explicitly stated when it is needed.
We will first prove various versions of the main theorem of the section as lemmas when some additional structural properties of
are assumed. After all needed versions are proven we combine them into the main theorem.
Lemma 3.1
If there are
in
such that
where
is a forward triangle from
to
and
is a subset of an a.p. of difference
with
, then either
is a subset of a b.p. of difference
or
.
Proof: Let
be a subset of an a.p.
of difference
such that
is the least element of
, and
is the largest element of
. Suppose
is not a subset of a b.p. of difference
. Since
is a forward triangle, there exist
such that for every
with
,
Without loss of generality (except in Case 3.1 .1.2) we can assume
. Under this assumption we have
and
.
Claim 3.1 .1 If
is not full in
, then
.
Proof of Claim 3.1 .1: Since
is not full, then
. Let
be the collection of all intervals
such that
,
, and
.
Then
Hence
| |
| |
If there is an interval
such that
, then
| |
| |
| |
| |
So we can assume
for every
. Since for each interval
, we have
| |
| |
| |
Hence
because the left-side is an integer. So
| |
| |
| |
(Claim 3.1 .1) By the claim above we can assume that
is full in
because otherwise
Next we divide the proof of the lemma into three cases with
,
, and
.
Case 3.1 .1
.
Let
in
be such that
. Then
| |
| |
| |
| |
because
.
(Case 3.1 .1) Case 3.1 .2
. Let
be the original set with
. If
is a subset of a b.p. of difference
, then the lemma is trivially true. Suppose
is not a subset of a b.p.
of difference
. Let
. Note that either
or
.
Suppose
. Let
be such that
and
. Note that
and
. Hence
. So we have
| |
| |
Suppose
. Then
(Case 3.1 .2) Case 3.1 .3
.
Since
, then
This ends the proof of Lemma 3.1 .
(Lemma 3.1 )
Lemma 3.2
Suppose there are
such that
, where
is a forward triangle from
to
and
is a backward triangle from
to
. If
, then
and
. Hence
is full in
and
is full in
. So
is a full subset of the b.p.
of difference
.
Proof: Suppose
. Let
. Then by Lemma 2.8
| |
| |
| |
| |
| |
Hence we can assume that
. But this implies
| |
| |
Hence
implies
. By Theorem 2.9 ,
. By a symmetric argument, we can also show that
.
(Lemma 3.2 )
Lemma 3.3
Suppose there are
such that
, where
is a forward triangle from
to
and
with
,
, and
.
Then
.
Proof: First we assume that there is an
such that
. Then
| |
| |
| |
| |
| |
If the assumption above is not true, let
and
. Then
,
, and
. Hence
| |
| |
This ends the proof.
(Lemma 3.3 )
Lemma 3.4
Suppose there are
such that
, where
is a forward triangle from
to
,
is a backward triangle from
to
, and
with
. Then
.
Proof: Without loss of generality we can assume
. By Lemma 2.3 we have that
implies
. So we can now assume
. Let
and
. By Lemma 3.2 , we have
,
,
is full in
, and
is full in
.
Case 3.4 .1 There is a
with
such that
.
We have
| |
| |
| |
| |
(Case 3.4 .1) Case 3.4 .2 For every
, if
, then
.
The assumption implies that for every
, there is a
with
. Let
be such that
. Then
| |
| |
| |
This ends the proof.
(Lemma 3.4 )
Lemma 3.5
Suppose there is an
with
such that
is a forward triangle from
to
and
. If
, then
is a full subset of a b.p. of difference
or a full subset of a b.p. of difference
.
Proof: Note that if
is a subset of a b.p. then
must be a full subset of that b.p. when
. Let
. If
, then
Hence
. By Lemma 2.9 ,
. This shows
and
. Hence
is the desired b.p. of difference
. So we can assume
.
If
, then
Hence we can assume
.
Suppose
is not a full subset of a b.p. of difference
. By Lemma 3.1 we can assume
. If
, then the lemma follows from Lemma 3.3 . So now we can assume that
.
By (2) of Lemma 2.6 there are
such that
is a backward triangle and
. If
, then by Lemma 3.4 we have
.
Hence we can assume
. But now
becomes the union of a forward triangle
and a backward triangle
. Now the lemma follows from Lemma 3.2 .
(Lemma 3.5 )
Lemma 3.6
Suppose there are
such that
,
,
is a forward triangle from
to
, and
is not a subset of a b.p. of difference
. Then
.
Proof: By Lemma 2.3 we can assume
. By Lemma 3.5 we can assume that
is full in a b.p.
for some
in
. If
, then the lemma follows from Lemma 3.4 . So we can assume
. Note that
.
Hence we have
. If there is a
in
with
such that
, then
| |
| |
| |
Otherwise choose
in
such that
. Without loss of generality let
. Then
So we have
| |
| |
| |
(Lemma 3.6 )
Lemma 3.7
Suppose there are
such that
,
,
is a forward triangle from
to
, and
is not a subset of an a.p. of difference
.
Then
.
proof: By Lemma 3.6 it suffices to show that
is not a subset of a b.p. of difference
. If
is a subset of a b.p. of difference
, then
implies that
is a full subset of the b.p. This implies that
is a subset of the union of an a.p. of difference
of length
and an a.p. of difference
of length
-both have the left-end points
, and
is a full subset of an a.p. of difference
, which contradicts the assumption of the lemma.
(Lemma 3.7 ) Starting from the next lemma to the end of this section, the condition ( IV ) is assumed.
Lemma 3.8
Assume that
and
is neither a subset of an a.p. of difference
nor a subset of a b.p. Suppose that there is a
such that
and
is a subset of an a.p. of difference
. Then
.
Proof: Let
and
. Let
. Note that
is a standard natural number because
.
First, we can assume that
by the following reason: Suppose
. If there is a
such that
and
, then
If for any
,
or
, then
is a subset of a b.p. unless
.
Assume
. Hence
is a set of even numbers and
is odd. If
is a set of odd numbers, then
is a subset of a b.p. So we can assume that there is an even number
with
. Clearly
. Let
be the set of all even number in
. Then
Hence if
, then
. By Theorem A.1 and the fact that
the set
is full in the set of all even numbers in
, which contradicts ( IV ).
Second, we can assume that
by the following reason: Suppose
.
If
, then
So we can assume
. By Theorem A.1
is full. This implies
. Hence we have
| |
| |
| |
| |
Now we are ready to prove the lemma. The proof is divided into five cases.
Case 3.8 .1
and
.
Clearly
is odd. Since
is not a subset of a b.p., then
is not an even number.
Suppose
. Let
. Then
and
for some
and
. By a symmetric argument of showing
above, we can assume
. With a little more effort we can show that
The second equality above is due to the fact that if
and
having
, then
, which implies
.
This implies
, which contradicts the choice of
. The reason for the third equality above is similar. Hence
| |
| |
| |
If
, then
and
. Hence
is full in the set of all even numbers in
and
is full in
.
Without loss of generality, we can assume
and
. Note that
,
, and
are pairwise disjoint because
is odd and
. Hence we have
| |
| |
| |
So
must be true. This ends the proof of the case for
.
Now assume that
. This implies
.
Hence
We now derive a contradiction by assuming
. By the inequality above we have that
is full in the set of all even numbers in
. Suppose
. If there is a
in
such that
. Then we have
| |
| |
| |
which contradicts
. Otherwise we can find a
in
such that
.
Let
be finite such that
and
. Then
Hence we have
So we can assume
. Recall that we have
,
,
,
is full,
, and
. Note that since
, then
implies
. Since
is full, we can, without loss of generality, assume that
.
Subcase 3.8 .1.1
.
Choose a
with
such that
. Let
be finite such that
and
. Then
| |
| |
| |
| |
which is again a contradiction.
(Subcase 3.8 .1.1) Subcase 3.8 .1.2
.
By (3) of Lemma 2.6 there exists a
such that
is a forward triangle from
to
. Since
, then
and
. If
, then
. Note that
is not a subset of a b.p.
of difference
because
. Hence by Lemma 3.5 ,
is a full subset of a b.p.
for some
. If
, then by the fact that
we have
If
, then the lemma follows from Lemma 3.4 .
(Subcase 3.8 .1.2) Subcase 3.8 .1.3
.
Suppose for any
in
we have
. Choose a
in
such that
. Since
, then
implies that
is full.
If
, then
, which contradicts the condition ( IV ).
Suppose
. Let
and
when
is odd, or let
such that
and
when
is even. Then
,
, and
are pairwise disjoint. Hence
| |
| |
| |
Suppose
or
. Then there are
in
such that
,
, and
are pairwise disjoint. Hence
by the same reason above.
Therefore, we can now assume that there is a
in
such that
.
Since
and
is not a subset of a
–unbounded b.p. of difference
because
, then by Lemma 2.2 there exists a
in
with
and
such that
. Hence by Lemma 2.3
, which implies
. This ends the proof.
(Case 3.8 .1) Case 3.8 .2
and
.
By Lemma 2.6 we can find
such that
is a backward triangle from
to
and
. Without loss of generality we can assume
. Then by Lemma 3.1 we have that
or
is a full subset of a b.p. of difference
. However, the former implies
by Lemma 2.3 and the latter is impossible because
.
(Case 3.8 .2) Case 3.8 .3
and
.
(Note that this case does not occur when
.) Since
is not a subset of a b.p., we can define
Let
,
, and
. Let
be the least element of
, respectively. Let
be the largest element of
, respectively. Note that the rest of the proof does not use the fact that
. Subcase 3.8 .3.1
.
We have
. We can also assume
because otherwise
Since
is a subset of a b.p., then by Theorem A.1 ,
is full and
is full. This implies
or
because
. Suppose
and
.
Then
| |
| |
| |
By the same reason, if
and
, then
. Note that if both
and
are true, then either
or
.
(Subcase 3.8 .3.1) Subcase 3.8 .3.2
.
Suppose
. If
, then the proof of this case is same as the proof in Case 3.8 .1 and Case 3.8 .2 by considering
in the place of
. So we can assume that
.
If
, then
. Note that
. We can assume
because if
, then
We can also assume
because otherwise let
such that
and for every
,
. Then
Let
. If
, then
| |
| |
| |
implies that
,
, and
are full. If
and
, then
| |
| |
| |
So we can assume
. By a similar argument we can also assume
. However, above assumptions imply that
| |
| |
| |
Suppose
. We re-define
to be
,
to be
,
, and
. Let
. Then
together with
imply that
,
, and
are all full. Note that
is always true. We can also assume
because otherwise we have
Hence we can assume
. Since there are
such that
,
, and
are pairwise disjoint, we have
| |
| |
| |
Therefore, we can now assume that
. If
, then by Lemma 2.6 there exist
such that
and
is a backward triangle. Since
, then
is not a subset of a b.p. of difference
. Clearly
is not a subset of a b.p. of difference
because
. Hence we have
by Lemma 3.5 and Lemma 2.3 . So we can now assume that
. let's re-define
to be
,
to be
,
, and
.
Then by Lemma 2.10 we have that
and
are full and
. We can also assume
because otherwise
, which implies
.
If
, then
. Since
,
, and
, then
, which implies
. Hence
| |
| |
| |
So we can assume
.
If
, then there is a
,
such that either
and
, or
. Let
be a finite set such that
and
. Then
| |
| |
| |
| |
| |
If
, then there is a
such that
is a forward triangle. Clearly
and
. Let
. Note that
. By Lemma 3.5 and Lemma 2.3 ,
implies that
is either a full subset of a b.p. of difference
or a full subset of a b.p. of difference
. Since
,
cannot be a subset of a b.p. of difference
. Let
be a full subset of the b.p.
for some
in
. Note that
. Then
| |
| |
| |
Now we can assume
. Suppose there is a
in
such that
, If
, then there is a
such that
is odd.
Hence
implies that
is full, which contradicts
. If
, then
, which contradicts
by Lemma 2.3 . So we can assume that there is an
in
such that
. Since
and
are full, we can assume
.
Hence
is neither a subset of an a.p. of difference
nor a subset of a
–unbounded b.p. By Lemma 2.2 there exists a
with
such that
and
. By Lemma 2.3 we have
, which implies
again by Lemma 2.3 .
(Case 3.8 .3) Case 3.8 .4
and
.
By Lemma 2.8 and ( IV ) we can find
such that
is a backward triangle and
. By ( IV ) we have
. If
, then the lemma follows from Lemma 3.5 . So we can assume
. Now the lemma follows from Lemma 3.6 unless
is a subset of a b.p. of difference
. Without loss of generality, let
be a subset of a b.p.
of difference
, where
for
. Let
and
. Then
. Let
.
Then
. If
, then
which implies
by Lemma 2.3 . So we can assume
.
Subcase 3.8 .4.1
. Then we have
. Hence we can find
such that
is a backward triangle from
to
and
. Since
contains two backward triangles, it cannot be a subset of a b.p. of difference
for
or
.
Hence by Lemma 3.5 we have
, which implies
.
(Subcase 3.8 .4.1) Subcase 3.8 .4.2
.
Let
. It is easy to see that
and
. Since
implies
, then we can assume that
is full in the b.p.
, which implies
. Hence
. So we can find a
with
such that
.
It is easy to show that there is a
such that
is a forward triangle. Since
cannot be a full subset of a b.p. of difference
, because it contains
, or
because
, then by Lemma 3.5 we have
. Since
is a subset of a b.p. of difference
we have
. By Lemma 2.3 we have
.
(Case 3.8 .4) Case 3.8 .5
.
Since
is not a subset of a b.p., the number
is well defined. Let
and
. Let
and
for
.
If
, then
because otherwise
is a subset of an a.p. with difference
. Hence we have either
or
. This implies
or
If
, then there are
such that
and
is a backward triangle. If
, then
is a full subset of either a b.p. of difference
or a b.p. of difference
. But both contradict
. So we can assume
.
Suppose
. By Lemma 2.10 we can show that
,
,
,
,
is full in
, and
is full in
.
Hence
| |
| |
| |
| |
Suppose
. Let
. Then we have
If
, then we have
| |
| |
| |
If
, then we have
| |
| |
| |
This ends the proof of Case 3.8 .5 as well as the lemma.
(Lemma 3.8 )
Lemma 3.9
Assume
,
, and
is a subset of a
–unbounded b.p. of difference
. If
is not a subset of a b.p., then
.
Proof: Suppose
is a subset of the
–unbounded b.p.
for some
. Clearly
. Let
. Note that
. By Lemma 3.8 we can assume
. If
, then we can find
such that
and
is a backward triangle from
to
. Note that
cannot be a subset of a b.p. of difference
because otherwise
is a subset of an a.p. of difference
. By Lemma 2.3 we can assume
. By Lemma 3.5
is a full subset of a b.p.
, which contradicts the assumption
. So we can assume
.
If
, then the proof of the lemma is the same as the proof of Case 3.8 .5. Suppose
. If
and
, then the lemma follows from Lemma 3.8 . If
or
, then
implies
, which implies
is a full subset of a b.p. of difference
. Since
is already a subset of the b.p., then
, which contradicts
.
(Lemma 3.9 ) Now we summarize all the proofs in this section into a theorem, which takes care of the case in Theorem 1.7 under the condition ( IV ).
Theorem 3.10
Assume
and
. Suppose
and
. If
is not a subset of a b.p., then
.
Proof: By Lemma 3.8 we can assume that for every
, if
, then
for every
. If there is a
in
such that
and
, then the theorem is true again by Lemma 3.8 with
replaced by
. So we can assume that for every
in
, if
, then
. We now divide the proof into four cases according to the value of
.
Case 3.10 .1
.
Then there is a
such that
is a forward triangle from
to
. Since
, then
. Now the theorem follows from Lemma 3.5 .
Case 3.10 .2
.
If
is a subset of an a.p. of difference
, then the theorem follows from Lemma 3.8 . If
is a subset of a
–unbounded b.p., then the theorem follows from Lemma 3.9 .
Otherwise by Lemma 2.2 we can find a
with
such that
and
. If
, then the theorem is already true because
. So we can assume
. If
, then the theorem follows from Lemma 3.8 . If
, then the theorem follows from Lemma 2.3 .
(Case 3.10 .2) Case 3.10 .3
and there is a
such that
.
By Lemma 2.6 we can find such
such that for any
,
.
If
, then we can find
such that,
, and
is a backward triangle. If
, then the theorem follows from Lemma 3.5 . Suppose
. Note that
cannot be a full subset of a b.p. of difference
by the condition of the case. Hence the lemma follows from Lemma 3.6 .
If
and
is a subset of an a.p. of difference
, then the theorem follows from Lemma 3.8 . If
and
is not a subset of an a.p. of difference
, then
(Case 3.10 .3) Case 3.10 .4
and for every
,
.
By symmetry we can also assume
and for every
,
.
Let
. Then
. By Lemma 2.6 there is a
in
such that
and
for every
. By the assumption of this case, we have
and
. If there is a
such that
or
is a subset of an a.p. of difference
, then the theorem follows from Lemma 3.8 . Note that
by the choice of
. By Lemma 2.3 we can assume
.
By Case 3.10 .1 and Case 3.10 .2 for
we can assume that
is a subset of a b.p. of difference
. Clearly
is a full subset of the b.p. If
, then
is a full subset of
, which implies either
or
. Each of them contradicts the assumption of the case. If
, then
, which is again a contradiction to the assumption of the case.
(Theorem 3.10 )
4 Second Step: When
is almost
.
In this section we again assume
,
, and
. In addition we also assume
|
(VI)
|
and
|
(VII)
|
for
. ( VII ) implies
. Under the condition above we want to prove
|
(VIII)
|
Without loss of generality, we can assume that
|
(IX)
|
because otherwise ( VIII ) is trivially true. In this section the letter
is reserved only for the purpose in ( VII ).
Lemma 4.1
Let
and let
. Suppose
and
. If
|
(X)
|
then
,
, and
.
Proof: If
, then
. By Theorem A.2 we have
, which contradicts
. So we can assume
. By the assumption of the lemma we have
. Hence
. Since
| |
| |
| |
then
. If
, then by Theorem A.1
is a subset of an a.p. of length
, which implies
, a contradiction to ( X ). Hence
. Finally
.
(Lemma 4.1 )
Lemma 4.2
If there is an
such that
is a subset of a b.p. of difference
, then
.
Proof: Without loss of generality we can assume
and
is not a subset of a b.p. of difference
. Fix
such that
where
and
for
. For
let
and
. For
let
and let
. Clearly
. Since
then we have
for
. By Theorem A.1 we have that
is full for
. Note that
for
by ( V ). If
and
, then
. By symmetry we can also prove that
and
together are impossible. So we can assume
and
. Without loss of generality we assume
. Then
implies
.
Suppose the lemma is not true. Then we can assume that ( VII ), ( IX ), and ( X ) are true.
Without loss of generality we can assume that
is the maximum among all the sets in
containing the original set and satisfying ( VII ), ( IX ), and ( X ).
Claim 4.2 .1: If
and
for
or
, then
. Proof of Claim 4.2 .1: Suppose not and let
. By Lemma 4.1 and by the maximality of
we need only to show that
for a contradiction. First let
. Let
.
If
and
, then
for some
, which implies
, by the pigeonhole principle.
If
and
, then
for some
, which implies
. If
and
, then
for some
, which implies
. If
and
, then
for some
, which implies
. If
, then
. Since
is full, then there are
and
such that
. Hence
. By all the arguments above we have
.
For the case that
the proof is similar.
(Claim 4.2 .1) Claim 4.2 .2: If
and
, then
.
Proof of Claim 4.2 .2: Suppose not and let
be the least number such that the claim is not true. By Claim 4.2 .1 we have
. Let
. It suffices to show
. Let
.
If
and
, then
for some
, which implies
. If
and
, then
by the minimality of
. If
and
, then
for some
, which implies
. If
and
, then
. If
, then
by the facts that
is full and
. Hence
.
(Claim 4.2 .2) Claim 4.2 .3: If
and
, then
.
Proof of Claim 4.2 .3: Suppose not and let
be the least number such that the claim is not true. By Claim 4.2 .1 we have
. Let
. Again it suffices to show
. Let
.
If
and
, then
for some
, which implies
. If
and
, then
by the minimality of
. If
and
, then
for some
, which implies
. If
and
, then
. Note that
by Claim 4.2 .1 and Claim 4.2 .2. If
and
, then
.
Hence
.
(Claim 4.2 .3) Claim 4.2 .4: There is an
such that
and
imply
.
Proof of Claim 4.2 .4: Suppose not and let
for
. By Claim 4.2 .1 we have
.
Subclaim 4.2 .4.1:
.
Proof of Subclaim 4.2 .4.1: Suppose the subclaim is not true. Without loss of generality we assume
. Let
. Since
, then
for
by the maximality of
. By the similar arguments in the last several claims we have
.
This contradicts the maximality of
by Lemma 4.1 . By a symmetric argument we can show
is also impossible.
(Subclaim 4.2 .4.1) Case 4.2 .4.1:
.
Let
. Note that
. Then
for
. Hence by the similar arguments as in Subclaim 4.2 .4.1 we can show
.
(Case 4.2 .4.1) Case 4.2 .4.2:
.
Let
. Then
for
by the maximality of
. Hence
.
(Case 4.2 .4.2) Following the two cases above we have
. By symmetric arguments we can also show that
. Subtracting the second equality from the first we have
. This implies
. But by Subclaim 4.2 .4.1 we have
. Hence
, which is absurd.
(Claim 4.2 .4) Claim 4.2 .5: If
and
, then
for
. Proof of Claim 4.2 .5: Suppose the claim is not true. By Claim 4.2 .4 we can assume, without loss of generality, that
and
imply
.
Let
. Let
. Then
. It is now easy to see that
. This contradicts the maximality of
.
(Claim 4.2 .5) Claim 4.2 .6:
and
.
Proof of Claim 4.2 .6: By symmetry we need only to show the first inequality. Assume it is not true and we have
. Then
. Let
and
.
Let
.
If
and
, then
. If
and
, then
for some
, which implies
. If
and
, then
for
. If
and
, then
. Hence
, a contradiction to the maximality of
by Lemma 4.1 .
(Claim 4.2 .6) Claim 4.2 .7: Let
and
. Then ( VII ), ( IX ), and ( X ) maintain true with
and
being replaced by
and
, respectively.
Proof of Claim 4.2 .7: By Lemma 4.1 it suffices to prove
. Suppose not. We derive a contradiction.
Subclaim 4.2 .7.1:
.
Prove of Subclaim 4.2 .7.1: Assume the subclaim is not true. So we have
. Let
If
and
, then
. If
and
, then
. If
, then
. Hence
for
. Now we have
, which contradicts the assumption that
.
(Subclaim 4.2 .7.1) We now ready to derive a contradiction. By Claim 4.2 .6 and Subclaim 4.2 .7.1 we have
. This implies
. Hence
. So by Subclaim 4.2 .7.1 again we have
. Since
, then
. We want to show
. Suppose
. Then by Claim 4.2 .6 and Subclaim 4.2 .7.1 we have
and
. So
implies
, which is absurd because
implies
. By symmetry we also have
. Hence
. By Claim 4.2 .6 and Subclaim 4.2 .7.1 again we have
and
, which imply
or equivalently
. Hence by Subclaim 4.2 .7.1 we have
. Note that
. So
. Assume
. The
or
. But each of the two cases contradicts the inequality
in Claim 4.2 .6 with
.
(Claim 4.2 .7) By Claim 4.2 .7 we can add
successively to
to form a set
so that ( VII ), ( IX ), and ( X ) maintain true with
and
being replaced by
and
, respectively. However, ( IX ) will be eventually violated in this process.
(Lemma 4.2 )
Lemma 4.3
Let
for
. If there is an
such that
, then
.
Proof: The ideas are same as in the proof of Lemma 4.2 . We will describe the steps without too much technical details. Let
,
,
, and
for
.
Without loss of generality let
. By Lemma 4.2 we can assume
.
Since
then
implies that
is full for
. Note that
,
, and
.
Suppose the lemma is not true. Without loss of generality we can assume that
is the maximum among all the sets in
containing the original set and satisfying ( VII ), ( IX ), and ( X ). Without loss of generality let's assume
.
Case 4.3 .1
.
If
, then
So we can assume
. By symmetry we can assume
. Since
by ( V ), we have
and
. Hence
This implies
by Lemma 4.1 and the maximality of
. Then we can show
again by Lemma 4.1 and the maximality of
. Furthermore, we can show
by the fact that
and by Lemma 4.1 . Now we add
,
,
, etc. successively to
so that the set maintains satisfying ( VII ), ( IX ), and ( X ). However, this process will eventually violate ( IX ).
(Case 4.3 .1) Case 4.3 .2
.
We can again show that
and
because otherwise we can show
. Since
, then
, which implies
and
. Again assume that
has the maximum cardinality among the sets satisfying ( VII ), ( IX ), and ( X ). Then we can show
for
.
Finally we can again add
,
,
, etc. successively to
so that the set maintains satisfying ( VII ), ( IX ), and ( X ). Again this process will eventually violate ( IX ).
(Lemma 4.3 )
Lemma 4.4
Suppose there are
such that
is a backward triangle as well as a subset of a b.p. of difference
and
is a forward triangle as well as a subset of a b.p.
of difference
. Then
.
Proof: The ideas are again the same as in the proof of Lemma 4.2 . Let
for
. By Lemma 4.3 we can assume that
and
.
For
let
,
,
, and
. Then we have
. Suppose the lemma is not true. Then
satisfies ( VII ), ( IX ), and ( X ). We again assume the maximality of
for
satisfying ( VII ), ( IX ), and ( X ). By Lemma 4.1 we can prove that for each
,
implies
. Then we can prove
by the same ideas as in the proof of Lemma 4.2 . Now we can add
successively to
such that the conditions ( VII ), ( IX ), and ( X ) maintain true. But this process will eventually violate ( IX ).
(Lemma 4.4 )
Lemma 4.5
If there is a
in
such that
, then
.
Proof: Since ( V ) is true, then
. Let
. Then
,
, and
is full. Let
be the set of all even numbers and
be the set of all odd numbers. Let
and
. Let
,
,
, and
.
Case 4.5 .1
is even.
Then
,
, and
is full. We want to show
.
Let
. Then
. By Theorem A.1 we have
.
On the other hand, by Theorem A.4 ,
If
, then
| |
| |
| |
This implies
. Hence
, which implies
.
If
, then
, which contradicts ( IX ).
(Case 4.5 .1) Case 4.5 .2
is odd.
Clearly,
and
. If
, then
is a subset of a b.p. Hence we can assume
and need to show
. Suppose
. Let
If
, let
. Otherwise, let
. Let
If
, let
. Otherwise, let
. Note that
. Since
is full, then
and
. For each
, we have
and for any
, we have
. By the pigeonhole principle
Let
,
, and
. Let
. Then
. Hence
This implies, by Theorem A.1 ,
Subcase 4.5 .2.1
.
Since
| |
| |
| |
| |
| |
then
. Hence
| |
| |
| |
| |
This implies
and
(Subcase 4.5 .2.1) Subcase 4.5 .2.2
.
Since
and
, then there exists a
such that
and
because otherwise we can find three disjoint intervals of length
for
in
such that each contains at least
elements from the set
. This contradicts the assumption
. Suppose
.
We want to derive a contradiction by induction on the size of the counterexamples
.
Suppose
is the set with the maximum cardinality
such that
,
for
, and
.
Claim 4.5 .2.2.1
.
Proof of Claim 4.5 .2.2.1: Suppose the claim is not true and let
. Let
and
. Note that if
, then
.
Hence
. Let
. Since
| |
| |
| |
| |
then
. Hence
. Now we have that
, which contradicts the maximality of
by Lemma 4.1 .
(Claim 4.5 .2.2.1) Claim 4.5 .2.2.2
.
Suppose the claim is not true and let
. Let
, and
. Then
. Note that if
, then
.
Hence
. If
, then
by the minimality of
and Claim 4.5 .2.2.1. Hence
. If
, then
. If
, then
.
From the arguments above, we have
, which contradicts the maximality of
by Lemma 4.1 .
(Claim 4.5 .2.2.2) Claim 4.5 .2.2.3
.
Proof of Claim 4.5 .2.2.3: Suppose the claim is not true and let
. Let
. Then
, which contradicts the maximality of
.
(Claim 4.5 .2.2.3) By the three claims above we have
.
Without loss of generality, we can assume that our original counterexample
satisfies
. Hence
. Note also that since
, we can assume that
.
Claim 4.5 .2.2.4
.
Proof of Claim 4.5 .2.2.4: Suppose
. For each even number
let
. Let
| |
| |
Clearly,
. For each
,
, which implies
. Let
. We now derive a contradiction.
By Theorem A.2 we can assume
. Note that since
, we have
Since for each
,
. Hence
, which contradicts the maximality of
by Lemma 4.1 .
(Claim 4.5 .2.2.4) Let
. Then
must be an even number. Let
and
.
Subsubcase 4.5 .2.2.1
.
First we can assume that
by the following argument.
Let
. Then
. Note that
. Since
and
, then there is a
such that
| |
| |
| |
| |
This shows
. So
| |
| |
| |
| |
Hence
is the desired counterexample. Now identify
with
.
Subsubsubcase 4.5 .2.2.1.1
.
Since
, then
and
.
Hence we have
. So we have
| |
| |
| |
| |
This shows
. On the other hand,
| |
| |
| |
| |
This contradicts the assumption that
.
(Subsubsubcase 4.5 .2.2.1.1) Subsubsubcase 4.5 .2.2.1.2
.
Then we have
| |
| |
| |
| |
This shows
. On the other hand,
| |
| |
| |
| |
by the assumption
. This again contradicts
.
(Subsubcase 4.5 .2.2.1) Subsubcase 4.5 .2.2.2
.
Subsubsubcase 4.5 .2.2.2.1
for some
.
Since
, then by Theorem A.1
. We also have
| |
| |
| |
which implies
. Hence
| |
| |
| |
This implies
. Hence
because
implies
.
(Subsubsubcase 4.5 .2.2.2.1) Subsubsubcase 4.5 .2.2.2.2
and
.
Since
| |
| |
then
. Hence
implies
| |
| |
| |
Since
| |
| |
then
| |
| |
| |
Hence
, a contradiction.
(Subsubsubcase 4.5 .2.2.2.2) Subsubsubcase 4.5 .2.2.2.3
and
.
This time we use the fact that
implied by Claim 4.5 .2.2.4. Since
| |
| |
then
. Hence
| |
| |
| |
This ends the proof of the lemma.
(Lemma 4.5 )
Lemma 4.6
Suppose
, where
is the set of all even numbers in
and
is the set of all odd numbers in
. Let
for
and
.
If (a)
and
or (b)
,
, and
, then
.
Proof: The proof of (a) of the lemma is identical to the proof of Case 4.5 .1. We sketch the proof of (b) using Lemma 4.1 . It is easy to see that
is full in
and
is full in
. Suppose the lemma is not true. Following the same ideas as in the proof of Claim 4.2 .1, Claim 4.2 .2, and Claim 4.2 .3, we can assume that
. However, this implies
which contradicts ( IX ).
(Lemma 4.6 )
Lemma 4.7
If
is a forward triangle from
to
, then
.
Proof: Assume the lemma is not true and we need to derive a contradiction. Clearly we have
. Furthermore we can assume
by the following argument: If
, then there exists
in
such that for all
If for every
in
we have
, then there is a
in
such that
by Lemma 2.7 . This implies that for each
we have
, which contradicts that
is a forward triangle. Hence we can choose
with
in
such that
. By Lemma 2.3 we have
. Let
Note that the smallest possible value of
is
. Note also that
is well defined because
. It is easy to check that
,
, and for every
in
we have
by the maximality of
.
Define
by
The number
is well defined by the fact that
,
, and
.
It is also easy to check that
,
is a forward triangle from
to
,
, and
. If
, then
by the minimality of
.
Let
.
Claim 4.7 .1:
.
Proof of Claim 4.7 .1: Let
. If
, then
. Hence
This implies
. Hence
. If
, then
. Hence
. This again implies
.
(Claim 4.7 .1) Let
. If
, then
. Hence
is a subset of the b.p.
. So from now on in this lemma we can assume
.
Claim 4.7 .2: Suppose
and
. If
, then
.
Proof of Claim 4.7 .2: Since
and
, then
| |
| |
Note that
. Since
, then
. Hence
| |
| |
This shows that
, which implies
.
(Claim 4.7 .2) Let
.
Claim 4.7 .3: Suppose
and
. If
, then
or
.
Proof of Claim 4.7 .3: Assume
. Since
, then
. Hence
| |
| |
Hence
. This shows
. If
, then
. If
, then
.
(Claim 4.7 .3) Claim 4.7 .4:
.
Proof of Claim 4.7 .4: The proof is divided into three cases for
,
, and
.
Case 4.7 .4.1:
.
By Claim 4.7 .2 we have
(this can be proven by induction on
). Hence
because
. So we have
| |
| |
| |
(Case 4.7 .4.1) Case 4.7 .4.2:
.
By Claim 4.7 .3 we have
. Hence
| |
| |
| |
| |
(Case 4.7 .4.2) Case 4.7 .4.3:
.
By Claim 4.7 .2 we have
and by Claim 4.7 .3 we have
. Hence
| |
| |
| |
| |
(Claim 4.7 .4) We now prove the lemma. The proof is divided into two cases. The first case is easy and the second case is hard.
Case 4.7 .1
.
Since
, then by Theorem A.4 we have
. Hence
| |
| |
| |
| |
| |
| |
This shows
. Hence
| |
| |
(Case 4.7 .1) Case 4.7 .2
.
Note that Case 4.7 .1 covers the case for
. So we can assume
. First we prove a claim.
Claim 4.7 .2.1 If
, then
.
Proof of Claim 4.7 .2.1 By the assumption we have
| |
| |
| |
| |
| |
Hence
. This implies
| |
| |
(Claim 4.7 .2.1) By Claim 4.7 .2.1 we need only to show that
is true. We divide the proof into cases according to the structural properties of
.
Subcase 4.7 .2.1
.
Note that
and
by the condition of Case 4.7 .2. Since
, then
and
. Since
, there is a
such that for all
in
we have
. Let
. Then there is a non-negative infinitesimal
such that
. By Theorem A.4 we have
| |
| |
| |
Since
| |
| |
| |
and
| |
| |
by the fact that
, then we have
| |
| |
Hence
| |
| |
| |
| |
Since
is an integer, then we have
Now the lemma follows from Claim 4.7 .2.1.
(Subcase 4.7 .2.1) Subcase 4.7 .2.2
but
.
Again let
be such that
for all
in
.
Claim 4.7 .2.2.1 For each
,
.
Proof of Claim 4.7 .2.2.1: We prove the claim by induction on
.
The case of
is trivially true.
Suppose the claim is true for
. Let
. Since
, and
for some
implies
or
, then
| |
| |
| |
for some non-negative infinitesimal
. Since either
or
, and
is an integer, then we have
Hence
| |
| |
| |
| |
(Claim 4.7 .2.2.1) Following Claim 4.7 .2.2.1 we now have
| |
| |
This implies
| |
| |
| |
| |
Now the lemma follows from Claim 4.7 .2.1.
(Subcase 4.7 .2.2) Subcase 4.7 .2.3
.
Note that
. Suppose
. If
, then
is a subset of the b.p.
.
Hence the lemma follows from Lemma 4.2 . So we can assume that
.
This implies
and hence
| |
| |
| |
| |
Now the lemma follows from Claim 4.7 .2.1. So we can assume
Suppose
, where
.
If
, let
Then
and
.
Hence
| |
| |
| |
| |
| |
Now the lemma follows from Claim 4.7 .2.1.
If
, let
.
Then
. Hence
| |
| |
| |
| |
| |
| |
| |
| |
This implies the lemma.
Now we can assume that
. For
let
Clearly
for
. By Theorem A.4 ,
Let
. Note that each term
in the sum has two possible lower bounds
or
. We divide the proof into the cases according to the different combinations of these lower bounds of
for
.
Subsubcase 4.7 .2.3.1
.
Together with the assumption of Case 4.7 .2, this subsubcase implies
Hence
| |
| |
| |
| |
Now the lemma follows from Claim 4.7 .2.1.
(Subsubcase 4.7 .2.3.1) Subsubcase 4.7 .2.3.2
.
Then
. Hence
| |
| |
| |
| |
(Subsubcase 4.7 .2.3.2) Subsubcase 4.7 .2.3.3
.
If
, then
and
. Hence
, which implies the assumption of Subsubcase 4.7 .2.3.1. So we can assume
and
. Since
and
, then
for some non-negative infinitesimal
. Hence
| |
| |
| |
| |
Hence again
(Subsubcase 4.7 .2.3.3) Subsubcase 4.7 .2.3.4
.
Again we can assume
and
. Then
| |
| |
for some non-negative infinitesimal
. Hence
. This implies
which again implies the lemma. The rest of the cases can be proven by symmetry of the proofs above.
(Lemma 4.7 )
Lemma 4.8
Suppose
such that
is a backward triangle from
to
and
is a forward triangle from
to
. Then
.
Proof: Let
Clearly
because
is a backward triangle. Also
because otherwise
Hence we have
. It is easy to see that
and
by the minimality of
. Also by the minimality of
we have that for any
,
.
Let
If
, let
. Otherwise let
. It is also easy to see that
,
, and
. Since
,
, and
, then the number
below is well defined.
Clearly
,
,
, and
. By the minimality we have that for any
,
. Now let
and
.
Since
and
, then
. Let
.
Without loss of generality we can assume that
is not a subset of a b.p. of difference
by the following reason:
Suppose not. By symmetry, we can also assume that there is a
such that
is a subset of a b.p. of difference
. Now the lemma follows from Lemma 4.4 .
The rest of the proofs are almost identical to the proofs of Lemma 4.7 . We will refer to the proofs of Lemma 4.7 when the steps are the same and add more proofs when the steps are not the same.
Claim 4.8 .1:
.
Proof of Claim 4.8 .1: The proof here is slightly different from the proof of Claim 4.7 .1.
If
, then
. Hence
. This implies
. Hence
. Suppose
. Then
.
If
, then
. Hence
, which implies
. If
, then by choosing a
with
we have
. Hence
, which implies
. Suppose
. If
, then by
we have
, which implies
. If
, then
. Hence
, which again implies
.
(Claim 4.8 .1) Claim 4.8 .2: Suppose
and
. If
, then
.
Proof of Claim 4.8 .2: The proof is identical to the proof of Claim 4.7 .2.
(Claim 4.8 .2) Claim 4.8 .3: Suppose
and
. If
, then
or
.
Proof of Claim 4.8 .3: Identical to the proof of Claim 4.7 .3.
(Claim 4.8 .3) Claim 4.8 .4:
.
Proof of Claim 4.8 .4: The proof is divided into three cases for
,
, and
.
Case 4.8 .4.1:
.
Identical to the proof of Case 4.7 .4.1.
(Case 4.8 .4.1) Case 4.8 .4.2:
.
Identical to the proof of Case 4.7 .4.2.
(Case 4.8 .4.2) Case 4.8 .4.3:
.
Identical to the proof of Case 4.7 .4.3.
(Case 4.8 .4.3) Now we prove the lemma. The proof is divided into two cases.
Case 4.8 .1
.
Identical to the proof of Case 4.7 .1.
(Case 4.8 .1) Case 4.8 .2
.
Claim 4.8 .2.1 If
, then
.
Proof of Claim 4.8 .2.1 Identical to the proof of Claim 4.7 .2.1.
(Claim 4.8 .2.1) By Claim 4.8 .2.1 we need only to show that
is true. We divide the proof into cases according to the structural properties of
.
Subcase 4.8 .2.1
.
The proof is the same as the proof of Subcase 4.7 .2.1 except that the term
needs to be replaced by the term
throughout the remaining of the proof of the lemma. Note that we can also assume that
by the same reason as stated at the beginning of the proof of Lemma 4.7 .
(Subcase 4.8 .2.1) Subcase 4.8 .2.2
but
.
Claim 4.8 .2.2.1 For each
,
.
Proof of Claim 4.8 .2.2.1: Identical to the proof of Claim 4.7 .2.2.1.
(Claim 4.8 .2.2.1) Following Claim 4.8 .2.2.1 we now have
| |
| |
This implies
| |
| |
| |
| |
Now the lemma follows from Claim 4.8 .2.1.
(Subcase 4.8 .2.2) Subcase 4.8 .2.3
.
the proof is identical to the proof of Subcase 4.7 .2.3. Note that we assume
in the beginning of the proof of this lemma.
(Lemma 4.8 )
Lemma 4.9
Suppose
with
such that
is a backward triangle and
is a subset of an a.p. of difference
. Then
.
Proof: Since ( V ), we have
, which implies
. Let
be the set of all even numbers and let
. Then
and
is full. Without loss of generality we can assume that
and
is odd. By the pigeonhole principle and Lemma 2.7 we can find
and
such that
.
Claim 4.9 .1: If
, then
.
Proof of Claim 4.9 .1: If
, then
. Hence
. So
, which implies
. Now we assume
. Let
. Then
implies
. Choose a
with
. Then
. Hence
| |
| |
and
. Hence
, which implies
.
(Claim 4.9 .1) Now let's assume that the lemma is not true. Let
be the set with the largest cardinality
such that
,
, and satisfying ( VII ), ( IX ), and ( X ) with
replaced by
and
replaced by
. We will derive a contradiction.
Claim 4.9 .2:
.
Proof of Claim 4.9 .2: The proof is divided into three cases. Let
be such that
. We want to show that
.
Case 4.9 .2.1
.
Suppose
. Let
. For each
,
, and for each
we have
, which implies
. Hence
by Claim 4.9 .1. So
, which contradict the maximality of
by Lemma 4.1 .
(Case 4.9 .2.1) Case 4.9 .2.2:
and
.
Suppose
. Without loss of generality we can, by Case 4.9 .2.1, assume
Let
.
If
, then
and
. Hence
, which implies
. If
and
, then choose a
such that
. Hence
and
imply
, which implies
.
If
, then choose a
with
such that
. Hence
and
imply
, which implies
.
If
, then
. Hence
is even and
. Now we have
.
If
,
, and
is even, then
by the maximality of
. Hence
.
If
,
is odd, and
, then
. Hence
.
By the arguments above we conclude that
. Hence
, which contradicts the maximality of
by Lemma 4.1 . So we conclude that
.
(Case 4.9 .2.2) Case 4.9 .2.3:
.
Suppose again
. Let
. By Case 4.9 .2.1 we have
.
Let
.
If
, then
.
If
, then
, which implies, by Claim 4.9 .1,
.
If
and
, then
by the minimality of
. Hence
.
If
,
, and
is odd, then
is even and
by the minimality of
. Hence
.
If
,
, and
is even, then
. Hence
.
By the arguments above we conclude that
, which contradicts the maximality of
by Lemma 4.1 .
(Claim 4.9 .2) Now we are ready to prove the lemma. Without loss of generality we can assume that the set
is already in the form of the set
in Claim 4.9 .2. Let
. Note that if there is a
such that
is a subset of a b.p. of difference
, then
implies that
is full in the b.p. Hence
or
because
is a backward triangle. However,
is a full subset of an a.p. of difference
, which contradicts
or
. Hence we have
. By ( IX ) and
we have
.
Let
. If
, then by Theorem A.1 we have
, which contradicts
. Hence we can assume
. Clearly
because otherwise we would have
. By Lemma 4.7 , we have
. Hence
| |
| |
| |
Above shows
. Hence
| |
| |
which contradicts
.
(Lemma 4.9 )
Lemma 4.10
If
, then
.
Proof: If
, then there exists a
such that
is a forward triangle. If
, then the lemma now follows from Lemma 4.7 . If
, then the lemma follows from Lemma 3.5 .
(Lemma 4.10 )
Lemma 4.11
Let
. If there is a
in
such that
, then
is either a subset of an a.p. of difference
or a subset of a
–unbounded b.p.
Proof: The lemma follows from Lemma 2.4 and Lemma 2.2 .
(Lemma 4.11 )
Lemma 4.12
Let
. If
is a subset of a
–unbounded b.p., then
.
Proof: Suppose
is a subset of a
–unbounded b.p. of difference
. Since
, then
or
. Let
and
where
. Then
. Since
or
, then
. By Lemma 4.6 we can assume that there is an
in
such that
.
Case 4.12 .1:
.
We want to show this case implies
, hence
is impossible.
By Lemma 2.4 it suffices to show that for
and for every
there is a
with
such that ( III ) is true. Suppose
is given. Let
. Without loss of generality we can re-choose
so that
,
, and for every
we have
. Choose a
with
such that
.
Let
. It is easy to see that
because for any two consecutive numbers in
, at least one of them is not in
.
Hence we have that
and
. Note that
. So the shortest b.p. containing
must have length
. Let
for
. Since
, then
. By the same reason we have
. Let
for some integer
. Since
is a subset of a b.p., then
.
If
, then
which implies ( III ).
If
, then by Theorem A.3 we have that
Hence
. So we have
which again implies ( III ). This ends the proof.
(Case 4.12 .1) Case 4.12 .2:
.
Without loss of generality we assume
and
. Suppose
is not a subset of a b.p. We want to derive a contradiction. Let
Let
where
for
. Then
for
because otherwise
. Note that since
, then there is an
or
such that
. Hence we can assume
because otherwise
.
Subcase 4.12 .2.1:
. By Lemma 2.6 there exist
such that
is a backward triangle and
.
If
, then the lemma follows from either Lemma 3.5 or Lemma 3.7 . so we can assume
.
If
, then the lemma follows from Lemma 4.7 . So we can assume
. If for any
in
,
, then the lemma follows from Lemma 4.9 . So we can assume that there is a
,
such that
.
If
, then by Lemma 2.6 there is a
such that
is a forward triangle. Now the lemma follows from Lemma 4.8 if
. If
, then by Lemma 3.5
implies that
is a full subset of a b.p.
. Hence
is the union of a forward triangle
and a backward triangle
. Now the lemma follows from Lemma 3.4 .
If
, then by Lemma 2.6 there are
such that
is a backward triangle and
. Now the lemma follows from Lemma 3.5 because
cannot be a full subset of a b.p. of difference
or
.
Assume
. Since
is a backward triangle, then we can assume
. Hence
is neither a subset of an a.p. of difference
nor a subset of a
–unbounded b.p. of difference
. If
is a subset of a
–unbounded b.p. of difference
, then by the proof of Case 4.12 .1 we have
, which implies
. Note that if there is an
in
such that
, then
and the lemma follows from Lemma 4.9 . So we can assume that
is neither a subset of an a.p. of difference
nor a subset of a
–unbounded b.p. and there is a
in
such that
. Now the lemma follows from Lemma 2.2 , Lemma 2.4 , and Lemma 2.3 .
(Subcase 4.12 .2.1) Subcase 4.12 .2.2:
.
By ( V ) we have
. Since
and
, then
is full for
. Hence we can find a
in
such that
. Since there is an
such that
, then by Lemma 2.3 we have
.
(Lemma 4.12 )
Lemma 4.13
Let
. If
is a subset of an a.p. of difference
, then
.
Proof: Let
. Since
, then
and
is odd.
Case 4.13 .1: There are
such that
is a backward triangle and
.
Note that
. By Lemma 3.5 we have either
, which is impossible because it implies
by Lemma 2.3 , or
is a full subset of a b.p.
, which contradicts
, or
is a full subset of a b.p. of difference
, which again contradicts
.
(Case 4.13 .1) Case 4.13 .2:
.
By lemma 2.6 there are
such that
and
is a backward triangle. Without loss of generality we can assume that
. By Case 4.13 .1 we can assume
and by Lemma 4.7 we can assume
.
Subcase 4.13 .2.1:
.
By Lemma 2.6 there is a
such that
is a forward triangle. If
, then the lemma follows from Lemma 4.8 . So we can assume
. By Lemma 2.3 we can assume
. By Lemma 3.5 this implies that
is either a full subset of a b.p. of difference
or a full subset of a b.p. of difference
. Note that
. So
cannot be a full subset of a b.p. of difference
because that would imply
. If
is a full subset of the b.p.
, then
because otherwise
is a forward triangle, which contradicts
. However,
implies that
is the union of a forward triangle
and a backward triangle
, which implies
by Lemma 3.4 .
(Subcase 4.13 .2.1) Subcase 4.13 .2.2:
.
By Lemma 2.6 there are
such that
is a backward triangle and
. By Lemma 3.5 we have
because
cannot be a full subset of a b.p. of difference
or
. Hence
by Lemma 2.3 .
(Subcase 4.13 .2.2) Subcase 4.13 .2.3:
.
If for every
in
,
, then there is an
such that
is a subset of an a.p. of difference
. Hence the lemma follows from Lemma 4.9 . So we can assume that there is a
in
such that
.
Note that
. Hence
is neither a subset of an a.p. of difference
nor a subset of a
–unbounded b.p. of difference
. If
is not a subset of a
–unbounded b.p. of difference
, then the lemma follows from Lemma 2.4 and Lemma 2.3 .
If
is a subset of a b.p. of difference
, then again
by the proof of Case 4.12 .1, which again implies
by Lemma 2.3 .
(Case 4.13 .2) Case 4.13 .3:
.
Since
, then we have
and
. Let
. Then
and
is full.
Subcase 4.13 .3.1:
.
By Lemma 2.6 there is a
such that
is a forward triangle. If
, then the lemma follows from Lemma 4.9 . So we can assume
, which implies that
cannot be a full subset of a b.p. of difference
. By Lemma 2.3 we can assume that
. Hence by Lemma 3.5
is a full subset of a b.p.
for some
. If
, then
is a forward triangle, which contradicts
. If
, then
is a backward triangle. Now the lemma follows from Lemma 3.4 .
(Subcase 4.13 .3.1) Subcase 4.13 .3.2:
.
By Lemma 2.6 there are
such that
is a backward triangle and
. Now the lemma follows from Lemma 3.5 or Lemma 3.7 .
(Subcase 4.13 .3.2) Subcase 4.13 .3.3:
.
If there exists a
in
such that
, then
and the lemma follows from Lemma 4.6 . So we can assume that there is a
in
such that
. Since
, then
implies that
is full. Without loss of generality we can assume
. Hence
is neither a subset of an a.p. of difference
nor a subset of a
–unbounded b.p. Now the lemma follows from Lemma 2.2 , Lemma 2.4 , and Lemma 2.3 .
(Lemma 4.13 )
Lemma 4.14
Suppose
. Then
.
Proof: Since
, by (4) of Lemma 2.6 there are
such that
is a backward triangle from
to
and
. If
and
, then the lemma follows from Lemma 4.7 . If
and
, then the lemma follows from Lemma 3.5 . If
and
, then
. Hence the lemma follows from Lemma 3.6 because
cannot be a full subset of a b.p. of difference
.
So we can now assume
and
.
If
, then there is a
such that
is a forward triangle. If
, then the lemma follows from Lemma 4.8 . If
, then
cannot be a full subset of a b.p. of difference
because
. Hence the lemma follows from Lemma 3.6 .
If
, then there are
such that
and
is a backward triangle. Note that
contains two backward triangle, hence is not a full subset of a b.p. By Lemma 3.5 we have
. Hence
by Lemma 2.3 .
Assume
. Since
is a backward triangle, we can assume there is a
in
such that
. This implies (1)
is not a subset of an a.p.
of difference
and (2) if
is a subset of a
–unbounded b.p. of difference
, then
.
Suppose
is a subset of a
–unbounded b.p. of difference
. By Case 4.12 .1 we have
, which imply
.
Suppose
is not a subset of a
–unbounded b.p. of difference
. If for each
in
,
, then the lemma follows from Lemma 4.9 . So we can assume that there is a
such that
. Now the lemma follows from Lemma 2.2 , Lemma 2.4 , and Lemma 2.3 .
(Lemma 4.14 )
Theorem 4.15
Let
be such that
,
,
is not a subset of a b.p.,
,
, and
for
. Then
.
Proof: If
, then the theorem follows from Lemma 4.10 . If
, then the theorem follows from Lemma 4.14 . Suppose
.
If
is a subset of an a.p. of difference
, then the theorem follows from Lemma 4.13 . If
is a subset of a
–unbounded b.p., then the theorem follows from Lemma 4.12 . So we can assume that
is neither a subset of an a.p. of difference
nor a subset of a
–unbounded b.p. Hence by Lemma 2.2 for every
there exists a
with
such that
.
If for any
in
we have
, then the theorem follows from Lemma 4.5 . So we can assume that there is a
in
such that
.
But by Lemma 2.4 , we have
, which contradicts the assumption of the theorem. Now we finish the proof.
(Theorem 4.15 ).
Remark 4.16
We already proved that Theorem 1.4 follows from Theorem 1.7 . Now Theorem 1.7 follows from Theorem 1.3 , Theorem 3.10 , and Theorem 4.15 .
5 A Corollary for Upper Asymptotic Density
In this section we slightly improve the most important part of the main theorem in [Ji2] using Theorem 1.4 .
For an infinite set
the upper asymptotic density of
is defined by
In this section we assume that
and
. By Theorem A.1 it is not hard to prove that
implies
. In [Ji2] the structure of
was characterized when
and
. Next we improve this result by substituting the condition
with the condition
for some positive real number
.
Corollary 5.1
Let
be the real number in Theorem 1.4 . For every real number
with
, if
and
, then either (a) there exist
and
such that
and
, or (b) for every increasing sequence
with
, there exist two sequences
such that
for each
,
Proof: Let
be any hyperfinite integer and
be the term in the internal sequence
from (b). Without loss of generality we can assume
. Let
.
Then
and
. If
is a subset of an a.p. of length
, then
, which is absurd. So by Theorem 1.4 we conclude that
is a subset of a b.p. of difference
of length at most
. Now the proofs can be found in [Bo] (with
) that if
, then
and
, and if
, then there are
such that
,
Note that the first inequality is a trivial consequence of Theorem 1.4 and the second inequality indicates that the interval
is much shorter than
. Since the arguments above are true for every hyperfinite integer
, then the corollary follows from the transfer principle.
(Corollary 5.1 )
Remark 5.2
(1) The result in [
Ji2]
mentioned above is a special case of Corollary 5.1 with
.
(2) Corollary 5.1 is very similar to the main theorem in [
Bo]
. The main theorem in [
Bo]
allows all
instead of
in Corollary 5.1 . However, Corollary 5.1 allows, for example
(note that
), instead of
for a small
in the main theorem in [
Bo]
. The reason for the difference is that the main theorem in [
Bo]
is a corollary of Theorem A.5 while Corollary 5.1 is a corollary of Theorem 1.4 . It should be interesting to see whether one can prove Corollary 5.1 with the condition
replaced by
. In fact, this is a corollary of Conjecture 6.1 .
6 Comments and a Conjecture
The reader might notice that the proof of the case when
is much more “nonstandard” than the proof of the case when
, which is combinatorial. However, the proof of the latter is significantly simplified after the possibility of
is eliminated.
After reading all the proofs above, the reader should be able to see the crucial role that Lemma 2.2 plays. In order to violate the condition
one needs only to find a small segment
of the set
, which already violates
, as long as the rest of the
at each side of the segment is not too dense and is not a subset of an a.p. of difference
(see the condition of Lemma 2.3 ). So if
does not have expected structural properties such as
,
,
is a subset of an a.p.
of difference
, or
is a subset of a
–unbounded b.p., then the segment mentioned above is guaranteed by Lemma 2.2 . Otherwise
must have one of some desired structural properties in an interval
for some
, which gives us a high standing ground to reach our final goal. When
has these structural properties, the proof of the main theorems can be clearly divided into a few possible cases.
Lemma 2.2 is inspired by Kneser's Theorem (cf. [HR] ) and uses the fact that
is an additive semigroup. This tool is not available in the standard setting, i.e. an initial segment of a finite interval cannot be closed under usual addition. This indicates that the use of nonstandard analysis in this paper is non-trivial.
Although Theorem 1.4 is a significant advancement of the current results, it confirms only a weak version of Conjecture 1.1 . It is interesting to see whether the ideas from nonstandard analysis can play a major role in the ultimate solution of Conjecture 1.1 . Many lemmas including Lemma 2.2 in this paper may be generalized. If these generalizations are achieved, then one can generalize Theorem 1.4 by allowing
. I would like to state that as a conjecture. The conjecture stated below should be much easier to prove than proving Conjecture 1.1 . However, the solution of the following conjecture is useful for improving Corollary 5.1 and could be the last stepping stone to the ultimate solution of Conjecture 1.1 .
Conjecture 6.1
For any real number
with
there exists a
such that for every finite set
with
, if
, then
is either a subset of an a.p. of length at most
or a subset of a b.p. of length at most
.
A Appendix
The following theorem is in [Fr1] and in [Na,p.28] .
Theorem A.1 (G. A. Freiman)
Let
be a finite set of integers and
. If
, then
is a subset of an a.p. of length at most
.
The following theorem is in [Fr1, Bi]
Theorem A.2 (G. A. Freiman)
Let
be a finite set of integers and
. If
, then
is either a subset of an a.p. of length at most
or a b.p.
The following theorem is in [Fr1] .
Theorem A.3 (G. A. Freiman)
Let
be such that
. If
for
and
is not a subset of a straight line, then
is
-isomorphic to a subset of
where
.
The following theorem is in [Na,p.118] and in [LS] .
Theorem A.4 (V. Lev & P. Y. Smeliansky)
Let
and
be two finite set of non-negative integers such that
,
,
,
, and
. If
, then
. If
, then
.
Note that Theorem A.4 is trivially true when
. In this paper Theorem A.4 is used in different variations. For example, we can replace the conditions of the theorem by
,
, and
. We can also consider that both
and
are subsets of a.p. 's of difference
with the conditions
,
, and
.
The next theorem is Bilu's version of Freiman's famous theorem for the inverse problems about the addition of finite sets [Bi,Theorem1.2andTheorem1.3] . we state only this weak version in order to make the paper a little shorter.
Theorem A.5 (Y. Bilu & G. A. Freiman)
Let
,
be a finite subset of integers such that
, and
. Then
is a subset of an
–progression
such that
for some constant
and
for some constant
. The constants
are independent of
.
References
-
Y. Bilu, Structure of sets with small sumset, Astérisque 258 (1999), 77—108.
-
G. Bordes, Sum-sets of small upper density, Acta Arithmetica, to appear.
-
J. Deshouilers, B. Landreau, and A. Yudin (editors), Structure Theory of Set Addition, Astérisque No. 258 (1999), Société Mathématique de France, Paris.
-
G. A. Freiman, Foundations of a structural theory of set addition. Translated from the Russian. Translations of Mathematical Monographs, Vol 37. American Mathematical Society, Providence, R. I., 1973
-
G. A. Freiman, Structure theory of set addition. II. Results and problems. Paul Erdös and his mathematics, I (Budapest, 1999), 243–260, Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, 2002.
-
H. Halberstam and K. F. Roth, Sequences, Oxford University Press, 1966
-
Y. O. Hamidoune and A. Plagne, A generalization of Freiman's
theorem. Acta Arith. 103 (2002), no. 2, 147–156.
-
C. W. Henson, Foundations of nonstandard analysis–A gentle introduction to nonstandard extension, in Nonstandard Analysis: Theory and Applications, ed. by N. J. Cutland, C. W. Henson, and L. Arkeryd, Kluwer Academic Publishers 1997.
-
R. Jin, Nonstandard methods for upper Banach density problems, The Journal of Number Theory, 91 (2001), 20—38.
-
R. Jin, Solution to the inverse problem for upper asymptotic density, to appear.
-
V. Lev and P. Y. Smeliansky, On addition of two distinct sets of integers, Acta Arithmetica, 70 (1995), No. 1, 85–91.
-
T. Lindstrom, An invitation to nonstandard analysis, in Nonstandard Analysis and Its Application, ed. by N. Cutland, Cambridge University Press 1988.
-
M. B. Nathanson, Additive Number Theory–Inverse Problems and the Geometry of Sumsets, Springer, 1996.