WikiSort.ru - Не сортированное

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

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

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

Замечания

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

История

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

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

Ссылки

Для улучшения этой статьи по математике желательно: Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).