Two-sided linear hashing and quadratic density bounds for smooth lattice coverings
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⊆𝔽qn projected to 𝔽qb, one theorem gives three regimes: at fixed discrepancy and failure probability, sufficient mean fiber sizes are O(q2b) for arbitrary q, O(q2) when q is at least a suitable constant multiple of b, and Oq(b) for fixed q. The resulting entropy loss over fixed fields is h−b=logq h+O(1), where h=logq|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(n3) bound for smooth lattice coverings to O(n2). For each fixed convex body K⊆ℝ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 vol(K), with prescribed high probability, once vol(K)≥ Cn2 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.
Related
- Intractable enumeration problems are like Russian nesting dolls: structural properties of monomer-dimer coverings on two-dimensional quadratic lattices
- Quadratic Euler Characteristic of Geometrically Cyclic Branched Coverings
- Lattice coverings by parallelotopes containing cube vertices
- Minimal Covering Bodies and a Minkowski-Type Criterion for Lattice Coverings
- Polynomially larger deletion codes by linear hashing of substring counts
BibTeX
@misc{lund2026twosided,
title = {{Two-sided linear hashing and quadratic density bounds for smooth lattice coverings}},
author = {Ben Lund},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20351},
eprint = {2609.20351},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20351},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Two-sided linear hashing and quadratic density bounds for smooth lattice coverings
AU - Ben Lund
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.20351
UR - https://arxiv.org/abs/2609.20351
AB - 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⊆𝔽_q^n projected to 𝔽_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⊆ℝ^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 vol(K), with prescribed high probability, once vol(K)≥ 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.
ER -