* [CZK14] Francesco Caltagirone, Lenka Zdeborová, and Florent Krzakala.  On convergence of approximate message passing.  In IEEE International Symposium on Information Theory, ISIT 2014, pages 1812–1816. IEEE, 2014.
  * [DG21] Amir Dembo and Reza Gheissari.  Diffusions interacting through a random matrix: universality via stochastic Taylor expansion.  Probability Theory and Related Fields, 180:1057–1097, 2021.
  * [DLS23] Rishabh Dudeja, Yue M. Lu, and Subhabrata Sen.  Universality of approximate message passing with semirandom matrices.  Annals of Probability, 51(5):1616–1683, 2023.
  * [DM15] Yash Deshpande and Andrea Montanari.  Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems.  In Conference on Learning Theory, COLT 2015, pages 523–562. PMLR, 2015.
  * [DMM09] David L. Donoho, Arian Maleki, and Andrea Montanari.  Message-passing algorithms for compressed sensing.  Proceedings of the National Academy of Sciences, 106(45):18914–18919, 2009.
  * [DMM10] David L. Donoho, Arian Maleki, and Andrea Montanari.  Message passing algorithms for compressed sensing: I. motivation and construction.  In IEEE Information Theory Workshop on Information Theory, ITW 2010, pages 1–5. IEEE, 2010.
  * [Dur19] Rick Durrett.  Probability: Theory and Examples.  Cambridge University Press, 2019.
  * [Fan22] Zhou Fan.  Approximate message passing algorithms for rotationally invariant matrices.  Annals of Statistics, 50(1):197–224, 2022.
  * [FKP19] Noah Fleming, Pravesh Kothari, and Toniann Pitassi.  Semialgebraic proofs and efficient algorithm design.  Foundations and Trends in Theoretical Computer Science, 14(1-2):1–221, 2019.
  * [FVRS22] Oliver Y. Feng, Ramji Venkataramanan, Cynthia Rush, and Richard J. Samworth.  A Unifying Tutorial on Approximate Message Passing.  Foundations and Trends in Machine Learning, 15(4):335–536, 2022.
  * [Gab20] Marylou Gabrié.  Mean-field inference methods for neural networks.  Journal of Physics A: Mathematical and Theoretical, 53(22):223002, 2020.
  * [GB23] Cédric Gerbelot and Raphaël Berthier.  Graph-based approximate message passing iterations.  Information and Inference: A Journal of the IMA, 12(4):2562–2628, 2023.
  * [GJJ+20] Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, and Goutham Rajendran.  Sum-of-squares lower bounds for Sherrington-Kirkpatrick via planted affine planes.  In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pages 954–965. IEEE, 2020.
  * [GTM+22] Cedric Gerbelot, Emanuele Troiani, Francesca Mignacco, Florent Krzakala, and Lenka Zdeborová.  Rigorous dynamical mean field theory for stochastic gradient descent methods.  arXiv preprint arXiv:2210.06591, 2022.
  * [HKP+17] Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer.  The Power of Sum-of-Squares for Detecting Hidden Structures.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 720–731. IEEE, 2017.
  * [HKP+18] Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, and Tselil Schramm.  On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique.  ACM Transactions on Algorithms, 14(3):1–31, 2018.
  * [HS23] Brice Huang and Mark Sellke.  Optimization Algorithms for Multi-Species Spherical Spin Glasses.  arXiv preprint arXiv:2308.09672, 2023.
  * [IS23] Misha Ivkov and Tselil Schramm.  Semidefinite programs simulate approximate message passing robustly.  arXiv preprint arXiv:2311.09017, 2023.
  * [Jan97] Svante Janson.  Gaussian Hilbert spaces, volume 129 of Cambridge Tracts in Mathematics.  Cambridge University Press, Cambridge, 1997.
  * [JM13] Adel Javanmard and Andrea Montanari.  State evolution for general approximate message passing algorithms, with applications to spatial coupling.  Information and Inference: A Journal of the IMA, 2(2):115–144, 2013.
  * [Jon22] Christopher Jones.  Symmetrized Fourier Analysis of Convex Relaxations for Combinatorial Optimization Problems.  PhD thesis, The University of Chicago, 2022.
  * [JP22] Chris Jones and Aaron Potechin.  Almost-orthogonal bases for inner product polynomials.  In Proceedings of the 13th Conference on Innovations in Theoretical Computer Science, ITCS 2022, volume 215, pages 89:1–89:21, 2022.
  * [JPR+21] Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, and Jeff Xu.  Sum-of-Squares Lower Bounds for Sparse Independent Set.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 406–416. IEEE, 2021.
  * [JPRX23] Chris Jones, Aaron Potechin, Goutham Rajendran, and Jeff Xu.  Sum-of-Squares Lower Bounds for Densest $k$-Subgraph.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 84–95. ACM, 2023.
  * [Kab03] Yoshiyuki Kabashima.  A CDMA multiuser detection algorithm on the basis of belief propagation.  Journal of Physics A: Mathematical and General, 36(43):11111, 2003.
  * [KF09] Daphne Koller and Nir Friedman.  Probabilistic Graphical Models: Principles and Techniques.  MIT press, 2009.
  * [KPX24] Pravesh Kothari, Aaron Potechin, and Jeff Xu.  Sum-of-squares lower bounds for ultra-sparse random graphs: Independent set and coloring.  To appear, 2024.
  * [KWB19] Dmitriy Kunisky, Alexander S. Wein, and Afonso S. Bandeira.  Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio.  In ISAAC Congress (International Society for Analysis, its Applications and Computation), pages 1–50. Springer, 2019.
  * [LFW23] Gen Li, Wei Fan, and Yuting Wei.  Approximate message passing from random initialization with applications to $\mathbb{Z}_{2}$-synchronization.  Proceedings of the National Academy of Sciences, 120(31):e2302930120, 2023.
  * [LSS23] Tengyuan Liang, Subhabrata Sen, and Pragya Sur.  High-dimensional Asymptotics of Langevin Dynamics in Spiked Matrix Models.  Information and Inference: A Journal of the IMA, 12(4):2720–2752, 2023.
  * [LW22] Gen Li and Yuting Wei.  A non-asymptotic framework for approximate message passing in spiked models.  arXiV preprint arXiv:2208.03313, 2022.
  * [LW24] Gen Li and Yuting Wei.  A non-asymptotic distributional theory of approximate message passing for sparse and robust regression.  To appear, 2024.
  * [MKTZ15] Andre Manoel, Florent Krzakala, Eric W. Tramel, and Lenka Zdeborová.  Swept Approximate Message Passing for Sparse Estimation.  In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, volume 37, pages 1123–1132, 2015.
  * [MM09] Marc Mézard and Andrea Montanari.  Information, Physics, and Computation.  Oxford University Press, 2009.
  * [MMZ01] Olivier C. Martin, Rémi Monasson, and Riccardo Zecchina.  Statistical mechanics methods and phase transitions in optimization problems.  Theoretical computer science, 265(1-2):3–67, 2001.
  * [Mon19] Andrea Montanari.  Optimization of the Sherrington-Kirkpatrick Hamiltonian.  In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, pages 1417–1433. IEEE, 2019.
  * [MP03] Marc Mézard and Giorgio Parisi.  The cavity method at zero temperature.  Journal of Statistical Physics, 111:1–34, 2003.
  * [MPV86] Marc Mézard, Giorgio Parisi, and Miguel Angel Virasoro.  SK Model: The Replica Solution without Replicas.  Europhysics Letters, 1(2):77, 1986.
  * [MPV87] Marc Mézard, Giorgio Parisi, and Miguel Angel Virasoro.  Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, volume 9.  World Scientific, 1987.
  * [MPW15] Raghu Meka, Aaron Potechin, and Avi Wigderson.  Sum-of-squares Lower Bounds for Planted Clique.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pages 87–96, 2015.
  * [MRB17] Yanting Ma, Cynthia Rush, and Dror Baron.  Analysis of approximate message passing with a class of non-separable denoisers.  In IEEE International Symposium on Information Theory, ISIT 2017, pages 231–235. IEEE, 2017.
  * [MSR73] Paul C. Martin, Eric D. Siggia, and Harvey A. Rose.  Statistical dynamics of classical systems.  Physical Review A, 8(1):423, 1973.
  * [MV21] Andrea Montanari and Ramji Venkataramanan.  Estimation of low-rank matrices via approximate message passing.  Annals of Statistics, 49:321–345, 2021.
  * [MV22] Marco Mondelli and Ramji Venkataramanan.  Approximate message passing with spectral initialization for generalized linear models.  Journal of Statistical Mechanics: Theory and Experiment, 2022(11):114003, 2022.
  * [MW19] Ankur Moitra and Alexander S Wein.  Spectral methods from tensor networks.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 926–937, 2019.
  * [MW22a] Andrea Montanari and Alexander S. Wein.  Equivalence of approximate message passing and low-degree polynomials in rank-one matrix estimation.  arXiv preprint arXiv:2212.06996, 2022.
  * [MW22b] Andrea Montanari and Yuchen Wu.  Statistically optimal first order algorithms: A proof via orthogonalization.  arXiv preprint arXiv:2201.05101, 2022.
  * [Pan13] Dmitry Panchenko.  The Sherrington–Kirkpatrick model.  Springer Science & Business Media, 2013.
  * [Par79] Giorgio Parisi.  Infinite number of order parameters for spin-glasses.  Physical Review Letters, 43(23):1754, 1979.
  * [Par80] Giorgio Parisi.  A sequence of approximated solutions to the SK model for spin glasses.  Journal of Physics A: Mathematical and General, 13(4):L115, 1980.
  * [Pea88] Judea Pearl.  Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference.  Morgan Kaufmann, 1988.
  * [PR20] Aaron Potechin and Goutham Rajendran.  Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems.  arXiv preprint arXiv:2011.04253, 2020.
  * [PR22] Aaron Potechin and Goutham Rajendran.  Sub-exponential time Sum-of-Squares lower bounds for Principal Components Analysis.  Advances in Neural Information Processing Systems, NeurIPS 2022, 35:35724–35740, 2022.
  * [RM14] Emile Richard and Andrea Montanari.  A statistical model for tensor PCA.  In Advances in Neural Information Processing Systems, NIPS 2014, pages 2897–2905, 2014.
  * [RSFS19] Sundeep Rangan, Philip Schniter, Alyson K. Fletcher, and Subrata Sarkar.  On the convergence of approximate message passing with arbitrary matrices.  IEEE Transactions on Information Theory, 65(9):5339–5351, 2019.
  * [RSS18] Prasad Raghavendra, Tselil Schramm, and David Steurer.  High dimensional estimation via sum-of-squares proofs.  In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 3389–3423. World Scientific, 2018.
  * [RT23] Goutham Rajendran and Madhur Tulsiani.  Concentration of polynomial random matrices via Efron-Stein inequalities.  In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, pages 3614–3653. SIAM, 2023.
  * [RV18] Cynthia Rush and Ramji Venkataramanan.  Finite sample analysis of approximate message passing algorithms.  IEEE Transactions on Information Theory, 64(11):7264–7286, 2018.
  * [SS24a] Juspreet Singh Sandhu and Jonathan Shi.  A sum-of-squares hierarchy in the absence of pointwise proofs i: Energy certificates.  arXiv preprint arXiv:2401.14383, 2024.
  * [SS24b] Juspreet Singh Sandhu and Jonathan Shi.  A sum-of-squares hierarchy in the absence of pointwise proofs ii: Rounding high-entropy steps.  To appear, 2024.
  * [Tak19a] Keigo Takeuchi.  Rigorous dynamics of expectation-propagation-based signal recovery from unitarily invariant measurements.  IEEE Transactions on Information Theory, 66(1):368–386, 2019.
  * [Tak19b] Keigo Takeuchi.  A unified framework of state evolution for message-passing algorithms.  In IEEE International Symposium on Information Theory, ISIT 2019, pages 151–155. IEEE, 2019.
  * [Tak21] Keigo Takeuchi.  Bayes-optimal convolutional AMP.  IEEE Transactions on Information Theory, 67(7):4405–4428, 2021.
  * [Tal06] Michel Talagrand.  The Parisi formula.  Annals of Mathematics, pages 221–263, 2006.
  * [Tal10] Michel Talagrand.  Mean field models for spin glasses: Volume I: Basic examples, volume 54.  Springer Science & Business Media, 2010.
  * [TAP77] David J. Thouless, Philip W. Anderson, and Robert G. Palmer.  Solution of ‘Solvable model of a spin glass’.  Philosophical Magazine, 35(3):593–601, 1977.
  * [VSR+15] Jeremy Vila, Philip Schniter, Sundeep Rangan, Florent Krzakala, and Lenka Zdeborová.  Adaptive damping and mean removal for the generalized approximate message passing algorithm.  In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2015, pages 2021–2025. IEEE, 2015.
  * [WZF22] Tianhao Wang, Xinyi Zhong, and Zhou Fan.  Universality of approximate message passing algorithms and tensor networks.  arXiv preprint arXiv:2206.13037, 2022.
  * [YFW03] Jonathan S. Yedidia, William T. Freeman, and Yair Weiss.  Understanding belief propagation and its generalizations.  Exploring artificial intelligence in the new millennium, 8(236-239):0018–9448, 2003.
  * [ZK16] Lenka Zdeborová and Florent Krzakala.  Statistical physics of inference: Thresholds and algorithms.  Advances in Physics, 65(5):453–552, 2016.
  * [ZY22] Qiuyun Zou and Hongwen Yang.  A Concise Tutorial on Approximate Message Passing.  arXiv preprint arXiv:2201.07487, 2022.

##  Appendix A Fourier analytic properties

In Definition 3.2, for a proper $\alpha\in{\cal A}$ (a graph instead of a
multigraph), $Z_{\alpha}$ has entries which are homogeneous multilinear
polynomials in the entries of the matrix $A$. The proper diagrams with size at
most $n$ form an orthogonal basis of symmetric polynomials in $A$ with respect
to the expectation over $A$, as shown in the next lemma.

######  Lemma A.1.

For all $i,j\in[n]$ and distinct proper diagrams $\alpha,\beta\in{\cal A}$,
$\operatorname*{\mathbb{E}}\left[Z_{\alpha,i}Z_{\beta,j}\right]=0$.

###### Proof.

For each distinct $S,T\subseteq\binom{[n]}{2}$, the independence and
centeredness of the off-diagonal entries of $A$ proves that

$\operatorname*{\mathbb{E}}\left[\prod_{\\{i,j\\}\in
S}A_{ij}\prod_{\\{k,\ell\\}\in T}A_{k\ell}\right]=0\,.$

Two distinct diagrams sum over distinct sets of multilinear monomials, so this
orthogonality extends to diagrams. ∎

The diagrams are not normalized for that inner product, but their variance can
be estimated as follows:

######  Lemma A.2.

For all $i\in[n]$ and proper $\alpha\in{\cal
A}\setminus\\{\vbox{\hbox{\includegraphics[height=8.61108pt]{diagram-
analysis/images/singleton.png}}}\\}$ we have
$\operatorname*{\mathbb{E}}\left[Z_{\alpha,i}\right]=0$ and

$\displaystyle\operatorname*{\mathbb{E}}\left[Z_{\alpha,i}^{2}\right]$
$\displaystyle\underset{\phantom{n\to\infty}}{=}\left\lvert\operatorname{Aut}(\alpha)\right\rvert\cdot\frac{(n-1)(n-2)\cdots(n-|V(\alpha)|+1)}{n^{|E(\alpha)|}}$
$\displaystyle\underset{n\to\infty}{=}\left\lvert\operatorname{Aut}(\alpha)\right\rvert\cdot
n^{\left\lvert V(\alpha)\right\rvert-1-\left\lvert
E(\alpha)\right\rvert}(1+o(1))\,,$

where the last estimate holds when $|V(\alpha)|=o(\sqrt{n})$.

###### Proof.

When $\alpha$ is proper, $Z_{\alpha,i}$ is a multilinear polynomial with zero
constant coefficient, and so it has expectation 0. For the second moment, we
have

$\displaystyle\operatorname*{\mathbb{E}}\left[Z_{\alpha,i}^{2}\right]$
$\displaystyle=\sum_{\begin{subarray}{c}\text{injective
}\varphi_{1}:V(\alpha)\to[n]\\\
\varphi_{1}(\vbox{\hbox{\includegraphics[height=4.52083pt]{diagram-
analysis/images/singleton.png}}})=i\end{subarray}}\sum_{\begin{subarray}{c}\text{injective
}\varphi_{2}:V(\alpha)\to[n]\\\
\varphi_{2}(\vbox{\hbox{\includegraphics[height=4.52083pt]{diagram-
analysis/images/singleton.png}}})=i\end{subarray}}\operatorname*{\mathbb{E}}\left[\prod_{\\{u,v\\}\in
E(\alpha)}A_{\varphi_{1}(u)\varphi_{1}(v)}A_{\varphi_{2}(u)\varphi_{2}(v)}\right]\,.$

Since $\operatorname*{\mathbb{E}}\left[A_{jk}\right]=0$ for $j\neq k$, the
only terms with nonzero expectation have each $A_{jk}$ occurring at least
twice. As $\varphi_{1}$ are $\varphi_{2}$ are injective, each $A_{jk}$ can
only occur at most twice. Therefore, if we fix $\varphi_{1}$ the embeddings
$\varphi_{2}$ that contribute a nonzero value are exactly graph isomorphisms
onto $\operatorname{im}(\varphi_{1})$. The total number of choices for
$\varphi_{1}$ and $\varphi_{2}$ is $(n-1)\cdots(n-\left\lvert
V(\alpha)\right\rvert+1)\cdot\left\lvert\operatorname{Aut}(\alpha)\right\rvert$
and the expectation of a nonzero term is

$\prod_{\\{j,k\\}\in
E(\alpha)}\operatorname*{\mathbb{E}}\left[A_{jk}^{2}\right]=\frac{1}{n^{|E(\alpha)|}}\,.$

This completes the proof of the first part of the statement. Under the further
assumption $|V(\alpha)|=o(\sqrt{n})$, the falling factorial can then be
estimated as

$\displaystyle\left|\log\left(\frac{(n-1)\ldots(n-|V(\alpha)|+1)}{n^{|V(\alpha)|-1}}\right)\right|$
$\displaystyle\leq\sum_{i=1}^{|V(\alpha)|-1}\left|\log\left(1-\frac{i}{n}\right)\right|$
$\displaystyle\leq\sum_{i=1}^{|V(\alpha)|-1}\frac{i}{n}\underset{n\to\infty}{\longrightarrow}0\,.$

This implies that $(n-1)\ldots(n-|V(\alpha)|+1)=(1+o(1))n^{|V(\alpha)|-1}$, as
desired. ∎

We can already see from the previous lemma that if $\alpha\in{\cal T}$ is a
tree, then the variance of $Z_{\alpha,i}$ is $\Theta(1)$, whereas if $\alpha$
is a connected graph with a cycle, then the variance of $Z_{\alpha,i}$ is
$o(1)$.

We will use orthogonality repeatedly in the sequel through the following
direct consequence of Lemma A.1 and Lemma A.2:

######  Corollary A.3.

Let $x=\sum_{\textnormal{proper }\alpha\in{\cal A}}c_{\alpha}Z_{\alpha}$. Then
for any $\tau\in{\cal T}$,

$\operatorname*{\mathbb{E}}\left[x_{i}Z_{\tau,i}\right]=c_{\tau}\operatorname*{\mathbb{E}}\left[Z_{\tau,i}^{2}\right]\underset{n\to\infty}{=}c_{\tau}\left\lvert\operatorname{Aut}(\tau)\right\rvert+o(1)\,,$

where the second estimate holds for $|V(\tau)|=o(\sqrt{n})$.

In particular,
$\operatorname*{\mathbb{E}}\left[x\right]=c_{\vbox{\hbox{\includegraphics[height=4.52083pt]{diagram-
analysis/images/singleton.png}}}}\vec{1}$ where
$c_{\vbox{\hbox{\includegraphics[height=4.52083pt]{diagram-
analysis/images/singleton.png}}}}$ is the coefficient of the singleton
diagram.

##  Appendix B Derivation of Operations on the Diagram Basis

The plan of this section is the following.

  * •

Section B.1 is a cheat sheet describing three important combinatorial
principles that underlie diagram calculus.

  * •

In Section B.2, we derive the effects of GFOM operations on the full diagram
expansion. We then deduce their asymptotic effects on tree diagrams.

  * •

In Section B.3, we define the repeated-label diagram basis, which is the
simplest way to represent a first-order iteration. We do not use the repeated-
label diagram basis directly in this paper.

###  B.1 General combinatorial principles

We demonstrate combinatorial principles for diagram analysis through an
example of squaring the 2-path diagram componentwise.

When we multiply two diagrams $\tau$ and $\rho$ coordinatewise, by virtue of
Definition 3.2 we obtain a sum over pairs of injective embeddings of the
vertices of $\tau$ and $\rho$ into $[n]$. The joint embedding may not be
injective, so we case on the overlap between the two embeddings. In this
example, we have the following (non-asymptotic) diagrammatic equality:

which corresponds to the algebraic identity:171717The factor of 2 is a
“symmetry factor” which appears when performing combinatorics on symmetry-
reduced objects such as the diagrams.

$\displaystyle\left(\sum_{\begin{subarray}{c}j,k=1\\\ i,j,k\text{
distinct}\end{subarray}}^{n}A_{ij}A_{jk}\right)^{2}$
$\displaystyle=\sum_{\begin{subarray}{c}j,k,\ell,m=1\\\ i,j,k,\ell,m\text{
distinct}\end{subarray}}^{n}A_{ij}A_{jk}A_{i\ell}A_{\ell
m}+\sum_{\begin{subarray}{c}j,k,\ell=1\\\ i,j,k,\ell\text{
distinct}\end{subarray}}^{n}A_{ij}^{2}A_{jk}A_{j\ell}+\sum_{\begin{subarray}{c}j,k=1\\\
i,j,k\text{ distinct}\end{subarray}}^{n}A_{ij}^{2}A_{jk}^{2}$
$\displaystyle\;\;\;+\sum_{\begin{subarray}{c}j,k,\ell=1\\\ i,j,k,\ell\text{
distinct}\end{subarray}}^{n}A_{ij}A_{jk}A_{i\ell}A_{\ell
k}+2\sum_{\begin{subarray}{c}j,k,\ell=1\\\ i,j,k,\ell\text{
distinct}\end{subarray}}^{n}A_{ij}A_{jk}A_{ik}A_{k\ell}+\sum_{\begin{subarray}{c}j,k=1\\\
i,j,k\text{ distinct}\end{subarray}}^{n}A_{ij}A_{ik}A_{jk}^{2}$

This is summarized in the following general principle:

######  Combinatorial Principle 1.

A joint summation over two or more embeddings can be partitioned based on
which vertices overlap.

This re-expresses the product of two diagrams in the diagram basis. Notice
that new multiedges may be created.

######  Combinatorial Principle 2.

A hanging double edge can be asymptotically removed. Inductively, a hanging
tree of double edges can be asymptotically removed.

The intuitive justification for this is as follows. If a hanging double edge
attaches a vertex $j$ to the hanging vertex $k$, then the contribution of $k$
to the diagram is $A_{jk}^{2}$ summed over $n-|V(\alpha)|+1$ choices for $k$.
We have $\operatorname*{\mathbb{E}}\left[A_{jk}^{2}\right]=\frac{1}{n}$ so
that in expectation the contribution is $1-\frac{|V(\alpha)|-1}{n}\approx 1$.
We can remove the hanging double edge up to a negligible multiplicative factor
and the negligible fluctuation of the summation over $k$.

As for the remaining intersection terms, it turns out that they are all
negligible.

######  Combinatorial Principle 3.

Let $\alpha$ be a rooted, connected diagram. If removing the hanging double
edges creates a tree of single edges, then $\alpha$ is non-negligible.
Otherwise, $\alpha$ is negligible.

The informal explanation is simply that cyclic diagrams sum over fewer terms
than tree-shaped diagrams. For example, the left diagram is a sum over
${\displaystyle\approx}\,n^{4}$ terms while the right diagram is a sum over
${\displaystyle\approx}\,n^{3}$ terms.181818 In the message passing viewpoint,
a vertex $v_{0}$ receives $\Theta(n^{4})$ messages along paths of distinct
vertices $(v_{0},v_{1},v_{2})$ and $(v_{0},v_{3},v_{4})$, whereas it only
receives $\Theta(n^{3})$ “cyclic” messages along paths
$(v_{0},v_{1},v_{2},v_{3},v_{0})$.

In almost all cases (cycles, non-hanging double edges, higher multiplicity
edges, etc), the smaller number of terms makes the diagram negligible. Trees
of single edges with hanging trees of double edges are the only non-negligible
cases.

Following the combinatorial principles, the asymptotic representation of the
componentwise square of the 2-path is:

###  B.2 Derivation of the asymptotic operations

First, we exactly express the effect of multiplying a diagram by $A$:

######  Lemma B.1.

For all diagrams $\alpha\in{\cal A}$,

$AZ_{\alpha}=Z_{\alpha^{+}}+\sum_{v\in V(\alpha)}Z_{\textnormal{contract $v$
and $\vbox{\hbox{\includegraphics[height=6.02777pt]{diagram-
analysis/images/singleton.png}}}$ in $\alpha^{+}$}}\,.$

###### Proof.

We write:

$\displaystyle(AZ_{\alpha})_{i}$
$\displaystyle=\sum_{j=1}^{n}A_{ij}\sum_{\begin{subarray}{c}\varphi:V(\alpha)\to[n]\\\
\varphi\text{ injective}\\\
\varphi(\vbox{\hbox{\includegraphics[height=4.52083pt]{diagram-
analysis/images/singleton.png}}})=j\end{subarray}}\prod_{\\{u,v\\}\in
E(\alpha)}A_{\varphi(u)\varphi(v)}$
$\displaystyle=\sum_{\begin{subarray}{c}\varphi:V(\alpha)\to[n]\\\
\varphi\text{
injective}\end{subarray}}A_{i,\varphi(\vbox{\hbox{\includegraphics[height=4.52083pt]{diagram-
analysis/images/singleton.png}}})}\prod_{\\{u,v\\}\in
E(\alpha)}A_{\varphi(u)\varphi(v)}\,.$

The sum over $\varphi$ can be partitioned based on whether
$i\in\operatorname{im}(\varphi)$. The terms with
$i\not\in\operatorname{im}(\varphi)$ sum to $Z_{\alpha^{+}}$. The terms with
$i\in\operatorname{im}(\varphi)$ sum to the different contractions of
$\alpha^{+}$ based on which vertex of $\alpha$ is labeled $i$. ∎

In the asymptotic diagram basis, we start from $\tau\in{\cal T}$. Following
the asymptotic classification of non-negligible diagrams (3 or Section 4.2),
which diagrams are non-negligible? The only diagrams that do not introduce a
cycle of length ${\geq 3}$ are $\tau^{+}$ and intersections between  in
$\tau^{+}$ and the children of the old root. The latter case introduces a
double edge, which can only be hanging if $\tau\in{\cal S}$ (and in this case
it can be removed asymptotically). Hence we conclude

$AZ_{\tau}\,\overset{\infty}{=}\,\begin{cases}Z_{\tau^{+}}+Z_{\tau^{-}}&\text{
if }\tau\in{\cal S}\\\ Z_{\tau^{+}}&\text{ if }\tau\in{\cal T}\setminus{\cal
S}\,.\end{cases}$

We now switch to describe the effect of componentwise product. To capture the
combinatorics, we define the concepts of intersection patterns and
intersection diagrams.

######  Definition B.2 (Intersection pattern, $P\in{\cal
P}(\alpha_{1},\dots,\alpha_{k})$).

Let $\alpha_{1},\dots,\alpha_{k}\in{\cal A}$. Let $\alpha$ be the diagram
obtained by putting all $\alpha_{i}$ at the same root. An intersection pattern
$P$ is a partition of
$V(\alpha)\setminus\\{\vbox{\hbox{\includegraphics[height=8.61108pt]{diagram-
analysis/images/singleton.png}}}\\}$ such that for all $i\in[k]$ and $v,w\in
V(\alpha_{i})\setminus\\{\vbox{\hbox{\includegraphics[height=8.61108pt]{diagram-
analysis/images/singleton.png}}}\\}$, $v$ and $w$ are not in the same block of
the partition.

Let ${\cal P}(\alpha_{1},\dots,\alpha_{k})$ be the set of intersection
patterns between $\alpha_{1},\dots,\alpha_{k}$.

######  Definition B.3 (Intersection diagram, $\alpha_{P}$).

Let $\alpha\in{\cal A}$. Given a partition $P$ of $V(\alpha)$, let
$\alpha_{P}$ be the diagram obtained by contracting each block of $P$ into a
single vertex. Keep all edges (hence there may be new multiedges).

By casing on which vertices are equal among the embeddings of
$\alpha_{1},\dots,\alpha_{k}$ as in the proof of Lemma B.1, we have:

######  Lemma B.4.

For $\alpha_{1},\dots,\alpha_{k}\in{\cal A}$, the componentwise product of
$Z_{\alpha_{1}},\ldots,Z_{\alpha_{k}}$ is

$Z_{\alpha_{1}}\odot\cdots\odot Z_{\alpha_{k}}=\sum_{P\in{\cal
P}(\alpha_{1},\dots,\alpha_{k})}Z_{\alpha_{P}}\,.$

Given tree diagrams $\tau_{1},\dots,\tau_{k}\in{\cal T}$, we can identify the
asymptotically non-negligible terms in the product as follows. Let
$\widetilde{\tau}$ be a non-negligible diagram appearing in the result, i.e.
$\widetilde{\tau}$ is a tree with hanging trees of double edges. Since
$\tau_{1},\dots,\tau_{k}$ are connected, the hanging double trees must hang
off the root vertex of $\widetilde{\tau}$ in order to avoid cycles.
Additionally, they must arise as the overlap of two complete copies of the
tree. Thus we see that the asymptotically non-negligible terms are the partial
matchings between isomorphic subtrees of the root. Two copies of a subtree
$\sigma\in{\cal S}$ can be matched up into a tree of double edges in
$\left\lvert\operatorname{Aut}(\sigma)\right\rvert$ ways.

###  B.3 Repeated-label diagram basis

An alternative basis for the diagram space consists of diagrams in which
labels are allowed to repeat. This representation was also defined by Ivkov
and Schramm [IS23, Section 3.5].

######  Definition B.5 ($\widetilde{Z}_{\alpha}$).

For a diagram $\alpha$ with root  , define
$\widetilde{Z}_{\alpha}\in\mathbb{R}^{n}$ by

$\widetilde{Z}_{\alpha,i}=\sum_{\begin{subarray}{c}\varphi:V(\alpha)\to[n]\\\
\varphi(\vbox{\hbox{\includegraphics[height=4.52083pt]{diagram-
analysis/images/singleton.png}}})=i\end{subarray}}\prod_{\\{u,v\\}\in
E(\alpha)}A_{\varphi(u)\varphi(v)}\,.$

The only difference between $\widetilde{Z}_{\alpha}$ and $Z_{\alpha}$ is that
the embedding $\varphi$ must be injective in $Z_{\alpha}$. To perform the
change of basis in one direction is as easy as replacing
$\widetilde{Z}_{\alpha}$ by a sum of $Z_{\alpha}$ based on which labels are
repeated.

######  Lemma B.6.

For $\alpha\in{\cal A}$,

$\widetilde{Z}_{\alpha}=\sum_{P\in{\cal P}(\alpha)}Z_{\alpha_{P}}$

where ${\cal P}(\alpha)$ is the set of partitions of $V(\alpha)$ and
$\alpha_{P}$ contracts the blocks of $P$ (Definition B.3).

###### Proof.

We have

$\widetilde{Z}_{\alpha,i}=\sum_{\begin{subarray}{c}\varphi:V(\alpha)\to[n]\\\
\varphi(\vbox{\hbox{\includegraphics[height=4.52083pt]{diagram-
analysis/images/singleton.png}}})=i\end{subarray}}\prod_{\\{u,v\\}\in
E(\alpha)}A_{\varphi(u)\varphi(v)}\,.$

The sum over $\varphi$ can be divided based on which vertices are assigned the
same label. The terms with a given partition $P$ of $V(\alpha)$ are exactly
$Z_{\alpha_{P},i}$. ∎

The algorithmic operations are simpler to compute in this basis, although the
asymptotic tree approximation does not seem to be easily visible in this basis
(the tree diagrams do not span the same space, and a diagram which is an even
cycle has entries with magnitude $\Theta(1)$ in $\widetilde{Z}_{\alpha}$ but
negligible entries in $Z_{\alpha}$).

Given the current representation $x_{t}=\sum_{\tau\in{\cal
T}}c_{\tau}\widetilde{Z}_{\tau}$ the operations have the following effects on
the $\widetilde{Z}_{\tau}$ (non-asymptotically i.e. without taking the limit
$n\to\infty$).

  1. (i)

Multiplying by $A$ extends the root.

We have $A\widetilde{Z}_{\alpha}=\widetilde{Z}_{\alpha^{+}}$ where
$\alpha^{+}$ is obtained by extending the root by one edge.

  2. (ii)

Componentwise products graft trees together.

To componentwise multiply $\widetilde{Z}_{\alpha}$ and
$\widetilde{Z}_{\beta}$, we “graft” $\alpha$ and $\beta$ by merging their
roots.

######  Example B.7.

Returning to the running example,

$x_{t+1}=(Ax_{t})^{2}\qquad\qquad x_{0}=\vec{1}$

where $\vec{1}\in\mathbb{R}^{n}$ is the all-ones vector and the square
function is applied componentwise. The first few iterations are,

$x_{0}=\vec{1}$ | $x_{1}=(A\vec{1})^{2}$ | $x_{2}=(A(A\vec{1})^{2})^{2}$
---|---|---
$x_{0,i}=1$ | $\displaystyle x_{1,i}=\sum_{\begin{subarray}{c}j_{1},j_{2}=1\end{subarray}}^{n}A_{ij_{1}}A_{ij_{2}}$ | $\displaystyle x_{2,i}=\sum_{j_{1},j_{2}=1}^{n}\sum_{k_{1},k_{2}=1}^{n}\sum_{\ell_{1},\ell_{2}=1}^{n}A_{ij_{1}}A_{ij_{2}}A_{j_{1}k_{1}}A_{j_{1}\ell_{1}}A_{j_{2}k_{2}}A_{j_{2}\ell_{2}}$
|  |

##  Appendix C Omitted Proofs

###  C.1 Removing hanging double edges

In order to implement the removal of hanging double edges, we introduce an
additional diagrammatic construct to track the error, 2-labeled edges. These
terms are equal to zero when $A$ is a Rademacher matrix and it is recommended
to ignore them on a first read.

######  Definition C.1 (Edge-labeled diagram).

An edge-labeled diagram is a diagram in which some of the edges are labeled
“2”.

We let $E(\alpha)$ denote the entire multiset of labeled and unlabeled edges
of $\alpha$, $E_{2}(\alpha)$ the multiset of 2-labeled edges and
$E_{1}(\alpha)=E\setminus E_{2}(\alpha)$ the multiset of non-labeled edges.

We use the convention that $\left\lvert E(\alpha)\right\rvert$ counts each
2-labeled edge twice, so that $\left\lvert E(\alpha)\right\rvert$ continues to
equal the degree of the polynomial $Z_{\alpha,i}$.

######  Definition C.2 (Edge-labeled $Z_{\alpha}$).

For an edge-labeled diagram $\alpha$, we define $Z_{\alpha}\in\mathbb{R}^{n}$
by

$Z_{\alpha,i}=\sum_{\begin{subarray}{c}\textnormal{injective
}\varphi:V(\alpha)\to[n]\\\
\varphi(\vbox{\hbox{\includegraphics[height=4.52083pt]{diagram-
analysis/images/singleton.png}}})=i\end{subarray}}\prod_{\\{u,v\\}\in
E_{1}(\alpha)}A_{\varphi(u)\varphi(v)}\prod_{\\{u,v\\}\in
E_{2}(\alpha)}\left(A_{\varphi(u)\varphi(v)}^{2}-\frac{1}{n}\right)\,.$

We extend the set of diagrams ${\cal A}$ to allow diagrams which may have
2-labeled edges. We update the definition of $I(\alpha)$ from Definition 4.1
to incorporate labeled edges (because a labeled edge is mean-0, it is treated
like a single edge).

######  Definition C.3 (Updated definition of $I(\alpha)$).

For a diagram $\alpha\in{\cal A}$, let $I(\alpha)$ be the subset of non-root
vertices such that every edge incident to that vertex has multiplicity $\geq
2$ or is a self-loop, treating 2-labeled edges as if they were normal edges.

We show the following exact decomposition for removing hanging double edges:

######  Lemma C.4.

Let $\alpha\in{\cal A}$ be a diagram with a hanging (unlabeled) double edge.
Let $\alpha_{0}$ be $\alpha$ with both the hanging double edge and
corresponding hanging vertex removed, and $\alpha_{2}$ be $\alpha$ with the
hanging double edge replaced by a single 2-labeled edge. Then,

$Z_{\alpha}=Z_{\alpha_{0}}-\frac{|V(\alpha)|-1}{n}\cdot
Z_{\alpha_{0}}+Z_{\alpha_{2}}\,.$

###### Proof.

We write:

$\displaystyle Z_{\alpha,i}$
$\displaystyle=\sum_{\begin{subarray}{c}\text{injective
}\varphi:V(\alpha)\to[n]\\\
\varphi(\vbox{\hbox{\includegraphics[height=4.52083pt]{diagram-
analysis/images/singleton.png}}})=i\end{subarray}}A_{u,v}^{2}\prod_{\\{x,y\\}\in
E(\alpha)\setminus\\{\\{u,v\\},\\{u,v\\}\\}}A_{\varphi(x)\varphi(y)}$
$\displaystyle=Z_{\alpha_{2},i}+\frac{1}{n}\sum_{\begin{subarray}{c}\text{injective
}\varphi:V(\alpha)\to[n]\\\
\varphi(\vbox{\hbox{\includegraphics[height=4.52083pt]{diagram-
analysis/images/singleton.png}}})=i\end{subarray}}\prod_{\\{x,y\\}\in
E(\alpha)\setminus\\{\\{u,v\\},\\{u,v\\}\\}}A_{\varphi(x)\varphi(y)}$
$\displaystyle=Z_{\alpha_{2},i}+\frac{n-|V(\alpha)|+1}{n}\cdot
Z_{\alpha_{0},i}=Z_{\alpha_{0},i}-\frac{|V(\alpha)|-1}{n}Z_{\alpha_{0},i}+Z_{\alpha_{2},i}\,.$

The additional $n-|V(\alpha)|+1$ scaling factor comes from removing the
hanging vertex. ∎

###  C.2 Omitted proofs for Section 4.1

We prove a more specific version of Lemma 4.2

######  Lemma C.5.

Let $q\in\mathbb{N},\alpha\in{\cal A},$ and $i\in[n]$. Then,

$\left\lvert\operatorname*{\mathbb{E}}\left[Z_{\alpha,i}^{q}\right]\right\rvert\leq
M_{q|E(\alpha)|}2^{q|E(\alpha)|}(q\left\lvert
V(\alpha)\right\rvert)^{q|V(\alpha)|}\cdot
n^{\frac{q}{2}\left(|V(\alpha)|-1-|E(\alpha)|+|I(\alpha)|\right)}\,,$

where $M_{k}$ is a bound on the $k$-th moment of the entries of $A$ (recall
the notations of 2.1),

$M_{k}=\max\left(\operatorname*{\mathbb{E}}_{X\sim\mu}\left[\left\lvert
X\right\rvert^{k}\right],\;\operatorname*{\mathbb{E}}_{X\sim\mu_{0}}\left[\left\lvert
X\right\rvert^{k}\right]\right)\,.$

When $q$ and $|V(\alpha)|$ are $O(1)$, the overall bound reduces to

$\left\lvert\operatorname*{\mathbb{E}}\left[Z_{\alpha,i}^{q}\right]\right\rvert\leq
O\left(n^{\frac{q}{2}\left(|V(\alpha)|-1-|E(\alpha)|+|I(\alpha)|\right)}\right)\,.$

###### Proof.

We expand $\operatorname*{\mathbb{E}}\left[Z_{\alpha,i}^{q}\right]$ as

$\displaystyle\sum_{\begin{subarray}{c}\text{injective
}\varphi_{1},\ldots,\varphi_{q}:V(\alpha)\to[n]\\\
\varphi_{1}(\vbox{\hbox{\includegraphics[height=4.52083pt]{diagram-
analysis/images/singleton.png}}})=\cdots=\varphi_{q}(\vbox{\hbox{\includegraphics[height=4.52083pt]{diagram-
analysis/images/singleton.png}}})=i\end{subarray}}\operatorname*{\mathbb{E}}\left[\prod_{p=1}^{q}\left(\prod_{\\{u,v\\}\in
E_{1}(\alpha)}A_{\varphi_{p}(u)\varphi_{p}(v)}\right)\left(\prod_{\\{u,v\\}\in
E_{2}(\alpha)}\left(A_{\varphi_{p}(u)\varphi_{p}(v)}^{2}-\frac{1}{n}\right)\right)\right]\,.$

This is a polynomial of degree $q|E(\alpha)|$ in $A$ (by convention every
2-labeled edge contributes $2$ to $|E(\alpha)|$). We first estimate the
magnitude of any summand of the sum over $\varphi_{1},\ldots,\varphi_{q}$ with
nonzero expectation. We decompose each such summand into
$2^{q|E_{2}(\alpha)|}$ terms by expanding out191919The factor
$2^{q|E_{2}(\alpha)|}$ may be removed with a tighter argument. the
$A_{ij}^{2}-\frac{1}{n}$. We are left with monomials in the entries of $A$ of
total degree at most $q|E(\alpha)|$. We bound the expected value of each of
these monomials by $M_{q|E(\alpha)|}n^{-q|E(\alpha)|/2}$ using Hölder’s
inequality. This shows that any nonzero term in the summation has magnitude at
most $2^{q|E_{2}(\alpha)|}M_{q|E(\alpha)|}n^{-q|E(\alpha)|/2}$.

To bound the number of nonzero terms, we observe that every edge $A_{jk}$ for
$j\neq k$ must occur zero times or at least twice in order to have nonzero
expectation (the self-loops $A_{jj}$ can occur any number of times, and the
2-labeled edges $A_{jk}^{2}-\frac{1}{n}$ must overlap at least one additional
edge in order to have nonzero expectation). Each vertex in $V(\alpha)\setminus
I(\alpha)\setminus\\{\vbox{\hbox{\includegraphics[height=8.61108pt]{diagram-
analysis/images/singleton.png}}}\\}$ is incident to an edge of multiplicity 1
or a 2-labeled edge, and so it must occur in at least two embeddings in order
for that edge $A_{jk}$ to overlap and not make the expectation 0. This implies
that the number of distinct non-root vertices among the embeddings is at most
$q\left(|V(\alpha)|-1+|I(\alpha)|\right)/2$ where the $-1$ is used to avoid
counting the root.

Hence, there are at most $n^{q\left(|V(\alpha)|-1+|I(\alpha)|\right)/2}$ ways
to choose the entire image
$\operatorname{im}(\varphi_{1})\cup\ldots\cup\operatorname{im}(\varphi_{q})$.
Once this is fixed, there are at most $(q|V(\alpha)|)^{q|V(\alpha)|}$
$q$-tuples of embeddings that map to these vertices. We conclude by combining
the bound on the number of nonzero terms and the bound on the magnitude of
each of these terms. ∎

See 4.5

###### Proof.

We first focus on a single combinatorially negligible term $a_{n}Z_{\alpha}$.
For any $\varepsilon>0$ and $i\in[n]$, by Lemma C.5 and Markov’s inequality,
we have

$\Pr\left(|a_{n}Z_{\alpha,i}|\geq\varepsilon\right)\leq\frac{\operatorname*{\mathbb{E}}\left[(a_{n}Z_{\alpha,i})^{6}\right]}{\varepsilon^{6}}\leq
O\left(\frac{1}{n^{3}\varepsilon^{6}}\right)\,.$

By a union bound over all coordinates $i\in[n]$,
$\Pr\left(\|a_{n}Z_{\alpha}\|_{\infty}\geq\varepsilon\right)\leq
O(n^{-2}\varepsilon^{-6})$. Applying this to every combinatorially negligible
term appearing in $x-y$ (there are constantly many such terms by definition),
if $x\,\overset{\infty}{=}\,y$ we also have
$\Pr\left(\|x-y\|_{\infty}\geq\varepsilon\right)\leq
O(n^{-2}\varepsilon^{-6})$. The conclusion follows from the Borel-Cantelli
lemma. ∎

See 4.6

###### Proof.

It suffices to prove that for a combinatorially negligible term
$n^{-k}Z_{\alpha}$:

  1. (i)

All terms in the diagram representation of $n^{-k}AZ_{\alpha}$ are
combinatorially negligible.

  2. (ii)

Let $n^{-\ell}Z_{\beta}$ be any term of combinatorial order $1$ or
combinatorially negligible. Then all terms in the diagram representation of
the componentwise product $n^{-(k+\ell)}Z_{\alpha}\odot Z_{\beta}$ are
combinatorially negligible, where $\odot$ is the componentwise product.

For (i), the diagram representation of $AZ_{\alpha}$ is given by Lemma B.1. In
the term $\alpha^{+}$ without intersections,

$|V(\alpha^{+})|=|V(\alpha)|+1\,,\qquad|I(\alpha^{+})|=|I(\alpha)|\,,\qquad|E(\alpha^{+})|=|E(\alpha)|+1\,.$

From this we can check that $n^{-k}Z_{\alpha^{+}}$ is still combinatorially
negligible.

In a term $\beta$ corresponding to an intersection between the new root and a
vertex of $\alpha$,

$|V(\beta)|=|V(\alpha)|\,,\qquad|I(\beta)|\leq|I(\alpha)|+1\,,\qquad|E(\beta)|=|E(\alpha)|+1\,.$

The second inequality follows from the observation that the only vertices from
$\alpha$ whose neighborhood structure can be affected by the intersection are
the root of $\alpha$ (which does not contribute to $|I(\alpha)|$) and the
intersected vertex. Hence, $n^{-k}Z_{\beta}$ is also combinatorially
negligible.

For (ii), the diagram representation of $Z_{\alpha}\odot Z_{\beta}$ is given
by Lemma B.4. Fix an intersection pattern $P\in{\cal P}(\alpha,\beta)$ that
has $b$ blocks and denote by $\gamma$ the resulting diagram. Then,

$\displaystyle|V(\gamma)|$ $\displaystyle=b+1\,,$ $\displaystyle|E(\gamma)|$
$\displaystyle=|E(\alpha)|+|E(\beta)|\,,$ $\displaystyle|I(\gamma)|$
$\displaystyle\leq|I(\alpha)|+|I(\beta)|+|V(\alpha)|+|V(\beta)|-b-2\,.$

The last inequality is proven by observing that for a non-root vertex that is
neither in $I(\alpha)$ nor $I(\beta)$ to contribute to $I(\gamma)$, it must
intersect another vertex. Moreover, there are at most
$|V(\alpha)|+|V(\beta)|-b-2$ intersected non-root vertices in $\gamma$.

Putting everything together,

$\displaystyle|V(\gamma)|-1-|E(\gamma)|+|I(\gamma)|$ $\displaystyle\leq\;$
$\displaystyle|V(\alpha)|-1-|E(\alpha)|+|I(\alpha)|+|V(\beta)|-1-|E(\beta)|+|I(\beta)|$
$\displaystyle<\;$ $\displaystyle 2(k+l)\,,$

since $n^{-k}Z_{\alpha}$ is combinatorially negligible and
$n^{-\ell}Z_{\beta}$ is at most order 1. This concludes the proof. ∎

Using the 2-labeled edges introduced in Section C.1, we can implement the
removal of hanging double edges. See 4.7

###### Proof.

Starting from the decomposition of Lemma C.4,

$a_{n}Z_{\alpha}=a_{n}Z_{\alpha_{0}}-a_{n}\frac{|V(\alpha)|-1}{n}Z_{\alpha_{0}}+a_{n}Z_{\alpha_{2}}\,,$

we claim that the first term is combinatorially order 1, and the second and
third terms are combinatorially negligible. Comparing $\alpha_{0}$ to
$\alpha$, two edges and one vertex in $I(\alpha)$ are removed. This does not
change the combinatorial order. The second term scales down by $n$ and this
becomes negligible (by assumption $|V(\alpha)|$ is constant). In the third
term, $\left\lvert I(\alpha_{2})\right\rvert<\left\lvert
I(\alpha)\right\rvert$ to take into account the hanging vertex, while
$|V(\alpha)|=|V(\alpha_{2})|$ and $|E(\alpha)|=|E(\alpha_{2})|$ remain
unchanged, making the term negligible. We remind the reader that
$|E(\alpha)|=|E(\alpha_{2})|$ because $|E(\alpha_{2})|$ counts 2-labeled edges
twice. ∎

Definition 4.3 includes the coefficient $a_{n}$ in the definition in order to
incorporate factors of $\frac{1}{n}$ on some error terms such as those in the
proof above.

###  C.3 Scalar diagrams

We now collect the properties of scalar diagrams (Definition 4.8) which
naturally generalize those of vector diagrams. We omit the proofs of the
results in this section, as they are direct modifications of their vector
analogs.

First, the scalar diagrams are an orthogonal basis for scalar functions of
$A$.

######  Lemma C.6.

For any proper $\alpha\in{\cal A}_{\textnormal{scalar}}$:

  * •

For any proper $\beta\in{\cal A}_{\textnormal{scalar}}$ such that
$\beta\neq\alpha$,
$\operatorname*{\mathbb{E}}\left[Z_{\alpha}Z_{\beta}\right]=0$.

  * •

$\operatorname*{\mathbb{E}}\left[Z_{\alpha}\right]=0$ if $\alpha$ is not a
singleton.

  * •

The second moment of $Z_{\alpha}$ is

$\displaystyle\operatorname*{\mathbb{E}}\left[Z_{\alpha}^{2}\right]$
$\displaystyle\underset{\phantom{n\to\infty}}{=}\left\lvert\operatorname{Aut}(\alpha)\right\rvert\cdot\frac{n(n-1)\cdots(n-|V(\alpha)|+1)}{n^{|E(\alpha)|}}$
$\displaystyle\underset{n\to\infty}{=}\left\lvert\operatorname{Aut}(\alpha)\right\rvert\cdot
n^{|V(\alpha)|-|E(\alpha)|}(1+o(1))\,,$

where the last estimate holds whenever $|V(\alpha)|=o(\sqrt{n})$.

###### Proof.

Analogous to Lemma A.1 and Lemma A.2. ∎

When scalar and vector diagrams are multiplied together, the result can be
expressed in terms of diagrams by extending the notion of intersection
patterns ${\cal P}(\alpha_{1},\dots,\alpha_{k})$ (Definition B.2) and
intersection diagrams (Definition B.3) to allow scalar and vector diagrams
simultaneously. The “unintersected” diagram consists of adding all the scalar
diagrams as floating components to the vector diagrams, which are put at the
same root. The intersection patterns are partitions of this vertex set such
that no two vertices from the same diagram are matched.

######  Lemma C.7.

Let $\alpha_{1},\dots,\alpha_{k}$ be either scalar or vector diagrams. Then

$Z_{\alpha_{1}}\cdots Z_{\alpha_{k}}=\sum_{P\in{\cal
P}(\alpha_{1},\dots,\alpha_{k})}Z_{\alpha_{P}}\,,$

where the product is componentwise for the vector diagrams.

###### Proof.

Analogous to Lemma B.4. ∎

We define $I(\alpha)$ for scalar diagrams exactly as in Definition 4.1.

######  Lemma C.8.

Let $q\in\mathbb{N},\alpha\in{\cal A}_{\textnormal{scalar}},$ and $i\in[n]$.
Then,

$\left\lvert\operatorname*{\mathbb{E}}\left[Z_{\alpha}^{q}\right]\right\rvert\leq
M_{q|E(\alpha)|}2^{q|E(\alpha)|}(q\left\lvert
V(\alpha)\right\rvert)^{q|V(\alpha)|}\cdot
n^{\frac{q}{2}\left(|V(\alpha)|-|E(\alpha)|+|I(\alpha)|\right)}\,,$

where $M_{k}$ is defined as in Lemma C.5. When $q$ and $|V(\alpha)|$ are
$O(1)$, this reduces to

$\left\lvert\operatorname*{\mathbb{E}}\left[Z_{\alpha}^{q}\right]\right\rvert\leq
O\left(n^{\frac{q}{2}\left(|V(\alpha)|-|E(\alpha)|+|I(\alpha)|\right)}\right)\,.$

###### Proof.

Analogous to Lemma C.5. ∎

######  Definition C.9 (Combinatorially negligible and order 1 scalar).

Let $(a_{n})_{n\in\mathbb{N}}$ be a sequence of real-valued coefficients with
$a_{n}=\Theta(n^{-k})$, where $k\geq 0$ is such that $2k\in\mathbb{Z}$. Let
$\alpha\in{\cal A}_{\textnormal{scalar}}$ be a scalar diagram.

  * •

We say that $a_{n}Z_{\alpha}$ is combinatorially negligible if

$|V(\alpha)|-|E(\alpha)|+|I(\alpha)|\leq 2k-1\,.$

  * •

We say that $a_{n}Z_{\alpha}$ has combinatorial order 1 if

$|V(\alpha)|-|E(\alpha)|+|I(\alpha)|=2k\,.$

We define $\,\overset{\infty}{=}\,$ for scalar diagram expressions exactly as
in Definition 4.4.

######  Lemma C.10.

Let $x$ and $y$ be scalar diagram expressions with
$x\,\overset{\infty}{=}\,y$. Then
$\left|x-y\right|\overset{a.s.}{\longrightarrow}0$.

###### Proof.

Analogous to Lemma 4.5. ∎

######  Lemma C.11.

Let $a_{n}Z_{\alpha}$ be a combinatorially negligible scalar term. Let
$b_{n}Z_{\beta}$ be any scalar or vector term of combinatorial order at most
$1$. Then all terms in the product $a_{n}b_{n}Z_{\alpha}Z_{\beta}$ are
combinatorially negligible.

###### Proof.

Analogous to Lemma 4.6. ∎

In Lemma 4.10, we characterized the connected vector diagrams which are
combinatorially order 1. We now similarly characterize the order 1 scalar
diagrams.

######  Lemma C.12.

Let $\alpha\in{\cal A}_{\textnormal{scalar}}$ be a scalar diagram with $c$
connected components, $c_{I}$ of which contain only vertices in $I(\alpha)$.
Then $n^{-(c+c_{I})/2}Z_{\alpha}$ is combinatorially negligible or
combinatorially order 1, and it is combinatorially order 1 if and only if the
following conditions hold simultaneously:

  1. (i)

Every multiedge has multiplicity 1 or 2.

  2. (ii)

There are no cycles.

  3. (iii)

In each component, the subgraph of multiplicity 1 edges is empty or a
connected graph (i.e. the multiplicity 2 edges consist of hanging trees)

  4. (iv)

There are no self-loops or 2-labeled edges (Section C.1).

###### Proof.

We proceed as in the proof of Lemma 4.10. In each connected component $C$
containing at least one vertex $s\in V(\alpha)\setminus I(\alpha)$, we run a
breadth-first search from $s$, assigning the multiedges used to explore a
vertex to that vertex. This assigns at least one edge to every vertex in
$C\setminus\\{s\\}$, and at least two edges to every vertex in $I(\alpha)\cap
C$. This encoding argument shows that

$\displaystyle 2\left\lvert I(\alpha)\cap
C\right\rvert+\left\lvert(V(\alpha)\setminus I(\alpha))\cap
C\right\rvert-1\leq\left\lvert E(C)\right\rvert\,,$ (12)

where $E(C)$ denotes the set of edges in the connected component $C$.

In each connected component $C$ composed only of vertices in $I(\alpha)$, we
run a breadth-first search from an arbitrary vertex, and obtain

$\displaystyle 2(\left\lvert I(\alpha)\cap C\right\rvert-1)=\left\lvert
V(\alpha)\cap C\right\rvert+\left\lvert I(\alpha)\cap
C\right\rvert-2\,\leq\left\lvert E(C)\right\rvert\,.$ (13)

Summing Eq. 12 and Eq. 13 over all connected components, we obtain

$\left\lvert V(\alpha)\right\rvert-\left\lvert
E(\alpha)\right\rvert+\left\lvert
I(\alpha)\right\rvert\leq(c-c_{I})+2c_{I}=c+c_{I}\,.$

This shows that $n^{-(c+c_{I})/2}Z_{\alpha}$ is combinatorially negligible or
combinatorially order 1, and it is combinatorially order 1 if and only if
equality holds in the argument. This happens if and only if there is no cycle,
multiplicity $\raisebox{1.0pt}{$\scriptstyle>$}2$ edges, self-loops, or
2-labeled edges anywhere; and if the graph induced by the multiplicity 1
multiedges is connected. ∎

With this result in hand, we can now characterize the order-1 vector diagrams
with several connected components:

######  Corollary C.13.

Let $\alpha\in{\cal A}$ be a vector diagram with $c$ floating components,
$c_{I}$ of which consist only of vertices in $I(\alpha)$. Then
$n^{-(c+c_{I})/2}Z_{\alpha}$ is combinatorially order 1 if and only if both
the floating components (viewed as one scalar diagram) scaled by
$n^{-(c+c_{I})/2}$ and the component of the root are combinatorially order 1.

###### Proof.

Definition 4.3 sums across the root and floating components, so we may apply
both Lemma 4.10 and Lemma C.12. ∎

###  C.4 Classification of diagrams

######  Lemma C.14.

For all $\sigma\in{\cal S}$ and $i\in[n]$,
$Z_{\sigma,i}\overset{d}{\longrightarrow}{\cal
N}(0,\left\lvert\operatorname{Aut}(\sigma)\right\rvert)$. Similarly, for all
$\tau\in{\cal T}_{\textnormal{scalar}}$,
$n^{-\frac{1}{2}}Z_{\tau}\overset{d}{\longrightarrow}{\cal
N}(0,\left\lvert\operatorname{Aut}(\tau)\right\rvert)$.

###### Proof.

We prove that the moments
$\operatorname*{\mathbb{E}}\left[Z_{\sigma,i}^{q}\right]$ match the Gaussian
moments and use Lemma 2.3.

Let $q\in\mathbb{N}$ be a constant independent of $n$. First, we expand the
product $Z_{\sigma,i}^{q}$ in the diagram basis using Lemma B.4. Using Lemma
4.10, the only combinatorially order 1 terms occur when there are no cycles,
all multiedges have multiplicity 1 or 2, and the multiplicity 2 edges form
hanging trees. Any term with an edge of multiplicity 1 disappears when we take
the expectation $\operatorname*{\mathbb{E}}\left[Z_{\sigma,i}^{q}\right]$,
while the diagrams which are entirely hanging trees are equal to  up to
combinatorially negligible terms (Lemma 4.7). Further,  has expectation 1, and
by Lemma C.5 each of the combinatorially negligible terms has expectation
$O(n^{-1/2})$. Thus, $\operatorname*{\mathbb{E}}\left[Z_{\sigma,i}^{q}\right]$
equals the number of ways to create hanging trees of double edges, up to a
term that converges to 0 as $n\to\infty$.

For each of the $q$ copies of $\sigma$, the single edge incident to the root
must be paired with another such edge. This extends to an automorphism of the
entire subtree. In conclusion,
$\operatorname*{\mathbb{E}}\left[Z_{\sigma,i}^{q}\right]$ converges to
$\left\lvert\operatorname{Aut}(\sigma)\right\rvert^{q/2}$ times the number of
perfect matchings on $q$ objects, and we conclude by Lemma 2.4 and Lemma 2.3.
The proof for the scalar case is analogous. ∎

######  Lemma C.15.

If $\tau\in{\cal T}$ consists of $d_{\sigma}$ copies of the subtrees
$\sigma\in{\cal S}$, then

$Z_{\tau}\,\overset{\infty}{=}\,\prod_{\sigma\in{\cal
S}}h_{d_{\sigma}}(Z_{\sigma};\left\lvert\operatorname{Aut}(\sigma)\right\rvert)\,.$

For $\rho\in{\cal F}_{\textnormal{scalar}}$ with $c$ components and consisting
of $d_{\tau}$ copies of each tree $\tau\in{\cal T}_{\textnormal{scalar}}$,

$n^{-\frac{c}{2}}Z_{\rho}\,\overset{\infty}{=}\,\prod_{\tau\in{\cal
T}_{\textnormal{scalar}}}h_{d_{\tau}}\left(n^{-\frac{1}{2}}Z_{\tau};\left\lvert\operatorname{Aut}(\tau)\right\rvert\right)\,.$

###### Proof.

We first expand
$h_{d}(Z_{\sigma};\left\lvert\operatorname{Aut}(\sigma)\right\rvert)$ in the
diagram basis using Lemma B.4 and identify the dominant terms, i.e. those
which are combinatorially order 1. As in the proof of Lemma C.14, the
combinatorially order 1 terms in each monomial $Z_{\sigma,i}^{k}$ consist of
pairing up copies of the tree $\sigma$:

$Z_{\sigma}^{k}\,\overset{\infty}{=}\,\sum_{M\in{\cal
M}(k)}\left\lvert\operatorname{Aut}(\sigma)\right\rvert^{|M|}Z_{k-2|M|\text{
copies of }\sigma}\,,$

where ${\cal M}(k)$ is the set of partial matchings on $k$ objects. Now we use
the combinatorial interpretation of Hermite polynomials (Lemma 2.5),

$\displaystyle
h_{d}(Z_{\sigma};\left\lvert\operatorname{Aut}(\sigma)\right\rvert)$
$\displaystyle=\sum_{N\in{\cal
M}(d)}(-1)^{|N|}\left\lvert\operatorname{Aut}(\sigma)\right\rvert^{|N|}Z_{\sigma}^{d-2|N|}$
$\displaystyle\,\overset{\infty}{=}\,\sum_{N\in{\cal
M}(d)}(-1)^{|N|}\left\lvert\operatorname{Aut}(\sigma)\right\rvert^{|N|}\sum_{M\in{\cal
M}(d-2|N|)}\left\lvert\operatorname{Aut}(\sigma)\right\rvert^{|M|}Z_{d-2|N|-2|M|\text{
copies of }\sigma}$ $\displaystyle=\sum_{M^{\prime}\in{\cal
M}(d)}\left\lvert\operatorname{Aut}(\sigma)\right\rvert^{|M^{\prime}|}Z_{d-2|M^{\prime}|\text{
copies of }\sigma}\sum_{N\subseteq M^{\prime}}(-1)^{|N|}$
$\displaystyle=Z_{d\text{ copies of }\sigma}\,.$

This completes the argument when $\tau$ consists of several copies of a single
$\sigma\in{\cal S}$. If $\sigma,\sigma^{\prime}\in{\cal S}$ are distinct,
using again Lemma B.4 and Lemma 4.10, we can check that

$Z_{\text{$d$ copies of $\sigma$}}\odot Z_{\text{$d^{\prime}$ copies of
$\sigma^{\prime}$}}\,\overset{\infty}{=}\,Z_{\text{$d$ copies of $\sigma$ and
$d^{\prime}$ copies of $\sigma^{\prime}$}}\,.$

The proof then follows by applying these arguments inductively, and extends
analogously to scalar diagrams. ∎

######  Lemma C.16.

Let $\alpha\in{\cal F}$ have $c$ floating components. Let
$\alpha_{\vbox{\hbox{\includegraphics[height=4.52083pt]{diagram-
analysis/images/singleton.png}}}}$ be the component of the root and
$\alpha_{\textnormal{float}}$ be the floating components. Then
$n^{-\frac{c}{2}}Z_{\alpha}\,\overset{\infty}{=}\,n^{-\frac{c}{2}}Z_{\alpha_{\textnormal{float}}}Z_{\alpha_{\vbox{\hbox{\includegraphics[height=3.22916pt]{diagram-
analysis/images/singleton.png}}}}}$.

###### Proof.

The product
$n^{-\frac{c}{2}}Z_{\alpha_{\textnormal{float}}}Z_{\alpha_{\vbox{\hbox{\includegraphics[height=3.22916pt]{diagram-
analysis/images/singleton.png}}}}}$ can be expanded in the diagram basis using
Lemma C.7. We claim that the only non combinatorially negligible diagram is
the one without intersections, which equals $n^{-\frac{c}{2}}Z_{\alpha}$. When
an intersection occurs, it can only be between the root component and a
floating component. The new component of the root is at most combinatorially
order 1 (this is a property of all connected vector diagrams, Lemma 4.10), so
there is an “extra” factor of $\frac{1}{\sqrt{n}}$ from the lost component
which makes the intersection term negligible. ∎

######  Lemma C.17.

$\left\\{Z_{\sigma,i}:\sigma\in{\cal
S},i\in[n]\right\\}\cup\left\\{n^{-\frac{1}{2}}Z_{\tau}:\tau\in{\cal
T}_{\textnormal{scalar}}\right\\}$ are asymptotically independent.

###### Proof.

Fix constants $q,r\in\mathbb{N}$. We proceed by computing the moment of a set
of diagrams $\sigma_{1},\dots,\sigma_{q}\in{\cal S}$ rooted at
$i_{1},\dots,i_{q}\in[n]$ and $\tau_{1},\dots,\tau_{r}\in{\cal
T}_{\textnormal{scalar}}$:

$\displaystyle\operatorname*{\mathbb{E}}\left[\prod_{p=1}^{q}Z_{\sigma_{p},i_{p}}\prod_{p=1}^{r}n^{-\frac{1}{2}}Z_{\tau_{p}}\right]\,.$
(14)

Let $|V|=\sum_{p=1}^{q}|V(\sigma_{p})|+\sum_{p=1}^{r}|V(\tau_{p})|$ and
$|E|=\sum_{p=1}^{q}|E(\sigma_{p})|+\sum_{p=1}^{r}|E(\tau_{p})|$. Let
$q_{\textnormal{distinct}}$ be the number of distinct roots, i.e. the number
of distinct elements in $\\{i_{1},\dots,i_{q}\\}$.

Expanding Eq. 14 gives a sum over embeddings of the diagrams. We will prove
that the dominant terms factor across the distinct $(\sigma_{p},i_{p})$ and
$\tau_{p}$; they correspond to pairing up isomorphic $\sigma_{p}$ at each
distinct root and isomorphic $\tau_{p}$.

Each nonzero term in the expansion of Eq. 14 equals $n^{-(|E|+r)/2}$ (when
every edge appears exactly twice) or $O(n^{-(|E|+r)/2})$ (in general) by 2.1.
We partition the summation based on the intersection pattern as in Definition
B.2. For a given intersection pattern, letting $I$ be the union of the images
of the embeddings, the number of terms with this pattern is $(1-o(1))\cdot
n^{|I|-q_{\textnormal{distinct}}}$ because the $q_{\textnormal{distinct}}$
root vertices are fixed. In an embedding with nonzero expectation, every edge
appears at least twice, so every non-root vertex is in at least two
embeddings. Applying this bound to all of the non-root vertices in $I$,

$|I|\leq q_{\textnormal{distinct}}+\frac{|V|-q}{2}\,.$

Multiplying the value of each term times the number of terms, the total
contribution of this intersection pattern is

$n^{|I|-q_{\textnormal{distinct}}-\frac{|E|+r}{2}}\leq
n^{\frac{1}{2}\left(|V|-q-|E|-r\right)}\,.$

Since the individual diagrams are connected, the exponent is nonpositive. The
dominant terms occur exactly when $|I|=q_{\textnormal{distinct}}+(|V|-q)/2$,
equivalently all of the non-root vertices intersect exactly one other non-root
vertex. Each edge must occur at least twice, and this condition implies that
each edge occurs exactly twice in the dominant terms.

We claim that the only way that each edge and vertex can be in exactly two
embeddings is if isomorphic $\sigma_{p}$ and $\tau_{p}$ are paired. Indeed, by
connectivity of $\sigma_{p}$ and $\tau_{p}$, sharing one edge extends to an
isomorphism. Furthermore, because non-root vertices must intersect other non-
root vertices in the dominant terms, we have that no pairs can be made between
$\sigma_{p}$ and $\tau_{p^{\prime}}$, or between $\sigma_{p}$ and
$\sigma_{p^{\prime}}$ which have distinct roots. ∎

Theorem 4.11 follows from Lemma C.14, Lemma C.15, Lemma C.16, and Lemma C.17.

###  C.5 Handling empirical expectations

Empirical expectations are highly concentrated and the following lemma
confirms this. Note that the empirical expectations in the Onsager correction
for AMP (Section 5.3) will create floating components in the diagrams of the
algorithmic state, but all such diagrams will be negligible.

See 4.22

###### Proof.

The effect of summing a vector diagram $Z_{\alpha}=(Z_{\alpha,i})_{i\in[n]}$
over $i$ is to unroot $\alpha$, converting it to a scalar diagram. We prove
this operation makes every diagram combinatorially negligible, except for the
constant term. For $k\geq 0$ and a vector diagram $\alpha\in{\cal A}$:

  1. (i)

If $a_{n}Z_{\alpha}$ is combinatorially negligible, then
$\frac{a_{n}}{n}\sum_{i=1}^{n}Z_{\alpha,i}$ is a combinatorially negligible
scalar term.

  2. (ii)

If $a_{n}Z_{\alpha}$ has combinatorial order 1, and the root of $\alpha$ is
incident to at least one edge of multiplicity 1, then
$\frac{a_{n}}{n}\sum_{i=1}^{n}Z_{\alpha,i}$ is a combinatorially negligible
scalar term.

Unrooting a vector diagram does not change the number of vertices nor the
number of edges. During this operation, the number of vertices in $I(\alpha)$
stays the same if the root is adjacent to an edge of multiplicity 1; otherwise
it increases by at most 1. We readily check from the definition that the extra
$\frac{1}{n}$ makes the resulting scalar terms combinatorially negligible.

Now let $\widehat{x}$ be the tree approximation to $x$. The difference
$x-\widehat{x}$ consists of combinatorially negligible terms which stay
negligible by part (i) above. The trees in ${\cal T}$ become negligible by
part (ii) above with the exception of the singleton tree which becomes $1$.
The singleton has coefficient
$\operatorname*{\mathbb{E}}[\widehat{x}_{1}]=\operatorname*{\mathbb{E}}[X]$
since the other trees are mean-zero. ∎

##  Appendix D High-degree tree diagrams are not Gaussian

Care must be taken when studying the diagrams of superconstant size. In this
section we compute that the star-shaped diagram with $\log n$ leaves and the
root at a leaf is not Gaussian (its fourth moment is significantly larger than
the square of its second moment).202020Similarly, adding an edge between two
of the leaves creates a cyclic diagram with negligible variance but non-
negligible fourth moment. This diagram appears after only $T=O(\log\log n)$
iterations in the recursion

$x_{1}=A\vec{1}\qquad x_{t+1}=(x_{t})^{2}\qquad x_{T+1}=Ax_{T}\,.$

However, we expect that this diagram does not contribute significantly to
nicer GFOMs that strictly alternate between multiplication by $A$ and
constant-degree componentwise operations.

Fixing $d$, let $\gamma$ denote ($d$-star graph)+. We compute that
$\operatorname*{\mathbb{E}}\left[Z_{\gamma,1}^{4}\right]\gg\operatorname*{\mathbb{E}}\left[Z_{\gamma,1}^{2}\right]^{2}$
when $d\approx\log n$. By Lemma A.2, the variance is

$\operatorname*{\mathbb{E}}\left[Z_{\gamma,1}^{2}\right]=(1+o(1))\left\lvert\operatorname{Aut}(\gamma)\right\rvert=(1+o(1))d!\,.$

When computing the fourth moment
$\operatorname*{\mathbb{E}}\left[Z_{\gamma,1}^{4}\right]$ for constant $d$,
the terms that are dominant consist of (1) a perfect matching between the four
edges incident to the root, (2) perfect matchings between their $d$ children.
There are $3(d!)^{2}$ such terms, recovering the fourth moment of a Gaussian
with variance $d!$.

For $d=\log n$, another type of term becomes dominant. These are the terms
where all four edges incident to the root are equal, then we have a perfect
matching on $4d$ objects divided into four groups of size $d$ such that no two
objects from the same group are matched. Denote the latter set of matchings by
${\cal M}(d,d,d,d)$.

######  Lemma D.1.

Up to a multiplicative $\operatorname{poly}(d)$ factor, $|{\cal
M}(d,d,d,d)|\gtrsim 3^{d}(d!)^{2}$.

These terms come with a $\frac{1}{n}$ factor due to the multiplicity 4 edge.
When $d=\Omega(\log n)$, the extra factor of $3^{d}$ overpowers the
$\frac{1}{n}$ and makes the fourth moment much larger than the the squared
variance $(d!)^{2}$.

###### Proof of Lemma D.1..

We establish a recursion. There are $(3d)(3d-1)\cdots(2d+1)$ ways to match up
the objects in the first group, which can be partitioned in $O(d^{2})$ ways
depending on how many objects in each other group are matched. We will recurse
on the “maximum-entropy” case in which the first group matches $d/3$ elements
from each other group, using the following claim.

######  Claim D.2.

Let $d,k\in\mathbb{N}$ such that $\frac{d}{k-1}$ is an integer. Counting the
matchings between $d$ objects and a subset of $(k-1)d$ objects in $k-1$
groups, as a function of the number of objects matched in each group, the
number of matchings is maximized when there are $\frac{d}{k-1}$ matched
elements per group.

###### Proof of D.2..

Letting $n_{1},\dots,n_{k-1}$ be the number of matched elements per group, we
may directly compute this number as

$\prod_{i=1}^{k-1}(d)_{n_{i}}$

where $(d)_{k}=d(d-1)\cdots(d-k+1)$ is the falling factorial. When $n_{i}$ and
$n_{j}$ are replaced by $n_{i}-1$ and $n_{j}+1$, the ratio of new to old
values is

$\displaystyle\frac{d-n_{j}}{d-n_{i}+1}$

which is at least 1 if $n_{i}\geq n_{j}+1$. Hence the $n_{i}$ are equal at the
maximum. ∎

Using D.2, up to a factor of $O(d^{2})$,

$\displaystyle|{\cal M}(d,d,d,d)|$
$\displaystyle\gtrsim(3d)(3d-1)\cdots(2d+1)|{\cal M}(2d/3,2d/3,2d/3)|$
$\displaystyle\asymp\left(\frac{3d}{e}\right)^{3d}\left(\frac{e}{2d}\right)^{2d}|{\cal
M}(2d/3,2d/3,2d/3)|$

where the second equality holds up to a $\operatorname{poly}(d)$ factor by
Stirling’s approximation:

######  Fact D.3 (Stirling’s approximation).

Up to a multiplicative $\operatorname{poly}(d)$ factor,
$d!\asymp\left(\frac{d}{e}\right)^{d}$.

Recursing via the same principle,

$\displaystyle|{\cal M}(2d/3,2d/3,2d/3)|$
$\displaystyle\gtrsim(4d/3)(4d/3-1)\cdots(2d/3+1)|{\cal M}(d/3,d/3)|$
$\displaystyle=(4d/3)(4d/3-1)\cdots(2d/3+1)(d/3)!$
$\displaystyle\asymp\left(\frac{4d}{3e}\right)^{4d/3}\left(\frac{3e}{2d}\right)^{2d/3}\left(\frac{d}{3e}\right)^{d/3}$
(D.3)

In total,

$|{\cal M}(d,d,d,d)|\gtrsim 3^{d}\left(\frac{d}{e}\right)^{2d}\,.\qed$