Министерство образования и науки РФ
Государственное образовательное учреждение высшего профессионального образования
Вятский государственный гуманитарный университет
Физико-математический факультет
Кафедра высшей математики
Выпускная квалификационная работа
Строение идеалов полукольца натуральных чисел
Выполнила студентка V курса
физико-математического факультета
Вахрушева Ольга Валерьевна
Научный руководитель: д.ф-м.н., профессор кафедры высшей математики Чермных В. В. Рецензент: д.ф-м.н., профессор, заведующий кафедрой высшей математики Вечтомов Е.М.
Киров 2010
Содержание
Введение
Глава 1. Структура идеалов в
1.1 Базовые понятия и факты
1.2 Описание идеалов в
Глава 2. Константа Фробениуса
Библиографический список
Приложение 1. Примеры работы программы "FindC" для различных исходных данных
Приложение 2. Описание алгоритма работы программы с помощью блок-схем
Приложение 3. Полный текст программы "FindC"
Введение
Теория полуколец – один из интенсивно развивающихся разделов общей алгебры, являющийся обобщением теории колец. Весомый вклад в ее изучение и развитие внесли Е.М. Вечтомов и В.В. Чермных. Большой интерес для изучения представляет собой полукольцо натуральных чисел с обычными операциями сложения и умножения. Его роль в теории полуколец примерно такая же, как и кольца целых чисел в теории колец. Вопросу строения полукольца натуральных чисел посвящена глава в книге В.В. Чермных "Полукольца" [6].
Целью данной квалификационной работы является исследование полукольца натуральных чисел и его строения. Более точно выясняется вопрос, как устроены идеалы этого полукольца, а также осуществляется отыскание либо определение границ расположения константы Фробениуса для некоторых идеалов.
Выпускная квалификационная работа состоит из двух глав. В главе 1 представлены основные определения и теоремы, связанные с полукольцом натуральных чисел, и дано описание его идеалов. Глава 2 посвящена исследованию проблемы нахождения константы Фробениуса.
Глава 1. Структура идеалов в
1.1 Базовые понятия и факты
Определение 1. Непустое множество S с бинарными операциями "+" и "×" называется полукольцом, если выполняются следующие аксиомы:
1. (S, +) - коммутативная полугруппа с нейтральным элементом 0;
2. (S, ×) - полугруппа с нейтральным элементом 1;
3. умножение дистрибутивно относительно сложения:
a(b + c) = ab + ac, (a + b)c = ac + bc длялюбых a, b, c Î S;
4. 0a = 0 = a0 длялюбого aÎ S.
По этому определению полукольцо отличается от ассоциативного кольца с единицей отсутствием операции вычитания, и именно это вызывает основные трудности при работе с полукольцами.
Несложно показать, что множество натуральных чисел с обычными операциями сложения и умножения при допущении, что , является полукольцом.
Определение 2. Непустое подмножество I полукольца S называется левым идеалом полукольца S, если для любых элементов элементы a+b и sa принадлежат I. Симметричным образом определяется правый идеал. Непустое подмножество, являющееся одновременно левым и правым идеалом, называется двусторонним идеалом или просто идеалом полукольца S.
В силу коммутативности операции умножения в полукольце все идеалы являются двусторонними, в дальнейшем будем называть их просто идеалами.
Идеал, отличный от полукольца S, называется собственным.
Определение 3. В полукольце S наименьший из всех идеалов, содержащих элемент , называется главным идеалом, порожденным элементом a.
Известно, что кольцо целых чисел является кольцом главных идеалов. Идеалы в не обязательно являются главными, но все они конечно порождены. Главные идеалы в будем обозначать aN, где a – элемент, порождающий идеал.
Определение 4. Идеал коммутативного полукольца называется конечно порожденным, если найдется конечное множество элементов таких, что
Теорема 1. Произвольный идеал полукольца натуральных чисел конечно порожден.
Доказательство. Пусть – произвольный идеал из , – его наименьший ненулевой элемент. Выберем, если возможно, наименьший элемент из N. В общем случае на очередном шаге будем выбирать наименьший элемент из множества . Заметим, что выбираемые элементы обязаны быть несравнимыми по модулю . По этой причине процесс выбора будет конечным, и на некотором шаге получим
Определение 5. Пусть – идеал полукольца натуральных чисел. Множество элементов из назовем системой образующих идеала, если и никакой элемент системы образующих нельзя представить в виде комбинации с неотрицательными коэффициентами остальных элементов системы.
Очевидно, что для любого идеала система образующих определяется однозначно. Множество элементов , построенное в доказательстве теоремы 1, является системой образующих.
Если имеется в виду конкретная система образующих идеала, то будем изображать ее в круглых скобках, например: (2,3)={0,2,3,4,…}={1}.
Аналог теоремы Гильберта о базисе, которая утверждает, что если R – коммутативное кольцо, каждый идеал которого конечно порожден, то любой идеал кольца многочленов над R является конечно порожденным, неверна в классе полуколец, и примером тому служит полукольцо . Как установлено, идеалы в конечно порождены. Покажем, что этим свойством не обладает полукольцо [x]. Пусть I – множество всех многочленов ненулевой степени над . Ясно, что I‒ идеал. Любой из многочленов x, x+1, x+2,…, нельзя нетривиальным образом представить в виде суммы многочленов из I, значит, все эти многочлены необходимо лежат в любой системе образующих идеала I. Таким образом, I не является конечно порожденным, и полукольцевой аналог теоремы Гильберта не верен.
Теорема 2. Пусть ‒ система образующих идеала полукольца . Начиная с некоторого элемента , все элементы идеала образуют арифметическую прогрессию с разностью , являющейся наибольшим общим делителем чисел .
Доказательство. Пусть ‒ НОД всех представителей системы образующих идеала . По теореме о линейном представлении НОД для некоторых целых . Положим ‒ максимум из абсолютных значений чисел . Тогда элементы и лежат в идеале . Очевидно, что ‒ наименьшее натуральное число, на которое могут отличаться два элемента идеала , и . Обозначим . Пусть , для некоторых целых , и одно из них, допустим , неположительно. В таком случае рассмотрим число с такими достаточно большими натуральными коэффициентами , чтобы для любого целого выполнялось . Тогда для любого такого элемент
лежит в . Таким образом, начиная с элемента , мы имеем арифметическую прогрессию в точности из элемента, лежащих в идеале , причем первый и последний элементы отличаются на . Прибавляя к каждому из этих элементов, начиная с , число , мы получим следующие элементов этой же прогрессии. Такую процедуру можно повторять сколь угодно долго, получая элементы прогрессии, очевидно, лежащие в идеале . Показали, что, по крайней мере, с числа все элементы идеала образуют арифметическую прогрессию.
Следствие 1. Пусть ‒ произвольный идеал полукольца . Существует такое конечное множество элементов из , что является главным идеалом.
Следствие 2. Если система образующих идеала полукольца состоит из взаимно простых в совокупности чисел, то, начиная с некоторого элемента, все последующие натуральные числа будут принадлежать идеалу .
Замечание. Пусть , и . Между идеалами и , порожденными системами образующих и соответственно, существует простая связь, а именно: состоит из всех элементов идеала , умноженных на число . Тем самым, изучение идеалов полукольца натуральных чисел сводится к идеалам с взаимно простой системой образующих. В дальнейшем будем считать, что образующие идеала в совокупности взаимно просты и занумерованы в порядке возрастания.
Теорема 3. В полукольце всякая строго возрастающая цепочка идеалов обрывается.
Доказательство. Пусть ‒ возрастающая цепочка в . Тогда ‒ конечно порожденный идеал с образующими . Каждый лежит в некоторых идеалах из цепочки, значит, найдется идеал из цепочки, содержащий все элементы . Получаем , следовательно, ‒ последний идеал в нашей цепочке.
Из доказанной теоремы делаем вывод о том, что исследуемое полукольцо натуральных чисел является нетеровым.
1.2 Описание идеалов в
Определение 6. Собственный идеал Pкоммутативного полукольца S называется простым, если или для любых идеалов A и B.
Теорема A. Если S – коммутативное полукольцо, то идеал P прост тогда и только тогда, когда влечет [6].
Простыми идеалами в являются, очевидно, нулевой идеал и идеалы p. Идеал, порожденный составным числом, не может быть простым. Более того, если составное число n=ab является элементом системы образующих идеала I, то элементы a,b не лежат в идеале I, и следовательно, I не прост. Таким образом, система образующих простого идеала может состоять только из простых чисел.
Пусть P – простой идеал в , не являющийся главным, и ‒ элементы из его системы образующих. Поскольку и взаимно просты, то по второму следствию теоремы 2 все натуральные числа, начиная с некоторого, лежат в идеале P. Значит, P содержит некоторые степени чисел 2 и 3. В силу простоты идеала P, 2 и 3 будут лежать в P. Идеал, порожденный числами 2 и 3, является единственным простым идеалом, не являющимся главным.
Таким образом, простыми идеалами полукольца являются следующие идеалы, и только они:
1. нулевой идеал;
2. главные идеалы, порожденные произвольным простым числом;
3. двухпорожденный идеал (2,3).
Определение 7. Собственный идеал M полукольца S называется максимальным, если влечет или для каждого идеала A в S.
Теорема Б. Максимальный идеал коммутативного полукольца прост.[6]
В нулевой идеал и идеалы, порожденные произвольным простым числом, не являются максимальными, так как включены в идеал (2,3), который не совпадает с ними и с . Таким образом, максимальным является двухпорожденный идеал (2,3) – наибольший собственный идеал в .
Множество простых идеалов можно упорядочить следующим образом:
Здесь наибольшим элементом является двухпорожденный идеал (2,3), а наименьшим – нулевой идеал.
Определение 8. Идеал I полукольца S называется полустрогим, если влечет
Теорема 6. Полустрогий идеал полукольца в точности является главным идеалом.
Доказательство. Главные идеалы, очевидно, являются полустрогими. Предположим, что в системе образующих полустрогого идеала может быть больше двух образующих. Пусть два элемента m и n – наименьшие в системе образующих идеала, и Рассмотрим равенство m+x=n, в нем x очевидно меньше, чем n. Это означает, что x принадлежит идеалу только в том случае, когда элемент x представим в виде x=ms, где . Тогда n линейно выражается через m, а противоречит тому, что m и n – образующие.
Множество полустрогих идеалов можно упорядочить следующим образом:
Здесь наибольшим является идеал, порожденный 1, на уровень ниже его находятся идеалы, порожденные простыми числами, еще ниже – порожденные произведением двух простых чисел, дальше трех и так далее.
Определение 9. Идеал I полукольца S называется строгим, если влечет и
Cтрогий идеал обязательно является полустрогим, а в полукольце и главным. Идеалы (0) и (1), очевидно, являются строгими. В любых других главных идеалах их образующие можно представить в виде суммы 1 и числа, на 1 меньше образующей, и оба этих слагаемых не будут принадлежать I. Таким образом, строгими идеалами полукольца являются только (0) и (1).
Глава 2. Константа Фробениуса
В теории полугрупп есть понятие константы Фробениуса, им описывается для аддитивной полугруппы, порожденной линейной формой с натуральными коэффициентами, переменные которой независимо принимают целые неотрицательные значения, наибольшее целое число, не являющееся значением указанной формы [4]. Для полукольца это понятие является неразрывно связанным с элементом , а именно, они отличаются на 1: константа Фробениуса есть наибольший элемент полукольца, не являющийся элементом идеала, а с – наименьший, начиная с которого все элементы полукольца лежат в идеа
Лемма 1. Пусть . Тогда для любого натурального найдутся такие целые и , что .
Доказательство. Пусть для некоторых целых . Тогда . По теореме о делении с остатком , где . Отсюда . Взяв , получаем доказываемое утверждение.
Теорема 7. Если ‒ двухпорожденный идеал и , то
Доказательство. Покажем, что для любого целого элементы лежат в идеале . Действительно, из предыдущей леммы для подходящих . Тогда
Заметим, что , откуда . Таким образом, начиная с , все числа лежат в идеале . Осталось показать, что . Предположим, что лежит в , т.е. для некоторых . Очевидно, что мы может выбрать таким образом, чтобы выполнялось . Тогда . В силу взаимной простоты образующих получаем , откуда . Это возможно только в том случае, когда . Но это влечет , противоречие.
На XIV Международной олимпиаде по математике, прошедшей в 1984 году, для решения предлагалась задача следующего содержания:
Пусть a,b,c – целые положительные числа, каждые два из которых взаимно просты. Докажите, что наибольшее из целых чисел, которые не представимы в виде xbc+yca+zab (где x,y,z – неотрицательные целые числа), равно 2abc-ab-bc-ca[1].
В незначительной переформулировке эта задача предлагает показать, чему равна константа Фробениуса для идеала, порожденного системой образующих (ab,ac,bc) в полукольце .
Удалось найти другое решение этой задачи, а также сделать обобщение.
Теорема 8. Если a, b и с попарно взаимно просты, то
.
Доказательство. Рассмотрим. По теоремам 2 и 5 . Значит, начиная с элемента все элементы вида где Заметим, что Из условия следует, что тогда ‒ полная система вычетов по модулю a, обозначим ее (*).
Рассмотрим число
Числа можем получить из системы вычетов (*), прибавляя к ним значит, все они лежат в идеале I. Число так как а Таким образом, нашли a подряд идущих чисел, принадлежащих идеалу I, и число перед ними, не принадлежащее I. Производя подстановку и преобразовывая выражение получаем искомый элемент с.
Обобщим результат, полученный в теореме 8:
Теорема 9. Пусть , Обозначим
, ,…,
Тогда
.
Доказательство. База метода математической индукции для значений k=2,3 доказана в теоремах 7 и 8. Предположив, что выполняется , доказательство проводится аналогично доказательству теоремы 8.
Предложение. В порожденном идеале выполняется .
Доказательство. Если , то найдется, по крайней мере, пара образующих и , , сравнимых по модулю . Тогда выражается через и , противоречие.
Крайний случай доказанного выше отношения позволяет найти элемент .
Теорема 10. .
Доказательство. Заметим, что образующие образуют полную систему вычетов по модулю . Рассмотрим еще одну полную систему вычетов по тому же вычету . Для произвольного найдется в точности один образующий , сравнимый с по модулю . Тогда для некоторого , откуда следует . Получили, что подряд идущих элементов из лежат в . Поскольку, очевидно,
, то
Теорема 11. Если ‒ наименьший образующий -порожденного идеала , то , причем обе оценки точные.
Доказательство. Пусть ‒ семейство образующих идеала . До полной системы вычетов по модулю не хватает одного числа. Обозначим через наименьшее число из идеала , дополняющее до полной системы. Заметим, что для некоторого . Отсюда легко получаем, что наименьшее возможное значение, которое может принять , равно . Число не лежит в идеале , получаем оценку.
С другой стороны, , а в случае равенства числа лежат в . Действительно, каждое из них сравнимо по модулю с некоторым образующим и , откуда . Это дает оценку . Не сложно проверить, что точность обеих полученных оценок дают соответственно идеалы
и .
В общем случае проблема нахождения элемента с представляется на данный момент неразрешимой. Однако для дальнейшего ее изучения может быть использована специально разработанная программа "FindC", которая позволяет находить элемент с для введенной системы образующих, причем она может быть не упорядоченной по возрастанию и содержать элементы, линейно выражающиеся через другие.
Действия программы:
1. Сортирует введенные образующие в порядке возрастания (процедура Sort).
2. Проверяет систему на наличие элементов, линейно выражающихся через другие, в случае наличия таковых выводит их и линейную комбинацию (осуществляется с помощью процедуры Lin).
3. Выводит линейно независимую систему образующих, находит их НОД (процедура NOD). Если НОД1, то осуществляется деление каждой образующей на НОД, дальнейшая работа происходит с новой системой.
4. Проверяет элементы полукольца , начиная с 2, на возможность выражения их в виде линейной комбинации системы образующих. При нахождении подряд идущих элементов , принадлежащих идеалу, можно сделать вывод о том, что и последующие элементы также принадлежат идеалу, и программа умножает элемент, на меньше текущего, на НОД, и это произведение будет искомым элементом c.
Библиографический список
1. Абрамов А.М. Квант, №3, 1984. с. 40-41.
2. Атья М., Макдональд И. Введение в коммутативную алгебру [Текст] / М. Атья, И. Макдональд. – М.:Мир,1972.
3. Вечтомов Е.М. Введение в полукольца [Текст] / Е.М. Вечтомов. – Киров: Изд-во ВГПУ, 2000.
4. Коганов Л.М. О функциях Мебиуса и константах Фробениуса полугрупп, порожденных линейными формами специального вида / Межвузовский сборник научных трудов Полугруппы и частичные группоиды, Ленинград, 1987. с. 15-25.
5. Скорняков, Л.А. Элементы теории структур [Текст]/Л.А. Скорняков.– М.: Наука, 1982.
6. Чермных, В.В. Полукольца [Текст]/В.В. Чермных. – Киров: Изд-во ВГПУ, 1997.
Приложение 1.
Примеры работы программы при различных исходных данных.
Приложение 2.
Описание алгоритма работы программы "FindC" с помощью блок-схем.
Приложение 3
Полный текст программы "FindC".
unit SearchFirstElementSequence;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Edit: TEdit;
Button1: TButton;
Memo: TListBox;
Button2: TButton;
procedure EditKeyUp(Sender: TObject; var Key: Word; Shift: TShiftState);
procedure Button2Click(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure EditKeyPress(Sender: TObject; var Key: Char);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
masA: variant;
KolObraz: integer;
i, j, l, koef, d, kol, VspomChislo, Chislo: integer;
S: Set of Char = ['0'..'9', ',', #8];
p: boolean;
implementation
{$R *.dfm}
{Сортировка массива}
Procedure SORT;
var min: integer;
begin
min := masA[1,1];;
for i := 1 to KolObraz-1 do
for j := i+1 to KolObraz do
if masA[i,1] > masA[j,1] then begin
min := masA[j,1];
masA[j,1] := masA[i,1];
masA[i,1] := min;
end;
end;
//ищем НОД (алгоритм Евклида)
Function NOD(a,b: integer): integer;
begin
while (a <> 0) and (b <> 0) do
if a > b then a := a mod b
else b := b mod a;
if a = 0 then nod := b
else nod := a;
end;
//проверка на линейность
Procedure Lin (n, j, Chislo: integer; var p: boolean; m1: integer);
var x :integer;
begin
while (n<=m1) and not (p) and (Chislo > 0) do
begin
if j = 0 then x := 0
else x := masA[n,1];
Chislo := Chislo - x;
if Chislo = 0 then p := true
else Lin(n+1, 0, Chislo, p, m1);
if p then masA[n,2] := j;
inc(j);
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
list: TStringList;
ss: string;
begin
Memo.Clear;
//разбиениестроки
ss := Edit.Text;
list := TStringList.Create; //создаем список list
//в нем будут хранится коэффициенты, полученные в результате разбиения строки
//с помощью процедуры extractStrings (разделителем будет ',')
extractStrings([','], [], PChar(ss), list);
KolObraz := list.Count; //количество переменных
masA := VarArrayCreate([1,KolObraz,1,2], varInteger); //создание двумерного массива
for i := 1 to KolObraz do
masA[i,1] := StrToInt(list.Strings[i-1]);
list.Free;
SORT;
ss := '';
for i := 1 to KolObraz do ss := ss + ' ' + IntToStr(masA[i,1]);
memo.Items.Add('ИСХОДНАЯ СИСТЕМА ОБРАЗУЮЩИХ В ПОРЯДКЕ ВОЗРАСТАНИЯ:');
memo.Items.Add(ss);
memo.Items.Add('');
memo.Items.Add('ЛИНЕЙНО ЗАВИСИМЫЕ ЭЛЕМЕНТЫ СИСТЕМЫ ОБРАЗУЮЩИХ:');
l := 0; i := 1;
while i <= KolObraz-l do begin
p := false;
Lin(1, 0, masA[i,1], p, i-1);
//если p = true то выводим линейную комбинацию и удаяем этот элемент из массива
ifpthenbegin
//вывод разложения элемента на линейную комбинацию
ss := IntToStr(masA[i,1]) + ' = ';
if i = 2 then ss := ss + IntToStr(masA[i-1,2]) + '*' + IntToStr(masA[i-1,1])
else begin
for j := 1 to i-2 do ss := ss + IntToStr(masA[j,2]) + '*' + IntToStr(masA[j,1]) + ' + ';
ss := ss + IntToStr(masA[i-1,2]) + '*' + IntToStr(masA[i-1,1]);
end;
memo.Items.Add(ss);
//смещаем элементы массива
for j := i to KolObraz-l-1 do begin masA[j,1] := masA[j+1,1]; masA[j,2] := masA[j+1,2]; end;
inc(l);
end
else inc(i);
end;
if l = 0 then memo.Items.Add('нет');
memo.Items.Add('');
KolObraz := KolObraz-l;
memo.Items.Add('ЛИНЕЙНО НЕЗАВИСИМАЯ СИСТЕМА ОБРАЗУЮЩИХ:');
ss := '';
for i := 1 to KolObraz do ss := ss + ' ' + IntToStr(masA[i,1]);
memo.Items.Add(ss);
memo.Items.Add('');
d := NOD(masA[1,1], masA[2,1]);
if KolObraz > 2 then for i := 3 to KolObraz do d := NOD(d, masA[i,1]);
for i := 1 to KolObraz do begin masA[i,1] := masA[i,1] div d; masA[i,2] := 0; end;
Chislo := masA[1,1];
p := false;
kol := 0;
VspomChislo := Chislo;
while kol<Chislo do begin
Lin(1, 0, VspomChislo, p, KolObraz);
if p then inc(kol)
else kol := 0;
inc(VspomChislo);
p := false;
end;
ss := 'ПЕРВЫЙ ЭЛЕМЕНТ В АРИФМЕТИЧЕСКОЙ ПРОГРЕССИИ ' + IntToStr((VspomChislo - kol) * d);
p := false; j := 0;
for i := 1 to KolObraz do masA[i,2] := 0;
Lin(1, j, (VspomChislo - kol) * d, p, KolObraz);
ss := ss + ' = ';
for j := 1 to KolObraz-1 do ss := ss + IntToStr(masA[j,2]) + '*' + IntToStr(masA[j,1]) + ' + ';
ss := ss + IntToStr(masA[KolObraz,2]) + '*' + IntToStr(masA[KolObraz,1]);
ss := ss + ' с разностью ' + IntToStr(d);
memo.Items.Add(ss);
masA := Unassigned;
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
Close;
end;
procedure TForm1.EditKeyPress(Sender: TObject; var Key: Char);
begin
if not (Key in S) then Key := #0
end;
procedure TForm1.EditKeyUp(Sender: TObject; var Key: Word; Shift: TShiftState);
begin
if Edit.Text = '' then Button1.Enabled := false
else Button1.Enabled := true;
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
Button1.Enabled := false;
Memo.Clear;
Edit.Clear;
end;
end.