Нарушить теорему Семереди

[Dims]

Прослушав подкаст на Постнауке: http://postnauka.ru/video/36221

я сперва подумал, что теорема Семереди интуитивно понятна. Действительно, множество натуральных чисел бесконечно и, как их ни раскрашивай, всё равно там останутся всевозможные подпоследовательности.

Но потом мне пришло в голову, допустим, что если я возьму числа $2^N$, то что, среди них тоже можно найти прогрессию любой длины?

Или я что-то не так понял в формулировке теоремы?

[nnosipov]

Dims в сообщении #929696 писал(а):

если я возьму числа $2^N$, то что, среди них тоже можно найти прогрессию любой длины?

Какое там любой длины, не найдёте даже прогрессии длины 3.

[venco]

А при чём тут числа $2^N$?

[nnosipov]

Dims в сообщении #929696 писал(а):

Или я что-то не так понял в формулировке теоремы?

Возможно, судя по примеру со степенями двойки. Этот пример не удовлетворяет условиям теоремы: степеней двойки на отрезке $[1,N]$ слишком мало ($O(\log{N})$), а множество $A$ должно иметь мощность $\delta N$ с некоторым фиксированным $\delta>0$.

[grizzly]

(Оффтоп)

Давным-давно (лет 10 тому) с огромным интересом следил за попытками найти ограничения с другой стороны (как здесь, например). Это, правда, больше Computer Science, чем математика, зато можно было и самому пробовать.

Помню, какой энтузиазм вызвало первое сообщение, что между 1 и 1092 $(< 3^7/2)$ помещается 128 $(= 2^7)$ чисел, не содержащих прогрессий длины 3. (Кто знает, поймёт :)

[Dims]

То есть, суть условий теоремы в том, что последовательность "покрашенных" чисел должна иметь плотность не ниже заданной на всей бесконечной числовой оси? Понятно.

-- Вт ноя 11, 2014 17:38:59 --

В том же подкасте была упомянута теорема, что простые числа обладают этим свойством (среди них можно выделить любую прогрессию). Означает ли это, что плотность простых чисел не опускается ниже некоторого значения?

-- Вт ноя 11, 2014 17:41:07 --

Нет, судя по Вики, это не так.

Означает ли это, что теорему Семереди, вероятно, можно усилить?

[shwedka]

Dims в сообщении #929696 писал(а):

Прослушав подкаст на Постнауке: http://postnauka.ru/video/36221

я сперва подумал, что теорема Семереди интуитивно понятна. Действительно, множество натуральных чисел бесконечно и, как их ни раскрашивай, всё равно там останутся всевозможные подпоследовательности.

Но потом мне пришло в голову, допустим, что если я возьму числа $2^N$, то что, среди них тоже можно найти прогрессию любой длины?

Или я что-то не так понял в формулировке теоремы?

Такая уж наука математика.
что-то интуитивно ясное
может оказаться
неверным

[Nilenbert]

Dims в сообщении #929752 писал(а):

Означает ли это, что теорему Семереди, вероятно, можно усилить?

Существует гипотеза Эрдёша об арифметических прогрессиях, утверждающая что если

$$ \sum_{n\in A} \frac{1}{n} = \infty $$

, то $A$ содержит арифметическую прогрессию любой наперёд заданной длины. Не доказана до сих пор.