В математике , то правило Литтлвуда-Ричардсон является комбинаторным описанием коэффициентов , которые возникают при разложении произведения двух функций Шуры в виде линейной комбинации других функций Шуры. Эти коэффициенты являются натуральными числами, которые в правиле Литтлвуда – Ричардсона описываются как подсчет определенных перекосов таблиц . Они возникают во многих других математических контекстах, например , в виде кратности в разложении тензорных произведений из конечномерных представлений общих линейных групп , или в разложении некоторых индуцированных представлений в теории представлений симметрической группы, или в области алгебраической комбинаторики, имеющей дело с таблицами Юнга и симметричными многочленами .
Коэффициенты Литтлвуда – Ричардсона зависят от трех разбиений , скажем, из которых а также описывают умножаемые функции Шура, и дает функцию Шура, коэффициент которой является коэффициентом линейной комбинации; другими словами, это коэффициенты такой, что
Правило Литтлвуда – Ричардсона гласит, что равно количеству таблиц Литтлвуда – Ричардсона косой формы и веса .
История
Гордон Джеймс ( 1987 )
Правило Литтлвуда – Ричардсона было впервые сформулировано Д. Е. Литтлвудом и А. Р. Ричардсоном ( 1934 , теорема III, стр. 119), но, хотя они заявили его как теорему, они доказали его только в некоторых довольно простых частных случаях. Робинсон ( 1938 ) утверждал, что завершил их доказательство, но в его аргументах были пробелы, хотя они были написаны настолько неясно, что эти пробелы не были замечены в течение некоторого времени, и его аргумент воспроизведен в книге ( Littlewood 1950 ). Некоторые из пробелов позже были заполнены Макдональдом (1995) . Первые строгие доказательства этого правила были даны через четыре десятилетия после его открытия Шютценбергером ( 1977 ) и Томасом (1974) , после того как необходимая комбинаторная теория была развита К. Шенстедом ( 1961 ), Шютценбергером ( 1963 ) и Кнутом ( 1970 ) в своей работе над перепиской Робинсона – Шенстеда . В настоящее время существует несколько коротких доказательств этого правила, таких как ( Гашаров, 1998 ) и ( Стембридж, 2002 ), с использованием инволюций Бендера-Кнута . Литтельманн (1994) использовал модель путей Литтельмана для обобщения правила Литтлвуда – Ричардсона на другие полупростые группы Ли.
Правило Литтлвуда – Ричардсона известно количеством ошибок, появившихся до его полного опубликованного доказательства. Несколько опубликованных попыток доказать его неполные, и особенно трудно избежать ошибок при ручных вычислениях с ним: даже оригинальный пример в DE Littlewood и AR Richardson ( 1934 ) содержит ошибку.
Таблицы Литтлвуда – Ричардсона
Таблица Литтлвуда – Ричардсона - это косая полустандартная таблица с дополнительным свойством, что последовательность, полученная путем конкатенации ее перевернутых строк, является решетчатым словом (или решеточной перестановкой), что означает, что в каждой начальной части последовательности любое число встречается не реже, чем число . Другая эквивалентная (хотя и не совсем очевидная) характеристика состоит в том, что сама таблица и любая таблица, полученная из нее путем удаления некоторого числа ее крайних левых столбцов, имеет слабо убывающий вес. Было обнаружено множество других комбинаторных понятий, которые, как оказалось, находятся в противоречии с таблицами Литтлвуда – Ричардсона и, следовательно, могут также использоваться для определения коэффициентов Литтлвуда – Ричардсона.
Пример
Рассмотрим случай, когда , а также . Тогда тот факт, что можно вывести из того факта, что две таблицы, показанные справа, являются единственными двумя таблицами формы Литтлвуда – Ричардсона. а вес . В самом деле, поскольку последний прямоугольник в первой непустой строке косой диаграммы может содержать только запись 1, вся первая строка должна быть заполнена записями 1 (это верно для любой таблицы Литтлвуда – Ричардсона); в последнем поле второй строки мы можем разместить только 2 по строгости столбца и тот факт, что наше слово решетки не может содержать какой-либо более крупный элемент, прежде чем оно будет содержать 2. Для первого поля второй строки мы теперь можем использовать либо 1 или 2. Как только эта запись выбрана, третья строка должна содержать оставшиеся записи, чтобы сделать вес (3,2,1), в слабо возрастающем порядке, так что у нас больше не остается выбора; в обоих случаях оказывается, что мы действительно находим таблицу Литтлвуда – Ричардсона.
Более геометрическое описание
Условие, что последовательность записей, считываемых из таблицы в несколько своеобразном порядке, образует слово решетки, может быть заменено более локальным и геометрическим условием. Поскольку в полустандартной таблице одинаковые записи никогда не встречаются в одном столбце, можно пронумеровать копии любого значения справа налево, что является их порядком появления в последовательности, которая должна быть словом решетки. Назовите номер, связанный таким образом с каждой записью, ее индексом и запишите запись i с индексом j как i [ j ]. Теперь, если некоторая таблица Литтлвуда – Ричардсона содержит записьс индексом j , то эта запись i [ j ] должна находиться в строке строго ниже, чем у(что, безусловно, также происходит, поскольку запись i - 1 встречается не реже, чем запись i ). Фактически, запись i [ j ] также должна находиться в столбце не дальше правее той же самой записи.(что на первый взгляд кажется более строгим условием). Если вес таблицы Литтлвуда – Ричардсона фиксирован заранее, то можно сформировать фиксированный набор индексированных записей, и если они будут размещены с соблюдением этих геометрических ограничений в дополнение к полустандартным таблицам и условию, при котором индексированные копии одинаковых записей должны соответствовать порядку индексов справа налево, тогда результирующие таблицы гарантированно будут таблицами Литтлвуда – Ричардсона.
Алгоритмическая форма правила
Таблица Литтлвуда – Ричардсона, как указано выше, дает комбинаторное выражение для отдельных коэффициентов Литтлвуда – Ричардсона, но не дает никаких указаний на практический метод перечисления таблиц Литтлвуда – Ричардсона, чтобы найти значения этих коэффициентов. Действительно, для данного не существует простого критерия, позволяющего определить, существуют ли какие-либо таблицы Литтлвуда – Ричардсона формы и веса существуют вообще (хотя есть ряд необходимых условий, простейшее из которых ); поэтому кажется неизбежным, что в некоторых случаях нужно пройти тщательный поиск только для того, чтобы обнаружить, что решения не существует.
Тем не менее, правило приводит к довольно эффективной процедуре для определения полного разложения произведения функций Шура, другими словами, для определения всех коэффициентов при фиксированных λ и μ, но при изменении ν. Это фиксирует вес таблиц Литтлвуда – Ричардсона, которые необходимо построить, и «внутреннюю часть» λ их формы, но оставляет «внешнюю часть» ν свободной. Поскольку вес известен, набор индексированных записей в геометрическом описании фиксирован. Теперь для последовательных проиндексированных записей все возможные позиции, разрешенные геометрическими ограничениями, можно попробовать при поиске с возвратом . Записи можно пробовать в возрастающем порядке, в то время как среди равных записей их можно пробовать, уменьшая индекс. Последний пункт является ключом к эффективности процедуры поиска: тогда запись i [ j ] ограничивается столбцом справа от, но не дальше вправо, чем (если такие записи есть). Это сильно ограничивает набор возможных позиций, но всегда оставляет хотя бы одну допустимую позицию для; таким образом, каждое размещение записи приведет по крайней мере к одной полной таблице Литтлвуда – Ричардсона, а дерево поиска не содержит тупиков.
Аналогичным методом можно найти все коэффициенты при фиксированных λ и ν, но при изменении μ.
Коэффициенты Литтлвуда – Ричардсона
Коэффициенты Литтлвуда – Ричардсона cν
λμ проявляются следующими взаимосвязанными способами:
- Они являются структурными константами для произведения в кольце симметрических функций относительно базиса функций Шура
- или эквивалентно cν
λμ является скалярным произведением s ν и s λ s μ .
- Они выражают косые функции Шура через функции Шура
- сν
λμ появляются как числа пересечения на грассманиане :
- где σ μ - класс многообразия Шуберта грассманиана, соответствующий μ .
- cν
λμ - количество раз неприводимое представление V λ ⊗ V μ произведения симметрических групп S | λ | × S | μ | появляется в ограничении представления V ν группы S | ν | к S | λ | × S | μ | . По взаимности Фробениуса это также число раз, которое V ν встречается в представлении S | ν | индуцированный из V λ ⊗ V μ . - сν
λμ появляются в разложении тензорного произведения ( Fulton 1997 ) двух модулей Шура (неприводимых представлений специальных линейных групп)
- cν
λμ - количество стандартных таблиц Юнга формы ν / μ , которые jeu de taquin эквивалентны некоторой фиксированной стандартной таблице Юнга формы λ . - cν
λμ - количество таблиц Литтлвуда – Ричардсона формы ν / λ и веса μ . - cν
λμ - количество изображений между μ и ν / λ.
Особые случаи
Формула Пиери
Формула Пиери , которая является частным случаем правила Литтлвуда – Ричардсона в случае, когда одно из разбиений имеет только одну часть , утверждает, что
где S n - функция Шура разбиения с одной строкой, а сумма берется по всем разбиениям λ, полученным из μ путем добавления n элементов к его диаграмме Феррерса , а не двух в одном столбце.
Прямоугольные перегородки
Если обе перегородки имеют прямоугольную форму, сумма также не зависит от кратности ( Okada 1998 ). Зафиксируем натуральные числа a , b , p и q с p q . Обозначим черезперегородка из p частей длины a . Разделы, индексирующие нетривиальные компоненты эти перегородки с длиной такой, что
Например,
.
Обобщения
Приведенные коэффициенты Кронекера симметрической группы
Приведенный коэффициент Кронекера симметрической группы является обобщением к трем произвольным диаграммам Юнга , который симметричен относительно перестановок трех диаграмм.
Косые функции Шура
Зелевинский (1981) распространил правило Литтлвуда – Ричардсона на искажение функций Шура следующим образом:
где сумма ведется по всем таблицам T на μ / ν, таким что для всех j последовательность целых чисел λ + ω ( T ≥ j ) не возрастает, а ω - вес.
Числа Ньюэлла-Литтлвуда
Числа Ньюэлла-Литтлвуда определяются из коэффициентов Литтлвуда-Ричардсона кубическим выражением [1]
Числа Ньюэлла-Литтлвуда дают некоторые из кратностей тензорного произведения конечномерных представлений классических групп Ли типов.
Условие ненулевого размера диаграмм Юнга приводит к
Числа Ньюэлла-Литтлвуда являются обобщением коэффициентов Литтлвуда-Ричардсона в том смысле, что
Числа Ньюэлла-Литтлвуда, которые включают диаграмму Юнга только с одной строкой, подчиняются правилу типа Пиери: количество способов удалить коробки из (из разных столбцов), затем добавьте ящики (в разные столбцы) сделать . [1]
Числа Ньюэлла-Литтлвуда - это структурные константы ассоциативной и коммутативной алгебры, базисными элементами которой являются разбиения с произведением . Например,
Примеры
Примеры коэффициентов Литтлвуда-Ричардсона, приведенные ниже, даны в терминах произведений многочленов Шура S π , индексированных разбиениями π, с использованием формулы
Все коэффициенты с ν не более 4 определяются по формуле:
- S 0 S π = S π для любого π. где S 0 = 1 - многочлен Шура пустого разбиения
- S 1 S 1 = S 2 + S 11
- S 2 S 1 = S 3 + S 21
- S 11 S 1 = S 111 + S 21
- S 3 S 1 = S 4 + S 31
- S 21 S 1 = S 31 + S 22 + S 211
- S 2 S 2 = S 4 + S 31 + S 22
- S 2 S 11 = S 31 + S 211
- S 111 S 1 = S 1111 + S 211
- S 11 S 11 = S 1111 + S 211 + S 22
Большинство коэффициентов для небольших разбиений равны 0 или 1, что, в частности, происходит, когда один из факторов имеет форму S n или S 11 ... 1 , из-за формулы Пиери и ее транспонированного аналога. Самый простой пример с коэффициентом больше 1 происходит, когда ни один из факторов не имеет такой формы:
- S 21 S 21 = S 42 + S 411 + S 33 + 2 S 321 + S 3111 + S 222 + S 2211 .
Для больших разделов коэффициенты усложняются. Например,
- S 321 S 321 = S 642 + S 6411 + S 633 + 2 S 6321 + S 63111 + S 6222 + S 62211 + S 552 + S 5511 + 2 S 543 +4 S 5421 +2 S 54111 +3 S 5331 +3 S 5322 + 4 S 53211 + S 531111 +2 S 52221 + S 522111 + S 444 +3 S 4431 +2 S 4422 +3 S 44211 + S 441111 +3 S 4332 +3 S 43311 +4 S 43221 +2 S 432111 + S 42222 + S 422211 + S 3333 +2 S 33321 + S 333111 + S 33222 + S 332211 с 34 членами и общей кратностью 62, а наибольший коэффициент равен 4
- S 4321 S 4321 - это сумма 206 членов с общей кратностью 930 и наибольшим коэффициентом 18.
- S 54321 S 54321 представляет собой сумму 1433 членов с общей кратностью 26704, а наибольший коэффициент (коэффициент S 86543211 ) равен 176.
- S 654321 S 654321 представляет собой сумму 10873 членов с общей кратностью 1458444 (таким образом, среднее значение коэффициентов больше 100, и они могут достигать 2064).
Первоначальный пример, приведенный Литтлвудом и Ричардсоном (1934 , стр. 122-124), был (после исправления трех таблиц, которые они нашли, но забыли включить в окончательную сумму)
- S 431 S 221 = S 652 + S 6511 + S 643 + 2 S 6421 + S 64111 + S 6331 + S 6322 + S 63211 + S 553 + 2 S 5521 + S 55111 + 2 S 5431 + 2 S 5422 + 3 S 54211 + S 541111 + S 5332 + S 53311 + 2 S 53221 + S 532111 + S 4432 + S 44311 + 2 S 44221 + S 442111 + S 43321 + S 43222 + S 432211
с 26 терминами, происходящими из следующих 34 таблиц:
.... 11 .... 11 .... 11 .... 11 .... 11 .... 11 .... 11 .... 11 .... 11 ... 22 ... 22 ... 2 ... 2 ... 2 ... 2 ... ... ....3. .23 .2 .3. .22 .2 .2 3 3 2 2 3 23 2 3 3.... 1 .... 1 .... 1 .... 1 .... 1 .... 1 .... 1 .... 1 .... 1 ... 12 ... 12 ... 12 ... 12 ... 1 ... 1 ... 1 ... 2 ... 1.23 .2 .3. .23 .22 .2 .1 .2 3 2 2 2 3 23 23 2 3 3.... 1 .... 1 .... 1 .... 1 .... 1 .... 1 .... 1 .... 1 ... 2 ... 2 ... 2 ... ... ... ... ... .1 .3. .12 .12 .1 .2 .2 2 1 1 23 2 22 13 13 2 2 3 3 2 2 3 3.... .... .... .... .... .... .... .... ... 1 ... 1 ... 1 ... 1 ... 1 ... ... ... .12 .12 .1 .2 .2 .11 .1 .1 23 2 22 13 1 22 12 12 3 3 2 2 3 23 2 3 3
Вычисление косых функций Шура аналогично. Например, 15 таблиц Литтлвуда – Ричардсона для ν = 5432 и λ = 331 таковы:
... 11 ... 11 ... 11 ... 11 ... 11 ... 11 ... 11 ... 11 ... 11 ... 11 ... 11 ... 11 .. .11 ... 11 ... 11... 2 ... 2 ... 2 ... 2 ... 2 ... 2 ... 2 ... 2 ... 2 ... 2 ... 2 ... 2 .. .2 ... 2 ... 2.11 .11 .11 .12 .11 .12 .13 .13 .23 .13 .13 .12 .12 .23 .2312 13 22 12 23 13 12 24 14 14 22 23 33 13 34
поэтому S 5432/331 = Σ cν
λμ S μ = S 52 + S 511 + S 4111 + S 2221 + 2 S 43 + 2 S 3211 + 2 S 322 + 2 S 331 + 3 S 421 ( Fulton 1997 , стр. 64).
Заметки
- ^ а б Гао, Шилян; Ореловиц, Гидон; Йонг, Александр (18.05.2020). «Числа Ньюэлла-Литтлвуда». arXiv : 2005.09012v1 [ math.CO ].
Рекомендации
- Фултон, Уильям (1997), таблицы Янга , Тексты студентов Лондонского математического общества, 35 , Cambridge University Press , стр. 121, ISBN 978-0-521-56144-0, MR 1464693
- Gasharov, Веселины (1998), "Короткое доказательство правила Литтлвуда-Ричардсон" , Европейский журнал комбинаторика , 19 (4): 451-453, DOI : 10,1006 / eujc.1998.0212 , ISSN 0195-6698 , MR 1630540
- Джеймс, Гордон (1987), "Теория представлений симметрических групп", Конференция Аркаты по представлениям конечных групп (Арката, Калифорния, 1986) , Proc. Симпозиумы. Чистая математика, 47 , Провиденс, Род-Айленд: Американское математическое общество , стр. 111–126, MR 0933355
- Кнут, Дональд (1970), "Перестановка, матрица и обобщен Юнга" , Тихоокеанский журнал математика , 34 (3): 709-727, DOI : 10,2140 / pjm.1970.34.709 , ISSN 0030-8730 , М.Р. 0272654
- Литтельманн, Питер (1994), "Правило Литтлвуда-Ричардсона для симметризуемых алгебр Каца-Муди" (PDF) , Invent. Математика. , 116 : 329-346, Bibcode : 1994InMat.116..329L , DOI : 10.1007 / BF01231564 , S2CID 85546837
- Литтлвуд, Дадли Э. (1950), Теория групповых характеров и матричных представлений групп , AMS Chelsea Publishing, Providence, RI, ISBN 978-0-8218-4067-2, MR 0002127
- Литтлвуд, Делавэр; Ричардсон, AR (1934), «Групповые персонажи и алгебра», Философские труды Лондонского королевского общества. Серия А, содержащих документы математического или физического характера , Королевское общество, 233 (721-730): 99-141, Bibcode : 1934RSPTA.233 ... 99L , DOI : 10.1098 / rsta.1934.0015 , ISSN 0264-3952 , JSTOR 91293
- Макдональд, И.Г. (1995), Симметричные функции и многочлены Холла , Оксфордские математические монографии (2-е изд.), The Clarendon Press Oxford University Press, ISBN 978-0-19-853489-1, MR 1354144 , архивируются с оригинала на 2012-12-11
- Окада, Soichi (1998), "Применение незначительных формул суммирования к прямоугольной формы представлений классических групп", Journal алгебры , 205 (2): 337-367, DOI : 10.1006 / jabr.1997.7408 , ISSN 0021-8693 , М.Р. 1632816
- Робинсон, Г. де Б. (1938), "О представлениях симметрической группы", American Journal математики , The Johns Hopkins University Press, 60 (3): 745-760, DOI : 10,2307 / 2371609 , ISSN 0002- 9327 , JSTOR 2371609 Zbl 0019.25102
- Шенстеда, С. (1961), "Серия увеличения и уменьшения подпоследовательности" , Canadian Journal математики , 13 : 179-191, DOI : 10,4153 / CJM-1961-015-3 , ISSN 0008-414X , МР 0121305
- Шютценберж, МП (1963), "Quelques Замечание в ипе конструкции де Шенстед" , Mathematica Scandinavica , 12 : 117-128, DOI : 10,7146 / math.scand.a-10676 , ISSN 0025-5521 , МР 0190017[ постоянная мертвая ссылка ]
- Schützenberger, Marcel-Paul (1977), "La correance de Robinson" , Combinatoire et représentation du groupe symétrique (Actes Table Ronde CNRS, Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976) , Lecture Notes in Mathematics, 579 , Berlin, New Йорк: Springer-Verlag ., стр 59-113 , DOI : 10.1007 / BFb0090012 , ISBN 978-3-540-08143-2, MR 0498826
- Стембридж, Джон Р. (2002), «Краткое доказательство правила Литтлвуда-Ричардсона» (PDF) , Electronic Journal of Combinatorics , 9 (1): Note 5, 4 pp. (Electronic), doi : 10.37236 / 1666 , ISSN 1077-8926 , MR 1912814
- Thomas, Glânffrwd P. (1974), Алгебры Бакстера и функции Шура , Ph.D. Диссертация, Суонси: Университетский колледж Суонси
- ван Леувен, Марк А.А. (2001), «Правило Литтлвуда-Ричардсона и связанная с ним комбинаторика» (PDF) , Взаимодействие комбинаторики и теории представлений , MSJ Mem., 11 , Tokyo: Math. Soc. Япония, стр. 95–145, MR 1862150
- Зелевинский, А.В. (1981), "Обобщение правила Литтлвуда-Ричардсона и соответствия Робинсона-Шенстеда-Кнута", Журнал алгебры , 69 (1): 82–94, DOI : 10.1016 / 0021-8693 (81) 90128 -9 , ISSN 0021-8693 , MR 0613858
Внешние ссылки
- Онлайн-программа , разлагающая произведения функций Шура с использованием правила Литтлвуда – Ричардсона.