Let $\F$ be the field of $q$ elements. An \emph{\afsext{n}{k}} is a mapping $D:\F^n\ar\B$
such that for any $k$-dimensional affine subspace $X\subseteq \F^n$, $D(x)$ is an almost unbiased
bit when $x$ is chosen uniformly from $X$.
Loosely speaking, the problem of explicitly constructing affine extractors gets harder as $q$ gets smaller and easier
as $k$ gets larger. This is reflected in previous results:
When $q$ is `large enough', specifically $q= \Omega(n^2)$, Gabizon and Raz \cite{GR05} construct affine extractors for any $k\geq 1$.
In the `hardest case', i.e. when $q=2$, Bourgain \cite{Bour05} constructs affine extractors for $k\geq \delta n$ for any constant (and even slightly sub-constant)
$\delta>0$.
Our main result is the following: Fix any $k\geq 2$ and let $d = 5n/k$. Then whenever $q>2\cdot d^2$ and $p=char(\F)>d$,
we give an explicit \afsext{n}{k}.
For example, when $k=\delta n$ for constant $\delta>0$, we get an extractor for a field of constant size $\Omega(\left(\frac{1}{\delta}\right)^2)$.
Thus our result may be viewed as a `field-size/dimension' tradeoff for affine extractors.
Although for large $k$ we are not able to improve (or even match) the previous result of \cite{Bour05}, our construction and proof have the advantage of being very simple:
Assume $n$ is prime and $d$ is odd, and fix any non-trivial linear map $T:\F^n\mapsto \F$.
Define $QR:\F\mapsto \B$ by $QR(x)=1$ if and only if $x$ is a quadratic residue. Then, the function $D:\F^n\mapsto \B$ defined by $D(x)\triangleq QR(T(x^d))$ is an \afsext{n}{k}.

Our proof uses a result of Heur, Leung and Xiang \cite{HLX02} giving a lower bound on the dimension of products of subspaces.

Proof in preliminaries section corrected. Remark Corrected

Let $\F$ be the field of $q$ elements. An (n,k)-affine extractor is a mapping $D:\F^n\ar\B$
such that for any $k$-dimensional affine subspace $X\subseteq \F^n$, $D(x)$ is an almost unbiased
bit when $x$ is chosen uniformly from $X$.
Loosely speaking, the problem of explicitly constructing affine extractors gets harder as $q$ gets smaller and easier
as $k$ gets larger. This is reflected in previous results:
When $q$ is `large enough', specifically $q= \Omega(n^2)$, Gabizon and Raz \cite{GR05} construct affine extractors for any $k\geq 1$.
In the `hardest case', i.e. when $q=2$, Bourgain \cite{Bour05} constructs affine extractors for $k\geq \delta n$ for any constant (and even slightly sub-constant)
$\delta>0$.
Our main result is the following: Fix any $k\geq 2$ and let $d = 5n/k$. Then whenever $q>2\cdot d^2$ and $p=char(\F)>d$,
we give an explicit \afsext{n}{k}.
For example, when $k=\delta n$ for constant $\delta>0$, we get an extractor for a field of constant size $\Omega(\left(\frac{1}{\delta}\right)^2)$.
Thus our result may be viewed as a `field-size/dimension' tradeoff for affine extractors.
Although for large $k$ we are not able to improve (or even match) the previous result of \cite{Bour05}, our construction and proof have the advantage of being very simple:
Assume $n$ is prime and $d$ is odd, and fix any non-trivial linear map $T:\F^n\mapsto \F$.
Define $QR:\F\mapsto \B$ by $QR(x)=1$ if and only if $x$ is a quadratic residue. Then, the function $D:\F^n\mapsto \B$ defined by $D(x)\triangleq QR(T(x^d))$ is an (n,k)-affine extractor.

Our proof uses a result of Heur, Leung and Xiang \cite{HLX02} giving a lower bound on the dimension of products of subspaces.

Abstract made more readable. Small correction in definition in preliminaries section

Let $\F$ be the field of $q$ elements. An \emph{\afsext{n}{k}} is a mapping $D:\F^n\ar\B$
such that for any $k$-dimensional affine subspace $X\subseteq \F^n$, $D(x)$ is an almost unbiased
bit when $x$ is chosen uniformly from $X$.
Loosely speaking, the problem of explicitly constructing affine extractors gets harder as $q$ gets smaller and easier
as $k$ gets larger. This is reflected in previous results:
When $q$ is `large enough', specifically $q= \Omega(n^2)$, Gabizon and Raz \cite{GR05} construct affine extractors for any $k\geq 1$.
In the `hardest case', i.e. when $q=2$, Bourgain \cite{Bour05} constructs affine extractors for $k\geq \delta n$ for any constant (and even slightly sub-constant)
$\delta>0$.
Our main result is the following: Fix any $k\geq 2$ and let $d = 5n/k$. Then whenever $q>2\cdot d^2$ and $p=char(\F)>d$,
we give an explicit \afsext{n}{k}.
For example, when $k=\delta n$ for constant $\delta>0$, we get an extractor for a field of constant size $\Omega(\left(\frac{1}{\delta}\right)^2)$.
Thus our result may be viewed as a `field-size/dimension' tradeoff for affine extractors.
Although for large $k$ we are not able to improve (or even match) the previous result of \cite{Bour05}, our construction and proof have the advantage of being very simple:
Assume $n$ is prime and $d$ is odd, and fix any non-trivial linear map $T:\F^n\mapsto \F$.
Define $QR:\F\mapsto \B$ by $QR(x)=1$ if and only if $x$ is a quadratic residue. Then, the function $D:\F^n\mapsto \B$ defined by $D(x)\triangleq QR(T(x^d))$ is an \afsext{n}{k}.

Our proof uses a result of Heur, Leung and Xiang \cite{HLX02} giving a lower bound on the dimension of products of subspaces.