Читать онлайн «Кибернетический сборник. Новая серия. Выпуск 03»

Кибернетический сборник НОВАЯ СЕРИЯ ВЫПУСК 3 Сборник; переводов Под редакцией А. А. ЛЯПУНОВА И О. Б. ЛУПАНОВА ИЗДАТЕЛЬСТВО «МИР» Москва 1966 Научный совет по кибернетике УДК 519. 05 Академии наук СССР Третий выпуск новой серии кибернетических сборников состоит из двух разделов: математические вопросы и математическая лингвистика. Первый из них открывается работой А. Альберта по теории конечных полей — важ- важному разделу алгебры, находящему широкое применение в теории кодирова- кодирования. Теория кодирования представлена статьями известных специалистов — Р. Галлагера и В. Истмена. Остальные статьи этого раздела посвящены тео- теории автоматов и теории оптимальных процессов. Раздел «Математическая лингвистика» включает работу Н. Хомского и М. Шютценберже по алгебраи- алгебраической теории контекстно-свободных языков. Сборник рассчитан на научных работников, инженеров, аспирантов и студентов различных специальностей, занимающихся и интересующихся ки- кибернетикой в ее математическом аспекте, Редакция литературы по математическим наукам Математические вопросы Конечные поля !) А. А. Ал ьберт 1. Число элементов. Поле, состоящее из конечного числа эле- элементов, называется конечным полем. Конечное поле, состоящее из ц элементов, будем обозначать символом Рд. Единичный элемент поля Р порождает подполе поля Р, ко- которое называется простым подполем. Простое подполе конеч- конечного поля Ря с необходимостью само конечно и представляет собой поле Р A) т. е. фактор-кольцо кольца К целых чисел по модулю (р), где р — характеристика поля Ря и (р) означает главный идеал, порожденный простым числом р. Как известно, элементы поля /?р можно представить целыми числами О, 1, ... , р—1, B) где каждое число а представляет класс вычетов а+(р), со- состоящий из всех целых чисел вида <х + Хр. Напомним, что для каждого а6 Яр справедливо свойство Ферма = а, C) так как множество Яр всех ненулевых элементов поля Яр является группой порядка р — 1. Каждое конечное поле К = РЯ есть векторное пространство над его простым подполем Яр. Так как К конечно, то и его размерность п над /?р конечна. Отсюда К^и^р+1... +ипКр, D) т. е. каждый элемент к 6 К единственным образом представим в виде пип, E) А1Ь е г 1 А. А. , Рипс1атеп1а1 сопсер1з о! Ы&Нег а!деЬга, СЬ. . V, 1956. А. А. Альберт где ^1, ... , 5п€ Нр. Так как &,... , ^п независимо друг от друга пробегают значения ряда B), то к принимает рп значений. Та- Таким образом, доказана Теорема 1. Конечное поле К состоит из ц=рп элементов, где р есть характеристика поля К, а п — степень поля К над /?р. 2. Существование и единственность. Ненулевые элементы любого поля К образуют мультипликативную группу /С*. Если К = РЯ, то группа /С* имеет порядок т = <7—1, и так как поря- порядок подгруппы является делителем порядка группы, то каждый элемент группы К* удовлетворяет уравнению хх=*1. Но в та- таком случае справедлива Теорема 2. Каждый элемент поля Ря является корнем уравнения F) Докажем теперь существование и единственность поля Ря. Теорема 3. Поле К разложения уравнения F) над Яр есть конечное поле, состоящее из д=рп элементов. Каждое поле Ря изоморфно полю К.