Обсуждение диофантовости простых чисел

[svv]

Удивился, когда пару лет назад узнал, что

Вики, статья Простое число писал(а):

существуют многочлены, множество положительных значений которых при неотрицательных (целых — svv) значениях переменных совпадает с множеством простых чисел

Например, полином Джонса 25 степени от 26 переменных (можно увидеть там же). Оговорка, что значение полинома будет простым числом, если оно будет положительным при неотрицательных значениях всех 26 переменных, в то время не показалась существенной. Так, небольшое неудобство, особенность функционирования девайса. Главное, что покрывается всё множество простых чисел.

Но оказывается, что с поиском аргументов, обеспечивающих положительные значения полинома, большие проблемы:

arseniiv в сообщении #1095236 писал(а):

Я его тут погонял со случайными аргументами. По несколько миллионов из 0…999, 0…9, 0…4, 0…2, 0…999 999 999 и ещё некоторых интервалов. Ноль положительных значений. Это показывает просто и прямо, что ничем не приправленный перебор практически бессмыслен.

grizzly в сообщении #1095242 писал(а):

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

И это уже потрясло.

[arseniiv]

Присоединюсь. Я надеялся наткнуться при переборе хоть на что-нибудь!

[svv]

Да... Коль я назвал выше этот полином девайсом, надо теперь заметить, что у него недружественный интерфейс.

[Aritaborian]

svv в сообщении #1095423 писал(а):

И это уже потрясло.

Подобные неконструктивные доказательства как-то раздражают, не находите? (Хотя и потрясают). То ли дело, к примеру, множество Мандельброта. Оно тоже потрясает, но его можно построить (и увидеть). «Парадокс» Банаха — Тарского с разбиением шара, кстати, конструктивен или точно так же, как упоминаемый многочлен: «доказали, что можно, но не знаем, как конкретно»?

[ovsov]

svv в сообщении #1095423 писал(а):

Удивился, когда пару лет назад узнал, что

Вики, статья Простое число писал(а):

существуют многочлены, множество положительных значений которых при неотрицательных (целых — svv) значениях переменных совпадает с множеством простых чисел

Например, полином Джонса 25 степени от 26 переменных (можно увидеть там же).

А меня еще 40 лет назад удивило (по журналу Квант о рез-те Матиясевича) то, что алфавитный пересчет переменных выдал (по памяти) 23 переменных. Уж точно меньше 24.

[arseniiv]

Возможны полиномы с разным числом переменных и степенью.

[svv]

Aritaborian
Раздражают, и не только нас, не зря на свете водятся конструктивисты. Я их понимаю, хоть чистый конструктивизм мне не по душе. В данном случае рано опускать руки. Может, кто-нибудь получит (или уже получил) какие-то оценки на значения параметров.

Интересная будет ситуация в каком-нибудь аналогичном случае, если будет доказано, что конструктивно задать объект невозможно, хоть он и существует. Интересно, нет ли здесь логического противоречия.

ovsov в сообщении #1095496 писал(а):

Уж точно меньше 24

Здесь точно 26, я посчитал. Не вручную. Скопировал формулу в Word, затем удалил заменой все небуквенные символы, остальные отсортировал по возрастанию, разбил на строки, так, чтобы на каждой строке были только одинаковые символы и посмотрел, сколько в документе строк.

[arseniiv]

(Оффтоп)

poly = ...; Variables[poly]

[Aritaborian]

svv, я не считаю себя конструктивистом. Меня всего лишь малость раздражает невозможность (в данный момент!) в каких-то конкретных случаях предъявить какой-либо конкретный пример существования чего-то; но я не считаю это принципиальным препятствием для существования математики, её непротиворечивости и уж тем более её пользы для человека. Я скорее платонист.

[Anton_Peplov]

Aritaborian в сообщении #1095487 писал(а):

«Парадокс» Банаха — Тарского с разбиением шара, кстати, конструктивен или точно так же, как упоминаемый многочлен: «доказали, что можно, но не знаем, как конкретно»?

Нет, не конструктивен, поскольку опирается на аксиому выбора. Опирался бы на какой-нибудь вычислимый предикат - был бы конструктивен.

-- 31.01.2016, 15:31 --

svv в сообщении #1095502 писал(а):

Интересная будет ситуация в каком-нибудь аналогичном случае, если будет доказано, что конструктивно задать объект невозможно, хоть он и существует. Интересно, нет ли здесь логического противоречия.

Невозможно конструктивно задать множество всех тотальных вычислимых функций, например (тотальная функция - это определенная на всем $\mathbb{N}$). Вообще в теории алгоритмов таких объектов до потолка.

[svv]

Спасибо. Как бы чётко отделить две ситуации?:
1. Объектов с таким-то свойством великое множество, привести несколько примеров — не проблема, просто нельзя конструктивно задать всё множество.
2. Доказано, что объект с таким-то свойством существует, возможно, не один, построить его явно невозможно.

[Anton_Peplov]

На первый наивный взгляд, достаточно договориться, что объект, упомянутый в п. 2 - не множество (а также не класс, не категория и что там еще формализует интуитивное представление о совокупности).

На самом деле не достаточно. Во-первых, на языке теории множеств все - множества. И упорядоченные пары, и функции, и отношения, и все остальное. Во-вторых, даже если договориться, что функции - не множества, задача построить множество эквивалента задаче построить его характеристическую функцию.

Собственно, я не уверен, что пп. 1 и 2 можно математически точно разграничить.

[ovsov]

svv в сообщении #1095502 писал(а):

ovsov в сообщении #1095496 писал(а):

Уж точно меньше 24

Здесь точно 26, я посчитал. Не вручную. Скопировал формулу в Word, затем удалил заменой все небуквенные символы, остальные отсортировал по возрастанию, разбил на строки, так, чтобы на каждой строке были только одинаковые символы и посмотрел, сколько в документе строк.

"Квант", 1987, № 4; цитата со стр.14 :
Совсем недавно был найден многочлен, все положительные значения
(Окончание см. на с. 38)
Открыли (перешли) на 38-ю и читаем дальше:
которого в целых точках совпадают с множеством всех простых чисел.
Этот многочлен имеет степень 25 и для его записи нужно использовать
все буквы английского алфавита --- переменных всего 26

далее приведен этот многочлен и набран зеленым цветом.
(набирать в латехе лень)

И снова идем по тексту:
Появился он в результате исследований диофантовых уравнений и связан с
решением 10- ой проблемы Гильберта советским математиком Ю. А. Матия-
севичем (см. "Квант", 1970, № 7, с. 39). --- конец цитаты.
Да, сам я не совсем был точен- сейчас увидел недостачу двух букв- переменных.
нет буквы b и нет буквы o. Более того, сейчас увидел в многочлене безхозный 0,
возведенный в квадрат.
Уверен, что речь идет об одном и том же многочлене, но из разных источников.

[vicvolf]

ovsov в сообщении #1095559 писал(а):

Совсем недавно был найден многочлен, все положительные значения
которого в целых точках совпадают с множеством всех простых чисел.
Этот многочлен имеет степень 25
Появился он в результате исследований диофантовых уравнений и связан с
решением 10- ой проблемы Гильберта советским математиком Ю. А. Матия-
севичем (см. "Квант", 1970, № 7, с. 39). --- конец цитаты.

Можно указать гораздо более простое диофантово уравнение, удовлетворяющее данному требованию.

[Aritaborian]

Так что ж вы его не указываете? Или можно лишь привести доказательство его существования? Забавно; это было бы примером «неконструктивности второго уровня». Вообще, есть подобные примеры или я только что такое выдумал?