Недавние успехи в решении задачи «суммы произведений» напоминают о знаменитом математическом результате, который продемонстрировал возможности миниатюрных систем счисления. Комментарий Сохранить статью Прочитать позже
В арифметике часов описывается любая конечная числовая система, которая зацикливается сама на себе.
Введение
Одно дело — сделать колесо на открытом поле. Совсем другое — справиться с этим в тесном пространстве, например, в ванне. И в каком-то смысле в этом заключается суть одного из важнейших результатов теории чисел за последние два десятилетия.
Результат связан с «задачой о сумме и произведении», о которой я писал на прошлой неделе. Она требует взять любой набор чисел, расположить их в квадратной сетке, а затем заполнить сетку либо суммами, либо произведениями пар чисел, расположенных крест-накрест.
В задаче о сумме и произведении утверждается, что количество различных сумм или произведений всегда будет близко к N² (где N обозначает количество чисел, использованных для составления таблицы).
В задаче о сумме и произведении, о которой я писал, для генерации сетки используется любой набор действительных чисел. Также можно ограничить задачу использованием уникальных числовых систем, которые меньше и более ограничены, чем действительные числа. Такие самодостаточные числовые системы называются «конечными полями».
В математике «поле» — это любая числовая система, в которой можно выполнять четыре основные арифметические операции: сложение, вычитание, умножение и деление. Поле образуют действительные числа. Эти операции можно выполнить над любыми двумя действительными числами, и результатом будет третье действительное число. Иными словами, арифметика действительных чисел никогда не даст числа, находящегося за пределами этого поля.
Целые числа — все положительные и отрицательные натуральные числа — не образуют поле. Да, вы можете складывать, вычитать и умножать любые два целых числа, чтобы получить третье целое число. Но если разделить 3 на 2, вы получите 1½, что не является целым числом.
«Конечное» поле — это система счисления, в которой количество чисел конечно. Существуют разные виды конечных полей, но самое простое связано с так называемой «модулярной» или «часовой» арифметикой. В модульной арифметике, достигнув конца конечного списка чисел, вы просто возвращаетесь к началу, как если бы вы считали числа на циферблате часов. Например, если вы пришли на вечеринку в 7 вечера и вернулись домой через шесть часов, то вернетесь в 1 час ночи. Более формально, 7 плюс 6 в двенадцатеричной модульной системе счисления равно 1.
(12 цифр на часах на самом деле не образуют поле, и причина этого связана с одной из важнейших особенностей теории чисел: модульные системы счисления образуют поля только тогда, когда состоят из простого числа элементов. В модульных системах счисления с непростым числом элементов, таких как 12-разрядные часы, возникают странные ситуации, когда произведение двух ненулевых чисел равно нулю. Например, 6 × 4 = 24, что равно 0 в двенадцатеричной системе счисления. Это приводит к другим последствиям, из-за которых деление становится невозможным. Но в модульной системе счисления с простым числом элементов два ненулевых числа никогда не умножаются на ноль.)
Конечные поля стали основой для многих известных результатов в математике. Будучи самодостаточными арифметическими мирами, они обладают богатой структурой, которую математики могут использовать для решения задач, связанных со всем, от простых чисел до закономерностей в решениях полиномиальных уравнений.
В 2003 году математики Жан Бурген, Нетс Кац и Терри Тао стали первыми, кто добился прогресса в решении проблемы сумм и произведений над конечными полями. Они доказали, что либо число различных сумм, либо число различных произведений должно быть хотя бы немного больше размера множества, используемого для генерации сеток сумм и произведений. Это утверждение было скромным по масштабу, но имело огромное значение.
Жан Бурген (вверху), игрок команды «Нетс» Кац и Терри Тао продемонстрировали важную связь между сложением и умножением.
Жан Бурген, Нетс Кац и Терри Тао (слева направо) продемонстрировали важную связь между сложением и умножением.
«Это было самое незначительное, чего мы смогли добиться, но суть в том, что это был первый результат такого рода», — сказал Кац, который сейчас работает в Калифорнийском технологическом институте.
Авторами статьи была мощная команда: Кац — весьма уважаемый теоретик чисел, а Бурген и Тао считаются одними из лучших математиков своего поколения. Бурген, скончавшийся от рака в декабре в возрасте 64 лет, был движущей силой доказательства. Несколькими годами ранее он решил другую задачу на сумму-произведение. Когда он обратился к версии для конечного поля, у него было довольно четкое представление о том, как проводить доказательство, но он привлек Каца и Тао для помощи в понимании всех следствий его предполагаемого метода.
«В принципе, Бурген знал, как это сделать, и хотел нашей помощи, потому что хотел описать некоторые примеры применения [своего подхода]», — сказал Кац.
Начиная с 2003 года, другие математики улучшили результат этой тройки, установив, что число различных сумм или произведений должно быть даже больше, чем то, что им удалось гарантировать. Математики также применили методы из их доказательства к совершенно другим вопросам математики, включая изучение объектов, называемых расширяющими графами, и вопросы о многочленах и простых числах.
Конечные поля, которые можно держать в руке, могут показаться менее сложной задачей для решения проблемы суммы-произведения, чем действительные числа. Но на самом деле в случае конечных полей этот вопрос имеет гораздо большую глубину и гораздо большее значение для всей математики.
Причина в том, что явление суммы и произведения гораздо сложнее реализовать для конечных полей, чем для действительных чисел. Первоначальная формулировка задачи предсказывала, что любой набор чисел будет порождать сетки сумм и произведений с гораздо большим количеством различных элементов, чем размер самого набора. Возможно, это не такое уж удивительное утверждение, если рассматривать его в контексте действительных чисел, которые бесконечны. Но чтобы это было правдой в конечных полях, где практически нет места для маневров? Это все равно что сделать колесо в ванне.
«Вещественные числа представляют собой бесконечное множество, и в них есть огромный потенциал для роста. Но в конечном поле возможности для роста очень ограничены, поэтому, когда вы получаете гарантию того, что часть этого роста произойдет, это становится более убедительным утверждением», — сказал Кац.
Источник: www.quantamagazine.org
