Замечательные задачи Эрдёша по теории чисел

Автор темы Researcher 
ОбъявленияПоследний пост
ОбъявлениеСтуденты и преподаватели мехмата МГУ могут бесплатно получать лицензию на Wolfram Mathematica25.11.2020 00:55
ОбъявлениеИсследовательские гранты фонда «БАЗИС» 202118.02.2021 17:56
ОбъявлениеАктуарий в PPF Life Insurance (Junior)25.03.2021 21:35
16.01.2007 10:00
Замечательные задачи Эрдёша по теории чисел
Легендарный Пауль Эрдёш оставил наследство - замечательные задачи по теории чисел ! Многие очень интересны и математикам 21 века.
Как говорил Эрдёш, учитесь "перерабатывать задачи в теоремы" ! Успехов !



С уважением,
Борис
16.01.2007 10:04
Задача 1 "ослабленная Гольдбаха"
Задача 1 "ослабленная Гольдбаха" :

Эрдёш и Мозер( 1959 ) спрашивают :

" существует ли для каждого целого n > 0 два целых числа
a, b, таких, что фи(a) + фи(b) = 2*n. "

( где фи(x) - функция Эйлера, x > 0 целое число. )

Из справедливости гипотезы Гольдбаха следует положительный ответ на задачу Эрдёша !

Возможно ли независимое решение задачи Эрдёша ?
16.01.2007 10:29
Задача 2 "о функции пи(x)"
Рассмотрим целочисленную функцию

пи(x) - число простых чисел, непревосходящих x.
пи(1) = 0, пи(2) = 1, пи(3) = 2, ...

Доказать или опровергнуть справедливость неравенства :

пи(x + y) =< пи(x) + пи(y)

Эрдёш называл доказательство данного неравенства - утверждением с далеко идущими последствиями !
16.01.2007 14:13
"решение"
Воспользуемся приближением pi(x) = x/ln x :)

Пусть y >= x, y = kx, k >= 1.
Тогда надо доказать, что

(k+1)x / (ln(k+1) + ln x) <= x / ln x + kx / (ln k + ln x) = x * (ln k + ln x + k ln x) / (ln k + ln x) ln x

Сокращаем на x, переносим знаменатель левой части в числитель правой, а знаменатель правой - в числитель левой, раскрываем скобки, сокращаем и получаем:

k*ln k*ln x <= ln (k+1) * (ln k + ln x + k ln x)
Сиё неравенство очевидно (т.к. в правой части содержится k*ln(k+1)*ln x + ещё что-то).

Естественно, это решение является "решением", потому что особо придирчивых может не устроить приближение pi(x) = x/ln x ;)
16.01.2007 15:11
не сломает ли ваше "решение" особый случай ?
Если x и y=2 - числа простые, тогда pi(x+2) = pi(x)+1 = pi(x)+p(2).
А как у вас :?
16.01.2007 15:54
да нет вроде
pi(4) <= pi(2) + pi(2)
И у меня так же. Нестрогое неравенство сохраняется)
16.01.2007 17:42
А требуется ли доказательство?
Если я правильно понял условие, то задачу 2 можно рассмотреть логически:
Допустим, что y>x (больше, для удобства).
Рассмотрим, как распределены простые числа в пределах числа y. Сначала ряд простых "плотный", но по мере "продвижения" вдоль числовой оси плотность падает. Добавляя к числу y число x, мы тем самым продвигаемся еще дальше - в еще более "разреженную" область.
И вопрос автора теперь звучит так: Плотнее ли расположены простые числа в начале числовой оси (в пределах числа x), чем в на равном ему интервале от y до (y+x)?
На это есть простой ответ: Да.

16.01.2007 18:19
Поясните, пожалуйста.
Во-первых, я хотел бы спросить, правильно ли считаю функцию Эйлера. У меня получается Фи(3)=2, Фи(4)=2, Фи(5)=4, Фи(6)=2, Фи(7)=6...
Если правильно, то, во-вторых, хотелось бы узнать, в чем заключается связь гипотезы Гольдбаха и приведенной задачи?

16.01.2007 20:08
связь простая
Если гипотеза Гольдбаха (в сильной форме) верна, то число 2n+2 можно представить в виде суммы двух простых p1+p2, тогда фи(p1)+фи(p2) = 2n
16.01.2007 20:12
А откуда такой ответ берётся?
А откуда такой ответ берётся? Из того, что производная функции x/ln убывает? Я понимаю, что ряд простых чисел чем дальше в лес, тем больще разреженный, но строго как доказать?
17.01.2007 03:47
контрпример: пи(1+2) > пи(1) + пи(2)
точнее надо формулировать задачи.

вот вам тривиальный контрпример к текущей формулировке: пи(1+2) > пи(1) + пи(2)

17.01.2007 04:25
2-я гипотеза Харди-Литтлвуда
А вообще, за исключением тривиальных примеров, это открытая проблема, которая носит имя Харди-Литтлвуда (2-я гипотеза Харди-Литтлвуда).

Можно показать, что существует интервал из 3159 последовательных чисел, среди которых имеется 447 чисел не делящихся на простые, непревосходящие 3159. Если окажется верна 1-я гипотеза Харди-Литтлвуда, то найдется отрезок (а точнее бесконечно много отрезков) из 3159 последовательных чисел [n+1,n+3159], содержащий 447 простых. Этот отрезок интересен тем, что пи(3159)=446<447, откуда немедленно следует контрпример ко 2-й гипотезе Харди-Литтвуда:
пи(n+3159)=пи(n)+447 > пи(n)+пи(3159)=пи(n)+446
Таким образом, 1-я гипотеза Харди-Литтлвуда влечет отрицание 2-й их же гипотезы.

Существование требуемого отрезка [n+1,n+3159] пока остается под вопросом - его ищут на http://www.opertech.com/primes/k-tuples.html.
17.01.2007 08:47
Уваж. maxal ! Речь идёт не только о задачах, лично поставленных
Паулем Эрдёшом, но чаще всего о задачах, которые он решал и пропагандировал !
:)
Так как пи(p) = пи(p-1)+1, то до вас всем было ясно, что |x-y| > 1, где всегда p - нечетное простое число!
:)
Полагая пи(1) =+оо, мы лишим вас навсегда возможности нас критиковать !
:)
Где теперь ваш контрпример ?
8))



С уважением,
Борис
17.01.2007 09:34
Задача 3 "арифметические прогрессии"

Пусть A - такое множество натуральных чисел, что сумма величин, обратных элементам A, бесконечна. Верно ли, что A содержит сколь угодно длинные арифметические прогрессии?


Задача взята из статьи
М. В. Волков Пол Эрдёш: необычная жизнь и необычайная математика



С уважением,
Борис
17.01.2007 10:56
уточняю
Цитата

Борис Тарасов писал(а) :
Так как пи(p) = пи(p-1)+1, то до вас всем было ясно, что |x-y| > 1, где всегда p - нечетное простое число!
:)
Полагая пи(1) =+оо, мы лишим вас навсегда возможности нас критиковать !
:)
Где теперь ваш контрпример ?
8))
Ну во-первых, может быть и "было ясно", но никто этого не озвучил. Кроме того, я вовсе не претендовал на первооткрывательство чего бы то ни было, а указал вам на недостаточную четкость формулировки.

Во-вторых, "положить пи(1) =+оо" вы не можете, так как пи() - это конкретная и уже определенная функция со значением пи(1)=0.

В-третьих, насчет "настоящего" контрпримера я написал в отдельном сообщении с темой "2-я гипотеза Харди-Литтлвуда". Исходя из изложенного там, контрпримера не существует, если min{x,y}<3159. С другой стороны, он скорее всего существует для x=3159 и некоторого y, которое было бы интересно найти.
17.01.2007 11:02
это известная открытая проблема
Это очень известная задача. Упоминается в "Конкретной Математике". Кроме того, если мне память не изменяет, Рон Грэхем (один из авторов КМ) говорил, что Эрдёш назначил за ее решение определенную сумму (точную цифру не помню). Это денежное предложение должно в силе и по сей день (см. статью про про задачи и чеки от Эрдеша).

17.01.2007 12:17
эта задача "дорогая" - $3000. В России не потянет даже на собачью будку :)
Усилия для решения задач требовались огромные, поэтому Эрдёш говорил, что его премии грубо нарушают закон о минимальной оплате труда. ... ))
17.01.2007 16:48
Уточнение
Как считать сумму чисел, принадлежащих множеству A? Если A - счётно, тогда это будет, понятно, сумма ряда этих чисел, занумерованных в любом порядке. А как быть с более чем счётным множеством? (не обязательно континуальным :))
17.01.2007 17:57
Ай-ай-ай
Указано же, что A - это подмножество натуральных чисел! Это уже значит что A не более чем счётно.
17.01.2007 18:41
Тфу ты
И в самом деле %)
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти