Arithmetic of weighted Catalan numbers

Andrew Gu; Yibo Gao

REVIEW 3 major objections 6 minor 10 references

Arithmetic of weighted Catalan numbers

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read The paper proves a weaker sufficient condition under which weighted Catalan numbers have exactly the same 2-adic valuations as ordinary Catalan numbers, and it extends the method to prime-power q-Catalan numbers and periodicity of…

desk verdict Genuinely relaxes Postnikov-Sagan's 2-adic divisibility conditions and resolves Postnikov's Morse link periodicity conjectures; the core combinatorial argument is solid, with two proof sketches that a referee should ask to be expanded. read the letter →

arxiv 1908.03914 v1 pith:64YSQCG4 submitted 2019-08-11 math.CO math.NT

Yibo Gao , Andrew Gu This is my paper · ORCID

classification math.COmath.NT MSC 05A1505A1905C0511A0711B5011B65

keywords weightedCatalannumbers2-adicvaluationfinitedifferencesbinarytreessymmetryorbitsq-CatalanperiodicitymodulomMorselinks

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

This paper finds a weaker condition on the weight function $b$ under which every weighted Catalan number $C_n^b$ is divisible by exactly the same power of 2 as the ordinary Catalan number $C_n$. The condition asks that $b(0)$ be odd, that $\Delta b(x)$ be divisible by 4 for every $x$, and that $\Delta^n b(x)$ be divisible by $2^n$ for $n \ge 2$; this weakens the earlier condition of Postnikov and Sagan, which required $2^{n+1}$ to divide the $n$-th difference. The proof encodes the residues of finite differences modulo powers of 2 into a parity sequence and tracks it over orbits of binary trees. The method extends to $q$-ary trees when $q$ is a prime power, and separately the paper characterizes when weighted Catalan numbers are eventually periodic modulo any integer, applying that to Morse link numbers.

What carries the argument

The central object is the parity map $\varepsilon$ on the class $\mathcal{F}$ of functions whose $n$-th finite differences are divisible by $2^n$. For $f\in\mathcal{F}$, the residue of $\Delta^n f$ modulo $2^{n+1}$ is either $0$ or $2^n$, and $\varepsilon_n(f)$ records which one occurs. For each orbit $O$ of binary trees under the symmetry group that exchanges left and right subtrees, the average weight function $r_b(O;x)=w_b(O;x)/|O|$ lies in $\mathcal{F}$, and $\varepsilon_0^O$ determines whether the orbit contributes an odd total weight. The explicit coin-configuration formula for $\varepsilon_m^O$ expresses it as a sum over configurations of coins placed at vertices with no sibling edges selected, and the reduction lemma factors out powers of $\varepsilon_0$ when complete binary subtrees are compressed to single vertices. Together with the structure theorem for minimal orbits, this machinery reduces the main theorem to a parity count on a smaller set of orbits.

What would settle it

Take $b(x)=4x+1$, which satisfies the hypotheses, and compute $\xi_2(C_n^b)$ by enumerating all Dyck paths of semilength $n$; for $n=10$ the theorem predicts $\xi_2(C_{10}^b)=s_2(11)-1=2$, so any other valuation refutes the central claim. Alternatively, enumerate the symmetry orbits of binary trees on a small $n$ and check that every orbit has size at least $2^{s_2(n+1)-1}$ and that the minimal orbits have exactly the predicted attaching structure.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 2.1: if $b:\mathbb{Z}_{\ge 0}\to\mathbb{Z}$ has $b(0)$ odd, $4\mid\Delta b(x)$ for all $x$, and $2^n\mid\Delta^n b(x)$ for all $n\ge 2$ and $x$, then $\xi_2(C_n^b)=\xi_2(C_n)=s_2(n+1)-1$ for every $n$. The proof computes $C_n^b$ modulo $2^{s+1}$, where $s=s_2(n+1)-1$, by grouping binary trees into symmetry orbits. Each orbit contributes a power of two times an average weight function, and those average functions live in a class closed under the operations used. A parity map detects which average weights are odd, and a coin-configuration formula describes the parity sequence of each orbit. A reduction lemma shows that replacing a complete binary subtree by a single vertex only multiplies the parity sequence by a fixed power of $\varepsilon_0$, so the parity count on minimal orbits reduces to small base cases. Along the way, the authors note a sharper parity fact: if only $2\mid\Delta b$ is assumed, the equality with $\xi_2(C_n)$ still holds for odd $n$, while even $n$ have strictly larger valuation when $4\nmid\Delta b$.

Load-bearing premise

The proof depends on the structural fact that symmetry orbits on binary trees with $n$ vertices have size at least $2^{s_2(n+1)-1}$ and that the smallest orbits are exactly the trees obtained by attaching complete binary trees with depths from the binary expansion of $n+1$ to an arbitrary smaller tree; if this structural fact failed, the parity count could break even though the hypotheses on the weight function still hold.

Editorial extensions

If this is right

For any weight function satisfying the three divisibility hypotheses of Theorem 2.1, $\xi_2(C_n^b)=s_2(n+1)-1$ exactly, so the 2-adic valuation of the weighted Catalan number is pinned down.
If $b(0)$ is odd but only $2\mid\Delta b$ is assumed, equality with $\xi_2(C_n)$ still holds for odd $n$, while for even $n$ the valuation is strictly larger exactly when $4\nmid\Delta b$.
For a prime power $q=p^k$, under the analogous hypotheses $b(0)\equiv 1\pmod q$, $q^2\mid\Delta b$, and $q^n\mid\Delta^n b$, the weighted $q$-Catalan numbers are congruent to the unweighted ones modulo $p^{\xi+k}$, with $\xi=(s_p((q-1)n+1)-1)/(p-1)$.
The sequence $\{C_n^b \bmod m\}$ is eventually periodic if and only if $m$ divides $b(0)b(1)\cdots b(k)$ for some positive integer $k$.
For Morse link numbers $L_n$, which are weighted Catalan numbers with $b(x)=(2x+1)^2$, the period modulo 7 is 12, modulo 11 is 55, and for $r\ge 3$ the period modulo $3^r$ divides $2\cdot 3^{r-3}$.

Reading between the lines

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

Because the $\varepsilon$ map records residues of finite differences modulo powers of 2, it should also measure the failure $\xi_2(C_n^b)-\xi_2(C_n)$ when the hypotheses fail, not merely detect parity; a natural next step is to express that defect as a coin-configuration sum.
The same orbit-reduction method likely yields a combinatorial proof of Conjecture 2.14, replacing the computational criterion for polynomial weight functions with a structural tree argument.
For Morse links, the period bound of Theorem 4.8 narrows the verification of Postnikov's conjectured exact period $2\cdot 3^{r-3}$ to checking that the two exceptional path classes do not cancel in the sum; a reader could test this numerically for small $r$.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Jake,

The paper is a genuine advance in the arithmetic of weighted Catalan numbers. The main theorem relaxes Postnikov-Sagan's divisibility hypotheses: instead of 2^{n+1} | Δ^n b, they need 2^n | Δ^n b for n≥2, keeping 4 | Δb. The proof via the epsilon map and coin configurations is clever and, as far as I can tell, correct. I also like the clean iff criterion for eventual periodicity modulo m (Theorem 4.2) and the Morse link period computations; those settle two of Postnikov's conjectures.

What is actually new: the epsilon invariant and the coin-configuration description of orbit reduction; Theorem 2.1; Theorem 4.2; the computations mod 7 and 11; and Theorem 4.8 bounding the period mod 3^r.

The soft spots are where the authors summarize instead of prove. Theorem 3.1 (the q-analog) is explicitly a sketch—"proof is similar"—and the details given are enough to convince me but not enough to verify line-by-line. Theorem 4.8 ends with a finite check left to the reader; the remaining cases are small, but a referee should ask for the table. The proof of Theorem 2.1 also leans on Theorem 2.5, the orbit-structure classification, which is cited from Konvalinka rather than proved here. The stress-test worry about that is real but not fatal: the uniqueness of the coloring is argued (children vs leaves), and the existence follows from the minimal-orbit property that leaves outnumber internal nodes by 0 or 1. I'd still like to see the "direct verification" expanded, because the parity reduction collapses if that part is wrong. It isn't, as far as I can tell.

For a reader in enumerative combinatorics, this is worth a careful reading. It deserves a serious referee; I'd send it out with minor-revision comments asking to expand the two sketched proofs and the finite check.

Referee Report

3 major / 6 minor

Summary. The paper studies arithmetic properties of weighted Catalan numbers C_n^b, which are sums over Dyck paths of products of weights b(height of an up-step). The main result (Theorem 2.1) replaces Postnikov and Sagan's sufficient condition 2^{n+1} | (Δ^n b)(x) for equality of 2-adic valuations by the weaker condition 2^n | (Δ^n b)(x) for all n ≥ 2 together with 4 | (Δ b)(x) and b(0) odd, proving ξ_2(C_n^b) = ξ_2(C_n) = s_2(n+1)-1. The proof introduces a map ε from a class of functions F with derivative divisibility conditions to binary sequences, analyzes parity of average weight functions on symmetry orbits of binary trees, and reduces the desired parity to a smaller case using the structure of minimal orbits. Section 3 states a generalization to q-ary trees and prime powers q (Theorem 3.1). Section 4 characterizes eventual periodicity of C_n^b modulo m (Theorem 4.2) and applies the results to Postnikov's conjectures on Morse link numbers, computing periods modulo 7 and 11 and showing that the period modulo 3^r divides 2·3^{r-3}.

Significance. If the proofs are completed, Theorem 2.1 is a genuine weakening of the known sufficient condition for the 2-adic valuation of weighted Catalan numbers to equal the classical Catalan valuation, and the ε-map is an elegant new tool for tracking parities of orbit averages. The periodicity theorem is a clean and complete characterization, and the applications to Morse link numbers explicitly resolve or partially resolve concrete conjectures of Postnikov. The paper is honest about open conjectures and includes helpful worked examples and tables. However, the manuscript is not fully self-contained: the central reduction in Theorem 2.1 relies on an unproved external orbit-structure theorem, Theorem 3.1 is only sketched, and Theorem 4.8 leaves a finite check to the reader. These gaps are fixable but currently limit verification.

major comments (3)

[Section 2.3 (proof of Theorem 2.1)] The reduction step in the proof of Theorem 2.1 is load-bearing and rests on Theorem 2.5, which is not proved in the paper and is cited only by the phrase 'This was done more generally for q-ary trees by Konvalinka [6].' In particular, the assertion that after reduction the white vertices are exactly the leaves and the black vertices are exactly the internal vertices, and that this gives a unique expansion of a minimal orbit on k vertices to a minimal orbit on n vertices, is used essentially to justify the congruence Σ_{O∈U_min^n} ε_0^O ≡ ε_0^{n-k} Σ_{O∈U_min^k} ε_0^O (mod 2). The 'Furthermore' reversal half of Theorem 2.5 (white iff the two child subtrees are isomorphic) is needed for this uniqueness/existence argument. Please provide a proof of Theorem 2.5, or a precise citation of the exact statement in the literature, and include a proof of the reversal property.
[Section 3 (Theorem 3.1)] Theorem 3.1 is advertised as a strengthening of Konvalinka's result, but its proof is only a sketch. After Lemma 3.5 the text says 'The proof of Theorem 3.1 is quite similar to the proof of Theorem 2.1 from here' and omits the q-analog of Theorem 2.5, the reduction-counting formula analogous to f(O) = s!M/2^s, the parity determination modulo q, the uniqueness/existence argument for expanding a minimal q-ary orbit, and the verification of the base cases n ≤ q. These are not routine details because the parity reduction must now be performed modulo q rather than modulo 2. Please supply a complete proof or a precise statement of the relevant q-analog results with full references.
[Section 4 (proof of Theorem 4.8)] The proof of Theorem 4.8 leaves the phrase 'further verification of the finitely many remaining cases leaves the following pairs' without showing the actual finite check, and it eliminates the case (a,b) = (4,0) for semilength at least 2 by assertion. In addition, Lemma 4.10 is applied to the sequence f(n) with generating function x^{cβ}/((1-x)^a(1+x)^b), but Lemma 4.10 as stated assumes a linear recurrence with initial conditions a_1=⋯=a_{k-1}=0, a_k=1; the reduction of the shifted sequence f(cβ+n) to this form is not shown. Please provide the omitted finite verification and spell out the reduction to Lemma 4.10.

minor comments (6)

[Section 4.1 (proof of Theorem 4.2)] In the 'if' direction of the proof, 'suppose that n | b(0)···b(k)' should be 'm | b(0)···b(k)'.
[Section 3 (Theorem 3.1 statement)] The statement contains an extra closing parenthesis: 'C_n^{(q)}(b))' should be 'C_n^{(q)}(b)'.
[Lemma 2.3] The expression (2s-1)!! is used for s=0; please state the convention (-1)!!=1.
[End of proof of Theorem 2.1] The claimed stronger result under the weaker condition 2 | Δb is stated without proof; please add a sentence explaining how the same induction verifies the base cases n=1 and n=2 in that case.
[Section 4.2 (proof of Theorem 4.8)] The sentence 'This implies with this generating function may be written as' is garbled; it should read something like 'This implies that the generating function may be written as'.
[Lemma 4.10] Lemma 4.10 is cited to an unpublished preprint [2]; please provide a proof or a published reference.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main theorem is proved from its hypotheses by a parity argument whose structural inputs are external, not self-referential.

full rationale

The paper contains no step in which a conclusion is assumed in the definition of an input, no fitted parameter is renamed as a prediction, and no load-bearing argument reduces to a self-citation. The epsilon map is defined from the same finite-difference divisibility conditions appearing in the hypotheses, but it is used as a bookkeeping device to track parities of average weight functions; the proof never assumes the target valuation equality. The reduction in Section 2.3 derives the parity of the sum of epsilon_0 over minimal orbits from the structure theorem for minimal orbits (Theorem 2.5), which is cited from Konvalinka [6], an external source whose stated assumptions do not include the valuation conclusion. Lemma 2.3 is likewise cited from Deutsch-Sagan [3]. These are independent combinatorial facts, not self-citations, and the parity induction is carried out explicitly with base cases n=1,2. No circularity is present.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters are fitted or chosen by hand; the theorem hypotheses are fixed assumptions. The paper relies on several external standard results: the continued fraction generating function, orbit size and structure theorems for binary trees, Lucas's theorem, and period lifting for linear recurrences. No new entities are introduced.

assumptions (6)

standard math Weighted Catalan numbers have the continued fraction generating function given in Proposition 1.2.
Invoked throughout Sections 2 and 4; cited to Goulden-Jackson [5], not reproved.
standard math Every orbit of the symmetry group on binary trees on n vertices has size 2^t for t >= s_2(n+1)-1, with equality for (2^s-1)!! orbits (Lemma 2.3).
External result from Deutsch-Sagan [3]; foundation of the reduction count in Theorem 2.1.
standard math Minimal orbits are parameterized by an arbitrary binary tree with s vertices with complete binary trees of depths given by the binary expansion of n+1 attached to endpoints (Theorem 2.5).
Attributed to Konvalinka [6]; used in the reduction step to identify which reduced orbits survive modulo 2.
standard math The analogous orbit-size and minimal-orbit structure holds for q-ary trees when q is a prime power.
Used in the proof of Theorem 3.1, which is only sketched.
standard math The period of a linear recurrence modulo p^r divides p^(r-1) times its period modulo p (Lemma 4.10).
Quoted from Bright [2] and used in Theorem 4.8 to lift period bounds from modulo 3 to modulo 3^r.
standard math Lucas's theorem on binomial coefficients modulo p, used in Lemma 4.9.
Standard number theory result; used to bound periods of binomial coefficient sequences modulo primes.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Arithmetic of weighted Catalan numbers." pith.science (2026). https://pith.science/paper/64YSQCG4

@misc{pith2026190803914,
  author       = {Pith},
  title        = {Pith review of: Arithmetic of weighted Catalan numbers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/64YSQCG4}},
  note         = {Machine review of arXiv:1908.03914}
}

abstract

In this paper, we study arithmetic properties of weighted Catalan numbers. Previously, Postnikov and Sagan found conditions under which the $2$-adic valuations of the weighted Catalan numbers are equal to the $2$-adic valutations of the Catalan numbers. We obtain the same result under weaker conditions by considering a map from a class of functions to $2$-adic integers. These methods are also extended to $q$-weighted Catalan numbers, strengthening a previous result by Konvalinka. Finally, we prove some results on the periodicity of weighted Catalan numbers modulo an integer and apply them to the specific case of the number of combinatorial types of Morse links. Many open questions are mentioned.

Figures

Figures reproduced from arXiv: 1908.03914 by the authors.

**Figure 2.** An example for n = 54, n + 1 = 25 + 24 + 22 + 21 + 20 . Furthermore, this mapping can be reversed in the following way: for every vertex, color it white if the left and right subtrees at that vertex are isomorphic, and otherwise color it black. The black vertices are the original s vertices and all white vertices are part of complete binary trees. The symmetries of such trees are generated precisely by reflections a… view at source ↗

**Figure 3.** An example of a coin-configuration of order 9 with weight (ε0) 2 (ε1)(ε2) 4 (ε3). Proposition 2.13. We have the following explicit formula for an orbit O: ε O m = X C∈COm wt(C) where the sum is over all coin-configurations C on O of order m. Proof. The proposition is a direct consequence of Lemma 2.10 and induction on the number of vertices of O. For the base case where O is a single vertex, by definition, ε O m equ… view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: The example tree from [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]

**Figure 5.** Figure 5: A Dyck path for n = 7, and its 3-power path. The white vertices are marked because P stays within the gray region. write Ln = X P wt(P) = X β X P:α(P)=β wt(P) where the first sum is over all Dyck paths P of semilength n, the second sum is over all 3-power paths β, and …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

[6]

Divisibility of generalized Catal an numbers

Matjaˇ z Konvalinka. Divisibility of generalized Catal an numbers. J. Combin. Theory Ser. A , 114(6):1089–1100, 2007

work page 2007
[1]

Combinatorial enumeration of weighted Catalan numbers

Junkyu An. Combinatorial enumeration of weighted Catalan numbers . PhD thesis, Massachusetts In- stitute of Technology, 2010

work page 2010
[2]

Modular periodicity of linear recurrenc e sequences

Curtis Bright. Modular periodicity of linear recurrenc e sequences. preprint, 2008. available at https://cs.uwaterloo.ca/~cbright/reports/PM434Project.pdf

work page 2008
[3]

Emeric Deutsch and Bruce E. Sagan. Congruences for Catal an and Motzkin numbers and related sequences. J. Number Theory , 117(1):191–215, 2006

work page 2006
[4]

History of the theory of numbers

Leonard Eugene Dickson. History of the theory of numbers. Vol. I: Divisibility and pr imality. Chelsea Publishing Co., New York, 1966

work page 1966
[5]

Goulden and David M

Ian P. Goulden and David M. Jackson. Combinatorial enumeration. Dover Publications, Inc., Mineola, NY, 2004. With a foreword by Gian-Carlo Rota, Reprint of the 1 983 original. ARITHMETIC OF WEIGHTED CATALAN NUMBERS 27

work page 2004
[7]

R. G. E. Pinch. Recurrent sequences modulo prime powers. In Cryptography and coding, III (Cirences- ter, 1991) , volume 45 of Inst. Math. Appl. Conf. Ser. New Ser. , pages 297–310. Oxford Univ. Press, New York, 1993

work page 1991
[8]

Counting morse curves and links

Alexander Postnikov. Counting morse curves and links. preprint, 2010. available at https://math.mit.edu/~apost/papers/morse-brief.pdf

work page 2010

Show all 10 references

[9]

Alexander Postnikov and Bruce E. Sagan. What power of two divides a weighted Catalan number? J. Combin. Theory Ser. A , 114(5):970–977, 2007

2007
[10]

Richard P. Stanley. Catalan numbers . Cambridge University Press, New York, 2015. Department of Mathematics, Massachusetts Institute of Tec hnology, Cambridge, MA 02139 E-mail address : gaoyibo@mit.edu Department of Mathematics, Massachusetts Institute of Tec hnology, Cambridg...

2015

Pith tools

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

[1] [6]

Divisibility of generalized Catal an numbers

Matjaˇ z Konvalinka. Divisibility of generalized Catal an numbers. J. Combin. Theory Ser. A , 114(6):1089–1100, 2007

work page 2007

[2] [1]

Combinatorial enumeration of weighted Catalan numbers

Junkyu An. Combinatorial enumeration of weighted Catalan numbers . PhD thesis, Massachusetts In- stitute of Technology, 2010

work page 2010

[3] [2]

Modular periodicity of linear recurrenc e sequences

Curtis Bright. Modular periodicity of linear recurrenc e sequences. preprint, 2008. available at https://cs.uwaterloo.ca/~cbright/reports/PM434Project.pdf

work page 2008

[4] [3]

Emeric Deutsch and Bruce E. Sagan. Congruences for Catal an and Motzkin numbers and related sequences. J. Number Theory , 117(1):191–215, 2006

work page 2006

[5] [4]

History of the theory of numbers

Leonard Eugene Dickson. History of the theory of numbers. Vol. I: Divisibility and pr imality. Chelsea Publishing Co., New York, 1966

work page 1966

[6] [5]

Goulden and David M

Ian P. Goulden and David M. Jackson. Combinatorial enumeration. Dover Publications, Inc., Mineola, NY, 2004. With a foreword by Gian-Carlo Rota, Reprint of the 1 983 original. ARITHMETIC OF WEIGHTED CATALAN NUMBERS 27

work page 2004

[7] [7]

R. G. E. Pinch. Recurrent sequences modulo prime powers. In Cryptography and coding, III (Cirences- ter, 1991) , volume 45 of Inst. Math. Appl. Conf. Ser. New Ser. , pages 297–310. Oxford Univ. Press, New York, 1993

work page 1991

[8] [8]

Counting morse curves and links

Alexander Postnikov. Counting morse curves and links. preprint, 2010. available at https://math.mit.edu/~apost/papers/morse-brief.pdf

work page 2010