Интервью с американским математиком Рональдом Грэхемом

21

ИНТЕРВЫЮ С ПРОФЕССОРOM РОНАЛЬДОМ ГРЭХЕМОМ

— Профессор Грэхем, когда и каким образом вы впервые заинтересовались математикой? Что повлияло на ваш выбор: семья, учитель, книги, современная?

— Сильный интерес к математике я впервые почувствовал в начальной школе, в третьем или четвертом классе. Особенно хорошо помню, как, позакомившись с алгоритмом извлечения квадратных корней — вы знаете этот старый интерционный алгоритм,— я заинтересовался,возможно ли сделать то же самое для кубических корней и для более высоких степеней. И я нашел аналогичный способ решения. Меня поддержал учитель, хорошо относившийся к моим увлечениям.

Позднее, когда я учился в младших классах средней школы, мне помогали два других учитель. Видя, что я могу решить любую задачу по алгебре, учитель мне как-то сказал: «Вот задача, которую ты решить не сможешь».
В задаче решила о скорости роста популяции мышей, зависящей от их численности, т. е. мне пришлось бы иметь дело с дифференциальным уравнением. Что же, учитель оказался прав — задачу решить я не смог. Тогда он дал мне учебник анализа и сказаал: «Если хочешь узнать решение — прочити эту книгу». Я так и сделал. Тогда математика меня и захватила.

Do этого я увлекался звездами, собирался стать астрономом. Только позднее я узнал, что наблюдание за звездами — это еще далеко не вся астрономия. Но эта наука интересует меня по-прежнему. Кроме диплома математика у меня есть еще один — по физике.

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

— Как вы стали математиком-исследовательем?

— Насколько я помню, в средней школе и на младших курсах университета такой цели я для себя не ставил — мне просто было интересно заниматься математикой. Потом, в 1950 году, я начал подготовку по специальной программе, дававшей право поступления в университете еще до окончания средней школы. Чтобы заниматься по этой программе, необходимо сдать определенные тестовые экзамены. По математике я оказался лучшим в Соединенных Штатах. В 15 лет я поступил в Чикагский университет, в котором знаменитый професитель Р. М. Хатчинс ввел тогда

23

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

Область математики, в котором я работаю — комбинаторика. Долгое время ее считали тихой заводу топологии. Лет dvенадцать тому назад французский математик Ж. Дьедонне назвал комбинаторку «математикой на завтрак». Думаю, он имел в виду, что это лишь преддверие главного этапа ее развития. Есть и другая крайность: иной раз, говоря о комбинаторике, ее называют «комбинаторной теории». Как теория, она еще не сравнима с алгебраической топологией или дифференциальной геометрией, хотя в них многие ключевые результаты и носят комбинаторный характер.

Конкретные задачи можно рассматривать как ступени создания методики или теории: если методика хорошо для решения данной конкретной задачи, значит исследование идет по верному пути. Здесь возникнет и более глубокий вопрос: создана ли математика искусственного или она существенно вечно? Большинство математков, которые я знаю, утверены, что математика в каком-то смысле существенно реагирует ее для людей. Но тут можно просить: как же в таком случае быть с музыкой, с Бетховеном?

Открыл ли он фортепианную сонату, посвященную Вальдштейну*) или создал ее? Ответ, наверное, можно формулировать следующим образом: принципиы, которые легли в основу сонаты, существовали, но их непосредственное применение, сами notы — все уже сотрудено композитором. То же относится и к математике: можно

*) Соната № 21 До.maxор «Аврора». (Примеч. перев.)

24

но придумать конкретиное доказательство, но не его основополагающие принципы. Теория чисел, теорема о разложении на простые множители остатуса без изменения и на другой планете. В других области, например в квантовой механике, наблюдаемые может изменить или создать наблюдаемое, хотя это и кажется несколько танистенным.

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

— Один из наших читателей прислада нам следующую задачу, связанную с гипотезой Эрдша: $n$ бесконечных арифметических прогрессий покрывают первые $2^n$ натуральных чисел; доказать, что они покрывают весь натуральный ряд. Что вы можете сказать про эту задачу?

— Это утверждение, или его вариант с заменой $2^{2n}$ на $2n!$, сравнительно несколько доказать по индукции. Но дело в том, что сама гипотеза Эрдша (в котором вместо $2^{2n}$ фигурирует $2^n$ — и эта оценка уже точная!) доказана Криттенденом и Ван ден Эйденом (1969 г.). Доказательство трудное, о нем коротко не расскажешь.

При решении подобных задач очень важен первый этап — убедиться, справедлива ли гипотеза: вы то пытаетесь строить контрипмеры, то — доказываете какие-то частные случаи, более слабые утверждения или следствия гипотезы; так проискодит, пока вы окончательно не обретете уверенность в справедливости того, что доказываете.

— Задание на арифметические прогрессии связаны с именем Ван-дер-Вардена. Имеются ли хорошо задчи по этой тематике?

— Вот интересная задача, связанная с теоремой Ван-дер-Вардена: Обозначим, в его числе, через $W(k)$ наименьшее натуральное число такое, что при любом разбиении чисел от 1 до $W(k)$ на два класса, хотя в одном из них найдется $k$-членная арифметическая прогрессия. (Ван-дер-Варден доказал, что $W(k)$ существует при любом $k$.) Легко видеть, что $W(2)=3$, $W(3)=9$; известно еще, что $W(4)=35$, $W(5)=178$, но уже $W(6)$ не найдено даже с помощью компьютера. Я предложаю гипотезу, что $W(k)$ растет не быстрее, чем «башня» из $k$ двое $2^{2n}$. Но есть основания сомневаться даже в этой оценке: есть некоторые похожие комбинаторы задачи, связанные с именем Рамсея, где встречаются функции, растущие еще быстрее. Вы знаете, есть такая широко известная на Западе «Книга рекордов Гинесса». Так вот, там есть «самое большое число, реализно использованное в математическом доказательстве». Оно было придумано мной в связи с одной задачей теории Рамсея.

— Одазадача такого «рамсевского» типа, который также занимается Эрдшем, недавно обсуждалась в «Кванте»: из какого наименьшего числа $S(k)$ точек на плоскости можно заведом выбрать $k$ точек, лежащих в вершинах выпуклого $k$-угольника? Есть гипотеза Секерша, что $S(k)=2^{k-2}+1$. Видимо, надежда на ее доказательство в общем случае пока не прибавилось?

— Да, найти значение $S(k)$ или даже дать хорошее его оценки — видимо, очень трудная задача. Задачу можно выражать: доказать, что при большом числе точек $N$ среди всех $k$-угольников с вершинами в этих $N$ точках должна выпуклых составлять не менее $C_k$, где $C_k>0$ зависит только от $k$, и пытается оценить $C_k$. А вот еще вариант этой задачи: найти из какого числа $n=f(k)$ точек всегда можно выбрать «пустой» выпуклый $k$-угольник (т. е. такой, внутри которого больше нет ни одной из этих $n$ точек). Оказывается, такое $f(k)$ существует для $k=3$, 4 и 5, а для $k\geq 7$ его просто не существует. Для $k=6$ — никакого ничего не знает.

А вообщее эту задачу Эрдшем называет «задачей со счастливым комом»: дело в том, что его вместе с Секершом увлеклась его спиранта Эстер Клейн, и все это кончилось тем… что спиранта стала женой Секерша.

— Могли бы высказать что-нибудь об истоках теории Рамсея, приведенные примеры теории Ramсея, привести примера теории Ramсея такое утверждение:

— В качестве почты шуточного, но типичного примера Ramсеевского теории приведу такое утверждение:

25

среди любых б людей всегда существует 3 попарно знакомых или 3 попарно незнакомых.*) Такие теоремы возникали и до Рамсея. Например, есть такая известная теорема И. Шура, доказательство которого, пожалуй, по плену наиболее подготовленным читателем «Кванта»; при любой раскраске чисел натурального ряда в два цета существует monoxроматическое решение (x, y, z) диффантово уравнения x+y=z (т. е. решение, составленное из чисел x, y, z одного цета). Занимаясь более тщательным изучением истории, я пришел к выводу, что впервые теорема рамеевского типа появлялась в трудах Д. Гильберта в 1892 году.

— Если уж говорить о предыстории теории Рамсея, не какется ли вам, что следует вести не от результатов Шура, а скорее от «причина ящиков» Дирихле?

— Ну, это уж слишком далекая история, это времена Адама и Евы!

— Есть задачи, которые нежиданно завоевывают популярность. Например, вы, конечно, слышали о такой: начав с некоторого натурального x₀, положим x₀+1=x₀/2, если x₀ четно, и x₀+1=(3x₀+1)/2, если x₀ — нечетно; всегда ли в этой последовательности встретися 1 (после чего она зацикливается)? Недавно школьники принесли нам лист с огромными машинными экспериментами, показывающими, как непредсказуемо поведение этой последовательности. Каждыйли вам подобные задачи интересными?

— О таких задач — просто формулируемых, но порой очень сложных, — трудно заранее сказать, есть ли в них какая-либо математическая идея, сложны они или нет, стоит ли на них траить больше числа. Но среди задач про «интерации» есть постине uidительные. Например, вы знаете, как обычно могут вести себя последовательности, задаваемые простыми формулиами типа x₀+1=x₀(a−x₀). Возьмем такую, более сложную, формулу: x₀+2=(1+x₀+1)/x₀. Оказывается (если в ней не встречается 0 или —1), она всегда периодна 5. А x₀+3=(1+x₀+1)+x₀²)/x₀ — с периодом 8. Есть ли еще подобные примеры? (Кажется, для линейных выражений в числи-

*) См. статью М. Гарднера в этом номере. (Примеч. ред.)

теле и знаменатель их больше нет, но из многочленов более высокой степени их можно сконструировать.)

Еще пример: положим

xₙ+1=[√2xₙ(xₙ+1)], x₁=1,

где […] — «целая часть»; тогда первые члены будут 1, 2, 3, 4, 6, 9, 13. Ясно, что xₙ растет примерно как √2n, так что xₙ+2 примерно вдвое больше xₙ. Оказывется, dₙ=x₂n+1−2x₂n+1 будет 0 или 1, и если записать их по порядку, то мы получим 1,011010100 … — в точности двойную запись √2! Для √3, например, ничего подобного я уже не знаю.

Последний пример: пусть ψ₁=2, ψₙ+1=ψₙ−1/ψₙ. Будет ли ψₙ неограниченным? Ответ почти наверняка положительный, но никто это не умеет доказать.

— Считайте ли вы, что вычислительная наука, информаτικά, поглотит математике?

— Это довольно трудный вопрос. Большинство наиболее талантливых ученых в США пользовятся компьютерами с самого начала своей научной деятельности. Если их интересуют графы или числа, то на компьютере можно проводить самые разнообразные эксперименты. Играя в компьютерные игры, школьники в США начинают пользоваться компьютерами в возрасте 6—7 лет. Потом круг математических занятий можно расширить с помощью тех же компьютеров.

Ситуация на рынке рабочей силы такая, что спрос на специализитов по вычислительных методам огромен. Поэтому многое талантливое молодое лицо рассматривает компьютеры в контексте своей будущей профессии.

Как молодые, так и уже признанные математики приходит к выводу, что вычислительный эксперимент является источником важных и интересных задач. Например, на Международном конкурсе в Беркли результаты трех из шестнадцатей пленарных докладов были построены на использовании компьютеров. Работа многохотных математиков связана с «гиперкубическим машинами». В них входит около 64 000 процессов, соединен-