Конечные алгебры, геометрии и коды. Лекция Григория Кабатянского в Яндексе

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

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

Для начала подумаем, как рассадить на n–мерном кубе максимальное число Sp(n) пауков так, чтобы они не дрались. У паука n лап — по одной на каждое ребро, при этом длина лапы равна длине ребра куба. Драка начинается, если два паука дотянулись до одной и той же вершины. Можем ли мы добиться совершенного расположения: чтобы на каждой вершине было по пауку?

К тому же классу можно отнести и две следующие задачи:

• Сколько можно расставить на n-мерной шахматной доске размера q × q… × q так, чтобы никакое поле не билось более одного раза?
• При каких n и q существует такая расстановка ладей на n-мерной шахматной доске размера q × q… × q, что каждое поле бьется один раз?

О пауках

В трехмерном пространстве все достаточно очевидно: Sp(3) = 2? Так как если мы поставили двух пауков в вершины трехмерного куба, то они обязательно диаметрально противоположны, и занимают своими лапами три исходящих вершины. Третьего паука уже ставить уже некуда.
Когда известно максимальное число пауков?
Sp(3) = 2, Sp(4) = 2, Sp(5) = 4, Sp(6) = 8, Sp(7) = 16…?
Sp(15) = 2¹¹, Sp(14) = 2¹⁰, Sp(13) = 2⁹, Sp(12) = 2⁸
Но Sp(8) = 20, Sp (9) = 40, Sp(10) = 72, Sp(11) = 144
То что Sp(10) ≥ 72; Sp(11) ≥ 144 было известно довольно давно, но доказать равенство удалось лишь в 1999 году.

Покажем, что если Sp(2^r-1)= 2^2r-1-r, то это совершенная расстановка пауков (или ладей при q =2). Каждый паук занимает вершину, где сидит, и еще n = 2^r — 1 вершин, куда дотягиваются его лапы. Итого n + 1 = 2^r вершин занято одним пауком, а их Sp(2^r-1)= 2^2r-1-r=2^n-r. Следовательно, все вершины куба заняты – это совершенная расстановка.

Зададим множество C вершин, где сидят пауки, для n = 7 системой из трех линейных уравнений.
x₁⊕x₃⊕x₅⊕x₇ = 0; x₂⊕x₃⊕x₆⊕x₇ = 0; x₄⊕x₅⊕x₆⊕x₇ = 0, где a⊕b – это сложение по mod2, т.е. 1⊕1 = 0(mod2), а остальное – как обычно.

Обозначим через H матрицу коэффициентов этой системы линейных уравнений:

Тогда эту систему можно переписать как Hx^T = 0. Заметим, что i-ный столбец – это двоичное представление числа i.

Нам надо доказать, что любой двоичный 7-мерный вектор y «принадлежит» ровно одному пауку, или, что тоже самое, поле y бьется ровно одной ладьей.

Вычислим s = Hy^T. Если s = (0, 0, 0), то y ∉ C там сидит какой-то паук. Если же s ≠ (0, 0, 0), то s = h_i – это i столбец матрицы H для некоторого i, и, следовательно, c = y ⊕ e_i ∈ C, где e_i – это вектор из всех нулей, кроме 1, стоящей в i-ой координате. Тогда паук, сидящий в вершине c = y ⊕ e_i, дотягивается лапой до i-ой координатной оси вектора y. Если бы паук, сидящий в другой вершине c', дотягивался лапой вдоль j-ой координатной оси до вектора y, то y = c' ⊕ e_j и Hy^T =Hc'^T + He_j^T = h_j, что ведет к противоречию, так как h_i ≠ h_j – все столбцы матрицы H различны. Если же i = j, то c' = c.

Коды исправления ошибок

Представим, что у нас есть последовательность нулей и единиц, которые мы хотим передавать по каналу, в котором в редких случаях могут происходить ошибки при передаче. При передаче по семь бит, у нас может либо совсем не быть ошибок, либо одна ошибка: какая-то из переданных позиций будет принята в противоположном положении. Предполагается, что мы заготовили список из 16 слов длиной по 7 бит. Слова могут быть пронумерованы двоичными векторами длины 4. И тогда получится, что получателю будет отправлено 4 бита информации при помощи 7 бит. Это конечно, накладные расходы. Есть более простой способ: мы можем каждый бит передавать по три раза. Если передаче допускается не более одной ошибки, неправильно переданный бит будет восстановлен. Но так мы будем передавать четыре бита при помощи двенадцати. Соответственно, передача четырех бит через семь выходит экономнее. Четыре бита из семи будут передавать информацию, а три оставшихся – выступать в роли проверочных.

Итак, передается вектор из нулей и единиц. Один из шестнадцати разрешенных. Мы точно не знаем произошла ли ошибка при передаче. На приемнике нам нужно знать, перешел ли один из битов в противоположное положение. Для этого мы возьмем вектор, который вышел из канала и вставим его в нашу систему линейных уравнений. Если все удовлетворится, то это кодовый вектор, один из разрешенных шестнадцати, ошибки при передаче не произошло. А если какие-то из трех уравнений выполнены, а какие-то нет, то мы запишем невыполненные как 1, а невыполненные – как 0. У нас получится то же самое, что мы рассматривали выше: умножение матрицы на вектор. Если s будет равен 0, то передача прошла без ошибок, в противном случае в позиции i произошла ошибка.

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

Автор: elcoyot

Источник ^[1]