On the Pseudo-Mixing of Kac's Walk

Motivated by a conjecture of Vaikuntanathan and Zamir, we study the pseudo-mixing of Kac's walk on 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.