12 Lemmas about the Inner Product Extractor

Proposition 12.1

✓

For a character \(\chi \), \(\chi (a) = \chi (b)\) iff \(\chi (a-b) = 1\).

Proposition 12.2

✓

The inner product is commutitive.

Lemma 12.3

✓

If \(\chi \) is a non-trivial character of a field \(\mathbb {F}\), then there is an injective function from elements of \(\mathbb {F}^2\) (red generalize this to any dimension) to characters of it, defined by \(f(x)(y) = \chi (x \cdot y)\).

Proof ▶

It’s easy to see this maps values to additive characters. For injectivity, we have some value \(x\) such that \(\chi (x) \neq 1\). Now if \(f((a_1, a_2)) = f((b_1, b_2))\), if they aren’t equal, we can apply either \(\frac{x}{a_1 - b_1}\) or \(\frac{x}{a_2 - b_2}\), and then we get \(\chi (x) = 1\) by 12.1, a contradiction.

Lemma 12.4

✓

The function in the previous lemma is actually a bijection.

Proof ▶

By 12.3 and the cardinality being equal.

Theorem 12.5

✓

Note: the inner product and DFT here aren’t normalized.

\[ \sum _x{a(x)\sum _y{b(y) \chi (x \cdot y)}} = \langle a, P(\hat b) \rangle \]

where \(P\) reorders \(\hat b\) based on 12.4

Proof ▶

TODO

Theorem 12.6

✓

\[ |\sum _x{a(x)\sum _y{b(y) \chi (x \cdot y)}}|^2 \leq |A|^2 \lVert a \rVert _{\ell ^2}^2 \lVert b \rVert _{\ell ^2}^2 \]

Proof ▶

We use 12.5 to rewrite the sum, and then use Cauchy-Schwartz. Then we can undo the reordering and use Parseval’s theorem to get the desired result.

Theorem 12.7

✓

\[ |\sum _x{a(x)\sum _y{b(y) \chi (x \cdot y)}}| \leq |A| \lVert a \rVert _{\ell ^2} \lVert b \rVert _{\ell ^2} \]

Proof ▶

Simplying apply a square root to 12.6.

Theorem 12.8

✓

For any bilinear form \(F\) and character \(\chi \),

\[ |\sum _x{a(x) \sum _y{b(y) \chi (F(x, y))}}|^2 \leq |\sum _x{a(x) \sum _y{(b-b)(y) \chi (F(x, y))}}| \]

Proof ▶

\begin{align} |\sum _x{a(x) \sum _y{b(y) \chi (F(x, y))}}|^2 & \leq & (\sum _x{a(x) |\sum _y{b(y) \chi (F(x, y))} | })^2 \\ & \leq & \sum _x{a(x) |\sum _y{b(y) \chi (F(x, y))} |^2}\\ & =& \sum _x{a(x) (\sum _y{b(y) \chi (F(x, y))}) \bar{(\sum _y{b(y) \chi (F(x, y))})}} \\ & =& \sum _x{a(x) \sum _y \sum _{y'}{b(y) b(y’) \chi (F(x, y)) \chi (-F(x, y’))} } \\ & =& \sum _x{a(x) \sum _y \sum _{y'}{b(y) b(y’) \chi (F(x, y - y’))} } \\ & =& \sum _x{a(x) \sum _y{(b-b)(y) \chi (F(x, y))} } \\ \end{align}

Theorem 12.9

✓

For any bilinear form \(F\) and character \(\chi \),

\[ |\sum _x{a(x) \sum _y{b(y) \chi (F(x, y))}}| \leq \sqrt{|\sum _x{a(x) \sum _y{(b-b)(y) \chi (F(x, y))}}|} \]

Proof ▶

Trivial from 12.8.

Theorem 12.10

✓

If \(a\) and \(b\) are \(\varepsilon \)-close to \(N\) entropy, then

\[ |\sum _x{a(x) \sum _y{b(y) \chi (F(x, y))}}| \leq \frac{|A|}N + 2\varepsilon \]

Proof ▶

From the hypothesis and 9.21 we can look at \(a'(x) = \begin{cases} a(x) & a(x) \leq \frac1N \\ 0 & \frac1N {\lt} a(x)\end{cases}\), and similarly for \(b'\), and the difference would be at most \(2 \varepsilon \). Then we can apply 12.7 to get the result.