Міністерство освіти і науки РФ
Державна освітня установа вищої професійної освіти
Вятский державний гуманітарний університет
Фізико-математичний факультет
Кафедра вищої математики
Випускна кваліфікаційна робота
Будова ідеалів півкільця натуральних чисел
Виконала студентка V курсу
фізико-математичного факультету
Вахрушева Ольга Валеріївна
Науковий керівник: д.ф.-м.н.., Професор кафедри вищої математики Чермний В. В. Рецензент: д.ф-м.н., Професор, завідувач кафедрою вищої математики Вечтомов Є.М.
Кіров 2010
Зміст
Введення
Глава 1. Структура ідеалів у
1.1 Базові поняття і факти
1.2 Опис ідеалів у
Глава 2. Константа Фробеніуса
Бібліографічний список
Додаток 1. Приклади роботи програми "FindC" для різних вихідних даних
Додаток 2. Опис алгоритму роботи програми за допомогою блок-схем
Додаток 3. Повний текст програми "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.
Відомо, що кільце цілих чисел є кільцем головних ідеалів. Ідеали в не обов'язково є головними, але всі вони звичайно породжені. Головні ідеали в будемо позначати a N, м де 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 - невід'ємні цілі числа), дорівнює 2 abc - 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.
Бібліографічний список
Абрамов А.М. Квант, № 3, 1984. с. 40-41.
Атья М., Макдональд І. Введення в комутативну алгебру [Текст] / М. Атья, І. Макдональд. - М.: Мир, 1972.
Вечтомов Є.М. Введення в півкільця [Текст] / О.М. Вечтомов. - К.: Вид-во ВДПУ, 2000.
Коганов Л.М. Про функції Мебіуса і константах Фробеніуса напівгруп, породжених лінійними формами спеціального виду / Міжвузівський збірник наукових праць Напівгрупи і часткові группоіди, Ленінград, 1987. с. 15-25.
Кушнірів, Л.А. Елементи теорії структур [Текст] / Л.А. Скорняков .- М.: Наука, 1982.
Червоне, В.В. Півкільця [Текст] / В.В. Чермний. - К.: Вид-во ВДПУ, 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.