Часто в отношении математических рассуждений можно услышать восклицание: "Да что же так сложно-то!" Оно, как правило, относится к объяснениям чего-то, что, как кажется, должно быть довольно простым.
Но ведь математика — это доступное нам волшебство, а волшебство не может быть примитивным, иначе оно превращается в трюкачество.
Меня всегда привлекали неочевидные математические решения, которые выглядят как чудо: решение очень простое и эффективное, но абсолютно непонятно, как это можно придумать! Найти такие чудеса случайно, чаще всего, невозможно, для этого нужно глубоко погрузиться в магию математики, от простого абстрагироваться к сложному, а потом вернуться обратно к простому и удобному результату. Большинство таких чудесных решений нужны в самой же математике и широкая публика ими не пользуется (например, гауссовы квадратуры, преобразования Лапласа и т.п.), но некоторые из них прочно вошли в повседневную жизнь.
Я хочу рассказать о том, как весьма абстрактная алгебра помогает нам правильно вводить номера банковских карт, авиабилетов и прочих номеров, при записи которых, легко допустить ошибку.
Вспомните, когда вы вводите номер банковской карты, компьютер может сообщить вам о том, что номер введён неверно. И действительно, одна цифра оказывается указана неправильно, или две цифры поменялись местами. После исправления этой ошибки, номер проходит проверку и вы продолжаете работу. Но откуда программе известен правильный номер карты? За нами следят? Возможно, но не в этом случае. Задача обнаружения ошибки решается проще, можно сказать, механически.
Взгляните на эти три последовательности:
Только одна из них (первая) может быть номером банковской карты, другие, отличающиеся от неё всего на одну цифру или на одну перестановку, уже не годятся. Таких банковских карт, попросту, не бывает, поскольку их никто не выпускает. А определяются "правильные" номера с помощью метода, который предложил и запатентовал американец Ганс Питер Лун в 1960 году. Вот как им пользоваться:
- Цифры проверяемой последовательности нумеруются справа налево.
- Цифры, оказавшиеся на нечётных местах, остаются без изменений.
- Цифры, стоящие на чётных местах, умножаются на 2.
- Если в результате такого умножения возникает число больше 9, оно заменяется суммой цифр получившегося произведения — однозначным числом, то есть цифрой.
- Все полученные в результате преобразования цифры складываются. Если сумма кратна 10, то исходные данные верны.
Проверьте, работает ли этот алгоритм на ваших банковских картах?
В своём патенте Лун, следуя духу своего времени, приводит чертежи механического устройства, которое способно выполнять эту проверку автоматически. Такой метод не способен показать где именно совершена ошибка, но он может указать, на то, что ошибка где-то есть. В частности, им обнаруживаются изменение любой одной цифры, и практически все парные перестановки подряд идущих цифр (за исключением 09 ⇆ 90). Однако метод Луна пропустит некоторые искажения двух подряд идущих цифр, а именно 22 ⇆ 55, 33 ⇆ 66 и 44 ⇆ 77. Кроме того, останутся незамеченными и перестановки чисел через одну, скажем, между третьей и пятой позициями.
Как именно рассуждал Лун, придумывая свой метод, мне не известно. В его оригинальном патенте метод предлагается "как есть" без подробного математического обоснования. Но для того, чтобы его значительно усовершенствовать и при этом упростить, потребовалась уже серьёзная математика.
* * *
Метод Луна для последовательности цифр a₁, a₂, a₃, a₄... можно компактно записать таким уравнением:
a₁ + f(a₂) + a₃ + f(a₄) + ... = 0 mod 10.
Где + — обыкновенное числовое сложение, а функция f — задаётся такой перестановкой: (0246813579). В перестановке порядковый номер числа указывает на аргумент функции, а само число — на соответствующий аргументу результат.
А можно ли отыскать такую функцию f, чтобы метод отлавливал как можно больше возможных ошибок? Можно, но для этого продуктивнее заняться совершенствованием не функции f, а операции +.
Числа можно не только складывать, а складывать можно не только числа. Размышления на эту тему породили теорию групп, и абстрактную алгебру, которые ныне "заправляют" почти во всех областях математики. Обычно, введение в теорию групп начинают с группы симметрии треугольника или квадрата. Их можно поворачивать и зеркально отражать, можно эти преобразования комбинировать и обращать.
По традиции, групповую операцию (комбинирование элементов) называют умножением и обозначают соответственно. Через семь лет после выхода работы Луна, голландский математик и скульптор Якобус Верхуфф показал, что если не складывать десять цифр, как числа, а перемножать, как десять преобразований симметрии правильного пятиугольника, то можно просто перемножив таким образом все цифры последовательности, "засечь" многие типичные ошибки: замены одной цифры и перестановки, а также парные замены и замены через одного. Вот как выглядит "таблица умножения" для диэдральной группы D₅ (группы симметрий правильного пятиугольника).
Каждая цифра в ней соответствует одному из преобразований пятилепесткового цветка, совмещающему лепестки, но переставляющему их цвета. Произведением двух цифр a и b, согласно этой таблице, будет цифра в строке a и столбце b. Например, 2*3 = 0, 3*3 = 1. Чтобы проверить на отсутствие ошибок последовательность a₁, a₂, a₃,,...,c, достаточно убедиться в том, что a₁*a₂*a₃·... = c, где последняя цифра приписывается к последовательности, как контрольная.
Например, для числа 4279 1610 4026 9835 групповое произведение в D₅ всех цифр равно 7. При попытке заменить одну произвольную цифру и при перестановке соседних цифр контрольное произведение изменится. В своей работе Верхуфф утверждал, что это единственное известное ему полезное применение группы D₅. Но на этом он не остановился, обнаружив, что если перед перемножением применить к цифре ещё и некую "волшебную" функцию, то эффективность проверки вырастет до 93%. Дополнительная функция задаётся ещё одной таблицей, и порождается подобно функции f, особой перестановкой. Дополненный метод Верхуффа позволяет заметить даже фонетические ошибки, характерные для английского языка: 13⇆30, 14⇆40 и т.п. Получился чрезвычайно эффективный, но уже сложноватый метод, требующий полноценной работы двух непонятно откуда взявшихся таблиц. Из-за своей сложности он не получил широкого распространения, уступая на практике методу Луна.
Группа — штука очень полезная и крутая, но она накладывает ряд серьёзных ограничений на то, что может делать с её элементами групповая операция. Она должна быть ассоциативна, все элементы обратимы и в группе должен иметься нейтральный элемент. У нас десять цифр и существует всего две группы с десятью элементами — упомянутая D₅ и циклическая группа C₁₀ (группа сложения чисел по модулю 10). Так вышло, что одна из них оказалась подходящей. Но, может быть, можно найти что-то ещё лучше, не требующее дополнительных функций и таблиц?
Можно! Но для этого нужно подняться ещё выше по ступенькам абстракции и от групп перейти к квазигруппам. Этим путём уже в 2004 году пошёл немец Микаэель Дамм. Квазигруппа — это довольно забавная структура: квазигрупповая операция в ней не обязана быть ассоциативной (не всегда (a*b)*c = a*(b*c)), для неё нет универсального нейтрального элемента (единицы), но она обратима (любое уравнение a*x = b или x*a = b имеет единственное решение). Квазигруппу, например, образуют целые числа с операцией вычитания и рациональные числа с операцией деления. Обратимость операции в квазигруппе приводит к тому, что таблица умножения для любой из них представляет собой латинский квадрат. Это такая таблица n×n, заполненная n различными символами (цифрами или буквами) так, что во всякой строке и во всяком столбце обязательно встречаются все символы (очевидно, по одному разу). Когда вы играете в Судоку, вы заполняете латинский квадрат 4×4, который является для какой-нибудь квазигруппы таблицей умножения. Достройте по принципам Судоку следующий квадрат:
и убедитесь в том, что он определяет квазигруппу со следующей операцией: a*b = (a – b) mod 4.
Квазигруппы дают гораздо больше свободы, чем группы, но вот беда! — из-за этого их не просто много, а катастрофически много! Только для 4 элементов можно построить 576 квазигрупп, а для 10 элементов их число равно 9 982 437 658 213 039 871 725 064 756 920 320 000. Однако Микаэель Дамм знал что искать в этом стоге сена (размером с приличную Вселенную). Он пошёл таким путём: составил уравнения для возможных ошибок и из них вывел ограничения на латинский квадрат (простая замена потребовала полной антисимметричности, парные перестановки – некоммутативности и т.д. всего 12 уравнений). Тем самым он смог ограничить число нужных квазигрупп с 10 додекалионов до 40 миллионов, с которыми уже может работать компьютер. И в 2004 году ему удалось построить латинский квадрат, который позволяет одним простым перемножением всех цифр последовательности по соответствующей квазигруппе вычислить контрольную цифру, исключающую практически все те же неприятности, с какими справляется метод Верхуффа, и даже немного больше.
Более того, впоследствии удалось отыскать квазигруппы, пригодные для сигнализации об ошибке не только в последовательности цифр, но и букв (вплоть до 64 знаков)! Более того, многие пригодные для детекции ошибок квазигруппы оказываются изоморфны (взаимозаменяемы) квазигруппам простых операций над целыми числами в модулярных арифметиках или иных кольцах, так что даже таблицы оказываются не нужными. Квазигрупповую операцию можно, в ряде случаев, заменить простым вычитанием в подходящем кольце.
Результат выглядит очень простым: одна волшебная табличка или даже простая формула. Её использование просто и быстро, оно на голову более эффективно чем метод Луна и существенно проще метода Верхуффа. Сейчас её постепенно берут на вооружение государственные и банковские структуры в различных странах. Но путь к этому решению оказался весьма и весьма непростым. Если диссертация Дамма потеряется, то его табличка превратится в классическую "утерянную технологию древних": она работает, но почему — не понятно, и придумать её заново будет очень сложно!
Не сетуйте на то, что математики из простых вещей городят невероятно сложные абстракции. Они — волшебники, и прямо сейчас творят волшебство будущего, простого и удобного для нас. Кроме того, они ещё и художники, создающие своим воображением тонкие и изящные формы из бесконечного многообразия мыслимых математических объектов.