Полином от 26 переменных

Vano

от 26 переменных, множество положительных значений которого на целых числах совпадает со множеством простых чисел...

natunchik

Че-то подозрительно мне число 26...

NHGKU2

и чо?

Xephon

уже было давным-давно в Кванте
связано с решением 10-й проблемы Гильберта

stm7543347

Больше не получилось, буквы кончились.

stm7543347

И как-нибудь это поможет нам сломать современные системы шифровки инфы?

Xephon

или я что-то не рюхаю
или тут умножается положительное число (k+2) на 1-(большое положительное)
мало того, что это число почти всегда положительно, так оно еще и на k+2 делицца.
или я неправильно (скорее всего) понял фигурные скобки

Xephon

There is an apparent paradox: the expression clearly factorises. Indeed it is of the form (k + 2){1 - M}. However, M is a sum of squares, so the expression is positive if and only if M = 0. and its value is then k + 2. So the polynomial M has to be constructed so that
M(k, other variables) = 0 if and only if k + 2 is prime.
теперь все ясно
также ясно, что никаким раком нам это не поможет для эффективного нахождения простых чисел

filippov2005

Мб с помощью меньшего количества результат записать сложнее (длиннее запись а с помощью большего - некрасивее, потому что придется использовать что-то кроме букв латинского алфавита?
А т.к. вопросом быстрого вычисления простых чисел по этой громоздкой формуле авторы, скорее всего, не заморачивались , то они выбрали самый удобочитаемый вариант.

kachokslava

индексы у букв отменили уже?

natunchik

гм.
Это то есть M(a..z) = 0 <=> k-2 простое.
Так даже прикольней на самом деле.
На самом деле очевидно, что такой полином существует, просто потому что есть такая формальная логика ЕА, всеми выражениями которой являются полиномы, и которая достаточно мощна. Там еще забавный прикол был - полином, описывающий экспоненциальный рост одной из своих переменных, что ли. Не помню, хотя летом ботал =(

locker

На самом деле очевидно, что такой полином существует

ну-ну-ну
а) это не доказано, как не доказано и обратное
б) такой полином ищут уже лет триста

Kraft1

А где Proof

Vitaminka

его нашли

Vikuschechka9

Скока ж бабок отвалят тем чувакам, кто его нашёл?
И ещё, откуда этот скриншот? Сорц есть? ;-)

Tfrn

Ты про это... http://ega-math.narod.ru
F(a, b, с, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z) =
= {k + 2} {1 – (wz + h + j – q)^2 – (2n + p + q + z – e)^2
– (a^2y^2 – y^2 + 1 – x^2)^2 – ({e^4 + 2e^3}{a + 1}^2 – o^2)^2
– (16{k + 1}^3{k + 2}{n + 1}^2 + 1 – f^ 2)^2
– ({(a + u^4 – u^2a)^2 – 1}{n + 4dy}^2 + 1 – {x + cu}^2)^2
– (a^i + k + 1 – l – i)^2
– ({gk + 2g + k + 1}{h + j} + h – z)^2
– (16r^2y^4{a2 – 1} + 1 – u^2)^2
– (p – m + l{a – n – 1} + b{2an + 2a – n^2 – 2n – 2})^2
– (z – pm + pla – p^2l + t{2ap – p^2 – 1})2
– (q – x + y{a – p – 1} + s{2ap + 2a – p^2 – 2p – 2})^2
– (a^2l^2 – l^2 + 1 – m^2)^2 – (n + l + v – y)^2}.

natunchik

Ты не рюхаешь.
Это доказано.
Собственно, если бы у меня бы был бы инет, то я бы мог там поискать, и дать тебе сцылку на метод построения такого полинома.
Еще раз перечитай мой пост, на который ты отвечал. Необходимый (наверное) комментарий - ЕА алгебра это такая формальная логика, построенная на натуральных числах и операциях сложения и умножения, с понтом, что ничего проще, но позволяющего формулировать достаточно мощные утверждения (типа непротиворечивости данной формальной логики быть не может. Там ВСЁ полиномы. Честно.

natunchik

Собственно, оно все было построено где-то почти сразу после 1930-го года. Ну то есть хз, когда именно. Но я лично видел строгую формулировку теоремы Геделя именно в терминах ЕА.

electricbird

>оно все было построено где-то почти сразу после 1930-го года. Ну то есть хз, когда именно.
>Но я лично видел строгую формулировку теоремы Геделя именно в терминах ЕА
следствие: лично ты "был построен" почти сразу после 1930-го года. Ну то есть хз, когда именно.

natunchik

Курт Гедель в 1930 как-то строго доказал свою теорему о неполноте. Доказать ее _строго_ он мог опираясь только на какую-то достаточно базовую формальную логику. Я видел доказательство, основанное на ЕА. Я не уверен в аутентичности этого доказательства, тем не менее, я полагаю, что оно имеет крайне много общего с оригинальным, и появилось ненамного позже.
Кста, может кто-нить дать книжку (можно электронную) про теорему Геделя? А то меня вдруг напрягло, что я уже ваще ничего кроме формулировки не помню...

Xephon

скорее всего он доказывал для формальной арифметики
это ИП + аксиомы Пеано
можно долго трепаться об "очевидности" существования этого полинома. я же попрошу тебя привести схему доказательства, если тебе оно ясно.

natunchik

В том-то все и дело, что я с удивлением обнаружил, что я почти полностью забыл, как именно там все вводилось и выводилось.
Тем не менее схема доказательства такова: строим алгоритм перевода вычисления реализуемого произвольной машыной тьюринга в EA (ИП + аксиомы Пеано, правда я не знаю, что такое ИП . Ето сделать можно, сам видел. То ЕА, которое я помню, это, по ходу дела, полиномы. Что с ними делаеццо, я, правда, не помню =(. Ну так вот. Потом строим машину тьюринга, выдающую простые числа подряд. Переводим. Вуаля.

Vano

Сцылки:
фактическое доказательство существования полинома (1970 год):
Yu. V. Matiyasevich. Diofantovost' perechislimih mnozhestv. Dokl. AN SSSR, 191(2):278-282, 1970
конструктивное построение (1976 год):
James P. Jones, Daihachiro Sato, Hideo Wada, and Douglas Wiens, Diophantine representation of the set of prime numbers. The American Mathematical Monthly, 83(6):449-464, 1976
P.S. Есть и другие полиномы от 10 переменных какой-то немерянной степени и есть от > 40 переменных какой небольшой степени. А вообще, их счётное число вроде.

Xephon

ИП - исчисление предикатов
то, что ты сказал - доказывается м.б. и несложно. по крайней мере, можно показать все вычислимые на машине Тьюринга ф-ции являются арифметичными в формальной арифметике (м.б. даже и в ЕА).
только вот преобразовать любую замкнутую формулу к виду, где все кванторы спереди - кванторы существования, в формальной арифметике нельзя.
вообще утверждение, о котором ты говоришь - ровно теорема Матиясевича, которая решила 10-ю проблему Гильберта. мне оно лично не кажется очевидным, правда доказательства я пока не читал

natunchik

Там не было кванторов. Там были полиномы. As Far As I Remember.
Оставить комментарий
Имя или ник:
Комментарий: