Bilinear Kloosterman sums over small boxes and uniformity of a random walk

Abstract

Given an additive character $\ddot{I}ˆ$ of an arbitrary finite field ${\mathbb{F}}_{p^n}$ and elements $a,b\in {\mathbb{F}}_{p^n}$, $b\ne 0$, we prove a bound on bilinear Kloosterman sums ${\sum }_{x\in B_1}{\sum }_{y\in B_2}\ddot{I}ˆ(axy+b{x}^{-1}{y}^{-1})$, where $B_1,B_2$ denote boxes in ${\mathbb{F}}_{p^n}$. Here, a box is a coordinate parallelepiped obtained by restricting the coefficients of field elements, with respect to a fixed basis of ${\mathbb{F}}_{p^n}$ over ${\mathbb{F}}_p$, to intervals in ${\mathbb{F}}_p$. Our estimates are nontrivial when $|B_1||B_2|>p^{n/2+\hat{I}\mu }$ and hence in a range not accessible by the Weil bound. We also consider the random walk on ${\mathbb{F}}_{p^n}$ defined by $S_k=S_0+W_1+\cdots +W_k$, where $W_i=a{X}_i{Y}_i+b(X_i{Y}_i{)}^{-1}$ and $X_i,Y_i$ are independent uniformly distributed random variables on $B_1$ and $B_2$ respectively. We show that the nontrivial Fourier coefficients of $S_k$ decay exponentially. Consequently, every nonzero ${\mathbb{F}}_p$-linear projection of $S_k$, as well as the full distribution of $S_k$ converge to the uniform distribution on ${\mathbb{F}}_p$ and ${\mathbb{F}}_{p^n}$, respectively. We also obtain bounds on the rate at which the entropy of $S_k$ converges to its maximal value.