1 Introduction
A well-known probability puzzle asks how to simulate a fair coin toss given a coin with unknown bias. A solution, due to von Neumann [Reference von Neumann, Householder, Forsythe and Germond21], is to flip the coin twice and if the flips disagree use the first, otherwise flip twice again and repeat. We leave it to the reader to verify that this algorithm does in fact solve the problem. The purpose of extractors in theoretical science is to address a similar problem: given the output of a random variable/source with unknown biases, subject to only some weak assumptions, use these outputs to simulate a random variable with much stronger (more uniform) randomness properties.
We say that a real-valued random variable
$X:\unicode[STIX]{x1D6FA}\rightarrow R$
has min-entropy
$k$
if
$\sup _{r\in R}\mathbb{P}[X=r]\leqslant 2^{-k}.$
Given random variables
$X$
and
$Y$
, we define the statistical distance between them as
$$\begin{eqnarray}\text{SD}(X,Y):=\frac{1}{2}\mathop{\sum }_{r\in R}|\mathbb{P}[X=r]-\mathbb{P}[Y=r]|.\end{eqnarray}$$
We call a family of maps
$\text{Ext}_{N}:[N]\times [N]\rightarrow \{0,1\}$
an extractor family with min-entropy
$\unicode[STIX]{x1D70C}$
if there exists a fixed
$\unicode[STIX]{x1D6FF}>0$
such that for any independent random variables
$X,Y:\unicode[STIX]{x1D6FA}\rightarrow [N]$
with min-entropy rate
$\unicode[STIX]{x1D70C}\log _{2}N$
one has
$$\begin{eqnarray}\text{SD}(\text{Ext}_{N}(X,Y),U)\lesssim \log ^{-\unicode[STIX]{x1D6FF}}N,\end{eqnarray}$$
where
$U$
is the uniform distribution on
$\{0,1\}$
. To ease notation, we will say that
$\text{Ext}_{N}$
is an extractor family with min-entropy rate near
$\unicode[STIX]{x1D70C}$
if it extracts from all sources with min-entropy rate
$\unicode[STIX]{x1D70C}^{\prime }>\unicode[STIX]{x1D70C}$
. We will say that
$\text{Ext}_{N}$
has exponentially small error if one has the stronger estimate
$$\begin{eqnarray}\text{SD}(\text{Ext}_{N}(X,Y),U)\lesssim N^{-\unicode[STIX]{x1D6FF}}\end{eqnarray}$$
for some fixed
$\unicode[STIX]{x1D6FF}>0$
.
Remark 1. The computer science literature typically considers maps from
$\{0,1\}^{\ell }\times \{0,1\}^{\ell }\rightarrow \{0,1\}$
when defining extractors. One can convert to this regime by taking
$\ell =\lceil 2\log p\rceil$
.
There are a number of elementary constructions of extractor families with min-entropy rate greater than
$1/2$
. In 2005, Bourgain [Reference Bourgain1] gave the first explicit constructions of an extractor with min-entropy rate less than
$1/2$
. His proof depended on the finite field Szemerédi–Trotter theorem [Reference Bourgain, Katz and Tao2] and gave an unspecified min-entropy rate. An optimization of the key ingredient, the Szemerédi–Trotter incidence theorem, by Helfgott and Rudnev [Reference Helfgott and Rudnev7] in 2010 gave an exponent
$\frac{3}{2}-\frac{1}{10\,678}$
in that result. Combined with Bourgain’s method in the form below, this gives a min-entropy rate estimate of
$\frac{16\,017}{32\,036}=0.49996\ldots .$
The incidence estimate was further refined by Jones in 2011 who gave an incidence estimate with exponent of
$\frac{3}{2}-\frac{1}{622}=\frac{496}{331}$
which gives a min-entropy rate of around
$\frac{2647}{5296}=0.4998\ldots .$
More recently, Stevens and de Zeeuw [Reference Stevens and de Zeeuw19] introduced several new ideas which allowed them to improve the exponent in the incidence theorem to
$\frac{3}{2}-\frac{1}{30}=\frac{22}{15}$
. This yields an extractor with min-entropy rate near
$\frac{45}{92}=0.489\ldots .$
Lastly, we note that an optimal Szemerédi–Trotter theorem in finite fields with exponent
$4/3$
would imply Bourgain’s extractor has min-entropy rate near
$\frac{9}{20}=0.45$
, following the initial approach of [Reference Bourgain1]. See also [Reference Hegyvari and Hennecart6] for generalizations of Bourgain’s work.
In a 2015 breakthrough paper, Chattopadhyay and Zuckerman [Reference Chattopadhyay and Zuckerman4] gave an alternative approach which produced explicit extractors which extract from sources with arbitrarily small (in fact poly-logarithmic) min-entropy rate. One advantage to Bourgain’s Fourier analytic constructions is that these extractors have exponentially small error, where Chattopadhyay and Zuckerman’s only have poly-logarithmically small error. Finding explicit constructions with both an arbitrarily small min-entropy rate and exponentially small error remains an important open problem in the field. Our interest here is in showing how one can push Bourgain’s Fourier analytic approach further using recent advances in finite field incidence geometry. This allows us to produce explicit constructions with exponentially small error and a lower min-entropy rate than available in the prior literature.
We start by recalling one of Bourgain’s constructions. Let
$F$
be a prime order finite field. Given an element
$x\in F$
, we let
$\unicode[STIX]{x1D70E}(x)\in [0,(p-1)/p]$
denote the real numbers in the interval
$[0,1]$
given by considering the integer representation of
$x$
between
$0$
and
$p-1$
and dividing that number by
$p$
. Moreover, we let
$\unicode[STIX]{x1D70C}:F\rightarrow \{0,1\}$
be defined by
$\unicode[STIX]{x1D70C}(x):=\operatorname{sign}\sin (2\unicode[STIX]{x1D70B}\unicode[STIX]{x1D70E}(x))$
, where we adopt the convention that
$\operatorname{sign}(0)=1$
. We take
$N=p^{2}$
and consider the maps
$\text{Ext}_{p^{2}}$
from
$F^{2}\times F^{2}\rightarrow \{0,1\}$
given by
$$\begin{eqnarray}(x,y)\rightarrow \unicode[STIX]{x1D70C}(x\cdot y+x\cdot x\times y\cdot y).\end{eqnarray}$$
If
$p$
is chosen so that there does not exist an element
$i\in F$
such that
$i^{2}=-1$
, then the map just defined is a Bourgain extractor. Our first result is a refined analysis of one of Bourgain’s extractors.
Theorem 2. Bourgain’s extractor (for
$F$
a prime order finite field in which
$-1$
is not a square) defined above extracts from two independent sources with min-entropy rate near
$\frac{21}{44}=0.477\ldots$
and has exponentially small error.
Next we show that one can construct extractors with lower min-entropy rate by replacing
$F^{2}$
in Bourgain’s construction with
$F^{3}$
.
Theorem 3. Let
$F$
be finite field of order
$p$
and identify
$[N]=F^{3}$
. Then the map
$\text{Ext}_{p^{3}}(x,y)\rightarrow \unicode[STIX]{x1D70C}(x\cdot y+x\cdot x\times y\cdot y)$
from
$F^{3}\times F^{3}\rightarrow \{0,1\}$
is a two-source extractor with min-entropy rate near
$\frac{4}{9}=0.444\ldots$
and has exponentially small error.
We note that Bourgain’s extractor requires one to restrict to prime order fields in which
$-1$
is not a square, while this hypothesis on the prime order field in Theorem 3. In Bourgain’s case, if
$F$
is such that there exists an
$i\in F$
such that
$i^{2}=-1$
then the the zero set of
$z:=\{x\in F^{2}:\unicode[STIX]{x1D70E}(x)=0\}$
contains the line
$\{(t,it):t\in F\}\subset F^{2}$
and the required additive energy will not hold for certain subsets of this line. In the second case, the analogous level set will contain a line regardless of the field. However, to prove Theorem 3 one only needs control of the additive energy for sets substantially larger than that of a line. This phenomenon is explained by the theory of quadratic forms in finite fields, and is discussed in detail in [Reference Lewko12] and also is connected to the recent observation that one can obtain sharp
$L^{2}$
restriction theorems for the finite field paraboloid in high dimensions while the analogous problem remains open in three dimensions. See [Reference Iosevich, Koh and Lewko8] and [Reference Rudnev and Shkredov18].
The proofs proceed by observing that Bourgain’s argument can be extended to a rather general statement relating extraction properties of certain maps to the additive energy of certain subsets in finite fields. Lemmas 4 and 6 below articulate this generalization. The second step is to observe that these statements reduce the maps above to additive energy estimates for subsets of the paraboloid obtained by Rudnev and Shkredov [Reference Rudnev and Shkredov18] in their recent work on the finite field restriction problem. See [Reference Iosevich, Koh and Lewko8, Reference Lewko and Lewko11–Reference Lewko13], and [Reference Mockenhaupt and Tao15] for a discussion of this problem.
Finally we remark that inserting an optimal finite field Szemerédi–Trotter theorem into the Rudnev–Shkredov [Reference Rudnev and Shkredov18] machinery yields an additive energy estimate which when inserted into the machinery below shows that Bourgain’s extractor defined above extracts from sources with min-entropy rate near
$3/8=0.375.$
2 Notation and preliminaries
We will use
$R$
and
$C$
to denote the fields of real and complex numbers, respectively. We will use
$F$
to denote a finite field, which will always be of prime order. We denote the non-zero elements of
$F$
by
$F_{\ast }$
. As usual, we write the additive character on
$F$
as
$e(x):=\text{e}^{2\unicode[STIX]{x1D70B}\text{i}x/p}$
. Given
$x,y\in F^{n}$
, we write
$x\cdot y:=x_{1}y_{1}+\cdots +x_{n}y_{n}$
. Given a subset
$A\in F^{n}$
, we define the additive energy
$$\begin{eqnarray}\unicode[STIX]{x1D6EC}(A):=\mathop{\sum }_{\substack{ a+b=c+d \\ a,b,c,d\in A}}1=\mathop{\sum }_{x\in F^{n}}\Bigg(\mathop{\sum }_{\substack{ a+b=x \\ a,b\in A}}1\Bigg)^{2}.\end{eqnarray}$$
Parseval’s identity is the equality
$$\begin{eqnarray}\mathop{\sum }_{x\in F^{n}}\bigg|\mathop{\sum }_{\unicode[STIX]{x1D709}\in F^{n}}f(\unicode[STIX]{x1D709})e(x\cdot \unicode[STIX]{x1D709})\bigg|^{2}=|F|\mathop{\sum }_{\unicode[STIX]{x1D709}\in F^{n}}|f(\unicode[STIX]{x1D709})|^{2}.\end{eqnarray}$$
If
$f$
is a real- or complex-valued function on a domain
$D$
we define
$\Vert f\Vert _{\ell ^{\infty }}:=\sup _{x\in D}|f(x)|$
. We will write
$X\sim Y$
to indicate that
$Y/2\leqslant X\leqslant 2Y$
. Typically we use this to select a level set of a function. For example
$D_{\unicode[STIX]{x1D706}}:=\{x\in D:f(x)\sim \unicode[STIX]{x1D706}\}$
would denote the elements of the domain,
$D$
, of
$f$
where
$\unicode[STIX]{x1D706}/2~\leqslant f(x)\leqslant 2\unicode[STIX]{x1D706}$
. We will also use the notation
$a\lesssim b$
to indicate that the inequality
$a\leqslant cb$
holds with some universal constant
$c$
. Let
$F^{d}$
denote the
$d$
-dimensional vector space over
$F$
. We define the
$d$
-dimensional paraboloid
$P_{d}\subset F^{d}$
by
$P_{d}:=\{(\text{}\underline{x},\text{}\underline{x}\cdot \text{}\underline{x}),\text{}\underline{x}:F^{d-1}\}$
.
3 Estimates
We start by showing how Fourier analytic estimates imply extractor-type properties. Recall that the Fourier coefficients in the expansion
$\operatorname{sign}\sin (x)=\sum _{\unicode[STIX]{x1D709}\in F}c(\unicode[STIX]{x1D709})e(\unicode[STIX]{x1D709}x)$
satisfy
$$\begin{eqnarray}\mathop{\sum }_{\unicode[STIX]{x1D709}\in F}|c(\unicode[STIX]{x1D709})|\lesssim \log |F|.\end{eqnarray}$$
This can be seen from a simple and direct computation with the Dirichlet kernel; see [Reference Bourgain1, Remark 3.3].
Lemma 4. Let
$f:F^{n}\times F^{n}\rightarrow F$
be a family of maps indexed by
$F$
, such that the following holds. For some fixed
$\unicode[STIX]{x1D6FF}>0$
, one has for all functions
$a,b:F^{n}\rightarrow F$
with
$\Vert a\Vert _{\ell ^{\infty }},\Vert b\Vert _{\ell ^{\infty }}\leqslant 1$
with respective supports
$A,B\in F^{n}$
satisfying
$|A|,|B|\geqslant |F|^{n\unicode[STIX]{x1D70C}}$
that
$$\begin{eqnarray}\max _{\unicode[STIX]{x1D706}\in F_{\ast }}\bigg|\mathop{\sum }_{x\in A,y\in B}a(x)b(y)e(\unicode[STIX]{x1D706}f(x,y))\bigg|\lesssim |F|^{-\unicode[STIX]{x1D6FF}}|A||B|.\end{eqnarray}$$
Then the family of maps
$\unicode[STIX]{x1D70C}(f(x,y))$
from
$F^{n}\times F^{n}\rightarrow \{0,1\}$
is a two-source extractor family with min-entropy rate near
$\unicode[STIX]{x1D70C}$
.
Proof. Let
$U$
denote the uniform distribution on
$\{0,1\}$
. Our goal is to show
$\text{SD}(\unicode[STIX]{x1D70C}(f(x,y)),U)\leqslant |F|^{-\unicode[STIX]{x1D6FF}}$
for some
$\unicode[STIX]{x1D6FF}>0$
. Let
$X$
and
$Y$
denote independent random variables with min-entropy
$k$
and probability mass functions
$A$
and
$B$
, respectively. Let
$J^{\prime }:F\times F\rightarrow \{0,1\}$
denote the probability mass function of
$\unicode[STIX]{x1D70C}(f(x,y))$
, that is,
$J^{\prime }(x):=\mathbb{P}[\unicode[STIX]{x1D70C}(f(x,y))=x]$
and
$J(x)=J^{\prime }(x)-2^{-1}$
. We then have
$$\begin{eqnarray}\text{SD}(\unicode[STIX]{x1D70C}(f(x,y)),U)=\frac{1}{2}\mathop{\sum }_{x\in \{0,1\}}|J(x)|.\end{eqnarray}$$
Expanding in a Fourier series
$\operatorname{sign}\sin x=\sum _{\unicode[STIX]{x1D706}\in F}c(\unicode[STIX]{x1D706})e(\unicode[STIX]{x1D706}x)$
, and applying the estimate (1), we have that the above is
$$\begin{eqnarray}\displaystyle \lesssim |\mathbb{E}\unicode[STIX]{x1D70C}(f(x,y))| & = & \displaystyle \bigg|\mathop{\sum }_{x\in F^{n}}\mathop{\sum }_{y\in F^{n}}\mathop{\sum }_{\unicode[STIX]{x1D706}\in F}A(x)B(y)c(n)e(\unicode[STIX]{x1D706}f(x,y))\bigg|\nonumber\\ \displaystyle & {\lesssim} & \displaystyle \log |F|\max _{\unicode[STIX]{x1D706}\in F_{\ast }}\bigg|\mathop{\sum }_{y\in F^{n}}\mathop{\sum }_{x\in F}A(x)B(y)e(\unicode[STIX]{x1D706}f(x,y))\bigg|.\nonumber\end{eqnarray}$$
The min-entropy assumption implies that
$A(x),B(x)\leqslant |F|^{-\unicode[STIX]{x1D702}}$
. Let
$S_{\unicode[STIX]{x1D703}}:=\{x\in F^{n}:A(x)\sim \unicode[STIX]{x1D703}\}$
, and similarly
$W_{\unicode[STIX]{x1D703}}:=\{x\in F^{n}:B(x)\sim \unicode[STIX]{x1D703}\}$
. Now we split
$A(x)$
and
$B(y)$
into
$O(\log |F|)$
level sets such that
$A_{\ell }(x)=A(x)\sim 2^{-\ell }$
and
$B_{\ell }(x)=B(x)\sim 2^{-\ell }$
on their support which is at most
$2^{\ell }$
. From the hypotheses we may assume that
$\ell \geqslant k$
and have
$$\begin{eqnarray}\displaystyle & & \displaystyle \max _{\unicode[STIX]{x1D706}\in F_{\ast }}\bigg|\mathop{\sum }_{x\in A,y\in B}A(x)B(y)e(\unicode[STIX]{x1D706}f(x,y))\bigg|\nonumber\\ \displaystyle & & \displaystyle \quad \leqslant \mathop{\sum }_{i,j=k}^{\log |F|}\max _{\unicode[STIX]{x1D706}\in F_{\ast }}|A_{i}(x)B_{j}(y)e(\unicode[STIX]{x1D706}f(x,y))|\nonumber\\ \displaystyle & & \displaystyle \quad \lesssim |F|^{-\unicode[STIX]{x1D6FF}}\mathop{\sum }_{i,j=k}^{\log |F|}2^{-i-j}|\text{supp}(A_{i})||\text{supp}(B_{j})|\lesssim |F|^{-\unicode[STIX]{x1D6FF}}\log |F|.\nonumber\end{eqnarray}$$
This completes the proof.◻
Remark 5. The above argument is a special case of what is called Vazirani’s XOR lemma in the computer science literature. See [Reference Rao16, Lemma 4.1]. This lemma, which considers the more general case where the function
$\unicode[STIX]{x1D70C}$
is replaced by a map into other finite abelian groups larger than
$\{0,1\}$
, allows one to use the methods presented here to obtain extractors that output more than one bit. We refer the reader to [Reference Rao16] and omit the routine details.
Next we show how to obtain estimates on exponential sums of the form appearing in the statement of Lemma 4.
Lemma 6. Let
$A,B\subseteq F^{n}$
and
$a,b$
be functions on
$A$
and
$B$
, respectively, such that
$\Vert a\Vert _{\ell ^{\infty }},\Vert b\Vert _{\ell ^{\infty }}\leqslant 1$
. Then
$$\begin{eqnarray}\max _{\unicode[STIX]{x1D706}\in F_{\ast }}\bigg|\mathop{\sum }_{x\in A,b\in B}a(x)b(y)e(\unicode[STIX]{x1D706}x\cdot y)\bigg|\leqslant |A|^{1/2}|B|^{1/2}|F|^{n/8}(\unicode[STIX]{x1D6EC}(A)\unicode[STIX]{x1D6EC}(B))^{1/8}.\end{eqnarray}$$
Proof. By Cauchy–Schwarz,
$$\begin{eqnarray}\displaystyle & & \displaystyle \max _{\unicode[STIX]{x1D706}\in F_{\ast }}\bigg|\mathop{\sum }_{x\in A,y\in B}a(x)b(y)e(\unicode[STIX]{x1D706}x\cdot y)\bigg|\nonumber\\ \displaystyle & & \displaystyle \quad \leqslant |A|^{1/2}\max _{\unicode[STIX]{x1D706}\in F_{\ast }}\bigg(\mathop{\sum }_{x\in A}\bigg|\mathop{\sum }_{y\in B}a(x)b(y)e(\unicode[STIX]{x1D706}x\cdot y)\bigg|^{2}\bigg)^{1/2}\nonumber\\ \displaystyle & & \displaystyle \quad =|A|^{1/2}\max _{\unicode[STIX]{x1D706}\in F_{\ast }}\bigg(\mathop{\sum }_{x\in A}\mathop{\sum }_{y_{1},y_{2}\in B}a(x)b(y_{1})b(y_{2})e(\unicode[STIX]{x1D706}x\cdot (y_{1}-y_{2}))\bigg)^{1/2}\nonumber\\ \displaystyle & & \displaystyle \quad \leqslant |A|^{1/2}|B|^{1/2}\nonumber\\ \displaystyle & & \displaystyle \qquad \times \max _{\unicode[STIX]{x1D706}\in F_{\ast }}\bigg(\!\mathop{\sum }_{x_{1},x_{2}\in A}\mathop{\sum }_{y_{1},y_{2}\in B}\!\!a(x_{1})a(x_{2})b(y_{1})b(y_{2})e(\unicode[STIX]{x1D706}(x_{1}-x_{2})\cdot (y_{1}-y_{2}))\bigg)^{1/4}.\nonumber\end{eqnarray}$$
Now, for
$\unicode[STIX]{x1D709},\unicode[STIX]{x1D702}\in F^{n}$
, let
$$\begin{eqnarray}\displaystyle \displaystyle {\mathcal{A}}_{\unicode[STIX]{x1D706}}(\unicode[STIX]{x1D709}) & = & \displaystyle \mathop{\sum }_{\substack{ x_{1},x_{2}\in A \\ x_{1}-x_{2}=\unicode[STIX]{x1D706}^{-1}\unicode[STIX]{x1D709}}}a(x_{1})a(x_{2}),\nonumber\\ \displaystyle \displaystyle {\mathcal{B}}(\unicode[STIX]{x1D702}) & = & \displaystyle \mathop{\sum }_{\substack{ y_{1},y_{2}\in B \\ y_{1}-y_{2}=\unicode[STIX]{x1D702}}}a(x_{1})a(x_{2}),\nonumber\end{eqnarray}$$
where we let
${\mathcal{A}}(\unicode[STIX]{x1D709}):={\mathcal{A}}_{1}(\unicode[STIX]{x1D709})$
. With this notation, we may rewrite the above as
$$\begin{eqnarray}\displaystyle \displaystyle & {\leqslant} & \displaystyle |A|^{1/2}|B|^{1/2}\max _{\unicode[STIX]{x1D706}}\bigg(\mathop{\sum }_{\unicode[STIX]{x1D709},\unicode[STIX]{x1D702}\in F^{n}}{\mathcal{A}}_{\unicode[STIX]{x1D706}}(\unicode[STIX]{x1D709}){\mathcal{B}}(\unicode[STIX]{x1D702})e(\unicode[STIX]{x1D709}\cdot \unicode[STIX]{x1D702})\bigg)^{1/4}\nonumber\\ \displaystyle \displaystyle & {\leqslant} & \displaystyle |A|^{1/2}|B|^{1/2}\bigg(\bigg(\mathop{\sum }_{\unicode[STIX]{x1D709}\in F^{n}}|{\mathcal{A}}(\unicode[STIX]{x1D709})|^{2}\bigg)^{1/2}\bigg(\mathop{\sum }_{\unicode[STIX]{x1D709}\in F^{n}}\bigg|\mathop{\sum }_{\unicode[STIX]{x1D702}\in F^{n}}{\mathcal{B}}(\unicode[STIX]{x1D702})e\bigg(\unicode[STIX]{x1D709}\cdot \unicode[STIX]{x1D702}\bigg)\bigg|^{2}\bigg)^{1/2}\bigg)^{1/4}.\nonumber\end{eqnarray}$$
Applying Parseval and noting that
$\sum _{\unicode[STIX]{x1D709}\in F^{n}}|{\mathcal{A}}(\unicode[STIX]{x1D709})|^{2}\leqslant \unicode[STIX]{x1D6EC}(A)$
gives
$$\begin{eqnarray}{\leqslant}|A|^{1/2}|B|^{1/2}|F|^{n/8}(\unicode[STIX]{x1D6EC}(A)\unicode[STIX]{x1D6EC}(B))^{1/8}.\end{eqnarray}$$
This completes the proof.◻
Remark 7. The referee has pointed out that nearly the same lemma appears in [Reference Bourgain and Garaev3].
Combining Lemmas 4 and 6 gives us the following proposition.
Proposition 8. Let
$n>d$
and
$M:F^{d}\rightarrow F^{n}$
. Let
$\unicode[STIX]{x1D702}>0$
and assume that for every subset
$A\subseteq F^{d}$
with
$|A|\sim |F|^{n/(8-2\unicode[STIX]{x1D6FC})}$
one has the energy estimate
$\unicode[STIX]{x1D6EC}(M(A))\lesssim |A|^{\unicode[STIX]{x1D6FC}}$
. Then the map
$(x,y)\rightarrow \unicode[STIX]{x1D70C}(M(x)\times M(y))$
is an extractor with min-entropy rate near
$n/d(8-d\unicode[STIX]{x1D6FC}).$
At this point we state the following additive energy estimates of Rudnev and Shkredov [Reference Rudnev and Shkredov18] for subsets of the three-dimensional and four-dimensional paraboloids,
$P_{3}$
and
$P_{4}$
.
Theorem 9. We have the following additive energy estimates. Let
$F$
be a prime order field in which
$-1$
is not a square. Let
$A\subset P_{3}$
with
$|A|\leqslant |F|^{26/21}$
. Then
$$\begin{eqnarray}\unicode[STIX]{x1D6EC}(A)\lesssim |A|^{17/7}.\end{eqnarray}$$
Let
$F$
be an arbitrary prime order finite field. Let
$B\subset P_{4}$
with
$p^{4/3}\leqslant |B|\leqslant p^{2}$
. Then
$$\begin{eqnarray}\unicode[STIX]{x1D6EC}(B)\lesssim |B|^{5/2}.\end{eqnarray}$$
Inserting these estimates into Proposition 8 proves Theorems 2 and 3.
Note added
Recently the author has slightly improved the exponent in the first energy estimate above from
$17/7$
to
$99/41+\unicode[STIX]{x1D716}$
for any
$\unicode[STIX]{x1D716}>0$
. This improves the min-entropy rate of the respective extractor to near
$123/260$
from
$21/41$
. See [Reference Lewko14].
Acknowledgement
We thank David Zuckerman for comments on an earlier draft of this note.
