We give new explicit constructions of several fundamental objects in linear-algebraic pseudorandomness and combinatorics, including lossless rank extractors, subspace designs, and strong $s$-blocking sets over finite fields.
Our focus is on the small-field regime, where the field size depends only on a secondary parameter (such as the rank or codimension) and is independent of the ambient dimension. This regime is central to several applications, yet remains poorly understood from the perspective of explicit constructions.
In this setting, we obtain the first explicit constructions of lossless rank extractors and subspace designs when the target rank or codimension $r$ is much smaller than the ambient dimension $k$, over finite fields $\mathbb{F}_q$ with $q \ge \mathrm{poly}(r)$ and $q$ non-prime, with near-optimal parameters. For other finite fields, including prime fields and small fields, we obtain weaker but still improved bounds.
As a consequence, we construct explicit strong $s$-blocking sets in $\mathrm{PG}(k-1,q)$ of size $O(s(k-s)q^s)$ for all sufficiently large non-prime fields $q \ge \mathrm{poly}(s)$, matching the best known non-explicit bounds up to constant factors. This significantly improves the previous best bound $2^{O(s^2 \log s)} q^s k$ of Bishnoi and Tomon (Combinatorica, 2026), which requires $q \ge 2^{\Omega(s)}$.
Our main algebraic constructions are function-field analogs of the rank-extractor constructions of Gabizon--Raz and Forbes--Shpilka. We further combine these constructions with PIT-based field reduction. In addition, we develop a complementary Fourier-analytic framework based on $\varepsilon$-biased sets, which yields improved explicit constructions of strong $s$-blocking sets over small fields.
We clarify that our techniques do yield strong lossless rank extractors and subspace designs by counting zeros with multiplicity, and upgrade our analysis accordingly; what they do not yield is an improved bound that depends on the gap between the test-subspace dimension and the codimension of the design subspaces.
We give new explicit constructions of several fundamental objects in linear-algebraic pseudorandomness and combinatorics, including lossless rank extractors, weak subspace designs, and strong $s$-blocking sets over finite fields.
Our focus is on the small-field regime, where the field size depends only on a secondary parameter (such as the rank or codimension) and is independent of the ambient dimension. This regime is central to several applications, yet remains poorly understood from the perspective of explicit constructions.
In this setting, we obtain the first explicit constructions of lossless rank extractors and weak subspace designs for $r\ll k$, where $r$ denotes the rank (or codimension), over finite fields $\mathbb{F}_q$ with $q \ge \mathrm{poly}(r)$ and $q$ non-prime, with near-optimal parameters. For other finite fields, including prime fields and small fields, we obtain weaker but still improved bounds.
As a consequence, we construct explicit strong $s$-blocking sets in $\mathrm{PG}(k-1,q)$ of size $O(s(k-s)q^s)$ for all sufficiently large non-prime fields $q \ge \mathrm{poly}(s)$, matching the best known non-explicit bounds up to constant factors. This significantly improves the previous best bound $2^{O(s^2 \log s)} q^s k$ of Bishnoi and Tomon (Combinatorica, 2026), which requires $q \ge 2^{\Omega(s)}$.
Our approach is primarily algebraic, combining techniques from function fields and polynomial identity testing. In addition, we develop a complementary Fourier-analytic framework based on $\varepsilon$-biased sets, which yields improved explicit constructions of strong $s$-blocking sets over small fields.
