{
  "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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.20351",
  "author_total": 1,
  "authors": [
    {
      "name": "Ben Lund"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/4q77tmztakmnj.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.20351",
  "fulltext_url": null,
  "id": "4q77tmztakmnj",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.20351",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "math.CO"
    ],
    [
      "openalex",
      "2607|Limits and Structures in Graph Theory"
    ]
  ],
  "openalex": "W7213589007",
  "pdf_url": "https://arxiv.org/pdf/2609.20351",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-17",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/4q77tmztakmnj.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:22:23Z",
      "native_id": "2609.20351",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.20351"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "Two-sided linear hashing and quadratic density bounds for smooth lattice coverings",
  "title_text": "Two-sided linear hashing and quadratic density bounds for smooth lattice coverings",
  "type": "preprint",
  "updated_at": "2026-10-30T12:22:23Z",
  "url": "https://research.draconitic.com/paper/4q77tmztakmnj",
  "venue": "arXiv",
  "versions": []
}