Гипотеза Кэмерона — Эрдёша

Гипотеза Кэмерона — Эрдёша — доказанная в 2003 году комбинаторная гипотеза.

Формулировка

Число $s(N)$ свободных от сумм подмножеств в $\{1,\ldots ,N\}$ равно $O\left({2^{N/2}}\right)$.

Замечания

Сумма двух нечётных чисел всегда чётна, так что любое множество нечётных чисел всегда свободно от сумм. Имеется $\lceil N/2\rceil$ нечётных чисел в $|N|$, соответственно получается $2^{N/2}$ подмножеств нечётных чисел в $|N|$. Гипотеза утверждает, что эта величина с точностью до константы определяет асимптотическое поведение количества свободных от сумм множеств.

История

Гипотеза была предложена Питером Кэмероном и Палом Эрдёшом в 1988 году, в 2003 году доказана Беном Грином и независимо — Александром Сапоженко.

Сапоженко показал, что $s(N)=C_{0}2^{N/2}$ при четных N и $s(N)=C_{1}2^{(N+1)/2}$ при нечётных N, где $C_{0}=6.0...,C_{1}=5.0....$