Skip to content
Preprint

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

Sep 2026 · 2 citations · 13 references
Mathematics

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.

View source

Similar papers

Preprint Sep 2026

List Decoding, Linear Hashing, and Furstenberg over $\mathbb{F}_q$

We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$. 1. Random linear codes over $\mathbb{F}_q$ with rate $1 - H_q(p) - \epsilon$ are $(p, O(q H_q(p)/\epsilon))$-list decodable with high probability for al...

Vinayak M. Kumar, Geoffrey Mon · 0 citations
Preprint Oct 2026

A near-quadratic lower bound for sets with no unique sums

Let $m(p)$ be the least size of a subset of $\F_p$ with at least two elements for which every sum has two distinct representations as unordered pairs, allowing repetition. We prove that, for every prime $p\ge64$, \[ m(p)\ge2^{-80}\left(\frac{\log p}{\log\log p}\right)^2. \] The argument compresses the full integer coll...

Jian-Feng Hou, Kai Yang · 0 citations
Preprint Oct 2026

Near-Optimal Oracle Bounds for Isotropic Rounding

We give optimal bounds, up to polylogarithmic factors, for rounding convex bodies to near-isotropic position. A convex body $B(0,r)\subseteq K\subseteq B(0,R)$ in $\R^n$ can be rounded using $\Ot(n^3)$ membership queries; the upper bound extends to logconcave distributions. We prove a matching $\Omegat(n^3)$ lower boun...

Yang P. Liu, Richard Peng, Alicia Stepin et al. · 2 citations
Preprint Oct 2026

A Hyperplane Bound and Ward's Divisibility Conjecture

Let $q=p^f$, where $p$ is prime. We prove that every $q$-ary linear code meeting the Griesmer bound, with positive dimension and minimum distance $d\ge1$, is $p^{\max\{0,\nu_p(d)-f+1\}}$-divisible, as asserted in Ward's conjecture. Arbitrary projective column multiplicities are allowed. The geometric ingredient is a bo...

Guang-Hui Zhang · 1 citation
Preprint Sep 2026

Weak $k$-metric dimension of Hamming graphs: rectangular products and near-maximum parameters

We determine weak $k$-metric dimensions for several families of Hamming graphs. For $n\ge3$, $m>n$, and $3\le k\le2n$, a cyclic construction proves Conjecture 6.1 of Fern\'andez, Klav\v{z}ar, Kuziak, Mu\~noz-M\'arquez and Yero (2026) on $K_n\square K_m$. For these rectangular products, we also prove that $\operatorname...

Aryan Kumar · 0 citations
Sep 2026

Polynomially larger deletion codes by linear hashing of substring counts

The result provides an edit-distance analogue of Varshamov's 1957 bound in the Hamming metric, both in the leading redundancy coefficient and in the role of linear independence in the proof.

Eyal En Gad · 4 citations · ⚡1

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.