Будова ідеалів півкільця натуральних чисел

Курсова робота

Будова ідеалів півкільця натуральних чисел

Зміст

Введення

Розділ 1. Структура ідеалів в

1.1 Базові поняття й факти

1.2 Опис ідеалів в

Розділ 2. Константа Фробениуса

Додаток 1. Опис алгоритму роботи програми за допомогою блок-схем

Додаток 2. Повний текст програми "FindC"

Бібліографічний список

Введення

Теорія півкілець - один з розділів загальної алгебри, що є узагальненням теорії кілець. Вагомий внесок у її вивчення й розвиток внесли Е.М. Вечтомов і В.В. Чермних. Великий інтерес для вивчення являє собою півкільце натуральних чисел зі звичайними операціями додавання й множення. Його роль у теорії півкілець приблизно така ж, як і кільця цілих чисел у теорії кілець. Питанню будови півкільця натуральних чисел присвячена глава в книзі В.В. Чермних "Півкільця" [6].

Метою даної роботи є дослідження півкільця натуральних чисел і його будови. Більш точно з'ясовується питання, як улаштовані ідеали цього півкільця, а також здійснюється відшукання або визначення границь розташування константи Фробениуса для деяких ідеалів.

Курсова робота складається із двох глав. У главі 1 представлені основні визначення й теореми, пов'язані з півкільцем натуральних чисел, і даний опис його ідеалів. Розділ 2 присвячена дослідженню проблеми знаходження константи Фробениуса.

Розділ 1. Структура ідеалів в

1.1 Базові поняття й факти

Визначення 1. Непуста множина S з бінарними операціями "+" і "(" називається півкільцем, якщо виконуються наступні аксіоми:

(S, +) ( комутативна напівгрупа з нейтральним елементом 0;

(S, () ( напівгрупа з нейтральним елементом 1;

множення дистрибутивні щодо додавання:

a(b + c) = ab + ac, (a + b)c = ac + bc для будь-яких a, b, c ( S;

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, є єдиним простим ідеалом, що не є головним.

Таким чином, простими ідеалами півкільця є наступні ідеали, і тільки вони:

нульовий ідеал;

головні ідеали, породжені довільним простим числом;

двохпороджений ідеал (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", що дозволяє знаходити елемент із для уведеної системи утворюючих, причому вона може бути не впорядкованої по зростанню й містити елементи, що лінійно виражаються через інші.

Дії програми:

Сортує уведені утворюючі в порядку зростання (процедура Sort).

Перевіряє систему на наявність елементів, що лінійно виражаються через інші, у випадку наявності таких виводить їх і лінійну комбінацію (здійснюється за допомогою процедури Lin).

Виводить лінійно незалежну систему утворюючих, знаходить їх НОД (процедура NOD). Якщо НОД 1, то здійснюється ділення кожної утворюючої на НОД, подальша робота відбувається з новою системою.

Перевіряє елементи півкільця , починаючи з 2, на можливість вираження їх у вигляді лінійної комбінації системи утворюючих. При знаходженні підряд, що йдуть елементів , що належать ідеалу, можна зробити висновок про те, що й наступні елементи також належать ідеалу, і програма множить елемент, на менше поточного, на НОД, і цей добуток буде шуканим елементом c.

Додаток 1.

Опис алгоритму роботи програми "FindC" за допомогою блок-схем.



Додаток 2

Повний текст програми "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.

Бібліографічний список

Абрамов А.М. Квант, №3, 1984. с. 40-41.

Атья М., Макдональд І. Введення в комутативну алгебру. - К., 2003

Вечтомов Є.М. Введення в півкільця. - К., 2000

Коганов Л.М. Про функції Мебиуса й константах Фробениуса напівгруп, породжених лінійними формами спеціального виду. - К., 2005

Кушнірів, Л.А. Елементи теорії структур. - К., 2005

Чермних, В.В. Півкільця. - К., 2003