Numeerinen puoliryhmä - Numerical semigroup

Matematiikassa numeerinen puoliryhmä on erityinen puoliryhmä . Sen taustalla sarja on asetettu kaikkien nonnegative kokonaisluvut paitsi äärellinen numero ja laskutoimitus on toimintaa lisäämällä kokonaislukuja. Lisäksi kokonaisluvun 0 on oltava puoliryhmän osa. Esimerkiksi vaikka joukko {0, 2, 3, 4, 5, 6, ...} on numeerinen puoliryhmä, joukko {0, 1, 3, 5, 6, ...} ei johdu siitä, että 1 on joukossa ja 1 + 1 = 2 ei ole joukossa. Numeeriset puoliryhmät ovat kommutatiivisia monoideja ja tunnetaan myös nimellä numeeriset monoidit .

Numeerisen puoliryhmän määritelmä liittyy läheisesti ongelmaan määrittää ei-negatiiviset kokonaisluvut, jotka voidaan ilmaista muodossa x 1 n 1 + x 2 n 2 + ... + x r n r tietylle joukolle { n 1 , n 2 , ..., n r } positiivisia kokonaislukuja ja mielivaltaisille ei-negatiivisille kokonaisluvuille x 1 , x 2 , ..., x r . Useat matemaatikot, kuten Frobenius (1849 - 1917) ja Sylvester (1814 - 1897), olivat ottaneet tämän ongelman huomioon 1800-luvun lopulla. 1900-luvun jälkipuoliskolla kiinnostus numeeristen puoliryhmien tutkimiseen nousi esiin niiden sovellusten vuoksi algebrallisessa geometriassa .

Määritelmä ja esimerkkejä

Määritelmä

Olkoon N ei-negatiivisten kokonaislukujen joukko. Osajoukko S on N kutsutaan numeerinen puoliryhmä, jos seuraavat ehdot täyttyvät.

  1. 0 on S: n osa
  2. N - S komplementti S on N , on rajallinen.
  3. Jos x ja y ovat S: ssä, niin x + y on myös S: ssä .

Numeeristen puoliryhmien muodostamiseksi on yksinkertainen menetelmä. Olkoon A = { n 1 , n 2 , ..., n r } positiivinen kokonaisluku. Määritä kaikki kokonaisluvut muotoa x 1 n 1 + x 2 n 2 + ... + x r n r on osajoukko N syntyy ja merkitään ⟨ ⟩. Seuraava lause kuvaa täysin numeerisia puoliryhmiä.

Lause

Olkoon S A: n muodostama N: n alaryhmä . Sitten S on numeerinen puoliryhmä vain ja vain, jos gcd ( A ) = 1. Lisäksi jokainen numeerinen puoliryhmä syntyy tällä tavalla.

Esimerkkejä

Seuraavat N: n osajoukot ovat numeerisia puoliryhmiä.

  1. ⟨1⟩ = {0, 1, 2, 3, ...}
  2. ⟨1, 2⟩ = {0, 1, 2, 3, ...}
  3. ⟨2, 3⟩ = {0, 2, 3, 4, 5, 6, ...}
  4. Anna olla positiivinen kokonaisluku. ⟨ , + 1, + 2, ..., 2 - 1⟩ = {0, , + 1, + 2, + 3, ...}.
  5. Olkoon b pariton kokonaisluku on suurempi kuin 1. Sitten ⟨2, b ⟩ = {0, 2, 4,. . . , b - 3, b - 1, b , b + 1, b + 2, b + 3, ...}.
  6. Hyvin karkaistu harmoninen puoliryhmä H = {0,12,19,24,28,31,34,36,38,40,42,43,45,46,47,48, ...}

Upottamisen ulottuvuus, moninaisuus

Joukko on joukko generaattorit numeerisen puoliryhmä ⟨ ⟩. Numeerisen puoliryhmän generaattorijoukko on minimaalinen generaattorijärjestelmä, jos mikään sen oikeista alijoukoista ei tuota numeerista puoliryhmää. Tiedetään, että jokaisella numeerisella puoliryhmällä S on ainutlaatuinen minimaalinen generaattorijärjestelmä ja että tämä minimaalinen generaattorijärjestelmä on rajallinen. Äärellisiin minimaalinen joukko generaattorit kutsutaan upottamisen ulottuvuus numeerisen puoliryhmä S ja merkitään e ( S ). Pienintä jäsentä generaattoreiden minimijärjestelmässä kutsutaan numeerisen puoliryhmän S moninaisuudeksi ja sitä merkitään m ( S ).

Frobeniuksen numero ja suku

Numeeriseen puoliryhmään S liittyy useita merkittäviä lukuja .

  1. Joukkoa N - S kutsutaan aukkojen joukoksi S: ssä ja sitä merkitään G ( S ).
  2. Elementtien lukumäärä on joukko aukkoja G ( S ) kutsutaan suvun S (tai, aste singulariteetti S ) ja on merkitty g ( S ).
  3. Suurin osa G ( S ) kutsutaan Frobenius lukumäärä on S ja merkitään F ( S ).
  4. S: n pienintä elementtiä, niin että kaikki suuremmat kokonaisluvut ovat samoin S: n elementtejä, kutsutaan johtimeksi; se on F ( S ) + 1.

Esimerkkejä

Olkoon S = ⟨5, 7, 9⟩. Sitten meillä on:

  • Elementtien joukko sarjassa S  : S = {0, 5, 7, 9, 10, 12, 14, ...}.
  • Minimi S- generaattorijoukko  : {5, 7, 9}.
  • S  : n upotusulottuvuus : e ( S ) = 3.
  • S  : n moninaisuus : m ( S ) = 5.
  • S- aukkojen joukko  : G ( S ) = {1, 2, 3, 4, 6, 8, 11, 13}.
  • Frobeniuksen numero S on F ( S ) = 13, ja sen johdin on 14.
  • Suku S  : g ( S ) = 8.

Numeeriset puoliryhmät, joissa on pieni Frobenius-numero tai suku

   n    Puoliryhmä S,
   jossa F ( S ) = n   		 Puoliryhmä S,
   jossa 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⟩

Frobenius-luvun laskeminen

Numeeriset puoliryhmät, joissa on kaksi ulottuvuutta

Seuraavat yleiset tulokset olivat Sylvesterin tiedossa. Olkoon a ja b positiivisia kokonaislukuja siten, että gcd ( a , b ) = 1. Sitten

  • F (⟨ , b ⟩) = ( - 1) ( b - 1) - 1 = ab - ( + b ).
  • g (⟨ , b ⟩) = ( - 1) ( b - 1) / 2.

Numeeriset puoliryhmät, joissa on upotusulottuvuus kolme

Ei ole tunnettua yleistä kaavaa sellaisten numeeristen puoliryhmien Frobeniuksen lukumäärän laskemiseksi, joiden upotusulottuvuus on vähintään kolme. Mitään polynomikaavaa ei löydy numeerisen puoliryhmän Frobenius-luvun tai -suvun laskemiseksi, johon upotetaan ulottuvuus kolme. Jokainen positiivinen kokonaisluku on joidenkin numeeristen puoliryhmien Frobenius-numero, johon on upotettu ulottuvuus kolme.

Rödsethin algoritmi

Seuraavaa algoritmia, joka tunnetaan nimellä Rödsethin algoritmi, voidaan käyttää laskemaan Frobenius-numero numeerisesta puoliryhmästä S, jonka muodostavat { a 1 , a 2 , a 3 }, jossa a 1 < a 2 < a 3 ja gcd ( a 1 , a 2 , a 3 ) = 1. Sen pahimmassa tapauksessa monimutkaisuus ei ole yhtä hyvä kuin Greenbergin algoritmi, mutta sitä on paljon yksinkertaisempi kuvata.

  • Olkoon s 0 ainutlaatuinen kokonaisluku siten, että a 2 s 0 ≡ a 3 mod a 1 , 0 ≤ s 0 < a 1 .
  • Jatkuvan murto-algoritmia sovelletaan suhteeseen a 1 / s 0 :
    • a 1 = q 1 s 0 - s 1 , 0 ≤ s 1 < s 0 ,
    • s 0 = q 2 s 1 - s 2 , 0 ≤ s 2 < s 1 ,
    • s 1 = q 3 s 2 - s 3 , 0 ≤ s 3 < s 2 ,
    • ...
    • s m −1 = q m +1 s m ,
    • s m +1 = 0,
missä q i ≥ 2, s i ≥ 0 kaikille i: lle.
  • Olkoon p −1 = 0, p 0 = 1, p i +1 = q i +1 p i - p i −1 ja r i = ( s i a 2 - p i a 3 ) / a 1 .
  • Olkoon v yksilöllinen kokonaisluku siten, että r v +1 ≤ 0 < r v , tai vastaavasti yksilöllinen kokonaisluku, kuten
    • s v +1 / p v +1 ≤ a 3 / a 2 < s v / p v ·
  • Sitten F ( S ) = - a 1 + a 2 ( s v - 1) + a 3 ( p v +1 - 1) - min { a 2 s v +1 , a 3 p v }.

Numeeristen puoliryhmien erikoisluokat

Jaoton numeerinen puoliryhmä on numeerinen puoliryhmä siten, että se ei voi kirjoittaa leikkauksena kahden numeerinen semigroups kunnolla sisältävät sitä. Numeerinen puoliryhmä S on pelkistämätön vain ja vain, jos S on maksimiarvo joukko-osallisuuden suhteen kaikkien numeeristen puoliryhmien kokoelmassa Frobenius-numerolla F ( S ).

Numeerinen puoliryhmä S on symmetrinen, jos sitä ei voida lukea ja sen Frobenius-numero F ( S ) on pariton. Sanomme, että S on pseudosymmetrinen edellyttäen, että S on pelkistämätön ja F (S) on tasainen. Tällaisilla numeerisilla puoliryhmillä on yksinkertaiset kuvaukset Frobenius-numeron ja suvun suhteen:

  • Numeerinen puoliryhmä S on symmetrinen vain ja vain, jos g ( S ) = ( F ( S ) + 1) / 2.
  • Numeerinen puoliryhmä S on pseudosymmetrinen vain ja vain, jos g ( S ) = ( F ( S ) + 2) / 2.

Katso myös

Viitteet