Проблема представления данных

Кольцо целых чисел

Из курса программирования известно, что целое число может быть представлено в памяти компьютера разными способами, в частности, это представление зависит от того, как оно описано: как величина типа integer, или real, или string. При этом в большинстве языков программирования под целыми числами понимаются числа из весьма ограниченного диапазона: типичный случай — от -215 = -32768 до 215 - 1 = 32767. Системы компьютерной алгебры имеют дело с большими целыми числами, в частности, любая такая система умеет вычислять и выводить в десятичной записи числа вида 1000! (более тысячи знаков).

В данном курсе мы будем рассматривать представление целых чисел в символьном виде и не вдаваться в подробности, какая память отводится для записи одного символа (бит, байт или другая). Наиболее распространенным является представление целых чисел в позиционных системах счисления. Такая система определяется выбором основания счисления, например, 10. Множество десятичных целых чисел обычно описывается следующим образом:

$$\smallskip \begin{verbatim} целое число == <натуральное число>|0| -<натуральное число> натуральное число == <значащая цифра> | <значащая цифра> <цифры> значащая цифра == 1|2|3|4|5|6|7|8|9 цифры == <цифра> | <цифра> <цифры> цифра == 0 | <значащая цифра> \end{verbatim} \smallskip$$

Выписанное определение целых чисел дает однозначность представления каждого такого числа, и аналогичное определение (только, может быть, с другим основанием) используется в большинстве систем компьютерной алгебры. Пользуясь таким представлением, удобно реализовать арифметические операции над целыми числами. При этом сложение и вычитание являются относительно "дешевыми" операциями, а умножение и деление — "дорогими" . При оценке сложности арифметических операций следует учитывать как стоимость элементарной операции (одноразрядной), так и количество одноразрядных операций для выполнения какого-либо действия над многозначными числами. Сложность умножения и деления обусловлена, в первую очередь, тем, что с ростом длины числа (его записи в какой-либо системе счисления) количество элементарных операций увеличивается по квадратичному закону, в отличие от линейного для сложения и вычитания. К тому же, то, что мы обычно называем алгоритмом деления многозначных чисел, в действительности основано на переборе (часто весьма значительном) возможной очередной цифры частного, и при этом недостаточно просто воспользоваться правилами деления однозначных чисел. При большом основании системы счисления (часто оно может иметь порядок 230 ) этот способ малоэффективен.

Пусть $$A$$ — натуральное число (записанное в десятичной системе). Чтобы получить его запись $$A=\sum_{i=0}^{d_A}b_ik^i$$ в $$k$$ -ичной системе счисления, можно воспользоваться следующим алгоритмом ( $$[A/k]$$ обозначает целую часть числа $$A/k$$ ):

Дано: A—натуральное число в десятичной системе счисления
	k > 1—натуральное число
Надо: A—запись числа A в k-ичной системе счисления

Начало
i := 0
цикл пока A > 0
	bi := A (mod k)
	A := [A/k]
	i := i + 1
конец цикла
dA := i - 1
Конец

Для восстановления десятичного числа по последовательности $$b_{d_A}, b_{d_A-1},\dots,b_1,b_0$$ его k -ичной записи $$\sum_{i=0}^{d_A}b_ik^i$$ используется следующий алгоритм:

Дано: k > 1—натуральное число
	последовательность цифр, представляющих число A
	в k-ичной системе
Надо: A—запись числа A в десятичной системе счисления

Начало
A := 0
цикл пока не конец последовательности
	b := очередной элемент последовательности
	A := A * k + b
конец цикла
Конец

1.2. УПРАЖНЕНИЕ. Объясните, почему для перевода числа из десятичной системы в k -ичную используется деление, а для перевода из k -ичной системы в десятичную — умножение.

Перемножая "столбиком" два двузначных числа в десятичной системе счисления, мы выполняем следующие операции:

(10a + b)(10c + d) = 100ac + 10(ad + bc) + bd,

т. е. 4 операции умножения одноразрядных чисел, 3 операции сложения и 2 операции умножения на степень основания счисления, которые сводятся к сдвигу. При оценке сложности можно учитывать все элементарные операции, не разделяя их по весам (в данном примере мы имеем 9 элементарных операций). Задача оптимизации алгоритма сводится при данном подходе к минимизации общего числа элементарных операций. Можно, однако, считать, что умножение является более "дорогой" операцией, чем сложение, которое, в свою очередь, "дороже" сдвига. Учитывая только наиболее дорогие операции, мы получаем, что мультипликативная сложность умножения двузначных чисел "столбиком" равна 4.

В параграфе 5 рассматриваются алгоритмы вычисления наибольших общих делителей и оценивается их сложность.

Рассмотренное представление не является единственным каноническим представлением целых чисел. Как уже отмечалось, для выбора канонического представления можно воспользоваться единственностью разложения натурального числа на простые множители. Такое представление целого числа может быть применено в тех задачах, где используются только операции умножения и деления, так как они становятся очень "дешевыми" , однако несоизмеримо возрастает стоимость операций сложения и вычитания, что препятствует использованию подобного представления. В некоторых задачах отказ от канонического представления дает значительный выигрыш в быстродействии, в частности, может использоваться частичное разложение числа на множители. Особенно полезен аналогичный метод при работе не с числами, а с многочленами.

Если известно, что при работе программы все встречающиеся в вычислениях целые числа ограничены по абсолютной величине некоторой заданной константой, то можно использовать для задания таких чисел их систему вычетов по модулям некоторых взаимно простых чисел, произведение которых превосходит упомянутую константу. Вычисления с классами вычетов выполняются, как правило, быстрее, чем арифметика многократной точности. А арифметикой многократной точности при таком подходе нужно пользоваться только при вводе или выводе информации.

Отметим, что наряду с каноническими представлениями в системах компьютерной алгебры используются и другие представления. В частности, желательно, чтобы наличие или отсутствие знака '+' перед целым числом не влияло на восприятие его компьютером. Таким образом, для положительных чисел получается неоднозначное представление, хотя форма отрицательных чисел определена однозначно.

$$\begin{verbatim} <положительное целое> == <натуральное число> | + <натуральное число> <отрицательное целое> == - <натуральное число> \end{verbatim} \smallskip$$

Другое требование — на восприятие числа не должно влиять наличие нулей перед первой значащей цифрой.

1.3. УПРАЖНЕНИЯ.

Оценить количество одноразрядных умножений, используемых при умножении столбиком m -значного числа на n - значное.

Показать, что два двузначных числа можно перемножить, используя только 3 умножения однозначных чисел и увеличив число сложений.

Найти алгоритм деления длинных чисел, не требующий большого перебора при нахождении первой цифры частного.

Описать алгоритм перевода натуральных чисел из m -ичной системы счисления в n -ичную.

В римской нумерации для записи чисел используются следующие символы: I — единица, V — пять, X — десять, L — пятьдесят, C — сто, D — пятьсот, M — тысяча. Символ считается отрицательным, если правее него найдется символ большего числа, и положительным в противном случае. Например, число 1948 в этой системе запишется так: MCMXLVIII. Сформулировать алгоритм перевода числа из римской записи в десятичную и обратно. Реализовать полученный алгоритм на одном из алгоритмических языков (например, C ). Ограничения на исходные данные: 1 <= N < 3700, в записи результата ни один символ не должен появляться больше 3 раз.

Сформулировать алгоритм и написать программу сложения натуральных чисел в римской нумерации.

Будем говорить, что мы имеем дело с системой счисления со смешанным или векторным основанием, если нам задан вектор из n натуральных чисел M = (m1, . . . ,mn) (осно вание счисления) и запись K = (k0, k1, . . . , kn) обозначает число k = k0+m1(k1+m2(k2+· · ·+mn ·kn) . . . )). Написать программу, которая по данным (день недели, часы, минуты, секунды) определяет, сколько секунд прошло с начала недели (понедельник, 0, 0, 0) = 0, и выполняет обратное преобразование.

Кольца вычетов и конечные поля.

Кольца вычетов и конечные поля представляют собой наиболее простые объекты с точки зрения задачи представления данных. Каждому элементу такого кольца или поля, состоящего из n элементов, можно сопоставить, например, взаимно однозначно неотрицательное целое число из отрезка [0, n - 1]. Для колец вычетов — это сопоставление каждому классу вычетов его единственного элемента, лежащего в [0, n - 1], при этом арифметические операции над такими "числами" выполняются как операции над целыми числами по модулю n. Часто в качестве системы представителей кольца вычетов $$\mathbb Z/n \mathbb Z$$ выбирается отрезок [-(n-1)/2, (n-1)/2] при нечетном n и [-n/2+1, n/2] при четном n. Арифметические операции +, -, * реализуются очевидным образом, для реализации операции деления обычно используется расширенный алгоритм Евклида (см. 7).

Хотя элементы конечного поля из n элементов также находятся во взаимнооднозначном соответствии с целыми числами из отрезка [0, n - 1], это соответствие не является таким же естественным, в частности, арифметические операции выполняются по более сложным правилам. Чаще используются другие формы представления, например, для записи элементов простого поля из p элементов ис пользуется система вычетов по модулю p, а поле GF(pk) представляется в виде факторкольца кольца многочленов $$\mathbb Zp[x]$$ по идеалу, порожденному некоторым неприводимым по модулю p многочленом степени k.

Сформулируем основные результаты о конечных полях.

Любая конечная область целостности является полем (следует из взаимной однозначности умножения на любой ненулевой элемент).

Характеристика конечного поля является простым числом (следует из отсутствия делителей нуля).

Любое конечное поле GF(q) характеристики p состоит из q = pk элементов, где k — натуральное число (поскольку оно является векторным пространством над $$\mathbb Z/p \mathbb Z$$, k — размерность этого пространства).

Мультипликативный порядок любого ненулевого элемента поля GF(q) делит q - 1 (ненулевые элементы образуют по умножению группу порядка q - 1 ).

Мультипликативная группа поля GF(q) является циклической, т. е. существует элемент порядка q-1 (следует из однозначности разложения на множители многочленов xm-1 над любым полем).

Любые два конечных поля, содержащих одинаковое число элементов, изоморфны (следует из однозначности поля разложения для многочлена xq-1 - 1 ).

$$GF(p^k)\subset GF(p^m)\iff k|m$$

Таким образом, существует два принципиально разных подхода к построению канонического представления элементов конечного поля GF(pk):

(векторное представление) выбрать элемент x такой, что его степени x0 = 1, x, x2, . . . , xk-1 порождают наше поле как векторное пространство над простым подполем $$\mathbb Z/p \mathbb Z$$, и любой элемент записывать как вектор в этом базисе;

(степенное представление) найти примитивный элемент $$\alpha,$$ порождающий мультипликативную группу этого поля, и любой элемент поля представлять в виде степени элемента $$\alpha.$$

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

1.4. УПРАЖНЕНИЯ.

Показать, что кольцо вычетов по модулю p2 не изоморфно конечному полю из p2 элементов.

Составить таблицу умножения и деления для колец $$\mathbb Z_4$$ и $$\mathbb Z_9$$ и для полей GF(4) и GF(9).

Для заданной матрицы размера p2 x p2, где p = 2 или 3, проверить, является ли она таблицей умножения в поле GF(p2) при какой-либо нумерации элементов этого поля.

Реализовать алгоритм деления в кольце вычетов $$\mathbb Zn$$ (учесть возможность получения неоднозначного результата).

Китайская теорема об остатках. Дано k взаимно простых натуральных чисел mi > 1. Для любого набора из k целых чисел ai, 1 <= i <= k, найти $$\alpha \in \mathbb Z, \; 0\le \alpha < \prod_{i=1}^km_i$$, такое, что $$a \equiv a_{i} (mod m_{i})$$ для всех i от 1 до k.

Обобщить предыдущую задачу на случай, когда числа mi не обязательно взаимно просты.

Найти все неприводимые над полем $$\mathbb Zp$$ многочлены степени n ( n небольшое).

Найти число неприводимых над полем $$\mathbb Zp $$ многочленов степени n.

Рациональные числа.

Множество рациональных чисел $$\mathbb Q$$ определяется как фактормножество множества пар $$(a, b) \in$$ $$\mathbb Z$$ x $$\mathbb Z$$, $$b \ne 0$$, по отношению эквивалентности: $$(a,b)\sim (c,d) \iff ad - bc = 0$$. Если у нас фиксирована каноническая форма целого числа, то каноническую форму рационального числа мы можем получить, например, выбирая из эквивалентных пар целых чисел (a, b) такую, у которой b > 0 и НОД(a, b) = 1. Все сказанное выше о представлении целых чисел относится и к представлению рациональных чисел.

Естественно, приведенная выше каноническая форма рационального числа не является единственно возможной. Из школьного курса известно, что любое рациональное число можно представить в виде бесконечной десятичной периодической дроби. Также известно, что любая бесконечная периодическая дробь представляет рациональное число, причем соответствие между рациональными дробями и бесконечными десятичными периодическими дробями не является взаимно однозначным: рациональные числа, знаменатели которых имеют вид 2n5m, могут быть представлены периодическими дробями с периодами (0) и (9).

1.5. УПРАЖНЕНИЯ. Пусть m — натуральное число, m > 1, рассматриваемое как основание системы счисления.

Доказать, что рациональные числа могут быть представлены бесконечными периодическими m -ичными дробями, причем неоднозначно.

Доказать, что любая бесконечная периодическая m -ичная дробь представляет некоторое рациональное число.

Установить взаимнооднозначное соответствие между множеством рациональных дробей и некоторым подмножеством бесконечных периодических m -ичных дробей.

Написать программу перевода рациональных чисел в бесконечные периодические m -ичные дроби и обратно.

Часто рациональные числа представляют в виде суммы целого числа и правильной дроби, т. е. положительного рационального числа $$0 < \alpha < 1$$. Исследователи утверждают, что в древнем Египте имелись обозначения только для дробей с числителем 1, остальные числа представлялись в виде суммы таких дробей.

1.6. УПРАЖНЕНИЯ.

Доказать, что любое положительное рациональное число $$0 < \alpha < 1$$ можно представить в виде суммы обратных величин различных натуральных чисел.

Показать, что такое представление не единственно.

Описать алгоритм, выбирающий из всех возможных представлений такого вида единственное.

Написать программу, представляющую любое положительное рациональное число $$0 < \alpha < 1$$ в виде суммы обратных величин различных натуральных чисел.

Приближенные вычисления.

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

Когда мы говорим о приближенных вычислениях, то подразумеваем, что определено понятие cходимости. Из курса математического анализа известно, что поле вещественных чисел $$\mathbb R$$ можно определить как пополнение поля рациональных чисел $$\mathbb Q$$ по архимедовой метрике, когда расстояние между двумя рациональными числами определяется как модуль их разности. В математике, в частности, в теории чисел, рассматриваются также другие метрики поля рациональных чисел, так называемые p -адические. При пополнении поля $$\mathbb Q$$ по p -адической метрике получается поле p -адических чисел. Некоторые сведения о таких полях приведены в лекциях 2, 3.

При вычислениях с вещественными числами мы, в действительности, имеем дело обычно с их приближенными значениями, которые представляют собой десятичные (или двоичные, при использовании компьютера) дроби с фиксированным числом значащих цифр. При работе с приближенными значениями p -адических чисел получаются объекты, которые известны как коды Гензеля. Их описание можно найти в специальной литературе, например, .

1.7. УПРАЖНЕНИЯ.

Привести пример аксиомы поля вещественных чисел, не выполняющейся при работе с числами типа float на языке Си.

Какие аксиомы поля вещественных чисел не выполняются при работе с числами типа float на языке Си?

Привести пример аксиомы поля вещественных чисел, не выполняющейся для интервальной арифметики.

Какие аксиомы поля вещественных чисел не выполняются для интервальной арифметики?

Алгебраические числа.

1.8. ОПРЕДЕЛЕНИЕ. Алгебраическим числом называется число $$\alpha$$, являющееся корнем многочлена от одной переменной с целыми коэффициентами. Если старший коэффициент этого многочлена равен 1, то алгебраическое число называется целым.

1.9. ПРЕДЛОЖЕНИЕ. Существуют алгебраические числа, не выражающиеся через радикалы.

Доказательство этого утверждения основано на теории Галуа и может быть найдено в учебниках по алгебре.

Таким образом, в поле алгебраических чисел можно выделить подполя алгебраических чисел, порожденных простыми радикала ми ( простые радикальные расширения ) и вложенными радикалами ( вложенные радикальные расширения ), а также соответствующие подкольца в кольце целых алгебраических чисел.

Представление алгебраических чисел представляет собой значительно более трудную задачу. Если речь идет об одном алгебраическом числе, то для его задания нужно знать минимальный многочлен, корнем которого является данное число. В большинстве алгебраических задач несущественно различие между различными корнями одного и того же неприводимого многочлена. Однако в задачах, где используются различные метрические свойства, часто приходится для задания алгебраического числа указывать не только соответствующий неприводимый многочлен, но и интервал на вещественной оси или область в комплексном пространстве, содержащую единственный корень указанного многочлена. При этом арифметические операции над алгебраическими числами оказываются очень трудоемкими. Нахождение минимального многочлена для суммы или произведения алгебраических чисел представляет собой нетривиальную задачу, методы его нахождения будут описаны ниже, при изучении базисов Гребнера.

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

1.10. УПРАЖНЕНИЯ.

Показать, что $$\sqrt2$$, $$\sqrt3+\sqrt2$$, $$\sqrt{2+\sqrt5}$$ — целые алгебраические числа.

Показать, что целые алгебраические числа образуют кольцо.

Показать, что алгебраические числа образуют поле.

Найти минимальный многочлен над $$\mathbb Q$$ для $$\sqrt2+\sqrt3$$.

Построить каноническое представление для элементов поля $$\mathbb Q(\sqrt2,\sqrt3,\sqrt5)$$.

Построить алгоритм получения канонического представления для простых радикальных расширений (полей алгебраических чисел, порожденных несколькими радикалами без вложений).

Построить алгоритм получения канонического представления для вложенных радикальных расширений.

Трансцендентные числа.

Большинство систем компьютерной алгебры допускает работу с трансцендентными числами e и $$\pi,$$ для которых фиксированы соответствующие свойства тригонометрических, логарифмических и показательных функций. Вычисления в трансцендентных расширениях производятся так же, как в полях рациональных функций. Задание конкретного трансцендентного числа какими-либо метрическими или функциональными свойствами и проверка его алгебраической независимости с уже имеющимися величинами представляет собой алгоритмически неразрешимую задачу.

Целые p-адические числа.

p -адические числа играют значительную роль в теории чисел, и для более подробного знакомства с ними читателю следует обратиться к литературе по теории чисел, например к книге . Здесь мы только приведем основные определения и некоторые свойства p -адических чисел.

2.1. ОПРЕДЕЛЕНИЕ. Пусть p — некоторое простое число. Последовательность целых чисел

{xn} = {x0, x1, . . . , xn, . . . },

обладающая тем свойством, что

$$\begin{equation}\label{BSh4} x_n\equiv x_{n-1}\pmod{p^n} \end{equation}$$

для всех n >= 1, определяет новый объект, называемый целым p - адическим числом. Две последовательности {xn} и $$\{x'_n\}$$ тогда и только тогда определяют одно и то же целое p -адическое число, когда $$x_n\equiv x'_n\pmod{p^{n+1}}$$ для всех n >= 0.

В отличие от целых p -адических чисел, обычные целые числа часто называют целыми рациональными.

Каждому целому рациональному числу x можно сопоставить целое p -адическое число, определяемое последовательностью

{x, x, . . . , x, . . . }.

Это p -адическое число будем обозначать той же буквой x. Множество целых p -адических чисел будем обозначать Op.

Укажем способ, при помощи которого из всех последовательностей, определяющих одно и то же p -адическое число, можно выбрать одну стандартную.

Пусть {xn} — целое p -адическое число. Обозначим через $$\bar x_n$$ наименьшее неотрицательное число, сравнимое с xn по модулю pn+1, т. е.

$$x_n\equiv \bar x_n\pmod{p^{n+1}}, \quad$$ $$0\le\bar x_n<p^{n+1}.\quad \quad \quad \quad$$

Для любого целого p -адического числа {xn}, последовательность, все члены которой удовлетворяют условиям (2.2) и (2.3), будем называть канонической.

Ставя в соответствие каждому целому p -адическому числу его каноническую последовательность, мы получаем взаимно однозначное соответствие между множеством целых p -адических чисел и множеством последовательностей вида

{a0, a0 + a1p, a0 + a1p + a2p2, . . . , },

где 0 <= ai < p.

2.2. ОПРЕДЕЛЕНИЕ. Суммой и произведением целых p -адических чисел $$\alpha$$ и $$\beta,$$ определяемых последовательностями {xn} и {yn}, называются целые p -адические числа, определяемые соответственно последовательностями {xn + yn} и {xnyn}.

2.3. УПРАЖНЕНИЕ. Показать, что введенные выше операции определены корректно и превращают Op в коммутативное кольцо с единицей.

Сформулируем несколько теорем, доказательство которых оставляется читателю в качестве упражнения (их можно найти, например, в ).

2.4. ТЕОРЕМА. Целое p -адическое число $$\alpha,$$ определяемое последовательностью {x0, x1, . . . , xn, . . . }, тогда и только тогда является единицей (т. е. обратимым) в Op, когда $$x_0\not\equiv 0\pmod p$$.

2.5. ТЕОРЕМА. Всякое отличное от нуля целое p -адическое число $$\alpha$$ однозначно представляется в виде

$$\begin{equation}\label{BSh8} \alpha=p^m\varepsilon, \end{equation}$$

где $$\varepsilon$$ — единица кольца Op.

2.6. ТЕОРЕМА. Для любого натурального n, всякое целое p -адическое число сравнимо с целым рациональным числом по модулю pn. Два целых рациональных числа тогда и только тогда сравнимы по модулю pn в кольце Op, когда они сравнимы по этому модулю в кольце $$\mathbb Z$$.

2.7. ОПРЕДЕЛЕНИЕ. Число m в представлении (2.4) отличного от нуля целого p -адического числа $$\alpha$$ называется p -показателем числа $$\alpha$$ и обозначается $$\nu p(\alpha )$$.

Индекс p в определении показателя мы будем часто опускать и говорить просто о показателе, обозначая его $$\nu (\alpha )$$. Доопределим показатель, полагая $$\nu (0) = \infty$$. Непосредственно проверяется, что

$$\nu(\alpha\beta)=\nu(\alpha)+\nu(\beta),$$ $$\nu(\alpha+\beta)\ge\min(\nu(\alpha),\nu(\beta)),$$ $$\nu(\alpha+\beta)=\min(\nu(\alpha),\nu(\beta)),\quad\text{если}\quad \nu(\alpha)\ne\nu(\beta).$$

Дробные p-адические числа.

ОПРЕДЕЛЕНИЕ. Дробь вида $$\frac\alpha{p^k}$$, $$\alpha\in O_p$$, k >= 0 определяет дробное p -адическое число или просто p -адическое число. Две дроби, $$\frac\alpha{p^k}$$ и $$\frac\beta{p^m}$$, определяют одно и тоже p -адическое число, если $$\alpha p^m=\beta p^k$$ в $$O_p$$.

Совокупность всех p -адических чисел обозначается Rp. Легко проверить, что операции сложения и умножения продолжаются с Op на Rp и превращают Rp в поле.

2.9. ТЕОРЕМА. Всякое p -адическое число $$\xi \ne 0$$ единственным образом представляется в виде

$$\xi=p^m \varepsilon,$$

где m — целое число, а $$\varepsilon$$ — единица кольца Op.

2.10. ТЕОРЕМА. Всякое отличное от нуля p -адическое число $$\xi$$ однозначно представляется в виде

$$\xi=p^m(a_0+a_1p+\dots+a_np^n+\dots),$$

где $$m=\nu_p(\xi), \; 1\le a_0\le p-1, \; 0\le a_n\le p-1 \; (n=1,2,\dots)$$.

Аксиоматическая характеристика поля p-адических чисел.

Выбрав некоторое вещественное число $$\rho,$$ такое, что $$0 < \rho < 1$$, (например, $$\rho = 1/p$$ ) положим

$$\begin{equation} \phi_p(\xi)=\begin{cases} \rho^{\nu_p(\xi)} \text{при } \xi\ne0, \\ 0 \text{при }\xi=0.\end{cases} \end{equation}$$

ОПРЕДЕЛЕНИЕ. Функция $$\phi_p(\xi)$$, $$\xi\in R_p$$, определенная условиями (2.10), называется $$p$$ - адической метрикой . Значение $$\phi_p(\xi)$$ называется величиной $$p$$ - адического числа $$\xi$$ в этой метрике.

Как и в случае показателя, функцию $$\varphi _{p}$$ иногда будем называть просто метрикой и обозначать $$\phi.$$

Легко проверяется, что p -адическая метрика обладает следующими свойствами:

$$\phi(\xi\eta)=\phi(\xi)\phi(\eta),$$ $$\phi(\xi+\eta)\le\max(\phi(\xi),\phi(\eta)),$$ $$\phi(\xi+\eta)\le \phi(\xi)+\phi(\eta).$$

Свойства (2.11) и (2.13) указывают, что введенное понятие является аналогом абсолютной величины в поле вещественных чисел.

2.12. ОПРЕДЕЛЕНИЕ. Пусть k — произвольное поле. Функция $$\phi,$$ определенная на элементах $$\alpha$$ поля k и принимающая вещественные значения $$\varphi (\alpha )$$, называется метрикой поля k, если она обладает следующими свойствами:

$$\phi(\alpha)>0$$ при $$\alpha\ne0$$ ; $$\phi(0)=0$$ ;

$$\phi(\alpha+\beta)\le\phi(\alpha)+\phi(\beta)$$ ;

$$\phi(\alpha\beta)=\phi(\alpha)\phi(\beta)$$.

Поле k вместе с заданной в нем метрикой $$\phi$$ называется метризованным полем.

Из определения легко вытекают следующие свойства метрик:

$$\begin{align*} \phi(\pm1)=1;\\ \phi(-\alpha)=\phi(\alpha);\\ \phi(\alpha-\beta)\le\phi(\alpha)+\phi(\beta);\\ \phi(\alpha\pm\beta)\ge|\phi(\alpha)-\phi(\beta)|;\\ \phi\genfrac(){}{}\alpha\beta=\frac{\phi(\alpha)}{\phi(\beta)}\quad (\beta\ne0). \end{align*}$$

Метриками являются:

абсолютная величина в поле рациональных чисел;

абсолютная величина в поле вещественных чисел;

модуль в поле комплексных чисел;

$$p$$ - адическая метрика $$\phi_p$$ в поле $$p$$ - адических чисел $$R_p$$ ;

функция $$\phi(\alpha)$$, определенная в произвольном поле $$k$$ условиями: $$\phi(0)=0$$, $$\phi(\alpha)=1$$ при $$\alpha\ne0$$. Такая метрика называется тривиальной.

Если метрику $$\phi_p$$ поля $$R_p$$ мы рассматриваем лишь на рациональных числах, то получаем некоторую новую метрику поля рациональных чисел $$\Q$$. Эта метрика, обозначаемая также через $$\phi_p$$, называется $$p$$ - адической метрикой поля $$\Q$$.

Аксиоматически поля вещественных и $$p$$ -адических чисел можно определить следующим образом.

Поле вещественных чисел $$\R$$ — это пополнение поля рациональных чисел $$\mathbb Q$$ по метрике 1.

Поле $$p$$ - адических чисел $$R_p$$ — это пополнение поля рациональных чисел $$\mathbb Q$$ по $$p$$ - адической метрике.

2.14. УПРАЖНЕНИЕ. Представить число -1 в поле p -адических чисел в виде ряда (2.9).

2.15. УПРАЖНЕНИЕ. Представить число $$-\frac23$$ в поле 5-адических чисел в виде ряда (2.9).

2.16. УПРАЖНЕНИЕ. Доказать для многочленов над полем p -адических чисел признак неприводимости Эйзенштейна: многочлен f(x) = a0xn + a1xn-1 + · · · + an с целыми p -адическими коэффициентами неприводим над полем Rp, если a0 не делится на p, все остальные коэффициенты a1, . . . , an делятся на p и свободный член an, делясь на p, не делится на p2.

Многочлены

Действия с многочленами лежат в основе любой системы компьютерной алгебры. Пусть K — некоторое кольцо, задача представления элементов которого уже решена. Представление элементов кольца многочленов K[x] можно выбирать различными способами. Наиболее распространенным является представление многочлена в виде последовательности коэффициентов, упорядоченной по возрастанию или убыванию степеней одночленов. Представление многочленов, при котором запоминаются все коэффициенты, включая нулевые, называется плотным. Плотное представление используется в задачах, где рассматриваемые многочлены имеют сравнительно небольшое количество нулевых коэффициентов. Если степени многочленов достаточно высоки, а количество ненулевых коэффициентов мало ( разреженные многочлены ), то удобнее использовать разреженное представление многочленов, в котором указываются только ненулевые коэффициенты и соответствующие степени одночленов. При этом алгоритмы работы с такой формой записи становятся более сложными, но значительно экономится память ЭВМ, а во многих случаях—и время работы программы.

Приведенная выше форма представления многочленов в случае, когда кольцо коэффициентов является полем, основана на том факте, что одночлены составляют базис кольца многочленов, рассматриваемого как бесконечномерное векторное пространство над полем коэффициентов. В некоторых случаях целесообразно использовать другие базисы этого пространства. Например, в лекции 4 изучаются многочлены вида $$\binom{x+k}k=\frac{(x+k)(x+k-1)\dots(x+1)}{k!},$$ обладающие многими полезными свойствами. Часто оказывается полезным представление многочленов фиксированной степени набором значений в разных точках.

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

лексикографическое упорядочение мономов, получающееся из фиксированного порядка на множестве переменных;

упорядочение мономов по степеням, а мономы одной и той же степени упорядочиваются лексикографически;

упорядочение мономов по степеням, а мономы одной и той же степени упорядочиваются в обратном лексикографическом порядке, т. е. при равенстве степеней большим считается вектор с меньшей последней координатой, при равенстве последних координат — с меньшей предпоследней и т. д. Может показаться, что этот порядок совпадает с предыдущим, для "отраженных" векторов. При n = 2 это действительно так, однако в общем случае эти два отношения порядка различаются более существенно, что продемонстрировано в примере 3.1б), где предполагается, что x > y > z

Более подробно вопросы, связанные с упорядочением мономов и каноническим представлением многочленов от нескольких переменных, будут рассмотрены ниже в разделе, посвященном базисам Гребнера.

3.1. ПРИМЕРЫ.

Пусть переменные x и y упорядочены так, что x > y. Тогда многочлен (x + y)2 + x + y + 1 с учетом соответствующих порядков записывается в виде:

$$x^2+2xy+x+y^2+y+1$$ (лексикографический порядок);

$$x^2+2xy+y^2+x+y+1$$ (по степени, затем лексикографический);

$$y^2+2xy+x^2+y+x+1$$ (по степени, затем обратный лексикографический).

Рассмотрим разложение многочлена (x+y+z)3. Из однородности многочлена следует, что первые два из рассматриваемых порядков для этого многочлена совпадают. Выпишем его представление с использованием второго и третьего порядка.

$$x^3+3x^2y+3x^2z+3xy^2+6xyz+3xz^2+y^3+3y^2z+3yz^2+z^3$$ и

$$x^3+3x^2y+3xy^2+y^3+3x^2z+6xyz+3y^2z+3xz^2+3yz^2+z^3$$ соответственно.

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

Отметим, что достаточно часто при действии с многочленами предпочтительнее пользоваться представлениями, отличными от канонического. Например, во многих отношениях запись (x + y + z)3 более удобна, чем приведенные выше разложения этого многочлена. В частности, для многочленов задача разложения на множители представляет еще большую сложность, чем для целых чисел, и поэтому не всегда целесообразно раскрывать при умножении скобки,- часто бывает полезным в ущерб каноничности записи хранить многочлен в виде произведения.

Рациональные функции.

Поле рациональных функций K(x1, . . . , xn), где K - некоторое поле, обычно определяется как поле частных кольца многочленов K[x1, . . . , xn]. Имея каноническое представление элементов кольца многочленов, каноническое представление рациональных функций можно получить наложением условия взаимной простоты числителя и знаменателя и нормировкой знаменателя (например, приравниванием старшего коэффициента знаменателя единице). Часто, однако, поле K само представляется как поле частных некоторой области целостности, например, поле $$\mathbb Q(x)$$ можно представить как поле частных кольца $$\mathbb Q[x]$$, а также как поле частных кольца $$\mathbb Z[x]$$. При представлении поля $$\mathbb Q(x)$$ как поля частных кольца $$\mathbb Z[x]$$ далеко не всегда можно в представлении рациональной функции приравнять старший коэффициент знаменателя единице. Множество обратимых элементов в Z состоит всего из двух элементов ( 1 и -1 ), и нормировку знаменателя можно осуществить, фиксируя знак старшего коэффициента.

Обобщенные многочлены и рациональные функции.

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

В этом параграфе приводятся основные определения и результаты из дифференциальной и разностной алгебры, которые понадобятся нам в дальнейшем.

3.2. ОПРЕДЕЛЕНИЕ. Оператор $$\delta,$$ действующий на некотором кольце, называется оператором дифференцирования (или просто дифференцированием), если $$\delta (a + b) = \delta a + \delta b$$ и $$\delta (ab) = (\delta a)b + a\delta b$$ для всех элементов a, b этого кольца. Дифференциальным кольцом называется коммутативное кольцо R с конечным множеством $$\Delta = \{ \delta _{1}, . . . , \delta _{n}\}$$ операторов дифференцирования кольца R, таких, что $$\delta \delta 'a = \delta '\delta a (a \in R, \delta \in \Delta , \delta ' \in \Delta )$$ ; если n = 1, то дифференциальное кольцо R называется обыкновенным, если n > 1, то R называется кольцом с частными производными. Если кольцо R является полем, то мы говорим о дифференциальном поле.

Показать, что любое кольцо можно рассматривать как дифференциальное кольцо с нулевым дифференцированием. Показать, что на кольцах $$\mathbb Z$$, $$\mathbb Q$$, $$\mathbb Z/m \mathbb Z$$ нет ненулевых дифференцирований.

Кольцо многочленов R[x] от одной переменной над обыкновенным дифференциальным кольцом можно превратить в обыкновенное дифференциальное кольцо, произвольным образом задав значение $$\delta x$$. Показать, что значением $$\delta x$$ продолжение дифференцирования $$\delta$$ на кольцо R[x] определяется однозначно. Аналогичное утверждение верно для кольца формальных степенных рядов.

Пусть R — дифференциальное кольцо без делителей нуля, F — его поле частных. Показать, что F можно единственным образом превратить в дифференциальное поле, содержащее дифференциальное кольцо R.

Поле мероморфных в некоторой области вещественного n - мерного пространства функций можно рассматривать как дифференциальное поле, с множеством дифференцирований $$\Delta=\{\partial/\partial x_i\}$$

ОПРЕДЕЛЕНИЕ. Пусть R — дифференциальное кольцо с множеством операторов дифференцирования $$\Delta.$$ Под дифференциальным модулем над R или дифференциальным R -модулем мы понимаем R -модуль M, на котором действуют операторы множества $$\Delta$$ в соответствии со следующими правилами:

$$\delta(u+v)=\delta u+\delta v,\qquad \delta(au)=(\delta a)u+a\delta u, \\ (\delta\in\Delta,\quad u\in M,\quad v\in M,\quad a\in R).$$

Дифференциальный модуль можно рассматривать как левый модуль над кольцом косых многочленов $$R[\Delta]=R[\delta_1,\dots,\delta_n]$$ дифференциального типа. Это кольцо мы будем называть кольцом линейных дифференциальных операторов. Пусть T обозначает свободную коммутативную полугруппу (записанную мультипликативно), порожденную элементами из множества $$\Delta.$$ Каждый элемент кольца $$R[\Delta ]$$ может быть единственным способом выражен в виде конечной суммы

$$\sum_{\theta\in T}a_\theta\theta=\sum_{i_1,\dots,i_n}a_{i_1,\dots,i_n}\delta_1^{i_1}\delta_2^{i_2}\dots\delta_n^{i_n},$$

умножение образующих определяется правилами:

$$\delta_i\delta_j =\delta_j\delta_i,\quad \delta_ia=a\delta_i+\delta_i(a), \quad \text{где}\quad \delta_i,\delta_j\in\Delta,\ a\in R,$$

В предположении, что для кольца коэффициентов R каноническое представление фиксировано, каноническое представление кольца дифференциальных операторов $$R[\Delta ]$$ получается так же, как и для кольца многочленов: достаточно упорядочить полугруппу T. Обычно рассматриваются отношения порядка, перечисленные в параграфе 3.1.

3.5. ПРИМЕР. Пусть R — кольцо многочленов над полем K, R = K[x1, . . . , xm], и $$\Delta=\{d_1,\dots,d_m\}= \{\partial/\partial x_1,\dots,\partial/\partial x_m\}$$. Тогда кольцо линейных дифференциальных операторов $$R[\Delta ]$$ называется алгеброй Вейля над K и обозначается Am(K).

Кольцо линейных дифференциальных операторов обладает многими свойствами, аналогичными свойствам кольца многочленов, в частности, если кольцо коэффициентов является дифференциальным полем, то в кольце дифференциальных операторов нет делителей нуля, для любых двух элементов существует наибольший общий делитель (правый или левый, причем в общем случае они не совпадают) и наименьшее общее кратное (правое и левое, снова не совпадающие); если $$F — \delta$$ -поле, то в $$F[\delta ]$$ имеется алгоритм Евклида для нахождения левого (правого) наибольшего общего делителя.

3.6. УПРАЖНЕНИЯ. Пусть F — обыкновенное дифференциальное поле с дифференцированием $$\delta.$$ Доказать следующие свойства кольца $$R = F[\delta ]$$ линейных дифференциальных операторов над F:

в R нет делителей нуля;

R является кольцом главных левых (правых) идеалов;

в R нет нетривиальных двусторонних идеалов;

в R имеется алгоритм Евклида для нахождения левого (правого) НОД двух операторов;

в R имеется расширенный алгоритм Евклида для нахождения левого (правого) НОД двух операторов;

R не обязательно является кольцом с однозначным разложением на множители (привести пример дифференциального поля F, для которого это свойство не выполняется).

Кольцо $$R[\Delta ]$$ иногда называют кольцом дифференциальных многочленов, но мы будем придерживаться терминологии, принятой в монографии , где кольцом дифференциальных многочленов над дифференциальным кольцом R называется кольцо R{y1, . . . , yr} многочленов от счетного множества переменных $$\{\theta y_j\colon \theta\in T,\ 1\le j\le r\}$$ над кольцом R. В кольце R{y1, . . . , yr} операторы дифференцирования из множества $$\Delta$$ действуют на коэффициентах по определению дифференциального кольца, а на образующих $$\theta y$$ —по правилу: $$\delta(\theta y_j) =(\delta\theta)y_j$$.

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

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

3.7. ОПРЕДЕЛЕНИЕ. Разностное кольцо определяется как кольцо R с фиксированным конечным множеством $$\smu{1} \Delta= \{\tau_1,\dots,\tau_n\}$$ взаимно коммутирующих мономорфизмов кольца R в себя. Если все мономорфизмы $$\tau _{i}$$ — изоморфизмы, то R называется инверсным разностным кольцом. Если n = 1, то R называется обыкновенным разностным кольцом, в противном случае R называется кольцом с частными разностями. Элементы множества $$\Delta$$ называются операторами трансляции.

3.8. УПРАЖНЕНИЯ.

Любое кольцо можно рассматривать как разностное кольцо с тождественным изоморфизмом.

Кольцо многочленов R[x] от одной переменной над обыкновенным разностным кольцом можно превратить в обыкновенное разностное кольцо, произвольным образом задав значение $$\tau (x)$$. Показать, что значением $$\tau (x)$$ трансляция кольца R[x] определяется однозначно.

Показать, что не любой автоморфизм $$\tau$$ кольца R[x] продолжается на кольцо формальных степенных рядов.

Пусть R - разностное кольцо без делителей нуля, F - его поле частных. Показать, что F можно единственным образом превратить в разностное поле, содержащее разностное кольцо R.

Поле формальных (сходящихся) рядов Лорана K((x)) можно рассматривать как обыкновенное разностное поле с оператором трансляции $$\tau,$$ таким, что $$\tau (x) = k \cdot x$$, где k — произвольный ненулевой элемент поля K.

3.9. ОПРЕДЕЛЕНИЕ. Пусть R — разностное кольцо с множеством операторов трансляции $$\Delta.$$ Под разностным модулем над R, или разностным R - модулем, мы понимаем R -модуль M, на котором действуют операторы из множества $$\Delta$$ в соответствии со следующими условиями

$$\tau(u+v)=\tau u+\tau v,\qquad \tau(au)=(\tau a)\tau u,\\ (\tau\in\Delta,\quad u\in M,\quad v\in M,\quad a\in R).$$

Разностный модуль M можно рассматривать как левый модуль над кольцом косых многочленов $$R[\Delta] = R[\tau_1,\dots,\tau_n]$$ разностного типа. Это кольцо мы будем называть кольцом разностных операторов. Пусть T — свободная коммутативная полугруппа (записываемая мультипликативно), порожденная элементами множества $$\Delta.$$ Каждый элемент кольца $$R[\Delta ]$$ может быть единственным образом записан в виде конечной суммы

$$\sum_{\theta\in T}a_\theta\theta=\sum_{i_1,\dots,i_n}a_{i_1,\dots,i_n}\tau_1^{i_1}\tau_2^{i_2}\dots\tau_n^{i_n},$$

умножение образующих задается соотношениями

$$\tau_i\tau_j =\tau_j\tau_i,\quad \tau_ia=\tau_i(a)\tau_i,\quad \text{где}\quad \tau_i,\tau_j\in\Delta,\ a\in R,$$

и по линейности распространяется на все кольцо $$R[\Delta ]$$. Это кольцо иногда называют кольцом разностных многочленов, но мы будем придерживаться терминологии, принятой в монографии , где кольцом разностных многочленов над разностным кольцом R называют разностное кольцо $$R\{y_1,\dots,y_r\}$$ многочленов от счетного множества неизвестных $$\{\theta y_j\colon \theta\in T,\ 1\le j\le r\}$$ над R. В кольце $$R\{y_1,\dots,y_r\}$$ операторы трансляции из множества $$\Delta$$ действуют на коэффициентах по определению разностного кольца, а на образующих $$\theta y_j$$ — по правилу: $$\tau(\theta y_j) =(\tau\theta)y_j.$$

3.10. УПРАЖНЕНИЯ. Пусть F — обыкновенное разностное поле с автоморфизмом $$\tau.$$ Доказать следующие свойства кольца $$R = F[\tau ]$$ линейных разностных операторов над F:

в R нет делителей нуля;

R является кольцом главных левых (правых, двусторонних) идеалов;

в R нет нетривиальных двусторонних идеалов;

в R имеется алгоритм Евклида для нахождения левого (правого) НОД двух операторов;

в R имеется алгоритм Евклида для нахождения левого (правого) НОД двух операторов;

R не обязательно является кольцом с однозначным разложением на множители (привести пример разностного поля F, для которого это свойство не выполняется).

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

Векторные пространства и модули.

В вычислительной математике и в алгебре понятие векторного пространства над некоторым полем K играет ключевую роль. При фиксированном базисе пространства задача представления данных не представляет какой-либо сложности — два вектора совпадают тогда и только тогда, когда совпадают все их координаты в фиксированном базисе. Соответствующая структура данных — вектор элементов типа K с индексом 1..n — является одной из базисных структур данных в программировании. Для случая, когда коэффициенты образуют кольцо R, не являющееся полем, положение существенно сложнее — аналогом понятия векторного пространства (множество, замкнутое относительно сложения, вычитания и умножения на элементы кольца с естественными аксиомами сложения и умножения) является в этом случае понятие модуля. Важным частным случаем модуля является свободный модуль над кольцом R ( R -модуль). В частности, любое кольцо с единицей можно рассматривать как свободный модуль над самим собой, любой идеал кольца является его подмодулем. С точки зрения задачи представления данных соответствующая структура данных такж может быть при фиксированном базисе описана как вектор элементов типа R с индексом 1..n.

С другой стороны, свободный модуль над алгеброй обобщенных многочленов можно рассматривать как бесконечномерное векторное пространство над основным полем. В качестве базиса этого пространства удобно выбрать всевозможные произведения мономов из кольца обобщенных многочленов на модульные образующие. Любой элемент модуля содержится в некотором конечномерном подпространстве, порожденном каким-то подмножеством базисных векторов. Выбор базисных векторов и отношения порядка на множестве базисных векторов определяет каноническую форму любого элемента свободного модуля над кольцом обобщенных многочленов.

К сожалению, множество свободных модулей незамкнуто относительно модульных гомоморфизмов, т. е. как подмодули, так и фактормодули свободного модуля не обязаны быть свободными модулями.

3.11. УПРАЖНЕНИЯ.

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

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