SMF

The structure of multisets with a small volume of subset sums

The structure of multisets with a small volume of subset sums

Vsevolod F. LEV
  • Année : 1999
  • Tome : 258
  • Format : Papier, Électronique
  • Langue de l'ouvrage :
    Anglais
  • Class. Math. : 11P99, 11B75
  • Pages : 179-186
  • DOI : 10.24033/ast.446

On recherche ici des ensembles d'entiers naturels $A=\{a_1,\dots , a_k\}$ (avec répétitions possibles) tels que l'ensemble des sommes $P(A)=\{\varepsilon _1a_1+\cdots +\varepsilon _ka_k\colon 0\le \varepsilon _1,\dots ,\varepsilon _k\le 1\}$ est petit. Précisément, soit $A$ un tel ensemble pour lequel le cardinal de $P(A)$ est borné par un multiple fixe du cardinal de $A$ (i.e. $|P(A)|\ll |A|$), nous montrons que l'ensemble $P(A)$ est alors la réunion d'un petit nombre de progressions arithmétiques de même raison. Des problèmes similaires ont déjà été considérés par G. Freiman [1] et M. Chaimovich [2]. À la différence de ces articles, nos conditions s'expriment seulement à l'aide du cardinal de $P(A)$ sans faire appel au plus grand élément de $A$.

We investigate multisets of natural volumes 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$ (that is, $|P(A)|\ll |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.

Subset sums, small doubling, multisets
Des problèmes avec le téléchargement?Des problèmes avec le téléchargement?
Informez-nous de tout problème que vous avez...