UPPER AND LOWER BOUNDS ON B_{k}^{+}-SETS

Craig Timmons^{1}

Dept. of Mathematics, University of California San Diego, La Jolla, California ctimmons@ucsd.edu

Received: 11/11/12, Revised: 10/2/13, Accepted: 12/6/13, Published: 1/6/14

Abstract

LetG be an abelian group. A setA⇢Gis a B_{k}^{+}-set if whenevera1+· · ·+ak =
b1+· · ·+bk withai, bj 2A, there is aniand ajsuch thatai=bj. IfAis aBk-set
then it is also a B_{k}^{+}-set, but the converse is not true in general. Determining the
largest size of aBk-set in the interval {1,2, . . . , N}⇢Zor in the cyclic group ZN

is a well-studied problem. In this paper we investigate the corresponding problem
for B_{k}^{+}-sets. We prove nontrivial upper bounds on the maximum size of aB_{k}^{+}-set
contained in the interval {1,2, . . . , N}. For odd k 3, we constructB_{k}^{+}-sets that
have more elements than theB_{k}-sets constructed by Bose and Chowla. We prove
that any B^{+}_{3}-set A ⇢ ZN has at most (1 +o(1))(8N)^{1/3} elements. A set A is a
B^{⇤}_{k}-set if whenevera_{1}+· · ·+a_{k} =a_{k+1}+· · ·+a_{2k} witha_{i}2A, there is ani6=j
such thata_{i} =a_{j}. We obtain new upper bounds on the maximum size of aB_{k}^{⇤}-set
A⇢{1,2, . . . , N}, a problem first investigated by Ruzsa.

1. Introduction

LetGbe an abelian group. A setA⇢Gis aB_{k}^{+}-set if

a1+· · ·+ak =b1+· · ·+bk with a1, . . . , ak, b1, . . . , bk2A (1)
impliesa_{i}=b_{j} for some iandj. A setAis aB_{k}-set if (1) implies (a_{1}, . . . , a_{k}) is a
permutation of (b_{1}, . . . , b_{k}). IfAis aB_{k}-set thenAis also aB_{k}^{+}-set, but in general
the converse is not true. OftenB_{2}-sets are calledSidon sets and have received much
attention since they were first studied by Erd˝os and Tur´an [9] in 1941. LetFk(N)
be the maximum size of a B_{k}-setA⇢[N] and letC_{k}(N) be the maximum size of
aB_{k}-setA⇢ZN. IfA⇢ZN is aB_{k}-set, thenAis also aB_{k}-set when viewed as a
subset ofZ. Thus, for anyk 2,C_{k}(N)F_{k}(N).

Erd˝os and Tur´an provedF_{2}(N)N^{1/2}+O(N^{1/4}). Their argument was used by
Lindstr¨om [13] to showF2(N)N^{1/2}+N^{1/4}+ 1. In 2010, Cilleruelo [5] obtained

1The author was partially supported by NSF Grant DMS-1101489 through Jacques Verstra¨ete.

F2(N)N^{1/2}+N^{1/4}+^{1}_{2} as a consequence of a more general result. This is the best
known upper bound onF_{2}(N). By counting di↵erencesa b witha6=b, it is easy
to prove C_{2}(N)p

N+ 1. There are several constructions of dense B_{2}-sets (see
[17], [2], [16]) that showC2(N) N^{1/2}for infinitely manyN. These constructions
implyF2(N)⇠p

N and lim sup^{C}^{p}^{2}^{(N)}_{N} = 1.

Fork 3, bounds onF_{k}(N) andC_{k}(N) are not as precise. For eachk 2 and
prime power q, Bose and Chowla [2] constructed aBk-setA⇢Zq^{k} 1 with|A|=q
so that

(1 +o(1))N^{1/k}F_{k}(N).

The current upper bounds onF_{k}(N) andC_{k}(N) do not match this lower bound for
anyk 3. IfA⇢[N] is aB_{k}-set then eachk-multiset inAgives rise to a unique sum
in {1, . . . , kN}. Therefore, ^{|A|+k}_{k} ^{1} kN which impliesF_{k}(N) (k!·kN)^{1/k}.
Similar counting shows Ck(N) (k!N)^{1/k}. By considering di↵erences one can
improve these bounds. We illustrate this idea with an example that is relevant to
our results. Let A ⇢ZN be a B_{3}-set. There are ^{|A|}_{2} (|A| 2) sums of the form
a_{1}+a_{2} a_{3} where a_{1}, a_{2}, anda_{3} are distinct elements ofA. Let A^{(2)} ={{x, y}:
x, y 2 A, x 6= y}. It is not hard to check that each n 2 ZN has at most one
representation as n=a1+a2 a3 with{a1, a2}2A^{(2)} anda32A\{a1, a2}. This
implies ^{|A|}_{2} (|A| 2)N so|A|(2N)^{1/3}+ 2. In general, for anyk 2

C_{k}(N)

✓ k 2

⌫

!

⇠k 2

⇡

!N

◆1/k

+O_{k}(1), (2)

and

F_{k}(N)

✓ k 2

⌫

!

⇠k 2

⇡

!·

⇠k 2

⇡ N

◆1/k

+O_{k}(N^{1/2k}). (3)
These bounds were first obtained by Jia [12] in the even case, and Chen [3] in
the odd case. The best upper bounds on Fk(N) are to due to Green [10]. For
every k 2, (3) has been improved (see for example [10] or [4]), but there is no
value ofk 3 for which (2) has been improved. This is interesting since all of the
constructions take place in cyclic groups and provide lower bounds onC_{k}(N). For
other bounds on Bk-sets the interested reader is referred to Green [10], Cilleruelo
[4], O’Bryant’s survey [14], or the book of Halberstam and Roth [11].

Now we discuss B_{k}^{+}-sets. WriteF_{k}^{+}(N) for the maximum size of aB_{k}^{+}-setA ⇢
[N], and C_{k}^{+}(N) for the maximum size of a B^{+}_{k}-set A ⇢ ZN. Ruzsa [16] proved
that a set A⇢[N] with no solution to the equation x_{1}+· · ·+x_{k} =y_{1}+· · ·+y_{k}
in 2k distinct integers has at most (1 +o(1))k^{2 1/k}N^{1/k} elements. Call such a set
a B^{⇤}_{k}-set and define F_{k}^{⇤}(N) in the obvious way. Any B_{k}^{+}-set is also a B_{k}^{⇤}-set so
thatF_{k}^{+}(N)F_{k}^{⇤}(N). Using the constructions of Bose and Chowla [2] and Ruzsa’s
Theorem 5.1 of [16], we get for everyk 3,

(1 +o(1))N^{1/k}F_{k}(N)F_{k}^{+}(N)F_{k}^{⇤}(N)(1 +o(1))k^{2 1/k}N^{1/k}.

In this paper we improve this upper bound on F_{k}^{+}(N) and F_{k}^{⇤}(N). We also
improve this lower bound onF_{k}^{+}(N) for all odd k 3, and we prove a nontrivial
upper bound on C_{3}^{+}(N). We do not consider the case when k = 2. The reason
for this is that Ruzsa [16] provedF_{2}^{⇤}(N)N^{1/2}+ 4N^{1/4}+ 11, and thusF2(N)⇠
F_{2}^{+}(N)⇠F_{2}^{⇤}(N)⇠N^{1/2}. In fact, aB2-set is the same as aB_{2}^{+}-set.

Our first result is a construction which shows that for any oddk 3, there is a
B^{+}_{k}-set in [N] that has more elements than any knownB_{k}-set contained in [N].

Theorem 1.1. For any prime power q and odd integer k 3, there is a B_{k}^{+}-set
A⇢Z2(q^{k} 1)with |A|= 2q.

Using known results on densities of primes (see [1] for example), Theorem 1.1 implies

Corollary 1.2. For any integerN 1and any odd integer k 3,
F_{k}^{+}(N) (1 +o(1))2^{1 1/k}N^{1/k}.

Green provedF3(N)(1 +o(1))(3.5N)^{1/3}. We will use a Bose-ChowlaB3-set to
construct a B_{3}^{+}-setA⇢[2q^{3}] with|A|= 2q= (4·2q^{3})^{1/3}. Putting the two results
together we see thatAis denser than anyB_{3}-set in [2q^{3}] for sufficiently large prime
powersq. Our construction and Green’s upper bound show thatF_{3}(N) andF_{3}^{⇤}(N)
are not asymptotically the same.

The proof of Theorem 1.1 is based on a simple lemma, Lemma 2.1, which implies
2C_{k}(N)C_{k}^{+}(2N) for any odd k 3. (4)
This inequality provides us with a method of estimating C_{k}(N) by proving upper
bounds on C_{k}^{+}(N) for odd k. Our next theorem provides such an estimate when
k= 3.

Theorem 1.3. If A⇢ZN is aB_{3}^{+}-set, then|A|(1 +o(1))(8N)^{1/3}.
Theorem 1.3 and (4) imply

Corollary 1.4. If A⇢ZN is aB3-set, then|A|(1 +o(1))(2N)^{1/3}.

As shown above, there is a simpler argument that implies this bound. The novelty
here is that our results imply (2) fork= 3. It is important to mention that the error
term we obtain is larger than the error term in the bound C_{3}(N)(2N)^{1/3}+ 2.

We feel that any improvement in the leading term of Theorem 1.3 or (2) would be significant.

InZwe obtain the following bounds for smallk.

Theorem 1.5. (i) IfA⇢[N] is aB_{3}^{+}-set, then|A|(1 +o(1))(18N)^{1/3}.
(ii) If A⇢[N]is aB_{4}^{+}-set, then |A|(1 +o(1))(272N)^{1/4}.

Recall that Ruzsa [16] proved F_{k}^{⇤}(N) (1 +o(1))k^{2 1/k}N^{1/k} which implies
F_{k}^{+}(N) (1 +o(1))k^{2 1/k}N^{1/k}. For k 5, we were able to improve this upper
bound on F_{k}^{+}(N) by modifying arguments of Ruzsa. Our method also applies to
B^{⇤}_{k}-sets. As a consequence, we improve the upper bound on F_{k}^{⇤}(N) for allk 3.

We state our result only for k= 3 and for largek. For other small values ofkthe reader is referred to Table 1 in Section 6.

Theorem 1.6. IfA⇢[N]is a B_{3}^{⇤}-set, then|A|(1 +o(1))(162N)^{1/3}. IfA⇢[N]
is aB^{⇤}_{k}-set, then

|A|

✓1 4+✏(k)

◆
k^{2}N^{1/k}
where✏(k)!0ask! 1.

We remark that Ruzsa’s upper bound onF_{k}^{⇤}(N) is asymptotic tok^{2}N^{1/k}. Our
results do not rule out the possibility ofF_{k}^{+}(N) being asymptotic toF_{k}^{⇤}(N).

Problem 1.7. Determine whether or notF_{k}^{+}(N) is asymptotic toF_{k}^{⇤}(N) fork 3.

IfA⇢[N] is aB_{k}^{⇤}-set, then the number of solutions to 2x_{1}+x_{2}+· · ·+x_{k} _{1}=
y_{1}+· · ·+y_{k} withx_{i}, y_{j}2Aiso(|A|^{k}) (see [16]). AB^{⇤}_{k}-set allows solutions to this
equation withx1, . . . , xk 1, y1, . . . , yk all distinct, but such a solution cannot occur
in a B_{k}^{+}-set. If it were true that F_{k}^{+}(N) is asymptotic toF_{k}^{⇤}(N), then this would
confirm the belief that it is the sums ofkdistinct elements ofAthat control the size
ofAand the lower order sums should not matter. Jia [12] defines asemi-B_{k}-set to
be a setAwith the property that all sums consisting ofkdistinct elements ofAare
distinct. He states that Erd˝os conjectured [8] that a semi-Bk-set A ⇢[N] should
satisfy|A|(1 +o(1))N^{1/k}. A positive answer to Problem 1.7 would be evidence
in favor of this conjecture.

At this time we do not know how to constructB^{+}_{2k}-sets orB^{⇤}_{2k}-sets for anyk 2
that are bigger than the corresponding Bose-Chowla B2k-sets. We were able to
construct interestingB_{4}^{+}-sets in the non-abelian setting.

LetGbe a non-abelian group. A setA⇢Gis anon-abelian Bk-set if

a_{1}a_{2}· · ·a_{k}=b_{1}b_{2}· · ·b_{k} with a_{i}, b_{j} 2A (5)
impliesa_{i}=b_{i} for 1ik. IfA⇢Gis a non-abelianB_{k}-set, then everyk-letter
word in |A| is di↵erent so |A|^{k} |G|. Odlyzko and Smith [15] proved that there
exist infinitely many groups Gsuch thatG has a non-abelian B4-set A⇢Gwith

|A|= (1 +o(1))⇣

|G|

1024

⌘1/4

. They actually proved a more general result that gives
constructions of non-abelian B_{k}-sets for all k 2. The case when k = 4 is the
only result that we will need. Define a non-abelian B^{+}_{k}-set to be a set A ⇢ G
such that (5) impliesai =bi for some i2{1,2, . . . , k}. As in the abelian setting,
a non-abelian Bk-set is also a non-abelian B^{+}_{k}-set but the converse is not true in
general. Using a construction of [15], we prove

Theorem 1.8. For any prime p with p 1 divisible by 4, there is a non-abelian
groupGof order48(p^{4} 1) that contains a non-abelianB_{4}^{+}-set A⇢Gwith

|A|= 1 2(p 1).

Our result shows that there are infinitely many groupsGsuch thatGhas a non-
abelian B_{4}^{+}-set Awith |A| =⇣

|G|

768

⌘1/4

+o(|G|^{1/4}). We conclude our introduction
with the following conjecture concerningB_{2k}^{+}-sets.

Conjecture 1.9. Ifk 4 is any even integer, then there exists a positive constant
c_{k} such that for infinitely manyN,

F_{k}^{+}(N) (1 +ck+o(1))N^{1/k}.

If Conjecture 1.9 is true with c_{k} = 2^{1 1/k} 1 as in the odd case, then using
Green’s upper boundF4(N)(1 +o(1))(7N)^{1/4}, we can conclude thatF4(N) and
F_{4}^{⇤}(N) are not asymptotically the same just as in the case when k= 3. Our hope
is that a positive answer to Conjecture 1.9 will either provide an analogue of (4) for
evenk 4, or a construction of aB_{k}^{+}-set that does not use Bose-ChowlaB_{k}-sets.

2. Proof of Theorem 1.1

In this section we show how to constructB_{k}^{+}-sets for oddk 3. Our idea is to take
a denseB_{k}-setA and a translate ofA.

Lemma 2.1. If A⇢ZN is aB_{k}-set wherek 3is odd, then
A^{+}:={a+bN :a2A, b2{0,1}}

is aB^{+}_{k}-set inZ2N.

Proof. Letk 3 be odd and suppose Xk

i=1

a_{i}+b_{i}N ⌘
Xk
i=1

c_{i}+d_{i}N (mod 2N) (6)

wherea_{i}, c_{i} 2A, andb_{i}, d_{i}2{0,1}. Taking (6) moduloN gives
Xk

i=1

ai⌘ Xk

i=1

ci (mod N).

Since A is aBk-set in ZN, (a1, . . . , ak) must be a permutation of (c1, . . . , ck). If
we label thea_{i}’s andc_{i}’s so thata_{1}a_{2}· · ·a_{k} and c_{1} c_{2} · · ·c_{k}, then
a_{i}=c_{i} for 1ik. Rewrite (6) as

Xk i=1

b_{i}N ⌘
Xk
i=1

d_{i}N (mod 2N).

The sums Pk

i=1b_{i} and Pk

i=1d_{i} have the same parity. Since k is odd and b_{i}, d_{i} 2
{0,1}, there must be ajsuch thatbj =dj, soaj+bjN⌘cj+djN (mod 2N).

Let q be a prime power, k 3 be an odd integer, and A_{k} be a Bose-Chowla
Bk-set withAk ⇢Zq^{k} 1 (see [2] for a description ofAk). Let

A^{+}_{k} ={a+b(q^{k} 1) :a2A_{k}, b2{0,1}}.

By Lemma 2.1, A^{+}_{k} is aB^{+}_{k}-set in Z2(q^{k} 1) and |A^{+}_{k}| = 2|A_{k}| = 2q. This proves
Theorem 1.1.

3. Proof of Theorem 1.3

LetA⇢ZNbe aB_{3}^{+}-set. IfNis odd, then 2x⌘2y(modN) impliesx⌘y(modN).

IfNis even, then 2x⌘2y(modN) impliesx⌘y(modN) orx⌘y+N/2 (modN).

Because of this, the odd case is quite a bit easier to deal with and so we present the more difficult case. In this sectionN is assumed to be even. IfN is odd, then the proof of Theorem 1.5(i) given in the next section works inZN. The only modification needed is to divide byN instead of 3Nwhen applying Cauchy-Schwarz.

For simplicity of notation, we writex=y rather thanx⌘y (modN).

Forn2ZN, define f(n) = #n

({a, c}, b)2A^{(2)}⇥A:n=a b+c,{a, c}\{b}=;o
.
Recall thatA^{(2)}={{x, y}:x, y2A, x6=y}. The sumP

f(n)(f(n) 1) counts the number of ordered pairs (({a, c}, b),({x, z}, y)) such that the tuples ({a, c}, b) and ({x, z}, y) are distinct, and both are counted byf(n). For each such pair we cannot have{a, c}={x, z}. Otherwise, the tuples would be equal. If (({a, c}, b),({x, z}, y)) is counted by P

f(n)(f(n) 1), thena+y+c=x+b+z. By the B_{3}^{+} property,
{a, y, c}\{x, b, z}6=;so that{a, c}\{x, z}6=;orb=y. The tuples are distinct,
so both of these cases cannot occur at the same time.

Case 1: {a, c}\{x, z}6=;andb6=y.

Without loss of generality, assume a = x. Cancel a from both sides of the equation a b+c =x y+z and solve forc to getc =b y+z. Here we are

using the ordering of the tuples (({a, c}, b),({x, z}, y)) to designate which element is solved for after the cancellation of the common term.

If z=b, thenc+y = 2b and we have a 3-term arithmetic progression (a.p. for short). The number of trivial 3-term a.p.’s inAis at most 2|A|since for anya2A,

a+a= 2a= 2(a+N/2).

Next we count the number of nontrivial 3-term a.p.’s. By nontrivial, we mean that all terms involved in the a.p. are distinct, anda+a= 2(a+N/2) is considered to be trivial.

Ifp+q= 2ris a 3-term a.p., then callpand qouter terms. Letpbe an outer
term of the 3-term a.p. p+q = 2r where p, q, r 2 A. We will show that pis an
outer term of at most one other nontrivial a.p. Let p+q^{0} = 2r^{0} be another a.p.

withq^{0}, r^{0} 2Aand (q, r,)6= (q^{0}, r^{0}).

Ifr=r^{0}, thenp+q= 2r= 2r^{0} =p+q^{0} so q=q^{0}. This is a contradiction and
so we can assume thatr6=r^{0}.

If q = q^{0}, then 2r = p+q = p+q^{0} = 2r^{0} so r^{0} = r or r^{0} = r+N/2. Thus,
p+q= 2rorp+q= 2(r+N/2).

Now supposer6=r^{0} andq6=q^{0}. Since 2r q=p= 2r^{0} q^{0} we have by theB^{+}_{3}
property,

{r, q^{0}}\{r^{0}, q}6=;.

The only two possibilities arer=qorr^{0}=q^{0}, but in either of these cases we get a
trivial 3-term a.p. Putting everything together proves the following lemma.

Lemma 3.1. If A ⇢ZN is a B^{+}_{3}-set, then the number of 3-term arithmetic pro-
gressions inA is at most4|A|.

Given a fixed elementa2Aand a fixed 3-term a.p. c+y = 2b inA, there are at most 4! ways to form an ordered tuple of the form (({a, c}, b),({a, b}, y)). The number of ordered tuples counted by P

f(n)(f(n) 1) when {a, c}\{x, z} 6= ;
andz =bis at most 4!|A| ·4|A|= 96|A|^{2}. The first factor of|A| in the expression
4!|A| ·3|A|comes from the number of ways to choose the elementa.

Assume now that z6=b. Recall that we have solved for c to getc =b y+z.

Ifb=y, thenc=z which implies{a, c}={x, z}, a contradiction as the tuples are
distinct. By definitiony6=z, soc=b y+zwhere{b, z}2A^{(2)}and{y}\{b, z}=;.
The number of ways to writec in this form isf(c). Given such a solution{b, z}, y
counted byf(c), there are two ways to orderbandz, and|A|ways to choosea=x.

The number of ordered tuples we obtain when{a, c}\{x, z}6=;andz 6=b is at most|A| ·2P

c2Af(c). This completes the analysis in Case 1.

Before addressing Case 2, the case when b = y and {a, c}\{x, z} = ;, some additional notation is needed. Ford2A+A, define

S(d) = {a, b}2A^{(2)} :a+b=dand there is a pair{a^{0}, b^{0}}2A^{(2)}
with{a, b}\{a^{0}, b^{0}}=;anda^{0}+b^{0}=d}.

Letd1, d2, . . . , dM be the integers for whichS(di)6=;. WriteS_{i}^{2}forS(di) and define
T_{i}^{1}={a:a2{a, b}for some{a, b}2S^{2}_{i}}.

Lets_{i}=|S_{i}^{2}|andd_{1}, d_{2}, . . . , d_{m}be the integers for whichs_{i}= 2. Letd_{m+1}, . . . , d_{M}
be the integers for which s_{i} 3. For 1 i M, we will use the notationS_{i}^{2} =
{{a^{i}_{1}, b^{i}_{1}},{a^{i}_{2}, b^{i}_{2}}, . . . ,{a^{i}_{s}_{i}, b^{i}_{s}_{i}}}. A simple, but important, observation is that for
any fixed i2{1, . . . , M}, any element ofAappears in at most one pair in S_{i}^{2}.

If A was a B_{3}-set, then there would be no d_{i}’s. This suggests that a B_{3}^{+}-set
or a B_{3}^{⇤}-set that is denser than a B_{3}-set should have many d_{i}’s. The B_{3}^{+}-set A^{+}_{3}
constructed in Theorem 1.1 hasm⇡ ^{1}_{2} ^{|A}_{2}^{+}^{3}^{|} . However, ifA^{+}_{3} is viewed as a subset
ofZ, thenm⇡^{1}_{4} ^{|A}_{2}^{+}^{3}^{|} (see Lemma 4.3 which also holds inZN ifN is odd).

Case 2: b=y and{a, c}\{x, z}=;.

Ifb=y, thena+c=x+z. There are|A|choices forb=y and XM

i=1

|S_{i}^{2}|(|S_{i}^{2}| 1)

ways to choose an ordered pair of di↵erent sets{a, c},{x, z}2A^{(2)}witha+c=x+z,
and{a, c}\{x, z}=;.

Putting Cases 1 and 2 together gives the estimate Xf(n)(f(n) 1)|A| 2X

c2A

f(c) + XM i=1

|S_{i}^{2}|(|S_{i}^{2}| 1)

!

+ 96|A|^{2}. (7)
Our goal is to find upper bounds on the sumsP

c2Af(c) andPM

i=1|S^{2}_{i}|(|S_{i}^{2}| 1).

Lemma 3.2. If x2T_{i}^{1}\T_{j}^{1} for some i6=j, then (i) max{s_{i}, s_{j}}3and (ii) if
si=sj = 3, then for somex1, y, z2Adepending oniandj, we havedj =di+N/2
andS_{i}^{2}={{x, x1},{y, z},{y+^{N}_{2}, z+^{N}_{2}}},S_{j}^{2}={{x, x1+^{N}_{2}},{y+^{N}_{2}, z},{y, z+^{N}_{2}}}.
Proof. If si = 2 and sj = 2 then we are done. Assume sj > 2. Let S_{i}^{2} =
{{a^{i}_{1}, b^{i}_{1}}, . . . ,{a^{i}_{s}_{i}, b^{i}_{s}_{i}}} and S_{j}^{2} ={{a^{j}_{1}, b^{j}_{1}}, . . . ,{a^{j}_{s}_{j}, b^{j}_{s}_{j}}}. Without loss of gen-
erality, suppose x = a^{1}_{i} and x = a^{1}_{j}. By definition, s_{i} 2 so we can write
di=x+b^{i}_{1}=a^{i}_{2}+b^{i}_{2} anddj=x+b^{j}_{1}=a^{j}_{2}+b^{j}_{2}=a^{j}_{3}+b^{j}_{3}.

Solve forxto getx=a^{i}_{2}+b^{i}_{2} b^{i}_{1}=a^{j}_{2}+b^{j}_{2} b^{j}_{1}. This can be rewritten as
a^{i}_{2}+b^{i}_{2}+b^{j}_{1}=a^{j}_{2}+b^{j}_{2}+b^{i}_{1}. (8)
Sinced_{i}6=d_{j},b^{i}_{1} cannot beb^{j}_{1} thereforeb^{j}_{1}is not on the right hand side of (8), and
b^{i}_{1} is not on the left hand side of (8). By theB^{+}_{3} property,{a^{i}_{2}, b^{i}_{2}}\{a^{j}_{2}, b^{j}_{2}}6=;.

The same argument can be repeated witha^{j}_{3}in place ofa^{j}_{2}andb^{j}_{3}in place ofb^{j}_{2} to
get

{a^{i}_{2}, b^{i}_{2}}\{a^{j}_{3}, b^{j}_{3}}6=;.

Recall any element of Acan occur at most once in the list a^{j}_{1}, b^{j}_{1}, a^{j}_{2}, b^{j}_{2}, . . . a^{j}_{s}_{j}, b^{j}_{s}_{j}
thussj 3. By symmetry,si3.

Now suppose si = sj = 3. Repeating the argument above, we have for each 2k3 and 2l3,

|{a^{i}_{l}, b^{i}_{l}}\{a^{j}_{k}, b^{j}_{k}}|= 1.

This intersection cannot have size 2 since d_{i} 6=d_{j}. Without loss of generality, let
y = a^{i}_{2} = a^{j}_{2}, z = b^{i}_{2} = a^{j}_{3}, u = a^{i}_{3} = b^{j}_{2}, and v = b^{i}_{3} = b^{j}_{3}. We represent these
equalities betweenT_{i}^{1} andT_{j}^{1} using a bipartite graph with partsT_{i}^{1} andT_{j}^{1} where
w2T_{i}^{1} is adjacent tow^{0} 2T_{j}^{1} if and only ifw=w^{0} (see Figure 1).

s s s s s s

s s s s s s

@@

@@

@@

a^{j}_{1}=x
a^{i}_{1}=x

b^{j}_{1}
b^{i}_{1}

a^{j}_{2}=y
a^{i}_{2}=y

b^{j}_{2}=u
b^{i}_{2}=z

a^{j}_{3}=z
a^{i}_{3}=u

b^{j}_{3}=v
b^{i}_{3}=v

### T

_{j}

^{1}

### T

_{i}

^{1}

Figure 1 - Equality Graph for Lemma 3.2

The equalitiesd_{i}=y+z=u+vandd_{j} =y+u=z+vimplyd_{i} d_{j}=z uand
di dj =u z. Therefore 2z= 2u. Ifz=u, then this is a contradiction since the
elements in the listx, b^{i}_{1}, y, z, u, v are all distinct. It is in this step that the parity
ofN plays an important role. We concludeu=z+N/2 and

d_{j} =y+u=y+ (z+N/2) =y+z+N/2 =d_{i}+N/2.

Letb^{i}_{1}=x1so b^{j}_{1}=x1+N/2. Sincedi=y+z=u+v andu=z+N/2,
v=y+z u=y+z (z+N/2) =y N/2 =y+N/2.

Substitutingu=z+N/2 and v=y+N/2 gives the assertion about the pairs in
S_{i}^{2} andS_{j}^{2} whens_{i}=s_{j}= 3.

Corollary 3.3. Ifs_{i} 4, then for anyj6=i,T_{i}^{1}\T_{j}^{1}=;. Furthermore, anyx2A
is in at most two T_{i}^{1}’s with si= 3.

Proof. The first statement follows immediately from Lemma 3.2. For the second
statement, suppose x 2 T_{i}^{1}\T_{j}^{1} with s_{i} = s_{j} = 3 and i 6= j. By Lemma 3.2,
{x, x_{1}}2S_{i}^{2} and{x, x_{1}+N/2}2S_{j}^{2} for somex_{1} 2A. Ifx2T_{k}^{1} withk6=i, then
{x, x1+N/2}2S^{2}_{k} sodj =x+ (x1+N/2) =dk andj=k.

Lemma 3.4. If A⇢ZN is aB_{3}^{+}-set, then
X

c2A

f(c)|A|^{2}+ 7|A|.
Proof. Forc2A, let

g1(c) = #n

({x, z}, y)2A^{(2)}⇥A:c=x y+z, c6=y,{x, z}\{y}=;o
and

g_{2}(c) = #n

({x, z}, y)2A^{(2)}⇥A:c=x y+z, c=y,{x, z}\{y}=;o
.
For each c2 A, f(c) =g_{1}(c) +g_{2}(c). The sumP

c2Ag_{2}(c) is exactly the number
of nontrivial 3-term a.p.’s in A. By Lemma 3.1, P

c2Ag1(c) 4|A|. Estimating P

c2Ag1(c) takes more work. To computeg1(c) with c 2A, we first choose ani
withc2T_{i}^{1}, and then choose one of the pairs{x, z}2S_{i}^{2}\{c, y}to obtain a solution
c=x y+zwithc6=yand{x, z}\{y}=;.

Ifc /2T_{1}^{1}[· · ·[T_{M}^{1}, then the equationc+y=x+zwithc, y, x, andzall distinct
has no solutions inA sog1(c) = 0. Assumec2T_{1}^{1}[· · ·[T_{M}^{1}.

Case 1: c /2T_{1}^{1}[· · ·[T_{m}^{1}.

By Corollary 3.3, there are two possibilities. One is that there is a uniquejwith
c2T_{j}^{1}and sj 3. In this case,|S^{2}_{j}| ^{|A|}_{2} so g1(c) ^{|A|}_{2} . The other possibility is
thatc 2T_{i}^{1}\T_{j}^{1} withs_{i} =s_{j} = 3 and i 6=j. In this case, g_{1}(c)4 because we
can choose eitheri or j, and then one of the two pairs in S^{2}_{i} or S_{j}^{2} that does not
containc.

Case 2: c2T_{1}^{1}[· · ·[T_{m}^{1}.

By Lemma 3.2,cis not in anyT_{j}^{1} withsj 4 andc is in at most twoT_{j}^{1}’s with
sj = 3. There are at most |A| T_{i}^{1}’s withc 2T_{i}^{1} since there are at most|A| pairs
{c, y}that containc sog_{1}(c)|A|+ 4.

In all cases,g_{1}(c)|A|+ 4 and
X

c2A

f(c) =X

c2A

(g_{1}(c) +g_{2}(c))|A|(|A|+ 4) + 4|A|
which proves the lemma.

Lemma 3.5. If g_{1}(c)is the function of Lemma 3.4, then
2

XM i=1

|S_{i}^{2}|(|S_{i}^{2}| 1) =X

c2A

g_{1}(c).

Proof. Define an edge-colored graphGwith vertex setA, edge set[^{M}i=1S^{2}_{i}, and such
that the color of edge {a, b}isa+b. The sumPM

i=1|S_{i}^{2}|(|S_{i}^{2}| 1) counts ordered
pairs ({c, y},{x, z}) of distinct edges of G where {c, y} and {x, z} have the same
color, i.e., c+y = x+z, and c, y, x, and z are all distinct elements of A. The
sum P

c2Ag1(c) counts each such ordered pair ({c, y},{x, z}) exactly two times,
one contribution coming from g_{1}(c) and the other fromg_{1}(y).

By Lemma 3.5,

XM i=1

|S_{i}^{2}|(|S_{i}^{2}| 1) 1
2

X

c2A

f(c). (9)

Next we use the following version of the Cauchy-Schwarz inequality.

Lemma 3.6. (Cauchy-Schwarz)Ifx_{1}, . . . , x_{n}are real numbers,t2{1,2, . . . , n 1},
and =^{1}_{t}P_{t}

i=1xi 1 n

P_{n}

i=1xi, then Xn

i=1

x^{2}_{i} 1
n

Xn i=1

x_{i}

!2

+tn ^{2}
n t.
A simple counting argument shows P

f(n) = ^{|A|}_{2} (|A| 2). Let P

c2Af(c) =

|A|^{2}. If

:= 1

|A| X

c2A

f(c) 1 N

X

n

f(n) = |A| 1 N

X

n

f(n)

then, using Ruzsa’s bound|A|=O(N^{1/3}) andC_{3}^{+}(N)F_{3}^{+}(N), we get

= |A|

|A|

2 (|A| 2)

N |A| C

whereC is some absolute constant. By Lemma 3.6,
Xf(n)^{2}

|A|2

2(|A| 2)^{2}

N +|A| ·N( |A| C)^{2}
N |A|

=

|A|

2

2(|A| 2)^{2}

N + ^{2}|A|^{3}

⇣1 _{|A|}^{C} ⌘2

1 ^{|A|}_{N} .
By (7) and (9),

Xf(n)^{2} X

f(n) +|A| 2X

c2A

f(c) + XM i=1

|S_{i}^{2}|(|S_{i}^{2}| 1)

!

+ 96|A|^{2}

|A|^{3}
2 +5|A|

2 X

c2A

f(c) + 96|A|^{2}

= |A|^{3}

✓1 + 5 2

◆

+ 96|A|^{2}.

Combining the two estimates onP

f(n)^{2} gives the inequality

|A|2

2(|A| 2)^{2}

N + ^{2}|A|^{3}

⇣1 _{|A|}^{C} ⌘2

1 ^{|A|}_{N} |A|^{3}

✓1 + 5 2

◆

+ 96|A|^{2}. (10)
If = 0, then (10) is not valid but we still get

|A|

2

2(|A| 2)^{2}
N |A|^{3}

2 + 96|A|^{2}.

This inequality implies |A|(1 +o(1))(2N)^{1/3}. Assume that >0. In this case,
(10) simplifies to

|A|(1 +o(1)) 2 + 10 4 ^{2 1}^{/3}N^{1/3}. (11)
At this point we find the maximum of the right hand side of (11) using the fact
that 0 1 +_{|A|}^{7} , which follows from Lemma 3.4. For|A| 28, the maximum
occurs when = 1 +_{|A|}^{7} therefore, after some simplifying, we find

|A|(1 +o(1))(8N)^{1/3}.

4. Proof of Theorem 1.5(i)

The proof of Theorem 1.5(i) follows along the same lines as the proof of Theorem 1.3.

We will use the same notation as in the previous section. The derivation of (7) is
very similar except in Z, or in ZN with N odd, there are fewer 3-term a.p.’s in
A. Regardless, (7) still holds under the assumption that A ⇢[N] is aB_{3}^{+}-set, or
A⇢ZN is aB_{3}^{+}-set andN odd.

Next we prove a lemma that corresponds to Lemma 3.2.

Lemma 4.1. If x2 T_{i}^{1}\T_{j}^{1} for distinct i and j, then either s_{i} =s_{j} = 2, or if
s_{j} >2, thens_{i}= 2,s_{j} = 3, and|T_{i}^{1}\T_{j}^{1}| 3.

Proof. The proof of this lemma is exactly the same as the proof of Lemma 3.2 up
until the point where we write the equation 2z = 2u. In Z(or ZN with N odd),
this impliesz=uwhich is a contradiction since the elementsx, b^{i}_{1}, y, z, u, vare all
distinct. This allows us to conclude thatT_{i}^{1}\T_{j}^{1}=;for anyi6=jwithsi 3 and
s_{j} 3.

The assertion|T_{i}^{1}\T_{j}^{1}| 3 can be verified with some easy computations. Alter-
natively, one can just ignorea^{i}_{3}=uandb^{i}_{3}=vin Figure 1 to see|T_{i}^{1}\T_{j}^{1}| 3.

Corollary 4.2. If m+ 1i < jM, thenT_{i}^{1}\T_{j}^{1}=;.

Proof. Ifx2Ti\Tj withi6=j, then by Lemma 4.1, one ofsi orsj must be equal to 2.

The next lemma has no corresponding lemma from the previous section. It will be used to estimateP

c2Af(c).

Lemma 4.3. IfA⇢[N]is a B_{3}^{+}-set or ifA⇢ZN is a B_{3}^{+}-set andN is odd, then
for any a2A, the number of distinct i2{1,2, . . . , m}such that a2T_{i}^{1} is at most

|A|

2 .

Proof. To make the notation simpler, we suppose a 2 T_{i}^{1} for 1 i k and we
will show k ^{|A|}_{2} . The case when a 2 T_{i}^{1}_{1} \· · ·\T_{i}^{1}_{k} for some sequence 1
i_{1} < · · · < i_{k} m is the same. For this lemma we deviate from the notation
S_{i}^{2} = {{a^{i}_{1}, b^{i}_{1}}, . . .{a^{i}_{s}_{i}, b^{i}_{s}_{i}}}. Write S_{i}^{2} = {{a, a_{i}},{b_{i}, c_{i}}} and a+a_{i} =b_{i}+c_{i}
where 1ik, and for fixedi, the elementsa, a_{i}, b_{i}, andc_{i}are all distinct. Observe
a1, . . . , ak are all distinct since the sums a+ai are all distinct. For 1 i k,
a=b_{i}+c_{i} a_{i}. Therefore,

bi+ci+aj =bj+cj+ai

for any 1i, j k. These two sums must intersect and they cannot intersect at aj or ai, unlessi=j, so for 2jk,

{b1, c1}\{bj, cj}6=;.

Let 2j l be the indices for which the sums intersect at b_{1}. Letl+ 1j k
be the indices for which the sums intersect atc1. Letb=b1 andc =c1. We have
thekequations

a+a1 = b+c,
a+a_{2} = b+c_{2},

... ...
a+a_{l} = b+c_{l},
a+a_{l+1} = b_{l+1}+c,

... ... a+ak = bk+c.

We will show thata_{1}, . . . , a_{k}, c_{1}, . . . , c_{l}, b_{l+1}, . . . , b_{k} are all distinct which implies
2k|A|.

Supposeai=bjfor some 2ilandl+1j k. Thena+bj=a+ai=b+ci,
but a = bj +c aj. Therefore, b+ci = a+bj = 2bj+c aj which implies
2b_{j}+c=b+c_{i}+a_{j}. The elementsa_{j}, b_{j}, andcare all distinct so these sums cannot

intersect ataj. Similarly they cannot intersect atc. The only remaining possibility
isb_{j} =c_{i}, but thena_{i} =b_{j}=c_{i}, which is a contradiction. We conclude thata_{i}and
b_{j} are distinct for 2il and l+ 1j k. A similar argument shows thata_{j}
andci are distinct forl+ 1jkand 2il.

Suppose now that ai = ci^{0} for some 2 i 6= i^{0} l. Then b+ci = a+ai =
a+ci^{0} =a+ (a+ai^{0} b), so that 2b+ci = 2a+ai^{0}. Since 2i^{0} l, these sums
cannot intersect atband they cannot intersect ata. Ifc_{i}=a_{i}0, thena=bwhich is
impossible. The equation 2b+c_{i}= 2a+a_{i}0 contradicts theB^{+}_{3} property. Note that
2b= 2aneed not imply a=b ifA⇢ZN with N even. We conclude thatai 6=ci^{0}

for each 2i6=i^{0} l. Similarly,aj 6=bj^{0} forl+ 1j6=j^{0}k.

The previous two paragraphs imply

{a_{1}, a_{2}, . . . , a_{k}}\{c_{2}, c_{3}, . . . , c_{l}, b_{l+1}, b_{l+2}, . . . , b_{k}}=;.

To finish the proof we show{c_{2}, c_{3}, . . . , c_{l}}\{b_{l+1}, b_{l+2}, . . . , b_{k}}=;. Supposec_{i}=b_{j}
for some 2il andl+ 1jk. Then

a+ai=b+ci=b+bj =b+ (a+aj c) =b+a+aj (a+a1 b) =aj+ 2b a1

which implies a+ai +a1 = aj + 2b. Since i < l+ 1 j, these sums cannot
intersect ata_{j}. They cannot intersect atbeither sincea, a_{i}, b, andc_{i}are all distinct
whenever 1il. This is a contradiction. Therefore,c_{i}6=b_{j} for all 2iland
l+ 1jk.

Lemma 4.4. If A⇢[N]is aB_{3}^{+}-set, then
X

c2A

f(c)|A|^{2}

2 + 4|A|.

Proof. Again we writef as a sum of the simpler functionsg_{1} andg_{2}. Recall that
forc2A,

g_{1}(c) = #n

({x, z}, y)2A^{(2)}⇥A:c=x y+z, c6=y,{x, z}\{y}=;o
,
and

g2(c) = #n

({x, z}, y)2A^{(2)}⇥A:c=x y+z, c=y,{x, z}\{y}=;o
.
For eachc2A,f(c) =g_{1}(c) +g_{2}(c). The sumP

c2Ag_{2}(c) is exactly the number of
nontrivial 3-term a.p.’s inA. By Lemma 3.1, this is at most 4|A|.

Ifc /2T_{1}^{1}[· · ·[T_{M}^{1}, then the equationc+y=x+zwithc, y, x, andzall distinct
has no solutions inA sog1(c) = 0. Assumec2T_{1}^{1}[· · ·[T_{M}^{1}.

Case 1: c /2T_{1}^{1}[· · ·[T_{m}^{1}.

By Corollary 4.2, there is a uniquej withc2T_{j}^{1} andm+ 1jM. For such
aj we have|S_{j}^{2}|^{|A|}_{2} by Corollary 4.2. There is a unique pair inS_{j}^{2}that contains
c so y is determined. There are at most ^{|A|}_{2} choices for the pair{x, z}2S_{j}^{2}\{c, y}
so g_{1}(c)^{|A|}_{2} .

Case 2: c2T_{1}^{1}[· · ·[T_{m}^{1}.

First assume c /2T_{m+1}^{1} [· · ·[T_{M}^{1}. A solution toc+y=x+zwith c, y, x, and
z all distinct corresponds to a choice of an S_{i}^{2} with 1 i m and c 2 T_{i}^{1}. By
Lemma 4.3,cis in at most ^{|A|}_{2} T_{i}^{1}’s and sog1(c) ^{|A|}_{2} .

Lastly suppose c 2 T_{m+1}^{1} [· · ·[T_{M}^{1} . There is a unique j with c 2 T_{j}^{1} and
m+ 1 j M. Furthermore, for this j we have |T_{j}^{1}| = 6 by Lemma 4.1. If
c 2 T_{i}^{1} with 1 im then, again by Lemma 4.1, |T_{i}^{1}\T_{j}^{1}| 3. There are ^{6}_{3}
3-subsets ofT_{j}^{1} and given such a 3-subset, there are ^{3}_{1} ways to pair up an element
in the 3-subset withcinS^{2}_{i}. This impliesc is in at most 3 ^{6}_{3} S_{i}^{2}’s with 1im,
so g_{1}(c) 2 + 3 ^{6}_{3} ^{|A|}_{2} . The 2 comes from choosing one of the two pairs in
S_{j}^{2}\{c, y}.

The rest of the proof of Theorem 1.5(i) is almost identical to that of Theorem 1.3.

IfP

c2Af(c) = |A|^{2}, then by (7) and (9),
Xf(n)^{2}|A|^{3}

✓1 + 5 2

◆

+O(|A|^{2}).

We use the same version of the Cauchy-Schwarz inequality to get

|A|2

2(|A| 2)^{2}

3N + ^{2}|A|^{3}

⇣1 ^{C}_{|A|}⌘
1 _{3N}^{|A|} |A|^{3}

✓1 + 5 2

◆

+O(|A|^{2}). (12)
If = 0, then

|A|

2

2(|A| 2)^{2}
3N |A|^{3}

2 +O(|A|^{2})

which implies|A|(1 +o(1))(6N)^{1/3}. Assume >0. Then (12) simplifies to

|A|(1 +o(1))(6 + 30 12 ^{2})^{1/3}N^{1/3}.

By Lemma 4.4, 0 ^{1}_{2}+_{|A|}^{3} . The maximum occurs when = ^{1}_{2}+_{|A|}^{3} and we
get

|A|(1 +o(1))(18N)^{1/3}.

If we were working inZN with N odd, then in (12) the 3N can be replaced by
N. Some simple calculations show that we get Theorem 1.3 in the odd case. We
actually obtain the upper bound|A|(1 +o(1))(6N)^{1/3}whenA⇢ZNis aB_{3}^{+}-set
andN is odd.

5. Proof of Theorem 1.5(ii)

LetA⇢[N] be aB_{4}^{+}-set. Forn2[ 2N,2N], define

f(n) = #{({a1, a2},{b1, b2}) 2 A^{(2)}⇥A^{(2)} :a1+a2 b1 b2=n,
{a1, a2}\{b1, b2}=;}.

Recall thatA^{(2)}={{x, y}:x, y2A, x6=y}.

Lemma 5.1. If A⇢[N]is aB_{4}^{+}-set, then Ais a B_{2}-set.

Proof. Suppose a+b = c+d with a, b, c, d 2 A. If {a, b}\{c, d}= ;, then the
equation 2(a+b) = 2(c+d) contradicts the B^{+}_{4} property so {a, b}\{c, d} 6= ;.
Sincea+b=c+dand{a, b}\{c, d}6=;, we have{a, b}={c, d}.

Lemma 5.2. If A⇢[N]is aB_{4}^{+}-set, then for any integer n,f(n)2|A|.

Proof. Suppose f(n) 1. Fix a tuple ({a_{1}, a_{2}},{b_{1}, b_{2}}) counted by f(n). Let
({c_{1}, c_{2}},{d_{1}, d_{2}}) be another tuple counted byf(n), not necessarily di↵erent from
({a_{1}, a_{2}},{b_{1}, b_{2}}). Thena_{1}+a_{2} b_{1} b_{2}=c_{1}+c_{2} d_{1} d_{2} so

a1+a2+d1+d2=c1+c2+b1+b2. (13)
By the B_{4}^{+} property, {a1, a2, d1, d2}\{c1, c2, b1, b2} 6= ;. In order for this in-
tersection to be non-empty, it must be the case that {a_{1}, a_{2}}\{c_{1}, c_{2}} 6= ; or
{b_{1}, b_{2}}\{d_{1}, d_{2}}6=;.

Case 1: {a_{1}, a_{2}}\{c_{1}, c_{2}}6=;.

Assumea_{1}=c_{1}. There are at most|A|choices forc_{2}so we fix one. The equality
a_{1}=c_{1} and (13) imply

d1+d2=b1+b2+c2 a2. (14)
The right hand side of (14) is determined. By Lemma 5.1, there is at most one pair
{d_{1}, d_{2}}such that (14) holds.

Case 2: {a_{1}, a_{2}}\{c_{1}, c_{2}}=;and {b_{1}, b_{2}}\{d_{1}, d_{2}}6=;.

Again there is no loss in assumingb_{1}=d_{1}. There are at most|A| choices ford_{2}
so fix one. The equality b_{1}=d_{1} and (13) imply

c_{1}+c_{2}=a_{1}+a_{2} b_{2}+d_{2}. (15)
The right hand side of (15) is determined and there is at most one pair {c1, c2}
satisfying (15) as before.

Putting the two possibilities together we get at most 2|A|solutions

({c_{1}, c_{2}},{d_{1}, d_{2}}). We have also accounted for the solution ({a_{1}, a_{2}},{b_{1}, b_{2}}) in
our count sof(n)2|A|.

Lemma 5.3. If A⇢[N]is aB_{4}^{+}-set, then

Xf(n)(f(n) 1)2|A| X

n2A A

f(n). (16)

Proof. The left hand side of (16) counts the number of ordered tuples
(({a_{1}, a_{2}},{b_{1}, b_{2}}),({c_{1}, c_{2}},{d_{1}, d_{2}}))

such that ({a1, a2},{b1, b2})6= ({c1, c2},{d1, d2}), and both tuples are counted by f(n). Equation (13) holds for these tuples. As before we consider two cases.

Case 1: {a1, a2}\{c1, c2}6=;.

Assumea1=c1 so thata2 c2=b1+b2 d1 d2.

If{b1, b2}\{d1, d2}6=;, sayb1=d1, thena2 c2=b2 d2. We can rewrite this
equation asa_{2}+d_{2}=b_{2}+c_{2}so that{a_{2}, d_{2}}={b_{2}, c_{2}}. Since{a_{1}, a_{2}}\{b_{1}, b_{2}}=;,
it must be the case that a_{2} =c_{2} and d_{2} =b_{2}. This contradicts the fact that the
tuples are distinct. We conclude{b1, b2}\{d1, d2}=;.

There are |A| choices for the element a1 =c1 and we fix one. Since a2 c2 =
b1+b2 d1 d2 and{b1, b2}\{d1, d2}=;, there are f(a2 c2) ways to choose
{b_{1}, b_{2}}and{d_{1}, d_{2}}. Also observe that each n2A A withn 6= 0 has a unique
representation as n=a_{2} c_{2} witha_{2}, c_{2}2A. This follows from the fact thatAis
aB_{2}-set.

Case 2: {a_{1}, a_{2}}\{c_{1}, c_{2}}=;and {b_{1}, b_{2}}\{d_{1}, d_{2}}6=;.

The argument in this case is essentially the same as that of Case 1.

Putting the two cases together proves the lemma.

Observe P

f(n) = ^{|A|}_{2} ^{|A|}_{2} ^{2} . Using Cauchy-Schwarz, and Lemmas 5.3 and
5.2,

⇣ |A|

2 |A| 2 2

⌘2

4N X

f(n)^{2}

✓|A| 2

◆✓|A| 2 2

◆

+ 2|A| X

n2A A

f(n)

|A|^{4}

4 + 2|A||A A| ·2|A|

|A|^{4}

4 + 4|A|^{4}=17|A|^{4}
4 .
After rearranging we get

|A|(1 +o(1))(16·17N)^{1/4}= (1 +o(1))(272N)^{1/4}.

6. Proof of Theorem 1.6

Lemma 6.1. Let A be a B_{k}^{+}-set with k 4. If k = 2l, then there is a subset
A^{0} ⇢A such thatA^{0} is aB^{+}_{l} -set and|A^{0}| |A| 2l. If k= 2l+ 1, then there is a
subsetA^{0}⇢Asuch that |A^{0}| |A| 2kandA^{0} is either a B_{l}^{+}-set or aB_{l+1}^{+} -set.

Proof. Supposek = 2l with l 2. IfA is not a B_{l}^{+}-set, then there is a set of 2l
(not necessarily distinct) elementsa1, . . . , a2l2A, such that

a1+· · ·+al=al+1+· · ·+a2l

and {a_{1}, . . . , a_{l}}\{a_{l+1}, . . . , a_{2l}}=;. LetA^{0} =A\{a_{1}, a_{2}, . . . , a_{2l}}. If A^{0} is not a
B^{+}_{l} -set, then there is another set of 2lelements ofA^{0}, sayb1, . . . , b2l, such that

b1+· · ·+bl=bl+1+· · ·+b2l

and{b_{1}, . . . , b_{l}}\{b_{l+1}, . . . , b_{2l}}=;. Adding these two equations together gives
a_{1}+· · ·+a_{l}+b_{1}+· · ·+b_{l}=a_{l+1}+· · ·+a_{2l}+b_{l+1}+· · ·+b_{2l}

with {a_{1}, . . . , a_{l}, b_{1}, . . . , b_{l}}\{a_{l+1}, . . . , a_{2l}, b_{l+1}, . . . , b_{2l}}=;. This is a contradic-
tion.

The case whenk= 2l+ 1 5 can be handled in a similar way.

It is easy to modify the proof of Lemma 6.1 to obtain a version forB_{k}^{⇤}-sets.

Lemma 6.2. LetAbe aB_{k}^{⇤}-set withk 4. Ifk= 2l, then there is a subsetA^{0}⇢A
such that A^{0} is a B_{l}^{⇤}-set and |A^{0}| |A| 2l. If k = 2l+ 1, then there is a subset
A^{0} ⇢Asuch that |A^{0}| |A| 2k andA^{0} is either aB_{l}^{⇤}-set or aB^{⇤}_{l+1}-set.

ForA⇢[N] andj 2, let

j(n) = # (a1, . . . , aj)2A^{j} :a1+· · ·+aj=n .
Lete(x) =e^{2⇡ix} andf(t) =X

a2A

e(at). For anyj 1,f(t)^{j} =P

j(n)e(nt) so by Parseval’s Identity,P

j(n)^{2}=R1

0 |f(t)|^{2j}dt. The next lemma is (5.9) of [16].

Lemma 6.3. If A⇢[N]is aB_{k}^{⇤}-set, then
X

k(n)^{2}(1 +o(1))k^{2}|A|X

k 1(n)^{2}. (17)

In [16], Ruzsa estimates the right hand side of (17) using H¨older’s Inequality and shows

X

k 1(n)^{2}⇣X

k(n)⌘^{k}_{k} ^{2}_{1}

|A|^{k}^{1}^{1}.
Our next lemma uses H¨older’s Inequality in a di↵erent way.