13 Bourgain Extractor
Given a distribution \(A\) on \(\mathbb {F}\), and a distribution \(B\) on \(\mathbb {F}^3\), we define a distribution \(L(A, B)\) by sampling \(x\) from \(A\), sampling \((y, z, w)\) from \(B\), and outputting \((x + y, z(x + y) + w)\).
We have \(L(f(A), g(B)) = L'(A\times B)\) with \(L'(x, y) = L(f(x), g(y))\).
Trivial with ?? and 9.14.
Given an integer \(N\) and a real number \(\beta \) such that \(p^\beta \leq N \leq p^{2 - \beta }\), and two nonempty sets \(A' \subseteq \mathbb {F}, B'\subseteq \mathbb {F}^3\), such that \(|B'| \leq N\) and the last two values in every element of \(B'\) are unique, then \(L(\operatorname{\operatorname {Uniform}}(A'), \operatorname{\operatorname {Uniform}}(B'))\) is \(\frac{C}{|A'| |B'|} N^{3/2 - \operatorname{\varepsilon }(\beta )}\)-close to \(N\) entropy.
TODO
TODO
TODO
TODO
TODO
\(M(x, y) = (x+y, 2(x+y), -((x+y)^2 + x^2 + y^2))\)
\(D(x,y) = (x, x^2 - y)\).
\(f \# (b \times b \times b) = D \# L(b, M \# (b \times b))\), with \(f(x, y, z) = (x+y+z, x^2+y^2+z^2)\).
If the maximum value of \(a\) is \(\varepsilon \), the maximum value of \(M \# (a \times a)\) is at most \(2 \varepsilon ^2\).
It suffices to show that every value can be obtained at most twice as an output of \(M\). Because the first value determines the second one, we can drop it, and then if want to get \((x_1, x_2)\) we need \(y_1 + y_2 = x_1, y_1 y_2 = x_1^2 + x_2 /2 \) (by calculation). A calculation can further show that \((x_1, x_2) \to -x_1\) is a bijection from this to the set of roots of \(y^2 + x_1 y + (x_1^2 + x_2/2)\), which is easily of size at most 2.
\(\beta = \frac{35686629198734976}{35686629198734977}\).
\(\alpha = \operatorname{\varepsilon }(\beta )\)
\(\alpha = \frac{11}2(1 - \beta )\).
By calculation.
For any source \(a\) with maximum value at most \(p^{-1/2 + 2/11 \alpha }\), \(D \# L(a, M \# (a \times a))\) is \(8 C p^{-2/11 \alpha }\)-close to \(p^{1+2/11 \alpha }\) entropy.
First, by 9.18, we can get rid of the \(D\). Now we want to apply 13.5. We already have a bound for the maximum value of \(a\), and using 13.9 we get a bound for the maximum value of \(M \# (a \times a)\). The last two values of a triple in the support \(M \# (a \times a)\) is an injective function by 8.10, as the first value is half of the second value for triples in the domain of \(M\).
\(C_b = \sqrt[64]{16C + 1}\).
For any two sources \(a, b\) with maximum value at most \(p^{-1/2 + 2/11 \alpha }\), and any non-trivial character \(\chi \),
First define \(a' = f \# a, b' = f \# b\) for \(f(x) = (x, x^2)\), then this is \(|\sum _x a'(x) \sum _y b'(y) \chi (x \cdot y)|\) Applying 12.9 3 times, then swapping \(x, y\) and doing it three more times, we can bound this by \( |\sum _x (b' + b' + b' + (b' - b' - b' - b' - b'))(x) \sum _y (a' + a' + a' + (a' - a' - a' - a' - a'))(y) \chi (x\cdot y)|^{1/64} \) Now we want to use 12.10. By 9.19, it suffices to show that \(b' + b' + b'\) and \(a' + a' + a'\) are close to high entropy. First, we can rewrite this by unfolding \(a'\) and \(b'\), using 9.11 and then 13.8. Finally, what we want is 13.13.
For any positive integer \(m\) and two sources \(a, b\) with maximum value at most \(p^{-1/2 + 2/11 \alpha }\), the statistical distance of \(f \# (a \times b)\) with \(f(x, y) = (xy + x^2 y^2 \bmod p) \bmod {m}\) to the uniform distribution is at most \(\varepsilon = C_b p^{-1/352 \alpha } \sqrt{m} (3 \ln (p) + 3) + \frac{m}{2p}\).
For any positive integer \(m\), the function \(f(x, y) = (xy + x^2 y^2 \bmod p) \bmod {m}\) is a two source extractor, with \(k = (1/2 - 2/11 \alpha ) \log (p), \varepsilon = C_b p^{-1/352 \alpha } \sqrt{m} (3 \ln (p) + 3) + \frac{m}{2p}\).
This is a simple restatement of 13.16