2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Нарушить теорему Семереди
Сообщение11.11.2014, 15:52 
Аватара пользователя
Прослушав подкаст на Постнауке: http://postnauka.ru/video/36221

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

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

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

 
 
 
 Re: Нарушить теорему Семереди
Сообщение11.11.2014, 16:01 
Dims в сообщении #929696 писал(а):
если я возьму числа $2^N$, то что, среди них тоже можно найти прогрессию любой длины?
Какое там любой длины, не найдёте даже прогрессии длины 3.

 
 
 
 Re: Нарушить теорему Семереди
Сообщение11.11.2014, 16:08 
А при чём тут числа $2^N$?

 
 
 
 Re: Нарушить теорему Семереди
Сообщение11.11.2014, 16:12 
Dims в сообщении #929696 писал(а):
Или я что-то не так понял в формулировке теоремы?
Возможно, судя по примеру со степенями двойки. Этот пример не удовлетворяет условиям теоремы: степеней двойки на отрезке $[1,N]$ слишком мало ($O(\log{N})$), а множество $A$ должно иметь мощность $\delta N$ с некоторым фиксированным $\delta>0$.

 
 
 
 Re: Нарушить теорему Семереди
Сообщение11.11.2014, 17:05 
Аватара пользователя

(Оффтоп)

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

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

 
 
 
 Re: Нарушить теорему Семереди
Сообщение11.11.2014, 17:37 
Аватара пользователя
То есть, суть условий теоремы в том, что последовательность "покрашенных" чисел должна иметь плотность не ниже заданной на всей бесконечной числовой оси? Понятно.

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

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

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

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

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

 
 
 
 Re: Нарушить теорему Семереди
Сообщение13.11.2014, 13:39 
Аватара пользователя
Dims в сообщении #929696 писал(а):
Прослушав подкаст на Постнауке: http://postnauka.ru/video/36221

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

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

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


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

 
 
 
 Re: Нарушить теорему Семереди
Сообщение15.11.2014, 05:35 
Аватара пользователя
Dims в сообщении #929752 писал(а):
Означает ли это, что теорему Семереди, вероятно, можно усилить?


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

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

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

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group