Two-sided linear hashing and quadratic density bounds for smooth lattice coverings

Source abstract

We study random linear projections of a finite-field subset for which every fiber has cardinality close to its mean. We bound the mean fiber size needed to ensure that all fibers satisfy a prescribed relative discrepancy, with a prescribed failure probability. For $S\subseteq\mathbb F_q^n$ projected to $\mathbb F_q^b$, one theorem gives three regimes: at fixed discrepancy and failure probability, sufficient mean fiber sizes are $O(q2^b)$ for arbitrary $q$, $O(q^2)$ when $q$ is at least a suitable constant multiple of $b$, and $O_q(b)$ for fixed $q$. The resulting entropy loss over fixed fields is $h-b=\log_q h+O(1)$, where $h=\log_q|S|$ is the input entropy. This matches the order of the binary obstruction of Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos (1999); we give a quantitative random-source refinement over every fixed field. Our proof combines a quotient-and-average counting lemma with the local balanced/unbalanced argument of Dhar and Dvir (arXiv:2204.01665) and Furstenberg estimates of Dhar and Dvir and Kumar and Mon (arXiv:2609.17020). We apply these bounds in the reduction of Ordentlich, Regev, and Weiss (arXiv:2311.04644) to improve their $O(n^3)$ bound for smooth lattice coverings to $O(n^2)$. For each fixed convex body $K\subseteq\mathbb R^n$, a Haar-Siegel random lattice of covolume one has the number of lattice points in every translate of $K$ within a prescribed relative error of $\operatorname{vol}(K)$, with prescribed high probability, once $\operatorname{vol}(K)\ge Cn^2$ and $n$ is sufficiently large. The constant and dimension cutoff depend only on the error and failure probability. Complements of higher-rank Kakeya sets of Kopparty, Lev, Saraf, and Sudan (arXiv:1003.3736) show that no hashing guarantee for arbitrary subsets can yield a smaller order in the same reduction.