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

  Хоча майже всі в навколишньому світі звичайно, в математиці донедавна домінували нескінченні об'єкти. Серйозний інтерес до кінцевої математики виник всього півстоліття тому — з появою перших комп'ютерів. І нескінченна (безперервна) математика залишається для нас набагато звичніше і зрозуміліше.
 
Ця лекція присвячена дивовижному повороту історії, коли кінцеві поля (поля Галуа), перш незнайомі навіть багатьом професійним математикам, стали раптом затребувані інженерами, і тому, як це змінило наше знання теорії кінцевих полів і споріднених об'єктів.
 
 
 
Для початку подумаємо, як розсадити на 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 11 , Sp (14) = 2 10 , Sp (13) = 2 9 , Sp (12) = 2 8
Але Sp (8) = 20, Sp (9) = 40, Sp (10) = 72, Sp (11) = 144
Те що Sp (10) ≥ 72; Sp (11) ≥ 144 було відомо досить давно, але довести рівність вдалося лише в 1999 році.
 
Покажемо, що якщо Sp (2 r -1) = 2 2 r -1-r , то це досконала розстановка павуків (або ладей при q = 2). Кожен павук займає вершину, де сидить, і ще n = 2 r — 1 вершин, куди дотягуються його лапи. Разом n + 1 = 2 r вершин зайнято одним павуком, а їх Sp (2 r -1) = 2 2 r -1-r = 2 nr . Отже, всі вершини куба зайняті — це досконала розстановка.
 
Задамо безліч C вершин, де сидять павуки, для n = 7 системою з трьох лінійних рівнянь.
 x 1 x 3 x 5 x 7 = 0; x 2 x 3 x 6 x 7 = 0; x 4 x 5 x 6 x 7 = 0 , де a b — це додавання по mod2 , тобто 1 ⊕ 1 = 0 (mod2 ), а решта — як звичайно.
 
Позначимо через H матрицю коефіцієнтів цієї системи лінійних рівнянь:
 
 image
 
Тоді цю систему можна переписати як 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 сталася помилка.
 
Додивившись лекцію до кінця, ви дізнаєтеся, як визначити, де саме сталася помилка, про коди Хеммінга, що виправляють помилки, кінцевих полях і про те, як все це пов'язано із звичайною математикою.
  
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.