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

- $ \text{Tr}$ maps $ \mathbb{F}_{2^\ell}$ into $ \mathbb{F}_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)$ .

So, fix a non-empty test $ \tau\in\{0,1\}^n$ , we need to show that $ $ \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 $ 2c\sqrt{n}$ it attains each value of $ \mathbb{F}_{2^\ell}$ with multiplicity at most $ 2c\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]=O(\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$ ?