×

Boltzmann distribution on “short” integer partitions with power parts: limit laws and sampling. (English) Zbl 07904793

Summary: The paper is concerned with the asymptotic analysis of a family of Boltzmann (multiplicative) distributions over the set \(\mathit{\check{\Lambda}}^q\) of strict integer partitions (i.e., with unequal parts) into perfect \(q\)-th powers. A combinatorial link is provided via a suitable conditioning by fixing the partition weight (the sum of parts) and length (the number of parts), leading to uniform distribution on the corresponding subspaces of partitions. The Boltzmann measure is calibrated through the hyper-parameters \(\langle N \rangle\) and \(\langle M \rangle\) controlling the expected weight and length, respectively. We study “short” partitions, where the parameter \(\langle M \rangle\) is either fixed or grows slower than for typical partitions in \(\check{\Lambda}^q\). For this model, we obtain a variety of limit theorems including the asymptotics of the cumulative cardinality in the case of fixed \(\langle M \rangle\) and a limit shape result in the case of slow growth of \(\langle M \rangle\). In both cases, we also characterize the joint distribution of the weight and length, as well as the growth of the smallest and largest parts. Using these results we construct suitable sampling algorithms and analyze their performance.

MSC:

05A17 Combinatorial aspects of partitions of integers
05A16 Asymptotic enumeration
60C05 Combinatorial probability
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
82B10 Quantum equilibrium statistical mechanics (general)
11P81 Elementary theory of partitions

Software:

DLMF

References:

[1] Agarwala, B. K.; Auluck, F. C., Statistical mechanics and partitions into non-integral powers of integers, Math. Proc. Camb. Philos. Soc., 47, 207-216, 1951, (MR0042998) · Zbl 0042.44208
[2] Andrews, G. E., The theory of partitions, (Rota, G.-C., Encyclopedia of Mathematics and Its Applications, vol. 2, 1976, Addison-Wesley: Addison-Wesley Reading, MA), reprinted by Cambridge University Press (Cambridge Mathematical Library), Cambridge, 1984 (MR0557013) · Zbl 0371.10001
[3] Arratia, R.; Barbour, A. D.; Tavaré, S., Logarithmic Combinatorial Structures: A Probabilistic Approach, EMS Monographs in Mathematics, 2003, European Mathematical Society: European Mathematical Society Zürich, (MR2032426) · Zbl 1040.60001
[4] Arratia, R.; DeSalvo, S., Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example, Comb. Probab. Comput., 25, 324-351, 2016, (MR3482658) · Zbl 1372.60006
[5] Arratia, R.; Tavaré, S., Independent process approximations for random combinatorial structures, Adv. Math., 104, 90-154, 1994, (MR1272071) · Zbl 0802.60008
[6] Auluck, F. C.; Kothari, D. S., Statistical mechanics and the partitions of numbers, Proc. Camb. Philos. Soc., 42, 272-277, 1946, (MR0017682) · Zbl 0061.46213
[7] Barbour, A.; Hall, P., On the rate of Poisson convergence, Math. Proc. Camb. Philos. Soc., 95, 473-480, 1984, (MR0755837) · Zbl 0544.60029
[8] Barbour, A. D.; Holst, L.; Janson, S., Poisson Approximation, Oxford Studies in Probability, vol. 2, 1992, Oxford Science Publications. Clarendon Press: Oxford Science Publications. Clarendon Press Oxford, (MR1163825) · Zbl 0746.60002
[9] Bendkowski, M.; Bodini, O.; Dovgal, S., Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers, Comb. Probab. Comput., 31, 765-811, 2022, (MR4472289) · Zbl 1512.68178
[10] Bernstein, M.; Fahrbach, M.; Randall, D., Analyzing Boltzmann samplers for Bose-Einstein condensates with Dirichlet generating functions, (Nebel, M.; Wagner, S., 2018 Proceedings of the Meeting on Analytic Algorithmics and Combinatorics (ANALCO), 2018, SIAM: SIAM Philadelphia, PA), 107-117, (MR3773639) · Zbl 1429.68154
[11] Bodini, O.; Duchon, P.; Jacquot, A.; Mutafchiev, L., Asymptotic analysis and random sampling of digitally convex polyominoes, (Gonzalez-Diaz, R.; etal., DGCI 2013: Discrete Geometry for Computer Imagery, Proceedings of the 17th IAPR International Conference. DGCI 2013: Discrete Geometry for Computer Imagery, Proceedings of the 17th IAPR International Conference, Seville, March 20-22, 2013. DGCI 2013: Discrete Geometry for Computer Imagery, Proceedings of the 17th IAPR International Conference. DGCI 2013: Discrete Geometry for Computer Imagery, Proceedings of the 17th IAPR International Conference, Seville, March 20-22, 2013, Lecture Notes in Computer Science, vol. 7749, 2013, Springer: Springer Berlin), 95-106, (MR3155272) · Zbl 1382.05015
[12] Bogachev, L. V., Unified derivation of the limit shape for multiplicative ensembles of random integer partitions with equiweighted parts, Random Struct. Algorithms, 47, 227-266, 2015, (MR3382672) · Zbl 1322.05017
[13] Bogachev, L. V.; Su, Z., Gaussian fluctuations of Young diagrams under the Plancherel measure, Proc. R. Soc. Ser. A, 463, 1069-1080, 2007, (MR2310137) · Zbl 1200.05248
[14] Bogachev, L. V.; Yakubovich, Yu. V., Limit shape of minimal difference partitions and fractional statistics, Commun. Math. Phys., 373, 1085-1131, 2020, (MR4061406) · Zbl 1435.05021
[15] Bogachev, L. V.; Zarbaliev, S. M., Universality of the limit shape of convex lattice polygonal lines, Ann. Probab., 39, 2271-2317, 2011, (MR2932669) · Zbl 1242.52007
[16] Borodin, A.; Okounkov, A.; Olshanski, G., Asymptotics of Plancherel measures for symmetric groups, J. Am. Math. Soc., 13, 481-515, 2000, (MR1758751) · Zbl 0938.05061
[17] Bridges, W., Partitions into distinct parts with bounded largest part, Res. Number Theory, 6, 40, 1-19, 2020, (MR4163635) · Zbl 1456.05009
[18] Bureaux, J.; Enriquez, N., Asymptotics of convex lattice polygonal lines with a constrained number of vertices, Isr. J. Math., 222, 515-549, 2017, (MR3722260) · Zbl 1394.52017
[19] Comtet, A.; Leboeuf, P.; Majumdar, S. N., Level density of a Bose gas and extreme value statistics, Phys. Rev. Lett., 98, 070404, 1-4, 2007
[20] Comtet, A.; Majumdar, S. N.; Ouvry, S.; Sabhapandit, S., Integer partitions and exclusion statistics: limit shapes and the largest parts of Young diagrams, J. Stat. Mech. Theory Exp., 10, P10001, 1-13, 2007, (MR2358050 · Zbl 1456.05011
[21] Cramér, H., Mathematical Methods of Statistics, Princeton Mathematical Series, vol. 9, 1946, Princeton University Press: Princeton University Press Princeton, NJ, (MR0016588) · Zbl 0063.01014
[22] De Gregorio, P.; Rondoni, L., Microcanonical entropy, partitions of a natural number into squares and the Bose-Einstein gas in a box, Entropy, 20, 645, 1-26, 2018
[23] Dembo, A.; Vershik, A.; Zeitouni, O., Large deviations for integer partitions, Markov Process. Relat. Fields, 6, 147-179, 2000, (MR1778750) · Zbl 0972.60006
[24] DeSalvo, S.; Pak, I., Limit shapes via bijections, Comb. Probab. Comput., 28, 187-240, 2019, (MR3922777) · Zbl 1434.05012
[25] Duchon, P.; Flajolet, P.; Louchard, G.; Schaeffer, G., Boltzmann samplers for the random generation of combinatorial structures, Comb. Probab. Comput., 13, 577-625, 2004, (MR2095975) · Zbl 1081.65007
[26] Erdős, P.; Lehner, J., The distribution of the number of summands in the partitions of a positive integer, Duke Math. J., 8, 335-345, 1941, (MR0004841) · Zbl 0025.10703
[27] Erdős, P.; Turán, P., On some general problems in the theory of partitions, I, Acta Arith., 18, 53-62, 1971, (MR0289446) · Zbl 0217.32202
[28] Erlihson, M. M.; Granovsky, B. L., Limit shapes of Gibbs distributions on the set of integer partitions: the expansive case, Ann. Inst. Henri Poincaré Probab. Stat., 44, 915-945, 2008, (MR2453776) · Zbl 1181.60146
[29] Ewens, W. J., The sampling theory of selectively neutral alleles, Theor. Popul. Biol., 3, 87-112, 1972, (MR0325177) · Zbl 0245.92009
[30] Feller, W., An Introduction to Probability Theory and Its Applications, Volume II, Wiley Series in Probability and Mathematical Statistics, 1971, Wiley: Wiley New York, (MR0270403) · Zbl 0219.60003
[31] Flajolet, P.; Fusy, É.; Pivoteau, C., Boltzmann sampling of unlabelled structures, (Panario, D.; Sedgewick, R., 2007 Proceedings of the Workshop on Analytic Algorithmics and Combinatorics (ANALCO), 2007, SIAM: SIAM Philadelphia, PA), 201-211, (MR2498128) · Zbl 1430.68164
[32] Fristedt, B., The structure of random partitions of large integers, Trans. Am. Math. Soc., 337, 703-735, 1993, (MR1094553) · Zbl 0795.05009
[33] Fulton, W., Young Diagrams, with Applications to Representation Theory and Geometry, London Mathematical Society Student Texts, vol. 35, 1997, Cambridge University Press: Cambridge University Press Cambridge, (MR1464693) · Zbl 0878.14034
[34] Garibaldi, U.; Scalas, E., Finitary Probabilistic Methods in Econophysics, 2010, Cambridge University Press: Cambridge University Press Cambridge, (MR2839542) · Zbl 1285.91001
[35] Goh, W. M.Y.; Hitczenko, P., Random partitions with restricted part sizes, Random Struct. Algorithms, 32, 440-462, 2008, (MR2422389) · Zbl 1156.05007
[36] Greiner, W.; Neise, L.; Stöcker, H., Thermodynamics and Statistical Mechanics, Classical Theoretical Physics, 1995, Springer: Springer New York · Zbl 0823.73001
[37] Guy, R. K., Unsolved Problems in Number Theory, Problem Books in Mathematics, 2003, Springer: Springer New York, (MR2076335)
[38] Hardy, G. H.; Ramanujan, S., Asymptotic formulæin combinatory analysis, Proc. Lond. Math. Soc. (2), 17, 75-115, 1918, (MR1575586) · JFM 46.0198.04
[39] Hardy, G. H.; Wright, E. M., An Introduction to the Theory of Numbers, 2008, Oxford University Press: Oxford University Press Oxford, (MR2445243), with a foreword by A. Wiles · Zbl 1159.11001
[40] Haselgrove, C. B.; Temperley, H. N.V., Asymptotic formulae in the theory of partitions, Proc. Camb. Philos. Soc., 50, 225-241, 1954, (MR0062782) · Zbl 0055.27401
[41] Hohloch, S., Optimal transport and integer partitions, Discrete Appl. Math., 190/191, 75-85, 2015, (MR3351722) · Zbl 1326.49076
[42] Horn, R. A.; Johnson, C. R., Matrix Analysis, 2013, Cambridge University Press: Cambridge University Press Cambridge, (MR2978290) · Zbl 1267.15001
[43] Hua, L.-K., On the number of partitions of a number into unequal parts, Trans. Am. Math. Soc., 51, 194-201, 1942, (MR0006195) · JFM 68.0077.01
[44] Huang, K., Statistical Mechanics, 1987, Wiley: Wiley New York, (MR1042093) · Zbl 1041.82500
[45] Hwang, H.-K., Limit theorems for the number of summands in integer partitions, J. Comb. Theory, Ser. A, 96, 89-126, 2001, (MR1855788) · Zbl 1029.60013
[46] Ingham, A. E., A Tauberian theorem for partitions, Ann. Math. (2), 42, 1075-1090, 1941, (MR0005522) · Zbl 0063.02973
[47] Khinchin, A. I., Mathematical Foundations of Statistical Mechanics, 1949, G. Gamow. Dover Publications: G. Gamow. Dover Publications New York, (MR0029808) · Zbl 0037.41102
[48] Khinchin, A. Y., Mathematical Foundations of Quantum Statistics, 1960, Graylock Press: Graylock Press Albany, NY, (MR0111217) · Zbl 0089.45004
[49] Kingman, J. F.C., Random partitions in population genetics, Proc. Royal Soc. Lond. Ser. A, 36, 11-20, 1978, (MR0526801) · Zbl 0393.92011
[50] Kolchin, V. F.; Sevast’yanov, B. A.; Chistyakov, V. P., Random Allocations, 1976, A. V. Balakrishnan, ed. Scripta Series in Mathematics. V. H. Winston & Sons/Scripta Technica, Inc., Washington, D.C., 1978 [distributed by Halsted Press/Wiley, New York]. (MR0471016) · Zbl 0464.60002
[51] Landau, E., Über die Einteilung der positiven ganzen Zahlen in vier Klassen nach der Mindestzahl der zu ihrer additiven Zusammensetzung erforderlichen Quadrate. (German) [On the division of positive integers into four classes according to the minimum number of squares required for their additive composition], Arch. Math. Phys. (3), 13, 305-312, 1908 · JFM 39.0264.03
[52] Lee, D. V., The asymptotic distribution of the number of summands in unrestricted Λ-partitions, Acta Arith., 65, 29-43, 1993, (MR1239241) · Zbl 0795.11052
[53] Lindsay, R. B., XXII. A modification of Brillouin’s unified statistics, Lond. Edinb. Dublin Philos. Mag. J. Sci. Ser. 7, 17, 264-271, 1934 · Zbl 0008.28106
[54] Lipnik, G. F.; Madritsch, M. G.; Tichy, R. F., A central limit theorem for integer partitions into small powers, Monatshefte Math., 203, 149-173, 2024, (MR4688350) · Zbl 07789021
[55] Loève, M., Probability Theory I, Graduate Texts in Mathematics, vol. 45, 1977, Springer: Springer New York, (MR0651017) · Zbl 0359.60001
[56] Logan, B. F.; Shepp, L. A., A variational problem for random Young tableaux, Adv. Math., 26, 206-222, 1977, (MR1417317) · Zbl 0363.62068
[57] Meinardus, G., Asymptotische Aussagen über Partitionen. (German) [Asymptotic statements about partitions], Math. Z., 59, 388-398, 1954, (MR0062781) · Zbl 0055.03806
[58] Novak, S. Y., Poisson approximation, Probab. Surv., 16, 228-276, 2019, (MR3992498) · Zbl 1422.60028
[59] Nuermaimaiti, R.; Bogachev, L. V.; Voss, J., A generalized power law model of citations, (Glänzel, W.; etal., 18th International Conference on Scientometrics & Informetrics. 18th International Conference on Scientometrics & Informetrics, ISSI 2021 (12-15 July 2021, KU Leuven, Belgium), Proceedings, 2021, International Society for Scientometrics (I.S.S.I.)), 843-848, 2024, Available online at
[60] (Olver, F. W.J.; etal., NIST Handbook of Mathematical Functions, 2010, National Institute of Standards and Technology, U.S. Department of Commerce/Cambridge University Press: National Institute of Standards and Technology, U.S. Department of Commerce/Cambridge University Press Washington, DC/Cambridge), 2024, (MR2723248), Online version: NIST Digital Library of Mathematical Functions, Release 1.1.7, 2022-10-15
[61] Pak, I., The nature of partition bijections I. involutions, Adv. Appl. Math., 33, 263-289, 2004, (MR2074399) · Zbl 1070.11047
[62] Pitman, J., Combinatorial stochastic processes, (Picard, J., Ecole d’Eté de Probabilités de Saint-Flour XXXII - 2002. Ecole d’Eté de Probabilités de Saint-Flour XXXII - 2002, Lecture Notes in Mathematics, vol. 1875, 2006, Springer: Springer Berlin), (MR2245368) · Zbl 1103.60004
[63] Pittel, B., On a likely shape of the random Ferrers diagram, Adv. Appl. Math., 18, 432-488, 1997, (MR1445358) · Zbl 0894.11039
[64] Polcari, J., An informative interpretation of decision theory: the information theoretic basis for signal-to-noise ratio and log likelihood ratio, IEEE Access, 1, 509-522, 2013
[65] Rabin, M. O., Probabilistic algorithm for testing primality, J. Number Theory, 12, 128-138, 1980, (MR0566880) · Zbl 0426.10006
[66] Resnick, S. I., Extreme Values, Regular Variation and Point Processes, Applied Probability. A Series of the Applied Probability Trust, vol. 4, 1987, Springer: Springer New York, (MR0900810) · Zbl 0633.60001
[67] Roccia, J.; Leboeuf, P., Level density of a Fermi gas and integer partitions: a Gumbel-like finite-size correction, Phys. Rev. C, 81, Article 044301 pp., 2010
[68] Romik, D., Partitions of n into \(t \sqrt{ n}\) parts, Eur. J. Comb., 26, 1-17, 2005, (MR2101031) · Zbl 1066.05020
[69] Shiryaev, A. N., Probability, Graduate Texts in Mathematics, vol. 95, 1996, Springer: Springer New York, (MR1368405)
[70] Sinaĭ, Ya. G., A probabilistic approach to the analysis of the statistics of convex polygonal lines, Funkc. Anal. Prilozh.. Funkc. Anal. Prilozh., Funct. Anal. Appl., 28, 2, 108-113, 1994, (MR1283251) · Zbl 0832.60099
[71] Szalay, M.; Turán, P., On some problems of the statistical theory of partitions with application to characters of the symmetric group, I, Acta Math. Acad. Sci. Hung., 29, 361-379, 1977, (MR0506108) · Zbl 0371.10033
[72] Su, Z., Random Matrices and Random Partitions: Normal Convergence, World Scientific Series on Probability Theory and Its Applications, 1, 2015, World Scientific: World Scientific Hackensack, NJ, (MR3381296) · Zbl 1351.60002
[73] Temperley, H. N.V., Statistical mechanics and the partition of numbers, I. The transition of liquid helium, Proc. Royal Soc. Lond. Ser. A, 199, 361-375, 1949, (MR0037247) · Zbl 0041.54709
[74] Temperley, H. N.V., Statistical mechanics and the partition of numbers, II. The form of crystal surfaces, Proc. Camb. Philos. Soc., 48, 683-697, 1952, (MR0053036) · Zbl 0048.19802
[75] Uspensky, J. V., Asymptotic expressions of numerical functions occurring in problems of partition of numbers, Bull. Acad. Sci. Rus. Ser. VI, 14, 199-218, 1920, (zbMATH JFM 48.1162.01)
[76] Vaughan, R. C., Squares: additive questions and partitions, Int. J. Number Theory, 11, 1367-1409, 2015, (MR3376217) · Zbl 1334.11080
[77] Vaughan, R. C.; Wooley, T. D., Waring’s problem: a survey, (Bennett, M. A.; etal., Number Theory for the Millennium, III (Urbana, IL, 2000), 2002, A K Peters: A K Peters Natick, MA), 285-324, 2003, CRC Press: CRC Press Boca Raton, FL, (MR1956283) Reprinted in Surveys in Number Theory: Papers from the Millennial Conference on Number Theory
[78] Vershik, A. M., Asymptotic combinatorics and algebraic analysis, (Chatterji, S. D., Proceedings of the International Congress of Mathematicians (Zürich, 1994), vol 2, 1995, Birkhäuser: Birkhäuser Basel), 1384-1394, (MR1404040) · Zbl 0843.05003
[79] Vershik, A. M., Statistical mechanics of combinatorial partitions, and their limit shapes, Funkc. Anal. Prilozh., 30, 2, 19-39, 1996, English translation: Funct. Anal. Appl. 30 (1996), 90-105 (MR1402079) · Zbl 0868.05004
[80] Vershik, A. M., Limit distribution of the energy of a quantum ideal gas from the viewpoint of the theory of partitions of natural numbers, Usp. Mat. Nauk, 52, 2, 139-146, 1997, English translation: Russian Math. Surveys 52 (1997), 379-386 (MR1480142) · Zbl 0927.60089
[81] Vershik, A. M.; Freĭman, G. A.; Yakubovich, Yu. V., A local limit theorem for random partitions of natural numbers, Teor. Veroyatn. Primen., 44, 506-525, 1999, (Russian); Freiman, G.; Vershik, A. M.; Yakubovich, Yu. V., A local limit theorem for random strict partitions, Theory Probab. Appl., 44, 453-468, 2000, (MR1805818) · Zbl 0969.60034
[82] Vershik, A. M.; Kerov, S. V., Asymptotics of the Plancherel measure of the symmetric group and the limit form of Young tableaux, Dokl. Akad. Nauk SSSR, 233, 1024-1027, 1977, English translation: Soviet Math. Doklady 18 (1977), 527-531 (MR0480398) · Zbl 0406.05008
[83] Vershik, A. M.; Kerov, S. V., Asymptotic behavior of the maximum and generic dimensions of irreducible representations of the symmetric group, Funkc. Anal. Prilozh., 19, 25-36, 1985, English translation: Funct. Anal. Appl. 19 (1985), 21-31 (MR0783703) · Zbl 0592.20015
[84] Vershik, A.; Yakubovich, Yu., The limit shape and fluctuations of random partitions of naturals with fixed number of summands, Mosc. Math. J., 1, 457-468, 2001, (MR1877604) · Zbl 0996.05006
[85] Vershik, A.; Yakubovich, Yu., Fluctuations of the maximal particle energy of the quantum ideal gas and random partitions, Commun. Math. Phys., 261, 759-769, 2006, (MR2197546) · Zbl 1113.82010
[86] Whittaker, E. T.; Watson, G. N., A Course of Modern Analysis: An Introduction to the General Theory of Infinite Processes and of Analytic Functions; with an Account of the Principal Transcendental Functions, Cambridge Mathematical Library, 1996, Cambridge University Press: Cambridge University Press Cambridge, (MR1424469) · Zbl 0951.30002
[87] Wright, E. M., Asymptotic partition formulae, III. Partitions into k-th powers, Acta Math., 63, 143-191, 1934, (MR1555393) · Zbl 0009.30001
[88] Wright, E. M., The asymptotic expansion of the generalized Bessel function, Proc. Lond. Math. Soc. (2), 38, 257-270, 1935, (MR1576315) · Zbl 0010.21103
[89] Yakubovich, Yu., Ergodicity of multiplicative statistics, J. Comb. Theory, Ser. A, 119, 1250-1279, 2012, (MR2915644) · Zbl 1242.05021
[90] Yeh, J., Martingales and Stochastic Analysis. Series on Multivariate Analysis, 1, 1995, World Scientific: World Scientific Singapore, (MR1412800) · Zbl 0848.60001
[91] Yong, A., Critique of Hirsch’s citation index: a combinatorial Fermi problem, Not. Am. Math. Soc., 61, 1040-1050, 2014, (MR3241560) · Zbl 1338.05014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.