Ensemble sans somme

En combinatoire additive et en théorie additive des nombres, un sous-ensemble ${\displaystyle A}$ d'un groupe abélien 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 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}.

La question suivante a été posée concernant les ensembles sans somme :

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

Les premières valeurs sont :

1, 2, 3, 6, 9, 16, 24, 42, 61, 108, 151, 253, 369, 607, 847, 1400, 1954,

C'est la suite A007865 de l'OEIS. 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 ?

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.