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

Technical Summary: Bilinear Kloosterman Sums over Small Boxes and Uniformity of a Random Walk

1. Problem Statement and Context
The paper addresses two interconnected problems in analytic number theory and probability over finite fields. First, it seeks to establish nontrivial bounds for bilinear Kloosterman sums over "boxes" in arbitrary finite fields $\mathbb{F}_q$ (where $q=p^n$). A box is defined as a coordinate parallelepiped formed by restricting the coefficients of field elements (with respect to a fixed basis over $\mathbb{F}_p$) to intervals in $\mathbb{F}_p$. The classical Weil bound for Kloosterman sums is effective only when the sum is taken over the entire field or very large subsets; it fails to provide nontrivial estimates when the product of the sizes of the summation sets $|B_1||B_2|$ is smaller than $q$. Specifically, the paper targets the range where $|B_1||B_2| > q^{1/2+\epsilon}$, a regime previously inaccessible by standard bounds.

Second, the paper investigates the mixing properties of a specific random walk on $\mathbb{F}_q$. The walk is defined by $S_k = S_0 + W_1 + \dots + W_k$, where the increments $W_i$ are of the form $aX_iY_i + b(X_iY_i)^{-1}$. Here, $X_i$ and $Y_i$ are independent random variables uniformly distributed on boxes $B_1$ and $B_2$. The central question is whether the additive structure inherent in the initial boxes is destroyed by the nonlinear transformation $(x, y) \mapsto axy + b(xy)^{-1}$, leading the distribution of $S_k$ to converge to the uniform distribution on $\mathbb{F}_q$ and its entropy to its maximal value.

2. Methodology
The author employs a combination of Fourier analysis over finite abelian groups, combinatorial number theory, and probabilistic methods.

• Fourier Analysis and Character Sums: The core of the argument relies on bounding the Fourier coefficients of the distribution of the random walk. The paper utilizes the orthogonality of additive characters $\psi(x) = e_p(\text{Tr}(x))$ to relate the decay of these coefficients to the magnitude of bilinear Kloosterman sums.
• Extension of Bourgain's Theorem: The primary technical achievement is extending a theorem by Bourgain (originally for $\mathbb{F}_p$) to arbitrary finite fields $\mathbb{F}_q$. This involves proving that for boxes $B_1, B_2$ with $|B_1||B_2| \ge q^{1/2+\epsilon}$, the sum
  $$\sum_{x \in B_1} \sum_{y \in B_2} \alpha(x)\beta(y)\psi(axy + bx^{-1}y^{-1})$$
  is bounded by $p^{-\delta}|B_1||B_2|$ for some $\delta > 0$.
• Combinatorial Lemmas: The proof of the sum bound utilizes several auxiliary results:
  • Multiplicative Energy: Bounds on the multiplicative energy $E^\times(B)$ of boxes are established, showing $E^\times(B) \ll n \log p \cdot |B|^2$.
  • Pigeonholing and Double Counting: The proof strategy involves partitioning boxes, applying the Cauchy-Schwarz inequality repeatedly, and using Hölder's inequality to reduce the problem to counting solutions to specific equations involving reciprocals.
  • Lemma 2 and Lemma 8: These lemmas provide bounds on the number of solutions to equations of the form $\sum \frac{1}{y+x_i} = \sum \frac{1}{y+x_j}$ and related rational function sums, which are crucial for controlling the "diagonal" terms in the energy estimates.
• Probabilistic Convergence: The decay of the Fourier coefficients is translated into convergence rates for the random walk using standard inequalities relating the Chi-square divergence ($\chi^2$), Total Variation distance ($\|\cdot\|_{TV}$), and Relative Entropy (Kullback-Leibler divergence).

3. Key Contributions and Results

• Theorem 1 (Bilinear Kloosterman Sum Estimate): The paper proves a power-saving estimate for weighted bilinear Kloosterman sums over arbitrary boxes in $\mathbb{F}_q$. The bound is nontrivial whenever $|B_1||B_2| \ge q^{1/2+\epsilon}$. This extends Bourgain's result from the prime field case to general finite fields and arbitrary coordinate boxes.
• Corollary 1 (Expansion of Sum Sets): As a consequence of the sum estimate, the paper establishes that the set of sums of reciprocals of elements in a box expands significantly. Specifically, for any box $B$, the size of the set $kB^{-1}$ (sums of $k$ reciprocals) satisfies $|kB^{-1}| \ge p^{-\delta} \min\{|B|^2, q\}$ for sufficiently large $k$.
• Theorem 2 (Uniformity of Linear Projections): The paper demonstrates that for the random walk $S_k$, every nonzero $\mathbb{F}_p$-linear projection $L(S_k)$ converges exponentially fast to the uniform distribution on $\mathbb{F}_p$. Specifically, the Chi-square divergence decays as $(p-1)\rho^{2k}$, where $\rho = \min\{1, C_\epsilon p^{-\delta}\}$. Consequently, the entropy of any single coordinate (in any basis) approaches its maximum value $\log p$.
• Theorem 3 (Uniformity of the Full Distribution): The paper extends the result to the full distribution of $S_k$ on $\mathbb{F}_q$. It shows that the distribution converges to the uniform distribution on $\mathbb{F}_q$ with a rate governed by $(q-1)\rho^{2k}$.
• Entropy Bounds: The paper provides explicit lower bounds on the entropy of $S_k$ and its projections, showing that the entropy converges to its maximal value ($\log q$ for the full walk, $\log p$ for projections) exponentially fast.

4. Significance and Claims
The paper claims that its estimates are significant because they operate in a range ($|B_1||B_2| > q^{1/2+\epsilon}$) where the classical Weil bound yields no nontrivial information. This allows for the analysis of "small" boxes that were previously inaccessible.

Regarding the random walk, the paper highlights a distinct difference in mixing scales:

• Coordinate-wise mixing: Every nonzero linear projection (and thus every coordinate in any basis) becomes asymptotically uniform after $O(1)$ steps (specifically, when $k > 1/(2\delta)$).
• Full joint mixing: The full distribution on $\mathbb{F}_q$ requires $k > n/(2\delta)$ steps to become uniform.

The author interprets this as evidence that "coordinate-wise pseudorandomness occurs before full joint pseudorandomness," with the latter requiring an additional factor of $n$ (the degree of the field extension). The results quantify how the nonlinear transformation $xy + (xy)^{-1}$ destroys the additive structure of the initial boxes, driving the system toward uniformity and maximizing entropy.