The structure of multisets with a small volume of subset sums. (English) Zbl 0969.11005

Lev, Vsevolod F.

Deshouillers, Jean-Marc (ed.) et al., Structure theory of set addition. Paris: Société Mathématique de France, Astérisque. 258, 179-186 (1999).

A multiset is a finite collection of natural numbers with repetitions allowed, \(A=\{a_1,a_2, \dots, a_k\}\), where \(a_1\leq a_2\leq \cdots\leq a_k\) are elements of \(A\). The sum of all elements of \(A\) is \(\sigma(A)= a_1+ \cdots +a_k\), and its subset sums set is \(P(A)= \{\varepsilon_1 a_1+ \cdots+ \varepsilon_k a_k\); \(0\leq \varepsilon_1, \dots, \varepsilon_k\leq 1\}\) \((0\) and \(\sigma(A)\) are included in \(P(A))\).
Another useful notation: \(A=\{a_1 \times k_1, \dots, a_s\times k_s\}\), \(a_1< \cdots< a_s\) are distinct elements of \(A\) with multiplicities \(k_1, \dots, k_s\geq 1\). In these terms the cardinality of \(A\) is \(|A|= k_1+\cdots +k_s\), the sums of its elements is \(\sigma (A)=k_1 a_1+\cdots +k_s a_s\), and its subset sums \(P(A)= \{v_1a_1 +\cdots + v_sa_s;\;0\leq v_i\leq k_i\), \(i=1,\dots, s\}\).
The main result: Suppose that \(A\) satisfies the condition \[ \bigl|P(A)|\leq C|A|-4C^3 \] where \(C\) is a positive integer and \(|A|\geq 8C^3\). Then \(P(A)\) is a union of at most \(C-1\) arithmetic progressions with the same common difference.
For the entire collection see [Zbl 0919.00044].

Reviewer: Tibor Šalát (Bratislava)

MSC:

11B25	Arithmetic progressions
11P99	Additive number theory; partitions
11B75	Other combinatorial number theory

Keywords:

subset sums; small doubling; multisets