You are an expert at summarizing long articles. Proceed to summarize the following text: 
we start with a regular lattice ; on each site @xmath4 lives a random energy @xmath5 , drawn independently from site to site from a common distribution @xmath6 . we assume @xmath6 is continuous and normalized to unity , i.e. @xmath7 . for any choice of the set of @xmath5 s we obtain an energy landscape , i.e. , a topological space ( defined through nearest neighbors on the lattice ) with an energy for each element . for a given realization of the landscape , a site @xmath4 is a local minimum if @xmath8 where @xmath9 denotes any nearest neighbour sites of @xmath4 . hereafter we shall denote by @xmath2 the number of local minima on this landscape . for any given realization of the landscape , one can formally express @xmath2 as @xmath10 where the product runs over all nearest neighbours @xmath9 of site @xmath4 and @xmath11 is the heaviside theta function . we are interested in computing the probability distribution @xmath12 of the total number of local minima ( or equivalently that of the maxima ) . the first important observation is that the distribution @xmath12 is completely independent of the energy distribution @xmath6 . to see this , we formally express the distribution as @xmath13 where @xmath14 is the dirac delta function . next we make a change of variable for each @xmath15 @xmath16 clearly @xmath17 is a monotonically increasing function of @xmath18 . therefore , @xmath19 . moreover , since @xmath6 is normalized to unity , the variable @xmath20 varies from @xmath21 to @xmath22 and so eq .  ( [ m2 ] ) simply becomes @xmath23 we see that the energy distribution @xmath6 simply drops out and @xmath12 , for arbitrary @xmath6 , is universal and is the same as when the ` new ' energy variable @xmath24 is drawn independently from a uniform distribution over @xmath25 $ ] . thus , the model is simplified : at each lattice site lives a random number @xmath26 $ ] drawn independently from a uniform distribution . we will refer to this model as the random minima model , for which we want to compute the distribution @xmath12 of the total number of local minima . following the mapping to the uniform distribution , it follows that the random minima model is just the continuous version of the permutation generated landscape recently studied by hivert et . they considered a set of integers @xmath27 . each of the @xmath28 permutations of this set defines a random energy landscape and they occur with equal probability . thus the energy at a site is now a discrete integer drawn uniformly from the set @xmath29 $ ] with equal probability @xmath30 . thus the statistics of the minima in the permutation generated landscape will be identical to that of the random minima model . the mean and the variance of @xmath2 are relatively straightforward to compute on an arbitrary lattice since they depend only on the local properties of the landscape . to see this , let us define the variable @xmath31 where @xmath9 runs over the nearest neighbours of @xmath4 and the @xmath24 s are independent random numbers in @xmath32 $ ] drawn from the uniform distribution . this @xmath33 is an indicator function which is 1 if site @xmath4 is a local minimum and 0 otherwise . then it follows that @xmath34 taking the average in eq . ( [ mean1 ] ) and using the translational invariance of the lattice , it follows that @xmath35^n = \frac{1}{n+1 } \label{mean2}\ ] ] where @xmath36 is the number of nearest neighbours of any site , i.e. , the co - ordination number of the lattice . this result also follows trivially from a combinatorial argument on the permutation landscape : consider the site @xmath4 with its @xmath36 neighbours . the number of ways one can arrange the integers on these @xmath37 sites with the restriction that @xmath4 is a local minimum is @xmath38 clearly . on the other hand , the total number of unrestricted configurations is @xmath39 so the probability that the site @xmath4 is a minimum is simply @xmath40 . the calculation of the variance takes a few more steps . squaring eq . ( [ mean1 ] ) and taking the average gives @xmath41 note that the @xmath33 s are correlated random variables but only over a short range . the calculation of the correlation function @xmath42 can therefore be performed by hand ( it only involves the calculation of simple integrals involving a maximum of @xmath43 sites ) . for example , in @xmath22-d , one gets @xmath44 this result has been obtained in various contexts before , such as in the calculation of the number of metastable states in @xmath22-d ising spin glass  @xcite and also in the context of the occupation time of a non - markovian sequence in @xmath22-d  @xcite . recently , the variance for the @xmath45 square lattice was computed in the permutation model by hivert et . al .  @xcite . for large @xmath3 , one gets @xmath46 in general , on any arbitrary lattice , for large @xmath3 @xmath47 where @xmath48 and @xmath49 are lattice dependent numbers that can be computed either using integrals or by combinatorics in the permutation model .    near the mean @xmath50 and within a region @xmath51 , the distribution @xmath12 is expected to be a gaussian  @xcite with mean and variance given in eq . ( [ mv ] ) @xmath52 . \label{gauss1}\ ] ] however , for @xmath2 far from the mean , one would expect deviations in @xmath12 from the gaussian form . in this paper , we are interested in the probabilities of such large deviations , i.e. , we are interested in computing the probabilities of occurrences of configurations that are far from typical . on general grounds , in the limit @xmath53 , @xmath54 but with their ratio @xmath55 fixed but arbitrary , one expects that @xmath12 has the form @xmath56 \label{ld1}\ ] ] where @xmath57 is a large deviation function . now , on a given lattice , @xmath2 can take values from @xmath21 to a maximal number @xmath58 . the upper limit follows from the fact that once a site is a local minimum , none of its nearest neighbours can be a local minimum . thus there is a nearest neighbour exclusion principle for the minima . this constraint indicates that one can not pack arbitrarily large number of minima on the lattice and there is an upper bound on the number of minima . for example , on a bipartite lattice , one can pack at most @xmath59 local minima , one at every alternate site . in particular , on a square lattice the minima will be placed on a checkerboard pattern . thus , in this case , the large deviation function @xmath57 is defined for @xmath60 . on the other hand , on a cayley tree with @xmath61 number of branches and @xmath3 sites , we will see later that @xmath62 , thus @xmath63 . as mentioned above , in the vicinity of its mean , i.e. , for @xmath64 , the distribution @xmath12 is gaussian as in eq . ( [ gauss1 ] ) . this indicates that the large deviation function @xmath57 is quadratic near @xmath65 @xmath66 such that @xmath67 \sim \exp\left[-(m - an)^2/{2bn}\right]$ ] has the required gaussian form . however , far from the mean , @xmath12 will have non - gaussian tails , indicating a departure of @xmath57 from the simple quadratic form . a knowledge of the function @xmath57 would then allow one to compute the probabilities of occurrences of atypical configurations , such as the probability of a configuration with the lowest number of minima ( e.g. @xmath68 ) or the ones with the maximal number of minima ( @xmath69 . a particular focus of this paper will be to compute the probability of a maximally packed configuration , i.e. , when @xmath70 . it follows from the general form in eq . ( [ ld1 ] ) that the probability of this maximal packing should decay exponentially with the system size for large @xmath3 , @xmath71 \sim \gamma^{-n } \label{ld2}\ ] ] where @xmath72 $ ] is a lattice dependent constant . of course , this expression also gives the scaling of the fraction of permutations which have @xmath73 local minima in the permutation landscape . it is then natural to interpret @xmath74 as the entropy cost per site to achieve maximally packed minima . we shall compute the constant @xmath75 exactly for a number of lattices . for the @xmath76 chain , we will show that @xmath77 note that this result appeared before in the context of metastable states in @xmath76 ising spin glasses at zero temperature  @xcite . furthermore , the same @xmath78 decay also appeared as the persistence probability of a @xmath76 non - markovian sequence  @xcite . for the @xmath76 case , one can also compute the full large deviation function @xmath57 ( see section  [ sec : onedimension ] ) . another lattice where we can calculate @xmath75 exactly is the cayley tree with @xmath61 branches where we show that @xmath79 where @xmath80 is the beta function . as expected , for @xmath81 , it reduces to the @xmath22-d result in eq . ( [ g1d ] ) . as @xmath61 increases , @xmath75 increases slowly and as @xmath82 , @xmath83 . a cayley tree with an infinite number of branches corresponds to a hypercubic lattice in @xmath0-dimensions in the @xmath84 limit . thus , based on these two limiting results , one expects the constant @xmath75 on any @xmath0-dimensional lattice to satisfy the bounds @xmath85 our numerical simulations for @xmath86 are consistent with these bounds . we have also been able to compute @xmath75 exactly for a two - leg ladder where we show that @xmath87^{1/3}=1.57657\dots \label{glad}\ ] ] where @xmath88 is the smallest positive root of the bessel function @xmath89 . the result in eq . ( [ glad ] ) is , of course , consistent with the general bounds in eq . ( [ bounds ] ) . we now consider these successive cases in detail . in a @xmath22-d chain of size @xmath3 , the distribution @xmath12 of the total number of local minima was computed exactly by derrida and gardner  @xcite , although they did not calculate the large deviation function @xmath57 explicitly . however , from their result for the generating function , it is easy to derive the large deviation function by a legendre transform . for the sake of completeness , we provide here a brief derivation of the @xmath22-d result , albeit by a slightly different method . it is useful to define the generating function or the partition function @xmath90 where @xmath91 is the fugacity or the weight associated with each minimum . for simplicity we consider an open chain of size @xmath3 and let @xmath92 be the value of the random variable at the @xmath3-th site . to write a recursion relation for the partition function , it is convenient to define two restricted partition functions : @xmath93 and @xmath94 denoting respectively the partition functions conditioned on the fact that the @xmath3-th site has value @xmath92 and that it is respectively a local minimum ( i.e. , @xmath95 ) or a local maximum ( @xmath96 ) . note that since we are considering an open chain , the last site ( @xmath3 ) has only one neighbour to its left , namely the @xmath97-th site . knowing the restricted partition functions , one can compute the full partition function from the relation @xmath98 . \label{pf1d}\ ] ]    the restricted partition functions satisfy a pair of simple recursion relations @xmath99\ , dy . \label{recur2}\end{aligned}\ ] ] these recursion relations can be easily understood by considering all possibilities when one adds a new site to the chain . if the new site is a minimum , we need to attach a factor @xmath91 . on the other hand , if the @xmath97-th site was a minimum and it ceases to be a minimum after the addition of the @xmath3-th site , we have to detach a factor @xmath91 . it follows from eqs . ( [ recur1 ] ) and ( [ recur2 ] ) that the restricted partition functions satisfy the boundary conditions : @xmath100 and @xmath101 . for large @xmath3 , one expects a separation of variables between @xmath20 and @xmath3 of the form , @xmath102 where @xmath103 is a function of @xmath91 only ( but independent of @xmath20 ) and the functions @xmath104 and @xmath105 satisfy the boundary conditions : @xmath106 and @xmath107 . substituting this ansatz in eqs . ( [ recur1 ] ) and ( [ recur2 ] ) and subsequently differentiating with respect to @xmath20 , we get a pair of differential equations @xmath108 diagonalizing the @xmath109 $ ] matrix , one obtains the solutions @xmath110 where @xmath48 and @xmath49 are arbitrary constants . the two boundary conditions @xmath106 and @xmath107 yield two relations between @xmath48 and @xmath49 @xmath111 eliminating @xmath48 and @xmath49 between eqs . ( [ rel1 ] ) and ( [ rel2 ] ) determines the eigenvalue @xmath103 exactly @xmath112,\quad\quad { \rm   for}\quad\quad 0\le z \le 1 \label{eigen1 } \\ & = & \frac{1}{\sqrt{z-1 } } \tan^{-1 } \left[\sqrt{z-1}\right ] \quad\quad { \rm for}\quad\quad z \ge 1 .\label{eigen2}\end{aligned}\ ] ] note that the function @xmath103 is analytic at @xmath113 . the form in eq . ( [ eigen2 ] ) is just an analytical continuation of the form in eq . ( [ eigen1 ] ) for @xmath114 .    substituting the large @xmath3 form of @xmath115 and @xmath116 in eq . ( [ pf1d ] ) , one obtains the large @xmath3 behavior of the partition function , @xmath117^{-n } \label{pfn1}\ ] ] where @xmath103 is given in eqs . ( [ eigen1 ] ) and ( [ eigen2 ] ) . substituting the anticipated form of @xmath118 $ ] in eq . ( [ pfn1 ] ) one gets @xmath119\sim [ \lambda(z)]^{-n}. \label{pfn2}\ ] ] taking the @xmath54 limit in eq . ( [ pfn2 ] ) gives @xmath120 = \ln ( \lambda(z ) ) . \label{pfn3}\ ] ] inverting via the legendre transform finally gives the large deviation function @xmath121 , \label{ld3}\ ] ] where @xmath103 is given in eqs . ( [ eigen1 ] ) and ( [ eigen2 ] ) . note that determining @xmath57 from eq . ( [ ld3 ] ) requires a knowledge of @xmath103 for all @xmath122 , thus we need both formulae of @xmath103 in eqs . ( [ eigen1 ] ) and ( [ eigen2 ] ) .     for @xmath123 in @xmath22-d obtained from eq . ( [ ld3 ] ) using mathematica.,width=377,height=264 ]    we have obtained @xmath57 from eq . ( [ ld3 ] ) using mathematica and it is displayed in fig . [ fig : ldf1d ] . since the maximal value of @xmath2 in @xmath22-d is @xmath124 , the allowed range of @xmath125 is @xmath123 . one can analytically obtain the form of @xmath57 in the three limiting cases @xmath126 , @xmath127 and @xmath128 . first let us consider the limit @xmath126 . to find @xmath57 in this limit we need to use the @xmath129 form of @xmath103 in eq . ( [ ld3 ] ) . as @xmath129 , it is easy to see from eq . ( [ eigen1 ] ) that @xmath130 . substituting this behavior in eq . ( [ ld3 ] ) and subsequently maximizing the r.h.s of eq . ( [ ld3 ] ) we find that @xmath57 diverges logarithmically , @xmath131 $ ] as @xmath126 . next we consider the @xmath127 limit . note that the mean number of minima @xmath132 in @xmath133 which follows from the general result in eq . ( [ mean2 ] ) . thus @xmath127 limit corresponds to behavior of @xmath2 near its mean and one expects a quadratic form for @xmath57 near @xmath134 . indeed this also follows from eq . ( [ ld3 ] ) . the limit @xmath127 corresponds to using the @xmath135 behavior of @xmath103 in eq . ( [ ld3 ] ) . substituting @xmath136 in eq . ( [ eigen2 ] ) and expanding in powers of @xmath137 , one gets @xmath138 . substituting this result on the r.h.s of eq . ( [ ld3 ] ) and maximizing one gets the expected quadratic behavior , @xmath139 near @xmath127 . this is thus a special case in @xmath22-d of the general behavior in eq . ( [ qua ] ) with @xmath140 and @xmath141 . finally , to derive the maximally packed limit @xmath128 , we need to use the @xmath142 behavior of @xmath103 in eq . ( [ ld3 ] ) . in this limit , it follows from eq . ( [ eigen2 ] ) that @xmath143 . using this form and maximizing the r.h.s . ( [ ld3 ] ) we get @xmath144 as @xmath128 . thus , summarizing the three limiting behaviors @xmath145 \quad\quad { \rm as}\quad\quad y\to 0 \nonumber \\ & \approx &   \frac{45}{4}\ , ( y-1/3)^2 \quad\quad { \rm as}\quad\quad y\to 1/3 \nonumber \\      & \approx &   \ln ( \pi/2 ) + 2(1/2-y)\ , \ln(\pi(1/2-y)/e ) \quad\quad { \rm as}\quad\quad y\to 1/2 . \label{limiting}\end{aligned}\ ] ] note that as one approaches the maximally packed limit @xmath128 , @xmath146 . thus , it follows from eq . ( [ ld2 ] ) that in @xmath22-d , for large @xmath3 @xmath147 the result declared in eq . ( [ g1d ] ) . in this section , we focus only on the maximally packed configuration ( where the number of minima on the lattice is maximal ) . from the general large deviation theory , we have already argued that the probability of such a configuration @xmath148 is expected to decay exponentially with the system size @xmath3 as in eq . ( [ ld2 ] ) . the goal is to compute the nontrivial constant @xmath75 . in the previous section , we have shown that in a @xmath22-d chain , @xmath149 . in this section , we compute @xmath75 exactly in a few other solvable cases , notably for a cayley tree with @xmath61 branches and also for a two - leg ladder in @xmath150-d . we consider a cayley tree with @xmath61 branches and @xmath36 generations . we label the generations by @xmath151 starting from the leaf sites at the bottom ( see fig .  [ fig : tree ] ) . the total number of sites on the tree is @xmath152 note that in the limit @xmath153 , the tree reduces to a @xmath22-d chain with @xmath154 sites . branches and @xmath155 generations . the layers are labelled @xmath156 starting with the bottom layer.,width=453 ]    at each site of this tree resides a random number @xmath24 drawn independently from the uniform distribution over @xmath32 $ ] . we want to calculate the probability of the configuration with the maximum possible number of local minima . note that if a site is a local minimum , its neighbours can not be local minima . to find the maximally packed configuration , we note that the number of sites at the bottom layer ( @xmath157 ) increases exponentially with @xmath36 as @xmath158 . thus , to achieve maximal packing , it is necessary to fill up the bottom layer ( the leaf sites ) with local minima . then the layer just above the bottom layer ( @xmath159 ) is devoid of local minima . the next layer @xmath160 ) can again be packed with local minima . thus , the maximally packed configuration is the one where alternate layers are fully packed with minima , starting with a fully packed layer at the bottom , as shown in fig . [ fig : tree ] . the total number of minima @xmath73 in this maximally packed configuration depends on whether the number of generations @xmath36 is even or odd @xmath161 for @xmath36 even , the root is not a minimum whereas for @xmath36 odd , the root is a minimum . in either case , for @xmath36 large , the total number of minima in the maximally packed configuration is proportional to the total number of sites @xmath3 , @xmath162 having identified the maximally packed configuration , we will next compute the probability of its occurrence and show that for large @xmath3 @xmath163    for simplicity , let us assume that @xmath36 is even . one can perform an identical calculation when @xmath36 is odd . for @xmath36 even , all the even layers ( labelled by @xmath164 with @xmath165 ) are devoid of local minima whereas all the odd layers ( labelled by @xmath166 with @xmath167 ) are fully packed with local minima . our aim is to write a recursion relation . for this , it is convenient to define two probabilities @xmath168 and @xmath169 defined respectively for even and odd layers . we define @xmath168 as the probability that a subtree of @xmath170 generations ( counted from the bottom of the tree ) has a random variable @xmath20 at its root and that @xmath20 is _ not _ a local minimum . on the other hand , @xmath169 is the probability that a subtree of @xmath171 generations ( again counted from the bottom of the tree ) has a random variable @xmath20 at its root and that @xmath20 is a local minima . it is then easy to see that they satisfy the recursion relations @xmath172^{\mu } \label{p1 } \\ q_{2m+1}(x ) & = & \left [ \int_x^1 p_{2m}(y ) \ , dy\right]^{\mu } \label{q1}\end{aligned}\ ] ] where @xmath165 . the recursions start with the initial condition @xmath173 . since @xmath36 is even , the root of the full tree with @xmath36 generations is not a local minima and hence the probability of the full tree is just @xmath174 given that the value at the root is @xmath20 . the probability of the maximally packed configuration is then obtained by integrating over @xmath20 at the root @xmath175 thus , we need to solve eqs . ( [ p1 ] ) and ( [ q1 ] ) and then substitute the solution for @xmath174 in eq . ( [ pmp1 ] ) to calculate @xmath176 .    to solve the nonlinear recursion relations , it is convenient to define @xmath177^{1/\mu}$ ] and @xmath178^{1/\mu}$ ] . then the recursions in eqs . ( [ p1 ] ) and ( [ q1 ] ) become @xmath179 starting with @xmath180 for @xmath181 . it follows from eqs . ( [ p2 ] ) and ( [ q2 ] ) that they satisfy the boundary conditions , @xmath182 and @xmath183 for all @xmath184 . however , @xmath185 and @xmath186 are nonzero . it is then useful to define the ratios , @xmath187 and @xmath188 so that @xmath189 , @xmath190 and @xmath191 , @xmath192 . in terms of the new functions , the recursions become @xmath193 starting with @xmath194 for @xmath181 . as @xmath195 increases , we expect that the ratio functions @xmath196 and @xmath197 will approach their respective @xmath195-independent fixed point forms @xmath198 and @xmath199 . this means that as @xmath200 , @xmath201 and @xmath202 and @xmath203 with the boundary conditions @xmath204 , @xmath205 and @xmath206 , @xmath207 . these boundary conditions will determine the eigenvalues @xmath208 and @xmath209 . differentiating eqs . ( [ f2 ] ) and ( [ g2 ] ) with respect to @xmath20 gives @xmath210 multiplying ( [ f3 ] ) by @xmath211 and ( [ g3 ] ) by @xmath212 , adding and then integrating , we find a conserved quantity @xmath213 where @xmath214 is a constant independent of @xmath20 . putting @xmath215 and using the respective boundary conditions gives @xmath216 . thus , @xmath217 and @xmath218 the common eigenvalue @xmath219 is yet to be determined . eliminating @xmath199 between eqs . ( [ f3 ] ) and ( [ com2 ] ) gives @xmath220^{\mu/(\mu+1 ) } \label{f4}\ ] ] subject to the boundary conditions @xmath204 and @xmath205 . integrating and using @xmath204 we get @xmath221 using the other boundary condition @xmath205 determines @xmath219 explicitly @xmath222 where @xmath223 is the standard beta function . the eigenfunction @xmath198 in eq . ( [ f5 ] ) can be expressed as the solution of the equation @xmath224 = \frac{x}{\mu+1}\ , b\left(\frac{1}{\mu+1},\frac{1}{\mu+1}\right ) \label{f6}\ ] ] where @xmath225 $ ] is the hypergeometric function . the other eigenfunction @xmath199 follows from eq . ( [ com2 ] ) , or simply from the symmetry @xmath226 . to check that the solutions to the original recursion relations ( [ p2 ] ) and ( [ q2 ] ) indeed converge to these fixed solutions , we have numerically solved eqs . ( [ p2 ] ) and ( [ q2 ] ) for @xmath227 . we find that the numerical solutions ( the ratio functions @xmath196 and @xmath197 ) converge to fixed point functions rather quickly after about @xmath228 or @xmath229 iterations . in fig . [ f3 ] , we compare the numerical fixed point solution ( the solution after @xmath230 iterations ) @xmath198 with the analytical solution in eq . ( [ f6 ] ) with @xmath227 . the agreement is perfect . after @xmath230 iterations , for @xmath227 , is compared to the analytical scaling function in eq . ( [ f6 ] ) obtained using mathematica . the two curves are difficult to distinguish indicating perfect agreement.,width=377,height=264 ]    to determine @xmath75 , we use eq . ( [ pmp1 ] ) and the recursion relation ( [ q2 ] ) which show that @xmath231 then we take ratios to extract the bulk contribution of the cayley tree , thereby removing artifacts coming from its surface  @xcite : as @xmath232 , we have @xmath233 and @xmath234 . eliminating @xmath185 gives a recursion for large @xmath195 @xmath235 iterating it , we obtain , for large @xmath195 , @xmath236 . substituting this result in eq . ( [ pmp2 ] ) and using @xmath237 gives our final result for large @xmath3 @xmath238    note that the recursion relation ( [ q1 ] ) is valid only for large @xmath195 . but in deriving the results above we have assumed that it holds even for small @xmath195 . even though the asymptotic result is not expected to change due to this ` initial condition ' effect , one can avoid this `` surface effect '' by appropriately defining @xmath75 as the ratio @xmath239^{\mu } dx } { \left[\int_0 ^ 1 p_n(x)dx\right]^{\mu}}. \label{gnf1}\ ] ] this definition follows from the following observation . the numerator on the r.h.s of ( [ gnf1 ] ) denotes the probability of a maximally packed configuration on a tree with @xmath37 generations . the denominator is the joint probability that the disconnected @xmath61 subtrees of @xmath36 generations are all maximally packed . thus , the ratio on the r.h.s . is just the factor by which the probability of a maximally packed configuration per site decreases when one fuses the @xmath61 number of @xmath36-generation trees and one additional root to construct a newly maximally packed configuration on a @xmath37-generation tree . but , asymptotically for large @xmath36 , this is precisely @xmath240 by the orginal definition in eq . ( [ ld2 ] ) . physically , @xmath74 is the additional entropy change when packing an extra minimum in the tree . using the recursion relations ( [ p1 ] ) , ( [ q1 ] ) in eq . ( [ gnf1 ] ) one gets @xmath241^{\mu } dx=\int_0 ^ 1    g_{n+1}^\mu(x ) dx . \label{gnf2}\ ] ] substituting @xmath242 , integrating and using @xmath205 , we get @xmath243    note that for @xmath81 , we recover the @xmath22-d result , @xmath149 . for @xmath227 , we get @xmath244 . as @xmath245 , @xmath75 converges slowly to @xmath246 . since the @xmath245 result should coincide with that on a hypercubic lattice in the infinite dimension limit , we expect that for hypercubic lattices in @xmath0 dimensions , @xmath75 is bounded , @xmath247 . as @xmath0 increases from @xmath22 to @xmath248 , @xmath75 should increase monotonically from its @xmath133 value @xmath249 to @xmath150 . our numerical solutions on @xmath0-dimensional hypercubic lattices with @xmath250 are consistent with these bounds .      on a bipartite lattice , the maximally packed configuration is the one where one places a local minimum at every alternate site . for example , on a square lattice , a maximally packed configuration has a checkerboard pattern as shown in fig . [ fig : plaque ] . let us first focus on the neighbourhood of a single local minimum . the sites at the corners of the plaquette containing this minimum are clearly not local minima . let @xmath251 , @xmath252 , @xmath253 and @xmath254 denote the values of the random variables at the four corners of the plaquette . then , given these four values , the probability that the site at the center of the plaquette is a local minimum is clearly @xmath255 where we have used the fact that the random variable at the center of the plaquette is drawn from a uniform distribution . so , the probability of the full checkerboard configuration where every alternate site is a local minimum , given the values of the random variables @xmath256 s at the sites of the other sublattice , is obtained by multiplying all the plaquettes @xmath257 where the plaquettes are labelled by @xmath9 and @xmath258 , @xmath259 , @xmath260 and @xmath261 are the four random variables at the corners of the @xmath9-th plaquette . the total number of plaquettes will also be denoted by @xmath2 since the number of plaquettes is the same as the number of local minima . to simplify , it is convenient to rotate the lattice by @xmath262 ( as shown in fig . [ fig : plaque ] ) . .,width=377 ]    we then have a plaquette model where at each corner of a plaquette lives a random variable @xmath24 drawn from a uniform distribution over @xmath32 $ ] and we are interested in calculating the product in eq . ( [ plaq2 ] ) . finally , the probability of the maximally packed configuration on the original lattice is obtained by averaging over the @xmath24 s with uniform distribution in @xmath32 $ ] @xmath263 where the angled brackets simply indicates integration over all the @xmath20 variables from @xmath21 to @xmath22 . note that this plaquette model is very general and can be extended to any bipartite lattice . also , the right hand side of eq . ( [ plaq3 ] ) is actually the probability of just one of the two checkerboard configurations , so the true @xmath148 is actually twice this amount , but to avoid unnecessary complications we shall keep to this notation .      as a simple example , for a @xmath22-d chain , one can reproduce the result @xmath149 quite easily using the plaquette representation . the number of plaquettes is clearly @xmath264 . in this case , eq . ( [ plaq3 ] ) gives @xmath265 where @xmath4 runs over every alternate sites of the original @xmath22-d chain . the quantity on the r.h.s . of ( [ cd1 ] ) can be evaluated using a simple transfer matrix approach . defining a transfer matrix via , @xmath266 , we have from eq . ( [ cd1 ] ) , assuming a closed periodic chain @xmath267   \label{cd2}\ ] ] where @xmath268 is the trace . the eigenvalue equation of the transfer matrix is @xmath269 where @xmath270 is an eigenfunction with eigenvalue @xmath219 . dividing the range of integration into @xmath271 $ ] and @xmath272 $ ] and differentiating twice , one gets @xmath273 with the boundary conditions @xmath274 and @xmath275 where @xmath276 . the solution is simply , @xmath277 where @xmath278 the largest eigenvalue is @xmath279 corresponding to @xmath280 . thus for large @xmath264 , one gets from eq . ( [ cd2 ] ) @xmath281^{n/2}\sim [ \pi/2]^{-n } \label{cd6}\ ] ] reproducing the results obtained in the previous section . another nontrivial solvable case of the plaquette model is on a two - leg ladder shown in fig . [ fig : ladder ] . it can be thought of as the first layer of the full @xmath150-d model shown on the right in fig .  [ fig : plaque ] . at the center of each plaquette lives a local minimum . let @xmath2 be the number of plaquettes . then the total number of sites in the lattice ( counting the minima at the centers ) is @xmath282 .        the probability of the maximally packed configuration in eq . ( [ plaq2 ] ) can again be computed by defining the transfer matrix , @xmath283 where @xmath284 refers to the two corners on the left of a plaquette and @xmath285 refers to the two corners on the right of a plaquette . then , @xmath267 \label{l1}\ ] ] the corresponding eigenvalue equation is now two dimensional @xmath286 which is considerably harder to solve compared to the @xmath22-d case . while one can solve the @xmath150-d eigenvalue equation directly , it is somewhat easier to first reduce it to an equivalent @xmath22-d eigenvalue problem by using the following trick . let us first define the random variable @xmath287 at the center of each plaquette @xmath4 . clearly @xmath288 where @xmath289 is the number of plaquettes . the random variables @xmath290 s are obviously correlated as two adjacent plaquettes will share two common random variables as shown in fig . [ fig : ladder1 ] .     at the center . on the right we have two adjacent plaquettes with minima @xmath291 and @xmath292 at their respective centers . the variables @xmath293 and @xmath294 are corrrelated as they share the common bond with the two elements @xmath253 and @xmath254.,width=529 ]    to evaluate the average on the r.h.s of eq . ( [ l3 ] ) we need to know the joint distribution of the @xmath290 s which are correlated ( see fig .  [ fig : ladder1 ] ) . this joint distribution can be explicitly computed . to see this , let us first compute the cumulative distribution of one single @xmath91 variable , say @xmath295 . for simplicity , we denote @xmath296 , @xmath297 etc . ( see fig . [ fig : ladder1 ] ) . evidently @xmath298 where we have used the fact that @xmath251 , @xmath252 , @xmath253 and @xmath254 are all independent random variables drawn from the uniform distribution over @xmath32 $ ] . next , let us consider the joint distribution of two consecutive @xmath91 s , say @xmath293 and @xmath294 . let us denote the random variables at the corners by @xmath251 , @xmath252 , @xmath253 , @xmath254 , @xmath299 and @xmath300 as shown in fig . [ fig : ladder1 ] . then it is easy to see that @xmath301 ^ 2\,(1-y_2)^2 . \label{l5}\end{aligned}\ ] ] in a similar way , one can construct the joint distribution of three adjacent plaquette minima @xmath302 ^ 2\ , \left[1-{\rm max}(y_2,y_3)\right]^2\ , ( 1-y_3)^2 . \label{l6}\ ] ] one can repeat the process above for higher number of adjacent plaquettes and one immediately sees the pattern for the full ladder . let us denote @xmath303 then , for a ladder with open ends , we get @xmath304 ^ 2\,\right ] ( 1-y_m)^2 . \label{l7}\ ] ] for a ladder with closed ( periodic ) ends , this is even simpler @xmath305 ^ 2 . \label{l8}\ ] ] where one identifies @xmath306 . once we have the joint distribution , it is easy to rewrite the average on the r.h.s . of eq . ( [ l3 ] ) in terms of the joint distribution @xmath307 the latter identity can be easily derived using integration by parts . let us , for simplicity , consider a plaquette with closed ends . then , substituting the joint distribution from eq . ( [ l8 ] ) into eq . ( [ l9 ] ) , we now have a one - dimensional multiple integral to peform @xmath308 ^ 2 . \label{l10}\ ] ] using the identity @xmath309 and making a change of variable @xmath310 , the integral in eq . ( [ l10 ] ) simplifies further @xmath311 . \label{l11}\ ] ] this one dimensional integral can now be performed by a transfer matrix technique which operates in one dimension . defining @xmath312 we get , @xmath313 $ ] and the eigenvalue equation is given by @xmath314 thus we have managed to reduce a two - dimensional eigenvalue problem in eq . ( [ l2 ] ) into an equivalent but much simpler @xmath22-d eigenvalue problem in eq . ( [ l12 ] ) which can then be solved exactly . to proceed , we first divide the range of integration in eq . ( [ l12 ] ) into @xmath271 $ ] and @xmath272 $ ] . next we differentiate once to get @xmath315 note the boundary conditions that emerge from eqs.([l12 ] ) and ( [ l13 ] ) : @xmath274 and @xmath316 . but in addition one also has to satisfy @xmath275 . dividing eq . ( [ l13 ] ) by @xmath20 and differentiating once more we get an ordinary second order differential equation @xmath317 with the boundary conditions : @xmath274 , @xmath316 and @xmath275 . the general solution to this equation , after a few changes of variables , can fortunately be obtained explicitly as a linear combination of two independent bessel functions . the boundary condition @xmath318 rules one of them out . then , the most general solution satisfying @xmath318 can be written as @xmath319 where @xmath320 is the ordinary bessel function with index @xmath321  @xcite and @xmath322 is an arbitrary amplitude . note that the other boundary condition at @xmath323 , namely @xmath324 is automatically satisfied by the solution in eq . ( [ l15 ] ) . this can be seen by using the small @xmath20 expansion of @xmath325 which indicates @xmath326 as @xmath327 . hence @xmath324 .    to determine the eigenvalue @xmath219 , we have to use the other nontrivial boundary condition at @xmath328 , namely @xmath275 . this condition , substituted in eq . ( [ l15 ] ) , gives us an implicit equation for @xmath219 that looks a bit complicated @xmath329 however , a nice simplication occurs when one uses the identity  @xcite , @xmath330 . ( [ l16 ] ) simply gives @xmath331 the bessel function oscillates on the positive axis of its argument , so each of its zeroes ( roots ) would give an eigenvalue @xmath219 . however , for large @xmath2 , we are interested only in the largest eigenvalue which is then given by @xmath332 where @xmath333 is smallest positive root of @xmath334 . the root @xmath333 is known  @xcite , @xmath335 . using @xmath336\sim \lambda^m$ ] for large @xmath2 and using @xmath289 , we finally get the exact result for the two - leg ladder @xmath337^{1/3}=1.57657\ldots \label{l19}\ ] ] when compared with the @xmath22-d result , @xmath338 , we see that @xmath75 changes by a very small amount as one goes from a chain to a ladder . it would be interesting to see if one can extend these calculations to ladders with more than two legs  @xcite and eventually to the full @xmath150-dimensional lattice . now we consider the dependence of @xmath75 on dimension . for simplicity , we have focused on @xmath0-dimensional hypercubic lattices as these lattices are simple to parametrize and are bipartite , allowing us to use the @xmath0-dimensional analog of the framework described in sect . [ subsect : plaquette ] . our approach will be computational : we numerically estimate @xmath176 from an integral representation for lattices of increasing size and then try to extract the limit of large sizes . to avoid boundary effects which slow down the convergence to this limit , we have used @xmath339 lattices having periodic boundary conditions in all directions . the integral in eq . ( [ plaq3 ] ) is based on decomposing the lattice into even and odd sites and imposing the local minima to be say on the even sites . its generalization to @xmath0 dimensions involves all the neighbors of a given even site @xmath9 , the corresponding `` star '' set of @xmath340 odd sites playing the role the plaquette had for the square lattice : @xmath341 here the average is over all values of the random variables belonging to stars ; these are uniform i.i.d . in @xmath32 $ ] . furthermore , as before , we neglect the factor 2 in @xmath148 coming from the fact that the minima could have been taken to be on the odd sites . the difficulty in computing these integrals is their high dimensionality . in monte carlo as used in most statistical physics applications , it is straightforward to use importance sampling methods ( e.g. , the metropolis algorithm ) to get expectation values of observables ; unfortunately here , the quantity to compute is the analog of the free energy and it is not directly accessible via such methods . we have thus used a different approach that is of the `` variance reduction '' type . it can be motivated as follows . in eq . ( [ eq : star ] ) we are to get the mean value of the integrand , sampling the random variables @xmath24 uniformly . it is quite easy to see that the signal to noise ratio goes to zero exponentially with the number of lattice sites ; to counteract this , we sample the @xmath24 with a different density and then correct for this biased sampling . for this to be practical , we keep the @xmath24 as i.i.d . variables , but optimize their individual distribution so as to maximize the signal to noise ratio . let @xmath342 be the probability density used for sampling the @xmath24 . for any such distribution , @xmath343^{1/2d } } \big \rangle_{\rho } . \label{eq : starvr}\ ] ] the denominator corrects for the modified measure of the random variables , taking into account the fact that each odd site appears in @xmath340 stars . if @xmath344 is well chosen , the numerator and denominator of the integrand will fluctuate together so that their ratio has a reduced variance . for our purposes , we parametrized @xmath344 as follows : @xmath345 where @xmath346 and @xmath347 are arbitrary parameters while @xmath322 and @xmath348 are set so that @xmath344 is continuous and is a normalized probability density . for each dimension , we adjust @xmath346 and @xmath347 to minimize the variance the integrand ; the signal to noise ratio still decreases exponentially with the number of lattice sites , but with a smaller exponent . the motivation for this functional form is simple : the odd sites , all of which are maxima , have an a posteriori distribution that is strongly suppressed at low values of the random variable . one last obstacle comes from the fact that the integrand typically takes on small values when one takes large lattices ; this is expected of course since the integral itself is becoming exponentially small . to keep track of values that are smaller than what can be represented by the machine coding , ( we used 96 bit representations of real numbers ) , we shifted multiplicatively each star term in the integrand and corrected for this shift when computing @xmath349 . the set of these procedures then gave us values of @xmath350 with measurable statistical errors for a range of @xmath351 from which we extrapolated to the large @xmath3 limit . in practice , we find that this strategy works very well in low dimensions . for instance in dimension @xmath133 , we still have a very good precision for @xmath352 sites , and the large @xmath353 limit can be very reliably extracted , giving @xmath75 to better than 5 significant figures . ( of course , since the exact value is known at @xmath133 , this really only serves as a check of our procedures . ) in dimension @xmath354 , the method gives better than 4 significant figures for @xmath355 . our estimates of @xmath356 as a function of @xmath357 are shown in fig . ( [ fig : gammaconvergence ] ) . the convergence to the @xmath358 limit seems to follow a @xmath359 law , a property we also find for the higher dimensions investigated . limit of the estimates of @xmath360 for the square lattice , @xmath361.,width=377 ]    here we see that @xmath360 converges rapidly to a value close to 1.658 . unfortunately the signal to noise ratio decreases with @xmath353 and with dimension ; furthermore the accessible range of @xmath353 decreases fast as @xmath0 increases ; because of this , we are able to extract @xmath75 reliably only for dimensions up to @xmath362 . our results are summarized in table  [ tab : numerics ] where the error estimates come from both statistical noise and uncertainties in the large @xmath353 extrapolation . ccccccc @xmath363 & @xmath133 & @xmath354 & @xmath364 & @xmath365 & @xmath362 +   + @xmath366 & 1.57082(6 ) & 1.6577(6 ) & 1.7152(10 ) & 1.761(5 ) & 1.806(10 ) + @xmath367 & 1.570796 & 1.854075 & 1.927621 & 1.956922 & 1.971464 we have been concerned with the statistical properties of @xmath2 , the number of local minima in a random energy landscape . the low order moments of @xmath2 can easily be obtained ; higher order moments could be computed by automated counting of graphs . atypical _ values of @xmath2 follow a large deviation principle as given in eq . ( [ ld1 ] ) ; we have been able to compute this function @xmath57 in one dimension analytically ; it diverges as @xmath126 and goes to a finite limit when @xmath2 reaches its maximum value where one half of the lattice sites are local minima . this then led us to consider the limit of maximum packing ( @xmath2 takes on its largest possible value ) for more general lattices . we focused on bipartite lattices where up to half of the sites can be local minima . we derived analytically the probability of this maximum packing @xmath368 for the cayley tree and for a two - leg ladder . we then tackled @xmath0-dimensional hypercubic lattices by computational techniques . for all these lattices , it is easy to see that @xmath369 simply by forcing the @xmath24 on the even ( odd ) sites to be less ( greater ) than @xmath370 ; this immediately leads to @xmath371 for all dimension . furthermore when @xmath0 becomes large , it will be very rare to have maximum packing if the @xmath24 do not very nearly satisfy this even - odd pattern so one expects @xmath372 to tend towards 2 in the large @xmath0 limit .    given this large @xmath0 limit , it is natural to ask how @xmath246 is approached . in fig . ( [ fig : gamma ] ) we show that the cayley tree case follows a very clear power correction law which can be derived analytically as being @xmath373 . the case of the @xmath0-dimensional lattice is less clear but is compatible with a @xmath374 law . the cayley tree thus provides an approximation to the hypercubic case but not a very accurate one ; this is probably because the nature of the correlations from site to site of the @xmath24 ( given that one has a maximally packed configuration ) are quite different when considering the tree rather than the hypercube . our work can be extended in several ways . ( i ) we computed the exact large deviation function in one dimension , but this function can also be determined for the cayley tree  @xcite . ( ii ) one can also introduce a chemical potential @xmath91 for each minimum and consider the thermodynamics of minima as a function of @xmath91 ; recent numerical results by derrida in @xmath150-d  @xcite indicate the presence of a phase transition with @xmath91 . ( iii ) our variables @xmath24 were i.i.d . random variables ; does a large deviation principle still hold if these variables have short range correlations ? one expects so . ( iv ) how do all these statistical properties generalize if one asks for minima within a given energy range ? finally , it would also be of interest to understand the similarities and differences between the statistics of local minima in continuous random energy landscapes  @xcite and in lattice models as presented here ; the energies could be random or correlated as in the sinai problem . this work was supported by the eec s fp6 information society technologies programme under contract ist-001935 , evergrow ( www.evergrow.org ) , and by the eec s hpp under contract hprn - ct-2002 - 00307 ( dyglagemem ) . s.m . wants to thank the hospitality of the isaac newton institute , cambridge ( uk ) where this work was completed . we thank our colleagues a.j . bray , b. derrida , d. dhar , m.r . evans , k. mallick , s. nechaev , g. oshanin and p. sollich for stimulating discussions .
we consider random energy landscapes constructed from @xmath0-dimensional lattices or trees . 
 the distribution of the number of local minima in such landscapes follows a large deviation principle and we derive the associated law exactly for dimension 1 . also of interest 
 is the probability of the maximum possible number of minima ; this probability scales exponentially with the number of sites . 
 we calculate analytically the corresponding exponent for the cayley tree and the two - leg ladder ; for 2 to 5 dimensional hypercubic lattices , we compute the exponent numerically and compare to the cayley tree case .    for many materials that are glassy  @xcite local minima of the energy ( or of the free energy ) trap the system for long times , leading to subtle equilibrium and out of equilibrium properties . 
 energy landscapes provide a simple conceptual framework for modeling these systems but in fact their use goes much beyond that . 
 for instance the vacua of string theories are expected to proliferate enormously , and the problem of estimating the number of local minima  @xcite of string energy landscapes is still an open problem . 
 other examples include rugged ( random ) energy landscapes in evolutionary biology  @xcite , quantum cosmology  @xcite , manifolds in random media  @xcite , glassy systems  @xcite random potentials  @xcite and the associated problems in random matrix theory  @xcite . 
 typically these systems consider a particle , a configuration of particles , or even a manifold , subject to a random potential . 
 one extreme case for its visual simplicity is that of a point particle in a random gaussian potential ; on the opposite extreme are energy landscapes associated with the configuration of a many body system . 
 examples in this last category include : ( 1 ) the @xmath1-spin glass model  @xcite , which in the limit of large @xmath1 reduces to the far simpler random energy model of derrida  @xcite ; ( 2 ) atomic clusters  @xcite and other glassy systems with no quenched disorder  @xcite ; ( 3 ) random manifolds in random media  @xcite . 
 for any landscape , it is desirable to know the statistical properties of the minima ( or more generally of the saddle points ) . 
 a quantity frequently considered is the expected number of minima as a function of their energy  @xcite . 
 it may also be of interest to consider how the set of minima are organized topologically , e.g. , whether the barrier tree  @xcite is ultrametric . 
 our focus here is to better understand the statistics of the total number of local minima in random energy landscapes ; our underlying space is a regular ( euclidean ) lattice on each site of which resides a random energy . 
 let @xmath2 denote the total number of local minima for given values of the energies on each site . 
 evidently @xmath2 is a random variable as it varies from one realization of the landscape to another . 
 we are interested in the statistics of @xmath2 as a function of the number @xmath3 of lattice sites . 
 similar questions were studied recently in the context of random permutations  @xcite , ballistic deposition  @xcite , and in simple models of glasses  @xcite . in this paper 
 , we provide a number of analytical results on the distribution of the total number of local minima for random energy landscapes on several lattices ; the moments of @xmath2 are easily derived , so our focus concerns mainly the probability of _ large deviations _ of @xmath2 from its mean value , i.e. , the probabilities of atypical configurations . 
 furthermore we ask what is the probability of @xmath2 being at its maximum , corresponding to the limit where the minima are maximally packed on the lattice . 
 the paper is organized as follows . in sect . 
 [ sec : model ] we specify the model and show that the statistical properties of the minima are independent of the individual distribution of energies as long as these energies are independent from site to site and are drawn from a continuous distribution . in sect . 
 [ sec : generalproperties ] we cover some of the simplest properties of the statistics of @xmath2 and formulate the large deviation principle . 
 then we derive the closed form expression for the large deviation function in the case of the one dimensional lattice in sect . 
 [ sec : onedimension ] . 
 the focus of the rest of the paper is the maximum packing problem . in sect . 
 [ sec : maxpack ] we determine the probability of maximum packings for several solvable cases , namely cayley trees and a two - leg ladder . 
 the case of @xmath0-dimensional hypercubic lattices is then treated by numerical computation in sect . 
 [ sec : numerics ] . 
 finally , these different results are discussed in sect . 
 [ sec : conclusions ] and some closing remarks are given .