Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

немного про конечные поля

  • свалка ссылок и выписок про историю конечных полей
  • постараюсь вкратце объяснить для нематематиков, чтоб совсем скучно не было, но лишь вкратце
  • математики называют "полем" набор чисел, с которыми можно делать обычные операции плюс, минус, умножить, делить (кроме деления на ноль), с обычными их свойствами: от перестановки слагаемых сумма не меняется, можно раскрывать скобки, итд. итд.
  • например, все рациональные числа (т.е. положительные и отрицательные целые и дроби) это поле, обозначают Q
  • все действительные числа (с десятичной запятой) это поле, обозначают R
  • все комплексные числа (...) это поле, обозначают C
  • но кроме того, бывают поля конечного размера, в них всего конечный набор "чисел"
  • самый простой пример - берем простое число p и считаем всё по модулю p (то есть берем остатки от деления на p). Например, p=5, тогда у нас в поле есть числа {0,1,2,3,4}, плюс и умножить как обычно, но по модулю p, 3*3 mod 5 = 9 mod 5 = 4, поэтому в этом поле 3*3=4. Казалось бы, мы не можем делить, потому что нет дробей типа 1/2, но оказывается, что из-за "по модулю" все можно поделить: 1 поделить на 2 будет 3, потому что 3*2 = 1 по модулю 5. Это поле называется F_5. Для любого простого p есть поле F_p.
  • если p не простое число, то это не работает и поля нет, потому что не все "делится": например, по модулю 6 нельзя поделить 1/3, потому что 3*x всегда либо 0 либо 3 по модулю 6, и не может быть 1.
  • поля вида F_p изучались начиная с 18 века, особенно много для их изучения сделал Эйлер (он конечно не называл это так, с его точки зрения он изучал свойства операций по модулю), Лежандр, потом Гаусс
  • есть и другие конечные поля, не только вида F_p, и их впервые построил Эварист Галуа, гениальный французский математик, погибший на дуэли в возрасте 21 года
  • у поля вида F_p размер (число элементов) ровно p, от 0 до p-1. У любого конечного поля размер обязан быть степенью простого числа, какое-то p^n. Например, есть конечное поле размером 9 (степень тройки), но нет поля размером 6 (не степень простого). У этого факта есть очень простое и потрясающе красивое доказательство, которое требует, однако, знания высшей математики, см. конец записи
  • возьмем какое-то конечное поле, например F_p: {0,1,2,3,4} по модулю 5, возьмем какой-то ненулевой элемент и начнем умножать на самого себя, рано или поздно мы придем к 1. Например: 4*4 = 16 = 1 mod 5, пришли всего за один шаг. С другой стороны, 3*3=4 mod p, (3*3)*3=4*3=12=2 mod p, (3*3*3)*3=2*3 = 6 = 1 mod p. То есть 3->4->2->1, по дороге к 1 мы прошли сквозь все ненулевые элементы. Если есть число, которое по модулю p проходит сквозь все ненулевые остатки, если его возводить в степень, то оно называется "примитивный элемент". В поле F_5, как мы увидели, 3 примитивный элемент, а 4 нет.
  • есть теорема: в любом конечном поле есть примитивный элемент. На современном языке это звучит так: "мультипликативная группа конечного поля циклична".
  • впервые эту теорему доказали только для всех F_p, а не конечных полей вообще, потому что это было до Галуа, и про другие поля не знали.
  • первое подробное доказательство есть в книге Гаусса Disquisitiones Arithmeticae (1801), параграф 52. У этой книги есть английский перевод, его можно скачать в обычном месте. Кроме того, есть доказательство Эйлера на четверть века раньше, и Лежандра между ними, но они не столь точные, как доказательство Гаусса
  • согласно Гауссу, в доказательстве Эйлера есть две "дыры", хотя Андре Вейль, знаменитый математик 20 века, написавший книгу об истории теории чисел, пишет в ней, что Гаусс придрался к Эйлеру и серьезных проблем с его доказательством нет
  • доказательство Эйлера есть в его статье Demonstrationes circa residua... (Е449, 1772). Эта статья до сих пор не переведена с латыни, как и большинство трудов Эйлера. Есть проект перевода всех непереведенных работ Эйлера, и есть определенный прогресс.
  • Галуа в своей работе про другие конечные поля (не F_p), просто пишет, что в них наличие примитивного элемента доказывается "аналогично" случаю F_p. Это в общем верно, если использовать доказательство Гаусса (но не Эйлера).
  • у теоремы про примитивный элемент есть несколько простых доказательств, которые можно сформулировать на современном языке. В этой заметке Кита Конрада собрано 7 доказательств. Они сформулированы для F_p, но 6 из них работают без изменений для любого конечного поля.
  • почти все доказательства пользуются следующим фактом, который верен в любом поле (не только конечном): у многочлена степени n не может быть больше n корней. Например, у квадратного уравнения есть не более 2 корней, у кубического не более 3, итд. Это может показаться тривиальным, но требует доказательства. В конечном поле именно этот факт позволяет доказать, что есть примитивный элемент.
  • интересный факт: до сих пор никто не знает, как найти примитивный элемент для данного F_p. Например, 97 простое число, значит есть примитивный элемент в F_97 (даже больше одного): может, это 2? может, 3? может, 4? Как узнать? Лучше чем пробовать возводить в степень и смотреть, что получится, математики пока не придумали.
  • мне интересно было, есть ли другие доказательства этой теоремы, не пользующиеся этим фактом о корнях многочленов, и как ее первоначально доказывали, когда придумали. Доказательств, не пользующихся фактом про многочлены, я не нашел (кроме конкретного случая F_p, см. седьмое доказательство Конрада). Первоначальные док-ва Гаусса и Эйлера уже пользовались фактом о корнях многочлена, хотя они конечно не оперировали понятиями "многочлен" или "поле". Гаусс просто и элегантно доказывает этот факт индукцией по степени многочлена (пар. 43 его книги). На современном языке это немедленно следует из алгоритма деления многочленов с остатком в кольце многочленов F[x] над полем F.
  • рекомендую отличную статью Heinz Liineburg, "On the Early History of Galois Fields", Finite Fields and Applications 1999, p. 341. Рассказывает более подробно и точно материал, описанный выше, и многое другое. Книжка есть в обычном месте.
  • Историческая книга Андре Вейля называется "Number theory: an approach through history. From Hammurapi to Legendre". Я собираюсь ее прочитать
  • приложение. Как доказать, что размер любого поля степень простого числа. Пусть есть конечное поле F. Выделим его "простое подполе" P следующим образом: 0, 1, 1+1, 1+1+1, .... пока не будет опять 0. Число элементов в простом подполе должно быть простым p, потому что иначе это не поле (если например число элементов p*q, то (1+1+1... p раз)(1+1+1... q раз) = 0). Все поле F может теперь быть рассмотрено как векторное пространство над полем P. Если размер базиса в этом пространстве n, то число элементов F равно p^n, все.
Tags: математика
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 48 comments