Русская Википедия:Гипотеза Кэмерона — Эрдёша

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

Замечания

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

История

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

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