Математические байки

Возвращаясь к ним-сложению: если взять d=2, то становится понятно, что это близкая история. А именно: d=2 означает, что мы последовательно (в словарном порядке) перечисляем варианты первых (n-1) букв — и пытаемся их дополнить последней буквой — наименьшей из тех, которая ещё не встречалась раньше для слов, отличающихся лишь в одной из первых (n-1) букв.

Тот самый код Голея, который применялся для передачи изображений от Вояджеров — который за счёт сокращения скорости вдвое (12 бит передаётся 24-мя) позволяет исправить 3 ошибки в группе (и обнаружить, хоть и не исправить, наличие четырёх: у него кодовое расстояние 8) — https://en.wikipedia.org/wiki/Binary_Golay_code#NASA_deep_space_missions

Интересно, что такая "жадная" процедура позволяет породить как код Хэмминга — что заметил ещё Левенштейн — так и код Голея, что заметили Конвей со Слоаном:

Для алфавита из {0,1} лексикографические коды рассматривал задолго до того Левенштейн — см. http://mi.mathnet.ru/dan39976 — но связи с теорией игр у него из-за этого не было (а Конвей со Слоаном о его работе, очевидно, не знали).

Вот кусочек из работы Конвея и Слоана, "Lexicographic Codes: Error-Correcting Codes from Game Theory" — посвящённый как раз этим утверждениям:

То, что ab=1, видно, например, из 2* 001321 = 002132 — в левой части мы знаем всё, кроме "2*3".

Но соотношения мы получаем как раз какие надо: в поле из 4 элементов, кроме 0 и 1, для которых 1+1=0, есть ещё два элемента, a и b (те самые наши "2" и "3"), причём a^2=b, b^2=a, ab=1, a+1=b, b+1=a.

И вот мы получаем "2*2=3" в поле из 4 элементов {0,1,2,3} — только обычно, конечно, никто не обозначает его элементы 2 и 3, потому что 2 это вовсе не 1+1 (которое там равно нулю).

И если верить в теорему выше — то слово 002023 должно быть равно 2*001012, где множитель два — элемент поля из 4 элементов.

Например, при B=4 (то есть k=2) и n=6 наш код начнётся со слов 000000 000111 000222 000333 001012 001103 001230 001321 002023 002132 ...

Собственно, если взять вместо бесконечного алфавита — алфавит из B=2^{2^k} символов, — а слова ограничить конечной длиной n — то мы получим часть этого кода: слова, у которых лишь последние n символов ненулевые, и которые не выходят за алфавит A={0,1,...,B-1}. И это уже совсем ситуация кодов, с которой этот рассказ начинался.

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

На самом деле, это поле будет объединением "возрастающей башни" полей из 2^{2^k} элементов (поле из p^m элементов это подполе p^r элементов, если r это степень m). Более того, сложение тут — это то самое ним-сложение (побитовое сложение двоичных записей), которым решается задача о выигрышных позициях в игре в ним.

Конечно же, сложение и умножение получаются нестандартными — а поле будет характеристики 2.

Но интересного больше. Теорема, которую рассказывал Конвей на лекции — Теорема. Можно так ввести на неотрицательных целых числах сложение и умножение (превратив их в поле), что построенный код будет линейным.

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

Так вот, мы всё это делали не просто так!

И когда мы, проявив упорство, добавим всё бесконечное число слов вида 001*** — первым словом вида 002*** будет 002023. Потому что 00200* слишком близко к 000000, 00201* слишком близко к 001012, 002020 — опять к 000000, 002021 — к 001321 (и это легко пропустить), 002022 — к 000222, ну и 002023 — то, что нужно.