OPTIMAL REPRESENTATIONS BY SUMSETS AND SUBSET SUMS

VSEVOLOD F. LEV

Abstract. Let A be a set of non-negative integers. In [3], for h ∈ ℤ, h ≥ 2 we estimated from below the cardinality of hA and this allowed us to obtain sharp estimates for such G, that every integer g ≥ G may be represented by a sum of elements of A (the linear diophantine problem of Frobenius). However, “not only the number of elements of hA is important, but also the way they are situated” (G.A. Freiman). In this paper we show that hA always contains long continuous chains of integers, and derive an estimation for the number of summands, required for representation of g of the above mentioned type.

1. Notation

If the opposite is not stated explicitly, we will use the following notations. A will denote a set of n = |A| ≥ 3 integers, contained in the segment [0; l] and satisfying 0, l ∈ A, gcd(A) = 1. For an integer h ≥ 1, by hA we denote the h-fold sumset A + ⋯ + A (h times), that is the set of all the integers representable by a sum of h elements of A.

By h·A we denote the set of all those integers, representable by a sum of exactly h distinct elements of A:

h·A = {∑_{b∈B} b | B ⊆ A, |B| = h}.

We write [u; v] ⊆ hA meaning that hA contains all the integers from the segment [u; v]. If there exists such a segment with v − u ≥ N (and u, v ∈ ℤ), we say that hA contains an interval of N + 1 integers.

We define integer numbers k, ρ ≥ 1 by

k(n − 2) + 1 ≤ l ≤ (k + 1)(n − 2) + 1,
ρ = (k + 1)(n − 2) + 2 − l.

If n − 2 divides l − 1, there are two choices for the pair (k, ρ), unless l = n − 1. Otherwise, k is the integral part of the “anti-density” \frac{l−1}{n−2}, and ρ characterizes in a way the fractional part. For further discussion it is worth mentioning, that for l ≠ k(n − 2) + 1 one has ρ ≤ n − 2, and then kρ < l.

2 VSEVOLOD F. LEV

2. Introduction

We discuss here the results which will be proved in subsequent sections.

Let G = k(l − ρ) (or in another form G = 2kl − k(k + 1)n + 2k^{2}). It was shown in [3] that every integer g ≥ G can be represented as the sum of elements of A. One of the central results of our present paper is the following.

Theorem 1. Let g be an integer.

i) Assume g ∈ [kl − kρ; kl + kρ]. Then g ∈ 2kA.

ii) Assume g ∈ [(k + ν)l + kρ; (k + ν + 1)l + kρ] for a non-negative integer ν. Then g ∈ (2k + ν + 1)A.

Note, that g ∈ hA is just an abbreviation for “g can be represented by a sum of h elements of A”. In view of 0 ∈ A, in the previous sentence we may replace “h elements” by “at most h elements” or by “exactly h elements”. For A not containing 0 one can apply to A a suitable linear transformation and then use the theorem to obtain an “exactly h-elements”-type result.

Concerning possible applications, rewrite Theorem 1 also as follows.

Theorem 1′. Let g ≥ 2kl − k(k + 1)n + 2k^{2}. Assume g ≤ νl + k(k + 1)n − 2k^{2} for a non-negative integer ν. Then g ∈ (2k + ν)A.

This theorem will be derived from the following lemma which seems to be of independent interest.

Lemma 1. We have:

i) [kl − kρ; kl + kρ] ⊆ 2kA;

ii) [kl − kρ; (k + 1)l + kρ] ⊆ (2k + 1)A.

For k = 1, assertion i) of the lemma was proved by G. Freiman in [2]. In [4], for k = 1 we proved [l; 2l] ⊆ 3A and (together with assertion i)) this easily implies assertion ii).

It is interesting to compare this lemma with the following theorem (see [5]):

Theorem 2 (Sárközy). Let A ⊆ [1; l] be an arbitrary set of n integers, and assume that the positive integer κ satisfies l ≤ κ(n−1)−1. Then there exist positive integers d, h such that d ≤ κ − 1, h < 118κ, and hA contains l consecutive multiples of d.

In this theorem one assumes all the elements of A to be positive and does not require l ∈ A or gcd(A) = 1. As a result, continuous intervals of integers become

OPTIMAL REPRESENTATIONS 3

here arithmetic progressions with some difference d. However, comparing Theorem 2 and assertion ii) of Lemma 1 in essence, we may say that the constant 118 of the theorem is replaced in the lemma by 2 (which is the best possible value), thus settling the problem posed by A. Sárközy in [5]. In Section 7 we prove the following theorem, solving the problem of Sárközy in its (virtually) initial setting and giving in fact somewhat more:

Theorem 2′. Let A ⊆ [1; l] be an arbitrary set of n integers, and assume that the positive integer κ satisfies l ≤ (κ + 1)(n − 2) + 1. Then there exist positive integers d, h such that d ≤ κ, h ≤ 2κ + 1, and hA contains l consecutive multiples of d. Moreover, d can be chosen to be the maximal integer such that all the elements of A fall into the same residue class modulo d, and h, — to be the maximal multiple of d, not exceeding 2κ + 1.

Return now to Lemma 1. We conjecture that in fact this lemma may be substantially strengthened:

Conjecture 1.

i) Assume l ≤ \frac{2k+1}{2}(n − 2) + \frac{3}{2}. Then 2kA contains a continuous interval of at least kl + kρ + 1 integers.

ii) (2k + 1)A always contains a continuous interval of at least (k + 1)l + kρ + 1 integers.

(Strictly speaking, assertion i) of the conjecture strengthens assertion i) of the lemma only for l ≤ \frac{2k+1}{2}(n − 2) + \frac{3}{2}).

We can prove this conjecture only for k = 1 and k = 2.

For h < 2k the set hA may not contain “long” integers chain (see the next section). However, for large h Conjecture 1 would easily imply

Corollary 1. Let ν be an integer,

ν ≥ \begin{cases}0, & if k(n − 2) + 1 ≤ l ≤ \frac{2k+1}{2}(n − 2) + \frac{3}{2} \\ 1, & if \frac{2k+1}{2}(n − 2) + \frac{3}{2} < l ≤ (k + 1)(n − 2) + 1. \end{cases}

Then (2k + ν)A contains a continuous interval of at least (k + ν)l + kρ + 1 integers.

Having Conjecture 1 proved only for k ≤ 2, we therefore establish the above corollary only for these values of k. Surprisingly, even the assertions we will prove for k ≤ 2 suffice to obtain a result which for ν ≥ k is as strong as Corollary 1 (and is unconditionally valid for all k):

4 VSEVOLOD F. LEV

Theorem 3.

i) Let 0 ≤ ν < k. Then (2k + ν)A contains a continuous interval of at least νl + 2kρ + 1 integers.

ii) Let ν ≥ k. Then (2k + ν)A contains a continuous interval of at least (k + ν)l + kρ + 1 integers.

In the last section, we apply this theorem to the problem of representation of integers by subset sums.

3. Examples

Below we give examples showing that the above discussed results are tight (either best possible or at least very close to the best possible). All these examples may be easily verified in a straightforward but rather tedious way, thus we leave the verification to the reader.

Define K = k + 1, t = ⌊l/K⌋ and set S = ∪_{h=1}^{∞}hA.

3.1. Theorem 1 can not be substantially improved.

3.1.1. If g < k(l − ρ), then possibly g ∉ S.

– If l = k(n − 2) + 1, let

A = {0, k, …, (n − 2)k} ∪ {l}.  (1)

Then k(l − ρ) − 1 ∉ S.

– If l ≥ k(n − 2) + 2, let

A = {0} ∪ {l − n + 2, l − n + 3, …, l}.

Then k(l − ρ) − 1 − k(l − k(n − 2) − 2) ∉ S.

– If l ≡ 0(mod K), let

A = {0, K, …, tK} ∪ {l − 1 − (n − t − 2)K, l − 1 − (n − t − 3)K, …, l − 1}.

Then k(l − ρ) − 1 ∉ S.

– If l ≡ r (mod K), where 0 < r < K, gcd(r, K) = 1, let

A = {0, K, …, tK} ∪ {l − (n − t − 2)K, l − (n − t − 3)K, …, l}.
Then k(l − ρ) − 1 − k(r − 1) ∉ S.

OPTIMAL REPRESENTATIONS 5

3.1.2. If k(l − ρ) ≤ g ≤ k(l + ρ), then possibly g ∉ (2k − 1)A. Let

A = {0, 1, …, n − ρ − 1} ∪ {l − ρ + 1, l − ρ + 2, …, l}.

Then k(l − ρ) + k − 1 ∉ (2k − 1)A save for the case l = k(n − 2) + 1, and moreover, k(l − ρ) ∉ (2k − 1)A for l ≥ k(n − 2) + 1 + k.

3.1.3. If g ≥ (k+ν)l+kρ+1, then possibly g ∉ (2k+ν)A. To see this, consider again the sets defined in Section 3.1.1. For each A, let A′ = l−A. Then k(l−ρ)−1−τ ∉ S implies (k + ν)l + kρ + 1 + τ ∉ (2k + ν)A′.

3.2. Lemma 1 i) is sharp.

3.2.1. The interval [kl − kρ; kl + kρ] can not be enlarged.

– If l = k(n − 2) + 1, define A by (1).

– If l ≥ k(n − 2) + 2, let

A = {0, 1, …, n − ρ − 2} ∪ {l − ρ, l − ρ + 1, …, l}.

In either case, k(l − ρ) − 1 ∉ 2kA.

Replace A by l − A to obtain the set A′ with k(l + ρ) + 1 ∉ 2kA′.

3.2.2. 2kA can not be replaced by (2k − 1)A. See Section 3.1.2.

3.3. Lemma 1 ii) can not be substantially improved.

3.3.1. The interval [kl − kρ; (k + 1)l + kρ] can not be enlarged. See Section 3.1.1 and Section 3.1.3 for ν = 1.

3.3.2. (2k + 1)A can not be replaced by 2kA. See Section 3.1.3 for ν = 0.

3.4. Conjecture 1 i) is tight.

3.4.1. 2kA can not be replaced by (2k−1)A. Consider examples of the Section 3.1.1. If k(l − ρ) − 1 − τ ∉ (2k − 1)A, then (2k − 1)A can not contain more than (k − 1)l + kρ + 1 + τ successive integers.

3.4.2. 2kA may not contain more than k(l + ρ) + 1 successive integers. We have already seen (Section 3.2) examples of A with k(l − ρ) − 1 ∉ 2kA, and in this case the longest interval contained in 2kA is of at most k(l + ρ) + 1 integers.

3.4.3. 2kA may not contain k(l + ρ) + 1 successive integers for l > \frac{2k+1}{2}(n − 2) + \frac{3}{2}. Define s_{0} = ⌊n/2⌋, s_{1} = ⌈n/2⌉ and let

A = {0, 1, …, s_{0} − 1} ∪ {l − s_{1} + 1, l − s_{1} + 2, …, l}.

3.5. Conjecture 1 ii) can not be substantially strengthened.

3.5.1. (2k + 1)A can not be replaced by 2kA. We have seen in Section 3.4 that 2kA may contain only k(l + ρ) + 1 or even less successive integers.

3.5.2. (2k + 1)A may not contain more than (k + 1)l + kρ + 1 successive integers. Section 3.1.1 gives examples of A with k(l−ρ)−1−τ ∉ (2k+1)A, and then obviously (2k+1)A can not possibly contain more than (k+1)l+kρ+1+τ successive integers.

3.6. Theorem 3 ii) can not be substantially improved. See Section 3.1.3.

3.7. Corollary 1 can not be substantially strengthened. See examples above.

4. Auxiliary results

We will need several auxiliary results.

The following well-known lemma (originated, evidently, to A. Shnirelman) in different shapes is available from many sources.

Lemma 2. Let B be an arbitrary set of integers, and assume 2|B ∩ [0; g]| > g + 1 for an integer g. Then g ∈ 2B.

Here is a useful generalization.

Lemma 2′. Let [β; g − γ], [γ; g − β] be two intervals (where β, γ, g ∈ ℤ), and let B, C ⊆ ℤ be two sets of integers. Assume

|B ∩ [β; g − γ]| + |C ∩ [γ; g − β]| > g − β − γ + 1.

Then g ∈ B + C.

Proof. Suppose g ∉ B + C, and let

δ_{B}(u) = \begin{cases}1, & if u ∈ B; \\ 0, & otherwise; \end{cases} δ_{C}(u) = \begin{cases}1, & if u ∈ C; \\ 0, & otherwise. \end{cases}

Obviously, δ_{B}(u) + δ_{C}(g − u) ≤ 1 for every u. Summing up over all u ∈ [β; g − γ], we obtain

|B ∩ [β; g − γ]| + |C ∩ [γ; g − β]| ≤ g − β − γ + 1.
□

The central role will be played by the following theorem, proved by the author in [3].

Theorem 4. For h ≥ 1, define B_{h}(n) = \frac{h(h+1)}{2}(n − 2) + h + 1. Then

|hA| ≥ \begin{cases}B_{h}(n), & if h ≤ k; \\ B_{k}(n) + (h − k)l, & if h ≥ k. \end{cases}

Specifically, we have:

|kA| ≥ \frac{1}{2}k(k + 1)(n − 2) + k + 1,

|(k + 1)A| ≥ \frac{1}{2}k(k + 1)(n − 2) + l + k + 1.

5. Proofs. I

In this section we prove Lemma 1, Theorem 1 and also derive Theorem 3 from Conjecture 1 assuming that this conjecture holds for k = 1. Proof of the Conjecture for k ≤ 2 will be presented in the following section.

Proof of Lemma 1.

i) Assume first g ∉ 2kA, 0 < g < kl, and show that actually g < kl − kρ. By Lemma 2,

2|kA ∩ [0; g]| ≤ g + 1,

and obviously,

2|kA ∩ [g + 1; kl]| ≤ 2(kl − g).

Summing up we obtain

2|kA| ≤ 2kl − g + 1,

and thus by Theorem 4

g ≤ 2kl − 2|kA| + 1 ≤
≤ 2kl − k(k + 1)(n − 2) − 2k − 1 =
= kl − kρ − 1,

which was to be proved.

Now, if g ∉ 2kA, kl < g < 2kl, we define A′ = l − A and apply the already proved part of the lemma to 2kl − g ∉ 2kA′ to conclude that 2kl − g < kl − kρ, and therefore g > kl + kρ. ii) Assume g ∉ (2k + 1)A, 0 < g < (k + 1)l and prove that actually g < kl − kρ. By Lemma 2′,

|kA ∩ [0; g]| + |(k + 1)A ∩ [0; g]| ≤ g + 1

8 VSEVOLOD F. LEV

and obviously,

|kA ∩ [g + 1; kl]| + |(k + 1)A ∩ [g + 1; (k + 1)l]| ≤ (2k + 1)l − 2g.

Summing up we obtain

|kA| + |(k + 1)A| ≤ (2k + 1)l − g + 1,

and thus by Theorem 4

g ≤ (2k + 1)l − |kA| − |(k + 1)A| + 1 ≤
≤ (2k + 1)l − k(k + 1)(n − 2) − l − 2k − 1 =
= kl − kρ − 1.

As above, one easily derives now that g > (k + 1)l + kρ for each g ∉ (2k + 1)A, g > kl. □

Proof of Theorem 1.

i) This is a direct consequence of Lemma 1. ii) Use induction by ν. If ν = 0, we are done by the same lemma. If ν ≥ 1, then g − l ∈ (2k + ν)A by the induction hypothesis, therefore g ∈ (2k + ν + 1)A. □

Proof of Theorem 3.

i) The case ν ≤ 1 is Lemma 1. For ν ≥ 2, we use induction: if (2k + ν − 1)A contains N ≥ l successive integers, then obviously (2k + ν)A contains at least N + l successive integers. ii) It is sufficient to consider the case ν = k (then induction is applicable). By Theorem 4,

2|kA| ≥ k((k + 1)(n − 2) + 1) + k + 2 ≥ kl + 3,
kl ≤ 2(|kA| − 2) + 1.

Applying now Conjecture 1 ii) to the set A′ = kA with

n′ = |kA|, l′ = kl, k′ = 1, ρ′ = 2(|kA| − 2) + 2 − kl

we see that the maximal number of successive integers contained in 3A′ = 3kA is at least

(k′ + 1)l′ + k′ρ′ + 1 = 2kl + (2(|kA| − 2) + 2 − kl) + 1 ≥
≥ 2kl + (k(k + 1)(n − 2) + 2k − kl) + 1 =
= 2kl + kρ + 1.

□

6. Proofs. II

Now we prove Conjecture 1 for k ≤ 2. We start with the second part of the conjecture.

Proof of Conjecture 1 ii) for k ≤ 2. Choose g′, g′′ ∉ (2k + 1)A satisfying 0 < g′ < kl < (k + 1)l < g′′ < (2k + 1)l (if such g′, g′′ do not exist, then either [0; kl] ⊆ (2k + 1)A, or [(k + 1)l; (2k + 1)l] ⊆ (2k + 1)A, and then the assertion holds true by Lemma 1). We prove that g′′ − g′ ≥ (k + 1)l + kρ + 2.

By Lemma 2′,

|kA ∩ [0; g′]| + |(k + 1)A ∩ [0; g′]| ≤ g′ + 1,  (2)

and by the same lemma

|kA ∩ [g′′ − (k + 1)l; kl]| + |(k + 1)A ∩ [g′′ − kl; (k + 1)l]| ≤ ≤ (2k + 1)l − g′′ + 1. (3)

We distinguish three cases according to the value of g′′ − g′.

i) If g′′ − g′ > (k + 1)l, then, summing up (2), (3), and the obvious estimate

|kA ∩ [g′ + 1; g′′ − (k + 1)l − 1]| + |(k + 1)A ∩ [g′ + 1; g′′ − kl − 1]| ≤ ≤ 2(g′′ − g′) − (2k + 1)l − 2,

we obtain |kA| + |(k + 1)A| ≤ g′′ − g′, hence by Theorem 4

g′′ − g′ ≥ k(k + 1)(n − 2) + l + 2k + 2 = (k + 1)l + kρ + 2,

proving the assertion. ii) If kl < g′′ − g′ ≤ (k + 1)l, then, summing up (2), (3), and the obvious estimate

|(k + 1)A ∩ [g′ + 1; g′′ − kl − 1]| ≤ g′′ − g′ − kl − 1,

we obtain |kA| + |(k + 1)A| ≤ (k + 1)l + 1, hence by Theorem 4

(k + 1)l + 1 ≥ k(k + 1)(n − 2) + l + 2k + 2,
kl > k(k + 1)(n − 2) + 2k,
l > (k + 1)(n − 2) + 2, −

a contradiction, showing that this case is actually impossible. iii) If g′′ − g′ ≤ kl, then, summing up (2) and (3) and using Theorem 4 we obtain

|kA| + |(k + 1)A| + |kA ∩ [g′′ − (k + 1)l; g′]| + |(k + 1)A ∩ [g′′ − kl; g′]| ≤ ≤ (2k + 1)l − g′′ + g′ + 2,

|kA ∩ [g′′ − (k + 1)l; g′]| + |(k + 1)A ∩ [g′′ − kl; g′] ≤ ≤ 2kl − k(k + 1)(n − 2) − 2k − g′′ + g′.

But

|kA ∩ [g′′ − (k + 1)l; g′]| ≥ |kA| − (g′′ − (k + 1)l) − (kl − g′) ≥

≥ \frac{1}{2}k(k + 1)(n − 2) + l + k + 1 − g′′ + g′,

therefore

2kl − k(k + 1)(n − 2) − 2k − g′′ + g′ ≥ k(k + 1)(n − 2)/2 + l + k + 1 − g′′ + g′,
(2k − 1)l ≥ 3k(k + 1)(n − 2)/2 + 3k + 1,
(2k − 1)((k + 1)(n − 2) + 1) ≥ 3k(k + 1)(n − 2)/2 + 3k + 1,
(k^{2}/2 − k/2 − 1)(n − 2) ≥ k + 2,

which is impossible for k ≤ 2. □

We note, that the above proof works perfectly also for k = 3 if l ≤ 3.6(n − 2) + 1.

Proof of Conjecture 1 i) for k = 1. Choose g′, g′′ ∉ 2A satisfying 0 < g′ < l < g′′ < 2l (if such g′, g′′ do not exist, then either [0; l] ⊆ 2A or [l; 2l] ⊆ 2A, and the assertion holds true by Lemma 1). We prove that g′′ − g′ ≥ k(l + ρ) + 2 = 2n.

By Lemma 2,

2|A ∩ [0; g′]| ≤ g′ + 1.  (4)

By Lemma 2′,

2|A ∩ [g′′ − l; l]| ≤ 2l − g′′ + 1.  (5)

We distinguish two cases.

i) If g′′ − g′ > l, then summing up (4), (5), and the obvious estimate

2|A ∩ [g′ + 1; g′′ − l − 1]| ≤ 2(g′′ − g′ − l − 1)

we obtain

g′′ − g′ ≥ 2|A| = 2n,

completing the proof. ii) If g′′ − g′ ≤ l then summing up (4) and (5) we obtain

2|A| ≤ 2l + g′ − g′′ + 2,
g′′ − g′ ≤ 2(l − n + 1).

But g′′ − g′ ≥ 2(kρ + 1) = 2(2n − l − 1) by Lemma 1, thus

l − n + 1 ≥ 2n − l − 1,
2l ≥ 3n − 2 = 3(n − 2) + 4, −

a contradiction, showing that this case is impossible. □

Proof of Conjecture 1 i) for k = 2. Choose g′, g′′ ∉ 4A satisfying 0 < g′ < 2l < g′′ < 4l (if such g′, g′′ do not exist, then we are done by Lemma 1). We prove that g′′ − g′ ≥ k(l + ρ) + 2 = 6n − 6.

By Lemmas 2 and 2′, we have:

2|2A ∩ [0; g′]| ≤ g′ + 1,  (6)
2|2A ∩ [g′′ − 2l; 2l]| ≤ 4l − g′′ + 1.  (7)

Again we distinguish two cases.

i) If g′′ − g′ > 2l, then summing up (6), (7), and the estimate

2|2A ∩ [g′ + 1; g′′ − 2l − 1]| ≤ 2(g′′ − g′ − 2l − 1)

and using Theorem 4 we obtain

g′′ − g′ ≥ 2|2A| ≥ 2(3n − 3),

proving the assertion. ii) The case g′′ − g′ ≤ 2l is actually impossible, as we show below. We may assume g′ > l (otherwise one has g′′ ≤ g′ + 2l < 3l, and we replace A by l − A, g′ by 4l − g′′, and g′′ by 4l − g′). We have now to consider two more cases. A) Let g′′ < 3l. Then by Lemma 2′

|A ∩ [0; g′′ − 2l]| + |2A ∩ [l; g′′ − l]| ≤ g′′ − 2l + 1,
|A ∩ [g′′ − 2l; l]| + |2A ∩ [g′′ − l; 2l]| ≤ 3l − g′′ + 1

(the first follows from g′′ − l ∉ 3A), and summing up we obtain

|2A ∩ [l; 2l]| ≤ l − n + 2.  (8)

12 VSEVOLOD F. LEV

Similarly, we have

|A ∩ [0; g′ − l]| + |2A ∩ [0; g′ − l]| ≤ g′ − l + 1,
|A ∩ [g′ − l; l]| + |2A ∩ [g′ − l; l]| ≤ 2l − g′ + 1,

and hence

|2A ∩ [0; l]| ≤ l − n + 2.  (9)

The summation of (8) and (9) in view of l ∈ 2A ∩ [0; l] ∩ [l; 2l] gives

|2A| ≤ 2(l − n + 2) − 1,
2l ≥ |2A| + 2n − 3 ≥ 5n − 6 = 5(n − 2) + 4,

contradicting the assumptions. B) Let g′′ > 3l.

We sum up (6) and (7):

2|2A| ≤ 4l − g′′ + g′ + 2,
g′′ ≤ 4l − 6n + 8 + g′,

and since

g′ ≤ k(l − ρ) − 1 = 2(2l − 3(n − 2) − 2) − 1 = 4l − 6n + 7

(by Lemma 1) then

g′′ ≤ 8l − 12n + 15.  (10)

Consider the following estimates:

2|A ∩ [0; g′′ − 3l − 1]| ≤ 2g′′ − 6l,
2|A ∩ [g′′ − 3l; g′ − l]| ≤ 2|2A ∩ [g′′ − 2l; g′]|,
2|A ∩ [g′ − l; l]|  ≤ 2l − g′ + 1

(the first and the second are obvious; the last follows by Lemma 2′). Summing this up and adding (6) and (7) we obtain

2|A| + 2|2A| ≤ (g′ + 1) + (4l − g′′ + 1) + (2g′′ − 6l) + (2l − g′ + 1) = g′′ + 3, g′′ ≥ 2(3n − 3) + 2n − 3 = 8n − 9.

Comparison with (10) gives

8l − 12n + 15 ≥ 8n − 9,

8l ≥ 20n − 24 = 20(n − 2) + 16,

l ≥ \frac{5}{2}(n − 2) + 2, −

a contradiction. □

7. The problem of Sárközy

In this section we prove Theorem 2′.

Let a_{0} be the minimal element of A, and let

A′ = {d^{−1}(a − a_{0}) | a ∈ A}.

Obviously, gcd(A′) = 1, and if l′ is the maximal element of A′, then

A′ ⊆ [0; l′], 0, l′ ∈ A′,
n − 1 ≤ l′ ≤ d^{−1}(l − 1).

We may assume κ(n − 2) + 1 ≤ l − 1 < (κ + 1)(n − 2) + 1, and we define positive integers r, k, ρ by

r = (κ + 1)(n − 2) + 3 − l,
k(n − 2) + 1 ≤ l′ < (k + 1)(n − 2) + 1,  (11)
ρ = (k + 1)(n − 2) + 2 − l′.

Lemma 3. If d ≥ 2, then 2k + d ≤ κ + 2.

Proof. We have:

k ≤ \frac{l′ − 1}{n − 2} ≤ \frac{l − 1}{d(n − 2)} − \frac{1}{n − 2},

and thus

2k + d ≤ \frac{1}{d} · \frac{2(l − 1)}{n − 2} + d − \frac{2}{n − 2}.

Denote the right-hand side by φ(d) and consider it as a function of real d for 2 ≤ d < \frac{l−1}{n−2}. This function is convex and

φ(2) = φ (\frac{l − 1}{n − 2}) = \frac{l − 1}{n − 2} + 2 − \frac{2}{n − 2} < \frac{l − 2}{n − 2} + 2,

therefore for every d holds

φ(d) < \frac{l − 2}{n − 2} + 2,

hence

2k + d ≤ ⌊φ(d)⌋ ≤ ⌊\frac{l − 2}{n − 2}⌋ + 2 = κ + 2.

□

14 VSEVOLOD F. LEV

Consider the set hA′ = (2k + ν)A′, where

ν = h − 2k ≥ 2κ − 2k + 2 − d ≥ 0

(in view of k ≤ κ and by Lemma 3). Then by Theorem 3 the set hA′ contains at least L = νl′+2kρ+1 consecutive integers, hence hA contains at least L consecutive multiples of d and it remains to prove that L ≥ l.

For this, we first note that

L ≥ (2κ − 2k + 2 − d)l′ + 2kρ + 1 =
= (2κ − 4k + 2 − d)l′ + 2k(k + 1)(n − 2) + 4k + 1.

We denote the right-hand side by F (l′) and consider it as a function of l′ (where k depends on l′ as in (11)). It is easily seen that

F (l′ + 1) − F (l′) = 2κ − 4k + 2 − d.  (12)

For l′ ≠ (k + 1)(n − 2) this is clear, and for the exceptional value l′ = (k + 1)(n − 2) this follows from

F (l′ + 1) − F (l′) = (2κ − 4(k + 1) + 2 − d)(l′ + 1) − (2κ − 4k + 2 − d)l′+
2(k + 1)(k + 2)(n − 2) − 2k(k + 1)(n − 2) + 4(k + 1) − 4k =
= (2κ − 4k + 2 − d) − 4l′ + 4(k + 1)(n − 2) =
= 2κ − 4k + 2 − d.

Now we consider two cases.

i) If d ≥ 2 then

F (l′ + 1) − F (l′) = 2(κ − 2k + 2 − d) + (d − 2) ≥ 0

(by (12) and Lemma 3), hence

F (l′) ≥ F (n − 1) = (2κ − 2 − d)(n − 1) + 4(n − 2) + 5 ≥
≥ (κ − 2)(n − 1) + 4(n − 2) + 5 =
= (κ + 2)(n − 2) + κ + 3 =
= l + n + r + κ − 2.

ii) If d = 1, then F (l′ + 1) ≥ F (l′) if and only if 4k ≤ 2κ + 1, that is k ≤ \frac{1}{2}κ. Thus, F (l′) is concave, and F (l′) ≥ min{F (n − 1), F (l − 1)}. But

F (n − 1) ≥ l + n + r + κ − 2

OPTIMAL REPRESENTATIONS 15

as we have already seen, and

F (l − 1) = (l − 1) + 2κr + 1 = l + 2κr,

which completes the proof.

Observe, that actually we proved the existence of at least

l + min{n + r + κ − 2, 2κr}

consecutive multiples of d in hA, which is somewhat more than was claimed.

8. Subset sums

Consider now representations of integers by subset sums, that is by sums of distinct elements of A. Here Theorem 3 may be used to derive results following the scheme, proposed by N. Alon in [1] and based on the theorem of K. Roth on 3-term arithmetic progressions.

Fix ε > 0. We say that A is ε-uniform if

|{a ∈ A | a ≡ r (mod d)}| ≤ (1 − ε)n

for each r, d ∈ ℤ (d ≥ 2).

In the following theorem, we do not assume 0 ∈ A or l ∈ A. Also, we do not require explicitly gcd(A) = 1, but this is implied by ε-uniformity.

Theorem 5. Let A ⊆ [0; l] be an arbitrary ε-uniform set of n integers, and let l ≤ (1 − ε)κn for an integer κ ≥ 2. Assume that h satisfies 3(κ − 1) ≤ h = O(1). Then there exists N (depending on ε and on the constant in the O-sign) such that for n ≥ N the set h·A contains an interval of at least l\frac{h}{κ} + h + 1 integers.

Below we give a sketch of the proof of Theorem 5, outlining only the details specific for our situation. For the detailed exposition of the method, see [1].

Proof of Theorem 5. Let A_{0} be the set of all those elements of A which are the midterm of at least h − 1 distinct 3-term arithmetic progressions of elements of A. Let a_{0} be the minimal element of A_{0}, and denote A′ = A_{0}−a_{0}. It is shown in [1] that n′ = |A′| = |A_{0}| ≥ n − (1 + \sqrt{3(h − 2)})r_{3}(l), where r_{3}(l) stands for the maximal cardinality of a subset of {1, 2, …, l} that contains no arithmetic progression of three terms. Hence, n′ ≥ (1 − ε)n + 2 if N is sufficiently large. Since A is εuniform, this implies gcd(A′) = 1. Next, the maximal element of A′ satisfies l′ < l ≤ (1 − ε)κn ≤ κ(n′ − 2), and therefore the appropriate k′ satisfies k′ ≤ κ − 1. In view of h ≥ 3(κ − 1) ≥ 3k′ and by Theorem 3 ii), the set hA′ contains at least (h−k′)l′ +k′ρ′ +1 successive integers, and so does the set h·A. It remains to observe that

(h − k′)l′ + k′ρ′ + 1 = (h − 2k′)l′ + k′(k′ + 1)(n′ − 2) + 2k′ + 1 ≥
≥ (h − 2k′)(k′(n′ − 2) + 1) + k′(k′ + 1)(n′ − 2) + 2k′ + 1 =
= (n′ − 2)(hk′ − k′^{2} + k′) + h + 1 =
= (n′ − 2)(k′ − 1)(h − k′) + h(n′ − 2) + h + 1 ≥
≥ h(n′ − 2) + h + 1 ≥
≥ (1 − ε)nh + h + 1 ≥
≥ lh/κ + h + 1.
□

Assuming no ε-uniformity, one can prove only the existence in h·A of an arithmetic progression of the length l\frac{h}{κ} +h+1 with some difference d ≤ κ−1. The proof follows closely that of Theorem 5, but we define A′ = d^{−1}(A_{0} − a_{0}) where

d = gcd(A_{0} − a_{0}) ≤ l/(n′ − 1) ≤ (1 − ε)κn/(n′ − 1) < κ.

This sharpens a theorem of Sárközy (see [5, Theorem 3]) which was proved by the same method, but using Theorem 2 instead of our Theorem 3.

On the contrary, if in addition to ε-uniformity we assume that elements of A are distributed in a sense “proportionally”, then we can guarantee the existence of even longer intervals of integers in h·A.

Theorem 6. Suppose, in addition to the assumptions of Theorem 5, that A has no subset of cardinality greater then (1 − ε)n which is contained in an interval of the length less then (1 − ε)^{2}l. Then h·A contains at least (1 − ε)^{2}(h − κ + 1)l + κ successive integers.

Proof. We act as in the proof of the previous theorem and observe, that l′ ≥ (1−ε)^{2}l. Therefore

(h − k′)l′ + k′ρ′ + 1 ≥ (h − k′)l′ + k′ + 1 ≥
≥ (h − κ + 1)l′ + κ ≥
≥ (1 − ε)^{2}(h − κ + 1)l + κ.
□

A comparison with Theorem 3 shows that this result is almost best possible (under the assumptions imposed on A and h, the most restrictive of which is κ, h = O(1)).

Finally, assuming only proportionality but not uniformity, we can prove that A contains an arithmetic progression with the difference d ≤ κ − 1 and of at least (1 − ε)^{2}(h − ⌈κ/d⌉ + 1)l/d + ⌈κ/d⌉ elements. The proof is like that of Theorem 6 and uses also the estimate

(1 − ε)^{2}l < dl′ < l ≤ (1 − ε)κn < κ(n′ − 2)

which implies l′ > (1 − ε)^{2}l/d and k′ ≤ ⌈κ/d⌉ − 1.

References

[1] N. Alon, Subset Sums, J. Number Theory, 27 (1987), 196–205.

[2] G. Freiman, Sumsets and powers of 2, Colloq. Math. Soc. János Bolyai, 60 (1992), North-Holland, Amsterdam.

[3] V. Lev, Structure theorem for multiple addition and the Frobenius’ problem, J. Number Theory, to appear.

[4] , On the extremal aspect of the Frobenius’ problem, J. Comb. Theory, Series A, to appear.

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

School of Math. Sciences, Tel-Aviv University, 69978 Tel-Aviv, Israel

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