Complexity and the Hilbert space dimension of 3D gravity Vijay Balasubramanian, Rathindra Nath Das, Johanna Erdmenger, Jonathan Karl, Herman Verlinde Abstract A central problem in formulating a theory of quantum gravity is to determine the size and structure of the Hilbert space of black holes. Here we use a quantum dynamical Krylov complexity approach to calculate the Hilbert space dimension of a black hole in 2+1-dimensional Anti-de Sitter space. We achieve this by obtaining the spread of an initial thermofield double state over the Krylov basis. The associated Lanczos coefficients match those for chaotic motion on the S ​ L ​ ( 2 , ℝ ) SL(2,\mathbb{R}) group. By including non-perturbative effects in the path integral, which computes coarse-grained ensemble averages, we find that the complexity saturates at late times. The saturation value is given by the exponential of the Bekenstein-Hawking entropy. Our results introduce a new way to compute the Hilbert space dimension of complex interacting systems from the saturating value of spread complexity. 1 1 footnotetext: See Supplemental Material for a derivation of the Lanczos coefficients following from the MWK density of states ( 13 ), a derivation of ( ), and a derivation of the double pole structure in ( 23 ) 2 2 footnotetext: We denote averaged quantities with an overline \bar{.}\ 3 3 footnotetext: For a theory with a discrete spectrum we have \rho(E)=\sum_{i}\delta(E_{i}-E) , where the E_{i} are the energy eigenvalues 4 4 footnotetext: see 39 ; 40 for a definition of the microcanonical TFD state Introduction— An outstanding problem in quantum gravity is to understand the size and structure of Hilbert spaces describing different gravitating objects. One way to determine the Hilbert space dimension is to work out the number of vectors in a complete, orthonormal basis. This is the procedure used in 49 to explain the entropy of certain extremal, supersymmetric black holes in string theory. A second approach is to consider any sufficiently large collection of distinct vectors. The rank of the Gram matrix of overlaps of these vectors equals the Hilbert space dimension. This is the procedure used in 7 ; 23 ; 34 ; 13 ; 6 ; 12 ; 11 to account for the entropy of general black holes. The latter approach employed the Euclidean gravity path integral and its saddlepoint approximation, assumed to be well defined by some high energy completion, perhaps by a string theory. There is a third approach which applies to chaotic, or at least sufficiently ergodic, systems: to compute the dimension of the span of all states explored by a generic initial vector as it evolves over time. We apply this third approach to asymptotically AdS 3 gravity by computing spread complexity 4 of evolving thermofield double (TFD) states describing near-extremal eternal black holes. Spread complexity is computed from the support of quantum states on the Krylov basis, constructed to span the time evolution. Our Krylov basis will be related to the generalized TFD states in 34 ; 13 . In chaotic theories, generic initial states are eventually completely delocalized in the Krylov basis 4 ; 10 ; 27 , so that measuring the spread reveals the dimension of the accessible part of the Hilbert space. We work with thermal states of 3d gravity with support on the entire infinite dimensional energy eigenspace, but the exponential suppression of high energies effectively restricts dynamics to a microcanonical band as in statistical mechanics. We start with the return amplitude, i.e., the probability for a state to remain unchanged, processed into hopping amplitudes, known as Lanczos coefficients, between a chain of Krylov basis states 4 . For initial TFD states the return amplitude is an analytically continued partition sum determined by the density of states. Spread complexity can then be written in terms of the spectral density and certain orthogonal polynomials in the energy built from the Lanczos coefficients 41 ; 21 ; 5 . Identifying these polynomials as those of a random matrix ensemble, our method introduces a new physical notion of the eigenvalue statistics of the Hamiltonian by means of a random matrix theory (RMT) with matrix potential e^{-V(E)}=|\phi_{0}(E)|^{2}\rho(E) specified by the reference state \phi_{0}(E) and microscopic spectral density \rho(E) . We apply this procedure to 3d gravity in a near-extremal limit, where the spectral density \rho(E) is known 35 ; 32 ; 37 . This goes beyond the well-understood example of JT gravity in 1+1 dimensions 31 ; 8 ; 39 . We show that the Lanczos coefficients match those of quantum particles moving on the SL(2,\mathbb{R}) manifold, with the associated Laguerre polynomials leading to monotonically increasing spread complexity. The spectral density \rho(E) in 35 ; 32 ; 37 was derived from the Euclidean gravity path integral (GPI); many studies, e.g., 46 ; 36 ; 7 and 24 for 3d gravity, suggest that this \rho(E) should be interpreted as a coarse-grained average over an underlying ensemble. As such, products like \rho(E)\rho(E^{\prime}) in the formula for spread complexity should be understood as spectral correlators in this ensemble rather than as simple products. We assume that these correlators follow random matrix universality, as suggested by effects of wormholes contributing to the product of partition sums in 2d and 3d gravity 37 ; 24 . The same wormholes imply a finite-dimensional black hole Hilbert space spanned by time-shifted TFD states 34 ; 13 . Including this effect, spread complexity saturates at a value exponential in the Bekenstein-Hawking entropy, i.e., the black hole Hilbert space dimension. Orthogonal polynomials and complexity— The idea behind spread complexity is to quantify the spread of a wavefunction in the Hilbert space as it evolves over time 4 ; 42 ; 3 ; 45 . Consider an initial state \left|\psi_{0}\right\rangle , evolving as \left|\psi(t)\right\rangle=e^{-itH}\left|\psi_{0}\right\rangle\equiv\sum\limits_{n}\psi_{n}(t)\left|K_{n}\right\rangle\,, (1) where the Krylov basis \{\left|K_{n}\right\rangle\,|\,n\in\mathbb{N}\} is obtained recursively from the set \{H^{n}\left|\psi_{0}\right\rangle\,|\,n\in\mathbb{N}\} through an orthogonalization procedure. By construction, the basis vectors satisfy a recursion relation H\left|K_{n}\right\rangle=a_{n}\left|K_{n}\right\rangle+b_{n}\left|K_{n-1}\right\rangle+b_{n+1}\left|K_{n+1}\right\rangle\,, (2) where a_{n} and b_{n} are the Lanczos coefficients. Since the \left|K_{n}\right\rangle are orthonormal, we obtain the coefficients \psi_{n}(t) of the state ( 1 ) in the Krylov basis as \psi_{n}(t)=\left\langle K_{n}|\psi(t)\right\rangle . The spread complexity is then defined as C_{S}(t)=\sum_{n}n|\psi_{n}(t)|^{2}\,. (3) We can also expand ( 1 ) in the energy basis as \left|\psi(t)\right\rangle=\int dE\,\rho(E)\,\phi_{0}(E)e^{-iEt}\left|E\right\rangle\,, (4) where \rho(E) is the spectral density and \phi_{0}(E)=\left\langle E|\psi_{0}\right\rangle . For a theory with a discrete spectrum \rho(E)=\sum_{i}\delta(E_{i}-E) , where the E_{i} are energy eigenvalues; we are working in a thermodynamic limit and approximating the spectral density as continuous. The energy eigenstates are normalized such that \left\langle E|E^{\prime}\right\rangle=\frac{\delta(E-E^{\prime})}{\rho(E)}\,,\quad\mathds{1}=\int dE\rho(E)\left|E\right\rangle\left\langle E\right|\,. (5) Projecting ( 4 ) onto |K_{n}\rangle gives \begin{split}\psi_{n}(t)=\int dE\,\rho(E)\,\phi_{0}(E)e^{-iEt}c^{*}_{n}(E)\,,\end{split} (6) where c_{n}(E)\equiv\left\langle E|K_{n}\right\rangle . It follows from ( 2 ) that the c_{n}(E) also satisfy a recursion relation ( A.1 ) with initial conditions c_{-1}(E)=0 and c_{0}(E)=\phi_{0}(E) (also see 2 ; 1 ). We show in the appendix that the solution to this recursion relation takes the form c_{n}(E)=\phi_{0}(E)\,h_{n}(E)\,, (7) where h_{n}(E) is a polynomial of degree n with coefficients determined purely from the Lanczos coefficients ( A.5 ). It follows from the orthonormality of the Krylov basis that \begin{split}\int dE\,\rho(E)\left|\phi_{0}(E)\right|^{2}\,h_{n}^{*}(E)h_{m}(E)=\delta_{nm}\,,\end{split} (8) which we obtain by inserting the identity ( 5 ) into the overlap \left\langle K_{n}|K_{m}\right\rangle . Therefore, the polynomials h_{n}(E) are orthogonal with respect to the measure \rho(E)\left|\phi_{0}(E)\right|^{2} . Moreover, from ( 6 ) and ( 7 ) we determine spread complexity ( 3 ) in terms of these polynomials as 41 ; 21 ; 5 \begin{split}C_{S}(t)&=\int dE\,dE^{\prime}\,e^{-i(E-E^{\prime})t}\,\rho(E^{\prime})\rho(E)\\ &\times\left|\phi_{0}(E)\right|^{2}\left|\phi_{0}(E^{\prime})\right|^{2}\sum_{n}n\,h_{n}(E^{\prime})h_{n}^{*}(E)\,.\end{split} (9) Early time complexity growth.— Now consider an eternal black hole in AdS d+1 . The Hartle-Hawking no-boundary Euclidean path integral constructs a vacuum wavefunction of the thermofield double (TFD) form \left|\text{TFD}(t)\right\rangle=\frac{1}{\sqrt{Z(\beta)}}\int dE\,\rho(E)e^{-\frac{\beta}{2}E}e^{-iEt}\left|E\right\rangle\,\, (10) where Z(\beta) is the canonical partition function Z(\beta)=\int\!dE\,\rho(E)\,e^{-\beta E}\,, (11) and we use the shorthand \left|E\right\rangle\equiv\left|E\right\rangle_{L}\otimes\left|E\right\rangle_{R} , as in 39 ; 40 . The Lanczos coefficients can be obtained from moments of the return amplitude 4 S_{\text{TFD}}(t):=\left\langle\text{TFD}(0)|\text{TFD}(t)\right\rangle=\frac{Z(\beta+it)}{Z(\beta)}\,. (12) In the effective low-energy description, Z is obtained from the gravitational path integral (GPI) over manifolds with boundary S^{1}_{\beta}\times S^{d-1} 30 , which computes a trace over the gravity Hilbert space 11 . For general spacetime dimension this path integral has to be approximated by the leading saddle point. However, for d+1=3 Maloney–Witten–Keller (MWK) evaluated the sum over all classical solutions to Einstein’s equations with torus boundary conditions 35 ; 32 . The torus parameter is \tau=\frac{\theta+i\beta}{2} , where \theta is the periodicity of the spatial circle. \tau is the dual variable to the angular momentum J of the black hole. Close to extremality 29 , i.e. \left|J\right|\gg\frac{L}{G_{N}} and 00\,,\end{cases} (16) which have the same form as for particles on SL(2,\mathbb{R}) 4 a_{n}=\gamma(h+n)+\xi\,,\quad b_{n}=\sigma\sqrt{n(2h+n-1)}\,. (17) The general SL(2,\mathbb{R}) case was worked out in 22 by directly solving ( 2 ) for a highest weight state of scaling dimension h , with an explicit Hamiltonian. One realization, the harmonic oscillator, gives ( 17 ) with h=1/2 4 . Here we find that the partition function of near-extremal 3d gravity leads to ( 17 ) with h=3/4 . The coefficients in ( 16 ) match the SL(2,\mathbb{R}) form in ( 17 ) because the near-extremal limit of 3d gravity has a dimensional reduction to JT gravity with defects 37 . The reduced theory contains a Schwarzian sector with SL(2,\mathbb{R}) symmetry. In the near-extremal limit the energy density of the Schwarzian theory is approximated by \sqrt{E-E_{\star}} , leading to the first term in ( 13 ). On the other hand, from 4 the spread complexity for the Schwarzian theory coincides with the SL(2,\mathbb{R}) model at late times or alternatively in the large C/\beta limit which is the regime where the Schwarzian theory describes JT gravity and C is interpreted as the boundary value of the dilaton. We show in the appendix that for the Lanczos coefficients ( 16 ) the polynomials in ( 7 ) take the form ( A.13 ) h_{n}(E)=\ \sqrt{\frac{\Gamma(\tfrac{3}{2})n!}{\Gamma(n+\tfrac{3}{2})}}L_{n}^{(1/2)}\!\Big(-\beta(E+E_{0}(J))\Big)\,, (18) where L_{n}^{(\alpha)} are the generalized Laguerre polynomials. The polynomials L_{n}^{(\alpha)}(y) are orthogonal with respect to the measure \mu(y)\propto y^{\alpha}e^{-y} . Therefore, ( 18 ) is indeed consistent with ( 8 ), since for the TFD state ( 10 ) we have \phi_{0}(E)\propto e^{-\beta E/2} , and ( 14 ) implies \alpha=1/2 . The generalized Laguerre polynomials were used to calculate complexity in 41 , and for \alpha=1/2 this leads to C_{S}^{\text{MT}}(t)=\frac{3t^{2}}{2\beta^{2}}\,. (19) This agrees with the complexity growth for a particle on SL(2,\mathbb{R}) 4 , after comparing ( 17 ) to ( 16 ) where we observe that \gamma^{2}/4-\sigma^{2}=0 . Complexity saturation from quantum gravity— We expect spread complexity to saturate at late times at a value set by the dimension of the underlying Hilbert space. For black holes we are studying this implies that complexity should saturate at e^{S_{0}} . The reason why ( 19 ) does not saturate is that we obtained it from a continuous energy spectrum ( 14 ) with infinitely many states in any energy band. By contrast the full quantum gravity theory should have a discrete spectrum if the finite black hole entropy has a sensible microscopic interpretation. These considerations suggest that the computations above are only valid for time scales shorter than the inverse of the typical energy spacing t\ll 1/\delta E\sim e^{S_{0}} , and that to go to later times we have to find a way to resolve the discreteness of the spectrum. The continuum spectral density in ( 14 ) was obtained by using the gravitational path integral (GPI), an effective field theory description of the underlying unltraviolet complete theory. By construction, the GPI only contains coarse grained information about the fundamental degrees of freedom, and is believed to compute quantities that act like averages in some underlying ensemble (see, e.g., 46 ; 36 ; 24 ; 14 ; 47 ; 7 ; 26 ). This suggests that the density of states ( 14 ) should be interpreted as an ensemble average that coarse grains a fundamentally discrete spectrum. From this perspective, we cannot simply substitute ( 14 ) into the integral expression for spread complexity ( 9 ). Rather, if we use the GPI to compute the integrand, the \rho(E^{\prime})\rho(E) factor should act like a density-density correlator in the effective ensemble. Thus, if we use the GPI to directly calculate the integrand in the complexity integral, we are effectively computing \begin{split}\overline{C_{S}(t)}&=\int dE\,dE^{\prime}\,e^{-i(E-E^{\prime})t}\,\overline{\rho(E^{\prime})\rho(E)}\\ &\times\left|\phi_{0}(E)\right|^{2}\left|\phi_{0}(E^{\prime})\right|^{2}A(E,E^{\prime})\,,\end{split} (20) where the overbar indicates that the quantity is computed by the GPI, and so acts effectively as an ensemble average. We also introduced the complexity kernel A(E,E^{\prime})=\sum_{n}n\,h_{n}(E^{\prime})h_{n}^{*}(E)\,. (21) The fine grained structure of the spectrum is encoded in the density-density correlator \overline{\rho(E^{\prime})\rho(E)} . This spectral correlator can be computed as an inverse Laplace transform of the two-boundary partition function \overline{Z(\beta^{\prime},\beta)} , where \beta,\beta^{\prime} are the periodicities of the two thermal circles. The leading path integral contribution to this partition function is disconnected 13 , resulting in the factorized form Z(\beta^{\prime})Z(\beta) , leading to spread complexity of the form ( 9 ), which does not saturate. The leading non-perturbative correction to the factorized partition function comes from a Euclidean wormhole that connects the two boundaries. For 3d gravity, this contribution has been calculated in 24 . In the near-extremal limit discussed above ( 13 ) the wormhole contribution has a universal random matrix form 19 , consistent with the fact that the effective dimensionally reduced description has a known random matrix dual in the Gaussian Unitary Ensemble (GUE) universality class 37 . Thus, the spectral correlator in ( 20 ) shows random matrix universality for E\approx E^{\prime} , so that 46 \begin{split}\overline{\rho(E^{\prime})\rho(E)}&\approx\rho(E^{\prime})\rho(E)-\frac{\sin^{2}(\pi\rho(\overline{E})(E^{\prime}-E))}{\pi^{2}(E^{\prime}-E)^{2}}+\dots\,.\end{split} (22) Here \overline{E}=\frac{E+E^{\prime}}{2} and “ \dots ” denotes contributions from contact terms proportional to \delta(E-E^{\prime}) , which lead to a constant offset in the spread complexity ( 20 ) that we can drop. The second term in ( 22 ), arising from the connected wormhole contribution to the path integral is called the sine kernel, and is universal for any matrix model in the GUE universality class 46 . Since ( 22 ) vanishes as E\to E^{\prime} , the universal form of the spectral correlator indicates level repulsion between the energy eigenvalues, a signature of spectral discreteness in the fundamental theory 39 ; 40 . We are now ready to evaluate the complexity integral ( 20 ) – the two key ingredients are the density-density correlator that we just discussed, and the orthogonal polynomials ( 18 ) from which we can explicitly calculate the complexity kernel ( 21 ). Note that we are interested in the late time behavior of ( 20 ), where the integral is dominated by frequencies \omega:=E-E^{\prime} of order 1/t . In this regime the spectral correlator has the form ( 22 ), and we show in the appendix that the kernel ( 21 ) is given by A(E,E^{\prime})\ =\ \frac{\mathcal{C}(\overline{E})}{(E-E^{\prime})^{2}}\,+\,\text{(terms regular in }E-E^{\prime})\,, (23) where \mathcal{C} is a non-zero and smooth function ( A.31 ). We show in the appendix that as E-E^{\prime}\to 0 the spectral correlator ( 22 ) vanishes as (E-E^{\prime})^{2} (see ( A.34 )); so the integrand is regular in \omega=E-E^{\prime} and will thus lead to a finite late time limit of spread complexity. Without the non-perturbative corrections, which result in the sine kernel contribution to the spectral correlator, the double pole in ( 23 ) would have led a late time divergence of complexity as in ( 19 ). Evaluating the \omega integral in the appendix, following 31 , where a similar integral appeared in the context of the wormhole length in JT gravity, we find ( A.35 ) \displaystyle\overline{C_{S}(\hat{t})} \displaystyle= \displaystyle C_{0}+\frac{2\pi^{2}e^{S_{0}}}{3\hat{Z}(\beta)^{2}}\int_{\overline{E}_{\star}(\hat{t})}^{\infty}d\overline{E}\;e^{-2\beta\overline{E}}\;\hat{\rho}(\overline{E})^{3}\;\mathcal{C}(\overline{E}) (24) \displaystyle\qquad\qquad\times\Bigl(1-X(\hat{t};\overline{E})\Bigr)^{3}\, where e^{S_{0}}\hat{\rho}(\overline{E})=\rho(\overline{E}) , e^{S_{0}}\hat{Z}(\beta)=Z(\beta) , and e^{S_{0}}\hat{t}=t . Moreover, X(\hat{t};\bar{E}) and \overline{E}_{\star}(\hat{t}) are defined in ( A.36 ) and ( A.37 ) and C_{0} is a constant. We show in the appendix that for \hat{t}\to\infty the integral in ( 24 ) vanishes. Therefore, we obtain the late-time saturation value of complexity from the constant term in ( 24 ), which we determine in the appendix and find ( A.39 ) C_{0}=e^{S_{0}}\,\frac{A\pi^{3}}{8}\,(2E_{0}(J))^{\frac{3}{2}}e^{4\beta E_{0}(J)}\Gamma\!\Bigl(-\frac{3}{2},\,4\beta E_{0}(J)\Bigr)\,. (25) This saturation relies on random matrix universality ( 22 ) and the double pole in the complexity kernel ( 23 ), similarly to observations in 2 ; 40 motivated by JT gravity and its relation with the double-scaled SYK model 31 ; 39 ; 38 . Our final result ( 25 ) shows that the Hilbert space of 3d gravity near extremality has a finite dimension that is exponential in the black hole entropy S_{0} . Summary and outlook— We used spread complexity to study the structure of the black hole Hilbert space in 3d gravity. For generic initial states of chaotic systems with discrete, bounded spectra, the saturating value of spread complexity is related to the Hilbert space dimension. In the context of gravity, the challenge is that without a complete microscopic theory, we can only compute complexity from the density of states in an effective theory described by the gravitational path integral. As this approach results in a continuous and unbounded spectrum, we find that naively complexity grows for all times, suggesting an infinite dimensional Hilbert space. We overcome this obstacle by extracting information about the discreteness of the spectrum in the microscopic theory from the density-density correlator appearing in the spectral representation of complexity. This correlator can be computed from the effective path integral, which averages over the microscopic details of the fundamental theory. The outcome is saturation of spread complexity at a value exponential in the black hole entropy. There is a conjecture that in holographic theories of gravity, the complexity of evolving TFD states is geometrized, possibly as the volume of distinguished spacelike slices passing through the Einstein-Rosen bridge in the gravitational description 50 ; 48 . Alternative proposals suggest that complexity might be related to other diffeomeorphism invariant quantities 20 ; 15 ; 28 ; 25 . In most of these proposals, the complexity in question was conceived of in terms of a dual field theory. But since, in holography, the field theory state and the quantum gravity state must be dual to each other, we might as well compute complexity directly in the bulk gravity if we are able to do it. The question is what notion of complexity to use. Here we looked at a measure of complexity associated to the spreading quantum state 4 that has found numerous applications. In fact, recently the authors of 33 ; 44 showed that this notion of spread complexity applied to TFD states of the Double-Scaled SYK model 18 ; 17 precisely reproduces the growing classical length of wormholes in the dual 2d Jackiw-Teitelboim gravity. Then by invoking RMT correlations in the Lanczos coefficients, the authors of 9 ; 43 ; 8 showed that the spread complexity saturates at late times, implying large quantum corrections to the classical notion of length. In a complementary approach, the authors of 31 defined a non-perturbative notion of wormhole length directly from the path integral of a class of 2d dilaton gravity theories, including JT gravity with defects, which is a dimensionally reduced description of the near-extremal sector of 3d gravity 37 (also see 39 ; 38 ). The resulting expression for 2d wormhole length is very similar to our result for spread complexity ( 24 ) and only differs in the functional form of the \mathcal{C}(\overline{E}) (compare ( A.31 ) and ( 24 ) to Eqs. 3.10 and 4.6 in 31 ). An explanation for this discrepancy is that the non-perturbative wormhole length in 31 is defined by summing over geodesics in all Euclidean 2d geometries with a single circular boundary, the simplest example being the disc that analytically continues to the Lorentzian black hole. If we define the non-perturbative wormhole length in a similar way for 3d gravity, we have to sum over geometries with a single torus boundary S_{\beta}^{1}\times S^{1} . Some of these lead to the aforementioned 2d geometries after dimensional reduction. However, there are infinitely many 3d geometries which do not have this 2d interpretation. Therefore, the 2d result of 31 will receive corrections, which should lead to our 3d formula ( 24 ). We leave the non-perturbative study of wormhole length in 3d gravity to future work. Acknowledgements. Acknowledgements— We thank Poulami Nandi for collaboration during early stages of this work, as well as Souvik Banerjee, Ben Craps, Gabriele Di Ubaldo, Felix Haehl, Thomas Kögel, Andrew Sontag and Tom Yildirim for useful discussions. RND, JE and JK are supported by Germany’s Excellence Strategy through the Würzburg-Dresden Cluster of Excellence ctd.qmat – Complexity, Topology and Dynamics in Quantum Matter (EXC 2147, project-id 390858490), and by the Deutsche Forschungsgemeinschaft (DFG) through the Collaborative Research centre “ToCoTronics” , Project-ID 258499086-SFB 1170. RND is supported by the PRIME programme of the German Academic Exchange Service (DAAD), with funds from the German Federal Ministry of Research, Technology and Space (BMFTR). VB was supported in part by the DOE through DE-SC0013528 and QuantISED grant DE-SC0020360. This project was also supported by FWO-Vlaanderen project G0A2226N. Supplemental Material Recursion relations, Lanczos coefficients, and orthogonal polynomials— Here we give more details on the recursion relation satisfied by the c_{n}(E) and show that the general solution is given in terms of orthogonal polynomials ( 7 ). Afterwards, we show that for the case of 3d gravity, which has the Lanczos coefficients of a particle on SL(2,\mathbb{R}) ( 17 ), the orthogonal polynomials are given in terms of Laguerre polynomials ( 18 ). Recall that by definition we have c_{n}(E)=\left\langle E|K_{n}\right\rangle and it follows from ( 2 ) that they satisfy the recursion relation \begin{split}E\,c_{n}(E)=a_{n}\,c_{n}(E)+b_{n}\,c_{n-1}(E)+b_{n+1}c_{n+1}(E)\,,\end{split} (A.1) with initial conditions c_{-1}(E)=0 and c_{0}(E)=\phi_{0}(E) . We now prove inductively that the solution to this recursion relation takes the form ( 7 ), with a polynomial of degree n h_{n}(E)=\sum_{k=0}^{n}\alpha_{nk}E^{k}\,. (A.2) proof: We first show that c_{1}(E) takes the form ( 7 ), with a polynomial h_{1}(E) of degree one. Indeed, we find from ( A.1 ) \begin{split}c_{1}(E)&=b_{1}^{-1}(E\,c_{0}(E)-a_{n}c_{0}(E)-b_{0}c_{-1}(E))=\frac{\phi_{0}(E)}{b_{1}}(E-a_{0})\,,\end{split} (A.3) and consequently h_{1}(E)=(E-a_{0})/b_{1} . By induction, we now prove that if all c_{n}(E) take the form ( 7 ) with h_{n}(E) given by ( A.2 ) up to a fixed finite n\in\mathbb{N} , then we have c_{n+1}(E)=\phi_{0}(E)h_{n+1}(E) with a polynomial h_{n+1}(E) given by ( A.2 ). Indeed, we find from ( A.1 ) \begin{split}c_{n+1}(E)&=b^{-1}_{n+1}(E\,c_{n}(E)-a_{n}c_{n}(E)-b_{n}c_{n-1}(E))=\frac{\phi_{0}(E)}{b_{n+1}}\left(\sum_{k=0}^{n}\alpha_{nk}E^{k+1}-a_{n}\sum_{k=0}^{n}\alpha_{nk}E^{k}-b_{n}\sum_{k=0}^{n-1}\alpha_{n-1,k}E^{k}\right)\\ &=\phi_{0}(E)\sum_{k=0}^{n+1}\frac{\alpha_{n,k-1}-(a_{n}\alpha_{nk}+b_{n}\alpha_{n-1,k})}{b_{n+1}}E^{k}=\phi_{0}(E)\sum_{k=0}^{n+1}\alpha_{n+1,k}E^{k}=\phi_{0}(E)h_{n+1}(E)\,,\end{split} (A.4) where we impose \alpha_{nk}=0 for k<0 and k>n . Thus, c_{n+1}(E) takes the form ( 7 ) and h_{n+1}(E) is a polynomial of degree n+1 , with coefficients satisfying a recursion relation \alpha_{n+1,k}=\frac{\alpha_{n,k-1}-(a_{n}\alpha_{nk}+b_{n}\alpha_{n-1,k})}{b_{n+1}}\,, (A.5) with initial conditions \alpha_{00}=1 , which concludes the proof. \square Now consider the case of 3d gravity. We show that the solutions to ( A.1 ) in this case are given by the generalized Laguerre polynomials ( 18 ). Hence, we first define the dimensionless shifted energy x:=\beta(E+E_{0}(J)) and insert the explicit form of the coefficients ( 16 ) into ( A.1 ) \begin{split}\sqrt{(n+1)(2h+n)}c_{n+1}(x)=\bigl[x+2(h+n)\bigr]c_{n}(x)-\sqrt{n(2h+n-1)}c_{n-1}(x)\,,\end{split} (A.6) where for us h=\tfrac{3}{4} . To remove the square roots, we define an n dependent prefactor A_{n} via \frac{A_{n+1}}{A_{n}}=\frac{1}{\sqrt{(n+1)(2h+n)}}\,, (A.7) which is solved by A_{n}=A_{0}\sqrt{\frac{\Gamma(2h)}{n!\Gamma(n+2h)}}\,, (A.8) where we used \prod_{j=0}^{n-1}(j+1)=n! and \prod_{j=0}^{n-1}(2h+j)=\Gamma(n+2h)/\Gamma(2h) . We set c_{n}(x)=A_{n}P_{n}(x) and ( A.6 ) becomes P_{n+1}(x)=\bigl[x+2(h+n)\bigr]P_{n}(x)-n(n+2h-1)P_{n-1}(x)\,, (A.9) which we compare with the standard recursion relation satisfied by the generalized Laguerre polynomials (n+1)L^{(\alpha)}_{n+1}(y)=(2n+1+\alpha-y)L^{(\alpha)}_{n}(y)-(n+\alpha)L^{(\alpha)}_{n-1}(y)\,. (A.10) This implies P_{n}(x)=n!L_{n}^{(\alpha)}(-x)\,, (A.11) with \alpha:=2h-1 . Thus, we find the closed form of the solution to ( A.1 ) from ( A.8 ) as c_{n}(E)=A_{0}\sqrt{\frac{\Gamma(2h)n!}{\Gamma(n+2h)}}L_{n}^{(2h-1)}\!\Bigl(-\beta(E+E_{0}(J))\Bigr)\;, (A.12) where the prefactor A_{0} is fixed through the initial condition A_{0}=c_{0}(E)=\phi_{0}(E) . Moreover, for our case we have h=\tfrac{3}{4} , implying that c_{n}(E)=\phi_{0}(E)\sqrt{\frac{\Gamma(\tfrac{3}{2})n!}{\Gamma(n+\tfrac{3}{2})}}L_{n}^{(1/2)}\!\Bigl(-\beta(E+E_{0}(J))\Bigr)\;, (A.13) which solves ( A.1 ) for arbitrary initial \phi_{0}(E) . Lanczos coefficients of the MWK density— Here we give more details about the Lanczos coefficients which we obtain from the MWK density of states ( 13 ). First, we determine the MWK partition function from ( 11 ) and find \;Z_{\text{MWK}}(\beta)=e^{-\beta\left|J\right|}\left[\frac{A\,e^{S_{0}}\Gamma\bigr(\frac{3}{2}\bigl)}{\beta^{3/2}}+\frac{B\,(-1)^{J}e^{S_{0}/2}\Gamma(\frac{1}{2}\bigl)}{\beta^{1/2}}\right]\,.\; (A.14) Thus, we obtain the return amplitude from ( 12 ) as S_{\text{MWK}}(t)=\frac{e^{-i\left|J\right|t}}{1+\delta}\left[\Big(\dfrac{\beta}{\beta+it}\Big)^{3/2}+\delta\cdot\Big(\dfrac{\beta}{\beta+it}\Big)^{1/2}\right]\,, (A.15) where we set \delta=2\frac{B}{A}(-1)^{J}e^{-S_{0}/2}\beta . From this return amplitude we determine the Lanczos coefficients \begin{gathered}a_{0}=-\left|J\right|-\frac{1}{2\beta}\left(1+\frac{2}{1+\delta}\right)\,,\\ a_{n}=-\left|J\right|-\frac{1}{2\beta}\Biggl[(4n+1)-(2n-1)(2n)\frac{Q_{n-2}(\delta)}{Q_{n-1}(\delta)}+(2n+1)(2n+2)\frac{Q_{n-1}(\delta)}{Q_{n}(\delta)}\Biggr]\,,\quad n\geq 1\,,\end{gathered} (A.16) and b_{0}=1\,,\qquad b_{n}=\frac{1}{\beta}\,\sqrt{\frac{n(2n-1)}{2}\;\frac{Q_{n-2}(\delta)\,Q_{n}(\delta)}{Q_{n-1}(\delta)^{2}}}\,,\quad n\geq 1\,, (A.17) where we introduce the functions \begin{split}Q_{n}(\delta):&=2^{n+1}(n+1)!\,L_{n+1}^{(-1/2)}\left(-\frac{\delta}{2}\right)\,,\end{split} (A.18) for n\geq-1 . We now show that these Lanczos coefficients approach ( 17 ) for large n . Therefore, we consider the asymptotic behavior of the ratio R_{n}:=\frac{Q_{n-1}(\delta)}{Q_{n}(\delta)}=\frac{1}{2n}\left(1-\frac{\sqrt{\delta/2}}{\sqrt{n}}+\frac{\delta-1}{2n}+O(n^{-3/2})\right)\,, (A.19) where we use the standard asymptotics of the Laguerre polynomials. We thus find the large n behavior of the Lanczos coefficients as a_{n}=-\frac{4n+3}{2\beta}-\left|J\right|\,,\quad b_{n}=\frac{n}{\beta}\,. (A.20) This agrees with the form of the Lanczos coefficients for a particle on the SL(2,\mathbb{R}) group manifold 4 , a_{n}=\gamma(h+n)+\xi,\qquad b_{n}=\sigma\sqrt{n(2h+n-1)}\;, (A.21) evaluated at large n . Calculation of the spread complexity kernel— In this appendix we give a detailed derivation of the complexity kernel ( 21 ) and show that it has a double pole in \omega=E-E^{\prime} . Therefore, we introduce the generating function F(s;E,E^{\prime}):=\sum_{n=0}^{\infty}e^{-sn}h_{n}(E)h_{n}(E^{\prime})\,, (A.22) which is related to ( 21 ) by A(E,E^{\prime})=-\partial_{s}F(s;E,E^{\prime})\Big|_{s=0^{+}}\,. (A.23) Note that the orthogonal polynomials in ( A.22 ) are given by generalized Laguerre polynomials ( 18 ). Thus, we use the Hille-Hardy kernel to evaluate the generating function ( A.22 ) explicitly as \begin{split}&F(s;x,y)=\Gamma\!\big(\tfrac{3}{2}\big)\sum_{n=0}^{\infty}\frac{n!\cdot e^{-sn}}{\Gamma\!\big(n+\tfrac{3}{2}\big)}L_{n}^{(1/2)}(-x)L_{n}^{(1/2)}(-y)=\Gamma\!\big(\tfrac{3}{2}\big)\frac{\exp\left(\frac{x+y}{e^{s}-1}\right)}{\big(1-e^{-s}\big)\big(xy\,e^{-s}\big)^{1/4}}\,I_{1/2}\!\!\left(\frac{2\sqrt{xy\,e^{-s}}}{1-e^{-s}}\right)\,,\end{split} (A.24) where we again set x:=\beta(E+E_{0}(J)) , and y:=\beta(E^{\prime}+E_{0}(J)) . We set t=e^{-s} and evaluate the right hand side of ( A.23 ) through -\partial_{s}\log(F)=t\partial_{t}\log F=\frac{t}{1-t}-\frac{t(x+y)}{(1-t)^{2}}-\frac{1}{4}+\,\sqrt{xy}\,\frac{t^{2}+t}{(t-1)^{2}\sqrt{t}}\,\frac{I^{\prime}_{1/2}\left(\frac{2\sqrt{xy\,t}}{1-t}\right)}{I_{1/2}\left(\frac{2\sqrt{xy\,t}}{1-t}\right)}\,, (A.25) where we set I^{\prime}_{1/2}(u)=\frac{d}{du}I_{1/2}(u) . We don’t actually need the full closed form of those algebraic pieces; what we need is the singular behavior as x\to y . Therefore, we set x=z+\frac{\beta\omega}{2} , and y=z-\frac{\beta\omega}{2} with \omega:=E-E^{\prime} and z=\frac{x+y}{2} . Then, as t\to 1^{-} , i.e., s\to 0^{+} , \begin{split}\frac{2\sqrt{xyt}}{1-t}=\frac{2z}{1-t}\sqrt{1-\frac{\beta^{2}\omega^{2}}{4z^{2}}+O(\omega^{3})}\sim\ \frac{2z}{1-t}-\frac{\beta^{2}\omega^{2}}{4(1-t)z}+O(\omega^{3}).\end{split} (A.26) Using the closed form of the Bessel function I_{1/2}(u)=\sqrt{\frac{2}{\pi u}}\sinh u and \sinh u\sim\tfrac{1}{2}e^{u} we find the characteristic edge exponent \begin{split}e^{\frac{t(x+y)}{1-t}}\sinh\left(\frac{2\sqrt{xy\,t}}{1-t}\right)&\sim\,\tfrac{1}{2}\exp\!\left[\frac{\beta^{2}\omega^{2}}{4z(1-t)}\right].\end{split} (A.27) Hence, up to an overall smooth prefactor G(z) that stays finite and nonzero as t\to 1 and \omega\to 0 , we have F(t;z,\omega)\ \sim\ \frac{G(z)}{\sqrt{1-t}}\exp\!\left[-\frac{\beta^{2}\omega^{2}}{4z(1-t)}\right],\quad\text{with}\quad(1-t)=1-e^{-s}\sim s. (A.28) From ( A.23 ) we find the leading singular term of the complexity kernel ( 21 ), as A(z,\omega)\ \sim\ \frac{G(z)}{(1-t)^{3/2}}\left[1+\frac{\beta^{2}\omega^{2}}{2z(1-t)}+\cdots\right]\exp\!\left[\frac{\beta^{2}\omega^{2}}{4z(1-t)}\right]. (A.29) In the strict s\to 0^{+} limit, with fixed \omega we find that the kernel has a double pole in \omega A(\overline{E},\omega)\ =\ \frac{\mathcal{C}(\overline{E})}{\omega^{2}}\ +\ \text{(terms regular in }\omega)\,, (A.30) with a non-zero, smooth coefficient \mathcal{C}(\overline{E})=-\frac{\pi}{8}\ \frac{\Gamma(\tfrac{3}{2})}{\beta^{2}z}\ =-\frac{\pi}{8}\ \frac{\sqrt{\pi}/2}{\beta^{3}(\overline{E}+E_{0}(J))}\ , (A.31) where z=\beta(\overline{E}+E_{0}(J)) . Late-time behavior of spread complexity— Here we analyze the late-time behavior of ( 20 ) and show that it saturates at a finite number, which is exponential in the black hole entropy. From ( 10 ) and ( 23 ) we find that the spectral representation of spread complexity is \overline{C_{S}(t)}=\frac{1}{Z(\beta)^{2}}\int dE\,dE^{\prime}\,e^{-i(E-E^{\prime})t}\,e^{-\beta(E+E^{\prime})}\,\overline{\rho(E^{\prime})\rho(E)}\,\frac{\mathcal{C}(\overline{E})}{(E-E^{\prime})^{2}}\,, (A.32) where \mathcal{C} , which only depends on \overline{E}=(E+E^{\prime})/2 , is given by ( A.31 ). Due to the oscillatory factor e^{-i(E-E^{\prime})t} the late time behavior of the integral is dominated by small energy differences \omega=E-E^{\prime}\sim 1/t . In this regime, the spectral correlator has the universal form ( 22 ), where for now we keep the density of states arbitrary. Introducing the rescaled variable \hat{\omega}=\omega t , ( A.32 ) is given by \overline{C_{S}(t)}=C_{0}+\frac{t}{Z(\beta)^{2}}\int d\overline{E}\;e^{-2\beta\bar{E}}\;\rho(\bar{E})^{2}\;\mathcal{C}(\bar{E})\int d\hat{\omega}\,e^{i\hat{\omega}}\frac{1}{\hat{\omega}^{2}}\left[1-\left(\frac{t}{\pi\rho(\bar{E})\hat{\omega}}\right)^{2}\sin^{2}\left(\frac{\pi\rho(\bar{E})\hat{\omega}}{t}\right)\right]\,, (A.33) where the constant term arises from contact terms in the spctral correlator and we fix it below such that \overline{C_{S}(0)}=0 . We also used that for small energy differences \overline{E}\approx E\approx E^{\prime} . Although the \hat{\omega} integral contains 1/\hat{\omega}^{2} , the integrand is finite at \hat{\omega}=0 , since the expression in brakets has the small \hat{\omega} expansion 1-\left(\frac{t}{\pi\rho(\bar{E})\hat{\omega}}\right)^{2}\sin^{2}\left(\frac{\pi\rho(\bar{E})\hat{\omega}}{t}\right)=\frac{1}{3}\left(\frac{\pi\rho(\bar{E})\hat{\omega}}{t}\right)^{2}+O(\hat{\omega}^{4})\,, (A.34) and thus cancels the pole at \hat{\omega}=0 . The \hat{\omega} integral has been solved in 31 , where it appeared in the definition of the non-perturbative wormhole length for a large class of 2d dilaton gravity models. Therefore, we obtain \overline{C_{S}(\hat{t})}=C_{0}+\frac{2\pi^{2}e^{S_{0}}}{3\hat{Z}(\beta)^{2}}\int_{\bar{E}_{*}(\hat{t})}^{\infty}d\bar{E}\;e^{-2\beta\bar{E}}\;\hat{\rho}(\bar{E})^{3}\;\mathcal{C}(\bar{E})\;\Bigl(1-X(\hat{t};\bar{E})\Bigr)^{3}\,. (A.35) where we introduce the rescaled quantities \rho(\bar{E})=e^{S_{0}}\hat{\rho}(\bar{E}) , Z(\beta)=e^{S_{0}}\hat{Z}(\beta) , and t=e^{S_{0}}\hat{t} to show the dependence on the black hole entropy S_{0} explicitly. We also have X(\hat{t};\bar{E})=\frac{\hat{t}}{2\pi\hat{\rho}(\bar{E})}\,, (A.36) and \bar{E}_{*}(\hat{t}) is defined implicitly by \pi\hat{\rho}(\bar{E}_{*})=\hat{t}\,. (A.37) For the Maxfield-Turiaci density ( 14 ) we have \bar{E}_{*}(\hat{t})=E_{0}(J)+\Bigl(\frac{\hat{t}}{\pi A}\Bigr)^{2}\, . Thus, at late times \hat{t}\to\infty , the lower limit \bar{E}_{*}(\hat{t}) tends to infinity, and the integral in ( A.35 ) vanishes. Therefore, we determine the late-time saturation value of ( A.35 ) from the constant term, which has to be fixed such that \overline{C_{S}(0)}=0 . For \hat{t}\to 0 we have \bar{E}_{*}(\hat{t})\to E_{0}(J) as well as X(\hat{t};\bar{E})\to 0 , and we find that the constant is given by C_{0}=-\frac{2\pi^{2}e^{S_{0}}}{3\,\hat{Z}(\beta)^{2}}\int_{E_{0}(J)}^{\infty}d\bar{E}\;e^{-2\beta\bar{E}}\;\hat{\rho}(\bar{E})^{3}\;\mathcal{C}(\bar{E})\,. (A.38) Using ( A.31 ) and the Maxfield-Turiaci density of states ( 14 ) a straightforward evaluation of the integral in ( A.38 ) gives C_{0}=e^{S_{0}}\,A\,\frac{\pi^{3}}{8}\,(2E_{0}(J))^{3/2}\,e^{4\beta E_{0}(J)}\,\Gamma\!\left(-\frac{3}{2},\,4\beta E_{0}(J)\right)\,. (A.39) For E_{0}(J)\beta\ll 1 , this further simplifies to C_{0}\simeq e^{S_{0}}\,A\,\frac{\pi^{3}}{12}\,(2\beta)^{-3/2}\,. (A.40)