pith. machine review for the scientific record. sign in

arxiv: 2605.12821 · v1 · submitted 2026-05-12 · 🧮 math.CO

Recognition: unknown

The Distribution of the Deepest Leaves in Binary Trees

Olivier Bodini , Antoine Genitrini , Khaydar Nurligareev
Authors on Pith no claims yet

Pith reviewed 2026-05-14 19:26 UTC · model grok-4.3

classification 🧮 math.CO
keywords plane binary treesdeepest leaveslimiting distributionCatalan iterationsingularity analysisAbel equationFatou coordinateexponential tail
0
0 comments X

The pith

In random plane binary trees, the number of leaves at maximum depth has a limiting distribution with probability of exactly 2m such leaves asymptotically equal to 4^{-m+1}.

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

The paper determines the distribution of leaves at the greatest depth in large random plane binary trees. It begins by solving for the probability of exactly two deepest leaves and the expected number at that level using generating functions tied to the Catalan iteration. These functions are shown to have square-root singularities at z=1/4 through analysis of truncation errors. The work then derives the full distribution by reducing a hierarchy of differential equations to a functional equation via the Fatou coordinate of an Abel equation. This yields an exponential tail for the probabilities, with numerical values confirming an average near 2.8 and a 70 percent chance of exactly two deepest leaves.

Core claim

The central result is that the probability κ[m] of having exactly 2m deepest leaves satisfies κ[m] ∼ 4^{-m+1}. This follows from encoding the parameters into a bivariate generating function that satisfies the Catalan recurrence, then using continuous iteration theory and the Fatou coordinate to characterize the distribution, combined with singularity analysis to extract the exponential decay.

What carries the argument

The Catalan iteration I_{k+1}(z)=1 + z I_k(z)^2 together with the Fatou coordinate of the associated Abel equation, which converts the nonlinear recurrence into a functional equation for the limiting distribution.

If this is right

  • The mean number of deepest leaves approaches approximately 2.8037.
  • The probability of exactly two deepest leaves approaches approximately 0.7009.
  • All generating functions involved admit square-root singular expansions at the dominant singularity ρ=1/4.
  • The distribution is fully characterized by a functional equation obtained from continuous iteration theory.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same techniques could extend to counting deepest leaves in other combinatorial structures that satisfy similar quadratic recurrences.
  • Knowing this distribution allows precise analysis of algorithms that depend on tree height or deepest levels, such as certain search or balancing procedures.
  • Further numerical solutions of the functional equation could yield exact closed forms or higher moments for the number of deepest leaves.

Load-bearing premise

The truncation error in the critical scaling regime of the Catalan iteration admits a three-zone dominated-convergence analysis producing clean square-root singular expansions for the generating functions.

What would settle it

Simulate millions of large random binary trees and measure the empirical frequency of trees with 2m=20 deepest leaves; it should be close to 4^{-9} if the asymptotic holds.

read the original abstract

We study the extreme local structure of plane binary trees through the distribution of leaves at maximum depth. We first address two basic questions: (i) the asymptotic probability that exactly two leaves occur at the deepest level, and (ii) the asymptotic mean number of leaves at that level. These problems lead to generating functions coupled with the Catalan iteration $I_{k+1}(z)=1+zI_k(z)^2$ through quasi-logistic recurrences. We show that both associated series have dominant singularity $\rho=1/4$ and admit square-root singular expansions. The singular terms are obtained through a three-zone dominated-convergence analysis of the critical scaling regime of the truncation error. We then extend the framework to derive the full limiting distribution of the number of deepest leaves. Enumerating trees with exactly $2m$ deepest leaves yields a hierarchy of differential equations that reduces to successive polynomial integrations. Encoding these parameters into a bivariate generating function transforms the nonlinear dynamics back into the Catalan recurrence. Using continuous iteration theory and the Fatou coordinate associated with an Abel equation, we obtain a functional equation characterizing the distribution. Finally, singularity analysis implies a strict exponential tail: the probability of having $2m$ deepest leaves satisfies $\kappa[m]\sim 4^{-m+1}$. Numerical evaluation gives an average number of deepest leaves equal to $\hat{\kappa}\approx 2.8037$, while the probability of exactly two deepest leaves is $\kappa\approx 0.7009$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper studies the distribution of the number of deepest leaves in random plane binary trees. It derives square-root singular expansions for the generating functions associated to the Catalan iteration I_{k+1}(z)=1+z I_k(z)^2 via a three-zone dominated-convergence analysis of the truncation error in the critical regime. These expansions are used to obtain the probability of exactly two deepest leaves and the mean number of such leaves. The framework is then extended to the full limiting distribution by encoding the parameters in a bivariate generating function, reducing the problem to a functional equation via the Fatou coordinate of the Abel equation at the parabolic point, from which singularity analysis yields the exponential tail κ[m]∼4^{-m+1} with numerical values κ≈0.7009 and mean ≈2.8037.

Significance. If the derivations hold, the paper delivers a precise analytic description of an extremal local statistic in Catalan trees, extending standard singularity analysis to iterated recurrences and continuous iteration theory. The explicit exponential tail and the functional equation for the limiting distribution provide concrete, falsifiable predictions that can be checked numerically, and the three-zone technique for controlling truncation errors near z=1/4 offers a reusable tool for similar critical scaling problems in analytic combinatorics.

minor comments (2)
  1. The abstract states that the hierarchy of differential equations reduces to successive polynomial integrations, but the explicit form of the first few integrated expressions or the pattern for the coefficients is not displayed; adding one or two low-order examples would clarify the reduction step.
  2. The numerical values κ≈0.7009 and κ̂≈2.8037 are reported without an indication of the truncation order or precision used in the computation from the functional equation; a brief remark on the numerical method would strengthen reproducibility.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of the manuscript. The summary accurately reflects the analytic approach via iterated generating functions, the three-zone error analysis, and the use of continuous iteration to obtain the limiting distribution and exponential tail. We are pleased that the referee finds the results falsifiable and the techniques reusable.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's derivation starts from the standard Catalan iteration I_{k+1}(z)=1+z I_k(z)^2 and applies external analytic combinatorics tools: a three-zone dominated-convergence argument to extract square-root singular expansions at the dominant singularity ρ=1/4, followed by reduction of the bivariate generating function to a functional equation via the Fatou coordinate of the associated Abel equation. Singularity analysis then directly yields the exponential tail κ[m]∼4^{-m+1} and the numerical constants κ≈0.7009, κ̂≈2.8037 as computed outputs. No step equates a claimed prediction to a fitted input by construction, invokes a self-citation as the sole justification for a uniqueness claim, or renames a known result; all load-bearing passages rest on independent mathematical frameworks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The analysis rests on the standard recursive decomposition of plane binary trees and on classical results from singularity analysis and continuous iteration theory; no free parameters or new entities are introduced.

axioms (1)
  • domain assumption Plane binary trees satisfy the iterative generating-function equation I_{k+1}(z) = 1 + z I_k(z)^2 with I_0(z) = 0.
    This is the standard combinatorial decomposition used throughout the paper.

pith-pipeline@v0.9.0 · 5572 in / 1290 out tokens · 62916 ms · 2026-05-14T19:26:08.897937+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references

  1. [1]

    and Genitrini, A

    Bodini, O. and Genitrini, A. and Nurligareev, K. , title =. 2026 , howpublished =

    2026

  2. [2]

    , title =

    Aldous, D. , title =. Ann. Probab. , volume =

  3. [3]

    , title =

    Aldous, D. , title =. Stochastic Analysis: Proceedings of the Durham Symposium on Stochastic Analysis, 1990 , publisher=. 1991 , pages=

    1990

  4. [4]

    Colloquium on trees in algebra and programming , pages=

    Varieties of increasing trees , author=. Colloquium on trees in algebra and programming , pages=. 1992 , publisher=

    1992

  5. [5]

    and Genitrini, A

    Bodini, O. and Genitrini, A. and Gittenberger, B. and Wagner, S. , title =. Discrete Math. , volume =

  6. [6]

    Bodini and A

    O. Bodini and A. Genitrini and M. Naima and A. Singh , title =. Computer Science - Theory and Applications - 15th International Computer Science Symposium in Russia,

  7. [7]

    and Genitrini, A

    Bodini, O. and Genitrini, A. and Mailler, C. and Naima, M. , title =. Adv. Appl. Math. , volume =

  8. [8]

    , title =

    Clark, D.S. , title =. Discrete Appl. Math. , volume =

  9. [9]

    Chauvin and M

    B. Chauvin and M. Drmota and J. Jabbour-Hattab , title =. The Annals of Applied Probability , number =

  10. [10]

    and Gittenberger, B

    Drmota, M. and Gittenberger, B. , title =. Random Structures & Algorithms , volume =

  11. [11]

    and Odlyzko, A

    Flajolet, P. and Odlyzko, A. , title =. Journal of Computer and System Sciences , volume =

  12. [12]

    and Sedgewick, R

    Flajolet, P. and Sedgewick, R. , title =. 2009 , publisher =

    2009

  13. [13]

    and Hwang, H.-K

    Fuchs, M. and Hwang, H.-K. and Neininger, R. , title =. Algorithmica , pages =. 2006 , publisher =

    2006

  14. [14]

    and Hwang, H.-K

    Drmota, M. and Hwang, H.-K. , title =. SIAM Journal on Discrete Mathematics , volume =

  15. [15]

    generatingfunctionology: Third Edition , author=

  16. [16]

    Dynamics in one complex variable , author =

  17. [17]

    2015 , publisher =

    Nonlinear Dynamics and Chaos: With Applications to Physics, Biology, Chemistry, and Engineering , author =. 2015 , publisher =

    2015

  18. [18]

    2003 , publisher=

    Practical Extrapolation Methods: Theory and Applications , author=. 2003 , publisher=

    2003