Limit Shape Theorems for Partitions
Anatoly Vershik
IHES, BuressurYvette
Algorithms Seminar
March 8, 1999
[summary by Sylvie Corteel]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Abstract
Many combinatorial and geometrical problems can be reduced to a problem
about partitions of
natural numbers or vectors, etc. The main asymptotic question is the
behaviour of the shape of such
a partition when the statistics or dynamics are fixed.
This leads us to the problem of limit shapes.
Example: what is the typical limit shape of the uniformly distributed
partition of the integers? An explicit answer can be given.
A partition of a nonnegative
integer n is a sequence
l=(l_{1},l_{2},... , l_{N})
such that l_{1}³ l_{2}³ ... ³ l_{N}³ 1,
n(l)=å_{i=1}^{N} l_{i}=n. The l_{i}'s are the summands of the partitions.
Let P_{n} denote the set of all partitions of the integer n
and Q_{n} the set of partitions of the integer n with distinct
summands. Let r_{k}(l) be the multiplicity of the summand k, that is
r_{k}(l)=#{jl_{j}=k}.
Clearly, n(l)=å_{k} kr_{k}(l) and
N(l)=å_{k} r_{k}(l). Recall that # P_{n}=p(n) is the
Euler function
and the generating function å_{n} p(n)x^{n} is Õ_{i³ 1}
(1q^{i})^{1}.
The author associates a function j_{l} on [0,¥)
with the partition
lÎ P_{n} by the following rule:
j_{l} is a step function, continuous on the right
and ò_{0}^{¥}j_{l}(t)=n.
Let a={a_{n}}_{n³ 0} with a_{n}>0 for all n; the function



(t)= 


r_{k}(l)= 

j 

(a_{n} t)

is j_{l} normed by a_{n}, so that
ò_{0}^{¥}j^{~}_{l}(t)=1.
Let µ^{n} be
the uniform measure on the set P_{n}
of all partitions of the integer n:µ^{n}(l)= p(n)^{1}, lÎ P_{n};
the question is whether one can
normalize the partitions in such a way that, in some properly chosen
space, the measures µ^{n} have a weak limit on generalized
diagrams, and whether this limit is singular. In the
last case, the limit measure is concentrated on a limit shape. An
affirmative answer to these questions, as well as explicit formulas for
limit shapes, are given in the sequel.
Theorem 1
The scaling a={a_{n}} for the uniform measure on P_{n}
such that a
non trivial limit
exists in the space of generalized diagrams is a_{n}=(n)^{1/2}.
The same scaling is appropriate for the uniform measure on Q_{n}.
Theorem 2
Under the previous scaling, the measures µ^{n} have a weak limit.
This limit is singular and concentrated on a continuous curve.
The limit shape of the uniformly distributed
ordinary partitions and partitions into distinct
summands can now be stated.
Theorem 3
For any e>0, 0<x,y<¥, there exists n_{0} such that for all n>n_{0}
µ^{n}{lÎ P 
_{n} 

 


(t)C(t)<e}>1e,

where C(t)=((6)^{1/2}/p)ln(1e^{p t/(6)}^{1/2}), or in more symmetric form
Theorem 4
For any e>0, 0<x,y<¥, there exists n_{0} such that for all n>n_{0}
µ^{n}{lÎ Q 
_{n} 

 


(t)C(t)<e}>1e,

where C(t)=((12)^{1/2}/p)ln(1+e^{p t/(12)}^{1/2}), or in more symmetric form
The limit shape can also be obtained for the uniform measure on partitions
included in a rectangle, partitions with a given number of summands,
vector partitions,...and other kinds of measures called
multiplicative measures. The detailed results and links with statistical
mechanics are presented in [2].
References
 [1]

Andrews (George E.). 
The theory of partitions. 
AddisonWesley Publishing Co., Reading, Mass., 1976,
Encyclopedia of Mathematics and its Applications, vol. 2, xiv+255p.
 [2]

Vershik (A. M.). 
Statistical mechanics of combinatorial partitions, and their limit
configurations. Rossiiskaya Akademiya Nauk. Funktsional'nyi
Analiz i ego Prilozheniya, vol. 30, n°2, 1996.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.