Ensemble sans somme

En combinatoire additive et en théorie additive des nombres, un sous-ensemble d'un groupe abélien noté additivement est un ensemble sans somme si la somme d'ensembles est disjointe de . De manière équivalente, est sans somme si l'équation n'a pas de solution avec .

Par exemple, l'ensemble des entiers impairs est un sous-ensemble sans somme de l'ensemble des entiers ; de même, si n est un entier naturel pair, l'ensemble {n/2 + 1, … , n} est un sous-ensemble sans somme de {1, … , n}.

Concernant ces ensembles, on peut se poser la question suivante :

Quel est le nombre de sous-ensembles sans somme de {1, … , n}, pour un entier n ?

est trivialement puisque l'ensemble vide et les singletons sont sans somme.

Les premières valeurs en commençant à sont :

2, 3, 6, 9, 16, 24, 42, 61, 108, 151, 253, 369, 607, 847, 1400, 1954,..., suite A007865 de l'OEIS.

Par exemple, , car hormis le vide et les singletons, seuls et sont sans somme.

Ben J. Green a montré[1] que la réponse asymptotique est O(2n/2), comme suggéré dans la conjecture de Cameron-Erdős[2].

Alexander Sapozhenko[3] a montré plus précisément que le nombre est c0 2n/2 si n est pair, et c1 2n/2 si n est impair, où c0 et c1 sont des constantes.

D'autres questions ont été posées et examinées[4] :

  • Quel est le nombre de sous-ensembles sans somme dans un groupe abélien ?
  • Quelle est la taille maximale d'un sous-ensemble sans somme dans un groupe abélien ?

Notes et références

modifier
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sum-free set » (voir la liste des auteurs).
  1. (en) Ben Green, « The Cameron–Erdős conjecture », Bulletin of the London Mathematical Society, vol. 36,‎ , p. 769-778
  2. (en) Peter J. Cameron et Paul Erdős, « On the number of sets of integers with various properties », dans R. A. Mullin (éditeur), Number Theory : Proceedings of the First Conference of the Canadian Number Theory Association (Banff, 1988), Berlin, de Gruyter, , p. 61-79
  3. (en) Alexander A. Sapozhenko, « The Cameron–Erdős conjecture », Discrete Mathematics, vol. 308, no 19,‎ , p. 4361-4369 (DOI 10.1016/j.disc.2007.08.103)
  4. (en) Ben Green et Imre Z. Ruzsa, Sum-free sets in abelian groups, 2005. « math/0307142v4 », texte en accès libre, sur arXiv.

Voir aussi

modifier

Lien externe

modifier

(en) Eric W. Weisstein, « Sum-Free Set », sur MathWorld