Розділ 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.