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

Chong Shangguan; Roshan Raj; Zeyu Guo; Zihan Zhang

arxiv: 2604.13431 · v1 · submitted 2026-04-15 · 💻 cs.IT · math.CO· math.IT

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

Zeyu Guo , Roshan Raj , Chong Shangguan , Zihan Zhang This is my paper

Pith reviewed 2026-05-10 13:06 UTC · model grok-4.3

classification 💻 cs.IT math.COmath.IT

keywords explicit constructionsrank extractorssubspace designsstrong blocking setsfunction fieldsfinite fieldspseudorandomnessprojective geometry

0 comments

The pith

Explicit constructions via function fields produce strong s-blocking sets of size O(s(k-s)q^s) over large non-prime fields.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops explicit algebraic constructions for lossless rank extractors, weak subspace designs, and strong s-blocking sets over finite fields in the small-field regime. The field size depends only on the secondary parameter such as rank or s, remaining independent of the ambient dimension k. For non-prime fields with q at least polynomial in s, the resulting strong s-blocking sets achieve size O(s(k-s)q^s), matching the best non-explicit bounds up to constants and improving on the prior explicit bound of 2 to the O(s squared log s) times q^s k. The methods rely on function fields combined with polynomial identity testing, with a Fourier-analytic approach supplying further gains over small fields.

Core claim

The authors construct explicit lossless rank extractors and weak subspace designs over non-prime finite fields F_q with q at least polynomial in the rank r. These objects immediately yield explicit strong s-blocking sets in PG(k-1,q) of size O(s(k-s)q^s) for all sufficiently large such q. The size matches the optimal non-explicit bound up to constant factors and removes the exponential dependence on s that appeared in earlier explicit constructions.

What carries the argument

Function-field constructions of rank extractors that preserve linear independence with high probability, which are then lifted to subspace designs and blocking sets.

Load-bearing premise

The function field and polynomial identity testing methods produce explicit objects with the claimed near-optimal parameters precisely when the finite field is non-prime and at least polynomial in s.

What would settle it

An explicit run of the function-field construction for s=2 and the smallest non-prime q polynomial in 2, followed by a direct count of the output set size, showing it exceeds C s (k-s) q^s for any fixed constant C.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives the first explicit lossless rank extractors and near-optimal strong blocking sets over non-prime fields using function fields, which is a concrete advance worth checking.

read the letter

The headline result is explicit constructions of lossless rank extractors for r much smaller than k over non-prime fields q at least polynomial in r, plus strong s-blocking sets of size O(s(k-s)q^s) that match the best non-explicit bounds up to constants. That improves on the Bishnoi-Tomon bound which carried an extra k factor and required q exponential in s. They also supply a Fourier-analytic backup for smaller fields that gives weaker but still better explicit parameters than before. The algebraic side combines function-field methods with polynomial identity testing, which is a standard toolkit in this area but applied here to hit the small-field regime that has been stuck on explicit constructions. The blocking-set application follows directly from the extractor parameters, so the two parts are linked cleanly. The work is technically grounded in the sense that it states precise parameter regimes and cites the relevant prior bounds without overclaiming. One soft spot is that the strongest results hold only for non-prime fields and sufficiently large q; for prime fields the bounds are weaker, which is honest but limits immediate applicability. Another is that the constructions are algebraic and the paper does not appear to include machine-checked verification or independent numerical checks for small cases, so a referee will need to verify the function-field degree and PIT arguments in detail. No circularity or hidden dependence on k shows up in the claims. This is for people working on explicit pseudorandom objects, subspace designs, and blocking sets in finite geometry. A reader who cares about derandomization or combinatorial constructions over small fields will get usable new objects and a clear improvement over the 2026 bound. It deserves a serious referee because the claims are specific, the improvement is measurable, and the techniques are reproducible in principle even if the proofs are involved.

Referee Report

0 major / 3 minor

Summary. The manuscript develops explicit constructions of lossless rank extractors and weak subspace designs over finite fields in the small-field regime (q depending only on the rank r or codimension s, with q non-prime and at least polynomial in that parameter). It combines function-field techniques with polynomial identity testing to obtain near-optimal parameters for r ≪ k. As a direct application, it yields explicit strong s-blocking sets in PG(k-1, q) of size O(s(k-s) q^s) for all sufficiently large non-prime q ≥ poly(s), matching the best non-explicit bounds up to constant factors and improving the prior explicit bound 2^{O(s^2 log s)} q^s k of Bishnoi-Tomon. A complementary Fourier-analytic construction based on ε-biased sets is supplied for the remaining small-field cases.

Significance. If the derivations hold, the work supplies the first explicit objects in the small-field regime that achieve parameters previously available only non-constructively, thereby closing a notable gap in linear-algebraic pseudorandomness. The function-field-plus-PIT framework is a reusable algebraic contribution, and the explicit blocking-set size is optimal up to constants for the stated field range. The paper also supplies an independent Fourier-analytic complement, increasing the robustness of the results.

minor comments (3)

The precise threshold for 'sufficiently large' q in the main blocking-set theorem (stated in the abstract and presumably in the applications section) should be made explicit, including the polynomial degree in s and any dependence on the characteristic.
Notation for the projective space PG(k-1, q) and the distinction between weak subspace designs and strong blocking sets is introduced early but could be recalled with a short paragraph in the preliminaries for readers outside the immediate subfield.
A few displayed equations in the function-field construction section use the same symbol for both the extension degree and a related parameter; a minor renaming would remove the potential for confusion.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and encouraging summary of the manuscript, for highlighting its significance in closing a gap in explicit constructions for the small-field regime, and for recommending minor revision. We are pleased that the function-field-plus-PIT approach and the resulting near-optimal parameters for lossless rank extractors, weak subspace designs, and strong s-blocking sets are viewed as a reusable contribution.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via independent algebraic techniques

full rationale

The paper's central constructions of lossless rank extractors, weak subspace designs, and strong s-blocking sets are derived from function-field methods combined with polynomial identity testing, plus a separate Fourier-analytic complement using epsilon-biased sets. These are standard, externally verifiable algebraic and analytic tools with no reduction to self-defined quantities, fitted inputs renamed as predictions, or load-bearing self-citations. The claimed size bound O(s(k-s)q^s) for non-prime fields is presented as a consequence of these techniques matching known non-explicit bounds, without any equation or step that equates the output to its own inputs by construction. The approach is self-contained against external benchmarks in algebraic combinatorics.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based solely on the abstract, the paper relies on standard properties of function fields and polynomial identity testing over finite fields; no free parameters, new entities, or ad-hoc axioms are visible in the summary. Full details would be needed to audit any hidden assumptions.

axioms (2)

domain assumption Function fields over finite fields admit explicit constructions of algebraic objects with controlled rank and intersection properties.
Invoked by the primary algebraic approach described in the abstract.
domain assumption Polynomial identity testing can certify or construct explicit rank extractors and subspace designs.
Cited as part of the method for the small-field regime.

pith-pipeline@v0.9.0 · 5644 in / 1626 out tokens · 60580 ms · 2026-05-10T13:06:37.755769+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

[1]

If for someT⊆E,x(T) =r 1(T)for allx∈F, orx(T) =r 2(T)for allx∈F, thenTis the union of sets fromP 1, respectivelyP 2

work page
[2]

Definition B.4.LetFbe a face of the polytopeP(M 1,M 2) with the partitionsP 1,P 2 from Lemma B.3

If for somee∈E,x e = 0for alle∈F, then there is aS 1 ∈ P 1 andS 2 ∈ P 2 such that S1 =S 2 ={e}andν S1 =µ S2 = 0. Definition B.4.LetFbe a face of the polytopeP(M 1,M 2) with the partitionsP 1,P 2 from Lemma B.3. A sequenceC= (e 1, e2, . . . , e2ℓ) of distinct elements ofEis called acyclewith respect to faceF, if consecutive pairs are alternately in a set f...

work page

[1] [1]

If for someT⊆E,x(T) =r 1(T)for allx∈F, orx(T) =r 2(T)for allx∈F, thenTis the union of sets fromP 1, respectivelyP 2

work page

[2] [2]

Definition B.4.LetFbe a face of the polytopeP(M 1,M 2) with the partitionsP 1,P 2 from Lemma B.3

If for somee∈E,x e = 0for alle∈F, then there is aS 1 ∈ P 1 andS 2 ∈ P 2 such that S1 =S 2 ={e}andν S1 =µ S2 = 0. Definition B.4.LetFbe a face of the polytopeP(M 1,M 2) with the partitionsP 1,P 2 from Lemma B.3. A sequenceC= (e 1, e2, . . . , e2ℓ) of distinct elements ofEis called acyclewith respect to faceF, if consecutive pairs are alternately in a set f...

work page