Extractors for Images of Varieties

Zeyu GuoSupported in part by a Simons Investigator Award (#409864, David Zuckerman).
CSE Department
Ohio State University

Ben Lee Volk
Efi Arazi School of Computer Science
Reichman University

Akhil Jalan
Computer Science Department
University of Texas at Austin

David ZuckermanSupported in part by NSF Grants CCF-1705028 and CCF-2008076, and a Simons Investigator Award (#409864), and the Center of Mathematical Sciences and Applications at Harvard University.

Computer Science Department
University of Texas at Austin

We construct explicit deterministic
extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map $f : \FF_q^r \to \FF_q^n$ to an element sampled uniformly at random from a $k$-dimensional variety $V \subseteq \FF_q^r$. This class of sources generalizes both polynomial sources, studied by Dvir, Gabizon and Wigderson (FOCS 2007, Comput. Complex. 2009), and variety sources, studied by Dvir (CCC 2009, Comput. Complex. 2012).

Assuming certain natural non-degeneracy conditions on the map $f$ and the variety $V$, which in particular ensure that the source has enough min-entropy, we extract almost all the min-entropy of the distribution.
Unlike the Dvir–Gabizon–Wigderson and Dvir results, our construction works over large enough finite fields of arbitrary characteristic.
One key part of our construction is an improved deterministic rank extractor for varieties.
As a by-product, we obtain explicit Noether normalization lemmas for affine varieties and affine algebras.

Additionally, we generalize a construction of affine extractors with exponentially small error due to Bourgain, Dvir and Leeman (Comput. Complex. 2016) by extending it to all finite prime fields of quasipolynomial size.

§ INTRODUCTION

Randomness is a powerful resource in computing.  There are many useful randomized algorithms, and randomness is provably necessary in cryptography and distributed computing.  Naturally, these uses of randomness assume access to uniformly random bits.  However, it can be expensive or impossible to obtain such high-quality randomness.
A randomness extractor converts low-quality randomness into high-quality randomness.

Low-quality random sources can arise in several ways.  First, natural sources of randomness may be defective.  Second, in cryptography, if an adversary gains information about a string, then conditioned on this information, the string is weakly random.  Third, in constructing pseudorandom generators, a similar situation arises when we condition on the state of the computation.  Besides the computer science motivation, randomness extraction questions are natural mathematically.

We model a weak source as a class $\mathcal{D}$  of distributions over a finite set $\Omega$.  A randomness extractor for $\mathcal{D}$
is a deterministic function that extracts randomness from any distribution in $\mathcal{D}$.

An extractor for a class $\mathcal{D}$ of distributions with error $\eps$, or an $\eps$-extractor, is a function $\Ext : \Omega \to B$ such that
for any $D \in \mathcal{D}$, the distribution $\Ext(D)$ is $\eps$-close, in statistical distance, to the uniform distribution over $B$.

Typically the codomain $B$ will be $\set{0,1}^m$.

The most general class of distributions is the set of distributions with high min-entropy, i.e., distributions that do not place much probability on any string.  However, it is not hard to show that it is impossible to extract from such sources.
It is possible to extract using an auxiliary seed, and there are many applications of such seeded extractors (see [52] for a survey).
It is also possible to extract from two independent general weak sources (e.g., [10]).
However, if we want to avoid adding a seed and only have one source, we must restrict the class of distributions further.

Various models of weak sources have been studied.  It is not hard to show that if there are not too many distributions in the class, then most functions are extractors with excellent parameters.  Of course, we really want efficiently-computable extractors.

Models of weak sources tend to be either complexity-theoretic or algebraic.
In this work, we focus on algebraic sources. That is, we consider distributions over subsets $\Omega$ which have a “nice” algebraic structure.

§.§ Algebraic Sources of Randomness

Suppose $\FF$ is a finite field and $\Omega=\FF^n$. The simplest class of algebraic sources is the set of affine sources. An affine source is simply the uniform distribution over an affine subspace $V \subseteq \FF^n$ of dimension $k$. Note that since $|V|=|\FF|^k$, the single parameter $k$ also determines the min-entropy of the uniform distribution over the source.

Gabizon and Raz [20] constructed an explicit extractor $\Ext : \FF^n \to \FF^{k-1}$, assuming the field size is bounded from below by a large enough polynomial in $n$. For a large enough field size $q$, their construction extracts almost all of the randomness from the source and has error $\eps = 1/\poly(q)$.

The last feature is slightly undesirable, as ideally, one would like the error to decrease exponentially with $k$, the dimension of the source. Such a construction was given by Bourgain, Dvir and Leeman [4], albeit their construction requires the field size to be slightly super-polynomial in $n$, and only works for certain fields.

Over smaller fields, constructing affine extractors for small min-entropy is a more challenging task. Further, it is possible to show that any function $f:\FF_2^n \to \FF_2$ is constant on some affine subspace of dimension $\Omega(\log n)$ (see, e.g., Lemma 6.7 of the arXiv version of [1]), and thus one cannot hope to extract even a single bit when the min-entropy is smaller than $\log n$ (compare this with the fact that over large fields, the Gabizon–Raz extractor works for any $k$).

Bourgain [7] constructed an extractor that works over $\FF_2$ for min-entropy $k=cn$ for a small constant $c$. This result was slightly improved by Yehudayoff [54] and Li [32].
Li [33] then presented a much improved construction which works when the min-entropy is as small as $k=\log^C(n)$ for some constant $C$, which was improved by [8] to $k=\log^{1+o(1)} (n)$. However, one drawback of the last two constructions is that the error parameter $\varepsilon$ is either constant or polynomially small, whereas one would hope for it to be exponentially small in $k$, as in the earlier constructions of Bourgain, Yehudayoff and Li.

There are several natural ways to generalize affine sources, but some care is needed when defining those generalizations. As we remarked earlier, for an affine subspace, the single parameter $k$ determines its size and hence the min-entropy of the corresponding source. For more complicated algebraic sets, however, as we shall now see, there are multiple parameters controlling their “complexity,” and the connection between those parameters and the min-entropy of the source is not always obvious.

Dvir, Gabizon and Wigderson [12] considered polynomial sources, which are defined by applying a low-degree polynomial map $P : \FF^k \to \FF^n$ on a uniformly random input from $\FF^k$. (Note that affine sources are a special case of polynomial sources when the degree equals one.) They further impose the algebraic condition that the Jacobian matrix of the map is of full rank, which in particular guarantees that the min-entropy of the source is high, assuming the characteristic of the field is large enough. The field size required by the construction of [12] is $\poly(k,d,n)^{k}$.

Dvir [15] studied a different generalization called variety sources, which are uniform distributions over sets $V \subseteq \FF^n$ that are the common zeros of a set of low-degree polynomials. Varieties also have an associated concept of dimension, but unlike the affine case, over finite fields having a large dimension does not guarantee by itself that the set $V$ is large, and thus this condition must be imposed explicitly. Dvir presented two constructions. The first requires exponentially large fields and works for any dimension $k$.
The second requires the variety to have size larger than $|\FF|^{n/2}$, but the field size depends only polynomially on the degree $d$ of the polynomials defining $V$.

Over $\FF_2$, the situation is much more mysterious. This setting is well motivated, since it turns out that explicit constructions of extractors (or even dispersers) for varieties with various parameters would imply new circuit lower bounds. Golovnev, Kulikov and Williams [19] proved multiple such results. One is that explicit extractors for varieties of size at least $2^{\varepsilon n}$ defined by constant degree polynomials would imply lower bounds for general circuits of the form $Cn$ for larger constants $C$ than what is currently known.
They also showed that extractors for varieties of size at least $2^{0.99n}$ defined by polynomials of degree at most $n^{0.01}$ would imply super-linear lower bounds for boolean circuits of depth $O(\log n)$, a long-standing challenge in complexity theory (see also [26]).

As for constructions over $\FF_2$, Li and Zuckerman [35] showed how to use correlation bounds against low-degree polynomials to obtain extractors for variety sources defined by degree $d$ polynomials for $d=O(1)$ and size at least $2^{(1-c_d)n}$ for some constant $c_d$ that depends on $d$. Remscrim [46] proved that the majority function is an extractor for varieties defined by polynomials of degree at most $n^{\alpha}$ and size at least $2^{n-n^{\beta}}$, assuming $\alpha+\beta < 1/2$. Thus, all the known constructions are not strong enough to imply new circuit lower bounds.

§.§ Our Results

§.§.§ Extractor for Polynomial Images of Varieties

In this paper, we study the class of polynomial images of varieties, which generalizes both variety sources and polynomial sources. Informally, the source is specified by a variety $V \subseteq \FF^r$ and a polynomial map $f: V \to \FF^{n}$,
and a sample from the source is a random variable $X$ computed by uniformly at random picking an element $x \in V$ and outputting $f(x)$.
We would like to construct an efficient extractor $\Ext : \FF^{n} \to \set{0,1}^m$
that has small error $\eps$ and large output length $m$.
The largest $m$ we can hope for is the min-entropy of the input, which is approximately
$k \log q$, where  $q = |\FF|$ and $k$ is the dimension of the variety $V$ (see Section <ref> for a definition of this notion). Our main result is a construction of an extractor with $m \approx k\log q$.

Formally defining such sources takes some care, since varieties and their associated complexity parameters are easier to define over algebraically closed fields. As in previous work, we further need to assume some natural non-degeneracy conditions on the variety $V$ and the map $f$. We now describe those sources in more detail.

Polynomial images of variety sources.
Let $\FF$ be a field.
For $h_1,\dots,h_s\in \FF[X_1,\dots,X_n]$, define

\[
\mathcal{L}_{h_1,\dots,h_s,\FF}:=\{c_0+c_1 h_1+\dots+c_s h_s: c_0,\dots,c_s\in\FF\}\subseteq \FF[X_1,\dots,X_n],
\]

i.e., $\mathcal{L}_{h_1,\dots,h_s,\FF}$ is the linear span of $h_1,\dots, h_s$ and $1$ over $\FF$.

Denote by $\overline{\FF}$ the algebraic closure of $\FF$.
An affine variety $V\subseteq \overline{\FF}^n$ over $\FF$ is the set of common zeros of a set of polynomials in $\FF[X_1,\dots,X_n]$. Two parameters naturally associated with a variety $V$ are its dimension, denoted $\dim V$, which equals the length of the maximal chain with respect to inclusion of distinct irreducible subvarieties, and its degree, denoted $\deg V$, which is the number of intersection points of the variety with an affine subspace of codimension $\dim V$  in general position (we refer to Section <ref> for more formal definitions).

Let $n,d\in\NN^+$ and $k\in\NN$.
We say a distribution $D$ over $\FF_q^{n}$ is an $(n,k,d)$ algebraic source over $\FF_q$ if there exist $r\in\NN$, an affine variety $V\subseteq\overline{\FF}_q^r$ over $\FF_q$, polynomials $h_1,\dots,h_s\in \FF_q[X_1,\dots,X_r]$
with $\deg h_1\geq \dots \geq \deg h_s$,
and $f_1,\dots,f_n\in \mathcal{L}_{h_1,\dots,h_s,\FF_q}$ such that
$D=f(U_{V(\FF_q)})$, where $f:\overline{\FF}_q^r\to \overline{\FF}_q^{n}$ is the polynomial map defined by $f_1,\dots,f_{n}$, and $U_{V(\FF_q)}$ is the uniform distribution over $V(\FF_q):=V \cap \FF_q^r$, and further, the following conditions hold:

* At least one irreducible component of $V$ of dimension $\dim V$ is absolutely irreducible.

* For every irreducible component $V_0$ of dimension $\dim V$ that is absolutely irreducible, the dimension of $\overline{f(V_0)}$ is at least $k$, where $\overline{f(V_0)}\subseteq \overline{\FF}_q^n$ denotes the closure of $f(V_0)$, i.e., the smallest affine variety over $\FF_q$ containing $f(V_0)$.

* $\deg V\cdot \prod_{i=1}^{k} \deg h_i \leq d$.[Note that $\dim \overline{f(V)}\geq k$ by previous conditions. So we necessarily have $s\geq k$ and $\deg h_i\geq 1$ for $i\in [k]$. This also implies $\deg V\leq d$.]

In addition, we say $D$ is an irreducible $(n,k,d)$ algebraic source over $\FF_q$ if $V$ can be chosen to be irreducible.
We say $D$ is a minimal $(n,k,d)$ algebraic source over $\FF_q$ if $V$ can be chosen to have dimension $k$.
Finally, we say $D$ is an irreducibly minimal $(n,k,d)$ algebraic source over $\FF_q$ if $V$ can be chosen to be irreducible of dimension $k$.

The conditions in Definition <ref> may look a bit contrived at first glance. However, as we now explain, they are quite natural, and indeed some form of them, as observed in previous work, is necessary.

The third condition is simply a convenient way to “pack” multiple “complexity” parameters of the components of the source that arise in the analysis. That is, $d$ is a single complexity parameter that, in particular, bounds the degree of the variety $V$ and the product of degrees of the polynomial map $f$. Having $d$ as a single parameter simplifies the statements of our theorems and clarifies the dependence between the various parameters: the larger $d$ is, the larger the field size we require and the smaller the output length of the extractor.

The purpose of the first two conditions is to guarantee that our source has enough min-entropy. As observed in previous work [12, 15], it is quite easy to come up with simple varieties $V$ (even of high dimension) or polynomial maps $f$ (even of low degree) such that sources arising as $f(V)$ would have very few points in $\FF_q^n$, so that there will be little to no randomness to extract.

The first condition is analogous to (and, as shown in Appendix <ref>, roughly equivalent to) Dvir's [15] condition that the variety $V$ contains enough points in $\FF_p^n$. The second condition is analogous to (and, over fields of large characteristic, implied by) the full-rank Jacobian condition of Dvir, Gabizon and Wigderson [12]. Thus, not only is some form of conditions 1 and 2 necessary for proving any meaningful results, but moreover, these conditions naturally generalize the conditions imposed by previous related works.

Finally, we note that the name “$(n,k,d)$ algebraic sources” suppresses the dependence on the parameter $r$ in the definition, which is the ambient dimension in which the variety $V$ lies. This is because our result, stated next, has no dependence on $r$. Even in the case where $r$ is very large with respect to $n$, $k$ and $d$, our results only depend on the latter three parameters. Further, note that when $r$ is very large, $\dim V$ can also be very large compared with $n$ and $k$. However, as the definition hints, we will reduce this case to the case where $\dim V=k$.

We can now state our main theorem.

Let $n,d\in\NN^+$, $k\in\NN$, and $\epsilon\in (0,1/2]$.
Let $q$ be a power of a prime $p$. Suppose $q\geq (nd/\epsilon)^c$, where $c>0$ is a large enough absolute constant. Then there exists an explicit
$\epsilon$-extractor $\Ext: \FF_q^{n}\to\{0,1\}^m$ for $(n,k,d)$ algebraic sources over $\FF_q$
with output length $m \geq k\log q-4\log\log p-O(\log (nd/\epsilon))$.
and an absolute constant $c'>0$ satisfying the following:

* If $p>(d/\epsilon)^{c'}$, then $m\geq k\log q-\log\log p-O(\log n+\log d+\log(1/\epsilon))$.

* Otherwise, $m\geq k\log q-O(\log n+\log d+\log(1/\epsilon))$.

It can be shown that any $(n,k,d)$ algebraic source $D$ over $\FF_q$, where $q\geq (kd)^c$ for a sufficiently large constant $c>0$, is (close to) a distribution with min-entropy at least $k\log q-O(\log d)$. Moreover, this estimate of the min-entropy is tight up to an additive term $O(\log d)$ if $D$ is not an $(n,k+1,d)$ algebraic source over $\FF_q$. See Lemma <ref> and Proposition <ref>. Therefore, the extractor in Theorem <ref> extracts most of the min-entropy from $(n,k,d)$ algebraic sources.
In addition, Theorem <ref> works over finite fields of any characteristic, while the extractors by Dvir, Gabizon, and Wigderson [12] and Dvir [15] require large enough characteristics.

As is standard in the literature, by “explicit” we mean that the output of the extractor is computable in time $\poly(n, \log q)$ (note that the input length to the extractor is $n \log q$).

Along the way to proving Theorem <ref>, we construct several other algebraic pseudorandom objects which are interesting on their own. We mention some of these constructions when we give an overview of our construction in Section <ref>.

§.§.§ Affine Extractors for Quasipolynomally Large Fields with Exponentially Small Error

Recall that an explicit affine extractor is
an efficiently computable function $\Ext : \FF^n \to \FF^m$ such that for every affine subspace $V \subseteq \FF^n$ of dimension $k$, and a random variable $X$ uniformly sampled from $V$, $\Ext(X)$ is close to the uniform distribution over $\FF^m$. We would like $m$ to be as close to $k$ as possible and, ideally, the error parameter $\epsilon$ to be exponentially small in $k$.

As mentioned earlier, the extractor of Gabizon and Raz [20] achieves $m=k-1$ and error $\varepsilon$ only polynomially small in the field size $q$. In particular, the error does not decrease with $k$. Bourgain, Dvir and Leeman [4] constructed an affine extractor with $m$ arbitrarily close to $k/2 $ and error $q^{-\Omega(k)}$. However, their construction requires $q$ to be slightly super-polynomial in $n$, namely $q=n^{\Omega(\log \log n)}$, and furthermore only works for “most” prime fields $\FF_q$. We improve the analysis of their construction and present a construction with identical parameters that works for all prime fields, assuming $q=n^{\Omega(\log \log n)}$.

For every $0 < \beta < 1/2$, there exists a constant $C$ such that the following holds: Let $k \le n$ be integers and $\FF$ be a prime field of size $q \ge n^{C \log \log n}$. Let $m=\beta k$. There exists an efficiently computable function $E : \FF^n \to \FF^m$ which is an affine extractor for min-entropy $k$ with error $q^{-\Omega(k)}$.

§.§ Techniques

Our construction from Theorem <ref> combines several techniques used in previous related constructions, as well as several new ideas which are required to successfully apply these techniques.
It is convenient to think of the construction as proceeding in several steps.

*Preliminary step: decomposing the sources.
Our definition for algebraic sources (Definition <ref>) is quite general, and it is convenient to work with slightly “nicer” sources. We start by approximating general $(n,k,d)$ algebraic sources as convex combinations of irreducibly minimal $(n,k,d)$ algebraic sources. Recall that this means that the variety $V$ is irreducible and has dimension $k$.

This step is done in Section <ref>: we first decompose a general source into a convex combination of irreducible sources in a manner that follows naturally from the decomposition of $V$ itself as a union of irreducible components. We then decompose an irreducible source into irreducibly minimal sources roughly by intersecting it with a linear space of the appropriate dimension. Both parts of the arguments incur a small error.

*First step: extracting a short seed.
Having reduced to the case of irreducibly minimal sources, we first design an extractor that extracts a small number of bits from the source. One commonly used technique for doing that is to show that the source is an $\epsilon$-biased distribution, i.e., a distribution whose nontrivial Fourier coefficients are all small. Similar methods work when the source is close to such a distribution or to a convex combination of such distributions. Analyzing and bounding the Fourier coefficients is often done using bounds on exponential sums from algebraic geometry, such as Bombieri's estimate (Theorem <ref>). We follow this general paradigm as well.

However, the case where the field characteristic is small presents some unique challenges to overcome. We first prove an extension of Bombieri's theorem for small characteristic $p$.  This extension bounds the corresponding exponential sums save for possibly a small set of “bad” characters. Hence, we then define and study a more general class than $\epsilon$-biased distributions: $(\epsilon,e)$-biased distributions, which are distributions in which all but at most $e$ of the Fourier coefficients have absolute value at most $\epsilon$. We show that the sources we consider are close to convex combinations of such distributions (for meaningful values of $\epsilon$ and $e$), and construct extractors for such distributions.

Previously, the XOR lemma has been used to construct extractors for $\eps$-biased sources; see, e.g., Rao [45].
We extend these ideas to the more general and challenging setting of $(\eps, e)$-biased distributions. On the technical level, we construct explicit functions $f: \FF_p^n \to \FF_p^t$ with the following properties: for every nontrivial character $\psi$ of $\FF_p^t$, both the $L_1$ and the $L_\infty$ norms of the Fourier transform of $\psi \circ f$ (which is a function from $\FF_p^n$ to $\mathbb{C}$) are upper bounded by sufficiently small quantities. We in fact present two constructions of such functions $f$. The first is based on standard error-correcting codes over $\FF_p$, and the second is an improved construction based on rank-metric codes. Those constructions appear in Section <ref>.

*Second step: applying a seeded extractor.

Having extracted a small number of bits, we wish to use them as a seed in an application of a seeded extractor on the source to extract almost all the min-entropy. The challenge, of course, is that the seed is correlated with the source, whereas a seeded extractor requires the seed to be independent of the source. Techniques for dealing with these problems were developed in [22, 20], as this is also the general methodology in their extractor constructions. This is done by analyzing the conditional distribution of the source conditioned on any possible output of the seeded extractor with a fixed seed, and showing that it maintains some nice properties. We first analyze the case where the image $f(V)$ of the polynomial map is of full rank inside $\FF^k$, using the effective fiber dimension theorem. We then consider the general case. In order to reduce to that case, we apply a rank extractor for varieties, a notion we define and develop in this work, building upon previous work which developed rank extractors for linear spaces.

*Rank extractor for varieties.

Let $V \subseteq \FF^n$ be a $k$-dimensional variety. We would like to obtain a map $E : \FF^n \to \FF^k$ which “extracts” all the rank from $V$, in the sense that $E(V) \subseteq \FF^k$ is $k$-dimensional. The first obvious challenge is that $E(V)$ need not necessarily be a variety. It is thus natural in this case to consider the closure of $E(V)$ in $\overline{\FF}^n$ where $\overline{\FF}$ is the algebraic closure of $\FF$.

Previous work has considered the case where $V$ is a linear subspace. In this case, observe that if $E$ is linear, then $E(V)$ is also a linear subspace. However, there clearly cannot be a single map $E$ that preserves the dimension of all linear subspaces, as given any fixed $E$, one could take $V$ to be the kernel of $E$. Therefore, a natural relaxation is to consider seeded linear rank extractors, which are collections of linear maps $E_1, \ldots, E_t$ such that for every $V$, most of the maps preserve the dimension. Such objects were first defined and constructed by Gabizon and Raz [20]. Improved and optimal parameters (in terms of the “seed length,” i.e., the number of maps) were obtained by Forbes and Shpilka [18], and a systematic study of these objects appears in [16].

In this work, we observe that seeded linear rank extractors for extractors are also seeded linear rank extractors for varieties (see Section <ref>). The key insight is that rank extractors (for linear subspaces) preserve the dimensions of the tangent spaces at nonsingular points of the variety, which turns out to be a sufficient criterion.

Linear rank extractors are very useful because they enable us to condense sources that are not full-rank to full-rank sources without increasing the degrees of the polynomial maps. However, it turns out that it is also possible to construct deterministic rank extractors for varieties, which we do in Section <ref>. Such extractors are obviously not linear maps, although in our constructions, they are polynomials of fairly small degrees (polynomial in $n$ and in the degree $d$ of the variety). We remark that Dvir [15] constructed such an extractor for one-dimensional varieties, and his extractor is a polynomial of degree exponential in $n$.  In addition, Dvir, Gabizon and Wigderson [12] constructed rank extractors for polynomial sources using a different technique.

Our construction adapts the construction of Dvir, Kollár and Lovett [13], who constructed different pseudorandom objects called variety evasive sets. By modifying their proof, we are able to show that a similar construction yields a deterministic rank extractor for varieties. This essentially follows because their map $\varphi$ satisfies the property that for every low-degree variety $V$ and every point $b \in \FF^k$, the intersection $\varphi^{-1}(b) \cap V$ is a finite set.  Dvir, Kollár and Lovett prove it only for the case $b=\mathbf{0}$, but it is not hard to extend it to general $b$.

*Explicit Noether normalization lemmas.
As a by-product of the above construction of deterministic rank extractors for varieties, we prove explicit Noether normalization lemmas for affine varieties and affine algebras. The Noether normalization lemma [43, 41] is a classical result in commutative algebra and algebraic geometry, which states that any affine variety of dimension $k$ admits a surjective finite morphism to an affine space of dimension $k$.
We show that the construction in [13] in fact gives a direct construction of such a finite morphism.
In contrast, the textbook proof of Nagata [41] is iterative and uses polynomials of degrees that are at least doubly exponential in the number of steps of the iteration.

Our proof is inspired by a geometric argument of  Kollár, Rónyai and Szabó [30].
See Section <ref> for more details.

*Affine extractors with exponentially small error.

Our proof of Theorem <ref> follows a very similar route to the proof of the main theorem of Bourgain, Dvir and Leeman [4], who constructed such an extractor for prime fields $\FF_q$ for “typical” primes $q$. Our main contribution is an improved number-theoretic lemma (Proposition <ref>) which shows how to find $n$ distinct integers $d_1, \ldots, d_n$ with desirable number theoretic properties. The proof then proceeds by estimating the Fourier coefficient of the distribution obtained by applying our extractor to a linear subspace using an exponential sum estimate of Deligne, much in the same way as [4].

§.§ Comparison with Previous Work

The two works closest to ours are by Dvir [15] and Dvir, Gabizon and Wigderson [12], both of which construct extractors for sources with algebraic structures.

As mentioned earlier, Dvir, Gabizon and Wigderson [12] study polynomial sources, defined by picking an element $x \in \FF_q^k$ uniformly at random and applying a polynomial map $f : \FF_q^k \to \FF_q^n$ of degree at most $d$. This is a special case of the sources we consider when the variety $V$ is taken to be $\FF_q^k$.

They further add the non-degeneracy condition that the Jacobian of the mapping $f$, namely, its matrix of partial derivatives, has full rank. This in particular guarantees that the source has a high enough min-entropy. Their main theorem gives an explicit extractor that outputs a constant fraction of the min-entropy over prime fields $\FF_p$ of cardinality $\poly(n,d)^{Ck}$ for some constant $C$. Our construction in Theorem <ref>, on the other hand, works for a larger class of sources, outputs almost all the min-entropy, and works over finite fields of small characteristics as well.

Dvir [15] considers variety sources, which he defines as uniform distributions over sets of the type $\set{x : f_1(x)=f_2(x) = \cdots = f_t(x)=0}$ in $\FF_p^n$, where $\deg f_i \le d$ for all $i$.
These sources are also a special case of the type of sources we consider. One should note, however, the different usage of the term “degree” in our definitions: Dvir always refers to the degree $\deg f_i$ of the polynomials which define the variety $V$, whereas we refer to the degree $\deg V$ of $V$ as an affine variety, which is often much larger.

Assuming $\dim V=k$ and $|V| \ge p^{k-c}$ for some small constant $c>0$, Dvir's extractor [15] outputs a constant fraction of the min-entropy over prime fields of characteristic $p>d^{Cn^2}$ for some constant $C$. Again, Dvir uses the parameter $d$ differently than we do in Theorem <ref>. In particular, in our construction, the field size $q$ is only polynomial in the parameter $d$ (but $d$ might be exponential in $n$).

As mentioned in the discussion after Definition <ref>, our assumptions are weaker than those of [12] and [15]. Thus, as our sources is more general, the characteristic in our results can be arbitrary, and our conclusions are stronger (since we extract more output bits), it follows that in particular our result subsumes the extractors of [12] and [15].

Dvir [15] also presents a different construction that outputs a very small number of bits from very large varieties over small fields. This construction is incomparable with our results.

On the more technical level, we discuss a particular feature of our proof that distinguishes it from [12, 15] and, in particular, allows us to extend the output length.

For simplicity, consider the case of $(1,1,d)$ algebraic sources. As mentioned in Section <ref>, we first prove an extension of Bombieri's estimate that holds even if the characteristic $p$ is small: if $p$ is small, this result implies that a $(1,1,d)$ algebraic source $D$ over $\FF_q$ is a convex combination of
$(\epsilon,d)$-biased sources. That is, we allow a few large Fourier coefficients.  Then we use the machinery developed in Section <ref> to extract randomness from $D$. On the other hand, if $p$ is large enough, then $D$ has no large nontrivial Fourier coefficients; it is $\epsilon$-biased. In this case, the XOR lemma is sufficient, as argued in [12, 15].

To apply Bombieri's estimate to a high-dimensional affine variety $V$, we follow [12, 15] and decompose $V$ into a family of affine curves $C_i$ such that the polynomial $f$ that does not vanish identically on $V$ still does not vanish on most $C_i$.

In [12], this is achieved using an argument based on the Jacobian criterion for algebraic independence, but it works only when the characteristic $p$ is large. Instead of using this argument, we use the decomposition of $(n,k,d)$ algebraic sources into irreducibly minimal $(n,k,d)$ algebraic sources proved in Section <ref>, whose proof is based on the effective fiber dimension theorem (Theorem <ref>) and works for any characteristic.

The last idea we introduce is the use of the effective Lang–Weil bound (Theorem <ref>), which allows us to extract almost $\log q$ bits.
To explain the idea, consider an affine variety $V\subseteq\AA_{\FF_q}^n$ and write $V(\FF_q)$ as a disjoint union of $C_i(\FF_q)$ for a family of affine curves $C_i$ over $\FF_q$. Let $f$ be a low-degree polynomial and assume for simplicity that $f$ is non-constant on every $C_i$. Let $\chi$ be a nontrivial character of $\FF_q$.
The following win-win argument was used in [12] to bound the bias $\delta:=\left|\Ex_{x\in V(\FF_q)}[\chi(f(x))]\right|$:
For a curve $C_i$, if $|C_i(\FF_q)|$ is small, say $|C_i(\FF_q)|\leq \Delta$ for some threshold $\Delta$, then its contribution to the bias $\delta$ is small assuming that $V$ has many rational points. On the other hand, if $C_i(\FF_q)>\Delta$, then Bombieri's estimate (Lemma <ref>), together with the fact that

\[
\left|\Ex_{x\in C_i(\FF_q)}[\chi(f(x))]\right|=\frac{\left|\sum_{x\in C_i(\FF_q)}[\chi(f(x))]\right|}{|C_i(\FF_q)|}
\leq \frac{\left|\sum_{x\in C_i(\FF_q)}[\chi(f(x))]\right|}{\Delta},
\]

implies that $\left|\Ex_{x\in C_i(\FF_q)}[\chi(f(x))]\right|$ is small. Considering all curves $C_i$ shows that the bias is small. We note that no information about $|C_i(\FF_q)|$ was used in this win-win argument. For this reason, the choice of threshold $\Delta$ cannot be too large or too small, and the resulting extractors only extract a constant fraction of $\log q$ bits. To improve the output length, we observe that the effective Lang–Weil bound (Theorem <ref>) together with Lemma <ref> gives more information about $|C_i(\FF_q)|$. In particular, for an irreducible affine curve $C$, the number $|C(\FF_q)|$ is either close to $q$ or very small, depending on whether $C$ is absolutely irreducible.
Exploiting this fact yields an explicit construction of deterministic extractors that output almost $\log q$ bits.

§.§ Open Problems

While improving the dependence on any of the parameters in our construction remains an open problem, in our opinion, the main challenge is reducing the field size.
In our construction for polynomial images of varieties (Theorem <ref>), we require field size $\poly(n,1/\epsilon,d)$. We stress that for certain varieties, $d$ can be exponential in $n$ (although it is by no means necessarily so).
Can we construct extractors for significantly smaller fields, perhaps even constant size?

As mentioned above, over very small fields, such as $\FF_2$, certain Ramsey-theoretic lower bounds imply that constructions such as ours that work for any min-entropy cannot exist. A key reason to study $\FF_2$ is that explicit extractors with certain parameters imply new circuit lower bounds.

In our construction of new affine extractors (Theorem <ref>), we obtain a field size that is slightly super-polynomial in $n$. It is a very appealing open problem to reduce the field size to a polynomial in $n$.

A related problem is reducing the degree of our deterministic rank extractor. In Section <ref>, we construct a deterministic rank extractor for varieties whose degree is $\poly(n,d)$ for degree $d$ varieties. Reducing the degree, perhaps to depend only on $d$, would help lower the field size requirement for the extractor for polynomial images of varieties to depend only on the degree.

We end with two general questions.  Can our constructions or techniques help in designing extractors for larger and more general classes of sources, either algebraic or complexity-theoretic? Do our constructions have any complexity-theoretic implications, such as lower bounds for certain models of computation?

§ NOTATIONS AND PRELIMINARIES

Let $\NN=\{0,1,\dots\}$, $\NN^+=\{1,2,\dots,\}$, and $[n]=\{1,2,\dots,n\}$ for $n\in\NN$.
Write $\ZZ_n$ for the cyclic group $\{0,1,\dots,n-1\}$ with addition modulo $n$.

The cardinality of a set $S$ is denoted by $|S|$.
We also use $|c|$ to denote the absolute value of a number $c\in\CC$.
Denote by $\log x$ the base 2 logarithm of $x$, and by $\ln x$ the natural logarithm of $x$.
For sets $A$ and $B$, denote by $A\setminus B$ the set difference $\{x\in A: x\not\in B\}$.
The restriction of a map $f: A\to B$ to a subset $A'\subseteq A$ is denoted by $f|_{A'}$, which is a map from $A'$ to $B$.

A formal Laurent series over a field $\FF$ has the form

\[
h(T)=c_{i} T^{i}+ c_{i+1} T^{i+1}+\dots
\]

where $i\in \ZZ$ and $c_j\in \FF$ for $j\geq i$.  Denote by $\ord(f)$ the least degree of the terms that appear in $f$, i.e., $f=c_0 T^{\ord(f)}+c_1 T^{\ord(f)+1}+\cdots$ where $c_0\neq 0$. If $f=0$, then let $\ord(f)=+\infty$.
The set of formal Laurent series over $\FF$ is a field, denoted by $\FF((T))$.  We say $f\in\FF((T))$ is a formal power series over $\FF$ if $\ord(f)\geq 0$. The set of formal power series over $\FF$ is a subring of $\FF((T))$, denoted by $\FF[[T]]$.

We write $x\sim D$ if $x$ is sampled from a distribution $D$.
The support of a distribution $D$ over a finite set $\Omega$ is $\supp(D):=\{a\in \Omega: \Pr[D=a]\neq 0\}$.
For an event $A$ that occurs with a nonzero probability under a distribution $D$, write $D|_A$ for the distribution of $D$ conditioned on $A$.
The product distribution of two distributions $D, D'$ is denoted by $D\times D'$.
The statistical distance between two distributions $D, D'$ over a finite set $\Omega$ is defined to be

\[
\Delta(D,D'):=\max_{A\subseteq \Omega} |\Pr[D\in A]-\Pr[D'\in A]|.
\]

Two distributions $D$ and $D'$ are $\epsilon$-close if their statistical distance is at most $\epsilon$, and we write $D=_{\epsilon} D'$ for this statement.

The uniform distribution over a finite set $S$ is denoted by $U_S$.
For $n\in\NN$, denote by $U_n$ the uniform distribution over $\{0,1\}^n$.

The min-entropy of a distribution $D$ over a finite set $\Omega$ is

\[
H_{\mathrm{min}}(D):=-\log(\max_{a\in \Omega}\Pr[D=a]).
\]

We say $D$ is a $k$-source if $H_{\mathrm{min}}(D)\geq k$.

Let $\Omega$ and $B$ be finite sets, and let $\mathcal{D}$ be a class of distributions over $\Omega$.
A function $\Ext: \Omega\to B$ is said to be a (deterministic) $\epsilon$-extractor for $\mathcal{D}$ if $\Ext(D)=_\epsilon U_B$ for all $D\in\mathcal{D}$.
A function $\Ext: \Omega\times\{0,1\}^\ell\to B$ is said to be a seeded $\epsilon$-extractor for $\mathcal{D}$ if $\Ext(D\times U_\ell)=_\epsilon U_B$ for all $D\in\mathcal{D}$, where $\ell\in\NN$ is called the seed length of $\Ext$.

Facts about distributions.

The following lemmas are standard and can be found in, e.g., <cit.>.

Let $f: A\to B$ be a map between finite sets.
Let $D$ and $D'$ be distributions over $A$. If $D=_\epsilon D'$, then $f(D)=_\epsilon f(D')$.

Let $D=(D_1,D_2)$ be a joint distribution over a finite product set $A\times B$.
Suppose $T$ is a subset of $A$ such that $\Pr[D_1\in T]\geq 1-\epsilon_1$ and $D_2|_{D_1=a}=_{\epsilon_2} D_2'$ for some distribution $D_2'$ over $B$ and all $a\in T\cap \supp(D_1)$.
Then $D=_{\epsilon_1+\epsilon_2} D_1\times D_2'$.

§ SOURCES WITH LOW BIAS AND THEIR EXTRACTORS

In this section, we consider several natural extensions of $\varepsilon$-biased sources which are useful for our extractor constructions. We then show how to extract randomness from such sources.

§.§ $(\epsilon,e)$-Biased Sources

Let $A$ be a finite abelian group and let $\widehat{A}$ denote the dual group of $A$, that is, the group of characters over $A$. A distribution $D$ over $A$ is $\epsilon$-biased if $|\Ex[\chi(D)]|\leq \epsilon$ for all nontrivial characters $\chi\in\widehat{A}$. This is a standard definition, introduced in [42], which has been immensely useful in the construction of extractors and in the theory of pseudorandomness in general.

We now introduce two natural generalizations. We say $D$ is $(\epsilon,e)$-biased if $|\Ex[\chi(D)]|\leq \epsilon$ for all but at most $e$ characters $\chi\in\widehat{A}$.
And we say $D$ is strongly $(\epsilon,e)$-biased if the set of $\chi\in\widehat{A}$ satisfying $|\Ex[\chi(D)]|> \epsilon$ is contained in an abelian subgroup of $A$ of size at most $e$. The usefulness of the latter definition will be clear shortly.

Note that if $A$ is a vector space over a finite field of characteristic $p$, then an $(\epsilon,e)$-biased distribution is also strongly $(\epsilon,p^e)$-biased.

We have the following easy observation, which shows that strongly $(\epsilon,e)$-biased sources generalize affine sources (of low codimension).

An affine source of codimension at most $k$ in $\FF_p^n$ is strongly $(0, p^k)$-biased.

The following proposition states that $(\epsilon, e)$-biased sources are (close to) distributions with high min-entropy.

Let $D$ be an $(\epsilon,e)$-biased distribution over $A$. Then $D$ is $\epsilon'$-close to a $k$-source if $\epsilon'\geq 2^k(\epsilon^2 + |A|^{-1}e)$.
In particular, this holds for  $k=\min\{2\log(1/\epsilon), \log |A|-\log e\}-\log (2/\epsilon')$.

View $D$ as a function $D: A\to \RR$ such that $D(x)=\Pr[D=x]$ for $x\in A$.
For $\chi\in\widehat{A}$, we have $\widehat{D}(\chi)=\Ex_{x\in A}[D(x)\overline{\chi(x)}]=|A|^{-1}\left(\sum_{x\in A}  \Pr[D=x] \cdot \overline{\chi(x)}\right)=|A|^{-1}\overline{\Ex[\chi(D)]}$.
So $|\widehat{D}(\chi)|\leq |A|^{-1}$ for all $\chi\in\widehat{A}$, and $|\widehat{D}(\chi)|\leq |A|^{-1}\epsilon$ for all but at most $e$ characters $\chi\in\widehat{A}$.
By Parseval's identity,

\[
\sum_{x\in A} |D(x)|^2=
|A|\cdot\left(\Ex_{x\in A} \left[|D(x)|^2\right]\right)=|A|\cdot\left(\sum_{\chi\in\widehat{A}} |\widehat{D}(\chi)|^2\right)\leq \epsilon^2 + |A|^{-1}e.
\]

Let $A' \subseteq A$ be the set of $x\in A$ such that $D(x)>2^{-k}$.

\[
\epsilon^2 + |A|^{-1}e\geq \sum_{x\in A} |D(x)|^2\geq \sum_{x\in A'} |D(x)|^2\geq \left(\sum_{x\in A'} D(x) \right)2^{-k}.
\]

So the total probability mass contributed by $x\in A'$ is bounded by $\epsilon'=2^k(\epsilon^2 + |A|^{-1}e)$.
This implies that $D$ is $\epsilon'$-close to a $k$-source.

Next, suppose that $A$ and $B$ are finite groups. We wish to bound the bias of conditional distributions over $A$ (or $B$), assuming bounds on the bias of a distribution over $A \times B$. We begin with the following technical calculation.

Let $A$ and $B$ be finite abelian groups. Identifying $\widehat{A}\times\widehat{B}$ with $\widehat{A\times B}$ so that $(\chi, \theta)(x,y)=\chi(x)\theta(y)$ for $(x,y)\in A\times B$ and $(\chi,\theta)\in \widehat{A}\times\widehat{B}$.
Let $D=(D_1,D_2)$ be a joint distribution over $A\times B$.
For $x\in \supp(D_1)$ and $\theta\in\widehat{B}$, we have

\[
\Ex[\theta(D_2|_{D_1=x})]
=\sum_{\chi\in \widehat{A}}\Pr[D_1=x]^{-1}\cdot |A|^{-1}\cdot \overline{\chi(x)}\cdot \Ex[(\chi, \theta)(D)].
\]

Define $\delta_x: A\to \{0,1\}$ to be the indicator function such that $\delta_x(z)=1$ if and only if $z=x$.

\begin{align*}
\Ex[\theta(D_2|_{D_1=x})]
&=\Pr[D_1=x]^{-1}\cdot \Ex[\delta_x(D_1)\theta(D_2)]\\
&=\Pr[D_1=x]^{-1}\cdot \Ex\left[\left(\sum_{\chi\in\widehat{A}}\widehat{\delta_x}(\chi)\chi(D_1)\right)\theta(D_2)\right]\\
&=\sum_{\chi\in\widehat{A}} \Pr[D_1=x]^{-1} \cdot \widehat{\delta_x}(\chi)\cdot \Ex[\chi(D_1)\theta(D_2)]\\
&=\sum_{\chi\in \widehat{A}}\Pr[D_1=x]^{-1}\cdot |A|^{-1}\cdot \overline{\chi(x)}\cdot \Ex[(\chi, \theta)(D)]
\end{align*}

where the last equality uses the fact $\widehat{\delta_x}(\chi)=\Ex_{z\in A}[\delta_x(z)\overline{\chi(z)}]=|A|^{-1}\cdot \overline{\chi(x)}$.

As a corollary, we bound the bias of the marginal distribution $D_2$ conditioned on any value of $D_1$.

Use the notations in Lemma <ref>.
Let $\epsilon, \epsilon'>0$.
Assume that every character $\chi\in\widehat{A\times B}\cong \widehat{A}\times\widehat{B}$ satisfying $\Ex[\chi(D)]>\epsilon$ is contained in the subgroup $\widehat{A}\times\{1\}$.
Then with probability at least $1-\epsilon'$ over $x\sim D_1$, the conditional distribution $D_2|_{D_1=x}$ is $|A|\epsilon /\epsilon'$-biased.

Let $T$ be the set of $x\in A$ satisfying $\Pr[D_1=x]\leq |A|^{-1}\epsilon'$.
Then $\Pr[D_1\in T]=\sum_{x\in T}\Pr[D_1=x]\leq \epsilon'$.
So it suffices to show that $|\Ex[\theta(D_2|_{D_1=x})]|\leq |A|\epsilon /\epsilon'$ holds  for every $x\in A\setminus T$ and every nontrivial character $\theta$ of $B$.

Consider $x\in A\setminus T$ and a nontrivial character $\theta$ of $B$. As $x\not\in T$, we have $\Pr[D_1=x]> |A|^{-1}\epsilon'$.
By Lemma <ref>,

\begin{align*}
|\Ex[\theta(D_2|_{D_1=x})]|&=\left|\sum_{\chi\in \widehat{A}}\Pr[D_1=x]^{-1}\cdot |A|^{-1}\cdot \overline{\chi(x)}\cdot \Ex[(\chi, \theta)(D)]\right|\\
&\leq \left|\sum_{\chi\in \widehat{A}}\overline{\chi(x)}\cdot \Ex[(\chi, \theta)(D)]\right| / \epsilon'\\
&\leq \sum_{\chi\in \widehat{A}} |\Ex[(\chi, \theta)(D)]|/\epsilon'.
\end{align*}

Note that for $\chi\in\widehat{A}$, $(\chi,\theta)$ is not in the subgroup $\widehat{A}\times\{1\}$ since $\theta\in\widehat{B}$ is nontrivial.
So $|\Ex[(\chi, \theta)(D)]|\leq \epsilon$ by assumption.
It follows that $|\Ex[\theta(D_2|_{D_1=x})]|\leq |A|\epsilon /\epsilon'$, as desired.

§.§ Extraction via the XOR Lemma and Rank-Metric Codes

We need the following form of Vazirani's XOR lemma, taken from [45].

Every $\epsilon$-biased distribution over a finite abelian group $A$ is $\epsilon |A|^{1/2}$-close to the uniform distribution over $A$.

Large characteristic.
Over fields of large characteristic, we use the mod-$M$ function in our constructions as an extractor for low-bias distributions, in a similar manner to [12] and [15]. We follow the treatment in [45].

For a finite abelian group $A$ and a function $h : A \to \mathbb{C}$, define $\Lone{h} = \sum_{x \in A} |h(x)|$ and $\Linf{h} = \max_{x \in A} |h(x)|$.

Let $A$ and $B$ be finite abelian groups. Let $D$ be an $\epsilon$-biased distribution over $A$.
Suppose $f: A \to B$ is a map such that for every character $\psi$ of $B$, we have that
$\Lone{\widehat{\psi\circ f}}\leq\tau$.
Then $f(D)$ is $\epsilon'$-close to $f(U_A)$, where $\epsilon'=\tau\epsilon |B|^{1/2}$.

Let $f: \ZZ_N\to \ZZ_M$ be the map sending $a\bmod N$ to $a\bmod M$ for $a\in\{0,1,\dots,N-1\}$. Let $\psi$ be a character of $\ZZ_M$. Then $\Lone{\widehat{\psi\circ f}}\leq c\log N$, where $c$ is an absolute constant.

When $p$ is large but $\FF_q$ is possibly non-prime, we  simply apply the mod-$M$ function to the last $\FF_p$-coordinate of $\FF_q$ and use the following corollary of Lemma <ref>.

Let $f: \ZZ_N^t\to \ZZ_N^{t-1}\times \ZZ_M$ be the map that sends $(a_1,\dots,a_{t-1},a\bmod N)$ to $(a_1,\dots,a_{t-1},a\bmod M)$ for $(a_1,\dots,a_{t-1},a)\in \ZZ_N^{t-1} \times \{0,1,\dots,N-1\}$. Let $\psi$ be a character of $\ZZ_N^{t-1}\times \ZZ_M$. Then $\Lone{\widehat{\psi\circ f}}\leq c\log N$, where $c$ is an absolute constant.

Combining Lemma <ref> and Corollary <ref> gives the following lemma, which allows us to extract randomness from $\epsilon$-biased sources over $\FF_q$.

Let $f: \ZZ_N^t\to \ZZ_N^{t-1}\times \ZZ_M$ be the map in Corollary <ref>.
Then for every $\epsilon$-biased distribution $D$ over $\ZZ_N^t$, $f(D)$ is $\epsilon'$-close to the uniform distribution over $\ZZ_N^{t-1}\times \ZZ_M$, where $\epsilon'=\epsilon\cdot (N^{t-1}M)^{1/2}\cdot c\log N+M/N$ and $c$ is an absolute constant.

By Lemma <ref> and Corollary <ref>, $f(D)$ is $\epsilon\cdot (N^{t-1}M)^{1/2}\cdot c\log N$-close to $f(U)$.
For each $b\in \ZZ_M$, the number of $a\in\{0,1,\dots, N-1\}$ satisfying $a\bmod M=b$ is either $\lfloor N/M\rfloor$ or $\lceil N/M\rceil$, and its difference from $N/M$ is bounded by one. So $f(U)$ is $M/N$-close to the uniform distribution over $\ZZ_N^{t-1}\times \ZZ_M$, and the lemma follows.

Small characteristic.
The XOR lemma requires the distribution to be $\epsilon$-biased.
However, when the characteristic is small, we need to deal with the more general class of $(\epsilon, e)$-biased distributions, where $e$ is small.
The following lemma states that we can extract randomness from such sources using a function $f$, provided that the $L_1$ and $L_\infty$ norms of the Fourier transforms of certain functions $\psi\circ f$ are reasonably bounded.

Let $A$ and $B$ be finite abelian groups.
Let $D$ be an $(\epsilon,e)$-biased distribution over $A$.
Let $f: A\to B$ be a map such that for every nontrivial character $\psi\in \widehat{B}$, $\Lone{\psi\circ f} \le a_1$ and $\Linf{\psi \circ f} \le a_{\infty}$.
Then $f(D)$ is $\epsilon'$-close to the uniform distribution over $B$, where $\epsilon'=(a_1\epsilon+a_\infty e)|B|^{1/2}$.

Let $\psi$ be a nontrivial character of $B$.
By the XOR lemma, we just need to prove that

\[
|\Ex[\psi(f(D))]|\leq a_1\epsilon+a_\infty e.
\]

Let $E$ be the set of $\chi\in\widehat{A}$ such that $|\Ex[\chi(D)]|>\epsilon$.
Then $|E|\leq e$.
Writing $\psi\circ f=\sum_{\chi\in \widehat{B}} \widehat{\psi\circ f}(\chi)\cdot \chi$, we have

\begin{align*}
|\Ex[\psi(f(D))]|&=|\Ex[(\psi\circ f)(D)]|\\
&\leq \sum_{\chi\in \widehat{A}} |\widehat{\psi\circ f}(\chi)|  \cdot |\Ex[ \chi(D))]|\\
&=\sum_{\chi\in \widehat{A}\setminus E} |\widehat{\psi\circ f}(\chi)|  \cdot |\Ex[ \chi(D))]|
+\sum_{\chi\in E} |\widehat{\psi\circ f}(\chi)|  \cdot |\Ex[ \chi(D))]|\\
&\leq \left(\sum_{\chi\in \widehat{A}\setminus E} |\widehat{\psi\circ f}(\chi)|\right) \cdot \epsilon
+ |E|\cdot \max_{\chi\in E} |\widehat{\psi\circ f}(\chi)| \\
&\leq a_1\epsilon+a_\infty e
\end{align*}

as desired.

We turn to constructing functions $f$ with the properties required by Lemma <ref>.
As a warm-up, we first give a construction based on the inner product function and error-correcting codes. Later, we give an improved construction based on rank-metric codes.

Construction of $f$ based on the inner product function and error-correcting codes.
We construct $f$ by adapting the inner product function $IP(x_1,\dots,x_{2r})=\sum_{i=1}^r x_{2i-1}x_{2i}$.
Suppose $r, n>0$ are integers such that $2r\leq n$.
Let $\pi:\FF_p^n\to\FF_p^{2r}$ be a projection over $\FF_p$.
Let $C\subseteq \FF_p^r$ be a linear code over $\FF_p$ of dimension $t$ and relative distance $\delta$ with a generating matrix $G=(c_{i,j})\in \FF_p^{t\times r}$ (i.e., $C$ is the row space of $G$).
For $i\in [t]$, define $f_i: \FF_p^n\to \FF_p$ by

\[
f_i(x)=\sum_{j=1}^r c_{i,j} y_{2j-1} y_{2j}, ~\text{where}~ (y_1,\dots,y_{2r})=\pi(x)\in\FF_p^{2r}.
\]

Let $f=(f_1,\dots,f_t):\FF_p^n\to \FF_p^t$.

Let $f$ be as above.
For every nontrivial character $\psi\in \widehat{\FF_p^t}$, we have $\Lone{\widehat{\psi\circ f}}\leq p^r$ and $\Linf{\widehat{\psi\circ f}}\leq p^{-\delta r}$.

Note that $\psi\circ f$ may be viewed as a function in $\pi(x)\in\FF_p^{2r}$ and hence can be written as a linear combination of the characters of $\FF_p^{2r}$.
On the other hand, the projection $\pi:\FF_p^n\to\FF_p^{2r}$ induces an injective group homomorphism $\iota:\widehat{\FF_p^{2r}}\hookrightarrow\widehat{\FF_p^n}$ via $\chi\mapsto \chi\circ\pi$.
This means the support of $\widehat{\psi\circ f}$ is contained in the subgroup $\iota(\widehat{\FF_p^{2r}})\subseteq\widehat{\FF_p^n}$ of size $p^{2r}$.
By the Cauchy–Schwarz inequality,

\[
\Lone{\widehat{\psi\circ f}}=\sum_{\chi\in\iota(\widehat{\FF_p^{2r}})} |\widehat{\psi\circ f}(\chi)|
\leq \left(\sum_{\chi\in\iota(\widehat{\FF_p^{2r}})} |\widehat{\psi\circ f}(\chi)|^2\right)^{1/2}\cdot p^r=\Ltwo{\widehat{\psi\circ f}}\cdot p^r=p^r.
\]

where the last equality uses the fact that $\psi\circ f$ takes values in the unit circle and hence $\Ltwo{\widehat{\psi\circ f}}=1$ by Parseval's identity.

We now prove the second claim, i.e., $|\widehat{\psi\circ f}(\chi)|\leq p^{-\delta r}$ for $\chi\in \widehat{\FF_p^n}$.
We may also assume $\chi\in \iota(\widehat{\FF_p^{2r}})$ since the support of $\widehat{\psi\circ f}$ is contained in $\iota(\widehat{\FF_p^{2r}})$.

Fix a nontrivial character $\sigma$ of $\FF_p$.
Then $\psi(x_1,\dots,x_t)=\sigma(\sum_{i=1}^t u_i x_i)$ for some nonzero vector $u=(u_1,\dots,u_t)\in\FF_p^t$.
Let $(v_1,\dots,v_r)=u G$, which is a nonzero codeword in $C$.
Note that by definition,

\[
(\psi\circ f)(x)=\sigma\left(\sum_{i=1}^t u_i f_i(x)\right)=\sigma\left(\sum_{i=1}^r v_i y_{2i-1} y_{2i}\right), ~\text{where}~ (y_1,\dots,y_{2r})=\pi(x)\in\FF_p^{2r}.
\]

As $\chi\in \iota(\widehat{\FF_p^{2r}})$,
we have $\chi(x)=\sigma(\sum_{i=1}^{2r} w_i y_i)$ for some $(w_1,\dots,w_{2r})\in\FF_p^{2r}$, where $(y_1,\dots,y_{2r})=\pi(x)$.

\begin{align*}
|\widehat{\psi\circ f}(\chi)|&=
\left|\Ex_{x\in\FF_p^n}\left[(\psi\circ f)(x)\overline{\chi(x)}\right]\right|\\
&=\left|\Ex_{(y_1,\dots,y_{2r})\in\FF_p^{2r}}\left[\sigma\left(\sum_{i=1}^r v_i y_{2i-1} y_{2i}\right)\cdot\overline{\sigma\left(\sum_{i=1}^{2r} w_i y_i\right)}\right]\right|\\
&=\left|\Ex_{(y_1,\dots,y_{2r})\in\FF_p^{2r}}\left[\sigma\left(\sum_{i=1}^r (v_i y_{2i-1} y_{2i}-w_{2i-1} y_{2i-1} - w_{2i} y_{2i})\right)\right]\right|\\
&=\prod_{i=1}^r \left|\Ex_{y,y'\in\FF_p}\left[\sigma\left(P_i(y,y')\right)\right]\right|
\end{align*}

where $P_i(y,y'):=v_i y y'-w_{2i-1} y - w_{2i} y'=(v_iy-w_{2i})y'-w_{2i-1}y$.
Note that $\left|\Ex_{y,y'\in\FF_p}\left[\sigma\left(P_i(y,y')\right)\right]\right|\leq 1/p$ whenever $v_i\neq 0$. (This holds since $\Ex_{y'\in\FF_p}\left[\sigma\left(P_i(y,y')\right)\right]$ is zero when $v_i\neq 0$ and $y$ is assigned a value in $\FF_p$ different from $w_{2i}/v_i$, in which case $P_i(y,y')$ is a degree-$1$ polynomial in $y'$.)
As $C$ is a linear code of relative distance $\delta$, there are at least $\delta r$ indices $i\in [r]$ for which $v_i\neq 0$. It follows that $|\widehat{\psi\circ f}(\chi)|\leq p^{-\delta r}$.

By choosing $C\subseteq\FF_p^r$ to be an explicit asymptotically good linear code over $\FF_p$ (e.g., an expander code), we obtain the following result.

There exist absolute constants $c, c'>0$ such that the following holds.
For integers $r,n>0$ such that $2r\leq n$, there exists an explicit function $\FF_p^n\to\FF_p^t$, where $t\geq c r$, such that $\Lone{\widehat{\psi\circ f}}\leq p^{r}$
$L_\infty(\widehat{\psi\circ f})\leq p^{-c' r}$
for every nontrivial character $\psi\in\widehat{\FF_p^t}$.

Construction of $f$ based on rank-metric codes.

The bilinear maps used in the above construction may be viewed as diagonal matrices with many nonzeros on the diagonal.
We observe that the analysis only requires the matrices to have a high rank, and they do not have to be diagonal or even square matrices.
This leads to the following improved construction of $f$ based on rank-metric codes, which are subspaces of matrices such that every non-zero matrix in the subspace has a high rank.
Here we use an optimal construction of rank-metric codes called Gabidulin codes.

Let $k\leq r\leq s$ be positive integers.
Fix $g_1,\dots,g_r\in \FF_{p^s}$ that are linearly independent over $\FF_p$.
Also fix $\tau:\FF_{p^s}\to \FF_p^s$ that is an isomorphism of vector spaces over $\FF_p$.
For $u=(u_1,\dots,u_k)\in \FF_{p^s}^k$, let $f_u:=\sum_{i=1}^k u_i X^{p^{i-1}}\in\FF_{p^s}[X]$ and $M_u:=(\tau(f_u(g_1)),\dots, \tau(f_u(g_r)))\in\FF_{p}^{s\times r}$, where each $\tau(f_u(g_i))\in\FF_p^s$ is viewed as a column vector.

For any nonzero $u\in \FF_{p^s}^k$, the matrix $M_u$ has rank at least $r-k+1$.

Let $Z\subseteq\FF_{p^s}$ be the set of roots of $f_u$ in $\FF_{p^s}$. We have $|Z|\leq \deg(f_u)\leq p^{k-1}$.
Note that for a column vector $y=(y_1,\dots,y_r)\in\FF_p^r$, we have $M_u y=\sum_{i=1}^r y_i \tau(f_u(g_i))=\tau(f_u(\sum_{i=1}^r y_i g_i))$ since $\tau$ is $\FF_p$-linear and $f_u$ is a linearized polynomial.
So $M_u y=0$ iff $\sum_{i=1}^r y_i g_i\in Z$. As $g_1,\dots,g_r$ are linearly independent over $\FF_p$, the map $y\mapsto \sum_{i=1}^r y_i g_i$ is injective. So there are at most $|Z|\leq p^{k-1}$ choices of $y$ such that $M_u y=0$. We conclude that the right kernel of $M_u$ has size at most $p^{k-1}$ and hence has dimension at most $k-1$. In other words, the rank of $M_u$ is at least $r-k+1$.

The map $u\mapsto M_u$ is an $\FF_p$-linear injective map by Lemma <ref>.
So  $\{M_u: u\in \FF_{p^s}^k\}$ is a linear space of dimension $ks$ over $\FF_p$, and any nonzero matrix in this space has rank at least $r-k+1$ by Lemma <ref>. We record this in the following corollary.

Let $k\leq r\leq s$ be positive integers.
Let $t\leq ks$.
There exist explicit matrices $M_1,\dots,M_t\in\FF_p^{s\times r}$ such that for any nonzero $c=(c_1,\dots,c_t)\in\FF_p^t$, the matrix $\sum_{i=1}^t c_i M_i$ has rank at least $r-k+1$.

Suppose $r,n>0$ are integers such that $2r\leq n$. Let $s=n-r\geq r$.
Let $k\in [r]$ and $t\in [ks]$. And let $M_1,\dots,M_t$ be as in Corollary <ref>.
Identify $\FF_p^n$ with $\FF_p^s\times\FF_p^r$.
Then for $i\in [t]$, define $f_i: \FF_p^n\cong \FF_p^s\times\FF_p^r\to \FF_p$ to be the $\FF_p$-bilinear map sending $(x,y)\in\FF_p^s\times\FF_p^r$ to $x^T M_i y$, where $x$ and $y$ are viewed as column vectors.
Finally, let $f=(f_1,\dots,f_t):\FF_p^n\to \FF_p^t$.

Let $f$ be as above.
For every nontrivial character $\psi\in \widehat{\FF_p^t}$, we have $\Lone{\widehat{\psi\circ f}}\leq p^r$ and $\Linf{\widehat{\psi\circ f}}\leq p^{-(r-k+1)}$.

Fix a nontrivial character $\sigma$ of $\FF_p$.
Identify $\FF_p^n$ with $\FF_p^s\times\FF_p^r$.
Then $\psi\circ f$ has the form $(x,y)\mapsto \sigma(x^T M y)$ where $M\in\FF^{s\times r}$ is a nontrivial linear combination of the matrices $M_1,\dots,M_t$. Let $R$ be the rank of $M$. Then $r-k+1\leq R\leq \min\{s,r\}=r$ by Corollary <ref>.

Let $U, V\subseteq\FF_p^s$ such that $U$ is the left kernel of $M$ and $V$ is a complement of $U$.
We have $\codim_{\FF_p} U=\dim_{\FF_p} V=R$.
Identify $\FF_p^s$ with $U\times V$.
Identify $\widehat{\FF_p^n}$ with $\widehat{U}\times \widehat{V}\times\widehat{\FF_p^r}$ so that $(\chi_1,\chi_2,\chi_3)$ sends $(u,v,y)\in U\times V\times\FF_p^r\cong \FF_p^n$ to $\chi_1(u)\chi_2(v)\chi_3(y)$.
Consider $\chi=(\chi_1,\chi_2,\chi_3)\in \widehat{\FF_p^n}$.
We have

\begin{equation}\label{eq:fourier_coeff}
\begin{aligned}
\widehat{\psi\circ f}(\chi)
&=\Ex_{x\in\FF_p^n}\left[(\psi\circ f)(x)\overline{\chi(x)}\right]\\
&=\Ex_{(u,v,y)\in U\times V\times\FF_p^r}\left[\sigma((u+v)^TMy)\overline{\chi_1(u)\chi_2(v)\chi_3(y)}\right]\\
&=\Ex_{(u,v,y)\in U\times V\times\FF_p^r}\left[\sigma(v^TMy)\overline{\chi_1(u)\chi_2(v)\chi_3(y)}\right]\\
&=\Ex_{(v,y)\in  V\times\FF_p^r}\left[\sigma(v^TMy)\overline{\chi_2(v)\chi_3(y)}\right]\Ex_{u\in U}\left[\overline{\chi_1(u)}\right]
\end{aligned}
\end{equation}

Note $\Ex_{u\in U}\left[\overline{\chi_1(u)}\right]=0$ whenever $\chi_1\neq 1$. So the support of $\widehat{\psi\circ f}$ is contained in the subgroup $\{1\}\times \widehat{V}\times\widehat{\FF_p^r}$ of size $p^{R+r}\leq p^{2r}$. Also note that $\psi\circ f$ takes values in the unit circle of $\CC$ and hence $\sum_{\chi\in\widehat{\FF_p^n}} |\widehat{\psi\circ f}(\chi)|^2=\Ex_{x\in\FF_p^n}\left[(\psi\circ f)(x)^2\right] =1$ by Parseval's identity.
Then by the Cauchy–Schwarz inequality,

\[
\Lone{\widehat{\psi\circ f}}=\sum_{\chi\in\{1\}\times \widehat{V}\times\widehat{\FF_p^r}} |\widehat{\psi\circ f}(\chi)|
\leq \left(\sum_{\chi\in\widehat{\FF_p^n}} |\widehat{\psi\circ f}(\chi)|^2\right)^{1/2}\cdot p^r=p^r.
\]

This proves the first claim.

We now prove the second claim, i.e., $|\widehat{\psi\circ f}(\chi)|\leq p^{-(r-k+1)}$ for $\chi\in \widehat{\FF_p^n}$.
We may assume $\chi=(\chi_1,\chi_2,\chi_3)\in \{1\}\times \widehat{V}\times\widehat{\FF_p^r}$ since otherwise $\widehat{\psi\circ f}(\chi)=0$.
Choose $w\in V$ such that $\chi_2$ sends $v\in V$ to $\sigma(v^T w)$.

\begin{align*}
|\widehat{\psi\circ f}(\chi)|
&=\left|\Ex_{(v,y)\in  V\times\FF_p^r}\left[\sigma(v^TMy)\overline{\chi_2(v)\chi_3(y)}\right]\right|\\
&=\left|\Ex_{(v,y)\in  V\times\FF_p^r}\left[\sigma(v^T(My-w))\overline{\chi_3(y)}\right]\right|\\
&=\left|\Ex_{y\in \FF_p^r}\left[\Ex_{v\in V}\left[\sigma(v^T(My-w))\right]\cdot \overline{\chi_3(y)} \right]\right|\\
&\leq \Pr_{y\in\FF_p^r}[My=w].
\end{align*}

The first equality holds by (<ref>) and the assumption $\chi_1=1$. The last inequality above holds since $\Ex_{v\in V}\left[\sigma(v^T(My-w))\right]=0$ when $My\neq w$.
Finally, note $\Pr_{y\in\FF_p^r}[My=w]$ is either zero or $p^{-R}$, depending on whether $My=w$ has a solution. In either case, we have $|\widehat{\psi\circ f}(\chi)|\leq p^{-R}\leq p^{-(r-k+1)}$.

Assuming that $n$ is sufficiently large and $\epsilon$ is not too much larger than $p^{-n/2}$, the construction above gives explicit deterministic extractors that extract a constant fraction of min-entropy from $(\epsilon,e)$-biased sources over $\FF_p^n$, as stated by the following theorem.

$n,t,e\in\NN^+$ and $d,\epsilon'>0$ such that $n\geq c$ and $t\log p\leq c^{-1}n\log p-2 \log(de/\epsilon')$, where $c>0$ is a large enough absolute constant. Let $\epsilon=dp^{-n/2}$.
Then there exists an explicit deterministic $\epsilon'$-extractor $f: \FF_p^n\to \FF_p^t$ for $(\epsilon, e)$-biased sources distributed over $\FF_p^n$.

Choose $r=n/4$, $s=n-r$, and
(For ease of readability, we omit floor and ceiling functions.)
Note $t\leq ks$ assuming $c$ is large enough.
Let $f:\FF_p^n\to \FF_p^t$ be as in Construction <ref>.
Then $\Lone{\widehat{\psi\circ f}}\leq p^r$ and $\Linf{\widehat{\psi\circ f}}\leq p^{-r/2}$ by Lemma <ref>.
By Lemma <ref>, for any $(\epsilon, e)$-biased distribution $D$ over $\FF_p^n$, $f(D)$ is $\epsilon''$-close to the uniform distribution over $\FF_p^t$, where $\epsilon''=(p^r d p^{-n/2}+p^{-r/2}e)\cdot p^{t/2}$.
As $c$ is large enough, the conditions in the theorem imply $p^r d p^{-n/2}\cdot p^{t/2}\leq \epsilon'/2$ and $p^{-r/2}e\cdot p^{t/2}\leq \epsilon'/2$. So $\epsilon''\leq \epsilon'$ and hence $f(D)$ is $\epsilon'$-close to the uniform distribution.

We also obtain an explicit construction of deterministic extractors that extract most min-entropy from very dense affine sources, and more generally, $(0,e)$-biased sources. It is interesting to compare and constant the theorem below with our construction in Section <ref>, which requires a large field size but works for arbitrary min-entropy, and is also based on very different ideas.

Let $n,t,e\in\NN^+$ and $\epsilon\in (0,1)$ such that $t\leq n-3-2\log_p(e/\epsilon)$.
Then there exists an explicit deterministic $\epsilon$-extractor $f: \FF_p^n\to\FF_p^t$ for $(0, e)$-biased sources, and in particular, for affine sources of codimension at most $\log_p e$.

Note that $n\geq t+3\geq 4$.
Choose $r=\lfloor n/2\rfloor\geq (n-1)/2$, $s=n-r$, and
$k=2\leq r$.
Note $t\leq ks$ since $t\leq n$ and $s\geq n/2$.
Let $f:\FF_p^n\to \FF_p^t$ be as in Construction <ref>.
Then $\Linf{\widehat{\psi\circ f}}\leq p^{-(r-k+1)}$ by Lemma <ref>.
By Lemma <ref>, for any $(0, e)$-biased distribution $D$ over $\FF_p^n$, $f(D)$ is $\epsilon'$-close to the uniform distribution over $\FF_p^t$, where $\epsilon'=p^{-(r-k+1)}\cdot e\cdot p^{t/2}$.
Finally, note that $\epsilon'\leq \epsilon$ by the choice of $t$.

Extracting most min-entropy from strongly $(\epsilon,e)$-biased sources.

We now construct deterministic extractors that extract most min-entropy from strongly $(\epsilon,e)$-biased sources.

The following lemma allows us to reduce to the case of affine sources.

Let $\pi: \FF_p^n\to \FF_p^m$ be a surjective $\FF_p$-linear map.
Let $D$ be a strongly $(\epsilon, e)$-biased distribution over $\FF_p^n$. Then $\pi(D)$ is $\epsilon'$-close to a convex combination of affine sources of codimension at most $\log_p e$ in $\FF_p^m$, where $\epsilon'=2(p^{m/2}\cdot e\cdot \epsilon)^{1/2}$.

Let $A$ be a subspace of $\FF_p^n$ of size at most $e$ and $B$ be a complement of $A$ such that by identifying $\FF_p^n$ with $A\times B$ and $\widehat{\FF_p^n}$ with $\widehat{A}\times\widehat{B}$, every nontrivial character $\chi$ of $\widehat{\FF_p^n}$ satisfying $|\Ex[\chi(D)]|>\epsilon$ is in the subgroup $\widehat{A}\times\{1\}$.
This is possible as $D$ is strongly $(\epsilon,e)$-biased.
Identify $A$ and $B$ with the subgroups $A\times\{0\}$ and $\{0\}\times B$ of $A\times B$ respectively.
Then the codimension of $B$ in $\FF_p^n$ is at most $\log_p e$.
Let $D_1$ and $D_2$ be the marginal distributions of $D$ over $A$ and $B$ respectively.

Let $\epsilon_0>0$, whose value is determined later.
By Corollary <ref>, for $x$ sampled from $D_1$, with probability at least $1-\epsilon_0$, the conditional distribution $D_2|_{D_1=x}$ is $|A|\epsilon /\epsilon_0$-biased. Fix $x\in\supp(D_1)$ such that $D_2|_{D_1=x}$ is $|A|\epsilon /\epsilon_0$-biased.
We claim that $\pi(D|_{D_1=x})$ is $\epsilon_1$-close to an affine source of codimension at most $\log_p e$, where $\epsilon_1=p^{m/2}|A|\epsilon/\epsilon_0$.
Note that $\pi(D|_{D_1=x})=\pi(x)+\pi(D_2|_{D_1=x})$.
So to prove the claim, we just need to show that $\pi(D_2|_{D_1=x})$ is $\epsilon_1$-close to an affine source of codimension at most $\log_p e$.

Let $H=\pi(B)$.
Then $\pi|_{B}: B\to H$ is a surjective linear map.
So the map $\chi\mapsto \chi\circ \pi$ sends a nontrivial character of $H$ to a nontrivial character of $B$.
As $D_2|_{D_1=x}$ is an $|A|\epsilon/\epsilon_0$-biased distribution over $B$, we see that $\pi(D_2|_{D_1=x})$ is an $|A|\epsilon/\epsilon_0$-biased distribution over $H$.
By the XOR lemma (Lemma <ref>), $\pi(D_2|_{D_1=x})$ is $|H|^{1/2}|A|\epsilon/\epsilon_0$-close to the uniform distribution over $H$.

\begin{align*}
\dim H=\dim B - \dim(B\cap \ker \pi)&\geq \dim B-\dim (\ker \pi)\\
&= \dim B - (n-m)
=m-\codim B.
\end{align*}

So the codimension of $H$ in $\FF_p^m$ is at most $\codim B\leq \log_p e$.
Therefore, the distribution  $\pi(D_2|_{D_1=x})$ is $|H|^{1/2}|A|\epsilon/\epsilon_0$-close to an affine source of codimension at most $\log_p e$. This proves the above claim as $|H|^{1/2}|A|\epsilon/\epsilon_0\leq p^{m/2}|A|\epsilon/\epsilon_0=\epsilon_1$.

We have shown that for $x$ sampled from $D_1$, with probability at least $1-\epsilon_0$, the distribution $D|_{D_1=x}$ is $\epsilon_1$-close to an affine source of codimension at most $\log_p e$.
It follows that $D$ is $(\epsilon_0+\epsilon_1)$-close to a convex combination of affine sources of codimension at most $\log_p e$, where $\epsilon_1=p^{m/2}|A|\epsilon/\epsilon_0$. Finally, choose $\epsilon_0=(p^{m/2}|A|\epsilon)^{1/2}$ so that

\[
\epsilon_0+\epsilon_1=2\epsilon_0=2(p^{m/2}\cdot |A|\cdot \epsilon)^{1/2}\leq 2(p^{m/2}\cdot e\cdot \epsilon)^{1/2}. \qedhere
\]

Let $n,t,e$ be positive integers and $\epsilon, \epsilon'\in (0,1)$.
Let $n'=\min\{\lfloor 2\log_p(1/\epsilon)-2\log_p(16e/\epsilon'^2)\rfloor, n\}$.
Suppose $t\leq n'-3-2\log_p(2e/\epsilon')$.
Then there exists an explicit  $\epsilon'$-extractor $\Ext: \FF_p^n\to\FF_p^t$ for strongly $(\epsilon, e)$-biased sources.

We construct the extractor $\Ext$ as follows.

* Let $\pi: \FF_p^n\to\FF_p^{n'}$ be an explicit linear surjective map.

* Let $f:\FF_p^{n'}\to\FF_p^t$ be an explicit deterministic $\epsilon'/2$-extractor for affine sources of codimension at most $\log_p e$.

* Finally, let $\Ext=f\circ \pi$.

Here the existence of $f$ is guaranteed by Theorem <ref> as $t\leq n'-3-2\log_p(2e/\epsilon')$.
We claim that $\Ext:\FF_p^n\to \FF_p^t$ is a deterministic $\epsilon'$-extractor for strongly $(\epsilon, e)$-biased sources.

Consider an arbitrary strongly $(\epsilon, e)$-biased source $D$.
By the choice of $n'$, we have $2(p^{n'/2}\cdot e\cdot \epsilon)^{1/2}\leq \epsilon'/2$.
So by Lemma <ref>, $\pi(D)$ is $\epsilon'/2$-close to a convex combination of affine sources of codimension at most $\log_p e$.
Then by the affine extractor property of $f$, we know $\pi(D)$ is $\epsilon'$-close to the uniform distribution. This proves the claim.

By Proposition <ref>, an $(\epsilon, e)$-biased source over $\FF_p^n$ is $\epsilon'$-close to a source of min-entropy at least $\min\{2\log(1/\epsilon), n\log p-\log e\}-\log(2/\epsilon')$.
The output bit-length $t\log p$ in Theorem <ref> matches this bound up to an additive term $O(\log e+\log(1/\epsilon')+\log p)$.

As $(\epsilon, e)$-biased sources over $\FF_p^n$ are strongly $(\epsilon, p^e)$-biased, Theorem <ref> also gives deterministic extractors for $(\epsilon, e)$-biased sources at the cost of replacing $e$ with $p^e$ in the theorem statement.
It is interesting to ask for deterministic extractors, explicit or not, that extract most min-entropy from $(\epsilon, e)$-biased sources (up to the lower bound in  Proposition <ref>)  without this exponential blow-up. We note that the extractors in Theorem <ref> could extract a constant fraction of the min-entropy from $(\epsilon, e)$-biased sources assuming that $\epsilon$ is small enough.

§ PRELIMINARIES ON ALGEBRAIC GEOMETRY

In this section, we introduce preliminaries and notations on algebraic geometry. One can also refer to a standard text, e.g., [49, 53].

§.§ Terminology

All rings in this paper are commutative rings with unity. A proper ideal $I$ of a ring $R$ is prime if $ab\in I$ implies $a\in I$ or $b\in I$ for $a,b\in R$.
This is equivalent to the condition that $R/I$ is an integral domain.
An ideal $I$ of  $R$ is radical if $a^m\in I$ implies $a\in I$ for every $a\in R$ and $m\in\NN^+$.

Affine varieties.
Let $\FF$ be a field and let $\overline{\FF}$ be its algebraic closure.
For $n\in\NN$, the affine $n$-space $\AA^n_\FF$  over $\FF$ is
the set $\overline{\FF}^n$ equipped with the Zariski topology, defined as follows. A subset $U\subseteq \AA_\FF^n$ is closed if it is the set of common zeros of a set of polynomials in $\FF[X_1,\dots, X_n]$. And $U\subseteq \AA_\FF^n$ is open if its complement is closed.
A closed subset $V\subseteq \AA^n_\FF$ is said to be an affine variety over $\FF$, and its elements are called points of $V$.[When $\FF$ is not algebraically closed, affine varieties (and affine spaces) are often defined in a different way such that each point of an affine variety is not a single point in $\overline{\FF}^n$, but an orbit consisting of all the conjugates of a point in $\overline{\FF}^n$ under the natural action of the automorphism group of $\overline{\FF}$ over $\FF$. Our definition instead follows that in [15], which suffices for us and is more elementary. One can switch between these two definitions by splitting the orbits into points in $\overline{\FF}^n$ and vice versa. One notable difference between the two definitions is that, in our definition, points are not necessarily closed in the Zariski topology over $\FF$ when the field $\FF$ is not algebraically closed, while they are always closed in the other definition.
We say $V$ is defined by a set $S\subseteq\FF[X_1,\dots, X_n]$ if it is the set of common zeros of the polynomials in $S$.

We often write  $\AA^n$ instead of $\AA^n_\FF$ when $\FF$ is algebraically closed and clear from the context.

A point $a\in \AA^n_\FF$  is said to be a rational point if the coordinates of $a$ are all in $\FF$.
For an affine variety $V$ over $\FF$, denote by $V(\FF)$ the set of rational points in $V$. Each rational point is closed (as a set containing the point itself) in the Zariski topology.

For an affine variety $V\subseteq \AA^n_\FF$ over $\FF$ defined by $S\subseteq\FF[X_1,\dots,X_n]$,
denote by $V_{\overline{\FF}}$ the affine variety $V'\subseteq \AA^n_{\overline{\FF}}$ over $\overline{\FF}$ defined by $S$.

Note that under our definitions, $V_{\overline{\FF}}$ is the same as $V$ as subsets of $\overline{\FF}^n$.

For two affine varieties $V, V'\subseteq \AA^n_\FF$ over a field $\FF$, we say $V$ is an affine subvariety of $V'$ if $V\subseteq V'$.
We say  $V$ is the affine subvariety of $V'$ defined by $S\subseteq\FF[X_1,\dots,X_n]$ if it is the set of common zeros in $V'$ of the polynomials in $S$.

Irreducibility and absolute irreducibility.

An affine variety $V$ over a field $\FF$  is irreducible if it is nonempty and cannot be written
as the union of finitely many proper affine subvarieties over $\FF$. Otherwise, we say $V$ is reducible.
A subvariety $V_0$ of an affine variety $V$ is an irreducible component of $V$ if $V_0$ is irreducible and maximal (with respect to set inclusion) for this property.
Every affine variety can be uniquely represented as the union of finitely many irreducible components.

An affine variety $V$ over $\FF$  is absolutely irreducible  if $V_{\overline{\FF}}$ is irreducible.
By definition, the Zariski topology over $\overline{\FF}$ is finer than that over $\FF$, i.e., if a set is closed over $\FF$, then it is also closed over $\overline{\FF}$. So absolute irreducibility implies irreducibility.

Let $V\subseteq\AA^n_\FF$ be an irreducible variety over $\FF$. The automorphism group $\mathrm{Aut}(\overline{\FF}/\FF)$ of $\overline{\FF}$ over $\FF$ acts naturally on $V_{\overline{\FF}}$ such that $\tau\in \mathrm{Aut}(\overline{\FF}/\FF)$ sends a point $a=(a_1,\dots,a_n)\in V_{\overline{\FF}}$ to $(\tau(a_1),\dots,\tau(a_n))$. Every $\tau\in \mathrm{Aut}(\overline{\FF}/\FF)$ permutes the irreducible components of $V_{\overline{\FF}}$.
When $\FF=\FF_q$, the Frobenius automorphism $\sigma: x\mapsto x^q$ of $\overline{\FF}_q$ over $\FF_q$ generates a cyclic group that acts transitively on the set of irreducible components of $V_{\overline{\FF}}$. In particular, if $V$ is not absolutely irreducible, then $\sigma$ sends each irreducible component of $V_{\overline{\FF}}$ to a different irreducible component.

The ideal-variety correspondence.
For an ideal $I$ of $\FF[X_1,\dots,X_n]$, denote by $V(I)$ the affine subvariety of $\AA^n_\FF$ over $\FF$ defined by $I$.
Define $V(f_1,\dots, f_k)=V(\langle f_1,\dots, f_k\rangle)$ for $f_1,\dots,f_k\in \FF[X_1,\dots,X_n]$.
For an affine variety $V\subseteq \AA^n$ over $\FF$, denote by $I(V)$ the ideal of $\FF[X_1,\dots,X_n]$ consisting of all the polynomials vanishing on $V$. The ideal $I(V)$, and in fact every ideal of $\FF[X_1,\dots, X_n]$, has a finite generating set by Hilbert's Basis Theorem.

The map $V\mapsto I(V)$ is an inclusion-reversing one-to-one correspondence between the affine subvarieties of $\AA^n_\FF$ over $\FF$ and the radical ideals of $\FF[X_1,\dots,X_n]$, with the inverse map $I\mapsto V(I)$.
An affine variety $V$ is irreducible iff $I(V)$ is a prime ideal.

For an affine variety $V\subseteq \AA^n_\FF$ over $\FF$, define

\[
\FF[V]:=\FF[X_1,\dots,X_n]/I(V),
\]

which is called the coordinate ring of $V$.
When $V$ is irreducible, the ideal $I(V)$ is prime and $\FF[V]$ is an integral domain.
In this case, define the  function field of $V$, denoted by $\FF(V)$, to be  the field of fractions of $\FF[V]$.

The dimension of an irreducible affine variety $V$ over a field $\FF$ is defined to be the largest integer $m$ such that there exists a chain of irreducible affine subvarieties $\emptyset\subsetneq V_0\subsetneq V_1\subsetneq\cdots\subsetneq V_m=V$ over $\FF$. More generally, the dimension of a nonempty affine variety $V$, denoted by $\dim V$, is the maximal dimension of its irreducible components. We have $\dim V=\dim V_{\overline{\FF}}$ for a nonempty affine variety $V$ over $\FF$.

The dimension of an irreducible affine variety $V$ over $\FF$ also equals the transcendence degree of $\FF(V)/\FF$, i.e., the largest cardinality of an algebraically independent subset of $\FF(V)$ over $\FF$.  In particular, $\dim \AA^n_\FF=n$ as its function field $\FF(X_1,\dots,X_n)$ has transcendence degree $n$ over $\FF$.

A nonempty affine variety is equidimensional if its irreducible components have the same dimension. Equidimensional affine varieties of dimension one are also called (affine) curves.

The following fact is a geometric version of Krull's principal ideal theorem. See, e.g., <cit.>.

Let $V\subseteq\AA^n_\FF$ be an irreducible affine variety over a field $\FF$. Let $f\in\FF[X_1,\dots,X_n]$ such that $f$ does not vanish identically on $V$. Then either $V\cap V(f)=\emptyset$ or $V\cap V(f)$ is equidimensional of dimension $\dim V-1$.

Degree. Let $\FF$ be an algebraically closed field. For an irreducible affine variety $V\subseteq \AA^n_\FF$ over $\FF$, the degree of $V$ in $\AA^n_\FF$, denoted by $\deg V$,  is the number of intersections of $V$ with an affine subspace of $\AA^n_\FF$ of codimension $\dim V$ in general position.  Following [27, 25],  for an affine variety $V\subseteq \AA^n_\FF$ over $\FF$ with irreducible components $V_1,\dots, V_k$, we let $\deg V:=\sum_{i=1}^k \deg V_i$.
For an affine variety $V$ over an arbitrary field $\FF$, let $\deg V:=\deg V_{\overline{\FF}}$.

For a nonzero polynomial $f\in \FF[X_1,\dots,X_n]$, we have $\deg (V(f))\leq \deg f $ (and the equality holds if $f$ is squarefree).

The following version of Bézout's inequality is very useful for us.

Let $V, V'\subseteq\AA^n_\FF$ be affine varieties over a field $\FF$. Then

\[
\deg(V\cap V')\leq \deg V\cdot \deg V'.
\]

Morphisms between affine varieties over a field $\FF$.
Let $\FF$ be a field. Let $f_1,\dots,f_m\in\FF[X_1,\dots,X_n]$, which define a map $f: \AA^n_{\FF}\to \AA^m_{\FF}$ sending $a\in \AA^n_{\FF}$ to $f(a)=(f_1(a),\dots,f_m(a))\in  \AA^m_{\FF}$.
Now suppose  $V\subseteq \AA^n_\FF$ and $V'\subseteq \AA^m_\FF$ are affine varieties over $\FF$ such that $f(V)\subseteq V'$. Then the map $f$ restricts to a map $\varphi: V\to V'$.
It is associated with an $\FF$-algebra homomorphism

\[
\varphi^\sharp: \FF[V']=\FF[Y_1,\dots,Y_m]/I(V')\to \FF[V]=\FF[X_1,\dots,X_n]/I(V),
\]

which sends $Y_i+I(V')$ to $f_i(X_1,\dots,X_n)+I(V)$ for $i\in [m]$.
Note that $\varphi^\sharp$ simply sends a function on $V'$ to its composition with $\varphi$, which is a function on $V$.

We say the pair $(\varphi, \varphi^\sharp)$ is a morphism  from $V$ to $V'$ (over $\FF$) and it is defined by $f_1,\dots,f_m$.
For simplicity, we usually suppress $\varphi^\sharp$ and denote the morphism by $\varphi$ when there is no confusion.

A morphism between affine spaces is also called a polynomial map in this paper.
Let $\varphi: \AA^n_\FF\to\AA^m_\FF$ be a polynomial map.
If $V\subseteq \AA^m_\FF$ is an affine variety defined by a set $S$ of polynomials, then $\varphi^{-1}(V)\subseteq \AA^n_\FF$ is the affine variety defined by $\varphi^\sharp(S)$.
So the preimage of a closed (resp. open) set under a polynomial map  is closed (resp. open).

Zariski closure and dominant morphisms.

For a set $S\subseteq \AA^n_\FF$, the (Zariski-)closure of $S$, denoted by $\overline{S}$, is the smallest closed set containing $S$, i.e., the intersection of all affine subvarieties of $\AA^n_\FF$ that contain $S$. We say $S$ is dense in $V$ if $\overline{S}=V$.

Suppose $V\subseteq  \AA^n_\FF$ is an affine variety over $\FF$ and $\varphi: V \to \AA^m_\FF$ is a morphism defined by polynomials $f_1,\dots,f_m\in \FF[X_1,\dots,X_n]$.
The image $\varphi(V)$ is not necessarily a closed set in $\AA^n_\FF$. To understand the closure $\overline{\varphi(V)}$, note that a polynomial $P\in \FF[Y_1,\dots,Y_m]$ vanishes on $\varphi(V)$ (or equivalently, on $\overline{\varphi(V)}$) iff the composition of $P$ with $\varphi$ vanishes on $V$, i.e., $\varphi^\sharp(P)=0$. So the ideal of $\FF[Y_1,\dots,Y_n]$ defining $\overline{\varphi(V)}$ is precisely the kernel of $\varphi^\sharp: \FF[Y_1,\dots,Y_n]\to \FF[V]$.
Let $r_i=X_i+I(V)\in \FF[X_1,\dots,X_n]/I(V)=\FF[V]$ for $i\in [n]$.
Then the coordinate ring $\FF[\overline{\varphi(V)}]=\FF[Y_1,\dots,Y_m]/I\left(\overline{\varphi(V)}\right)$ of $\overline{\varphi(V)}$ may be identified with $\FF[f_1(r_1,\dots,r_n),\dots,f_m(r_1,\dots, r_n)]\subseteq\FF[V]$ via $Y_i+I\left(\overline{\varphi(V)}\right)\mapsto f_i(r_1,\dots,r_n)$.

We say a morphism $\varphi: V\to V'$ between affine varieties is dominant if $\overline{\varphi(V)}=V'$.
If $\varphi: V\to V'$ is a dominant morphism between affine varieties and $V$ is irreducible, then $V'$ is also irreducible.

We also need the following lemma.

Let $V\subseteq\AA^n_\FF$ be an irreducible affine variety over a field $\FF$.
Let $f_1,\dots,f_s,g_1,\dots,g_t\in\FF[X_1,\dots,X_n]$.
The polynomials $f_1,\dots,f_s$ (resp. $f_1,\dots,f_s,g_1,\dots,g_t$) define a polynomial map $\pi_1:\AA^n_\FF\to \AA^{s}_\FF$ (resp. $\pi_2:\AA^n_\FF\to\AA^{s+t}_\FF$).
Then there exist distinct $i_1,\dots,i_k\in [t]$, where $k=\dim \overline{\pi_2(V)}-\dim \overline{\pi_1(V)}$, such that the polynomial map $\pi:\AA^n_\FF\to\AA^{s+k}_\FF$ defined by $f_1,\dots,f_s,g_{i_1},\dots,g_{i_k}$ satisfies $\dim \overline{\pi(V)}=\dim\overline{\pi_2(V)} = \dim\overline{\pi_1(V)} + k$.

Let $r_i=X_i+I(V)\in \FF[X_1,\dots,X_n]/I(V)=\FF[V]$ for $i\in [n]$.
Let $\bar{f}_i=f(r_1,\dots,r_n)$ for $i\in [s]$ and $\bar{g}_i=g(r_1,\dots,r_n)$ for $i\in [t]$.
The function fields of $\overline{\pi_1(V)}$ and $\overline{\pi_2(V)}$ are $\KK_1:=\FF(\bar{f}_1,\dots,\bar{f}_s)$ and $\KK_2:=\FF(\bar{f}_1,\dots,\bar{f}_s,\bar{g}_1,\dots,\bar{g}_t)$ respectively. So $\bar{g}_1,\dots,\bar{g}_t$ is a generating set of $\KK_2/\KK_1$.
The lemma then follows from the fact in field theory that a generating set of a field extension $\KK_2/\KK_1$ always contains a subset that is a transcendence basis of $\KK_2/\KK_1$ (see <cit.>).

Fibers of morphisms.

Let $\varphi: V\to V'$ be a morphism between affine varieties over $\FF$.
For $b\in V'(\FF)$, the preimage $\varphi^{-1}(b)=\{a\in V: \varphi(a)=b\}$ is an affine subvariety of $V$ over $\FF$. We call $\varphi^{-1}(b)$ the fiber of $\varphi$ over $b$, or the fiber of $V$ over $b$ if $\varphi$ is clear from the context.

The following theorem, known as the fiber dimension theorem, relates the dimension of a general fiber of a dominant morphism $\varphi: V\to V'$ between  irreducible affine varieties $V, V'$ to the dimension of $V$ and that of $V'$.

Suppose $\varphi: V\to V'$ is a dominant morphism between irreducible affine
varieties over an algebraically closed field $\FF$.
Then for every $b\in \varphi(V)$ and every irreducible component $Z$ of $\varphi^{-1}(b)$, it holds that

\[
\dim Z\geq \dim V-\dim V'.
\]

Moreover, there exists $U\subseteq \varphi(V)$ such that $U$ is a dense open subset of $V'$ and $\dim \varphi^{-1}(b)=\dim V-\dim V'$ holds for all $b\in U$.

See, e.g., <cit.> for a proof.
We also remark that the above version of the fiber dimension theorem can be generalized in several ways, but this version suffices for us.

Finite morphisms.

We say a morphism $\varphi: V\to V'$ between affine varieties $V$ and $V'$ over $\FF$ is a finite morphism if $\FF[V]$ is finitely generated as a module over its subring $\varphi^\sharp(\FF[V'])$.
The image of a closed set under a finite morphism is closed. In particular, a finite morphism is surjective if it is dominant.
Fibers of finite morphisms are finite sets.

§.§ Further Results

We list some further results in algebraic geometry, which are used in later sections.

Estimates for the number of rational points over $\FF_q$.

We start with the following elementary upper bound on the number of rational points of an affine variety over a finite field $\FF_q$, which can be derived from  Bézout's inequality [27, 9].

Let $V\subseteq\AA^n_{\FF}$ be an affine variety of dimension $k$ and degree $d$ over a field $\FF$. Let $S\subseteq\FF$ be a finite set.
Then $|V\cap S^n|\leq d |S|^{k}$.
In particular, if $\FF=\FF_q$, then $|V(\FF_q)|\leq d q^{k}$.

If $V$ is absolutely irreducible and $q$ is sufficiently large,  one can do better than Lemma <ref> and show that $|V(\FF_q)|$ is close to $q^{\dim V}$ using the Lang–Weil bound. We need the following effective version of this bound.

[Effective Lang–Weil bound]theoremlangweil

Let $V\subseteq\AA^n_{\FF_q}$ be an absolutely irreducible affine variety over $\FF_q$ of dimension $k$ and degree $d$. Then

\[
\]

In particular, we have $|V(\FF_q)|\geq q^k/2$ if $q\geq 20d^5$.

Theorem <ref> was proved by Cafure and Matera as <cit.> with an extra condition that $q > 2(k + 1)d^2$. However, a more careful analysis shows that this condition can be removed. This was confirmed to us in [36].  See Appendix <ref> for more details.
The fact that $q$ does not need to depend on $k$ is crucial to making our required field size independent of $\dim V$, where $V$ is an affine variety that defines an $(n,k,d)$ algebraic source over $\FF_q$.

Bombieri's estimate for exponential sums. We also need Bombieri's estimate for exponential sums over rational points of curves over $\FF_q$.

Let $C\subseteq\AA^n_{\FF_q}$ be an affine curve of degree $d_1$ over a finite field $\FF_q$ of characteristic $p$. Let $\sigma:\FF_p\to\CC^\times$ be the character $x\mapsto e^{2\pi i x/p}$ of $\FF_p$.
Suppose $f\in \FF_q[X_1,\dots,X_n]$ is a polynomial of degree $d_2$ such that for any $g\in \overline{\FF}_q[X_1,\dots,X_n]$ and any irreducible component $C_0$ of $C$, the function $f-(g^p-g)$ does not vanish identically on $C_0$.

\[
\left|\sum_{x\in C(\FF_q)} (\sigma\circ\Tr\circ f)(x)\right|\leq (d_1^2+2d_1 d_2-3d_1)q^{1/2}+d_1^2.
\]

where $\Tr$ denotes the trace map from $\FF_q$ to $\FF_p$.

Noether normalization.

The classical Noether normalization lemma proved by Noether [43] states that an affine variety $V$ of dimension $k$ over an infinite field $\FF$ admits a finite morphism $\varphi: V\to \AA^k_\FF$.
Moreover, $\varphi$ may be chosen to be a linear map.
We give the following quantitative version of this result, which states that the coefficients that specify the linear map can be chosen from a finite subset $S\subseteq\FF$ provided that $S$ is large enough. For simplicity, we assume $\FF$ is algebraically closed, even though the statement can be proved for general $\FF$.

[Noether normalization]lemmafinitelinearmap

Let $V\subseteq \AA^n$ be an affine variety of dimension $k$ and degree $d$ over an algebraically closed field $\FF$.
Suppose $S$ is a finite subset of $\FF$ of size greater than $d$.
Then there exists a polynomial map $\varphi: \AA^n\to\AA^k$ defined by linear polynomials $\ell_i=\sum_{j=1}^n c_{i,j} X_i\in\FF[X_1,\dots,X_n]$ with coefficients $c_{i,1},\dots,c_{i,n}\in S$ for $i=1,\dots,k$
such that $\varphi|_V: V\to \AA^k$ is a finite morphism.

See Appendix <ref> for its proof.

Effective fiber dimension theorem.

We also need an effective version of the fiber dimension theorem. To suit our needs, we first formulate the theorem in the following general form.
Recall that for $h_1,\dots,h_s\in \FF[X_1,\dots,X_n]$, we denote by $\mathcal{L}_{h_1,\dots,h_s, \FF}$ the linear span of $h_1,\dots, h_s$ and $1$ over $\FF$.

[Effective fiber dimension theorem – general form]theoremeffectiveFDTgeneral

Let $V\subseteq \AA^n$ be an irreducible affine variety of dimension $k$ over an algebraically closed field $\FF$, and let $\pi: \AA^n\to\AA^k$ be a polynomial map defined by linear polynomials $\ell_1,\dots,\ell_k\in\FF[X_1,\dots,X_n]$ such that $\pi|_V: V\to \AA^k$ is a finite morphism.
Let $h_1,\dots,h_s\in \FF[X_1,\dots,X_n]$
with $\deg h_1\geq \dots \geq \deg h_s$.
Also let $f_1,\dots,f_m\in \mathcal{L}_{h_1,\dots,h_s,\FF}$, which define a polynomial map $f: \AA^n\to\AA^m$.
Finally, let $W=\overline{f(V)}\subseteq\AA^m$.

Let $t\in\{0,\dots,k-\dim W\}$.
Then there exist distinct $i_1,\dots,i_t\in [k]$ and a polynomial $P\in\FF[X_1,\dots,X_n]$ of degree at most $\dim W\cdot \deg V\cdot  \prod_{i=1}^{\dim W} \deg h_i$ that does not vanish identically on $V$ such that the following holds:
Let $\varphi: \AA^n\to\AA^{t+m}$ be the polynomial map defined by $\ell_{i_1},\dots,\ell_{i_t},f_1,\dots,f_m$.
Then for every $a\in V$ satisfying $P(a)\neq 0$, the fiber $ \varphi|_V^{-1}(\varphi(a))$ is equidimensional of dimension $k-\dim W-t$.

As a corollary, we have the following effective fiber dimension theorem, stated in a more standard form.

Let $V\subseteq \AA^n$ be an irreducible affine variety over an algebraically closed field $\FF$.
Let $h_1,\dots,h_s\in \FF[X_1,\dots,X_n]$
with $\deg h_1\geq \dots \geq \deg h_s$.
Let $f_1,\dots,f_m\in \mathcal{L}_{h_1,\dots,h_s,\FF}$, which define a polynomial map $f: \AA^n\to\AA^m$.
Finally, let $W=\overline{f(V)}\subseteq\AA^m$.
Then there exists a polynomial $P\in\FF[X_1,\dots,X_n]$ of degree at most $\dim W\cdot \deg V\cdot  \prod_{i=1}^{\dim W} \deg h_i$ that does not vanish identically on $V$ such that for every $a\in V$ satisfying $P(a)\neq 0$, the fiber $f|_V^{-1}(f(a))$ is equidimensional of dimension $\dim V-\dim W$.

Let $k=\dim V$.
Note that the polynomial map $\pi: \AA^n\to\AA^k$ satisfying the conditions in Theorem <ref> always exists by Noether normalization (see, e.g., Lemma
<ref>). Now apply Theorem <ref> with $t=0$.

Theorem <ref> is proved in Appendix <ref>.

Degree bound for the images of affine varieties.

Finally, we need the following degree bound for the images of affine varieties (or more precisely, their closures) under polynomial maps.

Let $V\subseteq \AA^n_\FF$ be an affine variety over a field $\FF$.
Let $h_1,\dots,h_s\in \FF[X_1,\dots,X_n]$
with $\deg h_1\geq \dots \geq \deg h_s$.
Let $f_1,\dots,f_m\in \mathcal{L}_{h_1,\dots,h_s,\FF}$, which define a polynomial map $f: \AA^n_\FF\to\AA^m_\FF$.
Finally, let $W=\overline{f(V)}\subseteq \AA^m_\FF$.

\[
\deg W\leq \deg V\cdot \prod_{i=1}^{\dim W} \deg h_i.
\]

We prove Lemma <ref> in Appendix <ref>.
It generalizes a bound in <cit.>, which states that $\deg W\leq d^{\dim W}$ if $V=\AA^n_\FF$ and $\deg f_i\leq d\in \NN^+$ for $i\in [m]$.

§ LINEAR SEEDED RANK EXTRACTORS FOR VARIETIES

In this section, we consider the problem of constructing seeded rank extractors for varieties that are linear: i.e., a set of linear maps such that for every variety $V$ most of the maps in the set preserve the dimension of $V$.
We show that these objects are simply linear seeded rank extractors for subspaces, a well-known linear algebraic pseudorandom object for which explicit constructions were given in [20, 18, 17].

The proof is based on the notion of tangent spaces of varieties, which are linear subspaces that are local first-order approximations of varieties.
Intuitively, for an affine variety $V$, as we look at smaller and smaller neighborhoods of a nonsingular point $a$ of $V$, the tangent space $T_a V$ would become a better and better approximation of $V$. Thus, one should expect that a linear map that preserves the dimension of $T_a V$, which is a subspace, also preserves the dimension of $V$. While it is not entirely obvious what “smaller and smaller neighborhoods” mean in the Zariski topology, we will see that the claim is indeed true and follows from general facts in algebraic geometry.

Fix $\FF$ to be an algebraically closed field throughout this section. We first formally define seeded rank extractors for varieties and subspaces.

Let $\varphi_1,\dots,\varphi_\ell:\AA^n\to \AA^m$ be polynomial maps, where $n\geq m$. We say $(\varphi_i)_{i\in [\ell]}$ is an $(n, m, k, \epsilon)$ seeded rank extractor for varieties (resp. subspaces)  if for every affine variety (resp. linear subspace) $V\subseteq\AA^n$ over $\FF$ of dimension at least $k$, all but at most $\epsilon$-fraction of $\varphi_i$ satisfy $\dim \overline{\varphi_i(V)}=m$ (or equivalently, $\varphi_i|_V: V\to \AA^m$ is dominant).
We call $\log \ell$ the  seed length of the seeded rank extractor.

In addition, we say $(\varphi_i)_{i\in [\ell]}$ is linear if each $\varphi_i$ is a linear map, i.e., defined by linear polynomials.

The optimal choice of $k$ is $k=m$, in which case the seeded rank extractor is “lossless.”
Explicit linear $(n,m,k,\epsilon)$ seeded rank extractors for subspaces with seed length $O(\log n+\log(1/\epsilon))$ and $k=m$ was first constructed by Gabizon and Raz [20]. We use an improved construction given in [18, 17].

Let $n\in \NN^+$ and $m\in [n]$.
Let $\omega\in \FF^\times$ such that the multiplicative order of $\omega$ is at least $n$. Let $s_1,\dots,s_\ell$ be distinct elements in $\FF^\times$.
For $i\in [\ell]$, let $\varphi_i: \AA^n\to\AA^m$ be the linear map defined by the $m\times n$ matrix $((\omega^{j'-1} s_i)^{j-1})_{j'\in [m], j\in [n]}$.
In other words, $\varphi_i$ is given by

\[
\varphi_i:  (a_1,\dots,a_n)\mapsto \left(\sum_{j=1}^n s_i^{j-1} a_j,  \sum_{j=1}^n (\omega s_i)^{j-1} a_j, \dots, \sum_{j=1}^n (\omega^{m-1} s_i)^{j-1} a_j \right).
\]

Then $(\varphi_i)_{i\in [\ell]}$ is a linear $(n,m,m,\epsilon)$ seeded rank extractor for subspaces, where $\epsilon=m(n-m)/\ell$.

The main result of this section is the following theorem.

An $(n, m, k, \epsilon)$ linear seeded rank extractor for subspaces is also an $(n, m, k, \epsilon)$ linear seeded rank extractor for varieties.

The construction $(\varphi_i)_{i\in [\ell]}$ in Lemma <ref>  is a linear $(n,m,m,\epsilon)$ seeded rank extractor for varieties, where $\epsilon=m(n-m)/\ell$.

§.§ Tangent Spaces and the Jacobian Criterion for Smoothness

The proof of Theorem <ref> uses the notion of tangent spaces.

Let $V\subseteq \AA^n$ be an affine variety over $\FF$.
For a point $a\in V$,
the tangent space $T_a V$ of $V$ at $a$ is the linear subspace of $\AA^n$ defined by the linear equations

\[
\sum_{i=1}^n \frac{\partial f}{\partial X_i}(a)\cdot X_i=0,  \qquad f=f(X_1,\dots,X_n)\in I(V).
\]

To explain the intuition, note that at a point $a=(a_1,\dots,a_n)\in V$, the inhomogeneous linear equations $\sum_{i=1}^n \frac{\partial f}{\partial X_i}(a)\cdot (X_i - a_i)=0$ with $f\in I(V)$ define an affine subspace of $\AA^n$ passing through $a$, which can be seen as a first-order approximation of $V$ locally at $a$.
The tangent space $T_a V$ is defined to be the linear subspace that is a translate of this affine subspace.

The dimension of a tangent space is bounded from below by the dimension of the variety, as stated by the following lemma.

$\dim T_a V \geq \dim V$ for every affine variety $V$ over $\FF$ and $a\in V$.

The notion of smoothness can be defined in terms of whether the equality in Lemma <ref> is attained. For simplicity, we define it only for irreducible affine varieties, which suffices for us.

Let $V$ be an irreducible affine variety over $\FF$ and let $a\in V$.
If $\dim T_a V=\dim V$,
then we say $V$ is smooth or nonsingular at $a$, and $a$ is a nonsingular point of $V$.
Otherwise,   we say  $V$ is non-smooth or singular at $a$, and $a$ is a singular point of $V$.

Denote by $V_{\mathrm{sing}}$ the subset of singular points of $V$, called the singular locus of $V$.

Jacobian criterion for smoothness.

The singular locus $V_\mathrm{sing}$ of $V$ can be determined via the Jacobian criterion, which we explain now.

Let $f_1,\dots,f_m\in\FF[X_1,\dots,X_n]$. The associated Jacobian matrix $J_{\mathbf{f}}$ is an $m\times n$ matrix over the ring $\FF[X_1,\dots,X_n]$, defined by

\[
J_{\mathbf{f}}=\left(\frac{\partial f_i}{\partial X_j}\right)_{i\in [m], j\in [n]}.
\]

Let $V\subseteq\AA^n$ be an affine variety over $\FF$, and
let $f_1,\dots,f_m\in\FF[X_1,\dots,X_n]$ such that $\{f_1,\dots,f_m\}$ is a generating set of $I(V)$.
Then for $a=(a_1,\dots,a_n)\in V$, the tangent space $T_a V$ is the right nullspace of $J_{\mathbf{f}}(a)$.

By definition, we want to show the following statement:   $\sum_{j=1}^n \frac{\partial f_i}{\partial X_j}(a)\cdot a_j=0$  for all $i\in [m]$
iff $\sum_{j=1}^n \frac{\partial f}{\partial X_j}(a)\cdot a_j=0$ for all $f\in I(V)$. The “if” part is immediate as $f_1,\dots,f_m\in I(V)$.

To see the “only if” part, consider $f\in I(V)$. Then $f=\sum_{i=1}^m g_i f_i$ for some $g_1,\dots,g_m\in\FF[X_1,\dots,X_n]$.
So for $j\in [n]$,

\[
\frac{\partial f}{\partial X_j}(a)=\sum_{i=1}^m\left(\frac{\partial g_i}{\partial X_j}(a)f_i(a)+g_i(a)\frac{\partial f_i}{\partial X_j}(a)\right)
=\sum_{i=1}^m g_i(a)\frac{\partial f_i}{\partial X_j}(a)
\]

where the second equality holds as $f_i$ vanishes at $a\in V$ for $i\in [m]$.
It follows that if $\sum_{j=1}^n \frac{\partial f_i}{\partial X_j}(a)\cdot a_j=0$ for $i\in [m]$, then $\sum_{j=1}^n \frac{\partial f}{\partial X_j}(a)\cdot a_j=0$.

Let $V\subseteq\AA^n$ be an irreducible affine variety of dimension $k$  over $\FF$, and
let $f_1,\dots,f_m\in\FF[X_1,\dots,X_n]$ such that $\{f_1,\dots,f_m\}$ is a generating set of $I(V)$.
Then  the singular locus of $V$ is given by

\[
V_\mathrm{sing}=\{a\in V: \rank J_{\mathbf{f}}(a)<n-k\},
\]

which is an affine subvariety of $V$ defined by the set of all $(n-k)\times (n-k)$ minors of $J_{\mathbf{f}}$.

By Lemma <ref>, the condition that $\rank J_{\mathbf{f}}(a)<n-k$ is equivalent to $\dim T_a V>k$. This is further equivalent to $\dim T_a V\neq k$ by Lemma <ref>. So the claim holds by definition.

The above Jacobian criterion is related to but different from the Jacobian criterion for algebraic independence. The latter states that the transcendence degree of $\FF(f_1,\dots,f_m)/\FF$ equals the rank of the associated Jacobian matrix $J_{\mathbf{f}}$, and in particular, $f_1,\dots,f_m$ are algebraically independent iff $\rank J_{\mathbf{f}}=m$. However, this statement requires the characteristic of $\FF$ to be zero or large, or more generally, a certain separability condition to hold. On the other hand, the Jacobian criterion for smoothness that we use holds without extra conditions. In particular, it works in any characteristic.

We also need the fact that varieties are almost-everywhere-nonsingular.

The set of nonsingular points of an irreducible affine variety $V$ over $\FF$ is a dense open subset of $V$. That is, $V_{\mathrm{sing}}$ is a proper subvariety of $V$.

§.§ Proof of Theorem <ref>

The proof of Theorem <ref> is based on the following lemma.

Let $V\subseteq\AA^n$ be an irreducible affine variety over $\FF$ and let $a\in V$. Let $f_1,\dots,f_m\in \FF[X_1,\dots,X_n]$, which defines a polynomial map $\varphi: \AA^n\to \AA^m$.
Let $W$ be the right nullspace of $J_{\mathbf{f}}(a)=\left(\frac{\partial f_i}{\partial X_j}(a)\right)_{i\in [m], j\in [n]}$.
Suppose $\dim (W\cap T_a V)=\dim V - m$. Then $\dim \overline{\varphi(V)}=m$.

Let $b=(b_1,\dots,b_m)=\varphi(a)\in \AA^m$, so that $a\in\varphi^{-1}(b)$. As $V\cap \varphi^{-1}(b)$ is a subvariety of both $V$ and $\varphi^{-1}(b)$, we have $T_a(V\cap \varphi^{-1}(b))\subseteq (T_a V)\cap (T_a \varphi^{-1}(b))$.

Note that the fiber $\varphi^{-1}(b)\subseteq \AA^n$ is defined by the polynomials $\hat{f}_1,\dots,\hat{f}_m$ where $\hat{f}_i:=f_i-b_i$ for $i\in [m]$.
So $\hat{f}_i\in I(\varphi^{-1}(b))$ for $i\in [m]$.
Pick a finite generating set $\{g_1,\dots, g_s\}$ of $I(\varphi^{-1}(b))$ such that $s\geq m$ and  $g_i=\hat{f}_i$ for $i\in [m]$.
By Lemma <ref>,  the tangent space $T_a \varphi^{-1}(b)$ is the right nullspace of $J_{\mathbf{g}}(a)=\left(\frac{\partial g_i}{\partial X_j}(a)\right)_{i\in [s], j\in [n]}$.
As $\frac{\partial \hat{f}_i}{\partial X_j}=\frac{\partial f_i}{\partial X_j}$ for $i\in [m]$ and $j\in [n]$, we have  $J_{\mathbf{f}}(a)=\left(\frac{\partial \hat{f_i}}{\partial X_j}(a)\right)_{i\in [m], j\in [n]}$. As $g_i=\hat{f}_i$ for $i\in [m]$,  the matrix $J_{\mathbf{f}}(a)$ is the upper $m\times n$ submatrix of  $J_{\mathbf{g}}(a)$.
It follows that  $T_a \varphi^{-1}(b)\subseteq W$.
So $T_a(V\cap \varphi^{-1}(b))\subseteq W\cap T_a V$.

\[
\dim (V\cap \varphi^{-1}(b))\leq \dim T_a(V\cap \varphi^{-1}(b))\leq \dim (W\cap T_a V)=\dim V - m
\]

where the first inequality holds by Lemma <ref>.
On the other hand, by the fiber dimension theorem (Theorem <ref>),

\[
\dim (V\cap \varphi^{-1}(b))\geq \dim V-\dim  \overline{\varphi(V)} \geq \dim V-m.
\]

This forces $\dim (V\cap \varphi^{-1}(b))=\dim V-m$ and $\dim \overline{\varphi(V)}=m$.

We are now ready to prove Theorem <ref>.

Let $V\subseteq\AA^n$ be an affine variety over $\FF$ of dimension at least $k$, and let $V_0$ be an irreducible component of $V$ such that $\dim V_0=\dim V$.
Let $a$ be a nonsingular point of $V_0$, which exists by Lemma <ref>.
Then $\dim T_a V_0=\dim V_0\geq k$.

We claim that for a linear map $\varphi: \AA^n\to\AA^m$,  if $\dim \varphi(T_a V_0)=m$, then $\dim \overline{\varphi(V_0)}=m$ and hence $\dim \overline{\varphi(V)}=m$. Note that this claim implies Theorem <ref>. This follows by choosing $\varphi$ to be each of the linear maps in an $(n, m, k, \epsilon)$ linear seeded rank extractor and noting that $T_a V_0$ is a linear subspace of $\AA^n$ of dimension at least $k$.

So it remains to prove the above claim.
Assume $\dim \varphi(T_a V_0)=m$.
Suppose $\varphi$ is defined by  linear polynomials $f_1,\dots, f_m\in \FF[X_1,\dots,X_n]$.
Let $W$ be the kernel of $\varphi$. Then

\[
\dim (W\cap T_a V_0)=\dim T_a V_0 - \dim \varphi(T_a V_0) = \dim V_0 -m.
\]

As $\varphi$ is linear, $W$ equals the right nullspace of the  matrix $J_{\mathbf{f}}(a)=\left(\frac{\partial f_i}{\partial X_j}(a)\right)_{i\in [m], j\in [n]}$. So  $\dim \overline{\varphi(V_0)}=m$ by Lemma <ref>. This proves the claim and Theorem <ref> follows.

§ DETERMINISTIC RANK EXTRACTORS FOR VARIETIES

Let $\FF$ be an algebraically closed field.
In this section, we consider the problem of constructing explicit deterministic (lossless) rank extractors/condensers for varieties. These are polynomial maps $\AA^n\to\AA^m$ that preserve the dimension of low-degree affine varieties $V\subseteq\AA^n$ over $\FF$ but reduce the dimension of the ambient space.

Dvir, Gabizon and Wigderson [12] constructed explicit deterministic rank extractors for polynomial sources. These objects can also be viewed as deterministic rank extractors for varieties that are the closures of the images of polynomial maps.
A key technique used in their analysis is the  Jacobian criterion for algebraic independence, which requires the characteristic of $\FF$ to be zero or large.

To solve the problem for general varieties, one natural approach  is generalizing the Jacobian criterion for algebraic independence.
A key step in the proof of [12] is showing that a certain polynomial associated with the Jacobian matrix is nonzero.
Thus, it is natural for us to show that a similar polynomial does not vanish completely on affine varieties and that this is sufficient for constructing deterministic rank extractors for varieties.

While this idea can be made rigorous, the problem is that proving the nonvanishing of a polynomial on an affine variety appears to be challenging. We need to show that not only is the polynomial nonzero, but it remains nonzero modulo the ideal defining the variety. It is not clear to us how to prove such a result due to the generality of the variety.

The DKL construction.
Instead of using a Jacobian-based construction, we take a different approach. Namely, we show that the explicit construction of variety evasive sets by Dvir, Kollár, and Lovett [13] can be used to construct deterministic rank extractors for varieties.
Variety evasive sets are large finite subsets of $\AA^n$ that have small intersections with varieties of low degree and low dimension.
While they do not give deterministic rank extractors for varieties in general, we show that the construction of variety evasive sets in [13] does give such a construction.

More specifically, Dvir, Kollar and Lovett [13] construct explicit variety evasive sets by constructing an explicit polynomial map $\varphi:\AA^n\to\AA^m$ defined by polynomials $f_1,\dots,f_m\in \FF[X_1,\dots, X_n]$ such that the intersection of $\varphi^{-1}(\mathbf{0})=V(f_1,\dots,f_m)$ with any low-degree variety of dimension at most $m$ is finite, where $\mathbf{0}$ denotes the origin of $\AA^n$. We observe that this remains true if  $\varphi^{-1}(\mathbf{0})$ is replaced by  $\varphi^{-1}(b)$ for any $b\in \AA^m$. In other words, for any low-degree variety $V$ of dimension at most $m$, the polynomial map $\varphi$ restricts to a morphism $\varphi|_V: V\to \AA^m$ whose fibers are all finite sets. In the terminology of algebraic geometry, this means $\varphi|_V$ is a quasi-finite morphism. By the fiber dimension theorem (Theorem <ref>), we then have $\dim \overline{\varphi(V)}=\dim(V)$.

In this section, we construct explicit deterministic rank extractors and rank condensers for varieties by adapting the analysis in [13]. We also formulate the construction in a way that highlights the connection with linear error-correcting codes. In particular, a linear MDS code yields a deterministic rank extractor for varieties in the sense that the coefficients of the polynomials that define the rank extractor are specified by a parity-check matrix of the code.

In Section <ref>, we will show that the polynomial map $\varphi$ has the stronger property that $\varphi|_V$ is a finite morphism, not just quasi-finite, and this gives explicit Noether normalization lemmas for affine varieties and affine algebras.

§.§ The Explicit Construction

We first define deterministic rank extractors and rank condensers for varieties.

Let $n\in\NN^+$ and $m\in [n]$.
A polynomial map $\varphi:\AA^n\to \AA^m$ is an $(n,m,k,d)$ deterministic (lossless) rank condenser if $\dim\barr{\varphi(V)} = \dim V $ for every affine variety $V \subseteq \AA^n$ over $\FF$ of dimension at most $k$ and degree at most $d$.
When $k=m$, we also say $\varphi$ is an $(n,m,d)$ deterministic (lossless) rank extractor.

$k$-regular matrices.
Let $n\in\NN^+$ and $m,k\in [n]$.
We say a matrix $M\in\FF^{m\times n}$ is $k$-regular if any $k$ distinct columns of $M$ are linearly independent.
(The same definition was given in [13] but for only for the special case where $k=m$.)

The following lemma gives a coding-theoretic characterization of $k$-regularity. Its proof is straightforward.

Let $\KK$ be a subfield of $\FF$ and let $M\in \KK^{m\times n}\subseteq\FF^{m\times n}$, where $n\in\NN^+$ and $m,k\in [n]$. The following statements hold.

* $M$ is $k$-regular iff there does not exist a nonzero vector $u\in \KK^n$ of Hamming weight at most $k$ such that $Mu=0$.

* Suppose $k=m$.  Then $M$ is $k$-regular iff it is an MDS matrix, i.e., every maximal minor of $M$ is nonzero.

In particular, assuming $\KK$ is a finite field, the matrix $M$ is $k$-regular iff  the linear code $C=\{u\in\KK^n: Mu=0\}$ over $\KK$ defined by the parity check matrix $M$ has minimum distance at least $k+1$. And if $k=m$, then $M$ is $k$-regular iff $C$ is a linear MDS code of minimum distance $k+1$, i.e., it is a linear code of dimension $n-k$ and minimum distance $k+1$.[We define the minimum distance of the zero code $\{0\}$ to be $n+1$, so that the statement also holds for $k=n$.]

The construction.

We now present the explicit construction of deterministic rank extractors and condensers for varieties. It is based on the explicit construction of variety evasive sets in [13].

Let $n, d\in \NN^+$ and $m,k\in [n]$. Let $ d_1,\dots, d_n$ be $n$ pairwise coprime integers greater than $d$.[While [13] assumes $d_1>\dots>d_n$, this assumption does not really matter.]
Let $M=(c_{i,j})_{i\in [m], j\in [n]}\in\FF^{m\times n}$ be a $k$-regular matrix.
Let $\varphi=\varphi(M): \AA^n\to \AA^m$ be the polynomial map

\[
\varphi: (a_1,\dots,a_n)\mapsto \left(\sum_{j=1}^n c_{1,j} a_j^{d_j}, \dots, \sum_{j=1}^n c_{m,j} a_j^{d_j}\right).
\]

We remark that, curiously, the construction above is very similar to the construction of an affine extractor in Section <ref>, although their purposes and the techniques used to analyze them are substantially different.

The following theorem and its corollaries are the main results of this section.

For every $b\in \AA^m$ and every affine variety $V\subseteq\AA^n$ over $\FF$ of dimension at most $k$ and degree at most $d$, the fiber $(\varphi|_V)^{-1}(b)=\varphi^{-1}(b)\cap V$ is a finite set.

$\varphi$ is an $(n, m, k,d)$ deterministic rank condenser for varieties.
In particular, if $m=k$, then $\varphi$ is an $(n, m, d)$ deterministic rank extractor for varieties.

Let $V\subseteq \AA^n$ be an affine variety over $\FF$ of dimension at most $k$ and degree at most $d$. Let $V_0$ be an irreducible component of $V$.
Then $\dim V_0\leq k$ and $\deg V_0\leq d$.
It suffices to show $\dim \barr{\varphi(V_0)}= \dim V_0$.
This follows from Theorem <ref> and the fiber dimension theorem (Theorem <ref>).

Choosing $d_1,\dots,d_n$.

We still need to argue that $d_1,\dots,d_n$ and $M$ can be computed efficiently.
One can choose $d_1,\dots, d_n$ to be $n$ distinct primes greater than $d$.
The resulting deterministic time complexity of computing these integers is $\poly(n,d)$. The polynomial dependence on $d$ is due to the fact that there is no known deterministic $N^{o(1)}$-time algorithm for finding primes greater than an integer $N>0$.

To improve the time complexity, we may compute $d_i$ in the following alternative way. Compute the smallest $n$ distinct primes $p_1,\dots,p_n$, which have order $O(n\log n)$.
For $i\in [n]$, let $d_i$ be the smallest power of $p_i$ such that $d_i>d$, so that $d_i=O(p_i d)=O(nd\log n)$. Then $d_1,\dots,d_n$ can be computed
in time $\poly(n, \log d)$.

Choosing the matrix $M$.

We need to choose a $k$-regular matrix $M$.
For the problem of constructing an $(n,m,d)$ deterministic rank extractor for varieties (i.e., $k=m$), we need to choose $M\in \FF^{n\times m}$ to be an MDS matrix by Lemma <ref>.
This can be achieved by choosing $M$ to be an Vandermonde matrix $(\omega_j^{i-1})_{i\in [m], j\in [n]}$ with distinct $\omega_1,\dots,\omega_n\in \FF$.

Suppose $\FF$ has a finite subfield $\FF_q$. Then using a Vandermonde matrix, we need $q\geq n$ to have $M\in \FF_q^{m\times n}$.
The condition $q\geq n$  can be relaxed to $q\geq n-1$ in general, and to $q\geq n-2$ in some special cases as explicit MDS matrices $M\in\FF_q^{m\times n}$ are known in these cases [38].

In the case where $k=m\in\{1,n-1,n\}$, we do not need any lower bound on $q$ as all-one vectors and identity matrices are always MDS matrices, and so is the $(n-1)\times n$ matrix $M=(c_{i,j})_{i\in [n-1], j\in [n]}$ defined by

\[
1 & i=j,\\
-1 & j=n,\\
0 & \text{otherwise}.
\end{cases}
\]

So we have the following corollary.

For $m\in\{1,n-1,n\}$, there exists an explicit construction of an $(n,m,d)$ deterministic rank extractor for varieties that is defined by polynomials $f_1,\dots,f_m\in\FF[X_1,\dots, X_n]$ satisfying the following:

* All the coefficients of $f_1,\dots,f_m$ are in $\{0,1,-1\}$, and hence are in every subfield of $\FF$.

* $\deg f_1,\dots, \deg f_m=O((n+d)\log (n+d))$. And the sparse representations of $f_1,\dots,f_m$ can be computed in time $\poly(n, d)$. The time complexity can be improved to $\poly(n, \log d)$ at the cost of increasing the degrees of $f_1,\dots,f_m$ to $O(nd\log n)$.

A similar statement holds for general $m\in [n]$ and the coefficients of $f_1,\dots,f_m$ can be chosen in a finite field $\FF_q$, assuming $\FF_q$ is a subfield of $\FF$ and $q\geq n-1$. The time complexity would also depend polynomially on $\log q$.

The above explicit $(n,m,d)$ deterministic extractor for varieties will be used in the proof of Theorem <ref>, but only in the case where $m=1$.
Previously, Dvir <cit.> gave an explicit construction of an $(n, 1,d)$ deterministic rank extractor  for varieties, where the polynomial defining the rank extractor is recursively constructed and has degree $\poly(d^n)$. Corollary <ref> improves the degree of the polynomial to $\widetilde{O}(n+d)$ or $\widetilde{O}(nd)$.

§.§ Proof of Theorem <ref>

Theorem <ref> can be proved via a simple adaptation of the proof in [13].
For the sake of completeness, we present the proof below.

First, we need the following two lemmas from [13].

Let $V\subseteq\AA^n$ be an affine variety over $\FF$ of dimension at least one.
Then there exist Laurent power series $h_1(T),\dots,h_n(T)\in\FF((T))$
such that

* at least one $h_i(T)$ has a pole, i.e., $h_i(T)\not\in\FF[[T]]$, and

* $P(h_1(T),\dots,h_n(T))=0$ for all $P\in I(V)$.

Let $V\subseteq\AA^n$ be an affine variety over $\FF$ of dimension $k<n$ and degree $d$.
For every $J=\{i_1,\dots,i_{k+1}\}\subseteq [n]$ of size $k+1$, there exists a nonzero polynomial $g\in I(V)\cap \FF[X_{i_1},\dots,X_{i_{k+1}}]$ of degree at most $d$.

We adapt the proof of [13] to prove the following lemma.

Let $M=(c_{i,j})_{i\in [m], j\in [n]}\in\FF^{m\times n}$ be a $k$-regular matrix, and let $ d_1, \dots, d_n$ be pairwise coprime integers greater than $d$.
Let $V\subseteq\AA^n$ be an affine variety over $\FF$ of dimension at most $k$ and degree at most $d$.
Then, there do not exist $h_1(T), \dots , h_n(T) \in \FF((T))$ that simultaneously satisfy the following conditions:

* At least one $h_i(T)$ has a pole, i.e., $h_i(T)\not\in\FF[[T]]$.

* $P(h_1(T),\dots,h_n(T))=0$ for all $P\in I(V)$.

* $\sum_{j=1}^n c_{i,j} h_j(T)^{d_j}\in \FF[[T]]$ for all $i\in [m]$.

By replacing $k$ with $k'=\dim V$, we may assume the dimension of $V$ is exactly $k$.
Assume to the contrary that there exist $h_1(T), \dots, h_n(T) \in \FF((T))$ satisfying the three conditions.
Let $R$ be the greatest integer such that the term $T^{-R}$ appears in the Laurent series $h_j(T)^{d_j}$ for some $j\in [n]$. By the first condition, at least one of the $h_j(T)$ has a pole, so we know $R > 0$.

Let $J$ be the set of $j\in [n]$ for which the term $T^{-R}$ appears in the Laurent series $h_j(T)^{d_j}$. Then $J\neq \emptyset$.
We claim $|J|\geq k+1$.
To see this,
let $u_j\in\FF$ be the coefficient of the term $T^{-R}$ in $h_j(T)^{d_j}$ for $j\in [n]$.
Let $u=(u_1,\dots,u_n)\in\FF^n$.
Then the support of $u$ is precisely $J$.
By the third condition, for $i\in [m]$,

\begin{equation}\label{eq:condition-3}
\sum_{j=1}^n c_{i,j} h_j(T)^{d_j}\in \FF[[T]].
\end{equation}

The coefficient of $T^{-R}$ in the LHS of (<ref>) is $\sum_{j=1}^n c_{i,j} u_j$, which equals zero by (<ref>) and the fact that $R>0$.
So we get the equation

\[
M u=0.
\]

By the $k$-regularity of $M$ and Lemma <ref>, the Hamming weight of $u$ is at least $k+1$, i.e., $|J|\geq k+1$. This proves the claim. Also note that this implies $k<n$ as $|J|\leq n$.

From here, the rest of the proof is identical to that of <cit.>.
We present the proof for the sake of completeness.
For $j \in J$,  let $r_j$ be the maximal integer such that $T^{-r_j}$ appears in $h_j$, and it follows that $r_j = R/d_j$.

Let $\{j_1, \dots, j_{k+1}\}$ be a subset of $J$ of size $k+1$. By Lemma <ref>,
there exists a nonzero polynomial $g(X_{j_1},\dots,X_{j_{k+1}})\in I(V)\cap \FF[X_{j_1},\dots,X_{j_{k+1}}]$ of degree at most $d$.
By the second condition, we have

\begin{equation}\label{eq:vanishing-on-Laurent-series}
g(h_{j_1}(T),\dots, h_{j_{k+1}}(T))=0.
\end{equation}

Next, we observe that for every monomial $Q=X_{j_1}^{\gamma_1}\cdots X_{j_{k+1}}^{\gamma_{k+1}}$, the term $T^{-\sum_{i=1}^{k+1} \gamma_i r_{j_i}}$ appears in $Q(h_{j_1}(T),\dots, h_{j_{k+1}}(T))$.
Choose a monomial $X_{j_1}^{\alpha_1}\cdots X_{j_{k+1}}^{\alpha_{k+1}}$ that appears in $g$ such that $\sum_{i=1}^{k+1} \alpha_i r_{j_i}$ is maximized. Such a monomial exists as $g\neq 0$. Then $g$ must contain a different monomial $X_{j_1}^{\beta_1}\cdots X_{j_{k+1}}^{\beta_{k+1}}$ such that

\begin{equation}\label{eq:two-terms}
\sum_{i=1}^{k+1} \alpha_i r_{j_i}=\sum_{i=1}^{k+1} \beta_i r_{j_i}.
\end{equation}

Otherwise, the term $T^{-\sum_{i=1}^{k+1} \alpha_i r_{j_i}}$ would appear in $g(h_{j_1}(T),\dots, h_{j_{k+1}}(T))$, which contradicts (<ref>).

Let $D = \prod\limits_{i=1}^{k+1} d_{j_i}$.
Plugging $r_{j_i}=R/d_{j_i}$ into (<ref>) and then multiplying both sides of (<ref>) by $D/R$, we get

\begin{equation}\label{eq:two-terms-2}
\sum_{i=1}^{k+1} \alpha_i D/d_{j_i}=\sum_{i=1}^{k+1} \beta_i D/d_{j_i}.
\end{equation}

Consider arbitrary $i\in [k+1]$.
Taking (<ref>) modulo $d_{j_{i}}$, we get

\[
\alpha_{i} D/d_{j_{i}}\equiv\beta_{i} D/d_{j_{i}} \pmod{d_{j_{i}}}.
\]

As $D/d_{j_{i}}$ is coprime to $d_{j_{i}}$, we may cancel it from both sides, which gives

\[
\alpha_{i} \equiv\beta_{i} \pmod{d_{j_{i}}}.
\]

As $0\leq \alpha_{i}, \beta_{i}\leq \deg(g)\leq d< d_{j_{i}}$, we have $\alpha_{i}=\beta_{i}$. As $i\in [k+1]$ is arbitrary, we have $(\alpha_1,\dots,\alpha_{k+1})=(\beta_1,\dots,\beta_{k+1})$, contradicting the assumption that $X_{j_1}^{\alpha_1}\cdots X_{j_{k+1}}^{\alpha_{k+1}}\neq X_{j_1}^{\beta_1}\cdots X_{j_{k+1}}^{\beta_{k+1}}$.

Lemma <ref> was implicitly proved in [13] except that the third condition was replaced by the stronger statement $\sum_{j=1}^n c_{i,j} h_j(T)^{d_j}=0$.
Our observation is that the proof still works if this condition is relaxed to $\sum_{j=1}^n c_{i,j} h_j(T)^{d_j}\in \FF$, or even $\sum_{j=1}^n c_{i,j} h_j(T)^{d_j}\in \FF[[T]]$. (As can be seen below, the former relaxation suffices for proving Theorem <ref>, but we will need the latter in Section <ref> and Appendix <ref> when we prove that $\varphi|_V$ is a finite morphism.)

Now we are ready to prove Theorem <ref>.

Assume to the contrary that Theorem <ref> does not hold. Then there exist an affine variety $V\subseteq\AA^n$ over $\FF$ of dimension at most $k$ and degree at most $d$ and $b=(b_1,\dots,b_m)\in\AA^m$ such that $\varphi^{-1}(b)\cap V$ is not finite, i.e., $\dim (\varphi^{-1}(b)\cap V)\geq 1$.
Applying Lemma <ref> to $\varphi^{-1}(b)\cap V$, we see that there exist Laurent power series $h_1(T),\dots,h_n(T)\in\FF((T))$ such that

* at least one $h_i(T)$ has a pole, and

* $P(h_1(T),\dots,h_n(T))=0$ for all $P\in I(\varphi^{-1}(b)\cap V)$.

As $I(V)\subseteq I(\varphi^{-1}(b)\cap V)$, the second item implies $P(h_1(T),\dots,h_n(T))=0$ for all $P\in I(V)$.
In addition, for $i\in [m]$, we have $\left(\sum_{j=1}^n c_{i,j} X_j^{d_j}\right)-b_i\in I(\varphi^{-1}(b))\subseteq I(\varphi^{-1}(b)\cap V)$ by the definition of $\varphi$. So the second item also implies

\[
\sum_{j=1}^n c_{i,j} h_j(T)^{d_j}=b_i\in \FF\subseteq \FF[[T]] \qquad \text{for}~i\in [m].
\]

But then $h_1(T),\dots,h_n(T)$ satisfy the three conditions in Lemma <ref>, and $M=(c_{i,j})_{i\in [m], j\in [n]}$ is $k$-regular. This contradicts Lemma <ref>.

§ DECOMPOSITION AND MIN-ENTROPY ESTIMATION OF $(N,K,D)$ ALGEBRAIC SOURCES

In this section, we prove that every $(n,k,d)$ algebraic source can be (approximately) decomposed into a convex combination of irreducible, or even irreducibly minimal $(n,k,d)$ sources.
In particular, this reduces the problem of constructing deterministic extractors for general $(n,k,d)$ algebraic sources to that for irreducibly minimal $(n,k,d)$ algebraic sources. We will use this reduction in Section <ref>.

In addition, we show that every $(n,k,d)$ algebraic source $D$ over $\FF_q$ is close to a distribution with min-entropy about $k\log q$, and that this estimation is tight up to an additive term of order $O(\log d)$ assuming that $k$ is maximized, i.e., that $D$ is not an $(n,k+1,d)$ algebraic source over $\FF_q$.

§.§ Decomposition of $(n,k,d)$ Algebraic Sources

First, we prove some useful lemmas.

Let $V\subseteq\AA^n_\FF$ be an affine variety of dimension $k$ over a field $\FF$. Let $V_1,\dots, V_s$ be the irreducible components of $V$.
Suppose $S$ is a finite subset of $\FF$.
For $i\in [s]$, let $B_i$ be the subset of $V_i\cap S^n$ consisting of the points that are in the intersection of at least two irreducible components of $V$. Then $\sum_{i=1}^s |B_i|\leq (\deg V)^2 |S|^{k-1}$.

For $i\in [s]$, we have $|B_i|\leq \deg V_i\cdot \deg V\cdot q^{k-1}$ by Bézout's inequality (Lemma <ref>) and Lemma <ref>.
So $\sum_{i=1}^s |B_i|\leq \sum_{i=1}^s\deg V_i\cdot \deg V\cdot q^{k-1}=(\deg V)^2\cdot q^{k-1}$.

Let $V\subseteq\AA^n_{\FF_q}$ be an affine variety of dimension $k$ over $\FF_q$ such that no irreducible component of $V$ is absolutely irreducible. Then $|V(\FF_q)|\leq (\deg V)^2 q^{k-1}$.

Naturally identify $V(\FF_q)$ with $V_{\overline{\FF}_q}\cap \FF_q^n$.
The Frobenius automorphism over $\FF_q$ sends every irreducible component of $V_{\overline{\FF}_q}$ to a different irreducible component as these irreducible components are not absolutely irreducible. But it fixes every point in $V(\FF_q)$ since these points are rational. So every point in $V(\FF_q)$ is in the intersection of at least two irreducible components of $V_{\overline{\FF}_q}$.
Applying Lemma <ref> with $\FF=\overline{\FF}_q$ and $S=\FF_q$, we see $|V(\FF_q)|\leq (\deg V_{\overline{\FF}_q})^2 q^{k-1}=(\deg V)^2 q^{k-1}$.

Suppose $S$ is a finite set and $B$ is a proper subset of $S$.
Let $D$ and $D'$ be the uniform distributions over $S$ and $S\setminus B$ respectively. Then $D$ and $D'$ are $\frac{|B|}{|S|}$-close.

Consider the following process: First sample $x\sim D$. If $x\not\in B$, then output $x$. Otherwise sample $y\sim D'$ and output $y$. The distribution of the output is exactly $D'$. So the statistical distance between $D$ and $D'$ is at most $\Pr_{x\sim D}[x\in B]\leq \frac{|B|}{|S|}$.

The next lemma states that every $(n,k,d)$ algebraic source $D$ can be approximately decomposed into a convex combination of irreducible $(n,k,d)$ algebraic sources, and such a decomposition preserves the minimality (i.e., the property that $\dim V=k$). The idea behind the proof is quite natural: we start by decomposing $V$ as a union of irreducible components. We then observe that the contribution of components that are not absolutely irreducible or have dimensions strictly lower than $\dim V$ is small (using Lemma <ref>).
In addition, the remaining irreducible components are approximately disjoint, namely, the intersection of any two distinct irreducible components is small (by Lemma <ref>).
This implies that these irreducible components approximately define a convex combination of irreducible algebraic sources that is close to $D$.

Suppose $q\geq \max\{20d^5, 2d^2/\epsilon\}$, where $\epsilon\in (0,1)$.
Then every $(n,k,d)$ algebraic source $D$ over $\FF_q$ is $\epsilon$-close to a convex combination of irreducible $(n,k,d)$ algebraic sources $D_i$ over $\FF_q$. Moreover, if $D$ is a minimal $(n,k,d)$ algebraic source over $\FF_q$, then each $D_i$ can be chosen to be an irreducibly minimal $(n,k,d)$ algebraic source over $\FF_q$.

Let $D$ be an $(n,k,d)$ algebraic source.
Let $V\subseteq \AA^r_{\FF_q}$ and $f:\AA^r_{\FF_q}\to\AA^n_{\FF_q}$ be as in Definition <ref> so that $D=f(U_{V(\FF_q)})$.

Let $V_*$ be the union of the irreducible components of $V$ that are absolutely irreducible and have dimension $\dim V$, and let $V_*^\mathrm{c}$ be the union of the remaining irreducible components of $V$. Then $V_*\neq \emptyset$ by the first condition in Definition <ref>.
By the effective Lang–Weil bound (Theorem <ref>) and the assumption that $q\geq \max\{20d^5, 2d^2/\epsilon\}$, we have

\begin{equation}\label{eq:bound1}
|V(\FF_q)|\geq |V_*(\FF_q)|\geq q^{\dim V}/2\geq d^2 q^{\dim V-1}/\epsilon.
\end{equation}

Consider an irreducible component $V_0$ of $V_*^\mathrm{c}$. Either $\dim V_0<\dim V$ holds or $V_0$ is not absolutely irreducible.
In the former case, we have $|V_0(\FF_q)|\leq \deg V_0\cdot q^{\dim V-1}$ by Lemma <ref>.
And in the latter case, we have $|V_0(\FF_q)|\leq (\deg V_0)^2\cdot q^{\dim V-1}$ by Lemma <ref>.
Summing over all $V_0$, we conclude that

\begin{equation}\label{eq:bound2}
|V_*^\mathrm{c}(\FF_q)|\leq (\deg V_*^\mathrm{c})^2\cdot q^{\dim V-1}.
\end{equation}

Let $U_{V_*(\FF_q)}$ be the uniform distribution over $V_*(\FF_q)$.
By Lemma <ref>, the distributions $U_{V(\FF_q)}$ and $U_{V_*(\FF_q)}$ are $\epsilon'$-close, where

\begin{equation}\label{eq:bound3}
\epsilon':=\frac{|V(\FF_q)\setminus V_*(\FF_q)|}{|V(\FF_q)|}
\leq \frac{|V_*^\mathrm{c}(\FF_q)|}{|V(\FF_q)|}
\stackrel{\eqref{eq:bound1},\,\eqref{eq:bound2}}{\leq} \frac{(\deg V_*^\mathrm{c})^2}{d^2}\cdot\epsilon.
\end{equation}

Let $V_1,\dots, V_s$ be the irreducible components of $V_*$.
For $i\in [s]$, let $U_i$ be the uniform distribution over $V_i(\FF_q)$. Let $N=\sum_{i=1}^s |V_i(\FF_q)|\geq |V_*(\FF_q)|$.
Define the distribution $U'$ to be the convex combination

\[
U':=\sum_{i=1}^s \frac{|V_i(\FF_q)|}{N} U_i.
\]

Let $B$ be the set of points in $V_*(\FF_q)$ that are in the intersection of at least two irreducible components of $V_*$, and let $B_i=B\cap V_i(\FF_q)$ for $i\in [s]$.
Note that all the points in $V_*(\FF_q)\setminus B$ have the same probability $\frac{1}{N}$ in the distribution $U'$.

Let $p_B=\Pr_{x\sim U'}[x\in B]=\frac{\sum_{i=1}^s|B_i|}{N}$.
Consider the following process: Sample $x\sim U'$. If $x\not\in B$, then output $x$. Otherwise, output $x'\in V_*(\FF_q)$ such that each $y\in V_*(\FF_q)$ is output with probability $p_y$, where

\[
p_B^{-1}\Pr_{x\sim U_{V_*(\FF_q)}}[x=y] & \text{if}~y\in B, \\
p_B^{-1}\left(\Pr_{x\sim U_{V_*(\FF_q)}}[x=y]-\frac{1}{N}\right)=p_B^{-1}\left(\frac{1}{|V_*(\FF_q)|}-\frac{1}{N}\right) & \text{if}~y\not\in B.
\end{cases}
\]

It is easy to verify that the probabilities $p_y$ do define a distribution over $V_*(\FF_q)$.
Moreover, they are chosen in the way that the output distribution of the above process is precisely $U_{V_*(\FF_q)}$.
It follows that $U_{V_*(\FF_q)}$ and $U'$ are $p_B$-close.
By Lemma <ref>, we have $\sum_{i=1}^s |B_i|\leq (\deg V_*)^2 q^{\dim V-1}$. So

\begin{equation}\label{eq:bound4}
p_B=\frac{\sum_{i=1}^s|B_i|}{N}\leq \frac{(\deg V_*)^2 q^{\dim V-1}}{N}\leq \frac{(\deg V_*)^2 q^{\dim V-1}}{|V_*(\FF_q)|}\stackrel{\eqref{eq:bound1}}{\leq} \frac{(\deg V_*)^2}{d^2}\cdot\epsilon.
\end{equation}

As  $\deg V_*+\deg V_*^\mathrm{c}=\deg V\leq d$, we have

\[
\epsilon'+p_B\stackrel{\eqref{eq:bound3},\,\eqref{eq:bound4}}{\leq}
\frac{(\deg V_*^\mathrm{c})^2}{d^2}\cdot\epsilon+\frac{(\deg V_*)^2}{d^2}\cdot\epsilon
\leq \epsilon.
\]

So $U_{V(\FF_q)}$ and $U'$ are $\epsilon$-close. It follows that $D=f(U_{V(\FF_q)})$ and $f(U')$ are $\epsilon$-close. Recall that $U'$ is a convex combination of $U_1,\dots, U_s$, where each $U_i$ is the uniform distribution over $V_i(\FF_q)$. And by definition, $f(U_i)$ is an irreducible $(n,k,d)$ algebraic sources over $\FF_q$ for $i\in [s]$.
It follows that $D$ is $\epsilon$-close to a convex combination of the irreducible $(n,k,d)$ algebraic sources $f(U_1),\dots, f(U_s)$ over $\FF_q$.

Finally, if $D$ is a minimal $(n,k,d)$ algebraic source over $\FF_q$, then by definition, the affine variety $V$ may be chosen such that $\dim V=k$. Then we also have $\dim V_i=k$ for $i\in [s]$ in the above proof. In this case, each $f(U_i)$ is an irreducibly minimal $(n,k,d)$ algebraic source over $\FF_q$ by definition.
So $D$ is $\epsilon$-close to a convex combination of irreducibly minimal $(n,k,d)$ algebraic sources over $\FF_q$.

Next, we further decompose an irreducible $(n,k,d)$ algebraic source into a convex combination of irreducibly minimal $(n,k,d)$ algebraic sources. Our main tool is the effective fiber dimension theorem (Theorem <ref>). Using this theorem and the results of Section <ref>, we intersect the variety $V$ with various translates of a carefully chosen linear subspace. There are some bad events that could happen for some of these intersections. For example, the intersection may have the “wrong” dimension,
or the resulting variety might have the “correct" dimension $k$ but none of the irreducible components of dimension $k$ are absolutely irreducible.
Using the effective fiber dimension theorem, we are able to show that these bad events correspond to small portions of the variety $V$, and then we again obtain a natural way to decompose the remaining part as a convex combination of irreducibly minimal $(n,k,d)$ sources.

We start with the following application of the fiber dimension theorem.

Let $V\subseteq\AA^r_{\FF_q}$ be an irreducible affine variety over $\FF_q$.
Let $\varphi=(\varphi_1,\varphi_2):V\to \AA^{n}_{\FF_q}$ be a dominant morphism defined by $f_1,\dots,f_{n}$, where $\varphi_1$ and $\varphi_2$ are defined by the first $n_1$ and the last $n_2$ polynomials respectively and $n_1+n_2=n$.
Let $U$ be the subset of $a\in V(\FF_q)$ such that $\varphi^{-1}(\varphi(a))$ is equidimensional of dimension $\dim V-n_1-n_2$.
Then we have:

* For $a\in U$, the fiber $V_{\varphi_1(a)}:=\varphi_1^{-1}(\varphi_1(a))$ is equidimensional of dimension $\dim V-n_1$.

* For $a\in U$ and each irreducible component $Z$ of $V_{\varphi_1(a)}$, we have $\dim \overline{\varphi_2(Z)}\leq n_2$. Moreover, the equality is attained if $a\in Z$.

Let $a\in U$.
By the fiber dimension theorem (Theorem <ref>), every irreducible component of $V_{\varphi_1(a)}$ is at least $\dim V-\dim\overline{\varphi_1(V)}\geq \dim V-n_1$.
Also note that $\varphi^{-1}(\varphi(a))=\varphi_2|_{V_{\varphi_1(a)}}^{-1}(\varphi_2(a))$. Again by the fiber dimension theorem, we have

\[