Algebraic construction of $\varepsilon$-biased sets

Question

Let $\ell> 1$ be an integer and consider the mapping $\text{Tr}:\mathbb{F}_{2^\ell}\to\mathbb{F}_{2^\ell}$ defined by $$\text{Tr}(x)=x^{2^0}+x^{2^{1}}+\cdots+x^{2^{\ell-1}}$$ It is then possible to show the following

1. $\text{Tr}$ maps $\mathbb{F}_{2^\ell}$ into $\mathbb{F}_2$.
2. If $a\in\mathbb{F}_{2^\ell}$ is non-zero, then the mapping $f_a:\mathbb{F}_{2^\ell}\to\mathbb{F}_{2}$ defined by $f_a(x)=\text{Tr}(a\cdot x)$ is $\mathbb{F}_2$-linear and $\mathbb{E}_{x\sim\mathbb{F}_{2^\ell}}[f(x)]=\frac{1}{2}$.

Now, we consider the set $S=\{s(x,y,z):x,y,z\in\mathbb{F}_{2^\ell}\}$ such that we index the entries of $s(x,y,z)$ by $0\leq i,j$ such that $i+j\leq c\sqrt{n}$ ($c$ is a constant so that there are exactly $n$ entries). For such $x,y,z$ and $i,j$ we set $s(x,y,z)_{i,j}=\text{Tr}(x^iy^jz)$.

I want to show that for an appropriate choice of $\ell$, the set $S$ described above is an $\varepsilon$-biased set of size $O(n\sqrt{n}/\varepsilon^3)$.

Fix $\vec{0}\neq \tau\in\{0,1\}^n$, what we need to show is that (under good choice of $\ell$) $$\bigg|\mathbb{E}_{s\in S}\Big[(-1)^{\langle s,\tau\rangle}\Big]\bigg|\leq \varepsilon$$

Let $x,y,z\in\mathbb{F}_{2^\ell}$ and consider $\langle s(x,y,z),\tau\rangle$, I managed to show that (from $\mathbb{F}_2$-linearity above while indexing $\tau$ as we index $s(x,y,z)$) $$\langle s(x,y,z),\tau\rangle=\cdots=f_z\Big(\sum_{i,j}x^iy^j\tau_{i,j}\Big)$$ Finally, I thought of defining the bi-variate polynomial $p_\tau(x,y)=\sum\limits_{i,j}x^iy^j\tau_{i,j}$ and saying that since it is a non-zero polynomial of low degree at most $c\sqrt{n}$ it attains each value of $\mathbb{F}_{2^\ell}$ with multiplicity at most $c\sqrt{n}2^\ell$ (from Schwartz-Zippel), so $$\forall\alpha\in\mathbb{F}_{2^\ell}:\Pr\limits_{x,y\in\mathbb{F}_{2^\ell}}[p_\tau(x,y)=\alpha]\leq c\sqrt{n}/2^\ell$$

I want to use it but I am stuck..., maybe we can say that the distribution of $p_\tau(x,y)$ is close enough to $U_{\mathbb{F}_{2^\ell}}$ in statistical distance in order to infer that the expeced value of $f_z(p_\tau(x,y))$ is close enough to $1/2$?

Answer 1

recall that $$\langle s(x,y,z),\tau\rangle=\cdots=f_z\Big(\sum_{i,j}x^iy^j\tau_{i,j}\Big)$$

if we define $p_\tau(x,y)=\sum\limits_{i,j}x^iy^j\tau_{i,j}$, we have

$$\langle s(x,y,z),\tau\rangle=f_{p_\tau(x,y)}(z)$$

So, observe that whenever $p_\tau(x,y)\neq 0$ we win as $z$ is uniform and the expected value of $f_{p_\tau(x,y)}(z)$ is also $1/2$ which means that the contribution to the bias of these $x,y$ is zero.

Again from Schwartz-Zippel we have only $O(\sqrt{n}/2^\ell)$ many zeros of $p_\tau$ on them we lose the entire bias. So, the total bias is at most $O(\sqrt{n}/2^\ell)\stackrel{?}{\leq}\varepsilon$. Choosing $\ell=\Omega(\log(\sqrt{n}/\varepsilon))$ finishes the construction.