On the Pseudo-Mixing of Kac's Walk

On the Pseudo-Mixing of Kac’s Walk

arXiv:2608.17374v1 [math.PR] 18 Aug 2026

Natesh S. Pillai Harvard

Aaron Smith uOttawa and TIMC

Vinod Vaikuntanathan MIT

August 19, 2026 Abstract We study the pseudo-mixing properties of Kac’s walk, a popular Markov chain Monte Carlo algorithm introduced by Hastings in 1970 to sample from the Haar measure on (𝑛). The mixing time of the full walk is known to be 𝑛2 polylog(𝑛) in Wasserstein distance and very recently, in total variation distance (Oliveira, Annals of Applied Probability, 2009; and Pillai and Smith, Annals of Probability, 2018, and Arxiv, 2026). However, algorithms based on replacing Haar-distributed matrices with ones generated by Kac’s walk for a mere 𝑛 polylog(𝑛) ≪ 𝑛2 steps (which we will refer to as Kac matrices) have enjoyed strong empirical success achieving near-quadratic runtime speedup (e.g. Ailon and Chazelle, STOC 2006; and Jain et al., Annals of Applied Probability, 2022). Indeed, a recent work (Vaikuntanathan and Zamir, SODA 2025) conjectured that such matrices are computationally indistinguishable from Haarrandom matrices, meaning that any polynomial-time algorithm using Haar matrices would work just as well using Kac matrices. We show two results supporting this conjecture: • First, we prove a conjecture of Oliveira that the first 𝑘 columns of Kac’s walk mix in time 𝑛𝑘 polylog(𝑛) uniformly in 𝑛 and 𝑘; • Secondly, we use this and a representation-theoretic argument to show that low-degree polynomials cannot distinguish Kac matrices from Haar matrices. In particular, degree-𝑘 polynomials fail to distinguish 𝑛𝑘 2 polylog(𝑛)-step Kac matrices from Haar matrices. As an illustrative application, we also show that our second result immediately implies that Kac’s walk can be used as a plug-in replacement for Haar matrices in the fast Johnson-Lindenstrauss algorithm, providing a quick proof of a conjecture of Ailon and Chazelle (STOC 2006). We believe our results may be of independent interest to MCMC practitioners: they suggest that the “computational” mixing time is drastically smaller than the mixing time in “traditional” norms. While it is well-known that this phenomenon is possible (Rabinovich, Ramdas, Jordan and Wainwright, Bayesian Analysis, 2020), this is the first illustration of a drastic difference for useful functions of a non-toy chain that we are aware of.

1

1

Introduction

In a landmark paper, Hastings [Has70, Section 3] introduced a discrete-time random walk {𝑋𝑡 }𝑡≥0 on (𝑛),1 now called Kac’s walk, that evolves by the rule 𝑋𝑡+1 = 𝑅𝑖𝑡 𝑗𝑡 (𝜃𝑡 ) 𝑋𝑡 ,

(1.1)

where (𝑖𝑡 , 𝑗𝑡 ) ∈ {(𝑖, 𝑗) ∶ 1 ≤ 𝑖 < 𝑗 ≤ 𝑛} are chosen uniformly and independently, 𝜃𝑡 are sampled from the uniform distribution on [0, 2𝜋), and 𝑅𝑖𝑗 (𝜃) = 𝐼𝑛 + (cos 𝜃 − 1)(𝐸𝑖𝑖 + 𝐸𝑗𝑗 ) + sin 𝜃 𝐸𝑖𝑗 − sin 𝜃 𝐸𝑗𝑖 is simply rotation by angle 𝜃 in the (𝑖, 𝑗)-coordinate hyperplane. That is, starting from a fixed matrix 𝑋0 , the random process repeatedly picks uniformly random rows 𝑖𝑡 and 𝑗𝑡 at time 𝑡, performs a random rotation in the two-dimensional space they span, and replaces rows 𝑖𝑡 and 𝑗𝑡 with their rotated versions. It is straightforward to check that, for any 1 ≤ 𝑘 ≤ 𝑛, the projection of Kac’s walk to the first 𝑘 columns is again a Markov chain. This is called the 𝑘-column walk. The special case 𝑘 = 1, which gave the walk on (𝑛) its name, was introduced in the statistical physics literature in Kac’s insightful 1959 paper [Kac59] in an attempt to simplify Boltzmann’s equation. Previous Work on Mixing Times. The stationary distribution of the Kac walk is the Haar measure on (𝑛). Many notions of “mixing times” have been studied extensively for Kac’s walk. Early work focused on the relaxation time (i.e. inverse of the spectral gap of the transition operator), a rather weak notion of convergence. The first polynomial-time estimate appeared in Diaconis and Saloff-Coste [DSC00], who showed that the relaxation time was 𝑂(𝑛3 ). The relaxation time was shown to be Θ(𝑛) several years later in [CCL03], and [Mas03] computed the full spectrum of the transition operator. Although Kac’s walk is a random walk on a group, it is not conjugation-invariant, and so even complete spectral information does not automatically lead to good estimates of the mixing time in stronger norms. The Wasserstein mixing time was shown to be 𝑂(𝑛2 log(𝑛)) by Oliveira [Oli09], who also showed that this bound is tight modulo logarithmic factors. Finally, there has been substantial effort to estimate the mixing time in total variation. Diaconis and SaloffCoste [DSC00] proved the first bound, but it was exponential in 𝑛. The first polynomial-time bound was show Jiang [Jia17], who showed the mixing time was 𝑂(𝑛5 log2 𝑛). This was improved shortly after by Pillai and Smith [PS18] to 𝑂(𝑛4 log 𝑛), and very recently, in a work concurrent to ours, to the near-optimal 𝑂(𝑛2 log 𝑛) by the same authors [PS26b]. 1

(𝑛) is the special orthogonal group, the set of all matrices in ℝ𝑛×𝑛 with determinant 1.

2

This paper is focused on the mixing time of the 𝑘-column walk. In the case 𝑘 = 1, the tight mixing bound of 𝑂(𝑛 log 𝑛) was shown by Pillai and Smith [PS17] after a sequence of works [DSC00, Jia12]. To our knowledge, there are no strong bounds on the mixing time for 1 < 𝑘 ≪ 𝑛 in any sense except for the relaxation time. Our First Result. The first result in this paper fits squarely into the large literature on mixing times of Markov chains [LPW17]. It shows that the 𝑘-column walk mixes in 𝑂(𝑛 log(𝑛) ⋅ max(𝑘, log(𝑛))) steps uniformly in 𝑘 and 𝑛 in the Wasserstein metric, resolving a conjecture of [Oli09, pg. 1229]. Theorem 1.1 (Informal). Let 𝐷 be the Riemannian distance on the Stiefel manifold St(𝑛, 𝑘) 2 and let 𝑊𝐷 be Wasserstein distance with cost 𝐷. Let 𝑃 𝑇 (𝑋 ) denotes the probability distribution induced by running the 𝑘-column walk for 𝑇 steps starting with 𝑋 ∈ St(𝑛, 𝑘). Then, for every 𝑋 , 𝑌 ∈ St(𝑛, 𝑘), the Wasserstein distance 𝑊𝐷 (𝑃 𝑇 (𝑋 ), 𝑃 𝑇 (𝑌 )) is at most 𝜖 as long as 𝑇 = Ω(𝑛(𝑘 + log 𝑛) ⋅ log(𝐷(𝑋 , 𝑌 )/𝜖)) . When 𝑘 = 𝑛, the 𝑘-column chain is the usual Kac walk on (𝑛) and the corresponding Wasserstein contraction estimate matches the one proved in [Oli09]. Furthermore, for every 𝑘 and 𝑛, our bound is essentially optimal since Ω(𝑛𝑘) steps is absolutely necessary for convergence [Oli09]. We refer the reader to Theorem 1 for a formal statement, and to Section 3 for its proof. Pseudo-Mixing and Our Main Result. While Kac’s walk on (𝑛) does not mix in any traditional sense in 𝑜(𝑛2 ) steps, it does seem to produce “random enough” matrices after much fewer, e.g. 𝑛 ⋅ (log 𝑛)𝑂(1) steps. A major consequence is that you get matrices that look random yet admit fast matrix operations; for example, a 𝑇 -step Kac matrix admits matrix-vector multiplication in 𝑂(𝑇 ) time. This phenomenon was first conjectured by Ailon and Chazelle [AC06] in their groundbreaking work on fast Johnson-Lindenstrauss (JL) transforms. Recall that JL is a dimensionality reduction technique where, given a set 𝑆 of 𝑁 points in ℝ𝑛 , one applies a Gaussian (or scaled Rademacher) matrix 𝐴 ∈ ℝ𝓁×𝑛 to each 𝑥 ∈ 𝑆 so that (1 − 𝜖)||𝑥 − 𝑦||2 ≤ ||𝐴𝑥 − 𝐴𝑦||2 ≤ (1 + 𝜖)||𝑥 − 𝑦||2 for all 𝑥, 𝑦 ∈ 𝑆. Remarkably, this can be achieved when 𝓁 is only Θ(log 𝑁 /𝜖 2 ). While a naive application of the JL lemma requires runtime 𝑂(𝑛𝓁) for multiplication of 𝑥 by 𝐴, Ailon ̃ and Chazelle came up with several ways to reduce the runtime to 𝑂(𝑛), nearly the time required to just read the input 𝑥, by constructing the matrix 𝐴 cleverly. Curiously, they also propose an alternative construction, setting the matrix 𝐴 to be (the projection to the first 𝓁 2

For 1 ≤ 𝑘 ≤ 𝑛, the Stiefel manifold is St(𝑛, 𝑘) = {𝑋 ∈ ℝ𝑛×𝑘 ∶ 𝑋 ⊤ 𝑋 = 𝐼𝑘 }.

3

rows of) a matrix resulting from Kac’s walk after 𝑇 = 𝑂(𝑛 log 𝑛 + (log 𝑁 /𝜖)𝑂(1) ) steps, and conjecture it to be “at least as good as the one described in [their] paper, yet much more elegant”. Indeed, matrix-vector multiplication with such a matrix can be accomplished in 𝑂(𝑇 ) time, much faster than 𝑂(𝑛 log 𝑁 /𝜖 2 ) guaranteed by vanilla JL. This conjecture was essentially resolved nearly 15 years later by Jain, Pillai, Sah, Sawhney and Smith [JPS+ 22]. Yet, the phenomenon, that we will refer to as pseudo-mixing, appears to be much more general than that. In a recent work, Vaikuntanathan and Zamir [VZ26] conjectured that the Kac walk after 𝑛 ⋅ (log 𝑛)𝑂(1) steps is computationally indistinguishable from a “uniformly random” orthogonal matrix, namely from the Haar measure on (𝑛). That is, no polynomial-time algorithm can tell the two distributions of matrices apart. They relied on this conjecture to construct trapdoored matrices, distributions over 𝑛 × 𝑛 matrices which look (Haar-)random to any polynomial-time algorithm, yet admit near-linear time matrixvector multiplication (and many other matrix operations as well). The computational indistinguishability here is crucial: they also show via a simple counting argument that truly (Haar-)random matrices (and ones that are TV- or Wasserstein-close to them) cannot possibly admit subquadratic time matrix-vector multiplication. If the VZ conjecture is true, it says a far more general statement than the one predicted by Ailon and Chazelle. Not only is the Kac matrix (after a near-linear number of Kac steps) good enough for JL, it is good enough for any polynomial-time computable application. It is hopeless to prove the conjecture of [VZ26] in its full generality as it would imply that 𝑃 ≠ 𝑁 𝑃, and even that cryptographic one-way functions exist unconditionally. Short of that, we could attempt to prove the conjecture against restricted classes of distinguishers. In this work, we consider the family of low-degree polynomials over ℝ, drawing from an illustrious line of work in the algorithmic statistics literature (see the thesis of Hopkins [Hop18] and the survey of Wein [Wei25] for an extensive historical perspective.) Our second, and main, result, is thus about Kac’s walk on all of (𝑛) and says, roughly, that a certain class of test functions, namely (poly-logarithmically) low-degree polynomials, cannot distinguish between a sample from the Haar measure on (𝑛) and a sample obtained by running Kac’s walk for 𝑇 ≈ 𝑛 polylog(𝑛) steps. This resolves an open problem posed by Vaikuntanathan and Zamir [VZ26]. Theorem 1.2 (Informal). Polynomials over ℝ of total degree at most 𝑘 = 𝑘(𝑛) cannot distinguish between a sample from the Haar measure and a sample obtained by running Kac’s 2 ) steps. ̃ walk for 𝑇 (𝑛) = 𝑂(𝑛𝑘 We refer the reader to Theorem 2 for a formal statement, and to Section 5 for its proof. While this result may at first sight appear to contradict previous lower bounds on the mixing time of Kac’s walk, such as the lower bound of Ω(𝑛2 ) for mixing in Wasserstein due to [Oli09], it does not. The difference, of course, comes from the test functions being studied. Most of the literature on mixing times measures mixing using “classical” test functions such as all bounded functions (total variation) and all Lipschitz functions (Wasserstein), while we follow [Hop18, Wei25] and use low-degree polynomials. Low-degree polynomials 4

are not sufficient for all applications, but as we discuss in Section 1.1, they are good enough for many. Following the low-degree heuristic championed by [Hop18], one could also informally interpret this as saying that it is computationally difficult for any “natural” polynomial-time algorithm to distinguish between Haar and Kac matrices. However, such a statement should be made with some care as recently demonstrated by [BHJK25]; see also [HKK+ 26] for a more nuanced perspective of when predictions made by the low-degree heuristic can be turned into theorems. Broader Perspective: Pseudo-Mixing as a General Phenomenon. While Theorem 2 only applies to a single Markov chain, we believe our results are of broader interest. This is both because the Kac walk itself is of great interest, and because this is (to our knowledge) the first example of a phenomenon that would be of interest to the Markov chain Monte Carlo (MCMC) community: • MCMC: The Markov chain studied here was the main worked example in the first major paper on MCMC [Has70]. The last sentence of that paper asked, essentially, the question we are trying to answer in Theorem 2: for what functions on (𝑛) do we expect this MCMC chain to be “efficient”? In light of previous work on this walk [Oli09], we believe the answer of this paper to be perhaps a bit surprising: the walk “looks random” to certain computationally-bounded observers long before it “looks random” according to most metrics on probability measures. Beyond the historical interest in Kac’s walk, we believe this result is qualitatively interesting to MCMC practitioners. It is well-known that mixing times can give conservative estimates for the convergence of specific functions of Markov chains [RRJW20], but most mathematically tractable examples appear to be “toy” functions. Even when the phenomenon was empirically noticed for practical MCMC algorithms, it appeared to mostly require rather special functions. This is one of very few situations in which the usual mixing time is known to be very conservative for natural and important functions of a natural Markov chain. Having found one such example, we expect there to be many others. • Mathematical Techniques: Our paper also includes nontrivial representationtheoretic arguments that are used to lower-bound the variances of polynomials on (𝑛) (see Section D). These results may be of independent interest, as moment calculations on manifolds are generally difficult [CMN21]. Such variance lowerbounds are necessary for one major approach to computational hardness [Wei25], and could be used by researchers working on computational hardness against lowdegree polynomials in constrained state spaces such as (𝑛).

5

1.1

Applications

Machine Learning and Fast Matrix Calculations. As discussed in [VZ26], computational indistinguishability of 𝑇 -step Kac walk for 𝑇 ≪ 𝑛2 can be used in algorithmic applications. Informally, the heuristic is: if you can’t “easily” tell the difference between a target distribution 𝜇 and an easier-to-sample distribution 𝜈, then surely it must be “safe” to replace 𝜇 by 𝜈 in any “reasonable” statistical or machine learning workflow. It is sometimes possible to upgrade this heuristic to a precise theorem. As an illustrative example, we show that Theorem 2 almost immediately implies that Kac’s walk can, by itself, be used to give a fast Johnson-Lindenstrauss transform (see Theorem 6.1), providing a short proof of a conjecture of [AC06] who suggested this approach but did prove any formal guarantees. We note that our proof is inspired by the computational hardness heuristic of [VZ26], but is not a heuristic argument. We also note that the algorithm in [AC06] is no longer the state-of-the-art fast JohnsonLindenstrauss transform, and our theorem is no longer the state-of-the-art result. In the 20 years since [AC06], there has been substantial work on developing slightly faster transforms [AL13, DKS10, KW11, KN14, BK21, FHL23, HT23], and the conjecture of [AC06] was moreor-less proved in [JPS+ 22]. We nonetheless view Theorem 6.1 as interesting, since it shows how to obtain nontrivial results as a near-immediate consequence of a general bound on the computational mixing time. We suspect that this line of thinking is fruitful in a much broader set of applications and believe that it could be a modular source of speed-ups in various machine learning algorithms. Cryptography. A trapdoored matrix [Sot16, VZ26, BN25] consists of a public 𝑛-by-𝑛 matrix 𝑀, as well as a private trapdoor function 𝑃𝑀 with the following properties, for some 0 < 𝜀 ≪ 1. 1. We have 𝑃𝑀 (𝑣) = 𝑀𝑣 for all vectors 𝑣. 2. For any 𝑣, we can compute 𝑃𝑀 (𝑣) in 𝑂(𝑛1+𝜀 ) steps; however, 3. For a computationally bounded adversary, 𝑀 is indistinguishable from a random matrix, and consequently, by a simple counting argument, a polynomial-time adversary cannot come up with a 𝑜(𝑛2 )-size circuit that computes 𝑣 ↦ 𝑀𝑣. Sotiraki [Sot16] implicitly defined this notion and used it to construct an authentication ̃ protocol where the honest parties (the authenticators) run in 𝑂(𝑛) time, but no 𝑜(𝑛2 )time adversary can impersonate them. Her construction used matrices that result from a transvection walk over a finite field 𝔽, a process that is very similar to Kac’s walk. A transvection walk [DSC96] is one where, in each step, one chooses rows 𝑖 and 𝑗 randomly and performs a random invertible linear transformation to them. This forms a Markov chain 6

over 𝐺𝐿𝑛 (𝔽), similar to how Kac’s walk works over (𝑛). She proved that each column ̃ of the resulting matrix, after a 𝑂(𝑛)-step walk, is close to uniformly random over 𝔽𝑛 . These results have since then been improved, and much is known about the transvection walk by now [BHP18, BH25, PS26a]. Vaikuntanathan and Zamir, and independently, Braverman and Newman [VZ26, BN25] formally defined trapdoored matrices. [VZ26] used a construction based on the Kac walk (conjecturing that the Kac matrix is computationally indistinguishable from a Haar matrix) and used it to speed up algorithms that use random matrices (as discussed above) as well as to show improved worst-case to average-case reductions for matrix multiplication over finite fields. This latter application can be ported to the case of reals as well, as we briefly discuss below. Given a black-box that multiplies two Haar-random matrices 𝐴 and 𝐵 in (𝑛) correctly with probability 𝜖 > 0 (here, we ignore finite-precision issues), one can use it to compute 𝐴𝐵 for any two matrices 𝐴 and 𝐵. Pick three Kac matrices 𝑀1 , 𝑀2 and 𝑀3 . Feed the box with 𝐴′ = 𝑀1 𝐴𝑀2 and 𝐵′ = 𝑀2−1 𝐵𝑀3 . The black-box returns a matrix 𝐶 ′ , which if it did its job correctly, will be 𝑀1 𝐴𝐵𝑀3 . One can recover 𝐴𝐵 from this by multiplying on the left by 𝑀1−1 and on the right by 𝑀3−1 . Here, we use an additional property of Kac matrices: multiplication by a Kac matrix as well as by its inverse can be done in ̃ 2 ) time. One also crucially uses the fact that the correctness of the box, namely whether 𝑂(𝑛 𝐶 ′ = 𝐴′ 𝐵′ can be checked in 𝑂(𝑛2 ) time using (a variation of) Frievald’s checker [Fre79]. Note that this worst-case to average-case reduction is very different from the usual [BLR90] type additive randomization over finite fields that, unfortunately, does not work over the reals. The consequence of our Theorem 2 to this reduction is less clear, and we leave an in-depth exploration to future work. We also mention that variations of the cryptographic applications of [Sot16, BN25] can also be implemented using Kac walk over (𝑛) as opposed to the transvection walk over a finite field, but leave the details to future work.

1.2

Other Related Work

The notion of a unitary 𝑘-design from quantum information asks for a distribution over unitary matrices in 𝑆𝑈 (𝑁 ) (where 𝑁 = 2𝑛 , 𝑛 being the number of qubits in question, is the dimension of the underlying Hilbert space) whose 𝑘-th moments match those of a Haar-random matrix over 𝑆𝑈 (𝑁 ). This is very close to what we study in this paper. Indeed, there have been several recent works that construct 𝑘-designs, the closest to us being the construction based on random quantum circuits [TRC21, CHH+ 25]. Random quantum circuits are unitaries defined by composing many local quantum gates, that is, gates that operate on 𝑂(1) many qubits. However, the notion of locality here differs a great deal from the notion of locality in Kac’s walk. A local unitary gate on 𝑛 qubits actually acts on many columns of the underlying unitary in 𝑆𝑈 (2𝑛 ). On the other hand, a unitary on 𝑆𝑈 (2𝑛 ) that acts on just two columns (such as in Kac’s walk) is not a local gate in the sense that it has to act on many qubits. Beyond this, the techniques in our work and [CHH+ 25] seem to be 7

very different. Acknowledgments and Statement of AI Use. ChatGPT 5.5 pro was used throughout the creation of this document. Many of the uses were related to saving time and making the proof structure cleaner, such as propagating changes to notation, or simplifying some of our earlier estimates (e.g. Lemma A.1), or drafting straightforward modifications of standard calculations (e.g. Lemma E.2). ChatGPT 5.5 Pro provided extensive guidance on the representation-theoretic literature that was most relevant for the calculations in Appendix D. We also thank Mark Sepanski for providing a more experienced set of eyes in reviewing the calculations in Appendix D. The final results are of course the responsibility of the authors. Guide to the Paper. In Section 2, we state the formal versions of our theorems and give an outline of the proofs. We prove the main error upper bound in Section 3, the matching lower bound in 4, and the main computational mixing bound in Section 5. Section 6 gives an application to the analysis of fast Johnson-Lindenstrauss transforms. Most proof details are deferred to the appendices; the proofs in the main text are largely intended to show how those arguments can be tied together.

2

Technical Overview

2.1

Low-Degree Hardness and Pseudo-mixing

Our definitions follow [Wei25, Definition 3.4]. Definition 2.1 (Distinguishability With Respect to Fixed Sequences). Fix two sequences of distributions 𝜇𝑛 , 𝜈𝑛 that take on values in the set 𝑛 , and let 𝑓𝑛 be a sequence of functions from 𝑛 to ℝ. We say the sequence 𝑓𝑛 weakly distinguishes 𝜇𝑛 and 𝜈𝑛 if √ max(𝑉 𝑎𝑟𝜇𝑛 (𝑓𝑛 ), 𝑉 𝑎𝑟𝜈𝑛 (𝑓𝑛 )) = 𝑂(|𝔼𝜇𝑛 [𝑓𝑛 ] − 𝔼𝜈𝑛 [𝑓𝑛 ]|), and strongly distinguishes if the LHS is 𝑜(|𝔼𝜇𝑛 [𝑓𝑛 ] − 𝔼𝜈𝑛 [𝑓𝑛 ]|). Typically, we are interested in indistinguishability with respect to a large class of adversaries. The most important is the class of low-degree polynomials. Definition 2.2 (Indistinguishability With Respect to Low-Degree Polynomials). Fix a monotone sequence 𝑘(𝑛). We say that 𝜇𝑛 , 𝜈𝑛 are weakly indistinguishable by degree𝑘(𝑛) polynomials if, for every sequence of polynomials 𝑓𝑛 with 𝑑𝑒𝑔(𝑓𝑛 ) ≤ 𝑘(𝑛), 𝑓𝑛 does not weakly distinguish between 𝜇𝑛 , 𝜈𝑛 . The definition for strong indistinguishability is analogous. 8

This motivates the definitions of computational distance and computational mixing time. Definition 2.3 (Computational Distance). Fix two distributions 𝜇, 𝜈 on a state space indexed by a size parameter 𝑛, and fix a degree parameter 𝑑 > 0. We define 𝑑comp (𝜇, 𝜈) = 𝑑comp (𝜇, 𝜈; 𝑛, 𝑑) ≡ sup |𝔼𝜇 [𝑓 ] − 𝔼𝜈 [𝑓 ]|, 𝑓 ∈𝑛,𝑑

where 𝑛,𝑑 is the collection of real polynomials in the ambient coordinates of degree at most 𝑑 satisfying max(𝑉 𝑎𝑟𝜇 (𝑓 ), 𝑉 𝑎𝑟𝜈 (𝑓 )) = 1. Definition 2.4 (Computational Mixing Time, or Pseudo-mixing Time). Fix a sequence of Markov chains {𝑋𝑡(𝑛) } indexed by a size parameter 𝑛 and with unique stationary measures 𝜇(𝑛) . Fix a degree parameter 𝑑 > 0 and a tolerance 𝜀 > 0. Define 𝜏comp = min{𝑡 > 0 ∶ 𝑑comp ((𝑋𝑡(𝑛) ), 𝜇(𝑛) ; 𝑛, 𝑑) ≤ 𝜀}. where (𝑋𝑡(𝑛) ) is the probability law corresponding to the random variable 𝑋𝑡(𝑛) . Remark 2.5. A remark to experts on Markov chain theory: note that the definition of computational distance is very close to the definition of Wasserstein distance: both distances are defined as the largest difference in means across some collection of test functions, with only the test functions differing. Although this might make the notion of computational mixing or pseudo-mixing quite familiar to those with backgrounds in Markov chain theory, the computational distance does not have most of the familiar “nice” properties of Wasserstein distances. For example, single-step contraction of the computational distance does not imply multi-step contraction.

2.2

Statements of Main Theorems

Our result on the mixing time of the 𝑘-column walk is as follows. Theorem 1. There is a universal constant 𝐶 > 0 such that the following holds. For every 1 ≤ 𝑘 < 𝑛, let 𝑃 be the transition kernel of the 𝑘-column walk on St(𝑛, 𝑘), let 𝐷 be the Riemannian distance on St(𝑛, 𝑘), and let 𝑊𝐷 be Wasserstein distance with cost 𝐷. Then, for every 𝑇 ≥ 0 and every pair of starting points 𝑋0 , 𝑌0 ∈ St(𝑛, 𝑘), − 𝑇 / 𝐶𝑛(𝑘+log 𝑛) log 𝑛)⌋ 𝑊𝐷 (𝑃 𝑇 (𝑋0 , ⋅), 𝑃 𝑇 (𝑌0 , ⋅)) ≤ 𝑛 ⌊ ( 𝐷(𝑋0 , 𝑌0 ).

The proof is deferred to Section 3, where it is an immediate corollary of Theorem 3. When 𝑘 = 𝑛, if the chain is started in (𝑛), the 𝑘-column chain is the usual Kac walk on (𝑛); the corresponding Wasserstein contraction estimate is proved in [Oli09]. Let 𝛼𝑛 denote the Haar measure on (𝑛). For 𝑥 ∈ (𝑛), let 𝛽𝑛,𝑇 ,𝑥 denote the law of Kac’s walk at time 𝑇 started from 𝑥. Our main theorem is: 9

Theorem 2. Fix a sequence 𝑘 = 𝑘(𝑛) and a sequence 𝑇 = 𝑇 (𝑛) satisfying 𝑇 (𝑛) = 𝜔(𝑛𝑘 ⋅ (𝑘 + log 𝑛) ⋅ log 𝑛), 𝛽𝑛,𝑇 ,𝑥 and 𝛼𝑛 are weakly 𝑘(𝑛)-indistinguishable in the sense of Definition 2.2. The proof is deferred to Section 5 (which, in turn, heavily relies on Section 4).

2.3

Proof Sketches

We briefly sketch the proof of our main theorem, Theorem 2. The proof is divided into two parts: an upper bound on the difference |𝛽𝑛,𝑇 ,𝑥 (𝑓 ) − 𝛼𝑛 (𝑓 )| and a lower bound on the variance 𝑉 𝑎𝑟𝛼𝑛 (𝑓 ) for low-degree polynomials. To understand the upper bound, we begin by discussing some simple reductions. First, note that to control the error of any monomial in the entries of a matrix, it is sufficient to control the 1-Wasserstein distance between the matrices (see e.g. the standard estimate in Lemma B.1). Second, note that any monomial of degree 𝑘 is a function of variables that appear only in at most 𝑘 columns of Kac’s walk. Thus, by linearity of expectations and the previous reduction, it is enough to check that the 𝑘-column walk mixes quickly in Wasserstein distance. It is natural to try to mimic the existing sharp estimate on the Wasserstein mixing time of Kac’s walk found in [Oli09]. Unfortunately, there is an immediate problem. To see the problem, we briefly sketch [Oli09]. The main calculation is a proof that two copies of Kac’s walk that start at “very close” points 𝑥, 𝑦 can be coupled so that they “contract” at some rate (1 − 𝑐). From that, a standard local-to-global argument implies that the walk mixes well enough for our purposes in time 𝑐 −1 polylog(𝑛). For the full walk on (𝑛), [Oli09] shows that a contraction 𝑐 ≈ 𝑛−2 holds for all sufficiently nearby pairs, obtaining an optimal mixing time bound of roughly 𝑛2 polylog(𝑛). If we could show an analogous 1 bound of 𝑐 ≈ 𝑛(𝑘+log 𝑛) for the 𝑘-column walk, we would be done. Unfortunately, it does not seem to be possible to get such a bound uniformly in all nearby points. Rather than finding a global contraction rate 𝑐, we find that the optimal constant depends on the row norms of the base points and can vary over roughly the range 0 ≲ 𝑐 ≲ 𝑛−2 . While the typical value of the contraction 𝑐 in the neighbourhood of 1 a point sampled from Haar measure is roughly 𝑐 ≈ 𝑛(𝑘+log 𝑛) , this does not immediately give a one-step contraction estimate. Even worse, there are serious obstructions to going from any local contraction estimate to a global contraction estimates, since geodesic paths between points in high-contraction regions of (𝑛) may pass through low-contraction regions.3 Our proof of the upper bound proceeds roughly as follows: 3 On St(2, 1), the contraction rate near a point is proportional to 1 over the sup-norm. As a simple example of why contraction at points along a geodesic cannot be bounded by contraction at the endpoints, consider the points 𝑋 = ( √12 , √12 ) and 𝑌 = ( √12 , √−12 ) on the unit circle St(2, 1). These points have sup-norms satisfying ‖𝑋 ‖2𝑟𝑜𝑤,∞ = ‖𝑌 ‖2𝑟𝑜𝑤,∞ = 21 , which is the smallest possible value on the unit circle. However, the geodesic must clearly pass through 𝑍 = (1, 0), which has sup-norm ‖𝑍‖2𝑟𝑜𝑤,∞ = 1, the largest possible value.

10

1. We define an optimal coupling and use it to prove a local contraction estimate in Frobenius norm; see Lemma 3.1. The same coupling is deterministically nonexpansive in Frobenius norm; see Lemma A.5. 2. We use burn-in estimates based on [PS17] to show that, after a burn-in of order 𝑛 𝑛 log 𝑛, individual chains have row norms of order 𝑘+log with high probability and 𝑛 thus are in high-contraction regions; see Section C. 3. We next consider the contraction of two copies of Kac’s walk that are started very close to each other, over time periods of 𝑇epoch ≈ 𝑛 log(𝑛) steps. Using Lemma B.2, we combine the above burn-in estimates to show that these chains spend most of their time in high-contraction regions, the contraction estimate (3.4) in these highcontraction regions, and the non-expansion bound (C.3) outside of these regions, to obtain the multi-step contraction estimate (C.2) in Lemma C.4. 4. We apply a standard path-coupling result, Lemma 3.3, to go from these local contraction estimates to global contraction estimates.. The lower bound on the variance is a rather involved representation-theoretic argument, contained in Section D. Compared to standard variance lower bounds in [Wei25], the main difficulty here is illustrated by the fact that some nontrivial polynomials in the matrix entries, such as ∑𝑖,𝑗 𝑋𝑖,𝑗2 , have 0 variance under the Haar measure. For this reason, it is impossible to get any nontrivial lower bound purely in terms of the sizes of the coefficients, and any calculation must deal with very nontrivial correlation after “projecting away” from the space of zero-variance polynomials. The majority of our argument consists of projecting to a space of polynomials with nonzero variance, then carrying out exact calculations using the well-understood representations of (𝑛). These are combined with a general projection inequality, Theorem D.3, that might be useful for other statistical problems on manifolds. Finally, in terms of applications, we also show how our main results can be applied to get nontrivial bounds for a real algorithm: the fast Johnson-Lindenstrauss transform (see Theorem 6.1). The basic proof strategy is very similar to the elementary proof of the famous Johnson-Lindenstrauss theorem in [DG03]: we merely replace the bounds on exponential moments in [DG03] by bounds on moments of polynomials with low degree and propagate these changes.

3

Contraction in Columns of Kac’s Walk

The main ingredient in the proof of Theorem 2 is a proof that certain functions of Kac’s walk mix much more quickly than the walk itself. In this section, we make this precise and prove the following mixing bound (with some notation made precise later in this section):

11

Theorem 3 (Global Multi-Step Contraction). Fix 𝑛 ∈ ℕ and 𝑘 ∈ ℕ with 1 ≤ 𝑘 < 𝑛. Let 𝑃 be the one-step transition kernel of the 𝑘-column walk on St(𝑛, 𝑘), let 𝐷 be the Riemannian distance on St(𝑛, 𝑘), and let 𝑊𝐷 be Wasserstein distance with cost 𝐷. Then there exists a constant 𝐶 > 0 such that, for every 𝑇 ≥ 0 and every 𝑋0 , 𝑌0 ∈ St(𝑛, 𝑘), 𝑇

−

𝑊𝐷 (𝑃 𝑇 (𝑋0 , ⋅), 𝑃 𝑇 (𝑌0 , ⋅)) ≤ 𝑛 ⌊ 𝐶𝑛(𝑘+log(𝑛)) log(𝑛) ⌋ 𝐷(𝑋0 , 𝑌0 ). The case 𝑘 = 𝑛 is the full Kac walk on (𝑛) and is already covered by [Oli09], so we restrict the statement and proof to 1 ≤ 𝑘 < 𝑛. The proof is completed at the end of this section, using the epoch estimate proved in Section C. The proof relies on somewhat lengthy calculations on St(𝑛, 𝑘), so we introduce notation before returning to the Markov chain itself.

3.1

Notation and Basic Facts Related to Geometry

We write

(𝑛) = {𝑄 ∈ ℝ𝑛×𝑛 ∶ 𝑄 ⊤ 𝑄 = 𝐼𝑛 , det(𝑄) = 1}.

We will typically equip (𝑛) with the Riemannian structure induced by the HilbertSchmidt inner product ⟨𝐴, 𝐵⟩ ≡ Tr(𝐴⊤ 𝐵),

𝐴, 𝐵 ∈ ℝ𝑛×𝑛 .

The tangent space at the identity is the Lie algebra of skew-symmetric matrices so(𝑛) = {𝐴 ∈ ℝ𝑛×𝑛 ∶ 𝐴⊤ = −𝐴}, and the tangent space at a general point 𝑄 ∈ (𝑛) is 𝑇𝑄 (𝑛) = {𝐴𝑄 ∶ 𝐴 ∈ so(𝑛)}. For 1 ≤ 𝑖 < 𝑗 ≤ 𝑛, define the skew-symmetric matrix 1 𝑎𝑖𝑗 = √ (𝑒𝑖 𝑒𝑗⊤ − 𝑒𝑗 𝑒𝑖⊤ ) ∈ so(𝑛), 2 where {𝑒1 , … , 𝑒𝑛 } is the standard basis of ℝ𝑛 . We note that {𝑎𝑖𝑗 }1≤𝑖<𝑗≤𝑛 is an orthonormal basis of so(𝑛). For convenience, we define 𝑎𝑗𝑖 = 𝑎𝑖𝑗 for 𝑖 > 𝑗, noting that adding these to the earlier basis would of course prevent it from being a basis. For 1 ≤ 𝑘 ≤ 𝑛, the Stiefel manifold is St(𝑛, 𝑘) = {𝑋 ∈ ℝ𝑛×𝑘 ∶ 𝑋 ⊤ 𝑋 = 𝐼𝑘 }. The tangent space at 𝑋 ∈ St(𝑛, 𝑘) is 𝑇𝑋 St(𝑛, 𝑘) = {𝐻 ∈ ℝ𝑛×𝑘 ∶ 𝑋 ⊤ 𝐻 + 𝐻 ⊤ 𝑋 = 0}. 12

For two matrices 𝑥, 𝑦 ∈ St(𝑛, 𝑘), we denote by ‖𝑥 − 𝑦‖ the usual Frobenius norm. This agrees with the Hilbert-Schmidt norm on (𝑛) when 𝑛 = 𝑘. Let 𝐷 be the Riemannian metric on St(𝑛, 𝑘) obtained by viewing St(𝑛, 𝑘) as an embedded submanifold of ℝ𝑛𝑘 . If 𝑋 ∈ (𝑛), denote by 𝑘 (𝑋 ) ∈ St(𝑛, 𝑘) the first 𝑘 columns of 𝑋 . We note that, if {𝑋𝑡 } is a copy of Kac’s walk, then {𝑘 (𝑋𝑡 )} is also a Markov chain. We call this chain the 𝑘-column walk. Finally, for 𝑖 ∈ [𝑛] and 𝑋 ∈ St(𝑛, 𝑘), we will let 𝑟𝑖 (𝑋 ) = (𝑋 [𝑖, 1], … , 𝑋 [𝑖, 𝑘]) be the 𝑖-th row of 𝑋 . Define ‖𝑋 ‖2𝑟𝑜𝑤,∞ = max𝑖 ‖𝑟𝑖 (𝑋 )‖2 . In addition to this notation, we record some basic relationships between the main metrics of interest. For all 𝑥, 𝑦 ∈ St(𝑛, 𝑘), ‖𝑥 − 𝑦‖ ≤ 𝐷(𝑥, 𝑦).

(3.1)

In the other direction, we claim that there exist universal constants 𝐶𝐷 < ∞ and 𝜌𝐷 > 0 not depending on 𝑛 or 𝑘 such that, whenever ‖𝑥 − 𝑦‖ ≤ 𝜌𝐷 , 𝐷(𝑥, 𝑦) ≤ ‖𝑥 − 𝑦‖ + 𝐶𝐷 ‖𝑥 − 𝑦‖2 .

(3.2)

We believe that inequality (3.2) is standard, though we don’t know a reference. See Lemma A.4 for a complete proof.

3.2

Local Contraction and Averaging

The first important step in our argument is a local contraction estimate in Frobenius norm. The coupling used in the proof below optimizes over the two rows updated by one step of Kac’s walk. For 𝑘 = 𝑛 the angle in (3.7) agrees with the angle in [Oli09] up to first-order terms, but in general it can be substantially different. Lemma 3.1 (Local Contraction Bound). There is a universal constant 𝑐loc > 0 such that the following holds. Let 𝑋 , 𝑌 ∈ St(𝑛, 𝑘) satisfy ‖𝑋 − 𝑌 ‖ ≤ 1, and let 𝑀 = max max ‖𝑟𝑎 (𝑋 )‖2 , max ‖𝑟𝑎 (𝑌 )‖2 . ( 𝑎∈[𝑛] ) 𝑎∈[𝑛] Then there is a coupling (𝑋 ′ , 𝑌 ′ ) of one step of the 𝑘-column walk from 𝑋 and 𝑌 such that 𝔼[‖𝑋 ′ − 𝑌 ′ ‖2 ∣ 𝑋 , 𝑌 ] ≤ (1 −

𝑐loc ‖𝑋 − 𝑌 ‖2 . 𝑀𝑛2 )

(3.3)

After decreasing 𝑐loc by a universal factor, the same coupling also satisfies the Frobeniusdistance contraction 𝔼[‖𝑋 ′ − 𝑌 ′ ‖ ∣ 𝑋 , 𝑌 ] ≤ (1 −

13

𝑐loc ‖𝑋 − 𝑌 ‖. 𝑀𝑛2 )

(3.4)

Proof. We first construct the one-step coupling. Sample 𝑖, 𝑗 uniformly from {𝑖, 𝑗 ∈ [𝑛] ∶ 1 ≤ 𝑖 < 𝑗 ≤ 𝑛} and sample 𝜃 uniformly from [0, 2𝜋). For an angle shift 𝛼 = 𝛼(𝑋 , 𝑌 , 𝑖, 𝑗), set 𝑋 ′ = 𝑅𝑖𝑗 (𝜃)𝑋 ,

(3.5)

𝑌 ′ = 𝑅𝑖𝑗 (𝜃 + 𝛼)𝑌 .

As long as 𝛼 is a deterministic function of 𝑋 , 𝑌 , 𝑖, 𝑗, (3.5) is a valid coupling of the two one-step marginals: conditionally on 𝑋 , 𝑌 , 𝑖, 𝑗, the shifted angle 𝜃 + 𝛼 is uniform modulo 2𝜋. We now choose 𝛼. For the selected pair (𝑖, 𝑗), write 𝐵𝑋𝑖𝑗 =

𝑟𝑖 (𝑋 ) , (𝑟𝑗 (𝑋 ))

𝐵𝑌𝑖𝑗 =

𝑟𝑖 (𝑌 ) ∈ ℝ2×𝑘 , (𝑟𝑗 (𝑌 ))

𝐽 =

0 1 . (−1 0)

Define 𝑝𝑖𝑗 = ⟨𝐵𝑋𝑖𝑗 , 𝐵𝑌𝑖𝑗 ⟩𝐹 ,

𝑞𝑖𝑗 = ⟨𝐵𝑋𝑖𝑗 , 𝐽 𝐵𝑌𝑖𝑗 ⟩𝐹 .

(3.6)

If 𝑝𝑖𝑗2 + 𝑞𝑖𝑗2 > 0, define 𝛼 ̂𝑖𝑗 (𝑋 , 𝑌 ) ∈ (−𝜋, 𝜋] by 𝑝𝑖𝑗 , cos 𝛼 ̂𝑖𝑗 (𝑋 , 𝑌 ) = √ 𝑝𝑖𝑗2 + 𝑞𝑖𝑗2

sin 𝛼 ̂𝑖𝑗 (𝑋 , 𝑌 ) = √

𝑞𝑖𝑗 𝑝𝑖𝑗2 + 𝑞𝑖𝑗2

.

(3.7)

If 𝑝𝑖𝑗 = 𝑞𝑖𝑗 = 0, set 𝛼 ̂𝑖𝑗 (𝑋 , 𝑌 ) = 0. In (3.5), we take 𝛼 = 𝛼 ̂𝑖𝑗 (𝑋 , 𝑌 ). This choice maximizes the two-row overlap ⟨𝐵𝑋𝑖𝑗 , 𝑅𝛼(2) 𝐵𝑌𝑖𝑗 ⟩𝐹 = 𝑝𝑖𝑗 cos 𝛼 + 𝑞𝑖𝑗 sin 𝛼,

(3.8)

cos 𝛼 sin 𝛼 . For every angle 𝛼, applying the common inverse rotation (− sin 𝛼 cos 𝛼) 𝑅𝑖𝑗 (−𝜃) to both points in (3.5) gives

where 𝑅𝛼(2) =

‖𝑋 − 𝑅𝑖𝑗 (𝛼)𝑌 ‖2 = ‖𝑋 − 𝑌 ‖2 − 2(𝑝𝑖𝑗 cos 𝛼 + 𝑞𝑖𝑗 sin 𝛼 − 𝑝𝑖𝑗 ).

(3.9)

Combining (3.7) with (3.9) gives √ ‖𝑋 − 𝑌 ‖2 − ‖𝑋 ′ − 𝑌 ′ ‖2 = 2 ( 𝑝𝑖𝑗2 + 𝑞𝑖𝑗2 − 𝑝𝑖𝑗 ) ≡ Δ𝑖𝑗 . If

(3.10)

𝑀 ≥ max(‖𝑋 ‖2𝑟𝑜𝑤,∞ , ‖𝑌 ‖2𝑟𝑜𝑤,∞ ),

then |𝑝𝑖𝑗 |, |𝑞𝑖𝑗 | ≤ ‖𝐵𝑋𝑖𝑗 ‖𝐹 ‖𝐵𝑌𝑖𝑗 ‖𝐹 ≤ 2𝑀. We claim that there exists a universal constant 𝑐Δ > 0 such that 𝑐Δ Δ𝑖𝑗 ≥ 𝑞𝑖𝑗2 . (3.11) 𝑀 14

If 𝑞𝑖𝑗 = 0 the claim is trivial. Otherwise, rewriting Equation (3.10) gives 𝑞𝑖𝑗2 Δ𝑖𝑗 = 2 √ , 𝑝𝑖𝑗2 + 𝑞𝑖𝑗2 + 𝑝𝑖𝑗 and the denominator is at most 6𝑀. Let 𝐾 = 𝑌 − 𝑋 . By (3.10) and (3.11), 𝔼[‖𝑋 ′ − 𝑌 ′ ‖2 ∣ 𝑋 , 𝑌 ] ≤ ‖𝐾 ‖2 −

𝑐Δ ∑ 𝑞𝑖𝑗2 . 𝑛 𝑀 (2) 𝑖<𝑗

Since 𝐵𝑌𝑖𝑗 = 𝐵𝑋𝑖𝑗 + 𝐵𝐾𝑖𝑗 and ⟨𝐵𝑋𝑖𝑗 , 𝐽 𝐵𝑋𝑖𝑗 ⟩𝐹 = 0, we have 𝑞𝑖𝑗 = 𝑟𝑖 (𝑋 ) ⋅ 𝑟𝑗 (𝐾 ) − 𝑟𝑗 (𝑋 ) ⋅ 𝑟𝑖 (𝐾 ). Lemma A.1 gives, for ‖𝐾 ‖ ≤ 1,

3 ∑ 𝑞𝑖𝑗2 ≥ ‖𝐾 ‖2 . 4 𝑖<𝑗

Combining (3.11) with Lemma A.1, and decreasing the√universal constant if necessary, gives (3.3). Jensen’s inequality and the standard bound 1 − 𝑢 ≤ 1 − 𝑢/2 then give (3.4), again after decreasing 𝑐loc by a universal factor. Because the term 𝑀 appearing in Lemma 3.1 can be as large as 1, the contraction bound in Lemma 3.1 can be of the order (1 − Θ(𝑛−2 )) for the worst-case starting points 𝑋 , 𝑌 . This poor contraction is real, not merely an artifact of the proof strategy. We get around this 𝑛 problem by showing that 𝑀 is typically of order 𝑘+log after a burn-in of order Ω(𝑛 log 𝑛). 𝑛 The details of this calculation are given in Appendix C. The main estimate we need from that appendix is the following consequence of Lemma C.4. Corollary 3.2. Let 𝑃 be the one-step transition kernel of the 𝑘-column walk and let 𝑊𝐷 denote Wasserstein distance with cost 𝐷. There are universal constants 𝐶, 𝜌loc > 0 with the following property. For all sufficiently large 𝑛, if 𝑥, 𝑦 ∈ St(𝑛, 𝑘) satisfy 𝐷(𝑥, 𝑦) ≤ 𝜌loc , then 𝑊𝐷 (𝑃 𝑇epoch (𝑥, ⋅), 𝑃 𝑇epoch (𝑦, ⋅)) ≤ 𝑛−1 𝐷(𝑥, 𝑦), where 𝑇epoch is as in Definition C.3 and satisfies 𝑇epoch ≤ 𝐶𝑛(𝑘 + log 𝑛) log 𝑛.

15

(3.12)

3.3

From Local to Global Contraction

We use the standard local-to-global criterion for Wasserstein contraction on a geodesic metric space. The following lemma follows immediately from [Pau16, Proposition 3.1] and [Oll09, Propositions 19 and 20]. It is not substantially different from the original path-coupling argument of [BD97], except for technical difficulties related to being on a continuous state space. Lemma 3.3 (Local-to-global Wasserstein contraction). Let (𝐸, 𝐷) be a compact geodesic metric space and let 𝐾 be a Markov kernel on 𝐸. Let 𝑊𝐷 denote Wasserstein distance with cost 𝐷. Suppose that, for some 𝜌 > 0 and 𝜆 ∈ [0, 1), 𝑊𝐷 (𝐾 (𝑥, ⋅), 𝐾 (𝑦, ⋅)) ≤ 𝜆𝐷(𝑥, 𝑦)

whenever 𝐷(𝑥, 𝑦) ≤ 𝜌.

(3.13)

Then, for all 𝑥, 𝑦 ∈ 𝐸, 𝑊𝐷 (𝐾 (𝑥, ⋅), 𝐾 (𝑦, ⋅)) ≤ 𝜆𝐷(𝑥, 𝑦).

(3.14)

Consequently, for all probability measures 𝜇, 𝜈 on 𝐸, 𝑊𝐷 (𝜇𝐾 , 𝜈𝐾 ) ≤ 𝜆𝑊𝐷 (𝜇, 𝜈).

(3.15)

We are now ready to prove Theorem 3. Proof of Theorem 3. Let 𝑃 be the one-step transition kernel of the 𝑘-column walk and set 𝐾 = 𝑃 𝑇epoch . By Corollary 3.2, for all 𝑥, 𝑦 ∈ St(𝑛, 𝑘) with 𝐷(𝑥, 𝑦) ≤ 𝜌loc , 𝑊𝐷 (𝐾 (𝑥, ⋅), 𝐾 (𝑦, ⋅)) ≤ 𝑛−1 𝐷(𝑥, 𝑦).

(3.16)

For 1 ≤ 𝑘 < 𝑛, the space St(𝑛, 𝑘) with the Riemannian distance 𝐷 is a compact geodesic metric space.4 Applying Lemma 3.3 to (3.16), with 𝜌 = 𝜌loc and 𝜆 = 𝑛−1 , gives 𝑊𝐷 (𝐾 (𝑥, ⋅), 𝐾 (𝑦, ⋅)) ≤ 𝑛−1 𝐷(𝑥, 𝑦)

(3.17)

for all 𝑥, 𝑦 ∈ St(𝑛, 𝑘). The measure-level conclusion (3.15) gives the same contraction after each subsequent epoch. Let 𝑟 = ⌊𝑇 /𝑇epoch ⌋ and write 𝑇 = 𝑟𝑇epoch + 𝑠 with 0 ≤ 𝑠 < 𝑇epoch . Iterating (3.15) with 𝐾 = 𝑃 𝑇epoch and 𝜆 = 𝑛−1 gives 𝑊𝐷 (𝑃 𝑟𝑇epoch (𝑋0 , ⋅), 𝑃 𝑟𝑇epoch (𝑌0 , ⋅)) ≤ 𝑛−𝑟 𝐷(𝑋0 , 𝑌0 ). Since our coupling is non-expansive (see Lemma A.5), the last 𝑠 steps cannot increase the distance between the chains, and therefore cannot increase the expected distance. This completes the proof. 4

The only non-obvious part of this claim is the fact that any two points are joined by a minimizing geodesic. This is the content of the Hopf–Rinow theorem; see, for example, [Lee18, Theorem 6.13].

16

4

Bounds on Moments of Polynomials

We give bounds on the moments of low-degree polynomials under both (a) Haar measure and (b) the measure of Kac’s walk on (𝑛) after 𝑇 steps.

4.1

Upper Bounds on Differences of Means

We use the bounds in Section 3. Recall 𝛽𝑛,𝑇 ,𝑥 is the distribution of a copy of Kac’s walk on (𝑛) started at 𝑋0 = 𝑥 after 𝑇 steps, and 𝛼𝑛 is the Haar measure on (𝑛). Our main estimate is: Theorem 4.1. For 𝑛 ∈ ℕ, fix 1 ≤ 𝑘 < 𝑛 and 𝑇 ≥ 0. Then fix a function 𝑓 = 𝑓𝑛 with 𝑓 ∶ (𝑛) ↦ ℝ of the form 𝑘

𝑓 (𝑋 ) = ∏ 𝑋 [𝑖𝑟 , 𝑗𝑟 ]. 𝑟=1

Let 𝐶 > 0 be the constant appearing in the statement of Theorem 3 and let −

𝑇

𝜔𝑛 = 𝐶diam 𝑘 𝑛 ⌊ 𝐶𝑛(𝑘+log(𝑛)) log(𝑛) ⌋

(4.1)

be the upper bound obtained in that theorem.5 There exists some universal constant 𝑁0 so that, for all 𝑛 > 𝑁0 and all 𝑥 ∈ (𝑛), √ |𝛽𝑛,𝑇 ,𝑥 (𝑓 ) − 𝛼𝑛 (𝑓 )| ≤ 2 2𝑘 𝜔𝑛 . Proof. For convenience, define the sequences √ 2𝜔𝑛 𝜀𝑛 = , 𝑘

𝛿𝑛 =

𝜔𝑛 . 𝜀𝑛

(4.2)

We note that 𝑓 (𝑥) depends on only the entries of 𝑥 that appear in columns in the set {𝑗𝑟 }𝑘𝑟=1 , and this set clearly has at most 𝑘 entries. Without loss of generality, assume that {𝑗𝑟 }𝑘𝑟=1 ⊂ [𝑘]. The proof of Theorem 3 also gives the same contraction for any starting distribution, not merely point masses. Applying this to the point mass at 𝑘 (𝑥) and to the stationary 𝑘-column Haar law gives, by the definition of 𝜔𝑛 in (4.1), 𝑊𝐷 ((𝑘 (𝑋𝑇 )), (𝑘 (𝑌 ))) ≤ 𝜔𝑛 , where 𝑌 ∼ 𝛼𝑛 . Since St(𝑛, 𝑘) is compact, this Wasserstein distance is realized by an optimal transport plan. Thus we can couple 𝑘 (𝑋𝑇 ) to 𝑘 (𝑌 ) so that 𝔼[𝐷(𝑘 (𝑋𝑇 ), 𝑘 (𝑌 ))] ≤ 𝜔𝑛 . Hence Markov’s inequality gives ℙ[𝐷(𝑘 (𝑋𝑇 ), 𝑘 (𝑌 )) > 𝜀𝑛 ] ≤ 𝛿𝑛 . 5

(4.3)

Here we replace 𝐷(𝑋 , 𝑌 ) with the upper bound 𝐶diam 𝑘, where 𝐶diam is a universal constant chosen so that the diameter of St(𝑛, 𝑘) with respect to the Riemannian distance 𝐷 is at most 𝐶diam 𝑘.

17

Next, we obtain entrywise bounds. Denote by ‖ ⋅ ‖∞ the entrywise supnorm. By (3.1), we have ‖𝑘 (𝑋𝑇 ) − 𝑘 (𝑌 )‖ ≤ 𝐷(𝑘 (𝑋𝑇 ), 𝑘 (𝑌 )), and the standard norm inequality ‖𝐴‖∞ ≤ ‖𝐴‖ implies ℙ[‖𝑘 (𝑋𝑇 ) − 𝑘 (𝑌 )‖∞ > 𝜀𝑛 ] ≤ 𝛿𝑛 .

(4.4)

On the event {‖𝑘 (𝑋𝑇 ) − 𝑘 (𝑌 )‖∞ ≤ 𝜀𝑛 }, we have6 |𝑓 (𝑋𝑇 ) − 𝑓 (𝑌 )| ≤ 𝑘 𝜀𝑛 . Combining this with Inequality (4.4), and using the deterministic bound |𝑓 (𝑥)| ≤ 1, we conclude √ |𝔼[𝑓 (𝑋𝑇 )] − 𝔼[𝑓 (𝑌 )]| ≤ 𝑘 𝜀𝑛 + 2𝛿𝑛 = 2 2𝑘 𝜔𝑛 .

4.2

Lower Bounds on Variances

For a polynomial 𝑓 (𝑥) = ∑𝑢 𝑐𝑢 𝑥 𝑢 , define the 𝐿2 norm of the coefficients by ‖𝑓 ‖𝑐𝑜𝑒𝑓 𝑓 ,𝑝 = 𝑝

1

𝑝 (∑𝑢 𝑐𝑢 ) . The following is an immediate consequence of Corollary D.5:

Theorem 4.2. Fix a degree-𝑘 polynomial 𝑓 ∶ (𝑛) ↦ ℝ with mean 𝛼𝑛 (𝑓 ) = 0 under the Haar measure. Then there exists a polynomial 𝑓 ∗ ∶ (𝑛) ↦ ℝ such that, for all 𝑥 ∈ (𝑛), 𝑓 (𝑥) = 𝑓 ∗ (𝑥), and ∗

𝑉 𝑎𝑟𝛼𝑛 (𝑓 ) ≥

‖𝑓 ∗ ‖2𝑐𝑜𝑒𝑓 𝑓 ,2 (𝑘 + 1)𝑛𝑘

.

Here 𝑓 ∗ is obtained from the projection 𝑇 ♯ defined in Equation (D.13), after choosing a degree-at-most-𝑘 representative of 𝑓 . As it is somewhat unusual, we explain why the “reduced” form 𝑓 ∗ is required. While two polynomials with distinct coefficients can never agree over all of ℝ𝑑 , two such polynomials can agree on (𝑛). A typical example is the polynomial 𝑓 (𝑥) = ∑𝑛𝑖,𝑗=1 𝑥[𝑖, 𝑗]2 , which is equal to the constant polynomial 𝑔(𝑥) ≡ 𝑛 over (𝑛) (and in particular 𝑓 has variance 0 with respect to Haar measure). For this reason, it is impossible to obtain a variance lower bound in terms of the norm of the coefficients for “unreduced” polynomials, but such a bound turns out to hold for these “reduced” polynomials. 6

We are using a standard telescoping-sum argument here. See Lemma B.1 in the appendix for a detailed calculation of the telescoping-sum identity; we then apply the triangle inequality to the result.

18

5

Proof of Our Main Theorem (Theorem 2)

Let us first restate Theorem 2 here for convenience. Theorem (Theorem 2, copied). Fix a sequence 𝑘 = 𝑘(𝑛) and a sequence 𝑇 = 𝑇 (𝑛) satisfying 𝑇 (𝑛) = 𝜔(𝑛𝑘 ⋅ (𝑘 + log 𝑛) ⋅ log 𝑛), 𝛽𝑛,𝑇 ,𝑥 and 𝛼𝑛 are weakly 𝑘(𝑛)-indistinguishable in the sense of Definition 2.2. Fix a polynomial 𝑓 ; since replacing 𝑓 by the “reduced” polynomial 𝑓 ∗ appearing in the statement of Theorem 4.2 doesn’t change its value on (𝑛), we can assume without loss of generality that 𝑓 is reduced in this sense (see Equation (D.13) for an explicit formula for this reduction). Similarly, by simply dividing through the entire polynomial by a constant, we can assume without loss of generality that ‖𝑓 ∗ ‖2𝑐𝑜𝑒𝑓 𝑓 ,2 = 1. By Theorem 4.2, 𝑉 𝑎𝑟𝛼𝑛 (𝑓 ) ≥

1 . (𝑘 + 1)𝑛𝑘

(5.1)

Next, we compare this to the differences. By Cauchy–Schwarz and the graded coefficient √ representation used in Corollary D.5, ‖𝑓 ‖𝑐𝑜𝑒𝑓 𝑓 ,1 ≤ 𝑘 + 1 𝑛𝑘 . By Theorem 4.1 and linearity of expectations, there exists a universal constant 𝐶 > 0 so that −

𝑇

|𝛽𝑛,𝑇 ,𝑥 (𝑓 ) − 𝛼𝑛 (𝑓 )|2 ≤ 8𝐶diam (𝑘 + 1)𝑘 2 𝑛2𝑘 𝑛 ⌊ 𝐶𝑛(𝑘+log(𝑛)) log(𝑛) ⌋

(5.2)

Comparing Inequalities (5.1) and (5.2), we see that 𝑇 |𝛽𝑛,𝑇 ,𝑥 (𝑓 ) − 𝛼𝑛 (𝑓 )|2 − ≤ 8𝐶diam (𝑘 + 1)2 𝑘 2 𝑛3𝑘 𝑛 ⌊ 𝐶𝑛(𝑘+log(𝑛)) log(𝑛) ⌋ 𝑉 𝑎𝑟𝛼𝑛 (𝑓 )

(5.3)

The polynomial prefactor contributes only (𝑘 + 1)2 𝑘 2 𝑛3𝑘 , while the contraction factor contributes 𝑛−𝑟 with 𝑇 𝑟= . ⌊ 𝐶𝑛(𝑘 + log 𝑛) log 𝑛 ⌋ meaning that the quantity on the LHS in equation 5.3 tends to 0 superpolynomially fast if 𝑇 = 𝜔(𝑛𝑘 ⋅ (𝑘 + log 𝑛) ⋅ log 𝑛).

6 An Application to a Fast Johnson-Lindenstrauss Transform In this section, we show that the matrix obtained from running Kac’s walk gives a Johnson– Lindenstrauss transform at the usual target dimension, provided the walk is run long enough to control the low moments used below. This confirms the Johnson–Lindenstrauss conjecture from [AC06], up to the extra logarithmic factor in the running time appearing in Theorem 6.1. 19

Let Π𝓁 ∶ ℝ𝑛 → ℝ𝓁 be the coordinate projection onto the first 𝓁 coordinates. For 𝐺 ∈ (𝑛), define √ 𝑛 Π𝓁 𝐺. (6.1) 𝐴𝐺 = 𝓁 For a unit vector 𝑣 ∈ 𝕊𝑛−1 , define the squared-norm distortion 𝓁

𝑍𝑣 (𝐺) = ‖𝐴𝐺 𝑣‖22 − 1 =

𝑛 ∑⟨𝑒𝑎 , 𝐺𝑣⟩2 − 1. 𝓁 𝑎=1

(6.2)

Thus 𝑍𝑣 (𝐺) is a degree-2 polynomial in the entries of 𝐺. For a finite set  = {𝑥1 , … , 𝑥𝑁 } ⊂ ℝ𝑛 , define } { 𝑥𝑖 − 𝑥𝑗 ∶ 1 ≤ 𝑖 < 𝑗 ≤ 𝑁 , 𝑥𝑖 ≠ 𝑥𝑗 . (6.3)  = ‖𝑥𝑖 − 𝑥𝑗 ‖2 For 𝑣 = (𝑥𝑖 − 𝑥𝑗 )/‖𝑥𝑖 − 𝑥𝑗 ‖2 , the identity (6.2) gives 𝑍𝑣 (𝐺) =

‖𝐴𝐺 (𝑥𝑖 − 𝑥𝑗 )‖22 − 1. ‖𝑥𝑖 − 𝑥𝑗 ‖22

(6.4)

Consequently, controlling |𝑍𝑣 (𝐺)| for every 𝑣 ∈  is exactly the Johnson–Lindenstrauss condition for the point set . The application of our estimates to Kac’s walk to the JL transform is the following. Theorem 6.1 (Kac’s walk applied to the Johnson–Lindenstrauss transform). There is a universal constant 𝐶JL < ∞ such that the following holds. Let 𝑛 ≥ 2, let 𝑥 ∈ (𝑛), and let 𝑀 ∼ 𝛽𝑛,𝑇 ,𝑥 be the endpoint of 𝑇 steps of Kac’s walk started from 𝑥. Let  ⊂ ℝ𝑛 have 𝑁 ≥ 2 points, and let 0 < 𝜀, 𝛿 < 1/2. Set 𝑁 , 𝑟 = log ⌈ 𝛿⌉

(6.5)

and assume 4𝑟 < 𝑛. Let 𝓁 be an integer satisfying 𝐶JL 𝜀 −2 𝑟 ≤ 𝓁 < 𝑛.

(6.6)

𝑛 𝑁 𝑇 ≥ 𝐶JL 𝑛(4𝑟 + log 𝑛) 𝑟 log + log , ( 𝜀 𝛿)

(6.7)

If

then, with probability at least 1 − 𝛿 over 𝑀 ∼ 𝛽𝑛,𝑇 ,𝑥 , (1 − 𝜀)‖𝑥𝑖 − 𝑥𝑗 ‖22 ≤ ‖𝐴𝑀 (𝑥𝑖 − 𝑥𝑗 )‖22 ≤ (1 + 𝜀)‖𝑥𝑖 − 𝑥𝑗 ‖22

(6.8)

for every pair 1 ≤ 𝑖 < 𝑗 ≤ 𝑁 . In particular, for fixed 𝜀 and 𝑁 /𝛿 ≤ 𝑛𝐴 , with 𝐴 < ∞ fixed, the usual Johnson–Lindenstrauss target dimension 𝓁 = 𝑂(𝜀 −2 log(𝑁 /𝛿)) = 𝑂𝐴 (𝜀 −2 log 𝑛) is achieved by taking 𝑇 ≥ 𝐶𝐴 𝑛 log3 𝑛. 20

When 𝑥 = 𝐼𝑛 , the map 𝑣 ↦ 𝐴𝑀 𝑣 can be applied by successively applying the 𝑇 elementary rotations and then projecting to the first 𝓁 coordinates. Thus the arithmetic ̃ cost per vector is 𝑂(𝑇 + 𝓁); in the polynomial-size regime described above this is 𝑂(𝑛), compared with the 𝑂(𝑛𝓁) cost of applying a dense 𝓁 × 𝑛 projection matrix. The proof is given in Section E.

7

Open Questions

7.1

Immediate Open Questions

There are several natural open questions that come out of our work: • Can the 𝑘-column mixing result be extended to TV distance and not just Wasserstein? This appears plausible, and we leave it for future work. • Can we tighten the polynomial indistinguishability result? First, recall that our √ Theorem 2 stops being interesting for 𝑘 ≈ 𝑛: can we extend this all the way to 𝑘 ≈ 𝑛? Secondly, to be indistinguishable against degree-𝑘 polynomials, we need the walk to run for roughly 𝑛𝑘 2 steps: is that necessary? • Finally, a very natural question is whether low-degree polynomials of the spectrum of a Kac matrix can be a good distinguisher. It seems plausible that the answer is no: the basic intuition here is just that the spectral measure is a “nice” function of only n “pretty independent” numbers, so should mix in 𝑛poly(log 𝑛) steps. However, making this argument formally appears more difficult, since the spectrum is not quite a Markov chain (in contrast to the columns that we analyze here, which are).

7.2

Trapdoored Functions

While this work is about trapdoor matrices, one could investigate trapdoor functions more generally. What we really want is a random walk on functions, so that (i) it is easy to evaluate (trapdoored) functions based on short walks, and furthermore (ii) the functions can “hide” in a bigger class of functions that cannot be evaluated quickly. That is, we have a “big” space of circuits that are mostly “slow,” then we hide a “small” space of circuits that are all “fast” inside it. For matrix multiplication, something magic happens in part (ii) — compositions of matrices are matrices, so the hiding is essentially automatic. Are there other classes of functions for which such hiding is automatic? Do any of them have worse complexity than 𝑛2 ? In one extreme, when the class of functions is all functions say from {0, 1}𝑛 → {0, 1}𝑛 , the cryptographic notion of pseudorandom functions [GGM86] provides a solution. But how about, say, when the class of functions is all functions that can be computed by circuits of size 𝑛100 ? Can circuits of size 𝑛5 hide amongst them? 21

References [AC06] Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’06, page 557–563, New York, NY, USA, 2006. Association for Computing Machinery. 3, 6, 19 [AL13] Nir Ailon and Edo Liberty. An almost optimal unrestricted fast JohnsonLindenstrauss transform. ACM Transactions on Algorithms, 9(3):1–12, 2013. 6 [BD97] Russ Bubley and Martin E. Dyer. Path coupling: A technique for proving rapid mixing in Markov chains. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS ’97), pages 223–231. IEEE Computer Society, 1997. 16 [BH25] Anna Ben-Hamou. Mixing time of a matrix random walk generated by elementary transvections. Electronic Communications in Probability, 30(78):1–5, 2025. 7 [BHJK25] Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain, and Pravesh K. Kothari. The quasi-polynomial low-degree conjecture is false. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 2577–2590. IEEE, 2025. 5 [BHP18] Anna Ben-Hamou and Yuval Peres. Cutoff for a stratified random walk on the hypercube. Electronic Communications in Probability, 23(32):1–10, 2018. 7 [BK21] Stefan Bamberger and Felix Krahmer. Optimal fast Johnson-Lindenstrauss embeddings for large data sets. Sampling Theory, Signal Processing, and Data Analysis, 19(1), 2021. 6 [BLR90] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 73–83. ACM, 1990. 7 [BN25] Mark Braverman and Stephen Newman. Practical secure delegated linear algebra with trapdoored matrices. In Benny Applebaum and Huijia (Rachel) Lin, editors, Theory of Cryptography - 23rd International Conference, TCC 2025, Aarhus, Denmark, December 1-5, 2025, Proceedings, Part I, volume 16268 of Lecture Notes in Computer Science, pages 97–118. Springer, 2025. 6, 7

22

[CCL03] Eric A. Carlen, Maria C. Carvalho, and Michael Loss. Determination of the spectral gap for Kac’s master equation and related stochastic evolution. Acta Mathematica, 191(1):1–54, 2003. 2 [CHH+ 25] Chi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu, Tony Metger, and Xinyu Tan. Incompressibility and spectral gaps of random circuits. In 66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia, December 14-17, 2025, pages 1304–1312. IEEE, 2025. 7 [CMN21] B. Collins, S. Matsumoto, and J. Novak. The weingarten calculus. Notices of the American Mathematical Society, 2021. 5 [Dev86] Luc Devroye. Non-Uniform Random Variate Generation. Springer Series in Statistics. Springer-Verlag, New York, 1986. 27 [DG03] Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures & Algorithms, 22(1):60–65, 2003. 11, 45 [DKS10] Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós. A sparse JohnsonLindenstrauss transform. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC ’10, pages 341–350. Association for Computing Machinery, 2010. 6 [DSC96] Persi Diaconis and Laurent Saloff-Coste. Walks on generating sets of Abelian groups. Probability Theory and Related Fields, 105(3):393–421, 1996. 6 [DSC00] Persi Diaconis and Laurent Saloff-Coste. Bounds for Kac’s master equation. Communications in Mathematical Physics, 209(3):729–755, 2000. 2, 3 [FHL23] Ora Nova Fandina, Mikael Møller Høgsgaard, and Kasper Green Larsen. The fast Johnson-Lindenstrauss transform is even faster. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 9689–9715. PMLR, 2023. 6 [Fre79] Rūsiņš Freivalds. Fast probabilistic algorithms for verification of resultant matrices. In Mathematical Foundations of Computer Science 1979, pages 577–585. Springer, 1979. 7 [GGM86] Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. J. ACM, 33(4):792–807, 1986. 21 [Has70] W. K. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1):97–109, April 1970. 2, 5 23

[Hig08] Nicholas J. Higham. Functions of Matrices: Theory and Computation. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2008. 28 [HKK+ 26] Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari, Jerry Li, Sidhanth Mohanty, and Stefan Tiegel. Rigorous implications of the low-degree heuristic. In Aditya Bhaskara and Artur Czumaj, editors, Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC 2026, Salt Lake City, UT, USA, June 22-26, 2026, pages 1763–1770. ACM, 2026. 5 [Hop18] Samuel Hopkins. Statistical Inference and the Sum of Squares Method. PhD thesis, Cornell University, Ithaca, NY, August 2018. 4, 5 [HT23] Jakob Bæk Tejs Houen and Mikkel Thorup. A sparse Johnson-Lindenstrauss transform using fast hashing. In 50th International Colloquium on Automata, Languages, and Programming, volume 261 of Leibniz International Proceedings in Informatics, pages 76:1–76:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. 6 [Jia12] Yunjiang Jiang. Total variation bound for Kac’s random walk. The Annals of Applied Probability, 22(4):1712–1727, 2012. 3 [Jia17] Yunjiang Jiang. Kac’s random walk on the special orthogonal group mixes in polynomial time. Proceedings of the American Mathematical Society, 145(10):4533–4541, 2017. 2 [JPS+ 22] Vishesh Jain, Natesh S. Pillai, Ashwin Sah, Mehtaab Sawhney, and Aaron Smith. Fast and memory-optimal dimension reduction using Kac’s walk. The Annals of Applied Probability, 32(5):4038–4064, 2022. 4, 6 [Kac59] Mark Kac. Probability and Related Topics in Physical Sciences, volume 1 of Lectures in Applied Mathematics. Interscience Publishers, New York, 1959. 2 [KN14] Daniel M. Kane and Jelani Nelson. Sparser Johnson-Lindenstrauss transforms. Journal of the ACM, 61(1):1–23, 2014. 6 [KW11] Felix Krahmer and Rachel Ward. New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property. SIAM Journal on Mathematical Analysis, 43(3):1269–1281, 2011. 6 [Lee18] John M. Lee. Introduction to Riemannian Manifolds, volume 176 of Graduate Texts in Mathematics. Springer, Cham, 2 edition, 2018. 16 [LPW17] David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, Providence, RI, 2 edition, October 2017. 3 24

[Mas03] David K. Maslen. The eigenvalues of Kac’s master equation. Mathematische Zeitschrift, 243(2):291–331, 2003. 2 [Oli09] Roberto Imbuzeiro Oliveira. On the convergence to equilibrium of Kac’s random walk on matrices. The Annals of Applied Probability, 19(3):1200–1231, June 2009. 2, 3, 4, 5, 9, 10, 12, 13 [Oll09] Yann Ollivier. Ricci curvature of Markov chains on metric spaces. Journal of Functional Analysis, 256(3):810–864, 2009. 16 [Pau16] Daniel Paulin. Mixing and concentration by Ricci curvature. Journal of Functional Analysis, 270(5):1623–1662, 2016. 16 [PS17] Natesh S. Pillai and Aaron Smith. Kac’s walk on 𝑛-sphere mixes in 𝑛 log 𝑛 steps. The Annals of Applied Probability, 27(1):631–650, 2017. 3, 11, 31 [PS18] Natesh S. Pillai and Aaron Smith. On the mixing time of Kac’s walk and other high-dimensional Gibbs samplers with constraints. The Annals of Probability, 46(4):2345–2399, 2018. 2 [PS26a] Natesh Pillai and Aaron Smith. Mixing on 𝑘 columns of the transvection walk, 2026. 7 [PS26b] Natesh S. Pillai and Aaron Smith. Kac’s walk on rotation matrices mixes in 𝑛2 log 𝑛 steps. https://arxiv.org/abs/2604.23828, 2026. 2 [RRJW20] Maxim Rabinovich, Aaditya Ramdas, Michael I. Jordan, and Martin J. Wainwright. Function-specific mixing times and concentration away from equilibrium. Bayesian Analysis, 15(2):505–532, 2020. 5 [Sep07] Mark R. Sepanski. Compact Lie Groups, volume 235 of Graduate Texts in Mathematics. Springer, New York, 2007. 34, 37, 40, 41 [Sot16] Aikaterini Sotiraki. Authentication protocol using trapdoored matrices. Master’s thesis, Massachusetts Institute of Technology, 2016. EECS. 6, 7 [TRC21] Xinyu Tan, Narayanan Rengaswamy, and Robert Calderbank. Approximate unitary 3-designs from transvection markov chains, 2021. 7 [VZ26] Vinod Vaikuntanathan and Or Zamir. Improving algorithmic efficiency using cryptography: Trapdoored matrices and applications. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2554–2574, 2026. 4, 6, 7 [Wei25] Alexander S. Wein. Computational complexity of statistics: New insights from low-degree polynomials. arXiv preprint arXiv:2506.10748, 2025. 4, 5, 8, 11 25

A

Some Geometric Calculations

We collect some facts about the geometry of (𝑛) and St(𝑛, 𝑘). We suspect everything in this section is well-known, but include the details for completeness.

A.1

Exact row identities on the Stiefel manifold

The local contraction proof in Lemma 3.1 uses the following secant identity. Lemma A.1 (Secant row-sum identity). Let 𝑋 , 𝑌 ∈ St(𝑛, 𝑘) and set 𝐾 = 𝑌 − 𝑋 . Define 𝑞𝑖𝑗 = 𝑟𝑖 (𝑋 ) ⋅ 𝑟𝑗 (𝐾 ) − 𝑟𝑗 (𝑋 ) ⋅ 𝑟𝑖 (𝐾 ),

1 ≤ 𝑖 < 𝑗 ≤ 𝑛.

Then ∑ 𝑞𝑖𝑗2 = ‖𝐾 ‖2𝐹 − Tr((𝐾 ⊤ 𝑋 )2 ).

(A.1)

𝑖<𝑗

Moreover, 1 ∑ 𝑞𝑖𝑗2 ≥ ‖𝐾 ‖2𝐹 − ‖𝐾 ‖4𝐹 . 4 𝑖<𝑗 In particular, if ‖𝐾 ‖𝐹 ≤ 1, then

(A.2)

3 ∑ 𝑞𝑖𝑗2 ≥ ‖𝐾 ‖2𝐹 . 4 𝑖<𝑗

Proof. Set 𝐴 = 𝐾 𝑋 ⊤ ∈ ℝ𝑛×𝑛 . Then 𝐴𝑖𝑗 = 𝑟𝑖 (𝐾 ) ⋅ 𝑟𝑗 (𝑋 ), and hence 1 ∑ 𝑞𝑖𝑗2 = ∑(𝐴𝑖𝑗 − 𝐴𝑗𝑖 )2 = ‖𝐴 − 𝐴⊤ ‖2𝐹 . 2 𝑖<𝑗 𝑖<𝑗 Using 𝑋 ⊤ 𝑋 = 𝐼𝑘 and cyclicity of trace, 1 ‖𝐴 − 𝐴⊤ ‖2𝐹 = ‖𝐴‖2𝐹 − Tr(𝐴2 ) = ‖𝐾 ‖2𝐹 − Tr((𝐾 ⊤ 𝑋 )2 ), 2 which proves (A.1). Since 𝑌 = 𝑋 + 𝐾 and 𝑋 ⊤ 𝑋 = 𝑌 ⊤ 𝑌 = 𝐼𝑘 , 𝑋 ⊤ 𝐾 + 𝐾 ⊤ 𝑋 = −𝐾 ⊤ 𝐾 . Thus, writing 𝐵 = 𝐾 ⊤ 𝑋 = 𝐴0 + 𝑆0 with 𝐴0 skew-symmetric and 𝑆0 symmetric, we have 𝑆0 = −𝐾 ⊤ 𝐾 /2. Therefore 1 1 Tr(𝐵2 ) = Tr(𝐴20 ) + Tr(𝑆02 ) ≤ Tr(𝑆02 ) = ‖𝐾 ⊤ 𝐾 ‖2𝐹 ≤ ‖𝐾 ‖4𝐹 . 4 4 Plugging this into (A.1) proves (A.2). 26

A.2

Tail Bounds Supnorm of Haar-distributed Points on Sphere

The following estimate is standard but somewhat tedious to write down. Since we only need rather rough estimates, we give a sketch: Lemma A.2. Let 𝑌 be uniform on 𝕊𝑛−1 . There is a universal constant 𝐶 > 0 such that for all 𝛿 ∈ (0, 1), log(𝑛/𝛿) ℙ ‖𝑌 ‖2∞ ≥ 𝐶 ≤ 𝛿. [ ] 𝑛 𝑖𝑖𝑑

Proof sketch. Write 𝑌 = 𝑍/‖𝑍‖2 with 𝑍𝑖 ∼ 𝑁 (0, 1). By e.g. Theorem 4.1 of [Dev86], 𝑌 is distributed according to the Haar measure on the sphere. We can use (i) a union bound and standard Gaussian tail estimates to get an upper bound on max𝑖 |𝑍𝑖 |, and (ii) similar 𝜒 2 tail estimates to get a lower-tail bound for ‖𝑍‖2 . Lemma A.3 (Haar projection tail). Let 𝑌 be uniform on 𝕊𝑛−1 , and let 𝑉 ⊆ ℝ𝑛 be a fixed subspace with dim(𝑉 ) = 𝑘. There is a universal constant 𝐶 > 0 such that, for all 𝑠 ≥ 1, ℙ ‖𝑃𝑉 𝑌 ‖2 > 𝐶 [

𝑘+𝑠 ≤ 𝑒 −𝑠 . 𝑛 ]

Proof sketch. Write 𝑌 = 𝑍/‖𝑍‖ with 𝑍 ∼ 𝑁 (0, 𝐼𝑛 ), and rotate coordinates so that 𝑉 = span(𝑒1 , … , 𝑒𝑘 ). Then ‖𝑃𝑉 𝑍‖2 is 𝜒𝑘2 and ‖𝑍‖2 is 𝜒𝑛2 . Standard upper-tail bounds for 𝜒𝑘2 , together with the lower-tail bound ℙ[‖𝑍‖2 < 𝑛/2] ≤ 𝑒 −𝑐𝑛 , imply the displayed estimate after increasing 𝐶. If 𝑠 is larger than a constant multiple of 𝑛, the threshold is already at least 1 after increasing 𝐶, so the estimate is trivial.

A.3

Metric comparisons

Lemma A.4 (Metric comparison on the Stiefel manifold). Let 𝐷 be the Riemannian distance on St(𝑛, 𝑘) induced by the Frobenius inner product from the embedding St(𝑛, 𝑘) ⊂ ℝ𝑛×𝑘 . Then, for all 𝑋 , 𝑌 ∈ St(𝑛, 𝑘), ‖𝑋 − 𝑌 ‖ ≤ 𝐷(𝑋 , 𝑌 ). (A.3) Moreover, there are universal constants 𝜌𝐷 > 0 and 𝐶𝐷 < ∞, independent of 𝑛 and 𝑘, such that whenever ‖𝑋 − 𝑌 ‖ ≤ 𝜌𝐷 , 𝐷(𝑋 , 𝑌 ) ≤ ‖𝑋 − 𝑌 ‖ + 𝐶𝐷 ‖𝑋 − 𝑌 ‖2 .

(A.4)

Proof. We first prove (A.3). If 𝛾 ∶ [0, 1] → St(𝑛, 𝑘) is any piecewise 𝐶 1 curve with 𝛾 (0) = 𝑋 and 𝛾 (1) = 𝑌 , then 1 ‖ 1 ‖ ‖𝑋 − 𝑌 ‖ = ‖‖∫ 𝛾̇ (𝑡) 𝑑𝑡 ‖‖ ≤ ∫ ‖𝛾̇ (𝑡)‖ 𝑑𝑡. (A.5) 0 ‖ 0 ‖ Taking the infimum over all such curves gives (A.3). 27

We now prove the upper bound (A.4) by constructing a specific path from 𝑋 to 𝑌 and bounding its length. Set 𝐾 = 𝑌 − 𝑋, 𝛿 = ‖𝐾 ‖. (A.6) We will assume 𝛿 ≤ 1. Since 𝑋 ⊤ 𝑋 = 𝑌 ⊤ 𝑌 = 𝐼𝑘 and 𝑌 = 𝑋 + 𝐾 , we have 𝑋 ⊤ 𝐾 + 𝐾 ⊤ 𝑋 + 𝐾 ⊤ 𝐾 = 0.

(A.7)

𝑍𝑡 = 𝑋 + 𝑡𝐾 ,

0 ≤ 𝑡 ≤ 1,

(A.8)

𝐺𝑡 = 𝑍𝑡⊤ 𝑍𝑡 = 𝐼𝑘 − 𝑡(1 − 𝑡)𝐾 ⊤ 𝐾 ,

(A.9)

Let and write its Gram matrix as

where the last equality follows from (A.7). Since 𝑡(1 − 𝑡) ≤ 1/4 and ‖𝐾 ⊤ 𝐾 ‖op ≤ 𝛿 2 , every eigenvalue of 𝐺𝑡 lies in [1 − 𝛿 2 /4, 1]. In particular, if 𝛿 ≤ 1, then 𝐺𝑡 is positive definite for every 𝑡 ∈ [0, 1]. We claim that this allows us to define a path in St(𝑛, 𝑘) via the following polar normalization: 𝛾 (𝑡) = 𝑍𝑡 𝐺𝑡−1/2 , (A.10) where 𝐺𝑡−1/2 denotes the principal inverse square root. The map 𝐺 ↦ 𝐺−1/2 is smooth on the positive definite cone, and the polar-factor map 𝑍 ↦ 𝑍(𝑍 ⊤ 𝑍)−1/2 is smooth on the open set of full-column-rank matrices; see [Hig08, Chapters 6 and 8]. Thus 𝛾 is a smooth path. Moreover, 𝛾 (𝑡)⊤ 𝛾 (𝑡) = 𝐺𝑡−1/2 𝐺𝑡 𝐺𝑡−1/2 = 𝐼𝑘 , so 𝛾 (𝑡) ∈ St(𝑛, 𝑘) for every 𝑡. Since 𝐺0 = 𝐺1 = 𝐼𝑘 , we also have 𝛾 (0) = 𝑋 and 𝛾 (1) = 𝑌 . It remains to bound the length of this path. Because 𝐺𝑡 is a polynomial in the fixed symmetric matrix 𝐾 ⊤ 𝐾 , the matrices 𝐺𝑡 and 𝐺̇ 𝑡 commute. Differentiating (A.10) along this commuting family gives 𝛾̇ (𝑡) = 𝐾 𝐺𝑡−1/2 +

1 − 2𝑡 𝑍𝑡 𝐾 ⊤ 𝐾 𝐺𝑡−3/2 . 2

(A.11)

Equivalently, this follows by diagonalizing 𝐾 ⊤ 𝐾 and applying the scalar derivative of 𝑢 ↦ 𝑢−1/2 to each eigenvalue; this is a special case of the matrix-function calculus discussed in [Hig08, Chapter 6]. From the eigenvalue bound following (A.9), for 𝛿 ≤ 1 we have ‖𝐺𝑡−1/2 ‖op ≤ (1 − 𝛿 2 /4)−1/2 ≤ 1 + 𝛿 2 , Also,

‖𝑍𝑡 ‖2op = ‖𝐺𝑡 ‖op ≤ 1, 28

‖𝐺𝑡−3/2 ‖op ≤ (1 − 𝛿 2 /4)−3/2 ≤ 2.

(A.12)

‖𝐾 ⊤ 𝐾 ‖𝐹 ≤ ‖𝐾 ‖2 = 𝛿 2 .

(A.13)

Combining (A.11), (A.12), and (A.13), and using ‖𝐴𝐵‖𝐹 ≤ ‖𝐴‖𝐹 ‖𝐵‖op , gives ‖𝛾̇ (𝑡)‖ ≤ 𝛿(1 + 𝛿 2 ) + |1 − 2𝑡|𝛿 2 . Therefore

1

𝐷(𝑋 , 𝑌 ) ≤ ∫

0

1 ‖𝛾̇ (𝑡)‖ 𝑑𝑡 ≤ 𝛿(1 + 𝛿 2 ) + 𝛿 2 . 2

(A.14)

(A.15)

Since 𝛿 ≤ 1, this implies 𝐷(𝑋 , 𝑌 ) ≤ 𝛿 + 2𝛿 2 = ‖𝑋 − 𝑌 ‖ + 2‖𝑋 − 𝑌 ‖2 . Thus (A.4) holds, for example, with 𝜌𝐷 = 1 and 𝐶𝐷 = 2.

A.4

Deterministic non-expansion in Frobenius Norm

Lemma A.5 (Deterministic Frobenius non-expansion). Let 𝑋 , 𝑌 ∈ St(𝑛, 𝑘). Run one step of the coupled update 𝑋 ′ = 𝑅𝑖𝑗 (𝜃)𝑋 , 𝑌 ′ = 𝑅𝑖𝑗 (𝜃 + 𝛼)𝑌 , with 𝛼 = 𝛼 ̂𝑖𝑗 (𝑋 , 𝑌 ) chosen as in (3.7). Then deterministically ‖𝑋 ′ − 𝑌 ′ ‖ ≤ ‖𝑋 − 𝑌 ‖. Proof. Applying the common inverse rotation 𝑅𝑖𝑗 (−𝜃) to both updated points gives ‖𝑋 ′ − 𝑌 ′ ‖ = ‖𝑋 − 𝑅𝑖𝑗 (𝛼)𝑌 ‖. By (3.9) and (3.7), the choice 𝛼 = 𝛼 ̂𝑖𝑗 (𝑋 , 𝑌 ) minimizes ‖𝑋 − 𝑅𝑖𝑗 (𝛼)𝑌 ‖ over all angle shifts in the selected coordinate plane. Comparing to the admissible choice 𝛼 = 0 gives ‖𝑋 ′ − 𝑌 ′ ‖ ≤ ‖𝑋 − 𝑌 ‖.

B

Miscellaneous Estimates

We present useful estimates that we believe are essentially well-known, including proofs for completeness. The notation in this section is independent of the rest of the paper.

29

B.1

Telescoping Sum Inequality

Lemma B.1. Let 𝑋 = (𝑋1 , … , 𝑋𝑛 ) and 𝑌 = (𝑌1 , … , 𝑌𝑛 ) be vectors in ℝ𝑛 . Then 𝑛

𝑛

𝑛

𝑛

𝑘−1

∏ 𝑌𝑖 . ∏ 𝑋𝑖 − ∏ 𝑌𝑖 = ∑(𝑋𝑘 − 𝑌𝑘 ) ∏ 𝑋𝑖 ) ( ( 𝑖=1 𝑖=1 𝑖=1 𝑖=𝑘+1 ) 𝑘=1 Proof. Write 𝑛

𝑛

𝑛

𝑘

𝑛

𝑘−1

𝑛

∏ 𝑋𝑖 − ∏ 𝑌𝑖 = ∑ ∏ 𝑋𝑖 ∏ 𝑌𝑖 − ∏ 𝑋𝑖 ∏ 𝑌𝑖 , ) 𝑖=1 𝑖=1 𝑖=1 𝑘=1 ( 𝑖=1 𝑖=𝑘+1 𝑖=𝑘 in which all intermediate terms cancel. Factoring out 𝑘−1

𝑛

∏ 𝑋𝑖 ∏ 𝑌𝑖 𝑖=1

𝑖=𝑘+1

from each summand finishes the proof.

B.2

Contraction with occasional bad non-expansive steps

Lemma B.2. Let (𝑡 )𝑇𝑡=0 be a nonnegative process adapted to a filtration (F𝑡 )𝑇𝑡=0 . Let  ⊆ F0 be an initial sigma-field, and let 𝐵 be a nonnegative -measurable random variable such that 0 ≤ 𝐵. Fix 𝜅 ∈ (0, 1], and let 𝐺0 , … , 𝐺𝑇 −1 be events with 𝐺𝑡 ∈ F𝑡 . Assume that, for every 𝑡 = 0, … , 𝑇 − 1: 1. (Deterministic non-expansion) 𝑡+1 ≤ 𝑡 almost surely. 2. (Good-step contraction) On 𝐺𝑡 , 𝔼[𝑡+1 ∣ F𝑡 ] ≤ (1 − 𝜅)𝑡 . 3. (Conditional bad-event control) For deterministic numbers 𝛿𝑡 ≥ 0, ℙ(𝐺𝑡𝑐 ∣ ) ≤ 𝛿𝑡 . Then 𝑇 −1

𝔼[𝑇 ∣ ] ≤

(

(1 − 𝜅)𝑇 + ∑ 𝛿𝑡 𝑡=0

30

)

𝐵.

(B.1)

Proof. Deterministic non-expansion implies 𝑡 ≤ 𝐵 for every 𝑡. The first two assumptions imply 𝔼[𝑡+1 ∣ F𝑡 ] ≤ (1 − 𝜅)𝑡 + 𝐵𝟏𝐺𝑡𝑐 . Taking conditional expectations with respect to  and using the conditional bad-event bound gives 𝔼[𝑡+1 ∣ ] ≤ (1 − 𝜅)𝔼[𝑡 ∣ ] + 𝛿𝑡 𝐵. Since 0 ≤ 𝐵, iterating this recursion proves (B.1); in the iteration we simply bound the geometric weights multiplying the error terms by 1.

C

Burn-in Estimates

We give a sequence of estimates, with the goal of showing that certain functions of Kac’s walk are reasonably well-mixed after a short burn-in period.

C.1

Burn-in for 1-column Walk

Lemma C.1. Let {𝑋𝑡 } be the 1-column Kac walk on 𝕊𝑛−1 started from any 𝑋0 . For every 𝐵 < ∞ there is a constant 𝐶𝐵 < ∞ such that, for every 𝜂 ∈ (0, 1/2) and every 𝑡 ≥ 𝐶𝐵 𝑛 log(𝑛/𝜂), one can couple 𝑋𝑡 to a Haar-distributed point 𝑌 ∈ 𝕊𝑛−1 so that ℙ[‖𝑋𝑡 − 𝑌 ‖ > 𝑛−𝐵 ] ≤ 𝜂. Proof. By Lemma 3.3 of [PS17] and Markov’s inequality, it is possible to couple 𝑋𝑡 , 𝑌 so that ‖𝑋𝑡 − 𝑌 ‖∞ ℙ > 2𝑒 −𝑡/(3𝑛) ≤ 𝑒 −𝑡/3 . [ min𝑖 |𝑌 [𝑖]| ] By Lemma 3.5 of the same paper, ℙ [min |𝑌 [𝑖]| < 𝑒 −𝑡/(6𝑛) ] ≤ 2𝑛𝑒 −𝑡/(18𝑛) . 𝑖

Thus

ℙ[‖𝑋𝑡 − 𝑌 ‖∞ > 2𝑒 −𝑡/(6𝑛) ] ≤ (2𝑛 + 1)𝑒 −𝑡/(18𝑛) .

√ Choosing 𝐶𝐵 large enough makes the last probability at most 𝜂 and also makes 𝑛 2𝑒 −𝑡/(6𝑛) ≤ 𝑛−𝐵 .

31

C.2

Burn-in for 𝑘-Column Walk

Lemma C.2. Let {𝑋𝑡 } be the 𝑘-column walk on St(𝑛, 𝑘) started from any 𝑋0 , with 1 ≤ 𝑘 < 𝑛. There are universal constants 𝐶, 𝑐0 < ∞ such that, for all 𝛿 ∈ (0, 1/2) and all 𝑡 ≥ 𝑐0 𝑛 log(𝑛/𝛿), we have ℙ ‖𝑋𝑡 ‖2𝑟𝑜𝑤,∞ ≥ 𝐶 [

𝑘 + log(𝑛/𝛿) ≤ 𝛿. ] 𝑛

Proof. Write 𝑋𝑡 = 𝑄𝑡 𝑋0 , where 𝑄𝑡 is the product of the elementary rotations used by the walk, and let 𝑉0 = span(𝑋0 ). For a fixed row 𝑎, ‖𝑟𝑎 (𝑋𝑡 )‖2 = ‖𝑋0⊤ 𝑄𝑡⊤ 𝑒𝑎 ‖2 = ‖𝑃𝑉0 𝑄𝑡⊤ 𝑒𝑎 ‖2 . The random vector 𝑄𝑡⊤ 𝑒𝑎 has the same distribution as the 1-column Kac walk started from 𝑒𝑎 : transposition reverses the order of the rotations and replaces each angle by its negative, which does not change the joint law. Apply Lemma C.1 with 𝐵 = 10 and 𝜂 = 𝛿/(2𝑛). If 𝑈 is Haar on 𝕊𝑛−1 , then for 𝑡 ≥ 𝑐0 𝑛 log(𝑛/𝛿) we may couple 𝑄𝑡⊤ 𝑒𝑎 and 𝑈 so that the coupling error has probability at most 𝛿/(2𝑛). On the complement of this error event, ‖𝑃𝑉0 𝑄𝑡⊤ 𝑒𝑎 ‖2 ≤ 2‖𝑃𝑉0 𝑈 ‖2 + 2𝑛−20 . By Lemma A.3, with 𝑠 = log(2𝑛/𝛿), ℙ ‖𝑃𝑉0 𝑈 ‖2 > 𝐶 [

𝑘 + log(2𝑛/𝛿) 𝛿 ≤ . ] 2𝑛 𝑛

Increasing 𝐶 absorbs the 2𝑛−20 term. Thus the desired row bound fails for this fixed 𝑎 with probability at most 𝛿/𝑛. A union bound over 𝑎 ∈ [𝑛] completes the proof.

C.3

Contraction Over Epochs

We combine the conditional contraction estimate in Lemma 3.1, the deterministic nonexpansion in Lemma A.5, and the burn-in estimate in Lemma C.2 to obtain a local contraction estimate for a power of the transition kernel. The parameter choices are collected in the following definition. Definition C.3. Set 𝛿step = 𝑛−30 . Define 𝑀 by 𝑀=𝐶

𝑘 + log (2𝑛/𝛿step ) , 𝑛 32

where 𝐶 > 0 is chosen large enough for Lemma C.2, and let 𝑐loc > 0 be the universal constant from Lemma 3.1. Define 𝑐loc . 𝜅= 𝑀𝑛2 Finally, set the epoch lengths 𝑇burn = ⌈𝑐0 𝑛 log (2𝑛/𝛿step )⌉ ,

𝑇contr =

20 log 𝑛 , ⌈𝜅 ⌉

𝑇epoch = 𝑇burn + 𝑇contr .

Lemma C.4. Fix notation as in Definition C.3, let 𝑃 be the one-step transition kernel of the 𝑘-column walk, and let 𝑊𝐷 denote Wasserstein distance with cost 𝐷. There is a universal constant 𝜌loc > 0, independent of 𝑛 and 𝑘, such that 𝜌loc ≤ min(1, 𝜌𝐷 ) and the following holds. If 𝑋0 , 𝑌0 ∈ St(𝑛, 𝑘) satisfy 𝐷(𝑋0 , 𝑌0 ) ≤ 𝜌loc , then 𝑊𝐷 (𝑃 𝑇epoch (𝑋0 , ⋅), 𝑃 𝑇epoch (𝑌0 , ⋅)) ≤ (1 + 𝐶𝐷 𝜌loc )((1 − 𝜅)𝑇contr + 𝛿epoch )𝐷(𝑋0 , 𝑌0 ), (C.1) where 𝛿epoch = 𝑇contr 𝛿step . In particular, for all 𝑛 > 𝑁0 sufficiently large, 𝑊𝐷 (𝑃 𝑇epoch (𝑋0 , ⋅), 𝑃 𝑇epoch (𝑌0 , ⋅)) ≤ 𝑛−1 𝐷(𝑋0 , 𝑌0 ).

(C.2)

Proof. We construct a coupling realizing the stated bound. Starting from 𝑋0 , 𝑌0 , use the coupling defined in Equations (3.5)–(3.7) at every step. Let F𝑡 be the natural filtration and set 𝑡 = ‖𝑋𝑡 − 𝑌𝑡 ‖. By (3.1) and the assumption on 𝐷(𝑋0 , 𝑌0 ), 0 ≤ 𝐷(𝑋0 , 𝑌0 ) ≤ 𝜌loc ≤ 1. Lemma A.5 gives the deterministic non-expansion for every 𝑡.

𝑡+1 ≤ 𝑡

(C.3)

In particular, 𝑡 ≤ 𝜌loc for the whole epoch, so the local contraction lemma remains applicable whenever the row-norm parameter is at most 𝑀. For 𝑡 ≥ 𝑇burn , define { } 𝐺𝑡 (𝑀) = max (‖𝑋𝑡 ‖2𝑟𝑜𝑤,∞ , ‖𝑌𝑡 ‖2𝑟𝑜𝑤,∞ ) ≤ 𝑀 . By Lemma C.2, the Markov property, and a union bound over the two endpoints of the chains, for every 𝑡 ≥ 𝑇burn .

ℙ(𝐺𝑡 (𝑀)𝑐 ) ≤ 𝛿step

33

(C.4)

On 𝐺𝑡 (𝑀), Lemma 3.1 gives 𝔼[𝑡+1 ∣ F𝑡 ] ≤ (1 − 𝜅)𝑡 .

(C.5)

The burn-in portion is deterministically non-expanding, so 𝑇burn ≤ 𝐷(𝑋0 , 𝑌0 ). Apply Lemma B.2 to the shifted process 𝑇burn +𝑢 , 𝑢 = 0, … , 𝑇contr , with 𝐵 = 𝐷(𝑋0 , 𝑌0 ), the trivial initial sigma-field, and events 𝐺𝑇burn +𝑢 (𝑀). Using (C.3)–(C.5), we obtain 𝔼[𝑇epoch ] ≤ ((1 − 𝜅)𝑇contr + 𝛿epoch )𝐷(𝑋0 , 𝑌0 ). Because 𝑇epoch ≤ 𝜌loc ≤ 𝜌𝐷 deterministically, the local metric comparison (3.2) gives 𝐷(𝑋𝑇epoch , 𝑌𝑇epoch ) ≤ (1 + 𝐶𝐷 𝜌loc )𝑇epoch . Taking expectations proves (C.1). Finally, 𝑇contr = ⌈20𝜅−1 log 𝑛⌉ gives (1 − 𝜅)𝑇contr ≤ 𝑛−20 . Since 𝑀 = 𝑂((𝑘 + log 𝑛)/𝑛) and 1 ≤ 𝑘 < 𝑛, we have 𝑇contr = 𝑂(𝑛(𝑘 + log 𝑛) log 𝑛) ≤ 𝑂(𝑛2 log 𝑛), so 𝛿epoch = 𝑜(𝑛−10 ). The prefactor 1 + 𝐶𝐷 𝜌loc is a fixed constant, and (C.2) follows for all sufficiently large 𝑛. The same estimates also show 𝑇epoch ≤ 𝐶𝑛(𝑘 + log 𝑛) log 𝑛 after increasing 𝐶.

D Representation-Theoretic Variance Bounds for Haar Polynomials We prove the main representation-theory result for any compact group and then later transfer it to (𝑛). We also provide context in the broader representation-theory literature. We recall the following definition (see [Sep07, Definition 2.2]): Definition D.1 (Isotypic component). Let 𝑉 be a unitary representation of 𝐺. For an irreducible representation 𝐸𝜋 , define 𝑉 [𝜋] to be the largest subspace of 𝑉 that is a direct sum of irreducible subrepresentations equivalent to 𝐸𝜋 . The sub-module 𝑉 [𝜋] is called the 𝜋-isotypic component of 𝑉 . We also recall the following result (see [Sep07, Theorem 2.24]): Theorem D.2 (Canonical Decomposition). Let 𝑉 be a finite-dimensional representation of a compact Lie group 𝐺. 1. There is a 𝐺-intertwining isomorphism ∼

𝜄𝜋 ∶ Hom𝐺 (𝐸𝜋 , 𝑉 ) ⊗ 𝐸𝜋 −−→ 𝑉 [𝜋] induced by mapping 𝑇 ⊗ 𝑣 ↦ 𝑇 (𝑣) for 𝑇 ∈ Hom𝐺 (𝐸𝜋 , 𝑉 ) and 𝑣 ∈ 𝑉 . In particular, the multiplicity of 𝜋 is 𝑚𝜋 = dim Hom𝐺 (𝐸𝜋 , 𝑉 ). 34

2. There is a 𝐺-intertwining isomorphism ∼

⨁ Hom𝐺 (𝐸𝜋 , 𝑉 ) ⊗ 𝐸𝜋 −−→ 𝑉 = ⨁ 𝑉 [𝜋]. ̂ [𝜋]∈𝐺

̂ [𝜋]∈𝐺

Theorem D.3 (Compact-group variance inequality). Let 𝐺 be a compact Lie group, let 𝜇 be Haar probability measure on 𝐺, and let 𝑈 be a finite-dimensional real inner-product space. Let 𝜌 ∶ 𝐺 → End(𝑈ℂ ) be the complexification of an orthogonal representation of 𝐺 on 𝑈 . For 𝑇 ∈ End(𝑈ℂ ) define Φ(𝑇 )(𝑔) ∶= ⟨𝑇 , 𝜌(𝑔)⟩HS ,

Ψ(𝑇 ) ∶= Φ(𝑇 ) − ∫ Φ(𝑇 )(ℎ) 𝑑𝜇(ℎ). 𝐺

Let  ∶= {𝑇 ∈ End(𝑈ℂ ) ∶ Φ(𝑇 ) is constant on 𝐺}. Then ‖Ψ(𝑇 )‖2𝐿2 (𝐺,𝜇) ≥

1 ‖Proj ⟂ 𝑇 ‖2HS . dim 𝑈

Proof. By the canonical decomposition in Theorem D.2, the complexified representation admits a 𝐺-equivariant decomposition 𝑈 ℂ ≅ ⨁ 𝑉𝜆 ⊗ 𝑀 𝜆 ,

𝑀𝜆 ∶= Hom𝐺 (𝑉𝜆 , 𝑈ℂ ),

̂ 𝜆∈𝐺

where 𝑉𝜆 runs over irreducible representations and 𝑀𝜆 is the multiplicity space. We now describe the action of 𝜌(𝑔) under this identification. By Theorem D.2, the isomorphism is given by 𝜄𝜆 (𝑣 ⊗ 𝑇 ) = 𝑇 (𝑣),

𝑣 ∈ 𝑉𝜆 , 𝑇 ∈ 𝑀 𝜆 .

Since 𝑇 is 𝐺-equivariant, for every 𝑔 ∈ 𝐺, 𝜌(𝑔) 𝑇 (𝑣) = 𝑇 (𝜌𝜆 (𝑔)𝑣). Therefore 𝜌(𝑔) 𝜄𝜆 (𝑣 ⊗ 𝑇 ) = 𝜄𝜆 (𝜌𝜆 (𝑔)𝑣 ⊗ 𝑇 ), which shows that, under the above identification, 𝜌(𝑔)||𝑉𝜆 ⊗𝑀𝜆 = 𝜌𝜆 (𝑔) ⊗ 𝐼𝑀𝜆 . Hence 𝜌(𝑔) ≅ ⨁ 𝜌𝜆 (𝑔) ⊗ 𝐼𝑀𝜆 . ̂ 𝜆∈𝐺

35

Write 𝑑𝜆 ∶= dim 𝑉𝜆 ,

𝑚𝜆 ∶= dim 𝑀𝜆 .

With respect to this decomposition, every 𝑇 ∈ End(𝑈ℂ ) has block form 𝑇 = (𝑇𝜆𝜅 ),

𝑇𝜆𝜅 ∈ Hom(𝑉𝜆 ⊗ 𝑀𝜆 , 𝑉𝜅 ⊗ 𝑀𝜅 ).

Since 𝜌(𝑔) is block diagonal, only the diagonal blocks contribute to ⟨𝑇 , 𝜌(𝑔)⟩HS : Φ(𝑇 )(𝑔) = ∑⟨𝑇𝜆𝜆 , 𝜌𝜆 (𝑔) ⊗ 𝐼𝑀𝜆 ⟩HS . ̂ 𝜆∈𝐺

For each 𝜆, define a linear map 𝐿𝜆 ∶ End(𝑉𝜆 ⊗ 𝑀𝜆 ) → End(𝑉𝜆 ) as follows. If {𝑓𝑎 } is an orthonormal basis of 𝑀𝜆 , set ⟨𝐿𝜆 (𝐴)𝑢, 𝑣⟩ ∶= ∑⟨𝐴(𝑢 ⊗ 𝑓𝑎 ), 𝑣 ⊗ 𝑓𝑎 ⟩,

𝑢, 𝑣 ∈ 𝑉𝜆 .

(D.1)

𝑎

Thus 𝐿𝜆 (𝐴) = Trace𝑀𝜆 (𝐴) is the partial trace over 𝑀𝜆 . It is independent of the choice of orthonormal basis of 𝑀𝜆 . Set 𝐵𝜆 ∶= 𝐿𝜆 (𝑇𝜆𝜆 ) ∈ End(𝑉𝜆 ). We now compute the contribution of the 𝜆-block to Φ(𝑇 ). Fix orthonormal bases {𝑒𝑖 } of 𝑉𝜆 and {𝑓𝑎 } of 𝑀𝜆 . Then ⟨𝑇𝜆𝜆 , 𝜌𝜆 (𝑔) ⊗ 𝐼𝑀𝜆 ⟩HS = ∑⟨𝑇𝜆𝜆 (𝑒𝑖 ⊗ 𝑓𝑎 ), (𝜌𝜆 (𝑔)𝑒𝑖 ) ⊗ 𝑓𝑎 ⟩ 𝑖,𝑎

= ∑⟨𝑇𝜆𝜆 (𝑒𝑖 ⊗ 𝑓𝑎 ), 𝑒𝑗 ⊗ 𝑓𝑎 ⟩⟨𝜌𝜆 (𝑔)𝑒𝑖 , 𝑒𝑗 ⟩ 𝑖,𝑗,𝑎

= ∑⟨𝐵𝜆 𝑒𝑖 , 𝑒𝑗 ⟩⟨𝜌𝜆 (𝑔)𝑒𝑖 , 𝑒𝑗 ⟩ 𝑖,𝑗

= ⟨𝐵𝜆 , 𝜌𝜆 (𝑔)⟩HS . Hence Φ(𝑇 )(𝑔) = ∑⟨𝐵𝜆 , 𝜌𝜆 (𝑔)⟩HS . ̂ 𝜆∈𝐺

Next we identify the centered part. We have ∫ Φ(𝑇 )(ℎ) 𝑑𝜇(ℎ) = ∑ ⟨𝐵𝜆 , ∫ 𝜌𝜆 (ℎ) 𝑑𝜇(ℎ)⟩ 𝐺

̂ 𝜆∈𝐺

𝐺

36

HS

= ∑⟨𝐵𝜆 , 𝐴𝜆 ⟩HS ̂ 𝜆∈𝐺

with 𝐴𝜆 ∶= ∫ 𝜌𝜆 (ℎ) 𝑑𝜇(ℎ) ∈ End(𝑉𝜆 ). 𝐺

Since 𝐴𝜆 commutes with 𝜌𝜆 (𝑔) for every 𝑔 ∈ 𝐺, Schur’s lemma gives 𝐴𝜆 = 𝑐𝜆 𝐼𝑉𝜆 for some scalar 𝑐𝜆 . If 𝜆 is nontrivial, then 𝐴𝜆 ∶= ∫ 𝜌𝜆 (ℎ) 𝑑𝜇(ℎ) = 0. 𝐺

Indeed, for any 𝑔 ∈ 𝐺, by left invariance of Haar measure, 𝜌𝜆 (𝑔)𝐴𝜆 = ∫ 𝜌𝜆 (𝑔)𝜌𝜆 (ℎ) 𝑑𝜇(ℎ) = ∫ 𝜌𝜆 (𝑔ℎ) 𝑑𝜇(ℎ) = ∫ 𝜌𝜆 (ℎ) 𝑑𝜇(ℎ) = 𝐴𝜆 . 𝐺

𝐺

𝐺

Thus every vector in Im(𝐴𝜆 ) is fixed by 𝐺, so Im(𝐴𝜆 ) ⊆ 𝑉𝜆𝐺 , where 𝑉𝜆𝐺 ∶= {𝑣 ∈ 𝑉𝜆 ∶ 𝜌𝜆 (𝑔)𝑣 = 𝑣 ∀𝑔 ∈ 𝐺}. Since 𝑉𝜆 is irreducible and nontrivial, we have 𝑉𝜆𝐺 = {0}, and therefore 𝐴𝜆 = 0. If 𝜆 = triv, then 𝜌𝜆 (ℎ) = 𝐼𝑉𝜆 for all ℎ, so 𝐴𝜆 = 𝐼𝑉𝜆 . Therefore ∫ Φ(𝑇 )(ℎ) 𝑑𝜇(ℎ) = ⟨𝐵triv , 𝐼𝑉triv ⟩HS , 𝐺

and thus Ψ(𝑇 )(𝑔) = ∑ ⟨𝐵𝜆 , 𝜌𝜆 (𝑔)⟩HS .

(D.2)

𝜆≠triv

By Schur orthogonality (see [Sep07, Theorem 3.7]), ∫ ⟨𝐵, 𝜌𝜆 (𝑔)⟩HS ⟨𝐶, 𝜌𝜂 (𝑔)⟩HS 𝑑𝜇(𝑔) = ∑ 𝐵𝑖𝑗 𝐶𝑘𝓁 ∫ (𝜌𝜆 (𝑔))𝑖𝑗 (𝜌𝜂 (𝑔))𝑘𝓁 𝑑𝜇(𝑔) 𝐺

𝑖,𝑗,𝑘,𝓁

= 𝛿𝜆𝜂

𝐺

1 1 ∑ 𝐵𝑖𝑗 𝐶𝑖𝑗 = 𝛿𝜆𝜂 ⟨𝐵, 𝐶⟩HS . 𝑑𝜆 𝑖,𝑗 𝑑𝜆

Applying this to the above expression for Ψ(𝑇 ) in (D.2) gives 1 ‖𝐵𝜆 ‖2HS . 𝑑 𝜆 𝜆≠triv

‖Ψ(𝑇 )‖2𝐿2 (𝐺,𝜇) = ∑

(D.3)

We now compute the orthogonal projection onto  ⟂ . First observe from Equation (D.1) that for any 𝐴 ∈ End(𝑉𝜆 ⊗ 𝑀𝜆 ) and 𝐵 ∈ End(𝑉𝜆 ), ⟨𝐴, 𝐵 ⊗ 𝐼𝑀𝜆 ⟩HS = ⟨𝐿𝜆 (𝐴), 𝐵⟩HS . 37

Therefore the Hilbert–Schmidt adjoint of 𝐿𝜆 is 𝐿∗𝜆 (𝐵) = 𝐵 ⊗ 𝐼𝑀𝜆 , and hence

(ker 𝐿𝜆 )⟂ = {𝐵 ⊗ 𝐼𝑀𝜆 ∶ 𝐵 ∈ End(𝑉𝜆 )}.

We also have 𝐿𝜆

1 1 𝐵 ⊗ 𝐼𝑀𝜆 = 𝑚 𝐵 = 𝐵𝜆 , ( 𝑚𝜆 𝜆 ) 𝑚𝜆 𝜆 𝜆

so 𝑇𝜆𝜆 − while

1 𝐵𝜆 ⊗ 𝐼𝑀𝜆 ∈ ker 𝐿𝜆 , 𝑚𝜆

1 𝐵𝜆 ⊗ 𝐼𝑀𝜆 ∈ (ker 𝐿𝜆 )⟂ . 𝑚𝜆

Hence Proj(ker 𝐿𝜆 )⟂ (𝑇𝜆𝜆 ) =

1 𝐵𝜆 ⊗ 𝐼𝑀𝜆 . 𝑚𝜆

Now we finally identify . From Φ(𝑇 )(𝑔) = ∑⟨𝐵𝜆 , 𝜌𝜆 (𝑔)⟩HS , 𝜆

the function Φ(𝑇 ) is constant on 𝐺 if and only if 𝐵𝜆 = 0

∀𝜆 ≠ triv.

Thus  consists exactly of those operators whose nontrivial diagonal blocks lie in ker𝐿𝜆 , together with arbitrary off-diagonal blocks and an arbitrary trivial-isotypic diagonal contribution. Consequently,  ⟂ = ⨁ {𝐵 ⊗ 𝐼𝑀𝜆 ∶ 𝐵 ∈ End(𝑉𝜆 )}. 𝜆≠triv

Therefore

1 𝐵𝜆 ⊗ 𝐼 𝑀 𝜆 . 𝑚 𝜆≠triv 𝜆

Proj ⟂ 𝑇 = ⨁ Taking Hilbert–Schmidt norms,

‖ 1 ‖2 1 ‖Proj ⟂ 𝑇 ‖2HS = ∑ ‖‖ 𝐵𝜆 ⊗ 𝐼𝑀𝜆 ‖‖ = ∑ 2 ‖𝐵𝜆 ‖2HS ‖𝐼𝑀𝜆 ‖2HS 𝑚 ‖HS 𝜆≠triv 𝑚𝜆 𝜆≠triv ‖ 𝜆 1 = ∑ ‖𝐵𝜆 ‖2HS , 𝑚 𝜆≠triv 𝜆 38

(D.4) (D.5)

since ‖𝐼𝑀𝜆 ‖2HS = 𝑚𝜆 . From (D.3) and (D.5) we obtain 𝑚𝜆 1 ‖𝐵𝜆 ‖2HS 𝑑 𝑚 𝜆 𝜆 𝜆≠triv

(D.6)

‖Ψ(𝑇 )‖2𝐿2 (𝐺,𝜇) = ∑

𝑚𝜆 >0

1 𝑚𝜆 𝑚𝜆 ∑ ‖Proj ⟂ 𝑇 ‖2HS . ‖𝐵𝜆 ‖2HS = ( min ) 𝜆≠triv 𝑑𝜆 ) 𝜆≠triv 𝑑𝜆 𝑚 𝜆 𝜆≠triv

≥ ( min

𝑚𝜆 >0

(D.7)

𝑚𝜆 >0

𝑚𝜆 >0

Equality holds if and only if 𝐵𝜆 = 0 for every nontrivial 𝜆 with 𝑚𝜂 𝑚𝜆 . > min 𝑑𝜆 𝜂≠triv 𝑑𝜂 𝑚𝜂 >0

Finally, since 𝑑𝜆 ≤ dim 𝑈 and 𝑚𝜆 ≥ 1, this becomes ‖Ψ(𝑇 )‖2𝐿2 (𝐺,𝜇) ≥

1 ‖Proj ⟂ 𝑇 ‖2HS dim 𝑈

and the proof is done.

D.1

Equality cases and the Peter–Weyl–Plancherel picture

The proof of Theorem D.3 gives more than the universal lower bound: it yields the exact identities 1 ‖𝐵𝜆 ‖2HS , 𝑚 𝜆 𝜆≠triv

1 ‖𝐵𝜆 ‖2HS , 𝑑 𝜆 𝜆≠triv

‖Proj ⟂ 𝑇 ‖2HS = ∑

‖Ψ(𝑇 )‖2𝐿2 (𝐺,𝜇) = ∑

(D.8)

where 𝑑𝜆 = dim 𝑉𝜆 ,

𝑚𝜆 = dim 𝑀𝜆 .

Equation (D.8) is the only result in Subsection D.1 that is required for the main result in this paper, and so the remainder can be safely skipped on a first read-through. We include the rest of the subsection because we suspect that the general representation-theoretic estimates in this appendix may be of use to other statisticians working on the low-degreepolynomial heuristic, and we hope that the remarks in this section may help in generalizing our bounds beyond this specific problem. Continuing from Equation (D.8), we note that the sharp constant produced by the argument is 𝑚𝜆 𝜅(𝑈 ) ∶= min , 𝜆≠triv 𝑑𝜆 𝑚𝜆 >0

and we have

‖Ψ(𝑇 )‖2𝐿2 (𝐺,𝜇) ≥ 𝜅(𝑈 ) ‖Proj ⟂ 𝑇 ‖2HS . 39

Equality holds if and only if 𝐵𝜆 = 0

for every nontrivial 𝜆 such that

𝑚𝜆 > 𝜅(𝑈 ). 𝑑𝜆

Thus the equality case is governed exactly by the multiplicity ratios 𝑚𝜆 . 𝑑𝜆 The universal estimate in Theorem D.3 is obtained by replacing 𝜅(𝑈 ) with the crude lower bound 1 , 𝜅(𝑈 ) ≥ dim 𝑈 which follows from 𝑚𝜆 ≥ 1 and 𝑑𝜆 ≤ dim 𝑈 . This constant is sharp. Indeed, if 𝑈ℂ is irreducible and nontrivial, then the only nontrivial isotypic component has 𝑚𝜆 = 1 and 𝑑𝜆 = dim 𝑈 , so ‖Ψ(𝑇 )‖2𝐿2 (𝐺,𝜇) =

1 1 ‖𝑇 ‖2HS = ‖Proj ⟂ 𝑇 ‖2HS dim 𝑈 dim 𝑈

for every 𝑇 ∈ End(𝑈ℂ ). A second important equality pattern occurs when 𝑚𝜆 = 𝑑𝜆

for every nontrivial irreducible 𝜆 occurring in 𝑈ℂ .

Then the two identities in (D.8) coincide term by term, and hence ‖Ψ(𝑇 )‖2𝐿2 (𝐺,𝜇) = ‖Proj ⟂ 𝑇 ‖2HS . This is exactly the multiplicity pattern of the regular representation, and it is at this point that the present finite-dimensional argument meets classical harmonic analysis. Indeed, the passage from our finite-dimensional setting to 𝐿2 (𝐺) is precisely the passage from the finite-dimensional canonical decomposition [Sep07, Theorem 2.24] to its Hilbertspace analogue [Sep07, Theorem 3.19]. By the Peter–Weyl theorem [Sep07, Theorem 3.25 and Corollary 3.26], ̂ 𝐿2 (𝐺) ≅ ⨁[𝜋]∈𝐺̂𝐸𝜋∗ ⊗ 𝐸𝜋 as a 𝐺 × 𝐺-module. In particular, Hom𝐺 (𝐸𝜋 , 𝐿2 (𝐺)) ≅ 𝐸𝜋∗ ,

𝑚𝜋 = dim 𝐸𝜋∗ = dim 𝐸𝜋 = 𝑑𝜋 .

Thus every irreducible 𝐸𝜋 occurs in the regular representation with multiplicity equal to its dimension. Under the natural identification 𝐸𝜋∗ ⊗ 𝐸𝜋 ≅ End(𝐸𝜋 ), 40

the Peter–Weyl decomposition becomes the operator-valued Fourier decomposition of 𝐿2 (𝐺). In this form, the Plancherel theorem [Sep07, Theorem 3.38] states that ‖𝑓 ‖2𝐿2 (𝐺) = ∑ 𝑑𝜋 ‖𝜋(𝑓 )‖2HS . ̂ [𝜋]∈𝐺

This is the infinite-dimensional analogue of the first identity in (D.8): the quantities 𝐵𝜆 in our proof play the role of operator-valued Fourier coefficients, and the weights 1/𝑑𝜆 are exactly the Plancherel weights. ̂ Equivalently, by Schur orthogonality, for every finite subset 𝐹 ⊂ 𝐺, ‖ ‖2 ‖ ‖ 1 ‖ ∑ ⟨𝐵𝜋 , 𝜋(⋅)⟩HS ‖ ‖𝐵𝜋 ‖2HS . = ∑ ‖ ‖ 𝑑 𝜋 ‖[𝜋]∈𝐹 ‖2 ‖ ‖𝐿 (𝐺) [𝜋]∈𝐹 This is precisely the Parseval identity for matrix coefficients. In other words, one of the identities produced by our argument is exactly the finite-dimensional Peter–Weyl– Plancherel computation restricted to the coefficient function 𝑔 ↦ Φ(𝑇 )(𝑔) = ⟨𝑇 , 𝜌(𝑔)⟩HS . The ratio 𝑚𝜆 /𝑑𝜆 then measures how far the given representation 𝑈ℂ is from the regular representation: when 𝑚𝜆 = 𝑑𝜆 for all relevant 𝜆, our comparison becomes termwise identical to the Plancherel identity. In the Abelian case 𝐺 = 𝑆 1 , every irreducible representation is one-dimensional, so 𝑑𝜋 = 1 for all 𝜋, and the Peter–Weyl–Plancherel picture reduces to the usual Fourier series and Parseval identity on the circle; see [Sep07, Theorem 3.43]. Thus Theorem D.3 should be viewed as a finite-dimensional shadow of classical harmonic analysis, with the regular-representation equality case recovering exactly the classical Peter–Weyl–Plancherel mechanism.

D.2

Application to Polynomial Moments

Let 𝑋 be Haar-distributed on (𝑛) and let 𝜇 = 𝛼𝑛 denote Haar probability measure. All expectations 𝔼[⋅] are with respect to 𝜇. 𝑑 𝑑 Fix an integer 𝑑 ≥ 1. Let ℝ[𝑛] ×[𝑛] denote the space of real arrays 𝑇 = (𝑇𝛼,𝛽 )𝛼,𝛽∈[𝑛]𝑑 , where 𝛼 = (𝛼1 , … , 𝛼𝑑 ) and 𝛽 = (𝛽1 , … , 𝛽𝑑 ). For 𝑇 in this space define the homogeneous polynomial observable 𝑑

𝑓𝑇 (𝑋 ) = Ev𝑑 (𝑇 )(𝑋 ) ∶= ∑ 𝑇𝛼,𝛽 ∏ 𝑋𝛼𝑡 𝛽𝑡 . 𝛼,𝛽∈[𝑛]𝑑

41

𝑡=1

(D.9)

𝑑

𝑑

Equip ℝ[𝑛] ×[𝑛] with the Frobenius inner product ‖𝑇 ‖2𝐹 ∶= ⟨𝑇 , 𝑇 ⟩𝐹 .

⟨𝑇 , 𝑆⟩𝐹 ∶= ∑ 𝑇𝛼,𝛽 𝑆𝛼,𝛽 , 𝛼,𝛽

Let

𝑑 ∶= {𝑇 ∶ Ev𝑑 (𝑇 ) is constant 𝜇-a.s.}.

Equivalently, 𝑇 ∈ 𝑑 iff 𝑉 𝑎𝑟(Ev𝑑 (𝑇 )(𝑋 )) = 0. Let 𝑇 ♯ denote the orthogonal projection of 𝑇 onto 𝑑⟂ . Then 𝔼[Ev𝑑 (𝑇 ♯ )(𝑋 )] = 0,

𝑉 𝑎𝑟(Ev𝑑 (𝑇 )(𝑋 )) = 𝑉 𝑎𝑟(Ev𝑑 (𝑇 ♯ )(𝑋 )). 𝑑

(D.10)

𝑑

Corollary D.4 (Homogeneous case). For homogeneous 𝑇 ∈ ℝ[𝑛] ×[𝑛] define 𝑓𝑇 (𝑋 ) = Ev𝑑 (𝑇 )(𝑋 ) as in (D.9), and let 𝑇 ♯ be the Frobenius-orthogonal projection of 𝑇 onto 𝑑⟂ . Then (D.11)

𝑉 𝑎𝑟(𝑓𝑇 (𝑋 )) ≥ 𝑛−𝑑 ‖𝑇 ♯ ‖2𝐹 . Proof. Let

𝑈 ∶= (ℝ𝑛 )⊗𝑑 ,

𝐺 = (𝑛),

and let 𝜌 ∶ 𝐺 → End(𝑈ℂ ) be the complexification of the tensor-power representation 𝜌(𝑔) = 𝑔 ⊗𝑑 . We identify the coefficient array 𝑑 𝑑 𝑇 = (𝑇𝛼,𝛽 )𝛼,𝛽∈[𝑛]𝑑 ∈ ℝ[𝑛] ×[𝑛] with the corresponding linear operator on 𝑈 in the standard tensor-product basis: if 𝑒𝛼 ∶= 𝑒𝛼1 ⊗ ⋯ ⊗ 𝑒𝛼𝑑 ,

𝛼 ∈ [𝑛]𝑑 ,

then 𝑇 acts by 𝑇 𝑒𝛽 = ∑ 𝑇𝛼,𝛽 𝑒𝛼 . 𝛼∈[𝑛]𝑑 𝑑

𝑑

Under this identification, the Frobenius inner product on ℝ[𝑛] ×[𝑛] coincides with the Hilbert–Schmidt inner product on End(𝑈 ), and hence ‖𝑇 ‖𝐹 = ‖𝑇 ‖HS . Now let 𝑋 ∈ (𝑛). In the basis {𝑒𝛼 }𝛼∈[𝑛]𝑑 , the matrix entries of 𝜌(𝑋 ) = 𝑋 ⊗𝑑 are 𝑑 ⊗𝑑 (𝑋 )𝛼,𝛽 = ∏ 𝑋𝛼𝑡 𝛽𝑡 . 𝑡=1

42

Therefore 𝑑

⟨𝑇 , 𝜌(𝑋 )⟩HS = ∑ 𝑇𝛼,𝛽 (𝑋 ⊗𝑑 )𝛼,𝛽 = ∑ 𝑇𝛼,𝛽 ∏ 𝑋𝛼𝑡 𝛽𝑡 = Ev𝑑 (𝑇 )(𝑋 ). 𝛼,𝛽∈[𝑛]𝑑

𝛼,𝛽∈[𝑛]𝑑

𝑡=1

Since Ev𝑑 (𝑇 )(𝑔) = ⟨𝑇 , 𝜌(𝑔)⟩HS = Φ(𝑇 )(𝑔), the subspace 𝑑 coincides with , and hence 𝑇 ♯ is the orthogonal projection of 𝑇 onto  ⟂ . By applying Theorem D.3 with this choice of 𝐺, 𝑈 , and 𝜌, we obtain 𝑉 𝑎𝑟(𝑓𝑇 (𝑋 )) = 𝑉 𝑎𝑟(Ev𝑑 (𝑇 )(𝑋 )) = ‖Ψ(𝑇 )‖2𝐿2 (𝐺,𝜇) ≥

1 ‖𝑇 ♯ ‖2𝐹 = 𝑛−𝑑 ‖𝑇 ♯ ‖2𝐹 dim 𝑈

and the proof is finished.

D.3

Inhomogeneous polynomials via grading

Let 𝑓 be a polynomial function on (𝑛) that admits a representative of degree at most 𝑑 in the entries of 𝑋 . Choose one such representative and decompose it as 𝑑

𝑓 = ∑ 𝑓𝑘 , 𝑘=0

where each 𝑓𝑘 is homogeneous of degree 𝑘. (As a function on (𝑛), this decomposition need not be unique; here we fix one representative.) To treat all degrees simultaneously, we introduce a graded representation. Let 𝑑

𝑑

 ∶= ⨁(ℝ𝑛 )⊗𝑘 ,

𝜌(𝑔) ∶= ⨁ 𝑔 ⊗𝑘 ,

𝑘=0

𝑔 ∈ (𝑛).

𝑘=0

Each summand (ℝ𝑛 )⊗𝑘 corresponds to the chosen homogeneous representative of degree 𝑘, and the direct sum allows us to encode polynomials of mixed degree as a single linear functional. Arguing as in the homogeneous case, each 𝑓𝑘 can be written as 𝑓𝑘 (𝑔) = ⟨𝑇𝑘 , 𝑔 ⊗𝑘 ⟩HS for some 𝑇𝑘 ∈ End((ℝ𝑛 )⊗𝑘 ). Setting 𝑑

𝑇 ∶= ⨁ 𝑇𝑘 ∈ End( ), 𝑘=0

we obtain the representation 𝐹𝑇 (𝑔) = ⟨𝑇 , 𝜌(𝑔)⟩HS . 43

(D.12)

Define, in direct analogy with the homogeneous case, ≤𝑑 ∶= {𝑇 ∈ End( ) ∶ ⟨𝑇 , 𝜌(𝑔)⟩HS is constant 𝜇-a.s.}. Equivalently, 𝑇 ∈ ≤𝑑 if and only if 𝑉 𝑎𝑟(⟨𝑇 , 𝜌(𝑋 )⟩HS ) = 0. Let

(D.13)

𝑇 ♯ ∶= Proj ⟂ (𝑇 ). ≤𝑑

Then 𝑇 − 𝑇 ♯ ∈ ≤𝑑 , so ⟨𝑇 − 𝑇 ♯ , 𝜌(𝑔)⟩𝐻 𝑆 is constant 𝜇-a.s. Moreover, 𝔼[⟨𝑇 ♯ , 𝜌(𝑋 )⟩𝐻 𝑆 ] = 0. Hence

𝐹𝑇 (𝑋 ) − 𝔼[𝐹𝑇 (𝑋 )] = ⟨𝑇 ♯ , 𝜌(𝑋 )⟩𝐻 𝑆

and therefore

𝜇-a.s.

(D.14)

𝑉 𝑎𝑟(𝐹𝑇 (𝑋 )) = 𝑉 𝑎𝑟(⟨𝑇 ♯ , 𝜌(𝑋 )⟩𝐻 𝑆 ).

Corollary D.5 (Inhomogeneous case). Let 𝐹𝑇 be a polynomial in the entries of 𝑋 ∈ (𝑛) of degree at most 𝑑, and represent it as in (D.12). Then 𝑉 𝑎𝑟(𝐹𝑇 (𝑋 )) ≥

1 ‖𝑇 ♯ ‖2HS . (𝑑 + 1)𝑛𝑑

Proof. We apply Theorem D.3 with 𝑑

𝐺 = (𝑛),

𝑈 = ,

𝜌(𝑔) = ⨁ 𝑔 ⊗𝑘 . 𝑘=0

By construction (D.12), we have 𝐹𝑇 (𝑔) = Φ(𝑇 )(𝑔) = ⟨𝑇 , 𝜌(𝑔)⟩HS . Moreover, the space ≤𝑑 defined above coincides with the space  in Theorem D.3, so that 𝑇 ♯ = Proj ⟂ (𝑇 ). Therefore 1 ‖𝑇 ♯ ‖2HS . 𝑉 𝑎𝑟(𝐹𝑇 (𝑋 )) = ‖Ψ(𝑇 )‖2𝐿2 (𝐺,𝜇) ≥ dim  The dimension bounds follow from 𝑑

dim  = ∑ 𝑛𝑘 ≤ (𝑑 + 1)𝑛𝑑 𝑘=0

and the proof is finished. 44

E

Proof of Theorem 6.1

We begin by setting some additional notation. For a polynomial 𝑝 in the matrix entries, write ‖𝑝‖∞,(𝑛) =

sup |𝑝(𝑄)|.

(E.1)

𝑄∈(𝑛)

Given parameters 𝑑ph , 𝐿 > 0, say that a probability measure 𝜇 on (𝑛) is (𝑑ph , 𝐿)-pseudoHaar in supnorm if, for every real polynomial 𝑝 in the matrix entries with deg(𝑝) ≤ 𝑑ph and ‖𝑝‖∞,(𝑛) ≤ 1, | | −𝐿 | 𝑝 𝑑𝜇 − | |∫ ∫ 𝑝 𝑑𝛼𝑛 | ≤ 𝑛 . | |

(E.2)

Our main estimate is the following proof that being pseudo-Haar is good enough to obtain the usual Johnson-Lindenstrauss estimate: Theorem E.1. There is a universal constant 𝐶 < ∞ with the following property. Let 𝑄 be an (𝑛)-valued random matrix whose law is (𝑑ph , 𝐿)-pseudo-Haar in the sense of (E.2). Let  ⊂ ℝ𝑛 have 𝑁 ≥ 2 points, and let 0 < 𝜀, 𝛿 < 1. Set 𝑁 𝑟 = 𝐶 log . ⌈ 𝛿⌉

(E.3)

Assume 4𝑟 ≤ 𝑑ph ,

𝓁 ≥ 𝐶𝜀 −2 𝑟,

𝐿 log 𝑛 ≥ log

2(𝑁2 ) 𝑛 + 2𝑟 log . 𝛿 𝜀𝓁

(E.4)

Then, with probability at least 1 − 𝛿 over 𝑄, (1 − 𝜀)‖𝑥𝑖 − 𝑥𝑗 ‖22 ≤ ‖𝐴𝑄 (𝑥𝑖 − 𝑥𝑗 )‖22 ≤ (1 + 𝜀)‖𝑥𝑖 − 𝑥𝑗 ‖22

(E.5)

for every pair 1 ≤ 𝑖 < 𝑗 ≤ 𝑁 . The proof uses the following standard Haar moment estimate. We will use essentially the same argument as in [DG03], except that we replace exponential moments with merely the moderate-degree polynomial moments that are actually required. Lemma E.2 (Haar moment bound). There are universal constants 𝐶0 , 𝑐0 > 0 such that, for every unit vector 𝑣 ∈ 𝕊𝑛−1 and every integer 1 ≤ 𝑟 ≤ 𝑐0 𝓁, 𝑟 𝑟 𝔼𝐻 ∼𝛼𝑛 |𝑍𝑣 (𝐻 )|2𝑟 ≤ (𝐶0 ) . 𝓁

45

(E.6)

Proof. By Haar invariance of 𝛼𝑛 , the vector 𝐻 𝑣 is uniformly distributed on 𝕊𝑛−1 . Therefore ‖Π𝓁 𝐻 𝑣‖22 has the same distribution as the sum of the first 𝓁 squared coordinates of a uniform random point on 𝕊𝑛−1 , equivalently a beta random variable with parameters 𝓁/2 and (𝑛 − 𝓁)/2. The standard beta, or spherical-cap, concentration estimate gives universal constants 𝑎, 𝑏 > 0 such that 0 < 𝑡 ≤ 1,

(E.7)

𝑡 ≥ 1.

(E.8)

2𝑟𝑡 2𝑟−1 ℙ(|𝑍𝑣 (𝐻 )| > 𝑡) 𝑑𝑡,

(E.9)

ℙ(|𝑍𝑣 (𝐻 )| > 𝑡) ≤ 2 exp(−𝑎𝓁𝑡 2 ), and ℙ(|𝑍𝑣 (𝐻 )| > 𝑡) ≤ 2 exp(−𝑏𝓁𝑡), Using 𝔼|𝑍𝑣 (𝐻 )|2𝑟 = ∫

∞ 0

we bound the contribution from 0 < 𝑡 ≤ 1 by extending the integral to infinity and applying (E.7): ∞ 𝑟 𝑟 2𝑟−1 −𝑎𝓁𝑡 2 𝑒 𝑑𝑡 = 2𝑟(𝑎𝓁)−𝑟 Γ(𝑟) ≤ (𝐶 ) . ∫ 4𝑟𝑡 𝓁 0 Similarly, (E.8) gives ∞

∫

1

𝑟 2𝑟 𝑟 𝑟 4𝑟𝑡 2𝑟−1 𝑒 −𝑏𝓁𝑡 𝑑𝑡 ≤ (𝐶 ) ≤ (𝐶0 ) , 𝓁 𝓁

after choosing 𝑐0 > 0 sufficiently small and 𝐶0 < ∞ sufficiently large. Combining these estimates with (E.9) proves (E.6). Proposition E.3 (Moment-transfer form). Let 𝑄 be an (𝑛)-valued random matrix, let 𝐻 ∼ 𝛼𝑛 , and let  = {𝑥1 , … , 𝑥𝑁 } ⊂ ℝ𝑛 . Let 0 < 𝜀 < 1 and let 𝑟 be a positive integer with 𝑟 ≤ 𝑐0 𝓁, where 𝑐0 is the constant in Lemma E.2. Suppose that, for every 𝑣 ∈  , |𝔼𝑍𝑣 (𝑄)2𝑟 − 𝔼𝑍𝑣 (𝐻 )2𝑟 | ≤ 𝛼. | |

(E.10)

Then | ‖𝐴𝑄 (𝑥𝑖 − 𝑥𝑗 )‖22 | ℙ ∃ 𝑖 < 𝑗 ∶ || − 1|| > 𝜀 2 ) ( | | ‖𝑥𝑖 − 𝑥𝑗 ‖2 ≤

𝑁 𝑟 𝑟 𝛼 𝐶 + 2𝑟 ] . 0 ( 2 ) [( 𝜀 2 𝓁 ) 𝜀

46

(E.11)

Proof. For fixed 𝑣 ∈  , Markov’s inequality, (E.10), and Lemma E.2 give 𝑟 𝑟 𝛼 ℙ(|𝑍𝑣 (𝑄)| > 𝜀) ≤ 𝜀 −2𝑟 𝔼|𝑍𝑣 (𝑄)|2𝑟 ≤ (𝐶0 2 ) + 2𝑟 . 𝜀 𝓁 𝜀 Taking a union bound over the at most (𝑁2 ) vectors in  proves (E.11). Proof of Theorem E.1. Fix 𝑣 ∈ 𝕊𝑛−1 and define 𝑃𝑣,𝑟 (𝐺) = 𝑍𝑣 (𝐺)2𝑟 .

(E.12)

Since 𝑍𝑣 (𝐺) has degree 2 in the entries of 𝐺, (E.12) has degree at most 4𝑟. Moreover, for every 𝑄 ∈ (𝑛), 0 ≤ ‖Π𝓁 𝑄𝑣‖22 ≤ 1,

|𝑛 | 𝑛 |𝑍𝑣 (𝑄)| = | ‖Π𝓁 𝑄𝑣‖22 − 1| ≤ . |𝓁 | 𝓁

(E.13)

Thus 𝑛 2𝑟 ‖𝑃𝑣,𝑟 ‖∞,(𝑛) ≤ ( ) . 𝓁

(E.14)

By (E.4), the normalized polynomial (𝓁/𝑛)2𝑟 𝑃𝑣,𝑟 has degree at most 𝑑ph and supnorm at most 1. Applying (E.2) gives 𝑛 2𝑟 |𝔼𝑃𝑣,𝑟 (𝑄) − 𝔼𝑃𝑣,𝑟 (𝐻 )| ≤ 𝑛−𝐿 ( ) . 𝓁

(E.15)

Apply Proposition E.3 with 𝛼 = 𝑛−𝐿 (𝑛/𝓁)2𝑟 . After increasing the universal constant 𝐶 in (E.3) and (E.4), the condition 𝓁 ≥ 𝐶𝜀 −2 𝑟 makes the first term in (E.11) at most 𝛿/2. The last inequality in (E.4) makes the second term in (E.11) at most 𝛿/2. Therefore the bad event has probability at most 𝛿, and (6.4) gives (E.5). Proof of Theorem 6.1. Let 𝐻 ∼ 𝛼𝑛 and set 𝑑 = 4𝑟. We first verify the moment-transfer hypothesis (E.10) for 𝑄 = 𝑀. For a monomial m of degree 𝑚 ≤ 𝑑, Theorem 4.1 and the definition (4.1) give, after increasing universal constants if necessary, |𝔼𝑀∼𝛽 m(𝑀) − 𝔼𝐻 ∼𝛼 m(𝐻 )| ≤ 𝐶𝑑 𝑛−𝑠 , 𝑛 𝑛,𝑇 ,𝑥 | |

(E.16)

where 𝑠=

𝑇 . ⌊ 𝐶𝑛(𝑑 + log 𝑛) log 𝑛 ⌋

(E.17)

Indeed, when 𝑚 ≤ 𝑑, the monomial m depends on at most 𝑑 columns, and the bound (E.16) is the degree-𝑑 version of Theorem 4.1 with constants enlarged to dominate all lower degrees. 47

Next expand (6.2) as a polynomial in the entries of 𝐺: 𝓁

𝑛

𝑛 ∑ ∑ 𝑣𝑏 𝑣𝑐 𝐺𝑎𝑏 𝐺𝑎𝑐 − 1. 𝓁 𝑎=1 𝑏,𝑐=1

(E.18)

‖𝑍𝑣 ‖coeff,1 ≤ 1 + 𝑛‖𝑣‖21 ≤ 1 + 𝑛2 ≤ 2𝑛2 .

(E.19)

‖𝑍𝑣2𝑟 ‖coeff,1 ≤ (2𝑛2 )2𝑟 .

(E.20)

𝑍𝑣 (𝐺) = Since ‖𝑣‖21 ≤ 𝑛‖𝑣‖22 = 𝑛, (E.18) gives

Therefore

Combining (E.16) and (E.20), we obtain, uniformly over 𝑣 ∈ 𝕊𝑛−1 , |𝔼𝑍𝑣 (𝑀)2𝑟 − 𝔼𝑍𝑣 (𝐻 )2𝑟 | ≤ 𝐶𝑟(2𝑛2 )2𝑟 𝑛−𝑠 . | |

(E.21)

By increasing 𝐶JL in (6.6) and (6.7), the condition (6.6) makes 𝑟 ≤ 𝑐0 𝓁 and makes the first term in (E.11) at most 𝛿/2. Writing 𝐵 = 𝑟 log(𝑛/𝜀) + log(𝑁 /𝛿), the time condition (6.7) gives 𝑠 log 𝑛 ≥ 𝑐𝐶JL 𝐵 − log 𝑛 for a universal 𝑐 > 0; since 𝐵 ≥ log 𝑛, increasing 𝐶JL absorbs the final log 𝑛 loss. Thus (6.7), together with (E.21), makes the second term in (E.11) at most 𝛿/2. Applying Proposition E.3 with 𝑄 = 𝑀 gives | ‖𝐴𝑀 (𝑥𝑖 − 𝑥𝑗 )‖22 | ℙ ∃ 𝑖 < 𝑗 ∶ || − 1|| > 𝜀 ≤ 𝛿. 2 ( ) | ‖𝑥𝑖 − 𝑥𝑗 ‖2 | Using (6.4), this is exactly (6.8). Pairs with 𝑥𝑖 = 𝑥𝑗 satisfy (6.8) trivially. If 𝑁 /𝛿 ≤ 𝑛𝐴 and 𝜀 is fixed, then 𝑟 = 𝑂𝐴 (log 𝑛). The conditions (6.6) and (6.7) then reduce to 𝓁 = 𝑂𝐴 (𝜀 −2 log 𝑛) and 𝑇 ≥ 𝐶𝐴 𝑛 log3 𝑛, after increasing 𝐶𝐴 .

48

Related documents

• Rapid Mixing of Parallel Kac's Walk: From Spheres to Stiefel Manifolds#1142300
• Kac's Walk on Rotation Matrices Mixes in $\boldsymbol{Θ(n^2)}$ Steps: A Proof Discovered with AI#820675
• Li--Yorke Chaos Along Any Infinite Sequence: Relative Mixing, Sofic and Rokhlin Entropy versus Naive Entropy#1104460
• Phase transition for the asymptotic entropy of branching random walks on groups#652401
• Phase transition for the asymptotic entropy of branching random walks on groups#650948