Number of solid partitions of 72

This page hosts information about the run that will determine the number of solid partitions of all integers $\leq 72$.

Programming Details

The code consists of two parts — the pre and the post code. The pre code consists of the following programs (written by B. Srivatsan and Suresh Govindarajan):

1. bmsymm2.cpp This program generates all plane partitions (PP) of a given depth, here depth=21, organised by $S_3$ symmetry. It is based on the Bratley-McKay algorithm. It generates a *.bms file for each PP. The number of PP of 21 is 118794.
2. ATSb.cpp This program takes a given PP and generates all ATS' that have that shape and then does the required book-keeping (computes the curidx of the ATS and tracks its possible end-points). The output of the code is the PP, the list of curidx multiplicities for each end-point, one *.ats file per $S_3$ image. It is an inverse Bratley-McKay algorithm.
3. ReverseKnuth.cpp This program replaces ATSb.cpp and is an inverse Knuth algorithm and appears to run a lot faster than ATSb.cpp.

and the post code consists of the following programs written by B. Srivatsan:

1. 3d_lessthandepth.cpp This program is a straightahead Knuth algorithm that generates all numbers up to depth=21 as this data is lost in the parallelization. The output is stored in lessthandepth.post.
2. 3d3post.cpp This takes as input the *.ats and counts all topological sequences with index $< 72$ and length$>\textrm{depth}=21$ and initial shape the PP associated with the .ats file. The output is stored in a *.post file. This is based on the Knuth algorithm to count topological sequences.
3. 3d3postX.cpp Here we changed the data structure used for the topological sequence x[k] in 3d3post.cpp. It is now a simple integer as opposed to a triple (piii=make_pair(make_pair(x,y),z)). This is yet another clever trick of Srivatsan who makes use of the fact that a topological sequence of length N can only have a limited number of points. A simple algorithm then maps the set of possible entries in x[k] to the set of integers — this map preserves the ordering. This leads to a 10-20% speedup in the running of the post code.
4. combine.cpp This program combines (adds up) the data in all *.post files generated by the previous two post programs and generates the final numbers of topological sequences from with the numbers of solid partitions are obtained.

Run Details

Pre Run

In this run, we restricted to ATS' with curidx<69 to reduce run times. Hence, the data can be used only for topological sequences with index < 90. The run to generate the 118794 branches began at the start of September 2012 and will hopefully finish by the end of October 2012. Created a replacement to the program that generates ATS' which is faster and will replace ATSb.cpp in future runs. The generation of branches was completed on November 4, 2012. Validation for N=56 also carried out on the same day.

Post Run

There will be two post runs, one for N=56 to validate the branches and the other for N=72 to generate the new numbers. The start of these runs will be timed around the time 50% or more of the pre data is generated. The post runs have begun in mid-October and are using 3d3postX.cpp as it provides a 10-20% speedup.

Status Monitor

All 450*3 runs with S2 symmetry have been completed. The following table summarises the status of the 19574*6 runs with S1 symmetry. Runs 0-18 have 1000*6 branches while run 19 has 574*6 branches.

Run No	Status	Run No	Status
0	Done 14/11	10	Done 3/1
1	Done 24/11	11	Done 20/11
2	Done 20/11	12	Done 19/11
3	Done 25/11	13	Done 4/12
4	Done 24/11	14	Done 12/12
5	Done 30/11	15	Done 23/11
6	Done 4/12	16	Done 9/12
7	Done 5/12	17	Done 3/1
8	Done 27/12	18	Done 3/1
9	Done 3/1	19	Done 13/11

S2	Done

All runs have been completed on January 3, 2013.

Results

Announced on Thu Jan 3 08:23:58 IST 2013

c[1] = 1
c[2] = 4
c[3] = 10
c[4] = 26
c[5] = 59
c[6] = 140
c[7] = 307
c[8] = 684
c[9] = 1464
c[10] = 3122
c[11] = 6500
c[12] = 13426
c[13] = 27248
c[14] = 54804
c[15] = 108802
c[16] = 214071
c[17] = 416849
c[18] = 805124
c[19] = 1541637
c[20] = 2930329
c[21] = 5528733
c[22] = 10362312
c[23] = 19295226
c[24] = 35713454
c[25] = 65715094
c[26] = 120256653
c[27] = 218893580
c[28] = 396418699
c[29] = 714399381
c[30] = 1281403841
c[31] = 2287986987
c[32] = 4067428375
c[33] = 7200210523
c[34] = 12693890803
c[35] = 22290727268
c[36] = 38993410516
c[37] = 67959010130
c[38] = 118016656268
c[39] = 204233654229
c[40] = 352245710866
c[41] = 605538866862
c[42] = 1037668522922
c[43] = 1772700955975
c[44] = 3019333854177
c[45] = 5127694484375
c[46] = 8683676638832
c[47] = 14665233966068
c[48] = 24700752691832
c[49] = 41495176877972
c[50] = 69531305679518
c[51] = 116221415325837
c[52] = 193794476658112
c[53] = 322382365507746
c[54] = 535056771014674
c[55] = 886033384475166
c[56] = 1464009339299229
c[57] = 2413804282801444
c[58] = 3971409682633930
c[59] = 6520649543912193
c[60] = 10684614225715559
c[61] = 17472947006257293
c[62] = 28518691093388854
c[63] = 46458506464748807
c[64] = 75542021868032878
c[65] = 122606799866017598
c[66] = 198635761249922839
c[67] = 321241075686259326
c[68] = 518619444932991189

c[69] = 835840682363211461
c[70] = 1344830884987012679
c[71] = 2160197135019313694
c[72] = 3464274974065172792

c[n] is the number of solid partitions of n. The new numbers are for n=69-72. Numbers in red are prime (thanks to my colleague, Arul Lakshminarayan for pointing this out.).

Disclaimer: While a lot of effort has gone into ensuring the correctness of our results, this has not been independently verified. Our results do agree with known results up to N=50 and could be considered as an independent verfication of the 2003 Mustonen-Rajesh result. as well as a validation of the numbers for N=51,52 that were generated using different code (v2.0); N=53-55 that were generated using v3.0 of the code and N=56-68 that were generated using v3.2 of the code. A partial check of the numbers for N=69-72 is provided by our Monte Carlo simulations.

Estimates from Monte Carlo simulations

Nicolas Destainville and I have been running Monte Carlo simulations to establish the asymptotics of solid partitions. As a by-product, I have estimated the numbers of solid partitions in the range $[69,100]$ to fairly high accuracy (based on the statistical errors). In particular, here are the estimates for $[69,72]$ where we expect the first 5-6 digits (shown in boldface) to be correct! These estimates were done during Spring 2012 (around March/April).

(1)

\begin{align} mc_3(69)=\mathbf{83584}1291640288768 \quad,\quad mc_3(70)=\mathbf{134483}2639528153856 \\ \phantom{m}p_3(69) = 835840682363211461 \quad,\quad \phantom{m}p_3(70) = 1344830884987012679\\ mc_3(71)=\mathbf{216020}1142465445888 \quad, \quad mc_3(72)=\mathbf{346428}3320551847424\\ \phantom{m}p_3(71) = 2160197135019313694\quad,\quad \phantom{m}p_3(72) = 3464274974065172792 \end{align}

Notation: $mc_3(n)$ is the Monte Carlo estimate for $p_3(n).$

Acknowledgments

We are grateful for the support of IIT Madras, in particular, its High Performance Computing Environment, and Intel India towards the solid partitions project.

Support the solid partitions project

How? Either run code or work on improving the code or help with setting up/running the portal. Contact solidpartitions at gmail.com

---

© 2013 Suresh Govindarajan and Srivatsan Balakrishnan