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.
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...
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...
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
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...
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...
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· arXiv.org· 4 citations· ⚡1
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.