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

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

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

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

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

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

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

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

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

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

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

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

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

Собственно, сопоставив слову
003451
игру ним с кучками из 3, 4, 5 и 1 камня, мы увидим, что разрешённый ход это как раз уменьшение любой из координат, а условие, что ни одним разрешённым ходом нельзя попасть в слово кода (запрет на расстояние 1) как раз и значит, что из позиции нет хода в проигрышную — и потому она сама проигрышная.

А ход рассуждений с "наименьшим ещё не названным" для последнего символа соответствует доказательству теоремы Шпрага-Гранди — и принципу "наименьшего исключённого".

Да — мы тут потихоньку перешли от теории кодирования в область комбинаторной теории игр. (Где, кстати, книги Конвея "On Numbers and Games" и его же с Берлекампом и Ги "Winning Ways for your Mathematical Plays" — совершеннейшая классика.)

Ну и, наверное, до того, как переходить к этому рассказу, я показать несколько фотографий Рины Сергеевой с тех летних школ, на которых мы с Конвеем пересекались.

Вот тут — https://www.flickr.com/photos/lemezza/7958436406/in/album-72157631334930426/ — Конвей рассказывает про те самые лексикографические коды. В левой части доски как раз идёт выписывание слов, которые мы видели — а в правом верхнем углу доски можно даже разобрать "LEXICODE".

А вот тут — https://www.flickr.com/photos/lemezza/11280987216/in/album-72157638495119084/ —
Конвей в окружении участников. Собственно, это на всех школах было перманентное состояние Конвея: быть окружённым участниками, которым он что-то рассказывает, начиная с завтрака и зачастую заканчивая заполночь (и, конечно, включая завтраки, обеды и ужины!).

Вот тут — https://www.flickr.com/photos/lemezza/7902531034/in/album-72157631334930426/ — Конвей играет в футбол. Но не в обычный, а в придуманный им: см. https://en.wikipedia.org/wiki/Phutball

Гил Калаи вспоминает про эту игру (см. https://www.scottaaronson.com/blog/?p=4732#comment-1836693 ):
"<...>Conway set a special rule for me: Everytime I am convinced that I loose, we can switch sides. Needless to say that we switched sides several times; I was sure that my position is desperate beyond repair, we switched sides, and shortly afterward I was again sure that my position in the game is beyond repair.<...>"

А вот что пишет (см. https://terrytao.wordpress.com/2020/04/12/john-conway/ ) Теренс Тао:
"<...>I still remember being repeatedly obliterated in that game, which was a healthy and needed lesson in humility for me (and several of my fellow graduate students) at the time.<...>"