Department of Mathematics College of Charleston Charleston, SC 29424 jinr@cofc.edu

Characterizing the structure of A   when the ratio | 2 A | / | A |   is bounded by 3 + ε  

Renling Jin

November 27, 2006

1 Introduction

Inverse problems study the structural properties of the sets A i   when the sum of the sets i = 1 n A i = { i = 1 k a i : a i A i }   satisfies certain conditions. When A i = A   for every i   , we write n A   for i = 1 n A i   . Note that the term n A   should not be confused with the term n * A = { a n : a A }   , which will also be used later in this paper. For a number x   we write x ± A   for the set { x } ± A   and write A ± x   for the set A ± { x }   . G. A. Freiman and many others have studied inverse problems for the addition of finite sets and have obtained many results showing that if A + B   is small relative to the size of A   and the size of B   , then A   and B   must have some arithmetic structure (cf. [Na, DLY). In this paper we consider the addition of two copies of the same finite set A   of natural numbers. Let a , d , k N   with d , k 1   .
A set of the form { a , a + d , a + 2 d , , a + ( k 1 ) d }   is called an arithmetic progression of length k   with difference d   . A set of the form I J   is called a bi-arithmetic progression of length k   with difference d   if both I   and J   are arithmetic progressions of difference d   , | I | + | J | = k   , and I + I   , I + J   , J + J   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 m , n   the term [ m , n ]   represents exclusively the interval of integers. For a set of integers A   , we write A [ m , n ]   for the set A [ m , n ]   and A ( m , n )   for the number | A [ m , n ] |   . The reader needs to be able to distinguish 2 A ( a , b )   , which is 2   times the number A ( a , b )   , from ( 2 A ) ( a , b )   , which is the number of elements in the set ( 2 A ) [ a , b ]   .
Suppose | A | = k   . It is well known that if | 2 A | = 2 k 1   , then A   must be an a.p.
Note that it is always true that | 2 A | 2 k 1   . In [Fr1Freiman obtained the interesting generalizations of these facts by showing that (1) if k > 3   and | 2 A | = 2 k 1 + b < 3 k 3   , then A   is a subset of an a.p. of length at most k + b   ; (2) if k > 6   and | 2 A | = 3 k 3   , then either A   is a subset of an a.p. of length at most 2 k 1   or A   is a b.p.
In [Fr1the structure of A   was also characterized when | A | > 10   and | 2 A | = 3 k 2   .
The proof of the 3 k 3   theorem above in [Fr1was not short while the proof of the 3 k 2   theorem was omitted there because, commented by Freiman, it was too tedious 2   . There has been no further accurate characterization, until now, of the structure of A   when, for example, | 2 A | = 3 k 1   . In fact, Freiman made the following conjecture a few years ago in [Fr2.
Conjecture 1.1 (G. A. Freiman) There exists a natural number K   such that for any finite set of natural numbers A   with | A | = k > K   and | 2 A | = 3 k 3 + b   for 0 b < 1 3 k 2   , A   is either a subset of an a.p. of length at most 2 k 1 + 2 b   or a subset of a b.p. of length at most k + b   .
Note that Conjecture  1.1 is clearly false if b = 1 3 k 2   as shown in the following easy example.
Example 1.2 Suppose k = 3 a   and c > 2 k   . Let A = [ 0 , a 1 ] [ c , c + a 1 ] [ 2 c , 2 c + a 1 ]   . Then | A | = k   and | 2 A | = 3 | A | 3 + 1 3 k 2   . But A   is neither a subset of an a.p. of length 2 k 1 + 2 ( 1 3 k 2 )   nor a subset of a b.p. of length k + ( 1 3 k 2 )   .
It is easy to prove Freiman's conjecture if one adds an extra condition that the set A   is a subset of a b.p. We prove this in Theorem  1.3 as a simple consequence of Theorem  A.3 .
Let A   and B   be two subsets of two torsion–free groups, respectively. A bijection φ : A B   is called a F 2   -isomorphism 3   if for all a 1 , a 2 , a 3 , a 4 A   , a 1 + a 2 = a 3 + a 4   if and only if φ ( a 1 ) + φ ( a 2 ) = φ ( a 3 ) + φ ( a 4 )   . A set P = P ( x 0 ; x 1 , x 2 ; b 1 , b 2 ) = { x 0 + i x 1 + j x 2 : 0 i < b 1 and 0 j < b 2 }   with b 1 b 2 > 0   is called a F 2   -progression if the map φ : [ 0 , b 1 1 ] × [ 0 , b 2 1 ] P   with φ ( i , j ) = x 0 + i x 1 + j x 2   is a F 2   -isomorphism. P   is called to have rank 2 if b 2 > 1   and rank 1 if b 2 = 1   .
Theorem 1.3 Suppose A   is a subset of a b.p. I J   such that | A | = k > 10   and both A I   and A J   are non-empty. If | 2 A | = 3 k 3 + b   for 0 b < 1 3 k 2   , then I   and J   can be chosen so that | I | + | J | k + b   .
Proof: Without loss of generality we can assume that I J   has the shortest length.
Clearly, I J   is F 2   -isomorphic to the set
M = { ( 0 , 0 ) , ( 1 , 0 ) , , ( l 1 1 , 0 ) } { ( 0 , 1 ) , ( 1 , 1 ) , , ( l 2 1 , 1 ) } (I)
in Z 2   where l 1   is the length of I   and l 2   is the length of J   . Let φ   be the F 2   -isomorphism from I J   to M   . Then | φ ( A ) | = k   and | 2 φ ( A ) | = | 2 A | = 3 | A | = 3 k 3 + b < 10 3 k 5   . By Theorem  A.3 we have that l 1 + l 2 k + b   . Hence A   is a subset of a b.p. of length at most k + b   .   (Theorem  1.3 ) It is worth to mention another interesting generalization of Freiman's 3 k 3   Theorem in [HP, where the condition | 2 A | = 3 k 3   is replaced by | A + t * A | = 3 k 3   for an integer t   . The most interesting case of this generalization is when t = 1   . However, this generalization does not concern the case when | 2 A | = 3 k 3 + b   with b > 0   . Recently, we developed some ideas with the help of nonstandard analysis in the research of the inverse problem for upper asymptotic density [Ji2and found that these ideas can be applied to the case when | 2 A | = 3 k 3 + b   with some relatively small b > 0   . The following is the main result of this paper.
Theorem 1.4 There exists a positive real number ε   and a natural number K   such that for every finite set of natural numbers A   with | A | = k   , if k > K   and | 2 A | = 3 k 3 + b   for 0 b ε k   , then A   is either a subset of an a.p. of length at most 2 k 1 + 2 b   or a subset of a b.p. of length at most k + b   .
Theorem  1.4 gives an affirmative answer to Conjecture  1.1 when 0 b ε | A |   . Note that we have a new result even when b = 2   . Note also that the upper bound 2 k 1 + 2 b   of the length of the a.p. and the upper bound k + b   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 k > 15   let A = [ 0 , k 3 ] { k + 10 , 2 k + 20 }   . Then | A | = k   and | 2 A | = 3 k 3 + 11   .
The shortest a.p. containing A   has length 2 k 1 + 2 × 11   and A   is not a subset of a b.p. of length k + 11   .
Example 1.6 For k > 14   let A = [ 0 , k 3 ] { 3 k , 3 k + 12 }   . Then | A | = k   and | 2 A | = 3 k 3 + 11   .
The shortest b.p. containing A   has length k + 11   and A   is not a subset of an a.p. of length 2 k 1 + 2 × 11   .
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 * V   . For each standard set A N   , we write * A   for the nonstandard version of A   in * V   . For example, * N   is the set of all natural numbers in * V   , and if A   is the set of all even numbers in N   , then * A   is the set of all even numbers in * N   .
If we do not specify that A , B , C ,   are sets of standard natural numbers, then they are always assumed to be internal subsets of * N   . The lower case letters are used for integers.
The integers in * N \ N   are called hyperfinite integers. From now on, the letters H   and N   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 r , s   in * V   , by r s   we mean that r s   is an infinitesimal, i.e. the absolute value of r s   is less than any standard positive real numbers; by r s   ( r s   ) we mean r < s   ( r > s   ) and r s   ; by r s   ( r s   ) we mean r < s   ( r > s   ) or r s   . Given a hyperfinite integer H   and two real numbers r , s   , by r H s   we mean s r H 0   ; by r H s   ( r H s   ) we mean r < s   ( r > s   ) and r H s   ; by r H s   ( r H s   ) we mean r H s   ( r H s   ) or r H s   . It is often said that a quantity a   is insignificant with respect to H   if a H 0   . When using   ,   ,   , etc. insignificant quantities can often be neglected. For example, instead of writing A ( 0 , H ) H α ( H + 1 )   , we can write its equivalent form A ( 0 , H ) H α H   . For another example, when a c b   , we often write A ( a , c ) H A ( a , b ) + A ( b , c )   instead of A ( a , c ) = A ( a , b ) + A ( b + 1 , c )   . We will omit the subscript H   when it is clearly given. For a real number r * R   bounded by a standard real number, let s t ( r )   , the standard part of r   , be the unique standard real number α   such that r α   . Note that   ,   ,   , H   , H   , and H   are external relations. If A [ 0 , H ]   is a hyperfinite set with a = min A   and b = max A   , then A   is said to be full (in I   ) if A   is a subset of an a.p. I   such that | A | I ( a , b )   . We say that A   is full in a b.p. I 0 I 1   if A I 0 I 1   and | A | I 0 ( l 0 , u 0 ) + I 1 ( l 1 , u 1 )   where u i = max ( A I i )   and l i = min ( A I i )   for i = 0 , 1   . Note that if A [ 0 , H ]   be a subset of an a.p. I   and | I | 0   , then A   is always full. We always assume that A I 0   and A I 1   are non-empty when we say that A   is a subset of the b.p. I 0 I 1   .
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 H   be a hyperfinite integer and A [ 0 , H ]   be an internal set. Suppose 0 = min A   , H = max A   , | A | 0   , gcd ( A ) = 1   , and | 2 A | = 3 | A | 3 + b   for 0 b 0   . Then either H + 1 2 | A | 1 + 2 b   or A   is a subset of a b.p. of length at most | A | + b   .
Proof of Theorem  1.4 from Theorem  1.7 : Suppose Theorem  1.4 is not true. Then for ε k = 1 k   and K k = k   for each k N   , there is a finite set A k [ 0 , h k ]   satisfying the following: 0 = min A k   , h k = max A k   , | A k | > k   , gcd ( A k ) = 1   , | 2 A k | = 3 | A k | 3 + b k   for 0 b k | A | k   , h k + 1 > 2 | A k | 1 + 2 b k   , and A k   is not a subset of a b.p. of length at most | A k | + b k   .
Let K   be a hyperfinite integer and let A = A K   be the term in the internal sequence A k : k * N   . Then we have the following: 0 = min A   , H = h K = max A   , | A | > K   , gcd ( A ) = 1   , | 2 A | = 3 | A | 3 + b   for some b 0   with b | A | 1 K 0   , H + 1 > 2 k 1 + 2 b   , and A   is not a subset of a b.p. of length at most | A | + b   . If in addition we have | A | H 0   , then the set A   contradicts Theorem  1.7 . Hence it suffices to prove | A | H 0   or equivalently | A | 0   .
Suppose | A | 0   . By Theorem  A.5 the set A   is a subset of a F 2   -sequence P = P ( x 0 ; x 1 , x 2 ; b 1 , b 2 )   such that | A | | P | 0   . If P   has rank 1, then P   is an a.p. Since gcd ( A ) = 1   , then [ 0 , H ] P   . This contradicts | A | 0   . Hence we can assume that P   has rank 2. Let φ : P [ 0 , b 1 1 ] × [ 0 , b 2 1 ]   be a F 2   -isomorphism and B = φ ( A )   . Then B   is not a subset of a straight line. Since B   is a F 2   -isomorphic image of A   , we have | 2 B | = | 2 A |   . Hence by Theorem  A.3 , B   is F 2   -isomorphic to a subset of M   in ( I ) such that l 1 + l 2 | B | + b   . This shows that A   is a subset of a b.p. of length at most | A | + b   , which contradicts the assumption that A   is not a subset of a b.p. of length at most | A | + b   .   (Theorem  1.4 ) The approach of eliminating the possibility of | A | 0   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 | A | < δ ( max A min A )   is added.
It is possible but much more tedious to prove | A | 0   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 A [ 0 , H ]   contains significantly less than half of the elements in [ 0 , H ]   . In the second step we deal with the case when A [ 0 , H ]   contains roughly half of the elements in [ 0 , H ]   . 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   The conclusion of Freiman's 3 k 2   Theorem in [Fr1seems missing at least one case. For example, if A = [ 0 , k 3 ] { 4 k , 4 k + 2 }   , then | 2 A | = 3 k 2   . This case of A   was not covered by the theorem.

3   F   is the initial of Freiman.

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 U   of * N   is called a cut if U + U U   . Clearly U = N   and U = * N   are cuts. A cut U * N   is external because it has no maximum element. For example, N   is external. For a hyperfinite integer H   , the set
U H = n N [ 0 , [ H / n ] ] (II)
is an external cut. We often write x > U   for x * N \ U   and write x < U   for x U   . Note that if x < U   and y > U   , then x y 0   .
Let U   be a cut. A b.p. B = I J   is called a U   –unbounded b.p. if both I U   and J U   are upper unbounded in U   . Note that a U   –unbounded b.p. always has the difference greater than 2   .
Suppose U   is a cut. Given a function f : U * R   (not necessarily internal) bounded by a standard real number, the lower U   –density of f   is defined by d ̲ U ( f ) = sup { inf { s t ( f ( n ) ) : n U \ [ 0 , m ] } : m U } .   Given a set A [ 0 , H ]   , let f A ( x ) = A ( 0 , x ) x + 1   for each x [ 0 , H ]   . The lower U   –density of A   is defined by d ̲ U ( A ) = d ̲ U ( f A ) .   For any x * N   , we define the lower ( x + U )   –density and lower ( x U )   –density of A   by d ̲ x + U ( A ) = d ̲ U ( ( A x ) * N )   and d ̲ x U ( A ) = d ̲ U ( ( x A ) * N ) .  
Remark 2.1 (1) For any A N   , d ̲ ( A ) = d ̲ N ( * A )   , where d ̲ ( A ) = liminf n A ( 0 , n 1 ) n   is the standard definition of the lower asymptotic density of A   .
(2) It is easy to check that for each a U   , d ̲ U ( A + a ) = d ̲ U ( A )   and d ̲ U ( A \ [ 0 , a ] ) = d ̲ U ( A ) .   (3) Let H   be hyperfinite and A [ 0 , H ]   . If d ̲ U ( A ) > γ   , then there exist x U   and y [ 0 , H ] \ U   such that for any x z y   , A ( 0 , z ) z + 1 > γ   . Clearly one can find a x U   such that for every z x   in U   , A ( 0 , z ) z + 1 > γ   . Now the set of all z [ x , H ]   such that A ( 0 , z ) z + 1 > γ   is internal and contains all elements in U [ x , H ]   , hence contains all elements in [ x , y ]   for some y > U   .
(4) If d ̲ U ( A ) = α   , then there is a x U   such that for every y U   with y > x   , one has A ( 0 , y ) y + 1 α   . This can be proven by first choosing a x n U   for each n N   such that for all z x n   in U   , A ( 0 , z ) z + 1 > α 1 n   and then choosing a x U   such that x x n   for every n N   .
The element x   exists because, by countable saturation, the cofinality of U   is uncountable, i.e. any countable increasing sequence in U   is upper bounded in U   .
(5) If d ̲ U ( A ) > 1 2   , then there exists an a U   such that A ( 0 , a 1 ) = 1 2 a   and A ( a , c ) > 1 2 ( a c + 1 )   for every c U   with c a   . As a by-product we have a , a + 1 A   and A ( a , a + 3 ) 3   . The existence of a   is guaranteed by d ̲ U ( A ) > 1 2   .
From now on, the only cut we need is U H   defined by ( II ) for a given H   . Hence when H   is clearly given, the letter U   always represents the cut U H   . Note that with H   fixed we have that x < U   iff x 0   or equivalently x > U   iff x 0   .
The first lemma of this section bellow is [Ji2,Lemma2.12.
Lemma 2.2 Let H   be hyperfinite, U = U H   , and A * N   be such that 0 < d ̲ U ( A ) = α < 2 3   . If A U   is neither a subset of an a.p. of difference greater than 1   nor a subset of a U   –unbounded b.p., then there is a γ > 0   such that for every N > U   , there is a K A \ U   with K < N   such that
( 2 A ) ( 0 , 2 K ) 2 K + 1 3 2 A ( 0 , K ) K + 1 + γ . (III)
The following is [Ji2,Lemma2.4.
Lemma 2.3 Let A [ 0 , H ]   . Suppose 0 , H A   . If 0 x 1 x 2 H   satisfy the following (1) ( 2 A ) ( 2 x 1 , 2 x 2 ) 3 A ( x 1 , x 2 )   , (2) if 0 x 1   , then gcd ( A [ 0 , x ] ) = 1   and A ( 0 , x ) 1 2 ( x + 1 )   for some x x 1   in A   , (3) if x 2 H   , then gcd ( A [ x , H ] x ) = 1   and A ( x , H ) 1 2 ( H x + 1 )   for some x x 2   in A   , then | 2 A | 3 | A |   .
Lemma 2.4 Let A [ 0 , H ]   . Suppose 0 , H A   , | A | 1 2   , d ̲ U ( A ) = 1 2   , there is an a 0   in A   such that gcd ( A [ a , H ] a ) = 1   , and for every N 0   there is a K A   with 0 K N   such that ( III ) is true. Then | 2 A | 3 | A |   .
Proof: Let 0 < ε < 1   be such that for any N 0   there is a K A   with 0 K N   such that ( 2 A ) ( 0 , 2 K ) 2 K + 1 > ( 3 + ε ) A ( 0 , K ) 2 ( K + 1 ) .   Let δ > 0   be such that δ < ε 6   and let y A   be such that y 0   , y a   , A ( 0 , y ) ( 1 2 δ ) ( y + 1 )   , and ( 2 A ) ( 0 , 2 y ) > ( 3 + ε ) A ( 0 , y )   .
If A ( y , H ) 1 2 ( H y )   , then the lemma follows from Lemma  2.3 and Theorem  A.1 .
So we can assume A ( y , H ) 1 2 ( H y )   . By Theorem  A.4 we have | A [ y , H ] + A [ y , H ] | H y + A ( y , H )   . Hence
| 2 A | ( 2 A ) ( 0 , 2 y ) + | A [ y , H ] + A [ y , H ] |
( 3 + ε ) A ( 0 , y ) + H y + A ( y , H )
3 A ( 0 , y ) + ε A ( 0 , y ) + 2 | A | y + A ( y , H )
3 | A | + ε A ( 0 , y ) + 2 A ( 0 , y ) y
3 | A | + ( ε + 2 ) ( 1 2 δ ) y y
3 | A | + ( ε 2 ε δ 2 δ ) y
3 | A | + ( ε 2 ε 6 2 ε 6 ) y
= 3 | A | .
  (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 | 2 A | 3 | A |   in various situations. For example, if | A | 1 2 H   and A U   does not have “nice arithmetic structures”, then one can find an arbitrarily small y 0   in A   such that ( 2 A ) ( 0 , 2 y ) 3 A ( 0 , y )   . By Lemma  2.3 or Lemma  2.4 one needs only to make sure that A [ x , H ]   is not a subset of an a.p. of difference > 1   for some x 0   in order to conclude that | 2 A | 3 | A |   .
The next lemma is trivial and will be frequently referred as the pigeonhole principle.
Lemma 2.5 Let d 1   . Suppose a , b [ 0 , d 1 ]   , A a + ( d * * N )   , B b + ( d * * N )   , x a + ( d * * N )   , y b + ( d * * N )   , and t ( d * * N )   . If A ( x , x + t ) + A ( y t , y ) > t d + 1   , then x + y ( 2 A )   .
For convenience we give a name for each of the following two sets with special structural properties. Let a b   in [ 0 , H ]   . A set F [ a , b ]   is called a forward triangle from a   to b   if | F | 1 2 ( b a )   and for every x   with a x b   , F ( a , x ) 1 2 ( x a )   . A set B [ a , b ]   is called a backward triangle from a   to b   if the set ( b + a ) B   is a forward triangle from a   to b   . 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 F   is a forward triangle from a   to b   , then there is a z a   such that z , z + 1 A   and A ( z , z + 3 ) 3   . The number z   can be obtained by letting z 1   be the greatest number in a + U   such that A ( a , z 1 ) 1 2 ( z a )   .
Lemma 2.6 Let A [ 0 , H ]   be such that 0 , H A   and 0 | A | 1 2 H   . Let 0 < α 1 2   and 0 x H   .
(1) If A ( 0 , x ) α x   and | A | α H   , then there exists a y x   such that A ( 0 , y ) α y   and either y H   or for any z y   in [ 0 , H ]   , A ( 0 , z ) α z   .
(2) If A ( 0 , x ) 1 2 x   , then there are 0 y x y H   such that A ( 0 , y ) 1 2 y   and A [ y , y ]   is a forward triangle.
(3) If d ̲ U ( A ) > 1 2   , then there is a y 0   such that A [ 0 , y ]   is a forward triangle.
(4) If d ̲ U ( A ) < 1 2   and | A | 1 2 H   , then there are 0 y y H   such that A ( y , H ) 1 2 ( H y )   and A [ y , y ]   is a backward triangle.
Proof: (1) Let β = sup { s t ( z H + 1 ) : z [ 0 , H ] and A ( 0 , z ) α z } ,   where s t   is the standard part map. By the completeness of the standard real line, β   is well defined. Let y [ 0 , H ]   be such that y H + 1 β   . Clearly y x   .
It is easy to see that if y H   , then A ( 0 , z ) α z   for any y z H   by the supremality of β   . It is also easy to see that both A ( 0 , y ) α y   and A ( 0 , y ) α y   are impossible by the fact that β   is the least upper bound.
(2) By the same idea as in (1) we can find y x   such that A ( 0 , y ) 1 2 y   and A ( 0 , z ) 1 2 z   for any x z y   . Let 0 y x   be such that A ( 0 , y ) 1 2 y   and A ( 0 , z ) 1 2 z   for any y z x   . It is easy to see that A ( y , y )   is a forward triangle.
(3) By the definition of d ̲ U   and (1) above there exists y 0   such that A ( 0 , y ) 1 2 y   and A ( 0 , z ) 1 2 z   for every 0 z y   . Clearly A [ 0 , y ]   is a forward triangle.
(4) Choose a x 0   such that A ( 0 , x ) 1 2 x   . Hence A ( x , H ) 1 2 ( H x )   . Now the conclusion follows from (2) above with the order of [ 0 , H ]   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 X * N   be a proper external initial segment of non-negative integers and let A * N   be an internal set. (a) If A X   is upper unbounded in X   , then A \ X   . (b) If A \ X   is lower unbounded in * N \ X   , then A X   .
Proof: If (a) of the lemma is not true, then X = { v * N : ( x A ) ( v x ) } ,   which means that X   is internal. The proof of (b) is similar.   (Lemma  2.7 )
Lemma 2.8 Suppose a b   in [ 0 , H ]   .
(1) If T   is a forward triangle from a   to b   , then [ a , b ] ( 2 T )   for some a 2 a   and b a + b   .
(2) If B   is a backward triangle from a   to b   , then [ a , b ] ( 2 B )   for some a a + b   and b 2 b   .
Proof: Given each x   with a x b   , since T ( a , x ) 1 2 ( x a )   , then by the pigeonhole principle, T [ a , x ] ( x + a T [ a , x ] )   . This implies x + a ( 2 T )   . Since 2 T   is an internal set, then by Lemma  2.7 there are a 2 a   and b a + b   such that [ a , b ] ( 2 T )   . The proof of the second part follows from the symmetry.   (Lemma  2.8 ) The following is [Ji2,Lemma2.5
Lemma 2.9 Let A [ 0 , H ]   for a hyperfinite integer H   . If A [ 0 , a ]   is a forward triangle from 0   to a   and ( 2 A ) ( a , c ) 0   for some 0 a c   , then there is a b a 2   such that A [ 0 , a ] [ 0 , b ]   .
The following is a technical lemma, which will be used in the next two sections.
Lemma 2.10 Suppose 0 a H   , A ( 0 , a ) 0   , gcd ( A [ 0 , a ] ) = 1   , A [ 0 , a ]   is a subset of a b.p. I J   of difference d 3   , A [ 0 , a + 1 ]   is not a subset of a b.p. of difference d   , | 2 A | 3 | A |   , and | A [ a + 1 , H ] + A [ a + 1 , H ] | 3 A ( a + 1 , H )   . Then A [ 0 , a ]   is full in I J   and max ( A I ) max ( A J ) a   .
Proof: Let A 0 = A [ 0 , a ] I   , A 1 = A [ 0 , a ] J   , l i = min A i   , and u i = max A i   for i = 0 , 1   .
Since
| 2 A | | 2 A 0 | + | 2 A 1 | + | A 0 + A 1 | + | A [ a + 1 , H ] + A [ a + 1 , H ] |
3 | A 0 | + 3 | A 1 | + 3 A ( a + 1 , H ) 3 | A | ,
then | 2 A | 3 | A |   implies that | 2 A i | 2 | A i |   for i = 0 , 1   . Hence by Theorem  A.1 we have that A 0   is full in I   and A 1   is full in J   .
Without loss of generality we assume u 0 < u 1   . If u 1 a   , then | 2 A | 3 A ( 0 , a ) + 3 A ( a + 1 , H ) + | a + 1 + A [ 2 u 1 a , u 1 ] | 3 | A | .   If u 1 a   and u 0 a   , then | 2 A | 3 A ( 0 , a ) + 3 A ( a + 1 , H ) + | a + 1 + A 1 [ 2 u 0 a , a ] | 3 | A |   because ( a + 1 + A 1 [ 2 u 0 a , a ] ) ( A [ 0 , a ] + A [ 0 , a ] ) =   . Hence we have u i a   for i = 0 , 1   .
  (Lemma  2.10 )

3 First Step: When | A | H   is significantly less than 1 2   .

In this section we always assume that H   is a hyperfinite integer, A [ 0 , H ]   , 0 , H A   , and gcd ( A ) = 1   . We will prove Theorem  1.7 under one extra condition
| A | 1 2 H . (IV)
We will prove that if | 2 A | 3 | A |   and ( IV ) is true, then A   must be a subset of a b.p., which, by Theorem  1.3 , implies Theorem  1.7 . In this section the condition | 2 A | = 3 | A | 3 + b   is not explicitly used. Hence the letter b   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 A   are assumed. After all needed versions are proven we combine them into the main theorem.
Lemma 3.1 If there are 0 a < b H   in A   such that A = T P   where T = A [ 0 , a ]   is a forward triangle from 0   to a   and P = A [ b , H ]   is a subset of an a.p. of difference d > 1   with | P | 0   , then either A   is a subset of a b.p. of difference 3   or | 2 A | 3 | A |   .
Proof: Let P   be a subset of an a.p. I   of difference d > 1   such that b P   is the least element of I   , and H P   is the largest element of I   . Suppose T   is not a subset of a b.p. of difference 3   . Since T   is a forward triangle, there exist z , z + 1 A U   such that for every x   with z x a   , T ( z , x ) x z + 1 > 1 2 .   Without loss of generality (except in Case  3.1 .1.2) we can assume z = 0   . Under this assumption we have 0 , 1 A   and A ( 0 , 3 ) 3   .
Claim  3.1 .1 If P   is not full in I   , then ( T + P ) ( b , H ) 2 | P |   .
Proof of Claim  3.1 .1: Since P   is not full, then | I \ P | 0   . Let   be the collection of all intervals [ x , y ] [ b , H ]   such that y x 2 d 2   , [ x , y ] P =   , and x 1 , y + 1 P   .
Then I \ P = [ x , y ] ( [ x 1 + d , y + 1 d ] I ) .   Hence
| I \ P | = [ x , y ] 1 d ( y x + 2 d )
[ x , y ] 1 d ( y x ) [ x , y ] 1 2 ( y x ) [ x , y ] ( y x 1 ) .
If there is an interval [ x , y ]   such that y x a 2   , then
( P + T ) ( b , H )
| P | + | 1 + P | + | ( x 1 + T ) ( x + 1 , y ) |
2 | P | + T ( 2 , y x + 1 )
2 | P | + min { | T | 2 , 1 2 ( y x + 2 ) 2 }
2 | P | + 1 4 a 2 | P | .
So we can assume y x < a 2   for every [ x , y ]   . Since for each interval [ x , y ]   , we have
( P + T ) ( x + 1 , y ) | x 1 + T [ 2 , y x + 1 ] |
= T ( 2 , y x + 1 ) > 1 2 ( y x + 2 ) 2
= 1 2 ( y x 1 ) 1 2 .
Hence ( P + T ) ( x + 1 , y ) 1 2 ( y x 1 )   because the left-side is an integer. So
( P + T ) ( b , H )
| P | + | 1 + P | + [ x , y ] ( P + T ) ( x + 1 , y )
| P | + | 1 + P | + [ x , y ] 1 2 ( y x 1 )
2 | P | + 1 2 | I \ P | 2 | P | .
  (Claim  3.1 .1) By the claim above we can assume that P   is full in I   because otherwise | 2 A | a + ( P + T ) ( b , H ) + | H + A | 2 | T | + 2 | P | + | A | = 3 | A | .   Next we divide the proof of the lemma into three cases with d = 2   , d = 3   , and d 4   .
Case  3.1 .1 d = 2   .
Let c H   in P   be such that H c < a 2   . Then
| 2 A | a + | { 0 , 1 } + P | + ( H + T ) ( H , c + a )
+ ( c + P ) ( c + b , H + b ) + ( H + P ) ( H + b , 2 H )
2 | T | + 2 | P | + T ( 0 , c + a H ) + 1 2 ( H c ) + | P |
3 | T | + 3 | P | = 3 | A |
because T ( c + a H + 1 , a ) 1 2 ( H c )   .   (Case  3.1 .1) Case  3.1 .2 d = 3   . Let A   be the original set with z , z + 1 A U   . If A   is a subset of a b.p. of difference 3   , then the lemma is trivially true. Suppose A   is not a subset of a b.p.
of difference 3   . Let c = min { x A : x z + 2 ( mod 3 ) }   . Note that either c T   or c = b   .
Suppose c 0   . Let b x H   be such that x A   and H x < c   . Note that A [ 0 , c 1 ] ( z + ( 3 * * N ) ) ( z + 1 + ( 3 * * N ) )   and A [ x , H ] + c b + z + 2 + ( 3 * * N )   . Hence ( A [ x , H ] + c ) ( H + A [ 0 , c 1 ] ) =   . So we have
| 2 A | a + 2 | P | + | H + A | + | c + A [ x , H 1 ] |
2 | T | + 2 | P | + | A | + A ( x , H ) 3 | A | .
Suppose c 0   . Then | 2 A | a + | { z , z + 1 , c } + P | + | H + A | 3 | A | + | P | 3 | A | .     (Case  3.1 .2) Case  3.1 .3 d 4   .
Since T ( 0 , 3 ) 3   , then | 2 A | a + | T [ 0 , 3 ] + P | + | H + A | 3 | A | + | P | 3 | A | .   This ends the proof of Lemma  3.1 .   (Lemma  3.1 )
Lemma 3.2 Suppose there are 0 a < b H   such that A = F B   , where F   is a forward triangle from 0   to a   and B   is a backward triangle from b   to H   . If | 2 A | 3 | A |   , then a ¯ = max F a 2   and b ¯ = min B b + H 2   . Hence F   is full in [ 0 , a ¯ ]   and B   is full in [ b ¯ , H ]   . So A   is a full subset of the b.p. [ 0 , a ¯ ] [ b ¯ , H ]   of difference 1   .
Proof: Suppose b ¯ = min B b   . Let 0 x min { a , H b 2 }   . Then by Lemma  2.8 
| 2 A | a + | b ¯ + F [ 0 , x ] | + B ( b ¯ + x , H )
+ | H + F | + | [ H + b , 2 H ] |
2 | F | + F ( 0 , x ) + B ( b ¯ + x , H ) + | F | + 2 | B |
3 | F | + 1 2 ( x + 1 ) + B ( b ¯ + x , H ) + 2 | B |
3 | F | + 2 | B | + B ( b ¯ , H ) 3 | A | .
Hence we can assume that b ¯ b   . But this implies
| 2 A | a + ( 2 A ) ( a , b ¯ ) + A ( b ¯ , H ) + | H + F | + | [ H + b , 2 H ] |
2 | F | + ( 2 A ) ( a , b ¯ ) + | B | + | F | + 2 | B | 3 | A | + ( 2 A ) ( a , b ¯ ) .
Hence | 2 A | 3 | A |   implies ( 2 A ) ( a , b ¯ ) 0   . By Theorem  2.9 , a ¯ a 2   . By a symmetric argument, we can also show that b ¯ b + H 2   .   (Lemma  3.2 )
Lemma 3.3 Suppose there are 0 a < b H   such that A = F C   , where F [ 0 , a ]   is a forward triangle from 0   to a   and C [ b , H ]   with b C   , | C | 1 2 ( H b + 1 )   , and gcd ( C b ) = 1   .
Then | 2 A | 3 | A |   .
Proof: First we assume that there is an x C   such that 0 x b < a 2   . Then
| 2 A | a + | b + F [ 0 , x b ] |
+ | x + F [ 0 , a + b x ] | + | C [ b , H ] + C [ b , H ] |
2 | F | + F ( 0 , x b ) + F ( 0 , a + b x ) + 3 | C |
2 | F | + 3 | C | + F ( a + b x , a ) + F ( 0 , a + b x )
3 | F | + 3 | C | = 3 | A | .
If the assumption above is not true, let x = min { z C : z b + a 2 }   and y = max { z C : z < b + a 2 }   . Then y b   , ( 2 C ) ( 2 b , b + x ) 0   , and ( 2 C ) ( 2 b , 2 H ) ( 2 C ) ( b + x , 2 H )   . Hence
| 2 A | a + | b + F [ 0 , x b ] | + | x + F | + ( 2 C ) ( b + x , 2 H )
3 | F | + F ( 0 , x b ) + 3 | C | 3 | A | + F ( 0 , x b ) 3 | A | .
This ends the proof.   (Lemma  3.3 )
Lemma 3.4 Suppose there are 0 a < b c H   such that A = F B C   , where F   is a forward triangle from 0   to a   , B   is a backward triangle from b   to c   , and C [ c + 1 , H ]   with | C | 1 2 ( H c )   . Then | 2 A | 3 | A |   .
Proof: Without loss of generality we can assume c , c 1 B   . By Lemma  2.3 we have that | A [ 0 , c ] + A [ 0 , c ] | 3 A ( 0 , c )   implies | 2 A | 3 | A |   . So we can now assume | A [ 0 , c ] + A [ 0 , c ] | 3 A ( 0 , c )   . Let a ¯ = max F   and b ¯ = min B   . By Lemma  3.2 , we have a ¯ a 2   , b ¯ b + c 2   , F   is full in [ 0 , a ¯ ]   , and B   is full in [ b ¯ , c ]   .
Case  3.4 .1 There is a x C   with x c   such that C ( c , x ) 0   .
We have
| 2 A | 3 | F | + 3 | B | + | x + B [ 2 c x , c ] |
+ | ( { c 1 , c } C [ x , H ] ) + ( { c 1 , c } C [ x , H ] ) |
3 | F | + 3 | B | + B ( 2 c x , c ) + 3 | { c 1 , c } C [ x , H ] ) |
3 | F | + 3 | B | + 3 | C | + B ( 2 c x , c ) 3 | A | .
  (Case  3.4 .1) Case  3.4 .2 For every x C   , if x c   , then C ( c , x ) 0   .
The assumption implies that for every y c   , there is a x C   with c x y   . Let x C   be such that 0 x c < a ¯   . Then
| 2 A | a + B ( b , c ) + | c + F [ 0 , x c ] | + | x + F [ 0 , a ¯ ] |
+ | [ c + b , 2 c ] | + | ( { c 1 , c } C ) + ( { c 1 , c } C ) |
2 | F | + | B | + F ( 0 , x c ) + | F | + 2 | B | + 3 | C | 3 | A | .
This ends the proof.   (Lemma  3.4 )
Lemma 3.5 Suppose there is an a   with 0 a H   such that F = A [ 0 , a ]   is a forward triangle from 0   to a   and A ( a , H ) 1 2 ( H a )   . If | 2 A | 3 | A |   , then A   is a full subset of a b.p. of difference 3   or a full subset of a b.p. of difference 1   .
Proof: Note that if A   is a subset of a b.p. then A   must be a full subset of that b.p. when | 2 A | 3 | A |   . Let b = min A [ a + 1 , H ]   . If b H   , then | 2 A | a + ( 2 A ) ( a + 1 , H ) + | H + F | 3 | A | + ( 2 A ) ( a + 1 , H ) .   Hence ( 2 A ) ( a + 1 , H ) 0   . By Lemma  2.9 , a ¯ = max F 1 2 ( a + 1 )   . This shows 2 a ¯ b   and a ¯ + H 2 b   . Hence [ 0 , a ¯ ] [ b , H ]   is the desired b.p. of difference 1   . So we can assume b H   .
If A ( b , H ) 0   , then | 2 A | a + | b + A [ 0 , H b ] | + | H + A [ 0 , a ] | 3 | A | + A ( 0 , H b ) 3 | A | .   Hence we can assume A ( b , H ) 0   .
Suppose A   is not a full subset of a b.p. of difference 3   . By Lemma  3.1 we can assume gcd ( A [ b , H ] b ) = 1   . If A ( b , H ) 1 2 ( H b )   , then the lemma follows from Lemma  3.3 . So now we can assume that A ( b , H ) 1 2 ( H b )   .
By (2) of Lemma  2.6 there are a < c b c H   such that A [ c , c ]   is a backward triangle and A ( c , H ) 1 2 ( H c )   . If c H   , then by Lemma  3.4 we have | 2 A | 3 | A |   .
Hence we can assume c H   . But now A   becomes the union of a forward triangle A [ 0 , a ]   and a backward triangle A [ c , H ]   . Now the lemma follows from Lemma  3.2 .   (Lemma  3.5 )
Lemma 3.6 Suppose there are 0 a a H   such that A ( 0 , a ) 1 2 a   , A ( a , H ) 1 2 ( H a )   , A [ a , a ]   is a forward triangle from a   to a   , and A [ a , H ]   is not a subset of a b.p. of difference 3   . Then | 2 A | 3 | A |   .
Proof: By Lemma  2.3 we can assume | A [ a , H ] + A [ a , H ] | 3 A ( a , H )   . By Lemma  3.5 we can assume that A [ a , H ]   is full in a b.p. [ a , c ] [ c , H ]   for some c < c   in [ a , H ]   . If c H   , then the lemma follows from Lemma  3.4 . So we can assume c H   . Note that c a + a 2   .
Hence we have 2 c a + H   . If there is a x a   in A   with x 2 c H   such that A ( x , a ) 0   , then
| 2 A | ( 2 A ) ( 0 , 2 a ) + ( 2 A ) ( 2 a , 2 c )
+ ( 2 A ) ( H + x , H + a ) + | H + A [ a , c ] |
3 A ( 0 , a ) + 3 A ( a , c ) + A ( x , a ) 3 | A | .
Otherwise choose x a   in A   such that A ( x , a ) 0   . Without loss of generality let a , a + 1 A   . Then ( 2 A ) ( 0 , x + a ) | ( A [ 0 , x ] { a , a + 1 } ) + ( A [ 0 , x ] { a , a + 1 } ) | 3 A ( 0 , x ) 3 A ( 0 , a ) .   So we have
| 2 A | ( 2 A ) ( 0 , x + a ) + | x + A [ a , 2 a x ] |
+ ( 2 A ) ( 2 a , 2 c ) + | H + A [ a , c ] |
3 A ( 0 , a ) + 3 A ( a , c ) + A ( a , 2 a x ) 3 | A | .
  (Lemma  3.6 )
Lemma 3.7 Suppose there are 0 a a H   such that A ( 0 , a ) 1 2 a   , A ( a , H ) 1 2 ( H a )   , A [ a , a ]   is a forward triangle from a   to a   , and A [ a , H ]   is not a subset of an a.p. of difference 3   .
Then | 2 A | 3 | A |   .
proof: By Lemma  3.6 it suffices to show that A [ a , H ]   is not a subset of a b.p. of difference 3   . If A [ a , H ]   is a subset of a b.p. of difference 3   , then | 2 A | 3 | A |   implies that A [ a , H ]   is a full subset of the b.p. This implies that A [ a , a ]   is a subset of the union of an a.p. of difference 3   of length 1 3 ( a a )   and an a.p. of difference 3   of length 1 6 ( a a )   -both have the left-end points a   , and A [ a , H ]   is a full subset of an a.p. of difference 3   , 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 | A | 1 2 H   and A   is neither a subset of an a.p. of difference > 1   nor a subset of a b.p. Suppose that there is a x 0   such that A ( 0 , x ) 0   and A [ 0 , x ]   is a subset of an a.p. of difference > 1   . Then | 2 A | 3 | A |   .
Proof: Let a = min { y A : gcd ( A [ 0 , y ] ) = 1 }   and c = max A [ 0 , a 1 ]   . Let d = gcd ( A [ 0 , c ] )   . Note that d > 1   is a standard natural number because A ( 0 , x ) 0   .
First, we can assume that a H   by the following reason: Suppose a H   . If there is a b A   such that b 0 ( mod d )   and b a ( mod d )   , then | 2 A | | A [ 0 , c ] + A [ 0 , c ] | + | a + A [ 0 , c ] | + | b + A [ 0 , c ] | 4 | A | .   If for any b A   , b 0 ( mod d )   or b a ( mod d )   , then A   is a subset of a b.p. unless d = 2   .
Assume d = 2   . Hence A [ 0 , c ]   is a set of even numbers and a   is odd. If A [ a , H ]   is a set of odd numbers, then A = A [ 0 , c ] A [ a , H ]   is a subset of a b.p. So we can assume that there is an even number b A   with b > a   . Clearly b H   . Let A e   be the set of all even number in A   . Then | 2 A | | 2 A e | + | a + A e | 3 | A e | 3 | A | .   Hence if | 2 A | 3 | A |   , then | 2 A e | 2 | A e |   . By Theorem  A.1 and the fact that b H   the set A e   is full in the set of all even numbers in [ 0 , H ]   , which contradicts ( IV ).
Second, we can assume that A ( a , H ) 0   by the following reason: Suppose A ( a , H ) 0   .
If | A [ 0 , c ] + A [ 0 , c ] | 2 A ( 0 , c )   , then | 2 A | | A [ 0 , c ] + A [ 0 , c ] | + | a + A [ 0 , c ] | 3 | A | .   So we can assume | A [ 0 , c ] + A [ 0 , c ] | 2 A ( 0 , c )   . By Theorem  A.1  A [ 0 , c ]   is full. This implies A ( a + c H , c ) 0   . Hence we have
| 2 A | | A [ 0 , c ] + A [ 0 , c ] |
+ | a + A [ 0 , c ] | + | H + A [ a + c H , c ] |
3 A ( 0 , c ) + A ( a + c H , c )
3 | A | + A ( a + c H , c ) 3 | A | .
Now we are ready to prove the lemma. The proof is divided into five cases.
Case  3.8 .1 d = 2   and A ( a , H ) 1 2 ( H a )   .
Clearly a   is odd. Since A   is not a subset of a b.p., then gcd ( A [ a , H ] a ) = d   is not an even number.
Suppose d > 2   . Let c = max { x A : gcd ( A [ x , H ] x ) = 1 }   . Then c c   and A [ c + 1 , H ] ( H ( d * * N ) )   for some d > 1   and d | d   . By a symmetric argument of showing A ( a , H ) 0   above, we can assume A ( 0 , c ) 0   . With a little more effort we can show that ( A [ a , H ] + A [ a , H ] ) ( c + A [ a + 1 , H ] ) = ,   ( A [ 0 , c ] + A [ 0 , c ] ) ( c + A [ a + 1 , H ] ) = , and   ( a + A [ 0 , c ] ) ( c + A [ a + 1 , H ] ) = .   The second equality above is due to the fact that if x 1 , x 2 A [ 0 , c ]   and a A [ a + 1 , H ]   having x 1 + x 2 = c + a c + a + 1   , then x 1 , x 2 > c   , which implies x 1 , x 2 ( H ( d * * N ) )   .
This implies c = x 1 + x 2 a ( H ( d * * N ) )   , which contradicts the choice of c   . The reason for the third equality above is similar. Hence
| 2 A | | A [ 0 , c ] + A [ 0 , c ] | + | a + A [ 0 , c ] |
+ | A [ a , H ] + A [ a , H ] | + | c + A [ a + 1 , H ] |
3 A ( 0 , c ) + 3 A ( a , H ) 3 | A | .
If | 2 A | 3 | A |   , then | A [ 0 , c ] + A [ 0 , c ] | 2 A ( 0 , c )   and | A [ a , H ] + A [ a , H ] | 2 A ( a , H )   . Hence A [ 0 , c ]   is full in the set of all even numbers in [ 0 , c ]   and A [ a , H ]   is full in ( a + ( d * * N ) ) [ a , H ]   .
Without loss of generality, we can assume c , c 2 , c 4 A   and c = c   . Note that c + A [ a , H ]   , c 2 + A [ a , H ]   , and c 4 + A [ a , H ]   are pairwise disjoint because d   is odd and d > 2   . Hence we have
| 2 A | | A [ 0 , c ] + A [ 0 , c ] | + | a + A [ 0 , c ] |
+ | { c , c 2 , c 4 } + A [ a , H ] | + | H + A [ a , H ] |
3 A ( 0 , c ) + 4 A ( a , H ) 3 | A | .
So | 2 A | 3 | A |   must be true. This ends the proof of the case for d > 2   .
Now assume that gcd ( A [ a , H ] a ) = d = 1   . This implies | A [ a , H ] + A [ a , H ] | 3 A ( a , H )   .
Hence | 2 A | ( 2 A ) ( 0 , 2 c ) + | a + A [ 0 , c ] | + ( 2 A ) ( 2 a , 2 H ) 3 | A | .   We now derive a contradiction by assuming | 2 A | 3 | A |   . By the inequality above we have that A [ 0 , c ]   is full in the set of all even numbers in [ 0 , c ]   . Suppose c a   . If there is a x a   in A   such that x a < a c   . Then we have
| 2 A | 2 A ( 0 , c ) + | a + A [ 0 , c ] |
+ | x + A [ a + c x , c ] | + | A [ a , H ] + A [ a , H ] |
3 A ( 0 , c ) + 3 A ( a , H ) + A ( a + c x , c ) 3 | A | ,
which contradicts | 2 A | 3 | A |   . Otherwise we can find a x a   in A   such that A ( a , x ) 0   .
Let F A [ a , H ]   be finite such that a F   and gcd ( ( F A [ x , H ] ) a ) = 1   . Then ( 2 A ) ( x + a , 2 H ) | ( F A [ x , H ] ) + ( F A [ x , H ] ) | 3 A ( x , H ) 3 A ( a , H ) .   Hence we have | 2 A | 3 A ( 0 , c ) + 3 A ( a , H ) + | x + A [ 2 c x , c ] | 3 | A | .   So we can assume c a   . Recall that we have A ( 0 , c ) 0   , A ( a , H ) 0   , gcd ( A [ 0 , c ] ) = 2   , A [ 0 , c ]   is full, gcd ( A [ a , H ] a ) = 1   , and A ( a , H ) 1 2 ( H a )   . Note that since A ( 0 , c ) 1 2 ( c + 1 )   , then | A | 1 2 H   implies A ( a , H ) 1 2 ( H a )   . Since A [ 0 , c ]   is full, we can, without loss of generality, assume that c , c 2 , c 4 A   .
Subcase  3.8 .1.1 d ̲ a + U ( A ) = 0   .
Choose a x A   with x a   such that A ( a , x ) < 1 8 ( x a + 1 )   . Let F A [ a , H ]   be finite such that a F   and gcd ( F A [ x , H ] ) = 1   . Then
| 2 A | | A [ 0 , c ] + A [ 0 , c ] | + | a + A [ 0 , c ] | + | x + A [ a + c x , c ] |
+ | ( F A [ x , H ] ) + ( F A [ x , H ] ) |
3 A ( 0 , c ) + 1 2 ( x a + 1 ) + 3 A ( x , H )
3 | A | + 1 2 ( x a + 1 ) 3 A ( a , x ) 3 | A | ,
which is again a contradiction.   (Subcase  3.8 .1.1) Subcase  3.8 .1.2 d ̲ a + U ( A ) > 1 2   .
By (3) of Lemma  2.6 there exists a b a   such that A [ a , b ]   is a forward triangle from a   to b   . Since A ( a , H ) 1 2 ( H a )   , then A ( b , H ) 1 2 ( H b )   and b H   . If | 2 A | 3 | A |   , then | A [ c 4 , H ] + A [ c 4 , H ] | 3 A ( c 4 , H )   . Note that A [ c 4 , H ]   is not a subset of a b.p.
of difference 3   because c , c 2 , c 4 A   . Hence by Lemma  3.5 , A [ c 4 , H ]   is a full subset of a b.p. [ c 4 , a ] [ b , H ]   for some a , b A   . If b H   , then by the fact that 2 a a + H   we have | 2 A | 3 A ( 0 , c ) + 2 a 2 a + | H + A [ 2 a H , H ] | 3 | A | + A ( 2 a H , a ) 3 | A | .   If b H   , then the lemma follows from Lemma  3.4 .   (Subcase  3.8 .1.2) Subcase  3.8 .1.3 0 < d ̲ a + U ( A ) 1 2   .
Suppose for any x a   in A   we have gcd ( A [ x , H ] x ) > 1   . Choose a x a   in A   such that gcd ( A [ x , H ] x ) = d > 1   . Since gcd ( A [ a , H ] a ) = 1   , then | A [ a , H ] + A [ a , H ] | 3 A ( a , H )   implies that A [ x , H ]   is full.
If d = 2   , then | A | 1 2 H   , which contradicts the condition ( IV ).
Suppose d = 4   . Let c = c   and c = c 2   when x   is odd, or let c { c , c 2 }   such that c + x 2 x + 2 ( mod d )   and c = a   when x   is even. Then c + A [ x , H ]   , c + A [ x , H ]   , and A [ x , H ] + A [ x , H ]   are pairwise disjoint. Hence
| 2 A | | A [ 0 , a ] + A [ 0 , a ] | + | c + A [ x , H ] |
+ | c + A [ x , H ] | + | A [ x , H ] + A [ x , H ] |
3 | A | + A ( x , H ) 3 | A | .
Suppose d = 3   or d > 4   . Then there are c , c   in { c , c 2 , c 4 }   such that c + A [ x , H ]   , c + A [ x , H ]   , and A [ x , H ] + A [ x , H ]   are pairwise disjoint. Hence | 2 A | 3 | A |   by the same reason above.
Therefore, we can now assume that there is a x a   in A   such that gcd ( A [ x , H ] x ) = 1   .
Since gcd ( ( A [ c 4 , H ] c 4 ) U ) = 1   and ( A [ c 4 , H ] c 4 ) U   is not a subset of a U   –unbounded b.p. of difference d > 1   because a , c , c 2 , c 4 A   , then by Lemma  2.2 there exists a y a   in A   with c y x   and A ( y , H ) 1 2 ( H y + 1 )   such that ( 2 A ) ( 2 ( c 4 ) , 2 y ) 3 A ( c 4 , y )   . Hence by Lemma  2.3  | A [ c 4 , H ] + A [ c 4 , H ] | 3 A ( c 4 , H )   , which implies | 2 A | 3 | A |   . This ends the proof.   (Case  3.8 .1) Case  3.8 .2 d = 2   and A ( a , H ) 1 2 ( H a )   .
By Lemma  2.6 we can find 0 a a a H   such that A [ a , a ]   is a backward triangle from a   to a   and A ( a , H ) 1 2 ( H a )   . Without loss of generality we can assume gcd ( A [ a , H ] a ) = 1   . Then by Lemma  3.1 we have that | A [ 0 , a ] + A [ 0 , a ] | 3 A ( 0 , a )   or A [ 0 , a ]   is a full subset of a b.p. of difference 3   . However, the former implies | 2 A | 3 | A |   by Lemma  2.3 and the latter is impossible because d = 2   .   (Case  3.8 .2) Case  3.8 .3 d = 3   and A ( a , H ) 1 2 ( H a )   .
(Note that this case does not occur when | A | 1 2 H   .) Since A   is not a subset of a b.p., we can define b = min { x A : x { 0 , a } ( mod 3 ) } .   Let A 0 = A ( 3 * * N )   , A a = A ( a + ( 3 * * N ) )   , and A b = A ( b + ( 3 * * N ) )   . Let l 0 , l a , l b   be the least element of A 0 , A a , A b   , respectively. Let u 0 , u a , u b   be the largest element of A 0 , A a , A b   , respectively. Note that the rest of the proof does not use the fact that a 0   . Subcase  3.8 .3.1 b H   .
We have | A | | A 0 | + | A a |   . We can also assume | A a | 0   because otherwise | 2 A | | 2 A 0 | + | a + A 0 | + | b + A 0 | = 4 | A 0 | = 4 | A | .   Since A 0 A a   is a subset of a b.p., then by Theorem  A.1 , A 0   is full and A a   is full. This implies u a H   or u 0 H   because A ( a , H ) 1 2 ( H a )   . Suppose u a H   and u a u 0   .
Then
| 2 A | | 2 A 0 | + | 2 A a |
+ | A 0 + A a | + | b + A 0 [ u a + u 0 b , u 0 ] |
3 | A | + A 0 ( u a + u 0 b , u 0 ) 3 | A | .
By the same reason, if u 0 H   and u 0 u a   , then | 2 A | 3 | A |   . Note that if both u 0 H   and u a H   are true, then either u 0 u a   or u a u 0   .   (Subcase  3.8 .3.1) Subcase  3.8 .3.2 b H   .
Suppose d = gcd ( A [ b , H ] b ) > 1   . If d = 2   , then the proof of this case is same as the proof in Case  3.8 .1 and Case  3.8 .2 by considering H A   in the place of A   . So we can assume that d > 2   .
If d = 3   , then u 0 , u a < b   . Note that b { 0 , a } ( mod 3 )   . We can assume | A a | 0   because if | A a | 0   , then | 2 A | | 2 A 0 | + | 2 A b | + | A 0 + A b | + | u a + A 0 | 3 | A | .   We can also assume | A b | 0   because otherwise let c b   such that A ( c , b ) 0   and for every x c   , A ( x , c ) 0   . Then | 2 A | 3 | A 0 | + 3 | A a | + | H + A [ c + b H , c ] | 3 | A | .   Let u = max { u 0 , u a }   . If | 2 A | 3 | A |   , then
| 2 A | | 2 A 0 | + | 2 A a |
+ | A 0 + A a | + | 2 A b | + | u + A b |
3 | A 0 | + 3 | A a | + 3 | A b | = 3 | A |
implies that A 0   , A a   , and A b   are full. If u 0 b   and u 0 < u a   , then
| 2 A | | 2 A 0 | + | 2 A a | + | A 0 + A a | + | 2 A b |
+ | b + A a [ u a + u 0 b , u a ] | + | u a + A b |
3 | A 0 | + 3 | A a | + 3 | A b | + A a ( u a + u 0 b , u a ) 3 | A | .
So we can assume u 0 b   . By a similar argument we can also assume u a b   . However, above assumptions imply that
| 2 A | | 2 A 0 | + | 2 A a | + | A 0 + A a |
+ | 2 A b | + | u a + A b | + | u 0 + A b |
3 | A 0 | + 3 | A a | + 4 | A b | 3 | A | .
Suppose d 4   . We re-define A 0   to be A 0 [ 0 , b 1 ]   , A a   to be A a [ 0 , b 1 ]   , u 0 = max A 0   , and u a = max A a   . Let u = max { u 0 , u a }   . Then | 2 A | | 2 A 0 | + | 2 A a | + | A 0 + A a | + | 2 A b | + | u + A b | 3 | A |   together with | 2 A | 3 | A |   imply that A 0   , A a   , and A b   are all full. Note that | A 0 | 0   is always true. We can also assume | A a | 0   because otherwise we have | 2 A | | 2 A 0 | + | a + A 0 | + | b + A 0 | + | u + A b | + | 2 A b | 4 | A 0 | + 3 | A b | 3 | A | .   Hence we can assume u , u 3 , u 6 A 0 A a   . Since there are u , u { u , u 3 , u 6 }   such that u + A b   , u + A b   , and 2 A b   are pairwise disjoint, we have
| 2 A | | 2 A 0 | + | 2 A a | + | A 0 + A a |
+ | u + A b | + | u + A b | + | 2 A b |
3 | A 0 | + 3 | A a | + 4 | A b | 3 | A | .
Therefore, we can now assume that d = 1   . If A ( b , H ) 1 2 ( H b )   , then by Lemma  2.6 there exist b b b H   such that A ( b , H ) 1 2 ( H b )   and A [ b , b ]   is a backward triangle. Since 0 , a , b A [ 0 , b ]   , then A [ 0 , b ]   is not a subset of a b.p. of difference 3   . Clearly A [ 0 , b ]   is not a subset of a b.p. of difference 1   because d > 1   . Hence we have | 2 A | 3 | A |   by Lemma  3.5 and Lemma  2.3 . So we can now assume that A ( b , H ) 1 2 ( H b )   . let's re-define A 0   to be A 0 [ 0 , b 1 ]   , A a   to be A a [ 0 , b 1 ]   , u 0 = max A 0   , and u a = max A a   .
Then by Lemma  2.10 we have that A 0   and A a   are full and u 0 , u a b   . We can also assume A a ( l a , u a ) 0   because otherwise ( 2 A ) ( 0 , 2 b ) 4 A ( 0 , b )   , which implies | 2 A | 3 | A |   .
If A ( b , H ) 1 2 ( H b )   , then A ( 0 , b ) 1 2 b   . Since u 0 b   , u a b   , and d = 3   , then u a l a 1 2 b   , which implies l a 1 2 b   . Hence
| 2 A | | 2 A 0 | + | 2 A a | + | A 0 + A a |
+ | A [ b , H ] + A [ b , H ] | + | b + A 0 [ 0 , 2 l a b ] |
3 A ( 0 , b ) + 3 A ( b , H ) + A 0 ( 0 , 2 l a b ) 3 | A | .
So we can assume A ( b , H ) 1 2 ( H b )   .
If d ̲ b + U ( A ) = 0   , then there is a x A   , x b   such that either x b < u 0   and A ( b , x ) 1 10 ( x b + 1 )   , or A ( b , x ) 0   . Let F A [ b , H ]   be a finite set such that b F   and gcd ( ( F A [ x , H ] ) b ) = 1   . Then
| 2 A | | 2 A 0 | + | 2 A a | + | A 0 + A a |
+ | ( F A [ x , H ] ) + ( F A [ x , H ] ) | + | x + A 0 [ 2 u 0 x , u 0 ] |
3 A ( 0 , b ) + 3 A ( x , H ) + A 0 ( 2 u 0 x , u 0 )
3 A ( 0 , b ) + 3 A ( x , H ) + 1 3 ( x u 0 + 1 )
3 | A | + 1 3 ( x u 0 + 1 ) 3 10 ( x b + 1 ) 3 | A | .
If d ̲ b + U ( A ) > 1 2   , then there is a x b   such that A [ b , x ]   is a forward triangle. Clearly x H   and A ( x , H ) 1 2 ( H x )   . Let u = min { u 0 , u a }   . Note that u b   . By Lemma  3.5 and Lemma  2.3 , | 2 A | 3 | A |   implies that A [ u , H ]   is either a full subset of a b.p. of difference 3   or a full subset of a b.p. of difference 1   . Since u 0 , u a , b A [ u , H ]   , A [ u , H ]   cannot be a subset of a b.p. of difference 3   . Let A [ b , H ]   be a full subset of the b.p. [ b , z ] [ z , H ]   for some z < z   in A [ b , H ]   . Note that 2 z b + z   . Then
| 2 A | | 2 A 0 | + | 2 A a | + | A 0 + A a | + | A [ b , z ] + A [ b , z ] |
+ | A [ b , z ] + A [ z , H ] | + | A [ z , H ] + A [ z , H ] | + | z + A [ 2 z z , b ] |
3 A ( 0 , b ) + 3 A ( b , H ) + A ( 2 z z , b ) 3 | A | .
Now we can assume 0 < d ̲ b + U ( A ) 1 2   . Suppose there is a b b   in A   such that gcd ( A [ b , H ] b ) = d > 1   , If d = 2   , then there is a b b   such that d d   is odd.
Hence | A [ b , H ] + A [ b , H ] | 3 A ( b , H )   implies that A [ b , H ]   is full, which contradicts A ( b , H ) 1 2 ( H b )   . If d 3   , then | A [ u , H ] + A [ u , H ] | 4 A ( u , H ) 3 A ( u , H )   , which contradicts | 2 A | 3 | A |   by Lemma  2.3 . So we can assume that there is an x b   in A   such that gcd ( A [ x , H ] x ) = 1   . Since A 0   and A a   are full, we can assume u 3 A   .
Hence A ( u 3 + U )   is neither a subset of an a.p. of difference > 1   nor a subset of a ( u 3 + U )   –unbounded b.p. By Lemma  2.2 there exists a y A   with b y < x   such that A ( y , H ) 1 2 ( H y )   and ( 2 A ) ( 2 ( u 2 ) , 2 y ) 3 A ( u 2 , y )   . By Lemma  2.3 we have | A [ b , H ] + A [ b , H ] | 3 A ( b , H )   , which implies | 2 A | 3 | A |   again by Lemma  2.3 .   (Case  3.8 .3) Case  3.8 .4 d = 3   and A ( a , H ) 1 2 ( H a )   .
By Lemma  2.8 and ( IV ) we can find 0 a a a H   such that A [ a , a ]   is a backward triangle and A ( a , H ) 1 2 ( H a )   . By ( IV ) we have A ( 0 , a ) 1 2 a   . If a H   , then the lemma follows from Lemma  3.5 . So we can assume a H   . Now the lemma follows from Lemma  3.6 unless A [ 0 , a ]   is a subset of a b.p. of difference 3   . Without loss of generality, let A [ 0 , a ]   be a subset of a b.p. I 0 I 1   of difference 3   , where I i = i + ( 3 * * N )   for i [ 0 , 2 ]   . Let A i = A I i   and b = min ( A I 2 )   . Then b a   . Let l 1 = min A 1 [ 0 , a ]   .
Then 2 l 1 a   . If b a   , then ( 2 A ) ( 0 , 2 a ) 3 A ( 0 , a ) + | b + A 0 [ 0 , 2 l 1 b ] | 3 A ( 0 , a ) ,   which implies | 2 A | 3 | A |   by Lemma  2.3 . So we can assume b a   .
Subcase  3.8 .4.1 A ( a , b ) 1 2 ( b a )   . Then we have A ( b , H ) 1 2 ( H b )   . Hence we can find a c b c H   such that A [ c , c ]   is a backward triangle from c   to c   and A ( c , H ) 1 2 ( H c )   . Since A [ 0 , c ]   contains two backward triangles, it cannot be a subset of a b.p. of difference d   for d = 1   or d = 3   .
Hence by Lemma  3.5 we have | A [ 0 , c ] + A [ 0 , c ] | 3 A ( 0 , c )   , which implies | 2 A | 3 | A |   .
  (Subcase  3.8 .4.1) Subcase  3.8 .4.2 A ( a , b ) 1 2 ( b a )   .
Let c = max { x [ a , b 1 ] : x , x 1 A }   . It is easy to see that c a   and A ( c , b ) 1 3 ( b c )   . Since | 2 A | 3 | A |   implies | A [ 0 , c ] + A [ 0 , c ] | 3 A ( 0 , c )   , then we can assume that A [ 0 , c ]   is full in the b.p. I 0 I 1   , which implies A ( a , c ) 2 3 ( c a )   . Hence A ( c , H ) 1 2 ( H c )   . So we can find a m   with a m c   such that A ( m , H ) 1 2 ( H m )   .
It is easy to show that there is a m H   such that A [ m , m ]   is a forward triangle. Since A [ m , H ]   cannot be a full subset of a b.p. of difference 3   , because it contains b   , or 1   because A [ m , b 1 ] b m   , then by Lemma  3.5 we have | A [ m , H ] + A [ m , H ] | 3 A ( m , H )   . Since A [ 0 , m ]   is a subset of a b.p. of difference 3   we have | A [ 0 , m ] + A [ 0 , m ] | 3 A ( 0 , m )   . By Lemma  2.3 we have | 2 A | 3 | A |   .   (Case  3.8 .4) Case  3.8 .5 d 4   .
Since A   is not a subset of a b.p., the number b = min { x A : x { 0 , a } ( mod d ) }   is well defined. Let I i = i + ( d * * N )   and A i = A I i   . Let u i = max A i [ 0 , b 1 ]   and l i = min A i [ 0 , b 1 ]   for i = 0 , a   .
If b 2 a ( mod d )   , then a + b 0 ( mod d )   because otherwise A [ 0 , b ]   is a subset of an a.p. with difference d 3 > 1   . Hence we have either b 2 a ( mod d )   or a + b 0 ( mod d )   . This implies ( b + A 0 [ 0 , u 0 ] ) ( A [ 0 , b 1 ] + A [ 0 , b 1 ] ) =   or ( b + A a [ l a , u a ] ) ( A [ 0 , b 1 ] + A [ 0 , b 1 ] ) = .   If A ( b , H ) 1 2 ( H b )   , then there are 0 b b b H   such that A ( b , H ) 1 2 ( H b )   and A [ b , b ]   is a backward triangle. If | 2 A | 3 | A |   , then A [ 0 , b ]   is a full subset of either a b.p. of difference 3   or a b.p. of difference 1   . But both contradict d 4   . So we can assume A ( b , H ) 1 2 ( H b )   .
Suppose gcd ( A [ b , H ] b ) = 1   . By Lemma  2.10 we can show that u a b   , u 0 b   , A a ( l a , u a ) 0   , A 0 ( 0 , u 0 ) 0   , A 0 [ 0 , u 0 ]   is full in [ 0 , u 0 ]   , and A a [ l a , u a ]   is full in [ l a , u a ]   .
Hence
| 2 A | | A 0 [ 0 , u 0 ] + A 0 [ 0 , u 0 ] | + | A a [ l a , u a ] + A a [ l a , u a ] |
+ | A 0 [ 0 , u 0 ] + A a [ l a , u a ] | + | A [ b , H ] + A [ b , H ] |
+ min { | b + A 0 [ 0 , u 0 ] | , | b + A a [ l a , u a ] | }
3 A ( 0 , b ) + 3 A ( b , H ) + min { A 0 ( 0 , u 0 ) , A a ( l a , u a ) } 3 | A | .
Suppose gcd ( A [ b , H ] b ) = d > 1   . Let c = max { x A : gcd ( A [ x , H ] x ) < d }   . Then we have ( c + A [ b , H ] ) ( A [ b , H ] + A [ b , H ] ) = ,   ( c + A [ b , H ] ) ( A [ 0 , b 1 ] + A [ 0 , b 1 ] ) = , and   ( c + A [ b + 1 , H ] ) ( b + A [ 0 , b 1 ] ) = .   If A a ( l a , u a ) 0   , then we have
| 2 A | | A 0 [ 0 , u 0 ] + A 0 [ 0 , u 0 ] | + | A 0 [ 0 , u 0 ] + A a [ l a , u a ] |
+ | A a [ l a , u a ] + A a [ l a , u a ] | + min { | b + A 0 [ 0 , u 0 ] | , | a + A a [ l a , u a ] | }
+ | A [ b , H ] + A [ b , H ] | + | c + A [ b , H ] | 3 | A | .
If A a ( l a , u a ) 0   , then we have
| 2 A | | A 0 [ 0 , u 0 ] + A 0 [ 0 , u 0 ] | + | a + A 0 [ 0 , u 0 ] |
+ | b + A 0 [ 0 , u 0 ] | + | A [ b , H ] + A [ b , H ] | + | c + A [ b , H ] |
4 A 0 ( 0 , u 0 ) + 3 A ( b , H ) 3 | A | .
This ends the proof of Case  3.8 .5 as well as the lemma.   (Lemma  3.8 )
Lemma 3.9 Assume | A | 1 2 H   , 0 < d ̲ U ( A ) 1 2   , and A U   is a subset of a U   –unbounded b.p. of difference d   . If A   is not a subset of a b.p., then | 2 A | 3 | A |   .
Proof: Suppose A U   is a subset of the U   –unbounded b.p. ( d * U ) ( a + ( d * U ) )   for some a A U   . Clearly d 2   . Let b = min { x A : x { 0 , a } ( mod d ) }   . Note that A ( 0 , b 1 ) 0   . By Lemma  3.8 we can assume gcd ( A [ 0 , b 1 ] ) = 1   . If A ( b , H ) 1 2 ( H b )   , then we can find 0 b b b H   such that A ( b , H ) 1 2 ( H b )   and A [ b , b ]   is a backward triangle from b   to b   . Note that A [ 0 , b ]   cannot be a subset of a b.p. of difference 3   because otherwise A U   is a subset of an a.p. of difference 3   . By Lemma  2.3 we can assume | A [ 0 , b ] + A [ 0 , b ] | 3 A ( 0 , b )   . By Lemma  3.5  A [ 0 , b ]   is a full subset of a b.p. [ 0 , c ] [ c , b ]   , which contradicts the assumption 0 < d ̲ U ( A ) 1 2   . So we can assume A [ b , H ] 1 2 ( H b )   .
If d > 3   , then the proof of the lemma is the same as the proof of Case  3.8 .5. Suppose d = 3   . If b H   and gcd ( A [ b , H ] b ) > 1   , then the lemma follows from Lemma  3.8 . If gcd ( A [ b , H ] b ) = 1   or b H   , then | 2 A | 3 | A |   implies | A [ 0 , b 1 ] + A [ 0 , b 1 ] | 3 A ( 0 , b 1 )   , which implies A [ 0 , b 1 ]   is a full subset of a b.p. of difference 3   . Since A U   is already a subset of the b.p., then d ̲ U ( A ) = 2 3   , which contradicts d ̲ U ( A ) 1 2   .   (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 A [ 0 , H ]   and 0 , H A   . Suppose gcd ( A ) = 1   and 0 | A | 1 2 H   . If A   is not a subset of a b.p., then | 2 A | 3 | A |   .
Proof: By Lemma  3.8 we can assume that for every x 0   , if A ( 0 , x ) 0   , then gcd ( A [ 0 , x ] ) = 1   for every x 0   . If there is a x H   in A   such that A ( x , H ) 0   and gcd ( A [ x , H ] x ) > 1   , then the theorem is true again by Lemma  3.8 with A   replaced by H A   . So we can assume that for every x H   in A   , if A ( x , H ) 0   , then gcd ( A [ x , H ] x ) = 1   . We now divide the proof into four cases according to the value of d ̲ U ( A )   .
Case  3.10 .1 d ̲ U ( A ) > 1 2   .
Then there is a c 0   such that A [ 0 , c ]   is a forward triangle from 0   to c   . Since | A | 1 2 ( H + 1 )   , then c H   . Now the theorem follows from Lemma  3.5 .
Case  3.10 .2 0 < d ̲ U ( A ) 1 2   .
If A U   is a subset of an a.p. of difference > 1   , then the theorem follows from Lemma  3.8 . If A U   is a subset of a U   –unbounded b.p., then the theorem follows from Lemma  3.9 .
Otherwise by Lemma  2.2 we can find a y A   with 0 y H   such that A ( y , H ) 1 2 ( H y )   and ( 2 A ) ( 0 , 2 y ) 3 A ( 0 , y )   . If A ( y , H ) 0   , then the theorem is already true because | A | A ( 0 , y )   . So we can assume A ( y , H ) 0   . If gcd ( A [ y , H ] y ) > 1   , then the theorem follows from Lemma  3.8 . If gcd ( A [ y , H ] y ) = 1   , then the theorem follows from Lemma  2.3 .   (Case  3.10 .2) Case  3.10 .3 d ̲ U ( A ) = 0   and there is a x 0   such that A ( 0 , x ) 0   .
By Lemma  2.6 we can find such x A   such that for any y x   , A ( x , y ) 0   .
If A ( x , H ) 1 2 ( H x )   , then we can find 0 c x c H   such that, A ( c , H ) 1 2 ( H c )   , and A [ c , c ]   is a backward triangle. If c H   , then the theorem follows from Lemma  3.5 . Suppose c H   . Note that A [ 0 , c ]   cannot be a full subset of a b.p. of difference 3   by the condition of the case. Hence the lemma follows from Lemma  3.6 .
If A ( x , H ) 1 2 ( H x )   and A [ x , H ]   is a subset of an a.p. of difference > 1   , then the theorem follows from Lemma  3.8 . If A ( x , H ) 1 2 ( H x )   and A [ x , H ]   is not a subset of an a.p. of difference > 1   , then | 2 A | A ( x , 2 x ) + | A [ x , H ] + A [ x , H ] | 3 | A | + A ( x , 2 x ) 3 | A | .     (Case  3.10 .3) Case  3.10 .4 d ̲ U ( A ) = 0   and for every x 0   , A ( 0 , x ) 0   .
By symmetry we can also assume d ̲ H U ( A ) = 0   and for every y H   , A ( y , H ) 0   .
Let | A | α H   . Then 0 < α < 1 2   . By Lemma  2.6 there is a b 0   in A   such that A ( 0 , b ) α b   and A ( 0 , x ) α x   for every 0 x b   . By the assumption of this case, we have A ( 0 , b ) 0   and A ( b , H ) 0   . If there is a 0 x H   such that A [ 0 , x ]   or A [ x , H ]   is a subset of an a.p. of difference > 1   , then the theorem follows from Lemma  3.8 . Note that d ̲ b U ( A ) α   by the choice of b   . By Lemma  2.3 we can assume | A [ 0 , b ] + A [ 0 , b ] | 3 A ( 0 , b )   .
By Case  3.10 .1 and Case  3.10 .2 for A [ 0 , b ]   we can assume that A [ 0 , b ]   is a subset of a b.p. of difference d   . Clearly A [ 0 , b ]   is a full subset of the b.p. If d = 1   , then A [ 0 , b ]   is a full subset of [ 0 , x ] [ x , b ]   , which implies either A ( 0 , x ) 0   or d ̲ U ( A ) = 1   . Each of them contradicts the assumption of the case. If d > 1   , then d ̲ U ( A ) = 2 d   , which is again a contradiction to the assumption of the case.   (Theorem  3.10 )

4 Second Step: When | A | H   is almost 1 2   .

In this section we again assume A [ 0 , H ]   , 0 , H A   , and gcd ( A ) = 1   . In addition we also assume
| A | 1 2 H , (V)
A is not a subset of a b.p., (VI)
and
| 2 A | = 3 | A | 3 + b (VII)
for 0 b 0   . ( VII ) implies | 2 A | 3 | A |   . Under the condition above we want to prove
H + 1 2 | A | 1 + 2 b . (VIII)
Without loss of generality, we can assume that
| A | 1 2 ( H + 1 ) (IX)
because otherwise ( VIII ) is trivially true. In this section the letter b   is reserved only for the purpose in ( VII ).
Lemma 4.1 Let z [ 0 , H ] \ A   and let A = A { z }   . Suppose | ( 2 A ) \ ( 2 A ) | 2   and | 2 A | = 3 | A | 3 + b   . If
H + 1 > 2 | A | 1 + 2 b , (X)
then 0 b b 1   , | A | 1 2 ( H + 1 )   , and H + 1 > 2 | A | 1 + 2 b   .
Proof: If b = 0   , then | 2 A | = 3 | A | 3   . By Theorem  A.2 we have H + 1 2 | A | 1   , which contradicts | A | 1 2 ( H + 1 )   . So we can assume b > 0   . By the assumption of the lemma we have H + 1 2 | A | + 2 b   . Hence | A | = | A | + 1 1 2 ( H + 1 ) b + 1 1 2 ( H + 1 )   . Since
| 2 A | = 3 | A | 3 + b
| 2 A | + 2 = 3 | A | 1 + b
= 3 | A | 3 + ( b 1 ) ,
then b b 1   . If b < 0   , then by Theorem  A.1  A   is a subset of an a.p. of length 2 | A | 3 = 2 | A | 1   , which implies H + 1 2 | A | 1   , a contradiction to ( X ). Hence b 0   . Finally H + 1 > 2 | A | 1 + 2 b = 2 | A | 1 + 2 ( b 1 ) 2 | A | 1 + 2 b   .   (Lemma  4.1 )
Lemma 4.2 If there is an a 0   such that A [ a + 1 , H ]   is a subset of a b.p. of difference 3   , then H + 1 2 | A | 1 + 2 b   .
Proof: Without loss of generality we can assume a A   and A [ a , H ]   is not a subset of a b.p. of difference 3   . Fix j [ 2 , 0 ]   such that A [ a + 1 , H ] A 0 A 1   where A i = A J i   and J i = j + i + ( 3 * * N )   for i = 0 , 1 , 2   . For i = 0 , 1 , 2   let l i = min A i   and u i = max A i   . For i = 0 , 1   let I i = J i [ 0 , u i ]   and let I 2 = J 2 [ l 2 , u 2 ]   . Clearly a = u 2 0   . Since | 2 A | | 2 A 0 | + | 2 A 1 | + | A 0 + A 1 | 3 | A 0 | + 3 | A 1 | 3 | A | ,   then we have | 2 A i | 2 | A i |   for i = 0 , 1   . By Theorem  A.1 we have that A i   is full for i = 0 , 1   . Note that | A i | 0   for i = 0 , 1   by ( V ). If l 0 0   and l 0 l 1   , then | 2 A | 3 | A | + | a + A 1 [ l 1 , 2 l 0 ] | 3 | A |   . By symmetry we can also prove that l 1 0   and l 1 l 0   together are impossible. So we can assume l 0 0   and l 1 0   . Without loss of generality we assume u 0 = H   . Then | A | 1 2 ( H + 1 )   implies u 1 H 2   .
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 | A |   is the maximum among all the sets in I 0 I 1 I 2   containing the original set and satisfying ( VII ), ( IX ), and ( X ).
Claim  4.2 .1: If l i z u i   and z j + i ( mod 3 )   for i = 0   or i = 1   , then z A   . Proof of Claim  4.2 .1: Suppose not and let A = A { z }   . By Lemma  4.1 and by the maximality of | A |   we need only to show that | ( 2 A ) \ ( 2 A ) | 2   for a contradiction. First let z j ( mod 3 )   . Let y A   .
If y A 0 { z }   and y u 0   , then A 0 [ y + 1 , y + t ] ( y + z A 0 [ z t , z 1 ] )   for some 0 t min { u 0 y , z }   , which implies y + z ( 2 A 0 ) ( 2 A )   , by the pigeonhole principle.
If y A 0 { z }   and y u 0   , then A 0 [ y t , y 1 ] ( y + z A 0 [ z + 1 , z + t ] )   for some 0 t min { y , u 0 z }   , which implies y + z ( 2 A 0 ) ( 2 A )   . If y A 1   and y u 1   , then A 1 [ y + 1 , y + t ] ( y + z A 0 [ z t , z 1 ] )   for some 0 t min { u 1 y , z }   , which implies y + z A 1 + A 0 ( 2 A )   . If y A 1   and y u 1   , then A 1 [ y t , y 1 ] ( y + z A 0 [ z + 1 , z + t ] )   for some 0 t min { y , u 0 z }   , which implies y + z A 1 + A 0 ( 2 A )   . If y A 2   , then 0 y + z u 0 2 u 1   . Since A 1   is full, then there are x 2 l 1   and x 2 u 1   such that ( J 0 + J 2 ) [ x , x ] ( 2 A 1 )   . Hence y + z ( 2 A 1 ) ( 2 A )   . By all the arguments above we have ( 2 A ) = ( 2 A )   .
For the case that z j + 1 ( mod 3 )   the proof is similar.   (Claim  4.2 .1) Claim  4.2 .2: If u 1 2 < z < u 1   and z j + 1 ( mod 3 )   , then z A   .
Proof of Claim  4.2 .2: Suppose not and let z   be the least number such that the claim is not true. By Claim  4.2 .1 we have z u 1   . Let A = A { z }   . It suffices to show | ( 2 A ) \ ( 2 A ) | 2   . Let y A   .
If y A 0   and y u 0   , then A 0 [ y + 1 , y + t ] ( y + z A 1 [ z t , z 1 ] )   for some 0 t min { u 0 y , z }   , which implies y + z A 0 + A 1 ( 2 A )   . If y A 0   and u 0 y < u 0   , then y + z = u 0 + ( z ( u 0 y ) ) A 0 + A 1 ( 2 A )   by the minimality of z   . If y A 1 { z }   and y u 1   , then A 1 [ y + 1 , y + t ] ( y + z A 1 [ z t , z 1 ] )   for some 0 t min { u 1 y , z }   , which implies y + z ( 2 A 1 ) ( 2 A )   . If y A 1 { z }   and u 1 y < u 1   , then y + z = u 1 + ( z u 1 + y ) ( 2 A 1 ) ( 2 A )   . If y A 2   , then y + z ( 2 A 0 )   by the facts that A 0   is full and 2 l 0 y + z 2 u 0   . Hence ( ( 2 A ) \ ( 2 A ) ) { z + u 0 , z + u 1 }   .   (Claim  4.2 .2) Claim  4.2 .3: If u 0 2 < z < u 0   and z j ( mod 3 )   , then z A   .
Proof of Claim  4.2 .3: Suppose not and let z   be the least number such that the claim is not true. By Claim  4.2 .1 we have z u 0   . Let A = A { z }   . Again it suffices to show | ( 2 A ) \ ( 2 A ) | 2   . Let y A   .
If y A 0 { z }   and y u 0   , then A 0 [ y + 1 , y + t ] ( y + z A 0 [ z t , z 1 ] )   for some 0 t min { u 0 y , z }   , which implies y + z ( 2 A 0 ) ( 2 A )   . If y A 0 { z }   and u 0 y < u 0   , then y + z = u 0 + ( z ( u 0 y ) ) ( 2 A 0 ) ( 2 A )   by the minimality of z   . If y A 1   and y u 1   , then A 1 [ y + 1 , y + t ] ( y + z A 0 [ z t , z 1 ] )   for some 0 t min { u 1 y , z }   , which implies y + z A 1 + A 0 ( 2 A )   . If y A 1   and u 1 y u 1   , then y + z = ( y ( u 0 z ) ) + u 0 A 1 + A 0 ( 2 A )   . Note that y u 0 + z A 1   by Claim  4.2 .1 and Claim  4.2 .2. If y A 2   and y < u 2   , then y + z = u 2 + ( z u 2 + y ) A 2 + A 0 ( 2 A )   .
Hence ( ( 2 A ) \ ( 2 A ) ) { u 0 + z , u 2 + z }   .   (Claim  4.2 .3) Claim  4.2 .4: There is an i { 0 , 1 }   such that l i < z < u i 2   and z j + i ( mod 3 )   imply z A   .
Proof of Claim  4.2 .4: Suppose not and let z i = max { z [ 0 , H ] : l i < z < u i 2 , z j + i ( mod 3 ) and z A i }   for i = 0 , 1   . By Claim  4.2 .1 we have z i 0   .
Subclaim  4.2 .4.1: z 0 l 0 = z 1 l 1   .
Proof of Subclaim  4.2 .4.1: Suppose the subclaim is not true. Without loss of generality we assume z 0 l 0 < z 1 l 1   . Let A = A { z 1 }   . Since z 0 + l 1 < z 1 + l 0   , then z 1 + l 0 = ( z 0 + t ) + l 1 A 0 + A 1 ( 2 A )   for t = ( z 1 + l 0 ) ( z 0 + l 1 )   by the maximality of z 0   . By the similar arguments in the last several claims we have ( ( 2 A ) \ ( 2 A ) ) { z 1 + l 1 , z 1 + l 2 }   .
This contradicts the maximality of | A |   by Lemma  4.1 . By a symmetric argument we can show z 0 l 0 > z 1 l 1   is also impossible.   (Subclaim  4.2 .4.1) Case  4.2 .4.1: z 0 + l 2 < z 1 + l 1   .
Let A = A { z 1 }   . Note that z 0 + l 2 z 1 + l 1 ( mod 3 )   . Then z 1 + l 1 = z 0 + t + l 2 A 0 + A 2 ( 2 A )   for t = ( z 1 + l 1 ) ( z 0 + l 2 ) > 0   . Hence by the similar arguments as in Subclaim  4.2 .4.1 we can show ( ( 2 A ) \ ( 2 A ) ) { z 1 + l 0 , z 1 + l 2 }   .   (Case  4.2 .4.1) Case  4.2 .4.2: z 0 + l 2 > z 1 + l 1   .
Let A = A { z 0 }   . Then z 0 + l 2 = z 1 + t + l 1 ( 2 A 1 )   for t = ( z 0 + l 2 ) ( z 1 + l 1 ) > 0   by the maximality of z 1   . Hence ( ( 2 A ) \ ( 2 A ) ) { z 0 + l 0 , z 0 + l 1 }   .   (Case  4.2 .4.2) Following the two cases above we have z 0 + l 2 = z 1 + l 1   . By symmetric arguments we can also show that z 1 + l 2 = z 0 + l 0   . Subtracting the second equality from the first we have z 0 z 1 = z 1 z 0 + l 1 l 0   . This implies 2 ( z 0 z 1 ) = l 1 l 0   . But by Subclaim  4.2 .4.1 we have z 0 z 1 = ( l 1 l 0 )   . Hence l 1 l 0 = 0   , which is absurd.   (Claim  4.2 .4) Claim  4.2 .5: If l i < z < u i 2   and z j + i ( mod 3 )   , then z A   for i = 0 , 1   . 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 l 0 < z < u 0 2   and z j ( mod 3 )   imply z A   .
Let z 1 = max { z [ 0 , H ] : l 1 < z < u 1 2 , z j + 1 ( mod 3 ) and z A 1 }   . Let A = A { z 1 }   . Then z 1 + l 0 = l 1 + ( l 0 + z 1 l 1 ) A 1 + A 0 ( 2 A )   . It is now easy to see that ( ( 2 A ) \ ( 2 A ) ) { z 1 + l 1 , z 1 + l 2 }   . This contradicts the maximality of | A |   .   (Claim  4.2 .5) Claim  4.2 .6: l 0 + l 2 2 l 1 3   and l 1 + l 2 2 l 0 3   .
Proof of Claim  4.2 .6: By symmetry we need only to show the first inequality. Assume it is not true and we have l 0 + l 2 2 l 1 6   . Then l 1 [ 0 , 2 ]   . Let z = l 1 3   and A = A { z }   .
Let y A   .
If y A 0   and y l 0   , then y + z = ( y 3 ) + l 1 A 0 + A 1 ( 2 A )   . If y A 1   and y l 1   , then A 1 [ y t , y 1 ] ( y + z A 1 [ z + 1 , z + t ] )   for some 0 t min { y , u 1 }   , which implies y + z ( 2 A 1 ) ( 2 A )   . If y A 1 { z }   and y l 1   , then y + z = ( l 0 + t ) + l 2 A 0 + A 2   for t = ( y + z ) ( l 0 + l 2 ) ( 2 l 1 6 ) ( l 0 + l 2 ) 0   . If y A 2   and y > l 2   , then y + z = l 2 + ( z + y l 2 ) A 2 + A 1 ( 2 A )   . Hence ( ( 2 A ) \ ( 2 A ) ) { z + l 0 , z + l 2 }   , a contradiction to the maximality of | A |   by Lemma  4.1 .   (Claim  4.2 .6) Claim  4.2 .7: Let z = u 2 + 3   and A = A { z }   . Then ( VII ), ( IX ), and ( X ) maintain true with A   and b   being replaced by A   and b   , respectively.
Proof of Claim  4.2 .7: By Lemma  4.1 it suffices to prove | ( 2 A ) \ ( 2 A ) | 2   . Suppose not. We derive a contradiction.
Subclaim  4.2 .7.1: l 0 + l 1 6 u 2 + l 2   .
Prove of Subclaim  4.2 .7.1: Assume the subclaim is not true. So we have u 2 + l 2 l 0 + l 1 3   . Let y A   If y A 0   and y < u 0   , then y + z = ( y + 3 ) + ( z 3 ) A 0 + A 2 ( 2 A )   . If y A 1   and y < u 1   , then y + z = ( y + 3 ) + ( z 3 ) A 1 + A 2 ( 2 A )   . If y A 2 { z }   , then y + z = y + u 2 + 3 l 2 + u 2 + 3 l 0 + l 1   . Hence y + z = ( l 0 + t ) + l 1 A 0 + A 1 ( 2 A )   for t = ( y + z ) ( l 0 + l 1 ) 0   . Now we have ( ( 2 A ) \ ( 2 A ) ) { z + u 0 , z + u 1 }   , which contradicts the assumption that | ( 2 A ) \ ( 2 A ) | 2   .   (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 2 ( l 0 + l 1 + l 2 ) 2 l 0 + 2 l 1 + u 2 + l 2   . This implies l 2 u 2   . Hence A 2 = { l 2 }   . So by Subclaim  4.2 .7.1 again we have l 0 + l 1 6 2 l 2   . Since 0 = min A   , then 0 { l 0 , l 1 , l 2 }   . We want to show l 2 = 0   . Suppose l 0 = 0   . Then by Claim  4.2 .6 and Subclaim  4.2 .7.1 we have l 2 2 l 1 3   and l 1 6 2 l 2   . So l 1 6 2 ( 2 l 1 3 ) = 4 l 1 6   implies l 1 4 l 1   , which is absurd because l 0 = 0   implies l 1 > 0   . By symmetry we also have l 1 > 0   . Hence l 2 = 0   . By Claim  4.2 .6 and Subclaim  4.2 .7.1 again we have l 0 2 l 1 3   and l 1 2 l 0 3   , which imply l 0 + l 1 2 ( l 0 + l 1 ) 6   or equivalently l 0 + l 1 6   . Hence by Subclaim  4.2 .7.1 we have l 0 + l 1 = 6   . Note that l 0 l 1 ( mod 3 )   . So ( l 0 , l 1 ) ( 3 , 3 )   . Assume l 0 < l 1   . The ( l 0 , l 1 ) = ( 2 , 4 )   or ( l 0 , l 1 ) = ( 1 , 5 )   . But each of the two cases contradicts the inequality l 0 2 l 1 3   in Claim  4.2 .6 with l 2 = 0   .   (Claim  4.2 .7) By Claim  4.2 .7 we can add u 2 + 3 , u 2 + 6 , u 2 + 9 ,   successively to A   to form a set A   so that ( VII ), ( IX ), and ( X ) maintain true with A   and b   being replaced by A   and b   , respectively. However, ( IX ) will be eventually violated in this process.   (Lemma  4.2 )
Lemma 4.3 Let A i = { z A : z i ( mod 3 ) }   for i = 0 , 1 , 2   . If there is an i [ 0 , 2 ]   such that max A i min A i 0   , then H + 1 2 | A | 1 + 2 b   .
Proof: The ideas are same as in the proof of Lemma  4.2 . We will describe the steps without too much technical details. Let I i = i + ( 3 * * N )   , A i = A I i   , l i = min A i   , and u i = max A i   for i = 0 , 1 , 2   .
Without loss of generality let u 2 l 2   . By Lemma  4.2 we can assume 0 l 2 u 2 u 2   .
Since | 2 A | | 2 A 0 | + | 2 A 1 | + | A 0 + A 1 | 3 | A 0 | + 3 | A 1 | 3 | A | ,   then | 2 A | 3 | A |   implies that A i   is full for i = 0 , 1   . Note that | A 0 | H 6   , | A 1 | H 6   , and | A 0 A 1 | 1 2 H   .
Suppose the lemma is not true. Without loss of generality we can assume that | A |   is the maximum among all the sets in i = 0 2 I i [ l i , u i ]   containing the original set and satisfying ( VII ), ( IX ), and ( X ). Without loss of generality let's assume l 0 = 0   .
Case  4.3 .1 H = u 0   .
If l 2 2 l 1   , then | 2 A | | 2 A 0 | + | 2 A 1 | + | A 0 + A 1 | + | l 2 + A 0 [ 0 , 2 l 1 l 2 ] 3 | A | .   So we can assume 2 l 1 l 2   . By symmetry we can assume u 2 + H 2 u 1   . Since u 1 l 1 1 2 H   by ( V ), we have 2 l 1 l 2   and u 2 + H 2 u 1   . Hence A 2 + A 1 ( 2 A 0 ) [ l 1 + l 2 , u 1 + u 2 ] = ( 2 I 0 ) [ l 1 + l 2 , u 1 + u 2 ] .   This implies A 1 = I 1 [ l 1 , u 1 ]   by Lemma  4.1 and the maximality of | A |   . Then we can show A 0 = I 0 [ l 0 , u 0 ]   again by Lemma  4.1 and the maximality of | A |   . Furthermore, we can show A 2 = I 2 [ l 2 , u 2 ]   by the fact that ( 2 I 2 ) [ 2 l 2 , 2 u 2 ] A 0 + A 1   and by Lemma  4.1 . Now we add z = u 2 + 3   , z = u 2 + 6   , z = u 2 + 9   , etc. successively to A   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 H = u 1   .
We can again show that 2 l 1 l 2   and u 2 + H 2 u 0   because otherwise we can show | 2 A | 3 | A |   . Since H l 1 + u 0 3 2 H   , then u 0 l 1 H 2   , which implies 2 l 1 l 2   and u 2 + H 2 u 0   . Again assume that A i = 0 2 I i [ l i , u i ]   has the maximum cardinality among the sets satisfying ( VII ), ( IX ), and ( X ). Then we can show A i = I i [ l 0 , u 0 ]   for i = 0 , 1 , 2   .
Finally we can again add z = u 2 + 3   , z = u 2 + 6   , z = u 2 + 9   , etc. successively to A   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 0 a c H   such that A [ 0 , a ]   is a backward triangle as well as a subset of a b.p. of difference 3   and A [ c , H ]   is a forward triangle as well as a subset of a b.p.
of difference 3   . Then H + 1 2 | A | 1 + 2 b   .
Proof: The ideas are again the same as in the proof of Lemma  4.2 . Let I i = ( i + ( 3 * * N ) )   for i = 0 , 1 , 2   . By Lemma  4.3 we can assume that A [ 0 , a ] I 0 I 1   and A [ c , H ] I 0 I 2   .
For i = 0 , 1 , 2   let A i = A I i   , l i = min A i   , u i = max A i   , and J i = I i [ l i . u i ]   . Then we have u 1 l 2 a   . Suppose the lemma is not true. Then A   satisfies ( VII ), ( IX ), and ( X ). We again assume the maximality of | A |   for A J 0 J 1 J 2   satisfying ( VII ), ( IX ), and ( X ). By Lemma  4.1 we can prove that for each x   , l i x u i   implies x A   . Then we can prove A i = J i   by the same ideas as in the proof of Lemma  4.2 . Now we can add u 1 + 3 , u 1 + 6 , u 1 + 9 ,   successively to A   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 x 0   in A   such that gcd ( A [ x , H ] x ) = d > 1   , then H + 1 2 | A | 1 + 2 b   .
Proof: Since ( V ) is true, then d = 2   . Let c = min { x A : gcd ( A [ x , H ] x ) = 2 }   . Then c 0   , c > 0   , and A [ c , H ]   is full. Let E   be the set of all even numbers and O   be the set of all odd numbers. Let A e = A E   and A o = A O   . Let l e = min A e   , l o = min A o   , u e = max A e   , and u o = max A o   .
Case  4.5 .1 c   is even.
Then l e = 0   , u e = H   , and A e   is full. We want to show H + 1 2 | A | 1 + 2 b   .
Let | 2 A e | = 2 | A e | 1 + b e   . Then b e 0   . By Theorem  A.1 we have H 2 + 1 | A e | + b e   .
On the other hand, by Theorem  A.4 , | A e + A o | min { | A e | + 2 | A o | 2 , H 2 + | A o | } .   If H 2 + | A o | | A e | + 2 | A o | 2   , then
3 | A | 3 + b = | 2 A |
2 | A e | 1 + b e + | A e | + 2 | A o | 2
3 | A | 3 + b e | A o | .
This implies b e b + | A o |   . Hence H 2 + 1 | A e | + b e | A | + b   , which implies H + 1 2 | A | 1 + 2 b   .
If H 2 + | A o | < | A e | + 2 | A o | 2 = | A | + | A o | 2   , then | A | > H 2 + 2   , which contradicts ( IX ).   (Case  4.5 .1) Case  4.5 .2 c   is odd.
Clearly, 0 = l e   and H = u o   . If l o > u e   , then A   is a subset of a b.p. Hence we can assume l o < u e   and need to show H + 1 2 | A | 1 + 2 b   . Suppose H + 1 > 2 | A | 1 + 2 b   . Let S = { x O [ l o , u o ] : A o ( l o , x ) x l o + 1 1 4 } .   If S   , let l = ( max S ) + 1   . Otherwise, let l = l o   . Let T = { x O [ l o , u o ] : A o ( x , u o ) u o x + 1 1 4 } .   If T   , let u = ( min T ) 1   . Otherwise, let u = u o   . Note that l , u A o   . Since A o   is full, then l l o   and u u o   . For each x O [ l , u o ]   , we have A o ( l o , x ) x l o + 1 > 1 4   and for any x O [ l o , u ]   , we have A o ( x , u o ) u o x + 1 > 1 4   . By the pigeonhole principle E [ l o + l , u o + u ] ( 2 A o ) .   Let p = O ( l , u ) A o ( l , u )   , p = O ( l , l + u e ) A o ( l , l + u e )   , and p = p p   . Let A ¯ o = A o O [ l , u ]   . Then 2 A ¯ o = 2 A o   . Hence | 2 A ¯ o | = | 2 A o | = 2 | A o | 1 + b o = 2 | A ¯ o | 1 + b o 2 p .   This implies, by Theorem  A.1 , 1 2 ( H l o ) + 1 | A ¯ o | + b o 2 p = | A o | + b o p .   Subcase  4.5 .2.1 p 2 | A e |   .
Since
3 | A | 3 + b = | 2 A |
| 2 A o | + | A e + A o |
2 | A o | 1 + b o + | 0 + A o [ l o , l + u e 2 ] | + | u e + A o [ l , H ] |
2 | A o | 1 + b o + A o ( l o , l + u e 2 ) + A o ( l , H )
3 | A | 3 + b o 3 | A e | + A o ( l , l + u e ) + 1 ,
then b o b + 3 | A e | A o ( l , l + u e ) 1   . Hence
1 2 ( H l o ) + 1 | A o | + b o p
| A o | + b + 3 | A e | A o ( l , l + u e ) 1 p
| A | + b + ( 2 | A e | p ) O ( l , l + u e ) 1
| A | + b 1 2 u e 2 < | A | + b 1 2 u e .
This implies H l o + 2 2 | A | + 2 b u e   and H + 1 2 | A | 1 + 2 b ( u e l o ) < 2 | A | 1 + 2 b .     (Subcase  4.5 .2.1) Subcase  4.5 .2.2 p < 2 | A e |   .
Since u ( l + u e ) 0   and u e 0   , then there exists a t , t O [ l + 2 u e + 1 , u 2 u e 1 ]   such that t t > max { u o u , l l o }   and | A e | + A o ( t u e , t + 2 u e ) > 3 2 u e + t t 2 + 1   because otherwise we can find three disjoint intervals of length t t + 3 u e + 1   for t t = 2 + max { u o u , l l o }   in [ l + u e + 2 , u ]   such that each contains at least | A e |   elements from the set O \ A o   . This contradicts the assumption p < 2 | A e |   . Suppose H + 1 > 2 | A | 1 + 2 b   .
We want to derive a contradiction by induction on the size of the counterexamples A A   .
Suppose A = A e A o   is the set with the maximum cardinality | A |   such that A o A o O [ l o , u o ]   , | 2 A | = 3 | A | 3 + b   for 0 b b   , and H + 1 > 2 | A | 1 + 2 b   .
Claim  4.5 .2.2.1 A o [ t , t + u e ] = O [ t , t + u e ]   .
Proof of Claim  4.5 .2.2.1: Suppose the claim is not true and let g O [ t , t + u e ] \ A o   . Let A o = A o { g }   and A = A e A o   . Note that if x A o [ l o , u o ]   , then l o + l < x + g < u o + u   .
Hence x + g ( 2 A o ) ( 2 A )   . Let x A e [ 0 , u e ]   . Since
| A e | + A o ( g + x u e , g + x )
= | A e | + A o ( t u e , t + 2 u e )
A o ( t u e , g + x u e 2 ) A o ( g + x + 2 , t + 2 u e )
> 3 2 u e + t t 2 + 1 u e t t 2
= 1 2 u e + 1 ,
then ( g + x A e ) A o [ g + x u e , g + x ]   . Hence g + x A o + A e ( 2 A )   . Now we have that ( 2 A ) = ( 2 A )   , which contradicts the maximality of | A |   by Lemma  4.1 .   (Claim  4.5 .2.2.1) Claim  4.5 .2.2.2 A o [ t + u e + 2 , H ] = O [ t + u e + 2 , H ]   .
Suppose the claim is not true and let g = min ( O [ t + u e + 2 , H ] \ A o )   . Let A o = A o { g }   , and A = A e A o   . Then g > t + u e   . Note that if x A o [ l , u ]   , then l o + l x + g u o + u   .
Hence x + g ( 2 A )   . If x A o [ l o , l 2 ]   , then y = g ( l x ) A o   by the minimality of g   and Claim  4.5 .2.2.1. Hence x + g = l + y ( 2 A )   . If x A o [ u + 2 , H 2 ]   , then x + g = H + ( g ( H x ) ) ( 2 A )   . If x A e [ 0 , u e 2 ]   , then x + g = u e + ( g ( u e x ) ) ( 2 A )   .
From the arguments above, we have ( 2 A ) \ ( 2 A ) { H + g , u e + g }   , which contradicts the maximality of | A |   by Lemma  4.1 .   (Claim  4.5 .2.2.2) Claim  4.5 .2.2.3 A o [ l o , t 2 ] = O [ l o , t 2 ]   .
Proof of Claim  4.5 .2.2.3: Suppose the claim is not true and let g = max ( O [ l o , t 2 ] \ A o )   . Let A = A { g }   . Then ( 2 A ) \ ( 2 A ) { 0 + g , l o + g }   , which contradicts the maximality of | A |   .   (Claim  4.5 .2.2.3) By the three claims above we have A o = O [ l o , u o ]   .
Without loss of generality, we can assume that our original counterexample A   satisfies A o = O [ l o , u o ]   . Hence | A o | = H l o 2 + 1 or 2 | A o | 1 = H l o + 1   . Note also that since H + 1 = H l o + 1 + l o = 2 | A | 1 + l o 2 | A e |   , we can assume that l o 2 | A e | + 1   .
Claim  4.5 .2.2.4 2 l o u e + 4   .
Proof of Claim  4.5 .2.2.4: Suppose 2 l o u e + 2   . For each even number z E [ u e , H 1 ]   let A z = A E [ u e , z ]   . Let
S = { z E [ u e , H 1 ] : | 2 A z | = 3 | A z | 3 + b z 3 | A z | 3 ,
b z b , and H + 1 > 2 | A z | 1 + 2 b z } .
Clearly, u e S   . For each z 0   , | A z | = | A | + E ( u e + 2 , z ) 1 2 H   , which implies z S   . Let z 0 = max S 0   . We now derive a contradiction.
By Theorem  A.2 we can assume b z 0 > 0   . Note that since | A z 0 + 2 | = | A z 0 | + 1   , we have H + 1 > 2 | A z 0 | 1 + 2 b z 0 = 2 | A z 0 + 2 | 1 + 2 ( b z 0 1 ) .   Since for each x A z 0 + 2 E   , x + z 0 + 2 E [ 2 l o , 2 H ]   . Hence ( 2 A z 0 + 2 ) \ ( 2 A z 0 ) { z 0 + 2 + H }   , which contradicts the maximality of z 0   by Lemma  4.1 .   (Claim  4.5 .2.2.4) Let d = gcd ( A e )   . Then d   must be an even number. Let q = min ( A e [ l o + 1 , u e ] )   and q = max ( A e [ 0 , l o 1 ] )   .
Subsubcase  4.5 .2.2.1 d 4   .
First we can assume that u e = q   by the following argument.
Let A = A \ A e [ q + 2 , u e ]   . Then | A | = | A | A e ( q + 2 , u e )   . Note that A e ( q + 2 , u e ) u e q d u e q 4   . Since ( 2 A ) ( 2 A ) \ O [ q + 2 + H , u e + H ]   and O [ q + 2 + H , u e + H ] A e + A o ( 2 A )   , then there is a b 0   such that
3 | A | 3 + b = | 2 A |
| 2 A | u e q 2
= 3 | A | 3 + b u e q 2
= 3 | A | 3 + b u e q 2 + 3 A e ( q + 2 , u e )
3 | A | 3 + b + A e ( q + 2 , u e ) .
This shows b b + A e ( q + 2 , u e )   . So
H + 1 > 2 | A | 1 + 2 b
= 2 | A | + 2 A e ( q + 2 , u e ) 1 + 2 b
= 2 | A | 1 + 2 ( b + A e ( q + 2 , u e ) )
2 | A | 1 + 2 b .
Hence A   is the desired counterexample. Now identify A   with A   .
Subsubsubcase  4.5 .2.2.1.1 u e = l o + 1   .
Since q u e d < u e 2   , then q + u e 2 l o 2   and q + u e A e [ 0 , q ] + A e [ 0 , q ]   .
Hence we have ( 2 A e ) ( 0 , 2 l o 2 ) 2 A e ( 0 , q )   . So we have
| 2 A | = | 2 A o | + | A o + A e | + ( 2 A e ) ( 0 , 2 l o 2 )
2 | A o | 1 + | A o | + u e 2 + 2 A e ( 0 , q )
3 | A | 1 3 | A e | + u e 2 + 2 | A e | 2
3 | A | 3 | A e | + u e 2 .
This shows | A e | + u e 2 b   . On the other hand,
H + 1 = 2 | A o | 1 + l o
= 2 | A | 1 + l o 2 | A e |
2 | A | 1 + l o + 2 ( b u e 2 )
= 2 | A | 1 + 2 b + ( l o u e ) < 2 | A | 1 + 2 b .
This contradicts the assumption that H + 1 > 2 | A | 1 + 2 b   .   (Subsubsubcase  4.5 .2.2.1.1) Subsubsubcase  4.5 .2.2.1.2 u e > l o + 1   .
Then we have
| 2 A | = | 2 A o | + | A o + A e | + ( 2 A e ) ( 0 , 2 l o 2 )
2 | A o | 1 + | A o | + u e 2 + 2 A e ( 0 , q ) 1
3 | A | 1 3 | A e | + u e 2 + 2 | A e | 3
3 | A | 3 | A e | + u e 2 1 .
This shows | A e | + u e 2 1 b   . On the other hand,
H + 1 = 2 | A 0 | 1 + l o
= 2 | A | 1 + l o 2 | A e |
2 | A | 1 + l o + 2 ( b u e 2 + 1 )
= 2 | A | 1 + 2 b + ( l o u e + 2 )
2 | A | 1 + 2 b ,
by the assumption u e > l o + 1   . This again contradicts H + 1 > 2 | A | 1 + 2 b   .   (Subsubcase  4.5 .2.2.1) Subsubcase  4.5 .2.2.2 d = 2   .
Subsubsubcase  4.5 .2.2.2.1 | 2 A e | = 2 | A e | 1 + b e   for some b e < | A e | 2   .
Since A e E   , then by Theorem  A.1  u e 2 + 1 | A e | + b e   . We also have
| 2 A | = | 2 A o | + | 2 A e | + | A o + A e | ( 2 A e ) ( 2 l o , 2 u e )
2 | A o | 1 + 2 | A e | 1 + b e + | A o | + u e 2 2 u e 2 l o 2 1
3 | A | 3 | A e | + b e + u e 2 + l o u e ,
which implies | A e | + b e u e 2 + l o b   . Hence
u e 2 + 1 + H l o 2 + 1
| A e | + b e + | A o | = | A | + b e
| A | + b + | A e | + u e 2 l o .
This implies u e + 2 + H l o + 2 2 | A | + 2 b + 2 | A e | + u e 2 l o   . Hence H + 1 2 | A | 1 + 2 b + ( 2 | A e | l o 2 ) < 2 | A | 1 + 2 b   because | A | = | A e | + | A o | = | A e | + H l o 2 + 1 1 2 ( H + 1 )   implies l o > 2 | A e |   .   (Subsubsubcase  4.5 .2.2.2.1) Subsubsubcase  4.5 .2.2.2.2 | 2 A e | 3 | A e | 3   and u e l o 2 | A e | 4   .
Since
| 2 A | = 2 | A o | 1 + | A o | + u e 2 + ( 2 A e ) ( 0 , 2 l o 2 )
= 3 | A | 3 + u e 2 3 | A e | + ( 2 A e ) ( 0 , 2 l o 2 ) + 2 ,
then u e 2 3 | A e | + ( 2 A e ) ( 0 , 2 l o 2 ) + 2 b   . Hence H l o 2 + 1 = | A o |   implies
H + 1 = 2 | A | 1 + l o 2 | A e |
2 | A | 1 + l o + 2 ( b u e 2 + 2 | A e | ( 2 A e ) ( 0 , 2 l o 2 ) 2 )
2 | A | 1 + 2 b + ( 4 | A e | 4 ( u e l o ) 2 ( 2 A e ) ( 0 , 2 l o 2 ) ) .
Since
( 2 A e ) ( 0 , 2 l o 2 ) = ( 2 A e ) ( 0 , 2 u e ) ( 2 A e ) ( 2 l o , 2 u e )
3 | A e | 3 ( u e l o + 1 ) = 3 | A e | 4 u e + l o ,
then
4 | A e | 4 ( u e l o ) 2 ( 2 A e ) ( 0 , 2 l o 2 )
4 | A e | 4 ( u e l o ) 2 ( 3 | A e | 4 u e + l o )
2 | A e | + 4 + u e l o 0 .
Hence H + 1 2 | A | 1 + 2 b   , a contradiction.   (Subsubsubcase  4.5 .2.2.2.2) Subsubsubcase  4.5 .2.2.2.3 | 2 A e | 3 | A e | 3   and u e l o > 2 | A e | 4   .
This time we use the fact that ( 2 A e ) ( 0 , 2 l o 2 ) | 0 + A e | = | A e |   implied by Claim  4.5 .2.2.4. Since
| 2 A | 3 | A | 3 + u e 2 3 | A e | + ( 2 A e ) ( 0 , 2 l o 2 ) + 2
3 | A | 3 + u e 2 2 | A e | + 2 ,
then u e 2 2 | A e | + 2 b   . Hence
H + 1 = 2 | A | 1 + l o 2 | A e |
2 | A | 1 + l o + 2 ( b u e 2 + | A e | 2 )
= 2 | A | 1 + 2 b + ( l o u e + 2 | A e | 4 )
< 2 | A | 1 + 2 b .
This ends the proof of the lemma.   (Lemma  4.5 )
Lemma 4.6 Suppose A = A e A o   , where A e = A E   is the set of all even numbers in A   and A o = A O   is the set of all odd numbers in A   . Let u i = max A i   for i = e , o   and l o = min A o   .
If (a) u e = H   and u o l o 0   or (b) H = u o   , 0 l o < u e H   , and u e l o 0   , then H + 1 2 | A | 1 + 2 b   .
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 A e   is full in E [ 0 , u e ]   and A o   is full in O [ l o , H ]   . 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 A = E [ 0 , u e ] O [ l o , H ]   . However, this implies | A | = u e 2 + 1 + H l o 2 + 1 = H + ( u e l o ) 2 + 2 > H + 1 2 ,   which contradicts ( IX ).   (Lemma  4.6 )
Lemma 4.7 If A   is a forward triangle from 0   to H   , then H + 1 2 | A | 1 + 2 b   .
Proof: Assume the lemma is not true and we need to derive a contradiction. Clearly we have d ̲ U ( A ) 1 2   . Furthermore we can assume d ̲ U ( A ) 2 3   by the following argument: If d ̲ U ( A ) < 2 3   , then there exists y 0   in A   such that for all 0 y y   ( 2 A ) ( 0 , 2 y ) 2 y = 3 2 3 y 3 A ( 0 , y ) .   If for every x 0   in A   we have gcd ( A [ x , H ] x ) > 1   , then there is a u 0   in A   such that gcd ( A [ u , H ] u ) > 1   by Lemma  2.7 . This implies that for each x 0   we have A ( 0 , x ) 1 2 x   , which contradicts that A [ 0 , H ]   is a forward triangle. Hence we can choose y   with 0 y y   in A   such that gcd ( A [ y , H ] y ) = 1   . By Lemma  2.3 we have | 2 A | 3 | A |   . Let z = max { x U : A ( 0 , x 1 ) 1 2 x } .   Note that the smallest possible value of z   is 0   . Note also that z   is well defined because d ̲ U ( A ) 2 3   . It is easy to check that z A   , A ( 0 , z 1 ) = 1 2 z   , and for every x z   in U   we have A ( z , x ) > 1 2 ( x z + 1 )   by the maximality of z   .
Define a   by a = min { x [ z , H ] : A ( z , x ) 1 2 ( x z + 1 ) } .   The number a   is well defined by the fact that A ( 0 , z 1 ) = 1 2 z   , H A   , and | A | 1 2 ( H + 1 )   .
It is also easy to check that a H   , A [ z , a ]   is a forward triangle from z   to a   , a A   , and A ( z , a ) = 1 2 ( a z + 1 )   . If z x < a   , then A ( z , x ) > 1 2 ( x z + 1 )   by the minimality of a   .
Let a = max ( A [ z , a ] )   .
Claim  4.7 .1: [ z , a + z 1 ] ( 2 A )   .
Proof of Claim  4.7 .1: Let x [ z , a + z 1 ]   . If x < 2 z   , then x H a   . Hence A ( 0 , x ) = A ( 0 , z 1 ) + A ( z , x ) > 1 2 z + 1 2 ( x z + 1 ) = 1 2 ( x + 1 ) .   This implies A [ 0 , x ] ( x A [ 0 , x ] )   . Hence x ( 2 A )   . If x 2 z   , then A ( z , x z ) > 1 2 ( x 2 z + 1 )   . Hence A [ z , x z ] ( x A [ z , x z ] )   . This again implies x ( 2 A )   .
  (Claim  4.7 .1) Let c = min ( A [ a + 1 , H ] )   . If 2 a < c   , then a + H a + c 2 c   . Hence A   is a subset of the b.p. [ 0 , a ] [ c , H ]   . So from now on in this lemma we can assume 2 a c   .
Claim  4.7 .2: Suppose 2 a a + z   and a + z < x min { 2 a , c + z }   . If ( 2 A ) ( a + z , x 1 ) < 1 2 ( x a z )   , then x ( 2 A )   .
Proof of Claim  4.7 .2: Since A ( z , a ) = 1 2 ( a z + 1 )   and A ( a + 1 , a ) =   , then
A ( z + a a , a ) = A ( z , a ) A ( z , z + a a 1 )
1 2 ( a z + 1 ) ( a a ) = 1 2 ( 2 a z a + 1 ) .
Note that x a a   . Since a + A [ a + z a , x 1 a ] ( 2 A ) [ a + z , x 1 ]   , then A ( a + z a , x 1 a ) < 1 2 ( x a z )   . Hence
A ( x a , a ) = A ( a + z a , a ) A ( a + z a , x a 1 )
> 1 2 ( 2 a z a + 1 ) 1 2 ( x a z ) = 1 2 ( 2 a x + 1 ) .
This shows that A [ x a , a ] ( x A [ x a , a ] )   , which implies x ( 2 A )   .   (Claim  4.7 .2) Let S = ( 2 A ) [ 0 , z 1 ] \ A [ 0 , z 1 ]   .
Claim  4.7 .3: Suppose 2 a < c + z   and max { a + z , 2 a } x < c + z 1   . If ( 2 A ) ( x + 1 , c + z 1 ) < 1 2 ( c + z x 1 )   , then x ( 2 A )   or x c S   .
Proof of Claim  4.7 .3: Assume ( 2 A ) ( x + 1 , c + z 1 ) < 1 2 ( c + z x 1 )   . Since c + A [ x + 1 c , z 1 ] ( 2 A ) [ x + 1 , c + z 1 ]   , then A ( x + 1 c , z 1 ) < 1 2 ( c + z x 1 )   . Hence
A ( 0 , x c ) = A ( 0 , z 1 ) A ( x + 1 c , z 1 )
> 1 2 z 1 2 ( c + z x 1 ) = 1 2 ( x c + 1 ) .
Hence A [ 0 , x c ] ( x c A [ 0 , x c ] )   . This shows x c ( 2 A ) [ 0 , z 1 ]   . If x c A [ 0 , z 1 ]   , then x c + A [ 0 , z 1 ] ( 2 A )   . If x c A [ 0 , z 1 ]   , then x c S   .
  (Claim  4.7 .3) Claim  4.7 .4: ( 2 A ) ( 0 , c + z ) 3 A ( 0 , z 1 ) + 2 A ( z , a ) 1 + 1 2 ( c a + 1 )   .
Proof of Claim  4.7 .4: The proof is divided into three cases for 2 a c + z   , 2 a a + z   , and a + z < 2 a < c + z   .
Case  4.7 .4.1: 2 a c + z   .
By Claim  4.7 .2 we have ( 2 A ) ( a + z , c + z 1 ) 1 2 ( c a 1 )   (this can be proven by induction on x [ a + z , c + z 1 ]   ). Hence ( 2 A ) ( a + z , c + z ) 1 2 ( c a + 1 )   because c + z ( 2 A )   . So we have
( 2 A ) ( 0 , c + z )
= ( 2 A ) ( 0 , z 1 ) + ( 2 A ) ( z , a + z 1 ) + ( 2 A ) ( a + z , c + z )
A ( 0 , z 1 ) + a + 1 2 ( c a + 1 )
= 3 A ( 0 , z 1 ) + 2 A ( z , a ) 1 + 1 2 ( c a + 1 ) .
  (Case  4.7 .4.1) Case  4.7 .4.2: 2 a a + z   .
By Claim  4.7 .3 we have ( 2 A ) ( a + z , c + z ) 1 2 ( c a + 1 ) | S |   . Hence
( 2 A ) ( 0 , c + z ) = ( 2 A ) ( 0 , z 1 ) + a + ( 2 A ) ( a + z , c + z )
A ( 0 , z 1 ) + | S | + 2 A ( 0 , z 1 )
+ 2 A ( z , a ) 1 + 1 2 ( c a + 1 ) | S |
= 3 A ( 0 , z 1 ) + 2 A ( z , a ) 1 + 1 2 ( c a + 1 ) .
  (Case  4.7 .4.2) Case  4.7 .4.3: a + z < 2 a < c + z   .
By Claim  4.7 .2 we have ( 2 A ) ( a + z , 2 a ) 1 2 ( 2 a a z + 1 )   and by Claim  4.7 .3 we have ( 2 A ) ( 2 a + 1 , c + z ) 1 2 ( c + z 2 a ) | S |   . Hence
( 2 A ) ( 0 , c + z ) = A ( 0 , z 1 ) + | S | + 2 A ( 0 , z 1 )
+ 2 A ( z , a ) 1 + ( 2 A ) ( a + z , 2 a ) + ( 2 A ) ( 2 a + 1 , c + z )
3 A ( 0 , z 1 ) + 2 A ( z , a ) 1 + 1 2 ( 2 a a z + 1 ) + 1 2 ( c + z 2 a )
3 A ( 0 , z 1 ) + 2 A ( z , a ) 1 + 1 2 ( c a + 1 ) .
  (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 H c 2 A ( c + 1 , H ) = 2 A ( c , H ) 2   .
Since c z + A ( c , H ) A ( z , c ) + 2 A ( c , H ) 2   , then by Theorem  A.4 we have | A [ z , c ] + A [ c , H ] | A ( z , c ) + 2 A ( c , H ) 2   . Hence
3 | A | 3 + b = | 2 A |
( 2 A ) ( 0 , c + z ) 1 + | A [ z , c ] + A [ c , H ] | + | H + A [ c + 1 , H ] |
3 A ( 0 , z 1 ) + 2 A ( z , a ) 1 + 1 2 ( c a + 1 ) 1
+ A ( z , c ) + 2 A ( c , H ) 2 + A ( c + 1 , H )
= 3 A ( 0 , z 1 ) + 3 A ( z , a ) + 3 A ( c , H ) 4 + 1 2 ( c a + 1 )
= 3 | A | 3 + 1 2 ( c a 1 ) .
This shows 1 2 ( c a 1 ) b   . Hence
H + 1 = H c + c a 1 + a z + z + 2
2 A ( c , H ) 2 + 2 b + 2 A ( z , a ) 1 + 2 A ( 0 , z 1 ) + 2
= 2 | A | 1 + 2 b .
  (Case  4.7 .1) Case  4.7 .2 H c 2 A ( c + 1 , H ) + 1 = 2 A ( c , H ) 1   .
Note that Case  4.7 .1 covers the case for c = H   . So we can assume c < H   . First we prove a claim.
Claim  4.7 .2.1 If ( 2 A ) ( c + z , 2 H ) 1 2 ( H c ) + A ( c , H ) + A ( z , H ) 1   , then H + 1 2 | A | 1 + 2 b   .
Proof of Claim  4.7 .2.1 By the assumption we have
3 | A | 3 + b = | 2 A |
3 A ( 0 , z 1 ) + 2 A ( z , a ) 1 + 1 2 ( c a + 1 ) + ( 2 A ) ( c + z , 2 H ) 1
3 A ( 0 , z 1 ) + 2 A ( z , a ) 1 + 1 2 ( c a + 1 )
+ 1 2 ( H c ) + A ( c , H ) + A ( z , H ) 2
3 | A | 3 + 1 2 ( H c ) A ( c , H ) + 1 2 ( c a + 1 ) .
Hence 1 2 ( H c ) A ( c , H ) + 1 2 ( c a + 1 ) b   . This implies
H + 1 = H c + c a + 1 + a z + z
2 ( b + A ( c , H ) ) + 2 A ( z , a ) 1 + 2 A ( 0 , z 1 )
= 2 | A | 1 + 2 b .
  (Claim  4.7 .2.1) By Claim  4.7 .2.1 we need only to show that ( 2 A ) ( c + z , 2 H ) 1 2 ( H c ) + A ( c , H ) + A ( z , H ) 1   is true. We divide the proof into cases according to the structural properties of A [ c , H ]   .
Subcase  4.7 .2.1 gcd ( A [ c , H ] c ) = 1   .
Note that c H   and c H 1   by the condition of Case  4.7 .2. Since gcd ( A [ c , H ] c ) = 1   , then A ( c , H ) 3   and H c 2 A ( c + 1 , H ) + 1 5   . Since d ̲ U ( A ) 2 3   , there is a t U   such that for all u t   in U   we have A ( t , u ) u t + 1 2 3   . Let u = t + H c 1   . Then there is a non-negative infinitesimal r   such that A ( t , u ) u t + 1 = A ( t , u ) H c 2 3 r   . By Theorem  A.4 we have
( 2 A ) ( c + z , 2 H ) | A [ c , H ] + A [ z , H ] |
| c + A [ z , t 1 ] | + | A [ c , H ] + A [ t , u ] | + | H + A [ u + 1 , H ] |
A ( z , t 1 ) + min { H c + A ( t , u ) , A ( c , H ) + 2 A ( t , u ) 2 } + A ( u + 1 , H ) .
Since
H c = 1 2 ( H c ) + 1 2 ( H c )
1 2 ( H c ) + 1 2 ( 2 A ( c , H ) 1 )
= 1 2 ( H c ) + A ( c , H ) 1 2
and
A ( t , u ) ( 2 3 r ) ( H c )
1 2 ( H c ) + ( 1 6 r ) ( H c ) 1 2 ( H c ) + 5 6 5 r ,
by the fact that H c 5   , then we have
min { H c + A ( t , u ) , A ( c , H ) + 2 A ( t , u ) 2 }
1 2 ( H c ) + A ( c , H ) + A ( t , u ) 7 6 5 r .
Hence
( 2 A ) ( c + z , 2 H ) | A [ c , H ] + A [ z , H ] |
A ( z , t 1 ) + 1 2 ( H c ) + A ( c , H ) + A ( t , u )
7 6 5 r + A ( u + 1 , H )
= A ( z , H ) + A ( c , H ) + 1 2 ( H c ) 1 ( 1 6 + 5 r ) .
Since ( 2 A ) ( c + z , 2 H )   is an integer, then we have ( 2 A ) ( c + z , 2 H ) A ( z , H ) + A ( c , H ) + 1 2 ( H c ) 1 .   Now the lemma follows from Claim  4.7 .2.1.   (Subcase  4.7 .2.1) Subcase  4.7 .2.2 gcd ( A [ c , H ] c ) = d > 1   but d 3   .
Again let t U A   be such that A ( t , u ) u t + 1 3 2   for all u t   in U   .
Claim  4.7 .2.2.1 For each x A [ c , H ]   , ( 2 A ) ( t + c , t + x 1 ) A ( c , x 1 ) + 1 2 ( x c )   .
Proof of Claim  4.7 .2.2.1: We prove the claim by induction on x c   .
The case of x = c   is trivially true.
Suppose the claim is true for y A [ c , H 1 ]   . Let x = min A [ y + 1 , H ]   . Since [ y + 1 , x 1 ] A =   , and x y = n d   for some n > 0   implies x y = 2   or x y 4   , then
( 2 A ) ( t + y , t + x 1 ) | y + A [ t , t + ( x y ) 1 ] |
= A ( t , t + ( x y ) 1 ) ( 2 3 r ) ( x y )
= 1 2 ( x y ) + ( 1 6 r ) ( x y ) ,
for some non-negative infinitesimal r   . Since either x y = 2   or x y > 3   , and ( 2 A ) ( t + y , t + x 1 )   is an integer, then we have ( 2 A ) ( t + y , t + x 1 ) 1 2 ( x y ) + 1 = 1 2 ( x y ) + A ( y , x 1 ) .   Hence
( 2 A ) ( t + c , t + x 1 )
= ( 2 A ) ( t + c , t + y 1 ) + ( 2 A ) ( t + y , t + x 1 )
A ( c , y 1 ) + 1 2 ( y c ) + 1 2 ( x y ) + A ( y , x 1 )
= A ( c , x 1 ) + 1 2 ( x c ) .
  (Claim  4.7 .2.2.1) Following Claim  4.7 .2.2.1 we now have
( 2 A ) ( t + c , t + H ) = ( 2 A ) ( t + c , t + H 1 ) + 1
A ( c , H 1 ) + 1 2 ( H c ) + 1 = A ( c , H ) + 1 2 ( H c ) .
This implies
( 2 A ) ( c + z , 2 H ) | A [ c , H ] + A [ z , H ] |
| c + A [ z , t 1 ] | + ( 2 A ) ( t + c , t + H ) + | H + A [ t + 1 , H ] |
A ( z , t 1 ) + 1 2 ( H c ) + A ( c , H ) + A ( t + 1 , H )
= 1 2 ( H c ) + A ( c , H ) + A ( z , H ) 1 .
Now the lemma follows from Claim  4.7 .2.1.   (Subcase  4.7 .2.2) Subcase  4.7 .2.3 gcd ( A [ c , H ] c ) = 3   .
Note that t , t + 1 A   . Suppose { x A [ z , a ] : x t 2 ( mod 3 ) } =   . If c { t , t + 1 } ( mod 3 )   , then A [ z , H ]   is a subset of the b.p. ( t ± ( 3 * * N ) ) ( t + 1 ± ( 3 * * N ) )   .
Hence the lemma follows from Lemma  4.2 . So we can assume that c { t , t + 1 } ( mod 3 )   .
This implies ( A [ c , H ] + A [ c , H ] ) ( A [ c , H ] + A [ z , a ] ) =   and hence
| A [ c , H ] + A [ z , H ] |
| c + A [ z , z + H c 1 ] | + | H + A [ z , a ] | + | A [ c , H ] + A [ c , H ] |
A ( z , z + H c 1 ) + A ( z , a ) + 2 A ( c , H ) 1
1 2 ( H c ) + A ( c , H ) + A ( z , H ) 1 .
Now the lemma follows from Claim  4.7 .2.1. So we can assume { x A [ z , a ] : x t 2 ( mod 3 ) } .   Suppose { x A [ t , u ] : x t 2 ( mod 3 ) } =   , where u = t + H c 1   .
If { x A [ z , t 1 ] : x t 2 ( mod 3 ) }   , let k = max { x A [ z , t 1 ] : x t 2 ( mod 3 ) } .   Then ( k + A [ c + 1 , H ] ) ( c + A [ z , t 1 ] ) =   and ( k + A [ c + 1 , H ] ) ( A [ c , H ] + A [ t , u ] ) =   .
Hence
( 2 A ) ( c + z , 2 H )
| c + A [ z , t 1 ] | + | A [ c , H ] + A [ t , u ] | + | k + A [ c + 1 , H ] | + | H + A [ u + 1 , H ] |
A ( z , t 1 ) + | c + A [ t , u ] | + | H + A [ t , u ] | + A ( c + 1 , H ) + A ( u + 1 , H )
A ( z , t 1 ) + 2 A ( t , u ) + A ( c , H ) 1 + A ( u + 1 , H )
A ( z , H ) + A ( c , H ) + 1 2 ( u t + 1 ) 1
= 1 2 ( H c ) + A ( c , H ) + A ( z , H ) 1 .
Now the lemma follows from Claim  4.7 .2.1.
If { x A [ z , u ] : x t 2 ( mod 3 ) } =   , let k = min { x A [ u + 1 , a ] : x t 2 ( mod 3 ) }   .
Then ( k + A [ c , H ] ) ( A [ c , H ] + A [ z , k 1 ] ) =   . Hence
( 2 A ) ( c + z , 2 H ) | A [ c , H ] + A [ z , H ] |
| c + A [ z , t 1 ] | + | A [ c , H ] + A [ t , u ] | + | H + A [ u + 1 , k 1 ] |
+ | k + A [ c , H ] | + | H + A [ k + 1 , H ] |
A ( z , t 1 ) + | c + A [ t , u ] | + | H + A [ t , u ] |
+ A ( u + 1 , k 1 ) + A ( c , H ) + A ( k + 1 , H )
A ( z , t 1 ) + 2 A ( t , u ) + A ( u + 1 , k 1 ) + A ( c , H ) + A ( k + 1 , H )
A ( z , H ) 1 + A ( c , H ) + 1 2 ( u t + 1 )
= 1 2 ( H c ) + A ( c , H ) + A ( z , H ) 1 .
This implies the lemma.
Now we can assume that { x A [ t , u ] : x t 2 ( mod 3 ) }   . For i = 0 , 1 , 2   let A i = { x A [ t , u ] : x t i ( mod 3 ) } .   Clearly A i   for i = 0 , 1 , 2   . By Theorem  A.4 , | A [ c , H ] + A i | min { 1 3 ( H c ) + | A i | , A ( c , H ) + 2 | A i | 2 } .   Let Q = | A [ c , H ] + A [ t , u ] | = i = 0 2 | A [ c , H ] + A i |   . Note that each term | A [ c , H ] + A i |   in the sum has two possible lower bounds 1 3 ( H c ) + | A i |   or A ( c , H ) + 2 | A i | 2   . We divide the proof into the cases according to the different combinations of these lower bounds of | A [ c , H ] + A i |   for i = 0 , 1 , 2   .
Subsubcase  4.7 .2.3.1 Q i = 0 2 ( 1 3 ( H c ) + | A i | )   .
Together with the assumption of Case  4.7 .2, this subsubcase implies Q H c + A ( t , u ) 1 2 ( H c ) + A ( c , H ) 1 2 + A ( t , u ) .   Hence
( 2 A ) ( c + z , 2 H ) | A [ c , H ] + A [ z , H ] |
| c + A [ z , t 1 ] | + Q + | H + A [ u + 1 , H ] |
A ( z , t 1 ) + 1 2 ( H c ) + A ( c , H ) 1 2 + A ( t , u ) + A ( u + 1 , H )
1 2 ( H c ) + A ( c , H ) + A ( z , H ) 1 .
Now the lemma follows from Claim  4.7 .2.1.   (Subsubcase  4.7 .2.3.1) Subsubcase  4.7 .2.3.2 Q i = 0 1 ( 1 3 ( H c ) + | A i | ) + A ( c , H ) + 2 | A 2 | 2   .
Then Q 2 3 ( H c ) + A ( t , u ) + A ( c , H ) + | A 2 | 2   . Hence
( 2 A ) ( c + z , 2 H ) | A [ c , H ] + A [ z , H ] |
| c + A [ z , t 1 ] | + Q + | H + A [ u + 1 , H ] |
A ( z , t 1 ) + 2 3 ( H c ) + A ( t , u ) + A ( c , H ) + | A 2 | 2 + A ( u + 1 , H )
> 1 2 ( H c ) + A ( c , H ) + A ( z , H ) 1 .
  (Subsubcase  4.7 .2.3.2) Subsubcase  4.7 .2.3.3 Q ( 1 3 ( H c ) + | A 0 | ) + i = 1 2 ( A ( c , H ) + 2 | A i | 2 )   .
If H c = 3   , then A ( c , H ) = 2   and A [ t , u ] = { t , t + 1 , t + 2 }   . Hence | A [ c , H ] + A i | = 2 = 1 3 ( H c ) + | A i |   , which implies the assumption of Subsubcase  4.7 .2.3.1. So we can assume H c 6   and A ( c , H ) 3   . Since A ( t , u ) ( 2 3 r ) ( H c )   and | A 0 | 1 3 ( H c )   , then | A 1 | + | A 2 | ( 1 3 r ) ( H c )   for some non-negative infinitesimal r   . Hence
Q 1 3 ( H c ) + A ( t , u ) + 2 A ( c , H ) + | A 1 | + | A 2 | 4
1 2 ( H c ) + ( 1 6 r ) ( H c ) + A ( t , u ) + 2 A ( c , H ) 4
1 2 ( H c ) + ( 1 6 r ) ( H c ) + A ( t , u ) + A ( c , H ) 1
> 1 2 ( H c ) + A ( t , u ) + A ( c , H ) 1 .
Hence again ( 2 A ) ( c + z , 2 H ) | A [ c , H ] + A [ z , H ] | 1 2 ( H c ) + A ( c , H ) + A ( z , H ) 1 .     (Subsubcase  4.7 .2.3.3) Subsubcase  4.7 .2.3.4 Q i = 0 2 ( A ( c , H ) + 2 | A i | 2 )   .
Again we can assume H c 6   and A ( c , H ) 3   . Then
Q 3 A ( c , H ) + 2 A ( t , u ) 6
A ( t , u ) + 1 2 ( H c ) + A ( c , H ) ,
for some non-negative infinitesimal r   . Hence Q > A ( t , u ) + 1 2 ( H c ) + A ( c , H ) 1   . This implies ( 2 A ) ( c + z , 2 H ) | A [ c , H ] + A [ 0 , H ] | 1 2 ( H c ) + A ( c , H ) + A ( z , H ) 1 ,   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 0 s H   such that A [ 0 , s ]   is a backward triangle from 0   to s   and A [ s + 1 , H ]   is a forward triangle from s + 1   to H   . Then H + 1 2 | A | 1 + 2 b   .
Proof: Let u = min { x : s 2 < x < s + H 2 and A ( 0 , x ) 1 2 ( x + 1 ) } .   Clearly u s   because A [ 0 , s ]   is a backward triangle. Also u s   because otherwise A ( 0 , u ) A ( 0 , s ) + A ( s , u ) 1 2 s + 1 2 ( u s ) 1 2 u .   Hence we have u s   . It is easy to see that u A   and A ( 0 , u ) = 1 2 ( u + 1 )   by the minimality of u   . Also by the minimality of u   we have that for any 0 x u   , A ( x , u ) > 1 2 ( u x + 1 )   .
Let X = { x : u + 1 x < u + H 2 and A ( u + 1 , x ) 1 2 ( x u ) } .   If X   , let z = 1 + max X   . Otherwise let z = u + 1   . It is also easy to see that z A   , z u   , and A ( u + 1 , z 1 ) = 1 2 ( z u 1 )   . Since A ( 0 , z 1 ) = 1 2 z   , A ( 0 , H ) 1 2 ( H + 1 )   , and H A   , then the number a   below is well defined.
a = min { x : z x < H and A ( z , x ) 1 2 ( x z + 1 ) } .   Clearly a < H   , a H   , a A   , and A ( z , a ) = 1 2 ( a z + 1 )   . By the minimality we have that for any z x < a   , A ( z , x ) > 1 2 ( x z + 1 )   . Now let a = max ( A [ z , a 1 ] )   and c = min ( A [ a , H ] )   .
Since a z + H 2   and z 0   , then 2 a c   . Let S = ( 2 A ) [ 0 , z 1 ] \ A [ 0 , z 1 ]   .
Without loss of generality we can assume that A [ z , H ]   is not a subset of a b.p. of difference 3   by the following reason:
Suppose not. By symmetry, we can also assume that there is a z z   such that A [ 0 , z ]   is a subset of a b.p. of difference 3   . 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: [ z , a + z 1 ] ( 2 A )   .
Proof of Claim  4.8 .1: The proof here is slightly different from the proof of Claim  4.7 .1.
If 2 z x < a + z   , then z x z < a   . Hence A ( z , x z ) > 1 2 ( x 2 z + 1 )   . This implies A [ z , x z ] ( x A [ z , x z ] )   . Hence x ( 2 A )   . Suppose z x < 2 z   . Then 0 x z < z   .
If 0 x z u   , then A ( x z , z ) = A ( x z , u ) + A ( u + 1 , z ) > 1 2 ( u x + z + 1 ) + 1 2 ( z u 1 ) + 1 > 1 2 ( 2 z x + 1 )   . Hence A [ x z , z ] ( x A [ x z , z ] )   , which implies x ( 2 A )   . If u < x z < z   , then by choosing a y 0   with y min { a z , u }   we have A ( x z y , x z ) + A ( z , z + y ) y + 1   . Hence A [ x z y , x z ] ( x A [ z , z + y ] )   , which implies x ( 2 A )   . Suppose x z 0   . If A ( 0 , x z ) 1 2 ( x z + 1 )   , then by A ( z , x ) > 1 2 ( x z + 1 )   we have A [ 0 , x z ] ( x A [ z , x ] )   , which implies x ( 2 A )   . If A ( 0 , x z ) < 1 2 ( x z + 1 )   , then A ( x z + 1 , z 1 ) > 1 2 ( 2 z x 1 )   . Hence A [ x z + 1 , z 1 ] ( x A [ x z + 1 , z 1 ] )   , which again implies x ( 2 A )   .   (Claim  4.8 .1) Claim  4.8 .2: Suppose 2 a > a + z   and a + z < x min { 2 a , c + z }   . If ( 2 A ) ( a + z , x 1 ) < 1 2 ( x a z )   , then x 2 A   .
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 2 a < c + z   and max { a + z , 2 a } x < c + z 1   . If ( 2 A ) ( x + 1 , c + z 1 ) < 1 2 ( c + z x 1 )   , then x ( 2 A )   or x c S   .
Proof of Claim  4.8 .3: Identical to the proof of Claim  4.7 .3.   (Claim  4.8 .3) Claim  4.8 .4: ( 2 A ) ( 0 , c + z ) 3 A ( 0 , z 1 ) + 2 A ( z , a ) 1 + 1 2 ( c a + 1 )   .
Proof of Claim  4.8 .4: The proof is divided into three cases for 2 a c + z   , 2 a a + z   , and a + z < 2 a < c + z   .
Case  4.8 .4.1: 2 a c + z   .
Identical to the proof of Case  4.7 .4.1.   (Case  4.8 .4.1) Case  4.8 .4.2: 2 a a + z   .
Identical to the proof of Case  4.7 .4.2.   (Case  4.8 .4.2) Case  4.8 .4.3: a + z < 2 a < c + z   .
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 H c 2 A ( c + 1 , H ) = 2 A ( c , H ) 2   .
Identical to the proof of Case  4.7 .1.   (Case  4.8 .1) Case  4.8 .2 H c 2 A ( c + 1 , H ) + 1 = 2 A ( c , H ) 1   .
Claim  4.8 .2.1 If ( 2 A ) ( c + z , 2 H ) 1 2 ( H c ) + A ( c , H ) + A ( z , H ) 1   , then H + 1 2 | A | 1 + 2 b   .
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 ( 2 A ) ( c + z , 2 H ) 1 2 ( H c ) + A ( c , H ) + A ( z , H ) 1   is true. We divide the proof into cases according to the structural properties of A [ c , H ]   .
Subcase  4.8 .2.1 gcd ( A [ c , H ] c ) = 1   .
The proof is the same as the proof of Subcase  4.7 .2.1 except that the term U   needs to be replaced by the term z + U   throughout the remaining of the proof of the lemma. Note that we can also assume that d ̲ z + U 2 3   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 gcd ( A [ c , H ] c ) = d > 1   but d 3   .
Claim  4.8 .2.2.1 For each x A [ c , H ]   , ( 2 A ) ( t + c , t + x 1 ) A ( c , x 1 ) + 1 2 ( x c )   .
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
( 2 A ) ( t + c , t + H ) = ( 2 A ) ( t + c , t + H 1 ) + 1
A ( c , H 1 ) + 1 2 ( H c ) + 1 = A ( c , H ) + 1 2 ( H c ) .
This implies
( 2 A ) ( c + z , 2 H ) | A [ c , H ] + A [ z , H ] |
| c + A [ z , t 1 ] | + ( 2 A ) ( t + c , t + H ) + | H + A [ t + 1 , H ] |
A ( z , t 1 ) + 1 2 ( H c ) + A ( c , H ) + A ( t + 1 , H )
= 1 2 ( H c ) + A ( c , H ) + A ( z , H ) 1 .
Now the lemma follows from Claim  4.8 .2.1.   (Subcase  4.8 .2.2) Subcase  4.8 .2.3 gcd ( A [ c , H ] c ) = 3   .
the proof is identical to the proof of Subcase  4.7 .2.3. Note that we assume { x A [ z , a ] : x t 2 ( mod 3 ) }   in the beginning of the proof of this lemma.   (Lemma  4.8 )
Lemma 4.9 Suppose A = A [ 0 , s ] A [ s + 1 , H ]   with 0 s H   such that A [ 0 , s ]   is a backward triangle and A [ s + 1 , H ]   is a subset of an a.p. of difference d > 1   . Then H + 1 2 | A | 1 + 2 b   .
Proof: Since ( V ), we have A ( s + 1 , H ) 1 2 ( H s )   , which implies d = 2   . Let E   be the set of all even numbers and let c = min A [ s + 1 , H ]   . Then c s   and A [ c , H ]   is full. Without loss of generality we can assume that s A   and c s   is odd. By the pigeonhole principle and Lemma  2.7 we can find e 2 c   and e 2 H   such that E [ e , e ] = ( A [ c , H ] + A [ c , H ] ) [ e , e ]   .
Claim  4.9 .1: If s x s + H   , then x 2 A   .
Proof of Claim  4.9 .1: If s x 2 s   , then 0 x s s   . Hence A ( x s , s ) 1 2 ( 2 s x + 1 )   . So A [ x s , s ] ( x A [ x s , s ] )   , which implies x 2 A   . Now we assume 2 s x s + H   . Let z 1 = [ x 2 ]   . Then 2 z 1 x s + H   implies z 1 s H z 1   . Choose a y   with z 1 s y min { H z 1 , z 1 }   . Then 0 z 1 y s   . Hence
A ( z 1 y , z 1 ) A ( z 1 y , s ) + A ( s + 1 , z 1 )
1 2 ( s z 1 + y + 1 ) + 1 2 ( z 1 s ) = 1 2 ( y + 1 )
and A ( x z 1 , x z 1 + y ) 1 2 ( y + 1 )   . Hence A [ z 1 y , z 1 ] ( x A [ x z 1 , x z 1 + y ] )   , which implies x 2 A   .   (Claim  4.9 .1) Now let's assume that the lemma is not true. Let A [ 0 , H ]   be the set with the largest cardinality | A |   such that A [ s + 1 , H ] A [ s + 1 , H ] ( s + 1 + E )   , A [ 0 , s ] = A [ 0 , s ]   , and satisfying ( VII ), ( IX ), and ( X ) with A   replaced by A   and b   replaced by b   . We will derive a contradiction.
Claim  4.9 .2: A [ s + 1 , H ] = ( s + 1 + E ) [ s + 1 , H ]   .
Proof of Claim  4.9 .2: The proof is divided into three cases. Let x ( s + 1 + E )   be such that s + 1 x H   . We want to show that x A   .
Case  4.9 .2.1 s x s + H 2   .
Suppose x A   . Let A = A { x }   . For each y A [ s + 1 , H ] { x }   , x + y E [ e , e ] 2 A 2 A   , and for each y A [ 0 , s ]   we have s x + y s + s + H 2   , which implies s x + y s + H   . Hence x + y 2 A 2 A   by Claim  4.9 .1. So 2 A = 2 A   , which contradict the maximality of | A |   by Lemma  4.1 .   (Case  4.9 .2.1) Case  4.9 .2.2: x s + 1   and x s + 1   .
Suppose x A   . Without loss of generality we can, by Case  4.9 .2.1, assume x = max ( ( s + 1 + E ) [ s + 1 , 3 s + H 4 ] \ A ) .   Let y A = A { x }   .
If 0 y s   , then A ( y + 1 , s ) 1 2 ( s y )   and A ( x ( s y ) , x 1 ) 1 2 ( s y )   . Hence A [ y + 1 , s ] ( x + y A [ x ( s y ) , x 1 ] )   , which implies x + y A [ y + 1 , s ] + A [ x ( s y ) , x 1 ] ( 2 A )   . If y s   and y x   , then choose a z y   such that y z H s   . Hence A ( z , y 1 ) 1 2 ( y z )   and A ( x + 1 , x + ( y z ) ) 1 2 ( y z )   imply A [ z , y 1 ] ( x + y A [ x + 1 , x + ( y z ) ] )   , which implies x + y ( 2 A ) ( 2 A )   .
If x < y H   , then choose a z   with H z y   such that z y s   . Hence A ( y + 1 , z ) 1 2 ( z y )   and A ( x ( z y ) , x 1 ) 1 2 ( z y )   imply A [ y + 1 , z ] ( x + y A [ x ( z y ) , x 1 ] )   , which implies x + y ( 2 A )   .
If y H   , then y ( s + 1 + E )   . Hence x + y   is even and 2 s x + y 2 H   . Now we have x + y E [ e , e ] ( 2 A )   .
If y 0   , y > 0   , and y   is even, then x + y A   by the maximality of x   . Hence x + y = 0 + ( x + y ) ( 2 A )   .
If y 0   , y   is odd, and y > l = min { z A : z is odd }   , then x + ( y l ) A   . Hence x + y = l + ( x + y l ) ( 2 A )   .
By the arguments above we conclude that ( 2 A ) \ ( 2 A ) { x , x + l }   . Hence | 2 A | | 2 A | + 2   , which contradicts the maximality of | A |   by Lemma  4.1 . So we conclude that x A   .   (Case  4.9 .2.2) Case  4.9 .2.3: s + H 2 x H   .
Suppose again x A   . Let x = min ( A [ 3 s + H 4 , H ] )   . By Case  4.9 .2.1 we have x s + H 2   .
Let y A   .
If s + 1 y H   , then x + y E [ e , e ] ( 2 A )   .
If 0 y s   , then s x + y s + H   , which implies, by Claim  4.9 .1, x + y 2 A   .
If y < H   and y H   , then x ( H y ) A   by the minimality of x   . Hence x + y = H + ( x H + y ) 2 A   .
If y < s   , y s   , and s y   is odd, then s + 1 y   is even and x ( s + 1 y ) A   by the minimality of x   . Hence x + y = s + 1 + ( x s 1 + y ) 2 A   .
If y < s   , y s   , and s y   is even, then x ( s y ) A   . Hence x + y = s + ( x s + y ) 2 A   .
By the arguments above we conclude that ( 2 A ) \ ( 2 A ) { s + x , x + H }   , which contradicts the maximality of | A |   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 A   is already in the form of the set A   in Claim  4.9 .2. Let u = min ( { z A [ s + 1 , H ] : A [ 0 , z ] is not a subset of a b.p. } )   . Note that if there is a v s   such that A [ 0 , v ]   is a subset of a b.p. of difference d   , then | 2 A | 3 | A |   implies that A [ 0 , v ]   is full in the b.p. Hence d = 1   or d = 3   because A [ 0 , s ]   is a backward triangle. However, A [ s + 1 , v ]   is a full subset of an a.p. of difference 2   , which contradicts d = 1   or d = 3   . Hence we have u s   . By ( IX ) and A ( u , H ) = 1 2 ( H u ) + 1   we have A ( 0 , u ) = | A | A ( u , H ) + 1 H + 1 2 H u 2 = 1 2 ( u + 1 )   .
Let | A [ 0 , u ] + A [ 0 , u ] | = 3 A ( 0 , u ) 3 + b ¯   . If b ¯ < 0   , then by Theorem  A.1 we have u + 1 2 A ( 0 , u ) 2 + b ¯ < 2 A ( 0 , u ) 2   , which contradicts A ( 0 , u ) 1 2 ( u + 1 )   . Hence we can assume b ¯ 0   . Clearly b ¯ 0   because otherwise we would have | 2 A | 3 | A |   . By Lemma  4.7 , we have u + 1 2 A ( 0 , u ) 1 + 2 b ¯   . Hence
3 | A | 3 + b = | 2 A |
| A [ 0 , u ] + A [ 0 , u ] | + | s + A [ u + 2 , H ] | + | A [ u + 2 , H ] + A [ u , H ] |
3 A ( 0 , u ) 3 + b ¯ + A ( u + 2 , H ) + 2 A ( u + 2 , H )
= 3 | A | 3 + b ¯ .
Above shows b ¯ b   . Hence
H + 1 = H u + u + 1
2 A ( u + 2 , H ) + 2 A ( 0 , u ) 1 + 2 b ¯
= 2 | A | 1 + 2 b ¯ 2 | A | 1 + 2 b ,
which contradicts H + 1 > 2 | A | 1 + 2 b   .   (Lemma  4.9 )
Lemma 4.10 If d ̲ U ( A ) > 1 2   , then H + 1 2 | A | 1 + 2 b   .
Proof: If d ̲ U ( A ) > 1 2   , then there exists a x 0   such that A [ 0 , x ]   is a forward triangle. If x H   , then the lemma now follows from Lemma  4.7 . If x H   , then the lemma follows from Lemma  3.5 .   (Lemma  4.10 )
Lemma 4.11 Let d ̲ U ( A ) = 1 2   . If there is a x 0   in A   such that gcd ( A [ x , H ] x ) = 1   , then A U   is either a subset of an a.p. of difference > 1   or a subset of a U   –unbounded b.p.
Proof: The lemma follows from Lemma  2.4 and Lemma  2.2 .   (Lemma  4.11 )
Lemma 4.12 Let d ̲ U ( A ) = 1 2   . If A U   is a subset of a U   –unbounded b.p., then H + 1 2 | A | 1 + 2 b   .
Proof: Suppose A U   is a subset of a U   –unbounded b.p. of difference d   . Since d ̲ U ( A ) = 1 2   , then d = 3   or d = 4   . Let I 0 = d * * N   and I 1 = c + ( d * * N )   where c = min { z A : z 0 ( mod d ) }   . Then A U I 0 I 1   . Since d = 3   or d = 4   , then gcd ( c , d ) = 1   . By Lemma  4.6 we can assume that there is an a 0   in A   such that gcd ( A [ a , H ] a ) = 1   .
Case  4.12 .1: d = 3   .
We want to show this case implies | 2 A | 3 | A |   , hence d = 3   is impossible.
By Lemma  2.4 it suffices to show that for γ = 1 25   and for every N 0   there is a K A   with 0 K N   such that ( III ) is true. Suppose N 0   is given. Let 0 < ε < 1 12   . Without loss of generality we can re-choose a   so that a N   , A [ 0 , a ] I 0 I 1   , and for every 0 y a   we have A ( 0 , y ) ( 1 2 ε ) y   . Choose a x   with 0 x 1 2 a   such that A ( 0 , x ) ( 1 2 + ε ) x   .
Let K = min { z x : z , z 1 A }   . It is easy to see that A ( x , K ) 1 3 ( K x )   because for any two consecutive numbers in ( I 0 I 1 ) [ x , K 1 ]   , at least one of them is not in A   .
Hence we have that K 2 x a   and A ( 0 , K ) ( 1 2 + ε ) K   . Note that K , K 1 A   . So the shortest b.p. containing A [ 0 , K ]   must have length L 2 3 K   . Let A i = A [ 0 , K ] I i   for i = 0 , 1   . Since | A 0 | 1 3 K   , then | A 1 | = A ( 0 , K ) | A 0 | ( 1 6 ε ) K   . By the same reason we have | A 0 | ( 1 6 ε ) K   . Let | A [ 0 , K ] + A [ 0 , K ] | = 3 A ( 0 , K ) 3 + b   for some integer b   . Since A [ 0 , K ]   is a subset of a b.p., then b 0   .
If b 1 3 A ( 0 , K ) 3   , then ( 2 A ) ( 0 , 2 K ) 3 A ( 0 , K ) + 1 3 A ( 0 , K ) 3 A ( 0 , K ) + 1 3 ( 1 2 ε ) K ,   which implies ( III ).
If b < 1 3 A ( 0 , K ) 3   , then by Theorem  A.3 we have that 2 3 K L A ( 0 , K ) + b ( 1 2 + ε ) K + b .   Hence b ( 1 6 ε ) K   . So we have ( 2 A ) ( 0 , 2 K ) 3 A ( 0 , K ) + b 3 A ( 0 , K ) + 1 12 K ,   which again implies ( III ). This ends the proof.   (Case  4.12 .1) Case  4.12 .2: d = 4   .
Without loss of generality we assume 0 I 0   and 1 I 1   . Suppose A   is not a subset of a b.p. We want to derive a contradiction. Let c = min { z [ 0 , H ] : A [ 0 , z ] is not a subset of a b.p. of difference 4 } .   Let A [ 0 , c 1 ] = A 0 A 1   where A i = A [ 0 , c 1 ] I i   for i = 0 , 1   . Then | A i | 0   for i = 0 , 1   because otherwise d ̲ U ( A ) 1 4   . Note that since d = 4   , then there is an i = 0   or i = 1   such that ( c + A i ) | A [ 0 , c 1 ] + A [ 0 , c 1 ] | =   . Hence we can assume c H   because otherwise | 2 A | 3 | A | + | c + A i | 3 | A |   .
Subcase  4.12 .2.1: A ( c , H ) 1 2 ( H c )   . By Lemma  2.6 there exist x c y H   such that A [ x , y ]   is a backward triangle and A ( y , H ) 1 2 ( H y + 1 )   .
If x 0   , then the lemma follows from either Lemma  3.5 or Lemma  3.7 . so we can assume x 0   .
If y H   , then the lemma follows from Lemma  4.7 . So we can assume y H   . If for any y y H   in A   , gcd ( A [ y , H ] y ) > 1   , then the lemma follows from Lemma  4.9 . So we can assume that there is a y A   , y y H   such that gcd ( A [ y , H ] y ) = 1   .
If d ̲ y + U ( A ) > 1 2   , then by Lemma  2.6 there is a y z H   such that A [ y , z ]   is a forward triangle. Now the lemma follows from Lemma  4.8 if z H   . If z H   , then by Lemma  3.5  | 2 A | 3 | A |   implies that A [ y , H ]   is a full subset of a b.p. [ y , z ] [ z , H ]   . Hence A [ y , H ]   is the union of a forward triangle A [ y , 2 z y ]   and a backward triangle A [ 2 z y + 1 , H ]   . Now the lemma follows from Lemma  3.4 .
If d ̲ y + U < 1 2   , then by Lemma  2.6 there are y z z H   such that A [ z , z ]   is a backward triangle and A ( z , H ) 1 2 ( H z )   . Now the lemma follows from Lemma  3.5 because A [ 0 , z ]   cannot be a full subset of a b.p. of difference 1   or 3   .
Assume d ̲ y + U ( A ) = 1 2   . Since A [ 0 , y ]   is a backward triangle, then we can assume A ( y , y + 3 ) 3   . Hence ( A y ) U   is neither a subset of an a.p. of difference > 1   nor a subset of a U   –unbounded b.p. of difference d 3   . If ( A y ) U   is a subset of a U   –unbounded b.p. of difference 3   , then by the proof of Case  4.12 .1 we have | A [ y , H ] + A [ y , H ] | 3 A ( y , H )   , which implies | 2 A | 3 | A |   . Note that if there is an y y   in A   such that gcd ( A [ y , H ] y ) = d > 1   , then d = 2   and the lemma follows from Lemma  4.9 . So we can assume that ( A y ) U   is neither a subset of an a.p. of difference > 1   nor a subset of a U   –unbounded b.p. and there is a y y   in A   such that gcd ( A [ y , H ] y ) = 1   . 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: A ( c , H ) 1 2 ( H c )   .
By ( V ) we have A ( c , H ) 1 2 ( H c )   . Since | A 0 A 1 | = A ( 0 , c 1 ) 1 4 c + 1 4 c   and gcd ( A 0 ) = gcd ( A 1 1 ) = 4   , then A i   is full for i = 0 , 1   . Hence we can find a c c   in A   such that gcd ( A [ c , H ] c ) = 1   . Since there is an i { 0 , 1 }   such that ( 2 A ) ( 0 , 2 c ) 3 A ( 0 , c 1 ) + | c + A i | 3 A ( 0 , c )   , then by Lemma  2.3 we have | 2 A | 3 | A |   .   (Lemma  4.12 )
Lemma 4.13 Let d ̲ U ( A ) = 1 2   . If A U   is a subset of an a.p. of difference > 1   , then H + 1 2 | A | 1 + 2 b   .
Proof: Let l o = min { x A : gcd ( A [ 0 , x ] ) = 1 }   . Since d ̲ U ( A ) = 1 2   , then gcd ( A [ 0 , l o 1 ] ) = 2   and l o   is odd.
Case  4.13 .1: There are 0 a c H   such that A [ a , c ]   is a backward triangle and A ( c , H ) 1 2 ( H c )   .
Note that l o c   . By Lemma  3.5 we have either | A [ 0 , c ] + A [ 0 , c ] | 3 A ( 0 , c )   , which is impossible because it implies | 2 A | 3 | A |   by Lemma  2.3 , or A [ 0 , c ]   is a full subset of a b.p.
[ 0 , x ] [ x , c ]   , which contradicts d ̲ U ( A ) = 1 2   , or A [ 0 , c ]   is a full subset of a b.p. of difference 3   , which again contradicts d ̲ U ( A ) = 1 2   .   (Case  4.13 .1) Case  4.13 .2: A ( l o , H ) 1 2 ( H l o )   .
By lemma  2.6 there are 0 y l o y H   such that A ( y , H ) 1 2 ( H y )   and A [ y , y ]   is a backward triangle. Without loss of generality we can assume that A ( y , y + 3 ) 3   . By Case  4.13 .1 we can assume y 0   and by Lemma  4.7 we can assume y H   .
Subcase  4.13 .2.1: d ̲ y + U ( A ) > 1 2   .
By Lemma  2.6 there is a z y   such that A [ y , z ]   is a forward triangle. If z H   , then the lemma follows from Lemma  4.8 . So we can assume z H   . By Lemma  2.3 we can assume | A [ y , H ] + A [ y , H ] | 3 A ( y , H )   . By Lemma  3.5 this implies that A [ y , H ]   is either a full subset of a b.p. of difference 1   or a full subset of a