avva | немного про конечные поля (Reply)

свалка ссылок и выписок про историю конечных полей
постараюсь вкратце объяснить для нематематиков, чтоб совсем скучно не было, но лишь вкратце
математики называют "полем" набор чисел, с которыми можно делать обычные операции плюс, минус, умножить, делить (кроме деления на ноль), с обычными их свойствами: от перестановки слагаемых сумма не меняется, можно раскрывать скобки, итд. итд.
например, все рациональные числа (т.е. положительные и отрицательные целые и дроби) это поле, обозначают 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, все.