Explicit Rank Extractors and Subspace Designs via Function Fields, with Applications to Strong Blocking Sets

1. Problem Statement and Motivation

The paper addresses a central challenge in theoretical computer science and combinatorics: the explicit construction of fundamental algebraic objects over small finite fields.

• The Regime: The authors focus on the regime where the field size $q$ depends only on a secondary parameter (such as rank $r$ or blocking set parameter $s$) and is independent of the ambient dimension $k$. Specifically, they consider $q \ge \text{poly}(r)$ or $q \ge \text{poly}(s)$, even when $r \ll k$.
• The Gap: While the probabilistic method guarantees the existence of these objects with near-optimal parameters over any field, known explicit constructions typically require the field size to grow with the ambient dimension $k$ (e.g., $q > k$). Bridging this gap is crucial for applications in coding theory, derandomization, and finite geometry.
• Target Objects: The paper targets three interconnected objects:
  1. Lossless Rank Extractors: Collections of matrices that preserve the rank of any full-rank input matrix for most outputs.
  2. Weak Subspace Designs: Collections of subspaces that intersect any fixed subspace of a given dimension in a limited way.
  3. Strong $s$-Blocking Sets: Sets in projective space that intersect every codimension-$s$ subspace in a way that spans the subspace.

2. Methodology

The authors employ a primarily algebraic approach, combining techniques from function fields and polynomial identity testing (PIT), supplemented by a Fourier-analytic framework.

A. Function Fields and Algebraic Geometry (AG) Codes

Instead of using standard polynomial methods over large fields (which require distinct evaluation points in $\mathbb{F}_q$), the authors generalize the polynomial method to function fields.

• Concept: They replace the line (polynomial ring $\mathbb{F}_q[x]$) with an algebraic curve (function field $\mathbb{F}$). Even over small fields, a function field can have many rational places ($N \gg q$), providing enough evaluation points.
• Towers Used:
  • Garcia–Stichtenoth Tower: Used when $q$ is a square ($q=\ell^2$). It achieves the optimal Drinfeld–Vlăduț bound ($N/g \approx \sqrt{q}$).
  • Bassa–Beelen–Garcia–Stichtenoth Tower: Used when $q = p^{2m+1}$. It provides a polynomially related ratio $N/g$.
• Construction Strategy:
  • They construct symbolic matrices using elements from the function field (specifically, functions with prescribed valuations at a distinguished place $P_\infty$).
  • They analyze the determinant of the product of these symbolic matrices and an input matrix $M$.
  • Using the Cauchy–Binet formula and properties of valuations (strong triangle inequality), they prove that the determinant is non-zero as a function.
  • By evaluating this function at rational places, they bound the number of "bad" evaluations where the rank drops, leveraging the Riemann–Roch theorem to control the degree of the determinant.

B. Field Reduction and Polynomial Identity Testing (PIT)

To handle prime fields (where explicit function field towers with optimal parameters are not known to be explicit) and very small fields (like $\mathbb{F}_2$), the authors develop a reduction technique.

• Field Reduction: They construct an object over an extension field $\mathbb{F}_Q$ (where $Q = q^d$) and map it back to $\mathbb{F}_q$.
• The Challenge: Naive field reduction (expanding basis coordinates) causes an exponential blow-up in the size of the collection ($d^r$).
• The Solution (PIT): To avoid exponential blow-up, they treat the coefficients of the linear combination during field reduction as variables. They reduce the problem to finding a hitting set for a specific class of polynomials: symbolic determinants with rank-one summands.
• Result: Using the quasi-polynomial hitting sets by Gurjar and Thierauf [GT20], they reduce the size blow-up from exponential to quasi-polynomial in $r$.

C. Fourier-Analytic Approach

For strong $s$-blocking sets, the authors also develop a complementary approach using $\varepsilon$-biased sets.

• They show that an $\varepsilon$-biased set with sufficiently small bias acts as a blocking set because the indicator functions of subspaces have small $L_1$ Fourier norms.
• They instantiate this using the breakthrough constructions of Ta-Shma [TS17] and Jalan–Moshkovitz [JM21].

3. Key Contributions and Results

The paper provides the first explicit constructions for these objects in the small-field regime with near-optimal parameters.

A. Lossless Rank Extractors

• Non-prime Fields ($q \ge \text{poly}(r)$): They construct explicit $(k, r, L)$ lossless rank extractors with $L = O(r(k-r))$ and size $n$ such that $L/n \le q^{-1/4}$. This matches the best-known non-explicit bounds up to constants.
• Prime Fields ($q \ge \text{poly}(r)$): They achieve $L \le (2r/\delta)^{O(\log r)} r(k-r)$ with $L/n \le \delta$.
• Arbitrary Fields (including $\mathbb{F}_2$): They construct lossless rank dispersers (a weaker notion where at least one matrix preserves rank) with size $n = O(\max(\frac{c \log r}{\log q}, 2)^r r(k-r))$.

B. Weak Subspace Designs

By establishing the equivalence between lossless rank extractors and weak subspace designs, they derive:

• Non-prime Fields: Explicit $(k-r, A)$ weak subspace designs with $A = O(r(k-r))$ and size $n \ge (q^{1/4}/2)A$.
• Prime Fields: Similar bounds with a quasi-polynomial factor in $r$.
• Significance: These match the lower bound $A \ge s(k-s)$ for algebraically closed fields, a feat previously unknown for explicit constructions over small fields.

C. Strong $s$-Blocking Sets

This is a major application of the previous results.

• Non-prime Fields ($q \ge \text{poly}(s)$): They construct explicit strong $s$-blocking sets of size $O(s(k-s)q^s)$.
  • Comparison: This improves upon the previous best explicit bound of $2^{O(s^2 \log s)} q^{sk}$ by Bishnoi and Tomon [BT26], reducing the dependence on $s$ in the leading constant from exponential to polynomial.
  • Optimality: This matches the best-known non-explicit (probabilistic) upper bound up to a constant factor.
• Prime Fields: Size at most $(2s)^{O(\log s)}(k-s)q^s$.
• Arbitrary Fields (via PIT): Size $O(\max(\frac{c \log s}{\log q}, 2)^{s+1} s(k-s)q^s)$.
• Fourier Approach: For all $q$, they provide an alternative construction of size $k q^{(2+o_q(1))s}$. While weaker for large $q$, this is the best known for constant $q$ (e.g., $q=2$), yielding size $2^{O(s)} k q^s$.

4. Significance and Impact

1. Bridging the Explicit/Non-Explicit Gap: The work significantly narrows the gap between probabilistic existence and explicit construction for linear-algebraic pseudorandomness objects in the small-field regime.
2. Coding Theory: The results directly impact the construction of list-decodable codes. Strong subspace designs are the underlying mechanism for optimal list-decodability; explicit constructions over small fields enable practical, efficient codes with these properties.
3. Finite Geometry: The construction of strong $s$-blocking sets with near-optimal size resolves a long-standing open problem in finite geometry, improving the dependence on $s$ from exponential to polynomial.
4. Methodological Innovation: The paper introduces a novel synthesis of function field theory (specifically using towers to generalize the polynomial method) and polynomial identity testing to overcome the limitations of prime fields. This "PIT-based field reduction" is a powerful new tool for derandomization.
5. Applications: The results have immediate implications for derandomization, dimension expanders, and the construction of codes with strong locality and list-decoding properties.

In summary, this paper establishes that for small finite fields, one can explicitly construct fundamental combinatorial objects with parameters that were previously thought to be achievable only via the probabilistic method, fundamentally advancing the state of the art in algebraic combinatorics and coding theory.