Półgrupa numeryczna

0 W matematyce półgrupa liczbowa jest szczególnym rodzajem półgrupy . Jego podstawowym zbiorem jest zbiór wszystkich nieujemnych liczb całkowitych z wyjątkiem liczby skończonej, a operacja binarna to operacja dodawania liczb całkowitych. Ponadto liczba całkowita musi być elementem półgrupy. Na przykład, podczas gdy zbiór {0, 2, 3, 4, 5, 6, ...} jest półgrupą liczbową, zbiór {0, 1, 3, 5, 6, ...} nie jest, ponieważ 1 to w zbiorze i 1 + 1 = 2 nie jest w zbiorze. Półgrupy liczbowe są przemienne monoidy i są również znane jako monoidy numeryczne .

Definicja półgrupy liczbowej jest ściśle związana z problemem wyznaczania nieujemnych liczb całkowitych, które można wyrazić w postaci x ₁ n ₁ + x ₂ n ₂ + ... + x _r n _r dla danego zbioru { n ₁ , n ₂ , ..., n _r } liczb całkowitych dodatnich i dowolnych liczb całkowitych nieujemnych x ₁ , x ₂ , ..., x _r . Problem ten był rozważany przez kilku matematyków, takich jak Frobenius (1849–1917) i Sylvester (1814–1897) pod koniec XIX wieku. W drugiej połowie XX wieku zainteresowanie badaniem półgrup liczbowych powróciło ze względu na ich zastosowania w geometrii algebraicznej .

Definicja i przykłady

Definicja

Niech N będzie zbiorem nieujemnych liczb całkowitych. Podzbiór S z N nazywamy półgrupą numeryczną, jeśli spełnione są następujące warunki.

1. 0 jest elementem S
2. N - S , dopełnienie S w N , jest skończone.
3. Jeśli x i y są w S , to x + y również jest w S.

Istnieje prosta metoda konstruowania półgrup liczbowych. Niech A = { n ₁ , n ₂ , ..., n _r } będzie niepustym zbiorem dodatnich liczb całkowitych. Zbiór wszystkich liczb całkowitych postaci x ₁ n ₁ + x ₂ n ₂ + ... + x _r n _r jest podzbiorem N wygenerowanym przez A i jest oznaczony przez ⟨ A ⟩ Następujące twierdzenie w pełni charakteryzuje półgrupy liczbowe.

Twierdzenie

Niech S będzie podpółgrupą N wygenerowaną przez A . Wtedy S jest półgrupą liczbową wtedy i tylko wtedy, gdy gcd ( A ) = 1. Co więcej, każda półgrupa liczbowa powstaje w ten sposób.

Przykłady

Następujące podzbiory N są półgrupami numerycznymi.

1. ⟨ 1 ⟩ = {0, 1, 2, 3, ...}
2. ⟨ 1, 2 ⟩ = {0, 1, 2, 3, ...}
3. ⟨ 2, 3 ⟩ = {0, 2, 3, 4, 5, 6, ...}
4. Niech a będzie dodatnią liczbą całkowitą. ⟨ za , za + 1, za + 2, ... , 2 za – 1 ⟩ = {0, za , za + 1, za + 2, za + 3, ...}.
5. Niech b będzie nieparzystą liczbą całkowitą większą od 1. Wtedy ⟨ 2, b ⟩ = {0, 2, 4, . . . , b - 3 , b - 1, b , b + 1, b + 2, b + 3 , ...}.
6. Dobrze temperowana półgrupa harmoniczna H = {0,12,19,24,28,31,34,36,38,40,42,43,45,46,47,48,...}

Osadzanie wymiaru, krotność

Zbiór A jest zbiorem generatorów numerycznej półgrupy ⟨ A ⟩. Zbiór generatorów półgrupy liczbowej jest minimalnym układem generatorów, jeżeli żaden z jego właściwych podzbiorów nie generuje półgrupy liczbowej. Wiadomo, że każda półgrupa liczbowa S ma unikalny minimalny system generatorów, a także, że ten minimalny system generatorów jest skończony. Liczność minimalnego zestawu generatorów nazywana jest wymiarem osadzania numerycznej półgrupy S i jest oznaczana przez e ( S ). Najmniejszy element w minimalnym systemie generatorów nazywany jest krotnością numerycznej półgrupy S i jest oznaczany przez m ( S ).

Liczba i rodzaj Frobeniusa

Istnieje kilka godnych uwagi liczb związanych z półgrupą numeryczną S .

1. Zbiór N - S nazywany jest zbiorem luk w S i jest oznaczony przez G ( S ).
2. Liczba elementów w zbiorze przerw G ( S ) nazywana jest rodzajem S (lub stopniem osobliwości S ) i jest oznaczana przez g ( S ).
3. Największy element w G ( S ) nazywany jest liczbą Frobeniusa w S i jest oznaczony przez F ( S ).
4. Najmniejszy element S taki, że wszystkie większe liczby całkowite są podobnie elementami S , nazywany jest przewodnikiem; to jest F ( S ) + 1.

Przykłady

Niech S = ⟨ 5, 7, 9 ⟩. Następnie mamy:

• Zbiór elementów w S : S = {0, 5, 7, 9, 10, 12, 14, ...}.
• Minimalny zbiór generatorów S : {5, 7, 9}.
• Wymiar osadzania S : e ( S ) = 3.
• Krotność S : m ( S ) = 5.
• Zbiór luk w S : G ( S ) = {1, 2, 3, 4, 6, 8, 11, 13}.
• Liczba Frobeniusa S to F ( S ) = 13, a jej przewodnik to 14.
• Rodzaj S : g ( S ) = 8.

Półgrupy liczbowe z małą liczbą lub rodzajem Frobeniusa

N	Półgrupa S z F ( S ) = n	Półgrupa S z g ( S ) = n
1	⟨ 2, 3 ⟩	⟨ 2, 3 ⟩
2	⟨ 3, 4, 5 ⟩	⟨ 3, 4, 5 ⟩ ⟨ 2, 5 ⟩
3	⟨ 4, 5, 6, 7 ⟩ ⟨ 2, 5 ⟩	⟨ 4, 5, 6, 7 ⟩ ⟨ 3, 5, 7 ⟩ ⟨ 3, 4 ⟩ ⟨ 2, 7 ⟩
4	⟨ 5, 6, 7, 8, 9 ⟩ ⟨ 3, 5, 7 ⟩	⟨ 5, 6, 7, 8, 9 ⟩ ⟨ 4, 6, 7, 9 ⟩ ⟨ 3, 7, 8 ⟩ ⟨ 4, 5, 7 ⟩ ⟨ 4, 5, 6 ⟩ ⟨ 3, 5, ⟩ ⟨ 2, 9 ⟩

Obliczanie liczby Frobeniusa

Półgrupy liczbowe z osadzeniem w wymiarze drugim

Sylwesterowi znane były następujące ogólne wyniki. Niech a i b będą dodatnimi liczbami całkowitymi takimi, że gcd ( a , b ) = 1. Wtedy

• fa (⟨ za , b ⟩) = ( za - 1) ( b - 1) - 1 = ab - ( za + b ).
• sol (⟨ za , b ⟩) = ( za - 1) ( b - 1) / 2.

Półgrupy liczbowe z osadzeniem wymiaru trzy

Nie jest znany ogólny wzór do obliczania liczby Frobeniusa liczbowych półgrup mających wymiar osadzania trzy lub więcej. Nie można znaleźć formuły wielomianowej do obliczenia liczby Frobeniusa lub rodzaju półgrupy liczbowej z osadzonym wymiarem trzy. Każda dodatnia liczba całkowita jest liczbą Frobeniusa jakiejś półgrupy liczbowej z osadzonym wymiarem trzy.

Algorytm Rödsetha

Poniższy algorytm, znany jako algorytm Rödsetha, może być użyty do obliczenia liczby Frobeniusa numerycznej półgrupy S generowanej przez { a ₁ , a ₂ , a ₃ } gdzie a ₁ < a ₂ < a ₃ i gcd ( a ₁ , a ₂ , 3 _{_} ) = 1. Jego złożoność w najgorszym przypadku nie jest tak dobra jak algorytm Greenberga, ale jest znacznie prostsza do opisania.

• ₀₀₀ Niech s będzie unikalną liczbą całkowitą taką, że a ₂ s ≡ a ₃ mod a ₁ , 0 ≤ s < a ₁ .
• ₀ Algorytm ułamka ciągłego jest stosowany do stosunku a ₁ / s :
  • ₀₀ za ₁ = q ₁ s - s ₁ , 0 ≤ s ₁ < s ,
  • ₀ s = q ₂ s ₁ - s ₂ , 0 ≤ s ₂ < s ₁ ,
  • s ₁ = q ₃ s ₂ - s ₃ , 0 ≤ s ₃ < s ₂ ,
  • ...
  • s _{m −1} = q _{m +1} s _m ,
  • s _{m +1} = 0,

gdzie q _i ≥ 2, s _i ≥ 0 dla wszystkich i.

• ₀ Niech p _-1 = 0, p = 1, p _{ja +1} = q _{ja +1} p _ja - p _{ja -1} i r _ja = ( s _ja za ₂ - p _ja za ₃ )/ za ₁ .
• Niech v będzie niepowtarzalną liczbą całkowitą taką, że r _{v +1} ≤ 0 < r _v , lub równoważnie niepowtarzalną liczbą całkowitą taką
  • jak s _{v +1} / p _{v +1} ≤ a ₃ / a ₂ < s _v / p _v ·
• Wtedy fa ( S ) = - za ₁ + za ₂ ( s _v - 1) + za ₃ ( p _{v +1} - 1) - min { za ₂ s _{v +1} , za ₃ p _v }.

Specjalne klasy półgrup liczbowych

Nieredukowalna półgrupa liczbowa to półgrupa liczbowa taka, że ​​nie można jej zapisać jako przecięcia dwóch półgrup liczbowych, które ją właściwie zawierają. Półgrupa liczbowa S jest nieredukowalna wtedy i tylko wtedy , gdy S jest maksymalna ze względu na inkluzję zbioru w zbiorze wszystkich półgrup liczbowych o liczbie Frobeniusa F ( S ).

Numeryczna półgrupa S jest symetryczna , jeśli jest nierozkładalna, a jej liczba Frobeniusa F ( S ) jest nieparzysta. Mówimy, że S jest pseudosymetryczny pod warunkiem, że S jest nierozkładalny i F(S) jest parzysty. Takie półgrupy liczbowe mają proste charakterystyki pod względem liczby i rodzaju Frobeniusa:

• Numeryczna półgrupa S jest symetryczna wtedy i tylko wtedy, gdy g ( S ) = ( F ( S ) + 1)/2.
• Numeryczna półgrupa S jest pseudosymetryczna wtedy i tylko wtedy, gdy g ( S ) = ( F ( S ) + 2)/2.

Zobacz też

• liczba Frobeniusa
• Specjalne klasy półgrup
• Półgrupa
• Moneta srebrna