Plactic monoid - Plactic monoid

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

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

Определение

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

Генераторы - это буквы алфавита
Отношения элементарные преобразования Кнута yzx ≡ yxz в любое время Икс < у ≤ z и xzy ≡ zxy в любое время Икс ≤ у < z.

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

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

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

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

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

Кольцо Tableau

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

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

Рост

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

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

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

Смотрите также

Китайский моноид

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

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