Conjecture de Cameron-Erdős
# Conjecture de Cameron-Erdős

En combinatoire, la conjecture de Cameron-Erdős est l'énoncé selon lequel le nombre d'ensembles sans somme contenus dans l'ensemble {1, … , N} est $O(2^{N/2}).$

Comme la somme de deux entiers impairs est un entier pair, un ensemble d'entiers impairs est toujours sans somme. Il y a ⎡N/2⎤ entiers impairs inférieurs ou égaux à N, et il y a donc $2^{N/2}$ sous-ensembles de nombres impairs dans {1, … , N}. La conjecture de Cameron-Erdős affirme que ceci compte le nombre d'ensembles sans somme, à une constante multiplicative près.

La conjecture a été formulée par Peter J. Cameron et Paul Erdős en 1988. Elle a été démontrée par Ben Green et indépendamment par Alexander Sapozhenko. Sapozhenko donne une borne plus précise : le nombre de sous-ensembles sans somme est ∼ $c_0$ $2^{N/2}$ si N est pair, et ∼ $c_1$ $2^{N/2}$ si N est impair, où $c_0$ et $c_1$ sont des constantes.

