Increasing subsequences and the hard-to-soft edge

arXiv:math-ph/0205007v15May2002Increasingsubsequencesandthehard-to-softedgetransitioninmatrixensemblesAlexeiBorodin∗andPeterJ.Forrester†∗SchoolofMathematics,InstituteofAdvancedStudy,EinsteinDrive,PrincetonNJ08540,USA;†DepartmentofMathematicsandStatistics,UniversityofMelbourne,Victoria3010,Australia;email:[e-mail];[e-mail]lativeprobabilitiesPr(L(t)≤l)forthemaximumlengthofincreasingsubsequencesinPoissonizedensemblesofrandompermutations,randomfixedpointfreeinvolutionsandreversedrandomfixedpointfreeinvolutions.Itisshownthattheseprobabilitiesareequaltothehardedgegapprobabilityformatrixensembleswithunitary,orthogonalandsymplecticsymmetryrespectively.Thegapprobabilitiescanbewrittenasasumovercorrelationsforcertaindeterminantalpointprocesses.FromtheseexpressionsaproofcanbegiventhatthelimitingformofPr(L(t)≤l)inthethreecasesisequaltothesoftedgegapprobabilityformatrixensembleswithunitary,orthogonalandsymplecticsymmetryrespectively,therebyreclaimingtheoremsduetoBaik-Deift-JohanssonandBaik-Rains.1IntroductionLetSNdenotethesetofallpermutationsof{1,2,...,N}.Letπ∈SNandconsiderasubsequenceofimagepoints{π(i1),π(i2),...,π(ik)}where1≤i1···ik≤N.Suchasubsequenceisreferredtoasanincreasingsubsequenceoflengthkifπ(i1)π(i2)···π(ik).Foragivenπ,letLN(π)denotethemaximumlengthofalltheincreasingsubsequences.ThequestionofthedistributionofLN(π)=:LN,whenπischosenatrandomfromauniformdistributiononSN,wasposedintheearly1960’sbyUlam.In1999thequestionwasansweredbyBaik,DeiftandJohansson[3],whoprovedlimN→∞PrLN−2√NN1/6≤s=F2(s),(1.1)whereF2(s)isthescaledcumulativedistributionofthelargesteigenvaluesforlargerandomHermitianmatriceswithcomplexGaussianentries(technicallymatricesfromtheGaussianunitaryensemble(GUE))[35].Oneshouldconsult[2]forareviewoftheworkonUlam’sproblemculminatingintheBaik-Deift-Johanssontheorem.Inthecourseofproving(1.1),theexponentialgeneratingfunctionofPr(LN≤l),e−tDl(t),Dl(t):=∞XN=0tNN!Pr(LN≤l),(1.2)wasintroduced.ThisquantityitselfisthecumulativedistributionofanaturalquantityduetoHammer-sley(seee.g.[1]).ThusconsidertheunitsquarewithpointschosenatrandomaccordingtoaPoissonprocessofratet.Formacontinuouspiecewiselinearpath,withpositiveslopewheredefined,connecting(0,0)to(1,1)andonlychangingslopeatapoint.LetL(t)denotethelengthofthelongestsuch“up/right”path,wherethelengthisdefinedasthenumberofPoissonpointsinthepath.Toseetherelationto(1.2),labelthepoints1,...,Nfromlefttoright,thenattachasecondlabel1,...,Nfrombottomtotop.InthiswayeacharrayofNpointsisassociatedwithapermutation,andfurthermorethefactthatthepointsarechosenfromaPoissonprocessimpliestheuniformdisitributiononthesetof1permutationsofNsymbols.Up/rightpathscorrespondtoincreasingsubsequencesandwehavePr(L(t)≤l)=e−tDl(t).(1.3)Itwasprovedin[3]thatlimt→∞PrL(t)−2√tt1/6≤s=F2(s).(1.4)Infact(1.4)sufficestoprove(1.1),byapplyingasocalledde-Poissonizationlemma[19].Fourcompanionidentitiesto(1.4),relatingthelimitingdistributionoflongestpathsincertainup/rightpathsproblemstothelimitingdistributionofthelargesteigenvalueincertainrandomma-trixensembles,werefoundbyBaikandRains[4,5].Ofthesetwoareindependent,inthatitwasshownthattheothertwofollowascorollaries[4,Theorem2.5].Forthefirst,modifytheoriginallongestup/rightpathproblembyrequiringthatinitiallyonlytheregionbelowtheliney=1−xoftheunitsquarebefilledwithPoissonpointsofratet;thepointsabovethelinearethenspecifiedbytheimageoftheinitialpointsreflectedabouty=1−x.LetL(t)refertothelongestup/rightpathfrom(0,0)to(1,1)inthissetting.Thenonehaslimt→∞PrL(t)−2√t21/3t1/6≤s=F1(s),(1.5)whereF1(s)isthecumulativedistributionofthelargesteigenvalueforlargerandomrealsymmetricmatriceswithGaussianentries(technicallymatricesfromtheGaussianorthogonalensemble(GOE))[37].TherandomvariableL(t)isrelatedtothemaximumlengthL2Nofalldecreasingsubsequencesofrandomfixedpointfreeinvolutions(π2=π,π(i)6=i)foranyi)of{1,2,...,2N},orequivalentlyofallincreasingsubsequencesofreversedfixedpointfreeinvolutions.ThusPr(L(t)≤l)=e−t/2Dl(t),Dl(t):=∞XN=0tN2NPr(L2N≤l)(2N)!.(1.6)Forthesecondofthecompanionidentities,theoriginallongestup/rightpathproblemismodifiedbyrequiringthatinitiallyonlytheregionbelowtheliney=xoftheunitsquarebefilledwithPoissonpointsatratet,withthepointsabovethediagonalspecifiedastheimageofthesepointsreflectedabouty=x.WithL(t)referringtothelongestup/rightpathinthissetting,onehaslimt→∞PrL(t)−2√t21/3t1/6≤s=F4(s)(1.7)whereF4(s)isthescaledcumulativedistributionofthelargesteigenvalueforlargerandomHermitianmatriceswithrealquaternionelements(technicallymatricesfromtheGaussiansymplecticensemble(GSE)).WithL2Ndenotingthemaximumlengthofincreasingsubsequencesofrandomfixedpointfreeinvolutionsof{1,2,...,2N},onehasPr(L(t)≤l)=e−t/2Dl(t),Dl(t):=∞XN=0tN2NPr(L2N≤l)(2N)!.(1.8)Inthispaperwewillgivenewproofsoftheresults(1.4),(1.5)and(1.7).Theoriginalproofof(1.4)usesaRiemann-Hilbertanalysis[3].Thesubsequentproofsof(1.4)givenin[21,7]relyonprovingtheconvergenceofacertainFredholmintegraloperatordetermingPr(L(t)≤l)totheFredholmintegraloperatordeterminingF2(s).Acomb