#A1 INTEGERS 14 (2014) UPPER AND LOWER BOUNDS ON B

UPPER AND LOWER BOUNDS ON B_k⁺-SETS

Craig Timmons¹

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⁺₃-set A ⇢ ZN has at most (1 +o(1))(8N)^1/3 elements. A set A is a B^⇤_k-set if whenevera₁+· · ·+a_k =a_k+1+· · ·+a_2k witha_i2A, 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₁, . . . , a_k) is a permutation of (b₁, . . . , b_k). IfAis aB_k-set thenAis also aB_k⁺-set, but in general the converse is not true. OftenB₂-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₂(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+¹₂ as a consequence of a more general result. This is the best known upper bound onF₂(N). By counting di↵erencesa b witha6=b, it is easy to prove C₂(N)p

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

N and lim sup^Cp2(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 ¹  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₃-set. There are ^|A|₂ (|A| 2) sums of the form a₁+a₂ a₃ where a₁, a₂, anda₃ are distinct elements ofA. Let A⁽²⁾ ={{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⁽²⁾ anda32A\{a1, a2}. This implies ^|A|₂ (|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₁+· · ·+x_k =y₁+· · ·+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₃⁺(N). We do not consider the case when k = 2. The reason for this is that Ruzsa [16] provedF₂^⇤(N)N^1/2+ 4N^1/4+ 11, and thusF2(N)⇠ F₂⁺(N)⇠F₂^⇤(N)⇠N^1/2. In fact, aB2-set is the same as aB₂⁺-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₃⁺-setA⇢[2q³] with|A|= 2q= (4·2q³)^1/3. Putting the two results together we see thatAis denser than anyB₃-set in [2q³] for sufficiently large prime powersq. Our construction and Green’s upper bound show thatF₃(N) andF₃^⇤(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₃⁺-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₃(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₃⁺-set, then|A|(1 +o(1))(18N)^1/3. (ii) If A⇢[N]is aB₄⁺-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₃^⇤-set, then|A|(1 +o(1))(162N)^1/3. IfA⇢[N] is aB^⇤_k-set, then

|A|

✓1 4+✏(k)

◆ k²N^1/k where✏(k)!0ask! 1.

We remark that Ruzsa’s upper bound onF_k^⇤(N) is asymptotic tok²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₁+x₂+· · ·+x_{k 1}= y₁+· · ·+y_k withx_i, y_j2Aiso(|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₄⁺-sets in the non-abelian setting.

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

a₁a₂· · ·a_k=b₁b₂· · ·b_k with a_i, b_j 2A (5) impliesa_i=b_i for 1ik. 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⁴ 1) that contains a non-abelianB₄⁺-set A⇢Gwith

|A|= 1 2(p 1).

Our result shows that there are infinitely many groupsGsuch thatGhas a non- abelian B₄⁺-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₄^⇤(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_iN ⌘ Xk i=1

c_i+d_iN (mod 2N) (6)

wherea_i, c_i 2A, andb_i, d_i2{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₁a₂· · ·a_k and c₁ c₂ · · ·c_k, then a_i=c_i for 1ik. Rewrite (6) as

Xk i=1

b_iN ⌘ Xk i=1

d_iN (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₃⁺-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⁽²⁾⇥A:n=a b+c,{a, c}\{b}=;o . Recall thatA⁽²⁾={{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₃⁺ 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⁰ = 2r⁰ be another a.p.

withq⁰, r⁰ 2Aand (q, r,)6= (q⁰, r⁰).

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

If q = q⁰, then 2r = p+q = p+q⁰ = 2r⁰ so r⁰ = r or r⁰ = r+N/2. Thus, p+q= 2rorp+q= 2(r+N/2).

Now supposer6=r⁰ andq6=q⁰. Since 2r q=p= 2r⁰ q⁰ we have by theB⁺₃ property,

{r, q⁰}\{r⁰, q}6=;.

The only two possibilities arer=qorr⁰=q⁰, 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⁺₃-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|². 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⁽²⁾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⁽²⁾ :a+b=dand there is a pair{a⁰, b⁰}2A⁽²⁾ with{a, b}\{a⁰, b⁰}=;anda⁰+b⁰=d}.

Letd1, d2, . . . , dM be the integers for whichS(di)6=;. WriteS_i²forS(di) and define T_i¹={a:a2{a, b}for some{a, b}2S²_i}.

Lets_i=|S_i²|andd₁, d₂, . . . , d_mbe 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² = {{aⁱ₁, bⁱ₁},{aⁱ₂, bⁱ₂}, . . . ,{aⁱ_si, bⁱ_si}}. A simple, but important, observation is that for any fixed i2{1, . . . , M}, any element ofAappears in at most one pair in S_i².

If A was a B₃-set, then there would be no d_i’s. This suggests that a B₃⁺-set or a B₃^⇤-set that is denser than a B₃-set should have many d_i’s. The B₃⁺-set A⁺₃ constructed in Theorem 1.1 hasm⇡ ¹₂ ^|A₂^+3| . However, ifA⁺₃ is viewed as a subset ofZ, thenm⇡¹₄ ^|A₂^+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²|(|S_i²| 1)

ways to choose an ordered pair of di↵erent sets{a, c},{x, z}2A⁽²⁾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²|(|S_i²| 1)

!

+ 96|A|². (7) Our goal is to find upper bounds on the sumsP

c2Af(c) andPM

i=1|S²_i|(|S_i²| 1).

Lemma 3.2. If x2T_i¹\T_j¹ 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²={{x, x1},{y, z},{y+^N₂, z+^N₂}},S_j²={{x, x1+^N₂},{y+^N₂, z},{y, z+^N₂}}. Proof. If si = 2 and sj = 2 then we are done. Assume sj > 2. Let S_i² = {{aⁱ₁, bⁱ₁}, . . . ,{aⁱ_si, bⁱ_si}} and S_j² ={{a^j₁, b^j₁}, . . . ,{a^j_sj, b^j_sj}}. Without loss of gen- erality, suppose x = a¹_i and x = a¹_j. By definition, s_i 2 so we can write di=x+bⁱ₁=aⁱ₂+bⁱ₂ anddj=x+b^j₁=a^j₂+b^j₂=a^j₃+b^j₃.

Solve forxto getx=aⁱ₂+bⁱ₂ bⁱ₁=a^j₂+b^j₂ b^j₁. This can be rewritten as aⁱ₂+bⁱ₂+b^j₁=a^j₂+b^j₂+bⁱ₁. (8) Sinced_i6=d_j,bⁱ₁ cannot beb^j₁ thereforeb^j₁is not on the right hand side of (8), and bⁱ₁ is not on the left hand side of (8). By theB⁺₃ property,{aⁱ₂, bⁱ₂}\{a^j₂, b^j₂}6=;.

The same argument can be repeated witha^j₃in place ofa^j₂andb^j₃in place ofb^j₂ to get

{aⁱ₂, bⁱ₂}\{a^j₃, b^j₃}6=;.

Recall any element of Acan occur at most once in the list a^j₁, b^j₁, a^j₂, b^j₂, . . . a^j_sj, b^j_sj thussj 3. By symmetry,si3.

Now suppose si = sj = 3. Repeating the argument above, we have for each 2k3 and 2l3,

|{aⁱ_l, bⁱ_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ⁱ₂ = a^j₂, z = bⁱ₂ = a^j₃, u = aⁱ₃ = b^j₂, and v = bⁱ₃ = b^j₃. We represent these equalities betweenT_i¹ andT_j¹ using a bipartite graph with partsT_i¹ andT_j¹ where w2T_i¹ is adjacent tow⁰ 2T_j¹ if and only ifw=w⁰ (see Figure 1).

s s s s s s

s s s s s s

@@

@@

@@

a^j₁=x aⁱ₁=x

b^j₁ bⁱ₁

a^j₂=y aⁱ₂=y

b^j₂=u bⁱ₂=z

a^j₃=z aⁱ₃=u

b^j₃=v bⁱ₃=v

T

T

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ⁱ₁, 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ⁱ₁=x1so b^j₁=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² andS_j² whens_i=s_j= 3.

Corollary 3.3. Ifs_i 4, then for anyj6=i,T_i¹\T_j¹=;. Furthermore, anyx2A is in at most two T_i¹’s with si= 3.

Proof. The first statement follows immediately from Lemma 3.2. For the second statement, suppose x 2 T_i¹\T_j¹ with s_i = s_j = 3 and i 6= j. By Lemma 3.2, {x, x₁}2S_i² and{x, x₁+N/2}2S_j² for somex₁ 2A. Ifx2T_k¹ withk6=i, then {x, x1+N/2}2S²_k sodj =x+ (x1+N/2) =dk andj=k.

Lemma 3.4. If A⇢ZN is aB₃⁺-set, then X

c2A

f(c)|A|²+ 7|A|. Proof. Forc2A, let

g1(c) = #n

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

g₂(c) = #n

({x, z}, y)2A⁽²⁾⇥A:c=x y+z, c=y,{x, z}\{y}=;o . For each c2 A, f(c) =g₁(c) +g₂(c). The sumP

c2Ag₂(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¹, and then choose one of the pairs{x, z}2S_i²\{c, y}to obtain a solution c=x y+zwithc6=yand{x, z}\{y}=;.

Ifc /2T₁¹[· · ·[T_M¹, then the equationc+y=x+zwithc, y, x, andzall distinct has no solutions inA sog1(c) = 0. Assumec2T₁¹[· · ·[T_M¹.

Case 1: c /2T₁¹[· · ·[T_m¹.

By Corollary 3.3, there are two possibilities. One is that there is a uniquejwith c2T_j¹and sj 3. In this case,|S²_j| ^|A|₂ so g1(c) ^|A|₂ . The other possibility is thatc 2T_i¹\T_j¹ withs_i =s_j = 3 and i 6=j. In this case, g₁(c)4 because we can choose eitheri or j, and then one of the two pairs in S²_i or S_j² that does not containc.

Case 2: c2T₁¹[· · ·[T_m¹.

By Lemma 3.2,cis not in anyT_j¹ withsj 4 andc is in at most twoT_j¹’s with sj = 3. There are at most |A| T_i¹’s withc 2T_i¹ since there are at most|A| pairs {c, y}that containc sog₁(c)|A|+ 4.

In all cases,g₁(c)|A|+ 4 and X

c2A

f(c) =X

c2A

(g₁(c) +g₂(c))|A|(|A|+ 4) + 4|A| which proves the lemma.

Lemma 3.5. If g₁(c)is the function of Lemma 3.4, then 2

XM i=1

|S_i²|(|S_i²| 1) =X

c2A

g₁(c).

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

i=1|S_i²|(|S_i²| 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₁(c) and the other fromg₁(y).

By Lemma 3.5,

XM i=1

|S_i²|(|S_i²| 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₁, . . . , x_nare real numbers,t2{1,2, . . . , n 1}, and =¹_tP_t

i=1xi 1 n

P_n

i=1xi, then Xn

i=1

x²_i 1 n

Xn i=1

x_i

!2

+tn ² n t. A simple counting argument shows P

f(n) = ^|A|₂ (|A| 2). Let P

c2Af(c) =

|A|². 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₃⁺(N)F₃⁺(N), we get

= |A|

|A|

2 (|A| 2)

N |A| C

whereC is some absolute constant. By Lemma 3.6, Xf(n)²

|A|2

2(|A| 2)²

N +|A| ·N( |A| C)² N |A|

=

|A|

2

2(|A| 2)²

N + ²|A|³

⇣1 _|A|^C ⌘2

1 ^|A|_N . By (7) and (9),

Xf(n)²  X

f(n) +|A| 2X

c2A

f(c) + XM i=1

|S_i²|(|S_i²| 1)

!

+ 96|A|²

 |A|³ 2 +5|A|

2 X

c2A

f(c) + 96|A|²

= |A|³

✓1 + 5 2

◆

+ 96|A|².

Combining the two estimates onP

f(n)² gives the inequality

|A|2

2(|A| 2)²

N + ²|A|³

⇣1 _|A|^C ⌘2

1 ^|A|_N |A|³

✓1 + 5 2

◆

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

|A|

2

2(|A| 2)² N |A|³

2 + 96|A|².

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|⁷ , which follows from Lemma 3.4. For|A| 28, the maximum occurs when = 1 +_|A|⁷ 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₃⁺-set, or A⇢ZN is aB₃⁺-set andN odd.

Next we prove a lemma that corresponds to Lemma 3.2.

Lemma 4.1. If x2 T_i¹\T_j¹ 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¹\T_j¹| 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ⁱ₁, y, z, u, vare all distinct. This allows us to conclude thatT_i¹\T_j¹=;for anyi6=jwithsi 3 and s_j 3.

The assertion|T_i¹\T_j¹| 3 can be verified with some easy computations. Alter- natively, one can just ignoreaⁱ₃=uandbⁱ₃=vin Figure 1 to see|T_i¹\T_j¹| 3.

Corollary 4.2. If m+ 1i < jM, thenT_i¹\T_j¹=;.

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₃⁺-set or ifA⇢ZN is a B₃⁺-set andN is odd, then for any a2A, the number of distinct i2{1,2, . . . , m}such that a2T_i¹ is at most

|A|

2 .

Proof. To make the notation simpler, we suppose a 2 T_i¹ for 1  i  k and we will show k  ^|A|₂ . The case when a 2 T_i¹₁ \· · ·\T_i¹_k for some sequence 1  i₁ < · · · < i_k  m is the same. For this lemma we deviate from the notation S_i² = {{aⁱ₁, bⁱ₁}, . . .{aⁱ_si, bⁱ_si}}. Write S_i² = {{a, a_i},{b_i, c_i}} and a+a_i =b_i+c_i where 1ik, and for fixedi, the elementsa, a_i, b_i, andc_iare 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 1i, j k. These two sums must intersect and they cannot intersect at aj or ai, unlessi=j, so for 2jk,

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

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

a+a1 = b+c, a+a₂ = b+c₂,

... ... a+a_l = b+c_l, a+a_l+1 = b_l+1+c,

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

We will show thata₁, . . . , a_k, c₁, . . . , c_l, b_l+1, . . . , b_k are all distinct which implies 2k|A|.

Supposeai=bjfor some 2ilandl+1j 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_iand b_j are distinct for 2il and l+ 1j k. A similar argument shows thata_j andci are distinct forl+ 1jkand 2il.

Suppose now that ai = ci⁰ for some 2  i 6= i⁰  l. Then b+ci = a+ai = a+ci⁰ =a+ (a+ai⁰ b), so that 2b+ci = 2a+ai⁰. Since 2i⁰ l, these sums cannot intersect atband they cannot intersect ata. Ifc_i=a_i0, thena=bwhich is impossible. The equation 2b+c_i= 2a+a_i0 contradicts theB⁺₃ property. Note that 2b= 2aneed not imply a=b ifA⇢ZN with N even. We conclude thatai 6=ci⁰

for each 2i6=i⁰ l. Similarly,aj 6=bj⁰ forl+ 1j6=j⁰k.

The previous two paragraphs imply

{a₁, a₂, . . . , a_k}\{c₂, c₃, . . . , c_l, b_l+1, b_l+2, . . . , b_k}=;.

To finish the proof we show{c₂, c₃, . . . , c_l}\{b_l+1, b_l+2, . . . , b_k}=;. Supposec_i=b_j for some 2il andl+ 1jk. 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_iare all distinct whenever 1il. This is a contradiction. Therefore,c_i6=b_j for all 2iland l+ 1jk.

Lemma 4.4. If A⇢[N]is aB₃⁺-set, then X

c2A

f(c)|A|²

2 + 4|A|.

Proof. Again we writef as a sum of the simpler functionsg₁ andg₂. Recall that forc2A,

g₁(c) = #n

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

g2(c) = #n

({x, z}, y)2A⁽²⁾⇥A:c=x y+z, c=y,{x, z}\{y}=;o . For eachc2A,f(c) =g₁(c) +g₂(c). The sumP

c2Ag₂(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₁¹[· · ·[T_M¹, then the equationc+y=x+zwithc, y, x, andzall distinct has no solutions inA sog1(c) = 0. Assumec2T₁¹[· · ·[T_M¹.

Case 1: c /2T₁¹[· · ·[T_m¹.

By Corollary 4.2, there is a uniquej withc2T_j¹ andm+ 1jM. For such aj we have|S_j²|^|A|₂ by Corollary 4.2. There is a unique pair inS_j²that contains c so y is determined. There are at most ^|A|₂ choices for the pair{x, z}2S_j²\{c, y} so g₁(c)^|A|₂ .

Case 2: c2T₁¹[· · ·[T_m¹.

First assume c /2T_m+1¹ [· · ·[T_M¹. A solution toc+y=x+zwith c, y, x, and z all distinct corresponds to a choice of an S_i² with 1  i  m and c 2 T_i¹. By Lemma 4.3,cis in at most ^|A|₂ T_i¹’s and sog1(c) ^|A|₂ .

Lastly suppose c 2 T_m+1¹ [· · ·[T_M¹ . There is a unique j with c 2 T_j¹ and m+ 1  j  M. Furthermore, for this j we have |T_j¹| = 6 by Lemma 4.1. If c 2 T_i¹ with 1 im then, again by Lemma 4.1, |T_i¹\T_j¹| 3. There are ⁶₃ 3-subsets ofT_j¹ and given such a 3-subset, there are ³₁ ways to pair up an element in the 3-subset withcinS²_i. This impliesc is in at most 3 ⁶₃ S_i²’s with 1im, so g₁(c)  2 + 3 ⁶₃  ^|A|₂ . The 2 comes from choosing one of the two pairs in S_j²\{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|², then by (7) and (9), Xf(n)²|A|³

✓1 + 5 2

◆

+O(|A|²).

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

|A|2

2(|A| 2)²

3N + ²|A|³

⇣1 ^C_|A|⌘ 1 _3N^|A| |A|³

✓1 + 5 2

◆

+O(|A|²). (12) If = 0, then

|A|

2

2(|A| 2)² 3N  |A|³

2 +O(|A|²)

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

|A|(1 +o(1))(6 + 30 12 ²)^1/3N^1/3.

By Lemma 4.4, 0  ¹₂+_|A|³ . The maximum occurs when = ¹₂+_|A|³ 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/3whenA⇢ZNis aB₃⁺-set andN is odd.

5. Proof of Theorem 1.5(ii)

LetA⇢[N] be aB₄⁺-set. Forn2[ 2N,2N], define

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

Recall thatA⁽²⁾={{x, y}:x, y2A, x6=y}.

Lemma 5.1. If A⇢[N]is aB₄⁺-set, then Ais a B₂-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⁺₄ 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₄⁺-set, then for any integer n,f(n)2|A|.

Proof. Suppose f(n) 1. Fix a tuple ({a₁, a₂},{b₁, b₂}) counted by f(n). Let ({c₁, c₂},{d₁, d₂}) be another tuple counted byf(n), not necessarily di↵erent from ({a₁, a₂},{b₁, b₂}). Thena₁+a₂ b₁ b₂=c₁+c₂ d₁ d₂ so

a1+a2+d1+d2=c1+c2+b1+b2. (13) By the B₄⁺ 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₁, a₂}\{c₁, c₂} 6= ; or {b₁, b₂}\{d₁, d₂}6=;.

Case 1: {a₁, a₂}\{c₁, c₂}6=;.

Assumea₁=c₁. There are at most|A|choices forc₂so we fix one. The equality a₁=c₁ 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₁, d₂}such that (14) holds.

Case 2: {a₁, a₂}\{c₁, c₂}=;and {b₁, b₂}\{d₁, d₂}6=;.

Again there is no loss in assumingb₁=d₁. There are at most|A| choices ford₂ so fix one. The equality b₁=d₁ and (13) imply

c₁+c₂=a₁+a₂ b₂+d₂. (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₁, c₂},{d₁, d₂}). We have also accounted for the solution ({a₁, a₂},{b₁, b₂}) in our count sof(n)2|A|.

Lemma 5.3. If A⇢[N]is aB₄⁺-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₁, a₂},{b₁, b₂}),({c₁, c₂},{d₁, d₂}))

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₂+d₂=b₂+c₂so that{a₂, d₂}={b₂, c₂}. Since{a₁, a₂}\{b₁, b₂}=;, it must be the case that a₂ =c₂ and d₂ =b₂. 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₁, b₂}and{d₁, d₂}. Also observe that each n2A A withn 6= 0 has a unique representation as n=a₂ c₂ witha₂, c₂2A. This follows from the fact thatAis aB₂-set.

Case 2: {a₁, a₂}\{c₁, c₂}=;and {b₁, b₂}\{d₁, d₂}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|₂ ^|A|₂ ² . Using Cauchy-Schwarz, and Lemmas 5.3 and 5.2,

⇣ |A|

2 |A| 2 2

⌘2

4N  X

f(n)²

✓|A| 2

◆✓|A| 2 2

◆

+ 2|A| X

n2A A

f(n)

 |A|⁴

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

 |A|⁴

4 + 4|A|⁴=17|A|⁴ 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⁰ ⇢A such thatA⁰ is aB⁺_l -set and|A⁰| |A| 2l. If k= 2l+ 1, then there is a subsetA⁰⇢Asuch that |A⁰| |A| 2kandA⁰ 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₁, . . . , a_l}\{a_l+1, . . . , a_2l}=;. LetA⁰ =A\{a₁, a₂, . . . , a_2l}. If A⁰ is not a B⁺_l -set, then there is another set of 2lelements ofA⁰, sayb1, . . . , b2l, such that

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

and{b₁, . . . , b_l}\{b_l+1, . . . , b_2l}=;. Adding these two equations together gives a₁+· · ·+a_l+b₁+· · ·+b_l=a_l+1+· · ·+a_2l+b_l+1+· · ·+b_2l

with {a₁, . . . , a_l, b₁, . . . , 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⁰⇢A such that A⁰ is a B_l^⇤-set and |A⁰| |A| 2l. If k = 2l+ 1, then there is a subset A⁰ ⇢Asuch that |A⁰| |A| 2k andA⁰ 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)²=R1

0 |f(t)|^2jdt. The next lemma is (5.9) of [16].

Lemma 6.3. If A⇢[N]is aB_k^⇤-set, then X

k(n)²(1 +o(1))k²|A|X

k 1(n)². (17)

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

X

k 1(n)²⇣X

k(n)⌘^k_k ²₁

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