Limit Shape Theorems for Partitions

Anatoly Vershik

IHES, Bures-sur-Yvette

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=(l1,l2,... , lN) such that l1³ l2³ ... ³ lN³ 1, n(l)=åi=1N li=n. The li's are the summands of the partitions. Let Pn denote the set of all partitions of the integer n and Qn the set of partitions of the integer n with distinct summands. Let rk(l) be the multiplicity of the summand k, that is rk(l)=#{j|lj=k}. Clearly, n(l)=åk krk(l) and N(l)=åk rk(l). Recall that # Pn=p(n) is the Euler function and the generating function ån p(n)xn is Õi³ 1 (1-qi)-1. The author associates a function jl on [0,¥) with the partition lÎ Pn by the following rule:
j
 
l
(t)=
 
å
k³ t
rk(l)
jl is a step function, continuous on the right and ò0¥jl(t)=n. Let a={an}n³ 0 with an>0 for all n; the function
~
j
 
 
l
(t)=
an
n
 
å
k³ an t
rk(l)=
an
n
j
 
l
(an t)
is jl normed by an, so that ò0¥j~l(t)=1.

Let µn be the uniform measure on the set Pn of all partitions of the integer n:µn(l)= p(n)-1, lÎ Pn; 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={an} for the uniform measure on Pn such that a non trivial limit exists in the space of generalized diagrams is an=(n)1/2.
The same scaling is appropriate for the uniform measure on Qn.

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 n0 such that for all n>n0
µn{lÎ P n|
 
sup
tÎ[x,y]
|
~
j
 
 
l
(t)-C(t)|<e}>1-e,
where C(t)=-((6)1/2/p)ln(1-ep t/(6)1/2), or in more symmetric form
e
-p x/(6)1/2
 
+e
-p y/(6)1/2
 
=1.

Theorem 4   For any e>0, 0<x,y<¥, there exists n0 such that for all n>n0
µn{lÎ Q n|
 
sup
tÎ[x,y]
|
~
j
 
 
l
(t)-C(t)|<e}>1-e,
where C(t)=-((12)1/2/p)ln(1+e-p t/(12)1/2), or in more symmetric form
e
-p y/(12)1/2
 
-e
-p x/(12)1/2
 
=1.

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. -- Addison-Wesley 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 LATEX by HEVEA.