# Algebraic construction of $\varepsilon$-biased sets

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$$?

• Your notation is a bit strange to me. What the heck is a non-empty test $\tau$? A vector of nonzero hamming weight? And, what is your final goal, what's the upper bound you need in your last equation? – kodlu Jan 14 at 22:58
• @kodlu $\varepsilon$-biased distributions "fool" linear tests. Forget about the terminology "test", $\tau$ is just a vector in $\{0,1\}^n$ such that not all of its entries are $0$ (otherwise it is clear that the target expected value is not upper bounded by $\varepsilon$ but in fact is equal to $1$). – user621824 Jan 15 at 10:51

## 1 Answer

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.