{"id":"2e9c34df-4f20-4903-825a-aaaec47f87c0","arxiv_id":"2501.11731","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A new algorithm estimates orbit counts by multiplying estimates of orbit-count ratios from Burnside process samples, and estimates k(U_n(F_q)) for q=2,3 up to n=32.","lead":"This paper introduces a general Monte Carlo algorithm for counting group orbits by combining the Burnside process with importance sampling. It applies the method to estimate the number of conjugacy classes of unitriangular matrices over finite fields, with new numerical estimates up to n=32.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The numerical estimates for n>16 rest on an unverified burn-in assumption and on a variance bound whose proof is only sketched for the final level; both are testable gaps, not contradictions.","rationale":"The reader's weakest assumption is precisely the most load-bearing concern: the finite-run algorithm invokes Proposition 4.1 as if the Burnside chain were at its stationary distribution, but no mixing time is proved or even diagnosed by varying burn-in. This matters because the manuscript's headline empirical contribution is the n <= 32 estimates and the apparent approach to the 1/12 exponent; a systematic bias in every ratio estimate would invalidate those numbers while leaving the theoretical estimator identity intact. I also flag the explicit omission in Section 4.5, where Theorem 4.1 is proved only for m = N and the remaining cases are dismissed as similar. The variance bound in Corollary 4.1.1 is the stated justification for importance sampling at all levels, so this is not a purely cosmetic gap. The paper has real independent support: the estimator derivation is clean, the code is available, and the n <= 16 match with known exact values is a meaningful sanity check. Those facts prevent the concern from being fatal, but they do not replace a burn-in sensitivity test or a mixing-time argument. The verdict should remain CONDITIONAL, requiring either a substantial justification of the burn-in choice, confidence intervals or diagnostics, and ideally a proof or complete proof sketch of Theorem 4.1 for all levels, or a softening of the numerical claims. No change to the reader's verdict is needed.","tokens_in":14304,"tokens_out":6392,"duration_ms":63621,"concrete_test":"Rerun the published code for q = 2, n = 20 (and n = 24 if feasible) with B_m = 10^3, 10^4, 10^5, 10^6 for all m, using several independent chains initialized from the identity and from random elements of H_m, and tabulate log_2 of the final estimate. If the estimates shift by more than about 0.1 in log_2 across burn-in lengths or vary substantially across starts, then the Section 4.4 values for n > 16 are not reliable beyond the known n <= 16 range. Additionally, report per-level ratio estimates and their standard errors for one burn-in setting.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central numerical claim in Section 4.4 depends on the Burnside chain on each pattern group H_m being at or very near stationarity after B_m = 100000 burn-in steps, but no mixing-time bound is supplied and no diagnostic varies B_m. Proposition 4.1 is an exact identity only at stationarity; increasing N_m from 100000 to 300000 in Figures 3-6 reduces Monte Carlo error after burn-in but cannot remove a systematic burn-in bias. Thus the estimates for n > 16 could drift with B_m even though they appear stable in N_m. The paper itself flags this in Section 5, calling useful rates of convergence for the Burnside process 'an important theoretical problem.' A second gap is explicit in Section 4.5: Theorem 4.1 is stated for all 1 <= m <= N, but the proof treats only m = N and says the other cases are 'similar and omitted.' Since Corollary 4.1.1 uses Theorem 4.1 to justify the importance sampling step at every level, the variance control behind the algorithm is not actually established for all levels. Both gaps concern the reliability of the reported k(U_n(F_q)) values and the 'efficient algorithm' claim, not the unbiasedness identity itself.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14569,"tokens_out":5883,"duration_ms":59367,"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":[{"comment":"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.","section":"4.5, Theorem 4.1"},{"comment":"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.","section":"4.4"},{"comment":"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.","section":"4.4"},{"comment":"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.","section":"3"}],"minor_comments":[{"comment":"The word 'herafter' is a typo and should be 'hereafter'.","section":"Page 3"},{"comment":"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.","section":"2.1"},{"comment":"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.","section":"Figures 3-6"},{"comment":"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.","section":"Equation (1)"},{"comment":"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.","section":"4.2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is in scope and the core estimator is sound. The principal risk is that the headline numerical estimates are stated more strongly than the unverified burn-in assumption and the incomplete proof of Theorem 4.1 allow; a revision that addresses these two points would considerably strengthen the paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The reader's conditional verdict is about right, and the stress-test note lands on the actual weak points. The genuinely new thing is Proposition 3.1: an exact identity that lets you estimate a ratio of orbit counts between successive levels by importance sampling from the Burnside stationary distribution. That is natural once you see it, but I don't think it appears in the earlier literature. The specialization to unitriangular groups via pattern groups is well chosen, and the code is posted and reproducible. Theorem 4.1's deterministic bound, q^{-1} ≤ k(H_m)/k(H_{m-1}) ≤ q^3, is a real statement, and the proof for m = N is a real proof using a clever probabilistic interpretation of Burnside's lemma. If the other cases really are similar, that is minor, but as written it is a gap: Corollary 4.1.1, which gives the variance control used at every level, depends on the full theorem.\n\nThe bigger soft spot is the numerical section. The estimator is unbiased only at stationarity of the Burnside chain on each pattern group, and no mixing bound is known for these chains; the paper fixes B_m = 100000 including for the largest groups, and Section 5 openly says that useful rates of convergence are an important open problem. The stability across N_m = 100k, 200k, 300k is reassuring against Monte Carlo error after burn-in, but it says nothing about systematic burn-in bias. Varying B_m or showing trace plots would have helped. That said, the paper is honest about the gap, and I see no circularity: no parameter is fitted to the known values, and the n ≤ 16 agreement is a genuine check.\n\nMy take: the theoretical core is solid and the estimator identity is a contribution worth having. The numerical claims for n > 16 are plausible but not rigorously established, despite the word 'efficient' in the abstract. A referee should ask for the missing cases of Theorem 4.1, a burn-in diagnostic or mixing-time evidence, and confidence intervals, or a softened numerical claim. That is a normal revision path, not a fatal flaw. I'd send it to a good referee.","headline":"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.","tokens_in":15063,"tokens_out":2105,"would_cite":true,"duration_ms":21234,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60J10","20G40","05A15","65C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["Burnside process","importance sampling","orbit counting","unitriangular groups","conjugacy classes","pattern groups","Higman conjecture","approximate counting"],"falsifier":"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.","tokens_in":14100,"feed_emoji":"🎲","tokens_out":5292,"duration_ms":50428,"temperature":0.7,"pith_summary":"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.","feed_headline":"Burnside + importance sampling counts orbits to n = 32","feed_subtitle":"For unitriangular groups over F2 and F3, estimates match all known exact counts and support a 1/12 growth exponent.","key_machinery":"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).","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces the Burnside process, the Markov chain the algorithm runs to draw near-uniform orbit samples.","marker":"[20]"},{"why":"Supplies the importance-sampling sample-size theory used to justify convergence of the Monte Carlo averages.","marker":"[6]"},{"why":"Provides the known exact values for n ≤ 16 and reports the status of Higman's conjecture, used as benchmark.","marker":"[31]"},{"why":"Conjectures that the lower bound in (1) is sharp, the target of the numerical evidence.","marker":"[39]"},{"why":"Develops pattern groups and their supercharacters, used to build the nested sequence H_m.","marker":"[10]"},{"why":"Gives earlier computational data and the refined polynomial-degree conjecture ⌊n(n+6)/12⌋ referenced in the numerics.","marker":"[42]"},{"why":"Connects approximate counting and approximate sampling, the framework that motivates reducing counting to Burnside sampling.","marker":"[37]"}],"fun_headline_variants":["Burnside + importance sampling: orbit counts to n=32","Importance sampling boosts Burnside orbit counting to n=32","Orbit counting to n=32 matches exact known counts","Orbit counting via Burnside process and importance sampling hits n=32","Counting orbits up to n=32 with Burnside importance sampling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Burnside + importance sampling: orbit counts to n=32","Importance sampling boosts Burnside orbit counting to n=32","Orbit counting to n=32 matches exact known counts","Orbit counting via Burnside process and importance sampling hits n=32","Counting orbits up to n=32 with Burnside importance sampling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002207,"raw_usage":{"total_tokens":8483,"prompt_tokens":824,"completion_tokens":7659,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":440,"completion_tokens_details":{"reasoning_tokens":7572}},"tokens_in":440,"tokens_out":7659,"duration_ms":54920,"temperature":1.0,"reasoning_tokens":7572,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:55:14.409849+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Uniform sampling modulo a group of symmetries using Markov chain simulation","cited_arxiv_id":null,"evidence_quote":"Introduces the Burnside process, the Markov chain the algorithm runs to draw near-uniform orbit samples."},{"cited_title":"The sample size required in impor- tance sampling","cited_arxiv_id":null,"evidence_quote":"Supplies the importance-sampling sample-size theory used to justify convergence of the Monte Carlo averages."},{"cited_title":"On Higman's $k(U_n(\\mathbb{F}_q))$ conjecture","cited_arxiv_id":"1507.00411","evidence_quote":"Provides the known exact values for n ≤ 16 and reports the status of Higman's conjecture, used as benchmark."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Conjectures that the lower bound in (1) is sharp, the target of the numerical evidence."},{"cited_title":"Supercharacter formulas for pattern groups","cited_arxiv_id":null,"evidence_quote":"Develops pattern groups and their supercharacters, used to build the nested sequence H_m."},{"cited_title":"Conjugacy classes in unitriangular matrices","cited_arxiv_id":null,"evidence_quote":"Gives earlier computational data and the refined polynomial-degree conjecture ⌊n(n+6)/12⌋ referenced in the numerics."},{"cited_title":"Approximate counting, uniform genera- tion and rapidly mixing Markov chains","cited_arxiv_id":null,"evidence_quote":"Connects approximate counting and approximate sampling, the framework that motivates reducing counting to Burnside sampling."}],"review_version":1}