Discrepancy in modular arithmetic progressions

Celebrated theorems of Roth and of Matouv{s}ek and Spencer together show that the discrepancy of arithmetic progressions in the first $n$ positive integers is $Theta(n^{1/4})$. We study the analogous problem in the $mathbb{Z}_n$ setting. We asymptotically determine the logarithm of the discrepancy of arithmetic progressions in $mathbb{Z}_n$ for all positive integer $n$. We further determine up to a constant factor the discrepancy of arithmetic progressions in $mathbb{Z}_n$ for many $n$. For example, if $n=p^k$ is a prime power, then the discrepancy of arithmetic progressions in $mathbb{Z}_n$ is $Theta(n^{1/3+r_k/(6k)})$, where $r_k in {0,1,2}$ is the remainder when $k$ is divided by $3$. This solves a problem of Hebbinghaus and Srivastav.

Mixing time of fractional random walk on finite fields

We study a random walk on $mathbb{F}_p$ defined by $X_{n+1}=1/X_n+varepsilon_{n+1}$ if $X_n eq 0$, and $X_{n+1}=varepsilon_{n+1}$ if $X_n=0$, where $varepsilon_{n+1}$ are independent and identically distributed. This can be seen as a non-linear analogue of the Chung--Diaconis--Graham process. We show that the mixing time is of order $log p$, answering a question of Chatterjee and Diaconis.