THE STRUCTURE OF MULTISETS WITH A SMALL NUMBER OF SUBSET SUMS

VSEVOLOD F. LEV

Abstract. We investigate multisets of natural numbers with relatively few subset sums. Namely, let A be a multiset such that the number of distinct subset sums of A is bounded by a fixed multiple of the cardinality of A itself: |P (A)| ≪ |A|. We show that the set P (A) of subset sums is then a union of a small number of arithmetic progressions sharing a common difference.

Similar problems were considered by G. Freiman (see [1]) and M. Chaimovich (see [2]). Unlike those papers, our conditions are stated in terms of the cardinality of the subset sums set P (A) only and not on the largest element of the original multiset A.

The result obtained is nearly best possible.

1. Notation and definitions

By a multiset we mean a finite collection of natural numbers with repetitions allowed: A = {a_{1}, …, a_{k}}, where a_{1} ≤ ⋯ ≤ a_{k} are the elements of A. The number of appearances of an element will be called its multiplicity.

As with “normal” sets, |A| = k is called the cardinality of A. The sum of all elements of the multiset is σ(A) = a_{1} + ⋯ + a_{k}, and its subset sums set is

P (A) = {ε_{1}a_{1} + ⋯ + ε_{k}a_{k}: 0 ≤ ε_{1}, …, ε_{k} ≤ 1}.

Notice that 0 and σ(A) are both included in P (A); generally, e belongs to P (A) if and only if σ(A) − e does.

Another useful notation:

A = {a_{1} × k_{1}, …, a_{s} × k_{s}},

meaning that a_{1} < ⋯ < a_{s} are distinct elements of A with multiplicities k_{1}, …, k_{s} ≥ 1. In these terms, the cardinality of A is |A| = k_{1} + ⋯ + k_{s}, the sum of its elements is σ(A) = k_{1}a_{1} + ⋯ + k_{s}a_{s}, and its subset sums set is

P (A) = {κ_{1}a_{1} + ⋯ + κ_{s}a_{s}: 0 ≤ κ_{1} ≤ k_{1}, …, 0 ≤ κ_{s} ≤ k_{s}}.

2. The main result

The following theorem is our main result.

Theorem 1. Let A satisfy

|P (A)| ≤ C|A| − 4C^{3},  (1)

where C is a natural number, and suppose that the cardinality of A is sufficiently large: |A| ≥ 8C^{3}. Then P (A) is a union of at most C − 1 arithmetic progressions with the same common difference.

Theorem 1 (the proof of which will be given in Section 5) is somewhat unusual in describing the structure of the subset sums set P (A) rather then the structure of the multiset A itself. As the reader will notice, this reflects the essence of the problem: one can change A substantially without affecting P (A), and thus it seems impossible to describe the structure of A under any reasonable condition on P (A).

We conjecture that (1) can be replaced by the weaker restriction

|P (A)| ≤ C|A| − (C − 1)^{2}.  (2)

The following examples show that inequality (2) cannot be further relaxed.

Example 1. Let A = {1 × (k − C + 1), b × (C − 1)}, where k = |A| and b are sufficiently large. Then P (A) is the union of C progressions

0, 1, …, k − C + 1,
b, b + 1, …, b + (k − C + 1),
…
(C − 1)b, (C − 1)b + 1, …, (C − 1)b + (k − C + 1),

so that |P (A)| = C(k−C+2) = Ck−(C−1)^{2}+1. However, P (A) cannot be represented as a union of at most C − 1 arithmetic progressions with a common difference.

Example 2. Let A = {1 × (C − 1), b × (k − C + 1)}, where k = |A| and b are sufficiently large. Then P (A) is the union of C progressions

0, b, …, (k − C + 1)b,
1, 1 + b, …, 1 + (k − C + 1)b,
…
C − 1, C − 1 + b, …, C − 1 + (k − C + 1)b,

so that |P (A)| = Ck − (C − 1)^{2} + 1, and again P (A) cannot be represented as a union of at most C − 1 arithmetic progressions with a common difference.

MULTISETS WITH A FEW SUBSET SUMS 3

Note that in view of Lemma 2 below, the inequality |P (A)| ≥ |A| + 1 is always true. Hence, the conditions of Theorem 1 are never satisfied for C = 1, and from now on we assume C ≥ 2.

3. Small values of C

For A satisfying (1) (or even (2)) with small values of C (C = 2, 3) the structure of P (A), as well as the structure of A itself, can be completely described.

We begin with some basic properties of subset sums set. First, we estimate by how much |P (A)| increases if one adds an element to A.

Lemma 1. Let A = {a_{1} ×k_{1}, …, a_{s} ×k_{s}}, A^{+} = A∪{a}, and suppose that A contains at least i − 1 different elements less then a (that is, a > a_{i−1} unless i = 1). Then

|P (A^{+})| ≥ |P (A)| + i.

Proof. P (A^{+}) contains all the elements of P (A), as well as the i additional elements

σ(A) + a, σ(A) + a − a_{1}, …, σ(A) + a − a_{i−1}.
□

As a direct corollary, we obtain a lower-bound estimate for |P (A)|.

Lemma 2. The cardinality of the subset sums set P (A) of the multiset A = {a_{1} × k_{1}, …, a_{s} × k_{s}} satisfies

|P (A)| ≥ 1 + k_{1} + 2k_{2} + ⋯ + sk_{s}.

In particular, |P (A)| ≥ 1 + |A|.

Proof. The assertion is obviously true for |A| = 1, and we use induction on |A|. Denote by A^{−} the multiset obtained by removing from A its largest element a_{s}. Applying Lemma 1, we obtain then

|P (A)| ≥ |P (A^{−})| + s ≥ (1 + k_{1} + 2k_{2} + ⋯ + s(k_{s} − 1)) + s
= 1 + k_{1} + 2k_{2} + ⋯ + sk_{s}.
□

It follows from Lemma 2 that a multiset A with relatively small value of |P (A)| has at least one element with large multiplicity.

Lemma 3. Let A = {a_{1} × k_{1}, …, a_{s} × k_{s}}, and let k_{0} = max_{1≤i≤s} k_{i} be the maximal multiplicity of an element of A. Then

k_{0} > \frac{k^{2}}{2|P (A)|}.

Proof. For 1 ≤ i ≤ s we have:

|P (A)| ≥ 1 + k_{1} + 2k_{2} + ⋯ + ik_{i} + (i + 1)(k_{i+1} + ⋯ + k_{s})
> (i + 1)k − (k_{i} + 2k_{i−1} + ⋯ + ik_{1})
≥ (i + 1)k − \frac{1}{2}i(i + 1)k_{0}.

The resulting estimate

|P (A)| > (i + 1)k − \frac{1}{2}i(i + 1)k_{0}

also holds for i > s, as in this case the expression in the right-hand side, considered as a function of real i, has a negative derivative:

k − \frac{1}{2}(2i + 1)k_{0} < k − sk_{0} ≤ 0.

Hence,

k_{0} > \frac{2}{i} (k − \frac{|P (A)|}{i + 1})

for every i = 1, 2, … We choose i under the condition

2\frac{|P (A)|}{k} − 1 ≤ i < 2\frac{|P (A)|}{k}.

Then

\frac{2}{i} > \frac{k}{|P (A)|}, \frac{|P (A)|}{i + 1} ≤ \frac{k}{2},

and so

k_{0} > \frac{k}{|P (A)|} · \frac{k}{2} = \frac{k^{2}}{2|P (A)|}.

□

We now construct multisets whose subset sums sets have a particularly simple structure.

Example 3. Let A = {a_{1}, …, a_{k}} be a multiset such that i) a_{2}, …, a_{k} ≡ 0 (mod a_{1});

ii) a_{i+1} ≤ a_{1} + ⋯ + a_{i} for i = 1, …, k − 1.

Then P (A) is an arithmetic progression: P (A) = {0, a_{1}, 2a_{1}, …, σ(A)}.

MULTISETS WITH A FEW SUBSET SUMS 5

This easily follows by induction on k: if A^{−} = {a_{1}, …, a_{k−1}}, then

P (A) = P (A^{−}) ∪ (a_{k} + P (A^{−}))
= {0, a_{1}, …, σ(A^{−})} ∪ {a_{k}, a_{k} + a_{1}, …, a_{k} + σ(A^{−})}
= {0, a_{1}, …, σ(A)},

since a_{k} ≤ σ(A^{−}) and a_{k} + σ(A^{−}) = σ(A).

Proposition 1. Any multiset A, satisfying |P (A)| ≤ 2|A| − 1 (that is satisfying (2) with C = 2) has the structure, described in Example 3.

Proof. Suppose, on the contrary, that there exists an index 2 ≤ i ≤ k for which either a_{i} ≢ 0 (mod a_{1}) or a_{i} > a_{1} + ⋯ + a_{i−1}; we assume, moreover, that i is the minimum index with this property. Then, writing A_{j} = {a_{1}, …, a_{j}} (j = 1, …, k) and applying Lemma 2, we obtain

|P (A_{i})| = 2|P (A_{i−1})| ≥ 2i

(since P (A_{i}) = P (A_{i−1}) ∪ (a_{i} + P (A_{i−1})), and P (A_{i−1}) is disjoint with a_{i} + P (A_{i−1})), therefore

|P (A)| = |P (A_{k})| ≥ |P (A_{k−1})| + 2 ≥ ⋯ ≥ |P (A_{i})| + 2(k − i) ≥ 2k.
□

The following example describes the construction of multisets whose subset sums set consists of exactly two arithmetic progressions.

Example 4. Let A = {a_{1}, …, a_{m}} ∪ {b_{1}, b_{2}} ∪ {c_{1}, …, c_{n}}, where – a_{m} < b_{1} ≤ c_{1};

– A_{m} = {a_{1}, …, a_{m}} satisfies conditions (i) and (ii) of Example 3 with a_{1} = 2;

– b_{1}, b_{2} ≢ 0 (mod 2);
– b_{1} + b_{2} ≤ σ(A_{m}) + 2;

– c_{i+1} ≤ σ(C_{i}) − 2b_{1} + 3 (0 ≤ i ≤ n − 1), where C_{i} = {a_{1}, …, a_{m}} ∪ {b_{1}, b_{2}} ∪

{c_{1}, …, c_{i}}.

Then P (A) is a union of two progressions with the common difference 2: if σ(A) is even, then

P (A) = {0, 2, …, σ(A) − 2, σ(A)} ∪ {b_{1}, b_{1} + 2, …, σ(A) − b_{1}},

and if σ(A) is odd, then

P (A) = {0, 2, …, σ(A) − b_{1}} ∪ {b_{1}, b_{1} + 2, …, σ(A)}.

In either case, |P (A)| = σ(A) − b_{1} + 2.

The verification is left to the interested reader.

Proposition 2. Any multiset A with co-prime elements satisfying |P (A)| ≤ 3|A| − 4 (that is satisfying (2) with C = 3) has either the structure described in Example 3, or the structure described in Example 4.

This proposition will not be used in the sequel and is given just for completeness. Its proof (which is rather long and tedious) is available from the author.

4. More lemmas and properties of P (A)

In this section, we prepare for the proof of Theorem 1. To this end, we first determine the value of |P (A)| for multisets A with only two different elements. Without loss of generality we can restrict ourselves to the case when these two elements are co-prime.

Lemma 4. Let A = {a_{1} × k_{1}, a_{2} × k_{2}}, where (a_{1}, a_{2}) = 1. Then i) if k_{1} ≤ a_{2} − 1 or k_{2} ≤ a_{1} − 1, then

|P (A)| = (k_{1} + 1)(k_{2} + 1);
ii) if k_{1} ≥ a_{2} − 1 and k_{2} ≥ a_{1} − 1, then
|P (A)| = a_{1}k_{1} + a_{2}k_{2} − (a_{1} − 1)(a_{2} − 1) + 1.

Proof. In Case i), the assertion follows from the fact that all values of the linear form

a_{1}x + a_{2}y; 0 ≤ x ≤ k_{1}, 0 ≤ y ≤ k_{2}

are pairwise distinct: if, for instance, k_{1} ≤ a_{2} − 1, and a_{1}x + a_{2}y = a_{1}x′ + a_{2}y′, then x ≡ x′ (mod a_{2}); therefore (in view of 0 ≤ x, x′ ≤ k_{1} < a_{2}) we have x = x′, whence y = y′.

In Case ii) we use induction on k_{2}. For k_{2} = a_{1} − 1 we apply the above proved:

|P (A)| = (k_{1} + 1)(k_{2} + 1) = a_{1}k_{1} + a_{1}
= a_{1}k_{1} + a_{2}k_{2} − a_{2}k_{2} + a_{1}
= a_{1}k_{1} + a_{2}k_{2} − a_{1}a_{2} + a_{1} + a_{2}
= a_{1}k_{1} + a_{2}k_{2} − (a_{1} − 1)(a_{2} − 1) + 1.

Suppose now that k_{2} > a_{1} − 1. Write A^{−} = {a_{1} × k_{1}, a_{2} × (k_{2} − 1)}, so that

|P (A^{−})| = a_{1}k_{1} + a_{2}(k_{2} − 1) − (a_{1} − 1)(a_{2} − 1) + 1.

We have to prove, therefore, that |P (A)| = |P (A^{−})| + a_{2}. Obviously, the difference |P (A)| − |P (A^{−})| counts the numbers of the form

xa_{1} + k_{2}a_{2}; 0 ≤ x ≤ k_{1},  (3)

MULTISETS WITH A FEW SUBSET SUMS 7

which cannot be represented in the form

xa_{1} + ya_{2}; 0 ≤ x ≤ k_{1}, 0 ≤ y ≤ k_{2} − 1.

We show that this particular subset of (3) is obtained when k_{1} − a_{2} + 1 ≤ x ≤ k_{1}; that is, there exist exactly a_{2} such numbers. Indeed, if x < k_{1} − a_{2} + 1 then the number e = xa_{1} + k_{2}a_{2} possesses the representation e = (x + a_{2})a_{1} + (k_{2} − a_{1})a_{2}. On the other hand, for x ≥ k_{1} − a_{2} + 1 the equality xa_{1} + k_{2}a_{2} = x′a_{1} + ya_{2} is impossible: otherwise x′ ≡ x (mod a_{2}), meaning that x′ ≤ x, and then xa_{1} + k_{2}a_{2} > x′a_{1} + ya_{2}, a contradiction. □

The following lemma shows that under certain conditions, a multiset can be slightly modified in such a way that the number of its elements will increase while its subset sums set will not change. Once again, we start with multisets with exactly two distinct elements.

Lemma 5. Let A = {a_{1} × k_{1}, a_{2} × k_{2}}, where

a_{1} < a_{2}, k_{1} ≥ a_{2} − 1, k_{2} ≥ 2a_{1} − 1.

Then there exist k′_{1}, k′_{2} such that the multiset A′ = {a_{1} × k′_{1}, a_{2} × k′_{2}} satisfies

P (A′) = P (A), |A′| > |A|.

Proof. We set k′_{1} = k_{1} + a_{2}, k′_{2} = k_{2} − a_{1}. Since k′_{1} + k′_{2} = k_{1} + k_{2} + (a_{2} − a_{1}) > k_{1} + k_{2}, we have only to prove that P (A′) = P (A).

1) Suppose that e = xa_{1} + ya_{2} ∈ P (A), where 0 ≤ x ≤ k_{1}, 0 ≤ y ≤ k_{2}, and show that e ∈ P (A′). Indeed, this is trivial if y ≤ k_{2} − a_{1}, and otherwise follows from e = (x + a_{2})a_{1} + (y − a_{1})a_{2}.

2) Suppose that e = xa_{1} + ya_{2} ∈ P (A′), where 0 ≤ x ≤ k′_{1}, 0 ≤ y ≤ k′_{2}, and show that e ∈ P (A). Indeed, this is trivial if x ≤ k_{1}, and otherwise follows from e = (x − a_{2})a_{1} + (y + a_{1})a_{2}. □

We now wish to bring the assumptions of Lemma 5 to a more convenient form, as well as to extend this lemma for the case of multisets with arbitrarily many distinct elements.

Lemma 5′. Let A = {a_{1} × k_{1}, …, a_{s} × k_{s}}, and suppose that some two multiplicities k_{i}, k_{j} (1 ≤ i < j ≤ s) satisfy k_{i}k_{j} ≥ 2(|P (A)| − k). Then there exists a multiset A′ such that

P (A′) = P (A), |A′| > |A|.

8 VSEVOLOD F. LEV

Proof. Write A_{0} = {a_{i} ×k_{i}, a_{j} ×k_{j}} and A_{1} = A\A_{0} (so that A = A_{0} ∪A_{1}). We denote d = (a_{i}, a_{j}) and set a′_{i} = a_{i}/d, a′_{j} = a_{j}/d. Clearly,

|P (A)| ≥ |P (A_{0})| + |P (A_{1})| − 1 ≥ |P (A_{0})| + |A_{1}|,
|P (A_{0})| ≤ (\frac{1}{2}k_{i}k_{j} + k) − (k − k_{i} − k_{j}) = \frac{1}{2}k_{i}k_{j} + k_{i} + k_{j} < (k_{i} + 1)(k_{j} + 1),

whence, in view of Lemma 4, k_{i} ≥ a′_{j} and k_{j} ≥ a′_{i}. Moreover, applying Lemma 4 once more (this time part (ii)) we obtain:

|P (A_{0})| = k_{i}a′_{i} + k_{j}a′_{j} − (a′_{i} − 1)(a′_{j} − 1) + 1
> k_{i}a′_{i} + k_{j} + k_{j}(a′_{j} − 1) − (a′_{i} − 1)(a′_{j} − 1)
≥ k_{i}a′_{i} + k_{j},

which implies

\frac{1}{2}k_{i}k_{j} + k_{i} + k_{j} > k_{i}a′_{i} + k_{j},
k_{j} > 2a′_{i} − 2.

This allows us to apply Lemma 5 to A_{0} (more precisely, to the multiset {a′_{i}×k_{i}, a′_{j} ×k_{j}}) to find A′_{0} with P (A′_{0}) = P (A_{0}), |A′_{0}| > |A_{0}|. Then the multiset A′ = A′_{0} ∪ A_{1} will obviously satisfy the required conditions P (A′) = P (A), |A′| > |A|. □

5. Proof of Theorem 1

Two multisets A and A′ will be called equivalent, if P (A) = P (A′). Without loss of generality we can assume that A is a multiset of the maximum possible cardinality of all equivalent multisets. We write A in the form

A = {a_{0} × k_{0}} ∪ B, B = {b_{1} × k_{1}, …, b_{s} × k_{s}},

where k_{1}, …, k_{s} ≤ k_{0}, and b_{1}, …, b_{s} ≠ a_{0}.

By a chain we will mean a sequence E = {e_{1}, …, e_{t}} of the elements of P (B), satisfying the two following conditions:

i) 0 < e_{i+1} − e_{i} ≤ k_{0}a_{0}; i = 1, …, t − 1;

ii) e_{1} ≡ ⋯ ≡ e_{t} (mod a_{0}).

The chain E will be referred to as maximal if no more elements of P (B) can be added to E without violating either (i) or (ii).

Let S = P ({a_{0} × k_{0}}) = {0, a_{0}, …, k_{0}a_{0}}. It is obvious that:

– if E is a chain, then the sum S + E is an arithmetic progression with the difference a_{0};

– if E_{1} and E_{2} are two distinct maximal chains, then the progressions S + E_{1} and S + E_{2} are disjoint.

MULTISETS WITH A FEW SUBSET SUMS 9

Clearly, there is exactly one way to decompose P (B) into maximal chains, and we denote the number of these chains by N. We assume N ≥ C (since otherwise P (A) consists of at most C − 1 progressions with the difference a_{0}) and show that this assumption leads to a contradiction.

Since obviously |P (A)| − |P (B)| ≥ Nk_{0}, we obtain

|P (B)| ≤ |P (A)| − Nk_{0} < C(|A| − k_{0}) = C|B|

(in fact, one can easily prove that B satisfies (2)). Therefore, by Lemma 3,

max_{1≤i≤s} k_{i} ≥ \frac{|B|^{2}}{2|P (B)|} > \frac{|B|}{2C}.

By Lemma 5′ and in view of the maximality of A,

k_{0} · \frac{|B|}{2C} < 2(|P (A)| − k) < 2(C − 1)k,
k_{0}(k − k_{0}) < 4C(C − 1)k.

The left-hand side of the last inequality is a quadratic polynomial of k_{0} with zeroes at 0 and k, maximum at k/2, and attaining both at 4C^{2} and k − 4C^{2} the same common value

4C^{2}(k − 4C^{2}) ≥ 4C(C − 1)k.

Therefore, either k_{0} < 4C^{2} or k_{0} > k − 4C^{2} holds true.

The first is actually impossible, since by Lemma 3, k_{0} > \frac{k^{2}}{2Ck} ≥ 4C^{2}. Hence k_{0} > k − 4C^{2}, and it follows that

|P (A)| ≥ N(k_{0} + 1) > C(k − 4C^{2}) = Ck − 4C^{3},

a contradiction with (1). (Notice that this is the only place where we use (1) instead of the weaker (2).) This completes the proof of Theorem 1.

References

[1] Freiman G., Subset-sum problem with different summands, Congressus Numerantium 70 (1990), 207–215.

[2] Chaimovich M., Solving a value-independent knapsack problem with use of methods of additive number theory, Congressus Numerantium 72 (1990), 115–123.

School of Mathematical Sciences, Sackler Faculty of Exact Sciences, Tel-Aviv University, 69978 Tel-Aviv, Israel