Littlewood–Richardson härskar

Inom matematik är Littlewood –Richardson-regeln en kombinatorisk beskrivning av de koefficienter som uppstår när man sönderdelar en produkt av två Schur-funktioner som en linjär kombination av andra Schur-funktioner. Dessa koefficienter är naturliga tal, som Littlewood–Richardson-regeln beskriver som att de räknar vissa sneda tablåer . De förekommer i många andra matematiska sammanhang, till exempel som mångfald i sönderdelningen av tensorprodukter av finita dimensionella representationer av allmänna linjära grupper, eller i sönderdelningen av vissa inducerade representationer i representationsteorin för den symmetriska gruppen , eller i området för algebraisk kombinatorik som handlar om unga tablåer och symmetriska polynom .

Littlewood–Richardson-koefficienter beror på tre partitioner , säg , av vilka och beskriver Schur-funktionerna som är multiplicerad, och ger Schur-funktionen vars koefficient är i den linjära kombinationen; med andra ord är de koefficienterna så att

Littlewood–Richardson-regeln säger att är lika med antalet Littlewood-Richardson-tablåer med sned form och vikten .

Historia

Tyvärr är Littlewood-Richardson-regeln mycket svårare att bevisa än vad man först misstänkte. Författaren fick en gång höra att Littlewood-Richardson-regeln hjälpte till att få män på månen men bevisades inte förrän efter att de kom dit.

Gordon James ( 1987 )

Littlewood–Richardson-regeln uttalades först av DE Littlewood och AR Richardson ( 1934 , sats III s. 119) men även om de hävdade det som ett sats bevisade de det bara i några ganska enkla specialfall. Robinson ( 1938 ) hävdade att han kompletterade sina bevis, men hans argument hade luckor, även om det var så dunkelt skrivet att dessa luckor inte märktes på en tid, och hans argument återges i boken (Littlewood 1950 ) . Några av luckorna fylldes senare av Macdonald (1995) . De första rigorösa bevisen för regeln gavs fyra decennier efter att den hittades, av Schützenberger ( 1977 ) och Thomas (1974) , efter att den nödvändiga kombinatoriska teorin utvecklats av C. Schensted ( 1961 ), Schützenberger ( 1963 ) och Knuth (1963 ) . 1970 ) i ​​deras arbete med Robinson–Schensted-korrespondensen . Det finns nu flera korta bevis på regeln, såsom ( Gasharov 1998 ) och ( Stembridge 2002 ) med Bender-Knuth-involutioner . Littelmann (1994) använde Littelmanns vägmodell för att generalisera Littlewood–Richardson-regeln till andra halvenkla Lie-grupper.

Littlewood-Richardson-regeln är ökänd för antalet fel som dök upp innan dess fullständiga, publicerade bevis. Flera publicerade försök att bevisa det är ofullständigt, och det är särskilt svårt att undvika fel när man gör handberäkningar med det: även det ursprungliga exemplet i DE Littlewood och AR Richardson (1934) innehåller ett fel.

Littlewood–Richardson tablåer

En tablå av Littlewood–Richardson

En Littlewood–Richardson-tablå är en skev semistandard-tablå med den ytterligare egenskapen att sekvensen som erhålls genom att sammanfoga dess omvända rader är ett gitterord (eller gitterpermutation), vilket betyder att i varje initial del av sekvensen vilket nummer som helst förekommer minst lika ofta som talet . En annan ekvivalent (men inte helt uppenbart så) karaktärisering är att tablån själv, och varje tablå som erhålls från den genom att ta bort ett antal av dess kolumner längst till vänster, har en svagt minskande vikt. Många andra kombinatoriska föreställningar har hittats som visar sig stämma överens med Littlewood–Richardson-tablåer och kan därför också användas för att definiera Littlewood–Richardson-koefficienterna.

Ännu en Littlewood–Richardson-tablå

Exempel

Betrakta fallet att , och . Då kan det faktum att härledas från det faktum att de två tablåerna som visas till höger är de enda två Littlewood– Richardsons tablåer med formen och vikten . Eftersom den sista rutan på den första icke-tomma raden i skevningsdiagrammet bara kan innehålla en post 1, måste hela den första raden fyllas med post 1 (detta är sant för alla Littlewood–Richardson-tablåer); i den sista rutan i den andra raden kan vi bara placera en 2:a genom kolumnstränghet och det faktum att vårt gitterord inte kan innehålla någon större post innan det innehåller en 2. För den första rutan i den andra raden kan vi nu antingen använda en 1:a eller en 2. När den posten väl är vald, måste den tredje raden innehålla de återstående posterna för att göra vikten (3,2,1), i en svagt ökande ordning, så vi har inget val kvar längre; i båda fallen visar det sig att vi hittar en Littlewood–Richardson-tablå.

En mer geometrisk beskrivning

Villkoret att sekvensen av poster som läses från tablån i en något märklig ordning från ett gitterord kan ersättas med ett mer lokalt och geometriskt tillstånd. Eftersom det i en semistandard tablå aldrig förekommer lika poster i samma kolumn, kan man numrera kopiorna av vilket värde som helst från höger till vänster, vilket är deras förekomstordning i sekvensen som ska vara ett gitterord. Kalla numret så associerat med varje post dess index, och skriv en post i med index j som i [ j ]. Om nu någon Littlewood–Richardson-tablå innehåller en post med index j , då bör den posten i [ j ] förekomma i en rad strikt under den för (vilket säkert också förekommer, eftersom posten i − 1 förekommer minst lika ofta som posten i gör). Faktum är att posten i [ j ] också bör förekomma i en kolumn inte längre till höger än samma post (som vid första anblicken verkar vara vara ett strängare villkor). Om vikten av Littlewood-Richardson-tablån är fastställd i förväg, kan man bilda en fast samling av indexerade poster, och om dessa är placerade på ett sätt som respekterar de geometriska begränsningarna, utöver dem för halvstandardtablåer och villkoret som indexerade kopior av samma poster bör respektera höger-till-vänster-ordning av indexen, då är de resulterande tablåerna garanterat Littlewood–Richardson-tablåer.

En algoritmisk form av regeln

Littlewood–Richardson som nämnts ovan ger ett kombinatoriskt uttryck för individuella Littlewood–Richardson-koefficienter, men ger ingen indikation på en praktisk metod för att räkna upp Littlewood–Richardson-tablåerna för att hitta värdena för dessa koefficienter. För givna finns det faktiskt inget enkelt kriterium för att avgöra om några Littlewood–Richardson-tablåer med formen och av vikt existerar överhuvudtaget (även om det finns ett antal nödvändiga villkor, av vilka det enklaste är ); därför verkar det oundvikligt att man i vissa fall måste gå igenom en noggrann sökning, bara för att finna att det inte finns några lösningar.

Icke desto mindre leder regeln till en ganska effektiv procedur för att bestämma den fullständiga nedbrytningen av en produkt av Schur-funktioner, med andra ord för att bestämma alla koefficienter för fasta λ och μ, men varierande ν. Detta fixerar vikten av Littlewood–Richardson-tablåerna som ska konstrueras och den "inre delen" λ av deras form, men lämnar den "yttre delen" ν fri. Eftersom vikten är känd är uppsättningen av indexerade poster i den geometriska beskrivningen fast. Nu för successiva indexerade poster kan alla möjliga positioner som tillåts av de geometriska begränsningarna prövas i en bakåtspårningssökning . Posterna kan prövas i stigande ordning, medan de bland lika poster kan prövas genom minskande index. Den senare punkten är nyckeln till effektiviteten av sökproceduren: posten i [ j ] är då begränsad till att vara i en kolumn till höger om men nej längre till höger än (om sådana poster finns). Detta begränsar kraftigt uppsättningen av möjliga positioner, men lämnar alltid minst en giltig position för ; sålunda kommer varje placering av en post att ge upphov till minst en komplett Littlewood–Richardson-tablå, och sökträdet innehåller inga återvändsgränder.

En liknande metod kan användas för att hitta alla koefficienter för fasta λ och ν, men varierande μ.

Littlewood–Richardson-koefficienter

Littlewood–Richardson-koefficienterna c
ν λμ
visas på följande sätt som är relaterade till varandra:

eller ekvivalent c
ν λμ
är den inre produkten av s ν och s λ s μ .
där σ μ är klassen av Schubert-varianten av en Grassmannian motsvarande μ .
  • c
    ν λμ
    är antalet gånger den irreducibla representationen V λ V μ av produkten av symmetriska grupper S | λ | × S | μ | förekommer i begränsningen av representationen V v av S | ν | till S | λ | × S | μ | . Med Frobenius reciprocitet är detta också antalet gånger som V ν förekommer i representationen av S | ν | inducerad från V λ V μ .
  • c
    ν λμ
    uppträder i sönderdelningen av tensorprodukten ( Fulton 1997 ) av två Schur-moduler (irreducerbara representationer av speciella linjära grupper )
  • c
    ν λμ
    är antalet standard Young-tablåer med formen ν / μ som är jeu de taquin ekvivalenta med någon fast standard Young-tablå med formen λ .
  • c
    ν λμ
    är antalet Littlewood–Richardson-tablåer med formen ν / λ och vikten μ .
  • c
    ν λμ
    är antalet bilder mellan μ och ν/λ.

Speciella fall

Pieris formel

Pieris formel , som är specialfallet med Littlewood–Richardson-regeln i fallet när en av partitionerna bara har en del , säger att

där S n är Schur-funktionen för en partition med en rad och summan är över alla partitioner λ som erhålls från μ genom att lägga till n element till dess Ferrers-diagram , inga två i samma kolumn.

Rektangulära skiljeväggar

Om båda partitionerna är rektangulära till formen är summan också multiplicitetsfri ( Okada 1998 ). Fixa a , b , p och q positiva heltal med p q . Beteckna med partitionen med p delar av längden a . Partitionerna som indexerar icke-triviala komponenter i dessa partitioner med längden så att

Till exempel,

Schur functions rectangular example.png

.

Generaliseringar

Minskade Kronecker-koefficienter för den symmetriska gruppen

Den reducerade Kronecker-koefficienten för den symmetriska gruppen är en generalisering av till tre godtyckliga Young-diagram , vilket är symmetriskt under permutationer av de tre diagrammen.

Skew Schur-funktioner

Zelevinsky (1981) utökade Littlewood-Richardson-regeln till att snedvrida Schur-funktioner enligt följande:

där summan är över alla tablåer T på μ/ν så att för alla j är sekvensen av heltal λ+ω( T j ) icke-ökande, och ω är vikten.

Newell-Littlewood-nummer

Newell-Littlewood-tal definieras från Littlewood-Richardson-koefficienter genom det kubiska uttrycket

Newell-Littlewood-tal ger några av tensorproduktmultiplikheterna av finita dimensionella representationer av klassiska Lie-grupper av typerna .

Det icke-försvinnande villkoret på Young diagramstorlekar till

Newell-Littlewood-tal är generaliseringar av Littlewood-Richardson-koefficienter i den meningen att

Newell-Littlewood-tal som involverar ett Young-diagram med endast en rad följer en regel av Pieri-typ: är antalet sätt att ta bort rutor från (från olika kolumner), lägg sedan till rutor (till olika kolumner) för att göra .

Newell-Littlewood-tal är strukturkonstanter för en associativ och kommutativ algebra vars grundelement är partitioner, med produkten . Till exempel,

Exempel

Exemplen på Littlewood–Richardson-koefficienter nedan ges i termer av produkter av Schur-polynomen S π , indexerade med partitioner π, med hjälp av formeln

Alla koefficienter med ν som mest 4 ges av:

  • 00 S S π = S π för vilken π som helst. där S =1 är Schur-polynomet för den tomma partitionen
  • 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

De flesta av koefficienterna för små partitioner är 0 eller 1, vilket i synnerhet händer när en av faktorerna har formen S n eller S 11...1 , på grund av Pieris formel och dess transponerade motsvarighet. Det enklaste exemplet med en koefficient större än 1 händer när ingen av faktorerna har denna form:

  • S 21 S 21 = S 42 + S 411 + S 33 + 2 S 321 + S 3111 + S 222 + S 2211 .

För större partitioner blir koefficienterna mer komplicerade. Till exempel,

  • 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 3 + 54511 _ _ 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 43341 +1 S 43341 +1 S 42341 + S 42222 + S 422211 + S 3333 +2 S 33321 + S 333111 + S 33222 + S 332211 med 34 termer och total multiplicitet 62, och den största koefficienten är 4
  • S 4321 S 4321 är en summa av 206 termer med den totala multipliciteten är 930, och den största koefficienten är 18.
  • S 54321 S 54321 är en summa av 1433 termer med total multiplicitet 26704, och den största koefficienten (den för S 86543211 ) är 176.
  • S 654321 S 654321 är en summa av 10873 termer med total multiplicitet är 1458444 (så att medelvärdet för koefficienterna är mer än 100, och de kan vara så stora som 2064).

Det ursprungliga exemplet som gavs av Littlewood & Richardson (1934 , s. 122-124) var (efter att ha korrigerat för 3 tablåer de hittade men glömde att inkludera i slutsumman)

  • 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 + 1 + 2 S 3 + 2 S 25 54211 + S 541111 + S 5332 + S 53311 + 2 S 53221 + S 532111 + S 4432 + S 44311 + 2 S 44221 + S 442111 + S 43321 + S 4322 + S 1422 + S 4322

med 26 termer som kommer från följande 34 tablåer:

....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 ....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 ....1 ...2 ...2 ...2 ... ... ... ... ... .1 .3 . .12 .12 .1 .2 .2 2 1 1 23 2 22 13 1 3 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

Att beräkna skeva Schur-funktioner är liknande. Till exempel är de 15 Littlewood–Richardson-tablåerna för ν=5432 och λ=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 .23 12 13 22 12 23 13 12 24 14 14 22 23 33 13 34

   so 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 ( 9 Fulton , p. 64).

Anteckningar

externa länkar

  • Ett onlineprogram som bryter ned produkter från Schur-funktioner med hjälp av Littlewood–Richardson-regeln