Trees that can be grown in "too many" ways: Bouch's construction and a bound for every size

Abstract

We show that, for every positive integer $L$, there is a rooted tree on the square lattice that can be grown in at least $L!/C^L$ distinct ways, where $L$ denotes the number of bonds and $C>1$ is a constant independent of $L$. Bouch's hierarchical construction [Bouch2015] gives such trees along an unbounded sequence of sizes. We carefully review his construction and combine it with an elementary extraction lemma to obtain the bound for every size. (As discussed in Section~IV.A of [ParkerCaoAvdoshkinScaffidiAltman2019], Appendix~A.3 of [ShiraishiTasaki2024], and the video [TasakiVideo2025], the existence of such trees has an implication for operator growth and imaginary-time evolution in quantum spin systems in two or higher dimensions.) I wrote the first version of this note as a self-contained exposition of Bouch's construction. The stronger lower bound for every tree size presented here was proved by ChatGPT on the basis of that version (see the end of Section~1). I wish to make clear that I made no creative contribution to this beautiful and, I hope, useful theorem, whose proof is due to Bouch and ChatGPT.

12 pages, 6 figures. Expository note not to be submitted to any journals. Versions 1-3: A self-contained exposition of Bouch's construction. Version 4: Title changed. A new proof obtained by ChatGPT extends Bouch's bound to every tree size. The author claims no creative contribution to the proof