Александров (ред.) - Проблемы Гильберта (сборник статей) - 2000 (947342), страница 30
Текст из файла (страница 30)
И., Общий закон взавмиости к новое обосясвавве теорвиполей классов, ИАН СССР, сер. матам. 18 (1954), 335 — 378. К ДЕСЯТОИ ПРОБЛЕМЕ ГИЛЬБЕРТА Ю. ХХ. Хмелееезий Десятая проблема Гильберта относится к одной из самых древних областей математики — решению алгебраических уравнений с целымн коэффициентами в целых числах.
Такие уравнения называют диофантовыми в память греческого математика Диофанта, рассмотревшего некоторые иэ них. Гнльберт следующим образом формулирует эту проблему. «10. Решение проблемы разрешимости для произвольного диофантова уравнения. Пусть дано произвольное диофантово уравнение с произвольным числом неиввестных и с целыми рациональными коэффициентами; требуется указать общий метод, следуя которому можно было бы в конечное число шагов узнать, имеет данное уравнение решение в целых рациональных числах или нет».
Фундаментальный труд 1. Е. 0 1с Ь з о и, «Н[з1огу о1 1Ье ТЬеогу о11]ишЬегз» т. 2, «Диофантовы уравнения», дает представление о том, какой интерес испытывали математики всех времен к решению диофантовых уравнений. Целочисленными решениями алгебраических уравнений интересовались еще античные математики; например, в связи с теоремой Пифагора они рассматривали уравнение зз + рз = х', Евклид (1П в. до н.
з.) приводит формулы, позволяющие найти все целочисленные решения этого уравнения. Отдельные виды уравнений и систем уравнений второй степени с двумя неизвестными рассматривал Диофант (П1 в. н. э.). Например, он рассмотрел уравнение ахз + Ьл+ с = р' и решил его для 141 некоторых частных случаев. Работы Диофанта впоследствии легли в основу работ Ферма, Эйлера и других математиков по теории чисел ').
И в эпоху развитии аналиэа диофаитовы уравнения привлекали внимание выдающихся ученых. Ферма, Эйлер, Лагранж, Гаусс внесли свой вклад в теорию диофантовых уравнений. В частности, Ферма выдвинул знаменитую гипотезу о том, что уравнение я" + у" = г" при и ~ 2 не имеет целочисленных решений. Наибольшего успеха добился Лагранж. Благодаря трудам Ферма, Валлиса, Эйлера и других Лагранжу (1768 г.) удалось полностью исследовать вопрос об отыскании целочисленных решений любого уравнения второй степени с двумя неизвестными.
Поэднее другое изложение результата Лагранжа дал Гаусс (Ц. В Х1Х в. различные ученые предпринимали попытки решения днофантовых уравнений степени выше второй, в частности, в свяэи с проблемой Ферма. Однако сколько- нибудь общих результатов здесь получено не было; рассматривались лишь отдельные виды уравнений, для решения которых придумывался какой-либо специальный прием.
По-видимому, и сам Гнльберт пытался найти подходы к решению диофантовых уравнений. Таким образом, несмотря на усилия многих поколений математиков, проблема решения диофантовых уравнений оставалась открытой. Вместе с тем было ясно, что продвижение в этой области неизбежно связано с соэданием глубоких теорий, значение которых, по-внднмому, не ограничивалось бы только диофантовыми уравнениями (классический пример: исследования Куммера по проблеме Ферма, приведшие его к важному понятию идеала).
В этом, возможно, одна ив причин, побудивших Гильберта включить проблему диофантовых уравнений в число наиболее вюкных проблем, которые Х1Х в. оставил двадцатому. Таким обравом, если рассматривать вамысел Гильберта достаточно широко, то десятой проблемой Гнльберт нацеливал математиков на иселедсвание диофантовых уравнений. г) Пе атому наведу ем. работы И. Г. Б в ш м а к е в о й: Дне факт н Ферма (к истерии метода касательных к экстремумов), ИМИ, выл 17, «Наука», 1966, 185 — 204 н Ю)ерЬ«в«в «С Увгювы, Ивч. )г)в«е)гв ве). Х!Х, 1966, 289-306.
142 Что касается формулировки этой проблемы, данной самим Гнльбертом, то здесь надо скаэать следующее. Гильберт требовал отыскания «общего метода» для решения диофантовых уравнений. По-видимому, он считал, что такой метод рано нлн по»дно.будет найден; во всяком случае, в принципе такой метод существует, надо только его найти. Вопрос о том, что такого метода вообще не существует, во времена Гнльберта вряд ли мог возникнуть: точное понятие алгорнфма появилось в математике позднее. Теперь точное понятие алгорифма является предметом научения новой области математики — теории алгорнфмов.
Вместе с уточнением понятия алгорифма появилась принципиальная возможность рассматривать вопрос о несуществовании алгорнфмов, обладающих определенными свойствами. В настоящее время развиваются методы докавательства теорем о невозможности тех нлн иных алгорифмов. Имеются примеры массовых математических проблем, для которых невозможны алгорифмы, искомые в этих проблемах. «Общий метод», о котором говорит Гиль- берт, мы теперь понимаем как алгорифм. Если подойти теперь к проблеме Гильберта с алгорнфмической точки зрения, то ее можно сформулировать следующвм обраэом: «Существует лн алгорнфм, который по данному многочлену Р(л,,..., л„) с целыми коэффициентами распознавал бы, имеет уравнение Р = О решения в целых числах нлн не нмеетв.
Априори вовможно как положительное (построение алгорифма), так н отрицательное (докаэательство невозможности алгорифма) решение проблемы Гилъберта. Во времена Гильберта, как мы уже отмечали, точного понятия алгорифма не существовало, и речь могла идти только о положительном решении проблемы. Вскоре после того, как Гнльберт сформулировал свою проблему, появилась одна из самых аамечательных работ в области диофантова анализа (так называют иногда исследование диофантовых уравнений) — работа А. Т у э (21.
Используя полученную им оценку для приближения алгебраических чисел рациональными, Туэ докавал, что уравнение 1(л, у) = с, где с — целое число, / — неприводвмая форма ') степени ~ 3, не может иметь бесконечно г) Фермей мввывавтев зжогечлвк, у которого вев елагввммв вмвют едвквковув етвнввь. Нвкрвведкмый мнсгечлвн — вте мнегевлвк, который мв рвввагввтея кв миожитвли е целыми ке»ффкцавктамк. много целочисленных решений. Однако ни метод Туэ, ни более поздние методы не давали верхних оценок для границ, в которых должны лежать решения. (Противоречив получаешься из-за того, что решений бесконечно много, но не из-за того, что решения очень болыпне.) В силу последнего обстоятельства нэ теоремы Туэ не вытекает алгорифм для решения уравнения ~(х,у) = с.
К настоящему времеви алгорифм неизвестен даже для случая, когда степень многочлена ~ равна трем, хотя еще в 1922 г. Делоне доказал (13), стр. 302), что диофантово уравнение ахл+ Ьхлу + сху'+ Ыу' = 1 имеет не более пяти решений, и предложил некоторый способ распознавания, имеет ли уравнение хотя бы одно решение. Однако доказательства того, что этот способ дает ответ во всех случаях, до сих пор не было.
Недавно Бейкер (РЫ1. Тгалз. Боу. Ма(Ь. 8ос., ?.оптов,,) и)у — Апбиз$ 1968) нашел верхнюю границу величины решений уравнения / (х, у) = с, где с — целое число, ~ — нвпризодимая форма степени ь 3. Тем самым для уравнений указанного типа построен разрешающий алгорифм. В 1938 г. Сколом предложил довольно общий метод исследования диофактовых уравнений вида Р(х,,... ..., х„) = О, где Р— непрнводимый многочлен, разлагающийся в некотором расширении поля рациональных чисел в произведение т ) я линейных множителей (непол-ная разложимая форма) к удовлетворяющий некоторым дополнительным условиям.
Метод Сколема изложен в (4]. До появления- теории -алгорифмов исследования по проблеме Гильберта велись, если так можно выразиться, в одном направлении: найти алгорифм, которого требовал Гнльберт, хотя бы для некоторых частных классов диофантовых уравнений.
Однако уже проблема решения уравнений с двумя нензвестнымк, несмотря на классический результат Туэ, не поддавалась никаким усилиям. (Для уравнений с одним неизвестным разрешающий алгорифм весьма просто вытекает из теоремы Безу.) В середине 30-х годов (1935, 1936 гг.) в математической логике установилось точное понятие алгорифма и были получены первые примеры неразрешимых алгорнфмических проблем, сначала в области математической логики (Черч, Тьюринг, 1936 г.), а позднее и алгебры (Пост, А. А. Марков 15), 1947 г). В 1952 г. П. С.
Новиковым была доказана неразрешимость важной $44 алгорифмической проблемы теории групп — так называемой проблемы тождества слов. Зги примеры, с одной стороны, и трудности, связанные с решением диофантовых уравнений, с другой стороны, вызвали предположение, что алгорифма, которого требовал Гильберт, не существует. Зто предположение вместе с развитием самой теории алгорифмов стимулировало реальные попытки дать отрицательное решение десятой проблемы Гильберта. Начиная с 1953 г., появилась серия работ американских математиков 161 — 1101, авторам которых удалось доказать неразрешимость некоторых алгорифмнческнх проблем из области арифметики, в частности проблемы разрешимости показательно-диофантовых уравнений, близкой по формулировке к проблеме Гильберта.
Опишем в общих чертах метод, который применяется в этих исследованиях. Заметим сначала, что из теоремы Лагранжа о представлении любого натурального числа суммой четырех квадратов целых чисел вытекает, что если есть алгорифм для отыскания целочисленных решений днофантовых уравнений, то он есть и для отыскания натуральных решений, и наоборот. В силу этого при рассмотрении проблемы Гильбврта достаточно интересоваться решением диофантовых уравнений в натуральных числах.
Будем рассматривать множества натуральных чисел. Множество М называется разрешимым, если существует алгорифм, распознающий по любому натуральному числу, принадлежит это число множеству М или не принадлежит. Множество М называется перечислимым, если существует вычислимая арифметическая функция, множество значений которой совпадает с М. В теории алгорифмов доказывается, что можно построить перечислимое множество, не являющееся разрешимым.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
