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

[Munin]

А что, в обратную сторону нельзя расковырять: взять простое число, и найти переменные полинома, которым оно соответствует?

[Rak so dna]

Munin в сообщении #1095621 писал(а):

А что, в обратную сторону нельзя расковырять: взять простое число, и найти переменные полинома, которым оно соответствует?

Я пробовал. Например для простого числа $2$ мы получим $k=0$ и систему из $14$-ти уравнений, максимальной степени $12$. В котором, очень вероятно, $u>10^{20}$. Без тупого перебора хотя бы по $8$ переменным тут врятли обойдешься, а когда повылазили такие числа... Лично у меня весь энтузиазм пропал...

[Someone]

Почитайте тему "Что значит найти наибольшее простое число?". Там и ссылки на статьи есть. Из которых Вы узнаете, что $10^{20}$ — это мелочи, не заслуживающие упоминания.

[Rak so dna]

Someone в сообщении #1095698 писал(а):

Почитайте тему "Что значит найти наибольшее простое число?". Там и ссылки на статьи есть. Из которых Вы узнаете, что $10^{20}$ — это мелочи, не заслуживающие упоминания.

Я всего лишь хотел сказать, что тупой перебор, или попытка угадать решение - совершенно бесполезны (даже для самого маленького простого числа). Но все равно, вот это $r\simeq{10^{10^{52}}}$ очень впечатляет

[Someone]

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

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

Встречаются ситуации, когда объекты с некоторым свойством составляют, в некотором смысле, подавляющее большинство, но предъявление какого-нибудь примера составляет существенную проблему.
Приведу пример из топологии. Речь будет идти исключительно о метризуемых компактах, поэтому метризуемость далее упоминаться не будет.
Гильбертовым кирпичом называется подмножество пространства $l_2$ последовательностей $\bar x=(x_1,x_2,\ldots,x_n,\ldots)$, удовлетворяющих условию $\lvert x_k\rvert\leqslant\frac 1k$ для всех натуральных $k$. Его также можно представлять себе как произведение счётного множества отрезков. Будем обозначать его буквой $H$.
Известно, что каждый компакт гомеоморфен какому-нибудь замкнутому подмножеству гильбертова кирпича (не единственному). Наоборот, каждое замкнутое подмножество гильбертова кирпича является компактом.
Множество непустых замкнутых подмножеств гильбертова кирпича называется экспонентой гильбертова кирпича, снабжается метрикой Хаусдорфа и обозначается далее $\exp H$. Экспонента является компактом.
Для конечномерных компактов верно следующее утверждение: если компакт имеет (конечную) размерность $n>0$, то он содержит подкомпакты всех размерностей, меньших $n$.
Интересно, что для бесконечномерных компактов это утверждение неверно: существует бесконечномерный компакт, в котором каждое непустое замкнутое подмножество либо бесконечномерно, либо нульмерно. Такие компакты называются наследственно бесконечномерными.

Неожиданностью является то, что совокупность замкнутых подмножеств гильбертова кирпича, не являющихся наследственно бесконечномерными, образует в $\exp H$ множество первой категории (объединение счётного семейства нигде не плотных подмножеств), в то время как наследственно бесконечномерные образуют множество второй категории. Построение примера наследственно бесконечномерного компакта было сложной задачей: её решение потребовало 40 лет (с 1925 по 1965).

[svv]

Спасибо, не думал, что такая ситуация возможна.

[Anton_Peplov]

Someone в сообщении #1095783 писал(а):

Встречаются ситуации, когда объекты с некоторым свойством составляют, в некотором смысле, подавляющее большинство, но предъявление какого-нибудь примера составляет существенную проблему.

Например, невычислимые действительные числа. Вычислимых всего счетное множество, в то время как весь остальной континуум - невычислимые. Но предъявить невычислимое число... Нет, это, конечно, можно, константа Хайтина тому пример. Но уж очень для этого нужно изогнуться.

[Someone]

(Anton_Peplov)

Да, я думал об этом примере, но топология мне ближе.

[vicvolf]

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

Так что ж вы его не указываете? Или можно лишь привести доказательство его существования?

По теореме Вильсона $p$ простое, если $(p-1)!+1$ делится на $p$. Поэтому множество простых чисел является проекцией множества решений системы уравнений: $p=f+1,q=f!,ap-bq=1$, которое диофантово в силу диофантовости $q=f!$.

[g______d]

А диофантовость $q=f!$ так уж очевидна, да?

[vicvolf]

g______d в сообщении #1095978 писал(а):

А диофантовость $q=f!$ так уж очевидна, да?

Пусть переменная $p$ принимает целые значения в области $p>1$. Тогда переменные $f,q$ принимают натуральные значения и функция $q-f!$ - целочисленная.

[g______d]

Определение диофантовости напомните, пожалуйста.

[Anton_Peplov]

g______d в сообщении #1096165 писал(а):

Определение диофантовости напомните, пожалуйста.

Я тут спрашивал, но ответа не дождался.

[g______d]

Anton_Peplov в сообщении #1096174 писал(а):

но ответа не дождался.

Там же ответили... А если по поводу книжки, то, я думаю, в любой книжке с формулировкой теоремы Матиясевича будет и определение класса множеств, про которые идёт речь. Хотя и так понятно, что речь об алгебраических диофантовых множествах.

[vicvolf]

g______d в сообщении #1096186 писал(а):

речь об алгебраических диофантовых множествах.