On the Pseudo-Mixing of Kac's Walk

Abstract

Motivated by a conjecture of Vaikuntanathan and Zamir, we study the pseudo-mixing of Kac's walk on $\mathrm{SO}(n)$: whether short trajectories are indistinguishable from Haar measure by low-complexity tests. We prove that the first $k$ columns mix in Wasserstein distance in $O(n(k+\log n)\log n)$ steps for fixed accuracy, resolving a conjecture of Oliveira. Combining this with a representation-theoretic variance bound, we show that if $T=ω(nk(k+\log n)\log n)$, then every degree-$k$ polynomial normalized to have unit Haar variance has expectation under the $T$-step law within $o(1)$ of its Haar expectation. As an application, we show that this pseudo-mixing estimate can be used to prove the effectiveness of a fast Johnson--Lindenstrauss transform with the usual target dimension.

Disclosure

“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. Lem”

PDF page 8

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T05:23:09.975549Z

Structural counts