Affine Random Walks on the Torus

Weikun He, Tsviqa Lakrec, Elon Lindenstrauss

TL;DR

This paper investigates how quickly random walks on a torus, generated by affine transformations, spread out evenly (equidistribute). The authors provide quantitative estimates for this spreading speed, showing it depends primarily on the linear part of the transformation, unless the walk gets stuck in a small, repeating pattern. This work extends existing results on linear random walks to the more general affine case.

What Problem Does This Paper Address?

The paper tackles the problem of understanding the equidistribution of random walks on a torus. Imagine a point on a donut-shaped surface (a torus) that takes random steps. We want to know how quickly this point, on average, will visit all parts of the torus with equal probability. This is known as equidistribution.

Previous work (like Bourgain et al. [7] and He [14, 15]) had established results for linear random walks, where the steps are purely linear transformations. However, this paper extends these results to affine random walks. An affine transformation is a linear transformation followed by a translation (a shift). The challenge is that these translations can "trap" the random walk in a finite set of points, preventing it from truly equidistributing. The authors aim to quantify how fast equidistribution occurs and under what conditions it's guaranteed, or when the walk gets stuck.

Methods

The core of the paper involves adapting and extending techniques from the study of linear random walks to the affine setting. Key methods include:

  • Quantitative Equidistribution Estimates: The authors derive precise mathematical bounds on how quickly the random walk approaches the uniform distribution (Haar measure) on the torus. These bounds depend on the properties of the linear part of the affine transformation.
  • Zariski Closure and Irreducibility: A crucial assumption is that the Zariski closure of the group generated by the linear part of the transformation acts "strongly irreducibly" on $\mathbb{R}^d$. This means it doesn't preserve any non-trivial unions of proper linear subspaces, preventing certain types of "degenerate" behavior.
  • Finite Orbit Characterization: The paper provides a precise characterization of when an affine random walk gets trapped in a finite orbit. This involves defining a "height" for such orbits and relating it to rational points on the torus.
  • Reduction to Finite Fields: For certain technical arguments, the authors reduce the problem from the real torus to finite fields ($\mathbb{F}_p$). This allows them to use tools from algebraic geometry and number theory.
  • Margulis Function: A Margulis function is used to improve initial non-concentration estimates, providing stronger bounds on the energy of the random walk's distribution.
  • Bootstrapping: A "bootstrapping" procedure is employed to intensify concentration by going back in time, building upon initial estimates.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Linear Part Dominates: The most striking insight is that the speed of equidistribution for affine random walks is largely determined by the linear component of the transformation, provided certain conditions are met. The translation part primarily influences whether the walk gets trapped in a finite orbit.
  • Finite Orbits as the Obstacle: The paper clearly identifies finite orbits as the main obstacle to universal equidistribution. The conditions for a walk to be trapped in such an orbit are precisely delineated.
  • Bridging Linear and Affine: The work successfully bridges the gap between the well-understood linear random walks and the more complex affine case, showing that many of the analytical tools can be adapted.
  • Quantitative Guarantees: The paper moves beyond qualitative statements (e.g., "it equidistributes") to provide quantitative estimates (e.g., "it equidistributes at this rate"), which are crucial for deeper understanding and applications.

Key Results

  • Theorem 1.2: Under specific conditions on the linear part of the affine transformation (strong irreducibility, and either a proximal element or a connected Zariski closure), an affine random walk on the torus either equidistributes to the Haar measure or gets confined to a finite orbit.
  • Theorem 1.3: Provides a quantitative estimate for how fast the random walk equidistributes, showing that the rate depends on the linear part and is independent of the translation part, unless the walk is "trapped" in a finite orbit.
  • Proposition 1.4: Demonstrates the optimality of the convergence rate obtained in Theorem 1.3.

Limitations and Future Work

  • Assumptions on Linear Part: The results rely on strong assumptions about the linear part of the transformation, specifically its action being strongly irreducible and its Zariski closure having certain properties (connected or containing a proximal element). Relaxing these assumptions could be a direction for future work.
  • "Trapped" Walks: The paper precisely characterizes when walks are trapped in finite orbits, but the focus is on the equidistribution of walks that are not trapped. Further exploration of the dynamics within these finite orbits might be interesting.
  • Generalizations: The authors mention that their endgame strategy for Theorem 1.2 is somewhat different from previous work and might offer a simpler treatment, especially for non-proximal cases. This suggests potential for further simplification or generalization of the techniques.

Summary updated

Abstract

Abstract We study quantitative equidistribution of random walks on the torus by affine transformations. Under the assumption that the Zariski closure of the group generated by the linear part acts strongly irreducibly on ${{\mathbb{R}}}^d$ and is either Zariski connected or contains a proximal element, we give quantitative estimates (depending only on the linear part of the random walk) for how fast the random walk equidistributes unless the initial point and the translation part of the affine transformations can be perturbed so that the random walk is trapped in a finite orbit of small cardinality. In particular, we prove that the random walk equidistributes in law to the Haar measure if and only if the random walk is not trapped in a finite orbit.
BibTeX
@inproceedings{he2020affine,
  author = {Weikun He and Tsviqa Lakrec and Elon Lindenstrauss},
  title = {{Affine Random Walks on the Torus}},
  booktitle = {International Mathematics Research Notices},
  year = {2020},
  doi = {10.1093/imrn/rnaa322},
}
Figure