REVIEW 2 major objections 5 minor 10 references
A note on Puder's generalised co-growth formula for trees
T0 review · 2 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read The paper proves a conjecture extending the classical co-growth formula: on a bi-regular tree, the exponential growth rate of weighted walks is exactly determined by the growth rate of weighted non-backtracking walks, in two branches…
desk verdict Terse but sound proof of Puder's bi-regular co-growth conjecture; the missing spectral lower-bound citation is an exposition gap, not a correctness problem. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The bi-resolvent is the central object: for $Z=z_1 I_U+z_2 I_W$, where $I_U$ and $I_W$ project onto the two vertex classes of the bi-regular tree, it is the operator $(Z-A)^{-1}$ on $\ell^2(V)$. On a bi-regular graph one has $Z^{-1}AZ^{-1}=(z_1z_2)^{-1}A$, which splits the resolvent into even and odd powers of $A$ and yields the identity $(Z-A)^{-1}=\sum_{r\ge 0}(z_1z_2)^{-r}A_{2r}Z^{-1}+\sum_{r\ge 0}(z_1z_2)^{-(r+1)}A_{2r+1}$. Comparing this with the generating function for the non-backtracking walk matrices, derived from the recurrence $A_r A=A_{r+1}+A_{r-1}(D-I)$, gives equation (7), the operator-level co-growth formula. The convergence radius $(k-1)^{1/4}(l-1)^{1/4}$ comes from the spectral radius of the Hashimoto non-backtracking operator on the tree.
What would settle it
Choose a non-zero non-negative function $f$ on a $(k,l)$-bi-regular tree with $\alpha(f)\le (k-1)^{1/4}(l-1)^{1/4}$ and compute $\beta(f)$ numerically from weighted walk counts; the theorem predicts $\beta(f)=\sqrt{k-1}+\sqrt{l-1}$, so any computed example with $\beta(f)$ above this constant refutes the formula.
Extended reading notes
Core claim
Theorem 1.2 states the generalized co-growth formula for all non-negative functions on a $(k,l)$-bi-regular tree: if $\alpha(f)\le (k-1)^{1/4}(l-1)^{1/4}$, then $\beta(f)=\sqrt{k-1}+\sqrt{l-1}$, and if $\alpha(f)\ge (k-1)^{1/4}(l-1)^{1/4}$, then $\beta(f)=\sqrt{(\alpha(f)+(k-1)/\alpha(f))(\alpha(f)+(l-1)/\alpha(f))}$. The proof obtains this by way of the bi-resolvent identity, an operator-level equality relating powers of the adjacency matrix to the non-backtracking walk matrices; after pairing this identity with the monotone convergence of finitely supported truncations of $f$, the two inequalities $\beta(f)\le\dots$ and $\beta(f)\ge\dots$ follow from the convergence radii of the two generating functions. The lower bound uses the fact that any non-zero non-negative $f$ grows at least as fast as a point mass, and closed-walk growth from a vertex attains the operator norm $\sqrt{k-1}+\sqrt{l-1}$.
Load-bearing premise
The proof assumes that the spectral radius of the non-backtracking operator on the bi-regular tree is exactly $(k-1)^{1/4}(l-1)^{1/4}$ and that the adjacency operator norm is $\sqrt{k-1}+\sqrt{l-1}$; if either constant is wrong, the resolvent convergence and the lower bound $\beta(f)\ge\sqrt{k-1}+\sqrt{l-1}$ would collapse.
Editorial extensions
If this is right
- The same two-branch formula holds for every bi-regular graph, finite or infinite, by lifting $f$ to the universal covering tree.
- Weighted walk growth is now exactly computable from non-backtracking growth for arbitrary non-negative functions, not just vertex-indicator functions.
- At the threshold the two branches agree: setting $\alpha(f)=(k-1)^{1/4}(l-1)^{1/4}$ makes the second branch equal to $\sqrt{k-1}+\sqrt{l-1}$, so the formula is continuous in $\alpha(f)$.
- For the $d$-regular tree the same resolvent method gives a shorter proof of the existing generalized co-growth formula for all non-negative functions.
Reading between the lines
- A testable extension is to use the same bi-resolvent identity on finite bipartite graphs, where the operator identity holds formally and numerical values of $\alpha(f)$ and $\beta(f)$ can be compared with the predicted two-branch law as graph size grows.
- An implicit consequence is that the threshold $(k-1)^{1/4}(l-1)^{1/4}$ is the natural location for any analogue of the staircase spectral-outlier transition observed for random regular graphs; the paper notes this as a possible next step for random bi-regular graphs.
- The proof's separation of even and odd walks through the bi-resolvent suggests that parity-sensitive co-growth questions on bipartite trees can be treated by the same operator identity.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves Puder's conjecture that the generalized co-growth formula, previously known for indicator functions on bi-regular trees, holds for every non-negative function. The proof introduces a 'bi-resolvent' identity (Lemma 3.1) relating a two-variable resolvent of the adjacency operator to the non-backtracking walk matrices. After deriving a generating-function identity (equation (7)) and applying monotone convergence and standard power-series arguments, the authors obtain both branches of the formula. A simplified proof for the regular tree is also given.
Significance. The result settles a stated conjecture of Puder and gives a clean operator-theoretic proof that extends the classical co-growth formula. The bi-resolvent identity is a new tool that may be useful for other problems on bi-regular graphs, and the theorem has potential implications for outlier behavior in random bi-regular graphs (à la Chen–Garza-Vargas–Tropp–van Handel). The proof is self-contained up to standard spectral facts about trees, and the argument is transparent with no fitted parameters. The regular-tree part also provides a pedagogically simpler proof.
major comments (2)
- [§3, proof of Theorem 1.2, final lower bound] The assertion that lim sup_{r→∞} b_r(δ_e)^{1/r} = ||A|| = √(dU−1) + √(dW−1) is used as the lower-bound step for the α ≤ threshold branch, but it is neither proved nor referenced. This equality is a standard spectral fact for the (dU,dW)-bi-regular tree, but because it is load-bearing the authors should either prove it (for example from the two-type Green function recursion) or cite a source.
- [§3, proof of Theorem 1.2, upper-bound case] The upper-bound argument is written only for the case α(f) = ρ0 ≥ threshold. Since Theorem 1.2 also states the first branch for α(f) < threshold, the proof should either observe that α(f) ≥ threshold for every non-zero non-negative f (so the first branch reduces to equality), or apply the same inequality with arbitrary ρ > threshold and let ρ ↓ threshold. As written, the case α(f) < threshold is not covered.
minor comments (5)
- [§3, Lemma 3.2] The symbol B is used both for the Hashimoto operator and for the ball B(v,r); this is a potential source of confusion and the authors may wish to rename one of them.
- [§3, Lemma 3.2] After displaying the exact count of vertices at distance r from v, the paper only states an upper bound; it would be clearer to point out that the r-th root of the exact displayed expression already tends to τ = (dU−1)^{1/4}(dW−1)^{1/4}, so the equality in (6) is immediate.
- [Abstract] The abstract contains a typo: 'th e co-growth' should read 'the co-growth'.
- [§3, proof of Theorem 1.2] The sentence 'by an identical argument to the end of the proof of Theorem 1.1' should be accompanied by a cross-reference to the equality in the regular case, since the bi-regular case needs the analogous spectral-radius statement.
- [§3, proof of Theorem 1.2] The converse step (from β = F(ρ0) to α ≤ ρ0) is correct, but the paper does not spell out how the upper bound, lower bound, and converse combine to yield equality in both branches; a short explanatory sentence would improve readability.
Circularity Check
No circularity: the proof derives the resolvent identity and co-growth formula from independent operator-theoretic facts; the only gap is an unproved standard spectral equality in the lower-bound step.
full rationale
The paper's target is Puder's generalized co-growth formula for bi-regular trees (Theorem 1.2). The derivation chain is: (i) Lemma 3.1 proves the bi-resolvent expansion (4) from the algebraic identity Z^{-1}AZ^{-1}=(z1 z2)^{-1}A; (ii) Lemma 3.2 derives the recurrence for non-backtracking walk matrices and the generating function identity (5), using [1, Theorem 4.2] only to bound the spectral radius of the Hashimoto operator B, an external result that is independent of the target formula; (iii) comparing (4) and (5) yields the operator identity (7); (iv) finite-support truncations and monotone convergence turn (7) into the scalar identity (8); (v) limsup arguments convert (8) into the two branches of Theorem 1.2. Nothing is fitted, and neither Puder's conjecture nor Theorem 1.2 is assumed at any step. The cited results [1,6,8,10] supply contextual or standard operator-theoretic inputs, not the target conclusion. One exposition gap appears in the final lower-bound step: the paper asserts, 'by an identical argument to the end of the proof of Theorem 1.1', that limsup(r) br(delta_e)^{1/r} = ||A|| = sqrt(dU-1)+sqrt(dW-1). This equality is load-bearing for the first branch, but it is a standard independent spectral fact about the bi-regular tree (the support of the two-type Green function extends to the spectral radius), not a consequence of the paper's own construction and not derived from the theorem being proved. Supplying the short Green-function proof would remove the gap, but the omission is an unproved standard fact, not circularity. No equation in the paper reduces to its inputs by construction, and no parameter is fitted and then renamed a prediction.
Assumptions & free parameters
assumptions (4)
- standard math The spectral radius of the non-backtracking operator B on the directed-edge graph of a (dU,dW)-bi-regular tree equals (dU minus 1)^(1/4) times (dW minus 1)^(1/4)
- standard math The adjacency operator A on a (dU,dW)-bi-regular tree has norm sqrt(dU minus 1) plus sqrt(dW minus 1)
- standard math For an origin e in the tree, the closed-walk growth rate limsup of the inner product of delta_e with A^r delta_e to the power 1/r equals the norm of A
- standard math Monotone convergence can be applied termwise to the generating-function identities despite possibly infinite sums
Cite this review
Pith. "Pith review of A note on Puder's generalised co-growth formula for trees." pith.science (2026). https://pith.science/paper/LM7B7R3V
@misc{pith2026250206372,
author = {Pith},
title = {Pith review of: A note on Puder's generalised co-growth formula for trees},
year = {2026},
howpublished = {\url{https://pith.science/paper/LM7B7R3V}},
note = {Machine review of arXiv:2502.06372}
}
read the original abstract
In this note, we prove a conjecture of Puder on an extension of the co-growth formula to any non-negative function defined on a bi-regular tree. A key component of our proof is the establishment of a resolvent identity, which serves as an operator version of the co-growth formula. We also provide a simpler proof of Puder's generalised co-growth formula for the regular tree.
Reference graph
Works this paper leans on
-
[1]
Angel, O., Friedman, J., Hoory, S., The non-backtracking spectrum of the universal cover of a graph, Transactions of the American Mathematical Society, 367, no . (6), pp. 4287–4318, 2015
work page 2015
-
[2]
Brito G., Dumitriu I., Harris K.D., Spectral gap in random bipartite biregular graphs and applications, Combinatorics, Probability and Computing, 31(2), pp.229- 267, 2022
work page 2022
-
[3]
Cohen, J.M., Cogrowth and amenability of discrete groups, Journal of Functional Analysis, 48(3), pp.301-309, 1982
work page 1982
-
[4]
Davidoff, G. P., Sarnak, P. and Valette, A., Elementary number theory, group theory, and Ramanujan graphs, Vol. 55, No. 1. Cambridge: Cambridge University Press, 2003
work page 2003
-
[5]
and van Handel , R., A new approach to strong convergence, preprint, arXiv:2405.16026
Chen, C.F., Garza-Vargas, J., Tropp, J.A. and van Handel , R., A new approach to strong convergence, preprint, arXiv:2405.16026. 9
-
[6]
Grigorchuk, R.I., Symmetric random walks on discrete groups, Uspekhi Matematich- eskikh Nauk, 32(6), pp. 217-218, 1977
work page 1977
-
[7]
Kempton, M., Non-Backtracking Random Walks and a Weighted Ihara’s Theorem , Open Journal of Discrete Mathematics, 6, pp.207-226, 2016
work page 2016
-
[8]
and Peres, Y., Probability on trees and networks, Vol
Lyons, R. and Peres, Y., Probability on trees and networks, Vol. 42, Cambridge University Press, 2017
work page 2017
Show all 10 references
-
[9]
Northshield, S., Cogrowth of regular graphs, Proceedings of the American Mathemat- ical Society, 116(1), pp.203-205, 1992
1992
-
[10]
Puder, D., An extension of the co-growth formula to arbitrary subsets o f the tree, preprint, arXiv:2405.18169v2. Wenbo Li School of Mathematical Sciences, University of Science and Technology of China, No.96 Jinzhai Road, Hefei, China patlee@mail.ustc.edu.cn Joe Thomas Depart...
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.