[PDF] ASYMPTOTICS FOR THE NUMBER OF STANDARD TABLEAUX OF

View - Download ASYMPTOTICS FOR THE NUMBER OF STANDARD TABLEAUX OF

Previous PDF

Next PDF

ASYMPTOTICS FOR THE NUMBER OF STANDARD TABLEAUX OF

SKEW SHAPE AND FOR WEIGHTED LOZENGE TILINGS

ALEJANDRO H. MORALES, IGOR PAK, AND MARTIN TASSY

Abstract.We prove and generalize a conjecture in [MPP4] about the asymptotics of

1pn!f=, wheref=is the number of standard Young tableaux of skew shape=which

have stable limit shape under the 1=pnscaling. The proof is based on the variational principle on the partition function of certain weighted lozenge tilings.

1.Introduction

In enumerative and algebraic combinatorics,Young tableauxare fundamental objects that have been studied for over a century with a remarkable variety of both results and applica- tions to other elds. The asymptotic study of the number of standard Young tableaux is an interesting area in it own right, motivated by both probabilistic combinatorics (longest in- creasing subsequences) and representation theory. This paper is a surprising new advance in this direction, representing a progress which until recently could not be obtained by existing tools.

1.1.Main results.Let us begin by telling the story behind this paper. Denote byf==

SYT(=) the number of standard Young tableaux of skew shape=. There isFeit's deter- minant formulaforf=, which can also be derived from the Jacobi{Trudy identity for skew shapes. In some cases there are multiplicative formulas forf=, e.g. thehook-length formula (HLF) when=?, see also [MPP3]. However, in general it is dicult to use Feit's formula to obtain even the rst order of asymptotics, since there is no easy way to diagonalize the corresponding matrices. It was shown in [Pak2] by elementary means, that whenj=j=Nand1;`()spN, we have: c

N1f=2N!cN2;

wherec1;c2>0 are universal constants which depend only ons. Improving upon these estimates is of interest in both combinatorics and applications (cf. [MPP3, MPP4]). In [MPP4], much sharper bounds onc1;c2were given, when the diagramsandhave a limit shape =under 1=pNscaling in both directions (see below). Based on observations in special cases, we conjectured that there is always a limit lim N!11N logf=2N! in this setting. The main result of this paper is a proof of this conjecture.Date: April 30, 2018. 1

2 ALEJANDRO H. MORALES, IGOR PAK, AND MARTIN TASSY

Theorem 1.1.Let(N)and(N)be two partition sequences with strong stable (limit) shapes and, respectively(seex2.4 for precise denitions). Let(N):=(N)=(N), such thatj(N)j=N+o(N=logN). Then 1N logf(N)12 NlogN !c( =)asN! 1; for some xed constantc( =). The constantc( =) is given in Corollary 4.6. The proof of the theorem is even more interesting perhaps than one would expect. In [Nar], Naruse developed a novel approach to countingf=, via what is now known as theNaruse hook-length formula(NHLF): (1.1)f==N!X

D2E(=)Y

u2nD1h (u); whereE(=)[] jjis a collection of certain subsets of the Young diagram [], andh(u) is the hook-length atu2. The (usual) hook-length formula is a special case=?. Let us mention thatE(=) can be viewed as the set of certain particle congurations, giving it additional structure [MPP3]. AlthoughE(=) can have exponential size, the NHLF can be useful in getting the asymp- totic bounds [MPP4]. It has been reproved and studied further in [MPP1, MPP2, Kon, NO], including theq-analogues and generalizations to trees and shifted shapes. Seex2.3 for the precise statements. The next logical step was made in [MPP3], where a bijection betweenE(=) and lozenge tilings of a certain region was constructed. Thus, the number of standard Young tableaux f =can be viewed as a statistical sum of weighted lozenge tilings. In a special case ofthick hooksthis connection is especially interesting, as the corresponding weighted lozenge tilings were previously studied in [BGR] (see the example below). Now, there is a large literature on random lozenge tilings of the hexagon and its relatives in connection with thearctic circlephenomenon, see [CEP, CKP, Ken]. In this paper we adapt thevariational principleapproach in these papers to obtain the arctic circle behavior for the weighted tilings as well. Putting all these pieces together implies Theorem 1.1. Let us emphasize that the approach in this paper can be used to obtain certain probabilistic information on random SYTs of large shapes, e.g. in [MPP3,x8] we show how to compute asymptotics of various path probabilities. However, in the absence of a direct bijective proof of NHLF, our approach cannot be easily adapted to obtain limit shapes of SYTs as Sun has done recently [Sun] (see alsox6.5).

1.2.Thick hooks.Let= (a+c)b+c,=ab,N=j=j=c(a+b+c), wherea;b;c0.

This shape is called thethick hookin [MPP4]. The HLF applied to the 180 degree rotation of=gives: f ==N!(a)(b)(c)2(a+b+c)2(a+b)(a+c)(b+c)(a+b+ 2c): Here thesuperfactorial(n) = 1!2!(n1)! is the integer value of theBarnesG-function, see e.g. [AsR]. On the other hand,E(=) in this case in bijection with the set of lozenge tilings of the hexagonH(a;b;c) =habcabci, and the weight is simply a product of a linear function on horizontal lozenges (see below). The number of lozenge tilings in this cases is STANDARD YOUNG TABLEAUX AND WEIGHTED LOZENGE TILINGS 3 famously counted by theMacMahon box formulafor the numberP(a;b;c) ofsolid partitions which t into a [abc] box:

E(=)=P(a;b;c) =(a)(b)(c)(a+b+c)(a+b)(b+c)(a+c);

see e.g. [Sta2,x7.21]. It was noticed by Rains (see [MPP3,x9.5]), that in this example our weights are special cases of multiparameter weights studied in [BGR] in connection with closed formulas forq-Racah polynomials, cf.x6.2. Now, Theorem 1.1 in this case does not give anything new, of course, as existence of the limit whenc! 1,a=c!andb=c!, follows from either the Vershik{Kerov{Logan{ Shepphook integralof the strongly stable shapes [MPP4,x6.2] (see also [Rom]), or from the asymptotics of the superfactorial: log(n) =12 n2logn34 n2+ 2nlogn+O(n): This gives the exact valuec( =) as an elementary function of (;).

1.3.Thick ribbons.Letk:=2k=k, wherek= (k1;k2;:::;2;1). This skew shape

is a strong stable shape. The main theorem implies that there is a limit 1N logfk12 NlogN !Cask! 1; whereN=jkj=k(3k1)=2. This proves a conjecture in [MPP4,x13.7]. In that paper it was shown that0:3237C 0:0621. Both lower and upper bounds are further improved in [MPP5], but the exact value ofChas no known closed formula. This paper describesCas solution of a certain very involved variational problem (see Corollary 4.6 andx6.5).

1.4.Structure of the paper.We start with Section 2 which reviews the notation and known

results on tilings, standard Young tableaux and limit shapes. In Section 3 we state our main technical result (Theorem 3.3) on the variational principle for weighted lozenge tilings, whose proof is postponed until Section 5. In the technical Section 4 we deduce Theorem 1.1 from the variational principle. We conclude with nal remarks and open problems in Section 6.

2.Background and notation

2.1.Tilings and height functions.LetRbe a connected region in the triangular lattice.

One can view a lozenge tiling ofRas a stepped surface inR3where the rst two coordinates are the coordinates of the points in the lattice and the third coordinates is the height function h() of a lozenge tiling dened in the following way: For every edge (x;y) inR,h(y)h(x) = 1 if (x;y) is a vertical edge andh(y)h(x) = 0 otherwise. In fact, there is a one to one correspondence between tilings of a given region and functions which verify this property dened up to a constant. Using this bijection, we will denote byth the tiling associated to a given height functionhand we will do all the subsequent reasoning using height functions rather than tilings. We extend the denition of height functions to any region of the lattice as follows: for general setsS, we say that a functionh:S!Z is a height function if its restriction on each simply connected component ofSis a height function.

4 ALEJANDRO H. MORALES, IGOR PAK, AND MARTIN TASSY

yx Figure 1.A regionRof the triangular lattice. A lozenge tiling of that region and the associated admissible stepped curve (ASC).x Figure 2.Left: height function of the maximal tiling centered atxwith heightg(x). Right: the local move on lozenges. LetRbe a lozenge tileable region. We say that the three dimensional curve obtained by traveling along@Rand recording the height of each point is an admissible stepped curve (ASC). Lemma 2.1.LetRbe a connected region in the triangular grid and letgbe a height function on a subsetSofR, such that for allx= (x1;x2);y= (y1;y2)2S: (2.1)g(y)g(x)maxfy1x1;y2x2g: Thengcan be extended into a height function on the whole regionR. The lemma is a variation on [PST, Thm. 4.1] (see also [Thu]). It can be viewed as a Lipschitz extendability property on height functions (cf. [CPT]). We include a quick proof for completeness. Proof.Note thathx(y) =g(x)+maxfy1x1;y2x2gis the height function of the maximal tiling centered atxand with heightg(x) atx(see Figure 2). Deneh(y) := minx2Shx(y). Since the minimum of two height functions is still a height function, we conclude thathis itself a height function. Moreover, the inequality (2.1)) implies that for all pairsx;y2S: g(y)hx(y). We conclude thath(y) =g(y), which implies the result. Finally, we need the following standard proposition which will be useful later in this article. Proposition 2.2(see [Thu]).Every two lozenge tilings of a simply connected regionRhave equal number of lozenges of each type. In other words, the number of lozenges of each type depends only onRand not on the tiling. This follows, e.g. since every two tilings ofRare connected by local moves which do not change the number of lozenges of each type (see Figure 2). STANDARD YOUNG TABLEAUX AND WEIGHTED LOZENGE TILINGS 5

2.2.Skew shapes and tableaux.Let= (1;:::;r) and= (1;:::;s) denote integer

partitions of length`() =rand`() =s. The size of the partition is denoted byjj. We denote by0theconjugate partition, and by [] the correspondingYoung diagram(in English notation). Thehook lengthh(x;y) of a cell (x;y)2is dened ash(x;y) := xx+yy+ 1. It counts the number of cells directly to the right and directly below (x;y) in []. Askew shape=is dened as the dierence of two shapes. LetN=j=j. We always assume that the skew shape is connected. Astandard Young tableau(SYT) of shape=is a bijective functionT: [=]! f1;:::;Ng, increasing in rows and columns. The number of such tableaux is denoted byf=. This counts the number of linear extensions of the poset dened on [=], with cells increasing downward and to the right.

2.3.Naruse's hook-length formula.As mentioned in the introduction, the Naruse hook-

length formula (1.1) gives a positive formula forf=. It was restated in [MPP3] in terms of lozenge tilings as follows.yx ;dd Figure 3.ASC and two lozenge tilings corresponding to excited diagrams in

Naruse's formula.

Let=be a skew shape withNcells. Let

;dbe the ASC in the plane with upper side given byand bounded below by four sides of the hexagon of vertical heightd=`()`() (see Figure 3). LetH=be the set of height functionshthat extend ;dsuch that the corresponding lozenge tilingthhas no horizontal lozenges with coordinates (x;xk) for xk > x. The weight of a horizontal lozenge ofthat position (x;y) is the hook length h (x;y) :=xx+0yy+ 1. The weight of a tilingthis the product of the weights of its horizontal lozenges and we denote it by hooks (th), hooks (th) :=Y 2thh (x;y): Theorem 2.3(Naruse [Nar]; lozenge tiling version [MPP3,x7]). (2.2)f==N!Q (x;y)2h(x;y)X h2H=hooks (th): Example 2.4.The skew shape 332=21 has ve height functions that extend

21;1:Formula (2.2) yields in this case

f

332=21=5!542322544 + 541 + 541 + 511 + 311= 16:

6 ALEJANDRO H. MORALES, IGOR PAK, AND MARTIN TASSY

(N)=pN Figure 4.The sequence of shapes(N)has a strongly stable shapewith j(N)j= area()N+o(N=logN).

2.4.Stable shapes.Let : [0;a]![0;b] be a non-increasing continuous function. Assume

a sequence of partitionsf(N)gsatises the following property (pNL) <[(N)]<(pN+L) ;for someL >0; where [] denotes the function giving the boundary of the Young diagram of. In this setting, we say thatf(N)ghas a strong stable shape and denote it by(N)! . Note that`((N)), `((N)0) =O(pN). Such shapes are calledbalanced(see e.g. [FeS]). Let ;: [0;a]![0;b] be non-increasing functions, and suppose thatarea( =) = 1. LetfvN=(N)=(N)gbe a sequence of skew shapes with the strongly stable shape =, i.e. (N)! ,(N)!and satisfy the condition (2.3)j(N)j= area()N+o(N=logN): Denote byC=C( =)R2+the region between the curves. One can viewCas the stable shape of the skew diagrams. Finally, dene thehook function~:C !R+to be the limit of the scaled function of the hooks: (2.4)~(x;y) := limN!11pN h(N)bxpNc;bypNc:

3.Variational principle for weighted lozenge tilings

Lozenge tilings is a dimer model and the existence of a variational principle which governs the limiting behavior of dimers under the uniform measure is a well known result. Our goal in this section will be to extend it to the case where we add weights to each tilings that depend on the position and the type of the lozenge tiles.

3.1.Weighted tilings and smooth weights.LetDR2be a connected domain in the

plane, and letfw(i):D!Rgi3be three real valued functions corresponding to the weight of each type of lozenge. For a regionRD, dene theweightof a height functionhonR associated to the weight functionsw= (w(1);w(2);w(3)) as (3.1) wt(h) :=Y

2thexp(w(i)(x;y));

STANDARD YOUNG TABLEAUX AND WEIGHTED LOZENGE TILINGS 7 where (x;y) are the coordinates of the center of the tileandi2 f1;2;3gis the type of the lozenge tile:123 Given a weight functionw, the partition function associated to an ASC is dened as: Z( ;w) :=X h2H wt(h); whereH is the set of height functions which extend . LetN be the size ofH and let L (i)( ) be the (common) number of typeilozenges in each height function that extends Denition 3.1.LetDbe a domain inR2. A sequence of weight functionsfwngn2Nconverges to a piecewise smooth function:D!R3if it has the following property: () limn!1sup (x1;x2)2Dkwn(nx1;nx2)(x1;x2)k1= 0:

3.2.The variational principle.Our goal in this section is to establish a variational prin-

ciple for weighted tilings. We recall the unweighted version of the variational principle from [Ken, Thm. 9]. Let Lip [0;1]be the set of 1-Lipschitz functionsf:R2!Rthat satisfy

0@x1f; @x2f;1@x1f@x2f1

everywhere except on a set of Lebesgue measure 0. Let (3.2)(s;t) :=1 (s) + (t) + (1st) where () is theLobachevsky function, see e.g. [TM].

Theorem 3.2([Ken]).Letf

ngn2Nbe a sequence of ASC. Suppose that1n nconverges to a closed curve inR3in the`1norm asn! 1. Then: lim n!11n 2logN n!(gmax); wheregmax:U!Ris the only extension of inLip[0;1]that maximizes the following integral: (g) :=ZZ U rg(x1;x2)dx1dx2; andUis the region enclosed by the projection of . Moreover, for all >0the height function of a random tiling chosen from the weighted measure associated townon height functions with boundary n, stays withinofgmaxwith probability!1asn! 1. The proof of this result is sketched in [Ken] and is the analogue of an earlier result for dominoes [CKP]. The argument in the latter paper extends to our setting of lozenges. We are now ready to state the variational principle for the weighted case. The proof is postponed to Section 5.

Theorem 3.3(Weighted variational principle).Letf

ngn2Nbe a sequence of ASC, and let fwngn2Nbe a sequence of weight functions converging to a function. Suppose that1n n converges to a closed curved inR3in the`1norm asn! 1. Then we have: lim n!11n

2logZ(H

n;wn) = (fmax):

8 ALEJANDRO H. MORALES, IGOR PAK, AND MARTIN TASSY

Herefmax:U!Ris the only extension of

inLip[0;1]which maximizes the following integral: (3.3) (f) :=ZZ U (rf) +L(x1;x2;rf) dx 1dx2; whereUis the region enclosed by the projection of , and (3.4)L(x1;x2;rf) :=(x1;x2)(@x1f;@x2f;1@x1f@x2f): Moreover, for all >0, the height function of a random tiling chosen from the weighted measure associated townon height functions with boundary n, stays withinoffmaxwith probability tending to1.

4.From lozenge tilings to standard Young tableaux

In this section we apply the weighted variational principle to prove the main result on asymptotics of the number of skew SYT of skew shapes with strongly stable shapes. Recall thatfN=(N)=(N)gis a sequence of skew shapes with the strongly stable shape =as dened in Section 2.4.

4.1.The weight function of hook lengths.In order to apply the weighted variational

principle we need weight functions that converge in the sense of Denition 3.1. In order to obtain a partition function that matches Naruse's formula (2.2), the natural choice of weight function onC( =) is the following w

N(x;y) :=0;0;log(h(N)(x;y)=pN):

Denote by wt

N(h) the corresponding weight on height functions. Then wt(h) = (pN)j(N)jhooks(N)(th): However for this choice of weight function, logh(N)(x;y) can be very small for points (x;y) near the border of the shape(N); see Figure 5. In this regime, Property () might not hold. To x this, we change the weight function to cap these small values as follows. For >0 and (x;y) inC( =), let w

N(x;y) :=

0;0;maxlogh(N)(x;y)=pN

;log

Denote by wt

N(h) the corresponding weights on a height functionh. Similarly, denote byZN andZNthe corresponding partition functions associated to weightswNandwNrespectively.

4.2.From lozenge tilings to counting tableaux.We rst show that the weighted varia-

tional principle, Theorem 3.3, applies toZN. This implies that lim N!11N logZN=c(); for some constantc() depending onand the shapes and(Lemma 4.1). We then show that logZNconverges to logZNas!0 (Lemma 4.2). Finally, we conclude that lim N!11N logZN=c; for some constantcdepending on and(Corollary 4.4). In Section 4.3, we use this last result to prove Theorem 1.1. STANDARD YOUNG TABLEAUX AND WEIGHTED LOZENGE TILINGS 9 (N)=pN; pN (N)=pN Figure 5.Left: For points (x;y) near the top border of the region the values of logh(x;y) are small and can aect convergence of the weight function.

Right: The hook measured inh(N)(x;y).

Lemma 4.1.We have:

lim N!11N

ZN= sup

f2Lip[0;1] (f); where()is the integral dened in(3.3)for the limiting weight function (x;y) :=

0;0;maxlog~(x;y);log

Proof.First, we verify that the weight functionwN(x;y) converges to(x;y), in the sense of Denition 3.1. We verify property (). By convergence of the sequence of shapes, forNlarge enough, either bothh(N)(x;y)=pNand~(x;y) dened in (2.4) are smaller than or equal or both are greater or equal to. In the rst case, we havewN(x;y) =(x;y) = (0;0;log), and property () vacuously holds.

In the second case we have that for all (x;y)2D:

wN(xpN;y pN)(x;y)=log1pN h(N)bxpNc;bypNclog~(x;y) k1pN h(N)bxpNc;bypNc~(x;y); where the inequality follows from thek-Lipschitz property of the log, for some constantk. From the denition of hook lengths (see Figure 5), we also have:1pN h(N)bxpNc;bypNc~(x;y)p2 (N)=pN 1: Thus, by convergence of the sequence of shapes, we have: lim N!1 wN(pNx; pNy)(x;y)limN!1kp2 (N)=pN 1= 0:

This proves property ().

By construction of the sequence of partitionsf(N)g, we have that the corresponding sequencef (N);pN gof ASC satises that1pN (N);pN converges to. Thus the weighted variational principle, Theorem 3.3, applies giving (4.1) lim N!11N logZN= (fmax); as desired.

10 ALEJANDRO H. MORALES, IGOR PAK, AND MARTIN TASSY

Lemma 4.2.Let >0, there exists a functionF()satisfyinglim!0F() = 0such that logZN= logZN+F()N.

Proof.By the mediant inequality we have:

(4.2) ZNZ

Nmaxhwt

N(h)wt

N(h): Outside of a border strip of(N)of heightbpNcthe weights will not change. The hooks on the remaining lozenges in the strip are lower bounded by their depth. So the RHS in (4.2) can be bounded as follows, (4.3) max hwt

N(h)wt

N(h)(elog)NQ

bpNc k=1(elogk=(pN))pN =(elog)Nexp PbpNc k=1pNlogk=(pN) We can rewrite the denominator on the RHS above as (4.4) exp0 @bpNcX k=1pNlogk pN 1 A = exp0 N pN bpNcX k=1logk pN 1 A =eNR

0logxdx:

Finally, we denoteR

0logxdxby the functionF(). This function satises lim!0F() = 0.

quotesdbs_dbs47.pdfusesText_47

[PDF] losange nombre complexe

[PDF] losange périmètre

[PDF] losange propriété

[PDF] losange rectangle

[PDF] Loterie

[PDF] loterie green card 2018

[PDF] Lotissement de 4 maisons

[PDF] lotus blanc resort

[PDF] loubain ville

[PDF] loubaki j'invoque l'eau

[PDF] loubaki loussalat facebook

[PDF] loubaki loussalat j'invoque l'eau

[PDF] loubaki slam france

[PDF] louis antoine de bougainville

[PDF] Louis Aragon