Пластиковый моноид

В математике плактический моноид — это моноид всех слов в алфавите натуральных чисел по модулю эквивалентности Кнута . Ее элементы можно отождествить с полустандартными таблицами Юнга . Она была открыта Дональдом Кнутом ( 1970 ) (который назвал ее табличной алгеброй ), используя операцию, данную Крейгом Шенстедом ( 1961 ) в его исследовании самой длинной возрастающей подпоследовательности перестановки.

назвали его « monïde plaxique » Ласку и Шютценбергер (1981) , которые допускали в определении любой полностью упорядоченный алфавит. Этимология слова plaxique неясна; это может относиться к тектонике плит («tectonique des plaques» по-французски), поскольку элементарные отношения, генерирующие эквивалентность , допускают условную коммутацию генераторных символов: иногда они могут скользить друг по другу (по очевидной аналогии с тектоническими плитами), но не свободно.

Определение

Плактический моноид над некоторым полностью упорядоченным алфавитом (часто положительным целым числом) — это моноид следующего представления :

• Генераторы — буквы алфавита.
• Отношения представляют собой элементарные преобразования Кнута yzx ≡ yxz всякий раз, когда x < y ⩽ z , и xzy ≡ zxy всякий раз, когда x ≡ y < z .

Эквивалентность Кнута

Два слова называются эквивалентными по Кнуту, если они представляют один и тот же элемент плактического моноида, или, другими словами, если одно можно получить из другого последовательностью элементарных преобразований Кнута.

Некоторые свойства сохраняются благодаря эквивалентности Кнута.

• Если слово является словом обратной решетки , то таковым является и любое слово Кнута, эквивалентное ему.
• Если два слова эквивалентны по Кнуту, то эквивалентными являются и слова, полученные удалением их крайних правых максимальных элементов, а также слова, полученные удалением их крайних левых минимальных элементов.
• Эквивалентность Кнута сохраняет длину самой длинной неубывающей подпоследовательности и, в более общем смысле, сохраняет максимум суммы длин k непересекающихся неубывающих подпоследовательностей для любого фиксированного k .

Соответствие полустандартным таблицам Юнга

Умножение элемента табличной формы (38)(1257) с помощью генератора 4, проиллюстрированного с использованием обозначений таблицы Юнга:
• Используя пластические соотношения, (1257)*4 = 5*(1247)
• (38)*5 = 8*(35), поэтому (5) заменяет (8) во второй строке
• (8) создает третью строку
• Тогда продукт имеет табличную форму (8)(35)(1247).

Каждое слово является эквивалентом Кнута слову уникальной полустандартной таблицы Юнга (это означает, что каждая строка не убывает, а каждый столбец строго возрастает) в том же упорядоченном алфавите, где таблица может читаться по строкам или по столбцам. Таким образом, элементы плактического моноида можно отождествить с полустандартными таблицами Юнга, которые, следовательно, также образуют моноид.

Умножение слова полустандартной таблицы Юнга слева на генератор эквивалентно вставке Шенстеда в таблицу Юнга. В порядке строк слово таблицы эквивалентно произведению все более длинных неубывающих последовательностей образующих. Новый генератор можно вставить на свое место, либо добавив его, если он больше, либо повторно применив пластические отношения для перемещения элемента вне последовательности в следующую строку. В последнем случае неупорядоченный элемент заменяет крайнюю левую запись, большую, чем она, в каждой строке, а смещенный элемент затем вставляется в следующую строку.

Поскольку вставка Шенстеда сохраняет таблицы Юнга, это дает индуктивное доказательство того, что элементы плактического моноида могут быть записаны в стандартной форме, соответствующей таблице Юнга, и конструкция определяет натуральный продукт полустандартных таблиц.

Дразнящая игра

Основная статья: Дразнящая игра

Две косые таблицы Юнга эквивалентны Jeu de taquin тогда и только тогда, когда их прочтение слов эквивалентно Кнуту, т.е. соответствует эквивалентным элементам пластической группы. Это дает альтернативное определение произведения пластической группы непосредственно в терминах таблиц Юнга. Две таблицы можно умножить, нарисовав их обе вокруг пустого прямоугольника, чтобы сформировать перекос, и используя слайды «Игры с такином», чтобы исправить это.

Кольцо «Таблица»

Кольцо таблицы является моноидным кольцом пластического моноида, поэтому оно имеет Z -базис, состоящий из элементов пластического моноида, с тем же произведением, что и в пластикмоноиде.

Существует гомоморфизм плактического кольца алфавита кольцу многочленов (с переменными, индексированными в алфавите), переводящий любую таблицу в произведение переменных ее элементов, что соответствует абелианизации плактической полугруппы.

Рост

Производящая функция плактического моноида в алфавите размера n равна

$\Gamma (t)={\frac {1}{(1-t)^{n}}}{\frac {1}{(1-t^{2})^{n(n-1)/2}}}\$

показывая, что существует полиномиальный рост размерности ${\frac {n(n+1)}{2}}$.

См. также

• Китайский моноид
• Переписка Робинсона-Шенстеда
• Дразнящая игра

Ссылки

• Дюшан, Жерар; Кроб, Дэниел (1994), «Моноиды, похожие на пластический рост» , Слова, языки и комбинаторика, II (Киото, 1992) , World Sci. Publ., River Edge, Нью-Джерси, стр. 124–142, MR   1351284 , Zbl   0875.68720.
• Фултон, Уильям (1997), Таблицы Янга , Студенческие тексты Лондонского математического общества, том. 35, Издательство Кембриджского университета , ISBN  978-0-521-56144-0 , МР   1464693 , Збл   0878.14034
• Кнут, Дональд Э. (1970), «Перестановки, матрицы и обобщенные таблицы Юнга» , Pacific Journal of Mathematics , 34 (3): 709–727, doi : 10.2140/pjm.1970.34.709 , ISSN   0030-8730 , MR   0272654
• Ласку, Ален; Леклерк, Б.; Тибон, JY., «Плактический моноид» , заархивировано из оригинала 18 июля 2011 г. {{citation}}: Отсутствует или пусто |title= ( помощь )
• Литтельманн, Питер (1996), «Пластическая алгебра для полупростых алгебр Ли» , «Достижения в области математики» , 124 (2): 312–331, doi : 10.1006/aima.1996.0085 , ISSN   0001-8708 , MR   1424313
• Ласку, Ален; Шуценбергер, Марсель-П. (1981), «Le monoid plaxique» (PDF) , Некоммутативные структуры в алгебре и геометрической комбинаторике (Неаполь, 1978) , Quaderni de La Ricerca Scientifica, vol. 109, Рим: CNR, стр. 129–156, МР   0646486
• Лотер, М. (2011), Алгебраическая комбинаторика слов , Энциклопедия математики и ее приложений, том. 90, с предисловием Жана Берстеля и Доминика Перрена (перепечатка издания в твердом переплете 2002 г.), Cambridge University Press, ISBN  978-0-521-18071-9 , Збл   1221,68183
• Шенстед, К. (1961), «Самые длинные возрастающие и убывающие подпоследовательности» , Canadian Journal of Mathematics , 13 : 179–191, doi : 10.4153/CJM-1961-015-3 , ISSN   0008-414X , MR   0121305 , S2CID   247197258
• Шютценбергер, Марсель-Поль (1997), «Для плаксического моноида» , Математика, информатика и гуманитарные науки (140): 5–10, doi : 10.4000/msh.2764 , ISSN   0995-2314 , MR   1627563

Дальнейшее чтение

• Грин, Джеймс А. (2007), Полиномиальные представления GL _n , Конспекты лекций по математике, том. 830, С приложением К. Эрдмана, Дж. Грина и М. Шокера о соответствии Шенстеда и путях Литтельмана (2-е исправленное и дополненное изд.), Берлин: Springer-Verlag , ISBN  978-3-540-46944-5 , Збл   1108.20044