Гипотеза Римана

[AD]

Brukvalub в сообщении #198538 писал(а):

Не зря неформальным лозунгом математиков является лозунг: "Гильберт жив!"

А кто докажет гипотезу Римана - убьет Гильберта?

[Руст]

Skipper писал(а):

Вот интересно, неужели доказательство этой гипотезы Римана труднее чем доказательства Великой теоремы Ферма, гипотезы Пуанкаре и т.д. которые уже доказаны. Еще Гильберт предсказывал, что гипотезу Римана докажут при его жизни. И до сих пор никто не может.

В 1900 г., когда Гильберт поставил свои (кажется 23) проблемы у него спросили о перспективах решения его проблем. По поводу гипотезы Римана он тогда заявил, что решат ее в ближайшее 5 лет, а на счёт другой проблемы он высказался, что он доживёт до её решения. Именно эту проблему решили первым в том же году. Так что в предсказаниях сильно ошибаются даже великие люди. Спустя лет 15 он уже не был так оптистичен насчёт гипотезы Римана. Кажется он сказал, что если он уснет лет на 300, то его первым вопросом будет, доказана ли гипотеза Римана.

[Skipper]

Я читал что есть в данный момент доказательство гипотезы Римана, которое ДО СИХ ПОР НИКЕМ НЕ ОПРОВЕРГНУТО. Де Бранж, кажется. Спрашивается, почему это доказательство не признано математическим сообществом, если его не могут опровергнуть.

[Droog_Andrey]

У Луи Де Бранжа весьма перспективный подход, однако в его попытке доказательства были обнаружены ошибки. В частности, нашлись контрпримеры к некоторым леммам. Впрочем, я надеюсь, что он таки-доведёт дело до конца рано или поздно.

[bot]

Если никто из математиков доказательства не читал, то в СМИ пишут, что доказательство никем не опровергнуто.

Цитата:

http://www.compulenta.ru/news/47486/

Найдено доказательство гипотезы Римана
11 июня 2004 года, 12:05 | Текст: Владимир Парамонов

Профессор математики из Университета Пердью Луи де Бранж де Бурсия, лауреат премии Эдварда Эллиотта, утверждает, что нашел доказательство гипотезы Римана, над решением которой ученые со всего мира бьются вот уже полтора века.

Цитата:

http://www.philosophy.nsc.ru/journals/philscience/23_04/sab.pdf

Поскольку де Бранж в своем доказательстве использует математические средства, экспертом в которых являются он сам и немногочисленная группа математиков, прежде чем приступить к оценке самого доказательства необходимо изучить огромный материал. А это требует слишком много времени. Даже немногие математики из тех, кто знает де Бранжа и понимает его метод, страшатся этого трудоемкого дела.

Прошло почти 5 лет...

[Droog_Andrey]

Повторяю, уже давным давно прочитали и нашли ошибки. Обсуждалось на всевозможных математических рассылках. Например, на NMBRTHRY.

[Руст]

Этот математик известен как человек, доказавший лет 20-30 назад гипотезу Бибербаха о коеффициентах разложения аналитической функции, однолистно отображающий единичный круг. Соответственно если нормипровать $f'(0)=1$, то $|f^{(n)}(0)|\le n$. Сейчас ему уже за 70 (в таком возрасте мало кто может решит серъёзную проблему) и в доказательстве использует только ему хорошо известный аппарат ТФКП. Уже раза 3 менял свое доказательство. Некоторому утверждению, на котором основано доказательство, приводили контрпримеры.

[Skipper]

Я читал, что если докажут гипотезу Римана, то можно будет сделать проверку на простоту любого числа n, с трудоемкостью алгоритма всего лишь O(ln^3 n). O от логарифма в 3-й степени. Если L - длина числа n (скажем, десятичных разрядов), то трудоемкость такого алгоритма будет по сути O от полинома 3-й степени L , что эквивалентно O(L^3).

Простой перебор всех делителей до корня из n дает трудоемкость алгоритма O(n^1/2), а от L - по сути O(A ^ L), т.е. с экспоненциальной трудоемкостью O от A в степени L, где хотя основание A - меньше чем разрядность системы исчисления n , с помощью которой определялось L, но такой экспоненциальный алгоритм при достаточно больших n по трудоемкости превысит любой полиномиальный алгоритм.

Доказано ли что задача факторизации числа (разложение числа на множители) может иметь только имеет экспоненциальную трудоемкость? Хотелось бы, чтобы доказали. Если кто-нибудь найдет алгоритм с полиномиальной трудоемкостью, то это сразу же разрушит все нынешние системы шифрования, т.к. можно будет за приемлемое время расшифровывать любую информацию.

Читал, что в доказательстве гипотезы Римана видят угрозу для знаменитой системы шифрования RSA, хотя не могу понять в чем угроза-то? Не будет же доказано, что задача факторизации числа может решаться с полиномиальной сложностью? Или я в чем-то неправ?

[Xaositect]

Skipper в сообщении #198931 писал(а):

Я читал, что если докажут гипотезу Римана, то можно будет сделать проверку на простоту любого числа n, с трудоемкостью алгоритма всего лишь O(ln^3 n). O от логарифма в 3-й степени. Если L - длина числа n (скажем, десятичных разрядов), то трудоемкость такого алгоритма будет по сути O от полинома 3-й степени L , что эквивалентно O(L^3).

Насколько я помню, сам алгоритм от гипотезы Римана не зависит, просто если ее использовать, получается более низкая оценка скорости.
По крайней мере точно есть полиномиальный алгоритм распознавания простоты
Оригинальная статья: http://www.cse.iitk.ac.in/users/manindr ... ity_v6.pdf

Skipper в сообщении #198931 писал(а):

Доказано ли что задача факторизации числа (разложение числа на множители) может иметь только имеет экспоненциальную трудоемкость? Хотелось бы, чтобы доказали. Если кто-нибудь найдет алгоритм с полиномиальной трудоемкостью, то это сразу же разрушит все нынешние системы шифрования, т.к. можно будет за приемлемое время расшифровывать любую информацию.

Нет, не доказано. Если бы удалось это доказать, то из этого следовало бы $P\neq NP$.
Вроде бы есть статьи о связи $P\neq NP$ и гипотезы Римана, насчет деталей не в курсе, может именно в этом и угроза.

[Skipper]

Какая именно связь между гипотезой Римана и гипотезой о том, что P равно NP ? Типа, если докажут гипотезу Римана, то опровергнут утверждение P = NP, и наоборот если докажут P = NP, то опровергнут Римана?

Добавлено спустя 6 минут 49 секунд:

Вот вы пишете -

>> Нет, не доказано. Если бы удалось это доказать, то из этого следовало бы P не равно NP. Вроде бы есть статьи о связи P не равно NP и гипотезы Римана, насчет деталей не в курсе, может именно в этом и угроза.
>>

Значит - если докажут гипотезу Римана, то станет ясно что P не равно NP? Но из того что P не равно NP - МОЖЕТ следовать то, что задача факторизации может иметь экспоненциальную сложность. И какая тут угроза для шифрования? Наоборот, лишнее подтверждение, что возможно никогда не решат факторизацию за полиномиальное время, т.е. возможно она решается только за экспоненциальное. Наоборот, доказательство P = NP должно нести угрозу шифрованию. Т.к. будет доказано что и задачу факторизации можно решить с полиномиальной сложностью. Я правильно понял?

[Xaositect]

Так, я погуглил и извиняюсь за то, что ввел Вас в заблуждение.
Это не та гипотеза Римана, а некая уже доказанная Riemann hypthesis for finite fields.
И из каких-то ее обобщений выводится $P\neq NP$.

[Droog_Andrey]

Xaositect в сообщении #198938 писал(а):

Насколько я помню, сам алгоритм от гипотезы Римана не зависит

Речь идёт о тесте Миллера:
http://mathworld.wolfram.com/MillersPrimalityTest.html

Xaositect в сообщении #198938 писал(а):

По крайней мере точно есть полиномиальный алгоритм распознавания простоты

Недавно его улучшили:
http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0902&L=nmbrthry&T=0&P=1323

[Руст]

Skipper писал(а):

Я читал, что если докажут гипотезу Римана, то можно будет сделать проверку на простоту любого числа n, с трудоемкостью алгоритма всего лишь O(ln^3 n). O от логарифма в 3-й степени. Если L - длина числа n (скажем, десятичных разрядов), то трудоемкость такого алгоритма будет по сути O от полинома 3-й степени L , что эквивалентно O(L^3).

Доказано только в случае справедливости обобщённойгипотезы Римана (справедливость гипотезы типа Римана и для L функций Дирихле). Тогда достаточно по тесту Рабина-Миллера проверять для всех простых меньше $p<2ln^2n$.

Цитата:

Читал, что в доказательстве гипотезы Римана видят угрозу для знаменитой системы шифрования RSA, хотя не могу понять в чем угроза-то? Не будет же доказано, что задача факторизации числа может решаться с полиномиальной сложностью? Или я в чем-то неправ?

Никакой угрозы.
Между гипотезой Римана и проблемой P=NP пока нет прямой связи, т.е. одно другое не влечёт. Даже если P=NP, RSA устоит, если например лучший алгоритм факторизации числа N потребует порядка $n^{20}$ операций, где $n=1+[log_2 N]$ количество двоичных разрядов числа N.

[sceptic]

Недавно попалась мне на глаза любопытная статья Странный случай Луи де Бранжа Карла Саббага (тот, который написал известную книгу про ГР Dr. Riemann's Zeros) о работе француза по доказательству ГР и об отношении к ней математической общественности.
Странно, что эта статья опубликована в философском журнале.

[Skipper]

Ну если разница между проверкой на простоту и факторизацией будет в степенях соответственно 3-й и 20-й полиномов, определяющих трудоемкость, то может RSA и устоит. Но лучше все таки чтобы эта разница была вообще в разных классах роста сложности - т.е. чтобы задача факторизации решалась только с экспоненциальной трудоемкостью.

А как насчет P=NP? Математики верят больше, что P=NP или что P не равно NP ? Вот в гипотезу Римана, вроде бы верят практически все.