Hello, bonjour, selamat siang, gruezi,
Welcome to the fifth, no sixth, no seventh..
well, to the seventh tutorial of Statistical Mechanics: Algorithms and Computations,
from the Physics Department of Ecole Normale Supérieure.
and to a final discussion of quantum statistical mechanics
Our program today is twofold
for once, we discussed in this week's lecture
a 50-lines quantum Monte Carlo program
that allowed us to observe Bose-Einstein condensation
for 500 or 1000 bosons
in a three-dimensional harmonic trap. But attention!
Don't forget to wear your glasses, because of the many lasers
As we lower the temperature
all of a sudden
the bosons clump together in the center of the trap
very clearly, it was the permutations that provoked this transition
because if we turn them off, like this,
the effect simply disappears.
Thus we understand that long permutation cycles
play a key role in Bose-Einstein condensation
but it's Michael who will provide the full story.
He will derive a curious recursion relationship
for the permutations of ideal bosons, that are equivalent to a theorem on random permutations.
Alberto then will use this insight
to construct a rejection-free direct sampling algorithm for ideal boson.
Remember: in markov_harmonic_bosons.py
we used a Markov chain algorithm to sample permutations, by trial and error
but we can quite soon do better.
But now, let's first listen to Michael
explain to us how permutations really work.
In this week's lecture, you saw that the appearance of long permutation cycles
was the driving force behind Bose-Einstein condensation,
let us look at this from yet another angle.
Here, you see ten particles in one permutation cycle.
We can now unwind them, by drawing the path of the first particle
followed by a second particle, whose path starts where the first particle left off,
then, by a third particle, a fourth particle,
a fifth and a sixth and so on..
Finally, we have one particle of mass one
at inverse temperature 10 beta, that is ten times lower temperature than T.
Let us now focus on the analysis of permutation cycles without worrying too much about particles
We consider random permutations as those generated by the program
permutation_sample.py, in this week's lecture.
We modify it a bit in order to look at the permutation cycles.
This gives the program permutation_sample_cycle.py.
Central element here is the use of dictionaries
with the keys being the particles
and the values being the permutations of the particles, that is their successor in the permutation cycle.
So this is the output of permutation_sample_cycle.py for N=20, together with the length of permutation cycles.
See, there are cycles of all lengths.
We have 9, 11, 15, 6, 1, ..
This is what we will now fully understand.
For N=4, we already know that there are 4!=24 permutations.
And we can analyze the permutation structure exactly.
So here are the 24 permutations of the 4 particles.
We want to compute their partition function, let's call it YN
This is the sum over all permutations, if we give a weight to each permutation.
If this weight is one, we are already done, because then YN
simply equals N!, that is the number of possible permutations of N particles.
Let us be a bit more general. We give a weight z1 to each cycle of length 1,
a weight z2 to each cycle of length 2,
and so on.
So this permutation on the top has the weight z1 ^ 4
this permutation has the weight z1^2 * z2, and so on..
Let us now pull apart
the last element, together with its cycle: the last element cycle.
This last element cycle involves k elements, n1, .., n(k-1) and the last element.
And of course N - k elements do not belong to this last element cycle.
Their partition function is Y_(N-k) and we know nothing about them.
Y_N is computed from the number of choices k,
the cycle weight z_k,
the number of different sets n_1 to n_(k-1) (given k),
the number of different cycles (given the set n_1, .., n_(k-1), n_N)
and the partition function
Y_(N-k) of the particles that do not participate in the last element cycle.
It is easy to see that these different terms give for the number of different choices
this combinatorial factor
and the number of different cycles is( k-1)!
This finally leads to the expression shown here.
which is a recursion relation, as it allows us
to compute Y_N from the smaller elements Y_0, .., Y_(N-1)
If we set z_k=1 for all k
we simply have the case of random permutations
where Y_N = N!
Y_(N-k) = (N-k)!
then all terms on the right hand side of the equation are the same
This means that the last element appears with the same probability in cycles of all lengths
from 1 to N.
To confirm this finding for the case N=4, simply count.
Element 4 is in 6 cycles of length 4
6 cycles of lengths 3, 6 cycles of lengths 2, and 6 cycles of lengths 1.
In conclusion, we have seen a nice recursion formula
that can be used to count permutations with arbitrary weights.
Next, Alberto will apply this relation
to bosons, but before listening to him
please take a moment or two to download, run and modify the program
permutation_sample_cycle.py
with its characteristic use of dictionaries
one of the key features of modern programming languages like Python.
In this week's lecture, Werner already discussed that the partition function
associated let's say with 4 bosons is given by
one over 24, times the sum
of the partition functions associated to the 24 permutations.
Here for example the first permutation corresponds to z(beta)^4,
and the second term has a partition function which is
z(2 beta) z(beta)^2
This corresponds to a cycle of length 2 and a pair of cycles of length 1.
And then we have the third term, which has exactly the same partition function, the fourth term and so on.
Of course, z(beta)
is a number which is explicitly known,
it is the partition function of a single particle inside a three-dimensional harmonic trap.
In week 5 we have computed the partition function
for a one-dimensional harmonic trap
It was given by a geometric sum
So in three dimensions we have now to multiply three times this geometric sum
and this gives the following expression.
So, for ideal bosons
the N-particle partition function
is just a sum of a product of single-particle partition functions.
However, this sum is very non-trivial
except for small N, where we can enumerate all the N! permutations.
It is better to adapt the recursion formula introduced by Michael.
Now, the weight of a cycle of length k
is given by the single-particle partition function
at the inverse temperature beta*k
Taking into account that the partition function
carries a factor of 1/N!
we can reorganize the relation in this way.
This recursion relation goes back to Landsberg in 1961.
It relates the partition function
of a system of N ideal bosons
to the partition function of a single particle z
and the partition functions Z of systems with fewer particles.
So, we have arrived to an analytical solution
that is implemented in the Python program
canonic_harmonic_recursion.py for the partition function.
Here you see
that we have implemented
the small z as the partition function of a single particle inside a three-dimensional harmonic trap,
and note that we have shifted the ground-state
so that the energy levels are E=0, E=1, E=2 and so on.
But the method is very general.
We pause for a moment, to gain a better understanding of this recursion relation.
And remember: as discussed by Michael,
each component refers to the last element cycle.
So, the probability to find a particle n
in a cycle of length k is given by this relation
But the particle n is no way special, so this relation
gives the probability to find any particle inside a cycle of length k.
We can compute these probabilities
by modifying the program canonic_harmonic_recursion.py
as you see here for 1000 particles.
In a harmonic trap at high temperature, only short cycles appear
while at smaller temperature also longer cycles become probable.
In the limit of zero temperature
the probability of a single particle to belong to a cycle of length k
becomes independent of k.
The output for 1000 particles at different temperatures is shown here.
In this week's homework
you will produce this kind of figures from simulations
It can be shown that the derivative of this function gives the distribution function of condensed particles.
So, we have solved a physical problem: we can compute the partition function of N ideal bosons without any approximation.
Does this ring a bell with you?
Sure, we should have a rejection-free direct-sampling algorithm.
And indeed we have. Thanks to the last equation, we can sample
the permutation cycle associated with the last particle,
and then continue again and again until we have nothing left.
So, before continuing, please take a moment to download
run and modify the program direct_harmonic_bosons.py that we discussed in this section.
This is the last point of our development in quantum statistical mechanics.
It is remarkable that for such an intricate problem
we can write a rejection-free algorithm
as if we were on the Monte Carlo beach.
So in conclusion we have come in this tutorial to a clear understanding
of random permutations
and of their role in Bose-Einstein condensation.
In Michael's list of 24 permutations,
he was able to pull apart the last element
and the last element cycle.
And we were able to see that the last element 4
was just as often in a cycle of length 4
as in a cycle of length 3, or length 2, or length 1.
We then used this insight
on random permutations
to understand cycle probabilities in the ideal Bose gas.
And this allowed to compute the canonic partition function for ideal bosons.
Once more, this analytical solution gave a great sampling algorithm that Alberto just presented.
So it is now time to appropriate yourself
of this great algorithm, to get your own Bose-Einstein condensate
and most of all to have fun with homework session 7.
And thanks to all of you for your attention
and see you again next week at Statistical Mechanics: Algorithms and Computations.