Pith. sign in

REVIEW 1 major objections 5 minor 30 references

The Dimension of Nonterminating Resampling Computations

T0 review · 1 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read By powering the probabilities of repair actions, the paper shows that nontermination sets are governed by one trace-series bound, and that ordinary transition data can hide almost all of their geometry.

desk verdict Solid powered-LLL extension with a real gap in the effective-dimension coding proof. read the letter →

arxiv 2607.17469 v1 pith:KMPPQBMK submitted 2026-07-20 cs.CC cond-mat.stat-mechcs.LGmath.COmath.PR

Yunbei Xu This is my paper
classification cs.CCcond-mat.stat-mechcs.LGmath.COmath.PR MSC 68Q3028A8060J10
keywords resamplingcomputationsnonterminationsetHausdorffdimensioneffectiveRényipowersumspoweredrepairkernelsLovászlocallemmak-SAT
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 tries to establish that a single family of quantities—the Rényi power sums of the random-tape prefixes on which a resampling computation is still alive—controls both when a randomized repair algorithm stops and how large, in dimension and algorithmic complexity, the set of tapes on which it runs forever can be. The main theorem bounds these sums, term by term, by a commutative trace series, uniformly over every deterministic nonanticipating repair rule, provided the powered repair matrices for nonadjacent flaws commute. At power one the bound is a termination estimate; varying the power gives weak-source robustness and bounds on the Hausdorff and effective dimensions of nontermination. If the theorem is right, survival tails, robustness to imperfect randomness, and the geometry of exceptional tapes are all governed by one computable bound rather than by separate analyses.

What carries the argument

The central object is the source-power sum Z_T(s)=Σ_{w∈L_T} P[w]^s over minimal tape prefixes that survive T repairs, together with the powered action kernel K_{f,s}(σ,τ)=Σ_{a:Φ_f(σ,a)=τ} ρ_f(a|σ)^s. The proof mechanism is a direct full-prefix induction that bounds the powered mass of continuations inducing a given history DAG by b_s^T K_{H,s}1; when nonadjacent powered kernels commute, the history DAG collapses to a trace, and summing over traces yields the term-by-term inequality Z_T(s)≤γ_s a_T(s), whose generating function is 1/P_D(zλ(s)). The powered kernels do the load-bearing work: for s≠1 they retain Rényi-entropy information about action-label collisions that ordinary transition prob

What would settle it

Run the two P4 rules from Corollary 3.2 under the same tape source at a power s_0 strictly between their critical dimensions; if the rule claimed to be nonterminating stops with exponential tail, or the rule claimed to be robust runs forever, the sharp-threshold claim fails.

Watch

Extended reading notes

Core claim

For fixed s>0 and a process whose powered repair matrices K_{f,s} commute for nonadjacent flaws, the paper claims that every deterministic nonanticipating selector satisfies Z_T(s) ≤ γ_s a_T(s) for all T, where Z_T(s) is the sum of P[w]^s over minimal live prefixes of length T and a_T(s) is the T-th coefficient of the rational trace series 1/P_D(zλ(s)). At s=1 this gives termination estimates; at other s it bounds the Hausdorff dimension of the nontermination set and, under computability assumptions, the effective strong dimension of every nonterminating tape. The paper also claims that the family across s is not redundant: action labels that collide on the same state transition are invisibl

Load-bearing premise

The main theorem collapses if the powered repair rules for non-overlapping defects cannot be applied in either order without changing the probability-weighted outcome at the same exponent s, and the paper shows that ordinary power-one commutativity does not guarantee this.

Editorial extensions

If this is right

  • For bounded-dependence k-SAT, any redraw source with conditional block min-entropy above log_2 κ_D yields an exponential stopping tail, and the Hausdorff and effective dimensions of infinite runs are at most min{1, (log_2 κ_D)/k}.
  • The complexity of an individual infinite k-SAT run localizes: its effective dimension is bounded by the trace growth of the subgraph induced by the clauses repaired infinitely often.
  • For exact disagreement repair on any connected graph, the complete source-power law is governed by one tridiagonal matrix; its spectral radius determines the termination rate, the nontermination dimension, and the sharp weak-source domination threshold.
  • Two disagreement-repair maps on a four-vertex path with identical ordinary kernels and identical stopping-time law for every selector can have nontermination dimensions separated by nearly one, and there is a single dominated source on which one rule runs forever while the other stops exponentially.
  • A backward likelihood identity gives an exact per-run coding and tail bound that requires no commutativity assumption at all.

Reading between the lines

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

  • Inference: the same trace-series bound should also control the Laplace transform of the stopping time, not just the tail, which would give concentration inequalities for repair times in processes where the powered kernels commute.
  • Inference: the P4 separation suggests that any termination or local-lemma-style guarantee stated only at power one is intrinsically blind to action-label structure; algorithms that resample via non-uniform or label-dependent action sets may need powered-kernel commutativity even when ordinary matrices commute.
  • Inference: the displayed dependence on ϕ’s hidden collisions suggests a practical diagnostic: compute the powered kernels at the candidate dimension and check commutativity before trusting a dimension or weak-source bound from power-one data alone.
  • Inference: the backward identity likely extends beyond local repair to any backtracking or resampling process with injective reverse reconstruction, yielding pathwise coding bounds for algorithms that do not fit the commutativity framework.
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

1 major / 5 minor

Summary. The paper studies randomized resampling computations whose random tape may cause nontermination even when termination is almost sure. For each s > 0 it considers the source-power sum Z_T(s) = \sum_{w \in L_T} P[w]^s over minimal tape prefixes surviving T repairs. Under a powered commutation condition (5), Theorem 2.3 gives a termwise bound of Z_T(s) by a Cartier–Foata/Shearer trace series, uniformly over deterministic nonanticipating selectors. Consequences include exponential termination under weak sources, source-relative Hausdorff and effective dimension bounds for the nontermination set, k-SAT and rainbow-matching applications, and an exact disagreement-repair analysis showing that two maps with identical power-one kernels and identical stopping-time laws can have nearly opposite exceptional-tape dimensions. A backward likelihood identity gives pathwise coding and tail bounds.

Significance. The main theorem is a genuine source-power extension of matrix-commutative Lovász Local Lemma trace bounds, and the exact disagreement-repair example is striking: it shows that ordinary kernels and the full stopping-time law can miss essentially all information about weak-source robustness and nontermination dimension. The sharpness constructions for k-SAT are nontrivial and the paper is explicit about the powered-commutation assumption (5) and about what it does not prove. The axiomatic structure is clean: no ad hoc axioms are hidden, and the overlap with Harris et al. (2025) is acknowledged. The stress-test worry about the level-wise coding masses not forming a semimeasure does not, on reading, invalidate the coding conclusion, because Kraft–Chaitin applies to a prefix-free request family; however the manuscript's proof of the effective-dimension bound contains a sign error that must be fixed before the claim is established as written.

major comments (1)
  1. [Corollary 2.4, Eq. (22)] The proof of the effective-dimension conclusion is not written correctly. The defined masses κ_{T,s}(w)=P[w]^s/(\hat C_s \hat\vartheta_s^T) satisfy −log_2 κ_{T,s}=s log_2(1/P[w])+log_2 \hat C_s+T log_2(1/\hat\vartheta_s), not +T log_2 \hat\vartheta_s as displayed. If only these masses were used, the code-length bound would carry a positive T log(1/\hat\vartheta_s) term, which after division by source self-information gives only s+log(1/\hat\vartheta_s)/c, not the claimed s. The conclusion is salvageable: one can apply Kraft–Chaitin directly to the requested lengths L_w=s log_2(1/P[w])+log_2 \hat C_s+T log_2 \hat\vartheta_s, since \sum_w 2^{-L_w}=(\hat\vartheta_s^T Z_T(s))/\hat C_s≤1. This correction is load-bearing because Corollary 2.4 is the route to every effective-dimension statement in the paper (Cor 2.4, Thm 3.1, Cor 3.2, Thm 4.1, Cor 4.2, Thm 4.3, Cor 4.8).
minor comments (5)
  1. [Corollary 3.2, Eq. (36)] The displayed table for the maps H and L is very hard to read; the columns for x_i, y, u, v are not aligned. Please typeset it as an actual table. The intended assignment is recoverable from (37)–(38), but the table should match those formulas.
  2. [Eq. (40)] The notation H_s(χ) is called Rényi entropy, but base-two Rényi entropy of order s should be explicitly defined before this display.
  3. [Corollary 2.4 proof] The phrase 'prefix-free coding' is too terse. It would help to state explicitly that the coding is by Kraft–Chaitin requests on the prefix-free family L_T, not by a semimeasure on the whole prefix tree. The current wording invites the objection that the level-wise masses are not a semimeasure, although that objection is not fatal.
  4. [Theorem 4.7 proof] The reconstruction argument involving a 'unique selector-compatible linear extension' of a trace is intricate. A few more sentences explaining why the source-removal order is unique for a given deterministic selector would considerably improve verifiability.
  5. [Introduction / References] The references to the author's own recent preprints (Xu 2026a,b; Li–Xu 2026) are only motivational and do not enter the proofs; consider trimming them or explicitly marking them as background analogies.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: main theorem is proved from stated commutativity assumption; self-citations are motivational only.

full rationale

The derivation chain is self-contained. Theorem 2.3 is proved by an induction (Lemma 2.2) from the powered commutation assumption (5), using matrix products, the positive vector bound, and the Cartier–Foata identity; the conclusion is not equivalent to its own input by construction. The s=1 overlap with Harris et al. (2025) is explicitly acknowledged and not disguised as new. The exact disagreement-repair formulas, the separation example, the k-SAT applications, and the backward likelihood identity are all derived from definitions and standard lemmas rather than fitted to the claimed conclusions. The self-citations (Xu 2026a,b; Li–Xu 2026) appear only as motivation in Section 1 and are not load-bearing anywhere in the proofs. No parameter is fitted to a subset of data and then renamed a prediction, and no uniqueness theorem is imported from the authors' prior work. The possible concern about Corollary 2.4's level-wise coding measure is a mathematical-correctness question, not a circularity question, and in any event does not make the result definitionally equal to its input. Score 1 reflects only the presence of minor, non-load-bearing self-citations; no actual circular step was identified.

Assumptions & free parameters 4 free parameters · 9 assumptions · 0 invented entities

The paper is a self-contained mathematical argument built on standard tools (Perron–Frobenius, Cartier–Foata, Shearer, coding theorems) plus the explicit powered-commutation hypothesis (5). The free parameters listed are construction or optimization choices for examples and cluster bounds, not empirical fits; there are no data-driven constants. No new unobserved entities are introduced.

free parameters (4)
  • m (collision multiplicity) = m≥2, chosen large
    In Corollary 3.2, m controls the m-way action collision; the H-map dimension approaches 1 as m grows. This is an example-construction parameter, not a data fit.
  • t (small source atom) = 0<t<1/2, chosen small
    In Corollary 3.2, π(u)=π(v)=t and q=1/2−t; taking t→0 drives the L-map dimension toward 0.
  • s0 (intermediate source power) = Δ_L < s0 < Δ_H
    Chosen in Corollary 3.2 so the same tape source dominates H below its threshold and gives L an exponential stopping tail.
  • η (cluster expansion parameter) = η=1/(d−1) in Thm 4.3; η=1/(3C) in Cor 4.8
    Hand-optimized to make the local cluster bound (15) contractive; not an empirical fit.
assumptions (9)
  • standard math Perron–Frobenius theorem and strict monotonicity of spectral radius for nonnegative matrices
    Used to define Δ from ρ(B_δ)=1 and to compute exact rates (Prop A.1, Thm 3.1).
  • standard math Cartier–Foata identity for trace monoid generating functions
    Equation (13) converts trace counting to 1/P_D(zλ); the trace bound relies on it.
  • standard math Shearer's theorem / cluster expansion for the independence polynomial
    Used for the open Shearer region and cluster estimates in Theorem 2.3 and Theorem 4.3.
  • standard math Mass-distribution principle and Frostman's lemma
    Converts cylinder bounds P[w]^s into Hausdorff dimension upper and lower bounds (Cor 2.4, Thm 3.1).
  • standard math Kraft–Chaitin / Shannon–Fano coding and Levin–Schnorr for lower semicomputable semimeasures
    Used for effective dimension and the backward coding bound (Thm 5.1, Cor 2.4).
  • standard math Fekete's lemma for subadditive sequences
    Used in Theorem 4.7 to obtain lim N_T^{1/T} = κ.
  • domain assumption Powered commutation condition (5): K_{f,s}K_{g,s}=K_{g,s}K_{f,s} for nonadjacent flaws
    Hypothesis of Theorem 2.3; Lemma 2.1 gives sufficient conditions, but the theorem is not established when it fails.
  • domain assumption Potential-causality locality condition (3): F_{Φ_f(σ,a)} ⊆ (F_σ \ {f}) ∪ Γ(f)
    In local-repair applications this explains why D is the local dependency graph.
  • domain assumption Full-support computable source and ρ_max<1 for effective-dimension conclusions
    Corollary 2.4 and the effective parts of Theorems 3.1/4.7 assume computability and bounded atom probabilities.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Dimension of Nonterminating Resampling Computations." pith.science (2026). https://pith.science/paper/KMPPQBMK

@misc{pith2026260717469,
  author       = {Pith},
  title        = {Pith review of: The Dimension of Nonterminating Resampling Computations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KMPPQBMK}},
  note         = {Machine review of arXiv:2607.17469}
}
abstract

A randomized algorithm may terminate almost surely even though exceptional random tapes make it run forever. This paper studies the survival tail, the Kolmogorov complexity of one such tape, and the Hausdorff dimension of all of them. For each $s>0$ at which the powered repair matrices commute, the main theorem bounds $\sum_wP[w]^s$ over surviving prefixes $w$, uniformly over deterministic nonanticipating selectors. The case $s=1$ controls termination; the full family gives weak-source and dimension bounds. The source powers contain information absent even from the ordinary repair kernel and the complete stopping-time law. Under one common finite tape source, two overlapping disagreement-repair rules on a four-vertex path have the same ordinary kernels and the same stopping-time law for every selector, yet their nontermination dimensions can be arbitrarily close to zero and one. At one common source-power level, the same dominated tape source makes one rule run forever but gives the other an exponential stopping tail. The separation is caused by action labels that produce the same state transition and are therefore invisible at power one. For bounded-dependence $k$-SAT, conditional block min-entropy above the trace-growth threshold gives exponential termination, and the effective dimension of an individual infinite run is bounded by the trace growth induced by the clauses repaired infinitely often. Tree formulas asymptotically attain the maximum-degree dimension and global source bounds, while clique formulas attain the graph-specific one-step threshold in the stated regime. An exact backward likelihood identity complements these setwise results with tail and coding bounds for each run.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

30 extracted references · 17 canonical work pages

  1. [12]

    Mark Jerrum

    doi: 10.1137/1.9781611975031.102. Mark Jerrum. Fundamentals of partial rejection sampling.Probability Surveys, 21:171–199,

    work page doi:10.1137/1.9781611975031.102

  2. [15]

    Vladimir Koltchinskii

    doi: 10.1137/16M1093306. Vladimir Koltchinskii. Local Rademacher complexities and oracle inequalities in risk minimization. The Annals of Statistics, 34(6):2593–2656,

    work page doi:10.1137/16m1093306

  3. [17]

    Shaojie Li and Yunbei Xu

    doi: 10.1007/978-3-030-11298-1. Shaojie Li and Yunbei Xu. Pointwise generalization in deep neural networks. arXiv preprint arXiv:2605.18598,

    arXiv

  4. [22]

    32 Robin A

    doi: 10.1145/1536414.1536462. 32 Robin A. Moser and G´ abor Tardos. A constructive proof of the general Lov´ asz Local Lemma. Journal of the ACM, 57(2):11:1–11:15,

    arXiv

  5. [26]

    Claude E

    doi: 10.1007/ s10955-004-2055-4. Claude E. Shannon. A mathematical theory of communication.The Bell System Technical Journal, 27(3):379–423, July

  6. [28]

    Ludwig Staiger

    doi: 10.1007/s00224-014-9546-8. Ludwig Staiger. Kolmogorov complexity and hausdorff dimension.Information and Computation, 103(2):159–194,

    work page doi:10.1007/s00224-014-9546-8

  7. [30]

    doi: 10.1287/moor.2021.0076. 33

    arXiv 2021

  8. [1948]

    doi: 10.1002/j.1538-7305.1948.tb01338.x. James B. Shearer. On a problem of Spencer.Combinatorica, 5(3):241–245,

    arXiv 1948

Show all 30 references
  1. [1964]

    Wesley Pegden

    doi: 10.1090/S0002-9947-1964-0161372-1. Wesley Pegden. An extension of the moser–tardos algorithmic local lemma.SIAM Journal on Discrete Mathematics, 28(2):911–917,

    1964 doi

  2. [1975]

    Pierre Cartier and Dominique Foata.Probl` emes combinatoires de commutation et r´ earrangements, volume 85 ofLecture Notes in Mathematics

    doi: 10.1007/BFb0081029. Pierre Cartier and Dominique Foata.Probl` emes combinatoires de commutation et r´ earrangements, volume 85 ofLecture Notes in Mathematics. Springer,

    doi

  3. [1986]

    Alexander D

    doi: 10.1016/0022-0000(86) 90044-9. Alexander D. Scott and Alan D. Sokal. The repulsive lattice gas, the independent-set polynomial, and the Lov´ asz Local Lemma.Journal of Statistical Physics, 118:1151–1261,

    doi

  4. [1988]

    Jochen Messner and Thomas Thierauf

    doi: 10.1090/S0002-9947-1988-0961615-4. Jochen Messner and Thomas Thierauf. A Kolmogorov complexity proof of the Lov´ asz Local Lemma for satisfiability.Theoretical Computer Science, 461:55–64,

    1988 doi

  5. [1993]

    Yunbei Xu

    doi: 10.1006/inco.1993.1017. Yunbei Xu. Bellman-sufficient information complexity. arXiv preprint arXiv:2606.11171, 2026a. Yunbei Xu. Pointwise complexity for Gaussian fields: Upper envelopes, algorithmic lower bounds, and separation. arXiv preprint arXiv:2606.07931, 2026b. Yu...

    1993

  6. [2003]

    doi: 10.1016/S0890-5401(03)00187-0. Jack H. Lutz. A divergence formula for randomness and dimension.Theoretical Computer Science, 412(1–2):166–177,

    doi

  7. [2005]

    Patrick Billingsley.Ergodic Theory and Information

    doi: 10.1214/009053605000000282. Patrick Billingsley.Ergodic Theory and Information. John Wiley & Sons,

    doi

  8. [2006]

    Ming Li and Paul M

    doi: 10.1214/009053606000001019. Ming Li and Paul M. B. Vit´ anyi.An Introduction to Kolmogorov Complexity and Its Applications. Springer, Cham, 4 edition,

    doi

  9. [2007]

    doi: 10.1137/S0097539703446912. Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local Rademacher complexities.The Annals of Statistics, 33(4):1497–1537,

    doi

  10. [2009]

    Vladimir Kolmogorov

    doi: 10.1007/s10955-009-9747-8. Vladimir Kolmogorov. Commutativity in the algorithmic lov´ asz local lemma.SIAM Journal on Computing, 47(6):2029–2056,

    doi

  11. [2010]

    William Parry

    doi: 10.1145/1667053.1667060. William Parry. Intrinsic Markov chains.Transactions of the American Mathematical Society, 112: 55–66,

  12. [2011]

    doi: 10.1016/j.tcs.2010.09.005. R. Daniel Mauldin and S. C. Williams. Hausdorff dimension in graph directed construc- tions.Transactions of the American Mathematical Society, 309(2):811–829,

    2010 doi

  13. [2012]

    doi: 10.1016/j.tcs.2012.06.005. Robin A. Moser. A constructive proof of the Lov´ asz Local Lemma. InProceedings of the 41st Annual ACM Symposium on Theory of Computing, pages 343–350,

    2012 doi

  14. [2014]

    Robert M

    doi: 10.1002/9781119942399. Robert M. Fano. The transmission of information. Technical Report 65, Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Massachusetts,

    doi

  15. [2015]

    Krishna B

    doi: 10.1016/j.jcta.2015.05.003. Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo. Effective strong dimension, algorithmic information, and computational complexity.SIAM Journal on Computing, 37(3):671–705,

    2015 doi

  16. [2017]

    doi: 10.1145/3039869. David G. Harris, Fotios Iliopoulos, and Vladimir Kolmogorov. A new notion of commutativity for the algorithmic lov´ asz local lemma.Theory of Computing, 21(5):1–34,

    doi

  17. [2018]

    Endre Cs´ oka, Lukasz Grabowski, Andr´ as M´ ath´ e, Oleg Pikhurko, and Konstantinos Tyros

    doi: 10.1137/16M1105979. Endre Cs´ oka, Lukasz Grabowski, Andr´ as M´ ath´ e, Oleg Pikhurko, and Konstantinos Tyros. Moser– tardos algorithm with small number of random bits,

    doi

  18. [2019]

    Bernhard Haeupler and David G

    doi: 10.1145/3310131. Bernhard Haeupler and David G. Harris. Parallel algorithms and concentration bounds for the Lov´ asz Local Lemma via witness DAGs.ACM Transactions on Algorithms, 13(4):53:1–53:40,

    doi

  19. [2022]

    31 Heng Guo, Mark Jerrum, and Jingcheng Liu

    doi: 10.4171/AIHPD/122. 31 Heng Guo, Mark Jerrum, and Jingcheng Liu. Uniform sampling through the Lov´ asz Local Lemma. Journal of the ACM, 66(3):18:1–18:31,

    doi

  20. [2023]

    Paul Erd˝ os and L´ aszl´ o Lov´ asz

    doi: 10.1145/3564246.3585134. Paul Erd˝ os and L´ aszl´ o Lov´ asz. Problems and results on 3-chromatic hypergraphs and some related questions. In Andr´ as Hajnal, Richard Rado, and Vera T. S´ os, editors,Infinite and Finite Sets, Vol. II, volume 10 ofColloquia Mathematica Soc...

  21. [2024]

    Gerhard Keller and Carlangelo Liverani

    doi: 10.1214/24-PS29. Gerhard Keller and Carlangelo Liverani. Rare events, escape rates and quasistationarity: Some exact formulae.Journal of Statistical Physics, 135(3):519–534,

    doi

  22. [2025]

    2025.v021a005

    doi: 10.4086/toc. 2025.v021a005. Nicholas J. A. Harvey, Piyush Srivastava, and Jan Vondr´ ak. Computing the independence polynomial: From the tree threshold down to the roots. InProceedings of the Twenty-Ninth Annual ACM– SIAM Symposium on Discrete Algorithms, SODA ’18, pages ...

    2025 doi

Pith tools

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