Canadophobia

In 1955 Walter Homburger, Glenn Gould's manager, wrote to the Canadian Department of External Affairs a letter suggesting to organize a tour to Soviet Union for Glenn Gould, as a kind of "reciprocating" gesture to the then-recent tours by Emil Gilels and David Oistrakh to the USA. Some official at the department who apparently had no clue who Glenn Gould was answered: "The idea of Canadian musicians touring USSR has some merit, especially if only the very best of them go. Of course, they cannot stack up against Gilels and Oistrakh, but if they put up a respectable performance and perform a few pieces of Canadian music, this could have some value. I don't know if Glenn Gould belongs to this group." And suggested Homburger to contact the Soviet Embassy.

Hilbert's 10th Problem Reloaded

Сходил вчера на лекцию Бьорна Пунена про 10ю проблему Гильберта и ее обобщения. Уровень был для undergraduates, так что я вроде все понял. Сначала он "объяснил" теорему Davis-Putnam-Roberts-Матиясевича из которой следует, что ответ на 10ю проблему Гильберта отрицательный. Т.е. почему не может быть алгоритма, который решает, когда полиномиальное уравнение с целыми коэффициентами имеет целое решение. Сначала Пунен дал два определения: диофантова подмножества и перечислимого подмножества. Диофантово подмножество Х множества целых чисел Z - это такое множество, которое получается проекцией множества значений какого нибудь полинома с целыми коэффициентами в целых точках на одну из координатных осей. Перечислимое подмножество - это подмножество, которое может "выдать" машина Тьюринга следуя какой нибудь программе. Очевидно, что любое диофантово подмножество перечислимо. DPRM доказали, что обратное тоже верно: любое перечислимое подмножество диофантово. С другой стороны, давно известно, что бывают такие перечислимые множества, что не существует алгоритма, который ответит, приндалежит ли данное число этому множеству или нет. (Это следует, например, из отрицательного решения halting problem). Из этих двух результатов и вытекает отрицательный ответ на 10ю проблему Гильберта.

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

Наивная интуиция, вроде, говорит нам, что случай Q не должен существенно отличаться от случая Z. Т.е. хочется свести задачу к уже известной теореме DPRM. Но для этого надо доказать, что множество Z "диофантово над Q". Т.е. что существует полином с целыми коэффициентами, проекция значений которого в рациональных точках на одну из осей это в точности множество Z. А это, судя по всему, не так, хотя никто этого пока не доказал. На самом деле, есть даже более общая гипотеза Мазура, которая говорит,. что замыкание любого подмножества вещественных чисел, диофантова над Q, имеет конечное число компонент связности. Конечно, как это доказать тоже никто не знает. 

Пунен говорил немного и про другие интересные кольца (рациональные функции, числовые поля), но что именно, я забыл.