Компьютер проверил доказательство гипотезы Кеплера

[Amicus Plato]

Машина подтвердила правильность доказательства гипотезы Кеплера математиком Томасом Хейлзом (Thomas Hales) из Питтсбургского университета в США. Как считают специалисты, это демонстрирует широкие возможности компьютеров для проведения трудоемких вычислительных доказательств, позволяя человеку сконцентрироваться на концептуальных сторонах проверки, сообщается на сайте New Scientist.

Свою гипотезу Кеплер опубликовал еще в 1611 году в своем знаменитом исследовании «О шестиугольных снежинках». В нем он предположил, что наиболее плотная упаковка шаров одинаковых размеров (то есть такая, когда объем пространства между шарами минимален при заданном количестве шаров) достигается при их пирамидальном упорядочивании по отношению друг к другу. Постановке задачи ученый обязан военному вопросу об оптимальном расположении пушечных ядер на палубе корабля.
Читать полностью на Ленте.ру

Немножко сведений из Википедии

Гипотеза Кеплера Гипотеза Кеплера гласит: Среди всех упаковок шаров равного размера в трёхмерном пространстве наибольшую среднюю плотность имеет гранецентрированная кубическая упаковка и упаковки, равные ей по плотности. Плотность гранецентрированной кубической упаковки: `{V_{spheres}}/{V_{space}} = {pi}/{sqrt{18}} simeq 0,74048`, где `V_{spheres}` — суммарный объём шаров, `V_{space}` — объём пространства, занимаемого шарами. Отношение берётся в пределе бесконечного числа шаров. Математически доказать гипотезу не удавалось на протяжении 400 лет. Сообщение о компьютерном доказательстве гипотезы Кеплера появилось в 1998 году в работе математика Томаса Хейлса.

Кубическая гранецентрированная упаковка

---

На мой взгляд, очень подробно и занимательно гипотезу Кеплера описывает Саймон Сингх в книге "Великая теорема Ферма".
Приведу отрывок из нее.

*****
Из всех проблем, способных с большей или меньшей вероятностью занять место Великой теоремы Ферма, наибольшие шансы имеет проблема плотнейшей упаковки шаров Кеплера. В 1609 году немецкий ученый Иоганн Кеплер доказал, что планеты движутся не по круговым, а по эллиптическим орбитам. Это открытие совершило переворот в астрономии и позднее помогло Исааку Ньютону найти закон всемирного тяготения. Математическое наследие Кеплера не столь грандиозно по своим масштабам, как наследие Ньютона, но не менее глубоко. Проблему плотнейшей упаковки шаров можно сформулировать как задачу о том, как наиболее экономно сложить из апельсинов пирамиду.
Проблема родилась в 1611 году, когда Кеплер написал небольшое сочинение «О шестиугольных снежинках», предназначенное в дар его покровителю Иоганну Вакгеру фон Вакенфельсу. В этом сочинении Кеплер успешно объяснил, почему снежинки всегда имеют шестиугольную форму, высказав предположение, что рост каждой снежинки начинается с обладающего гексагональной симметрией зародыша, который, падая в атмосфере, увеличивается в размерах. Непрерывно изменяющиеся ветер, температура и влажность позволяют каждой снежинке сохранять индивидуальность, а малые размеры зародыша приводят к тому, что условия, от которых зависит его рост, остаются одинаковыми со всех шести сторон, тем самым способствуя сохранению симметрии. В этом, на первый взгляд легкомысленном, сочинении проявился присущий Кеплеру замечательный талант извлекать глубокие и далеко идущие результаты из простейших наблюдений. Впоследствии Кеплер стал одним из основоположников кристаллографии.
Интерес Кеплера к расположению и самоорганизации частиц вещества привел его к обсуждению другого вопроса — о плотнейшей упаковке частиц, при которой они занимают наименьший объем. Если предположить, что частицы имеют форму шаров, то ясно, что как бы они ни располагались в пространстве, между ними неизбежно останутся зазоры, и вопрос состоит в том, чтобы объем зазоров свести к минимуму. Кеплер рассмотрел несколько различных вариантов расположения шаров и для каждого варианта вычислил коэффициент заполнения пространства.
Один из первых вариантов расположения шаров, рассмотренных Кеплером, сейчас принято называть гранецентрированной кубической решеткой. Ее можно построить, выложив сначала нижний слой шаров так, чтобы каждый шар был окружен шестью другими шарами. Второй слой образуют шары, уложенные в «ямки» поверх первого слоя, как показано на рис. 24. По существу, второй слой повторяет первый, но только слегка смещен относительно первого, чтобы шары второго слоя расположились в ямках первого слоя. Именно так обычно укладывают апельсины торговцы фруктами. Коэффициент заполнения пространства такой укладки составляет 74 %. Это означает, что при укладке апельсинов в картонный ящик гранецентрированная стратегия позволяет заполнить 74 % объема ящика апельсинами.

Рис. 24. В гранецентрированной кубической упаковке шаров каждый слой состоит из сфер уложенных так, что каждая из них окружены шестью другими сферами. Поверх каждого слоя горизонтально накладывается следующий слой так, что любой из его шаров располагается не на шаре из предыдущего слоя, а в ямке. Частной разновидностью гранецентрированной кубической упаковки служат пирамиды из апельсинов в витринах овощных магазинов

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

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

Еще один вариант расположения шаров — гексагональная решетка — аналогичен гранецентрированной кубической решетке, поскольку каждый слой состоит из шаров, окруженных шестью другими шарами, но следующий слой не сдвинут относительно предыдущего, а расположен прямо поверх него так, что каждый шар опирается на самую верхнюю точку шара, расположенного под ним, как показано на рис. 26. У гексагональной решетки коэффициент заполнения пространства составляет всего лишь 60 %.

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

Кеплер исследовал множество различных конфигураций и пришел к заключению, что в сочинение «О шестиугольных снежинках» стоит включить только одну, а именно ту, которая в последствие получила название гранецентрированной кубической решетки, ибо у нее «упаковка оказывается плотнейшей из возможных». Утверждение Кеплера можно считать вполне разумным, так как коэффициент заполнения пространства для гранецентрированной кубической решетки наибольший из всех тех, которые были им обнаружены. Однако это не исключает возможность существования какого-то другого расположения шаров, с еще большим коэффициентом заполнения пространства, которое Кеплер попросту проглядел.
Проблема плотнейшей упаковки шаров требует от математиков доказательства того, что гранецентрированная кубическая решетка представляет собой наиболее эффективный вариант упаковки шаров. Эта проблема на полвека старше Великой теоремы Ферма и, как теперь оказалось, еще более неприступна.
Как и в случае Великой теоремы Ферма, решение проблемы Кеплера сводится к доказательству, охватывающему бесконечное множество возможных вариантов упаковки. Гипотеза Кеплера утверждает, что среди бесконечно многих вариантов расположения шаров нет ни одного такого, у которого коэффициент заполнения пространства был бы больше, чем у гранецентрированной кубической решетки. Математикам предстоит доказать, что это невозможно не только для регулярного, но и для случайного, хаотического, варианта расположения шаров.
За последние 380 лет никому не удалось доказать, что гранецентрированная кубическая решетка действительно служит оптимальной стратегией упаковки. Но никто пока не открыл более эффективного метода упаковки. Отсутствие контрпримера означает, что для всех практических целей утверждение Кеплера применимо, но в абсолютном мире математики абсолютно необходимо строгое доказательство. Британский специалист по упаковке шаров К. А. Роджерс говорит, что «большинство математиков в правильность гипотезы Кеплера верят, а все физики в ее правильности твердо убеждены, так как это знают».
Несмотря на отсутствие полного доказательства, за прошедшие со времен Кеплера столетия было пройдено несколько вех на пути к решению. В 1892 году скандинавский математик Аксель Туэ нашел доказательство для двумерного аналога проблемы Кеплера, т. е. обнаружил наиболее эффективное расположение шаров в одном-единственном слое, или, иначе говоря, укладки апельсинов не в ящике, а на подносе. Решением оказалось гексагональное расположение шаров. Впоследствие Тот, Сегрэ и Малер пришли к тому же заключению, но ни один из использованных в двумерном случае методов не применим к исходной трехмерной проблеме Кеплера.
В наше время некоторые математики попытались подойти к проблеме Кеплера с совершенно другой стороны, а именно — вычислить верхний предел коэффициента заполнения пространства. В 1958 году К. А. Роджерс вычислил его верхний предел, который оказался равным 77,97 %. Это означает, что невозможно расположить шары так, чтобы коэффициент заполнения пространства был выше 77,97 %. Такое значение коэффициента заполнения пространства не намного больше, чем его значение для гранецентрированной кубической решетки, равное 74,04 %. Следовательно, если у какого-нибудь расположения шаров коэффициент заполнения пространства и оказался бы выше, чем у гранецентрированной кубической решетки, то превышение составило бы всего лишь несколько процентов. Оставалось узкое окно в 3,93 %, в которое могло бы «втиснуться» какое-то дикое расположение шаров, которое стало бы контрпримером, опровергающим гипотезу Кеплера. После Роджерса другие математики попытались полностью закрыть образовавшееся окно, понизив верхний предел до 74,04 %. Если бы эти попытки оказались удачными, то для других расположений не осталось бы места, они не могли бы иметь более высокий коэффициент заполнения пространства, чем гранецентрированная кубическая решетка, и тем самым гипотеза Кеплера оказалась бы «оправданной ввиду неявки подозреваемой». К сожалению, снижение верхнего предела оказалось процессом медленным и трудным, и к 1988 году верхний предел удалось уменьшить лишь до 77,84 %, что лишь незначительно улучшает оценку Роджерса.
Несмотря на столь медленный прогресс, проблема плотнейшей упаковки шаров летом 1990 года неожиданно попала в заголовки на первых полосах газет. Ву-И Хзянь из Калифорнийского университета в Беркли опубликовал результат, который, по его утверждению, был доказательством гипотезы Кеплера. Первоначально реакция математического сообщества была оптимистической, но когда работа Ву-И Хзяня подверглась тщательному рецензированию, в ней был обнаружен ряд ошибок, и доказательство рухнуло.
Как и в случае с доказательством Уайлса, Хзянь через год представил пересмотренный вариант доказательства, в котором, как он утверждал, ему удалось обойти те проблемы, которые были обнаружены в первоначальном варианте рукописи. К сожалению для Хзяня, его критики продолжали считать, что в его логике остаются пробелы. В письме к Хзяню математик Томас Хейлис попытался объяснить свои сомнения: «Одно предположение, сделанное в Вашей второй статье, представляется мне более фундаментальным и не менее трудным для доказательства, чем остальные… Ваши рассуждения весьма основательно и по существу опираются на это предположение, однако нигде нет и намека на его доказательство».
С тех пор, как Хзянь представил усовершенствованный вариант доказательства, между ним и его критиками шла непрекращающаяся борьба. Правильность предъявленного Хзянем усовершенствованного доказательства остается под вопросом. Во всяком случае, для того, кто хочет доказать гипотезу Кеплера, дверь остается открытой. В 1996 году Дуг Мудер изложил свое ви́дение ситуации вокруг доказательства Хзяня, обнаружив некую интригу:
«Недавно я вернулся с Совместной летней научно-исследовательской конференции по дискретной и вычислительной геометрии, состоявшейся в Маунт Холиоке под эгидой Американского математического общества, Института управленческих наук и Общества промышленной и прикладной математики. Такие конференции проводятся раз в десять лет, поэтому акцент делался на прогрессе, достигнутом за последние десять лет. Хзянь заявил о том, что ему удалось доказать гипотезу Кеплера шесть лет назад. Я обнаружил, что сообщество пришло к согласию по этому поводу: его доказательство "никто не покупает".
На пленарных лекциях и во время неформальных дискуссий неоднократно обсуждались следующие вопросы.
1. В статье Хзяня (опубликованной в "International Journal of Mathematics" в 1993 году) не содержится доказательства гипотезы Кеплера. В лучшем случае это набросок доказательства (на 100 страниц!), его общий ход. Таким доказательство могло бы быть.
2. Эта статья не может считаться даже наброском, так как к некоторым ее утверждениям обнаружены контрпримеры.
3. Столь же необосновано утверждение Хзяня о якобы найденном им доказательстве гипотезы о додекаэдре (и различных других ранее недоказуемых проблем упаковки шаров).
4. Работа над гипотезой Кеплера и гипотезой о додекаэдре должна продолжаться так, как если бы статьи Хзяня никогда не существовали.
В одной из лекций Габор Фейеш-Тот из венгерской Академии наук так отозвался о статье Хзяня: "Эту работу нельзя рассматривать как доказательство. Проблема по-прежнему остается открытой." Ему вторил Томас Хейлис из Мичиганского университета: "Проблема Кеплера остается нерешенной. Я не решил ее. Хзянь не решил ее. Насколько мне известно, никто не решил ее." (Хейлис предсказывал, что его собственный метод позволит решить проблему Кеплера "через год-другой".)
Самое интересное в этой истории — то, что один математик так и не присоединился к общему мнению, а именно сам Хзянь (он не был участником конференции). Хзянь был великолепно осведомлен о контрпримерах и о том, что специалисты не верят его утверждениям, но продолжал выступать с лекциями по всему миру, в которых не уставал снова повторять эти утверждения. Те математики, которым доводилось лично общаться с Хзянем (например, Хейлис и Бездек), считают, что Хзянь никогда не признавал, что в его статье имеются ошибки.
Именно по этой причине «пыль» оседала так медленно. Хзянь впервые заявил о том, что располагает доказательством гипотезы Кеплера в 1990 году, т. е. шесть лет назад. Публичные выступления Хзяня достаточно расплывчаты и неопределенны для того, чтобы быть правдоподобными. Через несколько месяцев после первых заявлений о том, что он располагает доказательством, когда появился первый препринт, в доказательстве сразу же были обнаружены пробелы, а вскоре последовали и контрпримеры. Но Хзянь упорно не прекращал лекционную деятельность, и это обстоятельство создавало впечатление, что он, по-видимому, справляется с теми возражениями, которые возникают. Объем его статьи и то, что текст доказательства претерпел несколько переработок до публикации, еще больше усиливали разноголосицу и неразбериху.
Случай с Хзянем показывает, до какой степени математики полагаются на представления о чести. Математическое сообщество исходит из предположения, что почтенные профессора из самых престижных университетов не станут делать скоропалительные, безосновательные заявления и откажутся от ошибочных утверждений, едва в них будет обнаружен пробел. Тот, кто нарушит сложившуюся систему, основанную на представлениях о профессиональной честности, породит смятение, которое будет длиться долго, так как ни у кого нет ни желания, ни времени следовать повсюду за нарушителем и опровергать его всякий раз, когда он будет высказывать ложные утверждения. (Представьте себе, какой объем работы потребовалось проделать Хейлису, чтобы написать свою разоблачительную статью, опубликованную в 1993 году на страницах журнала "Mathematical Intelligencer", и примите во внимание, что она ничего не дала для математической карьеры самого Хейлиса, — и вы поймете эту проблему. Хзянь опубликовал ответ на статью Хейлиса, но его доводы оказались совершенно несостоятельными. Хейлис счел, что критика ответа Хзяня означала бы вхождение в нескончаемый цикл, на продолжение которого у него просто нет времени.)
Хзянь мог позволить себе не признавать своих ошибок, но как обстояло с редколлегией "International Journal"? Ясно, что члены редколлегии оказались вовлеченными в процесс, который пошел не так, как предполагалось. Статья Хзяня не была прорецензирована должным образом, если вообще была прорецензирована. Ранее «Journal» не проявлял ни малейшего интереса к проблеме плотнейшей упаковки шаров. Было ясно, что Хзянь остановил свой выбор на "International Journal" не потому, что это было подходящее периодическое издание для публикации его статьи, а потому, что этот журнал издавали его друзья.
Кароль Бездек, который больше года работал в контакте с Хзянем, пытался заполнить пробелы в его доказательстве, и представил в «Journal» статью, содержащую контрпример одной из лемм Хзяня. Публикация статьи Бездека затянулась надолго — с декабря. Столь долгий срок бывает иногда необходим для рецензирования статьи, но не совсем обычен для контрпримера к самой разрекламированной статье, опубликованной в «Journal» за многие годы».

Спасибо за новость  mkutubi

@темы: История математики, Литература, Люди, Новости, Наука

Comments

[Trotil]

Интересно, спасибо!
А какая цифра плотности упаковки двумерных дисков на бесконечном пространстве?

[Дилетант]

В этой же книге Сингха описывается история проблемы четырех красок (Википедия).


Это первая крупная теорема, доказанная с помощью компьютера.

[Дилетант]

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

***
В июне 1976 года, затратив 1200 часов машинного времени, Хакен и Аппель заявили во всеуслышание, что им удалось проанализировать все 1482 карты и для раскрашивания ни одной из них не требуется более четырех красок. Проблема четырех красок Гатри была наконец решена. Следует особенно подчеркнуть, что решение проблемы четырех красок стало первым математическим доказательством, в котором роль компьютера не сводилась к ускорению вычислений, — компьютер привнес в решение проблемы нечто гораздо большее: его роль была столь значительной, что без компьютера получить доказательство было бы невозможно. Решение проблемы четырех красок с помощью компьютера было выдающимся достижением, но в то же время оно вызвало у математического сообщества чувство тревоги, так как проверка доказательства в традиционном смысле не представлялась возможной.
Прежде, чем опубликовать решение Хакена и Аппеля на страницах «Illinois Journal of Mathematics», редакторам было необходимо подвергнуть его тщательному рецензированию в каком-то не известном ранее смысле. Традиционное рецензирование было невозможно, поэтому было решено ввести программу Хакена и Аппеля в независимый компьютер с тем, чтобы убедиться, что результат останется тем же.
Такое нестандартное рецензирование привело в ярость некоторых математиков, утверждавших, будто компьютерная поверка неадекватна, так как не дает гарантии от внезапного отказа в недрах компьютера, который может стать причиной сбоя в логике. X.П.Ф. Суиннертон-Дайер высказал следующее замечание по поводу компьютерных доказательств: «Когда теорема доказана с помощью компьютера, невозможно изложить доказательство в соответствии с традиционным критерием — так, чтобы достаточно терпеливый читатель смог шаг за шагом повторить доказательство и убедиться в том, что оно верно. Даже если бы кто-нибудь взял на себя труд распечатать все программы и все данные, использованные в доказательстве, нельзя быть уверенным в абсолютно правильной работе компьютера. Кроме того, у любого современного компьютера по каким-то неясным причинам могут быть слабые места как в программном обеспечении, так и в электронном оборудовании, которые могут приводить к сбоям так редко, что остаются необнаруженными на протяжении нескольких лет, и поэтому в работе каждого компьютера могут быть незамеченные ошибки».
До какой-то степени поведение математического сообщества, предпочитавшего избегать компьютеров вместо того, чтобы их использовать, можно рассматривать как своего рода паранойю. Джозеф Келлер как-то заметил, что в его университете (Стэнфорде) математический факультет имел меньше компьютеров, чем любой другой факультет, в том числе факультет французской литературы. Те математики, которые отказались признать работу Хакена и Аппеля, не могли отрицать, что все математики соглашались принимать традиционные доказательства, даже если они сами не проверяли их. В случае доказательства Великой теоремы Ферма, представленного Уайлсом, менее 10 % специалистов по теории чисел полностью понимали его рассуждения, но все 100 % сочли, что доказательство правильное. Те, кто не смог до конца понять все тонкости доказательства, приняли его потому, что доказательство признали другие—те, кто все понял, шаг за шагом проследил весь ход доказательства и проверил каждую деталь.
Еще более ярким примером может служить так называемое доказательство классификации конечных простых групп, состоящее из 500 отдельных работ, написанных более чем сотней математиков. Говорят, что полностью разобрался в этом доказательстве (общим объемом в 15000 страниц) один-единственный человек на свете — скончавшийся в 1992 году Дэниэл Горенстейн. Тем не менее, математическое сообщество в целом могло быть спокойным: каждый фрагмент доказательства был изучен группой специалистов, и каждая строка из 15000 страниц была десятки раз проверена и перепроверена. Что же касается проблемы четырех красок, то с ней дело обстояло иначе: она никем не была и не будет полностью проверена.
За двадцать лет, прошедших с тех пор, как Хакен и Аппель сообщили о доказательстве теоремы о четырех красках, компьютеры неоднократно использовались для решения других, менее известных, но столь же важных проблем. В математике — области, не ведавшей ранее вмешательства столь современной технологии, как компьютеры, — все больше и больше специалистов неохотно осваивали использование кремниевой логики и разделяли мнение Вольфганга Хакена: «Всякий, в любом месте доказательства, может полностью вникнуть в детали и проверить их. То, что компьютер может за несколько часов «просмотреть» столько деталей, сколько человек не сможет просмотреть за всю свою жизнь, не меняет в принципе представление о математическом доказательстве. Меняется не теория, а практика математического доказательства».

[Дилетант]

Trotil, Вот из Википедии:

Упаковка кругов на плоскости
В двумерном евклидовом пространстве наилучшим заполнением является размещение центров кругов в вершинах паркета, образованного правильными шестиугольниками, в котором каждый круг окружен шестью другими. Плотность данной упаковки:
`{\pi}/{2sqrt{3}} approx 0.9069`
Упаковка шаров

Получается, гораздо большая плотность.

[All_ex]

Дилетант, и снова, спасибо!...

[Диана Шипилова]

Спасибо, очень интересно!

[All_ex]

А всё-таки интересно, вроде задача нелинейна... как её свели к линейному программированию...

[olegch]

Интересно, а пытались ли доказать эту гипотезу для большего числа измерений? Часто бывает так, что для большего числа измерений доказательство получается проще, чем для 3-мерного пространства.

P.s. А вот, кстати, сам нашел...
«Помимо трехмерного пространства упаковка шаров также решается для более высоких размерностей. Так, в 2016 году украинский математик Марина Вязовская решила задачу об упаковке в восьми- и (в соавторстве) 24-мерных пространствах. Тогда же ученый получила премию Салема. Стоит отметить, что задача об упаковке в высших размерностях также имеет практическое применение, например в области передачи данных. Уплотнение упаковки позволяет минимизировать риск шумов и, как следствие, ошибок на этапе декодирования.»
(Ист. - naked-science.ru/article/sci/opublikovano-okonc...)

[Amicus Plato]

olegch, спасибо!

тоит отметить, что задача об упаковке в высших размерностях также имеет практическое применение, например в области передачи данных. Уплотнение упаковки позволяет минимизировать риск шумов и, как следствие, ошибок на этапе декодирования.

Хорошо бы, чтобы они это как-нибудь прокомментировали.
Как упаковка в 24-мерном пространстве может уменьшить риск шумов при передаче данных...

[olegch]

Хорошо бы, чтобы они это как-нибудь прокомментировали. Как упаковка в 24-мерном пространстве может уменьшить риск шумов при передаче данных...

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

[Гость]

"Хорошо бы, чтобы они это как-нибудь прокомментировали.
Как упаковка в 24-мерном пространстве может уменьшить риск шумов при передаче данных..." - речь шла о том, как округлять данные до неких целых значений (делать квантование вообщем) с наименьшими потерями, и сколько закладывать "на риск" =). в простейшем случае пример с сотами очень хорошо понятен будет. можно просто кругами замостить плоскость, но тогда дырки останутся. а можно внахлест, но тогда будет лишнее. а вот шестиугольники - самое то.