Сандық жартылай топ - Numerical semigroup

Математикада а сандық жартылай топ а-ның ерекше түрі жартылай топ. Оның астарында орнатылды барлық негативтердің жиынтығы бүтін сандар қоспағанда ақырлы нөмірі және екілік операция операциясы болып табылады қосу бүтін сандар. Сондай-ақ, бүтін сан 0 жартылай топтың элементі болуы керек. Мысалы, {0, 2, 3, 4, 5, 6, ...} жиыны сандық жартылай топ болғанымен, {0, 1, 3, 5, 6, ...} жиынтығы 1-ге тең емес жиынында және 1 + 1 = 2 жиынтықта жоқ. Сандық жартылай топтар болып табылады ауыстырмалы моноидтар және сондай-ақ ретінде белгілі сандық моноидтар.[1][2]

Сандық жартылай топтың анықтамасы формада көрсетуге болатын теріс емес бүтін сандарды анықтау мәселесімен тығыз байланысты. х1n1 + х2 n2 + ... + хр nр берілген жиын үшін {n1, n2, ..., nр} оң бүтін сандар және теріс емес бүтін сандар үшін х1, х2, ..., хр. Бұл мәселені бірнеше математиктер қарастырды Фробениус (1849 - 1917) және Сильвестр (1814 - 1897) 19 ғасырдың аяғында.[3] ХХ ғасырдың екінші жартысында сандық жартылай топтарды зерттеуге деген қызығушылық олардың қолданылуына байланысты қайта пайда болды алгебралық геометрия.[4]

Анықтама және мысалдар

Анықтама

Келіңіздер N теріс емес бүтін сандардың жиыны болуы керек. Ішкі жиын S туралы N егер келесі шарттар орындалса, сандық жартылай топ деп аталады.

  1. 0 - элементі S
  2. NS, толықтауыш S жылы N, ақырлы.
  3. Егер х және ж бар S содан кейін x + y сонымен қатар S.

Сандық жартылай топтар құрудың қарапайым әдісі бар. Келіңіздер A = {n1, n2, ..., nр} натурал сандардың бос емес жиыны болуы керек. Форманың барлық бүтін сандарының жиыны х1 n1 + х2 n2 + ... + хр nр ішкі бөлігі болып табылады N жасаған A және ⟨арқылы белгіленеді A ⟩. Келесі теорема сандық жартылай топтарды толығымен сипаттайды.

Теорема

Келіңіздер S кіші тобы болуы керек N жасаған A. Содан кейін S егер болса ғана, егер бұл сандық жартылай топ болса gcd (A) = 1. Сонымен, әр сандық жартылай топ осылай туындайды.[5]

Мысалдар

Келесі ішкі жиындар N сандық жартылай топтар.

  1. ⟨ 1 ⟩ = {0, 1, 2, 3, ...}
  2. ⟨ 1, 2 ⟩ = {0, 1, 2, 3, ...}
  3. ⟨ 2, 3 ⟩ = {0, 2, 3, 4, 5, 6, ...}
  4. Келіңіздер а оң бүтін сан болуы керек. ⟨ а, а + 1, а + 2, ... , 2а - 1 ⟩ = {0, а, а + 1, а + 2, а + 3, ...}.
  5. Келіңіздер б 1-ден үлкен тақ сан болуы керек. Сонда ⟨2, б ⟩ = {0, 2, 4, . . . , б − 3 , б − 1, б, б + 1, б + 2, б + 3 , ...}.
  6. Жақсы мінезді гармоникалық жартылай топ H={0,12,19,24,31,34,36,38,40,42,43,45,46,47,48,...} [6]

Өлшемді енгізу, көптік

Жинақ A - бұл сандық жартылай топ генераторларының жиынтығы is A ⟩. Егер сандық жартылай топ генераторларының жиынтығы, егер оның тиісті ішкі жиындарының ешқайсысы сандық жартылай топ құрмаса, генераторлардың минималды жүйесі болып табылады. Әрбір сандық жартылай топ екені белгілі S генераторлардың бірегей минималды жүйесі бар, сонымен қатар бұл генераторлардың минималды жүйесі ақырлы. Генераторлардың минималды жиынтығының маңыздылығы деп аталады өлшемді енгізу сандық жартылай топтың S және деп белгіленеді e(S). Генераторлардың минималды жүйесіндегі ең кіші мүше деп аталады көптік сандық жартылай топтың S және деп белгіленеді м(S).

Фробениус саны және тұқымы

Сандық жартылай топпен байланысты бірнеше маңызды сандар бар S.

  1. Жинақ NS саңылаулар жиынтығы деп аталады S және деп белгіленеді G(S).
  2. Саңылаулар жиынтығындағы элементтер саны G(S) деп аталады S (немесе, даралық дәрежесі S) деп белгіленеді ж(S).
  3. Ішіндегі ең үлкен элемент G(S) деп аталады Фробениус нөмірі туралы S және деп белгіленеді F(S).
  4. -Ның ең кіші элементі S барлық үлкен сандар да элементтері болатындай етіп S өткізгіш деп аталады; Бұл F(S) + 1.

Мысалдар

Келіңіздер S = ⟨5, 7, 9⟩. Сонда бізде:

  • Ішіндегі элементтер жиынтығы S : S = {0, 5, 7, 9, 10, 12, 14, ...}.
  • Генераторларының минималды жиынтығы S : {5, 7, 9}.
  • Ендіру өлшемі S : e(S) = 3.
  • -Ның еселігі S : м(S) = 5.
  • Бос орындардың жиынтығы S : G(S) = {1, 2, 3, 4, 6, 8, 11, 13}.
  • Фробениус саны S болып табылады F(S) = 13, ал оның өткізгіші 14-ке тең.
  • Тұқымдасы S : ж(S) = 8.

Кішкентай Frobenius саны немесе тұқымы бар сандық топтар

   n   Жартылай топ S
бірге F(S) = n   
Жартылай топ S
бірге ж(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 ⟩

Фробениус нөмірін есептеу

Екінші өлшемді ендірілген сандық топтар

Келесі жалпы нәтижелер Сильвестрге белгілі болды.[7][тексеру сәтсіз аяқталды ] Келіңіздер а және б натурал сандар болуы керек gcd (а, б) = 1. Сонда

  • F(⟨ а, б ⟩) = (а − 1) (б − 1) − 1 = аб − (а + б).
  • ж(⟨ а, б ⟩) = (а − 1)(б − 1) / 2.

Үшінші өлшемді ендіретін сандық топтар

Үш немесе одан да көп өлшемді ендіретін Frobenius сандық жартылай топтарының санын есептеудің белгілі жалпы формуласы жоқ. Үшінші өлшемді енгізе отырып, сандық жартылай топтың Frobenius санын немесе түрін есептейтін полиномдық формуланы табу мүмкін емес.[8] Әрбір оң бүтін сан - үш өлшемді ендірілген бірнеше жартылай топтың Frobenius саны.[9]

Родсеттің алгоритмі

Родсеттің алгоритмі деп аталатын келесі алгоритм,[10][11] сандық жартылай топтың Frobenius санын есептеу үшін қолдануға болады S жасаған {а1, а2, а3} қайда а1 < а2 < а3 және gcd ( а1, а2, а3) = 1. Оның ең нашар күрделілігі Гринбергтің алгоритміндей жақсы емес[12]бірақ оны сипаттау әлдеқайда қарапайым.

  • Келіңіздер с0 бірегей бүтін сан болуы керек а2с0а3 мод а1, 0 ≤ с0 < а1.
  • Жалғастырылған бөлшек алгоритмі қатынасқа қолданылады а1/с0:
    • а1 = q1с0с1, 0 ≤ с1 < с0,
    • с0 = q2с1с2, 0 ≤ с2 < с1,
    • с1 = q3с2с3, 0 ≤ с3 < с2,
    • ...
    • см−1 = qм+1см,
    • см+1 = 0,
қайда qмен ≥ 2, смен I 0 барлығы үшін.
  • Келіңіздер б−1 = 0, б0 = 1, бмен+1 = qмен+1бменбмен−1 және рмен = (смена2бмена3)/а1.
  • Келіңіздер v бірегей бүтін сан болуы керек рv+1 ≤ 0 < рv, немесе оған теңестірілген бірегей бүтін сан
    • сv+1/бv+1а3/а2 < сv/бv·
  • Содан кейін, F(S) = −а1 + а2(сv − 1) + а3(бv+1 - 1) - мин {а2сv+1, а3бv}.

Сандық жартылай топтардың арнайы сыныптары

Ан қысқартылмайтын сандық жартылай топ - бұл сандық жартылай топ, сондықтан оны дұрыс қамтитын екі сандық жартылай топтардың қиылысы ретінде жазуға болмайды. Сандық жартылай топ S және егер болса ғана азайтуға болмайды S Фробениус нөмірімен барлық сандық жартылай топтардың жиынтығына енгізуге қатысты максималды F(S).

Сандық жартылай топ S болып табылады симметриялы егер ол азайтылса және оның Фробениус саны болса F(S) тақ. Біз мұны айтамыз S болып табылады жалған симметриялы деген шартпен S азаймайды, ал F (S) - тең. Мұндай сандық жартылай топтар Frobenius саны мен түріне қатысты қарапайым сипаттамаларға ие:

  • Сандық жартылай топ S симметриялы, егер және егер болса ғана ж(S) = (F(S) + 1)/2.
  • Сандық жартылай топ S псевдо-симметриялы болып табылады және егер болса ж(S) = (F(S) + 2)/2.

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Гарсия-Санчес, П.А. «Миникурстың сандық топтары». Алынған 6 сәуір 2011.
  2. ^ Финч, Стивен. «Натурал сандардың моноидтары» (PDF). INRIA алгоритмдер жобасы. Алынған 7 сәуір 2011.
  3. ^ Дж.К.Розалес және П.А. Гарсия-Санчес (2009). Сандық топтар. Спрингер. ISBN  978-1-4419-0159-0.
  4. ^ В. Баруччи; т.б. (1997). «Сандық жартылай топтардағы максималды қасиеттер және бір өлшемді аналитикалық төмендетілмейтін жергілікті домендерге қосымшалар». Амер туралы естеліктер. Математика. Soc. 598.
  5. ^ Гарсия-Санчес, Дж.К. Розалес, П.А. (2009). Сандық жартылай топтар (Бірінші ред.). Нью-Йорк: Спрингер. б. 7. ISBN  978-1-4419-0160-6.
  6. ^ М.Брас-Аморос (2019). «Нақты сандардың шыңдалған моноидтары, алтын фрактал моноиды және жақсы шыңдалған гармоникалық жартылай топ». Semigroup форумы. 99: 496–516. arXiv:1703.01077. дои:10.1007 / s00233-019-10059-4.
  7. ^ Дж. Дж. Сильвестр (1884). «Математикалық сұрақтар олардың шешімдерімен». Education Times. 41 (21).
  8. ^ Ф.Кертис (1990). «Сандық жартылай топтың Фробениус санының формулалары туралы». Mathematica Scandinavica. 67 (2): 190–192. дои:10.7146 / math.scand.a-12330. Алынған 18 наурыз 2019.
  9. ^ Дж. Розалес; т.б. (2004). «Әрбір оң бүтін сан - бұл үш генераторы бар жартылай топтың Frobenius саны». Mathematica Scandinavica. 94: 5–12. дои:10.7146 / math.scand.a-14427. Алынған 14 наурыз 2015.
  10. ^ Дж.Л. Рамирес Альфонсин (2005). Диофантин Фробениус мәселесі. Оксфорд университетінің баспасы. бет.4 –6. ISBN  978-0-19-856820-9.
  11. ^ Ө.Ж. Родсет (1978). «Фробениустың сызықтық диофантиялық мәселесі туралы». Дж. Рейн Энгью. Математика. 301: 171–178.
  12. ^ Гарольд Гринберг (1988). «Теріс емес бүтін сандар үшін сызықтық диофантиялық теңдеуді шешу». Алгоритмдер журналы. 9 (3): 343–353. дои:10.1016/0196-6774(88)90025-9.