This page is regularly updated.

Emath.fr:

Directory

Calendar

Links

MATEXO

MathDoc

Postes

SFdS

-

SMAI

-

SMF

Heading:

Publications --- Choose a heading --- Presentation of the publications Titles Last titles Forthcomming titles Editorial staff committee / Secretary --- Electronic publishing --- Issues schedule Electronic distribution list Information for bookselers and subscription agencies --- Information for the authors Formats and documentation

Publication:

Choose a publication --- All publications --- Annales scientifiques de l'ENS Astérisque Bulletin de la SMF Cours Spécialisés Documents Mathématiques Journal de la SFdS La Série T Mémoires de la SMF Panoramas et Synthèses Revue d'Histoire des Mathématiques Revue de l'Institut Elie Cartan Séminaires et Congrès SMF/AMS Texts and Monographs --- Gazette des Mathématiciens Volumes "Journée Annuelle" --- Nicolas Bourbaki's seminar new edition Jean Leray's scientific works new edition Où en sont les mathématiques ? L'explosion des mathématiques Zoom sur les métiers des mathématiques

Astérisque - Titles - 1999 - 258 - pages 179-186 < Titles < 1999 < 258

Structure Theory of Set Addition
Jean-Marc Deshouillers, Bernard Landreau, Alexander A. Yudin (Ed.)
Astérisque 258 (1999), 458 pages
Buy the book

The structure of multisets with a small volume of subset sums
Vsevolod F. Lev
Astérisque 258 (1999), 179-186

Résumé :
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. $\vert P(A)\vert\ll \vert A\vert$), 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.

Abstract:
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, $\vert P(A)\vert\ll \vert A\vert$). 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.

Key words: Subset sums, small doubling, multisets

Class. math. : 11P99, 11B75

ISSN : 0303-1179
Publié avec le concours de : Centre National de la Recherche Scientifique

Legal information