В математике правило Литтлвуда –Ричардсона представляет собой комбинаторное описание коэффициентов, возникающих при разложении произведения двух функций Шура в линейную комбинацию других функций Шура. Эти коэффициенты являются натуральными числами, которые правило Литтлвуда–Ричардсона описывает как подсчет определенных перекошенных таблиц . Они встречаются во многих других математических контекстах, например, как кратность в разложении тензорных произведений конечномерных представлений общих линейных групп или в разложении определенных индуцированных представлений в теории представлений симметрической группы или в области алгебраической комбинаторики, имеющей дело с таблицами Юнга и симметрическими многочленами .
Коэффициенты Литтлвуда–Ричардсона зависят от трех разбиений , скажем , из которых и описывают функции Шура, которые умножаются, и дают функцию Шура, коэффициентом в линейной комбинации которой является этот; другими словами, это коэффициенты, такие что
Правило Литтлвуда–Ричардсона гласит, что равно числу таблиц Литтлвуда–Ричардсона косой формы и веса .
К сожалению, правило Литтлвуда–Ричардсона доказать гораздо сложнее, чем предполагалось изначально. Автору когда-то сказали, что правило Литтлвуда–Ричардсона помогло отправить людей на Луну, но не было доказано до тех пор, пока они там не оказались.
Гордон Джеймс (1987)
Правило Литтлвуда–Ричардсона впервые было сформулировано DE Littlewood и AR Richardson (1934, теорема III, стр. 119), но хотя они и утверждали его как теорему, они доказали его только в некоторых довольно простых частных случаях. Робинсон (1938) утверждал, что завершил их доказательство, но его аргумент имел пробелы, хотя он был настолько неясно написан, что эти пробелы не были замечены в течение некоторого времени, и его аргумент воспроизведен в книге (Littlewood 1950). Некоторые из пробелов были позже заполнены Macdonald (1995). Первые строгие доказательства правила были даны через четыре десятилетия после того, как оно было обнаружено, Schützenberger (1977) и Thomas (1974), после того, как необходимая комбинаторная теория была разработана C. Schensted (1961), Schützenberger (1963) и Knuth (1970) в их работе о соответствии Robinson–Schensted . В настоящее время существует несколько коротких доказательств правила, например (Gasharov 1998) и (Stembridge 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ν
λμ проявляются следующими взаимосвязанными способами:
Формула Пьери , которая является частным случаем правила Литтлвуда–Ричардсона в случае, когда одно из разбиений имеет только одну часть , утверждает, что
где S n — функция Шура разбиения с одной строкой, а сумма берется по всем разбиениям λ, полученным из μ путем добавления n элементов к его диаграмме Феррерса , причем никакие два элемента не находятся в одном столбце.
Если оба раздела имеют прямоугольную форму, сумма также не имеет кратности (Okada 1998). Зафиксируем a , b , p и q положительные целые числа с p q . Обозначим через раздел с p частями длины a . Разделы, индексирующие нетривиальные компоненты, — это разделы с длиной, такой что
Например,
.
Приведенный коэффициент Кронекера симметрической группы является обобщением на три произвольные диаграммы Юнга , которая симметрична относительно перестановок трех диаграмм.
Зелевинский (1981) расширил правило Литтлвуда–Ричардсона для искажения функций Шура следующим образом:
где сумма берется по всем таблицам T на μ/ν таким образом, что для всех j последовательность целых чисел λ+ω( T ≥ j ) не возрастает, а ω — вес.
Числа Ньюэлла-Литтлвуда определяются через коэффициенты Литтлвуда-Ричардсона с помощью кубического выражения [1]
Числа Ньюэлла-Литтлвуда дают некоторые кратности тензорного произведения конечномерных представлений классических групп Ли типов .
Условие неисчезания размеров диаграммы Юнга приводит к
Числа Ньюэлла-Литтлвуда являются обобщениями коэффициентов Литтлвуда-Ричардсона в том смысле, что
Числа Ньюэлла-Литтлвуда, включающие диаграмму Юнга только с одной строкой, подчиняются правилу типа Пьери: — это число способов удалить ящики из (из разных столбцов), а затем добавить ящики (в разные столбцы), чтобы получить . [1]
Числа Ньюэлла-Литтлвуда являются структурными константами ассоциативной и коммутативной алгебры, базисными элементами которой являются разбиения, с произведением . Например,
Примеры коэффициентов Литтлвуда–Ричардсона ниже даны в терминах произведений полиномов Шура S π , индексированных разбиениями π , с использованием формулы
Все коэффициенты, не превышающие 4, определяются по формуле:
Большинство коэффициентов для малых разбиений равны 0 или 1, что происходит, в частности, всякий раз, когда один из факторов имеет форму S n или S 11...1 , из-за формулы Пьери и ее транспонированного аналога. Простейший пример с коэффициентом больше 1 происходит, когда ни один из факторов не имеет такой формы:
Для больших разделов коэффициенты становятся сложнее. Например,
Первоначальный пример, приведенный Литтлвудом и Ричардсоном (1934, стр. 122-124), был следующим (после исправления трех таблиц, которые они нашли, но забыли включить в окончательную сумму):
с 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 ...2 ...1 ...1 ...2 ...1.23 .2 .3 . .13 .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 (Фултон 1997, стр. 64).