Строение идеалов полукольца натуральных чисел

Министерство образования и науки РФ

Государственное образовательное учреждение высшего профессионального образования

Вятский государственный гуманитарный университет

Физико-математический факультет

Кафедра высшей математики

Выпускная квалификационная работа

Строение идеалов полукольца натуральных чисел

Выполнила студентка 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 то выводим линейную комбинацию и удаяем этот элемент из массива

if p then begin

//вывод разложения элемента на линейную комбинацию

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.