11 XOR Lemma
Most of the material in here was taken from [Rao07].
For a function \(f\) with domain \(A\),
By 10.1 we have \(\lVert f \rVert _{\ell ^1} \leq \sqrt{|A|} \lVert f \rVert _{\ell ^2}\). Then using 10.2 this is \(|A| \lVert f \rVert _{L^2}\). By Parseval’s theorem, this is \(|A| \lVert \hat f \rVert _{\ell ^2}\). By 10.3, we have \(\lVert \hat f \rVert _{\ell ^2} \leq \sqrt{|A|} \lVert \hat f \rVert _{\ell ^\infty }\), which combines to the desired conclusion.
This is a very slight generalization of Lemma 4.3 in [Rao07]:
Let \(G, H\) be finite abelian groups. Let \(X\) be a function \(G \to \mathbb {R}\) such that for every nontrivial character \(\chi \), \(\hat{X}(\chi ) \leq \frac{\varepsilon }{|G|}\) and let \(U\) be the function with constant value \(E_x[X(x)]\). Let \(\sigma : G \to H\) be a function such that for every character \(\phi \), we have \(\lVert \widehat{\phi \circ \sigma } \rVert _{\ell ^1} \leq \tau \). Then \(\lVert \sigma \# X - \sigma \# U \rVert _{\ell ^1} \leq \tau \varepsilon \sqrt{|H|}\)
The proof is identical to the proof in [Rao07], using 11.1.
If \(a, b, n\) are reals, \(b, n\) are positive, and \(\frac ab \leq n\), then \(\frac ab \leq \frac{a+1}{b + 1/n}\).
By direct calculation (alternatively, this can be seen as an instance of the mediant inequality).
For a real \(x\), we have \(2 - |4x - 2| \leq |e^{x 2\pi i} - 1|\).
We have \(|e^{x 2\pi i} - 1| = |\cos (2 \pi x) - 1 + i \sin (2 \pi x)| = \sqrt{(\cos (2 \pi x) - 1)^2 + \sin ^2(2 \pi x)} = \sqrt{2 - 2\cos (2\pi x)}\). WLOG, it’s sufficient to consider the range \(0 \leq x \leq \frac12\). In this range, we have the inequality \(\cos (2 \pi x) \leq 1 - \frac{2}{\pi ^2} (2 \pi x)^2 = 1 - 8 x^2\), from which the result quickly follows.
In the following, we consider \(\sigma : \mathbb {Z}_N \to \mathbb {Z}_M\) defined as \(\sigma (x) = x \bmod M\).
We have \(\lVert \sigma \# U - U \rVert _{\ell ^1} \leq \frac nm\).
We can easily bound each difference by \(\frac1n\) using \((\sigma \# U)(x) = \frac{\lceil \frac{N - (x \bmod M)}{M} \rceil }N\) and \(U(x) = \frac{\frac NM}N\).
This is Lemma 4.4 in [Rao07] with explicit constants:
For any character \(\chi \) of \(\mathbb {Z}_M\), \(\lVert \widehat{\chi \circ \sigma }\rVert _{\ell ^1} \leq 6 \ln (N) + 6\)
Let \(\rho (x) = e^{x 2\pi i}\). We can find a value \(w\) such that \(\chi (x) = \rho (w x / M)\). Then \(\chi (\tau (x)) = \rho (w x / M)\). Now we have
We now want to claim \(|\sum _{x \in \mathbb {Z}_N} \rho (\frac{w N - t M}{N M})^x| \leq \frac{|\rho (\frac{w N - t M}{N M})^N - 1| + 1}{|\rho (\frac{w N - t M}{N M}) - 1| + 1/N}\) If \(\rho (\frac{w N - t M}{N M}) = 1\), this is trivially correct. Otherwise, this is a geometric sum, and then we can use 11.3. We easily have \(|\rho (\frac{w N - t M}{N M})^N - 1| + 1 \leq 3\), and now we need to bound \(\frac1N\sum _{t \in \mathbb {Z}_N} \frac1{|\rho (\frac{w N - t M}{N M}) - 1| + 1/N} = \frac1N\sum _{t \in \mathbb {Z}_N} \frac1{|\rho (\langle \frac{w N / M - t}{N}\rangle ) - 1| + 1/N}\). We can use 11.4 to bound this as \(\frac1N\sum _{t \in \mathbb {Z}_N} \frac1{(2 - |4(\langle \frac{w N / M - t}{N}\rangle ) - 2|) + 1/N}\) By writing \(w N / M = \lfloor w N / M \rfloor + \langle w N / M \rangle \), this is equal to \(\sum _{t \in \mathbb {Z}_N} \frac1{2N - |4(\langle {w N / M}\rangle + t) - 2N| + 1}\) Now by splitting to cases and calculating we can see that \(\frac1{2N - |4(\langle {w N / M}\rangle + t) - 2N| + 1} \leq \frac1{4t+1} + \frac1{4(n-1-t)+1}\). Applying bonuds on the harmonic sum, we get the desired result.
Let \(X\) be a distribution \(\mathbb {Z}_N\) such that for every nontrivial character \(\chi \), \(\hat{X}(\chi ) \leq \frac{\varepsilon }{|G|}\). Then \(\operatorname{\operatorname {SD}}(\sigma \# X, U) \leq \varepsilon \sqrt{M} (3\ln (N) + 3) + \frac{M}{2N}\).
[Rao07]: Rao, Anup. “An Exposition of Bourgain’s 2-Source Extractor.” Electron. Colloquium Comput. Complex. TR07 (2007): n. pag.