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

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

ФормулировкаПравить

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

ЗамечанияПравить

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

ИсторияПравить

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

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