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.