BLOCKS AND PROGRESSIONS IN SUBSET SUM SETS

VSEVOLOD F. LEV

Abstract. Let A be a finite set of positive integers and let A^{∗} be the set of all subset sums of A. We show that if A is dense enough (say, A ⊆ [1, l] and |A| ≥ 5(l ln l)^{1/2}), then A^{∗} contains a long block of consecutive integers or at least a long homogeneous arithmetic progression. This refines earlier results due to Freiman and Sárközy.

1. The background

Most problems in additive number theory share, with some deviations, the same common pattern: given a set A of positive integers, show that the set of all numbers representable as a sum of elements of A is “large”. The exact meaning of “large” can vary: one may actually count the numbers representable, or may wish to prove that there are, say, perfect squares, or prime numbers among them. Here we are concerned with the situation when A is finite, the summands are pairwise distinct, and any number of summands is allowed. (For the case of A infinite see Appendix; for representations with repetitions see [S89, Le97]; for representations with a fixed number of summands see Section 4.)

We let

A^{∗} := {a_{1} + ⋯ + a_{k}: a_{1} < … < a_{k}, a_{1}, …, a_{k} ∈ A},

the set of all integers representable as a sum of a number of pairwise distinct elements of A. Plainly, A^{∗} ⊆ [0, σ(A)], where σ(A) is the sum of all elements of A; moreover, A^{∗} is symmetric about σ(A)/2, the midpoint of the interval: s ∈ A^{∗} if and only if σ(A) − s ∈ A^{∗}. It is the set A^{∗} which is to be shown “large”.

Perhaps, the most radical approach is to prove that A^{∗} contains long blocks of consecutive integers, provided that A is sufficiently dense. It is

1991 Mathematics Subject Classification. Primary: 11B05; Secondary: 11B13, 11B25, 05D05, 11P99.

2 VSEVOLOD F. LEV

easily seen, however, that A^{∗} may fail to contain such blocks; this happens, for instance, if all or almost all elements of A have a common divisor d > 1. For this reason, instead of a block of integers one may seek in A^{∗} an arithmetic progression of the form

{(m + 1)d, (m + 2)d, …, (m + M)d}.

Such progressions are called homogeneous; they are just sets of consecutive multiples of an integer number d.

Two results in this direction were established independently and almost simultaneously by Freiman and Sárközy.

Theorem A (Freiman, [Fr93]). There exist absolute positive constants c_{1} and c_{2} with the following property. Let A ⊆ [1, l] be a set of n = |A| integers satisfying n > c_{1}(l ln l)^{1/2}. Write σ(A) = ∑_{a∈A} a. Then there is a positive integer d ≤ 3l/n such that A^{∗} contains all multiples of d which fall into the interval

[\frac{1}{2} σ(A) − c_{2}dn^{2}, \frac{1}{2} σ(A) + c_{2}dn^{2}].

Theorem B (Sárközy, [S94, Theorem 4]). Let A ⊆ [1, l] be a set of n = |A| integers satisfying

l > 2500, n > 200(l ln l)^{1/2}.

Then there are integers y, z, and d ≥ 1 such that

d < 10^{4} \frac{l}{n}, z > 7^{−1}10^{−4} n^{2}, \frac{z}{y} > 7^{−1}10^{−4} \frac{n^{2}}{l} ,

and {yd, (y + 1)d, …, zd} ⊆ A^{∗}.

Both theorems impose similar density restrictions on A, both give similar bounds for the difference d and the number of terms of the progression. The minor discrepancy is that Theorem A guarantees that the progression is centered about σ(A)/2, while Theorem B provides, instead, a lower bound for the “logarithmic length” (z/y) of the progression.

There is a number of papers where other results of this kind are obtained; we mention [AF88, Li89, C90, EF90, GM91, Le97] and [C99]. Theorems A and B, however, are most applicable and strongest up to date in the sense that the assumption n ≫ (l ln l)^{1/2} is less restrictive than those made elsewhere. (The only exception is [C99, Corollary 2.9] which is based on Theorem A and inherits its assumption.)

BLOCKS AND PROGRESSIONS IN SUBSET SUM SETS 3

2. The results

We develop Theorems A and B in the following directions.

First, we extend significantly the length of the progression which is guaranteed to exist in A^{∗} and show that in fact this progression stretches almost onto the whole interval [0, σ(A)].

Second, we formulate an arithmetic condition such that if A satisfies this condition, then the progression in question has difference one and is, therefore, a block of consecutive integers. Our condition is, in a sense, the weakest possible.

Third, we get rid of unspecified or excessively large constants replacing them by reasonably small ones.

For y and z real, y ≤ z, we denote by [y, z] the set of all integer numbers between y and z. Given a positive integer q, by N_{q}(A) we denote the number of elements of A, not divisible by q.

Theorem 1. Let A ⊆ [1, l] be a set of n = |A| ≥ n_{0} integers, where n_{0} is a sufficiently large absolute constant. Suppose that

n ≥ 20(l ln n)^{1/2}

and that for any positive integer q < 2l/n holds N_{q}(A) ≥ q − 1 . Then

[λ σ(A), (1 − λ) σ(A)] ⊆ A^{∗},

where σ(A) is the sum of all elements of A and λ = 280l/n^{2}.

We postpone the proof of this and other results of this paper (that will be presented shortly) until Sections 4–7.

Remarks.

1) The value of λ cannot be replaced by λ_{0} = l/2n^{2}: for any l and n such that 3n ≤ l ≤ n^{2}/6 there exist an n-element set A ⊆ [1, l] satisfying N_{q}(A) ≥ q − 1 for any q < 2l/n and an integer s ∈ [λ_{0}σ(A), (1 − λ_{0})σ(A)] such that s ∉ A^{∗}. To see this, take A = [l − (n − 1), l], h = ⌊l/(n − 1)⌋ − 1 > l/(2(n − 1)) > l/(2n) and s = hl, so that λ_{0}σ(A) ≤ s ≤ (1 − λ_{0})σ(A) (as follows by an easy verification). Then s cannot be represented as a sum of h + 1 or more distinct elements of A, for any such sum is greater than (h + 1)(l − (n − 1)) = s + (l − (h + 1)(n − 1)) ≥ s; and similarly, s cannot be represented as a sum of h or less distinct elements of A.

4 VSEVOLOD F. LEV

2) If A contains less than q−1 elements not divisible by q for an integer q ≥ 1, then it can happen that some residue classes modulo q are not represented in A^{∗}. (For instance, consider the situation when each a ∈ A is either zero or one modulo q.) Clearly, in this case A^{∗} does not contain q consecutive integers.

3) It is easily seen that for any fixed ε > 0 and n large enough, the condition n ≥ 20(l ln n)^{1/2} follows from n ≥ (10\sqrt{2} + ε)(l ln l)^{1/2}. Thus, we have in effect replaced Freiman’s constant c_{1} and Sárközy’s constant 200 by the constant 10\sqrt{2}. It will be seen later that 10\sqrt{2} can be further reduced to a value smaller than 5, but this comes at the expense of decreasing the block length.

As a corollary, we show that even if A fails to satisfy N_{q}(A) ≥ q − 1 for all q < 2l/n, the subset sum set A^{∗} still contains a long homogeneous progression. Let σ(A), λ, and N_{q}(A) be as in Theorem 1.

Corollary 1. Let A ⊆ [1, l] be a set of n = |A| ≥ n_{0} integers, where n_{0} is a sufficiently large absolute constant. Suppose that

n ≥ 20(l ln n)^{1/2}.

Then there exists a positive integer d < 2l/n such that A^{∗} contains all multiples of d that fall into the interval

I_{A} := [λ σ(A), (1 − λ) σ(A)].

Moreover, if N_{q}(A) ≥ q − 1 for any positive integer q < 2l/n, then one can take d = 1. Otherwise, one can take d to be the maximal number q < 2l/n for which N_{q}(A) < q − 1; in this case the set of all multiples of d that fall into I_{A} is contained already in A_{d}^{∗}, where A_{d} = {a ∈ A: a ≡ 0(mod d)}.

In applications, one sometimes is less concerned with the block (or progression) length and cares more about the density requirement and small values of n. For this reason we also provide a result which merely sharpens the constants of Theorem B.

Theorem 2. Let A ⊆ [1, l] be a set of n = |A| integers satisfying

n > 10(l ln n)^{1/2}

BLOCKS AND PROGRESSIONS IN SUBSET SUM SETS 5

(equivalently, l < 0.01n^{2}/ ln n). Then there are integers y, z, and d ≥ 1 such that

d < 6 \frac{l}{n}, z − y > \frac{n^{2}}{20}, \frac{z − y}{y} > \frac{n^{2}}{115l},

and {yd, (y + 1)d, …, zd} ⊆ A^{∗}.

Since the factor 10 (in the condition n > 10(l ln n)^{1/2}) is often more important than other constants, we give yet another version of this theorem.

Theorem 2′. Let A ⊆ [1, l] be a set of n = |A| ≥ 3803 integers satisfying

n > 7(l ln n)^{1/2}.

Then there are integers y, z, and d ≥ 1 such that

d < 5 \frac{l}{n}, z − y > \frac{n^{2}}{405}, \frac{z − y}{y} > \frac{n^{2}}{2425l},

and {yd, (y + 1)d, …, zd} ⊆ A^{∗}.

Remark. Observe that for any fixed ε > 0 and n large enough, the condition n > 7(l ln n)^{1/2} follows from n > (7/\sqrt{2} + ε)(l ln l)^{1/2}; furthermore, 7/\sqrt{2} ≈ 4.949.

3. The method

We prove Theorems 2 and 2′ in Section 5 and then derive Theorem 1 in Sections 6 and 7. Our proof of Theorems 2 and 2′ follows the lines of [S94] where their prototype, Theorem B, is established.

To prove Theorem B, Sárközy uses a result about arithmetic progressions in the set

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

(all integers, representable as a sum of precisely h pairwise distinct elements of A).

Theorem C (Sárközy, [S94, Theorem 3]). Let A ⊆ [1, l] be a set of n = |A| integers such that

l > 2500, n > 100(l ln l)^{1/2}.

Write L = ln(13l/n). Then for every integer M satisfying

l ≤ M ≤ 10^{−4} \frac{n^{2}}{L}

there exist positive integers d and h such that

d < 4828 \frac{l}{n}, h < 8496 \frac{M}{n}

and the set h · A contains an M-term homogeneous arithmetic progression of difference d.

As shown in [S94], this theorem is best possible save for the constants and logarithmic factors.

To upgrade Theorem B to Theorems 2 and 2′ we establish in Section 4 a refined version of Theorem C.

Theorem 3. Let A ⊆ [1, l] be a set of n = |A| integers. Write L = ln(4l/n). Then for every M satisfying

4l ≤ M ≤ \frac{n^{2}}{12L}.

there exist positive integers d and h such that

d < 4 \frac{l}{n}, h < 6 \frac{M}{n} ,

and the set h · A contains a homogeneous arithmetic progression of difference d and at least M + 1 terms. Moreover, d and h can be so chosen that 2d divides h.

Remarks.

1) Though in Theorem 3 we don’t impose any explicit restrictions on l or n, some are implied by the assumptions. For instance, from l ≥ n it follows that L ≥ ln 4 > 4/3, whence n^{2} ≥ 48lL > 64n, n > 64; we use this observation in the proof in Section 4.

2) Some further minor improvements of the constants are possible. Also, there is the usual trade-off: some of the constants can be improved at the expense of the others. In fact, for any ε > 0 we can find c = c(ε) > 0 and C = C(ε) > 0 such that if

cl ≤ M ≤ \frac{n^{2}}{CL},

then d and h exist so that d < (1 + ε)l/n and h < (1 + ε)M/n.

Once Theorem 3 is proven, Theorems 2 and 2′ are relatively easy to deduce; this is done in Section 5.

BLOCKS AND PROGRESSIONS IN SUBSET SUM SETS 7

Theorem 1 is derived from Theorem 2 in Sections 6 and 7. Among the rest, the proof uses some ideas from [AF88, C99]. Corollary 1 is proven in Section 8.

The reason why we believe that strengthening Theorems A and B is worthwhile is that they are used in the proofs of many important results in additive number theory. Replacing these theorems with Theorems 1, 2, and 2′ can lead to improvements in these results. We give an example in the Appendix.

Notation. Throughout the rest of the paper we continue to use the above introduced notation, unless indicated otherwise. Specifically, A is a finite, non-empty set of positive integers; l is a real number such that A ⊆ [1, l]; the cardinality of A is n = |A|; the sum of elements of A is denoted by σ(A); the number of elements of A, not divisible by an integer q ≥ 1, is denoted by N_{q}(A); the set of all numbers, representable as a sum of precisely h distinct elements of A, is h · A, and A^{∗} = ∪_{h=0}^{n} h · A is the subset sum set of A; finally, λ = 280l/n^{2}. Also, we write hA for the set of all numbers, representable as a sum of precisely h not necessarily distinct elements of A:

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

4. Fixed number of summands: proof of Theorem 3

Our proof of Theorem 3 employs the same idea as that of Theorem C. However, we replace the key component of the proof, Sárközy’s theorem [S89, Theorem 1], by the following result of ours.

Theorem 4 (Lev, [Le97, Theorem 3 ii)]). Let S ⊆ [0, l] be a set of |S| ≥ 3 integers such that 0, l ∈ S and gcd(S) = 1. Write

k = ⌊\frac{l − 1}{|S| − 2}⌋ ,

ρ = (k + 1)(|S| − 2) + 2 − l.

Suppose that h ≥ 3k is an integer number. Then hS contains a block of (h − k)l + kρ + 1 consecutive integers.

Another new ingredient we introduce in the proof is the following lemma.

8 VSEVOLOD F. LEV

Lemma 1. Let A be a set of n = |A| integers. For t = 1, 2, … denote by S_{t} the set of all integers s ∈ 2A which have at least t representations as s = a_{1} + a_{2} (a_{1}, a_{2} ∈ A), and let N_{t} = |S_{t}| be the cardinality of S_{t}. Then

N_{1} + ⋯ + N_{τ} ≥ 2nτ − τ^{2}

for any τ = 1, …, n.

Remark . Case τ = n is immediate (with equality sign) and was utilized in the original argument of Sárközy. Case τ = 1 is easy.

Proof of Lemma 1. The shortest way to prove the lemma is to derive it from a result of Pollard [P74] which says that if p is a prime number, A_{1} and A_{2} are non-empty sets of residues modulo p, and N_{t} is the number of residues modulo p with at least t representations as a_{1} + a_{2} (a_{i} ∈ A_{i}), then

N_{1} + ⋯ + N_{τ} ≥ τ min{|A_{1}| + |A_{2}| − τ, p}

for any τ = 1, …, min{|A_{1}|, |A_{2}|}. Now choose A_{1} = A_{2} to be the canonical image of A in ℤ/pℤ, where p is a sufficiently large prime number. □

From now on, we adopt S_{t} and N_{t} (not to be confused with N_{q}(A)!) as a standard notation.

Corollary 2. Let A, n, l and L be as in Theorem 3. Then there exists t ∈ [1, n] such that

N_{t} > \frac{n}{2} max \{\frac{n}{tL}, 1\} + 2.  (1)

Proof. Assume the opposite:

N_{t} ≤ \frac{n}{2} max \{\frac{n}{tL}, 1\} + 2; t = 1, …, n.  (2)

Set τ = ⌊3n/4⌋. Taking into account that N_{t} < 2l for any t, by Lemma 1 and (2) we get

2nτ − τ^{2} ≤ N_{1} + ⋯ + N_{τ}

< ∑_{1≤t≤n^{2}/4lL} 2l + ∑_{n^{2}/4lL<t≤n/L} (\frac{1}{2} \frac{n^{2}}{tL} + 2) + ∑_{n/L<t≤τ} (\frac{1}{2} n + 2)

≤ \frac{n^{2}}{2L} + 2(τ − 1) + \frac{1}{2} \frac{n^{2}}{L} (\frac{4lL}{n^{2}} + ln \frac{4l}{n}) + \frac{1}{2} n (τ + 1 − \frac{n}{L})

= \frac{1}{2} n^{2} + \frac{1}{2} nτ + (2l + \frac{1}{2} n + 2τ − 2) .

BLOCKS AND PROGRESSIONS IN SUBSET SUM SETS 9

(We use here the estimate ∑_{P <t≤Q} t^{−1} ≤ P^{−1} + ln Q/P. Also, the number of summands in ∑_{n/L<t≤τ} is at most τ + 1 − n/L, as τ + 1 > 3n/4 > n/L in view of L > 4/3.) This implies that

\frac{1}{16} n^{2} < (τ − \frac{3}{4} n)^{2} + (2l + \frac{1}{2} n + 2τ − 2)

< 2l + \frac{1}{2} n + 2τ − 1

≤ 2l + 2n − 1,

l > \frac{n^{2}}{32} − n > \frac{n^{2}}{64} > \frac{n^{2}}{48L},

contrary to the assumption that 4l ≤ M ≤ n^{2}/12L. □

Yet another lemma we need to prove Theorem 3 is parallel to [S94, Lemma 1].

Lemma 2. Let A be a set of integers, and suppose that h < ⌈(t + 3)/4⌉ is a positive integer. Then hS_{t} ⊆ 2h · A.

Sketch of the proof. Use induction on j = 1, …, h to show that jS_{t} ⊆ 2j · A. Let s_{1} + ⋯ + s_{j−1} + s_{j} be an element of jS_{t}. By the induction hypothesis, there is a representation s_{1} + ⋯ + s_{j−1} = a_{1} + ⋯ + a_{2j−2} with a_{i} ∈ A all distinct, and the assumption on h ensures that s_{j} has a representation s_{j} = a′ + a′′ with a′ ≠ a′′ and both a′ and a′′ distinct from all a_{i}. □

Proof of Theorem 3. We choose t ∈ [1, n] satisfying (1), and we put

d := gcd(S_{t} − S_{t}), S′_{t} := {d^{−1}(s − min(S_{t})): s ∈ S_{t}}, l′ := max(S′_{t}).

Thus, S′_{t} ⊆ [0, l′], 0, l′ ∈ S′_{t}, gcd(S′_{t}) = 1 and |S′_{t}| = N_{t}. Set

k := ⌊\frac{l′ − 1}{N_{t} − 2}⌋ ,
ρ := (k + 1)(N_{t} − 2) + 2 − l′.

For future references we note that

k(N_{t} − 2) < l′ ≤ \frac{1}{d} (max(S_{t}) − min(S_{t})) < \frac{2l}{d},  (3)

hence by (1) and 4l ≤ M ≤ n^{2}/12L,

d < \frac{2l}{k(N_{t} − 2)} < \frac{4l}{kn} min \{\frac{tL}{n}, 1\} ,  (4)
k < \frac{4l}{dn} min \{\frac{tL}{n}, 1\} ,  (5)
t > \frac{kdn^{2}}{4lL} ≥ \frac{3kdM}{l} ≥ 12kd.  (6)

We define now

h_{0} := max \{2k, ⌈\frac{M − kρ}{l′}⌉\} + k + δ, h = 2h_{0},

where δ ∈ [0, d−1] is chosen so that d | h_{0}. As h_{0} ≥ 3k, by Theorem 4 the set h_{0}S′_{t} contains a block of at least (h_{0}−k)l′+kρ+1 ≥ ⌈(M −kρ)/l′⌉l′+kρ+1 ≥ M + 1 consecutive integers, hence h_{0}S_{t} contains a homogeneous arithmetic progression of difference d and at least M + 1 terms. To complete the proof it suffices to show that

h_{0} < min \{\frac{t}{4}, 3 \frac{M}{n} \}  (7)

(the estimate d < 4l/n was already established in (4)): then by Lemma 2 we have h·A = 2h_{0} ·A ⊇ h_{0}S_{t}, whence h · A contains a homogeneous arithmetic progression of difference d and at least M + 1 terms.

Evidently, (7) will follow from

3k + d − 1 < min \{\frac{t}{4}, 3 \frac{M}{n} \} ,  (8)

and

\frac{M − kρ}{l′} + k + d < min \{\frac{t}{4}, 3 \frac{M}{n} \} .  (9)

To prove (8) we observe that by (4),

3k + d − 1 < 3k + \frac{4l}{kn} min \{\frac{tL}{n}, 1\} − 1.

We consider the right-hand side as a function of k ∈ [1, K], where

K := \frac{4l}{n} min \{\frac{tL}{n}, 1\}

(cf. (5)) and we denote this function by f(k). Now (8) follows from the fact that f is convex,

f(1) = \frac{4l}{n} min \{\frac{tL}{n}, 1\} + 2 ≤ min \{\frac{t}{12} + 2, \frac{M}{n} + 2\} ≤ min \{\frac{t}{4}, 3 \frac{M}{n} \} ,

(notice that t > 12 by (6)), and

f(K) = \frac{12l}{n} min \{\frac{tL}{n}, 1\} ≤ min \{\frac{t}{4}, 3 \frac{M}{n} \} .

Finally, to prove (9) we consider two cases: k = 1 and k ≥ 2.

If k = 1 then by (3) and (1)

\frac{M − kρ}{l′} + k + d < \frac{M − ρ + 2l}{l′} + 1

= \frac{M − (2N_{t} − 2 − l′) + 2l}{l′} + 1

≤ \frac{3M/2 − 2(N_{t} − 1)}{l′} + 2

< \frac{3M/2}{N_{t} − 2}

< 3 \frac{M}{n} min \{\frac{tL}{n}, 1\}

≤ min \{\frac{t}{4}, 3 \frac{M}{n} \} .

If k ≥ 2 then by (3) and (5)

\frac{M − kρ}{l′} + k + d < \frac{M + 2l}{l′} + k

< \frac{M + 2l}{n} min \{\frac{tL}{n}, 1\} + k

< \frac{M + 6l}{n} min \{\frac{tL}{n}, 1\}

< 3 \frac{M}{n} min \{\frac{tL}{n}, 1\}

≤ min \{\frac{t}{4}, 3 \frac{M}{n} \} .

□

12 VSEVOLOD F. LEV

5. Proof of Theorems 2 and 2′

We only sketch the proof of Theorem 2 which essentially follows that of Theorem B and indicate how it is to be modified to obtain Theorem 2′.

We need a lemma which is a minor variation of [S94, Lemma 3].

Lemma 3. Let U, V and d be positive integers and let B ⊆ [U, V] be a set of integers. Then for any s ∈ B^{∗} such that d|s, s ≤ U(|B| − d) there exists s′ ∈ B^{∗} satisfying

d | s′, 0 < s′ − s ≤ V d.

Proof. Choose S ⊆ B such that s = ∑_{b∈S} b. As

U|S| ≤ s ≤ U(|B| − d),

we have |B \ S| ≥ d, and therefore there is a set S_{0} ⊆ B \ S of cardinality 0 < |S_{0}| ≤ d such that ∑_{b∈S_{0}} b ≡ 0(mod d). We define S′ := S ∪ S_{0} and s′ := ∑_{b∈S′} b; then

s′ − s = ∑_{b∈S_{0}} b ≤ V |S_{0}| ≤ V d

and the validity of d|s′ is obvious from the construction. □

To prove Theorem 2 we write A = {a_{1}, …, a_{n}} (the elements being numbered in increasing order) and set

j := ⌊0.7n⌋, A_{1} := {a_{1}, …, a_{j}}, A_{2} := {a_{j+1}, , …, a_{n}}.

(For Theorem 2′, set j := ⌊0.99n⌋.) We apply Theorem 3 to the set A_{1} ⊆ [1, a_{j}] of cardinality j = |A_{1}| and with M = 4l. (Verification of the condition M ≤ |A_{1}|^{2}/12L, or equivalently j^{2} ≥ 48l ln(4a_{j}/j), is left to the reader; hint: 4a_{j}/j < 4l/j ≤ n, and j^{2} > 0.49n^{2} − 1.4n.) We conclude that there exist integers d, h ≥ 1 and y such that

{yd, (y + 1)d, …, (y + 4l)d} ⊆ h · A_{1}  (10)

and

d < 4 \frac{a_{j}}{j} , h < 24 \frac{l}{j} ;  (11)

we observe, moreover, that (11) implies

d < 4\frac{l}{j} < 6 \frac{l}{n}

BLOCKS AND PROGRESSIONS IN SUBSET SUM SETS 13

and

yd ≤ ha_{j} < 24 \frac{la_{j}}{j} .  (12)

Next, applying Lemma 3 to the set B = A_{2} ⊆ [a_{j}, l] we see that for any s ∈ A_{2}^{∗} such that d|s and s ≤ a_{j}(n − j − d) there exists s′ ∈ A_{2}^{∗} such that d|s′ and s′ − s ≤ ld. Along with (10) this shows that

{yd, (y + 1)d, …, (⌊a_{j}(n − j − d)/d⌋ + 1)d + (y + 4l)d} ⊆ A_{1}^{∗} + A_{2}^{∗} = A^{∗}.

We put

z := ⌊\frac{a_{j}(n − j − d)}{d}⌋ + 1 + (y + 4l),

so that by (11)

z − y > \frac{a_{j}(n − j)}{d} + (4l − a_{j}) > \frac{a_{j}(n − j)}{d}

> \frac{1}{4} j(n − j) ≥ \frac{0.21}{4} n^{2} > \frac{1}{20} n^{2}.

It remains to notice that by (12)

\frac{z − y}{y} > \frac{a_{j}(n − j)}{yd} > \frac{j(n − j)}{24l} ≥ \frac{0.21}{24} \frac{n^{2}}{l} > \frac{n^{2}}{115l}.

Remark . It is clear that the above argument actually gives slightly better constants than those indicated in the formulation of Theorems 2 and 2′. In particular, the reader can easily verify that our proof of Theorem 2 remains valid if the assumption n ≥ 10(l ln n)^{1/2} is relaxed to n ≥ 9.95(l ln n)^{1/2}. This observation will be used in Section 7 to avoid further loss of accuracy.

6. Auxiliary results on addition in ℤ_{q}

We say (modifying slightly the terminology of [C90, C99]) that a set of integers A is q-complete if A^{∗}(mod q) = ℤ_{q}; in other words, if all residues modulo q are represented in A^{∗}. In the spirit of the two papers just mentioned, we establish here a sufficient condition for q-completeness.

Lemma 4. Let A be a finite set of integers and let q ≥ 1 be an integer number. Suppose that N_{d}(A) ≥ d − 1 for any d | q. Then A is q-complete.

Proof. We can assume that A is finite, and we use induction by n = |A|. Write A = {a_{1}, …, a_{n}} and A_{i} = {a_{1}, …, a_{i}} (1 ≤ i ≤ n) and let overlined characters denote canonical images in ℤ_{q}. Suppose that a_{i} are so numbered

14 VSEVOLOD F. LEV

that Ā_{1}^{∗} ⊊ ⋯ ⊊ Ā_{j}^{∗} and that either A_{j} = A, or (Ā_{j} ∪ {ā})^{∗} = Ā_{j}^{∗} for any a ∈ A \ A_{j}. In the former case we have j = n and accordingly

|Ā^{∗}| = |Ā_{j}^{∗}| ≥ j + 1 = |A| + 1 ≥ N_{q}(A) + 1 ≥ q

which proves the assertion. We assume, therefore, that the second possibility takes place, which translates easily into Ā_{j}^{∗} + ā = Ā_{j}^{∗} (for any a ∈ A \ A_{j}).

Consider the subgroup of all g ∈ ℤ_{q} satisfying Ā_{j}^{∗} + g = Ā_{j}^{∗} and write this subgroup as dℤ_{q}, where d is a divisor of q. (This subgroup is often called the period, or stabilizer of Ā_{j}^{∗}.) The condition Ā_{j}^{∗} + ā = Ā_{j}^{∗} means that ā ∈ dℤ_{q}, that is d | a, and it follows that δ | a for any divisor δ | d. This shows that N_{δ}(A_{j}) = N_{δ}(A) ≥ δ − 1, provided δ | d. By the induction hypothesis, A_{j} is d-complete; that is, Ā_{j}^{∗} contains representatives of all dℤ_{q}-cosets. Now Ā_{j}^{∗} = Ā_{j}^{∗} + dℤ_{q} = ℤ_{q}, implying the result. □

Corollary 3. Suppose that A ⊆ ℤ satisfies N_{q}(A) ≥ q − 1 for any q ≤ Q. Then A is q-complete for any q ≤ Q.

Lemma 5 (Chaimovich, [C99, Lemma 2.3]). If A is q-complete then there is a subset A_{0} ⊆ A of cardinality |A_{0}| ≤ q − 1 which is q-complete also.

Proof. As in the proof of the previous lemma, we use overlined characters to denote canonical images in ℤ_{q}. Let A_{0} = {a_{1}, …, a_{k}} ⊆ A be a subset of minimum cardinality such that Ā_{0}^{∗} = ℤ_{q}, and let A_{j} = {a_{1}, …, a_{j}} (j = 1, …, k). If Ā_{1}^{∗} ⊊ ⋯ ⊊ Ā_{k}^{∗} then q = |Ā_{k}^{∗}| ≥ k + 1, as wanted. Otherwise, there is an index j ≤ k − 1 such that Ā_{j}^{∗} = Ā_{j+1}^{∗}. But in this case we would have

Ā_{0}^{∗} = Ā_{j+1}^{∗} + {ā_{j+2}, …, ā_{k}}^{∗} = Ā_{j}^{∗} + {ā_{j+2}, …, ā_{k}}^{∗} = {ā_{1}, …, ā_{j}, ā_{j+2}, …, ā_{k}}^{∗}

contradicting minimality of A_{0}. □

7. Proof of Theorem 1

Lemma 6. For any C, ε > 0 and K ≥ 2 there exists n_{0} = n_{0}(C, ε, K) with the following property. Let Q ≥ 2 and let A ⊆ [1, l] be a set of integers of cardinality n = |A| ≥ C(l ln l)^{1/2}, n ≥ n_{0} satisfying N_{q}(A) ≥ Kq for all q ∈ [2, Q]. Then there is a subset A_{0} ⊆ A such that

i) K^{−1}n < |A_{0}| < (1 + ε)K^{−1}n; ii) σ(A_{0}) < (1 + ε)K^{−1}σ(A); iii) N_{q}(A_{0}) ≥ q for all q ∈ [2, Q].

Proof. Fix arbitrarily p ∈ (K^{−1}, (1 + ε)K^{−1}), p < 1 and set

δ := \frac{1}{2} min\{1 − (pK)^{−1}, (1 + ε)(pK)^{−1} − 1\}.

Define P (q) := e^{− \frac{1}{2} δ^{2}pKq}. As the series ∑_{q=2}^{∞} P (q) converges, there is an integer Q_{0} = Q_{0}(p, K) such that ∑_{q=Q_{0}+1}^{∞} P (q) < 0.1.

The set A_{0} will be comprised of two parts. First, for each integer q ∈ [2, Q_{0}] we choose q arbitrary elements of A, not divisible by q, and we denote by A_{1} the set of all elements chosen. Plainly, |A_{1}| < \frac{1}{2} Q_{0}(Q_{0}+1). Second, we let A_{2} be the random subset of A to which any a ∈ A belongs with probability p (with all a ∈ A being selected independently). Thus |A_{2}| is distributed binomially with parameters n and p, and E |A_{2}| = pn. Eventually, we define A_{0} := A_{1} ∪ A_{2}.

Using an estimate for the right tail of binomial distribution (see, for instance, [JŁR, Theorems 2.1 and 2.10]) we get

Pr\{|A_{2}| ≤ (1 − δ)pn\} = Pr\{|A_{2}| ≤ (1 − δ) E |A_{2}|\} ≤ e^{− \frac{1}{2} δ^{2} E |A_{2}|} = e^{− \frac{1}{2} δ^{2}pn}.

As (1 − δ)p > K^{−1}, for n large enough this implies

Pr{|A_{0}| ≤ K^{−1}n} ≤ Pr{|A_{2}| ≤ (1 − δ)pn} < 0.1.

Similarly, in view of |A_{1}| = O_{p,K}(1) we have

Pr{|A_{0}| ≥ (1 + ε)K^{−1}n} ≤ Pr{|A_{2}| ≥ (1 + δ)pn} < 0.1;

therefore, i) fails with probability at most 0.2.

Furthermore, σ(A_{2}) := ∑_{a∈A_{2}} a is a random variable with expectation E σ(A_{2}) = pσ(A) and variance

Var σ(A_{2}) = p(1 − p) ∑_{a∈A} a^{2} < plσ(A).

By Chebychev’s inequality we have

Pr{σ(A_{2}) ≥ (1 + δ)pσ(A)} = Pr{σ(A_{2}) ≥ (1 + δ) E σ(A_{2})}

< \frac{plσ(A)}{(δ E σ(A_{2}))^{2}} = (δ^{2}p)^{−1} \frac{l}{σ(A)} < 2(δ^{2}p)^{−1} \frac{l}{n^{2}} < 0.1,

provided that n is large enough. As (1 + δ)p < (1 + ε)K^{−1} and in view of σ(A_{1}) = O(l) = o(σ(A)) this implies that

Pr{σ(A_{0}) ≥ (1 + ε)K^{−1}σ(A)} < 0.1;

that is, ii) fails with probability at most 0.1.

Finally, we take care of iii). For any integer q ∈ [Q_{0} + 1, Q] the random variable N_{q}(A_{2}) is distributed binomially with parameters N_{q}(A) and p, whence in view of q ≤ K^{−1}N_{q}(A) = (Kp)^{−1} E N_{q}(A_{2}) < (1 − δ) E N_{q}(A_{2}) we get

Pr{N_{q}(A_{2}) < q} ≤ Pr{N_{q}(A_{2}) < (1 − δ) E N_{q}(A_{2})}

< e^{− \frac{1}{2} δ^{2} E N_{q}(A_{2})} ≤ e^{− \frac{1}{2} δ^{2}pKq} = P (q)

(estimating the left binomial tail). It follows that the probability that there is a value of q ∈ [Q_{0} + 1, Q] such that N_{q}(A_{2}) < q, and therefore the probability that there is a value of q ∈ [2, Q] such that N_{q}(A_{0}) < q, is at most ∑_{q=Q_{0}+1}^{∞} P (q) < 0.1 (by the choice of Q_{0}). Therefore, iii) fails with probability 0.1 at most.

We see that the probability that any of conditions i)–iii) fails to hold is 0.2 + 0.1 + 0.1 < 1 at most. Hence, with a positive probability A_{0} satisfies all the properties required. □

Proposition 1. There exist positive constants K and n_{0} with the following property. Let A ⊆ [1, l] be a set of n = |A| ≥ n_{0} integers such that

n ≥ 9.96(l ln n)^{1/2}

and that N_{q}(A) ≥ Kq for any integer q ∈ [2, 7l/n]. Then there are integer numbers y and z such that [y, z] ⊆ A^{∗} and

z − y > \frac{n^{2}}{21}, \frac{z − y}{y} > \frac{n^{2}}{138l}.

Proof. Choose positive K and ε so that the former is sufficiently large and the latter is sufficiently small. By Lemma 6 and Corollary 3 there is a subset A_{0} ⊆ A of cardinality |A_{0}| < (1 + ε)K^{−1}n < 0.001n which is q-complete for any q ≤ 7l/n. Write A_{1} := A \ A_{0}, so that n_{1} := |A_{1}| > 0.999n. We have

n_{1} > 0.999 · 9.96(l ln n)^{1/2} > 9.95(l ln n_{1})^{1/2}

BLOCKS AND PROGRESSIONS IN SUBSET SUM SETS 17

and by Theorem 2 as applied to the set A_{1} (see also the remark at the end of Section 5), there exist integers y_{1}, z_{1} and d ≥ 1 such that {y_{1}d, (y_{1} + 1)d, …, z_{1}d} ⊆ A_{1}^{∗} and

d < 6 \frac{l}{n_{1}} < 7 \frac{l}{n},
z_{1} − y_{1} > \frac{n_{1}^{2}}{20} > \frac{n^{2}}{21},
\frac{z_{1} − y_{1}}{y_{1}} > \frac{n_{1}^{2}}{115l} > \frac{n^{2}}{116l}.

If d = 1 the assertion follows. Assuming that d ≥ 2, find B_{0} ⊆ A_{0} which is d-complete and such that |B_{0}| ≤ d − 1: this is possible by Lemma 5. Notice, that to any integer r ∈ [0, d − 1] there corresponds k_{r} ∈ [0, l − 1] such that r + k_{r}d ∈ B_{0}^{∗}. Now set y := (y_{1} + l)d and z := z_{1}d; then

z − y = (z_{1} − y_{1} − l)d > z_{1} − y_{1} > \frac{n^{2}}{21},

as z_{1} − y_{1} > n^{2}/21 > 2l ≥ ld/(d − 1). Furthermore, let κ = 116/21. If y_{1} ≥ κl then

\frac{z − y}{y} = \frac{z_{1}}{y_{1} + l} − 1 ≥ \frac{κ}{κ + 1} \frac{z_{1}}{y_{1}} − 1 > \frac{κ}{κ + 1} \frac{n^{2}}{116l} − 1 > \frac{n^{2}}{138l},

and if y_{1} ≤ κl then

\frac{z − y}{y} = \frac{z_{1}}{y_{1} + l} − 1 ≥ \frac{1}{κ + 1} \frac{z_{1}}{l} − 1 > \frac{1}{κ + 1} \frac{n^{2}}{21l} − 1 > \frac{n^{2}}{138l}.

To complete the proof we show that [y, z] ⊆ B_{0}^{∗}+A_{1}^{∗}. Indeed, given x ∈ [y, z] write x = r + kd where r ∈ [0, d − 1] and y_{1} + l ≤ k ≤ z_{1}. Then x = (r+k_{r}d)+(k−k_{r})d and it suffices to notice that y_{1} ≤ k−l < k−k_{r} ≤ z_{1}. □

As a next step, we show that the condition N_{q}(A) ≥ Kq of Proposition 1 can be relaxed considerably.

Proposition 2. Let A ⊆ [1, l] be a set of n = |A| ≥ n_{0} integers, where n_{0} is a sufficiently large absolute constant. Suppose that

n ≥ 9.96(l ln n)^{1/2}

and that N_{q}(A) ≥ q − 1 for any integer q < 2l/n. Then there are integer numbers y and z such that [y, z] ⊆ A^{∗} and

z − y > \frac{n^{2}}{21}, \frac{z − y}{y} > \frac{n^{2}}{138l}.

Proof. Let K be the constant of Proposition 1. If N_{q}(A) ≥ Kq for all integer q ∈ [2, 7l/n] then the result follows from Proposition 1. Otherwise, denote by q the maximal number such that 2 ≤ q ≤ 7l/n and N_{q}(A) < Kq. Let A_{0} be the set of all elements of A, not divisible by q, and let A_{1} be the set of integers such that A \ A_{0} = {qa: a ∈ A_{1}}. Evidently, we have A_{1} ⊆ [1, l_{1}] where l_{1} = ⌊l/q⌋ ≤ l/2. Furthermore, the cardinality of A_{1} satisfies n_{1} := |A_{1}| > n − Kq, and if n is large enough then q < 0.1K^{−1}n and n_{1} > 0.9n.

We want to apply Proposition 1 to the set A_{1}. We have

n_{1} > 0.9n ≥ 0.9 · 0.96(l ln n)^{1/2} > 0.96((l/2) ln n_{1})^{1/2} ≥ 0.96(l_{1} ln n_{1})^{1/2}

and for Proposition 1 to be applicable it is necessary and sufficient that N_{q_{1}}(A_{1}) ≥ Kq_{1} for any q_{1} ∈ [2, 7l_{1}/n_{1}]. Assume that this does not hold for some q_{1}. Then q_{1} ≤ 7l/(0.9n) ≤ 0.1K^{−1}n (again, assuming that n is sufficiently large), hence K(q + q_{1}) < 0.2n and therefore

\frac{l}{q} ≥ l_{1} > (n_{1} − Kq_{1})q_{1} > (n − K(q + q_{1}))q_{1} > 0.8nq_{1}, qq_{1} < 2 \frac{l}{n}.

Along with N_{qq_{1}}(A) < Kq + Kq_{1} ≤ Kqq_{1} this contradicts maximality of q.

We see that the conditions of Proposition 1 are fulfilled and there exist integers y_{1} and z_{1} such that

z_{1} − y_{1} > \frac{n_{1}^{2}}{21} > \frac{n^{2}}{26}, \frac{z_{1} − y_{1}}{y_{1}} > \frac{n_{1}^{2}}{138l_{1}} > \frac{n^{2}}{86l}

and [y_{1}, z_{1}] ⊆ A_{1}^{∗}. Notice, that the latter inclusion yields {y_{1}q, (y_{1} + 1)q, …, z_{1}q} ⊆ (A \ A_{0})^{∗}.

We have assumed that q ≤ 7l/n and we observe now that in fact, q < 2l/n holds, for

⌊\frac{l}{q} ⌋ = l_{1} ≥ n_{1} > 0.9n.

It follows that A, and therefore A_{0} also, is q-complete and, as in the proof of Proposition 1, we conclude that [y, z] ⊆ A^{∗} with y = (y_{1} + l)q and z = z_{1}q.

Finally, we have

z − y ≥ 2(z_{1} − y_{1} − l) ≥ 2(n^{2}/26 − l) > \frac{n^{2}}{21}

and to estimate (z − y)/y = z_{1}/(y_{1} + l) − 1 one can define κ = 86/26 and act as in the proof of Proposition 1. □

Proposition 3. Let A ⊆ [1, l] be a set of n = |A| ≥ n_{0} integers, where n_{0} is a sufficiently large absolute constant. Suppose that

n ≥ 20(l ln n)^{1/2}

and that N_{q}(A) ≥ 3q for any integer q ∈ [2, 5l/n]. Then

[λ σ(A), (1 − λ) σ(A)] ⊆ A^{∗}.

Proof. Set K = 2.008, fix ε positive and small enough and find a subset A_{0} ⊆ A satisfying conditions of Lemma 6. Write A_{1} := A \ A_{0}. We have

n_{0} := |A_{0}| > K^{−1}n ≥ 9.96(l ln n)^{1/2} ≥ 9.96(l ln n_{0})^{1/2}

and N_{q}(A_{0}) ≥ q −1 for any q ≤ 5l/n, hence for any q < 2l/n_{0}. Proposition 2 shows, therefore, that there is an interval [y, z] ⊆ A_{0}^{∗} such that z − y > n_{0}^{2}/21 > n^{2}/(21K^{2}) > l and (z − y)/y > n_{0}^{2}/(138l). Since the gaps between consecutive elements of A_{1}^{∗} do not exceed l, it follows that [y, σ(A_{1}) + z] ⊆ A_{0}^{∗} + A_{1}^{∗} = A^{∗}. We observe now that

y < 138 \frac{l}{n_{0}^{2}} z < 138K^{2} \frac{l}{n^{2}} σ(A_{0}) < 138(1 + ε)K \frac{l}{n^{2}} σ(A) < λσ(A)

and that

σ(A_{1}) + z ≥ σ(A) − σ(A_{0}) > (1 − (1 + ε)K^{−1})σ(A) > σ(A)/2.

Hence, [λσ(A), σ(A)/2] ⊆ A^{∗} and it remains to notice that A^{∗} is symmetric about σ(A)/2: if s ∈ A^{∗} then also σ(A) − s ∈ A^{∗} for any integer s. □

Finally, we are ready to prove Theorem 1. For this, we “improve” Proposition 3 in the same spirit as we did it with Proposition 1.

Proof of Theorem 1. The beginning of the proof runs as that of Proposition 2. If for any q ∈ [2, 5l/n] we have N_{q}(A) ≥ 3q, then the result follows at once by Proposition 3. Otherwise, let q ∈ [2, 5l/n] be the maximal integer satisfying N_{q}(A) < 3q. Define A_{0} to be the set of all elements of A, not divisible by q, (thus |A_{0}| = N_{q}(A) < 3q) and let A_{1} be the set of integers

20 VSEVOLOD F. LEV

such that A \ A_{0} = {qa: a ∈ A_{1}}. Evidently, we have A_{1} ⊆ [1, l_{1}], where l_{1} = ⌊l/q⌋, and n_{1} := |A_{1}| > n − 3q ≥ 0.9n for n large enough, as then q ≤ 5l/n ≤ 0.03n. Therefore,

n_{1} > 0.9n ≥ 18(l ln n)^{1/2} > 20((l/2) ln n_{1})^{1/2} ≥ 20(l_{1} ln n_{1})^{1/2}

and also N_{q_{1}}(A_{1}) ≥ 3q_{1} for q_{1} ∈ [2, 5l_{1}/n_{1}], as in the proof of Proposition 2. By Proposition 3 we have [y, z] ∈ A_{1}^{∗} with y and z integer and satisfying y ≤ ⌈λ_{1}σ(A_{1})⌉, z ≥ ⌊(1 − λ_{1})σ(A_{1})⌋, where λ_{1} = 280l_{1}/n_{1}^{2}. Furthermore, q ≤ l/l_{1} ≤ l/n_{1} < 2l/n whence A_{0} is q-complete. It follows that [(y + l)q, zq] ∈ A^{∗}. Next, we have

lq = 2 \frac{l}{n_{1}^{2}} \frac{n_{1}^{2}}{2} q < 3 \frac{l}{n^{2}} σ(A_{1})q ≤ 3 \frac{l}{n^{2}} σ(A)  (13)

implying

(y + l)q ≤ (λ_{1}σ(A_{1}) + l + 1)q ≤ 280 \frac{l}{qn_{1}^{2}} σ(A) + 2lq

≤ 200 \frac{l}{n^{2}} σ(A) + 6 \frac{l}{n^{2}} σ(A) ≤ λσ(A)

and

zq ≥ ((1 − λ_{1})σ(A_{1}) − 1)q ≥ (1 − λ_{1})σ(A) − σ(A_{0}) − q

≥ (1 − λ_{1})σ(A) − 4lq ≥ (1 − 280l_{1}/n_{1}^{2} − 12l/n^{2})σ(A) ≥ (1 − 212l/n^{2})σ(A) > (1 − λ)σ(A).

□

8. Proof of Corollary 1

We can assume that q < 2l/n with the property that N_{q}(A) < q − 1 do exist, and let d denote the maximal such q. Furthermore, let A_{0} be the set of all elements of A, not divisible by d (so that |A_{0}| = N_{d}(A) < d − 1), and let A_{1} be the set of integers such that A \ A_{0} = {ad: a ∈ A_{1}}; thus, n_{1} := |A_{1}| = |A_{d}| > n − d. We have A_{1} ⊆ [1, l_{1}], where l_{1} = ⌊l/d⌋, and we set λ_{1} := 280l_{1}/n_{1}^{2}. If n is large enough, then d < 2l/n < 0.1n and

n_{1} > 0.9n ≥ 18(l ln n)^{1/2} > 20(l_{1} ln n_{1})^{1/2}.

As in Proposition 2, maximality of d implies that N_{q}(A_{1}) ≥ q − 1 for any q < 2l_{1}/n_{1}; hence [λ_{1}σ(A_{1}), (1 − λ_{1})σ(A_{1})] ⊆ A_{1}^{∗} by Theorem 1, and A_{d}^{∗}

BLOCKS AND PROGRESSIONS IN SUBSET SUM SETS 21

contains all multiples of d from the interval [λ_{1}dσ(A_{1}), (1 − λ_{1})dσ(A_{1})]. It remains to observe that

λ_{1}dσ(A_{1}) ≤ 280 \frac{l}{dn_{1}^{2}} σ(A) ≤ 200 \frac{l}{n^{2}} σ(A)

and that, in view of ld < (3l/n^{2})σ(A) (cf. (13)),

(1 − λ_{1})dσ(A_{1}) ≥ (1 − λ_{1})σ(A) − σ(A_{0}) > (1 − 200l/n^{2})σ(A) − ld > (1 − 203l/n^{2})σ(A).

Appendix: infinite progressions in subset sums set

Let A be a (strictly increasing, infinite) sequence of positive integers. Write A(n) = |A ∩ [1, n]|, the counting function of A. A beautiful result of Folkman [Fo66, Theorem 1.3] is that A^{∗} contains an infinite arithmetic progression, provided that A(n) > n^{1/2+ε} for some fixed ε > 0 and all n large enough. In a striking development, Łuczak and Schoen showed recently that the progression can be chosen to be homogeneous and even under a somewhat relaxed assumption on A(n); their result is, in fact, the infinite version of Theorems A and B.

Theorem 5 (Łuczak and Schoen, [ŁS00, Theorem 2]). Let A be a sequence of positive integers satisfying A(n) ≥ 402\sqrt{n ln n} for all n large enough. Then there exists an integer d such that {d, 2d, 3d, …} ⊆ A^{∗}.

In this context we also mention a paper of Hegyvári [H00] where under a similar restriction on A(n) it is shown that A^{∗} contains an infinite arithmetic progression. However, the progression is not guaranteed to be homogenous.

An almost immediate consequence of Theorem 5, indicated in [ŁS00], is a (nearly sharp) estimate of the maximum possible density of a strongly sum-free sequence of integers.

Theorem 6 (Łuczak and Schoen, [ŁS00, Theorem 3]). Let A be a sequence of positive integers such that the equation a_{1} + ⋯ + a_{k} = a_{0} has no solutions in a_{i} ∈ A (for any k ≥ 2). Then A(n) ≤ 403\sqrt{n ln n} for all n large enough.

Using Theorem 2′ one can reduce the constants as follows.

Theorem 5′. Let A be a sequence of positive integers satisfying A(n) ≥ 5\sqrt{n ln n} for all n large enough. Then there exists an integer d such that {d, 2d, 3d, …} ⊆ A^{∗}.

22 VSEVOLOD F. LEV

Theorem 6′. Let A be a sequence of positive integers such that the equation a_{1} + ⋯ + a_{k} = a_{0} has no solutions in a_{i} ∈ A (for any k ≥ 2). Then A(n) < 5\sqrt{n ln n} for all n large enough.

Theorem 6′ can be deduced from Theorem 5′ exactly in the same way as Theorem 6 is deduced from Theorem 5, and we refer the reader to [ŁS00] for this deduction.^{1} On the other hand, modifications to be made to the original proof of Theorem 5 (to upgrade it to Theorem 5′) are minor but numerous, and for this reason we provide a sketch of the modified proof.

Sketch of the proof of Theorem 5′. Write A = {a_{1}, a_{2}, …}, set φ(i) := ⌊i ln^{1/4}(i + 1)⌋ and consider the decomposition A = A_{0} ∪ A_{1} defined by

A_{1} := {a_{φ(1)}, a_{φ(2)}, …}, A_{0} := A \ A_{1}.

Evidently,

A_{1}(n) = #{i: φ(i) ≤ A(n)}

= #{i: i ln^{1/4}(i + 1) ≤ A(n)}

= \frac{A(n)}{ln^{1/4} A(n)} (1 + o(1))

whence for n large enough we have A_{1}(n) ≫ \sqrt{n} ln^{1/4} n and A_{0}(n) = A(n)− A_{1}(n) ≥ 4.99\sqrt{n ln n}.

From [Fo66, Lemma 2.2] it follows that the condition

lim sup_{n→∞} A_{1}(n)/\sqrt{n} = ∞

guarantees that for any fixed integer d ≥ 1 the subset sum set A_{1}^{∗} has bounded gaps on the sequence of all multiples of d. That is, to any d there corresponds a constant C_{d} such that {(y + 1)d, (y + 2)d, …, (y + C_{d})d} ∩ A_{1}^{∗} ≠ ∅ for any integer y. On the other hand, we show that the condition A_{0}(n) ≥ 4.99\sqrt{n ln n} ensures the existence of d such that A_{0}^{∗} contains a homogeneous progression with difference d of any pre-assigned length. This will imply that A^{∗} = A_{0}^{∗} + A_{1}^{∗} contains an infinite progression of the form

1We have simplified the logic for the sake of clarity. In fact, to deduce Theorem 6′ one needs a version of Theorem 5′ with a constant strictly less than 5. The reader will see, however, that the argument we present below allows one to obtain any constant greater than 7/\sqrt{2} = 4.949 …

BLOCKS AND PROGRESSIONS IN SUBSET SUM SETS 23

{(m + 1)d, (m + 2)d, …} and therefore the infinite progression {d′, 2d′, …} where d′ = (m + 1)d.

We need a lemma which is, essentially, [ŁS00, Fact 5].

Lemma 7. Let P_{1} and P_{2} be homogeneous arithmetic progressions with differences d_{1} and d_{2} and at least m_{1} and m_{2} terms, respectively. Suppose that m_{2} ≥ d_{1}, m_{1} ≥ d_{2}, and d_{1} ≤ d_{2}. Then P_{1} + P_{2} contains a homogeneous arithmetic progression of difference d_{1} with at least m_{1} + m_{2} − 2d_{2} terms.

For the proof observe that P_{2} contains a homogeneous progression P′_{2} of difference d_{1}d_{2} with ⌊m_{2}/d_{1}⌋ ≥ 1 terms, and the sum of P_{1} and P′_{2} is a homogeneous progression of difference d_{1} with at least (⌊m_{2}/d_{1}⌋ − 1)d_{2} + m_{1} ≥ m_{1} +m_{2} −2d_{2} terms. (We use here the observation that the difference between consecutive terms of P′_{2} does not exceed the “length” of P_{1}.)

Back to the proof of Theorem 5′, for i = 0, 1, … we define l_{i} := 2^{2^{i}} (so that l_{i+1} = l_{i}^{2}) and we set A_{i} := A_{0} ∩ (l_{i−1}, l_{i}], n_{i} := |A_{i}|. For i large enough we have then A_{i} ⊆ [1, l_{i}] and

n_{i} = A_{0}(l_{i}) − A_{0}(l_{i−1}) ≥ 4.99\sqrt{l_{i} ln l_{i}} − \sqrt{l_{i}} ≥ 4.98\sqrt{l_{i} ln l_{i}},

\frac{n_{i}^{2}}{49 ln n_{i}} ≥ \frac{4.98^{2} l_{i} ln l_{i}}{49 (ln l_{i})/2} (1 + o(1)) ≥ 1.01(1 + o(1)) l_{i} > l_{i},

n_{i} > 7(l_{i} ln n_{i})^{1/2}.

Thus Theorem 2′ is applicable and A_{i}^{∗} contains a homogeneous progression of difference d_{i} < 5l_{i}/n_{i} < 2\sqrt{l_{i}/ ln l_{i}} and with at least n_{i}^{2}/405 > l_{i} ln l_{i}/20 > 4l_{i} terms.

Fix an integer j such that the above conclusions hold true and moreover, d_{i} ≥ d_{j} for i ≥ j. Using induction and Lemma 7 it is easy to verify that for any i ≥ j the set A_{j}^{∗} + ⋯ + A_{i}^{∗} contains a homogeneous progression of difference d_{j} with at least 4l_{i} terms: put P_{1} = A_{j}^{∗} + ⋯ + A_{i−1}^{∗}, P_{2} = A_{i}^{∗} and observe that

d_{i} < 2\frac{l_{i−1}}{\sqrt{2^{i} ln 2}} < 2l_{i−1}, d_{j} < 2\sqrt{l_{j}/(2 ln 2)} < 2l_{i},

4l_{i−1} + 4l_{i} − 2d_{i} = 4l_{i} + 2(2l_{i−1} − d_{i}) > 4l_{i}.

Therefore A_{0}^{∗} contains arbitrarily long homogeneous progressions of difference d = d_{j}, as required. □

References

[AF88] N. Alon and G.A. Freiman, On sums of subsets of a set of integers, Combinatorica 8 (4) (1988), 297–306.

[C90] M. Chaimovich, Subset-sums problems with different summands: computation, Discrete Applied Math. 27 (1990), 277–282.

[C99] M. Chaimovich, New algorithm for dense subset-sum problem, Astŕisque 258 (1999), 363–373.

[EF90] P. Erdős and G. Freiman, On two additive problems, J. Number Theory 34 (1990), 1–12.

[Fo66] J. Folkman, On the representation of integers as sums of distinct terms from a fixed sequence, Canad. J.Math. 18 (1966), 643–655.

[Fr93] G.A. Freiman, New analytical results in subset-sum problem, Discrete Math. 114 (1–3) (1993), 205–217.

[GM91] Z. Galil and O. Margalit, An almost linear-time algortihm for the dense subset sum problem, SIAM J. of Computing 20 (1991), 1157–1189.

[H00] N. Hegyvári, On the representation of integers as sums of distinct terms of a fixed set, Acta Arithmetica 92 (2000), 99–104.

[JŁR] Janson, Łuczak and Ruciński, Random Graphs, Wiley, New York, 2000.

[Le97] V. Lev, Optimal representations by sumsets and subset sums, J. Number Theory 62 (1) (1997), 127–143.

[Le97] V. Lev, On consecutive subset sums, Discrete Math. 187 (1–3) (1998), 151–160.

[Li89] E. Lipkin, On representation of r-powers by subset sums, Acta Arithmetica LII (1989), 353–366.

[ŁS00] T. Łuczak and T. Schoen, On the maximal density of sum-free sets, Acta

Arithmetica 95 (3) (2000), 225–229.

[P74] J.M. Pollard, A generalization of the theorem of Cauchy and Davenport, J. London Math. Society 8 (2) (1974), 460–462.

[S89] A. Sárközy, Finite Addition Theorems, I, J. Number Theory 32 (1989), 114–130.

[S94] A. Sárközy, Finite Addition Theorems, II, J. Number Theory 48 (1994), 197–218.

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

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