Pith. sign in

REVIEW 4 major objections 5 minor 43 references

Counting the number of group orbits by marrying the Burnside process with importance sampling

T0 review · 4 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A new algorithm estimates the number of orbits of a finite group action by splitting it into ratios, estimating each ratio with the Burnside process and importance sampling, and applies it to count conjugacy classes of unitriangular…

desk verdict Worth refereeing: the estimator identity is new and clean, but the numerical claims need a burn-in diagnostic and the variance-bound proof needs the missing cases. read the letter →

arxiv 2501.11731 v2 pith:4TNCITGU submitted 2025-01-20 math.PR math.COmath.GRstat.CO

Persi Diaconis , Chenyang Zhong This is my paper · ORCID
classification math.PRmath.COmath.GRstat.CO MSC 60J1020G4005A1565C05
keywords BurnsideprocessimportancesamplingorbitcountingunitriangulargroupsconjugacyclassespatternHigmanconjectureapproximate
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes a general Monte Carlo algorithm for approximately counting the number of orbits of a finite group action, a problem that is #P-complete in many natural cases. The method splits the orbit count into a product of successive ratios and estimates each ratio by running the Burnside process (a Markov chain whose stationary distribution favors large orbits) and applying importance sampling with a stabilizer-based statistic. For unitriangular groups U_n(F_q) acting on themselves by conjugation, the algorithm is shown to control the variance of each ratio via $q^{{-1}}$ ≤ k(H_m)/k(H_{m-1}) ≤ $q^{3}$, and numerical runs for q = 2, 3 reach n = 32, matching all known exact values for n ≤ 16 and supporting the conjecture that log_q k(U_n) grows like (1/12) times n choose 2.

What carries the argument

The Burnside process is the Markov chain on X that, from x, draws g uniformly from the stabilizer G_x and then moves to a uniformly chosen fixed point of g; its stationary distribution is π(x) ∝ |O(x)|, so after lumping it samples orbits almost uniformly. The estimator multiplies the reciprocal of each importance-sampling average, and the stabilizer sizes |C_H(g)| for pattern groups are computable in polynomial time because centralizers in pattern groups are linear spaces over F_q. Theorem 4.1, the variance-control result, is proved by coupling U_n and its index-(1,2) pattern subgroup through a single rejection-sampling algorithm that generates a uniform A ∈ U_n, a uniform B in its centralizer, and a uniform B̃ in the centralizer of φ(A); a dimension comparison of the acceptance subspaces gives $q^{{-3}}$k(G) ≤ k(H) ≤ q k(G).

What would settle it

Compute k(U_n(F_q)) exactly for a value of n beyond the current limit (e.g. n = 17 or n = 18 for q = 2 or 3) and compare it with the algorithm's estimate; alternatively, rerun the same experiments with burn-in increased from $10^{5}$ to $10^{6}$ and check whether any of the estimated ratios k(H_{m-1})/k(H_m) shifts by more than the reported Monte Carlo error. A third test would be to bound the total variation distance to stationarity of the Burnside chain on H_m after t steps for t ≤ $10^{5}$ and show it is not small.

Watch

Extended reading notes

Core claim

The central claim is that a fairly generic orbit-counting problem can be reduced to estimating a product of N-1 ratios, each ratio being recoverable from one importance-sampling average over states of the Burnside process. Proposition 3.1 makes this exact: with T_{i+1} drawn from the Burnside stationary distribution, the ratio k(X_i,G_i)/k(X_{i+1},G_{i+1}) equals a constant times the expectation of |Stab_i(φ_i(T))| / (|Stab_{i+1}(T)| · |$φ_i^{{-1}}$(φ_i(T))|). For the unitriangular specialization, the paper proves Theorem 4.1, that adjacent pattern-group class counts differ by at most a factor $q^{3}$ in one direction and $q^{{-1}}$ in the other, which keeps the importance sampling variance bounded by O($q^{2}$) times the ratio. On this basis the paper reports estimated conjugacy class counts for U_n(F_2) and U_n(F_3) up to n = 32, with the estimates for n ≤ 16 close to the known exact values and the normalized logarithms trending to 1/12.

Load-bearing premise

The reported numbers for n up to 32 rest on the untested assumption that after 100,000 burn-in steps the Burnside chain on each pattern group is already sampling from its stationary distribution; no mixing-time bound is proved for these chains.

Editorial extensions

If this is right

  • For q = 2 and q = 3, the algorithm produces the first estimates of k(U_n(F_q)) beyond the n = 16 limit of exact enumeration, up to n = 32.
  • The normalized estimates log_q k(U_n) / (n choose 2) trend toward 1/12, supporting Soffer's conjecture that Higman's lower bound gives the true exponent.
  • The variance bound for each ratio (standard deviation at most q^2 times the ratio) means the product estimate does not blow up exponentially with n, provided the Burnside chain is mixed.
  • The same template—nested sets, efficient stabilizer-size oracles, and Burnside sampling—applies to any action with a natural filtration, including the partitions, trees, and contingency tables mentioned in the paper.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A cheap check of the unproved burn-in assumption would be to rerun the q = 2, 3 experiments with burn-in 10^6 and compare; any shift in the estimated ratios would indicate the chain had not yet mixed at 10^5 steps.
  • The q^{-1} to q^3 ratio bounds suggest that the sequence k(H_m) is quite smooth, which may be of independent interest and could support a future proof of polynomiality for fixed n by induction along this filtration.
  • Outside pattern groups, the same estimator needs only a stabilizer-size oracle and a coupled sequence; adapting it to symmetric-group actions on k-tuples (already validated in the paper for n = 20) suggests it could be a generic tool for unlabeled enumeration problems.
  • If the 1/12 exponent is correct, it would confirm that most of the mass of k(U_n(F_q)) is carried by 'large' conjugacy classes in a very precise sense, connecting class-count growth to the geometry of upper triangular matrices.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper proposes a Monte Carlo method for approximate orbit counting. It assumes a nested sequence of finite sets X_i and groups G_i with surjective maps, and writes the orbit count as a product of ratios k(X_i,G_i)/k(X_{i+1},G_{i+1}). Each ratio is estimated by sampling from the Burnside process on X_{i+1} and applying an importance-sampling identity (Proposition 3.1, Equation (3)). The method is specialized to conjugacy classes of unitriangular groups U_n(F_q), using pattern groups H_0,...,H_N as the nested sequence; Proposition 4.1 gives the unbiased ratio identity, Theorem 4.1 asserts ratio bounds q^{-1} <= k(H_m)/k(H_{m-1}) <= q^3, and Corollary 4.1.1 converts these into a variance bound. The numerical section reports estimates for q=2,3 and n up to 32, with burn-in B_m=100000 and sample sizes N_m in {100000,200000,300000}; the values for n<=16 are close to known exact counts, and the normalized log-counts appear to approach 1/12. The paper explicitly notes that mixing-time rates for the Burnside process are open.

Significance. If the numerical estimates are trustworthy, the paper makes a useful practical contribution by extending reachable values of k(U_n(F_q)) beyond n=16 and by giving evidence for Soffer's conjecture. The derivation of the ratio estimator is clean, the code is provided, and the deterministic adjacent-ratio bound is an interesting result in itself. The main caveats are that the variance bound is proved only for the final level and that the numerical reliability rests on an unverified burn-in assumption.

major comments (4)
  1. [4.5, Theorem 4.1] The proof of Theorem 4.1 is given only for m=N, and the sentence 'the proof for other cases is similar and omitted' is not accompanied by a reduction. The displayed arguments, especially the dimension bounds (17) and (18), concern the specific subspaces U_1,U_2,W_1,W_2 for the first row of the final pair. Since Corollary 4.1.1 and Section 4.3 use Theorem 4.1 at every level m, the variance control for the importance sampling step is not established for the intermediate pattern groups. Please supply a complete proof for all m, or state the general bound as a conjecture and adjust the claims accordingly.
  2. [4.4] The choice B_m=100000 is heuristic: Proposition 4.1 is an identity at stationarity, but no mixing-time bound is proved for the Burnside chain on pattern groups, and the numerical experiments never vary the burn-in length. Increasing N_m from 100000 to 300000 only shrinks post-burn-in Monte Carlo error; it cannot remove a systematic bias if the chain has not converged by step 100000. Because Section 5 acknowledges that useful mixing-time rates are an open problem, the estimates for n>16 are conditional on an unverified assumption. Please add a burn-in sensitivity analysis or a stationarity diagnostic, and phrase the n>16 numbers as exploratory.
  3. [4.4] No confidence intervals or standard errors are reported for any of the estimates, so the statements that the estimates for different N_m 'match closely' and that the n<=16 values are 'very close' to the true values are visual assessments. Please report standard errors from independent replications or a batch-means procedure for the plotted log-counts and normalized counts.
  4. [3] The abstract and Section 3 describe the method as efficient, but no formal complexity bound is given for Algorithm 1; the sentence about standard large deviations estimates at the end of Section 3 appeals to rapid mixing without stating conditions. In the specialized setting, the numerical choices of B_m and N_m and the per-step Gaussian elimination cost should be converted into an explicit running-time statement, or the efficiency claim should be limited to the observed practical performance.
minor comments (5)
  1. [Page 3] The word 'herafter' is a typo and should be 'hereafter'.
  2. [2.1] The notation for group actions is not fully consistent: the paper writes both yg=y and xh=h with a right action; please fix the convention in the definitions of X^g and G_x.
  3. [Figures 3-6] The figures for the three choices of N_m would be easier to read with a legend and with distinct markers rather than colors alone; the absence of error bars also makes the plots hard to interpret.
  4. [Equation (1)] Equation (1) has a typesetting problem in the exponents, with 'n2 12' and 'n2 4' appearing instead of n^2/12 and n^2/4; please fix the rendering.
  5. [4.2] The definition of H_m via k_m,l_m is given by an equation that is easy to misread; an explicit example for n=4 or a verbal description of the indexing order would help, since the nested sequence is central to the algorithm.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the estimator is derived from exact orbit-stabilizer identities, and the numerical benchmarks are external; open gaps are reliability concerns rather than circular steps.

full rationale

The paper's derivation chain is self-contained. Equation (7) and Proposition 4.1 are exact identities: the importance-sampling statistic K_m is defined directly from stabilizer sizes, and the proof uses only the orbit-stabilizer theorem, with no parameter fitted from the k(U_n(F_q)) values later reported. Theorem 4.1 is a deterministic inequality proved by constructing a coupled sampling algorithm; it does not import a load-bearing result from the authors' prior work, and the omitted 'similar' cases for m < N are a proof-completeness gap, not a circular reduction. The n <= 16 agreement is checked against independently known exact values, and the n > 16 curves are extrapolations of an algorithm that was not tuned to produce the 1/12 limit. The self-citations that occur ([8,12] in the illustrative S_n example, and [11,43] in the final remarks) concern mixing-time context and are not load-bearing for the new counting claims. The acknowledged lack of a Burnside-chain mixing bound for the burn-in choice B_m = 100000 in Section 4.4, and the sketched variance proof in Section 4.5, are correctness and reliability limitations; they do not make any prediction equivalent to its inputs by construction.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central claims rest on standard finite group facts and on the algorithmic assumption that centralizer bases are computable by linear algebra. The numerical section additionally assumes a heuristic burn-in time; this is the main extra, non-standard premise. There are no invented entities and no fitted parameters in the theoretical parts.

free parameters (2)
  • burn_in_B_m = 100000
    Number of burn-in steps for the Burnside chain at each level m; chosen by hand without a mixing time bound.
  • sample_size_N_m = 100000, 200000, 300000
    Number of post-burn-in samples used in the importance sampling averages; varied to assess stability of the estimates.
assumptions (3)
  • standard math Orbit-stabilizer theorem and Burnside's lemma hold for finite group actions.
    Used in Propositions 3.1 and 4.1 and in equation (10) of Section 4.5.
  • domain assumption For each pattern group U_J, a basis of the centralizer linear space can be computed efficiently by Gaussian elimination.
    Used in Section 4.1 to sample uniformly from centralizers; assumed to hold for all pattern groups in the nested sequence.
  • ad hoc to paper The Burnside process on each pattern group H_m is near its stationary distribution after B_m=100000 burn-in steps.
    Assumed for the numerical results in Section 4.4; no mixing time bound is provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Counting the number of group orbits by marrying the Burnside process with importance sampling." pith.science (2026). https://pith.science/paper/4TNCITGU

@misc{pith2026250111731,
  author       = {Pith},
  title        = {Pith review of: Counting the number of group orbits by marrying the Burnside process with importance sampling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4TNCITGU}},
  note         = {Machine review of arXiv:2501.11731}
}
read the original abstract

This paper introduces a novel and general algorithm for approximately counting the number of orbits under group actions. The method is based on combining the Burnside process and importance sampling. Specializing to unitriangular groups yields an efficient algorithm for estimating the number of conjugacy classes of such groups.

Figures

Figures reproduced from arXiv: 2501.11731 by the authors.

Figure 1
Figure 1. Logarithm of true and estimated number of orbits [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Histogram of logarithm of estimated number of orbits for [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Plot of log2 (k(Un(F2))) for n = 1, 2, · · · , 32 13 [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Plot of log2 (k(Un(F2)))/(n 2 ) for n = 1, 2, · · · , 32 [PITH_FULL_IMAGE:figures/full_fig_p014_4.png]
Figure 5
Figure 5. Figure 5: Plot of log3 (k(Un(F3))) for n = 1, 2, · · · , 32 14 [PITH_FULL_IMAGE:figures/full_fig_p014_5.png]
Figure 6
Figure 6. Figure 6: Plot of log3 (k(Un(F3)))/(n 2 ) for n = 1, 2, · · · , 32 4.5 Proof of Theorem 4.1 This subsection gives the proof of Theorem 4.1 based on a probabilistic inter￾pretation of the Burnside process for sampling from conjugacy classes of pattern groups (as described in Sect…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 41 canonical work pages

  1. [1]

    Reversible Markov chains and random walks on graphs

    Aldous, D., and Fill, J. Reversible Markov chains and random walks on graphs. https://www.stat.berkeley.edu/~aldous/RWG/book.pdf, 2002

    work page 2002

  2. [2]

    An algorithm for uniform generation of unlabeled trees (P´ olya trees), with an extension of Cayley’s formula

    Bartholdi, L., and Diaconis, P. An algorithm for uniform generation of unlabeled trees (P´ olya trees), with an extension of Cayley’s formula. arXiv preprint arXiv:2411.17613 (2024)

    arXiv 2024

  3. [3]

    Broder, A. Z. How hard is it to marry at random? (On the approximation of the permanent). In Proceedings of the eighteenth annual ACM symposium on Theory of computing (1986), pp. 50–58

    work page 1986

  4. [4]

    Estimating the number of species: a review

    Bunge, J., and Fitzpatrick, M. Estimating the number of species: a review. Journal of the American Statistical Association 88 , 421 (1993), 364–373

    work page 1993

  5. [5]

    Inference in hidden Markov models

    Capp´e, O., Moulines, E., and Ryd ´en, T. Inference in hidden Markov models. Springer Science & Business Media, 2006

    work page 2006

  6. [6]

    The sample size required in impor- tance sampling

    Chatterjee, S., and Diaconis, P. The sample size required in impor- tance sampling. The Annals of Applied Probability 28, 2 (2018), 1099–1135

    work page 2018

  7. [7]

    Mixing times for Burnside processes

    Chen, W.-K. Mixing times for Burnside processes. Master’s thesis, Na- tional Chiao Tung University, 2006

    work page 2006

  8. [8]

    Analysis of a Bose-Einstein Markov chain

    Diaconis, P. Analysis of a Bose-Einstein Markov chain. Ann. Inst. H. Poincar´ e Probab. Statist. 41, 3 (2005), 409–418. 20

    work page 2005

Show all 43 references
  1. [9]

    Statistical enumeration of groups by double cosets

    Diaconis, P., and Simper, M. Statistical enumeration of groups by double cosets. Journal of Algebra 607 (2022), 214–246

    2022

  2. [10]

    Supercharacter formulas for pattern groups

    Diaconis, P., and Thiem, N. Supercharacter formulas for pattern groups. Transactions of the American Mathematical Society 361 , 7 (2009), 3501–3533

    2009

  3. [11]

    Poisson approximation for large permuta- tion groups

    Diaconis, P., and Tung, N. Poisson approximation for large permuta- tion groups. arXiv preprint arXiv:2408.06611 (2024)

    2024 arXiv

  4. [12]

    Hahn polynomials and the Burnside pro- cess

    Diaconis, P., and Zhong, C. Hahn polynomials and the Burnside pro- cess. Ramanujan J. 61 , 2 (2023), 567–595

    2023

  5. [13]

    Dittmer, S. J. Counting linear extensions and contingency tables . PhD thesis, University of California, Los Angeles, 2019

    2019

  6. [14]

    Goldberg, L. A. Automating P´ olya theory: The computational com- plexity of the cycle index polynomial. Information and Computation 105 , 2 (1993), 268–288

    1993

  7. [15]

    Burnside process

    Goldberg, L. A., and Jerrum, M. The “Burnside process” con- verges slowly. In Randomization and approximation techniques in com- puter science (Barcelona, 1998) , vol. 1518 of Lecture Notes in Comput. Sci. Springer, Berlin, 1998, pp. 331–345

    1998

  8. [16]

    A., and Jerrum, M

    Goldberg, L. A., and Jerrum, M. Counting unlabelled subtrees of a tree is #P-complete. LMS Journal of Computation and Mathematics 3 (2000), 117–124

    2000

  9. [17]

    Good, I. J. The population frequencies of species and the estimation of population parameters. Biometrika 40 , 3-4 (1953), 237–264

    1953

  10. [18]

    M., and Handscomb, D

    Hammersley, J. M., and Handscomb, D. C. Monte Carlo methods . Methuen & Co., Ltd., London; Barnes & Noble, Inc., New York, 1965

    1965

  11. [19]

    Enumerating p-groups

    Higman, G. Enumerating p-groups. I. Inequalities. Proc. London Math. Soc. (3) 10 (1960), 24–30

    1960

  12. [20]

    Uniform sampling modulo a group of symmetries using Markov chain simulation

    Jerrum, M. Uniform sampling modulo a group of symmetries using Markov chain simulation. In Expanding graphs (Princeton, NJ, 1992) , vol. 10 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci. Amer. Math. Soc., Providence, RI, 1993, pp. 37–47

    1992

  13. [21]

    Computational P´ olya theory

    Jerrum, M. Computational P´ olya theory. InSurveys in combinatorics, 1995 (Stirling), vol. 218 of London Math. Soc. Lecture Note Ser. Cambridge Univ. Press, Cambridge, 1995, pp. 103–118

    1995

  14. [22]

    Counting, sampling and integrating: algorithms and complex- ity

    Jerrum, M. Counting, sampling and integrating: algorithms and complex- ity. Springer Science & Business Media, 2003. 21

    2003

  15. [23]

    R., V aliant, L

    Jerrum, M. R., V aliant, L. G., and V azirani, V. V.Random gener- ation of combinatorial structures from a uniform distribution. Theoretical Computer Science 43 (1986), 169–188

    1986

  16. [24]

    Keller, T. M. Orbits in finite group actions. In Groups St. Andrews 2001 in Oxford. Vol. II , vol. 305 of London Math. Soc. Lecture Note Ser. Cambridge Univ. Press, Cambridge, 2003, pp. 306–331

    2001

  17. [25]

    G., and Snell, J

    Kemeny, J. G., and Snell, J. L. Finite Markov chains . Undergrad- uate Texts in Mathematics. Springer-Verlag, New York-Heidelberg, 1976. Reprinting of the 1960 original

    1976

  18. [26]

    Liu, J. S. Monte Carlo strategies in scientific computing . Springer Science & Business Media, 2008

    2008

  19. [27]

    Importance sampling for families of distributions

    Madras, N., and Piccioni, M. Importance sampling for families of distributions. The Annals of Applied Probability 9 , 4 (1999), 1202–1225

    1999

  20. [28]

    Constructing modules of algebra groups

    Marberg, E. Constructing modules of algebra groups. Undergraduate thesis, Stanford University (2008)

    2008

  21. [29]

    Combinatorial methods of character enumeration for the unitriangular group

    Marberg, E. Combinatorial methods of character enumeration for the unitriangular group. Journal of Algebra 345 , 1 (2011), 295–323

    2011

  22. [30]

    Mixing times of a Burnside process Markov chain on set partitions

    Paguyo, J. Mixing times of a Burnside process Markov chain on set partitions. arXiv preprint arXiv:2207.14269 (2022)

    2022

  23. [31]

    On Higman’s k(Un(Fq)) conjecture

    Pak, I., and Soffer, A. On Higman’s k(Un(Fq)) conjecture. arXiv preprint arXiv:1507.00411 (2015)

    2015 arXiv

  24. [32]

    Pollock, K. H. Capture-recapture models. Journal of the American Statistical Association 95 , 449 (2000), 293–296

    2000

  25. [33]

    P´olya, G., and Read, R. C. Combinatorial enumeration of groups, graphs, and chemical compounds. Springer-Verlag, New York, 1987. P´ olya’s contribution translated from the German by Dorothee Aeppli

    1987

  26. [34]

    Mixing times for the commuting chain on CA groups.Journal of Theoretical Probability 35, 1 (2022), 457–483

    Rahmani, J. Mixing times for the commuting chain on CA groups.Journal of Theoretical Probability 35, 1 (2022), 457–483

    2022

  27. [35]

    P., and Casella, G

    Robert, C. P., and Casella, G. Monte Carlo statistical methods. Springer Texts in Statistics (2004), 274

    2004

  28. [36]

    Algorithms for random generation and counting: a Markov chain approach

    Sinclair, A. Algorithms for random generation and counting: a Markov chain approach. Springer Science & Business Media, 2012

    2012

  29. [37]

    Approximate counting, uniform genera- tion and rapidly mixing Markov chains

    Sinclair, A., and Jerrum, M. Approximate counting, uniform genera- tion and rapidly mixing Markov chains. Information and Computation 82 , 1 (1989), 93–133. 22

    1989

  30. [38]

    Upper bounds on the number of conjugacy classes in unitri- angular groups

    Soffer, A. Upper bounds on the number of conjugacy classes in unitri- angular groups. Journal of Group Theory 19 , 6 (2016), 1063–1095

    2016

  31. [39]

    Soffer, A. L. Combinatorics of conjugacy classes in Un(Fq). PhD thesis, University of California, Los Angeles, 2016

    2016

  32. [40]

    Solow, A. R. On the Bayesian estimation of the number of species in a community. Ecology 75, 7 (1994), 2139–2142

    1994

  33. [41]

    Importance sampling: Applications in communications and detection

    Srinivasan, R. Importance sampling: Applications in communications and detection. Springer Science & Business Media, 2002

    2002

  34. [42]

    Conjugacy classes in unitriangular matrices

    Vera-L´opez, A., and Arregi, J. Conjugacy classes in unitriangular matrices. Linear Algebra and its Applications 370 (2003), 85–124

    2003

  35. [43]

    Mixing time of the commuting chain on the symmetric group

    Zhong, C. Mixing time of the commuting chain on the symmetric group. Tech. rep., Department of Statistics, Columbia University, 2024. 23

    2024

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.