Ensemble sans somme

En combinatoire additive et en théorie additive des nombres, un sous-ensemble ${\displaystyle A}$ d'un groupe abélien noté additivement est un ensemble sans somme si la somme d'ensembles ${\displaystyle A\oplus A=\{a+b\mid a,b\in A\}}$ est disjointe de ${\displaystyle A}$. De manière équivalente, ${\displaystyle A}$ est sans somme si l'équation ${\displaystyle a+b=c}$ n'a pas de solution avec ${\displaystyle a,b,c\in A}$.

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 ${\displaystyle a_{n}}$ de sous-ensembles sans somme de {1, … , n}, pour un entier n ?

${\displaystyle a_{n}}$ est trivialement ${\displaystyle \geqslant n+1}$ puisque l'ensemble vide et les singletons sont sans somme.

Les premières valeurs en commençant à ${\displaystyle n=1}$ sont :

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

Par exemple, ${\displaystyle a(3)=6}$, car hormis le vide et les singletons, seuls ${\displaystyle \{1,3\}}$ et ${\displaystyle \{2,3\}}$ sont sans somme.

Ben J. Green a montré^[1] que la réponse asymptotique est O(2^n/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 ∼ c₀ 2^n/2 si n est pair, et ∼ c₁ 2^n/2 si n est impair, où c₀ et c₁ 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 ?

• Suite sans somme

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

• Portail des mathématiques