Холл сөзі - Hall word

Жылы математика аудандарында топтық теория және комбинаторика, Холл сөздері бірегей ұсынады моноидты факторизация туралы ақысыз моноид. Олар сондай-ақ толығымен тапсырыс берілді, және осылайша моноид бойынша жалпы тапсырысты қамтамасыз етіңіз. Бұл ұқсас жағдайға ұқсас Линдон сөздері; Шын мәнінде, Линдон сөздері ерекше жағдай болып табылады және Линдон сөздерінің барлық қасиеттері Холл сөздеріне ауысады. Холл сөздері бір-біріне сәйкес келеді Холл ағаштары. Бұлар екілік ағаштар; бірігіп, олар құрайды Зал жиналды. Бұл жиынтық ерекше толығымен тапсырыс берілді ассоциативті емес алгебраның ішкі жиыны, яғни а ақысыз магма. Бұл нысанда Холл ағаштары негіз береді Lie алгебралары, және талап етілген коммутацияларды орындау үшін пайдалануға болады Пуанкаре – Бирхофф – Витт теоремасы а құрылысында қолданылады әмбебап қаптайтын алгебра. Осылайша, бұл Линдон сөздерімен жасалған кездегі процесті жалпылайды. Холл ағаштары топ элементтеріне жалпы тапсырыс беру үшін де қолданылуы мүмкін коммутаторды жинау процесі, бұл төменде келтірілген жалпы құрылыстың ерекше жағдайы. Мұны көрсетуге болады Lazard жиынтықтары Холл жиынтығымен сәйкес келеді.

Тарихи даму жоғарыда келтірілген сипаттамадан кері тәртіпте жүреді. The коммутаторды жинау процесі бірінші, 1934 жылы сипатталған Филип Холл және 1937 жылы зерттелген Вильгельм Магнус.[1][2] Зал жиынтықтары ұсынылды Маршалл Холл Филипп Холлдың топтардағы жұмысы негізінде.[3] Кейіннен, Вильгельм Магнус ретінде пайда болатындығын көрсетті өтірік алгебра фильтрациясымен байланысты тегін топ берілген төменгі орталық серия. Бұл корреспонденция түрткі болды коммутатор сәйкестік топтық теория байланысты Филипп Холл және Эрнст Витт.

Зал жиналды

The Зал жиналды Бұл толығымен тапсырыс берілді ассоциативті емес алгебраның ішкі жиыны, яғни а ақысыз магма. Келіңіздер генераторлардың жиынтығы болыңыз және рұқсат етіңіз ақысыз магма бол . Еркін магма - бұл жай әріптердегі ассоциативті емес жолдардың жиынтығы , топтастыруды көрсету үшін жақшамен бірге. Эквивалентті түрде, еркін магма - барлығының жиынтығы екілік ағаштар олардың жапырақтары элементтер болып табылады .

Зал жиналды рекурсивті түрде келесідей құрылуы мүмкін:

  • Элементтері ерікті жалпы тапсырыс беріледі.
  • Холл жиынтығында генераторлар бар:
  • Коммутатор егер және егер болса және және және:
    • Не (және осылайша ),
    • Немесе бірге және және .
  • Коммутаторларға ерікті түрде тапсырыс беруге болады, бұл жағдайда әрқашан ұстайды.

Төменде қолданылған құрылым мен жазба белгілерде қолданылғанмен бірдей коммутаторды жинау процесі, және де тікелей салыстыруға болады; салмақ - бұл жіптің ұзындығы. Айырмашылық мынада: топтар туралы сөз қозғалмайды. Бұл анықтамалардың барлығы X. Веньондықымен сәйкес келеді.[4] Кейбір авторлар теңсіздік ретін өзгерткеніне назар аударыңыз. Сондай-ақ, шарттардың бірі , «артқа» сезінуі мүмкін; бұл «артта қалушылық» факторизацияға қажетті кему тәртібін қамтамасыз етеді. Теңсіздікті қалпына келтіру керек емес бұл «артта қалушылықты» кері қайтару.

Мысал

Екі элементтен тұратын генератор жиынтығын қарастырайық Анықтаңыз және жаз үшін жақшаны қажеттілікке қарай пайдаланып, жазуды оңайлату. Зал жиынтығының бастапқы мүшелері содан кейін (ретімен)

Бар екеніне назар аударыңыз әр нақты ұзындықтың элементтері. Бұл екі элементтегі алқа полиномының басталу реттілігі (келесіде, төменде сипатталған).

Комбинаторика

Негізгі нәтиже - бұл ұзындық элементтерінің саны Холл жиынтығында (аяқталды) генераторлар) берілген алқа полиномы

қайда классикалық Мебиус функциясы. Қосынды а Дирихлет конволюциясы.

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

Кейбір негізгі анықтамалар пайдалы. Ағаш берілген , элемент деп аталады дереу сол жақ ағаш, және, болып табылады дереу оң жақ ағаш. A оң жақ ағаш ол да өзі немесе екеуінің де оң жақ ағашы немесе . Бұл айырмашылығы экстремалды оң жақ ағаш, бұл да өзі немесе экстремалды оң жақ ағаш .

Негізгі лемма - бұл - Холл ағашының оң жақ кіші ағашы , содан кейін

Холл сөздері

Холл сөздері коммутатор жақшаларын «ұмытып», бірақ басқаша тәртіп туралы ұғымды сақтай отырып, Холлдан алынған. Бұл «ұмыту» зиянсыз болып шығады, өйткені сөзден тиісті Холл ағашын шығаруға болады және ол ерекше. Яғни, Холл сөздері Холл ағаштарымен бір-біріне сәйкес келеді. Холл ағаштарындағы жалпы тапсырыс Холл сөздеріндегі жалпы тәртіпке ауысады.

Бұл сәйкестік а моноидты факторизация: Берілген ақысыз моноид , кез келген элементі Холл сөздерінің жоғарылау тізбегіне ерекше түрде бөлінуі мүмкін. Бұл факторизацияның ұқсас жағдайын жалпылайды және жалпылайды Линдон сөздері ұсынған Чен-Фокс-Линдон теоремасы.

Дәлірек айтсақ, әр сөз Холл сөздерінің сабақтастығы ретінде жазылуы мүмкін

әрбір Холл сөзімен толығымен Залдың бұйрығымен:

Осылайша, Холл сөзінің реті моноидтың жалпы тәртібіне таралады. Ағаштар арасындағы сәйкестікті қамтамасыз ету үшін қажет леммалар мен теоремалар және бірегей реттілік төменде келтірілген.

Жапырақтар

The жапырақ магманың канондық картаға түсіру болып табылады магмадан бастап ақысыз моноид , берілген үшін және басқаша. Жапырақ - бұл жай ғана ағаштың жапырақтарынан тұратын жіп, яғни коммутатор жақшаларымен жазылған ағашты алып, коммутатор жақшаларын өшіру.

Холл сөздерін факторизациялау

Келіңіздер Холл ағашы болыңыз және тиісті Холл сөзі болыңыз. Холл сөзінің кез-келген факторизациясы берілген бос емес екі қатарға және , содан кейін Холл ағаштарында факторизация баржәне бірге

және

Мұны және одан кейінгі дамуды Гай Меланчон келтіреді.[5]

Хат алмасу

Жоғарыда келтірілген факторизацияға керісінше Холл сөздері мен Холл ағаштары арасындағы сәйкестікті орнатады. Мұны келесі қызықты формада айтуға болады: егер бұл Холл ағашы және оған сәйкес Холл сөзі ретінде факторизациялайды

бірге

содан кейін . Басқаша айтқанда, Холл сөздері мүмкін емес басқа Холл сөздерінің кему ретімен ескерілсін.[5] Бұл Холл сөзімен сәйкес ағашты бірегей анықтауға болатындығын білдіреді.

Стандартты факторизация

Холл ағаштарындағы жалпы тапсырыс Холл сөзіне ауысады. Осылайша, Холл сөзі берілді , оны факторизациялауға болады бірге . Бұл деп аталады стандартты факторизация.

Стандартты реттілік

A жүйелі Холл сөздері деп аталады стандартты реттілік егер әрқайсысы болса не хат, не стандартты факторизация бірге Холл сөздерінің көбеюі стандартты болып табылатынын ескеріңіз.

Мерзімді қайта жазу

Кез-келген сөздің ерекше факторизациясы Холл сөздерінің көтерілу ретін біріктіруге бірге қарапайымды анықтау және рекурсивті қолдану арқылы қол жеткізуге болады мерзімді қайта жазу жүйесі. Факторизацияның бірегейлігі келесіден туындайды түйісу жүйенің қасиеттері.[5] Қайта жазу белгілі бір жұп дәйекті Холл сөздерінің алмасуымен жүзеге асырылады; ол осы анықтамалардан кейін беріледі.

A түсіру ретімен Холл сөздері - бұл жұп осындай Егер реттілік стандартты реттілік болса, онда құлдырау а деп аталады заңды құлдырау егер біреуінде бар болса

Заңды құлдырауы бар стандартты реттілікті ескере отырып, жаңа стандартты дәйектіліктер жасайтын екі қайта жазу ережелері бар. Біреуі тамшыдағы екі сөзді біріктіреді:

ал екіншісі тамшыдағы екі элементті ауыстырады:

Екі қайта жазудың да жаңа стандартты дәйектілікке әкелетінін көрсету қиын емес. Жалпы, қайта жазуды ең дұрыс заңды құлауға қолдану ыңғайлы; дегенмен, қайта жазудың келісімді екендігін көрсетуге болады, сондықтан кез-келген тәртіпке қарамастан бірдей нәтижелерге қол жеткізуге болады.

Жалпы тапсырыс

Сөздерге жалпы тапсырыс беруге болады Бұл стандартқа ұқсас лексикографиялық тәртіп, бірақ Холл сөздері деңгейінде. Екі сөз берілген көтерілу залының сөз реті бойынша ескерілген, мен. e. бұл

және

әрқайсысымен Холл сөзі, бұған бұйрық бар егер болса

және

немесе егер

және

Қасиеттері

Холл сөздері бірқатар қызықты қасиеттерге ие, олардың көпшілігі олармен бірдей Линдон сөздері. Бірінші және ең маңызды қасиет - Линдон сөздері Холл сөздерінің ерекше жағдайы. Яғни, Линдон сөзінің анықтамасы Холл сөзінің анықтамасын қанағаттандырады. Мұны тікелей салыстыру арқылы оңай тексеруге болады; жоғарыда келтірілген анықтамаларда қолданылатын теңсіздік бағыты Линдон сөздері үшін әдеттегі анықтамада қолданылған бағыттың дәл кері болатындығына назар аударыңыз. Линдон ағаштарының жиынтығы (стандартты факторизациядан шығады) - Холл жиынтығы.

Басқа қасиеттерге мыналар жатады:

  • Холл сөздері ациклді ака қарапайым. Яғни, оларды формада жазу мүмкін емес бір сөз үшін және .
  • Әрбір қарабайыр сөз болып табылады конъюгат Холл сөзіне. Яғни бар дөңгелек ауысым туралы бұл Холл сөзі. Бұған тең факторландыру бар осындай бұл Холл сөзі. Бұл коньюгат ерекше.
  • Сөз бұл кез-келген факторизация үшін ғана Холл сөзі бос емес сөздерге бағынады . (Тағы да ескертіңіз, бұл Линдон сөзінде сияқты; Линдон сөздері олардың конъюгация сыныбының ең кішісі, сондықтан біз Линдон сөзінен шыққан теңсіздік конвенциясымен жұмыс істейміз.)
  • Сөз бұл Холл сөзі, егер ол кез-келген тиісті фактордан үлкен болса ғана.
  • Әр сөз бірегей Холл сөзінің күшінің конъюгаты болып табылады.

Салдары

Осыған ұқсас мерзімді қайта жазу жүйесі бар Линдон сөздері, осылай моноидты факторизациялау Линдон сөздерімен орындалады.

Холл сөздерін Холл ағаштарына орналастыруға болатындықтан және әрбір Хол ағашын коммутатор ретінде түсіндіруге болатындықтан, қайта жазу терминін орындау үшін қолдануға болады коммутаторды жинау процесі топта.

Қайта жазу ережесінің тағы бір өте маңызды қолданылуы - пайда болатын коммутацияларды орындау Пуанкаре – Бирхофф – Витт теоремасы. Коммутация туралы егжей-тегжейлі талқылау туралы мақалада келтірілген әмбебап қаптайтын алгебралар. Терминалды Линдон сөздерімен қайта жазу PBW теоремасы үшін қажетті коммутацияны алу үшін де қолданыла алатындығын ескеріңіз.[6]

Тарих

Зал жиынтықтары ұсынылды Маршалл Холл жұмысына негізделген Филип Холл топтар бойынша.[3] Кейіннен, Вильгельм Магнус ретінде пайда болатындығын көрсетті өтірік алгебра фильтрациясымен байланысты тегін топ берілген төменгі орталық серия. Бұл корреспонденция түрткі болды коммутатор сәйкестік топтық теория байланысты Филипп Холл және Эрнст Витт.

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

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

  1. ^ Холл, Филипп (1934), «Премьер-қуат тәртібі топтарының теориясына үлес», Лондон математикалық қоғамының еңбектері, 36: 29–95, дои:10.1112 / plms / s2-36.1.29
  2. ^ В.Магнус, (1937) «Über Beziehungen zwischen höheren Kommutatoren», Дж. Грелле 177, 105-115.
  3. ^ а б Холл, Маршалл (1950), «Еркін топтардағы жалған сақиналар мен жоғары коммутаторларға негіз», Американдық математикалық қоғамның еңбектері, 1 (5): 575–581, дои:10.1090 / S0002-9939-1950-0038336-7, ISSN  0002-9939, МЫРЗА  0038336
  4. ^ X. Вено, (1978) «Algèbres de Lie libres et monoïdes libres», Математикадан дәрістер, 691 , Springer – Verlag
  5. ^ а б c Гай Меланчон, (1992) «Холл ағаштары мен холл сөздерінің комбинаторикасы ", Комбинаторлық теория журналы, 59А(2) 285–308 бб.
  6. ^ Гай Меланчон және К.Ройтенауэр (1989), «Линдон сөздері, еркін алгебралар мен араласулар», Канадалық математика журналы. 41, No4, 577-591 б.