SHARP ESTIMATES FOR THE NUMBER OF SUM-FREE SETS

VSEVOLOD F. LEV

Abstract. For positive integer numbers k, l, and n, the first two of which are fixed and the last grows to infinity, we determine the asymptotic behavior of the number of integer sets A ⊆ [1, n] such that the equation a′_{1}+⋯+a′_{k} = a′′_{1}+⋯+a′′_{l} has no solutions in the elements of A. The problem of counting sets A with this property remains open only for a finite number of exceptional pairs (k, l).

1. Introduction and summary of results

Let k and l be fixed positive integer numbers such that l < k. A non-empty set of integers is said to be (k, l) sum-free if no sum of k of its elements equals to a sum of l elements. (The elements are not assumed to be distinct.) For a positive integer n, we are interested in (k, l) sum-free subsets A ⊆ [1, n], and we denote by SF_{k,l}[n] the family of all such A.

Trying to find large (k, l) sum-free subsets of [1, n], one readily discovers the sets

{r, r + d, …, r + ⌊(n − r)/d⌋d}  (1)

and

[⌊ln′/k⌋ + 1, n′],  (2)

where r, d, n′ ∈ [1, n] can be any integer numbers such that d ∤ (k − l)r. (We use the standard notation: ⌊x⌋, {x}, and ⌈x⌉ denote the integer part of x, the fractional part of x, and the least integer which is greater than or equals to x, respectively.) Plainly, not only sets (1) and (2), but also all their subsets are (k, l) sum-free. We refer to sets of the form (1) and their non-empty subsets as regular non-archimedian, and to sets of the form (2) and their non-empty subsets as regular archimedian. A routine computation gives the number of these sets; specifically, letting ρ be the smallest positive integer that does not divide the difference k − l, we have

Theorem 1. There is a positive constant ε = ε(k, l) such that for n → ∞ the number of regular non-archimedian sets is

c_{k,l,n} 2^{\frac{n}{ρ}} + O (2^{(\frac{1}{ρ} −ε)n}) ,

2 VSEVOLOD F. LEV

and the number of regular archimedian sets is

c′_{k,l,n} 2^{\frac{k−l}{k} n} + O(1);

here

c_{k,l,n} = ∑_{\begin{matrix}i=1 \\ (i,ρ)=1 \end{matrix}}^{ρ−1} 2^{1− \frac{i}{ρ} −\{\frac{n−i}{ρ}\}},  (3)

and

c′_{k,l,n} = \frac{2^{k−l−1}}{2^{k−l} − 1} ∑_{i=0}^{k−1} 2^{\{^{\frac{li}{k}}\}−(k−l)\{\frac{n−i}{k}\}}.  (4)

Moreover, the number of sets which are both regular archimedian and regular nonarchimedian is O(2^{\frac{k−l}{kρ} n}).

This theorem will be proved in Section 3. We note that the quantities c_{k,l,n} depend on k, l, and the residue class of n modulo ρ only, and that c′_{k,l,n} depend on k, l, and the residue class of n modulo k only. Moreover, c_{k,l,n} and c′_{k,l,n} are uniformly in n bounded away from zero and infinity.

Set (1) is largest when d = ρ and r = 1, and in this case it has 2^{\frac{1}{ρ} (1+o(1)) n} subsets. Set (2) is largest when n′ = n, in this case it has 2^{\frac{k−l}{k} (1+o(1)) n} subsets. Accordingly, we say that a pair (k, l) is non-archimedian if

\frac{k − l}{k} < \frac{1}{ρ} ,  (5)

archimedian if

\frac{k − l}{k} > \frac{1}{ρ} ,  (6)

and mixed if

\frac{k − l}{k} = \frac{1}{ρ} .  (7)

If we believe the non-regular sum-free subsets of [1, n] to be sporadic and scanty, then it follows from Theorem 1 that the total number of sum-free subsets is

|SF_{k,l}[n]| = c_{k,l,n} 2^{\frac{n}{ρ}} (1 + o(1))  (8)

for (k, l) non-archimedian,

|SF_{k,l}[n]| = c′_{k,l,n} 2^{\frac{k−l}{k} n} (1 + o(1))  (9)

for (k, l) archimedian, and

|SF_{k,l}[n]| = (c_{k,l,n} + c′_{k,l,n}) 2^{\frac{k−l}{k} n} (1 + o(1))  (10)

for (k, l) mixed. We will see that this analysis is accurate in the non-archimedian case and indeed, in this case (8) holds true. The archimedian and mixed cases are more delicate,

SHARP ESTIMATES FOR SUM-FREE SETS 3

however, as there exist non-regular A ∈ SF_{k,l}[n] of cardinality |A| ≥ (k − l)n/k + O(1), and the number of subsets of these A is ≫ 2^{(k−l)n/k}. For example, if 2k^{2} ≤ n′ ≤ n and k ∤ ln′, then the set

{⌊ln′/k⌋} ∪ [⌊ln′/k⌋ + k, n′ − k] ∪ {n′}

is easily seen to be (k, l) sum-free. It is unlikely that a simple closed form expression can be obtained for the number of non-regular A ∈ SF_{k,l}[n] of this kind; probably, the best we can hope for is to obtain, instead of (9) and (10), estimates of the sort

|SF_{k,l}[n]| ≤ (c′_{k,l,n} + c′′_{k,l,n}) 2^{\frac{k−l}{k} n} (1 + o(1))  (11)

for (k, l) archimedian, and

|SF_{k,l}[n]| ≤ (c_{k,l,n} + c′_{k,l,n} + c′′_{k,l,n}) 2^{\frac{k−l}{k} n} (1 + o(1))  (12)

for (k, l) mixed, with some c′′_{k,l,n} = O_{k,l}(1). Indeed, the ultimate goal of this paper is to prove (8), (11), and (12) for all pairs (k, l), save for a finite number of exceptions. The exceptional set E is the set of all those (k, l) that satisfy any of the following conditions:

i) (k, l) is non-archimedian and l ≤ 9; ii) (k, l) ∈ {(12, 10), (13, 11), (14, 12), (15, 13), (16, 14), (17, 15), (18, 16),

(14, 10), (15, 11), (16, 12), (17, 13), (18, 14), (19, 15), (20, 16),
(25, 19), (26, 20), (27, 21), (28, 22), (29, 23),
(11, 10)}

(all these pairs are easily verified to be non-archimedian); iii) (k, l) is archimedian or mixed and k ≤ 27.

l⧹k 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 \underline{2} 3 2 3 2 4 2 3 2 3 2 5 2 3 2 3 2 5 2
2  2 3 2 3 2 4 2 3 2 3 2 5 2 3 2 3 2 5
3  2 3 \underline{2} 3 2 4 2 3 2 3 2 5 2 3 2 3 2
4  2 \underline{3} 2 3 2 4 2 3 2 3 2 5 2 3 2 3
5  2 3 2 3 \underline{2} 4 2 3 2 3 2 5 2 3 2
6  2 3 2 3 2 4 2 3 2 3 2 5 2 3
7  2 3 2 3 2 4 \underline{2} 3 2 3 2 5 2
8  2 3 2 \underline{3} 2 4 2 3 2 3 2 5
9  2 3 2 3 2 4 2 3 \underline{2} 3 2
10  2 3 2 3 2 4 2 3 2 3
11  2 3 2 3 2 4 2 3 2
12  2 3 2 3 2 4 2 3
13  2 3 2 3 2 4 2
14  2 3 2 3 2 4
15  2 3 2 3 2
16  2 3 2 3

Table 1. The entry in the lth row and kth column indicates the value of ρ. It is typed in bold if the pair (k, l) is non-archimedian and \underline{underlined} if it is mixed.

4 VSEVOLOD F. LEV

Notice, that there is only a finite number of type i) pairs: indeed, condition (5) along with ρ ≥ 2 imply that for any such pair holds k < 2l ≤ 18. In fact, there are 46 exceptional non-archimedian and 218 exceptional archimedian and mixed pairs.

There is little doubt that (8), (11), and (12) hold for most (if not all) pairs (k, l) ∈ E as well, and we believe that many of these pairs can be dealt with using a suitable refinement of our method.

We now state our main result.

Theorem 2. Suppose that (k, l) ∉ E. Then there exists a positive constant ε = ε(k, l) such that

|SF_{k,l}[n]| = c_{k,l,n} 2^{\frac{n}{ρ}} + O (2^{(\frac{1}{ρ} −ε)n})

if (k, l) is non-archimedian,

|SF_{k,l}[n]| ≤ (c′_{k,l,n} + c′′_{k,l,n}) 2^{\frac{k−l}{k} n} + O (2^{(\frac{k−l}{k} −ε)n})

if (k, l) is archimedian, and

|SF_{k,l}[n]| ≤ (c_{k,l,n} + c′_{k,l,n} + c′′_{k,l,n}) 2^{\frac{k−l}{k} n} + O (2^{(\frac{k−l}{k} −ε)n})

if (k, l) is mixed. Here c_{k,l,n} and c′_{k,l,n} are defined as in (3) and (4), and

c′′_{k,l,n} = \frac{5}{2^{\frac{k−l}{k}} − 1}.

2. Historical background

Why do we care about the number of sum-free sets? Perhaps, this is because the problem has a structure flavor: we have to show that large sum-free sets possess a rigid structure.

Probably, sum-free sets were first introduced by Schur. His well-known result (considered now one of the origins of Ramsey theory) asserts that for t fixed and n ≥ n_{0}(t), it is impossible to partition the interval [1, n] into t sets free of solutions of the equation x + y = z. In our terminology such sets are (2, 1) sum-free.

The problem of counting sum-free sets was raised by Cameron and Erdős in [CE90]. Motivated, evidently, by Schur’s theorem, they considered (2, 1) sum-free subsets of [1, n] and conjectured that the number of such subsets is O(2^{n/2}). Among other results, Cameron and Erdős have shown that this estimate holds true for the number of sum-free subsets of the smaller interval [n/3, n]. Alon [A91], Calkin [C90], and independently Erdős and Granville (personal communication, see [CE90]) estimated from above the number of sum-free subsets of the whole interval [1, n] by 2^{(0.5+o(1))n}. Deshouillers, Freiman, Sós, and Temkin investigated in [DFST99] the structure of sum-free subsets of [1, n] of cardinality greater than 2n/5+O(1), which allowed them to estimate the number of these subsets by O(2^{n/2}).

SHARP ESTIMATES FOR SUM-FREE SETS 5

Calkin and Taylor showed in [CT96] that for l = 1 and k ≥ 3, the number of (k, l) sum-free sets is O(2^{(k−l)n/k}); in [CT98], Calkin and Thomson extended this estimate onto all pairs (k, l) such that k ≥ 4l − 1. (Observe, that all these pairs are archimedian.)

In [S00], Schoen established asymptotic formula (8) for pairs (k, l) satisfying some complicated, but not too restrictive condition. (All pairs satisfying the condition of Schoen can be shown to be non-archimedian.) We note that Schoen’s version of (8) is

|SF_{k,l}[n]| = (φ(ρ) + φ_{n}(ρ) + o(1)) 2^{⌊^{\frac{n}{ρ}}⌋},

where φ(ρ) is the number of positive integers co-prime with ρ and not exceeding ρ, and φ_{n}(ρ) is the number of positive integers co-prime with ρ and not exceeding ρ{n/ρ} (the remainder upon division of n by ρ). This looks apparently different from, but is essentially equivalent to (8).

Recently, Bilu [B99] proved (8) for (4, 3) sum-free sets, and Schoen [S00a] for (3, 2) sumfree sets. It went unnoticed that these results readily yield the asymptotic formula for all pairs (k, l) such that the difference k−l is odd and k ≤ 3l/2. Indeed, for any non-negative integer t we have SF_{k+t,l+t}[n] ⊆ SF_{k,l}[n]: if A ∉ SF_{k,l}[n], then there exist a′_{1}, …, a′′_{l} ∈ A such that a′_{1} + ⋯ + a′_{k} = a′′_{1} + ⋯ + a′′_{l}, whence a_{1} + ⋯ + a_{k} + ta_{1} = a′_{1} + ⋯ + a′_{l} + ta_{1} and A ∉ SF_{k+t,l+t}[n]. Similarly, if t is a positive integer then SF_{kt,lt}[n] ⊆ SF_{k,l}[n]. Hence, for k ≤ 3l/2 we have

SF_{k,l}[n] = SF_{3(k−l)+(3l−2k),2(k−l)+(3l−2k)}[n] ⊆ SF_{3(k−l),2(k−l)}[n] ⊆ SF_{3,2}[n].

In view of Schoen’s result, this gives the upper bound |SF_{k,l}[n]| ≤ c_{3,2,n} 2^{n/2}(1 + o(1)) and implies the asymptotic formula, since for k − l odd and k ≤ 3l/2 the pair (k, l) is non-archimedian and c_{3,2,n} = c_{k,l,n}. Moreover, as

SF_{2,1}[n] ⊇ SF_{3,2}[n] ⊇ SF_{4,3}[n],

results of Bilu and Schoen can be considered as a weak form of the conjecture of Cameron and Erdős.

In conclusion, we remark that there are 91 pairs (k, l) ∈ E such that k ≥ 4l − 1, and therefore the result of [CT98] reduces from 218 to 127 the number of those archimedian and mixed pairs for which the estimate |SF_{k,l}[n]| = O(2^{(k−l)n/k}) is not established. Furthermore, there are 13 pairs (k, l) ∈ E with k − l odd and k ≤ 3l/2, and the result of [S00a] (in conjunction with the observation above) reduces from 46 to 33 the number of those non-archimedian pairs for which we cannot prove (8). Altogether, we are left with 160 exceptions.

Acknowledgments

I started my work on sum-free sets when I was visiting the universities of Bordeaux and Basel (May – June 1999). I am deeply indebted to the faculty of the Mathematics Departments of these universities and particularly to Jean-Marc Deshouillers and David

6 VSEVOLOD F. LEV

Masser for the invitations and excellent working conditions. My special thanks to Yuri Bilu for extremely fruitful conversations. I appreciate a useful suggestion, concerning the estimates of ρ, due to Carl Pomerance. I am grateful to Tomasz Schoen for presenting me with copies of his preprints.

It is worth pointing out that my proof incorporates further development of some of the ideas of Schoen, and that the “archimedian/non-archimedian” terminology is due to Bilu (personal communication).

3. Counting regular sum-free sets

In this section we prove Theorem 1.

Lemma 3. Let M ≥ 1 be an integer. Then the number of integer sets A_{0} ⊆ [0, M] such that 0, M ∈ A_{0} and gcd(A_{0}) = 1 is 2^{M−1} + O(2^{M/2}).

Proof. The total number of A_{0} ⊆ [0, M] such that 0, M ∈ A_{0} is 2^{M−1}, and for each d | M the number of those A_{0} with d | gcd(A_{0}) is 2^{M/d−1}. Thus, the number of A_{0} with gcd(A_{0}) = 1 differs from 2^{M−1} by at most

∑_{\begin{matrix}d|M \\ d>1 \end{matrix}} 2^{M/d} = O(2^{M/2}).

□

For an integer set A ⊆ [1, n] of cardinality |A| ≥ 2 we write

r := min(A), d := gcd(A − r)  (13)

(so that A is contained in the arithmetic progression with the minimal element r and difference d), and we define n′ and M by

n′ := max(A) = r + Md.  (14)

Evidently, A is regular archimedian if and only if r > ln′/k. Also, A is regular nonarchimedian if and only if d ∤ (k − l)r: for if A ⊆ {r_{0}, r_{0} + d_{0}, …} where d_{0} ∤ (k − l)r_{0}, then d_{0} | d and r ≡ r_{0} (mod d_{0}), whence (k − l)r ≡ (k − l)r_{0} ≢ 0(mod d_{0}) and therefore d ∤ (k − l)r.

First, we count regular non-archimedian (k, l) sum-free sets. As there are only n one-element sets A ⊆ [1, n], we can ignore such sets for the rest of the proof. On the other hand, as we have just observed a set A ⊆ [1, n] of cardinality |A| ≥ 2 is regular non-archimedian if and only if d ∤ (k − l)r. By Lemma 3 the number of such sets is

∑_{\begin{matrix}r,M,d≥1 \\ r+Md≤n \\ d∤(k−l)r \end{matrix}}(2^{M−1} + O(2^{M/2})) = ∑_{d=ρ} + ∑_{d≥ρ+1},

and the second sum at the right is easy to estimate:

∑_{d≥ρ+1} = O(n^{3} 2^{\frac{n}{ρ+1}} ) = O (2^{(\frac{1}{ρ} −ε)n})

for any sufficiently small positive ε. To evaluate the sum with d = ρ we notice that ρ is a power of a prime number, and that ρ ∤ (k − l)r is therefore equivalent to (r, ρ) = 1. It follows that

∑_{d=ρ} = ∑_{\begin{matrix}r,M≥1 \\ (r,ρ)=1 \\ M≤(n−r)/ρ \end{matrix}} (2^{M−1} + O(2^{M/2}))

= ∑_{\begin{matrix}1≤r≤n−ρ \\ (r,ρ)=1 \end{matrix}} (2^{⌊^{\frac{n−r}{ρ}}⌋} + O(2^{n/2ρ}))

= ∑_{\begin{matrix}i=1 \\ (i,ρ)=1 \end{matrix}}^{ρ−1} ∑_{0≤t≤(n−i)/ρ −1} 2^{⌊^{\frac{n−i}{ρ}}⌋−t} + O(n2^{n/2ρ})

= ∑_{\begin{matrix}i=1 \\ (i,ρ)=1 \end{matrix}}^{ρ−1} 2^{⌊^{\frac{n−i}{ρ}}⌋}(2 + O(2^{−n/ρ})) + O(n2^{n/2ρ})

= 2^{\frac{n}{ρ}} ∑_{\begin{matrix}i=1 \\ (i,ρ)=1 \end{matrix}}^{ρ−1} 2^{1− \frac{i}{ρ} −\{\frac{n−i}{ρ}\}} + O(n2^{n/2ρ}).

This proves the “non-archimedian part” of Theorem 1, and we now turn to the “archimedian part.” As regular archimedian (k, l) sum-free sets are those for which r > ln′/k, the number of such sets is

∑_{n′=1}^{n} 2^{n′−⌊ \frac{ln′}{k} ⌋−1} = ∑_{i=0}^{k−1} 2^{i−⌊\frac{li}{k}⌋−1} ∑_{0≤t≤(n−i)/k} 2^{(k−l)t} + O(1)

= \frac{1}{2^{k−l} − 1} ∑_{i=0}^{k−1} 2^{i−⌊\frac{li}{k}⌋−1} 2^{(k−l)(⌊\frac{n−i}{k}⌋+1)} + O(1)

= \frac{2^{k−l−1}}{2^{k−l} − 1} ∑_{i=0}^{k−1} 2^{i−⌊\frac{li}{k}⌋+(k−l)⌊\frac{n−i}{k}⌋} + O(1)

= \frac{2^{k−l−1}}{2^{k−l} − 1} 2^{\frac{k−l}{k} n} ∑_{i=0}^{k−1} 2^{\{^{\frac{li}{k}}\}−(k−l)\{\frac{n−i}{k}\}} + O(1).

Finally, we count sets A ⊆ [1, n] which are both regular archimedian and regular nonarchimedian. All these A are subsets of sets of the form {n′, n′ − d, …, n′ − td}, where d ∤ (k − l) and t < (k − l)n′/kd (the latter condition is equivalent to n′ − td > ln′/k); therefore their number does not exceed

∑_{d=ρ}^{n} ∑_{n′=1}^{n} 2^{⌈\frac{k−l}{kd} n′⌉}.

Here the term corresponding to d = ρ is at most

2 ∑_{n′=1}^{n} 2^{\frac{k−l}{kρ} n′} = O(2^{\frac{k−l}{kρ} n}),

and the rest of the sum over d is at most

2n ∑_{n′=1}^{n} 2^{\frac{k−l}{k(ρ+1)} n′} = O(n 2^{\frac{k−l}{k(ρ+1)} n}) = O(2^{\frac{k−l}{kρ} n}).

This completes the proof.

4. Notation and preliminaries

Given a set of integers A ⊆ [1, n] of cardinality N := |A| ≥ 3, we define r, d, n′, and M by (13) and (14), and we normalize A letting

A_{0} := (A − r)/d (= {(a − r)/d: a ∈ A});  (15)

thus,

A_{0} ⊆ [0, M], 0, M ∈ A_{0}, and gcd(A_{0}) = 1.  (16)

Furthermore, we write

κ := ⌊\frac{M − 1}{N − 2}⌋ ,  (17)

so that

κ(N − 2) + 1 ≤ M ≤ (κ + 1)(N − 2).  (18)

We tacitly assume throughout the rest of the paper that A, A_{0}, r, d, M, N, and κ are related as in (13), (14), (15), and (17).

As it follows from the discussion in Section 1, to prove Theorem 2 we have to estimate the number of non-regular A ∈ SF_{k,l}[n]; disregarding for convenience sets of cardinality less than three (the number of such sets is O(n^{2})), we denote by B the family of all remaining “bad” sets:

B := {A ∈ SF_{k,l}[n]: A is not regular, and N := |A| ≥ 3}.

As observed above, non-regularity implies that

d | (k − l)r,  (19)

and that r ≤ ln′/k; the latter inequality can be re-written equivalently as k(n′ − Md) ≤ ln′, or

M ≥ \frac{k − l}{k} n′d^{−1}.  (20)

We want to show that

|B| = O (2^{(\frac{1}{ρ} −ε)n})

if (k, l) is non-archimedian, and that

|B| ≤ c′′_{k,l,n} 2^{\frac{k−l}{k} n} + O (2^{(\frac{k−l}{k} −ε)n}) ,

if (k, l) is archimedian or mixed.

For x > 1 we define

H(x) = \frac{ln x}{x} + \frac{x − 1}{x} ln \frac{x}{x − 1}

so that H is a positive function, monotonically increasing on (1, 2], decreasing on [2, ∞), and satisfying

H(2) = ln 2, lim_{x→1+} H(x) = lim_{x→∞} H(x) = 0.

Lemma 4. Let U and V be positive integers such that U ≥ 2V. Then

ln \binom{U}{V} ≤ UH(U/V).

Proof. Let ξ = U/V. Using Stirling’s formula

ln W! = W ln W − W + \frac{1}{2} ln W + \frac{1}{2} ln 2π + \frac{θ_{W}}{12W} (0 < θ_{W} < 1),

we get

ln \binom{U}{V} ≤ U ln U − U + \frac{1}{2} ln U − \frac{1}{2} ln 2π + \frac{1}{12U}

− ξ^{−1}U ln ξ^{−1}U + ξ^{−1}U − \frac{1}{2} ln ξ^{−1}U

− (1 − ξ^{−1})U ln(1 − ξ^{−1})U + (1 − ξ^{−1})U − \frac{1}{2} ln(1 − ξ^{−1})U

= UH(ξ) + \frac{1}{2} (ln \frac{ξ^{2}}{ξ − 1} − ln 2U) + (\frac{1}{12U} − \frac{1}{2} ln π) .

It remains to observe that

\frac{ξ^{2}}{ξ − 1} ≤ ξ + 2 ≤ 2ξ ≤ 2U.

□

Proposition 5. Let r, d, M and N be positive integers such that M ≥ N − 1 ≥ 2, and let κ be defined by (17). Suppose that κ ≥ 2. Then the total number of sets A ⊆ [1, n] corresponding to the parameters r, d, M, and N is less than e^{H(κ)M}.

10 VSEVOLOD F. LEV

Proof. Obviously, the number of sets under consideration is at most the binomial coefficient \binom{M−1}{N−2}. We write ξ = (M − 1)/(N − 2) and use Lemma 4, taking into account that ξ ≥ κ ≥ 2:

\binom{M − 1}{N − 2} ≤ e^{H(ξ)(M−1)} < e^{H(κ)M}.

□

Proposition 5 estimates the number of all sets A corresponding to a prescribed system of parameters, be they (k, l) sum-free or not. However, it will be seen later that for all, but a “small” number of A ∈ B, the values of κ and M are related: if κ is small then so is M; therefore, the product H(κ)M is small always.

We need yet another property of the function H.

Lemma 6. For any real numbers U, V, and W satisfying

3 ≤ U ≤ V < W, W ≥ 12

the function H(x)/(W − x) attains its maximum value on the interval [U, V] at one of the endpoints:

max_{x∈[U,V]} \frac{H(x)}{W − x} = max \{\frac{H(U)}{W − U} , \frac{H(V)}{W − V} \} .

Proof. Let f(x) := H(x)/(W −x). The derivative f′(x) is of the same sign as the function

g(x) := H′(x)(W − x) + H(x)

= ln x − (\frac{W}{x^{2}} − \frac{2}{x} + 1) ln(x − 1).

As g(3) < 0, it suffices to show that g has at most one root on (3, W). Indeed, if x_{0} ≈ 3.1 is the root of the equation 2(x − 1) ln(x − 1) = x, then g is decreasing on (3, x_{0}) and increasing on (x_{0}, W) in view of

g′(x) = \frac{1}{x} − \frac{1}{x − 1} (\frac{W}{x^{2}} − \frac{2}{x} + 1) + ln(x − 1) (\frac{2W}{x^{3}} − \frac{2}{x^{2}} )

= \frac{W − x}{x^{3}(x − 1)} (2(x − 1) ln(x − 1) − x).

The result follows. □

5. Auxiliary results on set addition

For positive integers h, h_{1}, and h_{2} and an integer set A define

hA := {a_{1} + ⋯ + a_{h}: a_{1}, …, a_{h} ∈ A}

and

h_{1}A − h_{2}A := {a′ − a′′: a′ ∈ h_{1}A, a′′ ∈ h_{2}A}.

The condition that A is (k, l) sum-free can be written as

kA ∩ lA = ∅,

or equivalently in any of the following forms:

(kA_{0} + (k − l)rd^{−1}) ∩ lA_{0} = ∅,  (21)
((k − l)A_{0} + (k − l)rd^{−1}) ∩ (lA_{0} − lA_{0}) = ∅.  (22)

Moreover, if we define (h_{1}A_{0} − h_{2}A_{0})_{+} to be the set of all non-negative elements of h_{1}A_{0} − h_{2}A_{0}, then (22) is equivalent to

((k − l)A_{0} + (k − l)rd^{−1}) ∩ (lA_{0} − lA_{0})_{+} = ∅.  (23)

(Notice, that (k − l)rd^{−1} is an integer for a non-regular A.)

The following result is one of our main tools.

Theorem 7 (Lev [L97]). Let h_{1} and h_{2} be non-negative integers such that h = h_{1}+h_{2} ≥ 1, and let A_{0} ⊆ [0, M] be a set of N := |A_{0}| ≥ 3 integers satisfying 0, M ∈ A_{0} and gcd(A_{0}) = 1. Suppose that κ is defined by (17). Then

|h_{1}A_{0} − h_{2}A_{0}| ≥ \begin{cases}B_{h}(N) & if h ≤ κ, \\ B_{κ}(N) + (h − κ)M & if h ≥ κ, \end{cases}

where B_{j}(N) = \frac{1}{2}j(j + 1)(N − 2) + j + 1.

Corollary 8. Let A_{0} ⊆ [0, M] be a set of N := |A_{0}| ≥ 3 integers such that 0, M ∈ A_{0} and gcd(A_{0}) = 1, and let κ be as in (17). Suppose that h ≥ κ is an integer. Then

|hA_{0}| ≥ (h − \frac{1}{2}κ) M + 2.

Proof. By Theorem 7 and using (18) we get

|hA_{0}| ≥ \frac{1}{2}κ(κ + 1)(N − 2) + (h − κ)M + κ + 1

≥ \frac{1}{2}κM + (h − κ)M + 2.

□

Corollary 9. Let A_{0} ⊆ [0, M] be a set of N := |A_{0}| ≥ 3 integers such that 0, M ∈ A_{0} and gcd(A_{0}) = 1, and let κ be as in (17). Suppose that h ≥ κ/2 is an integer. Then

|(hA_{0} − hA_{0})_{+}| > (h − \frac{1}{4}κ) M.

Proof. Observing that hA_{0} − hA_{0} is symmetrical about zero, by Theorem 7 and using (18) we get

|(hA_{0} − hA_{0})_{+}| = \frac{1}{2}(|hA_{0} − hA_{0}| + 1)

≥ \frac{1}{4}κ(κ + 1)(N − 2) + \frac{1}{2}(2h − κ)M + \frac{1}{2}κ + 1

> \frac{1}{4}κM + (h − \frac{1}{2}κ) M.

□

To deal with the case κ ≤ 2 we need results about the structure (rather than cardinality) of the sets hA − hA; these results can be derived from Theorem 7 also. Specifically, we show that for h large enough sets hA − hA contain “long” continuous blocks of integers, centered about zero.

Lemma 10. Let A_{0} ⊆ [0, M] be a set of N := |A_{0}| ≥ 3 integers such that 0, M ∈ A_{0} and gcd(A_{0}) = 1, and let κ be as in (17). Suppose that κ = 1. Then

[−|2A_{0}| + 1, |2A_{0}| − 1] ⊆ 2A_{0} − 2A_{0}.

Proof. In view of the symmetry of the set 2A_{0} − 2A_{0} around zero, it suffices to show that [1, |2A_{0}| − 1] ⊆ 2A_{0} − 2A_{0}. We assume that g ∉ 2A_{0} − 2A_{0} and g ≥ 1, and we prove that g ≥ |2A_{0}|. For this we notice first that 2A_{0} and 2A_{0} + g are non-intersecting subsets of [0, 2M + g], whence 2M + g + 1 ≥ 2|2A_{0}|. Now by Theorem 7 (in fact, this special case of the theorem is due to Freiman, see [F66]) we have |2A_{0}| ≥ M + N, and therefore g ≥ 2(M + N) − 2M − 1 = 2N − 1 > M. Next, by the boxing principle from g ∉ 2A_{0} − 2A_{0} we derive

|[0, g − 1] ∩ 2A_{0}| + |[g, 2g − 1] ∩ 2A_{0}| ≤ g,

and it follows that

g ≥ |2A_{0} ∩ [0, 2g − 1]| = |2A_{0}|.
□

Back to the case of κ arbitrary, using Corollary 8 (and keeping its notation) we have

2(|κA_{0}| − 2) ≥ (2κ − κ)M > κM − 1,

whence

\frac{κM − 1}{|κA_{0}| − 2} < 2.

Therefore we can apply Lemma 10 to the set κA_{0} ⊆ [0, κM] to obtain

SHARP ESTIMATES FOR SUM-FREE SETS 13

Corollary 11. Let A_{0} ⊆ [0, M] be a set of N := |A_{0}| ≥ 3 integers such that 0, M ∈ A_{0} and gcd(A_{0}) = 1, and let κ be as in (17). Then

[−|2κA_{0}| + 1, |2κA_{0}| − 1] ⊆ 2κA_{0} − 2κA_{0}.

Lemma 12. Let A_{0} ⊆ [0, M] be a set of N := |A_{0}| ≥ 3 integers such that 0, M ∈ A_{0} and gcd(A_{0}) = 1, and let κ be as in (17). Suppose that h ≥ 2κ is an integer. Then

[−(h − κ/2)M, (h − κ/2)M] ⊆ hA_{0} − hA_{0}.

Proof. It suffices to prove the assertion for h = 2κ, as evidently

((h + 1)A_{0} − (h + 1)A_{0}) ⊇ (hA_{0} − hA_{0}) + {−M, 0, M}.

The result is now immediate from Corollary 11, for

|2κA_{0}| − 1 > (2κ − \frac{1}{2}κ) M

by Corollary 8. □

Remark . Combining Corollary 11 with Theorem 7 (instead of Corollary 8), we could draw a somewhat stronger conclusion:

[−U, U] ⊆ hA_{0} − hA_{0}, where U = (h − κ/2)M + κ((κ + 1)(N − 2) + 2 − M)/2.

For instance, for κ = 1, h = 2 this gives [−M − N + 1, M + N − 1] ⊆ 2A_{0} − 2A_{0}, against [−3M/2, 3M/2] ⊆ 2A_{0} − 2A_{0} guaranteed by Lemma 12. This, however, does not lead to any improvement of our further results.

6. More preparations

Given two positive real numbers U and V, we denote by B(U, V) the set of all those A ∈ B such that the value of κ = κ(A) defined by (17) is in the interval [U, V]. With a slight abuse of notation, we allow V < U (in which case B(U, V) = ∅) and V = ∞ in this definition.

Lemma 13. For μ ≥ 2 we have

|B(μ, ∞)| ≤ n^{4}e^{H(μ)n}.

Proof. To each A ∈ B(μ, ∞) there corresponds a quadruple (r, d, M, N) such that

κ = ⌊\frac{M − 1}{N − 2}⌋ ≥ μ.  (24)

Conversely, there are (trivially) at most n^{4} quadruples (r, d, M, N) satisfying (24), and by Proposition 5 the number of sets A corresponding to any such quadruple is less than e^{H(κ)M} < e^{H(μ)n}. □

We are now in a position to prove two results which are of crucial importance for our argument.

Proposition 14. Let A ∈ B, and suppose that κ = κ(A) ≤ l. Then

M < \frac{k − l}{k − κ} n.

Proof. We use (21) observing that both sets kA_{0} + (k − l)rd^{−1} and lA_{0} lie in the interval [0, kM + (k − l)rd^{−1}]. By Corollary 8 we have

|kA_{0}| ≥ (k − \frac{1}{2} κ) M + 2,
|lA_{0}| ≥ (l − \frac{1}{2} κ) M + 2,

and it follows by the boxing principle that

(k + l − κ)M + 4 ≤ kM + (k − l)rd^{−1} + 1,
(l − κ)M < (k − l)rd^{−1} = (k − l)(n′d^{−1} − M),
(k − κ)M < (k − l)n′d^{−1}.
□

Corollary 15. Suppose that k ≥ 12, and let μ ≥ 3 be an integer number. Then

|B(μ, l)| ≤ n^{4}e^{(k−l) max\{\frac{H(μ)}{k−μ} , \frac{H(l)}{k−l}\} n}.

Proof. If μ ≥ l + 1, there is nothing to prove. Assume that μ ≤ l. By Proposition 14, to each A ∈ B(μ, l) there corresponds a quadruple (r, d, M, N) such that

κ ∈ [μ, l] and M < \frac{k − l}{k − κ} n.  (25)

Conversely, there are at most n^{4} quadruples satisfying (25), and by Proposition 5 to any such quadruple there correspond less than

e^{(k−l) \frac{H(κ)}{k−κ} n} ≤ e^{(k−l) max_{μ≤κ≤l} \frac{H(κ)}{k−κ} n}

sets A. The result follows in view of Lemma 6 as applied with U = μ, V = l and W = k. (Notice that 3 ≤ μ = U ≤ l = V < k = W.) □

Proposition 16. Let A ∈ B, and suppose that κ = κ(A) ≤ min{k − l, 2l}. Then

M < \frac{k − l}{k − 3κ/4} n.

Proof. We use (23) observing that both sets (k − l)A_{0} + (k − l)rd^{−1} and (lA_{0} − lA_{0})_{+} lie in the interval [0, (k − l)M + max{(k − l)rd^{−1}, (2l − k)M}]. By Corollaries 8 and 9 we have

|(k − l)A_{0}| ≥ (k − l − \frac{1}{2} κ) M + 2,
|(lA_{0} − lA_{0})_{+}| > (l − \frac{1}{4} κ) M,

and it follows by the boxing principle that

(k − \frac{3}{4} κ) M + 2 < (k − l)M + max\{(k − l)rd^{−1}, (2l − k)M\} + 1,
(l − \frac{3}{4} κ) M < max\{(k − l)rd^{−1}, (2l − k)M\}.

Since

l − \frac{3}{4} κ > l − (k − l) = 2l − k,

we conclude that

(l − \frac{3}{4} κ) M < (k − l)rd^{−1} = (k − l)(n′d^{−1} − M),

(k − \frac{3}{4} κ) M < (k − l)n′d^{−1}.

□

Corollary 17. Suppose that k ≥ 9, and let μ ≤ min{k − l, 2l} be an integer number. Then

|B(3, μ)| ≤ n^{4}e^{(k−l) max\{\frac{H(3)}{k−9/4} , \frac{H(μ)}{k−3μ/4}\} n}.

Proof. If μ ≤ 2, there is nothing to prove. Assume that μ ≥ 3. By Proposition 16, to each A ∈ B(3, μ) there corresponds a quadruple (r, d, M, N) such that

κ ∈ [3, μ] and M < \frac{k − l}{k − 3κ/4} n.  (26)

Conversely, there are at most n^{4} quadruples satisfying (26), and by Proposition 5 to any such quadruple there correspond less than

e^{(k−l) \frac{H(κ)}{k−3κ/4} n} ≤ e^{(k−l) max_{3≤κ≤μ} \frac{H(κ)}{k−3κ/4} n}

sets A. The result follows in view of Lemma 6 as applied with U = 3, V = μ, and W = 4k/3. (Notice that U = 3 ≤ μ = V ≤ k − l < k < 4k/3 = W.) □

7. Estimates of ρ

For m ≥ 1 integer, we define ρ(m) to be the least positive non-divisor of m; thus ρ(k − l) = ρ. As a last step in our preparations for the proof of Theorem 2, we present two technical lemmas which establish estimates of the quantity ρ(m). (In fact, it is only the latter of the two lemmas that will be used in the course of the proof of Theorem 2, while the former is needed to prove the latter.)

Lemma 18. For any m ≥ 4 we have ρ(m) ≤ 2 log_{2} m + 2, where log_{2} stands for the base two logarithm.

16 VSEVOLOD F. LEV

Proof. Since m is divisible by any positive integer less than ρ(m), it is divisible by the least common multiple of all these integers: [1, 2, …, ρ(m) − 1] | m. Put t := ⌊(ρ(m) − 1)/2⌋, so that 2t ≤ ρ(m) − 1. By comparing the exponents with which a prime p enters the least common multiple [1, 2, …, 2t] and the binomial coefficient \binom{2t}{t}, we conclude that \binom{2t}{t} | [1, 2, …, 2t] and therefore

m ≥ \binom{2t}{t} ≥ \frac{4^{t}}{2t} ≥ \frac{2^{ρ(m)−2}}{ρ(m) − 2}.

Assuming that ρ(m) > 2 log_{2} m + 2 we obtain m > m^{2}/(2 log_{2} m), whence m < 2 log_{2} m, a contradiction. □

Remark. From the prime number theorem one derives easily that ρ(m) ≤ ln m (1+o(1)). However, for our purposes it is preferable to have an explicit estimate, even with a weaker constant.

Lemma 19. Let m be a positive integer number.

i) For m ≥ 4 we have

\frac{4mH(m)ρ(m)}{4mρ(m) − 3m + 4} < ln 2;

ii) for m = 6 and for m ≥ 8 we have

\frac{H(m + 1)ρ(m)}{ρ(m) − 1} < ln 2;

iii) for m ≥ 8 we have

H(mρ(m) − m + 1)ρ(m) < ln 2;

iv) for m ≥ 25 we have

H(m)ρ(m) < ln 2.

Proof. The proofs of all four assertions can be conducted in a similar manner: for m large enough we use the fact that both H(m) and ρ(m) are “small”, and then small values of m can be dealt with using a straightforward computation. Here we only consider m large, leaving the rest for the reader.

i) We make two observations: firstly, 4mρ(m) − 3m + 4 > 2mρ(m), and secondly, H(m) < (ln m + 1)/m. Thus for m ≥ 10 we have

\frac{4mH(m)ρ(m)}{4mρ(m) − 3m + 4} < \frac{2}{m} (ln m + 1) < \frac{3}{m} ln m < ln 2.

ii) Similarly, for m ≥ 10 we have

\frac{H(m + 1)ρ(m)}{ρ(m) − 1} < \frac{ln m + 1}{m} \frac{ρ(m)}{ρ(m)/2} < \frac{3}{m} ln m < ln 2.

iii) For m ≥ 25 the estimate follows from iv) in view of mρ(m) − m + 1 > m. iv) By Lemma 18, for m ≥ 200 we have

H(m)ρ(m) < \frac{2}{m} (ln m + 1)(log_{2} m + 1) < \frac{2}{m} ln 3m log_{2} 2m < \frac{6}{ln 2} \frac{ln^{2} 3m}{3m} < ln 2.

□

8. Proof of Theorem 2: non-archimedian case

In this section we assume (k, l) to be non-archimedian. For further references, we mention the following consequences of (5):

i) \frac{k−l}{k} < \frac{1}{ρ} ≤ \frac{1}{2}, whence k ≥ 2(k − l) + 1 and

l + 1 ≤ k ≤ 2l − 1;  (27)

ii) (k − l)ρ < k, whence (k − l)ρ ≤ k − 1 and

\frac{k − l}{k − 1} ≤ \frac{1}{ρ};  (28)

iii) (k − l)ρ < k = (k − l) + l, whence

l ≥ (k − l)(ρ − 1) + 1.  (29)

8.1. Estimating |B(1, 2)|.

Lemma 20. Suppose that l ≥ 4. Then

|B(1, 2)| ≤ n^{3} 2^{\frac{k−l}{k} n}.

Proof. For A ∈ B(1, 2) we define

λ := lM − (k − l)rd^{−1},  (30)

so that

λ = lM − (k − l)(n′d^{−1} − M) = k (M − \frac{k − l}{k} n′d^{−1}) ≥ 0  (31)

since A is non-regular (recall (20)). By (22) we have (k − l)rd^{−1} ∉ (lA_{0} − lA_{0}), and since [−(l − 1)M, (l − 1)M] ⊆ (lA_{0} − lA_{0}) by Lemma 12 (recall that l ≥ 4 ≥ 2κ), we get (k − l)rd^{−1} > (l − 1)M. It follows that

0 ≤ λ < M.  (32)

We notice now that λ ∈ lA_{0} − (k − l)rd^{−1}, whence λ ∉ kA_{0} by (21) and thus

λ ∉ 2A_{0}  (33)

in view of 2A_{0} ⊆ kA_{0}. From (32) and (33) we derive the result as follows.

There are at most n^{3} possibilities to choose r, M, and d, corresponding to a set A ∈ B(1, 2), and for each choice the value of λ is determined uniquely. Assuming r, M, and d fixed, there are at most 2^{M−λ} possibilities to choose the set [λ + 1, M] ∩ A_{0}, and at most 3^{λ/2} possibilities to choose the set [1, λ − 1] ∩ A_{0} in such a way that (33) holds true —

18 VSEVOLOD F. LEV

the latter since no intersection {i, λ − i} ∩ A_{0} (1 ≤ i < λ/2) contains two numbers, and therefore there are at most three options for each intersection. Thus, the number of A associated with each fixed triple (r, d, M) is at most

2^{M−λ(1−ln 3/2 ln 2)} < 2^{M−λ/5} ≤ 2^{M−λ/k}.

It remains to observe that

M − \frac{λ}{k} = \frac{k − l}{k} n′d^{−1} ≤ \frac{k − l}{k} n

by (31). □

Remark . By (27), there is only a finite number of non-archimedian pairs (k, l) which do not satisfy the restriction l ≥ 4 of Lemma 20. All these pairs are included into the exceptional set E.

8.2. Estimating |B(3, k − l)|.

Lemma 21. Suppose that k ≥ 9 and (k, l) ∉ {(11, 6), (13, 9), (15, 8)}. Then there exists a positive constant ε = ε(k, l) such that

|B(3, k − l)| = O (2^{(\frac{1}{ρ} −ε)n}) .

Proof. As (k, l) is non-archimedian, we have min{k − l, 2l} = k − l by (27). Now Corollary 17 as applied with μ = k − l gives

|B(3, k − l)| ≤ n^{4}e^{(k−l) max\{\frac{H(3)}{k−9/4} , \frac{4H(k−l)}{k+3l}\} n},

and the result follows from Lemmas 22 and 23 below. (Notice that k − l ≥ 3 can be assumed as otherwise B(3, k − l) = ∅.) □

Lemma 22. Suppose that k − l ≥ 3, k ≥ 9, and (k, l) ∉ {(11, 6), (13, 9), (15, 8)}. Then

(k − l) \frac{H(3)}{k − 9/4} < \frac{ln 2}{ρ}.

Proof. Assume first that k ≥ 17. Then using (28) we get

(k − l) \frac{H(3)}{k − 9/4} = \frac{k − l}{k − 1} \frac{k − 1}{k − 9/4} \frac{H(3)}{ln 2} ln 2 ≤ \frac{ln 2}{ρ} \frac{16}{59/4} \frac{H(3)}{ln 2} < \frac{ln 2}{ρ}.

Now assume that 9 ≤ k ≤ 16. As k − l ≤ (k − 1)/2 by (28), the possible values of k − l are 3, 4, 5, 6, and 7. On the other hand, the assertion of the lemma can be re-written as

k > \frac{9}{4} + (k − l)ρ \frac{H(3)}{ln 2}.  (34)

One finds readily that (34) holds in any of the following cases: k − l = 3, k ≥ 8; k − l = 4, k ≥ 14; k − l = 5, k ≥ 12; k − l = 6, k ≥ 25; k − l = 7, k ≥ 16. It is easily seen, however, that the only non-archimedian pairs (k, l) with 9 ≤ k ≤ 16 which do not fall into any of these cases are the three pairs listed in the formulation of the lemma. □

Lemma 23. Suppose that k − l ≥ 3 and k ≥ 9. Then

(k − l) \frac{4H(k − l)}{k + 3l} < \frac{ln 2}{ρ}.

Proof. Assume first that k − l ≥ 4. Then using (29) we get

(k − l) \frac{4H(k − l)}{k + 3l} ρ = \frac{4(k − l)H(k − l)ρ}{(k − l) + 4l} ≤ \frac{4(k − l)H(k − l)ρ}{4(k − l)ρ − 3(k − l) + 4},

and the result follows from Lemma 19 i).

Now assume that k − l = 3. Then

(k − l) \frac{4H(k − l)}{k + 3l} = \frac{12H(3)}{4k − 9} ≤ \frac{12H(3)}{27} < \frac{ln 2}{2} = \frac{ln 2}{ρ}.

□

8.3. Estimating |B(k − l + 1, l)|. Set μ := max{k − l + 1, 3}. We actually estimate |B(μ, l)| instead of |B(k − l + 1, l)|; in view of Lemma 20, this suffices for our purposes.

Lemma 24. Suppose that (k, l) ∉ E. Then there exists a positive constant ε = ε(k, l) such that

|B(μ, l)| = O (2^{(\frac{1}{ρ} −ε)n}) .

Proof. The result follows by combining Corollary 15 with Lemmas 25 and 26 below; one only has to observe that if (k, l) ∉ E is a non-archimedian pair, then k ≥ 12, l ≥ 10, and at least one of the conditions i)–iv) of Lemma 26 holds true. □

Lemma 25. Suppose that k ≥ 12. Then

\frac{k − l}{k − μ} H(μ) < \frac{ln 2}{ρ},

unless (k, l) ∈ {(13, 9), (12, 7), (15, 8)}.

Proof. If k − l ≤ 2 then

\frac{k − l}{k − μ} H(μ)ρ ≤ \frac{2 · 3}{k − 3} H(3) ≤ \frac{6}{9} H(3) < ln 2.

Assume now that k − l = 6 or k − l ≥ 8. By (29),

\frac{k − l}{k − μ} H(μ)ρ = \frac{k − l}{l − 1} H(k − l + 1)ρ ≤ \frac{H(k − l + 1)ρ}{ρ − 1},

hence the result follows from Lemma 19 ii).

Finally, assume that k − l ∈ {3, 4, 5, 7}. The assertion of the lemma can be re-written as l > 1 + (k − l)H(k − l + 1)ρ/ ln 2, and it is readily seen that this holds in any of the following cases: k − l = 3, l ≥ 6; k − l = 4, l ≥ 10; k − l = 5, l ≥ 8; k − l = 7, l ≥ 9. However, it is easy to check (cf. Table 1) that the only non-archimedian pairs (k, l) with k − l ∈ {3, 4, 5, 7} and k ≥ 12 which do not fall into any of these cases are the three pairs indicated in the formulation of the lemma. □

20 VSEVOLOD F. LEV

Lemma 26. Suppose that any of the following holds:

i) k − l ∈ {1, 3, 5, 7}, l ≥ 10; ii) k − l ∈ {2, 4}, l ≥ 17; iii) k − l = 6, l ≥ 24; iv) k − l ≥ 8.

Then H(l) < ln 2/ρ.

Proof. By (29), for k − l ≥ 8 we have

H(l)ρ ≤ H((k − l)ρ − (k − l) + 1)ρ < ln 2

in view of Lemma 19 iii). For k − l ∈ [1, 7], the assertion can be verified by a straightforward computation. (Notice that if k − l ∈ {1, 3, 5, 7}, then ρ = 2; if k − l ∈ {2, 4}, then ρ = 3; finally, if k − l = 6, then ρ = 4.) □

8.4. Estimating |B(l + 1, ∞)|.

Lemma 27. Suppose that (k, l) ∉ E. Then there exists a positive constant ε = ε(k, l) such that

|B(l + 1, ∞)| = O (2^{(\frac{1}{ρ} −ε)n}) .

Proof. We have |B(l+1, ∞)| < e^{H(l)n} by Lemma 13, and H(l) < ln 2/ρ by Lemma 26. □

8.5. Completing the proof. The assertion of Theorem 2 for (k, l) non-archimedian is immediate from Theorem 1 and Lemmas 20, 21, 24, and 27.

9. Proof of Theorem 2: archimedian and mixed cases

In this section we assume that (k, l) satisfies (6) or (7), that is k ≤ (k − l)ρ. We notice that along with k ≥ 28 this implies

k − l ≥ 10.  (35)

(One verifies easily that mρ(m) ≤ 24 for any positive integer number m ≤ 9.)

9.1. Estimating |B(1, 2)|. Though Lemma 20 remains valid in the archimedian and mixed cases, we now need a stronger result.

Lemma 28. Suppose that k ≥ 28. Then there exists a positive constant ε = ε(k, l) such that

|B(1, 2)| ≤ \frac{3 · 2^{\frac{k−l}{k}}}{2^{\frac{k−l}{k}} − 1} 2^{\frac{k−l}{k} n} + O (2^{(\frac{k−l}{k} −ε)n}) .

SHARP ESTIMATES FOR SUM-FREE SETS 21

Proof. As in the non-archimedian case, for A ∈ B(1, 2) we define λ by (30). Then (31) and (33) hold true, and (32) is true, provided l ≥ 4. Trivially, (32) is also true if l = 1. We now show that if l ∈ {2, 3}, then

λ < \frac{3}{2} M.

Indeed, since under our assumptions k − l ≥ 28 − 3 > 2 ≥ κ and l > 1 ≥ κ/2, by Corollaries 8 and 9 we have

|(k − l)A_{0}| ≥ (k − l − \frac{κ}{2}) M + 2,
|(lA_{0} − lA_{0})_{+}| > (l − \frac{κ}{4}) M,

hence by (23)

(k − \frac{3}{4} κ) M + 2 < (k − l)M + (k − l)rd^{−1},
λ < \frac{3}{4} κM − 2 < \frac{3}{2}M.

We distinguish two cases, according to whether λ < M or λ > M. (Observe, that λ ≠ M in view of (33).) Given a triple (r, d, M) with 0 < λ < M, the number of A ∈ B(1, 2) corresponding to this triple is less than 2^{M−λ/5}, as in the proof of Lemma 20. Given a triple (r, d, M) with M < λ < 3M/2, we notice that by (21)

2M − λ = (k − l)rd^{−1} − (l − 2)M ∉ 2A_{0},

hence there are at most 3^{(2M−λ)/2} possibilities to choose A_{0} ∩ [1, 2M − λ − 1] and at most 2^{M−(2M−λ)} = 2^{λ−M} possibilities to choose A_{0} ∩ [2M − λ + 1, M]. Therefore, the number of A ∈ B(1, 2) corresponding to the triple (r, d, M) is at most

3^{(2M−λ)/2}2^{λ−M} = 2^{M−γ(2M−λ)} < 2^{M− \frac{γ}{3} λ},

where

γ = 1 − \frac{ln 3}{2 ln 2} ≈ 0.2075.

In any case, the number of A corresponding to a the triple (r, d, M) is at most

2^{M− \frac{γ}{3} λ} < 2^{M− \frac{λ}{k} − \frac{λ}{30}} = 2^{M−(M− \frac{k−l}{k} n′d^{−1})(1+ \frac{k}{30})} = 2^{\frac{k−l}{k} n′d^{−1}} 2^{− \frac{k}{30}(M− \frac{k−l}{k} n′d^{−1})},

and it follows that

|B(1, 2)| < ∑_{\begin{matrix}r,M,d≥1 \\ n′=r+Md≤n \\ M>(k−l)k^{−1}n′d^{−1} \end{matrix}} 2^{\frac{k−l}{k} n′d^{−1}} 2^{− \frac{14}{15}(M− \frac{k−l}{k} n′d^{−1})} = ∑_{d=1} + ∑_{d≥2} .

The sum over d ≥ 2 can be estimated as

∑_{d≥2} ≤ n^{3} 2^{\frac{k−l}{2k} n} = O (2^{(\frac{k−l}{k} −ε)n})

for ε small enough. The sum with d = 1 satisfies

∑_{d=1} ≤ ∑_{n′=2}^{n} 2^{\frac{k−l}{k} n′} ∑_{M>(k−l)k^{−1} n′} 2^{− \frac{14}{15}(M− \frac{k−l}{k} n′)}

≤ ∑_{n′=2}^{n} 2^{\frac{k−l}{k} n′} ∑_{j=0}^{∞} 2^{− \frac{14}{15} j}

< 2.5 ∑_{n′=2}^{n} 2^{\frac{k−l}{k} n′}

< 2.5 \frac{2^{\frac{k−l}{k} (n+1)}}{2^{\frac{k−l}{k}} − 1} .

□

In view of Theorem 1 and Lemma 28, to complete the proof of the archimedian and mixed cases of Theorem 2 it suffices to show that

|B(3, ∞)| = O (2^{(\frac{k−l}{k} −ε)n})  (36)

for any archimedian or mixed pair (k, l) with k ≥ 28. We proceed by cases.

9.2. Suppose that k − l ≤ l. In this case, assuming k ≥ 28, by Corollaries 17 and 15 and Lemma 13 we have

|B(3, k − l)| < n^{4}e^{(k−l) max\{\frac{H(3)}{k−9/4} , \frac{4H(k−l)}{k+3l}\} n},  (37)
|B(k − l + 1, l)| < n^{4}e^{(k−l) max\{\frac{H(k−l+1)}{l−1} , \frac{H(l)}{k−l}\} n},  (38)
|B(l + 1, ∞)| < n^{4}e^{H(l+1)n}.  (39)

Taking into account (35) and the inequality l ≥ k/2 ≥ 14 we obtain

\frac{kH(3)}{k − 9/4} = \frac{k}{k − 9/4} H(3) ≤ \frac{28}{28 − 9/4} H(3) < ln 2,  (40)
\frac{4kH(k − l)}{k + 3l} ≤ \frac{4k}{k + 3k/2} H(10) = \frac{8}{5} H(10) < ln 2,  (41)
\frac{kH(k − l + 1)}{l − 1} ≤ \frac{2l}{l − 1} H(11) ≤ \frac{28}{13} H(11) < ln 2.  (42)

Furthermore,

\frac{kH(l)}{k − l} < ln 2 :  (43)

if k − l ≥ 25 then

\frac{kH(l)}{k − l} ≤ H(l)ρ ≤ H(k − l)ρ < ln 2

by Lemma 19 iv), while otherwise

k ≤ (k − l)ρ ≤ max_{10≤m≤24} mρ(m) = 120

whence l ≤ 110 and therefore

\frac{kH(l)}{k − l} ≤ \frac{l + 10}{10} H(l) < ln 2

by checking all l ∈ [14, 110] (or using calculus). Finally,

\frac{kH(l + 1)}{k − l} < \frac{kH(l)}{k − l} < ln 2  (44)

by (43). Now (36) follows by putting together (37)–(44).

9.3. Suppose that l < k − l ≤ 2l. If we assume k ≥ 28 then (37) remains valid and by Lemma 13,

|B(k − l + 1, ∞)| < n^{4}e^{H(k−l+1)n}.  (45)

Furthermore, (40) holds, and (36) follows once we observe that

\frac{4kH(k − l)}{k + 3l} ≤ \frac{4k}{k + 3k/3} H(k − l) ≤ 2H(10) < ln 2,
\frac{kH(k − l + 1)}{k − l} < 2H(k − l + 1) ≤ 2H(11) < ln 2.

9.4. Suppose that k − l ≥ 2l + 1 and l = 1. Then

|B(3, ∞)| < n^{4}e^{H(3)n}

by Lemma 13, and (36) follows from

\frac{kH(3)}{k − l} = \frac{k}{k − 1} H(3) ≤ \frac{28}{27} H(3) < ln 2.

9.5. Suppose that k − l ≥ 2l + 1 and l ≥ 2. Assuming that k ≥ 28, by Corollary 17 and Lemma 13 we have

|B(3, 2l)| < n^{4}e^{(k−l) max\{\frac{H(3)}{k−9/4} , \frac{H(2l)}{k−3l/2}\} n},
|B(2l + 1, ∞)| < n^{4}e^{H(2l+1)n}.

Furthermore, (40) holds and thus (36) follows from

\frac{kH(2l)}{k − 3l/2} ≤ \begin{cases}\frac{3l}{3l−3l/2} H(2l) = 2H(2l) < ln 2 & if l ≥ 5, \\ \frac{28}{28−3l/2} H(2l) < ln 2 & if 2 ≤ l ≤ 4 \end{cases}  (46)

(the latter by a direct computation), and

\frac{kH(2l + 1)}{k − l} < \frac{kH(2l)}{k − 3l/2} < ln 2

(by (46)).

This completes the proof of Theorem 2.

References

[A91] N. Alon, Independent sets in regular graphs and sum-free subsets of finite groups, Israel J. Math. 73 (1991), 247–256.

[B99] Y. Bilu, Sum-free sets and related sets, Combinatorica 18 (4) (1998), 449–459.

[C90] N.J. Calkin, On the number of sum-free sets, Bull. London Math. Soc. 22 (1990), 141-144.

[CT96] N.J. Calkin and A.C. Taylor, Counting sets of integers, no k of which sum to another, J. Number Theory 57 (1996), 323–327.

[CT98] N.J. Calkin and J.M. Thomson, Counting generalized sum-free sets, J. Number Theory 68 (1998), 151–160.

[CE90] P.J. Cameron and P. Erdős, On the number of sets of integers with various properties, in “Number Theory” (R.A. Mollin, Ed.), 61–79, de Gruyter, Berlin 1990.

[DFST99] J.-M. Deshouillers, G. Freiman, V. Sós and M. Temkin, On the structure of sum-free sets, Astérisque 258 (1999), 149–161.

[F66] G. Freiman, Foundations of a structure theory of set addition, Kazan 1966 [Russian]. English translation in: Translations of Math. Monographs 37 (1973), American Math. Soc., Providence.

[L97] V. Lev, Addendum to “Structure theorem for multiple addition”, J. Number Theory 65 (1) (1997), 96–100.

[S00] T. Schoen, A note on the number of (k, l) sum-free sets, Electronic Journal of Combinatorics 7 (1) (2000), #R30.

[S00a] T. Schoen, The number of (2,3)-sum-free subsets of {1, …, n}, Acta Arithmetica 98 (2) (2001), 155–163.

Department of Mathematics, University of Haifa at Oranim, Tivon 36006, Israel.

  E-mail address: seva@math.haifa.ac.il